You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@labs.apache.org by el...@apache.org on 2012/07/01 08:00:53 UTC
svn commit: r1355850 - in /labs/mavibot/trunk/mavibot: ./
src/main/java/org/apache/mavibot/btree/
src/test/java/org/apache/mavibot/btree/
Author: elecharny
Date: Sun Jul 1 06:00:52 2012
New Revision: 1355850
URL: http://svn.apache.org/viewvc?rev=1355850&view=rev
Log:
o Removed the next/prev pointers, as we can't keep them updated when we add a new revision
o Replaced them by a stack that stores the current position on the tree when using a cursor
o Added commons-collections dependency
Added:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ParentPos.java
Modified:
labs/mavibot/trunk/mavibot/pom.xml
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
Modified: labs/mavibot/trunk/mavibot/pom.xml
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/pom.xml?rev=1355850&r1=1355849&r2=1355850&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/pom.xml (original)
+++ labs/mavibot/trunk/mavibot/pom.xml Sun Jul 1 06:00:52 2012
@@ -35,6 +35,7 @@
<properties>
<junit.version>4.10</junit.version>
+ <commons.collections.version>3.2.1</commons.collections.version>
</properties>
<dependencies>
@@ -44,6 +45,12 @@
<version>${junit.version}</version>
<scope>test</scope>
</dependency>
+
+ <dependency>
+ <groupId>commons-collections</groupId>
+ <artifactId>commons-collections</artifactId>
+ <version>${commons.collections.version}</version>
+ </dependency>
</dependencies>
<build>
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java?rev=1355850&r1=1355849&r2=1355850&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java Sun Jul 1 06:00:52 2012
@@ -23,6 +23,7 @@ import java.io.IOException;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.Comparator;
+import java.util.LinkedList;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicLong;
@@ -307,7 +308,7 @@ public class BTree<K, V>
// Fetch the root page for this revision
Page<K, V> root = roots.get( transaction.getRevision() );
- Cursor<K, V> cursor = root.browse( key, transaction );
+ Cursor<K, V> cursor = root.browse( key, transaction, new LinkedList<ParentPos<K, V>>() );
return cursor;
}
@@ -325,7 +326,9 @@ public class BTree<K, V>
// Fetch the root page for this revision
Page<K, V> root = roots.get( transaction.getRevision() );
- Cursor<K, V> cursor = root.browse( transaction );
+ LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
+
+ Cursor<K, V> cursor = root.browse( transaction, stack );
return cursor;
}
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java?rev=1355850&r1=1355849&r2=1355850&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java Sun Jul 1 06:00:52 2012
@@ -19,6 +19,8 @@
*/
package org.apache.mavibot.btree;
+import java.util.LinkedList;
+
/**
* A Cursor is used to fetch elements in a BTree and is returned by the
* @see BTree#browse method. The cursor <strng>must</strong> be closed
@@ -34,15 +36,12 @@ public class Cursor<K, V>
/** The transaction used for this cursor */
private Transaction<K, V> transaction;
- /** The current leaf */
- private Leaf<K, V> leaf;
-
- /** The current position in the leaf */
- private int pos;
-
/** The Tuple used to return the results */
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;
+
/**
* Creates a new instance of Cursor, starting on a page at a given position.
*
@@ -50,11 +49,10 @@ public class Cursor<K, V>
* @param leaf The page in which the first element is present
* @param pos The position of the first element
*/
- public Cursor( Transaction<K, V> transaction, Leaf<K, V> leaf, int pos )
+ public Cursor( Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
{
this.transaction = transaction;
- this.leaf = leaf;
- this.pos = pos;
+ this.stack = stack;
}
@@ -65,34 +63,112 @@ public class Cursor<K, V>
*/
public Tuple<K, V> next()
{
- if ( leaf == null )
+ ParentPos<K, V> parentPos = stack.getFirst();
+
+ if ( parentPos.page == null )
{
return new Tuple<K, V>();
}
- if ( pos == leaf.nbElems )
+ if ( parentPos.pos == parentPos.page.getNbElems() )
{
- if ( leaf.nextPage == null )
+ // End of the leaf. We have to go back into the stack up to the
+ // parent, and down to the leaf
+ parentPos = findNextLeaf();
+
+ if ( parentPos.page == null )
{
// This is the end : no more value
return null;
}
- else
- {
- leaf = leaf.nextPage;
- pos = 0;
- }
}
- tuple.setKey( leaf.keys[pos] );
- tuple.setValue( leaf.values[pos] );
+ Leaf<K, V> leaf = (Leaf<K, V>)(parentPos.page);
+ tuple.setKey( leaf.keys[parentPos.pos] );
+ tuple.setValue( leaf.values[parentPos.pos] );
- pos++;
+ parentPos.pos++;
return tuple;
}
+ private ParentPos<K, V> findNextLeaf()
+ {
+ while ( true )
+ {
+ ParentPos<K, V> parentPos = stack.peek();
+
+ if ( parentPos == null )
+ {
+ return null;
+ }
+
+ if ( parentPos.pos == parentPos.page.getNbElems() )
+ {
+ stack.pop();
+ continue;
+ }
+ else
+ {
+ int newPos = ++parentPos.pos;
+ ParentPos<K, V> newParentPos = parentPos;
+
+ while ( newParentPos.page instanceof Node )
+ {
+ Node<K, V> node = (Node<K, V>)newParentPos.page;
+
+ newParentPos = new ParentPos<K, V>( node.children[newPos], 0 );
+
+ stack.push( newParentPos );
+
+ newPos = 0;
+ }
+
+ return newParentPos;
+ }
+ }
+ }
+
+
+ private ParentPos<K, V> findPreviousLeaf()
+ {
+ while ( true )
+ {
+ ParentPos<K, V> parentPos = stack.peek();
+
+ if ( parentPos == null )
+ {
+ return null;
+ }
+
+ if ( parentPos.pos == 0 )
+ {
+ stack.pop();
+ continue;
+ }
+ else
+ {
+ int newPos = --parentPos.pos;
+ ParentPos<K, V> newParentPos = parentPos;
+
+ while ( newParentPos.page instanceof Node )
+ {
+ Node<K, V> node = (Node<K, V>)newParentPos.page;
+
+ newParentPos = new ParentPos<K, V>( node.children[newPos], node.children[newPos].getNbElems() );
+
+ stack.push( newParentPos );
+
+ newPos = node.getNbElems();
+ }
+
+ return newParentPos;
+ }
+ }
+ }
+
+
/**
* Find the previous key/value
*
@@ -100,24 +176,32 @@ public class Cursor<K, V>
*/
public Tuple<K, V> prev()
{
- if ( pos == 0 )
+ ParentPos<K, V> parentPos = stack.peek();
+
+ if ( parentPos.page == null )
+ {
+ return new Tuple<K, V>();
+ }
+
+ if ( parentPos.pos == 0 )
{
- if ( leaf.prevPage == null )
+ // End of the leaf. We have to go back into the stack up to the
+ // parent, and down to the leaf
+ parentPos = findPreviousLeaf();
+
+ if ( parentPos.page == null )
{
// This is the end : no more value
return null;
}
- else
- {
- leaf = leaf.prevPage;
- pos = leaf.getNbElems();
- }
}
- pos--;
+ Leaf<K, V> leaf = (Leaf<K, V>)(parentPos.page);
+
+ parentPos.pos--;
- tuple.setKey( leaf.keys[pos] );
- tuple.setValue( leaf.values[pos] );
+ tuple.setKey( leaf.keys[parentPos.pos] );
+ tuple.setValue( leaf.values[parentPos.pos] );
return tuple;
}
@@ -129,26 +213,27 @@ public class Cursor<K, V>
*/
public boolean hasNext()
{
- if ( leaf == null )
+ ParentPos<K, V> parentPos = stack.peek();
+
+ if ( parentPos.page == null )
{
return false;
}
- if ( pos < leaf.nbElems )
+ if ( parentPos.pos == parentPos.page.getNbElems() )
{
- return true;
+ // Remove the leaf from the stack
+ stack.pop();
+
+ // End of the leaf. We have to go back into the stack up to the
+ // parent, and down to the leaf
+ parentPos = findNextLeaf();
+
+ return ( parentPos != null ) && ( parentPos.page != null );
}
else
{
- if ( leaf.nextPage == null )
- {
- // This is the end : no more value
- return false;
- }
- else
- {
- return true;
- }
+ return true;
}
}
@@ -159,26 +244,27 @@ public class Cursor<K, V>
*/
public boolean hasPrev()
{
- if ( leaf == null )
+ ParentPos<K, V> parentPos = stack.peek();
+
+ if ( parentPos.page == null )
{
return false;
}
- if ( pos > 0 )
+ if ( parentPos.pos == 0 )
{
- return true;
+ // Remove the leaf from the stack
+ stack.pop();
+
+ // Start of the leaf. We have to go back into the stack up to the
+ // parent, and down to the leaf
+ parentPos = findPreviousLeaf();
+
+ return ( parentPos != null ) && ( parentPos.page != null );
}
else
{
- if ( leaf.prevPage == null )
- {
- // This is the end : no more value
- return false;
- }
- else
- {
- return true;
- }
+ return true;
}
}
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java?rev=1355850&r1=1355849&r2=1355850&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java Sun Jul 1 06:00:52 2012
@@ -19,6 +19,8 @@
*/
package org.apache.mavibot.btree;
+import java.util.LinkedList;
+
/**
* A MVCC Leaf. It stores the keys and values. It does not have any children.
*
@@ -32,12 +34,6 @@ public class Leaf<K, V> extends Abstract
/** Values associated with keys */
protected V[] values;
- /** The page that comes next to this one */
- protected Leaf<K, V> nextPage;
-
- /** The page that comes previous to this one */
- protected Leaf<K, V> prevPage;
-
/**
* Empty constructor
@@ -145,19 +141,21 @@ public class Leaf<K, V> extends Abstract
// if it has more than N/2 elements, or to merge the two pages.
// Check in both next and previous page, if they have the same parent
// and select the biggest page with the same parent to borrow an element.
- Leaf<K,V> sibling = selectSibling( parent, parentPos );
+ int siblingPos = selectSibling( (Node<K, V>)parent, parentPos );
+
+ Leaf<K, V> sibling = (Leaf<K, V>)((Node<K, V>)parent).children[siblingPos];
if ( sibling.getNbElems() == halfSize )
{
// We will merge the current page with its sibling
- DeleteResult<K, V> result = mergeWithSibling( revision, sibling, index );
+ DeleteResult<K, V> result = mergeWithSibling( revision, sibling, ( siblingPos < index), index );
return result;
}
else
{
// We can borrow the element from the sibling
- if ( sibling == prevPage )
+ if ( siblingPos < parentPos )
{
DeleteResult<K, V> result = borrowFromLeft( revision, sibling, index );
@@ -193,14 +191,14 @@ public class Leaf<K, V> extends Abstract
* @param pos The position of the removed element
* @return The new created leaf containing the sibling and the old page.
*/
- private DeleteResult<K, V> mergeWithSibling( long revision, Leaf<K, V> sibling, int pos )
+ private DeleteResult<K, V> mergeWithSibling( long revision, Leaf<K, V> sibling, boolean isLeft, int pos )
{
// Create the new page. It will contain N - 1 elements (the maximum number)
// as we merge two pages that contain N/2 elements minus the one we remove
Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, btree.pageSize - 1 );
Tuple<K, V> removedElement = new Tuple<K, V>( keys[pos], values[pos] );
- if ( sibling == prevPage )
+ if ( isLeft )
{
// The sibling is on the left
// Copy all the elements from the sibling first
@@ -273,11 +271,6 @@ public class Leaf<K, V> extends Abstract
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 );
- // Update the prev/next references
- newLeaf.prevPage = newSibling;
- newLeaf.nextPage = this.nextPage;
- newSibling.nextPage = newLeaf;
-
// Create the result
Tuple<K, V> removedElement = new Tuple<K, V>( keys[pos], values[pos] );
@@ -326,11 +319,6 @@ public class Leaf<K, V> extends Abstract
System.arraycopy( keys, pos + 1, newLeaf.keys, pos, keys.length - pos - 1 );
System.arraycopy( values, pos + 1, newLeaf.values, pos, values.length - pos - 1 );
- // Update the prev/next references
- newLeaf.prevPage = this.prevPage;
- newLeaf.nextPage = newSibling;
- newSibling.prevPage = newLeaf;
-
// Create the result
Tuple<K, V> removedElement = new Tuple<K, V>( keys[pos], values[pos] );
@@ -344,32 +332,35 @@ public class Leaf<K, V> extends Abstract
* Select the sibling (the prev or next page with the same parent) which has
* the more element assuming it's above N/2
*/
- private Leaf<K, V> selectSibling( Page<K, V> parent, int parentPos )
+ private int selectSibling( Node<K, V> parent, int parentPos )
{
if ( parentPos == 0 )
{
// The current page is referenced on the left of its parent's page :
// we will not have a previous page with the same parent
- return nextPage;
+ return 1;
}
if ( parentPos == parent.getNbElems() )
{
// The current page is referenced on the right of its parent's page :
// we will not have a next page with the same parent
- return prevPage;
+ return -1;
}
+
+ Page<K, V> prevPage = parent.children[parentPos - 1];
+ Page<K, V> nextPage = parent.children[parentPos + 1];
int prevPageSize = prevPage.getNbElems();
int nextPageSize = nextPage.getNbElems();
if ( prevPageSize >= nextPageSize )
{
- return prevPage;
+ return parentPos - 1;
}
else
{
- return nextPage;
+ return parentPos + 1;
}
}
@@ -439,33 +430,35 @@ public class Leaf<K, V> extends Abstract
/**
* {@inheritDoc}
*/
- public Cursor<K, V> browse( K key, Transaction<K, V> transaction )
+ public Cursor<K, V> browse( K key, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
{
int pos = findPos( key );
Cursor<K, V> cursor = null;
if ( pos < 0 )
{
+ int index = - ( pos + 1 );
+
// The first element has been found. Create the cursor
- cursor = new Cursor<K, V>( transaction, this, - ( pos + 1 ) );
+ stack.push( new ParentPos<K, V>( this, index ) );
+
+ cursor = new Cursor<K, V>( transaction, stack );
}
else
{
// The key has not been found. Select the value just above, if we have one
if ( pos < nbElems )
{
- cursor = new Cursor<K, V>( transaction, this, pos );
+ stack.push( new ParentPos<K, V>( this, pos ) );
+
+ cursor = new Cursor<K, V>( transaction, stack );
}
else
{
- if ( nextPage != null )
- {
- cursor = new Cursor<K, V>( transaction, nextPage, 0 );
- }
- else
- {
- cursor = new Cursor<K, V>( transaction, null, -1 );
- }
+ // Not found : return a null cursor
+ stack.push( new ParentPos<K, V>( this, -1 ) );
+
+ return new Cursor<K, V>( transaction, stack );
}
}
@@ -476,20 +469,24 @@ public class Leaf<K, V> extends Abstract
/**
* {@inheritDoc}
*/
- public Cursor<K, V> browse( Transaction<K, V> transaction )
+ public Cursor<K, V> browse( Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
{
int pos = 0;
Cursor<K, V> cursor = null;
if ( nbElems == 0 )
{
- // The tree is empty, we have nothing to return
- return new Cursor<K, V>( transaction, null, -1 );
+ // The tree is empty, it's the root, we have nothing to return
+ stack.push( new ParentPos<K, V>( null, -1 ) );
+
+ return new Cursor<K, V>( transaction, stack );
}
else
{
// Start at the beginning of the page
- cursor = new Cursor<K, V>( transaction, this, pos );
+ stack.push( new ParentPos<K, V>( this, pos ) );
+
+ cursor = new Cursor<K, V>( transaction, stack );
}
return cursor;
@@ -536,10 +533,6 @@ public class Leaf<K, V> extends Abstract
V oldValue = newLeaf.values[pos];
newLeaf.values[pos] = value;
- // and update the prev/next references
- newLeaf.prevPage = this.prevPage;
- newLeaf.nextPage = this.nextPage;
-
// Create the result
InsertResult<K, V> result = new ModifyResult<K, V>( newLeaf, oldValue );
@@ -582,10 +575,6 @@ public class Leaf<K, V> extends Abstract
System.arraycopy( keys, pos, newLeaf.keys, pos + 1, keys.length - pos );
System.arraycopy( values, pos, newLeaf.values, pos + 1, values.length - pos );
}
-
- // Update the prev/next references
- newLeaf.prevPage = this.prevPage;
- newLeaf.nextPage = this.nextPage;
return newLeaf;
}
@@ -664,12 +653,6 @@ public class Leaf<K, V> extends Abstract
System.arraycopy( values, pos, rightLeaf.values, rightPos + 1, nbElems -pos );
}
- // and update the prev/next references
- leftLeaf.prevPage = this.prevPage;
- leftLeaf.nextPage = rightLeaf;
- rightLeaf.prevPage = leftLeaf;
- rightLeaf.nextPage = this.nextPage;
-
// Get the pivot
K pivot = rightLeaf.keys[0];
@@ -690,27 +673,6 @@ public class Leaf<K, V> extends Abstract
sb.append( "Leaf[" );
sb.append( super.toString() );
- sb.append( ", prev:" );
-
- if ( prevPage == null )
- {
- sb.append( "null" );
- }
- else
- {
- sb.append( prevPage.revision );
- }
-
- sb.append( ", next:" );
-
- if ( nextPage == null )
- {
- sb.append( "null" );
- }
- else
- {
- sb.append( nextPage.revision );
- }
sb.append ( "] -> {" );
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java?rev=1355850&r1=1355849&r2=1355850&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java Sun Jul 1 06:00:52 2012
@@ -19,6 +19,8 @@
*/
package org.apache.mavibot.btree;
+import java.util.LinkedList;
+
/**
* A MVCC Node. It stores the keys and references to its children page. It does not
* contain any value.
@@ -166,7 +168,7 @@ public class Node<K, V> extends Abstract
/**
* {@inheritDoc}
*/
- public Cursor<K, V> browse( K key, Transaction<K, V> transaction )
+ public Cursor<K, V> browse( K key, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
{
int pos = findPos( key );
@@ -174,11 +176,16 @@ public class Node<K, V> extends Abstract
{
// Here, if we have found the key in the node, then we must go down into
// the right child, not the left one
- return children[- pos ].browse( key, transaction );
+
+ stack.push( new ParentPos<K, V>( this, -pos ) );
+
+ return children[-pos].browse( key, transaction, stack );
}
else
{
- return children[pos].browse( key, transaction );
+ stack.push( new ParentPos<K, V>( this, pos ) );
+
+ return children[pos].browse( key, transaction, stack );
}
}
@@ -186,9 +193,11 @@ public class Node<K, V> extends Abstract
/**
* {@inheritDoc}
*/
- public Cursor<K, V> browse( Transaction<K, V> transaction )
+ public Cursor<K, V> browse( Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
{
- return children[0].browse( transaction );
+ stack.push( new ParentPos<K, V>( this, 0 ) );
+
+ return children[0].browse( transaction, stack );
}
@@ -397,13 +406,13 @@ public class Node<K, V> extends Abstract
{
// Start with the first child
sb.append( children[0].getId() ).append( "-r" ).append( children[0].getRevision() );
- sb.append( "{" ).append( children[0] ).append( "}" );
+ //sb.append( "{" ).append( children[0] ).append( "}" );
for ( int i = 0; i < nbElems; i++ )
{
sb.append( "|<" ).append( keys[i] ).append( ">|" ).
append( children[i + 1].getId() ).append( "-r" ).append( children[i + 1].getRevision() );
- sb.append( "{" ).append( children[i + 1] ).append( "}" );
+ //sb.append( "{" ).append( children[i + 1] ).append( "}" );
}
}
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java?rev=1355850&r1=1355849&r2=1355850&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java Sun Jul 1 06:00:52 2012
@@ -19,6 +19,8 @@
*/
package org.apache.mavibot.btree;
+import java.util.LinkedList;
+
/**
* A MVCC Page interface.
*
@@ -84,18 +86,20 @@ public interface Page<K, V>
*
* @param key The key we are looking for.
* @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 next elements
*/
- Cursor<K, V> browse( K key, Transaction<K, V> transaction );
+ Cursor<K, V> browse( K key, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack );
/**
* browse the whole tree, and create 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 next elements
*/
- Cursor<K, V> browse( Transaction<K, V> transaction );
+ Cursor<K, V> browse( Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack );
/**
Added: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ParentPos.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ParentPos.java?rev=1355850&view=auto
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ParentPos.java (added)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ParentPos.java Sun Jul 1 06:00:52 2012
@@ -0,0 +1,51 @@
+/*
+ * 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.mavibot.btree;
+
+/**
+ *
+ * @author <a href="mailto:labs@laps.apache.org">Mavibot labs Project</a>
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+ */
+public class ParentPos<K, V>
+{
+ /** The page we are browsing */
+ /* No qualifier*/ Page<K, V> page;
+
+ /** The current position in the page */
+ /* No qualifier*/ int pos;
+
+ public ParentPos( Page<K, V> page, int pos )
+ {
+ this.page = page;
+ this.pos = pos;
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ return "<" + pos + "," + page + ">";
+ }
+}
\ No newline at end of file
Modified: labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java?rev=1355850&r1=1355849&r2=1355850&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java (original)
+++ labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java Sun Jul 1 06:00:52 2012
@@ -172,10 +172,6 @@ public class LeafTest
Leaf<Long, String> target = new Leaf<Long, String>( btree );
Leaf<Long, String> right = new Leaf<Long, String>( btree );
- parent.children[0] = left;
- parent.children[1] = target;
- parent.children[2] = right;
-
// Fill the left page
left = insert( left, 1L, "v1" );
left = insert( left, 2L, "v2" );
@@ -195,15 +191,9 @@ public class LeafTest
right = insert( right, 12L, "v12" );
right = insert( right, 13L, "v13" );
- // Create the links between leaves
- left.prevPage = null;
- left.nextPage = target;
-
- target.prevPage = left;
- target.nextPage = right;
-
- right.prevPage = target;
- right.nextPage = null;
+ parent.children[0] = left;
+ parent.children[1] = target;
+ parent.children[2] = right;
// Update the parent
parent.keys[0] = 6L;
@@ -237,9 +227,6 @@ public class LeafTest
assertEquals( Long.valueOf( 2L ), leftSibling.keys[1] );
assertEquals( Long.valueOf( 3L ), leftSibling.keys[2] );
assertEquals( Long.valueOf( 4L ), leftSibling.keys[3] );
-
- assertEquals( leftSibling, newLeaf.prevPage );
- assertEquals( newLeaf.prevPage, leftSibling );
}
@@ -255,10 +242,6 @@ public class LeafTest
Leaf<Long, String> target = new Leaf<Long, String>( btree );
Leaf<Long, String> right = new Leaf<Long, String>( btree );
- parent.children[0] = left;
- parent.children[1] = target;
- parent.children[2] = right;
-
// Fill the left page
left = insert( left, 1L, "v1" );
left = insert( left, 2L, "v2" );
@@ -278,15 +261,9 @@ public class LeafTest
right = insert( right, 13L, "v13" );
right = insert( right, 14L, "v14" );
- // Create the links between leaves
- left.prevPage = null;
- left.nextPage = target;
-
- target.prevPage = left;
- target.nextPage = right;
-
- right.prevPage = target;
- right.nextPage = null;
+ parent.children[0] = left;
+ parent.children[1] = target;
+ parent.children[2] = right;
// Update the parent
parent.keys[0] = 6L;
@@ -320,9 +297,6 @@ public class LeafTest
assertEquals( Long.valueOf( 12L ), rightSibling.keys[1] );
assertEquals( Long.valueOf( 13L ), rightSibling.keys[2] );
assertEquals( Long.valueOf( 14L ), rightSibling.keys[3] );
-
- assertEquals( rightSibling, newLeaf.nextPage );
- assertEquals( newLeaf.nextPage, rightSibling );
}
@@ -338,10 +312,6 @@ public class LeafTest
Leaf<Long, String> target = new Leaf<Long, String>( btree );
Leaf<Long, String> right = new Leaf<Long, String>( btree );
- parent.children[0] = left;
- parent.children[1] = target;
- parent.children[2] = right;
-
// Fill the left page
left = insert( left, 1L, "v1" );
left = insert( left, 2L, "v2" );
@@ -359,16 +329,10 @@ public class LeafTest
right = insert( right, 10L, "v10" );
right = insert( right, 11L, "v11" );
right = insert( right, 12L, "v12" );
-
- // Create the links between leaves
- left.prevPage = null;
- left.nextPage = target;
-
- target.prevPage = left;
- target.nextPage = right;
- right.prevPage = target;
- right.nextPage = null;
+ parent.children[0] = left;
+ parent.children[1] = target;
+ parent.children[2] = right;
// Update the parent
parent.keys[0] = 5L;
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@labs.apache.org
For additional commands, e-mail: commits-help@labs.apache.org