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