1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package org.apache.directory.mavibot.btree.managed;
21
22
23 import java.io.IOException;
24 import java.lang.reflect.Array;
25 import java.util.List;
26
27 import org.apache.directory.mavibot.btree.BorrowedFromSiblingResult;
28 import org.apache.directory.mavibot.btree.BorrowedFromLeftResult;
29 import org.apache.directory.mavibot.btree.BorrowedFromRightResult;
30 import org.apache.directory.mavibot.btree.DeleteResult;
31 import org.apache.directory.mavibot.btree.InsertResult;
32 import org.apache.directory.mavibot.btree.ModifyResult;
33 import org.apache.directory.mavibot.btree.NotPresentResult;
34 import org.apache.directory.mavibot.btree.Page;
35 import org.apache.directory.mavibot.btree.ParentPos;
36 import org.apache.directory.mavibot.btree.RemoveResult;
37 import org.apache.directory.mavibot.btree.SplitResult;
38 import org.apache.directory.mavibot.btree.Transaction;
39 import org.apache.directory.mavibot.btree.Tuple;
40 import org.apache.directory.mavibot.btree.TupleCursor;
41 import org.apache.directory.mavibot.btree.ValueCursor;
42 import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
43 import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
44
45
46
47
48
49
50
51
52
53
54
55
56 {
57
58 protected PageHolder<K, V>[] children;
59
60
61
62
63
64
65
66
67
68
69
70 @SuppressWarnings("unchecked")
71
72 {
73 super( btree, revision, nbElems );
74
75
76 children = ( PageHolder<K, V>[] ) Array.newInstance( PageHolder.class, nbElems + 1 );
77 }
78
79
80
81
82
83
84
85
86
87
88
89
90
91 @SuppressWarnings("unchecked")
92
93 {
94 super( btree, revision, 1 );
95
96
97 children = ( PageHolder<K, V>[] ) Array.newInstance( PageHolder.class,
98 btree.getPageSize() + 1 );
99
100 children[0] = btree.createPageHolder( leftPage );
101 children[1] = btree.createPageHolder( rightPage );
102
103
104
105
106 keys = ( KeyHolder[] ) Array.newInstance( KeyHolder.class, btree.getPageSize() );
107
108 keys[0] = new KeyHolder<K>( btree.getKeySerializer(), key );
109 }
110
111
112
113
114
115
116
117
118
119
120
121
122
123 @SuppressWarnings("unchecked")
124
125 PageHolder<K, V> rightPage )
126 {
127 super( btree, revision, 1 );
128
129
130 children = ( PageHolder<K, V>[] ) Array.newInstance( PageHolder.class,
131 btree.getPageSize() + 1 );
132
133 children[0] = leftPage;
134 children[1] = rightPage;
135
136
137 keys = ( KeyHolder[] ) Array.newInstance( KeyHolder.class, btree.getPageSize() );
138
139 keys[0] = new KeyHolder<K>( btree.getKeySerializer(), key );
140 }
141
142
143
144
145
146 public InsertResult<K, V> insert( long revision, K key, V value ) throws IOException
147 {
148
149 int pos = findPos( key );
150
151 if ( pos < 0 )
152 {
153
154
155 pos = -( pos++ );
156 }
157
158
159 Page<K, V> child = children[pos].getValue( btree );
160
161
162 InsertResult<K, V> result = child.insert( revision, key, value );
163
164
165
166 if ( result instanceof ModifyResult )
167 {
168
169 return replaceChild( revision, ( ModifyResult<K, V> ) result, pos );
170 }
171 else
172 {
173
174
175 SplitResult<K, V> splitResult = ( SplitResult<K, V> ) result;
176 K pivot = splitResult.getPivot();
177 Page<K, V> leftPage = splitResult.getLeftPage();
178 Page<K, V> rightPage = splitResult.getRightPage();
179
180
181
182
183 if ( nbElems == btree.getPageSize() )
184 {
185
186 result = addAndSplit( splitResult.getCopiedPages(), revision, pivot, leftPage, rightPage, pos );
187 }
188 else
189 {
190
191 result = insertChild( splitResult.getCopiedPages(), revision, pivot, leftPage, rightPage, pos );
192 }
193
194 return result;
195 }
196 }
197
198
199
200
201
202
203
204
205
206
207
208
209
210 private RemoveResult<K, V> handleRemoveResult( RemoveResult<K, V> removeResult, int index, int pos, boolean found )
211 throws IOException
212 {
213
214
215
216 Node<K, V> newPage = copy( revision );
217
218 Page<K, V> modifiedPage = removeResult.getModifiedPage();
219
220 if ( found )
221 {
222 newPage.children[index + 1] = createHolder( modifiedPage );
223 }
224 else
225 {
226 newPage.children[index] = createHolder( modifiedPage );
227 }
228
229 if ( pos < 0 )
230 {
231 newPage.keys[index].setKey( removeResult.getModifiedPage().getLeftMostKey() );
232 }
233
234
235 removeResult.setModifiedPage( newPage );
236 removeResult.addCopiedPage( this );
237
238 return removeResult;
239 }
240
241
242
243
244
245
246
247
248
249
250
251
252 private RemoveResult<K, V> handleRootRemove( MergedWithSiblingResult<K, V> mergedResult, int pos, boolean found )
253 throws IOException
254 {
255 RemoveResult<K, V> removeResult = null;
256
257
258
259 if ( nbElems == 1 )
260 {
261 removeResult = new RemoveResult<K, V>( mergedResult.getCopiedPages(), mergedResult.getModifiedPage(),
262 mergedResult.getRemovedElement() );
263
264 removeResult.addCopiedPage( this );
265 }
266 else
267 {
268
269 removeResult = removeKey( mergedResult, revision, pos );
270 }
271
272 return removeResult;
273 }
274
275
276
277
278
279
280
281
282
283
284
285
286
287 private DeleteResult<K, V> borrowFromRight( long revision, MergedWithSiblingResult<K, V> mergedResult,
288 Node<K, V> sibling, int pos ) throws IOException
289 {
290
291 Node<K, V> newSibling = new Node<K, V>( btree, revision, sibling.getNbElems() - 1 );
292
293 K siblingKey = sibling.children[0].getValue( btree ).getLeftMostKey();
294
295
296 System.arraycopy( sibling.keys, 1, newSibling.keys, 0, newSibling.getNbElems() );
297 System.arraycopy( sibling.children, 1, newSibling.children, 0, newSibling.getNbElems() + 1 );
298
299
300
301 Node<K, V> newNode = new Node<K, V>( btree, revision, nbElems );
302
303
304 int index = Math.abs( pos );
305
306
307 newNode.keys[nbElems - 1] = new KeyHolder<K>( btree.getKeySerializer(), siblingKey );
308 newNode.children[nbElems] = sibling.children[0];
309
310 if ( index < 2 )
311 {
312
313 System.arraycopy( keys, 1, newNode.keys, 0, nbElems - 1 );
314
315
316 Page<K, V> modifiedPage = mergedResult.getModifiedPage();
317 newNode.children[0] = createHolder( modifiedPage );
318
319
320 System.arraycopy( children, 2, newNode.children, 1, nbElems - 1 );
321 }
322 else
323 {
324 if ( index > 2 )
325 {
326
327 System.arraycopy( keys, 0, newNode.keys, 0, index - 2 );
328 }
329
330
331 newNode.keys[index - 2] = new KeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
332 .getLeftMostKey() );
333
334 if ( index < nbElems )
335 {
336
337 System.arraycopy( keys, index, newNode.keys, index - 1, nbElems - index );
338
339
340 System.arraycopy( children, index + 1, newNode.children, index, nbElems - index );
341 }
342
343
344 System.arraycopy( children, 0, newNode.children, 0, index - 1 );
345
346
347 Page<K, V> modifiedPage = mergedResult.getModifiedPage();
348 newNode.children[index - 1] = createHolder( modifiedPage );
349 }
350
351
352 DeleteResult<K, V> result = new BorrowedFromRightResult<K, V>( mergedResult.getCopiedPages(), newNode,
353 newSibling, mergedResult.getRemovedElement() );
354
355 result.addCopiedPage( this );
356 result.addCopiedPage( sibling );
357
358 return result;
359 }
360
361
362
363
364
365
366
367
368
369
370
371
372
373 private DeleteResult<K, V> borrowFromLeft( long revision, MergedWithSiblingResult<K, V> mergedResult,
374 Node<K, V> sibling, int pos ) throws IOException
375 {
376
377 Page<K, V> siblingChild = sibling.children[sibling.nbElems].getValue( btree );
378
379
380 Node<K, V> newSibling = new Node<K, V>( btree, revision, sibling.getNbElems() - 1 );
381
382
383 System.arraycopy( sibling.keys, 0, newSibling.keys, 0, newSibling.getNbElems() );
384 System.arraycopy( sibling.children, 0, newSibling.children, 0, newSibling.getNbElems() + 1 );
385
386
387
388 Node<K, V> newNode = new Node<K, V>( btree, revision, nbElems );
389
390
391 newNode.children[0] = createHolder( siblingChild );
392
393 int index = Math.abs( pos );
394
395 if ( index < 2 )
396 {
397 newNode.keys[0] = new KeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
398 .getLeftMostKey() );
399 System.arraycopy( keys, 1, newNode.keys, 1, nbElems - 1 );
400
401 Page<K, V> modifiedPage = mergedResult.getModifiedPage();
402 newNode.children[1] = createHolder( modifiedPage );
403 System.arraycopy( children, 2, newNode.children, 2, nbElems - 1 );
404 }
405 else
406 {
407
408 newNode.keys[0] = new KeyHolder<K>( btree.getKeySerializer(), children[0].getValue( btree )
409 .getLeftMostKey() );
410
411 if ( index > 2 )
412 {
413
414 System.arraycopy( keys, 0, newNode.keys, 1, index - 2 );
415 }
416
417
418 newNode.keys[index - 1] = new KeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
419 .getLeftMostKey() );
420
421 if ( index < nbElems )
422 {
423
424 System.arraycopy( keys, index, newNode.keys, index, nbElems - index );
425
426
427 System.arraycopy( children, index + 1, newNode.children, index + 1, nbElems - index );
428 }
429
430
431 System.arraycopy( children, 0, newNode.children, 1, index - 1 );
432
433
434 Page<K, V> modifiedPage = mergedResult.getModifiedPage();
435 newNode.children[index] = createHolder( modifiedPage );
436 }
437
438
439 DeleteResult<K, V> result = new BorrowedFromLeftResult<K, V>( mergedResult.getCopiedPages(), newNode,
440 newSibling,
441 mergedResult.getRemovedElement() );
442
443 result.addCopiedPage( this );
444 result.addCopiedPage( sibling );
445
446 return result;
447 }
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462 private DeleteResult<K, V> mergeWithSibling( long revision, MergedWithSiblingResult<K, V> mergedResult,
463 Node<K, V> sibling, boolean isLeft, int pos ) throws IOException
464 {
465
466
467 Node<K, V> newNode = new Node<K, V>( btree, revision, btree.getPageSize() );
468 Tuple<K, V> removedElement = mergedResult.getRemovedElement();
469 int half = btree.getPageSize() / 2;
470 int index = Math.abs( pos );
471
472 if ( isLeft )
473 {
474
475 System.arraycopy( sibling.keys, 0, newNode.keys, 0, half );
476 System.arraycopy( sibling.children, 0, newNode.children, 0, half + 1 );
477
478
479 if ( index < 2 )
480 {
481 newNode.keys[half] = new KeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
482 .getLeftMostKey() );
483 System.arraycopy( keys, 1, newNode.keys, half + 1, half - 1 );
484
485 Page<K, V> modifiedPage = mergedResult.getModifiedPage();
486 newNode.children[half + 1] = createHolder( modifiedPage );
487 System.arraycopy( children, 2, newNode.children, half + 2, half - 1 );
488 }
489 else
490 {
491
492
493 newNode.keys[half] = new KeyHolder<K>( btree.getKeySerializer(), children[0].getValue( btree )
494 .getLeftMostKey() );
495
496 if ( index > 2 )
497 {
498 System.arraycopy( keys, 0, newNode.keys, half + 1, index - 2 );
499 }
500
501
502 newNode.keys[half + index - 1] = new KeyHolder<K>( btree.getKeySerializer(), mergedResult
503 .getModifiedPage().getLeftMostKey() );
504
505 if ( index < half )
506 {
507 System.arraycopy( keys, index, newNode.keys, half + index, half - index );
508 System.arraycopy( children, index + 1, newNode.children, half + index + 1, half - index );
509 }
510
511
512 System.arraycopy( children, 0, newNode.children, half + 1, index - 1 );
513
514
515 Page<K, V> modifiedPage = mergedResult.getModifiedPage();
516 newNode.children[half + index] = createHolder( modifiedPage );
517 }
518 }
519 else
520 {
521
522 if ( index < 2 )
523 {
524
525 System.arraycopy( keys, 1, newNode.keys, 0, half - 1 );
526
527
528 Page<K, V> modifiedPage = mergedResult.getModifiedPage();
529 newNode.children[0] = createHolder( modifiedPage );
530
531
532 System.arraycopy( children, 2, newNode.children, 1, half - 1 );
533 }
534 else
535 {
536
537 if ( index > 2 )
538 {
539
540 System.arraycopy( keys, 0, newNode.keys, 0, index - 2 );
541 }
542
543
544 System.arraycopy( children, 0, newNode.children, 0, index - 1 );
545
546
547 newNode.keys[index - 2] = new KeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
548 .getLeftMostKey() );
549
550
551 Page<K, V> modifiedPage = mergedResult.getModifiedPage();
552 newNode.children[index - 1] = createHolder( modifiedPage );
553
554
555 if ( index < half )
556 {
557 System.arraycopy( keys, index, newNode.keys, index - 1, half - index );
558
559
560 System.arraycopy( children, index + 1, newNode.children, index, half - index );
561 }
562 }
563
564
565 newNode.keys[half - 1] = new KeyHolder<K>( btree.getKeySerializer(), sibling.findLeftMost().getKey() );
566
567
568 System.arraycopy( sibling.keys, 0, newNode.keys, half, half );
569
570
571 System.arraycopy( sibling.children, 0, newNode.children, half, half + 1 );
572 }
573
574
575 DeleteResult<K, V> result = new MergedWithSiblingResult<K, V>( mergedResult.getCopiedPages(), newNode,
576 removedElement );
577
578 result.addCopiedPage( this );
579 result.addCopiedPage( sibling );
580
581 return result;
582 }
583
584
585
586
587
588 public DeleteResult<K, V> delete( long revision, K key, V value, Page<K, V> parent, int parentPos )
589 throws IOException
590 {
591
592
593 int pos = findPos( key );
594 boolean found = pos < 0;
595 int index = pos;
596 Page<K, V> child = null;
597 DeleteResult<K, V> deleteResult = null;
598
599 if ( found )
600 {
601 index = -( pos + 1 );
602 child = children[-pos].getValue( btree );
603 deleteResult = child.delete( revision, key, value, this, -pos );
604 }
605 else
606 {
607 child = children[pos].getValue( btree );
608 deleteResult = child.delete( revision, key, value, this, pos );
609 }
610
611
612 if ( deleteResult instanceof NotPresentResult )
613 {
614
615 return deleteResult;
616 }
617
618
619 if ( deleteResult instanceof RemoveResult )
620 {
621 RemoveResult<K, V> removeResult = handleRemoveResult( ( RemoveResult<K, V> ) deleteResult, index, pos,
622 found );
623
624 return removeResult;
625 }
626
627
628
629 if ( deleteResult instanceof BorrowedFromSiblingResult )
630 {
631 RemoveResult<K, V> removeResult = handleBorrowedResult( (org.apache.directory.mavibot.btree.BorrowedFromSiblingResult<K, V> ) deleteResult,
632 pos );
633
634 return removeResult;
635 }
636
637
638
639 if ( deleteResult instanceof MergedWithSiblingResult )
640 {
641 MergedWithSiblingResult<K, V> mergedResult = ( MergedWithSiblingResult<K, V> ) deleteResult;
642
643
644 if ( parent == null )
645 {
646 RemoveResult<K, V> result = handleRootRemove( mergedResult, pos, found );
647
648 return result;
649 }
650
651
652 int halfSize = btree.getPageSize() / 2;
653
654 if ( nbElems > halfSize )
655 {
656
657
658
659
660 RemoveResult<K, V> result = removeKey( mergedResult, revision, pos );
661
662 return result;
663 }
664 else
665 {
666
667
668
669 int siblingPos = selectSibling( ( Node<K, V> ) parent, parentPos );
670
671 Node<K, V> sibling = ( Node<K, V> ) ( ( ( Node<K, V> ) parent ).children[siblingPos].getValue( btree ) );
672
673 if ( sibling.getNbElems() > halfSize )
674 {
675
676
677 if ( siblingPos < parentPos )
678 {
679 DeleteResult<K, V> result = borrowFromLeft( revision, mergedResult, sibling, pos );
680
681 return result;
682 }
683 else
684 {
685
686 DeleteResult<K, V> result = borrowFromRight( revision, mergedResult, sibling, pos );
687
688 return result;
689 }
690 }
691 else
692 {
693
694 DeleteResult<K, V> result = mergeWithSibling( revision, mergedResult, sibling,
695 ( siblingPos < parentPos ), pos );
696
697 return result;
698 }
699 }
700 }
701
702
703 return null;
704 }
705
706
707
708
709
710
711
712
713
714
715 private RemoveResult<K, V> handleBorrowedResult( BorrowedFromSiblingResult<K, V> borrowedResult, int pos )
716 throws IOException
717 {
718 Page<K, V> modifiedPage = borrowedResult.getModifiedPage();
719 Page<K, V> modifiedSibling = borrowedResult.getModifiedSibling();
720
721 Node<K, V> newPage = copy( revision );
722
723 if ( pos < 0 )
724 {
725 pos = -( pos + 1 );
726
727 if ( borrowedResult.isFromRight() )
728 {
729
730 newPage.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), modifiedPage.findLeftMost().getKey() );
731 newPage.keys[pos + 1] = new KeyHolder<K>( btree.getKeySerializer(), modifiedSibling.findLeftMost()
732 .getKey() );
733
734
735 newPage.children[pos + 1] = createHolder( modifiedPage );
736 newPage.children[pos + 2] = createHolder( modifiedSibling );
737 }
738 else
739 {
740
741 newPage.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), modifiedPage.findLeftMost().getKey() );
742
743
744 newPage.children[pos] = createHolder( modifiedSibling );
745 newPage.children[pos + 1] = createHolder( modifiedPage );
746 }
747 }
748 else
749 {
750 if ( borrowedResult.isFromRight() )
751 {
752
753 newPage.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), modifiedSibling.findLeftMost().getKey() );
754
755
756 newPage.children[pos] = createHolder( modifiedPage );
757 newPage.children[pos + 1] = createHolder( modifiedSibling );
758 }
759 else
760 {
761
762 newPage.keys[pos - 1] = new KeyHolder<K>( btree.getKeySerializer(), modifiedPage.findLeftMost()
763 .getKey() );
764
765
766 newPage.children[pos - 1] = createHolder( modifiedSibling );
767 newPage.children[pos] = createHolder( modifiedPage );
768 }
769 }
770
771
772 RemoveResult<K, V> removeResult = new RemoveResult<K, V>( borrowedResult.getCopiedPages(), newPage,
773 borrowedResult.getRemovedElement() );
774
775 removeResult.addCopiedPage( this );
776
777 return removeResult;
778 }
779
780
781
782
783
784
785
786
787
788
789
790 private RemoveResult<K, V> removeKey( MergedWithSiblingResult<K, V> mergedResult, long revision, int pos )
791 throws IOException
792 {
793
794 Node<K, V> newNode = new Node<K, V>( btree, revision, nbElems - 1 );
795
796 int index = Math.abs( pos ) - 2;
797
798
799 if ( index < 0 )
800 {
801
802 System.arraycopy( keys, 1, newNode.keys, 0, newNode.nbElems );
803 Page<K, V> modifiedPage = mergedResult.getModifiedPage();
804 newNode.children[0] = createHolder( modifiedPage );
805 System.arraycopy( children, 2, newNode.children, 1, nbElems - 1 );
806 }
807 else
808 {
809
810 if ( index > 0 )
811 {
812 System.arraycopy( keys, 0, newNode.keys, 0, index );
813 }
814
815 newNode.keys[index] = new KeyHolder<K>( btree.getKeySerializer(), mergedResult.getModifiedPage()
816 .findLeftMost().getKey() );
817
818 if ( index < nbElems - 2 )
819 {
820 System.arraycopy( keys, index + 2, newNode.keys, index + 1, nbElems - index - 2 );
821 }
822
823
824 System.arraycopy( children, 0, newNode.children, 0, index + 1 );
825
826 Page<K, V> modifiedPage = mergedResult.getModifiedPage();
827 newNode.children[index + 1] = createHolder( modifiedPage );
828
829 if ( index < nbElems - 2 )
830 {
831 System.arraycopy( children, index + 3, newNode.children, index + 2, nbElems - index - 2 );
832 }
833 }
834
835
836 RemoveResult<K, V> result = new RemoveResult<K, V>( mergedResult.getCopiedPages(), newNode,
837 mergedResult.getRemovedElement() );
838
839 result.addCopiedPage( this );
840
841 return result;
842 }
843
844
845
846
847
848
849 {
850 if ( pos < nbElems )
851 {
852 return keys[pos];
853 }
854 else
855 {
856 return null;
857 }
858 }
859
860
861
862
863
864 public V get( K key ) throws IOException, KeyNotFoundException
865 {
866 int pos = findPos( key );
867
868 if ( pos < 0 )
869 {
870
871
872 return children[-pos].getValue( btree ).get( key );
873 }
874 else
875 {
876 return children[pos].getValue( btree ).get( key );
877 }
878 }
879
880
881
882
883
884 @Override
885 public ValueCursor<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
886 {
887 int pos = findPos( key );
888
889 if ( pos < 0 )
890 {
891
892
893 return children[-pos].getValue( btree ).getValues( key );
894 }
895 else
896 {
897 return children[pos].getValue( btree ).getValues( key );
898 }
899 }
900
901
902
903
904
905 @Override
906 public boolean hasKey( K key ) throws IOException
907 {
908 int pos = findPos( key );
909
910 if ( pos < 0 )
911 {
912
913
914 return children[-pos].getValue( btree ).hasKey( key );
915 }
916 else
917 {
918 Page<K, V> page = children[pos].getValue( btree );
919
920 if ( page == null )
921 {
922 System.out.println( "Page is null for pos = " + pos + ", children = " + children[pos] );
923 }
924
925 return page.hasKey( key );
926 }
927 }
928
929
930
931
932
933 @Override
934 public boolean contains( K key, V value ) throws IOException
935 {
936 int pos = findPos( key );
937
938 if ( pos < 0 )
939 {
940
941
942 return children[-pos].getValue( btree ).contains( key, value );
943 }
944 else
945 {
946 return children[pos].getValue( btree ).contains( key, value );
947 }
948 }
949
950
951
952
953
954
955
956
957 public void setValue( int pos, PageHolder<K, V> value )
958 {
959 children[pos] = value;
960 }
961
962
963
964
965
966 public Page<K, V> getReference( int pos ) throws IOException
967 {
968 if ( pos < nbElems + 1 )
969 {
970 return children[pos].getValue( btree );
971 }
972 else
973 {
974 return null;
975 }
976 }
977
978
979
980
981
982 public TupleCursor<K, V> browse( K key, Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
983 throws IOException
984 {
985 int pos = findPos( key );
986
987 if ( pos < 0 )
988 {
989 pos = -pos;
990 }
991
992
993 stack[depth++] = new ParentPos<K, V>( this, pos );
994
995 Page<K, V> page = children[pos].getValue( btree );
996
997 return page.browse( key, transaction, stack, depth );
998 }
999
1000
1001
1002
1003
1004 public TupleCursor<K, V> browse( Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
1005 throws IOException
1006 {
1007 stack[depth++] = new ParentPos<K, V>( this, 0 );
1008
1009 Page<K, V> page = children[0].getValue( btree );
1010
1011 return page.browse( transaction, stack, depth );
1012 }
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026 private InsertResult<K, V> replaceChild( long revision, ModifyResult<K, V> result, int pos ) throws IOException
1027 {
1028
1029 Page<K, V> newPage = copy( revision );
1030
1031
1032
1033 Page<K, V> modifiedPage = result.getModifiedPage();
1034
1035 ( ( Node<K, V> ) newPage ).children[pos] = createHolder( modifiedPage );
1036
1037
1038
1039 result.setModifiedPage( newPage );
1040
1041 result.addCopiedPage( this );
1042
1043 return result;
1044 }
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054 private PageHolder<K, V> createHolder( Page<K, V> page ) throws IOException
1055 {
1056 PageHolder<K, V> holder = btree.getRecordManager().writePage( btree,
1057 page,
1058 revision );
1059
1060 return holder;
1061 }
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077 private InsertResult<K, V> insertChild( List<Page<K, V>> copiedPages, long revision, K key, Page<K, V> leftPage,
1078 Page<K, V> rightPage, int pos )
1079 throws IOException
1080 {
1081
1082 Node<K, V> newNode = new Node<K, V>( btree, revision, nbElems + 1 );
1083
1084
1085 if ( nbElems > 0 )
1086 {
1087 System.arraycopy( keys, 0, newNode.keys, 0, pos );
1088 System.arraycopy( children, 0, newNode.children, 0, pos );
1089 }
1090
1091
1092 newNode.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), key );
1093
1094
1095
1096 newNode.children[pos] = createHolder( leftPage );
1097 newNode.children[pos + 1] = createHolder( rightPage );
1098
1099
1100 if ( nbElems > 0 )
1101 {
1102 System.arraycopy( keys, pos, newNode.keys, pos + 1, keys.length - pos );
1103 System.arraycopy( children, pos + 1, newNode.children, pos + 2, children.length - pos - 1 );
1104 }
1105
1106
1107 InsertResult<K, V> result = new ModifyResult<K, V>( copiedPages, newNode, null );
1108 result.addCopiedPage( this );
1109
1110 return result;
1111 }
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132 private InsertResult<K, V> addAndSplit( List<Page<K, V>> copiedPages, long revision, K pivot, Page<K, V> leftPage,
1133 Page<K, V> rightPage, int pos ) throws IOException
1134 {
1135 int middle = btree.getPageSize() >> 1;
1136
1137
1138 Node<K, V> newLeftPage = new Node<K, V>( btree, revision, middle );
1139 Node<K, V> newRightPage = new Node<K, V>( btree, revision, middle );
1140
1141
1142
1143
1144 if ( pos < middle )
1145 {
1146
1147 System.arraycopy( keys, 0, newLeftPage.keys, 0, pos );
1148 System.arraycopy( children, 0, newLeftPage.children, 0, pos );
1149
1150
1151 newLeftPage.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), pivot );
1152 newLeftPage.children[pos] = createHolder( leftPage );
1153 newLeftPage.children[pos + 1] = createHolder( rightPage );
1154
1155
1156 System.arraycopy( keys, pos, newLeftPage.keys, pos + 1, middle - pos - 1 );
1157 System.arraycopy( children, pos + 1, newLeftPage.children, pos + 2, middle - pos - 1 );
1158
1159
1160 System.arraycopy( keys, middle, newRightPage.keys, 0, middle );
1161 System.arraycopy( children, middle, newRightPage.children, 0, middle + 1 );
1162
1163
1164 pivot = keys[middle - 1].getKey();
1165
1166 if ( pivot == null )
1167 {
1168 pivot = keys[middle - 1].getKey();
1169 }
1170
1171 InsertResult<K, V> result = new SplitResult<K, V>( copiedPages, pivot, newLeftPage,
1172 newRightPage );
1173 result.addCopiedPage( this );
1174
1175 return result;
1176 }
1177 else if ( pos == middle )
1178 {
1179
1180
1181
1182 System.arraycopy( keys, 0, newLeftPage.keys, 0, middle );
1183 System.arraycopy( children, 0, newLeftPage.children, 0, middle );
1184 newLeftPage.children[middle] = createHolder( leftPage );
1185
1186
1187 System.arraycopy( keys, middle, newRightPage.keys, 0, middle );
1188 System.arraycopy( children, middle + 1, newRightPage.children, 1, middle );
1189 newRightPage.children[0] = createHolder( rightPage );
1190
1191
1192 InsertResult<K, V> result = new SplitResult<K, V>( copiedPages, pivot, newLeftPage, newRightPage );
1193 result.addCopiedPage( this );
1194
1195 return result;
1196 }
1197 else
1198 {
1199
1200 System.arraycopy( keys, 0, newLeftPage.keys, 0, middle );
1201 System.arraycopy( children, 0, newLeftPage.children, 0, middle + 1 );
1202
1203
1204 System.arraycopy( keys, middle + 1, newRightPage.keys, 0, pos - middle - 1 );
1205 System.arraycopy( children, middle + 1, newRightPage.children, 0, pos - middle - 1 );
1206
1207
1208 newRightPage.keys[pos - middle - 1] = new KeyHolder<K>( btree.getKeySerializer(), pivot );
1209 newRightPage.children[pos - middle - 1] = createHolder( leftPage );
1210 newRightPage.children[pos - middle] = createHolder( rightPage );
1211
1212
1213 System.arraycopy( keys, pos, newRightPage.keys, pos - middle, nbElems - pos );
1214 System.arraycopy( children, pos + 1, newRightPage.children, pos + 1 - middle, nbElems - pos );
1215
1216
1217 pivot = keys[middle].getKey();
1218
1219 if ( pivot == null )
1220 {
1221 pivot = keys[middle].getKey();
1222 }
1223
1224 InsertResult<K, V> result = new SplitResult<K, V>( copiedPages, pivot, newLeftPage,
1225 newRightPage );
1226 result.addCopiedPage( this );
1227
1228 return result;
1229 }
1230 }
1231
1232
1233
1234
1235
1236
1237
1238
1239 protected Node<K, V> copy( long revision )
1240 {
1241 Node<K, V> newPage = new Node<K, V>( btree, revision, nbElems );
1242
1243
1244 System.arraycopy( keys, 0, newPage.keys, 0, nbElems );
1245
1246
1247 System.arraycopy( children, 0, newPage.children, 0, nbElems + 1 );
1248
1249 return newPage;
1250 }
1251
1252
1253
1254
1255
1256 public K getLeftMostKey() throws EndOfFileExceededException, IOException
1257 {
1258 return children[0].getValue( btree ).getLeftMostKey();
1259 }
1260
1261
1262
1263
1264
1265 public K getRightMostKey() throws EndOfFileExceededException, IOException
1266 {
1267 int index = ( nbElems + 1 ) - 1;
1268
1269 if ( children[index] != null )
1270 {
1271 return children[index].getValue( btree ).getRightMostKey();
1272 }
1273
1274 return children[nbElems - 1].getValue( btree ).getRightMostKey();
1275 }
1276
1277
1278
1279
1280
1281 public Tuple<K, V> findLeftMost() throws EndOfFileExceededException, IOException
1282 {
1283 return children[0].getValue( btree ).findLeftMost();
1284 }
1285
1286
1287
1288
1289
1290 public Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException
1291 {
1292 return children[nbElems].getValue( btree ).findRightMost();
1293 }
1294
1295
1296
1297
1298
1299 public String toString()
1300 {
1301 StringBuilder sb = new StringBuilder();
1302
1303 sb.append( "Node[" );
1304 sb.append( super.toString() );
1305 sb.append( "] -> {" );
1306
1307 try
1308 {
1309 if ( nbElems > 0 )
1310 {
1311
1312 if ( children[0] == null )
1313 {
1314 sb.append( "null" );
1315 }
1316 else
1317 {
1318 sb.append( 'r' ).append( children[0].getValue( btree ).getRevision() );
1319 }
1320
1321 for ( int i = 0; i < nbElems; i++ )
1322 {
1323 sb.append( "|<" ).append( keys[i] ).append( ">|" );
1324
1325 if ( children[i + 1] == null )
1326 {
1327 sb.append( "null" );
1328 }
1329 else
1330 {
1331 sb.append( 'r' ).append( children[i + 1].getValue( btree ).getRevision() );
1332 }
1333 }
1334 }
1335 }
1336 catch ( IOException ioe )
1337 {
1338
1339 }
1340
1341 sb.append( "}" );
1342
1343 return sb.toString();
1344 }
1345
1346
1347
1348
1349
1350 public String dumpPage( String tabs )
1351 {
1352 StringBuilder sb = new StringBuilder();
1353
1354 if ( nbElems > 0 )
1355 {
1356 try
1357 {
1358
1359 sb.append( children[0].getValue( btree ).dumpPage( tabs + " " ) );
1360
1361 for ( int i = 0; i < nbElems; i++ )
1362 {
1363 sb.append( tabs );
1364 sb.append( "<" );
1365 sb.append( keys[i] ).append( ">\n" );
1366 sb.append( children[i + 1].getValue( btree ).dumpPage( tabs + " " ) );
1367 }
1368 }
1369 catch ( IOException ioe )
1370 {
1371
1372 }
1373 }
1374
1375 return sb.toString();
1376 }
1377 }