btree.java

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

package org.garret.perst.impl;
import  org.garret.perst.*;
import  java.util.*;

public class Btree extends PersistentResource implements Index { 
    int       root;
    int       height;
    int       type;
    int       nElems;
    boolean   unique;

    public void writeObject(IOutputStream out) {
        out.writeInt(root);
        out.writeInt(height);
        out.writeInt(type);
        out.writeInt(nElems);
        out.writeBoolean(unique);
    }

    public void readObject(IInputStream in) {
        root = in.readInt();
        height = in.readInt();
        type = in.readInt();
        nElems = in.readInt();
        unique = in.readBoolean();
    }

    transient int updateCounter;

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

    public Btree() {}

    static int checkType(int elemType) { 
        if (elemType > Types.Object && elemType != Types.ArrayOfByte) { 
            throw new StorageError(StorageError.UNSUPPORTED_INDEX_TYPE, Types.getSignature(elemType));
        }
        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(int elemType, boolean unique) {
        this.unique = unique;
        type = checkType(elemType);
    }

    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;

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

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

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

    final int insert(Key key, IPersistent 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, IPersistent 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 == Types.String || type == Types.ArrayOfByte) 
                        ? 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 IPersistent 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 db.lookupObject(rk.oldOid);
    }
        
        
    public IPersistent get(String key) { 
        return get(new Key(key.toCharArray(), true));
    }

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

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

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

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

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

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

    public void deallocate() { 
        if (root != 0) { 
            BtreePage.purge((StorageImpl)getStorage(), root, type, height);
        }