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/12/13 15:01:33 UTC
svn commit: r1550730 - in /directory/mavibot/trunk/mavibot/src:
main/java/org/apache/directory/mavibot/btree/
main/java/org/apache/directory/mavibot/btree/memory/
main/java/org/apache/directory/mavibot/btree/persisted/
test/java/org/apache/directory/ma...
Author: elecharny
Date: Fri Dec 13 14:01:33 2013
New Revision: 1550730
URL: http://svn.apache.org/r1550730
Log:
o Moved the getCursor(), findPos(), arrayContains(), btreeContains(), contains(), addInArray(), addInBtree() and ad() method to the AbstractValueHolder
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/memory/InMemoryValueHolder.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/persisted/PersistedValueHolder.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/persisted/RecordManagerWithDuplicatesTest.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=1550730&r1=1550729&r2=1550730&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 Fri Dec 13 14:01:33 2013
@@ -19,6 +19,13 @@
*/
package org.apache.directory.mavibot.btree;
+import java.io.IOException;
+import java.lang.reflect.Array;
+import java.util.Comparator;
+
+import org.apache.directory.mavibot.btree.persisted.PersistedBTree;
+import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
+
/**
* A holder to store the Values
@@ -33,10 +40,13 @@ public abstract class AbstractValueHolde
/** The array storing from 1 to N values */
protected V[] valueArray;
-
- /** The parent BTree */
- protected BTree<?, V> parentBtree;
-
+
+ /** The Value serializer */
+ protected ElementSerializer<V> valueSerializer;
+
+ /** The configuration for the array <-> BTree switch. Default to 1 */
+ protected int valueThresholdUp = 1;
+ protected int valueThresholdLow = 1;
/**
* {@inheritDoc}
@@ -56,4 +66,294 @@ public abstract class AbstractValueHolde
return copy;
}
+
+
+ /**
+ * @return a cursor on top of the values
+ */
+ public ValueCursor<V> getCursor()
+ {
+ if ( valueBtree != null )
+ {
+ return new ValueBTreeCursor<V>( valueBtree );
+ }
+ else
+ {
+ return new ValueArrayCursor<V>( valueArray );
+ }
+ }
+
+
+ /**
+ * Find the position of a given value in the array, or the position where we
+ * would insert the element (in this case, the position will be negative).
+ * As we use a 0-based array, the negative position for 0 is -1.
+ * -1 means the element can be added in position 0
+ * -2 means the element can be added in position 1
+ * ...
+ */
+ private int findPos( V value )
+ {
+ if ( valueArray.length == 0 )
+ {
+ return -1;
+ }
+
+ // Do a search using dichotomy
+ int pivot = valueArray.length / 2;
+ int low = 0;
+ int high = valueArray.length - 1;
+ Comparator<V> comparator = valueSerializer.getComparator();
+
+ while ( high > low )
+ {
+ switch ( high - low )
+ {
+ case 1:
+ // We have 2 elements
+ int result = comparator.compare( value, valueArray[pivot] );
+
+ if ( result == 0 )
+ {
+ return pivot;
+ }
+
+ if ( result < 0 )
+ {
+ if ( pivot == low )
+ {
+ return -( low + 1 );
+ }
+ else
+ {
+ result = comparator.compare( value, valueArray[low] );
+
+ if ( result == 0 )
+ {
+ return low;
+ }
+
+ if ( result < 0 )
+ {
+ return -( low + 1 );
+ }
+ else
+ {
+ return -( low + 2 );
+ }
+ }
+ }
+ else
+ {
+ if ( pivot == high )
+ {
+ return -( high + 2 );
+ }
+ else
+ {
+ result = comparator.compare( value, valueArray[high] );
+
+ if ( result == 0 )
+ {
+ return high;
+ }
+
+ if ( result < 0 )
+ {
+ return -( high + 1 );
+ }
+ else
+ {
+ return -( high + 2 );
+ }
+ }
+ }
+
+ default:
+ // We have 3 elements
+ result = comparator.compare( value, valueArray[pivot] );
+
+ if ( result == 0 )
+ {
+ return pivot;
+ }
+
+ if ( result < 0 )
+ {
+ high = pivot - 1;
+ }
+ else
+ {
+ low = pivot + 1;
+ }
+
+ pivot = ( high + low ) / 2;
+
+ continue;
+ }
+ }
+
+ int result = comparator.compare( value, valueArray[pivot] );
+
+ if ( result == 0 )
+ {
+ return pivot;
+ }
+
+ if ( result < 0 )
+ {
+ return -( pivot + 1 );
+ }
+ else
+ {
+ return -( pivot + 2 );
+ }
+ }
+
+
+ /**
+ * Check if the array of values contains a given value
+ */
+ private boolean arrayContains( V value )
+ {
+ if ( valueArray.length == 0 )
+ {
+ return false;
+ }
+
+ // Do a search using dichotomy
+ return findPos( value ) >= 0;
+ }
+
+
+ /**
+ * Check if the subBtree contains a given value
+ */
+ protected boolean btreeContains( V value )
+ {
+ try
+ {
+ return valueBtree.hasKey( value );
+ }
+ catch ( IOException e )
+ {
+ // TODO Auto-generated catch block
+ e.printStackTrace();
+ return false;
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean contains( V checkedValue )
+ {
+ if ( valueArray == null )
+ {
+ return btreeContains( checkedValue );
+ }
+ else
+ {
+ return arrayContains( checkedValue );
+ }
+ }
+
+
+ /**
+ * Create a new Sub-BTree to store the values.
+ */
+ protected abstract void createSubTree();
+
+
+ /**
+ * Add the value in an array
+ */
+ private void addInArray( V value )
+ {
+ // We have to check that we have reached the threshold or not
+ if ( valueArray.length >= valueThresholdUp )
+ {
+ // Ok, transform the array into a btree
+ createSubTree();
+
+ try
+ {
+ for ( V val : valueArray )
+ {
+ // Here, we should insert all the values in one shot then
+ // write the btree on disk only once.
+ valueBtree.insert( val, null );
+ }
+
+ // We can delete the array now
+ valueArray = null;
+
+ // And inject the new value
+ valueBtree.insert( value, null );
+ }
+ catch ( IOException e )
+ {
+ // TODO Auto-generated catch block
+ e.printStackTrace();
+ }
+ }
+ else
+ {
+ // First check that the value is not already present in the ValueHolder
+ int pos = findPos( value );
+
+ if ( pos >= 0 )
+ {
+ // The value exists : nothing to do
+ return;
+ }
+
+ // Ok, we just have to insert the new element at the right position
+ // We transform the position to a positive value
+ pos = -( pos + 1 );
+ // First, copy the array
+ V[] newValueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), valueArray.length + 1 );
+
+ System.arraycopy( valueArray, 0, newValueArray, 0, pos );
+ newValueArray[pos] = value;
+ System.arraycopy( valueArray, pos, newValueArray, pos + 1, valueArray.length - pos );
+
+ // And switch the arrays
+ valueArray = newValueArray;
+ }
+ }
+
+
+ /**
+ * Add the value in the subBTree
+ */
+ private void addInBtree( V value )
+ {
+ try
+ {
+ valueBtree.insert( value, null );
+ }
+ catch ( IOException e )
+ {
+ // TODO Auto-generated catch block
+ e.printStackTrace();
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public void add( V value )
+ {
+ if ( valueArray != null )
+ {
+ addInArray( value );
+ }
+ else
+ {
+ addInBtree( value );
+ }
+ }
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryValueHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryValueHolder.java?rev=1550730&r1=1550729&r2=1550730&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryValueHolder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InMemoryValueHolder.java Fri Dec 13 14:01:33 2013
@@ -28,9 +28,6 @@ import java.util.UUID;
import org.apache.directory.mavibot.btree.AbstractValueHolder;
import org.apache.directory.mavibot.btree.BTree;
import org.apache.directory.mavibot.btree.Tuple;
-import org.apache.directory.mavibot.btree.ValueArrayCursor;
-import org.apache.directory.mavibot.btree.ValueCursor;
-import org.apache.directory.mavibot.btree.ValueBTreeCursor;
import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
@@ -53,7 +50,7 @@ public class InMemoryValueHolder<V> exte
*/
InMemoryValueHolder( BTree<?, V> parentBtree, int nbValues )
{
- this.parentBtree = parentBtree;
+ valueSerializer = parentBtree.getValueSerializer();
}
@@ -66,7 +63,7 @@ public class InMemoryValueHolder<V> exte
*/
InMemoryValueHolder( BTree<?, V> parentBtree, V... values )
{
- this.parentBtree = parentBtree;
+ valueSerializer = parentBtree.getValueSerializer();
if ( ( values != null ) && ( values.length > 0 ) )
{
@@ -100,26 +97,6 @@ public class InMemoryValueHolder<V> exte
/**
- * @return a cursor on top of the values
- */
- public ValueCursor<V> getCursor()
- {
- ValueCursor<V> cursor;
-
- if ( valueBtree != null )
- {
- cursor = new ValueBTreeCursor<V>( valueBtree );
- }
- else
- {
- cursor = new ValueArrayCursor<V>( valueArray );
- }
-
- return cursor;
- }
-
-
- /**
* {@inheritDoc}
*/
public int size()
@@ -138,14 +115,16 @@ public class InMemoryValueHolder<V> exte
/**
* Create a new Sub-BTree to store the values.
*/
- private void createSubTree()
+ protected void createSubTree()
{
try
{
BTreeConfiguration<V, V> configuration = new BTreeConfiguration<V, V>();
configuration.setAllowDuplicates( false );
configuration.setName( UUID.randomUUID().toString() );
-
+ configuration.setKeySerializer( valueSerializer );
+ configuration.setValueSerializer( valueSerializer );
+
valueBtree = new InMemoryBTree<V, V>( configuration );
}
catch ( IOException e )
@@ -166,67 +145,6 @@ public class InMemoryValueHolder<V> exte
/**
- * Add the value in an array
- */
- private void addInBTree( V newValue )
- {
- // Ok, create a sub-btree
- try
- {
- valueBtree = new InMemoryBTree<V, V>( UUID.randomUUID().toString(), parentBtree.getValueSerializer(),
- parentBtree.getValueSerializer() );
-
- valueBtree.insert( valueArray[0], null, 0 );
- valueBtree.insert( newValue, null, 0 );
- valueArray = null;
- }
- catch ( IOException e )
- {
- throw new RuntimeException( e );
- }
- }
-
-
- /**
- * {@inheritDoc}
- */
- public void add( V newValue )
- {
- if ( ( valueArray != null ) && ( valueArray.length > 0 ) )
- {
- try
- {
- valueBtree = new InMemoryBTree<V, V>( UUID.randomUUID().toString(), parentBtree.getValueSerializer(),
- parentBtree.getValueSerializer() );
-
- valueBtree.insert( valueArray[0], null, 0 );
- valueBtree.insert( newValue, null, 0 );
- valueArray = null;
- }
- catch ( IOException e )
- {
- throw new RuntimeException( e );
- }
- }
- else if ( valueBtree != null )
- {
- try
- {
- valueBtree.insert( newValue, null, 0 );
- }
- catch ( IOException e )
- {
- throw new RuntimeException( e );
- }
- }
- else
- {
- this.valueArray[0] = newValue;
- }
- }
-
-
- /**
* {@inheritDoc}
*/
public V remove( V value )
@@ -271,7 +189,7 @@ public class InMemoryValueHolder<V> exte
{
try
{
- valueArray = ( V[] ) Array.newInstance( parentBtree.getValueSerializer().getType(), 1 );
+ valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), 1 );
valueArray[0] = valueBtree.browse().next().getKey();
valueBtree.close();
valueBtree = null;
@@ -296,7 +214,7 @@ public class InMemoryValueHolder<V> exte
private V removeFromArray( V value )
{
// First check that the value is not already present in the ValueHolder
- Comparator<V> comparator = parentBtree.getValueSerializer().getComparator();
+ Comparator<V> comparator = valueSerializer.getComparator();
int result = comparator.compare( valueArray[0], value );
@@ -335,7 +253,7 @@ public class InMemoryValueHolder<V> exte
}
else
{
- Comparator<V> comparator = parentBtree.getValueSerializer().getComparator();
+ Comparator<V> comparator = valueSerializer.getComparator();
int result = comparator.compare( checkedValue, valueArray[0] );
@@ -351,7 +269,7 @@ public class InMemoryValueHolder<V> exte
{
StringBuilder sb = new StringBuilder();
- sb.append( "ValueHolder[" ).append( parentBtree.getValueSerializer().getClass().getSimpleName() );
+ sb.append( "ValueHolder[" ).append( valueSerializer.getClass().getSimpleName() );
if ( valueBtree != null )
{
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/persisted/PersistedValueHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/persisted/PersistedValueHolder.java?rev=1550730&r1=1550729&r2=1550730&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/persisted/PersistedValueHolder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/persisted/PersistedValueHolder.java Fri Dec 13 14:01:33 2013
@@ -29,12 +29,9 @@ import org.apache.directory.mavibot.btre
import org.apache.directory.mavibot.btree.BTree;
import org.apache.directory.mavibot.btree.Tuple;
import org.apache.directory.mavibot.btree.TupleCursor;
-import org.apache.directory.mavibot.btree.ValueArrayCursor;
-import org.apache.directory.mavibot.btree.ValueBTreeCursor;
import org.apache.directory.mavibot.btree.ValueCursor;
import org.apache.directory.mavibot.btree.ValueHolder;
import org.apache.directory.mavibot.btree.exception.BTreeAlreadyManagedException;
-import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
import org.apache.directory.mavibot.btree.serializer.IntSerializer;
import org.apache.directory.mavibot.btree.serializer.LongSerializer;
@@ -47,6 +44,9 @@ import org.apache.directory.mavibot.btre
*/
public class PersistedValueHolder<V> extends AbstractValueHolder<V>
{
+ /** The parent BTree */
+ protected PersistedBTree<V, V> parentBtree;
+
/** The serialized value */
private byte[] raw;
@@ -56,9 +56,6 @@ public class PersistedValueHolder<V> ext
/** A flag to signal that the raw value represent the serialized values in their last state */
private boolean isRawUpToDate = false;
- /** The Value serializer */
- private ElementSerializer<V> valueSerializer;
-
/**
* Creates a new instance of a ValueHolder, containing the serialized values.
@@ -70,10 +67,12 @@ public class PersistedValueHolder<V> ext
*/
PersistedValueHolder( BTree<?, V> parentBtree, int nbValues, byte[] raw )
{
- this.parentBtree = parentBtree;
+ this.parentBtree = (PersistedBTree<V, V>)parentBtree;
this.valueSerializer = parentBtree.getValueSerializer();
this.raw = raw;
isRawUpToDate = true;
+ valueThresholdUp = PersistedBTree.valueThresholdUp;
+ valueThresholdLow = PersistedBTree.valueThresholdLow;
// We create the array of values if they fit in an array. If they are stored in a
// BTree, we do nothing atm.
@@ -94,8 +93,10 @@ public class PersistedValueHolder<V> ext
*/
PersistedValueHolder( BTree<?, V> parentBtree, V... values )
{
- this.parentBtree = parentBtree;
+ this.parentBtree = (PersistedBTree<V, V>)parentBtree;
this.valueSerializer = parentBtree.getValueSerializer();
+ valueThresholdUp = PersistedBTree.valueThresholdUp;
+ valueThresholdLow = PersistedBTree.valueThresholdLow;
if ( values != null )
{
@@ -150,21 +151,10 @@ public class PersistedValueHolder<V> ext
*/
public ValueCursor<V> getCursor()
{
- ValueCursor<V> cursor;
-
// Check that the values are deserialized before doing anything
checkAndDeserialize();
- if ( valueArray == null )
- {
- cursor = new ValueBTreeCursor<V>( valueBtree );
- }
- else
- {
- cursor = new ValueArrayCursor<V>( valueArray );
- }
-
- return cursor;
+ return super.getCursor();
}
@@ -252,7 +242,7 @@ public class PersistedValueHolder<V> ext
/**
* Create a new Sub-BTree to store the values.
*/
- private void createSubTree()
+ protected void createSubTree()
{
try
{
@@ -268,7 +258,7 @@ public class PersistedValueHolder<V> ext
try
{
- ((PersistedBTree<V, V>)parentBtree).getRecordManager().manage( valueBtree, RecordManager.INTERNAL_BTREE );
+ parentBtree.getRecordManager().manage( valueBtree, RecordManager.INTERNAL_BTREE );
raw = null;
}
catch ( BTreeAlreadyManagedException e )
@@ -319,101 +309,17 @@ public class PersistedValueHolder<V> ext
isDeserialized = true;
}
}
-
- /**
- * Add the value in an array
- */
- private void addInArray( V value )
- {
- checkAndDeserialize();
-
- // We have to check that we have reached the threshold or not
- if ( valueArray.length >= PersistedBTree.valueThresholdUp )
- {
- // Ok, transform the array into a btree
- createSubTree();
-
- try
- {
- for ( V val : valueArray )
- {
- // Here, we should insert all the values in one shot then
- // write the btree on disk only once.
- valueBtree.insert( val, null );
- }
-
- // We can delete the array now
- valueArray = null;
-
- // And inject the new value
- valueBtree.insert( value, null );
- }
- catch ( IOException e )
- {
- // TODO Auto-generated catch block
- e.printStackTrace();
- }
- }
- else
- {
- // First check that the value is not already present in the ValueHolder
- int pos = findPos( value );
-
- if ( pos >= 0 )
- {
- // The value exists : nothing to do
- return;
- }
-
- // Ok, we just have to insert the new element at the right position
- // We transform the position to a positive value
- pos = -( pos + 1 );
- // First, copy the array
- V[] newValueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), valueArray.length + 1 );
- System.arraycopy( valueArray, 0, newValueArray, 0, pos );
- newValueArray[pos] = value;
- System.arraycopy( valueArray, pos, newValueArray, pos + 1, valueArray.length - pos );
-
- // And switch the arrays
- valueArray = newValueArray;
- }
- }
-
/**
- * Add the value in the subBTree
+ * {@inheritDoc}
*/
- private void addInBtree( V value )
+ public void add( V value )
{
// First check that we have a loaded BTree
checkAndDeserialize();
-
- try
- {
- valueBtree.insert( value, null );
- }
- catch ( IOException e )
- {
- // TODO Auto-generated catch block
- e.printStackTrace();
- }
- }
-
- /**
- * {@inheritDoc}
- */
- public void add( V value )
- {
- if ( valueArray != null )
- {
- addInArray( value );
- }
- else
- {
- addInBtree( value );
- }
+ super.add( value );
// The raw value is not anymore up to date with the content
isRawUpToDate = false;
@@ -550,57 +456,14 @@ public class PersistedValueHolder<V> ext
/**
- * Check if the array of values contains a given value
- */
- private boolean arrayContains( V value )
- {
- // First, deserialize the value if it's still a byte[]
- checkAndDeserialize();
-
- if ( valueArray.length == 0 )
- {
- return false;
- }
-
- // Do a search using dichotomy
- return findPos( value ) >= 0;
- }
-
-
- /**
- * Check if the subBtree contains a given value
+ * {@inheritDoc}
*/
- private boolean btreeContains( V value )
+ public boolean contains( V checkedValue )
{
// First, deserialize the value if it's still a byte[]
checkAndDeserialize();
- try
- {
- return valueBtree.hasKey( value );
- }
- catch ( IOException e )
- {
- // TODO Auto-generated catch block
- e.printStackTrace();
- return false;
- }
- }
-
-
- /**
- * {@inheritDoc}
- */
- public boolean contains( V checkedValue )
- {
- if ( valueArray == null )
- {
- return btreeContains( checkedValue );
- }
- else
- {
- return arrayContains( checkedValue );
- }
+ return super.contains( checkedValue );
}
@@ -796,7 +659,7 @@ public class PersistedValueHolder<V> ext
long offset = LongSerializer.deserialize( raw );
// and reload the sub btree
- valueBtree = ((PersistedBTree<V, V>)parentBtree).getRecordManager().loadDupsBTree( offset );
+ valueBtree = parentBtree.getRecordManager().loadDupsBTree( offset );
}
Modified: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/persisted/RecordManagerWithDuplicatesTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/persisted/RecordManagerWithDuplicatesTest.java?rev=1550730&r1=1550729&r2=1550730&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/persisted/RecordManagerWithDuplicatesTest.java (original)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/persisted/RecordManagerWithDuplicatesTest.java Fri Dec 13 14:01:33 2013
@@ -166,6 +166,7 @@ public class RecordManagerWithDuplicates
btree.insert( i, v2 );
}
+ // Check that the elements are present
for ( long i = 1; i < 128; i++ )
{
String v1 = "V" + i;