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