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.memory;
21  
22  
23  import java.io.IOException;
24  import java.util.Comparator;
25  import java.util.UUID;
26  
27  import org.apache.directory.mavibot.btree.Tuple;
28  import org.apache.directory.mavibot.btree.TupleCursor;
29  import org.apache.directory.mavibot.btree.ValueCursor;
30  import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
31  
32  
33  /**
34   * A holder to store the Values
35   * 
36   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
37   * @param <V> The value type
38   */
39  public class ValueHolder<V> implements Cloneable
40  {
41      /** The deserialized value */
42      private V value;
43  
44      /** The BTree storing multiple value, if we have more than one value */
45      private BTree<V, V> valueBtree;
46  
47      /** The RecordManager */
48      private BTree<?, V> btree;
49  
50  
51      /**
52       * A class that encapsulate one single value
53       */
54      private class ValueSingletonCursor implements ValueCursor<V>
55      {
56          /** Store the current position in the array or in the BTree */
57          private int currentPos;
58  
59  
60          /**
61           * Create an instance
62           */
63          private ValueSingletonCursor()
64          {
65              // Start at -1 to be positioned before the first element
66              currentPos = BEFORE_FIRST;
67          }
68  
69  
70          /**
71           * {@inheritDoc}
72           */
73          @Override
74          public boolean hasNext()
75          {
76              return currentPos == BEFORE_FIRST;
77          }
78  
79  
80          /**
81           * {@inheritDoc}
82           */
83          public V next()
84          {
85              switch ( currentPos )
86              {
87                  case AFTER_LAST :
88                      return null;
89                      
90                  case BEFORE_FIRST :
91                      currentPos = 0;
92                      return value;
93                      
94                  default :
95                      currentPos = AFTER_LAST;
96                      return null;
97              }
98          }
99  
100 
101         /**
102          * {@inheritDoc}
103          */
104         @Override
105         public boolean hasPrev()
106         {
107             return currentPos > 0 || currentPos == AFTER_LAST;
108         }
109 
110 
111         /**
112          * {@inheritDoc}
113          */
114         @Override
115         public void close()
116         {
117         }
118 
119 
120         /**
121          * {@inheritDoc}
122          */
123         @Override
124         public void beforeFirst() throws IOException
125         {
126             currentPos = BEFORE_FIRST;
127         }
128 
129 
130         /**
131          * {@inheritDoc}
132          */
133         @Override
134         public void afterLast() throws IOException
135         {
136             currentPos = AFTER_LAST;
137         }
138 
139 
140         /**
141          * {@inheritDoc}
142          */
143         @Override
144         public V prev() throws EndOfFileExceededException, IOException
145         {
146             switch ( currentPos )
147             {
148                 case AFTER_LAST :
149                     currentPos = 0;
150                     return value;
151                     
152                 case BEFORE_FIRST :
153                     return null;
154                     
155                 default :
156                     currentPos = BEFORE_FIRST;
157                     return null;
158             }
159         }
160 
161 
162         /**
163          * {@inheritDoc}
164          */
165         @Override
166         public int size()
167         {
168             return 1;
169         }
170 
171 
172         /**
173          * @see Object#toString()
174          */
175         public String toString()
176         {
177             StringBuilder sb = new StringBuilder();
178             
179             sb.append( "SingletonCursor , currentpos =" );
180             
181             switch ( currentPos ) 
182             {
183                 case BEFORE_FIRST :
184                     sb.append(  "BEFORE_FIRST" );
185                     break;
186                     
187                 case AFTER_LAST :
188                     sb.append(  "AFTER_LAST" );
189                     break;
190                     
191                 default :
192                     sb.append( "0/0" );
193                     break;
194             }
195             
196             return sb.toString();
197         }
198     }
199 
200     
201     /**
202      * A class that encapsulate the values into an sub-btree
203      */
204     private class ValueBtreeCursor implements ValueCursor<V>
205     {
206         /** Store the current position in the array or in the BTree */
207         private TupleCursor<V, V> cursor;
208 
209 
210         /**
211          * Create an instance
212          */
213         private ValueBtreeCursor()
214         {
215             // Start at -1 to be positioned before the first element
216             try
217             {
218                 if ( valueBtree != null )
219                 {
220                     cursor = valueBtree.browse();
221                 }
222             }
223             catch ( IOException e )
224             {
225                 // TODO Auto-generated catch block
226                 e.printStackTrace();
227             }
228         }
229 
230 
231         /**
232          * {@inheritDoc}}
233          */
234         @Override
235         public boolean hasNext()
236         {
237             if ( cursor == null )
238             {
239                 return false;
240             }
241             else
242             {
243                 try
244                 {
245                     return cursor.hasNext();
246                 }
247                 catch ( EndOfFileExceededException e )
248                 {
249                     e.printStackTrace();
250                     return false;
251                 }
252                 catch ( IOException e )
253                 {
254                     e.printStackTrace();
255                     return false;
256                 }
257             }
258         }
259 
260 
261         /**
262          * {@inheritDoc}}
263          */
264         public V next()
265         {
266             try
267             {
268                 return cursor.next().getKey();
269             }
270             catch ( EndOfFileExceededException e )
271             {
272                 e.printStackTrace();
273                 return null;
274             }
275             catch ( IOException e )
276             {
277                 e.printStackTrace();
278                 return null;
279             }
280         }
281 
282 
283         /**
284          * {@inheritDoc}}
285          */
286         @Override
287         public boolean hasPrev() throws EndOfFileExceededException, IOException
288         {
289             if ( cursor == null )
290             {
291                 return false;
292             }
293             else
294             {
295                 try
296                 {
297                     return cursor.hasPrev();
298                 }
299                 catch ( EndOfFileExceededException e )
300                 {
301                     e.printStackTrace();
302                     return false;
303                 }
304                 catch ( IOException e )
305                 {
306                     e.printStackTrace();
307                     return false;
308                 }
309             }
310         }
311 
312 
313         /**
314          * {@inheritDoc}}
315          */
316         @Override
317         public void close()
318         {
319             if ( cursor != null )
320             {
321                 cursor.close();
322             }
323         }
324 
325 
326         /**
327          * {@inheritDoc}}
328          */
329         @Override
330         public void beforeFirst() throws IOException
331         {
332             if ( cursor != null )
333             {
334                 cursor.beforeFirst();
335             }
336         }
337 
338 
339         /**
340          * {@inheritDoc}}
341          */
342         @Override
343         public void afterLast() throws IOException
344         {
345             if ( cursor != null )
346             {
347                 cursor.afterLast();
348             }
349         }
350 
351 
352         /**
353          * {@inheritDoc}}
354          */
355         @Override
356         public V prev() throws EndOfFileExceededException, IOException
357         {
358             try
359             {
360                 return cursor.prev().getKey();
361             }
362             catch ( EndOfFileExceededException e )
363             {
364                 e.printStackTrace();
365                 return null;
366             }
367             catch ( IOException e )
368             {
369                 e.printStackTrace();
370                 return null;
371             }
372         }
373 
374 
375         /**
376          * {@inheritDoc}
377          */
378         @Override
379         public int size()
380         {
381             return ( int ) valueBtree.getNbElems();
382         }
383 
384 
385         /**
386          * @see Object#toString()
387          */
388         public String toString()
389         {
390             return "BTreeCursor";
391         }
392     }
393 
394     /**
395      * Creates a new instance of a ValueHolder, containing the serialized values.
396      * 
397      * @param btree the container BTree
398      * @param valueSerializer The Value's serializer
399      * @param raw The raw data containing the values
400      * @param nbValues the number of stored values
401      * @param raw the byte[] containing either the serialized array of values or the sub-btree offset
402      */
403     /* No qualifier */ValueHolder( BTree<?, V> btree, int nbValues )
404     {
405         this.btree = btree;
406     }
407 
408 
409     /**
410      * Creates a new instance of a ValueHolder, containing Values. This constructor is called
411      * whe we need to create a new ValueHolder with deserialized values.
412      * 
413      * @param valueSerializer The Value's serializer
414      * @param values The Values stored in the ValueHolder
415      */
416     /* No qualifier */ValueHolder( BTree<?, V> btree, V... values )
417     {
418         this.btree = btree;
419 
420         if ( ( values != null ) && ( values.length > 0 ) )
421         {
422             int nbValues = values.length;
423 
424             if ( nbValues < 2 )
425             {
426                 // Store the value
427                 value = values[0];
428             }
429             else
430             {
431                 // Use a sub btree, now that we have reached the threshold
432                 createSubTree();
433 
434                 // Now inject all the values into it
435                 for ( V value : values )
436                 {
437                     try
438                     {
439                         valueBtree.insert( value, value );
440                     }
441                     catch ( IOException e )
442                     {
443                         e.printStackTrace();
444                     }
445                 }
446             }
447         }
448     }
449 
450 
451     /**
452      * @return a cursor on top of the values
453      */
454     public ValueCursor<V> getCursor()
455     {
456         ValueCursor<V> cursor;
457 
458         if ( valueBtree != null )
459         {
460             cursor = new ValueBtreeCursor();
461         }
462         else
463         {
464             cursor = new ValueSingletonCursor();
465         }
466 
467         return cursor;
468     }
469 
470 
471     /**
472      * @return the isSubBtree
473      */
474     public boolean isSubBtree()
475     {
476         return valueBtree != null;
477     }
478 
479 
480     /**
481      * @return the number of stored values
482      */
483     public int size()
484     {
485         if ( valueBtree != null )
486         {
487             return ( int ) valueBtree.getNbElems();
488         }
489         else
490         {
491             return 1;
492         }
493     }
494 
495 
496     /**
497      * Create a new Sub-BTree to store the values.
498      */
499     private void createSubTree()
500     {
501         try
502         {
503             BTreeConfiguration<V, V> configuration = new BTreeConfiguration<V, V>();
504             configuration.setAllowDuplicates( false );
505             configuration.setName( UUID.randomUUID().toString() );
506             
507             valueBtree = new BTree<V, V>( configuration );
508         }
509         catch ( IOException e )
510         {
511             throw new RuntimeException( e );
512         }
513     }
514 
515 
516     /**
517      * Set the subBtree in the ValueHolder
518      */
519     /* No qualifier*/void setSubBtree( BTree<V, V> subBtree )
520     {
521         valueBtree = subBtree;
522         value = null;
523     }
524     
525     
526     /**
527      * Add the value in an array
528      */
529     private void addInBTree( V newValue )
530     {
531         // Ok, create a sub-btree
532         try
533         {
534             valueBtree = new BTree<V, V>( UUID.randomUUID().toString(), btree.getValueSerializer(),
535                 btree.getValueSerializer() );
536 
537             valueBtree.insert( value, null, 0 );
538             valueBtree.insert( newValue, null, 0 );
539             value = null;
540         }
541         catch ( IOException e )
542         {
543             throw new RuntimeException( e );
544         }
545     }
546 
547 
548     /**
549      * Add a new value in the ValueHolder
550      * 
551      * @param newValue The added value
552      */
553     public void add( V newValue )
554     {
555         if ( value != null )
556         {
557             try
558             {
559                 valueBtree = new BTree<V, V>( UUID.randomUUID().toString(), btree.getValueSerializer(),
560                     btree.getValueSerializer() );
561 
562                 valueBtree.insert( value, null, 0 );
563                 valueBtree.insert( newValue, null, 0 );
564                 value = null;
565             }
566             catch ( IOException e )
567             {
568                 throw new RuntimeException( e );
569             }
570         }
571         else if ( valueBtree != null )
572         {
573             try
574             {
575                 valueBtree.insert( newValue, null, 0 );
576             }
577             catch ( IOException e )
578             {
579                 throw new RuntimeException( e );
580             }
581         }
582         else
583         {
584             this.value = newValue;
585         }
586     }
587     
588     
589     /**
590      * Remove a value from the ValueHolder
591      * 
592      * @param removedValue The value to remove
593      */
594     public V remove( V removedValue )
595     {
596         if ( valueBtree == null )
597         {
598             if ( removedValue == null )
599             {
600                 return null; 
601             }
602             
603             Comparator<V> comparator = btree.getValueSerializer().getComparator();
604 
605             int result = comparator.compare( removedValue, value );
606 
607             if ( result != 0 )
608             {
609                 // The value does not exists : nothing to do
610                 return null;
611             }
612             else
613             {
614                 V returnedValue = value;
615                 value = null;
616                 
617                 return returnedValue;
618             }
619         }
620         else
621         {
622             V returnedValue = null;
623             
624             try
625             {
626                 Tuple<V, V> removedTuple = valueBtree.delete( removedValue );
627                 
628                 if ( removedTuple != null )
629                 {
630                     returnedValue = removedTuple.getKey();
631                 }
632             }
633             catch ( IOException e )
634             {
635                 throw new RuntimeException( e );
636             }
637 
638             if ( valueBtree.getNbElems() == 1 )
639             {
640                 try
641                 {
642                     value = valueBtree.browse().next().getKey();
643                     valueBtree.close();
644                     valueBtree = null;
645                 }
646                 catch ( EndOfFileExceededException e )
647                 {
648                     throw new RuntimeException( e );
649                 }
650                 catch ( IOException e )
651                 {
652                     throw new RuntimeException( e );
653                 }
654             }
655             
656             return returnedValue;
657         }
658     }
659     
660     
661     /**
662      * Check that a value exists in the ValueHolder
663      * 
664      * @param checkedValue The value to check
665      */
666     public boolean contains( V checkedValue )
667     {
668         if ( valueBtree != null )
669         {
670             try
671             {
672                 return valueBtree.hasKey( checkedValue );
673             }
674             catch ( IOException e )
675             {
676                 // TODO Auto-generated catch block
677                 e.printStackTrace();
678                 return false;
679             }
680         }
681         else
682         {
683             Comparator<V> comparator = btree.getValueSerializer().getComparator();
684 
685             int result = comparator.compare( checkedValue, value );
686             
687             return result == 0;
688         }
689     }
690 
691 
692     /**
693      * Find the position of a given value in the array, or the position where we
694      * would insert the element (in this case, the position will be negative).
695      * As we use a 0-based array, the negative position for 0 is -1.
696      * -1 means the element can be added in position 0
697      * -2 means the element can be added in position 1
698      * ... 
699      */
700     private int findPos1( V findValue )
701     {
702         if ( findValue == null )
703         {
704             return -1;
705         }
706 
707         Comparator<V> comparator = btree.getValueSerializer().getComparator();
708 
709         int result = comparator.compare( findValue, value );
710         
711         return result;
712     }
713 
714 
715     /**
716      * Create a clone of this instance
717      */
718     public ValueHolder<V> clone() throws CloneNotSupportedException
719     {
720         ValueHolder<V> copy = ( ValueHolder<V> ) super.clone();
721 
722         return copy;
723     }
724 
725 
726     /**
727      * @see Object#toString()
728      */
729     public String toString()
730     {
731         StringBuilder sb = new StringBuilder();
732 
733         sb.append( "ValueHolder[" ).append( btree.getValueSerializer().getClass().getSimpleName() );
734 
735         if ( valueBtree != null )
736         {
737             sb.append( ", SubBTree" );
738         }
739         else
740         {
741             sb.append( ", {" );
742             sb.append( value );
743             sb.append( "}" );
744         }
745         
746         sb.append( "]" );
747 
748         return sb.toString();
749     }
750 }