directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1233916 - /directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Page.java
Date Fri, 20 Jan 2012 14:08:07 GMT
Author: elecharny
Date: Fri Jan 20 14:08:07 2012
New Revision: 1233916

URL: http://svn.apache.org/viewvc?rev=1233916&view=rev
Log:
o Fixed the split method
o 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=1233916&r1=1233915&r2=1233916&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
Fri Jan 20 14:08:07 2012
@@ -332,7 +332,10 @@ public class Page<K, V> implements Clone
                     {
                         // 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
);
+                        OverflowResult<K, V> overflow = (OverflowResult<K, V>)result;
+                        
+                        return addAndSplit( revision, index, overflow.pivotKey, overflow.pivotValue,
overflow.leftPage, overflow.rightPage );
+                        //return split( revision, (OverflowResult<K, V>)result, index
);
                     }
                 }
             }
@@ -447,6 +450,7 @@ public class Page<K, V> implements Clone
     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>();
+        Page<K, V> child = null;
         
         int pivot = ( nbElems + 1 ) / 2;
 
@@ -467,7 +471,13 @@ 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 = copyHalfPage( revision, pivot, nbElems - 1 );
+            
+            if ( !isLeaf )
+            {
+                child = children[pivot];
+            }
+            
+            result.rightPage = copyHalfPage( revision, pivot, nbElems - 1, child );
 
             return result;
         }
@@ -476,7 +486,13 @@ 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 = copyHalfPage( revision, 0, pivot - 1);
+
+            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 );
 
             return result;
@@ -484,6 +500,7 @@ public class Page<K, V> implements Clone
     }
     
     
+    /*
     private InsertResult<K, V> split( long revision, OverflowResult<K, V> overflow,
int index )
     {
         OverflowResult<K, V> result = new OverflowResult<K, V>();
@@ -495,8 +512,8 @@ public class Page<K, V> implements Clone
         {
             result.pivotKey = overflow.pivotKey;
             result.pivotValue = overflow.pivotValue;
-            result.leftPage = copyHalfPage( revision, 0, pivot - 1 );
-            result.rightPage = copyHalfPage( revision, pivot, nbElems - 1 );
+            result.leftPage = copyHalfPage( revision, 0, pivot - 1, overflow.leftPage );
+            result.rightPage = copyHalfPage( revision, pivot, nbElems - 1, overflow.rightPage
);
 
             return result;
         }
@@ -506,8 +523,8 @@ 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 = copyHalfPage( revision, pivot, nbElems - 1 );
+            result.leftPage = copyAndInsert( revision, overflow, index, 0, pivot - 1 );
+            result.rightPage = copyHalfPage( revision, pivot, nbElems - 1, children[pivot]
);
 
             return result;
         }
@@ -516,12 +533,13 @@ 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 = copyHalfPage( revision, 0, pivot - 1);
-            result.rightPage = copyAndInsert( revision, key, value, index, pivot + 1, nbElems
);
+            result.leftPage = copyHalfPage( revision, 0, pivot - 1, children[pivot] );
+            result.rightPage = copyAndInsert( revision, overflow, index, pivot + 1, nbElems
);
 
             return result;
         }
     }
+    */
     
 
     /**
@@ -608,8 +626,19 @@ public class Page<K, V> implements Clone
     }
 
     
+    /**
+     * Copy a split page and insert the overflow element into it.
+     * 
+     * @param revision The revision for the new created page
+     * @param overflow The element to add in the new page
+     * @param index The position where to insert the element
+     * @param start The position in the original page to start the copy from
+     * @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 key, V value, Page<K, V>
left, Page<K, V> right, int index, int start, int end )
+    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;
@@ -622,20 +651,21 @@ public class Page<K, V> implements Clone
         
         newPage.keys = (K[])new Object[newPage.nbElems];
         arrayCopy( keys, start, newPage.keys, 0, middle );
-        newPage.keys[middle] = key;
+        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] = value;
+        newPage.values[middle] = pivotValue;
         System.arraycopy( values, index, newPage.values, middle + 1, newPage.nbElems - (
middle + 1 ) );
 
         if ( ! isLeaf )
         {
-            newPage.children = (Page<K, V>[])new Object[newPage.nbElems + 1];
+            newPage.children = new Page[newPage.nbElems + 1];
             System.arraycopy( children, start, newPage.children, 0, middle );
-            newPage.children[middle] = this;
-            System.arraycopy( children, index, newPage.children, middle + 1, newPage.nbElems
- middle );
+            newPage.children[middle] = leftPage;
+            newPage.children[middle + 1] = rightPage;
+            System.arraycopy( children, index + 1, newPage.children, middle + 2, newPage.nbElems
- ( middle + 1 ) );
         }
 
         return newPage;



Mime
View raw message