Java > Open Source Codes > com > daffodilwoods > daffodildb > server > datasystem > btree > BTree


1 package com.daffodilwoods.daffodildb.server.datasystem.btree;
2
3 import com.daffodilwoods.daffodildb.server.datasystem.indexsystem.*;
4 import com.daffodilwoods.daffodildb.server.datasystem.interfaces.*;
5 import com.daffodilwoods.daffodildb.server.datasystem.persistentsystem.*;
6 import com.daffodilwoods.daffodildb.server.sql99.utils.*;
7 import com.daffodilwoods.daffodildb.utils.*;
8 import com.daffodilwoods.daffodildb.utils.byteconverter.*;
9 import com.daffodilwoods.daffodildb.utils.comparator.*;
10 import com.daffodilwoods.database.resource.*;
11 import com.daffodilwoods.database.utility.*;
12
13 /**
14  *
15  * <p>Title: BTree</p>
16  * <p>Description:BTree : BTree represents a complete Balanced Tree.Sometimes user of index system needs an iterator which can iterate on
17  * corresponding data in order. So keeping this requirement in mind index system returns an iterator which
18  * is known as IndexIterator.IndexIterator does it's job with the help of BTree.It gives all the
19  * functionality which u can expect like insert,update,delete,seeking etc.
20  </p>
21  */
22
23 public class BTree
24     implements _Index {
25
26   /**
27    * Comparator to compare BtreeKeys.Comparator is necessary for maintaing the elements in order.
28    */
29
30   private SuperComparator comparator;
31
32   /**
33    * Number of elements in BTree
34    */
35
36   private _IndexInformation indexInformation;
37
38   /**
39    * order of columns on which index is created
40    */
41
42   private boolean[] orderType;
43
44   /**
45    * whether duplicate key,value pairs can exist in BTree or not
46    */
47
48   public boolean DUPLICATEKEYSALLOWED = true;
49
50   /**
51    * characteristics of btree
52    */
53
54   private _BTreeCharacteristics btreeCharacteristics;
55
56   /**
57    * To provide new node or any existing node of Btree
58    */
59
60   private _NodeManager nodeManager;
61
62   /**
63    *
64    */
65
66   Object [] uniqueColumnReferences;
67
68
69   public BTree(SuperComparator comparator0,
70                _BTreeCharacteristics btreeCharacteristics0,
71                _NodeManager nodeManger0) throws DException {
72     comparator = comparator0;
73     btreeCharacteristics = btreeCharacteristics0;
74     nodeManager = nodeManger0;
75     nodeManager.setBTree(this);
76
77
78   }
79
80   public _IndexInformation getIndexInformation() throws DException {
81     return indexInformation;
82   }
83
84   /**
85    * Sets IndexInformation of Btree
86    *
87    * @param indexInformation0 IndexInformation of Btree
88    */
89
90   public void setIndexInformation(_IndexInformation indexInformation0) throws
91       DException {
92     indexInformation = indexInformation0;
93     orderType = indexInformation.getOrderOfColumns();
94     uniqueColumnReferences = new Object [2];
95     uniqueColumnReferences[0] = indexInformation.getColumnIndexes();
96     uniqueColumnReferences[1] = indexInformation.getColumns();
97   }
98
99   /**
100    * Facts And Terminology :
101    * 1. BTree Node : Node in which new pair should reside.
102    * 2.If pair is the very first pair for this BTree then create a node newNode and
103    * assign it as root node and insert in it.
104    *
105    * As we know that insert in btree is performed at ground level.So we must have to
106    * locate the ground node first.For this starting from rootNode we move downwards
107    * using binarysearch until we reach the appropriate ground node.
108    *
109    * Now create a new Btree Element with the key Value pair.
110    *
111    * Every Node has an array of it's elements.Elements in a node reside in the
112    * appropriate order.Insert in a BTreeNode means place the element in elements
113    * array at the appropriate location.
114    *
115    * In Case Of Breaking Of Node :
116    * Some times BTree Node is full means It has no space for new pair.In this case these steps
117    * are followed :
118    *
119    * 1. A new node is created by the BTree.
120    * 2. Shift all the right half elements in new node from the node pair should reside.Right Half elements
121    * means all those elements which are at right side of middle element and middle element also.
122    * 3. Compare the new pair with middle element.
123    * 4. After the comparison insert the new pair in appropriate node whether in BTree Node or New Node.
124    * 5. And Now insert the middle element in parent of BTree Node.
125    *
126    * Special handling is done in it for the nodes which are used in insert method
127    * if any spliting occures than we set a flag false for the used nodes so that
128    * they can't be removed while we are loading child nodes of splited non leaf node
129    * than during updateNodeMapping nodes can be removed from the map .
130    * Now after setting all information of that node its flag is reseted to true
131    * so that it can be removed from map now.
132    */
133
134   public _IndexKey insert(_DatabaseUser user, Object key, Object value) throws
135       DException {
136     BTreeNode btreeNode = null;
137     BTreeNode rootNode = null;
138     BTreeKey btKey = null;
139     int insertPosition = -1;
140     if ( (rootNode = nodeManager.getRootNode(user)) == null) {
141       btreeNode = rootNode = nodeManager.getNewNode(user);
142       BTreeElement element = new BTreeElement();
143       element.setCurrentNode(btreeNode);
144       rootNode.insertDummyElement(element);
145       btreeNode.setLevel( (short) 1);
146       btKey = new BTreeKey(btreeNode, 0);
147     }
148     else {
149       btKey = locateNode(user, key, value, rootNode);
150       btreeNode = btKey.getNode();
151     }
152     BTreeNode newRootNode = rootNode;
153     BTreeNode newNode = null;
154     BTreeNode rightNode = null;
155     /* done by kuldeep ... after 3.2*/
156     int posa = btreeNode.insert(user, key, value, btKey.getPosition());
157     if (posa != -1) {
158       nodeManager.updateSizeAndBTreeInfo(user, true, rootNode);
159       BTreeKey btreeKey = new BTreeKey();
160       btreeKey.setNodeAndPosition(btreeNode, posa);
161       return btreeKey;
162     }
163     BTreeKey temp = null;
164     boolean flag = true;
165     BTreeElement dummyElement, middleElement;
166     BTreeNode parentNode;
167     int splitPoint, cmp, pos;
168     int testElementCount ;
169     while (posa == -1) {
170       btreeNode.setIsNodeCanBeRemovedFromMap(false);
171       newNode = nodeManager.getNewNode(user);
172       newNode.setIsNodeCanBeRemovedFromMap(false);
173       newNode.setLevel(btreeNode.getLevel());
174
175       dummyElement = new BTreeElement();
176       dummyElement.setCurrentNode(btreeNode);
177       newNode.insertDummyElement(dummyElement);
178       splitPoint = getSplitPoint(btreeNode);
179       testElementCount = btreeNode.getElementCount() ;
180       middleElement = btreeNode.getElement(splitPoint, user);
181
182       shiftRightHalf(user, btreeNode, newNode, splitPoint);
183       cmp = comparator.compare(middleElement.getKey(), key);
184       pos = -1;
185       if (!flag) {
186         btreeNode.setLeafNode(false);
187         newNode.setLeafNode(false);
188       }
189       pos = cmp > 0 ? btreeNode.insert(user, key, value, -1) :
190           newNode.insert(user, key, value, -1);
191       if (!flag) {
192         BTreeNode nod = cmp > 0 ? btreeNode : newNode;
193         BTreeElement bt = nod.getElement(pos, user);
194         bt.updateChild(rightNode);
195         rightNode.setIsNodeCanBeRemovedFromMap(true);
196       }
197
198       parentNode = btreeNode.getParentNode(user);
199       boolean isParentNode = false;
200       if (parentNode == null) {
201         isParentNode = true;
202         newRootNode = parentNode = nodeManager.getNewNode(user);
203         newRootNode.setIsNodeCanBeRemovedFromMap(false);
204         parentNode.setLevel( (short) (btreeNode.getLevel() + 1));
205         BTreeElement element = new BTreeElement();
206         element.setCurrentNode(parentNode);
207         element.setChild(btreeNode);
208         parentNode.insertDummyElement(element);
209         parentNode.setLeafNode(false);
210       }
211       if (flag) {
212         flag = false;
213         temp = new BTreeKey();
214         if (cmp > 0){
215           if(pos < 0){
216          ;//// Removed By Program ** System.out.println("BTree.insert(user, key, value) pos ="+pos+" splitPoint="+splitPoint+" element count before spliting ="+testElementCount +" now count ="+btreeNode.getElementCount() +" middle elemten ="+middleElement);
217 }
218
219           temp.setNodeAndPosition(btreeNode, pos); // btreeNode.getElement(pos,user)
220 }
221         else
222           temp.setNodeAndPosition(newNode, pos); // newNode.getElement(pos,user);
223 }
224       if (DUPLICATEKEYSALLOWED && !isParentNode) {
225         insertPosition = parentNode.binarySearch(key);
226       }
227       key = middleElement.getKey();
228       value = middleElement.getValue();
229       btreeNode.setIsNodeCanBeRemovedFromMap(true);
230       btreeNode = parentNode;
231       posa = btreeNode.insert(user, key, value,
232                               isParentNode ? 0 : insertPosition);
233       if (posa == -1) {
234         rightNode = newNode;
235         rightNode.setIsNodeCanBeRemovedFromMap(false);
236       }
237       else {
238         BTreeElement ele = btreeNode.getElement(posa, user);
239         ele.updateChild(newNode);
240       }
241         newNode.setIsNodeCanBeRemovedFromMap(true);
242     }
243     rootNode = newRootNode;
244     newRootNode.setIsNodeCanBeRemovedFromMap(true);
245     nodeManager.updateSizeAndBTreeInfo(user, true, rootNode);
246     return temp;
247   }
248
249   /**
250    * if btree is Default then update the btree element
251    * with new{newKey,newValue} pair
252    * else Delete the old {key,value} pair and insert new pair.
253    * if both old and new {key,value} pairs are same,do nothing.
254    *
255    * if both old and new {key,value} pairs are same,do nothing.
256    *
257    * @param user _DatabaseUser
258    * @param oldKey old Btree key made of old values of index columns
259    * @param newKey new Btree key made of new values of index columns
260    * @param oldValue TableKey of Record Before Updation in File
261    * @param newValue TableKey of Record After Updation in File
262    * @throws DException
263    */
264
265   public void update(_DatabaseUser user, Object oldKey, Object newKey,
266                      Object oldValue, Object newValue) throws DException {
267     int cmp = comparator.compare(oldKey, newKey);
268     if (cmp == 0) {
269       if (oldValue == null && newValue == null)
270         return;
271       if (oldValue != null && oldValue.equals(newValue))
272         return;
273     }
274     BTreeNode rootNode = nodeManager.getRootNode(user);
275     BTreeKey obj = searchNode(rootNode, oldKey, oldValue);
276     BTreeKey updateKey = (BTreeKey) obj.clone();
277     BTreeNode btreenode = obj.getNode();
278     boolean flag = true;
279     if (next1(obj)) {
280       Object nextKey = obj.getKey();
281       if (comparator.compare(nextKey, newKey) > 0 &&
282           updateKey.getNode().hashCode() == obj.getNode().hashCode()) {
283         previous1(obj);
284         flag = true;
285       }
286       else
287         flag = false;
288     }
289
290     if (flag) {
291       if (previous1(obj)) {
292         Object previousKey = obj.getKey();
293         if (comparator.compare(previousKey, newKey) < 0 &&
294             updateKey.getNode().hashCode() == obj.getNode().hashCode()) {
295           update(user, btreenode, updateKey, oldKey, oldValue, newKey, newValue);
296           return;
297         }
298       }
299       else {
300         update(user, btreenode, updateKey, oldKey, oldValue, newKey, newValue);
301         return;
302       }
303     }
304
305     delete(user, updateKey, rootNode);
306     insert(user, newKey, newValue);
307   }
308
309   private void update(_DatabaseUser user, BTreeNode btreenode, BTreeKey obj,
310                       Object oldKey, Object oldValue, Object newKey,
311                       Object newValue) throws DException {
312     btreenode = getNode(user, btreenode.getNodeKey());
313     try {
314       btreenode.update(null, obj, newKey, newValue);
315     }
316     catch (DException ex) {
317       if (ex.getDseCode().equalsIgnoreCase("DSE2001")) {
318         delete(user, oldKey, oldValue);
319         insert(user, newKey, newValue);
320       }
321       else
322         throw ex;
323     }
324   }
325
326
327   /**
328    * Searches the position of {key,value} on Lowest level of Btree, If {key, value} pair found then
329    * deletes element having that key value pair from btree.otherwise throws exception that key value
330    * pair not found in Btree.
331    *
332    * @param key key of element which has to delete
333    * @param value value of element which has to delete
334    * @return BtreeKey which is deleted from Btree
335    */
336
337   public _IndexKey delete(_DatabaseUser user, Object key, Object value) throws
338       DException {
339     BTreeNode rootNode = nodeManager.getRootNode(user);
340     BTreeKey obj = searchNode(rootNode, key, value);
341     if (obj == null) {
342       String we = "";
343       Object key1 = null;
344       try {
345         CbCzufIboemfs[] handlers = nodeManager.getByteHandlers();
346         key1 = getObject(key, handlers, nodeManager.getColumnTypes());
347         we = P.print(key1);
348       }
349       catch (Exception E) {
350         we = "" + key1;
351       }
352       obj = searchNode(rootNode, key, value);
353       throw new DException("DSE2008", new Object [] {we, value});
354     }
355
356     return delete(user, obj, rootNode);
357   }
358
359   /**
360    * Gets node from which key is to be deleted, deletes key from node and updates total btree size.
361    *
362    * @param key key which is to be deleted
363    * @return btreekey which is deleted
364    */
365
366   public _IndexKey delete(_DatabaseUser user, _IndexKey key) throws DException {
367
368     return delete(user, (BTreeKey) key, nodeManager.getRootNode(user));
369   }
370
371   /**
372    * Searches the KEY-VALUE pair starting from the NODE. it has to return the BtreeKey having key value
373    * pair in any leaf node of btree.
374    * 1. it does binary search to get position of key in given node.
375    * 2. if it finds that key in given node then checks all elemnts in that node if key value pair of any
376    * first element matches then returns that btree key otherwise makes range of keys havings same key.
377    * then gets all child node of elements within this range.and continues this process for all child
378    * nodes.
379    *
380    * 3. if element not found in that node binary serach return position as a negative value.then gets
381    * the child node of key at position of absolut value of returned position.
382    *
383    *
384    * @param node : Begin from this node
385    * @param key : btree key which has to search
386    * @param value : btree value which has to search
387    * @return : BTreeKey retuns BtreeKey of given key value pair
388    */
389
390   /**
391    * Used while insertin a new pair.It returns the appropriate leaf node in which this pair should reside.
392    */
393
394   private BTreeKey locateNode(_DatabaseUser user, Object key, Object value,
395                               BTreeNode rootNode) throws DException {
396     BTreeNode node = rootNode;
397     BTreeNode locatedNode = null;
398     int pos = -1;
399     do {
400       if (node.getElementCount() < 2 && node.isLeaf()) {
401         return new BTreeKey(node, 0);
402       }
403       locatedNode = node;
404       pos = node.binarySearch(key);
405       if (pos < 0) {
406         pos = Math.abs(pos);
407       }
408       node = node.isLeaf() ? null : getNode(user, node.getChildNodeKey(pos));
409     }
410     while (node != null);
411     return new BTreeKey(locatedNode, pos);
412   }
413
414   public void showBTree() throws DException {
415     BTreeNode rootNode = nodeManager.getRootNode(null);
416     if (rootNode == null || rootNode.getElementCount() == 1) {
417          ;//// Removed By Program ** System.out.println("No Records In BTree");
418 return;
419     }
420     showBTree(rootNode, 0);
421   }
422
423
424   private void showBTree(BTreeNode rootNode, int j) throws DException {
425     if (rootNode == null)
426       return;
427     BTreeNode nod = rootNode.getParentNode(null);
428     try {
429     }
430     catch (NullPointerException ex) {
431
432     }
433     if (rootNode.getElementCount() == 0)
434       return;
435     /*if(nods[1] != null){
436        BTreeNode nodea = getNode(rootNode,1,true);
437        showBTree(nodea,j);
438            } */
439     for (int i = 0; i < rootNode.getElementCount(); i++) {
440       BTreeElement ele = rootNode.getElement(i, null);
441       if (ele != null) {
442         BTreeNode nodea = getNode(null, rootNode.getChildNodeKey(i));
443         showBTree(nodea, j);
444       }
445     }
446
447   }
448
449   /**
450    * In case of breaking of a node shifts the right half elements into new node.and maintains linked
451    * list among old and new node.
452    *
453    * @param oldNode old node from which elements has to shift
454    * @param newNode new node in which elements has to insert
455    * @param splitPoint splitpoint from where element of old node has to shift in new node.
456    */
457
458   private void shiftRightHalf(_DatabaseUser user, BTreeNode oldNode,
459                               BTreeNode newNode, int splitPoint) throws
460       DException {
461     int insertPosition = oldNode.isLeaf() ? splitPoint : splitPoint + 1;
462     int deletePosition = splitPoint - 1;
463     int endPosition = oldNode.getElementCount() - 1;
464     newNode.insertRange(oldNode.getElements(), insertPosition, endPosition);
465     if (!oldNode.isLeaf()) {
466       BTreeElement ele;
467       BTreeNode nd;
468       for (int i = insertPosition; i <= endPosition; i++) {
469         ele = oldNode.getElement(i, user);
470         nd = nodeManager.getNode(user, ele.getChildNodeKey());
471         if (nd != null) {
472           nd.setParentNode(newNode);
473         }
474       }
475       ele = oldNode.getElement(splitPoint, user);
476       nd = nodeManager.getNode(user, ele.getChildNodeKey());
477       if (nd != null) {
478         newNode.getElement(0, user).updateChild(nd); //Setting of child of the split Point Element of the splitted node into the dummy element of the new node
479 }
480     }
481     oldNode.deleteRange(0, deletePosition);
482     BTreeNode nextNode = oldNode.getNextNode(user);
483     if (nextNode != null) {
484       newNode.setNextNode(nextNode);
485       nextNode.setPreviousNode(newNode);
486     }
487     oldNode.setNextNode(newNode);
488     newNode.setPreviousNode(oldNode);
489   }
490
491   /**
492    * Method written below returns the position from where we have to split the node.
493    *
494    * Check the document "SplitPoint.doc"
495    *
496    * @param node : which is going to split
497    * @return : position from where splitting begins
498    */
499
500   private int getSplitPoint(BTreeNode node) throws DException {
501     int splitPoint = node.getSplitPoint();
502     int startPosition = splitPoint;
503     if (DUPLICATEKEYSALLOWED) {
504       int count = node.getElementCount();
505       Object key = node.getKey(startPosition);
506       int a;
507       int b;
508       while (true) {
509         a = startPosition + 1;
510
511         if (a >= count) {
512           startPosition = splitPoint;
513           b = splitPoint - 1;
514           while (b > 0 && comparator.compare(key, node.getKey(b)) == 0) {
515             startPosition--;
516             b--;
517           }
518           if (startPosition == 1) {
519             return splitPoint;
520           }
521           return startPosition;
522         }
523
524         startPosition++;
525
526         if (comparator.compare(key, node.getKey(a)) != 0) {
527           if (a == splitPoint + 1 &&
528               comparator.compare(key, node.getKey(splitPoint - 1)) != 0) {
529             return splitPoint;
530           }
531           return startPosition;
532         }
533       }
534     }
535     return startPosition;
536   }
537
538   /**
539    * Return Names of Columns on which BTree is maintained
540    */
541
542   public String [] getColumnNames() throws DException {
543     return indexInformation == null ? null : indexInformation.getColumns();
544   }
545
546   public int getHighestLevelofBtree() throws DException {
547     return nodeManager.getRootNode(null).getLevel();
548   }
549
550   /**
551    * returns comparator of BTree
552    */
553
554   public SuperComparator getComparator() {
555     return comparator;
556   }
557
558   /**
559    * Returns the first element of Btree which satisfies the condition.
560    *
561    * @param condition :
562    * @return : BTreeElement if found any appropriate element otherwise null.
563    */
564
565   public Object seekFromTopRelative(_IndexPredicate[] condition) throws
566       DException {
567     if (getSize() == 0)
568       return null;
569     /*
570          Done by kuldeep after 3.2
571      */
572     BTreeNode currentRootNode = nodeManager.getRootNode(null);
573     return currentRootNode == null ? null :
574         searchNode(currentRootNode, condition,
575                    new BTreeReader(btreeCharacteristics), true);
576   }
577
578   /**
579    * Returns the last element of Btree which satisfies the condition.
580    *
581    * @param condition :
582    * @return : BTreeElement if found any appropriate element otherwise null.
583    */
584
585   public Object seekFromBottomRelative(_IndexPredicate[] condition) throws
586       DException {
587     if (getSize() == 0)
588       return null;
589     BTreeNode currentRootNode = nodeManager.getRootNode(null);
590
591     if (currentRootNode == null)
592       return null;
593
594     return searchNode(currentRootNode, condition,
595                       new BTreeReader(btreeCharacteristics), false);
596   }
597
598   private int search(BTreeNode cluster, _IndexPredicate[] condition,
599                      _VariableValues reader, int low, int high, boolean flag) throws
600       DException {
601     if (condition == null)
602       return flag ? low : high;
603     int cmp = 0;
604     int position = -1;
605     int length = 0;
606     for (int i = 0; i < condition.length && condition[i] != null; i++, length++)
607       ;
608     Object object = null;
609     while (low <= high) {
610       int mid = (low + high) / 2;
611       object = cluster.getKey(mid);
612       ( (BTreeReader) reader).setValue(object);
613       cmp = evaluate1(condition, reader, length);
614       if (cmp > 0)
615         low = mid + 1;
616       else if (cmp < 0)
617         high = mid - 1;
618       else {
619         cmp = evaluate(condition, reader, length);
620         if (cmp == 0)
621           position = mid;
622         if (flag)
623           high = mid - 1;
624         else
625           low = mid + 1;
626       }
627     }
628     return position == -1 ? - (low - 1) : position;
629
630   }
631
632   /**
633    * returns First BTreeKey having given indexkey otherwise null
634    * @param indexKey key which has to seek
635    * @return First BTreeKey having given indexkey otherwise null
636    */
637
638   public Object seek(Object indexKey) throws DException {
639     if (getSize() == 0)
640       return null;
641     boolean isPartial = false;
642     if (getColumnNames().length == 1) {
643       if (indexKey instanceof Object [])
644         indexKey = ( (Object []) indexKey)[0];
645     }
646     else {
647       isPartial = ( (Object []) indexKey).length != getColumnNames().length;
648     }
649     BTreeNode currentRootNode = nodeManager.getRootNode(null);
650     if (currentRootNode == null ||
651         currentRootNode.isLeaf() && currentRootNode.getElementCount() < 2)
652       return null;
653     return searchNode(currentRootNode, indexKey, false, true, isPartial);
654   }
655
656   private int search(BTreeNode cluster, Object keyToSeek, int low, int high,
657                      boolean flag) throws DException {
658     int cmp = 0;
659     int position = -1;
660     Object object = null;
661     while (low <= high) {
662       int mid = (low + high) / 2;
663       object = cluster.getKey(mid);
664       cmp = comparator.compare(keyToSeek, object);
665       if (cmp > 0)
666         low = mid + 1;
667       else if (cmp < 0)
668         high = mid - 1;
669       else {
670         if (cmp == 0)
671           position = mid;
672         if (flag)
673           high = mid - 1;
674         else
675           low = mid + 1;
676       }
677     }
678     return position == -1 ? - (low - 1) : position;
679   }
680
681   /**
682    * returns Btreekey having given indexkey or if not found then it's next key . it searches the key
683    * downwards from the given currentkey.If there is no key having value equal or greater than indexkey
684    * then it returns null.
685    *
686    * @param key from where indexkey has to search
687    * @param indexKey which has to search
688    * @return Btreekey having given indexkey or if not found then it's next key
689    * @throws DException
690    */
691
692   public Object seekFromTopRelative(Object key, Object indexKey) throws
693       DException {
694     if (getSize() == 0)
695       return null;
696     indexKey = getColumnNames().length == 1 && indexKey instanceof Object [] ?
697         ( (Object []) indexKey)[0] : indexKey;
698     BTreeKey currentKey = (BTreeKey) key;
699     boolean flag = currentKey == null ? first(currentKey = new BTreeKey()) :
700         next(currentKey);
701     while (flag) {
702       if (comparator.compare(currentKey.getKey(), indexKey) >= 0)
703         return currentKey;
704       flag = next(currentKey);
705     }
706     return null;
707   }
708
709   /**
710    * returns Btreekey having given indexkey or if not found then it's previous key . it searches the key
711    * upwards from the given currentkey.If there is no key having value equal or less than indexkey
712    * then it returns null.
713    *
714    * @param key from where indexkey has to search
715    * @param indexKey which has to search
716    * @return BtreeKey having given indexkey or if not found then it's previous key
717    */
718
719   public Object seekFromBottomRelative(Object key, Object indexKey) throws
720       DException {
721     if (getSize() == 0)
722       return null;
723     indexKey = getColumnNames().length == 1 && indexKey instanceof Object [] ?
724         ( (Object []) indexKey)[0] : indexKey;
725     BTreeKey currentKey = (BTreeKey) key;
726     boolean flag = currentKey == null ? last(currentKey = new BTreeKey()) :
727         previous(currentKey);
728     while (flag) {
729       comparator.compare(currentKey.getKey(), indexKey);
730       if (comparator.compare(currentKey.getKey(), indexKey) <= 0) {
731         return currentKey;
732       }
733       flag = previous(currentKey);
734     }
735     return null;
736   }
737
738   private int evaluate(_IndexPredicate[] conditions, _VariableValues reader,
739                        int start) throws DException {
740     int cmp = 0;
741     for (int i = start, length = conditions.length; cmp == 0 && i < length; i++) {
742       cmp = conditions[i] == null ? 0 : conditions[i].run(reader).hashCode();
743       cmp = (orderType == null || orderType[i]) ? cmp : -cmp;
744     }
745     return cmp;
746   }
747
748   private int evaluate1(_IndexPredicate[] conditions, _VariableValues reader,
749                         int stopPosition) throws DException {
750     int cmp = 0;
751     for (int i = 0; cmp == 0 && i < stopPosition; i++) {
752       cmp = conditions[i].run(reader).hashCode();
753       cmp = (orderType == null || orderType[i]) ? cmp : -cmp;
754     }
755     return cmp;
756   }
757
758   /**
759    * 1. if top is true
760    *
761    * returns first Btreekey having given indexkey or if not found then it's next key. If there is no key
762    * having value equal or greater than indexkey then it returns null.
763    * 1. if top is false
764    *
765    * returns last Btreekey having given indexkey or if not found then it's previous key. If there is no
766    * key having value equal or less than indexkey then it returns null.
767    *
768    * @param indexKey which has to locate
769    * @param top direction in which key has to locate
770    * @return BtreeKey having given indexkey or if not found then it's next or previous key on the basis
771    * of given variable top.
772    */
773
774   public _IndexKey locateKey(Object indexKey, boolean top) throws DException {
775     if (getSize() == 0)
776       return null;
777     String [] columnmNames = getColumnNames();
778     boolean isPartial = false;
779     if (columnmNames.length == 1) {
780       if (indexKey instanceof Object [])
781         indexKey = ( (Object []) indexKey)[0];
782     }
783     else {
784       isPartial = ( (Object []) indexKey).length != columnmNames.length;
785     }
786     BTreeKey entry = null;
787     BTreeNode currentRootNode = nodeManager.getRootNode(null);
788
789     if (currentRootNode == null ||
790         currentRootNode.isLeaf() && currentRootNode.getElementCount() < 2)
791       return null;
792     entry = searchNode(currentRootNode, indexKey, true, top, isPartial);
793     if (entry.getPosition() <= 0)
794       return locateNode(entry, top);
795     return entry;
796   }
797
798   public _IndexKey insert(Object key, Object value) throws DException {
799     return this.insert(null, key, value);
800   }
801
802   public void update(Object oldKey, Object newKey, Object oldValue,
803                      Object newValue) throws DException {
804     update(null, oldKey, newKey, oldValue, newValue);
805   }
806
807   public _IndexKey delete(Object key, Object value) throws DException {
808     return this.delete(null, key, value);
809   }
810
811   public Object seekAbsolute(Object key, Object indexKey) throws DException {
812     if (getSize() == 0)
813       return null;
814     indexKey = getColumnNames().length == 1 && indexKey instanceof Object [] ?
815         ( (Object []) indexKey)[0] : indexKey;
816     BTreeKey currentKey = (BTreeKey) key;
817     boolean flag = currentKey == null ? first(currentKey = new BTreeKey()) :
818         next(currentKey);
819     while (flag) {
820         int comp = comparator.compare(currentKey.getKey(), indexKey);
821         if (comp == 0)
822           return currentKey;
823         else flag = comp > 0 ? false : next(currentKey);
824       }
825       return null;
826     }
827
828   public int getSize() {
829     return nodeManager.getSize();
830   }
831
832   /**
833    * Sets first key of btree in parameter key, To get key first we have to reach on leftmost leaf node,
834    * then first valid key of that node is required key, if there is no valid key in that node then first
835    * valid key of next node is required key, this process continues until we get key otherwise returns
836    * false.
837    *
838    * @param key sets first key of btree in key
839    * @return true if first key exists otherwise returns false
840    */
841
842   public boolean first(_IndexKey key0) throws DException {
843     if (getSize() == 0)
844       return false;
845     BTreeKey key = (BTreeKey) key0;
846     BTreeNode node = nodeManager.getRootNode(null);
847     if (node == null)
848       return false;
849     while (!node.isLeaf()) {
850       node = getNode(null, node.getChildNodeKey(0)); //node.getElement(0,null).getChild();
851 }
852     try {
853       int position = node.getFirstValidPosition();
854       key.setNodeAndPosition(node, position);
855       return true;
856     }
857     catch (DException ex) {
858       if (ex.getDseCode().equals("DSE2042") ||
859           ex.getDseCode().equals("DSE2043")) {
860         node = node.getNextNode(null);
861         while (node != null) {
862           try {
863             key.setNodeAndPosition(node, node.getFirstValidPosition());
864             return true;
865           }
866           catch (DException ex1) {
867             node = node.getNextNode(null);
868           }
869         }
870         return false;
871       }
872       throw ex;
873     }
874   }
875
876   /**
877    * sets next key of given btreekey , first it checks that given key exists at given location or not.
878    * if it exists then sets next valid key of this key in given key, if it does not exist then locates
879    * this key in btree, locate return this key or its next key, if it finds that key at any other
880    * location then returns its next key otherwise returns key got from locate key.
881    * @param btreeKey current key whose next key has to set in btreekey
882    * @return true if next key of current key exists otherwise returns false.
883    */
884
885   public boolean next(_IndexKey btreeKey0) throws DException {
886     if (getSize() == 0)
887       return false;
888     BTreeKey btreeKey = (BTreeKey) btreeKey0;
889     btreeKey.checkValidity();
890     if (btreeKey.getPosition() == 0) {
891       return next1(btreeKey);
892     }
893     Object oldKey = btreeKey.getOldkey();
894     Object oldValue = btreeKey.getOldValue();
895     BTreeElement element = null;
896     Object newValue = null;
897     try {
898       BTreeNode node = btreeKey.getNode();
899       if (node.isNodeRemovedFromMap())
900         node = nodeManager.getNode(null, node.getNodeKey());
901       newValue = node.getValue(btreeKey.getPosition());
902     }
903     catch (DException de) {
904       if (!de.getDseCode().equalsIgnoreCase("DSE2043"))
905         throw de; //This try - catch block is valid
906 }
907     if (oldValue.equals(newValue)) {
908       return next1(btreeKey);
909     }
910     else {
911
912       BTreeKey btreeKeyAfterLocate = (BTreeKey) locateKey(oldKey, true);
913
914
915       if (btreeKeyAfterLocate == null) {
916         return false;
917       }
918       Object newKey = btreeKeyAfterLocate.getKey();
919       newValue = btreeKeyAfterLocate.getValue();
920       btreeKey.setNodeAndPosition(btreeKeyAfterLocate.getNode(),
921                                   btreeKeyAfterLocate.getPosition());
922       if (comparator.compare(oldKey, newKey) != 0)
923         return true;
924
925       BTreeKey clonedKey = (BTreeKey) btreeKey.clone();
926       boolean foundOldRecord = false;
927       while (comparator.compare(oldKey, newKey) == 0) {
928         if (oldValue.equals(newValue)) {
929           foundOldRecord = true;
930           break;
931         }
932         if (next1(btreeKey) == false)
933           break;
934
935         newValue = btreeKey.getValue();
936         newKey = btreeKey.getKey();
937       }
938
939       if (foundOldRecord)
940         return next1(btreeKey);
941       else {
942         btreeKey.setNodeAndPosition(clonedKey.getNode(), clonedKey.getPosition());
943         return true;
944       }
945
946     }
947   }
948
949   private boolean next1(BTreeKey key) throws DException {
950     BTreeNode node = key.getNode();
951     try {
952       if (node.isNodeRemovedFromMap())
953         node = nodeManager.getNode(null, node.getNodeKey());
954       int position = node.getNextValidPosition(key.getPosition());
955
956       key.setNodeAndPosition(node, position);
957       return true;
958     }
959     catch (DException de) {
960
961       if (de.getDseCode().equals("DSE2042") || de.getDseCode().equals("DSE2043")) {
962         node = node.getNextNode(null);
963         while (node != null) {
964           try {
965             key.setNodeAndPosition(node, node.getFirstValidPosition());
966             return true;
967           }
968           catch (DException ex) {
969             node = node.getNextNode(null);
970           }
971         }
972         return false;
973       }
974       throw de;
975     }
976   }
977
978   /**
979    * Sets last key of btree in parameter key, To get key first we have to reach on rightmost leaf node,
980    * then last valid key of that node is required key, if there is no valid key in that node then last
981    * valid key of previous node is required key, this process continues until we get key otherwise
982    * returns false.
983    *
984    * @param key sets last key of btree in key
985    * @return true if last key exists otherwise returns false
986    */
987
988   public boolean last(_IndexKey key0) throws DException {
989     if (getSize() == 0)
990       return false;
991     BTreeKey key = (BTreeKey) key0;
992     BTreeNode node = nodeManager.getRootNode(null);
993     if (node == null)
994       return false;
995     while (!node.isLeaf()) {
996       node = getNode(null, node.getChildNodeKey(node.getElementCount() - 1)); //node.getElement(node.getElementCount()-1,null).getChild();
997 }
998     try {
999       int position = node.getLastValidPosition();
1000      key.setNodeAndPosition(node, position);
1001      return true;
1002    }
1003    catch (DException ex) {
1004      if (ex.getDseCode().equals("DSE2042") || ex.getDseCode().equals("DSE2043")) {
1005        node = node.getPreviousNode(null);
1006        while (node != null) {
1007          try {
1008            key.setNodeAndPosition(node, node.getLastValidPosition());
1009            return true;
1010          }
1011          catch (DException ex1) {
1012            node = node.getPreviousNode(null);
1013          }
1014        }
1015        return false;
1016      }
1017      throw ex;
1018    }
1019  }
1020
1021  /**
1022   * sets previous key of given btreekey , first it checks that given key exists at given location or not.
1023   * if it exists then sets previous valid key of this key in given key, if it does not exist then
1024   * locates this key in btree, locate return this key or its previous key, if it finds that key at any
1025   * other location then returns its previous key otherwise returns key got from locate key.
1026   *
1027   * @param btreeKey current key whose previous key has to set in btreekey
1028   * @return true if previous key of current key exists otherwise returns false.
1029   */
1030  public boolean previous(_IndexKey btreeKey0) throws DException {
1031    if (getSize() == 0)
1032      return false;
1033    BTreeKey btreeKey = (BTreeKey) btreeKey0;
1034    Object oldKey = btreeKey.getOldkey();
1035    Object oldValue = btreeKey.getOldValue();
1036    Object newValue = null;
1037    try {
1038      BTreeNode node = btreeKey.getNode();
1039      if (node.isNodeRemovedFromMap())
1040        node = nodeManager.getNode(null, node.getNodeKey());
1041      newValue = node.getValue(btreeKey.getPosition());
1042    }
1043    catch (DException de) {
1044      if (!de.getDseCode().equalsIgnoreCase("DSE2043"))
1045        throw de;
1046    }
1047    if (oldValue.equals(newValue))
1048      return previous1(btreeKey);
1049    else {
1050      BTreeKey btreeKeyAfterLocate = (BTreeKey) locateKey(oldKey, false);
1051      if (btreeKeyAfterLocate == null)
1052        return false;
1053      Object newKey = btreeKeyAfterLocate.getKey();
1054      newValue = btreeKeyAfterLocate.getValue();
1055      btreeKey.setNodeAndPosition(btreeKeyAfterLocate.getNode(),
1056                                  btreeKeyAfterLocate.getPosition());
1057      if (comparator.compare(oldKey, newKey) != 0)
1058        return true;
1059
1060      BTreeKey clonedKey = (BTreeKey) btreeKey.clone();
1061      boolean foundOldRecord = false;
1062      while (comparator.compare(oldKey, newKey) == 0) {
1063        if (oldValue.equals(newValue)) {
1064          foundOldRecord = true;
1065          break;
1066        }
1067        if (previous1(btreeKey) == false)
1068          break;
1069
1070        newValue = btreeKey.getValue();
1071        newKey = btreeKey.getKey();
1072      }
1073
1074      if (foundOldRecord)
1075        return previous1(btreeKey);
1076      else {
1077        btreeKey.setNodeAndPosition(clonedKey.getNode(), clonedKey.getPosition());
1078        return true;
1079
1080      }
1081    }
1082  }
1083
1084  private boolean previous1(BTreeKey key) throws DException {
1085    BTreeNode node = key.getNode();
1086    try {
1087      int position = 0;
1088      if (node.isNodeRemovedFromMap())
1089        node = nodeManager.getNode(null, node.getNodeKey());
1090      position = node.getPreviousValidPosition(key.getPosition());
1091      key.setNodeAndPosition(node, position);
1092      return true;
1093    }
1094    catch (DException de) {
1095      if (de.getDseCode().equals("DSE2042") || de.getDseCode().equals("DSE2043")) {
1096        node = node.getPreviousNode(null);
1097        while (node != null) {
1098          try {
1099            key.setNodeAndPosition(node, node.getLastValidPosition());
1100            return true;
1101          }
1102          catch (DException ex) {
1103            node = node.getPreviousNode(null);
1104          }
1105        }
1106        return false;
1107      }
1108      throw de;
1109    }
1110  }
1111
1112  public BTreeNode getRootNode() throws DException {
1113    return nodeManager.getRootNode(null);
1114  }
1115
1116  public _NodeManager getNodeManager() throws DException {
1117    return nodeManager;
1118  }
1119
1120  private BTreeKey getBTreeKey(BTreeNode node, int position) throws DException {
1121    BTreeKey bk = new BTreeKey();
1122    bk.setNodeAndPosition(node, position);
1123    return bk;
1124  }
1125
1126  private static Object getObject(Object bb, CbCzufIboemfs[] handlers,
1127                                  int[] columnTypes) throws DException {
1128    if (bb instanceof BufferRange) {
1129      return ( (BufferRange) bb).getNull() ? null :
1130          handlers[0].getObject( (BufferRange) bb, columnTypes[0]);
1131    }
1132    BufferRange[] bytes = (BufferRange[]) bb;
1133    Object [] values = new Object [bytes.length];
1134    for (int i = 0; i < bytes.length; i++)
1135      values[i] = bytes[i] == null ? null : bytes[i].getNull() ? null :
1136          handlers[i].getObject(bytes[i], columnTypes[i]).getObject();
1137    return values;
1138  }
1139
1140  protected BTreeNode getNode(_DatabaseUser user, Object childNodeKey) throws
1141      DException {
1142    return childNodeKey == null ? null : nodeManager.getNode(user, childNodeKey);
1143  }
1144
1145  public Object [] getUniqueColumnReference() throws DException {
1146    return uniqueColumnReferences;
1147  }
1148
1149  public int getTotalNumberOfClusterLoadedInMemory() {
1150    return ( (FileNodeManager) nodeManager).getTotalSizeOfNodeMapAndWeakNodeMap();
1151  }
1152
1153  public Object getObject(Object key) throws DException {
1154    CbCzufIboemfs[] handlers = nodeManager.getByteHandlers();
1155    return getObject(key, handlers, nodeManager.getColumnTypes());
1156  }
1157
1158  protected void finalize123() {
1159  }
1160
1161  /**
1162   * Simple search method which searches the key(which is always full) and value pair in the btree,first it starts searching from the root node
1163   * and move down to the leaf node.
1164   *
1165   * If the key is found in the leaf node it returns its position which is +ve integer value
1166   * and then it matches the value for that key and if it's value also matches it returns the located key
1167   * bt if the value doesn't match then searches the key in the pervious nodeand checks it value also if it matches
1168   * and returns the key if it satisfies both the criteria else searches in the next node accordingly and returns
1169   * respective key.
1170   * Case:If leaf node doesn't contains the required key:then in this case the position returned by binary search is
1171   * a -ve integer value and if the postion is negative it returns null.
1172   * @param rootNode BTreeNode rootNode of the given btree
1173   * @param key Object key to be searched in btree
1174   * @param value Object value to be found in btree
1175   * @return BTreeKey btree key with the node and position of the required key.
1176   */
1177
1178  private BTreeKey searchNode(BTreeNode rootNode, Object key, Object value) throws
1179      DException {
1180    BTreeNode node = rootNode;
1181    BTreeNode locatedNode = null;
1182    int pos = -1;
1183    int valToRet = -1;
1184    do {
1185      if (node.getElementCount() < 2 && node.isLeaf())
1186        return null;
1187      locatedNode = node;
1188      pos = node.binarySearch(key);
1189      valToRet = pos;
1190      if (pos < 0) {
1191        pos = Math.abs(pos);
1192      }
1193      node = node.isLeaf() ? null : getNode(null, node.getChildNodeKey(pos));
1194    }
1195    while (node != null);
1196
1197    if (valToRet < 0) // = removed while test cases of btree split point are failed.
1198 return null;
1199
1200    BTreeKey btreeKey = getBTreeKey(locatedNode, valToRet);
1201    if (!DUPLICATEKEYSALLOWED)
1202      return btreeKey;
1203    if (value.equals(btreeKey.getValue()))
1204      return btreeKey;
1205    BTreeKey searchKey = (BTreeKey) btreeKey.clone();
1206    while (next1(btreeKey)) {
1207      Object nextKey = btreeKey.getKey();
1208      if ( (comparator.compare(nextKey, key) == 0)) {
1209        if (value.equals(btreeKey.getValue())) {
1210          return btreeKey;
1211        }
1212      }
1213      else
1214        break;
1215    }
1216
1217    btreeKey = (BTreeKey) searchKey.clone();
1218    while (previous1(btreeKey)) {
1219      Object previousKey = btreeKey.getKey();
1220      if (comparator.compare(previousKey, key) == 0) {
1221        if (value.equals(btreeKey.getValue())) {
1222          return btreeKey;
1223        }
1224      }
1225      else
1226        break;
1227    }
1228    return searchKey;
1229  }
1230
1231  /**
1232   * Searches the key in the btree,first it strats searching from the root node
1233   * and move down to the leaf node.
1234   *
1235   * If the key is found in the leaf node it returns its position which is +ve integer value
1236   * and if the top variale is set to true then it moves to the previous node till the
1237   * same key is encountered and returns the previous most key as it is the top most key else if
1238   * same key is not there in the previous node then it breaks the loop and the loacted key is returned.
1239   *
1240   * if top is false then it searches for the same key in the next node and similarly continues searching in
1241   * the next nodes till the same key is encounterd and returns the right most key as it is the bottom most key else if
1242   * same key is not there in the next node then it breaks the loop and the loacted key is returned.
1243   *
1244   * Case:If leaf node doesn't contains the required key:then in this case the position returned by binary search is
1245   * a -ve integer value.
1246   * Top true:In this case also searching is done in the previous node first
1247   * but if no maching key is find in the previous node then it
1248   * searches in the next node for that key and else returns a new BTreeKey with the located node nad -ve position value
1249   * if locate is true else returns null
1250   *
1251   * Top false:In this case also searching is done in the next node first
1252   * but if no maching key is find in the next node then it
1253   * searches in the previous node for that key and else returns a new BTreeKey with the located node nad -ve position value
1254   * if locate is true else returns null.
1255   *
1256   * @param rootNode BTreeNode rootNode of the given btree
1257   * @param key Object key to be searched in btree
1258   * @param locate boolean if the exact key is not found then return the next key or previous key if locate
1259   * is true else return null
1260   * @param top boolean boolean which states if the key to searches shd be top most
1261   * of bottom most
1262   * @param isPartial boolean key to be searched is full or partial
1263   * @return BTreeKey btree key with the node and position of the required key.
1264   */
1265
1266  private BTreeKey searchNode(BTreeNode rootNode, Object key, boolean locate,
1267                              boolean top, boolean isPartial) throws DException {
1268    BTreeNode node = rootNode;
1269    BTreeNode locatedNode = null;
1270    int pos = -1;
1271    int valToRet = -1;
1272    do {
1273      locatedNode = node;
1274      pos = search(node, key, 1, node.getElementCount() - 1, top);
1275      valToRet = pos;
1276      if (pos < 0) {
1277        pos = Math.abs(pos);
1278      }
1279      node = node.isLeaf() ? null : getNode(null, node.getChildNodeKey(pos));
1280    }
1281    while (node != null);
1282
1283    if (!isPartial && valToRet < 0) { // = removed while test cases of btree split point are failed.
1284 return locate ? new BTreeKey(locatedNode, valToRet) : null;
1285    }
1286    else if (valToRet > 0) {
1287      BTreeKey btreeKey = getBTreeKey(locatedNode, valToRet);
1288
1289      BTreeKey searchKey = (BTreeKey) btreeKey.clone();
1290      if (top) {
1291        while (previous1(btreeKey)) {
1292          Object previousKey = btreeKey.getKey();
1293          if (! (comparator.compare(previousKey, key) == 0)) {
1294            next1(btreeKey);
1295            return btreeKey;
1296          }
1297        }
1298        return btreeKey;
1299      }
1300      else {
1301        btreeKey = (BTreeKey) searchKey.clone();
1302        while (next1(btreeKey)) {
1303          Object nextKey = btreeKey.getKey();
1304          if (! (comparator.compare(nextKey, key) == 0)) {
1305            previous1(btreeKey);
1306            return btreeKey;
1307          }
1308        }
1309        return btreeKey;
1310      }
1311    }
1312    else {
1313      BTreeKey btreeKey = getBTreeKey(locatedNode, Math.abs(valToRet));
1314      BTreeKey searchKey = (BTreeKey) btreeKey.clone();
1315      BTreeKey locatedKey = null;
1316      if (top) {
1317        while (previous1(btreeKey)) {
1318          Object previousKey = btreeKey.getKey();
1319          if (comparator.compare(previousKey, key) != 0)
1320            break;
1321          else
1322            locatedKey = (BTreeKey) btreeKey.clone();
1323        }
1324        if (locatedKey != null)
1325          return locatedKey;
1326        btreeKey = (BTreeKey) searchKey.clone();
1327        /*
1328            Here while is used earlier because we need to get next valid position and than compare it
1329            But now we replace it with if because we need to compare with only first next valid position
1330            if it doesn't match than we doesn't need to serach in more nodes
1331         */
1332
1333        if (next1(btreeKey)) {
1334          Object nextKey = btreeKey.getKey();
1335          if (comparator.compare(nextKey, key) == 0)
1336            return btreeKey;
1337        }
1338
1339        return locate ? new BTreeKey(locatedNode, valToRet) : null;
1340      }
1341      else {
1342        while (next1(btreeKey)) {
1343          Object nextKey = btreeKey.getKey();
1344          if (comparator.compare(nextKey, key) != 0)
1345            break;
1346          else
1347            locatedKey = (BTreeKey) btreeKey.clone();
1348        }
1349        if (locatedKey != null)
1350          return locatedKey;
1351        btreeKey = (BTreeKey) searchKey.clone();
1352        /*
1353                 Here while is used earlier because we need to get next valid position and than compare it
1354                 But now we replace it with if because we need to compare with only first next valid position
1355         if it doesn't match than we doesn't need to serach in more nodes
1356         */
1357
1358        if (previous1(btreeKey)) {
1359          Object previousKey = btreeKey.getKey();
1360          if (comparator.compare(previousKey, key) == 0)
1361            return btreeKey;
1362        }
1363        return locate ? new BTreeKey(locatedNode, valToRet) : null;
1364      }
1365    }
1366
1367  }
1368
1369  /**
1370   * Searches the key with the given condition in the btree,first it strats searching from the root node
1371   * and move down to the leaf node.
1372   *
1373   * If the key is found in the leaf node it returns its position which is +ve integer value
1374   * and if the top variale is set to true then it moves to the previous node till the
1375   * same key is encountered and returns the previous most key as it is the top most key else if
1376   * same key is not there in the previous node then it breaks the loop and the loacted key is returned.
1377   *
1378   * if top is false then it searches for the same key in the next node and similarly continues searching in
1379   * the next nodes till the same key is encounterd and returns the right most key as it is the bottom most key else if
1380   * same key is not there in the next node then it breaks the loop and the loacted key is returned.
1381   *
1382   * Case:If leaf node doesn't contains the required key:then in this case the postion returned by binary search is
1383   * a -ve integer value.
1384   * Top true:In this case also searching is done in the previous node first
1385   * but if no maching key is find in the previous node then it
1386   * searches in the next node for that key and else returns null.
1387   * Top false:In this case also searching is done in the next node first
1388   * but if no maching key is find in the next node then it
1389   * searches in the previous node for that key and else returns null.
1390   *
1391   * @param rootNode BTreeNode rootNode
1392   * @param condition _IndexPredicate[] condition for searching the key in btree
1393   * @param top boolean boolean which states if the key to searches shd be top most
1394   * of bottom most
1395   * @return BTreeKey btree key with the node and position of the required key.
1396   */
1397
1398  private BTreeKey searchNode(BTreeNode rootNode, _IndexPredicate[] condition,
1399                              _VariableValues reader, boolean top) throws
1400      DException {
1401
1402    if (rootNode == null || (rootNode.getElementCount() < 2 && rootNode.isLeaf())) {
1403      return null;
1404    }
1405    BTreeNode node = rootNode;
1406    BTreeNode locatedNode = null;
1407    int pos = -1;
1408    int valToRet = -1;
1409    do {
1410      locatedNode = node;
1411      pos = search(node, condition, reader, 1, node.getElementCount() - 1, top);
1412      valToRet = pos;
1413      if (pos < 0) {
1414        pos = Math.abs(pos);
1415      }
1416      node = node.isLeaf() ? null : getNode(null, node.getChildNodeKey(pos));
1417    }
1418    while (node != null);
1419    boolean isPartial = condition.length != getColumnNames().length;
1420    if (!isPartial && valToRet < 0) // = removed while test cases of btree split point are failed.
1421 return null;
1422    else if (valToRet > 0) {
1423      BTreeKey btreeKey = getBTreeKey(locatedNode, valToRet);
1424      BTreeKey searchKey = (BTreeKey) btreeKey.clone();
1425      if (top) {
1426        while (previous1(btreeKey)) {
1427          Object previousKey = btreeKey.getKey();
1428          ( (BTreeReader) reader).setValue(previousKey);
1429          if (evaluate(condition, reader, 0) != 0) {
1430            next1(btreeKey);
1431            return btreeKey;
1432          }
1433        }
1434        return btreeKey;
1435      }
1436      else {
1437        btreeKey = (BTreeKey) searchKey.clone();
1438        while (next1(btreeKey)) {
1439          Object nextKey = btreeKey.getKey();
1440          ( (BTreeReader) reader).setValue(nextKey);
1441          if (evaluate(condition, reader, 0) != 0) {
1442            previous1(btreeKey);
1443            return btreeKey;
1444          }
1445        }
1446        return btreeKey;
1447      }
1448    }
1449    else {
1450      BTreeKey btreeKey = getBTreeKey(locatedNode, Math.abs(valToRet));
1451      BTreeKey searchKey = (BTreeKey) btreeKey.clone();
1452      BTreeKey locatedKey = null;
1453      if (top) {
1454        while (previous1(btreeKey)) {
1455          Object previousKey = btreeKey.getKey();
1456          ( (BTreeReader) reader).setValue(previousKey);
1457          if (evaluate(condition, reader, 0) != 0)
1458            break;
1459          else {
1460            locatedKey = (BTreeKey) btreeKey.clone();
1461          }
1462        }
1463        if (locatedKey != null)
1464          return locatedKey;
1465        btreeKey = (BTreeKey) searchKey.clone();
1466        /*
1467         Here while is used earlier because we need to get next valid position and than compare it
1468         But now we replace it with if because we need to compare with only first next valid position
1469         if it doesn't match than we doesn't need to serach in more nodes
1470         */
1471        if (next1(btreeKey)) {
1472          Object nextKey = btreeKey.getKey();
1473          ( (BTreeReader) reader).setValue(nextKey);
1474          if (evaluate(condition, reader, 0) == 0)
1475            return btreeKey;
1476        }
1477        return null;
1478      }
1479      else {
1480        while (next1(btreeKey)) {
1481          Object nextKey = btreeKey.getKey();
1482          ( (BTreeReader) reader).setValue(nextKey);
1483          if (evaluate(condition, reader, 0) != 0)
1484            break;
1485          else
1486            locatedKey = (BTreeKey) btreeKey.clone();
1487        }
1488        if (locatedKey != null)
1489          return locatedKey;
1490        btreeKey = (BTreeKey) searchKey.clone();
1491        /*
1492                Here while is used earlier because we need to get next valid position and than compare it
1493                But now we replace it with if because we need to compare with only first next valid position
1494         if it doesn't match than we doesn't need to serach in more nodes
1495         */
1496
1497        if (previous1(btreeKey)) {
1498          Object previousKey = btreeKey.getKey();
1499          ( (BTreeReader) reader).setValue(previousKey);
1500          if (evaluate(condition, reader, 0) == 0)
1501            return btreeKey;
1502        }
1503        return null;
1504      }
1505    }
1506  }
1507
1508  /**
1509   * used in case of next and previous methods
1510   * returns the next btreeKey if it exists else returns null in case top = true
1511   * else if top=false returns the previous btreeKey if it exists else return null
1512   * @param entry BTreeKey key returned from search node method with
1513   * -ve or 0 position
1514   * @param top boolean boolean which states if the key to searches shd be top most
1515   * of bottom most
1516   * @return BTreeKey which satisfies the condition or null if no match found
1517   */
1518  private BTreeKey locateNode(BTreeKey entry, boolean top) throws DException {
1519    int position = entry.getPosition();
1520    position = Math.abs(position);
1521    BTreeNode node = entry.getNode();
1522    if (node.isNodeRemovedFromMap())
1523      node = nodeManager.getNode(null, node.getNodeKey());
1524    entry.setNodeAndPosition(node, position);
1525    if (top)
1526      return next1(entry) ? entry : null;
1527    else
1528      return entry.getPosition() == 0 ? previous1(entry) ? entry : null : entry;
1529  }
1530
1531  private BTreeKey delete(_DatabaseUser user, BTreeKey key, BTreeNode rootNode) throws
1532      DException {
1533    BTreeNode node = key.getNode();
1534    node = getNode(user, node.getNodeKey());
1535    node.delete(user, key.getPosition());
1536    nodeManager.updateSizeAndBTreeInfo(user, false, rootNode);
1537    return key;
1538
1539  }
1540
1541  public void setDuplicateAllowed(boolean flag) {
1542    DUPLICATEKEYSALLOWED = flag;
1543  }
1544
1545  public void releaseResource(_DatabaseUser user, boolean releaseCompletely) throws
1546      DException {
1547    nodeManager.releaseResource(user, releaseCompletely);
1548  }
1549
1550  public boolean getDuplicateAllowed() {
1551    return DUPLICATEKEYSALLOWED;
1552  }
1553
1554  public _IndexKey keyInstance() {
1555    return new BTreeKey();
1556  }
1557
1558  public BTreeNavigator getNavigator() {
1559    return new BTreeNavigatorCurrent(this);
1560  }
1561
1562
1563
1564
1565
1566
1567
1568
1569  public void setSize(int size0) {
1570    nodeManager.setSize(size0);
1571  }
1572
1573
1574
1575  /**
1576    public void dataOrder(Object key) throws DException{
1577      boolean dataOrder = true;
1578      BTreeKey btreeKey = new BTreeKey();
1579      if(first(btreeKey) ){
1580        Object previouseValue = btreeKey.getKey();
1581        while(next(btreeKey) ){
1582          Object newValue = btreeKey.getKey();
1583          if( comparator.compare( previouseValue,newValue ) > 0 ){
1584            dataOrder = false;
1585            try {
1586              File file = new File("D:/data/kuldeep/btreeShowValues.txt" );
1587              if(!file.exists() )
1588                file.createNewFile() ;
1589              OutputStream os = new FileOutputStream(file);
1590              PrintStream ps = new PrintStream(os,true );
1591              ps.println("previouseValue =") ;
1592              ps.println(P.print(getObject(previouseValue)));
1593              ps.println("newValue =") ;
1594              ps.println(P.print(getObject(newValue)));
1595              ps.println("Value Inserted =") ;
1596              ps.println(P.print(getObject(key)));
1597              ps.close() ;
1598
1599            }
1600            catch (Exception ex) {
1601            }
1602            showBTree();
1603            System.exit(0);
1604          }
1605          previouseValue = newValue;
1606        }
1607      }
1608    }
1609
1610
1611   private ArrayList addInFreeList(_DatabaseUser user, BTreeNode rootNode) throws
1612      DException {
1613    if (rootNode.isLeaf())
1614      return null;
1615    ArrayList freeNodeList = new ArrayList(0);
1616    BTreeNode childNode;
1617    for (int i = 0; i < rootNode.getElementCount(); i++) {
1618      childNode = rootNode.getElement(i, null).getChild();
1619      if (childNode != null)
1620        addInFreeList(childNode,freeNodeList);
1621    }
1622    ClusterCharacteristics cc;
1623    return freeNodeList;
1624
1625   }
1626
1627   private ArrayList addInFreeList(BTreeNode node,ArrayList freeNodeList) throws DException {
1628   if (!node.isLeaf()) {
1629      BTreeNode childNode;
1630      for (int i = 0; i < node.getElementCount(); i++) {
1631         childNode = node.getElement(i, null).getChild();
1632         if (childNode != null){
1633            addInFreeList(childNode, freeNodeList);
1634         }
1635
1636      }
1637   }else
1638     freeNodeList.add(new Integer(((ClusterCharacteristics) node.getNode().getNodeKey()).getStartAddress()));
1639   return freeNodeList;
1640   }
1641
1642   private ArrayList dataListing() throws DException{
1643    ArrayList list = new ArrayList(0);
1644     BTreeKey lastKey = new BTreeKey();
1645     last(lastKey);
1646     int lastAddress = ((ClusterCharacteristics)lastKey.getNode().getNodeKey()).getStartAddress();
1647     BTreeKey btreeKey = new BTreeKey();
1648    if(first(btreeKey) ){
1649      Object previouseValue = btreeKey.getKey();
1650      BTreeNode previousNode = btreeKey.getNode();
1651      while( previousNode != null){
1652         list.add(new Integer(((ClusterCharacteristics)previousNode.getNodeKey()).getStartAddress()));
1653        if(((ClusterCharacteristics)previousNode.getNodeKey()).getStartAddress() == lastAddress)
1654          break;
1655         previousNode = previousNode.getNextNode(null);
1656   }
1657    }
1658    return list;
1659   }
1660
1661   private void checkOrder(ArrayList list1,ArrayList list2,Object key) throws DException{
1662    if(list1 == null || list2 == null){
1663         ;//// Removed By Program ** System.out.println(" RETURNING FROM LIST1 == null or list2 == null list1 = "+list1+" list2 ="+list2);
1664      return;
1665    }
1666     if(list1.size() != list2.size()){
1667         ;//// Removed By Program ** System.out.println(" Returning from list1.size() != list2.size()");
1668       showBTree();
1669       System.exit(0);
1670     }
1671
1672     for (int i = 0; i < list1.size(); i++) {
1673   if(((Integer)list1.get(i)).intValue()!=((Integer)list2.get(i)).intValue()){
1674         ;//// Removed By Program ** System.out.println(i+" RETURNING FROM list1.get(i)!=list2.get(i) ");
1675         showBTree();
1676         System.exit(0);
1677       }
1678     }
1679     }
1680   private BTreeKey searchNodeOld(BTreeNode rootNode, _IndexPredicate[] condition,
1681                                _VariableValues reader, boolean top) throws
1682    DException {
1683   if (rootNode == null || (rootNode.getElementCount() < 2 && rootNode.isLeaf())) {
1684        return null;
1685      }
1686      BTreeNode node = rootNode;
1687      BTreeNode locatedNode = null;
1688      int pos = -1;
1689      int valToRet = -1;
1690      do {
1691        locatedNode = node;
1692   pos = search(node, condition, reader, 1, node.getElementCount() - 1, top);
1693        valToRet = pos;
1694        if (pos < 0) {
1695          pos = Math.abs(pos);
1696        }
1697        node = node.isLeaf() ? null : getNode(null, node.getChildNodeKey(pos));
1698      }
1699      while (node != null);
1700      boolean isPartial = condition.length!=getColumnNames().length;
1701      if (!isPartial && valToRet <= 0)
1702        return null;
1703      else if(valToRet > 0){
1704        BTreeKey btreeKey = getBTreeKey(locatedNode, valToRet);
1705        BTreeKey searchKey = (BTreeKey) btreeKey.clone();
1706        boolean flag = true;
1707        if (top) {
1708          while (previous1(btreeKey)) {
1709            Object previousKey = btreeKey.getKey();
1710            ( (BTreeReader) reader).setValue(previousKey);
1711            if (evaluate(condition, reader, 0) != 0) {
1712              next1(btreeKey);
1713              return btreeKey;
1714            }
1715          }
1716          return btreeKey;
1717        }
1718        else {
1719          btreeKey = (BTreeKey) searchKey.clone();
1720          while (next1(btreeKey)) {
1721            Object nextKey = btreeKey.getKey();
1722            ( (BTreeReader) reader).setValue(nextKey);
1723            if (evaluate(condition, reader, 0) != 0) {
1724              previous1(btreeKey);
1725              return btreeKey;
1726            }
1727          }
1728          return btreeKey;
1729        }
1730      }
1731      else{
1732        BTreeKey btreeKey = getBTreeKey(locatedNode, Math.abs(valToRet));
1733        BTreeKey searchKey = (BTreeKey) btreeKey.clone();
1734        BTreeKey locatedKey = null;
1735        BTreeNode btreenode = btreeKey.getNode();
1736        boolean flag = true;
1737        if (top) {
1738          while (previous1(btreeKey)) {
1739            Object previousKey = btreeKey.getKey();
1740            ( (BTreeReader) reader).setValue(previousKey);
1741            if (evaluate(condition, reader, 0) != 0)
1742              break;
1743            else{
1744              locatedKey = (BTreeKey) btreeKey.clone();
1745            }
1746          }
1747          if(locatedKey!=null)
1748            return locatedKey;
1749          btreeKey = (BTreeKey) searchKey.clone();
1750          while (next1(btreeKey)) {
1751            Object nextKey = btreeKey.getKey();
1752            ( (BTreeReader) reader).setValue(nextKey);
1753            if (evaluate(condition, reader, 0) == 0)
1754              return btreeKey;
1755          }
1756          return null;
1757        }else{
1758          while (next1(btreeKey)) {
1759            Object nextKey = btreeKey.getKey();
1760            ( (BTreeReader) reader).setValue(nextKey);
1761            if (evaluate(condition, reader, 0) != 0)
1762              break;
1763            else
1764              locatedKey = (BTreeKey) btreeKey.clone();
1765          }
1766          if(locatedKey!= null)
1767            return locatedKey;
1768          btreeKey = (BTreeKey) searchKey.clone();
1769          while (previous1(btreeKey)) {
1770            Object previousKey = btreeKey.getKey();
1771            ( (BTreeReader) reader).setValue(previousKey);
1772            if (evaluate(condition, reader, 0) == 0)
1773              return btreeKey;
1774          }
1775          return null;
1776        }
1777      }
1778    }
1779   private BTreeKey searchNodeOld(BTreeNode rootNode, Object key, boolean locate,
1780   boolean top, boolean isPartial) throws DException {
1781      BTreeNode node = rootNode;
1782      BTreeNode locatedNode = null;
1783      int pos = -1;
1784      int valToRet = -1;
1785      do {
1786        locatedNode = node;
1787        pos = search(node, key, 1, node.getElementCount() - 1, top);
1788        valToRet = pos;
1789        if (pos < 0) {
1790          pos = Math.abs(pos);
1791        }
1792        node = node.isLeaf() ? null : getNode(null, node.getChildNodeKey(pos));
1793      }
1794      while (node != null);
1795
1796
1797      if (!isPartial && valToRet <= 0) {
1798        return locate ? new BTreeKey(locatedNode, valToRet) : null;
1799      }
1800      else if(valToRet > 0){
1801        BTreeKey btreeKey = getBTreeKey(locatedNode, valToRet);
1802
1803        BTreeKey searchKey = (BTreeKey) btreeKey.clone();
1804        BTreeNode btreenode = btreeKey.getNode();
1805        boolean flag = true;
1806        if (top) {
1807          while (previous1(btreeKey)) {
1808            Object previousKey = btreeKey.getKey();
1809            if (! (comparator.compare(previousKey, key) == 0)) {
1810              next1(btreeKey);
1811              return btreeKey;
1812            }
1813          }
1814          return btreeKey;
1815        }
1816        else {
1817          btreeKey = (BTreeKey) searchKey.clone();
1818          while (next1(btreeKey)) {
1819            Object nextKey = btreeKey.getKey();
1820            if (! (comparator.compare(nextKey, key) == 0)) {
1821              previous1(btreeKey);
1822              return btreeKey;
1823            }
1824          }
1825          return btreeKey;
1826        }
1827      }
1828      else{
1829        BTreeKey btreeKey = getBTreeKey(locatedNode, Math.abs(valToRet));
1830        BTreeKey searchKey = (BTreeKey) btreeKey.clone();
1831        BTreeKey locatedKey = null;
1832        BTreeNode btreenode = btreeKey.getNode();
1833
1834        boolean flag = true;
1835        if (top) {
1836          while (previous1(btreeKey)) {
1837            Object previousKey = btreeKey.getKey();
1838            if (comparator.compare(previousKey, key) != 0)
1839              break;
1840            else
1841              locatedKey = (BTreeKey) btreeKey.clone();
1842          }
1843          if(locatedKey!= null)
1844            return locatedKey;
1845          btreeKey = (BTreeKey) searchKey.clone();
1846          while (next1(btreeKey)) {
1847            Object nextKey = btreeKey.getKey();
1848            if (comparator.compare(nextKey, key) == 0)
1849              return btreeKey;
1850
1851          }
1852          return locate ? new BTreeKey(locatedNode, valToRet) : null;
1853        }else{
1854          while (next1(btreeKey)) {
1855            Object nextKey = btreeKey.getKey();
1856            if (comparator.compare(nextKey, key) != 0)
1857              break;
1858            else
1859              locatedKey = (BTreeKey) btreeKey.clone();
1860          }
1861          if(locatedKey!=null)
1862            return locatedKey;
1863          btreeKey = (BTreeKey) searchKey.clone();
1864          while (previous1(btreeKey)) {
1865            Object previousKey = btreeKey.getKey();
1866            if (comparator.compare(previousKey, key) == 0)
1867              return btreeKey;
1868          }
1869          return locate ? new BTreeKey(locatedNode, valToRet) : null;
1870        }
1871      }
1872
1873    }
1874
1875// **/
1876}
1877

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags