Author: kayyagari
Date: Sat Mar 30 15:55:17 2013
New Revision: 1462787
URL: http://svn.apache.org/r1462787
Log:
o added a new method getRightMostKey()
o added support for duplicate keys
o fixed the way hasNext() and hasPrev() work
o updated the cursor implementation to support duplicate keys
Added:
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/DuplicateKeyMemoryHolder.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/BTree.java
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/BTreeConfiguration.java
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.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/main/java/org/apache/mavibot/btree/ParentPos.java
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.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=1462787&r1=1462786&r2=1462787&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 15:55:17 2013
@@ -60,7 +60,7 @@ public class BTree<K, V>
/** Default page size (number of entries per node) */
public static final int DEFAULT_PAGE_SIZE = 16;
- /** Default size of the buffer used to write data n disk. Around 1Mb */
+ /** Default size of the buffer used to write data on disk. Around 1Mb */
public static final int DEFAULT_WRITE_BUFFER_SIZE = 4096 * 250;
/** The default journal name */
@@ -126,7 +126,9 @@ public class BTree<K, V>
/** The queue containing all the modifications applied on the bTree */
private BlockingQueue<Modification<K, V>> modificationsQueue;
-
+ /** Flag to enable duplicate key support */
+ private boolean allowDuplicates;
+
/**
* Create a thread that is responsible of cleaning the transactions when
* they hit the timeout
@@ -355,6 +357,7 @@ public class BTree<K, V>
comparator = keySerializer.getComparator();
readTimeOut = configuration.getReadTimeOut();
writeBufferSize = configuration.getWriteBufferSize();
+ allowDuplicates = configuration.isAllowDuplicates();
if ( comparator == null )
{
@@ -762,13 +765,6 @@ public class BTree<K, V>
existingValue = insert( key, value, revision );
- // Increase the number of element in the current tree if the
insertion is successful
- // and does not replace an element
- if ( existingValue == null )
- {
- btreeHeader.incrementNbElems();
- }
-
// If the BTree is managed, we have to update the rootPage on disk
if ( isManaged() )
{
@@ -946,8 +942,7 @@ public class BTree<K, V>
Transaction<K, V> transaction = beginReadTransaction();
// Fetch the root page for this revision
- Page<K, V> root = rootPage;
- Cursor<K, V> cursor = root.browse( key, transaction, new
LinkedList<ParentPos<K, V>>() );
+ Cursor<K, V> cursor = rootPage.browse( key, transaction, new
LinkedList<ParentPos<K, V>>() );
return cursor;
}
@@ -964,10 +959,9 @@ public class BTree<K, V>
Transaction<K, V> transaction = beginReadTransaction();
// Fetch the root page for this revision
- Page<K, V> root = rootPage;
LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
- Cursor<K, V> cursor = root.browse( transaction, stack );
+ Cursor<K, V> cursor = rootPage.browse( transaction, stack );
return cursor;
}
@@ -986,7 +980,7 @@ public class BTree<K, V>
* @param revision The revision to use
* @return Existing value, if any.
*/
- private V insert( K key, V value, long revision ) throws IOException
+ protected V insert( K key, V value, long revision ) throws IOException
{
if ( key == null )
{
@@ -1086,6 +1080,13 @@ public class BTree<K, V>
modificationsQueue.add( new Addition<K, V>( key, value ) );
}
+ // Increase the number of element in the current tree if the insertion
is successful
+ // and does not replace an element
+ if ( modifiedValue == null )
+ {
+ btreeHeader.incrementNbElems();
+ }
+
// Return the value we have found if it was modified
return modifiedValue;
}
@@ -1536,7 +1537,14 @@ public class BTree<K, V>
}
else
{
- return new MemoryHolder( this, value );
+ if( isAllowDuplicates() )
+ {
+ return new DuplicateKeyMemoryHolder<K, V>( this, ( V ) value );
+ }
+ else
+ {
+ return new MemoryHolder( this, value );
+ }
}
}
@@ -1613,6 +1621,12 @@ public class BTree<K, V>
}
+ public boolean isAllowDuplicates()
+ {
+ return allowDuplicates;
+ }
+
+
/**
* @see Object#toString()
*/
@@ -1659,6 +1673,8 @@ public class BTree<K, V>
sb.append( comparator.getClass().getSimpleName() );
}
+ sb.append( ", DuplicatesAllowed: " ).append( allowDuplicates );
+
if ( type == BTreeTypeEnum.PERSISTENT )
{
try
Modified:
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/BTreeConfiguration.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/BTreeConfiguration.java?rev=1462787&r1=1462786&r2=1462787&view=diff
==============================================================================
---
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/BTreeConfiguration.java
(original)
+++
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/BTreeConfiguration.java
Sat Mar 30 15:55:17 2013
@@ -91,6 +91,8 @@ public class BTreeConfiguration<K, V>
*/
private long checkPointDelay = 60 * 1000L;
+ /** Flag to enable duplicate key support */
+ private boolean allowDuplicates;
/**
* @return the pageSize
@@ -317,4 +319,27 @@ public class BTreeConfiguration<K, V>
{
this.name = name;
}
+
+
+ /**
+ * @return true if duplicate key support is enabled
+ */
+ public boolean isAllowDuplicates()
+ {
+ return allowDuplicates;
+ }
+
+
+ /**
+ * enable duplicate key support
+ *
+ * @param allowDuplicates
+ * @throws IllegalStateException if the btree was already initialized or
when tried to turn off duplicate suport on
+ * an existing btree containing duplicate
keys
+ */
+ public void setAllowDuplicates( boolean allowDuplicates )
+ {
+ this.allowDuplicates = allowDuplicates;
+ }
+
}
Modified:
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java?rev=1462787&r1=1462786&r2=1462787&view=diff
==============================================================================
---
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java
(original)
+++
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/Cursor.java
Sat Mar 30 15:55:17 2013
@@ -22,6 +22,7 @@ package org.apache.mavibot.btree;
import java.io.IOException;
import java.util.LinkedList;
+import java.util.NoSuchElementException;
import org.apache.mavibot.btree.exception.EndOfFileExceededException;
@@ -51,6 +52,8 @@ import org.apache.mavibot.btree.exceptio
/** The BTree we are walking */
private BTree<K, V> btree;
+ private boolean allowDuplicates;
+
/**
* Creates a new instance of Cursor, starting on a page at a given
position.
@@ -63,6 +66,7 @@ import org.apache.mavibot.btree.exceptio
this.transaction = transaction;
this.stack = stack;
this.btree = btree;
+ this.allowDuplicates = btree.isAllowDuplicates();
}
@@ -79,7 +83,8 @@ import org.apache.mavibot.btree.exceptio
if ( parentPos.page == null )
{
- return new Tuple<K, V>();
+ // This is the end : no more value
+ throw new NoSuchElementException( "No more tuples present" );
}
if ( parentPos.pos == parentPos.page.getNbElems() )
@@ -91,15 +96,42 @@ import org.apache.mavibot.btree.exceptio
if ( parentPos.page == null )
{
// This is the end : no more value
- return null;
+ throw new NoSuchElementException( "No more tuples present" );
}
}
+ // can happen if next() is called after prev()
+ if ( parentPos.pos < 0 )
+ {
+ parentPos.pos = 0;
+ }
+
Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
tuple.setKey( leaf.keys[parentPos.pos] );
- tuple.setValue( leaf.values[parentPos.pos].getValue( btree ) );
-
- parentPos.pos++;
+
+ if( allowDuplicates )
+ {
+ setDupsContainer( parentPos );
+
+ // can happen if next() is called after prev()
+ if ( parentPos.dupPos < 0 )
+ {
+ parentPos.dupPos = 0;
+ }
+
+ tuple.setValue( parentPos.dupsContainer.rootPage.getKey(
parentPos.dupPos ) );
+ parentPos.dupPos++;
+
+ if( parentPos.dupsContainer.rootPage.getNbElems() ==
parentPos.dupPos )
+ {
+ parentPos.pos++;
+ }
+ }
+ else
+ {
+ tuple.setValue( leaf.values[parentPos.pos].getValue( btree ) );
+ parentPos.pos++;
+ }
return tuple;
}
@@ -114,20 +146,23 @@ import org.apache.mavibot.btree.exceptio
*/
private ParentPos<K, V> findNextParentPos() throws
EndOfFileExceededException, IOException
{
+ ParentPos<K, V> lastParentPos = null;
+
while ( true )
{
- // We first go up the tree, until we reach a page which current
position
+ // We first go up the tree, until we reach a page whose current
position
// is not the last one
ParentPos<K, V> parentPos = stack.peek();
if ( parentPos == null )
{
+ stack.push( lastParentPos );
return null;
}
if ( parentPos.pos == parentPos.page.getNbElems() )
{
- stack.pop();
+ lastParentPos = stack.pop();
continue;
}
else
@@ -147,6 +182,11 @@ import org.apache.mavibot.btree.exceptio
newPos = 0;
}
+ if( allowDuplicates )
+ {
+ setDupsContainer( newParentPos );
+ }
+
return newParentPos;
}
}
@@ -162,6 +202,8 @@ import org.apache.mavibot.btree.exceptio
*/
private ParentPos<K, V> findPreviousParentPos() throws
EndOfFileExceededException, IOException
{
+ ParentPos<K, V> lastParentPos = null;
+
while ( true )
{
// We first go up the tree, until we reach a page which current
position
@@ -170,12 +212,13 @@ import org.apache.mavibot.btree.exceptio
if ( parentPos == null )
{
- return null;
+ stack.push( lastParentPos );
+ return lastParentPos;
}
if ( parentPos.pos == 0 )
{
- stack.pop();
+ lastParentPos = stack.pop();
continue;
}
else
@@ -196,6 +239,12 @@ import org.apache.mavibot.btree.exceptio
newPos = node.getNbElems();
}
+ if( allowDuplicates )
+ {
+ setDupsContainer( newParentPos );
+ parentPos.dupPos = ( int )
newParentPos.dupsContainer.getNbElems();
+ }
+
return newParentPos;
}
}
@@ -215,10 +264,11 @@ import org.apache.mavibot.btree.exceptio
if ( parentPos.page == null )
{
- return new Tuple<K, V>();
+ // This is the end : no more value
+ throw new NoSuchElementException( "No more tuples present" );
}
- if ( parentPos.pos == 0 )
+ if ( parentPos.pos == 0 && parentPos.dupPos == 0 )
{
// End of the leaf. We have to go back into the stack up to the
// parent, and down to the leaf
@@ -227,17 +277,49 @@ import org.apache.mavibot.btree.exceptio
if ( parentPos.page == null )
{
// This is the end : no more value
- return null;
+ throw new NoSuchElementException( "No more tuples present" );
}
}
Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
- parentPos.pos--;
-
- tuple.setKey( leaf.keys[parentPos.pos] );
- tuple.setValue( leaf.values[parentPos.pos].getValue( btree ) );
-
+
+ if( allowDuplicates )
+ {
+ setDupsContainer( parentPos );
+
+ // can happen if prev() was called after next()
+ if( parentPos.pos == parentPos.page.getNbElems() )
+ {
+ parentPos.pos--;
+ }
+
+ if( parentPos.dupPos == parentPos.dupsContainer.getNbElems() )
+ {
+ parentPos.dupPos--;
+ }
+ else if( parentPos.dupPos == 0 )
+ {
+ parentPos.pos--;
+ setDupsContainer( parentPos );
+ parentPos.dupPos = ( int )
parentPos.dupsContainer.getNbElems();
+ parentPos.dupPos--;
+ }
+ else
+ {
+ parentPos.dupPos--;
+ }
+
+ tuple.setKey( leaf.keys[parentPos.pos] );
+ tuple.setValue( parentPos.dupsContainer.rootPage.getKey(
parentPos.dupPos ) );
+ }
+ else
+ {
+ parentPos.pos--;
+ tuple.setKey( leaf.keys[parentPos.pos] );
+ tuple.setValue( leaf.values[parentPos.pos].getValue( btree ) );
+ }
+
return tuple;
}
@@ -257,21 +339,23 @@ import org.apache.mavibot.btree.exceptio
return false;
}
- if ( parentPos.pos == parentPos.page.getNbElems() )
- {
- // Remove the leaf from the stack
- stack.pop();
-
- // End of the leaf. We have to go back into the stack up to the
- // parent, and down to the leaf
- parentPos = findNextParentPos();
-
- return ( parentPos != null ) && ( parentPos.page != null );
- }
- else
+ for( ParentPos<K, V> p : stack )
{
- return true;
+ if( allowDuplicates )
+ {
+ if ( ( p.dupPos != p.dupsContainer.getNbElems() )
+ && ( p.pos != p.page.getNbElems() ) )
+ {
+ return true;
+ }
+ }
+ else if ( p.pos != p.page.getNbElems() )
+ {
+ return true;
+ }
}
+
+ return false;
}
@@ -290,21 +374,23 @@ import org.apache.mavibot.btree.exceptio
return false;
}
- if ( parentPos.pos == 0 )
+ for( ParentPos<K, V> p : stack )
{
- // Remove the leaf from the stack
- stack.pop();
-
- // Start of the leaf. We have to go back into the stack up to the
- // parent, and down to the leaf
- parentPos = findPreviousParentPos();
-
- return ( parentPos != null ) && ( parentPos.page != null );
- }
- else
- {
- return true;
+ if( allowDuplicates )
+ {
+ if( ( p.dupPos != 0 )
+ || ( p.pos != 0 ) )
+ {
+ return true;
+ }
+ }
+ else if ( p.pos != 0 )
+ {
+ return true;
+ }
}
+
+ return false;
}
@@ -333,4 +419,15 @@ import org.apache.mavibot.btree.exceptio
{
return transaction.getCreationDate();
}
+
+
+ private void setDupsContainer( ParentPos<K, V> parentPos ) throws
IOException
+ {
+ if( parentPos.dupsContainer == null )
+ {
+ Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
+ BTree<V, V> dupsContainer = ( BTree<V, V> )
leaf.values[parentPos.pos].getValue( btree );
+ parentPos.dupsContainer = dupsContainer;
+ }
+ }
}
Added:
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/DuplicateKeyMemoryHolder.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/DuplicateKeyMemoryHolder.java?rev=1462787&view=auto
==============================================================================
---
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/DuplicateKeyMemoryHolder.java
(added)
+++
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/DuplicateKeyMemoryHolder.java
Sat Mar 30 15:55:17 2013
@@ -0,0 +1,96 @@
+/*
+ * 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.io.IOException;
+import java.util.UUID;
+
+
+/**
+ * A In-Memory holder for values of duplicate keys. The values are always
present in memory.
+ *
+ * @param <K> The type of the BTree key
+ * @param <V> The type of the BTree value
+ *
+ * @author <a href="mailto:[email protected]";>Mavibot labs Project</a>
+ */
+public class DuplicateKeyMemoryHolder<K, V> implements ElementHolder<V, K, V>
+{
+ /** The BTree */
+ private BTree<K, V> btree;
+
+ /** The reference to the Value instance, or null if it's not present */
+ private BTree<V, V> valueContainer;
+
+
+ /**
+ * Create a new holder storing an offset and a SoftReference containing
the value.
+ *
+ * @param offset The offset in disk for this value
+ * @param value The value to store into a SoftReference
+ */
+ public DuplicateKeyMemoryHolder( BTree<K, V> btree, V value )
+ {
+ this.btree = btree;
+
+ try
+ {
+ this.valueContainer = new BTree<V, V>(
UUID.randomUUID().toString(), btree.getValueSerializer(),
+ btree.getValueSerializer() );
+ valueContainer.init();
+ valueContainer.insert( value, null, 0 );
+ }
+ catch ( IOException e )
+ {
+ throw new RuntimeException( e );
+ }
+ }
+
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public V getValue( BTree<K, V> btree )
+ {
+ // wrong cast to please compiler
+ return ( V ) valueContainer;
+ }
+
+
+ /**
+ * @see Object#toString()
+ */
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+
+ sb.append( "'" );
+
+ V value = getValue( btree );
+
+ sb.append( value );
+
+ sb.append( "'" );
+
+ return sb.toString();
+ }
+}
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=1462787&r1=1462786&r2=1462787&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 15:55:17 2013
@@ -60,7 +60,14 @@ public class Leaf<K, V> extends Abstract
{
super( btree, revision, nbElems );
- this.values = ( MemoryHolder<K, V>[] ) Array.newInstance(
MemoryHolder.class, nbElems );
+ if( btree.isAllowDuplicates() )
+ {
+ this.values = ( DuplicateKeyMemoryHolder<K, V>[] )
Array.newInstance( DuplicateKeyMemoryHolder.class, nbElems );
+ }
+ else
+ {
+ this.values = ( MemoryHolder<K, V>[] ) Array.newInstance(
MemoryHolder.class, nbElems );
+ }
}
@@ -467,8 +474,10 @@ public class Leaf<K, V> extends Abstract
int index = -( pos + 1 );
// The first element has been found. Create the cursor
- stack.push( new ParentPos<K, V>( this, index ) );
-
+ ParentPos<K, V> parentPos = new ParentPos<K, V>( this, index );
+ setDupsContainer( parentPos );
+ stack.push( parentPos );
+
cursor = new Cursor<K, V>( btree, transaction, stack );
}
else
@@ -476,7 +485,9 @@ public class Leaf<K, V> extends Abstract
// The key has not been found. Select the value just above, if we
have one
if ( pos < nbElems )
{
- stack.push( new ParentPos<K, V>( this, pos ) );
+ ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
+ setDupsContainer( parentPos );
+ stack.push( parentPos );
cursor = new Cursor<K, V>( btree, transaction, stack );
}
@@ -511,7 +522,11 @@ public class Leaf<K, V> extends Abstract
else
{
// Start at the beginning of the page
- stack.push( new ParentPos<K, V>( this, pos ) );
+ ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
+
+ setDupsContainer( parentPos );
+
+ stack.push( parentPos );
cursor = new Cursor<K, V>( btree, transaction, stack );
}
@@ -561,14 +576,24 @@ public class Leaf<K, V> extends Abstract
newLeaf = ( Leaf<K, V> ) copy( revision, nbElems );
}
- // Now we can inject the value
- V oldValue = newLeaf.values[pos].getValue( btree );
-
- newLeaf.values[pos] = btree.createHolder( value );
-
+ V oldValue = null;
+
+ 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 );
+ }
+ else
+ {
+ // Now we can inject the value
+ 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;
}
@@ -588,8 +613,19 @@ public class Leaf<K, V> extends Abstract
// First copy the current page, but add one element in the copied page
Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems + 1 );
- // Atm, store the value in memory
- MemoryHolder<K, V> valueHolder = new MemoryHolder<K, V>( btree, value
);
+ // Atm, store the value in memory
+
+ ElementHolder valueHolder = null;
+
+ if( btree.isAllowDuplicates() )
+ {
+ valueHolder = new DuplicateKeyMemoryHolder<K, V>( btree, value );
+ }
+ else
+ {
+ valueHolder = new MemoryHolder<K, V>( btree, value );
+ }
+
//ValueHolder<K, V> valueHolder = btree.createHolder( value );
// Deal with the special case of an empty page
@@ -713,12 +749,33 @@ public class Leaf<K, V> extends Abstract
/**
* {@inheritDoc}
+ */
+ public K getRightMostKey()
+ {
+ return keys[nbElems - 1];
+ }
+
+
+ /**
+ * {@inheritDoc}
* @throws IOException
* @throws EndOfFileExceededException
*/
public Tuple<K, V> findLeftMost() throws EndOfFileExceededException,
IOException
{
- return new Tuple<K, V>( keys[0], values[0].getValue( btree ) );
+ V val = null;
+
+ if( btree.isAllowDuplicates() )
+ {
+ 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 );
}
@@ -729,7 +786,19 @@ public class Leaf<K, V> extends Abstract
*/
public Tuple<K, V> findRightMost() throws EndOfFileExceededException,
IOException
{
- return new Tuple<K, V>( keys[nbElems - 1], values[nbElems -
1].getValue( btree ) );
+ V val = null;
+
+ if( btree.isAllowDuplicates() )
+ {
+ 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 );
}
@@ -769,6 +838,22 @@ public class Leaf<K, V> extends Abstract
return sb.toString();
}
+
+ private void setDupsContainer( ParentPos<K,V> parentPos )
+ {
+ if( btree.isAllowDuplicates() )
+ {
+ try
+ {
+ BTree<V, V> dupsContainer = ( BTree<V, V> )
values[parentPos.pos].getValue( btree );
+ parentPos.dupsContainer = dupsContainer;
+ }
+ 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=1462787&r1=1462786&r2=1462787&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 15:55:17 2013
@@ -1138,6 +1138,15 @@ public class Node<K, V> extends Abstract
/**
* {@inheritDoc}
+ */
+ public K getRightMostKey() throws EndOfFileExceededException, IOException
+ {
+ return children[nbElems - 1].getValue( btree ).getRightMostKey();
+ }
+
+
+ /**
+ * {@inheritDoc}
* @throws IOException
* @throws EndOfFileExceededException
*/
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=1462787&r1=1462786&r2=1462787&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 15:55:17 2013
@@ -152,6 +152,17 @@ public interface Page<K, V>
/**
+ * Find the rightmost key in this page. If the page is a node, it will go
+ * down in the rightmost children to recursively find the rightmost key.
+ *
+ * @return The rightmost key in the tree
+ * @throws IOException
+ * @throws EndOfFileExceededException
+ */
+ K getRightMostKey() throws EndOfFileExceededException, IOException;
+
+
+ /**
* Find 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.
*
Modified:
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/ParentPos.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/ParentPos.java?rev=1462787&r1=1462786&r2=1462787&view=diff
==============================================================================
---
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/ParentPos.java
(original)
+++
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/main/java/org/apache/mavibot/btree/ParentPos.java
Sat Mar 30 15:55:17 2013
@@ -37,7 +37,12 @@ package org.apache.mavibot.btree;
/** The current position in the page */
/* No qualifier*/int pos;
+ /** The current position of the duplicate container in the page */
+ /* No qualifier*/int dupPos;
+ /** the container of duplicate key's values. The tuples will be stored as
<V,null>*/
+ /* No qualifier*/BTree<V, V> dupsContainer;
+
/**
* Creates a new instance of ParentPos
* @param page The current Page
Added:
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=1462787&view=auto
==============================================================================
---
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/BTreeDuplicateKeyTest.java
(added)
+++
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/BTreeDuplicateKeyTest.java
Sat Mar 30 15:55:17 2013
@@ -0,0 +1,166 @@
+/*
+ * 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 static org.junit.Assert.*;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import java.io.IOException;
+import java.util.NoSuchElementException;
+
+import org.apache.mavibot.btree.serializer.IntSerializer;
+import org.junit.Test;
+
+
+/**
+ * TODO BTreeDuplicateKeyTest.
+ *
+ * @author <a href="mailto:[email protected]";>Apache Directory
Project</a>
+ */
+public class BTreeDuplicateKeyTest
+{
+ @Test
+ public void testInsertNullValue() throws IOException
+ {
+ IntSerializer serializer = new IntSerializer();
+
+ BTree<Integer, Integer> btree = new BTree<Integer, Integer>( "master",
serializer, serializer );
+ btree.init();
+
+ btree.insert( 1, null );
+
+ Cursor<Integer, Integer> cursor = btree.browse();
+ assertTrue( cursor.hasNext() );
+
+ Tuple<Integer, Integer> t = cursor.next();
+
+ assertEquals( Integer.valueOf( 1 ), t.getKey() );
+ assertEquals( null, t.getValue() );
+
+ cursor.close();
+ }
+
+
+ @Test
+ public void testBrowseEmptyTree() throws IOException
+ {
+ IntSerializer serializer = new IntSerializer();
+
+ BTree<Integer, Integer> btree = new BTree<Integer, Integer>( "master",
serializer, serializer );
+ btree.init();
+
+ Cursor<Integer, Integer> cursor = btree.browse();
+ assertFalse( cursor.hasNext() );
+ assertFalse( cursor.hasPrev() );
+
+ try
+ {
+ cursor.next();
+ fail("Should not reach here");
+ }
+ catch(NoSuchElementException e)
+ {
+ assertTrue(true);
+ }
+
+ try
+ {
+ cursor.prev();
+ fail("Should not reach here");
+ }
+ catch(NoSuchElementException e)
+ {
+ assertTrue(true);
+ }
+
+ cursor.close();
+ }
+
+ @Test
+ public void testDuplicateKey() throws IOException
+ {
+ 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 );
+
+ Cursor<Integer, Integer> cursor = btree.browse();
+ assertTrue( cursor.hasNext() );
+
+ Tuple<Integer, Integer> t = cursor.next();
+
+ assertEquals( Integer.valueOf( 1 ), t.getKey() );
+ assertEquals( Integer.valueOf( 1 ), t.getValue() );
+
+ assertTrue( cursor.hasNext() );
+
+ t = cursor.next();
+
+ assertEquals( Integer.valueOf( 1 ), t.getKey() );
+ assertEquals( Integer.valueOf( 2 ), t.getValue() );
+
+ assertFalse( cursor.hasNext() );
+
+ // test backward move
+ assertTrue( cursor.hasPrev() );
+
+ t = cursor.prev();
+
+ assertEquals( Integer.valueOf( 1 ), t.getKey() );
+ assertEquals( Integer.valueOf( 2 ), t.getValue() );
+
+ assertTrue( cursor.hasPrev() );
+
+ t = cursor.prev();
+
+ assertEquals( Integer.valueOf( 1 ), t.getKey() );
+ assertEquals( Integer.valueOf( 1 ), t.getValue() );
+
+ assertFalse( cursor.hasPrev() );
+
+ // again forward
+ assertTrue( cursor.hasNext() );
+
+ t = cursor.next();
+
+ assertEquals( Integer.valueOf( 1 ), t.getKey() );
+ assertEquals( Integer.valueOf( 1 ), t.getValue() );
+
+ assertTrue( cursor.hasNext() );
+
+ t = cursor.next();
+
+ assertEquals( Integer.valueOf( 1 ), t.getKey() );
+ assertEquals( Integer.valueOf( 2 ), t.getValue() );
+
+ assertFalse( cursor.hasNext() );
+
+ cursor.close();
+ }
+
+}
Modified:
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java?rev=1462787&r1=1462786&r2=1462787&view=diff
==============================================================================
---
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java
(original)
+++
labs/mavibot/branches/mavibot-multivalue-support/mavibot/src/test/java/org/apache/mavibot/btree/InMemoryBTreeTest.java
Sat Mar 30 15:55:17 2013
@@ -812,6 +812,8 @@ public class InMemoryBTreeTest
// get 12 (now, we must have gone through at least 2 pages)
assertEquals( 12, cursor.next().getKey().intValue() );
+ assertTrue( cursor.hasPrev() );
+
// Lets go backward. We should get the same value, as the next() call
have incremented the counter
assertEquals( 12, cursor.prev().getKey().intValue() );
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
