rndbtree.java

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

        Key getKey(int i) { 
            return new Key(((Comparable[])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.setObject(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
            && elemType != ClassDescriptor.tpEnum) 
        { 
            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;
        case ClassDescriptor.tpEnum:
            return Enum.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 T 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 (T)list.get(0);
            }
        }
        return null;
    }

    public ArrayList<T> prefixSearchList(String key) { 
        if (ClassDescriptor.tpString != type) { 
            throw new StorageError(StorageError.INCOMPATIBLE_KEY_TYPE);
        }
        ArrayList<T> list = new ArrayList<T>();
        if (root != null) { 
            ((BtreePageOfString)root).prefixSearch(key, height, list);
        }
        return list;
    }

    public IPersistent[] prefixSearch(String key) {
        ArrayList<T> list = prefixSearchList(key);
        return (IPersistent[])list.toArray(new IPersistent[list.size()]);
    }

    public ArrayList<T> getList(Key from, Key till) {
        ArrayList<T> list = new ArrayList<T>();
        if (root != null) { 
            root.find(checkKey(from), checkKey(till), height, list);
        }
        return list;
    }

    public ArrayList<T> getList(Object from, Object till) {
        return getList(Btree.getKeyFromObject(from), Btree.getKeyFromObject(till));
    }

    public IPersistent[] get(Key from, Key till) {
        ArrayList<T> list = getList(from, till);
        return (IPersistent[])list.toArray(new IPersistent[list.size()]);
    }

    public IPersistent[] get(Object from, Object till) {
        return get(Btree.getKeyFromObject(from), Btree.getKeyFromObject(till));
    }

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

    public T set(Key key, T 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:
        case ClassDescriptor.tpEnum:
            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.setObject(1, root);
        if (height != 0) { 
            newRoot.countChildren(1, height);
        }
        newRoot.nItems = 1;
        root = newRoot;
    }

    final T insert(Key key, T 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 (T)ins.oldNode;
            }
        }
        updateCounter += 1;
        nElems += 1;
        modify();
        return null;
    }

    public void remove(Key key, T 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 T remove(Key key) {
        if (!unique) { 
            throw new StorageError(StorageError.KEY_NOT_UNIQUE);
        }
        BtreeKey rk = new BtreeKey(checkKey(key), null);
        remove(rk);
        return (T)rk.oldNode;
    }
        
        
    public T get(Object key) { 
        return get(Btree.getKeyFromObject(key));
    }

    public ArrayList<T> getPrefixList(String prefix) { 
        return getList(new Key(prefix, true), new Key(prefix + Character.MAX_VALUE, false));
    }

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

    public boolean put(Object key, T obj) {
        return put(Btree.getKeyFromObject(key), obj);
    }

    public T set(Object key, T obj) {
        return set(Btree.getKeyFromObject(key), obj);
    }

    public void remove(Object key, T obj) {
        remove(Btree.getKeyFromObject(key), obj);
    }
    
    public T remove(String key) {
        return remove(new Key(key));
    }

    public T removeKey(Object key) {
        return removeKey(Btree.getKeyFromObject(key));
    }

    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 Object[] toArray() {
        return toPersistentArray();
    }

    public <E> E[] toArray(E[] arr) {
        if (arr.length < nElems) { 
            arr = (E[])Array.newInstance(arr.getClass().getComponentType(), nElems);
        }
        if (root != null) { 
            root.traverseForward(height, (IPersistent[])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<T> implements Map.Entry<Object,T> {
        public Object getKey() {
            return pg.getKeyValue(pos);
        }

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

        public T setValue(T 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 ? e.getValue() == null : getValue().equals(e.getValue())); 
	}

	public int hashCode() {
	    return ((getKey() == null) ? 0 : getKey().hashCode()) ^
                ((getValue() == null) ? 0 : getValue().hashCode());
	}

	public String toString() {
	    return getKey() + "=" + getValue();
	}