Author: kayyagari
Date: Sun Mar 31 15:41:47 2013
New Revision: 1462992
URL: http://svn.apache.org/r1462992
Log:
o modified delete operation to handle multiple values
o renamed removeElement() to copyAfterRemovingElement()
o fixed the LeafTest as per the new signature of delete()
o added tests
Modified:
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/BTreeDuplicateKeyTest.java
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
Modified:
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java?rev=1462992&r1=1462991&r2=1462992&view=diff
==============================================================================
---
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
(original)
+++
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/BTree.java
Sun Mar 31 15:41:47 2013
@@ -811,11 +811,13 @@ public class BTree<K, V>
/**
- * Delete the value from an entry which key is given as a parameter. If
the value
- * is present, we will return it. If the remaining entry is empty, we will
remove it
- * from the tree.
+ * Delete the value from an entry associated with the given key. If the
value
+ * If the value is present, it will be deleted first, later if there are
no other
+ * values associated with this key(which can happen when duplicates are
enabled),
+ * we will remove the key from the tree.
*
* @param key The key for the entry we try to remove
+ * @param value The value to delete (can be null)
* @return A Tuple<K, V> containing the removed entry, or null if it's not
found.
*/
public Tuple<K, V> delete( K key, V value ) throws IOException
@@ -832,7 +834,7 @@ public class BTree<K, V>
long revision = generateRevision();
- Tuple<K, V> deleted = delete( key, revision );
+ Tuple<K, V> deleted = delete( key, value, revision );
// Decrease the number of element in the current tree if the delete is
successful
if ( deleted != null )
@@ -853,6 +855,23 @@ public class BTree<K, V>
*/
private Tuple<K, V> delete( K key, long revision ) throws IOException
{
+ return delete( key, null, revision );
+ }
+
+ /**
+ *
+ * Deletes the given <key,value> pair if both key and value match. If the
given value is null
+ * and there is no null value associated with the given key then the entry
with the given key
+ * will be removed.
+ *
+ * @param key The key to be removed
+ * @param value The value to be removed (can be null, and when no null
value exists the key will be removed irrespective of the value)
+ * @param revision The revision to be associated with this operation
+ * @return
+ * @throws IOException
+ */
+ private Tuple<K, V> delete( K key, V value, long revision ) throws
IOException
+ {
writeLock.lock();
try
@@ -863,7 +882,7 @@ public class BTree<K, V>
// Try to delete the entry starting from the root page. Here, the
root
// page may be either a Node or a Leaf
- DeleteResult<K, V> result = rootPage.delete( revision, key, null,
-1 );
+ DeleteResult<K, V> result = rootPage.delete( revision, key, value,
null, -1 );
if ( result instanceof NotPresentResult )
{
Modified:
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java?rev=1462992&r1=1462991&r2=1462992&view=diff
==============================================================================
---
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java
(original)
+++
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java
Sun Mar 31 15:41:47 2013
@@ -123,7 +123,7 @@ public class Leaf<K, V> extends Abstract
* {@inheritDoc}
*/
@SuppressWarnings("unchecked")
- public DeleteResult<K, V> delete( long revision, K key, Page<K, V> parent,
int parentPos )
+ public DeleteResult<K, V> delete( long revision, K key, V value, Page<K,
V> parent, int parentPos )
throws IOException
{
// Check that the leaf is not empty
@@ -142,17 +142,83 @@ public class Leaf<K, V> extends Abstract
return NotPresentResult.NOT_PRESENT;
}
+ // Get the removed element
+ Tuple<K, V> removedElement = null;
+
+ // flag to detect if a key was completely removed
+ boolean keyRemoved = false;
+
int index = -( pos + 1 );
+
+ if( btree.isAllowDuplicates() )
+ {
+ if( value == null );
+ BTree<V,V> dups = ( BTree<V,V> ) values[index].getValue( btree );
+
+ if( dups.hasKey( value ) )
+ {
+ dups.delete( value );
+
+ if( dups.getNbElems() == 0 )
+ {
+ keyRemoved = true;
+ }
+
+ removedElement = new Tuple<K, V>( keys[index], value ); // we
deleted only one value (even if it is from a tree of size 1)
+ }
+ else if( value == null ) // this is a case to delete entire
<K,dupsTree>
+ {
+ removedElement = new Tuple<K, V>( keys[index], ( V ) dups );
// the entire tree was removed so pass it as the value
+ keyRemoved = true;
+ }
+ else // value is not found
+ {
+ return NotPresentResult.NOT_PRESENT;
+ }
+ }
+ else
+ {
+ V existing = values[index].getValue( btree );
+
+ if( ( ( existing == null ) && ( value == null ) ) || ( value ==
null ) )
+ {
+ removedElement = new Tuple<K, V>( keys[index], existing );
+ keyRemoved = true;
+ }
+ else if( btree.getValueSerializer().compare( value, existing ) ==
0 )
+ {
+ removedElement = new Tuple<K, V>( keys[index], value );
+ keyRemoved = true;
+ }
+ else
+ {
+ return NotPresentResult.NOT_PRESENT;
+ }
+ }
+
+ Leaf<K, V> newLeaf = null;
+
+ if( keyRemoved )
+ {
+ newLeaf = new Leaf<K, V>( btree, revision, nbElems - 1 );
+ }
+ else
+ {
+ newLeaf = new Leaf<K, V>( btree, revision, nbElems );
+ }
+
+ // Create the result
+ DeleteResult<K, V> defaultResult = new RemoveResult<K, V>( newLeaf,
removedElement );
// If the parent is null, then this page is the root page.
if ( parent == null )
{
// Just remove the entry if it's present
- DeleteResult<K, V> result = removeElement( revision, index );
+ copyAfterRemovingElement( keyRemoved, newLeaf, index );
- return result;
+ return defaultResult;
}
- else
+ else if( keyRemoved )
{
// The current page is not the root. Check if the leaf has more
than N/2
// elements
@@ -170,7 +236,7 @@ public class Leaf<K, V> extends Abstract
if ( sibling.getNbElems() == halfSize )
{
// We will merge the current page with its sibling
- DeleteResult<K, V> result = mergeWithSibling( revision,
sibling, ( siblingPos < parentPos ), index );
+ DeleteResult<K, V> result = mergeWithSibling(
removedElement, revision, sibling, ( siblingPos < parentPos ), index );
return result;
}
@@ -179,14 +245,14 @@ public class Leaf<K, V> extends Abstract
// We can borrow the element from the left sibling
if ( siblingPos < parentPos )
{
- DeleteResult<K, V> result = borrowFromLeft( revision,
sibling, index );
+ DeleteResult<K, V> result = borrowFromLeft(
removedElement, revision, sibling, index );
return result;
}
else
{
// Borrow from the right sibling
- DeleteResult<K, V> result = borrowFromRight( revision,
sibling, index );
+ DeleteResult<K, V> result = borrowFromRight(
removedElement, revision, sibling, index );
return result;
}
@@ -198,11 +264,13 @@ public class Leaf<K, V> extends Abstract
// We simply remove the element from the page, and if it was
the leftmost,
// we return the new pivot (it will replace any instance of
the removed
// key in its parents)
- DeleteResult<K, V> result = removeElement( revision, index );
+ copyAfterRemovingElement( keyRemoved, newLeaf, index );
- return result;
+ return defaultResult;
}
}
+
+ return defaultResult;
}
@@ -216,13 +284,12 @@ public class Leaf<K, V> extends Abstract
* @return The new created leaf containing the sibling and the old page.
* @throws IOException If we have an error while trying to access the page
*/
- private DeleteResult<K, V> mergeWithSibling( long revision, Leaf<K, V>
sibling, boolean isLeft, int pos )
+ private DeleteResult<K, V> mergeWithSibling( Tuple<K, V> removedElement,
long revision, Leaf<K, V> sibling, boolean isLeft, int pos )
throws EndOfFileExceededException, IOException
{
// Create the new page. It will contain N - 1 elements (the maximum
number)
// as we merge two pages that contain N/2 elements minus the one we
remove
Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision,
btree.getPageSize() - 1 );
- Tuple<K, V> removedElement = new Tuple<K, V>( keys[pos],
values[pos].getValue( btree ) );
if ( isLeft )
{
@@ -274,7 +341,7 @@ public class Leaf<K, V> extends Abstract
* @return The resulting pages
* @throws IOException If we have an error while trying to access the page
*/
- private DeleteResult<K, V> borrowFromLeft( long revision, Leaf<K, V>
sibling, int pos )
+ private DeleteResult<K, V> borrowFromLeft( Tuple<K, V> removedElement,
long revision, Leaf<K, V> sibling, int pos )
throws IOException
{
// The sibling is on the left, borrow the rightmost element
@@ -300,9 +367,6 @@ public class Leaf<K, V> extends Abstract
System.arraycopy( keys, pos + 1, newLeaf.keys, pos + 1, keys.length -
pos - 1 );
System.arraycopy( values, pos + 1, newLeaf.values, pos + 1,
values.length - pos - 1 );
- // Create the result
- Tuple<K, V> removedElement = new Tuple<K, V>( keys[pos],
values[pos].getValue( btree ) );
-
DeleteResult<K, V> result = new BorrowedFromLeftResult<K, V>( newLeaf,
newSibling, removedElement );
return result;
@@ -320,7 +384,7 @@ public class Leaf<K, V> extends Abstract
* @return The resulting pages
* @throws IOException If we have an error while trying to access the page
*/
- private DeleteResult<K, V> borrowFromRight( long revision, Leaf<K, V>
sibling, int pos )
+ private DeleteResult<K, V> borrowFromRight( Tuple<K, V> removedElement,
long revision, Leaf<K, V> sibling, int pos )
throws IOException
{
// The sibling is on the left, borrow the rightmost element
@@ -350,9 +414,6 @@ public class Leaf<K, V> extends Abstract
System.arraycopy( keys, pos + 1, newLeaf.keys, pos, keys.length - pos
- 1 );
System.arraycopy( values, pos + 1, newLeaf.values, pos, values.length
- pos - 1 );
- // Create the result
- Tuple<K, V> removedElement = new Tuple<K, V>( keys[pos],
values[pos].getValue( btree ) );
-
DeleteResult<K, V> result = new BorrowedFromRightResult<K, V>(
newLeaf, newSibling, removedElement );
return result;
@@ -360,38 +421,37 @@ public class Leaf<K, V> extends Abstract
/**
- * Removes the element at a given position.
- *
- * @param revision The revision of the modified page
+ * Copies the elements of the current page to a new page
+ *
+ * @param keyRemoved a flag stating if the key was removed
+ * @param newLeaf The new page into which the remaining keys and values
will be copied
* @param pos The position into the page of the element to remove
- * @return The modified page with the <K,V> element added
* @throws IOException If we have an error while trying to access the page
*/
- private DeleteResult<K, V> removeElement( long revision, int pos ) throws
IOException
+ private void copyAfterRemovingElement( boolean keyRemoved, Leaf<K, V>
newLeaf, int pos ) throws IOException
{
- // First copy the current page, but remove one element in the copied
page
- Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems - 1 );
-
- // Get the removed element
- Tuple<K, V> removedElement = new Tuple<K, V>( keys[pos],
values[pos].getValue( btree ) );
-
- // Deal with the special case of an page with only one element by
skipping
- // the copy, as we won't have any remaining element in the page
- if ( nbElems > 1 )
+ if( keyRemoved )
{
+ // Deal with the special case of a page with only one element by
skipping
+ // the copy, as we won't have any remaining element in the page
+ if( nbElems == 1 )
+ {
+ return;
+ }
+
// 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 );
-
+
// And copy the elements after the position
System.arraycopy( keys, pos + 1, newLeaf.keys, pos, keys.length -
pos - 1 );
System.arraycopy( values, pos + 1, newLeaf.values, pos,
values.length - pos - 1 );
}
-
- // Create the result
- DeleteResult<K, V> result = new RemoveResult<K, V>( newLeaf,
removedElement );
-
- return result;
+ else // one of the many values of the same key was removed, no change
in the number of keys
+ {
+ System.arraycopy( keys, 0, newLeaf.keys, 0, nbElems );
+ System.arraycopy( values, 0, newLeaf.values, 0, nbElems );
+ }
}
Modified:
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Node.java?rev=1462992&r1=1462991&r2=1462992&view=diff
==============================================================================
---
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
(original)
+++
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
Sun Mar 31 15:41:47 2013
@@ -560,7 +560,7 @@ public class Node<K, V> extends Abstract
/**
* {@inheritDoc}
*/
- public DeleteResult<K, V> delete( long revision, K key, Page<K, V> parent,
int parentPos ) throws IOException
+ public DeleteResult<K, V> delete( long revision, K key, V value, Page<K,
V> parent, int parentPos ) throws IOException
{
// We first try to delete the element from the child it belongs to
// Find the key in the page
@@ -574,12 +574,12 @@ public class Node<K, V> extends Abstract
{
index = -( pos + 1 );
child = children[-pos].getValue( btree );
- deleteResult = child.delete( revision, key, this, -pos );
+ deleteResult = child.delete( revision, key, value, this, -pos );
}
else
{
child = children[pos].getValue( btree );
- deleteResult = child.delete( revision, key, this, pos );
+ deleteResult = child.delete( revision, key, value, this, pos );
}
// If the key is not present in the tree, we simply return
Modified:
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Page.java?rev=1462992&r1=1462991&r2=1462992&view=diff
==============================================================================
---
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
(original)
+++
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
Sun Mar 31 15:41:47 2013
@@ -66,18 +66,20 @@ public interface Page<K, V>
/**
- * Deletes an entry with the given key from this page. We first find the
place were to
- * remove the <K,V> into the tree, by recursively browsing the pages :<br/>
- * <p>
+ * Deletes the value from an entry associated with the given key in this
page. We first find
+ * the place were to remove the <K,V> into the tree, by recursively
browsing the pages.
+ * If the value is present, it will be deleted first, later if there are
no other values associated with
+ * this key(which can happen when duplicates are enabled), we will remove
the key from the tree.
*
* @param revision The new revision for the modified pages
* @param key The key to delete
+ * @param value The value to delete (can be null)
* @param parent The parent page
* @param parentPos The position of the current page in it's parent
* @return Either a modified Page if the key has been removed from the
page, or a NotPresentResult.
* @throws IOException If we have an error while trying to access the page
*/
- DeleteResult<K, V> delete( long revision, K key, Page<K, V> parent, int
parentPos ) throws IOException;
+ DeleteResult<K, V> delete( long revision, K key, V value, Page<K, V>
parent, int parentPos ) throws IOException;
/**
Modified:
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/BTreeDuplicateKeyTest.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/BTreeDuplicateKeyTest.java?rev=1462992&r1=1462991&r2=1462992&view=diff
==============================================================================
---
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/BTreeDuplicateKeyTest.java
(original)
+++
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/BTreeDuplicateKeyTest.java
Sun Mar 31 15:41:47 2013
@@ -197,4 +197,36 @@ public class BTreeDuplicateKeyTest
assertFalse( btree.contains( 0, null ) );
assertFalse( btree.contains( null, null ) );
}
+
+ @Test
+ public void testRemoveDuplicateKey() throws Exception
+ {
+ IntSerializer serializer = new IntSerializer();
+
+ BTreeConfiguration<Integer, Integer> config = new
BTreeConfiguration<Integer, Integer>();
+ config.setAllowDuplicates( true );
+ config.setName( "master" );
+ config.setSerializers( serializer, serializer );
+ BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
+
+ btree.insert( 1, 1 );
+ btree.insert( 1, 2 );
+
+ assertEquals( 2l, btree.getNbElems() );
+
+ Tuple<Integer,Integer> t = btree.delete( 1, 1 );
+ assertEquals( Integer.valueOf( 1 ), t.getKey() );
+ assertEquals( Integer.valueOf( 1 ), t.getValue() );
+
+ assertEquals( 1l, btree.getNbElems() );
+
+ t = btree.delete( 1, 2 );
+ assertEquals( Integer.valueOf( 1 ), t.getKey() );
+ assertEquals( Integer.valueOf( 2 ), t.getValue() );
+
+ assertEquals( 0l, btree.getNbElems() );
+
+ t = btree.delete( 1, 2 );
+ assertNull( t );
+ }
}
Modified:
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java?rev=1462992&r1=1462991&r2=1462992&view=diff
==============================================================================
---
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
(original)
+++
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
Sun Mar 31 15:41:47 2013
@@ -83,7 +83,7 @@ public class LeafTest
{
Leaf<Long, String> leaf = new Leaf<Long, String>( btree );
- DeleteResult<Long, String> result = leaf.delete( 1L, 1L, null, -1 );
+ DeleteResult<Long, String> result = leaf.delete( 1L, 1L, null, null,
-1 );
assertEquals( NotPresentResult.NOT_PRESENT, result );
}
@@ -102,7 +102,7 @@ public class LeafTest
leaf = insert( leaf, 3L, "v3" );
leaf = insert( leaf, 4L, "v4" );
- DeleteResult<Long, String> result = leaf.delete( 2L, 5L, null, -1 );
+ DeleteResult<Long, String> result = leaf.delete( 2L, 5L, null, null,
-1 );
assertEquals( NotPresentResult.NOT_PRESENT, result );
}
@@ -121,7 +121,7 @@ public class LeafTest
leaf = insert( leaf, 3L, "v3" );
leaf = insert( leaf, 4L, "v4" );
- DeleteResult<Long, String> result = leaf.delete( 4L, 3L, null, -1 );
+ DeleteResult<Long, String> result = leaf.delete( 4L, 3L, null, null,
-1 );
assertTrue( result instanceof RemoveResult );
@@ -168,7 +168,7 @@ public class LeafTest
leaf = insert( leaf, 3L, "v3" );
leaf = insert( leaf, 4L, "v4" );
- DeleteResult<Long, String> result = leaf.delete( 4L, 1L, null, -1 );
+ DeleteResult<Long, String> result = leaf.delete( 4L, 1L, null, null,
-1 );
assertTrue( result instanceof RemoveResult );
@@ -248,7 +248,7 @@ public class LeafTest
parent.keys[1] = 10L;
// Now, delete the element from the target page
- DeleteResult<Long, String> result = target.delete( 2L, 7L, parent, 1 );
+ DeleteResult<Long, String> result = target.delete( 2L, 7L, null,
parent, 1 );
assertTrue( result instanceof BorrowedFromLeftResult );
@@ -321,7 +321,7 @@ public class LeafTest
parent.keys[1] = 10L;
// Now, delete the element from the target page
- DeleteResult<Long, String> result = target.delete( 2L, 7L, parent, 1 );
+ DeleteResult<Long, String> result = target.delete( 2L, 7L, null,
parent, 1 );
assertTrue( result instanceof BorrowedFromRightResult );
@@ -394,7 +394,7 @@ public class LeafTest
parent.keys[1] = 9L;
// Now, delete the element from the target page
- DeleteResult<Long, String> result = target.delete( 2L, 7L, parent, 1 );
+ DeleteResult<Long, String> result = target.delete( 2L, 7L, null,
parent, 1 );
assertTrue( result instanceof MergedWithSiblingResult );
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
