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.assertTrue;
25  import static org.junit.Assert.fail;
26  
27  import java.io.IOException;
28  
29  import org.apache.directory.mavibot.btree.BorrowedFromLeftResult;
30  import org.apache.directory.mavibot.btree.BorrowedFromRightResult;
31  import org.apache.directory.mavibot.btree.DeleteResult;
32  import org.apache.directory.mavibot.btree.InsertResult;
33  import org.apache.directory.mavibot.btree.NotPresentResult;
34  import org.apache.directory.mavibot.btree.Page;
35  import org.apache.directory.mavibot.btree.RemoveResult;
36  import org.apache.directory.mavibot.btree.Tuple;
37  import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
38  import org.apache.directory.mavibot.btree.serializer.LongSerializer;
39  import org.apache.directory.mavibot.btree.serializer.StringSerializer;
40  import org.junit.After;
41  import org.junit.Before;
42  import org.junit.Test;
43  
44  
45  /**
46   * A unit test class for Leaf
47   * 
48   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
49   */
50  public class LeafTest
51  {
52      private BTree<Long, String> btree = null;
53  
54  
55      /**
56       * Create a btree
57       */
58      @Before
59      public void setup() throws IOException
60      {
61          btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
62          btree.setPageSize( 8 );
63      }
64  
65  
66      @After
67      public void shutdown() throws IOException
68      {
69          btree.close();
70      }
71  
72  
73      /**
74       * A helper method to insert elements in a Leaf
75       * @throws IOException 
76       */
77      private Leaf<Long, String> insert( Leaf<Long, String> leaf, long key, String value ) throws IOException
78      {
79          InsertResult<Long, String> result = leaf.insert( 1L, key, value );
80  
81          return ( Leaf<Long, String> ) ( (org.apache.directory.mavibot.btree.ModifyResult<Long, String> ) result ).getModifiedPage();
82      }
83  
84  
85      /**
86       * Test that deleting an entry from an empty page returns a NOT_PRESENT result
87       * @throws IOException
88       */
89      @Test
90      public void testDeleteFromEmptyLeaf() throws IOException
91      {
92          Leaf<Long, String> leaf = new Leaf<Long, String>( btree );
93  
94          DeleteResult<Long, String> result = leaf.delete( 1L, 1L, null, null, -1 );
95  
96          assertEquals( NotPresentResult.NOT_PRESENT, result );
97      }
98  
99  
100     /**
101      * Test that deleting an entry which is not present in the leaf works
102      * @throws IOException
103      */
104     @Test
105     public void testDeleteNotPresentElementFromRootLeaf() throws IOException
106     {
107         Leaf<Long, String> leaf = new Leaf<Long, String>( btree );
108         leaf = insert( leaf, 1L, "v1" );
109         leaf = insert( leaf, 2L, "v2" );
110         leaf = insert( leaf, 3L, "v3" );
111         leaf = insert( leaf, 4L, "v4" );
112 
113         DeleteResult<Long, String> result = leaf.delete( 2L, 5L, null, null, -1 );
114 
115         assertEquals( NotPresentResult.NOT_PRESENT, result );
116     }
117 
118 
119     /**
120      * Test that deleting an entry which is present in the leaf works
121      * @throws IOException
122      */
123     @Test
124     public void testDeletePresentElementFromRootLeaf() throws IOException
125     {
126         Leaf<Long, String> leaf = new Leaf<Long, String>( btree );
127         leaf = insert( leaf, 1L, "v1" );
128         leaf = insert( leaf, 2L, "v2" );
129         leaf = insert( leaf, 3L, "v3" );
130         leaf = insert( leaf, 4L, "v4" );
131 
132         DeleteResult<Long, String> result = leaf.delete( 4L, 3L, null, null, -1 );
133 
134         assertTrue( result instanceof RemoveResult );
135 
136         Tuple<Long, String> removedElement = ( (org.apache.directory.mavibot.btree.RemoveResult<Long, String> ) result ).getRemovedElement();
137         Page<Long, String> newLeaf = ( (org.apache.directory.mavibot.btree.RemoveResult<Long, String> ) result ).getModifiedPage();
138 
139         assertEquals( Long.valueOf( 3L ), removedElement.getKey() );
140         assertEquals( "v3", removedElement.getValue() );
141         assertEquals( 3, newLeaf.getNbElems() );
142 
143         try
144         {
145             assertEquals( "v1", newLeaf.get( 1L ) );
146             assertEquals( "v2", newLeaf.get( 2L ) );
147             assertEquals( "v4", newLeaf.get( 4L ) );
148         }
149         catch ( KeyNotFoundException knfe )
150         {
151             fail();
152         }
153 
154         try
155         {
156             newLeaf.get( 3L );
157             fail();
158         }
159         catch ( KeyNotFoundException knfe )
160         {
161             // Expected
162         }
163     }
164 
165 
166     /**
167      * Test that deleting the first element return the correct result
168      * @throws IOException
169      */
170     @Test
171     public void testDeleteFirstElementFromRootLeaf() throws IOException
172     {
173         Leaf<Long, String> leaf = new Leaf<Long, String>( btree );
174         leaf = insert( leaf, 1L, "v1" );
175         leaf = insert( leaf, 2L, "v2" );
176         leaf = insert( leaf, 3L, "v3" );
177         leaf = insert( leaf, 4L, "v4" );
178 
179         DeleteResult<Long, String> result = leaf.delete( 4L, 1L, null, null, -1 );
180 
181         assertTrue( result instanceof RemoveResult );
182 
183         RemoveResult<Long, String> removeResult = (org.apache.directory.mavibot.btree.RemoveResult<Long, String> ) result;
184 
185         Tuple<Long, String> removedElement = removeResult.getRemovedElement();
186         Page<Long, String> newLeaf = removeResult.getModifiedPage();
187 
188         assertEquals( Long.valueOf( 1L ), removedElement.getKey() );
189         assertEquals( "v1", removedElement.getValue() );
190         assertEquals( 3, newLeaf.getNbElems() );
191 
192         try
193         {
194             newLeaf.get( 1L );
195             fail();
196         }
197         catch ( KeyNotFoundException knfe )
198         {
199             // expected
200         }
201 
202         try
203         {
204             assertEquals( "v2", newLeaf.get( 2L ) );
205             assertEquals( "v3", newLeaf.get( 3L ) );
206             assertEquals( "v4", newLeaf.get( 4L ) );
207         }
208         catch ( KeyNotFoundException knfe )
209         {
210             fail();
211         }
212     }
213 
214 
215     /**
216      * Check that deleting an element from a leaf with N/2 element works when we borrow
217      * an element in a left page with more than N/2 elements.
218      * The BTree contains :
219      *            +--[1, 2, 3, 4, 5]
220      * [6, 10]-+--[6, 7, 8, 9]
221      *            +--[10, 11, 12, 13]
222      * @throws IOException 
223      */
224     @Test
225     public void testDeleteBorrowingFromLeftSibling() throws IOException
226     {
227         Node<Long, String> parent = new Node<Long, String>( btree, 1L, 2 );
228         Leaf<Long, String> left = new Leaf<Long, String>( btree );
229         Leaf<Long, String> target = new Leaf<Long, String>( btree );
230         Leaf<Long, String> right = new Leaf<Long, String>( btree );
231 
232         // Fill the left page
233         left = insert( left, 1L, "v1" );
234         left = insert( left, 2L, "v2" );
235         left = insert( left, 3L, "v3" );
236         left = insert( left, 4L, "v4" );
237         left = insert( left, 5L, "v5" );
238 
239         // Fill the target page
240         target = insert( target, 6L, "v6" );
241         target = insert( target, 7L, "v7" );
242         target = insert( target, 8L, "v8" );
243         target = insert( target, 9L, "v9" );
244 
245         // Fill the right page
246         right = insert( right, 10L, "v10" );
247         right = insert( right, 11L, "v11" );
248         right = insert( right, 12L, "v12" );
249         right = insert( right, 13L, "v13" );
250 
251         parent.children[0] = left;
252         parent.children[1] = target;
253         parent.children[2] = right;
254 
255         // Update the parent
256         parent.keys[0] = 6L;
257         parent.keys[1] = 10L;
258 
259         // Now, delete the element from the target page
260         DeleteResult<Long, String> result = target.delete( 2L, 7L, null, parent, 1 );
261 
262         assertTrue( result instanceof BorrowedFromLeftResult );
263 
264         BorrowedFromLeftResult<Long, String> borrowed = (org.apache.directory.mavibot.btree.BorrowedFromLeftResult<Long, String> ) result;
265         Tuple<Long, String> removedKey = borrowed.getRemovedElement();
266 
267         assertEquals( Long.valueOf( 7L ), removedKey.getKey() );
268 
269         // Check the modified leaf
270         Leaf<Long, String> newLeaf = ( Leaf<Long, String> ) borrowed.getModifiedPage();
271 
272         assertEquals( 4, newLeaf.nbElems );
273         assertEquals( Long.valueOf( 5L ), newLeaf.keys[0] );
274         assertEquals( Long.valueOf( 6L ), newLeaf.keys[1] );
275         assertEquals( Long.valueOf( 8L ), newLeaf.keys[2] );
276         assertEquals( Long.valueOf( 9L ), newLeaf.keys[3] );
277 
278         // Check the sibling
279         Leaf<Long, String> leftSibling = ( Leaf<Long, String> ) borrowed.getModifiedSibling();
280 
281         assertEquals( 4, leftSibling.nbElems );
282         assertEquals( Long.valueOf( 1L ), leftSibling.keys[0] );
283         assertEquals( Long.valueOf( 2L ), leftSibling.keys[1] );
284         assertEquals( Long.valueOf( 3L ), leftSibling.keys[2] );
285         assertEquals( Long.valueOf( 4L ), leftSibling.keys[3] );
286     }
287 
288 
289     /**
290      * Check that deleting an element from a leaf with N/2 element works when we borrow
291      * an element in a right page with more than N/2 elements
292      * @throws IOException 
293      */
294     @Test
295     public void testDeleteBorrowingFromRightSibling() throws IOException
296     {
297         Node<Long, String> parent = new Node<Long, String>( btree, 1L, 2 );
298         Leaf<Long, String> left = new Leaf<Long, String>( btree );
299         Leaf<Long, String> target = new Leaf<Long, String>( btree );
300         Leaf<Long, String> right = new Leaf<Long, String>( btree );
301 
302         // Fill the left page
303         left = insert( left, 1L, "v1" );
304         left = insert( left, 2L, "v2" );
305         left = insert( left, 3L, "v3" );
306         left = insert( left, 4L, "v4" );
307 
308         // Fill the target page
309         target = insert( target, 6L, "v6" );
310         target = insert( target, 7L, "v7" );
311         target = insert( target, 8L, "v8" );
312         target = insert( target, 9L, "v9" );
313 
314         // Fill the right page
315         right = insert( right, 10L, "v10" );
316         right = insert( right, 11L, "v11" );
317         right = insert( right, 12L, "v12" );
318         right = insert( right, 13L, "v13" );
319         right = insert( right, 14L, "v14" );
320 
321         parent.children[0] = left;
322         parent.children[1] = target;
323         parent.children[2] = right;
324 
325         // Update the parent
326         parent.keys[0] = 6L;
327         parent.keys[1] = 10L;
328 
329         // Now, delete the element from the target page
330         DeleteResult<Long, String> result = target.delete( 2L, 7L, null, parent, 1 );
331 
332         assertTrue( result instanceof BorrowedFromRightResult );
333 
334         BorrowedFromRightResult<Long, String> borrowed = (org.apache.directory.mavibot.btree.BorrowedFromRightResult<Long, String> ) result;
335         assertEquals( Long.valueOf( 11L ), borrowed.getModifiedSibling().getKey( 0 ) );
336         Tuple<Long, String> removedKey = borrowed.getRemovedElement();
337 
338         assertEquals( Long.valueOf( 7L ), removedKey.getKey() );
339 
340         // Check the modified leaf
341         Leaf<Long, String> newLeaf = ( Leaf<Long, String> ) borrowed.getModifiedPage();
342 
343         assertEquals( 4, newLeaf.nbElems );
344         assertEquals( Long.valueOf( 6L ), newLeaf.keys[0] );
345         assertEquals( Long.valueOf( 8L ), newLeaf.keys[1] );
346         assertEquals( Long.valueOf( 9L ), newLeaf.keys[2] );
347         assertEquals( Long.valueOf( 10L ), newLeaf.keys[3] );
348 
349         // Check the sibling
350         Leaf<Long, String> rightSibling = ( Leaf<Long, String> ) borrowed.getModifiedSibling();
351 
352         assertEquals( 4, rightSibling.nbElems );
353         assertEquals( Long.valueOf( 11L ), rightSibling.keys[0] );
354         assertEquals( Long.valueOf( 12L ), rightSibling.keys[1] );
355         assertEquals( Long.valueOf( 13L ), rightSibling.keys[2] );
356         assertEquals( Long.valueOf( 14L ), rightSibling.keys[3] );
357     }
358 
359 
360     /**
361      * Check that deleting an element from a leaf with N/2 element works when we merge
362      * it with one of its sibling, if both has N/2 elements
363      * @throws IOException 
364      */
365     @Test
366     public void testDeleteMergeWithSibling() throws IOException
367     {
368         Node<Long, String> parent = new Node<Long, String>( btree, 1L, 2 );
369         Leaf<Long, String> left = new Leaf<Long, String>( btree );
370         Leaf<Long, String> target = new Leaf<Long, String>( btree );
371         Leaf<Long, String> right = new Leaf<Long, String>( btree );
372 
373         // Fill the left page
374         left = insert( left, 1L, "v1" );
375         left = insert( left, 2L, "v2" );
376         left = insert( left, 3L, "v3" );
377         left = insert( left, 4L, "v4" );
378 
379         // Fill the target page
380         target = insert( target, 5L, "v5" );
381         target = insert( target, 6L, "v6" );
382         target = insert( target, 7L, "v7" );
383         target = insert( target, 8L, "v8" );
384 
385         // Fill the right page
386         right = insert( right, 9L, "v9" );
387         right = insert( right, 10L, "v10" );
388         right = insert( right, 11L, "v11" );
389         right = insert( right, 12L, "v12" );
390 
391         parent.children[0] = left;
392         parent.children[1] = target;
393         parent.children[2] = right;
394 
395         // Update the parent
396         parent.keys[0] = 5L;
397         parent.keys[1] = 9L;
398 
399         // Now, delete the element from the target page
400         DeleteResult<Long, String> result = target.delete( 2L, 7L, null, parent, 1 );
401 
402         assertTrue( result instanceof MergedWithSiblingResult );
403 
404         MergedWithSiblingResult<Long, String> merged = ( MergedWithSiblingResult<Long, String> ) result;
405         Tuple<Long, String> removedKey = merged.getRemovedElement();
406 
407         assertEquals( Long.valueOf( 7L ), removedKey.getKey() );
408 
409         // Check the modified leaf
410         Leaf<Long, String> newLeaf = ( Leaf<Long, String> ) merged.getModifiedPage();
411 
412         assertEquals( 7, newLeaf.nbElems );
413         assertEquals( Long.valueOf( 1L ), newLeaf.keys[0] );
414         assertEquals( Long.valueOf( 2L ), newLeaf.keys[1] );
415         assertEquals( Long.valueOf( 3L ), newLeaf.keys[2] );
416         assertEquals( Long.valueOf( 4L ), newLeaf.keys[3] );
417         assertEquals( Long.valueOf( 5L ), newLeaf.keys[4] );
418         assertEquals( Long.valueOf( 6L ), newLeaf.keys[5] );
419         assertEquals( Long.valueOf( 8L ), newLeaf.keys[6] );
420     }
421 
422 
423     /**
424      * Test the findPos() method
425      * @throws Exception
426      */
427     @Test
428     public void testFindPos() throws Exception
429     {
430         Leaf<Long, String> leaf = new Leaf<Long, String>( btree );
431 
432         // Inject the values
433         for ( long i = 0; i < 8; i++ )
434         {
435             long value = i + i + 1;
436             leaf = ( Leaf<Long, String> ) ( (org.apache.directory.mavibot.btree.ModifyResult<Long, String> ) leaf.insert( 0L, value, "V" + value ) )
437                 .getModifiedPage();
438         }
439 
440         // Check the findPos() method now
441         for ( long i = 0; i < 17; i++ )
442         {
443             if ( i % 2 == 1 )
444             {
445                 assertEquals( -( i / 2 + 1 ), leaf.findPos( i ) );
446             }
447             else
448             {
449                 assertEquals( i / 2, leaf.findPos( i ) );
450             }
451         }
452     }
453 }