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
26 import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
27 import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
28
29
30
31
32
33
34
35
36
37
38 class InMemoryLeaf<K, V> extends AbstractPage<K, V>
39 {
40
41 protected ValueHolder<V>[] values;
42
43
44
45
46
47
48
49 InMemoryLeaf( BTree<K, V> btree )
50 {
51 super( btree );
52 }
53
54
55
56
57
58
59
60
61
62 @SuppressWarnings("unchecked")
63 InMemoryLeaf( BTree<K, V> btree, long revision, int nbElems )
64 {
65 super( btree, revision, nbElems );
66
67 this.values = ( InMemoryValueHolder<V>[] ) Array.newInstance( InMemoryValueHolder.class, nbElems );
68 }
69
70
71
72
73
74 public InsertResult<K, V> insert( K key, V value, long revision ) throws IOException
75 {
76
77 int pos = findPos( key );
78
79 if ( pos < 0 )
80 {
81
82
83 int index = -( pos + 1 );
84
85
86 InsertResult<K, V> result = replaceElement( revision, key, value, index );
87
88 return result;
89 }
90
91
92 if ( nbElems < btree.getPageSize() )
93 {
94
95
96 Page<K, V> modifiedPage = addElement( revision, key, value, pos );
97
98 InsertResult<K, V> result = new ModifyResult<K, V>( modifiedPage, null );
99 result.addCopiedPage( this );
100
101 return result;
102 }
103 else
104 {
105
106
107 InsertResult<K, V> result = addAndSplit( revision, key, value, pos );
108 result.addCopiedPage( this );
109
110 return result;
111 }
112 }
113
114
115
116
117
118 @SuppressWarnings("unchecked")
119 DeleteResult<K, V> delete( K key, V value, long revision, Page<K, V> parent, int parentPos )
120 throws IOException
121 {
122
123 if ( nbElems == 0 )
124 {
125
126 return NotPresentResult.NOT_PRESENT;
127 }
128
129
130 int pos = findPos( key );
131
132 if ( pos >= 0 )
133 {
134
135 return NotPresentResult.NOT_PRESENT;
136 }
137
138
139 Tuple<K, V> removedElement = null;
140
141
142 boolean keyRemoved = false;
143
144 int index = -( pos + 1 );
145
146 ValueHolder<V> valueHolder = values[index];
147
148 if ( value == null )
149 {
150
151 removedElement = new Tuple<K, V>( getKey( index ), valueHolder.getCursor().next() );
152 keyRemoved = true;
153 }
154 else
155 {
156 if ( valueHolder.contains( value ) )
157 {
158
159 if ( valueHolder.size() == 1 )
160 {
161
162 removedElement = new Tuple<K, V>( getKey( index ), null );
163 keyRemoved = true;
164 }
165 else
166 {
167
168 valueHolder.remove( value );
169 removedElement = new Tuple<K, V>( getKey( index ), value );
170 }
171 }
172 else
173 {
174
175 return NotPresentResult.NOT_PRESENT;
176 }
177 }
178
179 InMemoryLeaf<K, V> newLeaf = null;
180
181 if ( keyRemoved )
182 {
183 newLeaf = new InMemoryLeaf<K, V>( btree, revision, nbElems - 1 );
184 }
185 else
186 {
187 newLeaf = new InMemoryLeaf<K, V>( btree, revision, nbElems );
188 }
189
190
191 DeleteResult<K, V> defaultResult = new RemoveResult<K, V>( newLeaf, removedElement );
192
193
194 if ( parent == null )
195 {
196
197 copyAfterRemovingElement( keyRemoved, newLeaf, index );
198
199
200 defaultResult.addCopiedPage( this );
201
202 return defaultResult;
203 }
204 else if ( keyRemoved )
205 {
206
207
208 int halfSize = btree.getPageSize() / 2;
209
210 if ( nbElems == halfSize )
211 {
212
213
214
215
216 int siblingPos = selectSibling( parent, parentPos );
217 InMemoryLeaf<K, V> sibling = ( InMemoryLeaf<K, V> ) ( ( ( InMemoryNode<K, V> ) parent )
218 .getPage( siblingPos ) );
219
220 if ( sibling.getNbElems() == halfSize )
221 {
222
223 DeleteResult<K, V> result = mergeWithSibling( removedElement, revision, sibling,
224 ( siblingPos < parentPos ), index );
225
226 return result;
227 }
228 else
229 {
230
231 if ( siblingPos < parentPos )
232 {
233 DeleteResult<K, V> result = borrowFromLeft( removedElement, revision, sibling, index );
234
235 return result;
236 }
237 else
238 {
239
240 DeleteResult<K, V> result = borrowFromRight( removedElement, revision, sibling, index );
241
242 return result;
243 }
244 }
245 }
246 else
247 {
248
249
250
251
252 copyAfterRemovingElement( keyRemoved, newLeaf, index );
253
254
255 defaultResult.addCopiedPage( this );
256
257 return defaultResult;
258 }
259 }
260 else
261 {
262
263
264 System.arraycopy( getKeys(), 0, newLeaf.getKeys(), 0, nbElems );
265 System.arraycopy( values, 0, newLeaf.values, 0, nbElems );
266
267
268 defaultResult.addCopiedPage( this );
269
270 return defaultResult;
271 }
272 }
273
274
275
276
277
278
279
280
281
282
283
284
285 private DeleteResult<K, V> mergeWithSibling( Tuple<K, V> removedElement, long revision, InMemoryLeaf<K, V> sibling,
286 boolean isLeft, int pos )
287 throws EndOfFileExceededException, IOException
288 {
289
290
291 InMemoryLeaf<K, V> newLeaf = new InMemoryLeaf<K, V>( btree, revision, btree.getPageSize() - 1 );
292
293 if ( isLeft )
294 {
295
296
297 System.arraycopy( sibling.getKeys(), 0, newLeaf.getKeys(), 0, sibling.nbElems );
298 System.arraycopy( sibling.values, 0, newLeaf.values, 0, sibling.nbElems );
299
300
301 System.arraycopy( getKeys(), 0, newLeaf.getKeys(), sibling.nbElems, pos );
302 System.arraycopy( values, 0, newLeaf.values, sibling.nbElems, pos );
303
304
305 System.arraycopy( getKeys(), pos + 1, newLeaf.getKeys(), sibling.nbElems + pos, nbElems - pos - 1 );
306 System.arraycopy( values, pos + 1, newLeaf.values, sibling.nbElems + pos, nbElems - pos - 1 );
307 }
308 else
309 {
310
311
312 System.arraycopy( getKeys(), 0, newLeaf.getKeys(), 0, pos );
313 System.arraycopy( values, 0, newLeaf.values, 0, pos );
314
315
316 System.arraycopy( getKeys(), pos + 1, newLeaf.getKeys(), pos, nbElems - pos - 1 );
317 System.arraycopy( values, pos + 1, newLeaf.values, pos, nbElems - pos - 1 );
318
319
320 System.arraycopy( sibling.getKeys(), 0, newLeaf.getKeys(), nbElems - 1, sibling.nbElems );
321 System.arraycopy( sibling.values, 0, newLeaf.values, nbElems - 1, sibling.nbElems );
322 }
323
324
325 DeleteResult<K, V> result = new MergedWithSiblingResult<K, V>( newLeaf,
326 removedElement );
327
328 result.addCopiedPage( this );
329 result.addCopiedPage( sibling );
330
331 return result;
332 }
333
334
335
336
337
338
339
340
341
342
343
344
345
346 private DeleteResult<K, V> borrowFromLeft( Tuple<K, V> removedElement, long revision, InMemoryLeaf<K, V> sibling,
347 int pos )
348 throws IOException
349 {
350
351 K siblingKey = sibling.getKey( sibling.getNbElems() - 1 );
352 ValueHolder<V> siblingValue = sibling.values[sibling.getNbElems() - 1];
353
354
355 InMemoryLeaf<K, V> newSibling = ( InMemoryLeaf<K, V> ) sibling.copy( revision, sibling.getNbElems() - 1 );
356
357
358
359 InMemoryLeaf<K, V> newLeaf = new InMemoryLeaf<K, V>( btree, revision, nbElems );
360
361
362 newLeaf.setKey( 0, new KeyHolder<K>( siblingKey ) );
363 newLeaf.values[0] = siblingValue;
364
365
366 System.arraycopy( getKeys(), 0, newLeaf.getKeys(), 1, pos );
367 System.arraycopy( values, 0, newLeaf.values, 1, pos );
368
369
370 System.arraycopy( getKeys(), pos + 1, newLeaf.getKeys(), pos + 1, getKeys().length - pos - 1 );
371 System.arraycopy( values, pos + 1, newLeaf.values, pos + 1, values.length - pos - 1 );
372
373 DeleteResult<K, V> result = new BorrowedFromLeftResult<K, V>( newLeaf, newSibling, removedElement );
374
375
376 result.addCopiedPage( this );
377 result.addCopiedPage( sibling );
378
379 return result;
380 }
381
382
383
384
385
386
387
388
389
390
391
392
393
394 private DeleteResult<K, V> borrowFromRight( Tuple<K, V> removedElement, long revision, InMemoryLeaf<K, V> sibling,
395 int pos )
396 throws IOException
397 {
398
399 K siblingKey = sibling.getKey( 0 );
400 ValueHolder<V> siblingHolder = sibling.values[0];
401
402
403 InMemoryLeaf<K, V> newSibling = new InMemoryLeaf<K, V>( btree, revision, sibling.getNbElems() - 1 );
404
405
406 System.arraycopy( sibling.getKeys(), 1, newSibling.getKeys(), 0, sibling.nbElems - 1 );
407 System.arraycopy( sibling.values, 1, newSibling.values, 0, sibling.nbElems - 1 );
408
409
410
411 InMemoryLeaf<K, V> newLeaf = new InMemoryLeaf<K, V>( btree, revision, nbElems );
412
413
414 newLeaf.setKey( nbElems - 1, new KeyHolder<K>( siblingKey ) );
415 newLeaf.values[nbElems - 1] = siblingHolder;
416
417
418 System.arraycopy( getKeys(), 0, newLeaf.getKeys(), 0, pos );
419 System.arraycopy( values, 0, newLeaf.values, 0, pos );
420
421
422 System.arraycopy( getKeys(), pos + 1, newLeaf.getKeys(), pos, getKeys().length - pos - 1 );
423 System.arraycopy( values, pos + 1, newLeaf.values, pos, values.length - pos - 1 );
424
425 DeleteResult<K, V> result = new BorrowedFromRightResult<K, V>( newLeaf, newSibling, removedElement );
426
427
428 result.addCopiedPage( this );
429 result.addCopiedPage( sibling );
430
431 return result;
432 }
433
434
435
436
437
438
439
440
441
442
443 private void copyAfterRemovingElement( boolean keyRemoved, InMemoryLeaf<K, V> newLeaf, int pos ) throws IOException
444 {
445 if ( keyRemoved )
446 {
447
448
449 if ( nbElems == 1 )
450 {
451 return;
452 }
453
454
455 System.arraycopy( getKeys(), 0, newLeaf.getKeys(), 0, pos );
456 System.arraycopy( values, 0, newLeaf.values, 0, pos );
457
458
459 System.arraycopy( getKeys(), pos + 1, newLeaf.getKeys(), pos, getKeys().length - pos - 1 );
460 System.arraycopy( values, pos + 1, newLeaf.values, pos, values.length - pos - 1 );
461 }
462 else
463
464 {
465 System.arraycopy( getKeys(), 0, newLeaf.getKeys(), 0, nbElems );
466 System.arraycopy( values, 0, newLeaf.values, 0, nbElems );
467 }
468 }
469
470
471
472
473
474 public V get( K key ) throws KeyNotFoundException, IOException
475 {
476 int pos = findPos( key );
477
478 if ( pos < 0 )
479 {
480 InMemoryValueHolder<V> valueHolder = ( InMemoryValueHolder<V> ) values[-( pos + 1 )];
481
482 V value = valueHolder.getCursor().next();
483
484 return value;
485 }
486 else
487 {
488 throw KeyNotFoundException.INSTANCE;
489 }
490 }
491
492
493
494
495
496 @Override
497 public ValueCursor<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
498 {
499 if ( !btree.isAllowDuplicates() )
500 {
501 throw new IllegalArgumentException( "Duplicates are not allowed in this tree" );
502 }
503
504 int pos = findPos( key );
505
506 if ( pos < 0 )
507 {
508 InMemoryValueHolder<V> valueHolder = ( InMemoryValueHolder<V> ) values[-( pos + 1 )];
509
510 return valueHolder.getCursor();
511 }
512 else
513 {
514 throw KeyNotFoundException.INSTANCE;
515 }
516 }
517
518
519
520
521
522 public boolean hasKey( K key )
523 {
524 int pos = findPos( key );
525
526 if ( pos < 0 )
527 {
528 return true;
529 }
530
531 return false;
532 }
533
534
535 @Override
536 public boolean contains( K key, V value ) throws IOException
537 {
538 int pos = findPos( key );
539
540 if ( pos < 0 )
541 {
542 ValueHolder<V> valueHolder = values[-( pos + 1 )];
543
544 return valueHolder.contains( value );
545 }
546 else
547 {
548 return false;
549 }
550 }
551
552
553
554
555
556 ValueHolder<V> getValue( int pos )
557 {
558 if ( pos < nbElems )
559 {
560 return values[pos];
561 }
562 else
563 {
564 return null;
565 }
566 }
567
568
569
570
571
572
573
574 void setValue( int pos, ValueHolder<V> value )
575 {
576 values[pos] = value;
577 }
578
579
580
581
582
583 public TupleCursor<K, V> browse( K key, ReadTransaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
584 {
585 int pos = findPos( key );
586 TupleCursor<K, V> cursor = null;
587
588 if ( pos < 0 )
589 {
590 pos = -( pos + 1 );
591
592
593 ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
594
595
596 parentPos.valueCursor = values[pos].getCursor();
597
598 stack[depth] = parentPos;
599
600 cursor = new TupleCursor<K, V>( transaction, stack, depth );
601 }
602 else
603 {
604
605 if ( pos < nbElems )
606 {
607 ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
608
609
610 parentPos.valueCursor = values[pos].getCursor();
611
612 stack[depth] = parentPos;
613
614 cursor = new TupleCursor<K, V>( transaction, stack, depth );
615 }
616 else if ( nbElems > 0 )
617 {
618
619 ParentPos<K, V> parentPos = new ParentPos<K, V>( this, nbElems - 1 );
620
621
622 parentPos.valueCursor = values[nbElems - 1].getCursor();
623
624 stack[depth] = parentPos;
625
626 cursor = new TupleCursor<K, V>( transaction, stack, depth );
627
628 try
629 {
630 cursor.afterLast();
631 }
632 catch ( IOException e )
633 {
634
635 e.printStackTrace();
636 }
637 }
638 else
639 {
640
641 stack[depth] = null;
642
643 cursor = new TupleCursor<K, V>( transaction, null, 0 );
644 }
645 }
646
647 return cursor;
648 }
649
650
651
652
653
654 public TupleCursor<K, V> browse( ReadTransaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
655 {
656 int pos = 0;
657 TupleCursor<K, V> cursor = null;
658
659 if ( nbElems == 0 )
660 {
661
662 stack[depth] = new ParentPos<K, V>( null, -1 );
663
664 return new TupleCursor<K, V>( transaction, stack, depth );
665 }
666 else
667 {
668
669 ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
670
671
672 parentPos.valueCursor = values[0].getCursor();
673
674 stack[depth] = parentPos;
675
676 cursor = new TupleCursor<K, V>( transaction, stack, depth );
677 }
678
679 return cursor;
680 }
681
682
683
684
685
686 public KeyCursor<K> browseKeys( ReadTransaction<K, K> transaction, ParentPos<K, K>[] stack, int depth )
687 {
688 int pos = 0;
689 KeyCursor<K> cursor = null;
690
691 if ( nbElems == 0 )
692 {
693
694 stack[depth] = new ParentPos<K, K>( null, -1 );
695
696 return new KeyCursor<K>( transaction, stack, depth );
697 }
698 else
699 {
700
701 ParentPos<K, K> parentPos = new ParentPos( this, pos );
702
703 stack[depth] = parentPos;
704
705 cursor = new KeyCursor<K>( transaction, stack, depth );
706 }
707
708 return cursor;
709 }
710
711
712
713
714
715
716
717
718
719 private Page<K, V> copy( long revision, int nbElems )
720 {
721 InMemoryLeaf<K, V> newLeaf = new InMemoryLeaf<K, V>( btree, revision, nbElems );
722
723
724 System.arraycopy( getKeys(), 0, newLeaf.getKeys(), 0, nbElems );
725 System.arraycopy( values, 0, newLeaf.values, 0, nbElems );
726
727 return newLeaf;
728 }
729
730
731
732
733
734
735
736
737
738
739
740
741 private InsertResult<K, V> replaceElement( long revision, K key, V value, int pos )
742 throws IOException
743 {
744 InMemoryLeaf<K, V> newLeaf = this;
745
746
747 ValueHolder<V> valueHolder = values[pos];
748
749 boolean valueExists = valueHolder.contains( value );
750
751 if ( this.revision != revision )
752 {
753
754 newLeaf = ( InMemoryLeaf<K, V> ) copy( revision, nbElems );
755 }
756
757
758 valueHolder = newLeaf.values[pos];
759 V replacedValue = null;
760
761 if ( !valueExists && btree.isAllowDuplicates() )
762 {
763 valueHolder.add( value );
764 newLeaf.values[pos] = valueHolder;
765 }
766 else if ( valueExists && btree.isAllowDuplicates() )
767 {
768
769
770
771 replacedValue = valueHolder.remove( value );
772 valueHolder.add( value );
773 }
774 else if ( !btree.isAllowDuplicates() )
775 {
776 replacedValue = valueHolder.replaceValueArray( value );
777 }
778
779
780 InsertResult<K, V> result = new ModifyResult<K, V>( newLeaf, replacedValue );
781 result.addCopiedPage( this );
782
783 return result;
784 }
785
786
787
788
789
790
791
792
793
794
795
796
797 private Page<K, V> addElement( long revision, K key, V value, int pos )
798 {
799
800 InMemoryLeaf<K, V> newLeaf = new InMemoryLeaf<K, V>( btree, revision, nbElems + 1 );
801
802
803 InMemoryValueHolder<V> valueHolder = new InMemoryValueHolder<V>( btree, value );
804
805
806 if ( nbElems == 0 )
807 {
808 newLeaf.setKey( 0, new KeyHolder<K>( key ) );
809 newLeaf.values[0] = valueHolder;
810 }
811 else
812 {
813
814 System.arraycopy( getKeys(), 0, newLeaf.getKeys(), 0, pos );
815 System.arraycopy( values, 0, newLeaf.values, 0, pos );
816
817
818 newLeaf.setKey( pos, new KeyHolder<K>( key ) );
819 newLeaf.values[pos] = valueHolder;
820
821
822 System.arraycopy( getKeys(), pos, newLeaf.getKeys(), pos + 1, getKeys().length - pos );
823 System.arraycopy( values, pos, newLeaf.values, pos + 1, values.length - pos );
824 }
825
826 return newLeaf;
827 }
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845 private InsertResult<K, V> addAndSplit( long revision, K key, V value, int pos )
846 {
847 int middle = btree.getPageSize() >> 1;
848 InMemoryLeaf<K, V> leftLeaf = null;
849 InMemoryLeaf<K, V> rightLeaf = null;
850 InMemoryValueHolder<V> valueHolder = new InMemoryValueHolder<V>( btree, value );
851
852
853 if ( pos <= middle )
854 {
855
856 leftLeaf = new InMemoryLeaf<K, V>( btree, revision, middle + 1 );
857
858
859 System.arraycopy( getKeys(), 0, leftLeaf.getKeys(), 0, pos );
860 System.arraycopy( values, 0, leftLeaf.values, 0, pos );
861
862
863 leftLeaf.setKey( pos, new KeyHolder<K>( key ) );
864 leftLeaf.values[pos] = valueHolder;
865
866
867 System.arraycopy( getKeys(), pos, leftLeaf.getKeys(), pos + 1, middle - pos );
868 System.arraycopy( values, pos, leftLeaf.values, pos + 1, middle - pos );
869
870
871 rightLeaf = new InMemoryLeaf<K, V>( btree, revision, middle );
872
873
874 System.arraycopy( getKeys(), middle, rightLeaf.getKeys(), 0, middle );
875 System.arraycopy( values, middle, rightLeaf.values, 0, middle );
876 }
877 else
878 {
879
880 leftLeaf = new InMemoryLeaf<K, V>( btree, revision, middle );
881
882
883 System.arraycopy( getKeys(), 0, leftLeaf.getKeys(), 0, middle );
884 System.arraycopy( values, 0, leftLeaf.values, 0, middle );
885
886
887 rightLeaf = new InMemoryLeaf<K, V>( btree, revision, middle + 1 );
888
889 int rightPos = pos - middle;
890
891
892 System.arraycopy( getKeys(), middle, rightLeaf.getKeys(), 0, rightPos );
893 System.arraycopy( values, middle, rightLeaf.values, 0, rightPos );
894
895
896 rightLeaf.setKey( rightPos, new KeyHolder<K>( key ) );
897 rightLeaf.values[rightPos] = valueHolder;
898
899
900 System.arraycopy( getKeys(), pos, rightLeaf.getKeys(), rightPos + 1, nbElems - pos );
901 System.arraycopy( values, pos, rightLeaf.values, rightPos + 1, nbElems - pos );
902 }
903
904
905 K pivot = rightLeaf.getKey( 0 );
906
907
908 InsertResult<K, V> result = new SplitResult<K, V>( pivot, leftLeaf, rightLeaf );
909
910 return result;
911 }
912
913
914
915
916
917 public Tuple<K, V> findLeftMost() throws IOException
918 {
919 V val = null;
920
921 val = values[0].getCursor().next();
922
923 return new Tuple<K, V>( getKey( 0 ), val );
924 }
925
926
927
928
929
930 public Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException
931 {
932 V val = null;
933
934 ValueCursor<V> valueCursor = values[nbElems - 1].getCursor();
935 valueCursor.afterLast();
936 val = valueCursor.prev();
937
938 return new Tuple<K, V>( getKey( nbElems - 1 ), val );
939 }
940
941
942
943
944
945 public boolean isLeaf()
946 {
947 return true;
948 }
949
950
951
952
953
954 public boolean isNode()
955 {
956 return false;
957 }
958
959
960
961
962
963 public String toString()
964 {
965 StringBuilder sb = new StringBuilder();
966
967 sb.append( "Leaf[" );
968 sb.append( super.toString() );
969
970 sb.append( "] -> {" );
971
972 if ( nbElems > 0 )
973 {
974 boolean isFirst = true;
975
976 for ( int i = 0; i < nbElems; i++ )
977 {
978 if ( isFirst )
979 {
980 isFirst = false;
981 }
982 else
983 {
984 sb.append( ", " );
985 }
986
987 sb.append( "<" ).append( getKey( i ) ).append( "," ).append( values[i] ).append( ">" );
988 }
989 }
990
991 sb.append( "}" );
992
993 return sb.toString();
994 }
995
996
997
998
999
1000 public String dumpPage( String tabs )
1001 {
1002 StringBuilder sb = new StringBuilder();
1003
1004 sb.append( tabs );
1005
1006 if ( nbElems > 0 )
1007 {
1008 boolean isFirst = true;
1009
1010 for ( int i = 0; i < nbElems; i++ )
1011 {
1012 if ( isFirst )
1013 {
1014 isFirst = false;
1015 }
1016 else
1017 {
1018 sb.append( ", " );
1019 }
1020
1021 sb.append( "<" ).append( getKey( i ) ).append( "," ).append( values[i] ).append( ">" );
1022 }
1023 }
1024
1025 sb.append( "\n" );
1026
1027 return sb.toString();
1028 }
1029 }