directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1234913 - in /directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree: BTree.java ModifiedPage.java Page.java
Date Mon, 23 Jan 2012 17:45:06 GMT
Author: elecharny
Date: Mon Jan 23 17:45:06 2012
New Revision: 1234913

URL: http://svn.apache.org/viewvc?rev=1234913&view=rev
Log:
o Replaced the isLeaf boolean flag by an enum
o Started to work on elements removal.

Added:
    directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/ModifiedPage.java
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

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=1234913&r1=1234912&r2=1234913&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 Jan 23 17:45:06 2012
@@ -177,6 +177,7 @@ public class BTree<K, V>
                 {
                     rootPage.setRecordId();
                 }
+                
                 roots.put( revision, rootPage );
             }
         }
@@ -188,6 +189,34 @@ public class BTree<K, V>
     
     
     /**
+     * Removes the value associated with a given key. If the key is not found,
+     * does nothing.
+     * 
+     * @param key The key we are looking for
+     * @return The removed value
+     */
+    public V remove( K key )
+    {
+        if ( rootPage == null )
+        {
+            // No pages in the BTree just return
+            return null;
+        }
+        
+        ModifiedPage<K, V> removedPage = rootPage.remove( rootPage.getRevision(), key
);
+        
+        if ( removedPage != null )
+        {
+            return removedPage.getValue();
+        }
+        else
+        {
+            return null;
+        }
+    }
+    
+    
+    /**
      * @return The number of element we can stoe in a page
      */
     public int getPageSize()

Added: directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/ModifiedPage.java
URL: http://svn.apache.org/viewvc/directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/ModifiedPage.java?rev=1234913&view=auto
==============================================================================
--- directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/ModifiedPage.java
(added)
+++ directory/sandbox/elecharny/shared-mvbt/src/main/java/org/apache/directory/btree/ModifiedPage.java
Mon Jan 23 17:45:06 2012
@@ -0,0 +1,68 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one
+ *  or more contributor license agreements.  See the NOTICE file
+ *  distributed with this work for additional information
+ *  regarding copyright ownership.  The ASF licenses this file
+ *  to you under the Apache License, Version 2.0 (the
+ *  "License"); you may not use this file except in compliance
+ *  with the License.  You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing,
+ *  software distributed under the License is distributed on an
+ *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *  KIND, either express or implied.  See the License for the
+ *  specific language governing permissions and limitations
+ *  under the License.
+ *
+ */
+package org.apache.directory.btree;
+
+/**
+ * A result page when removing an element from a Page.
+ * 
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+/* No qualifier */ class ModifiedPage<K, V>
+{
+    /** A modified Page after removal or merge or simply with a new revision */
+    private Page<K, V> modifiedPage;
+    
+    /** The removed Value */
+    private V value;
+    
+    /**
+     * Creates an instance of this class
+     * 
+     * @param modifiedPage The modified Page
+     * @param value The removed value
+     */
+    ModifiedPage( Page<K, V> modifiedPage, V value )
+    {
+        this.modifiedPage = modifiedPage;
+        this.value = value;
+    }
+    
+    
+    /**
+     * @return The removed value
+     */
+    /* No qualifier */ V getValue()
+    {
+        return value;
+    }
+
+    
+    /**
+     * The modified page
+     * @return
+     */
+    /* No qualifier */ Page<K, V> getModifiedPage()
+    {
+        return modifiedPage;
+    }
+}

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=1234913&r1=1234912&r2=1234913&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 Jan 23 17:45:06 2012
@@ -28,7 +28,7 @@ package org.apache.directory.btree;
 
  * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
  */
-public class Page<K, V> implements Cloneable
+/* No qualifier */ class Page<K, V> implements Cloneable
 {
     private static final boolean DEBUG = false;
 
@@ -42,7 +42,7 @@ public class Page<K, V> implements Clone
     private long recordId;
     
     /** Flag indicating if this is a leaf BPage. */
-    private boolean isLeaf;
+    private PageType type;
 
     /** Keys of children nodes */
     private K[] keys;
@@ -65,6 +65,15 @@ public class Page<K, V> implements Clone
     /** A flag used to know that the Page is the result of a split */
     /* No qualifier */ static long OVERFLOW = -1L;
     
+    /**
+     * An enum with the three different kind of pages we are dealing with
+     */
+    private enum PageType
+    {
+        ROOT,
+        NODE,
+        LEAF
+    }
 
     /**
      * No-argument constructor used by serialization.
@@ -79,17 +88,17 @@ public class Page<K, V> implements Clone
      * Internal constructor used to create Page instance used when a page is being copied
or overflow
      */
     @SuppressWarnings("unchecked") // Cannot create an array of generic objects
-    private Page( BTree<K, V> btree, long revision, int nbElems, boolean isLeaf )
+    private Page( BTree<K, V> btree, long revision, int nbElems, PageType type )
     {
         this.btree = btree;
         this.revision = revision;
         this.nbElems = nbElems;
         this.keys = (K[])new Object[nbElems];
         this.values = (V[])new Object[nbElems];
-        this.isLeaf = isLeaf;
+        this.type = type;
         recordId = btree.generateRecordId();
         
-        if ( !isLeaf )
+        if ( type != PageType.LEAF )
         {
             this.children = new Page[nbElems + 1];
         }
@@ -112,7 +121,7 @@ public class Page<K, V> implements Clone
         this.recordId = btree.generateRecordId();
 
         // Newly created pages are leaves
-        isLeaf = true;
+        type = PageType.LEAF;
 
         // Create an array for the keys
         keys = (K[])new Object[1];
@@ -145,7 +154,7 @@ public class Page<K, V> implements Clone
         
         else
         {
-            if ( isLeaf )
+            if ( type == PageType.LEAF )
             {
                 return null;
             }
@@ -158,6 +167,109 @@ public class Page<K, V> implements Clone
     
     
     /**
+     * Remove a <K,V> from the tree, if found.
+     * 
+     * @param key The key we are looking for
+     * @return The removed Value, if we cound the key. Null otherwise
+     */
+    /* No qualifier */ ModifiedPage<K, V> remove( long revision, K key )
+    {
+        int index = findIndex( key );
+
+        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 )
+            {
+                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 )
+                {
+                    // The page will not contain enough elements after the removal
+                    return null;
+                }
+                else
+                {
+                    // 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 )
+                    {
+                        // 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;
+            }
+        }
+        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 )
+            {
+                // 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;
+        }
+    }
+    
+    
+    /**
      * Get largest key under this BPage.  Null is considered to be the
      * greatest possible key.
      */
@@ -209,7 +321,7 @@ public class Page<K, V> implements Clone
      */
     /* No qualifier */ boolean isLeaf()
     {
-        return isLeaf;
+        return type != PageType.NODE ;
     }
     
     
@@ -317,7 +429,7 @@ public class Page<K, V> implements Clone
      */
     /* No qualifier */ Page<K, V> insert( long revision, K key, V value )
     {
-        if ( isLeaf )
+        if ( type == PageType.LEAF )
         {
             // The current page is a leaf : we have to insert the <K,V> element
             // into a copied page with a new revision
@@ -436,7 +548,7 @@ public class Page<K, V> implements Clone
      */
     private Page<K, V> insertOverflow( long revision, Page<K, V> result, int
index )
     {
-        Page<K, V> newPage = new Page<K, V>( btree, revision, nbElems + 1, false
);
+        Page<K, V> newPage = new Page<K, V>( btree, revision, nbElems + 1, PageType.NODE
);
               
         System.arraycopy( keys, 0, newPage.keys, 0, index );
         newPage.keys[index] = result.keys[0];
@@ -446,7 +558,7 @@ public class Page<K, V> implements Clone
         newPage.values[index] = result.values[0];
         System.arraycopy( values, index, newPage.values, index + 1, newPage.nbElems - ( index
+ 1 ) );
 
-        if ( ! isLeaf )
+        if ( type != PageType.LEAF )
         {
             System.arraycopy( children, 0, newPage.children, 0, index );
             newPage.children[index] = result.children[0];
@@ -477,7 +589,7 @@ public class Page<K, V> implements Clone
      */
     private Page<K, V> addAndSplit( long revision, K key, V value, Page<K, V>
left, Page<K, V> right, int index )
     {
-        Page<K, V> newPage = new Page<K, V>( btree, revision, 1, false );
+        Page<K, V> newPage = new Page<K, V>( btree, revision, 1, PageType.NODE
);
         newPage.recordId = OVERFLOW;
 
         Page<K, V> child = null;
@@ -502,7 +614,7 @@ public class Page<K, V> implements Clone
             newPage.values[0] = values[pivot - 1];
             newPage.children[0] = copyAndInsert( revision, key, value, left, right, index,
0, pivot - 1 );
             
-            if ( !isLeaf )
+            if ( type != PageType.LEAF )
             {
                 child = children[pivot];
             }
@@ -517,7 +629,7 @@ public class Page<K, V> implements Clone
             newPage.keys[0] = keys[pivot];
             newPage.values[0] = values[pivot];
 
-            if ( !isLeaf )
+            if ( type != PageType.LEAF )
             {
                 child = children[pivot];
             }
@@ -540,12 +652,12 @@ public class Page<K, V> implements Clone
      */
     private Page<K, V> copyHalfPage( long revision, int start, int end, Page<K,
V> child )
     {
-        Page<K, V> newPage = new Page<K, V>( btree, revision, end - start + 1,
isLeaf );
+        Page<K, V> newPage = new Page<K, V>( btree, revision, end - start + 1,
type );
         
         System.arraycopy( keys, start, newPage.keys, 0, newPage.nbElems );
         System.arraycopy( values, start, newPage.values, 0, newPage.nbElems );
     
-        if ( ! isLeaf )
+        if ( type != PageType.LEAF )
         {
             if ( start == 0 )
             {
@@ -628,7 +740,7 @@ public class Page<K, V> implements Clone
     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>( btree, revision, end - start + 1,
isLeaf );
+        Page<K, V> newPage = new Page<K, V>( btree, revision, end - start + 1,
type );
         
         int middle = index - start;
         
@@ -640,7 +752,7 @@ public class Page<K, V> implements Clone
         newPage.values[middle] = pivotValue;
         System.arraycopy( values, index, newPage.values, middle + 1, newPage.nbElems - (
middle + 1 ) );
 
-        if ( ! isLeaf )
+        if ( type != PageType.LEAF )
         {
             System.arraycopy( children, start, newPage.children, 0, middle );
             newPage.children[middle] = leftPage;
@@ -650,6 +762,27 @@ public class Page<K, V> implements Clone
 
         return newPage;
     }
+
+    
+    /**
+     * Copy a page after having removed an element from it
+     * 
+     * @param revision The revision for the new created page
+     * @param index The position where to remove the element from
+     * @return A new page containing everything but the removed element
+     */
+    private ModifiedPage<K, V> copyAndRemove( long revision, int index )
+    {
+        Page<K, V> newPage = new Page<K, V>( btree, revision, nbElems - 1, type
);
+        
+        System.arraycopy( keys, 0, newPage.keys, 0, index );
+        System.arraycopy( keys, index + 1, newPage.keys, index, newPage.nbElems - index -
1 );
+        
+        System.arraycopy( values, 0, newPage.values, 0, index );
+        System.arraycopy( values, index + 1, newPage.values, index, newPage.nbElems - index
- 1 );
+
+        return new ModifiedPage<K, V>( newPage, values[index] );
+    }
     
     
     /**
@@ -681,7 +814,7 @@ public class Page<K, V> implements Clone
      */
     private Page<K, V> addElement( long revision, int index, K key, V value )
     {
-        Page<K, V> newPage = new Page<K, V>( btree, revision, nbElems + 1, true
);
+        Page<K, V> newPage = new Page<K, V>( btree, revision, nbElems + 1, PageType.LEAF
);
 
         copyAndAdd( keys, newPage.keys, key, index );
         copyAndAdd( values, newPage.values, value, index );
@@ -741,12 +874,12 @@ public class Page<K, V> implements Clone
      */
     private Page<K, V> copy( long revision )
     {
-        Page<K, V> newPage = new Page<K, V>( btree, revision, nbElems, isLeaf
);
+        Page<K, V> newPage = new Page<K, V>( btree, revision, nbElems, type );
 
         System.arraycopy( keys, 0, newPage.keys, 0, newPage.nbElems );
         System.arraycopy( values, 0, newPage.values, 0, newPage.nbElems );
 
-        if ( ! newPage.isLeaf )
+        if ( newPage.type != PageType.LEAF )
         {
             System.arraycopy( children, 0, newPage.children, 0, newPage.nbElems + 1 );
         }
@@ -789,15 +922,9 @@ public class Page<K, V> implements Clone
     public String toString()
     {
         StringBuilder sb = new StringBuilder();
-        
-        if ( isLeaf )
-        {
-            sb.append( "Leaf(" );
-        }
-        else
-        {
-            sb.append( "Node(" );
-        }
+
+        // The type
+        sb.append( type ).append( "(" );
         
         // The revision
         sb.append( "r" ).append( revision ).append( ", " );
@@ -809,7 +936,7 @@ public class Page<K, V> implements Clone
         sb.append( keys.length );
         sb.append( ") : [" );
         
-        if ( isLeaf )
+        if ( type == PageType.LEAF )
         {
             boolean isFirst = true;
             int index = 0;



Mime
View raw message