0001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
0002:
0003: This file is part of the db4o open source object database.
0004:
0005: db4o is free software; you can redistribute it and/or modify it under
0006: the terms of version 2 of the GNU General Public License as published
0007: by the Free Software Foundation and as clarified by db4objects' GPL
0008: interpretation policy, available at
0009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
0010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
0011: Suite 350, San Mateo, CA 94403, USA.
0012:
0013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
0014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
0015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0016: for more details.
0017:
0018: You should have received a copy of the GNU General Public License along
0019: with this program; if not, write to the Free Software Foundation, Inc.,
0020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
0021: package com.db4o.internal.btree;
0022:
0023: import com.db4o.*;
0024: import com.db4o.foundation.*;
0025: import com.db4o.internal.*;
0026:
0027: /**
0028: * We work with BTreeNode in two states:
0029: *
0030: * - deactivated: never read, no valid members, ID correct or 0 if new
0031: * - write: real representation of keys, values and children in arrays
0032: * The write state can be detected with canWrite(). States can be changed
0033: * as needed with prepareRead() and prepareWrite().
0034: *
0035: * @exclude
0036: */
0037: public final class BTreeNode extends PersistentBase {
0038:
0039: private static final int COUNT_LEAF_AND_3_LINK_LENGTH = (Const4.INT_LENGTH * 4) + 1;
0040:
0041: private static final int SLOT_LEADING_LENGTH = Const4.LEADING_LENGTH
0042: + COUNT_LEAF_AND_3_LINK_LENGTH;
0043:
0044: final BTree _btree;
0045:
0046: private int _count;
0047:
0048: private boolean _isLeaf;
0049:
0050: private Object[] _keys;
0051:
0052: /**
0053: * Can contain BTreeNode or Integer for ID of BTreeNode
0054: */
0055: private Object[] _children;
0056:
0057: private int _parentID;
0058:
0059: private int _previousID;
0060:
0061: private int _nextID;
0062:
0063: private boolean _cached;
0064:
0065: private boolean _dead;
0066:
0067: /* Constructor for new nodes */
0068: public BTreeNode(BTree btree, int count, boolean isLeaf,
0069: int parentID, int previousID, int nextID) {
0070: _btree = btree;
0071: _parentID = parentID;
0072: _previousID = previousID;
0073: _nextID = nextID;
0074: _count = count;
0075: _isLeaf = isLeaf;
0076: prepareArrays();
0077: }
0078:
0079: /* Constructor for existing nodes, requires valid ID */
0080: public BTreeNode(int id, BTree btree) {
0081: _btree = btree;
0082: setID(id);
0083: setStateDeactivated();
0084: }
0085:
0086: /* Constructor to create a new root from two nodes */
0087: public BTreeNode(Transaction trans, BTreeNode firstChild,
0088: BTreeNode secondChild) {
0089: this (firstChild._btree, 2, false, 0, 0, 0);
0090: _keys[0] = firstChild._keys[0];
0091: _children[0] = firstChild;
0092: _keys[1] = secondChild._keys[0];
0093: _children[1] = secondChild;
0094:
0095: write(trans.systemTransaction());
0096:
0097: firstChild.setParentID(trans, getID());
0098: secondChild.setParentID(trans, getID());
0099: }
0100:
0101: public BTree btree() {
0102: return _btree;
0103: }
0104:
0105: /**
0106: * @return the split node if this node is split
0107: * or this if the first key has changed
0108: */
0109: public BTreeNode add(Transaction trans, Object obj) {
0110:
0111: Buffer reader = prepareRead(trans);
0112: Searcher s = search(reader);
0113:
0114: if (_isLeaf) {
0115:
0116: prepareWrite(trans);
0117:
0118: if (wasRemoved(trans, s)) {
0119: cancelRemoval(trans, obj, s.cursor());
0120: return null;
0121: }
0122:
0123: if (s.count() > 0 && !s.beforeFirst()) {
0124: s.moveForward();
0125: }
0126:
0127: prepareInsert(s.cursor());
0128: _keys[s.cursor()] = newAddPatch(trans, obj);
0129: } else {
0130:
0131: BTreeNode childNode = child(reader, s.cursor());
0132: BTreeNode childNodeOrSplit = childNode.add(trans, obj);
0133: if (childNodeOrSplit == null) {
0134: return null;
0135: }
0136: prepareWrite(trans);
0137: _keys[s.cursor()] = childNode._keys[0];
0138: if (childNode != childNodeOrSplit) {
0139: int splitCursor = s.cursor() + 1;
0140: prepareInsert(splitCursor);
0141: _keys[splitCursor] = childNodeOrSplit._keys[0];
0142: _children[splitCursor] = childNodeOrSplit;
0143: }
0144: }
0145:
0146: if (mustSplit()) {
0147: return split(trans);
0148: }
0149:
0150: if (s.cursor() == 0) {
0151: return this ;
0152: }
0153:
0154: return null;
0155: }
0156:
0157: private boolean mustSplit() {
0158: return _count >= _btree.nodeSize();
0159: }
0160:
0161: private BTreeAdd newAddPatch(Transaction trans, Object obj) {
0162: sizeIncrement(trans);
0163: return new BTreeAdd(trans, obj);
0164: }
0165:
0166: private void cancelRemoval(Transaction trans, Object obj, int index) {
0167: final BTreeUpdate patch = (BTreeUpdate) keyPatch(index);
0168: BTreeUpdate nextPatch = patch.removeFor(trans);
0169: _keys[index] = newCancelledRemoval(trans, patch.getObject(),
0170: obj, nextPatch);
0171: sizeIncrement(trans);
0172: }
0173:
0174: private BTreePatch newCancelledRemoval(Transaction trans,
0175: Object originalObject, Object currentObject,
0176: BTreeUpdate existingPatches) {
0177: return new BTreeCancelledRemoval(trans, originalObject,
0178: currentObject, existingPatches);
0179: }
0180:
0181: private void sizeIncrement(Transaction trans) {
0182: _btree.sizeChanged(trans, 1);
0183: }
0184:
0185: private boolean wasRemoved(Transaction trans, Searcher s) {
0186: if (!s.foundMatch()) {
0187: return false;
0188: }
0189: BTreePatch patch = keyPatch(trans, s.cursor());
0190: return patch != null && patch.isRemove();
0191: }
0192:
0193: BTreeNodeSearchResult searchLeaf(Transaction trans,
0194: SearchTarget target) {
0195: Buffer reader = prepareRead(trans);
0196: Searcher s = search(reader, target);
0197: if (!_isLeaf) {
0198: return child(reader, s.cursor()).searchLeaf(trans, target);
0199: }
0200:
0201: if (!s.foundMatch() || target == SearchTarget.ANY
0202: || target == SearchTarget.HIGHEST) {
0203: return new BTreeNodeSearchResult(trans, reader, btree(), s,
0204: this );
0205: }
0206:
0207: if (target == SearchTarget.LOWEST) {
0208: BTreeNodeSearchResult res = findLowestLeafMatch(trans, s
0209: .cursor() - 1);
0210: if (res != null) {
0211: return res;
0212: }
0213: return createMatchingSearchResult(trans, reader, s.cursor());
0214: }
0215:
0216: throw new IllegalStateException();
0217:
0218: }
0219:
0220: private BTreeNodeSearchResult findLowestLeafMatch(
0221: Transaction trans, int index) {
0222: return findLowestLeafMatch(trans, prepareRead(trans), index);
0223: }
0224:
0225: private BTreeNodeSearchResult findLowestLeafMatch(
0226: Transaction trans, Buffer reader, int index) {
0227:
0228: if (index >= 0) {
0229: if (!compareEquals(reader, index)) {
0230: return null;
0231: }
0232: if (index > 0) {
0233: BTreeNodeSearchResult res = findLowestLeafMatch(trans,
0234: reader, index - 1);
0235: if (res != null) {
0236: return res;
0237: }
0238: return createMatchingSearchResult(trans, reader, index);
0239: }
0240: }
0241:
0242: final BTreeNode node = previousNode();
0243: if (node != null) {
0244: final Buffer nodeReader = node.prepareRead(trans);
0245: BTreeNodeSearchResult res = node.findLowestLeafMatch(trans,
0246: nodeReader, node.lastIndex());
0247: if (res != null) {
0248: return res;
0249: }
0250: }
0251:
0252: if (index < 0) {
0253: return null;
0254: }
0255:
0256: return createMatchingSearchResult(trans, reader, index);
0257: }
0258:
0259: private boolean compareEquals(final Buffer reader, int index) {
0260: if (canWrite()) {
0261: return compareInWriteMode(index) == 0;
0262: }
0263: return compareInReadMode(reader, index) == 0;
0264: }
0265:
0266: private BTreeNodeSearchResult createMatchingSearchResult(
0267: Transaction trans, Buffer reader, int index) {
0268: return new BTreeNodeSearchResult(trans, reader, btree(), this ,
0269: index, true);
0270: }
0271:
0272: public boolean canWrite() {
0273: return _keys != null;
0274: }
0275:
0276: BTreeNode child(int index) {
0277: if (_children[index] instanceof BTreeNode) {
0278: return (BTreeNode) _children[index];
0279: }
0280: return _btree.produceNode(((Integer) _children[index])
0281: .intValue());
0282: }
0283:
0284: BTreeNode child(Buffer reader, int index) {
0285: if (childLoaded(index)) {
0286: return (BTreeNode) _children[index];
0287: }
0288: BTreeNode child = _btree.produceNode(childID(reader, index));
0289:
0290: if (_children != null) {
0291: if (_cached || child.canWrite()) {
0292: _children[index] = child;
0293: }
0294: }
0295:
0296: return child;
0297: }
0298:
0299: private int childID(Buffer reader, int index) {
0300: if (_children == null) {
0301: seekChild(reader, index);
0302: return reader.readInt();
0303: }
0304: return childID(index);
0305: }
0306:
0307: private int childID(int index) {
0308: if (childLoaded(index)) {
0309: return ((BTreeNode) _children[index]).getID();
0310: }
0311: return ((Integer) _children[index]).intValue();
0312: }
0313:
0314: private boolean childLoaded(int index) {
0315: if (_children == null) {
0316: return false;
0317: }
0318: return _children[index] instanceof BTreeNode;
0319: }
0320:
0321: private boolean childCanSupplyFirstKey(int index) {
0322: if (!childLoaded(index)) {
0323: return false;
0324: }
0325: return ((BTreeNode) _children[index]).canWrite();
0326: }
0327:
0328: void commit(Transaction trans) {
0329: commitOrRollback(trans, true);
0330: }
0331:
0332: void commitOrRollback(Transaction trans, boolean isCommit) {
0333:
0334: if (DTrace.enabled) {
0335: DTrace.BTREE_NODE_COMMIT_OR_ROLLBACK.log(getID());
0336: }
0337:
0338: if (_dead) {
0339: return;
0340: }
0341:
0342: _cached = false;
0343:
0344: if (!_isLeaf) {
0345: return;
0346: }
0347:
0348: if (!isDirty(trans)) {
0349: return;
0350: }
0351:
0352: Object keyZero = _keys[0];
0353:
0354: Object[] tempKeys = new Object[_btree.nodeSize()];
0355: int count = 0;
0356:
0357: for (int i = 0; i < _count; i++) {
0358: Object key = _keys[i];
0359: BTreePatch patch = keyPatch(i);
0360: if (patch != null) {
0361: key = isCommit ? patch.commit(trans, _btree) : patch
0362: .rollback(trans, _btree);
0363: }
0364: if (key != No4.INSTANCE) {
0365: tempKeys[count] = key;
0366: count++;
0367: }
0368: }
0369:
0370: _keys = tempKeys;
0371: _count = count;
0372:
0373: if (freeIfEmpty(trans)) {
0374: return;
0375: }
0376:
0377: setStateDirty();
0378:
0379: // TODO: Merge nodes here on low _count value.
0380:
0381: if (_keys[0] != keyZero) {
0382: tellParentAboutChangedKey(trans);
0383: }
0384:
0385: }
0386:
0387: private boolean freeIfEmpty(Transaction trans) {
0388: return freeIfEmpty(trans, _count);
0389: }
0390:
0391: private boolean freeIfEmpty(Transaction trans, int count) {
0392: if (count > 0) {
0393: return false;
0394: }
0395: if (isRoot()) {
0396: return false;
0397: }
0398: free(trans);
0399: return true;
0400: }
0401:
0402: private boolean isRoot() {
0403: return _btree.root() == this ;
0404: }
0405:
0406: public boolean equals(Object obj) {
0407: if (this == obj) {
0408: return true;
0409: }
0410: if (!(obj instanceof BTreeNode)) {
0411: return false;
0412: }
0413: BTreeNode other = (BTreeNode) obj;
0414: return getID() == other.getID();
0415: }
0416:
0417: public int hashCode() {
0418: return getID();
0419: }
0420:
0421: public void free(Transaction trans) {
0422: _dead = true;
0423: if (!isRoot()) {
0424: BTreeNode parent = _btree.produceNode(_parentID);
0425: parent.removeChild(trans, this );
0426: }
0427: pointPreviousTo(trans, _nextID);
0428: pointNextTo(trans, _previousID);
0429: super .free(trans);
0430: _btree.removeNode(this );
0431: }
0432:
0433: void holdChildrenAsIDs() {
0434: if (_children == null) {
0435: return;
0436: }
0437: for (int i = 0; i < _count; i++) {
0438: if (_children[i] instanceof BTreeNode) {
0439: _children[i] = new Integer(((BTreeNode) _children[i])
0440: .getID());
0441: }
0442: }
0443: }
0444:
0445: private void removeChild(Transaction trans, BTreeNode child) {
0446: prepareWrite(trans);
0447: int id = child.getID();
0448: for (int i = 0; i < _count; i++) {
0449: if (childID(i) == id) {
0450: if (freeIfEmpty(trans, _count - 1)) {
0451: return;
0452: }
0453: remove(i);
0454: if (i <= 1) {
0455: tellParentAboutChangedKey(trans);
0456: }
0457: if (_count == 0) {
0458: // root node empty case only, have to turn it into a leaf
0459: _isLeaf = true;
0460: }
0461: return;
0462: }
0463: }
0464: throw new IllegalStateException("child not found");
0465: }
0466:
0467: private void keyChanged(Transaction trans, BTreeNode child) {
0468: prepareWrite(trans);
0469: int id = child.getID();
0470: for (int i = 0; i < _count; i++) {
0471: if (childID(i) == id) {
0472: _keys[i] = child._keys[0];
0473: _children[i] = child;
0474: keyChanged(trans, i);
0475: return;
0476: }
0477: }
0478: throw new IllegalStateException("child not found");
0479: }
0480:
0481: private void tellParentAboutChangedKey(Transaction trans) {
0482: if (!isRoot()) {
0483: BTreeNode parent = _btree.produceNode(_parentID);
0484: parent.keyChanged(trans, this );
0485: }
0486: }
0487:
0488: private boolean isDirty(Transaction trans) {
0489: if (!canWrite()) {
0490: return false;
0491: }
0492:
0493: for (int i = 0; i < _count; i++) {
0494: if (keyPatch(trans, i) != null) {
0495: return true;
0496: }
0497: }
0498:
0499: return false;
0500: }
0501:
0502: private int compareInWriteMode(int index) {
0503: return keyHandler().compareTo(key(index));
0504: }
0505:
0506: private int compareInReadMode(Buffer reader, int index) {
0507: seekKey(reader, index);
0508: return keyHandler().compareTo(
0509: keyHandler().readIndexEntry(reader));
0510: }
0511:
0512: public int count() {
0513: return _count;
0514: }
0515:
0516: private int entryLength() {
0517: int len = keyHandler().linkLength();
0518: if (!_isLeaf) {
0519: len += Const4.ID_LENGTH;
0520: }
0521: return len;
0522: }
0523:
0524: public int firstKeyIndex(Transaction trans) {
0525: for (int ix = 0; ix < _count; ix++) {
0526: if (indexIsValid(trans, ix)) {
0527: return ix;
0528: }
0529: }
0530: return -1;
0531: }
0532:
0533: public int lastKeyIndex(Transaction trans) {
0534: for (int ix = _count - 1; ix >= 0; ix--) {
0535: if (indexIsValid(trans, ix)) {
0536: return ix;
0537: }
0538: }
0539: return -1;
0540: }
0541:
0542: public boolean indexIsValid(Transaction trans, int index) {
0543: if (!canWrite()) {
0544: return true;
0545: }
0546: BTreePatch patch = keyPatch(index);
0547: if (patch == null) {
0548: return true;
0549: }
0550: return patch.key(trans) != No4.INSTANCE;
0551: }
0552:
0553: private Object firstKey(Transaction trans) {
0554: final int index = firstKeyIndex(trans);
0555: if (-1 == index) {
0556: return No4.INSTANCE;
0557: }
0558: return key(trans, index);
0559: }
0560:
0561: public byte getIdentifier() {
0562: return Const4.BTREE_NODE;
0563: }
0564:
0565: private void prepareInsert(int pos) {
0566: if (pos > lastIndex()) {
0567: _count++;
0568: return;
0569: }
0570: int len = _count - pos;
0571: System.arraycopy(_keys, pos, _keys, pos + 1, len);
0572: if (_children != null) {
0573: System.arraycopy(_children, pos, _children, pos + 1, len);
0574: }
0575: _count++;
0576: }
0577:
0578: private void remove(int pos) {
0579: if (DTrace.enabled) {
0580: DTrace.BTREE_NODE_REMOVE.log(getID());
0581: }
0582: int len = _count - pos;
0583: _count--;
0584: System.arraycopy(_keys, pos + 1, _keys, pos, len);
0585: _keys[_count] = null;
0586: if (_children != null) {
0587: System.arraycopy(_children, pos + 1, _children, pos, len);
0588: _children[_count] = null;
0589: }
0590: }
0591:
0592: Object key(int index) {
0593: Object obj = _keys[index];
0594: if (obj instanceof BTreePatch) {
0595: return ((BTreePatch) obj).getObject();
0596: }
0597: return obj;
0598: }
0599:
0600: Object key(Transaction trans, Buffer reader, int index) {
0601: if (canWrite()) {
0602: return key(trans, index);
0603: }
0604: seekKey(reader, index);
0605: return keyHandler().readIndexEntry(reader);
0606: }
0607:
0608: Object key(Transaction trans, int index) {
0609: BTreePatch patch = keyPatch(index);
0610: if (patch == null) {
0611: return _keys[index];
0612: }
0613: return patch.key(trans);
0614: }
0615:
0616: private BTreePatch keyPatch(int index) {
0617: Object obj = _keys[index];
0618: if (obj instanceof BTreePatch) {
0619: return (BTreePatch) obj;
0620: }
0621: return null;
0622: }
0623:
0624: private BTreePatch keyPatch(Transaction trans, int index) {
0625: Object obj = _keys[index];
0626: if (obj instanceof BTreePatch) {
0627: return ((BTreePatch) obj).forTransaction(trans);
0628: }
0629: return null;
0630: }
0631:
0632: private Indexable4 keyHandler() {
0633: return _btree.keyHandler();
0634: }
0635:
0636: void markAsCached(int height) {
0637: _cached = true;
0638: _btree.addNode(this );
0639:
0640: if (_isLeaf || (_children == null)) {
0641: return;
0642: }
0643:
0644: height--;
0645:
0646: if (height < 1) {
0647: holdChildrenAsIDs();
0648: return;
0649: }
0650:
0651: for (int i = 0; i < _count; i++) {
0652: if (_children[i] instanceof BTreeNode) {
0653: ((BTreeNode) _children[i]).markAsCached(height);
0654: }
0655: }
0656: }
0657:
0658: public int ownLength() {
0659: return SLOT_LEADING_LENGTH + (_count * entryLength())
0660: + Const4.BRACKETS_BYTES;
0661: }
0662:
0663: Buffer prepareRead(Transaction trans) {
0664:
0665: if (canWrite()) {
0666: return null;
0667: }
0668:
0669: if (isNew()) {
0670: return null;
0671: }
0672:
0673: if (_cached) {
0674: read(trans.systemTransaction());
0675: _btree.addToProcessing(this );
0676: return null;
0677: }
0678:
0679: Buffer reader = ((LocalTransaction) trans).file()
0680: .readReaderByID(trans.systemTransaction(), getID());
0681:
0682: if (Deploy.debug) {
0683: reader.readBegin(getIdentifier());
0684: }
0685:
0686: readNodeHeader(reader);
0687:
0688: return reader;
0689: }
0690:
0691: void prepareWrite(Transaction trans) {
0692:
0693: if (_dead) {
0694: return;
0695: }
0696:
0697: if (canWrite()) {
0698: setStateDirty();
0699: return;
0700: }
0701:
0702: read(trans.systemTransaction());
0703: setStateDirty();
0704: _btree.addToProcessing(this );
0705: }
0706:
0707: private void prepareArrays() {
0708: if (canWrite()) {
0709: return;
0710: }
0711: _keys = new Object[_btree.nodeSize()];
0712: if (!_isLeaf) {
0713: _children = new Object[_btree.nodeSize()];
0714: }
0715: }
0716:
0717: private void readNodeHeader(Buffer reader) {
0718: _count = reader.readInt();
0719: byte leafByte = reader.readByte();
0720: _isLeaf = (leafByte == 1);
0721: _parentID = reader.readInt();
0722: _previousID = reader.readInt();
0723: _nextID = reader.readInt();
0724: }
0725:
0726: public void readThis(Transaction trans, Buffer reader) {
0727: readNodeHeader(reader);
0728:
0729: prepareArrays();
0730:
0731: boolean isInner = !_isLeaf;
0732: for (int i = 0; i < _count; i++) {
0733: _keys[i] = keyHandler().readIndexEntry(reader);
0734: if (isInner) {
0735: _children[i] = new Integer(reader.readInt());
0736: }
0737: }
0738: }
0739:
0740: public void remove(Transaction trans, Object obj, int index) {
0741: if (!_isLeaf) {
0742: throw new IllegalStateException();
0743: }
0744:
0745: prepareWrite(trans);
0746:
0747: BTreePatch patch = keyPatch(index);
0748:
0749: // no patch, no problem, can remove
0750: if (patch == null) {
0751: _keys[index] = newRemovePatch(trans, obj);
0752: keyChanged(trans, index);
0753: return;
0754: }
0755:
0756: BTreePatch transPatch = patch.forTransaction(trans);
0757: if (transPatch != null) {
0758: if (transPatch.isAdd()) {
0759: cancelAdding(trans, index);
0760: return;
0761: }
0762: if (transPatch.isCancelledRemoval()) {
0763: BTreeRemove removePatch = applyNewRemovePatch(trans,
0764: transPatch.getObject());
0765: _keys[index] = ((BTreeUpdate) patch).replacePatch(
0766: transPatch, removePatch);
0767: keyChanged(trans, index);
0768: return;
0769: }
0770: } else {
0771: // If the patch is a removal of a cancelled removal for another
0772: // transaction, we need one for this transaction also.
0773: if (!patch.isAdd()) {
0774: ((BTreeUpdate) patch)
0775: .append(newRemovePatch(trans, obj));
0776: return;
0777: }
0778: }
0779:
0780: // now we try if removal is OK for the next element in this node
0781: if (index != lastIndex()) {
0782: if (compareInWriteMode(index + 1) != 0) {
0783: return;
0784: }
0785: remove(trans, obj, index + 1);
0786: return;
0787: }
0788:
0789: // nothing else worked so far, move on to the next node, try there
0790: BTreeNode node = nextNode();
0791:
0792: if (node == null) {
0793: return;
0794: }
0795:
0796: node.prepareWrite(trans);
0797: if (node.compareInWriteMode(0) != 0) {
0798: return;
0799: }
0800:
0801: node.remove(trans, obj, 0);
0802: }
0803:
0804: private void cancelAdding(Transaction trans, int index) {
0805: _btree.notifyRemoveListener(keyPatch(index).getObject());
0806: if (freeIfEmpty(trans, _count - 1)) {
0807: sizeDecrement(trans);
0808: return;
0809: }
0810: remove(index);
0811: keyChanged(trans, index);
0812: sizeDecrement(trans);
0813: }
0814:
0815: private void sizeDecrement(Transaction trans) {
0816: _btree.sizeChanged(trans, -1);
0817: }
0818:
0819: private int lastIndex() {
0820: return _count - 1;
0821: }
0822:
0823: private BTreeRemove newRemovePatch(Transaction trans, Object obj) {
0824: return applyNewRemovePatch(trans, obj);
0825: }
0826:
0827: private BTreeRemove applyNewRemovePatch(Transaction trans,
0828: Object key) {
0829: sizeDecrement(trans);
0830: return new BTreeRemove(trans, key);
0831: }
0832:
0833: private void keyChanged(Transaction trans, int index) {
0834: if (index == 0) {
0835: tellParentAboutChangedKey(trans);
0836: }
0837: }
0838:
0839: void rollback(Transaction trans) {
0840: commitOrRollback(trans, false);
0841: }
0842:
0843: private Searcher search(Buffer reader) {
0844: return search(reader, SearchTarget.ANY);
0845: }
0846:
0847: private Searcher search(Buffer reader, SearchTarget target) {
0848: Searcher s = new Searcher(target, _count);
0849: if (canWrite()) {
0850: while (s.incomplete()) {
0851: s.resultIs(compareInWriteMode(s.cursor()));
0852: }
0853: } else {
0854: while (s.incomplete()) {
0855: s.resultIs(compareInReadMode(reader, s.cursor()));
0856: }
0857: }
0858: return s;
0859: }
0860:
0861: private void seekAfterKey(Buffer reader, int ix) {
0862: seekKey(reader, ix);
0863: reader._offset += keyHandler().linkLength();
0864: }
0865:
0866: private void seekChild(Buffer reader, int ix) {
0867: seekAfterKey(reader, ix);
0868: }
0869:
0870: private void seekKey(Buffer reader, int ix) {
0871: reader._offset = SLOT_LEADING_LENGTH + (entryLength() * ix);
0872: }
0873:
0874: private BTreeNode split(Transaction trans) {
0875:
0876: BTreeNode res = new BTreeNode(_btree, _btree._halfNodeSize,
0877: _isLeaf, _parentID, getID(), _nextID);
0878:
0879: System.arraycopy(_keys, _btree._halfNodeSize, res._keys, 0,
0880: _btree._halfNodeSize);
0881: for (int i = _btree._halfNodeSize; i < _keys.length; i++) {
0882: _keys[i] = null;
0883: }
0884: if (_children != null) {
0885: res._children = new Object[_btree.nodeSize()];
0886: System.arraycopy(_children, _btree._halfNodeSize,
0887: res._children, 0, _btree._halfNodeSize);
0888: for (int i = _btree._halfNodeSize; i < _children.length; i++) {
0889: _children[i] = null;
0890: }
0891: }
0892:
0893: _count = _btree._halfNodeSize;
0894:
0895: res.write(trans.systemTransaction());
0896: _btree.addNode(res);
0897:
0898: int splitID = res.getID();
0899:
0900: pointNextTo(trans, splitID);
0901:
0902: setNextID(trans, splitID);
0903:
0904: if (_children != null) {
0905: for (int i = 0; i < _btree._halfNodeSize; i++) {
0906: if (res._children[i] == null) {
0907: break;
0908: }
0909: res.child(i).setParentID(trans, splitID);
0910: }
0911: }
0912: return res;
0913: }
0914:
0915: private void pointNextTo(Transaction trans, int id) {
0916: if (_nextID != 0) {
0917: nextNode().setPreviousID(trans, id);
0918: }
0919: }
0920:
0921: private void pointPreviousTo(Transaction trans, int id) {
0922: if (_previousID != 0) {
0923: previousNode().setNextID(trans, id);
0924: }
0925: }
0926:
0927: public BTreeNode previousNode() {
0928: if (_previousID == 0) {
0929: return null;
0930: }
0931: return _btree.produceNode(_previousID);
0932: }
0933:
0934: public BTreeNode nextNode() {
0935: if (_nextID == 0) {
0936: return null;
0937: }
0938: return _btree.produceNode(_nextID);
0939: }
0940:
0941: BTreePointer firstPointer(Transaction trans) {
0942: Buffer reader = prepareRead(trans);
0943: if (_isLeaf) {
0944: return leafFirstPointer(trans, reader);
0945: }
0946: return branchFirstPointer(trans, reader);
0947: }
0948:
0949: private BTreePointer branchFirstPointer(Transaction trans,
0950: Buffer reader) {
0951: for (int i = 0; i < _count; i++) {
0952: BTreePointer childFirstPointer = child(reader, i)
0953: .firstPointer(trans);
0954: if (childFirstPointer != null) {
0955: return childFirstPointer;
0956: }
0957: }
0958: return null;
0959: }
0960:
0961: private BTreePointer leafFirstPointer(Transaction trans,
0962: Buffer reader) {
0963: int index = firstKeyIndex(trans);
0964: if (index == -1) {
0965: return null;
0966: }
0967: return new BTreePointer(trans, reader, this , index);
0968: }
0969:
0970: public BTreePointer lastPointer(Transaction trans) {
0971: Buffer reader = prepareRead(trans);
0972: if (_isLeaf) {
0973: return leafLastPointer(trans, reader);
0974: }
0975: return branchLastPointer(trans, reader);
0976: }
0977:
0978: private BTreePointer branchLastPointer(Transaction trans,
0979: Buffer reader) {
0980: for (int i = _count - 1; i >= 0; i--) {
0981: BTreePointer childLastPointer = child(reader, i)
0982: .lastPointer(trans);
0983: if (childLastPointer != null) {
0984: return childLastPointer;
0985: }
0986: }
0987: return null;
0988: }
0989:
0990: private BTreePointer leafLastPointer(Transaction trans,
0991: Buffer reader) {
0992: int index = lastKeyIndex(trans);
0993: if (index == -1) {
0994: return null;
0995: }
0996: return new BTreePointer(trans, reader, this , index);
0997: }
0998:
0999: void purge() {
1000: if (_dead) {
1001: _keys = null;
1002: _children = null;
1003: return;
1004: }
1005:
1006: if (_cached) {
1007: return;
1008: }
1009:
1010: if (!canWrite()) {
1011: return;
1012: }
1013:
1014: for (int i = 0; i < _count; i++) {
1015: if (_keys[i] instanceof BTreePatch) {
1016: holdChildrenAsIDs();
1017: _btree.addNode(this );
1018: return;
1019: }
1020: }
1021: }
1022:
1023: private void setParentID(Transaction trans, int id) {
1024: prepareWrite(trans);
1025: _parentID = id;
1026: }
1027:
1028: private void setPreviousID(Transaction trans, int id) {
1029: prepareWrite(trans);
1030: _previousID = id;
1031: }
1032:
1033: private void setNextID(Transaction trans, int id) {
1034: prepareWrite(trans);
1035: _nextID = id;
1036: }
1037:
1038: public void traverseKeys(Transaction trans, Visitor4 visitor) {
1039: Buffer reader = prepareRead(trans);
1040: if (_isLeaf) {
1041: for (int i = 0; i < _count; i++) {
1042: Object obj = key(trans, reader, i);
1043: if (obj != No4.INSTANCE) {
1044: visitor.visit(obj);
1045: }
1046: }
1047: } else {
1048: for (int i = 0; i < _count; i++) {
1049: child(reader, i).traverseKeys(trans, visitor);
1050: }
1051: }
1052: }
1053:
1054: public boolean writeObjectBegin() {
1055: if (_dead) {
1056: return false;
1057: }
1058: if (!canWrite()) {
1059: return false;
1060: }
1061: return super .writeObjectBegin();
1062: }
1063:
1064: public void writeThis(Transaction trans, Buffer a_writer) {
1065:
1066: int count = 0;
1067: int startOffset = a_writer._offset;
1068:
1069: a_writer.incrementOffset(COUNT_LEAF_AND_3_LINK_LENGTH);
1070:
1071: if (_isLeaf) {
1072: for (int i = 0; i < _count; i++) {
1073: Object obj = key(trans, i);
1074: if (obj != No4.INSTANCE) {
1075: count++;
1076: keyHandler().writeIndexEntry(a_writer, obj);
1077: }
1078: }
1079: } else {
1080: for (int i = 0; i < _count; i++) {
1081: if (childCanSupplyFirstKey(i)) {
1082: BTreeNode child = (BTreeNode) _children[i];
1083: Object childKey = child.firstKey(trans);
1084: if (childKey != No4.INSTANCE) {
1085: count++;
1086: keyHandler()
1087: .writeIndexEntry(a_writer, childKey);
1088: a_writer.writeIDOf(trans, child);
1089: }
1090: } else {
1091: count++;
1092: keyHandler().writeIndexEntry(a_writer, key(i));
1093: a_writer.writeIDOf(trans, _children[i]);
1094: }
1095: }
1096: }
1097:
1098: int endOffset = a_writer._offset;
1099: a_writer._offset = startOffset;
1100: a_writer.writeInt(count);
1101: a_writer.writeByte(_isLeaf ? (byte) 1 : (byte) 0);
1102: a_writer.writeInt(_parentID);
1103: a_writer.writeInt(_previousID);
1104: a_writer.writeInt(_nextID);
1105: a_writer._offset = endOffset;
1106:
1107: }
1108:
1109: public String toString() {
1110: if (_count == 0) {
1111: return "Node " + getID() + " not loaded";
1112: }
1113: String str = "\nBTreeNode";
1114: str += "\nid: " + getID();
1115: str += "\nparent: " + _parentID;
1116: str += "\nprevious: " + _previousID;
1117: str += "\nnext: " + _nextID;
1118: str += "\ncount:" + _count;
1119: str += "\nleaf:" + _isLeaf + "\n";
1120:
1121: if (canWrite()) {
1122:
1123: str += " { ";
1124:
1125: boolean first = true;
1126:
1127: for (int i = 0; i < _count; i++) {
1128: if (_keys[i] != null) {
1129: if (!first) {
1130: str += ", ";
1131: }
1132: str += _keys[i].toString();
1133: first = false;
1134: }
1135: }
1136:
1137: str += " }";
1138: }
1139: return str;
1140: }
1141:
1142: public void debugLoadFully(Transaction trans) {
1143: prepareWrite(trans);
1144: if (_isLeaf) {
1145: return;
1146: }
1147: for (int i = 0; i < _count; ++i) {
1148: if (_children[i] instanceof Integer) {
1149: _children[i] = btree().produceNode(
1150: ((Integer) _children[i]).intValue());
1151: }
1152: ((BTreeNode) _children[i]).debugLoadFully(trans);
1153: }
1154: }
1155:
1156: public static void defragIndex(BufferPair readers,
1157: Indexable4 keyHandler) {
1158: if (Deploy.debug) {
1159: readers.readBegin(Const4.BTREE_NODE);
1160: }
1161: // count
1162: int count = readers.readInt();
1163: // leafByte
1164: byte leafByte = readers.readByte();
1165: boolean isLeaf = (leafByte == 1);
1166:
1167: readers.copyID(); // parent ID
1168: readers.copyID(); // previous ID
1169: readers.copyID(); // next ID
1170:
1171: for (int i = 0; i < count; i++) {
1172: keyHandler.defragIndexEntry(readers);
1173: if (!isLeaf) {
1174: readers.copyID();
1175: }
1176: }
1177: if (Deploy.debug) {
1178: readers.readEnd();
1179: }
1180: }
1181:
1182: public boolean isFreespaceComponent() {
1183: return _btree.isFreespaceComponent();
1184: }
1185:
1186: public boolean isLeaf() {
1187: return _isLeaf;
1188: }
1189:
1190: /** This traversal goes over all nodes, not just leafs */
1191: void traverseAllNodes(Transaction trans, Visitor4 command) {
1192: Buffer reader = prepareRead(trans);
1193: command.visit(this );
1194: if (_isLeaf) {
1195: return;
1196: }
1197: for (int childIdx = 0; childIdx < _count; childIdx++) {
1198: child(reader, childIdx).traverseAllNodes(trans, command);
1199: }
1200: }
1201:
1202: }
|