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