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 2014/05/17 15:31:25 UTC
svn commit: r1595477 [3/8] - in /directory/mavibot/trunk: ./ mavibot/img/
mavibot/src/main/java/org/apache/directory/mavibot/btree/
mavibot/src/main/java/org/apache/directory/mavibot/btree/comparator/
mavibot/src/main/java/org/apache/directory/mavibot/...
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeFactory.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeFactory.java?rev=1595477&r1=1595476&r2=1595477&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeFactory.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeFactory.java Sat May 17 13:31:23 2014
@@ -20,31 +20,31 @@
package org.apache.directory.mavibot.btree;
-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>
- *
+ * This class construct a B-tree from a serialized version of a B-tree. We need it
+ * to avoid exposing all the methods of the B-tree class.<br>
+ *
* All its methods are static.
- *
+ *
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
*
- * @param <K> The BTree key type
- * @param <V> The BTree valye type
+ * @param <K> The B-tree key type
+ * @param <V> The B-tree value type
*/
public class BTreeFactory<K, V>
{
//--------------------------------------------------------------------------------------------
// Create persisted btrees
//--------------------------------------------------------------------------------------------
-
/**
- * Creates a new persisted BTree, with no initialization.
+ * Creates a new persisted B-tree, with no initialization.
+ *
+ * @return a new B-tree instance
*/
public static <K, V> BTree<K, V> createPersistedBTree()
{
@@ -55,10 +55,36 @@ public class BTreeFactory<K, V>
/**
- * Creates a new persisted BTree using the BTreeConfiguration to initialize the
- * BTree
- *
+ * Creates a new persisted B-tree, with no initialization.
+ *
+ * @return a new B-tree instance
+ */
+ public static <K, V> BTree<K, V> createPersistedBTree( BTreeTypeEnum type )
+ {
+ BTree<K, V> btree = new PersistedBTree<K, V>();
+ ((AbstractBTree<K, V>)btree).setType( type );
+
+ return btree;
+ }
+
+
+ /**
+ * Sets the btreeHeader offset for a Persisted BTree
+ *
+ * @param btree The btree to update
+ * @param btreeHeaderOffset The offset
+ */
+ public static <K, V> void setBtreeHeaderOffset( PersistedBTree<K, V> btree, long btreeHeaderOffset )
+ {
+ btree.setBtreeHeaderOffset( btreeHeaderOffset );
+ }
+
+ /**
+ * Creates a new persisted B-tree using the BTreeConfiguration to initialize the
+ * B-tree
+ *
* @param configuration The configuration to use
+ * @return a new B-tree instance
*/
public static <K, V> BTree<K, V> createPersistedBTree( PersistedBTreeConfiguration<K, V> configuration )
{
@@ -69,14 +95,13 @@ public class BTreeFactory<K, V>
/**
- * Creates a new persisted BTree using the parameters to initialize the
- * BTree
- *
- * @param name The BTree's name
+ * Creates a new persisted B-tree using the parameters to initialize the
+ * B-tree
+ *
+ * @param name The B-tree's name
* @param keySerializer Key serializer
* @param valueSerializer Value serializer
- * @param allowDuplicates Tells if the BTree allows multiple value for a given key
- * @throws IOException
+ * @return a new B-tree instance
*/
public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer )
@@ -98,14 +123,14 @@ public class BTreeFactory<K, V>
/**
- * Creates a new persisted BTree using the parameters to initialize the
- * BTree
- *
- * @param name The BTree's name
+ * Creates a new persisted B-tree using the parameters to initialize the
+ * B-tree
+ *
+ * @param name The B-tree's name
* @param keySerializer Key serializer
* @param valueSerializer Value serializer
- * @param allowDuplicates Tells if the BTree allows multiple value for a given key
- * @throws IOException
+ * @param allowDuplicates Tells if the B-tree allows multiple value for a given key
+ * @return a new B-tree instance
*/
public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer, boolean allowDuplicates )
@@ -127,15 +152,15 @@ public class BTreeFactory<K, V>
/**
- * Creates a new persisted BTree using the parameters to initialize the
- * BTree
- *
- * @param name The BTree's name
+ * Creates a new persisted B-tree using the parameters to initialize the
+ * B-tree
+ *
+ * @param name The B-tree's name
* @param keySerializer Key serializer
* @param valueSerializer Value serializer
- * @param allowDuplicates Tells if the BTree allows multiple value for a given key
- * @param cacheSize The size to be used for this BTree cache
- * @throws IOException
+ * @param allowDuplicates Tells if the B-tree allows multiple value for a given key
+ * @param cacheSize The size to be used for this B-tree cache
+ * @return a new B-tree instance
*/
public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer, boolean allowDuplicates, int cacheSize )
@@ -157,14 +182,14 @@ public class BTreeFactory<K, V>
/**
- * Creates a new persisted BTree using the parameters to initialize the
- * BTree
- *
- * @param name The BTree's name
+ * Creates a new persisted B-tree using the parameters to initialize the
+ * B-tree
+ *
+ * @param name The B-tree's name
* @param keySerializer Key serializer
* @param valueSerializer Value serializer
* @param pageSize Size of the page
- * @throws IOException
+ * @return a new B-tree instance
*/
public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer, int pageSize )
@@ -186,15 +211,15 @@ public class BTreeFactory<K, V>
/**
- * Creates a new persisted BTree using the parameters to initialize the
- * BTree
- *
- * @param name The BTree's name
+ * Creates a new persisted B-tree using the parameters to initialize the
+ * B-tree
+ *
+ * @param name The B-tree's name
* @param keySerializer Key serializer
* @param valueSerializer Value serializer
* @param pageSize Size of the page
- * @param allowDuplicates Tells if the BTree allows multiple value for a given key
- * @throws IOException
+ * @param allowDuplicates Tells if the B-tree allows multiple value for a given key
+ * @return a new B-tree instance
*/
public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer, int pageSize, boolean allowDuplicates )
@@ -216,16 +241,16 @@ public class BTreeFactory<K, V>
/**
- * Creates a new persisted BTree using the parameters to initialize the
- * BTree
- *
- * @param name The BTree's name
+ * Creates a new persisted B-tree using the parameters to initialize the
+ * B-tree
+ *
+ * @param name The B-tree's name
* @param keySerializer Key serializer
* @param valueSerializer Value serializer
* @param pageSize Size of the page
- * @param allowDuplicates Tells if the BTree allows multiple value for a given key
- * @param cacheSize The size to be used for this BTree cache
- * @throws IOException
+ * @param allowDuplicates Tells if the B-tree allows multiple value for a given key
+ * @param cacheSize The size to be used for this B-tree cache
+ * @return a new B-tree instance
*/
public static <K, V> BTree<K, V> createPersistedBTree( String name, ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer, int pageSize, boolean allowDuplicates, int cacheSize )
@@ -247,10 +272,12 @@ public class BTreeFactory<K, V>
//--------------------------------------------------------------------------------------------
- // Create in-memory btrees
+ // Create in-memory B-trees
//--------------------------------------------------------------------------------------------
/**
- * Creates a new in-memory BTree, with no initialization.
+ * Creates a new in-memory B-tree, with no initialization.
+ *
+ * @return a new B-tree instance
*/
public static <K, V> BTree<K, V> createInMemoryBTree()
{
@@ -261,10 +288,11 @@ public class BTreeFactory<K, V>
/**
- * Creates a new in-memory BTree using the BTreeConfiguration to initialize the
- * BTree
- *
+ * Creates a new in-memory B-tree using the BTreeConfiguration to initialize the
+ * B-tree
+ *
* @param configuration The configuration to use
+ * @return a new B-tree instance
*/
public static <K, V> BTree<K, V> createInMemoryBTree( InMemoryBTreeConfiguration<K, V> configuration )
{
@@ -275,12 +303,13 @@ public class BTreeFactory<K, V>
/**
- * Creates a new in-memory BTree using the parameters to initialize the
- * BTree
- *
- * @param name The BTree's name
+ * Creates a new in-memory B-tree using the parameters to initialize the
+ * B-tree
+ *
+ * @param name The B-tree's name
* @param keySerializer Key serializer
* @param valueSerializer Value serializer
+ * @return a new B-tree instance
*/
public static <K, V> BTree<K, V> createInMemoryBTree( String name, ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer )
@@ -301,14 +330,14 @@ public class BTreeFactory<K, V>
/**
- * Creates a new in-memory BTree using the parameters to initialize the
- * BTree
- *
- * @param name The BTree's name
+ * Creates a new in-memory B-tree using the parameters to initialize the
+ * B-tree
+ *
+ * @param name The B-tree's name
* @param keySerializer Key serializer
* @param valueSerializer Value serializer
- * @param allowDuplicates Tells if the BTree allows multiple value for a given key
- * @throws IOException
+ * @param allowDuplicates Tells if the B-tree allows multiple value for a given key
+ * @return a new B-tree instance
*/
public static <K, V> BTree<K, V> createInMemoryBTree( String name, ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer, boolean allowDuplicates )
@@ -329,14 +358,14 @@ public class BTreeFactory<K, V>
/**
- * Creates a new in-memory BTree using the parameters to initialize the
- * BTree
- *
- * @param name The BTree's name
+ * Creates a new in-memory B-tree using the parameters to initialize the
+ * B-tree
+ *
+ * @param name The B-tree's name
* @param keySerializer Key serializer
* @param valueSerializer Value serializer
* @param pageSize Size of the page
- * @throws IOException
+ * @return a new B-tree instance
*/
public static <K, V> BTree<K, V> createInMemoryBTree( String name, ElementSerializer<K> keySerializer,
ElementSerializer<V> valueSerializer, int pageSize )
@@ -357,14 +386,14 @@ public class BTreeFactory<K, V>
/**
- * Creates a new in-memory BTree using the parameters to initialize the
- * BTree
- *
- * @param name The BTree's name
+ * Creates a new in-memory B-tree using the parameters to initialize the
+ * B-tree
+ *
+ * @param name The B-tree's name
* @param filePath The name of the data directory with absolute path
* @param keySerializer Key serializer
* @param valueSerializer Value serializer
- * @throws IOException
+ * @return a new B-tree instance
*/
public static <K, V> BTree<K, V> createInMemoryBTree( String name, String filePath,
ElementSerializer<K> keySerializer,
@@ -387,19 +416,18 @@ public class BTreeFactory<K, V>
/**
- * Creates a new in-memory BTree using the parameters to initialize the
- * BTree
- *
- * @param name The BTree's name
+ * Creates a new in-memory B-tree using the parameters to initialize the
+ * B-tree
+ *
+ * @param name The B-tree's name
* @param filePath 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
+ * @return a new B-tree instance
*/
public static <K, V> BTree<K, V> createInMemoryBTree( String name, String filePath,
- ElementSerializer<K> keySerializer,
- ElementSerializer<V> valueSerializer, int pageSize )
+ ElementSerializer<K> keySerializer, ElementSerializer<V> valueSerializer, int pageSize )
{
InMemoryBTreeConfiguration<K, V> configuration = new InMemoryBTreeConfiguration<K, V>();
@@ -418,16 +446,16 @@ public class BTreeFactory<K, V>
/**
- * Creates a new in-memory BTree using the parameters to initialize the
- * BTree
- *
- * @param name The BTree's name
+ * Creates a new in-memory B-tree using the parameters to initialize the
+ * B-tree
+ *
+ * @param name The B-tree's name
* @param filePath The name of the data directory with absolute path
* @param keySerializer Key serializer
* @param valueSerializer Value serializer
* @param pageSize Size of the page
- * @param allowDuplicates Tells if the BTree allows multiple value for a given key
- * @throws IOException
+ * @param allowDuplicates Tells if the B-tree allows multiple value for a given key
+ * @return a new B-tree instance
*/
public static <K, V> BTree<K, V> createInMemoryBTree( String name, String filePath,
ElementSerializer<K> keySerializer,
@@ -453,17 +481,17 @@ public class BTreeFactory<K, V>
// Create Pages
//--------------------------------------------------------------------------------------------
/**
- * Create a new Leaf for the given BTree.
- *
- * @param btree The BTree which will contain this leaf
+ * Create a new Leaf for the given B-tree.
+ *
+ * @param btree The B-tree which will contain this leaf
* @param revision The Leaf's revision
* @param nbElems The number or elements in this leaf
- *
+ *
* @return A Leaf instance
*/
/* no qualifier*/static <K, V> Page<K, V> createLeaf( BTree<K, V> btree, long revision, int nbElems )
{
- if ( btree.getType() == BTreeTypeEnum.PERSISTED )
+ if ( btree.getType() != BTreeTypeEnum.IN_MEMORY )
{
return new PersistedLeaf<K, V>( btree, revision, nbElems );
}
@@ -475,16 +503,16 @@ public class BTreeFactory<K, V>
/**
- * Create a new Node for the given BTree.
- *
- * @param btree The BTree which will contain this node
+ * Create a new Node for the given B-tree.
+ *
+ * @param btree The B-tree which will contain this node
* @param revision The Node's revision
* @param nbElems The number or elements in this node
* @return A Node instance
*/
/* no qualifier*/static <K, V> Page<K, V> createNode( BTree<K, V> btree, long revision, int nbElems )
{
- if ( btree.getType() == BTreeTypeEnum.PERSISTED )
+ if ( btree.getType() != BTreeTypeEnum.IN_MEMORY )
{
return new PersistedNode<K, V>( btree, revision, nbElems );
}
@@ -500,8 +528,8 @@ public class BTreeFactory<K, V>
//--------------------------------------------------------------------------------------------
/**
* Set the key at a give position
- *
- * @param btree The BTree to update
+ *
+ * @param btree The B-tree to update
* @param page The page to update
* @param pos The position in the keys array
* @param key The key to inject
@@ -510,7 +538,7 @@ public class BTreeFactory<K, V>
{
KeyHolder<K> keyHolder;
- if ( btree.getType() == BTreeTypeEnum.PERSISTED )
+ if ( btree.getType() != BTreeTypeEnum.IN_MEMORY )
{
keyHolder = new PersistedKeyHolder<K>( btree.getKeySerializer(), key );
}
@@ -525,12 +553,15 @@ public class BTreeFactory<K, V>
/**
* Set the value at a give position
+ *
+ * @param btree The B-tree to update
+ * @param page The page to update
* @param pos The position in the values array
* @param value the value to inject
*/
/* no qualifier*/static <K, V> void setValue( BTree<K, V> btree, Page<K, V> page, int pos, ValueHolder<V> value )
{
- if ( btree.getType() == BTreeTypeEnum.PERSISTED )
+ if ( btree.getType() != BTreeTypeEnum.IN_MEMORY )
{
( ( PersistedLeaf<K, V> ) page ).setValue( pos, value );
}
@@ -543,15 +574,15 @@ public class BTreeFactory<K, V>
/**
* Set the page at a give position
- *
- * @param btree The BTree to update
+ *
+ * @param btree The B-tree to update
* @param page The page to update
* @param pos The position in the values array
- * @param value the value to inject
+ * @param child the child page to inject
*/
/* no qualifier*/static <K, V> void setPage( BTree<K, V> btree, Page<K, V> page, int pos, Page<K, V> child )
{
- if ( btree.getType() == BTreeTypeEnum.PERSISTED )
+ if ( btree.getType() != BTreeTypeEnum.IN_MEMORY )
{
( ( PersistedNode<K, V> ) page ).setValue( pos, new PersistedPageHolder<K, V>( btree, child ) );
}
@@ -563,42 +594,76 @@ public class BTreeFactory<K, V>
//--------------------------------------------------------------------------------------------
- // Update BTree
+ // Update B-tree
//--------------------------------------------------------------------------------------------
/**
- * Sets the KeySerializer into the BTree
- *
- * @param btree The BTree to update
+ * Sets the KeySerializer into the B-tree
+ *
+ * @param btree The B-tree to update
* @param keySerializerFqcn the Key serializer FQCN to set
- * @throws ClassNotFoundException
- * @throws InstantiationException
- * @throws IllegalAccessException
+ * @throws ClassNotFoundException If the key serializer class cannot be found
+ * @throws InstantiationException If the key serializer class cannot be instanciated
+ * @throws IllegalAccessException If the key serializer class cannot be accessed
+ * @throws NoSuchFieldException
+ * @throws SecurityException
+ * @throws IllegalArgumentException
*/
/* no qualifier*/static <K, V> void setKeySerializer( BTree<K, V> btree, String keySerializerFqcn )
- throws ClassNotFoundException, IllegalAccessException, InstantiationException
+ throws ClassNotFoundException, IllegalAccessException, InstantiationException, IllegalArgumentException, SecurityException, NoSuchFieldException
{
Class<?> keySerializer = Class.forName( keySerializerFqcn );
@SuppressWarnings("unchecked")
- ElementSerializer<K> instance = ( ElementSerializer<K> ) keySerializer.newInstance();
+ ElementSerializer<K> instance = null;
+ try
+ {
+ instance = ( ElementSerializer<K> ) keySerializer.getDeclaredField( "INSTANCE" ).get( null );
+ }
+ catch( NoSuchFieldException e )
+ {
+ // ignore
+ }
+
+ if ( instance == null )
+ {
+ instance = ( ElementSerializer<K> ) keySerializer.newInstance();
+ }
+
btree.setKeySerializer( instance );
}
/**
- * Sets the ValueSerializer into the BTree
- *
- * @param btree The BTree to update
+ * Sets the ValueSerializer into the B-tree
+ *
+ * @param btree The B-tree to update
* @param valueSerializerFqcn the Value serializer FQCN to set
- * @throws ClassNotFoundException
- * @throws InstantiationException
- * @throws IllegalAccessException
+ * @throws ClassNotFoundException If the value serializer class cannot be found
+ * @throws InstantiationException If the value serializer class cannot be instanciated
+ * @throws IllegalAccessException If the value serializer class cannot be accessed
+ * @throws NoSuchFieldException
+ * @throws SecurityException
+ * @throws IllegalArgumentException
*/
/* no qualifier*/static <K, V> void setValueSerializer( BTree<K, V> btree, String valueSerializerFqcn )
- throws ClassNotFoundException, IllegalAccessException, InstantiationException
+ throws ClassNotFoundException, IllegalAccessException, InstantiationException, IllegalArgumentException, SecurityException, NoSuchFieldException
{
Class<?> valueSerializer = Class.forName( valueSerializerFqcn );
@SuppressWarnings("unchecked")
- ElementSerializer<V> instance = ( ElementSerializer<V> ) valueSerializer.newInstance();
+ ElementSerializer<V> instance = null;
+ try
+ {
+ instance = ( ElementSerializer<V> ) valueSerializer.getDeclaredField( "INSTANCE" ).get( null );
+ }
+ catch( NoSuchFieldException e )
+ {
+ // ignore
+ }
+
+ if ( instance == null )
+ {
+ instance = ( ElementSerializer<V> ) valueSerializer.newInstance();
+ }
+
btree.setValueSerializer( instance );
}
@@ -606,8 +671,8 @@ public class BTreeFactory<K, V>
/**
* Set the new root page for this tree. Used for debug purpose only. The revision
* will always be 0;
- *
- * @param btree The BTree to update
+ *
+ * @param btree The B-tree to update
* @param root the new root page.
*/
/* no qualifier*/static <K, V> void setRootPage( BTree<K, V> btree, Page<K, V> root )
@@ -617,9 +682,9 @@ public class BTreeFactory<K, V>
/**
- * Return the BTree root page
- *
- * @param btree The Btree we want to root page from
+ * Return the B-tree root page
+ *
+ * @param btree The B-tree we want to root page from
* @return The root page
*/
/* no qualifier */static <K, V> Page<K, V> getRootPage( BTree<K, V> btree )
@@ -629,9 +694,9 @@ public class BTreeFactory<K, V>
/**
- * update the BTree number of elements
- *
- * @param btree The BTree to update
+ * Update the B-tree number of elements
+ *
+ * @param btree The B-tree to update
* @param nbElems the nbElems to set
*/
/* no qualifier */static <K, V> void setNbElems( BTree<K, V> btree, long nbElems )
@@ -641,9 +706,9 @@ public class BTreeFactory<K, V>
/**
- * Update the btree revision
- *
- * @param btree The BTree to update
+ * Update the B-tree revision
+ *
+ * @param btree The B-tree to update
* @param revision the revision to set
*/
/* no qualifier*/static <K, V> void setRevision( BTree<K, V> btree, long revision )
@@ -653,9 +718,9 @@ public class BTreeFactory<K, V>
/**
- * Set the BTree name
- *
- * @param btree The BTree to update
+ * Set the B-tree name
+ *
+ * @param btree The B-tree to update
* @param name the name to set
*/
/* no qualifier */static <K, V> void setName( BTree<K, V> btree, String name )
@@ -666,8 +731,8 @@ public class BTreeFactory<K, V>
/**
* Set the maximum number of elements we can store in a page.
- *
- * @param btree The BTree to update
+ *
+ * @param btree The B-tree to update
* @param pageSize The requested page size
*/
/* no qualifier */static <K, V> void setPageSize( BTree<K, V> btree, int pageSize )
@@ -681,8 +746,8 @@ public class BTreeFactory<K, V>
//--------------------------------------------------------------------------------------------
/**
* Includes the intermediate nodes in the path up to and including the right most leaf of the tree
- *
- * @param btree the btree
+ *
+ * @param btree the B-tree
* @return a LinkedList of all the nodes and the final leaf
*/
/* no qualifier*/static <K, V> LinkedList<ParentPos<K, V>> getPathToRightMostLeaf( BTree<K, V> btree )
@@ -724,50 +789,31 @@ public class BTreeFactory<K, V>
//--------------------------------------------------------------------------------------------
- // Persisted BTree methods
+ // Persisted B-tree methods
//--------------------------------------------------------------------------------------------
/**
- * Set the rootPage offset of the BTree
- *
- * @param btree The btree to update
+ * Set the rootPage offset of the B-tree
+ *
+ * @param btree The B-tree to update
* @param rootPageOffset The rootPageOffset to set
*/
/* no qualifier*/static <K, V> void setRootPageOffset( BTree<K, V> btree, long rootPageOffset )
{
if ( btree instanceof PersistedBTree )
{
- ( ( PersistedBTree<K, V> ) btree ).setRootPageOffset( rootPageOffset );
- }
- else
- {
- throw new IllegalArgumentException( "The BTree must be a PersistedBTree" );
- }
- }
-
-
- /**
- * Set the nextBTree offset
- *
- * @param btree The btree to update
- * @param nextBTreeOffset The nextBTreeOffset to set
- */
- /* no qualifier*/static <K, V> void setNextBTreeOffset( BTree<K, V> btree, long nextBTreeOffset )
- {
- if ( btree instanceof PersistedBTree )
- {
- ( ( PersistedBTree<K, V> ) btree ).setNextBTreeOffset( nextBTreeOffset );
+ ( ( PersistedBTree<K, V> ) btree ).getBtreeHeader().setRootPageOffset( rootPageOffset );
}
else
{
- throw new IllegalArgumentException( "The BTree must be a PersistedBTree" );
+ throw new IllegalArgumentException( "The B-tree must be a PersistedBTree" );
}
}
/**
* Set the RecordManager
- *
- * @param btree The btree to update
+ *
+ * @param btree The B-tree to update
* @param recordManager The injected RecordManager
*/
/* no qualifier*/static <K, V> void setRecordManager( BTree<K, V> btree, RecordManager recordManager )
@@ -778,15 +824,15 @@ public class BTreeFactory<K, V>
}
else
{
- throw new IllegalArgumentException( "The BTree must be a PersistedBTree" );
+ throw new IllegalArgumentException( "The B-tree must be a PersistedBTree" );
}
}
/**
* Set the key at a give position
- *
- * @param btree The btree to update
+ *
+ * @param btree The B-tree to update
* @param page The page to update
* @param pos The position of this key in the page
* @param buffer The byte[] containing the serialized key
@@ -800,15 +846,15 @@ public class BTreeFactory<K, V>
}
else
{
- throw new IllegalArgumentException( "The BTree must be a PersistedBTree" );
+ throw new IllegalArgumentException( "The B-tree must be a PersistedBTree" );
}
}
/**
* Includes the intermediate nodes in the path up to and including the left most leaf of the tree
- *
- * @param btree The btree to process
+ *
+ * @param btree The B-tree to process
* @return a LinkedList of all the nodes and the final leaf
*/
/* no qualifier*/static <K, V> LinkedList<ParentPos<K, V>> getPathToLeftMostLeaf( BTree<K, V> btree )
@@ -850,7 +896,7 @@ public class BTreeFactory<K, V>
}
else
{
- throw new IllegalArgumentException( "The BTree must be a PersistedBTree" );
+ throw new IllegalArgumentException( "The B-tree must be a PersistedBTree" );
}
}
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeHeader.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeHeader.java?rev=1595477&r1=1595476&r2=1595477&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeHeader.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeHeader.java Sat May 17 13:31:23 2014
@@ -19,13 +19,12 @@
*/
package org.apache.directory.mavibot.btree;
-
-import java.util.concurrent.atomic.AtomicLong;
+import java.util.concurrent.atomic.AtomicInteger;
/**
- * Store in memory the information associated with a BTree. <br>
- * A BTree Header on disk contains the following elements :
+ * Store in memory the information associated with a B-tree. <br>
+ * A B-tree Header on disk contains the following elements :
* <pre>
* +--------------------+-------------+
* | revision | 8 bytes |
@@ -34,55 +33,42 @@ import java.util.concurrent.atomic.Atomi
* +--------------------+-------------+
* | rootPageOffset | 8 bytes |
* +--------------------+-------------+
- * | nextBtreeHeader | 8 bytes |
- * +--------------------+-------------+
- * | pageSize | 4 bytes |
- * +--------------------+-------------+
- * | name | 4 bytes + N |
- * +--------------------+-------------+
- * | keySerializeFQCN | 4 bytes + N |
- * +--------------------+-------------+
- * | valueSerializeFQCN | 4 bytes + N |
+ * | BtreeOffset | 8 bytes |
* +--------------------+-------------+
* </pre>
- * Each BtreeHeader will be written starting on a new page.
+ * Each B-tree Header will be written starting on a new page.
+ * In memory, a B-tree Header store a bit more of information :
+ * <li>
+ * <ul>rootPage : the associated rootPage in memory</lu>
+ * <ul>nbUsers : the number of readThreads using this revision</lu>
+ * <ul>offset : the offset of this B-tre header</lu>
+ * </li>
*
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
*/
-/* No qualifier*/class BTreeHeader
+/* No qualifier*/class BTreeHeader<K, V> implements Cloneable
{
/** The current revision */
- private AtomicLong revision = new AtomicLong( 0L );
+ private long revision = 0L;
- /** The number of elements in this BTree */
- private AtomicLong nbElems = new AtomicLong( 0L );
+ /** The number of elements in this B-tree */
+ private Long nbElems = 0L;
- /** The offset of the BTree RootPage */
+ /** The offset of the B-tree RootPage */
private long rootPageOffset;
- /** The offset of the next BTree */
- private long nextBTreeOffset;
-
- /** The number of elements in a page for this BTree */
- private int pageSize;
-
- /** The BTree name */
- private String name;
-
- /** The FQCN of the Key serializer */
- private String keySerializerFQCN;
-
- /** The FQCN of the Value serializer */
- private String valueSerializerFQCN;
+ /** The position of the B-tree header in the file */
+ private long btreeHeaderOffset;
// Those are data which aren't serialized : they are in memory only */
- /** The position in the file */
- private long btreeOffset;
+ /** A Map containing the rootPage for this tree */
+ private Page<K, V> rootPage;
- /** The existing versions */
- private long[] versions;
+ /** The number of users for this BtreeHeader */
+ private AtomicInteger nbUsers = new AtomicInteger( 0 );
- private int allowDuplicates = 0;
+ /** The B-tree this header is associated with */
+ private BTree<K, V> btree;
/**
@@ -94,56 +80,61 @@ import java.util.concurrent.atomic.Atomi
/**
- * @return the name
+ * @return the B-tree info Offset
*/
- public String getName()
+ public long getBTreeInfoOffset()
{
- return name;
+ return ((PersistedBTree<K, V>)btree).getBtreeInfoOffset();
}
/**
- * @param name the name to set
+ * @return the B-tree header Offset
*/
- /* no qualifier */void setName( String name )
+ public long getBTreeHeaderOffset()
{
- this.name = name;
+ return btreeHeaderOffset;
}
- /**
- * @return the versions
- */
- public long[] getVersions()
+ public BTreeHeader<K, V> clone()
{
- return versions;
+ try
+ {
+ BTreeHeader<K, V> copy = (BTreeHeader<K, V>)super.clone();
+
+ return copy;
+ }
+ catch ( CloneNotSupportedException cnse )
+ {
+ return null;
+ }
}
/**
- * @param versions the versions to set
+ * Copy the current B-tre header and return the copy
+ * @return
*/
- /* no qualifier */void setVersions( long[] versions )
+ /* no qualifier */ BTreeHeader<K, V> copy()
{
- this.versions = versions;
- }
+ BTreeHeader<K, V> copy = clone();
+ // Clear the fields that should not be copied
+ copy.rootPage = null;
+ copy.rootPageOffset = -1L;
+ copy.btreeHeaderOffset = -1L;
- /**
- * @return the btreeOffset
- */
- public long getBTreeOffset()
- {
- return btreeOffset;
+ return copy;
}
/**
- * @param btreeOffset the btreeOffset to set
+ * @param btreeOffset the B-tree header Offset to set
*/
- /* no qualifier */void setBTreeOffset( long btreeOffset )
+ /* no qualifier */void setBTreeHeaderOffset( long btreeHeaderOffset )
{
- this.btreeOffset = btreeOffset;
+ this.btreeHeaderOffset = btreeHeaderOffset;
}
@@ -170,7 +161,7 @@ import java.util.concurrent.atomic.Atomi
*/
public long getRevision()
{
- return revision.get();
+ return revision;
}
@@ -179,27 +170,25 @@ import java.util.concurrent.atomic.Atomi
*/
/* no qualifier */void setRevision( long revision )
{
- this.revision.set( revision );
+ this.revision = revision;
}
/**
- * Increment the revision
- *
- * @return the new revision
+ * @return the nbElems
*/
- /* no qualifier */long incrementRevision()
+ public long getNbElems()
{
- return revision.incrementAndGet();
+ return nbElems;
}
/**
- * @return the nbElems
+ * @param nbElems the nbElems to set
*/
- public long getNbElems()
+ /* no qualifier */void setNbElems( long nbElems )
{
- return nbElems.get();
+ this.nbElems = nbElems;
}
@@ -208,109 +197,80 @@ import java.util.concurrent.atomic.Atomi
*/
/* no qualifier */void incrementNbElems()
{
- nbElems.incrementAndGet();
+ nbElems++;
}
/**
* Decrement the number of elements
*/
- public void decrementNbElems()
+ /* no qualifier */void decrementNbElems()
{
- nbElems.decrementAndGet();
+ nbElems--;
}
/**
- * @param nbElems the nbElems to set
+ * @return the rootPage
*/
- /* no qualifier */void setNbElems( long nbElems )
+ /* no qualifier */ Page<K, V> getRootPage()
{
- this.nbElems.set( nbElems );
+ return rootPage;
}
/**
- * @return the nextBTreeOffset
+ * @param rootPage the rootPage to set
*/
- public long getNextBTreeOffset()
+ /* no qualifier */ void setRootPage( Page<K, V> rootPage )
{
- return nextBTreeOffset;
+ this.rootPage = rootPage;
+ this.rootPageOffset = ((AbstractPage<K, V>)rootPage).getOffset();
}
/**
- * @param nextBtreeOffset the nextBtreeOffset to set
+ * @return the nbUsers
*/
- /* no qualifier */void setNextBTreeOffset( long nextBTreeOffset )
+ /* no qualifier */ int getNbUsers()
{
- this.nextBTreeOffset = nextBTreeOffset;
+ return nbUsers.get();
}
/**
- * @return the pageSize
+ * Increment the number of users
*/
- public int getPageSize()
+ /* no qualifier */ void incrementNbUsers()
{
- return pageSize;
+ nbUsers.incrementAndGet();
}
/**
- * @param pageSize the pageSize to set
+ * Decrement the number of users
*/
- /* no qualifier */void setPageSize( int pageSize )
+ /* no qualifier */ void decrementNbUsers()
{
- this.pageSize = pageSize;
+ nbUsers.decrementAndGet();
}
/**
- * @return the keySerializerFQCN
+ * @return the btree
*/
- public String getKeySerializerFQCN()
+ /* no qualifier */ BTree<K, V> getBtree()
{
- return keySerializerFQCN;
+ return btree;
}
/**
- * @param keySerializerFQCN the keySerializerFQCN to set
+ * @param btree the btree to set
*/
- /* no qualifier */void setKeySerializerFQCN( String keySerializerFQCN )
+ /* no qualifier */ void setBtree( BTree<K, V> btree )
{
- this.keySerializerFQCN = keySerializerFQCN;
- }
-
-
- /**
- * @return the valueSerializerFQCN
- */
- public String getValueSerializerFQCN()
- {
- return valueSerializerFQCN;
- }
-
-
- /**
- * @param valueSerializerFQCN the valueSerializerFQCN to set
- */
- /* no qualifier */void setValueSerializerFQCN( String valueSerializerFQCN )
- {
- this.valueSerializerFQCN = valueSerializerFQCN;
- }
-
-
- public boolean isAllowDuplicates()
- {
- return ( allowDuplicates == 1 );
- }
-
-
- /* no qualifier */void setAllowDuplicates( boolean allowDuplicates )
- {
- this.allowDuplicates = ( allowDuplicates ? 1 : 0 );
+ this.btree = btree;
}
@@ -321,42 +281,14 @@ import java.util.concurrent.atomic.Atomi
{
StringBuilder sb = new StringBuilder();
- sb.append( "Btree '" ).append( name ).append( "'" );
+ sb.append( "B-treeHeader " );
+ sb.append( ", offset[0x" ).append( Long.toHexString( btreeHeaderOffset ) ).append( "]" );
+ sb.append( ", name[" ).append( btree.getName() ).append( "]" );
sb.append( ", revision[" ).append( revision ).append( "]" );
- sb.append( ", btreeOffset[" ).append( btreeOffset ).append( "]" );
- sb.append( ", rootPageOffset[" ).append( rootPageOffset ).append( "]" );
- sb.append( ", nextBTree[" ).append( nextBTreeOffset ).append( "]" );
+ sb.append( ", btreeInfoOffset[0x" ).append( Long.toHexString( ((PersistedBTree<K, V>)btree).getBtreeInfoOffset() ) ).append( "]" );
+ sb.append( ", rootPageOffset[0x" ).append( Long.toHexString( rootPageOffset ) ).append( "]" );
sb.append( ", nbElems[" ).append( nbElems ).append( "]" );
- sb.append( ", pageSize[" ).append( pageSize ).append( "]" );
- sb.append( ", hasDuplicates[" ).append( isAllowDuplicates() ).append( "]" );
- sb.append( "{\n" );
- sb.append( " Key serializer : " ).append( keySerializerFQCN ).append( "\n" );
- sb.append( " Value serializer : " ).append( valueSerializerFQCN ).append( "\n" );
- sb.append( "}\n" );
-
- if ( ( versions != null ) && ( versions.length != 0 ) )
- {
- sb.append( "Versions : \n" );
- sb.append( "{\n" );
-
- boolean isFirst = true;
-
- for ( long version : versions )
- {
- if ( isFirst )
- {
- isFirst = false;
- }
- else
- {
- sb.append( ",\n" );
- }
-
- sb.append( " " ).append( version );
- }
-
- sb.append( "}\n" );
- }
+ sb.append( ", nbUsers[" ).append( nbUsers.get() ).append( "]" );
return sb.toString();
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeTypeEnum.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeTypeEnum.java?rev=1595477&r1=1595476&r2=1595477&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeTypeEnum.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeTypeEnum.java Sat May 17 13:31:23 2014
@@ -21,24 +21,35 @@ package org.apache.directory.mavibot.btr
/**
- * An enum to describe the BTree type. We have three possible type :
+ * An enum to describe the B-tree 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
+ * <li>IN_MEMORY : the B-tree will remain in memory, and won't be persisted on disk</li>
+ * <li>BACKED_ON_DISK : the B-tree is in memory, but will be persisted on disk</li>
+ * <li>PERSISTED : the B-tree is managed by a RecordManager, and some pages may
* be swapped out from memory on demand</li>
+ * <li>PERSISTED_SUB : The B-tree is a Persisted B-tree, but a Sub B-tree one</li>
+ * <li>PERSISTED_MANAGEMENT : This is a Persisted B-tree used to manage the other B-trees</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 */
+ /** Pure in-memory B-tree, not persisted on disk */
IN_MEMORY,
- /** Persisted BTree */
+ /** Persisted B-tree */
PERSISTED,
- /** In-memory BTree but saved on disk */
+ /** Persisted sub B-tree */
+ PERSISTED_SUB,
+
+ /** Persisted Management B-tree */
+ BTREE_OF_BTREES,
+
+ /** Persisted Management B-tree */
+ COPIED_PAGES_BTREE,
+
+ /** In-memory B-tree but saved on disk */
BACKED_ON_DISK
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java?rev=1595477&r1=1595476&r2=1595477&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java Sat May 17 13:31:23 2014
@@ -29,7 +29,6 @@ import java.io.RandomAccessFile;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
import java.util.concurrent.ConcurrentLinkedQueue;
-import java.util.concurrent.locks.ReentrantLock;
import org.apache.directory.mavibot.btree.exception.InitializationException;
import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
@@ -72,18 +71,18 @@ import org.slf4j.LoggerFactory;
/** The associated journal. If null, this is an in-memory btree */
private File journal;
+ /** The directory where the journal will be stored */
private File envDir;
+ /** The Journal channel */
private FileChannel journalChannel = null;
-
/**
* Creates a new BTree, with no initialization.
*/
/* no qualifier */InMemoryBTree()
{
super();
- btreeHeader = new BTreeHeader();
setType( BTreeTypeEnum.IN_MEMORY );
}
@@ -97,9 +96,9 @@ import org.slf4j.LoggerFactory;
/* no qualifier */InMemoryBTree( InMemoryBTreeConfiguration<K, V> configuration )
{
super();
- String name = configuration.getName();
+ String btreeName = configuration.getName();
- if ( name == null )
+ if ( btreeName == null )
{
throw new IllegalArgumentException( "BTree name cannot be null" );
}
@@ -111,29 +110,35 @@ import org.slf4j.LoggerFactory;
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() );
+ // Store the configuration in the B-tree
+ setName( btreeName );
+ setPageSize( configuration.getPageSize() );
+ setKeySerializer( configuration.getKeySerializer() );
+ setValueSerializer( configuration.getValueSerializer() );
+ setAllowDuplicates( configuration.isAllowDuplicates() );
+ setType( configuration.getType() );
readTimeOut = configuration.getReadTimeOut();
writeBufferSize = configuration.getWriteBufferSize();
- btreeHeader.setAllowDuplicates( configuration.isAllowDuplicates() );
- setType( configuration.getType() );
if ( keySerializer.getComparator() == null )
{
throw new IllegalArgumentException( "Comparator should not be null" );
}
+ // Create the B-tree header
+ BTreeHeader<K, V> newBtreeHeader = new BTreeHeader<K, V>();
+
// Create the first root page, with revision 0L. It will be empty
// and increment the revision at the same time
- rootPage = new InMemoryLeaf<K, V>( this );
+ newBtreeHeader.setBTreeHeaderOffset( 0L );
+ newBtreeHeader.setRevision( 0L );
+ newBtreeHeader.setNbElems( 0L );
+ newBtreeHeader.setRootPage( new InMemoryLeaf<K, V>( this ) );
+ newBtreeHeader.setRootPageOffset( 0L );
+
+ btreeRevisions.put( 0L, newBtreeHeader );
+ currentBtreeHeader = newBtreeHeader;
// Now, initialize the BTree
try
@@ -152,7 +157,7 @@ import org.slf4j.LoggerFactory;
*
* @throws IOException If we get some exception while initializing the BTree
*/
- public void init() throws IOException
+ private void init() throws IOException
{
// if not in-memory then default to persist mode instead of managed
if ( envDir != null )
@@ -160,13 +165,14 @@ import org.slf4j.LoggerFactory;
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.file = new File( envDir, getName() + DATA_SUFFIX );
this.journal = new File( envDir, file.getName() + JOURNAL_SUFFIX );
setType( BTreeTypeEnum.BACKED_ON_DISK );
@@ -174,8 +180,9 @@ import org.slf4j.LoggerFactory;
// Create the queue containing the pending read transactions
readTransactions = new ConcurrentLinkedQueue<ReadTransaction<K, V>>();
-
- writeLock = new ReentrantLock();
+
+ // Create the transaction manager
+ transactionManager = new InMemoryTransactionManager();
// Check the files and create them if missing
// Create the queue containing the modifications, if it's not a in-memory btree
@@ -202,6 +209,12 @@ import org.slf4j.LoggerFactory;
else
{
setType( BTreeTypeEnum.IN_MEMORY );
+
+ // This is a new Btree, we have to store the BtreeHeader
+ BTreeHeader<K, V> btreeHeader = new BTreeHeader<K, V>();
+ btreeHeader.setRootPage( new InMemoryLeaf<K, V>( this ) );
+ btreeHeader.setBtree( this );
+ storeRevision( btreeHeader );
}
// Initialize the txnManager thread
@@ -211,6 +224,43 @@ import org.slf4j.LoggerFactory;
/**
+ * {@inheritDoc}
+ */
+ protected ReadTransaction<K, V> beginReadTransaction()
+ {
+ BTreeHeader<K, V> btreeHeader = getBtreeHeader();
+
+ ReadTransaction<K, V> readTransaction = new ReadTransaction<K, V>( btreeHeader, readTransactions );
+
+ readTransactions.add( readTransaction );
+
+ return readTransaction;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ protected ReadTransaction<K, V> beginReadTransaction( long revision )
+ {
+ BTreeHeader<K, V> btreeHeader = getBtreeHeader( revision );
+
+ if ( btreeHeader != null )
+ {
+ ReadTransaction<K, V> readTransaction = new ReadTransaction<K, V>( btreeHeader, readTransactions );
+
+ readTransactions.add( readTransaction );
+
+ return readTransaction;
+ }
+ else
+ {
+ return null;
+ }
+ }
+
+
+ /**
* Close the BTree, cleaning up all the data structure
*/
public void close() throws IOException
@@ -225,8 +275,6 @@ import org.slf4j.LoggerFactory;
flush();
journalChannel.close();
}
-
- rootPage = null;
}
@@ -244,59 +292,65 @@ import org.slf4j.LoggerFactory;
*/
protected Tuple<K, V> delete( K key, V value, long revision ) throws IOException
{
- writeLock.lock();
-
- try
+ if ( revision == -1L )
{
- // If the key exists, the existing value will be replaced. We store it
- // to return it to the caller.
- Tuple<K, V> tuple = null;
+ revision = currentRevision.get() + 1;
+ }
- // 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 );
+ BTreeHeader<K, V> oldBtreeHeader = getBtreeHeader();
+ BTreeHeader<K, V> newBtreeHeader = createNewBtreeHeader( oldBtreeHeader, revision );
+ newBtreeHeader.setBtree( this );
- if ( result instanceof NotPresentResult )
- {
- // Key not found.
- return null;
- }
+ // If the key exists, the existing value will be replaced. We store it
+ // to return it to the caller.
+ Tuple<K, V> tuple = null;
- // Keep the oldRootPage so that we can later access it
- Page<K, V> oldRootPage = rootPage;
+ // 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 = getRootPage().delete( key, value, revision );
- if ( result instanceof RemoveResult )
- {
- // The element was found, and removed
- RemoveResult<K, V> removeResult = ( RemoveResult<K, V> ) result;
+ if ( result instanceof NotPresentResult )
+ {
+ // Key not found.
+ return null;
+ }
- Page<K, V> modifiedPage = removeResult.getModifiedPage();
+ // Keep the oldRootPage so that we can later access it
+ //Page<K, V> oldRootPage = rootPage;
- // This is a new root
- rootPage = modifiedPage;
- tuple = removeResult.getRemovedElement();
- }
+ if ( result instanceof RemoveResult )
+ {
+ // The element was found, and removed
+ RemoveResult<K, V> removeResult = ( RemoveResult<K, V> ) result;
- if ( withJournal )
- {
- // Inject the modification into the modification queue
- writeToJournal( new Deletion<K, V>( key ) );
- }
+ Page<K, V> modifiedPage = removeResult.getModifiedPage();
- // Decrease the number of elements in the current tree if the deletion is successful
- if ( tuple != null )
- {
- btreeHeader.decrementNbElems();
- }
+ // This is a new root
+ newBtreeHeader.setRootPage( modifiedPage );
+ tuple = removeResult.getRemovedElement();
+ }
+
+ if ( withJournal )
+ {
+ // Inject the modification into the modification queue
+ writeToJournal( new Deletion<K, V>( key ) );
+ }
- // Return the value we have found if it was modified
- return tuple;
+ // Decrease the number of elements in the current tree if the deletion is successful
+ if ( tuple != null )
+ {
+ newBtreeHeader.decrementNbElems();
}
- finally
+
+ storeRevision( newBtreeHeader );
+
+ // Return the value we have found if it was modified
+ if ( oldBtreeHeader.getNbUsers() == 0 )
{
- // See above
- writeLock.unlock();
+ btreeRevisions.remove( oldBtreeHeader.getRevision() );
}
+
+ return tuple;
}
@@ -315,11 +369,17 @@ import org.slf4j.LoggerFactory;
*/
/* no qualifier */InsertResult<K, V> insert( K key, V value, long revision ) throws IOException
{
- if ( key == null )
+ // We have to start a new transaction, which will be committed or rollbacked
+ // locally. This will duplicate the current BtreeHeader during this phase.
+ if ( revision == -1L )
{
- throw new IllegalArgumentException( "Key must not be null" );
+ revision = currentRevision.get() + 1;
}
+ BTreeHeader<K, V> oldBtreeHeader = getBtreeHeader();
+ BTreeHeader<K, V> newBtreeHeader = createNewBtreeHeader( oldBtreeHeader, revision );
+ newBtreeHeader.setBtree( this );
+
// If the key exists, the existing value will be replaced. We store it
// to return it to the caller.
V modifiedValue = null;
@@ -327,7 +387,7 @@ import org.slf4j.LoggerFactory;
// 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 );
+ InsertResult<K, V> result = newBtreeHeader.getRootPage().insert( key, value, revision );
if ( result instanceof ModifyResult )
{
@@ -337,7 +397,7 @@ import org.slf4j.LoggerFactory;
// The root has just been modified, we haven't split it
// Get it and make it the current root page
- rootPage = modifiedPage;
+ newBtreeHeader.setRootPage( modifiedPage );
modifiedValue = modifyResult.getModifiedValue();
}
@@ -350,12 +410,9 @@ import org.slf4j.LoggerFactory;
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 InMemoryNode<K, V>( this, revision, pivot, leftPage, rightPage );
-
- rootPage = newRootPage;
+ newBtreeHeader.setRootPage( new InMemoryNode<K, V>( this, revision, pivot, leftPage, rightPage ) );
}
// Inject the modification into the modification queue
@@ -368,7 +425,19 @@ import org.slf4j.LoggerFactory;
// and does not replace an element
if ( modifiedValue == null )
{
- btreeHeader.incrementNbElems();
+ newBtreeHeader.incrementNbElems();
+ }
+
+ storeRevision( newBtreeHeader );
+
+ if ( oldBtreeHeader.getNbUsers() == 0 )
+ {
+ long oldRevision = oldBtreeHeader.getRevision();
+
+ if ( oldRevision < newBtreeHeader.getRevision() )
+ {
+ btreeRevisions.remove( oldBtreeHeader.getRevision() );
+ }
}
// Return the value we have found if it was modified
@@ -443,45 +512,53 @@ import org.slf4j.LoggerFactory;
// Create a buffer containing 200 4Kb pages (around 1Mb)
ByteBuffer bb = ByteBuffer.allocateDirect( writeBufferSize );
- TupleCursor<K, V> cursor = browse();
-
- if ( keySerializer == null )
- {
- throw new MissingSerializerException( "Cannot flush the btree without a Key serializer" );
- }
-
- if ( valueSerializer == null )
- {
- throw new MissingSerializerException( "Cannot flush the btree without a Value serializer" );
- }
-
- // Write the number of elements first
- bb.putLong( btreeHeader.getNbElems() );
-
- while ( cursor.hasNext() )
+ try
{
- 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 );
+ TupleCursor<K, V> cursor = browse();
+
+ if ( keySerializer == null )
+ {
+ throw new MissingSerializerException( "Cannot flush the btree without a Key serializer" );
+ }
+
+ if ( valueSerializer == null )
+ {
+ throw new MissingSerializerException( "Cannot flush the btree without a Value serializer" );
+ }
+
+ // Write the number of elements first
+ bb.putLong( getBtreeHeader().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();
}
-
- // Write the buffer if needed
- if ( bb.position() > 0 )
+ catch ( KeyNotFoundException knfe )
{
- bb.flip();
- ch.write( bb );
+ knfe.printStackTrace();
+ throw new IOException( knfe.getMessage() );
}
- // 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 );
@@ -501,8 +578,6 @@ import org.slf4j.LoggerFactory;
*/
private void applyJournal() throws IOException
{
- long revision = generateRevision();
-
if ( !journal.exists() )
{
throw new IOException( "The journal does not exist" );
@@ -535,7 +610,7 @@ import org.slf4j.LoggerFactory;
//values.add( value );
// Inject the data in the tree. (to be replaced by a bulk load)
- insert( key, value, revision );
+ insert( key, value, getBtreeHeader().getRevision() );
}
else
{
@@ -543,7 +618,7 @@ import org.slf4j.LoggerFactory;
K key = keySerializer.deserialize( bufferHandler );
// Remove the key from the tree
- delete( key, revision );
+ delete( key, getBtreeHeader().getRevision() );
}
}
}
@@ -565,8 +640,6 @@ import org.slf4j.LoggerFactory;
*/
public void load( File file ) throws IOException
{
- long revision = generateRevision();
-
if ( !file.exists() )
{
throw new IOException( "The file does not exist" );
@@ -579,11 +652,6 @@ import org.slf4j.LoggerFactory;
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;
@@ -596,15 +664,11 @@ import org.slf4j.LoggerFactory;
// 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 );
+ insert( key, value, getBtreeHeader().getRevision() );
}
// Restore the withJournal value
@@ -616,7 +680,7 @@ import org.slf4j.LoggerFactory;
/**
- * Get the rootPzge associated to a give revision.
+ * Get the rootPage associated to a give revision.
*
* @param revision The revision we are looking for
* @return The rootPage associated to this revision
@@ -626,7 +690,24 @@ import org.slf4j.LoggerFactory;
public Page<K, V> getRootPage( long revision ) throws IOException, KeyNotFoundException
{
// Atm, the in-memory BTree does not support searches in many revisions
- return rootPage;
+ return getBtreeHeader().getRootPage();
+ }
+
+
+ /**
+ * Get the current rootPage
+ *
+ * @return The rootPage
+ */
+ public Page<K, V> getRootPage()
+ {
+ return getBtreeHeader().getRootPage();
+ }
+
+
+ /* no qualifier */void setRootPage( Page<K, V> root )
+ {
+ getBtreeHeader().setRootPage( root );
}
@@ -718,29 +799,19 @@ import org.slf4j.LoggerFactory;
/**
- * Starts a transaction
- */
- public void beginTransaction()
- {
- // Does nothing...
- }
-
-
- /**
- * Commits a transaction
+ * Create a new B-tree header to be used for update operations
+ * @param revision The reclaimed revision
*/
- public void commit()
+ private BTreeHeader<K, V> createNewBtreeHeader( BTreeHeader<K, V> btreeHeader, long revision )
{
- // Does nothing...
- }
+ BTreeHeader<K, V> newBtreeHeader = new BTreeHeader<K, V>();
+ newBtreeHeader.setBTreeHeaderOffset( btreeHeader.getBTreeHeaderOffset() );
+ newBtreeHeader.setRevision( revision );
+ newBtreeHeader.setNbElems( btreeHeader.getNbElems() );
+ newBtreeHeader.setRootPage( btreeHeader.getRootPage() );
- /**
- * Rollback a transaction
- */
- public void rollback()
- {
- // Does nothing...
+ return newBtreeHeader;
}
@@ -760,16 +831,19 @@ import org.slf4j.LoggerFactory;
case BACKED_ON_DISK:
sb.append( "Persistent " );
break;
-
+
+ default :
+ sb.append( "Wrong type... " );
+ break;
}
sb.append( "BTree" );
- sb.append( "[" ).append( btreeHeader.getName() ).append( "]" );
- sb.append( "( pageSize:" ).append( btreeHeader.getPageSize() );
+ sb.append( "[" ).append( getName() ).append( "]" );
+ sb.append( "( pageSize:" ).append( getPageSize() );
- if ( rootPage != null )
+ if ( getBtreeHeader().getRootPage() != null )
{
- sb.append( ", nbEntries:" ).append( btreeHeader.getNbElems() );
+ sb.append( ", nbEntries:" ).append( getBtreeHeader().getNbElems() );
}
else
{
@@ -787,7 +861,7 @@ import org.slf4j.LoggerFactory;
sb.append( keySerializer.getComparator().getClass().getSimpleName() );
}
- sb.append( ", DuplicatesAllowed: " ).append( btreeHeader.isAllowDuplicates() );
+ sb.append( ", DuplicatesAllowed: " ).append( isAllowDuplicates() );
if ( getType() == BTreeTypeEnum.BACKED_ON_DISK )
{
@@ -822,7 +896,7 @@ import org.slf4j.LoggerFactory;
}
sb.append( ") : \n" );
- sb.append( rootPage.dumpPage( "" ) );
+ sb.append( getRootPage().dumpPage( "" ) );
return sb.toString();
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java?rev=1595477&r1=1595476&r2=1595477&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryLeaf.java Sat May 17 13:31:23 2014
@@ -27,7 +27,6 @@ import org.apache.directory.mavibot.btre
import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
-
/**
* A MVCC Leaf. It stores the keys and values. It does not have any children.
*
@@ -72,7 +71,7 @@ import org.apache.directory.mavibot.btre
/**
* {@inheritDoc}
*/
- public InsertResult<K, V> insert( long revision, K key, V value ) throws IOException
+ public InsertResult<K, V> insert( K key, V value, long revision ) throws IOException
{
// Find the key into this leaf
int pos = findPos( key );
@@ -117,7 +116,7 @@ import org.apache.directory.mavibot.btre
* {@inheritDoc}
*/
@SuppressWarnings("unchecked")
- public DeleteResult<K, V> delete( long revision, K key, V value, Page<K, V> parent, int parentPos )
+ /* no qualifier */ DeleteResult<K, V> delete( K key, V value, long revision, Page<K, V> parent, int parentPos )
throws IOException
{
// Check that the leaf is not empty
@@ -486,7 +485,7 @@ import org.apache.directory.mavibot.btre
}
else
{
- throw KEY_NOT_FOUND_EXCEPTION;
+ throw KeyNotFoundException.INSTANCE;
}
}
@@ -512,7 +511,7 @@ import org.apache.directory.mavibot.btre
}
else
{
- throw KEY_NOT_FOUND_EXCEPTION;
+ throw KeyNotFoundException.INSTANCE;
}
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryNode.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryNode.java?rev=1595477&r1=1595476&r2=1595477&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryNode.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryNode.java Sat May 17 13:31:23 2014
@@ -28,7 +28,7 @@ import java.util.List;
/**
* A MVCC Node. It stores the keys and references to its children page. It does not
* contain any value.
- *
+ *
* @param <K> The type for the Key
* @param <V> The type for the stored value
*
@@ -40,7 +40,7 @@ import java.util.List;
* Creates a new Node which will contain only one key, with references to
* a left and right page. This is a specific constructor used by the btree
* when the root was full when we added a new value.
- *
+ *
* @param btree the parent BTree
* @param revision the Node revision
* @param nbElems The number of elements in this Node
@@ -59,7 +59,7 @@ import java.util.List;
* Creates a new Node which will contain only one key, with references to
* a left and right page. This is a specific constructor used by the btree
* when the root was full when we added a new value.
- *
+ *
* @param btree the parent BTree
* @param revision the Node revision
* @param key The new key
@@ -89,7 +89,7 @@ import java.util.List;
/**
* {@inheritDoc}
*/
- public InsertResult<K, V> insert( long revision, K key, V value ) throws IOException
+ public InsertResult<K, V> insert( K key, V value, long revision ) throws IOException
{
// Find the key into this leaf
int pos = findPos( key );
@@ -105,7 +105,7 @@ import java.util.List;
Page<K, V> child = children[pos].getValue();
// and insert the <K, V> into this child
- InsertResult<K, V> result = child.insert( revision, key, value );
+ InsertResult<K, V> result = child.insert( key, value, revision );
// Ok, now, we have injected the <K, V> tuple down the tree. Let's check
// the result to see if we have to split the current page
@@ -145,7 +145,7 @@ import java.util.List;
/**
* Modifies the current node after a remove has been done in one of its children.
* The node won't be merged with another node.
- *
+ *
* @param removeResult The result of a remove operation
* @param index the position of the key, not transformed
* @param pos The position of the key, as a positive value
@@ -188,7 +188,7 @@ import java.util.List;
/**
* Handles the removal of an element from the root page, when two of its children
* have been merged.
- *
+ *
* @param mergedResult The merge result
* @param pos The position in the current root
* @param found Tells if the removed key is present in the root page
@@ -223,7 +223,7 @@ import java.util.List;
* Borrows an element from the right sibling, creating a new sibling with one
* less element and creating a new page where the element to remove has been
* deleted and the borrowed element added on the right.
- *
+ *
* @param revision The new revision for all the pages
* @param sibling The right sibling
* @param pos The position of the element to remove
@@ -308,7 +308,7 @@ import java.util.List;
* Borrows an element from the left sibling, creating a new sibling with one
* less element and creating a new page where the element to remove has been
* deleted and the borrowed element added on the left.
- *
+ *
* @param revision The new revision for all the pages
* @param sibling The left sibling
* @param pos The position of the element to remove
@@ -392,7 +392,7 @@ import java.util.List;
/**
* We have to merge the node with its sibling, both have N/2 elements before the element
* removal.
- *
+ *
* @param revision The revision
* @param mergedResult The result of the merge
* @param sibling The Page we will merge the current page with
@@ -523,7 +523,7 @@ import java.util.List;
/**
* {@inheritDoc}
*/
- public DeleteResult<K, V> delete( long revision, K key, V value, Page<K, V> parent, int parentPos )
+ /* no qualifier */ DeleteResult<K, V> delete( K key, V value, long revision, Page<K, V> parent, int parentPos )
throws IOException
{
// We first try to delete the element from the child it belongs to
@@ -538,12 +538,12 @@ import java.util.List;
{
index = -( pos + 1 );
child = children[-pos].getValue();
- deleteResult = child.delete( revision, key, value, this, -pos );
+ deleteResult = ((AbstractPage<K, V>)child).delete( key, value, revision, this, -pos );
}
else
{
child = children[pos].getValue();
- deleteResult = child.delete( revision, key, value, this, pos );
+ deleteResult = ((AbstractPage<K, V>)child).delete( key, value, revision, this, pos );
}
// If the key is not present in the tree, we simply return
@@ -604,7 +604,7 @@ import java.util.List;
// We will remove one element from a page that will have less than N/2 elements,
// which will lead to some reorganization : either we can borrow an element from
// a sibling, or we will have to merge two pages
- int siblingPos = selectSibling( ( InMemoryNode<K, V> ) parent, parentPos );
+ int siblingPos = selectSibling( parent, parentPos );
InMemoryNode<K, V> sibling = ( InMemoryNode<K, V> ) ( ( ( InMemoryNode<K, V> ) parent ).children[siblingPos]
.getValue() );
@@ -717,7 +717,7 @@ import java.util.List;
/**
* Remove the key at a given position.
- *
+ *
* @param mergedResult The page we will remove a key from
* @param revision The revision of the modified page
* @param pos The position into the page of the element to remove
@@ -780,7 +780,7 @@ import java.util.List;
/**
* Set the value at a give position
- *
+ *
* @param pos The position in the values array
* @param value the value to inject
*/
@@ -794,7 +794,7 @@ import java.util.List;
* This method is used when we have to replace a child in a page when we have
* found the key in the tree (the value will be changed, so we have made
* copies of the existing pages).
- *
+ *
* @param revision The current revision
* @param result The modified page
* @param pos The position of the found key
@@ -825,7 +825,7 @@ import java.util.List;
/**
* Adds a new key into a copy of the current page at a given position. We return the
* modified page. The new page will have one more key than the current page.
- *
+ *
* @param copiedPages the list of copied pages
* @param revision The revision of the modified page
* @param key The key to insert
@@ -880,7 +880,7 @@ import java.util.List;
* If the newly added element is in the middle, we will use it
* as a pivot. Otherwise, we will use either the last element in the left page if the element is added
* on the left, or the first element in the right page if it's added on the right.
- *
+ *
* @param copiedPages the list of copied pages
* @param revision The new revision for all the created pages
* @param pivot The key that will be move up after the split
@@ -978,7 +978,7 @@ import java.util.List;
/**
* Copies the current page and all its keys, with a new revision.
- *
+ *
* @param revision The new revision
* @return The copied page
*/
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryValueHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryValueHolder.java?rev=1595477&r1=1595476&r2=1595477&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryValueHolder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryValueHolder.java Sat May 17 13:31:23 2014
@@ -27,6 +27,7 @@ import java.util.UUID;
import org.apache.directory.mavibot.btree.exception.BTreeOperationException;
import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
+import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
/**
@@ -201,6 +202,10 @@ import org.apache.directory.mavibot.btre
{
throw new BTreeOperationException( e );
}
+ catch ( KeyNotFoundException knfe )
+ {
+ throw new BTreeOperationException( knfe );
+ }
}
return returnedValue;
@@ -249,6 +254,12 @@ import org.apache.directory.mavibot.btre
e.printStackTrace();
return false;
}
+ catch ( KeyNotFoundException knfe )
+ {
+ // TODO Auto-generated catch block
+ knfe.printStackTrace();
+ return false;
+ }
}
else
{
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/NameRevisionComparator.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/NameRevisionComparator.java?rev=1595477&r1=1595476&r2=1595477&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/NameRevisionComparator.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/NameRevisionComparator.java Sat May 17 13:31:23 2014
@@ -30,6 +30,17 @@ import java.util.Comparator;
*/
/* no qualifier*/class NameRevisionComparator implements Comparator<NameRevision>
{
+ /** A static instance of a NameRevisionComparator */
+ public static final NameRevisionComparator INSTANCE = new NameRevisionComparator();
+
+ /**
+ * A private constructor of the NameRevisionComparator class
+ */
+ private NameRevisionComparator()
+ {
+ }
+
+
/**
* {@inheritDoc}
*/
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/NameRevisionSerializer.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/NameRevisionSerializer.java?rev=1595477&r1=1595476&r2=1595477&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/NameRevisionSerializer.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/NameRevisionSerializer.java Sat May 17 13:31:23 2014
@@ -41,12 +41,15 @@ import org.apache.directory.mavibot.btre
*/
/* no qualifier*/class NameRevisionSerializer extends AbstractElementSerializer<NameRevision>
{
+ /** A static instance of a NameRevisionSerializer */
+ /*No qualifier*/ final static NameRevisionSerializer INSTANCE = new NameRevisionSerializer();
+
/**
* Create a new instance of a NameRevisionSerializer
*/
- /* no qualifier*/NameRevisionSerializer()
+ private NameRevisionSerializer()
{
- super( new NameRevisionComparator() );
+ super( NameRevisionComparator.INSTANCE );
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java?rev=1595477&r1=1595476&r2=1595477&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java Sat May 17 13:31:23 2014
@@ -31,7 +31,7 @@ import org.apache.directory.mavibot.btre
* (containing keys and references to child pages).<br/>
* A Page can be stored on disk. If so, we store the serialized value of this Page into
* one or more {@link PageIO} (they will be linked)
- *
+ *
* @param <K> The type for the Key
* @param <V> The type for the stored value
*
@@ -56,22 +56,22 @@ import org.apache.directory.mavibot.btre
* the Page is full, we split it and propagate the new pivot up into the tree</li>
* </ul>
* <p>
- *
- * @param revision The new revision for the modified pages
+ *
* @param key Inserted key
* @param value Inserted value
+ * @param revision The new revision for the modified pages
* @return Either a modified Page or an Overflow element if the Page was full
* @throws IOException If we have an error while trying to access the page
*/
- InsertResult<K, V> insert( long revision, K key, V value ) throws IOException;
+ InsertResult<K, V> insert( K key, V value, long revision ) throws IOException;
/**
- * Deletes the value from an entry associated with the given key in this page. We first find
+ * Deletes the value from an entry associated with the given key in this page. We first find
* the place were to remove the <K,V> into the tree, by recursively browsing the pages.
- * If the value is present, it will be deleted first, later if there are no other values associated with
+ * 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 revision The new revision for the modified pages
* @param key The key to delete
* @param value The value to delete (can be null)
@@ -80,15 +80,15 @@ import org.apache.directory.mavibot.btre
* @return Either a modified Page if the key has been removed from the page, or a NotPresentResult.
* @throws IOException If we have an error while trying to access the page
*/
- DeleteResult<K, V> delete( long revision, K key, V value, Page<K, V> parent, int parentPos ) throws IOException;
+ DeleteResult<K, V> delete( K key, V value, long revision /*, Page<K, V> parent, int parentPos*/ ) throws IOException;
/**
- * Gets the value associated with the given key, if any. If we don't have
+ * Gets the value associated with the given key, if any. If we don't have
* one, this method will throw a KeyNotFoundException.<br/>
- * Note that we may get back null if a null value has been associated
+ * Note that we may get back null if a null value has been associated
* with the key.
- *
+ *
* @param key The key we are looking for
* @return The associated value, which can be null
* @throws KeyNotFoundException If no entry with the given key can be found
@@ -98,23 +98,23 @@ import org.apache.directory.mavibot.btre
/**
- * Gets the values associated with the given key, if any. If we don't have
+ * Gets the values associated with the given key, if any. If we don't have
* the key, this method will throw a KeyNotFoundException.<br/>
- * Note that we may get back null if a null value has been associated
+ * Note that we may get back null if a null value has been associated
* with the key.
- *
+ *
* @param key The key we are looking for
* @return The associated value, which can be null
* @throws KeyNotFoundException If no entry with the given key can be found
* @throws IOException If we have an error while trying to access the page
- * @throws IllegalArgumentException If duplicates are not enabled
+ * @throws IllegalArgumentException If duplicates are not enabled
*/
ValueCursor<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException;
/**
* Checks if the page 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
@@ -125,7 +125,7 @@ import org.apache.directory.mavibot.btre
/**
* Browses the tree, looking for the given key, and creates a Cursor on top
* of the found result.
- *
+ *
* @param key The key we are looking for.
* @param transaction The started transaction for this operation
* @param stack The stack of parents we go through to get to this page
@@ -138,7 +138,7 @@ import org.apache.directory.mavibot.btre
/**
* Browses the whole tree, and creates a Cursor on top of it.
- *
+ *
* @param transaction The started transaction for this operation
* @param stack The stack of parents we go through to get to this page
* @return A Cursor to browse the next elements
@@ -156,7 +156,7 @@ import org.apache.directory.mavibot.btre
/**
* Returns the key at a given position
- *
+ *
* @param pos The position of the key we want to retrieve
* @return The key found at the given position
*/
@@ -166,7 +166,7 @@ import org.apache.directory.mavibot.btre
/**
* Finds the leftmost key in this page. If the page is a node, it will go
* down in the leftmost children to recursively find the leftmost key.
- *
+ *
* @return The leftmost key in the tree
*/
K getLeftMostKey();
@@ -175,7 +175,7 @@ import org.apache.directory.mavibot.btre
/**
* Finds the rightmost key in this page. If the page is a node, it will go
* down in the rightmost children to recursively find the rightmost key.
- *
+ *
* @return The rightmost key in the tree
*/
K getRightMostKey();
@@ -184,7 +184,7 @@ import org.apache.directory.mavibot.btre
/**
* Finds the leftmost element in this page. If the page is a node, it will go
* down in the leftmost children to recursively find the leftmost element.
- *
+ *
* @return The leftmost element in the tree
* @throws IOException If we have an error while trying to access the page
*/
@@ -194,7 +194,7 @@ import org.apache.directory.mavibot.btre
/**
* Finds the rightmost element in this page. If the page is a node, it will go
* down in the rightmost children to recursively find the rightmost element.
- *
+ *
* @return The rightmost element in the tree
* @throws IOException If we have an error while trying to access the page
*/
@@ -240,8 +240,8 @@ import org.apache.directory.mavibot.btre
* <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.
*/
@@ -250,7 +250,7 @@ import org.apache.directory.mavibot.btre
/**
* 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