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 [12/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/BTreeConfigurationTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeConfigurationTest.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeConfigurationTest.java (added)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeConfigurationTest.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,244 @@
+/*
+ * 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.assertNotNull;
+
+import java.io.File;
+import java.io.IOException;
+
+import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
+import org.apache.directory.mavibot.btree.serializer.IntSerializer;
+import org.apache.directory.mavibot.btree.serializer.StringSerializer;
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.rules.TemporaryFolder;
+
+
+/**
+ * Test the creation of a BTree with a configuration.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class BTreeConfigurationTest
+{
+ @Rule
+ public TemporaryFolder tempFolder = new TemporaryFolder();
+
+ // 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
+ };
+
+
+ /**
+ * Test the creation of a in-memory BTree using the BTreeConfiguration.
+ */
+ @Test
+ public void testConfigurationBasic() throws IOException, KeyNotFoundException
+ {
+ BTreeConfiguration<Integer, String> config = new BTreeConfiguration<Integer, String>();
+ config.setName( "basic" );
+ config.setPageSize( 32 );
+ config.setSerializers( new IntSerializer(), new StringSerializer() );
+
+ try
+ {
+ // Create the BTree
+ BTree<Integer, String> btree = new BTree<Integer, String>( config );
+
+ // 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 );
+ }
+
+ btree.close();
+ }
+ finally
+ {
+ // Erase the mavibot file now
+ File mavibotFile = new File( "", "mavibot" );
+
+ if ( mavibotFile.exists() )
+ {
+ mavibotFile.delete();
+ }
+
+ // Erase the journal too
+ File mavibotJournal = new File( "", "mavibot.log" );
+
+ if ( mavibotJournal.exists() )
+ {
+ mavibotJournal.delete();
+ }
+ }
+ }
+
+
+ /**
+ * Test the creation of a BTree using the BTreeConfiguration, flushing the
+ * tree on disk, then reloading it in another BTree.
+ */
+ @Test
+ public void testConfigurationFlushReload() throws IOException, KeyNotFoundException
+ {
+ // Create a temporary file
+ File file = tempFolder.newFile( "testFlush.data" );
+ String parent = file.getParent();
+
+ try
+ {
+ BTreeConfiguration<Integer, String> config = new BTreeConfiguration<Integer, String>();
+ config.setPageSize( 32 );
+ config.setSerializers( new IntSerializer(), new StringSerializer() );
+
+ config.setFilePath( parent );
+ config.setName( "mavibot" );
+
+ // Create the BTree
+ BTree<Integer, String> btree = new BTree<Integer, String>( config );
+
+ // 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 );
+ }
+
+ // Flush the data
+ btree.close();
+
+ // Now, create a new BTree using the same configuration
+ BTree<Integer, String> btreeCopy = new BTree<Integer, String>( config );
+
+ // Check that the tree contains all the values
+ for ( int key : sortedValues )
+ {
+ String value = btreeCopy.get( key );
+
+ assertNotNull( value );
+ }
+
+ btreeCopy.close();
+ }
+ finally
+ {
+ // Erase the mavibot file now
+ File mavibotFile = new File( parent, "mavibot.db" );
+
+ if ( mavibotFile.exists() )
+ {
+ mavibotFile.delete();
+ }
+
+ // Erase the journal too
+ File mavibotJournal = new File( parent, "mavibot.db.log" );
+
+ if ( mavibotJournal.exists() )
+ {
+ mavibotJournal.delete();
+ }
+ }
+ }
+}
Added: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeDuplicateKeyTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeDuplicateKeyTest.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeDuplicateKeyTest.java (added)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeDuplicateKeyTest.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,701 @@
+/*
+ * 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.util.NoSuchElementException;
+import java.util.UUID;
+
+import org.apache.directory.mavibot.btree.Cursor;
+import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.serializer.IntSerializer;
+import org.apache.directory.mavibot.btree.serializer.StringSerializer;
+import org.junit.Test;
+
+
+/**
+ * TODO BTreeDuplicateKeyTest.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class BTreeDuplicateKeyTest
+{
+ @Test
+ public void testInsertNullValue() throws IOException
+ {
+ IntSerializer serializer = new IntSerializer();
+
+ BTree<Integer, Integer> btree = new BTree<Integer, Integer>( "master", serializer, serializer );
+ btree.init();
+
+ btree.insert( 1, null );
+
+ Cursor<Integer, Integer> cursor = btree.browse();
+ assertTrue( cursor.hasNext() );
+
+ Tuple<Integer, Integer> t = cursor.next();
+
+ assertEquals( Integer.valueOf( 1 ), t.getKey() );
+ assertEquals( null, t.getValue() );
+
+ cursor.close();
+ }
+
+
+ @Test
+ public void testBrowseEmptyTree() throws IOException
+ {
+ IntSerializer serializer = new IntSerializer();
+
+ BTree<Integer, Integer> btree = new BTree<Integer, Integer>( "master", serializer, serializer );
+ btree.init();
+
+ Cursor<Integer, Integer> cursor = btree.browse();
+ assertFalse( cursor.hasNext() );
+ assertFalse( cursor.hasPrev() );
+
+ try
+ {
+ cursor.next();
+ fail( "Should not reach here" );
+ }
+ catch ( NoSuchElementException e )
+ {
+ assertTrue( true );
+ }
+
+ try
+ {
+ cursor.prev();
+ fail( "Should not reach here" );
+ }
+ catch ( NoSuchElementException e )
+ {
+ assertTrue( true );
+ }
+
+ cursor.close();
+ }
+
+
+ @Test
+ public void testDuplicateKey() throws IOException
+ {
+ IntSerializer serializer = new IntSerializer();
+
+ BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+ config.setAllowDuplicates( true );
+ config.setName( "master" );
+ config.setSerializers( serializer, serializer );
+ BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
+
+ btree.insert( 1, 1 );
+ btree.insert( 1, 2 );
+
+ Cursor<Integer, Integer> cursor = btree.browse();
+ assertTrue( cursor.hasNext() );
+
+ Tuple<Integer, Integer> t = cursor.next();
+
+ assertEquals( Integer.valueOf( 1 ), t.getKey() );
+ assertEquals( Integer.valueOf( 1 ), t.getValue() );
+
+ assertTrue( cursor.hasNext() );
+
+ t = cursor.next();
+
+ assertEquals( Integer.valueOf( 1 ), t.getKey() );
+ assertEquals( Integer.valueOf( 2 ), t.getValue() );
+
+ assertFalse( cursor.hasNext() );
+
+ // test backward move
+ assertTrue( cursor.hasPrev() );
+
+ t = cursor.prev();
+
+ assertEquals( Integer.valueOf( 1 ), t.getKey() );
+ assertEquals( Integer.valueOf( 2 ), t.getValue() );
+
+ assertTrue( cursor.hasPrev() );
+
+ t = cursor.prev();
+
+ assertEquals( Integer.valueOf( 1 ), t.getKey() );
+ assertEquals( Integer.valueOf( 1 ), t.getValue() );
+
+ assertFalse( cursor.hasPrev() );
+
+ // again forward
+ assertTrue( cursor.hasNext() );
+
+ t = cursor.next();
+
+ assertEquals( Integer.valueOf( 1 ), t.getKey() );
+ assertEquals( Integer.valueOf( 1 ), t.getValue() );
+
+ assertTrue( cursor.hasNext() );
+
+ t = cursor.next();
+
+ assertEquals( Integer.valueOf( 1 ), t.getKey() );
+ assertEquals( Integer.valueOf( 2 ), t.getValue() );
+
+ assertFalse( cursor.hasNext() );
+
+ cursor.close();
+ }
+
+
+ @Test
+ public void testGetDuplicateKey() throws Exception
+ {
+ IntSerializer serializer = new IntSerializer();
+
+ BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+ config.setAllowDuplicates( true );
+ config.setName( "master" );
+ config.setSerializers( serializer, serializer );
+ BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
+
+ Integer retVal = btree.insert( 1, 1 );
+ assertNull( retVal );
+
+ retVal = btree.insert( 1, 2 );
+ assertNull( retVal );
+
+ // check the return value when an existing value is added again
+ retVal = btree.insert( 1, 2 );
+ assertEquals( Integer.valueOf( 2 ), retVal );
+
+ assertEquals( Integer.valueOf( 1 ), btree.get( 1 ) );
+ assertTrue( btree.contains( 1, 1 ) );
+ assertTrue( btree.contains( 1, 2 ) );
+
+ assertFalse( btree.contains( 1, 0 ) );
+ assertFalse( btree.contains( 0, 1 ) );
+ assertFalse( btree.contains( 0, 0 ) );
+ assertFalse( btree.contains( null, 0 ) );
+ assertFalse( btree.contains( 0, null ) );
+ assertFalse( btree.contains( null, null ) );
+ }
+
+
+ @Test
+ public void testRemoveDuplicateKey() throws Exception
+ {
+ IntSerializer serializer = new IntSerializer();
+
+ BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+ config.setAllowDuplicates( true );
+ config.setName( "master" );
+ config.setSerializers( serializer, serializer );
+ BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
+
+ btree.insert( 1, 1 );
+ btree.insert( 1, 2 );
+
+ assertEquals( 2l, btree.getNbElems() );
+
+ Tuple<Integer, Integer> t = btree.delete( 1, 1 );
+ assertEquals( Integer.valueOf( 1 ), t.getKey() );
+ assertEquals( Integer.valueOf( 1 ), t.getValue() );
+
+ assertEquals( 1l, btree.getNbElems() );
+
+ t = btree.delete( 1, 2 );
+ assertEquals( Integer.valueOf( 1 ), t.getKey() );
+ assertEquals( Integer.valueOf( 2 ), t.getValue() );
+
+ assertEquals( 0l, btree.getNbElems() );
+
+ t = btree.delete( 1, 2 );
+ assertNull( t );
+ }
+
+
+ @Test
+ public void testFullPage() throws Exception
+ {
+ StringSerializer serializer = new StringSerializer();
+
+ BTreeConfiguration<String, String> config = new BTreeConfiguration<String, String>();
+ config.setAllowDuplicates( true );
+ config.setName( "master" );
+ config.setSerializers( serializer, serializer );
+ BTree<String, String> btree = new BTree<String, String>( config );
+
+ int i = 7;
+ for ( char ch = 'a'; ch <= 'z'; ch++ )
+ {
+ for ( int k = 0; k < i; k++ )
+ {
+ btree.insert( String.valueOf( ch ), UUID.randomUUID().toString() );
+ }
+ }
+
+ Cursor<String, String> cursor = btree.browse();
+
+ char ch = 'a';
+ int k = 0;
+
+ while ( cursor.hasNext() )
+ {
+ Tuple<String, String> t = cursor.next();
+ assertEquals( String.valueOf( ch ), t.getKey() );
+ k++;
+
+ if ( ( k % i ) == 0 )
+ {
+ ch++;
+ }
+ }
+
+ assertEquals( ( 'z' + 1 ), ch );
+
+ ch = 'z';
+
+ while ( cursor.hasPrev() )
+ {
+ Tuple<String, String> t = cursor.prev();
+ assertEquals( String.valueOf( ch ), t.getKey() );
+ k--;
+
+ if ( ( k % i ) == 0 )
+ {
+ ch--;
+ }
+ }
+
+ assertEquals( ( 'a' - 1 ), ch );
+ cursor.close();
+ }
+
+
+ @Test
+ public void testMoveFirst() throws Exception
+ {
+ StringSerializer serializer = new StringSerializer();
+
+ BTreeConfiguration<String, String> config = new BTreeConfiguration<String, String>();
+ config.setAllowDuplicates( true );
+ config.setName( "master" );
+ config.setSerializers( serializer, serializer );
+ BTree<String, String> btree = new BTree<String, String>( config );
+
+ for ( char ch = 'a'; ch <= 'z'; ch++ )
+ {
+ btree.insert( String.valueOf( ch ), UUID.randomUUID().toString() );
+ }
+
+ // add one more value for 'a'
+ btree.insert( String.valueOf( 'a' ), UUID.randomUUID().toString() );
+
+ Cursor<String, String> cursor = btree.browseFrom( "c" );
+
+ int i = 0;
+ while ( cursor.hasNext() )
+ {
+ assertNotNull( cursor.next() );
+ i++;
+ }
+ assertEquals( 24, i );
+
+ // now move the cursor first
+ cursor.beforeFirst();
+ assertTrue( cursor.hasNext() );
+ assertEquals( "c", cursor.next().getKey() );
+
+ i = 0;
+ while ( cursor.hasNext() )
+ {
+ assertNotNull( cursor.next() );
+ i++;
+ }
+ assertEquals( 23, i );
+
+ cursor.close();
+
+ cursor = btree.browse();
+
+ i = 0;
+ while ( cursor.hasNext() )
+ {
+ assertNotNull( cursor.next() );
+ i++;
+ }
+ assertEquals( 27, i );
+
+ // now move the cursor first
+ cursor.beforeFirst();
+ assertTrue( cursor.hasNext() );
+ assertEquals( "a", cursor.next().getKey() );
+
+ i = 0;
+ while ( cursor.hasNext() )
+ {
+ assertNotNull( cursor.next() );
+ i++;
+ }
+ assertEquals( 26, i );
+ }
+
+
+ @Test(expected = NoSuchElementException.class)
+ public void testMoveLast() throws Exception
+ {
+ StringSerializer serializer = new StringSerializer();
+
+ BTreeConfiguration<String, String> config = new BTreeConfiguration<String, String>();
+ config.setAllowDuplicates( true );
+ config.setName( "master" );
+ config.setSerializers( serializer, serializer );
+ BTree<String, String> btree = new BTree<String, String>( config );
+
+ for ( char ch = 'a'; ch <= 'z'; ch++ )
+ {
+ btree.insert( String.valueOf( ch ), UUID.randomUUID().toString() );
+ }
+
+ btree.insert( String.valueOf( 'z' ), UUID.randomUUID().toString() );
+
+ Cursor<String, String> cursor = btree.browseFrom( "c" );
+ cursor.afterLast();
+
+ assertFalse( cursor.hasNext() );
+ assertTrue( cursor.hasPrev() );
+ assertEquals( "z", cursor.prev().getKey() );
+ // the key, 'z', has two values
+ assertEquals( "z", cursor.prev().getKey() );
+ assertEquals( "y", cursor.prev().getKey() );
+
+ cursor.beforeFirst();
+ assertEquals( "c", cursor.next().getKey() );
+
+ cursor.afterLast();
+ assertFalse( cursor.hasNext() );
+ // make sure it throws NoSuchElementException
+ cursor.next();
+ }
+
+
+ @Test(expected = NoSuchElementException.class)
+ public void testMoveToNextPrevNonDuplicateKey() throws Exception
+ {
+ StringSerializer serializer = new StringSerializer();
+
+ BTreeConfiguration<String, String> config = new BTreeConfiguration<String, String>();
+ config.setAllowDuplicates( true );
+ config.setName( "master" );
+ config.setSerializers( serializer, serializer );
+ BTree<String, String> btree = new BTree<String, String>( config );
+
+ int i = 7;
+ for ( char ch = 'a'; ch <= 'z'; ch++ )
+ {
+ for ( int k = 0; k < i; k++ )
+ {
+ btree.insert( String.valueOf( ch ), String.valueOf( k ) );
+ }
+ }
+
+ Cursor<String, String> cursor = btree.browse();
+
+ assertTrue( cursor.hasNext() );
+ assertFalse( cursor.hasPrev() );
+ for ( int k = 0; k < 2; k++ )
+ {
+ assertEquals( "a", cursor.next().getKey() );
+ }
+
+ assertEquals( "a", cursor.next().getKey() );
+
+ cursor.moveToNextNonDuplicateKey();
+
+ assertEquals( "b", cursor.next().getKey() );
+
+ for ( char ch = 'b'; ch < 'z'; ch++ )
+ {
+ assertEquals( String.valueOf( ch ), cursor.next().getKey() );
+ cursor.moveToNextNonDuplicateKey();
+ char t = ch;
+ assertEquals( String.valueOf( ++t ), cursor.next().getKey() );
+ }
+
+ for ( int k = 0; k < i - 1; k++ )
+ {
+ assertEquals( "z", cursor.next().getKey() );
+ }
+
+ assertFalse( cursor.hasNext() );
+ assertTrue( cursor.hasPrev() );
+ Tuple<String, String> tuple = cursor.prev();
+ assertEquals( "z", tuple.getKey() );
+ assertEquals( "6", tuple.getValue() );
+
+ for ( char ch = 'z'; ch > 'a'; ch-- )
+ {
+ char t = ch;
+ t--;
+
+ assertEquals( String.valueOf( ch ), cursor.prev().getKey() );
+
+ cursor.moveToPrevNonDuplicateKey();
+
+ tuple = cursor.prev();
+ assertEquals( String.valueOf( t ), tuple.getKey() );
+ }
+
+ for ( int k = 5; k >= 0; k-- )
+ {
+ tuple = cursor.prev();
+ assertEquals( "a", tuple.getKey() );
+ assertEquals( String.valueOf( k ), tuple.getValue() );
+ }
+
+ assertTrue( cursor.hasNext() );
+ assertFalse( cursor.hasPrev() );
+ tuple = cursor.next();
+ assertEquals( "a", tuple.getKey() );
+ assertEquals( "0", tuple.getValue() );
+
+ cursor.close();
+
+ cursor = btree.browseFrom( "y" );
+ cursor.moveToNextNonDuplicateKey();
+ assertTrue( cursor.hasPrev() );
+ tuple = cursor.prev();
+ assertEquals( "y", tuple.getKey() );
+ assertEquals( "6", tuple.getValue() );
+ cursor.close();
+
+ cursor = btree.browse();
+ cursor.beforeFirst();
+ assertFalse( cursor.hasPrev() );
+ // make sure it throws NoSuchElementException
+ cursor.prev();
+ }
+
+
+ /**
+ * Test for moving between two leaves. When moveToNextNonDuplicateKey is called
+ * and cursor is on the last element of the current leaf.
+ *
+ * @throws Exception
+ */
+ @Test
+ public void testMoveToNextAndPrevWithPageBoundaries() throws Exception
+ {
+ IntSerializer serializer = new IntSerializer();
+
+ BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+ config.setAllowDuplicates( true );
+ 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( 3 );
+ cursor.moveToNextNonDuplicateKey();
+
+ assertTrue( cursor.hasNext() );
+ Tuple<Integer, Integer> tuple = cursor.next();
+ assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
+ assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
+ cursor.close();
+
+ cursor = btree.browseFrom( 3 );
+ cursor.moveToNextNonDuplicateKey();
+
+ assertTrue( cursor.hasPrev() );
+ tuple = cursor.prev();
+ assertEquals( Integer.valueOf( 3 ), tuple.getKey() );
+ assertEquals( Integer.valueOf( 3 ), tuple.getValue() );
+ cursor.close();
+
+ // 4 is the first element of the second leaf
+ cursor = btree.browseFrom( 4 );
+ cursor.moveToPrevNonDuplicateKey();
+
+ assertTrue( cursor.hasPrev() );
+ tuple = cursor.prev();
+ assertEquals( Integer.valueOf( 3 ), tuple.getKey() );
+ assertEquals( Integer.valueOf( 3 ), tuple.getValue() );
+
+ // the below assertion won't work cause of the index position
+ // issue when prev() and next() are called subsequently (in any order)
+ // assertTrue( cursor.hasNext() );
+ // tuple = cursor.next();
+ // assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
+ // assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
+ cursor.close();
+
+ // test the extremes of the BTree instead of that of leaves
+ cursor = btree.browseFrom( 6 );
+ cursor.moveToNextNonDuplicateKey();
+ assertFalse( cursor.hasNext() );
+ assertTrue( cursor.hasPrev() );
+ tuple = cursor.prev();
+ assertEquals( Integer.valueOf( 6 ), tuple.getKey() );
+ assertEquals( Integer.valueOf( 6 ), tuple.getValue() );
+ cursor.close();
+
+ cursor = btree.browse();
+ cursor.moveToPrevNonDuplicateKey();
+ assertTrue( cursor.hasNext() );
+ assertFalse( cursor.hasPrev() );
+ tuple = cursor.next();
+ assertEquals( Integer.valueOf( 0 ), tuple.getKey() );
+ assertEquals( Integer.valueOf( 0 ), tuple.getValue() );
+ cursor.close();
+ }
+
+
+ @Test
+ public void testNextAfterPrev() throws Exception
+ {
+ IntSerializer serializer = new IntSerializer();
+
+ BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+ config.setAllowDuplicates( true );
+ 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();
+
+ }
+
+
+ /**
+ * Test for moving after a key and traversing backwards.
+ *
+ * @throws Exception
+ */
+ @Test
+ public void testMoveToNextAndTraverseBackward() throws Exception
+ {
+ IntSerializer serializer = new IntSerializer();
+
+ BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+ config.setAllowDuplicates( true );
+ config.setName( "master" );
+ config.setPageSize( 8 );
+ config.setSerializers( serializer, serializer );
+ BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
+
+ int i = 5;
+ for ( int k = 0; k < i; k++ )
+ {
+ btree.insert( k, k );
+ }
+
+ // 4 is the last element in the tree
+ Cursor<Integer, Integer> cursor = btree.browseFrom( 4 );
+ cursor.moveToNextNonDuplicateKey();
+
+ int currentKey = 4;
+ while ( cursor.hasPrev() )
+ {
+ assertEquals( Integer.valueOf( currentKey ), cursor.prev().getKey() );
+ currentKey--;
+ }
+
+ cursor.close();
+ }
+
+
+ /**
+ * Test for moving after a key and traversing backwards.
+ *
+ * @throws Exception
+ */
+ @Test
+ public void testMoveToPrevAndTraverseForward() throws Exception
+ {
+ IntSerializer serializer = new IntSerializer();
+
+ BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+ config.setAllowDuplicates( true );
+ config.setName( "master" );
+ config.setPageSize( 8 );
+ config.setSerializers( serializer, serializer );
+ BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
+
+ int i = 5;
+ for ( int k = 0; k < i; k++ )
+ {
+ btree.insert( k, k );
+ }
+
+ // 4 is the last element in the tree
+ Cursor<Integer, Integer> cursor = btree.browseFrom( 0 );
+ cursor.moveToPrevNonDuplicateKey();
+
+ int currentKey = 0;
+ while ( cursor.hasNext() )
+ {
+ assertEquals( Integer.valueOf( currentKey ), cursor.next().getKey() );
+ currentKey++;
+ }
+
+ cursor.close();
+ }
+
+}
Added: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeFlushTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeFlushTest.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeFlushTest.java (added)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeFlushTest.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,297 @@
+/*
+ * 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.assertTrue;
+
+import java.io.File;
+import java.io.IOException;
+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.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.Rule;
+import org.junit.Test;
+import org.junit.rules.TemporaryFolder;
+
+
+/**
+ * A unit test class for BTree flush() operation
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class BTreeFlushTest
+{
+ @Rule
+ public TemporaryFolder tempFolder = new TemporaryFolder();
+
+ // 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
+ };
+
+
+ private String create100KElementsFile() throws IOException
+ {
+ Random random = new Random( System.nanoTime() );
+
+ int nbError = 0;
+
+ long l1 = System.currentTimeMillis();
+ int n = 0;
+ long delta = l1;
+ int nbElems = 100000;
+
+ 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 null;
+ }
+
+ if ( i % 10000 == 0 )
+ {
+ if ( n > 0 )
+ {
+ long t0 = System.currentTimeMillis();
+ System.out.println( "Written " + i + " elements in : " + ( t0 - delta ) + "ms" );
+ delta = t0;
+ }
+
+ n++;
+ }
+ }
+
+ long l2 = System.currentTimeMillis();
+
+ System.out.println( "Delta : " + ( l2 - l1 ) + ", nbError = " + nbError
+ + ", Nb insertion per second : " + ( ( nbElems ) / ( l2 - l1 ) ) * 1000 );
+
+ // Now, flush the btree
+
+ File tempFile = tempFolder.newFile( "mavibot.tmp" );
+
+ long t0 = System.currentTimeMillis();
+
+ btree.flush( tempFile );
+
+ long t1 = System.currentTimeMillis();
+
+ System.out.println( "Time to flush 100 000 elements : " + ( t1 - t0 ) + "ms" );
+ btree.close();
+
+ return tempFile.getCanonicalPath();
+ }
+
+
+ /**
+ * 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 browse method going backward
+ * @throws Exception
+ */
+ @Test
+ public void testFlushBTree() throws Exception
+ {
+ // Create a BTree with pages containing 8 elements
+ String path = tempFolder.getRoot().getCanonicalPath();
+
+ BTree<Integer, String> btree = new BTree<Integer, String>( "test", path, new IntSerializer(),
+ new StringSerializer() );
+ btree.setPageSize( 8 );
+
+ File journal = btree.getJournal();
+ File data = btree.getFile();
+
+ try
+ {
+ // Inject the values
+ for ( int value : sortedValues )
+ {
+ String strValue = "V" + value;
+
+ btree.insert( value, strValue );
+ }
+
+ // The journal must be full
+ assertTrue( journal.length() > 0 );
+
+ // Now, flush the btree
+ btree.flush();
+
+ // The journal must be empty
+ assertEquals( 0, journal.length() );
+
+ // Load the data into a new tree
+ BTree<Integer, String> btreeLoaded = new BTree<Integer, String>( "test", path, new IntSerializer(),
+ new StringSerializer() );
+ btree.setPageSize( 8 );
+
+ Cursor<Integer, String> cursor1 = btree.browse();
+ Cursor<Integer, String> cursor2 = btree.browse();
+
+ while ( cursor1.hasNext() )
+ {
+ assertTrue( cursor2.hasNext() );
+
+ Tuple<Integer, String> tuple1 = cursor1.next();
+ Tuple<Integer, String> tuple2 = cursor2.next();
+
+ assertEquals( tuple1.getKey(), tuple2.getKey() );
+ assertEquals( tuple1.getValue(), tuple2.getValue() );
+ }
+
+ assertFalse( cursor2.hasNext() );
+
+ btree.close();
+ btreeLoaded.close();
+ }
+ finally
+ {
+ data.delete();
+ journal.delete();
+ }
+ }
+
+
+ /**
+ * Test the insertion of 5 million elements in a BTree
+ * @throws Exception
+ */
+ @Test
+ public void testLoadBTreeFromFile() throws Exception
+ {
+ String data100K = create100KElementsFile();
+ File dataFile = new File( data100K );
+ BTree<Long, String> btree = new BTree<Long, String>(
+ "test",
+ dataFile.getParent(),
+ new LongSerializer(),
+ new StringSerializer() );
+ btree.setPageSize( 32 );
+ }
+}
Added: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BulkDataSorterTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BulkDataSorterTest.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BulkDataSorterTest.java (added)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BulkDataSorterTest.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,183 @@
+/*
+ * 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 java.io.DataOutputStream;
+import java.io.File;
+import java.io.FileOutputStream;
+import java.io.IOException;
+import java.lang.reflect.Array;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.Random;
+
+import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.util.IntTupleReaderWriter;
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.rules.TemporaryFolder;
+
+
+/**
+ * Test cases for BulkDataSorter.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class BulkDataSorterTest
+{
+ @Rule
+ public TemporaryFolder tempFolder = new TemporaryFolder();
+
+ private Comparator<Tuple<Integer, Integer>> tupleComp = new Comparator<Tuple<Integer, Integer>>()
+ {
+
+ @Override
+ public int compare( Tuple<Integer, Integer> o1, Tuple<Integer, Integer> o2 )
+ {
+ return o1.getKey().compareTo( o2.getKey() );
+ }
+ };
+
+
+ @Test
+ public void testSortedFileCount() throws IOException
+ {
+ int count = 7;
+ IntTupleReaderWriter itrw = new IntTupleReaderWriter();
+ Random random = new Random();
+
+ File dataFile = tempFolder.newFile( "tuple.data" );
+ DataOutputStream out = new DataOutputStream( new FileOutputStream( dataFile ) );
+
+ Tuple<Integer, Integer>[] arr = ( Tuple<Integer, Integer>[] ) Array.newInstance( Tuple.class, count );
+
+ for ( int i = 0; i < count; i++ )
+ {
+ int x = random.nextInt( 100 );
+ //System.out.println(x);
+
+ Tuple<Integer, Integer> t = new Tuple<Integer, Integer>( x, x );
+
+ arr[i] = t;
+
+ itrw.writeTuple( t, out );
+ }
+
+ out.close();
+
+ BulkDataSorter<Integer, Integer> bds = new BulkDataSorter<Integer, Integer>( itrw, tupleComp, 4 );
+ bds.sort( dataFile );
+
+ assertEquals( 2, bds.getWorkDir().list().length );
+
+ deleteDir( bds.getWorkDir() );
+ }
+
+
+ @Test
+ public void testSortedFileMerge() throws IOException
+ {
+ testSortedFileMerge( 10, 2 );
+ testSortedFileMerge( 100, 7 );
+ testSortedFileMerge( 1000, 25 );
+ testSortedFileMerge( 10000, 100 );
+ testSortedFileMerge( 10000, 101 );
+ testSortedFileMerge( 100000, 501 );
+ }
+
+
+ public void testSortedFileMerge( int count, int splitAfter ) throws IOException
+ {
+ IntTupleReaderWriter itrw = new IntTupleReaderWriter();
+ Random random = new Random();
+
+ File dataFile = tempFolder.newFile( "tuple.data" );
+
+ DataOutputStream out = new DataOutputStream( new FileOutputStream( dataFile ) );
+
+ Tuple<Integer, Integer>[] arr = ( Tuple<Integer, Integer>[] ) Array.newInstance( Tuple.class, count );
+
+ int randUpper = count;
+ if ( count < 100 )
+ {
+ randUpper = 100;
+ }
+
+ for ( int i = 0; i < count; i++ )
+ {
+ int x = random.nextInt( randUpper );
+ //System.out.println(x);
+
+ Tuple<Integer, Integer> t = new Tuple<Integer, Integer>( x, x );
+
+ arr[i] = t;
+
+ itrw.writeTuple( t, out );
+ }
+
+ out.close();
+
+ BulkDataSorter<Integer, Integer> bds = new BulkDataSorter<Integer, Integer>( itrw, tupleComp, splitAfter );
+ bds.sort( dataFile );
+
+ Iterator<Tuple<Integer, Integer>> itr = bds.getMergeSortedTuples();
+
+ Integer prev = null;
+ while ( itr.hasNext() )
+ {
+ Tuple<Integer, Integer> t = itr.next();
+
+ if ( prev == null )
+ {
+ prev = t.getKey();
+ }
+ else
+ {
+ assertTrue( prev <= t.getKey() );
+ }
+
+ //System.out.println(t);
+ }
+
+ deleteDir( bds.getWorkDir() );
+ }
+
+
+ private void deleteDir( File dir )
+ {
+ if ( dir.isFile() )
+ {
+ dir.delete();
+ }
+
+ File[] files = dir.listFiles();
+
+ for ( File f : files )
+ {
+ f.delete();
+ }
+
+ dir.delete();
+ }
+}