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.memory;
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.Tuple;
35 import org.apache.directory.mavibot.btree.TupleCursor;
36 import org.apache.directory.mavibot.btree.serializer.IntSerializer;
37 import org.apache.directory.mavibot.btree.serializer.StringSerializer;
38 import org.junit.Test;
39
40
41
42
43
44
45
46 public class BTreeDuplicateKeyTest
47 {
48 @Test
49 public void testInsertNullValue() throws IOException
50 {
51 IntSerializer serializer = new IntSerializer();
52
53 BTree<Integer, Integer> btree = new BTree<Integer, Integer>( "master", serializer, serializer );
54 btree.init();
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
68 btree.close();
69 }
70
71
72 @Test
73 public void testBrowseEmptyTree() throws IOException
74 {
75 IntSerializer serializer = new IntSerializer();
76
77 BTree<Integer, Integer> btree = new BTree<Integer, Integer>( "master", serializer, serializer );
78 btree.init();
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
111 {
112 IntSerializer serializer = new IntSerializer();
113
114 BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
115 config.setAllowDuplicates( true );
116 config.setName( "master" );
117 config.setSerializers( serializer, serializer );
118 BTree<Integer, Integer> btree = new BTree<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 = new IntSerializer();
169
170 BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
171 config.setAllowDuplicates( true );
172 config.setName( "master" );
173 config.setSerializers( serializer, serializer );
174 BTree<Integer, Integer> btree = new BTree<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 btree.close();
197 }
198
199
200 @Test
201 public void testRemoveDuplicateKey() throws Exception
202 {
203 IntSerializer serializer = new IntSerializer();
204
205 BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
206 config.setAllowDuplicates( true );
207 config.setName( "master" );
208 config.setSerializers( serializer, serializer );
209 BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
210
211 btree.insert( 1, 1 );
212 btree.insert( 1, 2 );
213
214
215 assertEquals( 2l, btree.getNbElems() );
216
217 Tuple<Integer, Integer> t = btree.delete( 1, 1 );
218 assertEquals( Integer.valueOf( 1 ), t.getKey() );
219 assertEquals( Integer.valueOf( 1 ), t.getValue() );
220
221 assertEquals( 1l, btree.getNbElems() );
222
223 t = btree.delete( 1, 2 );
224 assertEquals( Integer.valueOf( 1 ), t.getKey() );
225 assertNull( t.getValue() );
226
227 assertEquals( 0l, btree.getNbElems() );
228
229 t = btree.delete( 1, 2 );
230 assertNull( t );
231 btree.close();
232 }
233
234
235 @Test
236 public void testFullPage() throws Exception
237 {
238 StringSerializer serializer = new StringSerializer();
239
240 BTreeConfiguration<String, String> config = new BTreeConfiguration<String, String>();
241 config.setAllowDuplicates( true );
242 config.setName( "master" );
243 config.setSerializers( serializer, serializer );
244 BTree<String, String> btree = new BTree<String, String>( config );
245
246 int i = 7;
247 for ( char ch = 'a'; ch <= 'z'; ch++ )
248 {
249 for ( int k = 0; k < i; k++ )
250 {
251 String val = ch + Integer.toString( k );
252 btree.insert( String.valueOf( ch ), val );
253 }
254 }
255
256 TupleCursor<String, String> cursor = btree.browse();
257
258 char ch = 'a';
259 int k = 0;
260
261 while ( cursor.hasNext() )
262 {
263 Tuple<String, String> t = cursor.next();
264 assertEquals( String.valueOf( ch ), t.getKey() );
265 k++;
266
267 if ( ( k % i ) == 0 )
268 {
269 ch++;
270 }
271 }
272
273 assertEquals( ( 'z' + 1 ), ch );
274
275 ch = 'z';
276 cursor.afterLast();
277
278 while ( cursor.hasPrev() )
279 {
280 Tuple<String, String> t = cursor.prev();
281 assertEquals( String.valueOf( ch ), t.getKey() );
282 k--;
283
284 if ( ( k % i ) == 0 )
285 {
286 ch--;
287 }
288 }
289
290 assertEquals( ( 'a' - 1 ), ch );
291 cursor.close();
292 btree.close();
293 }
294
295
296 @Test
297 public void testMoveFirst() throws Exception
298 {
299 StringSerializer serializer = new StringSerializer();
300
301 BTreeConfiguration<String, String> config = new BTreeConfiguration<String, String>();
302 config.setAllowDuplicates( true );
303 config.setName( "master" );
304 config.setSerializers( serializer, serializer );
305 BTree<String, String> btree = new BTree<String, String>( config );
306
307 for ( char ch = 'a'; ch <= 'z'; ch++ )
308 {
309 btree.insert( String.valueOf( ch ), UUID.randomUUID().toString() );
310 }
311
312 assertEquals( 26, btree.getNbElems() );
313
314
315 btree.insert( String.valueOf( 'a' ), UUID.randomUUID().toString() );
316
317 assertEquals( 27, btree.getNbElems() );
318
319 TupleCursor<String, String> cursor = btree.browseFrom( "c" );
320
321 int i = 0;
322
323 while ( cursor.hasNext() )
324 {
325 assertNotNull( cursor.next() );
326 i++;
327 }
328
329 assertEquals( 24, i );
330
331
332 cursor.beforeFirst();
333 assertTrue( cursor.hasNext() );
334 Tuple<String, String> tuple = cursor.next();
335
336 assertEquals( "a", tuple.getKey() );
337
338 i = 0;
339
340 while ( cursor.hasNext() )
341 {
342 tuple = cursor.next();
343 assertNotNull( tuple );
344 i++;
345 }
346
347 assertEquals( 26, i );
348
349 cursor.close();
350
351
352 cursor = btree.browse();
353
354 i = 0;
355
356 while ( cursor.hasNext() )
357 {
358 assertNotNull( cursor.next() );
359 i++;
360 }
361
362 assertEquals( 27, i );
363
364
365 cursor.beforeFirst();
366 assertTrue( cursor.hasNext() );
367 assertEquals( "a", cursor.nextKey().getKey() );
368
369 i = 0;
370
371 while ( cursor.hasNext() )
372 {
373 tuple = cursor.nextKey();
374 String key = tuple.getKey();
375 assertNotNull( key );
376 i++;
377 }
378
379 assertEquals( 25, i );
380 btree.close();
381 }
382
383
384 @Test(expected = NoSuchElementException.class)
385 public void testMoveLast() throws Exception
386 {
387 StringSerializer serializer = new StringSerializer();
388
389 BTreeConfiguration<String, String> config = new BTreeConfiguration<String, String>();
390 config.setAllowDuplicates( true );
391 config.setName( "master" );
392 config.setSerializers( serializer, serializer );
393 BTree<String, String> btree = new BTree<String, String>( config );
394
395 for ( char ch = 'a'; ch <= 'z'; ch++ )
396 {
397 btree.insert( String.valueOf( ch ), UUID.randomUUID().toString() );
398 }
399
400 btree.insert( String.valueOf( 'z' ), UUID.randomUUID().toString() );
401
402 TupleCursor<String, String> cursor = btree.browseFrom( "c" );
403 cursor.afterLast();
404
405 assertFalse( cursor.hasNext() );
406 assertTrue( cursor.hasPrev() );
407 assertEquals( "z", cursor.prev().getKey() );
408
409 assertEquals( "z", cursor.prev().getKey() );
410 assertEquals( "y", cursor.prev().getKey() );
411
412 cursor.beforeFirst();
413 assertEquals( "a", cursor.next().getKey() );
414
415 cursor.afterLast();
416 assertFalse( cursor.hasNext() );
417
418
419 cursor.next();
420 btree.close();
421 }
422
423
424 @Test(expected = NoSuchElementException.class)
425 public void testNextPrevKey() throws Exception
426 {
427 StringSerializer serializer = new StringSerializer();
428
429 BTreeConfiguration<String, String> config = new BTreeConfiguration<String, String>();
430 config.setAllowDuplicates( true );
431 config.setName( "master" );
432 config.setSerializers( serializer, serializer );
433 BTree<String, String> btree = new BTree<String, String>( config );
434
435 int i = 7;
436
437
438 for ( char ch = 'a'; ch <= 'z'; ch++ )
439 {
440 for ( int k = 0; k < i; k++ )
441 {
442 btree.insert( String.valueOf( ch ), String.valueOf( k ) );
443 }
444 }
445
446 TupleCursor<String, String> cursor = btree.browse();
447
448 assertTrue( cursor.hasNext() );
449 assertFalse( cursor.hasPrev() );
450
451 for ( int k = 0; k < 2; k++ )
452 {
453 assertEquals( "a", cursor.next().getKey() );
454 }
455
456 assertEquals( "a", cursor.next().getKey() );
457
458 Tuple<String, String> tuple = cursor.nextKey();
459
460 assertEquals( "b", tuple.getKey() );
461
462 for ( char ch = 'b'; ch < 'z'; ch++ )
463 {
464 assertEquals( String.valueOf( ch ), cursor.next().getKey() );
465 tuple = cursor.nextKey();
466 char t = ch;
467 assertEquals( String.valueOf( ++t ), tuple.getKey() );
468 }
469
470 for ( int k = 0; k < i; k++ )
471 {
472 assertEquals( "z", cursor.next().getKey() );
473 }
474
475 assertFalse( cursor.hasNextKey() );
476 assertTrue( cursor.hasPrevKey() );
477 tuple = cursor.prev();
478 assertEquals( "z", tuple.getKey() );
479 assertEquals( "6", tuple.getValue() );
480
481 for ( char ch = 'z'; ch > 'a'; ch-- )
482 {
483 char t = ch;
484 t--;
485
486 assertEquals( String.valueOf( ch ), cursor.prev().getKey() );
487
488 tuple = cursor.prevKey();
489
490 assertEquals( String.valueOf( t ), tuple.getKey() );
491 }
492
493 for ( int k = 5; k >= 0; k-- )
494 {
495 tuple = cursor.prev();
496 assertEquals( "a", tuple.getKey() );
497 assertEquals( String.valueOf( k ), tuple.getValue() );
498 }
499
500 assertTrue( cursor.hasNext() );
501 assertFalse( cursor.hasPrev() );
502 tuple = cursor.next();
503 assertEquals( "a", tuple.getKey() );
504 assertEquals( "0", tuple.getValue() );
505
506 cursor.close();
507
508 cursor = btree.browseFrom( "y" );
509 tuple = cursor.prevKey();
510 assertNotNull( tuple );
511 assertEquals( "y", tuple.getKey() );
512 assertEquals( "6", tuple.getValue() );
513 cursor.close();
514
515 cursor = btree.browse();
516 cursor.beforeFirst();
517 assertFalse( cursor.hasPrev() );
518
519 cursor.prev();
520 btree.close();
521 }
522
523
524
525
526
527
528
529
530 @Test
531 public void testMoveToNextAndPrevWithPageBoundaries() throws Exception
532 {
533 IntSerializer serializer = new IntSerializer();
534
535 BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
536 config.setAllowDuplicates( true );
537 config.setName( "master" );
538 config.setPageSize( 4 );
539 config.setSerializers( serializer, serializer );
540 BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
541
542 int i = 7;
543 for ( int k = 0; k < i; k++ )
544 {
545 btree.insert( k, k );
546 }
547
548
549 TupleCursor<Integer, Integer> cursor = btree.browseFrom( 3 );
550 Tuple<Integer, Integer> tuple = cursor.nextKey();
551
552 assertNotNull( tuple );
553 assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
554 assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
555 cursor.close();
556
557 cursor = btree.browseFrom( 3 );
558 tuple = cursor.prevKey();
559
560 assertNotNull( tuple );
561 assertEquals( Integer.valueOf( 2 ), tuple.getKey() );
562 assertEquals( Integer.valueOf( 2 ), tuple.getValue() );
563 cursor.close();
564
565
566 cursor = btree.browseFrom( 4 );
567 tuple = cursor.prevKey();
568
569 assertNotNull( tuple );
570 assertEquals( Integer.valueOf( 3 ), tuple.getKey() );
571 assertEquals( Integer.valueOf( 3 ), tuple.getValue() );
572
573 assertTrue( cursor.hasNext() );
574 tuple = cursor.next();
575 assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
576 assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
577
578 cursor.close();
579
580
581 cursor = btree.browseFrom( 5 );
582 tuple = cursor.nextKey();
583 assertFalse( cursor.hasNext() );
584 assertTrue( cursor.hasPrev() );
585
586 assertEquals( Integer.valueOf( 6 ), tuple.getKey() );
587 assertEquals( Integer.valueOf( 6 ), tuple.getValue() );
588 cursor.close();
589
590 cursor = btree.browse();
591 cursor.beforeFirst();
592 assertTrue( cursor.hasNext() );
593 assertFalse( cursor.hasPrev() );
594
595 tuple = cursor.next();
596
597 assertEquals( Integer.valueOf( 0 ), tuple.getKey() );
598 assertEquals( Integer.valueOf( 0 ), tuple.getValue() );
599 cursor.close();
600 btree.close();
601 }
602
603
604 @Test
605 public void testNextAfterPrev() throws Exception
606 {
607 IntSerializer serializer = new IntSerializer();
608
609 BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
610 config.setAllowDuplicates( true );
611 config.setName( "master" );
612 config.setPageSize( 4 );
613 config.setSerializers( serializer, serializer );
614 BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
615
616 int i = 7;
617 for ( int k = 0; k < i; k++ )
618 {
619 btree.insert( k, k );
620 }
621
622
623 TupleCursor<Integer, Integer> cursor = btree.browseFrom( 4 );
624
625 assertTrue( cursor.hasNext() );
626 Tuple<Integer, Integer> tuple = cursor.next();
627 assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
628 assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
629
630 assertTrue( cursor.hasPrev() );
631 tuple = cursor.prev();
632 assertEquals( Integer.valueOf( 3 ), tuple.getKey() );
633 assertEquals( Integer.valueOf( 3 ), tuple.getValue() );
634
635 assertTrue( cursor.hasNext() );
636 tuple = cursor.next();
637 assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
638 assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
639 cursor.close();
640
641 btree.close();
642 }
643
644
645
646
647
648
649
650 @Test
651 public void testMoveToNextAndTraverseBackward() throws Exception
652 {
653 IntSerializer serializer = new IntSerializer();
654
655 BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
656 config.setAllowDuplicates( true );
657 config.setName( "master" );
658 config.setPageSize( 8 );
659 config.setSerializers( serializer, serializer );
660 BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
661
662 int i = 5;
663 for ( int k = 0; k < i; k++ )
664 {
665 btree.insert( k, k );
666 }
667
668
669 TupleCursor<Integer, Integer> cursor = btree.browseFrom( 4 );
670 cursor.nextKey();
671
672 int currentKey = 4;
673 while ( cursor.hasPrev() )
674 {
675 assertEquals( Integer.valueOf( currentKey ), cursor.prev().getKey() );
676 currentKey--;
677 }
678
679 cursor.close();
680 btree.close();
681 }
682
683
684
685
686
687
688
689 @Test
690 public void testMoveToPrevAndTraverseForward() throws Exception
691 {
692 IntSerializer serializer = new IntSerializer();
693
694 BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
695 config.setAllowDuplicates( true );
696 config.setName( "master" );
697 config.setPageSize( 8 );
698 config.setSerializers( serializer, serializer );
699 BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
700
701 int i = 5;
702
703 for ( int k = 0; k < i; k++ )
704 {
705 btree.insert( k, k );
706 }
707
708
709 TupleCursor<Integer, Integer> cursor = btree.browseFrom( 0 );
710
711 int currentKey = 0;
712
713 while ( cursor.hasNext() )
714 {
715 assertEquals( Integer.valueOf( currentKey ), cursor.next().getKey() );
716 currentKey++;
717 }
718
719 cursor.close();
720 btree.close();
721 }
722 }