KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > db4o > inside > btree > BTree


1 /* Copyright (C) 2004 - 2006 db4objects Inc. http://www.db4o.com
2
3 This file is part of the db4o open source object database.
4
5 db4o is free software; you can redistribute it and/or modify it under
6 the terms of version 2 of the GNU General Public License as published
7 by the Free Software Foundation and as clarified by db4objects' GPL
8 interpretation policy, available at
9 http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
10 Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
11 Suite 350, San Mateo, CA 94403, USA.
12
13 db4o is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License along
19 with this program; if not, write to the Free Software Foundation, Inc.,
20 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */

21 package com.db4o.inside.btree;
22
23 import com.db4o.*;
24 import com.db4o.foundation.*;
25 import com.db4o.inside.ix.*;
26 import com.db4o.inside.mapping.*;
27
28 /**
29  * @exclude
30  */

31 public class BTree extends YapMeta implements TransactionParticipant {
32     
33     private static final byte BTREE_VERSION = (byte)1;
34     
35     private static final int DEFRAGMENT_INCREMENT_OFFSET =
36         1 // version byte
37
+ YapConst.INT_LENGTH * 2; // size, node size
38

39     final Indexable4 _keyHandler;
40     
41     final Indexable4 _valueHandler;
42     
43     private BTreeNode _root;
44    
45     /**
46      * All instantiated nodes are held in this tree.
47      */

48     private TreeIntObject _nodes;
49     
50     private int _size;
51     
52     private Visitor4 _removeListener;
53     
54     private Hashtable4 _sizesByTransaction;
55     
56     protected Queue4 _processing;
57     
58     private int _nodeSize;
59     
60     int _halfNodeSize;
61     
62     private final int _cacheHeight;
63     
64     public BTree(Transaction trans, int id, Indexable4 keyHandler){
65         this(trans, id, keyHandler, null);
66     }
67             
68     public BTree(Transaction trans, int id, Indexable4 keyHandler, Indexable4 valueHandler){
69         this(trans, id, keyHandler, valueHandler, config(trans).bTreeNodeSize(), config(trans).bTreeCacheHeight());
70     }
71
72     public BTree(Transaction trans, int id, Indexable4 keyHandler, Indexable4 valueHandler, final int treeNodeSize, final int treeCacheHeight) {
73         if (null == keyHandler) {
74             throw new ArgumentNullException();
75         }
76         _nodeSize = treeNodeSize;
77         
78         _halfNodeSize = _nodeSize / 2;
79         _nodeSize = _halfNodeSize * 2;
80         _cacheHeight = treeCacheHeight;
81         _keyHandler = keyHandler;
82         _valueHandler = (valueHandler == null) ? Null.INSTANCE : valueHandler;
83         _sizesByTransaction = new Hashtable4();
84         if(id == 0){
85             setStateDirty();
86             _root = new BTreeNode(this, 0, true, 0, 0, 0);
87             _root.write(trans.systemTransaction());
88             addNode(_root);
89             write(trans.systemTransaction());
90         }else{
91             setID(id);
92             setStateDeactivated();
93         }
94     }
95     
96     public BTreeNode root() {
97         return _root;
98     }
99     
100     public int nodeSize() {
101         return _nodeSize;
102     }
103
104     public void add(Transaction trans, Object JavaDoc key){
105         add(trans, key, null);
106     }
107     
108     public void add(Transaction trans, Object JavaDoc key, Object JavaDoc value){
109         keyCantBeNull(key);
110         _keyHandler.prepareComparison(key);
111         _valueHandler.prepareComparison(value);
112         ensureDirty(trans);
113         BTreeNode rootOrSplit = _root.add(trans);
114         if(rootOrSplit != null && rootOrSplit != _root){
115             _root = new BTreeNode(trans, _root, rootOrSplit);
116             _root.write(trans.systemTransaction());
117             addNode(_root);
118         }
119     }
120
121     public void remove(Transaction trans, Object JavaDoc key){
122         keyCantBeNull(key);
123         
124         final Iterator4 pointers = search(trans, key).pointers();
125         if (!pointers.moveNext()) {
126             return;
127         }
128         BTreePointer first = (BTreePointer)pointers.current();
129         ensureDirty(trans);
130         BTreeNode node = first.node();
131         node.remove(trans, first.index());
132     }
133     
134     public BTreeRange search(Transaction trans, Object JavaDoc key) {
135         keyCantBeNull(key);
136         
137         // TODO: Optimize the following.
138
// Part of the search operates against the same nodes.
139
// As long as the bounds are on one node, the search
140
// should walk the nodes in one go.
141

142         BTreeNodeSearchResult start = searchLeaf(trans, key, SearchTarget.LOWEST);
143         BTreeNodeSearchResult end = searchLeaf(trans, key, SearchTarget.HIGHEST);
144         return start.createIncludingRange(end);
145     }
146     
147     private void keyCantBeNull(Object JavaDoc key) {
148         if (null == key) {
149             throw new ArgumentNullException();
150         }
151     }
152
153     public BTreeNodeSearchResult searchLeaf(Transaction trans, Object JavaDoc 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 JavaDoc sizeDiff = _sizesByTransaction.get(trans);
164         if(sizeDiff != null){
165             _size += ((Integer JavaDoc) sizeDiff).intValue();
166         }
167         _sizesByTransaction.remove(trans);
168         
169         if(_nodes != null){
170             
171             processAllNodes();
172             while(_processing.hasNext()){
173                 ((BTreeNode)_processing.next()).commit(trans);
174             }
175             _processing = null;
176             
177             writeAllNodes(systemTransaction, true);
178             
179         }
180         
181         setStateDirty();
182         write(systemTransaction);
183         
184         purge();
185     }
186     
187     public void rollback(final Transaction trans){
188         
189         final Transaction systemTransaction = trans.systemTransaction();
190         
191         _sizesByTransaction.remove(trans);
192         
193         if(_nodes == null){
194             return;
195         }
196         
197         processAllNodes();
198         while(_processing.hasNext()){
199             ((BTreeNode)_processing.next()).rollback(trans);
200         }
201         _processing = null;
202         
203         writeAllNodes(systemTransaction, false);
204         
205         setStateDirty();
206         write(systemTransaction);
207         
208         purge();
209     }
210     
211     private void writeAllNodes(final Transaction systemTransaction, final boolean setDirty){
212         if(_nodes == null){
213             return;
214         }
215         _nodes.traverse(new Visitor4() {
216             public void visit(Object JavaDoc obj) {
217                 BTreeNode node = (BTreeNode)((TreeIntObject)obj).getObject();
218                 if(setDirty){
219                     node.setStateDirty();
220                 }
221                 node.write(systemTransaction);
222             }
223         });
224     }
225     
226     
227     private void purge(){
228         if(_nodes == null){
229             return;
230         }
231         
232         Tree temp = _nodes;
233         _nodes = null;
234         
235         if(_cacheHeight > 0){
236             _root.markAsCached(_cacheHeight);
237         }else{
238             _root.holdChildrenAsIDs();
239             addNode(_root);
240         }
241         
242         temp.traverse(new Visitor4() {
243             public void visit(Object JavaDoc obj) {
244                 BTreeNode node = (BTreeNode)((TreeIntObject)obj).getObject();
245                 node.purge();
246             }
247         });
248     }
249     
250     private void processAllNodes(){
251         _processing = new Queue4();
252         _nodes.traverse(new Visitor4() {
253             public void visit(Object JavaDoc obj) {
254                 _processing.add(((TreeIntObject)obj).getObject());
255             }
256         });
257     }
258     
259     private void ensureActive(Transaction trans){
260         if(! isActive()){
261             read(trans.systemTransaction());
262         }
263     }
264     
265     private void ensureDirty(Transaction trans){
266         ensureActive(trans);
267         trans.enlist(this);
268         setStateDirty();
269     }
270     
271     public byte getIdentifier() {
272         return YapConst.BTREE;
273     }
274     
275     public void setRemoveListener(Visitor4 vis){
276         _removeListener = vis;
277     }
278     
279     public int ownLength() {
280         return 1 + YapConst.OBJECT_LENGTH + (YapConst.INT_LENGTH * 2) + YapConst.ID_LENGTH;
281     }
282     
283     BTreeNode produceNode(int id){
284         TreeIntObject addtio = new TreeIntObject(id);
285         _nodes = (TreeIntObject)Tree.add(_nodes, addtio);
286         TreeIntObject tio = (TreeIntObject)addtio.duplicateOrThis();
287         BTreeNode node = (BTreeNode)tio.getObject();
288         if(node == null){
289             node = new BTreeNode(id, this);
290             tio.setObject(node);
291             addToProcessing(node);
292         }
293         return node;
294     }
295     
296     void addNode(BTreeNode node){
297         _nodes = (TreeIntObject)Tree.add(_nodes, new TreeIntObject(node.getID(), node));
298         addToProcessing(node);
299     }
300     
301     void addToProcessing(BTreeNode node){
302         if(_processing != null){
303             _processing.add(node);
304         }
305     }
306     
307     void removeNode(BTreeNode node){
308         _nodes = (TreeIntObject)_nodes.removeLike(new TreeInt(node.getID()));
309     }
310     
311     void notifyRemoveListener(Object JavaDoc obj){
312         if(_removeListener != null){
313             _removeListener.visit(obj);
314         }
315     }
316
317     public void readThis(Transaction a_trans, YapReader a_reader) {
318         a_reader.incrementOffset(1); // first byte is version, for possible future format changes
319
_size = a_reader.readInt();
320         _nodeSize = a_reader.readInt();
321         _halfNodeSize = nodeSize() / 2;
322         _root = produceNode(a_reader.readInt());
323     }
324     
325     public void writeThis(Transaction trans, YapReader a_writer) {
326         a_writer.append(BTREE_VERSION);
327         a_writer.writeInt(_size);
328         a_writer.writeInt(nodeSize());
329         a_writer.writeIDOf(trans, _root);
330     }
331     
332     public int size(Transaction trans){
333         ensureActive(trans);
334         Object JavaDoc sizeDiff = _sizesByTransaction.get(trans);
335         if(sizeDiff != null){
336             return _size + ((Integer JavaDoc) sizeDiff).intValue();
337         }
338         return _size;
339     }
340     
341     public void traverseKeys(Transaction trans, Visitor4 visitor){
342         ensureActive(trans);
343         if(_root == null){
344             return;
345         }
346         _root.traverseKeys(trans, visitor);
347     }
348     
349     public void traverseValues(Transaction trans, Visitor4 visitor) {
350         ensureActive(trans);
351         if(_root == null){
352             return;
353         }
354         _root.traverseValues(trans, visitor);
355     }
356     
357     public void sizeChanged(Transaction trans, int changeBy){
358         Object JavaDoc sizeDiff = _sizesByTransaction.get(trans);
359         if(sizeDiff == null){
360             _sizesByTransaction.put(trans, new Integer JavaDoc(changeBy));
361             return;
362         }
363         _sizesByTransaction.put(trans, new Integer JavaDoc(((Integer JavaDoc) sizeDiff).intValue() + changeBy));
364     }
365
366     public void dispose(Transaction transaction) {
367         // nothing to do here
368
}
369
370     public BTreePointer firstPointer(Transaction trans) {
371         ensureActive(trans);
372         if (null == _root) {
373             return null;
374         }
375         return _root.firstPointer(trans);
376     }
377     
378     public BTreePointer lastPointer(Transaction trans) {
379         ensureActive(trans);
380         if (null == _root) {
381             return null;
382         }
383         return _root.lastPointer(trans);
384     }
385     
386     public BTree debugLoadFully(Transaction trans) {
387         ensureActive(trans);
388         _root.debugLoadFully(trans);
389         return this;
390     }
391     
392     private void traverseAllNodes(Transaction trans, Visitor4 command) {
393         ensureActive(trans);
394         _root.traverseAllNodes(trans, command);
395     }
396
397     public void defragIndex(ReaderPair readers) {
398         if (Deploy.debug) {
399             readers.readBegin(YapConst.BTREE);
400         }
401         readers.incrementOffset(DEFRAGMENT_INCREMENT_OFFSET);
402         readers.copyID();
403         if (Deploy.debug) {
404             readers.readEnd();
405         }
406     }
407
408     public void defragIndexNode(ReaderPair readers) {
409         BTreeNode.defragIndex(readers, _keyHandler, _valueHandler);
410     }
411
412     public void defragBTree(final DefragContext context) throws CorruptionException {
413         ReaderPair.processCopy(context,getID(),new SlotCopyHandler() {
414             public void processCopy(ReaderPair readers) throws CorruptionException {
415                 defragIndex(readers);
416             }
417         });
418         final CorruptionException[] exc={null};
419         try {
420             context.traverseAllIndexSlots(this, new Visitor4() {
421                 public void visit(Object JavaDoc obj) {
422                     final int id=((Integer JavaDoc)obj).intValue();
423                     try {
424                         ReaderPair.processCopy(context, id, new SlotCopyHandler() {
425                             public void processCopy(ReaderPair readers) {
426                                 defragIndexNode(readers);
427                             }
428                         });
429                     } catch (CorruptionException e) {
430                         exc[0]=e;
431                         throw new RuntimeException JavaDoc();
432                     }
433                 }
434             });
435         } catch (RuntimeException JavaDoc e) {
436             if(exc[0]!=null) {
437                 throw exc[0];
438             }
439             throw e;
440         }
441     }
442
443     public int compareKeys(Object JavaDoc key1, Object JavaDoc key2) {
444         _keyHandler.prepareComparison(key2);
445         return _keyHandler.compareTo(key1);
446     }
447     
448     private static Config4Impl config(Transaction trans) {
449         if (null == trans) {
450             throw new ArgumentNullException();
451         }
452         return trans.stream().configImpl();
453     }
454
455     public void free(Transaction systemTrans) {
456         freeAllNodeIds(systemTrans, allNodeIds(systemTrans));
457     }
458
459     private void freeAllNodeIds(Transaction systemTrans, final Iterator4 allNodeIDs) {
460         while(allNodeIDs.moveNext()){
461             int id = ((Integer JavaDoc)allNodeIDs.current()).intValue();
462             systemTrans.slotFreePointerOnCommit(id);
463         }
464     }
465
466     public Iterator4 allNodeIds(Transaction systemTrans) {
467         final Collection4 allNodeIDs = new Collection4();
468         traverseAllNodes(systemTrans, new Visitor4() {
469             public void visit(Object JavaDoc node) {
470                 allNodeIDs.add(new Integer JavaDoc(((BTreeNode)node).getID()));
471             }
472         });
473         return allNodeIDs.iterator();
474     }
475     
476     public BTreeRange asRange(Transaction trans){
477         return new BTreeRangeSingle(trans, this, firstPointer(trans), null);
478     }
479
480     
481 }
482
483
Popular Tags