Java > Open Source Codes > com > jofti > btree > BTree


1 /*
2  * BTree.java
3   * Copyright (C) <2005> <Steve Woodcock>
4  *
5
6  * Created on 09 May 2003, 15:13
7  */
8 package com.jofti.btree;
9
10 import java.lang.reflect.Array ;
11 import java.util.ArrayList ;
12 import java.util.Collection ;
13 import java.util.Iterator ;
14 import java.util.Map ;
15 import java.util.Properties ;
16 import java.util.Set ;
17 import java.util.Stack ;
18
19 import org.apache.commons.logging.Log;
20 import org.apache.commons.logging.LogFactory;
21
22 import edu.emory.mathcs.backport.java.util.concurrent.atomic.AtomicLong;
23
24
25 import com.jofti.core.IStoreManager;
26 import com.jofti.exception.JoftiException;
27 import com.jofti.locking.LockManager;
28 import com.jofti.oswego.concurrent.WriterPreferenceReadWriteLock;
29 import com.jofti.util.OpenHashMap;
30
31
32 /**
33  * A B*Tree variation based on the paper by Lehman and Yao [Efficient concurrent operations on b-trees - 1981] on concurrent BTree design.<p>
34  * Following on from this paper the tree also adopts the recommendations of not coalesing nodes when half full. Rather nodes are only removed when empty.
35  * This reduces the structural overheads significantly, while trading off for some redundant space. This space depends on the data order on deletion. But assuming it is reasonably
36  * random the space is a worthwhile tradeoff.<p>
37  *
38  * @author Steve Woodcock<br>
39  * @version 1.43<br>
40  */
41 public class BTree {
42
43     private static Log log = LogFactory.getLog(BTree.class);
44     
45     //not final as does get reset
46 private static int MAX_NODE_SIZE = 64;
47     
48     private Node rootNode = null;
49
50     private NodeFactory factory=null;
51     
52     public static LeafNodeEntry MAX_LEAF_ENTRY ;
53
54     
55     public static final ValueObject MIN_RIGHT_VALUE = new ValueObject(Integer.MIN_VALUE,ValueObject.MIN_COMAPARBLE_VALUE);
56     
57     // lock for the whole tree for structural modifications - possibly change to semaphore
58 private final WriterPreferenceReadWriteLock treeEntryLock = new WriterPreferenceReadWriteLock();
59
60     
61     private long nodes =0;
62     
63     // count of number of entries
64 private AtomicLong entries =new AtomicLong(0);
65     
66     // used to store LeafNodes to disk
67 IStoreManager overflowManager =null;
68     
69     /**
70      * Constructs a new BTree
71      */
72     public BTree()
73     {
74     }
75     
76     /**
77      * Creates a BTree with a set maxNodeSize.
78      * @param maxNodeSize
79      */
80     public BTree(int maxNodeSize)
81     {
82         MAX_NODE_SIZE = maxNodeSize;
83     }
84     
85     /**
86      * @return the tree's current maxnode size.
87      */
88     public static int getMaxNodeSize(){
89         return MAX_NODE_SIZE;
90     }
91
92     protected Node getRootNode()
93     {
94         return rootNode;
95     }
96
97
98     /**
99      * Used to initialise the B-Tree. This <b>must</b> be called in order to set a needed max
100      * right value. Without this subsequent calls will result in a failure.
101      *
102      * @throws JoftiException
103      */
104     public void init(Properties props) throws JoftiException
105     {
106         
107         // see if we have an overflow manager configured
108 factory = NodeFactory.getInstance(overflowManager);
109            
110         MAX_LEAF_ENTRY = factory.createMaxLeafNodeEntry();
111         
112         // we need to be sure that the tree is not being restrutured
113 LockManager.acquireRWLock(treeEntryLock, LockManager.WRITE_LOCK);
114         rootNode = factory.createLeafNode();
115         rootNode.setEntries(new Object [BTree.getMaxNodeSize()]);
116         
117         // max value for right value
118 rootNode.setRightValue(MAX_LEAF_ENTRY.getValue());
119         
120         // populate tree with max value
121 rootNode.insertEntry(MAX_LEAF_ENTRY);
122         nodes++;
123         LockManager.releaseRWLock(treeEntryLock, LockManager.WRITE_LOCK);
124
125     }
126
127
128     
129     /**
130      *
131      * Inserts a nodeEntry into the BTree. All values are stored in the leaves of the tree.<p>
132      * <p>
133      * The insertion acquires a readlock on the treeEntryLock.
134      * </p>
135      *<p>
136      *The insertion will acquire readlocks as it descends the tree until it finds the correct node, upon which it will
137      *acquire a write lock. The descent is not lock coupled so if we arrive at the wrong leaf node we scan across until we find the
138      *correct node to insert. This behaviour prevents us having to lock the tree, or the path and is enabled by the right nod pointers in each node.
139      *</p>
140      *<p>
141      *Having inserted the entry into a leaf node, the stack of nodes is then unwound to insert relevant pointers into the parent
142      *nodes if necessary. A similar locking strategy is applied on this ascent.
143      *</p>
144      * @param entry a Node Entry.
145      * @throws JoftiException thrown on error inserting the entry into a node.
146      */
147     public void insert(NodeEntry entry) throws JoftiException
148     {
149         Stack nodeStack = new Stack ();
150         
151         // we need to be sure that the tree is not being restrutured
152 LockManager.acquireRWLock(treeEntryLock, LockManager.READ_LOCK);
153         try {
154             nodeStack.push(rootNode);
155             insert(entry, nodeStack);
156             entries.incrementAndGet();
157         } finally{
158             LockManager.releaseRWLock(treeEntryLock, LockManager.READ_LOCK);
159         }
160     }
161
162     /**
163      * <p>
164      * Removes all entries in the index and resets the nodes to 0.
165      * </p>
166      * <p>
167      * Acquires a write lock on the treeEntryLock.
168      * </p>
169      * <p>
170      * If an overflowManager is set in the tree this will also dump the disk storage.
171      * </p>
172      */
173     public void removeAll(){
174         
175         try {
176             LockManager.acquireRWLock(treeEntryLock, LockManager.WRITE_LOCK);
177             
178             //reset the manager
179 if (overflowManager != null){
180                 overflowManager.removeAll();
181             }
182             
183             rootNode = factory.createLeafNode();
184             rootNode.setEntries(new Object [BTree.getMaxNodeSize()]);
185             rootNode.setRightValue(MAX_LEAF_ENTRY.getValue());
186             rootNode.insertEntry(MAX_LEAF_ENTRY);
187             nodes=1;
188             entries =new AtomicLong(0);
189             LockManager.releaseRWLock(treeEntryLock, LockManager.WRITE_LOCK);
190         } catch (JoftiException e){
191             log.fatal("Error removing all entries ",e);
192             
193         }
194
195     }
196
197     protected Node findNode(NodeEntry entry, Stack nodeStack) throws JoftiException
198     {
199         // get the first node
200 Node currentNode = (Node) nodeStack.pop();
201
202         //acquire a read lock on the node
203 LockManager.acquireLock(currentNode, LockManager.READ_LOCK);
204
205         // while not a leaf node scan through tree and record path
206 while (!currentNode.isLeaf())
207         {
208
209             Object returnNode = scanNode(entry.getValue(), currentNode);
210             // if not a link node then push prior node onto the stack
211
212             if (!(returnNode instanceof NodeLink))
213             {
214                 // if not the link node from scan node then it must be
215 // a child node and we can put that on the stack
216 nodeStack.push(currentNode);
217                 currentNode = (Node)returnNode;
218             } else
219             {
220                 currentNode = (Node)((NodeLink) returnNode).getNode();
221             }
222             // repeat this loop until we arrive at a leaf
223 }
224
225         // release the read lock we held on the leaf
226 LockManager.releaseLock(currentNode, LockManager.READ_LOCK);
227
228         // we now acquire a write lock on the leaf node
229 // we could be on the wrong leaf here by the time we acquire
230 // this write lock
231
232         LockManager.acquireLock(currentNode, LockManager.WRITE_LOCK);
233
234         // we may well be in the wrong node a split may have occurred between
235 // the read release and the
236
237         // write lock gain so lets scan right with (write) lock coupling
238 currentNode = (Node)moveRight(currentNode, entry);
239
240         return currentNode;
241     }
242
243
244     protected void insert(NodeEntry entry, Stack nodeStack) throws JoftiException
245     {
246
247         Node currentNode = (Node)findNode(entry, nodeStack);
248         // ok so now we can insert in this node and we have a write lock on this
249 // node
250
251         doInsert(currentNode, entry, nodeStack);
252
253     }
254
255
256     private void doInsert(Node currentNode, NodeEntry entry, Stack nodeStack)
257             throws JoftiException
258     {
259
260         // we should now have the right node
261 Object [] temp = currentNode.insertEntry(entry);
262
263         // see if we need to split
264 if (currentNode.isUnderFull())
265         {
266             // no need to split so we can return here
267 LockManager.releaseLock(currentNode, LockManager.WRITE_LOCK);
268         } else
269         {
270             // split the node
271 Node newNode = currentNode.splitNode(temp);
272
273             // set the link node for the new node to be
274 // the current node's link node
275 newNode.setLinkNode(currentNode.getLinkNode());
276
277             // create the new index node key
278 IndexNodeEntry newEntry = constructKey(newNode);
279             newEntry.setValue(newNode.getRightValue());
280
281             // create a link node the new node
282 NodeLink newLink = new NodeLink();
283             newLink.setNode(newNode);
284             // set up current node to point to new node - but no new node in
285 // parent yet
286 currentNode.setLinkNode(newLink);
287             
288             // current node is now sorted out and new node is populated
289 // now we have to insert the new node in the parent
290 // no one can read into current or new node as yet as write lock
291 // still
292 // in effect
293 Node oldNode = currentNode;
294             nodes++;
295             // see if we are at the top of the stack
296 if (nodeStack.isEmpty())
297             {
298
299                 IndexNode newRoot = factory.createIndexNode();
300
301                 // these must be inserted this way round
302 newRoot.insertEntry(newEntry);
303
304                 // create the new index node key
305 IndexNodeEntry originalEntry = constructKey(oldNode);
306                 originalEntry.setValue(oldNode.getRightValue());
307
308                 newRoot.insertEntry(originalEntry);
309
310                 //set new right value
311 newRoot.setRightValue(newEntry.getValue());
312
313                 rootNode = newRoot;
314                 LockManager.releaseLock(oldNode, LockManager.WRITE_LOCK);
315             } else
316             {
317                 currentNode = (Node) nodeStack.pop();
318                 // acquire a lock on the parent here
319 LockManager.acquireLock(currentNode, LockManager.WRITE_LOCK);
320                 // look through parents to make sure we can insert in the right
321 // place
322 currentNode = (Node)moveRight(currentNode, newEntry);
323
324                 LockManager.releaseLock(oldNode, LockManager.WRITE_LOCK);
325
326                 // we have a lock on the current node so lets insert it
327 doInsert(currentNode, newEntry, nodeStack);
328
329             }
330
331         }
332     }
333
334
335     private Node moveRight(Node currentNode, NodeEntry value)
336             throws JoftiException
337     {
338         boolean rightnode = false;
339         //scan along the level looking for a node whose right value
340 // is greater then the value we are looking for.
341 //we do this using lock coupling as we need to be
342 // sure the nodes are not altered as we move right
343 while (!rightnode)
344         {
345             // we have found the node we are looking for
346 if (currentNode.getRightValue().compareTo(value.getValue()) >= 0)
347             {
348                 rightnode = true;
349
350             } else
351             {
352                 // get the next node from the link node
353 // we cannot go further right as there should always be
354 // a max value set
355 Node nextNode = (Node)currentNode.getLinkNode().getNode();
356
357                 LockManager.acquireLock(nextNode, LockManager.WRITE_LOCK);
358                 // we have locks on both current and next node here
359 // if deleted we should set the next node link on the current
360 // node
361 // while we are scanning through it
362 while (nextNode.isDeleted())
363                 {
364                     // we have to set the next link of current node to be the
365 // next
366 // nodes one to free up the node
367 currentNode.setLinkNode(nextNode.getLinkNode());
368                     LockManager.releaseLock(nextNode, LockManager.WRITE_LOCK);
369                     nextNode = (Node)currentNode.getLinkNode().getNode();
370                     LockManager.acquireLock(nextNode, LockManager.WRITE_LOCK);
371                 }
372                 // now we can release the current Node
373 LockManager.releaseLock(currentNode, LockManager.WRITE_LOCK);
374                 // set this node to be current node in readiness for testing
375 // in while loop
376 currentNode = nextNode;
377             }
378         }
379         // ok so we have found the a node that has a bigger right value
380 // lets return here
381 return currentNode;
382     }
383
384
385     private Object scanNode(Comparable value, Node startNode)
386             throws JoftiException
387     {
388         Node currentNode = startNode;
389
390         // this is a split node as we expect to be in the right node
391 // but the high value is too low so we need to return the pointer to the
392 // next node instead
393 if (currentNode.getRightValue().compareTo(value) < 0)
394         {
395
396             // this is not lock coupled as we are using read locks here
397 // just to test one node at a time
398 NodeLink nodeLink = currentNode.getLinkNode();
399
400             LockManager.releaseLock(currentNode, LockManager.READ_LOCK);
401
402             LockManager.acquireLock((Node)nodeLink.getNode(), LockManager.READ_LOCK);
403
404             return nodeLink;
405         } else
406         {
407             // try and get the containing node from this index node
408 Node nextNode = ((IndexNode) currentNode).getContainingNode(value);
409
410             LockManager.releaseLock(currentNode, LockManager.READ_LOCK);
411
412             LockManager.acquireLock(nextNode, LockManager.READ_LOCK);
413
414             return nextNode;
415
416         }
417     }
418
419
420     /**
421      * <p>
422      * Used to find the node (if any) containing the value.
423      * </p>
424      * <p>
425      * acquires read lock on the treeEntryLock
426      * </p>
427      * @param value - value to find
428      * @return
429      * @throws JoftiException
430      */
431     public INode search(Comparable value) throws JoftiException
432     {
433         LockManager.acquireRWLock(treeEntryLock, LockManager.READ_LOCK);
434         try {
435                 return realSearch(value, rootNode);
436         }finally{
437             LockManager.releaseRWLock(treeEntryLock, LockManager.READ_LOCK);
438         }
439     }
440
441     
442     
443     /**
444      * <p>
445      * Used to test if the tree contains a value.
446      * </p>
447      * <p>
448      * acquires a read lock on the treeEntryLock
449      * </p>
450      * @param value to test
451      * @return
452      * @throws JoftiException
453      */
454     
455     
456     public boolean containsDirect(Comparable value) throws JoftiException{
457         
458         LockManager.acquireRWLock(treeEntryLock, LockManager.READ_LOCK);
459         
460         try{
461             Node currentNode = rootNode;
462             LockManager.acquireLock(currentNode, LockManager.READ_LOCK);
463
464             // while not a leaf node scan through tree and record path
465 while (!(currentNode.isLeaf()))
466             {
467                 // will either return a child node or a link node
468
469                 Object returnNode = scanNode(value, currentNode);
470                
471                 // if a link node then we try and scan the node pointed to by the
472 // link
473 if (returnNode instanceof NodeLink)
474                 {
475                     currentNode = (Node)((NodeLink) returnNode).getNode();
476                 } else
477                 {
478                     currentNode = (Node) returnNode;
479                 }
480
481             }
482             // repeat this loop until we arrive at a leaf
483 Node tempNode = scanLeafNode(currentNode, value);
484             boolean contains =false;
485             
486             // see if we actually have the value in our node
487 if (tempNode != null && (((Leaf)tempNode).getEntry(value) != null)){
488                 contains =true;;
489             }
490             
491           
492             
493             // release the node lock
494 LockManager.releaseLock(tempNode, LockManager.READ_LOCK);
495             
496             // return the val
497 return contains;
498                    
499         }finally{
500             
501                 LockManager.releaseRWLock(treeEntryLock, LockManager.READ_LOCK);
502             
503             }
504         
505     }
506
507
508   
509     protected Collection getAttributesDirect(Comparable value)
510             throws JoftiException {
511         Collection col = new ArrayList ();
512
513         LockManager.acquireRWLock(treeEntryLock, LockManager.READ_LOCK);
514
515         try {
516             Node currentNode = rootNode;
517             LockManager.acquireLock(currentNode, LockManager.READ_LOCK);
518
519             // while not a leaf node scan through tree and record path
520 while (!(currentNode.isLeaf())) {
521                 // will either return a child node or a link node
522
523                 Object returnNode = scanNode(value, currentNode);
524
525                 // if a link node then we try and scan the node pointed to by
526 // the
527 // link
528 if (returnNode instanceof NodeLink) {
529                     currentNode = (Node) ((NodeLink) returnNode).getNode();
530                 } else {
531                     currentNode = (Node) returnNode;
532                 }
533
534             }
535             // repeat this loop until we arrive at a leaf
536 Node tempNode = scanLeafNode(currentNode, value);
537
538             if (tempNode == null) {
539                 return col;
540             } else {
541                 try {
542                     // if no matching value in node it should be in then just
543 // return an
544 // empty map
545 LeafNodeEntry val = ((Leaf) tempNode).getEntry(value);
546
547                     if (val == null || val.getUniqueIdSet() == null
548                             || val.getUniqueIdSet().isEmpty()) {
549
550                         return col;
551                     } else {
552                         // put all the matching keys into the map
553 // get the attributes
554 KeyValueObject attribWrapper = null;
555                         try {
556                             attribWrapper = (KeyValueObject) val.getValue();
557                         } catch (ClassCastException t) {
558                             throw new JoftiException(
559                                     "key dimension must only contain KeyValueObjects");
560                         }
561
562                         Set tempSet = attribWrapper.getAttributes().entrySet();
563                         Iterator other = tempSet.iterator();
564
565                         for (int j = tempSet.size(); j > 0; j--) {
566                             Map.Entry entry = (Map.Entry ) other.next();
567                             Object tempVal = entry.getValue();
568                             if (tempVal.getClass().isArray()) {
569                                 int size = Array.getLength(tempVal);
570                                 for (int i = 0; i < size; i++) {
571                                     Object inner = Array.get(tempVal, i);
572                                     col.add(new ValueObject(((Integer ) entry
573                                             .getKey()).intValue(),
574                                             (Comparable ) inner));
575                                 }
576                             } else {
577                                 col.add(new ValueObject(((Integer ) entry
578                                         .getKey()).intValue(),
579                                         (Comparable ) entry.getValue()));
580                             }
581                         }
582
583                     }
584                 } finally {
585                     // release the node lock
586 LockManager.releaseLock(tempNode, LockManager.READ_LOCK);
587                 }
588             }
589
590         } finally {
591
592             LockManager.releaseRWLock(treeEntryLock, LockManager.READ_LOCK);
593
594         }
595         return col;
596
597     }
598
599
600 /**
601  * Optimized matching method that uses direct matching in the tree instead of intermediate ResulNode wrapping the results.
602  *
603  * @param value
604  * @param map
605  * @param valueReturn
606  * @return
607  * @throws JoftiException
608  */
609 protected OpenHashMap matchDirect(Comparable value, OpenHashMap map, final Object valueReturn) throws JoftiException{
610     
611     LockManager.acquireRWLock(treeEntryLock, LockManager.READ_LOCK);
612     
613     try{
614         Node currentNode = rootNode;
615         LockManager.acquireLock(currentNode, LockManager.READ_LOCK);
616
617         // while not a leaf node scan through tree and record path
618 while (!(currentNode instanceof Leaf))
619         {
620             // will either return a child node or a link node
621
622             Object returnNode = scanNode(value, currentNode);
623            
624             // if a link node then we try and scan the node pointed to by the
625 // link
626 if (returnNode instanceof NodeLink)
627             {
628                 currentNode = (Node)((NodeLink) returnNode).getNode();
629             } else
630             {
631                 currentNode = (Node) returnNode;
632             }
633
634         }
635         // repeat this loop until we arrive at a leaf
636 Node tempNode = scanLeafNode(currentNode, value);
637         
638         // we have to return an OpenHashMap here
639 if (tempNode == null) {
640             if (map == null){
641                 return new OpenHashMap(1);
642             }else{
643                 return map;
644             }
645         }
646         // get the results
647
648        try {
649         LeafNodeEntry val = ((Leaf)tempNode).getEntry(value);
650            
651         
652         if (val !=null){
653              
654             // this is cached call for subsequent access to the set
655 Object [] tempSet = val.uniqueIdSet.toArray();
656             
657             int setLength = tempSet.length;
658              // make the map initially big enough to hold the length - so no resize is needed
659 // this is 2x initial size - see openHashMap for docs
660 if (map == null){
661                  map = new OpenHashMap(setLength*2,0.00f,0.5f);
662                  // add all elements from set
663
664                  for (int i=setLength-1;i>=0;i--) {
665                      
666                      map.put(tempSet[i],valueReturn);
667                  }
668              } else{
669                 // make sure the map can enlarge to need no resize
670 map.ensureCapacity(map.size() + setLength);
671                  
672                  // add in value if it does not already contain it
673 for (int i=setLength-1;i>=0;i--) {
674                     Object temp = tempSet[i];
675                      if (! map.containsKey(temp)){
676                          map.put(temp,valueReturn);
677                      }
678                  }
679              }
680             
681         }else{
682             // return a minimum sized map
683 if (map == null){
684                 map = new OpenHashMap(1);
685             }
686         }
687         
688         // release lock
689 } finally {
690         LockManager.releaseLock(tempNode, LockManager.READ_LOCK);
691        }
692         return map;
693         
694
695         
696     }finally{
697         
698             LockManager.releaseRWLock(treeEntryLock, LockManager.READ_LOCK);
699         
700         }
701     
702 }
703
704     
705     private INode realSearch(Comparable value, Node currentNode) throws JoftiException
706     {
707         // first acquire a read lock on the root node
708 LockManager.acquireLock(currentNode, LockManager.READ_LOCK);
709
710         // while not a leaf node scan through tree and record path
711 while (!(currentNode instanceof Leaf))
712         {
713             // will either return a child node or a link node
714
715             Object returnNode = scanNode(value, currentNode);
716            
717             // if a link node then we try and scan the node pointed to by the
718 // link
719 if (returnNode instanceof NodeLink)
720             {
721                 currentNode = (Node)((NodeLink) returnNode).getNode();
722             } else
723             {
724                 currentNode = (Node) returnNode;
725             }
726
727         }
728         // repeat this loop until we arrive at a leaf
729 Node tempNode = scanLeafNode(currentNode, value);
730         INode resultNode = new ResultNode(tempNode);
731         
732         // we should have a read lock here and a leaf value with a containing
733 // range that is closest to our desired value
734 LockManager.releaseLock(tempNode, LockManager.READ_LOCK);
735         return resultNode;
736     }
737
738
739     private Node scanLeafNode(Node currentNode, Comparable value)
740             throws JoftiException
741     {
742         boolean rightnode = false;
743         while (!rightnode)
744         {
745             // this is true if any of the entries are >= the value
746 // we are looking for
747 if (currentNode.contains(value))
748             {
749                 rightnode = true;
750
751             } else
752             {
753                 // otherwise scan along the nodes until we find a node that
754 // may contain our value - no lock coupling here
755 Node nextNode = (Node)currentNode.getLinkNode().getNode();
756
757                 LockManager.releaseLock((Node)currentNode, LockManager.READ_LOCK);
758
759                 LockManager.acquireLock((Node)nextNode, LockManager.READ_LOCK);
760
761                 currentNode = nextNode;
762             }
763         }
764         // ok so we have found the node we are looking for
765 return currentNode;
766     }
767
768
769     private IndexNodeEntry constructKey(Node childNode)
770     {
771         IndexNodeEntry nodeKey = factory
772                 .createIndexNodeEntry();
773         nodeKey.setValue(childNode.getRightValue());
774         nodeKey.setChildNode(childNode);
775         return nodeKey;
776     }
777
778
779     /**
780      * <p>
781      * Removes an entry from the tree that matches the {@link NodeEntry}.
782      * </p>
783      * <p>
784      * acquires a readlock on the treeEntryLock.
785      * </p>
786      * @param entry the entry to remove.
787      * @throws JoftiException
788      */
789     public void removeEntry(NodeEntry entry) throws JoftiException
790     {
791         Stack nodeStack = new Stack ();
792
793         LockManager.acquireRWLock(treeEntryLock, LockManager.READ_LOCK);
794         try {
795             nodeStack.push(rootNode);
796             removeEntry(entry, nodeStack);
797             entries.decrementAndGet();
798         }finally{
799         
800             LockManager.releaseRWLock(treeEntryLock, LockManager.READ_LOCK);
801         
802         }
803             if (rootNode.getEntryNumber() == 1){
804                 collapseRoot();
805             }
806         }
807
808
809     private void collapseRoot() throws JoftiException{
810         LockManager.acquireRWLock(treeEntryLock, LockManager.WRITE_LOCK);
811         
812         // we need to make sure that no other threads are in the
813 // tree in order to do this collapse
814 try {
815             
816             while (rootNode instanceof IndexNode && rootNode.getEntryNumber() ==1){
817                 rootNode = ((IndexNodeEntry)rootNode.getEntries()[0]).getChildNode();
818             }
819         }finally{
820             
821             LockManager.releaseRWLock(treeEntryLock, LockManager.WRITE_LOCK);
822         
823         }
824     }
825     private void removeEntry(NodeEntry entry, Stack nodeStack)
826             throws JoftiException
827     {
828         Node currentNode = findNode(entry, nodeStack);
829         // ok so now we can delete in this node and we have a write lock on this
830 // node
831
832         doRemove(currentNode, entry, nodeStack);
833     }
834
835
836     private void doRemove(Node currentNode, NodeEntry entry, Stack nodeStack)
837             throws JoftiException
838     {
839
840         //we should now have the right node
841 // lets delete the entry
842
843         Comparable oldRightValue = currentNode.getRightValue();
844         boolean deleted = currentNode.deleteEntry(entry);
845
846         // if we did not delete a value or we are root or the right value of the
847 // node
848 // was not changed we can just release the lock and return
849 if (nodeStack.isEmpty() || !deleted
850                 || (currentNode.getRightValue().compareTo(oldRightValue) == 0))
851         {
852             
853             LockManager.releaseLock((Node)currentNode, LockManager.WRITE_LOCK);
854
855         } else
856         {
857             // construct an index entry so we can find the correct parent node
858 // for the value we have just deleted
859 IndexNodeEntry tempEntry = null;
860             
861             if (entry instanceof IndexNodeEntry){
862                 tempEntry = (IndexNodeEntry)entry;
863             }else{
864                 tempEntry = factory
865                         .createIndexNodeEntry();
866                 tempEntry.setValue(oldRightValue);
867             }
868
869             // we have deleted all the values from the node
870 if (currentNode.isEmpty())
871             {
872                 
873                 // set a min right value so the scans will always go past it
874 currentNode.setRightValue(MIN_RIGHT_VALUE);
875                 nodes --;
876 // we need to mark node for deletion
877 currentNode.setDeleted(true);
878                 // and somehow reset right link from previous node
879 // this we do on insert and delete from nodes
880 // when the next node is marked as deleted - the lazy
881 // removal can result in some nodes hanging around a bit
882 // but we dot really care about that as it is
883 // not really feasible to do it any other way
884
885                 currentNode = obtainParentNode(currentNode, nodeStack,
886                         tempEntry);
887
888                 // we need to remove the same value from the parent node
889 doRemove(currentNode, tempEntry, nodeStack);
890             } else
891             {
892                 // must have deleted the right value of the node
893 // without deleting the node
894 // so we must step back up one level and reset the
895 // value on the parent possibly to the root
896
897                 // get the right parent
898 currentNode = obtainParentNode(currentNode, nodeStack,
899                         tempEntry);
900                 // update the right values as far as we need to
901 doUpdateIndexValue(currentNode, tempEntry, nodeStack);
902
903             }
904         }
905
906     }
907
908
909     
910     private Node obtainParentNode(Node currentNode, Stack nodeStack,
911             IndexNodeEntry tempEntry) throws JoftiException
912     {
913         Node childNode = (Node)currentNode;
914
915         // pop what was the parent on the way down off the stack
916 currentNode = (Node) nodeStack.pop();
917         
918         // acquire a lock on the parent here
919 LockManager.acquireLock(currentNode, LockManager.WRITE_LOCK);
920         //scan the parent and if needed right siblings to find the correct
921 // parent (could have moved in between the delete)
922
923         currentNode = (Node)moveRight(currentNode, tempEntry);
924         
925         // we have the correct parent so release the child here
926 LockManager.releaseLock((Node)childNode, LockManager.WRITE_LOCK);
927         return currentNode;
928     }
929
930
931     private void doUpdateIndexValue(Node currentNode, NodeEntry entry,
932             Stack nodeStack) throws JoftiException
933     {
934
935         Comparable oldRightValue = currentNode.getRightValue();
936
937         boolean updated = ((IndexNode) currentNode).updateEntry(entry);
938         if (nodeStack.isEmpty() || !updated
939                 || (currentNode.getRightValue().compareTo(oldRightValue) == 0))
940         {
941             // we just need to return here
942 LockManager.releaseLock((Node)currentNode, LockManager.WRITE_LOCK);
943
944         } else
945         {
946             currentNode = obtainParentNode(currentNode, nodeStack,
947                     (IndexNodeEntry) entry);
948
949             doUpdateIndexValue(currentNode, entry, nodeStack);
950         }
951
952     }
953
954
955     /*
956      * returns a String representation of the number of node and entries in the tree.
957      * */
958     public String toString()
959     {
960         StringBuffer buf = new StringBuffer ();
961         buf.append("number of nodes " + nodes + " number of entries "+ entries);
962         return buf.toString();
963     }
964     
965     /*
966      *This method needs to be called with caution as it will print out the entire node structure for the tree.
967      * If you include this in log statements it will cause the performance to degenerate significantly.
968      */
969     public String treeToString()
970     {
971         StringBuffer buf = new StringBuffer ();
972         buf.append(rootNode);
973         return buf.toString();
974     }
975     
976     /**
977      * @return the number entries in the tree
978      */
979     public long getEntries(){
980         return entries.get();
981     }
982
983     /**
984      * Returns the StoreManager if one is configured or null.
985      * @return
986      */
987     public IStoreManager getOverflowManager() {
988         return overflowManager;
989     }
990     
991     /**
992      * Sets an overflowManager in the tree to enable paging nodes to and from disk.
993      * @param overflowManager
994      */
995     public void setOverflowManager(IStoreManager overflowManager) {
996         this.overflowManager = overflowManager;
997     }
998     
999 }

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags