View Javadoc

1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  You may obtain a copy of the License at
9    *
10   *    http://www.apache.org/licenses/LICENSE-2.0
11   *
12   *  Unless required by applicable law or agreed to in writing,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License.
18   *
19   */
20  package org.apache.directory.mavibot.btree.managed;
21  
22  
23  import static org.junit.Assert.assertEquals;
24  import static org.junit.Assert.assertFalse;
25  import static org.junit.Assert.assertNotNull;
26  import static org.junit.Assert.assertTrue;
27  import static org.junit.Assert.fail;
28  
29  import java.io.File;
30  import java.io.IOException;
31  import java.util.ArrayList;
32  import java.util.HashSet;
33  import java.util.List;
34  import java.util.Set;
35  import java.util.UUID;
36  
37  import org.apache.directory.mavibot.btree.Tuple;
38  import org.apache.directory.mavibot.btree.TupleCursor;
39  import org.apache.directory.mavibot.btree.ValueCursor;
40  import org.apache.directory.mavibot.btree.exception.BTreeAlreadyManagedException;
41  import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
42  import org.apache.directory.mavibot.btree.serializer.LongSerializer;
43  import org.apache.directory.mavibot.btree.serializer.StringSerializer;
44  import org.junit.Before;
45  import org.junit.Ignore;
46  import org.junit.Rule;
47  import org.junit.Test;
48  import org.junit.rules.TemporaryFolder;
49  
50  
51  /**
52   * test the RecordManager
53   * 
54   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
55   */
56  public class RecordManagerTest
57  {
58      private BTree<Long, String> btree = null;
59  
60      private RecordManager recordManager1 = null;
61  
62      @Rule
63      public TemporaryFolder tempFolder = new TemporaryFolder();
64  
65      private File dataDir = null;
66  
67  
68      @Before
69      public void createBTree()
70      {
71          dataDir = tempFolder.newFolder( UUID.randomUUID().toString() );
72  
73          openRecordManagerAndBtree();
74  
75          try
76          {
77              // Create a new BTree
78              btree = recordManager1.addBTree( "test", new LongSerializer(), new StringSerializer(), false );
79          }
80          catch ( Exception e )
81          {
82              throw new RuntimeException( e );
83          }
84      }
85  
86  
87      private void openRecordManagerAndBtree()
88      {
89          try
90          {
91              if ( recordManager1 != null )
92              {
93                  recordManager1.close();
94              }
95  
96              // Now, try to reload the file back
97              recordManager1 = new RecordManager( dataDir.getAbsolutePath() );
98  
99              // load the last created btree
100             if ( btree != null )
101             {
102                 btree = recordManager1.getManagedTree( btree.getName() );
103             }
104         }
105         catch ( Exception e )
106         {
107             throw new RuntimeException( e );
108         }
109     }
110 
111 
112     /**
113      * Test the creation of a RecordManager, and that we can read it back.  
114      */
115     @Test
116     public void testRecordManager() throws IOException, BTreeAlreadyManagedException
117     {
118         assertEquals( 1, recordManager1.getNbManagedTrees() );
119 
120         Set<String> managedBTrees = recordManager1.getManagedTrees();
121 
122         assertEquals( 1, managedBTrees.size() );
123         assertTrue( managedBTrees.contains( "test" ) );
124 
125         BTree<Long, String> btree1 = recordManager1.getManagedTree( "test" );
126 
127         assertNotNull( btree1 );
128         assertEquals( btree.getComparator().getClass().getName(), btree1.getComparator().getClass().getName() );
129         assertEquals( btree.getKeySerializer().getClass().getName(), btree1.getKeySerializer().getClass().getName() );
130         assertEquals( btree.getName(), btree1.getName() );
131         assertEquals( btree.getNbElems(), btree1.getNbElems() );
132         assertEquals( btree.getPageSize(), btree1.getPageSize() );
133         assertEquals( btree.getRevision(), btree1.getRevision() );
134         assertEquals( btree.getValueSerializer().getClass().getName(), btree1.getValueSerializer().getClass().getName() );
135     }
136 
137 
138     /**
139      * Test the creation of a RecordManager with a BTree containing data.
140      */
141     @Test
142     public void testRecordManagerWithBTree() throws IOException, BTreeAlreadyManagedException, KeyNotFoundException
143     {
144         // Now, add some elements in the BTree
145         btree.insert( 3L, "V3" );
146         btree.insert( 1L, "V1" );
147         btree.insert( 5L, "V5" );
148 
149         // Now, try to reload the file back
150         openRecordManagerAndBtree();
151 
152         assertEquals( 1, recordManager1.getNbManagedTrees() );
153 
154         Set<String> managedBTrees = recordManager1.getManagedTrees();
155 
156         assertEquals( 1, managedBTrees.size() );
157         assertTrue( managedBTrees.contains( "test" ) );
158 
159         BTree<Long, String> btree1 = recordManager1.getManagedTree( "test" );
160 
161         assertNotNull( btree1 );
162         assertEquals( btree.getComparator().getClass().getName(), btree1.getComparator().getClass().getName() );
163         assertEquals( btree.getKeySerializer().getClass().getName(), btree1.getKeySerializer().getClass().getName() );
164         assertEquals( btree.getName(), btree1.getName() );
165         assertEquals( btree.getNbElems(), btree1.getNbElems() );
166         assertEquals( btree.getPageSize(), btree1.getPageSize() );
167         assertEquals( btree.getRevision(), btree1.getRevision() );
168         assertEquals( btree.getValueSerializer().getClass().getName(), btree1.getValueSerializer().getClass().getName() );
169 
170         // Check the stored element
171         assertTrue( btree1.hasKey( 1L ) );
172         assertTrue( btree1.hasKey( 3L ) );
173         assertTrue( btree1.hasKey( 5L ) );
174         assertEquals( "V1", btree1.get( 1L ) );
175         assertEquals( "V3", btree1.get( 3L ) );
176         assertEquals( "V5", btree1.get( 5L ) );
177     }
178 
179 
180     /**
181      * Test the creation of a RecordManager with a BTree containing data, enough for some Node to be created.
182      */
183     @Test
184     public void testRecordManagerWithBTreeLeafNode() throws IOException, BTreeAlreadyManagedException,
185         KeyNotFoundException
186     {
187         // Now, add some elements in the BTree
188         for ( long i = 1L; i < 32L; i++ )
189         {
190             btree.insert( i, "V" + i );
191         }
192 
193         // Now, try to reload the file back
194         openRecordManagerAndBtree();
195 
196         assertEquals( 1, recordManager1.getNbManagedTrees() );
197 
198         Set<String> managedBTrees = recordManager1.getManagedTrees();
199 
200         assertEquals( 1, managedBTrees.size() );
201         assertTrue( managedBTrees.contains( "test" ) );
202 
203         BTree<Long, String> btree1 = recordManager1.getManagedTree( "test" );
204 
205         assertNotNull( btree1 );
206         assertEquals( btree.getComparator().getClass().getName(), btree1.getComparator().getClass().getName() );
207         assertEquals( btree.getKeySerializer().getClass().getName(), btree1.getKeySerializer().getClass().getName() );
208         assertEquals( btree.getName(), btree1.getName() );
209         assertEquals( btree.getNbElems(), btree1.getNbElems() );
210         assertEquals( btree.getPageSize(), btree1.getPageSize() );
211         assertEquals( btree.getRevision(), btree1.getRevision() );
212         assertEquals( btree.getValueSerializer().getClass().getName(), btree1.getValueSerializer().getClass().getName() );
213 
214         // Check the stored element
215         for ( long i = 1L; i < 32L; i++ )
216         {
217             assertTrue( btree1.hasKey( i ) );
218             assertEquals( "V" + i, btree1.get( i ) );
219         }
220     }
221 
222 
223     /**
224      * Test the creation of a RecordManager with a BTree containing 100 000 elements
225      */
226     @Test
227     @Ignore("This is a performance test")
228     public void testRecordManagerWithBTreeLeafNode100K() throws IOException, BTreeAlreadyManagedException,
229         KeyNotFoundException
230     {
231         // Don't keep any revision
232         recordManager1.setKeepRevisions( false );
233 
234         String fileName = dataDir.getAbsolutePath() + "/mavibot.db";
235         File file = new File( fileName );
236         long fileSize = file.length();
237         long nbElems = 100000L;
238         System.out.println( "----- Size before = " + fileSize );
239 
240         // Now, add some elements in the BTree
241         long t0 = System.currentTimeMillis();
242         for ( Long i = 0L; i < nbElems; i++ )
243         {
244             String value = "V" + i;
245             btree.insert( i, value );
246 
247             /*
248             if ( !recordManager1.check() )
249             {
250                 System.out.println( "Failure while adding element " + i );
251                 fail();
252             }
253             */
254 
255             if ( i % 10000 == 0 )
256             {
257                 fileSize = file.length();
258                 System.out.println( "----- Size after insertion of " + i + " = " + fileSize );
259                 System.out.println( recordManager1 );
260                 //System.out.println( btree );
261             }
262         }
263         long t1 = System.currentTimeMillis();
264 
265         fileSize = file.length();
266         System.out.println( "Size after insertion of 100 000 elements : " + fileSize );
267         System.out.println( "Time taken to write 100 000 elements : " + ( t1 - t0 ) );
268         System.out.println( "  Nb elem/s : " + ( ( nbElems * 1000 ) / ( t1 - t0 ) ) );
269         System.out.println( "Nb created page " + recordManager1.nbCreatedPages.get() );
270         System.out.println( "Nb allocated page " + recordManager1.nbReusedPages.get() );
271         System.out.println( "Nb page we have freed " + recordManager1.nbFreedPages.get() );
272         System.out.println( recordManager1 );
273 
274         // Now, try to reload the file back
275         openRecordManagerAndBtree();
276 
277         assertEquals( 1, recordManager1.getNbManagedTrees() );
278 
279         Set<String> managedBTrees = recordManager1.getManagedTrees();
280 
281         assertEquals( 1, managedBTrees.size() );
282         assertTrue( managedBTrees.contains( "test" ) );
283 
284         BTree<Long, String> btree1 = recordManager1.getManagedTree( "test" );
285 
286         assertNotNull( btree1 );
287         assertEquals( btree.getComparator().getClass().getName(), btree1.getComparator().getClass().getName() );
288         assertEquals( btree.getKeySerializer().getClass().getName(), btree1.getKeySerializer().getClass().getName() );
289         assertEquals( btree.getName(), btree1.getName() );
290         assertEquals( btree.getNbElems(), btree1.getNbElems() );
291         assertEquals( btree.getPageSize(), btree1.getPageSize() );
292         assertEquals( btree.getRevision(), btree1.getRevision() );
293         assertEquals( btree.getValueSerializer().getClass().getName(), btree1.getValueSerializer().getClass().getName() );
294 
295         // Check the stored element
296         long t2 = System.currentTimeMillis();
297         for ( long i = 0L; i < nbElems; i++ )
298         {
299             //assertTrue( btree1.exist( i ) );
300             assertEquals( "V" + i, btree1.get( i ) );
301         }
302         long t3 = System.currentTimeMillis();
303         System.out.println( "Time taken to verify 100 000 elements : " + ( t3 - t2 ) );
304 
305         // Check the stored element a second time
306         long t4 = System.currentTimeMillis();
307         for ( long i = 0L; i < nbElems; i++ )
308         {
309             //assertTrue( btree1.exist( i ) );
310             assertEquals( "V" + i, btree1.get( i ) );
311         }
312         long t5 = System.currentTimeMillis();
313         System.out.println( "Time taken to verify 100 000 elements : " + ( t5 - t4 ) );
314     }
315 
316 
317     private void checkBTreeRevisionBrowse( BTree<Long, String> btree, long revision, long... values )
318         throws IOException,
319         KeyNotFoundException
320     {
321         TupleCursor<Long, String> cursor = btree.browse( revision );
322         List<Long> expected = new ArrayList<Long>( values.length );
323         Set<Long> found = new HashSet<Long>( values.length );
324 
325         for ( long value : values )
326         {
327             expected.add( value );
328         }
329 
330         int nb = 0;
331 
332         while ( cursor.hasNext() )
333         {
334             Tuple<Long, String> res = cursor.next();
335 
336             long key = res.getKey();
337             assertEquals( expected.get( nb ), ( Long ) key );
338             assertFalse( found.contains( key ) );
339             found.add( key );
340             assertEquals( "V" + key, res.getValue() );
341             nb++;
342         }
343 
344         assertEquals( values.length, nb );
345         cursor.close();
346     }
347 
348 
349     private void checkBTreeRevisionBrowseFrom( BTree<Long, String> btree, long revision, long from, long... values )
350         throws IOException,
351         KeyNotFoundException
352     {
353         TupleCursor<Long, String> cursor = btree.browseFrom( revision, from );
354         List<Long> expected = new ArrayList<Long>( values.length );
355         Set<Long> found = new HashSet<Long>( values.length );
356 
357         for ( long value : values )
358         {
359             expected.add( value );
360         }
361 
362         int nb = 0;
363 
364         while ( cursor.hasNext() )
365         {
366             Tuple<Long, String> res = cursor.next();
367 
368             long key = res.getKey();
369             assertEquals( expected.get( nb ), ( Long ) key );
370             assertFalse( found.contains( key ) );
371             found.add( key );
372             assertEquals( "V" + key, res.getValue() );
373             nb++;
374         }
375 
376         assertEquals( values.length, nb );
377         cursor.close();
378 
379     }
380 
381 
382     /**
383      * Test the creation of a RecordManager with a BTree containing data, where we keep the revisions, 
384      * and browse the BTree.
385      */
386     @Test
387     public void testRecordManagerBrowseWithKeepRevisions() throws IOException, BTreeAlreadyManagedException,
388         KeyNotFoundException
389     {
390         recordManager1.setKeepRevisions( true );
391 
392         // Now, add some elements in the BTree
393         btree.insert( 3L, "V3" );
394         long rev1 = btree.getRevision();
395 
396         btree.insert( 1L, "V1" );
397         long rev2 = btree.getRevision();
398 
399         btree.insert( 5L, "V5" );
400         long rev3 = btree.getRevision();
401 
402         // Check that we can browse each revision
403         // revision 1
404         checkBTreeRevisionBrowse( btree, rev1, 3L );
405 
406         // Revision 2
407         checkBTreeRevisionBrowse( btree, rev2, 1L, 3L );
408 
409         // Revision 3
410         checkBTreeRevisionBrowse( btree, rev3, 1L, 3L, 5L );
411 
412         // Now, try to reload the file back
413         openRecordManagerAndBtree();
414 
415         assertEquals( 1, recordManager1.getNbManagedTrees() );
416 
417         Set<String> managedBTrees = recordManager1.getManagedTrees();
418 
419         assertEquals( 1, managedBTrees.size() );
420         assertTrue( managedBTrees.contains( "test" ) );
421 
422         BTree<Long, String> btree1 = recordManager1.getManagedTree( "test" );
423 
424         assertNotNull( btree1 );
425         assertEquals( btree.getComparator().getClass().getName(), btree1.getComparator().getClass().getName() );
426         assertEquals( btree.getKeySerializer().getClass().getName(), btree1.getKeySerializer().getClass().getName() );
427         assertEquals( btree.getName(), btree1.getName() );
428         assertEquals( btree.getNbElems(), btree1.getNbElems() );
429         assertEquals( btree.getPageSize(), btree1.getPageSize() );
430         assertEquals( btree.getRevision(), btree1.getRevision() );
431         assertEquals( btree.getValueSerializer().getClass().getName(), btree1.getValueSerializer().getClass().getName() );
432 
433         // Check the stored element
434         assertTrue( btree1.hasKey( 1L ) );
435         assertTrue( btree1.hasKey( 3L ) );
436         assertTrue( btree1.hasKey( 5L ) );
437         assertEquals( "V1", btree1.get( 1L ) );
438         assertEquals( "V3", btree1.get( 3L ) );
439         assertEquals( "V5", btree1.get( 5L ) );
440 
441         // Check that we can read the revision again
442         // revision 1
443         checkBTreeRevisionBrowse( btree, rev1, 3L );
444 
445         // Revision 2
446         checkBTreeRevisionBrowse( btree, rev2, 1L, 3L );
447 
448         // Revision 3
449         checkBTreeRevisionBrowse( btree, rev3, 1L, 3L, 5L );
450     }
451 
452 
453     /**
454      * Test the creation of a RecordManager with a BTree containing data, where we keep the revision, and 
455      * we browse from a key
456      */
457     @Test
458     public void testRecordManagerBrowseFromWithRevision() throws IOException, BTreeAlreadyManagedException,
459         KeyNotFoundException
460     {
461         recordManager1.setKeepRevisions( true );
462 
463         // Now, add some elements in the BTree
464         btree.insert( 3L, "V3" );
465         long rev1 = btree.getRevision();
466 
467         btree.insert( 1L, "V1" );
468         long rev2 = btree.getRevision();
469 
470         btree.insert( 5L, "V5" );
471         long rev3 = btree.getRevision();
472 
473         // Check that we can browse each revision
474         // revision 1
475         checkBTreeRevisionBrowseFrom( btree, rev1, 3L, 3L );
476 
477         // Revision 2
478         checkBTreeRevisionBrowseFrom( btree, rev2, 3L, 3L );
479 
480         // Revision 3
481         checkBTreeRevisionBrowseFrom( btree, rev3, 3L, 3L, 5L );
482 
483         // Now, try to reload the file back
484         openRecordManagerAndBtree();
485 
486         assertEquals( 1, recordManager1.getNbManagedTrees() );
487 
488         Set<String> managedBTrees = recordManager1.getManagedTrees();
489 
490         assertEquals( 1, managedBTrees.size() );
491         assertTrue( managedBTrees.contains( "test" ) );
492 
493         BTree<Long, String> btree1 = recordManager1.getManagedTree( "test" );
494 
495         assertNotNull( btree1 );
496         assertEquals( btree.getComparator().getClass().getName(), btree1.getComparator().getClass().getName() );
497         assertEquals( btree.getKeySerializer().getClass().getName(), btree1.getKeySerializer().getClass().getName() );
498         assertEquals( btree.getName(), btree1.getName() );
499         assertEquals( btree.getNbElems(), btree1.getNbElems() );
500         assertEquals( btree.getPageSize(), btree1.getPageSize() );
501         assertEquals( btree.getRevision(), btree1.getRevision() );
502         assertEquals( btree.getValueSerializer().getClass().getName(), btree1.getValueSerializer().getClass().getName() );
503 
504         // Check the stored element
505         assertTrue( btree1.hasKey( 1L ) );
506         assertTrue( btree1.hasKey( 3L ) );
507         assertTrue( btree1.hasKey( 5L ) );
508         assertEquals( "V1", btree1.get( 1L ) );
509         assertEquals( "V3", btree1.get( 3L ) );
510         assertEquals( "V5", btree1.get( 5L ) );
511 
512         // Check that we can read the revision again
513         // revision 1
514         checkBTreeRevisionBrowseFrom( btree, rev1, 3L, 3L );
515 
516         // Revision 2
517         checkBTreeRevisionBrowseFrom( btree, rev2, 3L, 3L );
518 
519         // Revision 3
520         checkBTreeRevisionBrowseFrom( btree, rev3, 3L, 3L, 5L );
521     }
522 
523 
524     /**
525      * Test a get() from a given revision
526      */
527     @Test
528     public void testGetWithRevision() throws IOException, BTreeAlreadyManagedException,
529         KeyNotFoundException
530     {
531         recordManager1.setKeepRevisions( true );
532 
533         // Now, add some elements in the BTree
534         btree.insert( 3L, "V3" );
535         long rev1 = btree.getRevision();
536 
537         btree.insert( 1L, "V1" );
538         long rev2 = btree.getRevision();
539 
540         btree.insert( 5L, "V5" );
541         long rev3 = btree.getRevision();
542 
543         // Delete one element
544         btree.delete( 3L );
545         long rev4 = btree.getRevision();
546 
547         // Check that we can get a value from each revision
548         // revision 1
549         assertEquals( "V3", btree.get( rev1, 3L ) );
550 
551         // revision 2
552         assertEquals( "V1", btree.get( rev2, 1L ) );
553         assertEquals( "V3", btree.get( rev2, 3L ) );
554 
555         // revision 3
556         assertEquals( "V1", btree.get( rev3, 1L ) );
557         assertEquals( "V3", btree.get( rev3, 3L ) );
558         assertEquals( "V5", btree.get( rev3, 5L ) );
559 
560         // revision 4
561         assertEquals( "V1", btree.get( rev4, 1L ) );
562         assertEquals( "V5", btree.get( rev4, 5L ) );
563 
564         try
565         {
566             btree.get( rev4, 3L );
567             fail();
568         }
569         catch ( KeyNotFoundException knfe )
570         {
571             // expected
572         }
573 
574         // Now, try to reload the file back
575         openRecordManagerAndBtree();
576 
577         assertEquals( 1, recordManager1.getNbManagedTrees() );
578 
579         Set<String> managedBTrees = recordManager1.getManagedTrees();
580 
581         assertEquals( 1, managedBTrees.size() );
582         assertTrue( managedBTrees.contains( "test" ) );
583 
584         BTree<Long, String> btree1 = recordManager1.getManagedTree( "test" );
585 
586         assertNotNull( btree1 );
587         assertEquals( btree.getComparator().getClass().getName(), btree1.getComparator().getClass().getName() );
588         assertEquals( btree.getKeySerializer().getClass().getName(), btree1.getKeySerializer().getClass().getName() );
589         assertEquals( btree.getName(), btree1.getName() );
590         assertEquals( btree.getNbElems(), btree1.getNbElems() );
591         assertEquals( btree.getPageSize(), btree1.getPageSize() );
592         assertEquals( btree.getRevision(), btree1.getRevision() );
593         assertEquals( btree.getValueSerializer().getClass().getName(), btree1.getValueSerializer().getClass().getName() );
594 
595         // Check the stored element
596         assertTrue( btree1.hasKey( 1L ) );
597         assertFalse( btree1.hasKey( 3L ) );
598         assertTrue( btree1.hasKey( 5L ) );
599         assertEquals( "V1", btree1.get( 1L ) );
600         assertEquals( "V5", btree1.get( 5L ) );
601 
602         // Check that we can get a value from each revision
603         // revision 1
604         assertEquals( "V3", btree.get( rev1, 3L ) );
605 
606         // revision 2
607         assertEquals( "V1", btree.get( rev2, 1L ) );
608         assertEquals( "V3", btree.get( rev2, 3L ) );
609 
610         // revision 3
611         assertEquals( "V1", btree.get( rev3, 1L ) );
612         assertEquals( "V3", btree.get( rev3, 3L ) );
613         assertEquals( "V5", btree.get( rev3, 5L ) );
614 
615         // revision 4
616         assertEquals( "V1", btree.get( rev4, 1L ) );
617         assertEquals( "V5", btree.get( rev4, 5L ) );
618 
619         try
620         {
621             btree.get( rev4, 3L );
622             fail();
623         }
624         catch ( KeyNotFoundException knfe )
625         {
626             // expected
627         }
628     }
629 
630 
631     /**
632      * Test a contain() from a given revision
633      */
634     @Test
635     public void testContainWithRevision() throws IOException, BTreeAlreadyManagedException,
636         KeyNotFoundException
637     {
638         recordManager1.setKeepRevisions( true );
639 
640         // Now, add some elements in the BTree
641         btree.insert( 3L, "V3" );
642         long rev1 = btree.getRevision();
643 
644         btree.insert( 1L, "V1" );
645         long rev2 = btree.getRevision();
646 
647         btree.insert( 5L, "V5" );
648         long rev3 = btree.getRevision();
649 
650         // Delete one element
651         btree.delete( 3L );
652         long rev4 = btree.getRevision();
653 
654         // Check that we can get a value from each revision
655         // revision 1
656         assertFalse( btree.contains( rev1, 1L, "V1" ) );
657         assertTrue( btree.contains( rev1, 3L, "V3" ) );
658         assertFalse( btree.contains( rev1, 5L, "V5" ) );
659 
660         // revision 2
661         assertTrue( btree.contains( rev2, 1L, "V1" ) );
662         assertTrue( btree.contains( rev2, 3L, "V3" ) );
663         assertFalse( btree.contains( rev2, 5L, "V5" ) );
664 
665         // revision 3
666         assertTrue( btree.contains( rev3, 1L, "V1" ) );
667         assertTrue( btree.contains( rev3, 3L, "V3" ) );
668         assertTrue( btree.contains( rev3, 5L, "V5" ) );
669 
670         // revision 4
671         assertTrue( btree.contains( rev4, 1L, "V1" ) );
672         assertFalse( btree.contains( rev4, 3L, "V3" ) );
673         assertTrue( btree.contains( rev4, 5L, "V5" ) );
674 
675         // Now, try to reload the file back
676         openRecordManagerAndBtree();
677 
678         assertEquals( 1, recordManager1.getNbManagedTrees() );
679 
680         Set<String> managedBTrees = recordManager1.getManagedTrees();
681 
682         assertEquals( 1, managedBTrees.size() );
683         assertTrue( managedBTrees.contains( "test" ) );
684 
685         BTree<Long, String> btree1 = recordManager1.getManagedTree( "test" );
686 
687         assertNotNull( btree1 );
688         assertEquals( btree.getComparator().getClass().getName(), btree1.getComparator().getClass().getName() );
689         assertEquals( btree.getKeySerializer().getClass().getName(), btree1.getKeySerializer().getClass().getName() );
690         assertEquals( btree.getName(), btree1.getName() );
691         assertEquals( btree.getNbElems(), btree1.getNbElems() );
692         assertEquals( btree.getPageSize(), btree1.getPageSize() );
693         assertEquals( btree.getRevision(), btree1.getRevision() );
694         assertEquals( btree.getValueSerializer().getClass().getName(), btree1.getValueSerializer().getClass().getName() );
695 
696         // Check the stored element
697         assertTrue( btree1.hasKey( 1L ) );
698         assertFalse( btree1.hasKey( 3L ) );
699         assertTrue( btree1.hasKey( 5L ) );
700         assertEquals( "V1", btree1.get( 1L ) );
701         assertEquals( "V5", btree1.get( 5L ) );
702 
703         // Check that we can get a value from each revision
704         // revision 1
705         assertFalse( btree.contains( rev1, 1L, "V1" ) );
706         assertTrue( btree.contains( rev1, 3L, "V3" ) );
707         assertFalse( btree.contains( rev1, 5L, "V5" ) );
708 
709         // revision 2
710         assertTrue( btree.contains( rev2, 1L, "V1" ) );
711         assertTrue( btree.contains( rev2, 3L, "V3" ) );
712         assertFalse( btree.contains( rev2, 5L, "V5" ) );
713 
714         // revision 3
715         assertTrue( btree.contains( rev3, 1L, "V1" ) );
716         assertTrue( btree.contains( rev3, 3L, "V3" ) );
717         assertTrue( btree.contains( rev3, 5L, "V5" ) );
718 
719         // revision 4
720         assertTrue( btree.contains( rev4, 1L, "V1" ) );
721         assertFalse( btree.contains( rev4, 3L, "V3" ) );
722         assertTrue( btree.contains( rev4, 5L, "V5" ) );
723     }
724 
725 
726     /**
727      * Test a hasKey() from a given revision
728      */
729     @Test
730     public void testHasKeyWithRevision() throws IOException, BTreeAlreadyManagedException,
731         KeyNotFoundException
732     {
733         recordManager1.setKeepRevisions( true );
734 
735         // Now, add some elements in the BTree
736         btree.insert( 3L, "V3" );
737         long rev1 = btree.getRevision();
738 
739         btree.insert( 1L, "V1" );
740         long rev2 = btree.getRevision();
741 
742         btree.insert( 5L, "V5" );
743         long rev3 = btree.getRevision();
744 
745         // Delete one element
746         btree.delete( 3L );
747         long rev4 = btree.getRevision();
748 
749         // Check that we can get a value from each revision
750         // revision 1
751         assertFalse( btree.hasKey( rev1, 1L ) );
752         assertTrue( btree.hasKey( rev1, 3L ) );
753         assertFalse( btree.hasKey( rev1, 5L ) );
754 
755         // revision 2
756         assertTrue( btree.hasKey( rev2, 1L ) );
757         assertTrue( btree.hasKey( rev2, 3L ) );
758         assertFalse( btree.hasKey( rev2, 5L ) );
759 
760         // revision 3
761         assertTrue( btree.hasKey( rev3, 1L ) );
762         assertTrue( btree.hasKey( rev3, 3L ) );
763         assertTrue( btree.hasKey( rev3, 5L ) );
764 
765         // revision 4
766         assertTrue( btree.hasKey( rev4, 1L ) );
767         assertFalse( btree.hasKey( rev4, 3L ) );
768         assertTrue( btree.hasKey( rev4, 5L ) );
769 
770         // Now, try to reload the file back
771         openRecordManagerAndBtree();
772 
773         assertEquals( 1, recordManager1.getNbManagedTrees() );
774 
775         Set<String> managedBTrees = recordManager1.getManagedTrees();
776 
777         assertEquals( 1, managedBTrees.size() );
778         assertTrue( managedBTrees.contains( "test" ) );
779 
780         BTree<Long, String> btree1 = recordManager1.getManagedTree( "test" );
781 
782         assertNotNull( btree1 );
783         assertEquals( btree.getComparator().getClass().getName(), btree1.getComparator().getClass().getName() );
784         assertEquals( btree.getKeySerializer().getClass().getName(), btree1.getKeySerializer().getClass().getName() );
785         assertEquals( btree.getName(), btree1.getName() );
786         assertEquals( btree.getNbElems(), btree1.getNbElems() );
787         assertEquals( btree.getPageSize(), btree1.getPageSize() );
788         assertEquals( btree.getRevision(), btree1.getRevision() );
789         assertEquals( btree.getValueSerializer().getClass().getName(), btree1.getValueSerializer().getClass().getName() );
790 
791         // Check the stored element
792         assertTrue( btree1.hasKey( 1L ) );
793         assertFalse( btree1.hasKey( 3L ) );
794         assertTrue( btree1.hasKey( 5L ) );
795         assertEquals( "V1", btree1.get( 1L ) );
796         assertEquals( "V5", btree1.get( 5L ) );
797 
798         // Check that we can get a value from each revision
799         // revision 1
800         assertFalse( btree.hasKey( rev1, 1L ) );
801         assertTrue( btree.hasKey( rev1, 3L ) );
802         assertFalse( btree.hasKey( rev1, 5L ) );
803 
804         // revision 2
805         assertTrue( btree.hasKey( rev2, 1L ) );
806         assertTrue( btree.hasKey( rev2, 3L ) );
807         assertFalse( btree.hasKey( rev2, 5L ) );
808 
809         // revision 3
810         assertTrue( btree.hasKey( rev3, 1L ) );
811         assertTrue( btree.hasKey( rev3, 3L ) );
812         assertTrue( btree.hasKey( rev3, 5L ) );
813 
814         // revision 4
815         assertTrue( btree.hasKey( rev4, 1L ) );
816         assertFalse( btree.hasKey( rev4, 3L ) );
817         assertTrue( btree.hasKey( rev4, 5L ) );
818     }
819 
820 
821     /**
822      * Test with BTrees containing duplicate keys
823      */
824     @Test
825     public void testBTreesDuplicateKeys() throws IOException, BTreeAlreadyManagedException,
826         KeyNotFoundException
827     {
828         int pageSize = 16;
829         int numKeys = 1;
830         String name = "duplicateTree";
831         String[] testValues = new String[]{ "00", "01", "02", "03", "04", "05", "06", "07", "08", "09", "0A", "0B", "0C", "0D", "0E", "0F", "10" };
832 
833         BTree<Long, String> dupsTree = new BTree<Long, String>( name, null, new LongSerializer(),
834             new StringSerializer(), pageSize,
835             true );
836 
837         recordManager1.manage( dupsTree );
838         
839         for ( long i = 0; i < numKeys; i++ )
840         {
841             for ( int k = 0; k < pageSize + 1; k++ )
842             {
843                 dupsTree.insert( i, testValues[ k ] );
844             }
845         }
846 
847         // Now, try to reload the file back
848         openRecordManagerAndBtree();
849 
850         dupsTree = recordManager1.getManagedTree( name );
851 
852         for ( long i = 0; i < numKeys; i++ )
853         {
854             ValueCursor<String> values = dupsTree.getValues( i );
855 
856             for ( int k = 0; k < pageSize + 1; k++ )
857             {
858                 assertTrue( values.next().equals( testValues[ k ] ) );
859             }
860         }
861     }
862 }