001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
002:
003: This file is part of the db4o open source object database.
004:
005: db4o is free software; you can redistribute it and/or modify it under
006: the terms of version 2 of the GNU General Public License as published
007: by the Free Software Foundation and as clarified by db4objects' GPL
008: interpretation policy, available at
009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
011: Suite 350, San Mateo, CA 94403, USA.
012:
013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: for more details.
017:
018: You should have received a copy of the GNU General Public License along
019: with this program; if not, write to the Free Software Foundation, Inc.,
020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
021: package com.db4o.internal.btree;
022:
023: import java.io.IOException;
024:
025: import com.db4o.*;
026: import com.db4o.foundation.*;
027: import com.db4o.internal.*;
028: import com.db4o.internal.mapping.*;
029:
030: /**
031: * @exclude
032: */
033: public class BTree extends PersistentBase implements
034: TransactionParticipant {
035:
036: private static final byte BTREE_VERSION = (byte) 1;
037:
038: private static final int DEFRAGMENT_INCREMENT_OFFSET = 1 // version byte
039: + Const4.INT_LENGTH * 2; // size, node size
040:
041: private final Indexable4 _keyHandler;
042:
043: private BTreeNode _root;
044:
045: /**
046: * All instantiated nodes are held in this tree.
047: */
048: private TreeIntObject _nodes;
049:
050: private int _size;
051:
052: private Visitor4 _removeListener;
053:
054: private Hashtable4 _sizesByTransaction;
055:
056: protected Queue4 _processing;
057:
058: private int _nodeSize;
059:
060: int _halfNodeSize;
061:
062: private final int _cacheHeight;
063:
064: public BTree(Transaction trans, int id, Indexable4 keyHandler) {
065: this (trans, id, keyHandler, config(trans).bTreeNodeSize(),
066: config(trans).bTreeCacheHeight());
067: }
068:
069: public BTree(Transaction trans, int id, Indexable4 keyHandler,
070: final int treeNodeSize, final int treeCacheHeight) {
071: if (null == keyHandler) {
072: throw new ArgumentNullException();
073: }
074: _nodeSize = treeNodeSize;
075:
076: _halfNodeSize = _nodeSize / 2;
077: _nodeSize = _halfNodeSize * 2;
078: _cacheHeight = treeCacheHeight;
079: _keyHandler = keyHandler;
080: _sizesByTransaction = new Hashtable4();
081: if (id == 0) {
082: setStateDirty();
083: _root = new BTreeNode(this , 0, true, 0, 0, 0);
084: _root.write(trans.systemTransaction());
085: addNode(_root);
086: write(trans.systemTransaction());
087: } else {
088: setID(id);
089: setStateDeactivated();
090: }
091: }
092:
093: public BTreeNode root() {
094: return _root;
095: }
096:
097: public int nodeSize() {
098: return _nodeSize;
099: }
100:
101: public void add(Transaction trans, Object key) {
102: keyCantBeNull(key);
103: _keyHandler.prepareComparison(key);
104: ensureDirty(trans);
105: BTreeNode rootOrSplit = _root.add(trans, key);
106: if (rootOrSplit != null && rootOrSplit != _root) {
107: _root = new BTreeNode(trans, _root, rootOrSplit);
108: _root.write(trans.systemTransaction());
109: addNode(_root);
110: }
111: }
112:
113: // FIXME: Change the signature to return true, if object could be removed.
114: public void remove(Transaction trans, Object key) {
115: keyCantBeNull(key);
116:
117: final Iterator4 pointers = search(trans, key).pointers();
118: if (!pointers.moveNext()) {
119: return;
120: }
121: BTreePointer first = (BTreePointer) pointers.current();
122: ensureDirty(trans);
123: BTreeNode node = first.node();
124: node.remove(trans, key, first.index());
125: }
126:
127: public BTreeRange search(Transaction trans, Object key) {
128: keyCantBeNull(key);
129:
130: // TODO: Optimize the following.
131: // Part of the search operates against the same nodes.
132: // As long as the bounds are on one node, the search
133: // should walk the nodes in one go.
134:
135: BTreeNodeSearchResult start = searchLeaf(trans, key,
136: SearchTarget.LOWEST);
137: BTreeNodeSearchResult end = searchLeaf(trans, key,
138: SearchTarget.HIGHEST);
139: return start.createIncludingRange(end);
140: }
141:
142: private void keyCantBeNull(Object key) {
143: if (null == key) {
144: throw new ArgumentNullException();
145: }
146: }
147:
148: public Indexable4 keyHandler() {
149: return _keyHandler;
150: }
151:
152: public BTreeNodeSearchResult searchLeaf(Transaction trans,
153: Object key, SearchTarget target) {
154: ensureActive(trans);
155: _keyHandler.prepareComparison(key);
156: return _root.searchLeaf(trans, target);
157: }
158:
159: public void commit(final Transaction trans) {
160:
161: final Transaction systemTransaction = trans.systemTransaction();
162:
163: Object sizeDiff = _sizesByTransaction.get(trans);
164: if (sizeDiff != null) {
165: _size += ((Integer) sizeDiff).intValue();
166: }
167: _sizesByTransaction.remove(trans);
168:
169: if (_nodes != null) {
170: commitNodes(trans);
171: writeAllNodes(systemTransaction);
172: }
173:
174: setStateDirty();
175: write(systemTransaction);
176:
177: purge();
178: }
179:
180: public void commitNodes(Transaction trans) {
181: if (_nodes == null) {
182: return;
183: }
184: processAllNodes();
185: while (_processing.hasNext()) {
186: ((BTreeNode) _processing.next()).commit(trans);
187: }
188: _processing = null;
189: }
190:
191: public void rollback(final Transaction trans) {
192:
193: final Transaction systemTransaction = trans.systemTransaction();
194:
195: _sizesByTransaction.remove(trans);
196:
197: if (_nodes == null) {
198: return;
199: }
200:
201: processAllNodes();
202: while (_processing.hasNext()) {
203: ((BTreeNode) _processing.next()).rollback(trans);
204: }
205: _processing = null;
206:
207: writeAllNodes(systemTransaction);
208:
209: setStateDirty();
210: write(systemTransaction);
211:
212: purge();
213: }
214:
215: private void writeAllNodes(final Transaction systemTransaction) {
216: if (_nodes == null) {
217: return;
218: }
219: _nodes.traverse(new Visitor4() {
220: public void visit(Object obj) {
221: BTreeNode node = (BTreeNode) ((TreeIntObject) obj)
222: .getObject();
223: node.write(systemTransaction);
224: }
225: });
226: }
227:
228: private void purge() {
229: if (_nodes == null) {
230: return;
231: }
232:
233: Tree temp = _nodes;
234: _nodes = null;
235:
236: if (_cacheHeight > 0) {
237: _root.markAsCached(_cacheHeight);
238: } else {
239: _root.holdChildrenAsIDs();
240: addNode(_root);
241: }
242:
243: temp.traverse(new Visitor4() {
244: public void visit(Object obj) {
245: BTreeNode node = (BTreeNode) ((TreeIntObject) obj)
246: .getObject();
247: node.purge();
248: }
249: });
250: }
251:
252: private void processAllNodes() {
253: _processing = new NonblockingQueue();
254: _nodes.traverse(new Visitor4() {
255: public void visit(Object obj) {
256: _processing.add(((TreeIntObject) obj).getObject());
257: }
258: });
259: }
260:
261: private void ensureActive(Transaction trans) {
262: if (!isActive()) {
263: read(trans.systemTransaction());
264: }
265: }
266:
267: private void ensureDirty(Transaction trans) {
268: ensureActive(trans);
269: if (canEnlistWithTransaction()) {
270: ((LocalTransaction) trans).enlist(this );
271: }
272: setStateDirty();
273: }
274:
275: protected boolean canEnlistWithTransaction() {
276: return true;
277: }
278:
279: public byte getIdentifier() {
280: return Const4.BTREE;
281: }
282:
283: public void setRemoveListener(Visitor4 vis) {
284: _removeListener = vis;
285: }
286:
287: public int ownLength() {
288: return 1 + Const4.OBJECT_LENGTH + (Const4.INT_LENGTH * 2)
289: + Const4.ID_LENGTH;
290: }
291:
292: BTreeNode produceNode(int id) {
293: TreeIntObject addtio = new TreeIntObject(id);
294: _nodes = (TreeIntObject) Tree.add(_nodes, addtio);
295: TreeIntObject tio = (TreeIntObject) addtio.addedOrExisting();
296: BTreeNode node = (BTreeNode) tio.getObject();
297: if (node == null) {
298: node = new BTreeNode(id, this );
299: tio.setObject(node);
300: addToProcessing(node);
301: }
302: return node;
303: }
304:
305: void addNode(BTreeNode node) {
306: _nodes = (TreeIntObject) Tree.add(_nodes, new TreeIntObject(
307: node.getID(), node));
308: addToProcessing(node);
309: }
310:
311: void addToProcessing(BTreeNode node) {
312: if (_processing != null) {
313: _processing.add(node);
314: }
315: }
316:
317: void removeNode(BTreeNode node) {
318: _nodes = (TreeIntObject) _nodes.removeLike(new TreeInt(node
319: .getID()));
320: }
321:
322: void notifyRemoveListener(Object obj) {
323: if (_removeListener != null) {
324: _removeListener.visit(obj);
325: }
326: }
327:
328: public void readThis(Transaction a_trans, Buffer a_reader) {
329: a_reader.incrementOffset(1); // first byte is version, for possible future format changes
330: _size = a_reader.readInt();
331: _nodeSize = a_reader.readInt();
332: _halfNodeSize = nodeSize() / 2;
333: _root = produceNode(a_reader.readInt());
334: }
335:
336: public void writeThis(Transaction trans, Buffer a_writer) {
337: a_writer.writeByte(BTREE_VERSION);
338: a_writer.writeInt(_size);
339: a_writer.writeInt(nodeSize());
340: a_writer.writeIDOf(trans, _root);
341: }
342:
343: public int size(Transaction trans) {
344: ensureActive(trans);
345: Object sizeDiff = _sizesByTransaction.get(trans);
346: if (sizeDiff != null) {
347: return _size + ((Integer) sizeDiff).intValue();
348: }
349: return _size;
350: }
351:
352: public void traverseKeys(Transaction trans, Visitor4 visitor) {
353: ensureActive(trans);
354: if (_root == null) {
355: return;
356: }
357: _root.traverseKeys(trans, visitor);
358: }
359:
360: public void sizeChanged(Transaction trans, int changeBy) {
361: Object sizeDiff = _sizesByTransaction.get(trans);
362: if (sizeDiff == null) {
363: _sizesByTransaction.put(trans, new Integer(changeBy));
364: return;
365: }
366: _sizesByTransaction.put(trans, new Integer(((Integer) sizeDiff)
367: .intValue()
368: + changeBy));
369: }
370:
371: public void dispose(Transaction transaction) {
372: // nothing to do here
373: }
374:
375: public BTreePointer firstPointer(Transaction trans) {
376: ensureActive(trans);
377: if (null == _root) {
378: return null;
379: }
380: return _root.firstPointer(trans);
381: }
382:
383: public BTreePointer lastPointer(Transaction trans) {
384: ensureActive(trans);
385: if (null == _root) {
386: return null;
387: }
388: return _root.lastPointer(trans);
389: }
390:
391: public BTree debugLoadFully(Transaction trans) {
392: ensureActive(trans);
393: _root.debugLoadFully(trans);
394: return this ;
395: }
396:
397: private void traverseAllNodes(Transaction trans, Visitor4 command) {
398: ensureActive(trans);
399: _root.traverseAllNodes(trans, command);
400: }
401:
402: public void defragIndex(BufferPair readers) {
403: if (Deploy.debug) {
404: readers.readBegin(Const4.BTREE);
405: }
406: readers.incrementOffset(DEFRAGMENT_INCREMENT_OFFSET);
407: readers.copyID();
408: if (Deploy.debug) {
409: readers.readEnd();
410: }
411: }
412:
413: public void defragIndexNode(BufferPair readers) {
414: BTreeNode.defragIndex(readers, _keyHandler);
415: }
416:
417: public void defragBTree(final DefragContext context)
418: throws CorruptionException, IOException {
419: BufferPair.processCopy(context, getID(), new SlotCopyHandler() {
420: public void processCopy(BufferPair readers)
421: throws CorruptionException {
422: defragIndex(readers);
423: }
424: });
425: final CorruptionException[] corruptx = { null };
426: final IOException[] iox = { null };
427: try {
428: context.traverseAllIndexSlots(this , new Visitor4() {
429: public void visit(Object obj) {
430: final int id = ((Integer) obj).intValue();
431: try {
432: BufferPair.processCopy(context, id,
433: new SlotCopyHandler() {
434: public void processCopy(
435: BufferPair readers) {
436: defragIndexNode(readers);
437: }
438: });
439: } catch (CorruptionException e) {
440: corruptx[0] = e;
441: throw new RuntimeException();
442: } catch (IOException e) {
443: iox[0] = e;
444: throw new RuntimeException();
445: }
446: }
447: });
448: } catch (RuntimeException e) {
449: if (corruptx[0] != null) {
450: throw corruptx[0];
451: }
452: if (iox[0] != null) {
453: throw iox[0];
454: }
455: throw e;
456: }
457: }
458:
459: public int compareKeys(Object key1, Object key2) {
460: _keyHandler.prepareComparison(key2);
461: return _keyHandler.compareTo(key1);
462: }
463:
464: private static Config4Impl config(Transaction trans) {
465: if (null == trans) {
466: throw new ArgumentNullException();
467: }
468: return trans.container().configImpl();
469: }
470:
471: public void free(Transaction systemTrans) {
472: freeAllNodeIds(systemTrans, allNodeIds(systemTrans));
473: super .free(systemTrans);
474: }
475:
476: private void freeAllNodeIds(Transaction systemTrans,
477: final Iterator4 allNodeIDs) {
478: while (allNodeIDs.moveNext()) {
479: int id = ((Integer) allNodeIDs.current()).intValue();
480: systemTrans.slotFreePointerOnCommit(id);
481: }
482: }
483:
484: public Iterator4 allNodeIds(Transaction systemTrans) {
485: final Collection4 allNodeIDs = new Collection4();
486: traverseAllNodes(systemTrans, new Visitor4() {
487: public void visit(Object node) {
488: allNodeIDs.add(new Integer(((BTreeNode) node).getID()));
489: }
490: });
491: return allNodeIDs.iterator();
492: }
493:
494: public BTreeRange asRange(Transaction trans) {
495: return new BTreeRangeSingle(trans, this , firstPointer(trans),
496: null);
497: }
498:
499: private void traverseAllNodes(final Visitor4 visitor) {
500: if (_nodes == null) {
501: return;
502: }
503: _nodes.traverse(new Visitor4() {
504: public void visit(Object obj) {
505: visitor.visit(((TreeIntObject) obj).getObject());
506: }
507: });
508: }
509:
510: public String toString() {
511: final StringBuffer sb = new StringBuffer();
512: sb.append("BTree ");
513: sb.append(getID());
514: sb.append(" Active Nodes: \n");
515: traverseAllNodes(new Visitor4() {
516: public void visit(Object obj) {
517: sb.append(obj);
518: sb.append("\n");
519: }
520: });
521: return sb.toString();
522: }
523:
524: }
|