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 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.assertNull;
27 import static org.junit.Assert.assertTrue;
28 import static org.junit.Assert.fail;
29
30 import java.io.File;
31 import java.io.IOException;
32 import java.util.NoSuchElementException;
33 import java.util.UUID;
34
35 import org.apache.commons.io.FileUtils;
36 import org.apache.directory.mavibot.btree.exception.BTreeAlreadyManagedException;
37 import org.apache.directory.mavibot.btree.exception.DuplicateValueNotAllowedException;
38 import org.apache.directory.mavibot.btree.serializer.IntSerializer;
39 import org.apache.directory.mavibot.btree.serializer.LongSerializer;
40 import org.apache.directory.mavibot.btree.serializer.StringSerializer;
41 import org.junit.After;
42 import org.junit.Before;
43 import org.junit.Rule;
44 import org.junit.Test;
45 import org.junit.rules.TemporaryFolder;
46
47
48
49
50
51
52
53 public class PersistedBTreeDuplicateKeyTest
54 {
55 private BTree<Long, String> btree = null;
56
57 private RecordManager recordManager1 = null;
58
59 @Rule
60 public TemporaryFolder tempFolder = new TemporaryFolder();
61
62 private File dataDir = null;
63
64
65 @Before
66 public void createBTree()
67 {
68 dataDir = tempFolder.newFolder( UUID.randomUUID().toString() );
69
70 openRecordManagerAndBtree();
71
72 try
73 {
74
75 btree = recordManager1.addBTree( "test", new LongSerializer(), new StringSerializer(),
76 BTree.ALLOW_DUPLICATES );
77 }
78 catch ( Exception e )
79 {
80 throw new RuntimeException( e );
81 }
82 }
83
84
85 @After
86 public void cleanup() throws IOException
87 {
88 dataDir = new File( System.getProperty( "java.io.tmpdir" ) + "/recordman" );
89
90 btree.close();
91
92 if ( dataDir.exists() )
93 {
94 FileUtils.deleteDirectory( dataDir );
95 }
96 }
97
98
99 private void openRecordManagerAndBtree()
100 {
101 try
102 {
103 if ( recordManager1 != null )
104 {
105 recordManager1.close();
106 }
107
108
109 recordManager1 = new RecordManager( dataDir.getAbsolutePath() );
110
111
112 if ( btree != null )
113 {
114 btree = recordManager1.getManagedTree( btree.getName() );
115 }
116 }
117 catch ( Exception e )
118 {
119 throw new RuntimeException( e );
120 }
121 }
122
123
124 @Test
125 public void testInsertNullValue() throws IOException
126 {
127 btree.insert( 1L, null );
128
129 TupleCursor<Long, String> cursor = btree.browse();
130 assertTrue( cursor.hasNext() );
131
132 Tuple<Long, String> t = cursor.next();
133
134 assertEquals( Long.valueOf( 1 ), t.getKey() );
135 assertEquals( null, t.getValue() );
136
137 cursor.close();
138
139 btree.close();
140 }
141
142
143 @Test
144 public void testBrowseEmptyTree() throws IOException
145 {
146 IntSerializer serializer = new IntSerializer();
147
148 BTree<Integer, Integer> btree = BTreeFactory.createPersistedBTree( "master", serializer, serializer );
149
150 TupleCursor<Integer, Integer> cursor = btree.browse();
151 assertFalse( cursor.hasNext() );
152 assertFalse( cursor.hasPrev() );
153
154 try
155 {
156 cursor.next();
157 fail( "Should not reach here" );
158 }
159 catch ( NoSuchElementException e )
160 {
161 assertTrue( true );
162 }
163
164 try
165 {
166 cursor.prev();
167 fail( "Should not reach here" );
168 }
169 catch ( NoSuchElementException e )
170 {
171 assertTrue( true );
172 }
173
174 cursor.close();
175 btree.close();
176 }
177
178
179 @Test
180 public void testDuplicateKey() throws IOException
181 {
182 btree.insert( 1L, "1" );
183 btree.insert( 1L, "2" );
184
185 TupleCursor<Long, String> cursor = btree.browse();
186 assertTrue( cursor.hasNext() );
187
188 Tuple<Long, String> t = cursor.next();
189
190 assertEquals( Long.valueOf( 1 ), t.getKey() );
191 assertEquals( "1", t.getValue() );
192
193 assertTrue( cursor.hasNext() );
194
195 t = cursor.next();
196
197 assertEquals( Long.valueOf( 1 ), t.getKey() );
198 assertEquals( "2", t.getValue() );
199
200 assertFalse( cursor.hasNext() );
201
202
203 assertTrue( cursor.hasPrev() );
204
205 t = cursor.prev();
206
207 assertEquals( Long.valueOf( 1 ), t.getKey() );
208 assertEquals( "1", t.getValue() );
209
210 assertFalse( cursor.hasPrev() );
211
212
213 assertTrue( cursor.hasNext() );
214
215 t = cursor.next();
216
217 assertEquals( Long.valueOf( 1 ), t.getKey() );
218 assertEquals( "2", t.getValue() );
219
220 assertFalse( cursor.hasNext() );
221
222 cursor.close();
223 btree.close();
224 }
225
226
227 @Test
228 public void testGetDuplicateKey() throws Exception
229 {
230 String retVal = btree.insert( 1L, "1" );
231 assertNull( retVal );
232
233 retVal = btree.insert( 1L, "2" );
234 assertNull( retVal );
235
236
237 retVal = btree.insert( 1L, "2" );
238 assertEquals( "2", retVal );
239
240 assertEquals( "1", btree.get( 1L ) );
241 assertTrue( btree.contains( 1L, "1" ) );
242 assertTrue( btree.contains( 1L, "2" ) );
243
244 assertFalse( btree.contains( 1L, "0" ) );
245 assertFalse( btree.contains( 0L, "1" ) );
246 assertFalse( btree.contains( 0L, "0" ) );
247 assertFalse( btree.contains( null, "0" ) );
248 assertFalse( btree.contains( 0L, null ) );
249 assertFalse( btree.contains( null, null ) );
250 btree.close();
251 }
252
253
254 @Test
255 public void testRemoveDuplicateKey() throws Exception
256 {
257 btree.insert( 1L, "1" );
258 btree.insert( 1L, "2" );
259
260 assertEquals( 2, btree.getNbElems() );
261
262 Tuple<Long, String> t = btree.delete( 1L, "1" );
263 assertEquals( Long.valueOf( 1 ), t.getKey() );
264 assertEquals( "1", t.getValue() );
265
266 assertEquals( 1l, btree.getNbElems() );
267
268 t = btree.delete( 1L, "2" );
269 assertEquals( Long.valueOf( 1 ), t.getKey() );
270 assertEquals( "2", t.getValue() );
271
272 assertEquals( 0l, btree.getNbElems() );
273
274 t = btree.delete( 1L, "2" );
275 assertNull( t );
276 btree.close();
277 }
278
279
280 @Test
281 public void testFullPage() throws Exception
282 {
283 int i = 7;
284 for ( char ch = 'a'; ch <= 'z'; ch++ )
285 {
286 for ( int k = 0; k < i; k++ )
287 {
288 String val = ch + Integer.toString( k );
289 btree.insert( Long.valueOf( ch ), val );
290 }
291 }
292
293 TupleCursor<Long, String> cursor = btree.browse();
294
295 char ch = 'a';
296 int k = 0;
297
298 while ( cursor.hasNext() )
299 {
300 Tuple<Long, String> t = cursor.next();
301 assertEquals( Long.valueOf( ch ), t.getKey() );
302 k++;
303
304 if ( ( k % i ) == 0 )
305 {
306 ch++;
307 }
308 }
309
310 assertEquals( ( 'z' + 1 ), ch );
311
312 ch = 'z';
313 cursor.afterLast();
314
315 while ( cursor.hasPrev() )
316 {
317 Tuple<Long, String> t = cursor.prev();
318 assertEquals( Long.valueOf( ch ), t.getKey() );
319 k--;
320
321 if ( ( k % i ) == 0 )
322 {
323 ch--;
324 }
325 }
326
327 assertEquals( ( 'a' - 1 ), ch );
328 cursor.close();
329 }
330
331
332 @Test
333 public void testMoveFirst() throws Exception
334 {
335 for ( char ch = 'a'; ch <= 'z'; ch++ )
336 {
337 String val = Character.toString( ch );
338 btree.insert( Long.valueOf( ch ), val );
339 }
340
341 assertEquals( 26, btree.getNbElems() );
342
343
344 btree.insert( Long.valueOf( 'a' ), "val" );
345
346 assertEquals( 27, btree.getNbElems() );
347
348
349 TupleCursor<Long, String> cursor = btree.browseFrom( Long.valueOf( 'c' ) );
350
351 int i = 0;
352
353 while ( cursor.hasNext() )
354 {
355 Tuple<Long, String> tuple = cursor.next();
356 assertNotNull( tuple );
357 i++;
358 }
359
360 assertEquals( 24, i );
361
362
363 cursor.beforeFirst();
364 assertTrue( cursor.hasNext() );
365 Tuple<Long, String> tuple = cursor.next();
366
367
368 assertEquals( Long.valueOf( 'a' ), tuple.getKey() );
369
370
371 i = 0;
372
373 while ( cursor.hasNext() )
374 {
375 tuple = cursor.next();
376 assertNotNull( tuple );
377 i++;
378 }
379
380 assertEquals( 26, i );
381
382 cursor.close();
383
384
385 cursor = btree.browse();
386
387 i = 0;
388
389 while ( cursor.hasNext() )
390 {
391 assertNotNull( cursor.next() );
392 i++;
393 }
394
395
396 assertEquals( 27, i );
397
398
399 cursor.beforeFirst();
400 assertTrue( cursor.hasNextKey() );
401 assertEquals( Long.valueOf( 'a' ), cursor.nextKey().getKey() );
402
403 i = 0;
404
405 while ( cursor.hasNextKey() )
406 {
407 tuple = cursor.nextKey();
408 long key = tuple.getKey();
409 assertNotNull( key );
410 i++;
411 }
412
413
414 assertEquals( 25, i );
415 }
416
417
418 @Test
419 public void testMoveLast() throws Exception
420 {
421 for ( char ch = 'a'; ch <= 'z'; ch++ )
422 {
423 String val = Character.toString( ch );
424 btree.insert( Long.valueOf( ch ), val );
425 }
426
427 assertEquals( 26, btree.getNbElems() );
428
429
430 btree.insert( Long.valueOf( 'z' ), "val" );
431
432 assertEquals( 27, btree.getNbElems() );
433
434
435 TupleCursor<Long, String> cursor = btree.browseFrom( Long.valueOf( 'x' ) );
436
437 int i = 0;
438
439 while ( cursor.hasPrev() )
440 {
441 Tuple<Long, String> tuple = cursor.prev();
442 assertNotNull( tuple );
443 i++;
444 }
445
446 assertEquals( 23, i );
447
448
449 cursor.afterLast();
450 assertTrue( cursor.hasPrev() );
451 Tuple<Long, String> tuple = cursor.prev();
452
453
454 assertEquals( Long.valueOf( 'z' ), tuple.getKey() );
455
456
457 i = 0;
458
459 while ( cursor.hasPrev() )
460 {
461 tuple = cursor.prev();
462 assertNotNull( tuple );
463 i++;
464 }
465
466 assertEquals( 26, i );
467
468 cursor.close();
469
470
471 cursor = btree.browse();
472 cursor.afterLast();
473
474 i = 0;
475
476 while ( cursor.hasPrev() )
477 {
478 assertNotNull( cursor.prev() );
479 i++;
480 }
481
482
483 assertEquals( 27, i );
484
485
486 cursor.afterLast();
487 assertTrue( cursor.hasPrevKey() );
488 assertEquals( Long.valueOf( 'z' ), cursor.prevKey().getKey() );
489
490 i = 0;
491
492 while ( cursor.hasPrevKey() )
493 {
494 tuple = cursor.prevKey();
495 long key = tuple.getKey();
496 assertNotNull( key );
497 i++;
498 }
499
500
501 assertEquals( 25, i );
502 }
503
504
505 @Test(expected = NoSuchElementException.class)
506 public void testMoveLast2() throws Exception
507 {
508 for ( char ch = 'a'; ch <= 'z'; ch++ )
509 {
510 btree.insert( Long.valueOf( ch ), UUID.randomUUID().toString() );
511 }
512
513 btree.insert( Long.valueOf( 'z' ), UUID.randomUUID().toString() );
514
515 TupleCursor<Long, String> cursor = btree.browseFrom( Long.valueOf( 'c' ) );
516 cursor.afterLast();
517
518 assertFalse( cursor.hasNext() );
519 assertTrue( cursor.hasPrev() );
520 assertEquals( Long.valueOf( 'z' ), cursor.prev().getKey() );
521
522 assertEquals( Long.valueOf( 'z' ), cursor.prev().getKey() );
523 assertEquals( Long.valueOf( 'y' ), cursor.prev().getKey() );
524
525 cursor.beforeFirst();
526 assertEquals( Long.valueOf( 'a' ), cursor.next().getKey() );
527
528 cursor.afterLast();
529 assertFalse( cursor.hasNext() );
530
531 cursor.next();
532 }
533
534
535 @Test(expected = NoSuchElementException.class)
536 public void testNextPrevKey() throws Exception
537 {
538 int i = 7;
539
540
541 for ( char ch = 'a'; ch <= 'z'; ch++ )
542 {
543 for ( int k = 0; k < i; k++ )
544 {
545 btree.insert( Long.valueOf( ch ), String.valueOf( k ) );
546 }
547 }
548
549 TupleCursor<Long, String> cursor = btree.browse();
550
551 assertTrue( cursor.hasNext() );
552 assertFalse( cursor.hasPrev() );
553
554 for ( int k = 0; k < 2; k++ )
555 {
556 assertEquals( Long.valueOf( 'a' ), cursor.next().getKey() );
557 }
558
559 assertEquals( Long.valueOf( 'a' ), cursor.next().getKey() );
560
561 Tuple<Long, String> tuple = cursor.nextKey();
562
563 assertEquals( Long.valueOf( 'b' ), tuple.getKey() );
564
565 for ( char ch = 'b'; ch < 'z'; ch++ )
566 {
567 assertEquals( Long.valueOf( ch ), cursor.next().getKey() );
568 tuple = cursor.nextKey();
569 char t = ch;
570 assertEquals( Long.valueOf( ++t ), tuple.getKey() );
571 }
572
573 for ( int k = 0; k < i; k++ )
574 {
575 assertEquals( Long.valueOf( 'z' ), cursor.next().getKey() );
576 }
577
578 assertFalse( cursor.hasNextKey() );
579 assertTrue( cursor.hasPrevKey() );
580 tuple = cursor.prev();
581 assertEquals( Long.valueOf( 'z' ), tuple.getKey() );
582 assertEquals( "6", tuple.getValue() );
583
584 for ( char ch = 'z'; ch > 'a'; ch-- )
585 {
586 char t = ch;
587 t--;
588
589 assertEquals( Long.valueOf( ch ), cursor.prev().getKey() );
590
591 tuple = cursor.prevKey();
592
593 assertEquals( Long.valueOf( t ), tuple.getKey() );
594 }
595
596 for ( int k = 5; k >= 0; k-- )
597 {
598 tuple = cursor.prev();
599 assertEquals( Long.valueOf( 'a' ), tuple.getKey() );
600 assertEquals( String.valueOf( k ), tuple.getValue() );
601 }
602
603 assertTrue( cursor.hasNext() );
604 assertFalse( cursor.hasPrev() );
605 tuple = cursor.next();
606 assertEquals( Long.valueOf( 'a' ), tuple.getKey() );
607 assertEquals( "0", tuple.getValue() );
608
609 cursor.close();
610
611 cursor = btree.browseFrom( Long.valueOf( 'y' ) );
612 tuple = cursor.prevKey();
613 assertNotNull( tuple );
614 assertEquals( Long.valueOf( 'y' ), tuple.getKey() );
615 assertEquals( "6", tuple.getValue() );
616 cursor.close();
617
618 cursor = btree.browse();
619 cursor.beforeFirst();
620 assertFalse( cursor.hasPrev() );
621
622 cursor.prev();
623 }
624
625
626
627
628
629
630
631
632 @Test
633 public void testMoveToNextAndPrevWithPageBoundaries() throws Exception
634 {
635 int i = 32;
636 for ( int k = 0; k < i; k++ )
637 {
638 btree.insert( ( long ) k, Long.toString( k ) );
639 }
640
641
642
643 TupleCursor<Long, String> cursor = btree.browseFrom( 15L );
644 Tuple<Long, String> tuple = cursor.nextKey();
645
646 assertNotNull( tuple );
647 assertEquals( Long.valueOf( 16 ), tuple.getKey() );
648 assertEquals( "16", tuple.getValue() );
649 cursor.close();
650
651
652 cursor = btree.browseFrom( 16L );
653 tuple = cursor.prevKey();
654
655 assertNotNull( tuple );
656 assertEquals( Long.valueOf( 15 ), tuple.getKey() );
657 assertEquals( "15", tuple.getValue() );
658 cursor.close();
659
660
661 cursor = btree.browseFrom( 16L );
662 tuple = cursor.prevKey();
663
664 assertNotNull( tuple );
665 assertEquals( Long.valueOf( 15 ), tuple.getKey() );
666 assertEquals( "15", tuple.getValue() );
667
668
669 assertTrue( cursor.hasNext() );
670 tuple = cursor.next();
671 assertEquals( Long.valueOf( 16 ), tuple.getKey() );
672 assertEquals( "16", tuple.getValue() );
673 cursor.close();
674
675
676 cursor = btree.browseFrom( 30L );
677 tuple = cursor.nextKey();
678 assertFalse( cursor.hasNext() );
679 assertTrue( cursor.hasPrev() );
680
681 assertEquals( Long.valueOf( 31 ), tuple.getKey() );
682 assertEquals( "31", tuple.getValue() );
683 cursor.close();
684
685 cursor = btree.browse();
686 assertTrue( cursor.hasNext() );
687 assertFalse( cursor.hasPrev() );
688
689 tuple = cursor.nextKey();
690 assertEquals( Long.valueOf( 0 ), tuple.getKey() );
691 assertEquals( "0", tuple.getValue() );
692 cursor.close();
693 }
694
695
696 @Test
697 public void testNextAfterPrev() throws Exception
698 {
699 int i = 32;
700
701 for ( int k = 0; k < i; k++ )
702 {
703 btree.insert( ( long ) k, String.valueOf( k ) );
704 }
705
706
707 TupleCursor<Long, String> cursor = btree.browseFrom( 16L );
708
709 assertTrue( cursor.hasNext() );
710 Tuple<Long, String> tuple = cursor.next();
711 assertEquals( Long.valueOf( 16 ), tuple.getKey() );
712 assertEquals( "16", tuple.getValue() );
713
714 assertTrue( cursor.hasPrev() );
715 tuple = cursor.prev();
716 assertEquals( Long.valueOf( 15 ), tuple.getKey() );
717 assertEquals( "15", tuple.getValue() );
718
719 assertTrue( cursor.hasNext() );
720 tuple = cursor.next();
721 assertEquals( Long.valueOf( 16 ), tuple.getKey() );
722 assertEquals( "16", tuple.getValue() );
723 cursor.close();
724
725 }
726
727
728
729
730
731
732
733 @Test
734 public void testMoveToNextAndTraverseBackward() throws Exception
735 {
736 int i = 5;
737
738 for ( int k = 0; k < i; k++ )
739 {
740 btree.insert( ( long ) k, Long.toString( k ) );
741 }
742
743
744 TupleCursor<Long, String> cursor = btree.browseFrom( 4L );
745 cursor.nextKey();
746
747 long currentKey = 4L;
748
749 while ( cursor.hasPrev() )
750 {
751 assertEquals( Long.valueOf( currentKey ), cursor.prev().getKey() );
752 currentKey--;
753 }
754
755 cursor.close();
756 }
757
758
759
760
761
762
763
764 @Test
765 public void testMoveToPrevAndTraverseForward() throws Exception
766 {
767 int i = 5;
768
769 for ( int k = 0; k < i; k++ )
770 {
771 btree.insert( ( long ) k, Long.toString( k ) );
772 }
773
774
775 TupleCursor<Long, String> cursor = btree.browseFrom( 0L );
776
777 long currentKey = 0L;
778
779 while ( cursor.hasNext() )
780 {
781 assertEquals( Long.valueOf( currentKey ), cursor.next().getKey() );
782 currentKey++;
783 }
784
785 cursor.close();
786 }
787
788
789
790
791
792 @Test(expected = DuplicateValueNotAllowedException.class)
793 public void testBTreeForbidDups() throws IOException, BTreeAlreadyManagedException
794 {
795 BTree<Long, String> singleValueBtree = recordManager1.addBTree( "test2", new LongSerializer(),
796 new StringSerializer(), BTree.FORBID_DUPLICATES );
797
798 for ( long i = 0; i < 64; i++ )
799 {
800 singleValueBtree.insert( i, Long.toString( i ) );
801 }
802
803 try
804 {
805 singleValueBtree.insert( 18L, "Duplicate" );
806 fail();
807 }
808 finally
809 {
810 singleValueBtree.close();
811 }
812 }
813 }