Quadcap Embeddable Database

com/quadcap/sql/Key.java

Go to the documentation of this file.

package com.quadcap.sql;

/* Copyright 1999 - 2003 Quadcap Software.  All rights reserved.
 *
 * This software is distributed under the Quadcap Free Software License.
 * This software may be used or modified for any purpose, personal or
 * commercial.  Open Source redistributions are permitted.  Commercial
 * redistribution of larger works derived from, or works which bundle
 * this software requires a "Commercial Redistribution License"; see
 * http://www.quadcap.com/purchase.
 *
 * Redistributions qualify as "Open Source" under  one of the following terms:
 *   
 *    Redistributions are made at no charge beyond the reasonable cost of
 *    materials and delivery.
 *
 *    Redistributions are accompanied by a copy of the Source Code or by an
 *    irrevocable offer to provide a copy of the Source Code for up to three
 *    years at the cost of materials and delivery.  Such redistributions
 *    must allow further use, modification, and redistribution of the Source
 *    Code under substantially the same terms as this license.
 *
 * Redistributions of source code must retain the copyright notices as they
 * appear in each source code file, these license terms, and the
 * disclaimer/limitation of liability set forth as paragraph 6 below.
 *
 * Redistributions in binary form must reproduce this Copyright Notice,
 * these license terms, and the disclaimer/limitation of liability set
 * forth as paragraph 6 below, in the documentation and/or other materials
 * provided with the distribution.
 *
 * The Software is provided on an "AS IS" basis.  No warranty is
 * provided that the Software is free of defects, or fit for a
 * particular purpose.  
 *
 * Limitation of Liability. Quadcap Software shall not be liable
 * for any damages suffered by the Licensee or any third party resulting
 * from use of the Software.
 */

import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.OutputStream;

import java.sql.SQLException;

import com.quadcap.sql.io.ObjectOutputStream;

import com.quadcap.sql.file.ByteUtil;
import com.quadcap.sql.file.SubPageManager;

import com.quadcap.sql.index.Comparator;

import com.quadcap.sql.types.KeyStream;
import com.quadcap.sql.types.Type;
import com.quadcap.sql.types.Value;
import com.quadcap.sql.types.ValueInteger;

import com.quadcap.util.Debug;
import com.quadcap.util.Util;

/**
 * Micro-optimized (-;) key serialization and comparison.  This class
 * is designed to eliminate copies and allocations during key comparison
 * and serialization operations.
 *
 * @author Stan Bailes
 */
public class Key extends Comparator {
    //#ifdef DEBUG
    static final boolean        paranoid                = false;
    //#endif

    boolean[]                   asc;

    public Key(int cnt) {
        asc = new boolean[cnt];
        for (int i = 0; i < cnt; i++) asc[i] = true;
    }

    public Key(boolean[] asc) {
        this.asc = asc;
    }

    public static byte[] makeKey(Tuple tuple, Row row, int[] map, long rowNum,
                                 boolean doRowNum) 
        throws SQLException
    {
        //#ifdef DEBUG
        if (false) {
            StringBuffer sb = new StringBuffer("makeKey(");
            sb.append(row.toString());
            sb.append(" (" + ((Object)row).toString());
            sb.append(", [");
            for (int i = 0; i < map.length; i++) {
                if (i>0) sb.append(',');
                sb.append(map[i]);
            }
            sb.append("], ");
            sb.append(SubPageManager.toString(rowNum));
            sb.append(", ");
            sb.append(doRowNum);
            sb.append(")");
            sb.append("\nFROM:\n");
            sb.append(Util.stackTrace());
            Debug.println(sb.toString());
        }
        //#endif
        try {
            ByteArrayOutputStream bos = new ByteArrayOutputStream();
            KeyStream out = new KeyStream(bos, Database.isCaseSensitive);
            //#ifdef DEBUG
            int cnt = 0;
            //#endif
            if (map != null) {
                //#ifdef DEBUG
                cnt = map.length;
                //#endif
                for (int i = 0; i < map.length; i++) {
                    int col = map[i];
                    Value v = row.item(col);
                    if (tuple != null) {
                        Column c = tuple.getColumn(col);
                        Type t = c.getType();
                        v = c.getType().convert(v);
                    }
                    v.serializeKey(out);
                }
            } else {
                //#ifdef DEBUG
                cnt = row.size();
                //#endif
                for (int i = 1; i <= row.size(); i++) {
                    Value v = row.item(i);
                    v.serializeKey(out);
                }
            }
            if (doRowNum) {
                out.writeLong(rowNum);
                //#ifdef DEBUG
                cnt++;
                //#endif
            }
            byte[] ret = bos.toByteArray();
            //#ifdef DEBUG
            if (paranoid) {
                Key k = new Key(cnt);
                k.checkKey(ret, 0, ret.length);
            }
            //#endif
            return ret;
        } catch (IOException e) {
            throw DbException.wrapThrowable(e);
        }
    }

    public static byte[] makeKey(Row row) throws SQLException {
        return makeKey(null, row, null, 0, false);
    }

    /**
     * Null comparison for GROUP BY
     */
    public boolean compareNulls(byte[] a, byte[] b) {
        // XXX hack 
        return compare(a, b) == 0;
    }

    public static final int COMPOUND            = KeyStream.COMPOUND;
    public static final int INTEGER             = KeyStream.INTEGER;
    public static final int STRING              = KeyStream.STRING;
    public static final int NULL                = KeyStream.NULL;               

    public int compare(byte[] a, byte[] b) {
        return compare(a, 0, a.length, b, 0, b.length);
    }

    //#ifdef DEBUG
    public final int compare(byte[] a, int aoff, int alen,
                             byte[] b, int boff, int blen) {
        try {
            if (paranoid) {
                checkKey(a, aoff, alen);
                checkKey(b, boff, blen);
            }
            int ret = compare2(a, aoff, alen, b, boff, blen);
            if (Trace.bit(6)) {
                Debug.println("Compare " + asc.length + " fields, ret=" + ret + ": " + 
                              toString(a, aoff, alen) + 
                              "(" + Util.hexBytes(a, aoff, alen) + ") " +
                              " vs " + 
                              toString(b, boff, blen) +
                              "(" + Util.hexBytes(b, boff, blen) + ") ");
                //Debug.println(Util.stackTrace());
            }
            return ret;
        } catch (RuntimeException t) {
            Debug.print(t);
            Debug.println("asc.len = " + asc.length);
            Debug.println("a = " + toString(a, aoff, alen));
            Debug.println("a = " + Util.hexBytes(a, aoff, alen));
            Debug.println("b = " + toString(b, boff, blen));
            Debug.println("b = " + Util.hexBytes(b, boff, blen));
            throw t;
        }
    }

    public void checkKey(byte[] buf, int off, int len) {
        if (getKeyLen(buf, off) != len) {
            Debug.println(Util.strBytes(buf, off, len));
            Debug.println(toString(buf, off, len));
            throw new RuntimeException("bad key len: " + 
                                       getKeyLen(buf, off) + " vs " +
                                       len);
        }
    }

    final int compare2
    //#else
//-    public final int compare
    //#endif
    (byte[] a, int aoff, int alen,
     byte[] b, int boff, int blen)
    {
        int i = 0;
        int askip = 0;
        int bskip = 0;
        int scalar = 0;
        while (i < asc.length) {
            int ac = a[aoff++] & 0xff;
            int bc = b[boff++] & 0xff;
            final int atype = ac & 3;
            final int btype = bc & 3;
            int al = (ac >> 2) & 0x1f;
            int bl = (bc >> 2) & 0x1f;
            if ((ac & 0x80) != 0) {
                al <<= 8;
                al |= (a[aoff++] & 0xff);
            }
            if ((bc & 0x80) != 0) {
                bl <<= 8;
                bl |= (b[boff++] & 0xff);
            }
            //Debug.println("Field " + i + ": " + atype + " - " + btype);
            //Debug.println("ac/al = " + ac + "/" + al + ", bc/bl = " + bc + "/" + bl);
            switch ((atype << 2) | btype) {
            case (COMPOUND << 2) | COMPOUND:
                askip = al;
                bskip = bl;
                break;
            case (INTEGER << 2) | INTEGER:
                int signMask = 0xffffffff;
                if (al > bl) {
                    int ab = a[aoff++];
                    if (ab != 0) return (ab < 0 ? -1 : 1) * (asc[i] ? 1 : -1);
                    while (--al > bl) {
                        if (a[aoff++] != 0) {
                            return asc[i] ? 1 : -1;
                        }
                    }
                    signMask = 0xff;
                }

                if (bl > al) {
                    int bb = b[boff++];
                    if (bb != 0) return (bb < 0 ? 1 : -1) * (asc[i] ? 1 : -1);
                    while (--bl > al) {
                        if (b[boff++] != 0) {
                            return asc[i] ? -1 : 1;
                        }
                    }
                    signMask = 0xff;
                }

                int neg = (a[aoff] < 0) ? -1 : 1;
                int rneg = 1;
                while (al-- > 0) {
                    int ab = a[aoff++] & signMask;
                    int bb = b[boff++] & signMask;
                    if (ab != bb) {
                        int xa = a[aoff-1];
                        return (ab < bb ? 1 : -1) * (asc[i] ? -1 : 1) * rneg;
                    }
                    rneg = neg;
                    signMask = 0xff;
                }
                break;
            case (STRING << 2) | STRING:
                while (al > 0 && bl > 0) {
                    int ab = a[aoff++] & 0xff;
                    int bb = b[boff++] & 0xff;
                    if (ab != bb) {
                        return (ab < bb ? 1 : -1) * (asc[i] ? -1 : 1);
                    }
                    al--;
                    bl--;
                }
                while (al-- > 0) {
                    if (a[aoff++] != 0) return asc[i] ? 1 : -1;
                }
                while (bl-- > 0) {
                    if (b[boff++] != 0) return asc[i] ? -1 : 1;
                }
                break;
            case (NULL << 2) | NULL:
                // length == 0: first null, otherwise last null
                if (al == 0) {
                    if (bl != 0) return -1;
                } else {
                    if (bl == 0) return 1;
                }
                break;
            case (NULL << 2) | COMPOUND:
            case (NULL << 2) | INTEGER:
            case (NULL << 2) | STRING:
                return al == 0 ? -1 : 1;
            case (COMPOUND << 2) | NULL:
            case (INTEGER << 2) | NULL:
            case (STRING << 2) | NULL:
                return bl == 0 ? 1 : -1;

            case (COMPOUND << 2) | INTEGER:
                askip = al;
                bskip = 1;
                boff--;
                break;
            case (INTEGER << 2) | COMPOUND:
                bskip = bl;
                askip = 1;
                aoff--;
                break;

            case (STRING << 2) | INTEGER:
                return 1;
            case (INTEGER << 2) | STRING:
                return -1;

            default:
                throw new RuntimeException("Cardinality error");
            }
            askip--;
            bskip--;
            if (askip < 0) {
                if (bskip < 0) {
                    // end of both compound fields
                    i++;
                } else {
                    // end of a, more fields left in b
                    while (bskip-- >= 0) {
                        bc = b[boff++] & 0xff;
                        bl = (bc >> 2) & 0x1f;
                        if ((bc & 0x80) != 0) {
                            bc <<= 8;
                            bc |= (b[boff++] & 0xff);
                        }
                        for (int j = 0; j < bl; j++) {
                            if (b[boff++] != 0) return -1;
                        }
                        i++;
                    }
                }
            } else {
                if (bskip < 0) {
                    // end of b, more fields left in a
                    while (askip-- >= 0) {
                        ac = a[aoff++] & 0xff;
                        al = (ac >> 2) & 0x1f;
                        if ((ac & 0x80) != 0) {
                            ac <<= 8;
                            ac |= (a[aoff++] & 0xff);
                        }
                        for (int j = 0; j < al; j++) {
                            if (a[aoff++] != 0) return 1;
                        }
                        i++;
                    }
                } else {
                    // next compound field
                }
            }
        }
        return 0;
    }

    public int getKeyLen(byte[] a, int aoff) {
        int start = aoff;
        int i = 0;
        int skip = 0;
        while (i < asc.length) {
            int ac = a[aoff++] & 0xff;
            final int atype = ac & 3;
            int al = (ac >> 2) & 0x1f;
            if ((ac & 0x80) != 0) {
                al <<= 8;
                al |= (a[aoff++] & 0xff);
            }
            switch (atype) {
            case NULL:
                break;
            case INTEGER:
            case STRING:
                aoff += al;
                break;
            case COMPOUND:
                skip = al;
                break;
            }
            skip--;
            if (skip < 0) i++;
        }
        return aoff - start;
    }

    //#ifdef DEBUG
    public static String toStringHelper(byte[] key) {
        return toStringHelper(key, 0, key.length);
    }
    
    public String toString(byte[] key, int off, int xlen) {
        return toStringHelper(key, off, xlen);
    }
    
    public static String toStringHelper(byte[] key, int off, int xlen) {
        StringBuffer sb = new StringBuffer();
        int lim = off + xlen;
        String delim = "";
        String sdelim = "";
        int clen = -1;
        while (off < lim) {
            clen--;
            sb.append(delim);
            sb.append(sdelim);
            if (clen > 0) sdelim =",";
            delim = ", ";
            int c = key[off++] & 0xff;
            int type = c & 3;
            int len = (c >> 2) & 0x1f;
            if ((c & 0x80) != 0) {
                len <<= 8;
                len |= key[off++];
            }
            //Debug.println("TYPE: " + type + ", off = " + off +
            //              ", len = " + len);
            switch (type) {
            case COMPOUND:
                sb.append("{");
                sdelim = "";
                clen = len;
                break;
            case INTEGER:
                sb.append("I(");
                sb.append(Util.hexBytes(key, off, len));
                sb.append(")");
                off += len;
                break;
            case STRING:
                sb.append("S(");
                //sb.append(Util.hexBytes(key, off, len));
                try {
                    sb.append(new String(key, off, len));
                } catch (Throwable t) {
                    sb.append("key[" + off + ":" + len + "]:*****(" + new String(key) + ")");
                }
                sb.append(")");
                off += len;
                break;
            case NULL:
                sb.append("NULL");
                break;
            }
            if (clen == 0) {
                sb.append("}");
                sdelim = "";
            }
        }
        return sb.toString();
    }

    public static void test1() throws IOException {
        com.quadcap.sql.file.BlockFile f =
            new com.quadcap.sql.file.BlockFile("test1.bf", "rw",
                                               new java.util.Properties(),
                                               4096, 256);
        long root = f.newPage();
        Key key = new Key(1);
        com.quadcap.sql.index.Btree tree = new com.quadcap.sql.index.Btree(f, key, root, true);
        byte[] vk = new byte[5];
        for (int i = 0; i < 40000; i++) {
            byte[] r = makeRandomKey();
            ByteUtil.putInt(vk, 0, i);
            tree.set(r, vk);
            if ((i % 1000) == 0) System.out.print(".");
        }
    }

    static java.util.Random random = new java.util.Random(666);

    public static byte[] makeRandomKey() throws IOException {
        ByteArrayOutputStream bos = new ByteArrayOutputStream();
        KeyStream k = new KeyStream(bos, true);
        StringBuffer sb = new StringBuffer();
        int lim = 40 + random.nextInt(50);
        for (int i = 0; i < lim; i++) {
            sb.append((char)random.nextInt(255));
        }
        k.writeChars(sb.toString());
        return bos.toByteArray();
    }

    public static void main(String[] args) {
        try {
            test1();
        } catch (Exception e) {
            Debug.print(e);
        }
    }
    //#endif
}