View Javadoc

1   /*
2    *   Copyright 2004 The Apache Software Foundation
3    *
4    *   Licensed under the Apache License, Version 2.0 (the "License");
5    *   you may not use this file except in compliance with the License.
6    *   You may obtain a copy of the License at
7    *
8    *       http://www.apache.org/licenses/LICENSE-2.0
9    *
10   *   Unless required by applicable law or agreed to in writing, software
11   *   distributed under the License is distributed on an "AS IS" BASIS,
12   *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   *   See the License for the specific language governing permissions and
14   *   limitations under the License.
15   *
16   */
17  package org.apache.ldap.server.partition.impl.btree.jdbm;
18  
19  
20  import java.io.IOException;
21  import java.util.ArrayList;
22  import java.util.Collections;
23  import java.util.Iterator;
24  import java.util.SortedSet;
25  import java.util.TreeSet;
26  
27  import javax.naming.NamingEnumeration;
28  import javax.naming.NamingException;
29  
30  import jdbm.RecordManager;
31  import jdbm.btree.BTree;
32  import jdbm.helper.TupleBrowser;
33  
34  import org.apache.ldap.common.util.EmptyEnumeration;
35  import org.apache.ldap.common.util.SingletonEnumeration;
36  import org.apache.ldap.server.partition.impl.btree.DupsEnumeration;
37  import org.apache.ldap.server.partition.impl.btree.KeyOnlyComparator;
38  import org.apache.ldap.server.partition.impl.btree.NoDupsEnumeration;
39  import org.apache.ldap.server.partition.impl.btree.Table;
40  import org.apache.ldap.server.partition.impl.btree.Tuple;
41  import org.apache.ldap.server.partition.impl.btree.TupleComparator;
42  import org.apache.ldap.server.partition.impl.btree.TupleEnumeration;
43  import org.apache.ldap.server.partition.impl.btree.TupleRenderer;
44  import org.apache.ldap.server.schema.SerializableComparator;
45  
46  
47  /***
48   * A jdbm Btree wrapper that enables duplicate sorted keys using collections.
49   *
50   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
51   * @version $Rev: 264732 $
52   */
53  public class JdbmTable implements Table
54  {
55      /***  */
56      private static final String SZSUFFIX = "_btree_sz";
57  
58      /*** */
59      private final String name;
60      /*** */
61      private final RecordManager recMan;
62      /*** */
63      private final boolean allowsDuplicates;
64      /*** */
65      private final TupleComparator comparator;
66  
67      /*** */
68      private int count = 0;
69      /*** */
70      private BTree bt;
71      /*** */
72      private TupleRenderer renderer;
73  
74  
75      // ------------------------------------------------------------------------
76      // C O N S T R U C T O R
77      // ------------------------------------------------------------------------
78  
79      
80      /***
81       * Creates a Jdbm BTree based tuple Table abstraction that enables 
82       * duplicates.
83       *
84       * @param name the name of the table
85       * @param allowsDuplicates whether or not duplicates are enabled 
86       * @param manager the record manager to be used for this table
87       * @param comparator a tuple comparator
88       * @throws NamingException if the table's file cannot be created
89       */
90      public JdbmTable( String name, boolean allowsDuplicates,
91          RecordManager manager, TupleComparator comparator )
92          throws NamingException
93      {
94          this.name = name;
95          this.recMan = manager;
96          this.comparator = comparator;
97          this.allowsDuplicates = allowsDuplicates;
98  
99          long recId;
100         
101         try
102         { 
103             recId = recMan.getNamedObject( name );
104         }
105         catch ( IOException e )
106         {
107             NamingException ne = new NamingException();
108             ne.setRootCause( e );
109             throw ne;
110         }
111         
112         try
113         {
114 
115             //            
116             // Load existing BTree
117             //
118             
119             if ( recId != 0 )
120             {
121                 bt = BTree.load( recMan, recId );
122                 recId = recMan.getNamedObject( name + SZSUFFIX );
123                 count = ( ( Integer ) recMan.fetch( recId ) ).intValue();
124             }
125             else
126             {
127                 bt = BTree.createInstance( recMan, comparator.getKeyComparator() );
128                 recId = bt.getRecid();
129                 recMan.setNamedObject( name, recId );
130                 recId = recMan.insert( new Integer( 0 ) );
131                 recMan.setNamedObject( name + SZSUFFIX, recId );
132             }
133         }   
134         catch ( IOException e ) 
135         {
136             NamingException ne = new NamingException();
137             ne.setRootCause( e );
138             throw ne;
139         }
140     }
141 
142 
143     /***
144      * Creates a Jdbm BTree based tuple Table abstraction without duplicates 
145      * enabled using a simple key comparator.
146      *
147      * @param name the name of the table
148      * @param manager the record manager to be used for this table
149      * @param keyComparator a tuple comparator
150      * @throws NamingException if the table's file cannot be created
151      */
152     public JdbmTable( String name, RecordManager manager,
153                       SerializableComparator keyComparator )
154             throws NamingException
155     {
156         this( name, false, manager, new KeyOnlyComparator( keyComparator ) );
157     }
158 
159 
160     // ------------------------------------------------------------------------
161     // Simple Table Properties
162     // ------------------------------------------------------------------------
163 
164 
165     /***
166      * @see org.apache.ldap.server.partition.impl.btree.Table#getComparator()
167      */
168     public TupleComparator getComparator()
169     {
170         return comparator;
171     }
172 
173 
174     /***
175      * @see org.apache.ldap.server.partition.impl.btree.Table#isDupsEnabled()
176      */
177     public boolean isDupsEnabled()
178     {
179         return allowsDuplicates;
180     }
181 
182 
183     /***
184      * @see org.apache.ldap.server.partition.impl.btree.Table#getName()
185      */
186     public String getName()
187     {
188         return name;
189     }
190 
191 
192     /***
193      * @see org.apache.ldap.server.partition.impl.btree.Table#getRenderer()
194      */
195     public TupleRenderer getRenderer()
196     {
197         return renderer;
198     }
199 
200 
201     /***
202      * @see Table#setRenderer(
203      * TupleRenderer)
204      */
205     public void setRenderer( TupleRenderer renderer )
206     {
207         this.renderer = renderer;
208     }
209 
210 
211     /***
212      * @see Table#isSortedDupsEnabled()
213      */
214     public boolean isSortedDupsEnabled()
215     {
216         // If duplicates are enabled than duplicates will be maintained in
217         // sorted order.
218         return allowsDuplicates;
219     }
220     
221     
222     // ------------------------------------------------------------------------
223     // Count Overloads
224     // ------------------------------------------------------------------------
225 
226 
227     /***
228      * @see Table#count(java.lang.Object, boolean)
229      */
230     public int count( Object key, boolean isGreaterThan )
231         throws NamingException
232     {
233         throw new UnsupportedOperationException();
234     }
235 
236 
237     /***
238      * @see Table#count(java.lang.Object)
239      */
240     public int count( Object key )
241         throws NamingException
242     {
243         if ( ! allowsDuplicates ) 
244         {
245             if ( null == getRaw( key ) ) 
246             {
247                 return 0;
248             } 
249             else 
250             {
251                 return 1;
252             }
253         }
254 
255         TreeSet set = ( TreeSet ) getRaw( key );
256 
257         if ( set != null ) 
258         {
259             return set.size();
260         }
261 
262         return 0;
263     }
264 
265 
266     /***
267      * @see org.apache.ldap.server.partition.impl.btree.Table#count()
268      */
269     public int count()
270         throws NamingException
271     {
272         return count;
273     }
274 
275 
276     // ------------------------------------------------------------------------
277     // get/has/put/remove Methods and Overloads
278     // ------------------------------------------------------------------------
279 
280 
281     /***
282      * @see Table#get(java.lang.Object)
283      */
284     public Object get( Object key ) throws NamingException
285     {
286         if ( allowsDuplicates ) 
287         {
288             TreeSet set = ( TreeSet ) getRaw( key );
289             if ( null == set || set.size() == 0 ) 
290             {
291                 return null;
292             } 
293             else 
294             {
295                 return set.first();
296             }
297         }
298 
299         Object value = getRaw( key );
300         return value;
301     }
302 
303 
304     /***
305      * @see Table#has(java.lang.Object,
306      * java.lang.Object, boolean)
307      */
308     public boolean has( Object key, Object val, boolean isGreaterThan )
309         throws NamingException
310     {
311         TreeSet set = null;
312         SortedSet subset = null;
313         
314         if ( ! allowsDuplicates ) 
315         {
316             Object rval = getRaw( key );
317 
318             // key does not exist so return nothing
319             if ( null == rval )
320             {
321                 return false;
322             }
323             // val == val return tuple
324             else if ( val.equals( rval ) )
325             {
326                 return true;
327             }
328             // val >= val and test is for greater then return tuple
329             else if ( comparator.compareValue( rval, val ) >= 1 && isGreaterThan )
330             {
331                 return true;
332             }
333             // val <= val and test is for lesser then return tuple
334             else if ( comparator.compareValue( rval, val ) <= 1 &&! isGreaterThan )
335             {
336                 return true;
337             }
338 
339             return false;
340         }
341 
342         set = ( TreeSet ) getRaw( key );
343         
344         if ( null == set || set.size() == 0 ) 
345         {
346             return false;
347         }
348 
349         if ( isGreaterThan ) 
350         {
351             subset = set.tailSet( val );
352         } 
353         else 
354         {
355             subset = set.headSet( val );
356         }
357 
358         if ( subset.size() > 0 || set.contains( val ) ) 
359         {
360             return true;
361         }
362 
363         return false;
364     }
365 
366 
367     /***
368      * @see Table#has(java.lang.Object, boolean)
369      */
370     public boolean has( Object key, boolean isGreaterThan ) throws NamingException
371     {
372         try
373         {
374             // See if we can find the border between keys greater than and less
375             // than in the set of keys.  This will be the spot we search from.
376             jdbm.helper.Tuple tuple = bt.findGreaterOrEqual( key );
377     
378             // Test for equality first since it satisfies both greater/less than
379             if ( null != tuple &&
380                 comparator.compareKey( tuple.getKey(), key ) == 0 )
381             {
382                 return true;
383             }
384     
385             // Greater searches are easy and quick thanks to findGreaterOrEqual
386             if ( isGreaterThan ) 
387             {
388                 // A null return above means there were no equal or greater keys
389                 if ( null == tuple ) 
390                 {
391                     return false;
392                 }
393     
394                 // Not Null! - we found a tuple with equal or greater key value
395                 return true;
396             }
397     
398             // Less than searches occur below and are not as efficient or easy.
399             // We need to scan up from the begining if findGreaterOrEqual failed
400             // or scan down if findGreaterOrEqual succeed.
401             TupleBrowser browser = null;
402             if ( null == tuple ) 
403             {
404                 // findGreaterOrEqual failed so we create a tuple and scan from
405                 // the lowest values up via getNext comparing each key to key
406                 tuple = new jdbm.helper.Tuple();
407                 browser = bt.browse();
408     
409                 // We should at most have to read one key.  If 1st key is not
410                 // less than or equal to key then all keys are > key
411                 // since the keys are assorted in ascending order based on the
412                 // comparator.
413                 while ( browser.getNext( tuple ) ) 
414                 {
415                     if ( comparator.compareKey( tuple.getKey(), key ) 
416                         <= 0 )
417                     {
418                         return true;
419                     } 
420 
421                     return false;
422                 }
423             } 
424             else 
425             {
426                 // findGreaterOrEqual succeeded so use the existing tuple and
427                 // scan the down from the highest key less than key via
428                 // getPrevious while comparing each key to key.
429                 browser = bt.browse( tuple.getKey() );
430     
431                 // The above call positions the browser just before the given
432                 // key so we need to step forward once then back.  Remember this
433                 // key represents a key greater than or equal to key.
434                 if ( comparator.compareKey( tuple.getKey(), key ) <= 0 ) 
435                 {
436                     return true;
437                 }
438                 
439                 browser.getNext( tuple );
440     
441                 // We should at most have to read one key, but we don't short
442                 // the search as in the search above first because the chance of
443                 // unneccessarily looping is nil since values get smaller.
444                 while ( browser.getPrevious( tuple ) ) 
445                 {
446                     if ( comparator.compareKey( tuple.getKey(), key ) 
447                         <= 0 )
448                     {
449                         return true;
450                     }
451                 }
452             }
453         }
454         catch ( IOException e ) 
455         {
456             NamingException ne = new NamingException();
457             ne.setRootCause( e );
458             throw ne;
459         }
460 
461         return false;
462     }
463 
464 
465     /***
466      * @see org.apache.ldap.server.partition.impl.btree.Table#has(java.lang.Object,
467      * java.lang.Object)
468      */
469     public boolean has( Object key, Object value )
470         throws NamingException
471     {
472         if ( allowsDuplicates ) 
473         {
474             TreeSet set = ( TreeSet ) getRaw( key );
475             
476             if ( null == set ) 
477             {
478                 return false;
479             }
480 
481             return set.contains( value );
482         }
483 
484         Object obj = getRaw( key );
485         
486         if ( null == obj ) 
487         {
488             return false;
489         }
490 
491         return obj.equals( value );
492     }
493 
494 
495     /***
496      * @see Table#has(java.lang.Object)
497      */
498     public boolean has( Object key )
499         throws NamingException
500     {
501         return getRaw( key ) != null;
502     }
503 
504 
505     /***
506      * @see org.apache.ldap.server.partition.impl.btree.Table#put(java.lang.Object,
507      * java.lang.Object)
508      */
509     public Object put( Object key, Object value )
510         throws NamingException
511     {
512         Object replaced = null;
513 
514         if ( allowsDuplicates ) 
515         {
516             TreeSet set = ( TreeSet ) getRaw( key );
517             
518             if ( null == set )
519             {
520                 set = new TreeSet( comparator.getValueComparator() );
521             } 
522             else if ( set.contains( value ) ) 
523             {
524                 return value;
525             }
526 
527             set.add( value );
528             putRaw( key, set, true );
529             count++;
530             return null;
531         }
532 
533         replaced = putRaw( key, value, true );
534 
535         if ( null == replaced ) 
536         {
537             count++;
538         }
539 
540         return replaced;
541     }
542 
543     
544     /***
545      * @see Table#put(java.lang.Object,
546      * javax.naming.NamingEnumeration)
547      */
548     public Object put( Object key, NamingEnumeration values )
549         throws NamingException
550     {
551         TreeSet set = null;
552 
553         /*
554          * If we do not allow duplicates call the single add put using the
555          * first value in the enumeration if it exists.  If it does not we
556          * just return null without doing anything.  If more than one value
557          * is in the enumeration than we blow a UnsupportedOperationException.
558          */
559         if ( ! allowsDuplicates )
560         {
561             if ( values.hasMore() )
562             {
563                 Object value = values.next();
564                 
565                 if ( values.hasMore() )
566                 {
567                     throw new UnsupportedOperationException(
568                         "Attempting to put duplicate keys into table " 
569                         + name + " which does not support duplicates" );    
570                 }
571                 
572                 return put( key, value );
573             }
574             
575             return null;
576         }
577 
578         /*
579          * Here the table allows duplicates so we get the TreeSet from the 
580          * Table holding all the duplicate key values or create one if it
581          * does not exist for key.  We check if the value is present and
582          * if it is we add it and increment the table entry counter.
583          */
584         set = ( TreeSet ) getRaw( key );
585 
586         if ( null == set ) 
587         {
588             set = new TreeSet( comparator.getValueComparator() );
589         } 
590 
591         while ( values.hasMore() ) 
592         {
593             Object val = values.next();
594             
595             if ( ! set.contains( val ) ) 
596             {
597                 set.add( val );
598                 count++;
599             }
600         }
601 
602         // Return the raw TreeSet
603         return putRaw( key, set, true );
604     }
605 
606 
607     /***
608      * @see Table#remove(java.lang.Object,
609      * java.lang.Object)
610      */
611     public Object remove( Object key, Object value )
612         throws NamingException
613     {
614         if ( allowsDuplicates ) 
615         {
616             TreeSet set = ( TreeSet ) getRaw( key );
617 
618             if ( null == set ) 
619             {
620                 return null;
621             }
622 
623             // If removal succeeds then remove if set is empty else replace it
624             if ( set.remove( value ) )  
625             {
626                 if ( set.isEmpty() ) 
627                 {
628                     removeRaw( key );
629                 } 
630                 else 
631                 {
632                     putRaw( key, set, true );
633                 }
634 
635                 // Decrement counter if removal occurs.
636                 count--;
637                 return value;
638             }
639 
640             return null;
641         }
642 
643         // Remove the value only if it is the same as value.
644         if ( getRaw( key ).equals( value ) ) 
645         {
646             return removeRaw( key );
647         }
648 
649         return null;
650     }
651 
652 
653     /***
654      * @see Table#remove(java.lang.Object,
655      * javax.naming.NamingEnumeration)
656      */
657     public Object remove( Object key, NamingEnumeration values )
658         throws NamingException
659     {
660         TreeSet set = null;
661         
662         /*
663          * If we do not allow dupliicates call the single remove using the
664          * first value in the enumeration if it exists.  If it does not we
665          * just return null without doing anything.  If more than one value
666          * is in the enumeration than we blow a UnsupportedOperationException.
667          */
668         if ( ! allowsDuplicates )
669         {
670             if ( values.hasMore() )
671             {
672                 Object value = values.next();
673                 
674                 if ( values.hasMore() )
675                 {
676                     throw new UnsupportedOperationException(
677                         "Attempting to put duplicate keys into table " 
678                         + name + " which does not support duplicates" );    
679                 }
680                 
681                 return remove( key, value );
682             }
683             
684             return null;
685         }
686 
687         /*
688          * Here the table allows duplicates so we get the TreeSet from the 
689          * Table holding all the duplicate key values or return null if it
690          * does not exist for key - nothing to do here.
691          */
692         set = ( TreeSet ) getRaw( key );
693         if ( null == set ) 
694         {
695             return null;
696         } 
697 
698         /*
699          * So we have a valid TreeSet with values in it.  We check if each value
700          * is in the set and remove it if it is present.  We decrement the 
701          * counter while doing so.
702          */
703         while ( values.hasMore() ) 
704         {
705             Object val = values.next();
706             
707             if ( ! set.contains( val ) ) 
708             {
709                 set.remove( val );
710                 count--;
711             }
712         }
713 
714         // Return the raw TreeSet and put the changed one back.
715         return putRaw( key, set, true );
716     }
717 
718 
719     /***
720      * @see Table#remove(java.lang.Object)
721      */
722     public Object remove( Object key )
723         throws NamingException
724     {
725         Object returned = removeRaw( key );
726 
727         if ( null == returned ) 
728         {
729             return null;
730         }
731 
732         if ( allowsDuplicates ) 
733         {
734             TreeSet set = ( TreeSet ) returned;
735             this.count -= set.size();
736             return set.first();
737         }
738 
739         this.count--;
740         return returned;
741     }
742 
743     
744     /***
745      * @see Table#listValues(java.lang.Object)
746      */
747     public NamingEnumeration listValues( Object key ) 
748         throws NamingException 
749     {
750         TreeSet set = null;
751         
752         if ( ! allowsDuplicates )
753         {
754             Object value = get( key );
755             
756             if ( null == value )
757             {
758                 return new EmptyEnumeration();
759             }
760             else 
761             {
762                 return new SingletonEnumeration( value );
763             }
764         }
765 
766         set = ( TreeSet ) getRaw( key );
767         if ( null == set )
768         {
769             return new EmptyEnumeration();
770         }
771 
772         final Iterator list = set.iterator();
773         return new NamingEnumeration()
774         {
775            public void close()
776            {
777            }
778            
779            public Object nextElement()
780            {
781                return list.next();
782            } 
783 
784            public Object next()
785            {
786                return list.next();
787            }
788            
789            public boolean hasMore() 
790            {
791                return list.hasNext();
792            }
793            
794            public boolean hasMoreElements()
795            {
796                return list.hasNext();
797            }           
798         };
799     }
800 
801 
802     // ------------------------------------------------------------------------
803     // listTuple Overloads 
804     // ------------------------------------------------------------------------
805 
806 
807     /***
808      * @see org.apache.ldap.server.partition.impl.btree.Table#listTuples()
809      */
810     public NamingEnumeration listTuples()
811         throws NamingException
812     {
813         NamingEnumeration list = null;
814         
815         try 
816         {
817             JdbmTupleBrowser browser = new JdbmTupleBrowser( bt.browse() );
818             list = new NoDupsEnumeration( browser, true );
819         }
820         catch ( IOException e ) 
821         {
822             NamingException ne = new NamingException();
823             ne.setRootCause( e );
824             throw ne;
825         }
826 
827         if ( allowsDuplicates ) 
828         {
829             return new DupsEnumeration( ( NoDupsEnumeration ) list );
830         }
831 
832         return list;
833     }
834 
835 
836     /***
837      * @see org.apache.ldap.server.partition.impl.btree.Table#listTuples(java.lang.Object)
838      */
839     public NamingEnumeration listTuples( Object key )
840         throws NamingException
841     {
842         TreeSet set = null;
843 
844         // Handle single and zero value returns without duplicates enabled
845         if ( ! allowsDuplicates ) 
846         {
847             Object val = getRaw( key );
848             
849             if ( null == val ) 
850             {
851                 return new EmptyEnumeration();
852             } 
853             else 
854             {
855                 return new SingletonEnumeration( 
856                     new Tuple( key, getRaw( key ) ) );
857             }
858         }
859 
860         set = ( TreeSet ) getRaw( key );
861         if ( set == null ) 
862         {
863             return new EmptyEnumeration();
864         }
865 
866         return new TupleEnumeration( key, set.iterator() );
867     }
868 
869 
870     /***
871      * @see Table#listTuples(java.lang.Object,
872      * boolean)
873      */
874     public NamingEnumeration listTuples( Object key, boolean isGreaterThan )
875         throws NamingException
876     {
877         NamingEnumeration list = null;
878 
879         try 
880         {
881             if ( isGreaterThan ) 
882             {
883                 JdbmTupleBrowser browser =
884                     new JdbmTupleBrowser( bt.browse( key ) );
885                 list = new NoDupsEnumeration( browser, isGreaterThan );
886             } 
887             else 
888             {
889                 /* According to the jdbm docs a browser is positioned right
890                  * before a key greater than or equal to key.  getNext() will
891                  * return the next tuple with a key greater than or equal to
892                  * key.  getPrevious() used in descending scans for less than
893                  * for equal to comparisions will not.  We need to advance
894                  * forward once and check if the returned Tuple key equals
895                  * key.  If it does then we do nothing feeding in the browser
896                  * to the NoDupsCursor.  If it does not we call getPrevious and
897                  * pass it into the NoDupsCursor constructor.
898                  */
899                 jdbm.helper.Tuple tuple = new jdbm.helper.Tuple();
900                 TupleBrowser browser = bt.browse( key ); 
901                 
902                 if ( browser.getNext( tuple ) ) 
903                 {
904                     Object greaterKey = tuple.getKey();
905                     
906                     if ( 0 != comparator.compareKey( key, greaterKey ) ) 
907                     {
908                         // Make sure we don't return greaterKey in cursor
909                         browser.getPrevious( tuple );
910                     }
911                 }
912 
913                 // If greaterKey != key above then it will not be returned.
914                 list = new NoDupsEnumeration( 
915                     new JdbmTupleBrowser( browser ), isGreaterThan );
916             }
917         } 
918         catch ( IOException e ) 
919         {
920             NamingException ne = new NamingException(
921                 "Failed to get TupleBrowser on table "
922                 + name + " using key " + renderKey( key ) );
923             ne.setRootCause( e );
924             throw ne;
925         }
926 
927         if ( allowsDuplicates ) 
928         {
929             list = new DupsEnumeration( ( NoDupsEnumeration ) list );
930         }
931 
932         return list;
933     }
934     
935 
936     /***
937      * @see org.apache.ldap.server.partition.impl.btree.Table#listTuples(java.lang.Object,
938      * java.lang.Object, boolean)
939      */
940     public NamingEnumeration listTuples( Object key, Object val, 
941         boolean isGreaterThan ) throws NamingException
942     {
943         TreeSet set = null;
944         
945         if ( ! allowsDuplicates ) 
946         {
947             Object rval = getRaw( key );
948 
949             if ( null == rval ) // key does not exist so return nothing
950             {
951                 return new EmptyEnumeration();
952             }
953             else if ( val.equals( rval ) ) // val == rval return tuple
954             {
955                 return new SingletonEnumeration( new Tuple( key, val ) );
956             }
957             // val >= val and test is for greater then return tuple
958             else if ( comparator.compareValue( val, rval ) >= 1 && isGreaterThan )
959             {
960                 return new SingletonEnumeration( new Tuple( key, val ) );
961             }
962             // val <= val and test is for lesser then return tuple
963             else if ( comparator.compareValue( val, rval ) <= 1 && ! isGreaterThan )
964             {
965                 return new SingletonEnumeration( new Tuple( key, val ) );
966             }
967 
968             return new EmptyEnumeration();
969         }
970 
971         
972         set = ( TreeSet ) getRaw( key );
973         if ( set == null ) 
974         {
975             return new EmptyEnumeration();
976         }
977 
978         if ( isGreaterThan ) 
979         {
980             return new TupleEnumeration( key, 
981                 set.tailSet( val ).iterator() );
982         } 
983         else 
984         {
985             // Get all values from the smallest upto val and put them into
986             // a list.  They will be in ascending order so we need to reverse
987             // the list after adding val which is not included in headSet.
988             SortedSet headset = set.headSet( val );
989             ArrayList list = new ArrayList( set.size() + 1 );
990             list.addAll( headset );
991 
992             // Add largest value (val) if it is in the set.  TreeSet.headSet
993             // does not get val if val is in the set.  So we add it now to
994             // the end of the list.  List is now ascending from smallest to
995             // val
996             if ( set.contains( val ) ) 
997             {
998                 list.add( val );
999             }
1000 
1001             // Reverse the list now we have descending values from val to the
1002             // smallest value that key has.  Return tuple cursor over list.
1003             Collections.reverse( list );
1004             return new TupleEnumeration( key, list.iterator() );
1005         }
1006     }
1007 
1008 
1009     // ------------------------------------------------------------------------
1010     // Maintenance Operations 
1011     // ------------------------------------------------------------------------
1012 
1013 
1014     /***
1015      * @see Table#close()
1016      */
1017     public synchronized void close()
1018         throws NamingException
1019     {
1020         sync();
1021     }
1022 
1023 
1024     /***
1025      * Synchronizes the buffers with disk.
1026      *
1027      * @throws NamingException if errors are encountered on the flush
1028      */
1029     public void sync() throws NamingException
1030     {
1031         try 
1032         {  
1033             long recId = recMan.getNamedObject( name + SZSUFFIX );
1034                   
1035             if ( 0 == recId ) 
1036             {
1037                 recId = recMan.insert( new Integer( count ) );
1038             } 
1039             else 
1040             {
1041                 recMan.update( recId, new Integer( count ) );
1042             }
1043         }
1044         catch ( IOException e )
1045         {
1046             NamingException ne = new NamingException();
1047             ne.setRootCause( e );
1048             throw ne;
1049         }
1050     }
1051 
1052 
1053     // ------------------------------------------------------------------------
1054     // Private Utility Methods 
1055     // ------------------------------------------------------------------------
1056 
1057 
1058     /***
1059      * Renders a key using the renderer associated with this table.
1060      *
1061      * @param obj the key to render.
1062      * @return the rendered String representation of obj
1063      */
1064     private String renderKey( Object obj )
1065     {
1066         StringBuffer buf = new StringBuffer();
1067 
1068         buf.append( "\'" );
1069         if ( null == renderer ) 
1070         {
1071             buf.append( obj.toString() );
1072         } 
1073         else 
1074         {
1075             buf.append( renderer.getKeyString( obj ) );
1076         }
1077         
1078         buf.append( "\'" );
1079         return buf.toString();
1080     }
1081 
1082 
1083     /***
1084      * Gets a Tuple value from the btree while wrapping any IOExceptions with a 
1085      * NamingException.
1086      *
1087      * @param key the key of the Tuple to get the value of 
1088      * @return the raw value object from the btree
1089      * @throws NamingException if there are any problems accessing the btree.
1090      */
1091     private Object getRaw( Object key ) throws NamingException
1092     {
1093         Object val = null;
1094         
1095         if ( null == key )
1096         {
1097             return null;
1098         }
1099 
1100         try
1101         {
1102             if ( ! allowsDuplicates )
1103             {
1104                 val = bt.find( key );
1105             }
1106             else 
1107             {
1108                 val = bt.find( key );
1109             }
1110         }
1111         catch ( IOException e ) 
1112         {
1113             NamingException ne = new NamingException();
1114             ne.setRootCause( e );
1115             throw ne;
1116         }
1117 
1118         return val;
1119     }
1120 
1121 
1122     /***
1123      * Puts a Tuple into the btree while wrapping any IOExceptions with a 
1124      * NamingException.
1125      *
1126      * @param key the key of the Tuple to put
1127      * @param value the value of the Tuple to put
1128      * @param doReplace whether or not to replace the object if it exists
1129      * @return the raw value object removed from the btree on replacement
1130      * @throws NamingException if there are any problems accessing the btree.
1131      */
1132     private Object putRaw( Object key, Object value, boolean doReplace )
1133         throws NamingException
1134     {
1135         Object val = null;
1136         
1137         try
1138         {
1139             val = bt.insert( key, value, doReplace );
1140         }
1141         catch ( IOException e ) 
1142         {
1143             NamingException ne = new NamingException();
1144             ne.setRootCause( e );
1145             throw ne;
1146         }
1147         
1148         return val;
1149     }
1150 
1151 
1152     /***
1153      * Removes a entry from the btree while wrapping any IOExceptions with a 
1154      * NamingException.
1155      *
1156      * @param key the key of the Tuple to remove
1157      * @return the raw value object removed from the btree
1158      * @throws NamingException if there are any problems accessing the btree.
1159      */
1160     private Object removeRaw( Object key )
1161         throws NamingException
1162     {
1163         Object val = null;
1164         
1165         try
1166         {
1167             val = bt.remove( key );
1168         }
1169         catch ( IOException e ) 
1170         {
1171             NamingException ne = new NamingException();
1172             ne.setRootCause( e );
1173             throw ne;
1174         }
1175         
1176         return val;
1177     }
1178 }