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.Closeable;
24  import java.io.EOFException;
25  import java.io.File;
26  import java.io.FileOutputStream;
27  import java.io.IOException;
28  import java.io.RandomAccessFile;
29  import java.lang.reflect.ParameterizedType;
30  import java.lang.reflect.Type;
31  import java.nio.ByteBuffer;
32  import java.nio.channels.FileChannel;
33  import java.util.Comparator;
34  import java.util.concurrent.ConcurrentLinkedQueue;
35  import java.util.concurrent.locks.ReentrantLock;
36  
37  import net.sf.ehcache.Cache;
38  import net.sf.ehcache.config.CacheConfiguration;
39  
40  import org.apache.directory.mavibot.btree.Addition;
41  import org.apache.directory.mavibot.btree.BTreeHeader;
42  import org.apache.directory.mavibot.btree.DeleteResult;
43  import org.apache.directory.mavibot.btree.Deletion;
44  import org.apache.directory.mavibot.btree.InsertResult;
45  import org.apache.directory.mavibot.btree.Modification;
46  import org.apache.directory.mavibot.btree.ModifyResult;
47  import org.apache.directory.mavibot.btree.NotPresentResult;
48  import org.apache.directory.mavibot.btree.Page;
49  import org.apache.directory.mavibot.btree.ParentPos;
50  import org.apache.directory.mavibot.btree.RemoveResult;
51  import org.apache.directory.mavibot.btree.SplitResult;
52  import org.apache.directory.mavibot.btree.Transaction;
53  import org.apache.directory.mavibot.btree.Tuple;
54  import org.apache.directory.mavibot.btree.TupleCursor;
55  import org.apache.directory.mavibot.btree.ValueCursor;
56  import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
57  import org.apache.directory.mavibot.btree.serializer.BufferHandler;
58  import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
59  import org.apache.directory.mavibot.btree.serializer.LongSerializer;
60  import org.slf4j.Logger;
61  import org.slf4j.LoggerFactory;
62  
63  
64  /**
65   * The B+Tree MVCC data structure.
66   * 
67   * @param <K> The type for the keys
68   * @param <V> The type for the stored values
69   *
70   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
71   */
72  public class BTree<K, V> implements Closeable
73  {
74      /** The LoggerFactory used by this class */
75      protected static final Logger LOG = LoggerFactory.getLogger( BTree.class );
76  
77      /** The Header for a managed BTree */
78      private BTreeHeader btreeHeader;
79  
80      /** Default page size (number of entries per node) */
81      public static final int DEFAULT_PAGE_SIZE = 16;
82  
83      /** Default size of the buffer used to write data on disk. Around 1Mb */
84      public static final int DEFAULT_WRITE_BUFFER_SIZE = 4096 * 250;
85  
86      /** The default journal name */
87      public static final String DEFAULT_JOURNAL = "mavibot.log";
88  
89      /** The default data file suffix */
90      public static final String DATA_SUFFIX = ".db";
91  
92      /** The default journal file suffix */
93      public static final String JOURNAL_SUFFIX = ".log";
94  
95      /** The current rootPage */
96      protected volatile Page<K, V> rootPage;
97  
98      /** The list of read transactions being executed */
99      private ConcurrentLinkedQueue<Transaction<K, V>> readTransactions;
100 
101     /** The size of the buffer used to write data in disk */
102     private int writeBufferSize;
103 
104     /** The type to use to create the keys */
105     protected Class<?> keyType;
106 
107     /** The Key serializer used for this tree.*/
108     private ElementSerializer<K> keySerializer;
109 
110     /** The Value serializer used for this tree. */
111     private ElementSerializer<V> valueSerializer;
112 
113     /** The associated file. If null, this is an in-memory btree  */
114     private File file;
115 
116     /** The BTree type : either in-memory, persistent or managed */
117     private BTreeTypeEnum type;
118 
119     /** A flag used to tell the BTree that the journal is activated */
120     private boolean withJournal;
121 
122     /** The associated journal. If null, this is an in-memory btree  */
123     private File journal;
124 
125     /** A lock used to protect the write operation against concurrent access */
126     private ReentrantLock writeLock;
127 
128     /** The thread responsible for the cleanup of timed out reads */
129     private Thread readTransactionsThread;
130 
131     /** Define a default delay for a read transaction. This is 10 seconds */
132     public static final long DEFAULT_READ_TIMEOUT = 10 * 1000L;
133 
134     /** The read transaction timeout */
135     private long readTimeOut = DEFAULT_READ_TIMEOUT;
136 
137     private File envDir;
138 
139     private FileChannel journalChannel = null;
140 
141     /** The cache associated with this BTree */
142     private Cache cache;
143 
144     /** The cache size, default to 1000 elements */
145     private int cacheSize = DEFAULT_CACHE_SIZE;
146 
147     /** The default number of pages to keep in memory */
148     private static final int DEFAULT_CACHE_SIZE = 1000;
149 
150 
151     /**
152      * Create a thread that is responsible of cleaning the transactions when
153      * they hit the timeout
154      */
155     private void createTransactionManager()
156     {
157         Runnable readTransactionTask = new Runnable()
158         {
159             public void run()
160             {
161                 try
162                 {
163                     Transaction<K, V> transaction = null;
164 
165                     while ( !Thread.currentThread().isInterrupted() )
166                     {
167                         long timeoutDate = System.currentTimeMillis() - readTimeOut;
168                         long t0 = System.currentTimeMillis();
169                         int nbTxns = 0;
170 
171                         // Loop on all the transactions from the queue
172                         while ( ( transaction = readTransactions.peek() ) != null )
173                         {
174                             nbTxns++;
175 
176                             if ( transaction.isClosed() )
177                             {
178                                 // The transaction is already closed, remove it from the queue
179                                 readTransactions.poll();
180                                 continue;
181                             }
182 
183                             // Check if the transaction has timed out
184                             if ( transaction.getCreationDate() < timeoutDate )
185                             {
186                                 transaction.close();
187                                 readTransactions.poll();
188                                 continue;
189                             }
190 
191                             // We need to stop now
192                             break;
193                         }
194 
195                         long t1 = System.currentTimeMillis();
196 
197                         if ( nbTxns > 0 )
198                         {
199                             System.out.println( "Processing old txn : " + nbTxns + ", " + ( t1 - t0 ) + "ms" );
200                         }
201 
202                         // Wait until we reach the timeout
203                         Thread.sleep( readTimeOut );
204                     }
205                 }
206                 catch ( InterruptedException ie )
207                 {
208                     //System.out.println( "Interrupted" );
209                 }
210                 catch ( Exception e )
211                 {
212                     throw new RuntimeException( e );
213                 }
214             }
215         };
216 
217         readTransactionsThread = new Thread( readTransactionTask );
218         readTransactionsThread.setDaemon( true );
219         readTransactionsThread.start();
220     }
221 
222 
223     /**
224      * Creates a new BTree, with no initialization. 
225      */
226     public BTree()
227     {
228         btreeHeader = new BTreeHeader();
229         type = BTreeTypeEnum.IN_MEMORY;
230     }
231 
232 
233     /**
234      * Creates a new in-memory BTree using the BTreeConfiguration to initialize the 
235      * BTree
236      * 
237      * @param comparator The comparator to use
238      */
239     public BTree( BTreeConfiguration<K, V> configuration ) throws IOException
240     {
241         String name = configuration.getName();
242 
243         if ( name == null )
244         {
245             throw new IllegalArgumentException( "BTree name cannot be null" );
246         }
247 
248         String filePath = configuration.getFilePath();
249 
250         if ( filePath != null )
251         {
252             envDir = new File( filePath );
253         }
254 
255         btreeHeader = new BTreeHeader();
256         btreeHeader.setName( name );
257         btreeHeader.setPageSize( configuration.getPageSize() );
258 
259         keySerializer = configuration.getKeySerializer();
260         btreeHeader.setKeySerializerFQCN( keySerializer.getClass().getName() );
261 
262         valueSerializer = configuration.getValueSerializer();
263         btreeHeader.setValueSerializerFQCN( valueSerializer.getClass().getName() );
264 
265         readTimeOut = configuration.getReadTimeOut();
266         writeBufferSize = configuration.getWriteBufferSize();
267         btreeHeader.setAllowDuplicates( configuration.isAllowDuplicates() );
268         type = configuration.getType();
269         cacheSize = configuration.getCacheSize();
270 
271         if ( keySerializer.getComparator() == null )
272         {
273             throw new IllegalArgumentException( "Comparator should not be null" );
274         }
275 
276         // Create the first root page, with revision 0L. It will be empty
277         // and increment the revision at the same time
278         rootPage = new Leaf<K, V>( this );
279 
280         // Now, initialize the BTree
281         init();
282     }
283 
284 
285     /**
286      * Creates a new in-memory BTree with a default page size and key/value serializers.
287      * 
288      * @param comparator The comparator to use
289      */
290     public BTree( String name, ElementSerializer<K> keySerializer, ElementSerializer<V> valueSerializer )
291         throws IOException
292     {
293         this( name, keySerializer, valueSerializer, false );
294     }
295 
296 
297     public BTree( String name, ElementSerializer<K> keySerializer, ElementSerializer<V> valueSerializer,
298         boolean allowDuplicates )
299         throws IOException
300     {
301         this( name, null, keySerializer, valueSerializer, DEFAULT_PAGE_SIZE, allowDuplicates, DEFAULT_CACHE_SIZE );
302     }
303 
304 
305     /**
306      * Creates a new in-memory BTree with a default page size and key/value serializers.
307      * 
308      * @param comparator The comparator to use
309      */
310     public BTree( String name, ElementSerializer<K> keySerializer, ElementSerializer<V> valueSerializer, int pageSize )
311         throws IOException
312     {
313         this( name, null, keySerializer, valueSerializer, pageSize );
314     }
315 
316 
317     /**
318      * Creates a new BTree with a default page size and a comparator, with an associated file.
319      * @param comparator The comparator to use
320      * @param serializer The serializer to use
321      */
322     public BTree( String name, String path, ElementSerializer<K> keySerializer, ElementSerializer<V> valueSerializer )
323         throws IOException
324     {
325         this( name, path, keySerializer, valueSerializer, DEFAULT_PAGE_SIZE );
326     }
327 
328 
329     /**
330      * 
331      * Creates a new instance of BTree with the given name and store it under the given dataDir if provided.
332      *
333      * @param name the name of the BTree
334      * @param dataDir the name of the data directory with absolute path
335      * @param keySerializer key serializer
336      * @param valueSerializer value serializer
337      * @param pageSize size of the page
338      * @throws IOException
339      */
340     public BTree( String name, String dataDir, ElementSerializer<K> keySerializer,
341         ElementSerializer<V> valueSerializer,
342         int pageSize )
343         throws IOException
344     {
345         this( name, dataDir, keySerializer, valueSerializer, pageSize, false, DEFAULT_CACHE_SIZE );
346     }
347 
348 
349     public BTree( String name, String dataDir, ElementSerializer<K> keySerializer,
350         ElementSerializer<V> valueSerializer,
351         int pageSize, boolean allowDuplicates )
352         throws IOException
353     {
354         this( name, dataDir, keySerializer, valueSerializer, pageSize, allowDuplicates, DEFAULT_CACHE_SIZE );
355     }
356 
357 
358     public BTree( String name, String dataDir, ElementSerializer<K> keySerializer,
359         ElementSerializer<V> valueSerializer,
360         int pageSize, boolean allowDuplicates, int cacheSize )
361         throws IOException
362     {
363         btreeHeader = new BTreeHeader();
364         btreeHeader.setName( name );
365 
366         if ( dataDir != null )
367         {
368             envDir = new File( dataDir );
369         }
370 
371         setPageSize( pageSize );
372         writeBufferSize = DEFAULT_WRITE_BUFFER_SIZE;
373 
374         this.cacheSize = cacheSize;
375 
376         this.keySerializer = keySerializer;
377 
378         btreeHeader.setKeySerializerFQCN( keySerializer.getClass().getName() );
379 
380         this.valueSerializer = valueSerializer;
381 
382         btreeHeader.setValueSerializerFQCN( valueSerializer.getClass().getName() );
383 
384         btreeHeader.setAllowDuplicates( allowDuplicates );
385 
386         // Create the first root page, with revision 0L. It will be empty
387         // and increment the revision at the same time
388         rootPage = new Leaf<K, V>( this );
389 
390         // Now, call the init() method
391         init();
392     }
393 
394 
395     /**
396      * Initialize the BTree.
397      * 
398      * @throws IOException If we get some exception while initializing the BTree
399      */
400     public void init() throws IOException
401     {
402         // if not in-memory then default to persist mode instead of managed
403         if ( envDir != null )
404         {
405             if ( !envDir.exists() )
406             {
407                 boolean created = envDir.mkdirs();
408                 if ( !created )
409                 {
410                     throw new IllegalStateException( "Could not create the directory " + envDir + " for storing data" );
411                 }
412             }
413 
414             this.file = new File( envDir, btreeHeader.getName() + DATA_SUFFIX );
415 
416             this.journal = new File( envDir, file.getName() + JOURNAL_SUFFIX );
417             type = BTreeTypeEnum.PERSISTENT;
418         }
419 
420         // Create the queue containing the pending read transactions
421         readTransactions = new ConcurrentLinkedQueue<Transaction<K, V>>();
422 
423         // We will extract the Type to use for keys, using the comparator for that
424         Class<?> comparatorClass = keySerializer.getComparator().getClass();
425         Type[] types = comparatorClass.getGenericInterfaces();
426 
427         if ( types[0] instanceof Class )
428         {
429             keyType = ( Class<?> ) types[0];
430         }
431         else
432         {
433             Type[] argumentTypes = ( ( ParameterizedType ) types[0] ).getActualTypeArguments();
434 
435             if ( ( argumentTypes != null ) && ( argumentTypes.length > 0 ) && ( argumentTypes[0] instanceof Class<?> ) )
436             {
437                 keyType = ( Class<?> ) argumentTypes[0];
438             }
439         }
440 
441         writeLock = new ReentrantLock();
442 
443         // Check the files and create them if missing
444         // Create the queue containing the modifications, if it's not a in-memory btree
445         if ( type == BTreeTypeEnum.PERSISTENT )
446         {
447             if ( file.length() > 0 )
448             {
449                 // We have some existing file, load it 
450                 load( file );
451             }
452 
453             withJournal = true;
454 
455             FileOutputStream stream = new FileOutputStream( journal );
456             journalChannel = stream.getChannel();
457 
458             // If the journal is not empty, we have to read it
459             // and to apply all the modifications to the current file
460             if ( journal.length() > 0 )
461             {
462                 applyJournal();
463             }
464         }
465         else if ( type == null )
466         {
467             type = BTreeTypeEnum.IN_MEMORY;
468         }
469 
470         // Initialize the caches
471         CacheConfiguration cacheConfiguration = new CacheConfiguration();
472         cacheConfiguration.setName( "pages" );
473         cacheConfiguration.setEternal( true );
474         cacheConfiguration.setOverflowToDisk( false );
475         cacheConfiguration.setCacheLoaderTimeoutMillis( 0 );
476         cacheConfiguration.setMaxElementsInMemory( cacheSize );
477         cacheConfiguration.setMemoryStoreEvictionPolicy( "LRU" );
478 
479         cache = new Cache( cacheConfiguration );
480         cache.initialise();
481 
482         // Initialize the txnManager thread
483         //FIXME we should NOT create a new transaction manager thread for each BTree
484         //createTransactionManager();
485     }
486 
487 
488     /**
489      * Return the cache we use in this BTree
490      */
491     /* No qualifier */Cache getCache()
492     {
493         return cache;
494     }
495 
496 
497     /**
498      * Close the BTree, cleaning up all the data structure
499      */
500     public void close() throws IOException
501     {
502         // Stop the readTransaction thread
503         // readTransactionsThread.interrupt();
504         // readTransactions.clear();
505 
506         if ( type == BTreeTypeEnum.PERSISTENT )
507         {
508             // Flush the data
509             flush();
510             journalChannel.close();
511         }
512 
513         rootPage = null;
514     }
515 
516 
517     /**
518      * @return the btreeOffset
519      */
520     /* No qualifier*/long getBtreeOffset()
521     {
522         return btreeHeader.getBTreeOffset();
523     }
524 
525 
526     /**
527      * @param btreeOffset the btreeOffset to set
528      */
529     /* No qualifier*/void setBtreeOffset( long btreeOffset )
530     {
531         btreeHeader.setBTreeOffset( btreeOffset );
532     }
533 
534 
535     /**
536      * @return the rootPageOffset
537      */
538     /* No qualifier*/long getRootPageOffset()
539     {
540         return btreeHeader.getRootPageOffset();
541     }
542 
543 
544     /**
545      * @param rootPageOffset the rootPageOffset to set
546      */
547     /* No qualifier*/void setRootPageOffset( long rootPageOffset )
548     {
549         btreeHeader.setRootPageOffset( rootPageOffset );
550     }
551 
552 
553     /**
554      * @return the nextBTreeOffset
555      */
556     /* No qualifier*/long getNextBTreeOffset()
557     {
558         return btreeHeader.getNextBTreeOffset();
559     }
560 
561 
562     /**
563      * @param nextBTreeOffset the nextBTreeOffset to set
564      */
565     /* No qualifier*/void setNextBTreeOffset( long nextBTreeOffset )
566     {
567         btreeHeader.setNextBTreeOffset( nextBTreeOffset );
568     }
569 
570 
571     /**
572      * Gets the number which is a power of 2 immediately above the given positive number.
573      */
574     private int getPowerOf2( int size )
575     {
576         int newSize = --size;
577         newSize |= newSize >> 1;
578         newSize |= newSize >> 2;
579         newSize |= newSize >> 4;
580         newSize |= newSize >> 8;
581         newSize |= newSize >> 16;
582         newSize++;
583 
584         return newSize;
585     }
586 
587 
588     /**
589      * Set the maximum number of elements we can store in a page. This must be a
590      * number greater than 1, and a power of 2. The default page size is 16.
591      * <br/>
592      * If the provided size is below 2, we will default to DEFAULT_PAGE_SIZE.<br/>
593      * If the provided size is not a power of 2, we will select the closest power of 2
594      * higher than the given number<br/>
595      * 
596      * @param pageSize The requested page size
597      */
598     public void setPageSize( int pageSize )
599     {
600         if ( pageSize <= 2 )
601         {
602             btreeHeader.setPageSize( DEFAULT_PAGE_SIZE );
603         }
604         else
605         {
606             btreeHeader.setPageSize( getPowerOf2( pageSize ) );
607         }
608     }
609 
610 
611     /**
612      * Set the new root page for this tree. Used for debug purpose only. The revision
613      * will always be 0;
614      * 
615      * @param root the new root page.
616      */
617     /* No qualifier */void setRoot( Page<K, V> root )
618     {
619         rootPage = root;
620     }
621 
622 
623     /**
624      * @return the pageSize
625      */
626     public int getPageSize()
627     {
628         return btreeHeader.getPageSize();
629     }
630 
631 
632     /**
633      * Generates a new revision number. It's only used by the Page instances.
634      * 
635      * @return a new incremental revision number
636      */
637     /** No qualifier */
638     long generateRevision()
639     {
640         return btreeHeader.incrementRevision();
641     }
642 
643 
644     /**
645      * Insert an entry in the BTree.
646      * <p>
647      * We will replace the value if the provided key already exists in the
648      * btree.
649      *
650      * @param key Inserted key
651      * @param value Inserted value
652      * @return Existing value, if any.
653      * @throws IOException TODO
654      */
655     public V insert( K key, V value ) throws IOException
656     {
657         long revision = generateRevision();
658 
659         V existingValue = null;
660 
661         try
662         {
663             // Commented atm, we will have to play around the idea of transactions later
664             writeLock.lock();
665 
666             InsertResult<K, V> result = insert( key, value, revision );
667 
668             if ( result instanceof ModifyResult )
669             {
670                 existingValue = ( (org.apache.directory.mavibot.btree.ModifyResult<K, V> ) result ).getModifiedValue();
671             }
672         }
673         finally
674         {
675             // See above
676             writeLock.unlock();
677         }
678 
679         return existingValue;
680     }
681 
682 
683     /**
684      * Delete the entry which key is given as a parameter. If the entry exists, it will
685      * be removed from the tree, the old tuple will be returned. Otherwise, null is returned.
686      * 
687      * @param key The key for the entry we try to remove
688      * @return A Tuple<K, V> containing the removed entry, or null if it's not found.
689      */
690     public Tuple<K, V> delete( K key ) throws IOException
691     {
692         if ( key == null )
693         {
694             throw new IllegalArgumentException( "Key must not be null" );
695         }
696 
697         long revision = generateRevision();
698 
699         Tuple<K, V> deleted = delete( key, revision );
700 
701         return deleted;
702     }
703 
704 
705     /**
706      * Delete the value from an entry associated with the given key. If the value
707      * If the value is present, it will be deleted first, later if there are no other 
708      * values associated with this key(which can happen when duplicates are enabled), 
709      * we will remove the key from the tree.
710      * 
711      * @param key The key for the entry we try to remove
712      * @param value The value to delete (can be null)
713      * @return A Tuple<K, V> containing the removed entry, or null if it's not found.
714      */
715     public Tuple<K, V> delete( K key, V value ) throws IOException
716     {
717         if ( key == null )
718         {
719             throw new IllegalArgumentException( "Key must not be null" );
720         }
721 
722         if ( value == null )
723         {
724             throw new IllegalArgumentException( "Value must not be null" );
725         }
726 
727         long revision = generateRevision();
728 
729         Tuple<K, V> deleted = delete( key, value, revision );
730 
731         return deleted;
732     }
733 
734 
735     /**
736      * Delete the entry which key is given as a parameter. If the entry exists, it will
737      * be removed from the tree, the old tuple will be returned. Otherwise, null is returned.
738      * 
739      * @param key The key for the entry we try to remove
740      * @return A Tuple<K, V> containing the removed entry, or null if it's not found.
741      */
742     private Tuple<K, V> delete( K key, long revision ) throws IOException
743     {
744         return delete( key, null, revision );
745     }
746 
747 
748     /**
749      * 
750      * Deletes the given <key,value> pair if both key and value match. If the given value is null
751      * and there is no null value associated with the given key then the entry with the given key
752      * will be removed.
753      *
754      * @param key The key to be removed 
755      * @param value The value to be removed (can be null, and when no null value exists the key will be removed irrespective of the value)
756      * @param revision The revision to be associated with this operation
757      * @return
758      * @throws IOException
759      */
760     private Tuple<K, V> delete( K key, V value, long revision ) throws IOException
761     {
762         writeLock.lock();
763 
764         try
765         {
766             // If the key exists, the existing value will be replaced. We store it
767             // to return it to the caller.
768             Tuple<K, V> tuple = null;
769 
770             // Try to delete the entry starting from the root page. Here, the root
771             // page may be either a Node or a Leaf
772             DeleteResult<K, V> result = rootPage.delete( revision, key, value, null, -1 );
773 
774             if ( result instanceof NotPresentResult )
775             {
776                 // Key not found.
777                 return null;
778             }
779 
780             // Keep the oldRootPage so that we can later access it
781             Page<K, V> oldRootPage = rootPage;
782 
783             if ( result instanceof RemoveResult )
784             {
785                 // The element was found, and removed
786                 RemoveResult<K, V> removeResult = (org.apache.directory.mavibot.btree.RemoveResult<K, V> ) result;
787 
788                 Page<K, V> modifiedPage = removeResult.getModifiedPage();
789 
790                 // This is a new root
791                 rootPage = modifiedPage;
792                 tuple = removeResult.getRemovedElement();
793             }
794 
795             if ( withJournal )
796             {
797                 // Inject the modification into the modification queue
798                 writeToJournal( new Deletion<K, V>( key ) );
799             }
800 
801             // Decrease the number of elements in the current tree if the deletion is successful
802             if ( tuple != null )
803             {
804                 btreeHeader.decrementNbElems();
805             }
806 
807             // Return the value we have found if it was modified
808             return tuple;
809         }
810         finally
811         {
812             // See above
813             writeLock.unlock();
814         }
815     }
816 
817 
818     /**
819      * Find a value in the tree, given its key. If the key is not found,
820      * it will throw a KeyNotFoundException. <br/>
821      * Note that we can get a null value stored, or many values.
822      * 
823      * @param key The key we are looking at
824      * @return The found value, or null if the key is not present in the tree
825      * @throws KeyNotFoundException If the key is not found in the BTree
826      * @throws IOException TODO
827      */
828     public V get( K key ) throws IOException, KeyNotFoundException
829     {
830         return rootPage.get( key );
831     }
832 
833 
834     /**
835      * @see Page#getValues(Object)
836      */
837     public ValueCursor<V> getValues( K key ) throws IOException, KeyNotFoundException
838     {
839         return rootPage.getValues( key );
840     }
841 
842 
843     /**
844      * Find a value in the tree, given its key, at a specific revision. If the key is not found,
845      * it will throw a KeyNotFoundException. <br/>
846      * Note that we can get a null value stored, or many values.
847      * 
848      * @param revision The revision for which we want to find a key
849      * @param key The key we are looking at
850      * @return The found value, or null if the key is not present in the tree
851      * @throws KeyNotFoundException If the key is not found in the BTree
852      * @throws IOException If there was an issue while fetching data from the disk
853      */
854     public V get( long revision, K key ) throws IOException, KeyNotFoundException
855     {
856         // Fetch the root page for this revision
857         Page<K, V> revisionRootPage = getRootPage( revision );
858 
859         return revisionRootPage.get( key );
860     }
861 
862 
863     /**
864      * Checks if the given key exists.
865      *  
866      * @param key The key we are looking at
867      * @return true if the key is present, false otherwise
868      * @throws IOException If we have an error while trying to access the page
869      */
870     public boolean hasKey( K key ) throws IOException
871     {
872         if ( key == null )
873         {
874             return false;
875         }
876 
877         return rootPage.hasKey( key );
878     }
879 
880 
881     /**
882      * Checks if the given key exists for a given revision.
883      *  
884      * @param revision The revision for which we want to find a key
885      * @param key The key we are looking at
886      * @return true if the key is present, false otherwise
887      * @throws IOException If we have an error while trying to access the page
888      * @throws KeyNotFoundException If the key is not found in the BTree
889      */
890     public boolean hasKey( long revision, K key ) throws IOException, KeyNotFoundException
891     {
892         if ( key == null )
893         {
894             return false;
895         }
896 
897         // Fetch the root page for this revision
898         Page<K, V> revisionRootPage = getRootPage( revision );
899 
900         return revisionRootPage.hasKey( key );
901     }
902 
903 
904     /**
905      * Checks if the BTree contains the given key with the given value.
906      * 
907      * @param key The key we are looking for
908      * @param value The value associated with the given key
909      * @return true if the key and value are associated with each other, false otherwise
910      */
911     public boolean contains( K key, V value ) throws IOException
912     {
913         return rootPage.contains( key, value );
914     }
915 
916 
917     /**
918      * Checks if the BTree contains the given key with the given value for a given revision
919      * 
920      * @param revision The revision we would like to browse
921      * @param key The key we are looking for
922      * @param value The value associated with the given key
923      * @return true if the key and value are associated with each other, false otherwise
924      * @throws KeyNotFoundException If the key is not found in the BTree
925      */
926     public boolean contains( long revision, K key, V value ) throws IOException, KeyNotFoundException
927     {
928         // Fetch the root page for this revision
929         Page<K, V> revisionRootPage = getRootPage( revision );
930 
931         return revisionRootPage.contains( key, value );
932     }
933 
934 
935     /**
936      * Creates a cursor starting at the beginning of the tree
937      * 
938      * @return A cursor on the btree
939      * @throws IOException
940      */
941     public TupleCursor<K, V> browse() throws IOException
942     {
943         Transaction<K, V> transaction = beginReadTransaction();
944 
945         // Fetch the root page for this revision
946         TupleCursor<K, V> cursor = rootPage.browse( transaction, new ParentPos[32], 0 );
947         
948         // Set the position before the first element
949         cursor.beforeFirst();
950 
951         return cursor;
952     }
953 
954 
955     /**
956      * Creates a cursor starting at the beginning of the tree, for a given revision
957      * 
958      * @param revision The revision we would like to browse
959      * @return A cursor on the btree
960      * @throws IOException If we had an issue while fetching data from the disk
961      * @throws KeyNotFoundException If the key is not found in the BTree
962      */
963     public TupleCursor<K, V> browse( long revision ) throws IOException, KeyNotFoundException
964     {
965         Transaction<K, V> transaction = beginReadTransaction();
966 
967         // Fetch the root page for this revision
968         Page<K, V> revisionRootPage = getRootPage( revision );
969 
970         // And get the cursor
971         TupleCursor<K, V> cursor = revisionRootPage.browse( transaction, new ParentPos[32], 0 );
972 
973         return cursor;
974     }
975 
976 
977     /**
978      * Creates a cursor starting on the given key
979      * 
980      * @param key The key which is the starting point. If the key is not found,
981      * then the cursor will always return null.
982      * @return A cursor on the btree
983      * @throws IOException
984      */
985     public TupleCursor<K, V> browseFrom( K key ) throws IOException
986     {
987         Transaction<K, V> transaction = beginReadTransaction();
988 
989         // Fetch the root page for this revision
990         TupleCursor<K, V> cursor = rootPage.browse( key, transaction, new ParentPos[32], 0 );
991 
992         return cursor;
993     }
994 
995 
996     /**
997      * Creates a cursor starting on the given key at the given revision
998      * 
999      * @param The revision we are looking for
1000      * @param key The key which is the starting point. If the key is not found,
1001      * then the cursor will always return null.
1002      * @return A cursor on the btree
1003      * @throws IOException If wxe had an issue reading the BTree from disk
1004      * @throws KeyNotFoundException  If we can't find a rootPage for this revision
1005      */
1006     public TupleCursor<K, V> browseFrom( long revision, K key ) throws IOException, KeyNotFoundException
1007     {
1008         Transaction<K, V> transaction = beginReadTransaction();
1009 
1010         // Fetch the rootPage for this revision
1011         Page<K, V> revisionRootPage = getRootPage( revision );
1012 
1013         // And get the cursor
1014         TupleCursor<K, V> cursor = revisionRootPage.browse( key, transaction, new ParentPos[32], 0 );
1015 
1016         return cursor;
1017     }
1018 
1019 
1020     /**
1021      * Insert an entry in the BTree.
1022      * <p>
1023      * We will replace the value if the provided key already exists in the
1024      * btree.
1025      * <p>
1026      * The revision number is the revision to use to insert the data.
1027      *
1028      * @param key Inserted key
1029      * @param value Inserted value
1030      * @param revision The revision to use
1031      * @return an instance of the InsertResult.
1032      */
1033     /*No qualifier*/InsertResult<K, V> insert( K key, V value, long revision ) throws IOException
1034     {
1035         if ( key == null )
1036         {
1037             throw new IllegalArgumentException( "Key must not be null" );
1038         }
1039 
1040         // If the key exists, the existing value will be replaced. We store it
1041         // to return it to the caller.
1042         V modifiedValue = null;
1043 
1044         // Try to insert the new value in the tree at the right place,
1045         // starting from the root page. Here, the root page may be either
1046         // a Node or a Leaf
1047         InsertResult<K, V> result = rootPage.insert( revision, key, value );
1048 
1049         if ( result instanceof ModifyResult )
1050         {
1051             ModifyResult<K, V> modifyResult = ( (org.apache.directory.mavibot.btree.ModifyResult<K, V> ) result );
1052 
1053             Page<K, V> modifiedPage = modifyResult.getModifiedPage();
1054 
1055             // The root has just been modified, we haven't split it
1056             // Get it and make it the current root page
1057             rootPage = modifiedPage;
1058 
1059             modifiedValue = modifyResult.getModifiedValue();
1060         }
1061         else
1062         {
1063             // We have split the old root, create a new one containing
1064             // only the pivotal we got back
1065             SplitResult<K, V> splitResult = ( (org.apache.directory.mavibot.btree.SplitResult<K, V> ) result );
1066 
1067             K pivot = splitResult.getPivot();
1068             Page<K, V> leftPage = splitResult.getLeftPage();
1069             Page<K, V> rightPage = splitResult.getRightPage();
1070             Page<K, V> newRootPage = null;
1071 
1072             // Create the new rootPage
1073             newRootPage = new Node<K, V>( this, revision, pivot, leftPage, rightPage );
1074 
1075             rootPage = newRootPage;
1076         }
1077 
1078         // Inject the modification into the modification queue
1079         if ( withJournal )
1080         {
1081             writeToJournal( new Addition<K, V>( key, value ) );
1082         }
1083 
1084         // Increase the number of element in the current tree if the insertion is successful
1085         // and does not replace an element
1086         if ( modifiedValue == null )
1087         {
1088             btreeHeader.incrementNbElems();
1089         }
1090 
1091         // Return the value we have found if it was modified
1092         return result;
1093     }
1094 
1095 
1096     /**
1097      * Starts a Read Only transaction. If the transaction is not closed, it will be 
1098      * automatically closed after the timeout
1099      * @return The created transaction
1100      */
1101     private Transaction<K, V> beginReadTransaction()
1102     {
1103         Transaction<K, V> readTransaction = new Transaction<K, V>( rootPage, btreeHeader.getRevision() - 1,
1104             System.currentTimeMillis() );
1105 
1106         readTransactions.add( readTransaction );
1107 
1108         return readTransaction;
1109     }
1110 
1111 
1112     /**
1113      * @return the type for the keys
1114      */
1115     /* No qualifier*/Class<?> getKeyType()
1116     {
1117         return keyType;
1118     }
1119 
1120 
1121     /**
1122      * @return the comparator
1123      */
1124     public Comparator<K> getComparator()
1125     {
1126         return keySerializer.getComparator();
1127     }
1128 
1129 
1130     /**
1131      * @param keySerializer the Key serializer to set
1132      */
1133     public void setKeySerializer( ElementSerializer<K> keySerializer )
1134     {
1135         this.keySerializer = keySerializer;
1136         btreeHeader.setKeySerializerFQCN( keySerializer.getClass().getName() );
1137     }
1138 
1139 
1140     /**
1141      * @param valueSerializer the Value serializer to set
1142      */
1143     public void setValueSerializer( ElementSerializer<V> valueSerializer )
1144     {
1145         this.valueSerializer = valueSerializer;
1146         btreeHeader.setValueSerializerFQCN( valueSerializer.getClass().getName() );
1147     }
1148 
1149 
1150     /**
1151      * Write the data in the ByteBuffer, and eventually on disk if needed.
1152      * 
1153      * @param channel The channel we want to write to
1154      * @param bb The ByteBuffer we want to feed
1155      * @param buffer The data to inject
1156      * @throws IOException If the write failed
1157      */
1158     private void writeBuffer( FileChannel channel, ByteBuffer bb, byte[] buffer ) throws IOException
1159     {
1160         int size = buffer.length;
1161         int pos = 0;
1162 
1163         // Loop until we have written all the data
1164         do
1165         {
1166             if ( bb.remaining() >= size )
1167             {
1168                 // No flush, as the ByteBuffer is big enough
1169                 bb.put( buffer, pos, size );
1170                 size = 0;
1171             }
1172             else
1173             {
1174                 // Flush the data on disk, reinitialize the ByteBuffer
1175                 int len = bb.remaining();
1176                 size -= len;
1177                 bb.put( buffer, pos, len );
1178                 pos += len;
1179 
1180                 bb.flip();
1181 
1182                 channel.write( bb );
1183 
1184                 bb.clear();
1185             }
1186         }
1187         while ( size > 0 );
1188     }
1189 
1190 
1191     /**
1192      * Flush the latest revision to disk
1193      * @param file The file into which the data will be written
1194      */
1195     public void flush( File file ) throws IOException
1196     {
1197         File parentFile = file.getParentFile();
1198         File baseDirectory = null;
1199 
1200         if ( parentFile != null )
1201         {
1202             baseDirectory = new File( file.getParentFile().getAbsolutePath() );
1203         }
1204         else
1205         {
1206             baseDirectory = new File( "." );
1207         }
1208 
1209         // Create a temporary file in the same directory to flush the current btree
1210         File tmpFileFD = File.createTempFile( "mavibot", null, baseDirectory );
1211         FileOutputStream stream = new FileOutputStream( tmpFileFD );
1212         FileChannel ch = stream.getChannel();
1213 
1214         // Create a buffer containing 200 4Kb pages (around 1Mb)
1215         ByteBuffer bb = ByteBuffer.allocateDirect( writeBufferSize );
1216 
1217         TupleCursor<K, V> cursor = browse();
1218 
1219         if ( keySerializer == null )
1220         {
1221             throw new RuntimeException( "Cannot flush the btree without a Key serializer" );
1222         }
1223 
1224         if ( valueSerializer == null )
1225         {
1226             throw new RuntimeException( "Cannot flush the btree without a Value serializer" );
1227         }
1228 
1229         // Write the number of elements first
1230         bb.putLong( btreeHeader.getNbElems() );
1231 
1232         while ( cursor.hasNext() )
1233         {
1234             Tuple<K, V> tuple = cursor.next();
1235 
1236             byte[] keyBuffer = keySerializer.serialize( tuple.getKey() );
1237 
1238             writeBuffer( ch, bb, keyBuffer );
1239 
1240             byte[] valueBuffer = valueSerializer.serialize( tuple.getValue() );
1241 
1242             writeBuffer( ch, bb, valueBuffer );
1243         }
1244 
1245         // Write the buffer if needed
1246         if ( bb.position() > 0 )
1247         {
1248             bb.flip();
1249             ch.write( bb );
1250         }
1251 
1252         // Flush to the disk for real
1253         ch.force( true );
1254         ch.close();
1255 
1256         // Rename the current file to save a backup
1257         File backupFile = File.createTempFile( "mavibot", null, baseDirectory );
1258         file.renameTo( backupFile );
1259 
1260         // Rename the temporary file to the initial file
1261         tmpFileFD.renameTo( file );
1262 
1263         // We can now delete the backup file
1264         backupFile.delete();
1265     }
1266 
1267 
1268     /** 
1269      * Inject all the modification from the journal into the btree
1270      * 
1271      * @throws IOException If we had some issue while reading the journal
1272      */
1273     private void applyJournal() throws IOException
1274     {
1275         long revision = generateRevision();
1276 
1277         if ( !journal.exists() )
1278         {
1279             throw new IOException( "The journal does not exist" );
1280         }
1281 
1282         FileChannel channel =
1283             new RandomAccessFile( journal, "rw" ).getChannel();
1284         ByteBuffer buffer = ByteBuffer.allocate( 65536 );
1285 
1286         BufferHandler bufferHandler = new BufferHandler( channel, buffer );
1287 
1288         // Loop on all the elements, store them in lists atm
1289         try
1290         {
1291             while ( true )
1292             {
1293                 // Read the type 
1294                 byte[] type = bufferHandler.read( 1 );
1295 
1296                 if ( type[0] == Modification.ADDITION )
1297                 {
1298                     // Read the key
1299                     K key = keySerializer.deserialize( bufferHandler );
1300 
1301                     //keys.add( key );
1302 
1303                     // Read the value
1304                     V value = valueSerializer.deserialize( bufferHandler );
1305 
1306                     //values.add( value );
1307 
1308                     // Inject the data in the tree. (to be replaced by a bulk load)
1309                     insert( key, value, revision );
1310                 }
1311                 else
1312                 {
1313                     // Read the key
1314                     K key = keySerializer.deserialize( bufferHandler );
1315 
1316                     // Remove the key from the tree
1317                     delete( key, revision );
1318                 }
1319             }
1320         }
1321         catch ( EOFException eofe )
1322         {
1323             eofe.printStackTrace();
1324             // Done reading the journal. truncate it
1325             journalChannel.truncate( 0 );
1326         }
1327     }
1328 
1329 
1330     /**
1331      * Read the data from the disk into this BTree. All the existing data in the 
1332      * BTree are kept, the read data will be associated with a new revision.
1333      * 
1334      * @param file
1335      * @throws IOException
1336      */
1337     public void load( File file ) throws IOException
1338     {
1339         long revision = generateRevision();
1340 
1341         if ( !file.exists() )
1342         {
1343             throw new IOException( "The file does not exist" );
1344         }
1345 
1346         FileChannel channel =
1347             new RandomAccessFile( file, "rw" ).getChannel();
1348         ByteBuffer buffer = ByteBuffer.allocate( 65536 );
1349 
1350         BufferHandler bufferHandler = new BufferHandler( channel, buffer );
1351 
1352         long nbElems = LongSerializer.deserialize( bufferHandler.read( 8 ) );
1353         btreeHeader.setNbElems( nbElems );
1354 
1355         // Prepare a list of keys and values read from the disk
1356         //List<K> keys = new ArrayList<K>();
1357         //List<V> values = new ArrayList<V>();
1358 
1359         // desactivate the journal while we load the file
1360         boolean isJournalActivated = withJournal;
1361 
1362         withJournal = false;
1363 
1364         // Loop on all the elements, store them in lists atm
1365         for ( long i = 0; i < nbElems; i++ )
1366         {
1367             // Read the key
1368             K key = keySerializer.deserialize( bufferHandler );
1369 
1370             //keys.add( key );
1371 
1372             // Read the value
1373             V value = valueSerializer.deserialize( bufferHandler );
1374 
1375             //values.add( value );
1376 
1377             // Inject the data in the tree. (to be replaced by a bulk load)
1378             insert( key, value, revision );
1379         }
1380 
1381         // Restore the withJournal value
1382         withJournal = isJournalActivated;
1383 
1384         // Now, process the lists to create the btree
1385         // TODO... BulkLoad
1386     }
1387 
1388 
1389     /**
1390      * Get the rootPzge associated to a give revision.
1391      * 
1392      * @param revision The revision we are looking for
1393      * @return The rootPage associated to this revision
1394      * @throws IOException If we had an issue while accessing the underlying file
1395      * @throws KeyNotFoundException If the revision does not exist for this Btree
1396      */
1397     private Page<K, V> getRootPage( long revision ) throws IOException, KeyNotFoundException
1398     {
1399         // Atm, the in-memory BTree does not support searches in many revisions
1400         return rootPage;
1401     }
1402 
1403 
1404     /**
1405      * Flush the latest revision to disk. We will replace the current file by the new one, as
1406      * we flush in a temporary file.
1407      */
1408     public void flush() throws IOException
1409     {
1410         if ( type == BTreeTypeEnum.PERSISTENT )
1411         {
1412             // Then flush the file
1413             flush( file );
1414             journalChannel.truncate( 0 );
1415         }
1416     }
1417 
1418 
1419     /**
1420      * @return the readTimeOut
1421      */
1422     public long getReadTimeOut()
1423     {
1424         return readTimeOut;
1425     }
1426 
1427 
1428     /**
1429      * @param readTimeOut the readTimeOut to set
1430      */
1431     public void setReadTimeOut( long readTimeOut )
1432     {
1433         this.readTimeOut = readTimeOut;
1434     }
1435 
1436 
1437     /**
1438      * @return the name
1439      */
1440     public String getName()
1441     {
1442         return btreeHeader.getName();
1443     }
1444 
1445 
1446     /**
1447      * @param name the name to set
1448      */
1449     public void setName( String name )
1450     {
1451         btreeHeader.setName( name );
1452     }
1453 
1454 
1455     /**
1456      * @return the file
1457      */
1458     public File getFile()
1459     {
1460         return file;
1461     }
1462 
1463 
1464     /**
1465      * @return the journal
1466      */
1467     public File getJournal()
1468     {
1469         return journal;
1470     }
1471 
1472 
1473     /**
1474      * @return the writeBufferSize
1475      */
1476     public int getWriteBufferSize()
1477     {
1478         return writeBufferSize;
1479     }
1480 
1481 
1482     /**
1483      * @param writeBufferSize the writeBufferSize to set
1484      */
1485     public void setWriteBufferSize( int writeBufferSize )
1486     {
1487         this.writeBufferSize = writeBufferSize;
1488     }
1489 
1490 
1491     /**
1492      * @return true if the BTree is fully in memory
1493      */
1494     public boolean isInMemory()
1495     {
1496         return type == BTreeTypeEnum.IN_MEMORY;
1497     }
1498 
1499 
1500     /**
1501      * @return true if the BTree is persisted on disk
1502      */
1503     public boolean isPersistent()
1504     {
1505         return type == BTreeTypeEnum.IN_MEMORY;
1506     }
1507 
1508 
1509     /**
1510      * Create a ValueHolder depending on the kind of holder we want.
1511      * 
1512      * @param value The value to store
1513      * @return The value holder
1514      */
1515     /* no qualifier */ValueHolder<V> createValueHolder( V value )
1516     {
1517         return new ValueHolder<V>( this, value );
1518     }
1519 
1520 
1521     /**
1522      * @return the keySerializer
1523      */
1524     public ElementSerializer<K> getKeySerializer()
1525     {
1526         return keySerializer;
1527     }
1528 
1529 
1530     /**
1531      * @return the keySerializer FQCN
1532      */
1533     public String getKeySerializerFQCN()
1534     {
1535         return btreeHeader.getKeySerializerFQCN();
1536     }
1537 
1538 
1539     /**
1540      * @return the valueSerializer
1541      */
1542     public ElementSerializer<V> getValueSerializer()
1543     {
1544         return valueSerializer;
1545     }
1546 
1547 
1548     /**
1549      * @return the valueSerializer FQCN
1550      */
1551     public String getValueSerializerFQCN()
1552     {
1553         return btreeHeader.getValueSerializerFQCN();
1554     }
1555 
1556 
1557     /** 
1558      * @return The current BTree revision
1559      */
1560     public long getRevision()
1561     {
1562         return btreeHeader.getRevision();
1563     }
1564 
1565 
1566     /**
1567      * @param revision the revision to set
1568      */
1569     /* No qualifier */void setRevision( long revision )
1570     {
1571         btreeHeader.setRevision( revision );
1572     }
1573 
1574 
1575     /** 
1576      * @return The current number of elements in the BTree
1577      */
1578     public long getNbElems()
1579     {
1580         return btreeHeader.getNbElems();
1581     }
1582 
1583 
1584     /**
1585      * @param nbElems the nbElems to set
1586      */
1587     /* No qualifier */void setNbElems( long nbElems )
1588     {
1589         btreeHeader.setNbElems( nbElems );
1590     }
1591 
1592 
1593     /**
1594      * @return true if this BTree allow duplicate values
1595      */
1596     public boolean isAllowDuplicates()
1597     {
1598         return btreeHeader.isAllowDuplicates();
1599     }
1600 
1601 
1602     /* No qualifier */void setAllowDuplicates( boolean allowDuplicates )
1603     {
1604         btreeHeader.setAllowDuplicates( allowDuplicates );
1605     }
1606 
1607 
1608     private void writeToJournal( Modification<K, V> modification )
1609         throws IOException
1610     {
1611         if ( modification instanceof Addition )
1612         {
1613             byte[] keyBuffer = keySerializer.serialize( modification.getKey() );
1614             ByteBuffer bb = ByteBuffer.allocateDirect( keyBuffer.length + 1 );
1615             bb.put( Modification.ADDITION );
1616             bb.put( keyBuffer );
1617             bb.flip();
1618 
1619             journalChannel.write( bb );
1620 
1621             byte[] valueBuffer = valueSerializer.serialize( modification.getValue() );
1622             bb = ByteBuffer.allocateDirect( valueBuffer.length );
1623             bb.put( valueBuffer );
1624             bb.flip();
1625 
1626             journalChannel.write( bb );
1627         }
1628         else if ( modification instanceof Deletion )
1629         {
1630             byte[] keyBuffer = keySerializer.serialize( modification.getKey() );
1631             ByteBuffer bb = ByteBuffer.allocateDirect( keyBuffer.length + 1 );
1632             bb.put( Modification.DELETION );
1633             bb.put( keyBuffer );
1634             bb.flip();
1635 
1636             journalChannel.write( bb );
1637         }
1638 
1639         // Flush to the disk for real
1640         journalChannel.force( true );
1641     }
1642 
1643 
1644     /**
1645      * @see Object#toString()
1646      */
1647     public String toString()
1648     {
1649         StringBuilder sb = new StringBuilder();
1650 
1651         switch ( type )
1652         {
1653             case IN_MEMORY:
1654                 sb.append( "In-memory " );
1655                 break;
1656 
1657             case PERSISTENT:
1658                 sb.append( "Persistent " );
1659                 break;
1660 
1661         }
1662 
1663         sb.append( "BTree" );
1664         sb.append( "[" ).append( btreeHeader.getName() ).append( "]" );
1665         sb.append( "( pageSize:" ).append( btreeHeader.getPageSize() );
1666 
1667         if ( rootPage != null )
1668         {
1669             sb.append( ", nbEntries:" ).append( btreeHeader.getNbElems() );
1670         }
1671         else
1672         {
1673             sb.append( ", nbEntries:" ).append( 0 );
1674         }
1675 
1676         sb.append( ", comparator:" );
1677 
1678         if ( keySerializer.getComparator() == null )
1679         {
1680             sb.append( "null" );
1681         }
1682         else
1683         {
1684             sb.append( keySerializer.getComparator().getClass().getSimpleName() );
1685         }
1686 
1687         sb.append( ", DuplicatesAllowed: " ).append( btreeHeader.isAllowDuplicates() );
1688 
1689         if ( type == BTreeTypeEnum.PERSISTENT )
1690         {
1691             try
1692             {
1693                 sb.append( ", file : " );
1694 
1695                 if ( file != null )
1696                 {
1697                     sb.append( file.getCanonicalPath() );
1698                 }
1699                 else
1700                 {
1701                     sb.append( "Unknown" );
1702                 }
1703 
1704                 sb.append( ", journal : " );
1705 
1706                 if ( journal != null )
1707                 {
1708                     sb.append( journal.getCanonicalPath() );
1709                 }
1710                 else
1711                 {
1712                     sb.append( "Unkown" );
1713                 }
1714             }
1715             catch ( IOException ioe )
1716             {
1717                 // There is little we can do here...
1718             }
1719         }
1720 
1721         sb.append( ") : \n" );
1722         sb.append( rootPage.dumpPage( "" ) );
1723 
1724         return sb.toString();
1725     }
1726 }