altbtree.java

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

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

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

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

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

    transient int updateCounter;

    public AltBtree() {}

    static class BtreeKey { 
        Key         key;
        IPersistent node;
        IPersistent oldNode;

        BtreeKey(Key key, IPersistent node) { 
            this.key = key;
            this.node = node;
        }
    }

    public static abstract class BtreePage extends Persistent { 
        int  nItems;
        Link items;

        public void writeObject(IOutputStream out) {
            out.writeInt(nItems);
            out.writeLink(items);
        }
        
        public void readObject(IInputStream in) {
            nItems = in.readInt();
            items = in.readLink();
        }


        static final int BTREE_PAGE_SIZE = Page.pageSize - ObjectHeader.sizeof - 4*3;

        abstract Object    getData();
        abstract Object    getKeyValue(int i);
        abstract Key       getKey(int i);
        abstract int       compare(Key key, int i);            
        abstract void      insert(BtreeKey key, int i);
        abstract BtreePage clonePage();
        
        void clearKeyValue(int i) {}

        boolean find(Key firstKey, Key lastKey, int height, ArrayList result)
        {
            int l = 0, n = nItems, r = n;
            height -= 1;
            if (firstKey != null) {
                while (l < r)  {
                    int i = (l+r) >> 1;
                    if (compare(firstKey, i) >= firstKey.inclusion) {
                        l = i+1;
                    } else {
                        r = i;
                    }
                }
                Assert.that(r == l);
            }
            if (lastKey != null) {
                if (height == 0) {
                    while (l < n) {
                        if (-compare(lastKey, l) >= lastKey.inclusion) {
                            return false;
                        }
                        result.add(items.get(l));
                        l += 1;
                    }
                    return true;
                } else {
                    do {
                        if (!((BtreePage)items.get(l)).find(firstKey, lastKey, height, result)) {
                            return false;
                        }
                        if (l == n) {
                            return true;
                        }
                    } while (compare(lastKey, l++) >= 0);
                    return false;
                }
            } 
            if (height == 0) { 
                while (l < n) { 
                    result.add(items.get(l));
                    l += 1;
                }
            } else { 
                do {
                    if (!((BtreePage)items.get(l)).find(firstKey, lastKey, height, result)) {
                        return false;
                    }
                } while (++l <= n);
            }
            return true;
        }

        static void memcpyData(BtreePage dst_pg, int dst_idx, BtreePage src_pg, int src_idx, int len) 
        { 
            System.arraycopy(src_pg.getData(), src_idx, dst_pg.getData(), dst_idx, len);
        }

        static void memcpyItems(BtreePage dst_pg, int dst_idx, BtreePage src_pg, int src_idx, int len) 
        { 
            System.arraycopy(src_pg.items.toRawArray(), src_idx, dst_pg.items.toRawArray(), dst_idx, len);            
        }

        static void memcpy(BtreePage dst_pg, int dst_idx, BtreePage src_pg, int src_idx, int len) 
        { 
            memcpyData(dst_pg, dst_idx, src_pg, src_idx, len);
            memcpyItems(dst_pg, dst_idx, src_pg, src_idx, len);
        }

        void memset(int i, int len) { 
            while (--len >= 0) { 
                items.set(i++, null);
            }
        }

        int insert(BtreeKey ins, int height, boolean unique, boolean overwrite)
        {
            int result;
            int l = 0, n = nItems, r = n;
            int ahead = unique ? 1 : 0;
            while (l < r)  {
                int i = (l+r) >> 1;
                if (compare(ins.key, i) >= ahead) { 
                    l = i+1; 
                } else { 
                    r = i;
                }
            }
            Assert.that(l == r);
            /* insert before e[r] */
            if (--height != 0) {
                result = ((BtreePage)items.get(r)).insert(ins, height, unique, overwrite);
                Assert.that(result != op_not_found);
                if (result != op_overflow) {
                    return result;
                }
                n += 1;
            } else if (r < n && compare(ins.key, r) == 0) { 
                if (overwrite) { 
                    ins.oldNode = items.get(r);
                    modify();
                    items.set(r, ins.node);
                    return op_overwrite;
                } else if (unique) { 
                    ins.oldNode = items.get(r);
                    return op_duplicate;
                }
            }
            int max = items.size();
            modify();
            if (n < max) {
                memcpy(this, r+1, this, r, n - r);
                insert(ins, r);
                nItems += 1;
                return op_done;
            } else { /* page is full then divide page */
                BtreePage b = clonePage();
                Assert.that(n == max);
                int m = max/2;
                if (r < m) {
                    memcpy(b, 0, this, 0, r);
                    memcpy(b, r+1, this, r, m-r-1);
                    memcpy(this, 0, this, m-1, max-m+1);
                    b.insert(ins, r);
                } else {
                    memcpy(b, 0, this, 0, m);
                    memcpy(this, 0, this, m, r-m);
                    memcpy(this, r-m+1, this, r, max-r);
                    insert(ins, r-m);
                }
                memset(max-m+1, m-1);
                ins.node = b;
                ins.key = b.getKey(m-1);
                if (height == 0) {
                    nItems = max - m + 1;
                    b.nItems = m;
                } else {
                    b.clearKeyValue(m-1);
                    nItems = max - m;
                    b.nItems = m - 1;
                }                            
                return op_overflow;
            }
        }

        int handlePageUnderflow(int r, BtreeKey rem, int height)
        {
            BtreePage a = (BtreePage)items.get(r);
            a.modify();
            modify();
            int an = a.nItems;
            if (r < nItems) { // exists greater page
                BtreePage b = (BtreePage)items.get(r+1);
                int bn = b.nItems; 
                Assert.that(bn >= an);
                if (height != 1) { 
                    memcpyData(a, an, this, r, 1);
                    an += 1;
                    bn += 1;
                }
                if (an + bn > items.size()) { 
                    // reallocation of nodes between pages a and b
                    int i = bn - ((an + bn) >> 1);
                    b.modify();
                    memcpy(a, an, b, 0, i);
                    memcpy(b, 0, b, i, bn-i);
                    memcpyData(this, r, a, an+i-1, 1);
                    if (height != 1) { 
                        a.clearKeyValue(an+i-1);
                    }
                    b.memset(bn-i, i);
                    b.nItems -= i;
                    a.nItems += i;
                    return op_done;
                } else { // merge page b to a  
                    memcpy(a, an, b, 0, bn);
                    b.deallocate();
                    memcpyData(this, r, this, r+1, nItems - r - 1);
                    memcpyItems(this, r+1, this, r+2, nItems - r - 1);
                    items.set(nItems, null);
                    a.nItems += bn;
                    nItems -= 1;
                    return nItems < (items.size() >> 1) ? op_underflow : op_done;
                }
            } else { // page b is before a
                BtreePage b = (BtreePage)items.get(r-1);
                int bn = b.nItems; 
                Assert.that(bn >= an);
                if (height != 1) { 
                    an += 1;
                    bn += 1;
                }
                if (an + bn > items.size()) { 
                    // reallocation of nodes between pages a and b
                    int i = bn - ((an + bn) >> 1);
                    b.modify();
                    memcpy(a, i, a, 0, an);
                    memcpy(a, 0, b, bn-i, i);
                    if (height != 1) { 
                        memcpyData(a, i-1, this, r-1, 1);
                    }
                    memcpyData(this, r-1, b, bn-i-1, 1);
                    if (height != 1) { 
                        b.clearKeyValue(bn-i-1);
                    }
                    b.memset(bn-i, i);
                    b.nItems -= i;
                    a.nItems += i;
                    return op_done;
                } else { // merge page b to a
                    memcpy(a, bn, a, 0, an);
                    memcpy(a, 0, b, 0, bn);
                    if (height != 1) { 
                        memcpyData(a, bn-1, this, r-1, 1);
                    }
                    b.deallocate();
                    items.set(r-1, a);
                    items.set(nItems, null);
                    a.nItems += bn;
                    nItems -= 1;
                    return nItems < (items.size() >> 1) ? op_underflow : op_done;
                }
            }
        }
   
        int remove(BtreeKey rem, int height)
        {
            int i, n = nItems, l = 0, r = n;
            
            while (l < r)  {
                i = (l+r) >> 1;
                if (compare(rem.key, i) > 0) { 
                    l = i+1; 
                } else { 
                    r = i;
                }
            }
            if (--height == 0) {
                IPersistent node = rem.node;
                while (r < n) {
                    if (compare(rem.key, r) == 0) {
                        if (node == null || items.containsElement(r, node)) {
                            rem.oldNode = items.get(r);
                            modify();
                            memcpy(this, r, this, r+1, n - r - 1);
                            nItems = --n;
                            memset(n, 1);
                            return n < (items.size() >> 1) ? op_underflow : op_done;
                        }
                    } else {
                        break;
                    }
                    r += 1;
                }
                return op_not_found;
            }
            do { 
                switch (((BtreePage)items.get(r)).remove(rem, height)) {
                case op_underflow: 
                    return handlePageUnderflow(r, rem, height);
                case op_done:
                    return op_done;
                } 
            } while (++r <= n);
            
            return op_not_found;
        }
        
        void purge(int height)
        {
            if (--height != 0) { 
                int n = nItems;
                do { 
                    ((BtreePage)items.get(n)).purge(height);
                } while (--n >= 0);
            }
            super.deallocate();
        }

        int traverseForward(int height, IPersistent[] result, int pos)
        {
            int i, n = nItems;
            if (--height != 0) {
                for (i = 0; i <= n; i++) { 
                    pos = ((BtreePage)items.get(i)).traverseForward(height, result, pos);
                }
            } else { 
                for (i = 0; i < n; i++) { 
                    result[pos++] = items.get(i);
                }
            }
            return pos;
        }

        BtreePage(Storage s, int n) 
        { 
            super(s);
            items = s.createLink(n);
            items.setSize(n);
        }

        public BtreePage() {}            
    }


    public static class BtreePageOfByte extends BtreePage { 
        byte[] data; 

        public void writeObject(IOutputStream out) {
            super.writeObject(out);
            out.writeArrayOfByte(data);
        }
        
        public void readObject(IInputStream in) {
            super.readObject(in);
            data = in.readArrayOfByte();
        }

        static final int MAX_ITEMS = BTREE_PAGE_SIZE / (4 + 1);