View Javadoc

1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  You may obtain a copy of the License at
9    *
10   *    http://www.apache.org/licenses/LICENSE-2.0
11   *
12   *  Unless required by applicable law or agreed to in writing,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License.
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   * A holder to store the Values
40   * 
41   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
42   * @param <V> The value type
43   */
44  public class ValueHolder<V> implements Cloneable
45  {
46      /** The deserialized value */
47      private V[] valueArray;
48  
49      /** The BTree storing multiple value, if we have more than a threshold values */
50      private BTree<V, V> valueBtree;
51  
52      /** The serialized value */
53      private byte[] raw;
54      
55      /** A flag set to true when the raw value has been deserialized */
56      private boolean isDeserialized = false;
57      
58      /** A flag to signal that the raw value represent the serialized values in their last state */
59      private boolean isRawUpToDate = false;
60  
61      /** The parent BTree */
62      private BTree<?, V> btree;
63  
64      /** The Value serializer */
65      private ElementSerializer<V> valueSerializer;
66  
67  
68      /**
69       * Creates a new instance of a ValueHolder, containing the serialized values.
70       * 
71       * @param btree the container BTree
72       * @param raw The raw data containing the values
73       * @param nbValues the number of stored values
74       * @param raw the byte[] containing either the serialized array of values or the sub-btree offset
75       */
76      /* No qualifier */ValueHolder( BTree<?, V> btree, int nbValues, byte[] raw )
77      {
78          this.btree = btree;
79          this.valueSerializer = btree.getValueSerializer();
80          this.raw = raw;
81          isRawUpToDate = true;
82  
83          // We create the array of values if they fit in an array. If they are stored in a 
84          // BTree, we do nothing atm.
85          if ( nbValues <= BTree.valueThresholdUp )
86          {
87              // The values are contained into an array
88              valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), nbValues );
89          }
90      }
91  
92  
93      /**
94       * Creates a new instance of a ValueHolder, containing Values. This constructor is called
95       * whe we need to create a new ValueHolder with deserialized values.
96       * 
97       * @param valueSerializer The Value's serializer
98       * @param values The Values stored in the ValueHolder
99       */
100     /* No qualifier */ValueHolder( BTree<?, V> btree, V... values )
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                 // Keep an array
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                 // Use a sub btree, now that we have reached the threshold
127                 createSubTree();
128 
129                 // Now inject all the values into it
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             // No value, we create an empty array
146             valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), 0 );
147         }
148         
149         isDeserialized = true;
150     }
151 
152 
153     /**
154      * @return a cursor on top of the values
155      */
156     public ValueCursor<V> getCursor()
157     {
158         ValueCursor<V> cursor;
159 
160         // Check that the values are deserialized before doing anything
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      * A class that encapsulate the values into an array
178      */
179     private class ValueArrayCursor implements ValueCursor<V>
180     {
181         /** Store the current position in the array or in the BTree */
182         private int currentPos;
183 
184 
185         /**
186          * Create an instance
187          */
188         private ValueArrayCursor()
189         {
190             // Start at -1 to be positioned before the first element
191             currentPos = BEFORE_FIRST;
192         }
193 
194 
195         /**
196          * {@inheritDoc}
197          */
198         @Override
199         public boolean hasNext()
200         {
201             return ( currentPos < valueArray.length - 1 ) && ( currentPos != AFTER_LAST );
202         }
203 
204 
205         /**
206          * {@inheritDoc}
207          */
208         public V next()
209         {
210             if ( valueArray == null )
211             {
212                 // Deserialize the array
213                 return null;
214             }
215             else
216             {
217                 currentPos++;
218 
219                 if ( currentPos == valueArray.length )
220                 {
221                     currentPos = AFTER_LAST;
222                     
223                     // We have reached the end of the array
224                     return null;
225                 }
226                 else
227                 {
228                     return valueArray[currentPos];
229                 }
230             }
231         }
232 
233 
234         /**
235          * {@inheritDoc}
236          */
237         @Override
238         public boolean hasPrev() throws EndOfFileExceededException, IOException
239         {
240             return currentPos > 0 || currentPos == AFTER_LAST;
241         }
242 
243 
244         /**
245          * {@inheritDoc}
246          */
247         @Override
248         public void close()
249         {
250         }
251 
252 
253         /**
254          * {@inheritDoc}
255          */
256         @Override
257         public void beforeFirst() throws IOException
258         {
259             currentPos = BEFORE_FIRST;
260         }
261 
262 
263         /**
264          * {@inheritDoc}
265          */
266         @Override
267         public void afterLast() throws IOException
268         {
269             currentPos = AFTER_LAST;
270         }
271 
272 
273         /**
274          * {@inheritDoc}
275          */
276         @Override
277         public V prev() throws EndOfFileExceededException, IOException
278         {
279             if ( valueArray == null )
280             {
281                 // Deserialize the array
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                     // We have reached the end of the array
298                     return null;
299                 }
300                 else
301                 {
302                     return valueArray[currentPos];
303                 }
304             }
305         }
306 
307 
308         /**
309          * {@inheritDoc}
310          */
311         @Override
312         public int size()
313         {
314             return valueArray.length;
315         }
316     }
317 
318     /**
319      * A class that encapsulate the values into an sub-btree
320      */
321     private class ValueBtreeCursor implements ValueCursor<V>
322     {
323         /** Store the current position in the array or in the BTree */
324         private TupleCursor<V, V> cursor;
325 
326 
327         /**
328          * Create an instance
329          */
330         private ValueBtreeCursor()
331         {
332             // Start at -1 to be positioned before the first element
333             try
334             {
335                 if ( valueBtree != null )
336                 {
337                     cursor = valueBtree.browse();
338                 }
339             }
340             catch ( IOException e )
341             {
342                 // TODO Auto-generated catch block
343                 e.printStackTrace();
344             }
345         }
346 
347 
348         /**
349          * {@inheritDoc}}
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          * {@inheritDoc}}
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          * {@inheritDoc}}
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          * {@inheritDoc}}
432          */
433         @Override
434         public void close()
435         {
436             if ( cursor != null )
437             {
438                 cursor.close();
439             }
440         }
441 
442 
443         /**
444          * {@inheritDoc}}
445          */
446         @Override
447         public void beforeFirst() throws IOException
448         {
449             if ( cursor != null )
450             {
451                 cursor.beforeFirst();
452             }
453         }
454 
455 
456         /**
457          * {@inheritDoc}}
458          */
459         @Override
460         public void afterLast() throws IOException
461         {
462             if ( cursor != null )
463             {
464                 cursor.afterLast();
465             }
466         }
467 
468 
469         /**
470          * {@inheritDoc}}
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          * {@inheritDoc}
494          */
495         @Override
496         public int size()
497         {
498             return ( int ) valueBtree.getNbElems();
499         }
500     }
501 
502 
503     /**
504      * @return the raw representation of the value holder. The serialized value will not be the same
505      * if the values are stored in an array or in a btree. <br/>
506      * If they are stored in a BTree, the raw value will contain the offset of the btree, otherwise
507      * it will contain a byte[] which will contain each serialized value, prefixed by their length. 
508      * 
509      */
510     /* No qualifier*/ byte[] getRaw()
511     {
512         if ( isRawUpToDate )
513         {
514             // Just have to return the raw value
515             return raw;
516         }
517 
518         if ( isSubBtree() )
519         {
520             // The values are stored into a subBtree, return the offset of this subBtree
521             long btreeOffset = valueBtree.getBtreeOffset();
522             raw = LongSerializer.serialize( btreeOffset );
523         }
524         else
525         {
526             // Create as many byte[] as we have length and serialized values to store
527             byte[][] valueBytes = new byte[valueArray.length * 2][];
528             int length = 0;
529             int pos = 0;
530     
531             // Process each value now
532             for ( V value : valueArray )
533             {
534                 // Serialize the value
535                 byte[] bytes = valueSerializer.serialize( value );
536                 length += bytes.length;
537     
538                 // Serialize the value's length
539                 byte[] sizeBytes = IntSerializer.serialize( bytes.length );
540                 length += sizeBytes.length;
541     
542                 // And store the two byte[]
543                 valueBytes[pos++] = sizeBytes;
544                 valueBytes[pos++] = bytes;
545             }
546     
547             // Last, not least, create a buffer large enough to contain all the created byte[],
548             // and copy all those byte[] into this buffer
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         // Update the flags
560         isRawUpToDate = true;
561 
562         return raw;
563     }
564 
565 
566     /**
567      * @return the isSubBtree
568      */
569     public boolean isSubBtree()
570     {
571         return valueArray == null;
572     }
573 
574 
575     /**
576      * @return the number of stored values
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      * Create a new Sub-BTree to store the values.
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                 // should never happen
618                 throw new RuntimeException( e );
619             }
620         }
621         catch ( IOException e )
622         {
623             throw new RuntimeException( e );
624         }
625     }
626 
627 
628     /**
629      * Set the subBtree in the ValueHolder
630      */
631     /* No qualifier*/void setSubBtree( BTree<V, V> subBtree )
632     {
633         valueBtree = subBtree;
634         raw = null;
635         valueArray = null;
636         isDeserialized = true;
637         isRawUpToDate = false;
638     }
639     
640     
641     /**
642      * Check that the values are stored as raw value
643      */
644     private void checkAndDeserialize()
645     {
646         if ( !isDeserialized )
647         {
648             if ( valueArray == null )
649             {
650                 // the values are stored into a sub-btree. Read it now if it's not already done
651                 deserializeSubBtree();
652             }
653             else
654             {
655                 // The values are stored into an array. Deserialize it now
656                 deserializeArray();
657             }
658 
659             // Change the flag
660             isDeserialized = true;
661         }
662     }
663     
664     /**
665      * Add the value in an array
666      */
667     private void addInArray( V value )
668     {
669         checkAndDeserialize();
670 
671         // We have to check that we have reached the threshold or not
672         if ( valueArray.length >= BTree.valueThresholdUp )
673         {
674             // Ok, transform the array into a btree
675             createSubTree();
676 
677             try
678             {
679                 for ( V val : valueArray )
680                 {
681                     // Here, we should insert all the values in one shot then 
682                     // write the btree on disk only once.
683                     valueBtree.insert( val, null );
684                 }
685 
686                 // We can delete the array now
687                 valueArray = null;
688 
689                 // And inject the new value
690                 valueBtree.insert( value, null );
691             }
692             catch ( IOException e )
693             {
694                 // TODO Auto-generated catch block
695                 e.printStackTrace();
696             }
697         }
698         else
699         {
700             // First check that the value is not already present in the ValueHolder
701             int pos = findPos( value );
702 
703             if ( pos >= 0 )
704             {
705                 // The value exists : nothing to do
706                 return;
707             }
708 
709             // Ok, we just have to insert the new element at the right position
710             // We transform the position to a positive value 
711             pos = -( pos + 1 );
712             // First, copy the array
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             // And switch the arrays
720             valueArray = newValueArray;
721         }
722     }
723     
724 
725     /**
726      * Add the value in the subBTree
727      */
728     private void addInBtree( V value )
729     {
730         // First check that we have a loaded BTree
731         checkAndDeserialize();
732         
733         try
734         {
735             valueBtree.insert( value, null );
736         }
737         catch ( IOException e )
738         {
739             // TODO Auto-generated catch block
740             e.printStackTrace();
741         }
742     }
743 
744 
745     /**
746      * Add a new value in the ValueHolder
747      * 
748      * @param value The added value
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         // The raw value is not anymore up to date with the content
762         isRawUpToDate = false;
763         raw = null;
764     }
765     
766     
767     /**
768      * Remove a value from an array
769      */
770     private V removeFromArray( V value )
771     {
772         checkAndDeserialize();
773 
774         // First check that the value is not already present in the ValueHolder
775         int pos = findPos( value );
776 
777         if ( pos < 0 )
778         {
779             // The value does not exists : nothing to do
780             return null;
781         }
782 
783         // Ok, we just have to delete the new element at the right position
784         // First, copy the array
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         // Get the removed element
791         V removedValue = valueArray[pos];
792         
793         // And switch the arrays
794         valueArray = newValueArray;
795         
796         return removedValue;
797     }
798 
799     
800     /**
801      * Remove the value from a sub btree
802      */
803     private V removeFromBtree( V removedValue )
804     {
805         // First check that we have a loaded BTree
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                     // We have to switch to an Array of values
817                     valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), nbValues );
818     
819                     // Now copy all the value but the one we have removed
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                             // This is the removed value : skip it
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                 // TODO Auto-generated catch block
860                 e.printStackTrace();
861                 return null;
862             }
863         }
864         else
865         {
866             return null;
867         }
868     }
869 
870     /**
871      * Add a new value in the ValueHolder
872      * 
873      * @param value The added value
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         // The raw value is not anymore up to date wth the content
889         isRawUpToDate = false;
890         raw = null;
891         
892         return removedValue;
893     }
894     
895     
896     /**
897      * Check if the array of values contains a given value
898      */
899     private boolean arrayContains( V value )
900     {
901         // First, deserialize the value if it's still a byte[]
902         checkAndDeserialize();
903         
904         if ( valueArray.length == 0 )
905         {
906             return false;
907         }
908 
909         // Do a search using dichotomy
910         return findPos( value ) >= 0;
911     }
912     
913     
914     /**
915      * Check if the subBtree contains a given value
916      */
917     private boolean btreeContains( V value )
918     {
919         // First, deserialize the value if it's still a byte[]
920         checkAndDeserialize();
921         
922         try
923         {
924             return valueBtree.hasKey( value );
925         }
926         catch ( IOException e )
927         {
928             // TODO Auto-generated catch block
929             e.printStackTrace();
930             return false;
931         }
932     }
933 
934 
935     /**
936      * Add a new value in the ValueHolder
937      * 
938      * @param value The added value
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      * Find the position of a given value in the array, or the position where we
955      * would insert the element (in this case, the position will be negative).
956      * As we use a 0-based array, the negative position for 0 is -1.
957      * -1 means the element can be added in position 0
958      * -2 means the element can be added in position 1
959      * ... 
960      */
961     private int findPos( V value )
962     {
963         if ( valueArray.length == 0 )
964         {
965             return -1;
966         }
967 
968         // Do a search using dichotomy
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                     // We have 2 elements
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                     // We have 3 elements
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      * Create a clone of this instance
1082      */
1083     public ValueHolder<V> clone() throws CloneNotSupportedException
1084     {
1085         ValueHolder<V> copy = ( ValueHolder<V> ) super.clone();
1086 
1087         // copy the valueArray if it's not null
1088         // We don't clone the BTree, as we will create new revisions when 
1089         // modifying it
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         // Also clone the raw value if its up to date
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      * Deserialize the values stored in an array
1109      */
1110     private void deserializeArray()
1111     {
1112         // We haven't yet deserialized the values. Let's do it now. The values are
1113         // necessarily stored in an array at this point
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      * Deserialize the values stored in a sub-btree
1138      */
1139     private void deserializeSubBtree()
1140     {
1141         // Get the sub-btree offset
1142         long offset = LongSerializer.deserialize( raw );
1143         
1144         // and reload the sub btree
1145         valueBtree = btree.getRecordManager().loadDupsBTree( offset );
1146     }
1147 
1148     /**
1149      * @return The sub-btree offset
1150      */
1151     /* No qualifier */long getOffset()
1152     {
1153         if ( valueArray == null )
1154         {
1155             return valueBtree.getBtreeOffset();
1156         }
1157         else
1158         {
1159             return -1L;
1160         }
1161     }
1162 
1163 
1164     /**
1165      * @see Object#toString()
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 }