directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1659557 - in /directory/mavibot/trunk/mavibot/src: main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java test/java/org/apache/directory/mavibot/btree/PersistedBTreeBrowseTest.java
Date Fri, 13 Feb 2015 13:38:38 GMT
Author: elecharny
Date: Fri Feb 13 13:38:38 2015
New Revision: 1659557

URL: http://svn.apache.org/r1659557
Log:
o Fixed the browse(K,...) method, which was incorrectly positioning the cursor when the key
was not found in the BTree, and when the closest higher key was on a next page.
o Added a test to check that the browse method works

Modified:
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java
    directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBrowseTest.java

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=1659557&r1=1659556&r2=1659557&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
Fri Feb 13 13:38:38 2015
@@ -20,13 +20,14 @@
 package org.apache.directory.mavibot.btree;
 
 
+import static org.apache.directory.mavibot.btree.BTreeTypeEnum.PERSISTED_SUB;
+
 import java.io.IOException;
 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 +65,7 @@ import static org.apache.directory.mavib
     PersistedLeaf( BTree<K, V> btree, long revision, int nbElems )
     {
         super( btree, revision, nbElems );
-        if( btree.getType() != BTreeTypeEnum.PERSISTED_SUB )
+        if ( btree.getType() != BTreeTypeEnum.PERSISTED_SUB )
         {
             values = ( ValueHolder<V>[] ) Array.newInstance( PersistedValueHolder.class,
nbElems );
         }
@@ -87,11 +88,11 @@ import static org.apache.directory.mavib
             // into a copy of this page, unless the page has already be copied
             int index = -( pos + 1 );
 
-            if( isSubTree )
+            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
);
 
@@ -104,7 +105,7 @@ import static org.apache.directory.mavib
             // The current page is not full, it can contain the added element.
             // We insert it into a copied page and return the result
             Page<K, V> modifiedPage = null;
-            
+
             if ( isSubTree )
             {
                 modifiedPage = addSubTreeElement( revision, key, pos );
@@ -124,8 +125,8 @@ import static org.apache.directory.mavib
             // The Page is already full : we split it and return the overflow element,
             // after having created two pages.
             InsertResult<K, V> result = null;
-            
-            if( isSubTree )
+
+            if ( isSubTree )
             {
                 result = addAndSplitSubTree( revision, key, pos );
             }
@@ -133,7 +134,7 @@ import static org.apache.directory.mavib
             {
                 result = addAndSplit( revision, key, value, pos );
             }
-            
+
             result.addCopiedPage( this );
 
             return result;
@@ -145,7 +146,7 @@ import static org.apache.directory.mavib
      * {@inheritDoc}
      */
     @SuppressWarnings("unchecked")
-    /* no qualifier */ DeleteResult<K, V> delete( K key, V value, long revision, Page<K,
V> parent, int parentPos )
+    /* no qualifier */DeleteResult<K, V> delete( K key, V value, long revision, Page<K,
V> parent, int parentPos )
         throws IOException
     {
         // Check that the leaf is not empty
@@ -175,12 +176,13 @@ import static org.apache.directory.mavib
         boolean isNotSubTree = ( btree.getType() != PERSISTED_SUB );
 
         ValueHolder<V> valueHolder = null;
-        
-        if( isNotSubTree )
+
+        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
+        else
+        // set value to null, just incase if a non-null value passed while deleting a key
from from sub-btree
         {
             value = null;
         }
@@ -332,7 +334,7 @@ import static org.apache.directory.mavib
         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 );
@@ -412,7 +414,7 @@ import static org.apache.directory.mavib
         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 = null;
@@ -444,7 +446,7 @@ import static org.apache.directory.mavib
 
         // And copy the remaining elements
         System.arraycopy( keys, pos + 1, newLeaf.keys, pos + 1, keys.length - pos - 1 );
-        if( isNotSubTree )
+        if ( isNotSubTree )
         {
             System.arraycopy( values, pos + 1, newLeaf.values, pos + 1, values.length - pos
- 1 );
         }
@@ -475,7 +477,7 @@ import static org.apache.directory.mavib
         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 = null;
@@ -493,7 +495,7 @@ import static org.apache.directory.mavib
         {
             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 );
@@ -504,21 +506,21 @@ import static org.apache.directory.mavib
         {
             newLeaf.values[nbElems - 1] = siblingHolder;
         }
-        
+
         // Copy the keys and the values up to the deletion position,
         System.arraycopy( keys, 0, newLeaf.keys, 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 );
         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
@@ -541,7 +543,7 @@ import static org.apache.directory.mavib
         throws IOException
     {
         boolean isNotSubTree = ( btree.getType() != PERSISTED_SUB );
-        
+
         if ( keyRemoved )
         {
             // Deal with the special case of a page with only one element by skipping
@@ -733,10 +735,11 @@ import static org.apache.directory.mavib
     public TupleCursor<K, V> browse( K key, ReadTransaction<K, V> transaction,
ParentPos<K, V>[] stack, int depth )
     {
         int pos = findPos( key );
-        TupleCursor<K, V> cursor = null;
+        TupleCursor<K, V> cursor = new TupleCursor<K, V>( transaction, stack,
depth );;
 
         if ( pos < 0 )
         {
+            // The key has been found.
             pos = -( pos + 1 );
 
             // Start at the beginning of the page
@@ -746,43 +749,67 @@ import static org.apache.directory.mavib
             parentPos.valueCursor = values[pos].getCursor();
 
             stack[depth] = parentPos;
-
-            cursor = new TupleCursor<K, V>( transaction, stack, depth );
         }
         else
         {
             // The key has not been found. Select the value just above, if we have one
             if ( pos < nbElems )
             {
+                // There is at least one key above the one we are looking for.
+                // This will be the starting point.
                 ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
 
                 // Create the value cursor
                 parentPos.valueCursor = values[pos].getCursor();
 
                 stack[depth] = parentPos;
-
-                cursor = new TupleCursor<K, V>( transaction, stack, depth );
             }
             else if ( nbElems > 0 )
             {
-                // after the last element
-                ParentPos<K, V> parentPos = new ParentPos<K, V>( this, nbElems
- 1 );
-
-                // Create the value cursor
-                parentPos.valueCursor = values[nbElems - 1].getCursor();
-
-                stack[depth] = parentPos;
-
-                cursor = new TupleCursor<K, V>( transaction, stack, depth );
-
-                try
+                // We are at the end of a leaf. We have to check if we are at the end 
+                // of the tree or not
+                if ( depth == 0 )
                 {
-                    cursor.afterLast();
+                    // No children, we are at the end of the root page
+                    stack[depth] = new ParentPos<K, V>( this, pos );
+
+                    try
+                    {
+                        cursor.afterLast();
+                    }
+                    catch ( IOException e )
+                    {
+                        // TODO Auto-generated catch block
+                        e.printStackTrace();
+                    }
                 }
-                catch ( IOException e )
+                else
                 {
-                    // TODO Auto-generated catch block
-                    e.printStackTrace();
+                    boolean isLast = true;
+                    stack[depth] = new ParentPos<K, V>( this, pos );
+
+                    // Check each upper node
+                    for ( int i = depth - 2; i >= 0; i-- )
+                    {
+                        if ( stack[i].pos < stack[i].page.getNbElems() )
+                        {
+                            isLast = false;
+                            break;
+                        }
+                    }
+
+                    if ( isLast )
+                    {
+                        try
+                        {
+                            cursor.afterLast();
+                        }
+                        catch ( IOException e )
+                        {
+                            // TODO Auto-generated catch block
+                            e.printStackTrace();
+                        }
+                    }
                 }
             }
             else
@@ -849,7 +876,7 @@ import static org.apache.directory.mavib
             // It' not enough to copy the ValueHolder, we have to clone them
             // as ValueHolders are mutable
             int pos = 0;
-            
+
             for ( ValueHolder<V> valueHolder : values )
             {
                 try
@@ -861,7 +888,7 @@ import static org.apache.directory.mavib
                     // TODO Auto-generated catch block
                     e.printStackTrace();
                 }
-                
+
                 // Stop when we have copied nbElems values
                 if ( pos == nbElems )
                 {
@@ -921,7 +948,7 @@ import static org.apache.directory.mavib
         {
             replacedValue = valueHolder.replaceValueArray( value );
         }
-        
+
         // Create the result
         InsertResult<K, V> result = new ModifyResult<K, V>( newLeaf, replacedValue
);
         result.addCopiedPage( this );
@@ -1068,11 +1095,11 @@ import static org.apache.directory.mavib
      */
     public K getLeftMostKey()
     {
-        if( keys.length == 0 )
+        if ( keys.length == 0 )
         {
-            System.out.println("");
+            System.out.println( "" );
         }
-        
+
         return keys[0].getKey();
     }
 
@@ -1092,14 +1119,14 @@ import static org.apache.directory.mavib
     public Tuple<K, V> findLeftMost() throws IOException
     {
         K key = keys[0].getKey();
-        
+
         boolean isSubTree = ( btree.getType() == PERSISTED_SUB );
-        
+
         if ( isSubTree )
         {
             return new Tuple<K, V>( key, null );
         }
-        
+
         ValueCursor<V> cursor = values[0].getCursor();
 
         try
@@ -1127,11 +1154,11 @@ import static org.apache.directory.mavib
      */
     public Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException
     {
-        
+
         K key = keys[nbElems - 1].getKey();
-        
+
         boolean isSubTree = ( btree.getType() == PERSISTED_SUB );
-        
+
         if ( isSubTree )
         {
             return new Tuple<K, V>( key, null );
@@ -1244,7 +1271,7 @@ import static org.apache.directory.mavib
         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.
@@ -1342,17 +1369,17 @@ import static org.apache.directory.mavib
         return cursor;
     }
 
-    
+
     /**
      * sets the values to null
      * WARNING: only used by the internal API (especially during the bulk loading)
      */
-    /* no qualifier */ void _clearValues_()
+    /* no qualifier */void _clearValues_()
     {
         values = null;
     }
 
-    
+
     /**
      * {@inheritDoc}
      */

Modified: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBrowseTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBrowseTest.java?rev=1659557&r1=1659556&r2=1659557&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBrowseTest.java
(original)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBrowseTest.java
Fri Feb 13 13:38:38 2015
@@ -997,6 +997,7 @@ public class PersistedBTreeBrowseTest
             Tuple<Long, String> tuple = cursor.nextKey();
 
             checkTuple( tuple, i, "1" );
+            System.out.println( i );
 
             if ( i == 999L )
             {



Mime
View raw message