btree.java

JXTA&#8482 is a set of open, generalized peer-to-peer (P2P) protocols that allow any networked devi

                break;

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

            // 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(), rNode.page.getPageNum()});

                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());
            }
        }

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

        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");
                }
            }
        }
    }

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

    @Override
    public FileHeader createFileHeader() {
        BTreeFileHeader header = new BTreeFileHeader();

        header.setPageCount(1);
        header.setTotalCount(1);
        return header;
    }

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

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

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

    @Override
    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);
        }

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

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

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

        /**
         * The root page of the storage tree
         * @return the root page
         */
        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);
        }

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

            valueCount = dis.readShort();
        }

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

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

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

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