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