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