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