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 [8/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/memory/BTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTree.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTree.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTree.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,1753 @@
+/*
+ * 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.memory;
+
+
+import java.io.Closeable;
+import java.io.EOFException;
+import java.io.File;
+import java.io.FileOutputStream;
+import java.io.IOException;
+import java.io.RandomAccessFile;
+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.Addition;
+import org.apache.directory.mavibot.btree.BTreeHeader;
+import org.apache.directory.mavibot.btree.Cursor;
+import org.apache.directory.mavibot.btree.Deletion;
+import org.apache.directory.mavibot.btree.Modification;
+import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
+import org.apache.directory.mavibot.btree.serializer.BufferHandler;
+import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
+import org.apache.directory.mavibot.btree.serializer.LongSerializer;
+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 BTree type : either in-memory, persistent or managed */
+ private BTreeTypeEnum type;
+
+ /** A flag used to tell the BTree that the journal is activated */
+ private boolean withJournal;
+
+ /** The associated journal. If null, this is an in-memory btree */
+ private File journal;
+
+ /** 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;
+
+ private File envDir;
+
+ private FileChannel journalChannel = null;
+
+ /** 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();
+ type = BTreeTypeEnum.IN_MEMORY;
+ }
+
+
+ /**
+ * 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" );
+ }
+
+ String filePath = configuration.getFilePath();
+
+ if ( filePath != null )
+ {
+ envDir = new File( filePath );
+ }
+
+ 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() );
+ type = configuration.getType();
+ 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 );
+
+ if ( dataDir != null )
+ {
+ envDir = new File( dataDir );
+ }
+
+ 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
+ {
+ // if not in-memory then default to persist mode instead of managed
+ if ( envDir != null )
+ {
+ if ( !envDir.exists() )
+ {
+ boolean created = envDir.mkdirs();
+ if ( !created )
+ {
+ throw new IllegalStateException( "Could not create the directory " + envDir + " for storing data" );
+ }
+ }
+
+ this.file = new File( envDir, btreeHeader.getName() + DATA_SUFFIX );
+
+ this.journal = new File( envDir, file.getName() + JOURNAL_SUFFIX );
+ type = BTreeTypeEnum.PERSISTENT;
+ }
+
+ // 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();
+
+ // Check the files and create them if missing
+ // Create the queue containing the modifications, if it's not a in-memory btree
+ if ( type == BTreeTypeEnum.PERSISTENT )
+ {
+ if ( file.length() > 0 )
+ {
+ // We have some existing file, load it
+ load( file );
+ }
+
+ withJournal = true;
+
+ FileOutputStream stream = new FileOutputStream( journal );
+ journalChannel = stream.getChannel();
+
+ // If the journal is not empty, we have to read it
+ // and to apply all the modifications to the current file
+ if ( journal.length() > 0 )
+ {
+ applyJournal();
+ }
+ }
+ else if ( type == null )
+ {
+ type = BTreeTypeEnum.IN_MEMORY;
+ }
+
+ // 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();
+
+ if ( type == BTreeTypeEnum.PERSISTENT )
+ {
+ // Flush the data
+ flush();
+ journalChannel.close();
+ }
+
+ 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;
+ }
+
+
+ /**
+ * @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();
+
+ // This is a new root
+ rootPage = modifiedPage;
+ tuple = removeResult.getRemovedElement();
+ }
+
+ if ( withJournal )
+ {
+ // Inject the modification into the modification queue
+ writeToJournal( new Deletion<K, V>( key ) );
+ }
+
+ // Decrease the number of elements in the current tree if the deletion is successful
+ if ( tuple != null )
+ {
+ btreeHeader.decrementNbElems();
+ }
+
+ // 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 Cursor<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>>();
+
+ Cursor<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 Cursor<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>>();
+ Cursor<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 Cursor<K, V> browseFrom( K key ) throws IOException
+ {
+ Transaction<K, V> transaction = beginReadTransaction();
+
+ // Fetch the root page for this revision
+ Cursor<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 Cursor<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>>();
+ Cursor<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();
+
+ // 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;
+
+ // Create the new rootPage
+ newRootPage = new Node<K, V>( this, revision, pivot, leftPage, rightPage );
+
+ rootPage = newRootPage;
+ }
+
+ // Inject the modification into the modification queue
+ if ( withJournal )
+ {
+ writeToJournal( new Addition<K, V>( key, value ) );
+ }
+
+ // 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();
+ }
+
+ // 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 );
+ }
+
+
+ /**
+ * Flush the latest revision to disk
+ * @param file The file into which the data will be written
+ */
+ public void flush( File file ) throws IOException
+ {
+ File parentFile = file.getParentFile();
+ File baseDirectory = null;
+
+ if ( parentFile != null )
+ {
+ baseDirectory = new File( file.getParentFile().getAbsolutePath() );
+ }
+ else
+ {
+ baseDirectory = new File( "." );
+ }
+
+ // Create a temporary file in the same directory to flush the current btree
+ File tmpFileFD = File.createTempFile( "mavibot", null, baseDirectory );
+ FileOutputStream stream = new FileOutputStream( tmpFileFD );
+ FileChannel ch = stream.getChannel();
+
+ // Create a buffer containing 200 4Kb pages (around 1Mb)
+ ByteBuffer bb = ByteBuffer.allocateDirect( writeBufferSize );
+
+ Cursor<K, V> cursor = browse();
+
+ if ( keySerializer == null )
+ {
+ throw new RuntimeException( "Cannot flush the btree without a Key serializer" );
+ }
+
+ if ( valueSerializer == null )
+ {
+ throw new RuntimeException( "Cannot flush the btree without a Value serializer" );
+ }
+
+ // Write the number of elements first
+ bb.putLong( btreeHeader.getNbElems() );
+
+ while ( cursor.hasNext() )
+ {
+ Tuple<K, V> tuple = cursor.next();
+
+ byte[] keyBuffer = keySerializer.serialize( tuple.getKey() );
+
+ writeBuffer( ch, bb, keyBuffer );
+
+ byte[] valueBuffer = valueSerializer.serialize( tuple.getValue() );
+
+ writeBuffer( ch, bb, valueBuffer );
+ }
+
+ // Write the buffer if needed
+ if ( bb.position() > 0 )
+ {
+ bb.flip();
+ ch.write( bb );
+ }
+
+ // Flush to the disk for real
+ ch.force( true );
+ ch.close();
+
+ // Rename the current file to save a backup
+ File backupFile = File.createTempFile( "mavibot", null, baseDirectory );
+ file.renameTo( backupFile );
+
+ // Rename the temporary file to the initial file
+ tmpFileFD.renameTo( file );
+
+ // We can now delete the backup file
+ backupFile.delete();
+ }
+
+
+ /**
+ * Inject all the modification from the journal into the btree
+ *
+ * @throws IOException If we had some issue while reading the journal
+ */
+ private void applyJournal() throws IOException
+ {
+ long revision = generateRevision();
+
+ if ( !journal.exists() )
+ {
+ throw new IOException( "The journal does not exist" );
+ }
+
+ FileChannel channel =
+ new RandomAccessFile( journal, "rw" ).getChannel();
+ ByteBuffer buffer = ByteBuffer.allocate( 65536 );
+
+ BufferHandler bufferHandler = new BufferHandler( channel, buffer );
+
+ // Loop on all the elements, store them in lists atm
+ try
+ {
+ while ( true )
+ {
+ // Read the type
+ byte[] type = bufferHandler.read( 1 );
+
+ if ( type[0] == Modification.ADDITION )
+ {
+ // Read the key
+ K key = keySerializer.deserialize( bufferHandler );
+
+ //keys.add( key );
+
+ // Read the value
+ V value = valueSerializer.deserialize( bufferHandler );
+
+ //values.add( value );
+
+ // Inject the data in the tree. (to be replaced by a bulk load)
+ insert( key, value, revision );
+ }
+ else
+ {
+ // Read the key
+ K key = keySerializer.deserialize( bufferHandler );
+
+ // Remove the key from the tree
+ delete( key, revision );
+ }
+ }
+ }
+ catch ( EOFException eofe )
+ {
+ eofe.printStackTrace();
+ // Done reading the journal. truncate it
+ journalChannel.truncate( 0 );
+ }
+ }
+
+
+ /**
+ * Read the data from the disk into this BTree. All the existing data in the
+ * BTree are kept, the read data will be associated with a new revision.
+ *
+ * @param file
+ * @throws IOException
+ */
+ public void load( File file ) throws IOException
+ {
+ long revision = generateRevision();
+
+ if ( !file.exists() )
+ {
+ throw new IOException( "The file does not exist" );
+ }
+
+ FileChannel channel =
+ new RandomAccessFile( file, "rw" ).getChannel();
+ ByteBuffer buffer = ByteBuffer.allocate( 65536 );
+
+ BufferHandler bufferHandler = new BufferHandler( channel, buffer );
+
+ long nbElems = LongSerializer.deserialize( bufferHandler.read( 8 ) );
+ btreeHeader.setNbElems( nbElems );
+
+ // Prepare a list of keys and values read from the disk
+ //List<K> keys = new ArrayList<K>();
+ //List<V> values = new ArrayList<V>();
+
+ // desactivate the journal while we load the file
+ boolean isJournalActivated = withJournal;
+
+ withJournal = false;
+
+ // Loop on all the elements, store them in lists atm
+ for ( long i = 0; i < nbElems; i++ )
+ {
+ // Read the key
+ K key = keySerializer.deserialize( bufferHandler );
+
+ //keys.add( key );
+
+ // Read the value
+ V value = valueSerializer.deserialize( bufferHandler );
+
+ //values.add( value );
+
+ // Inject the data in the tree. (to be replaced by a bulk load)
+ insert( key, value, revision );
+ }
+
+ // Restore the withJournal value
+ withJournal = isJournalActivated;
+
+ // Now, process the lists to create the btree
+ // TODO... BulkLoad
+ }
+
+
+ /**
+ * 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
+ {
+ // Atm, the in-memory BTree does not support searches in many revisions
+ return rootPage;
+ }
+
+
+ /**
+ * 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
+ {
+ if ( type == BTreeTypeEnum.PERSISTENT )
+ {
+ // Then flush the file
+ flush( file );
+ journalChannel.truncate( 0 );
+ }
+ }
+
+
+ /**
+ * @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 file
+ */
+ public File getFile()
+ {
+ return file;
+ }
+
+
+ /**
+ * @return the journal
+ */
+ public File getJournal()
+ {
+ return journal;
+ }
+
+
+ /**
+ * @return the writeBufferSize
+ */
+ public int getWriteBufferSize()
+ {
+ return writeBufferSize;
+ }
+
+
+ /**
+ * @param writeBufferSize the writeBufferSize to set
+ */
+ public void setWriteBufferSize( int writeBufferSize )
+ {
+ this.writeBufferSize = writeBufferSize;
+ }
+
+
+ /**
+ * @return true if the BTree is fully in memory
+ */
+ public boolean isInMemory()
+ {
+ return type == BTreeTypeEnum.IN_MEMORY;
+ }
+
+
+ /**
+ * @return true if the BTree is persisted on disk
+ */
+ public boolean isPersistent()
+ {
+ return type == BTreeTypeEnum.IN_MEMORY;
+ }
+
+
+ /**
+ * 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
+ {
+ return new MemoryHolder( 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 MemoryHolder( this, value );
+ }
+
+
+ /**
+ * @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 );
+ }
+
+
+ private void writeToJournal( Modification<K, V> modification )
+ throws IOException
+ {
+ if ( modification instanceof Addition )
+ {
+ byte[] keyBuffer = keySerializer.serialize( modification.getKey() );
+ ByteBuffer bb = ByteBuffer.allocateDirect( keyBuffer.length + 1 );
+ bb.put( Modification.ADDITION );
+ bb.put( keyBuffer );
+ bb.flip();
+
+ journalChannel.write( bb );
+
+ byte[] valueBuffer = valueSerializer.serialize( modification.getValue() );
+ bb = ByteBuffer.allocateDirect( valueBuffer.length );
+ bb.put( valueBuffer );
+ bb.flip();
+
+ journalChannel.write( bb );
+ }
+ else if ( modification instanceof Deletion )
+ {
+ byte[] keyBuffer = keySerializer.serialize( modification.getKey() );
+ ByteBuffer bb = ByteBuffer.allocateDirect( keyBuffer.length + 1 );
+ bb.put( Modification.DELETION );
+ bb.put( keyBuffer );
+ bb.flip();
+
+ journalChannel.write( bb );
+ }
+
+ // Flush to the disk for real
+ journalChannel.force( true );
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ switch ( type )
+ {
+ case IN_MEMORY:
+ sb.append( "In-memory " );
+ break;
+
+ case PERSISTENT:
+ sb.append( "Persistent " );
+ break;
+
+ }
+
+ sb.append( "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() );
+
+ if ( type == BTreeTypeEnum.PERSISTENT )
+ {
+ try
+ {
+ sb.append( ", file : " );
+
+ if ( file != null )
+ {
+ sb.append( file.getCanonicalPath() );
+ }
+ else
+ {
+ sb.append( "Unknown" );
+ }
+
+ sb.append( ", journal : " );
+
+ if ( journal != null )
+ {
+ sb.append( journal.getCanonicalPath() );
+ }
+ else
+ {
+ sb.append( "Unkown" );
+ }
+ }
+ catch ( IOException ioe )
+ {
+ // There is little we can do here...
+ }
+ }
+
+ sb.append( ") : \n" );
+ sb.append( rootPage.dumpPage( "" ) );
+
+ return sb.toString();
+ }
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTreeBuilder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTreeBuilder.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTreeBuilder.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/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.memory;
+
+
+import static org.apache.directory.mavibot.btree.memory.BTreeFactory.createLeaf;
+import static org.apache.directory.mavibot.btree.memory.BTreeFactory.createNode;
+import static org.apache.directory.mavibot.btree.memory.BTreeFactory.setKey;
+import static org.apache.directory.mavibot.btree.memory.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.Tuple;
+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/memory/BTreeConfiguration.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTreeConfiguration.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTreeConfiguration.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTreeConfiguration.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,343 @@
+/*
+ * 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.memory;
+
+
+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 type of BTree */
+ private BTreeTypeEnum type;
+
+ /** 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 type of BTree
+ */
+ public BTreeTypeEnum getType()
+ {
+ return type;
+ }
+
+
+ /**
+ * Sets the type of the BTree
+ *
+ * @param type the type of the tree
+ */
+ public void setType( BTreeTypeEnum type )
+ {
+ this.type = type;
+ }
+
+
+ /**
+ * @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/memory/BTreeFactory.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTreeFactory.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTreeFactory.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTreeFactory.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,276 @@
+/*
+ * 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.memory;
+
+
+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 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/memory/BTreeTypeEnum.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTreeTypeEnum.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTreeTypeEnum.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTreeTypeEnum.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,41 @@
+/*
+ * 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.memory;
+
+
+/**
+ * An enum to describe the BTree type. We have three possible type :
+ * <ul>
+ * <li>IN_MEMORY : the BTree will remain in memory, and won't be persisted on disk</li>
+ * <li>PERSISTENT : the BTree is in memory, but will be persisted on disk</li>
+ * <li>MANAGED : the BTree is managed by a RecordManager, and some pages may
+ * be swapped out from memory on demand</li>
+ * </ul>
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public enum BTreeTypeEnum
+{
+ /** Pure in-memory BTree, not persisted on disk */
+ IN_MEMORY,
+
+ /** In-memory BTree but persisted on disk */
+ PERSISTENT
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BorrowedFromLeftResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BorrowedFromLeftResult.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BorrowedFromLeftResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/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.memory;
+
+
+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/memory/BorrowedFromRightResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BorrowedFromRightResult.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BorrowedFromRightResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/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.memory;
+
+
+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();
+ }
+}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BorrowedFromSiblingResult.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BorrowedFromSiblingResult.java?rev=1527458&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BorrowedFromSiblingResult.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BorrowedFromSiblingResult.java Mon Sep 30 06:32:25 2013
@@ -0,0 +1,53 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.mavibot.btree.memory;
+
+
+/**
+ * The result of an delete operation, when we have borrowed some element from a sibling.
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+interface BorrowedFromSiblingResult<K, V> extends DeleteResult<K, V>
+{
+ /**
+ * @return the modifiedSibling
+ */
+ Page<K, V> getModifiedSibling();
+
+
+ /**
+ * Tells if the sibling is on the left
+ *
+ * @return True if the sibling is on the left
+ */
+ boolean isFromLeft();
+
+
+ /**
+ * Tells if the sibling is on the right
+ *
+ * @return True if the sibling is on the right
+ */
+ boolean isFromRight();
+}