FileDocCategorySizeDatePackage
RecordStoreIndex.javaAPI DocphoneME MR2 API (J2ME)39047Wed May 02 18:00:12 BST 2007com.sun.midp.rms

RecordStoreIndex

public class RecordStoreIndex extends Object
A class implementing a index of the record store. Methods used by the RecordStoreImpl close() deleteIndex() getRecordIDs() getRecordHeader() getFreeBlock() updateBlock() deleteRecordIndex() removeBlock()

Fields Summary
static final int
IDX0_SIZE
IDX_SIZE offset
static final int
IDX1_ID_ROOT
IDX_ID_ROOT offset
static final int
IDX2_FREE_BLOCK_ROOT
IDX_FREE_ROOT offset
static final int
IDX3_FREE_NODE_HEAD
IDX_FREE_NODES offset
static final int
IDX_HEADER_SIZE
Size of the index header
static final int
NODE_ELEMENTS
The maximum number of data elements in each node
static final int
NODE_SIZE
The size of the tree blocks
private AbstractRecordStoreImpl
recordStore
The Record Store that this object indexes
private AbstractRecordStoreFile
dbFile
The Record Store database file
private AbstractRecordStoreFile
idxFile
The Record Store database index file
private byte[]
idxHeader
The header of the index file
private byte[]
nodeBuf
The node buffer for initializing nodes
private int
maxStackDepth
Maximum depth of the parent node stack
Constructors Summary
RecordStoreIndex(AbstractRecordStoreImpl rs, int suiteId, String recordStoreName)
Constructor for creating an index object for the given Record Store.

param
rs record store that this object indexes
param
suiteId unique ID of the suite that owns the store
param
recordStoreName a string to name the record store
exception
IOException if there are any file errors


                                                        
       
                         
        recordStore = rs;
        if (rs != null) {
            dbFile = rs.getDbFile();
        }

        boolean exist =
          RecordStoreUtil.exists(suiteId, recordStoreName,
                                 AbstractRecordStoreFile.IDX_EXTENSION);

        idxFile = rs.createIndexFile(suiteId, recordStoreName);

        if (exist) {
            // load header
            if (idxFile.read(idxHeader) != IDX_HEADER_SIZE) {
               throw new IOException("Index file corrupted");
            }
        } else {
            RecordStoreUtil.putInt(IDX_HEADER_SIZE + NODE_SIZE * 2,
                                   idxHeader, IDX0_SIZE);
            RecordStoreUtil.putInt(IDX_HEADER_SIZE, idxHeader, IDX1_ID_ROOT);
            RecordStoreUtil.putInt(IDX_HEADER_SIZE + NODE_SIZE,
                                   idxHeader, IDX2_FREE_BLOCK_ROOT);
            idxFile.write(idxHeader);
            idxFile.write(nodeBuf);
            idxFile.write(nodeBuf);
            idxFile.commitWrite();
        }
    
Methods Summary
private intallocateNode()
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

        // 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;
    
voidclose()
Closes the index file.

exception
IOException if there are any file errors

        idxFile.close();
    
static booleandeleteIndex(int suiteId, java.lang.String recordStoreName)
Deletes index files of the named record store. MIDlet suites are only allowed to delete their own record stores.

param
suiteId ID of the MIDlet suite that owns the record store
param
recordStoreName the MIDlet suite unique record store to delete
return
true if file was found and deleted successfully, false otherwise.

        return RecordStoreUtil.quietDeleteFile(suiteId,
                                   recordStoreName,
                                   AbstractRecordStoreFile.IDX_EXTENSION);
    
intdeleteKey(com.sun.midp.rms.RecordStoreIndex$Node node, int key)
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

        // 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;
    
private intdeleteKeyFromNode(com.sun.midp.rms.RecordStoreIndex$Node node, int index)
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

        // 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;
                    rightNode = siblingNode;
                } else {
                    leftNode = siblingNode;
                    rightNode = node;
                }
                leftNode.addKey(parentNode.key[midpointIdx],
                                parentNode.value[midpointIdx],
                                rightNode.child[0],
                                leftNode.numKeys);

                for (int i = 0; i < rightNode.numKeys; i++) {
                    leftNode.addKey(rightNode.key[i],
                                    rightNode.value[i],
                                    rightNode.child[i+1],
                                    leftNode.numKeys);
                }

                leftNode.save();
                freeNode(rightNode.offset);

                parentNode.deleteKey(midpointIdx);
                if (parentNode.numKeys > 0) {
                    parentNode.save();
                } else {
                    // parentNode is empty
                    parentOffset = node.popParent();
                    if (parentOffset == 0) {
                        // the parent node is the root
                        return leftNode.offset;
                    } else {
                        int tempOffset = parentNode.offset;
                        freeNode(parentNode.offset);
                        parentNode.load(parentOffset);

                        // find the parentOffset
                        for (int x = 0; x < NODE_ELEMENTS+1; x++) {
                             if (parentNode.child[x] == tempOffset) {
                                 parentNode.child[x] = leftNode.offset;
                                 break;
                             }
                        }
                    }
                }
            } else {
                // could not merge the siblings
                // make sure each siblings has a minimum number of nodes
                if (midpointIdx == childIdx) {
                    // node is on the left, sibling is on the right
                    node.addKey(parentNode.key[midpointIdx],
                                parentNode.value[midpointIdx],
                                siblingNode.child[0],
                                node.numKeys);

                    parentNode.key[midpointIdx] = siblingNode.key[0];
                    parentNode.value[midpointIdx] = siblingNode.value[0];

                    siblingNode.child[0] = siblingNode.child[1];
                    siblingNode.deleteKey(0);
                } else {
                    // sibling is on the left, node is on the right
                    node.addKey(parentNode.key[midpointIdx],
                                parentNode.value[midpointIdx],
                                node.child[0],
                                0);

                    int tempIdx = siblingNode.numKeys;
                    node.child[0] = siblingNode.child[tempIdx];
                    parentNode.key[midpointIdx] = siblingNode.key[tempIdx-1];
                    parentNode.value[midpointIdx] =
                        siblingNode.value[tempIdx-1];
                    siblingNode.deleteKey(tempIdx-1);
                }

                siblingNode.save();
                parentNode.save();
                node.save();

                // check if the sibling lost too many keys
                if (siblingNode.numKeys < NODE_ELEMENTS/2) {
                    // make the sibling the merge candidate
                    siblingNode.copyStack(node);
                    node = siblingNode;
                    continue;
                }
            }

            // done with this node, move up the tree
            parentNode.copyStack(node);
            node = parentNode;
            parentOffset = node.popParent();
        }

        return 0;
    
voiddeleteRecordIndex(int recordId)
The record is deleted from the record store index.

param
recordId the ID of the record index to delete
exception
IOException if there is an error accessing the db index

        int rootOffset = getRecordIdRootOffset();
        Node node = new Node(idxFile);
        node.load(rootOffset);

        // find the key's node
        int loc_offset = deleteKey(node, recordId);

        // check if the offset of a new root was returned
        if (loc_offset > 0) {
            // new root, free old one
            freeNode(rootOffset);

            // save the new root
            setRecordIdRootOffset(loc_offset);
        }
    
private intfindNodeWithKey(com.sun.midp.rms.RecordStoreIndex$Node node, int key)
Searches the tree starting with the given node for the given key. The node that contains the key or the node where the key belongs is loaded into the given node object then the method returns. If the key is in the tree, the index of the key is returned. If the key is not in the tree, the index where the key should be inserted is returned.

param
node the root node of the tree to search for the key
param
key the key to search for
exception
IOException if there is an error accessing the index file
return
the index of the key or where the key belongs in the node

        // find node with given key
        int i = 0;
        while (i < NODE_ELEMENTS+1) {
            if (node.key[i] <= 0) {
                // reached end of keys
                // check if right child of last element exist
                if (node.child[i] > 0) {
                    // load the node
                    node.pushParent(node.offset);
                    node.load(node.child[i]);

                    // restart the loop for this node
                    i = 0;
                } else {
                    // key is not in tree, but belongs in this node
                    return i;
                }
            } else if (key == node.key[i]) {
                // found the key
                return i;
            } else if (key < node.key[i]) {
                // check for child tree
                if (node.child[i] > 0) {
                    // load the node
                    node.pushParent(node.offset);
                    node.load(node.child[i]);

                    // restart the loop for this node
                    i = 0;
                } else {
                    // key is not in tree, but belongs in this node
                    return i;
                }
            } else {
                i++;
            }
        }

        // belongs at the end of the current node
        return i;
    
private voidfreeNode(int inp_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

        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();
    
intgetBlockOffsetOfRecord(int recordId)
Returns the offset to the header for the given recordId

param
recordId the ID of the record to use in this operation
exception
IOException if there is an error accessing the db file
exception
InvalidRecordIDException if the recordId is invalid
return
the offset in the db file of the record block


        Node node = new Node(idxFile);
        node.load(getRecordIdRootOffset());

        int loc_offset = getKeyValue(node, recordId);

        if (loc_offset == 0) {
            // did not find the recordId
            throw new InvalidRecordIDException();
        }

        return loc_offset;
    
intgetFreeBlock(byte[] header)
Searches for a free block large enough for the record.

param
header a block header with the size set to the record data size
exception
IOException if there is an error accessing the db file
return
the offset in the db file of the block added

        int targetSize = RecordStoreUtil.
            calculateBlockSize(RecordStoreUtil.getInt(header, 4));
        int currentId = 0;
        int currentOffset = AbstractRecordStoreImpl.DB_HEADER_SIZE;
        int currentSize = 0;

        // search through the data blocks for a free block that is large enough
        while (currentOffset < recordStore.getSize()) {
            // seek to the next offset
            dbFile.seek(currentOffset);

            // read the block header
            if (dbFile.read(header) != AbstractRecordStoreImpl.BLOCK_HEADER_SIZE) {
                // did not find the recordId
                throw new IOException();
            }

            currentId = RecordStoreUtil.getInt(header, 0);
            currentSize = RecordStoreUtil.
                calculateBlockSize(RecordStoreUtil.getInt(header, 4));

            // check for a free block big enough to hold the data
            if (currentId < 0 && currentSize >= targetSize) {
                // a free block
                return currentOffset;
            }

            // added the block size to the currentOffset
            currentOffset += currentSize;
        }

        return 0;
    
intgetFreeBlockRootOffset()
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

        return RecordStoreUtil.getInt(idxHeader, IDX2_FREE_BLOCK_ROOT);
    
intgetKeyValue(com.sun.midp.rms.RecordStoreIndex$Node node, int key)
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

        // find the node that contains the key
        int index = findNodeWithKey(node, key);

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

        return 0;
    
intgetRecordHeader(int recordId, byte[] header)
Finds the record header for the given record and returns the offset to the header.

param
recordId the ID of the record to use in this operation
param
header the header of the block to free
exception
IOException if there is an error accessing the db file
exception
InvalidRecordIDException if the recordId is invalid
return
the offset in the db file of the block added


        if (recordId <= 0) {
            throw new InvalidRecordIDException("error finding record data");
        }

        int loc_offset = getBlockOffsetOfRecord(recordId);

        if (loc_offset == 0) {
            // did not find the recordId
            throw new InvalidRecordIDException();
        }

        // read the header
        dbFile.seek(loc_offset);

        // read the block header
        if (dbFile.read(header) != AbstractRecordStoreImpl.BLOCK_HEADER_SIZE) {
            // did not find the recordId
            throw new InvalidRecordIDException();
        }

        return loc_offset;
    
int[]getRecordIDs()
Returns all of the recordId's currently in the record store index.

return
an array of the recordId's currently in the index.

        int count = recordStore.getNumRecords();

        int[] recordIdList = new int[count];
        getRecordIds(recordIdList);

        return recordIdList;
    
intgetRecordIdRootOffset()
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

        return RecordStoreUtil.getInt(idxHeader, IDX1_ID_ROOT);
    
intgetRecordIds(int[] recordIdList)
Returns places all of the recordId's in the index. If the array is not big enough, the recordId list will be limited to the size of the given array.

param
recordIdList array to place the recordId's
return
the number of recordId's placed in the array.

        int count = 0;

        try {
            Node node = new Node(idxFile);
            node.load(getRecordIdRootOffset());

            count = walk(node, recordIdList, 0);
        } catch (IOException e) {
            if (Logging.REPORT_LEVEL <= Logging.ERROR) {
                Logging.report(Logging.ERROR, LogChannels.LC_RMS,
                               "Could not walk the tree");
            }
        }

        return count;
    
voidremoveBlock(int blockOffset, byte[] header)
Removes the given block from the list of free blocks.

param
blockOffset the offset in db file to the block to remove
param
header the header of the block to remove
exception
IOException if there is an error accessing the db file

    
voidsetFreeBlockRootOffset(int newOffset)
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

        RecordStoreUtil.putInt(newOffset, idxHeader, IDX2_FREE_BLOCK_ROOT);
        idxFile.seek(0);
        idxFile.write(idxHeader);
        idxFile.commitWrite();
    
voidsetRecordIdRootOffset(int newOffset)
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

        RecordStoreUtil.putInt(newOffset, idxHeader, IDX1_ID_ROOT);
        idxFile.seek(0);
        idxFile.write(idxHeader);
        idxFile.commitWrite();
    
voidupdateBlock(int blockOffset, byte[] header)
Updates the index of the given block and its offset.

param
blockOffset the offset in db file to the block to update
param
header the header of the block to update
exception
IOException if there is an error accessing the index file

        int recordId = RecordStoreUtil.getInt(header, 0);

        if (recordId > 0) {
            updateRecordId(recordId, blockOffset);
        }
    
intupdateKey(com.sun.midp.rms.RecordStoreIndex$Node node, int key, int value)
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

        // 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;
    
voidupdateRecordId(int recordId, int blockOffset)
Updates the given recordId with the given offset. Adds the recordId if it did not already exist.

param
recordId the id of the record
param
blockOffset the offset in db file to the block to update
exception
IOException if there is an error accessing the index file

        Node node = new Node(idxFile);
        node.load(getRecordIdRootOffset());

        // update the key
        int newOffset = updateKey(node, recordId, blockOffset);

        // check if a new root node was added
        if (newOffset > 0) {
            // save the new root node offset
            setRecordIdRootOffset(newOffset);
        }
    
intwalk(com.sun.midp.rms.RecordStoreIndex$Node node, int[] keyList, int count)
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.

        // 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;