rndbtree.java

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

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

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

    transient int updateCounter;

    RndBtree() {}

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

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

    static abstract class BtreePage extends Persistent { 
        int   nItems;
        Link  items;
        int[] nChildren;

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

        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) {}

        Object getAt(int i, int height) { 
            if (--height == 0) {
                return items.get(i);
            } else { 
                int j;
                for (j = 0; i >= nChildren[j]; j++) {
                    i -= nChildren[j];
                }
                return ((BtreePage)items.get(j)).getAt(i, height);
            }
        }
        
        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);  
            System.arraycopy(src_pg.nChildren, src_idx, dst_pg.nChildren, 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);
            }
        }

        private void countChildren(int i, int height) {
            nChildren[i] = ((BtreePage)items.get(i)).totalCount(height);
        }

        private int totalCount(int height) { 
            if (--height == 0) { 
                return nItems;
            } else { 
                int sum = 0;
                for (int i = nItems; i >= 0; i--) { 
                    sum += nChildren[i];
                }
                return sum;
            }
        }

        private void insert(BtreeKey key, int i, int height) {
            insert(key, i);
            if (height != 0) {
                countChildren(i, height);
            }
        }

        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) {
                    if (result == op_done) {
                        modify();
                        nChildren[r] += 1;
                    }
                    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 (height != 0) {
                countChildren(r, height);
            }
            if (n < max) {
                memcpy(this, r+1, this, r, n - r);
                insert(ins, r, height);
                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, height);
                } 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, height);
                }
                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;
                    countChildren(r, height);
                    countChildren(r+1, height);
                    return op_done;
                } else { // merge page b to a  
                    memcpy(a, an, b, 0, bn);
                    b.deallocate();
                    int nMergedChildren = nChildren[r+1];
                    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;
                    nChildren[r] += nMergedChildren-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;
                    countChildren(r-1, height);
                    countChildren(r, height);
                    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);
                    nChildren[r-1] += nChildren[r] - 1;
                    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:
                    modify();
                    nChildren[r] -= 1;
                    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);
            nChildren = new int[n];
        }

        BtreePage() {}            
    }