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