bitindeximpl.java

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

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

class BitIndexImpl<T extends IPersistent> extends Btree<T> implements BitIndex<T> 
{ 
    BitIndexImpl() {
        super(ClassDescriptor.tpInt, true);
    }

    static class Key { 
        int key;
        int oid;

        Key(int key, int oid) { 
            this.key = key;
            this.oid = oid;
        }
    }
        
    public int get(T obj) 
    {
        StorageImpl db = (StorageImpl)getStorage();
        if (root == 0) { 
            throw new StorageError(StorageError.KEY_NOT_FOUND);
        } 
        return BitIndexPage.find(db, root, obj.getOid(), height);
    }
 
    public void put(T obj, int mask) 
    {
        StorageImpl db = (StorageImpl)getStorage();
        if (db == null) {             
            throw new StorageError(StorageError.DELETED_OBJECT);
        }
        if (!obj.isPersistent()) { 
            db.makePersistent(obj);
        }
        Key ins = new Key(mask, obj.getOid());
        if (root == 0) { 
            root = BitIndexPage.allocate(db, 0, ins);
            height = 1;
        } else { 
            int result = BitIndexPage.insert(db, root, ins, height);
            if (result == op_overflow) { 
                root = BitIndexPage.allocate(db, root, ins);
                height += 1;
            }
        }
        updateCounter += 1;
        nElems += 1;
        modify();
    }

    public void remove(T obj) 
    {
        StorageImpl db = (StorageImpl)getStorage();
        if (db == null) {             
            throw new StorageError(StorageError.DELETED_OBJECT);
        }
        if (root == 0) {
            throw new StorageError(StorageError.KEY_NOT_FOUND);
        }
        int result = BitIndexPage.remove(db, root, obj.getOid(), height);
        if (result == op_not_found) { 
            throw new StorageError(StorageError.KEY_NOT_FOUND);
        }
        nElems -= 1;
        if (result == op_underflow) { 
            Page pg = db.getPage(root);
            if (BitIndexPage.getnItems(pg) == 0) {                         
                int newRoot = 0;
                if (height != 1) { 
                    newRoot = BitIndexPage.getItem(pg, BitIndexPage.maxItems-1);
                }
                db.freePage(root);
                root = newRoot;
                height -= 1;
            }
            db.pool.unfix(pg);
        }
        updateCounter += 1;
        modify();
    }
        
    class BitIndexIterator<E> extends IterableIterator<E> implements PersistentIterator 
    { 
        BitIndexIterator(int set, int clear) 
        { 
            sp = 0;
            counter = updateCounter;
            if (height == 0) { 
                return;
            }
            int pageId = root;
            StorageImpl db = (StorageImpl)getStorage();
            if (db == null) {             
                throw new StorageError(StorageError.DELETED_OBJECT);
            }
            int h = height;
            this.set = set;
            this.clear = clear;
            
            pageStack = new int[h];
            posStack = new int[h];
            
            while (true) { 
                pageStack[sp] = pageId;
                Page pg = db.getPage(pageId);
                sp += 1;
                if (--h == 0) { 
                    gotoNextItem(pg, 0);
                    break;
                }
                pageId = BitIndexPage.getItem(pg, BitIndexPage.maxItems-1);
                db.pool.unfix(pg);
            }
        }

        public boolean hasNext() 
        {
            if (counter != updateCounter) { 
                throw new ConcurrentModificationException();
            }
            return sp != 0;
        }

        public E next() 
        {
            return (E)((StorageImpl)getStorage()).lookupObject(nextOid(), null);
        }

        public int nextOid() 
        {
            if (!hasNext()) { 
                throw new NoSuchElementException();
            }
            StorageImpl db = (StorageImpl)getStorage();
            int pos = posStack[sp-1];   
            Page pg = db.getPage(pageStack[sp-1]);
            int oid = BitIndexPage.getItem(pg, BitIndexPage.maxItems-1-pos);
            gotoNextItem(pg, pos+1);
            return oid;
        }

        private final void gotoNextItem(Page pg, int pos)
        {
            StorageImpl db = (StorageImpl)getStorage();
                
            do { 
                int end = BitIndexPage.getnItems(pg); 
                while (pos < end) { 
                    int mask = BitIndexPage.getItem(pg, pos);
                    if ((set & mask) == set && (clear & mask) == 0) { 
                        posStack[sp-1] = pos;
                        db.pool.unfix(pg);
                        return;
                    }
                    pos += 1;
                }
                while (--sp != 0) { 
                    db.pool.unfix(pg);
                    pos = posStack[sp-1];
                    pg = db.getPage(pageStack[sp-1]);
                    if (++pos <= BitIndexPage.getnItems(pg)) {
                        posStack[sp-1] = pos;
                        do { 
                            int pageId = BitIndexPage.getItem(pg, BitIndexPage.maxItems-1-pos);
                            db.pool.unfix(pg);
                            pg = db.getPage(pageId);
                            pageStack[sp] = pageId;
                            posStack[sp] = pos = 0;
                        } while (++sp < pageStack.length);
                        break;
                    }
                }
            } while (sp != 0);

            db.pool.unfix(pg);
        }

        public void remove() 
        { 
            throw new UnsupportedOperationException();
        }

        int[]       pageStack;
        int[]       posStack;
        int         sp;
        int         set;
        int         clear;
        int         counter;
    }

    public Iterator<T> iterator() 
    {
        return iterator(0, 0);
    }

    public IterableIterator<T> iterator(int set, int clear) 
    { 
        return new BitIndexIterator<T>(set, clear);
    }

    static class BitIndexPage extends BtreePage { 
        static final int max = keySpace / 8;    

        static int getItem(Page pg, int index) { 
            return Bytes.unpack4(pg.data, firstKeyOffs + index*4);
        }
    
        static void setItem(Page pg, int index, int mask) { 
            Bytes.pack4(pg.data, firstKeyOffs + index*4, mask);
        }

        static int allocate(StorageImpl db, int root, Key ins) 
        {
            int pageId = db.allocatePage();
            Page pg = db.putPage(pageId);
            setnItems(pg, 1);
            setItem(pg, 0, ins.key);
            setItem(pg, maxItems-1, ins.oid);
            setItem(pg, maxItems-2, root);
            db.pool.unfix(pg);
            return pageId;
        }
        
        static void memcpy(Page dst_pg, int dst_idx, Page src_pg, int src_idx, int len) 
        { 
            System.arraycopy(src_pg.data, firstKeyOffs + src_idx*4, 
                             dst_pg.data, firstKeyOffs + dst_idx*4, 
                             len*4);
        }
        
        static int find(StorageImpl db, int pageId, int oid, int height)
        {
            Page pg = db.getPage(pageId);
            try { 
                int i, n = getnItems(pg), l = 0, r = n;
                if (--height == 0) {
                    while (l < r)  {
                        i = (l+r) >> 1;
                        if (oid > getItem(pg, maxItems-1-i)) { 
                            l = i+1; 
                        } else { 
                            r = i;
                        }
                    }
                    if (r < n && getItem(pg, maxItems-r-1) == oid) {
                        return getItem(pg, r);
                    }
                    throw new StorageError(StorageError.KEY_NOT_FOUND);                    
                } else { 
                    while (l < r)  {
                        i = (l+r) >> 1;