directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1234279 - in /directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree: BTree.java Page.java
Date Sat, 21 Jan 2012 07:44:14 GMT
Author: elecharny
Date: Sat Jan 21 07:44:14 2012
New Revision: 1234279

URL: http://svn.apache.org/viewvc?rev=1234279&view=rev
Log:
o Removed the inner classes, they are useless : we can propagate a split without having to
create intermediary objects. This result to a 50% faster insertion

Modified:
    directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/BTree.java
    directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Page.java

Modified: directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/BTree.java
URL: http://svn.apache.org/viewvc/directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/BTree.java?rev=1234279&r1=1234278&r2=1234279&view=diff
==============================================================================
--- directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/BTree.java
(original)
+++ directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/BTree.java
Sat Jan 21 07:44:14 2012
@@ -25,8 +25,6 @@ import java.util.Comparator;
 import java.util.HashMap;
 import java.util.Map;
 import java.util.concurrent.atomic.AtomicLong;
-import org.apache.directory.btree.Page.OverflowResult;
-import org.apache.directory.btree.Page.PageResult;
 
 
 /**
@@ -154,24 +152,13 @@ public class BTree<K, V>
                 // starting from the root page
                 long revision = generateRevision();
                 
-                Page.InsertResult<K, V> insert = rootPage.insert( revision, key, value
);
-
-                if ( insert == null )
-                {
-                    System.out.println( "------------> NULL" );
-                }
+                rootPage = rootPage.insert( revision, key, value );
                 
-                if ( insert instanceof PageResult )
-                {
-                    rootPage = ( ( PageResult<K, V> ) insert ).page;
-                    roots.put( revision, rootPage );
-                }
-                else
+                if ( rootPage.getRecordId() == Page.OVERFLOW )
                 {
-                    // We have to create a new rootPage
-                    rootPage = new Page<K, V>( revision, this, (OverflowResult<K,
V>)insert );
-                    roots.put( revision, rootPage );
+                    rootPage.setRecordId();
                 }
+                roots.put( revision, rootPage );
             }
         }
         finally

Modified: directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Page.java
URL: http://svn.apache.org/viewvc/directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Page.java?rev=1234279&r1=1234278&r2=1234279&view=diff
==============================================================================
--- directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Page.java
(original)
+++ directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Page.java
Sat Jan 21 07:44:14 2012
@@ -62,6 +62,9 @@ public class Page<K, V> implements Clone
     /** The number of current values in the Page */
     private int nbElems;
     
+    /** A flag used to know that the Page is the result of a split */
+    /* No qualifier */ static long OVERFLOW = -1L;
+    
 
     /**
      * No-argument constructor used by serialization.
@@ -73,6 +76,27 @@ public class Page<K, V> implements Clone
     
     
     /**
+     * Internal constructor used to create Page instance used when a page is being copied
or overflow
+     */
+    @SuppressWarnings("unchecked") // Cannot create an array of generic objects
+    private Page( BTree<K, V> btree, long revision, int nbElems, boolean isLeaf )
+    {
+        this.btree = btree;
+        this.revision = revision;
+        this.nbElems = nbElems;
+        this.keys = (K[])new Object[nbElems];
+        this.values = (V[])new Object[nbElems];
+        this.isLeaf = isLeaf;
+        recordId = btree.generateRecordId();
+        
+        if ( !isLeaf )
+        {
+            this.children = new Page[nbElems + 1];
+        }
+    }
+    
+    
+    /**
      * Page constructor, for newly created pages.
      * 
      * @param btree The parent B+tree
@@ -105,31 +129,6 @@ public class Page<K, V> implements Clone
 
 
     /**
-     * Creates a new root page, when the root is not anymore a leaf, and has been split.
-     * 
-     * @param revision The new page revision
-     * @param btree The associated btree
-     * @param result The split Page
-     */
-    @SuppressWarnings("unchecked")
-    /* No qualifier */ Page( long revision, BTree<K, V> btree, OverflowResult<K,
V> result )
-    {
-        this.revision = revision;
-        this.btree = btree;
-        this.recordId = btree.generateRecordId();
-        isLeaf = false;
-        nbElems = 1;
-        keys = (K[])new Object[nbElems];
-        keys[0] = result.pivotKey;
-        values = (V[])new Object[nbElems];
-        values[0] = result.pivotValue;
-        children = new Page[nbElems + 1];
-        children[0] = result.leftPage;
-        children[1] = result.rightPage;
-    }
-    
-    
-    /**
      * Find a value in the tree, using its key. If it's not found, this method returns null
      * 
      * @param key The key of the searched value
@@ -178,6 +177,15 @@ public class Page<K, V> implements Clone
     
     
     /**
+     * Generate a new recordId for this page
+     */
+    /* No qualifier */ void setRecordId()
+    {
+        this.recordId = btree.generateRecordId();
+    }
+    
+    
+    /**
      * @return The page's revision
      */
     /* No qualifier */ long getRevision()
@@ -307,7 +315,7 @@ public class Page<K, V> implements Clone
      * @param value Inserted value
      * @return Either a modified Page or an Overflow element if the Page was full
      */
-    /* No qualifier */ InsertResult<K, V> insert( long revision, K key, V value )
+    /* No qualifier */ Page<K, V> insert( long revision, K key, V value )
     {
         if ( isLeaf )
         {
@@ -332,13 +340,13 @@ public class Page<K, V> implements Clone
             }
             else
             {
-                InsertResult<K, V> result = children[index].insert( revision, key,
value );
+                Page<K, V> result = children[index].insert( revision, key, value );
                 
-                if ( result instanceof PageResult )
+                if ( result.recordId != OVERFLOW )
                 {
                     // The result is a modified page, we have to replace the associated
                     // child and to copy the current page with a new revision
-                    return replaceChild( revision, (PageResult<K, V>)result, index
);
+                    return replaceChild( revision, result, index );
                 }
                 else
                 {
@@ -348,15 +356,14 @@ public class Page<K, V> implements Clone
                     {
                         // The current page has some room : inject the overflow element in
                         // a copy of the current page and return it
-                        return insertOverflow( revision, (OverflowResult<K, V>)result,
index );
+                        return insertOverflow( revision, result, index );
                     }
                     else
                     {
                         // We don't have enough room in the current page : we split it and
                         // return the new overflow element we computed.
-                        OverflowResult<K, V> overflow = (OverflowResult<K, V>)result;
-                        
-                        return addAndSplit( revision, index, overflow.pivotKey, overflow.pivotValue,
overflow.leftPage, overflow.rightPage );
+                        return addAndSplit( revision, result.keys[0], result.values[0],
+                            result.children[0], result.children[1], index );
                     }
                 }
             }
@@ -373,7 +380,7 @@ public class Page<K, V> implements Clone
      * @param value The value
      * @return The copied Page
      */
-    private InsertResult<K, V> insertInLeaf( long revision, K key, V value )
+    private Page<K, V> insertInLeaf( long revision, K key, V value )
     {
         // Find the key into this leaf
         int index = findIndex( key );
@@ -395,7 +402,7 @@ public class Page<K, V> implements Clone
         else
         {
             // The Page is already full : we split it and return the overflow element
-            return addAndSplit( revision, index, key, value, null, null );
+            return addAndSplit( revision, key, value, null, null, index );
         }
     }
 
@@ -409,12 +416,12 @@ public class Page<K, V> implements Clone
      * @param index The position of the modified Page
      * @return the copy of this page
      */
-    private InsertResult<K, V> replaceChild( long revision, PageResult<K, V>
pageResult, int index )
+    private Page<K, V> replaceChild( long revision, Page<K, V> page, int index
)
     {
         Page<K, V> newPage = copy( revision );
-        newPage.children[index] = pageResult.page;
+        newPage.children[index] = page;
         
-        return new PageResult<K, V>( newPage );
+        return newPage;
     }
     
     
@@ -427,36 +434,27 @@ public class Page<K, V> implements Clone
      * @param index The position of the overflow element in the current page
      * @return The modified page containing the overflow element
      */
-    @SuppressWarnings("unchecked")
-    private InsertResult<K, V> insertOverflow( long revision, OverflowResult<K,
V> result, int index )
+    private Page<K, V> insertOverflow( long revision, Page<K, V> result, int
index )
     {
-        Page<K, V> newPage = new Page<K, V>();
-        newPage.btree = btree;
-        newPage.revision = revision;
-        newPage.isLeaf = false;
-        newPage.recordId = btree.generateRecordId();
-        newPage.nbElems = nbElems + 1;
+        Page<K, V> newPage = new Page<K, V>( btree, revision, nbElems + 1, false
);
               
-        newPage.keys = (K[])new Object[newPage.nbElems];
         System.arraycopy( keys, 0, newPage.keys, 0, index );
-        newPage.keys[index] = result.pivotKey;
+        newPage.keys[index] = result.keys[0];
         System.arraycopy( keys, index, newPage.keys, index + 1, newPage.nbElems - ( index
+ 1 ) );
               
-        newPage.values = (V[])new Object[newPage.nbElems];
         System.arraycopy( values, 0, newPage.values, 0, index );
-        newPage.values[index] = result.pivotValue;
+        newPage.values[index] = result.values[0];
         System.arraycopy( values, index, newPage.values, index + 1, newPage.nbElems - ( index
+ 1 ) );
 
         if ( ! isLeaf )
         {
-            newPage.children = new Page[newPage.nbElems + 1];
             System.arraycopy( children, 0, newPage.children, 0, index );
-            newPage.children[index] = result.leftPage;
-            newPage.children[index + 1] = result.rightPage;
+            newPage.children[index] = result.children[0];
+            newPage.children[index + 1] = result.children[1];
             System.arraycopy( children, index + 1, newPage.children, index + 2, newPage.nbElems
+ 1 - ( index + 2 ) );
         }
 
-        return new PageResult<K, V>( newPage );
+        return newPage;
     }
     
     
@@ -477,9 +475,11 @@ public class Page<K, V> implements Clone
      * @param right The right child of the added element
      * @return An OverflowPage containing the pivor, and the new left and right pages
      */
-    private InsertResult<K, V> addAndSplit( long revision, int index, K key, V value,
Page<K, V> left, Page<K, V> right )
+    private Page<K, V> addAndSplit( long revision, K key, V value, Page<K, V>
left, Page<K, V> right, int index )
     {
-        OverflowResult<K, V> result = new OverflowResult<K, V>();
+        Page<K, V> newPage = new Page<K, V>( btree, revision, 1, false );
+        newPage.recordId = OVERFLOW;
+
         Page<K, V> child = null;
         
         int pivot = ( nbElems + 1 ) / 2;
@@ -487,45 +487,45 @@ public class Page<K, V> implements Clone
         // i == P -> left = a[0..P-1], median = X, right = a[P..N-1]
         if ( index == pivot )
         {
-            result.pivotKey = key;
-            result.pivotValue = value;
-            result.leftPage = copyHalfPage( revision, 0, pivot - 1, left );
-            result.rightPage = copyHalfPage( revision, pivot, nbElems - 1, right );
+            newPage.keys[0] = key;
+            newPage.values[0] = value;
+            newPage.children[0] = copyHalfPage( revision, 0, pivot - 1, left );
+            newPage.children[1] = copyHalfPage( revision, pivot, nbElems - 1, right );
 
-            return result;
+            return newPage;
         }
 
         // i < P -> left = a[0..index, X, index+1..P - 2], median = a[P-1], right =
a[P..N-1]
         if ( index < pivot )
         {
-            result.pivotKey = keys[pivot - 1];
-            result.pivotValue = values[pivot - 1];
-            result.leftPage = copyAndInsert( revision, key, value, left, right, index, 0,
pivot - 1 );
+            newPage.keys[0] = keys[pivot - 1];
+            newPage.values[0] = values[pivot - 1];
+            newPage.children[0] = copyAndInsert( revision, key, value, left, right, index,
0, pivot - 1 );
             
             if ( !isLeaf )
             {
                 child = children[pivot];
             }
             
-            result.rightPage = copyHalfPage( revision, pivot, nbElems - 1, child );
+            newPage.children[1] = copyHalfPage( revision, pivot, nbElems - 1, child );
 
-            return result;
+            return newPage;
         }
         else
         {
             // i < P -> left = a[0..P - 1], median = a[P], right = a[P+1..N-1]
-            result.pivotKey = keys[pivot];
-            result.pivotValue = values[pivot];
+            newPage.keys[0] = keys[pivot];
+            newPage.values[0] = values[pivot];
 
             if ( !isLeaf )
             {
                 child = children[pivot];
             }
             
-            result.leftPage = copyHalfPage( revision, 0, pivot - 1, child );
-            result.rightPage = copyAndInsert( revision, key, value, left, right, index, pivot
+ 1, nbElems );
+            newPage.children[0] = copyHalfPage( revision, 0, pivot - 1, child );
+            newPage.children[1] = copyAndInsert( revision, key, value, left, right, index,
pivot + 1, nbElems );
 
-            return result;
+            return newPage;
         }
     }
     
@@ -538,24 +538,15 @@ public class Page<K, V> implements Clone
      * @param end The end in the original page
      * @return A page containing all the elements in [start..end] in the original page.
      */
-    @SuppressWarnings("unchecked")
     private Page<K, V> copyHalfPage( long revision, int start, int end, Page<K,
V> child )
     {
-        Page<K, V> newPage = new Page<K, V>();
-        newPage.btree = btree;
-        newPage.revision = revision;
-        newPage.isLeaf = isLeaf;
-        newPage.recordId = btree.generateRecordId();
-        newPage.nbElems = end - start + 1;
-        newPage.keys = (K[])new Object[newPage.nbElems];
+        Page<K, V> newPage = new Page<K, V>( btree, revision, end - start + 1,
isLeaf );
+        
         System.arraycopy( keys, start, newPage.keys, 0, newPage.nbElems );
-        newPage.values = (V[])new Object[newPage.nbElems];
         System.arraycopy( values, start, newPage.values, 0, newPage.nbElems );
     
         if ( ! isLeaf )
         {
-            newPage.children = new Page[newPage.nbElems + 1];
-            
             if ( start == 0 )
             {
                 // The child has to be copied on the right of the left page
@@ -634,32 +625,23 @@ public class Page<K, V> implements Clone
      * @param end The position in the original page to stop the copy
      * @return A new page containing half of the split page plus the overflow element
      */
-    @SuppressWarnings("unchecked")
     private Page<K, V> copyAndInsert( long revision, K pivotKey, V pivotValue, Page<K,
V> leftPage,
         Page<K, V> rightPage, int index, int start, int end )
     {
-        Page<K, V> newPage = new Page<K, V>();
-        newPage.btree = btree;
-        newPage.revision = revision;
-        newPage.isLeaf = isLeaf;
-        newPage.recordId = btree.generateRecordId();
-        newPage.nbElems = end - start + 1;
+        Page<K, V> newPage = new Page<K, V>( btree, revision, end - start + 1,
isLeaf );
         
         int middle = index - start;
         
-        newPage.keys = (K[])new Object[newPage.nbElems];
         arrayCopy( keys, start, newPage.keys, 0, middle );
         newPage.keys[middle] = pivotKey;
         System.arraycopy( keys, index, newPage.keys, middle + 1, newPage.nbElems - ( middle
+ 1 ) );
         
-        newPage.values = (V[])new Object[newPage.nbElems];
         System.arraycopy( values, start, newPage.values, 0, middle );
         newPage.values[middle] = pivotValue;
         System.arraycopy( values, index, newPage.values, middle + 1, newPage.nbElems - (
middle + 1 ) );
 
         if ( ! isLeaf )
         {
-            newPage.children = new Page[newPage.nbElems + 1];
             System.arraycopy( children, start, newPage.children, 0, middle );
             newPage.children[middle] = leftPage;
             newPage.children[middle + 1] = rightPage;
@@ -678,12 +660,12 @@ public class Page<K, V> implements Clone
      * @param value the new value
      * @return The copied page
      */
-    private InsertResult<K, V> replaceValue( long revision, int index, V value )
+    private Page<K, V> replaceValue( long revision, int index, V value )
     {
         Page<K, V> newPage = copy( revision );
         newPage.values[index] = value;
         
-        return new PageResult<K, V>( newPage );
+        return newPage;
     }
     
     
@@ -697,21 +679,14 @@ public class Page<K, V> implements Clone
      * @param value The value to insert
      * @return The modified page with the <K,V> element added
      */
-    @SuppressWarnings("unchecked")
-    private InsertResult<K, V> addElement( long revision, int index, K key, V value
)
+    private Page<K, V> addElement( long revision, int index, K key, V value )
     {
-        Page<K, V> newPage = new Page<K, V>();
-        newPage.btree = btree;
-        newPage.revision = revision;
-        newPage.isLeaf = isLeaf;
-        newPage.recordId = btree.generateRecordId();
-        newPage.nbElems = nbElems + 1;
-        newPage.keys = (K[])new Object[newPage.nbElems];
+        Page<K, V> newPage = new Page<K, V>( btree, revision, nbElems + 1, true
);
+
         copyAndAdd( keys, newPage.keys, key, index );
-        newPage.values = (V[])new Object[newPage.nbElems];
         copyAndAdd( values, newPage.values, value, index );
 
-        return new PageResult<K, V>( newPage );
+        return newPage;
     }
     
     
@@ -764,23 +739,15 @@ public class Page<K, V> implements Clone
      * @param revision The new revision
      * @return The copied page
      */
-    @SuppressWarnings("unchecked")
     private Page<K, V> copy( long revision )
     {
-        Page<K, V> newPage = new Page<K, V>();
-        newPage.btree = btree;
-        newPage.revision = revision;
-        newPage.isLeaf = isLeaf;
-        newPage.recordId = btree.generateRecordId();
-        newPage.nbElems = nbElems;
-        newPage.keys = (K[])new Object[newPage.nbElems];
+        Page<K, V> newPage = new Page<K, V>( btree, revision, nbElems, isLeaf
);
+
         System.arraycopy( keys, 0, newPage.keys, 0, newPage.nbElems );
-        newPage.values = (V[])new Object[newPage.nbElems];
         System.arraycopy( values, 0, newPage.values, 0, newPage.nbElems );
 
         if ( ! newPage.isLeaf )
         {
-            newPage.children = new Page[newPage.nbElems + 1];
             System.arraycopy( children, 0, newPage.children, 0, newPage.nbElems + 1 );
         }
 
@@ -817,73 +784,6 @@ public class Page<K, V> implements Clone
 
 
     /**
-     *  Result from insert() method call. If the insertion has created
-     *  a new page, it will be contained in the overflow field.
-     *  If the inserted element already exist, then we will store
-     *  the existing element.
-     */
-    /* No qualifier */ interface InsertResult<K, V>
-    {
-    }
-    
-    /**
-     * A inner class used to store a split page. It has a pivot element
-     * and a left and right page.
-     */
-    static class OverflowResult<K, V> implements InsertResult<K, V>
-    {
-        /** The Left page if it has been split, or the new page containing the new value
*/
-        Page<K, V> leftPage;
-        
-        /** The right page if it has been split, null otherwise*/
-        Page<K, V> rightPage;
-
-        /** The Key that must be copied in the parent page if the page was full */
-        K pivotKey;
-        
-        /** The Value that must be copied in the parent page if the page was full */
-        V pivotValue;
-        
-        /**
-         * @see Object#toString()
-         */
-        public String toString()
-        {
-            // This is a split page
-            return "Split Page [" + leftPage.recordId + ", r" + leftPage.revision + "], ["
+
-                rightPage.recordId + ", r" + rightPage.revision + "], <" + pivotKey +
"/" + pivotValue + ">";
-        }
-    }
-    
-    
-    /**
-     * An inner class used to store a modified page.
-     */
-    static class PageResult<K, V> implements InsertResult<K, V>
-    {
-        /** The modified page */
-        Page<K, V> page;
-        
-        /**
-         * Create the instance of a PageResult
-         * @param page The modified page
-         */
-        private PageResult( Page<K, V> page )
-        {
-            this.page = page;
-        }
-        
-        /**
-         * @see Object#toString()
-         */
-        public String toString()
-        {
-            return "Modified Page [" + page.recordId + ", r" + page.revision + "]";
-        }
-    }
-    
-    
-    /**
      * @see Object#toString()
      */
     public String toString()



Mime
View raw message