You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@labs.apache.org by el...@apache.org on 2013/02/03 06:25:28 UTC
svn commit: r1441858 - in /labs/mavibot/trunk/mavibot/src:
main/java/org/apache/mavibot/btree/ test/java/org/apache/mavibot/btree/
Author: elecharny
Date: Sun Feb 3 05:25:28 2013
New Revision: 1441858
URL: http://svn.apache.org/viewvc?rev=1441858&view=rev
Log:
o Added a exception
o Added a delete(K, V) method
o Renamed the find() method to get()
o The get() method now throws a KeyNotFond exception if the key we are looking for does not exist : this has been done to allow the addition of null values in a BTree
Added:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/KeyNotFoundException.java
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/BTreeConfigurationTest.java
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/BTreeFlushTest.java
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/MultiThreadedBtreeTest.java
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java?rev=1441858&r1=1441857&r2=1441858&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java Sun Feb 3 05:25:28 2013
@@ -713,6 +713,40 @@ public class BTree<K, V>
/**
+ * Delete the value from an entry which key is given as a parameter. If the value
+ * is present, we will return it. If the remaining entry is empty, we will remove it
+ * from the tree.
+ *
+ * @param key The key for the entry we try to remove
+ * @return A Tuple<K, V> containing the removed entry, or null if it's not found.
+ */
+ public Tuple<K, V> delete( K key, V value ) throws IOException
+ {
+ if ( key == null )
+ {
+ throw new IllegalArgumentException( "Key must not be null" );
+ }
+
+ if ( value == null )
+ {
+ throw new IllegalArgumentException( "Value must not be null" );
+ }
+
+ long revision = generateRevision();
+
+ Tuple<K, V> deleted = delete( key, revision );
+
+ // Decrease the number of element in the current tree if the delete is successful
+ if ( deleted != null )
+ {
+ nbElems.getAndDecrement();
+ }
+
+ return deleted;
+ }
+
+
+ /**
* Delete the entry which key is given as a parameter. If the entry exists, it will
* be removed from the tree, the old tuple will be returned. Otherwise, null is returned.
*
@@ -776,9 +810,9 @@ public class BTree<K, V>
* @return The found value, or null if the key is not present in the tree
* @throws IOException TODO
*/
- public V find( K key ) throws IOException
+ public V get( K key ) throws IOException, KeyNotFoundException
{
- return rootPage.find( key );
+ return rootPage.get( key );
}
Added: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/KeyNotFoundException.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/KeyNotFoundException.java?rev=1441858&view=auto
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/KeyNotFoundException.java (added)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/KeyNotFoundException.java Sun Feb 3 05:25:28 2013
@@ -0,0 +1,72 @@
+/*
+ * 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.mavibot.btree;
+
+
+/**
+ * An exception thrown when we can't find a key in the BTree.
+ *
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+public class KeyNotFoundException extends Exception
+{
+ /** The serial version UUID */
+ private static final long serialVersionUID = 1L;
+
+
+ /**
+ * Creates a new instance of KeyNotFoundException.
+ */
+ public KeyNotFoundException()
+ {
+ }
+
+
+ /**
+ * Creates a new instance of KeyNotFoundException.
+ *
+ * @param explanation The message associated with the exception
+ */
+ public KeyNotFoundException( String explanation )
+ {
+ super( explanation );
+ }
+
+
+ /**
+ * Creates a new instance of KeyNotFoundException.
+ */
+ public KeyNotFoundException( Throwable cause )
+ {
+ super( cause );
+ }
+
+
+ /**
+ * Creates a new instance of KeyNotFoundException.
+ *
+ * @param explanation The message associated with the exception
+ * @param cause The root cause for this exception
+ */
+ public KeyNotFoundException( String explanation, Throwable cause )
+ {
+ super( explanation, cause );
+ }
+}
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java?rev=1441858&r1=1441857&r2=1441858&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java Sun Feb 3 05:25:28 2013
@@ -371,7 +371,7 @@ public class Leaf<K, V> extends Abstract
/**
* {@inheritDoc}
*/
- public V find( K key )
+ public V get( K key ) throws KeyNotFoundException
{
int pos = findPos( key );
@@ -381,7 +381,7 @@ public class Leaf<K, V> extends Abstract
}
else
{
- return null;
+ throw new KeyNotFoundException( "Cannot find an entry for key " + key );
}
}
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java?rev=1441858&r1=1441857&r2=1441858&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java Sun Feb 3 05:25:28 2013
@@ -731,7 +731,7 @@ import java.util.LinkedList;
/**
* {@inheritDoc}
*/
- public V find( K key )
+ public V get( K key ) throws KeyNotFoundException
{
int pos = findPos( key );
@@ -739,11 +739,11 @@ import java.util.LinkedList;
{
// Here, if we have found the key in the node, then we must go down into
// the right child, not the left one
- return children[-pos].find( key );
+ return children[-pos].get( key );
}
else
{
- return children[pos].find( key );
+ return children[pos].get( key );
}
}
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java?rev=1441858&r1=1441857&r2=1441858&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java Sun Feb 3 05:25:28 2013
@@ -74,12 +74,16 @@ import java.util.LinkedList;
/**
- * Find the value associated with the given key, if any.
+ * Get the value associated with the given key, if any. If we don't have
+ * one, this method will throw a KeyNotFoundException.<br/>
+ * Note that we may get back null if a null value has been associated
+ * with the key.
*
* @param key The key we are looking for
+ * @throws KeyNotFoundException If no entry with the given key can be found
* @return The associated value, or null if there is none
*/
- V find( K key );
+ V get( K key ) throws KeyNotFoundException;
/**
Modified: labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/BTreeConfigurationTest.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/BTreeConfigurationTest.java?rev=1441858&r1=1441857&r2=1441858&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/BTreeConfigurationTest.java (original)
+++ labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/BTreeConfigurationTest.java Sun Feb 3 05:25:28 2013
@@ -110,7 +110,7 @@ public class BTreeConfigurationTest
* Test the creation of a in-memory BTree using the BTreeConfiguration.
*/
@Test
- public void testConfigurationBasic() throws IOException
+ public void testConfigurationBasic() throws IOException, KeyNotFoundException
{
BTreeConfiguration<Integer, String> config = new BTreeConfiguration<Integer, String>();
config.setPageSize( 32 );
@@ -130,7 +130,7 @@ public class BTreeConfigurationTest
// Check that the tree contains all the values
for ( int key : sortedValues )
{
- String value = btree.find( key );
+ String value = btree.get( key );
assertNotNull( value );
}
@@ -144,7 +144,7 @@ public class BTreeConfigurationTest
* tree on disk, then reloading it in another BTree.
*/
@Test
- public void testConfigurationFlushReload() throws IOException
+ public void testConfigurationFlushReload() throws IOException, KeyNotFoundException
{
// Create a temporary file
File file = File.createTempFile( "testFlush", "data" );
@@ -174,7 +174,7 @@ public class BTreeConfigurationTest
// Check that the tree contains all the values
for ( int key : sortedValues )
{
- String value = btree.find( key );
+ String value = btree.get( key );
assertNotNull( value );
}
@@ -188,7 +188,7 @@ public class BTreeConfigurationTest
// Check that the tree contains all the values
for ( int key : sortedValues )
{
- String value = btreeCopy.find( key );
+ String value = btreeCopy.get( key );
assertNotNull( value );
}
Modified: labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/BTreeFlushTest.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/BTreeFlushTest.java?rev=1441858&r1=1441857&r2=1441858&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/BTreeFlushTest.java (original)
+++ labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/BTreeFlushTest.java Sun Feb 3 05:25:28 2013
@@ -43,8 +43,8 @@ import org.junit.Test;
*/
public class BTreeFlushTest
{
- /** A file containing 1 million elements */
- private static String data1M;
+ /** A file containing 100 000 elements */
+ private static String data100K;
// Some values to inject in a btree
private static int[] sortedValues = new int[]
@@ -124,7 +124,7 @@ public class BTreeFlushTest
long l1 = System.currentTimeMillis();
int n = 0;
long delta = l1;
- int nbElems = 1000000;
+ int nbElems = 100000;
BTree<Long, String> btree = new BTree<Long, String>( new LongSerializer(), new StringSerializer() );
btree.setPageSize( 32 );
@@ -148,7 +148,7 @@ public class BTreeFlushTest
return;
}
- if ( i % 100000 == 0 )
+ if ( i % 10000 == 0 )
{
if ( n > 0 )
{
@@ -177,10 +177,10 @@ public class BTreeFlushTest
long t1 = System.currentTimeMillis();
- System.out.println( "Time to flush 5 million elements : " + ( t1 - t0 ) + "ms" );
+ System.out.println( "Time to flush 100 000 elements : " + ( t1 - t0 ) + "ms" );
btree.close();
- data1M = tempFile.getCanonicalPath();
+ data100K = tempFile.getCanonicalPath();
}
@@ -200,9 +200,11 @@ public class BTreeFlushTest
// into the btree
for ( Long key : expected )
{
- String value = btree.find( key );
-
- if ( value == null )
+ try
+ {
+ btree.get( key );
+ }
+ catch ( KeyNotFoundException knfe )
{
return false;
}
@@ -290,7 +292,7 @@ public class BTreeFlushTest
@Test
public void testLoadBTreeFromFile() throws Exception
{
- File dataFile = new File( data1M );
+ File dataFile = new File( data100K );
BTree<Long, String> btree = new BTree<Long, String>(
dataFile.getParent(),
dataFile.getName(),
Modified: labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java?rev=1441858&r1=1441857&r2=1441858&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java (original)
+++ labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java Sun Feb 3 05:25:28 2013
@@ -23,7 +23,6 @@ package org.apache.mavibot.btree;
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;
@@ -126,9 +125,11 @@ public class InMemoryBTreeTest
// into the btree
for ( Long key : expected )
{
- String value = btree.find( key );
-
- if ( value == null )
+ try
+ {
+ btree.get( key );
+ }
+ catch ( KeyNotFoundException knfe )
{
return false;
}
@@ -246,7 +247,7 @@ public class InMemoryBTreeTest
* @throws Exception
*/
@Test
- public void testPageDeleteRandom() throws Exception
+ public void testPageDeleteRandom() throws IOException
{
Set<Long> expected = new HashSet<Long>();
List<Long> added = new ArrayList<Long>();
@@ -327,7 +328,8 @@ public class InMemoryBTreeTest
}
assertEquals( Long.valueOf( element ), tuple.getKey() );
- assertNull( btree.find( element ) );
+
+ checkNull( btree, element );
//System.out.println( "" );
}
@@ -418,7 +420,7 @@ public class InMemoryBTreeTest
assertEquals( Long.valueOf( value ), tuple.getKey() );
}
- assertNull( btree.find( value ) );
+ checkNull( btree, value );
}
btree.close();
@@ -523,7 +525,11 @@ public class InMemoryBTreeTest
for ( int i = 0; i < size; i++ )
{
- if ( btree.find( elems[i] ) == null )
+ try
+ {
+ btree.get( elems[i] );
+ }
+ catch ( KeyNotFoundException knfe )
{
System.out.println( "Bad tree, missing " + elems[i] + ", " + btree );
}
@@ -608,7 +614,7 @@ public class InMemoryBTreeTest
// Check that the tree contains all the values
for ( int key : sortedValues )
{
- String value = btree.find( key );
+ String value = btree.get( key );
assertNotNull( value );
}
@@ -692,7 +698,7 @@ public class InMemoryBTreeTest
// Check that the tree contains all the values
for ( int key : sortedValues )
{
- String value = btree.find( key );
+ String value = btree.get( key );
assertNotNull( value );
}
@@ -838,33 +844,47 @@ public class InMemoryBTreeTest
// The tree remains the same after the deletion
// First, no borrow nor merge
btree.delete( 1 );
- assertNull( btree.find( 1 ) );
+
+ checkNull( btree, 1 );
+
btree.insert( 1, "V1" );
btree.delete( 3 );
- assertNull( btree.find( 3 ) );
+
+ checkNull( btree, 3 );
+
btree.insert( 3, "V3" );
btree.delete( 4 );
- assertNull( btree.find( 4 ) );
+
+ checkNull( btree, 4 );
+
btree.insert( 4, "V4" );
btree.delete( 11 );
- assertNull( btree.find( 11 ) );
+
+ checkNull( btree, 11 );
+
btree.insert( 11, "V11" );
btree.delete( 20 );
- assertNull( btree.find( 20 ) );
+
+ checkNull( btree, 20 );
+
btree.insert( 20, "V20" );
btree.delete( 0 );
- assertNull( btree.find( 0 ) );
+
+ checkNull( btree, 0 );
btree.delete( 5 );
- assertNull( btree.find( 5 ) );
+
+ checkNull( btree, 5 );
btree.delete( 9 );
- assertNull( btree.find( 9 ) );
+
+ checkNull( btree, 9 );
+
btree.close();
}
@@ -893,19 +913,23 @@ public class InMemoryBTreeTest
// Delete the leftmost key
btree.delete( 1 );
- assertNull( btree.find( 1 ) );
+
+ checkNull( btree, 1 );
// Delete the rightmost key
btree.delete( 18 );
- assertNull( btree.find( 18 ) );
+
+ checkNull( btree, 18 );
// Delete one element in the left page, but not the first one
btree.delete( 5 );
- assertNull( btree.find( 5 ) );
+
+ checkNull( btree, 5 );
// Delete the one element in the right page, but the first one
btree.delete( 16 );
- assertNull( btree.find( 16 ) );
+
+ checkNull( btree, 16 );
btree.close();
@@ -918,10 +942,12 @@ public class InMemoryBTreeTest
// and delete some
btree.delete( 2 );
- assertNull( btree.find( 2 ) );
+
+ checkNull( btree, 2 );
btree.delete( 6 );
- assertNull( btree.find( 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" );
@@ -929,21 +955,25 @@ public class InMemoryBTreeTest
// and delete some
btree.delete( 98 );
- assertNull( btree.find( 98 ) );
+
+ checkNull( btree, 98 );
btree.delete( 99 );
- assertNull( btree.find( 99 ) );
+
+ checkNull( btree, 99 );
// Now try to delete elements in the middle
btree.insert( 48, "V48" );
btree.delete( 42 );
- assertNull( btree.find( 42 ) );
+
+ checkNull( btree, 42 );
btree.insert( 72, "V72" );
btree.delete( 67 );
- assertNull( btree.find( 67 ) );
+
+ checkNull( btree, 67 );
btree.close();
}
@@ -1093,7 +1123,8 @@ public class InMemoryBTreeTest
Tuple<Integer, String> removed = btree.delete( element );
assertEquals( element, removed.getKey().intValue() );
assertEquals( "v" + element, removed.getValue() );
- assertNull( btree.find( element ) );
+
+ checkNull( btree, element );
expected.remove( element );
checkTree( btree, expected );
@@ -1171,85 +1202,85 @@ public class InMemoryBTreeTest
Tuple<Integer, String> removed = btree.delete( 2 );
assertEquals( 2, removed.getKey().intValue() );
assertEquals( "v2", removed.getValue() );
- assertNull( btree.find( 2 ) );
+ checkNull( btree, 2 );
// delete the third element in the first leaf
removed = btree.delete( 7 );
assertEquals( 7, removed.getKey().intValue() );
assertEquals( "v7", removed.getValue() );
- assertNull( btree.find( 7 ) );
+ 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() );
- assertNull( btree.find( 6 ) );
+ checkNull( btree, 6 );
// delete the third element in the first leaf
removed = btree.delete( 11 );
assertEquals( 11, removed.getKey().intValue() );
assertEquals( "v11", removed.getValue() );
- assertNull( btree.find( 11 ) );
+ 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() );
- assertNull( btree.find( 99 ) );
+ checkNull( btree, 99 );
// delete the third element in the last leaf
removed = btree.delete( 98 );
assertEquals( 98, removed.getKey().intValue() );
assertEquals( "v98", removed.getValue() );
- assertNull( btree.find( 98 ) );
+ 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() );
- assertNull( btree.find( 94 ) );
+ checkNull( btree, 94 );
// delete the third element in the last leaf
removed = btree.delete( 95 );
assertEquals( 95, removed.getKey().intValue() );
assertEquals( "v95", removed.getValue() );
- assertNull( btree.find( 95 ) );
+ 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() );
- assertNull( btree.find( 22 ) );
+ checkNull( btree, 22 );
// delete the third element in the last leaf
removed = btree.delete( 27 );
assertEquals( 27, removed.getKey().intValue() );
assertEquals( "v27", removed.getValue() );
- assertNull( btree.find( 27 ) );
+ 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() );
- assertNull( btree.find( 70 ) );
+ checkNull( btree, 70 );
// delete the third element in the leaf
removed = btree.delete( 71 );
assertEquals( 71, removed.getKey().intValue() );
assertEquals( "v71", removed.getValue() );
- assertNull( btree.find( 71 ) );
+ 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() );
- assertNull( btree.find( 51 ) );
+ checkNull( btree, 51 );
// delete the third element in the leaf
removed = btree.delete( 50 );
assertEquals( 50, removed.getKey().intValue() );
assertEquals( "v50", removed.getValue() );
- assertNull( btree.find( 50 ) );
+ checkNull( btree, 50 );
btree.close();
}
@@ -1268,31 +1299,31 @@ public class InMemoryBTreeTest
// Test removals leadings to various merges.
// Delete from the middle, not the leftmost value of the leaf
btree.delete( 10 );
- assertNull( btree.find( 10 ) );
+ checkNull( btree, 10 );
// Delete the extraneous value
btree.delete( 9 );
- assertNull( btree.find( 9 ) );
+ checkNull( btree, 9 );
// Delete the leftmost element in the middle
btree.delete( 13 );
- assertNull( btree.find( 13 ) );
+ checkNull( btree, 13 );
// Delete the extraneous value
btree.delete( 14 );
- assertNull( btree.find( 14 ) );
+ checkNull( btree, 14 );
// Delete the rightmost value
btree.delete( 18 );
- assertNull( btree.find( 18 ) );
+ checkNull( btree, 18 );
// Delete the extraneous value
btree.delete( 5 );
- assertNull( btree.find( 5 ) );
+ checkNull( btree, 5 );
// Delete the leftmost value of the right leaf
btree.delete( 6 );
- assertNull( btree.find( 6 ) );
+ checkNull( btree, 6 );
btree.close();
}
@@ -1618,14 +1649,14 @@ public class InMemoryBTreeTest
* @throws Exception
*/
@Test
- public void testBrowse5M() throws Exception
+ public void testBrowse500K() throws Exception
{
Random random = new Random( System.nanoTime() );
int nbError = 0;
int n = 0;
- int nbElems = 5000000;
+ int nbElems = 500000;
long delta = System.currentTimeMillis();
// Create a BTree with 5 million entries
@@ -1692,4 +1723,32 @@ public class InMemoryBTreeTest
System.out.println( "Delta : " + ( l2 - l1 ) + ", nbError = " + nbError
+ ", Nb searches per second : " + ( ( nbElems ) / ( l2 - l1 ) ) * 1000 );
}
+
+
+ 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
+ }
+ }
}
Modified: labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java?rev=1441858&r1=1441857&r2=1441858&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java (original)
+++ labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java Sun Feb 3 05:25:28 2013
@@ -21,8 +21,8 @@ package org.apache.mavibot.btree;
import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
import java.io.IOException;
@@ -130,10 +130,26 @@ public class LeafTest
assertEquals( "v3", removedElement.getValue() );
assertEquals( 3, newLeaf.getNbElems() );
- assertEquals( "v1", newLeaf.find( 1L ) );
- assertEquals( "v2", newLeaf.find( 2L ) );
- assertNull( newLeaf.find( 3L ) );
- assertEquals( "v4", newLeaf.find( 4L ) );
+ 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
+ }
}
@@ -163,10 +179,26 @@ public class LeafTest
assertEquals( "v1", removedElement.getValue() );
assertEquals( 3, newLeaf.getNbElems() );
- assertNull( newLeaf.find( 1L ) );
- assertEquals( "v2", newLeaf.find( 2L ) );
- assertEquals( "v3", newLeaf.find( 3L ) );
- assertEquals( "v4", newLeaf.find( 4L ) );
+ 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();
+ }
}
Modified: labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/MultiThreadedBtreeTest.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/MultiThreadedBtreeTest.java?rev=1441858&r1=1441857&r2=1441858&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/MultiThreadedBtreeTest.java (original)
+++ labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/MultiThreadedBtreeTest.java Sun Feb 3 05:25:28 2013
@@ -21,6 +21,7 @@ package org.apache.mavibot.btree;
import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.fail;
import java.io.IOException;
import java.util.Random;
@@ -203,7 +204,7 @@ public class MultiThreadedBtreeTest
long t1 = System.currentTimeMillis();
- System.out.println( " Time to create 5M entries and to have " + nbThreads + " threads reading them : "
+ System.out.println( " Time to create 500K entries and to have " + nbThreads + " threads reading them : "
+ ( ( t1 - t0 ) / 1000 ) + " seconds" );
}
@@ -231,10 +232,10 @@ public class MultiThreadedBtreeTest
{
try
{
- // Inject 100000 elements
- for ( int j = 0; j < 100000; j++ )
+ // Inject 10000 elements
+ for ( int j = 0; j < 10000; j++ )
{
- long value = prefix * 100000 + j;
+ long value = prefix * 10000 + j;
btree.insert( value, Long.toString( value ) );
/*
@@ -264,9 +265,16 @@ public class MultiThreadedBtreeTest
long t1 = System.currentTimeMillis();
// Check that the tree contains all the values
- for ( long i = 0L; i < 1000000L; i++ )
+ try
{
- assertEquals( Long.toString( i ), btree.find( i ) );
+ for ( long i = 0L; i < 100000L; i++ )
+ {
+ assertEquals( Long.toString( i ), btree.get( i ) );
+ }
+ }
+ catch ( KeyNotFoundException knfe )
+ {
+ fail();
}
System.out.println( " Time to create 1M entries : "
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@labs.apache.org
For additional commands, e-mail: commits-help@labs.apache.org