altbtree.java

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

        }

        private BtreePage pg;
        private int pos;
    }


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

    public IterableIterator<Map.Entry<Object,T>> entryIterator() { 
        return entryIterator(null, null, ASCENT_ORDER);
    }

    class BtreeSelectionIterator<E> extends IterableIterator<E> implements PersistentIterator { 
        BtreeSelectionIterator(Key from, Key till, int order) { 
            this.from = from;
            this.till = till;
            this.order = order;
            reset();
        }

        void reset() { 
            int i, l, r;
            
            sp = 0;
            counter = updateCounter;
            if (height == 0) { 
                return;
            }
            BtreePage page = root;
            int h = height;
            
            pageStack = new BtreePage[h];
            posStack =  new int[h];
            
            if (order == ASCENT_ORDER) { 
                if (from == null) { 
                    while (--h > 0) { 
                        posStack[sp] = 0;
                        pageStack[sp] = page;
                        page = (BtreePage)page.items.get(0);
                        sp += 1;
                    }
                    posStack[sp] = 0;
                    pageStack[sp] = page;
                    end = page.nItems;
                    sp += 1;                     
                } else { 
                    while (--h > 0) { 
                        pageStack[sp] = page;
                        l = 0;
                        r = page.nItems;
                        while (l < r)  {
                            i = (l+r) >> 1;
                            if (page.compare(from, i) >= from.inclusion) {
                                l = i + 1; 
                            } else { 
                                r = i;
                            }
                        }
                        Assert.that(r == l); 
                        posStack[sp] = r;
                        page = (BtreePage)page.items.get(r);
                        sp += 1;
                    }
                    pageStack[sp] = page;
                    l = 0;
                    r = end = page.nItems;
                    while (l < r)  {
                        i = (l+r) >> 1;
                        if (page.compare(from, i) >= from.inclusion) {
                            l = i + 1; 
                        } else { 
                            r = i;
                        }
                    }
                    Assert.that(r == l); 
                    if (r == end) {
                        sp += 1;
                        gotoNextItem(page, r-1);
                    } else { 
                        posStack[sp++] = r;
                    }
                }
                if (sp != 0 && till != null) { 
                    page = pageStack[sp-1];
                    if (-page.compare(till, posStack[sp-1]) >= till.inclusion) { 
                        sp = 0;
                    }
                }
            } else { // descent order
                if (till == null) { 
                    while (--h > 0) { 
                        pageStack[sp] = page;
                        posStack[sp] = page.nItems;
                        page = (BtreePage)page.items.get(page.nItems);
                        sp += 1;
                    }
                    pageStack[sp] = page;
                    posStack[sp++] = page.nItems-1;
                } else {
                    while (--h > 0) { 
                        pageStack[sp] = page;
                        l = 0;
                        r = page.nItems;
                        while (l < r)  {
                            i = (l+r) >> 1;
                            if (page.compare(till, i) >= 1-till.inclusion) {
                                l = i + 1; 
                            } else { 
                                r = i;
                            }
                        }
                        Assert.that(r == l); 
                        posStack[sp] = r;
                        page = (BtreePage)page.items.get(r);
                        sp += 1;
                    }
                    pageStack[sp] = page;
                    l = 0;
                    r = page.nItems;
                    while (l < r)  {
                        i = (l+r) >> 1;
                        if (page.compare(till, i) >= 1-till.inclusion) {
                            l = i + 1; 
                        } else { 
                            r = i;
                        }
                    }
                    Assert.that(r == l);  
                    if (r == 0) { 
                        sp += 1;
                        gotoNextItem(page, r);
                    } else { 
                        posStack[sp++] = r-1;
                    }
                }
                if (sp != 0 && from != null) { 
                    page = pageStack[sp-1];
                    if (page.compare(from, posStack[sp-1]) >= from.inclusion) { 
                        sp = 0;
                    }
                }
            }
        }
                
        public boolean hasNext() {
            if (counter != updateCounter) { 
                if (((StorageImpl)getStorage()).concurrentIterator) { 
                    refresh();
                } else { 
                    throw new ConcurrentModificationException();
                }
            }
            return sp != 0;
        }

        public E next() {
            if (!hasNext()) { 
                throw new NoSuchElementException();
            }
            int pos = posStack[sp-1];   
            BtreePage pg = pageStack[sp-1];
            currPos = pos;
            currPage = pg;
            E curr = (E)getCurrent(pg, pos);
            if (((StorageImpl)getStorage()).concurrentIterator) { 
                currKey = new BtreeKey(pg.getKey(pos), pg.items.getRaw(pos));
            }
            gotoNextItem(pg, pos);
            return curr;
        }

        public int nextOid() {
            if (!hasNext()) { 
                throw new NoSuchElementException();
            }
            int pos = posStack[sp-1];   
            BtreePage pg = pageStack[sp-1];
            currPos = pos;
            currPage = pg;
            int oid =  pg.items.getRaw(pos).getOid();
            if (((StorageImpl)getStorage()).concurrentIterator) { 
                currKey = new BtreeKey(pg.getKey(pos), pg.items.getRaw(pos));
            }
            gotoNextItem(pg, pos);
            return oid;
        }

        protected Object getCurrent(BtreePage pg, int pos) { 
            return pg.items.get(pos);
        }

        protected final void gotoNextItem(BtreePage pg, int pos)
        {
            if (order == ASCENT_ORDER) {                     
                if (++pos == end) { 
                    while (--sp != 0) { 
                        pos = posStack[sp-1];
                        pg = pageStack[sp-1];
                        if (++pos <= pg.nItems) {
                            posStack[sp-1] = pos;
                            do { 
                                pg = (BtreePage)pg.items.get(pos);
                                end = pg.nItems;
                                pageStack[sp] = pg;
                                posStack[sp] = pos = 0;
                            } while (++sp < pageStack.length);
                            break;
                        }
                    }
                } else { 
                    posStack[sp-1] = pos;
                }
                if (sp != 0 && till != null && -pg.compare(till, pos) >= till.inclusion) { 
                    sp = 0;
                }
            } else { // descent order
                if (--pos < 0) { 
                    while (--sp != 0) { 
                        pos = posStack[sp-1];
                        pg = pageStack[sp-1];
                        if (--pos >= 0) {
                            posStack[sp-1] = pos;
                            do { 
                                pg = (BtreePage)pg.items.get(pos);
                                pageStack[sp] = pg;
                                posStack[sp] = pos = pg.nItems;
                            } while (++sp < pageStack.length);
                            posStack[sp-1] = --pos;
                            break;
                        }
                    }
                } else { 
                    posStack[sp-1] = pos;
                }
                if (sp != 0 && from != null && pg.compare(from, pos) >= from.inclusion) { 
                    sp = 0;
                }                    
            }
            if (((StorageImpl)getStorage()).concurrentIterator && sp != 0) { 
                nextKey = pg.getKey(pos);
                nextObj = pg.items.getRaw(pos);
            }
        }


        private void refresh() { 
            if (sp != 0) { 
                if (nextKey == null) { 
                    reset();
                } else { 
                    if (order == ASCENT_ORDER) { 
                        from = nextKey;
                    } else { 
                        till = nextKey;
                    }
                    IPersistent next = nextObj;
                    reset();
                    while (true) { 
                        int pos = posStack[sp-1];   
                        BtreePage pg = pageStack[sp-1];
                        if (!pg.items.getRaw(pos).equals(next)) { 
                            gotoNextItem(pg, pos);
                        } else { 
                            break;
                        }
                    }
                }
            }
            counter = updateCounter;
        }

        public void remove() { 
            if (currPage == null) { 
                throw new NoSuchElementException();
            }
            StorageImpl db = (StorageImpl)getStorage();
            if (!db.concurrentIterator) { 
                if (counter != updateCounter) { 
                    throw new ConcurrentModificationException();
                }
                currKey = new BtreeKey(currPage.getKey(currPos), currPage.items.getRaw(currPos));
                if (sp != 0) { 
                    int pos = posStack[sp-1];   
                    BtreePage pg = pageStack[sp-1];
                    nextKey = pg.getKey(pos);
                    nextObj = pg.items.getRaw(pos);
                }
            }
            AltBtree.this.removeIfExists(currKey);
            refresh();
            currPage = null;
        }

        BtreePage[] pageStack;
        int[]       posStack;
        BtreePage   currPage;
        int         currPos;
        int         sp;
        int         end;
        Key         from;
        Key         till;
        int         order;
        int         counter;
        BtreeKey    currKey;
        Key         nextKey;
        IPersistent nextObj;
    }

    class BtreeSelectionEntryIterator extends BtreeSelectionIterator<Map.Entry<Object,T>> { 
        BtreeSelectionEntryIterator(Key from, Key till, int order) {
            super(from, till, order);
        }
            
        protected Object getCurrent(BtreePage pg, int pos) { 
            return new BtreeEntry(pg, pos);
        }
    }

    class BtreeEntryStartFromIterator extends BtreeSelectionEntryIterator
    { 
        BtreeEntryStartFromIterator(int start, int order) {
            super(null, null, order);
            this.start = start;
            reset();
        }
        
        void reset() { 
            super.reset();
            int skip = (order == ASCENT_ORDER) ? start : nElems - start - 1;
            while (--skip >= 0 && hasNext()) {
                next();
            }
        }
        
        int start;
    }

    public IterableIterator<T> iterator(Key from, Key till, int order) { 
        return new BtreeSelectionIterator<T>(checkKey(from), checkKey(till), order);
    }

    public IterableIterator<T> iterator(Object from, Object till, int order) { 
        return new BtreeSelectionIterator<T>(checkKey(Btree.getKeyFromObject(from)), 
                                             checkKey(Btree.getKeyFromObject(till)), order);
    }

    public IterableIterator<T> prefixIterator(String prefix) {
        return iterator(new Key(prefix), new Key(prefix + Character.MAX_VALUE, false), ASCENT_ORDER);
    }


    public IterableIterator<Map.Entry<Object,T>> entryIterator(Key from, Key till, int order) { 
        return new BtreeSelectionEntryIterator(checkKey(from), checkKey(till), order);
    }

    public IterableIterator<Map.Entry<Object,T>> entryIterator(Object from, Object till, int order) { 
        return new BtreeSelectionEntryIterator(checkKey(Btree.getKeyFromObject(from)), 
                                               checkKey(Btree.getKeyFromObject(till)), order);
    }

    public T getAt(int i) {
        IterableIterator<Map.Entry<Object,T>> iterator;
        if (i < 0 || i >= nElems) {
            throw new IndexOutOfBoundsException("Position " + i + ", index size "  + nElems);
        }            
        if (i <= (nElems/2)) {
            iterator = entryIterator(null, null, ASCENT_ORDER);
            while (--i >= 0) { 
                iterator.next();
            }
        } else {
            iterator = entryIterator(null, null, DESCENT_ORDER);
            i -= nElems;
            while (++i < 0) { 
                iterator.next();
            }
        }
        return iterator.next().getValue();   
    }

    public IterableIterator<Map.Entry<Object,T>> entryIterator(int start, int order) {
        return new BtreeEntryStartFromIterator(start, order);
    }
}