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/20 12:16:54 UTC
svn commit: r1363707 - in
/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree:
AbstractPage.java Leaf.java Node.java
Author: elecharny
Date: Fri Jul 20 10:16:54 2012
New Revision: 1363707
URL: http://svn.apache.org/viewvc?rev=1363707&view=rev
Log:
o Fixed various bugs
o Simplified some code in leaf and node
o Handle the null values in toString()
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java
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
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java?rev=1363707&r1=1363706&r2=1363707&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java Fri Jul 20 10:16:54 2012
@@ -84,7 +84,7 @@ public abstract class AbstractPage<K, V>
*
* @param parent The parent of the current page
* @param The position of the current page reference in its parent
- * @return The position of the sibling, or -1 if we hav'nt found any sibling
+ * @return The position of the sibling, or -1 if we have'nt found any sibling
*/
protected int selectSibling( Node<K, V> parent, int parentPos )
{
@@ -99,7 +99,7 @@ public abstract class AbstractPage<K, V>
{
// The current page is referenced on the right of its parent's page :
// we will not have a next page with the same parent
- return -1;
+ return parentPos - 1;
}
Page<K, V> prevPage = parent.children[parentPos - 1];
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=1363707&r1=1363706&r2=1363707&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 Fri Jul 20 10:16:54 2012
@@ -143,21 +143,12 @@ 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 = 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];
- }
+ Leaf<K, V> sibling = (Leaf<K, V>)((Node<K, V>)parent).children[siblingPos];
if ( sibling.getNbElems() == halfSize )
{
// We will merge the current page with its sibling
- DeleteResult<K, V> result = mergeWithSibling( revision, sibling, ( siblingPos < index), index );
+ DeleteResult<K, V> result = mergeWithSibling( revision, sibling, ( siblingPos < parentPos), index );
return result;
}
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=1363707&r1=1363706&r2=1363707&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 Fri Jul 20 10:16:54 2012
@@ -175,6 +175,43 @@ import java.util.LinkedList;
return removeResult;
}
+
+
+ /**
+ * Handle the removal of an element from the root page, when two of its children
+ * have been merged.
+ *
+ * @param mergedResult The merge result
+ * @param pos The position in the current root
+ * @param found Tells if the removed key is present in the root page
+ * @return The resulting root page
+ */
+ private RemoveResult<K, V> handleRootRemove( MergedWithSiblingResult<K, V> mergedResult, int pos, boolean found )
+ {
+ RemoveResult<K, V> removeResult = 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 = new RemoveResult<K, V>( mergedResult.getModifiedPage(),
+ mergedResult.getRemovedElement(), mergedResult.getNewLeftMost() );
+ }
+ else
+ {
+ // Remove the element and update the reference to the changed pages
+ if ( found )
+ {
+ removeResult = removeKey( mergedResult, revision, pos );
+ }
+ else
+ {
+ removeResult = removeKey( mergedResult, revision, pos - 1 );
+ }
+ }
+
+ return removeResult;
+ }
/**
@@ -235,27 +272,7 @@ import java.util.LinkedList;
// If the parent is null, then this page is the root page.
if ( parent == null )
{
- RemoveResult<K, V> result = 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 )
- {
- result = new RemoveResult<K, V>( mergedResult.getModifiedPage(),
- mergedResult.getRemovedElement(), mergedResult.getNewLeftMost() );
- }
- else
- {
- // Remove the element and update the reference to the changed pages
- if ( found )
- {
- result = removeKey( mergedResult, revision, index );
- }
- else
- {
- result = removeKey( mergedResult, revision, index - 1 );
- }
- }
+ RemoveResult<K, V> result = handleRootRemove( mergedResult, index, found );
return result;
}
@@ -269,7 +286,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( mergedResult, revision, - (pos + 1 ) );
+ RemoveResult<K, V> result = removeKey( mergedResult, revision, - (pos + 1 ) );
return result;
}
@@ -399,7 +416,7 @@ import java.util.LinkedList;
K newLeftMost = null;
// Copy the keys and the children up to the insertion position
- System.arraycopy( keys, 0, newNode.keys, 0, pos - 1 );
+ System.arraycopy( keys, 0, newNode.keys, 0, pos - 1);
System.arraycopy( children, 0, newNode.children, 0, pos );
// Insert the new elements
@@ -408,7 +425,7 @@ import java.util.LinkedList;
// And copy the elements after the position
System.arraycopy( keys, pos + 1, newNode.keys, pos, keys.length - pos - 1 );
- System.arraycopy( children, pos + 2, newNode.children, pos, children.length - pos - 2 );
+ System.arraycopy( children, pos + 2, newNode.children, pos + 1, children.length - pos - 2 );
if ( pos == 0 )
{
@@ -694,14 +711,27 @@ import java.util.LinkedList;
if ( nbElems > 0 )
{
// Start with the first child
- sb.append( children[0].getId() ).append( "-r" ).append( children[0].getRevision() );
- //sb.append( "{" ).append( children[0] ).append( "}" );
+ if ( children[0] == null )
+ {
+ sb.append( "null" );
+ }
+ else
+ {
+ sb.append( children[0].getId() ).append( "-r" ).append( children[0].getRevision() );
+ }
for ( int i = 0; i < nbElems; i++ )
{
- sb.append( "|<" ).append( keys[i] ).append( ">|" ).
- append( children[i + 1].getId() ).append( "-r" ).append( children[i + 1].getRevision() );
- //sb.append( "{" ).append( children[i + 1] ).append( "}" );
+ sb.append( "|<" ).append( keys[i] ).append( ">|" );
+
+ if ( children[i + 1] == null )
+ {
+ sb.append( "null" );
+ }
+ else
+ {
+ sb.append( children[i + 1].getId() ).append( "-r" ).append( children[i + 1].getRevision() );
+ }
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@labs.apache.org
For additional commands, e-mail: commits-help@labs.apache.org