directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1233613 - /directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Page.java
Date Thu, 19 Jan 2012 22:37:31 GMT
Author: elecharny
Date: Thu Jan 19 22:37:31 2012
New Revision: 1233613

URL: http://svn.apache.org/viewvc?rev=1233613&view=rev
Log:
Did some methods renaming and added some Javadoc

Modified:
    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/Page.java
URL: http://svn.apache.org/viewvc/directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Page.java?rev=1233613&r1=1233612&r2=1233613&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
Thu Jan 19 22:37:31 2012
@@ -184,11 +184,34 @@ public class Page<K, V> implements Clone
     
     
     /**
-     * Find the position in the current page where we will insert
-     * the new key
-     * @param array
-     * @param value
-     * @return
+     * Find the position of the given key in the current page. If the key exists,
+     * we will return a negative value representing the position of the key in the page.
+     * If the key does not exists, we will return the position of the key immediately
+     * higher than the given key.<br/><br/>
+     * For instance, if a Page contains the following keys : <br/>
+     * <pre>
+     *   0   1   2
+     * +---+---+---+
+     * | 2 | 4 | 6 |
+     * +---+---+---+
+     * </pre>
+     * searching for the following keys will return the following position :<br/>
+     * <ul>
+     * <li>1 ->  0</li>
+     * <li>2 -> -1</li>
+     * <li>3 ->  1</li>
+     * <li>4 -> -2</li>
+     * <li>5 ->  2</li>
+     * <li>6 -> -3</li>
+     * <li>7 ->  3</li>
+     * </ul>
+     * 
+     * Note that for keys found in the page, the returned negative position is not zero-based,
+     * we have subtracted 1 in order to avoid a collision with 0. To find the actual position,
+     * we must compute <code>- (index + 1)</code>
+     * 
+     * @param key the key to find
+     * @return the 0-based index in this page
      */
     private int findIndex( K key )
     {
@@ -246,21 +269,29 @@ public class Page<K, V> implements Clone
     
     
     /**
-     * Insert the given key and value into this page.
+     * Insert the given key and value into this page. We first find the place were to
+     * inject the <K,V> into the tree, by recursively browsing the pages :<br/>
+     * <ul>
+     * <li>If the index is below zero, the key is present in the Page : we modify the
+     * value and return</li>
+     * <li>If the page is a node, we have to go down to the right child page</li>
+     * <li>If the page is a leaf, we insert the new <K,V> element into the page,
and if
+     * the Page is full, we split it and propagate the new pivot up into the tree</li>
+     * </ul>
      * <p>
-     *
-     * @param height Height of the current BPage (zero is leaf page)
-     * @param key Insert key
-     * @param value Insert value
-     * @param replace Set to true to replace the existing value, if one exists.
-     * @return Insertion result containing existing value OR a BPage if the key
-     *         was inserted and provoked a BPage overflow.
+     * 
+     * @param revision The new revision for the modified pages
+     * @param key Inserted key
+     * @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 */ InsertResult<K, V> insert( long revision, K key, V value )
     {
         if ( isLeaf )
         {
-            return insertPage( revision, key, value );
+            // The current page is a leaf : we have to insert the <K,V> element
+            // into a copied page with a new revision
+            return insertInLeaf( revision, key, value );
         }
         else
         {
@@ -270,8 +301,11 @@ public class Page<K, V> implements Clone
             
             if ( index < 0 )
             {
+                // Found key.
                 index = - ( index + 1 );
                 
+                // The key already exists, we just have to replace the associated value.
+                // We still have to create a copy of the current page with a new revision
                 return replaceValue( revision, index, value );
             }
             else
@@ -280,16 +314,24 @@ public class Page<K, V> implements Clone
                 
                 if ( result instanceof PageResult )
                 {
+                    // 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
);
                 }
                 else
                 {
+                    // We've get back an Overflow : the new <K,V> element we got back
+                    // from the split has to be inserted into the current page
                     if ( nbElems < btree.pageSize )
                     {
-                        return insert( revision, (OverflowResult<K, V>)result, index
);
+                        // 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 );
                     }
                     else
                     {
+                        // We don't have enough room in the current page : we split it and
+                        // return the new overflow element we computed.
                         return split( revision, (OverflowResult<K, V>)result, index
);
                     }
                 }
@@ -298,38 +340,51 @@ public class Page<K, V> implements Clone
     }
     
     
-    private InsertResult<K, V> insertPage( long revision, K key, V value )
+    /**
+     * Insert a new <K,V> element in a leaf page. The current page will be copied,
with a new revision
+     * and the K and V values will be injected.
+     * 
+     * @param revision The new page revision
+     * @param key The key
+     * @param value The value
+     * @return The copied Page
+     */
+    private InsertResult<K, V> insertInLeaf( long revision, K key, V value )
     {
+        // Find the key into this leaf
         int index = findIndex( key );
 
         if ( index < 0 )
         {
+            // We already have the key in the page : replace the value
+            // into a copy of this page
             index = - ( index + 1 );
-            Page<K, V> newPage = copy( revision );
-            newPage.values[index] = value;
             
-            return new PageResult<K, V>( newPage );
+            return replaceValue( revision, index, value );
         }
         
         if ( nbElems < btree.pageSize )
         {
-            if ( index < 0 )
-            {
-                index = - ( index + 1 );
-                return replaceValue( revision, index, value );
-            }
-            else
-            {
-                return insert( revision, index, key, value );
-            }
+            // The Page can contain the added element. We insert it into a copied page
+            return addElement( revision, index, key, value );
         }
         else
         {
-            return splitLeaf( revision, index, key, value, null, null );
+            // The Page is already full : we split it and return the overflow element
+            return addAndSplit( revision, index, key, value, null, null );
         }
     }
 
     
+    /**
+     * Copy the current page, and update the children that has been modified. The new page
+     * will have the same revision than the modified child page.
+     * 
+     * @param revision The revision
+     * @param pageResult The modified Page
+     * @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 )
     {
         Page<K, V> newPage = copy( revision );
@@ -340,7 +395,7 @@ public class Page<K, V> implements Clone
     
     
     @SuppressWarnings("unchecked")
-    private InsertResult<K, V> insert( long revision, OverflowResult<K, V> result,
int index )
+    private InsertResult<K, V> insertOverflow( long revision, OverflowResult<K,
V> result, int index )
     {
         Page<K, V> newPage = new Page<K, V>();
         newPage.btree = btree;
@@ -372,7 +427,24 @@ public class Page<K, V> implements Clone
     }
     
     
-    private InsertResult<K, V> splitLeaf( long revision, int index, K key, V value,
Page<K, V> left, Page<K, V> right )
+    /**
+     * Split a full page into two new pages, a left, a right and a pivot element. The new
pages will
+     * each contains half of the original elements. <br/>
+     * The pivot will be computed, depending on the place
+     * we will inject the newly added element. <br/>
+     * If the newly added element is in the middle, we will use it
+     * as a pivot. Otherwise, we will use either the last element in the left page if the
element is added
+     * on the left, or the first element in the right page if it's added on the right.
+     * 
+     * @param revision The new revision for all the created pages
+     * @param index The position of the insertion of the new element
+     * @param key The key to add
+     * @param value The value to add
+     * @param left The left child of the added element
+     * @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 )
     {
         OverflowResult<K, V> result = new OverflowResult<K, V>();
         
@@ -383,8 +455,8 @@ public class Page<K, V> implements Clone
         {
             result.pivotKey = key;
             result.pivotValue = value;
-            result.leftPage = copy( revision, 0, pivot - 1 );
-            result.rightPage = copy( revision, pivot, nbElems - 1 );
+            result.leftPage = copyHalfPage( revision, 0, pivot - 1, left );
+            result.rightPage = copyHalfPage( revision, pivot, nbElems - 1, right );
 
             return result;
         }
@@ -395,7 +467,7 @@ public class Page<K, V> implements Clone
             result.pivotKey = keys[pivot - 1];
             result.pivotValue = values[pivot - 1];
             result.leftPage = copyAndInsert( revision, key, value, left, right, index, 0,
pivot - 1 );
-            result.rightPage = copy( revision, pivot, nbElems - 1 );
+            result.rightPage = copyHalfPage( revision, pivot, nbElems - 1 );
 
             return result;
         }
@@ -404,7 +476,7 @@ public class Page<K, V> implements Clone
             // i < P -> left = a[0..P - 1], median = a[P], right = a[P+1..N-1]
             result.pivotKey = keys[pivot];
             result.pivotValue = values[pivot];
-            result.leftPage = copy( revision, 0, pivot - 1);
+            result.leftPage = copyHalfPage( revision, 0, pivot - 1);
             result.rightPage = copyAndInsert( revision, key, value, left, right, index, pivot
+ 1, nbElems );
 
             return result;
@@ -423,8 +495,8 @@ public class Page<K, V> implements Clone
         {
             result.pivotKey = overflow.pivotKey;
             result.pivotValue = overflow.pivotValue;
-            result.leftPage = copy( revision, 0, pivot - 1 );
-            result.rightPage = copy( revision, pivot, nbElems - 1 );
+            result.leftPage = copyHalfPage( revision, 0, pivot - 1 );
+            result.rightPage = copyHalfPage( revision, pivot, nbElems - 1 );
 
             return result;
         }
@@ -435,7 +507,7 @@ public class Page<K, V> implements Clone
             result.pivotKey = keys[pivot - 1];
             result.pivotValue = values[pivot - 1];
             result.leftPage = copyAndInsert( revision, key, value, index, 0, pivot - 1 );
-            result.rightPage = copy( revision, pivot, nbElems - 1 );
+            result.rightPage = copyHalfPage( revision, pivot, nbElems - 1 );
 
             return result;
         }
@@ -444,7 +516,7 @@ public class Page<K, V> implements Clone
             // i < P -> left = a[0..P - 1], median = a[P], right = a[P+1..N-1]
             result.pivotKey = keys[pivot];
             result.pivotValue = values[pivot];
-            result.leftPage = copy( revision, 0, pivot - 1);
+            result.leftPage = copyHalfPage( revision, 0, pivot - 1);
             result.rightPage = copyAndInsert( revision, key, value, index, pivot + 1, nbElems
);
 
             return result;
@@ -452,8 +524,16 @@ public class Page<K, V> implements Clone
     }
     
 
+    /**
+     * Copy half of a full page into a new page This method is called when a split of a page
is done.
+     * 
+     * @param revision The new page revision
+     * @param start The starting point in the original page
+     * @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> copy( long revision, int start, int end )
+    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;
@@ -469,7 +549,19 @@ public class Page<K, V> implements Clone
         if ( ! isLeaf )
         {
             newPage.children = new Page[newPage.nbElems + 1];
-            System.arraycopy( children, start, newPage.children, 0, newPage.nbElems );
+            
+            if ( start == 0 )
+            {
+                // The child has to be copied on the right of the left page
+                System.arraycopy( children, start, newPage.children, 0, newPage.nbElems );
+                newPage.children[newPage.nbElems] = child;
+            }
+            else
+            {
+                // The child has to be copied on the left of the right page
+                newPage.children[start] = child;
+                System.arraycopy( children, start, newPage.children, 1, newPage.nbElems );
+            }
         }
     
         return newPage;
@@ -550,6 +642,14 @@ public class Page<K, V> implements Clone
     }
     
     
+    /**
+     * Copy the current page, and replace the value at the position we hav found the key.
+     * 
+     * @param revision The new page revision
+     * @param index The position of the key in the page
+     * @param value the new value
+     * @return The copied page
+     */
     private InsertResult<K, V> replaceValue( long revision, int index, V value )
     {
         Page<K, V> newPage = copy( revision );
@@ -559,8 +659,18 @@ public class Page<K, V> implements Clone
     }
     
     
+    /**
+     * Add a new <K, V> into a copy of the current page at a given position. We return
the
+     * modified page. The new page will have one more element than the current page.
+     * 
+     * @param revision The revision of the modified page
+     * @param index The position into the page
+     * @param key The key to insert
+     * @param value The value to insert
+     * @return The modified page with the <K,V> element added
+     */
     @SuppressWarnings("unchecked")
-    private InsertResult<K, V> insert( long revision, int index, K key, V value )
+    private InsertResult<K, V> addElement( long revision, int index, K key, V value
)
     {
         Page<K, V> newPage = new Page<K, V>();
         newPage.btree = btree;
@@ -569,23 +679,63 @@ public class Page<K, V> implements Clone
         newPage.recordId = btree.generateRecordId();
         newPage.nbElems = nbElems + 1;
         newPage.keys = (K[])new Object[newPage.nbElems];
-        copyArray( keys, newPage.keys, key, index );
+        copyAndAdd( keys, newPage.keys, key, index );
         newPage.values = (V[])new Object[newPage.nbElems];
-        copyArray( values, newPage.values, value, index );
+        copyAndAdd( values, newPage.values, value, index );
 
         return new PageResult<K, V>( newPage );
     }
     
     
-    private void copyArray( Object[] src, Object[] dest, Object object, int index )
+    /**
+     * Copy an array of object to a new array, inserting an object into the array
+     * at a given position in the initial array. <br/>
+     * 
+     * <pre>
+     *   0   1   2
+     * +---+---+---
+     * | 2 | 4 | 6 |
+     * +---+---+---+
+     * 
+     * If we add A at position 0 :
+     * 
+     * +---+---+---+---
+     * | A | 2 | 4 | 6 |
+     * +---+---+---+---+
+     * 
+     * If we add B at position 2 :
+     * 
+     * +---+---+---+---
+     * | 2 | 4 | B | 6 |
+     * +---+---+---+---+
+     * 
+     * If we add C at position 3 :
+     * 
+     * +---+---+---+---
+     * | 2 | 4 | 6 | C |
+     * +---+---+---+---+
+     * </pre>
+     * 
+     * @param src The initial array
+     * @param dest The copied array
+     * @param object The object to add into the destination array
+     * @param index The position of the added object in the initial array
+     */
+    private void copyAndAdd( Object[] src, Object[] dest, Object object, int index )
     {
         int length = dest.length;
         System.arraycopy( src, 0, dest, 0, index );
         dest[index] = object;
         System.arraycopy( src, index, dest, index+1, length - ( index + 1 ) );
     }
-
     
+    
+    /**
+     * Copy the current page and all of the keys, values and children, if it's not a leaf.
+     * 
+     * @param revision The new revision
+     * @return The copied page
+     */
     @SuppressWarnings("unchecked")
     private Page<K, V> copy( long revision )
     {



Mime
View raw message