rndbtree.java

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

        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.set(i, key.node);
            data.set(i, (IPersistent)key.key.oval);
        }

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

        public BtreePageOfObject() {}
    }

    static class BtreePageOfString extends BtreePage { 
        String[] data; 

        public void writeObject(IOutputStream out) {
            super.writeObject(out);
            out.writeArrayOfString(data);
        }
        
        public void readObject(IInputStream in) {
            super.readObject(in);
            data = in.readArrayOfString();
        }

        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.set(i, key.node);
            data[i] = (String)key.key.oval;
        }

        void memset(int i, int len) { 
            while (--len >= 0) { 
                items.set(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];
        }

        public BtreePageOfString() {}
    }


    static int checkType(int elemType) { 
        if (elemType > Types.Object) { 
            throw new StorageError(StorageError.UNSUPPORTED_INDEX_TYPE, Types.getSignature(elemType));
        }
        return elemType;
    }
       
    RndBtree(int elemType, boolean unique) {
        this.unique = unique;
        type = checkType(elemType);
    }

    static final int op_done      = 0;
    static final int op_overflow  = 1;
    static final int op_underflow = 2;
    static final int op_not_found = 3;
    static final int op_duplicate = 4;
    static final int op_overwrite = 5;

    Key checkKey(Key key) { 
        if (key != null) { 
            if (key.type != type) { 
                throw new StorageError(StorageError.INCOMPATIBLE_KEY_TYPE);
            }
            if (type == Types.Object && key.ival == 0 && key.oval != null) { 
                IPersistent obj = (IPersistent)key.oval;
                getStorage().makePersistent(obj);
                key = new Key(obj, key.inclusion != 0);
            }
            if (key.oval instanceof char[]) { 
                key = new Key(new String((char[])key.oval), key.inclusion != 0);
            }
        }
        return key;
    }    

    public IPersistent get(Key key) { 
        key = checkKey(key);
        if (root != null) { 
            ArrayList list = new ArrayList();
            root.find(key, key, height, list);
            if (list.size() > 1) { 
                throw new StorageError(StorageError.KEY_NOT_UNIQUE);
            } else if (list.size() == 0) { 
                return null;
            } else { 
                return (IPersistent)list.get(0);
            }
        }
        return null;
    }

    static final IPersistent[] emptySelection = new IPersistent[0];

    public IPersistent[] prefixSearch(String key) { 
        if (Types.String != type) { 
            throw new StorageError(StorageError.INCOMPATIBLE_KEY_TYPE);
        }
        if (root != null) { 
            ArrayList list = new ArrayList();
            ((BtreePageOfString)root).prefixSearch(key, height, list);
            if (list.size() != 0) { 
                return (IPersistent[])list.toArray(new IPersistent[list.size()]);
            }
        }
        return emptySelection;
    }

    public IPersistent[] get(Key from, Key till) {
        if (root != null) { 
            ArrayList list = new ArrayList();
            root.find(checkKey(from), checkKey(till), height, list);
            if (list.size() != 0) { 
                return (IPersistent[])list.toArray(new IPersistent[list.size()]);
            }
        }
        return emptySelection;
    }

    public boolean put(Key key, IPersistent obj) {
        return insert(key, obj, false) == null;
    }

    public IPersistent set(Key key, IPersistent obj) {
        return insert(key, obj, true);
    }

    final void allocateRootPage(BtreeKey ins, int height) { 
        Storage s = getStorage();
        BtreePage newRoot = null;
        switch (type) { 
        case Types.Byte:
            newRoot = new BtreePageOfByte(s);
            break;
        case Types.Short:
            newRoot = new BtreePageOfShort(s);
            break;
        case Types.Char:
            newRoot = new BtreePageOfChar(s);
            break;
        case Types.Boolean:
            newRoot = new BtreePageOfBoolean(s);
            break;
        case Types.Int:
            newRoot = new BtreePageOfInt(s);
            break;
        case Types.Long:
            newRoot = new BtreePageOfLong(s);
            break;
        case Types.Float:
            newRoot = new BtreePageOfFloat(s);
            break;
        case Types.Double:
            newRoot = new BtreePageOfDouble(s);
            break;
        case Types.Object:
            newRoot = new BtreePageOfObject(s);
            break;
        case Types.String:
            newRoot = new BtreePageOfString(s);
            break;
        default:
            Assert.failed("Invalid type");
        }
        newRoot.insert(ins, 0, height);
        newRoot.items.set(1, root);
        if (height != 0) { 
            newRoot.countChildren(1, height);
        }
        newRoot.nItems = 1;
        root = newRoot;
    }

    final IPersistent insert(Key key, IPersistent obj, boolean overwrite) {
        BtreeKey ins = new BtreeKey(checkKey(key), obj);
        if (root == null) { 
            allocateRootPage(ins, 0);
            height = 1;
        } else { 
            int result = root.insert(ins, height, unique, overwrite);
            if (result == op_overflow) { 
                allocateRootPage(ins, height);
                height += 1;
            } else if (result == op_duplicate || result == op_overwrite) { 
                return ins.oldNode;
            }
        }
        updateCounter += 1;
        nElems += 1;
        modify();
        return null;
    }

    public void remove(Key key, IPersistent obj) 
    {
        remove(new BtreeKey(checkKey(key), obj));
    }

    
    void remove(BtreeKey rem) 
    {
        if (!removeIfExists(rem)) { 
            throw new StorageError(StorageError.KEY_NOT_FOUND);
        }
    }

    boolean removeIfExists(BtreeKey rem) 
    {            
        if (root == null) {
            return false;
        }
        int result = root.remove(rem, height);
        if (result == op_not_found) { 
            return false;
        }
        nElems -= 1;
        if (result == op_underflow) { 
            if (root.nItems == 0) {                         
                BtreePage newRoot = null;
                if (height != 1) { 
                    newRoot = (BtreePage)root.items.get(0);
                }
                root.deallocate();
                root = newRoot;
                height -= 1;
            }
        }
        updateCounter += 1;
        modify();
        return true;
    }
        
    public IPersistent remove(Key key) {
        if (!unique) { 
            throw new StorageError(StorageError.KEY_NOT_UNIQUE);
        }
        BtreeKey rk = new BtreeKey(checkKey(key), null);
        remove(rk);
        return rk.oldNode;
    }
        
        
    public IPersistent get(String key) { 
        return get(new Key(key, true));
    }

    public IPersistent[] getPrefix(String prefix) { 
        return get(new Key(prefix, true), new Key(prefix + Character.MAX_VALUE, false));
    }

    public boolean put(String key, IPersistent obj) {
        return put(new Key(key, true), obj);
    }

    public IPersistent set(String key, IPersistent obj) {
        return set(new Key(key, true), obj);
    }

    public void  remove(String key, IPersistent obj) {
        remove(new Key(key, true), obj);
    }
    
    public IPersistent remove(String key) {
        return remove(new Key(key, true));
    }

    public int size() {
        return nElems;
    }
    
    public void clear() {
        if (root != null) { 
            root.purge(height);
            root = null;
            nElems = 0;
            height = 0;
            updateCounter += 1;
            modify();
        }
    }
        
    public IPersistent[] toPersistentArray() {
        IPersistent[] arr = new IPersistent[nElems];
        if (root != null) { 
            root.traverseForward(height, arr, 0);
        }
        return arr;
    }

    public IPersistent[] toPersistentArray(IPersistent[] arr) {
        if (arr.length < nElems) { 
            throw new IllegalArgumentException();
        }
        if (root != null) { 
            root.traverseForward(height, arr, 0);
        }
        if (arr.length > nElems) { 
            arr[nElems] = null;
        }
        return arr;
    }

    public void deallocate() { 
        if (root != null) { 
            root.purge(height);
        }
        super.deallocate();
    }

    static class BtreeEntry implements Map.Entry {
        public Object getKey() {
            return pg.getKeyValue(pos);
        }

        public Object getValue() {
            return pg.items.get(pos);
        }


        public Object setValue(Object value) { 
            throw new UnsupportedOperationException();
        }

        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry)) {
                return false;
            }