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