directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1527458 [4/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/Leaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Leaf.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/Leaf.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/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.managed;
+
+
+import static org.apache.directory.mavibot.btree.managed.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/managed/MemoryHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/MemoryHolder.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/MemoryHolder.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/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.managed;
+
+
+/**
+ * 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/managed/MergedWithSiblingResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/MergedWithSiblingResult.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/MergedWithSiblingResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/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.managed;
+
+
+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();
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ModifyResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ModifyResult.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ModifyResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ModifyResult.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,104 @@
+/*
+ *  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.util.List;
+
+
+/**
+ * The result of an insert operation, when the child has not been split. It contains the
+ * reference to the modified page.
+ * 
+ * @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 ModifyResult<K, V> extends AbstractResult<K, V> implements InsertResult<K, V>
+{
+    /** The modified page reference */
+    protected Page<K, V> modifiedPage;
+
+    /** The modified value if the key was found in the tree*/
+    protected V modifiedValue;
+
+
+    /**
+     * The default constructor for ModifyResult.
+     * 
+     * @param modifiedPage The modified page
+     * @param modifiedvalue The modified value (can be null if the key wasn't present in the tree)
+     */
+    /* No qualifier */ModifyResult( Page<K, V> modifiedPage, V modifiedValue )
+    {
+        super();
+        this.modifiedPage = modifiedPage;
+        this.modifiedValue = modifiedValue;
+    }
+
+
+    /**
+     * A constructor for ModifyResult which takes a list of copied pages.
+     * 
+     * @param copiedPages the list of copied pages
+     * @param modifiedPage The modified page
+     * @param modifiedvalue The modified value (can be null if the key wasn't present in the tree)
+     */
+    /* No qualifier */ModifyResult( List<Page<K, V>> copiedPages, Page<K, V> modifiedPage, V modifiedValue )
+    {
+        super( copiedPages );
+        this.modifiedPage = modifiedPage;
+        this.modifiedValue = modifiedValue;
+    }
+
+
+    /**
+     * @return the modifiedPage
+     */
+    /* No qualifier */Page<K, V> getModifiedPage()
+    {
+        return modifiedPage;
+    }
+
+
+    /**
+     * @return the modifiedValue
+     */
+    /* No qualifier */V getModifiedValue()
+    {
+        return modifiedValue;
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( "ModifyResult, old value = " ).append( modifiedValue );
+        sb.append( ", modifiedPage = " ).append( modifiedPage );
+        sb.append( super.toString() );
+
+        return sb.toString();
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/MultipleMemoryHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/MultipleMemoryHolder.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/MultipleMemoryHolder.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/MultipleMemoryHolder.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,203 @@
+/*
+ *  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 java.lang.ref.SoftReference;
+import java.util.UUID;
+
+import org.apache.directory.mavibot.btree.exception.BTreeAlreadyManagedException;
+
+
+/**
+ * A holder for values of duplicate keys. The values are either present in memory
+ * or loaded on the fly from disk when needed.
+ * 
+ * @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 MultipleMemoryHolder<K, V> implements ElementHolder<V, K, V>
+{
+    /** The BTree */
+    private BTree<K, V> btree;
+
+    /** the offset of the value container btree. This value is set only when the parent BTree is in managed mode */
+    private long valContainerOffset = -1;
+
+    /** The reference to the Value instance, or null if it's not present. This will be null when the parent BTree is in managed mode */
+    private BTree<V, V> valueContainer;
+
+    /** This value is set only when the parent BTree is in managed mode */
+    private SoftReference<BTree<V, V>> reference;
+
+    /** the single value of the key when only one value exists for the key */
+    private V singleValue;
+
+
+    /**
+     * 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 MultipleMemoryHolder( BTree<K, V> btree, V value )
+    {
+        this.btree = btree;
+        this.singleValue = value;
+    }
+
+
+    /**
+     * 
+     * Creates a new instance of DuplicateKeyMemoryHolder.
+     * 
+     * Note: the valueContainer should have a valid offset, in other words
+     *       the valueContainer should always be the one that is already
+     *       managed by RecordManager
+     * 
+     * @param btree the parent BTree
+     * @param valueContainer the BTree holding the values of a duplicate key
+     *        present in the parent tree
+     */
+    MultipleMemoryHolder( BTree<K, V> btree, BTree<V, V> valueContainer )
+    {
+        this.btree = btree;
+
+        valContainerOffset = valueContainer.getBtreeOffset();
+        reference = new SoftReference<BTree<V, V>>( valueContainer );
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public V getValue( BTree<K, V> btree )
+    {
+        if ( reference != null )
+        {
+            BTree<V, V> valueContainer = reference.get();
+
+            if ( valueContainer == null )
+            {
+                valueContainer = btree.getRecordManager().loadDupsBTree( valContainerOffset );
+                reference = new SoftReference<BTree<V, V>>( valueContainer );
+            }
+
+            return ( V ) valueContainer;
+        }
+
+        return singleValue;
+    }
+
+
+    void switchToSingleValMode()
+    {
+        if ( ( valueContainer == null ) || ( reference == null ) )
+        {
+            return;
+        }
+
+        try
+        {
+            //delete the btree using offset
+            BTree<V, V> values = ( BTree<V, V> ) getValue( btree );
+            singleValue = values.rootPage.getLeftMostKey();
+            reference = null;
+            valContainerOffset = -1;
+            valueContainer = null;
+            //FIXME reclaim the free space of the sub-tree
+            //btree.getRecordManager().freeBtree(values);
+        }
+        catch ( IOException e )
+        {
+            throw new RuntimeException( e );
+        }
+    }
+
+
+    BTree<V, V> createAndSwitchToSubTree()
+    {
+        if ( reference != null )
+        {
+            throw new IllegalStateException( "Subtree was already created with offset " + valContainerOffset );
+        }
+
+        try
+        {
+            BTree<V, V> valueContainer = new BTree<V, V>( UUID.randomUUID().toString(), btree.getValueSerializer(),
+                btree.getValueSerializer() );
+
+            try
+            {
+                btree.getRecordManager().manage( valueContainer, true );
+                valContainerOffset = valueContainer.getBtreeOffset();
+            }
+            catch ( BTreeAlreadyManagedException e )
+            {
+                // should never happen
+                throw new RuntimeException( e );
+            }
+
+            reference = new SoftReference<BTree<V, V>>( valueContainer );
+
+            valueContainer.insert( singleValue, null, 0 );
+        }
+        catch ( IOException e )
+        {
+            throw new RuntimeException( e );
+        }
+
+        return valueContainer;
+    }
+
+
+    /**
+     * Tells if there is only one value in this element holder
+     * 
+     * @return true if single value is present, false if multiple values are present
+     */
+    public boolean isSingleValue()
+    {
+        return ( reference == null );
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( "'" );
+
+        V value = getValue( btree );
+
+        sb.append( value );
+
+        sb.append( "'" );
+
+        return sb.toString();
+    }
+}



Mime
View raw message