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/19 23:37:31 UTC
svn commit: r1233613 -
/directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/Page.java
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 )
{