1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
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
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
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
204
205 return allowsDuplicates;
206 }
207
208
209
210
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
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
305 if ( null == rval )
306 {
307 return false;
308 }
309
310 else if ( val.equals( rval ) )
311 {
312 return true;
313 }
314
315 else if ( comparator.compareValue( rval, val ) >= 1 && isGreaterThan )
316 {
317 return true;
318 }
319
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
361
362 jdbm.helper.Tuple tuple = bt.findGreaterOrEqual( key );
363
364
365 if ( null != tuple &&
366 comparator.compareKey( tuple.getKey(), key ) == 0 )
367 {
368 return true;
369 }
370
371
372 if ( isGreaterThan )
373 {
374
375 if ( null == tuple )
376 {
377 return false;
378 }
379
380
381 return true;
382 }
383
384
385
386
387 TupleBrowser browser = null;
388 if ( null == tuple )
389 {
390
391
392 tuple = new jdbm.helper.Tuple();
393 browser = bt.browse();
394
395
396
397
398
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
413
414
415 browser = bt.browse( tuple.getKey() );
416
417
418
419
420 if ( comparator.compareKey( tuple.getKey(), key ) <= 0 )
421 {
422 return true;
423 }
424
425 browser.getNext( tuple );
426
427
428
429
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
541
542
543
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
566
567
568
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
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
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
622 count--;
623 return value;
624 }
625
626 return null;
627 }
628
629
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
650
651
652
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
675
676
677
678 set = ( TreeSet ) getRaw( key );
679 if ( null == set )
680 {
681 return null;
682 }
683
684
685
686
687
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
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
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
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
876
877
878
879
880
881
882
883
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
895 browser.getPrevious( tuple );
896 }
897 }
898
899
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 )
936 {
937 return new EmptyEnumeration();
938 }
939 else if ( val.equals( rval ) )
940 {
941 return new SingletonEnumeration( new Tuple( key, val ) );
942 }
943
944 else if ( comparator.compareValue( val, rval ) >= 1 && isGreaterThan )
945 {
946 return new SingletonEnumeration( new Tuple( key, val ) );
947 }
948
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
972
973
974 SortedSet headset = set.headSet( val );
975 ArrayList list = new ArrayList( set.size() + 1 );
976 list.addAll( headset );
977
978
979
980
981
982 if ( set.contains( val ) )
983 {
984 list.add( val );
985 }
986
987
988
989 Collections.reverse( list );
990 return new TupleEnumeration( key, list.iterator() );
991 }
992 }
993
994
995
996
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
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 }