rndbtree.java

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

        }    


        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;
        }

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

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

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

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

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

        BtreePageOfRaw(Storage s) {
            super(s, MAX_ITEMS);
            data = new Object[MAX_ITEMS];
        }

        BtreePageOfRaw() {}
    }



    static int checkType(Class c) { 
        int elemType = ClassDescriptor.getTypeCode(c);
        if (elemType > ClassDescriptor.tpObject && elemType != ClassDescriptor.tpRaw) { 
            throw new StorageError(StorageError.UNSUPPORTED_INDEX_TYPE, c);
        }
        return elemType;
    }
       
    RndBtree(Class cls, boolean unique) {
        this.unique = unique;
        type = checkType(cls);
    }

    RndBtree(int type, boolean unique) { 
        this.type = type;
        this.unique = unique;
    }

    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;

    public Class[] getKeyTypes() {
        return new Class[]{getKeyType()};
    }

    public Class getKeyType() {
        return mapKeyType(type);
    }

    static Class mapKeyType(int type) {
        switch (type) { 
        case ClassDescriptor.tpBoolean:
            return boolean.class;
        case ClassDescriptor.tpByte:
            return byte.class;
        case ClassDescriptor.tpChar:
            return char.class;
        case ClassDescriptor.tpShort:
            return short.class;
        case ClassDescriptor.tpInt:
            return int.class;
        case ClassDescriptor.tpLong:
            return long.class;
        case ClassDescriptor.tpFloat:
            return float.class;
        case ClassDescriptor.tpDouble:
            return double.class;
        case ClassDescriptor.tpString:
            return String.class;
        case ClassDescriptor.tpDate:
            return Date.class;
        case ClassDescriptor.tpObject:
            return IPersistent.class;
        case ClassDescriptor.tpRaw:
            return Comparable.class;
        default:
            return null;
        }
    }

    Key checkKey(Key key) { 
        if (key != null) { 
            if (key.type != type) { 
                throw new StorageError(StorageError.INCOMPATIBLE_KEY_TYPE);
            }
            if (type == ClassDescriptor.tpObject && 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 (ClassDescriptor.tpString != 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 ClassDescriptor.tpByte:
            newRoot = new BtreePageOfByte(s);
            break;
        case ClassDescriptor.tpShort:
            newRoot = new BtreePageOfShort(s);
            break;
        case ClassDescriptor.tpChar:
            newRoot = new BtreePageOfChar(s);
            break;
        case ClassDescriptor.tpBoolean:
            newRoot = new BtreePageOfBoolean(s);
            break;
        case ClassDescriptor.tpInt:
            newRoot = new BtreePageOfInt(s);
            break;
        case ClassDescriptor.tpLong:
            newRoot = new BtreePageOfLong(s);
            break;
        case ClassDescriptor.tpFloat:
            newRoot = new BtreePageOfFloat(s);
            break;
        case ClassDescriptor.tpDouble:
            newRoot = new BtreePageOfDouble(s);
            break;
        case ClassDescriptor.tpObject:
            newRoot = new BtreePageOfObject(s);
            break;
        case ClassDescriptor.tpString:
            newRoot = new BtreePageOfString(s);
            break;
        case ClassDescriptor.tpRaw:
            newRoot = new BtreePageOfRaw(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) { 
            arr = (IPersistent[])Array.newInstance(arr.getClass().getComponentType(), nElems);
        }
        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;
            }
            Map.Entry e = (Map.Entry)o;
            return (getKey()==null 
                    ? e.getKey()==null : getKey().equals(e.getKey())) 
                && (getValue()==null 
                    ? getValue()==null : getValue().equals(e.getValue()));
        }

        BtreeEntry(BtreePage pg, int pos) {
            this.pg = pg;
            this.pos = pos;
        }