You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by ka...@apache.org on 2014/08/03 20:25:42 UTC
svn commit: r1615428 - in /directory/mavibot/trunk/mavibot/src:
main/java/org/apache/directory/mavibot/btree/
test/java/org/apache/directory/mavibot/btree/
Author: kayyagari
Date: Sun Aug 3 18:25:41 2014
New Revision: 1615428
URL: http://svn.apache.org/r1615428
Log:
o added support for replacing value of an existing key
o fixed an issue in InMemoryBTree when a key already exists
o fixed an NPE in findLeftMost() findRightMost() of PersistedLeaf of a persisted sub-BTree
o made RevisionName serializable
o added and updated tests
Modified:
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractValueHolder.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RevisionName.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/SpaceReclaimer.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ValueHolder.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeDuplicateKeyTest.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeTest.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBrowseTest.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeDuplicateKeyTest.java
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractValueHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractValueHolder.java?rev=1615428&r1=1615427&r2=1615428&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractValueHolder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractValueHolder.java Sun Aug 3 18:25:41 2014
@@ -375,4 +375,25 @@ import org.apache.directory.mavibot.btre
addInBtree( value );
}
}
+
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public V replaceValueArray( V newValue )
+ {
+ if( isSubBtree() )
+ {
+ throw new IllegalStateException( "method is not applicable for the duplicate B-Trees" );
+ }
+
+ V tmp = valueArray[0];
+
+ nbArrayElems = 1;
+ valueArray[0] = newValue;
+
+ return tmp;
+ }
+
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java?rev=1615428&r1=1615427&r2=1615428&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java Sun Aug 3 18:25:41 2014
@@ -389,6 +389,11 @@ import org.slf4j.LoggerFactory;
// a Node or a Leaf
InsertResult<K, V> result = newBtreeHeader.getRootPage().insert( key, value, revision );
+ if ( result instanceof ExistsResult )
+ {
+ return result;
+ }
+
if ( result instanceof ModifyResult )
{
ModifyResult<K, V> modifyResult = ( ( ModifyResult<K, V> ) result );
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java?rev=1615428&r1=1615427&r2=1615428&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java Sun Aug 3 18:25:41 2014
@@ -748,12 +748,6 @@ import org.apache.directory.mavibot.btre
boolean valueExists = valueHolder.contains( value );
- // Check we can add a new value
- if ( !valueExists && !btree.isAllowDuplicates() )
- {
- throw new DuplicateValueNotAllowedException( "Duplicate values are not allowed" );
- }
-
if ( this.revision != revision )
{
// The page hasn't been modified yet, we need to copy it first
@@ -764,12 +758,12 @@ import org.apache.directory.mavibot.btre
valueHolder = newLeaf.values[pos];
V replacedValue = null;
- if ( !valueExists )
+ if ( !valueExists && btree.isAllowDuplicates() )
{
valueHolder.add( value );
newLeaf.values[pos] = valueHolder;
}
- else
+ else if ( valueExists && btree.isAllowDuplicates() )
{
// As strange as it sounds, we need to remove the value to reinject it.
// There are cases where the value retrieval just use one part of the
@@ -777,6 +771,10 @@ import org.apache.directory.mavibot.btre
replacedValue = valueHolder.remove( value );
valueHolder.add( value );
}
+ else if ( !btree.isAllowDuplicates() )
+ {
+ replacedValue = valueHolder.replaceValueArray( value );
+ }
// Create the result
InsertResult<K, V> result = new ModifyResult<K, V>( newLeaf, replacedValue );
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java?rev=1615428&r1=1615427&r2=1615428&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java Sun Aug 3 18:25:41 2014
@@ -844,26 +844,29 @@ import static org.apache.directory.mavib
// Copy the keys and the values
System.arraycopy( keys, 0, newLeaf.keys, 0, nbElems );
- // It' not enough to copy the ValueHolder, we have to clone them
- // as ValueHolders are mutable
- int pos = 0;
-
- for ( ValueHolder<V> valueHolder : values )
+ if ( values != null )
{
- try
+ // It' not enough to copy the ValueHolder, we have to clone them
+ // as ValueHolders are mutable
+ int pos = 0;
+
+ for ( ValueHolder<V> valueHolder : values )
{
- newLeaf.values[pos++] = valueHolder.clone();
- }
- catch ( CloneNotSupportedException e )
- {
- // TODO Auto-generated catch block
- e.printStackTrace();
- }
-
- // Stop when we have copied nbElems values
- if ( pos == nbElems )
- {
- break;
+ try
+ {
+ newLeaf.values[pos++] = valueHolder.clone();
+ }
+ catch ( CloneNotSupportedException e )
+ {
+ // TODO Auto-generated catch block
+ e.printStackTrace();
+ }
+
+ // Stop when we have copied nbElems values
+ if ( pos == nbElems )
+ {
+ break;
+ }
}
}
@@ -891,17 +894,6 @@ import static org.apache.directory.mavib
boolean valueExists = valueHolder.contains( value );
- // Check we can add a new value
- if ( !valueExists && !btree.isAllowDuplicates() )
- {
- throw new DuplicateValueNotAllowedException( "Duplicate values are not allowed" );
- }
-
- if ( valueExists )
- {
- return ExistsResult.EXISTS;
- }
-
if ( this.revision != revision )
{
// The page hasn't been modified yet, we need to copy it first
@@ -912,21 +904,24 @@ import static org.apache.directory.mavib
valueHolder = newLeaf.values[pos];
V replacedValue = null;
- if ( !valueExists )
+ if ( !valueExists && btree.isAllowDuplicates() )
{
valueHolder.add( value );
newLeaf.values[pos] = valueHolder;
}
- else
+ else if ( valueExists && btree.isAllowDuplicates() )
{
- // this block should be deleted after fixing MAVIBOT-39
// As strange as it sounds, we need to remove the value to reinject it.
// There are cases where the value retrieval just use one part of the
// value only (typically for LDAP Entries, where we use the DN)
- //replacedValue = valueHolder.remove( value );
- //valueHolder.add( value );
+ replacedValue = valueHolder.remove( value );
+ valueHolder.add( value );
}
-
+ else if ( !btree.isAllowDuplicates() )
+ {
+ replacedValue = valueHolder.replaceValueArray( value );
+ }
+
// Create the result
InsertResult<K, V> result = new ModifyResult<K, V>( newLeaf, replacedValue );
result.addCopiedPage( this );
@@ -1096,6 +1091,15 @@ import static org.apache.directory.mavib
*/
public Tuple<K, V> findLeftMost() throws IOException
{
+ K key = keys[0].getKey();
+
+ boolean isSubTree = ( btree.getType() == PERSISTED_SUB );
+
+ if ( isSubTree )
+ {
+ return new Tuple<K, V>( key, null );
+ }
+
ValueCursor<V> cursor = values[0].getCursor();
try
@@ -1103,12 +1107,12 @@ import static org.apache.directory.mavib
cursor.beforeFirst();
if ( cursor.hasNext() )
{
- return new Tuple<K, V>( keys[0].getKey(), cursor.next() );
+ return new Tuple<K, V>( key, cursor.next() );
}
else
{
// Null value
- return new Tuple<K, V>( keys[0].getKey(), null );
+ return new Tuple<K, V>( key, null );
}
}
finally
@@ -1123,6 +1127,16 @@ import static org.apache.directory.mavib
*/
public Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException
{
+
+ K key = keys[nbElems - 1].getKey();
+
+ boolean isSubTree = ( btree.getType() == PERSISTED_SUB );
+
+ if ( isSubTree )
+ {
+ return new Tuple<K, V>( key, null );
+ }
+
ValueCursor<V> cursor = values[nbElems - 1].getCursor();
try
@@ -1131,12 +1145,12 @@ import static org.apache.directory.mavib
if ( cursor.hasPrev() )
{
- return new Tuple<K, V>( keys[nbElems - 1].getKey(), cursor.prev() );
+ return new Tuple<K, V>( key, cursor.prev() );
}
else
{
// Null value
- return new Tuple<K, V>( keys[nbElems - 1].getKey(), null );
+ return new Tuple<K, V>( key, null );
}
}
finally
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java?rev=1615428&r1=1615427&r2=1615428&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java Sun Aug 3 18:25:41 2014
@@ -410,6 +410,8 @@ import static org.apache.directory.mavib
}
}
+ cursor.close();
+
return returnedValue;
}
else
@@ -636,6 +638,17 @@ import static org.apache.directory.mavib
}
+ @Override
+ public V replaceValueArray( V newValue )
+ {
+ V val = super.replaceValueArray( newValue );
+ // The raw value is not anymore up to date with the content
+ isRawUpToDate = false;
+
+ return val;
+ }
+
+
/**
* Deserialize the values stored in an array
*/
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RevisionName.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RevisionName.java?rev=1615428&r1=1615427&r2=1615428&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RevisionName.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RevisionName.java Sun Aug 3 18:25:41 2014
@@ -19,6 +19,8 @@
*/
package org.apache.directory.mavibot.btree;
+import java.io.Serializable;
+
/**
* A data structure that stores a revision associated to a BTree name. We use
@@ -26,7 +28,7 @@ package org.apache.directory.mavibot.btr
*
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
*/
-/* no qualifier*/class RevisionName extends Tuple<Long, String>
+/* no qualifier*/class RevisionName extends Tuple<Long, String> implements Serializable
{
/**
* A constructor for the RevisionName class
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/SpaceReclaimer.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/SpaceReclaimer.java?rev=1615428&r1=1615427&r2=1615428&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/SpaceReclaimer.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/SpaceReclaimer.java Sun Aug 3 18:25:41 2014
@@ -83,7 +83,7 @@ public class SpaceReclaimer
try
{
- LOG.debug( "Storing {} RevisionName of Copied page map", rm.copiedPageMap.size() );
+ LOG.debug( "Storing {} RevisionNames of Copied page map", rm.copiedPageMap.size() );
OutputStream fileOut = new FileOutputStream( file );
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ValueHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ValueHolder.java?rev=1615428&r1=1615427&r2=1615428&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ValueHolder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ValueHolder.java Sun Aug 3 18:25:41 2014
@@ -69,6 +69,18 @@ package org.apache.directory.mavibot.btr
*/
V remove( V removedValue );
+
+ /**
+ * Replaces the single value present in the array.
+ *
+ * This is only applicable for B-Trees that don't
+ * support duplicate values.
+ *
+ * @param newValue the new value
+ * @return the value that was replaced
+ */
+ V replaceValueArray( V newValue );
+
/**
* Create a clone of this instance
Modified: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeDuplicateKeyTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeDuplicateKeyTest.java?rev=1615428&r1=1615427&r2=1615428&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeDuplicateKeyTest.java (original)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeDuplicateKeyTest.java Sun Aug 3 18:25:41 2014
@@ -37,6 +37,7 @@ import org.apache.directory.mavibot.btre
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;
@@ -743,6 +744,7 @@ public class InMemoryBTreeDuplicateKeyTe
* Test that a BTree which forbid duplicate values does not accept them
*/
@Test(expected = DuplicateValueNotAllowedException.class)
+ @Ignore("this condition is removed")
public void testBTreeForbidDups() throws IOException, BTreeAlreadyManagedException
{
BTree<Long, String> singleValueBtree = BTreeFactory.createInMemoryBTree( "test2", LongSerializer.INSTANCE,
Modified: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeTest.java?rev=1615428&r1=1615427&r2=1615428&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeTest.java (original)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeTest.java Sun Aug 3 18:25:41 2014
@@ -1982,4 +1982,29 @@ public class InMemoryBTreeTest
btree.close();
}
+
+
+ /**
+ * Test the overwriting of elements
+ */
+ @Test
+ public void testOverwrite() throws Exception
+ {
+ BTree<Integer, Integer> btree = BTreeFactory.createInMemoryBTree( "test", IntSerializer.INSTANCE,
+ IntSerializer.INSTANCE );
+
+ // Adding an element with a null value
+ btree.insert( 1, 1 );
+
+ assertTrue( btree.hasKey( 1 ) );
+
+ assertEquals( Integer.valueOf( 1 ), btree.get( 1 ) );
+
+ btree.insert( 1, 10 );
+
+ assertTrue( btree.hasKey( 1 ) );
+ assertEquals( Integer.valueOf( 10 ), btree.get( 1 ) );
+
+ btree.close();
+ }
}
Modified: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBrowseTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBrowseTest.java?rev=1615428&r1=1615427&r2=1615428&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBrowseTest.java (original)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBrowseTest.java Sun Aug 3 18:25:41 2014
@@ -36,6 +36,7 @@ import org.apache.commons.io.FileUtils;
import org.apache.directory.mavibot.btree.exception.BTreeAlreadyManagedException;
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.After;
@@ -1107,6 +1108,30 @@ public class PersistedBTreeBrowseTest
}
+ /**
+ * Test the overwriting of elements
+ */
+ @Test
+ public void testOverwrite() throws Exception
+ {
+ btree.setAllowDuplicates( false );
+
+ // Adding an element with a null value
+ btree.insert( 1L, "1" );
+
+ assertTrue( btree.hasKey( 1L ) );
+
+ assertEquals( "1", btree.get( 1L ) );
+
+ btree.insert( 1L, "10" );
+
+ assertTrue( btree.hasKey( 1L ) );
+ assertEquals( "10", btree.get( 1L ) );
+
+ btree.close();
+ }
+
+
@Ignore("test used for debugging")
@Test
public void testAdd20Random() throws IOException, BTreeAlreadyManagedException, KeyNotFoundException
Modified: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeDuplicateKeyTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeDuplicateKeyTest.java?rev=1615428&r1=1615427&r2=1615428&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeDuplicateKeyTest.java (original)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeDuplicateKeyTest.java Sun Aug 3 18:25:41 2014
@@ -41,6 +41,7 @@ import org.apache.directory.mavibot.btre
import org.apache.directory.mavibot.btree.serializer.StringSerializer;
import org.junit.After;
import org.junit.Before;
+import org.junit.Ignore;
import org.junit.Rule;
import org.junit.Test;
import org.junit.rules.TemporaryFolder;
@@ -792,11 +793,40 @@ public class PersistedBTreeDuplicateKeyT
cursor.close();
}
+
+ @Test
+ public void testFindLeftAndRightMosetInSubBTree() throws Exception
+ {
+ PersistedBTreeConfiguration<Integer, Integer> config = new PersistedBTreeConfiguration<Integer, Integer>();
+
+ config.setName( "test" );
+ config.setKeySerializer( IntSerializer.INSTANCE );
+ config.setValueSerializer( IntSerializer.INSTANCE );
+ config.setAllowDuplicates( false );
+ config.setBtreeType( BTreeTypeEnum.PERSISTED_SUB );
+
+ PersistedBTree<Integer, Integer> subBtree = new PersistedBTree<Integer, Integer>( config );
+
+ subBtree.setRecordManager( recordManager1 );
+
+ subBtree.insert( 1, 1 ); // the values will be discarded in this BTree type
+ subBtree.insert( 2, 2 );
+ subBtree.insert( 3, 3 );
+ subBtree.insert( 4, 4 );
+ subBtree.insert( 5, 5 );
+
+ Tuple<Integer, Integer> t = subBtree.getRootPage().findLeftMost();
+ assertEquals( Integer.valueOf( 1 ), t.getKey() );
+
+ t = subBtree.getRootPage().findRightMost();
+ assertEquals( Integer.valueOf( 5 ), t.getKey() );
+ }
/**
* Test that a BTree which forbid duplicate values does not accept them
*/
@Test(expected = DuplicateValueNotAllowedException.class)
+ @Ignore("this condition is removed")
public void testBTreeForbidDups() throws IOException, BTreeAlreadyManagedException
{
BTree<Long, String> singleValueBtree = recordManager1.addBTree( "test2", LongSerializer.INSTANCE,