View Javadoc
1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  You may obtain a copy of the License at
9    *
10   *    http://www.apache.org/licenses/LICENSE-2.0
11   *
12   *  Unless required by applicable law or agreed to in writing,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License.
18   *
19   */
20  package org.apache.directory.mavibot.btree;
21  
22  
23  import java.io.IOException;
24  import java.lang.reflect.Array;
25  import java.util.Comparator;
26  import java.util.Map;
27  import java.util.concurrent.ConcurrentHashMap;
28  import java.util.concurrent.ConcurrentLinkedQueue;
29  import java.util.concurrent.atomic.AtomicBoolean;
30  import java.util.concurrent.atomic.AtomicLong;
31  
32  import org.apache.directory.mavibot.btree.exception.BTreeCreationException;
33  import org.apache.directory.mavibot.btree.exception.DuplicateValueNotAllowedException;
34  import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
35  import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
36  
37  
38  /**
39   * A BTree abstract class containing the methods shared by the PersistedBTree or the InMemoryBTree
40   * implementations.
41   *
42   * @param <K> The Key type
43   * @param <V> The Value type
44   *
45   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
46   */
47  /* No qualifier*/abstract class AbstractBTree<K, V> implements BTree<K, V>
48  {
49      /** The read transaction timeout */
50      protected long readTimeOut = DEFAULT_READ_TIMEOUT;
51  
52      /** The current Header for a managed BTree */
53      protected BTreeHeader<K, V> currentBtreeHeader;
54  
55      /** The Key serializer used for this tree.*/
56      protected ElementSerializer<K> keySerializer;
57  
58      /** The Value serializer used for this tree. */
59      protected ElementSerializer<V> valueSerializer;
60  
61      /** The list of read transactions being executed */
62      protected ConcurrentLinkedQueue<ReadTransaction<K, V>> readTransactions;
63  
64      /** The size of the buffer used to write data in disk */
65      protected int writeBufferSize;
66  
67      /** Flag to enable duplicate key support */
68      protected boolean allowDuplicates;
69  
70      /** The number of elements in a page for this B-tree */
71      protected int pageSize;
72  
73      /** The BTree name */
74      protected String name;
75  
76      /** The FQCN of the Key serializer */
77      protected String keySerializerFQCN;
78  
79      /** The FQCN of the Value serializer */
80      protected String valueSerializerFQCN;
81  
82      /** The thread responsible for the cleanup of timed out reads */
83      protected Thread readTransactionsThread;
84  
85      /** The BTree type : either in-memory, disk backed or persisted */
86      protected BTreeTypeEnum btreeType;
87  
88      /** The current transaction */
89      protected AtomicBoolean transactionStarted = new AtomicBoolean( false );
90  
91      /** The map of all the used BtreeHeaders */
92      protected Map<Long, BTreeHeader<K, V>> btreeRevisions = new ConcurrentHashMap<Long, BTreeHeader<K, V>>();
93  
94      /** The current revision */
95      protected AtomicLong currentRevision = new AtomicLong( 0L );
96  
97      /** The TransactionManager used for this BTree */
98      protected TransactionManager transactionManager;
99  
100 
101     /**
102      * Starts a Read Only transaction. If the transaction is not closed, it will be
103      * automatically closed after the timeout
104      *
105      * @return The created transaction
106      */
107     protected abstract ReadTransaction<K, V> beginReadTransaction();
108 
109 
110     /**
111      * Starts a Read Only transaction. If the transaction is not closed, it will be
112      * automatically closed after the timeout
113      *
114      * @return The created transaction
115      */
116     protected abstract ReadTransaction<K, V> beginReadTransaction( long revision );
117 
118 
119     /**
120      * {@inheritDoc}
121      */
122     public TupleCursor<K, V> browse() throws IOException, KeyNotFoundException
123     {
124         // Check that we have a TransactionManager
125         if ( transactionManager == null )
126         {
127             throw new BTreeCreationException( "We don't have a transactionLManager" );
128         }
129 
130         ReadTransaction<K, V> transaction = beginReadTransaction();
131 
132         if ( transaction == null )
133         {
134             return new EmptyTupleCursor<K, V>();
135         }
136         else
137         {
138             ParentPos<K, V>[] stack = ( ParentPos<K, V>[] ) Array.newInstance( ParentPos.class, 32 );
139 
140             TupleCursor<K, V> cursor = getRootPage().browse( transaction, stack, 0 );
141 
142             // Set the position before the first element
143             cursor.beforeFirst();
144 
145             return cursor;
146         }
147     }
148 
149 
150     /**
151      * {@inheritDoc}
152      */
153     public TupleCursor<K, V> browse( long revision ) throws IOException, KeyNotFoundException
154     {
155         // Check that we have a TransactionManager
156         if ( transactionManager == null )
157         {
158             throw new BTreeCreationException( "We don't have a transactionLManager" );
159         }
160 
161         ReadTransaction<K, V> transaction = beginReadTransaction( revision );
162 
163         if ( transaction == null )
164         {
165             return new EmptyTupleCursor<K, V>();
166         }
167         else
168         {
169             ParentPos<K, V>[] stack = ( ParentPos<K, V>[] ) Array.newInstance( ParentPos.class, 32 );
170 
171             // And get the cursor
172             TupleCursor<K, V> cursor = getRootPage( transaction.getRevision() ).browse( transaction, stack, 0 );
173 
174             return cursor;
175         }
176     }
177 
178 
179     /**
180      * {@inheritDoc}
181      */
182     public TupleCursor<K, V> browseFrom( K key ) throws IOException
183     {
184         // Check that we have a TransactionManager
185         if ( transactionManager == null )
186         {
187             throw new BTreeCreationException( "We don't have a transactionLManager" );
188         }
189 
190         ReadTransaction<K, V> transaction = beginReadTransaction();
191 
192         ParentPos<K, V>[] stack = ( ParentPos<K, V>[] ) Array.newInstance( ParentPos.class, 32 );
193 
194         try
195         {
196             TupleCursor<K, V> cursor = getRootPage( transaction.getRevision() ).browse( key, transaction, stack, 0 );
197 
198             return cursor;
199         }
200         catch ( KeyNotFoundException e )
201         {
202             throw new IOException( e.getMessage() );
203         }
204     }
205 
206 
207     /**
208      * {@inheritDoc}
209      */
210     public TupleCursor<K, V> browseFrom( long revision, K key ) throws IOException, KeyNotFoundException
211     {
212         // Check that we have a TransactionManager
213         if ( transactionManager == null )
214         {
215             throw new BTreeCreationException( "We don't have a transactionLManager" );
216         }
217 
218         ReadTransaction<K, V> transaction = beginReadTransaction( revision );
219 
220         if ( transaction == null )
221         {
222             return new EmptyTupleCursor<K, V>();
223         }
224         else
225         {
226             ParentPos<K, V>[] stack = ( ParentPos<K, V>[] ) Array.newInstance( ParentPos.class, 32 );
227 
228             // And get the cursor
229             TupleCursor<K, V> cursor = getRootPage( transaction.getRevision() ).browse( key, transaction, stack, 0 );
230 
231             return cursor;
232         }
233     }
234 
235 
236     /**
237      * {@inheritDoc}
238      */
239     public boolean contains( K key, V value ) throws IOException
240     {
241         // Check that we have a TransactionManager
242         if ( transactionManager == null )
243         {
244             throw new BTreeCreationException( "We don't have a transactionLManager" );
245         }
246 
247         ReadTransaction<K, V> transaction = beginReadTransaction();
248 
249         if ( transaction == null )
250         {
251             return false;
252         }
253         else
254         {
255             try
256             {
257                 return getRootPage( transaction.getRevision() ).contains( key, value );
258             }
259             catch ( KeyNotFoundException knfe )
260             {
261                 throw new IOException( knfe.getMessage() );
262             }
263             finally
264             {
265                 transaction.close();
266             }
267         }
268     }
269 
270 
271     /**
272      * {@inheritDoc}
273      */
274     public boolean contains( long revision, K key, V value ) throws IOException, KeyNotFoundException
275     {
276         // Check that we have a TransactionManager
277         if ( transactionManager == null )
278         {
279             throw new BTreeCreationException( "We don't have a transactionLManager" );
280         }
281 
282         // Fetch the root page for this revision
283         ReadTransaction<K, V> transaction = beginReadTransaction( revision );
284 
285         if ( transaction == null )
286         {
287             return false;
288         }
289         else
290         {
291             try
292             {
293                 return getRootPage( transaction.getRevision() ).contains( key, value );
294             }
295             finally
296             {
297                 transaction.close();
298             }
299         }
300     }
301 
302 
303     /**
304      * {@inheritDoc}
305      */
306     public Tuple<K, V> delete( K key ) throws IOException
307     {
308         // Check that we have a TransactionManager
309         if ( transactionManager == null )
310         {
311             throw new BTreeCreationException( "We don't have a transactionLManager" );
312         }
313 
314         if ( key == null )
315         {
316             throw new IllegalArgumentException( "Key must not be null" );
317         }
318 
319         // Take the lock if it's not already taken by another thread
320         transactionManager.beginTransaction();
321 
322         try
323         {
324             Tuple<K, V> deleted = delete( key, currentRevision.get() + 1 );
325 
326             // Commit now
327             transactionManager.commit();
328 
329             return deleted;
330         }
331         catch ( IOException ioe )
332         {
333             // We have had an exception, we must rollback the transaction
334             transactionManager.rollback();
335 
336             return null;
337         }
338     }
339 
340 
341     /**
342      * {@inheritDoc}
343      */
344     public Tuple<K, V> delete( K key, V value ) throws IOException
345     {
346         // Check that we have a TransactionManager
347         if ( transactionManager == null )
348         {
349             throw new BTreeCreationException( "We don't have a transactionLManager" );
350         }
351 
352         if ( key == null )
353         {
354             throw new IllegalArgumentException( "Key must not be null" );
355         }
356 
357         if ( value == null )
358         {
359             throw new IllegalArgumentException( "Value must not be null" );
360         }
361 
362         transactionManager.beginTransaction();
363 
364         try
365         {
366             Tuple<K, V> deleted = delete( key, value, currentRevision.get() + 1 );
367 
368             transactionManager.commit();
369 
370             return deleted;
371         }
372         catch ( IOException ioe )
373         {
374             transactionManager.rollback();
375 
376             throw ioe;
377         }
378     }
379 
380 
381     /**
382      * Delete the entry which key is given as a parameter. If the entry exists, it will
383      * be removed from the tree, the old tuple will be returned. Otherwise, null is returned.
384      *
385      * @param key The key for the entry we try to remove
386      * @return A Tuple<K, V> containing the removed entry, or null if it's not found.
387      */
388     /*no qualifier*/Tuple<K, V> delete( K key, long revision ) throws IOException
389     {
390         return delete( key, null, revision );
391     }
392 
393 
394     /*no qualifier*/abstract Tuple<K, V> delete( K key, V value, long revision ) throws IOException;
395 
396 
397     /**
398      * {@inheritDoc}
399      */
400     public V insert( K key, V value ) throws IOException
401     {
402         // Check that we have a TransactionManager
403         if ( transactionManager == null )
404         {
405             throw new BTreeCreationException( "We don't have a transactionLManager" );
406         }
407 
408         V existingValue = null;
409 
410         if ( key == null )
411         {
412             throw new IllegalArgumentException( "Key must not be null" );
413         }
414 
415         // Take the lock if it's not already taken by another thread and if we 
416         // aren't on a sub-btree
417         if ( btreeType != BTreeTypeEnum.PERSISTED_SUB )
418         {
419             transactionManager.beginTransaction();
420         }
421 
422         try
423         {
424             InsertResult<K, V> result = insert( key, value, -1L );
425 
426             if ( result instanceof ExistsResult )
427             {
428                 existingValue = value;
429             }
430             else if ( result instanceof ModifyResult )
431             {
432                 existingValue = ( ( ModifyResult<K, V> ) result ).getModifiedValue();
433             }
434 
435             // Commit now if it's not a sub-btree
436             if ( btreeType != BTreeTypeEnum.PERSISTED_SUB )
437             {
438                 //FIXME when result type is ExistsResult then we should avoid writing the headers
439                 transactionManager.commit();
440             }
441 
442             return existingValue;
443         }
444         catch ( IOException ioe )
445         {
446             // We have had an exception, we must rollback the transaction
447             // if it's not a sub-btree
448             if ( btreeType != BTreeTypeEnum.PERSISTED_SUB )
449             {
450                 transactionManager.rollback();
451             }
452 
453             return null;
454         }
455         catch ( DuplicateValueNotAllowedException e )
456         {
457             // We have had an exception, we must rollback the transaction
458             // if it's not a sub-btree
459             if ( btreeType != BTreeTypeEnum.PERSISTED_SUB )
460             {
461                 transactionManager.rollback();
462             }
463 
464             throw e;
465         }
466     }
467 
468 
469     /**
470      * {@inheritDoc}
471      */
472     /* no qualifier */abstract InsertResult<K, V> insert( K key, V value, long revision ) throws IOException;
473 
474 
475     /**
476      * Flush the latest revision to disk. We will replace the current file by the new one, as
477      * we flush in a temporary file.
478      */
479     public void flush() throws IOException
480     {
481     }
482 
483 
484     /**
485      * {@inheritDoc}
486      */
487     public V get( K key ) throws IOException, KeyNotFoundException
488     {
489         // Check that we have a TransactionManager
490         if ( transactionManager == null )
491         {
492             throw new BTreeCreationException( "We don't have a transactionLManager" );
493         }
494 
495         ReadTransaction<K, V> transaction = beginReadTransaction();
496 
497         if ( transaction == null )
498         {
499             return null;
500         }
501         else
502         {
503             try
504             {
505                 return getRootPage( transaction.getRevision() ).get( key );
506             }
507             finally
508             {
509                 transaction.close();
510             }
511         }
512     }
513 
514 
515     /**
516      * {@inheritDoc}
517      */
518     public V get( long revision, K key ) throws IOException, KeyNotFoundException
519     {
520         // Check that we have a TransactionManager
521         if ( transactionManager == null )
522         {
523             throw new BTreeCreationException( "We don't have a transactionLManager" );
524         }
525 
526         ReadTransaction<K, V> transaction = beginReadTransaction( revision );
527 
528         if ( transaction == null )
529         {
530             return null;
531         }
532         else
533         {
534             try
535             {
536                 return getRootPage( transaction.getRevision() ).get( key );
537             }
538             finally
539             {
540                 transaction.close();
541             }
542         }
543     }
544 
545 
546     /**
547      * {@inheritDoc}
548      */
549     public abstract Page<K, V> getRootPage();
550 
551 
552     /**
553      * {@inheritDoc}
554      */
555     /* no qualifier */abstract void setRootPage( Page<K, V> root );
556 
557 
558     /**
559      * {@inheritDoc}
560      */
561     public ValueCursor<V> getValues( K key ) throws IOException, KeyNotFoundException
562     {
563         // Check that we have a TransactionManager
564         if ( transactionManager == null )
565         {
566             throw new BTreeCreationException( "We don't have a transactionLManager" );
567         }
568 
569         ReadTransaction<K, V> transaction = beginReadTransaction();
570 
571         if ( transaction == null )
572         {
573             return new EmptyValueCursor<V>( 0L );
574         }
575         else
576         {
577             try
578             {
579                 return getRootPage( transaction.getRevision() ).getValues( key );
580             }
581             finally
582             {
583                 transaction.close();
584             }
585         }
586     }
587 
588 
589     /**
590      * {@inheritDoc}
591      */
592     public boolean hasKey( K key ) throws IOException, KeyNotFoundException
593     {
594         // Check that we have a TransactionManager
595         if ( transactionManager == null )
596         {
597             throw new BTreeCreationException( "We don't have a transactionLManager" );
598         }
599 
600         if ( key == null )
601         {
602             return false;
603         }
604 
605         ReadTransaction<K, V> transaction = beginReadTransaction();
606 
607         if ( transaction == null )
608         {
609             return false;
610         }
611         else
612         {
613             try
614             {
615                 return getRootPage( transaction.getRevision() ).hasKey( key );
616             }
617             finally
618             {
619                 transaction.close();
620             }
621         }
622     }
623 
624 
625     /**
626      * {@inheritDoc}
627      */
628     public boolean hasKey( long revision, K key ) throws IOException, KeyNotFoundException
629     {
630         // Check that we have a TransactionManager
631         if ( transactionManager == null )
632         {
633             throw new BTreeCreationException( "We don't have a transactionLManager" );
634         }
635 
636         if ( key == null )
637         {
638             return false;
639         }
640 
641         ReadTransaction<K, V> transaction = beginReadTransaction( revision );
642 
643         if ( transaction == null )
644         {
645             return false;
646         }
647         else
648         {
649             try
650             {
651                 return getRootPage( transaction.getRevision() ).hasKey( key );
652             }
653             finally
654             {
655                 transaction.close();
656             }
657         }
658     }
659 
660 
661     /**
662      * {@inheritDoc}
663      */
664     public ElementSerializer<K> getKeySerializer()
665     {
666         return keySerializer;
667     }
668 
669 
670     /**
671      * {@inheritDoc}
672      */
673     public void setKeySerializer( ElementSerializer<K> keySerializer )
674     {
675         this.keySerializer = keySerializer;
676         keySerializerFQCN = keySerializer.getClass().getName();
677     }
678 
679 
680     /**
681      * {@inheritDoc}
682      */
683     public String getKeySerializerFQCN()
684     {
685         return keySerializerFQCN;
686     }
687 
688 
689     /**
690      * {@inheritDoc}
691      */
692     public ElementSerializer<V> getValueSerializer()
693     {
694         return valueSerializer;
695     }
696 
697 
698     /**
699      * {@inheritDoc}
700      */
701     public void setValueSerializer( ElementSerializer<V> valueSerializer )
702     {
703         this.valueSerializer = valueSerializer;
704         valueSerializerFQCN = valueSerializer.getClass().getName();
705     }
706 
707 
708     /**
709      * {@inheritDoc}
710      */
711     public String getValueSerializerFQCN()
712     {
713         return valueSerializerFQCN;
714     }
715 
716 
717     /**
718      * {@inheritDoc}
719      */
720     public long getRevision()
721     {
722         // Check that we have a TransactionManager
723         if ( transactionManager == null )
724         {
725             throw new BTreeCreationException( "We don't have a transactionLManager" );
726         }
727 
728         ReadTransaction<K, V> transaction = beginReadTransaction();
729 
730         if ( transaction == null )
731         {
732             return -1L;
733         }
734         else
735         {
736             try
737             {
738                 return transaction.getRevision();
739             }
740             finally
741             {
742                 transaction.close();
743             }
744         }
745     }
746 
747 
748     /**
749      * {@inheritDoc}
750      */
751     /* no qualifier */void setRevision( long revision )
752     {
753         transactionManager.getBTreeHeader( getName() ).setRevision( revision );
754     }
755 
756 
757     /**
758      * Store the new revision in the map of btrees, increment the current revision
759      */
760     protected void storeRevision( BTreeHeader<K, V> btreeHeader, boolean keepRevisions )
761     {
762         long revision = btreeHeader.getRevision();
763 
764         if ( keepRevisions )
765         {
766             synchronized ( btreeRevisions )
767             {
768                 btreeRevisions.put( revision, btreeHeader );
769             }
770         }
771 
772         currentRevision.set( revision );
773         currentBtreeHeader = btreeHeader;
774 
775         // And update the newBTreeHeaders map
776         if ( btreeHeader.getBtree().getType() != BTreeTypeEnum.PERSISTED_SUB )
777         {
778             transactionManager.updateNewBTreeHeaders( btreeHeader );
779         }
780     }
781 
782 
783     /**
784      * Store the new revision in the map of btrees, increment the current revision
785      */
786     protected void storeRevision( BTreeHeader<K, V> btreeHeader )
787     {
788         long revision = btreeHeader.getRevision();
789 
790         synchronized ( btreeRevisions )
791         {
792             btreeRevisions.put( revision, btreeHeader );
793         }
794 
795         currentRevision.set( revision );
796         currentBtreeHeader = btreeHeader;
797 
798         // And update the newBTreeHeaders map
799         if ( btreeHeader.getBtree().getType() != BTreeTypeEnum.PERSISTED_SUB )
800         {
801             transactionManager.updateNewBTreeHeaders( btreeHeader );
802         }
803     }
804 
805 
806     /**
807      * {@inheritDoc}
808      */
809     public long getReadTimeOut()
810     {
811         return readTimeOut;
812     }
813 
814 
815     /**
816      * {@inheritDoc}
817      */
818     public void setReadTimeOut( long readTimeOut )
819     {
820         this.readTimeOut = readTimeOut;
821     }
822 
823 
824     /**
825      * {@inheritDoc}
826      */
827     public long getNbElems()
828     {
829         // Check that we have a TransactionManager
830         if ( transactionManager == null )
831         {
832             throw new BTreeCreationException( "We don't have a transactionLManager" );
833         }
834 
835         ReadTransaction<K, V> transaction = beginReadTransaction();
836 
837         if ( transaction == null )
838         {
839             return -1L;
840         }
841         else
842         {
843             try
844             {
845                 return transaction.getBtreeHeader().getNbElems();
846             }
847             finally
848             {
849                 transaction.close();
850             }
851         }
852     }
853 
854 
855     /**
856      * {@inheritDoc}
857      */
858     /* no qualifier */void setNbElems( long nbElems )
859     {
860         transactionManager.getBTreeHeader( getName() ).setNbElems( nbElems );
861     }
862 
863 
864     /**
865      * {@inheritDoc}
866      */
867     public int getPageSize()
868     {
869         return pageSize;
870     }
871 
872 
873     /**
874      * {@inheritDoc}
875      */
876     public void setPageSize( int pageSize )
877     {
878         if ( pageSize <= 2 )
879         {
880             this.pageSize = DEFAULT_PAGE_SIZE;
881         }
882         else
883         {
884             this.pageSize = getPowerOf2( pageSize );
885         }
886     }
887 
888 
889     /**
890      * {@inheritDoc}
891      */
892     public String getName()
893     {
894         return name;
895     }
896 
897 
898     /**
899      * {@inheritDoc}
900      */
901     public void setName( String name )
902     {
903         this.name = name;
904     }
905 
906 
907     /**
908      * {@inheritDoc}
909      */
910     public Comparator<K> getKeyComparator()
911     {
912         return keySerializer.getComparator();
913     }
914 
915 
916     /**
917      * {@inheritDoc}
918      */
919     public Comparator<V> getValueComparator()
920     {
921         return valueSerializer.getComparator();
922     }
923 
924 
925     /**
926      * {@inheritDoc}
927      */
928     public int getWriteBufferSize()
929     {
930         return writeBufferSize;
931     }
932 
933 
934     /**
935      * {@inheritDoc}
936      */
937     public void setWriteBufferSize( int writeBufferSize )
938     {
939         this.writeBufferSize = writeBufferSize;
940     }
941 
942 
943     /**
944      * {@inheritDoc}
945      */
946     public boolean isAllowDuplicates()
947     {
948         return allowDuplicates;
949     }
950 
951 
952     /**
953      * {@inheritDoc}
954      */
955     public void setAllowDuplicates( boolean allowDuplicates )
956     {
957         this.allowDuplicates = allowDuplicates;
958     }
959 
960 
961     /**
962      * {@inheritDoc}
963      */
964     public BTreeTypeEnum getType()
965     {
966         return btreeType;
967     }
968 
969 
970     /**
971      * @param type the type to set
972      */
973     public void setType( BTreeTypeEnum type )
974     {
975         this.btreeType = type;
976     }
977 
978 
979     /**
980      * Gets the number which is a power of 2 immediately above the given positive number.
981      */
982     private int getPowerOf2( int size )
983     {
984         int newSize = --size;
985         newSize |= newSize >> 1;
986         newSize |= newSize >> 2;
987         newSize |= newSize >> 4;
988         newSize |= newSize >> 8;
989         newSize |= newSize >> 16;
990         newSize++;
991 
992         return newSize;
993     }
994 
995 
996     /**
997      * @return The current BtreeHeader
998      */
999     protected BTreeHeader<K, V> getBtreeHeader()
1000     {
1001         return currentBtreeHeader;
1002     }
1003 
1004 
1005     /**
1006      * @return The current BtreeHeader
1007      */
1008     protected BTreeHeader<K, V> getBtreeHeader( long revision )
1009     {
1010         return btreeRevisions.get( revision );
1011     }
1012 
1013 
1014     /**
1015      * {@inheritDoc}
1016      */
1017     public KeyCursor<K> browseKeys() throws IOException, KeyNotFoundException
1018     {
1019         // Check that we have a TransactionManager
1020         if ( transactionManager == null )
1021         {
1022             throw new BTreeCreationException( "We don't have a Transaction Manager" );
1023         }
1024 
1025         ReadTransaction transaction = beginReadTransaction();
1026 
1027         if ( transaction == null )
1028         {
1029             return new KeyCursor<K>();
1030         }
1031         else
1032         {
1033             ParentPos<K, K>[] stack = ( ParentPos<K, K>[] ) Array.newInstance( ParentPos.class, 32 );
1034 
1035             KeyCursor<K> cursor = getRootPage().browseKeys( transaction, stack, 0 );
1036 
1037             // Set the position before the first element
1038             cursor.beforeFirst();
1039 
1040             return cursor;
1041         }
1042     }
1043 
1044 
1045     /**
1046      * Create a thread that is responsible of cleaning the transactions when
1047      * they hit the timeout
1048      */
1049     /*no qualifier*/void createTransactionManager()
1050     {
1051         Runnable readTransactionTask = new Runnable()
1052         {
1053             public void run()
1054             {
1055                 try
1056                 {
1057                     ReadTransaction<K, V> transaction = null;
1058 
1059                     while ( !Thread.currentThread().isInterrupted() )
1060                     {
1061                         long timeoutDate = System.currentTimeMillis() - readTimeOut;
1062                         long t0 = System.currentTimeMillis();
1063                         int nbTxns = 0;
1064 
1065                         // Loop on all the transactions from the queue
1066                         while ( ( transaction = readTransactions.peek() ) != null )
1067                         {
1068                             nbTxns++;
1069 
1070                             if ( transaction.isClosed() )
1071                             {
1072                                 // The transaction is already closed, remove it from the queue
1073                                 readTransactions.poll();
1074                                 continue;
1075                             }
1076 
1077                             // Check if the transaction has timed out
1078                             if ( transaction.getCreationDate() < timeoutDate )
1079                             {
1080                                 transaction.close();
1081                                 readTransactions.poll();
1082 
1083                                 synchronized ( btreeRevisions )
1084                                 {
1085                                     btreeRevisions.remove( transaction.getRevision() );
1086                                 }
1087 
1088                                 continue;
1089                             }
1090 
1091                             // We need to stop now
1092                             break;
1093                         }
1094 
1095                         long t1 = System.currentTimeMillis();
1096 
1097                         // Wait until we reach the timeout
1098                         Thread.sleep( readTimeOut );
1099                     }
1100                 }
1101                 catch ( InterruptedException ie )
1102                 {
1103                     //System.out.println( "Interrupted" );
1104                 }
1105                 catch ( Exception e )
1106                 {
1107                     throw new RuntimeException( e );
1108                 }
1109             }
1110         };
1111 
1112         readTransactionsThread = new Thread( readTransactionTask );
1113         readTransactionsThread.setDaemon( true );
1114         readTransactionsThread.start();
1115     }
1116 }