Author: elecharny
Date: Sat Jun 16 09:07:05 2012
New Revision: 1350894
URL: http://svn.apache.org/viewvc?rev=1350894&view=rev
Log:
o Some renaming
o Implemented the insertion into leaf pages
o Added some code in the inster method in Node (not finished yet)
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/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=1350894&r1=1350893&r2=1350894&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
Sat Jun 16 09:07:05 2012
@@ -108,30 +108,31 @@ public class AbstractPage<K, V> implemen
* @param key The key to find
* @return The position in the page.
*/
- protected int findKeyInPage( K key )
+ protected int findPos( K key )
{
- int left = 0;
- int right = nbElems - 1;
+ // Deal with the special key where we have an empty page
+ if ( nbElems == 0 )
+ {
+ return 0;
+ }
+
+ int min = 0;
+ int max = nbElems - 1;
// binary search
- while ( left < right )
+ while ( min < max )
{
- int middle = ( left + right ) >>> 1;
+ int middle = ( min + max + 1 ) >> 1;
int comp = compare( keys[middle], key );
if ( comp < 0 )
{
- left = middle + 1;
+ min = middle + 1;
}
else if ( comp > 0 )
{
- if ( middle == left )
- {
- return left;
- }
-
- right = middle - 1;
+ max = middle - 1;
}
else
{
@@ -143,21 +144,21 @@ public class AbstractPage<K, V> implemen
}
// Special case : we don't know if the key is present
- int comp = compare( keys[left], key );
+ int comp = compare( keys[max], key );
if ( comp == 0 )
{
- return - ( left + 1 );
+ return - ( max + 1 );
}
else
{
if ( comp < 0 )
{
- return left + 1;
+ return max + 1;
}
else
{
- return left;
+ return min;
}
}
}
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=1350894&r1=1350893&r2=1350894&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
Sat Jun 16 09:07:05 2012
@@ -237,9 +237,6 @@ public class BTree<K, V>
rootPage = modifyResult.getModifiedPage();
modifiedValue = modifyResult.getModifiedValue();
-
- // Save it into the roots.
- roots.put( revision, rootPage );
}
else
{
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=1350894&r1=1350893&r2=1350894&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
Sat Jun 16 09:07:05 2012
@@ -66,16 +66,16 @@ public class Leaf<K, V> extends Abstract
public InsertResult<K, V> insert( long revision, K key, V value )
{
// Find the key into this leaf
- int index = findKeyInPage( key );
+ int pos = findPos( key );
- if ( index < 0 )
+ if ( pos < 0 )
{
// We already have the key in the page : replace the value
// into a copy of this page, unless the page has already be copied
- index = - ( index++ );
+ int index = - ( pos + 1 );
// Replace the existing value in a copy of the current page
- InsertResult<K, V> result = replaceValue( revision, index, value );
+ InsertResult<K, V> result = replaceElement( revision, key, value,
index );
return result;
}
@@ -85,7 +85,7 @@ public class Leaf<K, V> extends Abstract
{
// The current page is not full, it can contain the added element.
// We insert it into a copied page and return the result
- InsertResult<K, V> result = addElement( revision, index, key,
value );
+ InsertResult<K, V> result = addElement( revision, key, value, pos
);
return result;
}
@@ -93,7 +93,7 @@ public class Leaf<K, V> extends Abstract
{
// The Page is already full : we split it and return the overflow
element,
// after having created two pages.
- InsertResult<K, V> result = addAndSplit( revision, key, value,
null, null, index );
+ InsertResult<K, V> result = addAndSplit( revision, key, value, pos
);
return result;
}
@@ -122,26 +122,30 @@ public class Leaf<K, V> extends Abstract
* Copy the current page if needed, and replace the value at the position
we have found the key.
*
* @param revision The new page revision
- * @param index The position of the key in the page
+ * @param pos The position of the key in the page
* @param value the new value
* @return The copied page
*/
- private InsertResult<K, V> replaceValue( long revision, int index, V value
)
+ private InsertResult<K, V> replaceElement( long revision, K key, V value,
int pos )
{
- Leaf<K, V> newPage = this;
+ Leaf<K, V> newLeaf = this;
if ( this.revision != revision )
{
// The page hasn't been modified yet, we need to copy it first
- newPage = (Leaf<K, V>)copy( revision, nbElems );
+ newLeaf = (Leaf<K, V>)copy( revision, nbElems );
}
- // Now we can inject the value and get back the previous one
- V oldValue = newPage.values[index];
- newPage.values[index] = value;
+ // Now we can inject the value
+ V oldValue = newLeaf.values[pos];
+ newLeaf.values[pos] = value;
+
+ // and update the prev/next references
+ newLeaf.prevPage = this.prevPage;
+ newLeaf.nextPage = this.nextPage;
// Create the result
- InsertResult<K, V> result = new ModifyResult<K, V>( newPage, oldValue
);
+ InsertResult<K, V> result = new ModifyResult<K, V>( newLeaf, oldValue
);
return result;
}
@@ -152,14 +156,45 @@ public class Leaf<K, V> extends Abstract
* modified page. The new page will have one more element than the current
page.
*
* @param revision The revision of the modified page
- * @param index The position into the page
* @param key The key to insert
* @param value The value to insert
+ * @param pos The position into the page
* @return The modified page with the <K,V> element added
*/
- private InsertResult<K, V> addElement( long revision, int index, K key, V
value )
+ private InsertResult<K, V> addElement( long revision, K key, V value, int
pos )
{
- return null;
+ // First copy the current page, but add one element in the copied page
+ Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems + 1 );
+
+ // Deal with the special case of an empty page
+ if ( nbElems == 0 )
+ {
+ newLeaf.keys[0] = key;
+ newLeaf.values[0] = value;
+ }
+ else
+ {
+ // Copy the keys and the values up to the insertion position
+ System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
+ System.arraycopy( values, 0, newLeaf.values, 0, pos );
+
+ // Add the new element
+ newLeaf.keys[pos] = key;
+ newLeaf.values[pos] = value;
+
+ // And copy the remaining elements
+ System.arraycopy( keys, pos, newLeaf.keys, pos + 1, keys.length -
pos );
+ System.arraycopy( values, pos, newLeaf.values, pos + 1,
values.length - pos );
+ }
+
+ // Update the prev/next references
+ newLeaf.prevPage = this.prevPage;
+ newLeaf.nextPage = this.nextPage;
+
+ // Create the result
+ InsertResult<K, V> result = new ModifyResult<K, V>( newLeaf, null );
+
+ return result;
}
@@ -173,15 +208,80 @@ public class Leaf<K, V> extends Abstract
* 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 index The position of the insertion of the new element
* @param key The key to add
* @param value The value to add
- * @param left The left child of the added element
- * @param right The right child of the added element
- * @return An OverflowPage containing the pivor, and the new left and
right pages
+ * @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 key, V value,
AbstractPage<K, V> left, AbstractPage<K, V> right, int index )
+ private InsertResult<K, V> addAndSplit( long revision, K key, V value, int
pos )
{
- return null;
+ int middle = btree.pageSize >> 1;
+ Leaf<K, V> leftLeaf = null;
+ Leaf<K, V> rightLeaf = null;
+
+ // Determinate where to store the new value
+ if ( pos < middle )
+ {
+ // The left page will contain the new value
+ leftLeaf = new Leaf<K, V>( btree, revision, middle + 1 );
+
+ // Copy the keys and the values up to the insertion position
+ System.arraycopy( keys, 0, leftLeaf.keys, 0, pos );
+ System.arraycopy( values, 0, leftLeaf.values, 0, pos );
+
+ // Add the new element
+ leftLeaf.keys[pos] = key;
+ leftLeaf.values[pos] = value;
+
+ // And copy the remaining elements
+ System.arraycopy( keys, pos, leftLeaf.keys, pos + 1, middle - pos
);
+ System.arraycopy( values, pos, leftLeaf.values, pos + 1, middle
-pos );
+
+ // Now, create the right page
+ rightLeaf = new Leaf<K, V>( btree, revision, middle );
+
+ // Copy the keys and the values in the right page
+ System.arraycopy( keys, middle, rightLeaf.keys, 0, middle );
+ System.arraycopy( values, middle, rightLeaf.values, 0, middle );
+ }
+ else
+ {
+ // Create the left page
+ leftLeaf = new Leaf<K, V>( btree, revision, middle + 1 );
+
+ // Copy all the element into the left page
+ System.arraycopy( keys, 0, leftLeaf.keys, 0, middle );
+ System.arraycopy( values, 0, leftLeaf.values, 0, middle );
+
+ // Now, create the right page
+ rightLeaf = new Leaf<K, V>( btree, revision, middle );
+
+ // Copy the keys and the values up to the insertion position
+ System.arraycopy( keys, middle, rightLeaf.keys, 0, pos );
+ System.arraycopy( values, middle, rightLeaf.values, 0, pos );
+
+ // Add the new element
+ rightLeaf.keys[pos] = key;
+ rightLeaf.values[pos] = value;
+
+ // And copy the remaining elements
+ System.arraycopy( keys, pos, rightLeaf.keys, pos + 1, nbElems -
pos );
+ System.arraycopy( values, pos, rightLeaf.values, pos + 1, nbElems
-pos );
+ }
+
+ // and update the prev/next references
+ leftLeaf.prevPage = this.prevPage;
+ leftLeaf.nextPage = rightLeaf;
+ rightLeaf.prevPage = leftLeaf;
+ rightLeaf.nextPage = this.nextPage;
+
+ // Get the pivot
+ K pivot = rightLeaf.keys[0];
+
+ // Prepare the result
+ // Create the result
+ InsertResult<K, V> result = new SplitResult<K, V>( pivot, leftLeaf,
rightLeaf );
+
+ 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=1350894&r1=1350893&r2=1350894&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
Sat Jun 16 09:07:05 2012
@@ -86,7 +86,7 @@ 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 = findKeyInPage( key );
+ int index = findPos( key );
if ( index < 0 )
{
@@ -123,8 +123,24 @@ public class Node<K, V> extends Abstract
}
else
{
- // The child has been split
- SplitResult<K, V> modifyResult = (SplitResult<K, V>)result;
+ // The child has been split. We have to insert the new pivot in the
+ // current page, and to reference the two new pages
+ SplitResult<K, V> splitResult = (SplitResult<K, V>)result;
+ K pivot = splitResult.getPivot();
+ Page<K, V> leftPage = splitResult.getLeftPage();
+ Page<K, V> rightPage = splitResult.getRightPage();
+
+ // We have to deal with the two cases :
+ // - the current page is full, we have to split it
+ // - the current page is not full, we insert the new pivot
+ if ( nbElems == btree.getPageSize() )
+ {
+ // The page is full
+ }
+ else
+ {
+ // The page can contain the new pivot
+ }
return null;
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
