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/04/29 08:15:10 UTC
svn commit: r1476901 -
/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/
Author: elecharny
Date: Mon Apr 29 06:15:10 2013
New Revision: 1476901
URL: http://svn.apache.org/r1476901
Log:
Added the copiedPages lists into the results
Added:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Result.java
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractBorrowedFromSiblingResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractDeleteResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTreeBuilder.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromLeftResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromRightResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/DeleteResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/InsertResult.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/MergedWithSiblingResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ModifyResult.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/NotPresentResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RemoveResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/SplitResult.java
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractBorrowedFromSiblingResult.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractBorrowedFromSiblingResult.java?rev=1476901&r1=1476900&r2=1476901&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractBorrowedFromSiblingResult.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractBorrowedFromSiblingResult.java Mon Apr 29 06:15:10 2013
@@ -20,6 +20,9 @@
package org.apache.mavibot.btree;
+import java.util.List;
+
+
/**
* The result of a delete operation, when the child has not been merged, and when
* we have borrowed an element from the left sibling. It contains the
@@ -64,6 +67,24 @@ package org.apache.mavibot.btree;
/**
+ * A constructor for RemoveResult with a list of copied pages.
+ *
+ * @param copiedPages the list of copied pages
+ * @param modifiedPage The modified page
+ * @param modifiedSibling The modified sibling
+ * @param removedElement The removed element (can be null if the key wasn't present in the tree)
+ */
+ /* No qualifier */AbstractBorrowedFromSiblingResult( List<Page<K, V>> copiedPages, Page<K, V> modifiedPage,
+ Page<K, V> modifiedSibling,
+ Tuple<K, V> removedElement, SiblingPosition position )
+ {
+ super( copiedPages, modifiedPage, removedElement );
+ this.modifiedSibling = modifiedSibling;
+ this.position = position;
+ }
+
+
+ /**
* {@inheritDoc}
*/
public Page<K, V> getModifiedSibling()
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractDeleteResult.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractDeleteResult.java?rev=1476901&r1=1476900&r2=1476901&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractDeleteResult.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractDeleteResult.java Mon Apr 29 06:15:10 2013
@@ -20,6 +20,9 @@
package org.apache.mavibot.btree;
+import java.util.List;
+
+
/**
* An abstract class to gather common elements of the DeleteResult
*
@@ -28,7 +31,7 @@ package org.apache.mavibot.btree;
* @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
*/
-/* No qualifier */abstract class AbstractDeleteResult<K, V> implements DeleteResult<K, V>
+/* No qualifier */abstract class AbstractDeleteResult<K, V> extends AbstractResult<K, V> implements DeleteResult<K, V>
{
/** The modified page reference */
private Page<K, V> modifiedPage;
@@ -45,6 +48,23 @@ package org.apache.mavibot.btree;
*/
/* No qualifier */AbstractDeleteResult( Page<K, V> modifiedPage, Tuple<K, V> removedElement )
{
+ super();
+ this.modifiedPage = modifiedPage;
+ this.removedElement = removedElement;
+ }
+
+
+ /**
+ * The default constructor for AbstractDeleteResult.
+ *
+ * @param copiedPages the list of copied pages
+ * @param modifiedPage The modified page
+ * @param removedElement The removed element (can be null if the key wasn't present in the tree)
+ */
+ /* No qualifier */AbstractDeleteResult( List<Page<K, V>> copiedPages, Page<K, V> modifiedPage,
+ Tuple<K, V> removedElement )
+ {
+ super( copiedPages );
this.modifiedPage = modifiedPage;
this.removedElement = removedElement;
}
Added: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractResult.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractResult.java?rev=1476901&view=auto
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractResult.java (added)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractResult.java Mon Apr 29 06:15:10 2013
@@ -0,0 +1,78 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.mavibot.btree;
+
+
+import java.util.ArrayList;
+import java.util.List;
+
+
+/**
+ * An abstract class to gather common elements of the Result classes
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+/* No qualifier */abstract class AbstractResult<K, V> implements Result<K, V>
+{
+ /** The list of copied page reference */
+ private List<Page<K, V>> copiedPage;
+
+
+ /**
+ * The default constructor for AbstractResult.
+ *
+ */
+ /* No qualifier */AbstractResult()
+ {
+ copiedPage = new ArrayList<Page<K, V>>();
+ }
+
+
+ /**
+ * Creates an instance of AbstractResult with an initialized list of copied pages.
+ *
+ * @param copiedPages The list of copied pages to store in this result
+ */
+ /* No qualifier */AbstractResult( List<Page<K, V>> copiedPages )
+ {
+ this.copiedPage = copiedPages;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public List<Page<K, V>> getCopiedPages()
+ {
+ return copiedPage;
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ public void addCopiedPage( Page<K, V> page )
+ {
+ copiedPage.add( page );
+ }
+}
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTreeBuilder.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTreeBuilder.java?rev=1476901&r1=1476900&r2=1476901&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTreeBuilder.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BTreeBuilder.java Mon Apr 29 06:15:10 2013
@@ -43,11 +43,11 @@ import org.apache.mavibot.btree.serializ
public class BTreeBuilder<K, V>
{
private String name;
-
+
private int numKeysInNode;
-
+
private ElementSerializer<K> keySerializer;
-
+
private ElementSerializer<V> valueSerializer;
@@ -67,9 +67,9 @@ public class BTreeBuilder<K, V>
btree.init();
List<Page<K, V>> lstLeaves = new ArrayList<Page<K, V>>();
-
+
int totalTupleCount = 0;
-
+
Leaf<K, V> leaf1 = createLeaf( btree, 0, numKeysInNode );
lstLeaves.add( leaf1 );
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromLeftResult.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromLeftResult.java?rev=1476901&r1=1476900&r2=1476901&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromLeftResult.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromLeftResult.java Mon Apr 29 06:15:10 2013
@@ -20,6 +20,9 @@
package org.apache.mavibot.btree;
+import java.util.List;
+
+
/**
* The result of a delete operation, when the child has not been merged, and when
* we have borrowed an element from the left sibling. It contains the
@@ -47,6 +50,23 @@ package org.apache.mavibot.btree;
/**
+ * A constructor for BorrowedFromLeftResult which takes a list of copied pages.
+ *
+ * @param copiedPages the list of copied pages
+ * @param modifiedPage The modified page
+ * @param modifiedSibling The modified sibling
+ * @param removedElement The removed element (can be null if the key wasn't present in the tree)
+ */
+ /* No qualifier */BorrowedFromLeftResult( List<Page<K, V>> copiedPages, Page<K, V> modifiedPage,
+ Page<K, V> modifiedSibling,
+ Tuple<K, V> removedElement )
+ {
+ super( copiedPages, modifiedPage, modifiedSibling, removedElement,
+ AbstractBorrowedFromSiblingResult.SiblingPosition.LEFT );
+ }
+
+
+ /**
* @see Object#toString()
*/
public String toString()
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromRightResult.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromRightResult.java?rev=1476901&r1=1476900&r2=1476901&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromRightResult.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromRightResult.java Mon Apr 29 06:15:10 2013
@@ -20,6 +20,9 @@
package org.apache.mavibot.btree;
+import java.util.List;
+
+
/**
* The result of a delete operation, when the child has not been merged. It contains the
* reference to the modified page, and the removed element.
@@ -46,6 +49,22 @@ package org.apache.mavibot.btree;
/**
+ * A constructor for BorrowedFromRightResult which takes a list of copied pages.
+ *
+ * @param copiedPages the list of copied pages
+ * @param modifiedPage The modified page
+ * @param modifiedSibling The modified sibling
+ * @param removedElement The removed element (can be null if the key wasn't present in the tree)
+ */
+ /* No qualifier */BorrowedFromRightResult( List<Page<K, V>> copiedPages, Page<K, V> modifiedPage,
+ Page<K, V> modifiedSibling, Tuple<K, V> removedElement )
+ {
+ super( copiedPages, modifiedPage, modifiedSibling, removedElement,
+ AbstractBorrowedFromSiblingResult.SiblingPosition.RIGHT );
+ }
+
+
+ /**
* @see Object#toString()
*/
public String toString()
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/DeleteResult.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/DeleteResult.java?rev=1476901&r1=1476900&r2=1476901&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/DeleteResult.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/DeleteResult.java Mon Apr 29 06:15:10 2013
@@ -28,7 +28,7 @@ package org.apache.mavibot.btree;
* @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
*/
-interface DeleteResult<K, V>
+interface DeleteResult<K, V> extends Result<K, V>
{
/**
* @return the modifiedPage
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/InsertResult.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/InsertResult.java?rev=1476901&r1=1476900&r2=1476901&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/InsertResult.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/InsertResult.java Mon Apr 29 06:15:10 2013
@@ -30,6 +30,6 @@ package org.apache.mavibot.btree;
* @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
*/
-interface InsertResult<K, V>
+interface InsertResult<K, V> extends Result<K, V>
{
}
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=1476901&r1=1476900&r2=1476901&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 Apr 29 06:15:10 2013
@@ -20,13 +20,14 @@
package org.apache.mavibot.btree;
+import static org.apache.mavibot.btree.InternalUtil.setDupsContainer;
+
import java.io.IOException;
import java.lang.reflect.Array;
import java.util.LinkedList;
import org.apache.mavibot.btree.exception.EndOfFileExceededException;
import org.apache.mavibot.btree.exception.KeyNotFoundException;
-import static org.apache.mavibot.btree.InternalUtil.*;
/**
@@ -107,6 +108,7 @@ import static org.apache.mavibot.btree.I
Page<K, V> modifiedPage = addElement( revision, key, value, pos );
InsertResult<K, V> result = new ModifyResult<K, V>( modifiedPage, null );
+ result.addCopiedPage( this );
return result;
}
@@ -115,6 +117,7 @@ import static org.apache.mavibot.btree.I
// 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, pos );
+ result.addCopiedPage( this );
return result;
}
@@ -154,8 +157,6 @@ import static org.apache.mavibot.btree.I
if ( btree.isAllowDuplicates() )
{
- if ( value == null )
- ;
BTree<V, V> dups = ( BTree<V, V> ) values[index].getValue( btree );
if ( dups.hasKey( value ) )
@@ -220,6 +221,9 @@ import static org.apache.mavibot.btree.I
// Just remove the entry if it's present
copyAfterRemovingElement( keyRemoved, newLeaf, index );
+ // The current page is added in the copied page list
+ defaultResult.addCopiedPage( this );
+
return defaultResult;
}
else if ( keyRemoved )
@@ -271,6 +275,9 @@ import static org.apache.mavibot.btree.I
// key in its parents)
copyAfterRemovingElement( keyRemoved, newLeaf, index );
+ // The current page is added in the copied page list
+ defaultResult.addCopiedPage( this );
+
return defaultResult;
}
}
@@ -332,6 +339,9 @@ import static org.apache.mavibot.btree.I
DeleteResult<K, V> result = new MergedWithSiblingResult<K, V>( newLeaf,
removedElement );
+ result.addCopiedPage( this );
+ result.addCopiedPage( sibling );
+
return result;
}
@@ -375,6 +385,10 @@ import static org.apache.mavibot.btree.I
DeleteResult<K, V> result = new BorrowedFromLeftResult<K, V>( newLeaf, newSibling, removedElement );
+ // Add the copied pages to the list
+ result.addCopiedPage( this );
+ result.addCopiedPage( sibling );
+
return result;
}
@@ -422,6 +436,10 @@ import static org.apache.mavibot.btree.I
DeleteResult<K, V> result = new BorrowedFromRightResult<K, V>( newLeaf, newSibling, removedElement );
+ // Add the copied pages to the list
+ result.addCopiedPage( this );
+ result.addCopiedPage( sibling );
+
return result;
}
@@ -495,11 +513,11 @@ import static org.apache.mavibot.btree.I
@Override
public BTree<V, V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
{
- if( !btree.isAllowDuplicates() )
+ if ( !btree.isAllowDuplicates() )
{
throw new IllegalArgumentException( "Duplicates are not allowed in this tree" );
}
-
+
int pos = findPos( key );
if ( pos < 0 )
@@ -704,6 +722,7 @@ import static org.apache.mavibot.btree.I
if ( btree.isAllowDuplicates() )
{
BTree<V, V> dupValues = ( BTree<V, V> ) newLeaf.values[pos].getValue( btree );
+
// return value will always be null here
if ( !dupValues.hasKey( value ) )
{
@@ -723,6 +742,7 @@ import static org.apache.mavibot.btree.I
// Create the result
InsertResult<K, V> result = new ModifyResult<K, V>( newLeaf, oldValue );
+ result.addCopiedPage( this );
return result;
}
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/MergedWithSiblingResult.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/MergedWithSiblingResult.java?rev=1476901&r1=1476900&r2=1476901&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/MergedWithSiblingResult.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/MergedWithSiblingResult.java Mon Apr 29 06:15:10 2013
@@ -20,6 +20,9 @@
package org.apache.mavibot.btree;
+import java.util.List;
+
+
/**
* The result of a delete operation, when the child has not been merged. It contains the
* reference to the modified page, and the removed element.
@@ -44,6 +47,20 @@ package org.apache.mavibot.btree;
/**
+ * A constructor for RemoveResult which takes a list of copied page.
+ *
+ * @param copiedPages the list of copied pages
+ * @param modifiedPage The modified page
+ * @param removedElement The removed element (can be null if the key wasn't present in the tree)
+ */
+ /* No qualifier */MergedWithSiblingResult( List<Page<K, V>> copiedPages, Page<K, V> modifiedPage,
+ Tuple<K, V> removedElement )
+ {
+ super( copiedPages, modifiedPage, removedElement );
+ }
+
+
+ /**
* @see Object#toString()
*/
public String toString()
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ModifyResult.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ModifyResult.java?rev=1476901&r1=1476900&r2=1476901&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ModifyResult.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ModifyResult.java Mon Apr 29 06:15:10 2013
@@ -20,6 +20,9 @@
package org.apache.mavibot.btree;
+import java.util.List;
+
+
/**
* The result of an insert operation, when the child has not been split. It contains the
* reference to the modified page.
@@ -29,7 +32,7 @@ package org.apache.mavibot.btree;
* @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
*/
-/* No qualifier */class ModifyResult<K, V> implements InsertResult<K, V>
+/* No qualifier */class ModifyResult<K, V> extends AbstractResult<K, V> implements InsertResult<K, V>
{
/** The modified page reference */
protected Page<K, V> modifiedPage;
@@ -46,6 +49,22 @@ package org.apache.mavibot.btree;
*/
/* No qualifier */ModifyResult( Page<K, V> modifiedPage, V modifiedValue )
{
+ super();
+ this.modifiedPage = modifiedPage;
+ this.modifiedValue = modifiedValue;
+ }
+
+
+ /**
+ * A constructor for ModifyResult which takes a list of copied pages.
+ *
+ * @param copiedPages the list of copied pages
+ * @param modifiedPage The modified page
+ * @param modifiedvalue The modified value (can be null if the key wasn't present in the tree)
+ */
+ /* No qualifier */ModifyResult( List<Page<K, V>> copiedPages, Page<K, V> modifiedPage, V modifiedValue )
+ {
+ super( copiedPages );
this.modifiedPage = modifiedPage;
this.modifiedValue = modifiedValue;
}
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=1476901&r1=1476900&r2=1476901&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 Apr 29 06:15:10 2013
@@ -23,6 +23,7 @@ package org.apache.mavibot.btree;
import java.io.IOException;
import java.lang.reflect.Array;
import java.util.LinkedList;
+import java.util.List;
import org.apache.mavibot.btree.exception.EndOfFileExceededException;
import org.apache.mavibot.btree.exception.KeyNotFoundException;
@@ -180,12 +181,12 @@ import org.apache.mavibot.btree.exceptio
if ( nbElems == btree.getPageSize() )
{
// The page is full
- result = addAndSplit( revision, pivot, leftPage, rightPage, pos );
+ result = addAndSplit( splitResult.getCopiedPages(), revision, pivot, leftPage, rightPage, pos );
}
else
{
// The page can contain the new pivot, let's insert it
- result = insertChild( revision, pivot, leftPage, rightPage, pos );
+ result = insertChild( splitResult.getCopiedPages(), revision, pivot, leftPage, rightPage, pos );
}
return result;
@@ -230,6 +231,7 @@ import org.apache.mavibot.btree.exceptio
// Modify the result and return
removeResult.setModifiedPage( newPage );
+ removeResult.addCopiedPage( this );
return removeResult;
}
@@ -254,8 +256,10 @@ import org.apache.mavibot.btree.exceptio
// the new root. Deal with this case
if ( nbElems == 1 )
{
- removeResult = new RemoveResult<K, V>( mergedResult.getModifiedPage(),
+ removeResult = new RemoveResult<K, V>( mergedResult.getCopiedPages(), mergedResult.getModifiedPage(),
mergedResult.getRemovedElement() );
+
+ removeResult.addCopiedPage( this );
}
else
{
@@ -342,8 +346,11 @@ import org.apache.mavibot.btree.exceptio
}
// Create the result
- DeleteResult<K, V> result = new BorrowedFromRightResult<K, V>( newNode, newSibling,
- mergedResult.getRemovedElement() );
+ DeleteResult<K, V> result = new BorrowedFromRightResult<K, V>( mergedResult.getCopiedPages(), newNode,
+ newSibling, mergedResult.getRemovedElement() );
+
+ result.addCopiedPage( this );
+ result.addCopiedPage( sibling );
return result;
}
@@ -423,9 +430,13 @@ import org.apache.mavibot.btree.exceptio
}
// Create the result
- DeleteResult<K, V> result = new BorrowedFromLeftResult<K, V>( newNode, newSibling,
+ DeleteResult<K, V> result = new BorrowedFromLeftResult<K, V>( mergedResult.getCopiedPages(), newNode,
+ newSibling,
mergedResult.getRemovedElement() );
+ result.addCopiedPage( this );
+ result.addCopiedPage( sibling );
+
return result;
}
@@ -551,7 +562,11 @@ import org.apache.mavibot.btree.exceptio
}
// And create the result
- DeleteResult<K, V> result = new MergedWithSiblingResult<K, V>( newNode, removedElement );
+ DeleteResult<K, V> result = new MergedWithSiblingResult<K, V>( mergedResult.getCopiedPages(), newNode,
+ removedElement );
+
+ result.addCopiedPage( this );
+ result.addCopiedPage( sibling );
return result;
}
@@ -742,9 +757,11 @@ import org.apache.mavibot.btree.exceptio
}
// Modify the result and return
- RemoveResult<K, V> removeResult = new RemoveResult<K, V>( newPage,
+ RemoveResult<K, V> removeResult = new RemoveResult<K, V>( borrowedResult.getCopiedPages(), newPage,
borrowedResult.getRemovedElement() );
+ removeResult.addCopiedPage( this );
+
return removeResult;
}
@@ -803,7 +820,10 @@ import org.apache.mavibot.btree.exceptio
}
// Create the result
- RemoveResult<K, V> result = new RemoveResult<K, V>( newNode, mergedResult.getRemovedElement() );
+ RemoveResult<K, V> result = new RemoveResult<K, V>( mergedResult.getCopiedPages(), newNode,
+ mergedResult.getRemovedElement() );
+
+ result.addCopiedPage( this );
return result;
}
@@ -978,6 +998,8 @@ import org.apache.mavibot.btree.exceptio
// to avoid the creation of a new object
result.modifiedPage = newPage;
+ result.addCopiedPage( this );
+
return result;
}
@@ -1014,6 +1036,7 @@ import org.apache.mavibot.btree.exceptio
* Adds 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 copiedPages the list of copied pages
* @param revision The revision of the modified page
* @param key The key to insert
* @param leftPage The left child
@@ -1022,7 +1045,8 @@ import org.apache.mavibot.btree.exceptio
* @return The modified page with the <K,V> element added
* @throws IOException If we have an error while trying to access the page
*/
- private InsertResult<K, V> insertChild( long revision, K key, Page<K, V> leftPage, Page<K, V> rightPage, int pos )
+ private InsertResult<K, V> insertChild( List<Page<K, V>> copiedPages, long revision, K key, Page<K, V> leftPage,
+ Page<K, V> rightPage, int pos )
throws IOException
{
// First copy the current page, but add one element in the copied page
@@ -1051,7 +1075,8 @@ import org.apache.mavibot.btree.exceptio
}
// Create the result
- InsertResult<K, V> result = new ModifyResult<K, V>( newNode, null );
+ InsertResult<K, V> result = new ModifyResult<K, V>( copiedPages, newNode, null );
+ result.addCopiedPage( this );
return result;
}
@@ -1066,6 +1091,7 @@ import org.apache.mavibot.btree.exceptio
* 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 copiedPages the list of copied pages
* @param revision The new revision for all the created pages
* @param pivot The key that will be move up after the split
* @param leftPage The left child
@@ -1074,8 +1100,8 @@ import org.apache.mavibot.btree.exceptio
* @return An OverflowPage containing the pivot, and the new left and right pages
* @throws IOException If we have an error while trying to access the page
*/
- private InsertResult<K, V> addAndSplit( long revision, K pivot, Page<K, V> leftPage, Page<K, V> rightPage, int pos )
- throws IOException
+ private InsertResult<K, V> addAndSplit( List<Page<K, V>> copiedPages, long revision, K pivot, Page<K, V> leftPage,
+ Page<K, V> rightPage, int pos ) throws IOException
{
int middle = btree.getPageSize() >> 1;
@@ -1106,7 +1132,8 @@ import org.apache.mavibot.btree.exceptio
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 );
+ InsertResult<K, V> result = new SplitResult<K, V>( copiedPages, keys[middle - 1], newLeftPage, newRightPage );
+ result.addCopiedPage( this );
return result;
}
@@ -1125,7 +1152,8 @@ import org.apache.mavibot.btree.exceptio
newRightPage.children[0] = createHolder( rightPage );
// Create the result
- InsertResult<K, V> result = new SplitResult<K, V>( pivot, newLeftPage, newRightPage );
+ InsertResult<K, V> result = new SplitResult<K, V>( copiedPages, pivot, newLeftPage, newRightPage );
+ result.addCopiedPage( this );
return result;
}
@@ -1149,7 +1177,8 @@ import org.apache.mavibot.btree.exceptio
System.arraycopy( children, pos + 1, newRightPage.children, pos + 1 - middle, nbElems - pos );
// Create the result
- InsertResult<K, V> result = new SplitResult<K, V>( keys[middle], newLeftPage, newRightPage );
+ InsertResult<K, V> result = new SplitResult<K, V>( copiedPages, keys[middle], newLeftPage, newRightPage );
+ result.addCopiedPage( this );
return result;
}
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/NotPresentResult.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/NotPresentResult.java?rev=1476901&r1=1476900&r2=1476901&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/NotPresentResult.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/NotPresentResult.java Mon Apr 29 06:15:10 2013
@@ -28,7 +28,7 @@ package org.apache.mavibot.btree;
* @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
*/
-/* No qualifier */class NotPresentResult<K, V> implements DeleteResult<K, V>
+/* No qualifier */class NotPresentResult<K, V> extends AbstractResult<K, V> implements DeleteResult<K, V>
{
/** The unique instance for this class */
@SuppressWarnings("rawtypes")
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RemoveResult.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RemoveResult.java?rev=1476901&r1=1476900&r2=1476901&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RemoveResult.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RemoveResult.java Mon Apr 29 06:15:10 2013
@@ -20,6 +20,9 @@
package org.apache.mavibot.btree;
+import java.util.List;
+
+
/**
* The result of a delete operation, when the child has not been merged. It contains the
* reference to the modified page, and the removed element.
@@ -44,6 +47,19 @@ package org.apache.mavibot.btree;
/**
+ * A constructor for RemoveResult which takes a list of copied pages.
+ *
+ * @param copiedPages the list of copied pages
+ * @param modifiedPage The modified page
+ * @param removedElement The removed element (can be null if the key wasn't present in the tree)
+ */
+ /* No qualifier */RemoveResult( List<Page<K, V>> copiedPages, Page<K, V> modifiedPage, Tuple<K, V> removedElement )
+ {
+ super( copiedPages, modifiedPage, removedElement );
+ }
+
+
+ /**
* @see Object#toString()
*/
public String toString()
Added: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Result.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Result.java?rev=1476901&view=auto
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Result.java (added)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Result.java Mon Apr 29 06:15:10 2013
@@ -0,0 +1,47 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.mavibot.btree;
+
+
+import java.util.List;
+
+
+/**
+ * The result of an insert or delete operation.
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+/* No qualifier */interface Result<K, V>
+{
+ /**
+ * @return the copiedPage
+ */
+ /* No qualifier */List<Page<K, V>> getCopiedPages();
+
+
+ /**
+ * Add a new copied page
+ * @param copiedPage the added page
+ */
+ /* No qualifier */void addCopiedPage( Page<K, V> copiedPage );
+}
Modified: labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/SplitResult.java
URL: http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/SplitResult.java?rev=1476901&r1=1476900&r2=1476901&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/SplitResult.java (original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/SplitResult.java Mon Apr 29 06:15:10 2013
@@ -20,6 +20,9 @@
package org.apache.mavibot.btree;
+import java.util.List;
+
+
/**
* The result of an insert operation, when the page has been split. It contains
* the new pivotal value, plus the reference on the two new pages.
@@ -28,7 +31,7 @@ package org.apache.mavibot.btree;
* @param <V> The type for the stored value
* @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
*/
-/* No qualifier */class SplitResult<K, V> implements InsertResult<K, V>
+/* No qualifier */class SplitResult<K, V> extends AbstractResult<K, V> implements InsertResult<K, V>
{
/** The left child */
protected Page<K, V> leftPage;
@@ -48,6 +51,24 @@ package org.apache.mavibot.btree;
*/
/* No qualifier */SplitResult( K pivot, Page<K, V> leftPage, Page<K, V> rightPage )
{
+ super();
+ this.pivot = pivot;
+ this.leftPage = leftPage;
+ this.rightPage = rightPage;
+ }
+
+
+ /**
+ * A constructor for SplitResult with copied pages.
+ *
+ * @param copiedPages the list of copied pages
+ * @param pivot The new key to insert into the parent
+ * @param leftPage The new left page
+ * @param rightPage The new right page
+ */
+ /* No qualifier */SplitResult( List<Page<K, V>> copiedPages, K pivot, Page<K, V> leftPage, Page<K, V> rightPage )
+ {
+ super( copiedPages );
this.pivot = pivot;
this.leftPage = leftPage;
this.rightPage = rightPage;
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@labs.apache.org
For additional commands, e-mail: commits-help@labs.apache.org