0001: /*
0002: *
0003: *
0004: * Copyright 1990-2007 Sun Microsystems, Inc. All Rights Reserved.
0005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
0006: *
0007: * This program is free software; you can redistribute it and/or
0008: * modify it under the terms of the GNU General Public License version
0009: * 2 only, as published by the Free Software Foundation.
0010: *
0011: * This program is distributed in the hope that it will be useful, but
0012: * WITHOUT ANY WARRANTY; without even the implied warranty of
0013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
0014: * General Public License version 2 for more details (a copy is
0015: * included at /legal/license.txt).
0016: *
0017: * You should have received a copy of the GNU General Public License
0018: * version 2 along with this work; if not, write to the Free Software
0019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
0020: * 02110-1301 USA
0021: *
0022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
0023: * Clara, CA 95054 or visit www.sun.com if you need additional
0024: * information or have any questions.
0025: */
0026:
0027: package com.sun.midp.rms;
0028:
0029: import java.io.IOException;
0030:
0031: import javax.microedition.rms.*;
0032:
0033: import com.sun.midp.log.Logging;
0034: import com.sun.midp.log.LogChannels;
0035:
0036: /**
0037: * A class implementing a index of the record store.
0038: *
0039: * Methods used by the RecordStoreImpl
0040: * close()
0041: * deleteIndex()
0042: * getRecordIDs()
0043: * getRecordHeader()
0044: * getFreeBlock()
0045: * updateBlock()
0046: * deleteRecordIndex()
0047: * removeBlock()
0048: *
0049: */
0050:
0051: class RecordStoreIndex {
0052: /*
0053: * The layout of the database file is as follows:
0054: *
0055: * Bytes - Usage
0056: * 00-03 - Size of index file (big endian)
0057: * 04-07 - Offset to recordId tree root (big endian)
0058: * 08-11 - Offset to free block tree root (big endian)
0059: * 12-15 - Offset to the list of free tree blocks (big endian)
0060: * 16-xx - Tree Blocks
0061: */
0062:
0063: /** IDX_SIZE offset */
0064: static final int IDX0_SIZE = 0;
0065:
0066: /** IDX_ID_ROOT offset */
0067: static final int IDX1_ID_ROOT = 4;
0068:
0069: /** IDX_FREE_ROOT offset */
0070: static final int IDX2_FREE_BLOCK_ROOT = 8;
0071:
0072: /** IDX_FREE_NODES offset */
0073: static final int IDX3_FREE_NODE_HEAD = 12;
0074:
0075: /** Size of the index header */
0076: static final int IDX_HEADER_SIZE = 16;
0077:
0078: /** The maximum number of data elements in each node */
0079: static final int NODE_ELEMENTS = 8;
0080:
0081: /** The size of the tree blocks */
0082: static final int NODE_SIZE = 4 + (NODE_ELEMENTS * (4 + 4 + 4));
0083:
0084: /** The Record Store that this object indexes */
0085: private AbstractRecordStoreImpl recordStore;
0086:
0087: /** The Record Store database file */
0088: private AbstractRecordStoreFile dbFile;
0089:
0090: /** The Record Store database index file */
0091: private AbstractRecordStoreFile idxFile;
0092:
0093: /** The header of the index file */
0094: private byte[] idxHeader = new byte[IDX_HEADER_SIZE];
0095:
0096: /** The node buffer for initializing nodes */
0097: private byte[] nodeBuf = new byte[NODE_SIZE];
0098:
0099: /**
0100: * Constructor for creating an index object for the given Record Store.
0101: *
0102: * @param rs record store that this object indexes
0103: * @param suiteId unique ID of the suite that owns the store
0104: * @param recordStoreName a string to name the record store
0105: *
0106: * @exception IOException if there are any file errors
0107: */
0108: RecordStoreIndex(AbstractRecordStoreImpl rs, int suiteId,
0109: String recordStoreName) throws IOException {
0110: recordStore = rs;
0111: if (rs != null) {
0112: dbFile = rs.getDbFile();
0113: }
0114:
0115: boolean exist = RecordStoreUtil.exists(suiteId,
0116: recordStoreName, AbstractRecordStoreFile.IDX_EXTENSION);
0117:
0118: idxFile = rs.createIndexFile(suiteId, recordStoreName);
0119:
0120: if (exist) {
0121: // load header
0122: if (idxFile.read(idxHeader) != IDX_HEADER_SIZE) {
0123: throw new IOException("Index file corrupted");
0124: }
0125: } else {
0126: RecordStoreUtil.putInt(IDX_HEADER_SIZE + NODE_SIZE * 2,
0127: idxHeader, IDX0_SIZE);
0128: RecordStoreUtil.putInt(IDX_HEADER_SIZE, idxHeader,
0129: IDX1_ID_ROOT);
0130: RecordStoreUtil.putInt(IDX_HEADER_SIZE + NODE_SIZE,
0131: idxHeader, IDX2_FREE_BLOCK_ROOT);
0132: idxFile.write(idxHeader);
0133: idxFile.write(nodeBuf);
0134: idxFile.write(nodeBuf);
0135: idxFile.commitWrite();
0136: }
0137: }
0138:
0139: /**
0140: * Closes the index file.
0141: *
0142: * @exception IOException if there are any file errors
0143: */
0144: void close() throws IOException {
0145: idxFile.close();
0146: }
0147:
0148: /**
0149: * Deletes index files of the named record store. MIDlet suites are
0150: * only allowed to delete their own record stores.
0151: *
0152: * @param suiteId ID of the MIDlet suite that owns the record store
0153: * @param recordStoreName the MIDlet suite unique record store to
0154: * delete
0155: * @return <code>true</code> if file was found and deleted successfully,
0156: * <code>false</code> otherwise.
0157: */
0158: static boolean deleteIndex(int suiteId, String recordStoreName) {
0159: return RecordStoreUtil.quietDeleteFile(suiteId,
0160: recordStoreName, AbstractRecordStoreFile.IDX_EXTENSION);
0161: }
0162:
0163: /**
0164: * Returns all of the recordId's currently in the record store index.
0165: *
0166: * @return an array of the recordId's currently in the index.
0167: */
0168: int[] getRecordIDs() {
0169: int count = recordStore.getNumRecords();
0170:
0171: int[] recordIdList = new int[count];
0172: getRecordIds(recordIdList);
0173:
0174: return recordIdList;
0175: }
0176:
0177: /**
0178: * Returns places all of the recordId's in the index.
0179: * If the array is not big enough, the recordId list will be
0180: * limited to the size of the given array.
0181: *
0182: * @param recordIdList array to place the recordId's
0183: *
0184: * @return the number of recordId's placed in the array.
0185: */
0186: int getRecordIds(int[] recordIdList) {
0187: int count = 0;
0188:
0189: try {
0190: Node node = new Node(idxFile);
0191: node.load(getRecordIdRootOffset());
0192:
0193: count = walk(node, recordIdList, 0);
0194: } catch (IOException e) {
0195: if (Logging.REPORT_LEVEL <= Logging.ERROR) {
0196: Logging.report(Logging.ERROR, LogChannels.LC_RMS,
0197: "Could not walk the tree");
0198: }
0199: }
0200:
0201: return count;
0202: }
0203:
0204: /**
0205: * Finds the record header for the given record and returns the
0206: * offset to the header.
0207: *
0208: * @param recordId the ID of the record to use in this operation
0209: * @param header the header of the block to free
0210: *
0211: * @exception IOException if there is an error accessing the db file
0212: * @exception InvalidRecordIDException if the recordId is invalid
0213: *
0214: * @return the offset in the db file of the block added
0215: */
0216: int getRecordHeader(int recordId, byte[] header)
0217: throws IOException, InvalidRecordIDException {
0218:
0219: if (recordId <= 0) {
0220: throw new InvalidRecordIDException(
0221: "error finding record data");
0222: }
0223:
0224: int loc_offset = getBlockOffsetOfRecord(recordId);
0225:
0226: if (loc_offset == 0) {
0227: // did not find the recordId
0228: throw new InvalidRecordIDException();
0229: }
0230:
0231: // read the header
0232: dbFile.seek(loc_offset);
0233:
0234: // read the block header
0235: if (dbFile.read(header) != AbstractRecordStoreImpl.BLOCK_HEADER_SIZE) {
0236: // did not find the recordId
0237: throw new InvalidRecordIDException();
0238: }
0239:
0240: return loc_offset;
0241: }
0242:
0243: /**
0244: * Returns the offset to the header for the given recordId
0245: *
0246: * @param recordId the ID of the record to use in this operation
0247: *
0248: * @exception IOException if there is an error accessing the db file
0249: * @exception InvalidRecordIDException if the recordId is invalid
0250: *
0251: * @return the offset in the db file of the record block
0252: */
0253: int getBlockOffsetOfRecord(int recordId) throws IOException,
0254: InvalidRecordIDException {
0255:
0256: Node node = new Node(idxFile);
0257: node.load(getRecordIdRootOffset());
0258:
0259: int loc_offset = getKeyValue(node, recordId);
0260:
0261: if (loc_offset == 0) {
0262: // did not find the recordId
0263: throw new InvalidRecordIDException();
0264: }
0265:
0266: return loc_offset;
0267: }
0268:
0269: /**
0270: * Updates the index of the given block and its offset.
0271: *
0272: * @param blockOffset the offset in db file to the block to update
0273: * @param header the header of the block to update
0274: *
0275: * @exception IOException if there is an error accessing the index file
0276: */
0277: void updateBlock(int blockOffset, byte[] header) throws IOException {
0278: int recordId = RecordStoreUtil.getInt(header, 0);
0279:
0280: if (recordId > 0) {
0281: updateRecordId(recordId, blockOffset);
0282: }
0283: }
0284:
0285: /**
0286: * Updates the given recordId with the given offset. Adds the
0287: * recordId if it did not already exist.
0288: *
0289: * @param recordId the id of the record
0290: * @param blockOffset the offset in db file to the block to update
0291: *
0292: * @exception IOException if there is an error accessing the index file
0293: */
0294: void updateRecordId(int recordId, int blockOffset)
0295: throws IOException {
0296: Node node = new Node(idxFile);
0297: node.load(getRecordIdRootOffset());
0298:
0299: // update the key
0300: int newOffset = updateKey(node, recordId, blockOffset);
0301:
0302: // check if a new root node was added
0303: if (newOffset > 0) {
0304: // save the new root node offset
0305: setRecordIdRootOffset(newOffset);
0306: }
0307: }
0308:
0309: /**
0310: * The record is deleted from the record store index.
0311: *
0312: * @param recordId the ID of the record index to delete
0313: *
0314: * @exception IOException if there is an error accessing the db index
0315: */
0316: void deleteRecordIndex(int recordId) throws IOException {
0317: int rootOffset = getRecordIdRootOffset();
0318: Node node = new Node(idxFile);
0319: node.load(rootOffset);
0320:
0321: // find the key's node
0322: int loc_offset = deleteKey(node, recordId);
0323:
0324: // check if the offset of a new root was returned
0325: if (loc_offset > 0) {
0326: // new root, free old one
0327: freeNode(rootOffset);
0328:
0329: // save the new root
0330: setRecordIdRootOffset(loc_offset);
0331: }
0332: }
0333:
0334: /**
0335: * Searches for a free block large enough for the record.
0336: *
0337: * @param header a block header with the size set to the record data size
0338: *
0339: * @exception IOException if there is an error accessing the db file
0340: *
0341: * @return the offset in the db file of the block added
0342: */
0343: int getFreeBlock(byte[] header) throws IOException {
0344: int targetSize = RecordStoreUtil
0345: .calculateBlockSize(RecordStoreUtil.getInt(header, 4));
0346: int currentId = 0;
0347: int currentOffset = AbstractRecordStoreImpl.DB_HEADER_SIZE;
0348: int currentSize = 0;
0349:
0350: // search through the data blocks for a free block that is large enough
0351: while (currentOffset < recordStore.getSize()) {
0352: // seek to the next offset
0353: dbFile.seek(currentOffset);
0354:
0355: // read the block header
0356: if (dbFile.read(header) != AbstractRecordStoreImpl.BLOCK_HEADER_SIZE) {
0357: // did not find the recordId
0358: throw new IOException();
0359: }
0360:
0361: currentId = RecordStoreUtil.getInt(header, 0);
0362: currentSize = RecordStoreUtil
0363: .calculateBlockSize(RecordStoreUtil.getInt(header,
0364: 4));
0365:
0366: // check for a free block big enough to hold the data
0367: if (currentId < 0 && currentSize >= targetSize) {
0368: // a free block
0369: return currentOffset;
0370: }
0371:
0372: // added the block size to the currentOffset
0373: currentOffset += currentSize;
0374: }
0375:
0376: return 0;
0377: }
0378:
0379: /**
0380: * Removes the given block from the list of free blocks.
0381: *
0382: * @param blockOffset the offset in db file to the block to remove
0383: * @param header the header of the block to remove
0384: *
0385: * @exception IOException if there is an error accessing the db file
0386: */
0387: void removeBlock(int blockOffset, byte[] header) throws IOException {
0388: }
0389:
0390: /**
0391: * Getter/Setter for header info
0392: */
0393:
0394: /**
0395: * Gets the offset to the root of the recordId tree.
0396: *
0397: * @exception IOException if there is an error accessing the index file
0398: *
0399: * @return the offset of the recordId tree root
0400: */
0401: int getRecordIdRootOffset() throws IOException {
0402: return RecordStoreUtil.getInt(idxHeader, IDX1_ID_ROOT);
0403: }
0404:
0405: /**
0406: * Sets the offset to the root of the recordId tree.
0407: *
0408: * @param newOffset the new root offset
0409: *
0410: * @exception IOException if there is an error accessing the index file
0411: */
0412: void setRecordIdRootOffset(int newOffset) throws IOException {
0413: RecordStoreUtil.putInt(newOffset, idxHeader, IDX1_ID_ROOT);
0414: idxFile.seek(0);
0415: idxFile.write(idxHeader);
0416: idxFile.commitWrite();
0417: }
0418:
0419: /**
0420: * Gets the offset to the root of the free block tree.
0421: *
0422: * @exception IOException if there is an error accessing the index file
0423: *
0424: * @return the offset of the free block tree
0425: */
0426: int getFreeBlockRootOffset() throws IOException {
0427: return RecordStoreUtil.getInt(idxHeader, IDX2_FREE_BLOCK_ROOT);
0428: }
0429:
0430: /**
0431: * Sets the offset to the root of the free block tree.
0432: *
0433: * @param newOffset the new root offset
0434: *
0435: * @exception IOException if there is an error accessing the index file
0436: */
0437: void setFreeBlockRootOffset(int newOffset) throws IOException {
0438: RecordStoreUtil.putInt(newOffset, idxHeader,
0439: IDX2_FREE_BLOCK_ROOT);
0440: idxFile.seek(0);
0441: idxFile.write(idxHeader);
0442: idxFile.commitWrite();
0443: }
0444:
0445: /**
0446: * node allocation and free management
0447: */
0448:
0449: /**
0450: * Returns the offset to a free node if one exists. Otherwise,
0451: * returns the offset of a newly create node.
0452: *
0453: * @exception IOException if there is an error accessing the index file
0454: *
0455: * @return the offset the new node in the index file
0456: */
0457: private int allocateNode() throws IOException {
0458: // check if there is a free node to use
0459: int loc_offset = RecordStoreUtil.getInt(idxHeader,
0460: IDX3_FREE_NODE_HEAD);
0461:
0462: if (loc_offset == 0) {
0463: // no free blocks, add one to the end of the index file
0464: loc_offset = RecordStoreUtil.getInt(idxHeader, IDX0_SIZE);
0465: RecordStoreUtil.putInt(loc_offset + NODE_SIZE, idxHeader,
0466: IDX0_SIZE);
0467: } else {
0468: idxFile.seek(loc_offset);
0469: idxFile.read(idxHeader, IDX3_FREE_NODE_HEAD, 4);
0470: }
0471: idxFile.seek(0);
0472: idxFile.write(idxHeader);
0473: idxFile.commitWrite();
0474:
0475: return loc_offset;
0476: }
0477:
0478: /**
0479: * Adds the node to the list of free nodes.
0480: *
0481: * @param inp_offset the offset of the node to free
0482: *
0483: * @exception IOException if there is an error accessing the index file
0484: */
0485: private void freeNode(int inp_offset) throws IOException {
0486: idxFile.seek(inp_offset);
0487: idxFile.write(idxHeader, IDX3_FREE_NODE_HEAD, 4);
0488:
0489: RecordStoreUtil.putInt(inp_offset, idxHeader,
0490: IDX3_FREE_NODE_HEAD);
0491: idxFile.seek(0);
0492: idxFile.write(idxHeader);
0493: idxFile.commitWrite();
0494: }
0495:
0496: /**
0497: * Tree management
0498: */
0499:
0500: /**
0501: * Walks the tree starting at the given node and loads all of the tree's
0502: * keys into the given array.
0503: *
0504: * @param node the root node of the tree to walk
0505: * @param keyList array to fill with the tree's keys
0506: * @param count must be 0 for user call, other value for recursive call
0507: *
0508: * @exception IOException if there is an error accessing the index file
0509: *
0510: * @return the number of keys placed into the array.
0511: */
0512: int walk(Node node, int[] keyList, int count) throws IOException {
0513: // number of keys in the key list
0514: int i;
0515: if (count > keyList.length - 1) { // array is filled
0516: return keyList.length;
0517: }
0518: for (i = 0; i < NODE_ELEMENTS + 1 && count < keyList.length; i++) {
0519: if (node.child[i] > 0) { // subtree
0520: // load the node
0521: int parent_offset = node.offset; // save the parent's offset
0522: node.load(node.child[i]);
0523: count = walk(node, keyList, count); // walk along subtree
0524: node.load(parent_offset); // the parent node
0525: }
0526: if (node.key[i] > 0 && count < keyList.length) {
0527: // add the current key
0528: keyList[count++] = node.key[i];
0529: } else { // no more keys - stop walking
0530: break;
0531: }
0532: }
0533: return count;
0534: }
0535:
0536: /**
0537: * Searches the tree starting at the given node for the given key and
0538: * returns the value associated with the key
0539: *
0540: * @param node the root node of the tree to search for the key
0541: * @param key the search key
0542: *
0543: * @exception IOException if there is an error accessing the index file
0544: *
0545: * @return the value for the key or 0 if the key was not found
0546: */
0547: int getKeyValue(Node node, int key) throws IOException {
0548: // find the node that contains the key
0549: int index = findNodeWithKey(node, key);
0550:
0551: if (node.key[index] == key) {
0552: return node.value[index];
0553: }
0554:
0555: return 0;
0556: }
0557:
0558: /**
0559: * Updates the tree starting with the given node with the key value pair.
0560: * If the key is already in the tree, the value is updated. If the key
0561: * is not in the tree, it is inserted. If the insertion causes the root
0562: * node to be split, the offset to the new root is returned, otherwise 0
0563: * is returned.
0564: *
0565: * @param node the root node of the tree to update the key with
0566: * @param key the key to update
0567: * @param value the new value
0568: *
0569: * @exception IOException if there is an error accessing the index file
0570: *
0571: * @return the offset of the new tree root if one was added, 0 otherwise
0572: */
0573: int updateKey(Node node, int key, int value) throws IOException {
0574: // find the node that contains the key
0575: int index = findNodeWithKey(node, key);
0576:
0577: if (node.key[index] == key) {
0578: // key is already in the tree, update it
0579: node.value[index] = value;
0580: node.save();
0581:
0582: return 0;
0583: }
0584:
0585: // add the key to the node
0586: Node newNode = new Node(idxFile);
0587: int rightChild = 0;
0588:
0589: while (key > 0) {
0590: // add new triplet at index
0591: node.addKey(key, value, rightChild, index);
0592:
0593: // check if node has overflowed
0594: if (node.key[NODE_ELEMENTS] == 0) {
0595: node.save();
0596: break;
0597: }
0598:
0599: // node overflowed, split node
0600: newNode.init(allocateNode());
0601:
0602: // save the midpoint value
0603: key = node.key[NODE_ELEMENTS / 2];
0604: value = node.value[NODE_ELEMENTS / 2];
0605: rightChild = node.child[NODE_ELEMENTS / 2 + 1];
0606:
0607: // clear midpoint
0608: node.key[NODE_ELEMENTS / 2] = 0;
0609: node.value[NODE_ELEMENTS / 2] = 0;
0610: node.child[NODE_ELEMENTS / 2 + 1] = 0;
0611:
0612: // copy the top half of original node to new node
0613: int j = 0;
0614: newNode.child[0] = rightChild;
0615: for (int i = NODE_ELEMENTS / 2 + 1; i < NODE_ELEMENTS + 1; i++, j++) {
0616: newNode.key[j] = node.key[i];
0617: newNode.value[j] = node.value[i];
0618: newNode.child[j + 1] = node.child[i + 1];
0619:
0620: node.key[i] = 0;
0621: node.value[i] = 0;
0622: node.child[i + 1] = 0;
0623: }
0624: node.numKeys = NODE_ELEMENTS / 2;
0625: newNode.numKeys = j;
0626: rightChild = newNode.offset;
0627: int leftChild = node.offset;
0628:
0629: // save both nodes
0630: node.save();
0631: newNode.save();
0632:
0633: // load the parent of the node
0634: int parentOffset = node.popParent();
0635: if (parentOffset == 0) {
0636: // need to add a new root to tree
0637: int newRoot = allocateNode();
0638:
0639: node.init(newRoot);
0640: node.key[0] = key;
0641: node.value[0] = value;
0642: node.child[0] = leftChild;
0643: node.child[1] = rightChild;
0644: node.save();
0645:
0646: // done with split
0647: return newRoot;
0648: }
0649:
0650: // load the parent
0651: node.load(parentOffset);
0652:
0653: // find position to insert the midpoint of split
0654: for (index = 0; index < NODE_ELEMENTS
0655: && node.child[index] != leftChild; index++)
0656: ;
0657: }
0658:
0659: return 0;
0660: }
0661:
0662: /**
0663: * Searches the tree starting with the given node for the given key. If
0664: * the key is in the tree, the key value pair is deleted. If the key
0665: * is not in the tree, nothing happens. If the deletion causes the root
0666: * node to be merged, the offset to the new root is returned, otherwise 0
0667: * is returned.
0668: *
0669: * @param node the root node of the tree to remove key from
0670: * @param key the key to remove
0671: *
0672: * @exception IOException if there is an error accessing the index file
0673: *
0674: * @return the offset of the new tree root if the old one was removed,
0675: * otherwise 0
0676: */
0677: int deleteKey(Node node, int key) throws IOException {
0678: // find the key's node
0679: int index = findNodeWithKey(node, key);
0680:
0681: // check if key was found
0682: if (node.key[index] == key) {
0683: return deleteKeyFromNode(node, index);
0684: }
0685:
0686: return 0;
0687: }
0688:
0689: /**
0690: * Deleted the key value pair at the given index from the given node. If
0691: * the deletion causes the root node to be merged, the offset to the new
0692: * root is returned, otherwise 0 is returned.
0693: *
0694: * @param node the root node of the tree to remove key from
0695: * @param index the index to the key to remove
0696: *
0697: * @exception IOException if there is an error accessing the index file
0698: *
0699: * @return the offset of the new tree root if the old one was removed,
0700: * otherwise 0
0701: */
0702: private int deleteKeyFromNode(Node node, int index)
0703: throws IOException {
0704: // check if this node has right child
0705: if (node.child[index + 1] > 0) {
0706: // find the least key in the subtree
0707: Node rootNode = node;
0708: node = new Node(idxFile);
0709: node.load(rootNode.child[index + 1]);
0710: node.copyStack(rootNode);
0711: node.pushParent(rootNode.offset);
0712:
0713: while (node.child[0] > 0) {
0714: node.pushParent(node.offset);
0715: node.load(node.child[0]);
0716: }
0717:
0718: // replace delete key with discovered key
0719: rootNode.key[index] = node.key[0];
0720: rootNode.value[index] = node.value[0];
0721: rootNode.save();
0722:
0723: // now delete discovered key
0724: index = 0;
0725:
0726: // preserve right subtree from deleting
0727: node.child[0] = node.child[1];
0728: }
0729:
0730: // the node has no right child for the key, remove the key
0731: node.deleteKey(index);
0732: node.save();
0733:
0734: // get the parent offset
0735: int parentOffset = node.popParent();
0736:
0737: // rebalance tree as needed
0738: while (parentOffset > 0) {
0739: // check if node needs to be merged with sibling
0740: if (node.numKeys >= NODE_ELEMENTS / 2) {
0741: // this node has at least the minimum number of keys
0742: node.load(parentOffset);
0743: parentOffset = node.popParent();
0744: continue;
0745: }
0746:
0747: // load the parent of this node
0748: Node parentNode = new Node(idxFile);
0749: parentNode.load(parentOffset);
0750:
0751: // find the offset of the node in the parent
0752: int childIdx = 0;
0753: for (; parentNode.child[childIdx] != node.offset
0754: && childIdx < NODE_ELEMENTS + 1; childIdx++)
0755: ;
0756:
0757: int midpointIdx = childIdx;
0758: Node siblingNode = null;
0759:
0760: // try loading the left sibling
0761: if (childIdx - 1 >= 0) {
0762: // load the left sibling
0763: siblingNode = new Node(idxFile);
0764: siblingNode.load(parentNode.child[childIdx - 1]);
0765: midpointIdx = childIdx - 1;
0766: }
0767:
0768: // check if this is a merge candidate
0769: if (siblingNode == null
0770: || node.numKeys + siblingNode.numKeys + 1 > NODE_ELEMENTS) {
0771: if (siblingNode == null) {
0772: siblingNode = new Node(idxFile);
0773: }
0774:
0775: // not a merge candidate, check the right sibling
0776: if (childIdx + 1 < NODE_ELEMENTS + 1
0777: && parentNode.child[childIdx + 1] > 0) {
0778: // load the right sibling
0779: siblingNode.load(parentNode.child[childIdx + 1]);
0780: midpointIdx = childIdx;
0781: }
0782: }
0783:
0784: // check if a merge is needed
0785: if (node.numKeys + siblingNode.numKeys + 1 <= NODE_ELEMENTS) {
0786: // merge the siblings
0787: Node leftNode, rightNode;
0788: if (childIdx == midpointIdx) {
0789: leftNode = node;
0790: rightNode = siblingNode;
0791: } else {
0792: leftNode = siblingNode;
0793: rightNode = node;
0794: }
0795: leftNode.addKey(parentNode.key[midpointIdx],
0796: parentNode.value[midpointIdx],
0797: rightNode.child[0], leftNode.numKeys);
0798:
0799: for (int i = 0; i < rightNode.numKeys; i++) {
0800: leftNode.addKey(rightNode.key[i],
0801: rightNode.value[i], rightNode.child[i + 1],
0802: leftNode.numKeys);
0803: }
0804:
0805: leftNode.save();
0806: freeNode(rightNode.offset);
0807:
0808: parentNode.deleteKey(midpointIdx);
0809: if (parentNode.numKeys > 0) {
0810: parentNode.save();
0811: } else {
0812: // parentNode is empty
0813: parentOffset = node.popParent();
0814: if (parentOffset == 0) {
0815: // the parent node is the root
0816: return leftNode.offset;
0817: } else {
0818: int tempOffset = parentNode.offset;
0819: freeNode(parentNode.offset);
0820: parentNode.load(parentOffset);
0821:
0822: // find the parentOffset
0823: for (int x = 0; x < NODE_ELEMENTS + 1; x++) {
0824: if (parentNode.child[x] == tempOffset) {
0825: parentNode.child[x] = leftNode.offset;
0826: break;
0827: }
0828: }
0829: }
0830: }
0831: } else {
0832: // could not merge the siblings
0833: // make sure each siblings has a minimum number of nodes
0834: if (midpointIdx == childIdx) {
0835: // node is on the left, sibling is on the right
0836: node.addKey(parentNode.key[midpointIdx],
0837: parentNode.value[midpointIdx],
0838: siblingNode.child[0], node.numKeys);
0839:
0840: parentNode.key[midpointIdx] = siblingNode.key[0];
0841: parentNode.value[midpointIdx] = siblingNode.value[0];
0842:
0843: siblingNode.child[0] = siblingNode.child[1];
0844: siblingNode.deleteKey(0);
0845: } else {
0846: // sibling is on the left, node is on the right
0847: node.addKey(parentNode.key[midpointIdx],
0848: parentNode.value[midpointIdx],
0849: node.child[0], 0);
0850:
0851: int tempIdx = siblingNode.numKeys;
0852: node.child[0] = siblingNode.child[tempIdx];
0853: parentNode.key[midpointIdx] = siblingNode.key[tempIdx - 1];
0854: parentNode.value[midpointIdx] = siblingNode.value[tempIdx - 1];
0855: siblingNode.deleteKey(tempIdx - 1);
0856: }
0857:
0858: siblingNode.save();
0859: parentNode.save();
0860: node.save();
0861:
0862: // check if the sibling lost too many keys
0863: if (siblingNode.numKeys < NODE_ELEMENTS / 2) {
0864: // make the sibling the merge candidate
0865: siblingNode.copyStack(node);
0866: node = siblingNode;
0867: continue;
0868: }
0869: }
0870:
0871: // done with this node, move up the tree
0872: parentNode.copyStack(node);
0873: node = parentNode;
0874: parentOffset = node.popParent();
0875: }
0876:
0877: return 0;
0878: }
0879:
0880: /**
0881: * Searches the tree starting with the given node for the given key. The
0882: * node that contains the key or the node where the key belongs is loaded
0883: * into the given node object then the method returns. If the key is in
0884: * the tree, the index of the key is returned. If the key is not in the
0885: * tree, the index where the key should be inserted is returned.
0886: *
0887: * @param node the root node of the tree to search for the key
0888: * @param key the key to search for
0889: *
0890: * @exception IOException if there is an error accessing the index file
0891: *
0892: * @return the index of the key or where the key belongs in the node
0893: */
0894: private int findNodeWithKey(Node node, int key) throws IOException {
0895: // find node with given key
0896: int i = 0;
0897: while (i < NODE_ELEMENTS + 1) {
0898: if (node.key[i] <= 0) {
0899: // reached end of keys
0900: // check if right child of last element exist
0901: if (node.child[i] > 0) {
0902: // load the node
0903: node.pushParent(node.offset);
0904: node.load(node.child[i]);
0905:
0906: // restart the loop for this node
0907: i = 0;
0908: } else {
0909: // key is not in tree, but belongs in this node
0910: return i;
0911: }
0912: } else if (key == node.key[i]) {
0913: // found the key
0914: return i;
0915: } else if (key < node.key[i]) {
0916: // check for child tree
0917: if (node.child[i] > 0) {
0918: // load the node
0919: node.pushParent(node.offset);
0920: node.load(node.child[i]);
0921:
0922: // restart the loop for this node
0923: i = 0;
0924: } else {
0925: // key is not in tree, but belongs in this node
0926: return i;
0927: }
0928: } else {
0929: i++;
0930: }
0931: }
0932:
0933: // belongs at the end of the current node
0934: return i;
0935: }
0936:
0937: /** Maximum depth of the parent node stack */
0938: private int maxStackDepth = 3;
0939:
0940: /**
0941: * Abstraction of a tree node
0942: */
0943: class Node {
0944: /** file that contains the tree, the index file */
0945: AbstractRecordStoreFile treeFile;
0946:
0947: /** number of keys in this node */
0948: int numKeys;
0949:
0950: /** offset of this node in the tree file */
0951: int offset;
0952:
0953: /** keys in this node */
0954: int[] key = new int[NODE_ELEMENTS + 1];
0955:
0956: /** values in this node */
0957: int[] value = new int[NODE_ELEMENTS + 1];
0958:
0959: /** children in this node */
0960: int[] child = new int[NODE_ELEMENTS + 2];
0961:
0962: /** stack of parents of this node */
0963: int[] parentStack = new int[maxStackDepth];
0964:
0965: /** depth of the parent stack */
0966: int stackDepth = 0;
0967:
0968: /**
0969: * Constructor for creating a node in the tree.
0970: *
0971: * @param file the index file that contains this node
0972: */
0973: Node(AbstractRecordStoreFile file) {
0974: treeFile = file;
0975: }
0976:
0977: /**
0978: * Adds the given offset to the parent stack. Grows the stack as needed.
0979: *
0980: * @param inp_offset the offset value to push on top of the stack
0981: */
0982: void pushParent(int inp_offset) {
0983: if (stackDepth == parentStack.length) {
0984: maxStackDepth++;
0985: int[] newStack = new int[maxStackDepth];
0986: // copy old stack
0987: for (int i = 0; i < stackDepth; i++) {
0988: newStack[i] = parentStack[i];
0989: }
0990: parentStack = newStack;
0991: newStack = null;
0992: }
0993:
0994: parentStack[stackDepth++] = inp_offset;
0995: }
0996:
0997: /**
0998: * Removes the top value of the stack and returns it.
0999: *
1000: * @return the top value of the stack or 0 if the stack is empty
1001: */
1002: int popParent() {
1003: if (stackDepth > 0) {
1004: return parentStack[--stackDepth];
1005: }
1006:
1007: return 0;
1008: }
1009:
1010: /**
1011: * Copies the stack of the given node to this node.
1012: *
1013: * @param fromNode the node whose stack is to be copied
1014: */
1015: void copyStack(Node fromNode) {
1016: stackDepth = 0;
1017: for (int i = 0; i < fromNode.stackDepth; i++) {
1018: pushParent(fromNode.parentStack[i]);
1019: }
1020: }
1021:
1022: /**
1023: * Initialize this node with given offset. Clear all key, value,
1024: * and child values.
1025: *
1026: * @param inp_offset the new offset of the node data
1027: * this node represents
1028: */
1029: void init(int inp_offset) {
1030: offset = inp_offset;
1031:
1032: // initialize all the node members
1033: numKeys = 0;
1034: child[0] = 0;
1035: for (int i = 0; i < NODE_ELEMENTS + 1; i++) {
1036: key[i] = 0;
1037: value[i] = 0;
1038: child[i + 1] = 0;
1039: }
1040: }
1041:
1042: /**
1043: * Adds the key, value, child values to the node at the given index.
1044: *
1045: * @param newKey the new key to add
1046: * @param newValue the new value to add
1047: * @param rightChild the new right child of the new key
1048: * @param index the index at which to add the key, value, child values
1049: */
1050: void addKey(int newKey, int newValue, int rightChild, int index) {
1051: for (int i = numKeys; i > index; i--) {
1052: key[i] = key[i - 1];
1053: value[i] = value[i - 1];
1054: child[i + 1] = child[i];
1055: }
1056:
1057: // add new triplet
1058: key[index] = newKey;
1059: value[index] = newValue;
1060: child[index + 1] = rightChild;
1061:
1062: numKeys++;
1063: }
1064:
1065: /**
1066: * Deletes the key, value, right child values from the node
1067: * at the given index.
1068: *
1069: * @param index the index at which to remove the key, value,
1070: * child values
1071: */
1072: void deleteKey(int index) {
1073: for (int i = index; i < numKeys; i++) {
1074: key[i] = key[i + 1];
1075: value[i] = value[i + 1];
1076: child[i + 1] = child[i + 2];
1077: }
1078:
1079: numKeys--;
1080: }
1081:
1082: /**
1083: * Loads the node data at the given offset in the tree file into
1084: * this node object.
1085: *
1086: * @param inp_offset the offset to the node data to load
1087: *
1088: * @exception IOException if there is an error accessing the tree file
1089: */
1090: void load(int inp_offset) throws IOException {
1091: offset = inp_offset;
1092: numKeys = 0;
1093:
1094: // seek to the start of the node
1095: treeFile.seek(inp_offset);
1096:
1097: byte[] buffer = new byte[12];
1098:
1099: // read the first child
1100: if (treeFile.read(buffer, 0, 4) != 4) {
1101: throw new IOException("Could not read first child "
1102: + inp_offset);
1103: }
1104: child[0] = RecordStoreUtil.getInt(buffer, 0);
1105:
1106: // read the key, value, child triplets
1107: int i = 0;
1108: for (; i < NODE_ELEMENTS; i++) {
1109: if (treeFile.read(buffer) != buffer.length) {
1110: throw new IOException(
1111: "Could not read entire buffer "
1112: + inp_offset);
1113: }
1114:
1115: int tempKey = RecordStoreUtil.getInt(buffer, 0);
1116: if (tempKey <= 0) {
1117: break;
1118: }
1119:
1120: numKeys++;
1121: key[i] = tempKey;
1122: value[i] = RecordStoreUtil.getInt(buffer, 4);
1123: child[i + 1] = RecordStoreUtil.getInt(buffer, 8);
1124: }
1125:
1126: // clear the rest of the entries
1127: for (; i < NODE_ELEMENTS + 1; i++) {
1128: key[i] = 0;
1129: value[i] = 0;
1130: child[i + 1] = 0;
1131: }
1132: }
1133:
1134: /**
1135: * Saves the node data in this node object to the given offset in the
1136: * tree file.
1137: *
1138: * @exception IOException if there is an error accessing the tree file
1139: */
1140: void save() throws IOException {
1141: // seek to the start of the node
1142: treeFile.seek(offset);
1143:
1144: byte[] buffer = new byte[12];
1145:
1146: // write the left most child
1147: RecordStoreUtil.putInt(child[0], buffer, 0);
1148: treeFile.write(buffer, 0, 4);
1149:
1150: // write the key, value, child triplets
1151: for (int i = 0; i < NODE_ELEMENTS; i++) {
1152: RecordStoreUtil.putInt(key[i], buffer, 0);
1153: RecordStoreUtil.putInt(value[i], buffer, 4);
1154: RecordStoreUtil.putInt(child[i + 1], buffer, 8);
1155: treeFile.write(buffer);
1156: }
1157:
1158: treeFile.commitWrite();
1159: }
1160:
1161: /**
1162: * Returns a string representation of this node object
1163: *
1164: * @return the string representation of the node
1165: */
1166: public String toString() {
1167: String temp = "offset=" + offset + "\n" + child[0] + "\n";
1168: for (int i = 0; i < NODE_ELEMENTS + 1; i++) {
1169: temp += i + " " + key[i] + " " + value[i] + " "
1170: + child[i + 1] + "\n";
1171: }
1172:
1173: return temp;
1174: }
1175: }
1176: }
|