You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by el...@apache.org on 2013/09/30 08:32:28 UTC
svn commit: r1527458 [13/14] - in /directory/mavibot/trunk/mavibot: img/
src/main/java/org/apache/directory/mavibot/btree/
src/main/java/org/apache/directory/mavibot/btree/managed/
src/main/java/org/apache/directory/mavibot/btree/memory/ src/main/java/...
Added: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/InMemoryBTreeTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/InMemoryBTreeTest.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/InMemoryBTreeTest.java (added)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/InMemoryBTreeTest.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,1936 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.memory;
+
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.io.IOException;
+import java.lang.reflect.Array;
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+
+import org.apache.directory.mavibot.btree.Cursor;
+import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
+import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
+import org.apache.directory.mavibot.btree.serializer.IntSerializer;
+import org.apache.directory.mavibot.btree.serializer.LongSerializer;
+import org.apache.directory.mavibot.btree.serializer.StringSerializer;
+import org.junit.Ignore;
+import org.junit.Test;
+
+
+/**
+ * A unit test class for in-memory BTree
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class InMemoryBTreeTest
+{
+ // Some values to inject in a btree
+ private static int[] sortedValues = new int[]
+ {
+ 0, 1, 2, 4, 5, 6, 8, 9, 11, 12,
+ 13, 14, 16, 19, 21, 22, 23, 25, 26, 28,
+ 30, 31, 32, 34, 36, 37, 38, 39, 41, 42,
+ 44, 45, 47, 50, 52, 53, 54, 55, 56, 58,
+ 59, 60, 63, 64, 67, 68, 70, 72, 73, 74,
+ 76, 77, 79, 80, 81, 82, 85, 88, 89, 90,
+ 92, 93, 95, 97, 98, 100, 101, 102, 103, 104,
+ 105, 106, 107, 109, 110, 111, 112, 117, 118, 120,
+ 121, 128, 129, 130, 131, 132, 135, 136, 137, 138,
+ 139, 140, 141, 142, 143, 146, 147, 148, 149, 150,
+ 152, 154, 156, 160, 161, 162, 163, 165, 167, 168,
+ 169, 171, 173, 174, 175, 176, 177, 178, 179, 180,
+ 181, 182, 183, 189, 190, 193, 194, 195, 199, 200,
+ 202, 203, 205, 206, 207, 208, 209, 210, 212, 215,
+ 216, 217, 219, 220, 222, 223, 224, 225, 226, 227,
+ 228, 230, 231, 235, 236, 238, 239, 241, 242, 243,
+ 245, 246, 247, 249, 250, 251, 252, 254, 256, 257,
+ 258, 259, 261, 262, 263, 264, 266, 268, 272, 273,
+ 274, 276, 277, 278, 279, 282, 283, 286, 289, 290,
+ 292, 293, 294, 296, 298, 299, 300, 301, 303, 305,
+ 308, 310, 316, 317, 318, 319, 322, 323, 324, 326,
+ 327, 329, 331, 333, 334, 335, 336, 337, 338, 339,
+ 340, 341, 346, 347, 348, 349, 350, 351, 352, 353,
+ 355, 356, 357, 358, 359, 361, 365, 366, 373, 374,
+ 375, 379, 380, 381, 382, 384, 385, 387, 388, 389,
+ 390, 392, 393, 395, 396, 397, 398, 399, 400, 401,
+ 404, 405, 406, 407, 410, 411, 412, 416, 417, 418,
+ 420, 421, 422, 424, 426, 427, 428, 430, 431, 432,
+ 433, 436, 439, 441, 443, 444, 445, 446, 447, 448,
+ 449, 450, 451, 452, 453, 454, 455, 456, 458, 459,
+ 464, 466, 469, 470, 471, 472, 475, 477, 478, 482,
+ 483, 484, 485, 486, 488, 490, 491, 492, 493, 495,
+ 496, 497, 500, 502, 503, 504, 505, 506, 507, 509,
+ 510, 514, 516, 518, 520, 521, 523, 524, 526, 527,
+ 528, 529, 530, 532, 533, 535, 538, 539, 540, 542,
+ 543, 544, 546, 547, 549, 550, 551, 553, 554, 558,
+ 559, 561, 563, 564, 566, 567, 568, 569, 570, 571,
+ 572, 576, 577, 578, 580, 582, 583, 586, 588, 589,
+ 590, 592, 593, 596, 597, 598, 599, 600, 601, 604,
+ 605, 606, 607, 609, 610, 613, 615, 617, 618, 619,
+ 620, 621, 626, 627, 628, 631, 632, 633, 635, 636,
+ 637, 638, 639, 640, 641, 643, 645, 647, 648, 649,
+ 650, 651, 652, 653, 655, 656, 658, 659, 660, 662,
+ 666, 669, 673, 674, 675, 676, 677, 678, 680, 681,
+ 682, 683, 685, 686, 687, 688, 689, 690, 691, 692,
+ 693, 694, 696, 698, 699, 700, 701, 705, 708, 709,
+ 711, 713, 714, 715, 719, 720, 723, 725, 726, 727,
+ 728, 731, 732, 733, 734, 735, 736, 739, 740, 743,
+ 744, 745, 746, 747, 749, 750, 752, 753, 762, 763,
+ 765, 766, 768, 770, 772, 773, 774, 776, 777, 779,
+ 782, 784, 785, 788, 790, 791, 793, 794, 795, 798,
+ 799, 800, 801, 803, 804, 805, 808, 810, 812, 813,
+ 814, 816, 818, 821, 822, 823, 824, 827, 828, 829,
+ 831, 832, 833, 834, 835, 837, 838, 839, 840, 843,
+ 846, 847, 849, 852, 853, 854, 856, 857, 859, 860,
+ 863, 864, 865, 866, 867, 868, 869, 872, 873, 877,
+ 880, 881, 882, 883, 887, 888, 889, 890, 891, 894,
+ 895, 897, 898, 899, 902, 904, 905, 907, 908, 910,
+ 911, 912, 915, 916, 917, 918, 919, 923, 925, 926,
+ 927, 928, 929, 930, 932, 935, 936, 937, 938, 939,
+ 944, 945, 947, 952, 953, 954, 955, 956, 957, 958,
+ 960, 967, 970, 971, 972, 974, 975, 976, 978, 979,
+ 980, 981, 983, 984, 985, 987, 988, 989, 991, 995
+ };
+
+
+ /**
+ * Checks the created BTree contains the expected values
+ */
+ private boolean checkTreeLong( Set<Long> expected, BTree<Long, String> btree ) throws IOException
+ {
+ // We loop on all the expected value to see if they have correctly been inserted
+ // into the btree
+ for ( Long key : expected )
+ {
+ try
+ {
+ btree.get( key );
+ }
+ catch ( KeyNotFoundException knfe )
+ {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+
+ /**
+ * Test the insertion of elements in a BTree. We will try 1000 times to insert 1000
+ * random elements in [0..1024], and check every tree to see if all the added elements
+ * are present. This pretty much validate the the insertion, assuming that due to the
+ * randomization of the injected values, we will statically meet all the use cases.
+ * @throws Exception
+ */
+ @Test
+ public void testPageInsert() throws Exception
+ {
+ Set<Long> expected = new HashSet<Long>();
+ List<Long> added = new ArrayList<Long>();
+
+ Random random = new Random( System.nanoTime() );
+
+ int nbError = 0;
+
+ long l1 = System.currentTimeMillis();
+ int n = 0;
+ long delta = l1;
+ int nbTrees = 1000;
+ int nbElems = 1000;
+
+ for ( int j = 0; j < nbTrees; j++ )
+ {
+ BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
+ btree.setPageSize( 32 );
+
+ for ( int i = 0; i < nbElems; i++ )
+ {
+ Long key = ( long ) random.nextInt( 1024 );
+ String value = "V" + key;
+ expected.add( key );
+ added.add( key );
+
+ //System.out.println( "Adding " + i + "th : " + key );
+
+ try
+ {
+ btree.insert( key, value );
+ }
+ catch ( Exception e )
+ {
+ e.printStackTrace();
+ System.out.println( btree );
+ System.out.println( "Error while adding " + value );
+ nbError++;
+ return;
+ }
+ }
+
+ assertTrue( checkTreeLong( expected, btree ) );
+
+ /* For debug only
+ if ( !checkTree( expected, btree ) )
+ {
+ boolean isFirst = true;
+
+ for ( Long key : added )
+ {
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ System.out.print( ", " );
+ }
+
+ System.out.print( key );
+ }
+ }
+ */
+
+ if ( j % 10000 == 0 )
+ {
+ if ( n > 0 )
+ {
+ long t0 = System.currentTimeMillis();
+ System.out.println( "Delta" + n + ": " + ( t0 - delta ) );
+ delta = t0;
+ }
+
+ n++;
+ }
+
+ expected.clear();
+ added.clear();
+
+ btree.close();
+ }
+
+ long l2 = System.currentTimeMillis();
+
+ System.out.println( "Delta : " + ( l2 - l1 ) + ", nbError = " + nbError
+ + ", Nb insertion per second : " + ( nbTrees * nbElems * 1000 ) / ( l2 - l1 ) );
+ }
+
+
+ /**
+ * Test the deletion of elements in a BTree. We will try 1000 times to delete 1000
+ * random elements in [0..1024], and check every tree to see if all the removed elements
+ * are absent. This pretty much validate the the deletion operation is valid, assuming
+ * that due to the randomization of the deleted values, we will statically meet all the
+ * use cases.
+ * @throws Exception
+ */
+ @Test
+ public void testPageDeleteRandom() throws IOException
+ {
+ Set<Long> expected = new HashSet<Long>();
+ List<Long> added = new ArrayList<Long>();
+
+ Random random = new Random( System.nanoTime() );
+
+ int nbError = 0;
+
+ long l1 = System.currentTimeMillis();
+ int n = 0;
+ long delta = l1;
+ int nbTrees = 1000;
+ int nbElems = 1000;
+
+ for ( int j = 0; j < nbTrees; j++ )
+ {
+ BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
+ btree.setPageSize( 8 );
+
+ for ( int i = 0; i < nbElems; i++ )
+ {
+ Long key = ( long ) random.nextInt( 1024 );
+ String value = "V" + key;
+ expected.add( key );
+ added.add( key );
+
+ //System.out.println( "Adding " + i + "th : " + key );
+
+ try
+ {
+ btree.insert( key, value );
+ }
+ catch ( Exception e )
+ {
+ e.printStackTrace();
+ System.out.println( btree );
+ System.out.println( "Error while adding " + value );
+ nbError++;
+ return;
+ }
+ }
+
+ assertTrue( checkTreeLong( expected, btree ) );
+
+ // Now, delete the elements
+ /*
+ boolean isFirst = true;
+
+ for ( long element : added )
+ {
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ System.out.print( ", " );
+ }
+
+ System.out.print( element );
+ }
+
+ //System.out.println( "\n--------------------" );
+ */
+
+ //int i = 0;
+
+ for ( long element : expected )
+ {
+ //System.out.println( "Deleting #" + i + " : " + element );
+ //i++;
+ //System.out.println( btree );
+ Tuple<Long, String> tuple = btree.delete( element );
+
+ if ( tuple == null )
+ {
+ System.out.println( btree );
+ }
+
+ assertEquals( Long.valueOf( element ), tuple.getKey() );
+
+ checkNull( btree, element );
+
+ //System.out.println( "" );
+ }
+
+ if ( j % 10000 == 0 )
+ {
+ if ( n > 0 )
+ {
+ long t0 = System.currentTimeMillis();
+ System.out.println( "Delta" + n + ": " + ( t0 - delta ) );
+ delta = t0;
+ }
+
+ n++;
+
+ }
+
+ expected.clear();
+ added.clear();
+
+ btree.close();
+ }
+
+ long l2 = System.currentTimeMillis();
+
+ System.out.println( "Delta : " + ( l2 - l1 ) + ", nbError = " + nbError
+ + ", Nb deletion per second : " + ( nbTrees * nbElems * 1000 ) / ( l2 - l1 ) );
+ }
+
+
+ @Test
+ public void testDeleteDebug() throws IOException
+ {
+ long[] values = new long[]
+ {
+ 148, 746, 525, 327, 1, 705, 171, 1023, 769, 1021,
+ 128, 772, 744, 771, 925, 884, 346, 519, 989, 350,
+ 649, 895, 464, 164, 190, 298, 203, 69, 483, 38,
+ 266, 83, 88, 285, 879, 342, 231, 432, 722, 432,
+ 258, 307, 237, 151, 43, 36, 135, 166, 325, 886,
+ 878, 307, 925, 835, 800, 895, 519, 947, 703, 27,
+ 324, 668, 40, 943, 804, 230, 223, 584, 828, 575,
+ 69, 955, 344, 325, 896, 423, 855, 783, 225, 447,
+ 28, 23, 262, 679, 782, 517, 412, 878, 641, 940,
+ 368, 245, 1005, 226, 939, 320, 396, 437, 373, 61
+ };
+
+ BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
+ btree.setPageSize( 8 );
+
+ for ( long value : values )
+ {
+ String strValue = "V" + value;
+
+ try
+ {
+ btree.insert( value, strValue );
+ }
+ catch ( Exception e )
+ {
+ e.printStackTrace();
+ System.out.println( btree );
+ System.out.println( "Error while adding " + value );
+ return;
+ }
+ }
+
+ long[] deletes = new long[]
+ {
+ 1,
+ 828,
+ 285,
+ 804,
+ 258,
+ 262,
+ };
+
+ for ( long value : deletes )
+ {
+ Tuple<Long, String> tuple = btree.delete( value );
+
+ if ( tuple != null )
+ {
+ assertEquals( Long.valueOf( value ), tuple.getKey() );
+ }
+
+ checkNull( btree, value );
+ }
+
+ btree.close();
+ }
+
+
+ /**
+ * Test the deletion of elements from a BTree.
+ */
+ @Test
+ public void testPageDelete() throws Exception
+ {
+ Set<Long> expected = new HashSet<Long>();
+ List<Long> added = new ArrayList<Long>();
+
+ Random random = new Random( System.nanoTime() );
+
+ BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
+ btree.setPageSize( 8 );
+
+ // Insert some values
+ for ( int i = 0; i < 8; i++ )
+ {
+ Long key = ( long ) random.nextInt( 1024 );
+ String value = "V" + key;
+ added.add( key );
+
+ try
+ {
+ btree.insert( key, value );
+ }
+ catch ( Exception e )
+ {
+ e.printStackTrace();
+ System.out.println( btree );
+ System.out.println( "Error while adding " + value );
+ return;
+ }
+ }
+
+ assertTrue( checkTreeLong( expected, btree ) );
+
+ // Now, delete entries
+ for ( long key : added )
+ {
+ //System.out.println( "Removing " + key + " from " + btree );
+ try
+ {
+ btree.delete( key );
+ }
+ catch ( Exception e )
+ {
+ e.printStackTrace();
+ System.out.println( btree );
+ System.out.println( "Error while deleting " + key );
+ return;
+ }
+
+ assertTrue( checkTreeLong( expected, btree ) );
+ }
+
+ btree.close();
+ }
+
+
+ /**
+ * This test is used to debug some corner cases.
+ * We don't run it except to check a special condition
+ */
+ @Test
+ @Ignore
+ public void testPageInsertDebug() throws Exception
+ {
+ BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
+ btree.setPageSize( 4 );
+
+ Long[] elems = new Long[]
+ {
+ 235L, 135L, 247L, 181L, 12L, 112L, 117L, 253L,
+ 37L, 158L, 56L, 118L, 184L, 101L, 173L, 126L,
+ 61L, 81L, 140L, 173L, 32L, 163L, 224L, 114L,
+ 133L, 18L, 14L, 82L, 107L, 219L, 244L, 255L,
+ 6L, 103L, 170L, 151L, 134L, 196L, 155L, 97L,
+ 80L, 122L, 89L, 253L, 33L, 101L, 56L, 168L,
+ 253L, 187L, 99L, 58L, 151L, 206L, 34L, 96L,
+ 20L, 188L, 143L, 150L, 76L, 111L, 234L, 66L,
+ 12L, 194L, 164L, 190L, 19L, 192L, 161L, 147L,
+ 92L, 89L, 237L, 187L, 250L, 13L, 233L, 34L,
+ 187L, 232L, 248L, 237L, 129L, 1L, 233L, 252L,
+ 18L, 98L, 56L, 121L, 162L, 233L, 29L, 48L,
+ 176L, 48L, 182L, 130L
+ };
+
+ int size = 0;
+ for ( Long elem : elems )
+ {
+ size++;
+ String value = "V" + elem;
+ btree.insert( elem, value );
+
+ System.out.println( "Adding " + elem + " :\n" + btree );
+
+ for ( int i = 0; i < size; i++ )
+ {
+ try
+ {
+ btree.get( elems[i] );
+ }
+ catch ( KeyNotFoundException knfe )
+ {
+ System.out.println( "Bad tree, missing " + elems[i] + ", " + btree );
+ }
+ }
+
+ if ( size == 27 )
+ {
+ System.out.println( btree );
+ }
+ //System.out.println( "added " + elem + ":\n" + btree );
+ }
+
+ //System.out.println( btree );
+
+ btree.close();
+ }
+
+
+ /*
+ @Test
+ public void testPageRemove() throws Exception
+ {
+ Long[] keys = new Long[]{ 101L, 113L, 20L, 72L, 215L, 239L, 108L, 21L };
+
+ BTree<Long, String> btree = new BTree<Long, String>( new LongComparator(), 8 );
+ System.out.println( btree );
+
+ for ( Long key : keys )
+ {
+ btree.insert( key, "V" + key );
+ }
+
+ System.out.println( btree );
+
+ // Remove from the left
+ btree.remove( 20L );
+ System.out.println( btree );
+
+ // Remove from the right
+ btree.remove( 239L );
+ System.out.println( btree );
+
+ // Remove from the middle
+ btree.remove( 72L );
+ System.out.println( btree );
+
+ // Remove all the remaining elements
+ btree.remove( 101L );
+ System.out.println( btree );
+ btree.remove( 108L );
+ System.out.println( btree );
+ btree.remove( 215L );
+ System.out.println( btree );
+ btree.remove( 113L );
+ System.out.println( btree );
+ btree.remove( 21L );
+ System.out.println( btree );
+
+ btree.close();
+ }
+ */
+
+ /**
+ * Test the browse method going forward
+ * @throws Exception
+ */
+ @Test
+ public void testBrowseForward() throws Exception
+ {
+ // Create a BTree with pages containing 8 elements
+ BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
+ btree.setPageSize( 8 );
+
+ // Inject the values
+ for ( int value : sortedValues )
+ {
+ String strValue = "V" + value;
+
+ btree.insert( value, strValue );
+ }
+
+ // Check that the tree contains all the values
+ for ( int key : sortedValues )
+ {
+ String value = btree.get( key );
+
+ assertNotNull( value );
+ }
+
+ // Browse starting at position 10
+ int pos = 10;
+ Cursor<Integer, String> cursor = btree.browseFrom( sortedValues[pos] );
+
+ while ( cursor.hasNext() )
+ {
+ Tuple<Integer, String> tuple = cursor.next();
+
+ assertNotNull( tuple );
+ Integer val = sortedValues[pos];
+ Integer res = tuple.getKey();
+ assertEquals( val, res );
+ pos++;
+ }
+
+ cursor.close();
+
+ // Now, start on a non existing key (7)
+ cursor = btree.browseFrom( 7 );
+
+ // We should start reading values superior to 7, so value 8 at position 6 in the array
+ pos = 6;
+
+ while ( cursor.hasNext() )
+ {
+ Tuple<Integer, String> tuple = cursor.next();
+
+ assertNotNull( tuple );
+ Integer val = sortedValues[pos];
+ Integer res = tuple.getKey();
+ assertEquals( val, res );
+ pos++;
+ }
+
+ cursor.close();
+
+ // Last, let's browse with no key, we should get all the values
+ cursor = btree.browse();
+
+ pos = 0;
+
+ while ( cursor.hasNext() )
+ {
+ Tuple<Integer, String> tuple = cursor.next();
+
+ assertNotNull( tuple );
+ Integer val = sortedValues[pos];
+ Integer res = tuple.getKey();
+ assertEquals( val, res );
+ pos++;
+ }
+
+ cursor.close();
+ btree.close();
+ }
+
+
+ /**
+ * Test the browse method going backward
+ * @throws Exception
+ */
+ @Test
+ public void testBrowseBackward() throws Exception
+ {
+ // Create a BTree with pages containing 8 elements
+ BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
+ btree.setPageSize( 8 );
+
+ // Inject the values
+ for ( int value : sortedValues )
+ {
+ String strValue = "V" + value;
+
+ btree.insert( value, strValue );
+ }
+
+ // Check that the tree contains all the values
+ for ( int key : sortedValues )
+ {
+ String value = btree.get( key );
+
+ assertNotNull( value );
+ }
+
+ // Browse starting at position 10
+ int pos = 10;
+ Cursor<Integer, String> cursor = btree.browseFrom( sortedValues[pos] );
+
+ while ( cursor.hasPrev() )
+ {
+ Tuple<Integer, String> tuple = cursor.prev();
+
+ pos--;
+
+ assertNotNull( tuple );
+ Integer val = sortedValues[pos];
+ Integer res = tuple.getKey();
+ assertEquals( val, res );
+ }
+
+ cursor.close();
+
+ // Now, start on a non existing key (7)
+ cursor = btree.browseFrom( 7 );
+
+ // We should start reading values superior to 7, so value 8 at position 6 in the array
+ pos = 6;
+
+ while ( cursor.hasPrev() )
+ {
+ Tuple<Integer, String> tuple = cursor.prev();
+
+ pos--;
+ assertNotNull( tuple );
+ Integer val = sortedValues[pos];
+ Integer res = tuple.getKey();
+ assertEquals( val, res );
+ }
+
+ cursor.close();
+
+ // Last, let's browse with no key, we should get no values
+ cursor = btree.browse();
+
+ pos = 0;
+
+ assertFalse( cursor.hasPrev() );
+
+ cursor.close();
+ btree.close();
+ }
+
+
+ /**
+ * Test a browse over an empty tree
+ */
+ @Test
+ public void testBrowseEmptyTree() throws Exception
+ {
+ // Create a BTree with pages containing 8 elements
+ BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
+ btree.setPageSize( 8 );
+
+ Cursor<Integer, String> cursor = btree.browse();
+
+ assertFalse( cursor.hasNext() );
+ assertFalse( cursor.hasPrev() );
+
+ cursor.close();
+ btree.close();
+ }
+
+
+ /**
+ * Test a browse forward and backward
+ */
+ @Test
+ public void testBrowseForwardBackward() throws Exception
+ {
+ // Create a BTree with pages containing 4 elements
+ BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
+ btree.setPageSize( 4 );
+
+ for ( int i = 0; i < 16; i++ )
+ {
+ String strValue = "V" + i;
+ btree.insert( i, strValue );
+ }
+
+ // Start to browse in the middle
+ Cursor<Integer, String> cursor = btree.browseFrom( 8 );
+
+ assertTrue( cursor.hasNext() );
+
+ // Get 8
+ assertEquals( 8, cursor.next().getKey().intValue() );
+
+ // get 9
+ assertEquals( 9, cursor.next().getKey().intValue() );
+
+ // get 10
+ assertEquals( 10, cursor.next().getKey().intValue() );
+
+ // get 11
+ assertEquals( 11, cursor.next().getKey().intValue() );
+
+ // get 12 (now, we must have gone through at least 2 pages)
+ assertEquals( 12, cursor.next().getKey().intValue() );
+
+ assertTrue( cursor.hasPrev() );
+
+ // Lets go backward. We should get the same value, as the next() call have incremented the counter
+ assertEquals( 12, cursor.prev().getKey().intValue() );
+
+ // Get 11
+ assertEquals( 11, cursor.prev().getKey().intValue() );
+
+ // Get 10
+ assertEquals( 10, cursor.prev().getKey().intValue() );
+
+ // Get 9
+ assertEquals( 9, cursor.prev().getKey().intValue() );
+
+ // Get 8
+ assertEquals( 8, cursor.prev().getKey().intValue() );
+
+ // Get 7
+ assertEquals( 7, cursor.prev().getKey().intValue() );
+
+ cursor.close();
+ btree.close();
+ }
+
+
+ /**
+ * Test various deletions in a tree, when we have full leaves
+ */
+ @Test
+ public void testDeleteFromFullLeaves() throws Exception
+ {
+ // Create a BTree with pages containing 4 elements
+ BTree<Integer, String> btree = createTwoLevelBTreeFullLeaves();
+
+ // Test removals leadings to various RemoveResult.
+ // The tree remains the same after the deletion
+ // First, no borrow nor merge
+ btree.delete( 1 );
+
+ checkNull( btree, 1 );
+
+ btree.insert( 1, "V1" );
+
+ btree.delete( 3 );
+
+ checkNull( btree, 3 );
+
+ btree.insert( 3, "V3" );
+
+ btree.delete( 4 );
+
+ checkNull( btree, 4 );
+
+ btree.insert( 4, "V4" );
+
+ btree.delete( 11 );
+
+ checkNull( btree, 11 );
+
+ btree.insert( 11, "V11" );
+
+ btree.delete( 20 );
+
+ checkNull( btree, 20 );
+
+ btree.insert( 20, "V20" );
+
+ btree.delete( 0 );
+
+ checkNull( btree, 0 );
+
+ btree.delete( 5 );
+
+ checkNull( btree, 5 );
+
+ btree.delete( 9 );
+
+ checkNull( btree, 9 );
+
+ btree.close();
+ }
+
+
+ /**
+ * Test the exist() method
+ */
+ @Test
+ public void testExist() throws IOException
+ {
+ // Create a BTree with pages containing 4 elements
+ BTree<Integer, String> btree = createTwoLevelBTreeFullLeaves();
+
+ for ( int i = 1; i < 21; i++ )
+ {
+ assertTrue( btree.hasKey( 5 ) );
+ }
+
+ assertFalse( btree.hasKey( 0 ) );
+ assertFalse( btree.hasKey( 21 ) );
+ }
+
+
+ /**
+ * Test various deletions in a tree, leadings to borrowFromSibling
+ */
+ @Test
+ public void testDeleteBorrowFromSibling() throws Exception
+ {
+ // Create a BTree with pages containing 4 elements
+ BTree<Integer, String> btree = createTwoLevelBTreeFullLeaves();
+
+ // Delete some useless elements to simulate the tree we want to test
+ // Make the left leaf to contain N/2 elements
+ btree.delete( 3 );
+ btree.delete( 4 );
+
+ // Make the right leaf to contain N/2 elements
+ btree.delete( 19 );
+ btree.delete( 20 );
+
+ // Make the middle leaf to contain N/2 elements
+ btree.delete( 11 );
+ btree.delete( 12 );
+
+ // Delete the leftmost key
+ btree.delete( 1 );
+
+ checkNull( btree, 1 );
+
+ // Delete the rightmost key
+ btree.delete( 18 );
+
+ checkNull( btree, 18 );
+
+ // Delete one element in the left page, but not the first one
+ btree.delete( 5 );
+
+ checkNull( btree, 5 );
+
+ // Delete the one element in the right page, but the first one
+ btree.delete( 16 );
+
+ checkNull( btree, 16 );
+
+ btree.close();
+
+ // Now do that with a deeper btree
+ btree = createMultiLevelBTreeLeavesHalfFull();
+
+ // Add some more elements on the second leaf before deleting some elements in the first leaf
+ btree.insert( 8, "V8" );
+ btree.insert( 9, "V9" );
+
+ // and delete some
+ btree.delete( 2 );
+
+ checkNull( btree, 2 );
+
+ btree.delete( 6 );
+
+ checkNull( btree, 6 );
+
+ // Add some more elements on the pre-last leaf before deleting some elements in the last leaf
+ btree.insert( 96, "V96" );
+ btree.insert( 97, "V97" );
+
+ // and delete some
+ btree.delete( 98 );
+
+ checkNull( btree, 98 );
+
+ btree.delete( 99 );
+
+ checkNull( btree, 99 );
+
+ // Now try to delete elements in the middle
+ btree.insert( 48, "V48" );
+
+ btree.delete( 42 );
+
+ checkNull( btree, 42 );
+
+ btree.insert( 72, "V72" );
+
+ btree.delete( 67 );
+
+ checkNull( btree, 67 );
+
+ btree.close();
+ }
+
+
+ /**
+ * Test the browse method with a non existing key
+ * @throws Exception
+ */
+ @Test
+ public void testBrowseNonExistingKey() throws Exception
+ {
+ // Create a BTree with pages containing 8 elements
+ BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
+ btree.setPageSize( 8 );
+ for ( int i = 0; i < 11; i++ )
+ {
+ btree.insert( i, String.valueOf( i ) );
+ }
+
+ for ( int i = 0; i < 11; i++ )
+ {
+ assertNotNull( btree.get( i ) );
+ }
+
+ assertTrue( btree.hasKey( 8 ) );
+ assertFalse( btree.hasKey( 11 ) );
+
+ Cursor<Integer, String> cursor = btree.browseFrom( 11 );
+ assertFalse( cursor.hasNext() );
+ }
+
+
+ private Page<Integer, String> createLeaf( BTree<Integer, String> btree, long revision,
+ Tuple<Integer, String>... tuples )
+ {
+ Leaf<Integer, String> leaf = new Leaf<Integer, String>( btree );
+ int pos = 0;
+ leaf.revision = revision;
+ leaf.nbElems = tuples.length;
+ leaf.keys = new Integer[leaf.nbElems];
+ leaf.values = ( MemoryHolder<Integer, String>[] ) Array
+ .newInstance( MemoryHolder.class, leaf.nbElems );
+
+ for ( Tuple<Integer, String> tuple : tuples )
+ {
+ leaf.keys[pos] = tuple.getKey();
+ leaf.values[pos] = btree.createValueHolder( tuple.getValue() );
+ pos++;
+ }
+
+ return leaf;
+ }
+
+
+ private void addPage( BTree<Integer, String> btree, Node<Integer, String> node, Page<Integer, String> page, int pos )
+ throws EndOfFileExceededException, IOException
+ {
+ Tuple<Integer, String> leftmost = page.findLeftMost();
+
+ if ( pos > 0 )
+ {
+ node.keys[pos - 1] = leftmost.getKey();
+ }
+
+ node.children[pos] = btree.createPageHolder( page );
+ }
+
+
+ /**
+ * Creates a 2 level depth tree of full pages
+ */
+ private BTree<Integer, String> createTwoLevelBTreeFullLeaves() throws IOException
+ {
+ BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
+ btree.setPageSize( 4 );
+
+ // Create a tree with 5 children containing 4 elements each. The tree is full.
+ int[] keys = new int[]
+ { 1, 2, 5, 6, 3, 4, 9, 10, 7, 8, 13, 14, 11, 12, 17, 18, 15, 16, 19, 20 };
+
+ for ( int key : keys )
+ {
+ String value = "V" + key;
+ btree.insert( key, value );
+ }
+
+ return btree;
+ }
+
+
+ /**
+ * Creates a 2 level depth tree of half full pages
+ */
+ private BTree<Integer, String> createTwoLevelBTreeHalfFullLeaves() throws IOException
+ {
+ BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
+ btree.setPageSize( 4 );
+
+ // Create a tree with 5 children containing 4 elements each. The tree is full.
+ int[] keys = new int[]
+ { 1, 2, 17, 18, 13, 14, 9, 10, 5, 6, 3 };
+
+ for ( int key : keys )
+ {
+ String value = "V" + key;
+ btree.insert( key, value );
+ }
+
+ // Regulate the tree by removing the last value added, so that all the leaves have only 2 elements
+ btree.delete( 3 );
+
+ return btree;
+ }
+
+ /** A set used to check that the tree contains the contained elements */
+ private Set<Integer> EXPECTED1 = new HashSet<Integer>();
+
+
+ /**
+ * Creates a 3 level depth tree, with each page containing only N/2 elements
+ */
+ private BTree<Integer, String> createMultiLevelBTreeLeavesHalfFull() throws IOException
+ {
+ // Create a BTree with pages containing 4 elements
+ int pageSize = 4;
+
+ BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer(),
+ pageSize );
+
+ Node<Integer, String> root = new Node<Integer, String>( btree, 1L, pageSize );
+
+ // Create the tree with 3 levels, all the leaves containing only N/2 elements
+ int counter = 1;
+ for ( int i = 0; i < pageSize + 1; i++ )
+ {
+ Node<Integer, String> node = new Node<Integer, String>( btree, 1L, pageSize );
+
+ for ( int j = 0; j < pageSize + 1; j++ )
+ {
+ int even = counter * 2;
+
+ @SuppressWarnings("unchecked")
+ Page<Integer, String> leaf = createLeaf(
+ btree,
+ 1L,
+ new Tuple<Integer, String>( even, "v" + even ),
+ new Tuple<Integer, String>( even + 1, "v" + ( even + 1 ) )
+ );
+
+ counter += 2;
+
+ addPage( btree, node, leaf, j );
+
+ EXPECTED1.add( even );
+ EXPECTED1.add( even + 1 );
+ }
+
+ addPage( btree, root, node, i );
+ }
+
+ btree.setRoot( root );
+
+ return btree;
+ }
+
+
+ /**
+ * Remove an element from the tree, checking that the removal was successful
+ * @param btree The btree on which we remove an element
+ * @param element The removed element
+ * @param expected The expected set of elements
+ */
+ private void checkRemoval( BTree<Integer, String> btree, int element, Set<Integer> expected ) throws IOException
+ {
+ Tuple<Integer, String> removed = btree.delete( element );
+ assertEquals( element, removed.getKey().intValue() );
+ assertEquals( "v" + element, removed.getValue() );
+
+ checkNull( btree, element );
+
+ expected.remove( element );
+ checkTree( btree, expected );
+ }
+
+
+ /**
+ * Check that the tree contains all the elements in the expected set, and that
+ * all the elements in the tree are also present in the set
+ *
+ * @param btree The tree to check
+ * @param expected The set with the expected elements
+ */
+ private void checkTree( BTree<Integer, String> btree, Set<Integer> expected )
+ {
+ try
+ {
+ Cursor<Integer, String> cursor = btree.browse();
+ Integer value = null;
+
+ while ( cursor.hasNext() )
+ {
+ Tuple<Integer, String> tuple = cursor.next();
+
+ if ( value == null )
+ {
+ value = tuple.getKey();
+ }
+ else
+ {
+ assertTrue( value < tuple.getKey() );
+ value = tuple.getKey();
+ }
+
+ assertTrue( expected.contains( value ) );
+ expected.remove( value );
+ }
+
+ assertEquals( 0, expected.size() );
+ }
+ catch ( IOException ioe )
+ {
+ fail();
+ }
+ }
+
+
+ /**
+ * Remove a set of values from a btree
+ *
+ * @param btree The modified btree
+ * @param expected The set of expected values to update
+ * @param values The values to remove
+ */
+ private void delete( BTree<Integer, String> btree, Set<Integer> expected, int... values ) throws IOException
+ {
+ for ( int value : values )
+ {
+ btree.delete( value );
+ expected.remove( value );
+ }
+ }
+
+
+ /**
+ * Test deletions in a tree with more than one level. We are specifically testing
+ * the deletions that will generate a merge in the leaves.
+ */
+ @Test
+ public void testDeleteMultiLevelsLeadingToLeafMerge() throws Exception
+ {
+ BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
+
+ // Case 1 : delete the leftmost element in the btree in the leftmost leaf
+ Tuple<Integer, String> removed = btree.delete( 2 );
+ assertEquals( 2, removed.getKey().intValue() );
+ assertEquals( "v2", removed.getValue() );
+ checkNull( btree, 2 );
+
+ // delete the third element in the first leaf
+ removed = btree.delete( 7 );
+ assertEquals( 7, removed.getKey().intValue() );
+ assertEquals( "v7", removed.getValue() );
+ checkNull( btree, 7 );
+
+ // Case 2 : Delete the second element in the leftmost leaf
+ removed = btree.delete( 6 );
+ assertEquals( 6, removed.getKey().intValue() );
+ assertEquals( "v6", removed.getValue() );
+ checkNull( btree, 6 );
+
+ // delete the third element in the first leaf
+ removed = btree.delete( 11 );
+ assertEquals( 11, removed.getKey().intValue() );
+ assertEquals( "v11", removed.getValue() );
+ checkNull( btree, 11 );
+
+ // Case 3 : delete the rightmost element in the btree in the rightmost leaf
+ removed = btree.delete( 99 );
+ assertEquals( 99, removed.getKey().intValue() );
+ assertEquals( "v99", removed.getValue() );
+ checkNull( btree, 99 );
+
+ // delete the third element in the last leaf
+ removed = btree.delete( 98 );
+ assertEquals( 98, removed.getKey().intValue() );
+ assertEquals( "v98", removed.getValue() );
+ checkNull( btree, 98 );
+
+ // Case 2 : Delete the first element in the rightmost leaf
+ removed = btree.delete( 94 );
+ assertEquals( 94, removed.getKey().intValue() );
+ assertEquals( "v94", removed.getValue() );
+ checkNull( btree, 94 );
+
+ // delete the third element in the last leaf
+ removed = btree.delete( 95 );
+ assertEquals( 95, removed.getKey().intValue() );
+ assertEquals( "v95", removed.getValue() );
+ checkNull( btree, 95 );
+
+ // Case 5 : delete the leftmost element which is referred in the root node
+ removed = btree.delete( 22 );
+ assertEquals( 22, removed.getKey().intValue() );
+ assertEquals( "v22", removed.getValue() );
+ checkNull( btree, 22 );
+
+ // delete the third element in the last leaf
+ removed = btree.delete( 27 );
+ assertEquals( 27, removed.getKey().intValue() );
+ assertEquals( "v27", removed.getValue() );
+ checkNull( btree, 27 );
+
+ // Case 6 : delete the leftmost element in a leaf in the middle of the tree
+ removed = btree.delete( 70 );
+ assertEquals( 70, removed.getKey().intValue() );
+ assertEquals( "v70", removed.getValue() );
+ checkNull( btree, 70 );
+
+ // delete the third element in the leaf
+ removed = btree.delete( 71 );
+ assertEquals( 71, removed.getKey().intValue() );
+ assertEquals( "v71", removed.getValue() );
+ checkNull( btree, 71 );
+
+ // Case 7 : delete the rightmost element in a leaf in the middle of the tree
+ removed = btree.delete( 51 );
+ assertEquals( 51, removed.getKey().intValue() );
+ assertEquals( "v51", removed.getValue() );
+ checkNull( btree, 51 );
+
+ // delete the third element in the leaf
+ removed = btree.delete( 50 );
+ assertEquals( 50, removed.getKey().intValue() );
+ assertEquals( "v50", removed.getValue() );
+ checkNull( btree, 50 );
+
+ btree.close();
+ }
+
+
+ /**
+ * Test various deletions in a two level high tree, when we have leaves
+ * containing N/2 elements (thus each deletion leads to a merge)
+ */
+ @Test
+ public void testDelete2LevelsTreeWithHalfFullLeaves() throws Exception
+ {
+ // Create a BTree with pages containing 4 elements
+ BTree<Integer, String> btree = createTwoLevelBTreeHalfFullLeaves();
+
+ // Test removals leadings to various merges.
+ // Delete from the middle, not the leftmost value of the leaf
+ btree.delete( 10 );
+ checkNull( btree, 10 );
+
+ // Delete the extraneous value
+ btree.delete( 9 );
+ checkNull( btree, 9 );
+
+ // Delete the leftmost element in the middle
+ btree.delete( 13 );
+ checkNull( btree, 13 );
+
+ // Delete the extraneous value
+ btree.delete( 14 );
+ checkNull( btree, 14 );
+
+ // Delete the rightmost value
+ btree.delete( 18 );
+ checkNull( btree, 18 );
+
+ // Delete the extraneous value
+ btree.delete( 5 );
+ checkNull( btree, 5 );
+
+ // Delete the leftmost value of the right leaf
+ btree.delete( 6 );
+ checkNull( btree, 6 );
+
+ btree.close();
+ }
+
+
+ /**
+ * Test deletions in a tree with more than one level. We are specifically testing
+ * the deletions that will make a node borrowing some element from a sibling.
+ *
+ * 1: remove the leftmost element
+ */
+ @Test
+ public void testDeleteMultiLevelsLeadingToNodeBorrowRight1() throws Exception
+ {
+ BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
+
+ // deleting as many elements as necessary to get the node ready for a merge
+ delete( btree, EXPECTED1, 2, 3, 6, 7 );
+
+ // delete the element
+ checkRemoval( btree, 10, EXPECTED1 );
+
+ btree.close();
+ }
+
+
+ /**
+ * Test deletions in a tree with more than one level. We are specifically testing
+ * the deletions that will make a node borrowing some element from a sibling.
+ *
+ * 2: remove an element on the leftmost page but not the first one
+ */
+ @Test
+ public void testDeleteMultiLevelsLeadingToNodeBorrowRight2() throws Exception
+ {
+ BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
+
+ // deleting as many elements as necessary to get the node ready for a merge
+ delete( btree, EXPECTED1, 2, 3, 6, 7 );
+
+ // delete the element
+ checkRemoval( btree, 11, EXPECTED1 );
+
+ btree.close();
+ }
+
+
+ /**
+ * Test deletions in a tree with more than one level. We are specifically testing
+ * the deletions that will make a node borrowing some element from a sibling.
+ *
+ * 3: remove an element on the rightmost page on the leftmost node on the upper level
+ */
+ @Test
+ public void testDeleteMultiLevelsLeadingToNodeBorrowRight3() throws Exception
+ {
+ BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
+
+ // deleting as many elements as necessary to get the node ready for a merge
+ delete( btree, EXPECTED1, 2, 3, 6, 7 );
+
+ // delete the element
+ checkRemoval( btree, 19, EXPECTED1 );
+
+ btree.close();
+ }
+
+
+ /**
+ * Test deletions in a tree with more than one level. We are specifically testing
+ * the deletions that will make a node borrowing some element from a sibling.
+ *
+ * 4: remove the first element in a page in the middle of the first node
+ */
+ @Test
+ public void testDeleteMultiLevelsLeadingToNodeBorrowRight4() throws Exception
+ {
+ BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
+
+ // deleting as many elements as necessary to get the node ready for a merge
+ delete( btree, EXPECTED1, 2, 3, 6, 7 );
+
+ // delete the element
+ checkRemoval( btree, 14, EXPECTED1 );
+
+ btree.close();
+ }
+
+
+ /**
+ * Test deletions in a tree with more than one level. We are specifically testing
+ * the deletions that will make a node borrowing some element from a sibling.
+ *
+ * 5: remove the second element in a page in the middle of the first node
+ */
+ @Test
+ public void testDeleteMultiLevelsLeadingToNodeBorrowRight5() throws Exception
+ {
+ BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
+
+ // deleting as many elements as necessary to get the node ready for a merge
+ delete( btree, EXPECTED1, 2, 3, 6, 7 );
+
+ // delete the element
+ checkRemoval( btree, 15, EXPECTED1 );
+
+ btree.close();
+ }
+
+
+ /**
+ * Test deletions in a tree with more than one level. We are specifically testing
+ * the deletions that will make a node borrowing some element from a sibling.
+ *
+ * 1: remove the rightmost element
+ */
+ @Test
+ public void testDeleteMultiLevelsLeadingToNodeBorrowLeft1() throws Exception
+ {
+ BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
+
+ // deleting as many elements as necessary to get the node ready for a merge
+ delete( btree, EXPECTED1, 94, 95, 98, 99 );
+
+ // delete the element
+ checkRemoval( btree, 91, EXPECTED1 );
+
+ btree.close();
+ }
+
+
+ /**
+ * Test deletions in a tree with more than one level. We are specifically testing
+ * the deletions that will make a node borrowing some element from a sibling.
+ *
+ * 1: remove the element before the rightmost element
+ */
+ @Test
+ public void testDeleteMultiLevelsLeadingToNodeBorrowLeft2() throws Exception
+ {
+ BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
+
+ // deleting as many elements as necessary to get the node ready for a merge
+ delete( btree, EXPECTED1, 94, 95, 98, 99 );
+
+ // delete the element
+ checkRemoval( btree, 90, EXPECTED1 );
+
+ btree.close();
+ }
+
+
+ /**
+ * Test deletions in a tree with more than one level. We are specifically testing
+ * the deletions that will make a node borrowing some element from a sibling.
+ *
+ * 1: remove the leftmost element of the rightmost leaf
+ */
+ @Test
+ public void testDeleteMultiLevelsLeadingToNodeBorrowLeft3() throws Exception
+ {
+ BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
+
+ // deleting as many elements as necessary to get the node ready for a merge
+ delete( btree, EXPECTED1, 94, 95, 98, 99 );
+
+ // delete the element
+ checkRemoval( btree, 82, EXPECTED1 );
+
+ btree.close();
+ }
+
+
+ /**
+ * Test deletions in a tree with more than one level. We are specifically testing
+ * the deletions that will make a node borrowing some element from a sibling.
+ *
+ * 1: remove the second elemnt of the leftmost page on the rightmost second level node
+ */
+ @Test
+ public void testDeleteMultiLevelsLeadingToNodeBorrowLeft4() throws Exception
+ {
+ BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
+
+ // deleting as many elements as necessary to get the node ready for a merge
+ delete( btree, EXPECTED1, 94, 95, 98, 99 );
+
+ // delete the element
+ checkRemoval( btree, 83, EXPECTED1 );
+
+ btree.close();
+ }
+
+
+ /**
+ * Test deletions in a tree with more than one level. We are specifically testing
+ * the deletions that will make a node borrowing some element from a sibling.
+ *
+ * 6: remove the first element of a leaf in the middle of the tree
+ */
+ @Test
+ public void testDeleteMultiLevelsLeadingToNodeBorrowLeft6() throws Exception
+ {
+ BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
+
+ // deleting as many elements as necessary to get the node ready for a merge
+ delete( btree, EXPECTED1, 42, 43, 46, 47 );
+
+ // delete
+ checkRemoval( btree, 50, EXPECTED1 );
+
+ btree.close();
+ }
+
+
+ /**
+ * Test deletions in a tree with more than one level. We are specifically testing
+ * the deletions that will make a node borrowing some element from a sibling.
+ *
+ * 7: remove the second element of a leaf in the middle of the tree
+ */
+ @Test
+ public void testDeleteMultiLevelsLeadingToNodeBorrowLeft7() throws Exception
+ {
+ BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
+
+ // deleting as many elements as necessary to get the node ready for a merge
+ delete( btree, EXPECTED1, 42, 43, 46, 47 );
+
+ // delete
+ checkRemoval( btree, 51, EXPECTED1 );
+
+ btree.close();
+ }
+
+
+ /**
+ * Test deletions in a tree with more than one level. We are specifically testing
+ * the deletions that will make a node borrowing some element from a sibling.
+ *
+ * 8: remove the last element of a leaf in the middle of the tree
+ */
+ @Test
+ public void testDeleteMultiLevelsLeadingToNodeBorrowLeft8() throws Exception
+ {
+ BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
+
+ // deleting as many elements as necessary to get the node ready for a merge
+ delete( btree, EXPECTED1, 42, 43, 46, 47 );
+
+ // delete
+ checkRemoval( btree, 59, EXPECTED1 );
+
+ btree.close();
+ }
+
+
+ /**
+ * Test deletions in a tree with more than one level. We are specifically testing
+ * the deletions that will make a node borrowing some element from a sibling.
+ *
+ * 9: remove the element before the last one of a leaf in the middle of the tree
+ */
+ @Test
+ public void testDeleteMultiLevelsLeadingToNodeBorrowLeft9() throws Exception
+ {
+ BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
+
+ // deleting as many elements as necessary to get the node ready for a merge
+ delete( btree, EXPECTED1, 42, 43, 46, 47 );
+
+ // delete
+ checkRemoval( btree, 58, EXPECTED1 );
+
+ btree.close();
+ }
+
+
+ /**
+ * Test deletions in a tree with more than one level. We are specifically testing
+ * the deletions that will make a node borrowing some element from a sibling.
+ *
+ * 10: remove the mid element of a leaf in the middle of the tree
+ */
+ @Test
+ public void testDeleteMultiLevelsLeadingToNodeBorrowLeft10() throws Exception
+ {
+ BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
+
+ // deleting as many elements as necessary to get the node ready for a merge
+ delete( btree, EXPECTED1, 42, 43, 46, 47 );
+
+ // delete
+ checkRemoval( btree, 54, EXPECTED1 );
+
+ btree.close();
+ }
+
+
+ /**
+ * Test deletions in a tree with more than one level. We are specifically testing
+ * the deletions that will make a node borrowing some element from a sibling.
+ *
+ * 11: remove the mid+1 element of a leaf in the middle of the tree
+ */
+ @Test
+ public void testDeleteMultiLevelsLeadingToNodeBorrowLeft11() throws Exception
+ {
+ BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
+
+ // deleting as many elements as necessary to get the node ready for a merge
+ delete( btree, EXPECTED1, 42, 43, 46, 47 );
+
+ // delete
+ checkRemoval( btree, 55, EXPECTED1 );
+
+ btree.close();
+ }
+
+
+ /**
+ * Test the addition of elements with null values
+ */
+ @Test
+ public void testAdditionNullValues() throws IOException
+ {
+ BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
+
+ // Adding an element with a null value
+ btree.insert( 100, null );
+
+ assertTrue( btree.hasKey( 100 ) );
+
+ try
+ {
+ assertNull( btree.get( 100 ) );
+ }
+ catch ( KeyNotFoundException knfe )
+ {
+ fail();
+ }
+
+ Tuple<Integer, String> deleted = btree.delete( 100 );
+
+ assertNotNull( deleted );
+ assertNull( deleted.getValue() );
+ }
+
+
+ /**
+ * Test the insertion of 5 million elements in a BTree
+ * @throws Exception
+ */
+ @Test
+ public void testBrowse500K() throws Exception
+ {
+ Random random = new Random( System.nanoTime() );
+
+ int nbError = 0;
+
+ int n = 0;
+ int nbElems = 500000;
+ long delta = System.currentTimeMillis();
+
+ // Create a BTree with 5 million entries
+ BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
+ btree.setPageSize( 32 );
+
+ for ( int i = 0; i < nbElems; i++ )
+ {
+ Long key = ( long ) random.nextLong();
+ String value = Long.toString( key );
+
+ try
+ {
+ btree.insert( key, value );
+ }
+ catch ( Exception e )
+ {
+ e.printStackTrace();
+ System.out.println( btree );
+ System.out.println( "Error while adding " + value );
+ nbError++;
+ return;
+ }
+
+ if ( i % 100000 == 0 )
+ {
+ if ( n > 0 )
+ {
+ long t0 = System.currentTimeMillis();
+ System.out.println( "Delta" + n + ": " + ( t0 - delta ) );
+ delta = t0;
+ }
+
+ n++;
+ }
+ }
+
+ // Now browse them
+ long l1 = System.currentTimeMillis();
+
+ Cursor<Long, String> cursor = btree.browse();
+
+ int nb = 0;
+ long elem = Long.MIN_VALUE;
+
+ while ( cursor.hasNext() )
+ {
+ Tuple<Long, String> res = cursor.next();
+
+ if ( res.getKey() > elem )
+ {
+ elem = res.getKey();
+ nb++;
+ }
+ }
+
+ System.out.println( "Nb elements read : " + nb );
+
+ cursor.close();
+ btree.close();
+
+ long l2 = System.currentTimeMillis();
+
+ System.out.println( "Delta : " + ( l2 - l1 ) + ", nbError = " + nbError
+ + ", Nb searches per second : " + ( ( nbElems * 1000 ) / ( l2 - l1 ) ) );
+ }
+
+
+ private void checkNull( BTree<Long, String> btree, long key ) throws IOException
+ {
+ try
+ {
+ btree.get( key );
+ fail();
+ }
+ catch ( KeyNotFoundException knfe )
+ {
+ // expected
+ }
+ }
+
+
+ private void checkNull( BTree<Integer, String> btree, int key ) throws IOException
+ {
+ try
+ {
+ btree.get( key );
+ fail();
+ }
+ catch ( KeyNotFoundException knfe )
+ {
+ // expected
+ }
+ }
+
+
+ /**
+ * Test a browse forward and backward
+ */
+ @Test
+ public void testBrowseForwardBackwardExtremes() throws Exception
+ {
+ // Create a BTree with pages containing 4 elements
+ BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
+ btree.setPageSize( 4 );
+
+ for ( int i = 8; i < 13; i++ )
+ {
+ String strValue = "V" + i;
+ btree.insert( i, strValue );
+ }
+
+ // Start to browse in the middle
+ Cursor<Integer, String> cursor = btree.browseFrom( 8 );
+
+ assertTrue( cursor.hasNext() );
+
+ // Get 8
+ assertEquals( 8, cursor.next().getKey().intValue() );
+
+ // get 9
+ assertEquals( 9, cursor.next().getKey().intValue() );
+
+ // get 10
+ assertEquals( 10, cursor.next().getKey().intValue() );
+
+ // get 11
+ assertEquals( 11, cursor.next().getKey().intValue() );
+
+ // get 12 (now, we must have gone through at least 2 pages)
+ assertEquals( 12, cursor.next().getKey().intValue() );
+
+ assertFalse( cursor.hasNext() );
+ assertTrue( cursor.hasPrev() );
+
+ // Lets go backward. We should get the same value, as the next() call have incremented the counter
+ assertEquals( 12, cursor.prev().getKey().intValue() );
+
+ // Get 11
+ assertEquals( 11, cursor.prev().getKey().intValue() );
+
+ // Get 10
+ assertEquals( 10, cursor.prev().getKey().intValue() );
+
+ // Get 9
+ assertEquals( 9, cursor.prev().getKey().intValue() );
+
+ // Get 8
+ assertEquals( 8, cursor.prev().getKey().intValue() );
+
+ assertFalse( cursor.hasPrev() );
+ assertTrue( cursor.hasNext() );
+
+ cursor.close();
+ btree.close();
+ }
+
+
+ @Test
+ public void testNextAfterPrev() throws Exception
+ {
+ IntSerializer serializer = new IntSerializer();
+
+ BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+ config.setName( "master" );
+ config.setPageSize( 4 );
+ config.setSerializers( serializer, serializer );
+ BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
+
+ int i = 7;
+ for ( int k = 0; k < i; k++ )
+ {
+ btree.insert( k, k );
+ }
+
+ // 3 is the last element of the first leaf
+ Cursor<Integer, Integer> cursor = btree.browseFrom( 4 );
+
+ assertTrue( cursor.hasNext() );
+ Tuple<Integer, Integer> tuple = cursor.next();
+ assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
+ assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
+
+ assertTrue( cursor.hasPrev() );
+ tuple = cursor.prev();
+ assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
+ assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
+
+ assertTrue( cursor.hasNext() );
+ tuple = cursor.next();
+ assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
+ assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
+ cursor.close();
+ }
+
+}
Added: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/InMemoryBTreeTestOps.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/InMemoryBTreeTestOps.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/InMemoryBTreeTestOps.java (added)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/InMemoryBTreeTestOps.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,114 @@
+package org.apache.directory.mavibot.btree.memory;
+
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+import java.io.IOException;
+import java.util.Random;
+
+import org.apache.directory.mavibot.btree.serializer.LongSerializer;
+import org.apache.directory.mavibot.btree.serializer.StringSerializer;
+import org.junit.AfterClass;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+
+/**
+ * A class to test multi-threaded operations on the btree
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class InMemoryBTreeTestOps
+{
+ /** The btree we use */
+ private static BTree<Long, String> btree;
+
+
+ /**
+ * Create the btree once
+ * @throws IOException If the creation failed
+ */
+ @BeforeClass
+ public static void setup() throws IOException
+ {
+ btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
+ }
+
+
+ /**
+ * Close the btree
+ */
+ @AfterClass
+ public static void shutdown() throws IOException
+ {
+ btree.close();
+ }
+
+
+ /**
+ * Create a btree with 500 000 elements in it
+ * @throws IOException If the creation failed
+ */
+ private void createTree() throws IOException
+ {
+ Random random = new Random( System.nanoTime() );
+
+ int nbElems = 500000;
+
+ // Create a BTree with 500 000 entries
+ btree.setPageSize( 32 );
+ for ( int i = 0; i < nbElems; i++ )
+ {
+ Long key = ( long ) random.nextLong();
+ String value = Long.toString( key );
+
+ try
+ {
+ btree.insert( key, value );
+
+ if ( i % 100000 == 0 )
+ {
+ System.out.println( "Written " + i + " elements" );
+ }
+ }
+ catch ( Exception e )
+ {
+ e.printStackTrace();
+ System.out.println( btree );
+ System.out.println( "Error while adding " + value );
+ return;
+ }
+ }
+
+ }
+
+
+ @Test
+ public void testCreateTree() throws InterruptedException, IOException
+ {
+
+ long t0 = System.currentTimeMillis();
+
+ // Start the writer
+ createTree();
+ long t1 = System.currentTimeMillis();
+ System.out.println( "Time to create a tree with 500 in memory:" + ( ( t1 - t0 ) ) + " Mseconds" );
+ }
+}
Added: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/LeafTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/LeafTest.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/LeafTest.java (added)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/LeafTest.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,446 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.memory;
+
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.io.IOException;
+
+import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
+import org.apache.directory.mavibot.btree.serializer.LongSerializer;
+import org.apache.directory.mavibot.btree.serializer.StringSerializer;
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+
+
+/**
+ * A unit test class for Leaf
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class LeafTest
+{
+ private BTree<Long, String> btree = null;
+
+
+ /**
+ * Create a btree
+ */
+ @Before
+ public void setup() throws IOException
+ {
+ btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
+ btree.setPageSize( 8 );
+ }
+
+
+ @After
+ public void shutdown() throws IOException
+ {
+ btree.close();
+ }
+
+
+ /**
+ * A helper method to insert elements in a Leaf
+ * @throws IOException
+ */
+ private Leaf<Long, String> insert( Leaf<Long, String> leaf, long key, String value ) throws IOException
+ {
+ InsertResult<Long, String> result = leaf.insert( 1L, key, value );
+
+ return ( Leaf<Long, String> ) ( ( ModifyResult<Long, String> ) result ).getModifiedPage();
+ }
+
+
+ /**
+ * Test that deleting an entry from an empty page returns a NOT_PRESENT result
+ * @throws IOException
+ */
+ @Test
+ public void testDeleteFromEmptyLeaf() throws IOException
+ {
+ Leaf<Long, String> leaf = new Leaf<Long, String>( btree );
+
+ DeleteResult<Long, String> result = leaf.delete( 1L, 1L, null, null, -1 );
+
+ assertEquals( NotPresentResult.NOT_PRESENT, result );
+ }
+
+
+ /**
+ * Test that deleting an entry which is not present in the leaf works
+ * @throws IOException
+ */
+ @Test
+ public void testDeleteNotPresentElementFromRootLeaf() throws IOException
+ {
+ Leaf<Long, String> leaf = new Leaf<Long, String>( btree );
+ leaf = insert( leaf, 1L, "v1" );
+ leaf = insert( leaf, 2L, "v2" );
+ leaf = insert( leaf, 3L, "v3" );
+ leaf = insert( leaf, 4L, "v4" );
+
+ DeleteResult<Long, String> result = leaf.delete( 2L, 5L, null, null, -1 );
+
+ assertEquals( NotPresentResult.NOT_PRESENT, result );
+ }
+
+
+ /**
+ * Test that deleting an entry which is present in the leaf works
+ * @throws IOException
+ */
+ @Test
+ public void testDeletePresentElementFromRootLeaf() throws IOException
+ {
+ Leaf<Long, String> leaf = new Leaf<Long, String>( btree );
+ leaf = insert( leaf, 1L, "v1" );
+ leaf = insert( leaf, 2L, "v2" );
+ leaf = insert( leaf, 3L, "v3" );
+ leaf = insert( leaf, 4L, "v4" );
+
+ DeleteResult<Long, String> result = leaf.delete( 4L, 3L, null, null, -1 );
+
+ assertTrue( result instanceof RemoveResult );
+
+ Tuple<Long, String> removedElement = ( ( RemoveResult<Long, String> ) result ).getRemovedElement();
+ Page<Long, String> newLeaf = ( ( RemoveResult<Long, String> ) result ).getModifiedPage();
+
+ assertEquals( Long.valueOf( 3L ), removedElement.getKey() );
+ assertEquals( "v3", removedElement.getValue() );
+ assertEquals( 3, newLeaf.getNbElems() );
+
+ try
+ {
+ assertEquals( "v1", newLeaf.get( 1L ) );
+ assertEquals( "v2", newLeaf.get( 2L ) );
+ assertEquals( "v4", newLeaf.get( 4L ) );
+ }
+ catch ( KeyNotFoundException knfe )
+ {
+ fail();
+ }
+
+ try
+ {
+ newLeaf.get( 3L );
+ fail();
+ }
+ catch ( KeyNotFoundException knfe )
+ {
+ // Expected
+ }
+ }
+
+
+ /**
+ * Test that deleting the first element return the correct result
+ * @throws IOException
+ */
+ @Test
+ public void testDeleteFirstElementFromRootLeaf() throws IOException
+ {
+ Leaf<Long, String> leaf = new Leaf<Long, String>( btree );
+ leaf = insert( leaf, 1L, "v1" );
+ leaf = insert( leaf, 2L, "v2" );
+ leaf = insert( leaf, 3L, "v3" );
+ leaf = insert( leaf, 4L, "v4" );
+
+ DeleteResult<Long, String> result = leaf.delete( 4L, 1L, null, null, -1 );
+
+ assertTrue( result instanceof RemoveResult );
+
+ RemoveResult<Long, String> removeResult = ( RemoveResult<Long, String> ) result;
+
+ Tuple<Long, String> removedElement = removeResult.getRemovedElement();
+ Page<Long, String> newLeaf = removeResult.getModifiedPage();
+
+ assertEquals( Long.valueOf( 1L ), removedElement.getKey() );
+ assertEquals( "v1", removedElement.getValue() );
+ assertEquals( 3, newLeaf.getNbElems() );
+
+ try
+ {
+ newLeaf.get( 1L );
+ fail();
+ }
+ catch ( KeyNotFoundException knfe )
+ {
+ // expected
+ }
+
+ try
+ {
+ assertEquals( "v2", newLeaf.get( 2L ) );
+ assertEquals( "v3", newLeaf.get( 3L ) );
+ assertEquals( "v4", newLeaf.get( 4L ) );
+ }
+ catch ( KeyNotFoundException knfe )
+ {
+ fail();
+ }
+ }
+
+
+ /**
+ * Check that deleting an element from a leaf with N/2 element works when we borrow
+ * an element in a left page with more than N/2 elements.
+ * The BTree contains :
+ * +--[1, 2, 3, 4, 5]
+ * [6, 10]-+--[6, 7, 8, 9]
+ * +--[10, 11, 12, 13]
+ * @throws IOException
+ */
+ @Test
+ public void testDeleteBorrowingFromLeftSibling() throws IOException
+ {
+ Node<Long, String> parent = new Node<Long, String>( btree, 1L, 2 );
+ Leaf<Long, String> left = new Leaf<Long, String>( btree );
+ Leaf<Long, String> target = new Leaf<Long, String>( btree );
+ Leaf<Long, String> right = new Leaf<Long, String>( btree );
+
+ // Fill the left page
+ left = insert( left, 1L, "v1" );
+ left = insert( left, 2L, "v2" );
+ left = insert( left, 3L, "v3" );
+ left = insert( left, 4L, "v4" );
+ left = insert( left, 5L, "v5" );
+
+ // Fill the target page
+ target = insert( target, 6L, "v6" );
+ target = insert( target, 7L, "v7" );
+ target = insert( target, 8L, "v8" );
+ target = insert( target, 9L, "v9" );
+
+ // Fill the right page
+ right = insert( right, 10L, "v10" );
+ right = insert( right, 11L, "v11" );
+ right = insert( right, 12L, "v12" );
+ right = insert( right, 13L, "v13" );
+
+ parent.children[0] = new MemoryHolder( btree, left );
+ parent.children[1] = new MemoryHolder( btree, target );
+ parent.children[2] = new MemoryHolder( btree, right );
+
+ // Update the parent
+ parent.keys[0] = 6L;
+ parent.keys[1] = 10L;
+
+ // Now, delete the element from the target page
+ DeleteResult<Long, String> result = target.delete( 2L, 7L, null, parent, 1 );
+
+ assertTrue( result instanceof BorrowedFromLeftResult );
+
+ BorrowedFromLeftResult<Long, String> borrowed = ( BorrowedFromLeftResult<Long, String> ) result;
+ Tuple<Long, String> removedKey = borrowed.getRemovedElement();
+
+ assertEquals( Long.valueOf( 7L ), removedKey.getKey() );
+
+ // Check the modified leaf
+ Leaf<Long, String> newLeaf = ( Leaf<Long, String> ) borrowed.getModifiedPage();
+
+ assertEquals( 4, newLeaf.nbElems );
+ assertEquals( Long.valueOf( 5L ), newLeaf.keys[0] );
+ assertEquals( Long.valueOf( 6L ), newLeaf.keys[1] );
+ assertEquals( Long.valueOf( 8L ), newLeaf.keys[2] );
+ assertEquals( Long.valueOf( 9L ), newLeaf.keys[3] );
+
+ // Check the sibling
+ Leaf<Long, String> leftSibling = ( Leaf<Long, String> ) borrowed.getModifiedSibling();
+
+ assertEquals( 4, leftSibling.nbElems );
+ assertEquals( Long.valueOf( 1L ), leftSibling.keys[0] );
+ assertEquals( Long.valueOf( 2L ), leftSibling.keys[1] );
+ assertEquals( Long.valueOf( 3L ), leftSibling.keys[2] );
+ assertEquals( Long.valueOf( 4L ), leftSibling.keys[3] );
+ }
+
+
+ /**
+ * Check that deleting an element from a leaf with N/2 element works when we borrow
+ * an element in a right page with more than N/2 elements
+ * @throws IOException
+ */
+ @Test
+ public void testDeleteBorrowingFromRightSibling() throws IOException
+ {
+ Node<Long, String> parent = new Node<Long, String>( btree, 1L, 2 );
+ Leaf<Long, String> left = new Leaf<Long, String>( btree );
+ Leaf<Long, String> target = new Leaf<Long, String>( btree );
+ Leaf<Long, String> right = new Leaf<Long, String>( btree );
+
+ // Fill the left page
+ left = insert( left, 1L, "v1" );
+ left = insert( left, 2L, "v2" );
+ left = insert( left, 3L, "v3" );
+ left = insert( left, 4L, "v4" );
+
+ // Fill the target page
+ target = insert( target, 6L, "v6" );
+ target = insert( target, 7L, "v7" );
+ target = insert( target, 8L, "v8" );
+ target = insert( target, 9L, "v9" );
+
+ // Fill the right page
+ right = insert( right, 10L, "v10" );
+ right = insert( right, 11L, "v11" );
+ right = insert( right, 12L, "v12" );
+ right = insert( right, 13L, "v13" );
+ right = insert( right, 14L, "v14" );
+
+ parent.children[0] = new MemoryHolder( null, left );
+ parent.children[1] = new MemoryHolder( null, target );
+ parent.children[2] = new MemoryHolder( null, right );
+
+ // Update the parent
+ parent.keys[0] = 6L;
+ parent.keys[1] = 10L;
+
+ // Now, delete the element from the target page
+ DeleteResult<Long, String> result = target.delete( 2L, 7L, null, parent, 1 );
+
+ assertTrue( result instanceof BorrowedFromRightResult );
+
+ BorrowedFromRightResult<Long, String> borrowed = ( BorrowedFromRightResult<Long, String> ) result;
+ assertEquals( Long.valueOf( 11L ), borrowed.getModifiedSibling().getKey( 0 ) );
+ Tuple<Long, String> removedKey = borrowed.getRemovedElement();
+
+ assertEquals( Long.valueOf( 7L ), removedKey.getKey() );
+
+ // Check the modified leaf
+ Leaf<Long, String> newLeaf = ( Leaf<Long, String> ) borrowed.getModifiedPage();
+
+ assertEquals( 4, newLeaf.nbElems );
+ assertEquals( Long.valueOf( 6L ), newLeaf.keys[0] );
+ assertEquals( Long.valueOf( 8L ), newLeaf.keys[1] );
+ assertEquals( Long.valueOf( 9L ), newLeaf.keys[2] );
+ assertEquals( Long.valueOf( 10L ), newLeaf.keys[3] );
+
+ // Check the sibling
+ Leaf<Long, String> rightSibling = ( Leaf<Long, String> ) borrowed.getModifiedSibling();
+
+ assertEquals( 4, rightSibling.nbElems );
+ assertEquals( Long.valueOf( 11L ), rightSibling.keys[0] );
+ assertEquals( Long.valueOf( 12L ), rightSibling.keys[1] );
+ assertEquals( Long.valueOf( 13L ), rightSibling.keys[2] );
+ assertEquals( Long.valueOf( 14L ), rightSibling.keys[3] );
+ }
+
+
+ /**
+ * Check that deleting an element from a leaf with N/2 element works when we merge
+ * it with one of its sibling, if both has N/2 elements
+ * @throws IOException
+ */
+ @Test
+ public void testDeleteMergeWithSibling() throws IOException
+ {
+ Node<Long, String> parent = new Node<Long, String>( btree, 1L, 2 );
+ Leaf<Long, String> left = new Leaf<Long, String>( btree );
+ Leaf<Long, String> target = new Leaf<Long, String>( btree );
+ Leaf<Long, String> right = new Leaf<Long, String>( btree );
+
+ // Fill the left page
+ left = insert( left, 1L, "v1" );
+ left = insert( left, 2L, "v2" );
+ left = insert( left, 3L, "v3" );
+ left = insert( left, 4L, "v4" );
+
+ // Fill the target page
+ target = insert( target, 5L, "v5" );
+ target = insert( target, 6L, "v6" );
+ target = insert( target, 7L, "v7" );
+ target = insert( target, 8L, "v8" );
+
+ // Fill the right page
+ right = insert( right, 9L, "v9" );
+ right = insert( right, 10L, "v10" );
+ right = insert( right, 11L, "v11" );
+ right = insert( right, 12L, "v12" );
+
+ parent.children[0] = new MemoryHolder( null, left );
+ parent.children[1] = new MemoryHolder( null, target );
+ parent.children[2] = new MemoryHolder( null, right );
+
+ // Update the parent
+ parent.keys[0] = 5L;
+ parent.keys[1] = 9L;
+
+ // Now, delete the element from the target page
+ DeleteResult<Long, String> result = target.delete( 2L, 7L, null, parent, 1 );
+
+ assertTrue( result instanceof MergedWithSiblingResult );
+
+ MergedWithSiblingResult<Long, String> merged = ( MergedWithSiblingResult<Long, String> ) result;
+ Tuple<Long, String> removedKey = merged.getRemovedElement();
+
+ assertEquals( Long.valueOf( 7L ), removedKey.getKey() );
+
+ // Check the modified leaf
+ Leaf<Long, String> newLeaf = ( Leaf<Long, String> ) merged.getModifiedPage();
+
+ assertEquals( 7, newLeaf.nbElems );
+ assertEquals( Long.valueOf( 1L ), newLeaf.keys[0] );
+ assertEquals( Long.valueOf( 2L ), newLeaf.keys[1] );
+ assertEquals( Long.valueOf( 3L ), newLeaf.keys[2] );
+ assertEquals( Long.valueOf( 4L ), newLeaf.keys[3] );
+ assertEquals( Long.valueOf( 5L ), newLeaf.keys[4] );
+ assertEquals( Long.valueOf( 6L ), newLeaf.keys[5] );
+ assertEquals( Long.valueOf( 8L ), newLeaf.keys[6] );
+ }
+
+
+ /**
+ * Test the findPos() method
+ * @throws Exception
+ */
+ @Test
+ public void testFindPos() throws Exception
+ {
+ Leaf<Long, String> leaf = new Leaf<Long, String>( btree );
+
+ // Inject the values
+ for ( long i = 0; i < 8; i++ )
+ {
+ long value = i + i + 1;
+ leaf = ( Leaf<Long, String> ) ( ( ModifyResult<Long, String> ) leaf.insert( 0L, value, "V" + value ) )
+ .getModifiedPage();
+ }
+
+ // Check the findPos() method now
+ for ( long i = 0; i < 17; i++ )
+ {
+ if ( i % 2 == 1 )
+ {
+ assertEquals( -( i / 2 + 1 ), leaf.findPos( i ) );
+ }
+ else
+ {
+ assertEquals( i / 2, leaf.findPos( i ) );
+ }
+ }
+ }
+}