recordstoreindex.java

来自「This is a resource based on j2me embedde」· Java 代码 · 共 1,179 行 · 第 1/3 页

     * Gets the offset to the root of the recordId tree.
     *
     * @exception IOException if there is an error accessing the index file
     *
     * @return the offset of the recordId tree root
     */
    int getRecordIdRootOffset() throws IOException {
        return RecordStoreUtil.getInt(idxHeader, IDX1_ID_ROOT);
    }

    /**
     * Sets the offset to the root of the recordId tree.
     *
     * @param newOffset the new root offset
     *
     * @exception IOException if there is an error accessing the index file
     */
    void setRecordIdRootOffset(int newOffset) throws IOException {
        RecordStoreUtil.putInt(newOffset, idxHeader, IDX1_ID_ROOT);
        idxFile.seek(0);
        idxFile.write(idxHeader);
        idxFile.commitWrite();
    }

    /**
     * Gets the offset to the root of the free block tree.
     *
     * @exception IOException if there is an error accessing the index file
     *
     * @return the offset of the free block tree
     */
    int getFreeBlockRootOffset() throws IOException {
        return RecordStoreUtil.getInt(idxHeader, IDX2_FREE_BLOCK_ROOT);
    }

    /**
     * Sets the offset to the root of the free block tree.
     *
     * @param newOffset the new root offset
     *
     * @exception IOException if there is an error accessing the index file
     */
    void setFreeBlockRootOffset(int newOffset) throws IOException {
        RecordStoreUtil.putInt(newOffset, idxHeader, IDX2_FREE_BLOCK_ROOT);
        idxFile.seek(0);
        idxFile.write(idxHeader);
        idxFile.commitWrite();
    }

    /**
     *  node allocation and free management
     */

    /**
     * Returns the offset to a free node if one exists. Otherwise,
     * returns the offset of a newly create node.
     *
     * @exception IOException if there is an error accessing the index file
     *
     * @return the offset the new node in the index file
     */
    private int allocateNode() throws IOException {
        // check if there is a free node to use
        int loc_offset = RecordStoreUtil.getInt(idxHeader, IDX3_FREE_NODE_HEAD);

        if (loc_offset == 0) {
            // no free blocks, add one to the end of the index file
            loc_offset = RecordStoreUtil.getInt(idxHeader, IDX0_SIZE);
            RecordStoreUtil.putInt(loc_offset + NODE_SIZE,
	                           idxHeader, IDX0_SIZE);
        } else {
            idxFile.seek(loc_offset);
            idxFile.read(idxHeader, IDX3_FREE_NODE_HEAD, 4);
        }
        idxFile.seek(0);
        idxFile.write(idxHeader);
        idxFile.commitWrite();

        return loc_offset;
    }

    /**
     * Adds the node to the list of free nodes.
     *
     * @param inp_offset the offset of the node to free
     *
     * @exception IOException if there is an error accessing the index file
     */
    private void freeNode(int inp_offset) throws IOException {
        idxFile.seek(inp_offset);
        idxFile.write(idxHeader, IDX3_FREE_NODE_HEAD, 4);

        RecordStoreUtil.putInt(inp_offset, idxHeader, IDX3_FREE_NODE_HEAD);
        idxFile.seek(0);
        idxFile.write(idxHeader);
        idxFile.commitWrite();
    }


    /**
     *  Tree management
     */

    /**
     * Walks the tree starting at the given node and loads all of the tree's
     * keys into the given array.
     *
     * @param node the root node of the tree to walk
     * @param keyList array to fill with the tree's keys
     * @param count must be 0 for user call, other value for recursive call
     *
     * @exception IOException if there is an error accessing the index file
     *
     * @return the number of keys placed into the array.
     */
    int walk(Node node, int[] keyList, int count) throws IOException {
        // number of keys in the key list
	int i;
	if (count > keyList.length - 1) { // array is filled
	    return keyList.length;
	}
	for (i = 0; i < NODE_ELEMENTS + 1 &&
                    count < keyList.length; i++) {
	    if (node.child[i] > 0) { // subtree
                // load the node
	        int parent_offset = node.offset; // save the parent's offset
                node.load(node.child[i]);
	        count = walk(node, keyList, count); // walk along subtree
                node.load(parent_offset);     // the parent node
	    }
	    if (node.key[i] > 0 && count < keyList.length) {
	        // add the current key
                keyList[count++] = node.key[i];
	    } else { // no more keys - stop walking
	        break;
	    }
	}
        return count;
    }

    /**
     * Searches the tree starting at the given node for the given key and
     * returns the value associated with the key
     *
     * @param node the root node of the tree to search for the key
     * @param key the search key
     *
     * @exception IOException if there is an error accessing the index file
     *
     * @return the value for the key or 0 if the key was not found
     */
    int getKeyValue(Node node, int key) throws IOException {
        // find the node that contains the key
        int index = findNodeWithKey(node, key);

        if (node.key[index] == key) {
            return node.value[index];
        }

        return 0;
    }

    /**
     * Updates the tree starting with the given node with the key value pair.
     * If the key is already in the tree, the value is updated.  If the key
     * is not in the tree, it is inserted.  If the insertion causes the root
     * node to be split, the offset to the new root is returned, otherwise 0
     * is returned.
     *
     * @param node the root node of the tree to update the key with
     * @param key the key to update
     * @param value the new value
     *
     * @exception IOException if there is an error accessing the index file
     *
     * @return the offset of the new tree root if one was added, 0 otherwise
     */
    int updateKey(Node node,
                  int key, int value) throws IOException {
        // find the node that contains the key
        int index = findNodeWithKey(node, key);

        if (node.key[index] == key) {
            // key is already in the tree, update it
            node.value[index] = value;
            node.save();

            return 0;
        }

        // add the key to the node
        Node newNode = new Node(idxFile);
        int rightChild = 0;

        while (key > 0) {
            // add new triplet at index
            node.addKey(key, value, rightChild, index);

            // check if node has overflowed
            if (node.key[NODE_ELEMENTS] == 0) {
                node.save();
                break;
            }

            // node overflowed, split node
            newNode.init(allocateNode());

            // save the midpoint value
            key = node.key[NODE_ELEMENTS/2];
            value = node.value[NODE_ELEMENTS/2];
            rightChild = node.child[NODE_ELEMENTS/2 + 1];

            // clear midpoint
            node.key[NODE_ELEMENTS/2] = 0;
            node.value[NODE_ELEMENTS/2] = 0;
            node.child[NODE_ELEMENTS/2 + 1] = 0;

            // copy the top half of original node to new node
            int j = 0;
            newNode.child[0] = rightChild;
            for (int i = NODE_ELEMENTS/2 + 1; i < NODE_ELEMENTS+1; i++, j++) {
                newNode.key[j] = node.key[i];
                newNode.value[j] = node.value[i];
                newNode.child[j + 1] = node.child[i + 1];

                node.key[i] = 0;
                node.value[i] = 0;
                node.child[i + 1] = 0;
            }
            node.numKeys = NODE_ELEMENTS/2;
            newNode.numKeys = j;
            rightChild = newNode.offset;
            int leftChild = node.offset;

            // save both nodes
            node.save();
            newNode.save();

            // load the parent of the node
            int parentOffset = node.popParent();
            if (parentOffset == 0) {
                // need to add a new root to tree
                int newRoot = allocateNode();

                node.init(newRoot);
                node.key[0] = key;
                node.value[0] = value;
                node.child[0] = leftChild;
                node.child[1] = rightChild;
                node.save();

                // done with split
                return newRoot;
            }

            // load the parent
            node.load(parentOffset);

            // find position to insert the midpoint of split
            for (index = 0; index < NODE_ELEMENTS &&
                 node.child[index] != leftChild; index++);
        }

        return 0;
    }

    /**
     * Searches the tree starting with the given node for the given key. If
     * the key is in the tree, the key value pair is deleted.  If the key
     * is not in the tree, nothing happens.  If the deletion causes the root
     * node to be merged, the offset to the new root is returned, otherwise 0
     * is returned.
     *
     * @param node the root node of the tree to remove key from
     * @param key the key to remove
     *
     * @exception IOException if there is an error accessing the index file
     *
     * @return the offset of the new tree root if the old one was removed,
     *         otherwise 0
     */
    int deleteKey(Node node, int key) throws IOException {
        // find the key's node
        int index = findNodeWithKey(node, key);

        // check if key was found
        if (node.key[index] == key) {
            return deleteKeyFromNode(node, index);
        }

        return 0;
    }

    /**
     * Deleted the key value pair at the given index from the given node. If
     * the deletion causes the root node to be merged, the offset to the new
     * root is returned, otherwise 0 is returned.
     *
     * @param node the root node of the tree to remove key from
     * @param index the index to the key to remove
     *
     * @exception IOException if there is an error accessing the index file
     *
     * @return the offset of the new tree root if the old one was removed,
     *         otherwise 0
     */
    private int deleteKeyFromNode(Node node,
                                  int index) throws IOException {
        // check if this node has right child
        if (node.child[index+1] > 0) {
            // find the least key in the subtree
            Node rootNode = node;
            node = new Node(idxFile);
            node.load(rootNode.child[index+1]);
            node.copyStack(rootNode);
            node.pushParent(rootNode.offset);

            while (node.child[0] > 0) {
                node.pushParent(node.offset);
                node.load(node.child[0]);
            }

            // replace delete key with discovered key
            rootNode.key[index] = node.key[0];
            rootNode.value[index] = node.value[0];
            rootNode.save();

            // now delete discovered key
            index = 0;

            // preserve right subtree from deleting
            node.child[0] = node.child[1];
        }

        // the node has no right child for the key, remove the key
        node.deleteKey(index);
        node.save();

        // get the parent offset
        int parentOffset = node.popParent();

        // rebalance tree as needed
        while (parentOffset > 0) {
            // check if node needs to be merged with sibling
            if (node.numKeys >= NODE_ELEMENTS/2) {
                // this node has at least the minimum number of keys
                node.load(parentOffset);
                parentOffset = node.popParent();
                continue;
            }

            // load the parent of this node
            Node parentNode = new Node(idxFile);
            parentNode.load(parentOffset);

            // find the offset of the node in the parent
            int childIdx = 0;
            for (; parentNode.child[childIdx] != node.offset &&
                 childIdx < NODE_ELEMENTS+1; childIdx++);

            int midpointIdx = childIdx;
            Node siblingNode = null;

            // try loading the left sibling
            if (childIdx-1 >= 0) {
                // load the left sibling
                siblingNode = new Node(idxFile);
                siblingNode.load(parentNode.child[childIdx-1]);
                midpointIdx = childIdx-1;
            }

            // check if this is a merge candidate
            if (siblingNode == null ||
                node.numKeys + siblingNode.numKeys + 1 > NODE_ELEMENTS) {
                if (siblingNode == null) {
                    siblingNode = new Node(idxFile);
                }

                // not a merge candidate, check the right sibling
                if (childIdx+1 < NODE_ELEMENTS+1 &&
                    parentNode.child[childIdx+1] > 0) {
                    // load the right sibling
                    siblingNode.load(parentNode.child[childIdx+1]);
                    midpointIdx = childIdx;
                }
            }

            // check if a merge is needed
            if (node.numKeys + siblingNode.numKeys + 1 <= NODE_ELEMENTS) {
                // merge the siblings
                Node leftNode, rightNode;
                if (childIdx == midpointIdx) {
                    leftNode = node;