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;
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   * TODO BTreeDuplicateKeyTest.
44   *
45   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
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         // test backward move
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         // again forward
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         // check the return value when an existing value is added again
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         // We should have only one element in the tree (even if it has 2 values)
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         // add one more value for 'a'
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         // now move the cursor first
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         // Rebrowse
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         // now move the cursor first
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         // the key, 'z', has two values
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         // make sure it throws NoSuchElementException
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         // Insert keys from a to z with 7 values for each key
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         // make sure it throws NoSuchElementException
529         try
530         {
531             cursor.prev();
532         }
533         finally
534         {
535             btree.close();
536         }
537     }
538 
539 
540     /**
541      * Test for moving between two leaves. When moveToNextNonDuplicateKey is called
542      * and cursor is on the last element of the current leaf.
543      *
544      * @throws Exception
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         // 3 is the last element of the first leaf
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         // 4 is the first element of the second leaf
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         // test the extremes of the BTree instead of that of leaves
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         // 3 is the last element of the first leaf
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      * Test for moving after a key and traversing backwards.
664      *
665      * @throws Exception
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         // 4 is the last element in the tree
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      * Test for moving after a key and traversing backwards.
703      *
704      * @throws Exception
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         // 4 is the last element in the tree
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      * Test that a BTree which forbid duplicate values does not accept them
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 }