btree.java

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

package org.garret.perst.impl;
import  org.garret.perst.*;
import  java.util.*;
import  java.lang.reflect.Array;

class Btree<T extends IPersistent> extends PersistentCollection<T> implements Index<T> { 
    int       root;
    int       height;
    int       type;
    int       nElems;
    boolean   unique;

    transient int updateCounter;

    static final int sizeof = ObjectHeader.sizeof + 4*4 + 1;

    Btree() {}

    static int checkType(Class c) { 
        int elemType = ClassDescriptor.getTypeCode(c);
        if (elemType > ClassDescriptor.tpObject 
            && elemType != ClassDescriptor.tpEnum 
            && elemType != ClassDescriptor.tpArrayOfByte) 
        { 
            throw new StorageError(StorageError.UNSUPPORTED_INDEX_TYPE, c);
        }
        return elemType;
    }
       
    int compareByteArrays(byte[] key, byte[] item, int offs, int length) { 
        int n = key.length >= length ? length : key.length;
        for (int i = 0; i < n; i++) { 
            int diff = key[i] - item[i+offs];
            if (diff != 0) { 
                return diff;
            }
        }
        return key.length - length;
    }

    Btree(Class cls, boolean unique) {
        this.unique = unique;
        type = checkType(cls);
    }

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

    Btree(byte[] obj, int offs) {
        root = Bytes.unpack4(obj, offs);
        offs += 4;
        height = Bytes.unpack4(obj, offs);
        offs += 4;
        type = Bytes.unpack4(obj, offs);
        offs += 4;
        nElems = Bytes.unpack4(obj, offs);
        offs += 4;
        unique = obj[offs] != 0;
    }

    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.tpEnum:
            return Enum.class;
        case ClassDescriptor.tpString:
            return String.class;
        case ClassDescriptor.tpDate:
            return Date.class;
        case ClassDescriptor.tpObject:
            return IPersistent.class;
        case ClassDescriptor.tpArrayOfByte:
            return byte[].class;
        default:
            return Comparable.class;
        }
    }

    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 String) { 
                key = new Key(((String)key.oval).toCharArray(), key.inclusion != 0);
            }
        }
        return key;
    }            

    public T get(Key key) { 
        key = checkKey(key);
        if (root != 0) { 
            ArrayList list = new ArrayList();
            BtreePage.find((StorageImpl)getStorage(), root, key, key, this, 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 != 0) { 
            BtreePage.prefixSearch((StorageImpl)getStorage(), root, key.toCharArray(), 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 != 0) { 
            BtreePage.find((StorageImpl)getStorage(), root, checkKey(from), checkKey(till), this, height, list);
        }
        return list;
    }

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

    public T get(Object key) { 
        return get(getKeyFromObject(key));
    }

    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(getKeyFromObject(from), getKeyFromObject(till));
    }

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

    public T set(Key key, T obj) {
        int oid = insert(key, obj, true);
        return (T)((oid != 0) ? ((StorageImpl)getStorage()).lookupObject(oid, null) :  null);
    }

    final int insert(Key key, T obj, boolean overwrite) {
        StorageImpl db = (StorageImpl)getStorage();
        if (db == null) {             
            throw new StorageError(StorageError.DELETED_OBJECT);
        }
        key = checkKey(key);
        if (!obj.isPersistent()) { 
            db.makePersistent(obj);
        }
        BtreeKey ins = new BtreeKey(key, obj.getOid());
        if (root == 0) { 
            root = BtreePage.allocate(db, 0, type, ins);
            height = 1;
        } else { 
            int result = BtreePage.insert(db, root, this, ins, height, unique, overwrite);
            if (result == op_overflow) { 
                root = BtreePage.allocate(db, root, type, ins);
                height += 1;
            } else if (result == op_duplicate) { 
                return -1;
            } else if (result == op_overwrite) { 
                return ins.oldOid;
            }
        }
        updateCounter += 1;
        nElems += 1;
        modify();
        return 0;
    }

    public void remove(Key key, T obj) {
        remove(new BtreeKey(checkKey(key), obj.getOid()));
    }

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

    boolean removeIfExists(BtreeKey rem) 
    {            
        StorageImpl db = (StorageImpl)getStorage();
        if (db == null) {             
            throw new StorageError(StorageError.DELETED_OBJECT);
        }
        if (root == 0) {
            return false;
        }
        int result = BtreePage.remove(db, root, this, rem, height);
        if (result == op_not_found) { 
            return false;
        }
        nElems -= 1;
        if (result == op_underflow) { 
            Page pg = db.getPage(root);
            if (BtreePage.getnItems(pg) == 0) {                         
                int newRoot = 0;
                if (height != 1) { 
                    newRoot = (type == ClassDescriptor.tpString || type == ClassDescriptor.tpArrayOfByte) 
                        ? BtreePage.getKeyStrOid(pg, 0)
                        : BtreePage.getReference(pg, BtreePage.maxItems-1);
                }
                db.freePage(root);
                root = newRoot;
                height -= 1;
            }
            db.pool.unfix(pg);
        } else if (result == op_overflow) { 
            root = BtreePage.allocate(db, root, type, rem);
            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), 0);
        StorageImpl db = (StorageImpl)getStorage();
        remove(rk);
        return (T)db.lookupObject(rk.oldOid, null);
    }
        
    static Key getKeyFromObject(Object o) {
        if (o == null) { 
            return null;
        } else if (o instanceof Byte) { 
            return new Key(((Byte)o).byteValue());
        } else if (o instanceof Short) {
            return new Key(((Short)o).shortValue());
        } else if (o instanceof Integer) {
            return new Key(((Integer)o).intValue());
        } else if (o instanceof Long) {
            return new Key(((Long)o).longValue());
        } else if (o instanceof Float) {
            return new Key(((Float)o).floatValue());
        } else if (o instanceof Double) {
            return new Key(((Double)o).doubleValue());
        } else if (o instanceof Boolean) {
            return new Key(((Boolean)o).booleanValue());
        } else if (o instanceof Character) {
            return new Key(((Character)o).charValue());
        } else if (o instanceof String) {
            return new Key((String)o);
        } else if (o instanceof java.util.Date) {
            return new Key((java.util.Date)o);
        } else if (o instanceof byte[]) {
            return new Key((byte[])o);
        } else if (o instanceof Object[]) {
            return new Key((Object[])o);
        } else if (o instanceof Enum) {
            return new Key((Enum)o);
        } else if (o instanceof IPersistent) {
            return new Key((IPersistent)o);
        } else if (o instanceof Comparable) {
            return new Key((Comparable)o);
        }
        throw new StorageError(StorageError.UNSUPPORTED_TYPE);
    }
        

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

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

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