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.server.core.partition.impl.btree.jdbm;
21  
22  
23  import jdbm.RecordManager;
24  import jdbm.btree.BTree;
25  import jdbm.helper.*;
26  
27  import org.apache.directory.server.core.avltree.*;
28  import org.apache.directory.server.core.cursor.Cursor;
29  import org.apache.directory.server.core.cursor.EmptyCursor;
30  import org.apache.directory.server.core.cursor.SingletonCursor;
31  import org.apache.directory.server.schema.SerializableComparator;
32  import org.apache.directory.server.xdbm.*;
33  import org.apache.directory.shared.ldap.util.SynchronizedLRUMap;
34  
35  import java.io.IOException;
36  import java.util.*;
37  
38  
39  /**
40   * A jdbm Btree wrapper that enables duplicate sorted keys using collections.
41   *
42   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
43   * @version $Rev: 689396 $
44   */
45  public class JdbmTable<K,V> implements Table<K,V>
46  {
47      private static final byte[] EMPTY_BYTES = new byte[0];
48  
49      /** the key to store and retreive the count information */
50      private static final String SZSUFFIX = "_btree_sz";
51  
52      /** the name of this table */
53      private final String name;
54      /** the JDBM record manager for the file this table is managed in */
55      private final RecordManager recMan;
56      /** whether or not this table allows for duplicates */
57      private final boolean allowsDuplicates;
58      /** a key comparator for the keys in this Table */
59      private final Comparator<K> keyComparator;
60      /** a value comparator for the values in this Table */
61      private final Comparator<V> valueComparator;
62  
63      /** the current count of entries in this Table */
64      private int count;
65      /** the wrappedCursor JDBM btree used in this Table */
66      private BTree bt;
67  
68  
69      /** the limit at which we start using btree redirection for duplicates */
70      private int numDupLimit = JdbmIndex.DEFAULT_DUPLICATE_LIMIT;
71      /** a cache of duplicate BTrees */
72      private final Map<Long, BTree> duplicateBtrees;
73  
74      private final Serializer keySerializer;
75  
76      private final Serializer valueSerializer;
77  
78      AvlTreeMarshaller<V> marshaller;
79  
80  
81      // ------------------------------------------------------------------------
82      // C O N S T R U C T O R
83      // ------------------------------------------------------------------------
84  
85      
86      /**
87       * Creates a Jdbm BTree based tuple Table abstraction that enables 
88       * duplicates.
89       *
90       * @param name the name of the table
91       * @param numDupLimit the size limit of duplicates before switching to
92       * BTrees for values instead of AvlTrees
93       * @param manager the record manager to be used for this table
94       * @param keyComparator a key comparator
95       * @param valueComparator a value comparator
96       * @param keySerializer a serializer to use for the keys instead of using
97       * default Java serialization which could be very expensive
98       * @param valueSerializer a serializer to use for the values instead of
99       * using default Java serialization which could be very expensive
100      * @throws IOException if the table's file cannot be created
101      */
102     @SuppressWarnings("unchecked")
103     public JdbmTable( String name, int numDupLimit, RecordManager manager,
104         Comparator<K> keyComparator, Comparator<V> valueComparator,
105         Serializer keySerializer, Serializer valueSerializer )
106         throws IOException
107     {
108         // TODO make the size of the duplicate btree cache configurable via constructor
109         duplicateBtrees = new SynchronizedLRUMap( 100 );
110 
111         if ( valueSerializer != null )
112         {
113             marshaller = new AvlTreeMarshaller<V>( valueComparator,
114                     new MarshallerSerializerBridge<V>( valueSerializer ) );
115         }
116         else
117         {
118             marshaller = new AvlTreeMarshaller<V>( valueComparator );
119         }
120 
121         if ( keyComparator == null )
122         {
123             throw new NullPointerException( "Key comparator cannot be null." );
124         }
125         else
126         {
127             this.keyComparator = keyComparator;
128         }
129 
130         if ( valueComparator == null )
131         {
132             throw new NullPointerException( "Value comparator must not be null for tables with duplicate keys." );
133         }
134         else
135         {
136             this.valueComparator = valueComparator;
137         }
138 
139         this.numDupLimit = numDupLimit;
140         this.name = name;
141         this.recMan = manager;
142 
143         this.keySerializer = keySerializer;
144         this.valueSerializer = valueSerializer;
145 
146         this.allowsDuplicates = true;
147 
148         long recId = recMan.getNamedObject( name );
149 
150         if ( recId == 0 ) // Create new main BTree
151         {
152             // we do not use the value serializer in the btree since duplicates will use
153             // either BTreeRedirect objects or AvlTree objects whose marshalling is
154             // explicitly managed by this code.  Value serialization is delegated to these
155             // marshallers.
156 
157             bt = BTree.createInstance( recMan, keyComparator, keySerializer, null );
158             recId = bt.getRecid();
159             recMan.setNamedObject( name, recId );
160             recId = recMan.insert( 0 );
161             recMan.setNamedObject( name + SZSUFFIX, recId );
162         }
163         else // Load existing BTree
164         {
165             bt = BTree.load( recMan, recId );
166             recId = recMan.getNamedObject( name + SZSUFFIX );
167             count = ( Integer ) recMan.fetch( recId );
168         }
169 
170     }
171 
172 
173     /**
174      * Creates a Jdbm BTree based tuple Table abstraction without duplicates 
175      * enabled using a simple key comparator.
176      *
177      * @param name the name of the table
178      * @param manager the record manager to be used for this table
179      * @param keyComparator a tuple comparator
180      * @param keySerializer a serializer to use for the keys instead of using
181      * default Java serialization which could be very expensive
182      * @param valueSerializer a serializer to use for the values instead of
183      * using default Java serialization which could be very expensive
184      * @throws IOException if the table's file cannot be created
185      */
186     public JdbmTable( String name, RecordManager manager, SerializableComparator<K> keyComparator,
187                       Serializer keySerializer, Serializer valueSerializer )
188         throws IOException
189     {
190         this.duplicateBtrees = null;
191         this.numDupLimit = Integer.MAX_VALUE;
192         this.name = name;
193         this.recMan = manager;
194 
195         this.keyComparator = keyComparator;
196         this.valueComparator = null;
197 
198         this.keySerializer = keySerializer;
199         this.valueSerializer = valueSerializer;
200 
201         this.allowsDuplicates = false;
202 
203         long recId = recMan.getNamedObject( name );
204 
205         if ( recId != 0 )
206         {
207             bt = BTree.load( recMan, recId );
208             bt.setValueSerializer( valueSerializer );
209             recId = recMan.getNamedObject( name + SZSUFFIX );
210             count = ( Integer ) recMan.fetch( recId );
211         }
212         else
213         {
214             bt = BTree.createInstance( recMan, keyComparator, keySerializer, valueSerializer );
215             recId = bt.getRecid();
216             recMan.setNamedObject( name, recId );
217             recId = recMan.insert( 0 );
218             recMan.setNamedObject( name + SZSUFFIX, recId );
219         }
220     }
221 
222 
223     // ------------------------------------------------------------------------
224     // Simple Table Properties
225     // ------------------------------------------------------------------------
226 
227     
228     /**
229      * @see Table#getKeyComparator()
230      */
231     public Comparator<K> getKeyComparator()
232     {
233         return keyComparator;
234     }
235 
236 
237     /**
238      * @see Table#getValueComparator()
239      */
240     public Comparator<V> getValueComparator()
241     {
242         return valueComparator;
243     }
244 
245 
246     public Serializer getKeySerializer()
247     {
248         return keySerializer;
249     }
250 
251 
252     public Serializer getValueSerializer()
253     {
254         return valueSerializer;
255     }
256 
257 
258     /**
259      * @see org.apache.directory.server.xdbm.Table#isDupsEnabled()
260      */
261     public boolean isDupsEnabled()
262     {
263         return allowsDuplicates;
264     }
265 
266 
267     /**
268      * @see org.apache.directory.server.xdbm.Table#getName()
269      */
270     public String getName()
271     {
272         return name;
273     }
274 
275 
276     public boolean isCountExact()
277     {
278         return false;
279     }
280         
281 
282     // ------------------------------------------------------------------------
283     // Count Overloads
284     // ------------------------------------------------------------------------
285 
286     
287     /**
288      * @see Table#greaterThanCount(Object)
289      */
290     public int greaterThanCount( K key ) throws IOException
291     {
292         // take a best guess
293         return count;
294     }
295     
296     
297     /**
298      * @see Table#lessThanCount(Object)
299      */
300     public int lessThanCount( K key ) throws IOException
301     {
302         // take a best guess
303         return count;
304     }
305 
306 
307     /**
308      * @see org.apache.directory.server.xdbm.Table#count(java.lang.Object)
309      */
310     public int count( K key ) throws IOException
311     {
312         if ( key == null )
313         {
314             return 0;
315         }
316 
317         if ( ! allowsDuplicates )
318         {
319             if ( null == bt.find( key ) )
320             {
321                 return 0;
322             }
323             else
324             {
325                 return 1;
326             }
327         }
328 
329         DupsContainer<V> values = getDupsContainer( ( byte[] ) bt.find( key ) );
330         if ( values.isAvlTree() )
331         {
332             return values.getAvlTree().getSize();
333         }
334 
335         return getBTree( values.getBTreeRedirect() ).size();
336     }
337 
338 
339     /**
340      * @see org.apache.directory.server.xdbm.Table#count()
341      */
342     public int count() throws IOException
343     {
344         return count;
345     }
346 
347     
348     // ------------------------------------------------------------------------
349     // get/has/put/remove Methods and Overloads
350     // ------------------------------------------------------------------------
351 
352 
353     @SuppressWarnings("unchecked")
354     public V get( K key ) throws Exception
355     {
356         if ( key == null )
357         {
358             return null;
359         }
360 
361         if ( ! allowsDuplicates )
362         {
363             return ( V ) bt.find( key );
364         }                         
365 
366         DupsContainer<V> values = getDupsContainer( ( byte[] ) bt.find( key ) );
367         if ( values.isAvlTree() )
368         {
369             AvlTree<V> set = values.getAvlTree();
370 
371             if ( set.getFirst() == null )
372             {
373                 return null;
374             }
375             
376             return set.getFirst().getKey();
377         }
378 
379         // Handle values if they are stored in another BTree
380         BTree tree = getBTree( values.getBTreeRedirect() );
381         jdbm.helper.Tuple tuple = new jdbm.helper.Tuple();
382         tree.browse().getNext( tuple );
383         //noinspection unchecked
384         return ( V ) tuple.getKey();
385     }
386 
387     
388     /**
389      * @see Table#hasGreaterOrEqual(Object,Object)
390      */
391     @SuppressWarnings("unchecked")
392     public boolean hasGreaterOrEqual( K key, V val ) throws IOException
393     {
394         if ( key == null )
395         {
396             return false;
397         }
398 
399         if ( ! allowsDuplicates )
400         {
401             throw new UnsupportedOperationException( "Unfortunately this Table without duplicates enabled " +
402                     "does not contain a value comparator which is needed to answer your ordering question." );
403         }
404 
405         DupsContainer<V> values = getDupsContainer( ( byte[] ) bt.find( key ) );
406         if ( values.isAvlTree() )
407         {
408             AvlTree<V> set = values.getAvlTree();
409             LinkedAvlNode<V> result = set.findGreaterOrEqual( val );
410             return result != null;
411         }
412 
413         // last option is to try a btree with BTreeRedirects
414         BTree tree = getBTree( values.getBTreeRedirect() );
415         return tree.size() != 0 && btreeHas( tree, val, true );
416     }
417 
418 
419     /**
420      * @see Table#hasLessOrEqual(Object,Object)
421      */
422     @SuppressWarnings("unchecked")
423     public boolean hasLessOrEqual( K key, V val ) throws IOException
424     {
425         if ( key == null )
426         {
427             return false;
428         }
429 
430         if ( ! allowsDuplicates )
431         {
432             throw new UnsupportedOperationException( "Unfortunately this Table without duplicates enabled " +
433                     "does not contain a value comparator which is needed to answer your ordering question." );
434         }
435 
436         DupsContainer<V> values = getDupsContainer( ( byte[] ) bt.find( key ) );
437         if ( values.isAvlTree() )
438         {
439             AvlTree<V> set = values.getAvlTree();
440             LinkedAvlNode<V> result = set.findLessOrEqual( val );
441             return result != null;
442         }
443 
444         // last option is to try a btree with BTreeRedirects
445         BTree tree = getBTree( values.getBTreeRedirect() );
446         return tree.size() != 0 && btreeHas( tree, val, false );
447     }
448 
449 
450     /**
451      * @see org.apache.directory.server.xdbm.Table#hasGreaterOrEqual(Object)
452      */
453     @SuppressWarnings("unchecked")
454     public boolean hasGreaterOrEqual( K key ) throws IOException
455     {
456         // See if we can find the border between keys greater than and less
457         // than in the set of keys.  This will be the spot we search from.
458         jdbm.helper.Tuple tuple = bt.findGreaterOrEqual( key );
459 
460         // Test for equality first since it satisfies both greater/less than
461         if ( null != tuple && keyComparator.compare( ( K ) tuple.getKey(), key ) == 0 )
462         {
463             return true;
464         }
465 
466         // Greater searches are easy and quick thanks to findGreaterOrEqual
467         // A null return above means there were no equal or greater keys
468         if ( null == tuple )
469         {
470             return false;
471         }
472 
473         // Not Null! - we found a tuple with equal or greater key value
474         return true;
475     }
476 
477 
478     /**
479      * @see Table#hasLessOrEqual(Object)
480      */
481     @SuppressWarnings("unchecked")
482     public boolean hasLessOrEqual( K key ) throws IOException
483     {
484         // Can only find greater than or equal to with JDBM so we find that
485         // and work backwards to see if we can find one less than the key
486         jdbm.helper.Tuple tuple = bt.findGreaterOrEqual( key );
487 
488         // Test for equality first since it satisfies equal to condition
489         if ( null != tuple && keyComparator.compare( ( K ) tuple.getKey(), key ) == 0 )
490         {
491             return true;
492         }
493 
494         if ( null == tuple )
495         {
496             /*
497              * Jdbm failed to find a key greater than or equal to the argument
498              * which means all the keys in the table are less than the
499              * supplied key argument.  We can hence return true if the table
500              * contains any Tuples.
501              */
502             return count > 0;
503         }
504         else
505         {
506             /*
507              * We have the next tuple whose key is the next greater than the
508              * key argument supplied.  We use this key to advance a browser to
509              * that tuple and scan down to lesser Tuples until we hit one
510              * that is less than the key argument supplied.  Usually this will
511              * be the previous tuple if it exists.
512              */
513             TupleBrowser browser = bt.browse( tuple.getKey() );
514             if ( browser.getPrevious( tuple ) )
515             {
516                 return true;
517             }
518         }
519 
520         return false;
521     }
522 
523 
524     /**
525      * @see org.apache.directory.server.xdbm.Table#has(java.lang.Object,
526      * java.lang.Object)
527      */
528     @SuppressWarnings("unchecked")
529     public boolean has( K key, V value ) throws IOException
530     {
531         if ( key == null )
532         {
533             return false;
534         }
535 
536         if ( ! allowsDuplicates )
537         {
538             V stored = ( V ) bt.find( key );
539             return null != stored && stored.equals( value );
540         }
541         
542         DupsContainer<V> values = getDupsContainer( ( byte[] ) bt.find( key ) );
543         if ( values.isAvlTree() )
544         {
545             return values.getAvlTree().find( value ) != null;
546         }
547         
548         return getBTree( values.getBTreeRedirect() ).find( value ) != null;
549     }
550     
551 
552     /**
553      * @see Table#has(java.lang.Object)
554      */
555     public boolean has( K key ) throws IOException
556     {
557         return key != null && bt.find(key) != null;
558     }
559 
560 
561     /**
562      * @see org.apache.directory.server.xdbm.Table#put(java.lang.Object,
563      * java.lang.Object)
564      */
565     @SuppressWarnings("unchecked")
566     public void put( K key, V value ) throws Exception
567     {
568         if ( value == null || key == null )
569         {
570             throw new IllegalArgumentException( "null for key or value is not valid" );
571         }
572         
573         V replaced;
574 
575         if ( ! allowsDuplicates )
576         {
577             replaced = ( V ) bt.insert( key, value, true );
578 
579             if ( null == replaced )
580             {
581                 count++;
582             }
583 
584             return;
585         }
586         
587         DupsContainer<V> values = getDupsContainer( ( byte[] ) bt.find( key ) );
588         if ( values.isAvlTree() )
589         {
590             AvlTree<V> set = values.getAvlTree();
591             replaced = set.insert( value );
592             
593             if ( replaced != null )// if the value already present returns the same value
594             {
595                 return;
596             }
597             
598             if ( set.getSize() > numDupLimit )
599             {
600                 BTree tree = convertToBTree( set );
601                 BTreeRedirect redirect = new BTreeRedirect( tree.getRecid() );
602                 bt.insert( key, BTreeRedirectMarshaller.INSTANCE.serialize( redirect ), true );
603             }
604             else
605             {
606                 bt.insert( key, marshaller.serialize( set ), true );
607             }
608 
609             count++;
610             return;
611         }
612         
613         BTree tree = getBTree( values.getBTreeRedirect() );
614         replaced = ( V ) tree.insert( value, EMPTY_BYTES, true );
615         
616         if ( replaced == null )
617         {
618             count++;
619         }
620     }
621     
622 
623     /**
624      * @see org.apache.directory.server.xdbm.Table#remove(java.lang.Object,
625      * java.lang.Object)
626      */
627     @SuppressWarnings("unchecked")
628     public void remove( K key, V value ) throws IOException
629     {
630         if ( key == null )
631         {
632             return;
633         }
634 
635         if ( ! allowsDuplicates )
636         {
637             V oldValue = ( V ) bt.find( key );
638         
639             // Remove the value only if it is the same as value.
640             if ( oldValue != null && oldValue.equals( value ) )
641             {
642                 bt.remove( key );
643                 count--;
644                 return;
645             }
646 
647             return;
648         }
649 
650         DupsContainer<V> values = getDupsContainer( ( byte[] ) bt.find( key ) );
651         if ( values.isAvlTree() )
652         {
653             AvlTree<V> set = values.getAvlTree();
654 
655             // If removal succeeds then remove if set is empty else replace it
656             if ( set.remove( value ) != null )
657             {
658                 if ( set.isEmpty() )
659                 {
660                     bt.remove( key );
661                 }
662                 else
663                 {
664                     bt.insert( key, marshaller.serialize( set ), true );
665                 }
666                 count--;
667                 return;
668             }
669 
670             return;
671         }
672 
673         // if the number of duplicates falls below the numDupLimit value
674         BTree tree = getBTree( values.getBTreeRedirect() );
675         if ( removeDupFromBTree( tree, value ) )
676         {
677             /*
678              * If we drop below the duplicate limit then we revert from using
679              * a Jdbm BTree to using an in memory AvlTree.
680              */
681             if ( tree.size() <= numDupLimit )
682             {
683                 AvlTree<V> avlTree = convertToAvlTree( tree );
684                 bt.insert( key, marshaller.serialize( avlTree ), true );
685                 recMan.delete( tree.getRecid() );
686             }
687             
688             count--;
689         }
690         
691     }
692 
693 
694     /**
695      * @see Table#remove(Object)
696      */
697     public void remove( K key ) throws IOException
698     {
699         if ( key == null )
700         {
701             return;
702         }
703 
704         Object returned = bt.remove( key );
705 
706         if ( null == returned )
707         {
708             return;
709         }
710 
711         if ( ! allowsDuplicates )
712         {
713             this.count--;
714             return;
715         }
716 
717         byte[] serialized = ( byte[] ) returned;
718 
719         if ( BTreeRedirectMarshaller.isRedirect( serialized ) )
720         {
721             BTree tree = getBTree( BTreeRedirectMarshaller.INSTANCE.deserialize( serialized ) );
722             this.count -= tree.size();
723             return;
724         }
725         else
726         {
727             AvlTree<V> set = marshaller.deserialize( serialized );
728             this.count -= set.getSize();
729             return;
730         }
731     }
732 
733 
734     public Cursor<org.apache.directory.server.xdbm.Tuple<K,V>> cursor() throws Exception
735     {
736         if ( allowsDuplicates )
737         {
738             return new DupsCursor<K,V>( this );
739         }
740 
741         return new NoDupsCursor<K,V>( this );
742     }
743 
744 
745     @SuppressWarnings("unchecked")
746     public Cursor<org.apache.directory.server.xdbm.Tuple<K,V>> cursor( K key ) throws Exception
747     {
748         if ( key == null )
749         {
750             return new EmptyCursor<org.apache.directory.server.xdbm.Tuple<K,V>>();
751         }
752 
753         Object raw = bt.find( key );
754 
755         if ( null == raw )
756         {
757             return new EmptyCursor<org.apache.directory.server.xdbm.Tuple<K,V>>();
758         }
759 
760         if ( ! allowsDuplicates )
761         {
762             return new SingletonCursor<org.apache.directory.server.xdbm.Tuple<K,V>>( new org.apache.directory.server.xdbm.Tuple<K,V>( key, ( V ) raw ) );
763         }
764 
765         byte[] serialized = ( byte[] ) raw;
766         if ( BTreeRedirectMarshaller.isRedirect( serialized ) )
767         {
768             BTree tree = getBTree( BTreeRedirectMarshaller.INSTANCE.deserialize( serialized ) );
769             return new KeyTupleBTreeCursor<K,V>( tree, key, valueComparator );
770         }
771 
772         AvlTree<V> set = marshaller.deserialize( serialized );
773         return new KeyTupleAvlCursor<K,V>( set, key );
774     }
775 
776 
777     @SuppressWarnings("unchecked")
778     public Cursor<V> valueCursor( K key ) throws Exception
779     {
780         if ( key == null )
781         {
782             return new EmptyCursor<V>();
783         }
784 
785         Object raw = bt.find( key );
786 
787         if ( null == raw )
788         {
789             return new EmptyCursor<V>();
790         }
791 
792         if ( ! allowsDuplicates )
793         {
794             return new SingletonCursor<V>( ( V ) raw );
795         }
796 
797         byte[] serialized = ( byte[] ) raw;
798         if ( BTreeRedirectMarshaller.isRedirect( serialized ) )
799         {
800             BTree tree = getBTree( BTreeRedirectMarshaller.INSTANCE.deserialize( serialized ) );
801             return new KeyBTreeCursor<V>( tree, valueComparator );
802         }
803 
804         return new AvlTreeCursor<V>( marshaller.deserialize( serialized ) );
805     }
806 
807 
808     // ------------------------------------------------------------------------
809     // Maintenance Operations 
810     // ------------------------------------------------------------------------
811 
812 
813     /**
814      * @see Table#close()
815      */
816     public synchronized void close() throws IOException
817     {
818         sync();
819     }
820 
821 
822     /**
823      * Synchronizes the buffers with disk.
824      *
825      * @throws IOException if errors are encountered on the flush
826      */
827     public void sync() throws IOException
828     {
829         long recId = recMan.getNamedObject( name + SZSUFFIX );
830         recMan.update( recId, count );
831     }
832 
833     
834     public Marshaller<AvlTree<V>> getMarshaller()
835     {
836         return marshaller;
837     }
838     
839 
840     // ------------------------------------------------------------------------
841     // Private/Package Utility Methods 
842     // ------------------------------------------------------------------------
843 
844 
845     DupsContainer<V> getDupsContainer( byte[] serialized ) throws IOException
846     {
847         if ( serialized == null )
848         {
849             return new DupsContainer<V>( new AvlTree<V>( valueComparator ) );
850         }
851 
852         if ( BTreeRedirectMarshaller.isRedirect( serialized ) )
853         {
854             return new DupsContainer<V>( BTreeRedirectMarshaller.INSTANCE.deserialize( serialized ) );
855         }
856 
857         return new DupsContainer<V>( marshaller.deserialize( serialized ) );
858     }
859 
860 
861     /**
862      * Returns the main BTree used by this table.
863      *
864      * @return the main JDBM BTree used by this table
865      */
866     BTree getBTree()
867     {
868         return bt;
869     }
870 
871 
872     BTree getBTree( BTreeRedirect redirect ) throws IOException
873     {
874         if ( duplicateBtrees.containsKey( redirect.getRecId() ) )
875         {
876             return duplicateBtrees.get( redirect.getRecId() );
877         }
878         
879         BTree tree = BTree.load( recMan, redirect.getRecId() );
880         duplicateBtrees.put( redirect.getRecId(), tree );
881         return tree;
882     }
883 
884 
885     @SuppressWarnings("unchecked")
886     private boolean btreeHas( BTree tree, V key, boolean isGreaterThan ) throws IOException
887     {
888         jdbm.helper.Tuple tuple = new jdbm.helper.Tuple();
889         
890         TupleBrowser browser = tree.browse( key );
891         if ( isGreaterThan )
892         {
893             return browser.getNext( tuple );
894         }
895         else
896         {
897             if ( browser.getPrevious( tuple ) )
898             {
899                 return true;
900             }
901             else
902             {
903                 /*
904                  * getPrevious() above fails which means the browser has is
905                  * before the first Tuple of the btree.  A call to getNext()
906                  * should work every time.
907                  */
908                 browser.getNext( tuple );
909 
910                 /*
911                  * Since the browser is positioned now on the Tuple with the
912                  * smallest key we just need to check if it equals this key
913                  * which is the only chance for returning true.
914                  */
915                 V firstKey = ( V ) tuple.getKey();
916                 return valueComparator.compare( key, firstKey ) == 0;
917             }
918         }
919     }
920 
921 
922     private boolean removeDupFromBTree( BTree tree, V value ) throws IOException
923     {
924         Object removed = null;
925         if ( tree.find( value ) != null )
926         {
927             removed = tree.remove( value );
928         }
929         return null != removed;
930     }
931 
932 
933     @SuppressWarnings("unchecked")
934     private AvlTree<V> convertToAvlTree( BTree bTree ) throws IOException
935     {
936         AvlTree<V> avlTree = new AvlTree<V>( valueComparator );
937         TupleBrowser browser = bTree.browse();
938         jdbm.helper.Tuple tuple = new jdbm.helper.Tuple();
939         while ( browser.getNext( tuple ) )
940         {
941             avlTree.insert( ( V ) tuple.getKey() );
942         }
943 
944         return avlTree;
945     }
946     
947 
948     private BTree convertToBTree( AvlTree<V> avlTree ) throws Exception
949     {
950         BTree bTree;
951 
952         if ( valueSerializer != null )
953         {
954             bTree = BTree.createInstance( recMan, valueComparator, valueSerializer, null );
955         }
956         else
957         {
958             bTree = BTree.createInstance( recMan, valueComparator );
959         }
960 
961         Cursor<V> keys = new AvlTreeCursor<V>( avlTree );
962         keys.beforeFirst();
963         while ( keys.next() )
964         {
965             bTree.insert( keys.get(), EMPTY_BYTES, true );
966         }
967         return bTree;
968     }
969 }