directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1784232 [3/9] - in /directory/mavibot/branches/single-value/mavibot/src: main/java/org/apache/directory/mavibot/btree/ main/java/org/apache/directory/mavibot/btree/serializer/ test/java/org/apache/directory/mavibot/btree/
Date Fri, 24 Feb 2017 07:16:38 GMT
Modified: directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/Leaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/Leaf.java?rev=1784232&r1=1784231&r2=1784232&view=diff
==============================================================================
--- directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/Leaf.java (original)
+++ directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/Leaf.java Fri Feb 24 07:16:37 2017
@@ -22,10 +22,13 @@ package org.apache.directory.mavibot.btr
 
 import java.io.IOException;
 import java.lang.reflect.Array;
+import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.List;
 
-import org.apache.directory.mavibot.btree.exception.CursorException;
-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;
 
 
 /**
@@ -39,7 +42,7 @@ import org.apache.directory.mavibot.btre
 /* No qualifier */class Leaf<K, V> extends AbstractPage<K, V>
 {
     /** Values associated with keys */
-    protected ValueHolder<V>[] values;
+    private ValueHolder<V>[] values;
 
 
     /**
@@ -58,20 +61,21 @@ import org.apache.directory.mavibot.btre
      *
      * @param btree The BTree this page belongs to.
      * @param revision The page revision
-     * @param nbElems The number of elements this page will contain
+     * @param nbPageElems The number of elements this page will contain
      */
     @SuppressWarnings("unchecked")
-    Leaf( BTree<K, V> btree, long revision, int nbElems )
+    Leaf( BTree<K, V> btree, long revision, int nbPageElems )
     {
-        super( btree, revision, nbElems );
-        values = ( ValueHolder<V>[] ) Array.newInstance( ValueHolderImpl.class, btree.getPageSize() );
+        super( btree, revision, nbPageElems );
+        values = ( ValueHolder<V>[] ) Array.newInstance( ValueHolder.class, btree.getPageNbElem() );
     }
 
 
     /**
      * {@inheritDoc}
      */
-    public InsertResult<K, V> insert( K key, V value, long revision ) throws IOException
+    @Override
+    public InsertResult<K, V> insert( WriteTransaction transaction, K key, V value ) throws IOException
     {
         // Find the key into this leaf
         int pos = findPos( key );
@@ -80,39 +84,21 @@ import org.apache.directory.mavibot.btre
         {
             // We already have the key in the page : replace the value
             // into a copy of this page, unless the page has already be copied
-            int index = -( pos + 1 );
-
-            // Replace the existing value in a copy of the current page
-            InsertResult<K, V> result = replaceElement( revision, key, value, index );
-
-            return result;
+            return replaceElement( transaction, value, -( pos + 1 ) );
         }
 
         // The key is not present in the leaf. We have to add it in the page
-        if ( nbElems < btree.getPageSize() )
+        if ( nbPageElems < btree.getPageNbElem() )
         {
             // The current page is not full, it can contain the added element.
             // We insert it into a copied page and return the result
-            Page<K, V> modifiedPage = null;
-
-            modifiedPage = addElement( revision, key, value, pos );
-
-            InsertResult<K, V> result = new ModifyResult<K, V>( modifiedPage, null );
-            result.addCopiedPage( this );
-
-            return result;
+            return modifyLeaf( transaction, key, value, pos );
         }
         else
         {
             // The Page is already full : we split it and return the overflow element,
             // after having created two pages.
-            InsertResult<K, V> result = null;
-
-            result = addAndSplit( revision, key, value, pos );
-
-            result.addCopiedPage( this );
-
-            return result;
+            return addAndSplit( transaction, key, value, pos );
         }
     }
 
@@ -121,11 +107,14 @@ import org.apache.directory.mavibot.btre
      * {@inheritDoc}
      */
     @SuppressWarnings("unchecked")
-    /* no qualifier */DeleteResult<K, V> delete( K key, V value, long revision, Page<K, V> parent, int parentPos )
+    @Override
+    /* no qualifier */DeleteResult<K, V> delete( WriteTransaction transaction, K key, Page<K, V> parent, int parentPos )
         throws IOException
     {
+        long revision = transaction.getRevision();
+        
         // Check that the leaf is not empty
-        if ( nbElems == 0 )
+        if ( nbPageElems == 0 )
         {
             // Empty leaf
             return NotPresentResult.NOT_PRESENT;
@@ -141,43 +130,30 @@ import org.apache.directory.mavibot.btre
         }
 
         // Get the removed element
-        Tuple<K, V> removedElement = null;
+        Tuple<K, V> removedElement;
 
         // flag to detect if a key was completely removed
         int index = -( pos + 1 );
 
         ValueHolder<V> valueHolder = values[index];
 
-        if ( value == null )
-        {
-            // we have to delete the whole value
-            removedElement = new Tuple<K, V>( keys[index].getKey(), value ); // the entire value was removed
-        }
-        else
-        {
-            if ( valueHolder.contains( value ) )
-            {
-                removedElement = new Tuple<K, V>( keys[index].getKey(), value ); // only one value was removed
-            }
-            else
-            {
-                return NotPresentResult.NOT_PRESENT;
-            }
-        }
+        // we have to delete the whole value
+        removedElement = new Tuple<>( keys[index].getKey(), valueHolder.get() ); // the entire value was removed
 
-        Leaf<K, V> newLeaf = null;
+        Leaf<K, V> newLeaf;
 
         // No value, we can remove the key
-        newLeaf = new Leaf<K, V>( btree, revision, nbElems - 1 );
+        newLeaf = new Leaf<>( btree, revision, nbPageElems - 1 );
+        newLeaf.initId( transaction.getRecordManagerHeader() );
 
         // Create the result
-        DeleteResult<K, V> defaultResult = new RemoveResult<K, V>( newLeaf, removedElement );
+        DeleteResult<K, V> defaultResult = new RemoveResult<>( newLeaf, removedElement );
 
         // If the parent is null, then this page is the root page.
         if ( parent == null )
         {
             // Just remove the entry if it's present, or replace it if we have more than one value in the ValueHolder
-            copyAfterRemovingElement( value, newLeaf, index );
+            copyAfterRemovingElement( newLeaf, index );
 
             // The current page is added in the copied page list
             defaultResult.addCopiedPage( this );
@@ -188,41 +164,34 @@ import org.apache.directory.mavibot.btre
         {
             // The current page is not the root. Check if the leaf has more than N/2
             // elements
-            int halfSize = btree.getPageSize() / 2;
+            int halfSize = btree.getPageNbElem() / 2;
 
-            if ( nbElems == halfSize )
+            if ( nbPageElems == halfSize )
             {
                 // We have to find a sibling now, and either borrow an entry from it
                 // if it has more than N/2 elements, or to merge the two pages.
                 // Check in both next and previous page, if they have the same parent
                 // and select the biggest page with the same parent to borrow an element.
-                int siblingPos = selectSibling( parent, parentPos );
+                int siblingPos = selectSibling( transaction, parent, parentPos );
                 Leaf<K, V> sibling = ( Leaf<K, V> ) ( ( ( Node<K, V> ) parent )
                     .getPage( siblingPos ) );
 
-                if ( sibling.getNbElems() == halfSize )
+                if ( sibling.nbPageElems == halfSize )
                 {
                     // We will merge the current page with its sibling
-                    DeleteResult<K, V> result = mergeWithSibling( removedElement, revision, sibling,
-                        ( siblingPos < parentPos ), index );
-
-                    return result;
+                    return mergeWithSibling( transaction, removedElement, sibling, siblingPos < parentPos , index );
                 }
                 else
                 {
                     // We can borrow the element from the left sibling
                     if ( siblingPos < parentPos )
                     {
-                        DeleteResult<K, V> result = borrowFromLeft( removedElement, revision, sibling, index );
-
-                        return result;
+                        return borrowFromLeft( transaction, removedElement, sibling, index );
                     }
                     else
                     {
                         // Borrow from the right sibling
-                        DeleteResult<K, V> result = borrowFromRight( removedElement, revision, sibling, index );
-
-                        return result;
+                        return borrowFromRight( transaction, removedElement, sibling, index );
                     }
                 }
             }
@@ -232,7 +201,7 @@ import org.apache.directory.mavibot.btre
                 // We simply remove the element from the page, and if it was the leftmost,
                 // we return the new pivot (it will replace any instance of the removed
                 // key in its parents)
-                copyAfterRemovingElement( value, newLeaf, index );
+                copyAfterRemovingElement( newLeaf, index );
 
                 // The current page is added in the copied page list
                 defaultResult.addCopiedPage( this );
@@ -253,29 +222,30 @@ import org.apache.directory.mavibot.btre
      * @return The new created leaf containing the sibling and the old page.
      * @throws IOException If we have an error while trying to access the page
      */
-    private DeleteResult<K, V> mergeWithSibling( Tuple<K, V> removedElement, long revision,
-        Leaf<K, V> sibling,
-        boolean isLeft, int pos )
-        throws EndOfFileExceededException, IOException
+    private DeleteResult<K, V> mergeWithSibling( WriteTransaction transaction, Tuple<K, V> removedElement,
+        Leaf<K, V> sibling, boolean isLeft, int pos ) throws IOException
     {
+        long revision = transaction.getRevision();
+        
         // Create the new page. It will contain N - 1 elements (the maximum number)
         // as we merge two pages that contain N/2 elements minus the one we remove
-        Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, btree.getPageSize() - 1 );
+        Leaf<K, V> newLeaf = new Leaf<>( btree, revision, btree.getPageNbElem() - 1 );
+        newLeaf.initId( transaction.getRecordManagerHeader() );
 
         if ( isLeft )
         {
             // The sibling is on the left
             // Copy all the elements from the sibling first
-            System.arraycopy( sibling.keys, 0, newLeaf.keys, 0, sibling.nbElems );
-            System.arraycopy( sibling.values, 0, newLeaf.values, 0, sibling.nbElems );
+            System.arraycopy( sibling.keys, 0, newLeaf.keys, 0, sibling.nbPageElems );
+            System.arraycopy( sibling.values, 0, newLeaf.values, 0, sibling.nbPageElems );
 
             // Copy all the elements from the page up to the deletion position
-            System.arraycopy( keys, 0, newLeaf.keys, sibling.nbElems, pos );
-            System.arraycopy( values, 0, newLeaf.values, sibling.nbElems, pos );
+            System.arraycopy( keys, 0, newLeaf.keys, sibling.nbPageElems, pos );
+            System.arraycopy( values, 0, newLeaf.values, sibling.nbPageElems, pos );
 
             // And copy the remaining elements after the deletion point
-            System.arraycopy( keys, pos + 1, newLeaf.keys, sibling.nbElems + pos, nbElems - pos - 1 );
-            System.arraycopy( values, pos + 1, newLeaf.values, sibling.nbElems + pos, nbElems - pos - 1 );
+            System.arraycopy( keys, pos + 1, newLeaf.keys, sibling.nbPageElems + pos, nbPageElems - pos - 1 );
+            System.arraycopy( values, pos + 1, newLeaf.values, sibling.nbPageElems + pos, nbPageElems - pos - 1 );
         }
         else
         {
@@ -285,16 +255,16 @@ import org.apache.directory.mavibot.btre
             System.arraycopy( values, 0, newLeaf.values, 0, pos );
 
             // Then copy the remaining elements after the deletion point
-            System.arraycopy( keys, pos + 1, newLeaf.keys, pos, nbElems - pos - 1 );
-            System.arraycopy( values, pos + 1, newLeaf.values, pos, nbElems - pos - 1 );
+            System.arraycopy( keys, pos + 1, newLeaf.keys, pos, nbPageElems - pos - 1 );
+            System.arraycopy( values, pos + 1, newLeaf.values, pos, nbPageElems - pos - 1 );
 
             // And copy all the elements from the sibling
-            System.arraycopy( sibling.keys, 0, newLeaf.keys, nbElems - 1, sibling.nbElems );
-            System.arraycopy( sibling.values, 0, newLeaf.values, nbElems - 1, sibling.nbElems );
+            System.arraycopy( sibling.keys, 0, newLeaf.keys, nbPageElems - 1, sibling.nbPageElems );
+            System.arraycopy( sibling.values, 0, newLeaf.values, nbPageElems - 1, sibling.nbPageElems );
         }
 
         // And create the result
-        DeleteResult<K, V> result = new MergedWithSiblingResult<K, V>( newLeaf, removedElement );
+        DeleteResult<K, V> result = new MergedWithSiblingResult<>( newLeaf, removedElement );
 
         result.addCopiedPage( this );
         result.addCopiedPage( sibling );
@@ -314,24 +284,28 @@ import org.apache.directory.mavibot.btre
      * @return The resulting pages
      * @throws IOException If we have an error while trying to access the page
      */
-    private DeleteResult<K, V> borrowFromLeft( Tuple<K, V> removedElement, long revision, Leaf<K, V> sibling,
+    private DeleteResult<K, V> borrowFromLeft( WriteTransaction transaction, Tuple<K, V> removedElement, Leaf<K, V> sibling,
         int pos )
         throws IOException
     {
+        long revision = transaction.getRevision();
+        
         // The sibling is on the left, borrow the rightmost element
-        K siblingKey = sibling.keys[sibling.getNbElems() - 1].getKey();
-        ValueHolder<V> siblingValue = null;
-        siblingValue = sibling.values[sibling.getNbElems() - 1];
+        K siblingKey = sibling.keys[sibling.nbPageElems - 1].getKey();
+        ValueHolder<V> siblingValue;
+        siblingValue = sibling.values[sibling.nbPageElems - 1];
 
         // Create the new sibling, with one less element at the end
-        Leaf<K, V> newSibling = ( Leaf<K, V> ) sibling.copy( revision, sibling.getNbElems() - 1 );
+        Leaf<K, V> newSibling = ( Leaf<K, V> ) sibling.copy( transaction, sibling.nbPageElems - 1 );
+        newSibling.initId( transaction.getRecordManagerHeader() );
 
         // Create the new page and add the new element at the beginning
         // First copy the current page, with the same size
-        Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems );
+        Leaf<K, V> newLeaf = new Leaf<>( btree, revision, nbPageElems );
+        newLeaf.initId( transaction.getRecordManagerHeader() );
 
         // Insert the borrowed element
-        newLeaf.keys[0] = new KeyHolderImpl<K>( btree.getKeySerializer(), siblingKey );
+        newLeaf.keys[0] = new KeyHolder<K>( btree.getKeySerializer(), siblingKey );
         newLeaf.values[0] = siblingValue;
 
         // Copy the keys and the values up to the insertion position,
@@ -342,7 +316,7 @@ import org.apache.directory.mavibot.btre
         System.arraycopy( keys, pos + 1, newLeaf.keys, pos + 1, keys.length - pos - 1 );
         System.arraycopy( values, pos + 1, newLeaf.values, pos + 1, values.length - pos - 1 );
 
-        DeleteResult<K, V> result = new BorrowedFromLeftResult<K, V>( newLeaf, newSibling, removedElement );
+        DeleteResult<K, V> result = new BorrowedFromLeftResult<>( newLeaf, newSibling, removedElement );
 
         // Add the copied pages to the list
         result.addCopiedPage( this );
@@ -363,29 +337,33 @@ import org.apache.directory.mavibot.btre
      * @return The resulting pages
      * @throws IOException If we have an error while trying to access the page
      */
-    private DeleteResult<K, V> borrowFromRight( Tuple<K, V> removedElement, long revision, Leaf<K, V> sibling,
+    private DeleteResult<K, V> borrowFromRight( WriteTransaction transaction, Tuple<K, V> removedElement, Leaf<K, V> sibling,
         int pos )
         throws IOException
     {
+        long revision = transaction.getRevision();
+        
         // The sibling is on the left, borrow the rightmost element
         K siblingKey = sibling.keys[0].getKey();
-        ValueHolder<V> siblingHolder = null;
+        ValueHolder<V> siblingHolder;
         siblingHolder = sibling.values[0];
 
         // Create the new sibling
-        Leaf<K, V> newSibling = new Leaf<K, V>( btree, revision, sibling.getNbElems() - 1 );
+        Leaf<K, V> newSibling = new Leaf<>( btree, revision, sibling.nbPageElems - 1 );
+        newSibling.initId( transaction.getRecordManagerHeader() );
 
         // Copy the keys and the values from 1 to N in the new sibling
-        System.arraycopy( sibling.keys, 1, newSibling.keys, 0, sibling.nbElems - 1 );
-        System.arraycopy( sibling.values, 1, newSibling.values, 0, sibling.nbElems - 1 );
+        System.arraycopy( sibling.keys, 1, newSibling.keys, 0, sibling.nbPageElems - 1 );
+        System.arraycopy( sibling.values, 1, newSibling.values, 0, sibling.nbPageElems - 1 );
 
         // Create the new page and add the new element at the end
         // First copy the current page, with the same size
-        Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems );
+        Leaf<K, V> newLeaf = new Leaf<>( btree, revision, nbPageElems );
+        newLeaf.initId( transaction.getRecordManagerHeader() );
 
         // Insert the borrowed element at the end
-        newLeaf.keys[nbElems - 1] = new KeyHolderImpl<K>( btree.getKeySerializer(), siblingKey );
-        newLeaf.values[nbElems - 1] = siblingHolder;
+        newLeaf.keys[nbPageElems - 1] = new KeyHolder<K>( btree.getKeySerializer(), siblingKey );
+        newLeaf.values[nbPageElems - 1] = siblingHolder;
 
         // Copy the keys and the values up to the deletion position,
         System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
@@ -395,7 +373,7 @@ import org.apache.directory.mavibot.btre
         System.arraycopy( keys, pos + 1, newLeaf.keys, pos, keys.length - pos - 1 );
         System.arraycopy( values, pos + 1, newLeaf.values, pos, values.length - pos - 1 );
 
-        DeleteResult<K, V> result = new BorrowedFromRightResult<K, V>( newLeaf, newSibling, removedElement );
+        DeleteResult<K, V> result = new BorrowedFromRightResult<>( newLeaf, newSibling, removedElement );
 
         // Add the copied pages to the list
         result.addCopiedPage( this );
@@ -413,12 +391,12 @@ import org.apache.directory.mavibot.btre
      * @param pos The position into the page of the element to remove
      * @throws IOException If we have an error while trying to access the page
      */
-    private void copyAfterRemovingElement( V removedValue, Leaf<K, V> newLeaf, int pos )
+    private void copyAfterRemovingElement( Leaf<K, V> newLeaf, int pos )
         throws IOException
     {
         // Deal with the special case of a page with only one element by skipping
         // the copy, as we won't have any remaining  element in the page
-        if ( nbElems == 1 )
+        if ( nbPageElems == 1 )
         {
             return;
         }
@@ -436,6 +414,7 @@ import org.apache.directory.mavibot.btre
     /**
      * {@inheritDoc}
      */
+    @Override
     public V get( K key ) throws KeyNotFoundException, IOException
     {
         int pos = findPos( key );
@@ -456,7 +435,7 @@ import org.apache.directory.mavibot.btre
      */
     /* No qualifier */KeyHolder<K> getKeyHolder( int pos )
     {
-        if ( pos < nbElems )
+        if ( pos < nbPageElems )
         {
             return keys[pos];
         }
@@ -470,6 +449,7 @@ import org.apache.directory.mavibot.btre
     /**
      * {@inheritDoc}
      */
+    @Override
     public boolean hasKey( K key )
     {
         int pos = findPos( key );
@@ -506,7 +486,7 @@ import org.apache.directory.mavibot.btre
      */
     /* no qualifier */ValueHolder<V> getValue( int pos )
     {
-        if ( pos < nbElems )
+        if ( pos < nbPageElems )
         {
             return values[pos];
         }
@@ -522,6 +502,7 @@ import org.apache.directory.mavibot.btre
      * @param pos The position in the values array
      * @param value the value to inject
      */
+    @Override
     /* no qualifier */void setValue( int pos, ValueHolder<V> value )
     {
         values[pos] = value;
@@ -531,139 +512,88 @@ import org.apache.directory.mavibot.btre
     /**
      * {@inheritDoc}
      */
-    public TupleCursor<K, V> browse( K key, ReadTransaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
+    @Override
+    public TupleCursor<K, V> browse( Transaction transaction, K key, ParentPos<K, V>[] stack, int depth )
     {
         int pos = findPos( key );
 
         // First use case : the leaf is empty (this is a root page)
-        if ( nbElems == 0 )
+        if ( nbPageElems == 0 )
         {
             // We have to return an empty cursor
-            return new EmptyTupleCursor<K, V>();
+            return new EmptyTupleCursor<>();
         }
 
         // The cursor we will return
-        TupleCursor<K, V> cursor = new TupleCursor<K, V>( transaction, stack, depth );
+        TupleCursor<K, V> cursor = new TupleCursor<>( transaction, stack, depth );
 
         // Depending on the position, we will proceed differently :
         // 1) if the key is found in the page, the cursor will be 
-        // set to the previous position (or BEFORE_FIRST).
-        // 2) The key has not been found, but is in the middle of the
-        // page (ie, other keys above the one we are looking for exist),
-        // the cursor will be set to the current position
-        // 3) The key has not been found, and we are at the end of
-        // the page. We have to fetch the next key in yhe B-tree
+        // set to its position
+        // 2) The key has not been found, we set the position to the
+        // value findPos returned
         if ( pos < 0 )
         {
             // The key has been found.
             pos = -( pos + 1 );
 
             // Start at the found position in the page
-            ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
-
-            // And store this position in the stack
-            stack[depth] = parentPos;
-
-            return cursor;
+            stack[depth] = new ParentPos<>( this, pos );
         }
         else
         {
             // The key has not been found, there are keys above this one. 
-            // Select the value just above
-            if ( pos < nbElems )
+            // Select the value just above if we have some
+            if ( pos == 0 )
+            {
+                // We are before the first value
+                stack[depth] = new ParentPos<>( this, pos );
+                
+                cursor.beforeFirst();
+            }
+            else if ( pos < nbPageElems )
             {
                 // There is at least one key above the one we are looking for.
                 // This will be the starting point.
-                ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
-
-                stack[depth] = parentPos;
-
-                return cursor;
+                stack[depth] = new ParentPos<>( this, pos );
             }
             else
             {
-                // We are at the end of a leaf. We have to see if we have other
-                // keys on the right.
-                if ( depth == 0 )
-                {
-                    // No children, we are at the end of the root page
-                    stack[depth] = new ParentPos<K, V>( this, pos );
-
-                    // As we are done, set the cursor at the end
-                    try
-                    {
-                        cursor.afterLast();
-                    }
-                    catch ( CursorException e )
-                    {
-                        e.printStackTrace();
-                    }
+                // We are at the end of the tree.
+                // No children, we are at the end of the root page
+                stack[depth] = new ParentPos<>( this, pos );
 
-                    return cursor;
-                }
-                else
-                {
-                    // We have to find the adjacent key in the B-tree
-                    boolean isLast = true;
-                    stack[depth] = new ParentPos<K, V>( this, pos );
-
-                    // Check each upper node, starting from the direct parent
-                    int stackIndex = depth - 1;
-
-                    for ( int i = stackIndex; i >= 0; i-- )
-                    {
-                        if ( stack[i].pos < stack[i].page.getNbElems() )
-                        {
-                            isLast = false;
-                            break;
-                        }
-
-                        stackIndex--;
-                    }
-
-                    if ( isLast )
-                    {
-                        // We don't have any more elements
-                        try
-                        {
-                            cursor.afterLast();
-                        }
-                        catch ( CursorException e )
-                        {
-                            e.printStackTrace();
-                        }
-
-                        return cursor;
-                    }
-
-                    return cursor;
-                }
+                // As we are done, set the cursor at the end
+                cursor.afterLast();
             }
         }
+
+        return cursor;
     }
 
 
     /**
      * {@inheritDoc}
      */
-    public TupleCursor<K, V> browse( ReadTransaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
+    @Override
+    public TupleCursor<K, V> browse( Transaction transaction, ParentPos<K, V>[] stack, int depth )
     {
         int pos = 0;
-        TupleCursor<K, V> cursor = null;
+        TupleCursor<K, V> cursor;
 
-        if ( nbElems == 0 )
+        if ( nbPageElems == 0 )
         {
             // The tree is empty, it's the root, we have nothing to return
-            stack[depth] = new ParentPos<K, V>( null, -1 );
+            stack[depth] = new ParentPos<>( null, -1 );
 
-            return new TupleCursor<K, V>( transaction, stack, depth );
+            return new TupleCursor<>( transaction, stack, depth );
         }
         else
         {
             // Start at the beginning of the page
-            ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
+            ParentPos<K, V> parentPos = new ParentPos<>( this, pos );
             stack[depth] = parentPos;
-            cursor = new TupleCursor<K, V>( transaction, stack, depth );
+            cursor = new TupleCursor<>( transaction, stack, depth );
         }
 
         return cursor;
@@ -674,15 +604,16 @@ import org.apache.directory.mavibot.btre
      * Copy the current page and all of the keys, values and children, if it's not a leaf.
      *
      * @param revision The new revision
-     * @param nbElems The number of elements to copy
+     * @param nbPageElems The number of elements to copy
      * @return The copied page
      */
-    public Page<K, V> copy( long revision, int nbElems )
+    public Page<K, V> copy( WriteTransaction transaction, int nbPageElems )
     {
-        Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems );
+        Leaf<K, V> newLeaf = new Leaf<>( btree, transaction.getRevision(), nbPageElems );
+        newLeaf.setId( id );
 
         // Copy the keys and the values
-        System.arraycopy( keys, 0, newLeaf.keys, 0, nbElems );
+        System.arraycopy( keys, 0, newLeaf.keys, 0, nbPageElems );
 
         if ( values != null )
         {
@@ -692,18 +623,20 @@ import org.apache.directory.mavibot.btre
 
             for ( ValueHolder<V> valueHolder : values )
             {
-                try
-                {
-                    newLeaf.values[pos++] = valueHolder.clone();
-                }
-                catch ( CloneNotSupportedException e )
+                if ( valueHolder != null )
                 {
-                    // TODO Auto-generated catch block
-                    e.printStackTrace();
+                    try
+                    {
+                        newLeaf.values[pos++] = valueHolder.clone();
+                    }
+                    catch ( CloneNotSupportedException e )
+                    {
+                        e.printStackTrace();
+                    }
                 }
 
-                // Stop when we have copied nbElems values
-                if ( pos == nbElems )
+                // Stop when we have copied nbPageElems values
+                if ( pos == nbPageElems )
                 {
                     break;
                 }
@@ -718,17 +651,21 @@ import org.apache.directory.mavibot.btre
      * Copy the current page and all of the keys, values and children, if it's not a leaf.
      *
      * @param revision The new revision
-     * @param nbElems The number of elements to copy
+     * @param nbPageElems The number of elements to copy
      * @return The copied page
      */
-    public Page<K, V> copy( long revision )
+    @Override
+    public Page<K, V> copy( WriteTransaction transaction )
     {
-        Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems );
+        long revision = transaction.getRevision();
+        
+        Leaf<K, V> newLeaf = new Leaf<>( btree, revision, nbPageElems );
+        newLeaf.initId( transaction.getRecordManagerHeader() );
 
         // Copy the keys and the values
-        System.arraycopy( keys, 0, newLeaf.keys, 0, nbElems );
+        System.arraycopy( keys, 0, newLeaf.keys, 0, nbPageElems );
 
-        if ( values != null )
+        if ( ( values != null ) && ( nbPageElems > 0 ) )
         {
             // It' not enough to copy the ValueHolder, we have to clone them
             // as ValueHolders are mutable
@@ -742,12 +679,11 @@ import org.apache.directory.mavibot.btre
                 }
                 catch ( CloneNotSupportedException e )
                 {
-                    // TODO Auto-generated catch block
                     e.printStackTrace();
                 }
 
-                // Stop when we have copied nbElems values
-                if ( pos == nbElems )
+                // Stop when we have copied nbPageElems values
+                if ( pos == nbPageElems )
                 {
                     break;
                 }
@@ -761,54 +697,102 @@ import org.apache.directory.mavibot.btre
     /**
      * Copy the current page if needed, and replace the value at the position we have found the key.
      *
-     * @param revision The new page revision
+     * @param transaction The {@link WriteTransaction} we are processing this update in
      * @param key The new key
      * @param value the new value
      * @param pos The position of the key in the page
-     * @return The copied page
+     * @return A {@link InserResult} instance, containing the reference to the new page, or an 
+     * {@link ExistsResult} instance, if the value already exists in the page.
      * @throws IOException If we have an error while trying to access the page
      */
-    private InsertResult<K, V> replaceElement( long revision, K key, V value, int pos )
+    private InsertResult<K, V> replaceElement( WriteTransaction transaction, V value, int pos )
         throws IOException
     {
         Leaf<K, V> newLeaf = this;
-
+    
         // Get the previous value from the leaf (it's a copy)
         ValueHolder<V> valueHolder = values[pos];
 
         boolean valueExists = valueHolder.contains( value );
-
-        if ( this.revision != revision )
+        
+        // Check if the value does not already exist in the leaf
+        if ( valueExists )
         {
-            // The page hasn't been modified yet, we need to copy it first
-            newLeaf = ( Leaf<K, V> ) copy( revision, nbElems );
+            // Nothing to do, just return
+            return ExistsResult.EXISTS;
         }
 
-        // Get the previous value from the leaf (it's a copy)
-        valueHolder = newLeaf.values[pos];
-        V replacedValue = null;
-
-        if ( !valueExists )
-        {
-            valueHolder.set( value );
-            newLeaf.values[pos] = valueHolder;
-        }
-        else
+        // If the page was created in a previous revision, copy it
+        if ( revision != transaction.getRevision() )
         {
-            // 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.set( value );
+            newLeaf = ( Leaf<K, V> ) copy( transaction, nbPageElems );
         }
 
+        // Get the previous value from the leaf
+        V replacedValue = newLeaf.values[pos].get();
+        newLeaf.values[pos].set( value );
+
         // Create the result
-        InsertResult<K, V> result = new ModifyResult<K, V>( newLeaf, replacedValue );
-        result.addCopiedPage( this );
+        InsertResult<K, V> result = new ModifyResult<>( newLeaf, replacedValue );
+        
+        // If we have copied a page, put it in the transaction
+        if ( revision != transaction.getRevision() )
+        {
+            transaction.addWALObject( newLeaf );
+            
+            // And store the old leaf into teh CopiedPages B-tree, if we are not
+            // processing the CopiedPages B-tree itself
+            if ( btree.getType() != BTreeTypeEnum.COPIED_PAGES_BTREE )
+            {
+                transaction.addCopiedWALObject( this );
+            }
+        }
 
         return result;
     }
 
+    
+    /**
+     * Add a new element in a page, at a gven position. The page will not be fulled up by this addition.
+     *
+     * @param transaction The {@link WriteTransaction} we are processing this update in
+     * @param key The key to add
+     * @param value The value to add
+     * @param pos The position of the insertion of the new element
+     * @return An {@link InserResult} instance, containing a reference to the newly created Leaf.
+     * @throws IOException If we have an error while trying to access the page
+     */
+    private InsertResult<K, V> modifyLeaf( WriteTransaction transaction, K key, V value, int pos ) throws IOException
+    {
+        Leaf<K, V> newLeaf = this;
+        
+        // If the page was created in a previous revision, copy it
+        if ( revision != transaction.getRevision() )
+        {
+            newLeaf = ( Leaf<K, V> ) copy( transaction, nbPageElems );
+        }
+
+        // Inject the <K, V> into the new leaf
+        Page<K, V> modifiedPage = newLeaf.addElement( key, value, pos );
+
+        // And return a modified result
+        InsertResult<K, V> result = new ModifyResult<>( modifiedPage, null );
+        
+        // Add the new leaf in the transaction pages map, and add
+        // the old leaf into the CopiedPages B-tree, if needed
+        if ( revision != transaction.getRevision() )
+        {
+            transaction.addWALObject( newLeaf );
+            
+            if ( btree.getType() != BTreeTypeEnum.COPIED_PAGES_BTREE )
+            {
+                transaction.addCopiedWALObject( this );
+            }
+        }
+
+        return result;
+    }
+    
 
     /**
      * Adds a new <K, V> into the current page at a given position. We return the
@@ -820,30 +804,30 @@ import org.apache.directory.mavibot.btre
      * @param pos The position into the page
      * @return The modified page with the <K,V> element added
      */
-    private Page<K, V> addElement( long revision, K key, V value, int pos )
+    private Page<K, V> addElement( K key, V value, int pos )
     {
         // Create the value holder
-        ValueHolder<V> valueHolder = new ValueHolderImpl<V>( btree, value );
+        ValueHolder<V> valueHolder = new ValueHolder<>( btree, value );
 
         // Deal with the special case of an empty page
-        if ( nbElems == 0 )
+        if ( nbPageElems == 0 )
         {
-            keys[0] = new KeyHolderImpl<K>( btree.getKeySerializer(), key );
+            keys[0] = new KeyHolder<>( btree.getKeySerializer(), key );
             values[0] = valueHolder;
         }
         else
         {
             // Copy the keys and the values from the insertion point one position to the right
-        	int nbElementToMove = nbElems - pos;
+            int nbElementToMove = nbPageElems - pos;
             System.arraycopy( keys, pos, keys, pos + 1, nbElementToMove );
             System.arraycopy( values, pos, values, pos + 1, nbElementToMove );
 
             // Add the new element
-            keys[pos] = new KeyHolderImpl<K>( btree.getKeySerializer(), key );
+            keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), key );
             values[pos] = valueHolder;
         }
 
-        nbElems++;
+        nbPageElems++;
 
         return this;
     }
@@ -852,37 +836,40 @@ import org.apache.directory.mavibot.btre
     /**
      * Split a full page into two new pages, a left, a right and a pivot element. The new pages will
      * each contains half of the original elements. <br/>
-     * The pivot will be computed, depending on the place
-     * we will inject the newly added element. <br/>
+     * The pivot will be computed, depending on the place we will inject the newly added element. <br/>
      * If the newly added element is in the middle, we will use it
      * as a pivot. Otherwise, we will use either the last element in the left page if the element is added
      * on the left, or the first element in the right page if it's added on the right.
      *
-     * @param revision The new revision for all the created pages
+     * @param transaction The {@link WriteTransaction} we are processing this update in
      * @param key The key to add
      * @param value The value to add
      * @param pos The position of the insertion of the new element
-     * @return An OverflowPage containing the pivot, and the new left and right pages
+     * @return An {@SplitResult} instance containing the pivot, and the new left and right pages. We haven't 
+     * created the new parent Node yet.
+     * @throws IOException If we have an error while trying to access the page
      */
-    private InsertResult<K, V> addAndSplit( long revision, K key, V value, int pos )
+    private SplitResult<K, V> addAndSplit( WriteTransaction transaction, K key, V value, int pos ) throws IOException
     {
-        int middle = btree.getPageSize() >> 1;
-        Leaf<K, V> leftLeaf = null;
-        Leaf<K, V> rightLeaf = null;
-        ValueHolder<V> valueHolder = new ValueHolderImpl<V>( btree, value );
+        long revision = transaction.getRevision();
+        int middle = btree.getPageNbElem() >> 1;
+        Leaf<K, V> leftLeaf;
+        Leaf<K, V> rightLeaf;
+        ValueHolder<V> valueHolder = new ValueHolder<>( btree, value );
 
         // Determinate where to store the new value
         if ( pos <= middle )
         {
             // The left page will contain the new value
-            leftLeaf = new Leaf<K, V>( btree, revision, middle + 1 );
+            leftLeaf = new Leaf<>( btree, revision, middle + 1 );
+            leftLeaf.initId( transaction.getRecordManagerHeader() );
 
             // Copy the keys and the values up to the insertion position
             System.arraycopy( keys, 0, leftLeaf.keys, 0, pos );
             System.arraycopy( values, 0, leftLeaf.values, 0, pos );
 
             // Add the new element
-            leftLeaf.keys[pos] = new KeyHolderImpl<K>( btree.getKeySerializer(), key );
+            leftLeaf.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), key );
             leftLeaf.values[pos] = valueHolder;
 
             // And copy the remaining elements
@@ -890,7 +877,8 @@ import org.apache.directory.mavibot.btre
             System.arraycopy( values, pos, leftLeaf.values, pos + 1, middle - pos );
 
             // Now, create the right page
-            rightLeaf = new Leaf<K, V>( btree, revision, middle );
+            rightLeaf = new Leaf<>( btree, revision, middle );
+            rightLeaf.initId( transaction.getRecordManagerHeader() );
 
             // Copy the keys and the values in the right page
             System.arraycopy( keys, middle, rightLeaf.keys, 0, middle );
@@ -899,14 +887,16 @@ import org.apache.directory.mavibot.btre
         else
         {
             // Create the left page
-            leftLeaf = new Leaf<K, V>( btree, revision, middle );
+            leftLeaf = new Leaf<>( btree, revision, middle );
+            leftLeaf.initId( transaction.getRecordManagerHeader() );
 
             // Copy all the element into the left page
             System.arraycopy( keys, 0, leftLeaf.keys, 0, middle );
             System.arraycopy( values, 0, leftLeaf.values, 0, middle );
 
             // Now, create the right page
-            rightLeaf = new Leaf<K, V>( btree, revision, middle + 1 );
+            rightLeaf = new Leaf<>( btree, revision, middle + 1 );
+            rightLeaf.initId( transaction.getRecordManagerHeader() );
 
             int rightPos = pos - middle;
 
@@ -915,27 +905,39 @@ import org.apache.directory.mavibot.btre
             System.arraycopy( values, middle, rightLeaf.values, 0, rightPos );
 
             // Add the new element
-            rightLeaf.keys[rightPos] = new KeyHolderImpl<K>( btree.getKeySerializer(), key );
+            rightLeaf.keys[rightPos] = new KeyHolder<>( btree.getKeySerializer(), key );
             rightLeaf.values[rightPos] = valueHolder;
 
             // And copy the remaining elements
-            System.arraycopy( keys, pos, rightLeaf.keys, rightPos + 1, nbElems - pos );
-            System.arraycopy( values, pos, rightLeaf.values, rightPos + 1, nbElems - pos );
+            System.arraycopy( keys, pos, rightLeaf.keys, rightPos + 1, nbPageElems - pos );
+            System.arraycopy( values, pos, rightLeaf.values, rightPos + 1, nbPageElems - pos );
         }
 
         // Get the pivot
         K pivot = rightLeaf.keys[0].getKey();
+        
+        // Inject the created leaves in the transaction
+        transaction.addWALObject( leftLeaf );
+        transaction.addWALObject( rightLeaf );
+        
+        // And remove the original page from the transaction
+        transaction.removeWALObject( id );
+        
+        // Add the old page into the CopiedPages B-tree if we aren't processing it
+        if ( btree.getType() != BTreeTypeEnum.COPIED_PAGES_BTREE )
+        {
+            transaction.addCopiedWALObject( this );
+        }
 
         // Create the result
-        InsertResult<K, V> result = new SplitResult<K, V>( pivot, leftLeaf, rightLeaf );
-
-        return result;
+        return new SplitResult<>( pivot, leftLeaf, rightLeaf );
     }
 
 
     /**
      * {@inheritDoc}
      */
+    @Override
     public K getLeftMostKey()
     {
         return keys[0].getKey();
@@ -945,39 +947,43 @@ import org.apache.directory.mavibot.btre
     /**
      * {@inheritDoc}
      */
+    @Override
     public K getRightMostKey()
     {
-        return keys[nbElems - 1].getKey();
+        return keys[nbPageElems - 1].getKey();
     }
 
 
     /**
      * {@inheritDoc}
      */
+    @Override
     public Tuple<K, V> findLeftMost() throws IOException
     {
         K key = keys[0].getKey();
 
-        return new Tuple<K, V>( key, values[0].get() );
+        return new Tuple<>( key, values[0].get() );
     }
 
 
     /**
      * {@inheritDoc}
      */
-    public Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException
+    @Override
+    public Tuple<K, V> findRightMost() throws IOException
     {
 
-        K key = keys[nbElems - 1].getKey();
-        V value = values[nbElems - 1].get();
+        K key = keys[nbPageElems - 1].getKey();
+        V value = values[nbPageElems - 1].get();
 
-        return new Tuple<K, V>( key, value );
+        return new Tuple<>( key, value );
     }
 
 
     /**
      * {@inheritDoc}
      */
+    @Override
     public boolean isLeaf()
     {
         return true;
@@ -987,6 +993,7 @@ import org.apache.directory.mavibot.btre
     /**
      * {@inheritDoc}
      */
+    @Override
     public boolean isNode()
     {
         return false;
@@ -994,8 +1001,222 @@ import org.apache.directory.mavibot.btre
 
 
     /**
+     * Serialize a Leaf's Value.
+     */
+    private int serializeLeafValue( int pos, List<byte[]> serializedData )
+        throws IOException
+    {
+        ValueHolder<V> valueHolder = getValue( pos );
+        int dataSize = 0;
+
+        // We have a serialized value. Just flush it
+        byte[] data = valueHolder.getRaw();
+
+        // Store the data if it's not 0
+        if ( data.length > 0 )
+        {
+            serializedData.add( data );
+            dataSize = data.length;
+        }
+
+        return dataSize;
+    }
+
+
+    /**
+     * Serialize a Leaf's key
+     */
+    private int serializeLeafKey( int pos, List<byte[]> serializedData )
+    {
+        int dataSize = 0;
+        KeyHolder<K> keyHolder = getKeyHolder( pos );
+        byte[] keyData = keyHolder.getRaw();
+
+        if ( keyData != null )
+        {
+            // We have to store the serialized key data
+            serializedData.add( keyData );
+            dataSize += keyData.length;
+        }
+        else
+        {
+            throw new RuntimeException( "Key cannot be null" );
+        }
+
+        return dataSize;
+    }
+
+
+    /**
+     * Write a root page with no elements in it
+     */
+    private PageIO[] serializeRootPage( WriteTransaction transaction, long revision ) throws IOException
+    {
+        RecordManager recordManager = transaction.getRecordManager();
+        RecordManagerHeader recordManagerHeader = transaction.getRecordManagerHeader();
+        
+        // We will have 1 single page if we have no elements
+        int bufferSize = RecordManager.LONG_SIZE + RecordManager.LONG_SIZE + RecordManager.INT_SIZE;
+
+        // This is either a new root page or a new page that will be filled later
+        pageIOs = recordManager.getFreePageIOs( recordManagerHeader, bufferSize );
+
+        // We need first to create a byte[] that will contain all the data
+        // For the root page, this is easy, as we only have to store the revision,
+        // and the number of elements, which is 0.
+        long position = 0L;
+
+        position = recordManager.store( recordManagerHeader, position, id, pageIOs[0] );
+        position = recordManager.store( recordManagerHeader, position, revision, pageIOs[0] );
+        position = recordManager.store( recordManagerHeader, position, 0, pageIOs[0] );
+
+        // Update the page size now
+        pageIOs[0].setSize( ( int ) position );
+
+        offset = pageIOs[0].getOffset();
+
+        return pageIOs;
+    }
+
+
+    /**
+     * Serialize a new Leaf. It will contain the following data :<br/>
+     * <ul>
+     * <li>the revision : a long</li>
+     * <li>the number of elements in the page : a positive int </li>
+     * <li>the keys : an array of serialized keys</li>
+     * <li>the values : an array of serialized values</li>
+     * </ul>
+     * {@inheritDoc}
+     */
+    @Override
+    public PageIO[] serialize( WriteTransaction transaction ) throws IOException
+    {
+        RecordManager recordManager = transaction.getRecordManager();
+        RecordManagerHeader recordManagerHeader = transaction.getRecordManagerHeader();
+        
+        if ( nbPageElems == 0 )
+        {
+            return serializeRootPage( transaction, revision );
+        }
+        else
+        {
+            // Prepare a list of byte[] that will contain the serialized page
+            int nbBuffers = 1 + 1 + 1 + 1 + nbPageElems * 2;
+            int dataSize = 0;
+            int serializedSize = 0;
+
+            // Now, we can create the list with the right size
+            List<byte[]> serializedData = new ArrayList<>( nbBuffers );
+
+            // The id
+            byte[] buffer = LongSerializer.serialize( id );
+            serializedData.add( buffer );
+            serializedSize += buffer.length;
+
+            // The revision
+            buffer = LongSerializer.serialize( revision );
+            serializedData.add( buffer );
+            serializedSize += buffer.length;
+
+            // The number of elements
+            buffer = IntSerializer.serialize( nbPageElems );
+            serializedData.add( buffer );
+            serializedSize += buffer.length;
+
+            // Iterate on the keys and values. We first serialize the value, then the key
+            // until we are done with all of them. If we are serializing a page, we have
+            // to serialize one more value
+            for ( int pos = 0; pos < nbPageElems; pos++ )
+            {
+                // Start with the value
+                dataSize += serializeLeafValue( pos, serializedData );
+                dataSize += serializeLeafKey( pos, serializedData );
+            }
+
+            // Store the data size
+            buffer = IntSerializer.serialize( dataSize );
+            serializedData.add( 3, buffer );
+            serializedSize += buffer.length;
+
+            serializedSize += dataSize;
+
+            // We are done. Allocate the pages we need to store the data, if we don't have
+            // a pageIOs or not enough room in it.
+            if ( pageIOs != null ) 
+            {
+                int nbNeededPages = RecordManager.computeNbPages( recordManagerHeader, dataSize );
+                
+                if ( nbNeededPages > pageIOs.length )
+                {
+                    pageIOs = recordManager.getFreePageIOs( recordManagerHeader, serializedSize );
+                }
+                else
+                {
+                    // Resize the page
+                    pageIOs[0].setSize( serializedSize );
+                }
+            }
+            else
+            {
+                pageIOs = recordManager.getFreePageIOs( recordManagerHeader, serializedSize );
+            }
+
+            // And store the data into those pages
+            long position = 0L;
+
+            for ( byte[] bytes : serializedData )
+            {
+                position = recordManager.storeRaw( recordManagerHeader, position, bytes, pageIOs );
+            }
+
+            offset = pageIOs[0].getOffset();
+            
+            return pageIOs;
+        }
+    }
+
+
+    /**
+     * Deserialize a Leaf. It will contain the following data :<br/>
+     * <ul>
+     * <li>the ID : a long</li>
+     * <li>the revision : a long</li>
+     * <li>the number of elements in the page : a positive int </li>
+     * <li>the size of the values/keys when serialized
+     * <li>the keys : an array of serialized keys</li>
+     * <li>the values : an array of serialized values</li>
+     * </ul>
+     * 
+     * The three first values have already been deserialized by the caller.
+     * {@inheritDoc}
+     */
+    @Override
+    public Page<K, V> deserialize( Transaction transaction, ByteBuffer byteBuffer ) throws IOException
+    {
+        // Iterate on the keys and values. We first serialize the value, then the key
+        // until we are done with all of them. If we are serializing a page, we have
+        // to serialize one more value
+        for ( int pos = 0; pos < nbPageElems; pos++ )
+        {
+            // Start with the value
+            V value = btree.getValueSerializer().deserialize( byteBuffer );
+            ValueHolder<V> valueHolder = new ValueHolder<>( btree, value );
+            BTreeFactory.setValue( btree, this, pos, valueHolder );
+
+            // Then the key
+            K key = btree.getKeySerializer().deserialize( byteBuffer );
+            BTreeFactory.setKey( btree, this, pos, key );
+        }
+        
+        return this;
+    }
+
+
+    /**
      * @see Object#toString()
      */
+    @Override
     public String toString()
     {
         StringBuilder sb = new StringBuilder();
@@ -1005,11 +1226,11 @@ import org.apache.directory.mavibot.btre
 
         sb.append( "] -> {" );
 
-        if ( nbElems > 0 )
+        if ( nbPageElems > 0 )
         {
             boolean isFirst = true;
 
-            for ( int i = 0; i < nbElems; i++ )
+            for ( int i = 0; i < nbPageElems; i++ )
             {
                 if ( isFirst )
                 {
@@ -1045,15 +1266,18 @@ import org.apache.directory.mavibot.btre
      * same as {@link #addElement(long, Object, Object, int)} except the values are not copied.
      * This method is only used while inserting an element into a sub-BTree.
      */
-    private Page<K, V> addSubTreeElement( long revision, K key, int pos )
+    private Page<K, V> addSubTreeElement( WriteTransaction transaction, K key, int pos )
     {
+        long revision = transaction.getRevision();
+        
         // First copy the current page, but add one element in the copied page
-        Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems + 1 );
+        Leaf<K, V> newLeaf = new Leaf<>( btree, revision, nbPageElems + 1 );
+        newLeaf.initId( transaction.getRecordManagerHeader() );
 
         // Deal with the special case of an empty page
-        if ( nbElems == 0 )
+        if ( nbPageElems == 0 )
         {
-            newLeaf.keys[0] = new KeyHolderImpl<K>( btree.getKeySerializer(), key );
+            newLeaf.keys[0] = new KeyHolder<K>( btree.getKeySerializer(), key );
         }
         else
         {
@@ -1061,7 +1285,7 @@ import org.apache.directory.mavibot.btre
             System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
 
             // Add the new element
-            newLeaf.keys[pos] = new KeyHolderImpl<K>( btree.getKeySerializer(), key );
+            newLeaf.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), key );
 
             // And copy the remaining elements
             System.arraycopy( keys, pos, newLeaf.keys, pos + 1, keys.length - pos );
@@ -1075,29 +1299,33 @@ import org.apache.directory.mavibot.btre
      * same as {@link #addAndSplit(long, Object, Object, int)} except the values are not copied.
      * This method is only used while inserting an element into a sub-BTree.
      */
-    private InsertResult<K, V> addAndSplitSubTree( long revision, K key, int pos )
+    private InsertResult<K, V> addAndSplitSubTree( WriteTransaction transaction, K key, int pos )
     {
-        int middle = btree.getPageSize() >> 1;
-        Leaf<K, V> leftLeaf = null;
-        Leaf<K, V> rightLeaf = null;
+        long revision = transaction.getRevision();
+        
+        int middle = btree.getPageNbElem() >> 1;
+        Leaf<K, V> leftLeaf;
+        Leaf<K, V> rightLeaf;
 
         // Determinate where to store the new value
         if ( pos <= middle )
         {
             // The left page will contain the new value
-            leftLeaf = new Leaf<K, V>( btree, revision, middle + 1 );
+            leftLeaf = new Leaf<>( btree, revision, middle + 1 );
+            leftLeaf.initId( transaction.getRecordManagerHeader() );
 
             // Copy the keys and the values up to the insertion position
             System.arraycopy( keys, 0, leftLeaf.keys, 0, pos );
 
             // Add the new element
-            leftLeaf.keys[pos] = new KeyHolderImpl<K>( btree.getKeySerializer(), key );
+            leftLeaf.keys[pos] = new KeyHolder<K>( btree.getKeySerializer(), key );
 
             // And copy the remaining elements
             System.arraycopy( keys, pos, leftLeaf.keys, pos + 1, middle - pos );
 
             // Now, create the right page
-            rightLeaf = new Leaf<K, V>( btree, revision, middle );
+            rightLeaf = new Leaf<>( btree, revision, middle );
+            rightLeaf.initId( transaction.getRecordManagerHeader() );
 
             // Copy the keys and the values in the right page
             System.arraycopy( keys, middle, rightLeaf.keys, 0, middle );
@@ -1105,13 +1333,15 @@ import org.apache.directory.mavibot.btre
         else
         {
             // Create the left page
-            leftLeaf = new Leaf<K, V>( btree, revision, middle );
+            leftLeaf = new Leaf<>( btree, revision, middle );
+            leftLeaf.initId( transaction.getRecordManagerHeader() );
 
             // Copy all the element into the left page
             System.arraycopy( keys, 0, leftLeaf.keys, 0, middle );
 
             // Now, create the right page
-            rightLeaf = new Leaf<K, V>( btree, revision, middle + 1 );
+            rightLeaf = new Leaf<>( btree, revision, middle + 1 );
+            rightLeaf.initId( transaction.getRecordManagerHeader() );
 
             int rightPos = pos - middle;
 
@@ -1119,36 +1349,34 @@ import org.apache.directory.mavibot.btre
             System.arraycopy( keys, middle, rightLeaf.keys, 0, rightPos );
 
             // Add the new element
-            rightLeaf.keys[rightPos] = new KeyHolderImpl<K>( btree.getKeySerializer(), key );
+            rightLeaf.keys[rightPos] = new KeyHolder<K>( btree.getKeySerializer(), key );
 
             // And copy the remaining elements
-            System.arraycopy( keys, pos, rightLeaf.keys, rightPos + 1, nbElems - pos );
+            System.arraycopy( keys, pos, rightLeaf.keys, rightPos + 1, nbPageElems - pos );
         }
 
         // Get the pivot
         K pivot = rightLeaf.keys[0].getKey();
 
         // Create the result
-        InsertResult<K, V> result = new SplitResult<K, V>( pivot, leftLeaf, rightLeaf );
-
-        return result;
+        return new SplitResult<>( pivot, leftLeaf, rightLeaf );
     }
 
 
     /**
      * {@inheritDoc}
      */
-    public KeyCursor<K> browseKeys( ReadTransaction<K, K> transaction, ParentPos<K, K>[] stack, int depth )
+    public KeyCursor<K> browseKeys( ReadTransaction transaction, ParentPos<K, K>[] stack, int depth )
     {
         int pos = 0;
-        KeyCursor<K> cursor = null;
+        KeyCursor<K> cursor;
 
-        if ( nbElems == 0 )
+        if ( nbPageElems == 0 )
         {
             // The tree is empty, it's the root, we have nothing to return
-            stack[depth] = new ParentPos<K, K>( null, -1 );
+            stack[depth] = new ParentPos<>( null, -1 );
 
-            return new KeyCursor<K>( transaction, stack, depth );
+            return new KeyCursor<>( transaction, stack, depth );
         }
         else
         {
@@ -1157,7 +1385,7 @@ import org.apache.directory.mavibot.btre
 
             stack[depth] = parentPos;
 
-            cursor = new KeyCursor<K>( transaction, stack, depth );
+            cursor = new KeyCursor<>( transaction, stack, depth );
         }
 
         return cursor;
@@ -1175,19 +1403,65 @@ import org.apache.directory.mavibot.btre
 
 
     /**
+     * @return the values
+     */
+    /* no qualifier */ValueHolder<V>[] getValues()
+    {
+        return values;
+    }
+
+
+    /**
+     * @param values the values to set
+     */
+    /* no qualifier */void setValues( ValueHolder<V>[] values )
+    {
+        this.values = values;
+    }
+
+    
+    /**
      * {@inheritDoc}
      */
+    @Override
+    public String prettyPrint()
+    {
+        StringBuilder sb = new StringBuilder();
+        
+        sb.append( "{Leaf(" ).append( id ).append( ")@" );
+        
+        if ( offset == RecordManager.NO_PAGE )
+        {
+            sb.append( "---" );
+        }
+        else
+        {
+            sb.append( String.format( "0x%4X", offset ) );
+        }
+        
+        sb.append( ",<" );
+        sb.append( getName() ).append( ':' ).append( getRevision() );
+        sb.append( ">}" );
+
+        return sb.toString();
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
     public String dumpPage( String tabs )
     {
         StringBuilder sb = new StringBuilder();
 
         sb.append( tabs );
 
-        if ( nbElems > 0 )
+        if ( nbPageElems > 0 )
         {
             boolean isFirst = true;
 
-            for ( int i = 0; i < nbElems; i++ )
+            for ( int i = 0; i < nbPageElems; i++ )
             {
                 if ( isFirst )
                 {

Modified: directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/LevelInfo.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/LevelInfo.java?rev=1784232&r1=1784231&r2=1784232&view=diff
==============================================================================
--- directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/LevelInfo.java (original)
+++ directory/mavibot/branches/single-value/mavibot/src/main/java/org/apache/directory/mavibot/btree/LevelInfo.java Fri Feb 24 07:16:37 2017
@@ -82,7 +82,7 @@ public class LevelInfo<K, V>
     /**
      * @return the nbElems
      */
-    public int getNbElems()
+    public int getNbPageElems()
     {
         return nbElems;
     }
@@ -254,7 +254,7 @@ public class LevelInfo<K, V>
         sb.append( "\n    nbAddedElems      = " ).append( nbAddedElems );
         sb.append( "\n    currentPos        = " ).append( currentPos );
         sb.append( "\n    currentPage" );
-        sb.append( "\n        nbKeys : " ).append( currentPage.getNbElems() );
+        sb.append( "\n        nbKeys : " ).append( currentPage.getNbPageElems() );
 
         return sb.toString();
     }



Mime
View raw message