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