directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kayyag...@apache.org
Subject svn commit: r1510115 [3/13] - in /directory/mavibot/trunk: ./ mavibot/ mavibot/src/main/java/org/apache/directory/ mavibot/src/main/java/org/apache/directory/mavibot/ mavibot/src/main/java/org/apache/directory/mavibot/btree/ mavibot/src/main/java/org/a...
Date Sun, 04 Aug 2013 09:22:58 GMT
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeHeader.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeHeader.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeHeader.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeHeader.java Sun Aug  4 09:22:56 2013
@@ -0,0 +1,361 @@
+/*
+ *  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;
+
+
+import java.util.concurrent.atomic.AtomicLong;
+
+
+/**
+ * Store in memory the information associated with a BTree. <br>
+ * A BTree Header on disk contains the following elements :
+ * <pre>
+ * +--------------------+-------------+
+ * | revision           | 8 bytes     |
+ * +--------------------+-------------+
+ * | nbElems            | 8 bytes     |
+ * +--------------------+-------------+
+ * | rootPageOffset     | 8 bytes     |
+ * +--------------------+-------------+
+ * | nextBtreeHeader    | 8 bytes     |
+ * +--------------------+-------------+
+ * | pageSize           | 4 bytes     |
+ * +--------------------+-------------+
+ * | name               | 4 bytes + N |
+ * +--------------------+-------------+
+ * | keySerializeFQCN   | 4 bytes + N |
+ * +--------------------+-------------+
+ * | valueSerializeFQCN | 4 bytes + N |
+ * +--------------------+-------------+
+ * </pre>
+ * Each BtreeHeader will be written starting on a new page.
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+/* No qualifier*/class BTreeHeader
+{
+    /** The current revision */
+    private AtomicLong revision = new AtomicLong( 0L );
+
+    /** The number of elements in this BTree */
+    private AtomicLong nbElems = new AtomicLong( 0L );
+
+    /** The offset of the BTree RootPage */
+    private long rootPageOffset;
+
+    /** The offset of the next BTree */
+    private long nextBTreeOffset;
+
+    /** The number of elements in a page for this BTree */
+    private int pageSize;
+
+    /** The BTree name */
+    private String name;
+
+    /** The FQCN of the Key serializer */
+    private String keySerializerFQCN;
+
+    /** The FQCN of the Value serializer */
+    private String valueSerializerFQCN;
+
+    // Those are data which aren't serialized : they are in memory only */
+    /** The position in the file */
+    private long btreeOffset;
+
+    /** The existing versions */
+    private long[] versions;
+
+    private int allowDuplicates = 0;
+
+    /**
+     * Creates a BTreeHeader instance
+     */
+    public BTreeHeader()
+    {
+    }
+
+
+    /**
+     * @return the name
+     */
+    public String getName()
+    {
+        return name;
+    }
+
+
+    /**
+     * @param name the name to set
+     */
+    public void setName( String name )
+    {
+        this.name = name;
+    }
+
+
+    /**
+     * @return the versions
+     */
+    public long[] getVersions()
+    {
+        return versions;
+    }
+
+
+    /**
+     * @param versions the versions to set
+     */
+    /* No qualifier*/void setVersions( long[] versions )
+    {
+        this.versions = versions;
+    }
+
+
+    /**
+     * @return the btreeOffset
+     */
+    /* No qualifier*/long getBTreeOffset()
+    {
+        return btreeOffset;
+    }
+
+
+    /**
+     * @param btreeOffset the btreeOffset to set
+     */
+    /* No qualifier*/void setBTreeOffset( long btreeOffset )
+    {
+        this.btreeOffset = btreeOffset;
+    }
+
+
+    /**
+     * @return the rootPageOffset
+     */
+    /* No qualifier*/long getRootPageOffset()
+    {
+        return rootPageOffset;
+    }
+
+
+    /**
+     * @param rootPageOffset the rootPageOffset to set
+     */
+    /* No qualifier*/void setRootPageOffset( long rootPageOffset )
+    {
+        this.rootPageOffset = rootPageOffset;
+    }
+
+
+    /**
+     * @return the revision
+     */
+    public long getRevision()
+    {
+        return revision.get();
+    }
+
+
+    /**
+     * @param revision the revision to set
+     */
+    /* No qualifier*/void setRevision( long revision )
+    {
+        this.revision.set( revision );
+    }
+
+
+    /**
+     * Increment the revision
+     * 
+     * @return the new revision
+     */
+    /* No qualifier*/long incrementRevision()
+    {
+        return revision.incrementAndGet();
+    }
+
+
+    /**
+     * @return the nbElems
+     */
+    public long getNbElems()
+    {
+        return nbElems.get();
+    }
+
+
+    /**
+     * Increment the number of elements
+     */
+    /* No qualifier*/void incrementNbElems()
+    {
+        nbElems.incrementAndGet();
+    }
+
+
+    /**
+     * Decrement the number of elements
+     */
+    /* No qualifier*/void decrementNbElems()
+    {
+        nbElems.decrementAndGet();
+    }
+
+
+    /**
+     * @param nbElems the nbElems to set
+     */
+    public void setNbElems( long nbElems )
+    {
+        this.nbElems.set( nbElems );
+    }
+
+
+    /**
+     * @return the nextBTreeOffset
+     */
+    /* No qualifier*/long getNextBTreeOffset()
+    {
+        return nextBTreeOffset;
+    }
+
+
+    /**
+     * @param nextBtreeOffset the nextBtreeOffset to set
+     */
+    /* No qualifier*/void setNextBTreeOffset( long nextBTreeOffset )
+    {
+        this.nextBTreeOffset = nextBTreeOffset;
+    }
+
+
+    /**
+     * @return the pageSize
+     */
+    public int getPageSize()
+    {
+        return pageSize;
+    }
+
+
+    /**
+     * @param pageSize the pageSize to set
+     */
+    public void setPageSize( int pageSize )
+    {
+        this.pageSize = pageSize;
+    }
+
+
+    /**
+     * @return the keySerializerFQCN
+     */
+    /* No qualifier*/String getKeySerializerFQCN()
+    {
+        return keySerializerFQCN;
+    }
+
+
+    /**
+     * @param keySerializerFQCN the keySerializerFQCN to set
+     */
+    /* No qualifier*/void setKeySerializerFQCN( String keySerializerFQCN )
+    {
+        this.keySerializerFQCN = keySerializerFQCN;
+    }
+
+
+    /**
+     * @return the valueSerializerFQCN
+     */
+    /* No qualifier*/String getValueSerializerFQCN()
+    {
+        return valueSerializerFQCN;
+    }
+
+
+    /**
+     * @param valueSerializerFQCN the valueSerializerFQCN to set
+     */
+    /* No qualifier*/void setValueSerializerFQCN( String valueSerializerFQCN )
+    {
+        this.valueSerializerFQCN = valueSerializerFQCN;
+    }
+
+
+    /* No qualifier*/boolean isAllowDuplicates()
+    {
+        return ( allowDuplicates == 1 );
+    }
+
+
+    /* No qualifier*/void setAllowDuplicates( boolean allowDuplicates )
+    {
+        this.allowDuplicates = ( allowDuplicates ? 1 : 0 );
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( "Btree '" ).append( name ).append( "'" );
+        sb.append( ", revision[" ).append( revision ).append( "]" );
+        sb.append( ", btreeOffset[" ).append( btreeOffset ).append( "]" );
+        sb.append( ", rootPageOffset[" ).append( rootPageOffset ).append( "]" );
+        sb.append( ", nextBTree[" ).append( nextBTreeOffset ).append( "]" );
+        sb.append( ", nbElems[" ).append( nbElems ).append( "]" );
+        sb.append( ", pageSize[" ).append( pageSize ).append( "]" );
+        sb.append( ", hasDuplicates[" ).append( isAllowDuplicates() ).append( "]" );
+        sb.append( "{\n" );
+        sb.append( "    Key serializer   : " ).append( keySerializerFQCN ).append( "\n" );
+        sb.append( "    Value serializer : " ).append( valueSerializerFQCN ).append( "\n" );
+        sb.append( "}\n" );
+
+        if ( ( versions != null ) && ( versions.length != 0 ) )
+        {
+            sb.append( "Versions : \n" );
+            sb.append( "{\n" );
+
+            boolean isFirst = true;
+
+            for ( long version : versions )
+            {
+                if ( isFirst )
+                {
+                    isFirst = false;
+                }
+                else
+                {
+                    sb.append( ",\n" );
+                }
+
+                sb.append( "    " ).append( version );
+            }
+
+            sb.append( "}\n" );
+        }
+
+        return sb.toString();
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeTypeEnum.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeTypeEnum.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeTypeEnum.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeTypeEnum.java Sun Aug  4 09:22:56 2013
@@ -0,0 +1,43 @@
+/*
+ *  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;
+
+
+/**
+ * An enum to describe the BTree type. We have three possible type :
+ * <ul>
+ * <li>IN_MEMORY : the BTree will remain in memory, and won't be persisted on disk</li>
+ * <li>PERSISTENT : the BTree is in memory, but will be persisted on disk</li>
+ * <li>MANAGED : the BTree is managed by a RecordManager, and some pages may
+ * be swapped out from memory on demand</li>
+ * </ul>
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+public enum BTreeTypeEnum
+{
+    /** Pure in-memory BTree, not persisted on disk */
+    IN_MEMORY,
+
+    /** In-memory BTree but persisted on disk */
+    PERSISTENT,
+
+    /** A BTree associated with a RecordManager */
+    MANAGED
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromLeftResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromLeftResult.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromLeftResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromLeftResult.java Sun Aug  4 09:22:56 2013
@@ -0,0 +1,81 @@
+/*
+ *  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;
+
+
+import java.util.List;
+
+
+/**
+ * The result of a delete operation, when the child has not been merged, and when
+ * we have borrowed an element from the left sibling. 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:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+/* No qualifier */class BorrowedFromLeftResult<K, V> extends AbstractBorrowedFromSiblingResult<K, V>
+{
+    /**
+     * The default constructor for BorrowedFromLeftResult.
+     * 
+     * @param modifiedPage The modified page
+     * @param modifiedSibling The modified sibling
+     * @param removedElement The removed element (can be null if the key wasn't present in the tree)
+     */
+    /* No qualifier */BorrowedFromLeftResult( Page<K, V> modifiedPage, Page<K, V> modifiedSibling,
+        Tuple<K, V> removedElement )
+    {
+        super( modifiedPage, modifiedSibling, removedElement, AbstractBorrowedFromSiblingResult.SiblingPosition.LEFT );
+    }
+
+
+    /**
+     * A constructor for BorrowedFromLeftResult which takes a list of copied pages.
+     * 
+     * @param copiedPages the list of copied pages
+     * @param modifiedPage The modified page
+     * @param modifiedSibling The modified sibling
+     * @param removedElement The removed element (can be null if the key wasn't present in the tree)
+     */
+    /* No qualifier */BorrowedFromLeftResult( List<Page<K, V>> copiedPages, Page<K, V> modifiedPage,
+        Page<K, V> modifiedSibling,
+        Tuple<K, V> removedElement )
+    {
+        super( copiedPages, modifiedPage, modifiedSibling, removedElement,
+            AbstractBorrowedFromSiblingResult.SiblingPosition.LEFT );
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( "Borrowed from left" );
+        sb.append( super.toString() );
+
+        return sb.toString();
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromRightResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromRightResult.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromRightResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromRightResult.java Sun Aug  4 09:22:56 2013
@@ -0,0 +1,79 @@
+/*
+ *  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;
+
+
+import java.util.List;
+
+
+/**
+ * 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:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+/* No qualifier */class BorrowedFromRightResult<K, V> extends AbstractBorrowedFromSiblingResult<K, V>
+{
+    /**
+     * The default constructor for BorrowedFromRightResult.
+     * 
+     * @param modifiedPage The modified page
+     * @param modifiedSibling The modified sibling
+     * @param removedElement The removed element (can be null if the key wasn't present in the tree)
+     */
+    /* No qualifier */BorrowedFromRightResult( Page<K, V> modifiedPage, Page<K, V> modifiedSibling,
+        Tuple<K, V> removedElement )
+    {
+        super( modifiedPage, modifiedSibling, removedElement, AbstractBorrowedFromSiblingResult.SiblingPosition.RIGHT );
+    }
+
+
+    /**
+     * A constructor for BorrowedFromRightResult which takes a list of copied pages.
+     * 
+     * @param copiedPages the list of copied pages
+     * @param modifiedPage The modified page
+     * @param modifiedSibling The modified sibling
+     * @param removedElement The removed element (can be null if the key wasn't present in the tree)
+     */
+    /* No qualifier */BorrowedFromRightResult( List<Page<K, V>> copiedPages, Page<K, V> modifiedPage,
+        Page<K, V> modifiedSibling, Tuple<K, V> removedElement )
+    {
+        super( copiedPages, modifiedPage, modifiedSibling, removedElement,
+            AbstractBorrowedFromSiblingResult.SiblingPosition.RIGHT );
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( "Borrowed from right" );
+        sb.append( super.toString() );
+
+        return sb.toString();
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromSiblingResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromSiblingResult.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromSiblingResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BorrowedFromSiblingResult.java Sun Aug  4 09:22:56 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;
+
+
+/**
+ * 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:labs@labs.apache.org">Mavibot labs 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/Cursor.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.java Sun Aug  4 09:22:56 2013
@@ -0,0 +1,581 @@
+/*
+ *  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;
+
+
+import java.io.IOException;
+import java.util.LinkedList;
+import java.util.NoSuchElementException;
+
+import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
+
+import static org.apache.directory.mavibot.btree.InternalUtil.*;
+
+/**
+ * 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>
+ * 
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+ */
+public class 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
+     */
+    /* No qualifier */Cursor( 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 )
+        {
+            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 )
+        {
+            setDupsContainer( parentPos, btree );
+            
+            // can happen if prev() was called after next()
+            if( parentPos.pos == parentPos.page.getNbElems() )
+            {
+                parentPos.pos--;
+            }
+            
+            if( parentPos.dupPos == parentPos.dupsContainer.getNbElems() )
+            {
+                parentPos.dupPos--;
+            }
+            else if( parentPos.dupPos == 0 )
+            {
+                changePrevDupsContainer( parentPos, btree );
+                parentPos.pos--;
+                parentPos.dupPos--;
+            }
+            else
+            {
+                parentPos.dupPos--;
+            }
+            
+            tuple.setKey( leaf.keys[parentPos.pos] );
+            tuple.setValue( parentPos.dupsContainer.rootPage.getKey( parentPos.dupPos ) );
+        }
+        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.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.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 = ( LinkedList<ParentPos<K, V>> ) 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/DeleteResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/DeleteResult.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/DeleteResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/DeleteResult.java Sun Aug  4 09:22:56 2013
@@ -0,0 +1,43 @@
+/*
+ *  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;
+
+
+/**
+ * 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:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+interface DeleteResult<K, V> extends Result<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/Deletion.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Deletion.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Deletion.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Deletion.java Sun Aug  4 09:22:56 2013
@@ -0,0 +1,42 @@
+/*
+ *  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;
+
+
+/**
+ * A class used to store a Delete modification done on a BTree.
+ *  
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
+ *
+ * @param <K> The key type
+ * @param <V> The value type
+ */
+public class Deletion<K, V> extends Modification<K, V>
+{
+    /**
+     * Create a new Deletion instance.
+     * 
+     * @param key The key to be deleted
+     */
+    public Deletion( K key )
+    {
+        super( key, null );
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/DuplicateKeyMemoryHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/DuplicateKeyMemoryHolder.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/DuplicateKeyMemoryHolder.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/DuplicateKeyMemoryHolder.java Sun Aug  4 09:22:56 2013
@@ -0,0 +1,167 @@
+/*
+ *  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;
+
+
+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:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+public class DuplicateKeyMemoryHolder<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;
+
+
+    /**
+     * 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 DuplicateKeyMemoryHolder( BTree<K, V> btree, V value )
+    {
+        this.btree = btree;
+
+        try
+        {
+            BTree<V, V> valueContainer = new BTree<V, V>( UUID.randomUUID().toString(), btree.getValueSerializer(),
+                btree.getValueSerializer() );
+
+            if ( btree.isManaged() )
+            {
+                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 );
+            }
+            else
+            {
+                this.valueContainer = valueContainer;
+            }
+
+            valueContainer.insert( value, null, 0 );
+        }
+        catch ( IOException e )
+        {
+            throw new RuntimeException( e );
+        }
+    }
+
+
+    /**
+     * 
+     * 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
+     */
+    /* No qualifier */DuplicateKeyMemoryHolder( BTree<K, V> btree, BTree<V, V> valueContainer )
+    {
+        this.btree = btree;
+
+        if ( btree.isManaged() )
+        {
+            valContainerOffset = valueContainer.getBtreeOffset();
+            reference = new SoftReference<BTree<V, V>>( valueContainer );
+        }
+        else
+        {
+            this.valueContainer = valueContainer;
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public V getValue( BTree<K, V> btree )
+    {
+        if ( !btree.isManaged() )
+        {
+            // wrong cast to please compiler
+            return ( V ) valueContainer;
+        }
+
+        BTree<V, V> valueContainer = reference.get();
+
+        if ( valueContainer == null )
+        {
+            valueContainer = btree.getRecordManager().loadDupsBTree( valContainerOffset );
+            reference = new SoftReference<BTree<V, V>>( valueContainer );
+        }
+
+        return ( V ) valueContainer;
+    }
+
+
+    /**
+     * @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/ElementHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ElementHolder.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ElementHolder.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/ElementHolder.java Sun Aug  4 09:22:56 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;
+
+
+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 value or a page)
+ * @param <K> The type of the BTree key
+ * @param <V> The type of the BTree value
+ *
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs 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/InsertResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InsertResult.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InsertResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InsertResult.java Sun Aug  4 09:22:56 2013
@@ -0,0 +1,35 @@
+/*
+ *  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;
+
+
+/**
+ * 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:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+interface InsertResult<K, V> extends Result<K, V>
+{
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InternalUtil.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InternalUtil.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InternalUtil.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InternalUtil.java Sun Aug  4 09:22:56 2013
@@ -0,0 +1,127 @@
+/*
+ *   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;
+
+
+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;
+        }
+
+        try
+        {
+            if ( parentPos.dupsContainer == null )
+            {
+                Leaf leaf = ( Leaf ) ( parentPos.page );
+                BTree dupsContainer = ( BTree ) leaf.values[parentPos.pos].getValue( btree );
+                parentPos.dupsContainer = dupsContainer;
+            }
+        }
+        catch ( IOException e )
+        {
+            throw new RuntimeException( e );
+        }
+    }
+
+
+    /**
+     * 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 );
+            BTree dupsContainer = ( BTree ) leaf.values[parentPos.pos].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 );
+            BTree dupsContainer = ( BTree ) leaf.values[index].getValue( btree );
+            parentPos.dupsContainer = dupsContainer;
+            parentPos.dupPos = ( int ) parentPos.dupsContainer.getNbElems();
+        }
+    }
+
+
+    /**
+     * 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