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