RecordStoreIndexpublic 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_SIZEIDX_SIZE offset | | static final int | IDX1_ID_ROOTIDX_ID_ROOT offset | | static final int | IDX2_FREE_BLOCK_ROOTIDX_FREE_ROOT offset | | static final int | IDX3_FREE_NODE_HEADIDX_FREE_NODES offset | | static final int | IDX_HEADER_SIZESize of the index header | | static final int | NODE_ELEMENTSThe maximum number of data elements in each node | | static final int | NODE_SIZEThe size of the tree blocks | | private AbstractRecordStoreImpl | recordStoreThe Record Store that this object indexes | | private AbstractRecordStoreFile | dbFileThe Record Store database file | | private AbstractRecordStoreFile | idxFileThe Record Store database index file | | private byte[] | idxHeaderThe header of the index file | | private byte[] | nodeBufThe node buffer for initializing nodes | | private int | maxStackDepthMaximum 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.
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 int | allocateNode()Returns the offset to a free node if one exists. Otherwise,
returns the offset of a newly create node.
// 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;
| | void | close()Closes the index file.
idxFile.close();
| | static boolean | deleteIndex(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.
return RecordStoreUtil.quietDeleteFile(suiteId,
recordStoreName,
AbstractRecordStoreFile.IDX_EXTENSION);
| | int | deleteKey(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.
// 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 int | deleteKeyFromNode(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.
// 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;
| | void | deleteRecordIndex(int recordId)The record is deleted from the record store 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 int | findNodeWithKey(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.
// 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 void | freeNode(int inp_offset)Adds the node to the list of free nodes.
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();
| | int | getBlockOffsetOfRecord(int recordId)Returns the offset to the header for the given recordId
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;
| | int | getFreeBlock(byte[] header)Searches for a free block large enough for the record.
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;
| | int | getFreeBlockRootOffset()Gets the offset to the root of the free block tree.
return RecordStoreUtil.getInt(idxHeader, IDX2_FREE_BLOCK_ROOT);
| | int | getKeyValue(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
// find the node that contains the key
int index = findNodeWithKey(node, key);
if (node.key[index] == key) {
return node.value[index];
}
return 0;
| | int | getRecordHeader(int recordId, byte[] header)Finds the record header for the given record and returns the
offset to the header.
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.
int count = recordStore.getNumRecords();
int[] recordIdList = new int[count];
getRecordIds(recordIdList);
return recordIdList;
| | int | getRecordIdRootOffset()Gets the offset to the root of the recordId tree.
return RecordStoreUtil.getInt(idxHeader, IDX1_ID_ROOT);
| | int | getRecordIds(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.
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;
| | void | removeBlock(int blockOffset, byte[] header)Removes the given block from the list of free blocks.
| | void | setFreeBlockRootOffset(int newOffset)Sets the offset to the root of the free block tree.
RecordStoreUtil.putInt(newOffset, idxHeader, IDX2_FREE_BLOCK_ROOT);
idxFile.seek(0);
idxFile.write(idxHeader);
idxFile.commitWrite();
| | void | setRecordIdRootOffset(int newOffset)Sets the offset to the root of the recordId tree.
RecordStoreUtil.putInt(newOffset, idxHeader, IDX1_ID_ROOT);
idxFile.seek(0);
idxFile.write(idxHeader);
idxFile.commitWrite();
| | void | updateBlock(int blockOffset, byte[] header)Updates the index of the given block and its offset.
int recordId = RecordStoreUtil.getInt(header, 0);
if (recordId > 0) {
updateRecordId(recordId, blockOffset);
}
| | int | updateKey(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.
// 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;
| | void | updateRecordId(int recordId, int blockOffset)Updates the given recordId with the given offset. Adds the
recordId if it did not already exist.
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);
}
| | int | walk(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.
// 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;
|
|
