directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1527458 [3/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...
Date Mon, 30 Sep 2013 06:32:28 GMT
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BorrowedFromSiblingResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BorrowedFromSiblingResult.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BorrowedFromSiblingResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BorrowedFromSiblingResult.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,53 @@
+/*
+ *  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.managed;
+
+
+/**
+ * The result of an delete operation, when we have borrowed some element from a sibling.
+ * 
+ * @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 BorrowedFromSiblingResult<K, V> extends DeleteResult<K, V>
+{
+    /**
+     * @return the modifiedSibling
+     */
+    Page<K, V> getModifiedSibling();
+
+
+    /**
+     * Tells if the sibling is on the left
+     * 
+     * @return True if the sibling is on the left
+     */
+    boolean isFromLeft();
+
+
+    /**
+     * Tells if the sibling is on the right
+     * 
+     * @return True if the sibling is on the right
+     */
+    boolean isFromRight();
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BulkDataSorter.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BulkDataSorter.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BulkDataSorter.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/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.managed;
+
+
+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/managed/CacheHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/CacheHolder.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/CacheHolder.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/CacheHolder.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,183 @@
+/*
+ *  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.managed;
+
+
+import java.io.IOException;
+
+import net.sf.ehcache.Element;
+
+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 value or a page)
+ * @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 CacheHolder<E, K, V> implements ElementHolder<E, K, V>
+{
+    /** The BTree */
+    private BTree<K, V> btree;
+
+    /** The offset of the first {@link PageIO} storing the page on disk */
+    private long offset;
+
+    /** The offset of the last {@link PageIO} storing the page on disk */
+    private long lastOffset;
+
+
+    /**
+     * Create a new holder storing an offset and a SoftReference containing the element.
+     * 
+     * @param offset The offset in disk for this value
+     * @param element The element to store into a SoftReference
+     */
+    public CacheHolder( BTree<K, V> btree, Page<K, V> element, long offset, long lastOffset )
+    {
+        this.btree = btree;
+        this.offset = offset;
+        this.lastOffset = lastOffset;
+
+        if ( element instanceof Page<?, ?> )
+        {
+            ( ( AbstractPage<K, V> ) element ).setOffset( offset );
+            ( ( AbstractPage<K, V> ) element ).setLastOffset( lastOffset );
+        }
+
+        btree.getCache().put( new Element( offset, element ) );
+    }
+
+
+    /**
+     * {@inheritDoc}
+     * @throws IOException 
+     * @throws EndOfFileExceededException 
+     */
+    @Override
+    public E getValue( BTree<K, V> btree ) throws EndOfFileExceededException, IOException
+    {
+        Element element = btree.getCache().get( offset );
+
+        if ( element == null )
+        {
+            // We haven't found the element in the cache, reload it
+            // We have to fetch the element from disk, using the offset now
+            Page<K, V> page = fetchElement( btree );
+
+            btree.getCache().put( new Element( offset, page ) );
+
+            return ( E ) page;
+        }
+
+        V value = ( V ) element.getObjectValue();
+
+        if ( value == null )
+        {
+            // We have to fetch the element from disk, using the offset now
+            Page<K, V> page = fetchElement( btree );
+
+            if ( page instanceof Page<?, ?> )
+            {
+                ( ( AbstractPage<K, V> ) page ).setOffset( offset );
+                ( ( AbstractPage<K, V> ) page ).setLastOffset( lastOffset );
+            }
+
+            btree.getCache().put( new Element( offset, page ) );
+
+            element = btree.getCache().get( offset );
+
+            return ( E ) page;
+        }
+        else
+        {
+            return ( E ) value;
+        }
+    }
+
+
+    /**
+     * Retrieve the value from the disk, using the BTree and offset
+     * @return The deserialized element (
+     * @throws IOException 
+     * @throws EndOfFileExceededException 
+     */
+    private Page<K, V> fetchElement( BTree<K, V> btree ) throws EndOfFileExceededException, IOException
+    {
+        Page<K, V> element = btree.getRecordManager().deserialize( btree, offset );
+
+        return element;
+    }
+
+
+    /**
+     * @return The offset of the first {@link PageIO} storing the data on disk
+     */
+    /* No qualifier */long getOffset()
+    {
+        return offset;
+    }
+
+
+    /**
+     * @return The offset of the last {@link PageIO} storing the data on disk
+     */
+    /* No qualifier */long getLastOffset()
+    {
+        return lastOffset;
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        StringBuilder sb = new StringBuilder();
+
+        try
+        {
+            E element = getValue( btree );
+
+            if ( element != null )
+            {
+                sb.append( btree.getName() ).append( "[" ).append( offset ).append( ", " ).append( lastOffset )
+                    .append( "]:" ).append( element );
+            }
+            else
+            {
+                sb.append( btree.getName() ).append( "[" ).append( offset ).append( ", " ).append( lastOffset )
+                    .append( "]" );
+            }
+        }
+        catch ( IOException ioe )
+        {
+            // Nothing we can do...
+        }
+
+        return sb.toString();
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/CursorImpl.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/CursorImpl.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/CursorImpl.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/CursorImpl.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,650 @@
+/*
+ *  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.managed;
+
+
+import static org.apache.directory.mavibot.btree.managed.InternalUtil.changeNextDupsContainer;
+import static org.apache.directory.mavibot.btree.managed.InternalUtil.changePrevDupsContainer;
+import static org.apache.directory.mavibot.btree.managed.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/managed/DeleteResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/DeleteResult.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/DeleteResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/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.managed;
+
+
+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/managed/DuplicateKeyVal.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/DuplicateKeyVal.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/DuplicateKeyVal.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/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.managed;
+
+
+/**
+ * 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/managed/ElementHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ElementHolder.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ElementHolder.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/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.managed;
+
+
+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/managed/InsertResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InsertResult.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InsertResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/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.managed;
+
+
+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/managed/InternalUtil.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/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.managed;
+
+
+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 );
+    }
+}



Mime
View raw message