directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1527458 [2/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/AbstractPage.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/AbstractPage.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/AbstractPage.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/AbstractPage.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,357 @@
+/*
+ *  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.reflect.Array;
+
+
+/**
+ * A MVCC abstract Page. It stores the field and the methods shared by the Node and Leaf
+ * classes.
+ * 
+ * @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 */abstract class AbstractPage<K, V> implements Page<K, V>
+{
+    /** Parent B+Tree. */
+    protected transient BTree<K, V> btree;
+
+    /** This BPage's revision */
+    protected long revision;
+
+    /** Keys of children nodes */
+    protected K[] keys;
+
+    /** The number of current values in the Page */
+    protected int nbElems;
+
+    /** The first {@link PageIO} storing the serialized Page on disk */
+    private long offset = -1L;
+
+    /** The last {@link PageIO} storing the serialized Page on disk */
+    private long lastOffset = -1L;
+
+
+    /**
+     * Creates a default empty AbstractPage
+     * 
+     * @param btree The associated BTree
+     */
+    protected AbstractPage( BTree<K, V> btree )
+    {
+        this.btree = btree;
+    }
+
+
+    /**
+     * Internal constructor used to create Page instance used when a page is being copied or overflow
+     */
+    @SuppressWarnings("unchecked")
+    // Cannot create an array of generic objects
+    protected AbstractPage( BTree<K, V> btree, long revision, int nbElems )
+    {
+        this.btree = btree;
+        this.revision = revision;
+        this.nbElems = nbElems;
+
+        // We get the type of array to create from the btree
+        // Yes, this is an hack...
+        Class<?> keyType = btree.getKeyType();
+        this.keys = ( K[] ) Array.newInstance( keyType, nbElems );
+    }
+
+
+    /**
+     * Selects the sibling (the previous or next page with the same parent) which has
+     * the more element assuming it's above N/2
+     * 
+     * @param parent The parent of the current page
+     * @param The position of the current page reference in its parent
+     * @return The position of the sibling, or -1 if we have'nt found any sibling
+     * @throws IOException If we have an error while trying to access the page
+     */
+    protected int selectSibling( Node<K, V> parent, int parentPos ) throws IOException
+    {
+        if ( parentPos == 0 )
+        {
+            // The current page is referenced on the left of its parent's page :
+            // we will not have a previous page with the same parent
+            return 1;
+        }
+
+        if ( parentPos == parent.getNbElems() )
+        {
+            // The current page is referenced on the right of its parent's page :
+            // we will not have a next page with the same parent
+            return parentPos - 1;
+        }
+
+        Page<K, V> prevPage = parent.children[parentPos - 1].getValue( btree );
+        Page<K, V> nextPage = parent.children[parentPos + 1].getValue( btree );
+
+        int prevPageSize = prevPage.getNbElems();
+        int nextPageSize = nextPage.getNbElems();
+
+        if ( prevPageSize >= nextPageSize )
+        {
+            return parentPos - 1;
+        }
+        else
+        {
+            return parentPos + 1;
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public int getNbElems()
+    {
+        return nbElems;
+    }
+
+
+    /**
+     * Finds the position of the given key in the page. If we have found the key,
+     * we will return its position as a negative value.
+     * <p/>
+     * Assuming that the array is zero-indexed, the returned value will be : <br/>
+     *   position = - ( position + 1)
+     * <br/>
+     * So for the following table of keys : <br/>
+     * <pre>
+     * +---+---+---+---+
+     * | b | d | f | h |
+     * +---+---+---+---+
+     *   0   1   2   3
+     * </pre>
+     * looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return -3 (-(2+1)).<br/>
+     * Computing the real position is just a matter to get -(position++).
+     * <p/>
+     * If we don't find the key in the table, we will return the position of the key
+     * immediately above the key we are looking for. <br/>
+     * For instance, looking for :
+     * <ul>
+     * <li>'a' will return 0</li>
+     * <li>'b' will return -1</li>
+     * <li>'c' will return 1</li>
+     * <li>'d' will return -2</li>
+     * <li>'e' will return 2</li>
+     * <li>'f' will return -3</li>
+     * <li>'g' will return 3</li>
+     * <li>'h' will return -4</li>
+     * <li>'i' will return 4</li>
+     * </ul>
+     * 
+     * 
+     * @param key The key to find
+     * @return The position in the page.
+     */
+    public int findPos( K key )
+    {
+        // Deal with the special key where we have an empty page
+        if ( nbElems == 0 )
+        {
+            return 0;
+        }
+
+        int min = 0;
+        int max = nbElems - 1;
+
+        // binary search
+        while ( min < max )
+        {
+            int middle = ( min + max + 1 ) >> 1;
+
+            int comp = compare( keys[middle], key );
+
+            if ( comp < 0 )
+            {
+                min = middle + 1;
+            }
+            else if ( comp > 0 )
+            {
+                max = middle - 1;
+            }
+            else
+            {
+                // Special case : the key already exists,
+                // we can return immediately. The value will be
+                // negative, and as the index may be 0, we subtract 1
+                return -( middle + 1 );
+            }
+        }
+
+        // Special case : we don't know if the key is present
+        int comp = compare( keys[max], key );
+
+        if ( comp == 0 )
+        {
+            return -( max + 1 );
+        }
+        else
+        {
+            if ( comp < 0 )
+            {
+                return max + 1;
+            }
+            else
+            {
+                return max;
+            }
+        }
+    }
+
+
+    /**
+     * Compares two keys
+     * 
+     * @param key1 The first key
+     * @param key2 The second key
+     * @return -1 if the first key is above the second one, 1 if it's below, and 0
+     * if the two keys are equal
+     */
+    private final int compare( K key1, K key2 )
+    {
+        if ( key1 == key2 )
+        {
+            return 0;
+        }
+
+        if ( key1 == null )
+        {
+            return 1;
+        }
+
+        if ( key2 == null )
+        {
+            return -1;
+        }
+
+        return btree.getComparator().compare( key1, key2 );
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public long getRevision()
+    {
+        return revision;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public K getKey( int pos )
+    {
+        if ( pos < nbElems )
+        {
+            return keys[pos];
+        }
+        else
+        {
+            return null;
+        }
+    }
+
+
+    /**
+     * Sets the key at a give position
+     * 
+     * @param pos The position in the keys array
+     * @param key the key to inject
+     */
+    /* No qualifier*/void setKey( int pos, K key )
+    {
+        keys[pos] = key;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public long getOffset()
+    {
+        return offset;
+    }
+
+
+    /**
+     * @param offset the offset to set
+     */
+    /* No qualifier */void setOffset( long offset )
+    {
+        this.offset = offset;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public long getLastOffset()
+    {
+        return lastOffset;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    /* No qualifier */void setLastOffset( long lastOffset )
+    {
+        this.lastOffset = lastOffset;
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( "r" ).append( revision );
+        sb.append( ", nbElems:" ).append( nbElems );
+
+        if ( offset > 0 )
+        {
+            sb.append( ", offset:" ).append( offset );
+        }
+
+        return sb.toString();
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public String dumpPage( String tabs )
+    {
+        return "";
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/AbstractResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/AbstractResult.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/AbstractResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/AbstractResult.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,108 @@
+/*
+ *  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.ArrayList;
+import java.util.List;
+
+import org.apache.directory.mavibot.btree.Result;
+
+
+/**
+ * An abstract class to gather common elements of the Result classes
+ * 
+ * @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 */abstract class AbstractResult<K, V> implements Result<Page<K, V>>
+{
+    /** The list of copied page reference */
+    private List<Page<K, V>> copiedPage;
+
+
+    /**
+     * The default constructor for AbstractResult.
+     * 
+     */
+    /* No qualifier */AbstractResult()
+    {
+        copiedPage = new ArrayList<Page<K, V>>();
+    }
+
+
+    /**
+     * Creates an instance of AbstractResult with an initialized list of copied pages.
+     * 
+     * @param copiedPages The list of copied pages to store in this result
+     */
+    /* No qualifier */AbstractResult( List<Page<K, V>> copiedPages )
+    {
+        this.copiedPage = copiedPages;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public List<Page<K, V>> getCopiedPages()
+    {
+        return copiedPage;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void addCopiedPage( Page<K, V> page )
+    {
+        copiedPage.add( page );
+    }
+
+
+    public String toString()
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( "\n    copiedPage = <" );
+
+        boolean isFirst = true;
+
+        for ( Page<K, V> copiedPage : getCopiedPages() )
+        {
+            if ( isFirst )
+            {
+                isFirst = false;
+            }
+            else
+            {
+                sb.append( ", " );
+            }
+
+            sb.append( copiedPage.getOffset() );
+        }
+
+        sb.append( ">" );
+
+        return sb.toString();
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,1411 @@
+/*
+ *  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.Closeable;
+import java.io.IOException;
+import java.lang.reflect.ParameterizedType;
+import java.lang.reflect.Type;
+import java.nio.ByteBuffer;
+import java.nio.channels.FileChannel;
+import java.util.Comparator;
+import java.util.LinkedList;
+import java.util.concurrent.ConcurrentLinkedQueue;
+import java.util.concurrent.locks.ReentrantLock;
+
+import net.sf.ehcache.Cache;
+import net.sf.ehcache.config.CacheConfiguration;
+
+import org.apache.directory.mavibot.btree.BTreeHeader;
+import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
+import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+
+/**
+ * The B+Tree MVCC data structure.
+ * 
+ * @param <K> The type for the keys
+ * @param <V> The type for the stored values
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class BTree<K, V> implements Closeable
+{
+    /** The LoggerFactory used by this class */
+    protected static final Logger LOG = LoggerFactory.getLogger( BTree.class );
+
+    /** The Header for a managed BTree */
+    private BTreeHeader btreeHeader;
+
+    /** Default page size (number of entries per node) */
+    public static final int DEFAULT_PAGE_SIZE = 16;
+
+    /** Default size of the buffer used to write data on disk. Around 1Mb */
+    public static final int DEFAULT_WRITE_BUFFER_SIZE = 4096 * 250;
+
+    /** The default journal name */
+    public static final String DEFAULT_JOURNAL = "mavibot.log";
+
+    /** The default data file suffix */
+    public static final String DATA_SUFFIX = ".db";
+
+    /** The default journal file suffix */
+    public static final String JOURNAL_SUFFIX = ".log";
+
+    /** Comparator used to index entries. */
+    private Comparator<K> comparator;
+
+    /** The current rootPage */
+    protected volatile Page<K, V> rootPage;
+
+    /** The list of read transactions being executed */
+    private ConcurrentLinkedQueue<Transaction<K, V>> readTransactions;
+
+    /** The size of the buffer used to write data in disk */
+    private int writeBufferSize;
+
+    /** The type to use to create the keys */
+    protected Class<?> keyType;
+
+    /** The Key serializer used for this tree.*/
+    private ElementSerializer<K> keySerializer;
+
+    /** The Value serializer used for this tree. */
+    private ElementSerializer<V> valueSerializer;
+
+    /** The associated file. If null, this is an in-memory btree  */
+    //private File file;
+
+    /** The RecordManager if the BTree is managed */
+    private RecordManager recordManager;
+
+    /** A lock used to protect the write operation against concurrent access */
+    private ReentrantLock writeLock;
+
+    /** The thread responsible for the cleanup of timed out reads */
+    private Thread readTransactionsThread;
+
+    /** Define a default delay for a read transaction. This is 10 seconds */
+    public static final long DEFAULT_READ_TIMEOUT = 10 * 1000L;
+
+    /** The read transaction timeout */
+    private long readTimeOut = DEFAULT_READ_TIMEOUT;
+
+    /** The cache associated with this BTree */
+    private Cache cache;
+
+    /** The cache size, default to 1000 elements */
+    private int cacheSize = DEFAULT_CACHE_SIZE;
+
+    /** The default number of pages to keep in memory */
+    private static final int DEFAULT_CACHE_SIZE = 1000;
+
+
+    /**
+     * Create a thread that is responsible of cleaning the transactions when
+     * they hit the timeout
+     */
+    private void createTransactionManager()
+    {
+        Runnable readTransactionTask = new Runnable()
+        {
+            public void run()
+            {
+                try
+                {
+                    Transaction<K, V> transaction = null;
+
+                    while ( !Thread.currentThread().isInterrupted() )
+                    {
+                        long timeoutDate = System.currentTimeMillis() - readTimeOut;
+                        long t0 = System.currentTimeMillis();
+                        int nbTxns = 0;
+
+                        // Loop on all the transactions from the queue
+                        while ( ( transaction = readTransactions.peek() ) != null )
+                        {
+                            nbTxns++;
+
+                            if ( transaction.isClosed() )
+                            {
+                                // The transaction is already closed, remove it from the queue
+                                readTransactions.poll();
+                                continue;
+                            }
+
+                            // Check if the transaction has timed out
+                            if ( transaction.getCreationDate() < timeoutDate )
+                            {
+                                transaction.close();
+                                readTransactions.poll();
+                                continue;
+                            }
+
+                            // We need to stop now
+                            break;
+                        }
+
+                        long t1 = System.currentTimeMillis();
+
+                        if ( nbTxns > 0 )
+                        {
+                            System.out.println( "Processing old txn : " + nbTxns + ", " + ( t1 - t0 ) + "ms" );
+                        }
+
+                        // Wait until we reach the timeout
+                        Thread.sleep( readTimeOut );
+                    }
+                }
+                catch ( InterruptedException ie )
+                {
+                    //System.out.println( "Interrupted" );
+                }
+                catch ( Exception e )
+                {
+                    throw new RuntimeException( e );
+                }
+            }
+        };
+
+        readTransactionsThread = new Thread( readTransactionTask );
+        readTransactionsThread.setDaemon( true );
+        readTransactionsThread.start();
+    }
+
+
+    /**
+     * Creates a new BTree, with no initialization. 
+     */
+    public BTree()
+    {
+        btreeHeader = new BTreeHeader();
+    }
+
+
+    /**
+     * Creates a new in-memory BTree using the BTreeConfiguration to initialize the 
+     * BTree
+     * 
+     * @param comparator The comparator to use
+     */
+    public BTree( BTreeConfiguration<K, V> configuration ) throws IOException
+    {
+        String name = configuration.getName();
+
+        if ( name == null )
+        {
+            throw new IllegalArgumentException( "BTree name cannot be null" );
+        }
+
+        btreeHeader = new BTreeHeader();
+        btreeHeader.setName( name );
+        btreeHeader.setPageSize( configuration.getPageSize() );
+
+        keySerializer = configuration.getKeySerializer();
+        btreeHeader.setKeySerializerFQCN( keySerializer.getClass().getName() );
+
+        valueSerializer = configuration.getValueSerializer();
+        btreeHeader.setValueSerializerFQCN( valueSerializer.getClass().getName() );
+
+        comparator = keySerializer.getComparator();
+        readTimeOut = configuration.getReadTimeOut();
+        writeBufferSize = configuration.getWriteBufferSize();
+        btreeHeader.setAllowDuplicates( configuration.isAllowDuplicates() );
+        cacheSize = configuration.getCacheSize();
+
+        if ( comparator == null )
+        {
+            throw new IllegalArgumentException( "Comparator should not be null" );
+        }
+
+        // Create the first root page, with revision 0L. It will be empty
+        // and increment the revision at the same time
+        rootPage = new Leaf<K, V>( this );
+
+        // Now, initialize the BTree
+        init();
+    }
+
+
+    /**
+     * Creates a new in-memory BTree with a default page size and key/value serializers.
+     * 
+     * @param comparator The comparator to use
+     */
+    public BTree( String name, ElementSerializer<K> keySerializer, ElementSerializer<V> valueSerializer )
+        throws IOException
+    {
+        this( name, keySerializer, valueSerializer, false );
+    }
+
+
+    public BTree( String name, ElementSerializer<K> keySerializer, ElementSerializer<V> valueSerializer,
+        boolean allowDuplicates )
+        throws IOException
+    {
+        this( name, null, keySerializer, valueSerializer, DEFAULT_PAGE_SIZE, allowDuplicates, DEFAULT_CACHE_SIZE );
+    }
+
+
+    /**
+     * Creates a new in-memory BTree with a default page size and key/value serializers.
+     * 
+     * @param comparator The comparator to use
+     */
+    public BTree( String name, ElementSerializer<K> keySerializer, ElementSerializer<V> valueSerializer, int pageSize )
+        throws IOException
+    {
+        this( name, null, keySerializer, valueSerializer, pageSize );
+    }
+
+
+    /**
+     * Creates a new BTree with a default page size and a comparator, with an associated file.
+     * @param comparator The comparator to use
+     * @param serializer The serializer to use
+     */
+    public BTree( String name, String path, ElementSerializer<K> keySerializer, ElementSerializer<V> valueSerializer )
+        throws IOException
+    {
+        this( name, path, keySerializer, valueSerializer, DEFAULT_PAGE_SIZE );
+    }
+
+
+    /**
+     * 
+     * Creates a new instance of BTree with the given name and store it under the given dataDir if provided.
+     *
+     * @param name the name of the BTree
+     * @param dataDir the name of the data directory with absolute path
+     * @param keySerializer key serializer
+     * @param valueSerializer value serializer
+     * @param pageSize size of the page
+     * @throws IOException
+     */
+    public BTree( String name, String dataDir, ElementSerializer<K> keySerializer,
+        ElementSerializer<V> valueSerializer,
+        int pageSize )
+        throws IOException
+    {
+        this( name, dataDir, keySerializer, valueSerializer, pageSize, false, DEFAULT_CACHE_SIZE );
+    }
+
+
+    public BTree( String name, String dataDir, ElementSerializer<K> keySerializer,
+        ElementSerializer<V> valueSerializer,
+        int pageSize, boolean allowDuplicates )
+        throws IOException
+    {
+        this( name, dataDir, keySerializer, valueSerializer, pageSize, allowDuplicates, DEFAULT_CACHE_SIZE );
+    }
+
+
+    public BTree( String name, String dataDir, ElementSerializer<K> keySerializer,
+        ElementSerializer<V> valueSerializer,
+        int pageSize, boolean allowDuplicates, int cacheSize )
+        throws IOException
+    {
+        btreeHeader = new BTreeHeader();
+        btreeHeader.setName( name );
+
+        setPageSize( pageSize );
+        writeBufferSize = DEFAULT_WRITE_BUFFER_SIZE;
+
+        this.cacheSize = cacheSize;
+
+        this.keySerializer = keySerializer;
+
+        btreeHeader.setKeySerializerFQCN( keySerializer.getClass().getName() );
+
+        this.valueSerializer = valueSerializer;
+
+        btreeHeader.setValueSerializerFQCN( valueSerializer.getClass().getName() );
+
+        comparator = keySerializer.getComparator();
+
+        btreeHeader.setAllowDuplicates( allowDuplicates );
+
+        // Create the first root page, with revision 0L. It will be empty
+        // and increment the revision at the same time
+        rootPage = new Leaf<K, V>( this );
+
+        // Now, call the init() method
+        init();
+    }
+
+
+    /**
+     * Initialize the BTree.
+     * 
+     * @throws IOException If we get some exception while initializing the BTree
+     */
+    public void init() throws IOException
+    {
+        // Create the queue containing the pending read transactions
+        readTransactions = new ConcurrentLinkedQueue<Transaction<K, V>>();
+
+        // We will extract the Type to use for keys, using the comparator for that
+        Class<?> comparatorClass = comparator.getClass();
+        Type[] types = comparatorClass.getGenericInterfaces();
+
+        if ( types[0] instanceof Class )
+        {
+            keyType = ( Class<?> ) types[0];
+        }
+        else
+        {
+            Type[] argumentTypes = ( ( ParameterizedType ) types[0] ).getActualTypeArguments();
+
+            if ( ( argumentTypes != null ) && ( argumentTypes.length > 0 ) && ( argumentTypes[0] instanceof Class<?> ) )
+            {
+                keyType = ( Class<?> ) argumentTypes[0];
+            }
+        }
+
+        writeLock = new ReentrantLock();
+
+        // Initialize the caches
+        CacheConfiguration cacheConfiguration = new CacheConfiguration();
+        cacheConfiguration.setName( "pages" );
+        cacheConfiguration.setEternal( true );
+        cacheConfiguration.setOverflowToDisk( false );
+        cacheConfiguration.setCacheLoaderTimeoutMillis( 0 );
+        cacheConfiguration.setMaxElementsInMemory( cacheSize );
+        cacheConfiguration.setMemoryStoreEvictionPolicy( "LRU" );
+
+        cache = new Cache( cacheConfiguration );
+        cache.initialise();
+
+        // Initialize the txnManager thread
+        //FIXME we should NOT create a new transaction manager thread for each BTree
+        //createTransactionManager();
+    }
+
+
+    /**
+     * Return the cache we use in this BTree
+     */
+    /* No qualifier */Cache getCache()
+    {
+        return cache;
+    }
+
+
+    /**
+     * Close the BTree, cleaning up all the data structure
+     */
+    public void close() throws IOException
+    {
+        // Stop the readTransaction thread
+        // readTransactionsThread.interrupt();
+        // readTransactions.clear();
+
+        rootPage = null;
+    }
+
+
+    /**
+     * @return the btreeOffset
+     */
+    /* No qualifier*/long getBtreeOffset()
+    {
+        return btreeHeader.getBTreeOffset();
+    }
+
+
+    /**
+     * @param btreeOffset the btreeOffset to set
+     */
+    /* No qualifier*/void setBtreeOffset( long btreeOffset )
+    {
+        btreeHeader.setBTreeOffset( btreeOffset );
+    }
+
+
+    /**
+     * @return the rootPageOffset
+     */
+    /* No qualifier*/long getRootPageOffset()
+    {
+        return btreeHeader.getRootPageOffset();
+    }
+
+
+    /**
+     * @param rootPageOffset the rootPageOffset to set
+     */
+    /* No qualifier*/void setRootPageOffset( long rootPageOffset )
+    {
+        btreeHeader.setRootPageOffset( rootPageOffset );
+    }
+
+
+    /**
+     * @return the nextBTreeOffset
+     */
+    /* No qualifier*/long getNextBTreeOffset()
+    {
+        return btreeHeader.getNextBTreeOffset();
+    }
+
+
+    /**
+     * @param nextBTreeOffset the nextBTreeOffset to set
+     */
+    /* No qualifier*/void setNextBTreeOffset( long nextBTreeOffset )
+    {
+        btreeHeader.setNextBTreeOffset( nextBTreeOffset );
+    }
+
+
+    /**
+     * Gets the number which is a power of 2 immediately above the given positive number.
+     */
+    private int getPowerOf2( int size )
+    {
+        int newSize = --size;
+        newSize |= newSize >> 1;
+        newSize |= newSize >> 2;
+        newSize |= newSize >> 4;
+        newSize |= newSize >> 8;
+        newSize |= newSize >> 16;
+        newSize++;
+
+        return newSize;
+    }
+
+
+    /**
+     * Set the maximum number of elements we can store in a page. This must be a
+     * number greater than 1, and a power of 2. The default page size is 16.
+     * <br/>
+     * If the provided size is below 2, we will default to DEFAULT_PAGE_SIZE.<br/>
+     * If the provided size is not a power of 2, we will select the closest power of 2
+     * higher than the given number<br/>
+     * 
+     * @param pageSize The requested page size
+     */
+    public void setPageSize( int pageSize )
+    {
+        if ( pageSize <= 2 )
+        {
+            btreeHeader.setPageSize( DEFAULT_PAGE_SIZE );
+        }
+        else
+        {
+            btreeHeader.setPageSize( getPowerOf2( pageSize ) );
+        }
+    }
+
+
+    /**
+     * Set the new root page for this tree. Used for debug purpose only. The revision
+     * will always be 0;
+     * 
+     * @param root the new root page.
+     */
+    /* No qualifier */void setRoot( Page<K, V> root )
+    {
+        rootPage = root;
+    }
+
+
+    /**
+     * Gets the RecordManager for a managed BTree
+     * 
+     * @return The recordManager if the BTree is managed
+     */
+    /* No qualifier */RecordManager getRecordManager()
+    {
+        return recordManager;
+    }
+
+
+    /**
+     * Inject a RecordManager for a managed BTree
+     * 
+     * @param recordManager The injected RecordManager
+     */
+    /* No qualifier */void setRecordManager( RecordManager recordManager )
+    {
+        this.recordManager = recordManager;
+    }
+
+
+    /**
+     * @return the pageSize
+     */
+    public int getPageSize()
+    {
+        return btreeHeader.getPageSize();
+    }
+
+
+    /**
+     * Generates a new revision number. It's only used by the Page instances.
+     * 
+     * @return a new incremental revision number
+     */
+    /** No qualifier */
+    long generateRevision()
+    {
+        return btreeHeader.incrementRevision();
+    }
+
+
+    /**
+     * Insert an entry in the BTree.
+     * <p>
+     * We will replace the value if the provided key already exists in the
+     * btree.
+     *
+     * @param key Inserted key
+     * @param value Inserted value
+     * @return Existing value, if any.
+     * @throws IOException TODO
+     */
+    public V insert( K key, V value ) throws IOException
+    {
+        long revision = generateRevision();
+
+        V existingValue = null;
+
+        try
+        {
+            // Commented atm, we will have to play around the idea of transactions later
+            writeLock.lock();
+
+            InsertResult<K, V> result = insert( key, value, revision );
+
+            if ( result instanceof ModifyResult )
+            {
+                existingValue = ( ( ModifyResult<K, V> ) result ).getModifiedValue();
+            }
+        }
+        finally
+        {
+            // See above
+            writeLock.unlock();
+        }
+
+        return existingValue;
+    }
+
+
+    /**
+     * Delete the entry which key is given as a parameter. If the entry exists, it will
+     * be removed from the tree, the old tuple will be returned. Otherwise, null is returned.
+     * 
+     * @param key The key for the entry we try to remove
+     * @return A Tuple<K, V> containing the removed entry, or null if it's not found.
+     */
+    public Tuple<K, V> delete( K key ) throws IOException
+    {
+        if ( key == null )
+        {
+            throw new IllegalArgumentException( "Key must not be null" );
+        }
+
+        long revision = generateRevision();
+
+        Tuple<K, V> deleted = delete( key, revision );
+
+        return deleted;
+    }
+
+
+    /**
+     * Delete the value from an entry associated with the given key. If the value
+     * If the value is present, it will be deleted first, later if there are no other 
+     * values associated with this key(which can happen when duplicates are enabled), 
+     * we will remove the key from the tree.
+     * 
+     * @param key The key for the entry we try to remove
+     * @param value The value to delete (can be null)
+     * @return A Tuple<K, V> containing the removed entry, or null if it's not found.
+     */
+    public Tuple<K, V> delete( K key, V value ) throws IOException
+    {
+        if ( key == null )
+        {
+            throw new IllegalArgumentException( "Key must not be null" );
+        }
+
+        if ( value == null )
+        {
+            throw new IllegalArgumentException( "Value must not be null" );
+        }
+
+        long revision = generateRevision();
+
+        Tuple<K, V> deleted = delete( key, value, revision );
+
+        return deleted;
+    }
+
+
+    /**
+     * Delete the entry which key is given as a parameter. If the entry exists, it will
+     * be removed from the tree, the old tuple will be returned. Otherwise, null is returned.
+     * 
+     * @param key The key for the entry we try to remove
+     * @return A Tuple<K, V> containing the removed entry, or null if it's not found.
+     */
+    private Tuple<K, V> delete( K key, long revision ) throws IOException
+    {
+        return delete( key, null, revision );
+    }
+
+
+    /**
+     * 
+     * Deletes the given <key,value> pair if both key and value match. If the given value is null
+     * and there is no null value associated with the given key then the entry with the given key
+     * will be removed.
+     *
+     * @param key The key to be removed 
+     * @param value The value to be removed (can be null, and when no null value exists the key will be removed irrespective of the value)
+     * @param revision The revision to be associated with this operation
+     * @return
+     * @throws IOException
+     */
+    private Tuple<K, V> delete( K key, V value, long revision ) throws IOException
+    {
+        writeLock.lock();
+
+        try
+        {
+            // If the key exists, the existing value will be replaced. We store it
+            // to return it to the caller.
+            Tuple<K, V> tuple = null;
+
+            // Try to delete the entry starting from the root page. Here, the root
+            // page may be either a Node or a Leaf
+            DeleteResult<K, V> result = rootPage.delete( revision, key, value, null, -1 );
+
+            if ( result instanceof NotPresentResult )
+            {
+                // Key not found.
+                return null;
+            }
+
+            // Keep the oldRootPage so that we can later access it
+            Page<K, V> oldRootPage = rootPage;
+
+            if ( result instanceof RemoveResult )
+            {
+                // The element was found, and removed
+                RemoveResult<K, V> removeResult = ( RemoveResult<K, V> ) result;
+
+                Page<K, V> modifiedPage = removeResult.getModifiedPage();
+
+                // Write the modified page on disk
+                // Note that we don't use the holder, the new root page will
+                // remain in memory.
+                ElementHolder<Page<K, V>, K, V> holder = recordManager.writePage( this, modifiedPage,
+                    revision );
+
+                // Store the offset on disk in the page in memory
+                ( ( AbstractPage<K, V> ) modifiedPage ).setOffset( ( ( CacheHolder<Page<K, V>, K, V> ) holder )
+                    .getOffset() );
+
+                // Store the last offset on disk in the page in memory
+                ( ( AbstractPage<K, V> ) modifiedPage )
+                    .setLastOffset( ( ( CacheHolder<Page<K, V>, K, V> ) holder )
+                        .getLastOffset() );
+
+                // This is a new root
+                rootPage = modifiedPage;
+                tuple = removeResult.getRemovedElement();
+            }
+
+            // Decrease the number of elements in the current tree if the deletion is successful
+            if ( tuple != null )
+            {
+                btreeHeader.decrementNbElems();
+
+                // We have to update the rootPage on disk
+                // Update the BTree header now
+                recordManager.updateBtreeHeader( this, ( ( AbstractPage<K, V> ) rootPage ).getOffset() );
+            }
+
+            recordManager.addFreePages( this, result.getCopiedPages() );
+
+            // Store the created rootPage into the revision BTree, this will be stored in RecordManager only if revisions are set to keep
+            recordManager.storeRootPage( this, rootPage );
+
+            // Return the value we have found if it was modified
+            return tuple;
+        }
+        finally
+        {
+            // See above
+            writeLock.unlock();
+        }
+    }
+
+
+    /**
+     * Find a value in the tree, given its key. If the key is not found,
+     * it will throw a KeyNotFoundException. <br/>
+     * Note that we can get a null value stored, or many values.
+     * 
+     * @param key The key we are looking at
+     * @return The found value, or null if the key is not present in the tree
+     * @throws KeyNotFoundException If the key is not found in the BTree
+     * @throws IOException TODO
+     */
+    public V get( K key ) throws IOException, KeyNotFoundException
+    {
+        return rootPage.get( key );
+    }
+
+
+    /**
+     * @see Page#getValues(Object)
+     */
+    public DuplicateKeyVal<V> getValues( K key ) throws IOException, KeyNotFoundException
+    {
+        return rootPage.getValues( key );
+    }
+
+
+    /**
+     * Find a value in the tree, given its key, at a specific revision. If the key is not found,
+     * it will throw a KeyNotFoundException. <br/>
+     * Note that we can get a null value stored, or many values.
+     * 
+     * @param revision The revision for which we want to find a key
+     * @param key The key we are looking at
+     * @return The found value, or null if the key is not present in the tree
+     * @throws KeyNotFoundException If the key is not found in the BTree
+     * @throws IOException If there was an issue while fetching data from the disk
+     */
+    public V get( long revision, K key ) throws IOException, KeyNotFoundException
+    {
+        // Fetch the root page for this revision
+        Page<K, V> revisionRootPage = getRootPage( revision );
+
+        return revisionRootPage.get( key );
+    }
+
+
+    /**
+     * Checks if the given key exists.
+     *  
+     * @param key The key we are looking at
+     * @return true if the key is present, false otherwise
+     * @throws IOException If we have an error while trying to access the page
+     */
+    public boolean hasKey( K key ) throws IOException
+    {
+        if ( key == null )
+        {
+            return false;
+        }
+
+        return rootPage.hasKey( key );
+    }
+
+
+    /**
+     * Checks if the given key exists for a given revision.
+     *  
+     * @param revision The revision for which we want to find a key
+     * @param key The key we are looking at
+     * @return true if the key is present, false otherwise
+     * @throws IOException If we have an error while trying to access the page
+     * @throws KeyNotFoundException If the key is not found in the BTree
+     */
+    public boolean hasKey( long revision, K key ) throws IOException, KeyNotFoundException
+    {
+        if ( key == null )
+        {
+            return false;
+        }
+
+        // Fetch the root page for this revision
+        Page<K, V> revisionRootPage = getRootPage( revision );
+
+        return revisionRootPage.hasKey( key );
+    }
+
+
+    /**
+     * Checks if the BTree contains the given key with the given value.
+     * 
+     * @param key The key we are looking for
+     * @param value The value associated with the given key
+     * @return true if the key and value are associated with each other, false otherwise
+     */
+    public boolean contains( K key, V value ) throws IOException
+    {
+        return rootPage.contains( key, value );
+    }
+
+
+    /**
+     * Checks if the BTree contains the given key with the given value for a given revision
+     * 
+     * @param revision The revision we would like to browse
+     * @param key The key we are looking for
+     * @param value The value associated with the given key
+     * @return true if the key and value are associated with each other, false otherwise
+     * @throws KeyNotFoundException If the key is not found in the BTree
+     */
+    public boolean contains( long revision, K key, V value ) throws IOException, KeyNotFoundException
+    {
+        // Fetch the root page for this revision
+        Page<K, V> revisionRootPage = getRootPage( revision );
+
+        return revisionRootPage.contains( key, value );
+    }
+
+
+    /**
+     * Creates a cursor starting at the beginning of the tree
+     * 
+     * @return A cursor on the btree
+     * @throws IOException
+     */
+    public CursorImpl<K, V> browse() throws IOException
+    {
+        Transaction<K, V> transaction = beginReadTransaction();
+
+        // Fetch the root page for this revision
+        LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
+
+        CursorImpl<K, V> cursor = rootPage.browse( transaction, stack );
+
+        return cursor;
+    }
+
+
+    /**
+     * Creates a cursor starting at the beginning of the tree, for a given revision
+     * 
+     * @param revision The revision we would like to browse
+     * @return A cursor on the btree
+     * @throws IOException If we had an issue while fetching data from the disk
+     * @throws KeyNotFoundException If the key is not found in the BTree
+     */
+    public CursorImpl<K, V> browse( long revision ) throws IOException, KeyNotFoundException
+    {
+        Transaction<K, V> transaction = beginReadTransaction();
+
+        // Fetch the root page for this revision
+        Page<K, V> revisionRootPage = getRootPage( revision );
+
+        // And get the cursor
+        LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
+        CursorImpl<K, V> cursor = revisionRootPage.browse( transaction, stack );
+
+        return cursor;
+    }
+
+
+    /**
+     * Creates a cursor starting on the given key
+     * 
+     * @param key The key which is the starting point. If the key is not found,
+     * then the cursor will always return null.
+     * @return A cursor on the btree
+     * @throws IOException
+     */
+    public CursorImpl<K, V> browseFrom( K key ) throws IOException
+    {
+        Transaction<K, V> transaction = beginReadTransaction();
+
+        // Fetch the root page for this revision
+        CursorImpl<K, V> cursor = rootPage.browse( key, transaction, new LinkedList<ParentPos<K, V>>() );
+
+        return cursor;
+    }
+
+
+    /**
+     * Creates a cursor starting on the given key at the given revision
+     * 
+     * @param The revision we are looking for
+     * @param key The key which is the starting point. If the key is not found,
+     * then the cursor will always return null.
+     * @return A cursor on the btree
+     * @throws IOException If wxe had an issue reading the BTree from disk
+     * @throws KeyNotFoundException  If we can't find a rootPage for this revision
+     */
+    public CursorImpl<K, V> browseFrom( long revision, K key ) throws IOException, KeyNotFoundException
+    {
+        Transaction<K, V> transaction = beginReadTransaction();
+
+        // Fetch the rootPage for this revision
+        Page<K, V> revisionRootPage = getRootPage( revision );
+
+        // And get the cursor
+        LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
+        CursorImpl<K, V> cursor = revisionRootPage.browse( key, transaction, stack );
+
+        return cursor;
+    }
+
+
+    /**
+     * Insert an entry in the BTree.
+     * <p>
+     * We will replace the value if the provided key already exists in the
+     * btree.
+     * <p>
+     * The revision number is the revision to use to insert the data.
+     *
+     * @param key Inserted key
+     * @param value Inserted value
+     * @param revision The revision to use
+     * @return an instance of the InsertResult.
+     */
+    /*No qualifier*/InsertResult<K, V> insert( K key, V value, long revision ) throws IOException
+    {
+        if ( key == null )
+        {
+            throw new IllegalArgumentException( "Key must not be null" );
+        }
+
+        // If the key exists, the existing value will be replaced. We store it
+        // to return it to the caller.
+        V modifiedValue = null;
+
+        // Try to insert the new value in the tree at the right place,
+        // starting from the root page. Here, the root page may be either
+        // a Node or a Leaf
+        InsertResult<K, V> result = rootPage.insert( revision, key, value );
+
+        if ( result instanceof ModifyResult )
+        {
+            ModifyResult<K, V> modifyResult = ( ( ModifyResult<K, V> ) result );
+
+            Page<K, V> modifiedPage = modifyResult.getModifiedPage();
+
+            // Write the modified page on disk
+            // Note that we don't use the holder, the new root page will
+            // remain in memory.
+            ElementHolder<Page<K, V>, K, V> holder = recordManager.writePage( this, modifiedPage,
+                revision );
+
+            // The root has just been modified, we haven't split it
+            // Get it and make it the current root page
+            rootPage = modifiedPage;
+
+            modifiedValue = modifyResult.getModifiedValue();
+        }
+        else
+        {
+            // We have split the old root, create a new one containing
+            // only the pivotal we got back
+            SplitResult<K, V> splitResult = ( ( SplitResult<K, V> ) result );
+
+            K pivot = splitResult.getPivot();
+            Page<K, V> leftPage = splitResult.getLeftPage();
+            Page<K, V> rightPage = splitResult.getRightPage();
+            Page<K, V> newRootPage = null;
+
+            // If the BTree is managed, we have to write the two pages that were created
+            // and to keep a track of the two offsets for the upper node
+            ElementHolder<Page<K, V>, K, V> holderLeft = recordManager.writePage( this,
+                leftPage, revision );
+
+            ElementHolder<Page<K, V>, K, V> holderRight = recordManager.writePage( this,
+                rightPage, revision );
+
+            // Create the new rootPage
+            newRootPage = new Node<K, V>( this, revision, pivot, holderLeft, holderRight );
+
+            // If the BTree is managed, we now have to write the page on disk
+            // and to add this page to the list of modified pages
+            ElementHolder<Page<K, V>, K, V> holder = recordManager
+                .writePage( this, newRootPage, revision );
+
+            rootPage = newRootPage;
+        }
+
+        // Increase the number of element in the current tree if the insertion is successful
+        // and does not replace an element
+        if ( modifiedValue == null )
+        {
+            btreeHeader.incrementNbElems();
+        }
+
+        // If the BTree is managed, we have to update the rootPage on disk
+        // Update the BTree header now
+        recordManager.updateBtreeHeader( this, ( ( AbstractPage<K, V> ) rootPage ).getOffset() );
+
+        // Moved the free pages into the list of free pages
+        recordManager.addFreePages( this, result.getCopiedPages() );
+
+        // Store the created rootPage into the revision BTree, this will be stored in RecordManager only if revisions are set to keep
+        recordManager.storeRootPage( this, rootPage );
+
+        // Return the value we have found if it was modified
+        return result;
+    }
+
+
+    /**
+     * Starts a Read Only transaction. If the transaction is not closed, it will be 
+     * automatically closed after the timeout
+     * @return The created transaction
+     */
+    private Transaction<K, V> beginReadTransaction()
+    {
+        Transaction<K, V> readTransaction = new Transaction<K, V>( rootPage, btreeHeader.getRevision() - 1,
+            System.currentTimeMillis() );
+
+        readTransactions.add( readTransaction );
+
+        return readTransaction;
+    }
+
+
+    /**
+     * @return the type for the keys
+     */
+    /* No qualifier*/Class<?> getKeyType()
+    {
+        return keyType;
+    }
+
+
+    /**
+     * @return the comparator
+     */
+    public Comparator<K> getComparator()
+    {
+        return comparator;
+    }
+
+
+    /**
+     * @param comparator the comparator to set
+     */
+    public void setComparator( Comparator<K> comparator )
+    {
+        this.comparator = comparator;
+    }
+
+
+    /**
+     * @param keySerializer the Key serializer to set
+     */
+    public void setKeySerializer( ElementSerializer<K> keySerializer )
+    {
+        this.keySerializer = keySerializer;
+        this.comparator = keySerializer.getComparator();
+        btreeHeader.setKeySerializerFQCN( keySerializer.getClass().getName() );
+    }
+
+
+    /**
+     * @param valueSerializer the Value serializer to set
+     */
+    public void setValueSerializer( ElementSerializer<V> valueSerializer )
+    {
+        this.valueSerializer = valueSerializer;
+        btreeHeader.setValueSerializerFQCN( valueSerializer.getClass().getName() );
+    }
+
+
+    /**
+     * Write the data in the ByteBuffer, and eventually on disk if needed.
+     * 
+     * @param channel The channel we want to write to
+     * @param bb The ByteBuffer we want to feed
+     * @param buffer The data to inject
+     * @throws IOException If the write failed
+     */
+    private void writeBuffer( FileChannel channel, ByteBuffer bb, byte[] buffer ) throws IOException
+    {
+        int size = buffer.length;
+        int pos = 0;
+
+        // Loop until we have written all the data
+        do
+        {
+            if ( bb.remaining() >= size )
+            {
+                // No flush, as the ByteBuffer is big enough
+                bb.put( buffer, pos, size );
+                size = 0;
+            }
+            else
+            {
+                // Flush the data on disk, reinitialize the ByteBuffer
+                int len = bb.remaining();
+                size -= len;
+                bb.put( buffer, pos, len );
+                pos += len;
+
+                bb.flip();
+
+                channel.write( bb );
+
+                bb.clear();
+            }
+        }
+        while ( size > 0 );
+    }
+
+
+    /**
+     * Get the rootPzge associated to a give revision.
+     * 
+     * @param revision The revision we are looking for
+     * @return The rootPage associated to this revision
+     * @throws IOException If we had an issue while accessing the underlying file
+     * @throws KeyNotFoundException If the revision does not exist for this Btree
+     */
+    private Page<K, V> getRootPage( long revision ) throws IOException, KeyNotFoundException
+    {
+        return recordManager.getRootPage( this, revision );
+    }
+
+
+    /**
+     * Flush the latest revision to disk. We will replace the current file by the new one, as
+     * we flush in a temporary file.
+     */
+    public void flush() throws IOException
+    {
+    }
+
+
+    /**
+     * @return the readTimeOut
+     */
+    public long getReadTimeOut()
+    {
+        return readTimeOut;
+    }
+
+
+    /**
+     * @param readTimeOut the readTimeOut to set
+     */
+    public void setReadTimeOut( long readTimeOut )
+    {
+        this.readTimeOut = readTimeOut;
+    }
+
+
+    /**
+     * @return the name
+     */
+    public String getName()
+    {
+        return btreeHeader.getName();
+    }
+
+
+    /**
+     * @param name the name to set
+     */
+    public void setName( String name )
+    {
+        btreeHeader.setName( name );
+    }
+
+
+    /**
+     * @return the writeBufferSize
+     */
+    public int getWriteBufferSize()
+    {
+        return writeBufferSize;
+    }
+
+
+    /**
+     * @param writeBufferSize the writeBufferSize to set
+     */
+    public void setWriteBufferSize( int writeBufferSize )
+    {
+        this.writeBufferSize = writeBufferSize;
+    }
+
+
+    /**
+     * Create a ValueHolder depending on the kind of holder we want.
+     * 
+     * @param value The value to store
+     * @return The value holder
+     */
+    /* no qualifier */ElementHolder<V, K, V> createValueHolder( V value )
+    {
+        if ( isAllowDuplicates() )
+        {
+            return new MultipleMemoryHolder<K, V>( this, value );
+        }
+        else
+        {
+            // Atm, keep the values in memory
+            return new MemoryHolder<K, V>( this, value );
+        }
+    }
+
+
+    /**
+     * Create a ValueHolder depending on the kind of holder we want.
+     * 
+     * @param value The value to store
+     * @return The value holder
+     */
+    /* no qualifier */ElementHolder<Page<K, V>, K, V> createPageHolder( Page<K, V> value )
+    {
+        return new CacheHolder<Page<K, V>, K, V>( this, value,
+            value.getOffset(), value.getLastOffset() );
+    }
+
+
+    /**
+     * @return the keySerializer
+     */
+    public ElementSerializer<K> getKeySerializer()
+    {
+        return keySerializer;
+    }
+
+
+    /**
+     * @return the keySerializer FQCN
+     */
+    public String getKeySerializerFQCN()
+    {
+        return btreeHeader.getKeySerializerFQCN();
+    }
+
+
+    /**
+     * @return the valueSerializer
+     */
+    public ElementSerializer<V> getValueSerializer()
+    {
+        return valueSerializer;
+    }
+
+
+    /**
+     * @return the valueSerializer FQCN
+     */
+    public String getValueSerializerFQCN()
+    {
+        return btreeHeader.getValueSerializerFQCN();
+    }
+
+
+    /** 
+     * @return The current BTree revision
+     */
+    public long getRevision()
+    {
+        return btreeHeader.getRevision();
+    }
+
+
+    /**
+     * @param revision the revision to set
+     */
+    /* No qualifier */void setRevision( long revision )
+    {
+        btreeHeader.setRevision( revision );
+    }
+
+
+    /** 
+     * @return The current number of elements in the BTree
+     */
+    public long getNbElems()
+    {
+        return btreeHeader.getNbElems();
+    }
+
+
+    /**
+     * @param nbElems the nbElems to set
+     */
+    /* No qualifier */void setNbElems( long nbElems )
+    {
+        btreeHeader.setNbElems( nbElems );
+    }
+
+
+    /**
+     * @return true if this BTree allow duplicate values
+     */
+    public boolean isAllowDuplicates()
+    {
+        return btreeHeader.isAllowDuplicates();
+    }
+
+
+    /* No qualifier */void setAllowDuplicates( boolean allowDuplicates )
+    {
+        btreeHeader.setAllowDuplicates( allowDuplicates );
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( "Managed BTree" );
+        sb.append( "[" ).append( btreeHeader.getName() ).append( "]" );
+        sb.append( "( pageSize:" ).append( btreeHeader.getPageSize() );
+
+        if ( rootPage != null )
+        {
+            sb.append( ", nbEntries:" ).append( btreeHeader.getNbElems() );
+        }
+        else
+        {
+            sb.append( ", nbEntries:" ).append( 0 );
+        }
+
+        sb.append( ", comparator:" );
+
+        if ( comparator == null )
+        {
+            sb.append( "null" );
+        }
+        else
+        {
+            sb.append( comparator.getClass().getSimpleName() );
+        }
+
+        sb.append( ", DuplicatesAllowed: " ).append( btreeHeader.isAllowDuplicates() );
+
+        sb.append( ") : \n" );
+        sb.append( rootPage.dumpPage( "" ) );
+
+        return sb.toString();
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeBuilder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeBuilder.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeBuilder.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeBuilder.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,192 @@
+/*
+ *   Licensed to the Apache Software Foundation (ASF) under one
+ *   or more contributor license agreements.  See the NOTICE file
+ *   distributed with this work for additional information
+ *   regarding copyright ownership.  The ASF licenses this file
+ *   to you under the Apache License, Version 2.0 (the
+ *   "License"); you may not use this file except in compliance
+ *   with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *   Unless required by applicable law or agreed to in writing,
+ *   software distributed under the License is distributed on an
+ *   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *   KIND, either express or implied.  See the License for the
+ *   specific language governing permissions and limitations
+ *   under the License.
+ *
+ */
+
+package org.apache.directory.mavibot.btree.managed;
+
+
+import org.apache.directory.mavibot.btree.Tuple;
+import static org.apache.directory.mavibot.btree.managed.BTreeFactory.createLeaf;
+import static org.apache.directory.mavibot.btree.managed.BTreeFactory.createNode;
+import static org.apache.directory.mavibot.btree.managed.BTreeFactory.setKey;
+import static org.apache.directory.mavibot.btree.managed.BTreeFactory.setValue;
+
+import java.io.IOException;
+import java.lang.reflect.Array;
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
+
+
+/**
+ * A BTree builder that builds a tree from the bottom.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class BTreeBuilder<K, V>
+{
+    private String name;
+
+    private int numKeysInNode;
+
+    private ElementSerializer<K> keySerializer;
+
+    private ElementSerializer<V> valueSerializer;
+
+
+    public BTreeBuilder( String name, int numKeysInNode, ElementSerializer<K> keySerializer,
+        ElementSerializer<V> valueSerializer )
+    {
+        this.name = name;
+        this.numKeysInNode = numKeysInNode;
+        this.keySerializer = keySerializer;
+        this.valueSerializer = valueSerializer;
+    }
+
+
+    @SuppressWarnings("unchecked")
+    public BTree<K, V> build( Iterator<Tuple<K, V>> sortedTupleItr ) throws IOException
+    {
+        BTree<K, V> btree = new BTree<K, V>( name, keySerializer, valueSerializer );
+        btree.init();
+
+        List<Page<K, V>> lstLeaves = new ArrayList<Page<K, V>>();
+
+        int totalTupleCount = 0;
+
+        Leaf<K, V> leaf1 = createLeaf( btree, 0, numKeysInNode );
+        lstLeaves.add( leaf1 );
+
+        int leafIndex = 0;
+        while ( sortedTupleItr.hasNext() )
+        {
+            Tuple<K, V> tuple = sortedTupleItr.next();
+
+            setKey( leaf1, leafIndex, tuple.getKey() );
+
+            MemoryHolder<K, V> eh = new MemoryHolder<K, V>( btree, tuple.getValue() );
+
+            setValue( leaf1, leafIndex, eh );
+
+            leafIndex++;
+            totalTupleCount++;
+            if ( ( totalTupleCount % numKeysInNode ) == 0 )
+            {
+                leafIndex = 0;
+                leaf1 = createLeaf( btree, 0, numKeysInNode );
+                lstLeaves.add( leaf1 );
+            }
+        }
+
+        if ( lstLeaves.isEmpty() )
+        {
+            return btree;
+        }
+
+        // remove null keys and values from the last leaf and resize
+        Leaf<K, V> lastLeaf = ( Leaf<K, V> ) lstLeaves.get( lstLeaves.size() - 1 );
+        for ( int i = 0; i < lastLeaf.nbElems; i++ )
+        {
+            if ( lastLeaf.keys[i] == null )
+            {
+                int n = i;
+                lastLeaf.nbElems = n;
+                K[] keys = lastLeaf.keys;
+
+                Class<?> keyType = btree.getKeyType();
+                lastLeaf.keys = ( K[] ) Array.newInstance( keyType, n );
+                System.arraycopy( keys, 0, lastLeaf.keys, 0, n );
+
+                ElementHolder<V, K, V>[] values = lastLeaf.values;
+                lastLeaf.values = ( MemoryHolder<K, V>[] ) Array.newInstance( MemoryHolder.class, n );
+                System.arraycopy( values, 0, lastLeaf.values, 0, n );
+
+                break;
+            }
+        }
+
+        Page<K, V> rootPage = attachNodes( lstLeaves, btree );
+
+        btree.rootPage = rootPage;
+
+        return btree;
+    }
+
+
+    @SuppressWarnings("unchecked")
+    private Page<K, V> attachNodes( List<Page<K, V>> children, BTree<K, V> btree ) throws IOException
+    {
+        if ( children.size() == 1 )
+        {
+            return children.get( 0 );
+        }
+
+        List<Page<K, V>> lstNodes = new ArrayList<Page<K, V>>();
+
+        int numChildren = numKeysInNode + 1;
+
+        Node<K, V> node = createNode( btree, 0, numKeysInNode );
+        lstNodes.add( node );
+        int i = 0;
+        int totalNodes = 0;
+
+        for ( Page<K, V> p : children )
+        {
+            if ( i != 0 )
+            {
+                setKey( node, i - 1, p.getLeftMostKey() );
+            }
+
+            node.children[i] = btree.createPageHolder( p );
+
+            i++;
+            totalNodes++;
+
+            if ( ( totalNodes % numChildren ) == 0 )
+            {
+                i = 0;
+                node = createNode( btree, 0, numKeysInNode );
+                lstNodes.add( node );
+            }
+        }
+
+        // remove null keys and values from the last node and resize
+        AbstractPage<K, V> lastNode = ( AbstractPage<K, V> ) lstNodes.get( lstNodes.size() - 1 );
+
+        for ( int j = 0; j < lastNode.nbElems; j++ )
+        {
+            if ( lastNode.keys[j] == null )
+            {
+                int n = j;
+                lastNode.nbElems = n;
+                K[] keys = lastNode.keys;
+
+                Class<?> keyType = btree.getKeyType();
+                lastNode.keys = ( K[] ) Array.newInstance( keyType, n );
+                System.arraycopy( keys, 0, lastNode.keys, 0, n );
+
+                break;
+            }
+        }
+
+        return attachNodes( lstNodes, btree );
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeConfiguration.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeConfiguration.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeConfiguration.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeConfiguration.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,320 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.managed;
+
+
+import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
+
+
+/**
+ * The B+Tree Configuration. This class can be used to store all the configurable
+ * parameters used by the BTree class
+ * 
+ * @param <K> The type for the keys
+ * @param <V> The type for the stored values
+ * 
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class BTreeConfiguration<K, V>
+{
+    /** Number of entries in each Page. */
+    private int pageSize = BTree.DEFAULT_PAGE_SIZE;
+
+    /** The size of the buffer used to write data in disk */
+    private int writeBufferSize = BTree.DEFAULT_WRITE_BUFFER_SIZE;
+
+    /** The Key and Value serializer used for this tree. If none is provided, 
+     * the BTree will deduce the serializer to use from the generic type, and
+     * use the default Java serialization  */
+    private ElementSerializer<K> keySerializer;
+    private ElementSerializer<V> valueSerializer;
+
+    /** The BTree name */
+    private String name;
+
+    /** The path where the BTree file will be stored. Default to the local 
+     * temporary directory.
+     */
+    private String filePath;
+
+    /** 
+     * The maximum delay to wait before a revision is considered as unused.
+     * This delay is necessary so that a read that does not ends does not 
+     * hold a revision in memory forever.
+     * The default value is 10000 (10 seconds). If the value is 0 or below,
+     * the delay is considered as infinite
+     */
+    private long readTimeOut = BTree.DEFAULT_READ_TIMEOUT;
+
+    /** The maximal size of the journal. When this size is reached, the tree is 
+     * flushed on disk.
+     * The default size is 10 Mb
+     */
+    private long journalSize = 10 * 1024 * 1024L;
+
+    /**
+     * The journal's name. Default to "mavibot.log".
+     */
+    private String journalName = BTree.DEFAULT_JOURNAL;
+
+    /** 
+     * The delay between two checkpoints. When we reach the maximum delay,
+     * the BTree is flushed on disk, but only if we have had some modifications.
+     * The default value is 60 seconds.
+     */
+    private long checkPointDelay = 60 * 1000L;
+
+    /** Flag to enable duplicate key support */
+    private boolean allowDuplicates;
+
+    /** The cache size */
+    private int cacheSize;
+
+
+    /**
+     * @return the pageSize
+     */
+    public int getPageSize()
+    {
+        return pageSize;
+    }
+
+
+    /**
+     * @param pageSize the pageSize to set
+     */
+    public void setPageSize( int pageSize )
+    {
+        this.pageSize = pageSize;
+    }
+
+
+    /**
+     * @return the key serializer
+     */
+    public ElementSerializer<K> getKeySerializer()
+    {
+        return keySerializer;
+    }
+
+
+    /**
+     * @return the value serializer
+     */
+    public ElementSerializer<V> getValueSerializer()
+    {
+        return valueSerializer;
+    }
+
+
+    /**
+     * @param keySerializer the key serializer to set
+     * @param valueSerializer the value serializer to set
+     */
+    public void setSerializers( ElementSerializer<K> keySerializer, ElementSerializer<V> valueSerializer )
+    {
+        this.keySerializer = keySerializer;
+        this.valueSerializer = valueSerializer;
+    }
+
+
+    /**
+     * @param serializer the key serializer to set
+     */
+    public void setKeySerializer( ElementSerializer<K> keySerializer )
+    {
+        this.keySerializer = keySerializer;
+    }
+
+
+    /**
+     * @param serializer the key serializer to set
+     */
+    public void setValueSerializer( ElementSerializer<V> valueSerializer )
+    {
+        this.valueSerializer = valueSerializer;
+    }
+
+
+    /**
+     * @return the readTimeOut
+     */
+    public long getReadTimeOut()
+    {
+        return readTimeOut;
+    }
+
+
+    /**
+     * @param readTimeOut the readTimeOut to set
+     */
+    public void setReadTimeOut( long readTimeOut )
+    {
+        this.readTimeOut = readTimeOut;
+    }
+
+
+    /**
+     * @return the journalSize
+     */
+    public long getJournalSize()
+    {
+        return journalSize;
+    }
+
+
+    /**
+     * @param journalSize the journalSize to set
+     */
+    public void setJournalSize( long journalSize )
+    {
+        this.journalSize = journalSize;
+    }
+
+
+    /**
+     * @return the checkPointDelay
+     */
+    public long getCheckPointDelay()
+    {
+        return checkPointDelay;
+    }
+
+
+    /**
+     * @param checkPointDelay the checkPointDelay to set
+     */
+    public void setCheckPointDelay( long checkPointDelay )
+    {
+        this.checkPointDelay = checkPointDelay;
+    }
+
+
+    /**
+     * @return the filePath
+     */
+    public String getFilePath()
+    {
+        return filePath;
+    }
+
+
+    /**
+     * @param filePath the filePath to set
+     */
+    public void setFilePath( String filePath )
+    {
+        this.filePath = filePath;
+    }
+
+
+    /**
+     * @return the journal name
+     */
+    public String getJournalName()
+    {
+        return journalName;
+    }
+
+
+    /**
+     * @param journalName the journal name to set
+     */
+    public void setJournalName( String journalName )
+    {
+        this.journalName = journalName;
+    }
+
+
+    /**
+     * @return the writeBufferSize
+     */
+    public int getWriteBufferSize()
+    {
+        return writeBufferSize;
+    }
+
+
+    /**
+     * @param writeBufferSize the writeBufferSize to set
+     */
+    public void setWriteBufferSize( int writeBufferSize )
+    {
+        this.writeBufferSize = writeBufferSize;
+    }
+
+
+    /**
+     * @return the name
+     */
+    public String getName()
+    {
+        return name;
+    }
+
+
+    /**
+     * @param name the name to set
+     */
+    public void setName( String name )
+    {
+        this.name = name.trim();
+    }
+
+
+    /**
+     * @return true if duplicate key support is enabled
+     */
+    public boolean isAllowDuplicates()
+    {
+        return allowDuplicates;
+    }
+
+
+    /**
+     * enable duplicate key support
+     * 
+     * @param allowDuplicates
+     * @throws IllegalStateException if the btree was already initialized or when tried to turn off duplicate suport on
+     *                               an existing btree containing duplicate keys
+     */
+    public void setAllowDuplicates( boolean allowDuplicates )
+    {
+        this.allowDuplicates = allowDuplicates;
+    }
+
+
+    /**
+     * @return the cacheSize
+     */
+    public int getCacheSize()
+    {
+        return cacheSize;
+    }
+
+
+    /**
+     * @param cacheSize the cacheSize to set
+     */
+    public void setCacheSize( int cacheSize )
+    {
+        this.cacheSize = cacheSize;
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeFactory.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeFactory.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeFactory.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTreeFactory.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,287 @@
+/*
+ *  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.util.LinkedList;
+
+import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
+
+
+/**
+ * This class construct a BTree from a serialized version of a BTree. We need it
+ * to avoid exposing all the methods of the BTree class.<br>
+ * 
+ * All its methods are static.
+ *  
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class BTreeFactory
+{
+    /**
+     * Create a new BTree.
+     * 
+     * @return The created BTree
+     */
+    public static <K, V> BTree<K, V> createBTree()
+    {
+        BTree<K, V> btree = new BTree<K, V>();
+
+        return btree;
+    }
+
+
+    /**
+     * Create a new Node for the give BTree.
+     * 
+     * @param btree The BTree which will contain this node
+     * @param revision The Node's revision
+     * @param nbElems The number or elements in this node
+     * @return A Node instance
+     */
+    public static <K, V> Node<K, V> createNode( BTree<K, V> btree, long revision, int nbElems )
+    {
+        Node<K, V> node = new Node<K, V>( btree, revision, nbElems );
+
+        return node;
+    }
+
+
+    /**
+     * Create a new Leaf for the give BTree.
+     * 
+     * @param btree The BTree which will contain this leaf
+     * @param revision The Leaf's revision
+     * @param nbElems The number or elements in this leaf
+     * @return A Leaf instance
+     */
+    public static <K, V> Leaf<K, V> createLeaf( BTree<K, V> btree, long revision, int nbElems )
+    {
+        Leaf<K, V> leaf = new Leaf<K, V>( btree, revision, nbElems );
+
+        return leaf;
+    }
+
+
+    /**
+     * Set the new root page for this tree. Used for debug purpose only. The revision
+     * will always be 0;
+     * 
+     * @param root the new root page.
+     */
+    public static <K, V> void setRoot( BTree<K, V> btree, Page<K, V> root )
+    {
+        btree.setRoot( root );
+    }
+
+
+    /**
+     * Return the BTree root page
+     * 
+     * @param btree The Btree we want to root page from
+     * @return The root page
+     */
+    public static <K, V> Page<K, V> getRoot( BTree<K, V> btree )
+    {
+        return btree.rootPage;
+    }
+
+
+    /**
+     * @param nbElems the nbElems to set
+     */
+    public static <K, V> void setNbElems( BTree<K, V> btree, long nbElems )
+    {
+        btree.setNbElems( nbElems );
+    }
+
+
+    /**
+     * @param revision the revision to set
+     */
+    public static <K, V> void setRevision( BTree<K, V> btree, long revision )
+    {
+        btree.setRevision( revision );
+    }
+
+
+    /**
+     * @param rootPageOffset the rootPageOffset to set
+     */
+    public static <K, V> void setRootPageOffset( BTree<K, V> btree, long rootPageOffset )
+    {
+        btree.setRootPageOffset( rootPageOffset );
+    }
+
+
+    /**
+     * @param nextBTreeOffset the nextBTreeOffset to set
+     */
+    public static <K, V> void setNextBTreeOffset( BTree<K, V> btree, long nextBTreeOffset )
+    {
+        btree.setNextBTreeOffset( nextBTreeOffset );
+    }
+
+
+    /**
+     * @param name the name to set
+     */
+    public static <K, V> void setName( BTree<K, V> btree, String name )
+    {
+        btree.setName( name );
+    }
+
+
+    /**
+     * Sets the KeySerializer into the BTree
+     *  
+     * @param btree The BTree to update
+     * @param keySerializerFqcn the Key serializer FQCN to set
+     * @throws ClassNotFoundException
+     * @throws InstantiationException 
+     * @throws IllegalAccessException
+     */
+    public static <K, V> void setKeySerializer( BTree<K, V> btree, String keySerializerFqcn )
+        throws ClassNotFoundException, IllegalAccessException, InstantiationException
+    {
+        Class<?> keySerializer = Class.forName( keySerializerFqcn );
+        @SuppressWarnings("unchecked")
+        ElementSerializer<K> instance = ( ElementSerializer<K> ) keySerializer.newInstance();
+        btree.setKeySerializer( instance );
+
+        btree.setComparator( instance.getComparator() );
+    }
+
+
+    /**
+     * Sets the ValueSerializer into the BTree
+     *  
+     * @param btree The BTree to update
+     * @param valueSerializerFqcn the Value serializer FQCN to set
+     * @throws ClassNotFoundException
+     * @throws InstantiationException 
+     * @throws IllegalAccessException
+     */
+    public static <K, V> void setValueSerializer( BTree<K, V> btree, String valueSerializerFqcn )
+        throws ClassNotFoundException, IllegalAccessException, InstantiationException
+    {
+        Class<?> valueSerializer = Class.forName( valueSerializerFqcn );
+        @SuppressWarnings("unchecked")
+        ElementSerializer<V> instance = ( ElementSerializer<V> ) valueSerializer.newInstance();
+        btree.setValueSerializer( instance );
+    }
+
+
+    /**
+     * Set the maximum number of elements we can store in a page.
+     * 
+     * @param pageSize The requested page size
+     */
+    public static <K, V> void setPageSize( BTree<K, V> btree, int pageSize )
+    {
+        btree.setPageSize( pageSize );
+    }
+
+
+    /**
+     * Set the RecordManager
+     * 
+     * @param recordManager The injected RecordManager
+     */
+    public static <K, V> void setRecordManager( BTree<K, V> btree, RecordManager recordManager )
+    {
+        btree.setRecordManager( recordManager );
+    }
+
+
+    /**
+     * Set the key at a give position
+     * @param pos The position in the keys array
+     * @param key the key to inject
+     */
+    public static <K, V> void setKey( Page<K, V> page, int pos, K key )
+    {
+        ( ( AbstractPage<K, V> ) page ).setKey( pos, key );
+    }
+
+
+    /**
+     * Set the value at a give position
+     * @param pos The position in the values array
+     * @param value the value to inject
+     */
+    public static <K, V> void setValue( Leaf<K, V> page, int pos, ElementHolder<V, K, V> value )
+    {
+        page.setValue( pos, value );
+    }
+
+
+    /**
+     * Set the value at a give position
+     * @param pos The position in the values array
+     * @param value the value to inject
+     */
+    public static <K, V> void setValue( Node<K, V> page, int pos, ElementHolder<Page<K, V>, K, V> value )
+    {
+        page.setValue( pos, value );
+    }
+
+
+    /**
+     * Includes the intermediate nodes in the path up to and including the right most leaf of the tree
+     * 
+     * @param btree the btree
+     * @return a LinkedList of all the nodes and the final leaf
+     * @throws IOException
+     */
+    public static <K, V> LinkedList<ParentPos<K, V>> getPathToRightMostLeaf( BTree<K, V> btree ) throws IOException
+    {
+        LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
+
+        ParentPos<K, V> last = new ParentPos<K, V>( btree.rootPage, btree.rootPage.getNbElems() );
+        stack.push( last );
+
+        if ( btree.rootPage instanceof Leaf )
+        {
+            InternalUtil.setLastDupsContainer( last, btree );
+        }
+        else
+        {
+            Node<K, V> node = ( Node<K, V> ) btree.rootPage;
+
+            while ( true )
+            {
+                Page<K, V> p = node.children[node.getNbElems()].getValue( btree );
+
+                last = new ParentPos<K, V>( p, p.getNbElems() );
+                stack.push( last );
+
+                if ( p instanceof Leaf )
+                {
+                    InternalUtil.setLastDupsContainer( last, btree );
+                    break;
+                }
+            }
+        }
+
+        return stack;
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BorrowedFromLeftResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BorrowedFromLeftResult.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BorrowedFromLeftResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BorrowedFromLeftResult.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,83 @@
+/*
+ *  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, 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:dev@directory.apache.org">Apache Directory 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/managed/BorrowedFromRightResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BorrowedFromRightResult.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BorrowedFromRightResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BorrowedFromRightResult.java Mon Sep 30 06:32:25 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.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 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();
+    }
+}



Mime
View raw message