directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1539986 - in /directory/mavibot/trunk/mavibot/src: main/java/org/apache/directory/mavibot/btree/managed/ test/java/org/apache/directory/mavibot/btree/managed/
Date Fri, 08 Nov 2013 11:37:27 GMT
Author: elecharny
Date: Fri Nov  8 11:37:27 2013
New Revision: 1539986

URL: http://svn.apache.org/r1539986
Log:
o Modified the way we handle the values when we have duplicates. We now use either an Array or  sub-btree
o Modified the cursor and the way it works (no more linkedList created, we use a direct array)

Added:
    directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/managed/ManagedBTreeBrowseTest.java
Modified:
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeFactory.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Leaf.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Node.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Page.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ParentPos.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/TupleCursorImpl.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ValueHolder.java
    directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/managed/RecordManagerFreePageTest.java

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java?rev=1539986&r1=1539985&r2=1539986&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java Fri Nov  8 11:37:27 2013
@@ -122,7 +122,6 @@ public class BTree<K, V> implements Clos
     /*No qualifier*/static int valueThresholdUp = DEFAULT_VALUE_THRESHOLD_UP;
     /*No qualifier*/static int valueThresholdLow = DEFAULT_VALUE_THRESHOLD_LOW;
 
-
     /**
      * Create a thread that is responsible of cleaning the transactions when
      * they hit the timeout
@@ -874,9 +873,7 @@ public class BTree<K, V> implements Clos
         Transaction<K, V> transaction = beginReadTransaction();
 
         // Fetch the root page for this revision
-        LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
-
-        TupleCursor<K, V> cursor = rootPage.browse( transaction, stack );
+        TupleCursor<K, V> cursor = rootPage.browse( transaction, new ParentPos[32], 0 );
 
         return cursor;
     }
@@ -898,8 +895,7 @@ public class BTree<K, V> implements Clos
         Page<K, V> revisionRootPage = getRootPage( revision );
 
         // And get the cursor
-        LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
-        TupleCursor<K, V> cursor = revisionRootPage.browse( transaction, stack );
+        TupleCursor<K, V> cursor = revisionRootPage.browse( transaction, new ParentPos[32], 0 );
 
         return cursor;
     }
@@ -918,7 +914,7 @@ public class BTree<K, V> implements Clos
         Transaction<K, V> transaction = beginReadTransaction();
 
         // Fetch the root page for this revision
-        TupleCursor<K, V> cursor = rootPage.browse( key, transaction, new LinkedList<ParentPos<K, V>>() );
+        TupleCursor<K, V> cursor = rootPage.browse( key, transaction, new ParentPos[32], 0 );
 
         return cursor;
     }
@@ -942,8 +938,7 @@ public class BTree<K, V> implements Clos
         Page<K, V> revisionRootPage = getRootPage( revision );
 
         // And get the cursor
-        LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
-        TupleCursor<K, V> cursor = revisionRootPage.browse( key, transaction, stack );
+        TupleCursor<K, V> cursor = revisionRootPage.browse( key, transaction, new ParentPos[32], 0 );
 
         return cursor;
     }

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeFactory.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeFactory.java?rev=1539986&r1=1539985&r2=1539986&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeFactory.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeFactory.java Fri Nov  8 11:37:27 2013
@@ -294,4 +294,49 @@ public class BTreeFactory
 
         return stack;
     }
+
+
+    /**
+     * Includes the intermediate nodes in the path up to and including the left most leaf of the tree
+     * 
+     * @param btree the btree
+     * @return a LinkedList of all the nodes and the final leaf
+     * @throws IOException
+     */
+    public static <K, V> LinkedList<ParentPos<K, V>> getPathToLeftMostLeaf( BTree<K, V> btree ) throws IOException
+    {
+        LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
+
+        ParentPos<K, V> first = new ParentPos<K, V>( btree.rootPage, 0 );
+        stack.push( first );
+
+        if ( btree.rootPage instanceof Leaf )
+        {
+            Leaf<K, V> leaf = ( Leaf<K, V> ) ( btree.rootPage );
+            ValueHolder<V> valueHolder = leaf.values[first.pos];
+            first.valueCursor = valueHolder.getCursor();
+        }
+        else
+        {
+            Node<K, V> node = ( Node<K, V> ) btree.rootPage;
+
+            while ( true )
+            {
+                Page<K, V> page = node.children[0].getValue( btree );
+
+                first = new ParentPos<K, V>( page, 0 );
+                stack.push( first );
+
+                if ( page instanceof Leaf )
+                {
+                    Leaf<K, V> leaf = ( Leaf<K, V> ) ( page );
+                    ValueHolder<V> valueHolder = leaf.values[first.pos];
+                    first.valueCursor = valueHolder.getCursor();
+                    break;
+                }
+            }
+        }
+
+        return stack;
+    }
 }

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java?rev=1539986&r1=1539985&r2=1539986&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java Fri Nov  8 11:37:27 2013
@@ -33,29 +33,6 @@ import java.io.IOException;
 /* No qualifier */class InternalUtil
 {
 
-    /**
-     * Sets the multi-value container(a.k.a dupsContainer) of the key at the given position.
-     * 
-     * This method will not update the existing value of 'dupsPos'. To change this value
-     * use {@link #changeNextDupsContainer(ParentPos, BTree)} or {@link #changePrevDupsContainer(ParentPos, BTree)}
-     *  
-     * @param parentPos the parent position object
-     * @param btree the BTree
-     */
-    public static void setDupsContainer( ParentPos parentPos, BTree btree )
-    {
-        if ( !btree.isAllowDuplicates() )
-        {
-            return;
-        }
-
-        if ( parentPos.valueHolder == null )
-        {
-            Leaf leaf = ( Leaf ) ( parentPos.page );
-            parentPos.valueHolder = leaf.values[parentPos.pos];
-        }
-    }
-
 
     /**
      * Sets the multi-value container(a.k.a dupsContainer) of the key at the given position
@@ -75,7 +52,8 @@ import java.io.IOException;
         if ( parentPos.pos < parentPos.page.getNbElems() )
         {
             Leaf leaf = ( Leaf ) ( parentPos.page );
-            parentPos.valueHolder = leaf.values[parentPos.pos];
+            ValueHolder valueHolder = leaf.values[parentPos.pos];
+            parentPos.valueCursor = valueHolder.getCursor();
         }
     }
 
@@ -100,7 +78,8 @@ import java.io.IOException;
         if ( index >= 0 )
         {
             Leaf leaf = ( Leaf ) ( parentPos.page );
-            parentPos.valueHolder = leaf.values[index];
+            ValueHolder valueHolder = leaf.values[index];
+            parentPos.valueCursor = valueHolder.getCursor();
         }
     }
 

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Leaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Leaf.java?rev=1539986&r1=1539985&r2=1539986&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Leaf.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Leaf.java Fri Nov  8 11:37:27 2013
@@ -20,13 +20,12 @@
 package org.apache.directory.mavibot.btree.managed;
 
 
-import static org.apache.directory.mavibot.btree.managed.InternalUtil.setDupsContainer;
-
 import java.io.IOException;
 import java.lang.reflect.Array;
 import java.util.LinkedList;
 
 import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.TupleCursor;
 import org.apache.directory.mavibot.btree.ValueCursor;
 import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
 import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
@@ -606,21 +605,23 @@ import org.apache.directory.mavibot.btre
     /**
      * {@inheritDoc}
      */
-    public TupleCursorImpl<K, V> browse( K key, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+    public TupleCursor<K, V> browse( K key, Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
     {
         int pos = findPos( key );
-        TupleCursorImpl<K, V> cursor = null;
+        TupleCursor<K, V> cursor = null;
 
         if ( pos < 0 )
         {
-            int index = -( pos + 1 );
+            pos = -( pos + 1 );
 
-            // The first element has been found. Create the cursor
-            ParentPos<K, V> parentPos = new ParentPos<K, V>( this, index );
-            setDupsContainer( parentPos, btree );
-            stack.push( parentPos );
+            cursor = new TupleCursorImpl<K, V>( btree, transaction, null, 0 );
 
-            cursor = new TupleCursorImpl<K, V>( btree, transaction, stack );
+            // Start at the beginning of the page
+            ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
+
+            stack[depth] = parentPos;
+
+            cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
         }
         else
         {
@@ -628,17 +629,17 @@ import org.apache.directory.mavibot.btre
             if ( pos < nbElems )
             {
                 ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
-                setDupsContainer( parentPos, btree );
-                stack.push( parentPos );
+                
+                stack[depth] = parentPos;
 
-                cursor = new TupleCursorImpl<K, V>( btree, transaction, stack );
+                cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, 0 );
             }
             else
             {
                 // Not found : return a null cursor
-                stack.push( new ParentPos<K, V>( null, -1 ) );
+                stack[depth] = null;
 
-                return new TupleCursorImpl<K, V>( btree, transaction, stack );
+                return new TupleCursorImpl<K, V>( btree, transaction, null, 0 );
             }
         }
 
@@ -649,28 +650,26 @@ import org.apache.directory.mavibot.btre
     /**
      * {@inheritDoc}
      */
-    public TupleCursorImpl<K, V> browse( Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+    public TupleCursor<K, V> browse( Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
     {
         int pos = 0;
-        TupleCursorImpl<K, V> cursor = null;
+        TupleCursor<K, V> cursor = null;
 
         if ( nbElems == 0 )
         {
             // The tree is empty, it's the root, we have nothing to return
-            stack.push( new ParentPos<K, V>( null, -1 ) );
+            stack[depth] = new ParentPos<K, V>( null, -1 );
 
-            return new TupleCursorImpl<K, V>( btree, transaction, stack );
+            return new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
         }
         else
         {
             // Start at the beginning of the page
             ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
 
-            setDupsContainer( parentPos, btree );
-
-            stack.push( parentPos );
+            stack[depth] = parentPos;
 
-            cursor = new TupleCursorImpl<K, V>( btree, transaction, stack );
+            cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
         }
 
         return cursor;

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Node.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Node.java?rev=1539986&r1=1539985&r2=1539986&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Node.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Node.java Fri Nov  8 11:37:27 2013
@@ -22,7 +22,6 @@ package org.apache.directory.mavibot.btr
 
 import java.io.IOException;
 import java.lang.reflect.Array;
-import java.util.LinkedList;
 import java.util.List;
 
 import org.apache.directory.mavibot.btree.Tuple;
@@ -968,7 +967,7 @@ import org.apache.directory.mavibot.btre
     /**
      * {@inheritDoc}
      */
-    public TupleCursor<K, V> browse( K key, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+    public TupleCursor<K, V> browse( K key, Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
         throws IOException
     {
         int pos = findPos( key );
@@ -979,21 +978,25 @@ import org.apache.directory.mavibot.btre
         }
 
         // We first stack the current page
-        stack.push( new ParentPos<K, V>( this, pos ) );
+        stack[depth++] = new ParentPos<K, V>( this, pos );
+        
+        Page<K, V> page = children[0].getValue( btree );
 
-        return children[pos].getValue( btree ).browse( key, transaction, stack );
+        return page.browse( key, transaction, stack, depth );
     }
 
 
     /**
      * {@inheritDoc}
      */
-    public TupleCursor<K, V> browse( Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+    public TupleCursor<K, V> browse( Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
         throws IOException
     {
-        stack.push( new ParentPos<K, V>( this, 0 ) );
+        stack[depth++] = new ParentPos<K, V>( this, 0 );
+        
+        Page<K, V> page = children[0].getValue( btree );
 
-        return children[0].getValue( btree ).browse( transaction, stack );
+        return page.browse( transaction, stack, depth );
     }
 
 

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Page.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Page.java?rev=1539986&r1=1539985&r2=1539986&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Page.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Page.java Fri Nov  8 11:37:27 2013
@@ -136,7 +136,7 @@ import org.apache.directory.mavibot.btre
      * @return A Cursor to browse the next elements
      * @throws IOException If we have an error while trying to access the page
      */
-    TupleCursor<K, V> browse( K key, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+    TupleCursor<K, V> browse( K key, Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
         throws IOException;
 
 
@@ -148,7 +148,7 @@ import org.apache.directory.mavibot.btre
      * @return A Cursor to browse the next elements
      * @throws IOException If we have an error while trying to access the page
      */
-    TupleCursor<K, V> browse( Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+    TupleCursor<K, V> browse( Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
         throws EndOfFileExceededException, IOException;
 
 

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ParentPos.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ParentPos.java?rev=1539986&r1=1539985&r2=1539986&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ParentPos.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ParentPos.java Fri Nov  8 11:37:27 2013
@@ -19,6 +19,8 @@
  */
 package org.apache.directory.mavibot.btree.managed;
 
+import org.apache.directory.mavibot.btree.ValueCursor;
+
 
 /**
  * This class is used to store the parent page and the position in it during
@@ -38,10 +40,7 @@ package org.apache.directory.mavibot.btr
     /* No qualifier*/int pos;
 
     /** The current position of the duplicate container in the page */
-    /* No qualifier*/int dupPos;
-
-    /** the container of duplicate key's values. The tuples will be stored as <V,null>*/
-    /* No qualifier*/ValueHolder<V> valueHolder;
+    /* No qualifier*/ValueCursor<V> valueCursor;
 
 
     /**
@@ -53,6 +52,20 @@ package org.apache.directory.mavibot.btr
     {
         this.page = page;
         this.pos = pos;
+        
+        if ( page instanceof Leaf )
+        {
+            try
+            {
+                ValueHolder<V> valueHolder = ( ( Leaf<K, V> ) page ).getValue( pos );
+                
+                valueCursor = valueHolder.getCursor();
+            }
+            catch ( IllegalArgumentException e )
+            {
+                e.printStackTrace();
+            }
+        }
     }
 
 

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/TupleCursorImpl.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/TupleCursorImpl.java?rev=1539986&r1=1539985&r2=1539986&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/TupleCursorImpl.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/TupleCursorImpl.java Fri Nov  8 11:37:27 2013
@@ -24,11 +24,11 @@ import static org.apache.directory.mavib
 import static org.apache.directory.mavibot.btree.managed.InternalUtil.changePrevDupsContainer;
 
 import java.io.IOException;
-import java.util.LinkedList;
 import java.util.NoSuchElementException;
 
 import org.apache.directory.mavibot.btree.Tuple;
 import org.apache.directory.mavibot.btree.TupleCursor;
+import org.apache.directory.mavibot.btree.ValueCursor;
 import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
 
 
@@ -52,16 +52,16 @@ public class TupleCursorImpl<K, V> imple
     private Tuple<K, V> tuple = new Tuple<K, V>();
 
     /** The stack of pages from the root down to the leaf */
-    private LinkedList<ParentPos<K, V>> stack;
+    private ParentPos<K, V>[] stack;
+    
+    /** The stack's depth */
+    private int depth = 0;
 
     /** The BTree we are walking */
     private BTree<K, V> btree;
 
     private boolean allowDuplicates;
 
-    /** a copy of the stack given at the time of initializing the cursor. This is used for moving the cursor to start position */
-    private LinkedList<ParentPos<K, V>> _initialStack;
-
 
     /**
      * Creates a new instance of Cursor, starting on a page at a given position.
@@ -69,16 +69,13 @@ public class TupleCursorImpl<K, V> imple
      * @param transaction The transaction this operation is protected by
      * @param stack The stack of parent's from root to this page
      */
-    TupleCursorImpl( BTree<K, V> btree, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+    TupleCursorImpl( BTree<K, V> btree, Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
     {
         this.transaction = transaction;
         this.stack = stack;
         this.btree = btree;
         this.allowDuplicates = btree.isAllowDuplicates();
-
-        _initialStack = new LinkedList<ParentPos<K, V>>();
-
-        cloneStack( stack, _initialStack );
+        this.depth = depth;
     }
 
 
@@ -91,7 +88,7 @@ public class TupleCursorImpl<K, V> imple
      */
     public Tuple<K, V> next() throws EndOfFileExceededException, IOException
     {
-        ParentPos<K, V> parentPos = stack.getFirst();
+        ParentPos<K, V> parentPos = stack[depth];
 
         if ( parentPos.page == null )
         {
@@ -107,25 +104,53 @@ public class TupleCursorImpl<K, V> imple
 
             // we also need to check for the type of page cause
             // findNextParentPos will never return a null ParentPos
-            if ( parentPos.page == null || ( parentPos.page instanceof Node ) )
+            if ( ( parentPos == null ) || ( parentPos.page == null ) )
             {
                 // This is the end : no more value
                 throw new NoSuchElementException( "No more tuples present" );
             }
         }
 
-        // can happen if next() is called after prev()
-        if ( parentPos.pos < 0 )
+        V value = null;
+        
+        if ( parentPos.valueCursor.hasNext() )
         {
-            parentPos.pos = 0;
+            value = parentPos.valueCursor.next();
         }
+        else
+        {
+            if ( parentPos.pos == parentPos.page.getNbElems() - 1 )
+            {
+                parentPos = findNextParentPos();
 
+                if ( ( parentPos == null ) || ( parentPos.page == null ) )
+                {
+                    // This is the end : no more value
+                    throw new NoSuchElementException( "No more tuples present" );
+                }
+            }
+            else
+            {
+                parentPos.pos++;
+            }
+                
+            try
+            {
+                ValueHolder<V> valueHolder = ( ( Leaf<K, V> ) parentPos.page ).getValue( parentPos.pos );
+                
+                parentPos.valueCursor = valueHolder.getCursor();
+                
+                value = parentPos.valueCursor.next();
+            }
+            catch ( IllegalArgumentException e )
+            {
+                e.printStackTrace();
+            }
+        }
+        
         Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
         tuple.setKey( leaf.keys[parentPos.pos].getKey() );
-
-        ValueHolder<V> valueHolder = leaf.values[parentPos.pos];
-        tuple.setValue( valueHolder.getCursor().next() );
-        parentPos.pos++;
+        tuple.setValue( value );
 
         return tuple;
     }
@@ -140,53 +165,57 @@ public class TupleCursorImpl<K, V> imple
      */
     private ParentPos<K, V> findNextParentPos() throws EndOfFileExceededException, IOException
     {
-        ParentPos<K, V> lastParentPos = null;
+        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, V> child = null;
 
-        while ( true )
+        // 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, V> parentPos = stack.peek();
-
-            if ( parentPos == null )
-            {
-                stack.push( lastParentPos );
-                return lastParentPos;
-            }
+            ParentPos<K, V> parentPos = stack[currentDepth];
 
             if ( parentPos.pos == parentPos.page.getNbElems() )
             {
-                lastParentPos = stack.pop();
-                continue;
+                // No more element on the right : go up
+                currentDepth--;
             }
             else
             {
-                // Then we go down the tree until we find a leaf which position is not the last one.
-                int newPos = ++parentPos.pos;
-                ParentPos<K, V> newParentPos = parentPos;
-
-                while ( newParentPos.page instanceof Node )
+                // We can pick the next element at this level
+                parentPos.pos++;
+                child = ((Node<K, V>)parentPos.page).children[parentPos.pos].getValue( btree );
+                
+                // and go down the tree through the nodes
+                while ( currentDepth < depth - 1 )
                 {
-                    Node<K, V> node = ( Node<K, V> ) newParentPos.page;
-
-                    newParentPos = new ParentPos<K, V>( node.children[newPos].getValue( btree ), 0 );
-
-                    stack.push( newParentPos );
-
-                    newPos = 0;
+                    currentDepth++;
+                    parentPos = stack[currentDepth];
+                    parentPos.page = child;
+                    parentPos.pos = 0;
+                    child = ((Node<K, V>)parentPos.page).children[parentPos.pos].getValue( btree );
                 }
 
-                if ( allowDuplicates )
-                {
-                    changeNextDupsContainer( newParentPos, btree );
-                }
+                // and the leaf
+                parentPos = stack[depth];
+                parentPos.pos = 0;
+                parentPos.page = child;
+                parentPos.valueCursor = ((Leaf<K, V>)child).values[0].getCursor();
 
-                return newParentPos;
+                return parentPos;
             }
         }
+        
+        return null;
     }
-
-
+    
+    
     /**
      * Find the leaf containing the previous elements.
      * 
@@ -194,53 +223,58 @@ public class TupleCursorImpl<K, V> imple
      * @throws IOException 
      * @throws EndOfFileExceededException 
      */
-    private ParentPos<K, V> findPreviousParentPos() throws EndOfFileExceededException, IOException
+    private ParentPos<K, V> findPrevParentPos() throws EndOfFileExceededException, IOException
     {
-        ParentPos<K, V> lastParentPos = null;
-
-        while ( true )
+        if ( depth == 0 )
         {
-            // We first go up the tree, until we reach a page which current position
-            // is not the first one
-            ParentPos<K, V> parentPos = stack.peek();
+            // No need to go any further, there is only one leaf in the btree
+            return null;
+        }
 
-            if ( parentPos == null )
-            {
-                stack.push( lastParentPos );
-                return lastParentPos;
-            }
+        int currentDepth = depth - 1;
+        Page<K, V> 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, V> parentPos = stack[currentDepth];
 
             if ( parentPos.pos == 0 )
             {
-                lastParentPos = stack.pop();
-                continue;
+                // No more element on the right : go up
+                currentDepth--;
             }
             else
             {
-                // Then we go down the tree until we find a leaf which position is not the first one.
-                int newPos = --parentPos.pos;
-                ParentPos<K, V> newParentPos = parentPos;
-
-                while ( newParentPos.page instanceof Node )
+                // We can pick the next element at this level
+                parentPos.pos--;
+                child = ((Node<K, V>)parentPos.page).children[parentPos.pos].getValue( btree );
+                
+                // and go down the tree through the nodes
+                while ( currentDepth < depth - 1 )
                 {
-                    Node<K, V> node = ( Node<K, V> ) newParentPos.page;
-
-                    newParentPos = new ParentPos<K, V>( node.children[newPos].getValue( btree ), node.children[newPos]
-                        .getValue( btree ).getNbElems() );
-
-                    stack.push( newParentPos );
-
-                    newPos = node.getNbElems();
+                    currentDepth++;
+                    parentPos = stack[currentDepth];
+                    parentPos.pos = child.getNbElems();
+                    parentPos.page = child;
+                    child = ((Node<K, V>)parentPos.page).children[((Node<K, V>)parentPos.page).nbElems].getValue( btree );
                 }
 
-                if ( allowDuplicates )
-                {
-                    changePrevDupsContainer( newParentPos, btree );
-                }
+                // and the leaf
+                parentPos = stack[depth];
+                parentPos.pos = child.getNbElems() - 1;
+                parentPos.page = child;
+                ValueHolder<V> valueHolder = ((Leaf<K, V>)parentPos.page).values[parentPos.pos];
+                parentPos.valueCursor = valueHolder.getCursor();
+                parentPos.valueCursor.afterLast();
 
-                return newParentPos;
+                return parentPos;
             }
         }
+        
+        return null;
     }
 
 
@@ -253,7 +287,7 @@ public class TupleCursorImpl<K, V> imple
      */
     public Tuple<K, V> prev() throws EndOfFileExceededException, IOException
     {
-        ParentPos<K, V> parentPos = stack.peek();
+        ParentPos<K, V> parentPos = stack[depth];
 
         if ( parentPos.page == null )
         {
@@ -261,66 +295,121 @@ public class TupleCursorImpl<K, V> imple
             throw new NoSuchElementException( "No more tuples present" );
         }
 
-        if ( parentPos.pos == 0 && parentPos.dupPos == 0 )
+        if ( ( parentPos.pos == 0 ) && ( !parentPos.valueCursor.hasPrev() ) )
         {
             // End of the leaf. We have to go back into the stack up to the
             // parent, and down to the leaf
-            parentPos = findPreviousParentPos();
+            parentPos = findPrevParentPos();
 
             // we also need to check for the type of page cause
             // findPrevParentPos will never return a null ParentPos
-            if ( parentPos.page == null || ( parentPos.page instanceof Node ) )
+            if ( ( parentPos == null ) || ( parentPos.page == null ) || ( parentPos.page instanceof Node ) )
             {
                 // This is the end : no more value
                 throw new NoSuchElementException( "No more tuples present" );
             }
         }
+        
+        V value = null;
+        
+        if ( parentPos.valueCursor.hasPrev() )
+        {
+            value = parentPos.valueCursor.prev();
+        }
+        else
+        {
+            if ( parentPos.pos == 0 )
+            {
+                parentPos = findPrevParentPos();
+
+                if ( ( parentPos == null ) || ( parentPos.page == null ) )
+                {
+                    // This is the end : no more value
+                    throw new NoSuchElementException( "No more tuples present" );
+                }
+            }
+            else
+            {
+                parentPos.pos--;
+                
+                try
+                {
+                    ValueHolder<V> valueHolder = ( ( Leaf<K, V> ) parentPos.page ).getValue( parentPos.pos );
+                    
+                    parentPos.valueCursor = valueHolder.getCursor();
+                    parentPos.valueCursor.afterLast();
+                    
+                    value = parentPos.valueCursor.prev();
+                }
+                catch ( IllegalArgumentException e )
+                {
+                    e.printStackTrace();
+                }
+            }
+        }
+
 
         Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
-        ValueHolder<V> valueHolder = leaf.values[parentPos.pos];
         tuple.setKey( leaf.keys[parentPos.pos].getKey() );
-        tuple.setValue( valueHolder.getCursor().next() );
+        tuple.setValue( value );
 
         return tuple;
     }
 
 
     /**
-     * Tells if the cursor can return a next element
+     * Tells if the cursor can return a next tupe.
+     * 
      * @return true if there are some more elements
      * @throws IOException 
      * @throws EndOfFileExceededException 
      */
     public boolean hasNext() throws EndOfFileExceededException, IOException
     {
-        ParentPos<K, V> parentPos = stack.peek();
+        // Take the leaf and check if we have no mare values
+        ParentPos<K, V> parentPos = stack[depth];
 
         if ( parentPos.page == null )
         {
+            // Empty BTree, get out
             return false;
         }
 
-        for ( ParentPos<K, V> p : stack )
+        if ( parentPos.pos < parentPos.page.getNbElems() - 1 )
+        {
+            // Not the last position, we have a next value
+            return true;
+        }
+        else
         {
-            if ( allowDuplicates && ( p.page instanceof Leaf ) )
+            // Check if we have some more value
+            if ( parentPos.valueCursor.hasNext() )
             {
-                if ( ( p.valueHolder == null ) && ( p.pos != p.page.getNbElems() ) )
+                return true;
+            }
+            
+            // Ok, here, we have reached the last value in the leaf. We have to go up and 
+            // see if we have some remaining values
+            int currentDepth = depth - 1;
+            
+            while ( currentDepth >= 0 )
+            {
+                parentPos = stack[currentDepth];
+                
+                if ( parentPos.pos < parentPos.page.getNbElems() )
                 {
+                    // The parent has some remaining values on the right, get out
                     return true;
                 }
-                else if ( ( p.valueHolder != null ) && ( p.dupPos != p.valueHolder.size() )
-                    && ( p.pos != p.page.getNbElems() ) )
+                else
                 {
-                    return true;
+                    currentDepth --;
                 }
             }
-            else if ( p.pos != p.page.getNbElems() )
-            {
-                return true;
-            }
+            
+            // We are done, there are no more value left
+            return false;
         }
-
-        return false;
     }
 
 
@@ -332,34 +421,49 @@ public class TupleCursorImpl<K, V> imple
      */
     public boolean hasPrev() throws EndOfFileExceededException, IOException
     {
-        ParentPos<K, V> parentPos = stack.peek();
+        // Take the leaf and check if we have no mare values
+        ParentPos<K, V> parentPos = stack[depth];
 
         if ( parentPos.page == null )
         {
+            // Empty BTree, get out
             return false;
         }
 
-        for ( ParentPos<K, V> p : stack )
+        if ( parentPos.pos > 0 )
+        {
+            // get out, we have values on the left
+            return true;
+        }
+        else
         {
-            if ( allowDuplicates && ( p.page instanceof Leaf ) )
+            // Check if we have some more value
+            if ( parentPos.valueCursor.hasPrev() )
             {
-                if ( ( p.valueHolder == null ) && ( p.pos != 0 ) )
+                return true;
+            }
+
+            // Ok, here, we have reached the first value in the leaf. We have to go up and 
+            // see if we have some remaining values
+            int currentDepth = depth - 1;
+            
+            while ( currentDepth >= 0 )
+            {
+                parentPos = stack[currentDepth];
+                
+                if ( parentPos.pos > 0 )
                 {
+                    // The parent has some remaining values on the right, get out
                     return true;
                 }
-                else if ( ( p.valueHolder != null ) &&
-                    ( ( p.dupPos != 0 ) || ( p.pos != 0 ) ) )
+                else
                 {
-                    return true;
+                    currentDepth --;
                 }
             }
-            else if ( p.pos != 0 )
-            {
-                return true;
-            }
+            
+            return false;
         }
-
-        return false;
     }
 
 
@@ -409,7 +513,7 @@ public class TupleCursorImpl<K, V> imple
      */
     public void moveToNextNonDuplicateKey() throws EndOfFileExceededException, IOException
     {
-        ParentPos<K, V> parentPos = stack.getFirst();
+        ParentPos<K, V> parentPos = stack[depth];
 
         if ( parentPos.page == null )
         {
@@ -462,7 +566,7 @@ public class TupleCursorImpl<K, V> imple
      */
     public void moveToPrevNonDuplicateKey() throws EndOfFileExceededException, IOException
     {
-        ParentPos<K, V> parentPos = stack.peek();
+        ParentPos<K, V> parentPos = stack[depth];
 
         if ( parentPos.page == null )
         {
@@ -474,7 +578,7 @@ public class TupleCursorImpl<K, V> imple
         {
             // End of the leaf. We have to go back into the stack up to the
             // parent, and down to the leaf
-            parentPos = findPreviousParentPos();
+            parentPos = findPrevParentPos();
 
             // if the returned value is a Node that means cursor is already at the first position
             // call beforeFirst() to restore the stack to the initial state
@@ -502,7 +606,36 @@ public class TupleCursorImpl<K, V> imple
      */
     public void beforeFirst() throws IOException
     {
-        cloneStack( _initialStack, stack );
+        Page<K, V> child = null;
+        
+        for ( int i = 0; i < depth; i++ )
+        {
+            ParentPos<K, V> parentPos = stack[i];
+            parentPos.pos = 0;
+            
+            if ( child != null )
+            {
+                parentPos.page = child;
+            }
+            
+            child = ((Node<K, V>)parentPos.page).children[0].getValue( btree );
+        }
+        
+        // and leaf
+        ParentPos<K, V> parentPos = stack[depth];
+        parentPos.pos = 0;
+        
+        if ( child == null )
+        {
+            child = parentPos.page;
+        }
+        else
+        {
+            parentPos.page = child;
+        }
+        
+        parentPos.valueCursor = ((Leaf<K, V>)parentPos.page).values[parentPos.pos].getCursor();
+        parentPos.valueCursor.beforeFirst();
     }
 
 
@@ -513,28 +646,40 @@ public class TupleCursorImpl<K, V> imple
      */
     public void afterLast() throws IOException
     {
-        stack.clear();
-        stack = BTreeFactory.getPathToRightMostLeaf( btree );
-    }
+        Page<K, V> child = null;
 
+        for ( int i = 0; i < depth; i++ )
+        {
+            ParentPos<K, V> parentPos = stack[i];
+            
+            if ( child != null )
+            {
+                parentPos.page = child;
+                parentPos.pos = ((Node<K, V>)child).nbElems;
+            }
+            else
+            {
+                parentPos.pos = ((Node<K, V>)parentPos.page).nbElems;
+            }
 
-    /**
-     * clones the original stack of ParentPos objects
-     * 
-     * @param original the original stack
-     * @param clone the stack where the cloned ParentPos objects to be copied
-     */
-    private void cloneStack( LinkedList<ParentPos<K, V>> original, LinkedList<ParentPos<K, V>> clone )
-    {
-        clone.clear();
+            child = ((Node<K, V>)parentPos.page).children[parentPos.pos].getValue( btree );
+        }
+        
+        // and leaf
+        ParentPos<K, V> parentPos = stack[depth];
 
-        // preserve the first position
-        for ( ParentPos<K, V> o : original )
+        if ( child == null )
         {
-            ParentPos<K, V> tmp = new ParentPos<K, V>( o.page, o.pos );
-            tmp.dupPos = o.dupPos;
-            tmp.valueHolder = o.valueHolder;
-            clone.add( tmp );
+            child = parentPos.page;
+            parentPos.pos = ((Leaf<K, V>)parentPos.page).nbElems - 1;
         }
+        else
+        {
+            parentPos.page = child;
+            parentPos.pos = ((Leaf<K, V>)child).nbElems - 1;
+        }
+
+        parentPos.valueCursor = ((Leaf<K, V>)parentPos.page).values[parentPos.pos].getCursor();
+        parentPos.valueCursor.afterLast();
     }
 }

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ValueHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ValueHolder.java?rev=1539986&r1=1539985&r2=1539986&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ValueHolder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ValueHolder.java Fri Nov  8 11:37:27 2013
@@ -246,7 +246,7 @@ public class ValueHolder<V> implements C
             }
             else
             {
-                return ( valueArray != null ) && ( currentPos < valueArray.length - 1 );
+                return currentPos < valueArray.length - 1;
             }
         }
 
@@ -284,7 +284,15 @@ public class ValueHolder<V> implements C
         @Override
         public boolean hasPrev() throws EndOfFileExceededException, IOException
         {
-            return false;
+            if ( valueArray == null )
+            {
+                // Load the array from the raw data
+                return false;
+            }
+            else
+            {
+                return currentPos > 0;
+            }
         }
 
 
@@ -303,6 +311,7 @@ public class ValueHolder<V> implements C
         @Override
         public void beforeFirst() throws IOException
         {
+            currentPos = -1;
         }
 
 
@@ -312,6 +321,7 @@ public class ValueHolder<V> implements C
         @Override
         public void afterLast() throws IOException
         {
+            currentPos = valueArray.length;
         }
 
 
@@ -321,7 +331,25 @@ public class ValueHolder<V> implements C
         @Override
         public V prev() throws EndOfFileExceededException, IOException
         {
-            return null;
+            if ( valueArray == null )
+            {
+                // Deserialize the array
+                return null;
+            }
+            else
+            {
+                currentPos--;
+
+                if ( currentPos == -1 )
+                {
+                    // We have reached the end of the array
+                    return null;
+                }
+                else
+                {
+                    return valueArray[currentPos];
+                }
+            }
         }
 
 

Added: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/managed/ManagedBTreeBrowseTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/managed/ManagedBTreeBrowseTest.java?rev=1539986&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/managed/ManagedBTreeBrowseTest.java (added)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/managed/ManagedBTreeBrowseTest.java Fri Nov  8 11:37:27 2013
@@ -0,0 +1,733 @@
+/*
+ *  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.managed;
+
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.io.File;
+import java.io.IOException;
+import java.util.NoSuchElementException;
+import java.util.UUID;
+
+import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.TupleCursor;
+import org.apache.directory.mavibot.btree.exception.BTreeAlreadyManagedException;
+import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
+import org.apache.directory.mavibot.btree.serializer.LongSerializer;
+import org.apache.directory.mavibot.btree.serializer.StringSerializer;
+import org.junit.Before;
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.rules.TemporaryFolder;
+
+
+/**
+ * Tests the browse methods on a managed BTree
+ * 
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class ManagedBTreeBrowseTest
+{
+    private BTree<Long, String> btree = null;
+
+    private RecordManager recordManager1 = null;
+
+    @Rule
+    public TemporaryFolder tempFolder = new TemporaryFolder();
+
+    private File dataDir = null;
+
+
+    @Before
+    public void createBTree()
+    {
+        dataDir = tempFolder.newFolder( UUID.randomUUID().toString() );
+
+        openRecordManagerAndBtree();
+
+        try
+        {
+            // Create a new BTree
+            btree = recordManager1.addBTree( "test", new LongSerializer(), new StringSerializer(), false );
+        }
+        catch ( Exception e )
+        {
+            throw new RuntimeException( e );
+        }
+    }
+
+
+    private void openRecordManagerAndBtree()
+    {
+        try
+        {
+            if ( recordManager1 != null )
+            {
+                recordManager1.close();
+            }
+
+            // Now, try to reload the file back
+            recordManager1 = new RecordManager( dataDir.getAbsolutePath() );
+
+            // load the last created btree
+            if ( btree != null )
+            {
+                btree = recordManager1.getManagedTree( btree.getName() );
+            }
+        }
+        catch ( Exception e )
+        {
+            throw new RuntimeException( e );
+        }
+    }
+
+
+    /**
+     * Check a next() call
+     */
+    private void checkNext( TupleCursor<Long, String> cursor, long key, String value, boolean next, boolean prev ) throws EndOfFileExceededException, IOException
+    {
+        Tuple<Long, String> tuple = cursor.next();
+        assertNotNull( tuple );
+        assertEquals( key, (long)tuple.getKey() );
+        assertEquals( value, tuple.getValue() );
+        assertEquals( next, cursor.hasNext() );
+        assertEquals( prev, cursor.hasPrev() );
+    }
+
+
+    /**
+     * Check a prev() call
+     */
+    private void checkPrev( TupleCursor<Long, String> cursor, long key, String value, boolean next, boolean prev ) throws EndOfFileExceededException, IOException
+    {
+        Tuple<Long, String> tuple = cursor.prev();
+        assertNotNull( tuple );
+        assertEquals( key, (long)tuple.getKey() );
+        assertEquals( value, tuple.getValue() );
+        assertEquals( next, cursor.hasNext() );
+        assertEquals( prev, cursor.hasPrev() );
+    }
+
+    
+    /**
+     * Test the browse methods on an empty btree  
+     */
+    @Test
+    public void testBrowseEmptyBTree() throws IOException, BTreeAlreadyManagedException
+    {
+        TupleCursor<Long, String> cursor = btree.browse();
+        
+        assertFalse( cursor.hasNext() );
+        assertFalse( cursor.hasPrev() );
+        
+        try
+        {
+            cursor.next();
+            fail();
+        }
+        catch ( NoSuchElementException nsee )
+        {
+            // Expected
+        }
+        
+        try
+        {
+            cursor.prev();
+            fail();
+        }
+        catch ( NoSuchElementException nsee )
+        {
+            // Expected
+        }
+        
+        assertEquals( -1L, cursor.getRevision() );
+    }
+
+
+    /**
+     * Test the browse methods on a btree containing just a leaf
+     */
+    @Test
+    public void testBrowseBTreeLeafNext() throws IOException, BTreeAlreadyManagedException
+    {
+        // Inject some data
+        btree.insert( 1L, "1" );
+        btree.insert( 4L, "4" );
+        btree.insert( 2L, "2" );
+        btree.insert( 3L, "3" );
+        btree.insert( 5L, "5" );
+
+        // Create the cursor
+        TupleCursor<Long, String> cursor = btree.browse();
+        
+        // Move forward
+        cursor.beforeFirst();
+        
+        assertFalse( cursor.hasPrev() );
+        assertTrue( cursor.hasNext() );
+        
+        checkNext( cursor, 1L, "1", true, false );
+        checkNext( cursor, 2L, "2", true, true );
+        checkNext( cursor, 3L, "3", true, true );
+        checkNext( cursor, 4L, "4", true, true );
+        checkNext( cursor, 5L, "5", false, true );
+    }
+
+
+    /**
+     * Test the browse methods on a btree containing just a leaf
+     */
+    @Test
+    public void testBrowseBTreeLeafPrev() throws IOException, BTreeAlreadyManagedException
+    {
+        // Inject some data
+        btree.insert( 1L, "1" );
+        btree.insert( 4L, "4" );
+        btree.insert( 2L, "2" );
+        btree.insert( 3L, "3" );
+        btree.insert( 5L, "5" );
+
+        // Create the cursor
+        TupleCursor<Long, String> cursor = btree.browse();
+        
+        // Move backward
+        cursor.afterLast();
+        
+        checkPrev( cursor, 5L, "5", false, true );
+        checkPrev( cursor, 4L, "4", true, true );
+        checkPrev( cursor, 3L, "3", true, true );
+        checkPrev( cursor, 2L, "2", true, true );
+        checkPrev( cursor, 1L, "1", true, false );
+    }
+
+
+    /**
+     * Test the browse methods on a btree containing just a leaf and see if we can
+     * move at the end or at the beginning
+     */
+    @Test
+    public void testBrowseBTreeLeafFirstLast() throws IOException, BTreeAlreadyManagedException
+    {
+        // Inject some data
+        btree.insert( 1L, "1" );
+        btree.insert( 4L, "4" );
+        btree.insert( 2L, "2" );
+        btree.insert( 3L, "3" );
+        btree.insert( 5L, "5" );
+
+        // Create the cursor
+        TupleCursor<Long, String> cursor = btree.browse();
+        
+        // We should not be able to move backward
+        try
+        {
+            cursor.prev();
+            fail();
+        }
+        catch ( NoSuchElementException nsee )
+        {
+            // Expected
+        }
+
+        // Start browsing three elements
+        assertFalse( cursor.hasPrev() );
+        assertTrue( cursor.hasNext() );
+        Tuple<Long, String> tuple = cursor.next();
+        tuple = cursor.next();
+        tuple = cursor.next();
+        
+        // We should be at 3 now
+        assertTrue( cursor.hasPrev() );
+        assertTrue( cursor.hasNext() );
+        assertEquals( 3L, (long)tuple.getKey() );
+        assertEquals( "3", tuple.getValue() );
+        
+        // Move to the end
+        cursor.afterLast();
+
+        assertTrue( cursor.hasPrev() );
+        assertFalse( cursor.hasNext() );
+
+        // We should not be able to move forward
+        try
+        {
+            cursor.next();
+            fail();
+        }
+        catch ( NoSuchElementException nsee )
+        {
+            // Expected
+        }
+
+        
+        // We should be at 5
+        tuple = cursor.prev();
+        assertEquals( 5L, (long)tuple.getKey() );
+        assertEquals( "5", tuple.getValue() );
+        
+        assertTrue( cursor.hasPrev() );
+        assertFalse( cursor.hasNext() );
+
+        // Move back to the origin
+        cursor.beforeFirst();
+        
+        assertFalse( cursor.hasPrev() );
+        assertTrue( cursor.hasNext() );
+
+        // We should be at 1
+        tuple = cursor.next();
+        assertEquals( 1L, (long)tuple.getKey() );
+        assertEquals( "1", tuple.getValue() );
+        
+        assertFalse( cursor.hasPrev() );
+        assertTrue( cursor.hasNext() );
+    }
+
+
+    /**
+     * Test the browse methods on a btree containing just a leaf and see if we can
+     * move back and forth
+     */
+    @Test
+    public void testBrowseBTreeLeafNextPrev() throws IOException, BTreeAlreadyManagedException
+    {
+        // Inject some data
+        btree.insert( 1L, "1" );
+        btree.insert( 4L, "4" );
+        btree.insert( 2L, "2" );
+        btree.insert( 3L, "3" );
+        btree.insert( 5L, "5" );
+
+        // Create the cursor
+        TupleCursor<Long, String> cursor = btree.browse();
+        
+        // We should not be able to move backward
+        try
+        {
+            cursor.prev();
+            fail();
+        }
+        catch ( NoSuchElementException nsee )
+        {
+            // Expected
+        }
+
+        // Start browsing three elements
+        assertFalse( cursor.hasPrev() );
+        assertTrue( cursor.hasNext() );
+        Tuple<Long, String> tuple = cursor.next();
+        tuple = cursor.next();
+        tuple = cursor.next();
+        
+        // We should be at 3 now
+        assertTrue( cursor.hasPrev() );
+        assertTrue( cursor.hasNext() );
+        assertEquals( 3L, (long)tuple.getKey() );
+        assertEquals( "3", tuple.getValue() );
+        
+        // Now, move to the prev value
+        cursor.prev();
+        assertEquals( 2L, (long)tuple.getKey() );
+        assertEquals( "2", tuple.getValue() );
+        
+        // And to the next value
+        cursor.next();
+        assertEquals( 3L, (long)tuple.getKey() );
+        assertEquals( "3", tuple.getValue() );
+    }
+
+
+    /**
+     * Test the browse methods on a btree containing many nodes
+     */
+    @Test
+    public void testBrowseBTreeNodesNext() throws IOException, BTreeAlreadyManagedException
+    {
+        // Inject some data
+        for ( long i = 1; i < 1000L; i++ )
+        {
+            btree.insert( i, Long.toString( i ) );
+        }
+
+        // Create the cursor
+        TupleCursor<Long, String> cursor = btree.browse();
+        
+        // Move forward
+        cursor.beforeFirst();
+        
+        assertFalse( cursor.hasPrev() );
+        assertTrue( cursor.hasNext() );
+
+        checkNext( cursor, 1L, "1", true, false );
+        
+        for ( long i = 2L; i < 999L; i++ )
+        {
+            checkNext( cursor, i, Long.toString( i ), true, true );
+        }
+
+        checkNext( cursor, 999L, "999", false, true );
+    }
+
+
+    /**
+     * Test the browse methods on a btree containing many nodes
+     */
+    @Test
+    public void testBrowseBTreeNodesPrev() throws IOException, BTreeAlreadyManagedException
+    {
+        // Inject some data
+        for ( long i = 1; i < 1000L; i++ )
+        {
+            btree.insert( i, Long.toString( i ) );
+        }
+
+        // Create the cursor
+        TupleCursor<Long, String> cursor = btree.browse();
+        
+        // Move backward
+        cursor.afterLast();
+        
+        assertTrue( cursor.hasPrev() );
+        assertFalse( cursor.hasNext() );
+        
+        checkPrev( cursor, 999L, "999", false, true );
+        
+        for ( long i = 998L; i > 1L; i-- )
+        {
+            checkPrev( cursor, i, Long.toString( i ), true, true );
+        }
+
+        checkPrev( cursor, 1L, "1", true, false );
+    }
+
+
+    /**
+     * Test the browse methods on a btree containing just a leaf with duplicate values
+     */
+    @Test
+    public void testBrowseBTreeLeafNextDups1() throws IOException, BTreeAlreadyManagedException
+    {
+        // Inject some duplicate data
+        btree.insert( 1L, "1" );
+        btree.insert( 1L, "4" );
+        btree.insert( 1L, "2" );
+        btree.insert( 1L, "3" );
+        btree.insert( 1L, "5" );
+
+        // Create the cursor
+        TupleCursor<Long, String> cursor = btree.browse();
+        
+        // Move forward
+        cursor.beforeFirst();
+        
+        assertFalse( cursor.hasPrev() );
+        assertTrue( cursor.hasNext() );
+        
+        checkNext( cursor, 1L, "1", true, false );
+        checkNext( cursor, 1L, "2", true, true );
+        checkNext( cursor, 1L, "3", true, true );
+        checkNext( cursor, 1L, "4", true, true );
+        checkNext( cursor, 1L, "5", false, true );
+    }
+
+
+    /**
+     * Test the browse methods on a btree containing just a leaf with duplicate values
+     */
+    @Test
+    public void testBrowseBTreeLeafNextDupsN() throws IOException, BTreeAlreadyManagedException
+    {
+        // Inject some duplicate data
+        btree.insert( 1L, "1" );
+        btree.insert( 1L, "4" );
+        btree.insert( 1L, "2" );
+        btree.insert( 2L, "3" );
+        btree.insert( 3L, "5" );
+        btree.insert( 3L, "7" );
+        btree.insert( 3L, "6" );
+
+        // Create the cursor
+        TupleCursor<Long, String> cursor = btree.browse();
+        
+        // Move forward
+        cursor.beforeFirst();
+        
+        assertFalse( cursor.hasPrev() );
+        assertTrue( cursor.hasNext() );
+        
+        checkNext( cursor, 1L, "1", true, false );
+        checkNext( cursor, 1L, "2", true, true );
+        checkNext( cursor, 1L, "4", true, true );
+        checkNext( cursor, 2L, "3", true, true );
+        checkNext( cursor, 3L, "5", true, true );
+        checkNext( cursor, 3L, "6", true, true );
+        checkNext( cursor, 3L, "7", false, true );
+    }
+
+
+    /**
+     * Test the browse methods on a btree containing just a leaf with duplicate values
+     */
+    @Test
+    public void testBrowseBTreeLeafPrevDups1() throws IOException, BTreeAlreadyManagedException
+    {
+        // Inject some duplicate data
+        btree.insert( 1L, "1" );
+        btree.insert( 1L, "4" );
+        btree.insert( 1L, "2" );
+        btree.insert( 1L, "3" );
+        btree.insert( 1L, "5" );
+
+        // Create the cursor
+        TupleCursor<Long, String> cursor = btree.browse();
+        
+        // Move backward
+        cursor.afterLast();
+        
+        assertTrue( cursor.hasPrev() );
+        assertFalse( cursor.hasNext() );
+        
+        checkPrev( cursor, 1L, "5", false, true );
+        checkPrev( cursor, 1L, "4", true, true );
+        checkPrev( cursor, 1L, "3", true, true );
+        checkPrev( cursor, 1L, "2", true, true );
+        checkPrev( cursor, 1L, "1", true, false );
+    }
+
+
+    /**
+     * Test the browse methods on a btree containing just a leaf with duplicate values
+     */
+    @Test
+    public void testBrowseBTreeLeafPrevDupsN() throws IOException, BTreeAlreadyManagedException
+    {
+        // Inject some duplicate data
+        btree.insert( 1L, "1" );
+        btree.insert( 1L, "4" );
+        btree.insert( 1L, "2" );
+        btree.insert( 2L, "3" );
+        btree.insert( 3L, "5" );
+        btree.insert( 3L, "7" );
+        btree.insert( 3L, "6" );
+
+        // Create the cursor
+        TupleCursor<Long, String> cursor = btree.browse();
+        
+        // Move backward
+        cursor.afterLast();
+        
+        assertTrue( cursor.hasPrev() );
+        assertFalse( cursor.hasNext() );
+        
+        checkPrev( cursor, 3L, "7", false, true );
+        checkPrev( cursor, 3L, "6", true, true );
+        checkPrev( cursor, 3L, "5", true, true );
+        checkPrev( cursor, 2L, "3", true, true );
+        checkPrev( cursor, 1L, "4", true, true );
+        checkPrev( cursor, 1L, "2", true, true );
+        checkPrev( cursor, 1L, "1", true, false );
+    }
+
+
+    /**
+     * Test the browse methods on a btree containing just a leaf with duplicate values
+     */
+    @Test
+    public void testBrowseBTreeNodesNextDupsN() throws IOException, BTreeAlreadyManagedException
+    {
+        // Inject some data
+        for ( long i = 1; i < 1000L; i++ )
+        {
+            for ( long j = 1; j < 10; j++ )
+            {
+                btree.insert( i, Long.toString( j ) );
+            }
+        }
+
+        // Create the cursor
+        TupleCursor<Long, String> cursor = btree.browse();
+        
+        // Move backward
+        cursor.beforeFirst();
+        
+        assertFalse( cursor.hasPrev() );
+        assertTrue( cursor.hasNext() );
+        boolean next = true;
+        boolean prev = false;
+        
+        for ( long i = 1L; i < 1000L; i++ )
+        {
+            for ( long j = 1L; j < 10L; j++ )
+            {
+                checkNext( cursor, i, Long.toString( j ), next, prev );
+                
+                if ( ( i == 1L ) && ( j == 1L ) )
+                {
+                    prev = true;
+                }
+                
+                if ( ( i == 999L ) && ( j == 8L ) )
+                {
+                    next = false;
+                }
+            }
+        }
+    }
+
+
+    /**
+     * Test the browse methods on a btree containing just a leaf with duplicate values
+     */
+    @Test
+    public void testBrowseBTreeNodesPrevDupsN() throws IOException, BTreeAlreadyManagedException
+    {
+        // Inject some data
+        long t0 = System.currentTimeMillis();
+        for ( long i = 1; i < 1000L; i++ )
+        {
+            for ( int j = 1; j < 10; j++ )
+            {
+                btree.insert( i, Long.toString( j ) );
+            }
+        }
+        long t1 = System.currentTimeMillis();
+        
+        
+        System.out.println( "Delta = " + ( t1 - t0) );
+
+        // Create the cursor
+        TupleCursor<Long, String> cursor = btree.browse();
+        
+        // Move backward
+        cursor.afterLast();
+        
+        assertTrue( cursor.hasPrev() );
+        assertFalse( cursor.hasNext() );
+        boolean next = false;
+        boolean prev = true;
+        
+        for ( long i = 999L; i > 0L; i-- )
+        {
+            for ( long j = 9L; j > 0L; j-- )
+            {
+                checkPrev( cursor, i, Long.toString( j ), next, prev );
+                
+                if ( ( i == 1L ) && ( j == 2L ) )
+                {
+                    prev = false;
+                }
+                
+                if ( ( i == 999L ) && ( j == 9L ) )
+                {
+                    next = true;
+                }
+            }
+        }
+    }
+
+    
+    private String toString( long value, int size )
+    {
+        String valueStr = Long.toString( value );
+        
+        StringBuilder sb = new StringBuilder();
+        
+        if ( size > valueStr.length() )
+        {
+            for ( int i = valueStr.length(); i < size; i++ )
+            {
+                sb.append( "0" );
+            }
+        }
+        
+        sb.append( valueStr );
+        
+        return sb.toString();
+    }
+
+    /**
+     * Test the browse methods on a btree containing just a leaf with duplicate values
+     * stored into a sub btree
+     */
+    @Test
+    public void testBrowseBTreeLeafNextDupsSubBTree1() throws IOException, BTreeAlreadyManagedException
+    {
+        // Inject some duplicate data which will be stored into a sub btree
+        for ( long i = 1L; i < 32L; i++ )
+        {
+            btree.insert( 1L, toString( i, 2 ) );
+        }
+
+        // Create the cursor
+        TupleCursor<Long, String> cursor = btree.browse();
+        
+        // Move forward
+        cursor.beforeFirst();
+        
+        assertFalse( cursor.hasPrev() );
+        assertTrue( cursor.hasNext() );
+        
+        checkNext( cursor, 1L, "01", true, false );
+        
+        for ( long i = 2L; i < 31L; i++ )
+        {
+            checkNext( cursor, 1L, toString( i, 2 ), true, true );
+        }
+        
+        checkNext( cursor, 1L, "31", false, true );
+    }
+
+    /**
+     * Test the browse methods on a btree containing just a leaf with duplicate values
+     */
+    @Test
+    public void testBrowseBTreeLeafPrevDupsSubBTree1() throws IOException, BTreeAlreadyManagedException
+    {
+        // Inject some duplicate data which will be stored into a sub btree
+        for ( long i = 1L; i < 32L; i++ )
+        {
+            btree.insert( 1L, toString( i, 2 ) );
+        }
+
+        // Create the cursor
+        TupleCursor<Long, String> cursor = btree.browse();
+        
+        // Move backward
+        cursor.afterLast();
+        
+        assertTrue( cursor.hasPrev() );
+        assertFalse( cursor.hasNext() );
+        
+        checkPrev( cursor, 1L, "31", false, true );
+        
+        for ( long i = 30L; i > 1L; i-- )
+        {
+            checkPrev( cursor, 1L, toString( i, 2 ), true, true );
+        }
+        
+        checkPrev( cursor, 1L, "01", true, false );
+    }
+}
\ No newline at end of file

Modified: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/managed/RecordManagerFreePageTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/managed/RecordManagerFreePageTest.java?rev=1539986&r1=1539985&r2=1539986&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/managed/RecordManagerFreePageTest.java (original)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/managed/RecordManagerFreePageTest.java Fri Nov  8 11:37:27 2013
@@ -170,6 +170,7 @@ public class RecordManagerFreePageTest
         TupleCursor<Long, String> cursor = btree.browse();
 
         long i = 0;
+        
         while ( cursor.hasNext() )
         {
             Tuple<Long, String> t = cursor.next();



Mime
View raw message