Author: elecharny
Date: Wed Nov 27 07:03:46 2013
New Revision: 1545944
URL: http://svn.apache.org/r1545944
Log:
o Huge refactoring in the way we hold ValueHolder
o The TupleCursor interface have renamed methods and added ones
o Many fixes in the serialization/deserialition
o SpeedUp in managed BTrees
Modified:
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/KeyHolder.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/RecordManager.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/TupleCursorImpl.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ValueHolder.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTree.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InternalUtil.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Leaf.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Page.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/TupleCursorImpl.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/managed/ManagedBTreeBrowseTest.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/managed/RecordManagerTest.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeDuplicateKeyTest.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/InMemoryBTreeTest.java
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.java Wed Nov 27 07:03:46 2013
@@ -37,6 +37,10 @@ import org.apache.directory.mavibot.btre
*/
public interface Cursor<K>
{
+ /** Static value for the beforeFrst and afterLast positions */
+ static final int BEFORE_FIRST = -1;
+ static final int AFTER_LAST = -2;
+
/**
* Tells if the cursor can return a next element
* @return true if there are some more elements
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java Wed Nov 27 07:03:46 2013
@@ -39,6 +39,15 @@ import org.apache.directory.mavibot.btre
public interface TupleCursor<K, V> extends Cursor<K>
{
/**
+ * Tells if the cursor can return a next element
+ *
+ * @return true if there are some more elements
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ public boolean hasNext() throws EndOfFileExceededException, IOException;
+
+ /**
* Find the next key/value
*
* @return A Tuple containing the found key and value
@@ -49,6 +58,16 @@ public interface TupleCursor<K, V> exten
/**
+ * Tells if the cursor can return a previous element
+ *
+ * @return true if there are some more elements
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ public boolean hasPrev() throws EndOfFileExceededException, IOException;
+
+
+ /**
* Find the previous key/value
*
* @return A Tuple containing the found key and value
@@ -71,40 +90,75 @@ public interface TupleCursor<K, V> exten
/**
- * Moves the cursor to the next non-duplicate key.
-
- * If the BTree contains
+ * Tells if the cursor can return a next key
+ *
+ * @return true if there are some more keys
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ public boolean hasNextKey() throws EndOfFileExceededException, IOException;
+
+
+ /**
+ * Get the next non-duplicate key.
+ * If the BTree contains :
*
* <ul>
* <li><1,0></li>
* <li><1,1></li>
+ * <li><1,2></li>
* <li><2,0></li>
* <li><2,1></li>
* </ul>
*
- * and cursor is present at <1,0> then the cursor will move to <2,0>
+ * and cursor is present at <1,1> then the returned tuple will be <2,0> (not <1,2>)
*
+ * @return A Tuple containing the found key and value
* @throws EndOfFileExceededException
* @throws IOException
*/
- void moveToNextNonDuplicateKey() throws EndOfFileExceededException, IOException;
+ Tuple<K, V> nextKey() throws EndOfFileExceededException, IOException;
/**
- * Moves the cursor to the previous non-duplicate key
- * If the BTree contains
+ * Tells if the cursor can return a previous key
+ *
+ * @return true if there are some more keys
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ public boolean hasPrevKey() throws EndOfFileExceededException, IOException;
+
+
+ /**
+ * Get the previous non-duplicate key.
+ * If the BTree contains :
*
* <ul>
* <li><1,0></li>
* <li><1,1></li>
+ * <li><1,2></li>
* <li><2,0></li>
* <li><2,1></li>
* </ul>
*
- * and cursor is present at <2,1> then the cursor will move to <1,1>
- *
+ * and cursor is present at <2,1> then the returned tuple will be <1,0> (not <2,0>)
+ *
+ * @return A Tuple containing the found key and value
* @throws EndOfFileExceededException
* @throws IOException
*/
- void moveToPrevNonDuplicateKey() throws EndOfFileExceededException, IOException;
+ Tuple<K, V> prevKey() throws EndOfFileExceededException, IOException;
+
+
+ /**
+ * Change the position in the current cursor tbefore the first key
+ */
+ void beforeFirst() throws IOException;
+
+
+ /**
+ * Change the position in the current cursor to set it after the last key
+ */
+ void afterLast() throws IOException;
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java Wed Nov 27 07:03:46 2013
@@ -1028,7 +1028,7 @@ public class BTree<K, V> implements Clos
// remain in memory.
ElementHolder<Page<K, V>, K, V> holder = recordManager.writePage( this, modifiedPage,
revision );
-
+
// The root has just been modified, we haven't split it
// Get it and make it the current root page
rootPage = modifiedPage;
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java Wed Nov 27 07:03:46 2013
@@ -32,32 +32,6 @@ import java.io.IOException;
@SuppressWarnings("all")
/* No qualifier */class InternalUtil
{
-
-
- /**
- * Sets the multi-value container(a.k.a dupsContainer) of the key at the given position
- * and resets the 'dupsPos' to zero. This is mostly used by Cursor while navigating using
- * next()
- *
- * @param parentPos the parent position object
- * @param btree the BTree
- */
- public static void changeNextDupsContainer( ParentPos parentPos, BTree btree ) throws IOException
- {
- if ( !btree.isAllowDuplicates() )
- {
- return;
- }
-
- if ( parentPos.pos < parentPos.page.getNbElems() )
- {
- Leaf leaf = ( Leaf ) ( parentPos.page );
- ValueHolder valueHolder = leaf.values[parentPos.pos];
- parentPos.valueCursor = valueHolder.getCursor();
- }
- }
-
-
/**
* Sets the multi-value container(a.k.a dupsContainer) of the key at the index below the given position( i.e pos - 1)
* and resets the 'dupsPos' to the number of elements present in the multi-value container.
@@ -73,12 +47,10 @@ import java.io.IOException;
return;
}
- int index = parentPos.pos - 1;
-
- if ( index >= 0 )
+ if ( parentPos.pos >= 0 )
{
Leaf leaf = ( Leaf ) ( parentPos.page );
- ValueHolder valueHolder = leaf.values[index];
+ ValueHolder valueHolder = leaf.values[parentPos.pos];
parentPos.valueCursor = valueHolder.getCursor();
}
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/KeyHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/KeyHolder.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/KeyHolder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/KeyHolder.java Wed Nov 27 07:03:46 2013
@@ -104,7 +104,7 @@ public class KeyHolder<K>
/**
* @return The internal serialized byte[]
*/
- /* No qualifier */byte[] getBuffer()
+ /* No qualifier */byte[] getRaw()
{
return raw;
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/RecordManager.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/RecordManager.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/RecordManager.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/RecordManager.java Wed Nov 27 07:03:46 2013
@@ -594,12 +594,12 @@ public class RecordManager
if ( nbElems >= 0 )
{
// It's a leaf
- page = readLeaf( btree, nbElems, revision, byteBuffer, pageIos );
+ page = readLeafKeysAndValues( btree, nbElems, revision, byteBuffer, pageIos );
}
else
{
// It's a node
- page = readNode( btree, -nbElems, revision, byteBuffer, pageIos );
+ page = readNodeKeysAndValues( btree, -nbElems, revision, byteBuffer, pageIos );
}
return page;
@@ -609,7 +609,7 @@ public class RecordManager
/**
* Deserialize a Leaf from some PageIOs
*/
- private <K, V> Leaf<K, V> readLeaf( BTree<K, V> btree, int nbElems, long revision, ByteBuffer byteBuffer,
+ private <K, V> Leaf<K, V> readLeafKeysAndValues( BTree<K, V> btree, int nbElems, long revision, ByteBuffer byteBuffer,
PageIO[] pageIos )
{
// Its a leaf, create it
@@ -632,40 +632,12 @@ public class RecordManager
if ( nbValues < 0 )
{
// This is a sub-btree
- long btreeOffset = byteBuffer.getLong();
-
- // Load the BTree now.
- try
- {
- PageIO[] rootPageIos = readPageIOs( btreeOffset, Long.MAX_VALUE );
-
- BTree<V, V> subBtree = BTreeFactory.createBTree();
- subBtree.setBtreeOffset( btreeOffset );
-
- try
- {
- loadBTree( rootPageIos, subBtree );
- }
- catch ( Exception e )
- {
- // should not happen
- throw new RuntimeException( e );
- }
-
- valueHolder = new ValueHolder<V>( btree, btree.getValueSerializer(), subBtree );
-
- valueHolder.setSubBtree( subBtree );
- }
- catch ( EndOfFileExceededException e1 )
- {
- // TODO Auto-generated catch block
- e1.printStackTrace();
- }
- catch ( IOException e1 )
- {
- // TODO Auto-generated catch block
- e1.printStackTrace();
- }
+ byte[] btreeOffsetBytes = new byte[LONG_SIZE];
+ byteBuffer.get( btreeOffsetBytes );
+
+ // Create the valueHolder. As the number of values is negative, we have to switch
+ // to a positive value but as we start at -1 for 0 value, add 1.
+ valueHolder = new ValueHolder<V>( btree, btree.getValueSerializer(), 1 - nbValues, btreeOffsetBytes );
}
else
{
@@ -674,10 +646,9 @@ public class RecordManager
valueLengths[i] = byteBuffer.getInt();
// This is an Array of values, read the byte[] associated with it
- byte[] valueBytes = new byte[valueLengths[i]];
- byteBuffer.get( valueBytes );
- valueHolder = new ValueHolder<V>( btree, btree.getValueSerializer(), false, nbValues,
- valueBytes );
+ byte[] arrayBytes = new byte[valueLengths[i]];
+ byteBuffer.get( arrayBytes );
+ valueHolder = new ValueHolder<V>( btree, btree.getValueSerializer(), nbValues, arrayBytes );
}
BTreeFactory.setValue( leaf, i, valueHolder );
@@ -695,7 +666,7 @@ public class RecordManager
/**
* Deserialize a Node from some PageIos
*/
- private <K, V> Node<K, V> readNode( BTree<K, V> btree, int nbElems, long revision, ByteBuffer byteBuffer,
+ private <K, V> Node<K, V> readNodeKeysAndValues( BTree<K, V> btree, int nbElems, long revision, ByteBuffer byteBuffer,
PageIO[] pageIos ) throws IOException
{
Node<K, V> node = BTreeFactory.createNode( btree, revision, nbElems );
@@ -1256,7 +1227,7 @@ public class RecordManager
private <K, V> int serializeNodeKey( Node<K, V> node, int pos, List<byte[]> serializedData )
{
KeyHolder<K> holder = node.getKeyHolder( pos );
- byte[] buffer = holder.getBuffer();
+ byte[] buffer = holder.getRaw();
// We have to store the serialized key length
byte[] length = IntSerializer.serialize( buffer.length );
@@ -1265,7 +1236,7 @@ public class RecordManager
// And store the serialized key now
serializedData.add( buffer );
- return buffer.length + 4;
+ return buffer.length + INT_SIZE;
}
@@ -1299,7 +1270,7 @@ public class RecordManager
{
int dataSize = 0;
KeyHolder<K> keyHolder = leaf.getKeyHolder( pos );
- byte[] keyData = keyHolder.getBuffer();
+ byte[] keyData = keyHolder.getRaw();
if ( keyData != null )
{
@@ -1309,12 +1280,12 @@ public class RecordManager
// And the key data
serializedData.add( keyData );
- dataSize += keyData.length + 4;
+ dataSize += keyData.length + INT_SIZE;
}
else
{
serializedData.add( IntSerializer.serialize( 0 ) );
- dataSize += 4;
+ dataSize += INT_SIZE;
}
return dataSize;
@@ -1330,50 +1301,75 @@ public class RecordManager
// The value can be an Array or a sub-btree, but we don't care
// we just iterate on all the values
ValueHolder<V> valueHolder = leaf.getValue( pos );
-
- // First take the number of values
- int nbValues = valueHolder.size();
int dataSize = 0;
- if ( nbValues == 0 )
+ if ( !valueHolder.isSubBtree() )
{
- // No value.
+ int nbValues = valueHolder.size();
+
+ // Write the nb elements first
byte[] buffer = IntSerializer.serialize( nbValues );
serializedData.add( buffer );
+ dataSize = INT_SIZE;
- return buffer.length;
- }
-
- if ( valueHolder.isSubBtree() )
- {
- byte[] buffer = IntSerializer.serialize( -nbValues );
+ // We have a serialized value. Just flush it
+ byte[] data = valueHolder.getRaw();
+ dataSize += data.length;
+
+ // Store the data size
+ buffer = IntSerializer.serialize( data.length );
serializedData.add( buffer );
- dataSize += buffer.length;
+ dataSize += INT_SIZE;
- // the BTree offset
- buffer = LongSerializer.serialize( valueHolder.getOffset() );
- serializedData.add( buffer );
- dataSize += buffer.length;
+ // and add the data
+ serializedData.add( data );
}
else
{
- // This is an array, store the nb of values as a positive number
- byte[] buffer = IntSerializer.serialize( nbValues );
- serializedData.add( buffer );
- dataSize += buffer.length;
-
- // Now store each value
- byte[] data = valueHolder.getRaw();
- buffer = IntSerializer.serialize( data.length );
- serializedData.add( buffer );
- dataSize += buffer.length;
-
- if ( data.length > 0 )
+ // First take the number of values
+ int nbValues = valueHolder.size();
+
+ if ( nbValues == 0 )
+ {
+ // No value.
+ byte[] buffer = IntSerializer.serialize( nbValues );
+ serializedData.add( buffer );
+
+ return buffer.length;
+ }
+
+ if ( valueHolder.isSubBtree() )
+ {
+ // Store the nbVlues as a negative number. We add 1 so that 0 is not confused with an Array value
+ byte[] buffer = IntSerializer.serialize( -( nbValues + 1 ) );
+ serializedData.add( buffer );
+ dataSize += buffer.length;
+
+ // the BTree offset
+ buffer = LongSerializer.serialize( valueHolder.getOffset() );
+ serializedData.add( buffer );
+ dataSize += buffer.length;
+ }
+ else
{
- serializedData.add( data );
+ // This is an array, store the nb of values as a positive number
+ byte[] buffer = IntSerializer.serialize( nbValues );
+ serializedData.add( buffer );
+ dataSize += buffer.length;
+
+ // Now store each value
+ byte[] data = valueHolder.getRaw();
+ buffer = IntSerializer.serialize( data.length );
+ serializedData.add( buffer );
+ dataSize += buffer.length;
+
+ if ( data.length > 0 )
+ {
+ serializedData.add( data );
+ }
+
+ dataSize += data.length;
}
-
- dataSize += data.length;
}
return dataSize;
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/TupleCursorImpl.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/TupleCursorImpl.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/TupleCursorImpl.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/TupleCursorImpl.java Wed Nov 27 07:03:46 2013
@@ -20,15 +20,11 @@
package org.apache.directory.mavibot.btree.managed;
-import static org.apache.directory.mavibot.btree.managed.InternalUtil.changeNextDupsContainer;
-import static org.apache.directory.mavibot.btree.managed.InternalUtil.changePrevDupsContainer;
-
import java.io.IOException;
import java.util.NoSuchElementException;
import org.apache.directory.mavibot.btree.Tuple;
import org.apache.directory.mavibot.btree.TupleCursor;
-import org.apache.directory.mavibot.btree.ValueCursor;
import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
@@ -96,7 +92,7 @@ public class TupleCursorImpl<K, V> imple
ParentPos<K, V> parentPos = stack[depth];
- if ( parentPos.page == null )
+ if ( ( parentPos.page == null ) || ( parentPos.pos == AFTER_LAST ) )
{
// This is the end : no more value
throw new NoSuchElementException( "No more tuples present" );
@@ -121,6 +117,12 @@ public class TupleCursorImpl<K, V> imple
if ( parentPos.valueCursor.hasNext() )
{
+ // Deal with the BeforeFirst case
+ if ( parentPos.pos == BEFORE_FIRST )
+ {
+ parentPos.pos++;
+ }
+
value = parentPos.valueCursor.next();
}
else
@@ -217,7 +219,7 @@ public class TupleCursorImpl<K, V> imple
return parentPos;
}
}
-
+
return null;
}
@@ -301,7 +303,7 @@ public class TupleCursorImpl<K, V> imple
ParentPos<K, V> parentPos = stack[depth];
- if ( parentPos.page == null )
+ if ( ( parentPos.page == null ) || ( parentPos.pos == BEFORE_FIRST ) )
{
// This is the end : no more value
throw new NoSuchElementException( "No more tuples present" );
@@ -326,6 +328,12 @@ public class TupleCursorImpl<K, V> imple
if ( parentPos.valueCursor.hasPrev() )
{
+ // Deal with the AfterLast case
+ if ( parentPos.pos == AFTER_LAST )
+ {
+ parentPos.pos = parentPos.page.getNbElems() - 1;
+ }
+
value = parentPos.valueCursor.prev();
}
else
@@ -370,11 +378,7 @@ public class TupleCursorImpl<K, V> imple
/**
- * Tells if the cursor can return a next tupe.
- *
- * @return true if there are some more elements
- * @throws IOException
- * @throws EndOfFileExceededException
+ * {@inheritDoc}
*/
public boolean hasNext() throws EndOfFileExceededException, IOException
{
@@ -393,6 +397,11 @@ public class TupleCursorImpl<K, V> imple
return false;
}
+ if ( parentPos.pos == AFTER_LAST )
+ {
+ return false;
+ }
+
if ( parentPos.pos < parentPos.page.getNbElems() - 1 )
{
// Not the last position, we have a next value
@@ -432,10 +441,7 @@ public class TupleCursorImpl<K, V> imple
/**
- * Tells if the cursor can return a previous element
- * @return true if there are some more elements
- * @throws IOException
- * @throws EndOfFileExceededException
+ * {@inheritDoc}
*/
public boolean hasPrev() throws EndOfFileExceededException, IOException
{
@@ -461,6 +467,12 @@ public class TupleCursorImpl<K, V> imple
}
else
{
+ // Check that we are not before the first value
+ if ( parentPos.pos == BEFORE_FIRST )
+ {
+ return false;
+ }
+
// Check if we have some more value
if ( parentPos.valueCursor.hasPrev() )
{
@@ -519,87 +531,158 @@ public class TupleCursorImpl<K, V> imple
/**
- * Moves the cursor to the next non-duplicate key.
+ * {@inheritDoc}
+ */
+ public boolean hasNextKey() throws EndOfFileExceededException, IOException
+ {
+ // First check that we have elements in the BTree
+ if ( ( stack == null ) || ( stack.length == 0 ) )
+ {
+ // This is the end : no more key
+ return false;
+ }
- * If the BTree contains
- *
- * <ul>
- * <li><1,0></li>
- * <li><1,1></li>
- * <li><2,0></li>
- * <li><2,1></li>
- * </ul>
- *
- * and cursor is present at <1,0> then the cursor will move to <2,0>
- *
- * @throws EndOfFileExceededException
- * @throws IOException
+ ParentPos<K, V> parentPos = stack[depth];
+
+ if ( parentPos.page == null )
+ {
+ // This is the end : no more key
+ return false;
+ }
+
+ if ( parentPos.pos == ( parentPos.page.getNbElems() - 1 ) )
+ {
+ // End of the leaf. We have to go back into the stack up to the
+ // parent, and down to the next leaf
+ parentPos = findNextParentPos();
+
+ // we also need to check the result of the call to
+ // findNextParentPos as it will return a null ParentPos
+ if ( ( parentPos == null ) || ( parentPos.page == null ) )
+ {
+ // This is the end : no more key
+ return false;
+ }
+ else
+ {
+ // We have more keys
+ return true;
+ }
+ }
+ else
+ {
+ return true;
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
*/
- public void moveToNextNonDuplicateKey() throws EndOfFileExceededException, IOException
+ public Tuple<K, V> nextKey() throws EndOfFileExceededException, IOException
{
// First check that we have elements in the BTree
if ( ( stack == null ) || ( stack.length == 0 ) )
{
- return;
+ // This is the end : no more value
+ throw new NoSuchElementException( "No more tuples present" );
}
ParentPos<K, V> parentPos = stack[depth];
if ( parentPos.page == null )
{
- return;
+ // This is the end : no more value
+ throw new NoSuchElementException( "No more tuples present" );
}
if ( parentPos.pos == ( parentPos.page.getNbElems() - 1 ) )
{
// End of the leaf. We have to go back into the stack up to the
- // parent, and down to the leaf
- // increment the position cause findNextParentPos checks "parentPos.pos == parentPos.page.getNbElems()"
+ // parent, and down to the next leaf
+ parentPos = findNextParentPos();
+
+ // we also need to check the result of the call to
+ // findNextParentPos as it will return a null ParentPos
+ if ( ( parentPos == null ) || ( parentPos.page == null ) )
+ {
+ // This is the end : no more value
+ throw new NoSuchElementException( "No more tuples present" );
+ }
+ }
+ else
+ {
+ // Get the next key
parentPos.pos++;
- ParentPos<K, V> nextPos = findNextParentPos();
+ }
+
+ // The key
+ Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
+ tuple.setKey( leaf.keys[parentPos.pos].getKey() );
+
+ // The value
+ ValueHolder<V> valueHolder = leaf.values[parentPos.pos];
+ parentPos.valueCursor = valueHolder.getCursor();
+ V value = parentPos.valueCursor.next();
+ tuple.setValue( value );
+
+ return tuple;
+ }
+
- // if the returned value is a Node OR if it is same as the parentPos
- // that means cursor is already at the last position
- // call afterLast() to restore the stack with the path to the right most element
- if ( ( nextPos.page instanceof Node ) || ( nextPos == parentPos ) )
+ /**
+ * {@inheritDoc}
+ */
+ public boolean hasPrevKey() throws EndOfFileExceededException, IOException
+ {
+ // First check that we have elements in the BTree
+ if ( ( stack == null ) || ( stack.length == 0 ) )
+ {
+ // This is the end : no more key
+ return false;
+ }
+
+ ParentPos<K, V> parentPos = stack[depth];
+
+ if ( parentPos.page == null )
+ {
+ // This is the end : no more key
+ return false;
+ }
+
+ if ( parentPos.pos == 0 )
+ {
+ // Beginning of the leaf. We have to go back into the stack up to the
+ // parent, and down to the leaf
+ parentPos = findPrevParentPos();
+
+ if ( ( parentPos == null ) || ( parentPos.page == null ) )
{
- afterLast();
+ // This is the end : no more key
+ return false;
}
else
{
- parentPos = nextPos;
+ return true;
}
}
else
{
- parentPos.pos++;
- changeNextDupsContainer( parentPos, btree );
+ return true;
}
}
/**
- * Moves the cursor to the previous non-duplicate key
- * If the BTree contains
- *
- * <ul>
- * <li><1,0></li>
- * <li><1,1></li>
- * <li><2,0></li>
- * <li><2,1></li>
- * </ul>
- *
- * and cursor is present at <2,1> then the cursor will move to <1,1>
- *
- * @throws EndOfFileExceededException
- * @throws IOException
+ * {@inheritDoc}
*/
- public void moveToPrevNonDuplicateKey() throws EndOfFileExceededException, IOException
+ public Tuple<K, V> prevKey() throws EndOfFileExceededException, IOException
{
// First check that we have elements in the BTree
if ( ( stack == null ) || ( stack.length == 0 ) )
{
- return;
+ // This is the end : no more value
+ throw new NoSuchElementException( "No more tuples present" );
}
ParentPos<K, V> parentPos = stack[depth];
@@ -607,38 +690,51 @@ public class TupleCursorImpl<K, V> imple
if ( parentPos.page == null )
{
// This is the end : no more value
- return;
+ throw new NoSuchElementException( "No more tuples present" );
}
if ( parentPos.pos == 0 )
{
- // End of the leaf. We have to go back into the stack up to the
+ // Beginning of the leaf. We have to go back into the stack up to the
// parent, and down to the leaf
parentPos = findPrevParentPos();
- // if the returned value is a Node that means cursor is already at the first position
- // call beforeFirst() to restore the stack to the initial state
- if ( parentPos.page instanceof Node )
+ if ( ( parentPos == null ) || ( parentPos.page == null ) )
{
- beforeFirst();
+ // This is the end : no more value
+ throw new NoSuchElementException( "No more tuples present" );
}
}
else
{
- changePrevDupsContainer( parentPos, btree );
- parentPos.pos--;
+ if ( parentPos.pos == AFTER_LAST )
+ {
+ parentPos.pos = parentPos.page.getNbElems() - 1;
+ }
+ else
+ {
+ parentPos.pos--;
+ }
}
+
+ // Update the Tuple
+ Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
+
+ // The key
+ tuple.setKey( leaf.keys[parentPos.pos].getKey() );
+
+ // The value
+ ValueHolder<V> valueHolder = leaf.values[parentPos.pos];
+ parentPos.valueCursor = valueHolder.getCursor();
+ V value = parentPos.valueCursor.next();
+ tuple.setValue( value );
+
+ return tuple;
}
/**
- * moves the cursor to the same position that was given at the time of instantiating the cursor.
- *
- * For example, if the cursor was created using browse() method, then beforeFirst() will
- * place the cursor before the 0th position.
- *
- * If the cursor was created using browseFrom(K), then calling beforeFirst() will reset the position
- * to the just before the position where K is present.
+ * {@inheritDoc}
*/
public void beforeFirst() throws IOException
{
@@ -649,34 +745,30 @@ public class TupleCursorImpl<K, V> imple
}
Page<K, V> child = null;
-
+
for ( int i = 0; i < depth; i++ )
{
ParentPos<K, V> parentPos = stack[i];
parentPos.pos = 0;
-
+
if ( child != null )
{
parentPos.page = child;
}
-
+
child = ((Node<K, V>)parentPos.page).children[0].getValue( btree );
}
-
+
// and leaf
ParentPos<K, V> parentPos = stack[depth];
- parentPos.pos = 0;
-
- if ( child == null )
- {
- child = parentPos.page;
- }
- else
+ parentPos.pos = BEFORE_FIRST;
+
+ if ( child != null )
{
parentPos.page = child;
}
- parentPos.valueCursor = ((Leaf<K, V>)parentPos.page).values[parentPos.pos].getCursor();
+ parentPos.valueCursor = ((Leaf<K, V>)parentPos.page).values[0].getCursor();
parentPos.valueCursor.beforeFirst();
}
@@ -707,6 +799,7 @@ public class TupleCursorImpl<K, V> imple
}
else
{
+ // We have N+1 children if the page is a Node, so we don't decrement the nbElems field
parentPos.pos = ((Node<K, V>)parentPos.page).nbElems;
}
@@ -718,7 +811,6 @@ public class TupleCursorImpl<K, V> imple
if ( child == null )
{
- child = parentPos.page;
parentPos.pos = ((Leaf<K, V>)parentPos.page).nbElems - 1;
}
else
@@ -729,5 +821,6 @@ public class TupleCursorImpl<K, V> imple
parentPos.valueCursor = ((Leaf<K, V>)parentPos.page).values[parentPos.pos].getCursor();
parentPos.valueCursor.afterLast();
+ parentPos.pos = AFTER_LAST;
}
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ValueHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ValueHolder.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ValueHolder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ValueHolder.java Wed Nov 27 07:03:46 2013
@@ -31,6 +31,7 @@ import org.apache.directory.mavibot.btre
import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
import org.apache.directory.mavibot.btree.serializer.IntSerializer;
+import org.apache.directory.mavibot.btree.serializer.LongSerializer;
/**
@@ -49,9 +50,12 @@ public class ValueHolder<V> implements C
/** The serialized value */
private byte[] raw;
-
- /** A flag set to true if the values are stored in a BTree */
- private boolean isSubBtree = false;
+
+ /** A flag set to true when the raw value has been deserialized */
+ private boolean isDeserialized = false;
+
+ /** A flag to signal that the raw value represent the serialized values in their last state */
+ private boolean isRawUpToDate = false;
/** The RecordManager */
private BTree<?, V> btree;
@@ -59,59 +63,36 @@ public class ValueHolder<V> implements C
/** The Value serializer */
private ElementSerializer<V> valueSerializer;
- /** An internal flag used when the values are not yet deserialized */
- private boolean isRaw = true;
-
/**
- * Creates a new instance of a ValueHolder, containing the serialized values
+ * Creates a new instance of a ValueHolder, containing the serialized values.
*
+ * @param btree the container BTree
* @param valueSerializer The Value's serializer
* @param raw The raw data containing the values
+ * @param nbValues the number of stored values
+ * @param raw the byte[] containing either the serialized array of values or the sub-btree offset
*/
- /* No qualifier */ValueHolder( BTree<?, V> btree, ElementSerializer<V> valueSerializer,
- boolean isSubBtree, int nbValues,
- byte[] raw )
+ /* No qualifier */ValueHolder( BTree<?, V> btree, ElementSerializer<V> valueSerializer, int nbValues, byte[] raw )
{
this.valueSerializer = valueSerializer;
this.raw = raw;
- this.isSubBtree = isSubBtree;
this.btree = btree;
+ isRawUpToDate = true;
+ // We create the array of values if they fit in an array. If they are stored in a
+ // BTree, we do nothing atm.
if ( nbValues < BTree.valueThresholdUp )
{
- // Keep an array
+ // The values are contained into an array
valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), nbValues );
}
- else
- {
- // Use a sub btree
-
- //raw = ByteBuffer.wrap( valueSerializer.serialize( key ) );
- }
- }
-
-
- /**
- * Creates a new instance of a ValueHolder, containing the serialized values
- *
- * @param valueSerializer The Value's serializer
- * @param raw The raw data containing the values
- */
- /* No qualifier */ValueHolder( BTree<?, V> btree, ElementSerializer<V> valueSerializer,
- BTree<V, V> subBtree )
- {
- this.valueSerializer = valueSerializer;
- this.btree = btree;
- raw = null;
- isRaw = false;
- isSubBtree = true;
- valueBtree = subBtree;
}
/**
- * Creates a new instance of a ValueHolder, containing Values
+ * Creates a new instance of a ValueHolder, containing Values. This constructor is called
+ * whe we need to create a new ValueHolder with deserialized values.
*
* @param valueSerializer The Value's serializer
* @param values The Values stored in the ValueHolder
@@ -139,28 +120,6 @@ public class ValueHolder<V> implements C
ase.printStackTrace();
throw ase;
}
-
- // Serialize the values
- byte[][] data = new byte[nbValues][];
- int pos = 0;
- int length = 0;
-
- for ( V value : values )
- {
- byte[] serializedValue = valueSerializer.serialize( value );
-
- data[pos++] = serializedValue;
- length += serializedValue.length;
- }
-
- raw = new byte[length];
- pos = 0;
-
- for ( byte[] bytes : data )
- {
- System.arraycopy( bytes, 0, raw, pos, bytes.length );
- pos += bytes.length;
- }
}
else
{
@@ -185,11 +144,9 @@ public class ValueHolder<V> implements C
{
// No value, we create an empty array
valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), 0 );
-
- //raw = ByteBuffer.wrap( valueSerializer.serialize( key ) );
}
-
- isRaw = false;
+
+ isDeserialized = true;
}
@@ -198,11 +155,12 @@ public class ValueHolder<V> implements C
*/
public ValueCursor<V> getCursor()
{
- checkRaw();
-
ValueCursor<V> cursor;
- if ( isSubBtree )
+ // Check that the values are deserialized before doing anything
+ checkAndDeserialize();
+
+ if ( valueArray == null )
{
cursor = new ValueBtreeCursor();
}
@@ -214,6 +172,7 @@ public class ValueHolder<V> implements C
return cursor;
}
+
/**
* A class that encapsulate the values into an array
*/
@@ -229,7 +188,7 @@ public class ValueHolder<V> implements C
private ValueArrayCursor()
{
// Start at -1 to be positioned before the first element
- currentPos = -1;
+ currentPos = BEFORE_FIRST;
}
@@ -239,15 +198,7 @@ public class ValueHolder<V> implements C
@Override
public boolean hasNext()
{
- if ( valueArray == null )
- {
- // Load the array from the raw data
- return false;
- }
- else
- {
- return currentPos < valueArray.length - 1;
- }
+ return ( currentPos < valueArray.length - 1 ) && ( currentPos != AFTER_LAST );
}
@@ -267,6 +218,8 @@ public class ValueHolder<V> implements C
if ( currentPos == valueArray.length )
{
+ currentPos = AFTER_LAST;
+
// We have reached the end of the array
return null;
}
@@ -284,15 +237,7 @@ public class ValueHolder<V> implements C
@Override
public boolean hasPrev() throws EndOfFileExceededException, IOException
{
- if ( valueArray == null )
- {
- // Load the array from the raw data
- return false;
- }
- else
- {
- return currentPos > 0;
- }
+ return currentPos > 0 || currentPos == AFTER_LAST;
}
@@ -311,7 +256,7 @@ public class ValueHolder<V> implements C
@Override
public void beforeFirst() throws IOException
{
- currentPos = -1;
+ currentPos = BEFORE_FIRST;
}
@@ -321,7 +266,7 @@ public class ValueHolder<V> implements C
@Override
public void afterLast() throws IOException
{
- currentPos = valueArray.length;
+ currentPos = AFTER_LAST;
}
@@ -338,9 +283,16 @@ public class ValueHolder<V> implements C
}
else
{
- currentPos--;
+ if ( currentPos == AFTER_LAST )
+ {
+ currentPos = valueArray.length - 1;
+ }
+ else
+ {
+ currentPos--;
+ }
- if ( currentPos == -1 )
+ if ( currentPos == BEFORE_FIRST )
{
// We have reached the end of the array
return null;
@@ -359,14 +311,7 @@ public class ValueHolder<V> implements C
@Override
public int size()
{
- if ( valueArray != null )
- {
- return valueArray.length;
- }
- else
- {
- return 0;
- }
+ return valueArray.length;
}
}
@@ -384,7 +329,7 @@ public class ValueHolder<V> implements C
*/
private ValueBtreeCursor()
{
- // Start at -1 to be positionned before the first element
+ // Start at -1 to be positioned before the first element
try
{
if ( valueBtree != null )
@@ -418,13 +363,11 @@ public class ValueHolder<V> implements C
}
catch ( EndOfFileExceededException e )
{
- // TODO Auto-generated catch block
e.printStackTrace();
return false;
}
catch ( IOException e )
{
- // TODO Auto-generated catch block
e.printStackTrace();
return false;
}
@@ -443,13 +386,11 @@ public class ValueHolder<V> implements C
}
catch ( EndOfFileExceededException e )
{
- // TODO Auto-generated catch block
e.printStackTrace();
return null;
}
catch ( IOException e )
{
- // TODO Auto-generated catch block
e.printStackTrace();
return null;
}
@@ -474,13 +415,11 @@ public class ValueHolder<V> implements C
}
catch ( EndOfFileExceededException e )
{
- // TODO Auto-generated catch block
e.printStackTrace();
return false;
}
catch ( IOException e )
{
- // TODO Auto-generated catch block
e.printStackTrace();
return false;
}
@@ -539,13 +478,11 @@ public class ValueHolder<V> implements C
}
catch ( EndOfFileExceededException e )
{
- // TODO Auto-generated catch block
e.printStackTrace();
return null;
}
catch ( IOException e )
{
- // TODO Auto-generated catch block
e.printStackTrace();
return null;
}
@@ -558,61 +495,71 @@ public class ValueHolder<V> implements C
@Override
public int size()
{
- if ( valueBtree != null )
- {
- return ( int ) valueBtree.getNbElems();
- }
- else
- {
- return 0;
- }
+ return ( int ) valueBtree.getNbElems();
}
}
/**
- * @return the raw representation of the value holder.
+ * @return the raw representation of the value holder. The serialized value will not be the same
+ * if the values are stored in an array or in a btree. <br/>
+ * If they are stored in a BTree, the raw value will contain the offset of the btree, otherwise
+ * it will contain a byte[] which will contain each serialized value, prefixed by their length.
+ *
*/
- public byte[] getRaw()
+ /* No qualifier*/ byte[] getRaw()
{
- if ( isRaw )
+ if ( isRawUpToDate )
{
- // We don't have to serialize the ValueHolder, it has not been changed
+ // Just have to return the raw value
return raw;
}
+
+ if ( isSubBtree() )
+ {
+ // The values are stored into a subBtree, return the offset of this subBtree
+ long btreeOffset = valueBtree.getBtreeOffset();
+ raw = LongSerializer.serialize( btreeOffset );
+ }
else
{
- // Ok, some values have been added/modified/removed, we have to serialize the ValueHolder
+ // Create as many byte[] as we have length and serialized values to store
byte[][] valueBytes = new byte[valueArray.length * 2][];
int length = 0;
int pos = 0;
-
+
+ // Process each value now
for ( V value : valueArray )
{
// Serialize the value
byte[] bytes = valueSerializer.serialize( value );
length += bytes.length;
-
+
// Serialize the value's length
byte[] sizeBytes = IntSerializer.serialize( bytes.length );
length += sizeBytes.length;
-
+
// And store the two byte[]
valueBytes[pos++] = sizeBytes;
valueBytes[pos++] = bytes;
}
-
+
+ // Last, not least, create a buffer large enough to contain all the created byte[],
+ // and copy all those byte[] into this buffer
raw = new byte[length];
pos = 0;
-
+
for ( byte[] bytes : valueBytes )
{
System.arraycopy( bytes, 0, raw, pos, bytes.length );
pos += bytes.length;
}
-
- return raw;
}
+
+ // Update the flags
+ isRawUpToDate = true;
+
+ return raw;
}
@@ -621,7 +568,7 @@ public class ValueHolder<V> implements C
*/
public boolean isSubBtree()
{
- return isSubBtree;
+ return valueArray == null;
}
@@ -630,7 +577,9 @@ public class ValueHolder<V> implements C
*/
public int size()
{
- if ( isSubBtree )
+ checkAndDeserialize();
+
+ if ( valueArray == null )
{
return ( int ) valueBtree.getNbElems();
}
@@ -661,8 +610,6 @@ public class ValueHolder<V> implements C
try
{
btree.getRecordManager().manage( valueBtree, true );
- isSubBtree = true;
- isRaw = false;
raw = null;
}
catch ( BTreeAlreadyManagedException e )
@@ -685,79 +632,61 @@ public class ValueHolder<V> implements C
{
valueBtree = subBtree;
raw = null;
- isRaw = false;
- isSubBtree = true;
valueArray = null;
+ isDeserialized = true;
+ isRawUpToDate = false;
}
-
-
+
+
/**
- * Add a new value in the ValueHolder
- *
- * @param value The added value
+ * Check that the values are stored as raw value
*/
- public void add( V value )
+ private void checkAndDeserialize()
{
- checkRaw();
-
- if ( !isSubBtree )
+ if ( !isDeserialized )
{
- // We have to check that we have reached the threshold or not
- if ( valueArray.length + 1 > BTree.valueThresholdUp )
+ if ( valueArray == null )
{
- // 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();
- }
+ // the values are stored into a sub-btree. Read it now if it's not already done
+ deserializeSubBtree();
}
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;
+ // The values are stored into an array. Deserialize it now
+ deserializeArray();
}
+
+ // Change the flag
+ isDeserialized = true;
}
- else
+ }
+
+ /**
+ * 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 + 1 > BTree.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 )
@@ -766,50 +695,49 @@ public class ValueHolder<V> implements C
e.printStackTrace();
}
}
- }
-
-
- /**
- * Add a new value in the ValueHolder
- *
- * @param value The added value
- */
- public void remove( V value )
- {
- checkRaw();
-
- if ( !isSubBtree )
+ else
{
// First check that the value is not already present in the ValueHolder
int pos = findPos( value );
- if ( pos < 0 )
+ if ( pos >= 0 )
{
- // The value does not exists : nothing to do
+ // The value exists : nothing to do
return;
}
- // Ok, we just have to delete the new element at the right position
+ // 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 );
+ V[] newValueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), valueArray.length + 1 );
System.arraycopy( valueArray, 0, newValueArray, 0, pos );
- System.arraycopy( valueArray, pos + 1, newValueArray, pos, valueArray.length - pos - 1 );
+ newValueArray[pos] = value;
+ System.arraycopy( valueArray, pos, newValueArray, pos + 1, valueArray.length - pos );
// And switch the arrays
valueArray = newValueArray;
}
- else
+ }
+
+
+ /**
+ * Add the value in the subBTree
+ */
+ private void addInBtree( V value )
+ {
+ // First check that we have a loaded BTree
+ checkAndDeserialize();
+
+ try
{
- try
- {
- valueBtree.delete( value );
- }
- catch ( IOException e )
- {
- // TODO Auto-generated catch block
- e.printStackTrace();
- }
+ valueBtree.insert( value, null );
+ }
+ catch ( IOException e )
+ {
+ // TODO Auto-generated catch block
+ e.printStackTrace();
}
}
@@ -819,15 +747,76 @@ public class ValueHolder<V> implements C
*
* @param value The added value
*/
- public boolean contains( V value )
+ public void add( V value )
+ {
+ if ( valueArray != null )
+ {
+ addInArray( value );
+ }
+ else
+ {
+ addInBtree( value );
+ }
+
+ // The raw value is not anymore up to date with the content
+ isRawUpToDate = false;
+ raw = null;
+ }
+
+
+ /**
+ * Remove a value from an array
+ */
+ private void removeFromArray( V value )
+ {
+ checkAndDeserialize();
+
+ // First check that the value is not already present in the ValueHolder
+ int pos = findPos( value );
+
+ if ( pos < 0 )
+ {
+ // The value does not exists : nothing to do
+ return;
+ }
+
+ // Ok, we just have to delete the new element at the right position
+ // First, copy the array
+ V[] newValueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), valueArray.length - 1 );
+
+ System.arraycopy( valueArray, 0, newValueArray, 0, pos );
+ System.arraycopy( valueArray, pos + 1, newValueArray, pos, valueArray.length - pos - 1 );
+
+ // And switch the arrays
+ valueArray = newValueArray;
+ }
+
+
+ /**
+ * Remove the value from a sub btree
+ */
+ private void removeFromBtree( V value )
{
- checkRaw();
+ // First check that we have a loaded BTree
+ checkAndDeserialize();
- if ( isSubBtree )
+ if ( btreeContains( value ) )
{
try
{
- return valueBtree.hasKey( value );
+ if ( valueBtree.getNbElems() - 1 < BTree.valueThresholdLow )
+ {
+ int nbValues = (int)(valueBtree.getNbElems() - 1);
+
+ // We have to switch to an Array of values
+ valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), nbValues );
+
+ // Now copy all the value sbut the one we have removed
+ }
+ else
+ {
+ valueBtree.delete( value );
+ }
}
catch ( IOException e )
{
@@ -835,18 +824,84 @@ public class ValueHolder<V> implements C
e.printStackTrace();
}
}
+ }
+
+ /**
+ * Add a new value in the ValueHolder
+ *
+ * @param value The added value
+ */
+ public void remove( V value )
+ {
+ if ( valueArray != null )
+ {
+ removeFromArray( value );
+ }
else
{
- if ( valueArray.length == 0 )
- {
- return false;
- }
+ removeFromBtree( value );
+ }
- // Do a search using dichotomy
- return findPos( value ) >= 0;
+ // The raw value is not anymore up to date wth the content
+ isRawUpToDate = false;
+ raw = null;
+ }
+
+
+ /**
+ * 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;
}
- return true;
+ // Do a search using dichotomy
+ return findPos( value ) >= 0;
+ }
+
+
+ /**
+ * Check if the subBtree contains a given value
+ */
+ private boolean btreeContains( V value )
+ {
+ // 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;
+ }
+ }
+
+
+ /**
+ * Add a new value in the ValueHolder
+ *
+ * @param value The added value
+ */
+ public boolean contains( V value )
+ {
+ if ( valueArray == null )
+ {
+ return btreeContains( value );
+ }
+ else
+ {
+ return arrayContains( value );
+ }
}
@@ -984,67 +1039,73 @@ public class ValueHolder<V> implements C
{
ValueHolder<V> copy = ( ValueHolder<V> ) super.clone();
- //copy the valueArray if it's not null
+ // copy the valueArray if it's not null
// We don't clone the BTree, as we will create new revisions when
- //modifying it
- if ( ( !isSubBtree ) && ( valueArray != null ) )
+ // modifying it
+ if ( valueArray != null )
{
copy.valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), valueArray.length );
System.arraycopy( valueArray, 0, copy.valueArray, 0, valueArray.length );
}
+
+ // Also clone the raw value if its up to date
+ if ( isRawUpToDate )
+ {
+ copy.raw = new byte[raw.length];
+ System.arraycopy( raw, 0, copy.raw, 0, raw.length );
+ }
return copy;
}
/**
- * Check if we haven't yet deserialized the values, and if so, do it
+ * Deserialize the values stored in an array
*/
- private void checkRaw()
+ private void deserializeArray()
{
- if ( isRaw )
+ // We haven't yet deserialized the values. Let's do it now. The values are
+ // necessarily stored in an array at this point
+ int index = 0;
+ int pos = 0;
+
+ while ( pos < raw.length )
{
- // We haven't yet deserialized the values. Let's do it now
- if ( isSubBtree )
+ try
{
- // This is a sub BTree, we have to read the tree from the offsets
+ int size = IntSerializer.deserialize( raw, pos );
+ pos += 4;
+ V value = valueSerializer.fromBytes( raw, pos );
+ pos += size;
+ valueArray[index++] = value;
}
- else
+ catch ( IOException e )
{
- // We have to deserialize the array of values
- int index = 0;
- int pos = 0;
-
- while ( pos < raw.length )
- {
- try
- {
- int size = IntSerializer.deserialize( raw, pos );
- pos += 4;
-
- V value = valueSerializer.fromBytes( raw, pos );
- pos += size;
- valueArray[index++] = value;
- }
- catch ( IOException e )
- {
- e.printStackTrace();
- }
- }
+ e.printStackTrace();
}
-
- isRaw = false;
}
}
/**
+ * Deserialize the values stored in a sub-btree
+ */
+ private void deserializeSubBtree()
+ {
+ // Get the sub-btree offset
+ long offset = LongSerializer.deserialize( raw );
+
+ // and reload the sub btree
+ valueBtree = btree.getRecordManager().loadDupsBTree( offset );
+ }
+
+ /**
* @return The sub-btree offset
*/
/* No qualifier */long getOffset()
{
- if ( isSubBtree )
+ if ( valueArray == null )
{
return valueBtree.getBtreeOffset();
}
@@ -1064,13 +1125,13 @@ public class ValueHolder<V> implements C
sb.append( "ValueHolder[" ).append( valueSerializer.getClass().getSimpleName() );
- if ( isRaw )
+ if ( !isDeserialized )
{
sb.append( ", isRaw[" ).append( raw.length ).append( "]" );
}
else
{
- if ( isSubBtree )
+ if ( valueArray == null )
{
sb.append( ", SubBTree" );
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTree.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTree.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTree.java Wed Nov 27 07:03:46 2013
@@ -31,7 +31,6 @@ import java.lang.reflect.Type;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
import java.util.Comparator;
-import java.util.LinkedList;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.locks.ReentrantLock;
@@ -934,9 +933,7 @@ public class BTree<K, V> implements Clos
Transaction<K, V> transaction = beginReadTransaction();
// Fetch the root page for this revision
- LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
-
- TupleCursor<K, V> cursor = rootPage.browse( transaction, stack );
+ TupleCursor<K, V> cursor = rootPage.browse( transaction, new ParentPos[32], 0 );
return cursor;
}
@@ -958,8 +955,7 @@ public class BTree<K, V> implements Clos
Page<K, V> revisionRootPage = getRootPage( revision );
// And get the cursor
- LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
- TupleCursor<K, V> cursor = revisionRootPage.browse( transaction, stack );
+ TupleCursor<K, V> cursor = revisionRootPage.browse( transaction, new ParentPos[32], 0 );
return cursor;
}
@@ -978,7 +974,7 @@ public class BTree<K, V> implements Clos
Transaction<K, V> transaction = beginReadTransaction();
// Fetch the root page for this revision
- TupleCursor<K, V> cursor = rootPage.browse( key, transaction, new LinkedList<ParentPos<K, V>>() );
+ TupleCursor<K, V> cursor = rootPage.browse( key, transaction, new ParentPos[32], 0 );
return cursor;
}
@@ -1002,8 +998,7 @@ public class BTree<K, V> implements Clos
Page<K, V> revisionRootPage = getRootPage( revision );
// And get the cursor
- LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
- TupleCursor<K, V> cursor = revisionRootPage.browse( key, transaction, stack );
+ TupleCursor<K, V> cursor = revisionRootPage.browse( key, transaction, new ParentPos[32], 0 );
return cursor;
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InternalUtil.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InternalUtil.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InternalUtil.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InternalUtil.java Wed Nov 27 07:03:46 2013
@@ -23,6 +23,8 @@ package org.apache.directory.mavibot.btr
import java.io.IOException;
+import org.apache.directory.mavibot.btree.TupleCursor;
+
/**
* A class containing utility methods to be used internally.
@@ -52,11 +54,22 @@ import java.io.IOException;
if ( parentPos.dupsContainer == null )
{
Leaf leaf = ( Leaf ) ( parentPos.page );
- MultipleMemoryHolder mvHolder = ( MultipleMemoryHolder ) leaf.values[parentPos.pos];
- if( !mvHolder.isSingleValue() )
+
+ // Deal with BEFORE_FIRST and AFTER_LAST cases
+ if ( ( parentPos.pos == TupleCursor.BEFORE_FIRST ) || ( parentPos.pos == TupleCursor.AFTER_LAST ) )
{
- BTree dupsContainer = ( BTree ) mvHolder.getValue( btree );
- parentPos.dupsContainer = dupsContainer;
+ // Nothing to do in this case
+ return;
+ }
+ else
+ {
+ MultipleMemoryHolder mvHolder = ( MultipleMemoryHolder ) leaf.values[parentPos.pos];
+
+ if ( !mvHolder.isSingleValue() )
+ {
+ BTree dupsContainer = ( BTree ) mvHolder.getValue( btree );
+ parentPos.dupsContainer = dupsContainer;
+ }
}
}
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Leaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Leaf.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Leaf.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Leaf.java Wed Nov 27 07:03:46 2013
@@ -24,7 +24,6 @@ import static org.apache.directory.mavib
import java.io.IOException;
import java.lang.reflect.Array;
-import java.util.LinkedList;
import org.apache.directory.mavibot.btree.Tuple;
import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
@@ -670,7 +669,7 @@ import org.apache.directory.mavibot.btre
/**
* {@inheritDoc}
*/
- public TupleCursorImpl<K, V> browse( K key, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+ public TupleCursorImpl<K, V> browse( K key, Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
{
int pos = findPos( key );
TupleCursorImpl<K, V> cursor = null;
@@ -682,9 +681,9 @@ import org.apache.directory.mavibot.btre
// The first element has been found. Create the cursor
ParentPos<K, V> parentPos = new ParentPos<K, V>( this, index );
setDupsContainer( parentPos, btree );
- stack.push( parentPos );
+ stack[depth] = parentPos;
- cursor = new TupleCursorImpl<K, V>( btree, transaction, stack );
+ cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
}
else
{
@@ -693,16 +692,17 @@ import org.apache.directory.mavibot.btre
{
ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
setDupsContainer( parentPos, btree );
- stack.push( parentPos );
+ stack[depth] = parentPos;
- cursor = new TupleCursorImpl<K, V>( btree, transaction, stack );
+ cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
}
else
{
// Not found : return a null cursor
- stack.push( new ParentPos<K, V>( null, -1 ) );
+ ParentPos<K, V> parentPos = new ParentPos<K, V>( null, -1 );
+ stack[depth] = parentPos;
- return new TupleCursorImpl<K, V>( btree, transaction, stack );
+ return new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
}
}
@@ -713,7 +713,7 @@ import org.apache.directory.mavibot.btre
/**
* {@inheritDoc}
*/
- public TupleCursorImpl<K, V> browse( Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+ public TupleCursorImpl<K, V> browse( Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
{
int pos = 0;
TupleCursorImpl<K, V> cursor = null;
@@ -721,9 +721,9 @@ import org.apache.directory.mavibot.btre
if ( nbElems == 0 )
{
// The tree is empty, it's the root, we have nothing to return
- stack.push( new ParentPos<K, V>( null, -1 ) );
+ stack[depth] = new ParentPos<K, V>( null, -1 );
- return new TupleCursorImpl<K, V>( btree, transaction, stack );
+ return new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
}
else
{
@@ -732,9 +732,9 @@ import org.apache.directory.mavibot.btre
setDupsContainer( parentPos, btree );
- stack.push( parentPos );
+ stack[depth] = parentPos;
- cursor = new TupleCursorImpl<K, V>( btree, transaction, stack );
+ cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
}
return cursor;
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java Wed Nov 27 07:03:46 2013
@@ -22,7 +22,6 @@ package org.apache.directory.mavibot.btr
import java.io.IOException;
import java.lang.reflect.Array;
-import java.util.LinkedList;
import java.util.List;
import org.apache.directory.mavibot.btree.Tuple;
@@ -943,7 +942,7 @@ import org.apache.directory.mavibot.btre
/**
* {@inheritDoc}
*/
- public TupleCursorImpl<K, V> browse( K key, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+ public TupleCursorImpl<K, V> browse( K key, Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
throws IOException
{
int pos = findPos( key );
@@ -954,21 +953,25 @@ import org.apache.directory.mavibot.btre
}
// We first stack the current page
- stack.push( new ParentPos<K, V>( this, pos ) );
+ stack[depth++] = new ParentPos<K, V>( this, pos );
+
+ Page<K, V> page = children[pos].getValue( btree );
- return children[pos].getValue( btree ).browse( key, transaction, stack );
+ return page.browse( key, transaction, stack, depth );
}
/**
* {@inheritDoc}
*/
- public TupleCursorImpl<K, V> browse( Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+ public TupleCursorImpl<K, V> browse( Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
throws IOException
{
- stack.push( new ParentPos<K, V>( this, 0 ) );
+ stack[depth++] = new ParentPos<K, V>( this, 0 );
+
+ Page<K, V> page = children[0].getValue( btree );
- return children[0].getValue( btree ).browse( transaction, stack );
+ return page.browse( transaction, stack, depth );
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Page.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Page.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Page.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Page.java Wed Nov 27 07:03:46 2013
@@ -131,10 +131,11 @@ import org.apache.directory.mavibot.btre
* @param key The key we are looking for.
* @param transaction The started transaction for this operation
* @param stack The stack of parents we go through to get to this page
+ * @param depth The current depth
* @return A Cursor to browse the next elements
* @throws IOException If we have an error while trying to access the page
*/
- TupleCursorImpl<K, V> browse( K key, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+ TupleCursorImpl<K, V> browse( K key, Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
throws IOException;
@@ -146,7 +147,7 @@ import org.apache.directory.mavibot.btre
* @return A Cursor to browse the next elements
* @throws IOException If we have an error while trying to access the page
*/
- TupleCursorImpl<K, V> browse( Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+ TupleCursorImpl<K, V> browse( Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
throws EndOfFileExceededException, IOException;
|