directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1545944 [1/2] - in /directory/mavibot/trunk/mavibot/src: main/java/org/apache/directory/mavibot/btree/ main/java/org/apache/directory/mavibot/btree/managed/ main/java/org/apache/directory/mavibot/btree/memory/ test/java/org/apache/director...
Date Wed, 27 Nov 2013 07:03:47 GMT
Author: elecharny
Date: Wed Nov 27 07:03:46 2013
New Revision: 1545944

URL: http://svn.apache.org/r1545944
Log:
o Huge refactoring in the way we hold ValueHolder
o The TupleCursor interface have renamed methods and added ones
o Many fixes in the serialization/deserialition
o SpeedUp in managed BTrees

Modified:
    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/TupleCursor.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/KeyHolder.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/RecordManager.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/TupleCursorImpl.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ValueHolder.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTree.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InternalUtil.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Leaf.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Page.java
    directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/TupleCursorImpl.java
    directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/managed/ManagedBTreeBrowseTest.java
    directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/managed/RecordManagerTest.java
    directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/BTreeDuplicateKeyTest.java
    directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/memory/InMemoryBTreeTest.java

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=1545944&r1=1545943&r2=1545944&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 Wed Nov 27 07:03:46 2013
@@ -37,6 +37,10 @@ import org.apache.directory.mavibot.btre
  */
 public interface Cursor<K>
 {
+    /** Static value for the beforeFrst and afterLast positions */
+    static final int BEFORE_FIRST = -1; 
+    static final int AFTER_LAST = -2; 
+
     /**
      * Tells if the cursor can return a next element
      * @return true if there are some more elements

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/TupleCursor.java Wed Nov 27 07:03:46 2013
@@ -39,6 +39,15 @@ import org.apache.directory.mavibot.btre
 public interface TupleCursor<K, V> extends Cursor<K>
 {
     /**
+     * Tells if the cursor can return a next element
+     * 
+     * @return true if there are some more elements
+     * @throws IOException 
+     * @throws EndOfFileExceededException 
+     */
+    public boolean hasNext() throws EndOfFileExceededException, IOException;
+
+    /**
      * Find the next key/value
      * 
      * @return A Tuple containing the found key and value
@@ -49,6 +58,16 @@ public interface TupleCursor<K, V> exten
 
 
     /**
+     * Tells if the cursor can return a previous element
+     * 
+     * @return true if there are some more elements
+     * @throws IOException 
+     * @throws EndOfFileExceededException 
+     */
+    public boolean hasPrev() throws EndOfFileExceededException, IOException;
+    
+    
+    /**
      * Find the previous key/value
      * 
      * @return A Tuple containing the found key and value
@@ -71,40 +90,75 @@ public interface TupleCursor<K, V> exten
 
 
     /**
-     * Moves the cursor to the next non-duplicate key.
-
-     * If the BTree contains 
+     * Tells if the cursor can return a next key
+     * 
+     * @return true if there are some more keys
+     * @throws IOException 
+     * @throws EndOfFileExceededException 
+     */
+    public boolean hasNextKey() throws EndOfFileExceededException, IOException;
+    
+    
+    /**
+     * Get the next non-duplicate key.
+     * If the BTree contains :
      * 
      *  <ul>
      *    <li><1,0></li>
      *    <li><1,1></li>
+     *    <li><1,2></li>
      *    <li><2,0></li>
      *    <li><2,1></li>
      *  </ul>
      *   
-     *  and cursor is present at <1,0> then the cursor will move to <2,0>
+     *  and cursor is present at <1,1> then the returned tuple will be <2,0> (not <1,2>)
      *  
+     * @return A Tuple containing the found key and value
      * @throws EndOfFileExceededException
      * @throws IOException
      */
-    void moveToNextNonDuplicateKey() throws EndOfFileExceededException, IOException;
+    Tuple<K, V> nextKey() throws EndOfFileExceededException, IOException;
 
 
     /**
-     * Moves the cursor to the previous non-duplicate key
-     * If the BTree contains 
+     * Tells if the cursor can return a previous key
+     * 
+     * @return true if there are some more keys
+     * @throws IOException 
+     * @throws EndOfFileExceededException 
+     */
+    public boolean hasPrevKey() throws EndOfFileExceededException, IOException;
+
+    
+    /**
+     * Get the previous non-duplicate key.
+     * If the BTree contains :
      * 
      *  <ul>
      *    <li><1,0></li>
      *    <li><1,1></li>
+     *    <li><1,2></li>
      *    <li><2,0></li>
      *    <li><2,1></li>
      *  </ul>
      *   
-     *  and cursor is present at <2,1> then the cursor will move to <1,1>
-     * 
+     *  and cursor is present at <2,1> then the returned tuple will be <1,0> (not <2,0>)
+     *  
+     * @return A Tuple containing the found key and value
      * @throws EndOfFileExceededException
      * @throws IOException
      */
-    void moveToPrevNonDuplicateKey() throws EndOfFileExceededException, IOException;
+    Tuple<K, V> prevKey() throws EndOfFileExceededException, IOException;
+    
+    
+    /**
+     * Change the position in the current cursor tbefore the first key
+     */
+    void beforeFirst() throws IOException;
+    
+    
+    /**
+     * Change the position in the current cursor to set it after the last key
+     */
+    void afterLast() throws IOException;
 }

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/BTree.java Wed Nov 27 07:03:46 2013
@@ -1028,7 +1028,7 @@ public class BTree<K, V> implements Clos
             // remain in memory.
             ElementHolder<Page<K, V>, K, V> holder = recordManager.writePage( this, modifiedPage,
                 revision );
-
+            
             // The root has just been modified, we haven't split it
             // Get it and make it the current root page
             rootPage = modifiedPage;

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/InternalUtil.java Wed Nov 27 07:03:46 2013
@@ -32,32 +32,6 @@ import java.io.IOException;
 @SuppressWarnings("all")
 /* No qualifier */class InternalUtil
 {
-
-
-    /**
-     * Sets the multi-value container(a.k.a dupsContainer) of the key at the given position
-     * and resets the 'dupsPos' to zero. This is mostly used by Cursor while navigating using
-     * next() 
-     *
-     * @param parentPos the parent position object
-     * @param btree the BTree
-     */
-    public static void changeNextDupsContainer( ParentPos parentPos, BTree btree ) throws IOException
-    {
-        if ( !btree.isAllowDuplicates() )
-        {
-            return;
-        }
-
-        if ( parentPos.pos < parentPos.page.getNbElems() )
-        {
-            Leaf leaf = ( Leaf ) ( parentPos.page );
-            ValueHolder valueHolder = leaf.values[parentPos.pos];
-            parentPos.valueCursor = valueHolder.getCursor();
-        }
-    }
-
-
     /**
      * Sets the multi-value container(a.k.a dupsContainer) of the key at the index below the given position( i.e pos - 1)
      * and resets the 'dupsPos' to the number of elements present in the multi-value container.
@@ -73,12 +47,10 @@ import java.io.IOException;
             return;
         }
 
-        int index = parentPos.pos - 1;
-
-        if ( index >= 0 )
+        if ( parentPos.pos >= 0 )
         {
             Leaf leaf = ( Leaf ) ( parentPos.page );
-            ValueHolder valueHolder = leaf.values[index];
+            ValueHolder valueHolder = leaf.values[parentPos.pos];
             parentPos.valueCursor = valueHolder.getCursor();
         }
     }

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/KeyHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/KeyHolder.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/KeyHolder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/KeyHolder.java Wed Nov 27 07:03:46 2013
@@ -104,7 +104,7 @@ public class KeyHolder<K>
     /**
      * @return The internal serialized byte[]
      */
-    /* No qualifier */byte[] getBuffer()
+    /* No qualifier */byte[] getRaw()
     {
         return raw;
     }

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/RecordManager.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/RecordManager.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/RecordManager.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/RecordManager.java Wed Nov 27 07:03:46 2013
@@ -594,12 +594,12 @@ public class RecordManager
         if ( nbElems >= 0 )
         {
             // It's a leaf
-            page = readLeaf( btree, nbElems, revision, byteBuffer, pageIos );
+            page = readLeafKeysAndValues( btree, nbElems, revision, byteBuffer, pageIos );
         }
         else
         {
             // It's a node
-            page = readNode( btree, -nbElems, revision, byteBuffer, pageIos );
+            page = readNodeKeysAndValues( btree, -nbElems, revision, byteBuffer, pageIos );
         }
 
         return page;
@@ -609,7 +609,7 @@ public class RecordManager
     /**
      * Deserialize a Leaf from some PageIOs
      */
-    private <K, V> Leaf<K, V> readLeaf( BTree<K, V> btree, int nbElems, long revision, ByteBuffer byteBuffer,
+    private <K, V> Leaf<K, V> readLeafKeysAndValues( BTree<K, V> btree, int nbElems, long revision, ByteBuffer byteBuffer,
         PageIO[] pageIos )
     {
         // Its a leaf, create it
@@ -632,40 +632,12 @@ public class RecordManager
             if ( nbValues < 0 )
             {
                 // This is a sub-btree
-                long btreeOffset = byteBuffer.getLong();
-
-                // Load the BTree now.
-                try
-                {
-                    PageIO[] rootPageIos = readPageIOs( btreeOffset, Long.MAX_VALUE );
-
-                    BTree<V, V> subBtree = BTreeFactory.createBTree();
-                    subBtree.setBtreeOffset( btreeOffset );
-
-                    try
-                    {
-                        loadBTree( rootPageIos, subBtree );
-                    }
-                    catch ( Exception e )
-                    {
-                        // should not happen
-                        throw new RuntimeException( e );
-                    }
-
-                    valueHolder = new ValueHolder<V>( btree, btree.getValueSerializer(), subBtree );
-
-                    valueHolder.setSubBtree( subBtree );
-                }
-                catch ( EndOfFileExceededException e1 )
-                {
-                    // TODO Auto-generated catch block
-                    e1.printStackTrace();
-                }
-                catch ( IOException e1 )
-                {
-                    // TODO Auto-generated catch block
-                    e1.printStackTrace();
-                }
+                byte[] btreeOffsetBytes = new byte[LONG_SIZE];
+                byteBuffer.get( btreeOffsetBytes );
+                
+                // Create the valueHolder. As the number of values is negative, we have to switch
+                // to a positive value but as we start at -1 for 0 value, add 1.
+                valueHolder = new ValueHolder<V>( btree, btree.getValueSerializer(), 1 - nbValues, btreeOffsetBytes );
             }
             else
             {
@@ -674,10 +646,9 @@ public class RecordManager
                 valueLengths[i] = byteBuffer.getInt();
 
                 // This is an Array of values, read the byte[] associated with it
-                byte[] valueBytes = new byte[valueLengths[i]];
-                byteBuffer.get( valueBytes );
-                valueHolder = new ValueHolder<V>( btree, btree.getValueSerializer(), false, nbValues,
-                    valueBytes );
+                byte[] arrayBytes = new byte[valueLengths[i]];
+                byteBuffer.get( arrayBytes );
+                valueHolder = new ValueHolder<V>( btree, btree.getValueSerializer(), nbValues, arrayBytes );
             }
 
             BTreeFactory.setValue( leaf, i, valueHolder );
@@ -695,7 +666,7 @@ public class RecordManager
     /**
      * Deserialize a Node from some PageIos
      */
-    private <K, V> Node<K, V> readNode( BTree<K, V> btree, int nbElems, long revision, ByteBuffer byteBuffer,
+    private <K, V> Node<K, V> readNodeKeysAndValues( BTree<K, V> btree, int nbElems, long revision, ByteBuffer byteBuffer,
         PageIO[] pageIos ) throws IOException
     {
         Node<K, V> node = BTreeFactory.createNode( btree, revision, nbElems );
@@ -1256,7 +1227,7 @@ public class RecordManager
     private <K, V> int serializeNodeKey( Node<K, V> node, int pos, List<byte[]> serializedData )
     {
         KeyHolder<K> holder = node.getKeyHolder( pos );
-        byte[] buffer = holder.getBuffer();
+        byte[] buffer = holder.getRaw();
         
         // We have to store the serialized key length
         byte[] length = IntSerializer.serialize( buffer.length );
@@ -1265,7 +1236,7 @@ public class RecordManager
         // And store the serialized key now
         serializedData.add( buffer );
 
-        return buffer.length + 4;
+        return buffer.length + INT_SIZE;
     }
 
 
@@ -1299,7 +1270,7 @@ public class RecordManager
     {
         int dataSize = 0;
         KeyHolder<K> keyHolder = leaf.getKeyHolder( pos );
-        byte[] keyData = keyHolder.getBuffer();
+        byte[] keyData = keyHolder.getRaw();
 
         if ( keyData != null )
         {
@@ -1309,12 +1280,12 @@ public class RecordManager
 
             // And the key data
             serializedData.add( keyData );
-            dataSize += keyData.length + 4;
+            dataSize += keyData.length + INT_SIZE;
         }
         else
         {
             serializedData.add( IntSerializer.serialize( 0 ) );
-            dataSize += 4;
+            dataSize += INT_SIZE;
         }
 
         return dataSize;
@@ -1330,50 +1301,75 @@ public class RecordManager
         // The value can be an Array or a sub-btree, but we don't care
         // we just iterate on all the values
         ValueHolder<V> valueHolder = leaf.getValue( pos );
-
-        // First take the number of values
-        int nbValues = valueHolder.size();
         int dataSize = 0;
 
-        if ( nbValues == 0 )
+        if ( !valueHolder.isSubBtree() )
         {
-            // No value. 
+            int nbValues = valueHolder.size();
+            
+            // Write the nb elements first
             byte[] buffer = IntSerializer.serialize( nbValues );
             serializedData.add( buffer );
+            dataSize = INT_SIZE;
 
-            return buffer.length;
-        }
-
-        if ( valueHolder.isSubBtree() )
-        {
-            byte[] buffer = IntSerializer.serialize( -nbValues );
+            // We have a serialized value. Just flush it
+            byte[] data = valueHolder.getRaw();
+            dataSize += data.length;
+            
+            // Store the data size
+            buffer = IntSerializer.serialize( data.length );
             serializedData.add( buffer );
-            dataSize += buffer.length;
+            dataSize += INT_SIZE;
 
-            // the BTree offset
-            buffer = LongSerializer.serialize( valueHolder.getOffset() );
-            serializedData.add( buffer );
-            dataSize += buffer.length;
+            // and add the data
+            serializedData.add( data );
         }
         else
         {
-            // This is an array, store the nb of values as a positive number
-            byte[] buffer = IntSerializer.serialize( nbValues );
-            serializedData.add( buffer );
-            dataSize += buffer.length;
-
-            // Now store each value
-            byte[] data = valueHolder.getRaw();
-            buffer = IntSerializer.serialize( data.length );
-            serializedData.add( buffer );
-            dataSize += buffer.length;
-
-            if ( data.length > 0 )
+            // First take the number of values
+            int nbValues = valueHolder.size();
+    
+            if ( nbValues == 0 )
+            {
+                // No value. 
+                byte[] buffer = IntSerializer.serialize( nbValues );
+                serializedData.add( buffer );
+    
+                return buffer.length;
+            }
+
+            if ( valueHolder.isSubBtree() )
+            {
+                // Store the nbVlues as a negative number. We add 1 so that 0 is not confused with an Array value 
+                byte[] buffer = IntSerializer.serialize( -( nbValues + 1 ) );
+                serializedData.add( buffer );
+                dataSize += buffer.length;
+    
+                // the BTree offset
+                buffer = LongSerializer.serialize( valueHolder.getOffset() );
+                serializedData.add( buffer );
+                dataSize += buffer.length;
+            }
+            else
             {
-                serializedData.add( data );
+                // This is an array, store the nb of values as a positive number
+                byte[] buffer = IntSerializer.serialize( nbValues );
+                serializedData.add( buffer );
+                dataSize += buffer.length;
+    
+                // Now store each value
+                byte[] data = valueHolder.getRaw();
+                buffer = IntSerializer.serialize( data.length );
+                serializedData.add( buffer );
+                dataSize += buffer.length;
+    
+                if ( data.length > 0 )
+                {
+                    serializedData.add( data );
+                }
+    
+                dataSize += data.length;
             }
-
-            dataSize += data.length;
         }
 
         return dataSize;

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/TupleCursorImpl.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/TupleCursorImpl.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/TupleCursorImpl.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/TupleCursorImpl.java Wed Nov 27 07:03:46 2013
@@ -20,15 +20,11 @@
 package org.apache.directory.mavibot.btree.managed;
 
 
-import static org.apache.directory.mavibot.btree.managed.InternalUtil.changeNextDupsContainer;
-import static org.apache.directory.mavibot.btree.managed.InternalUtil.changePrevDupsContainer;
-
 import java.io.IOException;
 import java.util.NoSuchElementException;
 
 import org.apache.directory.mavibot.btree.Tuple;
 import org.apache.directory.mavibot.btree.TupleCursor;
-import org.apache.directory.mavibot.btree.ValueCursor;
 import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
 
 
@@ -96,7 +92,7 @@ public class TupleCursorImpl<K, V> imple
 
         ParentPos<K, V> parentPos = stack[depth];
 
-        if ( parentPos.page == null )
+        if ( ( parentPos.page == null ) || ( parentPos.pos == AFTER_LAST ) )
         {
             // This is the end : no more value
             throw new NoSuchElementException( "No more tuples present" );
@@ -121,6 +117,12 @@ public class TupleCursorImpl<K, V> imple
         
         if ( parentPos.valueCursor.hasNext() )
         {
+            // Deal with the BeforeFirst case
+            if ( parentPos.pos == BEFORE_FIRST )
+            {
+                parentPos.pos++;
+            }
+            
             value = parentPos.valueCursor.next();
         }
         else
@@ -217,7 +219,7 @@ public class TupleCursorImpl<K, V> imple
                 return parentPos;
             }
         }
-        
+
         return null;
     }
     
@@ -301,7 +303,7 @@ public class TupleCursorImpl<K, V> imple
 
         ParentPos<K, V> parentPos = stack[depth];
 
-        if ( parentPos.page == null )
+        if ( ( parentPos.page == null ) || ( parentPos.pos == BEFORE_FIRST ) )
         {
             // This is the end : no more value
             throw new NoSuchElementException( "No more tuples present" );
@@ -326,6 +328,12 @@ public class TupleCursorImpl<K, V> imple
         
         if ( parentPos.valueCursor.hasPrev() )
         {
+            // Deal with the AfterLast case
+            if ( parentPos.pos == AFTER_LAST )
+            {
+                parentPos.pos = parentPos.page.getNbElems() - 1;
+            }
+            
             value = parentPos.valueCursor.prev();
         }
         else
@@ -370,11 +378,7 @@ public class TupleCursorImpl<K, V> imple
 
 
     /**
-     * Tells if the cursor can return a next tupe.
-     * 
-     * @return true if there are some more elements
-     * @throws IOException 
-     * @throws EndOfFileExceededException 
+     * {@inheritDoc} 
      */
     public boolean hasNext() throws EndOfFileExceededException, IOException
     {
@@ -393,6 +397,11 @@ public class TupleCursorImpl<K, V> imple
             return false;
         }
 
+        if ( parentPos.pos == AFTER_LAST )
+        {
+            return false;
+        }
+        
         if ( parentPos.pos < parentPos.page.getNbElems() - 1 )
         {
             // Not the last position, we have a next value
@@ -432,10 +441,7 @@ public class TupleCursorImpl<K, V> imple
 
 
     /**
-     * Tells if the cursor can return a previous element
-     * @return true if there are some more elements
-     * @throws IOException 
-     * @throws EndOfFileExceededException 
+     * {@inheritDoc} 
      */
     public boolean hasPrev() throws EndOfFileExceededException, IOException
     {
@@ -461,6 +467,12 @@ public class TupleCursorImpl<K, V> imple
         }
         else
         {
+            // Check that we are not before the first value
+            if ( parentPos.pos == BEFORE_FIRST )
+            {
+                return false;
+            }
+            
             // Check if we have some more value
             if ( parentPos.valueCursor.hasPrev() )
             {
@@ -519,87 +531,158 @@ public class TupleCursorImpl<K, V> imple
 
 
     /**
-     * Moves the cursor to the next non-duplicate key.
+     * {@inheritDoc}
+     */
+    public boolean hasNextKey() throws EndOfFileExceededException, IOException
+    {
+        // First check that we have elements in the BTree
+        if ( ( stack == null ) || ( stack.length == 0 ) )
+        {
+            // This is the end : no more key
+            return false;
+        }
 
-     * If the BTree contains 
-     * 
-     *  <ul>
-     *    <li><1,0></li>
-     *    <li><1,1></li>
-     *    <li><2,0></li>
-     *    <li><2,1></li>
-     *  </ul>
-     *   
-     *  and cursor is present at <1,0> then the cursor will move to <2,0>
-     *  
-     * @throws EndOfFileExceededException
-     * @throws IOException
+        ParentPos<K, V> parentPos = stack[depth];
+
+        if ( parentPos.page == null )
+        {
+            // This is the end : no more key
+            return false;
+        }
+        
+        if ( parentPos.pos == ( parentPos.page.getNbElems() - 1 ) )
+        {
+            // End of the leaf. We have to go back into the stack up to the
+            // parent, and down to the next leaf
+            parentPos = findNextParentPos();
+
+            // we also need to check the result of the call to
+            // findNextParentPos as it will return a null ParentPos
+            if ( ( parentPos == null ) || ( parentPos.page == null ) )
+            {
+                // This is the end : no more key
+                return false;
+            }
+            else
+            {
+                // We have more keys
+                return true;
+            }
+        }
+        else
+        {
+            return true;
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
      */
-    public void moveToNextNonDuplicateKey() throws EndOfFileExceededException, IOException
+    public Tuple<K, V> nextKey() throws EndOfFileExceededException, IOException
     {
         // First check that we have elements in the BTree
         if ( ( stack == null ) || ( stack.length == 0 ) )
         {
-            return;
+            // This is the end : no more value
+            throw new NoSuchElementException( "No more tuples present" );
         }
 
         ParentPos<K, V> parentPos = stack[depth];
 
         if ( parentPos.page == null )
         {
-            return;
+            // This is the end : no more value
+            throw new NoSuchElementException( "No more tuples present" );
         }
 
         if ( parentPos.pos == ( parentPos.page.getNbElems() - 1 ) )
         {
             // End of the leaf. We have to go back into the stack up to the
-            // parent, and down to the leaf
-            // increment the position cause findNextParentPos checks "parentPos.pos == parentPos.page.getNbElems()"
+            // parent, and down to the next leaf
+            parentPos = findNextParentPos();
+
+            // we also need to check the result of the call to
+            // findNextParentPos as it will return a null ParentPos
+            if ( ( parentPos == null ) || ( parentPos.page == null ) )
+            {
+                // This is the end : no more value
+                throw new NoSuchElementException( "No more tuples present" );
+            }
+        }
+        else
+        {
+            // Get the next key
             parentPos.pos++;
-            ParentPos<K, V> nextPos = findNextParentPos();
+        }
+
+        // The key
+        Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
+        tuple.setKey( leaf.keys[parentPos.pos].getKey() );
+        
+        // The value
+        ValueHolder<V> valueHolder = leaf.values[parentPos.pos];
+        parentPos.valueCursor = valueHolder.getCursor();
+        V value = parentPos.valueCursor.next();
+        tuple.setValue( value );
+
+        return tuple;
+    }
+
 
-            // if the returned value is a Node OR if it is same as the parentPos
-            // that means cursor is already at the last position
-            // call afterLast() to restore the stack with the path to the right most element
-            if ( ( nextPos.page instanceof Node ) || ( nextPos == parentPos ) )
+    /**
+     * {@inheritDoc}
+     */
+    public boolean hasPrevKey() throws EndOfFileExceededException, IOException
+    {
+        // First check that we have elements in the BTree
+        if ( ( stack == null ) || ( stack.length == 0 ) )
+        {
+            // This is the end : no more key
+            return false;
+        }
+
+        ParentPos<K, V> parentPos = stack[depth];
+
+        if ( parentPos.page == null )
+        {
+            // This is the end : no more key
+            return false;
+        }
+        
+        if ( parentPos.pos == 0 )
+        {
+            // Beginning of the leaf. We have to go back into the stack up to the
+            // parent, and down to the leaf
+            parentPos = findPrevParentPos();
+
+            if ( ( parentPos == null ) || ( parentPos.page == null ) )
             {
-                afterLast();
+                // This is the end : no more key
+                return false;
             }
             else
             {
-                parentPos = nextPos;
+                return true;
             }
         }
         else
         {
-            parentPos.pos++;
-            changeNextDupsContainer( parentPos, btree );
+            return true;
         }
     }
 
 
     /**
-     * Moves the cursor to the previous non-duplicate key
-     * If the BTree contains 
-     * 
-     *  <ul>
-     *    <li><1,0></li>
-     *    <li><1,1></li>
-     *    <li><2,0></li>
-     *    <li><2,1></li>
-     *  </ul>
-     *   
-     *  and cursor is present at <2,1> then the cursor will move to <1,1>
-     * 
-     * @throws EndOfFileExceededException
-     * @throws IOException
+     * {@inheritDoc}
      */
-    public void moveToPrevNonDuplicateKey() throws EndOfFileExceededException, IOException
+    public Tuple<K, V> prevKey() throws EndOfFileExceededException, IOException
     {
         // First check that we have elements in the BTree
         if ( ( stack == null ) || ( stack.length == 0 ) )
         {
-            return;
+            // This is the end : no more value
+            throw new NoSuchElementException( "No more tuples present" );
         }
 
         ParentPos<K, V> parentPos = stack[depth];
@@ -607,38 +690,51 @@ public class TupleCursorImpl<K, V> imple
         if ( parentPos.page == null )
         {
             // This is the end : no more value
-            return;
+            throw new NoSuchElementException( "No more tuples present" );
         }
 
         if ( parentPos.pos == 0 )
         {
-            // End of the leaf. We have to go back into the stack up to the
+            // Beginning of the leaf. We have to go back into the stack up to the
             // parent, and down to the leaf
             parentPos = findPrevParentPos();
 
-            // if the returned value is a Node that means cursor is already at the first position
-            // call beforeFirst() to restore the stack to the initial state
-            if ( parentPos.page instanceof Node )
+            if ( ( parentPos == null ) || ( parentPos.page == null ) )
             {
-                beforeFirst();
+                // This is the end : no more value
+                throw new NoSuchElementException( "No more tuples present" );
             }
         }
         else
         {
-            changePrevDupsContainer( parentPos, btree );
-            parentPos.pos--;
+            if ( parentPos.pos == AFTER_LAST )
+            {
+                parentPos.pos = parentPos.page.getNbElems() - 1;
+            }
+            else
+            {
+                parentPos.pos--;
+            }
         }
+        
+        // Update the Tuple 
+        Leaf<K, V> leaf = ( Leaf<K, V> ) ( parentPos.page );
+
+        // The key
+        tuple.setKey( leaf.keys[parentPos.pos].getKey() );
+
+        // The value
+        ValueHolder<V> valueHolder = leaf.values[parentPos.pos];
+        parentPos.valueCursor = valueHolder.getCursor();
+        V value = parentPos.valueCursor.next();
+        tuple.setValue( value );
+        
+        return tuple;
     }
 
 
     /**
-     * moves the cursor to the same position that was given at the time of instantiating the cursor.
-     * 
-     *  For example, if the cursor was created using browse() method, then beforeFirst() will
-     *  place the cursor before the 0th position.
-     *  
-     *  If the cursor was created using browseFrom(K), then calling beforeFirst() will reset the position
-     *  to the just before the position where K is present.
+     * {@inheritDoc}
      */
     public void beforeFirst() throws IOException
     {
@@ -649,34 +745,30 @@ public class TupleCursorImpl<K, V> imple
         }
 
         Page<K, V> child = null;
-        
+
         for ( int i = 0; i < depth; i++ )
         {
             ParentPos<K, V> parentPos = stack[i];
             parentPos.pos = 0;
-            
+
             if ( child != null )
             {
                 parentPos.page = child;
             }
-            
+
             child = ((Node<K, V>)parentPos.page).children[0].getValue( btree );
         }
-        
+
         // and leaf
         ParentPos<K, V> parentPos = stack[depth];
-        parentPos.pos = 0;
-        
-        if ( child == null )
-        {
-            child = parentPos.page;
-        }
-        else
+        parentPos.pos = BEFORE_FIRST;
+
+        if ( child != null )
         {
             parentPos.page = child;
         }
         
-        parentPos.valueCursor = ((Leaf<K, V>)parentPos.page).values[parentPos.pos].getCursor();
+        parentPos.valueCursor = ((Leaf<K, V>)parentPos.page).values[0].getCursor();
         parentPos.valueCursor.beforeFirst();
     }
 
@@ -707,6 +799,7 @@ public class TupleCursorImpl<K, V> imple
             }
             else
             {
+                // We have N+1 children if the page is a Node, so we don't decrement the nbElems field
                 parentPos.pos = ((Node<K, V>)parentPos.page).nbElems;
             }
 
@@ -718,7 +811,6 @@ public class TupleCursorImpl<K, V> imple
 
         if ( child == null )
         {
-            child = parentPos.page;
             parentPos.pos = ((Leaf<K, V>)parentPos.page).nbElems - 1;
         }
         else
@@ -729,5 +821,6 @@ public class TupleCursorImpl<K, V> imple
 
         parentPos.valueCursor = ((Leaf<K, V>)parentPos.page).values[parentPos.pos].getCursor();
         parentPos.valueCursor.afterLast();
+        parentPos.pos = AFTER_LAST;
     }
 }

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ValueHolder.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ValueHolder.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ValueHolder.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/managed/ValueHolder.java Wed Nov 27 07:03:46 2013
@@ -31,6 +31,7 @@ import org.apache.directory.mavibot.btre
 import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
 import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
 import org.apache.directory.mavibot.btree.serializer.IntSerializer;
+import org.apache.directory.mavibot.btree.serializer.LongSerializer;
 
 
 /**
@@ -49,9 +50,12 @@ public class ValueHolder<V> implements C
 
     /** The serialized value */
     private byte[] raw;
-
-    /** A flag set to true if the values are stored in a BTree */
-    private boolean isSubBtree = false;
+    
+    /** A flag set to true when the raw value has been deserialized */
+    private boolean isDeserialized = false;
+    
+    /** A flag to signal that the raw value represent the serialized values in their last state */
+    private boolean isRawUpToDate = false;
 
     /** The RecordManager */
     private BTree<?, V> btree;
@@ -59,59 +63,36 @@ public class ValueHolder<V> implements C
     /** The Value serializer */
     private ElementSerializer<V> valueSerializer;
 
-    /** An internal flag used when the values are not yet deserialized */
-    private boolean isRaw = true;
-
 
     /**
-     * Creates a new instance of a ValueHolder, containing the serialized values
+     * Creates a new instance of a ValueHolder, containing the serialized values.
      * 
+     * @param btree the container BTree
      * @param valueSerializer The Value's serializer
      * @param raw The raw data containing the values
+     * @param nbValues the number of stored values
+     * @param raw the byte[] containing either the serialized array of values or the sub-btree offset
      */
-    /* No qualifier */ValueHolder( BTree<?, V> btree, ElementSerializer<V> valueSerializer,
-        boolean isSubBtree, int nbValues,
-        byte[] raw )
+    /* No qualifier */ValueHolder( BTree<?, V> btree, ElementSerializer<V> valueSerializer, int nbValues, byte[] raw )
     {
         this.valueSerializer = valueSerializer;
         this.raw = raw;
-        this.isSubBtree = isSubBtree;
         this.btree = btree;
+        isRawUpToDate = true;
 
+        // We create the array of values if they fit in an array. If they are stored in a 
+        // BTree, we do nothing atm.
         if ( nbValues < BTree.valueThresholdUp )
         {
-            // Keep an array
+            // The values are contained into an array
             valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), nbValues );
         }
-        else
-        {
-            // Use a sub btree
-
-            //raw = ByteBuffer.wrap( valueSerializer.serialize( key ) );
-        }
-    }
-
-
-    /**
-     * Creates a new instance of a ValueHolder, containing the serialized values
-     * 
-     * @param valueSerializer The Value's serializer
-     * @param raw The raw data containing the values
-     */
-    /* No qualifier */ValueHolder( BTree<?, V> btree, ElementSerializer<V> valueSerializer,
-        BTree<V, V> subBtree )
-    {
-        this.valueSerializer = valueSerializer;
-        this.btree = btree;
-        raw = null;
-        isRaw = false;
-        isSubBtree = true;
-        valueBtree = subBtree;
     }
 
 
     /**
-     * Creates a new instance of a ValueHolder, containing Values
+     * Creates a new instance of a ValueHolder, containing Values. This constructor is called
+     * whe we need to create a new ValueHolder with deserialized values.
      * 
      * @param valueSerializer The Value's serializer
      * @param values The Values stored in the ValueHolder
@@ -139,28 +120,6 @@ public class ValueHolder<V> implements C
                     ase.printStackTrace();
                     throw ase;
                 }
-
-                // Serialize the values
-                byte[][] data = new byte[nbValues][];
-                int pos = 0;
-                int length = 0;
-
-                for ( V value : values )
-                {
-                    byte[] serializedValue = valueSerializer.serialize( value );
-
-                    data[pos++] = serializedValue;
-                    length += serializedValue.length;
-                }
-
-                raw = new byte[length];
-                pos = 0;
-
-                for ( byte[] bytes : data )
-                {
-                    System.arraycopy( bytes, 0, raw, pos, bytes.length );
-                    pos += bytes.length;
-                }
             }
             else
             {
@@ -185,11 +144,9 @@ public class ValueHolder<V> implements C
         {
             // No value, we create an empty array
             valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), 0 );
-
-            //raw = ByteBuffer.wrap( valueSerializer.serialize( key ) );
         }
-
-        isRaw = false;
+        
+        isDeserialized = true;
     }
 
 
@@ -198,11 +155,12 @@ public class ValueHolder<V> implements C
      */
     public ValueCursor<V> getCursor()
     {
-        checkRaw();
-
         ValueCursor<V> cursor;
 
-        if ( isSubBtree )
+        // Check that the values are deserialized before doing anything
+        checkAndDeserialize();
+
+        if ( valueArray == null )
         {
             cursor = new ValueBtreeCursor();
         }
@@ -214,6 +172,7 @@ public class ValueHolder<V> implements C
         return cursor;
     }
 
+
     /**
      * A class that encapsulate the values into an array
      */
@@ -229,7 +188,7 @@ public class ValueHolder<V> implements C
         private ValueArrayCursor()
         {
             // Start at -1 to be positioned before the first element
-            currentPos = -1;
+            currentPos = BEFORE_FIRST;
         }
 
 
@@ -239,15 +198,7 @@ public class ValueHolder<V> implements C
         @Override
         public boolean hasNext()
         {
-            if ( valueArray == null )
-            {
-                // Load the array from the raw data
-                return false;
-            }
-            else
-            {
-                return currentPos < valueArray.length - 1;
-            }
+            return ( currentPos < valueArray.length - 1 ) && ( currentPos != AFTER_LAST );
         }
 
 
@@ -267,6 +218,8 @@ public class ValueHolder<V> implements C
 
                 if ( currentPos == valueArray.length )
                 {
+                    currentPos = AFTER_LAST;
+                    
                     // We have reached the end of the array
                     return null;
                 }
@@ -284,15 +237,7 @@ public class ValueHolder<V> implements C
         @Override
         public boolean hasPrev() throws EndOfFileExceededException, IOException
         {
-            if ( valueArray == null )
-            {
-                // Load the array from the raw data
-                return false;
-            }
-            else
-            {
-                return currentPos > 0;
-            }
+            return currentPos > 0 || currentPos == AFTER_LAST;
         }
 
 
@@ -311,7 +256,7 @@ public class ValueHolder<V> implements C
         @Override
         public void beforeFirst() throws IOException
         {
-            currentPos = -1;
+            currentPos = BEFORE_FIRST;
         }
 
 
@@ -321,7 +266,7 @@ public class ValueHolder<V> implements C
         @Override
         public void afterLast() throws IOException
         {
-            currentPos = valueArray.length;
+            currentPos = AFTER_LAST;
         }
 
 
@@ -338,9 +283,16 @@ public class ValueHolder<V> implements C
             }
             else
             {
-                currentPos--;
+                if ( currentPos == AFTER_LAST )
+                {
+                    currentPos = valueArray.length - 1;
+                }
+                else
+                {
+                    currentPos--;
+                }
 
-                if ( currentPos == -1 )
+                if ( currentPos == BEFORE_FIRST )
                 {
                     // We have reached the end of the array
                     return null;
@@ -359,14 +311,7 @@ public class ValueHolder<V> implements C
         @Override
         public int size()
         {
-            if ( valueArray != null )
-            {
-                return valueArray.length;
-            }
-            else
-            {
-                return 0;
-            }
+            return valueArray.length;
         }
     }
 
@@ -384,7 +329,7 @@ public class ValueHolder<V> implements C
          */
         private ValueBtreeCursor()
         {
-            // Start at -1 to be positionned before the first element
+            // Start at -1 to be positioned before the first element
             try
             {
                 if ( valueBtree != null )
@@ -418,13 +363,11 @@ public class ValueHolder<V> implements C
                 }
                 catch ( EndOfFileExceededException e )
                 {
-                    // TODO Auto-generated catch block
                     e.printStackTrace();
                     return false;
                 }
                 catch ( IOException e )
                 {
-                    // TODO Auto-generated catch block
                     e.printStackTrace();
                     return false;
                 }
@@ -443,13 +386,11 @@ public class ValueHolder<V> implements C
             }
             catch ( EndOfFileExceededException e )
             {
-                // TODO Auto-generated catch block
                 e.printStackTrace();
                 return null;
             }
             catch ( IOException e )
             {
-                // TODO Auto-generated catch block
                 e.printStackTrace();
                 return null;
             }
@@ -474,13 +415,11 @@ public class ValueHolder<V> implements C
                 }
                 catch ( EndOfFileExceededException e )
                 {
-                    // TODO Auto-generated catch block
                     e.printStackTrace();
                     return false;
                 }
                 catch ( IOException e )
                 {
-                    // TODO Auto-generated catch block
                     e.printStackTrace();
                     return false;
                 }
@@ -539,13 +478,11 @@ public class ValueHolder<V> implements C
             }
             catch ( EndOfFileExceededException e )
             {
-                // TODO Auto-generated catch block
                 e.printStackTrace();
                 return null;
             }
             catch ( IOException e )
             {
-                // TODO Auto-generated catch block
                 e.printStackTrace();
                 return null;
             }
@@ -558,61 +495,71 @@ public class ValueHolder<V> implements C
         @Override
         public int size()
         {
-            if ( valueBtree != null )
-            {
-                return ( int ) valueBtree.getNbElems();
-            }
-            else
-            {
-                return 0;
-            }
+            return ( int ) valueBtree.getNbElems();
         }
     }
 
 
     /**
-     * @return the raw representation of the value holder. 
+     * @return the raw representation of the value holder. The serialized value will not be the same
+     * if the values are stored in an array or in a btree. <br/>
+     * If they are stored in a BTree, the raw value will contain the offset of the btree, otherwise
+     * it will contain a byte[] which will contain each serialized value, prefixed by their length. 
+     * 
      */
-    public byte[] getRaw()
+    /* No qualifier*/ byte[] getRaw()
     {
-        if ( isRaw )
+        if ( isRawUpToDate )
         {
-            // We don't have to serialize the ValueHolder, it has not been changed 
+            // Just have to return the raw value
             return raw;
         }
+
+        if ( isSubBtree() )
+        {
+            // The values are stored into a subBtree, return the offset of this subBtree
+            long btreeOffset = valueBtree.getBtreeOffset();
+            raw = LongSerializer.serialize( btreeOffset );
+        }
         else
         {
-            // Ok, some values have been added/modified/removed, we have to serialize the ValueHolder
+            // Create as many byte[] as we have length and serialized values to store
             byte[][] valueBytes = new byte[valueArray.length * 2][];
             int length = 0;
             int pos = 0;
-
+    
+            // Process each value now
             for ( V value : valueArray )
             {
                 // Serialize the value
                 byte[] bytes = valueSerializer.serialize( value );
                 length += bytes.length;
-
+    
                 // Serialize the value's length
                 byte[] sizeBytes = IntSerializer.serialize( bytes.length );
                 length += sizeBytes.length;
-
+    
                 // And store the two byte[]
                 valueBytes[pos++] = sizeBytes;
                 valueBytes[pos++] = bytes;
             }
-
+    
+            // Last, not least, create a buffer large enough to contain all the created byte[],
+            // and copy all those byte[] into this buffer
             raw = new byte[length];
             pos = 0;
-
+    
             for ( byte[] bytes : valueBytes )
             {
                 System.arraycopy( bytes, 0, raw, pos, bytes.length );
                 pos += bytes.length;
             }
-
-            return raw;
         }
+        
+        // Update the flags
+        isRawUpToDate = true;
+
+        return raw;
     }
 
 
@@ -621,7 +568,7 @@ public class ValueHolder<V> implements C
      */
     public boolean isSubBtree()
     {
-        return isSubBtree;
+        return valueArray == null;
     }
 
 
@@ -630,7 +577,9 @@ public class ValueHolder<V> implements C
      */
     public int size()
     {
-        if ( isSubBtree )
+        checkAndDeserialize();
+
+        if ( valueArray == null )
         {
             return ( int ) valueBtree.getNbElems();
         }
@@ -661,8 +610,6 @@ public class ValueHolder<V> implements C
             try
             {
                 btree.getRecordManager().manage( valueBtree, true );
-                isSubBtree = true;
-                isRaw = false;
                 raw = null;
             }
             catch ( BTreeAlreadyManagedException e )
@@ -685,79 +632,61 @@ public class ValueHolder<V> implements C
     {
         valueBtree = subBtree;
         raw = null;
-        isRaw = false;
-        isSubBtree = true;
         valueArray = null;
+        isDeserialized = true;
+        isRawUpToDate = false;
     }
-
-
+    
+    
     /**
-     * Add a new value in the ValueHolder
-     * 
-     * @param value The added value
+     * Check that the values are stored as raw value
      */
-    public void add( V value )
+    private void checkAndDeserialize()
     {
-        checkRaw();
-
-        if ( !isSubBtree )
+        if ( !isDeserialized )
         {
-            // We have to check that we have reached the threshold or not
-            if ( valueArray.length + 1 > BTree.valueThresholdUp )
+            if ( valueArray == null )
             {
-                // Ok, transform the array into a btree
-                createSubTree();
-
-                try
-                {
-                    for ( V val : valueArray )
-                    {
-                        // Here, we should insert all the values in one shot then 
-                        // write the btree on disk only once.
-                        valueBtree.insert( val, null );
-                    }
-
-                    // We can delete the array now
-                    valueArray = null;
-
-                    // And inject the new value
-                    valueBtree.insert( value, null );
-                }
-                catch ( IOException e )
-                {
-                    // TODO Auto-generated catch block
-                    e.printStackTrace();
-                }
+                // the values are stored into a sub-btree. Read it now if it's not already done
+                deserializeSubBtree();
             }
             else
             {
-                // First check that the value is not already present in the ValueHolder
-                int pos = findPos( value );
-
-                if ( pos >= 0 )
-                {
-                    // The value exists : nothing to do
-                    return;
-                }
-
-                // Ok, we just have to insert the new element at the right position
-                // We transform the position to a positive value 
-                pos = -( pos + 1 );
-                // First, copy the array
-                V[] newValueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), valueArray.length + 1 );
-
-                System.arraycopy( valueArray, 0, newValueArray, 0, pos );
-                newValueArray[pos] = value;
-                System.arraycopy( valueArray, pos, newValueArray, pos + 1, valueArray.length - pos );
-
-                // And switch the arrays
-                valueArray = newValueArray;
+                // The values are stored into an array. Deserialize it now
+                deserializeArray();
             }
+
+            // Change the flag
+            isDeserialized = true;
         }
-        else
+    }
+    
+    /**
+     * Add the value in an array
+     */
+    private void addInArray( V value )
+    {
+        checkAndDeserialize();
+
+        // We have to check that we have reached the threshold or not
+        if ( valueArray.length + 1 > BTree.valueThresholdUp )
         {
+            // Ok, transform the array into a btree
+            createSubTree();
+
             try
             {
+                for ( V val : valueArray )
+                {
+                    // Here, we should insert all the values in one shot then 
+                    // write the btree on disk only once.
+                    valueBtree.insert( val, null );
+                }
+
+                // We can delete the array now
+                valueArray = null;
+
+                // And inject the new value
                 valueBtree.insert( value, null );
             }
             catch ( IOException e )
@@ -766,50 +695,49 @@ public class ValueHolder<V> implements C
                 e.printStackTrace();
             }
         }
-    }
-
-
-    /**
-     * Add a new value in the ValueHolder
-     * 
-     * @param value The added value
-     */
-    public void remove( V value )
-    {
-        checkRaw();
-
-        if ( !isSubBtree )
+        else
         {
             // First check that the value is not already present in the ValueHolder
             int pos = findPos( value );
 
-            if ( pos < 0 )
+            if ( pos >= 0 )
             {
-                // The value does not exists : nothing to do
+                // The value exists : nothing to do
                 return;
             }
 
-            // Ok, we just have to delete the new element at the right position
+            // Ok, we just have to insert the new element at the right position
+            // We transform the position to a positive value 
+            pos = -( pos + 1 );
             // First, copy the array
-            V[] newValueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), valueArray.length - 1 );
+            V[] newValueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), valueArray.length + 1 );
 
             System.arraycopy( valueArray, 0, newValueArray, 0, pos );
-            System.arraycopy( valueArray, pos + 1, newValueArray, pos, valueArray.length - pos - 1 );
+            newValueArray[pos] = value;
+            System.arraycopy( valueArray, pos, newValueArray, pos + 1, valueArray.length - pos );
 
             // And switch the arrays
             valueArray = newValueArray;
         }
-        else
+    }
+    
+
+    /**
+     * Add the value in the subBTree
+     */
+    private void addInBtree( V value )
+    {
+        // First check that we have a loaded BTree
+        checkAndDeserialize();
+        
+        try
         {
-            try
-            {
-                valueBtree.delete( value );
-            }
-            catch ( IOException e )
-            {
-                // TODO Auto-generated catch block
-                e.printStackTrace();
-            }
+            valueBtree.insert( value, null );
+        }
+        catch ( IOException e )
+        {
+            // TODO Auto-generated catch block
+            e.printStackTrace();
         }
     }
 
@@ -819,15 +747,76 @@ public class ValueHolder<V> implements C
      * 
      * @param value The added value
      */
-    public boolean contains( V value )
+    public void add( V value )
+    {
+        if ( valueArray != null )
+        {
+            addInArray( value );
+        }
+        else
+        {
+            addInBtree( value );
+        }
+        
+        // The raw value is not anymore up to date with the content
+        isRawUpToDate = false;
+        raw = null;
+    }
+    
+    
+    /**
+     * Remove a value from an array
+     */
+    private void removeFromArray( V value )
+    {
+        checkAndDeserialize();
+
+        // First check that the value is not already present in the ValueHolder
+        int pos = findPos( value );
+
+        if ( pos < 0 )
+        {
+            // The value does not exists : nothing to do
+            return;
+        }
+
+        // Ok, we just have to delete the new element at the right position
+        // First, copy the array
+        V[] newValueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), valueArray.length - 1 );
+
+        System.arraycopy( valueArray, 0, newValueArray, 0, pos );
+        System.arraycopy( valueArray, pos + 1, newValueArray, pos, valueArray.length - pos - 1 );
+
+        // And switch the arrays
+        valueArray = newValueArray;
+    }
+
+    
+    /**
+     * Remove the value from a sub btree
+     */
+    private void removeFromBtree( V value )
     {
-        checkRaw();
+        // First check that we have a loaded BTree
+        checkAndDeserialize();
 
-        if ( isSubBtree )
+        if ( btreeContains( value ) )
         {
             try
             {
-                return valueBtree.hasKey( value );
+                if ( valueBtree.getNbElems() - 1 < BTree.valueThresholdLow )
+                {
+                    int nbValues = (int)(valueBtree.getNbElems() - 1);
+                        
+                    // We have to switch to an Array of values
+                    valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), nbValues );
+    
+                    // Now copy all the value sbut the one we have removed
+                }
+                else
+                {
+                    valueBtree.delete( value );
+                }
             }
             catch ( IOException e )
             {
@@ -835,18 +824,84 @@ public class ValueHolder<V> implements C
                 e.printStackTrace();
             }
         }
+    }
+
+    /**
+     * Add a new value in the ValueHolder
+     * 
+     * @param value The added value
+     */
+    public void remove( V value )
+    {
+        if ( valueArray != null )
+        {
+            removeFromArray( value );
+        }
         else
         {
-            if ( valueArray.length == 0 )
-            {
-                return false;
-            }
+            removeFromBtree( value );
+        }
 
-            // Do a search using dichotomy
-            return findPos( value ) >= 0;
+        // The raw value is not anymore up to date wth the content
+        isRawUpToDate = false;
+        raw = null;
+    }
+    
+    
+    /**
+     * Check if the array of values contains a given value
+     */
+    private boolean arrayContains( V value )
+    {
+        // First, deserialize the value if it's still a byte[]
+        checkAndDeserialize();
+        
+        if ( valueArray.length == 0 )
+        {
+            return false;
         }
 
-        return true;
+        // Do a search using dichotomy
+        return findPos( value ) >= 0;
+    }
+    
+    
+    /**
+     * Check if the subBtree contains a given value
+     */
+    private boolean btreeContains( V value )
+    {
+        // First, deserialize the value if it's still a byte[]
+        checkAndDeserialize();
+        
+        try
+        {
+            return valueBtree.hasKey( value );
+        }
+        catch ( IOException e )
+        {
+            // TODO Auto-generated catch block
+            e.printStackTrace();
+            return false;
+        }
+    }
+
+
+    /**
+     * Add a new value in the ValueHolder
+     * 
+     * @param value The added value
+     */
+    public boolean contains( V value )
+    {
+        if ( valueArray == null )
+        {
+            return btreeContains( value );
+        }
+        else
+        {
+            return arrayContains( value );
+        }
     }
 
 
@@ -984,67 +1039,73 @@ public class ValueHolder<V> implements C
     {
         ValueHolder<V> copy = ( ValueHolder<V> ) super.clone();
 
-        //copy the valueArray if it's not null
+        // copy the valueArray if it's not null
         // We don't clone the BTree, as we will create new revisions when 
-        //modifying it
-        if ( ( !isSubBtree ) && ( valueArray != null ) )
+        // modifying it
+        if ( valueArray != null )
         {
             copy.valueArray = ( V[] ) Array.newInstance( valueSerializer.getType(), valueArray.length );
             System.arraycopy( valueArray, 0, copy.valueArray, 0, valueArray.length );
         }
+        
+        // Also clone the raw value if its up to date
+        if ( isRawUpToDate )
+        {
+            copy.raw = new byte[raw.length];
+            System.arraycopy( raw,  0,  copy.raw, 0, raw.length );
+        }
 
         return copy;
     }
 
 
     /**
-     * Check if we haven't yet deserialized the values, and if so, do it
+     * Deserialize the values stored in an array
      */
-    private void checkRaw()
+    private void deserializeArray()
     {
-        if ( isRaw )
+        // We haven't yet deserialized the values. Let's do it now. The values are
+        // necessarily stored in an array at this point
+        int index = 0;
+        int pos = 0;
+
+        while ( pos < raw.length )
         {
-            // We haven't yet deserialized the values. Let's do it now
-            if ( isSubBtree )
+            try
             {
-                // This is a sub BTree, we have to read the tree from the offsets
+                int size = IntSerializer.deserialize( raw, pos );
+                pos += 4;
 
+                V value = valueSerializer.fromBytes( raw, pos );
+                pos += size;
+                valueArray[index++] = value;
             }
-            else
+            catch ( IOException e )
             {
-                // We have to deserialize the array of values
-                int index = 0;
-                int pos = 0;
-
-                while ( pos < raw.length )
-                {
-                    try
-                    {
-                        int size = IntSerializer.deserialize( raw, pos );
-                        pos += 4;
-
-                        V value = valueSerializer.fromBytes( raw, pos );
-                        pos += size;
-                        valueArray[index++] = value;
-                    }
-                    catch ( IOException e )
-                    {
-                        e.printStackTrace();
-                    }
-                }
+                e.printStackTrace();
             }
-
-            isRaw = false;
         }
     }
 
 
     /**
+     * Deserialize the values stored in a sub-btree
+     */
+    private void deserializeSubBtree()
+    {
+        // Get the sub-btree offset
+        long offset = LongSerializer.deserialize( raw );
+        
+        // and reload the sub btree
+        valueBtree = btree.getRecordManager().loadDupsBTree( offset );
+    }
+
+    /**
      * @return The sub-btree offset
      */
     /* No qualifier */long getOffset()
     {
-        if ( isSubBtree )
+        if ( valueArray == null )
         {
             return valueBtree.getBtreeOffset();
         }
@@ -1064,13 +1125,13 @@ public class ValueHolder<V> implements C
 
         sb.append( "ValueHolder[" ).append( valueSerializer.getClass().getSimpleName() );
 
-        if ( isRaw )
+        if ( !isDeserialized )
         {
             sb.append( ", isRaw[" ).append( raw.length ).append( "]" );
         }
         else
         {
-            if ( isSubBtree )
+            if ( valueArray == null )
             {
                 sb.append( ", SubBTree" );
             }

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTree.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTree.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTree.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/BTree.java Wed Nov 27 07:03:46 2013
@@ -31,7 +31,6 @@ import java.lang.reflect.Type;
 import java.nio.ByteBuffer;
 import java.nio.channels.FileChannel;
 import java.util.Comparator;
-import java.util.LinkedList;
 import java.util.concurrent.ConcurrentLinkedQueue;
 import java.util.concurrent.locks.ReentrantLock;
 
@@ -934,9 +933,7 @@ public class BTree<K, V> implements Clos
         Transaction<K, V> transaction = beginReadTransaction();
 
         // Fetch the root page for this revision
-        LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
-
-        TupleCursor<K, V> cursor = rootPage.browse( transaction, stack );
+        TupleCursor<K, V> cursor = rootPage.browse( transaction, new ParentPos[32], 0 );
 
         return cursor;
     }
@@ -958,8 +955,7 @@ public class BTree<K, V> implements Clos
         Page<K, V> revisionRootPage = getRootPage( revision );
 
         // And get the cursor
-        LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
-        TupleCursor<K, V> cursor = revisionRootPage.browse( transaction, stack );
+        TupleCursor<K, V> cursor = revisionRootPage.browse( transaction, new ParentPos[32], 0 );
 
         return cursor;
     }
@@ -978,7 +974,7 @@ public class BTree<K, V> implements Clos
         Transaction<K, V> transaction = beginReadTransaction();
 
         // Fetch the root page for this revision
-        TupleCursor<K, V> cursor = rootPage.browse( key, transaction, new LinkedList<ParentPos<K, V>>() );
+        TupleCursor<K, V> cursor = rootPage.browse( key, transaction, new ParentPos[32], 0 );
 
         return cursor;
     }
@@ -1002,8 +998,7 @@ public class BTree<K, V> implements Clos
         Page<K, V> revisionRootPage = getRootPage( revision );
 
         // And get the cursor
-        LinkedList<ParentPos<K, V>> stack = new LinkedList<ParentPos<K, V>>();
-        TupleCursor<K, V> cursor = revisionRootPage.browse( key, transaction, stack );
+        TupleCursor<K, V> cursor = revisionRootPage.browse( key, transaction, new ParentPos[32], 0 );
 
         return cursor;
     }

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InternalUtil.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InternalUtil.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InternalUtil.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/InternalUtil.java Wed Nov 27 07:03:46 2013
@@ -23,6 +23,8 @@ package org.apache.directory.mavibot.btr
 
 import java.io.IOException;
 
+import org.apache.directory.mavibot.btree.TupleCursor;
+
 
 /**
  * A class containing utility methods to be used internally. 
@@ -52,11 +54,22 @@ import java.io.IOException;
         if ( parentPos.dupsContainer == null )
         {
             Leaf leaf = ( Leaf ) ( parentPos.page );
-            MultipleMemoryHolder mvHolder = ( MultipleMemoryHolder ) leaf.values[parentPos.pos];
-            if( !mvHolder.isSingleValue() )
+            
+            // Deal with BEFORE_FIRST and AFTER_LAST cases
+            if ( ( parentPos.pos == TupleCursor.BEFORE_FIRST ) || ( parentPos.pos == TupleCursor.AFTER_LAST ) )
             {
-                BTree dupsContainer = ( BTree ) mvHolder.getValue( btree );
-                parentPos.dupsContainer = dupsContainer;
+                // Nothing to do in this case
+                return;
+            }
+            else
+            {
+                MultipleMemoryHolder mvHolder = ( MultipleMemoryHolder ) leaf.values[parentPos.pos];
+                
+                if ( !mvHolder.isSingleValue() )
+                {
+                    BTree dupsContainer = ( BTree ) mvHolder.getValue( btree );
+                    parentPos.dupsContainer = dupsContainer;
+                }
             }
         }
     }

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Leaf.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Leaf.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Leaf.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Leaf.java Wed Nov 27 07:03:46 2013
@@ -24,7 +24,6 @@ import static org.apache.directory.mavib
 
 import java.io.IOException;
 import java.lang.reflect.Array;
-import java.util.LinkedList;
 
 import org.apache.directory.mavibot.btree.Tuple;
 import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
@@ -670,7 +669,7 @@ import org.apache.directory.mavibot.btre
     /**
      * {@inheritDoc}
      */
-    public TupleCursorImpl<K, V> browse( K key, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+    public TupleCursorImpl<K, V> browse( K key, Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
     {
         int pos = findPos( key );
         TupleCursorImpl<K, V> cursor = null;
@@ -682,9 +681,9 @@ import org.apache.directory.mavibot.btre
             // The first element has been found. Create the cursor
             ParentPos<K, V> parentPos = new ParentPos<K, V>( this, index );
             setDupsContainer( parentPos, btree );
-            stack.push( parentPos );
+            stack[depth] = parentPos;
 
-            cursor = new TupleCursorImpl<K, V>( btree, transaction, stack );
+            cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
         }
         else
         {
@@ -693,16 +692,17 @@ import org.apache.directory.mavibot.btre
             {
                 ParentPos<K, V> parentPos = new ParentPos<K, V>( this, pos );
                 setDupsContainer( parentPos, btree );
-                stack.push( parentPos );
+                stack[depth] = parentPos;
 
-                cursor = new TupleCursorImpl<K, V>( btree, transaction, stack );
+                cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
             }
             else
             {
                 // Not found : return a null cursor
-                stack.push( new ParentPos<K, V>( null, -1 ) );
+                ParentPos<K, V> parentPos = new ParentPos<K, V>( null, -1 );
+                stack[depth] = parentPos;
 
-                return new TupleCursorImpl<K, V>( btree, transaction, stack );
+                return new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
             }
         }
 
@@ -713,7 +713,7 @@ import org.apache.directory.mavibot.btre
     /**
      * {@inheritDoc}
      */
-    public TupleCursorImpl<K, V> browse( Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+    public TupleCursorImpl<K, V> browse( Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
     {
         int pos = 0;
         TupleCursorImpl<K, V> cursor = null;
@@ -721,9 +721,9 @@ import org.apache.directory.mavibot.btre
         if ( nbElems == 0 )
         {
             // The tree is empty, it's the root, we have nothing to return
-            stack.push( new ParentPos<K, V>( null, -1 ) );
+            stack[depth] = new ParentPos<K, V>( null, -1 );
 
-            return new TupleCursorImpl<K, V>( btree, transaction, stack );
+            return new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
         }
         else
         {
@@ -732,9 +732,9 @@ import org.apache.directory.mavibot.btre
 
             setDupsContainer( parentPos, btree );
 
-            stack.push( parentPos );
+            stack[depth] = parentPos;
 
-            cursor = new TupleCursorImpl<K, V>( btree, transaction, stack );
+            cursor = new TupleCursorImpl<K, V>( btree, transaction, stack, depth );
         }
 
         return cursor;

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Node.java Wed Nov 27 07:03:46 2013
@@ -22,7 +22,6 @@ package org.apache.directory.mavibot.btr
 
 import java.io.IOException;
 import java.lang.reflect.Array;
-import java.util.LinkedList;
 import java.util.List;
 
 import org.apache.directory.mavibot.btree.Tuple;
@@ -943,7 +942,7 @@ import org.apache.directory.mavibot.btre
     /**
      * {@inheritDoc}
      */
-    public TupleCursorImpl<K, V> browse( K key, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+    public TupleCursorImpl<K, V> browse( K key, Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
         throws IOException
     {
         int pos = findPos( key );
@@ -954,21 +953,25 @@ import org.apache.directory.mavibot.btre
         }
 
         // We first stack the current page
-        stack.push( new ParentPos<K, V>( this, pos ) );
+        stack[depth++] = new ParentPos<K, V>( this, pos );
+        
+        Page<K, V> page = children[pos].getValue( btree );
 
-        return children[pos].getValue( btree ).browse( key, transaction, stack );
+        return page.browse( key, transaction, stack, depth );
     }
 
 
     /**
      * {@inheritDoc}
      */
-    public TupleCursorImpl<K, V> browse( Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+    public TupleCursorImpl<K, V> browse( Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
         throws IOException
     {
-        stack.push( new ParentPos<K, V>( this, 0 ) );
+        stack[depth++] = new ParentPos<K, V>( this, 0 );
+        
+        Page<K, V> page = children[0].getValue( btree );
 
-        return children[0].getValue( btree ).browse( transaction, stack );
+        return page.browse( transaction, stack, depth );
     }
 
 

Modified: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Page.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Page.java?rev=1545944&r1=1545943&r2=1545944&view=diff
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Page.java (original)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/memory/Page.java Wed Nov 27 07:03:46 2013
@@ -131,10 +131,11 @@ import org.apache.directory.mavibot.btre
      * @param key The key we are looking for.
      * @param transaction The started transaction for this operation
      * @param stack The stack of parents we go through to get to this page
+     * @param depth The current depth
      * @return A Cursor to browse the next elements
      * @throws IOException If we have an error while trying to access the page
      */
-    TupleCursorImpl<K, V> browse( K key, Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+    TupleCursorImpl<K, V> browse( K key, Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
         throws IOException;
 
 
@@ -146,7 +147,7 @@ import org.apache.directory.mavibot.btre
      * @return A Cursor to browse the next elements
      * @throws IOException If we have an error while trying to access the page
      */
-    TupleCursorImpl<K, V> browse( Transaction<K, V> transaction, LinkedList<ParentPos<K, V>> stack )
+    TupleCursorImpl<K, V> browse( Transaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
         throws EndOfFileExceededException, IOException;
 
 



Mime
View raw message