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/02/14 00:56:41 UTC
svn commit: r1243749 - in /directory/sandbox/elecharny/shared-mvbt/src:
main/java/org/apache/directory/btree/BTree.java
main/java/org/apache/directory/btree/Page.java
test/java/org/apache/directory/btree/PageTest.java
Author: elecharny
Date: Mon Feb 13 23:56:40 2012
New Revision: 1243749
URL: http://svn.apache.org/viewvc?rev=1243749&view=rev
Log:
o Added a test on BTree removal
o Added some code to handle BTree removal (not completed yet)
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
directory/sandbox/elecharny/shared-mvbt/src/test/java/org/apache/directory/btree/PageTest.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=1243749&r1=1243748&r2=1243749&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 Mon Feb 13 23:56:40 2012
@@ -197,21 +197,40 @@ public class BTree<K, V>
*/
public V remove( K key )
{
- if ( rootPage == null )
+ if ( key == null )
{
- // No pages in the BTree just return
- return null;
+ throw new IllegalArgumentException( "Key must not be null" );
}
- ModifiedPage<K, V> removedPage = rootPage.remove( rootPage.getRevision(), key );
-
- if ( removedPage != null )
+ //acquireWriteLock();
+
+ try
{
- return removedPage.getValue();
+ if ( rootPage == null )
+ {
+ // No pages in the BTree just return
+ return null;
+ }
+
+ long revision = generateRevision();
+
+ ModifiedPage<K, V> removedPage = rootPage.remove( revision, key );
+
+ if ( removedPage != null )
+ {
+ rootPage = removedPage.getModifiedPage();
+ roots.put( revision, rootPage );
+
+ return removedPage.getValue();
+ }
+ else
+ {
+ return null;
+ }
}
- else
+ finally
{
- return null;
+ //releaseWriteLock()
}
}
@@ -292,7 +311,16 @@ public class BTree<K, V>
sb.append( "BTree" );
sb.append( "(height:" ).append(bTreeHeight );
sb.append( ", pageSize:" ).append( pageSize );
- sb.append( ", nbEntries:" ).append( rootPage.getNbElems() );
+
+ if ( rootPage != null )
+ {
+ sb.append( ", nbEntries:" ).append( rootPage.getNbElems() );
+ }
+ else
+ {
+ sb.append( ", nbEntries:" ).append( 0 );
+ }
+
//sb.append( ", rootId:" ).append( rootId );
sb.append( ", comparator:" );
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=1243749&r1=1243748&r2=1243749&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 Mon Feb 13 23:56:40 2012
@@ -70,7 +70,8 @@ package org.apache.directory.btree;
*/
private enum PageType
{
- ROOT,
+ ROOT_NODE,
+ ROOT_LEAF,
NODE,
LEAF
}
@@ -175,97 +176,329 @@ package org.apache.directory.btree;
/* No qualifier */ ModifiedPage<K, V> remove( long revision, K key )
{
int index = findIndex( key );
-
- if ( type == PageType.LEAF )
+
+ // either we found the key in the current page, or it's somewhere down in the tree
+ if ( index < 0 )
{
- // Either the leaf page contains the key, and we remove it from the page,
- // or we return null.
- if ( index < 0 )
+ // The key is in this page.
+ index = - ( index + 1 );
+
+ if ( ( type == PageType.LEAF ) || ( type == PageType.ROOT_LEAF ) )
{
- index = - ( index + 1 );
-
- // The key is in this page : get the value
V value = values[index];
- // Now, we remove it from the page. There is one case to consider :
- // if the page does not contains enough keys after the removal,
- // we will have to either move a sibling, or to merge the page with
- // its closest page.
+ Page<K, V> modifiedLeaf = null;
- if ( nbElems > btree.pageSize / 2 )
+ // If the page have 1 element remaining, no need to create a new page.
+ if ( nbElems > 1 )
{
- // The page will not contain enough elements after the removal
- return null;
+ modifiedLeaf = removeFromLeaf( this, revision, index );
+ }
+
+ // We return a page with one less element, and the removed value
+ return new ModifiedPage<K, V>( modifiedLeaf, value );
+ }
+ else
+ {
+ // This is a node page : we have to remove the value and to reorganize the children.
+ return null;
+ }
+ }
+ else
+ {
+ // not found in the current page : go down one page and handle the reorganization, if any
+ ModifiedPage<K, V> resultPage = remove( revision, key );
+ Page<K, V> modifiedChild = resultPage.getModifiedPage();
+ V removedValue = resultPage.getValue();
+
+ if ( modifiedChild == null )
+ {
+ // The child is empty (corner case when managing BTrees with pages containing
+ // only 2 elements.
+ }
+ else if ( modifiedChild.getNbElems() > btree.pageSize / 2 )
+ {
+ // The modified child has the same number of elements, there is no
+ // underflow. We just have to copy the current page and update the
+ // number of elements in it.
+ Page<K, V> newPage = replaceChild( revision, modifiedChild, index );
+ ModifiedPage<K, V> modifiedPage = new ModifiedPage<K, V>( newPage, removedValue );
+
+ return modifiedPage;
+ }
+ else
+ {
+ // The modified child is now too small. We have to reorganize it.
+ // We will have to check if one of the left or right child has
+ // one element we can use to replace the previous pivot
+ if ( index == 0 )
+ {
+ // The child is the leftmost child : we need to check the right child
+ }
+ else if ( index == nbElems )
+ {
+ // The child is the rightmost child : we need to check the left child
}
else
{
- // Ok, simply remove the element, and return the new page
- ModifiedPage<K, V> removed = copyAndRemove( revision, index );
+ // The child is in the middle. We have to check on the left and right child
+ // and to pick the child which has the higher number of elements
+ Page<K, V> leftPage = children[index - 1];
+ Page<K, V> rightPage = children[index + 1];
+ int nbElemsLeft = leftPage.nbElems;
+ int nbElemsRight = rightPage.nbElems;
- return removed;
+ if ( ( nbElemsLeft > nbElemsRight ) ||
+ ( ( nbElemsLeft == nbElemsRight ) && ( nbElemsLeft > btree.pageSize / 2 ) ) )
+ {
+ // First create a copy of the current page
+ Page<K, V> newPage = copy( revision );
+
+ // Use the left child higher value as the value to inject in the
+ // underflow page
+ int leftIndex = nbElemsLeft - 1;
+ V leftValue = leftPage.values[leftIndex];
+ K leftKey = leftPage.keys[leftIndex];
+ Page<K, V> newLeftPage = removeFromLeaf( leftPage, revision, leftIndex );
+
+ // Replace the left page reference
+ newPage.children[index - 1] = newLeftPage;
+
+ // Change the pivot element and move the old one in the overflow page
+ V movedValue = values[index];
+ K movedKey = keys[index];
+ newPage.values[index] = leftValue;
+ newPage.keys[index] = leftKey;
+ Page<K, V> newModifiedChild = modifiedChild.addElement( revision, 0, movedKey, movedValue );
+ newPage.children[index] = newModifiedChild;
+
+ ModifiedPage<K, V> modifiedPage = new ModifiedPage<K, V>( newPage, removedValue );
+
+ return modifiedPage;
+ }
+ else if ( nbElemsLeft < nbElemsRight )
+ {
+ // First create a copy of the current page
+ Page<K, V> newPage = copy( revision );
+
+ // Use the right child lower value as the value to inject in the
+ // underflow page
+ int rightIndex = 0;
+ V rightValue = rightPage.values[0];
+ K rightKey = rightPage.keys[0];
+ Page<K, V> newRightPage = removeFromLeaf( rightPage, revision, 0 );
+
+ // Replace the right page reference
+ newPage.children[index] = newRightPage;
+
+ // Change the pivot element and move the old one in the overflow page
+ V movedValue = values[index];
+ K movedKey = keys[index];
+ newPage.values[index] = rightValue;
+ newPage.keys[index] = rightKey;
+ Page<K, V> newModifiedChild = modifiedChild.addElement( revision, modifiedChild.nbElems, movedKey, movedValue );
+ newPage.children[index - 1] = newModifiedChild;
+
+ ModifiedPage<K, V> modifiedPage = new ModifiedPage<K, V>( newPage, removedValue );
+
+ return modifiedPage;
+ }
+ else
+ {
+ // Merge the left child and the modified child with the pivot value
+ // The new page will be pointed by the current page
+
+ }
}
}
- else
+ }
+ }
+ /*
+ switch ( type )
{
- if ( children[index].type == PageType.LEAF )
+ case LEAF :
+ // Remove the element from the leaf, and return the modified page.
+ ModifiedPage<K, V> modifiedPage = removeKey( revision, index );
+
+ return modifiedPage;
+
+ // Remove the key from the root page
+ ModifiedPage<K, V> modifiedPage = removeKey( revision, index );
+
+ return modifiedPage;
+
+ case NODE :
+ // Remove the key from the node page, and reorganize the page
+
+ case ROOT_NODE :
+ }
+ }
+ else
+ {
+ // The key is not in the current page : go down the tree
+ if ( type == PageType.LEAF )
+ {
+ // Either the leaf page contains the key, and we remove it from the page,
+ // or we return null.
+ if ( index < 0 )
{
- if ( children[index].nbElems > btree.pageSize / 2 )
+ index = - ( index + 1 );
+
+ // The key is in this page : get the value
+ V value = values[index];
+
+ // Now, we remove it from the page. There is one case to consider :
+ // if the page does not contains enough keys after the removal,
+ // we will have to either move a sibling, or to merge the page with
+ // its closest page.
+
+ if ( nbElems > btree.pageSize / 2 )
{
- // Ok, simply remove the element from the child,
- // and update the current page
- ModifiedPage<K, V> removed = children[index].copyAndRemove( revision, index );
+ // The page will not contain enough elements after the removal
+ return null;
}
else
{
- // Not enough elements in the child page after the removal :
- // try to move one element either from the left or the right page
- if ( index == 0 )
+ // Ok, simply remove the element, and return the new page
+ ModifiedPage<K, V> removed = copyAndRemove( revision, index );
+
+ return removed;
+ }
+ }
+ else
+ {
+ if ( children[index].type == PageType.LEAF )
+ {
+ if ( children[index].nbElems > btree.pageSize / 2 )
{
- // necessarily from the right...
- if ( children[1].type == PageType.LEAF )
- {
- }
+ // Ok, simply remove the element from the child,
+ // and update the current page
+ ModifiedPage<K, V> removed = children[index].copyAndRemove( revision, index );
}
else
{
-
+ // Not enough elements in the child page after the removal :
+ // try to move one element either from the left or the right page
+ if ( index == 0 )
+ {
+ // necessarily from the right...
+ if ( children[1].type == PageType.LEAF )
+ {
+ }
+ }
+ else
+ {
+
+ }
}
}
+
+ // It's a leaf, and it does not contain the key : that means
+ // the tree does not contain the key
+ return null;
}
-
- // It's a leaf, and it does not contain the key : that means
- // the tree does not contain the key
- return null;
}
- }
- else
- {
- // Go down into the child, and when done, depending on whether the underlying
- // page has been merged or not, we rebalance the current page
- ModifiedPage<K, V> modifiedPage = children[index].remove( revision, key );
-
- if ( modifiedPage != null )
+ else
{
- // We actually have found the value :
- Page<K, V> page = modifiedPage.getModifiedPage();
+ // Go down into the child, and when done, depending on whether the underlying
+ // page has been merged or not, we re-balance the current page
+ ModifiedPage<K, V> modifiedPage = children[index].remove( revision, key );
- if ( page.nbElems < btree.pageSize / 2 )
+ if ( modifiedPage != null )
{
- // The resulting page is too small.
+ // We actually have found the value :
+ Page<K, V> page = modifiedPage.getModifiedPage();
+
+ if ( page.nbElems < btree.pageSize / 2 )
+ {
+ // The resulting page is too small.
+ }
+ else
+ {
+
+ }
}
else
{
-
+ // The key was not found. Get out.
+ return modifiedPage;
}
+
+ return null;
}
- else
- {
- // The key was not found. Get out.
- return modifiedPage;
- }
-
+ }
+ }
+
+
+ /**
+ * Copy an array of object to a new array, removing an object from the original array
+ * at a given position in the original array. <br/>
+ *
+ * <pre>
+ * 0 1 2
+ * +---+---+---
+ * | 2 | 4 | 6 |
+ * +---+---+---+
+ *
+ * If we remove 2 at position 0 :
+ *
+ * +---+---
+ * | 4 | 6 |
+ * +---+---+
+ *
+ * If we remove 4 at position 1 :
+ *
+ * +---+---+
+ * | 2 | 6 |
+ * +---+---+
+ *
+ * If we remove 6 at position 2 :
+ *
+ * +---+---+
+ * | 2 | 4 |
+ * +---+---+
+ * </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 copyAndRemove( Object[] src, Object[] dest, int index )
+ {
+ int length = dest.length;
+
+ if ( index == 0 )
+ {
+ System.arraycopy( src, 1, dest, 0, length );
+ }
+ else if ( index == src.length - 1 )
+ {
+ System.arraycopy( src, 0, dest, 0, length );
+ }
+ else
+ {
+ System.arraycopy( src, 0, dest, 0, index );
+ System.arraycopy( src, index + 1, dest, index, length - index );
+ }
+ }
+
+
+ private Page<K, V> removeFromLeaf( Page<K, V> page, long revision, int index )
+ {
+ if ( nbElems == 1 )
+ {
+ // No more element, return null;
return null;
}
+
+ // Create a new page, with one less element in it
+ Page<K, V> newPage = new Page<K, V>( btree, revision, page.nbElems - 1, page.type );
+
+ copyAndRemove( page.keys, newPage.keys, index );
+ copyAndRemove( page.values, newPage.values, index );
+
+ return newPage;
}
Modified: directory/sandbox/elecharny/shared-mvbt/src/test/java/org/apache/directory/btree/PageTest.java
URL: http://svn.apache.org/viewvc/directory/sandbox/elecharny/shared-mvbt/src/test/java/org/apache/directory/btree/PageTest.java?rev=1243749&r1=1243748&r2=1243749&view=diff
==============================================================================
--- directory/sandbox/elecharny/shared-mvbt/src/test/java/org/apache/directory/btree/PageTest.java (original)
+++ directory/sandbox/elecharny/shared-mvbt/src/test/java/org/apache/directory/btree/PageTest.java Mon Feb 13 23:56:40 2012
@@ -20,7 +20,9 @@
package org.apache.directory.btree;
import java.io.IOException;
+import java.util.ArrayList;
import java.util.HashSet;
+import java.util.List;
import java.util.Random;
import java.util.Set;
@@ -65,6 +67,28 @@ public class PageTest
}
+ private void dump( List<Long> added )
+ {
+ boolean isFirst = true;
+
+ for ( Long element : added )
+ {
+ if ( isFirst )
+ {
+ isFirst = false;
+ }
+ else
+ {
+ System.out.print( ", " );
+ }
+
+ System.out.print( element + "L" );
+ }
+
+ System.out.println();
+ }
+
+
@Test
public void testPageInsert1() throws Exception
{
@@ -90,6 +114,7 @@ public class PageTest
public void testPageInsert() throws Exception
{
Set<Long> expected = new HashSet<Long>();
+ List<Long> added = new ArrayList<Long>();
Random random = new Random( System.nanoTime() );
@@ -97,17 +122,20 @@ public class PageTest
long l1 = System.currentTimeMillis();
- for ( int j = 0; j < 10000000; j++ )
+ for ( int j = 0; j < 100; j++ )
{
BTree<Long, String> btree = new BTree<Long, String>( new LongComparator() );
- btree.setPageSize( 4 );
+ btree.setPageSize( 8 );
- for ( int i = 0; i < 16; i++ )
+ for ( int i = 0; i < 65536; i++ )
{
Long key = (long)random.nextInt( 256 );
String value = "V" + key;
expected.add( key );
+ added.add( key );
+ //System.out.println( "Adding " + key );
+
try
{
btree.insert( key, value );
@@ -115,15 +143,21 @@ public class PageTest
catch ( Exception e)
{
e.printStackTrace();
+ System.out.println( btree );
+ System.out.println( "Error while adding " + value );
+ dump( added );
nbError++;
+ return;
}
//System.out.println( btree );
+ //dump( added );
}
assertTrue( checkTree( expected, btree ) );
expected.clear();
+ added.clear();
}
long l2 = System.currentTimeMillis();
@@ -185,4 +219,78 @@ public class PageTest
System.out.println( btree );
}
+
+
+ @Test
+ public void testPageInsert3() throws Exception
+ {
+ BTree<Long, String> btree = new BTree<Long, String>( new LongComparator() );
+ btree.setPageSize( 4 );
+
+ Long[]elems = new Long[]
+ {
+ 101L, 113L, 20L, 72L, 215L, 239L, 108L, 21L, 192L, 130L,
+ 151L, 209L, 229L, 10L, 115L, 234L, 206L, 208L, 197L, 226L,
+ 51L, 62L, 122L, 241L, 249L, 198L, 180L, 208L, 21L, 150L,
+ 21L, 9L, 235L, 45L, 188L, 79L, 194L, 106L, 21L, 12L, 107L,
+ 163L, 61L, 192L, 148L, 206L, 252L, 160L, 115L, 101L, 113L,
+ 20L, 72L, 215L, 239L, 108L, 21L, 192L, 130L, 151L, 209L,
+ 229L, 10L, 115L, 234L, 206L, 208L, 197L, 226L, 51L, 62L,
+ 122L, 241L, 249L, 198L, 180L, 208L, 21L, 150L, 21L, 9L, 235L,
+ 45L, 188L, 79L, 194L, 106L, 21L, 12L, 107L, 163L, 61L, 192L,
+ 148L, 206L, 252L , 160L, 115L
+ };
+
+ for ( Long elem : elems )
+ {
+ btree.insert( elem, "V" + elem );
+
+ System.out.println( "added " + elem + ":" + btree);
+ }
+
+ //btree.insert( 115L, "V115" );
+
+ System.out.println( btree );
+ }
+
+
+ @Test
+ public void testPageRemove() throws Exception
+ {
+ Long[] keys = new Long[]{ 101L, 113L, 20L, 72L, 215L, 239L, 108L, 21L };
+
+ BTree<Long, String> btree = new BTree<Long, String>( new LongComparator(), 8 );
+ System.out.println( btree );
+
+ for ( Long key : keys )
+ {
+ btree.insert( key, "V" + key );
+ }
+
+ System.out.println( btree );
+
+ // Remove from the left
+ btree.remove( 20L );
+ System.out.println( btree );
+
+ // Remove from the right
+ btree.remove( 239L );
+ System.out.println( btree );
+
+ // Remove from the middle
+ btree.remove( 72L );
+ System.out.println( btree );
+
+ // Remove all the remaining elements
+ btree.remove( 101L );
+ System.out.println( btree );
+ btree.remove( 108L );
+ System.out.println( btree );
+ btree.remove( 215L );
+ System.out.println( btree );
+ btree.remove( 113L );
+ System.out.println( btree );
+ btree.remove( 21L );
+ System.out.println( btree );
+ }
}