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 2013/03/15 20:37:34 UTC
svn commit: r1457076 - in /labs/mavibot/trunk/mavibot/src:
main/java/org/apache/mavibot/btree/ main/java/org/apache/mavibot/btree/store/
test/java/org/apache/mavibot/btree/ test/java/org/apache/mavibot/btree/store/
Author: elecharny
Date: Fri Mar 15 19:37:34 2013
New Revision: 1457076
URL: http://svn.apache.org/r1457076
Log:
o The references to pages are now done using a ReferenceHolder
o Renamed the RM.modifyPage method to writePage
o Added a first drop of code to manage the injection of values that leads to a page split (not yet functional)
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/Cursor.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/store/RecordManager.java
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/store/RecordManagerTest.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=1457076&r1=1457075&r2=1457076&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 Mar 15 19:37:34 2013
@@ -103,8 +103,8 @@ public abstract class AbstractPage<K, V>
return parentPos - 1;
}
- Page<K, V> prevPage = parent.children[parentPos - 1];
- Page<K, V> nextPage = parent.children[parentPos + 1];
+ Page<K, V> prevPage = parent.children[parentPos - 1].getValue( btree );
+ Page<K, V> nextPage = parent.children[parentPos + 1].getValue( btree );
int prevPageSize = prevPage.getNbElems();
int nextPageSize = nextPage.getNbElems();
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java?rev=1457076&r1=1457075&r2=1457076&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java Fri Mar 15 19:37:34 2013
@@ -133,7 +133,7 @@ import java.util.LinkedList;
{
Node<K, V> node = ( Node<K, V> ) newParentPos.page;
- newParentPos = new ParentPos<K, V>( node.children[newPos], 0 );
+ newParentPos = new ParentPos<K, V>( node.children[newPos].getValue( btree ), 0 );
stack.push( newParentPos );
@@ -179,7 +179,8 @@ import java.util.LinkedList;
{
Node<K, V> node = ( Node<K, V> ) newParentPos.page;
- newParentPos = new ParentPos<K, V>( node.children[newPos], node.children[newPos].getNbElems() );
+ newParentPos = new ParentPos<K, V>( node.children[newPos].getValue( btree ), node.children[newPos]
+ .getValue( btree ).getNbElems() );
stack.push( newParentPos );
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=1457076&r1=1457075&r2=1457076&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 Mar 15 19:37:34 2013
@@ -96,7 +96,7 @@ public class Leaf<K, V> extends Abstract
if ( btree.isManaged() )
{
ElementHolder holder = btree.getRecordManager()
- .modifyPage( btree, this, revision, modifiedPage, revision );
+ .writePage( btree, this, modifiedPage, revision );
// Store the offset on disk in the page
( ( AbstractPage<K, V> ) modifiedPage ).setOffset( ( ( ReferenceHolder ) holder ).getOffset() );
@@ -112,6 +112,27 @@ public class Leaf<K, V> extends Abstract
// after having created two pages.
InsertResult<K, V> result = addAndSplit( revision, key, value, pos );
+ // If the BTree is managed, we have to write the two pages
+ // and to keep a track of the two offsets for the upper node
+ if ( btree.isManaged() )
+ {
+ ElementHolder holderLeft = btree.getRecordManager().writePage( btree, this,
+ ( ( SplitResult ) result ).getLeftPage(),
+ revision );
+
+ // Store the offset on disk in the page
+ ( ( AbstractPage ) ( ( SplitResult ) result ).getLeftPage() )
+ .setOffset( ( ( ReferenceHolder ) holderLeft ).getOffset() );
+
+ ElementHolder holderRight = btree.getRecordManager().writePage( btree, this,
+ ( ( SplitResult ) result ).getRightPage(),
+ revision );
+
+ // Store the offset on disk in the page
+ ( ( AbstractPage<K, V> ) ( ( SplitResult ) result ).getRightPage() )
+ .setOffset( ( ( ReferenceHolder ) holderRight ).getOffset() );
+ }
+
return result;
}
}
@@ -162,7 +183,7 @@ 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 = ( Leaf<K, V> ) ( ( ( Node<K, V> ) parent ).children[siblingPos].getValue( btree ) );
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=1457076&r1=1457075&r2=1457076&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 Mar 15 19:37:34 2013
@@ -39,7 +39,7 @@ import org.apache.mavibot.btree.exceptio
public class Node<K, V> extends AbstractPage<K, V>
{
/** Children pages associated with keys. */
- protected Page<K, V>[] children;
+ protected ElementHolder<Page<K, V>, K, V>[] children;
/**
@@ -57,7 +57,7 @@ public class Node<K, V> extends Abstract
super( btree, revision, nbElems );
// Create the children array
- children = new Page[nbElems + 1];
+ children = ( ReferenceHolder<Page<K, V>, K, V>[] ) Array.newInstance( ReferenceHolder.class, nbElems + 1 );
}
@@ -78,9 +78,10 @@ public class Node<K, V> extends Abstract
super( btree, revision, 1 );
// Create the children array, and store the left and right children
- children = new Page[btree.getPageSize()];
- children[0] = leftPage;
- children[1] = rightPage;
+ children = ( ReferenceHolder<Page<K, V>, K, V>[] ) Array.newInstance( ReferenceHolder.class,
+ btree.getPageSize() );
+ children[0] = new ReferenceHolder( btree, leftPage, ( ( AbstractPage ) leftPage ).getOffset() );
+ children[1] = new ReferenceHolder( btree, rightPage, ( ( AbstractPage ) rightPage ).getOffset() );
// Create the keys array and store the pivot into it
// We get the type of array to create from the btree
@@ -108,7 +109,7 @@ public class Node<K, V> extends Abstract
}
// Get the child page into which we will insert the <K, V> tuple
- Page<K, V> child = children[pos];
+ Page<K, V> child = children[pos].getValue( btree );
// and insert the <K, V> into this child
InsertResult<K, V> result = child.insert( revision, key, value );
@@ -159,13 +160,17 @@ public class Node<K, V> extends Abstract
// the modified page.
Node<K, V> newPage = copy( revision );
+ Page<K, V> modifiedPage = removeResult.getModifiedPage();
+
if ( found )
{
- newPage.children[index + 1] = removeResult.getModifiedPage();
+ newPage.children[index + 1] = new ReferenceHolder( btree, modifiedPage,
+ ( ( AbstractPage ) modifiedPage ).getOffset() );
}
else
{
- newPage.children[index] = removeResult.getModifiedPage();
+ newPage.children[index] = new ReferenceHolder( btree, modifiedPage,
+ ( ( AbstractPage ) modifiedPage ).getOffset() );
}
if ( pos < 0 )
@@ -226,7 +231,7 @@ public class Node<K, V> extends Abstract
// Create the new sibling, with one less element at the beginning
Node<K, V> newSibling = new Node<K, V>( btree, revision, sibling.getNbElems() - 1 );
- K siblingKey = sibling.children[0].getLeftMostKey();
+ K siblingKey = sibling.children[0].getValue( btree ).getLeftMostKey();
// Copy the keys and children of the old sibling in the new sibling
System.arraycopy( sibling.keys, 1, newSibling.keys, 0, newSibling.getNbElems() );
@@ -249,7 +254,9 @@ public class Node<K, V> extends Abstract
System.arraycopy( keys, 1, newNode.keys, 0, nbElems - 1 );
// Inject the modified page
- newNode.children[0] = mergedResult.getModifiedPage();
+ Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+ newNode.children[0] = new ReferenceHolder( btree, modifiedPage,
+ ( ( AbstractPage ) modifiedPage ).getOffset() );
// Copy the children
System.arraycopy( children, 2, newNode.children, 1, nbElems - 1 );
@@ -278,7 +285,9 @@ public class Node<K, V> extends Abstract
System.arraycopy( children, 0, newNode.children, 0, index - 1 ); // 5
// Inject the modified page
- newNode.children[index - 1] = mergedResult.getModifiedPage(); // 6
+ Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+ newNode.children[index - 1] = new ReferenceHolder( btree, modifiedPage,
+ ( ( AbstractPage ) modifiedPage ).getOffset() ); // 6
}
// Create the result
@@ -303,7 +312,7 @@ public class Node<K, V> extends Abstract
Node<K, V> sibling, int pos )
{
// The sibling is on the left, borrow the rightmost element
- Page<K, V> siblingChild = sibling.children[sibling.nbElems];
+ Page<K, V> siblingChild = sibling.children[sibling.nbElems].getValue( btree );
// Create the new sibling, with one less element at the end
Node<K, V> newSibling = new Node<K, V>( btree, revision, sibling.getNbElems() - 1 );
@@ -317,7 +326,7 @@ public class Node<K, V> extends Abstract
Node<K, V> newNode = new Node<K, V>( btree, revision, nbElems );
// Sets the first children
- newNode.children[0] = siblingChild; //1
+ newNode.children[0] = new ReferenceHolder( btree, siblingChild, sibling.getOffset() ); //1
int index = Math.abs( pos );
@@ -326,13 +335,15 @@ public class Node<K, V> extends Abstract
newNode.keys[0] = mergedResult.getModifiedPage().getLeftMostKey();
System.arraycopy( keys, 1, newNode.keys, 1, nbElems - 1 );
- newNode.children[1] = mergedResult.getModifiedPage();
+ Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+ newNode.children[1] = new ReferenceHolder( btree, modifiedPage,
+ ( ( AbstractPage ) modifiedPage ).getOffset() );
System.arraycopy( children, 2, newNode.children, 2, nbElems - 1 );
}
else
{
// Set the first key
- newNode.keys[0] = children[0].getLeftMostKey(); //2
+ newNode.keys[0] = children[0].getValue( btree ).getLeftMostKey(); //2
if ( index > 2 )
{
@@ -356,7 +367,9 @@ public class Node<K, V> extends Abstract
System.arraycopy( children, 0, newNode.children, 1, index - 1 ); // 6
// Insert the modified page
- newNode.children[index] = mergedResult.getModifiedPage(); // 7
+ Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+ newNode.children[index] = new ReferenceHolder( btree, modifiedPage,
+ ( ( AbstractPage ) modifiedPage ).getOffset() ); // 7
}
// Create the result
@@ -398,14 +411,16 @@ public class Node<K, V> extends Abstract
newNode.keys[half] = mergedResult.getModifiedPage().getLeftMostKey();
System.arraycopy( keys, 1, newNode.keys, half + 1, half - 1 );
- newNode.children[half + 1] = mergedResult.getModifiedPage();
+ Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+ newNode.children[half + 1] = new ReferenceHolder( btree, modifiedPage,
+ ( ( AbstractPage ) modifiedPage ).getOffset() );
System.arraycopy( children, 2, newNode.children, half + 2, half - 1 );
}
else
{
// Copy the left part of the node keys up to the deletion point
// Insert the new key
- newNode.keys[half] = children[0].getLeftMostKey(); // 3
+ newNode.keys[half] = children[0].getValue( btree ).getLeftMostKey(); // 3
if ( index > 2 )
{
@@ -425,7 +440,9 @@ public class Node<K, V> extends Abstract
System.arraycopy( children, 0, newNode.children, half + 1, index - 1 ); // 7
// Inject the new merged child
- newNode.children[half + index] = mergedResult.getModifiedPage(); //8
+ Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+ newNode.children[half + index] = new ReferenceHolder( btree, modifiedPage,
+ ( ( AbstractPage ) modifiedPage ).getOffset() ); //8
}
}
else
@@ -437,7 +454,9 @@ public class Node<K, V> extends Abstract
System.arraycopy( keys, 1, newNode.keys, 0, half - 1 );
// Insert the first child
- newNode.children[0] = mergedResult.getModifiedPage();
+ Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+ newNode.children[0] = new ReferenceHolder( btree, modifiedPage,
+ ( ( AbstractPage ) modifiedPage ).getOffset() );
// Copy the node children
System.arraycopy( children, 2, newNode.children, 1, half - 1 );
@@ -458,7 +477,9 @@ public class Node<K, V> extends Abstract
newNode.keys[index - 2] = mergedResult.getModifiedPage().getLeftMostKey(); //2
// Inject the modified children
- newNode.children[index - 1] = mergedResult.getModifiedPage(); // 7
+ Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+ newNode.children[index - 1] = new ReferenceHolder( btree, modifiedPage,
+ ( ( AbstractPage ) modifiedPage ).getOffset() ); // 7
// Add the remaining node's key if needed
if ( index < half )
@@ -503,12 +524,12 @@ public class Node<K, V> extends Abstract
if ( found )
{
index = -( pos + 1 );
- child = children[-pos];
+ child = children[-pos].getValue( btree );
deleteResult = child.delete( revision, key, this, -pos );
}
else
{
- child = children[pos];
+ child = children[pos].getValue( btree );
deleteResult = child.delete( revision, key, this, pos );
}
@@ -572,7 +593,7 @@ public class Node<K, V> extends Abstract
// a sibling, or we will have to merge two pages
int siblingPos = selectSibling( ( Node<K, V> ) parent, parentPos );
- Node<K, V> sibling = ( Node<K, V> ) ( ( Node<K, V> ) parent ).children[siblingPos];
+ Node<K, V> sibling = ( Node<K, V> ) ( ( ( Node<K, V> ) parent ).children[siblingPos].getValue( btree ) );
if ( sibling.getNbElems() > halfSize )
{
@@ -633,8 +654,10 @@ public class Node<K, V> extends Abstract
newPage.keys[pos + 1] = modifiedSibling.findLeftMost().getKey();
// Update the children
- newPage.children[pos + 1] = modifiedPage;
- newPage.children[pos + 2] = modifiedSibling;
+ newPage.children[pos + 1] = new ReferenceHolder( btree, modifiedPage,
+ ( ( AbstractPage ) modifiedPage ).getOffset() );
+ newPage.children[pos + 2] = new ReferenceHolder( btree, modifiedSibling,
+ ( ( AbstractPage ) modifiedSibling ).getOffset() );
}
else
{
@@ -642,8 +665,10 @@ public class Node<K, V> extends Abstract
newPage.keys[pos] = modifiedPage.findLeftMost().getKey();
// Update the children
- newPage.children[pos] = modifiedSibling;
- newPage.children[pos + 1] = modifiedPage;
+ newPage.children[pos] = new ReferenceHolder( btree, modifiedSibling,
+ ( ( AbstractPage ) modifiedSibling ).getOffset() );
+ newPage.children[pos + 1] = new ReferenceHolder( btree, modifiedPage,
+ ( ( AbstractPage ) modifiedPage ).getOffset() );
}
}
else
@@ -654,8 +679,10 @@ public class Node<K, V> extends Abstract
newPage.keys[pos] = modifiedSibling.findLeftMost().getKey();
// Update the children
- newPage.children[pos] = modifiedPage;
- newPage.children[pos + 1] = modifiedSibling;
+ newPage.children[pos] = new ReferenceHolder( btree, modifiedPage,
+ ( ( AbstractPage ) modifiedPage ).getOffset() );
+ newPage.children[pos + 1] = new ReferenceHolder( btree, modifiedSibling,
+ ( ( AbstractPage ) modifiedSibling ).getOffset() );
}
else
{
@@ -663,8 +690,10 @@ public class Node<K, V> extends Abstract
newPage.keys[pos - 1] = modifiedPage.findLeftMost().getKey();
// Update the children
- newPage.children[pos - 1] = modifiedSibling;
- newPage.children[pos] = modifiedPage;
+ newPage.children[pos - 1] = new ReferenceHolder( btree, modifiedSibling,
+ ( ( AbstractPage ) modifiedSibling ).getOffset() );
+ newPage.children[pos] = new ReferenceHolder( btree, modifiedPage,
+ ( ( AbstractPage ) modifiedPage ).getOffset() );
}
}
@@ -695,7 +724,9 @@ public class Node<K, V> extends Abstract
{
// Copy the keys and the children
System.arraycopy( keys, 1, newNode.keys, 0, newNode.nbElems );
- newNode.children[0] = mergedResult.getModifiedPage();
+ Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+ newNode.children[0] = new ReferenceHolder( btree, modifiedPage,
+ ( ( AbstractPage ) modifiedPage ).getOffset() );
System.arraycopy( children, 2, newNode.children, 1, nbElems - 1 );
}
else
@@ -716,7 +747,9 @@ public class Node<K, V> extends Abstract
// Copy the children
System.arraycopy( children, 0, newNode.children, 0, index + 1 );
- newNode.children[index + 1] = mergedResult.getModifiedPage();
+ Page<K, V> modifiedPage = mergedResult.getModifiedPage();
+ newNode.children[index + 1] = new ReferenceHolder( btree, modifiedPage,
+ ( ( AbstractPage ) modifiedPage ).getOffset() );
if ( index < nbElems - 2 )
{
@@ -742,11 +775,11 @@ public class Node<K, V> extends Abstract
{
// Here, if we have found the key in the node, then we must go down into
// the right child, not the left one
- return children[-pos].exist( key );
+ return children[-pos].getValue( btree ).exist( key );
}
else
{
- return children[pos].exist( key );
+ return children[pos].getValue( btree ).exist( key );
}
}
@@ -762,11 +795,11 @@ public class Node<K, V> extends Abstract
{
// Here, if we have found the key in the node, then we must go down into
// the right child, not the left one
- return children[-pos].get( key );
+ return children[-pos].getValue( btree ).get( key );
}
else
{
- return children[pos].get( key );
+ return children[pos].getValue( btree ).get( key );
}
}
@@ -778,7 +811,8 @@ public class Node<K, V> extends Abstract
*/
public void setValue( int pos, ElementHolder<Page<K, V>, K, V> value )
{
- children[pos] = value.getValue( btree );
+ Page<K, V> page = value.getValue( btree );
+ children[pos] = new ReferenceHolder( btree, page, ( ( AbstractPage<K, V> ) page ).getOffset() );
}
@@ -789,7 +823,7 @@ public class Node<K, V> extends Abstract
{
if ( pos < nbElems + 1 )
{
- return children[pos];
+ return children[pos].getValue( btree );
}
else
{
@@ -813,7 +847,7 @@ public class Node<K, V> extends Abstract
// We first stack the current page
stack.push( new ParentPos<K, V>( this, pos ) );
- return children[pos].browse( key, transaction, stack );
+ return children[pos].getValue( btree ).browse( key, transaction, stack );
}
@@ -824,7 +858,7 @@ public class Node<K, V> extends Abstract
{
stack.push( new ParentPos<K, V>( this, 0 ) );
- return children[0].browse( transaction, stack );
+ return children[0].getValue( btree ).browse( transaction, stack );
}
@@ -845,7 +879,9 @@ 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[pos] = result.modifiedPage;
+ Page<K, V> modifiedPage = result.getModifiedPage();
+ ( ( Node<K, V> ) newPage ).children[pos] = new ReferenceHolder( btree, modifiedPage,
+ ( ( AbstractPage ) modifiedPage ).getOffset() );
// We can return the result, where we update the modifiedPage,
// to avoid the creation of a new object
@@ -875,8 +911,8 @@ public class Node<K, V> extends Abstract
if ( nbElems == 0 )
{
newNode.keys[0] = key;
- newNode.children[0] = leftPage;
- newNode.children[1] = rightPage;
+ newNode.children[0] = new ReferenceHolder( btree, leftPage, ( ( AbstractPage ) leftPage ).getOffset() );
+ newNode.children[1] = new ReferenceHolder( btree, rightPage, ( ( AbstractPage ) rightPage ).getOffset() );
}
else
{
@@ -886,8 +922,9 @@ public class Node<K, V> extends Abstract
// Add the new key and children
newNode.keys[pos] = key;
- newNode.children[pos] = leftPage;
- newNode.children[pos + 1] = rightPage;
+ newNode.children[pos] = new ReferenceHolder( btree, leftPage, ( ( AbstractPage ) leftPage ).getOffset() );
+ newNode.children[pos + 1] = new ReferenceHolder( btree, rightPage,
+ ( ( AbstractPage ) rightPage ).getOffset() );
// And copy the remaining keys and children
System.arraycopy( keys, pos, newNode.keys, pos + 1, keys.length - pos );
@@ -936,8 +973,9 @@ public class Node<K, V> extends Abstract
// Add the new element
newLeftPage.keys[pos] = pivot;
- newLeftPage.children[pos] = leftPage;
- newLeftPage.children[pos + 1] = rightPage;
+ newLeftPage.children[pos] = new ReferenceHolder( btree, leftPage, ( ( AbstractPage ) leftPage ).getOffset() );
+ newLeftPage.children[pos + 1] = new ReferenceHolder( btree, rightPage,
+ ( ( AbstractPage ) rightPage ).getOffset() );;
// And copy the remaining elements minus the new pivot
System.arraycopy( keys, pos, newLeftPage.keys, pos + 1, middle - pos - 1 );
@@ -959,12 +997,14 @@ public class Node<K, V> extends Abstract
// Copy the keys and the children up to the insertion position (here, middle)
System.arraycopy( keys, 0, newLeftPage.keys, 0, middle );
System.arraycopy( children, 0, newLeftPage.children, 0, middle );
- newLeftPage.children[middle] = leftPage;
+ newLeftPage.children[middle] = new ReferenceHolder( btree, leftPage,
+ ( ( AbstractPage ) leftPage ).getOffset() );
// And process the right page now
System.arraycopy( keys, middle, newRightPage.keys, 0, middle );
System.arraycopy( children, middle + 1, newRightPage.children, 1, middle );
- newRightPage.children[0] = rightPage;
+ newRightPage.children[0] = new ReferenceHolder( btree, rightPage,
+ ( ( AbstractPage ) rightPage ).getOffset() );;
// Create the result
InsertResult<K, V> result = new SplitResult<K, V>( pivot, newLeftPage, newRightPage );
@@ -983,8 +1023,10 @@ public class Node<K, V> extends Abstract
// Add the new element
newRightPage.keys[pos - middle - 1] = pivot;
- newRightPage.children[pos - middle - 1] = leftPage;
- newRightPage.children[pos - middle] = rightPage;
+ newRightPage.children[pos - middle - 1] = new ReferenceHolder( btree, leftPage,
+ ( ( AbstractPage ) leftPage ).getOffset() );
+ newRightPage.children[pos - middle] = new ReferenceHolder( btree, rightPage,
+ ( ( AbstractPage ) rightPage ).getOffset() );
// And copy the remaining elements minus the new pivot
System.arraycopy( keys, pos, newRightPage.keys, pos - middle, nbElems - pos );
@@ -1023,7 +1065,7 @@ public class Node<K, V> extends Abstract
*/
public K getLeftMostKey()
{
- return children[0].getLeftMostKey();
+ return children[0].getValue( btree ).getLeftMostKey();
}
@@ -1032,7 +1074,7 @@ public class Node<K, V> extends Abstract
*/
public Tuple<K, V> findLeftMost()
{
- return children[0].findLeftMost();
+ return children[0].getValue( btree ).findLeftMost();
}
@@ -1041,7 +1083,7 @@ public class Node<K, V> extends Abstract
*/
public Tuple<K, V> findRightMost()
{
- return children[nbElems].findRightMost();
+ return children[nbElems].getValue( btree ).findRightMost();
}
@@ -1065,7 +1107,7 @@ public class Node<K, V> extends Abstract
}
else
{
- sb.append( 'r' ).append( children[0].getRevision() );
+ sb.append( 'r' ).append( children[0].getValue( btree ).getRevision() );
}
for ( int i = 0; i < nbElems; i++ )
@@ -1078,7 +1120,7 @@ public class Node<K, V> extends Abstract
}
else
{
- sb.append( 'r' ).append( children[i + 1].getRevision() );
+ sb.append( 'r' ).append( children[i + 1].getValue( btree ).getRevision() );
}
}
}
@@ -1099,14 +1141,14 @@ public class Node<K, V> extends Abstract
if ( nbElems > 0 )
{
// Start with the first child
- sb.append( children[0].dumpPage( tabs + " " ) );
+ sb.append( children[0].getValue( btree ).dumpPage( tabs + " " ) );
for ( int i = 0; i < nbElems; i++ )
{
sb.append( tabs );
sb.append( "<" );
sb.append( keys[i] ).append( ">\n" );
- sb.append( children[i + 1].dumpPage( tabs + " " ) );
+ sb.append( children[i + 1].getValue( btree ).dumpPage( tabs + " " ) );
}
}
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/store/RecordManager.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/store/RecordManager.java?rev=1457076&r1=1457075&r2=1457076&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/store/RecordManager.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/store/RecordManager.java Fri Mar 15 19:37:34 2013
@@ -1476,7 +1476,7 @@ public class RecordManager
* @return The offset of the new page
* @throws IOException
*/
- public ElementHolder modifyPage( BTree btree, Page oldPage, long oldRevision, Page newPage, long newRevision )
+ public ElementHolder writePage( BTree btree, Page oldPage, Page newPage, long newRevision )
throws IOException
{
// We first need to save the new page on disk
Modified: labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java?rev=1457076&r1=1457075&r2=1457076&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java (original)
+++ labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java Fri Mar 15 19:37:34 2013
@@ -1023,7 +1023,7 @@ public class InMemoryBTreeTest
}
- private void addPage( Node<Integer, String> node, Page<Integer, String> page, int pos )
+ private void addPage( BTree<Integer, String> btree, Node<Integer, String> node, Page<Integer, String> page, int pos )
{
Tuple<Integer, String> leftmost = page.findLeftMost();
@@ -1032,7 +1032,8 @@ public class InMemoryBTreeTest
node.keys[pos - 1] = leftmost.getKey();
}
- node.children[pos] = page;
+ node.children[pos] = new ReferenceHolder<Page<Integer, String>, Integer, String>( btree, page,
+ ( ( AbstractPage<Integer, String> ) page ).getOffset() );
}
@@ -1119,13 +1120,13 @@ public class InMemoryBTreeTest
counter += 2;
- addPage( node, leaf, j );
+ addPage( btree, node, leaf, j );
EXPECTED1.add( even );
EXPECTED1.add( even + 1 );
}
- addPage( root, node, i );
+ addPage( btree, root, node, i );
}
btree.setRoot( root );
Modified: labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java?rev=1457076&r1=1457075&r2=1457076&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java (original)
+++ labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java Fri Mar 15 19:37:34 2013
@@ -236,9 +236,12 @@ public class LeafTest
right = insert( right, 12L, "v12" );
right = insert( right, 13L, "v13" );
- parent.children[0] = left;
- parent.children[1] = target;
- parent.children[2] = right;
+ parent.children[0] = new ReferenceHolder<Page<Long, String>, Long, String>( null, left,
+ ( ( AbstractPage<Long, String> ) left ).getOffset() );
+ parent.children[1] = new ReferenceHolder<Page<Long, String>, Long, String>( null, target,
+ ( ( AbstractPage<Long, String> ) target ).getOffset() );
+ parent.children[2] = new ReferenceHolder<Page<Long, String>, Long, String>( null, right,
+ ( ( AbstractPage<Long, String> ) right ).getOffset() );
// Update the parent
parent.keys[0] = 6L;
@@ -306,9 +309,12 @@ public class LeafTest
right = insert( right, 13L, "v13" );
right = insert( right, 14L, "v14" );
- parent.children[0] = left;
- parent.children[1] = target;
- parent.children[2] = right;
+ parent.children[0] = new ReferenceHolder<Page<Long, String>, Long, String>( null, left,
+ ( ( AbstractPage<Long, String> ) left ).getOffset() );
+ parent.children[1] = new ReferenceHolder<Page<Long, String>, Long, String>( null, target,
+ ( ( AbstractPage<Long, String> ) target ).getOffset() );
+ parent.children[2] = new ReferenceHolder<Page<Long, String>, Long, String>( null, right,
+ ( ( AbstractPage<Long, String> ) right ).getOffset() );
// Update the parent
parent.keys[0] = 6L;
@@ -376,9 +382,12 @@ public class LeafTest
right = insert( right, 11L, "v11" );
right = insert( right, 12L, "v12" );
- parent.children[0] = left;
- parent.children[1] = target;
- parent.children[2] = right;
+ parent.children[0] = new ReferenceHolder<Page<Long, String>, Long, String>( null, left,
+ ( ( AbstractPage<Long, String> ) left ).getOffset() );
+ parent.children[1] = new ReferenceHolder<Page<Long, String>, Long, String>( null, target,
+ ( ( AbstractPage<Long, String> ) target ).getOffset() );;
+ parent.children[2] = new ReferenceHolder<Page<Long, String>, Long, String>( null, right,
+ ( ( AbstractPage<Long, String> ) right ).getOffset() );
// Update the parent
parent.keys[0] = 5L;
Modified: labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/store/RecordManagerTest.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/store/RecordManagerTest.java?rev=1457076&r1=1457075&r2=1457076&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/store/RecordManagerTest.java (original)
+++ labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/store/RecordManagerTest.java Fri Mar 15 19:37:34 2013
@@ -93,7 +93,6 @@ public class RecordManagerTest
/**
* Test the creation of a RecordManager with a BTree containing data.
- * @throws KeyNotFoundException
*/
@Test
public void testRecordManagerWithBTree() throws IOException, BTreeAlreadyManagedException, KeyNotFoundException
@@ -142,7 +141,7 @@ public class RecordManagerTest
assertEquals( btree.getRevision(), btree1.getRevision() );
assertEquals( btree.getValueSerializer().getClass().getName(), btree1.getValueSerializer().getClass().getName() );
- // Check the stord element
+ // Check the stored element
assertTrue( btree1.exist( 1L ) );
assertTrue( btree1.exist( 3L ) );
assertTrue( btree1.exist( 5L ) );
@@ -150,4 +149,65 @@ public class RecordManagerTest
assertEquals( "V3", btree1.get( 3L ) );
assertEquals( "V5", btree1.get( 5L ) );
}
+
+
+ /**
+ * Test the creation of a RecordManager with a BTree containing data, enough for some Node to be created.
+ */
+ @Test
+ public void testRecordManagerWithBTreeLeafNode() throws IOException, BTreeAlreadyManagedException,
+ KeyNotFoundException
+ {
+ File tempFile = File.createTempFile( "mavibot", ".db" );
+ String tempFileName = tempFile.getAbsolutePath();
+ tempFile.deleteOnExit();
+
+ RecordManager recordManager = new RecordManager( tempFileName, 32 );
+
+ assertNotNull( recordManager );
+
+ // Create a new BTree
+ BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
+
+ // And make it managed by the RM
+ recordManager.manage( btree );
+
+ // Now, add some elements in the BTree
+ for ( long i = 1L; i < 32L; i++ )
+ {
+ btree.insert( i, "V" + i );
+ }
+
+ // Close the recordManager
+ recordManager.close();
+
+ // Now, try to reload the file back
+ RecordManager recordManager1 = new RecordManager( tempFileName );
+
+ assertEquals( 1, recordManager1.getNbManagedTrees() );
+
+ Set<String> managedBTrees = recordManager1.getManagedTrees();
+
+ assertEquals( 1, managedBTrees.size() );
+ assertTrue( managedBTrees.contains( "test" ) );
+
+ BTree<Long, String> btree1 = recordManager1.getManagedTree( "test" );
+
+ assertNotNull( btree1 );
+ assertEquals( btree.getComparator().getClass().getName(), btree1.getComparator().getClass().getName() );
+ assertEquals( btree.getFile(), btree1.getFile() );
+ assertEquals( btree.getKeySerializer().getClass().getName(), btree1.getKeySerializer().getClass().getName() );
+ assertEquals( btree.getName(), btree1.getName() );
+ assertEquals( btree.getNbElems(), btree1.getNbElems() );
+ assertEquals( btree.getPageSize(), btree1.getPageSize() );
+ assertEquals( btree.getRevision(), btree1.getRevision() );
+ assertEquals( btree.getValueSerializer().getClass().getName(), btree1.getValueSerializer().getClass().getName() );
+
+ // Check the stored element
+ for ( long i = 1L; i < 32L; i++ )
+ {
+ assertTrue( btree1.exist( i ) );
+ assertEquals( "V" + i, btree1.get( i ) );
+ }
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@labs.apache.org
For additional commands, e-mail: commits-help@labs.apache.org