Source Code Cross Referenced for BTree.java in  » EJB-Server-resin-3.1.5 » resin » com » caucho » db » index » 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 » EJB Server resin 3.1.5 » resin » com.caucho.db.index 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


0001:        /*
0002:         * Copyright (c) 1998-2008 Caucho Technology -- all rights reserved
0003:         *
0004:         * This file is part of Resin(R) Open Source
0005:         *
0006:         * Each copy or derived work must preserve the copyright notice and this
0007:         * notice unmodified.
0008:         *
0009:         * Resin Open Source is free software; you can redistribute it and/or modify
0010:         * it under the terms of the GNU General Public License as published by
0011:         * the Free Software Foundation; either version 2 of the License, or
0012:         * (at your option) any later version.
0013:         *
0014:         * Resin Open Source is distributed in the hope that it will be useful,
0015:         * but WITHOUT ANY WARRANTY; without even the implied warranty of
0016:         * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE, or any warranty
0017:         * of NON-INFRINGEMENT.  See the GNU General Public License for more
0018:         * details.
0019:         *
0020:         * You should have received a copy of the GNU General Public License
0021:         * along with Resin Open Source; if not, write to the
0022:         *
0023:         *   Free Software Foundation, Inc.
0024:         *   59 Temple Place, Suite 330
0025:         *   Boston, MA 02111-1307  USA
0026:         *
0027:         * @author Scott Ferguson
0028:         */
0029:
0030:        package com.caucho.db.index;
0031:
0032:        import com.caucho.db.Database;
0033:        import com.caucho.db.store.Block;
0034:        import com.caucho.db.store.BlockManager;
0035:        import com.caucho.db.store.Lock;
0036:        import com.caucho.db.store.Store;
0037:        import com.caucho.db.store.Transaction;
0038:        import com.caucho.log.Log;
0039:        import com.caucho.sql.SQLExceptionWrapper;
0040:        import com.caucho.util.L10N;
0041:        import com.caucho.vfs.Path;
0042:
0043:        import java.io.IOException;
0044:        import java.sql.SQLException;
0045:        import java.util.ArrayList;
0046:        import java.util.logging.Level;
0047:        import java.util.logging.Logger;
0048:
0049:        /**
0050:         * Structure of the table:
0051:         *
0052:         * <pre>
0053:         * b4 - flags
0054:         * b4 - length
0055:         * b8 - parent
0056:         * b8 - next
0057:         * tuples*
0058:         * </pre>
0059:         * 
0060:         * Structure of a tuple:
0061:         *
0062:         * <pre>
0063:         * b8  - ptr to the actual data
0064:         * key - the tuple's key
0065:         * </pre>
0066:         */
0067:        public final class BTree {
0068:            private final static L10N L = new L10N(BTree.class);
0069:            private final static Logger log = Log.open(BTree.class);
0070:
0071:            public final static long FAIL = 0;
0072:            private final static int BLOCK_SIZE = Store.BLOCK_SIZE;
0073:            private final static int PTR_SIZE = 8;
0074:
0075:            private final static int FLAGS_OFFSET = 0;
0076:            private final static int LENGTH_OFFSET = FLAGS_OFFSET + 4;
0077:            private final static int PARENT_OFFSET = LENGTH_OFFSET + 4;
0078:            private final static int NEXT_OFFSET = PARENT_OFFSET + PTR_SIZE;
0079:            private final static int HEADER_SIZE = NEXT_OFFSET + PTR_SIZE;
0080:
0081:            private final static int LEAF_FLAG = 1;
0082:
0083:            private BlockManager _blockManager;
0084:
0085:            private final Lock _lock;
0086:            private Store _store;
0087:
0088:            private long _rootBlockId;
0089:            private Block _rootBlock;
0090:
0091:            private int _keySize;
0092:            private int _tupleSize;
0093:            private int _n;
0094:            private int _minN;
0095:
0096:            private KeyCompare _keyCompare;
0097:
0098:            private int _blockCount;
0099:
0100:            private volatile boolean _isStarted;
0101:
0102:            /**
0103:             * Creates a new BTree with the given backing.
0104:             *
0105:             * @param store the underlying store containing the btree.
0106:             */
0107:            public BTree(Store store, long rootBlockId, int keySize,
0108:                    KeyCompare keyCompare) throws IOException {
0109:                if (keyCompare == null)
0110:                    throw new NullPointerException();
0111:
0112:                _store = store;
0113:                _blockManager = _store.getBlockManager();
0114:
0115:                _rootBlockId = rootBlockId;
0116:                _rootBlock = store.readBlock(rootBlockId);
0117:
0118:                _lock = new Lock("index:" + store.getName());
0119:
0120:                if (BLOCK_SIZE < keySize + HEADER_SIZE)
0121:                    throw new IOException(L.l(
0122:                            "BTree key size `{0}' is too large.", keySize));
0123:
0124:                _keySize = keySize;
0125:
0126:                _tupleSize = keySize + PTR_SIZE;
0127:
0128:                _n = (BLOCK_SIZE - HEADER_SIZE) / _tupleSize;
0129:                _minN = (_n + 1) / 2;
0130:                if (_minN < 0)
0131:                    _minN = 1;
0132:
0133:                _keyCompare = keyCompare;
0134:            }
0135:
0136:            /**
0137:             * Returns the index root.
0138:             */
0139:            public long getIndexRoot() {
0140:                return _rootBlockId;
0141:            }
0142:
0143:            /**
0144:             * Creates and initializes the btree.
0145:             */
0146:            public void create() throws IOException {
0147:            }
0148:
0149:            public long lookup(byte[] keyBuffer, int keyOffset, int keyLength,
0150:                    Transaction xa) throws IOException, SQLException {
0151:                return lookup(keyBuffer, keyOffset, keyLength, xa, _rootBlockId);
0152:            }
0153:
0154:            private long lookup(byte[] keyBuffer, int keyOffset, int keyLength,
0155:                    Transaction xa, long blockId) throws IOException,
0156:                    SQLException {
0157:                Block block;
0158:
0159:                if (blockId == _rootBlockId) {
0160:                    block = _rootBlock;
0161:                    block.allocate();
0162:                } else
0163:                    block = _store.readBlock(blockId);
0164:
0165:                try {
0166:                    Lock blockLock = block.getLock();
0167:                    xa.lockRead(blockLock);
0168:
0169:                    try {
0170:                        byte[] buffer = block.getBuffer();
0171:
0172:                        boolean isLeaf = isLeaf(buffer);
0173:
0174:                        long value = lookupTuple(blockId, buffer, keyBuffer,
0175:                                keyOffset, keyLength, isLeaf);
0176:
0177:                        if (isLeaf || value == FAIL)
0178:                            return value;
0179:                        else
0180:                            return lookup(keyBuffer, keyOffset, keyLength, xa,
0181:                                    value);
0182:                    } finally {
0183:                        xa.unlockRead(blockLock);
0184:                    }
0185:                } finally {
0186:                    block.free();
0187:                }
0188:            }
0189:
0190:            /**
0191:             * Inserts the new value for the given key.
0192:             *
0193:             * @return false if the block needs to be split
0194:             */
0195:            public void insert(byte[] keyBuffer, int keyOffset, int keyLength,
0196:                    long value, Transaction xa, boolean isOverride)
0197:                    throws SQLException {
0198:                try {
0199:                    while (!insert(keyBuffer, keyOffset, keyLength, value, xa,
0200:                            isOverride, _rootBlockId)) {
0201:                        splitRoot(_rootBlockId, xa);
0202:                    }
0203:                } catch (IOException e) {
0204:                    log.log(Level.FINE, e.toString(), e);
0205:
0206:                    throw new SQLExceptionWrapper(e.toString(), e);
0207:                }
0208:            }
0209:
0210:            /**
0211:             * Inserts the new value for the given key.
0212:             *
0213:             * @return false if the block needs to be split
0214:             */
0215:            private boolean insert(byte[] keyBuffer, int keyOffset,
0216:                    int keyLength, long value, Transaction xa,
0217:                    boolean isOverride, long blockId) throws IOException,
0218:                    SQLException {
0219:                Block block;
0220:
0221:                if (blockId == _rootBlockId) {
0222:                    block = _rootBlock;
0223:                    block.allocate();
0224:                } else
0225:                    block = _store.readBlock(blockId);
0226:
0227:                try {
0228:                    Lock blockLock = block.getLock();
0229:                    xa.lockRead(blockLock);
0230:
0231:                    try {
0232:                        byte[] buffer = block.getBuffer();
0233:
0234:                        int length = getLength(buffer);
0235:
0236:                        if (length == _n) {
0237:                            // return false if the block needs to be split
0238:                            return false;
0239:                        }
0240:
0241:                        if (isLeaf(buffer)) {
0242:                            insertValue(keyBuffer, keyOffset, keyLength, value,
0243:                                    xa, isOverride, block);
0244:
0245:                            return true;
0246:                        }
0247:
0248:                        long childBlockId = lookupTuple(blockId, buffer,
0249:                                keyBuffer, keyOffset, keyLength, false);
0250:
0251:                        while (!insert(keyBuffer, keyOffset, keyLength, value,
0252:                                xa, isOverride, childBlockId)) {
0253:                            split(block, childBlockId, xa);
0254:
0255:                            childBlockId = lookupTuple(blockId, buffer,
0256:                                    keyBuffer, keyOffset, keyLength, false);
0257:                        }
0258:
0259:                        return true;
0260:                    } finally {
0261:                        xa.unlockRead(blockLock);
0262:                    }
0263:                } finally {
0264:                    block.free();
0265:                }
0266:            }
0267:
0268:            /**
0269:             * Inserts into the next block given the current block and the given key.
0270:             */
0271:            private void insertValue(byte[] keyBuffer, int keyOffset,
0272:                    int keyLength, long value, Transaction xa,
0273:                    boolean isOverride, Block block) throws IOException,
0274:                    SQLException {
0275:                byte[] buffer = block.getBuffer();
0276:
0277:                Lock blockLock = block.getLock();
0278:                xa.lockWrite(blockLock);
0279:                try {
0280:                    block.setFlushDirtyOnCommit(false);
0281:                    block.setDirty(0, Store.BLOCK_SIZE);
0282:
0283:                    insertLeafBlock(block.getBlockId(), buffer, keyBuffer,
0284:                            keyOffset, keyLength, value, isOverride);
0285:                } finally {
0286:                    xa.unlockWrite(blockLock);
0287:                }
0288:            }
0289:
0290:            /**
0291:             * Inserts into the next block given the current block and the given key.
0292:             */
0293:            private long insertLeafBlock(long blockId, byte[] buffer,
0294:                    byte[] keyBuffer, int keyOffset, int keyLength, long value,
0295:                    boolean isOverride) throws IOException, SQLException {
0296:                int offset = HEADER_SIZE;
0297:                int tupleSize = _tupleSize;
0298:                int length = getLength(buffer);
0299:
0300:                for (int i = 0; i < length; i++) {
0301:                    int cmp = _keyCompare.compare(keyBuffer, keyOffset, buffer,
0302:                            offset + PTR_SIZE, keyLength);
0303:
0304:                    if (0 < cmp) {
0305:                        offset += tupleSize;
0306:                        continue;
0307:                    } else if (cmp == 0) {
0308:                        if (!isOverride) {
0309:                            long oldValue = getPointer(buffer, offset);
0310:
0311:                            if (value != oldValue)
0312:                                throw new SQLException(
0313:                                        L
0314:                                                .l(
0315:                                                        "'{0}' insert of key '{1}' fails index uniqueness.",
0316:                                                        _store,
0317:                                                        _keyCompare.toString(
0318:                                                                keyBuffer,
0319:                                                                keyOffset,
0320:                                                                keyLength)));
0321:                        }
0322:
0323:                        setPointer(buffer, offset, value);
0324:                        //writeBlock(blockIndex, block);
0325:
0326:                        return 0;
0327:                    } else if (length < _n) {
0328:                        return addKey(blockId, buffer, offset, i, length,
0329:                                keyBuffer, keyOffset, keyLength, value);
0330:                    } else {
0331:                        throw new IllegalStateException("ran out of key space");
0332:                    }
0333:                }
0334:
0335:                if (length < _n) {
0336:                    return addKey(blockId, buffer, offset, length, length,
0337:                            keyBuffer, keyOffset, keyLength, value);
0338:                }
0339:
0340:                throw new IllegalStateException();
0341:
0342:                // return split(blockIndex, block);
0343:            }
0344:
0345:            private long addKey(long blockId, byte[] buffer, int offset,
0346:                    int index, int length, byte[] keyBuffer, int keyOffset,
0347:                    int keyLength, long value) throws IOException {
0348:                int tupleSize = _tupleSize;
0349:
0350:                if (index < length) {
0351:                    if (offset + tupleSize < HEADER_SIZE)
0352:                        throw new IllegalStateException();
0353:
0354:                    System.arraycopy(buffer, offset, buffer,
0355:                            offset + tupleSize, (length - index) * tupleSize);
0356:                }
0357:
0358:                setPointer(buffer, offset, value);
0359:                setLength(buffer, length + 1);
0360:
0361:                if (log.isLoggable(Level.FINEST))
0362:                    log.finest("btree insert at " + debugId(blockId) + ":"
0363:                            + offset + " value:" + debugId(value));
0364:
0365:                if (offset + PTR_SIZE < HEADER_SIZE)
0366:                    throw new IllegalStateException();
0367:
0368:                System.arraycopy(keyBuffer, keyOffset, buffer, offset
0369:                        + PTR_SIZE, keyLength);
0370:
0371:                for (int j = PTR_SIZE + keyLength; j < tupleSize; j++)
0372:                    buffer[offset + j] = 0;
0373:
0374:                return -value;
0375:            }
0376:
0377:            /**
0378:             * The length in lBuf is assumed to be the length of the buffer.
0379:             */
0380:            private void split(Block parent, long blockId, Transaction xa)
0381:                    throws IOException, SQLException {
0382:                Lock parentLock = parent.getLock();
0383:                xa.lockWrite(parentLock);
0384:
0385:                try {
0386:                    Block block = _store.readBlock(blockId);
0387:
0388:                    try {
0389:                        Lock blockLock = block.getLock();
0390:                        xa.lockReadAndWrite(blockLock);
0391:
0392:                        try {
0393:                            split(parent, block, xa);
0394:                        } finally {
0395:                            xa.unlockReadAndWrite(blockLock);
0396:                        }
0397:                    } finally {
0398:                        block.free();
0399:                    }
0400:                } finally {
0401:                    xa.unlockWrite(parentLock);
0402:                }
0403:            }
0404:
0405:            /**
0406:             * The length in lBuf is assumed to be the length of the buffer.
0407:             */
0408:            private void split(Block parentBlock, Block block, Transaction xa)
0409:                    throws IOException, SQLException {
0410:                long parentId = parentBlock.getBlockId();
0411:                long blockId = block.getBlockId();
0412:
0413:                log.finer("btree splitting " + debugId(blockId));
0414:
0415:                block.setFlushDirtyOnCommit(false);
0416:                block.setDirty(0, Store.BLOCK_SIZE);
0417:
0418:                byte[] buffer = block.getBuffer();
0419:                int length = getLength(buffer);
0420:
0421:                // Check length to avoid possible timing issue, since we release the
0422:                // read lock for the block between the initial check in insert() and
0423:                // getting it back in split()
0424:                if (length < _n / 2)
0425:                    return;
0426:
0427:                if (length < 2)
0428:                    throw new IllegalStateException(L.l(
0429:                            "illegal length '{0}' for block {1}", length,
0430:                            debugId(blockId)));
0431:
0432:                //System.out.println("INDEX SPLIT: " + debugId(blockId) + " " + length + " " + block + " " + buffer);
0433:
0434:                Block leftBlock = null;
0435:
0436:                try {
0437:                    parentBlock.setFlushDirtyOnCommit(false);
0438:                    parentBlock.setDirty(0, Store.BLOCK_SIZE);
0439:
0440:                    byte[] parentBuffer = parentBlock.getBuffer();
0441:                    int parentLength = getLength(parentBuffer);
0442:
0443:                    leftBlock = _store.allocateIndexBlock();
0444:                    leftBlock.setFlushDirtyOnCommit(false);
0445:                    leftBlock.setDirty(0, Store.BLOCK_SIZE);
0446:
0447:                    byte[] leftBuffer = leftBlock.getBuffer();
0448:                    long leftBlockId = leftBlock.getBlockId();
0449:
0450:                    int pivot = length / 2;
0451:
0452:                    int pivotSize = pivot * _tupleSize;
0453:                    int pivotEnd = HEADER_SIZE + pivotSize;
0454:
0455:                    System.arraycopy(buffer, HEADER_SIZE, leftBuffer,
0456:                            HEADER_SIZE, pivotSize);
0457:
0458:                    setInt(leftBuffer, FLAGS_OFFSET, getInt(buffer,
0459:                            FLAGS_OFFSET));
0460:                    setLength(leftBuffer, pivot);
0461:                    // XXX: NEXT_OFFSET needs to work with getRightIndex
0462:                    setPointer(leftBuffer, NEXT_OFFSET, 0);
0463:                    setPointer(leftBuffer, PARENT_OFFSET, parentId);
0464:
0465:                    System.arraycopy(buffer, pivotEnd, buffer, HEADER_SIZE,
0466:                            length * _tupleSize - pivotEnd);
0467:
0468:                    setLength(buffer, length - pivot);
0469:
0470:                    insertLeafBlock(parentId, parentBuffer, leftBuffer,
0471:                            pivotEnd - _tupleSize + PTR_SIZE, _keySize,
0472:                            leftBlockId, true);
0473:                } finally {
0474:                    if (leftBlock != null)
0475:                        leftBlock.free();
0476:                }
0477:            }
0478:
0479:            /**
0480:             * The length in lBuf is assumed to be the length of the buffer.
0481:             */
0482:            private void splitRoot(long rootBlockId, Transaction xa)
0483:                    throws IOException, SQLException {
0484:                Block rootBlock = _rootBlock; // store.readBlock(rootBlockId);
0485:                rootBlock.allocate();
0486:
0487:                try {
0488:                    Lock rootLock = rootBlock.getLock();
0489:                    xa.lockReadAndWrite(rootLock);
0490:
0491:                    try {
0492:                        splitRoot(rootBlock, xa);
0493:                    } finally {
0494:                        xa.unlockReadAndWrite(rootLock);
0495:                    }
0496:                } finally {
0497:                    rootBlock.free();
0498:                }
0499:            }
0500:
0501:            /**
0502:             * Splits the current leaf into two.  Half of the entries go to the
0503:             * left leaf and half go to the right leaf.
0504:             */
0505:            private void splitRoot(Block parentBlock, Transaction xa)
0506:                    throws IOException {
0507:                long parentId = parentBlock.getBlockId();
0508:
0509:                //System.out.println("INDEX SPLIT ROOT: " + (parentId / BLOCK_SIZE));
0510:                log.finer("btree splitting root " + (parentId / BLOCK_SIZE));
0511:
0512:                Block leftBlock = null;
0513:                Block rightBlock = null;
0514:
0515:                try {
0516:                    parentBlock.setFlushDirtyOnCommit(false);
0517:                    parentBlock.setDirty(0, Store.BLOCK_SIZE);
0518:
0519:                    byte[] parentBuffer = parentBlock.getBuffer();
0520:
0521:                    int parentFlags = getInt(parentBuffer, FLAGS_OFFSET);
0522:
0523:                    leftBlock = _store.allocateIndexBlock();
0524:                    leftBlock.setFlushDirtyOnCommit(false);
0525:                    leftBlock.setDirty(0, Store.BLOCK_SIZE);
0526:
0527:                    long leftBlockId = leftBlock.getBlockId();
0528:
0529:                    rightBlock = _store.allocateIndexBlock();
0530:                    rightBlock.setFlushDirtyOnCommit(false);
0531:                    rightBlock.setDirty(0, Store.BLOCK_SIZE);
0532:
0533:                    long rightBlockId = rightBlock.getBlockId();
0534:
0535:                    int length = getLength(parentBuffer);
0536:
0537:                    int pivot = (length - 1) / 2;
0538:
0539:                    if (length <= 2 || _n < length || pivot < 1
0540:                            || length <= pivot)
0541:                        throw new IllegalStateException(length
0542:                                + " is an illegal length, or pivot " + pivot
0543:                                + " is bad, with n=" + _n);
0544:
0545:                    int pivotOffset = HEADER_SIZE + pivot * _tupleSize;
0546:                    long pivotValue = getPointer(parentBuffer, pivotOffset);
0547:
0548:                    byte[] leftBuffer = leftBlock.getBuffer();
0549:
0550:                    System
0551:                            .arraycopy(parentBuffer, HEADER_SIZE, leftBuffer,
0552:                                    HEADER_SIZE, pivotOffset + _tupleSize
0553:                                            - HEADER_SIZE);
0554:                    setInt(leftBuffer, FLAGS_OFFSET, parentFlags);
0555:                    setLength(leftBuffer, pivot + 1);
0556:                    setPointer(leftBuffer, PARENT_OFFSET, parentId);
0557:                    setPointer(leftBuffer, NEXT_OFFSET, rightBlockId);
0558:
0559:                    byte[] rightBuffer = rightBlock.getBuffer();
0560:
0561:                    if (length - pivot - 1 < 0)
0562:                        throw new IllegalStateException("illegal length "
0563:                                + pivot + " " + length);
0564:
0565:                    System.arraycopy(parentBuffer, pivotOffset + _tupleSize,
0566:                            rightBuffer, HEADER_SIZE, (length - pivot - 1)
0567:                                    * _tupleSize);
0568:
0569:                    setInt(rightBuffer, FLAGS_OFFSET, parentFlags);
0570:                    setLength(rightBuffer, length - pivot - 1);
0571:                    setPointer(rightBuffer, PARENT_OFFSET, parentId);
0572:                    setPointer(rightBuffer, NEXT_OFFSET, getPointer(
0573:                            parentBuffer, NEXT_OFFSET));
0574:
0575:                    System.arraycopy(parentBuffer, pivotOffset, parentBuffer,
0576:                            HEADER_SIZE, _tupleSize);
0577:                    setPointer(parentBuffer, HEADER_SIZE, leftBlockId);
0578:
0579:                    setInt(parentBuffer, FLAGS_OFFSET, LEAF_FLAG);
0580:                    setLength(parentBuffer, 1);
0581:                    setPointer(parentBuffer, NEXT_OFFSET, rightBlockId);
0582:                } finally {
0583:                    if (leftBlock != null)
0584:                        leftBlock.free();
0585:
0586:                    if (rightBlock != null)
0587:                        rightBlock.free();
0588:                }
0589:            }
0590:
0591:            public void remove(byte[] keyBuffer, int keyOffset, int keyLength,
0592:                    Transaction xa) throws SQLException {
0593:                try {
0594:                    Block rootBlock = _rootBlock; // _store.readBlock(_rootBlockId);
0595:                    rootBlock.allocate();
0596:
0597:                    try {
0598:                        Lock rootLock = rootBlock.getLock();
0599:                        xa.lockRead(rootLock);
0600:
0601:                        try {
0602:                            remove(rootBlock, keyBuffer, keyOffset, keyLength,
0603:                                    xa);
0604:                        } finally {
0605:                            xa.unlockRead(rootLock);
0606:                        }
0607:                    } finally {
0608:                        rootBlock.free();
0609:                    }
0610:                } catch (IOException e) {
0611:                    throw new SQLExceptionWrapper(e.toString(), e);
0612:                }
0613:            }
0614:
0615:            /**
0616:             * Recursively remove a key from the index.
0617:             *
0618:             * block is read-locked by the parent.
0619:             */
0620:            private boolean remove(Block block, byte[] keyBuffer,
0621:                    int keyOffset, int keyLength, Transaction xa)
0622:                    throws IOException, SQLException {
0623:                byte[] buffer = block.getBuffer();
0624:                long blockId = block.getBlockId();
0625:
0626:                boolean isLeaf = isLeaf(buffer);
0627:
0628:                if (isLeaf) {
0629:                    Lock blockLock = block.getLock();
0630:
0631:                    xa.lockWrite(blockLock);
0632:
0633:                    try {
0634:                        block.setFlushDirtyOnCommit(false);
0635:                        block.setDirty(0, Store.BLOCK_SIZE);
0636:
0637:                        removeLeafEntry(blockId, buffer, keyBuffer, keyOffset,
0638:                                keyLength);
0639:                    } finally {
0640:                        xa.unlockWrite(blockLock);
0641:                    }
0642:                } else {
0643:                    long childId;
0644:
0645:                    childId = lookupTuple(blockId, buffer, keyBuffer,
0646:                            keyOffset, keyLength, isLeaf);
0647:
0648:                    if (childId == FAIL)
0649:                        return true;
0650:
0651:                    Block childBlock = _store.readBlock(childId);
0652:                    try {
0653:                        boolean isJoin = false;
0654:
0655:                        Lock childLock = childBlock.getLock();
0656:                        xa.lockRead(childLock);
0657:
0658:                        try {
0659:                            isJoin = !remove(childBlock, keyBuffer, keyOffset,
0660:                                    keyLength, xa);
0661:                        } finally {
0662:                            xa.unlockRead(childLock);
0663:                        }
0664:
0665:                        if (isJoin) {
0666:                            if (joinBlocks(block, childBlock, xa)) {
0667:                                xa.deallocateBlock(childBlock);
0668:                            }
0669:                        }
0670:                    } finally {
0671:                        childBlock.free();
0672:                    }
0673:                }
0674:
0675:                return _minN <= getLength(buffer);
0676:            }
0677:
0678:            /**
0679:             * Performs any block-merging cleanup after the delete.
0680:             *
0681:             * parent is read-locked by the parent.
0682:             * block is not locked.
0683:             *
0684:             * @return true if the block should be deleted/freed
0685:             */
0686:            private boolean joinBlocks(Block parent, Block block, Transaction xa)
0687:                    throws IOException, SQLException {
0688:                byte[] parentBuffer = parent.getBuffer();
0689:                int parentLength = getLength(parentBuffer);
0690:
0691:                long blockId = block.getBlockId();
0692:                byte[] buffer = block.getBuffer();
0693:
0694:                //System.out.println("INDEX JOIN: " + debugId(blockId));
0695:
0696:                Lock parentLock = parent.getLock();
0697:                xa.lockWrite(parentLock);
0698:                try {
0699:                    long leftBlockId = getLeftBlockId(parent, blockId);
0700:                    long rightBlockId = getRightBlockId(parent, blockId);
0701:
0702:                    // try to shift from left and right first
0703:                    if (leftBlockId > 0) {
0704:                        Block leftBlock = _store.readBlock(leftBlockId);
0705:
0706:                        try {
0707:                            byte[] leftBuffer = leftBlock.getBuffer();
0708:
0709:                            Lock leftLock = leftBlock.getLock();
0710:                            xa.lockReadAndWrite(leftLock);
0711:
0712:                            try {
0713:                                int leftLength = getLength(leftBuffer);
0714:
0715:                                Lock blockLock = block.getLock();
0716:                                xa.lockReadAndWrite(blockLock);
0717:
0718:                                try {
0719:                                    if (_minN < leftLength
0720:                                            && isLeaf(buffer) == isLeaf(leftBuffer)) {
0721:                                        parent.setFlushDirtyOnCommit(false);
0722:                                        parent.setDirty(0, Store.BLOCK_SIZE);
0723:
0724:                                        leftBlock.setFlushDirtyOnCommit(false);
0725:                                        leftBlock.setDirty(0, Store.BLOCK_SIZE);
0726:
0727:                                        //System.out.println("MOVE_FROM_LEFT: " + debugId(blockId) + " from " + debugId(leftBlockId));
0728:                                        moveFromLeft(parentBuffer, leftBuffer,
0729:                                                buffer, blockId);
0730:
0731:                                        return false;
0732:                                    }
0733:                                } finally {
0734:                                    xa.unlockReadAndWrite(blockLock);
0735:                                }
0736:                            } finally {
0737:                                xa.unlockReadAndWrite(leftLock);
0738:                            }
0739:                        } finally {
0740:                            leftBlock.free();
0741:                        }
0742:                    }
0743:
0744:                    if (rightBlockId > 0) {
0745:                        Block rightBlock = _store.readBlock(rightBlockId);
0746:
0747:                        try {
0748:                            byte[] rightBuffer = rightBlock.getBuffer();
0749:
0750:                            Lock blockLock = block.getLock();
0751:                            xa.lockReadAndWrite(blockLock);
0752:
0753:                            try {
0754:                                Lock rightLock = rightBlock.getLock();
0755:                                xa.lockReadAndWrite(rightLock);
0756:
0757:                                try {
0758:                                    int rightLength = getLength(rightBuffer);
0759:
0760:                                    if (_minN < rightLength
0761:                                            && isLeaf(buffer) == isLeaf(rightBuffer)) {
0762:                                        parent.setFlushDirtyOnCommit(false);
0763:                                        parent.setDirty(0, Store.BLOCK_SIZE);
0764:
0765:                                        rightBlock.setFlushDirtyOnCommit(false);
0766:                                        rightBlock
0767:                                                .setDirty(0, Store.BLOCK_SIZE);
0768:
0769:                                        //System.out.println("MOVE_FROM_RIGHT: " + debugId(blockId) + " from " + debugId(rightBlockId));
0770:
0771:                                        moveFromRight(parentBuffer, buffer,
0772:                                                rightBuffer, blockId);
0773:
0774:                                        return false;
0775:                                    }
0776:                                } finally {
0777:                                    xa.unlockReadAndWrite(rightLock);
0778:                                }
0779:                            } finally {
0780:                                xa.unlockReadAndWrite(blockLock);
0781:                            }
0782:                        } finally {
0783:                            rightBlock.free();
0784:                        }
0785:                    }
0786:
0787:                    if (parentLength < 2)
0788:                        return false;
0789:
0790:                    if (leftBlockId > 0) {
0791:                        Block leftBlock = _store.readBlock(leftBlockId);
0792:
0793:                        try {
0794:                            byte[] leftBuffer = leftBlock.getBuffer();
0795:
0796:                            Lock leftLock = leftBlock.getLock();
0797:                            xa.lockReadAndWrite(leftLock);
0798:
0799:                            try {
0800:                                int leftLength = getLength(leftBuffer);
0801:
0802:                                Lock blockLock = block.getLock();
0803:                                xa.lockReadAndWrite(blockLock);
0804:
0805:                                try {
0806:                                    int length = getLength(buffer);
0807:
0808:                                    if (isLeaf(leftBuffer) == isLeaf(buffer)
0809:                                            && length + leftLength <= _n) {
0810:                                        parent.setFlushDirtyOnCommit(false);
0811:                                        parent.setDirty(0, Store.BLOCK_SIZE);
0812:
0813:                                        leftBlock.setFlushDirtyOnCommit(false);
0814:                                        leftBlock.setDirty(0, Store.BLOCK_SIZE);
0815:
0816:                                        //System.out.println("MERGE_LEFT: " + debugId(blockId) + " from " + debugId(leftBlockId));
0817:
0818:                                        mergeLeft(parentBuffer, leftBuffer,
0819:                                                buffer, blockId);
0820:
0821:                                        return true;
0822:                                    }
0823:                                } finally {
0824:                                    xa.unlockReadAndWrite(blockLock);
0825:                                }
0826:                            } finally {
0827:                                xa.unlockReadAndWrite(leftLock);
0828:                            }
0829:                        } finally {
0830:                            leftBlock.free();
0831:                        }
0832:                    }
0833:
0834:                    if (rightBlockId > 0) {
0835:                        Block rightBlock = _store.readBlock(rightBlockId);
0836:
0837:                        try {
0838:                            byte[] rightBuffer = rightBlock.getBuffer();
0839:
0840:                            Lock blockLock = block.getLock();
0841:                            xa.lockReadAndWrite(blockLock);
0842:
0843:                            try {
0844:                                Lock rightLock = rightBlock.getLock();
0845:                                xa.lockReadAndWrite(rightLock);
0846:
0847:                                try {
0848:                                    int length = getLength(buffer);
0849:                                    int rightLength = getLength(rightBuffer);
0850:
0851:                                    if (isLeaf(rightBuffer) == isLeaf(buffer)
0852:                                            && length + rightLength <= _n) {
0853:                                        rightBlock.setFlushDirtyOnCommit(false);
0854:                                        rightBlock
0855:                                                .setDirty(0, Store.BLOCK_SIZE);
0856:
0857:                                        parent.setFlushDirtyOnCommit(false);
0858:                                        parent.setDirty(0, Store.BLOCK_SIZE);
0859:
0860:                                        //System.out.println("MERGE_RIGHT: " + debugId(blockId) + " from " + debugId(rightBlockId));
0861:
0862:                                        mergeRight(parentBuffer, buffer,
0863:                                                rightBuffer, blockId);
0864:
0865:                                        return true;
0866:                                    }
0867:                                } finally {
0868:                                    xa.unlockReadAndWrite(rightLock);
0869:                                }
0870:                            } finally {
0871:                                xa.unlockReadAndWrite(blockLock);
0872:                            }
0873:                        } finally {
0874:                            rightBlock.free();
0875:                        }
0876:                    }
0877:
0878:                    return false;
0879:                } finally {
0880:                    xa.unlockWrite(parentLock);
0881:                }
0882:            }
0883:
0884:            /**
0885:             * Returns the index to the left of the current one
0886:             */
0887:            private long getLeftBlockId(Block parent, long blockId) {
0888:                byte[] buffer = parent.getBuffer();
0889:
0890:                int length = getLength(buffer);
0891:
0892:                if (length < 1)
0893:                    throw new IllegalStateException("zero length for "
0894:                            + debugId(parent.getBlockId()));
0895:
0896:                int offset = HEADER_SIZE;
0897:                int tupleSize = _tupleSize;
0898:                int end = offset + length * tupleSize;
0899:
0900:                for (; offset < end; offset += tupleSize) {
0901:                    long pointer = getPointer(buffer, offset);
0902:
0903:                    if (pointer == blockId) {
0904:                        if (HEADER_SIZE < offset) {
0905:                            return getPointer(buffer, offset - tupleSize);
0906:                        } else
0907:                            return -1;
0908:                    }
0909:                }
0910:
0911:                long pointer = getPointer(buffer, NEXT_OFFSET);
0912:
0913:                if (pointer == blockId)
0914:                    return getPointer(buffer, HEADER_SIZE + (length - 1)
0915:                            * tupleSize);
0916:                else
0917:                    throw new IllegalStateException("Can't find "
0918:                            + debugId(blockId) + " in parent "
0919:                            + debugId(parent.getBlockId()));
0920:            }
0921:
0922:            /**
0923:             * Takes the last entry from the left block and moves it to the
0924:             * first entry in the current block.
0925:             *
0926:             * @param parentBuffer the parent block buffer
0927:             * @param leftBuffer the left block buffer
0928:             * @param buffer the block's buffer
0929:             * @param index the index of the block
0930:             */
0931:            private void moveFromLeft(byte[] parentBuffer, byte[] leftBuffer,
0932:                    byte[] buffer, long blockId) {
0933:                int parentLength = getLength(parentBuffer);
0934:
0935:                int tupleSize = _tupleSize;
0936:                int parentOffset = HEADER_SIZE;
0937:                int parentEnd = parentOffset + parentLength * tupleSize;
0938:
0939:                int leftLength = getLength(leftBuffer);
0940:
0941:                int length = getLength(buffer);
0942:
0943:                // pointer in the parent to the left defaults to the tail - 1
0944:                int parentLeftOffset = -1;
0945:
0946:                if (blockId == getPointer(parentBuffer, NEXT_OFFSET)) {
0947:                    // parentLeftOffset = parentOffset - tupleSize;
0948:                    parentLeftOffset = parentEnd - tupleSize;
0949:                } else {
0950:                    for (parentOffset += tupleSize; parentOffset < parentEnd; parentOffset += tupleSize) {
0951:                        long pointer = getPointer(parentBuffer, parentOffset);
0952:
0953:                        if (pointer == blockId) {
0954:                            parentLeftOffset = parentOffset - tupleSize;
0955:                            break;
0956:                        }
0957:                    }
0958:                }
0959:
0960:                if (parentLeftOffset < 0) {
0961:                    log
0962:                            .warning("Can't find parent left in deletion borrow left ");
0963:                    return;
0964:                }
0965:
0966:                // shift the data in the buffer
0967:                System.arraycopy(buffer, HEADER_SIZE, buffer, HEADER_SIZE
0968:                        + tupleSize, length * tupleSize);
0969:
0970:                // copy the last item in the left to the buffer
0971:                System.arraycopy(leftBuffer, HEADER_SIZE + (leftLength - 1)
0972:                        * tupleSize, buffer, HEADER_SIZE, tupleSize);
0973:
0974:                // add the buffer length
0975:                setLength(buffer, length + 1);
0976:
0977:                // subtract from the left length
0978:                leftLength -= 1;
0979:                setLength(leftBuffer, leftLength);
0980:
0981:                // copy the entry from the new left tail to the parent
0982:                System.arraycopy(leftBuffer, HEADER_SIZE + (leftLength - 1)
0983:                        * tupleSize + PTR_SIZE, parentBuffer, parentLeftOffset
0984:                        + PTR_SIZE, tupleSize - PTR_SIZE);
0985:            }
0986:
0987:            /**
0988:             * Returns the index to the left of the current one
0989:             */
0990:            private void mergeLeft(byte[] parentBuffer, byte[] leftBuffer,
0991:                    byte[] buffer, long blockId) {
0992:                int leftLength = getLength(leftBuffer);
0993:                int length = getLength(buffer);
0994:
0995:                int parentLength = getLength(parentBuffer);
0996:
0997:                int tupleSize = _tupleSize;
0998:                int parentOffset = HEADER_SIZE;
0999:                int parentEnd = parentOffset + parentLength * tupleSize;
1000:
1001:                for (parentOffset += tupleSize; parentOffset < parentEnd; parentOffset += tupleSize) {
1002:                    long pointer = getPointer(parentBuffer, parentOffset);
1003:
1004:                    if (pointer == blockId) {
1005:                        int leftOffset = HEADER_SIZE + leftLength * tupleSize;
1006:
1007:                        // copy the pointer from the left pointer
1008:                        setPointer(parentBuffer, parentOffset, getPointer(
1009:                                parentBuffer, parentOffset - tupleSize));
1010:
1011:                        if (parentOffset - tupleSize < HEADER_SIZE)
1012:                            throw new IllegalStateException();
1013:
1014:                        // shift the parent
1015:                        System.arraycopy(parentBuffer, parentOffset,
1016:                                parentBuffer, parentOffset - tupleSize,
1017:                                parentEnd - parentOffset);
1018:                        setLength(parentBuffer, parentLength - 1);
1019:
1020:                        // the new left.next value is the buffer's next value
1021:                        setPointer(leftBuffer, NEXT_OFFSET, getPointer(buffer,
1022:                                NEXT_OFFSET));
1023:
1024:                        if (leftOffset < HEADER_SIZE)
1025:                            throw new IllegalStateException();
1026:
1027:                        // append the buffer to the left buffer
1028:                        // XXX: leaf vs non-leaf?
1029:                        System.arraycopy(buffer, HEADER_SIZE, leftBuffer,
1030:                                leftOffset, length * tupleSize);
1031:
1032:                        setLength(leftBuffer, leftLength + length);
1033:
1034:                        return;
1035:                    }
1036:                }
1037:
1038:                long pointer = getPointer(parentBuffer, NEXT_OFFSET);
1039:
1040:                if (pointer != blockId) {
1041:                    log.warning("BTree remove can't find matching block: "
1042:                            + debugId(blockId));
1043:                    return;
1044:                }
1045:
1046:                int leftOffset = HEADER_SIZE + (parentLength - 1) * tupleSize;
1047:
1048:                long leftPointer = getPointer(parentBuffer, leftOffset);
1049:
1050:                setPointer(parentBuffer, NEXT_OFFSET, leftPointer);
1051:                setLength(parentBuffer, parentLength - 1);
1052:
1053:                // XXX: leaf vs non-leaf?
1054:
1055:                // the new left.next value is the buffer's next value
1056:                setPointer(leftBuffer, NEXT_OFFSET, getPointer(buffer,
1057:                        NEXT_OFFSET));
1058:
1059:                // append the buffer to the left buffer
1060:                System.arraycopy(buffer, HEADER_SIZE, leftBuffer, HEADER_SIZE
1061:                        + leftLength * tupleSize, length * tupleSize);
1062:
1063:                setLength(leftBuffer, leftLength + length);
1064:            }
1065:
1066:            /**
1067:             * Returns the index to the right of the current one
1068:             */
1069:            private long getRightBlockId(Block parent, long blockId) {
1070:                byte[] buffer = parent.getBuffer();
1071:
1072:                int length = getLength(buffer);
1073:
1074:                int offset = HEADER_SIZE;
1075:                int tupleSize = _tupleSize;
1076:                int end = offset + length * tupleSize;
1077:
1078:                for (; offset < end; offset += tupleSize) {
1079:                    long pointer = getPointer(buffer, offset);
1080:
1081:                    if (pointer == blockId) {
1082:                        if (offset + tupleSize < end) {
1083:                            return getPointer(buffer, offset + tupleSize);
1084:                        } else
1085:                            return getPointer(buffer, NEXT_OFFSET);
1086:                    }
1087:                }
1088:
1089:                return -1;
1090:            }
1091:
1092:            /**
1093:             * Takes the first entry from the right block and moves it to the
1094:             * last entry in the current block.
1095:             *
1096:             * @param parentBuffer the parent block buffer
1097:             * @param rightBuffer the right block buffer
1098:             * @param buffer the block's buffer
1099:             * @param index the index of the block
1100:             */
1101:            private void moveFromRight(byte[] parentBuffer, byte[] buffer,
1102:                    byte[] rightBuffer, long blockId) {
1103:                int parentLength = getLength(parentBuffer);
1104:
1105:                int tupleSize = _tupleSize;
1106:                int parentOffset = HEADER_SIZE;
1107:                int parentEnd = parentOffset + parentLength * tupleSize;
1108:
1109:                int rightLength = getLength(rightBuffer);
1110:
1111:                int length = getLength(buffer);
1112:
1113:                for (; parentOffset < parentEnd; parentOffset += tupleSize) {
1114:                    long pointer = getPointer(parentBuffer, parentOffset);
1115:
1116:                    if (pointer == blockId)
1117:                        break;
1118:                }
1119:
1120:                if (parentEnd <= parentOffset) {
1121:                    log.warning("Can't find buffer in deletion borrow right ");
1122:                    return;
1123:                }
1124:
1125:                // copy the first item in the right to the buffer
1126:                System.arraycopy(rightBuffer, HEADER_SIZE, buffer, HEADER_SIZE
1127:                        + length * tupleSize, tupleSize);
1128:
1129:                // shift the data in the right buffer
1130:                System
1131:                        .arraycopy(rightBuffer, HEADER_SIZE + tupleSize,
1132:                                rightBuffer, HEADER_SIZE, (rightLength - 1)
1133:                                        * tupleSize);
1134:
1135:                // add the buffer length
1136:                setLength(buffer, length + 1);
1137:
1138:                // subtract from the right length
1139:                setLength(rightBuffer, rightLength - 1);
1140:
1141:                // copy the entry from the new buffer tail to the parent
1142:                System.arraycopy(buffer, HEADER_SIZE + length * tupleSize
1143:                        + PTR_SIZE, parentBuffer, parentOffset + PTR_SIZE,
1144:                        tupleSize - PTR_SIZE);
1145:            }
1146:
1147:            /**
1148:             * Merges the buffer with the right-most one.
1149:             */
1150:            private void mergeRight(byte[] parentBuffer, byte[] buffer,
1151:                    byte[] rightBuffer, long blockId) {
1152:                int parentLength = getLength(parentBuffer);
1153:
1154:                int tupleSize = _tupleSize;
1155:                int parentOffset = HEADER_SIZE;
1156:                int parentEnd = parentOffset + parentLength * tupleSize;
1157:
1158:                int rightLength = getLength(rightBuffer);
1159:
1160:                int length = getLength(buffer);
1161:
1162:                for (; parentOffset < parentEnd; parentOffset += tupleSize) {
1163:                    long pointer = getPointer(parentBuffer, parentOffset);
1164:
1165:                    if (pointer == blockId) {
1166:                        // add space in the right buffer
1167:                        System.arraycopy(rightBuffer, HEADER_SIZE, rightBuffer,
1168:                                HEADER_SIZE + length * tupleSize, rightLength
1169:                                        * tupleSize);
1170:
1171:                        // add the buffer to the right buffer
1172:                        System.arraycopy(buffer, HEADER_SIZE, rightBuffer,
1173:                                HEADER_SIZE, length * tupleSize);
1174:
1175:                        setLength(rightBuffer, length + rightLength);
1176:
1177:                        if (parentOffset < HEADER_SIZE)
1178:                            throw new IllegalStateException();
1179:
1180:                        // remove the buffer's pointer from the parent
1181:                        System.arraycopy(parentBuffer,
1182:                                parentOffset + tupleSize, parentBuffer,
1183:                                parentOffset, parentEnd - parentOffset
1184:                                        - tupleSize);
1185:
1186:                        setLength(parentBuffer, parentLength - 1);
1187:
1188:                        return;
1189:                    }
1190:                }
1191:
1192:                log.warning("BTree merge right can't find matching index: "
1193:                        + debugId(blockId));
1194:            }
1195:
1196:            /**
1197:             * Looks up the next block given the current block and the given key.
1198:             */
1199:            private long lookupTuple(long blockId, byte[] buffer,
1200:                    byte[] keyBuffer, int keyOffset, int keyLength,
1201:                    boolean isLeaf) throws IOException {
1202:                int length = getLength(buffer);
1203:
1204:                int offset = HEADER_SIZE;
1205:                int tupleSize = _tupleSize;
1206:                int end = offset + length * tupleSize;
1207:
1208:                long value;
1209:
1210:                while (length > 0) {
1211:                    int tail = offset + tupleSize * length;
1212:                    int delta = tupleSize * (length / 2);
1213:                    int newOffset = offset + delta;
1214:
1215:                    if (newOffset < 0) {
1216:                        System.out.println("UNDERFLOW: " + debugId(blockId)
1217:                                + " LENGTH:" + length + " STU:"
1218:                                + getLength(buffer) + " DELTA:" + delta);
1219:                        throw new IllegalStateException(
1220:                                "lookupTuple underflow newOffset:" + newOffset);
1221:
1222:                    } else if (newOffset > 65536) {
1223:                        System.out.println("OVERFLOW: " + debugId(blockId)
1224:                                + " LENGTH:" + length + " STU:"
1225:                                + getLength(buffer) + " DELTA:" + delta);
1226:                        throw new IllegalStateException(
1227:                                "lookupTuple overflow newOffset:" + newOffset);
1228:
1229:                    }
1230:
1231:                    int cmp = _keyCompare.compare(keyBuffer, keyOffset, buffer,
1232:                            PTR_SIZE + newOffset, keyLength);
1233:
1234:                    if (cmp == 0) {
1235:                        value = getPointer(buffer, newOffset);
1236:
1237:                        if (value == 0 && !isLeaf)
1238:                            throw new IllegalStateException(
1239:                                    "illegal 0 value at " + newOffset
1240:                                            + " for block " + debugId(blockId));
1241:
1242:                        return value;
1243:                    } else if (cmp > 0) {
1244:                        offset = newOffset + tupleSize;
1245:                        length = (tail - offset) / tupleSize;
1246:                    } else if (cmp < 0) {
1247:                        length = length / 2;
1248:                    }
1249:
1250:                    if (length > 0) {
1251:                    } else if (isLeaf)
1252:                        return 0;
1253:                    else if (cmp < 0) {
1254:                        value = getPointer(buffer, newOffset);
1255:
1256:                        if (value == 0 && !isLeaf)
1257:                            throw new IllegalStateException(
1258:                                    "illegal 0 value at " + newOffset
1259:                                            + " for block " + debugId(blockId));
1260:
1261:                        return value;
1262:                    } else if (offset == end) {
1263:                        value = getPointer(buffer, NEXT_OFFSET);
1264:
1265:                        if (value == 0 && !isLeaf)
1266:                            throw new IllegalStateException(
1267:                                    "illegal 0 value at " + newOffset
1268:                                            + " for block " + debugId(blockId));
1269:
1270:                        return value;
1271:                    } else {
1272:                        value = getPointer(buffer, offset);
1273:
1274:                        if (value == 0 && !isLeaf)
1275:                            throw new IllegalStateException(
1276:                                    "illegal 0 value at " + newOffset
1277:                                            + " for block " + debugId(blockId));
1278:
1279:                        return value;
1280:                    }
1281:                }
1282:
1283:                if (isLeaf)
1284:                    return 0;
1285:                else {
1286:                    value = getPointer(buffer, NEXT_OFFSET);
1287:
1288:                    if (value == 0 && !isLeaf)
1289:                        throw new IllegalStateException(
1290:                                "illegal 0 value at NEXT_OFFSET for block "
1291:                                        + debugId(blockId));
1292:
1293:                    return value;
1294:                }
1295:            }
1296:
1297:            /**
1298:             * Removes from the next block given the current block and the given key.
1299:             */
1300:            private long removeLeafEntry(long blockIndex, byte[] buffer,
1301:                    byte[] keyBuffer, int keyOffset, int keyLength)
1302:                    throws IOException {
1303:                int offset = HEADER_SIZE;
1304:                int tupleSize = _tupleSize;
1305:                int length = getLength(buffer);
1306:
1307:                for (int i = 0; i < length; i++) {
1308:                    int cmp = _keyCompare.compare(keyBuffer, keyOffset, buffer,
1309:                            offset + PTR_SIZE, keyLength);
1310:
1311:                    if (0 < cmp) {
1312:                        offset += tupleSize;
1313:                        continue;
1314:                    } else if (cmp == 0) {
1315:                        int tupleLength = length * tupleSize;
1316:
1317:                        if (offset + tupleSize < HEADER_SIZE + tupleLength) {
1318:                            if (offset < HEADER_SIZE)
1319:                                throw new IllegalStateException();
1320:
1321:                            System.arraycopy(buffer, offset + tupleSize,
1322:                                    buffer, offset, HEADER_SIZE + tupleLength
1323:                                            - offset - tupleSize);
1324:                        }
1325:
1326:                        setLength(buffer, length - 1);
1327:
1328:                        return i;
1329:                    } else {
1330:                        return 0;
1331:                    }
1332:                }
1333:
1334:                return 0;
1335:            }
1336:
1337:            private boolean isLeaf(byte[] buffer) {
1338:                return (getInt(buffer, FLAGS_OFFSET) & LEAF_FLAG) == 0;
1339:            }
1340:
1341:            private void setLeaf(byte[] buffer, boolean isLeaf) {
1342:                if (isLeaf)
1343:                    setInt(buffer, FLAGS_OFFSET, getInt(buffer, FLAGS_OFFSET)
1344:                            & ~LEAF_FLAG);
1345:                else
1346:                    setInt(buffer, FLAGS_OFFSET, getInt(buffer, FLAGS_OFFSET)
1347:                            | LEAF_FLAG);
1348:            }
1349:
1350:            /**
1351:             * Reads an int
1352:             */
1353:            private int getInt(byte[] buffer, int offset) {
1354:                return (((buffer[offset + 0] & 0xff) << 24)
1355:                        + ((buffer[offset + 1] & 0xff) << 16)
1356:                        + ((buffer[offset + 2] & 0xff) << 8) + ((buffer[offset + 3] & 0xff)));
1357:            }
1358:
1359:            /**
1360:             * Reads a pointer.
1361:             */
1362:            private long getPointer(byte[] buffer, int offset) {
1363:                return (((buffer[offset + 0] & 0xffL) << 56)
1364:                        + ((buffer[offset + 1] & 0xffL) << 48)
1365:                        + ((buffer[offset + 2] & 0xffL) << 40)
1366:                        + ((buffer[offset + 3] & 0xffL) << 32)
1367:                        + ((buffer[offset + 4] & 0xffL) << 24)
1368:                        + ((buffer[offset + 5] & 0xffL) << 16)
1369:                        + ((buffer[offset + 6] & 0xffL) << 8) + ((buffer[offset + 7] & 0xffL)));
1370:            }
1371:
1372:            /**
1373:             * Sets an int
1374:             */
1375:            private void setInt(byte[] buffer, int offset, int value) {
1376:                buffer[offset + 0] = (byte) (value >> 24);
1377:                buffer[offset + 1] = (byte) (value >> 16);
1378:                buffer[offset + 2] = (byte) (value >> 8);
1379:                buffer[offset + 3] = (byte) (value);
1380:            }
1381:
1382:            /**
1383:             * Sets the length
1384:             */
1385:            private void setLength(byte[] buffer, int value) {
1386:                if (value < 0 || BLOCK_SIZE / _tupleSize < value) {
1387:                    System.out.println("BAD-LENGTH: " + value);
1388:                    throw new IllegalArgumentException("BTree: bad length "
1389:                            + value);
1390:                }
1391:
1392:                setInt(buffer, LENGTH_OFFSET, value);
1393:            }
1394:
1395:            /**
1396:             * Sets the length
1397:             */
1398:            private int getLength(byte[] buffer) {
1399:                int value = getInt(buffer, LENGTH_OFFSET);
1400:
1401:                if (value < 0 || value > 65536) {
1402:                    System.out.println("BAD-LENGTH: " + value);
1403:                    throw new IllegalArgumentException("BTree: bad length "
1404:                            + value);
1405:                }
1406:
1407:                return value;
1408:            }
1409:
1410:            /**
1411:             * Sets a pointer.
1412:             */
1413:            private void setPointer(byte[] buffer, int offset, long value) {
1414:                if (offset <= LENGTH_OFFSET)
1415:                    System.out.println("BAD_POINTER: " + offset);
1416:
1417:                buffer[offset + 0] = (byte) (value >> 56);
1418:                buffer[offset + 1] = (byte) (value >> 48);
1419:                buffer[offset + 2] = (byte) (value >> 40);
1420:                buffer[offset + 3] = (byte) (value >> 32);
1421:                buffer[offset + 4] = (byte) (value >> 24);
1422:                buffer[offset + 5] = (byte) (value >> 16);
1423:                buffer[offset + 6] = (byte) (value >> 8);
1424:                buffer[offset + 7] = (byte) (value);
1425:            }
1426:
1427:            /**
1428:             * Opens the BTree.
1429:             */
1430:            private void start() throws IOException {
1431:                synchronized (this ) {
1432:                    if (_isStarted)
1433:                        return;
1434:
1435:                    _isStarted = true;
1436:                }
1437:            }
1438:
1439:            /**
1440:             * Testing: returns the keys for a block
1441:             */
1442:            public ArrayList<String> getBlockKeys(long blockIndex)
1443:                    throws IOException {
1444:                long blockId = _store.addressToBlockId(blockIndex * BLOCK_SIZE);
1445:
1446:                if (_store.isIndexBlock(blockId))
1447:                    return null;
1448:
1449:                Block block = _store.readBlock(blockId);
1450:
1451:                block.read();
1452:                byte[] buffer = block.getBuffer();
1453:
1454:                int length = getInt(buffer, LENGTH_OFFSET);
1455:                int offset = HEADER_SIZE;
1456:                int tupleSize = _tupleSize;
1457:
1458:                ArrayList<String> keys = new ArrayList<String>();
1459:                for (int i = 0; i < length; i++) {
1460:                    keys.add(_keyCompare.toString(buffer, offset + i
1461:                            * tupleSize + PTR_SIZE, tupleSize - PTR_SIZE));
1462:                }
1463:
1464:                block.free();
1465:
1466:                return keys;
1467:            }
1468:
1469:            public static BTree createTest(Path path, int keySize)
1470:                    throws IOException, java.sql.SQLException {
1471:                Database db = new Database();
1472:                db.setPath(path);
1473:                db.init();
1474:
1475:                Store store = new Store(db, "test", null);
1476:                store.create();
1477:
1478:                Block block = store.allocateIndexBlock();
1479:                long blockId = block.getBlockId();
1480:                block.free();
1481:
1482:                return new BTree(store, blockId, keySize, new KeyCompare());
1483:            }
1484:
1485:            public static BTree createStringTest(Path path, int keySize)
1486:                    throws IOException, java.sql.SQLException {
1487:                Store store = Store.create(path);
1488:
1489:                Block block = store.allocateIndexBlock();
1490:                long blockId = block.getBlockId();
1491:                block.free();
1492:
1493:                return new BTree(store, blockId, keySize,
1494:                        new StringKeyCompare());
1495:            }
1496:
1497:            private String debugId(long blockId) {
1498:                return "" + (blockId % Store.BLOCK_SIZE) + ":"
1499:                        + (blockId / Store.BLOCK_SIZE);
1500:            }
1501:
1502:            public void close() {
1503:                Block rootBlock = _rootBlock;
1504:                _rootBlock = null;
1505:
1506:                if (rootBlock != null)
1507:                    rootBlock.free();
1508:            }
1509:
1510:            public String toString() {
1511:                return "BTree[" + _store + "," + (_rootBlockId / BLOCK_SIZE)
1512:                        + "]";
1513:            }
1514:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.