directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kayyag...@apache.org
Subject svn commit: r1510115 [9/13] - in /directory/mavibot/trunk: ./ mavibot/ mavibot/src/main/java/org/apache/directory/ mavibot/src/main/java/org/apache/directory/mavibot/ mavibot/src/main/java/org/apache/directory/mavibot/btree/ mavibot/src/main/java/org/a...
Date Sun, 04 Aug 2013 09:22:58 GMT
Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/util/Strings.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/util/Strings.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/util/Strings.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/util/Strings.java Sun Aug  4 09:22:56 2013
@@ -0,0 +1,540 @@
+/*
+ *  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.util;
+
+
+import java.io.UnsupportedEncodingException;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+
+/**
+ * Various string manipulation methods that are more efficient then chaining
+ * string operations: all is done in the same buffer without creating a bunch of
+ * string objects.
+ *
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+public final class Strings
+{
+    /** Hex chars */
+    private static final byte[] HEX_CHAR = new byte[]
+        { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };
+
+    /** A empty byte array */
+    public static final byte[] EMPTY_BYTES = new byte[0];
+
+
+    /**
+     * Helper function that dump an array of bytes in hex form
+     *
+     * @param buffer The bytes array to dump
+     * @return A string representation of the array of bytes
+     */
+    public static String dumpBytes( byte[] buffer )
+    {
+        if ( buffer == null )
+        {
+            return "";
+        }
+
+        StringBuffer sb = new StringBuffer();
+
+        for ( byte b : buffer )
+        {
+            sb.append( "0x" ).append( ( char ) ( HEX_CHAR[( b & 0x00F0 ) >> 4] ) ).append(
+                ( char ) ( HEX_CHAR[b & 0x000F] ) ).append( " " );
+        }
+
+        return sb.toString();
+    }
+
+
+    /**
+     * Helper function that dump a byte in hex form
+     *
+     * @param octet The byte to dump
+     * @return A string representation of the byte
+     */
+    public static String dumpByte( byte octet )
+    {
+        return new String( new byte[]
+            { '0', 'x', HEX_CHAR[( octet & 0x00F0 ) >> 4], HEX_CHAR[octet & 0x000F] } );
+    }
+
+
+    /**
+     * Helper function that returns a char from an hex
+     *
+     * @param hex The hex to dump
+     * @return A char representation of the hex
+     */
+    public static char dumpHex( byte hex )
+    {
+        return ( char ) HEX_CHAR[hex & 0x000F];
+    }
+
+
+    /**
+     * Helper function that dump an array of bytes in hex pair form,
+     * without '0x' and space chars
+     *
+     * @param buffer The bytes array to dump
+     * @return A string representation of the array of bytes
+     */
+    public static String dumpHexPairs( byte[] buffer )
+    {
+        if ( buffer == null )
+        {
+            return "";
+        }
+
+        char[] str = new char[buffer.length << 1];
+
+        int pos = 0;
+
+        for ( byte b : buffer )
+        {
+            str[pos++] = ( char ) ( HEX_CHAR[( b & 0x00F0 ) >> 4] );
+            str[pos++] = ( char ) ( HEX_CHAR[b & 0x000F] );
+        }
+
+        return new String( str );
+    }
+
+
+    /**
+     * Gets a hex string from byte array.
+     *
+     * @param res the byte array
+     * @return the hex string representing the binary values in the array
+     */
+    public static String toHexString( byte[] res )
+    {
+        StringBuffer buf = new StringBuffer( res.length << 1 );
+
+        for ( byte b : res )
+        {
+            String digit = Integer.toHexString( 0xFF & b );
+
+            if ( digit.length() == 1 )
+            {
+                digit = '0' + digit;
+            }
+
+            buf.append( digit );
+        }
+
+        return buf.toString().toUpperCase();
+    }
+
+
+    /**
+     * Get byte array from hex string
+     *
+     * @param hexString the hex string to convert to a byte array
+     * @return the byte form of the hex string.
+     */
+    public static byte[] toByteArray( String hexString )
+    {
+        int arrLength = hexString.length() >> 1;
+        byte[] buf = new byte[arrLength];
+
+        for ( int ii = 0; ii < arrLength; ii++ )
+        {
+            int index = ii << 1;
+
+            String digit = hexString.substring( index, index + 2 );
+            buf[ii] = ( byte ) Integer.parseInt( digit, 16 );
+        }
+
+        return buf;
+    }
+
+    private static final byte[] UTF8 = new byte[]
+        { 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A,
+            0x0B, 0x0C, 0x0D, 0x0E, 0x0F, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1A, 0x1B, 0x1C,
+            0x1D, 0x1E, 0x1F, 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2A, 0x2B, 0x2C, 0x2D, 0x2E,
+            0x2F, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F, 0x40,
+            0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4A, 0x4B, 0x4C, 0x4D, 0x4E, 0x4F, 0x50, 0x51, 0x52,
+            0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, 0x5A, 0x5B, 0x5C, 0x5D, 0x5E, 0x5F, 0x60, 0x61, 0x62, 0x63, 0x64,
+            0x65, 0x66, 0x67, 0x68, 0x69, 0x6A, 0x6B, 0x6C, 0x6D, 0x6E, 0x6F, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76,
+            0x77, 0x78, 0x79, 0x7A, 0x7B, 0x7C, 0x7D, 0x7E, 0x7F };
+
+
+    /**
+     * Return an UTF-8 encoded String
+     *
+     * @param bytes The byte array to be transformed to a String
+     * @return A String.
+     */
+    public static String utf8ToString( byte[] bytes )
+    {
+        if ( bytes == null )
+        {
+            return "";
+        }
+
+        char[] chars = new char[bytes.length];
+        int pos = 0;
+
+        try
+        {
+            for ( byte b : bytes )
+            {
+                chars[pos++] = ( char ) UTF8[b];
+            }
+        }
+        catch ( ArrayIndexOutOfBoundsException aioobe )
+        {
+            try
+            {
+                return new String( bytes, "UTF-8" );
+            }
+            catch ( UnsupportedEncodingException uee )
+            {
+                // if this happens something is really strange
+                throw new RuntimeException( uee );
+            }
+        }
+
+        return new String( chars );
+    }
+
+
+    /**
+     * Return an UTF-8 encoded String
+     *
+     * @param bytes The byte array to be transformed to a String
+     * @param length The length of the byte array to be converted
+     * @return A String.
+     */
+    public static String utf8ToString( byte[] bytes, int length )
+    {
+        if ( bytes == null )
+        {
+            return "";
+        }
+
+        try
+        {
+            return new String( bytes, 0, length, "UTF-8" );
+        }
+        catch ( UnsupportedEncodingException uee )
+        {
+            // if this happens something is really strange
+            throw new RuntimeException( uee );
+        }
+    }
+
+
+    /**
+     * Return an UTF-8 encoded String
+     *
+     * @param bytes  The byte array to be transformed to a String
+     * @param start the starting position in the byte array
+     * @param length The length of the byte array to be converted
+     * @return A String.
+     */
+    public static String utf8ToString( byte[] bytes, int start, int length )
+    {
+        if ( bytes == null )
+        {
+            return "";
+        }
+
+        try
+        {
+            return new String( bytes, start, length, "UTF-8" );
+        }
+        catch ( UnsupportedEncodingException uee )
+        {
+            // if this happens something is really strange
+            throw new RuntimeException( uee );
+        }
+    }
+
+
+    /**
+     * <p>
+     * Checks if a String is empty ("") or null.
+     * </p>
+     *
+     * <pre>
+     *  StringUtils.isEmpty(null)      = true
+     *  StringUtils.isEmpty(&quot;&quot;)        = true
+     *  StringUtils.isEmpty(&quot; &quot;)       = false
+     *  StringUtils.isEmpty(&quot;bob&quot;)     = false
+     *  StringUtils.isEmpty(&quot;  bob  &quot;) = false
+     * </pre>
+     *
+     * <p>
+     * NOTE: This method changed in Lang version 2.0. It no longer trims the
+     * String. That functionality is available in isBlank().
+     * </p>
+     *
+     * @param str the String to check, may be null
+     * @return <code>true</code> if the String is empty or null
+     */
+    public static boolean isEmpty( String str )
+    {
+        return ( str == null ) || ( str.length() == 0 );
+    }
+
+
+    /**
+     * Checks if a bytes array is empty or null.
+     *
+     * @param bytes The bytes array to check, may be null
+     * @return <code>true</code> if the bytes array is empty or null
+     */
+    public static boolean isEmpty( byte[] bytes )
+    {
+        return ( bytes == null ) || ( bytes.length == 0 );
+    }
+
+
+    /**
+     * Return UTF-8 encoded byte[] representation of a String
+     *
+     * @param string The string to be transformed to a byte array
+     * @return The transformed byte array
+     */
+    public static byte[] getBytesUtf8( String string )
+    {
+        if ( string == null )
+        {
+            return EMPTY_BYTES;
+        }
+
+        try
+        {
+            return string.getBytes( "UTF-8" );
+        }
+        catch ( UnsupportedEncodingException uee )
+        {
+            // if this happens something is really strange
+            throw new RuntimeException( uee );
+        }
+    }
+
+
+    /**
+     * When the string to convert to bytes is pure ascii, this is a faster 
+     * method than the getBytesUtf8. Otherwise, it's slower.
+     * 
+     * @param string The string to convert to byte[]
+     * @return The bytes 
+     */
+    public static byte[] getBytesUtf8Ascii( String string )
+    {
+        if ( string == null )
+        {
+            return new byte[0];
+        }
+
+        try
+        {
+            try
+            {
+                char[] chars = string.toCharArray();
+                byte[] bytes = new byte[chars.length];
+                int pos = 0;
+
+                for ( char c : chars )
+                {
+                    bytes[pos++] = UTF8[c];
+                }
+
+                return bytes;
+            }
+            catch ( ArrayIndexOutOfBoundsException aioobe )
+            {
+                return string.getBytes( "UTF-8" );
+            }
+        }
+        catch ( UnsupportedEncodingException uee )
+        {
+            // if this happens something is really strange
+            throw new RuntimeException( uee );
+        }
+    }
+
+
+    /**
+     * Utility method that return a String representation of a list
+     *
+     * @param list The list to transform to a string
+     * @return A csv string
+     */
+    public static String listToString( List<?> list )
+    {
+        if ( ( list == null ) || ( list.size() == 0 ) )
+        {
+            return "";
+        }
+
+        StringBuilder sb = new StringBuilder();
+        boolean isFirst = true;
+
+        for ( Object elem : list )
+        {
+            if ( isFirst )
+            {
+                isFirst = false;
+            }
+            else
+            {
+                sb.append( ", " );
+            }
+
+            sb.append( elem );
+        }
+
+        return sb.toString();
+    }
+
+
+    /**
+     * Utility method that return a String representation of a set
+     *
+     * @param set The set to transform to a string
+     * @return A csv string
+     */
+    public static String setToString( Set<?> set )
+    {
+        if ( ( set == null ) || ( set.size() == 0 ) )
+        {
+            return "";
+        }
+
+        StringBuilder sb = new StringBuilder();
+        boolean isFirst = true;
+
+        for ( Object elem : set )
+        {
+            if ( isFirst )
+            {
+                isFirst = false;
+            }
+            else
+            {
+                sb.append( ", " );
+            }
+
+            sb.append( elem );
+        }
+
+        return sb.toString();
+    }
+
+
+    /**
+     * Utility method that return a String representation of a list
+     *
+     * @param list The list to transform to a string
+     * @param tabs The tabs to add in ffront of the elements
+     * @return A csv string
+     */
+    public static String listToString( List<?> list, String tabs )
+    {
+        if ( ( list == null ) || ( list.size() == 0 ) )
+        {
+            return "";
+        }
+
+        StringBuffer sb = new StringBuffer();
+
+        for ( Object elem : list )
+        {
+            sb.append( tabs );
+            sb.append( elem );
+            sb.append( '\n' );
+        }
+
+        return sb.toString();
+    }
+
+
+    /**
+     * Utility method that return a String representation of a map. The elements
+     * will be represented as "key = value"
+     *
+     * @param map The map to transform to a string
+     * @return A csv string
+     */
+    public static String mapToString( Map<?, ?> map )
+    {
+        if ( ( map == null ) || ( map.size() == 0 ) )
+        {
+            return "";
+        }
+
+        StringBuffer sb = new StringBuffer();
+        boolean isFirst = true;
+
+        for ( Map.Entry<?, ?> entry : map.entrySet() )
+        {
+            if ( isFirst )
+            {
+                isFirst = false;
+            }
+            else
+            {
+                sb.append( ", " );
+            }
+
+            sb.append( entry.getKey() );
+            sb.append( " = '" ).append( entry.getValue() ).append( "'" );
+        }
+
+        return sb.toString();
+    }
+
+
+    /**
+     * Utility method that return a String representation of a map. The elements
+     * will be represented as "key = value"
+     *
+     * @param map The map to transform to a string
+     * @param tabs The tabs to add in ffront of the elements
+     * @return A csv string
+     */
+    public static String mapToString( Map<?, ?> map, String tabs )
+    {
+        if ( ( map == null ) || ( map.size() == 0 ) )
+        {
+            return "";
+        }
+
+        StringBuffer sb = new StringBuffer();
+
+        for ( Map.Entry<?, ?> entry : map.entrySet() )
+        {
+            sb.append( tabs );
+            sb.append( entry.getKey() );
+
+            sb.append( " = '" ).append( entry.getValue().toString() ).append( "'\n" );
+        }
+
+        return sb.toString();
+    }
+}

Added: directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/util/TupleReaderWriter.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/util/TupleReaderWriter.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/util/TupleReaderWriter.java (added)
+++ directory/mavibot/trunk/mavibot/src/main/java/org/apache/directory/mavibot/btree/util/TupleReaderWriter.java Sun Aug  4 09:22:56 2013
@@ -0,0 +1,41 @@
+/*
+ *   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.util;
+
+
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+
+import org.apache.directory.mavibot.btree.Tuple;
+
+
+/**
+ * TODO TupleReaderWriter.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public interface TupleReaderWriter<K, V>
+{
+    Tuple<K, V> readTuple( DataInputStream in );
+
+
+    void writeTuple( Tuple<K, V> t, DataOutputStream out ) throws IOException;
+}

Added: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BTreeBuilderTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BTreeBuilderTest.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BTreeBuilderTest.java (added)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BTreeBuilderTest.java Sun Aug  4 09:22:56 2013
@@ -0,0 +1,80 @@
+/*
+ *   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;
+
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.directory.mavibot.btree.BTree;
+import org.apache.directory.mavibot.btree.BTreeBuilder;
+import org.apache.directory.mavibot.btree.Cursor;
+import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.serializer.IntSerializer;
+import org.junit.Test;
+import static org.junit.Assert.*;
+
+
+/**
+ * Test cases for BTreeBuilder.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class BTreeBuilderTest
+{
+    @Test
+    public void testIntegerTree() throws IOException
+    {
+        List<Tuple<Integer, Integer>> sortedTuple = new ArrayList<Tuple<Integer, Integer>>();
+        for ( int i = 1; i < 8; i++ )
+        {
+            Tuple<Integer, Integer> t = new Tuple<Integer, Integer>( i, i );
+            sortedTuple.add( t );
+        }
+
+        IntSerializer ser = new IntSerializer();
+        BTreeBuilder<Integer, Integer> bb = new BTreeBuilder<Integer, Integer>( "master", 4, ser, ser );
+
+        // contains 1, 2, 3, 4, 5, 6, 7
+        BTree btree = bb.build( sortedTuple.iterator() );
+
+        assertEquals( 1, btree.rootPage.getNbElems() );
+        
+        assertEquals( 7, btree.rootPage.findRightMost().getKey() );
+        
+        assertEquals( 1, btree.rootPage.findLeftMost().getKey() );
+        
+        Cursor<Integer, Integer> cursor = btree.browse();
+        int i = 0;
+        while ( cursor.hasNext() )
+        {
+            Tuple<Integer, Integer> expected = sortedTuple.get( i++ );
+            Tuple<Integer, Integer> actual = cursor.next();
+            assertEquals( expected.getKey(), actual.getKey() );
+            assertEquals( expected.getValue(), actual.getValue() );
+        }
+        
+        cursor.close();
+        btree.close();
+    }
+
+}

Added: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BTreeConfigurationTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BTreeConfigurationTest.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BTreeConfigurationTest.java (added)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BTreeConfigurationTest.java Sun Aug  4 09:22:56 2013
@@ -0,0 +1,242 @@
+/*
+ *  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;
+
+
+import static org.junit.Assert.assertNotNull;
+
+import java.io.File;
+import java.io.IOException;
+
+import org.apache.directory.mavibot.btree.BTree;
+import org.apache.directory.mavibot.btree.BTreeConfiguration;
+import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
+import org.apache.directory.mavibot.btree.serializer.IntSerializer;
+import org.apache.directory.mavibot.btree.serializer.StringSerializer;
+import org.junit.Test;
+
+
+/**
+ * Test the creation of a BTree with a configuration.
+ * 
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+public class BTreeConfigurationTest
+{
+    // Some values to inject in a btree
+    private static int[] sortedValues = new int[]
+        {
+            0, 1, 2, 4, 5, 6, 8, 9, 11, 12,
+            13, 14, 16, 19, 21, 22, 23, 25, 26, 28,
+            30, 31, 32, 34, 36, 37, 38, 39, 41, 42,
+            44, 45, 47, 50, 52, 53, 54, 55, 56, 58,
+            59, 60, 63, 64, 67, 68, 70, 72, 73, 74,
+            76, 77, 79, 80, 81, 82, 85, 88, 89, 90,
+            92, 93, 95, 97, 98, 100, 101, 102, 103, 104,
+            105, 106, 107, 109, 110, 111, 112, 117, 118, 120,
+            121, 128, 129, 130, 131, 132, 135, 136, 137, 138,
+            139, 140, 141, 142, 143, 146, 147, 148, 149, 150,
+            152, 154, 156, 160, 161, 162, 163, 165, 167, 168,
+            169, 171, 173, 174, 175, 176, 177, 178, 179, 180,
+            181, 182, 183, 189, 190, 193, 194, 195, 199, 200,
+            202, 203, 205, 206, 207, 208, 209, 210, 212, 215,
+            216, 217, 219, 220, 222, 223, 224, 225, 226, 227,
+            228, 230, 231, 235, 236, 238, 239, 241, 242, 243,
+            245, 246, 247, 249, 250, 251, 252, 254, 256, 257,
+            258, 259, 261, 262, 263, 264, 266, 268, 272, 273,
+            274, 276, 277, 278, 279, 282, 283, 286, 289, 290,
+            292, 293, 294, 296, 298, 299, 300, 301, 303, 305,
+            308, 310, 316, 317, 318, 319, 322, 323, 324, 326,
+            327, 329, 331, 333, 334, 335, 336, 337, 338, 339,
+            340, 341, 346, 347, 348, 349, 350, 351, 352, 353,
+            355, 356, 357, 358, 359, 361, 365, 366, 373, 374,
+            375, 379, 380, 381, 382, 384, 385, 387, 388, 389,
+            390, 392, 393, 395, 396, 397, 398, 399, 400, 401,
+            404, 405, 406, 407, 410, 411, 412, 416, 417, 418,
+            420, 421, 422, 424, 426, 427, 428, 430, 431, 432,
+            433, 436, 439, 441, 443, 444, 445, 446, 447, 448,
+            449, 450, 451, 452, 453, 454, 455, 456, 458, 459,
+            464, 466, 469, 470, 471, 472, 475, 477, 478, 482,
+            483, 484, 485, 486, 488, 490, 491, 492, 493, 495,
+            496, 497, 500, 502, 503, 504, 505, 506, 507, 509,
+            510, 514, 516, 518, 520, 521, 523, 524, 526, 527,
+            528, 529, 530, 532, 533, 535, 538, 539, 540, 542,
+            543, 544, 546, 547, 549, 550, 551, 553, 554, 558,
+            559, 561, 563, 564, 566, 567, 568, 569, 570, 571,
+            572, 576, 577, 578, 580, 582, 583, 586, 588, 589,
+            590, 592, 593, 596, 597, 598, 599, 600, 601, 604,
+            605, 606, 607, 609, 610, 613, 615, 617, 618, 619,
+            620, 621, 626, 627, 628, 631, 632, 633, 635, 636,
+            637, 638, 639, 640, 641, 643, 645, 647, 648, 649,
+            650, 651, 652, 653, 655, 656, 658, 659, 660, 662,
+            666, 669, 673, 674, 675, 676, 677, 678, 680, 681,
+            682, 683, 685, 686, 687, 688, 689, 690, 691, 692,
+            693, 694, 696, 698, 699, 700, 701, 705, 708, 709,
+            711, 713, 714, 715, 719, 720, 723, 725, 726, 727,
+            728, 731, 732, 733, 734, 735, 736, 739, 740, 743,
+            744, 745, 746, 747, 749, 750, 752, 753, 762, 763,
+            765, 766, 768, 770, 772, 773, 774, 776, 777, 779,
+            782, 784, 785, 788, 790, 791, 793, 794, 795, 798,
+            799, 800, 801, 803, 804, 805, 808, 810, 812, 813,
+            814, 816, 818, 821, 822, 823, 824, 827, 828, 829,
+            831, 832, 833, 834, 835, 837, 838, 839, 840, 843,
+            846, 847, 849, 852, 853, 854, 856, 857, 859, 860,
+            863, 864, 865, 866, 867, 868, 869, 872, 873, 877,
+            880, 881, 882, 883, 887, 888, 889, 890, 891, 894,
+            895, 897, 898, 899, 902, 904, 905, 907, 908, 910,
+            911, 912, 915, 916, 917, 918, 919, 923, 925, 926,
+            927, 928, 929, 930, 932, 935, 936, 937, 938, 939,
+            944, 945, 947, 952, 953, 954, 955, 956, 957, 958,
+            960, 967, 970, 971, 972, 974, 975, 976, 978, 979,
+            980, 981, 983, 984, 985, 987, 988, 989, 991, 995
+    };
+
+
+    /**
+     * Test the creation of a in-memory BTree using the BTreeConfiguration.
+     */
+    @Test
+    public void testConfigurationBasic() throws IOException, KeyNotFoundException
+    {
+        BTreeConfiguration<Integer, String> config = new BTreeConfiguration<Integer, String>();
+        config.setName( "basic" );
+        config.setPageSize( 32 );
+        config.setSerializers( new IntSerializer(), new StringSerializer() );
+
+        try
+        {
+            // Create the BTree
+            BTree<Integer, String> btree = new BTree<Integer, String>( config );
+
+            // Inject the values
+            for ( int value : sortedValues )
+            {
+                String strValue = "V" + value;
+
+                btree.insert( value, strValue );
+            }
+
+            // Check that the tree contains all the values
+            for ( int key : sortedValues )
+            {
+                String value = btree.get( key );
+
+                assertNotNull( value );
+            }
+
+            btree.close();
+        }
+        finally
+        {
+            // Erase the mavibot file now
+            File mavibotFile = new File( "", "mavibot" );
+
+            if ( mavibotFile.exists() )
+            {
+                mavibotFile.delete();
+            }
+
+            // Erase the journal too
+            File mavibotJournal = new File( "", "mavibot.log" );
+
+            if ( mavibotJournal.exists() )
+            {
+                mavibotJournal.delete();
+            }
+        }
+    }
+
+
+    /**
+     * Test the creation of a BTree using the BTreeConfiguration, flushing the 
+     * tree on disk, then reloading it in another BTree.
+     */
+    @Test
+    public void testConfigurationFlushReload() throws IOException, KeyNotFoundException
+    {
+        // Create a temporary file
+        File file = File.createTempFile( "testFlush", "data" );
+        file.deleteOnExit();
+        String parent = file.getParent();
+
+        try
+        {
+            BTreeConfiguration<Integer, String> config = new BTreeConfiguration<Integer, String>();
+            config.setPageSize( 32 );
+            config.setSerializers( new IntSerializer(), new StringSerializer() );
+
+            config.setFilePath( parent );
+            config.setName( "mavibot" );
+
+            // Create the BTree
+            BTree<Integer, String> btree = new BTree<Integer, String>( config );
+
+            // Inject the values
+            for ( int value : sortedValues )
+            {
+                String strValue = "V" + value;
+
+                btree.insert( value, strValue );
+            }
+
+            // Check that the tree contains all the values
+            for ( int key : sortedValues )
+            {
+                String value = btree.get( key );
+
+                assertNotNull( value );
+            }
+
+            // Flush the data
+            btree.close();
+
+            // Now, create a new BTree using the same configuration
+            BTree<Integer, String> btreeCopy = new BTree<Integer, String>( config );
+
+            // Check that the tree contains all the values
+            for ( int key : sortedValues )
+            {
+                String value = btreeCopy.get( key );
+
+                assertNotNull( value );
+            }
+
+            btreeCopy.close();
+        }
+        finally
+        {
+            // Erase the mavibot file now
+            File mavibotFile = new File( parent, "mavibot.db" );
+
+            if ( mavibotFile.exists() )
+            {
+                mavibotFile.delete();
+            }
+
+            // Erase the journal too
+            File mavibotJournal = new File( parent, "mavibot.db.log" );
+
+            if ( mavibotJournal.exists() )
+            {
+                mavibotJournal.delete();
+            }
+        }
+    }
+}

Added: 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=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BTreeDuplicateKeyTest.java (added)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BTreeDuplicateKeyTest.java Sun Aug  4 09:22:56 2013
@@ -0,0 +1,701 @@
+/*
+ *   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;
+
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.io.IOException;
+import java.util.NoSuchElementException;
+import java.util.UUID;
+
+import org.apache.directory.mavibot.btree.BTree;
+import org.apache.directory.mavibot.btree.BTreeConfiguration;
+import org.apache.directory.mavibot.btree.Cursor;
+import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.serializer.IntSerializer;
+import org.apache.directory.mavibot.btree.serializer.StringSerializer;
+import org.junit.Test;
+
+
+/**
+ * TODO BTreeDuplicateKeyTest.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class BTreeDuplicateKeyTest
+{
+    @Test
+    public void testInsertNullValue() throws IOException
+    {
+        IntSerializer serializer = new IntSerializer();
+
+        BTree<Integer, Integer> btree = new BTree<Integer, Integer>( "master", serializer, serializer );
+        btree.init();
+
+        btree.insert( 1, null );
+
+        Cursor<Integer, Integer> cursor = btree.browse();
+        assertTrue( cursor.hasNext() );
+
+        Tuple<Integer, Integer> t = cursor.next();
+
+        assertEquals( Integer.valueOf( 1 ), t.getKey() );
+        assertEquals( null, t.getValue() );
+
+        cursor.close();
+    }
+
+
+    @Test
+    public void testBrowseEmptyTree() throws IOException
+    {
+        IntSerializer serializer = new IntSerializer();
+
+        BTree<Integer, Integer> btree = new BTree<Integer, Integer>( "master", serializer, serializer );
+        btree.init();
+
+        Cursor<Integer, Integer> cursor = btree.browse();
+        assertFalse( cursor.hasNext() );
+        assertFalse( cursor.hasPrev() );
+
+        try
+        {
+            cursor.next();
+            fail( "Should not reach here" );
+        }
+        catch ( NoSuchElementException e )
+        {
+            assertTrue( true );
+        }
+
+        try
+        {
+            cursor.prev();
+            fail( "Should not reach here" );
+        }
+        catch ( NoSuchElementException e )
+        {
+            assertTrue( true );
+        }
+
+        cursor.close();
+    }
+
+
+    @Test
+    public void testDuplicateKey() throws IOException
+    {
+        IntSerializer serializer = new IntSerializer();
+
+        BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+        config.setAllowDuplicates( true );
+        config.setName( "master" );
+        config.setSerializers( serializer, serializer );
+        BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
+
+        btree.insert( 1, 1 );
+        btree.insert( 1, 2 );
+
+        Cursor<Integer, Integer> cursor = btree.browse();
+        assertTrue( cursor.hasNext() );
+
+        Tuple<Integer, Integer> t = cursor.next();
+
+        assertEquals( Integer.valueOf( 1 ), t.getKey() );
+        assertEquals( Integer.valueOf( 1 ), t.getValue() );
+
+        assertTrue( cursor.hasNext() );
+
+        t = cursor.next();
+
+        assertEquals( Integer.valueOf( 1 ), t.getKey() );
+        assertEquals( Integer.valueOf( 2 ), t.getValue() );
+
+        assertFalse( cursor.hasNext() );
+
+        // test backward move
+        assertTrue( cursor.hasPrev() );
+
+        t = cursor.prev();
+
+        assertEquals( Integer.valueOf( 1 ), t.getKey() );
+        assertEquals( Integer.valueOf( 2 ), t.getValue() );
+
+        assertTrue( cursor.hasPrev() );
+
+        t = cursor.prev();
+
+        assertEquals( Integer.valueOf( 1 ), t.getKey() );
+        assertEquals( Integer.valueOf( 1 ), t.getValue() );
+
+        assertFalse( cursor.hasPrev() );
+
+        // again forward
+        assertTrue( cursor.hasNext() );
+
+        t = cursor.next();
+
+        assertEquals( Integer.valueOf( 1 ), t.getKey() );
+        assertEquals( Integer.valueOf( 1 ), t.getValue() );
+
+        assertTrue( cursor.hasNext() );
+
+        t = cursor.next();
+
+        assertEquals( Integer.valueOf( 1 ), t.getKey() );
+        assertEquals( Integer.valueOf( 2 ), t.getValue() );
+
+        assertFalse( cursor.hasNext() );
+
+        cursor.close();
+    }
+
+
+    @Test
+    public void testGetDuplicateKey() throws Exception
+    {
+        IntSerializer serializer = new IntSerializer();
+
+        BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+        config.setAllowDuplicates( true );
+        config.setName( "master" );
+        config.setSerializers( serializer, serializer );
+        BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
+
+        Integer retVal = btree.insert( 1, 1 );
+        assertNull( retVal );
+
+        retVal = btree.insert( 1, 2 );
+        assertNull( retVal );
+
+        // check the return value when an existing value is added again
+        retVal = btree.insert( 1, 2 );
+        assertEquals( Integer.valueOf( 2 ), retVal );
+
+        assertEquals( Integer.valueOf( 1 ), btree.get( 1 ) );
+        assertTrue( btree.contains( 1, 1 ) );
+        assertTrue( btree.contains( 1, 2 ) );
+
+        assertFalse( btree.contains( 1, 0 ) );
+        assertFalse( btree.contains( 0, 1 ) );
+        assertFalse( btree.contains( 0, 0 ) );
+        assertFalse( btree.contains( null, 0 ) );
+        assertFalse( btree.contains( 0, null ) );
+        assertFalse( btree.contains( null, null ) );
+    }
+
+
+    @Test
+    public void testRemoveDuplicateKey() throws Exception
+    {
+        IntSerializer serializer = new IntSerializer();
+
+        BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+        config.setAllowDuplicates( true );
+        config.setName( "master" );
+        config.setSerializers( serializer, serializer );
+        BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
+
+        btree.insert( 1, 1 );
+        btree.insert( 1, 2 );
+
+        assertEquals( 2l, btree.getNbElems() );
+
+        Tuple<Integer, Integer> t = btree.delete( 1, 1 );
+        assertEquals( Integer.valueOf( 1 ), t.getKey() );
+        assertEquals( Integer.valueOf( 1 ), t.getValue() );
+
+        assertEquals( 1l, btree.getNbElems() );
+
+        t = btree.delete( 1, 2 );
+        assertEquals( Integer.valueOf( 1 ), t.getKey() );
+        assertEquals( Integer.valueOf( 2 ), t.getValue() );
+
+        assertEquals( 0l, btree.getNbElems() );
+
+        t = btree.delete( 1, 2 );
+        assertNull( t );
+    }
+
+
+    @Test
+    public void testFullPage() throws Exception
+    {
+        StringSerializer serializer = new StringSerializer();
+
+        BTreeConfiguration<String, String> config = new BTreeConfiguration<String, String>();
+        config.setAllowDuplicates( true );
+        config.setName( "master" );
+        config.setSerializers( serializer, serializer );
+        BTree<String, String> btree = new BTree<String, String>( config );
+
+        int i = 7;
+        for ( char ch = 'a'; ch <= 'z'; ch++ )
+        {
+            for( int k = 0; k< i; k++ )
+            {
+                btree.insert( String.valueOf( ch ), UUID.randomUUID().toString() );
+            }
+        }
+
+        Cursor<String, String> cursor = btree.browse();
+
+        char ch = 'a';
+        int k = 0;
+        
+        while ( cursor.hasNext() )
+        {
+            Tuple<String, String> t = cursor.next();
+            assertEquals( String.valueOf( ch ), t.getKey() );
+            k++;
+            
+            if( ( k % i ) == 0 )
+            {
+                ch++;
+            }
+        }
+        
+        assertEquals( ( 'z' + 1 ) , ch );
+        
+        ch = 'z';
+        
+        while(cursor.hasPrev())
+        {
+            Tuple<String, String> t = cursor.prev();
+            assertEquals( String.valueOf( ch ), t.getKey() );
+            k--;
+            
+            if( ( k % i ) == 0 )
+            {
+                ch--;
+            }
+        }
+
+        assertEquals( ( 'a' - 1 ) , ch );
+        cursor.close();
+    }
+
+    @Test
+    public void testMoveFirst() throws Exception
+    {
+        StringSerializer serializer = new StringSerializer();
+
+        BTreeConfiguration<String, String> config = new BTreeConfiguration<String, String>();
+        config.setAllowDuplicates( true );
+        config.setName( "master" );
+        config.setSerializers( serializer, serializer );
+        BTree<String, String> btree = new BTree<String, String>( config );
+
+        for ( char ch = 'a'; ch <= 'z'; ch++ )
+        {
+            btree.insert( String.valueOf( ch ), UUID.randomUUID().toString() );
+        }
+
+        // add one more value for 'a'
+        btree.insert( String.valueOf( 'a' ), UUID.randomUUID().toString() );
+        
+        Cursor<String, String> cursor = btree.browseFrom( "c" );
+
+        int i = 0;
+        while( cursor.hasNext() )
+        {
+            assertNotNull( cursor.next() );
+            i++;
+        }
+        assertEquals( 24, i );
+        
+        // now move the cursor first
+        cursor.beforeFirst();
+        assertTrue( cursor.hasNext() );
+        assertEquals( "c", cursor.next().getKey() );
+        
+        i = 0;
+        while( cursor.hasNext() )
+        {
+            assertNotNull( cursor.next() );
+            i++;
+        }
+        assertEquals( 23, i );
+        
+        cursor.close();
+        
+        cursor = btree.browse();
+        
+        i = 0;
+        while( cursor.hasNext() )
+        {
+            assertNotNull( cursor.next() );
+            i++;
+        }
+        assertEquals( 27, i );
+        
+        // now move the cursor first
+        cursor.beforeFirst();
+        assertTrue( cursor.hasNext() );
+        assertEquals( "a", cursor.next().getKey() );
+        
+        i = 0;
+        while( cursor.hasNext() )
+        {
+            assertNotNull( cursor.next() );
+            i++;
+        }
+        assertEquals( 26, i );
+    }
+
+
+    @Test(expected = NoSuchElementException.class)
+    public void testMoveLast() throws Exception
+    {
+        StringSerializer serializer = new StringSerializer();
+
+        BTreeConfiguration<String, String> config = new BTreeConfiguration<String, String>();
+        config.setAllowDuplicates( true );
+        config.setName( "master" );
+        config.setSerializers( serializer, serializer );
+        BTree<String, String> btree = new BTree<String, String>( config );
+
+        for ( char ch = 'a'; ch <= 'z'; ch++ )
+        {
+            btree.insert( String.valueOf( ch ), UUID.randomUUID().toString() );
+        }
+        
+        btree.insert( String.valueOf( 'z' ), UUID.randomUUID().toString() );
+        
+        Cursor<String, String> cursor = btree.browseFrom( "c" );
+        cursor.afterLast();
+        
+        assertFalse( cursor.hasNext() );
+        assertTrue( cursor.hasPrev() );
+        assertEquals( "z", cursor.prev().getKey() );
+        assertEquals( "z", cursor.prev().getKey() );
+        assertEquals( "y", cursor.prev().getKey() );
+        
+        cursor.beforeFirst();
+        assertEquals( "c", cursor.next().getKey() );
+
+        cursor.afterLast();
+        assertFalse( cursor.hasNext() );
+        // make sure it throws NoSuchElementException
+        cursor.next();
+    }
+
+    
+    @Test(expected = NoSuchElementException.class)
+    public void testMoveToNextPrevNonDuplicateKey() throws Exception
+    {
+        StringSerializer serializer = new StringSerializer();
+
+        BTreeConfiguration<String, String> config = new BTreeConfiguration<String, String>();
+        config.setAllowDuplicates( true );
+        config.setName( "master" );
+        config.setSerializers( serializer, serializer );
+        BTree<String, String> btree = new BTree<String, String>( config );
+
+        int i = 7;
+        for ( char ch = 'a'; ch <= 'z'; ch++ )
+        {
+            for( int k = 0; k< i; k++ )
+            {
+                btree.insert( String.valueOf( ch ), String.valueOf( k ) );
+            }
+        }
+        
+        Cursor<String, String> cursor = btree.browse();
+
+        assertTrue( cursor.hasNext() );
+        assertFalse( cursor.hasPrev() );
+        for(int k =0; k < 2; k++)
+        {
+            assertEquals( "a", cursor.next().getKey() );
+        }
+        
+        assertEquals( "a", cursor.next().getKey() );
+        
+        cursor.moveToNextNonDuplicateKey();
+        
+        assertEquals( "b", cursor.next().getKey() );
+        
+        for ( char ch = 'b'; ch < 'z'; ch++ )
+        {
+            assertEquals( String.valueOf( ch ), cursor.next().getKey() );
+            cursor.moveToNextNonDuplicateKey();
+            char t = ch;
+            assertEquals( String.valueOf( ++t ), cursor.next().getKey() );
+        }
+
+        for(int k =0; k < i-1; k++)
+        {
+            assertEquals( "z", cursor.next().getKey() );
+        }
+
+        assertFalse( cursor.hasNext() );
+        assertTrue( cursor.hasPrev() );
+        Tuple<String, String> tuple = cursor.prev();
+        assertEquals( "z", tuple.getKey() );
+        assertEquals( "6", tuple.getValue() );
+        
+        for ( char ch = 'z'; ch > 'a'; ch-- )
+        {
+            char t = ch;
+            t--;
+            
+            assertEquals( String.valueOf( ch ), cursor.prev().getKey() );
+            
+            cursor.moveToPrevNonDuplicateKey();
+
+            tuple = cursor.prev();
+            assertEquals( String.valueOf( t ), tuple.getKey() );
+        }
+        
+        for(int k =5; k >=0; k--)
+        {
+            tuple = cursor.prev();
+            assertEquals( "a", tuple.getKey() );
+            assertEquals( String.valueOf( k ), tuple.getValue() );
+        }
+
+        assertTrue( cursor.hasNext() );
+        assertFalse( cursor.hasPrev() );
+        tuple = cursor.next();
+        assertEquals( "a", tuple.getKey() );
+        assertEquals( "0", tuple.getValue() );
+
+        cursor.close();
+        
+        cursor = btree.browseFrom("y");
+        cursor.moveToNextNonDuplicateKey();
+        assertTrue( cursor.hasPrev() );
+        tuple = cursor.prev();
+        assertEquals( "y", tuple.getKey() );
+        assertEquals( "6", tuple.getValue() );
+        cursor.close();
+        
+        cursor = btree.browse();
+        cursor.beforeFirst();
+        assertFalse( cursor.hasPrev() );
+        // make sure it throws NoSuchElementException
+        cursor.prev();
+    }
+    
+    
+    /**
+     * Test for moving between two leaves. When moveToNextNonDuplicateKey is called
+     * and cursor is on the last element of the current leaf.
+     *
+     * @throws Exception
+     */
+    @Test
+    public void testMoveToNextAndPrevWithPageBoundaries() throws Exception
+    {
+        IntSerializer serializer = new IntSerializer();
+
+        BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+        config.setAllowDuplicates( true );
+        config.setName( "master" );
+        config.setPageSize( 4 );
+        config.setSerializers( serializer, serializer );
+        BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
+
+        int i = 7;
+        for ( int k=0; k < i; k++ )
+        {
+            btree.insert( k, k );
+        }
+        
+        // 3 is the last element of the first leaf
+        Cursor<Integer, Integer> cursor = btree.browseFrom(3);
+        cursor.moveToNextNonDuplicateKey();
+
+        assertTrue( cursor.hasNext() );
+        Tuple<Integer, Integer> tuple = cursor.next();
+        assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
+        assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
+        cursor.close();
+
+        cursor = btree.browseFrom(3);
+        cursor.moveToNextNonDuplicateKey();
+
+        assertTrue( cursor.hasPrev() );
+        tuple = cursor.prev();
+        assertEquals( Integer.valueOf( 3 ), tuple.getKey() );
+        assertEquals( Integer.valueOf( 3 ), tuple.getValue() );
+        cursor.close();
+        
+        // 4 is the first element of the second leaf
+        cursor = btree.browseFrom(4);
+        cursor.moveToPrevNonDuplicateKey();
+
+        assertTrue( cursor.hasPrev() );
+        tuple = cursor.prev();
+        assertEquals( Integer.valueOf( 3 ), tuple.getKey() );
+        assertEquals( Integer.valueOf( 3 ), tuple.getValue() );
+        
+        // the below assertion won't work cause of the index position
+        // issue when prev() and next() are called subsequently (in any order) 
+//        assertTrue( cursor.hasNext() );
+//        tuple = cursor.next();
+//        assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
+//        assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
+        cursor.close();
+        
+        // test the extremes of the BTree instead of that of leaves
+        cursor = btree.browseFrom(6);
+        cursor.moveToNextNonDuplicateKey();
+        assertFalse( cursor.hasNext() );
+        assertTrue( cursor.hasPrev() );
+        tuple = cursor.prev();
+        assertEquals( Integer.valueOf( 6 ), tuple.getKey() );
+        assertEquals( Integer.valueOf( 6 ), tuple.getValue() );
+        cursor.close();
+        
+        cursor = btree.browse();
+        cursor.moveToPrevNonDuplicateKey();
+        assertTrue( cursor.hasNext() );
+        assertFalse( cursor.hasPrev() );
+        tuple = cursor.next();
+        assertEquals( Integer.valueOf( 0 ), tuple.getKey() );
+        assertEquals( Integer.valueOf( 0 ), tuple.getValue() );
+        cursor.close();
+    }
+    
+    
+    @Test
+    public void testNextAfterPrev() throws Exception
+    {
+        IntSerializer serializer = new IntSerializer();
+
+        BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+        config.setAllowDuplicates( true );
+        config.setName( "master" );
+        config.setPageSize( 4 );
+        config.setSerializers( serializer, serializer );
+        BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
+
+        int i = 7;
+        for ( int k=0; k < i; k++ )
+        {
+            btree.insert( k, k );
+        }
+        
+        // 3 is the last element of the first leaf
+        Cursor<Integer, Integer> cursor = btree.browseFrom(4);
+
+        assertTrue( cursor.hasNext() );
+        Tuple<Integer, Integer> tuple = cursor.next();
+        assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
+        assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
+        
+        assertTrue( cursor.hasPrev() );
+        tuple = cursor.prev();
+        assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
+        assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
+
+        assertTrue( cursor.hasNext() );
+        tuple = cursor.next();
+        assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
+        assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
+        cursor.close();
+
+    }
+    
+    
+    /**
+     * Test for moving after a key and traversing backwards.
+     *
+     * @throws Exception
+     */
+    @Test
+    public void testMoveToNextAndTraverseBackward() throws Exception
+    {
+        IntSerializer serializer = new IntSerializer();
+
+        BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+        config.setAllowDuplicates( true );
+        config.setName( "master" );
+        config.setPageSize( 8 );
+        config.setSerializers( serializer, serializer );
+        BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
+
+        int i = 5;
+        for ( int k=0; k < i; k++ )
+        {
+            btree.insert( k, k );
+        }
+        
+        // 4 is the last element in the tree
+        Cursor<Integer, Integer> cursor = btree.browseFrom(4);
+        cursor.moveToNextNonDuplicateKey();
+        
+        int currentKey = 4;
+        while( cursor.hasPrev() )
+        {
+        	assertEquals( Integer.valueOf( currentKey ), cursor.prev().getKey() );
+        	currentKey--;
+        }
+        
+        cursor.close();
+    }
+    
+    
+    /**
+     * Test for moving after a key and traversing backwards.
+     *
+     * @throws Exception
+     */
+    @Test
+    public void testMoveToPrevAndTraverseForward() throws Exception
+    {
+        IntSerializer serializer = new IntSerializer();
+
+        BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
+        config.setAllowDuplicates( true );
+        config.setName( "master" );
+        config.setPageSize( 8 );
+        config.setSerializers( serializer, serializer );
+        BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
+
+        int i = 5;
+        for ( int k=0; k < i; k++ )
+        {
+            btree.insert( k, k );
+        }
+        
+        // 4 is the last element in the tree
+        Cursor<Integer, Integer> cursor = btree.browseFrom(0);
+        cursor.moveToPrevNonDuplicateKey();
+        
+        int currentKey = 0;
+        while( cursor.hasNext() )
+        {
+        	assertEquals( Integer.valueOf( currentKey ), cursor.next().getKey() );
+        	currentKey++;
+        }
+        
+        cursor.close();
+    }
+
+}

Added: directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BTreeFlushTest.java
URL: http://svn.apache.org/viewvc/directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BTreeFlushTest.java?rev=1510115&view=auto
==============================================================================
--- directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BTreeFlushTest.java (added)
+++ directory/mavibot/trunk/mavibot/src/test/java/org/apache/directory/mavibot/btree/BTreeFlushTest.java Sun Aug  4 09:22:56 2013
@@ -0,0 +1,296 @@
+/*
+ *  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;
+
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import java.io.File;
+import java.io.IOException;
+import java.util.Random;
+import java.util.Set;
+
+import org.apache.directory.mavibot.btree.BTree;
+import org.apache.directory.mavibot.btree.Cursor;
+import org.apache.directory.mavibot.btree.Tuple;
+import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
+import org.apache.directory.mavibot.btree.serializer.IntSerializer;
+import org.apache.directory.mavibot.btree.serializer.LongSerializer;
+import org.apache.directory.mavibot.btree.serializer.StringSerializer;
+import org.junit.Test;
+
+
+/**
+ * A unit test class for BTree flush() operation
+ * 
+ * @author <a href="mailto:labs@labs.apache.org">Mavibot labs Project</a>
+ */
+public class BTreeFlushTest
+{
+    // Some values to inject in a btree
+    private static int[] sortedValues = new int[]
+        {
+            0, 1, 2, 4, 5, 6, 8, 9, 11, 12,
+            13, 14, 16, 19, 21, 22, 23, 25, 26, 28,
+            30, 31, 32, 34, 36, 37, 38, 39, 41, 42,
+            44, 45, 47, 50, 52, 53, 54, 55, 56, 58,
+            59, 60, 63, 64, 67, 68, 70, 72, 73, 74,
+            76, 77, 79, 80, 81, 82, 85, 88, 89, 90,
+            92, 93, 95, 97, 98, 100, 101, 102, 103, 104,
+            105, 106, 107, 109, 110, 111, 112, 117, 118, 120,
+            121, 128, 129, 130, 131, 132, 135, 136, 137, 138,
+            139, 140, 141, 142, 143, 146, 147, 148, 149, 150,
+            152, 154, 156, 160, 161, 162, 163, 165, 167, 168,
+            169, 171, 173, 174, 175, 176, 177, 178, 179, 180,
+            181, 182, 183, 189, 190, 193, 194, 195, 199, 200,
+            202, 203, 205, 206, 207, 208, 209, 210, 212, 215,
+            216, 217, 219, 220, 222, 223, 224, 225, 226, 227,
+            228, 230, 231, 235, 236, 238, 239, 241, 242, 243,
+            245, 246, 247, 249, 250, 251, 252, 254, 256, 257,
+            258, 259, 261, 262, 263, 264, 266, 268, 272, 273,
+            274, 276, 277, 278, 279, 282, 283, 286, 289, 290,
+            292, 293, 294, 296, 298, 299, 300, 301, 303, 305,
+            308, 310, 316, 317, 318, 319, 322, 323, 324, 326,
+            327, 329, 331, 333, 334, 335, 336, 337, 338, 339,
+            340, 341, 346, 347, 348, 349, 350, 351, 352, 353,
+            355, 356, 357, 358, 359, 361, 365, 366, 373, 374,
+            375, 379, 380, 381, 382, 384, 385, 387, 388, 389,
+            390, 392, 393, 395, 396, 397, 398, 399, 400, 401,
+            404, 405, 406, 407, 410, 411, 412, 416, 417, 418,
+            420, 421, 422, 424, 426, 427, 428, 430, 431, 432,
+            433, 436, 439, 441, 443, 444, 445, 446, 447, 448,
+            449, 450, 451, 452, 453, 454, 455, 456, 458, 459,
+            464, 466, 469, 470, 471, 472, 475, 477, 478, 482,
+            483, 484, 485, 486, 488, 490, 491, 492, 493, 495,
+            496, 497, 500, 502, 503, 504, 505, 506, 507, 509,
+            510, 514, 516, 518, 520, 521, 523, 524, 526, 527,
+            528, 529, 530, 532, 533, 535, 538, 539, 540, 542,
+            543, 544, 546, 547, 549, 550, 551, 553, 554, 558,
+            559, 561, 563, 564, 566, 567, 568, 569, 570, 571,
+            572, 576, 577, 578, 580, 582, 583, 586, 588, 589,
+            590, 592, 593, 596, 597, 598, 599, 600, 601, 604,
+            605, 606, 607, 609, 610, 613, 615, 617, 618, 619,
+            620, 621, 626, 627, 628, 631, 632, 633, 635, 636,
+            637, 638, 639, 640, 641, 643, 645, 647, 648, 649,
+            650, 651, 652, 653, 655, 656, 658, 659, 660, 662,
+            666, 669, 673, 674, 675, 676, 677, 678, 680, 681,
+            682, 683, 685, 686, 687, 688, 689, 690, 691, 692,
+            693, 694, 696, 698, 699, 700, 701, 705, 708, 709,
+            711, 713, 714, 715, 719, 720, 723, 725, 726, 727,
+            728, 731, 732, 733, 734, 735, 736, 739, 740, 743,
+            744, 745, 746, 747, 749, 750, 752, 753, 762, 763,
+            765, 766, 768, 770, 772, 773, 774, 776, 777, 779,
+            782, 784, 785, 788, 790, 791, 793, 794, 795, 798,
+            799, 800, 801, 803, 804, 805, 808, 810, 812, 813,
+            814, 816, 818, 821, 822, 823, 824, 827, 828, 829,
+            831, 832, 833, 834, 835, 837, 838, 839, 840, 843,
+            846, 847, 849, 852, 853, 854, 856, 857, 859, 860,
+            863, 864, 865, 866, 867, 868, 869, 872, 873, 877,
+            880, 881, 882, 883, 887, 888, 889, 890, 891, 894,
+            895, 897, 898, 899, 902, 904, 905, 907, 908, 910,
+            911, 912, 915, 916, 917, 918, 919, 923, 925, 926,
+            927, 928, 929, 930, 932, 935, 936, 937, 938, 939,
+            944, 945, 947, 952, 953, 954, 955, 956, 957, 958,
+            960, 967, 970, 971, 972, 974, 975, 976, 978, 979,
+            980, 981, 983, 984, 985, 987, 988, 989, 991, 995
+    };
+
+
+    private String create100KElementsFile() throws IOException
+    {
+        Random random = new Random( System.nanoTime() );
+
+        int nbError = 0;
+
+        long l1 = System.currentTimeMillis();
+        int n = 0;
+        long delta = l1;
+        int nbElems = 100000;
+
+        BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
+        btree.setPageSize( 32 );
+
+        for ( int i = 0; i < nbElems; i++ )
+        {
+            Long key = ( long ) random.nextLong();
+            String value = Long.toString( key );
+
+            try
+            {
+                btree.insert( key, value );
+            }
+            catch ( Exception e )
+            {
+                e.printStackTrace();
+                System.out.println( btree );
+                System.out.println( "Error while adding " + value );
+                nbError++;
+
+                return null;
+            }
+
+            if ( i % 10000 == 0 )
+            {
+                if ( n > 0 )
+                {
+                    long t0 = System.currentTimeMillis();
+                    System.out.println( "Written " + i + " elements in : " + ( t0 - delta ) + "ms" );
+                    delta = t0;
+                }
+
+                n++;
+            }
+        }
+
+        long l2 = System.currentTimeMillis();
+
+        System.out.println( "Delta : " + ( l2 - l1 ) + ", nbError = " + nbError
+            + ", Nb insertion per second : " + ( ( nbElems ) / ( l2 - l1 ) ) * 1000 );
+
+        // Now, flush the btree
+
+        File tempFile = File.createTempFile( "mavibot", ".tmp" );
+        tempFile.deleteOnExit();
+
+        long t0 = System.currentTimeMillis();
+
+        btree.flush( tempFile );
+
+        long t1 = System.currentTimeMillis();
+
+        System.out.println( "Time to flush 100 000 elements : " + ( t1 - t0 ) + "ms" );
+        btree.close();
+
+        return tempFile.getCanonicalPath();
+    }
+
+
+    /**
+     * Checks the created BTree contains the expected values
+     */
+    private boolean checkTreeLong( Set<Long> expected, BTree<Long, String> btree ) throws IOException
+    {
+        // We loop on all the expected value to see if they have correctly been inserted
+        // into the btree
+        for ( Long key : expected )
+        {
+            try
+            {
+                btree.get( key );
+            }
+            catch ( KeyNotFoundException knfe )
+            {
+                return false;
+            }
+        }
+
+        return true;
+    }
+
+
+    /**
+     * Test the browse method going backward
+     * @throws Exception
+     */
+    @Test
+    public void testFlushBTree() throws Exception
+    {
+        // Create a BTree with pages containing 8 elements
+        // Create the file, it will be deleted on exit
+        File tempFile = File.createTempFile( "testFlush", null );
+        String path = tempFile.getParent();
+        tempFile.delete();
+
+        BTree<Integer, String> btree = new BTree<Integer, String>( "test", path, new IntSerializer(), new StringSerializer() );
+        btree.setPageSize( 8 );
+        
+        File journal = btree.getJournal();
+        File data = btree.getFile();
+        
+        try
+        {
+            // Inject the values
+            for ( int value : sortedValues )
+            {
+                String strValue = "V" + value;
+
+                btree.insert( value, strValue );
+            }
+
+            // The journal must be full
+            assertTrue( journal.length() > 0 );
+
+            // Now, flush the btree
+            btree.flush();
+
+            // The journal must be empty
+            assertEquals( 0, journal.length() );
+
+            // Load the data into a new tree
+            BTree<Integer, String> btreeLoaded = new BTree<Integer, String>( "test", path, new IntSerializer(),
+                new StringSerializer() );
+            btree.setPageSize( 8 );
+
+            Cursor<Integer, String> cursor1 = btree.browse();
+            Cursor<Integer, String> cursor2 = btree.browse();
+
+            while ( cursor1.hasNext() )
+            {
+                assertTrue( cursor2.hasNext() );
+
+                Tuple<Integer, String> tuple1 = cursor1.next();
+                Tuple<Integer, String> tuple2 = cursor2.next();
+
+                assertEquals( tuple1.getKey(), tuple2.getKey() );
+                assertEquals( tuple1.getValue(), tuple2.getValue() );
+            }
+
+            assertFalse( cursor2.hasNext() );
+
+            btree.close();
+            btreeLoaded.close();
+        }
+        finally
+        {
+            data.delete();
+            journal.delete();
+        }
+    }
+
+
+    /**
+     * Test the insertion of 5 million elements in a BTree
+     * @throws Exception
+     */
+    @Test
+    public void testLoadBTreeFromFile() throws Exception
+    {
+        String data100K = create100KElementsFile();
+        File dataFile = new File( data100K );
+        BTree<Long, String> btree = new BTree<Long, String>(
+            "test",
+            dataFile.getParent(),
+            new LongSerializer(),
+            new StringSerializer() );
+        btree.setPageSize( 32 );
+    }
+}



Mime
View raw message