Author: elecharny
Date: Mon Jun 18 17:45:35 2012
New Revision: 1351421
URL: http://svn.apache.org/viewvc?rev=1351421&view=rev
Log:
o Renamed the AbstractPage to BasePage : this is not an abstract class
o Fixed an issue in the way we compute the power of 2 of a number
o Fixed a comparison in the Leaf addAndSplit() method in Leaf
o Added the addAndSplit() method in Node
o Added a dumpPage() method used to pretty-print a tree
Added:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BasePage.java
- copied, changed from r1351298,
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java
Removed:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.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
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java?rev=1351421&r1=1351420&r2=1351421&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
Mon Jun 18 17:45:35 2012
@@ -105,7 +105,7 @@ public class BTree<K, V>
*/
private int getPowerOf2( int size )
{
- int newSize = size--;
+ int newSize = --size;
newSize |= newSize >> 1;
newSize |= newSize >> 2;
newSize |= newSize >> 4;
@@ -315,8 +315,8 @@ public class BTree<K, V>
sb.append( comparator.getClass().getSimpleName() );
}
- sb.append( ") : " );
- sb.append( rootPage );
+ sb.append( ") : \n" );
+ sb.append( rootPage.dumpPage( "" ) );
return sb.toString();
}
Copied:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BasePage.java
(from r1351298,
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/BasePage.java?p2=labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BasePage.java&p1=labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java&r1=1351298&r2=1351421&rev=1351421&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/BasePage.java
Mon Jun 18 17:45:35 2012
@@ -28,7 +28,7 @@ package org.apache.mavibot.btree;
*
* @author <a href="mailto:[email protected]";>Mavibot labs Project</a>
*/
-public class AbstractPage<K, V> implements Page<K, V>
+public class BasePage<K, V> implements Page<K, V>
{
/** Parent B+Tree. */
protected transient BTree<K, V> btree;
@@ -51,7 +51,7 @@ public class AbstractPage<K, V> implemen
*
* @param btree The associated BTree
*/
- protected AbstractPage( BTree<K, V> btree )
+ protected BasePage( BTree<K, V> btree )
{
this.btree = btree;
}
@@ -61,7 +61,7 @@ public class AbstractPage<K, V> implemen
* 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
- protected AbstractPage( BTree<K, V> btree, long revision, int nbElems )
+ protected BasePage( BTree<K, V> btree, long revision, int nbElems )
{
this.btree = btree;
this.revision = revision;
@@ -201,10 +201,10 @@ public class AbstractPage<K, V> implemen
*/
protected Page<K, V> copy( long revision )
{
- Page<K, V> newPage = new AbstractPage<K, V>( btree, revision, nbElems
);
+ Page<K, V> newPage = new BasePage<K, V>( btree, revision, nbElems );
// Copy the keys
- System.arraycopy( keys, 0, ((AbstractPage<K, V>)newPage).keys, 0,
nbElems );
+ System.arraycopy( keys, 0, ((BasePage<K, V>)newPage).keys, 0, nbElems
);
return newPage;
}
@@ -250,4 +250,13 @@ public class AbstractPage<K, V> implemen
return sb.toString();
}
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public String dumpPage( String tabs )
+ {
+ return "";
+ }
}
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=1351421&r1=1351420&r2=1351421&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 Jun 18 17:45:35 2012
@@ -27,7 +27,7 @@ package org.apache.mavibot.btree;
*
* @author <a href="mailto:[email protected]";>Mavibot labs Project</a>
*/
-public class Leaf<K, V> extends AbstractPage<K, V>
+public class Leaf<K, V> extends BasePage<K, V>
{
/** Values associated with keys */
private V[] values;
@@ -220,7 +220,7 @@ public class Leaf<K, V> extends Abstract
Leaf<K, V> rightLeaf = null;
// Determinate where to store the new value
- if ( pos < middle )
+ if ( pos <= middle )
{
// The left page will contain the new value
leftLeaf = new Leaf<K, V>( btree, revision, middle + 1 );
@@ -344,4 +344,17 @@ public class Leaf<K, V> extends Abstract
return sb.toString();
}
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public String dumpPage( String tabs )
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( tabs ).append( toString() );
+
+ return sb.toString();
+ }
}
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=1351421&r1=1351420&r2=1351421&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 Jun 18 17:45:35 2012
@@ -28,7 +28,7 @@ package org.apache.mavibot.btree;
*
* @author <a href="mailto:[email protected]";>Mavibot labs Project</a>
*/
-public class Node<K, V> extends AbstractPage<K, V>
+public class Node<K, V> extends BasePage<K, V>
{
/** Children pages associated with keys. */
protected Page<K, V>[] children;
@@ -49,8 +49,8 @@ public class Node<K, V> extends Abstract
{
super( btree, revision, nbElems );
- // Create the children array, and store the left and right children
- children = new Page[btree.getPageSize()];
+ // Create the children array
+ children = new Page[nbElems + 1];
}
@@ -86,17 +86,17 @@ public class Node<K, V> extends Abstract
public InsertResult<K, V> insert( long revision, K key, V value )
{
// Find the key into this leaf
- int index = findPos( key );
+ int pos = findPos( key );
- if ( index < 0 )
+ if ( pos < 0 )
{
// The key has been found in the page. As it's a Node, that means
// we must go down in the right child to insert the value
- index = - ( index++ );
+ pos = - ( pos++ );
}
// Get the child page into which we will insert the <K, V> tuple
- Page<K, V> child = children[index];
+ Page<K, V> child = children[pos];
// and insert the <K, V> into this child
InsertResult<K, V> result = child.insert( revision, key, value );
@@ -113,7 +113,7 @@ public class Node<K, V> extends Abstract
// Last, we update the children table of the newly created page
// to point on the modified child
- ((Node<K, V>)newPage).children[index] = modifyResult.modifiedPage;
+ ((Node<K, V>)newPage).children[pos] = modifyResult.modifiedPage;
// We can return the result, where we update the modifiedPage,
// to avoid the creation of a new object
@@ -136,13 +136,160 @@ public class Node<K, V> extends Abstract
if ( nbElems == btree.getPageSize() )
{
// The page is full
+ result = addAndSplit( revision, pivot, leftPage, rightPage,
pos );
}
else
{
- // The page can contain the new pivot
+ // The page can contain the new pivot, let's insert it
+ result = addElement( revision, pivot, leftPage, rightPage, pos
);
}
- return null;
+ return result;
+ }
+ }
+
+
+ /**
+ * Add a new key into a copy of the current page at a given position. We
return the
+ * modified page. The new page will have one more key than the current
page.
+ *
+ * @param revision The revision of the modified page
+ * @param key The key to insert
+ * @param leftPage The left child
+ * @param rightPage The right child
+ * @param pos The position into the page
+ * @return The modified page with the <K,V> element added
+ */
+ private InsertResult<K, V> addElement( long revision, K key, Page<K, V>
leftPage, Page<K, V> rightPage, int pos )
+ {
+ // First copy the current page, but add one element in the copied page
+ Node<K, V> newNode = new Node<K, V>( btree, revision, nbElems + 1 );
+
+ // Deal with the special case of an empty page
+ if ( nbElems == 0 )
+ {
+ newNode.keys[0] = key;
+ newNode.children[0] = leftPage;
+ newNode.children[1] = rightPage;
+ }
+ else
+ {
+ // Copy the keys and the children up to the insertion position
+ System.arraycopy( keys, 0, newNode.keys, 0, pos );
+ System.arraycopy( children, 0, newNode.children, 0, pos );
+
+ // Add the new key and children
+ newNode.keys[pos] = key;
+ newNode.children[pos] = leftPage;
+ newNode.children[pos + 1] = rightPage;
+
+ // And copy the remaining keys and children
+ System.arraycopy( keys, pos, newNode.keys, pos + 1, keys.length -
pos );
+ System.arraycopy( children, pos + 1, newNode.children, pos + 2,
children.length - pos - 1 );
+ }
+
+ // Create the result
+ InsertResult<K, V> result = new ModifyResult<K, V>( newNode, null );
+
+ return result;
+ }
+
+
+ /**
+ * Split a full page into two new pages, a left, a right and a pivot
element. The new pages will
+ * each contains half of the original elements. <br/>
+ * The pivot will be computed, depending on the place
+ * we will inject the newly added element. <br/>
+ * If the newly added element is in the middle, we will use it
+ * as a pivot. Otherwise, we will use either the last element in the left
page if the element is added
+ * on the left, or the first element in the right page if it's added on
the right.
+ *
+ * @param revision The new revision for all the created pages
+ * @param key The key to add
+ * @param leftPage The left child
+ * @param rightPage The right child
+ * @param pos The position of the insertion of the new element
+ * @return An OverflowPage containing the pivot, and the new left and
right pages
+ */
+ private InsertResult<K, V> addAndSplit( long revision, K pivot, Page<K, V>
leftPage, Page<K, V> rightPage, int pos )
+ {
+ int middle = btree.pageSize >> 1;
+
+ // Create two new pages
+ Node<K, V> newLeftPage = new Node<K, V>( btree, revision, middle );
+ Node<K, V> newRightPage = new Node<K, V>( btree, revision, middle );
+
+ // Determinate where to store the new value
+ // If it's before the middle, insert the value on the left,
+ // the key in the middle will become the new pivot
+ if ( pos < middle )
+ {
+ // Copy the keys and the children up to the insertion position
+ System.arraycopy( keys, 0, newLeftPage.keys, 0, pos );
+ System.arraycopy( children, 0, newLeftPage.children, 0, pos );
+
+ // Add the new element
+ newLeftPage.keys[pos] = pivot;
+ newLeftPage.children[pos] = leftPage;
+ newLeftPage.children[pos+1] = rightPage;
+
+ // And copy the remaining elements minus the new pivot
+ System.arraycopy( keys, pos, newLeftPage.keys, pos + 1, middle -
pos - 1 );
+ System.arraycopy( children, pos + 1, newLeftPage.children, pos +
2, middle - pos - 1 );
+
+ // Copy the keys and the values in the right page
+ System.arraycopy( keys, middle, newRightPage.keys, 0, middle );
+ System.arraycopy( children, middle, newRightPage.children, 0,
middle + 1 );
+
+ // Create the result
+ InsertResult<K, V> result = new SplitResult<K, V>( keys[middle -
1], newLeftPage, newRightPage );
+
+ return result;
+ }
+ else if ( pos == middle )
+ {
+ // A special case : the pivot will be propagated up in the tree
+ // The left and right pages will be spread on the two new pages
+ // Copy the keys and the children up to the insertion position
+ System.arraycopy( keys, 0, newLeftPage.keys, 0, middle );
+ System.arraycopy( children, 0, newLeftPage.children, 0, middle );
+
+ // And process the right page now
+ System.arraycopy( keys, middle, newLeftPage.keys, 0, middle );
+ System.arraycopy( children, middle, newLeftPage.children, 1,
middle );
+
+ // add the new references
+ newLeftPage.children[middle] = leftPage;
+ newRightPage.children[0] = rightPage;
+
+ // Create the result
+ InsertResult<K, V> result = new SplitResult<K, V>( pivot,
newLeftPage, newRightPage );
+
+ return result;
+ }
+ else
+ {
+ // Copy the keys and the children up to the middle
+ System.arraycopy( keys, 0, newLeftPage.keys, 0, middle );
+ System.arraycopy( children, 0, newLeftPage.children, 0, middle + 1
);
+
+ // Copy the keys and the values in the right page up to the pos
+ System.arraycopy( keys, middle, newRightPage.keys, 0, pos - middle
- 1 );
+ System.arraycopy( children, middle, newRightPage.children, 0, pos
- middle - 1 );
+
+ // Add the new element
+ newLeftPage.keys[pos] = pivot;
+ newLeftPage.children[pos] = leftPage;
+ newLeftPage.children[pos+1] = rightPage;
+
+ // And copy the remaining elements minus the new pivot
+ System.arraycopy( keys, pos, newLeftPage.keys, pos + 1, nbElems -
pos - 1 );
+ System.arraycopy( children, pos, newLeftPage.children, pos + 2,
nbElems - pos - 1 );
+
+ // Create the result
+ InsertResult<K, V> result = new SplitResult<K, V>( keys[middle -
1], newLeftPage, newRightPage );
+
+ return result;
}
}
@@ -157,8 +304,11 @@ public class Node<K, V> extends Abstract
{
Page<K, V> newPage = new Node<K, V>( btree, revision, nbElems );
+ // Copy the keys
+ System.arraycopy( keys, 0, ((Node<K, V>)newPage).keys, 0, nbElems );
+
// Copy the children
- System.arraycopy( children, 0, ((Node<K, V>)newPage).children, 0,
nbElems );
+ System.arraycopy( children, 0, ((Node<K, V>)newPage).children, 0,
nbElems + 1);
return newPage;
}
@@ -179,11 +329,13 @@ public class Node<K, V> extends Abstract
{
// Start with the first child
sb.append( children[0].getId() ).append( "-r" ).append(
children[0].getRevision() );
+ sb.append( "{" ).append( children[0] ).append( "}" );
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( "}" );
}
}
@@ -191,4 +343,31 @@ public class Node<K, V> extends Abstract
return sb.toString();
}
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public String dumpPage( String tabs )
+ {
+ StringBuilder sb = new StringBuilder();
+
+ if ( nbElems > 0 )
+ {
+ // Start with the first child
+ sb.append( children[0].dumpPage( tabs + " " ) ).append( "\n" );
+
+ for ( int i = 0; i < nbElems; i++ )
+ {
+ sb.append( tabs );
+ sb.append( "Node[" );
+ sb.append( super.toString() );
+ sb.append ( "] <" );
+ sb.append( keys[i] ).append( ">\n" );
+ sb.append( children[i + 1].dumpPage( tabs + " " ) ).append(
"\n" );
+ }
+ }
+
+ return sb.toString();
+ }
}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java?rev=1351421&r1=1351420&r2=1351421&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
(original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
Mon Jun 18 17:45:35 2012
@@ -65,4 +65,12 @@ public interface Page<K, V>
* @return the id
*/
long getId();
+
+
+ /**
+ * Pretty-print the tree with tabs
+ * @param tabs The tabs to add in front of each node
+ * @return A pretty-print dump of the tree
+ */
+ String dumpPage( String tabs );
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
