btreepage.java

这个是perst-269.zip下面的SOURCECODE,和大家分享了。

package org.garret.perst.impl;
import  org.garret.perst.*;
import  java.util.ArrayList;

class BtreePage { 
    static final int firstKeyOffs = 4;
    static final int keySpace = Page.pageSize - firstKeyOffs;
    static final int strKeySize = 8;    
    static final int maxItems = keySpace / 4;    

    static int getnItems(Page pg) { 
        return Bytes.unpack2(pg.data, 0);
    }
    static int getSize(Page pg) { 
        return Bytes.unpack2(pg.data, 2);
    }
    static int getKeyStrOid(Page pg, int index) {
                return Bytes.unpack4(pg.data, firstKeyOffs + index*8);
    }
    static int getKeyStrSize(Page pg, int index) { 
        return Bytes.unpack2(pg.data, firstKeyOffs + index*8+4);
    }
    static int getKeyStrOffs(Page pg, int index) { 
        return Bytes.unpack2(pg.data, firstKeyOffs + index*8+6);
    }

    static int getReference(Page pg, int index) { 
        return Bytes.unpack4(pg.data, firstKeyOffs + index*4);
    }
    
    static void setnItems(Page pg, int nItems) { 
        Bytes.pack2(pg.data, 0, (short)nItems);
    }
    static void setSize(Page pg, int size) { 
        Bytes.pack2(pg.data, 2, (short)size);
    }
    static void setKeyStrOid(Page pg, int index, int oid) { 
        Bytes.pack4(pg.data, firstKeyOffs + index*8, oid);
    }
    static void setKeyStrSize(Page pg, int index, int size) { 
        Bytes.pack2(pg.data, firstKeyOffs + index*8+4, (short)size);
    }
    static void setKeyStrOffs(Page pg, int index, int offs) { 
        Bytes.pack2(pg.data, firstKeyOffs + index*8+6, (short)offs);
    }
    static void setKeyStrChars(Page pg, int offs, char[] str) { 
        int len = str.length;
        for (int i = 0; i < len; i++) { 
            Bytes.pack2(pg.data, firstKeyOffs + offs, (short)str[i]);
            offs += 2;
        }
    }
    static void setKeyBytes(Page pg, int offs, byte[] bytes) { 
        System.arraycopy(bytes, 0, pg.data, firstKeyOffs + offs, bytes.length);
    }
    static void setReference(Page pg, int index, int oid) { 
        Bytes.pack4(pg.data, firstKeyOffs + index*4, oid);
    }

    final static int compare(Key key, Page pg, int i) { 
        long   i8;
        int    i4;
        float  r4;
        double r8;
        switch (key.type) {
          case ClassDescriptor.tpBoolean:
          case ClassDescriptor.tpByte:
            return (byte)key.ival - pg.data[BtreePage.firstKeyOffs + i];
          case ClassDescriptor.tpShort:
            return (short)key.ival - Bytes.unpack2(pg.data, BtreePage.firstKeyOffs + i*2);
          case ClassDescriptor.tpChar:
            return (char)key.ival - (char)Bytes.unpack2(pg.data, BtreePage.firstKeyOffs + i*2);
          case ClassDescriptor.tpObject:
          case ClassDescriptor.tpInt:
            i4 = Bytes.unpack4(pg.data, BtreePage.firstKeyOffs + i*4);
            return key.ival < i4 ? -1 : key.ival == i4 ? 0 : 1;
          case ClassDescriptor.tpLong:
          case ClassDescriptor.tpDate:
            i8 = Bytes.unpack8(pg.data, BtreePage.firstKeyOffs + i*8);
            return key.lval < i8 ? -1 : key.lval == i8 ? 0 : 1;
          case ClassDescriptor.tpFloat:
            r4 = Float.intBitsToFloat(Bytes.unpack4(pg.data, 
                                                    BtreePage.firstKeyOffs + i*4));
            return key.dval < r4 ? -1 : key.dval == r4 ? 0 : 1;
          case ClassDescriptor.tpDouble:
            r8 = Double.longBitsToDouble(Bytes.unpack8(pg.data, 
                                                       BtreePage.firstKeyOffs + i*8));
            return key.dval < r8 ? -1 : key.dval == r8 ? 0 : 1;
        }
        Assert.failed("Invalid type");
        return 0;
    }


    final static int compareStr(Key key, Page pg, int i) { 
        char[] chars = (char[])key.oval;
        int alen = chars.length;
        int blen = BtreePage.getKeyStrSize(pg, i);
        int minlen = alen < blen ? alen : blen;
        int offs = BtreePage.getKeyStrOffs(pg, i) + BtreePage.firstKeyOffs;
        byte[] b = pg.data;
        for (int j = 0; j < minlen; j++) { 
            int diff = chars[j] - (char)Bytes.unpack2(b, offs);
            if (diff != 0) { 
                return diff;
            }
            offs += 2;
        }
        return alen - blen;
    }

    final static int comparePrefix(char[] key, Page pg, int i) { 
        int alen = key.length;
        int blen = BtreePage.getKeyStrSize(pg, i);
        int minlen = alen < blen ? alen : blen;
        int offs = BtreePage.getKeyStrOffs(pg, i) + BtreePage.firstKeyOffs;
        byte[] b = pg.data;
        for (int j = 0; j < minlen; j++) { 
            int diff = key[j] - (char)Bytes.unpack2(b, offs);
            if (diff != 0) { 
                return diff;
            }
            offs += 2;
        }
        return minlen - blen;
    }


    static boolean find(StorageImpl db, int pageId, Key firstKey, Key lastKey, 
                        Btree tree, int height, ArrayList result)
    {
        Page pg = db.getPage(pageId);
        int l = 0, n = getnItems(pg), r = n;
        int oid;
        height -= 1;
        try { 
            if (tree.type == ClassDescriptor.tpString) { 
                if (firstKey != null) { 
                    while (l < r)  {
                        int i = (l+r) >> 1;
                        if (compareStr(firstKey, pg, i) >= firstKey.inclusion) {
                            l = i + 1; 
                        } else { 
                            r = i;
                        }
                    }
                    Assert.that(r == l); 
                }
                if (lastKey != null) { 
                    if (height == 0) { 
                        while (l < n) { 
                            if (-compareStr(lastKey, pg, l) >= lastKey.inclusion) { 
                                return false;
                            }
                            oid = getKeyStrOid(pg, l);
                            result.add(db.lookupObject(oid, null));
                            l += 1;
                        }
                    } else { 
                        do {
                            if (!find(db, getKeyStrOid(pg, l), firstKey, lastKey, tree, height, result)) {
                                return false;
                            }
                            if (l == n) { 
                                return true;
                            }
                        } while (compareStr(lastKey, pg, l++) >= 0);
                        return false;
                    }
                } else { 
                    if (height == 0) { 
                        while (l < n) { 
                            oid = getKeyStrOid(pg, l); 
                            result.add(db.lookupObject(oid, null));
                            l += 1;
                        }
                    } else {
                        do {
                            if (!find(db, getKeyStrOid(pg, l), firstKey, lastKey, tree, height, result)) {
                                return false;
                            }
                        } while (++l <= n);
                    }
                }
            } else if (tree.type == ClassDescriptor.tpArrayOfByte) { 
                if (firstKey != null) { 
                    while (l < r)  {
                        int i = (l+r) >> 1;
                        if (tree.compareByteArrays(firstKey, pg, i) >= firstKey.inclusion) {
                            l = i + 1; 
                        } else { 
                            r = i;
                        }
                    }
                    Assert.that(r == l); 
                }
                if (lastKey != null) { 
                    if (height == 0) { 
                        while (l < n) { 
                            if (-tree.compareByteArrays(lastKey, pg, l) >= lastKey.inclusion) { 
                                return false;
                            }
                            oid = getKeyStrOid(pg, l);
                            result.add(db.lookupObject(oid, null));
                            l += 1;
                        }
                    } else { 
                        do {
                            if (!find(db, getKeyStrOid(pg, l), firstKey, lastKey, tree, height, result)) {
                                return false;
                            }
                            if (l == n) { 
                                return true;
                            }
                        } while (tree.compareByteArrays(lastKey, pg, l++) >= 0);
                        return false;
                    }
                } else { 
                    if (height == 0) { 
                        while (l < n) { 
                            oid = getKeyStrOid(pg, l); 
                            result.add(db.lookupObject(oid, null));
                            l += 1;
                        }
                    } else {
                        do {
                            if (!find(db, getKeyStrOid(pg, l), firstKey, lastKey, tree, height, result)) {
                                return false;
                            }
                        } while (++l <= n);
                    }
                }
            } else { 
                if (firstKey != null) {
                    while (l < r)  {
                        int i = (l+r) >> 1;
                        if (compare(firstKey, pg, i) >= firstKey.inclusion) {
                            l = i+1;
                        } else {
                            r = i;
                        }
                    }
                    Assert.that(r == l);
                }
                if (lastKey != null) {
                    if (height == 0) {
                        while (l < n) {
                            if (-compare(lastKey, pg, l) >= lastKey.inclusion) {
                                return false;
                            }
                            oid = getReference(pg, maxItems-1-l);
                            result.add(db.lookupObject(oid, null));
                            l += 1;
                        }
                        return true;
                    } else {
                        do {
                            if (!find(db, getReference(pg, maxItems-1-l), firstKey, lastKey, tree, height, result)) {
                                return false;
                            }
                            if (l == n) {
                                return true;
                            }
                        } while (compare(lastKey, pg, l++) >= 0);
                        return false;
                    }
                } 
                if (height == 0) { 
                    while (l < n) { 
                        oid = getReference(pg, maxItems-1-l);
                        result.add(db.lookupObject(oid, null));
                        l += 1;
                    }
                } else { 
                    do {
                        if (!find(db, getReference(pg, maxItems-1-l), firstKey, lastKey, tree, height, result)) {
                            return false;
                        }
                    } while (++l <= n);
                }
            }    
        } finally { 
            db.pool.unfix(pg);
        }
        return true;
    }    


    static boolean prefixSearch(StorageImpl db, int pageId, char[] key,
                                int height, ArrayList result)
    {
        Page pg = db.getPage(pageId);
        int l = 0, n = getnItems(pg), r = n;
        int oid;
        height -= 1;
        try { 
            while (l < r)  {
                int i = (l+r) >> 1;
                if (comparePrefix(key, pg, i) > 0) {