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.managed;
21
22
23 import java.io.IOException;
24 import java.lang.reflect.Array;
25 import java.util.Comparator;
26 import java.util.UUID;
27
28 import org.apache.directory.mavibot.btree.Tuple;
29 import org.apache.directory.mavibot.btree.TupleCursor;
30 import org.apache.directory.mavibot.btree.ValueCursor;
31 import org.apache.directory.mavibot.btree.exception.BTreeAlreadyManagedException;
32 import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
33 import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
34 import org.apache.directory.mavibot.btree.serializer.IntSerializer;
35 import org.apache.directory.mavibot.btree.serializer.LongSerializer;
36
37
38
39
40
41
42
43
44 public class ValueHolder<V> implements Cloneable
45 {
46
47 private V[] valueArray;
48
49
50 private BTree<V, V> valueBtree;
51
52
53 private byte[] raw;
54
55
56 private boolean isDeserialized = false;
57
58
59 private boolean isRawUpToDate = false;
60
61
62 private BTree<?, V> btree;
63
64
65 private ElementSerializer<V> valueSerializer;
66
67
68
69
70
71
72
73
74
75
76
77 {
78 this.btree = btree;
79 this.valueSerializer = btree.getValueSerializer();
80 this.raw = raw;
81 isRawUpToDate = true;
82
83
84
85 if ( nbValues <= BTree.valueThresholdUp )
86 {
87
88 valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), nbValues );
89 }
90 }
91
92
93
94
95
96
97
98
99
100
101 {
102 this.btree = btree;
103 this.valueSerializer = btree.getValueSerializer();
104
105 if ( values != null )
106 {
107 int nbValues = values.length;
108
109 if ( nbValues < BTree.valueThresholdUp )
110 {
111
112 valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), nbValues );
113
114 try
115 {
116 System.arraycopy( values, 0, valueArray, 0, values.length );
117 }
118 catch ( ArrayStoreException ase )
119 {
120 ase.printStackTrace();
121 throw ase;
122 }
123 }
124 else
125 {
126
127 createSubTree();
128
129
130 for ( V value : values )
131 {
132 try
133 {
134 valueBtree.insert( value, value );
135 }
136 catch ( IOException e )
137 {
138 e.printStackTrace();
139 }
140 }
141 }
142 }
143 else
144 {
145
146 valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), 0 );
147 }
148
149 isDeserialized = true;
150 }
151
152
153
154
155
156 public ValueCursor<V> getCursor()
157 {
158 ValueCursor<V> cursor;
159
160
161 checkAndDeserialize();
162
163 if ( valueArray == null )
164 {
165 cursor = new ValueBtreeCursor();
166 }
167 else
168 {
169 cursor = new ValueArrayCursor();
170 }
171
172 return cursor;
173 }
174
175
176
177
178
179 private class ValueArrayCursor implements ValueCursor<V>
180 {
181
182 private int currentPos;
183
184
185
186
187
188 private ValueArrayCursor()
189 {
190
191 currentPos = BEFORE_FIRST;
192 }
193
194
195
196
197
198 @Override
199 public boolean hasNext()
200 {
201 return ( currentPos < valueArray.length - 1 ) && ( currentPos != AFTER_LAST );
202 }
203
204
205
206
207
208 public V next()
209 {
210 if ( valueArray == null )
211 {
212
213 return null;
214 }
215 else
216 {
217 currentPos++;
218
219 if ( currentPos == valueArray.length )
220 {
221 currentPos = AFTER_LAST;
222
223
224 return null;
225 }
226 else
227 {
228 return valueArray[currentPos];
229 }
230 }
231 }
232
233
234
235
236
237 @Override
238 public boolean hasPrev() throws EndOfFileExceededException, IOException
239 {
240 return currentPos > 0 || currentPos == AFTER_LAST;
241 }
242
243
244
245
246
247 @Override
248 public void close()
249 {
250 }
251
252
253
254
255
256 @Override
257 public void beforeFirst() throws IOException
258 {
259 currentPos = BEFORE_FIRST;
260 }
261
262
263
264
265
266 @Override
267 public void afterLast() throws IOException
268 {
269 currentPos = AFTER_LAST;
270 }
271
272
273
274
275
276 @Override
277 public V prev() throws EndOfFileExceededException, IOException
278 {
279 if ( valueArray == null )
280 {
281
282 return null;
283 }
284 else
285 {
286 if ( currentPos == AFTER_LAST )
287 {
288 currentPos = valueArray.length - 1;
289 }
290 else
291 {
292 currentPos--;
293 }
294
295 if ( currentPos == BEFORE_FIRST )
296 {
297
298 return null;
299 }
300 else
301 {
302 return valueArray[currentPos];
303 }
304 }
305 }
306
307
308
309
310
311 @Override
312 public int size()
313 {
314 return valueArray.length;
315 }
316 }
317
318
319
320
321 private class ValueBtreeCursor implements ValueCursor<V>
322 {
323
324 private TupleCursor<V, V> cursor;
325
326
327
328
329
330 private ValueBtreeCursor()
331 {
332
333 try
334 {
335 if ( valueBtree != null )
336 {
337 cursor = valueBtree.browse();
338 }
339 }
340 catch ( IOException e )
341 {
342
343 e.printStackTrace();
344 }
345 }
346
347
348
349
350
351 @Override
352 public boolean hasNext()
353 {
354 if ( cursor == null )
355 {
356 return false;
357 }
358 else
359 {
360 try
361 {
362 return cursor.hasNext();
363 }
364 catch ( EndOfFileExceededException e )
365 {
366 e.printStackTrace();
367 return false;
368 }
369 catch ( IOException e )
370 {
371 e.printStackTrace();
372 return false;
373 }
374 }
375 }
376
377
378
379
380
381 public V next()
382 {
383 try
384 {
385 return cursor.next().getKey();
386 }
387 catch ( EndOfFileExceededException e )
388 {
389 e.printStackTrace();
390 return null;
391 }
392 catch ( IOException e )
393 {
394 e.printStackTrace();
395 return null;
396 }
397 }
398
399
400
401
402
403 @Override
404 public boolean hasPrev() throws EndOfFileExceededException, IOException
405 {
406 if ( cursor == null )
407 {
408 return false;
409 }
410 else
411 {
412 try
413 {
414 return cursor.hasPrev();
415 }
416 catch ( EndOfFileExceededException e )
417 {
418 e.printStackTrace();
419 return false;
420 }
421 catch ( IOException e )
422 {
423 e.printStackTrace();
424 return false;
425 }
426 }
427 }
428
429
430
431
432
433 @Override
434 public void close()
435 {
436 if ( cursor != null )
437 {
438 cursor.close();
439 }
440 }
441
442
443
444
445
446 @Override
447 public void beforeFirst() throws IOException
448 {
449 if ( cursor != null )
450 {
451 cursor.beforeFirst();
452 }
453 }
454
455
456
457
458
459 @Override
460 public void afterLast() throws IOException
461 {
462 if ( cursor != null )
463 {
464 cursor.afterLast();
465 }
466 }
467
468
469
470
471
472 @Override
473 public V prev() throws EndOfFileExceededException, IOException
474 {
475 try
476 {
477 return cursor.prev().getKey();
478 }
479 catch ( EndOfFileExceededException e )
480 {
481 e.printStackTrace();
482 return null;
483 }
484 catch ( IOException e )
485 {
486 e.printStackTrace();
487 return null;
488 }
489 }
490
491
492
493
494
495 @Override
496 public int size()
497 {
498 return ( int ) valueBtree.getNbElems();
499 }
500 }
501
502
503
504
505
506
507
508
509
510
511 {
512 if ( isRawUpToDate )
513 {
514
515 return raw;
516 }
517
518 if ( isSubBtree() )
519 {
520
521 long btreeOffset = valueBtree.getBtreeOffset();
522 raw = LongSerializer.serialize( btreeOffset );
523 }
524 else
525 {
526
527 byte[][] valueBytes = new byte[valueArray.length * 2][];
528 int length = 0;
529 int pos = 0;
530
531
532 for ( V value : valueArray )
533 {
534
535 byte[] bytes = valueSerializer.serialize( value );
536 length += bytes.length;
537
538
539 byte[] sizeBytes = IntSerializer.serialize( bytes.length );
540 length += sizeBytes.length;
541
542
543 valueBytes[pos++] = sizeBytes;
544 valueBytes[pos++] = bytes;
545 }
546
547
548
549 raw = new byte[length];
550 pos = 0;
551
552 for ( byte[] bytes : valueBytes )
553 {
554 System.arraycopy( bytes, 0, raw, pos, bytes.length );
555 pos += bytes.length;
556 }
557 }
558
559
560 isRawUpToDate = true;
561
562 return raw;
563 }
564
565
566
567
568
569 public boolean isSubBtree()
570 {
571 return valueArray == null;
572 }
573
574
575
576
577
578 public int size()
579 {
580 checkAndDeserialize();
581
582 if ( valueArray == null )
583 {
584 return ( int ) valueBtree.getNbElems();
585 }
586 else
587 {
588 return valueArray.length;
589 }
590 }
591
592
593
594
595
596 private void createSubTree()
597 {
598 try
599 {
600 BTreeConfiguration<V, V> configuration = new BTreeConfiguration<V, V>();
601 configuration.setAllowDuplicates( false );
602 configuration.setKeySerializer( valueSerializer );
603 configuration.setName( UUID.randomUUID().toString() );
604 configuration.setValueSerializer( valueSerializer );
605 configuration.setParentBTree( btree );
606 configuration.setSubBtree( true );
607
608 valueBtree = new BTree<V, V>( configuration );
609
610 try
611 {
612 btree.getRecordManager().manage( valueBtree, RecordManager.INTERNAL_BTREE );
613 raw = null;
614 }
615 catch ( BTreeAlreadyManagedException e )
616 {
617
618 throw new RuntimeException( e );
619 }
620 }
621 catch ( IOException e )
622 {
623 throw new RuntimeException( e );
624 }
625 }
626
627
628
629
630
631
632 {
633 valueBtree = subBtree;
634 raw = null;
635 valueArray = null;
636 isDeserialized = true;
637 isRawUpToDate = false;
638 }
639
640
641
642
643
644 private void checkAndDeserialize()
645 {
646 if ( !isDeserialized )
647 {
648 if ( valueArray == null )
649 {
650
651 deserializeSubBtree();
652 }
653 else
654 {
655
656 deserializeArray();
657 }
658
659
660 isDeserialized = true;
661 }
662 }
663
664
665
666
667 private void addInArray( V value )
668 {
669 checkAndDeserialize();
670
671
672 if ( valueArray.length >= BTree.valueThresholdUp )
673 {
674
675 createSubTree();
676
677 try
678 {
679 for ( V val : valueArray )
680 {
681
682
683 valueBtree.insert( val, null );
684 }
685
686
687 valueArray = null;
688
689
690 valueBtree.insert( value, null );
691 }
692 catch ( IOException e )
693 {
694
695 e.printStackTrace();
696 }
697 }
698 else
699 {
700
701 int pos = findPos( value );
702
703 if ( pos >= 0 )
704 {
705
706 return;
707 }
708
709
710
711 pos = -( pos + 1 );
712
713 V[] newValueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), valueArray.length + 1 );
714
715 System.arraycopy( valueArray, 0, newValueArray, 0, pos );
716 newValueArray[pos] = value;
717 System.arraycopy( valueArray, pos, newValueArray, pos + 1, valueArray.length - pos );
718
719
720 valueArray = newValueArray;
721 }
722 }
723
724
725
726
727
728 private void addInBtree( V value )
729 {
730
731 checkAndDeserialize();
732
733 try
734 {
735 valueBtree.insert( value, null );
736 }
737 catch ( IOException e )
738 {
739
740 e.printStackTrace();
741 }
742 }
743
744
745
746
747
748
749
750 public void add( V value )
751 {
752 if ( valueArray != null )
753 {
754 addInArray( value );
755 }
756 else
757 {
758 addInBtree( value );
759 }
760
761
762 isRawUpToDate = false;
763 raw = null;
764 }
765
766
767
768
769
770 private V removeFromArray( V value )
771 {
772 checkAndDeserialize();
773
774
775 int pos = findPos( value );
776
777 if ( pos < 0 )
778 {
779
780 return null;
781 }
782
783
784
785 V[] newValueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), valueArray.length - 1 );
786
787 System.arraycopy( valueArray, 0, newValueArray, 0, pos );
788 System.arraycopy( valueArray, pos + 1, newValueArray, pos, valueArray.length - pos - 1 );
789
790
791 V removedValue = valueArray[pos];
792
793
794 valueArray = newValueArray;
795
796 return removedValue;
797 }
798
799
800
801
802
803 private V removeFromBtree( V removedValue )
804 {
805
806 checkAndDeserialize();
807
808 if ( btreeContains( removedValue ) )
809 {
810 try
811 {
812 if ( valueBtree.getNbElems() - 1 < BTree.valueThresholdLow )
813 {
814 int nbValues = (int)(valueBtree.getNbElems() - 1);
815
816
817 valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), nbValues );
818
819
820 TupleCursor<V,V> cursor = valueBtree.browse();
821 V returnedValue = null;
822 int pos = 0;
823
824 while ( cursor.hasNext() )
825 {
826 Tuple<V, V> tuple = cursor.next();
827
828 V value = tuple.getKey();
829
830 if ( valueSerializer.getComparator().compare( removedValue, value ) == 0 )
831 {
832
833 returnedValue = value;
834 }
835 else
836 {
837 valueArray[pos++] = value;
838 }
839 }
840
841 return returnedValue;
842 }
843 else
844 {
845 Tuple<V, V> removedTuple = valueBtree.delete( removedValue );
846
847 if ( removedTuple != null )
848 {
849 return removedTuple.getKey();
850 }
851 else
852 {
853 return null;
854 }
855 }
856 }
857 catch ( IOException e )
858 {
859
860 e.printStackTrace();
861 return null;
862 }
863 }
864 else
865 {
866 return null;
867 }
868 }
869
870
871
872
873
874
875 public V remove( V value )
876 {
877 V removedValue = null;
878
879 if ( valueArray != null )
880 {
881 removedValue = removeFromArray( value );
882 }
883 else
884 {
885 removedValue = removeFromBtree( value );
886 }
887
888
889 isRawUpToDate = false;
890 raw = null;
891
892 return removedValue;
893 }
894
895
896
897
898
899 private boolean arrayContains( V value )
900 {
901
902 checkAndDeserialize();
903
904 if ( valueArray.length == 0 )
905 {
906 return false;
907 }
908
909
910 return findPos( value ) >= 0;
911 }
912
913
914
915
916
917 private boolean btreeContains( V value )
918 {
919
920 checkAndDeserialize();
921
922 try
923 {
924 return valueBtree.hasKey( value );
925 }
926 catch ( IOException e )
927 {
928
929 e.printStackTrace();
930 return false;
931 }
932 }
933
934
935
936
937
938
939
940 public boolean contains( V value )
941 {
942 if ( valueArray == null )
943 {
944 return btreeContains( value );
945 }
946 else
947 {
948 return arrayContains( value );
949 }
950 }
951
952
953
954
955
956
957
958
959
960
961 private int findPos( V value )
962 {
963 if ( valueArray.length == 0 )
964 {
965 return -1;
966 }
967
968
969 int pivot = valueArray.length / 2;
970 int low = 0;
971 int high = valueArray.length - 1;
972 Comparator<V> comparator = valueSerializer.getComparator();
973
974 while ( high > low )
975 {
976 switch ( high - low )
977 {
978 case 1:
979
980 int result = comparator.compare( value, valueArray[pivot] );
981
982 if ( result == 0 )
983 {
984 return pivot;
985 }
986
987 if ( result < 0 )
988 {
989 if ( pivot == low )
990 {
991 return -( low + 1 );
992 }
993 else
994 {
995 result = comparator.compare( value, valueArray[low] );
996
997 if ( result == 0 )
998 {
999 return low;
1000 }
1001
1002 if ( result < 0 )
1003 {
1004 return -( low + 1 );
1005 }
1006 else
1007 {
1008 return -( low + 2 );
1009 }
1010 }
1011 }
1012 else
1013 {
1014 if ( pivot == high )
1015 {
1016 return -( high + 2 );
1017 }
1018 else
1019 {
1020 result = comparator.compare( value, valueArray[high] );
1021
1022 if ( result == 0 )
1023 {
1024 return high;
1025 }
1026
1027 if ( result < 0 )
1028 {
1029 return -( high + 1 );
1030 }
1031 else
1032 {
1033 return -( high + 2 );
1034 }
1035 }
1036 }
1037
1038 default:
1039
1040 result = comparator.compare( value, valueArray[pivot] );
1041
1042 if ( result == 0 )
1043 {
1044 return pivot;
1045 }
1046
1047 if ( result < 0 )
1048 {
1049 high = pivot - 1;
1050 }
1051 else
1052 {
1053 low = pivot + 1;
1054 }
1055
1056 pivot = ( high + low ) / 2;
1057
1058 continue;
1059 }
1060 }
1061
1062 int result = comparator.compare( value, valueArray[pivot] );
1063
1064 if ( result == 0 )
1065 {
1066 return pivot;
1067 }
1068
1069 if ( result < 0 )
1070 {
1071 return -( pivot + 1 );
1072 }
1073 else
1074 {
1075 return -( pivot + 2 );
1076 }
1077 }
1078
1079
1080
1081
1082
1083 public ValueHolder<V> clone() throws CloneNotSupportedException
1084 {
1085 ValueHolder<V> copy = ( ValueHolder<V> ) super.clone();
1086
1087
1088
1089
1090 if ( valueArray != null )
1091 {
1092 copy.valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), valueArray.length );
1093 System.arraycopy( valueArray, 0, copy.valueArray, 0, valueArray.length );
1094 }
1095
1096
1097 if ( isRawUpToDate )
1098 {
1099 copy.raw = new byte[raw.length];
1100 System.arraycopy( raw, 0, copy.raw, 0, raw.length );
1101 }
1102
1103 return copy;
1104 }
1105
1106
1107
1108
1109
1110 private void deserializeArray()
1111 {
1112
1113
1114 int index = 0;
1115 int pos = 0;
1116
1117 while ( pos < raw.length )
1118 {
1119 try
1120 {
1121 int size = IntSerializer.deserialize( raw, pos );
1122 pos += 4;
1123
1124 V value = valueSerializer.fromBytes( raw, pos );
1125 pos += size;
1126 valueArray[index++] = value;
1127 }
1128 catch ( IOException e )
1129 {
1130 e.printStackTrace();
1131 }
1132 }
1133 }
1134
1135
1136
1137
1138
1139 private void deserializeSubBtree()
1140 {
1141
1142 long offset = LongSerializer.deserialize( raw );
1143
1144
1145 valueBtree = btree.getRecordManager().loadDupsBTree( offset );
1146 }
1147
1148
1149
1150
1151
1152 {
1153 if ( valueArray == null )
1154 {
1155 return valueBtree.getBtreeOffset();
1156 }
1157 else
1158 {
1159 return -1L;
1160 }
1161 }
1162
1163
1164
1165
1166
1167 public String toString()
1168 {
1169 StringBuilder sb = new StringBuilder();
1170
1171 sb.append( "ValueHolder[" ).append( valueSerializer.getClass().getSimpleName() );
1172
1173 if ( !isDeserialized )
1174 {
1175 sb.append( ", isRaw[" ).append( raw.length ).append( "]" );
1176 }
1177 else
1178 {
1179 if ( valueArray == null )
1180 {
1181 sb.append( ", SubBTree" );
1182 }
1183 else
1184 {
1185 sb.append( ", array{" );
1186
1187 if ( valueArray == null )
1188 {
1189 sb.append( "}" );
1190 }
1191 else
1192 {
1193 boolean isFirst = true;
1194
1195 for ( V value : valueArray )
1196 {
1197 if ( isFirst )
1198 {
1199 isFirst = false;
1200 }
1201 else
1202 {
1203 sb.append( "/" );
1204 }
1205
1206 sb.append( value );
1207 }
1208
1209 sb.append( "}" );
1210 }
1211 }
1212 }
1213
1214 sb.append( "]" );
1215
1216 return sb.toString();
1217 }
1218 }