001/*
002 *   Licensed to the Apache Software Foundation (ASF) under one
003 *   or more contributor license agreements.  See the NOTICE file
004 *   distributed with this work for additional information
005 *   regarding copyright ownership.  The ASF licenses this file
006 *   to you under the Apache License, Version 2.0 (the
007 *   "License"); you may not use this file except in compliance
008 *   with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 *   Unless required by applicable law or agreed to in writing,
013 *   software distributed under the License is distributed on an
014 *   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015 *   KIND, either express or implied.  See the License for the
016 *   specific language governing permissions and limitations
017 *   under the License.
018 *
019 */
020package org.apache.directory.mavibot.btree;
021
022
023import java.util.LinkedList;
024
025import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
026
027
028/**
029 * This class construct a B-tree from a serialized version of a B-tree. We need it
030 * to avoid exposing all the methods of the B-tree class.<br>
031 *
032 * All its methods are static.
033 *
034 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
035 *
036 * @param <K> The B-tree key type
037 * @param <V> The B-tree value type
038 */
039public class BTreeFactory<K, V>
040{
041    //--------------------------------------------------------------------------------------------
042    // Create persisted btrees
043    //--------------------------------------------------------------------------------------------
044    /**
045     * Creates a new persisted B-tree, with no initialization.
046     *
047     * @return a new B-tree instance
048     */
049    public static <K, V> BTree<K, V> createPersistedBTree()
050    {
051        BTree<K, V> btree = new PersistedBTree<K, V>();
052
053        return btree;
054    }
055
056
057    /**
058     * Creates a new persisted B-tree, with no initialization.
059     *
060     * @return a new B-tree instance
061     */
062    public static <K, V> BTree<K, V> createPersistedBTree( BTreeTypeEnum type )
063    {
064        BTree<K, V> btree = new PersistedBTree<K, V>();
065        ( ( AbstractBTree<K, V> ) btree ).setType( type );
066
067        return btree;
068    }
069
070
071    /**
072     * Sets the btreeHeader offset for a Persisted BTree
073     *
074     * @param btree The btree to update
075     * @param btreeHeaderOffset The offset
076     */
077    public static <K, V> void setBtreeHeaderOffset( PersistedBTree<K, V> btree, long btreeHeaderOffset )
078    {
079        btree.setBtreeHeaderOffset( btreeHeaderOffset );
080    }
081
082
083    /**
084     * Creates a new persisted B-tree using the BTreeConfiguration to initialize the
085     * B-tree
086     *
087     * @param configuration The configuration to use
088     * @return a new B-tree instance
089     */
090    public static <K, V> BTree<K, V> createPersistedBTree( PersistedBTreeConfiguration<K, V> configuration )
091    {
092        BTree<K, V> btree = new PersistedBTree<K, V>( configuration );
093
094        return btree;
095    }
096
097
098    /**
099     * Creates a new persisted B-tree using the parameters to initialize the
100     * B-tree
101     *
102     * @param name The B-tree's name
103     * @param keySerializer Key serializer
104     * @param valueSerializer Value serializer
105     * @return a new B-tree instance
106     */
107    public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer,
108        ElementSerializer<V> valueSerializer )
109    {
110        PersistedBTreeConfiguration<K, V> configuration = new PersistedBTreeConfiguration<K, V>();
111
112        configuration.setName( name );
113        configuration.setKeySerializer( keySerializer );
114        configuration.setValueSerializer( valueSerializer );
115        configuration.setPageSize( BTree.DEFAULT_PAGE_SIZE );
116        configuration.setAllowDuplicates( BTree.FORBID_DUPLICATES );
117        configuration.setCacheSize( PersistedBTree.DEFAULT_CACHE_SIZE );
118        configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
119
120        BTree<K, V> btree = new PersistedBTree<K, V>( configuration );
121
122        return btree;
123    }
124
125
126    /**
127     * Creates a new persisted B-tree using the parameters to initialize the
128     * B-tree
129     *
130     * @param name The B-tree's name
131     * @param keySerializer Key serializer
132     * @param valueSerializer Value serializer
133     * @param allowDuplicates Tells if the B-tree allows multiple value for a given key
134     * @return a new B-tree instance
135     */
136    public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer,
137        ElementSerializer<V> valueSerializer, boolean allowDuplicates )
138    {
139        PersistedBTreeConfiguration<K, V> configuration = new PersistedBTreeConfiguration<K, V>();
140
141        configuration.setName( name );
142        configuration.setKeySerializer( keySerializer );
143        configuration.setValueSerializer( valueSerializer );
144        configuration.setPageSize( BTree.DEFAULT_PAGE_SIZE );
145        configuration.setAllowDuplicates( allowDuplicates );
146        configuration.setCacheSize( PersistedBTree.DEFAULT_CACHE_SIZE );
147        configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
148
149        BTree<K, V> btree = new PersistedBTree<K, V>( configuration );
150
151        return btree;
152    }
153
154
155    /**
156     * Creates a new persisted B-tree using the parameters to initialize the
157     * B-tree
158     *
159     * @param name The B-tree's name
160     * @param keySerializer Key serializer
161     * @param valueSerializer Value serializer
162     * @param allowDuplicates Tells if the B-tree allows multiple value for a given key
163     * @param cacheSize The size to be used for this B-tree cache
164     * @return a new B-tree instance
165     */
166    public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer,
167        ElementSerializer<V> valueSerializer, boolean allowDuplicates, int cacheSize )
168    {
169        PersistedBTreeConfiguration<K, V> configuration = new PersistedBTreeConfiguration<K, V>();
170
171        configuration.setName( name );
172        configuration.setKeySerializer( keySerializer );
173        configuration.setValueSerializer( valueSerializer );
174        configuration.setPageSize( BTree.DEFAULT_PAGE_SIZE );
175        configuration.setAllowDuplicates( allowDuplicates );
176        configuration.setCacheSize( cacheSize );
177        configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
178
179        BTree<K, V> btree = new PersistedBTree<K, V>( configuration );
180
181        return btree;
182    }
183
184
185    /**
186     * Creates a new persisted B-tree using the parameters to initialize the
187     * B-tree
188     *
189     * @param name The B-tree's name
190     * @param keySerializer Key serializer
191     * @param valueSerializer Value serializer
192     * @param pageSize Size of the page
193     * @return a new B-tree instance
194     */
195    public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer,
196        ElementSerializer<V> valueSerializer, int pageSize )
197    {
198        PersistedBTreeConfiguration<K, V> configuration = new PersistedBTreeConfiguration<K, V>();
199
200        configuration.setName( name );
201        configuration.setKeySerializer( keySerializer );
202        configuration.setValueSerializer( valueSerializer );
203        configuration.setPageSize( pageSize );
204        configuration.setAllowDuplicates( BTree.FORBID_DUPLICATES );
205        configuration.setCacheSize( PersistedBTree.DEFAULT_CACHE_SIZE );
206        configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
207
208        BTree<K, V> btree = new PersistedBTree<K, V>( configuration );
209
210        return btree;
211    }
212
213
214    /**
215     * Creates a new persisted B-tree using the parameters to initialize the
216     * B-tree
217     *
218     * @param name The B-tree's name
219     * @param keySerializer Key serializer
220     * @param valueSerializer Value serializer
221     * @param pageSize Size of the page
222     * @param allowDuplicates Tells if the B-tree allows multiple value for a given key
223     * @return a new B-tree instance
224     */
225    public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer,
226        ElementSerializer<V> valueSerializer, int pageSize, boolean allowDuplicates )
227    {
228        PersistedBTreeConfiguration<K, V> configuration = new PersistedBTreeConfiguration<K, V>();
229
230        configuration.setName( name );
231        configuration.setKeySerializer( keySerializer );
232        configuration.setValueSerializer( valueSerializer );
233        configuration.setPageSize( pageSize );
234        configuration.setAllowDuplicates( allowDuplicates );
235        configuration.setCacheSize( PersistedBTree.DEFAULT_CACHE_SIZE );
236        configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
237
238        BTree<K, V> btree = new PersistedBTree<K, V>( configuration );
239
240        return btree;
241    }
242
243
244    /**
245     * Creates a new persisted B-tree using the parameters to initialize the
246     * B-tree
247     *
248     * @param name The B-tree's name
249     * @param keySerializer Key serializer
250     * @param valueSerializer Value serializer
251     * @param pageSize Size of the page
252     * @param allowDuplicates Tells if the B-tree allows multiple value for a given key
253     * @param cacheSize The size to be used for this B-tree cache
254     * @return a new B-tree instance
255     */
256    public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer,
257        ElementSerializer<V> valueSerializer, int pageSize, boolean allowDuplicates, int cacheSize )
258    {
259        PersistedBTreeConfiguration<K, V> configuration = new PersistedBTreeConfiguration<K, V>();
260
261        configuration.setName( name );
262        configuration.setKeySerializer( keySerializer );
263        configuration.setValueSerializer( valueSerializer );
264        configuration.setPageSize( pageSize );
265        configuration.setAllowDuplicates( allowDuplicates );
266        configuration.setCacheSize( cacheSize );
267        configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
268
269        BTree<K, V> btree = new PersistedBTree<K, V>( configuration );
270
271        return btree;
272    }
273
274
275    //--------------------------------------------------------------------------------------------
276    // Create in-memory B-trees
277    //--------------------------------------------------------------------------------------------
278    /**
279     * Creates a new in-memory B-tree, with no initialization.
280     *
281     * @return a new B-tree instance
282     */
283    public static <K, V> BTree<K, V> createInMemoryBTree()
284    {
285        BTree<K, V> btree = new InMemoryBTree<K, V>();
286
287        return btree;
288    }
289
290
291    /**
292     * Creates a new in-memory B-tree using the BTreeConfiguration to initialize the
293     * B-tree
294     *
295     * @param configuration The configuration to use
296     * @return a new B-tree instance
297     */
298    public static <K, V> BTree<K, V> createInMemoryBTree( InMemoryBTreeConfiguration<K, V> configuration )
299    {
300        BTree<K, V> btree = new InMemoryBTree<K, V>( configuration );
301
302        return btree;
303    }
304
305
306    /**
307     * Creates a new in-memory B-tree using the parameters to initialize the
308     * B-tree
309     *
310     * @param name The B-tree's name
311     * @param keySerializer Key serializer
312     * @param valueSerializer Value serializer
313     * @return a new B-tree instance
314     */
315    public static <K, V> BTree<K, V> createInMemoryBTree( String name, ElementSerializer<K> keySerializer,
316        ElementSerializer<V> valueSerializer )
317    {
318        InMemoryBTreeConfiguration<K, V> configuration = new InMemoryBTreeConfiguration<K, V>();
319
320        configuration.setName( name );
321        configuration.setKeySerializer( keySerializer );
322        configuration.setValueSerializer( valueSerializer );
323        configuration.setPageSize( BTree.DEFAULT_PAGE_SIZE );
324        configuration.setAllowDuplicates( BTree.FORBID_DUPLICATES );
325        configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
326
327        BTree<K, V> btree = new InMemoryBTree<K, V>( configuration );
328
329        return btree;
330    }
331
332
333    /**
334     * Creates a new in-memory B-tree using the parameters to initialize the
335     * B-tree
336     *
337     * @param name The B-tree's name
338     * @param keySerializer Key serializer
339     * @param valueSerializer Value serializer
340     * @param allowDuplicates Tells if the B-tree allows multiple value for a given key
341     * @return a new B-tree instance
342     */
343    public static <K, V> BTree<K, V> createInMemoryBTree( String name, ElementSerializer<K> keySerializer,
344        ElementSerializer<V> valueSerializer, boolean allowDuplicates )
345    {
346        InMemoryBTreeConfiguration<K, V> configuration = new InMemoryBTreeConfiguration<K, V>();
347
348        configuration.setName( name );
349        configuration.setKeySerializer( keySerializer );
350        configuration.setValueSerializer( valueSerializer );
351        configuration.setPageSize( BTree.DEFAULT_PAGE_SIZE );
352        configuration.setAllowDuplicates( allowDuplicates );
353        configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
354
355        BTree<K, V> btree = new InMemoryBTree<K, V>( configuration );
356
357        return btree;
358    }
359
360
361    /**
362     * Creates a new in-memory B-tree using the parameters to initialize the
363     * B-tree
364     *
365     * @param name The B-tree's name
366     * @param keySerializer Key serializer
367     * @param valueSerializer Value serializer
368     * @param pageSize Size of the page
369     * @return a new B-tree instance
370     */
371    public static <K, V> BTree<K, V> createInMemoryBTree( String name, ElementSerializer<K> keySerializer,
372        ElementSerializer<V> valueSerializer, int pageSize )
373    {
374        InMemoryBTreeConfiguration<K, V> configuration = new InMemoryBTreeConfiguration<K, V>();
375
376        configuration.setName( name );
377        configuration.setKeySerializer( keySerializer );
378        configuration.setValueSerializer( valueSerializer );
379        configuration.setPageSize( pageSize );
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 B-tree using the parameters to initialize the
391     * B-tree
392     *
393     * @param name The B-tree'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     * @return a new B-tree instance
398     */
399    public static <K, V> BTree<K, V> createInMemoryBTree( String name, String filePath,
400        ElementSerializer<K> keySerializer,
401        ElementSerializer<V> valueSerializer )
402    {
403        InMemoryBTreeConfiguration<K, V> configuration = new InMemoryBTreeConfiguration<K, V>();
404
405        configuration.setName( name );
406        configuration.setFilePath( filePath );
407        configuration.setKeySerializer( keySerializer );
408        configuration.setValueSerializer( valueSerializer );
409        configuration.setPageSize( BTree.DEFAULT_PAGE_SIZE );
410        configuration.setAllowDuplicates( BTree.FORBID_DUPLICATES );
411        configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
412
413        BTree<K, V> btree = new InMemoryBTree<K, V>( configuration );
414
415        return btree;
416    }
417
418
419    /**
420     * Creates a new in-memory B-tree using the parameters to initialize the
421     * B-tree
422     *
423     * @param name The B-tree's name
424     * @param filePath The name of the data directory with absolute path
425     * @param keySerializer Key serializer
426     * @param valueSerializer Value serializer
427     * @param pageSize Size of the page
428     * @return a new B-tree instance
429     */
430    public static <K, V> BTree<K, V> createInMemoryBTree( String name, String filePath,
431        ElementSerializer<K> keySerializer, ElementSerializer<V> valueSerializer, int pageSize )
432    {
433        InMemoryBTreeConfiguration<K, V> configuration = new InMemoryBTreeConfiguration<K, V>();
434
435        configuration.setName( name );
436        configuration.setFilePath( filePath );
437        configuration.setKeySerializer( keySerializer );
438        configuration.setValueSerializer( valueSerializer );
439        configuration.setPageSize( pageSize );
440        configuration.setAllowDuplicates( BTree.FORBID_DUPLICATES );
441        configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
442
443        BTree<K, V> btree = new InMemoryBTree<K, V>( configuration );
444
445        return btree;
446    }
447
448
449    /**
450     * Creates a new in-memory B-tree using the parameters to initialize the
451     * B-tree
452     *
453     * @param name The B-tree's name
454     * @param filePath The name of the data directory with absolute path
455     * @param keySerializer Key serializer
456     * @param valueSerializer Value serializer
457     * @param pageSize Size of the page
458     * @param allowDuplicates Tells if the B-tree allows multiple value for a given key
459     * @return a new B-tree instance
460     */
461    public static <K, V> BTree<K, V> createInMemoryBTree( String name, String filePath,
462        ElementSerializer<K> keySerializer,
463        ElementSerializer<V> valueSerializer, int pageSize, boolean allowDuplicates )
464    {
465        InMemoryBTreeConfiguration<K, V> configuration = new InMemoryBTreeConfiguration<K, V>();
466
467        configuration.setName( name );
468        configuration.setFilePath( filePath );
469        configuration.setKeySerializer( keySerializer );
470        configuration.setValueSerializer( valueSerializer );
471        configuration.setPageSize( pageSize );
472        configuration.setAllowDuplicates( allowDuplicates );
473        configuration.setWriteBufferSize( BTree.DEFAULT_WRITE_BUFFER_SIZE );
474
475        BTree<K, V> btree = new InMemoryBTree<K, V>( configuration );
476
477        return btree;
478    }
479
480
481    //--------------------------------------------------------------------------------------------
482    // Create Pages
483    //--------------------------------------------------------------------------------------------
484    /**
485     * Create a new Leaf for the given B-tree.
486     *
487     * @param btree The B-tree which will contain this leaf
488     * @param revision The Leaf's revision
489     * @param nbElems The number or elements in this leaf
490     *
491     * @return A Leaf instance
492     */
493    /* no qualifier*/static <K, V> Page<K, V> createLeaf( BTree<K, V> btree, long revision, int nbElems )
494    {
495        if ( btree.getType() != BTreeTypeEnum.IN_MEMORY )
496        {
497            return new PersistedLeaf<K, V>( btree, revision, nbElems );
498        }
499        else
500        {
501            return new InMemoryLeaf<K, V>( btree, revision, nbElems );
502        }
503    }
504
505
506    /**
507     * Create a new Node for the given B-tree.
508     *
509     * @param btree The B-tree which will contain this node
510     * @param revision The Node's revision
511     * @param nbElems The number or elements in this node
512     * @return A Node instance
513     */
514    /* no qualifier*/static <K, V> Page<K, V> createNode( BTree<K, V> btree, long revision, int nbElems )
515    {
516        if ( btree.getType() != BTreeTypeEnum.IN_MEMORY )
517        {
518            //System.out.println( "Creating a node with nbElems : " + nbElems );
519            return new PersistedNode<K, V>( btree, revision, nbElems );
520        }
521        else
522        {
523            return new InMemoryNode<K, V>( btree, revision, nbElems );
524        }
525    }
526
527
528    //--------------------------------------------------------------------------------------------
529    // Update pages
530    //--------------------------------------------------------------------------------------------
531    /**
532     * Set the key at a give position
533     *
534     * @param btree The B-tree to update
535     * @param page The page to update
536     * @param pos The position in the keys array
537     * @param key The key to inject
538     */
539    /* no qualifier*/static <K, V> void setKey( BTree<K, V> btree, Page<K, V> page, int pos, K key )
540    {
541        KeyHolder<K> keyHolder;
542
543        if ( btree.getType() != BTreeTypeEnum.IN_MEMORY )
544        {
545            keyHolder = new PersistedKeyHolder<K>( btree.getKeySerializer(), key );
546        }
547        else
548        {
549            keyHolder = new KeyHolder<K>( key );
550        }
551
552        ( ( AbstractPage<K, V> ) page ).setKey( pos, keyHolder );
553    }
554
555
556    /**
557     * Set the value at a give position
558     *
559     * @param btree The B-tree to update
560     * @param page The page to update
561     * @param pos The position in the values array
562     * @param value the value to inject
563     */
564    /* no qualifier*/static <K, V> void setValue( BTree<K, V> btree, Page<K, V> page, int pos, ValueHolder<V> value )
565    {
566        if ( btree.getType() != BTreeTypeEnum.IN_MEMORY )
567        {
568            ( ( PersistedLeaf<K, V> ) page ).setValue( pos, value );
569        }
570        else
571        {
572            ( ( InMemoryLeaf<K, V> ) page ).setValue( pos, value );
573        }
574    }
575
576
577    /**
578     * Set the page at a give position
579     *
580     * @param btree The B-tree to update
581     * @param page The page to update
582     * @param pos The position in the values array
583     * @param child the child page to inject
584     */
585    /* no qualifier*/static <K, V> void setPage( BTree<K, V> btree, Page<K, V> page, int pos, Page<K, V> child )
586    {
587        if ( btree.getType() != BTreeTypeEnum.IN_MEMORY )
588        {
589            ( ( PersistedNode<K, V> ) page ).setValue( pos, new PersistedPageHolder<K, V>( btree, child ) );
590        }
591        else
592        {
593            ( ( InMemoryNode<K, V> ) page ).setPageHolder( pos, new PageHolder<K, V>( btree, child ) );
594        }
595    }
596
597
598    //--------------------------------------------------------------------------------------------
599    // Update B-tree
600    //--------------------------------------------------------------------------------------------
601    /**
602     * Sets the KeySerializer into the B-tree
603     *
604     * @param btree The B-tree to update
605     * @param keySerializerFqcn the Key serializer FQCN to set
606     * @throws ClassNotFoundException If the key serializer class cannot be found
607     * @throws InstantiationException If the key serializer class cannot be instanciated
608     * @throws IllegalAccessException If the key serializer class cannot be accessed
609     * @throws NoSuchFieldException
610     * @throws SecurityException
611     * @throws IllegalArgumentException
612     */
613    /* no qualifier*/static <K, V> void setKeySerializer( BTree<K, V> btree, String keySerializerFqcn )
614        throws ClassNotFoundException, IllegalAccessException, InstantiationException, IllegalArgumentException,
615        SecurityException, NoSuchFieldException
616    {
617        Class<?> keySerializer = Class.forName( keySerializerFqcn );
618        @SuppressWarnings("unchecked")
619        ElementSerializer<K> instance = null;
620        try
621        {
622            instance = ( ElementSerializer<K> ) keySerializer.getDeclaredField( "INSTANCE" ).get( null );
623        }
624        catch ( NoSuchFieldException e )
625        {
626            // ignore
627        }
628
629        if ( instance == null )
630        {
631            instance = ( ElementSerializer<K> ) keySerializer.newInstance();
632        }
633
634        btree.setKeySerializer( instance );
635    }
636
637
638    /**
639     * Sets the ValueSerializer into the B-tree
640     *
641     * @param btree The B-tree to update
642     * @param valueSerializerFqcn the Value serializer FQCN to set
643     * @throws ClassNotFoundException If the value serializer class cannot be found
644     * @throws InstantiationException If the value serializer class cannot be instanciated
645     * @throws IllegalAccessException If the value serializer class cannot be accessed
646     * @throws NoSuchFieldException
647     * @throws SecurityException
648     * @throws IllegalArgumentException
649     */
650    /* no qualifier*/static <K, V> void setValueSerializer( BTree<K, V> btree, String valueSerializerFqcn )
651        throws ClassNotFoundException, IllegalAccessException, InstantiationException, IllegalArgumentException,
652        SecurityException, NoSuchFieldException
653    {
654        Class<?> valueSerializer = Class.forName( valueSerializerFqcn );
655        @SuppressWarnings("unchecked")
656        ElementSerializer<V> instance = null;
657        try
658        {
659            instance = ( ElementSerializer<V> ) valueSerializer.getDeclaredField( "INSTANCE" ).get( null );
660        }
661        catch ( NoSuchFieldException e )
662        {
663            // ignore
664        }
665
666        if ( instance == null )
667        {
668            instance = ( ElementSerializer<V> ) valueSerializer.newInstance();
669        }
670
671        btree.setValueSerializer( instance );
672    }
673
674
675    /**
676     * Set the new root page for this tree. Used for debug purpose only. The revision
677     * will always be 0;
678     *
679     * @param btree The B-tree to update
680     * @param root the new root page.
681     */
682    /* no qualifier*/static <K, V> void setRootPage( BTree<K, V> btree, Page<K, V> root )
683    {
684        ( ( AbstractBTree<K, V> ) btree ).setRootPage( root );
685    }
686
687
688    /**
689     * Return the B-tree root page
690     *
691     * @param btree The B-tree we want to root page from
692     * @return The root page
693     */
694    /* no qualifier */static <K, V> Page<K, V> getRootPage( BTree<K, V> btree )
695    {
696        return btree.getRootPage();
697    }
698
699
700    /**
701     * Update the B-tree number of elements
702     *
703     * @param btree The B-tree to update
704     * @param nbElems the nbElems to set
705     */
706    /* no qualifier */static <K, V> void setNbElems( BTree<K, V> btree, long nbElems )
707    {
708        ( ( AbstractBTree<K, V> ) btree ).setNbElems( nbElems );
709    }
710
711
712    /**
713     * Update the B-tree revision
714     *
715     * @param btree The B-tree to update
716     * @param revision the revision to set
717     */
718    /* no qualifier*/static <K, V> void setRevision( BTree<K, V> btree, long revision )
719    {
720        ( ( AbstractBTree<K, V> ) btree ).setRevision( revision );
721    }
722
723
724    /**
725     * Set the B-tree name
726     *
727     * @param btree The B-tree to update
728     * @param name the name to set
729     */
730    /* no qualifier */static <K, V> void setName( BTree<K, V> btree, String name )
731    {
732        btree.setName( name );
733    }
734
735
736    /**
737     * Set the maximum number of elements we can store in a page.
738     *
739     * @param btree The B-tree to update
740     * @param pageSize The requested page size
741     */
742    /* no qualifier */static <K, V> void setPageSize( BTree<K, V> btree, int pageSize )
743    {
744        btree.setPageSize( pageSize );
745    }
746
747
748    //--------------------------------------------------------------------------------------------
749    // Utility method
750    //--------------------------------------------------------------------------------------------
751    /**
752     * Includes the intermediate nodes in the path up to and including the right most leaf of the tree
753     *
754     * @param btree the B-tree
755     * @return a LinkedList of all the nodes and the final leaf
756     */
757    /* no qualifier*/static <K, V> LinkedList<ParentPos<K, V>> getPathToRightMostLeaf( BTree<K, V> btree )
758    {
759        LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
760
761        ParentPos<K, V> last = new ParentPos<K, V>( btree.getRootPage(), btree.getRootPage().getNbElems() );
762        stack.push( last );
763
764        if ( btree.getRootPage().isLeaf() )
765        {
766            Page<K, V> leaf = btree.getRootPage();
767            ValueHolder<V> valueHolder = ( ( AbstractPage<K, V> ) leaf ).getValue( last.pos );
768            last.valueCursor = valueHolder.getCursor();
769        }
770        else
771        {
772            Page<K, V> node = btree.getRootPage();
773
774            while ( true )
775            {
776                Page<K, V> p = ( ( AbstractPage<K, V> ) node ).getPage( node.getNbElems() );
777
778                last = new ParentPos<K, V>( p, p.getNbElems() );
779                stack.push( last );
780
781                if ( p.isLeaf() )
782                {
783                    Page<K, V> leaf = last.page;
784                    ValueHolder<V> valueHolder = ( ( AbstractPage<K, V> ) leaf ).getValue( last.pos );
785                    last.valueCursor = valueHolder.getCursor();
786                    break;
787                }
788            }
789        }
790
791        return stack;
792    }
793
794
795    //--------------------------------------------------------------------------------------------
796    // Persisted B-tree methods
797    //--------------------------------------------------------------------------------------------
798    /**
799     * Set the rootPage offset of the B-tree
800     *
801     * @param btree The B-tree to update
802     * @param rootPageOffset The rootPageOffset to set
803     */
804    /* no qualifier*/static <K, V> void setRootPageOffset( BTree<K, V> btree, long rootPageOffset )
805    {
806        if ( btree instanceof PersistedBTree )
807        {
808            ( ( PersistedBTree<K, V> ) btree ).getBtreeHeader().setRootPageOffset( rootPageOffset );
809        }
810        else
811        {
812            throw new IllegalArgumentException( "The B-tree must be a PersistedBTree" );
813        }
814    }
815
816
817    /**
818     * Set the RecordManager
819     *
820     * @param btree The B-tree to update
821     * @param recordManager The injected RecordManager
822     */
823    /* no qualifier*/static <K, V> void setRecordManager( BTree<K, V> btree, RecordManager recordManager )
824    {
825        if ( btree instanceof PersistedBTree )
826        {
827            ( ( PersistedBTree<K, V> ) btree ).setRecordManager( recordManager );
828        }
829        else
830        {
831            throw new IllegalArgumentException( "The B-tree must be a PersistedBTree" );
832        }
833    }
834
835
836    /**
837     * Set the key at a give position
838     *
839     * @param btree The B-tree to update
840     * @param page The page to update
841     * @param pos The position of this key in the page
842     * @param buffer The byte[] containing the serialized key
843     */
844    /* no qualifier*/static <K, V> void setKey( BTree<K, V> btree, Page<K, V> page, int pos, byte[] buffer )
845    {
846        if ( btree instanceof PersistedBTree )
847        {
848            KeyHolder<K> keyHolder = new PersistedKeyHolder<K>( btree.getKeySerializer(), buffer );
849            ( ( AbstractPage<K, V> ) page ).setKey( pos, keyHolder );
850        }
851        else
852        {
853            throw new IllegalArgumentException( "The B-tree must be a PersistedBTree" );
854        }
855    }
856
857
858    /**
859     * Includes the intermediate nodes in the path up to and including the left most leaf of the tree
860     *
861     * @param btree The B-tree to process
862     * @return a LinkedList of all the nodes and the final leaf
863     */
864    /* no qualifier*/static <K, V> LinkedList<ParentPos<K, V>> getPathToLeftMostLeaf( BTree<K, V> btree )
865    {
866        if ( btree instanceof PersistedBTree )
867        {
868            LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
869
870            ParentPos<K, V> first = new ParentPos<K, V>( btree.getRootPage(), 0 );
871            stack.push( first );
872
873            if ( btree.getRootPage().isLeaf() )
874            {
875                Page<K, V> leaf = btree.getRootPage();
876                ValueHolder<V> valueHolder = ( ( AbstractPage<K, V> ) leaf ).getValue( first.pos );
877                first.valueCursor = valueHolder.getCursor();
878            }
879            else
880            {
881                Page<K, V> node = btree.getRootPage();
882
883                while ( true )
884                {
885                    Page<K, V> page = ( ( AbstractPage<K, V> ) node ).getPage( 0 );
886
887                    first = new ParentPos<K, V>( page, 0 );
888                    stack.push( first );
889
890                    if ( page.isLeaf() )
891                    {
892                        ValueHolder<V> valueHolder = ( ( AbstractPage<K, V> ) page ).getValue( first.pos );
893                        first.valueCursor = valueHolder.getCursor();
894                        break;
895                    }
896                }
897            }
898
899            return stack;
900        }
901        else
902        {
903            throw new IllegalArgumentException( "The B-tree must be a PersistedBTree" );
904        }
905    }
906}