btree.java

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

            root.setPage(p);
            addValue(parent, root.name, p);
        }
    }

    /**
     * setRootNode resets the file's root to the provided
     * BTreeNode's page number.
     *
     * This method is not thread safe.
     *
     * @param rootNode the new root node to use
     * @throws java.io.IOException if an io error occurs
     * @throws BTreeException if a DB exception occurs
     */
    protected final void setRootNode(BTreeNode rootNode) throws IOException, BTreeException {
        setRootNode(rootInfo, rootNode);
    }

    /**
     * getRootNode retreives the BTree node for the specified
     * root object.
     *
     * @param root The root object to retrieve with
     * @return The root node
     */
    protected final BTreeNode getRootNode(BTreeRootInfo root) {
        if (root.page == rootInfo.page) {
            return rootNode;
        } else {
            return getBTreeNode(root.getPage(), null);
        }
    }

    /**
     * getRootNode retreives the BTree node for the file's root.
     *
     * @return The root node
     */
    protected final BTreeNode getRootNode() {
        return rootNode;
    }

    private BTreeNode getBTreeNode(long page, BTreeNode parent) {
        try {
            BTreeNode node = null;

            synchronized (cache) {
                WeakReference<BTreeNode> ref = cache.get(page);

                if (ref != null) {
                    node = ref.get();
                }

                if (node == null) {
                    node = new BTreeNode(getPage(page), parent);
                } else {
                    node.parent = parent;
                }

                cache.put(node.page.getPageNum(), new WeakReference<BTreeNode>(node));
            }

            node.read();
            return node;
        } catch (Exception e) {
            if (Logging.SHOW_WARNING && LOG.isLoggable(Level.WARNING)) {
                LOG.log(Level.WARNING, "Ignored exception", e);
            }
            return null;
        }
    }

    private BTreeNode createBTreeNode(byte status, BTreeNode parent) throws IOException {
        Page p = getFreePage();
        BTreeNode node = new BTreeNode(p, parent, new Value[0], new long[0]);

        node.ph.setStatus(status);
        synchronized (cache) {
            cache.put(p.getPageNum(), new WeakReference<BTreeNode>(node));
        }
        return node;
    }

    /**
     * BTreeRootInfo
     */
    public final class BTreeRootInfo {
        private final BTreeRootInfo parent;
        private final Value name;
        private long page;

        public BTreeRootInfo(BTreeRootInfo parent, String name, long page) {
            this.parent = parent;
            this.name = new Value(name);
            this.page = page;
        }

        public BTreeRootInfo(BTreeRootInfo parent, Value name, long page) {
            this.parent = parent;
            this.name = name;
            this.page = page;
        }

        public BTreeRootInfo(String name, long page) {
            this.parent = rootInfo;
            this.name = new Value(name);
            this.page = page;
        }

        public BTreeRootInfo(Value name, long page) {
            this.parent = rootInfo;
            this.name = name;
            this.page = page;
        }

        private BTreeRootInfo(long page) {
            parent = null;
            name = null;
            this.page = page;
        }

        public BTreeRootInfo getParent() {
            return parent;
        }

        public Value getName() {
            return name;
        }

        public synchronized long getPage() {
            return page;
        }

        public synchronized void setPage(long page) {
            this.page = page;
        }
    }


    /**
     * BTreeNode
     */
    private final class BTreeNode {
        private final Page page;
        private final BTreePageHeader ph;
        private Value[] values;
        private long[] ptrs;
        private BTreeNode parent;
        private boolean loaded;

        public BTreeNode(Page page) {
            this(page, null);
        }

        public BTreeNode(Page page, BTreeNode parent) {
            this.page = page;
            this.parent = parent;
            this.ph = (BTreePageHeader) page.getPageHeader();
        }

        public BTreeNode(Page page, BTreeNode parent, Value[] values, long[] ptrs) {
            this(page, parent);
            set(values, ptrs);
            this.loaded = true;
        }

        /**
         * Sets values and pointers.
         * Internal (to the BTreeNode) method, not synchronized.
         * @param ptrs  pointers
         * @param values their values
         */
        private void set(Value[] values, long[] ptrs) {
            this.values = values;
            this.ph.setValueCount((short) values.length);
            this.ptrs = ptrs;
        }

        /**
         * Reads node only if it is not loaded yet
         * @throws java.io.IOException if an io error occurs
         */
        public synchronized void read() throws IOException {
            if (!this.loaded) {
                Value v = readValue(page);
                DataInputStream is = new DataInputStream(v.getInputStream());

                // Read in the Values
                values = new Value[ph.getValueCount()];
                for (int i = 0; i < values.length; i++) {
                    short valSize = is.readShort();
                    byte[] b = new byte[valSize];

                    is.read(b);
                    values[i] = new Value(b);
                }

                // Read in the pointers
                ptrs = new long[ph.getPointerCount()];
                for (int i = 0; i < ptrs.length; i++) {
                    ptrs[i] = is.readLong();
                }

                this.loaded = true;
            }
        }

        public synchronized void write() throws IOException {
            ByteArrayOutputStream bos = new ByteArrayOutputStream(fileHeader.getWorkSize());
            DataOutputStream os = new DataOutputStream(bos);

            // Write out the Values
            for (Value value : values) {
                os.writeShort(value.getLength());
                value.streamTo(os);
            }

            // Write out the pointers
            for (long ptr : ptrs) {
                os.writeLong(ptr);
            }

            writeValue(page, new Value(bos.toByteArray()));
        }

        /**
         * Internal (to the BTreeNode) method.
         * Because this method is called only by BTreeNode itself, no synchronization done inside of this method.
         * @param idx  the index
         * @return the BTree node
         */
        private BTreeNode getChildNode(int idx) {
            if (ph.getStatus() == BRANCH && idx >= 0 && idx < ptrs.length) {
                return getBTreeNode(ptrs[idx], this);
            } else {
                return null;
            }
        }

        /* Not used
         private synchronized void getChildStream(int idx, Streamable stream) throws IOException {
         if (ph.getStatus() == LEAF && idx >= 0 && idx < ptrs.length) {
         Value v = readValue(ptrs[idx]);
         DataInputStream dis = new DataInputStream(v.getInputStream());
         stream.read(dis);
         }
         }
         */

        public synchronized long removeValue(Value value) throws IOException, BTreeException {
            int idx = Arrays.binarySearch(values, value);

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

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

                    set(deleteArrayValue(values, idx), deleteArrayLong(ptrs, idx));

                    write();
                    return oldPtr;
                }

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

        public synchronized long addValue(Value value, long pointer) throws IOException, BTreeException {
            if (value == null) {
                throw new BTreeException(FaultCodes.DBE_CANNOT_CREATE, "Can't add a null Value");
            }

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

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

            case LEAF:
                if (idx >= 0) {
                    // Value was found... Overwrite
                    long oldPtr = ptrs[idx];

                    ptrs[idx] = pointer;

                    set(values, ptrs);

                    write();
                    return oldPtr;
                } else {
                    // Value was not found
                    idx = -(idx + 1);

                    // Check to see if we've exhausted the block
                    boolean split = needSplit(value);

                    set(insertArrayValue(values, value, idx), insertArrayLong(ptrs, pointer, idx));

                    if (split) {
                        split();
                    } else {
                        write();
                    }
                }
                return -1;

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

        private synchronized void promoteValue(Value value, long rightPointer) throws IOException, BTreeException {
            // Check to see if we've exhausted the block
            boolean split = needSplit(value);

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

            idx = idx < 0 ? -(idx + 1) : idx + 1;

            set(insertArrayValue(values, value, idx), insertArrayLong(ptrs, rightPointer, idx + 1));

            if (split) {
                split();
            } else {
                write();
            }
        }

        private Value getSeparator(Value value1, Value value2) {
            int idx = value1.compareTo(value2);
            byte[] b = new byte[Math.abs(idx)];

            value2.copyTo(b, 0, b.length);
            return new Value(b);
        }

        /**
         * Do we need to split this node after adding one more value?
         * @param value the value to split
         * @return true if successful
         */
        private boolean needSplit(Value value) {
            // Do NOT split if just 4 key/values are in the node.
            return this.values.length > 4 && // CurrLength + one Long pointer + value length + one short
                    this.ph.getDataLen() + 8 + value.getLength() + 2 > BTree.this.fileHeader.getWorkSize();
        }

        /**
         * Internal to the BTreeNode method
         * @throws java.io.IOException if an io error occurs
         * @throws BTreeException if a DB exception occurs
         */
        private void split() throws IOException, BTreeException {
            Value[] leftVals;
            Value[] rightVals;
            long[] leftPtrs;
            long[] rightPtrs;
            Value separator;

            short vc = ph.getValueCount();
            int pivot = vc / 2;

            // Split the node into two nodes
            switch (ph.getStatus()) {
            case BRANCH:
                leftVals = new Value[pivot];
                leftPtrs = new long[leftVals.length + 1];
                rightVals = new Value[vc - (pivot + 1)];
                rightPtrs = new long[rightVals.length + 1];

                System.arraycopy(values, 0, leftVals, 0, leftVals.length);
                System.arraycopy(ptrs, 0, leftPtrs, 0, leftPtrs.length);
                System.arraycopy(values, leftVals.length + 1, rightVals, 0, rightVals.length);
                System.arraycopy(ptrs, leftPtrs.length, rightPtrs, 0, rightPtrs.length);

                separator = values[leftVals.length];
                break;

            case LEAF:
                leftVals = new Value[pivot];
                leftPtrs = new long[leftVals.length];
                rightVals = new Value[vc - pivot];
                rightPtrs = new long[rightVals.length];

                System.arraycopy(values, 0, leftVals, 0, leftVals.length);
                System.arraycopy(ptrs, 0, leftPtrs, 0, leftPtrs.length);
                System.arraycopy(values, leftVals.length, rightVals, 0, rightVals.length);
                System.arraycopy(ptrs, leftPtrs.length, rightPtrs, 0, rightPtrs.length);

                separator = getSeparator(leftVals[leftVals.length - 1], rightVals[0]);