directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kayyag...@apache.org
Subject svn commit: r1518569 - in /directory/mavibot/trunk/mavibot/src: main/java/org/apache/directory/mavibot/btree/ test/java/org/apache/directory/mavibot/btree/
Date Thu, 29 Aug 2013 10:12:14 GMT
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 ) ) );



Mime
View raw message