directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject 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
Date Mon, 13 Feb 2012 23:56:41 GMT
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 );
+    }
 }



Mime
View raw message