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.memory;
21
22
23 import java.io.Closeable;
24 import java.io.EOFException;
25 import java.io.File;
26 import java.io.FileOutputStream;
27 import java.io.IOException;
28 import java.io.RandomAccessFile;
29 import java.lang.reflect.ParameterizedType;
30 import java.lang.reflect.Type;
31 import java.nio.ByteBuffer;
32 import java.nio.channels.FileChannel;
33 import java.util.Comparator;
34 import java.util.concurrent.ConcurrentLinkedQueue;
35 import java.util.concurrent.locks.ReentrantLock;
36
37 import net.sf.ehcache.Cache;
38 import net.sf.ehcache.config.CacheConfiguration;
39
40 import org.apache.directory.mavibot.btree.Addition;
41 import org.apache.directory.mavibot.btree.BTreeHeader;
42 import org.apache.directory.mavibot.btree.DeleteResult;
43 import org.apache.directory.mavibot.btree.Deletion;
44 import org.apache.directory.mavibot.btree.InsertResult;
45 import org.apache.directory.mavibot.btree.Modification;
46 import org.apache.directory.mavibot.btree.ModifyResult;
47 import org.apache.directory.mavibot.btree.NotPresentResult;
48 import org.apache.directory.mavibot.btree.Page;
49 import org.apache.directory.mavibot.btree.ParentPos;
50 import org.apache.directory.mavibot.btree.RemoveResult;
51 import org.apache.directory.mavibot.btree.SplitResult;
52 import org.apache.directory.mavibot.btree.Transaction;
53 import org.apache.directory.mavibot.btree.Tuple;
54 import org.apache.directory.mavibot.btree.TupleCursor;
55 import org.apache.directory.mavibot.btree.ValueCursor;
56 import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
57 import org.apache.directory.mavibot.btree.serializer.BufferHandler;
58 import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
59 import org.apache.directory.mavibot.btree.serializer.LongSerializer;
60 import org.slf4j.Logger;
61 import org.slf4j.LoggerFactory;
62
63
64
65
66
67
68
69
70
71
72 public class BTree<K, V> implements Closeable
73 {
74
75 protected static final Logger LOG = LoggerFactory.getLogger( BTree.class );
76
77
78 private BTreeHeader btreeHeader;
79
80
81 public static final int DEFAULT_PAGE_SIZE = 16;
82
83
84 public static final int DEFAULT_WRITE_BUFFER_SIZE = 4096 * 250;
85
86
87 public static final String DEFAULT_JOURNAL = "mavibot.log";
88
89
90 public static final String DATA_SUFFIX = ".db";
91
92
93 public static final String JOURNAL_SUFFIX = ".log";
94
95
96 protected volatile Page<K, V> rootPage;
97
98
99 private ConcurrentLinkedQueue<Transaction<K, V>> readTransactions;
100
101
102 private int writeBufferSize;
103
104
105 protected Class<?> keyType;
106
107
108 private ElementSerializer<K> keySerializer;
109
110
111 private ElementSerializer<V> valueSerializer;
112
113
114 private File file;
115
116
117 private BTreeTypeEnum type;
118
119
120 private boolean withJournal;
121
122
123 private File journal;
124
125
126 private ReentrantLock writeLock;
127
128
129 private Thread readTransactionsThread;
130
131
132 public static final long DEFAULT_READ_TIMEOUT = 10 * 1000L;
133
134
135 private long readTimeOut = DEFAULT_READ_TIMEOUT;
136
137 private File envDir;
138
139 private FileChannel journalChannel = null;
140
141
142 private Cache cache;
143
144
145 private int cacheSize = DEFAULT_CACHE_SIZE;
146
147
148 private static final int DEFAULT_CACHE_SIZE = 1000;
149
150
151
152
153
154
155 private void createTransactionManager()
156 {
157 Runnable readTransactionTask = new Runnable()
158 {
159 public void run()
160 {
161 try
162 {
163 Transaction<K, V> transaction = null;
164
165 while ( !Thread.currentThread().isInterrupted() )
166 {
167 long timeoutDate = System.currentTimeMillis() - readTimeOut;
168 long t0 = System.currentTimeMillis();
169 int nbTxns = 0;
170
171
172 while ( ( transaction = readTransactions.peek() ) != null )
173 {
174 nbTxns++;
175
176 if ( transaction.isClosed() )
177 {
178
179 readTransactions.poll();
180 continue;
181 }
182
183
184 if ( transaction.getCreationDate() < timeoutDate )
185 {
186 transaction.close();
187 readTransactions.poll();
188 continue;
189 }
190
191
192 break;
193 }
194
195 long t1 = System.currentTimeMillis();
196
197 if ( nbTxns > 0 )
198 {
199 System.out.println( "Processing old txn : " + nbTxns + ", " + ( t1 - t0 ) + "ms" );
200 }
201
202
203 Thread.sleep( readTimeOut );
204 }
205 }
206 catch ( InterruptedException ie )
207 {
208
209 }
210 catch ( Exception e )
211 {
212 throw new RuntimeException( e );
213 }
214 }
215 };
216
217 readTransactionsThread = new Thread( readTransactionTask );
218 readTransactionsThread.setDaemon( true );
219 readTransactionsThread.start();
220 }
221
222
223
224
225
226 public BTree()
227 {
228 btreeHeader = new BTreeHeader();
229 type = BTreeTypeEnum.IN_MEMORY;
230 }
231
232
233
234
235
236
237
238
239 public BTree( BTreeConfiguration<K, V> configuration ) throws IOException
240 {
241 String name = configuration.getName();
242
243 if ( name == null )
244 {
245 throw new IllegalArgumentException( "BTree name cannot be null" );
246 }
247
248 String filePath = configuration.getFilePath();
249
250 if ( filePath != null )
251 {
252 envDir = new File( filePath );
253 }
254
255 btreeHeader = new BTreeHeader();
256 btreeHeader.setName( name );
257 btreeHeader.setPageSize( configuration.getPageSize() );
258
259 keySerializer = configuration.getKeySerializer();
260 btreeHeader.setKeySerializerFQCN( keySerializer.getClass().getName() );
261
262 valueSerializer = configuration.getValueSerializer();
263 btreeHeader.setValueSerializerFQCN( valueSerializer.getClass().getName() );
264
265 readTimeOut = configuration.getReadTimeOut();
266 writeBufferSize = configuration.getWriteBufferSize();
267 btreeHeader.setAllowDuplicates( configuration.isAllowDuplicates() );
268 type = configuration.getType();
269 cacheSize = configuration.getCacheSize();
270
271 if ( keySerializer.getComparator() == null )
272 {
273 throw new IllegalArgumentException( "Comparator should not be null" );
274 }
275
276
277
278 rootPage = new Leaf<K, V>( this );
279
280
281 init();
282 }
283
284
285
286
287
288
289
290 public BTree( String name, ElementSerializer<K> keySerializer, ElementSerializer<V> valueSerializer )
291 throws IOException
292 {
293 this( name, keySerializer, valueSerializer, false );
294 }
295
296
297 public BTree( String name, ElementSerializer<K> keySerializer, ElementSerializer<V> valueSerializer,
298 boolean allowDuplicates )
299 throws IOException
300 {
301 this( name, null, keySerializer, valueSerializer, DEFAULT_PAGE_SIZE, allowDuplicates, DEFAULT_CACHE_SIZE );
302 }
303
304
305
306
307
308
309
310 public BTree( String name, ElementSerializer<K> keySerializer, ElementSerializer<V> valueSerializer, int pageSize )
311 throws IOException
312 {
313 this( name, null, keySerializer, valueSerializer, pageSize );
314 }
315
316
317
318
319
320
321
322 public BTree( String name, String path, ElementSerializer<K> keySerializer, ElementSerializer<V> valueSerializer )
323 throws IOException
324 {
325 this( name, path, keySerializer, valueSerializer, DEFAULT_PAGE_SIZE );
326 }
327
328
329
330
331
332
333
334
335
336
337
338
339
340 public BTree( String name, String dataDir, ElementSerializer<K> keySerializer,
341 ElementSerializer<V> valueSerializer,
342 int pageSize )
343 throws IOException
344 {
345 this( name, dataDir, keySerializer, valueSerializer, pageSize, false, DEFAULT_CACHE_SIZE );
346 }
347
348
349 public BTree( String name, String dataDir, ElementSerializer<K> keySerializer,
350 ElementSerializer<V> valueSerializer,
351 int pageSize, boolean allowDuplicates )
352 throws IOException
353 {
354 this( name, dataDir, keySerializer, valueSerializer, pageSize, allowDuplicates, DEFAULT_CACHE_SIZE );
355 }
356
357
358 public BTree( String name, String dataDir, ElementSerializer<K> keySerializer,
359 ElementSerializer<V> valueSerializer,
360 int pageSize, boolean allowDuplicates, int cacheSize )
361 throws IOException
362 {
363 btreeHeader = new BTreeHeader();
364 btreeHeader.setName( name );
365
366 if ( dataDir != null )
367 {
368 envDir = new File( dataDir );
369 }
370
371 setPageSize( pageSize );
372 writeBufferSize = DEFAULT_WRITE_BUFFER_SIZE;
373
374 this.cacheSize = cacheSize;
375
376 this.keySerializer = keySerializer;
377
378 btreeHeader.setKeySerializerFQCN( keySerializer.getClass().getName() );
379
380 this.valueSerializer = valueSerializer;
381
382 btreeHeader.setValueSerializerFQCN( valueSerializer.getClass().getName() );
383
384 btreeHeader.setAllowDuplicates( allowDuplicates );
385
386
387
388 rootPage = new Leaf<K, V>( this );
389
390
391 init();
392 }
393
394
395
396
397
398
399
400 public void init() throws IOException
401 {
402
403 if ( envDir != null )
404 {
405 if ( !envDir.exists() )
406 {
407 boolean created = envDir.mkdirs();
408 if ( !created )
409 {
410 throw new IllegalStateException( "Could not create the directory " + envDir + " for storing data" );
411 }
412 }
413
414 this.file = new File( envDir, btreeHeader.getName() + DATA_SUFFIX );
415
416 this.journal = new File( envDir, file.getName() + JOURNAL_SUFFIX );
417 type = BTreeTypeEnum.PERSISTENT;
418 }
419
420
421 readTransactions = new ConcurrentLinkedQueue<Transaction<K, V>>();
422
423
424 Class<?> comparatorClass = keySerializer.getComparator().getClass();
425 Type[] types = comparatorClass.getGenericInterfaces();
426
427 if ( types[0] instanceof Class )
428 {
429 keyType = ( Class<?> ) types[0];
430 }
431 else
432 {
433 Type[] argumentTypes = ( ( ParameterizedType ) types[0] ).getActualTypeArguments();
434
435 if ( ( argumentTypes != null ) && ( argumentTypes.length > 0 ) && ( argumentTypes[0] instanceof Class<?> ) )
436 {
437 keyType = ( Class<?> ) argumentTypes[0];
438 }
439 }
440
441 writeLock = new ReentrantLock();
442
443
444
445 if ( type == BTreeTypeEnum.PERSISTENT )
446 {
447 if ( file.length() > 0 )
448 {
449
450 load( file );
451 }
452
453 withJournal = true;
454
455 FileOutputStream stream = new FileOutputStream( journal );
456 journalChannel = stream.getChannel();
457
458
459
460 if ( journal.length() > 0 )
461 {
462 applyJournal();
463 }
464 }
465 else if ( type == null )
466 {
467 type = BTreeTypeEnum.IN_MEMORY;
468 }
469
470
471 CacheConfiguration cacheConfiguration = new CacheConfiguration();
472 cacheConfiguration.setName( "pages" );
473 cacheConfiguration.setEternal( true );
474 cacheConfiguration.setOverflowToDisk( false );
475 cacheConfiguration.setCacheLoaderTimeoutMillis( 0 );
476 cacheConfiguration.setMaxElementsInMemory( cacheSize );
477 cacheConfiguration.setMemoryStoreEvictionPolicy( "LRU" );
478
479 cache = new Cache( cacheConfiguration );
480 cache.initialise();
481
482
483
484
485 }
486
487
488
489
490
491
492 {
493 return cache;
494 }
495
496
497
498
499
500 public void close() throws IOException
501 {
502
503
504
505
506 if ( type == BTreeTypeEnum.PERSISTENT )
507 {
508
509 flush();
510 journalChannel.close();
511 }
512
513 rootPage = null;
514 }
515
516
517
518
519
520
521 {
522 return btreeHeader.getBTreeOffset();
523 }
524
525
526
527
528
529
530 {
531 btreeHeader.setBTreeOffset( btreeOffset );
532 }
533
534
535
536
537
538
539 {
540 return btreeHeader.getRootPageOffset();
541 }
542
543
544
545
546
547
548 {
549 btreeHeader.setRootPageOffset( rootPageOffset );
550 }
551
552
553
554
555
556
557 {
558 return btreeHeader.getNextBTreeOffset();
559 }
560
561
562
563
564
565
566 {
567 btreeHeader.setNextBTreeOffset( nextBTreeOffset );
568 }
569
570
571
572
573
574 private int getPowerOf2( int size )
575 {
576 int newSize = --size;
577 newSize |= newSize >> 1;
578 newSize |= newSize >> 2;
579 newSize |= newSize >> 4;
580 newSize |= newSize >> 8;
581 newSize |= newSize >> 16;
582 newSize++;
583
584 return newSize;
585 }
586
587
588
589
590
591
592
593
594
595
596
597
598 public void setPageSize( int pageSize )
599 {
600 if ( pageSize <= 2 )
601 {
602 btreeHeader.setPageSize( DEFAULT_PAGE_SIZE );
603 }
604 else
605 {
606 btreeHeader.setPageSize( getPowerOf2( pageSize ) );
607 }
608 }
609
610
611
612
613
614
615
616
617
618 {
619 rootPage = root;
620 }
621
622
623
624
625
626 public int getPageSize()
627 {
628 return btreeHeader.getPageSize();
629 }
630
631
632
633
634
635
636
637
638 long generateRevision()
639 {
640 return btreeHeader.incrementRevision();
641 }
642
643
644
645
646
647
648
649
650
651
652
653
654
655 public V insert( K key, V value ) throws IOException
656 {
657 long revision = generateRevision();
658
659 V existingValue = null;
660
661 try
662 {
663
664 writeLock.lock();
665
666 InsertResult<K, V> result = insert( key, value, revision );
667
668 if ( result instanceof ModifyResult )
669 {
670 existingValue = ( (org.apache.directory.mavibot.btree.ModifyResult<K, V> ) result ).getModifiedValue();
671 }
672 }
673 finally
674 {
675
676 writeLock.unlock();
677 }
678
679 return existingValue;
680 }
681
682
683
684
685
686
687
688
689
690 public Tuple<K, V> delete( K key ) throws IOException
691 {
692 if ( key == null )
693 {
694 throw new IllegalArgumentException( "Key must not be null" );
695 }
696
697 long revision = generateRevision();
698
699 Tuple<K, V> deleted = delete( key, revision );
700
701 return deleted;
702 }
703
704
705
706
707
708
709
710
711
712
713
714
715 public Tuple<K, V> delete( K key, V value ) throws IOException
716 {
717 if ( key == null )
718 {
719 throw new IllegalArgumentException( "Key must not be null" );
720 }
721
722 if ( value == null )
723 {
724 throw new IllegalArgumentException( "Value must not be null" );
725 }
726
727 long revision = generateRevision();
728
729 Tuple<K, V> deleted = delete( key, value, revision );
730
731 return deleted;
732 }
733
734
735
736
737
738
739
740
741
742 private Tuple<K, V> delete( K key, long revision ) throws IOException
743 {
744 return delete( key, null, revision );
745 }
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760 private Tuple<K, V> delete( K key, V value, long revision ) throws IOException
761 {
762 writeLock.lock();
763
764 try
765 {
766
767
768 Tuple<K, V> tuple = null;
769
770
771
772 DeleteResult<K, V> result = rootPage.delete( revision, key, value, null, -1 );
773
774 if ( result instanceof NotPresentResult )
775 {
776
777 return null;
778 }
779
780
781 Page<K, V> oldRootPage = rootPage;
782
783 if ( result instanceof RemoveResult )
784 {
785
786 RemoveResult<K, V> removeResult = (org.apache.directory.mavibot.btree.RemoveResult<K, V> ) result;
787
788 Page<K, V> modifiedPage = removeResult.getModifiedPage();
789
790
791 rootPage = modifiedPage;
792 tuple = removeResult.getRemovedElement();
793 }
794
795 if ( withJournal )
796 {
797
798 writeToJournal( new Deletion<K, V>( key ) );
799 }
800
801
802 if ( tuple != null )
803 {
804 btreeHeader.decrementNbElems();
805 }
806
807
808 return tuple;
809 }
810 finally
811 {
812
813 writeLock.unlock();
814 }
815 }
816
817
818
819
820
821
822
823
824
825
826
827
828 public V get( K key ) throws IOException, KeyNotFoundException
829 {
830 return rootPage.get( key );
831 }
832
833
834
835
836
837 public ValueCursor<V> getValues( K key ) throws IOException, KeyNotFoundException
838 {
839 return rootPage.getValues( key );
840 }
841
842
843
844
845
846
847
848
849
850
851
852
853
854 public V get( long revision, K key ) throws IOException, KeyNotFoundException
855 {
856
857 Page<K, V> revisionRootPage = getRootPage( revision );
858
859 return revisionRootPage.get( key );
860 }
861
862
863
864
865
866
867
868
869
870 public boolean hasKey( K key ) throws IOException
871 {
872 if ( key == null )
873 {
874 return false;
875 }
876
877 return rootPage.hasKey( key );
878 }
879
880
881
882
883
884
885
886
887
888
889
890 public boolean hasKey( long revision, K key ) throws IOException, KeyNotFoundException
891 {
892 if ( key == null )
893 {
894 return false;
895 }
896
897
898 Page<K, V> revisionRootPage = getRootPage( revision );
899
900 return revisionRootPage.hasKey( key );
901 }
902
903
904
905
906
907
908
909
910
911 public boolean contains( K key, V value ) throws IOException
912 {
913 return rootPage.contains( key, value );
914 }
915
916
917
918
919
920
921
922
923
924
925
926 public boolean contains( long revision, K key, V value ) throws IOException, KeyNotFoundException
927 {
928
929 Page<K, V> revisionRootPage = getRootPage( revision );
930
931 return revisionRootPage.contains( key, value );
932 }
933
934
935
936
937
938
939
940
941 public TupleCursor<K, V> browse() throws IOException
942 {
943 Transaction<K, V> transaction = beginReadTransaction();
944
945
946 TupleCursor<K, V> cursor = rootPage.browse( transaction, new ParentPos[32], 0 );
947
948
949 cursor.beforeFirst();
950
951 return cursor;
952 }
953
954
955
956
957
958
959
960
961
962
963 public TupleCursor<K, V> browse( long revision ) throws IOException, KeyNotFoundException
964 {
965 Transaction<K, V> transaction = beginReadTransaction();
966
967
968 Page<K, V> revisionRootPage = getRootPage( revision );
969
970
971 TupleCursor<K, V> cursor = revisionRootPage.browse( transaction, new ParentPos[32], 0 );
972
973 return cursor;
974 }
975
976
977
978
979
980
981
982
983
984
985 public TupleCursor<K, V> browseFrom( K key ) throws IOException
986 {
987 Transaction<K, V> transaction = beginReadTransaction();
988
989
990 TupleCursor<K, V> cursor = rootPage.browse( key, transaction, new ParentPos[32], 0 );
991
992 return cursor;
993 }
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006 public TupleCursor<K, V> browseFrom( long revision, K key ) throws IOException, KeyNotFoundException
1007 {
1008 Transaction<K, V> transaction = beginReadTransaction();
1009
1010
1011 Page<K, V> revisionRootPage = getRootPage( revision );
1012
1013
1014 TupleCursor<K, V> cursor = revisionRootPage.browse( key, transaction, new ParentPos[32], 0 );
1015
1016 return cursor;
1017 }
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034 {
1035 if ( key == null )
1036 {
1037 throw new IllegalArgumentException( "Key must not be null" );
1038 }
1039
1040
1041
1042 V modifiedValue = null;
1043
1044
1045
1046
1047 InsertResult<K, V> result = rootPage.insert( revision, key, value );
1048
1049 if ( result instanceof ModifyResult )
1050 {
1051 ModifyResult<K, V> modifyResult = ( (org.apache.directory.mavibot.btree.ModifyResult<K, V> ) result );
1052
1053 Page<K, V> modifiedPage = modifyResult.getModifiedPage();
1054
1055
1056
1057 rootPage = modifiedPage;
1058
1059 modifiedValue = modifyResult.getModifiedValue();
1060 }
1061 else
1062 {
1063
1064
1065 SplitResult<K, V> splitResult = ( (org.apache.directory.mavibot.btree.SplitResult<K, V> ) result );
1066
1067 K pivot = splitResult.getPivot();
1068 Page<K, V> leftPage = splitResult.getLeftPage();
1069 Page<K, V> rightPage = splitResult.getRightPage();
1070 Page<K, V> newRootPage = null;
1071
1072
1073 newRootPage = new Node<K, V>( this, revision, pivot, leftPage, rightPage );
1074
1075 rootPage = newRootPage;
1076 }
1077
1078
1079 if ( withJournal )
1080 {
1081 writeToJournal( new Addition<K, V>( key, value ) );
1082 }
1083
1084
1085
1086 if ( modifiedValue == null )
1087 {
1088 btreeHeader.incrementNbElems();
1089 }
1090
1091
1092 return result;
1093 }
1094
1095
1096
1097
1098
1099
1100
1101 private Transaction<K, V> beginReadTransaction()
1102 {
1103 Transaction<K, V> readTransaction = new Transaction<K, V>( rootPage, btreeHeader.getRevision() - 1,
1104 System.currentTimeMillis() );
1105
1106 readTransactions.add( readTransaction );
1107
1108 return readTransaction;
1109 }
1110
1111
1112
1113
1114
1115
1116 {
1117 return keyType;
1118 }
1119
1120
1121
1122
1123
1124 public Comparator<K> getComparator()
1125 {
1126 return keySerializer.getComparator();
1127 }
1128
1129
1130
1131
1132
1133 public void setKeySerializer( ElementSerializer<K> keySerializer )
1134 {
1135 this.keySerializer = keySerializer;
1136 btreeHeader.setKeySerializerFQCN( keySerializer.getClass().getName() );
1137 }
1138
1139
1140
1141
1142
1143 public void setValueSerializer( ElementSerializer<V> valueSerializer )
1144 {
1145 this.valueSerializer = valueSerializer;
1146 btreeHeader.setValueSerializerFQCN( valueSerializer.getClass().getName() );
1147 }
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158 private void writeBuffer( FileChannel channel, ByteBuffer bb, byte[] buffer ) throws IOException
1159 {
1160 int size = buffer.length;
1161 int pos = 0;
1162
1163
1164 do
1165 {
1166 if ( bb.remaining() >= size )
1167 {
1168
1169 bb.put( buffer, pos, size );
1170 size = 0;
1171 }
1172 else
1173 {
1174
1175 int len = bb.remaining();
1176 size -= len;
1177 bb.put( buffer, pos, len );
1178 pos += len;
1179
1180 bb.flip();
1181
1182 channel.write( bb );
1183
1184 bb.clear();
1185 }
1186 }
1187 while ( size > 0 );
1188 }
1189
1190
1191
1192
1193
1194
1195 public void flush( File file ) throws IOException
1196 {
1197 File parentFile = file.getParentFile();
1198 File baseDirectory = null;
1199
1200 if ( parentFile != null )
1201 {
1202 baseDirectory = new File( file.getParentFile().getAbsolutePath() );
1203 }
1204 else
1205 {
1206 baseDirectory = new File( "." );
1207 }
1208
1209
1210 File tmpFileFD = File.createTempFile( "mavibot", null, baseDirectory );
1211 FileOutputStream stream = new FileOutputStream( tmpFileFD );
1212 FileChannel ch = stream.getChannel();
1213
1214
1215 ByteBuffer bb = ByteBuffer.allocateDirect( writeBufferSize );
1216
1217 TupleCursor<K, V> cursor = browse();
1218
1219 if ( keySerializer == null )
1220 {
1221 throw new RuntimeException( "Cannot flush the btree without a Key serializer" );
1222 }
1223
1224 if ( valueSerializer == null )
1225 {
1226 throw new RuntimeException( "Cannot flush the btree without a Value serializer" );
1227 }
1228
1229
1230 bb.putLong( btreeHeader.getNbElems() );
1231
1232 while ( cursor.hasNext() )
1233 {
1234 Tuple<K, V> tuple = cursor.next();
1235
1236 byte[] keyBuffer = keySerializer.serialize( tuple.getKey() );
1237
1238 writeBuffer( ch, bb, keyBuffer );
1239
1240 byte[] valueBuffer = valueSerializer.serialize( tuple.getValue() );
1241
1242 writeBuffer( ch, bb, valueBuffer );
1243 }
1244
1245
1246 if ( bb.position() > 0 )
1247 {
1248 bb.flip();
1249 ch.write( bb );
1250 }
1251
1252
1253 ch.force( true );
1254 ch.close();
1255
1256
1257 File backupFile = File.createTempFile( "mavibot", null, baseDirectory );
1258 file.renameTo( backupFile );
1259
1260
1261 tmpFileFD.renameTo( file );
1262
1263
1264 backupFile.delete();
1265 }
1266
1267
1268
1269
1270
1271
1272
1273 private void applyJournal() throws IOException
1274 {
1275 long revision = generateRevision();
1276
1277 if ( !journal.exists() )
1278 {
1279 throw new IOException( "The journal does not exist" );
1280 }
1281
1282 FileChannel channel =
1283 new RandomAccessFile( journal, "rw" ).getChannel();
1284 ByteBuffer buffer = ByteBuffer.allocate( 65536 );
1285
1286 BufferHandler bufferHandler = new BufferHandler( channel, buffer );
1287
1288
1289 try
1290 {
1291 while ( true )
1292 {
1293
1294 byte[] type = bufferHandler.read( 1 );
1295
1296 if ( type[0] == Modification.ADDITION )
1297 {
1298
1299 K key = keySerializer.deserialize( bufferHandler );
1300
1301
1302
1303
1304 V value = valueSerializer.deserialize( bufferHandler );
1305
1306
1307
1308
1309 insert( key, value, revision );
1310 }
1311 else
1312 {
1313
1314 K key = keySerializer.deserialize( bufferHandler );
1315
1316
1317 delete( key, revision );
1318 }
1319 }
1320 }
1321 catch ( EOFException eofe )
1322 {
1323 eofe.printStackTrace();
1324
1325 journalChannel.truncate( 0 );
1326 }
1327 }
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337 public void load( File file ) throws IOException
1338 {
1339 long revision = generateRevision();
1340
1341 if ( !file.exists() )
1342 {
1343 throw new IOException( "The file does not exist" );
1344 }
1345
1346 FileChannel channel =
1347 new RandomAccessFile( file, "rw" ).getChannel();
1348 ByteBuffer buffer = ByteBuffer.allocate( 65536 );
1349
1350 BufferHandler bufferHandler = new BufferHandler( channel, buffer );
1351
1352 long nbElems = LongSerializer.deserialize( bufferHandler.read( 8 ) );
1353 btreeHeader.setNbElems( nbElems );
1354
1355
1356
1357
1358
1359
1360 boolean isJournalActivated = withJournal;
1361
1362 withJournal = false;
1363
1364
1365 for ( long i = 0; i < nbElems; i++ )
1366 {
1367
1368 K key = keySerializer.deserialize( bufferHandler );
1369
1370
1371
1372
1373 V value = valueSerializer.deserialize( bufferHandler );
1374
1375
1376
1377
1378 insert( key, value, revision );
1379 }
1380
1381
1382 withJournal = isJournalActivated;
1383
1384
1385
1386 }
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397 private Page<K, V> getRootPage( long revision ) throws IOException, KeyNotFoundException
1398 {
1399
1400 return rootPage;
1401 }
1402
1403
1404
1405
1406
1407
1408 public void flush() throws IOException
1409 {
1410 if ( type == BTreeTypeEnum.PERSISTENT )
1411 {
1412
1413 flush( file );
1414 journalChannel.truncate( 0 );
1415 }
1416 }
1417
1418
1419
1420
1421
1422 public long getReadTimeOut()
1423 {
1424 return readTimeOut;
1425 }
1426
1427
1428
1429
1430
1431 public void setReadTimeOut( long readTimeOut )
1432 {
1433 this.readTimeOut = readTimeOut;
1434 }
1435
1436
1437
1438
1439
1440 public String getName()
1441 {
1442 return btreeHeader.getName();
1443 }
1444
1445
1446
1447
1448
1449 public void setName( String name )
1450 {
1451 btreeHeader.setName( name );
1452 }
1453
1454
1455
1456
1457
1458 public File getFile()
1459 {
1460 return file;
1461 }
1462
1463
1464
1465
1466
1467 public File getJournal()
1468 {
1469 return journal;
1470 }
1471
1472
1473
1474
1475
1476 public int getWriteBufferSize()
1477 {
1478 return writeBufferSize;
1479 }
1480
1481
1482
1483
1484
1485 public void setWriteBufferSize( int writeBufferSize )
1486 {
1487 this.writeBufferSize = writeBufferSize;
1488 }
1489
1490
1491
1492
1493
1494 public boolean isInMemory()
1495 {
1496 return type == BTreeTypeEnum.IN_MEMORY;
1497 }
1498
1499
1500
1501
1502
1503 public boolean isPersistent()
1504 {
1505 return type == BTreeTypeEnum.IN_MEMORY;
1506 }
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516 {
1517 return new ValueHolder<V>( this, value );
1518 }
1519
1520
1521
1522
1523
1524 public ElementSerializer<K> getKeySerializer()
1525 {
1526 return keySerializer;
1527 }
1528
1529
1530
1531
1532
1533 public String getKeySerializerFQCN()
1534 {
1535 return btreeHeader.getKeySerializerFQCN();
1536 }
1537
1538
1539
1540
1541
1542 public ElementSerializer<V> getValueSerializer()
1543 {
1544 return valueSerializer;
1545 }
1546
1547
1548
1549
1550
1551 public String getValueSerializerFQCN()
1552 {
1553 return btreeHeader.getValueSerializerFQCN();
1554 }
1555
1556
1557
1558
1559
1560 public long getRevision()
1561 {
1562 return btreeHeader.getRevision();
1563 }
1564
1565
1566
1567
1568
1569
1570 {
1571 btreeHeader.setRevision( revision );
1572 }
1573
1574
1575
1576
1577
1578 public long getNbElems()
1579 {
1580 return btreeHeader.getNbElems();
1581 }
1582
1583
1584
1585
1586
1587
1588 {
1589 btreeHeader.setNbElems( nbElems );
1590 }
1591
1592
1593
1594
1595
1596 public boolean isAllowDuplicates()
1597 {
1598 return btreeHeader.isAllowDuplicates();
1599 }
1600
1601
1602
1603 {
1604 btreeHeader.setAllowDuplicates( allowDuplicates );
1605 }
1606
1607
1608 private void writeToJournal( Modification<K, V> modification )
1609 throws IOException
1610 {
1611 if ( modification instanceof Addition )
1612 {
1613 byte[] keyBuffer = keySerializer.serialize( modification.getKey() );
1614 ByteBuffer bb = ByteBuffer.allocateDirect( keyBuffer.length + 1 );
1615 bb.put( Modification.ADDITION );
1616 bb.put( keyBuffer );
1617 bb.flip();
1618
1619 journalChannel.write( bb );
1620
1621 byte[] valueBuffer = valueSerializer.serialize( modification.getValue() );
1622 bb = ByteBuffer.allocateDirect( valueBuffer.length );
1623 bb.put( valueBuffer );
1624 bb.flip();
1625
1626 journalChannel.write( bb );
1627 }
1628 else if ( modification instanceof Deletion )
1629 {
1630 byte[] keyBuffer = keySerializer.serialize( modification.getKey() );
1631 ByteBuffer bb = ByteBuffer.allocateDirect( keyBuffer.length + 1 );
1632 bb.put( Modification.DELETION );
1633 bb.put( keyBuffer );
1634 bb.flip();
1635
1636 journalChannel.write( bb );
1637 }
1638
1639
1640 journalChannel.force( true );
1641 }
1642
1643
1644
1645
1646
1647 public String toString()
1648 {
1649 StringBuilder sb = new StringBuilder();
1650
1651 switch ( type )
1652 {
1653 case IN_MEMORY:
1654 sb.append( "In-memory " );
1655 break;
1656
1657 case PERSISTENT:
1658 sb.append( "Persistent " );
1659 break;
1660
1661 }
1662
1663 sb.append( "BTree" );
1664 sb.append( "[" ).append( btreeHeader.getName() ).append( "]" );
1665 sb.append( "( pageSize:" ).append( btreeHeader.getPageSize() );
1666
1667 if ( rootPage != null )
1668 {
1669 sb.append( ", nbEntries:" ).append( btreeHeader.getNbElems() );
1670 }
1671 else
1672 {
1673 sb.append( ", nbEntries:" ).append( 0 );
1674 }
1675
1676 sb.append( ", comparator:" );
1677
1678 if ( keySerializer.getComparator() == null )
1679 {
1680 sb.append( "null" );
1681 }
1682 else
1683 {
1684 sb.append( keySerializer.getComparator().getClass().getSimpleName() );
1685 }
1686
1687 sb.append( ", DuplicatesAllowed: " ).append( btreeHeader.isAllowDuplicates() );
1688
1689 if ( type == BTreeTypeEnum.PERSISTENT )
1690 {
1691 try
1692 {
1693 sb.append( ", file : " );
1694
1695 if ( file != null )
1696 {
1697 sb.append( file.getCanonicalPath() );
1698 }
1699 else
1700 {
1701 sb.append( "Unknown" );
1702 }
1703
1704 sb.append( ", journal : " );
1705
1706 if ( journal != null )
1707 {
1708 sb.append( journal.getCanonicalPath() );
1709 }
1710 else
1711 {
1712 sb.append( "Unkown" );
1713 }
1714 }
1715 catch ( IOException ioe )
1716 {
1717
1718 }
1719 }
1720
1721 sb.append( ") : \n" );
1722 sb.append( rootPage.dumpPage( "" ) );
1723
1724 return sb.toString();
1725 }
1726 }