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