View Javadoc

1   /*
2    *   Licensed to the Apache Software Foundation (ASF) under one
3    *   or more contributor license agreements.  See the NOTICE file
4    *   distributed with this work for additional information
5    *   regarding copyright ownership.  The ASF licenses this file
6    *   to you under the Apache License, Version 2.0 (the
7    *   "License"); you may not use this file except in compliance
8    *   with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   *   Unless required by applicable law or agreed to in writing,
13   *   software distributed under the License is distributed on an
14   *   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *   KIND, either express or implied.  See the License for the
16   *   specific language governing permissions and limitations
17   *   under the License.
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   * TODO BTreeDuplicateKeyTest.
43   *
44   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
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         // test backward move
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         // again forward
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         // check the return value when an existing value is added again
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         // We should have only one element in the tree (even if it has 2 values)
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         // add one more value for 'a'
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         // now move the cursor first
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         // Rebrowse
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         // now move the cursor first
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         // the key, 'z', has two values
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         // make sure it throws NoSuchElementException
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         // Insert keys from a to z with 7 values for each key
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         // make sure it throws NoSuchElementException
519         cursor.prev();
520         btree.close();
521     }
522 
523 
524     /**
525      * Test for moving between two leaves. When moveToNextNonDuplicateKey is called
526      * and cursor is on the last element of the current leaf.
527      *
528      * @throws Exception
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         // 3 is the last element of the first leaf
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         // 4 is the first element of the second leaf
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         // test the extremes of the BTree instead of that of leaves
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         // 3 is the last element of the first leaf
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      * Test for moving after a key and traversing backwards.
647      *
648      * @throws Exception
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         // 4 is the last element in the tree
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      * Test for moving after a key and traversing backwards.
686      *
687      * @throws Exception
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         // 4 is the last element in the tree
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 }