You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by el...@apache.org on 2013/09/30 08:32:28 UTC
svn commit: r1527458 [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...
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();
+ }
+}