Author: elecharny
Date: Thu Jun 14 22:59:43 2012
New Revision: 1350421
URL: http://svn.apache.org/viewvc?rev=1350421&view=rev
Log:
o Removed some warnings
o Added a method to copy a Node
o Added some constructors, and the first step for the insert() method in the
Node class
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/BTree.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=1350421&r1=1350420&r2=1350421&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
Thu Jun 14 22:59:43 2012
@@ -190,4 +190,21 @@ public class AbstractPage<K, V> implemen
return btree.getComparator().compare( key1, key2 );
}
+
+
+ /**
+ * Copy the current page and all its keys, with a new revision.
+ *
+ * @param revision The new revision
+ * @return The copied page
+ */
+ protected Page<K, V> copy( long revision )
+ {
+ Page<K, V> newPage = new AbstractPage<K, V>( btree, revision, nbElems
);
+
+ // Copy the keys
+ System.arraycopy( keys, 0, ((AbstractPage<K, V>)newPage).keys, 0,
nbElems );
+
+ return newPage;
+ }
}
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=1350421&r1=1350420&r2=1350421&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
Thu Jun 14 22:59:43 2012
@@ -224,12 +224,13 @@ public class BTree<K, V>
V modifiedValue = null;
// Try to insert the new value in the tree at the right place,
- // starting from the root page
+ // starting from the root page. Here, the root page may be either
+ // a Node or a Leaf
InsertResult<K, V> result = rootPage.insert( revision, key, value
);
if ( result instanceof ModifyResult )
{
- ModifyResult<K, V> modifyResult = ((ModifyResult)result);
+ ModifyResult<K, V> modifyResult = ((ModifyResult<K, V>)result);
// The root has just been modified, we haven't split it
// Get it and make it the current root page
@@ -244,7 +245,7 @@ public class BTree<K, V>
{
// We have split the old root, create a new one containing
// only the pivotal we got back
- SplitResult<K, V> splitResult = ((SplitResult)result);
+ SplitResult<K, V> splitResult = ((SplitResult<K, V>)result);
K pivot = splitResult.getPivot();
Page<K, V> leftPage = splitResult.getLeftPage();
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=1350421&r1=1350420&r2=1350421&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
Thu Jun 14 22:59:43 2012
@@ -45,6 +45,26 @@ public class Node<K, V> extends Abstract
* @param leftPage The left page
* @param rightPage The right page
*/
+ /* No qualifier */ Node( BTree<K, V> btree, long revision, int nbElems )
+ {
+ super( btree, revision, nbElems );
+
+ // Create the children array, and store the left and right children
+ children = (Page<K, V>[])new Object[btree.getPageSize()];
+ }
+
+
+ /**
+ * Create a new Node which will contain only one key, with references to
+ * a left and right page. This is a specific constructor used by the btree
+ * when the root was full when we added a new value.
+ *
+ * @param btree the parent BTree
+ * @param revision the Node revision
+ * @param key The new key
+ * @param leftPage The left page
+ * @param rightPage The right page
+ */
/* No qualifier */ Node( BTree<K, V> btree, long revision, K key, Page<K,
V> leftPage, Page<K, V> rightPage )
{
super( btree, revision, 1 );
@@ -58,4 +78,72 @@ public class Node<K, V> extends Abstract
keys = (K[])new Object[btree.getPageSize()];
keys[0] = key;
}
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public InsertResult<K, V> insert( long revision, K key, V value )
+ {
+ // Find the key into this leaf
+ int index = findKeyInPage( key );
+
+ if ( index < 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++ );
+ }
+
+ // Get the child page into which we will insert the <K, V> tuple
+ Page<K, V> child = children[index];
+
+ // and insert the <K, V> into this child
+ InsertResult<K, V> result = child.insert( revision, key, value );
+
+ // Ok, now, we have injected the <K, V> tuple down the tree. Let's
check
+ // the result to see if we have to split the current page
+ if ( result instanceof ModifyResult )
+ {
+ // The child has been modified.
+ ModifyResult<K, V> modifyResult = (ModifyResult<K, V>)result;
+
+ // Just copy the current page and update its revision
+ Page<K, V> newPage = copy( revision );
+
+ // 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;
+
+ // We can return the result, where we update the modifiedPage,
+ // to avoid the creation of a new object
+ modifyResult.modifiedPage = newPage;
+
+ return modifyResult;
+ }
+ else
+ {
+ // The child has been split
+ SplitResult<K, V> modifyResult = (SplitResult<K, V>)result;
+
+ return null;
+ }
+ }
+
+
+ /**
+ * Copy the current page and all its keys, with a new revision.
+ *
+ * @param revision The new revision
+ * @return The copied page
+ */
+ protected Page<K, V> copy( long revision )
+ {
+ Page<K, V> newPage = new Node<K, V>( btree, revision, nbElems );
+
+ // Copy the children
+ System.arraycopy( children, 0, ((Node<K, V>)newPage).children, 0,
nbElems );
+
+ return newPage;
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
