You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by el...@apache.org on 2012/01/20 15:08:07 UTC
svn commit: r1233916 -
/directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Page.java
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;