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: }
|