Source Code Cross Referenced for RecordStoreIndex.java in  » 6.0-JDK-Modules » j2me » com » sun » midp » rms » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » 6.0 JDK Modules » j2me » com.sun.midp.rms 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


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:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.