You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by el...@apache.org on 2015/03/01 05:49:36 UTC
svn commit: r1663024 -
/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java
Author: elecharny
Date: Sun Mar 1 04:49:36 2015
New Revision: 1663024
URL: http://svn.apache.org/r1663024
Log:
Refactored the PersistedLeaf browse(K) method. That should fix DIRSERVER-2047
Modified:
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.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=1663024&r1=1663023&r2=1663024&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 Sun Mar 1 04:49:36 2015
@@ -743,16 +743,17 @@ import org.apache.directory.mavibot.btre
return new EmptyTupleCursor<K, V>();
}
- // Create the cursor we will use
+ // The cursor we will return
TupleCursor<K, V> cursor = new TupleCursor<K, V>( transaction, stack, depth );
// Depending on the position, we will proceed differently :
// 1) if the key is found in the page, the cursor will be
// set to this position.
- // 2) The value has not been found, but is in the middle of the
- // page (ie, other keys above teh one we are looking for exist),
+ // 2) The key has not been found, but is in the middle of the
+ // page (ie, other keys above the one we are looking for exist),
// the cursor will be set to the current position
- // 3) The key has not been found,
+ // 3) The key has not been found, and we are at the end of
+ // the page. We have to fetch the next key in yhe B-tree
if ( pos < 0 )
{
// The key has been found.
@@ -766,6 +767,8 @@ import org.apache.directory.mavibot.btre
// And store this position in the stack
stack[depth] = parentPos;
+
+ return cursor;
}
else
{
@@ -781,57 +784,88 @@ import org.apache.directory.mavibot.btre
parentPos.valueCursor = values[pos].getCursor();
stack[depth] = parentPos;
+
+ return cursor;
}
else
{
- // We are at the end of a leaf. We have to check if we are at the end
- // of the tree or not
+ // We are at the end of a leaf. We have to see if we have other
+ // keys on the right.
if ( depth == 0 )
{
// No children, we are at the end of the root page
stack[depth] = new ParentPos<K, V>( this, pos );
+ // As we are done, set the cursor at the end
try
{
cursor.afterLast();
}
- catch ( IOException ioe )
+ catch ( IOException e )
{
- // Not likely to happen
+ e.printStackTrace();
}
+
+ return cursor;
}
else
{
+ // We have to find the adjacent key in the B-tree
boolean isLast = true;
stack[depth] = new ParentPos<K, V>( this, pos );
- // Check each upper node
- for ( int i = depth - 2; i >= 0; i-- )
+ // Check each upper node, starting from the direct parent
+ int stackIndex = depth - 1;
+
+ for ( int i = stackIndex; i >= 0; i-- )
{
if ( stack[i].pos < stack[i].page.getNbElems() )
{
isLast = false;
break;
}
+
+ stackIndex--;
}
if ( isLast )
{
+ // We don't have any more elements
try
{
cursor.afterLast();
}
catch ( IOException e )
{
- // TODO Auto-generated catch block
e.printStackTrace();
}
+
+ return cursor;
+ }
+ else
+ {
+ // go down the tree again, but one position to the right
+ stack[stackIndex].pos++;
+
+ for ( int i = stackIndex + 1; i < depth - 1; i++ )
+ {
+ ParentPos<K, V> parentPos = new ParentPos<K, V>( this, 0 );
+
+ stack[i] = parentPos;
+ }
+
+ ParentPos<K, V> parentPos = new ParentPos<K, V>( this, 0 );
+
+ // Create the value cursor
+ parentPos.valueCursor = values[0].getCursor();
+
+ stack[depth - 1] = parentPos;
+
+ return cursor;
}
}
}
}
-
- return cursor;
}