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;
21  
22  
23  import java.io.IOException;
24  import java.util.LinkedList;
25  
26  import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
27  
28  
29  /**
30   * This class construct a BTree from a serialized version of a BTree. We need it
31   * to avoid exposing all the methods of the BTree class.<br>
32   * 
33   * All its methods are static.
34   *  
35   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
36   *
37   * @param <K> The BTree key type
38   * @param <V> The BTree valye type
39   */
40  public class BTreeFactory<K, V>
41  {
42      //--------------------------------------------------------------------------------------------
43      // Create persisted btrees
44      //--------------------------------------------------------------------------------------------
45  
46      /**
47       * Creates a new persisted BTree, with no initialization. 
48       */
49      public static <K, V> BTree<K, V> createPersistedBTree()
50      {
51          BTree<K, V> btree = new PersistedBTree<K, V>();
52  
53          return btree;
54      }
55  
56  
57      /**
58       * Creates a new persisted BTree using the BTreeConfiguration to initialize the 
59       * BTree
60       * 
61       * @param configuration The configuration to use
62       */
63      public static <K, V> BTree<K, V> createPersistedBTree( PersistedBTreeConfiguration<K, V> configuration )
64      {
65          BTree<K, V> btree = new PersistedBTree<K, V>( configuration );
66  
67          return btree;
68      }
69  
70  
71      /**
72       * Creates a new persisted BTree using the parameters to initialize the 
73       * BTree
74       * 
75       * @param name The BTree's name
76       * @param keySerializer Key serializer
77       * @param valueSerializer Value serializer
78       * @param allowDuplicates Tells if the BTree allows multiple value for a given key
79       * @throws IOException
80       */
81      public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer,
82          ElementSerializer<V> valueSerializer )
83      {
84          PersistedBTreeConfiguration<K, V> configuration = new PersistedBTreeConfiguration<K, V>();
85  
86          configuration.setName( name );
87          configuration.setKeySerializer( keySerializer );
88          configuration.setValueSerializer( valueSerializer );
89          configuration.setPageSize( BTree.DEFAULT_PAGE_SIZE );
90          configuration.setAllowDuplicates( BTree.FORBID_DUPLICATES );
91          configuration.setCacheSize( PersistedBTree.DEFAULT_CACHE_SIZE );
92          configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
93  
94          BTree<K, V> btree = new PersistedBTree<K, V>( configuration );
95  
96          return btree;
97      }
98  
99  
100     /**
101      * Creates a new persisted BTree using the parameters to initialize the 
102      * BTree
103      * 
104      * @param name The BTree's name
105      * @param keySerializer Key serializer
106      * @param valueSerializer Value serializer
107      * @param allowDuplicates Tells if the BTree allows multiple value for a given key
108      * @throws IOException
109      */
110     public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer,
111         ElementSerializer<V> valueSerializer, boolean allowDuplicates )
112     {
113         PersistedBTreeConfiguration<K, V> configuration = new PersistedBTreeConfiguration<K, V>();
114 
115         configuration.setName( name );
116         configuration.setKeySerializer( keySerializer );
117         configuration.setValueSerializer( valueSerializer );
118         configuration.setPageSize( BTree.DEFAULT_PAGE_SIZE );
119         configuration.setAllowDuplicates( allowDuplicates );
120         configuration.setCacheSize( PersistedBTree.DEFAULT_CACHE_SIZE );
121         configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
122 
123         BTree<K, V> btree = new PersistedBTree<K, V>( configuration );
124 
125         return btree;
126     }
127 
128 
129     /**
130      * Creates a new persisted BTree using the parameters to initialize the 
131      * BTree
132      * 
133      * @param name The BTree's name
134      * @param keySerializer Key serializer
135      * @param valueSerializer Value serializer
136      * @param allowDuplicates Tells if the BTree allows multiple value for a given key
137      * @param cacheSize The size to be used for this BTree cache
138      * @throws IOException
139      */
140     public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer,
141         ElementSerializer<V> valueSerializer, boolean allowDuplicates, int cacheSize )
142     {
143         PersistedBTreeConfiguration<K, V> configuration = new PersistedBTreeConfiguration<K, V>();
144 
145         configuration.setName( name );
146         configuration.setKeySerializer( keySerializer );
147         configuration.setValueSerializer( valueSerializer );
148         configuration.setPageSize( BTree.DEFAULT_PAGE_SIZE );
149         configuration.setAllowDuplicates( allowDuplicates );
150         configuration.setCacheSize( cacheSize );
151         configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
152 
153         BTree<K, V> btree = new PersistedBTree<K, V>( configuration );
154 
155         return btree;
156     }
157 
158 
159     /**
160      * Creates a new persisted BTree using the parameters to initialize the 
161      * BTree
162      * 
163      * @param name The BTree's name
164      * @param keySerializer Key serializer
165      * @param valueSerializer Value serializer
166      * @param pageSize Size of the page
167      * @throws IOException
168      */
169     public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer,
170         ElementSerializer<V> valueSerializer, int pageSize )
171     {
172         PersistedBTreeConfiguration<K, V> configuration = new PersistedBTreeConfiguration<K, V>();
173 
174         configuration.setName( name );
175         configuration.setKeySerializer( keySerializer );
176         configuration.setValueSerializer( valueSerializer );
177         configuration.setPageSize( pageSize );
178         configuration.setAllowDuplicates( BTree.FORBID_DUPLICATES );
179         configuration.setCacheSize( PersistedBTree.DEFAULT_CACHE_SIZE );
180         configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
181 
182         BTree<K, V> btree = new PersistedBTree<K, V>( configuration );
183 
184         return btree;
185     }
186 
187 
188     /**
189      * Creates a new persisted BTree using the parameters to initialize the 
190      * BTree
191      * 
192      * @param name The BTree's name
193      * @param keySerializer Key serializer
194      * @param valueSerializer Value serializer
195      * @param pageSize Size of the page
196      * @param allowDuplicates Tells if the BTree allows multiple value for a given key
197      * @throws IOException
198      */
199     public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer,
200         ElementSerializer<V> valueSerializer, int pageSize, boolean allowDuplicates )
201     {
202         PersistedBTreeConfiguration<K, V> configuration = new PersistedBTreeConfiguration<K, V>();
203 
204         configuration.setName( name );
205         configuration.setKeySerializer( keySerializer );
206         configuration.setValueSerializer( valueSerializer );
207         configuration.setPageSize( pageSize );
208         configuration.setAllowDuplicates( allowDuplicates );
209         configuration.setCacheSize( PersistedBTree.DEFAULT_CACHE_SIZE );
210         configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
211 
212         BTree<K, V> btree = new PersistedBTree<K, V>( configuration );
213 
214         return btree;
215     }
216 
217 
218     /**
219      * Creates a new persisted BTree using the parameters to initialize the 
220      * BTree
221      * 
222      * @param name The BTree's name
223      * @param keySerializer Key serializer
224      * @param valueSerializer Value serializer
225      * @param pageSize Size of the page
226      * @param allowDuplicates Tells if the BTree allows multiple value for a given key
227      * @param cacheSize The size to be used for this BTree cache
228      * @throws IOException
229      */
230     public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer,
231         ElementSerializer<V> valueSerializer, int pageSize, boolean allowDuplicates, int cacheSize )
232     {
233         PersistedBTreeConfiguration<K, V> configuration = new PersistedBTreeConfiguration<K, V>();
234 
235         configuration.setName( name );
236         configuration.setKeySerializer( keySerializer );
237         configuration.setValueSerializer( valueSerializer );
238         configuration.setPageSize( pageSize );
239         configuration.setAllowDuplicates( allowDuplicates );
240         configuration.setCacheSize( cacheSize );
241         configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
242 
243         BTree<K, V> btree = new PersistedBTree<K, V>( configuration );
244 
245         return btree;
246     }
247 
248 
249     //--------------------------------------------------------------------------------------------
250     // Create in-memory btrees
251     //--------------------------------------------------------------------------------------------
252     /**
253      * Creates a new in-memory BTree, with no initialization. 
254      */
255     public static <K, V> BTree<K, V> createInMemoryBTree()
256     {
257         BTree<K, V> btree = new InMemoryBTree<K, V>();
258 
259         return btree;
260     }
261 
262 
263     /**
264      * Creates a new in-memory BTree using the BTreeConfiguration to initialize the 
265      * BTree
266      * 
267      * @param configuration The configuration to use
268      */
269     public static <K, V> BTree<K, V> createInMemoryBTree( InMemoryBTreeConfiguration<K, V> configuration )
270     {
271         BTree<K, V> btree = new InMemoryBTree<K, V>( configuration );
272 
273         return btree;
274     }
275 
276 
277     /**
278      * Creates a new in-memory BTree using the parameters to initialize the 
279      * BTree
280      * 
281      * @param name The BTree's name
282      * @param keySerializer Key serializer
283      * @param valueSerializer Value serializer
284      */
285     public static <K, V> BTree<K, V> createInMemoryBTree( String name, ElementSerializer<K> keySerializer,
286         ElementSerializer<V> valueSerializer )
287     {
288         InMemoryBTreeConfiguration<K, V> configuration = new InMemoryBTreeConfiguration<K, V>();
289 
290         configuration.setName( name );
291         configuration.setKeySerializer( keySerializer );
292         configuration.setValueSerializer( valueSerializer );
293         configuration.setPageSize( BTree.DEFAULT_PAGE_SIZE );
294         configuration.setAllowDuplicates( BTree.FORBID_DUPLICATES );
295         configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
296 
297         BTree<K, V> btree = new InMemoryBTree<K, V>( configuration );
298 
299         return btree;
300     }
301 
302 
303     /**
304      * Creates a new in-memory BTree using the parameters to initialize the 
305      * BTree
306      * 
307      * @param name The BTree's name
308      * @param keySerializer Key serializer
309      * @param valueSerializer Value serializer
310      * @param allowDuplicates Tells if the BTree allows multiple value for a given key
311      * @throws IOException
312      */
313     public static <K, V> BTree<K, V> createInMemoryBTree( String name, ElementSerializer<K> keySerializer,
314         ElementSerializer<V> valueSerializer, boolean allowDuplicates )
315     {
316         InMemoryBTreeConfiguration<K, V> configuration = new InMemoryBTreeConfiguration<K, V>();
317 
318         configuration.setName( name );
319         configuration.setKeySerializer( keySerializer );
320         configuration.setValueSerializer( valueSerializer );
321         configuration.setPageSize( BTree.DEFAULT_PAGE_SIZE );
322         configuration.setAllowDuplicates( allowDuplicates );
323         configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
324 
325         BTree<K, V> btree = new InMemoryBTree<K, V>( configuration );
326 
327         return btree;
328     }
329 
330 
331     /**
332      * Creates a new in-memory BTree using the parameters to initialize the 
333      * BTree
334      * 
335      * @param name The BTree's name
336      * @param keySerializer Key serializer
337      * @param valueSerializer Value serializer
338      * @param pageSize Size of the page
339      * @throws IOException
340      */
341     public static <K, V> BTree<K, V> createInMemoryBTree( String name, ElementSerializer<K> keySerializer,
342         ElementSerializer<V> valueSerializer, int pageSize )
343     {
344         InMemoryBTreeConfiguration<K, V> configuration = new InMemoryBTreeConfiguration<K, V>();
345 
346         configuration.setName( name );
347         configuration.setKeySerializer( keySerializer );
348         configuration.setValueSerializer( valueSerializer );
349         configuration.setPageSize( pageSize );
350         configuration.setAllowDuplicates( BTree.FORBID_DUPLICATES );
351         configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
352 
353         BTree<K, V> btree = new InMemoryBTree<K, V>( configuration );
354 
355         return btree;
356     }
357 
358 
359     /**
360      * Creates a new in-memory BTree using the parameters to initialize the 
361      * BTree
362      * 
363      * @param name The BTree's name
364      * @param filePath The name of the data directory with absolute path
365      * @param keySerializer Key serializer
366      * @param valueSerializer Value serializer
367      * @throws IOException
368      */
369     public static <K, V> BTree<K, V> createInMemoryBTree( String name, String filePath,
370         ElementSerializer<K> keySerializer,
371         ElementSerializer<V> valueSerializer )
372     {
373         InMemoryBTreeConfiguration<K, V> configuration = new InMemoryBTreeConfiguration<K, V>();
374 
375         configuration.setName( name );
376         configuration.setFilePath( filePath );
377         configuration.setKeySerializer( keySerializer );
378         configuration.setValueSerializer( valueSerializer );
379         configuration.setPageSize( BTree.DEFAULT_PAGE_SIZE );
380         configuration.setAllowDuplicates( BTree.FORBID_DUPLICATES );
381         configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
382 
383         BTree<K, V> btree = new InMemoryBTree<K, V>( configuration );
384 
385         return btree;
386     }
387 
388 
389     /**
390      * Creates a new in-memory BTree using the parameters to initialize the 
391      * BTree
392      * 
393      * @param name The BTree's name
394      * @param filePath The name of the data directory with absolute path
395      * @param keySerializer Key serializer
396      * @param valueSerializer Value serializer
397      * @param pageSize Size of the page
398      * @throws IOException
399      */
400     public static <K, V> BTree<K, V> createInMemoryBTree( String name, String filePath,
401         ElementSerializer<K> keySerializer,
402         ElementSerializer<V> valueSerializer, int pageSize )
403     {
404         InMemoryBTreeConfiguration<K, V> configuration = new InMemoryBTreeConfiguration<K, V>();
405 
406         configuration.setName( name );
407         configuration.setFilePath( filePath );
408         configuration.setKeySerializer( keySerializer );
409         configuration.setValueSerializer( valueSerializer );
410         configuration.setPageSize( pageSize );
411         configuration.setAllowDuplicates( BTree.FORBID_DUPLICATES );
412         configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
413 
414         BTree<K, V> btree = new InMemoryBTree<K, V>( configuration );
415 
416         return btree;
417     }
418 
419 
420     /**
421      * Creates a new in-memory BTree using the parameters to initialize the 
422      * BTree
423      * 
424      * @param name The BTree's name
425      * @param filePath The name of the data directory with absolute path
426      * @param keySerializer Key serializer
427      * @param valueSerializer Value serializer
428      * @param pageSize Size of the page
429      * @param allowDuplicates Tells if the BTree allows multiple value for a given key
430      * @throws IOException
431      */
432     public static <K, V> BTree<K, V> createInMemoryBTree( String name, String filePath,
433         ElementSerializer<K> keySerializer,
434         ElementSerializer<V> valueSerializer, int pageSize, boolean allowDuplicates )
435     {
436         InMemoryBTreeConfiguration<K, V> configuration = new InMemoryBTreeConfiguration<K, V>();
437 
438         configuration.setName( name );
439         configuration.setFilePath( filePath );
440         configuration.setKeySerializer( keySerializer );
441         configuration.setValueSerializer( valueSerializer );
442         configuration.setPageSize( pageSize );
443         configuration.setAllowDuplicates( allowDuplicates );
444         configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
445 
446         BTree<K, V> btree = new InMemoryBTree<K, V>( configuration );
447 
448         return btree;
449     }
450 
451 
452     //--------------------------------------------------------------------------------------------
453     // Create Pages
454     //--------------------------------------------------------------------------------------------
455     /**
456      * Create a new Leaf for the given BTree.
457      * 
458      * @param btree The BTree which will contain this leaf
459      * @param revision The Leaf's revision
460      * @param nbElems The number or elements in this leaf
461      * 
462      * @return A Leaf instance
463      */
464     /* no qualifier*/static <K, V> Page<K, V> createLeaf( BTree<K, V> btree, long revision, int nbElems )
465     {
466         if ( btree.getType() == BTreeTypeEnum.PERSISTED )
467         {
468             return new PersistedLeaf<K, V>( btree, revision, nbElems );
469         }
470         else
471         {
472             return new InMemoryLeaf<K, V>( btree, revision, nbElems );
473         }
474     }
475 
476 
477     /**
478      * Create a new Node for the given BTree.
479      * 
480      * @param btree The BTree which will contain this node
481      * @param revision The Node's revision
482      * @param nbElems The number or elements in this node
483      * @return A Node instance
484      */
485     /* no qualifier*/static <K, V> Page<K, V> createNode( BTree<K, V> btree, long revision, int nbElems )
486     {
487         if ( btree.getType() == BTreeTypeEnum.PERSISTED )
488         {
489             return new PersistedNode<K, V>( btree, revision, nbElems );
490         }
491         else
492         {
493             return new InMemoryNode<K, V>( btree, revision, nbElems );
494         }
495     }
496 
497 
498     //--------------------------------------------------------------------------------------------
499     // Update pages
500     //--------------------------------------------------------------------------------------------
501     /**
502      * Set the key at a give position
503      * 
504      * @param btree The BTree to update
505      * @param page The page to update
506      * @param pos The position in the keys array
507      * @param key The key to inject
508      */
509     /* no qualifier*/static <K, V> void setKey( BTree<K, V> btree, Page<K, V> page, int pos, K key )
510     {
511         KeyHolder<K> keyHolder;
512 
513         if ( btree.getType() == BTreeTypeEnum.PERSISTED )
514         {
515             keyHolder = new PersistedKeyHolder<K>( btree.getKeySerializer(), key );
516         }
517         else
518         {
519             keyHolder = new KeyHolder<K>( key );
520         }
521 
522         ( ( AbstractPage<K, V> ) page ).setKey( pos, keyHolder );
523     }
524 
525 
526     /**
527      * Set the value at a give position
528      * @param pos The position in the values array
529      * @param value the value to inject
530      */
531     /* no qualifier*/static <K, V> void setValue( BTree<K, V> btree, Page<K, V> page, int pos, ValueHolder<V> value )
532     {
533         if ( btree.getType() == BTreeTypeEnum.PERSISTED )
534         {
535             ( ( PersistedLeaf<K, V> ) page ).setValue( pos, value );
536         }
537         else
538         {
539             ( ( InMemoryLeaf<K, V> ) page ).setValue( pos, value );
540         }
541     }
542 
543 
544     /**
545      * Set the page at a give position
546      * 
547      * @param btree The BTree to update
548      * @param page The page to update
549      * @param pos The position in the values array
550      * @param value the value to inject
551      */
552     /* no qualifier*/static <K, V> void setPage( BTree<K, V> btree, Page<K, V> page, int pos, Page<K, V> child )
553     {
554         if ( btree.getType() == BTreeTypeEnum.PERSISTED )
555         {
556             ( ( PersistedNode<K, V> ) page ).setValue( pos, new PersistedPageHolder<K, V>( btree, child ) );
557         }
558         else
559         {
560             ( ( InMemoryNode<K, V> ) page ).setPageHolder( pos, new PageHolder<K, V>( btree, child ) );
561         }
562     }
563 
564 
565     //--------------------------------------------------------------------------------------------
566     // Update BTree
567     //--------------------------------------------------------------------------------------------
568     /**
569      * Sets the KeySerializer into the BTree
570      *  
571      * @param btree The BTree to update
572      * @param keySerializerFqcn the Key serializer FQCN to set
573      * @throws ClassNotFoundException
574      * @throws InstantiationException 
575      * @throws IllegalAccessException
576      */
577     /* no qualifier*/static <K, V> void setKeySerializer( BTree<K, V> btree, String keySerializerFqcn )
578         throws ClassNotFoundException, IllegalAccessException, InstantiationException
579     {
580         Class<?> keySerializer = Class.forName( keySerializerFqcn );
581         @SuppressWarnings("unchecked")
582         ElementSerializer<K> instance = ( ElementSerializer<K> ) keySerializer.newInstance();
583         btree.setKeySerializer( instance );
584     }
585 
586 
587     /**
588      * Sets the ValueSerializer into the BTree
589      *  
590      * @param btree The BTree to update
591      * @param valueSerializerFqcn the Value serializer FQCN to set
592      * @throws ClassNotFoundException
593      * @throws InstantiationException 
594      * @throws IllegalAccessException
595      */
596     /* no qualifier*/static <K, V> void setValueSerializer( BTree<K, V> btree, String valueSerializerFqcn )
597         throws ClassNotFoundException, IllegalAccessException, InstantiationException
598     {
599         Class<?> valueSerializer = Class.forName( valueSerializerFqcn );
600         @SuppressWarnings("unchecked")
601         ElementSerializer<V> instance = ( ElementSerializer<V> ) valueSerializer.newInstance();
602         btree.setValueSerializer( instance );
603     }
604 
605 
606     /**
607      * Set the new root page for this tree. Used for debug purpose only. The revision
608      * will always be 0;
609      * 
610      * @param btree The BTree to update
611      * @param root the new root page.
612      */
613     /* no qualifier*/static <K, V> void setRootPage( BTree<K, V> btree, Page<K, V> root )
614     {
615         ( ( AbstractBTree<K, V> ) btree ).setRootPage( root );
616     }
617 
618 
619     /**
620      * Return the BTree root page
621      * 
622      * @param btree The Btree we want to root page from
623      * @return The root page
624      */
625     /* no qualifier */static <K, V> Page<K, V> getRootPage( BTree<K, V> btree )
626     {
627         return btree.getRootPage();
628     }
629 
630 
631     /**
632      * update the BTree number of elements
633      * 
634      * @param btree The BTree to update
635      * @param nbElems the nbElems to set
636      */
637     /* no qualifier */static <K, V> void setNbElems( BTree<K, V> btree, long nbElems )
638     {
639         ( ( AbstractBTree<K, V> ) btree ).setNbElems( nbElems );
640     }
641 
642 
643     /**
644      * Update the btree revision
645      * 
646      * @param btree The BTree to update
647      * @param revision the revision to set
648      */
649     /* no qualifier*/static <K, V> void setRevision( BTree<K, V> btree, long revision )
650     {
651         ( ( AbstractBTree<K, V> ) btree ).setRevision( revision );
652     }
653 
654 
655     /**
656      * Set the BTree name
657      * 
658      * @param btree The BTree to update
659      * @param name the name to set
660      */
661     /* no qualifier */static <K, V> void setName( BTree<K, V> btree, String name )
662     {
663         btree.setName( name );
664     }
665 
666 
667     /**
668      * Set the maximum number of elements we can store in a page.
669      * 
670      * @param btree The BTree to update
671      * @param pageSize The requested page size
672      */
673     /* no qualifier */static <K, V> void setPageSize( BTree<K, V> btree, int pageSize )
674     {
675         btree.setPageSize( pageSize );
676     }
677 
678 
679     //--------------------------------------------------------------------------------------------
680     // Utility method
681     //--------------------------------------------------------------------------------------------
682     /**
683      * Includes the intermediate nodes in the path up to and including the right most leaf of the tree
684      * 
685      * @param btree the btree
686      * @return a LinkedList of all the nodes and the final leaf
687      */
688     /* no qualifier*/static <K, V> LinkedList<ParentPos<K, V>> getPathToRightMostLeaf( BTree<K, V> btree )
689     {
690         LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
691 
692         ParentPos<K, V> last = new ParentPos<K, V>( btree.getRootPage(), btree.getRootPage().getNbElems() );
693         stack.push( last );
694 
695         if ( btree.getRootPage().isLeaf() )
696         {
697             Page<K, V> leaf = btree.getRootPage();
698             ValueHolder<V> valueHolder = ( ( AbstractPage<K, V> ) leaf ).getValue( last.pos );
699             last.valueCursor = valueHolder.getCursor();
700         }
701         else
702         {
703             Page<K, V> node = btree.getRootPage();
704 
705             while ( true )
706             {
707                 Page<K, V> p = ( ( AbstractPage<K, V> ) node ).getPage( node.getNbElems() );
708 
709                 last = new ParentPos<K, V>( p, p.getNbElems() );
710                 stack.push( last );
711 
712                 if ( p.isLeaf() )
713                 {
714                     Page<K, V> leaf = last.page;
715                     ValueHolder<V> valueHolder = ( ( AbstractPage<K, V> ) leaf ).getValue( last.pos );
716                     last.valueCursor = valueHolder.getCursor();
717                     break;
718                 }
719             }
720         }
721 
722         return stack;
723     }
724 
725 
726     //--------------------------------------------------------------------------------------------
727     // Persisted BTree methods
728     //--------------------------------------------------------------------------------------------
729     /**
730      * Set the rootPage offset of the BTree
731      * 
732      * @param btree The btree to update
733      * @param rootPageOffset The rootPageOffset to set
734      */
735     /* no qualifier*/static <K, V> void setRootPageOffset( BTree<K, V> btree, long rootPageOffset )
736     {
737         if ( btree instanceof PersistedBTree )
738         {
739             ( ( PersistedBTree<K, V> ) btree ).setRootPageOffset( rootPageOffset );
740         }
741         else
742         {
743             throw new IllegalArgumentException( "The BTree must be a PersistedBTree" );
744         }
745     }
746 
747 
748     /**
749      * Set the nextBTree offset
750      * 
751      * @param btree The btree to update
752      * @param nextBTreeOffset The nextBTreeOffset to set
753      */
754     /* no qualifier*/static <K, V> void setNextBTreeOffset( BTree<K, V> btree, long nextBTreeOffset )
755     {
756         if ( btree instanceof PersistedBTree )
757         {
758             ( ( PersistedBTree<K, V> ) btree ).setNextBTreeOffset( nextBTreeOffset );
759         }
760         else
761         {
762             throw new IllegalArgumentException( "The BTree must be a PersistedBTree" );
763         }
764     }
765 
766 
767     /**
768      * Set the RecordManager
769      * 
770      * @param btree The btree to update
771      * @param recordManager The injected RecordManager
772      */
773     /* no qualifier*/static <K, V> void setRecordManager( BTree<K, V> btree, RecordManager recordManager )
774     {
775         if ( btree instanceof PersistedBTree )
776         {
777             ( ( PersistedBTree<K, V> ) btree ).setRecordManager( recordManager );
778         }
779         else
780         {
781             throw new IllegalArgumentException( "The BTree must be a PersistedBTree" );
782         }
783     }
784 
785 
786     /**
787      * Set the key at a give position
788      * 
789      * @param btree The btree to update
790      * @param page The page to update
791      * @param pos The position of this key in the page
792      * @param buffer The byte[] containing the serialized key
793      */
794     /* no qualifier*/static <K, V> void setKey( BTree<K, V> btree, Page<K, V> page, int pos, byte[] buffer )
795     {
796         if ( btree instanceof PersistedBTree )
797         {
798             KeyHolder<K> keyHolder = new PersistedKeyHolder<K>( btree.getKeySerializer(), buffer );
799             ( ( AbstractPage<K, V> ) page ).setKey( pos, keyHolder );
800         }
801         else
802         {
803             throw new IllegalArgumentException( "The BTree must be a PersistedBTree" );
804         }
805     }
806 
807 
808     /**
809      * Includes the intermediate nodes in the path up to and including the left most leaf of the tree
810      * 
811      * @param btree The btree to process
812      * @return a LinkedList of all the nodes and the final leaf
813      */
814     /* no qualifier*/static <K, V> LinkedList<ParentPos<K, V>> getPathToLeftMostLeaf( BTree<K, V> btree )
815     {
816         if ( btree instanceof PersistedBTree )
817         {
818             LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
819 
820             ParentPos<K, V> first = new ParentPos<K, V>( btree.getRootPage(), 0 );
821             stack.push( first );
822 
823             if ( btree.getRootPage().isLeaf() )
824             {
825                 Page<K, V> leaf = btree.getRootPage();
826                 ValueHolder<V> valueHolder = ( ( AbstractPage<K, V> ) leaf ).getValue( first.pos );
827                 first.valueCursor = valueHolder.getCursor();
828             }
829             else
830             {
831                 Page<K, V> node = btree.getRootPage();
832 
833                 while ( true )
834                 {
835                     Page<K, V> page = ( ( AbstractPage<K, V> ) node ).getPage( 0 );
836 
837                     first = new ParentPos<K, V>( page, 0 );
838                     stack.push( first );
839 
840                     if ( page.isLeaf() )
841                     {
842                         ValueHolder<V> valueHolder = ( ( AbstractPage<K, V> ) page ).getValue( first.pos );
843                         first.valueCursor = valueHolder.getCursor();
844                         break;
845                     }
846                 }
847             }
848 
849             return stack;
850         }
851         else
852         {
853             throw new IllegalArgumentException( "The BTree must be a PersistedBTree" );
854         }
855     }
856 }