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