directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kayyag...@apache.org
Subject svn commit: r1643645 [1/2] - in /directory/mavibot/branches/free-page-mgmt: ./ distribution/ mavibot/ mavibot/src/main/java/org/apache/directory/mavibot/btree/ mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/ mavibot/src/test/java/o...
Date Sun, 07 Dec 2014 03:28:54 GMT
Author: kayyagari
Date: Sun Dec  7 03:28:54 2014
New Revision: 1643645

URL: http://svn.apache.org/r1643645
Log:
merged with trunk revision 1642979
(stashing a lot of untested code as well)


Modified:
    directory/mavibot/branches/free-page-mgmt/distribution/pom.xml
    directory/mavibot/branches/free-page-mgmt/mavibot/pom.xml
    directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java
    directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java
    directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java
    directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeFactory.java
    directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java
    directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilder.java
    directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyHolder.java
    directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java
    directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java
    directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java
    directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java
    directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/SpaceReclaimer.java
    directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/Tuple.java
    directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java
    directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/AbstractElementSerializer.java
    directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilderTest.java
    directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBrowseTest.java
    directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBuilderTest.java
    directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeDuplicateKeyTest.java
    directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/RecordManagerTest.java
    directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/RecordManagerWithDuplicatesTest.java
    directory/mavibot/branches/free-page-mgmt/pom.xml

Modified: directory/mavibot/branches/free-page-mgmt/distribution/pom.xml
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/distribution/pom.xml?rev=1643645&r1=1643644&r2=1643645&view=diff
==============================================================================
--- directory/mavibot/branches/free-page-mgmt/distribution/pom.xml (original)
+++ directory/mavibot/branches/free-page-mgmt/distribution/pom.xml Sun Dec  7 03:28:54 2014
@@ -24,7 +24,7 @@
   <parent>
     <groupId>org.apache.directory.mavibot</groupId>
     <artifactId>mavibot-parent</artifactId>
-    <version>1.0.0-M6-SNAPSHOT</version>
+    <version>1.0.0-M7-SNAPSHOT</version>
   </parent>
  
   <artifactId>distribution</artifactId>

Modified: directory/mavibot/branches/free-page-mgmt/mavibot/pom.xml
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/pom.xml?rev=1643645&r1=1643644&r2=1643645&view=diff
==============================================================================
--- directory/mavibot/branches/free-page-mgmt/mavibot/pom.xml (original)
+++ directory/mavibot/branches/free-page-mgmt/mavibot/pom.xml Sun Dec  7 03:28:54 2014
@@ -23,12 +23,12 @@
   <parent>
     <groupId>org.apache.directory.mavibot</groupId>
     <artifactId>mavibot-parent</artifactId>
-    <version>1.0.0-M6-SNAPSHOT</version>
+    <version>1.0.0-M7-SNAPSHOT</version>
   </parent>
 
   <artifactId>mavibot</artifactId>
   <name>ApacheDS MVCC BTree implementation</name>
-  <packaging>jar</packaging>
+  <packaging>bundle</packaging>
 
   <description>A MVCC BTree Implementation</description>
 
@@ -65,12 +65,44 @@
       <artifactId>slf4j-log4j12</artifactId>
       <version>${slf4j.log4j12.version}</version>
     </dependency>
+  </dependencies>
+  
+  <build>
+    <plugins>
+      <plugin>
+        <groupId>org.apache.maven.plugins</groupId>
+        <artifactId>maven-jar-plugin</artifactId>
+        <configuration>
+          <archive>
+            <manifestFile>META-INF/MANIFEST.MF</manifestFile>
+            <addMavenDescriptor>false</addMavenDescriptor>
+          </archive>
+        </configuration>
+      </plugin>
+      
+      <plugin>
+        <groupId>org.apache.felix</groupId>
+        <artifactId>maven-bundle-plugin</artifactId>
+        <inherited>true</inherited>
+        <extensions>true</extensions>
+        <configuration>
+          <manifestLocation>META-INF</manifestLocation>
+          <instructions>
+            <Bundle-SymbolicName>${project.groupId}.mavibot</Bundle-SymbolicName>
+            <Export-Package>
+              org.apache.directory.mavibot.btree;version=${project.version};-noimport:=true,
+              org.apache.directory.mavibot.btree.comparator;version=${project.version};-noimport:=true,
+              org.apache.directory.mavibot.btree.exception;version=${project.version};-noimport:=true,
+              org.apache.directory.mavibot.btree.memory;version=${project.version};-noimport:=true,
+              org.apache.directory.mavibot.btree.persisted;version=${project.version};-noimport:=true,
+              org.apache.directory.mavibot.btree.serializer;version=${project.version};-noimport:=true,
+              org.apache.directory.mavibot.btree.util;version=${project.version};-noimport:=true
+            </Export-Package>
+          </instructions>
+        </configuration>
+      </plugin>
 
-    <dependency>
-      <groupId>log4j</groupId>
-      <artifactId>log4j</artifactId>
-      <version>${log4j.version}</version>
-    </dependency>
-  </dependencies>  
+    </plugins>
+  </build>
 </project>
 

Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java?rev=1643645&r1=1643644&r2=1643645&view=diff
==============================================================================
--- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java (original)
+++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractBTree.java Sun Dec  7 03:28:54 2014
@@ -93,10 +93,11 @@ import org.apache.directory.mavibot.btre
 
     /** The current revision */
     protected AtomicLong currentRevision = new AtomicLong( 0L );
-    
+
     /** The TransactionManager used for this BTree */
     protected TransactionManager transactionManager;
 
+
     /**
      * Starts a Read Only transaction. If the transaction is not closed, it will be
      * automatically closed after the timeout
@@ -125,7 +126,7 @@ import org.apache.directory.mavibot.btre
         {
             throw new BTreeCreationException( "We don't have a transactionLManager" );
         }
-        
+
         ReadTransaction<K, V> transaction = beginReadTransaction();
 
         if ( transaction == null )
@@ -134,7 +135,7 @@ import org.apache.directory.mavibot.btre
         }
         else
         {
-            ParentPos<K, V>[] stack = (ParentPos<K, V>[]) Array.newInstance( ParentPos.class, 32 );
+            ParentPos<K, V>[] stack = ( ParentPos<K, V>[] ) Array.newInstance( ParentPos.class, 32 );
 
             TupleCursor<K, V> cursor = getRootPage().browse( transaction, stack, 0 );
 
@@ -165,7 +166,7 @@ import org.apache.directory.mavibot.btre
         }
         else
         {
-            ParentPos<K, V>[] stack = (ParentPos<K, V>[]) Array.newInstance( ParentPos.class, 32 );
+            ParentPos<K, V>[] stack = ( ParentPos<K, V>[] ) Array.newInstance( ParentPos.class, 32 );
 
             // And get the cursor
             TupleCursor<K, V> cursor = getRootPage( transaction.getRevision() ).browse( transaction, stack, 0 );
@@ -188,13 +189,13 @@ import org.apache.directory.mavibot.btre
 
         ReadTransaction<K, V> transaction = beginReadTransaction();
 
-        ParentPos<K, V>[] stack = (ParentPos<K, V>[]) Array.newInstance( ParentPos.class, 32 );
+        ParentPos<K, V>[] stack = ( ParentPos<K, V>[] ) Array.newInstance( ParentPos.class, 32 );
 
         TupleCursor<K, V> cursor;
         try
         {
             cursor = getRootPage( transaction.getRevision() ).browse( key, transaction, stack, 0 );
-            
+
             return cursor;
         }
         catch ( KeyNotFoundException e )
@@ -223,7 +224,7 @@ import org.apache.directory.mavibot.btre
         }
         else
         {
-            ParentPos<K, V>[] stack = (ParentPos<K, V>[]) Array.newInstance( ParentPos.class, 32 );
+            ParentPos<K, V>[] stack = ( ParentPos<K, V>[] ) Array.newInstance( ParentPos.class, 32 );
 
             // And get the cursor
             TupleCursor<K, V> cursor = getRootPage( transaction.getRevision() ).browse( key, transaction, stack, 0 );
@@ -316,22 +317,33 @@ import org.apache.directory.mavibot.btre
             throw new IllegalArgumentException( "Key must not be null" );
         }
 
-        // Take the lock if it's not already taken by another thread
-        transactionManager.beginTransaction();
+        boolean txnAllowed = ( ( btreeType != BTreeTypeEnum.PERSISTED_SUB ) && ( btreeType != BTreeTypeEnum.BTREE_OF_BTREES ) );
+        
+        if ( txnAllowed )
+        {
+            // Take the lock if it's not already taken by another thread
+            transactionManager.beginTransaction();
+        }
 
         try
         {
             Tuple<K, V> deleted = delete( key, currentRevision.get() + 1 );
 
-            // Commit now
-            transactionManager.commit();
+            if ( txnAllowed )
+            {
+                // Commit now
+                transactionManager.commit();
+            }
 
             return deleted;
         }
         catch ( IOException ioe )
         {
-            // We have had an exception, we must rollback the transaction
-            transactionManager.rollback();
+            if ( txnAllowed )
+            {
+                // We have had an exception, we must rollback the transaction
+                transactionManager.rollback();
+            }
             
             return null;
         }
@@ -359,19 +371,30 @@ import org.apache.directory.mavibot.btre
             throw new IllegalArgumentException( "Value must not be null" );
         }
 
-        transactionManager.beginTransaction();
-
+        boolean txnAllowed = ( ( btreeType != BTreeTypeEnum.PERSISTED_SUB ) && ( btreeType != BTreeTypeEnum.BTREE_OF_BTREES ) );
+        
+        if ( txnAllowed )
+        {
+            transactionManager.beginTransaction();
+        }
+        
         try
         {
             Tuple<K, V> deleted = delete( key, value, currentRevision.get() + 1 );
-            
-            transactionManager.commit();
+        
+            if ( txnAllowed )
+            {
+                transactionManager.commit();
+            }
     
             return deleted;
         }
         catch ( IOException ioe )
         {
-            transactionManager.rollback();
+            if ( txnAllowed )
+            {
+                transactionManager.rollback();
+            }
             
             throw ioe;
         }
@@ -412,9 +435,11 @@ import org.apache.directory.mavibot.btre
             throw new IllegalArgumentException( "Key must not be null" );
         }
 
+        boolean txnAllowed = ( ( btreeType != BTreeTypeEnum.PERSISTED_SUB ) && ( btreeType != BTreeTypeEnum.BTREE_OF_BTREES ) );
+        
         // Take the lock if it's not already taken by another thread and if we 
         // aren't on a sub-btree
-        if ( btreeType != BTreeTypeEnum.PERSISTED_SUB )
+        if ( txnAllowed )
         {
             transactionManager.beginTransaction();
         }
@@ -433,7 +458,7 @@ import org.apache.directory.mavibot.btre
             }
             
             // Commit now if it's not a sub-btree
-            if ( btreeType != BTreeTypeEnum.PERSISTED_SUB )
+            if ( txnAllowed )
             {
                 //FIXME when result type is ExistsResult then we should avoid writing the headers
                 transactionManager.commit();
@@ -445,7 +470,7 @@ import org.apache.directory.mavibot.btre
         {
             // We have had an exception, we must rollback the transaction
             // if it's not a sub-btree
-            if ( btreeType != BTreeTypeEnum.PERSISTED_SUB )
+            if ( txnAllowed )
             {
                 transactionManager.rollback();
             }
@@ -456,7 +481,7 @@ import org.apache.directory.mavibot.btre
         {
             // We have had an exception, we must rollback the transaction
             // if it's not a sub-btree
-            if ( btreeType != BTreeTypeEnum.PERSISTED_SUB )
+            if ( txnAllowed )
             {
                 transactionManager.rollback();
             }
@@ -771,7 +796,7 @@ import org.apache.directory.mavibot.btre
 
         currentRevision.set( revision );
         currentBtreeHeader = btreeHeader;
-        
+
         // And update the newBTreeHeaders map
         if ( btreeHeader.getBtree().getType() != BTreeTypeEnum.PERSISTED_SUB )
         {
@@ -794,7 +819,7 @@ import org.apache.directory.mavibot.btre
 
         currentRevision.set( revision );
         currentBtreeHeader = btreeHeader;
-        
+
         // And update the newBTreeHeaders map
         if ( btreeHeader.getBtree().getType() != BTreeTypeEnum.PERSISTED_SUB )
         {
@@ -907,7 +932,7 @@ import org.apache.directory.mavibot.btre
     /**
      * {@inheritDoc}
      */
-    public Comparator<K> getComparator()
+    public Comparator<K> getKeyComparator()
     {
         return keySerializer.getComparator();
     }
@@ -916,6 +941,15 @@ import org.apache.directory.mavibot.btre
     /**
      * {@inheritDoc}
      */
+    public Comparator<V> getValueComparator()
+    {
+        return valueSerializer.getComparator();
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
     public int getWriteBufferSize()
     {
         return writeBufferSize;
@@ -1012,7 +1046,7 @@ import org.apache.directory.mavibot.btre
         {
             throw new BTreeCreationException( "We don't have a Transaction Manager" );
         }
-        
+
         ReadTransaction transaction = beginReadTransaction();
 
         if ( transaction == null )
@@ -1021,7 +1055,7 @@ import org.apache.directory.mavibot.btre
         }
         else
         {
-            ParentPos<K, K>[] stack = (ParentPos<K, K>[]) Array.newInstance( ParentPos.class, 32 );
+            ParentPos<K, K>[] stack = ( ParentPos<K, K>[] ) Array.newInstance( ParentPos.class, 32 );
 
             KeyCursor<K> cursor = getRootPage().browseKeys( transaction, stack, 0 );
 
@@ -1032,7 +1066,7 @@ import org.apache.directory.mavibot.btre
         }
     }
 
-    
+
     /**
      * Create a thread that is responsible of cleaning the transactions when
      * they hit the timeout

Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java?rev=1643645&r1=1643644&r2=1643645&view=diff
==============================================================================
--- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java (original)
+++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/AbstractPage.java Sun Dec  7 03:28:54 2014
@@ -59,6 +59,7 @@ import org.apache.directory.mavibot.btre
     /** The last {@link PageIO} storing the serialized Page on disk */
     protected long lastOffset = -1L;
 
+
     /**
      * Creates a default empty AbstractPage
      *
@@ -155,7 +156,14 @@ import org.apache.directory.mavibot.btre
     {
         if ( pos < nbElems + 1 )
         {
-            return children[pos].getValue();
+            if ( children[pos] != null )
+            {
+                return children[pos].getValue();
+            }
+            else
+            {
+                return null;
+            }
         }
         else
         {
@@ -227,7 +235,8 @@ import org.apache.directory.mavibot.btre
      * @return The result
      * @throws IOException If we had an issue while processing the deletion
      */
-    /* no qualifier */abstract DeleteResult<K, V> delete( K key, V value, long revision, Page<K, V> parent, int parentPos )
+    /* no qualifier */abstract DeleteResult<K, V> delete( K key, V value, long revision, Page<K, V> parent,
+        int parentPos )
         throws IOException;
 
 
@@ -258,7 +267,14 @@ import org.apache.directory.mavibot.btre
     {
         if ( ( pos >= 0 ) && ( pos < children.length ) )
         {
-            return children[pos].getValue();
+            if ( children[pos] != null )
+            {
+                return children[pos].getValue();
+            }
+            else
+            {
+                return null;
+            }
         }
         else
         {
@@ -268,7 +284,10 @@ import org.apache.directory.mavibot.btre
 
 
     /**
-     * {@inheritDoc}
+     * Inject a pageHolder into the node, at a given position
+     * 
+     * @param pos The position of the added pageHolder
+     * @param pageHolder The pageHolder to add
      */
     /* no qualifier */void setPageHolder( int pos, PageHolder<K, V> pageHolder )
     {
@@ -327,7 +346,7 @@ import org.apache.directory.mavibot.btre
         return page.browseKeys( transaction, stack, depth );
     }
 
-    
+
     /**
      * Selects the sibling (the previous or next page with the same parent) which has
      * the more element assuming it's above N/2
@@ -507,7 +526,7 @@ import org.apache.directory.mavibot.btre
             return -1;
         }
 
-        return btree.getComparator().compare( key1, key2 );
+        return btree.getKeyComparator().compare( key1, key2 );
     }
 
 

Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java?rev=1643645&r1=1643644&r2=1643645&view=diff
==============================================================================
--- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java (original)
+++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java Sun Dec  7 03:28:54 2014
@@ -73,7 +73,7 @@ public interface BTree<K, V>
 
 
     /**
-     * @return the pageSize
+     * @return the number of elements per page
      */
     int getPageSize();
 
@@ -264,11 +264,17 @@ public interface BTree<K, V>
      */
     KeyCursor<K> browseKeys() throws IOException, KeyNotFoundException;
 
-    
+
+    /**
+     * @return the key comparator
+     */
+    Comparator<K> getKeyComparator();
+
+
     /**
-     * @return the comparator
+     * @return the value comparator
      */
-    Comparator<K> getComparator();
+    Comparator<V> getValueComparator();
 
 
     /**

Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeFactory.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeFactory.java?rev=1643645&r1=1643644&r2=1643645&view=diff
==============================================================================
--- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeFactory.java (original)
+++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTreeFactory.java Sun Dec  7 03:28:54 2014
@@ -62,7 +62,7 @@ public class BTreeFactory<K, V>
     public static <K, V> BTree<K, V> createPersistedBTree( BTreeTypeEnum type )
     {
         BTree<K, V> btree = new PersistedBTree<K, V>();
-        ((AbstractBTree<K, V>)btree).setType( type );
+        ( ( AbstractBTree<K, V> ) btree ).setType( type );
 
         return btree;
     }
@@ -79,6 +79,7 @@ public class BTreeFactory<K, V>
         btree.setBtreeHeaderOffset( btreeHeaderOffset );
     }
 
+
     /**
      * Creates a new persisted B-tree using the BTreeConfiguration to initialize the
      * B-tree
@@ -514,6 +515,7 @@ public class BTreeFactory<K, V>
     {
         if ( btree.getType() != BTreeTypeEnum.IN_MEMORY )
         {
+            //System.out.println( "Creating a node with nbElems : " + nbElems );
             return new PersistedNode<K, V>( btree, revision, nbElems );
         }
         else
@@ -609,7 +611,8 @@ public class BTreeFactory<K, V>
      * @throws IllegalArgumentException
      */
     /* no qualifier*/static <K, V> void setKeySerializer( BTree<K, V> btree, String keySerializerFqcn )
-        throws ClassNotFoundException, IllegalAccessException, InstantiationException, IllegalArgumentException, SecurityException, NoSuchFieldException
+        throws ClassNotFoundException, IllegalAccessException, InstantiationException, IllegalArgumentException,
+        SecurityException, NoSuchFieldException
     {
         Class<?> keySerializer = Class.forName( keySerializerFqcn );
         @SuppressWarnings("unchecked")
@@ -618,7 +621,7 @@ public class BTreeFactory<K, V>
         {
             instance = ( ElementSerializer<K> ) keySerializer.getDeclaredField( "INSTANCE" ).get( null );
         }
-        catch( NoSuchFieldException e )
+        catch ( NoSuchFieldException e )
         {
             // ignore
         }
@@ -645,7 +648,8 @@ public class BTreeFactory<K, V>
      * @throws IllegalArgumentException
      */
     /* no qualifier*/static <K, V> void setValueSerializer( BTree<K, V> btree, String valueSerializerFqcn )
-        throws ClassNotFoundException, IllegalAccessException, InstantiationException, IllegalArgumentException, SecurityException, NoSuchFieldException
+        throws ClassNotFoundException, IllegalAccessException, InstantiationException, IllegalArgumentException,
+        SecurityException, NoSuchFieldException
     {
         Class<?> valueSerializer = Class.forName( valueSerializerFqcn );
         @SuppressWarnings("unchecked")
@@ -654,16 +658,16 @@ public class BTreeFactory<K, V>
         {
             instance = ( ElementSerializer<V> ) valueSerializer.getDeclaredField( "INSTANCE" ).get( null );
         }
-        catch( NoSuchFieldException e )
+        catch ( NoSuchFieldException e )
         {
             // ignore
         }
-        
+
         if ( instance == null )
         {
             instance = ( ElementSerializer<V> ) valueSerializer.newInstance();
         }
-        
+
         btree.setValueSerializer( instance );
     }
 

Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java?rev=1643645&r1=1643644&r2=1643645&view=diff
==============================================================================
--- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java (original)
+++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTree.java Sun Dec  7 03:28:54 2014
@@ -77,6 +77,7 @@ import org.slf4j.LoggerFactory;
     /** The Journal channel */
     private FileChannel journalChannel = null;
 
+
     /**
      * Creates a new BTree, with no initialization.
      */
@@ -137,7 +138,7 @@ import org.slf4j.LoggerFactory;
         newBtreeHeader.setRootPage( new InMemoryLeaf<K, V>( this ) );
         newBtreeHeader.setRootPageOffset( 0L );
 
-        btreeRevisions.put( 0L,  newBtreeHeader );
+        btreeRevisions.put( 0L, newBtreeHeader );
         currentBtreeHeader = newBtreeHeader;
 
         // Now, initialize the BTree
@@ -180,7 +181,7 @@ import org.slf4j.LoggerFactory;
 
         // Create the queue containing the pending read transactions
         readTransactions = new ConcurrentLinkedQueue<ReadTransaction<K, V>>();
-        
+
         // Create the transaction manager
         transactionManager = new InMemoryTransactionManager();
 
@@ -236,8 +237,8 @@ import org.slf4j.LoggerFactory;
 
         return readTransaction;
     }
-    
-    
+
+
     /**
      * {@inheritDoc}
      */
@@ -247,7 +248,7 @@ import org.slf4j.LoggerFactory;
 
         if ( btreeHeader != null )
         {
-            ReadTransaction<K, V> readTransaction = new ReadTransaction<K, V>(  btreeHeader, readTransactions );
+            ReadTransaction<K, V> readTransaction = new ReadTransaction<K, V>( btreeHeader, readTransactions );
 
             readTransactions.add( readTransaction );
 
@@ -520,40 +521,40 @@ import org.slf4j.LoggerFactory;
         try
         {
             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();
@@ -741,6 +742,20 @@ import org.slf4j.LoggerFactory;
 
 
     /**
+     * Set the file path where the journal will be stored
+     * 
+     * @param filePath The file path
+     */
+    public void setFilePath( String filePath )
+    {
+        if ( filePath != null )
+        {
+            envDir = new File( filePath );
+        }
+    }
+
+
+    /**
      * @return the journal
      */
     public File getJournal()
@@ -836,8 +851,8 @@ import org.slf4j.LoggerFactory;
             case BACKED_ON_DISK:
                 sb.append( "Persistent " );
                 break;
-                
-            default :
+
+            default:
                 sb.append( "Wrong type... " );
                 break;
         }

Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilder.java?rev=1643645&r1=1643644&r2=1643645&view=diff
==============================================================================
--- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilder.java (original)
+++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilder.java Sun Dec  7 03:28:54 2014
@@ -37,94 +37,415 @@ import org.apache.directory.mavibot.btre
  */
 public class InMemoryBTreeBuilder<K, V>
 {
-    private String name;
-
-    private int numKeysInNode;
-
-    private ElementSerializer<K> keySerializer;
-
-    private ElementSerializer<V> valueSerializer;
+    /** The Btree configuration */
+    private InMemoryBTreeConfiguration<K, V> btreeConfiguration;
 
 
+    /**
+     * Creates a new instance of InMemoryBTreeBuilder.
+     *
+     * @param name The BTree name
+     * @param numKeysInNode The number of keys per node
+     * @param keySerializer The key serializer
+     * @param valueSerializer The value  serializer
+     */
     public InMemoryBTreeBuilder( String name, int numKeysInNode, ElementSerializer<K> keySerializer,
         ElementSerializer<V> valueSerializer )
     {
-        this.name = name;
-        this.numKeysInNode = numKeysInNode;
-        this.keySerializer = keySerializer;
-        this.valueSerializer = valueSerializer;
+        btreeConfiguration = new InMemoryBTreeConfiguration<K, V>();
+        btreeConfiguration.setName( name );
+        btreeConfiguration.setPageSize( numKeysInNode );
+        btreeConfiguration.setKeySerializer( keySerializer );
+        btreeConfiguration.setValueSerializer( valueSerializer );
+    }
+
+
+    /**
+     * Creates a new instance of InMemoryBTreeBuilder.
+     *
+     * @param btreeConfiguration The Btree configuration
+     */
+    public InMemoryBTreeBuilder( InMemoryBTreeConfiguration<K, V> btreeConfiguration )
+    {
+        this.btreeConfiguration = btreeConfiguration;
     }
 
 
     @SuppressWarnings("unchecked")
     public BTree<K, V> build( Iterator<Tuple<K, V>> sortedTupleItr ) throws IOException
     {
-        BTree<K, V> btree = BTreeFactory.createInMemoryBTree( name, keySerializer, valueSerializer );
+        BTree<K, V> btree = BTreeFactory.createInMemoryBTree( btreeConfiguration );
+        int pageSize = btree.getPageSize();
+        int maxElements = ( pageSize + 1 ) * pageSize;
+
+        // The stack used to store all the levels. No need to have more than 16 levels, 
+        // it will allow the storage of 2^64 elements with pages containing 4 elements each.
+        List<InMemoryNode<K, V>>[] pageStack = new ArrayList[15];
+
+        for ( int i = 0; i < 15; i++ )
+        {
+            pageStack[i] = new ArrayList<InMemoryNode<K, V>>( maxElements );
+        }
 
-        List<Page<K, V>> lstLeaves = new ArrayList<Page<K, V>>();
+        // The number of added elements
+        int nbAdded = 0;
 
-        int totalTupleCount = 0;
+        // The btree height
+        int btreeHeight = 0;
 
-        InMemoryLeaf<K, V> leaf1 = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0, numKeysInNode );
-        lstLeaves.add( leaf1 );
+        // An array containing the number of elements necessary to fulfill a layer :
+        // pageSize * (pageSize + 1)
+        List<Tuple<K, V>> tuples = new ArrayList<Tuple<K, V>>( maxElements );
 
-        int leafIndex = 0;
+        // A list of nodes that are going to be created
+        List<InMemoryNode<K, V>> nodes = new ArrayList<InMemoryNode<K, V>>();
 
+        // Now, loop on all the elements
         while ( sortedTupleItr.hasNext() )
         {
+            nbAdded++;
+
+            // Get the tuple to inject
             Tuple<K, V> tuple = sortedTupleItr.next();
+            tuples.add( tuple );
+
+            if ( tuples.size() == maxElements )
+            {
+                // We have enough elements to create pageSize leaves, and the upper node
+                InMemoryNode<K, V> node = ( InMemoryNode<K, V> ) addLeaves( btree, tuples, maxElements );
+                int level = 0;
+
+                if ( node != null )
+                {
+                    while ( true )
+                    {
+                        pageStack[level].add( node );
+
+                        // If the node list has enough elements to fulfill a parent node,
+                        // then process 
+                        if ( pageStack[level].size() > btree.getPageSize() )
+                        {
+                            node = createParentNode( btree, pageStack[level], btree.getPageSize() );
+                            pageStack[level].clear();
+                            level++;
+                        }
+                        else
+                        {
+                            break;
+                        }
+                    }
+
+                    ( ( AbstractBTree<K, V> ) btree ).setRootPage( pageStack[level].get( 0 ) );
+
+                    // Update the btree height
+                    if ( btreeHeight < level )
+                    {
+                        btreeHeight = level;
+                    }
+                }
 
-            BTreeFactory.setKey( btree, leaf1, leafIndex, tuple.getKey() );
+                tuples.clear();
+            }
+        }
 
-            InMemoryValueHolder<V> eh = new InMemoryValueHolder<V>( btree, tuple.getValue() );
+        if ( tuples.size() > 0 )
+        {
+            // Let's deal with the remaining elements
+            Page<K, V> page = addLeaves( btree, tuples, maxElements );
 
-            BTreeFactory.setValue( btree, leaf1, leafIndex, eh );
+            if ( page instanceof InMemoryNode )
+            {
+                nodes.add( ( InMemoryNode<K, V> ) page );
 
-            leafIndex++;
-            totalTupleCount++;
+                // If the node list has enough elements to fulfill a parent node,
+                // then process 
+                if ( nodes.size() == maxElements )
+                {
+                    Page<K, V> rootPage = createParentNode( btree, nodes, maxElements );
 
-            if ( ( totalTupleCount % numKeysInNode ) == 0 )
+                    ( ( AbstractBTree<K, V> ) btree ).setRootPage( rootPage );
+                }
+            }
+            else
             {
-                leafIndex = 0;
-                leaf1 = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0, numKeysInNode );
-                lstLeaves.add( leaf1 );
+                InMemoryLeaf<K, V> leaf = ( InMemoryLeaf<K, V> ) page;
+
+                // Its a leaf. That means we may have to balance the btree
+                if ( pageStack[0].size() != 0 )
+                {
+                    // We have some leaves in level 0, which means we just have to add the new leaf
+                    // there, after having check we don't have to borrow some elements from the last leaf
+                    if ( leaf.getNbElems() < btree.getPageSize() / 2 )
+                    {
+                        // Not enough elements in the added leaf. Borrow some from the left.
+                    }
+                    else
+                    {
+                        // Enough elements in the added leaf (at least N/2). We just have to update
+                        // the parent's node.
+                    }
+                }
             }
         }
 
-        if ( lstLeaves.isEmpty() )
+        // Update the number of elements
+        ( ( AbstractBTree<K, V> ) btree ).getBtreeHeader().setNbElems( nbAdded );
+
+        return btree;
+    }
+
+
+    /**
+     * Creates all the nodes using the provided node pages, and update the upper laye
+     */
+    private InMemoryNode<K, V> createParentNode( BTree<K, V> btree, List<InMemoryNode<K, V>> nodes, int maxElements )
+    {
+        // We have enough tuples to fulfill the upper node.
+        // First, create the new node
+        InMemoryNode<K, V> parentNode = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0,
+            btreeConfiguration.getPageSize() );
+
+        int nodePos = 0;
+
+        // Then iterate on the tuples, creating the needed pages
+        for ( InMemoryNode<K, V> node : nodes )
         {
-            return btree;
+            if ( nodePos == 0 )
+            {
+                PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, node );
+                parentNode.setPageHolder( nodePos, pageHolder );
+            }
+            else if ( nodePos == btree.getPageSize() )
+            {
+                K key = node.getLeftMostKey();
+                BTreeFactory.setKey( btree, parentNode, nodePos - 1, key );
+                PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, node );
+                parentNode.setPageHolder( nodePos, pageHolder );
+            }
+            else
+            {
+                K key = node.getLeftMostKey();
+                BTreeFactory.setKey( btree, parentNode, nodePos - 1, key );
+                PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, node );
+                parentNode.setPageHolder( nodePos, pageHolder );
+            }
+
+            nodePos++;
         }
 
-        // remove null keys and values from the last leaf and resize
-        InMemoryLeaf<K, V> lastLeaf = ( InMemoryLeaf<K, V> ) lstLeaves.get( lstLeaves.size() - 1 );
+        // And return the node
+        return parentNode;
+    }
+
 
-        for ( int i = 0; i < lastLeaf.getNbElems(); i++ )
+    /**
+     * Creates all the leaves using the provided tuples, and update the upper layer if needed
+     */
+    private Page<K, V> addLeaves( BTree<K, V> btree, List<Tuple<K, V>> tuples, int maxElements )
+    {
+        if ( tuples.size() == 0 )
         {
-            if ( lastLeaf.getKeys()[i] == null )
+            // No element to inject in the BTree
+            return null;
+        }
+
+        // The insertion position in the leaf
+        int leafPos = 0;
+
+        // Deal with special cases : 
+        // First, everything will fit in a single page
+        if ( tuples.size() < btree.getPageSize() )
+        {
+            // The leaf will be the rootPage
+            // creates a first leaf
+            InMemoryLeaf<K, V> leaf = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0,
+                btreeConfiguration.getPageSize() );
+
+            // Iterate on the tuples
+            for ( Tuple<K, V> tuple : tuples )
             {
-                int n = i;
-                lastLeaf.setNbElems( n );
-                KeyHolder<K>[] keys = lastLeaf.getKeys();
+                injectTuple( btree, leaf, leafPos, tuple );
+                leafPos++;
+            }
+
+            return leaf;
+        }
 
-                lastLeaf.setKeys( ( KeyHolder[] ) Array.newInstance( KeyHolder.class, n ) );
-                System.arraycopy( keys, 0, lastLeaf.getKeys(), 0, n );
+        // Second, the data will fit into a 2 level tree
+        if ( tuples.size() < maxElements )
+        {
+            // We will just create the necessary leaves and the upper node if needed
+            // We have enough tuples to fulfill the uper node.
+            // First, create the new node
+            InMemoryNode<K, V> node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0,
+                btreeConfiguration.getPageSize() );
+
+            // creates a first leaf
+            InMemoryLeaf<K, V> leaf = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0,
+                btreeConfiguration.getPageSize() );
 
-                ValueHolder<V>[] values = lastLeaf.values;
-                lastLeaf.values = ( InMemoryValueHolder<V>[] ) Array.newInstance( InMemoryValueHolder.class, n );
-                System.arraycopy( values, 0, lastLeaf.values, 0, n );
+            int nodePos = 0;
 
-                break;
+            // Then iterate on the tuples, creating the needed pages
+            for ( Tuple<K, V> tuple : tuples )
+            {
+                if ( leafPos == btree.getPageSize() )
+                {
+                    // The leaf is full, we need to attach it to its parent's node
+                    // and to create a new leaf
+                    BTreeFactory.setKey( btree, node, nodePos, tuple.getKey() );
+                    PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, leaf );
+                    node.setPageHolder( nodePos, pageHolder );
+                    nodePos++;
+
+                    // When done, we need to create a new leaf
+                    leaf = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0,
+                        btree.getPageSize() );
+
+                    // and inject the tuple in the leaf
+                    injectTuple( btree, leaf, 0, tuple );
+                    leafPos = 1;
+                }
+                else
+                {
+                    // Inject the tuple in the leaf
+                    injectTuple( btree, leaf, leafPos, tuple );
+                    leafPos++;
+                }
+            }
+
+            // Last, not least, deal with the last created leaf, which has to be injected in its parent's node
+            if ( leafPos > 0 )
+            {
+                PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, leaf );
+                node.setPageHolder( nodePos, pageHolder );
             }
+
+            return node;
         }
+        else
+        {
+            // We have enough tuples to fulfill the upper node.
+            // First, create the new node
+            InMemoryNode<K, V> node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0,
+                btreeConfiguration.getPageSize() );
+
+            // creates a first leaf
+            InMemoryLeaf<K, V> leaf = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0,
+                btreeConfiguration.getPageSize() );
+
+            int nodePos = 0;
 
-        Page<K, V> rootPage = attachNodes( lstLeaves, btree );
+            // Then iterate on the tuples, creating the needed pages
+            for ( Tuple<K, V> tuple : tuples )
+            {
+                if ( leafPos == btree.getPageSize() )
+                {
+                    // The leaf is full, we need to attach it to its parent's node
+                    // and to create a new node
+                    BTreeFactory.setKey( btree, node, nodePos, tuple.getKey() );
+                    PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, leaf );
+                    node.setPageHolder( nodePos, pageHolder );
+                    nodePos++;
+
+                    // When done, we need to create a new leaf
+                    leaf = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0,
+                        btree.getPageSize() );
+
+                    // and inject the tuple in the leaf
+                    injectTuple( btree, leaf, 0, tuple );
+                    leafPos = 1;
+                }
+                else
+                {
+                    // Inject the tuple in the leaf
+                    injectTuple( btree, leaf, leafPos, tuple );
+                    leafPos++;
+                }
+            }
 
-        System.out.println( "built rootpage : " + rootPage );
+            // Last, not least, deal with the last created leaf, which has to be injected in its parent's node
+            if ( leafPos > 0 )
+            {
+                PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, leaf );
+                node.setPageHolder( nodePos, pageHolder );
+            }
 
-        ( ( AbstractBTree<K, V> ) btree ).setRootPage( rootPage );
+            // And return the node
+            return node;
+        }
+    }
 
-        return btree;
+
+    private void injectTuple( BTree<K, V> btree, InMemoryLeaf<K, V> leaf, int leafPos, Tuple<K, V> tuple )
+    {
+        BTreeFactory.setKey( btree, leaf, leafPos, tuple.getKey() );
+        ValueHolder<V> valueHolder = new InMemoryValueHolder<V>( btree, tuple.getValue() );
+        BTreeFactory.setValue( btree, leaf, leafPos, valueHolder );
+    }
+
+
+    private int add( BTree<K, V> btree, Page<K, V>[] pageStack, int level, Page<K, V> page, Tuple<K, V> tuple )
+    {
+        if ( page == null )
+        {
+            // No existing page at this level, create a new one
+            if ( level == 0 )
+            {
+                // creates a leaf
+                InMemoryLeaf<K, V> leaf = ( InMemoryLeaf<K, V> ) BTreeFactory.createLeaf( btree, 0,
+                    btreeConfiguration.getPageSize() );
+
+                // Store the new leaf in the stack
+                pageStack[level] = leaf;
+
+                // Inject the tuple in the leaf
+                BTreeFactory.setKey( btree, leaf, 0, tuple.getKey() );
+                ValueHolder<V> valueHolder = new InMemoryValueHolder<V>( btree, tuple.getValue() );
+                BTreeFactory.setValue( btree, leaf, 0, valueHolder );
+            }
+            else
+            {
+                // Create a node
+                InMemoryNode<K, V> node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0,
+                    btreeConfiguration.getPageSize() );
+
+                // Inject the tuple key in the node
+                BTreeFactory.setKey( btree, node, 0, tuple.getKey() );
+                PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, pageStack[level - 1] );
+                node.setPageHolder( 0, pageHolder );
+            }
+        }
+        else
+        {
+            // Check first if the current page is full
+            if ( page.getNbElems() == btree.getPageSize() )
+            {
+                // Ok, it's full. We need to create a new page and to propagate the
+                // added element to the upper level
+            }
+            else
+            {
+                // We just have to inject the tuple in the current page
+                // be it a leaf or a node
+                if ( page.isLeaf() )
+                {
+                    // It's a leaf
+                    BTreeFactory.setKey( btree, page, page.getNbElems(), tuple.getKey() );
+                    ValueHolder<V> valueHolder = new InMemoryValueHolder<V>( btree, tuple.getValue() );
+                    BTreeFactory.setValue( btree, page, page.getNbElems(), valueHolder );
+                }
+                else
+                {
+                    // It's a node
+                    BTreeFactory.setKey( btree, page, page.getNbElems(), tuple.getKey() );
+                    PageHolder<K, V> pageHolder = new PageHolder<K, V>( btree, pageStack[level - 1] );
+                    ( ( InMemoryNode<K, V> ) page ).setPageHolder( page.getNbElems(), pageHolder );
+                }
+            }
+        }
+
+        return level;
     }
 
 
@@ -138,9 +459,10 @@ public class InMemoryBTreeBuilder<K, V>
 
         List<Page<K, V>> lstNodes = new ArrayList<Page<K, V>>();
 
-        int numChildren = numKeysInNode + 1;
+        int numChildren = btreeConfiguration.getPageSize() + 1;
 
-        InMemoryNode<K, V> node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0, numKeysInNode );
+        InMemoryNode<K, V> node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0,
+            btreeConfiguration.getPageSize() );
         lstNodes.add( node );
         int i = 0;
         int totalNodes = 0;
@@ -160,7 +482,7 @@ public class InMemoryBTreeBuilder<K, V>
             if ( ( totalNodes % numChildren ) == 0 )
             {
                 i = 0;
-                node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0, numKeysInNode );
+                node = ( InMemoryNode<K, V> ) BTreeFactory.createNode( btree, 0, btreeConfiguration.getPageSize() );
                 lstNodes.add( node );
             }
         }

Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyHolder.java?rev=1643645&r1=1643644&r2=1643645&view=diff
==============================================================================
--- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyHolder.java (original)
+++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/KeyHolder.java Sun Dec  7 03:28:54 2014
@@ -60,4 +60,13 @@ package org.apache.directory.mavibot.btr
     {
         return key;
     }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return key.toString();
+    }
 }

Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java?rev=1643645&r1=1643644&r2=1643645&view=diff
==============================================================================
--- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java (original)
+++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedBTree.java Sun Dec  7 03:28:54 2014
@@ -68,10 +68,11 @@ public class PersistedBTree<K, V> extend
 
     /** The BtreeInfo offset */
     private long btreeInfoOffset;
-    
+
     /** The internal recordManager */
     private RecordManager recordManager;
 
+
     /**
      * Creates a new BTree, with no initialization.
      */
@@ -130,13 +131,13 @@ public class PersistedBTree<K, V> extend
                 currentBtreeHeader = btreeHeader;
                 break;
 
-            case PERSISTED_SUB :
+            case PERSISTED_SUB:
                 init( ( PersistedBTree<K, V> ) configuration.getParentBTree() );
                 btreeRevisions.put( 0L, btreeHeader );
                 currentBtreeHeader = btreeHeader;
                 break;
-                
-            default :
+
+            default:
                 // We will create a new cache and a new readTransactions map 
                 init( null );
                 btreeRevisions.put( 0L, btreeHeader );
@@ -164,13 +165,13 @@ public class PersistedBTree<K, V> extend
             {
                 cacheSize = 1;
             }
-            
+
             cache = new LRUMap( cacheSize );
         }
         else
         {
-            this.cache = ((PersistedBTree<K, V>)parentBTree).getCache();
-            this.readTransactions = ((PersistedBTree<K, V>)parentBTree).getReadTransactions();
+            this.cache = ( ( PersistedBTree<K, V> ) parentBTree ).getCache();
+            this.readTransactions = ( ( PersistedBTree<K, V> ) parentBTree ).getReadTransactions();
         }
 
         // Initialize the txnManager thread
@@ -274,7 +275,7 @@ public class PersistedBTree<K, V> extend
      * @return
      * @throws IOException
      */
-    /* no qualifier */ Tuple<K, V> delete( K key, V value, long revision ) throws IOException
+    /* no qualifier */Tuple<K, V> delete( K key, V value, long revision ) throws IOException
     {
         // We have to start a new transaction, which will be committed or rollbacked
         // locally. This will duplicate the current BtreeHeader during this phase.
@@ -327,7 +328,7 @@ public class PersistedBTree<K, V> extend
 
         // 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 = btreeHeader.getRootPage().delete( key, value, revision);
+        DeleteResult<K, V> result = btreeHeader.getRootPage().delete( key, value, revision );
 
         if ( result instanceof NotPresentResult )
         {
@@ -369,11 +370,10 @@ public class PersistedBTree<K, V> extend
         // Write down the data on disk
         long newBtreeHeaderOffset = recordManager.writeBtreeHeader( this, newBtreeHeader );
 
-
         // Update the B-tree of B-trees with this new offset, if we are not already doing so
         switch ( btreeType )
         {
-            case PERSISTED :
+            case PERSISTED:
                 // We have a new B-tree header to inject into the B-tree of btrees
                 recordManager.addInBtreeOfBtrees( getName(), revision, newBtreeHeaderOffset );
 
@@ -383,19 +383,18 @@ public class PersistedBTree<K, V> extend
                 storeRevision( newBtreeHeader, recordManager.isKeepRevisions() );
 
                 break;
-                
-            case PERSISTED_SUB :
+
+            case PERSISTED_SUB:
                 // Sub-B-trees are only updating the CopiedPage B-tree
                 recordManager.addInCopiedPagesBtree( getName(), revision, result.getCopiedPages() );
-                
+
                 //btreeRevisions.put( revision, newBtreeHeader );
 
                 currentRevision.set( revision );
 
-
                 break;
 
-            case BTREE_OF_BTREES :
+            case BTREE_OF_BTREES:
                 // The B-tree of B-trees or the copiedPages B-tree has been updated, update the RMheader parameters
                 recordManager.updateRecordManagerHeader( newBtreeHeaderOffset, -1L );
 
@@ -471,20 +470,20 @@ public class PersistedBTree<K, V> extend
         }
     }
 
-    
+
     private BTreeHeader<K, V> getNewBTreeHeader( String name )
     {
         if ( btreeType == BTreeTypeEnum.PERSISTED_SUB )
         {
             return getBtreeHeader();
         }
-        
+
         BTreeHeader<K, V> btreeHeader = recordManager.getNewBTreeHeader( getName() );
 
         return btreeHeader;
     }
 
-    
+
     /**
      * Insert the tuple into the B-tree rootPage, get back the new rootPage
      */
@@ -565,7 +564,7 @@ public class PersistedBTree<K, V> extend
         // Update the B-tree of B-trees with this new offset, if we are not already doing so
         switch ( btreeType )
         {
-            case PERSISTED :
+            case PERSISTED:
                 // We have a new B-tree header to inject into the B-tree of btrees
                 recordManager.addInBtreeOfBtrees( getName(), revision, newBtreeHeaderOffset );
 
@@ -576,10 +575,10 @@ public class PersistedBTree<K, V> extend
 
                 break;
 
-            case PERSISTED_SUB :
+            case PERSISTED_SUB:
                 // Sub-B-trees are only updating the CopiedPage B-tree
                 recordManager.addInCopiedPagesBtree( getName(), revision, result.getCopiedPages() );
-                
+
                 // Store the new revision
                 storeRevision( newBtreeHeader, recordManager.isKeepRevisions() );
 
@@ -587,7 +586,7 @@ public class PersistedBTree<K, V> extend
 
                 break;
 
-            case BTREE_OF_BTREES :
+            case BTREE_OF_BTREES:
                 // The B-tree of B-trees or the copiedPages B-tree has been updated, update the RMheader parameters
                 recordManager.updateRecordManagerHeader( newBtreeHeaderOffset, -1L );
 
@@ -608,6 +607,7 @@ public class PersistedBTree<K, V> extend
         return result;
     }
 
+
     /**
      * Write the data in the ByteBuffer, and eventually on disk if needed.
      *
@@ -660,6 +660,7 @@ public class PersistedBTree<K, V> extend
         return pageHolder;
     }
 
+
     /**
      * Get the rootPzge associated to a give revision.
      *
@@ -722,8 +723,8 @@ public class PersistedBTree<K, V> extend
 
         return readTransaction;
     }
-    
-    
+
+
     /**
      * {@inheritDoc}
      */
@@ -733,7 +734,8 @@ public class PersistedBTree<K, V> extend
 
         if ( btreeHeader != null )
         {
-            ReadTransaction<K, V> readTransaction = new ReadTransaction<K, V>(  recordManager, btreeHeader, readTransactions );
+            ReadTransaction<K, V> readTransaction = new ReadTransaction<K, V>( recordManager, btreeHeader,
+                readTransactions );
 
             readTransactions.add( readTransaction );
 
@@ -744,7 +746,7 @@ public class PersistedBTree<K, V> extend
             return null;
         }
     }
-    
+
 
     /**
      * @see Object#toString()

Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java?rev=1643645&r1=1643644&r2=1643645&view=diff
==============================================================================
--- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java (original)
+++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedLeaf.java Sun Dec  7 03:28:54 2014
@@ -946,6 +946,7 @@ import static org.apache.directory.mavib
         PersistedLeaf<K, V> newLeaf = new PersistedLeaf<K, V>( btree, revision, nbElems + 1 );
 
         // Create the value holder
+        //System.out.println("( addElement ) creating sub-btree for key " + key + " value " + value );
         ValueHolder<V> valueHolder = new PersistedValueHolder<V>( btree, value );
 
         // Deal with the special case of an empty page
@@ -994,6 +995,8 @@ import static org.apache.directory.mavib
         int middle = btree.getPageSize() >> 1;
         PersistedLeaf<K, V> leftLeaf = null;
         PersistedLeaf<K, V> rightLeaf = null;
+        
+        //System.out.println("(addAndSplit) creating sub-btree for key " + key + " value " + value );
         ValueHolder<V> valueHolder = new PersistedValueHolder<V>( btree, value );
 
         // Determinate where to store the new value

Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java?rev=1643645&r1=1643644&r2=1643645&view=diff
==============================================================================
--- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java (original)
+++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/PersistedValueHolder.java Sun Dec  7 03:28:54 2014
@@ -20,6 +20,10 @@
 package org.apache.directory.mavibot.btree;
 
 
+import static org.apache.directory.mavibot.btree.BTreeFactory.createLeaf;
+import static org.apache.directory.mavibot.btree.BTreeFactory.createNode;
+import static org.apache.directory.mavibot.btree.BTreeFactory.setKey;
+
 import java.io.IOException;
 import java.lang.reflect.Array;
 import java.util.ArrayList;
@@ -34,7 +38,9 @@ import org.apache.directory.mavibot.btre
 import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
 import org.apache.directory.mavibot.btree.serializer.IntSerializer;
 import org.apache.directory.mavibot.btree.serializer.LongSerializer;
-import static org.apache.directory.mavibot.btree.BTreeFactory.*;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
 
 /**
  * A holder to store the Values
@@ -44,6 +50,9 @@ import static org.apache.directory.mavib
  */
 /* No qualifier */class PersistedValueHolder<V> extends AbstractValueHolder<V>
 {
+    /** The LoggerFactory used by this class */
+    protected static final Logger LOG = LoggerFactory.getLogger( PersistedValueHolder.class );
+
     /** The parent BTree */
     protected PersistedBTree<V, V> parentBtree;
 
@@ -132,7 +141,7 @@ import static org.apache.directory.mavib
                         buildSubBTree( ( PersistedBTree<V, V> ) valueBtree, values );
                     }
                 }
-                catch( Exception e )
+                catch ( Exception e )
                 {
                     throw new RuntimeException( e );
                 }
@@ -405,7 +414,7 @@ import static org.apache.directory.mavib
                     }
 
                     cursor.close();
-                    
+
                     return returnedValue;
                 }
                 else
@@ -638,7 +647,7 @@ import static org.apache.directory.mavib
         V val = super.replaceValueArray( newValue );
         // The raw value is not anymore up to date with the content
         isRawUpToDate = false;
-        
+
         return val;
     }
 
@@ -702,7 +711,12 @@ import static org.apache.directory.mavib
 
 
     /**
-     * {@inheritDoc}
+     * Constructs the sub-BTree using bulkload instead of performing sequential inserts.
+     * 
+     * @param btree the sub-BTtree to be constructed
+     * @param dupKeyValues the array of values to be inserted as keys
+     * @return
+     * @throws Exception
      */
     protected BTree buildSubBTree( BTree<V, V> givenBTree, V[] dupKeyValues ) throws Exception
     {
@@ -805,7 +819,8 @@ import static org.apache.directory.mavib
      * @return the new root page of the sub-BTree after attaching all the nodes
      * @throws IOException
      */
-    private Page attachNodes( List<Page<V, V>> children, BTree btree, int numKeysInNode, RecordManager rm ) throws IOException
+    private Page attachNodes( List<Page<V, V>> children, BTree btree, int numKeysInNode, RecordManager rm )
+        throws IOException
     {
         if ( children.size() == 1 )
         {
@@ -864,15 +879,15 @@ import static org.apache.directory.mavib
             }
         }
 
-        if( lastNode.keys.length == 0 )
+        if ( lastNode.keys.length == 0 )
         {
             lstNodes.remove( lastNode );
         }
 
         return attachNodes( lstNodes, btree, numKeysInNode, rm );
     }
-    
-    
+
+
     /**
      * @see Object#toString()
      */

Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java?rev=1643645&r1=1643644&r2=1643645&view=diff
==============================================================================
--- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java (original)
+++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java Sun Dec  7 03:28:54 2014
@@ -219,7 +219,7 @@ public class RecordManager extends Abstr
     private int commitCount = 0;
     
     /** the threshold at which the SpaceReclaimer will be run to free the copied pages */
-    private int spaceReclaimerThreshold = 200;
+    private int spaceReclaimerThreshold = 0;
     
     /**
      * Create a Record manager which will either create the underlying file
@@ -579,6 +579,14 @@ public class RecordManager extends Abstr
                 return;
             
             case 1 :
+                
+                commitCount++;
+                
+                if( commitCount >= spaceReclaimerThreshold )
+                {
+                    runReclaimer();
+                }
+                
                 // We are done with the transaction, we can update the RMHeader and swap the BTreeHeaders
                 // First update the RMHeader to be sure that we have a way to restore from a crash
                 updateRecordManagerHeader();
@@ -610,19 +618,20 @@ public class RecordManager extends Abstr
                 // And decrement the number of started transactions
                 decrementTxnLevel();
 
-                commitCount++;
-                
-                if( commitCount >= spaceReclaimerThreshold )
-                {
-                    runReclaimer();
-                }
-                
                 // Finally, release the global lock
                 transactionLock.unlock();
                 
                 return;
                 
             default :
+                
+                commitCount++;
+                
+                if( commitCount >= spaceReclaimerThreshold )
+                {
+                    runReclaimer();
+                }
+
                 // We are inner an existing transaction. Just update the necessary elements
                 // Update the RMHeader to be sure that we have a way to restore from a crash
                 updateRecordManagerHeader();
@@ -654,13 +663,6 @@ public class RecordManager extends Abstr
                 // And decrement the number of started transactions
                 decrementTxnLevel();
 
-                commitCount++;
-                
-                if( commitCount >= spaceReclaimerThreshold )
-                {
-                    runReclaimer();
-                }
-
                 // Finally, release the global lock
                 transactionLock.unlock();
                 
@@ -771,7 +773,7 @@ public class RecordManager extends Abstr
         
         if( firstPage.isFree() )
         {
-            System.out.println("------------- NOT freeing free page ---------------");
+            //System.out.println("------------- NOT freeing free page ---------------");
             return new PageIO[]{};
         }
         else
@@ -3931,6 +3933,8 @@ public class RecordManager extends Abstr
     @SuppressWarnings("all")
     /* No qualifier */boolean chopTree( PersistedBTree tree, Object key)
     {
+        beginTransaction();
+        
         AbstractPage root = ( AbstractPage ) tree.getRootPage();
         
         try
@@ -3975,7 +3979,7 @@ public class RecordManager extends Abstr
             
             Object leftKey = null;
             
-            long revision = tree.getRevision();
+            long revision = tree.getRevision() + 1;
             
             while( !stack.isEmpty() )
             {
@@ -4114,15 +4118,21 @@ public class RecordManager extends Abstr
             BTreeHeader header = tree.getBtreeHeader();
             
             header.setRootPage( pageHolder.getValue() );
-            header.setRevision( tree.getRevision() );
+            header.setRevision( revision );
             
             // compute 
             header.setNbElems( tree.getNbElems() - keysToRemove );
             
-            writeBtreeHeader( tree, header );
+            long newBtreeHeaderOffset = writeBtreeHeader( tree, header );
+            
+            // We have a new B-tree header to inject into the B-tree of btrees
+            addInBtreeOfBtrees( tree.name, revision, newBtreeHeaderOffset );
+            
+            commit();
         }
         catch( IOException e )
         {
+            rollback();
             LOG.warn( "Failed to free the pages of the tree {}", tree.getName() );
             LOG.warn( "", e );
             return false;

Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/SpaceReclaimer.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/SpaceReclaimer.java?rev=1643645&r1=1643644&r2=1643645&view=diff
==============================================================================
--- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/SpaceReclaimer.java (original)
+++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/SpaceReclaimer.java Sun Dec  7 03:28:54 2014
@@ -28,6 +28,7 @@ import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
 import java.io.OutputStream;
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Collections;
 import java.util.Iterator;
 import java.util.List;
@@ -36,6 +37,7 @@ import java.util.Set;
 import java.util.TreeSet;
 import java.util.concurrent.ConcurrentHashMap;
 
+import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
@@ -162,6 +164,7 @@ public class SpaceReclaimer
         return map;
     }
 
+    //void reclaim(){}
     
     /**
      * relcaims the copied pages
@@ -191,6 +194,8 @@ public class SpaceReclaimer
 
                 List<RevisionOffset> copiedRevisions = getRevisions( name );
 
+                long lastRev = -1L;
+                
                 for ( RevisionOffset ro : copiedRevisions )
                 {
                     long rv = ro.getRevision();
@@ -207,7 +212,39 @@ public class SpaceReclaimer
                     rm.free( offsets );
 
                     RevisionName key = new RevisionName( rv, name );
+                    
                     rm.copiedPageMap.remove( key );
+                    
+                    if( rv > lastRev )
+                    {
+                        lastRev = rv;
+                    }
+                }
+                
+                if( lastRev != -1 )
+                {
+                    System.out.println( "===================== start ======================= " + name );
+                    System.out.println( "BoB root offset " + ( ( AbstractPage ) rm.btreeOfBtrees.getRootPage() ).getOffset() );
+                    System.out.println( "deleting revisions from BoB upto and including " + lastRev );
+                    ValueCursor<RevisionAndHeaderOffset> values = rm.btreeOfBtrees.getValues( name );
+                    RevisionAndHeaderOffset prevRho = null;
+                    while( values.hasNext() )
+                    {
+                        RevisionAndHeaderOffset rho = values.next();
+                        if( rho.getRevision() > lastRev )
+                        {
+                            System.out.println( "stopped after deleting revision " + prevRho.getRevision() );
+                            break;
+                        }
+                        prevRho = rho;
+                        rm.btreeOfBtrees.delete( name, rho );
+                        System.out.println( "------- deleted " + rho.getRevision() + " , " + rho.getOffset() );
+                    }
+                    
+                    
+                    values.close();
+                    System.out.println( "BoB root offset " + ( ( AbstractPage ) rm.btreeOfBtrees.getRootPage() ).getOffset() );
+                    System.out.println( "===================== end ======================= " + name );
                 }
             }
         }

Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/Tuple.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/Tuple.java?rev=1643645&r1=1643644&r2=1643645&view=diff
==============================================================================
--- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/Tuple.java (original)
+++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/Tuple.java Sun Dec  7 03:28:54 2014
@@ -20,6 +20,9 @@
 package org.apache.directory.mavibot.btree;
 
 
+import java.util.Comparator;
+
+
 /**
  * The Tuple class is used when we browse a btree, it will contain the results
  * fetched from the btree.
@@ -29,7 +32,7 @@ package org.apache.directory.mavibot.btr
  * @param <K> The type for the Key
  * @param <V> The type for the stored value
  */
-public class Tuple<K, V>
+public class Tuple<K, V> implements Comparable<Tuple<K, V>>
 {
     /** The key */
     protected K key;
@@ -37,6 +40,9 @@ public class Tuple<K, V>
     /** The value */
     protected V value;
 
+    /** The key comparator */
+    protected Comparator<K> keyComparator;
+
 
     /**
      * Creates a Tuple with no content
@@ -59,6 +65,19 @@ public class Tuple<K, V>
 
 
     /**
+     * Creates a Tuple containing a key and its associated value.
+     * @param key The key
+     * @param value The associated value
+     */
+    public Tuple( K key, V value, Comparator<K> keyComparator )
+    {
+        this.key = key;
+        this.value = value;
+        this.keyComparator = keyComparator;
+    }
+
+
+    /**
      * @return the key
      */
     public K getKey()
@@ -94,6 +113,77 @@ public class Tuple<K, V>
     }
 
 
+    /**
+     * @see Object#hashCode()
+     */
+    @Override
+    public int hashCode()
+    {
+        return key.hashCode();
+    }
+
+
+    /**
+     * @see Object#equals()
+     */
+    @SuppressWarnings("unchecked")
+    @Override
+    public boolean equals( Object obj )
+    {
+        if ( this == obj )
+        {
+            return true;
+        }
+
+        if ( !( obj instanceof Tuple ) )
+        {
+            return false;
+        }
+
+        if ( this.key == null )
+        {
+            return ( ( Tuple<K, V> ) obj ).key == null;
+        }
+
+        return this.key.equals( ( ( Tuple<K, V> ) obj ).key );
+    }
+
+
+    /**
+     * @see java.lang.Comparable#compareTo(java.lang.Object)
+     */
+    @Override
+    public int compareTo( Tuple<K, V> t )
+    {
+        if ( keyComparator != null )
+        {
+            return keyComparator.compare( key, t.key );
+        }
+        else
+        {
+            return 0;
+        }
+    }
+
+
+    /**
+     * @return the keyComparator
+     */
+    public Comparator<K> getKeyComparator()
+    {
+        return keyComparator;
+    }
+
+
+    /**
+     * @param keyComparator the keyComparator to set
+     */
+    public void setKeyComparator( Comparator<K> keyComparator )
+    {
+        this.keyComparator = keyComparator;
+    }
+
+
     /**
      * @see Object#toString()
      */

Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java?rev=1643645&r1=1643644&r2=1643645&view=diff
==============================================================================
--- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java (original)
+++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java Sun Dec  7 03:28:54 2014
@@ -54,9 +54,6 @@ public class TupleCursor<K, V>
     /** The transaction used for this cursor */
     protected ReadTransaction<K, V> transaction;
 
-    /** The Tuple used to return the results */
-    protected Tuple<K, V> tuple = new Tuple<K, V>();
-
 
     /**
      * Creates a new instance of Cursor.
@@ -322,8 +319,7 @@ public class TupleCursor<K, V>
         }
 
         AbstractPage<K, V> leaf = ( AbstractPage<K, V> ) ( parentPos.page );
-        tuple.setKey( leaf.getKey( parentPos.pos ) );
-        tuple.setValue( value );
+        Tuple<K, V> tuple = new Tuple<K, V>( leaf.getKey( parentPos.pos ), value );
 
         return tuple;
     }
@@ -396,6 +392,7 @@ public class TupleCursor<K, V>
 
         // The key
         AbstractPage<K, V> leaf = ( AbstractPage<K, V> ) ( parentPos.page );
+        Tuple<K, V> tuple = new Tuple<K, V>();
         tuple.setKey( leaf.getKey( parentPos.pos ) );
 
         // The value
@@ -595,8 +592,7 @@ public class TupleCursor<K, V>
         }
 
         AbstractPage<K, V> leaf = ( AbstractPage<K, V> ) ( parentPos.page );
-        tuple.setKey( leaf.getKey( parentPos.pos ) );
-        tuple.setValue( value );
+        Tuple<K, V> tuple = new Tuple<K, V>( leaf.getKey( parentPos.pos ), value );
 
         return tuple;
     }
@@ -665,6 +661,7 @@ public class TupleCursor<K, V>
         AbstractPage<K, V> leaf = ( AbstractPage<K, V> ) ( parentPos.page );
 
         // The key
+        Tuple<K, V> tuple = new Tuple<K, V>();
         tuple.setKey( leaf.getKey( parentPos.pos ) );
 
         // The value
@@ -703,16 +700,16 @@ public class TupleCursor<K, V>
 
         switch ( parentPos.pos )
         {
-            case 0 :
+            case 0:
                 // Beginning of the leaf. We have to go back into the stack up to the
                 // parent, and down to the leaf
                 return hasPrevParentPos();
-                
-            case -1 :
+
+            case -1:
                 // no previous key
                 return false;
-                
-            default :
+
+            default:
                 // we have a previous key
                 return true;
         }

Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/AbstractElementSerializer.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/AbstractElementSerializer.java?rev=1643645&r1=1643644&r2=1643645&view=diff
==============================================================================
--- directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/AbstractElementSerializer.java (original)
+++ directory/mavibot/branches/free-page-mgmt/mavibot/src/main/java/org/apache/directory/mavibot/btree/serializer/AbstractElementSerializer.java Sun Dec  7 03:28:54 2014
@@ -50,9 +50,9 @@ public abstract class AbstractElementSer
     {
         this.comparator = comparator;
 
-        // We will extract the Type to use for values, using the serializer for that
-        Class<?> valueSerializerClass = comparator.getClass();
-        Type[] types = valueSerializerClass.getGenericInterfaces();
+        // We will extract the Type to use for values, using the comparator for that
+        Class<?> comparatorClass = comparator.getClass();
+        Type[] types = comparatorClass.getGenericInterfaces();
 
         if ( types[0] instanceof Class )
         {

Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilderTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilderTest.java?rev=1643645&r1=1643644&r2=1643645&view=diff
==============================================================================
--- directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilderTest.java (original)
+++ directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/InMemoryBTreeBuilderTest.java Sun Dec  7 03:28:54 2014
@@ -29,6 +29,7 @@ import java.util.List;
 
 import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
 import org.apache.directory.mavibot.btree.serializer.IntSerializer;
+import org.junit.Ignore;
 import org.junit.Test;
 
 
@@ -40,6 +41,7 @@ import org.junit.Test;
 public class InMemoryBTreeBuilderTest
 {
     @Test
+    @Ignore
     public void testIntegerTree() throws IOException, KeyNotFoundException
     {
         List<Tuple<Integer, Integer>> sortedTuple = new ArrayList<Tuple<Integer, Integer>>();

Modified: directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBrowseTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBrowseTest.java?rev=1643645&r1=1643644&r2=1643645&view=diff
==============================================================================
--- directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBrowseTest.java (original)
+++ directory/mavibot/branches/free-page-mgmt/mavibot/src/test/java/org/apache/directory/mavibot/btree/PersistedBTreeBrowseTest.java Sun Dec  7 03:28:54 2014
@@ -36,7 +36,6 @@ import org.apache.commons.io.FileUtils;
 import org.apache.directory.mavibot.btree.exception.BTreeAlreadyManagedException;
 import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
 import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
-import org.apache.directory.mavibot.btree.serializer.IntSerializer;
 import org.apache.directory.mavibot.btree.serializer.LongSerializer;
 import org.apache.directory.mavibot.btree.serializer.StringSerializer;
 import org.junit.After;
@@ -52,6 +51,7 @@ import org.junit.rules.TemporaryFolder;
  *
  * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
  */
+@Ignore
 public class PersistedBTreeBrowseTest
 {
     private BTree<Long, String> btree = null;
@@ -98,7 +98,7 @@ public class PersistedBTreeBrowseTest
         {
             FileUtils.deleteDirectory( dataDir );
         }
-        
+
         recordManager1.close();
         assertTrue( recordManager1.isContextOk() );
     }
@@ -416,12 +416,12 @@ public class PersistedBTreeBrowseTest
         assertEquals( "3", tuple.getValue() );
 
         // Now, move to the prev value
-        cursor.prev();
+        tuple = cursor.prev();
         assertEquals( 2L, ( long ) tuple.getKey() );
         assertEquals( "2", tuple.getValue() );
 
         // And to the next value
-        cursor.next();
+        tuple = cursor.next();
         assertEquals( 3L, ( long ) tuple.getKey() );
         assertEquals( "3", tuple.getValue() );
     }
@@ -633,7 +633,7 @@ public class PersistedBTreeBrowseTest
                 btree.insert( i, Long.toString( j ) );
             }
         }
-
+System.out.println("inserted");
         // Create the cursor
         TupleCursor<Long, String> cursor = btree.browse();
 
@@ -716,7 +716,8 @@ public class PersistedBTreeBrowseTest
      * stored into a sub btree
      */
     @Test
-    public void testBrowseBTreeLeafNextDupsSubBTree1() throws IOException, BTreeAlreadyManagedException, KeyNotFoundException
+    public void testBrowseBTreeLeafNextDupsSubBTree1() throws IOException, BTreeAlreadyManagedException,
+        KeyNotFoundException
     {
         // Inject some duplicate data which will be stored into a sub btree
         for ( long i = 1L; i < 32L; i++ )
@@ -748,7 +749,8 @@ public class PersistedBTreeBrowseTest
      * Test the browse methods on a btree containing just a leaf with duplicate values
      */
     @Test
-    public void testBrowseBTreeLeafPrevDupsSubBTree1() throws IOException, BTreeAlreadyManagedException, KeyNotFoundException
+    public void testBrowseBTreeLeafPrevDupsSubBTree1() throws IOException, BTreeAlreadyManagedException,
+        KeyNotFoundException
     {
         // Inject some duplicate data which will be stored into a sub btree
         for ( long i = 1L; i < 32L; i++ )
@@ -911,7 +913,7 @@ public class PersistedBTreeBrowseTest
 
         // Create the cursor
         TupleCursor<Long, String> cursor = btree.browseFrom( 1500L );
-        
+
         assertFalse( cursor.hasNext() );
         assertTrue( cursor.hasPrev() );
         assertEquals( 1000L, cursor.prev().getKey().longValue() );
@@ -1009,55 +1011,55 @@ public class PersistedBTreeBrowseTest
         }
     }
 
-    
+
     /**
      * Test the TupleCursor.nextKey method on a btree containing nodes
      * with duplicate values.
      */
-   @Test
-   @Ignore
-   public void testNextKeyDups() throws IOException, BTreeAlreadyManagedException, KeyNotFoundException
-   {
-       // Inject some data
-       //for ( long i = 1; i < 3; i++ )
-       {
-           for ( long j = 1; j < 9; j++ )
-           {
-               btree.insert( 1L, Long.toString( j ) );
-           }
-       }
-
-       btree.insert( 1L, "10" );
-
-       // Create the cursor
-       TupleCursor<Long, String> cursor = btree.browse();
-
-       // Move forward
-       cursor.beforeFirst();
-
-       assertFalse( cursor.hasPrevKey() );
-       assertTrue( cursor.hasNextKey() );
-
-       Tuple<Long, String> tuple = cursor.nextKey();
-
-       checkTuple( tuple, 1L, "1" );
-       
-       cursor.beforeFirst();
-       long val = 1L;
-       
-       while ( cursor.hasNext() )
-       {
-           tuple = cursor.next();
-           
-           assertEquals( Long.valueOf( 1L ), tuple.getKey() );
-           assertEquals( Long.toString( val ), tuple.getValue() );
-           
-           val++;
-       }
-       
-       assertFalse( cursor.hasNextKey() );
-       assertFalse( cursor.hasPrevKey() );
-   }
+    @Test
+    @Ignore
+    public void testNextKeyDups() throws IOException, BTreeAlreadyManagedException, KeyNotFoundException
+    {
+        // Inject some data
+        //for ( long i = 1; i < 3; i++ )
+        {
+            for ( long j = 1; j < 9; j++ )
+            {
+                btree.insert( 1L, Long.toString( j ) );
+            }
+        }
+
+        btree.insert( 1L, "10" );
+
+        // Create the cursor
+        TupleCursor<Long, String> cursor = btree.browse();
+
+        // Move forward
+        cursor.beforeFirst();
+
+        assertFalse( cursor.hasPrevKey() );
+        assertTrue( cursor.hasNextKey() );
+
+        Tuple<Long, String> tuple = cursor.nextKey();
+
+        checkTuple( tuple, 1L, "1" );
+
+        cursor.beforeFirst();
+        long val = 1L;
+
+        while ( cursor.hasNext() )
+        {
+            tuple = cursor.next();
+
+            assertEquals( Long.valueOf( 1L ), tuple.getKey() );
+            assertEquals( Long.toString( val ), tuple.getValue() );
+
+            val++;
+        }
+
+        assertFalse( cursor.hasNextKey() );
+        assertFalse( cursor.hasPrevKey() );
+    }
 
 
     /**
@@ -1106,8 +1108,8 @@ public class PersistedBTreeBrowseTest
             }
         }
     }
-    
-    
+
+
     /**
      * Test the overwriting of elements
      */
@@ -1115,14 +1117,14 @@ public class PersistedBTreeBrowseTest
     public void testOverwrite() throws Exception
     {
         btree.setAllowDuplicates( false );
-        
+
         // Adding an element with a null value
         btree.insert( 1L, "1" );
 
         assertTrue( btree.hasKey( 1L ) );
 
         assertEquals( "1", btree.get( 1L ) );
-        
+
         btree.insert( 1L, "10" );
 
         assertTrue( btree.hasKey( 1L ) );
@@ -1131,17 +1133,17 @@ public class PersistedBTreeBrowseTest
         btree.close();
     }
 
-    
+
     @Ignore("test used for debugging")
     @Test
     public void testAdd20Random() throws IOException, BTreeAlreadyManagedException, KeyNotFoundException
     {
-        long [] values = new long[]
-            { 
-                14,  7, 43, 37, 49,  3, 20, 26, 17, 29, 
-                40, 33, 21, 18,  9, 30, 45, 36, 12,  8
-            };
-    
+        long[] values = new long[]
+            {
+                14, 7, 43, 37, 49, 3, 20, 26, 17, 29,
+                40, 33, 21, 18, 9, 30, 45, 36, 12, 8
+        };
+
         btree.setPageSize( 4 );
         // Inject some data
         for ( long value : values )
@@ -1150,16 +1152,45 @@ public class PersistedBTreeBrowseTest
             System.out.println( btree );
         }
 
-
         Map copiedPagesBtree = recordManager1.copiedPageMap;
-        
+
         System.out.println( copiedPagesBtree );
-        
+
         TupleCursor<Long, String> cursor = btree.browse();
-        
+
         while ( cursor.hasNext() )
         {
             System.out.println( cursor.nextKey() );
         }
     }
-}
\ No newline at end of file
+    
+    
+    /**
+     * Test the overwriting of elements
+     */
+    @Test
+    public void testDelete() throws Exception
+    {
+        btree.setAllowDuplicates( false );
+        
+        btree.setPageSize( 4 );
+        
+        for(long i = 0; i < 8; i++ )
+        {
+            btree.insert( i, String.valueOf( i ) );
+        }
+
+        for( long i =7; i > 1; i-- )
+        {
+            btree.delete( i );
+            System.out.println("======================= deleted " + i + " =======================");
+            System.out.println( btree );
+            System.out.println("=================================================================");
+        }
+        
+        System.out.println( btree );
+        
+        btree.close();
+    }
+
+}



Mime
View raw message