btree.java

jxta平台的开发包

            // Promote the pivot to the parent branch
            if (parent == null) {
                // This can only happen if this is the root
                BTreeNode rNode = createBTreeNode(ph.getStatus(), this);
                rNode.set(rightVals, rightPtrs);

                BTreeNode lNode = createBTreeNode(ph.getStatus(), this);
                lNode.set(leftVals, leftPtrs);

                ph.setStatus(BRANCH);
                set(new Value[] {
                        separator
                    },
                    new long[] {
                        lNode.page.getPageNum().longValue(),
                        rNode.page.getPageNum().longValue()
                    });

                write();
                rNode.write();
                lNode.write();
            } else {
                set(leftVals, leftPtrs);

                BTreeNode rNode = createBTreeNode(ph.getStatus(), parent);
                rNode.set(rightVals, rightPtrs);

                write();
                rNode.write();
                parent.promoteValue(separator,
                                    rNode.page.getPageNum().longValue());
            }
        }

        /////////////////////////////////////////////////////////////////

        public synchronized long findValue(Value value) throws IOException, BTreeException {
            if (value == null) {
                throw new BTreeNotFoundException("Can't search on null Value");
            }

            int idx = Arrays.binarySearch(values, value);

            switch (ph.getStatus()) {
                case BRANCH:
                    idx = idx < 0 ? -(idx + 1) : idx + 1;
                    return getChildNode(idx).findValue(value);

                case LEAF:
                    if (idx < 0) {
                        throw new BTreeNotFoundException("Value '" + value + "' doesn't exist");
                    } else {
                        return ptrs[idx];
                    }

                default :
                    throw new BTreeCorruptException("Invalid page type '" + ph.getStatus() +
                                                    "' in findValue");
            }
        }

        // query is a BEAST of a method
        public synchronized void query(IndexQuery query, BTreeCallback callback) throws IOException, BTreeException {
            if (query != null && query.getOperator() != IndexQuery.ANY) {
                Value[] qvals = query.getValues();
                int leftIdx = Arrays.binarySearch(values, qvals[0]);
                int rightIdx = qvals.length > 1 ? Arrays.binarySearch(values, qvals[qvals.length - 1]) : leftIdx;

                switch (ph.getStatus()) {
                case BRANCH:
                    leftIdx = leftIdx < 0 ? -(leftIdx + 1) : leftIdx + 1;
                    rightIdx = rightIdx < 0 ? -(rightIdx + 1) : rightIdx + 1;

                    switch (query.getOperator()) {
                    case IndexQuery.BWX:
                    case IndexQuery.BW:
                    case IndexQuery.IN:
                    case IndexQuery.SW:
                                // TODO: Can leftIdx be less than 0 here?
                                if (leftIdx < 0) {
                                    leftIdx = 0;
                                }
                                if (rightIdx > ptrs.length - 1) {
                                    rightIdx = ptrs.length - 1;
                                }
                                for (int i = leftIdx; i <= rightIdx; i++) {
                                    getChildNode(i).query(query, callback);
                                }
                        break;

                    case IndexQuery.NBWX:
                    case IndexQuery.NBW:
                    case IndexQuery.NIN:
                    case IndexQuery.NSW:
                                if (leftIdx > ptrs.length - 1) {
                                    leftIdx = ptrs.length - 1;
                                }
                                for (int i = 0; i <= leftIdx; i++) {
                                    getChildNode(i).query(query, callback);
                                }
                                if (rightIdx < 0) {
                                    rightIdx = 0;
                                }
                                for (int i = rightIdx; i < ptrs.length; i++) {
                                    getChildNode(i).query(query, callback);
                                }
                                break;

                    case IndexQuery.EQ:
                        getChildNode(leftIdx).query(query, callback);
                        break;

                    case IndexQuery.LT:
                    case IndexQuery.LEQ:
                                if (leftIdx > ptrs.length - 1) {
                                    leftIdx = ptrs.length - 1;
                                }
                                for (int i = 0; i <= leftIdx; i++) {
                                    getChildNode(i).query(query, callback);
                                }
                                break;

                    case IndexQuery.GT:
                    case IndexQuery.GEQ:
                                if (rightIdx < 0) {
                                    rightIdx = 0;
                                }
                                for (int i = rightIdx; i < ptrs.length; i++) {
                                    getChildNode(i).query(query, callback);
                                }
                        break;

                    case IndexQuery.NEQ:
                    default :
                        for (int i = 0; i < ptrs.length; i++) {
                            getChildNode(i).query(query, callback);
                        }
                        break;
                    }
                    break;

                case LEAF:
                    switch (query.getOperator()) {
                    case IndexQuery.EQ:
                        if (leftIdx >= 0) {
                            callback.indexInfo(values[leftIdx], ptrs[leftIdx]);
                        }
                        break;

                    case IndexQuery.NEQ:
                        for (int i = 0; i < ptrs.length; i++) {
                            if (i != leftIdx) {
                                callback.indexInfo(values[i], ptrs[i]);
                            }
                        }
                        break;

                    case IndexQuery.BWX:
                    case IndexQuery.BW:
                    case IndexQuery.SW:
                    case IndexQuery.IN:
                        if (leftIdx < 0) {
                            leftIdx = -(leftIdx + 1);
                        }
                        if (rightIdx < 0) {
                            rightIdx = -(rightIdx + 1);
                        }
                        for (int i = 0; i < ptrs.length; i++) { // FIXME: VG: Optimize this loop
                            if (i >= leftIdx && i <= rightIdx && query.testValue(values[i])) {
                                callback.indexInfo(values[i], ptrs[i]);
                            }
                        }
                        break;

                    case IndexQuery.NBWX:
                    case IndexQuery.NBW:
                    case IndexQuery.NSW:
                        if (leftIdx < 0) {
                            leftIdx = -(leftIdx + 1);
                        }
                        if (rightIdx < 0) {
                            rightIdx = -(rightIdx + 1);
                        }
                        for (int i = 0; i < ptrs.length; i++) {
                            if ((i <= leftIdx || i >= rightIdx) && query.testValue(values[i])) {
                                callback.indexInfo(values[i], ptrs[i]);
                            }
                        }
                        break;

                        case IndexQuery.LT:
                        case IndexQuery.LEQ:
                            if (leftIdx < 0) {
                                leftIdx = -(leftIdx + 1);
                            }
                            for (int i = 0; i < ptrs.length; i++) {
                                if (i <= leftIdx && query.testValue(values[i])) {
                                    callback.indexInfo(values[i], ptrs[i]);
                                }
                            }
                            break;

                        case IndexQuery.GT:
                        case IndexQuery.GEQ:
                            if (rightIdx < 0) {
                                rightIdx = -(rightIdx + 1);
                            }

                            for (int i = 0; i < ptrs.length; i++) {
                                if (i >= rightIdx && query.testValue(values[i])) {
                                    callback.indexInfo(values[i], ptrs[i]);
                                }
                            }
                            break;

                        case IndexQuery.NIN:
                        default :
                            for (int i = 0; i < ptrs.length; i++) {
                                if (query.testValue(values[i])) {
                                    callback.indexInfo(values[i], ptrs[i]);
                                }
                            }
                            break;
                        }
                        break;

                    default :
                        throw new BTreeCorruptException("Invalid Page Type In query");
                    }

                } else {
                    // No Query - Just Walk The Tree
                    switch (ph.getStatus()) {
                    case BRANCH:
                        for (int i = 0; i < ptrs.length; i++) {
                            getChildNode(i).query(query, callback);
                        }
                        break;

                    case LEAF:
                        for (int i = 0; i < values.length; i++) {
                            callback.indexInfo(values[i], ptrs[i]);
                        }
                        break;

                    default :
                        throw new BTreeCorruptException("Invalid Page Type In query");
                    }
                }
            }
        }

        ////////////////////////////////////////////////////////////////////

        public FileHeader createFileHeader() {
            BTreeFileHeader header = new BTreeFileHeader();
            header.setPageCount(1);
            header.setTotalCount(1);
            return header;
        }

        public FileHeader createFileHeader(boolean read) throws IOException {
            return new BTreeFileHeader(read);
        }

        public FileHeader createFileHeader(long pageCount) {
            return new BTreeFileHeader(pageCount);
        }

        public FileHeader createFileHeader(long pageCount, int pageSize) {
            return new BTreeFileHeader(pageCount, pageSize);
        }

        public PageHeader createPageHeader() {
            return new BTreePageHeader();
        }

        /**
         * BTreeFileHeader
         */

        protected class BTreeFileHeader extends FileHeader {
            private long rootPage = 0;

            public BTreeFileHeader() {
	    }

            public BTreeFileHeader(long pageCount) {
                super(pageCount);
            }

            public BTreeFileHeader(long pageCount, int pageSize) {
                super(pageCount, pageSize);
            }

            public BTreeFileHeader(boolean read) throws IOException {
                super(read);
            }

            public synchronized void read(RandomAccessFile raf) throws IOException {
                super.read(raf);
                rootPage = raf.readLong();
            }

            public synchronized void write(RandomAccessFile raf) throws IOException {
                super.write(raf);
                raf.writeLong(rootPage);
            }

            /** The root page of the storage tree */
            public synchronized final void setRootPage(long rootPage) {
                this.rootPage = rootPage;
                setDirty();
            }

            /** The root page of the storage tree */
            public synchronized final long getRootPage() {
                return rootPage;
            }
        }

        /**
         * BTreePageHeader
         */

        protected class BTreePageHeader extends PageHeader {
            private short valueCount = 0;

            public BTreePageHeader() {
	    }

            public BTreePageHeader(DataInputStream dis) throws IOException {
                super(dis);
            }

            public synchronized void read(DataInputStream dis) throws IOException {
                super.read(dis);
                if (getStatus() == UNUSED) {
                    return;
                }

                valueCount = dis.readShort();
            }

            public synchronized void write(DataOutputStream dos) throws IOException {
                super.write(dos);
                dos.writeShort(valueCount);
            }

            /** The number of values stored by this page */
            public synchronized final void setValueCount(short valueCount) {
                this.valueCount = valueCount;
                setDirty();
            }

            /** The number of values stored by this page */
            public synchronized final short getValueCount() {
                return valueCount;
            }

            /** The number of pointers stored by this page */
            public synchronized final short getPointerCount() {
                if (getStatus() == BRANCH) {
                    return (short) (valueCount + 1);
                } else {
                    return valueCount;
                }
            }
        }
    }