rndbtree.java

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

            return new Byte(data[i]);
        }

        Key getKey(int i) { 
            return new Key(data[i]);
        }

        BtreePage clonePage() { 
            return new BtreePageOfByte(getStorage());
        }

        int compare(Key key, int i) {
            return (byte)key.ival - data[i];
        }

        void insert(BtreeKey key, int i) { 
            items.setObject(i, key.node);
            data[i] = (byte)key.key.ival;
        }

        BtreePageOfByte(Storage s) {
            super(s, MAX_ITEMS);
            data = new byte[MAX_ITEMS];
        }

        BtreePageOfByte() {}
    }

    static class BtreePageOfBoolean extends BtreePageOfByte { 
        Key getKey(int i) { 
            return new Key(data[i] != 0);
        }

        Object getKeyValue(int i) { 
            return Boolean.valueOf(data[i] != 0);
        }

        BtreePage clonePage() { 
            return new BtreePageOfBoolean(getStorage());
        }

        BtreePageOfBoolean() {}
        
        BtreePageOfBoolean(Storage s) {
            super(s);
        }        
    }

    static class BtreePageOfShort extends BtreePage { 
        short[] data; 

        static final int MAX_ITEMS = BTREE_PAGE_SIZE / (4 + 4 + 2);
            
        Object getData() { 
            return data;
        }

        Key getKey(int i) { 
            return new Key(data[i]);
        }

        Object getKeyValue(int i) { 
            return new Short(data[i]);
        }

        BtreePage clonePage() { 
            return new BtreePageOfShort(getStorage());
        }

        int compare(Key key, int i) {
            return (short)key.ival - data[i];
        }

        void insert(BtreeKey key, int i) { 
            items.setObject(i, key.node);
            data[i] = (short)key.key.ival;
        }

        BtreePageOfShort(Storage s) {
            super(s, MAX_ITEMS);
            data = new short[MAX_ITEMS];
        }

        BtreePageOfShort() {}
    }

    static class BtreePageOfChar extends BtreePage { 
        char[] data; 

        static final int MAX_ITEMS = BTREE_PAGE_SIZE / (4 + 4 + 2);
            
        Object getData() { 
            return data;
        }

        Key getKey(int i) { 
            return new Key(data[i]);
        }

        Object getKeyValue(int i) { 
            return new Character(data[i]);
        }

        BtreePage clonePage() { 
            return new BtreePageOfChar(getStorage());
        }

        int compare(Key key, int i) {
            return (char)key.ival - data[i];
        }

        void insert(BtreeKey key, int i) { 
            items.setObject(i, key.node);
            data[i] = (char)key.key.ival;
        }

        BtreePageOfChar(Storage s) {
            super(s, MAX_ITEMS);
            data = new char[MAX_ITEMS];
        }

        BtreePageOfChar() {}
    }

    static class BtreePageOfInt extends BtreePage { 
        int[] data; 

        static final int MAX_ITEMS = BTREE_PAGE_SIZE / (4 + 4 + 4);
            
        Object getData() { 
            return data;
        }

        Key getKey(int i) { 
            return new Key(data[i]);
        }

        Object getKeyValue(int i) { 
            return new Integer(data[i]);
        }

        BtreePage clonePage() { 
            return new BtreePageOfInt(getStorage());
        }

        int compare(Key key, int i) {
            return key.ival - data[i];
        }

        void insert(BtreeKey key, int i) { 
            items.setObject(i, key.node);
            data[i] = key.key.ival;
        }

        BtreePageOfInt(Storage s) { 
            super(s, MAX_ITEMS);
            data = new int[MAX_ITEMS];
        }

        BtreePageOfInt() {}
    }

    static class BtreePageOfLong extends BtreePage { 
        long[] data; 

        static final int MAX_ITEMS = BTREE_PAGE_SIZE / (4 + 4 + 8);
            
        Object getData() { 
            return data;
        }

        Key getKey(int i) { 
            return new Key(data[i]);
        }

        Object getKeyValue(int i) { 
            return new Long(data[i]);
        }

        BtreePage clonePage() { 
            return new BtreePageOfLong(getStorage());
        }

        int compare(Key key, int i) {
            return key.lval < data[i] ?  -1 : key.lval == data[i] ? 0 : 1;
        }

        void insert(BtreeKey key, int i) { 
            items.setObject(i, key.node);
            data[i] = key.key.lval;
        }

        BtreePageOfLong(Storage s) { 
            super(s, MAX_ITEMS);
            data = new long[MAX_ITEMS];
        }

        BtreePageOfLong() {}
    }

    static class BtreePageOfFloat extends BtreePage { 
        float[] data; 

        static final int MAX_ITEMS = BTREE_PAGE_SIZE / (4 + 4 + 4);
            
        Object getData() { 
            return data;
        }

        Key getKey(int i) { 
            return new Key(data[i]);
        }

        Object getKeyValue(int i) { 
            return new Float(data[i]);
        }

        BtreePage clonePage() { 
            return new BtreePageOfFloat(getStorage());
        }

        int compare(Key key, int i) {
            return (float)key.dval < data[i] ? -1 : (float)key.dval == data[i] ? 0 : 1;
        }

        void insert(BtreeKey key, int i) { 
            items.setObject(i, key.node);
            data[i] = (float)key.key.dval;
        }

        BtreePageOfFloat(Storage s) {
            super(s, MAX_ITEMS);
            data = new float[MAX_ITEMS];
        }

        BtreePageOfFloat() {}
    }

    static class BtreePageOfDouble extends BtreePage { 
        double[] data; 

        static final int MAX_ITEMS = BTREE_PAGE_SIZE / (4 + 4 + 8);
            
        Object getData() { 
            return data;
        }

        Key getKey(int i) { 
            return new Key(data[i]);
        }

        Object getKeyValue(int i) { 
            return new Double(data[i]);
        }

        BtreePage clonePage() { 
            return new BtreePageOfDouble(getStorage());
        }

        int compare(Key key, int i) {
            return key.dval < data[i] ? -1 : key.dval == data[i] ? 0 : 1;
        }

        void insert(BtreeKey key, int i) { 
            items.setObject(i, key.node);
            data[i] = key.key.dval;
        }

        BtreePageOfDouble(Storage s) {
            super(s, MAX_ITEMS);
            data = new double[MAX_ITEMS];
        }

        BtreePageOfDouble() {}
    }


    static class BtreePageOfObject extends BtreePage { 
        Link data; 

        static final int MAX_ITEMS = BTREE_PAGE_SIZE / (4 + 4 + 4);
            
        Object getData() { 
            return data.toRawArray();
        }

        Key getKey(int i) { 
            return new Key(data.getRaw(i));
        }

        Object getKeyValue(int i) { 
            return data.get(i);
        }

        BtreePage clonePage() { 
            return new BtreePageOfObject(getStorage());
        }

        int compare(Key key, int i) {
            return key.ival - data.getRaw(i).getOid();
        }

        void insert(BtreeKey key, int i) { 
            items.setObject(i, key.node);
            data.setObject(i, (IPersistent)key.key.oval);
        }

        BtreePageOfObject(Storage s) {
            super(s, MAX_ITEMS);
            data = s.createLink(MAX_ITEMS);
            data.setSize(MAX_ITEMS);
        }

        BtreePageOfObject() {}
    }

    static class BtreePageOfString extends BtreePage { 
        String[] data; 

        static final int MAX_ITEMS = 100;
            
        Object getData() { 
            return data;
        }

        Key getKey(int i) { 
            return new Key(data[i]);
        }

        Object getKeyValue(int i) { 
            return data[i];
        }

        void clearKeyValue(int i) {
            data[i] = null;
        }
        
        BtreePage clonePage() { 
            return new BtreePageOfString(getStorage());
        }

        int compare(Key key, int i) {
            return ((String)key.oval).compareTo(data[i]);
        }

        void insert(BtreeKey key, int i) { 
            items.setObject(i, key.node);
            data[i] = (String)key.key.oval;
        }

        void memset(int i, int len) { 
            while (--len >= 0) { 
                items.setObject(i, null);
                data[i] = null;
                i += 1;
            }
        }

        boolean prefixSearch(String key, int height, ArrayList result)
        {
            int l = 0, n = nItems, r = n;
            height -= 1;
            while (l < r)  {
                int i = (l+r) >> 1;
                if (!key.startsWith(data[i]) && key.compareTo(data[i]) > 0) {
                    l = i + 1; 
                } else { 
                    r = i;
                }
            }
            Assert.that(r == l); 
            if (height == 0) { 
                while (l < n) { 
                    if (key.compareTo(data[l]) < 0) { 
                        return false;
                    }
                    result.add(items.get(l));
                    l += 1;
                }
            } else { 
                do {
                    if (!((BtreePageOfString)items.get(l)).prefixSearch(key, height, result)) {
                        return false;
                    }
                    if (l == n) { 
                        return true;
                    }
                } while (key.compareTo(data[l++]) >= 0);
                return false;
            }
            return true;
        }    


        BtreePageOfString(Storage s) {
            super(s, MAX_ITEMS);
            data = new String[MAX_ITEMS];
        }

        BtreePageOfString() {}
    }

    static class BtreePageOfRaw extends BtreePage { 
        Object data; 

        static final int MAX_ITEMS = 100;
            
        Object getData() { 
            return data;
        }