directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kayyag...@apache.org
Subject svn commit: r1597950 - in /directory/mavibot/trunk/mavibot/src: main/java/org/apache/directory/mavibot/btree/ test/java/org/apache/directory/mavibot/btree/
Date Wed, 28 May 2014 09:22:25 GMT
Author: kayyagari
Date: Wed May 28 09:22:24 2014
New Revision: 1597950

URL: http://svn.apache.org/r1597950
Log:
o avoid copying pages and incrementing revision when the key and value already exist (MAVIBOT-39)
o do not create value holders in sub-btrees (MAVIBOT-38)
o updated serialization code in RecordManager to handle the changes made to sub-btrees
o added a new cursor to browse keys of sub-btree
o added test for KeyCursor

Added:
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ExistsResult.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyCursor.java
    directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedSubBtreeKeyCursorTest.java
Modified:
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedNode.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ValueBTreeCursor.java

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java?rev=1597950&r1=1597949&r2=1597950&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java Wed May 28 09:22:24 2014
@@ -423,7 +423,11 @@ import org.apache.directory.mavibot.btre
         {
             InsertResult<K, V> result = insert( key, value, -1L );
 
-            if ( result instanceof ModifyResult )
+            if ( result instanceof ExistsResult )
+            {
+                existingValue = value;
+            }
+            else if ( result instanceof ModifyResult )
             {
                 existingValue = ( ( ModifyResult<K, V> ) result ).getModifiedValue();
             }
@@ -431,6 +435,7 @@ import org.apache.directory.mavibot.btre
             // Commit now if it's not a sub-btree
             if ( btreeType != BTreeTypeEnum.PERSISTED_SUB )
             {
+                //FIXME when result type is ExistsResult then we should avoid writing the headers
                 transactionManager.commit();
             }
     
@@ -998,6 +1003,37 @@ import org.apache.directory.mavibot.btre
 
 
     /**
+     * {@inheritDoc}
+     */
+    public KeyCursor<K> browseKeys() throws IOException, KeyNotFoundException
+    {
+        // Check that we have a TransactionManager
+        if ( transactionManager == null )
+        {
+            throw new BTreeCreationException( "We don't have a Transaction Manager" );
+        }
+        
+        ReadTransaction transaction = beginReadTransaction();
+
+        if ( transaction == null )
+        {
+            return new KeyCursor<K>();
+        }
+        else
+        {
+            ParentPos<K, K>[] stack = (ParentPos<K, K>[]) Array.newInstance( ParentPos.class, 32 );
+
+            KeyCursor<K> cursor = getRootPage().browseKeys( transaction, stack, 0 );
+
+            // Set the position before the first element
+            cursor.beforeFirst();
+
+            return cursor;
+        }
+    }
+
+    
+    /**
      * Create a thread that is responsible of cleaning the transactions when
      * they hit the timeout
      */

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java?rev=1597950&r1=1597949&r2=1597950&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java Wed May 28 09:22:24 2014
@@ -314,6 +314,20 @@ import org.apache.directory.mavibot.btre
 
 
     /**
+     * {@inheritDoc}
+     */
+    public KeyCursor<K> browseKeys( ReadTransaction<K, K> transaction, ParentPos<K, K>[] stack, int depth )
+        throws IOException
+    {
+        stack[depth++] = new ParentPos( this, 0 );
+
+        Page<K, V> page = children[0].getValue();
+
+        return page.browseKeys( transaction, stack, depth );
+    }
+
+    
+    /**
      * Selects the sibling (the previous or next page with the same parent) which has
      * the more element assuming it's above N/2
      *

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java?rev=1597950&r1=1597949&r2=1597950&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java Wed May 28 09:22:24 2014
@@ -257,6 +257,15 @@ public interface BTree<K, V>
 
 
     /**
+     * Creates a cursor starting at the beginning of the tree
+     *
+     * @return A cursor on the B-tree keys
+     * @throws IOException
+     */
+    KeyCursor<K> browseKeys() throws IOException, KeyNotFoundException;
+
+    
+    /**
      * @return the comparator
      */
     Comparator<K> getComparator();

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ExistsResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ExistsResult.java?rev=1597950&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ExistsResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ExistsResult.java Wed May 28 09:22:24 2014
@@ -0,0 +1,32 @@
+/*
+ *   Licensed to the Apache Software Foundation (ASF) under one
+ *   or more contributor license agreements.  See the NOTICE file
+ *   distributed with this work for additional information
+ *   regarding copyright ownership.  The ASF licenses this file
+ *   to you under the Apache License, Version 2.0 (the
+ *   "License"); you may not use this file except in compliance
+ *   with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *   Unless required by applicable law or agreed to in writing,
+ *   software distributed under the License is distributed on an
+ *   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *   KIND, either express or implied.  See the License for the
+ *   specific language governing permissions and limitations
+ *   under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree;
+
+/**
+ * The result of an insert operation, returned when the given <key,value> tuple 
+ * already exists in the btree that doesn't support duplicates, or while inserting
+ * a <key, null> in a sub-btree that is used to hold the values of a key. 
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+/* No qualifier*/ class ExistsResult<K, V> extends AbstractResult<K, V> implements InsertResult<K, V>
+{
+    public static final ExistsResult EXISTS = new ExistsResult();
+}

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java?rev=1597950&r1=1597949&r2=1597950&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java Wed May 28 09:22:24 2014
@@ -681,6 +681,35 @@ import org.apache.directory.mavibot.btre
 
 
     /**
+     * {@inheritDoc}
+     */
+    public KeyCursor<K> browseKeys( ReadTransaction<K, K> transaction, ParentPos<K, K>[] stack, int depth )
+    {
+        int pos = 0;
+        KeyCursor<K> cursor = null;
+
+        if ( nbElems == 0 )
+        {
+            // The tree is empty, it's the root, we have nothing to return
+            stack[depth] = new ParentPos<K, K>( null, -1 );
+
+            return new KeyCursor<K>( transaction, stack, depth );
+        }
+        else
+        {
+            // Start at the beginning of the page
+            ParentPos<K, K> parentPos = new ParentPos( this, pos );
+
+            stack[depth] = parentPos;
+
+            cursor = new KeyCursor<K>( transaction, stack, depth );
+        }
+
+        return cursor;
+    }
+
+    
+    /**
      * Copy the current page and all of the keys, values and children, if it's not a leaf.
      *
      * @param revision The new revision

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyCursor.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyCursor.java?rev=1597950&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyCursor.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyCursor.java Wed May 28 09:22:24 2014
@@ -0,0 +1,777 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree;
+
+
+import java.io.IOException;
+import java.util.NoSuchElementException;
+
+import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
+
+
+/**
+ * A Cursor is used to fetch only keys in a BTree and is returned by the
+ * @see BTree#browseKeys method. The cursor <strng>must</strong> be closed
+ * when the user is done with it.
+ * <p>
+ *
+ * @param <K> The type for the Key
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class KeyCursor<K>
+{
+    /** A marker to tell that we are before the first element */
+    private static final int BEFORE_FIRST = -1;
+
+    /** A marker to tell that we are after the last element */
+    private static final int AFTER_LAST = -2;
+
+    /** The stack of pages from the root down to the leaf */
+    protected ParentPos<K, K>[] stack;
+
+    /** The stack's depth */
+    protected int depth = 0;
+
+    /** The transaction used for this cursor */
+    protected ReadTransaction<K, K> transaction;
+
+
+    /**
+     * Creates a new instance of Cursor.
+     */
+    protected KeyCursor()
+    {
+    }
+
+
+    /**
+     * Creates a new instance of Cursor, starting on a page at a given position.
+     *
+     * @param transaction The transaction this operation is protected by
+     * @param stack The stack of parent's from root to this page
+     */
+    public KeyCursor( ReadTransaction<K, K> transaction, ParentPos<K, K>[] stack, int depth )
+    {
+        this.transaction = transaction;
+        this.stack = stack;
+        this.depth = depth;
+    }
+
+
+    /**
+     * Change the position in the current cursor to set it after the last key
+     */
+    public void afterLast() throws IOException
+    {
+        // First check that we have elements in the BTree
+        if ( ( stack == null ) || ( stack.length == 0 ) )
+        {
+            return;
+        }
+
+        Page<K, K> child = null;
+
+        for ( int i = 0; i < depth; i++ )
+        {
+            ParentPos<K, K> parentPos = stack[i];
+
+            if ( child != null )
+            {
+                parentPos.page = child;
+                parentPos.pos = child.getNbElems();
+            }
+            else
+            {
+                // We have N+1 children if the page is a Node, so we don't decrement the nbElems field
+                parentPos.pos = parentPos.page.getNbElems();
+            }
+
+            child = ( ( AbstractPage<K, K> ) parentPos.page ).getPage( parentPos.pos );
+        }
+
+        // and leaf
+        ParentPos<K, K> parentPos = stack[depth];
+
+        if ( child == null )
+        {
+            parentPos.pos = parentPos.page.getNbElems() - 1;
+        }
+        else
+        {
+            parentPos.page = child;
+            parentPos.pos = child.getNbElems() - 1;
+        }
+
+        parentPos.pos = AFTER_LAST;
+    }
+
+
+    /**
+     * Change the position in the current cursor before the first key
+     */
+    public void beforeFirst() throws IOException
+    {
+        // First check that we have elements in the BTree
+        if ( ( stack == null ) || ( stack.length == 0 ) )
+        {
+            return;
+        }
+
+        Page<K, K> child = null;
+
+        for ( int i = 0; i < depth; i++ )
+        {
+            ParentPos<K, K> parentPos = stack[i];
+            parentPos.pos = 0;
+
+            if ( child != null )
+            {
+                parentPos.page = child;
+            }
+
+            child = ( ( AbstractPage<K, K> ) parentPos.page ).getPage( 0 );
+        }
+
+        // and leaf
+        ParentPos<K, K> parentPos = stack[depth];
+        parentPos.pos = BEFORE_FIRST;
+
+        if ( child != null )
+        {
+            parentPos.page = child;
+        }
+    }
+
+
+    /**
+     * 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
+    {
+        // First check that we have elements in the BTree
+        if ( ( stack == null ) || ( stack.length == 0 ) )
+        {
+            return false;
+        }
+
+        // Take the leaf and check if we have no mare keys
+        ParentPos<K, K> parentPos = stack[depth];
+
+        if ( parentPos.page == null )
+        {
+            // Empty BTree, get out
+            return false;
+        }
+
+        if ( parentPos.pos == AFTER_LAST )
+        {
+            return false;
+        }
+
+        if ( parentPos.pos == BEFORE_FIRST )
+        {
+            return true;
+        }
+
+        if ( parentPos.pos < parentPos.page.getNbElems() - 1 )
+        {
+            // Not the last position, we have a next key
+            return true;
+        }
+        else
+        {
+            // Ok, here, we have reached the last key in the leaf. We have to go up and
+            // see if we have some remaining keys
+            int currentDepth = depth - 1;
+
+            while ( currentDepth >= 0 )
+            {
+                parentPos = stack[currentDepth];
+
+                if ( parentPos.pos < parentPos.page.getNbElems() )
+                {
+                    // The parent has some remaining keys on the right, get out
+                    return true;
+                }
+                else
+                {
+                    currentDepth--;
+                }
+            }
+
+            // We are done, there are no more key left
+            return false;
+        }
+    }
+
+
+    /**
+     * Find the next key
+     *
+     * @return the found key
+     * @throws IOException
+     * @throws EndOfFileExceededException
+     */
+    public K next() throws EndOfFileExceededException, IOException
+    {
+        // First check that we have elements in the BTree
+        if ( ( stack == null ) || ( stack.length == 0 ) )
+        {
+            throw new NoSuchElementException( "No Key is present" );
+        }
+
+        ParentPos<K, K> parentPos = stack[depth];
+
+        if ( ( parentPos.page == null ) || ( parentPos.pos == AFTER_LAST ) )
+        {
+            // This is the end : no more keys
+            throw new NoSuchElementException( "No more keys present" );
+        }
+
+        if ( parentPos.pos == parentPos.page.getNbElems() )
+        {
+            // End of the leaf. We have to go back into the stack up to the
+            // parent, and down to the leaf
+            parentPos = findNextParentPos();
+
+            // we also need to check for the type of page cause
+            // findNextParentPos will never return a null ParentPos
+            if ( ( parentPos == null ) || ( parentPos.page == null ) )
+            {
+                // This is the end : no more keys
+                throw new NoSuchElementException( "No more keys present" );
+            }
+        }
+
+        // Deal with the BeforeFirst case
+        if ( parentPos.pos == BEFORE_FIRST )
+        {
+            parentPos.pos++;
+        }
+        else
+        {
+            if ( parentPos.pos == parentPos.page.getNbElems() - 1 )
+            {
+                parentPos = findNextParentPos();
+                
+                if ( ( parentPos == null ) || ( parentPos.page == null ) )
+                {
+                    // This is the end : no more keys
+                    throw new NoSuchElementException( "No more keys present" );
+                }
+            }
+            else
+            {
+                parentPos.pos++;
+            }
+        }
+        
+        AbstractPage<K, K> leaf = ( AbstractPage<K, K> ) ( parentPos.page );
+
+        return leaf.getKey( parentPos.pos );
+    }
+
+
+    /**
+     * Get the next key.
+     */
+    public K nextKey() throws EndOfFileExceededException, IOException
+    {
+        return next();
+    }
+
+
+    /**
+     * 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
+    {
+        // 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, K> 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
+            return hasNextParentPos();
+        }
+        else
+        {
+            return true;
+        }
+    }
+
+
+    /**
+     * 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
+    {
+        // First check that we have elements in the BTree
+        if ( ( stack == null ) || ( stack.length == 0 ) )
+        {
+            return false;
+        }
+
+        // Take the leaf and check if we have no mare keys
+        ParentPos<K, K> parentPos = stack[depth];
+
+        if ( parentPos.page == null )
+        {
+            // Empty BTree, get out
+            return false;
+        }
+
+        if ( parentPos.pos > 0 )
+        {
+            // get out, we have keys on the left
+            return true;
+        }
+        else
+        {
+            // Check that we are not before the first key
+            if ( parentPos.pos == BEFORE_FIRST )
+            {
+                return false;
+            }
+
+            if ( parentPos.pos == AFTER_LAST )
+            {
+                return true;
+            }
+
+            // Ok, here, we have reached the first key in the leaf. We have to go up and
+            // see if we have some remaining keys
+            int currentDepth = depth - 1;
+
+            while ( currentDepth >= 0 )
+            {
+                parentPos = stack[currentDepth];
+
+                if ( parentPos.pos > 0 )
+                {
+                    // The parent has some remaining keys on the right, get out
+                    return true;
+                }
+                else
+                {
+                    currentDepth--;
+                }
+            }
+
+            return false;
+        }
+    }
+
+
+    /**
+     * Find the previous key
+     *
+     * @return the found key
+     * @throws IOException
+     * @throws EndOfFileExceededException
+     */
+    public K prev() throws EndOfFileExceededException, IOException
+    {
+        // First check that we have elements in the BTree
+        if ( ( stack == null ) || ( stack.length == 0 ) )
+        {
+            throw new NoSuchElementException( "No more keys present" );
+        }
+
+        ParentPos<K, K> parentPos = stack[depth];
+
+        if ( ( parentPos.page == null ) || ( parentPos.pos == BEFORE_FIRST ) )
+        {
+            // This is the end : no more keys
+            throw new NoSuchElementException( "No more keys present" );
+        }
+
+        // Deal with the AfterLast case
+        if ( parentPos.pos == AFTER_LAST )
+        {
+            parentPos.pos = parentPos.page.getNbElems() - 1;
+        }
+        else
+        {
+            if ( parentPos.pos == 0 )
+            {
+                parentPos = findPrevParentPos();
+                
+                if ( ( parentPos == null ) || ( parentPos.page == null ) )
+                {
+                    // This is the end : no more keys
+                    throw new NoSuchElementException( "No more keys present" );
+                }
+            }
+            else
+            {
+                parentPos.pos--;
+            }
+        }
+
+        AbstractPage<K, K> leaf = ( AbstractPage<K, K> ) ( parentPos.page );
+
+        return leaf.getKey( parentPos.pos );
+    }
+
+
+    /**
+     * Get the previous key.
+     * 
+     * @return the found key
+     * @throws EndOfFileExceededException
+     * @throws IOException
+     */
+    public K prevKey() throws EndOfFileExceededException, IOException
+    {
+        return prev();
+    }
+
+
+    /**
+     * 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
+    {
+        // 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, K> parentPos = stack[depth];
+
+        if ( parentPos.page == null )
+        {
+            // This is the end : no more key
+            return false;
+        }
+
+        switch ( parentPos.pos )
+        {
+            case 0 :
+                // Beginning of the leaf. We have to go back into the stack up to the
+                // parent, and down to the leaf
+                return hasPrevParentPos();
+                
+            case -1 :
+                // no previous key
+                return false;
+                
+            default :
+                // we have a previous key
+                return true;
+        }
+    }
+
+
+    /**
+     * Tells if there is a next ParentPos
+     *
+     * @return the new ParentPos instance, or null if we have no following leaf
+     * @throws IOException
+     * @throws EndOfFileExceededException
+     */
+    private boolean hasNextParentPos() throws EndOfFileExceededException, IOException
+    {
+        if ( depth == 0 )
+        {
+            // No need to go any further, there is only one leaf in the btree
+            return false;
+        }
+
+        int currentDepth = depth - 1;
+        Page<K, K> child = null;
+
+        // First, go up the tree until we find a Node which has some element on the right
+        while ( currentDepth >= 0 )
+        {
+            // We first go up the tree, until we reach a page whose current position
+            // is not the last one
+            ParentPos<K, K> parentPos = stack[currentDepth];
+
+            if ( parentPos.pos + 1 > parentPos.page.getNbElems() )
+            {
+                // No more element on the right : go up
+                currentDepth--;
+            }
+            else
+            {
+                // We can pick the next element at this level
+                child = ( ( AbstractPage<K, K> ) parentPos.page ).getPage( parentPos.pos + 1 );
+
+                // and go down the tree through the nodes
+                while ( currentDepth < depth - 1 )
+                {
+                    currentDepth++;
+                    child = ( ( AbstractPage<K, K> ) child ).getPage( 0 );
+                }
+
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+
+    /**
+     * Find the leaf containing the following elements.
+     *
+     * @return the new ParentPos instance, or null if we have no following leaf
+     * @throws IOException
+     * @throws EndOfFileExceededException
+     */
+    private ParentPos<K, K> findNextParentPos() throws EndOfFileExceededException, IOException
+    {
+        if ( depth == 0 )
+        {
+            // No need to go any further, there is only one leaf in the btree
+            return null;
+        }
+
+        int currentDepth = depth - 1;
+        Page<K, K> child = null;
+
+        // First, go up the tree until we find a Node which has some element on the right
+        while ( currentDepth >= 0 )
+        {
+            // We first go up the tree, until we reach a page whose current position
+            // is not the last one
+            ParentPos<K, K> parentPos = stack[currentDepth];
+
+            if ( parentPos.pos + 1 > parentPos.page.getNbElems() )
+            {
+                // No more element on the right : go up
+                currentDepth--;
+            }
+            else
+            {
+                // We can pick the next element at this level
+                parentPos.pos++;
+                child = ( ( AbstractPage<K, K> ) parentPos.page ).getPage( parentPos.pos );
+
+                // and go down the tree through the nodes
+                while ( currentDepth < depth - 1 )
+                {
+                    currentDepth++;
+                    parentPos = stack[currentDepth];
+                    parentPos.pos = 0;
+                    parentPos.page = child;
+                    child = ( ( AbstractPage<K, K> ) child ).getPage( 0 );
+                }
+
+                // and the leaf
+                parentPos = stack[depth];
+                parentPos.page = child;
+                parentPos.pos = 0;
+
+                return parentPos;
+            }
+        }
+
+        return null;
+    }
+
+
+    /**
+     * Find the leaf containing the previous elements.
+     *
+     * @return the new ParentPos instance, or null if we have no previous leaf
+     * @throws IOException
+     * @throws EndOfFileExceededException
+     */
+    private ParentPos<K, K> findPrevParentPos() throws EndOfFileExceededException, IOException
+    {
+        if ( depth == 0 )
+        {
+            // No need to go any further, there is only one leaf in the btree
+            return null;
+        }
+
+        int currentDepth = depth - 1;
+        Page<K, K> child = null;
+
+        // First, go up the tree until we find a Node which has some element on the left
+        while ( currentDepth >= 0 )
+        {
+            // We first go up the tree, until we reach a page whose current position
+            // is not the last one
+            ParentPos<K, K> parentPos = stack[currentDepth];
+
+            if ( parentPos.pos == 0 )
+            {
+                // No more element on the right : go up
+                currentDepth--;
+            }
+            else
+            {
+                // We can pick the next element at this level
+                parentPos.pos--;
+                child = ( ( AbstractPage<K, K> ) parentPos.page ).getPage( parentPos.pos );
+
+                // and go down the tree through the nodes
+                while ( currentDepth < depth - 1 )
+                {
+                    currentDepth++;
+                    parentPos = stack[currentDepth];
+                    parentPos.pos = child.getNbElems();
+                    parentPos.page = child;
+                    child = ( ( AbstractPage<K, K> ) parentPos.page ).getPage( parentPos.page.getNbElems() );
+                }
+
+                // and the leaf
+                parentPos = stack[depth];
+                parentPos.pos = child.getNbElems() - 1;
+                parentPos.page = child;
+
+                return parentPos;
+            }
+        }
+
+        return null;
+    }
+
+
+    /**
+     * Tells if there is a prev ParentPos
+     *
+     * @return the new ParentPos instance, or null if we have no previous leaf
+     * @throws IOException
+     * @throws EndOfFileExceededException
+     */
+    private boolean hasPrevParentPos() throws EndOfFileExceededException, IOException
+    {
+        if ( depth == 0 )
+        {
+            // No need to go any further, there is only one leaf in the btree
+            return false;
+        }
+
+        int currentDepth = depth - 1;
+        Page<K, K> child = null;
+
+        // First, go up the tree until we find a Node which has some element on the right
+        while ( currentDepth >= 0 )
+        {
+            // We first go up the tree, until we reach a page whose current position
+            // is not the last one
+            ParentPos<K, K> parentPos = stack[currentDepth];
+
+            if ( parentPos.pos == 0 )
+            {
+                // No more element on the left : go up
+                currentDepth--;
+            }
+            else
+            {
+                // We can pick the previous element at this level
+                child = ( ( AbstractPage<K, K> ) parentPos.page ).getPage( parentPos.pos - 1 );
+
+                // and go down the tree through the nodes
+                while ( currentDepth < depth - 1 )
+                {
+                    currentDepth++;
+                    child = ( ( AbstractPage<K, K> ) child ).getPage( child.getNbElems() );
+                }
+
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void close()
+    {
+        transaction.close();
+    }
+
+
+    /**
+     * Get the creation date
+     * @return The creation date for this cursor
+     */
+    public long getCreationDate()
+    {
+        return transaction.getCreationDate();
+    }
+
+
+    /**
+     * Get the current revision
+     *
+     * @return The revision this cursor is based on
+     */
+    public long getRevision()
+    {
+        return transaction.getRevision();
+    }
+
+
+    public String toString()
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( "KeyCursor, depth = " ).append( depth ).append( "\n" );
+
+        for ( int i = 0; i <= depth; i++ )
+        {
+            sb.append( "    " ).append( stack[i] ).append( "\n" );
+        }
+
+        return sb.toString();
+    }
+}

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java?rev=1597950&r1=1597949&r2=1597950&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java Wed May 28 09:22:24 2014
@@ -149,6 +149,18 @@ import org.apache.directory.mavibot.btre
 
 
     /**
+     * Browses the keys of whole tree, and creates a Cursor on top of it.
+     *
+     * @param transaction The started transaction for this operation
+     * @param stack The stack of parents we go through to get to this page
+     * @return A Cursor to browse the keys
+     * @throws IOException If we have an error while trying to access the page
+     */
+    KeyCursor<K> browseKeys( ReadTransaction<K, K> transaction, ParentPos<K, K>[] stack, int depth )
+        throws EndOfFileExceededException, IOException;
+
+    
+    /**
      * @return the revision
      */
     long getRevision();

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java?rev=1597950&r1=1597949&r2=1597950&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java Wed May 28 09:22:24 2014
@@ -523,6 +523,11 @@ public class PersistedBTree<K, V> extend
         BTreeHeader<K, V> btreeHeader = getBTreeHeader( getName() );
         InsertResult<K, V> result = btreeHeader.getRootPage().insert( key, value, revision );
 
+        if ( result instanceof ExistsResult )
+        {
+            return result;
+        }
+
         // Create a new BTreeHeader
         BTreeHeader<K, V> newBtreeHeader = btreeHeader.copy();
 

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java?rev=1597950&r1=1597949&r2=1597950&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java Wed May 28 09:22:24 2014
@@ -26,7 +26,7 @@ import java.lang.reflect.Array;
 import org.apache.directory.mavibot.btree.exception.DuplicateValueNotAllowedException;
 import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
 import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
-
+import static org.apache.directory.mavibot.btree.BTreeTypeEnum.*;
 
 /**
  * A MVCC Leaf. It stores the keys and values. It does not have any children.
@@ -64,7 +64,10 @@ import org.apache.directory.mavibot.btre
     PersistedLeaf( BTree<K, V> btree, long revision, int nbElems )
     {
         super( btree, revision, nbElems );
-        values = ( ValueHolder<V>[] ) Array.newInstance( PersistedValueHolder.class, nbElems );
+        if( btree.getType() != BTreeTypeEnum.PERSISTED_SUB )
+        {
+            values = ( ValueHolder<V>[] ) Array.newInstance( PersistedValueHolder.class, nbElems );
+        }
     }
 
 
@@ -76,12 +79,19 @@ import org.apache.directory.mavibot.btre
         // Find the key into this leaf
         int pos = findPos( key );
 
+        boolean isSubTree = ( btree.getType() == PERSISTED_SUB );
+
         if ( pos < 0 )
         {
             // 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 );
 
+            if( isSubTree )
+            {
+                return ExistsResult.EXISTS;
+            }
+            
             // Replace the existing value in a copy of the current page
             InsertResult<K, V> result = replaceElement( revision, key, value, index );
 
@@ -93,7 +103,16 @@ import org.apache.directory.mavibot.btre
         {
             // 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 = addElement( revision, key, value, pos );
+            Page<K, V> modifiedPage = null;
+            
+            if ( isSubTree )
+            {
+                modifiedPage = addSubTreeElement( revision, key, pos );
+            }
+            else
+            {
+                modifiedPage = addElement( revision, key, value, pos );
+            }
 
             InsertResult<K, V> result = new ModifyResult<K, V>( modifiedPage, null );
             result.addCopiedPage( this );
@@ -104,7 +123,17 @@ import org.apache.directory.mavibot.btre
         {
             // The Page is already full : we split it and return the overflow element,
             // after having created two pages.
-            InsertResult<K, V> result = addAndSplit( revision, key, value, pos );
+            InsertResult<K, V> result = null;
+            
+            if( isSubTree )
+            {
+                result = addAndSplitSubTree( revision, key, pos );
+            }
+            else
+            {
+                result = addAndSplit( revision, key, value, pos );
+            }
+            
             result.addCopiedPage( this );
 
             return result;
@@ -143,7 +172,18 @@ import org.apache.directory.mavibot.btre
 
         int index = -( pos + 1 );
 
-        ValueHolder<V> valueHolder = values[index];
+        boolean isNotSubTree = ( btree.getType() != PERSISTED_SUB );
+
+        ValueHolder<V> valueHolder = null;
+        
+        if( isNotSubTree )
+        {
+            valueHolder = values[index];
+        }
+        else // set value to null, just incase if a non-null value passed while deleting a key from from sub-btree
+        {
+            value = null;
+        }
 
         if ( value == null )
         {
@@ -265,8 +305,7 @@ import org.apache.directory.mavibot.btre
             }
             catch ( CloneNotSupportedException e )
             {
-                // TODO Auto-generated catch block
-                e.printStackTrace();
+                throw new RuntimeException( e );
             }
 
             // The current page is added in the copied page list
@@ -292,6 +331,8 @@ import org.apache.directory.mavibot.btre
         boolean isLeft, int pos )
         throws EndOfFileExceededException, IOException
     {
+        boolean isNotSubTree = ( btree.getType() != PERSISTED_SUB );
+        
         // 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
         PersistedLeaf<K, V> newLeaf = new PersistedLeaf<K, V>( btree, revision, btree.getPageSize() - 1 );
@@ -301,30 +342,48 @@ import org.apache.directory.mavibot.btre
             // 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 );
+            if ( isNotSubTree )
+            {
+                System.arraycopy( sibling.values, 0, newLeaf.values, 0, sibling.nbElems );
+            }
 
             // 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 );
+            if ( isNotSubTree )
+            {
+                System.arraycopy( values, 0, newLeaf.values, sibling.nbElems, 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 );
+            if ( isNotSubTree )
+            {
+                System.arraycopy( values, pos + 1, newLeaf.values, sibling.nbElems + pos, nbElems - pos - 1 );
+            }
         }
         else
         {
             // The sibling is on the right
             // Copy all the elements from the page up to the deletion position
             System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
-            System.arraycopy( values, 0, newLeaf.values, 0, pos );
+            if ( isNotSubTree )
+            {
+                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 );
+            if ( isNotSubTree )
+            {
+                System.arraycopy( values, pos + 1, newLeaf.values, pos, nbElems - 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 );
+            if ( isNotSubTree )
+            {
+                System.arraycopy( sibling.values, 0, newLeaf.values, nbElems - 1, sibling.nbElems );
+            }
         }
 
         // And create the result
@@ -352,9 +411,15 @@ import org.apache.directory.mavibot.btre
         int pos )
         throws IOException
     {
+        boolean isNotSubTree = ( btree.getType() != PERSISTED_SUB );
+        
         // The sibling is on the left, borrow the rightmost element
         K siblingKey = sibling.keys[sibling.getNbElems() - 1].getKey();
-        ValueHolder<V> siblingValue = sibling.values[sibling.getNbElems() - 1];
+        ValueHolder<V> siblingValue = null;
+        if ( isNotSubTree )
+        {
+            siblingValue = sibling.values[sibling.getNbElems() - 1];
+        }
 
         // Create the new sibling, with one less element at the end
         PersistedLeaf<K, V> newSibling = ( PersistedLeaf<K, V> ) sibling.copy( revision, sibling.getNbElems() - 1 );
@@ -365,15 +430,24 @@ import org.apache.directory.mavibot.btre
 
         // Insert the borrowed element
         newLeaf.keys[0] = new PersistedKeyHolder<K>( btree.getKeySerializer(), siblingKey );
-        newLeaf.values[0] = siblingValue;
+        if ( isNotSubTree )
+        {
+            newLeaf.values[0] = siblingValue;
+        }
 
         // Copy the keys and the values up to the insertion position,
         System.arraycopy( keys, 0, newLeaf.keys, 1, pos );
-        System.arraycopy( values, 0, newLeaf.values, 1, pos );
+        if ( isNotSubTree )
+        {
+            System.arraycopy( values, 0, newLeaf.values, 1, pos );
+        }
 
         // And copy the remaining elements
         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 );
+        if( isNotSubTree )
+        {
+            System.arraycopy( values, pos + 1, newLeaf.values, pos + 1, values.length - pos - 1 );
+        }
 
         DeleteResult<K, V> result = new BorrowedFromLeftResult<K, V>( newLeaf, newSibling, removedElement );
 
@@ -400,33 +474,51 @@ import org.apache.directory.mavibot.btre
         int pos )
         throws IOException
     {
+        boolean isNotSubTree = ( btree.getType() != PERSISTED_SUB );
+        
         // The sibling is on the left, borrow the rightmost element
         K siblingKey = sibling.keys[0].getKey();
-        ValueHolder<V> siblingHolder = sibling.values[0];
+        ValueHolder<V> siblingHolder = null;
+        if ( isNotSubTree )
+        {
+            siblingHolder = sibling.values[0];
+        }
 
         // Create the new sibling
         PersistedLeaf<K, V> newSibling = new PersistedLeaf<K, V>( btree, revision, sibling.getNbElems() - 1 );
 
         // 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 );
-
+        if ( isNotSubTree )
+        {
+            System.arraycopy( sibling.values, 1, newSibling.values, 0, sibling.nbElems - 1 );
+        }
+        
         // Create the new page and add the new element at the end
         // First copy the current page, with the same size
         PersistedLeaf<K, V> newLeaf = new PersistedLeaf<K, V>( btree, revision, nbElems );
 
         // Insert the borrowed element at the end
         newLeaf.keys[nbElems - 1] = new PersistedKeyHolder<K>( btree.getKeySerializer(), siblingKey );
-        newLeaf.values[nbElems - 1] = siblingHolder;
-
+        if ( isNotSubTree )
+        {
+            newLeaf.values[nbElems - 1] = siblingHolder;
+        }
+        
         // Copy the keys and the values up to the deletion position,
         System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
-        System.arraycopy( values, 0, newLeaf.values, 0, pos );
-
+        if ( isNotSubTree )
+        {
+            System.arraycopy( values, 0, newLeaf.values, 0, pos );
+        }
+        
         // And copy the remaining elements
         System.arraycopy( keys, pos + 1, newLeaf.keys, pos, keys.length - pos - 1 );
-        System.arraycopy( values, pos + 1, newLeaf.values, pos, values.length - pos - 1 );
-
+        if ( isNotSubTree )
+        {
+            System.arraycopy( values, pos + 1, newLeaf.values, pos, values.length - pos - 1 );
+        }
+        
         DeleteResult<K, V> result = new BorrowedFromRightResult<K, V>( newLeaf, newSibling, removedElement );
 
         // Add the copied pages to the list
@@ -448,6 +540,8 @@ import org.apache.directory.mavibot.btre
     private void copyAfterRemovingElement( boolean keyRemoved, V removedValue, PersistedLeaf<K, V> newLeaf, int pos )
         throws IOException
     {
+        boolean isNotSubTree = ( btree.getType() != PERSISTED_SUB );
+        
         if ( keyRemoved )
         {
             // Deal with the special case of a page with only one element by skipping
@@ -459,11 +553,17 @@ import org.apache.directory.mavibot.btre
 
             // Copy the keys and the values up to the insertion position
             System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
-            System.arraycopy( values, 0, newLeaf.values, 0, pos );
+            if ( isNotSubTree )
+            {
+                System.arraycopy( values, 0, newLeaf.values, 0, pos );
+            }
 
             // And copy the elements after the position
             System.arraycopy( keys, pos + 1, newLeaf.keys, pos, keys.length - pos - 1 );
-            System.arraycopy( values, pos + 1, newLeaf.values, pos, values.length - pos - 1 );
+            if ( isNotSubTree )
+            {
+                System.arraycopy( values, pos + 1, newLeaf.values, pos, values.length - pos - 1 );
+            }
         }
         else
         // one of the many values of the same key was removed, no change in the number of keys
@@ -797,6 +897,11 @@ import org.apache.directory.mavibot.btre
             throw new DuplicateValueNotAllowedException( "Duplicate values are not allowed" );
         }
 
+        if ( valueExists )
+        {
+            return ExistsResult.EXISTS;
+        }
+        
         if ( this.revision != revision )
         {
             // The page hasn't been modified yet, we need to copy it first
@@ -814,11 +919,12 @@ import org.apache.directory.mavibot.btre
         }
         else
         {
+            // this block should be deleted after fixing MAVIBOT-39
             // As strange as it sounds, we need to remove the value to reinject it.
             // There are cases where the value retrieval just use one part of the
             // value only (typically for LDAP Entries, where we use the DN)
-            replacedValue = valueHolder.remove( value );
-            valueHolder.add( value );
+            //replacedValue = valueHolder.remove( value );
+            //valueHolder.add( value );
         }
 
         // Create the result
@@ -967,6 +1073,11 @@ import org.apache.directory.mavibot.btre
      */
     public K getLeftMostKey()
     {
+        if( keys.length == 0 )
+        {
+            System.out.println("");
+        }
+        
         return keys[0].getKey();
     }
 
@@ -1091,6 +1202,134 @@ 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 )
+    {
+        // First copy the current page, but add one element in the copied page
+        PersistedLeaf<K, V> newLeaf = new PersistedLeaf<K, V>( btree, revision, nbElems + 1 );
+
+        // Deal with the special case of an empty page
+        if ( nbElems == 0 )
+        {
+            newLeaf.keys[0] = new PersistedKeyHolder<K>( btree.getKeySerializer(), key );
+        }
+        else
+        {
+            // Copy the keys and the values up to the insertion position
+            System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
+
+            // Add the new element
+            newLeaf.keys[pos] = new PersistedKeyHolder<K>( btree.getKeySerializer(), key );
+
+            // And copy the remaining elements
+            System.arraycopy( keys, pos, newLeaf.keys, pos + 1, keys.length - pos );
+        }
+
+        return newLeaf;
+    }
+
+    
+    /**
+     * 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 )
+    {
+        int middle = btree.getPageSize() >> 1;
+        PersistedLeaf<K, V> leftLeaf = null;
+        PersistedLeaf<K, V> rightLeaf = null;
+
+        // Determinate where to store the new value
+        if ( pos <= middle )
+        {
+            // The left page will contain the new value
+            leftLeaf = new PersistedLeaf<K, V>( btree, revision, middle + 1 );
+
+            // 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 PersistedKeyHolder<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 PersistedLeaf<K, V>( btree, revision, middle );
+
+            // Copy the keys and the values in the right page
+            System.arraycopy( keys, middle, rightLeaf.keys, 0, middle );
+        }
+        else
+        {
+            // Create the left page
+            leftLeaf = new PersistedLeaf<K, V>( btree, revision, middle );
+
+            // Copy all the element into the left page
+            System.arraycopy( keys, 0, leftLeaf.keys, 0, middle );
+
+            // Now, create the right page
+            rightLeaf = new PersistedLeaf<K, V>( btree, revision, middle + 1 );
+
+            int rightPos = pos - middle;
+
+            // Copy the keys and the values up to the insertion position
+            System.arraycopy( keys, middle, rightLeaf.keys, 0, rightPos );
+
+            // Add the new element
+            rightLeaf.keys[rightPos] = new PersistedKeyHolder<K>( btree.getKeySerializer(), key );
+
+            // And copy the remaining elements
+            System.arraycopy( keys, pos, rightLeaf.keys, rightPos + 1, nbElems - pos );
+        }
+
+        // Get the pivot
+        K pivot = rightLeaf.keys[0].getKey();
+
+        if ( pivot == null )
+        {
+            pivot = rightLeaf.keys[0].getKey();
+        }
+
+        // Create the result
+        InsertResult<K, V> result = new SplitResult<K, V>( pivot, leftLeaf, rightLeaf );
+
+        return result;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public KeyCursor<K> browseKeys( ReadTransaction<K, K> transaction, ParentPos<K, K>[] stack, int depth )
+    {
+        int pos = 0;
+        KeyCursor<K> cursor = null;
+
+        if ( nbElems == 0 )
+        {
+            // The tree is empty, it's the root, we have nothing to return
+            stack[depth] = new ParentPos<K, K>( null, -1 );
+
+            return new KeyCursor<K>( transaction, stack, depth );
+        }
+        else
+        {
+            // Start at the beginning of the page
+            ParentPos<K, K> parentPos = new ParentPos( this, pos );
+
+            stack[depth] = parentPos;
+
+            cursor = new KeyCursor<K>( transaction, stack, depth );
+        }
+
+        return cursor;
+    }
+
+    
+    /**
      * {@inheritDoc}
      */
     public String dumpPage( String tabs )

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedNode.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedNode.java?rev=1597950&r1=1597949&r2=1597950&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedNode.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedNode.java Wed May 28 09:22:24 2014
@@ -140,7 +140,11 @@ import java.util.List;
 
         // Ok, now, we have injected the <K, V> tuple down the tree. Let's check
         // the result to see if we have to split the current page
-        if ( result instanceof ModifyResult )
+        if ( result instanceof ExistsResult )
+        {
+            return result;
+        }
+        else if ( result instanceof ModifyResult )
         {
             // The child has been modified.
             return replaceChild( revision, ( ModifyResult<K, V> ) result, pos );

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java?rev=1597950&r1=1597949&r2=1597950&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java Wed May 28 09:22:24 2014
@@ -1042,37 +1042,42 @@ public class RecordManager extends Abstr
         int[] keyLengths = new int[nbElems];
         int[] valueLengths = new int[nbElems];
 
+        boolean isNotSubTree = ( btree.getType() != BTreeTypeEnum.PERSISTED_SUB );
+        
         // Read each key and value
         for ( int i = 0; i < nbElems; i++ )
         {
-            // Read the number of values
-            int nbValues = byteBuffer.getInt();
-            PersistedValueHolder<V> valueHolder = null;
-
-            if ( nbValues < 0 )
-            {
-                // This is a sub-btree
-                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 PersistedValueHolder<V>( btree, 1 - nbValues, btreeOffsetBytes );
-            }
-            else
+            if ( isNotSubTree )
             {
-                // This is an array
-                // Read the value's array length
-                valueLengths[i] = byteBuffer.getInt();
-
-                // This is an Array of values, read the byte[] associated with it
-                byte[] arrayBytes = new byte[valueLengths[i]];
-                byteBuffer.get( arrayBytes );
-                valueHolder = new PersistedValueHolder<V>( btree, nbValues, arrayBytes );
+                // Read the number of values
+                int nbValues = byteBuffer.getInt();
+                PersistedValueHolder<V> valueHolder = null;
+                
+                if ( nbValues < 0 )
+                {
+                    // This is a sub-btree
+                    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 PersistedValueHolder<V>( btree, 1 - nbValues, btreeOffsetBytes );
+                }
+                else
+                {
+                    // This is an array
+                    // Read the value's array length
+                    valueLengths[i] = byteBuffer.getInt();
+                    
+                    // This is an Array of values, read the byte[] associated with it
+                    byte[] arrayBytes = new byte[valueLengths[i]];
+                    byteBuffer.get( arrayBytes );
+                    valueHolder = new PersistedValueHolder<V>( btree, nbValues, arrayBytes );
+                }
+                
+                BTreeFactory.setValue( btree, leaf, i, valueHolder );
             }
 
-            BTreeFactory.setValue( btree, leaf, i, valueHolder );
-
             keyLengths[i] = byteBuffer.getInt();
             byte[] data = new byte[keyLengths[i]];
             byteBuffer.get( data );
@@ -1498,6 +1503,8 @@ public class RecordManager extends Abstr
     {
         int nbElems = page.getNbElems();
 
+        boolean isNotSubTree = ( btree.getType() != BTreeTypeEnum.PERSISTED_SUB );
+        
         if ( nbElems == 0 )
         {
             return serializeRootPage( revision );
@@ -1549,7 +1556,11 @@ public class RecordManager extends Abstr
                 }
                 else
                 {
-                    dataSize += serializeLeafValue( ( PersistedLeaf<K, V> ) page, pos, serializedData );
+                    if ( isNotSubTree )
+                    {
+                        dataSize += serializeLeafValue( ( PersistedLeaf<K, V> ) page, pos, serializedData );
+                    }
+                    
                     dataSize += serializeLeafKey( ( PersistedLeaf<K, V> ) page, pos, serializedData );
                 }
             }

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ValueBTreeCursor.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ValueBTreeCursor.java?rev=1597950&r1=1597949&r2=1597950&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ValueBTreeCursor.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ValueBTreeCursor.java Wed May 28 09:22:24 2014
@@ -35,7 +35,7 @@ import org.apache.directory.mavibot.btre
 /* No qualifier */class ValueBTreeCursor<V> implements ValueCursor<V>
 {
     /** Store the current position in the array or in the BTree */
-    private TupleCursor<V, V> cursor;
+    private KeyCursor<V> cursor;
 
     /** The Value sub-btree */
     private BTree<V, V> valueBtree;
@@ -53,7 +53,7 @@ import org.apache.directory.mavibot.btre
         {
             if ( valueBtree != null )
             {
-                cursor = valueBtree.browse();
+                cursor = valueBtree.browseKeys();
             }
         }
         catch ( IOException e )
@@ -106,7 +106,7 @@ import org.apache.directory.mavibot.btre
     {
         try
         {
-            return cursor.next().getKey();
+            return cursor.next();
         }
         catch ( EndOfFileExceededException e )
         {
@@ -198,7 +198,7 @@ import org.apache.directory.mavibot.btre
     {
         try
         {
-            return cursor.prev().getKey();
+            return cursor.prev();
         }
         catch ( EndOfFileExceededException e )
         {

Added: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedSubBtreeKeyCursorTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedSubBtreeKeyCursorTest.java?rev=1597950&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedSubBtreeKeyCursorTest.java (added)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedSubBtreeKeyCursorTest.java Wed May 28 09:22:24 2014
@@ -0,0 +1,129 @@
+/*
+ *   Licensed to the Apache Software Foundation (ASF) under one
+ *   or more contributor license agreements.  See the NOTICE file
+ *   distributed with this work for additional information
+ *   regarding copyright ownership.  The ASF licenses this file
+ *   to you under the Apache License, Version 2.0 (the
+ *   "License"); you may not use this file except in compliance
+ *   with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *   Unless required by applicable law or agreed to in writing,
+ *   software distributed under the License is distributed on an
+ *   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *   KIND, either express or implied.  See the License for the
+ *   specific language governing permissions and limitations
+ *   under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import java.io.File;
+import java.io.IOException;
+import java.util.UUID;
+
+import org.apache.commons.io.FileUtils;
+import org.apache.directory.mavibot.btree.serializer.IntSerializer;
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.rules.TemporaryFolder;
+
+/**
+ * Tests for KeyCursor of a persisted sub-Btree.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class PersistedSubBtreeKeyCursorTest
+{
+    private BTree<Integer, Integer> btree = null;
+
+    private RecordManager recordManager = null;
+
+    @Rule
+    public TemporaryFolder tempFolder = new TemporaryFolder();
+
+    private File dataDir = null;
+
+
+    @Before
+    public void createBTree()
+    {
+        dataDir = tempFolder.newFolder( UUID.randomUUID().toString() );
+
+        // Now, try to reload the file back
+        recordManager = new RecordManager( dataDir.getAbsolutePath() );
+
+        try
+        {
+            PersistedBTreeConfiguration<Integer, Integer> configuration = new PersistedBTreeConfiguration<Integer, Integer>();
+            configuration.setAllowDuplicates( false );
+            configuration.setKeySerializer( IntSerializer.INSTANCE );
+            configuration.setValueSerializer( IntSerializer.INSTANCE );
+            configuration.setName( "sub-btree" );
+            configuration.setBtreeType( BTreeTypeEnum.PERSISTED_SUB );
+
+            btree = BTreeFactory.createPersistedBTree( configuration );
+
+            recordManager.manage( btree, RecordManager.INTERNAL_BTREE );
+        }
+        catch ( Exception e )
+        {
+            throw new RuntimeException( e );
+        }
+    }
+
+
+    @After
+    public void cleanup() throws IOException
+    {
+        dataDir = new File( System.getProperty( "java.io.tmpdir" ) + "/recordman" );
+
+        btree.close();
+
+        if ( dataDir.exists() )
+        {
+            FileUtils.deleteDirectory( dataDir );
+        }
+        
+        recordManager.close();
+        assertTrue( recordManager.isContextOk() );
+    }
+
+    @Test
+    public void testBrowseKeys() throws Exception
+    {
+        for( int i=0; i< 10; i++ )
+        {
+            // only the keys are stored, values are ignored
+            btree.insert( i, i );
+        }
+        
+        KeyCursor<Integer> cursor = btree.browseKeys();
+        
+        for( int i=0; i< 10; i++ )
+        {
+            assertTrue( cursor.hasNext() );
+            assertEquals( String.valueOf( i ), String.valueOf( cursor.next() ) );
+        }
+        
+        assertFalse( cursor.hasNext() );
+
+        cursor.afterLast();
+        
+        for( int i=9; i>= 0; i-- )
+        {
+            assertTrue( cursor.hasPrev() );
+            assertEquals( String.valueOf( i ), String.valueOf( cursor.prev() ) );
+        }
+
+        assertFalse( cursor.hasPrev() );
+        cursor.close();
+    }
+}



Mime
View raw message