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 2013/12/10 21:42:17 UTC
svn commit: r1549961 [2/3] - in /directory/mavibot/trunk/mavibot/src:
main/java/org/apache/directory/mavibot/btree/
main/java/org/apache/directory/mavibot/btree/managed/
main/java/org/apache/directory/mavibot/btree/memory/
test/java/org/apache/director...
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Leaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Leaf.java?rev=1549961&r1=1549960&r2=1549961&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Leaf.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Leaf.java Tue Dec 10 20:42:16 2013
@@ -20,13 +20,17 @@
package org.apache.directory.mavibot.btree.memory;
-import static org.apache.directory.mavibot.btree.memory.InternalUtil.setDupsContainer;
-
import java.io.IOException;
import java.lang.reflect.Array;
+import org.apache.directory.mavibot.btree.DeleteResult;
+import org.apache.directory.mavibot.btree.InsertResult;
+import org.apache.directory.mavibot.btree.Page;
+import org.apache.directory.mavibot.btree.ParentPos;
+import org.apache.directory.mavibot.btree.Transaction;
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;
@@ -42,7 +46,7 @@ import org.apache.directory.mavibot.btre
/* No qualifier */class Leaf<K, V> extends AbstractPage<K, V>
{
/** Values associated with keys */
- protected ElementHolder<V, K, V>[] values;
+ protected ValueHolder<V>[] values;
/**
@@ -69,15 +73,7 @@ import org.apache.directory.mavibot.btre
{
super( btree, revision, nbElems );
- if ( btree.isAllowDuplicates() )
- {
- this.values = ( MultipleMemoryHolder<K, V>[] ) Array.newInstance( MultipleMemoryHolder.class,
- nbElems );
- }
- else
- {
- this.values = ( MemoryHolder<K, V>[] ) Array.newInstance( MemoryHolder.class, nbElems );
- }
+ this.values = ( ValueHolder<V>[] ) Array.newInstance( ValueHolder.class, nbElems );
}
@@ -156,81 +152,35 @@ import org.apache.directory.mavibot.btre
int index = -( pos + 1 );
- if ( btree.isAllowDuplicates() )
- {
- MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) values[index];
-
- //FIXME should the internal sub-tree should be deleted from RM?
-
- V existingVal = mvHolder.getValue();
+ ValueHolder<V> valueHolder = values[index];
- if ( value == null ) // this is a case to delete entire <K,sub-BTree> or <K,single-V>
- {
- removedElement = new Tuple<K, V>( keys[index], existingVal ); // the entire value was removed
- keyRemoved = true;
- }
- else
+ if ( value == null )
+ {
+ // we have to delete the whole value
+ removedElement = new Tuple<K, V>( keys[index], valueHolder.getCursor().next() ); // the entire value was removed
+ keyRemoved = true;
+ }
+ else
+ {
+ if ( valueHolder.contains( value ) )
{
- if ( mvHolder.isSingleValue() )
+ // this is a case to delete entire <K,sub-BTree> or <K,single-V>
+ if ( valueHolder.size() == 1 )
{
- if ( btree.getValueSerializer().compare( value, existingVal ) == 0 )
- {
- removedElement = new Tuple<K, V>( keys[index], existingVal ); // the entire value was removed
- keyRemoved = true;
- }
- else
- // value is not found
- {
- return NotPresentResult.NOT_PRESENT;
- }
+ // Ok, we can remove the value
+ removedElement = new Tuple<K, V>( keys[index], null ); // the entire value was removed
+ keyRemoved = true;
}
else
{
- BTree<V, V> dups = ( BTree<V, V> ) existingVal;
-
- if ( dups.hasKey( value ) )
- {
- dups.delete( value );
-
- if ( dups.getNbElems() == 0 )
- {
- keyRemoved = true;
- }
- else
- {
- if ( dups.getNbElems() == 1 )
- {
- //FIXME switch to single value mode
- mvHolder.switchToSingleValMode();
- }
- }
-
- removedElement = new Tuple<K, V>( keys[index], value ); // we deleted only one value (even if it is from a tree of size 1)
- }
- else
- // value is not found
- {
- return NotPresentResult.NOT_PRESENT;
- }
+ // Update the ValueHolder
+ valueHolder.remove( value );
+ removedElement = new Tuple<K, V>( keys[index], value ); // the entire value was removed
}
}
- }
- else
- {
- V existing = values[index].getValue();
-
- if ( ( ( existing == null ) && ( value == null ) ) || ( value == null ) )
- {
- removedElement = new Tuple<K, V>( keys[index], existing );
- keyRemoved = true;
- }
- else if ( btree.getValueSerializer().compare( value, existing ) == 0 )
- {
- removedElement = new Tuple<K, V>( keys[index], value );
- keyRemoved = true;
- }
else
{
+ // Not found
return NotPresentResult.NOT_PRESENT;
}
}
@@ -273,7 +223,7 @@ import org.apache.directory.mavibot.btre
// 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.
int siblingPos = selectSibling( ( Node<K, V> ) parent, parentPos );
- Leaf<K, V> sibling = ( Leaf<K, V> ) ( ( ( Node<K, V> ) parent ).children[siblingPos].getValue() );
+ Leaf<K, V> sibling = ( Leaf<K, V> ) ( ( ( Node<K, V> ) parent ).children[siblingPos] );
if ( sibling.getNbElems() == halfSize )
{
@@ -406,7 +356,7 @@ import org.apache.directory.mavibot.btre
{
// The sibling is on the left, borrow the rightmost element
K siblingKey = sibling.keys[sibling.getNbElems() - 1];
- ElementHolder<V, K, V> siblingValue = sibling.values[sibling.getNbElems() - 1];
+ ValueHolder<V> siblingValue = sibling.values[sibling.getNbElems() - 1];
// Create the new sibling, with one less element at the end
Leaf<K, V> newSibling = ( Leaf<K, V> ) sibling.copy( revision, sibling.getNbElems() - 1 );
@@ -453,7 +403,7 @@ import org.apache.directory.mavibot.btre
{
// The sibling is on the left, borrow the rightmost element
K siblingKey = sibling.keys[0];
- ElementHolder<V, K, V> siblingHolder = sibling.values[0];
+ ValueHolder<V> siblingHolder = sibling.values[0];
// Create the new sibling
Leaf<K, V> newSibling = new Leaf<K, V>( btree, revision, sibling.getNbElems() - 1 );
@@ -533,24 +483,11 @@ import org.apache.directory.mavibot.btre
if ( pos < 0 )
{
- if ( btree.isAllowDuplicates() )
- {
- MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) values[-( pos + 1 )];
- if ( mvHolder.isSingleValue() )
- {
- return mvHolder.getValue();
- }
- else
- {
- // always return the first value for get(key) when duplicates are allowed
- BTree<V, V> dupTree = ( BTree<V, V> ) mvHolder.getValue();
- return dupTree.rootPage.getLeftMostKey();
- }
- }
-
- V v = values[-( pos + 1 )].getValue();
-
- return v;
+ ValueHolder<V> valueHolder = ( ValueHolder<V> ) values[-( pos + 1 )];
+
+ V value = valueHolder.getCursor().next();
+
+ return value;
}
else
{
@@ -563,7 +500,7 @@ import org.apache.directory.mavibot.btre
* {@inheritDoc}
*/
@Override
- public DuplicateKeyVal<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
+ public ValueCursor<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
{
if ( !btree.isAllowDuplicates() )
{
@@ -574,14 +511,9 @@ import org.apache.directory.mavibot.btre
if ( pos < 0 )
{
- MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) values[-( pos + 1 )];
-
- if ( mvHolder.isSingleValue() )
- {
- return new DuplicateKeyVal<V>( mvHolder.getValue() );
- }
+ ValueHolder<V> valueHolder = ( ValueHolder<V> ) values[-( pos + 1 )];
- return new DuplicateKeyVal<V>( ( BTree<V, V> ) mvHolder.getValue() );
+ return valueHolder.getCursor();
}
else
{
@@ -613,25 +545,9 @@ import org.apache.directory.mavibot.btre
if ( pos < 0 )
{
- if ( btree.isAllowDuplicates() )
- {
- MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) values[-( pos + 1 )];
- if ( mvHolder.isSingleValue() )
- {
- return ( btree.getValueSerializer().compare( value, mvHolder.getValue() ) == 0 );
- }
- else
- {
- // always return the first value for get(key) when duplicates are allowed
- BTree<V, V> dupTree = ( ( BTree<V, V> ) mvHolder.getValue() );
- return dupTree.hasKey( value );
- }
- }
- else
- {
- V v = values[-( pos + 1 )].getValue();
- return ( btree.getValueSerializer().compare( value, v ) == 0 );
- }
+ ValueHolder<V> valueHolder = values[-( pos + 1 )];
+
+ return valueHolder.contains( value );
}
else
{
@@ -643,7 +559,7 @@ import org.apache.directory.mavibot.btre
/**
* {@inheritDoc}
*/
- public ElementHolder<V, K, V> getValue( int pos )
+ public ValueHolder<V> getValue( int pos )
{
if ( pos < nbElems )
{
@@ -661,7 +577,7 @@ import org.apache.directory.mavibot.btre
* @param pos The position in the values array
* @param value the value to inject
*/
- public void setValue( int pos, ElementHolder<V, K, V> value )
+ public void setValue( int pos, ValueHolder<V> value )
{
values[pos] = value;
}
@@ -677,11 +593,14 @@ import org.apache.directory.mavibot.btre
if ( pos < 0 )
{
- int index = -( pos + 1 );
+ pos = -( pos + 1 );
+
+ // Start at the beginning of the page
+ ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
+
+ // Create the value cursor
+ parentPos.valueCursor = values[pos].getCursor();
- // The first element has been found. Create the cursor
- ParentPos<K, V> parentPos = new ParentPos<K, V>( this, index );
- setDupsContainer( parentPos, btree );
stack[depth] = parentPos;
cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
@@ -692,18 +611,42 @@ import org.apache.directory.mavibot.btre
if ( pos < nbElems )
{
ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
- setDupsContainer( parentPos, btree );
+
+ // Create the value cursor
+ parentPos.valueCursor = values[pos].getCursor();
+
stack[depth] = parentPos;
cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
}
- else
+ else if ( nbElems > 0 )
{
- // Not found : return a null cursor
- ParentPos<K, V> parentPos = new ParentPos<K, V>( null, -1 );
+ // 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;
- return new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
+ cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
+
+ try
+ {
+ cursor.afterLast();
+ }
+ catch ( IOException e )
+ {
+ // TODO Auto-generated catch block
+ e.printStackTrace();
+ }
+ }
+ else
+ {
+ // Not found, because there are no elements : return a null cursor
+ stack[depth] = null;
+
+ cursor = new TupleCursorImpl<K, V>( btree, transaction, null, 0 );
}
}
@@ -731,7 +674,8 @@ import org.apache.directory.mavibot.btre
// Start at the beginning of the page
ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
- setDupsContainer( parentPos, btree );
+ // Create the value cursor
+ parentPos.valueCursor = values[0].getCursor();
stack[depth] = parentPos;
@@ -782,54 +726,26 @@ import org.apache.directory.mavibot.btre
newLeaf = ( Leaf<K, V> ) copy( revision, nbElems );
}
- V oldValue = null;
+ // Get the previous value from the leaf (it's a copy)
+ ValueHolder<V> valueHolder = newLeaf.values[pos];
+ V replacedValue = null;
- if ( btree.isAllowDuplicates() )
+ if ( !valueHolder.contains( value ) )
{
- MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) newLeaf.values[pos];
-
- if ( mvHolder.isSingleValue() )
- {
- V singleVal = mvHolder.getValue();
-
- // see if the given value already matches
- if ( btree.getValueSerializer().compare( value, singleVal ) == 0 )
- {
- oldValue = value;
- }
- else
- // create a sub-tree
- {
- mvHolder.createAndSwitchToSubTree();
- }
- }
-
- // if oldValue is null then the given 'value' is different and needs to be added
- // ('oldValue' will be not null if it matched with the 'singleValue', see above nested if block )
- if ( oldValue == null )
- {
- BTree<V, V> dupValues = ( BTree<V, V> ) mvHolder.getValue();
-
- // return value will always be null here
- if ( !dupValues.hasKey( value ) )
- {
- dupValues.insert( value, null, 0 );
- }
- else
- {
- oldValue = value;
- }
- }
+ valueHolder.add( value );
+ newLeaf.values[pos] = valueHolder;
}
else
{
- // Now we can inject the value
- oldValue = newLeaf.values[pos].getValue();
- newLeaf.values[pos] = btree.createValueHolder( value );
+ // As strange as it sounds, we need to remove the value to reinject it.
+ // There are cases where the value retrieval just use one part of the
+ // value only (typically for LDAP Entries, where we use the DN)
+ replacedValue = valueHolder.remove( value );
+ valueHolder.add( value );
}
// Create the result
- InsertResult<K, V> result = new ModifyResult<K, V>( newLeaf, oldValue );
+ InsertResult<K, V> result = new ModifyResult<K, V>( newLeaf, replacedValue );
result.addCopiedPage( this );
return result;
@@ -852,19 +768,7 @@ import org.apache.directory.mavibot.btre
Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems + 1 );
// Atm, store the value in memory
-
- ElementHolder valueHolder = null;
-
- if ( btree.isAllowDuplicates() )
- {
- valueHolder = new MultipleMemoryHolder<K, V>( btree, value );
- }
- else
- {
- valueHolder = new MemoryHolder<K, V>( btree, value );
- }
-
- //ValueHolder<K, V> valueHolder = btree.createHolder( value );
+ ValueHolder<V> valueHolder = new ValueHolder<V>( btree, value );
// Deal with the special case of an empty page
if ( nbElems == 0 )
@@ -912,7 +816,7 @@ import org.apache.directory.mavibot.btre
int middle = btree.getPageSize() >> 1;
Leaf<K, V> leftLeaf = null;
Leaf<K, V> rightLeaf = null;
- ElementHolder<V, K, V> valueHolder = btree.createValueHolder( value );
+ ValueHolder<V> valueHolder = new ValueHolder<V>( btree, value );
// Determinate where to store the new value
if ( pos <= middle )
@@ -1001,15 +905,7 @@ import org.apache.directory.mavibot.btre
{
V val = null;
- if ( btree.isAllowDuplicates() )
- {
- BTree<V, V> dupTree = ( BTree<V, V> ) values[0].getValue();
- val = dupTree.rootPage.getLeftMostKey();
- }
- else
- {
- val = values[0].getValue();
- }
+ val = values[0].getCursor().next();
return new Tuple<K, V>( keys[0], val );
}
@@ -1022,15 +918,9 @@ import org.apache.directory.mavibot.btre
{
V val = null;
- if ( btree.isAllowDuplicates() )
- {
- BTree<V, V> dupTree = ( BTree<V, V> ) values[nbElems - 1].getValue();
- val = dupTree.rootPage.getRightMostKey();
- }
- else
- {
- val = values[nbElems - 1].getValue();
- }
+ ValueCursor<V> valueCursor = values[nbElems - 1].getCursor();
+ valueCursor.afterLast();
+ val = valueCursor.prev();
return new Tuple<K, V>( keys[nbElems - 1], val );
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/MergedWithSiblingResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/MergedWithSiblingResult.java?rev=1549961&r1=1549960&r2=1549961&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/MergedWithSiblingResult.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/MergedWithSiblingResult.java Tue Dec 10 20:42:16 2013
@@ -22,6 +22,7 @@ package org.apache.directory.mavibot.btr
import java.util.List;
+import org.apache.directory.mavibot.btree.Page;
import org.apache.directory.mavibot.btree.Tuple;
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/ModifyResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/ModifyResult.java?rev=1549961&r1=1549960&r2=1549961&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/ModifyResult.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/ModifyResult.java Tue Dec 10 20:42:16 2013
@@ -22,6 +22,9 @@ package org.apache.directory.mavibot.btr
import java.util.List;
+import org.apache.directory.mavibot.btree.InsertResult;
+import org.apache.directory.mavibot.btree.Page;
+
/**
* The result of an insert operation, when the child has not been split. It contains the
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java?rev=1549961&r1=1549960&r2=1549961&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java Tue Dec 10 20:42:16 2013
@@ -24,8 +24,14 @@ import java.io.IOException;
import java.lang.reflect.Array;
import java.util.List;
+import org.apache.directory.mavibot.btree.DeleteResult;
+import org.apache.directory.mavibot.btree.InsertResult;
+import org.apache.directory.mavibot.btree.Page;
+import org.apache.directory.mavibot.btree.ParentPos;
+import org.apache.directory.mavibot.btree.Transaction;
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;
@@ -42,7 +48,7 @@ import org.apache.directory.mavibot.btre
/* No qualifier */class Node<K, V> extends AbstractPage<K, V>
{
/** Children pages associated with keys. */
- protected ElementHolder<Page<K, V>, K, V>[] children;
+ protected Page<K, V>[] children;
/**
@@ -60,7 +66,7 @@ import org.apache.directory.mavibot.btre
super( btree, revision, nbElems );
// Create the children array
- children = ( ElementHolder<Page<K, V>, K, V>[] ) Array.newInstance( ElementHolder.class, nbElems + 1 );
+ children = ( Page<K, V>[] ) Array.newInstance( Page.class, nbElems + 1 );
}
@@ -81,41 +87,7 @@ import org.apache.directory.mavibot.btre
super( btree, revision, 1 );
// Create the children array, and store the left and right children
- children = ( MemoryHolder[] ) Array.newInstance( MemoryHolder.class,
- btree.getPageSize() + 1 );
-
- children[0] = btree.createPageHolder( leftPage );
- children[1] = btree.createPageHolder( rightPage );
-
- // Create the keys array and store the pivot into it
- // We get the type of array to create from the btree
- // Yes, this is an hack...
- Class<?> keyType = btree.getKeyType();
- keys = ( K[] ) Array.newInstance( keyType, btree.getPageSize() );
-
- keys[0] = key;
- }
-
-
- /**
- * Creates a new Node which will contain only one key, with references to
- * a left and right page. This is a specific constructor used by the btree
- * when the root was full when we added a new value.
- *
- * @param btree the parent BTree
- * @param revision the Node revision
- * @param key The new key
- * @param leftPage The left page
- * @param rightPage The right page
- */
- @SuppressWarnings("unchecked")
- /* No qualifier */Node( BTree<K, V> btree, long revision, K key, ElementHolder<Page<K, V>, K, V> leftPage,
- ElementHolder<Page<K, V>, K, V> rightPage )
- {
- super( btree, revision, 1 );
-
- // Create the children array, and store the left and right children
- children = ( ElementHolder<Page<K, V>, K, V>[] ) Array.newInstance( MemoryHolder.class,
+ children = ( Page[] ) Array.newInstance( Page.class,
btree.getPageSize() + 1 );
children[0] = leftPage;
@@ -147,7 +119,7 @@ import org.apache.directory.mavibot.btre
}
// Get the child page into which we will insert the <K, V> tuple
- Page<K, V> child = children[pos].getValue();
+ Page<K, V> child = children[pos];
// and insert the <K, V> into this child
InsertResult<K, V> result = child.insert( revision, key, value );
@@ -210,11 +182,11 @@ import org.apache.directory.mavibot.btre
if ( found )
{
- newPage.children[index + 1] = createHolder( modifiedPage );
+ newPage.children[index + 1] = modifiedPage;
}
else
{
- newPage.children[index] = createHolder( modifiedPage );
+ newPage.children[index] = modifiedPage;
}
if ( pos < 0 )
@@ -281,7 +253,7 @@ import org.apache.directory.mavibot.btre
// Create the new sibling, with one less element at the beginning
Node<K, V> newSibling = new Node<K, V>( btree, revision, sibling.getNbElems() - 1 );
- K siblingKey = sibling.children[0].getValue().getLeftMostKey();
+ K siblingKey = sibling.children[0].getLeftMostKey();
// Copy the keys and children of the old sibling in the new sibling
System.arraycopy( sibling.keys, 1, newSibling.keys, 0, newSibling.getNbElems() );
@@ -305,7 +277,7 @@ import org.apache.directory.mavibot.btre
// Inject the modified page
Page<K, V> modifiedPage = mergedResult.getModifiedPage();
- newNode.children[0] = createHolder( modifiedPage );
+ newNode.children[0] = modifiedPage;
// Copy the children
System.arraycopy( children, 2, newNode.children, 1, nbElems - 1 );
@@ -335,7 +307,7 @@ import org.apache.directory.mavibot.btre
// Inject the modified page
Page<K, V> modifiedPage = mergedResult.getModifiedPage();
- newNode.children[index - 1] = createHolder( modifiedPage ); // 6
+ newNode.children[index - 1] = modifiedPage; // 6
}
// Create the result
@@ -364,7 +336,7 @@ import org.apache.directory.mavibot.btre
Node<K, V> sibling, int pos ) throws IOException
{
// The sibling is on the left, borrow the rightmost element
- Page<K, V> siblingChild = sibling.children[sibling.nbElems].getValue();
+ Page<K, V> siblingChild = sibling.children[sibling.nbElems];
// Create the new sibling, with one less element at the end
Node<K, V> newSibling = new Node<K, V>( btree, revision, sibling.getNbElems() - 1 );
@@ -378,7 +350,7 @@ import org.apache.directory.mavibot.btre
Node<K, V> newNode = new Node<K, V>( btree, revision, nbElems );
// Sets the first children
- newNode.children[0] = createHolder( siblingChild ); //1
+ newNode.children[0] = siblingChild; //1
int index = Math.abs( pos );
@@ -388,13 +360,13 @@ import org.apache.directory.mavibot.btre
System.arraycopy( keys, 1, newNode.keys, 1, nbElems - 1 );
Page<K, V> modifiedPage = mergedResult.getModifiedPage();
- newNode.children[1] = createHolder( modifiedPage );
+ newNode.children[1] = modifiedPage;
System.arraycopy( children, 2, newNode.children, 2, nbElems - 1 );
}
else
{
// Set the first key
- newNode.keys[0] = children[0].getValue().getLeftMostKey(); //2
+ newNode.keys[0] = children[0].getLeftMostKey(); //2
if ( index > 2 )
{
@@ -419,7 +391,7 @@ import org.apache.directory.mavibot.btre
// Insert the modified page
Page<K, V> modifiedPage = mergedResult.getModifiedPage();
- newNode.children[index] = createHolder( modifiedPage ); // 7
+ newNode.children[index] = modifiedPage; // 7
}
// Create the result
@@ -469,14 +441,14 @@ import org.apache.directory.mavibot.btre
System.arraycopy( keys, 1, newNode.keys, half + 1, half - 1 );
Page<K, V> modifiedPage = mergedResult.getModifiedPage();
- newNode.children[half + 1] = createHolder( modifiedPage );
+ newNode.children[half + 1] = modifiedPage;
System.arraycopy( children, 2, newNode.children, half + 2, half - 1 );
}
else
{
// Copy the left part of the node keys up to the deletion point
// Insert the new key
- newNode.keys[half] = children[0].getValue().getLeftMostKey(); // 3
+ newNode.keys[half] = children[0].getLeftMostKey(); // 3
if ( index > 2 )
{
@@ -497,7 +469,7 @@ import org.apache.directory.mavibot.btre
// Inject the new merged child
Page<K, V> modifiedPage = mergedResult.getModifiedPage();
- newNode.children[half + index] = createHolder( modifiedPage ); //8
+ newNode.children[half + index] = modifiedPage; //8
}
}
else
@@ -510,7 +482,7 @@ import org.apache.directory.mavibot.btre
// Insert the first child
Page<K, V> modifiedPage = mergedResult.getModifiedPage();
- newNode.children[0] = createHolder( modifiedPage );
+ newNode.children[0] = modifiedPage;
// Copy the node children
System.arraycopy( children, 2, newNode.children, 1, half - 1 );
@@ -532,7 +504,7 @@ import org.apache.directory.mavibot.btre
// Inject the modified children
Page<K, V> modifiedPage = mergedResult.getModifiedPage();
- newNode.children[index - 1] = createHolder( modifiedPage ); // 7
+ newNode.children[index - 1] = modifiedPage; // 7
// Add the remaining node's key if needed
if ( index < half )
@@ -582,12 +554,12 @@ import org.apache.directory.mavibot.btre
if ( found )
{
index = -( pos + 1 );
- child = children[-pos].getValue();
+ child = children[-pos];
deleteResult = child.delete( revision, key, value, this, -pos );
}
else
{
- child = children[pos].getValue();
+ child = children[pos];
deleteResult = child.delete( revision, key, value, this, pos );
}
@@ -651,7 +623,7 @@ import org.apache.directory.mavibot.btre
// a sibling, or we will have to merge two pages
int siblingPos = selectSibling( ( Node<K, V> ) parent, parentPos );
- Node<K, V> sibling = ( Node<K, V> ) ( ( ( Node<K, V> ) parent ).children[siblingPos].getValue() );
+ Node<K, V> sibling = ( Node<K, V> ) ( ( ( Node<K, V> ) parent ).children[siblingPos] );
if ( sibling.getNbElems() > halfSize )
{
@@ -714,8 +686,8 @@ import org.apache.directory.mavibot.btre
newPage.keys[pos + 1] = modifiedSibling.findLeftMost().getKey();
// Update the children
- newPage.children[pos + 1] = createHolder( modifiedPage );
- newPage.children[pos + 2] = createHolder( modifiedSibling );
+ newPage.children[pos + 1] = modifiedPage;
+ newPage.children[pos + 2] = modifiedSibling;
}
else
{
@@ -723,8 +695,8 @@ import org.apache.directory.mavibot.btre
newPage.keys[pos] = modifiedPage.findLeftMost().getKey();
// Update the children
- newPage.children[pos] = createHolder( modifiedSibling );
- newPage.children[pos + 1] = createHolder( modifiedPage );
+ newPage.children[pos] = modifiedSibling;
+ newPage.children[pos + 1] = modifiedPage;
}
}
else
@@ -735,8 +707,8 @@ import org.apache.directory.mavibot.btre
newPage.keys[pos] = modifiedSibling.findLeftMost().getKey();
// Update the children
- newPage.children[pos] = createHolder( modifiedPage );
- newPage.children[pos + 1] = createHolder( modifiedSibling );
+ newPage.children[pos] = modifiedPage;
+ newPage.children[pos + 1] = modifiedSibling;
}
else
{
@@ -744,8 +716,8 @@ import org.apache.directory.mavibot.btre
newPage.keys[pos - 1] = modifiedPage.findLeftMost().getKey();
// Update the children
- newPage.children[pos - 1] = createHolder( modifiedSibling );
- newPage.children[pos] = createHolder( modifiedPage );
+ newPage.children[pos - 1] = modifiedSibling;
+ newPage.children[pos] = modifiedPage;
}
}
@@ -782,7 +754,7 @@ import org.apache.directory.mavibot.btre
// Copy the keys and the children
System.arraycopy( keys, 1, newNode.keys, 0, newNode.nbElems );
Page<K, V> modifiedPage = mergedResult.getModifiedPage();
- newNode.children[0] = createHolder( modifiedPage );
+ newNode.children[0] = modifiedPage;
System.arraycopy( children, 2, newNode.children, 1, nbElems - 1 );
}
else
@@ -804,7 +776,7 @@ import org.apache.directory.mavibot.btre
System.arraycopy( children, 0, newNode.children, 0, index + 1 );
Page<K, V> modifiedPage = mergedResult.getModifiedPage();
- newNode.children[index + 1] = createHolder( modifiedPage );
+ newNode.children[index + 1] = modifiedPage;
if ( index < nbElems - 2 )
{
@@ -833,11 +805,11 @@ import org.apache.directory.mavibot.btre
{
// 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].getValue().get( key );
+ return children[-pos].get( key );
}
else
{
- return children[pos].getValue().get( key );
+ return children[pos].get( key );
}
}
@@ -846,7 +818,7 @@ import org.apache.directory.mavibot.btre
* {@inheritDoc}
*/
@Override
- public DuplicateKeyVal<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
+ public ValueCursor<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
{
int pos = findPos( key );
@@ -854,11 +826,11 @@ import org.apache.directory.mavibot.btre
{
// 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].getValue().getValues( key );
+ return children[-pos].getValues( key );
}
else
{
- return children[pos].getValue().getValues( key );
+ return children[pos].getValues( key );
}
}
@@ -875,11 +847,11 @@ import org.apache.directory.mavibot.btre
{
// 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].getValue().hasKey( key );
+ return children[-pos].hasKey( key );
}
else
{
- Page<K, V> page = children[pos].getValue();
+ Page<K, V> page = children[pos];
if ( page == null )
{
@@ -903,11 +875,11 @@ import org.apache.directory.mavibot.btre
{
// 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].getValue().contains( key, value );
+ return children[-pos].contains( key, value );
}
else
{
- return children[pos].getValue().contains( key, value );
+ return children[pos].contains( key, value );
}
}
@@ -918,7 +890,7 @@ import org.apache.directory.mavibot.btre
* @param pos The position in the values array
* @param value the value to inject
*/
- public void setValue( int pos, ElementHolder<Page<K, V>, K, V> value )
+ public void setValue( int pos, Page<K, V> value )
{
children[pos] = value;
}
@@ -931,7 +903,7 @@ import org.apache.directory.mavibot.btre
{
if ( pos < nbElems + 1 )
{
- return children[pos].getValue();
+ return children[pos];
}
else
{
@@ -956,7 +928,7 @@ import org.apache.directory.mavibot.btre
// We first stack the current page
stack[depth++] = new ParentPos<K, V>( this, pos );
- Page<K, V> page = children[pos].getValue();
+ Page<K, V> page = children[pos];
return page.browse( key, transaction, stack, depth );
}
@@ -970,7 +942,7 @@ import org.apache.directory.mavibot.btre
{
stack[depth++] = new ParentPos<K, V>( this, 0 );
- Page<K, V> page = children[0].getValue();
+ Page<K, V> page = children[0];
return page.browse( transaction, stack, depth );
}
@@ -996,7 +968,7 @@ import org.apache.directory.mavibot.btre
// to point on the modified child
Page<K, V> modifiedPage = result.getModifiedPage();
- ( ( Node<K, V> ) newPage ).children[pos] = createHolder( modifiedPage );
+ ( ( Node<K, V> ) newPage ).children[pos] = modifiedPage;
// We can return the result, where we update the modifiedPage,
// to avoid the creation of a new object
@@ -1009,19 +981,6 @@ import org.apache.directory.mavibot.btre
/**
- * Creates a new holder contaning a reference to a Page
- *
- * @param page The page we will refer to
- * @return A holder contaning a reference to the child page
- * @throws IOException If we have an error while trying to access the page
- */
- private ElementHolder<Page<K, V>, K, V> createHolder( Page<K, V> page ) throws IOException
- {
- return btree.createPageHolder( page );
- }
-
-
- /**
* Adds a new key into a copy of the current page at a given position. We return the
* modified page. The new page will have one more key than the current page.
*
@@ -1053,8 +1012,8 @@ import org.apache.directory.mavibot.btre
// If the BTree is managed, we now have to write the modified page on disk
// and to add this page to the list of modified pages
- newNode.children[pos] = createHolder( leftPage );
- newNode.children[pos + 1] = createHolder( rightPage );
+ newNode.children[pos] = leftPage;
+ newNode.children[pos + 1] = rightPage;
// And copy the remaining keys and children
if ( nbElems > 0 )
@@ -1109,8 +1068,8 @@ import org.apache.directory.mavibot.btre
// Add the new element
newLeftPage.keys[pos] = pivot;
- newLeftPage.children[pos] = createHolder( leftPage );
- newLeftPage.children[pos + 1] = createHolder( rightPage );
+ newLeftPage.children[pos] = leftPage;
+ newLeftPage.children[pos + 1] = rightPage;
// And copy the remaining elements minus the new pivot
System.arraycopy( keys, pos, newLeftPage.keys, pos + 1, middle - pos - 1 );
@@ -1133,12 +1092,12 @@ import org.apache.directory.mavibot.btre
// Copy the keys and the children up to the insertion position (here, middle)
System.arraycopy( keys, 0, newLeftPage.keys, 0, middle );
System.arraycopy( children, 0, newLeftPage.children, 0, middle );
- newLeftPage.children[middle] = createHolder( leftPage );
+ newLeftPage.children[middle] = leftPage;
// And process the right page now
System.arraycopy( keys, middle, newRightPage.keys, 0, middle );
System.arraycopy( children, middle + 1, newRightPage.children, 1, middle );
- newRightPage.children[0] = createHolder( rightPage );
+ newRightPage.children[0] = rightPage;
// Create the result
InsertResult<K, V> result = new SplitResult<K, V>( copiedPages, pivot, newLeftPage, newRightPage );
@@ -1158,8 +1117,8 @@ import org.apache.directory.mavibot.btre
// Add the new element
newRightPage.keys[pos - middle - 1] = pivot;
- newRightPage.children[pos - middle - 1] = createHolder( leftPage );
- newRightPage.children[pos - middle] = createHolder( rightPage );
+ newRightPage.children[pos - middle - 1] = leftPage;
+ newRightPage.children[pos - middle] = rightPage;
// And copy the remaining elements minus the new pivot
System.arraycopy( keys, pos, newRightPage.keys, pos - middle, nbElems - pos );
@@ -1199,7 +1158,7 @@ import org.apache.directory.mavibot.btre
*/
public K getLeftMostKey() throws EndOfFileExceededException, IOException
{
- return children[0].getValue().getLeftMostKey();
+ return children[0].getLeftMostKey();
}
@@ -1212,10 +1171,10 @@ import org.apache.directory.mavibot.btre
if ( children[index] != null )
{
- return children[index].getValue().getRightMostKey();
+ return children[index].getRightMostKey();
}
- return children[nbElems - 1].getValue().getRightMostKey();
+ return children[nbElems - 1].getRightMostKey();
}
@@ -1224,7 +1183,7 @@ import org.apache.directory.mavibot.btre
*/
public Tuple<K, V> findLeftMost() throws EndOfFileExceededException, IOException
{
- return children[0].getValue().findLeftMost();
+ return children[0].findLeftMost();
}
@@ -1233,7 +1192,7 @@ import org.apache.directory.mavibot.btre
*/
public Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException
{
- return children[nbElems].getValue().findRightMost();
+ return children[nbElems].findRightMost();
}
@@ -1248,39 +1207,32 @@ import org.apache.directory.mavibot.btre
sb.append( super.toString() );
sb.append( "] -> {" );
- try
+ if ( nbElems > 0 )
{
- if ( nbElems > 0 )
+ // Start with the first child
+ if ( children[0] == null )
{
- // Start with the first child
- if ( children[0] == null )
+ sb.append( "null" );
+ }
+ else
+ {
+ sb.append( 'r' ).append( children[0].getRevision() );
+ }
+
+ for ( int i = 0; i < nbElems; i++ )
+ {
+ sb.append( "|<" ).append( keys[i] ).append( ">|" );
+
+ if ( children[i + 1] == null )
{
sb.append( "null" );
}
else
{
- sb.append( 'r' ).append( children[0].getValue().getRevision() );
- }
-
- for ( int i = 0; i < nbElems; i++ )
- {
- sb.append( "|<" ).append( keys[i] ).append( ">|" );
-
- if ( children[i + 1] == null )
- {
- sb.append( "null" );
- }
- else
- {
- sb.append( 'r' ).append( children[i + 1].getValue().getRevision() );
- }
+ sb.append( 'r' ).append( children[i + 1].getRevision() );
}
}
}
- catch ( IOException ioe )
- {
- // Do nothing
- }
sb.append( "}" );
@@ -1297,22 +1249,15 @@ import org.apache.directory.mavibot.btre
if ( nbElems > 0 )
{
- try
- {
- // Start with the first child
- sb.append( children[0].getValue().dumpPage( tabs + " " ) );
+ // Start with the first child
+ sb.append( children[0].dumpPage( tabs + " " ) );
- for ( int i = 0; i < nbElems; i++ )
- {
- sb.append( tabs );
- sb.append( "<" );
- sb.append( keys[i] ).append( ">\n" );
- sb.append( children[i + 1].getValue().dumpPage( tabs + " " ) );
- }
- }
- catch ( IOException ioe )
+ for ( int i = 0; i < nbElems; i++ )
{
- // Do nothing
+ sb.append( tabs );
+ sb.append( "<" );
+ sb.append( keys[i] ).append( ">\n" );
+ sb.append( children[i + 1].dumpPage( tabs + " " ) );
}
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/NotPresentResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/NotPresentResult.java?rev=1549961&r1=1549960&r2=1549961&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/NotPresentResult.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/NotPresentResult.java Tue Dec 10 20:42:16 2013
@@ -20,6 +20,8 @@
package org.apache.directory.mavibot.btree.memory;
+import org.apache.directory.mavibot.btree.DeleteResult;
+import org.apache.directory.mavibot.btree.Page;
import org.apache.directory.mavibot.btree.Tuple;
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/RemoveResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/RemoveResult.java?rev=1549961&r1=1549960&r2=1549961&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/RemoveResult.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/RemoveResult.java Tue Dec 10 20:42:16 2013
@@ -22,6 +22,7 @@ package org.apache.directory.mavibot.btr
import java.util.List;
+import org.apache.directory.mavibot.btree.Page;
import org.apache.directory.mavibot.btree.Tuple;
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/SplitResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/SplitResult.java?rev=1549961&r1=1549960&r2=1549961&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/SplitResult.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/SplitResult.java Tue Dec 10 20:42:16 2013
@@ -22,6 +22,9 @@ package org.apache.directory.mavibot.btr
import java.util.List;
+import org.apache.directory.mavibot.btree.InsertResult;
+import org.apache.directory.mavibot.btree.Page;
+
/**
* The result of an insert operation, when the page has been split. It contains
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/TupleCursorImpl.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/TupleCursorImpl.java?rev=1549961&r1=1549960&r2=1549961&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/TupleCursorImpl.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/TupleCursorImpl.java Tue Dec 10 20:42:16 2013
@@ -20,13 +20,12 @@
package org.apache.directory.mavibot.btree.memory;
-import static org.apache.directory.mavibot.btree.memory.InternalUtil.changeNextDupsContainer;
-import static org.apache.directory.mavibot.btree.memory.InternalUtil.changePrevDupsContainer;
-import static org.apache.directory.mavibot.btree.memory.InternalUtil.setDupsContainer;
-
import java.io.IOException;
import java.util.NoSuchElementException;
+import org.apache.directory.mavibot.btree.Page;
+import org.apache.directory.mavibot.btree.ParentPos;
+import org.apache.directory.mavibot.btree.Transaction;
import org.apache.directory.mavibot.btree.Tuple;
import org.apache.directory.mavibot.btree.TupleCursor;
import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
@@ -57,9 +56,6 @@ public class TupleCursorImpl<K, V> imple
/** The stack's depth */
private int depth = 0;
- /** The BTree we are walking */
- private BTree<K, V> btree;
-
private boolean allowDuplicates;
@@ -73,92 +69,131 @@ public class TupleCursorImpl<K, V> imple
{
this.transaction = transaction;
this.stack = stack;
- this.btree = btree;
this.allowDuplicates = btree.isAllowDuplicates();
this.depth = depth;
}
/**
- * Find the next key/value
- *
- * @return A Tuple containing the found key and value
- * @throws IOException
- * @throws EndOfFileExceededException
+ * Closes the cursor, thus releases the associated transaction
*/
- public Tuple<K, V> next() throws EndOfFileExceededException, IOException
+ public void close()
+ {
+ transaction.close();
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public long getRevision()
+ {
+ return transaction.getRevision();
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public long getCreationDate()
+ {
+ return transaction.getCreationDate();
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public void afterLast() throws IOException
{
// First check that we have elements in the BTree
if ( ( stack == null ) || ( stack.length == 0 ) )
{
- throw new NoSuchElementException( "No tuple present" );
+ return;
}
- ParentPos<K, V> parentPos = stack[depth];
+ Page<K, V> child = null;
- if ( parentPos.page == null )
+ for ( int i = 0; i < depth; i++ )
{
- // This is the end : no more value
- throw new NoSuchElementException( "No more tuples present" );
+ ParentPos<K, V> parentPos = stack[i];
+
+ if ( child != null )
+ {
+ parentPos.page = child;
+ parentPos.pos = ((Node<K, V>)child).nbElems;
+ }
+ else
+ {
+ // We have N+1 children if the page is a Node, so we don't decrement the nbElems field
+ parentPos.pos = ((Node<K, V>)parentPos.page).nbElems;
+ }
+
+ child = ((Node<K, V>)parentPos.page).children[parentPos.pos];
}
+
+ // and leaf
+ ParentPos<K, V> parentPos = stack[depth];
- if ( parentPos.pos == parentPos.page.getNbElems() )
+ if ( child == null )
{
- // End of the leaf. We have to go back into the stack up to the
- // parent, and down to the leaf
- parentPos = findNextParentPos();
-
- // we also need to check for the type of page cause
- // findNextParentPos will never return a null ParentPos
- if ( parentPos.page == null || ( parentPos.page instanceof Node ) )
- {
- // This is the end : no more value
- throw new NoSuchElementException( "No more tuples present" );
- }
+ parentPos.pos = ((Leaf<K, V>)parentPos.page).nbElems - 1;
+ }
+ else
+ {
+ parentPos.page = child;
+ parentPos.pos = ((Leaf<K, V>)child).nbElems - 1;
}
- // can happen if next() is called after prev()
- if ( parentPos.pos == BEFORE_FIRST )
+ parentPos.valueCursor = ((Leaf<K, V>)parentPos.page).values[parentPos.pos].getCursor();
+ parentPos.valueCursor.afterLast();
+ parentPos.pos = AFTER_LAST;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public void beforeFirst() throws IOException
+ {
+ // First check that we have elements in the BTree
+ if ( ( stack == null ) || ( stack.length == 0 ) )
{
- parentPos.pos = 0;
+ return;
}
- Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
- tuple.setKey( leaf.keys[parentPos.pos] );
+ Page<K, V> child = null;
- if ( allowDuplicates )
+ for ( int i = 0; i < depth; i++ )
{
- MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) leaf.values[parentPos.pos];
+ ParentPos<K, V> parentPos = stack[i];
+ parentPos.pos = 0;
- if ( mvHolder.isSingleValue() )
+ if ( child != null )
{
- tuple.setValue( mvHolder.getValue() );
- parentPos.pos++;
+ parentPos.page = child;
}
- else
- {
- setDupsContainer( parentPos, btree );
- tuple.setValue( parentPos.valueCursor.rootPage.getKey( parentPos.dupPos ) );
- parentPos.dupPos++;
+ child = ((Node<K, V>)parentPos.page).children[0];
+ }
- if ( parentPos.valueCursor.getNbElems() == parentPos.dupPos )
- {
- parentPos.pos++;
- changeNextDupsContainer( parentPos, btree );
- }
- }
+ // and leaf
+ ParentPos<K, V> parentPos = stack[depth];
+ parentPos.pos = BEFORE_FIRST;
+
+ if ( child != null )
+ {
+ parentPos.page = child;
}
- else
+
+ if ( parentPos.valueCursor != null )
{
- tuple.setValue( leaf.values[parentPos.pos].getValue() );
- parentPos.pos++;
+ parentPos.valueCursor = ((Leaf<K, V>)parentPos.page).values[0].getCursor();
+ parentPos.valueCursor.beforeFirst();
}
-
- return tuple;
}
-
-
+
+
/**
* Find the leaf containing the following elements.
*
@@ -184,7 +219,7 @@ public class TupleCursorImpl<K, V> imple
// is not the last one
ParentPos<K, V> parentPos = stack[currentDepth];
- if ( parentPos.pos == parentPos.page.getNbElems() )
+ if ( parentPos.pos + 1 > parentPos.page.getNbElems() )
{
// No more element on the right : go up
currentDepth--;
@@ -193,36 +228,32 @@ public class TupleCursorImpl<K, V> imple
{
// We can pick the next element at this level
parentPos.pos++;
- child = ((Node<K, V>)parentPos.page).children[parentPos.pos].getValue();
+ child = ((Node<K, V>)parentPos.page).children[parentPos.pos];
// and go down the tree through the nodes
while ( currentDepth < depth - 1 )
{
currentDepth++;
parentPos = stack[currentDepth];
- parentPos.page = child;
parentPos.pos = 0;
- child = ((Node<K, V>)parentPos.page).children[parentPos.pos].getValue();
+ parentPos.page = child;
+ child = ((Node<K, V>)child).children[0];
}
// and the leaf
parentPos = stack[depth];
- parentPos.pos = 0;
parentPos.page = child;
-
- if ( allowDuplicates )
- {
- changeNextDupsContainer( parentPos, btree );
- }
+ parentPos.pos = 0;
+ parentPos.valueCursor = ((Leaf<K, V>)child).values[0].getCursor();
return parentPos;
}
}
-
+
return null;
}
-
-
+
+
/**
* Find the leaf containing the previous elements.
*
@@ -257,7 +288,7 @@ public class TupleCursorImpl<K, V> imple
{
// We can pick the next element at this level
parentPos.pos--;
- child = ((Node<K, V>)parentPos.page).children[parentPos.pos].getValue();
+ child = ((Node<K, V>)parentPos.page).children[parentPos.pos];
// and go down the tree through the nodes
while ( currentDepth < depth - 1 )
@@ -266,18 +297,16 @@ public class TupleCursorImpl<K, V> imple
parentPos = stack[currentDepth];
parentPos.pos = child.getNbElems();
parentPos.page = child;
- child = ((Node<K, V>)parentPos.page).children[((Node<K, V>)parentPos.page).nbElems].getValue();
+ child = ((Node<K, V>)parentPos.page).children[((Node<K, V>)parentPos.page).nbElems];
}
// and the leaf
parentPos = stack[depth];
- parentPos.pos = child.getNbElems();
+ parentPos.pos = child.getNbElems() - 1;
parentPos.page = child;
-
- if ( allowDuplicates )
- {
- changePrevDupsContainer( parentPos, btree );
- }
+ ValueHolder<V> valueHolder = ((Leaf<K, V>)parentPos.page).values[parentPos.pos];
+ parentPos.valueCursor = valueHolder.getCursor();
+ parentPos.valueCursor.afterLast();
return parentPos;
}
@@ -288,131 +317,6 @@ public class TupleCursorImpl<K, V> imple
/**
- * Find the previous key/value
- *
- * @return A Tuple containing the found key and value
- * @throws IOException
- * @throws EndOfFileExceededException
- */
- public Tuple<K, V> prev() throws EndOfFileExceededException, IOException
- {
- // First check that we have elements in the BTree
- if ( ( stack == null ) || ( stack.length == 0 ) )
- {
- throw new NoSuchElementException( "No tuple present" );
- }
-
- ParentPos<K, V> parentPos = stack[depth];
-
- if ( parentPos.page == null )
- {
- // This is the end : no more value
- throw new NoSuchElementException( "No more tuples present" );
- }
-
- if ( ( parentPos.pos == 0 ) && ( parentPos.dupPos == 0 ) )
- {
- // End of the leaf. We have to go back into the stack up to the
- // parent, and down to the leaf
- 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 ) )
- {
- // This is the end : no more value
- throw new NoSuchElementException( "No more tuples present" );
- }
- }
-
- Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
-
- if ( allowDuplicates )
- {
- boolean posDecremented = false;
-
- // can happen if prev() was called after next()
- if ( parentPos.pos == parentPos.page.getNbElems() )
- {
- parentPos.pos--;
- posDecremented = true;
- }
-
- MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) leaf.values[parentPos.pos];
-
- boolean prevHasSubtree = false;
- // if the current key has only one value then advance to previous position
- if ( mvHolder.isSingleValue() )
- {
- if ( !posDecremented )
- {
- parentPos.pos--;
- mvHolder = ( MultipleMemoryHolder<K, V> ) leaf.values[parentPos.pos];
- posDecremented = true;
- }
-
- if ( mvHolder.isSingleValue() )
- {
- tuple.setKey( leaf.keys[parentPos.pos] );
- tuple.setValue( mvHolder.getValue() );
- }
- else
- {
- prevHasSubtree = true;
- }
- }
- else
- {
- prevHasSubtree = true;
- }
-
- if ( prevHasSubtree )
- {
- setDupsContainer( parentPos, btree );
-
- if ( parentPos.dupPos == parentPos.valueCursor.getNbElems() )
- {
- parentPos.dupPos--;
- }
- else if ( parentPos.dupPos == 0 )
- {
- changePrevDupsContainer( parentPos, btree );
- parentPos.pos--;
-
- if ( parentPos.valueCursor != null )
- {
- parentPos.dupPos--;
- }
- }
- else
- {
- parentPos.dupPos--;
- }
-
- tuple.setKey( leaf.keys[parentPos.pos] );
-
- if ( parentPos.valueCursor != null )
- {
- tuple.setValue( parentPos.valueCursor.rootPage.getKey( parentPos.dupPos ) );
- }
- else
- {
- tuple.setValue( leaf.values[parentPos.pos].getValue() );
- }
- }
- }
- else
- {
- parentPos.pos--;
- tuple.setKey( leaf.keys[parentPos.pos] );
- tuple.setValue( leaf.values[parentPos.pos].getValue() );
- }
-
- return tuple;
- }
-
-
- /**
* {@inheritDoc}
*/
public boolean hasNext() throws EndOfFileExceededException, IOException
@@ -422,7 +326,8 @@ public class TupleCursorImpl<K, V> imple
{
return false;
}
-
+
+ // Take the leaf and check if we have no mare values
ParentPos<K, V> parentPos = stack[depth];
if ( parentPos.page == null )
@@ -436,7 +341,7 @@ public class TupleCursorImpl<K, V> imple
return false;
}
- if ( parentPos.pos < parentPos.page.getNbElems() )
+ if ( parentPos.pos < parentPos.page.getNbElems() - 1 )
{
// Not the last position, we have a next value
return true;
@@ -444,9 +349,8 @@ public class TupleCursorImpl<K, V> imple
else
{
// Check if we have some more value
- if ( allowDuplicates && ( parentPos.valueCursor != null ) && ( parentPos.dupPos < parentPos.valueCursor.getNbElems() - 1 ) )
+ if ( parentPos.valueCursor.hasNext() )
{
- // We have some more values
return true;
}
@@ -476,50 +380,132 @@ public class TupleCursorImpl<K, V> imple
/**
- * {@inheritDoc}
+ * {@inheritDoc}
*/
- public boolean hasPrev() throws EndOfFileExceededException, IOException
+ public boolean hasNextKey() throws EndOfFileExceededException, IOException
{
// First check that we have elements in the BTree
if ( ( stack == null ) || ( stack.length == 0 ) )
{
+ // This is the end : no more key
return false;
}
- // 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
+ // This is the end : no more key
return false;
}
-
- if ( parentPos.pos > 0 )
+
+ if ( parentPos.pos == ( parentPos.page.getNbElems() - 1 ) )
{
- // get out, we have values on the left
- return true;
+ // End of the leaf. We have to go back into the stack up to the
+ // parent, and down to the next leaf
+ return hasNextParentPos();
}
-
else
{
- // Check that we are not before the first value
- if ( parentPos.pos == BEFORE_FIRST )
- {
- return false;
- }
-
- // Check if we have some more value
- if ( allowDuplicates && ( parentPos.dupPos > 0 ) )
- {
- return true;
- }
+ 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 )
+
+ /**
+ * Tells if there is a next ParentPos
+ *
+ * @return the new ParentPos instance, or null if we have no following leaf
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ private boolean hasNextParentPos() throws EndOfFileExceededException, IOException
+ {
+ if ( depth == 0 )
+ {
+ // No need to go any further, there is only one leaf in the btree
+ return false;
+ }
+
+ int currentDepth = depth - 1;
+ Page<K, V> child = null;
+
+ // First, go up the tree until we find a Node which has some element on the right
+ while ( currentDepth >= 0 )
+ {
+ // We first go up the tree, until we reach a page whose current position
+ // is not the last one
+ ParentPos<K, V> parentPos = stack[currentDepth];
+
+ if ( parentPos.pos + 1 > parentPos.page.getNbElems() )
+ {
+ // No more element on the right : go up
+ currentDepth--;
+ }
+ else
+ {
+ // We can pick the next element at this level
+ child = ((Node<K, V>)parentPos.page).children[parentPos.pos + 1];
+
+ // and go down the tree through the nodes
+ while ( currentDepth < depth - 1 )
+ {
+ currentDepth++;
+ child = ((Node<K, V>)child).children[0];
+ }
+
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean hasPrev() throws EndOfFileExceededException, IOException
+ {
+ // First check that we have elements in the BTree
+ if ( ( stack == null ) || ( stack.length == 0 ) )
+ {
+ return false;
+ }
+
+ // Take the leaf and check if we have no mare values
+ ParentPos<K, V> parentPos = stack[depth];
+
+ if ( parentPos.page == null )
+ {
+ // Empty BTree, get out
+ return false;
+ }
+
+ if ( parentPos.pos > 0 )
+ {
+ // get out, we have values on the left
+ return true;
+ }
+ else
+ {
+ // Check that we are not before the first value
+ if ( parentPos.pos == BEFORE_FIRST )
+ {
+ return false;
+ }
+
+ // Check if we have some more value
+ if ( parentPos.valueCursor.hasPrev() )
+ {
+ 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];
@@ -540,78 +526,173 @@ public class TupleCursorImpl<K, V> imple
/**
- * Closes the cursor, thus releases the associated transaction
+ * {@inheritDoc}
*/
- public void close()
+ public boolean hasPrevKey() throws EndOfFileExceededException, IOException
{
- transaction.close();
- }
+ // First check that we have elements in the BTree
+ if ( ( stack == null ) || ( stack.length == 0 ) )
+ {
+ // This is the end : no more key
+ return false;
+ }
+ ParentPos<K, V> parentPos = stack[depth];
+ if ( parentPos.page == null )
+ {
+ // This is the end : no more key
+ return false;
+ }
+
+ if ( parentPos.pos == 0 )
+ {
+ // Beginning of the leaf. We have to go back into the stack up to the
+ // parent, and down to the leaf
+ return hasPrevParentPos();
+ }
+ else
+ {
+ return true;
+ }
+ }
+
+
/**
- * @return The revision this cursor is based on
+ * Tells if there is a prev ParentPos
+ *
+ * @return the new ParentPos instance, or null if we have no previous leaf
+ * @throws IOException
+ * @throws EndOfFileExceededException
*/
- public long getRevision()
+ private boolean hasPrevParentPos() throws EndOfFileExceededException, IOException
{
- return transaction.getRevision();
- }
+ if ( depth == 0 )
+ {
+ // No need to go any further, there is only one leaf in the btree
+ return false;
+ }
+ int currentDepth = depth - 1;
+ Page<K, V> child = null;
- /**
- * @return The creation date for this cursor
- */
- public long getCreationDate()
- {
- return transaction.getCreationDate();
+ // 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[currentDepth];
+
+ if ( parentPos.pos == 0 )
+ {
+ // No more element on the left : go up
+ currentDepth--;
+ }
+ else
+ {
+ // We can pick the previous element at this level
+ child = ((Node<K, V>)parentPos.page).children[parentPos.pos - 1];
+
+ // and go down the tree through the nodes
+ while ( currentDepth < depth - 1 )
+ {
+ currentDepth++;
+ child = ((Node<K, V>)child).children[child.getNbElems()];
+ }
+
+ return true;
+ }
+ }
+
+ return false;
}
/**
* {@inheritDoc}
*/
- public boolean hasNextKey() throws EndOfFileExceededException, IOException
+ public Tuple<K, V> next() throws EndOfFileExceededException, IOException
{
// First check that we have elements in the BTree
if ( ( stack == null ) || ( stack.length == 0 ) )
{
- // This is the end : no more key
- return false;
+ throw new NoSuchElementException( "No tuple present" );
}
ParentPos<K, V> parentPos = stack[depth];
- if ( parentPos.page == null )
+ if ( ( parentPos.page == null ) || ( parentPos.pos == AFTER_LAST ) )
{
- // This is the end : no more key
- return false;
+ // This is the end : no more value
+ throw new NoSuchElementException( "No more tuples present" );
}
-
- if ( parentPos.pos == ( parentPos.page.getNbElems() - 1 ) )
+
+ if ( parentPos.pos == parentPos.page.getNbElems() )
{
// End of the leaf. We have to go back into the stack up to the
- // parent, and down to the next leaf
+ // parent, and down to the leaf
parentPos = findNextParentPos();
- // we also need to check the result of the call to
- // findNextParentPos as it will return a null ParentPos
+ // we also need to check for the type of page cause
+ // findNextParentPos will never return a null ParentPos
if ( ( parentPos == null ) || ( parentPos.page == null ) )
{
- // This is the end : no more key
- return false;
+ // This is the end : no more value
+ throw new NoSuchElementException( "No more tuples present" );
}
- else
+ }
+
+ V value = null;
+
+ if ( parentPos.valueCursor.hasNext() )
+ {
+ // Deal with the BeforeFirst case
+ if ( parentPos.pos == BEFORE_FIRST )
{
- // We have more keys
- return true;
+ parentPos.pos++;
}
+
+ value = parentPos.valueCursor.next();
}
else
{
- return true;
+ 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] );
+ tuple.setValue( value );
+
+ return tuple;
}
-
+
/**
* {@inheritDoc}
*/
@@ -636,14 +717,24 @@ 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 next leaf
- parentPos = findNextParentPos();
+ ParentPos<K, V> newParentPos = findNextParentPos();
// we also need to check the result of the call to
// findNextParentPos as it will return a null ParentPos
- if ( ( parentPos == null ) || ( parentPos.page == null ) )
+ if ( ( newParentPos == null ) || ( newParentPos.page == null ) )
{
// This is the end : no more value
- throw new NoSuchElementException( "No more tuples present" );
+ Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
+ ValueHolder<V> valueHolder = leaf.values[parentPos.pos];
+ parentPos.pos = AFTER_LAST;
+ parentPos.valueCursor = valueHolder.getCursor();
+ parentPos.valueCursor.afterLast();
+
+ return null;
+ }
+ else
+ {
+ parentPos = newParentPos;
}
}
else
@@ -657,91 +748,104 @@ public class TupleCursorImpl<K, V> imple
tuple.setKey( leaf.keys[parentPos.pos] );
// The value
- if ( allowDuplicates )
- {
- MultipleMemoryHolder mvHolder = ( MultipleMemoryHolder<V, V> ) leaf.values[parentPos.pos];
-
- if( !mvHolder.isSingleValue() )
- {
- BTree<V, V> valueCursor = ( BTree ) mvHolder.getValue();
- parentPos.valueCursor = valueCursor;
- parentPos.dupPos = 0;
- }
-
- TupleCursor<V, V> cursor = parentPos.valueCursor.browse();
- cursor.beforeFirst();
-
- V value = cursor.next().getKey();
- tuple.setValue( value );
- }
- else
- {
- V value = leaf.values[parentPos.pos].getValue();
- tuple.setValue( value );
- }
+ ValueHolder<V> valueHolder = leaf.values[parentPos.pos];
+ parentPos.valueCursor = valueHolder.getCursor();
+ V value = parentPos.valueCursor.next();
+ tuple.setValue( value );
return tuple;
}
/**
- * {@inheritDoc}
+ * {@inheritDoc}
*/
- public boolean hasPrevKey() throws EndOfFileExceededException, IOException
+ public Tuple<K, V> prev() throws EndOfFileExceededException, IOException
{
// First check that we have elements in the BTree
if ( ( stack == null ) || ( stack.length == 0 ) )
{
- // This is the end : no more key
- return false;
+ throw new NoSuchElementException( "No more tuple present" );
}
ParentPos<K, V> parentPos = stack[depth];
- if ( parentPos.page == null )
+ if ( ( parentPos.page == null ) || ( parentPos.pos == BEFORE_FIRST ) )
{
- // This is the end : no more key
- return false;
+ // This is the end : no more value
+ throw new NoSuchElementException( "No more tuples present" );
}
-
- if ( parentPos.pos == 0 )
+
+ if ( ( parentPos.pos == 0 ) && ( !parentPos.valueCursor.hasPrev() ) )
{
- // Beginning of the leaf. We have to go back into the stack up to the
+ // End of the leaf. We have to go back into the stack up to the
// parent, and down to the leaf
parentPos = findPrevParentPos();
- if ( ( parentPos == null ) || ( parentPos.page == null ) )
+ // we also need to check for the type of page cause
+ // findPrevParentPos will never return a null ParentPos
+ if ( ( parentPos == null ) || ( parentPos.page == null ) || ( parentPos.page instanceof Node ) )
{
- // This is the end : no more key
- return false;
+ // This is the end : no more value
+ throw new NoSuchElementException( "No more tuples present" );
}
- else
+ }
+
+ V value = null;
+
+ if ( parentPos.valueCursor.hasPrev() )
+ {
+ // Deal with the AfterLast case
+ if ( parentPos.pos == AFTER_LAST )
{
- return true;
+ parentPos.pos = parentPos.page.getNbElems() - 1;
}
+
+ value = parentPos.valueCursor.prev();
}
else
{
- return true;
+ 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 );
+ tuple.setKey( leaf.keys[parentPos.pos] );
+ tuple.setValue( value );
+
+ return tuple;
}
/**
- * Moves the cursor to the previous non-duplicate key
- * If the BTree contains
- *
- * <ul>
- * <li><1,0></li>
- * <li><1,1></li>
- * <li><2,0></li>
- * <li><2,1></li>
- * </ul>
- *
- * and cursor is present at <2,1> then the cursor will move to <1,1>
- *
- * @throws EndOfFileExceededException
- * @throws IOException
+ * {@inheritDoc}
*/
public Tuple<K, V> prevKey() throws EndOfFileExceededException, IOException
{
@@ -784,7 +888,6 @@ public class TupleCursorImpl<K, V> imple
}
}
-
// Update the Tuple
Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
@@ -792,121 +895,26 @@ public class TupleCursorImpl<K, V> imple
tuple.setKey( leaf.keys[parentPos.pos] );
// The value
- if ( allowDuplicates )
- {
- MultipleMemoryHolder mvHolder = ( MultipleMemoryHolder<V, V> ) leaf.values[parentPos.pos];
-
- if( !mvHolder.isSingleValue() )
- {
- parentPos.valueCursor = ( BTree ) mvHolder.getValue();
- parentPos.dupPos = 0;
- }
-
- TupleCursor<V, V> cursor = parentPos.valueCursor.browse();
- cursor.beforeFirst();
-
- V value = cursor.next().getKey();
- tuple.setValue( value );
- }
- else
- {
- V value = leaf.values[parentPos.pos].getValue();
- tuple.setValue( value );
- }
+ ValueHolder<V> valueHolder = leaf.values[parentPos.pos];
+ parentPos.valueCursor = valueHolder.getCursor();
+ V value = parentPos.valueCursor.next();
+ tuple.setValue( value );
return tuple;
}
-
-
- /**
- * {@inheritDoc}
- */
- public void beforeFirst() throws IOException
+
+
+ public String toString()
{
- // First check that we have elements in the BTree
- if ( ( stack == null ) || ( stack.length == 0 ) )
- {
- return;
- }
-
- 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();
- }
+ StringBuilder sb = new StringBuilder();
- // and leaf
- ParentPos<K, V> parentPos = stack[depth];
- parentPos.pos = BEFORE_FIRST;
-
- if ( child != null )
- {
- parentPos.page = child;
- }
-
- if ( allowDuplicates )
- {
- setDupsContainer( parentPos, btree );
- }
- }
-
-
- /**
- * Places the cursor at the end of the last position
- *
- * @throws IOException
- */
- public void afterLast() throws IOException
- {
- // First check that we have elements in the BTree
- if ( ( stack == null ) || ( stack.length == 0 ) )
- {
- return;
- }
-
- Page<K, V> child = null;
-
- // Go fown the tree picking the rightmost element of each Node
- 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
- {
- // We have N+1 children if the page is a Node, so we don't decrement the nbElems field
- parentPos.pos = ((Node<K, V>)parentPos.page).nbElems;
- }
-
- child = ((Node<K, V>)parentPos.page).children[parentPos.pos].getValue();
- }
+ sb.append( "TupleCursor, depth = " ).append( depth ).append( "\n" );
- // and now, the leaf
- ParentPos<K, V> parentPos = stack[depth];
-
- if ( child != null )
+ for ( int i = 0; i <= depth; i++ )
{
- parentPos.page = child;
- }
-
- parentPos.pos = AFTER_LAST;
-
- if ( allowDuplicates )
- {
- setDupsContainer( parentPos, btree );
+ sb.append( " " ).append( stack[i] ).append( "\n" );
}
+
+ return sb.toString();
}
}