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.Comparator;
26 import java.util.UUID;
27
28 import org.apache.directory.mavibot.btree.exception.BTreeAlreadyCreatedException;
29 import org.apache.directory.mavibot.btree.exception.BTreeAlreadyManagedException;
30 import org.apache.directory.mavibot.btree.exception.BTreeCreationException;
31 import org.apache.directory.mavibot.btree.serializer.IntSerializer;
32 import org.apache.directory.mavibot.btree.serializer.LongSerializer;
33
34
35
36
37
38
39
40
41
42 {
43
44 protected PersistedBTree<V, V> parentBtree;
45
46
47 private byte[] raw;
48
49
50 private boolean isDeserialized = false;
51
52
53 private boolean isRawUpToDate = false;
54
55
56
57
58
59
60
61
62
63
64 PersistedValueHolder( BTree<?, V> parentBtree, int nbValues, byte[] raw )
65 {
66 this.parentBtree = ( PersistedBTree<V, V> ) parentBtree;
67 this.valueSerializer = parentBtree.getValueSerializer();
68 this.raw = raw;
69 isRawUpToDate = true;
70 valueThresholdUp = PersistedBTree.valueThresholdUp;
71 valueThresholdLow = PersistedBTree.valueThresholdLow;
72
73
74
75 if ( nbValues <= valueThresholdUp )
76 {
77
78 valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), nbValues );
79 }
80 }
81
82
83
84
85
86
87
88
89
90 PersistedValueHolder( BTree<?, V> parentBtree, V... values )
91 {
92 this.parentBtree = ( PersistedBTree<V, V> ) parentBtree;
93 this.valueSerializer = parentBtree.getValueSerializer();
94 valueThresholdUp = PersistedBTree.valueThresholdUp;
95 valueThresholdLow = PersistedBTree.valueThresholdLow;
96
97 if ( values != null )
98 {
99 int nbValues = values.length;
100
101 if ( nbValues < PersistedBTree.valueThresholdUp )
102 {
103
104 valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), nbValues );
105
106 try
107 {
108 System.arraycopy( values, 0, valueArray, 0, values.length );
109 }
110 catch ( ArrayStoreException ase )
111 {
112 ase.printStackTrace();
113 throw ase;
114 }
115 }
116 else
117 {
118
119 createSubTree();
120
121
122 for ( V value : values )
123 {
124 try
125 {
126 valueBtree.insert( value, value );
127 }
128 catch ( IOException e )
129 {
130 e.printStackTrace();
131 }
132 }
133 }
134 }
135 else
136 {
137
138 valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), 0 );
139 }
140
141 isDeserialized = true;
142 }
143
144
145
146
147
148 public ValueCursor<V> getCursor()
149 {
150
151 checkAndDeserialize();
152
153 return super.getCursor();
154 }
155
156
157
158
159
160
161
162
163
164
165 {
166 if ( isRawUpToDate )
167 {
168
169 return raw;
170 }
171
172 if ( isSubBtree() )
173 {
174
175 long btreeOffset = ( ( PersistedBTree<V, V> ) valueBtree ).getBtreeOffset();
176 raw = LongSerializer.serialize( btreeOffset );
177 }
178 else
179 {
180
181 byte[][] valueBytes = new byte[valueArray.length * 2][];
182 int length = 0;
183 int pos = 0;
184
185
186 for ( V value : valueArray )
187 {
188
189 byte[] bytes = valueSerializer.serialize( value );
190 length += bytes.length;
191
192
193 byte[] sizeBytes = IntSerializer.serialize( bytes.length );
194 length += sizeBytes.length;
195
196
197 valueBytes[pos++] = sizeBytes;
198 valueBytes[pos++] = bytes;
199 }
200
201
202
203 raw = new byte[length];
204 pos = 0;
205
206 for ( byte[] bytes : valueBytes )
207 {
208 System.arraycopy( bytes, 0, raw, pos, bytes.length );
209 pos += bytes.length;
210 }
211 }
212
213
214 isRawUpToDate = true;
215
216 return raw;
217 }
218
219
220
221
222
223 public int size()
224 {
225 checkAndDeserialize();
226
227 if ( valueArray == null )
228 {
229 return ( int ) valueBtree.getNbElems();
230 }
231 else
232 {
233 return valueArray.length;
234 }
235 }
236
237
238
239
240
241 protected void createSubTree()
242 {
243 try
244 {
245 PersistedBTreeConfiguration<V, V> configuration = new PersistedBTreeConfiguration<V, V>();
246 configuration.setAllowDuplicates( false );
247 configuration.setKeySerializer( valueSerializer );
248 configuration.setName( UUID.randomUUID().toString() );
249 configuration.setValueSerializer( valueSerializer );
250 configuration.setParentBTree( parentBtree );
251 configuration.setSubBtree( true );
252
253 valueBtree = BTreeFactory.createPersistedBTree( configuration );
254
255 try
256 {
257 parentBtree.getRecordManager().manage( valueBtree, RecordManager.INTERNAL_BTREE );
258 raw = null;
259 }
260 catch ( BTreeAlreadyManagedException e )
261 {
262
263 throw new BTreeAlreadyCreatedException( e );
264 }
265 }
266 catch ( IOException e )
267 {
268 throw new BTreeCreationException( e );
269 }
270 }
271
272
273
274
275
276
277 {
278 valueBtree = subBtree;
279 raw = null;
280 valueArray = null;
281 isDeserialized = true;
282 isRawUpToDate = false;
283 }
284
285
286
287
288
289 private void checkAndDeserialize()
290 {
291 if ( !isDeserialized )
292 {
293 if ( valueArray == null )
294 {
295
296 deserializeSubBtree();
297 }
298 else
299 {
300
301 deserializeArray();
302 }
303
304
305 isDeserialized = true;
306 }
307 }
308
309
310
311
312
313 public void add( V value )
314 {
315
316 checkAndDeserialize();
317
318 super.add( value );
319
320
321 isRawUpToDate = false;
322 raw = null;
323 }
324
325
326
327
328
329 private V removeFromArray( V value )
330 {
331 checkAndDeserialize();
332
333
334 int pos = findPos( value );
335
336 if ( pos < 0 )
337 {
338
339 return null;
340 }
341
342
343
344 V[] newValueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), valueArray.length - 1 );
345
346 System.arraycopy( valueArray, 0, newValueArray, 0, pos );
347 System.arraycopy( valueArray, pos + 1, newValueArray, pos, valueArray.length - pos - 1 );
348
349
350 V removedValue = valueArray[pos];
351
352
353 valueArray = newValueArray;
354
355 return removedValue;
356 }
357
358
359
360
361
362 private V removeFromBtree( V removedValue )
363 {
364
365 checkAndDeserialize();
366
367 if ( btreeContains( removedValue ) )
368 {
369 try
370 {
371 if ( valueBtree.getNbElems() - 1 < PersistedBTree.valueThresholdLow )
372 {
373 int nbValues = ( int ) ( valueBtree.getNbElems() - 1 );
374
375
376 valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), nbValues );
377
378
379 TupleCursor<V, V> cursor = valueBtree.browse();
380 V returnedValue = null;
381 int pos = 0;
382
383 while ( cursor.hasNext() )
384 {
385 Tuple<V, V> tuple = cursor.next();
386
387 V value = tuple.getKey();
388
389 if ( valueSerializer.getComparator().compare( removedValue, value ) == 0 )
390 {
391
392 returnedValue = value;
393 }
394 else
395 {
396 valueArray[pos++] = value;
397 }
398 }
399
400 return returnedValue;
401 }
402 else
403 {
404 Tuple<V, V> removedTuple = valueBtree.delete( removedValue );
405
406 if ( removedTuple != null )
407 {
408 return removedTuple.getKey();
409 }
410 else
411 {
412 return null;
413 }
414 }
415 }
416 catch ( IOException e )
417 {
418
419 e.printStackTrace();
420 return null;
421 }
422 }
423 else
424 {
425 return null;
426 }
427 }
428
429
430
431
432
433 public V remove( V value )
434 {
435 V removedValue = null;
436
437 if ( valueArray != null )
438 {
439 removedValue = removeFromArray( value );
440 }
441 else
442 {
443 removedValue = removeFromBtree( value );
444 }
445
446
447 isRawUpToDate = false;
448 raw = null;
449
450 return removedValue;
451 }
452
453
454
455
456
457 public boolean contains( V checkedValue )
458 {
459
460 checkAndDeserialize();
461
462 return super.contains( checkedValue );
463 }
464
465
466
467
468
469
470
471
472
473
474 private int findPos( V value )
475 {
476 if ( valueArray.length == 0 )
477 {
478 return -1;
479 }
480
481
482 int pivot = valueArray.length / 2;
483 int low = 0;
484 int high = valueArray.length - 1;
485 Comparator<V> comparator = valueSerializer.getComparator();
486
487 while ( high > low )
488 {
489 switch ( high - low )
490 {
491 case 1:
492
493 int result = comparator.compare( value, valueArray[pivot] );
494
495 if ( result == 0 )
496 {
497 return pivot;
498 }
499
500 if ( result < 0 )
501 {
502 if ( pivot == low )
503 {
504 return -( low + 1 );
505 }
506 else
507 {
508 result = comparator.compare( value, valueArray[low] );
509
510 if ( result == 0 )
511 {
512 return low;
513 }
514
515 if ( result < 0 )
516 {
517 return -( low + 1 );
518 }
519 else
520 {
521 return -( low + 2 );
522 }
523 }
524 }
525 else
526 {
527 if ( pivot == high )
528 {
529 return -( high + 2 );
530 }
531 else
532 {
533 result = comparator.compare( value, valueArray[high] );
534
535 if ( result == 0 )
536 {
537 return high;
538 }
539
540 if ( result < 0 )
541 {
542 return -( high + 1 );
543 }
544 else
545 {
546 return -( high + 2 );
547 }
548 }
549 }
550
551 default:
552
553 result = comparator.compare( value, valueArray[pivot] );
554
555 if ( result == 0 )
556 {
557 return pivot;
558 }
559
560 if ( result < 0 )
561 {
562 high = pivot - 1;
563 }
564 else
565 {
566 low = pivot + 1;
567 }
568
569 pivot = ( high + low ) / 2;
570
571 continue;
572 }
573 }
574
575 int result = comparator.compare( value, valueArray[pivot] );
576
577 if ( result == 0 )
578 {
579 return pivot;
580 }
581
582 if ( result < 0 )
583 {
584 return -( pivot + 1 );
585 }
586 else
587 {
588 return -( pivot + 2 );
589 }
590 }
591
592
593
594
595
596 public ValueHolder<V> clone() throws CloneNotSupportedException
597 {
598 PersistedValueHolder<V> copy = ( PersistedValueHolder<V> ) super.clone();
599
600
601
602
603 if ( valueArray != null )
604 {
605 copy.valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), valueArray.length );
606 System.arraycopy( valueArray, 0, copy.valueArray, 0, valueArray.length );
607 }
608
609
610 if ( isRawUpToDate )
611 {
612 copy.raw = new byte[raw.length];
613 System.arraycopy( raw, 0, copy.raw, 0, raw.length );
614 }
615
616 return copy;
617 }
618
619
620
621
622
623 private void deserializeArray()
624 {
625
626
627 int index = 0;
628 int pos = 0;
629
630 while ( pos < raw.length )
631 {
632 try
633 {
634 int size = IntSerializer.deserialize( raw, pos );
635 pos += 4;
636
637 V value = valueSerializer.fromBytes( raw, pos );
638 pos += size;
639 valueArray[index++] = value;
640 }
641 catch ( IOException e )
642 {
643 e.printStackTrace();
644 }
645 }
646 }
647
648
649
650
651
652 private void deserializeSubBtree()
653 {
654
655 long offset = LongSerializer.deserialize( raw );
656
657
658 valueBtree = parentBtree.getRecordManager().loadDupsBTree( offset );
659 }
660
661
662
663
664
665
666 {
667 if ( valueArray == null )
668 {
669 return ( ( PersistedBTree<V, V> ) valueBtree ).getBtreeOffset();
670 }
671 else
672 {
673 return -1L;
674 }
675 }
676
677
678
679
680
681 public String toString()
682 {
683 StringBuilder sb = new StringBuilder();
684
685 sb.append( "ValueHolder[" ).append( valueSerializer.getClass().getSimpleName() );
686
687 if ( !isDeserialized )
688 {
689 sb.append( ", isRaw[" ).append( raw.length ).append( "]" );
690 }
691 else
692 {
693 if ( valueArray == null )
694 {
695 sb.append( ", SubBTree" );
696 }
697 else
698 {
699 sb.append( ", array{" );
700
701 if ( valueArray == null )
702 {
703 sb.append( "}" );
704 }
705 else
706 {
707 boolean isFirst = true;
708
709 for ( V value : valueArray )
710 {
711 if ( isFirst )
712 {
713 isFirst = false;
714 }
715 else
716 {
717 sb.append( "/" );
718 }
719
720 sb.append( value );
721 }
722
723 sb.append( "}" );
724 }
725 }
726 }
727
728 sb.append( "]" );
729
730 return sb.toString();
731 }
732 }