|
1
21 package com.db4o.inside.btree;
22
23 import com.db4o.*;
24 import com.db4o.foundation.*;
25 import com.db4o.inside.ix.*;
26
27
37 public final class BTreeNode extends YapMeta{
38
39 private static final int COUNT_LEAF_AND_3_LINK_LENGTH = (YapConst.INT_LENGTH * 4) + 1;
40
41 private static final int SLOT_LEADING_LENGTH = YapConst.LEADING_LENGTH + COUNT_LEAF_AND_3_LINK_LENGTH;
42
43
44 final BTree _btree;
45
46
47 private int _count;
48
49 private boolean _isLeaf;
50
51
52 private Object  [] _keys;
53
54
57 private Object [] _children;
58
59
62 private Object [] _values;
63
64
65 private int _parentID;
66
67 private int _previousID;
68
69 private int _nextID;
70
71 private boolean _cached;
72
73 private boolean _dead;
74
75
76
77
78 public BTreeNode(BTree btree,
79 int count,
80 boolean isLeaf,
81 int parentID,
82 int previousID,
83 int nextID){
84 _btree = btree;
85 _parentID = parentID;
86 _previousID = previousID;
87 _nextID = nextID;
88 _count = count;
89 _isLeaf = isLeaf;
90 prepareArrays();
91 setStateDirty();
92 }
93
94
95 public BTreeNode(int id, BTree btree){
96 _btree = btree;
97 setID(id);
98 setStateDeactivated();
99 }
100
101
102 public BTreeNode(Transaction trans, BTreeNode firstChild, BTreeNode secondChild){
103 this(firstChild._btree, 2, false, 0, 0, 0);
104 _keys[0] = firstChild._keys[0];
105 _children[0] = firstChild;
106 _keys[1] = secondChild._keys[0];
107 _children[1] = secondChild;
108
109 write(trans.systemTransaction());
110
111 firstChild.setParentID(trans, getID());
112 secondChild.setParentID(trans, getID());
113 }
114
115 public BTree btree() {
116 return _btree;
117 }
118
119
123 public BTreeNode add(Transaction trans){
124
125 YapReader reader = prepareRead(trans);
126
127 Searcher s = search(reader);
128
129 if(_isLeaf){
130
131 prepareWrite(trans);
132
133 if (wasRemoved(trans, s)) {
134 cancelRemoval(trans, s.cursor());
135 return null;
136 }
137
138 if(s.count() > 0 && ! s.beforeFirst()){
139 s.moveForward();
140 }
141
142 prepareInsert(s.cursor());
143 _keys[s.cursor()] = newAddPatch(trans);
144 if(handlesValues()){
145 _values[s.cursor()] = valueHandler().current();
146 }
147
148 }else{
149
150 BTreeNode childNode = child(reader, s.cursor());
151 BTreeNode childNodeOrSplit = childNode.add(trans);
152 if(childNodeOrSplit == null){
153 return null;
154 }
155 prepareWrite(trans);
156 _keys[s.cursor()] = childNode._keys[0];
157 if(childNode != childNodeOrSplit){
158 int splitCursor = s.cursor() + 1;
159 prepareInsert(splitCursor);
160 _keys[splitCursor] = childNodeOrSplit._keys[0];
161 _children[splitCursor] = childNodeOrSplit;
162 }
163 }
164
165 if(_count >= _btree.nodeSize()){
166 return split(trans);
167 }
168
169 if(s.cursor() == 0){
170 return this;
171 }
172
173 return null;
174 }
175
176 private BTreeAdd newAddPatch(Transaction trans) {
177 sizeIncrement(trans);
178 return new BTreeAdd(trans, currentKey());
179 }
180
181 private Object currentKey() {
182 return keyHandler().current();
183 }
184
185 private void cancelRemoval(Transaction trans, int index) {
186 final BTreeUpdate patch = (BTreeUpdate)keyPatch(index);
187 BTreeUpdate nextPatch = patch.removeFor(trans);
188 _keys[index] = newCancelledRemoval(trans, patch.getObject(), nextPatch);
189 sizeIncrement(trans);
190 }
191
192 private BTreePatch newCancelledRemoval(Transaction trans, Object originalObject, BTreeUpdate existingPatches) {
193 return new BTreeCancelledRemoval(trans, originalObject, currentKey(), existingPatches);
194 }
195
196 private void sizeIncrement(Transaction trans) {
197 _btree.sizeChanged(trans, 1);
198 }
199
200 private boolean wasRemoved(Transaction trans, Searcher s) {
201 if (!s.foundMatch()) {
202 return false;
203 }
204 BTreePatch patch = keyPatch(trans, s.cursor());
205 return patch != null && patch.isRemove();
206 }
207
208 BTreeNodeSearchResult searchLeaf(Transaction trans, SearchTarget target) {
209 YapReader reader = prepareRead(trans);
210 Searcher s = search(reader, target);
211 if(! _isLeaf){
212 return child(reader, s.cursor()).searchLeaf(trans, target);
213 }
214
215 if(! s.foundMatch() || target == SearchTarget.ANY || target == SearchTarget.HIGHEST){
216 return new BTreeNodeSearchResult(trans, reader, btree(), s, this);
217 }
218
219 if(target == SearchTarget.LOWEST){
220 BTreeNodeSearchResult res = findLowestLeafMatch(trans, s.cursor() - 1);
221 if(res != null){
222 return res;
223 }
224 return createMatchingSearchResult(trans, reader, s.cursor());
225 }
226
227 throw new IllegalStateException ();
228
229 }
230
231 private BTreeNodeSearchResult findLowestLeafMatch(Transaction trans, int index){
232 return findLowestLeafMatch(trans, prepareRead(trans), index);
233 }
234
235 private BTreeNodeSearchResult findLowestLeafMatch(Transaction trans, YapReader reader, int index){
236
237 if(index >= 0){
238 if(!compareEquals(reader, index)){
239 return null;
240 }
241 if(index > 0){
242 BTreeNodeSearchResult res = findLowestLeafMatch(trans, reader, index - 1);
243 if(res != null){
244 return res;
245 }
246 return createMatchingSearchResult(trans, reader, index);
247 }
248 }
249
250 final BTreeNode node = previousNode();
251 if(node != null){
252 final YapReader nodeReader = node.prepareRead(trans);
253 BTreeNodeSearchResult res = node.findLowestLeafMatch(trans, nodeReader, node.lastIndex());
254 if(res != null){
255 return res;
256 }
257 }
258
259 if(index < 0){
260 return null;
261 }
262
263 return createMatchingSearchResult(trans, reader, index);
264 }
265
266 private boolean compareEquals(final YapReader reader, int index) {
267 if(canWrite()){
268 return compareInWriteMode(index) == 0;
269 }
270 return compareInReadMode(reader, index) == 0;
271 }
272
273 private BTreeNodeSearchResult createMatchingSearchResult(Transaction trans, YapReader reader, int index) {
274 return new BTreeNodeSearchResult(trans, reader, btree(), this, index, true);
275 }
276
277 public boolean canWrite(){
278 return _keys != null;
279 }
280
281 BTreeNode child(int index){
282 if (_children[index] instanceof BTreeNode){
283 return (BTreeNode)_children[index];
284 }
285 return _btree.produceNode(((Integer )_children[index]).intValue());
286 }
287
288 BTreeNode child(YapReader reader, int index){
289 if( childLoaded(index) ){
290 return (BTreeNode)_children[index];
291 }
292 BTreeNode child = _btree.produceNode(childID(reader, index));
293
294 if(_children != null){
295 if(_cached || child.canWrite()){
296 _children[index] = child;
297 }
298 }
299
300 return child;
301 }
302
303 private int childID(YapReader reader, int index){
304 if(_children == null){
305 seekChild(reader, index);
306 return reader.readInt();
307 }
308 return childID(index);
309 }
310
311 private int childID(int index){
312 if(childLoaded(index)){
313 return ((BTreeNode)_children[index]).getID();
314 }
315 return ((Integer )_children[index]).intValue();
316 }
317
318 private boolean childLoaded(int index){
319 if(_children == null){
320 return false;
321 }
322 return _children[index] instanceof BTreeNode;
323 }
324
325 private boolean childCanSupplyFirstKey(int index){
326 if(! childLoaded(index)){
327 return false;
328 }
329 return ((BTreeNode)_children[index]).canWrite();
330 }
331
332 void commit(Transaction trans){
333 commitOrRollback(trans, true);
334 }
335
336 void commitOrRollback(Transaction trans, boolean isCommit){
337
338 if(DTrace.enabled){
339 DTrace.BTREE_NODE_COMMIT_OR_ROLLBACK.log(getID());
340 }
341
342 if(_dead){
343 return;
344 }
345
346 _cached = false;
347
348 if(! _isLeaf){
349 return;
350 }
351
352 if(! isDirty(trans)){
353 return;
354 }
355
356 Object keyZero = _keys[0];
357
358 boolean vals = handlesValues();
359
360 Object [] tempKeys = new Object [_btree.nodeSize()];
361 Object [] tempValues = vals ? new Object [_btree.nodeSize()] : null;
362
363 int count = 0;
364
365 for (int i = 0; i < _count; i++) {
366 Object key = _keys[i];
367 BTreePatch patch = keyPatch(i);
368 if(patch != null){
369 key = isCommit ? patch.commit(trans, _btree) : patch.rollback(trans, _btree);
370 }
371 if(key != No4.INSTANCE){
372 tempKeys[count] = key;
373 if(vals){
374 tempValues[count] = _values[i];
375 }
376 count ++;
377 }
378 }
379
380 _keys = tempKeys;
381 _values = tempValues;
382
383 _count = count;
384
385 if(freeIfEmpty(trans)){
386 return;
387 }
388
389
391 if(_keys[0] != keyZero){
392 tellParentAboutChangedKey(trans);
393 }
394
395 }
396
397 private boolean freeIfEmpty(Transaction trans){
398 return freeIfEmpty(trans, _count);
399 }
400
401 private boolean freeIfEmpty(Transaction trans, int count){
402 if(count > 0){
403 return false;
404 }
405 if(isRoot()){
406 return false;
407 }
408 free(trans);
409 return true;
410 }
411
412 private boolean isRoot() {
413 return _btree.root() == this;
414 }
415
416 public boolean equals(Object obj) {
417 if (this == obj){
418 return true;
419 }
420 if(! (obj instanceof BTreeNode)){
421 return false;
422 }
423 BTreeNode other = (BTreeNode) obj;
424 return getID() == other.getID();
425 }
426
427 private void free(Transaction trans){
428 _dead = true;
429 if(! isRoot()){
430 BTreeNode parent = _btree.produceNode(_parentID);
431 parent.removeChild(trans, this);
432 }
433 pointPreviousTo(trans, _nextID);
434 pointNextTo(trans, _previousID);
435 trans.systemTransaction().slotFreePointerOnCommit(getID());
436 _btree.removeNode(this);
437 }
438
439 void holdChildrenAsIDs(){
440 if(_children == null){
441 return;
442 }
443 for (int i = 0; i < _count; i++) {
444 if(_children[i] instanceof BTreeNode){
445 _children[i] = new Integer ( ((BTreeNode)_children[i]).getID() );
446 }
447 }
448 }
449
450 private void removeChild(Transaction trans, BTreeNode child) {
451 prepareWrite(trans);
452 int id = child.getID();
453 for (int i = 0; i < _count; i++) {
454 if(childID(i) == id){
455 if(freeIfEmpty(trans, _count -1)){
456 return;
457 }
458 remove(i);
459 if(i <= 1){
460 tellParentAboutChangedKey(trans);
461 }
462 if(_count == 0){
463 _isLeaf = true;
465 prepareValues();
466 }
467 return;
468 }
469 }
470 throw new IllegalStateException ("child not found");
471 }
472
473 private void keyChanged(Transaction trans, BTreeNode child) {
474 prepareWrite(trans);
475 int id = child.getID();
476 for (int i = 0; i < _count; i++) {
477 if(childID(i) == id){
478 _keys[i] = child._keys[0];
479 _children[i] = child;
480 keyChanged(trans, i);
481 return;
482 }
483 }
484 throw new IllegalStateException ("child not found");
485 }
486
487 private void tellParentAboutChangedKey(Transaction trans){
488 if(! isRoot()){
489 BTreeNode parent = _btree.produceNode(_parentID);
490 parent.keyChanged(trans, this);
491 }
492 }
493
494 private boolean isDirty(Transaction trans){
495 if(! canWrite()){
496 return false;
497 }
498
499 for (int i = 0; i < _count; i++) {
500 if(keyPatch(trans, i) != null){
501 return true;
502 }
503 }
504
505 return false;
506 }
507
508 private int compareInWriteMode(int index){
509 return keyHandler().compareTo(key(index));
510 }
511
512 private int compareInReadMode(YapReader reader, int index){
513 seekKey(reader, index);
514 return keyHandler().compareTo(keyHandler().readIndexEntry(reader));
515 }
516
517 public int count() {
518 return _count;
519 }
520
521 private int entryLength(){
522 int len = keyHandler().linkLength();
523 if(_isLeaf){
524 if(handlesValues()){
525 len += valueHandler().linkLength();
526 }
527 }else{
528 len += YapConst.ID_LENGTH;
529 }
530 return len;
531 }
532
533 public int firstKeyIndex(Transaction trans) {
534 for (int ix = 0; ix < _count; ix++) {
535 if(indexIsValid(trans, ix)){
536 return ix;
537 }
538 }
539 return -1;
540 }
541
542 public int lastKeyIndex(Transaction trans) {
543 for (int ix = _count - 1; ix >= 0; ix--) {
544 if(indexIsValid(trans, ix)){
545 return ix;
546 }
547 }
548 return -1;
549 }
550
551 public boolean indexIsValid(Transaction trans, int index){
552 if(!canWrite()){
553 return true;
554 }
555 BTreePatch patch = keyPatch(index);
556 if(patch == null){
557 return true;
558 }
559 return patch.key(trans) != No4.INSTANCE;
560 }
561
562 private Object firstKey(Transaction trans){
563 final int index = firstKeyIndex(trans);
564 if (-1 == index) {
565 return No4.INSTANCE;
566 }
567 return key(trans, index);
568 }
569
570 public byte getIdentifier() {
571 return YapConst.BTREE_NODE;
572 }
573
574 private boolean handlesValues(){
575 return _btree._valueHandler != Null.INSTANCE;
576 }
577
578 private void prepareInsert(int pos){
579 if(pos > lastIndex()){
580 _count ++;
581 return;
582 }
583 int len = _count - pos;
584 System.arraycopy(_keys, pos, _keys, pos + 1, len);
585 if(_values != null){
586 System.arraycopy(_values, pos, _values, pos + 1, len);
587 }
588 if(_children != null){
589 System.arraycopy(_children, pos, _children, pos + 1, len);
590 }
591 _count++;
592 }
593
594 private void remove(int pos){
595 if(DTrace.enabled){
596 DTrace.BTREE_NODE_REMOVE.log(getID());
597 }
598 int len = _count - pos;
599 _count--;
600 System.arraycopy(_keys, pos + 1, _keys, pos, len);
601 _keys[_count] = null;
602 if(_values != null){
603 System.arraycopy(_values, pos + 1, _values, pos, len);
604 _values[_count] = null;
605 }
606 if(_children != null){
607 System.arraycopy(_children, pos + 1, _children, pos, len);
608 _children[_count] = null;
609 }
610 }
611
612 Object key(int index){
613 Object obj = _keys[index];
614 if( obj instanceof BTreePatch){
615 return ((BTreePatch)obj).getObject();
616 }
617 return obj;
618 }
619
620 Object key(Transaction trans, YapReader reader, int index){
621 if(canWrite()){
622 return key(trans, index);
623 }
624 seekKey(reader, index);
625 return keyHandler().readIndexEntry(reader);
626 }
627
628 Object key(Transaction trans, int index){
629 BTreePatch patch = keyPatch(index);
630 if(patch == null){
631 return _keys[index];
632 }
633 return patch.key(trans);
634 }
635
636 private BTreePatch keyPatch(int index){
637 Object obj = _keys[index];
638 if( obj instanceof BTreePatch){
639 return (BTreePatch)obj;
640 }
641 return null;
642 }
643
644 private BTreePatch keyPatch(Transaction trans, int index){
645 Object obj = _keys[index];
646 if( obj instanceof BTreePatch){
647 return ((BTreePatch)obj).forTransaction(trans);
648 }
649 return null;
650 }
651
652 private Indexable4 keyHandler(){
653 return _btree._keyHandler;
654 }
655
656 void markAsCached(int height){
657 _cached = true;
658 _btree.addNode(this);
659
660 if( _isLeaf || (_children == null)){
661 return;
662 }
663
664 height --;
665
666 if(height < 1){
667 holdChildrenAsIDs();
668 return;
669 }
670
671 for (int i = 0; i < _count; i++) {
672 if(_children[i] instanceof BTreeNode){
673 ((BTreeNode)_children[i]).markAsCached(height);
674 }
675 }
676 }
677
678 public int ownLength() {
679 return SLOT_LEADING_LENGTH
680 + (_count * entryLength())
681 + YapConst.BRACKETS_BYTES;
682 }
683
684 YapReader prepareRead(Transaction trans){
685
686 if(canWrite()){
687 return null;
688 }
689
690 if(isNew()){
691 return null;
692 }
693
694 if(_cached){
695 read(trans.systemTransaction());
696 _btree.addToProcessing(this);
697 return null;
698 }
699
700 YapReader reader = trans.i_file.readReaderByID(trans.systemTransaction(), getID());
701
702 if (Deploy.debug) {
703 reader.readBegin(getIdentifier());
704 }
705
706 readNodeHeader(reader);
707
708 return reader;
709 }
710
711 void prepareWrite(Transaction trans){
712
713 if(_dead){
714 return;
715 }
716
717 if(canWrite()){
718 setStateDirty();
719 return;
720 }
721
722 read(trans.systemTransaction());
723 setStateDirty();
724 _btree.addToProcessing(this);
725 }
726
727 private void prepareArrays(){
728 if(canWrite()){
729 return;
730 }
731 _keys = new Object [_btree.nodeSize()];
732 if(_isLeaf){
733 prepareValues();
734 }else{
735 _children = new Object [_btree.nodeSize()];
736 }
737 }
738
739 private void prepareValues(){
740 if(handlesValues()){
741 _values = new Object [_btree.nodeSize()];
742 }
743 }
744
745 private void readNodeHeader(YapReader reader){
746 _count = reader.readInt();
747 byte leafByte = reader.readByte();
748 _isLeaf = (leafByte == 1);
749 _parentID = reader.readInt();
750 _previousID = reader.readInt();
751 _nextID = reader.readInt();
752 }
753
754 public void readThis(Transaction trans, YapReader reader) {
755 readNodeHeader(reader);
756
757 prepareArrays();
758
759 boolean isInner = ! _isLeaf;
760 boolean vals = handlesValues() && _isLeaf;
761 for (int i = 0; i < _count; i++) {
762 _keys[i] = keyHandler().readIndexEntry(reader);
763 if(vals){
764 _values[i] = valueHandler().readIndexEntry(reader);
765 }else{
766 if(isInner){
767 _children[i] = new Integer (reader.readInt());
768 }
769 }
770 }
771 }
772
773 public void remove(Transaction trans, int index){
774 if(!_isLeaf){
775 throw new IllegalStateException ();
776 }
777
778 prepareWrite(trans);
779
780 BTreePatch patch = keyPatch(index);
781
782 if(patch == null){
784 _keys[index] = newRemovePatch(trans);
785 keyChanged(trans, index);
786 return;
787 }
788
789 BTreePatch transPatch = patch.forTransaction(trans);
790 if(transPatch != null){
791 if(transPatch.isAdd()){
792 cancelAdding(trans, index);
793 return;
794 }
795 }else{
796 if(! patch.isAdd()){
799 ((BTreeUpdate)patch).append(newRemovePatch(trans));
800 return;
801 }
802 }
803
804 if(index != lastIndex()){
806 if(compareInWriteMode(index + 1 ) != 0){
807 return;
808 }
809 remove(trans, index + 1);
810 return;
811 }
812
813 BTreeNode node = nextNode();
815
816 if(node == null){
817 return;
818 }
819
820 node.prepareWrite(trans);
821 if(node.compareInWriteMode(0) != 0){
822 return;
823 }
824
825 node.remove(trans, 0);
826 }
827
828 private void cancelAdding(Transaction trans, int index) {
829 _btree.notifyRemoveListener(keyPatch(index).getObject());
830 if(freeIfEmpty(trans, _count-1)){
831 sizeDecrement(trans);
832 return;
833 }
834 remove(index);
835 keyChanged(trans, index);
836 sizeDecrement(trans);
837 }
838
839 private void sizeDecrement(Transaction trans) {
840 _btree.sizeChanged(trans, -1);
841 }
842
843 private int lastIndex() {
844 return _count - 1;
845 }
846
847 private BTreeUpdate newRemovePatch(Transaction trans) {
848 _btree.sizeChanged(trans, -1);
849 return new BTreeRemove(trans, currentKey());
850 }
851
852 private void keyChanged(Transaction trans, int index) {
853 if(index == 0){
854 tellParentAboutChangedKey(trans);
855 }
856 }
857
858
859 void rollback(Transaction trans){
860 commitOrRollback(trans, false);
861 }
862
863 private Searcher search(YapReader reader){
864 return search(reader, SearchTarget.ANY);
865 }
866
867 private Searcher search(YapReader reader, SearchTarget target){
868 Searcher s = new Searcher(target, _count);
869 if(canWrite()){
870 while(s.incomplete()){
871 s.resultIs( compareInWriteMode(s.cursor()));
872 }
873 }else{
874 while(s.incomplete()){
875 s.resultIs( compareInReadMode(reader, s.cursor()));
876 }
877 }
878 return s;
879 }
880
881 private void seekAfterKey(YapReader reader, int ix){
882 seekKey(reader, ix);
883 reader._offset += keyHandler().linkLength();
884 }
885
886 private void seekChild(YapReader reader, int ix){
887 seekAfterKey(reader, ix);
888 }
889
890 private void seekKey(YapReader reader, int ix){
891 reader._offset = SLOT_LEADING_LENGTH + (entryLength() * ix);
892 }
893
894 private void seekValue(YapReader reader, int ix){
895 if(handlesValues()){
896 seekAfterKey(reader, ix);
897 }else{
898 seekKey(reader, ix);
899 }
900 }
901
902 private BTreeNode split(Transaction trans){
903
904
905 BTreeNode res = new BTreeNode(_btree, _btree._halfNodeSize, _isLeaf,_parentID, getID(), _nextID);
906
907 System.arraycopy(_keys, _btree._halfNodeSize, res._keys, 0, _btree._halfNodeSize);
908 for (int i = _btree._halfNodeSize; i < _keys.length; i++) {
909 _keys[i] = null;
910 }
911 if(_values != null){
912 res._values = new Object [_btree.nodeSize()];
913 System.arraycopy(_values, _btree._halfNodeSize, res._values, 0, _btree._halfNodeSize);
914 for (int i = _btree._halfNodeSize; i < _values.length; i++) {
915 _values[i] = null;
916 }
917 }
918 if(_children != null){
919 res._children = new Object [_btree.nodeSize()];
920 System.arraycopy(_children, _btree._halfNodeSize, res._children, 0, _btree._halfNodeSize);
921 for (int i = _btree._halfNodeSize; i < _children.length; i++) {
922 _children[i] = null;
923 }
924 }
925
926 _count = _btree._halfNodeSize;
927
928 res.write(trans.systemTransaction());
929 _btree.addNode(res);
930
931 int splitID = res.getID();
932
933 pointNextTo(trans, splitID);
934
935 setNextID(trans, splitID);
936
937 if(_children != null){
938 for (int i = 0; i < _btree._halfNodeSize; i++) {
939 if(res._children[i] == null){
940 break;
941 }
942 res.child(i).setParentID(trans, splitID );
943 }
944 }
945 return res;
946 }
947
948 private void pointNextTo(Transaction trans, int id){
949 if(_nextID != 0){
950 nextNode().setPreviousID(trans, id);
951 }
952 }
953
954 private void pointPreviousTo(Transaction trans, int id){
955 if(_previousID != 0){
956 previousNode().setNextID(trans, id);
957 }
958 }
959
960 public BTreeNode previousNode() {
961 if(_previousID == 0){
962 return null;
963 }
964 return _btree.produceNode(_previousID);
965 }
966
967 public BTreeNode nextNode() {
968 if(_nextID == 0){
969 return null;
970 }
971 return _btree.produceNode(_nextID);
972 }
973
974 BTreePointer firstPointer(Transaction trans) {
975 YapReader reader = prepareRead(trans);
976 if (_isLeaf) {
977 return leafFirstPointer(trans, reader);
978 }
979 return branchFirstPointer(trans, reader);
980 }
981
982 private BTreePointer branchFirstPointer(Transaction trans, YapReader reader) {
983 for (int i = 0; i < _count; i++) {
984 BTreePointer childFirstPointer = child(reader, i).firstPointer(trans);
985 if(childFirstPointer != null){
986 return childFirstPointer;
987 }
988 }
989 return null;
990 }
991
992 private BTreePointer leafFirstPointer(Transaction trans, YapReader reader) {
993 int index = firstKeyIndex(trans);
994 if(index == -1){
995 return null;
996 }
997 return new BTreePointer(trans, reader, this, index);
998 }
999
1000 public BTreePointer lastPointer(Transaction trans) {
1001 YapReader reader = prepareRead(trans);
1002 if (_isLeaf) {
1003 return leafLastPointer(trans, reader);
1004 }
1005 return branchLastPointer(trans, reader);
1006 }
1007
1008 private BTreePointer branchLastPointer(Transaction trans, YapReader reader) {
1009 for (int i = _count - 1; i >= 0; i--) {
1010 BTreePointer childLastPointer = child(reader, i).lastPointer(trans);
1011 if(childLastPointer != null){
1012 return childLastPointer;
1013 }
1014 }
1015 return null;
1016 }
1017
1018 private BTreePointer leafLastPointer(Transaction trans, YapReader reader) {
1019 int index = lastKeyIndex(trans);
1020 if(index == -1){
1021 return null;
1022 }
1023 return new BTreePointer(trans, reader, this, index);
1024 }
1025
1026 void purge(){
1027 if(_dead){
1028 _keys = null;
1029 _values = null;
1030 _children = null;
1031 return;
1032 }
1033
1034 if(_cached){
1035 return;
1036 }
1037
1038 if(!canWrite()){
1039 return;
1040 }
1041
1042 for (int i = 0; i < _count; i++) {
1043 if(_keys[i] instanceof BTreePatch){
1044 holdChildrenAsIDs();
1045 _btree.addNode(this);
1046 return;
1047 }
1048 }
1049 }
1050
1051 private void setParentID(Transaction trans, int id){
1052 prepareWrite(trans);
1053 _parentID = id;
1054 setStateDirty();
1055 }
1056
1057 private void setPreviousID(Transaction trans, int id){
1058 prepareWrite(trans);
1059 _previousID = id;
1060 setStateDirty();
1061 }
1062
1063 private void setNextID(Transaction trans, int id){
1064 prepareWrite(trans);
1065 _nextID = id;
1066 setStateDirty();
1067 }
1068
1069 public void traverseKeys(Transaction trans, Visitor4 visitor){
1070 YapReader reader = prepareRead(trans);
1071 if(_isLeaf){
1072 for (int i = 0; i < _count; i++) {
1073 Object obj = key(trans,reader, i);
1074 if(obj != No4.INSTANCE){
1075 visitor.visit(obj);
1076 }
1077 }
1078 }else{
1079 for (int i = 0; i < _count; i++) {
1080 child(reader,i).traverseKeys(trans, visitor);
1081 }
1082 }
1083 }
1084
1085 public void traverseValues(Transaction trans, Visitor4 visitor){
1086 if(! handlesValues()){
1087 traverseKeys(trans, visitor);
1088 return;
1089 }
1090 YapReader reader = prepareRead(trans);
1091 if(_isLeaf){
1092 for (int i = 0; i < _count; i++) {
1093 if(key(trans,reader, i) != No4.INSTANCE){
1094 visitor.visit(value(reader, i));
1095 }
1096 }
1097 }else{
1098 for (int i = 0; i < _count; i++) {
1099 child(reader,i).traverseValues(trans, visitor);
1100 }
1101 }
1102 }
1103
1104 Object value(int index) {
1105 return _values[index];
1106 }
1107
1108 Object value(YapReader reader, int index){
1109 if( _values != null ){
1110 return _values[index];
1111 }
1112 seekValue(reader, index);
1113 return valueHandler().readIndexEntry(reader);
1114 }
1115
1116
1117 private Indexable4 valueHandler(){
1118 return _btree._valueHandler;
1119 }
1120
1121 public boolean writeObjectBegin() {
1122 if(_dead){
1123 return false;
1124 }
1125 if(!canWrite()){
1126 return false;
1127 }
1128 return super.writeObjectBegin();
1129 }
1130
1131
1132 public void writeThis(Transaction trans, YapReader a_writer) {
1133
1134 int count = 0;
1135 int startOffset = a_writer._offset;
1136
1137 a_writer.incrementOffset(COUNT_LEAF_AND_3_LINK_LENGTH);
1138
1139 if(_isLeaf){
1140 boolean vals = handlesValues();
1141 for (int i = 0; i < _count; i++) {
1142 Object obj = key(trans, i);
1143 if(obj != No4.INSTANCE){
1144 count ++;
1145 keyHandler().writeIndexEntry(a_writer, obj);
1146 if(vals){
1147 valueHandler().writeIndexEntry(a_writer, _values[i]);
1148 }
1149 }
1150 }
1151 }else{
1152 for (int i = 0; i < _count; i++) {
1153 if(childCanSupplyFirstKey(i)){
1154 BTreeNode child = (BTreeNode)_children[i];
1155 Object childKey = child.firstKey(trans);
1156 if(childKey != No4.INSTANCE){
1157 count ++;
1158 keyHandler().writeIndexEntry(a_writer, childKey);
1159 a_writer.writeIDOf(trans, child);
1160 }
1161 }else{
1162 count ++;
1163 keyHandler().writeIndexEntry(a_writer, key(i));
1164 a_writer.writeIDOf(trans, _children[i]);
1165 }
1166 }
1167 }
1168
1169 int endOffset = a_writer._offset;
1170 a_writer._offset = startOffset;
1171 a_writer.writeInt(count);
1172 a_writer.append( _isLeaf ? (byte) 1 : (byte) 0);
1173 a_writer.writeInt(_parentID);
1174 a_writer.writeInt(_previousID);
1175 a_writer.writeInt(_nextID);
1176 a_writer._offset = endOffset;
1177
1178 }
1179
1180 public String toString() {
1181 if(_count == 0){
1182 return "Node " + getID() + " not loaded";
1183 }
1184 String str = "\nBTreeNode";
1185 str += "\nid: " + getID();
1186 str += "\nparent: " + _parentID;
1187 str += "\nprevious: " + _previousID;
1188 str += "\nnext: " + _nextID;
1189 str += "\ncount:" + _count;
1190 str += "\nleaf:" + _isLeaf + "\n";
1191
1192 if(canWrite()){
1193
1194 str += " { ";
1195
1196 boolean first = true;
1197
1198 for (int i = 0; i < _count; i++) {
1199 if(_keys[i] != null){
1200 if(! first){
1201 str += ", ";
1202 }
1203 str += _keys[i].toString();
1204 first = false;
1205 }
1206 }
1207
1208 str += " }";
1209 }
1210 return str;
1211 }
1212
1213 public void debugLoadFully(Transaction trans) {
1214 prepareWrite(trans);
1215 if (_isLeaf) {
1216 return;
1217 }
1218 for (int i=0; i<_count; ++i) {
1219 if(_children[i] instanceof Integer ){
1220 _children[i] = btree().produceNode(((Integer )_children[i]).intValue());
1221 }
1222 ((BTreeNode)_children[i]).debugLoadFully(trans);
1223 }
1224 }
1225
1226 public static void defragIndex(ReaderPair readers,Indexable4 keyHandler,Indexable4 valueHandler) {
1227 if (Deploy.debug) {
1228 readers.readBegin(YapConst.BTREE_NODE);
1229 }
1230 int count=readers.readInt();
1232 byte leafByte = readers.readByte();
1234 boolean isLeaf = (leafByte == 1);
1235 boolean handlesValues=(valueHandler!=null)&&isLeaf;
1236
1237 readers.copyID(); readers.copyID(); readers.copyID();
1241 for (int i = 0; i < count; i++) {
1242 keyHandler.defragIndexEntry(readers);
1243 if(handlesValues){
1244 valueHandler.defragIndexEntry(readers);
1245 }else{
1246 if(!isLeaf){
1247 readers.copyID();
1248 }
1249 }
1250 }
1251 if (Deploy.debug) {
1252 readers.readEnd();
1253 }
1254 }
1255
1256 public boolean isLeaf() {
1257 return _isLeaf;
1258 }
1259
1260
1261 void traverseAllNodes(Transaction trans, Visitor4 command) {
1262 YapReader reader = prepareRead(trans);
1263 command.visit(this);
1264 if(_isLeaf){
1265 return;
1266 }
1267 for (int childIdx=0;childIdx<_count;childIdx++) {
1268 child(reader, childIdx).traverseAllNodes(trans, command);
1269 }
1270 }
1271}
1272 |
Popular Tags |
Java API By Example, From Geeks To Geeks.