Author: kayyagari
Date: Sat Mar 30 19:09:57 2013
New Revision: 1462845
URL: http://svn.apache.org/r1462845
Log:
o added hasKey(key) and contains(key, value) methods
o moved findPos() to Page interface
o merged the javadoc changes from previous revision
Modified:
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java
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
Modified:
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java?rev=1462845&r1=1462844&r2=1462845&view=diff
==============================================================================
---
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java
(original)
+++
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/AbstractPage.java
Sat Mar 30 19:09:57 2013
@@ -135,42 +135,9 @@ public abstract class AbstractPage<K, V>
/**
- * Find the position of the given key in the page. If we have found the
key,
- * we will return its position as a negative value.
- * <p/>
- * Assuming that the array is zero-indexed, the returned value will be :
<br/>
- * position = - ( position + 1)
- * <br/>
- * So for the following table of keys : <br/>
- * <pre>
- * +---+---+---+---+
- * | b | d | f | h |
- * +---+---+---+---+
- * 0 1 2 3
- * </pre>
- * looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return
-3 (-(2+1)).<br/>
- * Computing the real position is just a matter to get -(position++).
- * <p/>
- * If we don't find the key in the table, we will return the position of
the key
- * immediately above the key we are looking for. <br/>
- * For instance, looking for :
- * <ul>
- * <li>'a' will return 0</li>
- * <li>'b' will return -1</li>
- * <li>'c' will return 1</li>
- * <li>'d' will return -2</li>
- * <li>'e' will return 2</li>
- * <li>'f' will return -3</li>
- * <li>'g' will return 3</li>
- * <li>'h' will return -4</li>
- * <li>'i' will return 4</li>
- * </ul>
- *
- *
- * @param key The key to find
- * @return The position in the page.
+ * {@inheritDoc}
*/
- protected int findPos( K key )
+ public int findPos( K key )
{
// Deal with the special key where we have an empty page
if ( nbElems == 0 )
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=1462845&r1=1462844&r2=1462845&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
Sat Mar 30 19:09:57 2013
@@ -930,6 +930,31 @@ public class BTree<K, V>
/**
+ * Checks if the given key exists.
+ *
+ * @param key The key we are looking at
+ * @return true if the key is present, false otherwise
+ */
+ public boolean hasKey( K key ) throws IOException
+ {
+ return rootPage.findPos( key ) < 0;
+ }
+
+
+ /**
+ * Checks if the BTree contains the given key with the given value.
+ *
+ * @param key The key we are looking for
+ * @param value The value associated with the given key
+ * @return true if the key and value are associated with each other, false
otherwise
+ */
+ public boolean contains( K key, V value ) throws IOException
+ {
+ return rootPage.contains( key, value );
+ }
+
+
+ /**
* Creates a cursor starting on the given key
*
* @param key The key which is the starting point. If the key is not found,
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=1462845&r1=1462844&r2=1462845&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
Sat Mar 30 19:09:57 2013
@@ -58,7 +58,7 @@ public class Leaf<K, V> extends Abstract
*
* @param btree The BTree this page belongs to.
* @param revision The page revision
- * @param nbElems The number of elements this page will contain
+ * @param nbElems The number of elements this page will contain
*/
@SuppressWarnings("unchecked")
// Cannot create an array of generic objects
@@ -66,10 +66,9 @@ public class Leaf<K, V> extends Abstract
{
super( btree, revision, nbElems );
- if ( btree.isAllowDuplicates() )
+ if( btree.isAllowDuplicates() )
{
- this.values = ( DuplicateKeyMemoryHolder<K, V>[] )
Array.newInstance( DuplicateKeyMemoryHolder.class,
- nbElems );
+ this.values = ( DuplicateKeyMemoryHolder<K, V>[] )
Array.newInstance( DuplicateKeyMemoryHolder.class, nbElems );
}
else
{
@@ -273,7 +272,7 @@ public class Leaf<K, V> extends Abstract
* @param sibling The left sibling
* @param pos The position of the element to remove
* @return The resulting pages
- * @throws IOException If we have an error while trying to access the page
+ * @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 )
throws IOException
@@ -319,7 +318,7 @@ public class Leaf<K, V> extends Abstract
* @param sibling The right sibling
* @param pos The position of the element to remove
* @return The resulting pages
- * @throws IOException If we have an error while trying to access the page
+ * @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 )
throws IOException
@@ -423,7 +422,16 @@ public class Leaf<K, V> extends Abstract
if ( pos < 0 )
{
- return values[-( pos + 1 )].getValue( btree );
+ V v = values[-( pos + 1 )].getValue( btree );
+
+ if( btree.isAllowDuplicates() )
+ {
+ // always return the first value for get(key) when duplicates
are allowed
+ BTree<V,V> dupTree = ( ( BTree<V,V> ) v );
+ return dupTree.rootPage.getLeftMostKey();
+ }
+
+ return v;
}
else
{
@@ -432,6 +440,33 @@ public class Leaf<K, V> extends Abstract
}
+ @Override
+ public boolean contains( K key, V value ) throws IOException
+ {
+ int pos = findPos( key );
+
+ if ( pos < 0 )
+ {
+ V v = values[-( pos + 1 )].getValue( btree );
+
+ if( btree.isAllowDuplicates() )
+ {
+ // always return the first value for get(key) when duplicates
are allowed
+ BTree<V,V> dupTree = ( ( BTree<V,V> ) v );
+ return dupTree.hasKey( value );
+ }
+ else
+ {
+ return ( btree.getValueSerializer().compare( value, v ) == 0 );
+ }
+ }
+ else
+ {
+ return false;
+ }
+ }
+
+
/**
* {@inheritDoc}
*/
@@ -449,8 +484,7 @@ public class Leaf<K, V> extends Abstract
/**
- * Sets the value at a give position.
- *
+ * Sets the value at a give position
* @param pos The position in the values array
* @param value the value to inject
*/
@@ -476,7 +510,7 @@ public class Leaf<K, V> extends Abstract
ParentPos<K, V> parentPos = new ParentPos<K, V>( this, index );
setDupsContainer( parentPos );
stack.push( parentPos );
-
+
cursor = new Cursor<K, V>( btree, transaction, stack );
}
else
@@ -522,9 +556,9 @@ public class Leaf<K, V> extends Abstract
{
// Start at the beginning of the page
ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
-
+
setDupsContainer( parentPos );
-
+
stack.push( parentPos );
cursor = new Cursor<K, V>( btree, transaction, stack );
@@ -575,12 +609,19 @@ public class Leaf<K, V> extends Abstract
}
V oldValue = null;
-
- if ( btree.isAllowDuplicates() )
+
+ if( btree.isAllowDuplicates() )
{
- BTree<V, V> dupValues = ( BTree<V, V> )
newLeaf.values[pos].getValue( btree );
- // 'oldValue' will always be null here
- oldValue = dupValues.insert( value, null, 0 );
+ BTree<V, V> dupValues = ( BTree<V, V> )
newLeaf.values[pos].getValue( btree );
+ // return value will always be null here
+ if( !dupValues.hasKey( value ) )
+ {
+ dupValues.insert( value, null, 0 );
+ }
+ else
+ {
+ oldValue = value;
+ }
}
else
{
@@ -588,10 +629,10 @@ public class Leaf<K, V> extends Abstract
oldValue = newLeaf.values[pos].getValue( btree );
newLeaf.values[pos] = btree.createHolder( value );
}
-
+
// Create the result
InsertResult<K, V> result = new ModifyResult<K, V>( newLeaf, oldValue
);
-
+
return result;
}
@@ -612,10 +653,10 @@ public class Leaf<K, V> extends Abstract
Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems + 1 );
// Atm, store the value in memory
-
+
ElementHolder valueHolder = null;
-
- if ( btree.isAllowDuplicates() )
+
+ if( btree.isAllowDuplicates() )
{
valueHolder = new DuplicateKeyMemoryHolder<K, V>( btree, value );
}
@@ -623,7 +664,7 @@ public class Leaf<K, V> extends Abstract
{
valueHolder = new MemoryHolder<K, V>( btree, value );
}
-
+
//ValueHolder<K, V> valueHolder = btree.createHolder( value );
// Deal with the special case of an empty page
@@ -760,17 +801,17 @@ public class Leaf<K, V> extends Abstract
public Tuple<K, V> findLeftMost() throws IOException
{
V val = null;
-
- if ( btree.isAllowDuplicates() )
+
+ if( btree.isAllowDuplicates() )
{
- BTree<V, V> dupTree = ( BTree<V, V> ) values[0].getValue( btree );
+ BTree<V,V> dupTree = ( BTree<V,V> ) values[0].getValue( btree );
val = dupTree.rootPage.getLeftMostKey();
}
else
{
val = values[0].getValue( btree );
}
-
+
return new Tuple<K, V>( keys[0], val );
}
@@ -781,17 +822,17 @@ public class Leaf<K, V> extends Abstract
public Tuple<K, V> findRightMost() throws EndOfFileExceededException,
IOException
{
V val = null;
-
- if ( btree.isAllowDuplicates() )
+
+ if( btree.isAllowDuplicates() )
{
- BTree<V, V> dupTree = ( BTree<V, V> ) values[nbElems -
1].getValue( btree );
+ BTree<V,V> dupTree = ( BTree<V,V> ) values[nbElems - 1].getValue(
btree );
val = dupTree.rootPage.getRightMostKey();
}
else
{
val = values[nbElems - 1].getValue( btree );
}
-
+
return new Tuple<K, V>( keys[nbElems - 1], val );
}
@@ -835,26 +876,26 @@ public class Leaf<K, V> extends Abstract
/**
* Creates a sub-tree if the BTree accept multiple values for a key.
- *
+ *
* @param parentPos The position we will add the sub-tree at
*/
- private void setDupsContainer( ParentPos<K, V> parentPos )
+ private void setDupsContainer( ParentPos<K,V> parentPos )
{
- if ( btree.isAllowDuplicates() )
+ if( btree.isAllowDuplicates() )
{
try
{
BTree<V, V> dupsContainer = ( BTree<V, V> )
values[parentPos.pos].getValue( btree );
parentPos.dupsContainer = dupsContainer;
}
- catch ( IOException e )
+ catch( IOException e )
{
throw new RuntimeException( e );
}
}
}
-
+
/**
* {@inheritDoc}
*/
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=1462845&r1=1462844&r2=1462845&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
Sat Mar 30 19:09:57 2013
@@ -849,6 +849,27 @@ public class Node<K, V> extends Abstract
/**
+ * {@inheritDoc}
+ */
+ @Override
+ public boolean contains( K key, V value ) throws IOException
+ {
+ int pos = findPos( key );
+
+ if ( pos < 0 )
+ {
+ // 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].getValue( btree ).contains( key, value );
+ }
+ else
+ {
+ return children[pos].getValue( btree ).contains( key, value );
+ }
+ }
+
+
+ /**
* Set the value at a give position
*
* @param pos The position in the values array
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=1462845&r1=1462844&r2=1462845&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
Sat Mar 30 19:09:57 2013
@@ -105,8 +105,18 @@ public interface Page<K, V>
/**
+ * Checks if the page contains the given key with the given value.
+ *
+ * @param key The key we are looking for
+ * @param value The value associated with the given key
+ * @return true if the key and value are associated with each other, false
otherwise
+ */
+ boolean contains( K key, V value ) throws IOException;
+
+
+ /**
* Browses the tree, looking for the given key, and creates a Cursor on top
- * of the found results.
+ * of the found result.
*
* @param key The key we are looking for.
* @param transaction The started transaction for this operation
@@ -164,7 +174,7 @@ public interface Page<K, V>
*/
K getRightMostKey() throws IOException;
-
+
/**
* Finds the leftmost element in this page. If the page is a node, it will
go
* down in the leftmost children to recursively find the leftmost element.
@@ -182,14 +192,52 @@ public interface Page<K, V>
* @return The rightmost element in the tree
* @throws IOException If we have an error while trying to access the page
*/
- Tuple<K, V> findRightMost() throws IOException;
+ Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException;
/**
* Pretty-prints the tree with tabs
- *
* @param tabs The tabs to add in front of each node
* @return A pretty-print dump of the tree
*/
String dumpPage( String tabs );
+
+
+ /**
+ * Find the position of the given key in the page. If we have found the
key,
+ * we will return its position as a negative value.
+ * <p/>
+ * Assuming that the array is zero-indexed, the returned value will be :
<br/>
+ * position = - ( position + 1)
+ * <br/>
+ * So for the following table of keys : <br/>
+ * <pre>
+ * +---+---+---+---+
+ * | b | d | f | h |
+ * +---+---+---+---+
+ * 0 1 2 3
+ * </pre>
+ * looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return
-3 (-(2+1)).<br/>
+ * Computing the real position is just a matter to get -(position++).
+ * <p/>
+ * If we don't find the key in the table, we will return the position of
the key
+ * immediately above the key we are looking for. <br/>
+ * For instance, looking for :
+ * <ul>
+ * <li>'a' will return 0</li>
+ * <li>'b' will return -1</li>
+ * <li>'c' will return 1</li>
+ * <li>'d' will return -2</li>
+ * <li>'e' will return 2</li>
+ * <li>'f' will return -3</li>
+ * <li>'g' will return 3</li>
+ * <li>'h' will return -4</li>
+ * <li>'i' will return 4</li>
+ * </ul>
+ *
+ *
+ * @param key The key to find
+ * @return The position in the page.
+ */
+ int findPos( K key );
}
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=1462845&r1=1462844&r2=1462845&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
Sat Mar 30 19:09:57 2013
@@ -71,30 +71,31 @@ public class BTreeDuplicateKeyTest
Cursor<Integer, Integer> cursor = btree.browse();
assertFalse( cursor.hasNext() );
assertFalse( cursor.hasPrev() );
-
+
try
{
cursor.next();
- fail("Should not reach here");
+ fail( "Should not reach here" );
}
- catch(NoSuchElementException e)
+ catch ( NoSuchElementException e )
{
- assertTrue(true);
+ assertTrue( true );
}
try
{
cursor.prev();
- fail("Should not reach here");
+ fail( "Should not reach here" );
}
- catch(NoSuchElementException e)
+ catch ( NoSuchElementException e )
{
- assertTrue(true);
+ assertTrue( true );
}
-
+
cursor.close();
}
+
@Test
public void testDuplicateKey() throws IOException
{
@@ -163,4 +164,37 @@ public class BTreeDuplicateKeyTest
cursor.close();
}
+
+ @Test
+ public void testGetDuplicateKey() 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 );
+
+ Integer retVal = btree.insert( 1, 1 );
+ assertNull( retVal );
+
+ retVal = btree.insert( 1, 2 );
+ assertNull( retVal );
+
+ // check the return value when an existing value is added again
+ retVal = btree.insert( 1, 2 );
+ assertEquals( Integer.valueOf( 2 ), retVal );
+
+ assertEquals( Integer.valueOf( 1 ), btree.get( 1 ) );
+ assertTrue( btree.contains( 1, 1 ) );
+ assertTrue( btree.contains( 1, 2 ) );
+
+ assertFalse( btree.contains( 1, 0 ) );
+ assertFalse( btree.contains( 0, 1 ) );
+ assertFalse( btree.contains( 0, 0 ) );
+ assertFalse( btree.contains( null, 0 ) );
+ assertFalse( btree.contains( 0, null ) );
+ assertFalse( btree.contains( null, null ) );
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
