You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@labs.apache.org by ka...@apache.org on 2013/04/08 21:04:13 UTC
svn commit: r1465727 - in
/labs/mavibot/branches/mavibot-multivalue-support/mavibot/src:
main/java/org/apache/mavibot/btree/Cursor.java
test/java/org/apache/mavibot/btree/BTreeDuplicateKeyTest.java
Author: kayyagari
Date: Mon Apr 8 19:04:13 2013
New Revision: 1465727
URL: http://svn.apache.org/r1465727
Log:
o fixed cursor navigation when a leaf if full and duplicates are enabled
o added a test case
Modified:
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/BTreeDuplicateKeyTest.java
Modified: labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java
URL: http://svn.apache.org/viewvc/labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java?rev=1465727&r1=1465726&r2=1465727&view=diff
==============================================================================
--- labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java (original)
+++ labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java Mon Apr 8 19:04:13 2013
@@ -122,9 +122,10 @@ public class Cursor<K, V>
tuple.setValue( parentPos.dupsContainer.rootPage.getKey( parentPos.dupPos ) );
parentPos.dupPos++;
- if( parentPos.dupsContainer.rootPage.getNbElems() == parentPos.dupPos )
+ if( parentPos.dupsContainer.getNbElems() == parentPos.dupPos )
{
parentPos.pos++;
+ changeNextDupsContainer( parentPos );
}
}
else
@@ -241,8 +242,7 @@ public class Cursor<K, V>
if( allowDuplicates )
{
- setDupsContainer( newParentPos );
- parentPos.dupPos = ( int ) newParentPos.dupsContainer.getNbElems();
+ changePrevDupsContainer( newParentPos );
}
return newParentPos;
@@ -300,9 +300,8 @@ public class Cursor<K, V>
}
else if( parentPos.dupPos == 0 )
{
+ changePrevDupsContainer( parentPos );
parentPos.pos--;
- setDupsContainer( parentPos );
- parentPos.dupPos = ( int ) parentPos.dupsContainer.getNbElems();
parentPos.dupPos--;
}
else
@@ -341,7 +340,7 @@ public class Cursor<K, V>
for( ParentPos<K, V> p : stack )
{
- if( allowDuplicates )
+ if( allowDuplicates && ( p.page instanceof Leaf ) )
{
if ( ( p.dupPos != p.dupsContainer.getNbElems() )
&& ( p.pos != p.page.getNbElems() ) )
@@ -376,7 +375,7 @@ public class Cursor<K, V>
for( ParentPos<K, V> p : stack )
{
- if( allowDuplicates )
+ if( allowDuplicates && ( p.page instanceof Leaf ) )
{
if( ( p.dupPos != 0 )
|| ( p.pos != 0 ) )
@@ -430,4 +429,28 @@ public class Cursor<K, V>
parentPos.dupsContainer = dupsContainer;
}
}
+
+ private void changeNextDupsContainer( ParentPos<K, V> parentPos ) throws IOException
+ {
+ if( parentPos.pos < parentPos.page.getNbElems() )
+ {
+ Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
+ BTree<V, V> dupsContainer = ( BTree<V, V> ) leaf.values[parentPos.pos].getValue( btree );
+ parentPos.dupsContainer = dupsContainer;
+ parentPos.dupPos = 0;
+ }
+ }
+
+ private void changePrevDupsContainer( ParentPos<K, V> parentPos ) throws IOException
+ {
+ int index = parentPos.pos - 1;
+ if( index >= 0 )
+ {
+ Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
+ BTree<V, V> dupsContainer = ( BTree<V, V> ) leaf.values[index].getValue( btree );
+ parentPos.dupsContainer = dupsContainer;
+ parentPos.dupPos = ( int ) parentPos.dupsContainer.getNbElems();
+ }
+ }
+
}
Modified: labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/BTreeDuplicateKeyTest.java
URL: http://svn.apache.org/viewvc/labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/BTreeDuplicateKeyTest.java?rev=1465727&r1=1465726&r2=1465727&view=diff
==============================================================================
--- labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/BTreeDuplicateKeyTest.java (original)
+++ labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/BTreeDuplicateKeyTest.java Mon Apr 8 19:04:13 2013
@@ -26,8 +26,10 @@ import static org.junit.Assert.assertTru
import java.io.IOException;
import java.util.NoSuchElementException;
+import java.util.UUID;
import org.apache.mavibot.btree.serializer.IntSerializer;
+import org.apache.mavibot.btree.serializer.StringSerializer;
import org.junit.Test;
@@ -178,10 +180,10 @@ public class BTreeDuplicateKeyTest
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 );
@@ -198,6 +200,7 @@ public class BTreeDuplicateKeyTest
assertFalse( btree.contains( null, null ) );
}
+
@Test
public void testRemoveDuplicateKey() throws Exception
{
@@ -211,22 +214,80 @@ public class BTreeDuplicateKeyTest
btree.insert( 1, 1 );
btree.insert( 1, 2 );
-
+
assertEquals( 2l, btree.getNbElems() );
-
- Tuple<Integer,Integer> t = btree.delete( 1, 1 );
+
+ 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();
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@labs.apache.org
For additional commands, e-mail: commits-help@labs.apache.org