001: /*
002: * BTOperations.java
003: *
004: * Created on 26 May 2003, 08:53
005: */
006:
007: package com.jofti.btree;
008:
009: import java.util.ArrayList;
010: import java.util.Collection;
011: import java.util.LinkedHashMap;
012: import java.util.List;
013: import java.util.Map;
014:
015: import com.jofti.exception.JoftiException;
016: import com.jofti.locking.LockManager;
017: import com.jofti.util.OpenHashMap;
018:
019: /**
020: * Provides the group of low level operations that can be performed on the BTree. All
021: * operations on the BTree are performed by this class ,rather than directly on the tree.<p>
022: * <p>
023: * The class is essentially an encapsulation of the functional update,search, contains and remove variants used
024: * by the TreeIndex. The class does not retain a handle to any particular {@link BTree} and so the same instance can be used
025: * for the transactional {@link BTree} instances found in some Tree instances.
026: * </p>
027: *
028: *
029: * @author Steve Woodcock<br>
030: * @version 1.31
031: */
032: public class BTOperations {
033:
034: private static NodeFactory factory = NodeFactory.getInstance();
035:
036: /** Creates a new instance of BTOperations */
037: private BTOperations() {
038: }
039:
040: /** approximate size of average results returned for map sizing*/
041: private static int avRangeResults = 100;
042:
043: /**
044: * Inserts a value in the tree using a specific dimension. The key/value/dimension are
045: * grouped into a leaf node entry as a single entity. <p>
046: *
047: * This method delegates the insert to the {@link BTree} insert method.
048: * <p>
049: * @param tree - the tree to insert the value into<br>
050: * @param key - the key to use as the unique id<br>
051: * @param object - the value to be inserted into the tree. This must be Comparable.<br>
052: * @param dimension - the dimension that this value is part of.<br>
053: * <br>
054: * @throws JoftiException a wrapping exception to trap errors in the tree.
055: */
056: public static void insertValue(BTree tree, Comparable key,
057: Comparable object, int dimension) throws JoftiException {
058:
059: LeafNodeEntry entry = factory.createLeafNodeEntry(key,
060: new ValueObject(dimension, object));
061: tree.insert(entry);
062: }
063:
064: /**
065: * Inserts a key and the object attributes in the tree using a specific key dimension. The key/attributes/dimension are
066: * grouped into a leaf node entry. <p>
067: *
068: * This method delegates the insert to the BTree insert method.
069: * <p>
070: * @param tree - the tree to insert the value into<br>
071: * @param key - the key to use as the unique id<br>
072: * @param object - the value to be inserted into the tree. This must be Comparable.<br>
073: * @param dimension - the dimension that this value is part of.<br>
074: * <br>
075: * @throws JoftiException a wrapping exception to trap errors in the tree.
076: */
077: public static void insertKeyValue(BTree tree, Comparable key,
078: Map attributes, int dimension) throws JoftiException {
079:
080: LeafNodeEntry entry = factory.createLeafNodeEntry(key,
081: new KeyValueObject(dimension, key, attributes));
082:
083: tree.insert(entry);
084: }
085:
086: /**
087: * Removes a particular uniqueId from the tree if it is indexed with that value and dimension. If the value
088: * exists but the uniqueId is not stored with the value then no remove is performed. Otherwise the
089: * the uniqueid is removed from the value's id set.
090: * <p>
091: * @param tree - the tree to operate on.<br>
092: * @param uniqueId - the uniqueId to remove<br>
093: * @param object - the value to look for in the tree<br>
094: * @param dimension - the dimension that the value is in.<br>
095: * @throws JoftiException
096: */
097: public static void removeValue(BTree tree, Object uniqueId,
098: Comparable object, int dimension) throws JoftiException {
099: removeValueObject(tree, uniqueId, new ValueObject(dimension,
100: object));
101: }
102:
103: /**
104: * Removes a particular uniqueId from the tree if it is indexed with that
105: * valueObject. If the value
106: * exists but the uniqueId is not stored with the value then no remove is performed. Otherwise the
107: * the uniqueid is removed from the value's id set.<p>
108: *
109: * @param tree - the tree to operate on.<br>
110: * @param uniqueId - the uniqueId to remove<br>
111: * @param object - the value to look for in the tree<br>
112: * @throws JoftiException
113: */
114:
115: public static void removeValueObject(BTree tree, Object uniqueId,
116: Comparable object) throws JoftiException {
117:
118: LeafNodeEntry entry = factory.createLeafNodeEntry(uniqueId,
119: object);
120: tree.removeEntry(entry);
121: }
122:
123: /**
124: * Retrieves the matching uniqueIds for a particular value and dimension (if any).
125: * Failure to find a match returns an empty Map.<p>
126: *
127: * @param tree - the tree to perform the search upon.<br>
128: * @param obj - the object to search for.<br>
129: * @param dimension - the dimension that the value is in.<br>
130: * @return the Map of results.<br>
131: * @throws JoftiException
132: *
133: */
134: public static Map match(BTree tree, Comparable obj, int dimension)
135: throws JoftiException {
136: return tree.matchDirect(new ValueObject(dimension, obj), null,
137: null);
138: }
139:
140: /**
141: * Retrieves the matching uniqueIds for a particular value and dimension (if any). The valueReturn object is used to specify what field alias we should
142: * be looking for against this ID.
143: * Failure to find a match returns an empty Map.<p>
144: *
145: * @param tree - the tree to perform the search upon.<br>
146: * @param obj - the object to search for.<br>
147: * @param dimension - the dimension that the value is in.<br>
148: * @param valueReturn - The alias value of the object to return or null if we do not want to indicate a return restriction.<br>
149: * @return the Map of results.<br>
150: * @throws JoftiException
151: *
152: */
153: public static Map match(BTree tree, Comparable obj, int dimension,
154: Object valueReturn) throws JoftiException {
155: return tree.matchDirect(new ValueObject(dimension, obj), null,
156: valueReturn);
157: }
158:
159: /**
160: * Retrieves the matching uniqueIds for a particular array of values and dimension (if any).
161: * Failure to find a match returns an empty Map.<p>
162: *
163: * @param tree - the tree to perofrm the search upon.<br>
164: * @param obj - the object to search for.<br>
165: * @param dimension - the dimension that the value is in.<br>
166: * @return the Map of results.<br>
167: * @throws JoftiException
168: *
169: */
170: public static Map match(BTree tree, Comparable[] obj, int dimension)
171: throws JoftiException {
172: return match(tree, obj, dimension, null);
173:
174: }
175:
176: /**
177: * Retrieves the matching uniqueIds for a particular array of values and dimension (if any).
178: * The alias is used to pecify which alis we should use for the id. Failure to find a match returns an empty Map.<p>
179: *
180: * @param tree - the tree to perform the search upon.<br>
181: * @param obj - the object array containing the objects to search for.<br>
182: * @param dimension - the dimension that the value is in.<br>
183: * @param alias - The alias value of the object to return or null if we do not want to indicate a return restriction.<br>
184: * @return the Map of results.<br>
185: * @throws JoftiException
186: *
187: */
188: public static Map match(BTree tree, Comparable[] obj,
189: int dimension, Object alias) throws JoftiException {
190:
191: OpenHashMap map = null;
192: for (int i = obj.length - 1; i >= 0; i--) {
193: map = tree.matchDirect(new ValueObject(dimension, obj[i]),
194: map, alias);
195: }
196: return map;
197: }
198:
199: /**
200: * Returns the keys that are mapped against the comparable value.
201: * @param tree
202: * @param obj
203: * @param dimension
204: * @return
205: * @throws JoftiException
206: */
207: public static Collection getKeyAttributes(BTree tree,
208: Comparable obj, int dimension) throws JoftiException {
209:
210: return tree
211: .getAttributesDirect(new ValueObject(dimension, obj));
212: }
213:
214: /**
215: * Checks if the tree contains a particular value in a dimension. This does not check if any
216: * uniqueIds are stored against the value.<p>
217: *
218: * @param tree - the tree to perform the search upon.<br>
219: * @param obj - the object to search for.<br>
220: * @param dimension - the dimension that the value is in.<br>
221: * @return the Map of results.<br>
222: * @throws JoftiException
223: */
224: public static boolean contains(BTree tree, Comparable obj,
225: int dimension) throws JoftiException {
226: return tree.containsDirect(new ValueObject(dimension, obj));
227:
228: }
229:
230: private static INode getContainingNode(BTree tree, Comparable obj,
231: int dimension) throws JoftiException {
232:
233: //first get the node we think the entry should be in
234: ValueObject temp = new ValueObject(dimension, obj);
235: INode result = (INode) tree.search(temp);
236: if (result == null) {
237: return null;
238: }
239: // now get the entry - is it exists from the node
240: LeafNodeEntry val = ((IResultNode) result).getEntry(temp);
241: if (val == null) {
242: return null;
243: } else {
244: return ((ResultNode) result).getDelegate();
245: }
246: }
247:
248: /**
249: * Gets a collection of all value/dimension matches in the tree for a specific uniqueid.
250: * This method is used when we have a uniqueId and no object left in the cache (due to expiry etc)
251: * and so the only alternative is a scan of the leaf nodes to find matches. This is very inefficient
252: * if there are a lot of values in the tree but some cache implementations leave us with no alternative, as there are
253: * no callbacks for some events.<p>
254: * @param tree - the Tree to search
255: * @param obj - the unique id to look for
256: * @param startDimension - the dimension where the key is by type.
257: * @return - a Collection of all the matching values that has the uniqueId
258: * @throws JoftiException
259: */
260: public static Collection getAllValuesForKey(BTree tree,
261: Comparable obj, int startDimension) throws JoftiException {
262: // get the start point in the tree for the key dimension in the tree
263: INode result = getContainingNode(tree, obj, startDimension);
264: if (result != null) {
265: // scan along the leaves if we find a key mapping
266: Collection col = getAllValuesInTree(tree, result, obj,
267: startDimension);
268: return col;
269:
270: } else {
271: // otherwise we should not have any entries ifthere is no key mapping
272: return new ArrayList();
273: }
274: }
275:
276: /**
277: * Gets a collection of all value/dimension matches in the tree for a specific uniqueid.
278: * This method is used when we have a unique and no object left in the cache (due to expiry etc)
279: * and so the only alternative is a scan of the leaf nodes to find matches. This is very inefficient
280: * if there are a lot of values in the tree but some caches leave us with no alternative, as there are
281: * no callbacks for some events.<p>
282: * @param tree - the Tree to search
283: * @param realNode - the initial node for the first value.
284: * @param obj - the unique id to look for
285: * @param startDimension - the dimension where the key is by type.
286: * @return - a Collection of all the matching values that has the uniqueId
287: * @throws JoftiException
288: */
289:
290: private static Collection getAllValuesInTree(BTree tree,
291: INode realNode, Comparable obj, int startDimension)
292: throws JoftiException {
293:
294: List resultList = new ArrayList();
295: // gives us the containing node of this value
296:
297: if (realNode != null) {
298:
299: // get a read lock on this node
300: try {
301: boolean foundInDimension = false;
302: boolean dimensionEnd = false;
303: LockManager.acquireLock((Node) realNode,
304: LockManager.READ_LOCK);
305: boolean notEnd = true;
306:
307: while (notEnd) {
308: Object[] entries = realNode.getEntries();
309: for (int i = 0; i < entries.length; i++) {
310: LeafNodeEntry entry = (LeafNodeEntry) entries[i];
311:
312: if (entry != BTree.MAX_LEAF_ENTRY) {
313: if (entry.getUniqueIdSet().contains(obj)
314: && ((ValueObject) entry.getValue())
315: .getDimension() == startDimension) {
316:
317: resultList.add(entry.getValue());
318: foundInDimension = true;
319: if (entries[entries.length - 1] != BTree.MAX_LEAF_ENTRY) {
320: break;
321: }
322: } else if (((ValueObject) entry.getValue())
323: .getDimension() > startDimension) {
324:
325: dimensionEnd = true;
326: break;
327: }
328:
329: } else {
330: notEnd = false;
331:
332: }
333: }
334: if (notEnd) {
335: INode nextNode = null;
336: if (foundInDimension || dimensionEnd) {
337:
338: nextNode = getLowestNodeForDimension(tree,
339: ++startDimension);
340:
341: foundInDimension = false;
342: dimensionEnd = false;
343: } else {
344: nextNode = realNode.getLinkNode().getNode();
345:
346: }
347:
348: LockManager.releaseLock((Node) realNode,
349: LockManager.READ_LOCK);
350: LockManager.acquireLock((Node) nextNode,
351: LockManager.READ_LOCK);
352:
353: realNode = nextNode;
354:
355: }
356: }
357:
358: } finally {
359: LockManager.releaseLock((Node) realNode,
360: LockManager.READ_LOCK);
361:
362: }
363: }
364:
365: return (Collection) resultList;
366:
367: }
368:
369: /**
370: * Gets a collection of all uniqueIds in tree for a specific dimension.<p>
371:
372: * @param tree - the Tree to search
373: * @param dimension - the dimension where the key is by type.
374: * @return - a Collection of all the matching values
375: * @throws JoftiException
376: */
377: public static Map getAllResultsForDimension(BTree tree,
378: int dimension) throws JoftiException {
379:
380: return range(tree, ValueObject.MIN_COMAPARBLE_VALUE,
381: ValueObject.MAX_COMAPARBLE_VALUE, dimension, true);
382:
383: }
384:
385: /**
386: * Gets the node containing the first entry for a dimension.<p>
387:
388: * @param tree - the Tree to search
389: * @param dimension - the dimension where the key is by type.
390: * @return - the starting node
391: * @throws JoftiException
392: */
393: public static INode getLowestNodeForDimension(BTree tree,
394: int dimension) throws JoftiException {
395: ValueObject temp = new ValueObject(dimension,
396: ValueObject.MIN_COMAPARBLE_VALUE);
397:
398: IResultNode result = (IResultNode) tree.search(temp);
399:
400: return ((ResultNode) result).getDelegate();
401: }
402:
403: /**
404: * Gets the node containing the last entry for a dimension.<p>
405:
406: * @param tree - the Tree to search
407: * @param dimension - the dimension where the key is by type.
408: * @return - the starting node
409: * @throws JoftiException
410: */
411: public static INode getHighestNodeForDimension(BTree tree,
412: int dimension) throws JoftiException {
413: ValueObject temp = new ValueObject(dimension,
414: ValueObject.MAX_COMAPARBLE_VALUE);
415:
416: IResultNode result = (IResultNode) tree.search(temp);
417:
418: return ((ResultNode) result).getDelegate();
419: }
420:
421: /**
422: * Gets all the uniqueIds that fall between the two objects for a dimension. If the startObj is NULL
423: * it is assumed that the lower range starts from the first value in the dimension. Similarly, if the endObj is NULL
424: * it is assumed the upper bound is the maximum value in the dimension. <p>
425:
426: * @param tree - the Tree to search
427: * @param startObj - the starting value for the range search
428: * @param endObj - the end value for the range search
429: * @param dimension - the dimension where the key is by type.
430: * @param inclusive - sets whether the range search should be inclusive of the start and end objects.
431: * @return - A Map of the results.
432: * @throws JoftiException
433: */
434: public static Map range(BTree tree, Comparable startObj,
435: Comparable endObj, int dimension, boolean inclusive)
436: throws JoftiException {
437:
438: return rangeArray(tree, startObj, endObj, dimension, dimension,
439: inclusive, null);
440: }
441:
442: /**
443: * Gets all the uniqueIds that fall between the two objects for a dimension. If the startObj is NULL
444: * it is assumed that the lower range starts from the first value in the dimension. Similarly, if the endObj is NULL
445: * it is assumed the upper bound is the maximum value in the dimension. <p>
446:
447: * @param tree - the Tree to search
448: * @param startObj - the starting value for the range search
449: * @param endObj - the end value for the range search
450: * @param dimension - the dimension where the key is by type.
451: * @param inclusive - sets whether the range search should be inclusive of the start and end objects.
452: * @param alias - passed back in the result map as the value to indicate what fields the key should filter on.
453: * @return - a Map of the results.
454: * @throws JoftiException
455: */
456: public static Map range(BTree tree, Comparable startObj,
457: Comparable endObj, int dimension, boolean inclusive,
458: Object alias) throws JoftiException {
459:
460: return rangeArray(tree, startObj, endObj, dimension, dimension,
461: inclusive, alias);
462: }
463:
464: private static Map rangeArray(BTree tree, Comparable startObj,
465: Comparable endObj, int dimension, int endDimension,
466: boolean inclusive, Object valueReturn)
467: throws JoftiException {
468:
469: // we use an OpenHashMap here as it has lower memory and better speed
470: // performance for larger numbers of results
471: final OpenHashMap map = new OpenHashMap(avRangeResults * 2,
472: 0.00f, 0.5f);
473:
474: if (startObj == null) {
475: startObj = ValueObject.MIN_COMAPARBLE_VALUE;
476: }
477: if (endObj == null) {
478: endObj = ValueObject.MAX_COMAPARBLE_VALUE;
479: }
480:
481: ValueObject startRange = new ValueObject(dimension, startObj);
482: ValueObject finishRange = new ValueObject(endDimension, endObj);
483:
484: // we do not need a lock on this node as it is a results node wrapper
485: IResultNode startNode = (IResultNode) tree.search(startRange);
486:
487: boolean end = false;
488:
489: while (!end) {
490: Object[] entries = startNode.getEntries();
491:
492: int tempLength = entries.length;
493:
494: // see if all are within range - we can short circuit some checks
495: if (entries[tempLength - 1] != BTree.MAX_LEAF_ENTRY
496: && ((LeafNodeEntry) entries[0]).value
497: .compareTo(startRange) > 0
498: && ((LeafNodeEntry) entries[tempLength - 1]).value
499: .compareTo(finishRange) < 0) {
500: for (int i = 0; i < tempLength; i++) {
501: LeafNodeEntry entry = (LeafNodeEntry) entries[i];
502:
503: Object[] tempSet = entry.uniqueIdSet.toArray();
504: final int length = tempSet.length;
505: map.ensureCapacity(map.size() + length);
506:
507: // has to be iterator
508: for (int j = length - 1; j >= 0; j--) {
509: map.put(tempSet[j], valueReturn);
510: }
511: }
512: } else {
513: // we need to look at all values
514: // change to int method of access
515: for (int i = 0; i < tempLength; i++) {
516: LeafNodeEntry entry = (LeafNodeEntry) entries[i];
517: if (entry != BTree.MAX_LEAF_ENTRY) {
518:
519: if (inclusive
520: && entry.value.compareTo(startRange) >= 0
521: && entry.value.compareTo(finishRange) <= 0) {
522:
523: Object[] tempSet = entry.uniqueIdSet
524: .toArray();
525: final int length = tempSet.length;
526: map.ensureCapacity(map.size() + length);
527:
528: // has to be iterator
529: for (int j = length - 1; j >= 0; j--) {
530: map.put(tempSet[j], valueReturn);
531: }
532:
533: } else if ((!inclusive)
534: && entry.value.compareTo(startRange) > 0
535: && entry.value.compareTo(finishRange) < 0) {
536:
537: Object[] tempSet = entry.uniqueIdSet
538: .toArray();
539: final int length = tempSet.length;
540:
541: map.ensureCapacity(map.size() + length);
542:
543: // has to be iterator
544: for (int j = length - 1; j >= 0; j--) {
545: map.put(tempSet[j], valueReturn);
546: }
547:
548: } else if (entry.value.compareTo(finishRange) > 0) {
549: // we are at the end
550:
551: end = true;
552: break;
553:
554: }
555: } else {
556: end = true;
557: break;
558: }
559:
560: }
561: }
562: if (!end) {
563:
564: INode tempNode = ((ResultNode) startNode).getDelegate();
565:
566: // we temporarily acquire a lock here so we can get the result
567: // node delegate
568: LockManager.acquireLock((Node) tempNode,
569: LockManager.READ_LOCK);
570:
571: // get the result node that is next node
572: try {
573: startNode = (IResultNode) startNode.getLinkNode()
574: .getNode();
575:
576: } finally {
577:
578: // do not lock couple here - and release the lock on the
579: // node
580: LockManager.releaseLock((Node) tempNode,
581: LockManager.READ_LOCK);
582: }
583:
584: }
585: }
586:
587: // update the current average result size
588: avRangeResults = (avRangeResults + map.size()) / 2;
589: return map;
590:
591: }
592:
593: /**
594: * Gets all the uniqueIds that are contained in the tree between two values irrespective of the dimension. If the startObj is NULL
595: * it is assumed that the lower range starts from the first value in the dimension. Similarly, if the endObj is NULL
596: * it is assumed the upper bound is the maximum value in the dimension. <p>
597:
598: * @param tree - the Tree to search
599: * @param startObj - the starting value for the range search
600: * @param endObj - the end value for the range search
601: * @param startdimension - the dimension of the startObj.
602: * @param enddimension - the dimension of the end Obj.
603: * @param inclusive - sets whether the range search should be inclusive of the start and end objects.
604: * @return - A Map of the results.
605: * @throws JoftiException
606: */
607: public static Map getSubTreeKeyValues(BTree tree,
608: Comparable startObj, Comparable endObj, int dimension,
609: int endDimension, boolean inclusive) throws JoftiException {
610: Map map = new LinkedHashMap();
611:
612: if (startObj == null) {
613: startObj = ValueObject.MIN_COMAPARBLE_VALUE;
614: }
615: if (endObj == null) {
616: endObj = ValueObject.MAX_COMAPARBLE_VALUE;
617: }
618:
619: ValueObject startRange = new ValueObject(dimension, startObj);
620: ValueObject finishRange = new ValueObject(endDimension, endObj);
621:
622: IResultNode startNode = (IResultNode) tree.search(startRange);
623:
624: boolean end = false;
625:
626: while (!end) {
627: Object[] entries = startNode.getEntries();
628: // change to int method of access
629: for (int i = 0; i < entries.length; i++) {
630: LeafNodeEntry entry = (LeafNodeEntry) entries[i];
631: if (entry != BTree.MAX_LEAF_ENTRY) {
632:
633: if (inclusive
634: && entry.value.compareTo(startRange) >= 0
635: && entry.value.compareTo(finishRange) <= 0) {
636:
637: Object[] tempSet = entry.getUniqueIdSet()
638: .toArray();
639: // has to be iterator
640: for (int j = 0; j < tempSet.length; j++) {
641: if (entry.getValue() instanceof ValueObject) {
642: Map tmpMap = getMapForDimension(
643: map,
644: new Integer(
645: ((ValueObject) entry
646: .getValue()).dimension));
647: tmpMap.put(tempSet[j], entry.value);
648: }
649: }
650:
651: } else if ((!inclusive)
652: && entry.value.compareTo(startRange) > 0
653: && entry.value.compareTo(finishRange) < 0) {
654:
655: Object[] tempSet = entry.getUniqueIdSet()
656: .toArray();
657: // has to be iterator
658: for (int j = 0; j < tempSet.length; j++) {
659: if (entry.getValue() instanceof ValueObject) {
660: Map tmpMap = getMapForDimension(
661: map,
662: new Integer(
663: ((ValueObject) entry
664: .getValue()).dimension));
665:
666: tmpMap.put(tempSet[j], entry.value);
667: }
668: }
669:
670: } else if (entry.value.compareTo(finishRange) > 0) {
671: //we are at the end
672:
673: end = true;
674: break;
675:
676: }
677: } else {
678: end = true;
679: break;
680: }
681:
682: }
683: if (!end) {
684:
685: INode tempNode = ((ResultNode) startNode).getDelegate();
686: LockManager.acquireLock((Node) tempNode,
687: LockManager.READ_LOCK);
688:
689: try {
690: startNode = (IResultNode) startNode.getLinkNode()
691: .getNode();
692:
693: } finally {
694:
695: //do not lock couple here
696: LockManager.releaseLock((Node) tempNode,
697: LockManager.READ_LOCK);
698: }
699:
700: }
701: }
702:
703: return map;
704:
705: }
706:
707: private static Map getMapForDimension(Map resultMap,
708: Integer dimension) {
709:
710: Map tempMap = (Map) resultMap.get(dimension);
711: if (tempMap == null) {
712: tempMap = new LinkedHashMap();
713: resultMap.put(dimension, tempMap);
714: }
715: return tempMap;
716:
717: }
718:
719: /**
720: * Gets all the uniqueIds that do not equal the object for a dimension. <p>
721:
722: * @param tree - the Tree to search
723: * @param obj - the value we want to exclude
724: * @param dimension - the dimension of the object.
725: * @return - the starting node
726: * @throws JoftiException
727: */
728: public static Map notEqual(BTree tree, Comparable obj,
729: int dimension, Object valueReturn) throws JoftiException {
730: OpenHashMap map = new OpenHashMap(avRangeResults * 2, 0.00f,
731: 0.5f);
732:
733: Comparable start = ValueObject.MIN_COMAPARBLE_VALUE;
734:
735: Comparable endObj = ValueObject.MAX_COMAPARBLE_VALUE;
736:
737: ValueObject startRange = new ValueObject(dimension, start);
738: ValueObject finishRange = new ValueObject(dimension, endObj);
739:
740: ValueObject actualValue = new ValueObject(dimension, obj);
741:
742: IResultNode startNode = (IResultNode) tree.search(startRange);
743: INode realNode = ((ResultNode) startNode).getDelegate();
744:
745: try {
746: LockManager.acquireLock((Node) realNode,
747: LockManager.READ_LOCK);
748:
749: boolean end = false;
750:
751: while (!end) {
752: Object[] entries = realNode.getEntries();
753:
754: for (int i = 0; i < entries.length; i++) {
755: LeafNodeEntry entry = (LeafNodeEntry) entries[i];
756: if (entry != BTree.MAX_LEAF_ENTRY) {
757: Comparable tempObj = entry.value;
758: if (tempObj.compareTo(startRange) >= 0
759: && tempObj.compareTo(finishRange) <= 0) {
760:
761: if (tempObj.compareTo(actualValue) != 0) {
762:
763: Object[] tempEntrySet = entry
764: .getUniqueIdSet().toArray();
765:
766: map.ensureCapacity(map.size()
767: + tempEntrySet.length);
768: Object retVal = valueReturn != null ? valueReturn
769: : null;
770:
771: for (int j = 0; j < tempEntrySet.length; j++) {
772: map.put(tempEntrySet[j], retVal);
773: }
774: }
775:
776: } else if (tempObj.compareTo(finishRange) > 0) {
777: //we are at the end
778:
779: end = true;
780: break;
781:
782: }
783:
784: } else {
785: end = true;
786: break;
787: }
788:
789: }
790: if (!end) {
791:
792: INode nextNode = realNode.getLinkNode().getNode();
793:
794: //do not lock couple here
795: LockManager.releaseLock((Node) realNode,
796: LockManager.READ_LOCK);
797: LockManager.acquireLock((Node) nextNode,
798: LockManager.READ_LOCK);
799:
800: realNode = nextNode;
801: }
802: }
803: } finally {
804: LockManager.releaseLock((Node) realNode,
805: LockManager.READ_LOCK);
806: }
807: return map;
808:
809: }
810:
811: }
|