You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by ka...@apache.org on 2013/08/29 12:12:14 UTC
svn commit: r1518569 - in /directory/mavibot/trunk/mavibot/src:
main/java/org/apache/directory/mavibot/btree/
test/java/org/apache/directory/mavibot/btree/
Author: kayyagari
Date: Thu Aug 29 10:12:13 2013
New Revision: 1518569
URL: http://svn.apache.org/r1518569
Log:
avoid creating a sub-tree if only one value is present for a key in a tree that allows duplicate keys (MAVIBOT-8)
Added:
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/DuplicateKeyVal.java
Modified:
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InternalUtil.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Leaf.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/MultipleMemoryHolder.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Node.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java
directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BTreeDuplicateKeyTest.java
directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/RecordManagerTest.java
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java?rev=1518569&r1=1518568&r2=1518569&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/BTree.java Thu Aug 29 10:12:13 2013
@@ -842,7 +842,7 @@ public class BTree<K, V> implements Clos
/**
* @see Page#getValues(Object)
*/
- public BTree<V, V> getValues( K key ) throws IOException, KeyNotFoundException
+ public DuplicateKeyVal<V> getValues( K key ) throws IOException, KeyNotFoundException
{
return rootPage.getValues( key );
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.java?rev=1518569&r1=1518568&r2=1518569&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Cursor.java Thu Aug 29 10:12:13 2013
@@ -124,21 +124,31 @@ public class Cursor<K, V>
if ( allowDuplicates )
{
- setDupsContainer( parentPos, btree );
-
- // can happen if next() is called after prev()
- if ( parentPos.dupPos < 0 )
+ MultipleMemoryHolder<K,V> mvHolder = ( MultipleMemoryHolder<K,V> ) leaf.values[parentPos.pos];
+
+ if( mvHolder.isSingleValue() )
{
- parentPos.dupPos = 0;
+ tuple.setValue( mvHolder.getValue( btree ) );
+ parentPos.pos++;
}
-
- tuple.setValue( parentPos.dupsContainer.rootPage.getKey( parentPos.dupPos ) );
- parentPos.dupPos++;
-
- if ( parentPos.dupsContainer.getNbElems() == parentPos.dupPos )
+ else
{
- parentPos.pos++;
- changeNextDupsContainer( parentPos, btree );
+ setDupsContainer( parentPos, btree );
+
+ // 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.getNbElems() == parentPos.dupPos )
+ {
+ parentPos.pos++;
+ changeNextDupsContainer( parentPos, btree );
+ }
}
}
else
@@ -300,31 +310,76 @@ public class Cursor<K, V>
if ( allowDuplicates )
{
- setDupsContainer( parentPos, btree );
-
+ boolean posDecremented = false;
+
// can happen if prev() was called after next()
if ( parentPos.pos == parentPos.page.getNbElems() )
{
parentPos.pos--;
+ posDecremented = true;
}
- if ( parentPos.dupPos == parentPos.dupsContainer.getNbElems() )
+ MultipleMemoryHolder<K,V> mvHolder = ( MultipleMemoryHolder<K,V> ) leaf.values[parentPos.pos];
+
+ boolean prevHasSubtree = false;
+ // if the current key has only one value then advance to previous position
+ if( mvHolder.isSingleValue() )
{
- parentPos.dupPos--;
+ if( !posDecremented )
+ {
+ parentPos.pos--;
+ mvHolder = ( MultipleMemoryHolder<K,V> ) leaf.values[parentPos.pos];
+ posDecremented = true;
+ }
+
+ if( mvHolder.isSingleValue() )
+ {
+ tuple.setKey( leaf.keys[parentPos.pos] );
+ tuple.setValue( mvHolder.getValue( btree ) );
+ }
+ else
+ {
+ prevHasSubtree = true;
+ }
}
- else if ( parentPos.dupPos == 0 )
+ else
{
- changePrevDupsContainer( parentPos, btree );
- parentPos.pos--;
- parentPos.dupPos--;
+ prevHasSubtree = true;
}
- else
+
+ if( prevHasSubtree )
{
- parentPos.dupPos--;
+ setDupsContainer( parentPos, btree );
+
+ if ( parentPos.dupPos == parentPos.dupsContainer.getNbElems() )
+ {
+ parentPos.dupPos--;
+ }
+ else if ( parentPos.dupPos == 0 )
+ {
+ changePrevDupsContainer( parentPos, btree );
+ parentPos.pos--;
+
+ if( parentPos.dupsContainer != null )
+ {
+ parentPos.dupPos--;
+ }
+ }
+ else
+ {
+ parentPos.dupPos--;
+ }
+
+ tuple.setKey( leaf.keys[parentPos.pos] );
+ if( parentPos.dupsContainer != null )
+ {
+ tuple.setValue( parentPos.dupsContainer.rootPage.getKey( parentPos.dupPos ) );
+ }
+ else
+ {
+ tuple.setValue( leaf.values[parentPos.pos].getValue( btree ) );
+ }
}
-
- tuple.setKey( leaf.keys[parentPos.pos] );
- tuple.setValue( parentPos.dupsContainer.rootPage.getKey( parentPos.dupPos ) );
}
else
{
@@ -356,8 +411,12 @@ public class Cursor<K, V>
{
if ( allowDuplicates && ( p.page instanceof Leaf ) )
{
- if ( ( p.dupPos != p.dupsContainer.getNbElems() )
- && ( p.pos != p.page.getNbElems() ) )
+ if( ( p.dupsContainer == null ) && ( p.pos != p.page.getNbElems() ) )
+ {
+ return true;
+ }
+ else if ( ( p.dupsContainer != null ) && ( p.dupPos != p.dupsContainer.getNbElems() )
+ && ( p.pos != p.page.getNbElems() ) )
{
return true;
}
@@ -391,8 +450,12 @@ public class Cursor<K, V>
{
if ( allowDuplicates && ( p.page instanceof Leaf ) )
{
- if ( ( p.dupPos != 0 )
- || ( p.pos != 0 ) )
+ if( ( p.dupsContainer == null ) && ( p.pos != 0 ) )
+ {
+ return true;
+ }
+ else if ( ( p.dupsContainer != null ) &&
+ ( ( p.dupPos != 0 ) || ( p.pos != 0 ) ) )
{
return true;
}
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/DuplicateKeyVal.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/DuplicateKeyVal.java?rev=1518569&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/DuplicateKeyVal.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/DuplicateKeyVal.java Thu Aug 29 10:12:13 2013
@@ -0,0 +1,72 @@
+/*
+ * 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.directory.mavibot.btree;
+
+
+/**
+ * A class to hold a single value or multiple values (in a sub-tree) of a key.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class DuplicateKeyVal<V>
+{
+ private V singleValue;
+
+ private BTree<V, V> subTree;
+
+
+ /** No Qualifier */
+ DuplicateKeyVal( V singleValue )
+ {
+ this.singleValue = singleValue;
+ }
+
+
+ /** No Qualifier */
+ DuplicateKeyVal( BTree<V, V> subTree )
+ {
+ this.subTree = subTree;
+ }
+
+
+ public boolean isSingleValue()
+ {
+ return ( singleValue != null );
+ }
+
+
+ /**
+ * @return the singleValue
+ */
+ public V getSingleValue()
+ {
+ return singleValue;
+ }
+
+
+ /**
+ * @return the subTree
+ */
+ public BTree<V, V> getSubTree()
+ {
+ return subTree;
+ }
+
+}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InternalUtil.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InternalUtil.java?rev=1518569&r1=1518568&r2=1518569&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InternalUtil.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/InternalUtil.java Thu Aug 29 10:12:13 2013
@@ -49,19 +49,16 @@ import java.io.IOException;
return;
}
- try
+ if ( parentPos.dupsContainer == null )
{
- if ( parentPos.dupsContainer == null )
+ Leaf leaf = ( Leaf ) ( parentPos.page );
+ MultipleMemoryHolder mvHolder = ( MultipleMemoryHolder ) leaf.values[parentPos.pos];
+ if( !mvHolder.isSingleValue() )
{
- Leaf leaf = ( Leaf ) ( parentPos.page );
- BTree dupsContainer = ( BTree ) leaf.values[parentPos.pos].getValue( btree );
+ BTree dupsContainer = ( BTree ) mvHolder.getValue( btree );
parentPos.dupsContainer = dupsContainer;
}
}
- catch ( IOException e )
- {
- throw new RuntimeException( e );
- }
}
@@ -83,9 +80,13 @@ import java.io.IOException;
if ( parentPos.pos < parentPos.page.getNbElems() )
{
Leaf leaf = ( Leaf ) ( parentPos.page );
- BTree dupsContainer = ( BTree ) leaf.values[parentPos.pos].getValue( btree );
- parentPos.dupsContainer = dupsContainer;
- parentPos.dupPos = 0;
+ MultipleMemoryHolder mvHolder = ( MultipleMemoryHolder ) leaf.values[parentPos.pos];
+ if( !mvHolder.isSingleValue() )
+ {
+ BTree dupsContainer = ( BTree ) mvHolder.getValue( btree );
+ parentPos.dupsContainer = dupsContainer;
+ parentPos.dupPos = 0;
+ }
}
}
@@ -109,9 +110,18 @@ import java.io.IOException;
if ( index >= 0 )
{
Leaf leaf = ( Leaf ) ( parentPos.page );
- BTree dupsContainer = ( BTree ) leaf.values[index].getValue( btree );
- parentPos.dupsContainer = dupsContainer;
- parentPos.dupPos = ( int ) parentPos.dupsContainer.getNbElems();
+ MultipleMemoryHolder mvHolder = ( MultipleMemoryHolder ) leaf.values[index];
+ if( !mvHolder.isSingleValue() )
+ {
+ BTree dupsContainer = ( BTree ) mvHolder.getValue( btree );
+ parentPos.dupsContainer = dupsContainer;
+ parentPos.dupPos = ( int ) parentPos.dupsContainer.getNbElems();
+ }
+ else
+ {
+ parentPos.dupsContainer = null;
+ parentPos.dupPos = -1;
+ }
}
}
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Leaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Leaf.java?rev=1518569&r1=1518568&r2=1518569&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Leaf.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Leaf.java Thu Aug 29 10:12:13 2013
@@ -157,28 +157,60 @@ import org.apache.directory.mavibot.btre
if ( btree.isAllowDuplicates() )
{
- BTree<V, V> dups = ( BTree<V, V> ) values[index].getValue( btree );
+ MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) values[index];
- if ( dups.hasKey( value ) )
+ //FIXME should the internal sub-tree should be deleted from RM?
+
+ V existingVal = mvHolder.getValue( btree );
+
+ if ( value == null ) // this is a case to delete entire <K,sub-BTree> or <K,single-V>
{
- 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
+ removedElement = new Tuple<K, V>( keys[index], existingVal ); // the entire value was removed
keyRemoved = true;
}
else
- // value is not found
{
- return NotPresentResult.NOT_PRESENT;
+ if( mvHolder.isSingleValue() )
+ {
+ if ( btree.getValueSerializer().compare( value, existingVal ) == 0 )
+ {
+ removedElement = new Tuple<K, V>( keys[index], existingVal ); // the entire value was removed
+ keyRemoved = true;
+ }
+ else // value is not found
+ {
+ return NotPresentResult.NOT_PRESENT;
+ }
+ }
+ else
+ {
+ BTree<V, V> dups = ( BTree<V, V> ) existingVal;
+
+ if ( dups.hasKey( value ) )
+ {
+ dups.delete( value );
+
+ if ( dups.getNbElems() == 0 )
+ {
+ keyRemoved = true;
+ }
+ else
+ {
+ if ( dups.getNbElems() == 1 )
+ {
+ //FIXME switch to single value mode
+ mvHolder.switchToSingleValMode();
+ }
+ }
+
+ removedElement = new Tuple<K, V>( keys[index], value ); // we deleted only one value (even if it is from a tree of size 1)
+ }
+ else
+ // value is not found
+ {
+ return NotPresentResult.NOT_PRESENT;
+ }
+ }
}
}
else
@@ -499,15 +531,23 @@ import org.apache.directory.mavibot.btre
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.rootPage.getLeftMostKey();
+ MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) values[-( pos + 1 )];
+ if ( mvHolder.isSingleValue() )
+ {
+ return mvHolder.getValue( btree );
+ }
+ else
+ {
+ // always return the first value for get(key) when duplicates are allowed
+ BTree<V, V> dupTree = ( BTree<V, V> ) mvHolder.getValue( btree );
+ return dupTree.rootPage.getLeftMostKey();
+ }
}
+ V v = values[-( pos + 1 )].getValue( btree );
+
return v;
}
else
@@ -521,7 +561,7 @@ import org.apache.directory.mavibot.btre
* {@inheritDoc}
*/
@Override
- public BTree<V, V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
+ public DuplicateKeyVal<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
{
if ( !btree.isAllowDuplicates() )
{
@@ -532,9 +572,14 @@ import org.apache.directory.mavibot.btre
if ( pos < 0 )
{
- V v = values[-( pos + 1 )].getValue( btree );
+ MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) values[-( pos + 1 )];
- return ( ( BTree<V, V> ) v );
+ if( mvHolder.isSingleValue() )
+ {
+ return new DuplicateKeyVal<V>( mvHolder.getValue( btree ) );
+ }
+
+ return new DuplicateKeyVal<V>( ( BTree<V, V> ) mvHolder.getValue( btree ) );
}
else
{
@@ -566,16 +611,23 @@ import org.apache.directory.mavibot.btre
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 );
+ MultipleMemoryHolder<K,V> mvHolder = ( MultipleMemoryHolder<K,V> ) values[-( pos + 1 )];
+ if( mvHolder.isSingleValue() )
+ {
+ return ( btree.getValueSerializer().compare( value, mvHolder.getValue( btree ) ) == 0 );
+ }
+ else
+ {
+ // always return the first value for get(key) when duplicates are allowed
+ BTree<V, V> dupTree = ( ( BTree<V, V> ) mvHolder.getValue( btree ) );
+ return dupTree.hasKey( value );
+ }
}
else
{
+ V v = values[-( pos + 1 )].getValue( btree );
return ( btree.getValueSerializer().compare( value, v ) == 0 );
}
}
@@ -731,16 +783,38 @@ import org.apache.directory.mavibot.btre
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 ) )
- {
- dupValues.insert( value, null, 0 );
+ MultipleMemoryHolder<K,V> mvHolder = ( MultipleMemoryHolder<K,V> ) newLeaf.values[pos];
+
+ if ( mvHolder.isSingleValue() )
+ {
+ V singleVal = mvHolder.getValue( btree );
+
+ // see if the given value already matches
+ if( btree.getValueSerializer().compare( value, singleVal ) == 0 )
+ {
+ oldValue = value;
+ }
+ else // create a sub-tree
+ {
+ mvHolder.createAndSwitchToSubTree();
+ }
}
- else
- {
- oldValue = value;
+
+ // if oldValue is null then the given 'value' is different and needs to be added
+ // ('oldValue' will be not null if it matched with the 'singleValue', see above nested if block )
+ if( oldValue == null )
+ {
+ BTree<V, V> dupValues = ( BTree<V, V> ) mvHolder.getValue( btree );
+
+ // return value will always be null here
+ if ( !dupValues.hasKey( value ) )
+ {
+ dupValues.insert( value, null, 0 );
+ }
+ else
+ {
+ oldValue = value;
+ }
}
}
else
@@ -797,7 +871,6 @@ import org.apache.directory.mavibot.btre
}
else
{
- //FIXME do not copy the duplicate key's value container, this will improve the perf significantly
// 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 );
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/MultipleMemoryHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/MultipleMemoryHolder.java?rev=1518569&r1=1518568&r2=1518569&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/MultipleMemoryHolder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/MultipleMemoryHolder.java Thu Aug 29 10:12:13 2013
@@ -50,6 +50,8 @@ public class MultipleMemoryHolder<K, V>
/** This value is set only when the parent BTree is in managed mode */
private SoftReference<BTree<V, V>> reference;
+ /** the single value of the key when only one value exists for the key */
+ private V singleValue;
/**
* Create a new holder storing an offset and a SoftReference containing the value.
@@ -60,38 +62,7 @@ public class MultipleMemoryHolder<K, V>
public MultipleMemoryHolder( BTree<K, V> btree, V value )
{
this.btree = btree;
-
- try
- {
- BTree<V, V> valueContainer = new BTree<V, V>( UUID.randomUUID().toString(), btree.getValueSerializer(),
- btree.getValueSerializer() );
-
- if ( btree.isManaged() )
- {
- try
- {
- btree.getRecordManager().manage( valueContainer, true );
- valContainerOffset = valueContainer.getBtreeOffset();
- }
- catch ( BTreeAlreadyManagedException e )
- {
- // should never happen
- throw new RuntimeException( e );
- }
-
- reference = new SoftReference<BTree<V, V>>( valueContainer );
- }
- else
- {
- this.valueContainer = valueContainer;
- }
-
- valueContainer.insert( value, null, 0 );
- }
- catch ( IOException e )
- {
- throw new RuntimeException( e );
- }
+ this.singleValue = value;
}
@@ -122,7 +93,7 @@ public class MultipleMemoryHolder<K, V>
}
}
-
+
/**
* {@inheritDoc}
*/
@@ -131,22 +102,126 @@ public class MultipleMemoryHolder<K, V>
{
if ( !btree.isManaged() )
{
- // wrong cast to please compiler
+ if( valueContainer != null )
+ {
+ // wrong cast to please compiler
+ return ( V ) valueContainer;
+ }
+ else
+ {
+ return singleValue;
+ }
+ }
+
+ if( reference != null )
+ {
+ BTree<V, V> valueContainer = reference.get();
+
+ if ( valueContainer == null )
+ {
+ valueContainer = btree.getRecordManager().loadDupsBTree( valContainerOffset );
+ reference = new SoftReference<BTree<V, V>>( valueContainer );
+ }
+
return ( V ) valueContainer;
}
- BTree<V, V> valueContainer = reference.get();
+ return singleValue;
+ }
- if ( valueContainer == null )
+
+ void switchToSingleValMode()
+ {
+ if( ( valueContainer == null ) || ( reference == null ) )
{
- valueContainer = btree.getRecordManager().loadDupsBTree( valContainerOffset );
- reference = new SoftReference<BTree<V, V>>( valueContainer );
+ return;
+ }
+
+ try
+ {
+ //delete the btree using offset
+ if( !btree.isManaged() )
+ {
+ singleValue = valueContainer.rootPage.getLeftMostKey();
+ valueContainer = null;
+ }
+ else
+ {
+ BTree<V,V> values = ( BTree<V,V> ) getValue( btree );
+ singleValue = values.rootPage.getLeftMostKey();
+ reference = null;
+ valContainerOffset = -1;
+ valueContainer = null;
+ //FIXME reclaim the free space of the sub-tree
+ //btree.getRecordManager().freeBtree(values);
+ }
+ }
+ catch( IOException e )
+ {
+ throw new RuntimeException( e );
}
-
- return ( V ) valueContainer;
}
+
+
+ BTree<V,V> createAndSwitchToSubTree()
+ {
+ if( reference != null )
+ {
+ throw new IllegalStateException( "Subtree was already created with offset " + valContainerOffset );
+ }
+
+ try
+ {
+ BTree<V, V> valueContainer = new BTree<V, V>( UUID.randomUUID().toString(), btree.getValueSerializer(),
+ btree.getValueSerializer() );
+ if ( btree.isManaged() )
+ {
+ try
+ {
+ btree.getRecordManager().manage( valueContainer, true );
+ valContainerOffset = valueContainer.getBtreeOffset();
+ }
+ catch ( BTreeAlreadyManagedException e )
+ {
+ // should never happen
+ throw new RuntimeException( e );
+ }
+
+ reference = new SoftReference<BTree<V, V>>( valueContainer );
+ }
+ else
+ {
+ this.valueContainer = valueContainer;
+ }
+
+ valueContainer.insert( singleValue, null, 0 );
+ }
+ catch ( IOException e )
+ {
+ throw new RuntimeException( e );
+ }
+
+ return valueContainer;
+ }
+
+ /**
+ * Tells if there is only one value in this element holder
+ *
+ * @return true if single value is present, false if multiple values are present
+ */
+ public boolean isSingleValue()
+ {
+ if( !btree.isManaged() )
+ {
+ return ( valueContainer == null );
+ }
+
+ return ( reference == null );
+ }
+
+
/**
* @see Object#toString()
*/
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Node.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Node.java?rev=1518569&r1=1518568&r2=1518569&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Node.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Node.java Thu Aug 29 10:12:13 2013
@@ -853,7 +853,7 @@ import org.apache.directory.mavibot.btre
* {@inheritDoc}
*/
@Override
- public BTree<V, V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
+ public DuplicateKeyVal<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException
{
int pos = findPos( key );
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java?rev=1518569&r1=1518568&r2=1518569&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java Thu Aug 29 10:12:13 2013
@@ -110,7 +110,7 @@ import org.apache.directory.mavibot.btre
* @throws IOException If we have an error while trying to access the page
* @throws IllegalArgumentException If duplicates are not enabled
*/
- BTree<V, V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException;
+ DuplicateKeyVal<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException;
/**
Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java?rev=1518569&r1=1518568&r2=1518569&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/RecordManager.java Thu Aug 29 10:12:13 2013
@@ -595,11 +595,25 @@ public class RecordManager
if ( btree.isAllowDuplicates() )
{
- long value = OFFSET_SERIALIZER.deserialize( byteBuffer );
-
- BTree<K, V> dupValueContainer = loadDupsBTree( value );
-
- valueHolder = new MultipleMemoryHolder( btree, dupValueContainer );
+ byte flag = byteBuffer.get();
+
+ if( flag == 0 )
+ {
+ V singleValue = btree.getValueSerializer().deserialize( byteBuffer );
+ valueHolder = new MultipleMemoryHolder( btree, singleValue );
+ }
+ else if( flag == 1 )
+ {
+ long value = OFFSET_SERIALIZER.deserialize( byteBuffer );
+
+ BTree<K, V> dupValueContainer = loadDupsBTree( value );
+
+ valueHolder = new MultipleMemoryHolder( btree, dupValueContainer );
+ }
+ else
+ {
+ throw new IllegalStateException( "Unknown multiple value holder flag " + flag );
+ }
}
else
{
@@ -1149,10 +1163,25 @@ public class RecordManager
{
if ( btree.isAllowDuplicates() )
{
- MultipleMemoryHolder<K, V> value = ( MultipleMemoryHolder<K, V> ) ( ( Leaf<K, V> ) page )
+ MultipleMemoryHolder<K, V> mvHolder = ( MultipleMemoryHolder<K, V> ) ( ( Leaf<K, V> ) page )
.getValue( pos );
- long duplicateContainerOffset = ( ( BTree<K, V> ) value.getValue( btree ) ).getBtreeOffset();
- buffer = LongSerializer.serialize( duplicateContainerOffset );
+ if( mvHolder.isSingleValue() )
+ {
+ buffer = btree.getValueSerializer().serialize( mvHolder.getValue( btree ) );
+
+ //FIXME find a better way to avoid the copying
+ byte[] tmp = new byte[ buffer.length + 1 ];
+ tmp[0] = 0; // single value flag
+ System.arraycopy( buffer, 0, tmp, 1, buffer.length );
+ buffer = tmp;
+ }
+ else
+ {
+ long duplicateContainerOffset = ( ( BTree<K, V> ) mvHolder.getValue( btree ) ).getBtreeOffset();
+ buffer = new byte[ 8 + 1 ];
+ buffer[0] = 1; // sub-tree flag
+ buffer = LongSerializer.serialize( buffer, 1, duplicateContainerOffset );
+ }
}
else
{
Modified: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BTreeDuplicateKeyTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BTreeDuplicateKeyTest.java?rev=1518569&r1=1518568&r2=1518569&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BTreeDuplicateKeyTest.java (original)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BTreeDuplicateKeyTest.java Thu Aug 29 10:12:13 2013
@@ -388,6 +388,7 @@ public class BTreeDuplicateKeyTest
assertFalse( cursor.hasNext() );
assertTrue( cursor.hasPrev() );
assertEquals( "z", cursor.prev().getKey() );
+ // the key, 'z', has two values
assertEquals( "z", cursor.prev().getKey() );
assertEquals( "y", cursor.prev().getKey() );
Modified: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/RecordManagerTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/RecordManagerTest.java?rev=1518569&r1=1518568&r2=1518569&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/RecordManagerTest.java (original)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/RecordManagerTest.java Thu Aug 29 10:12:13 2013
@@ -862,7 +862,7 @@ public class RecordManagerTest
for ( long i = 0; i < numKeys; i++ )
{
- BTree<String, String> values = dupsTree.getValues( i );
+ DuplicateKeyVal<String> dupVal = dupsTree.getValues( i );
// Cursor<String, String> cursor = values.browse();
// while( cursor.hasNext() )
// {
@@ -870,6 +870,8 @@ public class RecordManagerTest
// }
// cursor.close();
+ BTree<String, String> values = dupVal.getSubTree();
+
for ( int k = 0; k < pageSize + 1; k++ )
{
assertTrue( values.hasKey( String.valueOf( k ) ) );