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/09/30 08:32:28 UTC
svn commit: r1527458 [9/14] - in /directory/mavibot/trunk/mavibot: img/
src/main/java/org/apache/directory/mavibot/btree/
src/main/java/org/apache/directory/mavibot/btree/managed/
src/main/java/org/apache/directory/mavibot/btree/memory/ src/main/java/o...
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BulkDataSorter.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BulkDataSorter.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BulkDataSorter.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BulkDataSorter.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,273 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.memory;
+
+
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.FileOutputStream;
+import java.io.IOException;
+import java.lang.reflect.Array;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.UUID;
+
+import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.util.TupleReaderWriter;
+
+
+/**
+ * A utility class for sorting a large number of keys before building a BTree using {@link BTreeBuilder}.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class BulkDataSorter<K, V>
+{
+ private File workDir;
+
+ private int splitAfter = 1000;
+
+ private Comparator<Tuple<K, V>> tupleComparator;
+
+ private TupleReaderWriter<K, V> readerWriter;
+
+ private boolean sorted;
+
+
+ public BulkDataSorter( TupleReaderWriter<K, V> readerWriter, Comparator<Tuple<K, V>> tupleComparator,
+ int splitAfter )
+ {
+ if ( splitAfter <= 0 )
+ {
+ throw new IllegalArgumentException( "Value of splitAfter parameter cannot be null" );
+ }
+
+ this.splitAfter = splitAfter;
+
+ this.workDir = new File( System.getProperty( "java.io.tmpdir" ), System.currentTimeMillis() + "-sort" );
+ workDir.mkdir();
+
+ this.readerWriter = readerWriter;
+ this.tupleComparator = tupleComparator;
+ }
+
+
+ public void sort( File dataFile ) throws IOException
+ {
+ int i = 0;
+
+ Tuple<K, V>[] arr = ( Tuple<K, V>[] ) Array.newInstance( Tuple.class, splitAfter );
+
+ Tuple<K, V> t = null;
+
+ DataInputStream in = new DataInputStream( new FileInputStream( dataFile ) );
+
+ while ( ( t = readerWriter.readTuple( in ) ) != null )
+ {
+ arr[i++] = t;
+
+ if ( ( i % splitAfter ) == 0 )
+ {
+ i = 0;
+ Arrays.sort( arr, tupleComparator );
+
+ storeSortedData( arr );
+ }
+ }
+
+ if ( i != 0 )
+ {
+ Tuple<K, V>[] tmp = ( Tuple<K, V>[] ) Array.newInstance( Tuple.class, i );
+ System.arraycopy( arr, 0, tmp, 0, i );
+ Arrays.sort( tmp, tupleComparator );
+
+ storeSortedData( tmp );
+ }
+
+ sorted = true;
+ }
+
+
+ private void storeSortedData( Tuple<K, V>[] arr ) throws IOException
+ {
+ File tempFile = File.createTempFile( UUID.randomUUID().toString(), ".batch", workDir );
+ DataOutputStream out = new DataOutputStream( new FileOutputStream( tempFile ) );
+
+ for ( Tuple<K, V> t : arr )
+ {
+ readerWriter.writeTuple( t, out );
+ }
+
+ out.flush();
+ out.close();
+ }
+
+
+ public File getWorkDir()
+ {
+ return workDir;
+ }
+
+
+ public Iterator<Tuple<K, V>> getMergeSortedTuples() throws IOException
+ {
+ if ( !sorted )
+ {
+ throw new IllegalStateException( "Data is not sorted" );
+ }
+
+ File[] batches = workDir.listFiles();
+
+ if ( batches.length == 0 )
+ {
+ return Collections.EMPTY_LIST.iterator();
+ }
+
+ final DataInputStream[] streams = new DataInputStream[batches.length];
+
+ for ( int i = 0; i < batches.length; i++ )
+ {
+ streams[i] = new DataInputStream( new FileInputStream( batches[i] ) );
+ }
+
+ Iterator<Tuple<K, V>> itr = new Iterator<Tuple<K, V>>()
+ {
+ private Tuple<K, V>[] heads = ( Tuple<K, V>[] ) Array.newInstance( Tuple.class, streams.length );
+
+ private Tuple<K, V> candidate = null;
+
+ private boolean closed;
+
+ private int candidatePos = -1;
+
+
+ @Override
+ public boolean hasNext()
+ {
+
+ if ( closed )
+ {
+ throw new IllegalStateException( "No elements to read" );
+ }
+
+ Tuple<K, V> available = null;
+
+ for ( int i = 0; i < streams.length; i++ )
+ {
+ if ( heads[i] == null )
+ {
+ heads[i] = readerWriter.readTuple( streams[i] );
+ }
+
+ if ( available == null )
+ {
+ available = heads[i];
+ candidatePos = i;
+ }
+ else
+ {
+ if ( ( available != null ) && ( heads[i] != null ) )
+ {
+ int comp = tupleComparator.compare( heads[i], available );
+ if ( comp <= 0 )
+ {
+ available = heads[i];
+ candidatePos = i;
+ }
+ }
+ }
+ }
+
+ heads[candidatePos] = null;
+
+ if ( available == null )
+ {
+ for ( int i = 0; i < streams.length; i++ )
+ {
+ if ( heads[i] != null )
+ {
+ available = heads[i];
+ heads[i] = readerWriter.readTuple( streams[i] );
+ break;
+ }
+ }
+ }
+
+ if ( available != null )
+ {
+ candidate = available;
+ return true;
+ }
+
+ // finally close the streams
+ for ( DataInputStream in : streams )
+ {
+ try
+ {
+ in.close();
+ }
+ catch ( Exception e )
+ {
+ e.printStackTrace();
+ }
+ }
+
+ closed = true;
+
+ return false;
+ }
+
+
+ @Override
+ public Tuple<K, V> next()
+ {
+ if ( candidate == null )
+ {
+ if ( !closed )
+ {
+ hasNext();
+ }
+ }
+
+ if ( candidate == null )
+ {
+ throw new NoSuchElementException( "No tuples found" );
+ }
+
+ return candidate;
+ }
+
+
+ @Override
+ public void remove()
+ {
+ throw new UnsupportedOperationException( "Not supported" );
+ }
+
+ };
+
+ return itr;
+ }
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/CursorImpl.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/CursorImpl.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/CursorImpl.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/CursorImpl.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,651 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.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.LinkedList;
+import java.util.NoSuchElementException;
+
+import org.apache.directory.mavibot.btree.Cursor;
+import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
+
+
+/**
+ * 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
+ * when the user is done with it.
+ * <p>
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class CursorImpl<K, V> implements Cursor<K, V>
+{
+ /** The transaction used for this cursor */
+ private Transaction<K, V> transaction;
+
+ /** 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;
+
+ /** The BTree we are walking */
+ private BTree<K, V> btree;
+
+ private boolean allowDuplicates;
+
+ /** a copy of the stack given at the time of initializing the cursor. This is used for moving the cursor to start position */
+ private LinkedList<ParentPos<K, V>> _initialStack;
+
+
+ /**
+ * Creates a new instance of Cursor, starting on a page at a given position.
+ *
+ * @param transaction The transaction this operation is protected by
+ * @param stack The stack of parent's from root to this page
+ */
+ CursorImpl( BTree<K, V> btree, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+ {
+ this.transaction = transaction;
+ this.stack = stack;
+ this.btree = btree;
+ this.allowDuplicates = btree.isAllowDuplicates();
+
+ _initialStack = new LinkedList<ParentPos<K, V>>();
+
+ cloneStack( stack, _initialStack );
+ }
+
+
+ /**
+ * Find the next key/value
+ *
+ * @return A Tuple containing the found key and value
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ public Tuple<K, V> next() throws EndOfFileExceededException, IOException
+ {
+ ParentPos<K, V> parentPos = stack.getFirst();
+
+ if ( parentPos.page == null )
+ {
+ // This is the end : no more value
+ throw new NoSuchElementException( "No more tuples present" );
+ }
+
+ 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 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" );
+ }
+ }
+
+ // can happen if next() is called after prev()
+ if ( parentPos.pos < 0 )
+ {
+ parentPos.pos = 0;
+ }
+
+ Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
+ tuple.setKey( leaf.keys[parentPos.pos] );
+
+ if ( allowDuplicates )
+ {
+ MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) leaf.values[parentPos.pos];
+
+ if ( mvHolder.isSingleValue() )
+ {
+ tuple.setValue( mvHolder.getValue( btree ) );
+ parentPos.pos++;
+ }
+ else
+ {
+ setDupsContainer( parentPos, btree );
+
+ // can happen if next() is called after prev()
+ if ( parentPos.dupPos < 0 )
+ {
+ parentPos.dupPos = 0;
+ }
+
+ tuple.setValue( parentPos.dupsContainer.rootPage.getKey( parentPos.dupPos ) );
+ parentPos.dupPos++;
+
+ if ( parentPos.dupsContainer.getNbElems() == parentPos.dupPos )
+ {
+ parentPos.pos++;
+ changeNextDupsContainer( parentPos, btree );
+ }
+ }
+ }
+ else
+ {
+ tuple.setValue( leaf.values[parentPos.pos].getValue( btree ) );
+ parentPos.pos++;
+ }
+
+ return tuple;
+ }
+
+
+ /**
+ * Find the leaf containing the following elements.
+ *
+ * @return the new ParentPos instance, or null if we have no following leaf
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ private ParentPos<K, V> findNextParentPos() throws EndOfFileExceededException, IOException
+ {
+ ParentPos<K, V> lastParentPos = null;
+
+ while ( true )
+ {
+ // We first go up the tree, until we reach a page whose current position
+ // is not the last one
+ ParentPos<K, V> parentPos = stack.peek();
+
+ if ( parentPos == null )
+ {
+ stack.push( lastParentPos );
+ return lastParentPos;
+ }
+
+ if ( parentPos.pos == parentPos.page.getNbElems() )
+ {
+ lastParentPos = stack.pop();
+ continue;
+ }
+ else
+ {
+ // Then we go down the tree until we find a leaf which position is not the last one.
+ int newPos = ++parentPos.pos;
+ ParentPos<K, V> newParentPos = parentPos;
+
+ while ( newParentPos.page instanceof Node )
+ {
+ Node<K, V> node = ( Node<K, V> ) newParentPos.page;
+
+ newParentPos = new ParentPos<K, V>( node.children[newPos].getValue( btree ), 0 );
+
+ stack.push( newParentPos );
+
+ newPos = 0;
+ }
+
+ if ( allowDuplicates )
+ {
+ changeNextDupsContainer( newParentPos, btree );
+ }
+
+ return newParentPos;
+ }
+ }
+ }
+
+
+ /**
+ * Find the leaf containing the previous elements.
+ *
+ * @return the new ParentPos instance, or null if we have no previous leaf
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ private ParentPos<K, V> findPreviousParentPos() throws EndOfFileExceededException, IOException
+ {
+ ParentPos<K, V> lastParentPos = null;
+
+ while ( true )
+ {
+ // We first go up the tree, until we reach a page which current position
+ // is not the first one
+ ParentPos<K, V> parentPos = stack.peek();
+
+ if ( parentPos == null )
+ {
+ stack.push( lastParentPos );
+ return lastParentPos;
+ }
+
+ if ( parentPos.pos == 0 )
+ {
+ lastParentPos = stack.pop();
+ continue;
+ }
+ else
+ {
+ // Then we go down the tree until we find a leaf which position is not the first one.
+ int newPos = --parentPos.pos;
+ ParentPos<K, V> newParentPos = parentPos;
+
+ while ( newParentPos.page instanceof Node )
+ {
+ Node<K, V> node = ( Node<K, V> ) newParentPos.page;
+
+ newParentPos = new ParentPos<K, V>( node.children[newPos].getValue( btree ), node.children[newPos]
+ .getValue( btree ).getNbElems() );
+
+ stack.push( newParentPos );
+
+ newPos = node.getNbElems();
+ }
+
+ if ( allowDuplicates )
+ {
+ changePrevDupsContainer( newParentPos, btree );
+ }
+
+ return newParentPos;
+ }
+ }
+ }
+
+
+ /**
+ * 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
+ {
+ ParentPos<K, V> parentPos = stack.peek();
+
+ 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 = findPreviousParentPos();
+
+ // 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( btree ) );
+ }
+ else
+ {
+ prevHasSubtree = true;
+ }
+ }
+ else
+ {
+ prevHasSubtree = true;
+ }
+
+ if ( prevHasSubtree )
+ {
+ setDupsContainer( parentPos, btree );
+
+ if ( parentPos.dupPos == parentPos.dupsContainer.getNbElems() )
+ {
+ parentPos.dupPos--;
+ }
+ else if ( parentPos.dupPos == 0 )
+ {
+ changePrevDupsContainer( parentPos, btree );
+ parentPos.pos--;
+
+ if ( parentPos.dupsContainer != null )
+ {
+ parentPos.dupPos--;
+ }
+ }
+ else
+ {
+ parentPos.dupPos--;
+ }
+
+ tuple.setKey( leaf.keys[parentPos.pos] );
+
+ if ( parentPos.dupsContainer != null )
+ {
+ tuple.setValue( parentPos.dupsContainer.rootPage.getKey( parentPos.dupPos ) );
+ }
+ else
+ {
+ tuple.setValue( leaf.values[parentPos.pos].getValue( btree ) );
+ }
+ }
+ }
+ else
+ {
+ parentPos.pos--;
+ tuple.setKey( leaf.keys[parentPos.pos] );
+ tuple.setValue( leaf.values[parentPos.pos].getValue( btree ) );
+ }
+
+ return tuple;
+ }
+
+
+ /**
+ * Tells if the cursor can return a next element
+ * @return true if there are some more elements
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ public boolean hasNext() throws EndOfFileExceededException, IOException
+ {
+ ParentPos<K, V> parentPos = stack.peek();
+
+ if ( parentPos.page == null )
+ {
+ return false;
+ }
+
+ for ( ParentPos<K, V> p : stack )
+ {
+ if ( allowDuplicates && ( p.page instanceof Leaf ) )
+ {
+ if ( ( p.dupsContainer == null ) && ( p.pos != p.page.getNbElems() ) )
+ {
+ return true;
+ }
+ else if ( ( p.dupsContainer != null ) && ( p.dupPos != p.dupsContainer.getNbElems() )
+ && ( p.pos != p.page.getNbElems() ) )
+ {
+ return true;
+ }
+ }
+ else if ( p.pos != p.page.getNbElems() )
+ {
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+
+ /**
+ * Tells if the cursor can return a previous element
+ * @return true if there are some more elements
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ public boolean hasPrev() throws EndOfFileExceededException, IOException
+ {
+ ParentPos<K, V> parentPos = stack.peek();
+
+ if ( parentPos.page == null )
+ {
+ return false;
+ }
+
+ for ( ParentPos<K, V> p : stack )
+ {
+ if ( allowDuplicates && ( p.page instanceof Leaf ) )
+ {
+ if ( ( p.dupsContainer == null ) && ( p.pos != 0 ) )
+ {
+ return true;
+ }
+ else if ( ( p.dupsContainer != null ) &&
+ ( ( p.dupPos != 0 ) || ( p.pos != 0 ) ) )
+ {
+ return true;
+ }
+ }
+ else if ( p.pos != 0 )
+ {
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+
+ /**
+ * Closes the cursor, thus releases the associated transaction
+ */
+ public void close()
+ {
+ transaction.close();
+ }
+
+
+ /**
+ * @return The revision this cursor is based on
+ */
+ public long getRevision()
+ {
+ return transaction.getRevision();
+ }
+
+
+ /**
+ * @return The creation date for this cursor
+ */
+ public long getCreationDate()
+ {
+ return transaction.getCreationDate();
+ }
+
+
+ /**
+ * Moves the cursor to the next 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 <1,0> then the cursor will move to <2,0>
+ *
+ * @throws EndOfFileExceededException
+ * @throws IOException
+ */
+ public void moveToNextNonDuplicateKey() throws EndOfFileExceededException, IOException
+ {
+ ParentPos<K, V> parentPos = stack.getFirst();
+
+ if ( parentPos.page == null )
+ {
+ return;
+ }
+
+ if ( parentPos.pos == ( parentPos.page.getNbElems() - 1 ) )
+ {
+ // End of the leaf. We have to go back into the stack up to the
+ // parent, and down to the leaf
+ // increment the position cause findNextParentPos checks "parentPos.pos == parentPos.page.getNbElems()"
+ parentPos.pos++;
+ ParentPos<K, V> nextPos = findNextParentPos();
+
+ // if the returned value is a Node OR if it is same as the parentPos
+ // that means cursor is already at the last position
+ // call afterLast() to restore the stack with the path to the right most element
+ if ( ( nextPos.page instanceof Node ) || ( nextPos == parentPos ) )
+ {
+ afterLast();
+ }
+ else
+ {
+ parentPos = nextPos;
+ }
+ }
+ else
+ {
+ parentPos.pos++;
+ changeNextDupsContainer( parentPos, btree );
+ }
+ }
+
+
+ /**
+ * 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
+ */
+ public void moveToPrevNonDuplicateKey() throws EndOfFileExceededException, IOException
+ {
+ ParentPos<K, V> parentPos = stack.peek();
+
+ if ( parentPos.page == null )
+ {
+ // This is the end : no more value
+ return;
+ }
+
+ if ( parentPos.pos == 0 )
+ {
+ // End of the leaf. We have to go back into the stack up to the
+ // parent, and down to the leaf
+ parentPos = findPreviousParentPos();
+
+ // if the returned value is a Node that means cursor is already at the first position
+ // call beforeFirst() to restore the stack to the initial state
+ if ( parentPos.page instanceof Node )
+ {
+ beforeFirst();
+ }
+ }
+ else
+ {
+ changePrevDupsContainer( parentPos, btree );
+ parentPos.pos--;
+ }
+ }
+
+
+ /**
+ * moves the cursor to the same position that was given at the time of instantiating the cursor.
+ *
+ * For example, if the cursor was created using browse() method, then beforeFirst() will
+ * place the cursor before the 0th position.
+ *
+ * If the cursor was created using browseFrom(K), then calling beforeFirst() will reset the position
+ * to the just before the position where K is present.
+ */
+ public void beforeFirst() throws IOException
+ {
+ cloneStack( _initialStack, stack );
+ }
+
+
+ /**
+ * Places the cursor at the end of the last position
+ *
+ * @throws IOException
+ */
+ public void afterLast() throws IOException
+ {
+ stack.clear();
+ stack = BTreeFactory.getPathToRightMostLeaf( btree );
+ }
+
+
+ /**
+ * clones the original stack of ParentPos objects
+ *
+ * @param original the original stack
+ * @param clone the stack where the cloned ParentPos objects to be copied
+ */
+ private void cloneStack( LinkedList<ParentPos<K, V>> original, LinkedList<ParentPos<K, V>> clone )
+ {
+ clone.clear();
+
+ // preserve the first position
+ for ( ParentPos<K, V> o : original )
+ {
+ ParentPos<K, V> tmp = new ParentPos<K, V>( o.page, o.pos );
+ tmp.dupPos = o.dupPos;
+ tmp.dupsContainer = o.dupsContainer;
+ clone.add( tmp );
+ }
+ }
+
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/DeleteResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/DeleteResult.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/DeleteResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/DeleteResult.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,47 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.memory;
+
+
+import org.apache.directory.mavibot.btree.Result;
+import org.apache.directory.mavibot.btree.Tuple;
+
+
+/**
+ * The result of an delete operation.
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+interface DeleteResult<K, V> extends Result<Page<K, V>>
+{
+ /**
+ * @return the modifiedPage
+ */
+ Page<K, V> getModifiedPage();
+
+
+ /**
+ * @return the removed element
+ */
+ Tuple<K, V> getRemovedElement();
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/DuplicateKeyVal.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/DuplicateKeyVal.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/DuplicateKeyVal.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/DuplicateKeyVal.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,72 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.memory;
+
+
+/**
+ * A class to hold a single value or multiple values (in a sub-tree) of a key.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class DuplicateKeyVal<V>
+{
+ private V singleValue;
+
+ private BTree<V, V> subTree;
+
+
+ /** No Qualifier */
+ DuplicateKeyVal( V singleValue )
+ {
+ this.singleValue = singleValue;
+ }
+
+
+ /** No Qualifier */
+ DuplicateKeyVal( BTree<V, V> subTree )
+ {
+ this.subTree = subTree;
+ }
+
+
+ public boolean isSingleValue()
+ {
+ return ( singleValue != null );
+ }
+
+
+ /**
+ * @return the singleValue
+ */
+ public V getSingleValue()
+ {
+ return singleValue;
+ }
+
+
+ /**
+ * @return the subTree
+ */
+ public BTree<V, V> getSubTree()
+ {
+ return subTree;
+ }
+
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/ElementHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/ElementHolder.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/ElementHolder.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/ElementHolder.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,49 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.memory;
+
+
+import java.io.IOException;
+
+import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
+
+
+/**
+ * A Value holder. As we may not store all the values in memory (except for an in-memory
+ * BTree), we will use a SoftReference to keep a reference to a Value, and if it's null,
+ * then we will load the Value from the underlying physical support, using the offset.
+ *
+ * @param <E> The type for the stored element (either a V or a Page<K, V>)
+ * @param <K> The type of the BTree key
+ * @param <V> The type of the BTree value
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public interface ElementHolder<E, K, V>
+{
+ /**
+ * Get back the element
+ *
+ * @param btree The Btree storing the element
+ *
+ * @return The stored element
+ */
+ E getValue( BTree<K, V> btree ) throws EndOfFileExceededException, IOException;
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InsertResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InsertResult.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InsertResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InsertResult.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,38 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.memory;
+
+
+import org.apache.directory.mavibot.btree.Result;
+
+
+/**
+ * The result of an insert operation. This is just a container that stores either
+ * the new pivot that has been extracted after a page split, or a modified page if
+ * the child page hasn't been split.
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+interface InsertResult<K, V> extends Result<Page<K, V>>
+{
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InternalUtil.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InternalUtil.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InternalUtil.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InternalUtil.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,137 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+package org.apache.directory.mavibot.btree.memory;
+
+
+import java.io.IOException;
+
+
+/**
+ * A class containing utility methods to be used internally.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+@SuppressWarnings("all")
+/* No qualifier */class InternalUtil
+{
+
+ /**
+ * Sets the multi-value container(a.k.a dupsContainer) of the key at the given position.
+ *
+ * This method will not update the existing value of 'dupsPos'. To change this value
+ * use {@link #changeNextDupsContainer(ParentPos, BTree)} or {@link #changePrevDupsContainer(ParentPos, BTree)}
+ *
+ * @param parentPos the parent position object
+ * @param btree the BTree
+ */
+ public static void setDupsContainer( ParentPos parentPos, BTree btree )
+ {
+ if ( !btree.isAllowDuplicates() )
+ {
+ return;
+ }
+
+ if ( parentPos.dupsContainer == null )
+ {
+ Leaf leaf = ( Leaf ) ( parentPos.page );
+ MultipleMemoryHolder mvHolder = ( MultipleMemoryHolder ) leaf.values[parentPos.pos];
+ if( !mvHolder.isSingleValue() )
+ {
+ BTree dupsContainer = ( BTree ) mvHolder.getValue( btree );
+ parentPos.dupsContainer = dupsContainer;
+ }
+ }
+ }
+
+
+ /**
+ * Sets the multi-value container(a.k.a dupsContainer) of the key at the given position
+ * and resets the 'dupsPos' to zero. This is mostly used by Cursor while navigating using
+ * next()
+ *
+ * @param parentPos the parent position object
+ * @param btree the BTree
+ */
+ public static void changeNextDupsContainer( ParentPos parentPos, BTree btree ) throws IOException
+ {
+ if ( !btree.isAllowDuplicates() )
+ {
+ return;
+ }
+
+ if ( parentPos.pos < parentPos.page.getNbElems() )
+ {
+ Leaf leaf = ( Leaf ) ( parentPos.page );
+ MultipleMemoryHolder mvHolder = ( MultipleMemoryHolder ) leaf.values[parentPos.pos];
+ if( !mvHolder.isSingleValue() )
+ {
+ BTree dupsContainer = ( BTree ) mvHolder.getValue( btree );
+ parentPos.dupsContainer = dupsContainer;
+ parentPos.dupPos = 0;
+ }
+ }
+ }
+
+
+ /**
+ * Sets the multi-value container(a.k.a dupsContainer) of the key at the index below the given position( i.e pos - 1)
+ * and resets the 'dupsPos' to the number of elements present in the multi-value container.
+ * This is used by Cursor while navigating using prev()
+ *
+ * @param parentPos the parent position object
+ * @param btree the BTree
+ */
+ public static void changePrevDupsContainer( ParentPos parentPos, BTree btree ) throws IOException
+ {
+ if ( !btree.isAllowDuplicates() )
+ {
+ return;
+ }
+
+ int index = parentPos.pos - 1;
+ if ( index >= 0 )
+ {
+ Leaf leaf = ( Leaf ) ( parentPos.page );
+ MultipleMemoryHolder mvHolder = ( MultipleMemoryHolder ) leaf.values[index];
+ if( !mvHolder.isSingleValue() )
+ {
+ BTree dupsContainer = ( BTree ) mvHolder.getValue( btree );
+ parentPos.dupsContainer = dupsContainer;
+ parentPos.dupPos = ( int ) parentPos.dupsContainer.getNbElems();
+ }
+ else
+ {
+ parentPos.dupsContainer = null;
+ parentPos.dupPos = -1;
+ }
+ }
+ }
+
+
+ /**
+ * Same as @see #changePrevDupsContainer(ParentPos, BTree) but with a different name
+ * to make it sound semantically right when used inside {@link BTreeFactory#getPathToRightMostLeaf(BTree)}
+ */
+ public static void setLastDupsContainer( ParentPos parentPos, BTree btree ) throws IOException
+ {
+ changePrevDupsContainer( parentPos, btree );
+ }
+}
Added: 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=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Leaf.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Leaf.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,1107 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.memory;
+
+
+import static org.apache.directory.mavibot.btree.memory.InternalUtil.setDupsContainer;
+
+import java.io.IOException;
+import java.lang.reflect.Array;
+import java.util.LinkedList;
+
+import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
+import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
+
+
+/**
+ * A MVCC Leaf. It stores the keys and values. It does not have any children.
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+/* No qualifier */class Leaf<K, V> extends AbstractPage<K, V>
+{
+ /** Values associated with keys */
+ protected ElementHolder<V, K, V>[] values;
+
+
+ /**
+ * Constructor used to create a new Leaf when we read it from a file.
+ *
+ * @param btree The BTree this page belongs to.
+ */
+ /* No qualifier */Leaf( BTree<K, V> btree )
+ {
+ super( btree );
+ }
+
+
+ /**
+ * Internal constructor used to create Page instance used when a page is being copied or overflow
+ *
+ * @param btree The BTree this page belongs to.
+ * @param revision The page revision
+ * @param nbElems The number of elements this page will contain
+ */
+ @SuppressWarnings("unchecked")
+ // Cannot create an array of generic objects
+ /* No qualifier */Leaf( BTree<K, V> btree, long revision, int nbElems )
+ {
+ 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 );
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public InsertResult<K, V> insert( long revision, K key, V value ) throws IOException
+ {
+ // Find the key into this leaf
+ int pos = findPos( key );
+
+ if ( pos < 0 )
+ {
+ // We already have the key in the page : replace the value
+ // into a copy of this page, unless the page has already be copied
+ int index = -( pos + 1 );
+
+ // Replace the existing value in a copy of the current page
+ InsertResult<K, V> result = replaceElement( revision, key, value, index );
+
+ return result;
+ }
+
+ // The key is not present in the leaf. We have to add it in the page
+ if ( nbElems < btree.getPageSize() )
+ {
+ // The current page is not full, it can contain the added element.
+ // We insert it into a copied page and return the result
+ Page<K, V> modifiedPage = addElement( revision, key, value, pos );
+
+ InsertResult<K, V> result = new ModifyResult<K, V>( modifiedPage, null );
+ result.addCopiedPage( this );
+
+ return result;
+ }
+ else
+ {
+ // The Page is already full : we split it and return the overflow element,
+ // after having created two pages.
+ InsertResult<K, V> result = addAndSplit( revision, key, value, pos );
+ result.addCopiedPage( this );
+
+ return result;
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ @SuppressWarnings("unchecked")
+ public DeleteResult<K, V> delete( long revision, K key, V value, Page<K, V> parent, int parentPos )
+ throws IOException
+ {
+ // Check that the leaf is not empty
+ if ( nbElems == 0 )
+ {
+ // Empty leaf
+ return NotPresentResult.NOT_PRESENT;
+ }
+
+ // Find the key in the page
+ int pos = findPos( key );
+
+ if ( pos >= 0 )
+ {
+ // Not found : return the not present result.
+ return NotPresentResult.NOT_PRESENT;
+ }
+
+ // Get the removed element
+ Tuple<K, V> removedElement = null;
+
+ // flag to detect if a key was completely removed
+ boolean keyRemoved = false;
+
+ 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( btree );
+
+ 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 ( mvHolder.isSingleValue() )
+ {
+ 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;
+ }
+ }
+ 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;
+ }
+ }
+ }
+ }
+ else
+ {
+ V existing = values[index].getValue( btree );
+
+ 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
+ {
+ return NotPresentResult.NOT_PRESENT;
+ }
+ }
+
+ Leaf<K, V> newLeaf = null;
+
+ if ( keyRemoved )
+ {
+ newLeaf = new Leaf<K, V>( btree, revision, nbElems - 1 );
+ }
+ else
+ {
+ newLeaf = new Leaf<K, V>( btree, revision, nbElems );
+ }
+
+ // Create the result
+ DeleteResult<K, V> defaultResult = new RemoveResult<K, V>( newLeaf, removedElement );
+
+ // If the parent is null, then this page is the root page.
+ if ( parent == null )
+ {
+ // Just remove the entry if it's present
+ copyAfterRemovingElement( keyRemoved, newLeaf, index );
+
+ // The current page is added in the copied page list
+ defaultResult.addCopiedPage( this );
+
+ return defaultResult;
+ }
+ else if ( keyRemoved )
+ {
+ // The current page is not the root. Check if the leaf has more than N/2
+ // elements
+ int halfSize = btree.getPageSize() / 2;
+
+ if ( nbElems == halfSize )
+ {
+ // We have to find a sibling now, and either borrow an entry from it
+ // 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.
+ int siblingPos = selectSibling( ( Node<K, V> ) parent, parentPos );
+ Leaf<K, V> sibling = ( Leaf<K, V> ) ( ( ( Node<K, V> ) parent ).children[siblingPos].getValue( btree ) );
+
+ if ( sibling.getNbElems() == halfSize )
+ {
+ // We will merge the current page with its sibling
+ DeleteResult<K, V> result = mergeWithSibling( removedElement, revision, sibling,
+ ( siblingPos < parentPos ), index );
+
+ return result;
+ }
+ else
+ {
+ // We can borrow the element from the left sibling
+ if ( siblingPos < parentPos )
+ {
+ DeleteResult<K, V> result = borrowFromLeft( removedElement, revision, sibling, index );
+
+ return result;
+ }
+ else
+ {
+ // Borrow from the right sibling
+ DeleteResult<K, V> result = borrowFromRight( removedElement, revision, sibling, index );
+
+ return result;
+ }
+ }
+ }
+ else
+ {
+ // The page has more than N/2 elements.
+ // We simply remove the element from the page, and if it was the leftmost,
+ // we return the new pivot (it will replace any instance of the removed
+ // key in its parents)
+ copyAfterRemovingElement( keyRemoved, newLeaf, index );
+
+ // The current page is added in the copied page list
+ defaultResult.addCopiedPage( this );
+
+ return defaultResult;
+ }
+ }
+ else
+ {
+ // Last, not least : we can copy the full page
+ // Copy the keys and the values
+ System.arraycopy( keys, 0, newLeaf.keys, 0, nbElems );
+ System.arraycopy( values, 0, newLeaf.values, 0, nbElems );
+
+ // The current page is added in the copied page list
+ defaultResult.addCopiedPage( this );
+
+ return defaultResult;
+ }
+ }
+
+
+ /**
+ * Merges the sibling with the current leaf, after having removed the element in the page.
+ *
+ * @param revision The new revision
+ * @param sibling The sibling we will merge with
+ * @param isLeft Tells if the sibling is on the left or on the right
+ * @param pos The position of the removed element
+ * @return The new created leaf containing the sibling and the old page.
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private DeleteResult<K, V> mergeWithSibling( Tuple<K, V> removedElement, long revision, Leaf<K, V> sibling,
+ boolean isLeft, int pos )
+ throws EndOfFileExceededException, IOException
+ {
+ // 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.getPageSize() - 1 );
+
+ if ( isLeft )
+ {
+ // The sibling is on the left
+ // Copy all the elements from the sibling first
+ System.arraycopy( sibling.keys, 0, newLeaf.keys, 0, sibling.nbElems );
+ System.arraycopy( sibling.values, 0, newLeaf.values, 0, sibling.nbElems );
+
+ // Copy all the elements from the page up to the deletion position
+ System.arraycopy( keys, 0, newLeaf.keys, sibling.nbElems, pos );
+ System.arraycopy( values, 0, newLeaf.values, sibling.nbElems, pos );
+
+ // And copy the remaining elements after the deletion point
+ System.arraycopy( keys, pos + 1, newLeaf.keys, sibling.nbElems + pos, nbElems - pos - 1 );
+ System.arraycopy( values, pos + 1, newLeaf.values, sibling.nbElems + pos, nbElems - pos - 1 );
+ }
+ else
+ {
+ // The sibling is on the right
+ // Copy all the elements from the page up to the deletion position
+ System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
+ System.arraycopy( values, 0, newLeaf.values, 0, pos );
+
+ // Then copy the remaining elements after the deletion point
+ System.arraycopy( keys, pos + 1, newLeaf.keys, pos, nbElems - pos - 1 );
+ System.arraycopy( values, pos + 1, newLeaf.values, pos, nbElems - pos - 1 );
+
+ // And copy all the elements from the sibling
+ System.arraycopy( sibling.keys, 0, newLeaf.keys, nbElems - 1, sibling.nbElems );
+ System.arraycopy( sibling.values, 0, newLeaf.values, nbElems - 1, sibling.nbElems );
+ }
+
+ // And create the result
+ DeleteResult<K, V> result = new MergedWithSiblingResult<K, V>( newLeaf,
+ removedElement );
+
+ result.addCopiedPage( this );
+ result.addCopiedPage( sibling );
+
+ return result;
+ }
+
+
+ /**
+ * Borrows an element from the left sibling, creating a new sibling with one
+ * less element and creating a new page where the element to remove has been
+ * deleted and the borrowed element added on the left.
+ *
+ * @param revision The new revision for all the pages
+ * @param sibling The left sibling
+ * @param pos The position of the element to remove
+ * @return The resulting pages
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private DeleteResult<K, V> borrowFromLeft( Tuple<K, V> removedElement, long revision, Leaf<K, V> sibling, int pos )
+ throws IOException
+ {
+ // 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];
+
+ // Create the new sibling, with one less element at the end
+ Leaf<K, V> newSibling = ( Leaf<K, V> ) sibling.copy( revision, sibling.getNbElems() - 1 );
+
+ // Create the new page and add the new element at the beginning
+ // First copy the current page, with the same size
+ Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems );
+
+ // Insert the borrowed element
+ newLeaf.keys[0] = siblingKey;
+ newLeaf.values[0] = siblingValue;
+
+ // Copy the keys and the values up to the insertion position,
+ System.arraycopy( keys, 0, newLeaf.keys, 1, pos );
+ System.arraycopy( values, 0, newLeaf.values, 1, pos );
+
+ // And copy the remaining elements
+ 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 );
+
+ DeleteResult<K, V> result = new BorrowedFromLeftResult<K, V>( newLeaf, newSibling, removedElement );
+
+ // Add the copied pages to the list
+ result.addCopiedPage( this );
+ result.addCopiedPage( sibling );
+
+ return result;
+ }
+
+
+ /**
+ * Borrows an element from the right sibling, creating a new sibling with one
+ * less element and creating a new page where the element to remove has been
+ * deleted and the borrowed element added on the right.
+ *
+ * @param revision The new revision for all the pages
+ * @param sibling The right sibling
+ * @param pos The position of the element to remove
+ * @return The resulting pages
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private DeleteResult<K, V> borrowFromRight( Tuple<K, V> removedElement, long revision, Leaf<K, V> sibling, int pos )
+ throws IOException
+ {
+ // The sibling is on the left, borrow the rightmost element
+ K siblingKey = sibling.keys[0];
+ ElementHolder<V, K, V> siblingHolder = sibling.values[0];
+
+ // Create the new sibling
+ Leaf<K, V> newSibling = new Leaf<K, V>( btree, revision, sibling.getNbElems() - 1 );
+
+ // Copy the keys and the values from 1 to N in the new sibling
+ System.arraycopy( sibling.keys, 1, newSibling.keys, 0, sibling.nbElems - 1 );
+ System.arraycopy( sibling.values, 1, newSibling.values, 0, sibling.nbElems - 1 );
+
+ // Create the new page and add the new element at the end
+ // First copy the current page, with the same size
+ Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems );
+
+ // Insert the borrowed element at the end
+ newLeaf.keys[nbElems - 1] = siblingKey;
+ newLeaf.values[nbElems - 1] = siblingHolder;
+
+ // Copy the keys and the values up to the deletion position,
+ System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
+ System.arraycopy( values, 0, newLeaf.values, 0, pos );
+
+ // And copy the remaining elements
+ System.arraycopy( keys, pos + 1, newLeaf.keys, pos, keys.length - pos - 1 );
+ System.arraycopy( values, pos + 1, newLeaf.values, pos, values.length - pos - 1 );
+
+ DeleteResult<K, V> result = new BorrowedFromRightResult<K, V>( newLeaf, newSibling, removedElement );
+
+ // Add the copied pages to the list
+ result.addCopiedPage( this );
+ result.addCopiedPage( sibling );
+
+ return result;
+ }
+
+
+ /**
+ * Copies the elements of the current page to a new page
+ *
+ * @param keyRemoved a flag stating if the key was removed
+ * @param newLeaf The new page into which the remaining keys and values will be copied
+ * @param pos The position into the page of the element to remove
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private void copyAfterRemovingElement( boolean keyRemoved, Leaf<K, V> newLeaf, int pos ) throws IOException
+ {
+ if ( keyRemoved )
+ {
+ // Deal with the special case of a page with only one element by skipping
+ // the copy, as we won't have any remaining element in the page
+ if ( nbElems == 1 )
+ {
+ return;
+ }
+
+ // Copy the keys and the values up to the insertion position
+ System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
+ System.arraycopy( values, 0, newLeaf.values, 0, pos );
+
+ // And copy the elements after the position
+ System.arraycopy( keys, pos + 1, newLeaf.keys, pos, keys.length - pos - 1 );
+ System.arraycopy( values, pos + 1, newLeaf.values, pos, values.length - pos - 1 );
+ }
+ else
+ // one of the many values of the same key was removed, no change in the number of keys
+ {
+ System.arraycopy( keys, 0, newLeaf.keys, 0, nbElems );
+ System.arraycopy( values, 0, newLeaf.values, 0, nbElems );
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public V get( K key ) throws KeyNotFoundException, IOException
+ {
+ int pos = findPos( key );
+
+ if ( pos < 0 )
+ {
+ if ( btree.isAllowDuplicates() )
+ {
+ MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) values[-( pos + 1 )];
+ if ( mvHolder.isSingleValue() )
+ {
+ return mvHolder.getValue( btree );
+ }
+ else
+ {
+ // always return the first value for get(key) when duplicates are allowed
+ BTree<V, V> dupTree = ( BTree<V, V> ) mvHolder.getValue( btree );
+ return dupTree.rootPage.getLeftMostKey();
+ }
+ }
+
+ V v = values[-( pos + 1 )].getValue( btree );
+
+ return v;
+ }
+ else
+ {
+ throw new KeyNotFoundException( "Cannot find an entry for key " + key );
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public DuplicateKeyVal<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
+ {
+ if ( !btree.isAllowDuplicates() )
+ {
+ throw new IllegalArgumentException( "Duplicates are not allowed in this tree" );
+ }
+
+ int pos = findPos( key );
+
+ if ( pos < 0 )
+ {
+ MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) values[-( pos + 1 )];
+
+ if ( mvHolder.isSingleValue() )
+ {
+ return new DuplicateKeyVal<V>( mvHolder.getValue( btree ) );
+ }
+
+ return new DuplicateKeyVal<V>( ( BTree<V, V> ) mvHolder.getValue( btree ) );
+ }
+ else
+ {
+ throw new KeyNotFoundException( "Cannot find an entry for key " + key );
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public boolean hasKey( K key )
+ {
+ int pos = findPos( key );
+
+ if ( pos < 0 )
+ {
+ return true;
+ }
+
+ return false;
+ }
+
+
+ @Override
+ public boolean contains( K key, V value ) throws IOException
+ {
+ int pos = findPos( key );
+
+ 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( btree ) ) == 0 );
+ }
+ else
+ {
+ // always return the first value for get(key) when duplicates are allowed
+ BTree<V, V> dupTree = ( ( BTree<V, V> ) mvHolder.getValue( btree ) );
+ return dupTree.hasKey( value );
+ }
+ }
+ else
+ {
+ V v = values[-( pos + 1 )].getValue( btree );
+ return ( btree.getValueSerializer().compare( value, v ) == 0 );
+ }
+ }
+ else
+ {
+ return false;
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public ElementHolder<V, K, V> getValue( int pos )
+ {
+ if ( pos < nbElems )
+ {
+ return values[pos];
+ }
+ else
+ {
+ return null;
+ }
+ }
+
+
+ /**
+ * Sets the value at a give position
+ * @param pos The position in the values array
+ * @param value the value to inject
+ */
+ public void setValue( int pos, ElementHolder<V, K, V> value )
+ {
+ values[pos] = value;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public CursorImpl<K, V> browse( K key, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+ {
+ int pos = findPos( key );
+ CursorImpl<K, V> cursor = null;
+
+ if ( pos < 0 )
+ {
+ int index = -( pos + 1 );
+
+ // The first element has been found. Create the cursor
+ ParentPos<K, V> parentPos = new ParentPos<K, V>( this, index );
+ setDupsContainer( parentPos, btree );
+ stack.push( parentPos );
+
+ cursor = new CursorImpl<K, V>( btree, transaction, stack );
+ }
+ else
+ {
+ // The key has not been found. Select the value just above, if we have one
+ if ( pos < nbElems )
+ {
+ ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
+ setDupsContainer( parentPos, btree );
+ stack.push( parentPos );
+
+ cursor = new CursorImpl<K, V>( btree, transaction, stack );
+ }
+ else
+ {
+ // Not found : return a null cursor
+ stack.push( new ParentPos<K, V>( null, -1 ) );
+
+ return new CursorImpl<K, V>( btree, transaction, stack );
+ }
+ }
+
+ return cursor;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public CursorImpl<K, V> browse( Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+ {
+ int pos = 0;
+ CursorImpl<K, V> cursor = null;
+
+ if ( nbElems == 0 )
+ {
+ // The tree is empty, it's the root, we have nothing to return
+ stack.push( new ParentPos<K, V>( null, -1 ) );
+
+ return new CursorImpl<K, V>( btree, transaction, stack );
+ }
+ else
+ {
+ // Start at the beginning of the page
+ ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
+
+ setDupsContainer( parentPos, btree );
+
+ stack.push( parentPos );
+
+ cursor = new CursorImpl<K, V>( btree, transaction, stack );
+ }
+
+ return cursor;
+ }
+
+
+ /**
+ * Copy the current page and all of the keys, values and children, if it's not a leaf.
+ *
+ * @param revision The new revision
+ * @param nbElems The number of elements to copy
+ * @return The copied page
+ */
+ private Page<K, V> copy( long revision, int nbElems )
+ {
+ Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems );
+
+ // Copy the keys and the values
+ System.arraycopy( keys, 0, newLeaf.keys, 0, nbElems );
+ System.arraycopy( values, 0, newLeaf.values, 0, nbElems );
+
+ return newLeaf;
+ }
+
+
+ /**
+ * Copy the current page if needed, and replace the value at the position we have found the key.
+ *
+ * @param revision The new page revision
+ * @param key The new key
+ * @param value the new value
+ * @param pos The position of the key in the page
+ * @return The copied page
+ * @throws IOException If we have an error while trying to access the page
+ */
+ private InsertResult<K, V> replaceElement( long revision, K key, V value, int pos )
+ throws IOException
+ {
+ Leaf<K, V> newLeaf = this;
+
+ if ( this.revision != revision )
+ {
+ // The page hasn't been modified yet, we need to copy it first
+ newLeaf = ( Leaf<K, V> ) copy( revision, nbElems );
+ }
+
+ V oldValue = null;
+
+ if ( btree.isAllowDuplicates() )
+ {
+ MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) newLeaf.values[pos];
+
+ if ( mvHolder.isSingleValue() )
+ {
+ V singleVal = mvHolder.getValue( btree );
+
+ // 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( btree );
+
+ // return value will always be null here
+ if ( !dupValues.hasKey( value ) )
+ {
+ dupValues.insert( value, null, 0 );
+ }
+ else
+ {
+ oldValue = value;
+ }
+ }
+ }
+ else
+ {
+ // Now we can inject the value
+ oldValue = newLeaf.values[pos].getValue( btree );
+ newLeaf.values[pos] = btree.createValueHolder( value );
+ }
+
+ // Create the result
+ InsertResult<K, V> result = new ModifyResult<K, V>( newLeaf, oldValue );
+ result.addCopiedPage( this );
+
+ return result;
+ }
+
+
+ /**
+ * Adds a new <K, V> into a copy of the current page at a given position. We return the
+ * modified page. The new page will have one more element than the current page.
+ *
+ * @param revision The revision of the modified page
+ * @param key The key to insert
+ * @param value The value to insert
+ * @param pos The position into the page
+ * @return The modified page with the <K,V> element added
+ */
+ private Page<K, V> addElement( long revision, K key, V value, int pos )
+ {
+ // First copy the current page, but add one element in the copied page
+ 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 );
+
+ // Deal with the special case of an empty page
+ if ( nbElems == 0 )
+ {
+ newLeaf.keys[0] = key;
+
+ newLeaf.values[0] = valueHolder;
+ }
+ else
+ {
+ // Copy the keys and the values up to the insertion position
+ System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
+ System.arraycopy( values, 0, newLeaf.values, 0, pos );
+
+ // Add the new element
+ newLeaf.keys[pos] = key;
+ newLeaf.values[pos] = valueHolder;
+
+ // And copy the remaining elements
+ System.arraycopy( keys, pos, newLeaf.keys, pos + 1, keys.length - pos );
+ System.arraycopy( values, pos, newLeaf.values, pos + 1, values.length - pos );
+ }
+
+ return newLeaf;
+ }
+
+
+ /**
+ * Split a full page into two new pages, a left, a right and a pivot element. The new pages will
+ * each contains half of the original elements. <br/>
+ * The pivot will be computed, depending on the place
+ * we will inject the newly added element. <br/>
+ * If the newly added element is in the middle, we will use it
+ * as a pivot. Otherwise, we will use either the last element in the left page if the element is added
+ * on the left, or the first element in the right page if it's added on the right.
+ *
+ * @param revision The new revision for all the created pages
+ * @param key The key to add
+ * @param value The value to add
+ * @param pos The position of the insertion of the new element
+ * @return An OverflowPage containing the pivot, and the new left and right pages
+ */
+ private InsertResult<K, V> addAndSplit( long revision, K key, V value, int pos )
+ {
+ int middle = btree.getPageSize() >> 1;
+ Leaf<K, V> leftLeaf = null;
+ Leaf<K, V> rightLeaf = null;
+ ElementHolder<V, K, V> valueHolder = btree.createValueHolder( value );
+
+ // Determinate where to store the new value
+ if ( pos <= middle )
+ {
+ // The left page will contain the new value
+ leftLeaf = new Leaf<K, V>( btree, revision, middle + 1 );
+
+ // Copy the keys and the values up to the insertion position
+ System.arraycopy( keys, 0, leftLeaf.keys, 0, pos );
+ System.arraycopy( values, 0, leftLeaf.values, 0, pos );
+
+ // Add the new element
+ leftLeaf.keys[pos] = key;
+ leftLeaf.values[pos] = valueHolder;
+
+ // And copy the remaining elements
+ System.arraycopy( keys, pos, leftLeaf.keys, pos + 1, middle - pos );
+ System.arraycopy( values, pos, leftLeaf.values, pos + 1, middle - pos );
+
+ // Now, create the right page
+ rightLeaf = new Leaf<K, V>( btree, revision, middle );
+
+ // Copy the keys and the values in the right page
+ System.arraycopy( keys, middle, rightLeaf.keys, 0, middle );
+ System.arraycopy( values, middle, rightLeaf.values, 0, middle );
+ }
+ else
+ {
+ // Create the left page
+ leftLeaf = new Leaf<K, V>( btree, revision, middle );
+
+ // Copy all the element into the left page
+ System.arraycopy( keys, 0, leftLeaf.keys, 0, middle );
+ System.arraycopy( values, 0, leftLeaf.values, 0, middle );
+
+ // Now, create the right page
+ rightLeaf = new Leaf<K, V>( btree, revision, middle + 1 );
+
+ int rightPos = pos - middle;
+
+ // Copy the keys and the values up to the insertion position
+ System.arraycopy( keys, middle, rightLeaf.keys, 0, rightPos );
+ System.arraycopy( values, middle, rightLeaf.values, 0, rightPos );
+
+ // Add the new element
+ rightLeaf.keys[rightPos] = key;
+ rightLeaf.values[rightPos] = valueHolder;
+
+ // And copy the remaining elements
+ System.arraycopy( keys, pos, rightLeaf.keys, rightPos + 1, nbElems - pos );
+ System.arraycopy( values, pos, rightLeaf.values, rightPos + 1, nbElems - pos );
+ }
+
+ // Get the pivot
+ K pivot = rightLeaf.keys[0];
+
+ // Create the result
+ InsertResult<K, V> result = new SplitResult<K, V>( pivot, leftLeaf, rightLeaf );
+
+ return result;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public K getLeftMostKey()
+ {
+ return keys[0];
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public K getRightMostKey()
+ {
+ return keys[nbElems - 1];
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public Tuple<K, V> findLeftMost() throws IOException
+ {
+ V val = null;
+
+ if ( btree.isAllowDuplicates() )
+ {
+ BTree<V, V> dupTree = ( BTree<V, V> ) values[0].getValue( btree );
+ val = dupTree.rootPage.getLeftMostKey();
+ }
+ else
+ {
+ val = values[0].getValue( btree );
+ }
+
+ return new Tuple<K, V>( keys[0], val );
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException
+ {
+ V val = null;
+
+ if ( btree.isAllowDuplicates() )
+ {
+ BTree<V, V> dupTree = ( BTree<V, V> ) values[nbElems - 1].getValue( btree );
+ val = dupTree.rootPage.getRightMostKey();
+ }
+ else
+ {
+ val = values[nbElems - 1].getValue( btree );
+ }
+
+ return new Tuple<K, V>( keys[nbElems - 1], val );
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "Leaf[" );
+ sb.append( super.toString() );
+
+ sb.append( "] -> {" );
+
+ if ( nbElems > 0 )
+ {
+ boolean isFirst = true;
+
+ for ( int i = 0; i < nbElems; i++ )
+ {
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ sb.append( ", " );
+ }
+
+ sb.append( "<" ).append( keys[i] ).append( "," ).append( values[i] ).append( ">" );
+ }
+ }
+
+ sb.append( "}" );
+
+ return sb.toString();
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public String dumpPage( String tabs )
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( tabs );
+
+ if ( nbElems > 0 )
+ {
+ boolean isFirst = true;
+
+ for ( int i = 0; i < nbElems; i++ )
+ {
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ sb.append( ", " );
+ }
+
+ sb.append( "<" ).append( keys[i] ).append( "," ).append( values[i] ).append( ">" );
+ }
+ }
+
+ sb.append( "\n" );
+
+ return sb.toString();
+ }
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/MemoryHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/MemoryHolder.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/MemoryHolder.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/MemoryHolder.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,80 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.memory;
+
+
+/**
+ * A In-Memory Value holder. The value is always present in memory.
+ *
+ * @param <K> The type of the BTree key
+ * @param <V> The type of the BTree value
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class MemoryHolder<K, V> implements ElementHolder<V, K, V>
+{
+ /** The BTree */
+ private BTree<K, V> btree;
+
+ /** The reference to the Value instance, or null if it's not present */
+ private V value;
+
+
+ /**
+ * Create a new holder storing an offset and a SoftReference containing the value.
+ *
+ * @param offset The offset in disk for this value
+ * @param value The value to store into a SoftReference
+ */
+ public MemoryHolder( BTree<K, V> btree, V value )
+ {
+ this.btree = btree;
+ this.value = value;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public V getValue( BTree<K, V> btree )
+ {
+ return value;
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "'" );
+
+ V value = getValue( btree );
+
+ sb.append( value );
+
+ sb.append( "'" );
+
+ return sb.toString();
+ }
+}
Added: 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=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/MergedWithSiblingResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/MergedWithSiblingResult.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,78 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.memory;
+
+
+import java.util.List;
+
+import org.apache.directory.mavibot.btree.Tuple;
+
+
+/**
+ * The result of a delete operation, when the child has not been merged. It contains the
+ * reference to the modified page, and the removed element.
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+/* No qualifier */class MergedWithSiblingResult<K, V> extends AbstractDeleteResult<K, V>
+{
+ /**
+ * The default constructor for RemoveResult.
+ *
+ * @param modifiedPage The modified page
+ * @param removedElement The removed element (can be null if the key wasn't present in the tree)
+ */
+ /* No qualifier */MergedWithSiblingResult( Page<K, V> modifiedPage, Tuple<K, V> removedElement )
+ {
+ super( modifiedPage, removedElement );
+ }
+
+
+ /**
+ * A constructor for RemoveResult which takes a list of copied page.
+ *
+ * @param copiedPages the list of copied pages
+ * @param modifiedPage The modified page
+ * @param removedElement The removed element (can be null if the key wasn't present in the tree)
+ */
+ /* No qualifier */MergedWithSiblingResult( List<Page<K, V>> copiedPages, Page<K, V> modifiedPage,
+ Tuple<K, V> removedElement )
+ {
+ super( copiedPages, modifiedPage, removedElement );
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "MergedWithSiblingResult" );
+ sb.append( "\n removed element : " ).append( getRemovedElement() );
+ sb.append( "\n modifiedPage : " ).append( getModifiedPage() );
+
+ return sb.toString();
+ }
+}