1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package org.apache.directory.mavibot.btree;
21
22
23 import java.io.IOException;
24 import java.lang.reflect.Array;
25 import java.util.Comparator;
26 import java.util.Map;
27 import java.util.concurrent.ConcurrentHashMap;
28 import java.util.concurrent.ConcurrentLinkedQueue;
29 import java.util.concurrent.atomic.AtomicBoolean;
30 import java.util.concurrent.atomic.AtomicLong;
31
32 import org.apache.directory.mavibot.btree.exception.BTreeCreationException;
33 import org.apache.directory.mavibot.btree.exception.DuplicateValueNotAllowedException;
34 import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
35 import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
36
37
38
39
40
41
42
43
44
45
46
47 abstract class AbstractBTree<K, V> implements BTree<K, V>
48 {
49
50 protected long readTimeOut = DEFAULT_READ_TIMEOUT;
51
52
53 protected BTreeHeader<K, V> currentBtreeHeader;
54
55
56 protected ElementSerializer<K> keySerializer;
57
58
59 protected ElementSerializer<V> valueSerializer;
60
61
62 protected ConcurrentLinkedQueue<ReadTransaction<K, V>> readTransactions;
63
64
65 protected int writeBufferSize;
66
67
68 protected boolean allowDuplicates;
69
70
71 protected int pageSize;
72
73
74 protected String name;
75
76
77 protected String keySerializerFQCN;
78
79
80 protected String valueSerializerFQCN;
81
82
83 protected Thread readTransactionsThread;
84
85
86 protected BTreeTypeEnum btreeType;
87
88
89 protected AtomicBoolean transactionStarted = new AtomicBoolean( false );
90
91
92 protected Map<Long, BTreeHeader<K, V>> btreeRevisions = new ConcurrentHashMap<Long, BTreeHeader<K, V>>();
93
94
95 protected AtomicLong currentRevision = new AtomicLong( 0L );
96
97
98 protected TransactionManager transactionManager;
99
100
101
102
103
104
105
106
107 protected abstract ReadTransaction<K, V> beginReadTransaction();
108
109
110
111
112
113
114
115
116 protected abstract ReadTransaction<K, V> beginReadTransaction( long revision );
117
118
119
120
121
122 public TupleCursor<K, V> browse() throws IOException, KeyNotFoundException
123 {
124
125 if ( transactionManager == null )
126 {
127 throw new BTreeCreationException( "We don't have a transactionLManager" );
128 }
129
130 ReadTransaction<K, V> transaction = beginReadTransaction();
131
132 if ( transaction == null )
133 {
134 return new EmptyTupleCursor<K, V>();
135 }
136 else
137 {
138 ParentPos<K, V>[] stack = ( ParentPos<K, V>[] ) Array.newInstance( ParentPos.class, 32 );
139
140 TupleCursor<K, V> cursor = getRootPage().browse( transaction, stack, 0 );
141
142
143 cursor.beforeFirst();
144
145 return cursor;
146 }
147 }
148
149
150
151
152
153 public TupleCursor<K, V> browse( long revision ) throws IOException, KeyNotFoundException
154 {
155
156 if ( transactionManager == null )
157 {
158 throw new BTreeCreationException( "We don't have a transactionLManager" );
159 }
160
161 ReadTransaction<K, V> transaction = beginReadTransaction( revision );
162
163 if ( transaction == null )
164 {
165 return new EmptyTupleCursor<K, V>();
166 }
167 else
168 {
169 ParentPos<K, V>[] stack = ( ParentPos<K, V>[] ) Array.newInstance( ParentPos.class, 32 );
170
171
172 TupleCursor<K, V> cursor = getRootPage( transaction.getRevision() ).browse( transaction, stack, 0 );
173
174 return cursor;
175 }
176 }
177
178
179
180
181
182 public TupleCursor<K, V> browseFrom( K key ) throws IOException
183 {
184
185 if ( transactionManager == null )
186 {
187 throw new BTreeCreationException( "We don't have a transactionLManager" );
188 }
189
190 ReadTransaction<K, V> transaction = beginReadTransaction();
191
192 ParentPos<K, V>[] stack = ( ParentPos<K, V>[] ) Array.newInstance( ParentPos.class, 32 );
193
194 try
195 {
196 TupleCursor<K, V> cursor = getRootPage( transaction.getRevision() ).browse( key, transaction, stack, 0 );
197
198 return cursor;
199 }
200 catch ( KeyNotFoundException e )
201 {
202 throw new IOException( e.getMessage() );
203 }
204 }
205
206
207
208
209
210 public TupleCursor<K, V> browseFrom( long revision, K key ) throws IOException, KeyNotFoundException
211 {
212
213 if ( transactionManager == null )
214 {
215 throw new BTreeCreationException( "We don't have a transactionLManager" );
216 }
217
218 ReadTransaction<K, V> transaction = beginReadTransaction( revision );
219
220 if ( transaction == null )
221 {
222 return new EmptyTupleCursor<K, V>();
223 }
224 else
225 {
226 ParentPos<K, V>[] stack = ( ParentPos<K, V>[] ) Array.newInstance( ParentPos.class, 32 );
227
228
229 TupleCursor<K, V> cursor = getRootPage( transaction.getRevision() ).browse( key, transaction, stack, 0 );
230
231 return cursor;
232 }
233 }
234
235
236
237
238
239 public boolean contains( K key, V value ) throws IOException
240 {
241
242 if ( transactionManager == null )
243 {
244 throw new BTreeCreationException( "We don't have a transactionLManager" );
245 }
246
247 ReadTransaction<K, V> transaction = beginReadTransaction();
248
249 if ( transaction == null )
250 {
251 return false;
252 }
253 else
254 {
255 try
256 {
257 return getRootPage( transaction.getRevision() ).contains( key, value );
258 }
259 catch ( KeyNotFoundException knfe )
260 {
261 throw new IOException( knfe.getMessage() );
262 }
263 finally
264 {
265 transaction.close();
266 }
267 }
268 }
269
270
271
272
273
274 public boolean contains( long revision, K key, V value ) throws IOException, KeyNotFoundException
275 {
276
277 if ( transactionManager == null )
278 {
279 throw new BTreeCreationException( "We don't have a transactionLManager" );
280 }
281
282
283 ReadTransaction<K, V> transaction = beginReadTransaction( revision );
284
285 if ( transaction == null )
286 {
287 return false;
288 }
289 else
290 {
291 try
292 {
293 return getRootPage( transaction.getRevision() ).contains( key, value );
294 }
295 finally
296 {
297 transaction.close();
298 }
299 }
300 }
301
302
303
304
305
306 public Tuple<K, V> delete( K key ) throws IOException
307 {
308
309 if ( transactionManager == null )
310 {
311 throw new BTreeCreationException( "We don't have a transactionLManager" );
312 }
313
314 if ( key == null )
315 {
316 throw new IllegalArgumentException( "Key must not be null" );
317 }
318
319
320 transactionManager.beginTransaction();
321
322 try
323 {
324 Tuple<K, V> deleted = delete( key, currentRevision.get() + 1 );
325
326
327 transactionManager.commit();
328
329 return deleted;
330 }
331 catch ( IOException ioe )
332 {
333
334 transactionManager.rollback();
335
336 return null;
337 }
338 }
339
340
341
342
343
344 public Tuple<K, V> delete( K key, V value ) throws IOException
345 {
346
347 if ( transactionManager == null )
348 {
349 throw new BTreeCreationException( "We don't have a transactionLManager" );
350 }
351
352 if ( key == null )
353 {
354 throw new IllegalArgumentException( "Key must not be null" );
355 }
356
357 if ( value == null )
358 {
359 throw new IllegalArgumentException( "Value must not be null" );
360 }
361
362 transactionManager.beginTransaction();
363
364 try
365 {
366 Tuple<K, V> deleted = delete( key, value, currentRevision.get() + 1 );
367
368 transactionManager.commit();
369
370 return deleted;
371 }
372 catch ( IOException ioe )
373 {
374 transactionManager.rollback();
375
376 throw ioe;
377 }
378 }
379
380
381
382
383
384
385
386
387
388 Tuple<K, V> delete( K key, long revision ) throws IOException
389 {
390 return delete( key, null, revision );
391 }
392
393
394 abstract Tuple<K, V> delete( K key, V value, long revision ) throws IOException;
395
396
397
398
399
400 public V insert( K key, V value ) throws IOException
401 {
402
403 if ( transactionManager == null )
404 {
405 throw new BTreeCreationException( "We don't have a transactionLManager" );
406 }
407
408 V existingValue = null;
409
410 if ( key == null )
411 {
412 throw new IllegalArgumentException( "Key must not be null" );
413 }
414
415
416
417 if ( btreeType != BTreeTypeEnum.PERSISTED_SUB )
418 {
419 transactionManager.beginTransaction();
420 }
421
422 try
423 {
424 InsertResult<K, V> result = insert( key, value, -1L );
425
426 if ( result instanceof ExistsResult )
427 {
428 existingValue = value;
429 }
430 else if ( result instanceof ModifyResult )
431 {
432 existingValue = ( ( ModifyResult<K, V> ) result ).getModifiedValue();
433 }
434
435
436 if ( btreeType != BTreeTypeEnum.PERSISTED_SUB )
437 {
438
439 transactionManager.commit();
440 }
441
442 return existingValue;
443 }
444 catch ( IOException ioe )
445 {
446
447
448 if ( btreeType != BTreeTypeEnum.PERSISTED_SUB )
449 {
450 transactionManager.rollback();
451 }
452
453 return null;
454 }
455 catch ( DuplicateValueNotAllowedException e )
456 {
457
458
459 if ( btreeType != BTreeTypeEnum.PERSISTED_SUB )
460 {
461 transactionManager.rollback();
462 }
463
464 throw e;
465 }
466 }
467
468
469
470
471
472 abstract InsertResult<K, V> insert( K key, V value, long revision ) throws IOException;
473
474
475
476
477
478
479 public void flush() throws IOException
480 {
481 }
482
483
484
485
486
487 public V get( K key ) throws IOException, KeyNotFoundException
488 {
489
490 if ( transactionManager == null )
491 {
492 throw new BTreeCreationException( "We don't have a transactionLManager" );
493 }
494
495 ReadTransaction<K, V> transaction = beginReadTransaction();
496
497 if ( transaction == null )
498 {
499 return null;
500 }
501 else
502 {
503 try
504 {
505 return getRootPage( transaction.getRevision() ).get( key );
506 }
507 finally
508 {
509 transaction.close();
510 }
511 }
512 }
513
514
515
516
517
518 public V get( long revision, K key ) throws IOException, KeyNotFoundException
519 {
520
521 if ( transactionManager == null )
522 {
523 throw new BTreeCreationException( "We don't have a transactionLManager" );
524 }
525
526 ReadTransaction<K, V> transaction = beginReadTransaction( revision );
527
528 if ( transaction == null )
529 {
530 return null;
531 }
532 else
533 {
534 try
535 {
536 return getRootPage( transaction.getRevision() ).get( key );
537 }
538 finally
539 {
540 transaction.close();
541 }
542 }
543 }
544
545
546
547
548
549 public abstract Page<K, V> getRootPage();
550
551
552
553
554
555 abstract void setRootPage( Page<K, V> root );
556
557
558
559
560
561 public ValueCursor<V> getValues( K key ) throws IOException, KeyNotFoundException
562 {
563
564 if ( transactionManager == null )
565 {
566 throw new BTreeCreationException( "We don't have a transactionLManager" );
567 }
568
569 ReadTransaction<K, V> transaction = beginReadTransaction();
570
571 if ( transaction == null )
572 {
573 return new EmptyValueCursor<V>( 0L );
574 }
575 else
576 {
577 try
578 {
579 return getRootPage( transaction.getRevision() ).getValues( key );
580 }
581 finally
582 {
583 transaction.close();
584 }
585 }
586 }
587
588
589
590
591
592 public boolean hasKey( K key ) throws IOException, KeyNotFoundException
593 {
594
595 if ( transactionManager == null )
596 {
597 throw new BTreeCreationException( "We don't have a transactionLManager" );
598 }
599
600 if ( key == null )
601 {
602 return false;
603 }
604
605 ReadTransaction<K, V> transaction = beginReadTransaction();
606
607 if ( transaction == null )
608 {
609 return false;
610 }
611 else
612 {
613 try
614 {
615 return getRootPage( transaction.getRevision() ).hasKey( key );
616 }
617 finally
618 {
619 transaction.close();
620 }
621 }
622 }
623
624
625
626
627
628 public boolean hasKey( long revision, K key ) throws IOException, KeyNotFoundException
629 {
630
631 if ( transactionManager == null )
632 {
633 throw new BTreeCreationException( "We don't have a transactionLManager" );
634 }
635
636 if ( key == null )
637 {
638 return false;
639 }
640
641 ReadTransaction<K, V> transaction = beginReadTransaction( revision );
642
643 if ( transaction == null )
644 {
645 return false;
646 }
647 else
648 {
649 try
650 {
651 return getRootPage( transaction.getRevision() ).hasKey( key );
652 }
653 finally
654 {
655 transaction.close();
656 }
657 }
658 }
659
660
661
662
663
664 public ElementSerializer<K> getKeySerializer()
665 {
666 return keySerializer;
667 }
668
669
670
671
672
673 public void setKeySerializer( ElementSerializer<K> keySerializer )
674 {
675 this.keySerializer = keySerializer;
676 keySerializerFQCN = keySerializer.getClass().getName();
677 }
678
679
680
681
682
683 public String getKeySerializerFQCN()
684 {
685 return keySerializerFQCN;
686 }
687
688
689
690
691
692 public ElementSerializer<V> getValueSerializer()
693 {
694 return valueSerializer;
695 }
696
697
698
699
700
701 public void setValueSerializer( ElementSerializer<V> valueSerializer )
702 {
703 this.valueSerializer = valueSerializer;
704 valueSerializerFQCN = valueSerializer.getClass().getName();
705 }
706
707
708
709
710
711 public String getValueSerializerFQCN()
712 {
713 return valueSerializerFQCN;
714 }
715
716
717
718
719
720 public long getRevision()
721 {
722
723 if ( transactionManager == null )
724 {
725 throw new BTreeCreationException( "We don't have a transactionLManager" );
726 }
727
728 ReadTransaction<K, V> transaction = beginReadTransaction();
729
730 if ( transaction == null )
731 {
732 return -1L;
733 }
734 else
735 {
736 try
737 {
738 return transaction.getRevision();
739 }
740 finally
741 {
742 transaction.close();
743 }
744 }
745 }
746
747
748
749
750
751 void setRevision( long revision )
752 {
753 transactionManager.getBTreeHeader( getName() ).setRevision( revision );
754 }
755
756
757
758
759
760 protected void storeRevision( BTreeHeader<K, V> btreeHeader, boolean keepRevisions )
761 {
762 long revision = btreeHeader.getRevision();
763
764 if ( keepRevisions )
765 {
766 synchronized ( btreeRevisions )
767 {
768 btreeRevisions.put( revision, btreeHeader );
769 }
770 }
771
772 currentRevision.set( revision );
773 currentBtreeHeader = btreeHeader;
774
775
776 if ( btreeHeader.getBtree().getType() != BTreeTypeEnum.PERSISTED_SUB )
777 {
778 transactionManager.updateNewBTreeHeaders( btreeHeader );
779 }
780 }
781
782
783
784
785
786 protected void storeRevision( BTreeHeader<K, V> btreeHeader )
787 {
788 long revision = btreeHeader.getRevision();
789
790 synchronized ( btreeRevisions )
791 {
792 btreeRevisions.put( revision, btreeHeader );
793 }
794
795 currentRevision.set( revision );
796 currentBtreeHeader = btreeHeader;
797
798
799 if ( btreeHeader.getBtree().getType() != BTreeTypeEnum.PERSISTED_SUB )
800 {
801 transactionManager.updateNewBTreeHeaders( btreeHeader );
802 }
803 }
804
805
806
807
808
809 public long getReadTimeOut()
810 {
811 return readTimeOut;
812 }
813
814
815
816
817
818 public void setReadTimeOut( long readTimeOut )
819 {
820 this.readTimeOut = readTimeOut;
821 }
822
823
824
825
826
827 public long getNbElems()
828 {
829
830 if ( transactionManager == null )
831 {
832 throw new BTreeCreationException( "We don't have a transactionLManager" );
833 }
834
835 ReadTransaction<K, V> transaction = beginReadTransaction();
836
837 if ( transaction == null )
838 {
839 return -1L;
840 }
841 else
842 {
843 try
844 {
845 return transaction.getBtreeHeader().getNbElems();
846 }
847 finally
848 {
849 transaction.close();
850 }
851 }
852 }
853
854
855
856
857
858 void setNbElems( long nbElems )
859 {
860 transactionManager.getBTreeHeader( getName() ).setNbElems( nbElems );
861 }
862
863
864
865
866
867 public int getPageSize()
868 {
869 return pageSize;
870 }
871
872
873
874
875
876 public void setPageSize( int pageSize )
877 {
878 if ( pageSize <= 2 )
879 {
880 this.pageSize = DEFAULT_PAGE_SIZE;
881 }
882 else
883 {
884 this.pageSize = getPowerOf2( pageSize );
885 }
886 }
887
888
889
890
891
892 public String getName()
893 {
894 return name;
895 }
896
897
898
899
900
901 public void setName( String name )
902 {
903 this.name = name;
904 }
905
906
907
908
909
910 public Comparator<K> getKeyComparator()
911 {
912 return keySerializer.getComparator();
913 }
914
915
916
917
918
919 public Comparator<V> getValueComparator()
920 {
921 return valueSerializer.getComparator();
922 }
923
924
925
926
927
928 public int getWriteBufferSize()
929 {
930 return writeBufferSize;
931 }
932
933
934
935
936
937 public void setWriteBufferSize( int writeBufferSize )
938 {
939 this.writeBufferSize = writeBufferSize;
940 }
941
942
943
944
945
946 public boolean isAllowDuplicates()
947 {
948 return allowDuplicates;
949 }
950
951
952
953
954
955 public void setAllowDuplicates( boolean allowDuplicates )
956 {
957 this.allowDuplicates = allowDuplicates;
958 }
959
960
961
962
963
964 public BTreeTypeEnum getType()
965 {
966 return btreeType;
967 }
968
969
970
971
972
973 public void setType( BTreeTypeEnum type )
974 {
975 this.btreeType = type;
976 }
977
978
979
980
981
982 private int getPowerOf2( int size )
983 {
984 int newSize = --size;
985 newSize |= newSize >> 1;
986 newSize |= newSize >> 2;
987 newSize |= newSize >> 4;
988 newSize |= newSize >> 8;
989 newSize |= newSize >> 16;
990 newSize++;
991
992 return newSize;
993 }
994
995
996
997
998
999 protected BTreeHeader<K, V> getBtreeHeader()
1000 {
1001 return currentBtreeHeader;
1002 }
1003
1004
1005
1006
1007
1008 protected BTreeHeader<K, V> getBtreeHeader( long revision )
1009 {
1010 return btreeRevisions.get( revision );
1011 }
1012
1013
1014
1015
1016
1017 public KeyCursor<K> browseKeys() throws IOException, KeyNotFoundException
1018 {
1019
1020 if ( transactionManager == null )
1021 {
1022 throw new BTreeCreationException( "We don't have a Transaction Manager" );
1023 }
1024
1025 ReadTransaction transaction = beginReadTransaction();
1026
1027 if ( transaction == null )
1028 {
1029 return new KeyCursor<K>();
1030 }
1031 else
1032 {
1033 ParentPos<K, K>[] stack = ( ParentPos<K, K>[] ) Array.newInstance( ParentPos.class, 32 );
1034
1035 KeyCursor<K> cursor = getRootPage().browseKeys( transaction, stack, 0 );
1036
1037
1038 cursor.beforeFirst();
1039
1040 return cursor;
1041 }
1042 }
1043
1044
1045
1046
1047
1048
1049 void createTransactionManager()
1050 {
1051 Runnable readTransactionTask = new Runnable()
1052 {
1053 public void run()
1054 {
1055 try
1056 {
1057 ReadTransaction<K, V> transaction = null;
1058
1059 while ( !Thread.currentThread().isInterrupted() )
1060 {
1061 long timeoutDate = System.currentTimeMillis() - readTimeOut;
1062 long t0 = System.currentTimeMillis();
1063 int nbTxns = 0;
1064
1065
1066 while ( ( transaction = readTransactions.peek() ) != null )
1067 {
1068 nbTxns++;
1069
1070 if ( transaction.isClosed() )
1071 {
1072
1073 readTransactions.poll();
1074 continue;
1075 }
1076
1077
1078 if ( transaction.getCreationDate() < timeoutDate )
1079 {
1080 transaction.close();
1081 readTransactions.poll();
1082
1083 synchronized ( btreeRevisions )
1084 {
1085 btreeRevisions.remove( transaction.getRevision() );
1086 }
1087
1088 continue;
1089 }
1090
1091
1092 break;
1093 }
1094
1095 long t1 = System.currentTimeMillis();
1096
1097
1098 Thread.sleep( readTimeOut );
1099 }
1100 }
1101 catch ( InterruptedException ie )
1102 {
1103
1104 }
1105 catch ( Exception e )
1106 {
1107 throw new RuntimeException( e );
1108 }
1109 }
1110 };
1111
1112 readTransactionsThread = new Thread( readTransactionTask );
1113 readTransactionsThread.setDaemon( true );
1114 readTransactionsThread.start();
1115 }
1116 }