You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@labs.apache.org by el...@apache.org on 2012/07/09 11:27:44 UTC
svn commit: r1358996 - in /labs/mavibot/trunk/mavibot/src:
main/java/org/apache/mavibot/btree/Leaf.java
main/java/org/apache/mavibot/btree/Node.java
test/java/org/apache/mavibot/btree/BTreeTest.java
Author: elecharny
Date: Mon Jul 9 09:27:43 2012
New Revision: 1358996
URL: http://svn.apache.org/viewvc?rev=1358996&view=rev
Log:
o Fixed a AOOBE in the Leaf.delete() method
o Handled two more use case when a delete results in a merge of pages
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/BTreeTest.java
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java?rev=1358996&r1=1358995&r2=1358996&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java Mon Jul 9 09:27:43 2012
@@ -143,8 +143,16 @@ public class Leaf<K, V> extends Abstract
// Check in both next and previous page, if they have the same parent
// and select the biggest page with the same parent to borrow an element.
int siblingPos = selectSibling( (Node<K, V>)parent, parentPos );
-
- Leaf<K, V> sibling = (Leaf<K, V>)((Node<K, V>)parent).children[siblingPos];
+ Leaf<K, V> sibling = null;
+
+ if ( siblingPos == -1 )
+ {
+ sibling = (Leaf<K, V>)((Node<K, V>)parent).children[parentPos - 1];
+ }
+ else
+ {
+ sibling = (Leaf<K, V>)((Node<K, V>)parent).children[siblingPos];
+ }
if ( sibling.getNbElems() == halfSize )
{
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java?rev=1358996&r1=1358995&r2=1358996&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java Mon Jul 9 09:27:43 2012
@@ -211,10 +211,8 @@ import java.util.LinkedList;
}
else
{
- // Just remove the entry if it's present
- int newIndex = findPos( mergedResult.getRemovedElement().getKey() );
-
- DeleteResult<K, V> result = removeKey( revision, newIndex );
+ // Remove the element and update the reference to the changed pages
+ RemoveResult<K, V> result = removeKey( mergedResult, revision, index );
return result;
}
@@ -266,7 +264,7 @@ import java.util.LinkedList;
// We simply remove the element from the page, and if it was the leftmost,
// we return the new pivot (it will replace any instance of the removed
// key in its parents)
- DeleteResult<K, V> result = removeKey( revision, index );
+ DeleteResult<K, V> result = removeKey( mergedResult, revision, index );
return result;
}
@@ -304,6 +302,35 @@ import java.util.LinkedList;
{
return borrowedResult( deleteResult, pos );
}
+ else
+ {
+ MergedWithSiblingResult<K, V> mergedResult = (MergedWithSiblingResult<K, V>)deleteResult;
+
+ // Here, we have to delete an element from the current page, and if the resulting
+ // page does not contain enough elements (ie below N/2), then we have to borrow
+ // one element from a sibling or merge the page with a sibling.
+
+ // If the parent is null, then this page is the root page.
+ if ( parent == null )
+ {
+ // If the current node contains only one key, then the merged result will be
+ // the new root. Deal with this case
+ if ( nbElems == 1 )
+ {
+ RemoveResult<K, V> removeResult = new RemoveResult<K, V>( mergedResult.getModifiedPage(),
+ mergedResult.getRemovedElement(), mergedResult.getNewLeftMost() );
+
+ return removeResult;
+ }
+ else
+ {
+ // Remove the element and update the reference to the changed pages
+ RemoveResult<K, V> result = removeKey( mergedResult, revision, pos - 1 );
+
+ return result;
+ }
+ }
+ }
}
@@ -388,7 +415,7 @@ import java.util.LinkedList;
* @param pos The position into the page of the element to remove
* @return The modified page with the <K,V> element added
*/
- private DeleteResult<K, V> removeKey( long revision,int pos )
+ private RemoveResult<K, V> removeKey( MergedWithSiblingResult<K, V> mergedResult, long revision, int pos )
{
// Get the removed element
Tuple<K, V> removedElement = new Tuple<K, V>( keys[pos], null );
@@ -398,15 +425,17 @@ import java.util.LinkedList;
K newLeftMost = null;
- // Deal with the special case of a node with only one element by skipping
- // the copy, as we won't have any remaining element in the page
// Copy the keys and the children up to the insertion position
- System.arraycopy( keys, 0, newNode.keys, 0, pos );
+ System.arraycopy( keys, 0, newNode.keys, 0, pos - 1 );
System.arraycopy( children, 0, newNode.children, 0, pos );
+ // Insert the new elements
+ newNode.keys[pos - 1] = mergedResult.getModifiedPage().getKey( 0 );
+ newNode.children[pos] = mergedResult.getModifiedPage();
+
// And copy the elements after the position
System.arraycopy( keys, pos + 1, newNode.keys, pos, keys.length - pos - 1 );
- System.arraycopy( children, pos + 1, newNode.children, pos, children.length - pos - 1 );
+ System.arraycopy( children, pos + 2, newNode.children, pos, children.length - pos - 2 );
if ( pos == 0 )
{
@@ -414,7 +443,7 @@ import java.util.LinkedList;
}
// Create the result
- DeleteResult<K, V> result = new RemoveResult<K, V>( newNode, removedElement, newLeftMost );
+ RemoveResult<K, V> result = new RemoveResult<K, V>( newNode, removedElement, newLeftMost );
return result;
}
Modified: labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/BTreeTest.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/BTreeTest.java?rev=1358996&r1=1358995&r2=1358996&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/BTreeTest.java (original)
+++ labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/BTreeTest.java Mon Jul 9 09:27:43 2012
@@ -651,5 +651,16 @@ public class BTreeTest
// Delete a key at the first place, borrow from left
btree.delete( 9 );
assertNull( btree.find( 9 ) );
+
+ // Delete a key on first position that will generate a merge between two pages
+ btree.delete( 19 );
+ assertNull( btree.find( 19 ) );
+
+ // Delete one element and another one, so that we have another merge, but removed the second key of the right page
+ btree.delete( 20 );
+ assertNull( btree.find( 20 ) );
+
+ btree.delete( 18 );
+ assertNull( btree.find( 18 ) );
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@labs.apache.org
For additional commands, e-mail: commits-help@labs.apache.org