directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From akaras...@apache.org
Subject svn commit: r439940 - in /directory/branches/apacheds/optimization: core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/ core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/ server-tools/src/main/java...
Date Mon, 04 Sep 2006 05:50:09 GMT
Author: akarasulu
Date: Sun Sep  3 22:50:08 2006
New Revision: 439940

URL: http://svn.apache.org/viewvc?view=rev&rev=439940
Log:
Added functionality that allows a Table to store duplicate key values in a BTree
instead of a TreeSet after a certain size limit is reached.  This code has not 
been fully tested yet.

Added:
    directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeEnumeration.java
    directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeTupleEnumeration.java
    directory/branches/apacheds/optimization/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeEnumerationTest.java
    directory/branches/apacheds/optimization/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeTupleEnumerationTest.java
    directory/branches/apacheds/optimization/server-tools/src/main/java/org/apache/directory/server/tools/CapacityTestCommand.java
Modified:
    directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTable.java
    directory/branches/apacheds/optimization/server-tools/src/main/java/org/apache/directory/server/tools/BaseCommand.java

Added: directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeEnumeration.java
URL: http://svn.apache.org/viewvc/directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeEnumeration.java?view=auto&rev=439940
==============================================================================
--- directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeEnumeration.java (added)
+++ directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeEnumeration.java Sun Sep  3 22:50:08 2006
@@ -0,0 +1,128 @@
+/*
+ *  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.server.core.partition.impl.btree.jdbm;
+
+
+import java.io.IOException;
+import java.util.NoSuchElementException;
+
+import javax.naming.NamingEnumeration;
+import javax.naming.NamingException;
+
+import org.apache.directory.shared.ldap.exception.LdapNamingException;
+import org.apache.directory.shared.ldap.message.ResultCodeEnum;
+
+import jdbm.btree.BTree;
+import jdbm.helper.TupleBrowser;
+
+
+/**
+ * A NamingEnumeration that returns keys in a BTree.  This is used specifically 
+ * for situations when tables support duplicate keys and a BTree is used for 
+ * storing the values for that key.  This enumeration thus advances a browser forwards 
+ * returning keys from a BTree as values.
+ * 
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$
+ */
+public class BTreeEnumeration implements NamingEnumeration
+{
+    private final jdbm.helper.Tuple jdbmTuple = new jdbm.helper.Tuple();
+    private TupleBrowser browser;
+    private boolean success = false;
+    
+    
+    BTreeEnumeration( BTree tree ) throws NamingException 
+    {
+        try
+        {
+            browser = tree.browse();
+            prefetch();
+        }
+        catch ( IOException e )
+        {
+            LdapNamingException lne = new LdapNamingException( "Failure on btree: " + e.getMessage(), 
+                ResultCodeEnum.OTHER );
+            lne.setRootCause( e );
+            throw lne;
+        }
+    }
+
+    
+    private void prefetch() throws IOException
+    {
+        success = browser.getNext( jdbmTuple );
+    }
+    
+    
+    public void close() throws NamingException
+    {
+        success = false;
+    }
+
+
+    public boolean hasMore() throws NamingException
+    {
+        return success;
+    }
+
+
+    public Object next() throws NamingException
+    {
+        if ( ! success )
+        {
+            throw new NoSuchElementException();
+        }
+        
+        Object next = jdbmTuple.getKey();
+        try
+        {
+            prefetch();
+        }
+        catch ( IOException e )
+        {
+            LdapNamingException lne = new LdapNamingException( "Failure on btree: " + e.getMessage(), 
+                ResultCodeEnum.OTHER );
+            lne.setRootCause( e );
+            throw lne;
+        }
+        return next;
+    }
+
+
+    public boolean hasMoreElements()
+    {
+        return success;
+    }
+
+
+    public Object nextElement()
+    {
+        try
+        {
+            return next();
+        }
+        catch ( NamingException e )
+        {
+            e.printStackTrace();
+            throw new NoSuchElementException( "Got IO Failure on btree: " + e.getCause().getMessage() );
+        }
+    }
+}

Added: directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeTupleEnumeration.java
URL: http://svn.apache.org/viewvc/directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeTupleEnumeration.java?view=auto&rev=439940
==============================================================================
--- directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeTupleEnumeration.java (added)
+++ directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeTupleEnumeration.java Sun Sep  3 22:50:08 2006
@@ -0,0 +1,186 @@
+/*
+ *  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.server.core.partition.impl.btree.jdbm;
+
+
+import java.io.IOException;
+import java.util.Comparator;
+import java.util.NoSuchElementException;
+
+import javax.naming.NamingEnumeration;
+import javax.naming.NamingException;
+
+import org.apache.directory.server.core.partition.impl.btree.Tuple;
+import org.apache.directory.shared.ldap.exception.LdapNamingException;
+import org.apache.directory.shared.ldap.message.ResultCodeEnum;
+
+import jdbm.btree.BTree;
+import jdbm.helper.TupleBrowser;
+
+
+/**
+ * A NamingEnumeration that returns underlying keys in a BTree as values for a 
+ * single key within a Tuple.  This is used specifically for situations when tables
+ * support duplicate keys and a BTree is used for storing the values for that
+ * key.  This enumeration thus advances a browser forwards or reverse returning
+ * keys from a BTree as Tuple values.  The key provided in the constructor is always
+ * returned as the key of the Tuple.
+ * 
+ * <p>
+ * WARNING: The tuple returned is reused every time for efficiency and populated
+ * a over and over again with the new value.  The key never changes.
+ * </p>
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$
+ */
+public class BTreeTupleEnumeration implements NamingEnumeration
+{
+    private final Object key;
+    private final Tuple tuple = new Tuple();
+    private final jdbm.helper.Tuple jdbmTuple = new jdbm.helper.Tuple();
+    private final boolean stepForward;
+    private TupleBrowser browser;
+    private boolean success = false;
+    
+    
+    BTreeTupleEnumeration( BTree tree, Comparator comparator, Object key, Object val, boolean isGreaterThan ) throws LdapNamingException 
+    {
+        this.key = key;
+        stepForward = isGreaterThan;
+        
+        try
+        {
+            browser = tree.browse( val );
+            
+            if ( ! isGreaterThan )
+            {
+                boolean gotNextOk = browser.getNext( jdbmTuple );
+                if ( gotNextOk )
+                {
+                    Object nextVal = jdbmTuple.getKey();
+                    int compared = comparator.compare( val, nextVal );
+                    if ( compared != 0 )
+                    {
+                        browser.getPrevious( jdbmTuple );
+                    }
+                }
+            }
+            
+            prefetch();
+        }
+        catch ( IOException e )
+        {
+            LdapNamingException lne = new LdapNamingException( "Failure on btree: " + e.getMessage(), 
+                ResultCodeEnum.OTHER );
+            lne.setRootCause( e );
+            throw lne;
+        }
+    }
+
+    
+    BTreeTupleEnumeration( BTree tree, Object key ) throws NamingException 
+    {
+        this.key = key;
+        stepForward = true;
+        
+        try
+        {
+            browser = tree.browse();
+            prefetch();
+        }
+        catch ( IOException e )
+        {
+            LdapNamingException lne = new LdapNamingException( "Failure on btree: " + e.getMessage(), 
+                ResultCodeEnum.OTHER );
+            lne.setRootCause( e );
+            throw lne;
+        }
+    }
+
+    
+    private void prefetch() throws IOException
+    {
+        if ( stepForward )
+        {
+            success = browser.getNext( jdbmTuple );
+        }
+        else
+        {
+            success = browser.getPrevious( jdbmTuple );
+        }
+    }
+    
+    
+    public void close() throws NamingException
+    {
+        success = false;
+    }
+
+
+    public boolean hasMore() throws NamingException
+    {
+        return success;
+    }
+
+
+    public Object next() throws NamingException
+    {
+        if ( ! success )
+        {
+            throw new NoSuchElementException();
+        }
+        
+        tuple.setKey( key );
+        tuple.setValue( jdbmTuple.getKey() );
+        try
+        {
+            prefetch();
+        }
+        catch ( IOException e )
+        {
+            LdapNamingException lne = new LdapNamingException( "Failure on btree: " + e.getMessage(), 
+                ResultCodeEnum.OTHER );
+            lne.setRootCause( e );
+            throw lne;
+        }
+        return tuple;
+    }
+
+
+    public boolean hasMoreElements()
+    {
+        return success;
+    }
+
+
+    public Object nextElement()
+    {
+        try
+        {
+            return next();
+        }
+        catch ( NamingException e )
+        {
+            e.printStackTrace();
+            throw new NoSuchElementException( "Got IO Failure on btree: " + e.getCause().getMessage() );
+        }
+    }
+}

Modified: directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTable.java
URL: http://svn.apache.org/viewvc/directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTable.java?view=diff&rev=439940&r1=439939&r2=439940
==============================================================================
--- directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTable.java (original)
+++ directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTable.java Sun Sep  3 22:50:08 2006
@@ -45,6 +45,8 @@
 import org.apache.directory.server.core.partition.impl.btree.TupleRenderer;
 import org.apache.directory.server.core.schema.SerializableComparator;
 
+import org.apache.directory.shared.ldap.exception.LdapNamingException;
+import org.apache.directory.shared.ldap.message.ResultCodeEnum;
 import org.apache.directory.shared.ldap.util.EmptyEnumeration;
 import org.apache.directory.shared.ldap.util.SingletonEnumeration;
 
@@ -76,6 +78,7 @@
     /** */
     private TupleRenderer renderer;
 
+    private int numDupLimit = 1000;
 
     // ------------------------------------------------------------------------
     // C O N S T R U C T O R
@@ -249,14 +252,41 @@
             }
         }
 
-        TreeSet set = ( TreeSet ) getRaw( key );
+        Object values = getRaw( key );
+        
+        // -------------------------------------------------------------------
+        // Handle the use of a TreeSet for storing duplicates
+        // -------------------------------------------------------------------
 
-        if ( set != null )
+        if ( values instanceof TreeSet )
         {
-            return set.size();
+            TreeSet set = ( TreeSet ) values;
+    
+            if ( set != null )
+            {
+                return set.size();
+            }
+
+            return 0;
         }
 
-        return 0;
+        // -------------------------------------------------------------------
+        // Handle the use of a BTree for storing duplicates
+        // -------------------------------------------------------------------
+
+        if ( values instanceof BTree )
+        {
+            BTree tree = ( BTree ) values;
+            
+            if ( values != null )
+            {
+                return tree.size();
+            }
+            
+            return 0;
+        }
+        
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
     }
 
 
@@ -278,9 +308,16 @@
      */
     public Object get( Object key ) throws NamingException
     {
-        if ( allowsDuplicates )
+        if ( ! allowsDuplicates )
         {
-            TreeSet set = ( TreeSet ) getRaw( key );
+            return getRaw( key );
+        }
+
+        Object values = getRaw( key );
+        
+        if ( values instanceof TreeSet )
+        {
+            TreeSet set = ( TreeSet ) values;
             if ( null == set || set.size() == 0 )
             {
                 return null;
@@ -291,10 +328,51 @@
             }
         }
 
-        Object value = getRaw( key );
-        return value;
+        if ( values instanceof BTree )
+        {
+            BTree tree = ( BTree ) values;
+            
+            if ( null == tree || tree.size() == 0 )
+            {
+                return null;
+            }
+            else
+            {
+                return firstKey( tree );
+            }
+        }
+        
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
     }
 
+    
+    private Object firstKey ( BTree tree ) throws NamingException
+    {
+        jdbm.helper.Tuple tuple = new jdbm.helper.Tuple();
+        boolean success = false;
+        
+        try
+        {
+            success = tree.browse().getNext( tuple );
+            
+            if ( success )
+            {
+                return tuple.getKey();
+            }
+            else 
+            {
+                return null;
+            }
+        }
+        catch ( IOException e )
+        {
+            LdapNamingException lne = new LdapNamingException( "IO failure while acessing btree: "
+                + e.getMessage(), ResultCodeEnum.OTHER );
+            lne.setRootCause( e );
+            throw lne;
+        }
+    }
+    
 
     /**
      * @see Table#has(java.lang.Object,
@@ -302,9 +380,6 @@
      */
     public boolean has( Object key, Object val, boolean isGreaterThan ) throws NamingException
     {
-        TreeSet set = null;
-        SortedSet subset = null;
-
         if ( !allowsDuplicates )
         {
             Object rval = getRaw( key );
@@ -314,17 +389,17 @@
             {
                 return false;
             }
-            // val == val return tuple
+            // val == val return true
             else if ( val.equals( rval ) )
             {
                 return true;
             }
-            // val >= val and test is for greater then return tuple
+            // val >= val and test is for greater then return true
             else if ( comparator.compareValue( rval, val ) >= 1 && isGreaterThan )
             {
                 return true;
             }
-            // val <= val and test is for lesser then return tuple
+            // val <= val and test is for lesser then return true
             else if ( comparator.compareValue( rval, val ) <= 1 && !isGreaterThan )
             {
                 return true;
@@ -333,30 +408,91 @@
             return false;
         }
 
-        set = ( TreeSet ) getRaw( key );
-
-        if ( null == set || set.size() == 0 )
-        {
+        Object values = getRaw( key );
+        
+        if ( values instanceof TreeSet )
+        {
+            TreeSet set = ( TreeSet ) values;
+            SortedSet subset = null;
+    
+            if ( null == set || set.size() == 0 )
+            {
+                return false;
+            }
+    
+            if ( isGreaterThan )
+            {
+                subset = set.tailSet( val );
+            }
+            else
+            {
+                subset = set.headSet( val );
+            }
+    
+            if ( subset.size() > 0 || set.contains( val ) )
+            {
+                return true;
+            }
+    
             return false;
         }
-
-        if ( isGreaterThan )
+        
+        if ( values instanceof BTree )
         {
-            subset = set.tailSet( val );
+            BTree tree = ( BTree ) values;
+            if ( null == tree || tree.size() == 0 )
+            {
+                return false;
+            }
+
+            return btreeHas( tree, val, isGreaterThan );
         }
-        else
+        
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
+    }
+
+    
+    private boolean btreeHas( BTree tree, Object key, boolean isGreaterThan ) throws NamingException
+    {
+        jdbm.helper.Tuple tuple = new jdbm.helper.Tuple();
+        
+        try
         {
-            subset = set.headSet( val );
+            TupleBrowser browser = tree.browse( key );
+            if ( isGreaterThan )
+            {
+                boolean success = browser.getNext( tuple );
+                if ( success )
+                {
+                    return true;
+                }
+                else
+                {
+                    return false;
+                }
+            }
+            else
+            {
+                boolean success = browser.getPrevious( tuple );
+                if ( success )
+                {
+                    return true;
+                }
+                else
+                {
+                    return false;
+                }
+            }
         }
-
-        if ( subset.size() > 0 || set.contains( val ) )
+        catch ( IOException e )
         {
-            return true;
+            LdapNamingException lne = new LdapNamingException( "IO failure while acessing btree: "
+                + e.getMessage(), ResultCodeEnum.OTHER );
+            lne.setRootCause( e );
+            throw lne;
         }
-
-        return false;
     }
-
+    
 
     /**
      * @see Table#has(java.lang.Object, boolean)
@@ -459,26 +595,72 @@
      */
     public boolean has( Object key, Object value ) throws NamingException
     {
-        if ( allowsDuplicates )
+        if ( ! allowsDuplicates )
         {
-            TreeSet set = ( TreeSet ) getRaw( key );
+            Object obj = getRaw( key );
 
-            if ( null == set )
+            if ( null == obj )
             {
                 return false;
             }
 
-            return set.contains( value );
+            return obj.equals( value );
         }
+        
+        Object values = getRaw( key );
+        
+        if ( values instanceof TreeSet )
+        {
+            TreeSet set = ( TreeSet ) values;
 
-        Object obj = getRaw( key );
+            if ( null == set )
+            {
+                return false;
+            }
 
-        if ( null == obj )
+            return set.contains( value );
+        }
+        
+        if ( values instanceof BTree )
         {
-            return false;
+            BTree tree = ( BTree ) values;
+            
+            if ( null == tree )
+            {
+                return  false;
+            }
+            
+            return btreeHas( tree, value );
+        }
+        
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
+    }
+    
+    
+    private boolean btreeHas( BTree tree, Object key ) throws NamingException
+    {
+        jdbm.helper.Tuple tuple = new jdbm.helper.Tuple();
+        
+        try
+        {
+            TupleBrowser browser = tree.browse( key );
+            boolean success = browser.getNext( tuple );
+            if ( success )
+            {
+                return true;
+            }
+            else
+            {
+                return false;
+            }
+        }
+        catch ( IOException e )
+        {
+            LdapNamingException lne = new LdapNamingException( "IO failure while acessing btree: "
+                + e.getMessage(), ResultCodeEnum.OTHER );
+            lne.setRootCause( e );
+            throw lne;
         }
-
-        return obj.equals( value );
     }
 
 
@@ -499,9 +681,23 @@
     {
         Object replaced = null;
 
-        if ( allowsDuplicates )
+        if ( ! allowsDuplicates )
         {
-            TreeSet set = ( TreeSet ) getRaw( key );
+            replaced = putRaw( key, value, true );
+
+            if ( null == replaced )
+            {
+                count++;
+            }
+
+            return replaced;
+        }
+        
+        Object values = getRaw( key );
+        
+        if ( values instanceof TreeSet )
+        {
+            TreeSet set = ( TreeSet ) values;
 
             if ( null == set )
             {
@@ -512,31 +708,100 @@
                 return value;
             }
 
-            set.add( value );
-            putRaw( key, set, true );
-            count++;
+            boolean addSuccessful = set.add( value );
+            
+            if ( set.size() > numDupLimit )
+            {
+                BTree tree = convertToBTree( set );
+                putRaw( key, tree, true );
+            }
+            else
+            {
+                putRaw( key, set, true );
+            }
+            
+            if ( addSuccessful )
+            {
+                count++;
+            }
             return null;
         }
-
-        replaced = putRaw( key, value, true );
-
-        if ( null == replaced )
+        
+        if ( values instanceof BTree )
         {
-            count++;
+            BTree tree = ( BTree ) values;
+            if ( insertDupIntoBTree( tree, value ) )
+            {
+                count++;
+            }
         }
+        
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
+    }
 
-        return replaced;
+    
+    private boolean insertDupIntoBTree( BTree tree, Object value ) throws LdapNamingException
+    {
+        try
+        {
+            Object replaced = tree.insert( value, EMPTY_BYTES, true );
+            return null == replaced;
+        }
+        catch ( IOException e )
+        {
+            LdapNamingException lne = new LdapNamingException( "Failed to insert dup into BTree", 
+                ResultCodeEnum.OTHER );
+            lne.setRootCause( e );
+            throw lne;
+        }
     }
+    
 
+    private boolean removeDupFromBTree( BTree tree, Object value ) throws LdapNamingException
+    {
+        try
+        {
+            Object removed = tree.remove( value );
+            return null != removed;
+        }
+        catch ( IOException e )
+        {
+            LdapNamingException lne = new LdapNamingException( "Failed to remove dup from BTree", 
+                ResultCodeEnum.OTHER );
+            lne.setRootCause( e );
+            throw lne;
+        }
+    }
+    
 
+    private static final byte[] EMPTY_BYTES = new byte[0];
+    private BTree convertToBTree( TreeSet set ) throws NamingException
+    {
+        try
+        {
+            BTree tree = BTree.createInstance( recMan, comparator.getValueComparator() );
+            for ( Iterator ii = set.iterator(); ii.hasNext(); /**/ )
+            {
+                tree.insert( ii.next(), EMPTY_BYTES, true );
+            }
+            return tree;
+        }
+        catch ( IOException e )
+        {
+            LdapNamingException lne = new LdapNamingException( "Failed to convert TreeSet values to BTree", 
+                ResultCodeEnum.OTHER );
+            lne.setRootCause( e );
+            throw lne;
+        }
+    }
+    
+    
     /**
      * @see Table#put(java.lang.Object,
      * javax.naming.NamingEnumeration)
      */
     public Object put( Object key, NamingEnumeration values ) throws NamingException
     {
-        TreeSet set = null;
-
         /*
          * If we do not allow duplicates call the single add put using the
          * first value in the enumeration if it exists.  If it does not we
@@ -561,32 +826,65 @@
             return null;
         }
 
-        /*
-         * Here the table allows duplicates so we get the TreeSet from the 
-         * Table holding all the duplicate key values or create one if it
-         * does not exist for key.  We check if the value is present and
-         * if it is we add it and increment the table entry counter.
-         */
-        set = ( TreeSet ) getRaw( key );
-
-        if ( null == set )
-        {
-            set = new TreeSet( comparator.getValueComparator() );
+        Object storedValues = getRaw( key );
+        
+        if ( storedValues instanceof TreeSet )
+        {
+            /*
+             * Here the table allows duplicates so we get the TreeSet from the 
+             * Table holding all the duplicate key values or create one if it
+             * does not exist for key.  We check if the value is present and
+             * if it is we add it and increment the table entry counter.
+             */
+            TreeSet set = ( TreeSet ) storedValues;
+    
+            if ( null == set )
+            {
+                set = new TreeSet( comparator.getValueComparator() );
+            }
+    
+            while ( values.hasMore() )
+            {
+                Object val = values.next();
+    
+                if ( !set.contains( val ) )
+                {
+                    boolean isAddSuccessful = set.add( val );
+                    if ( isAddSuccessful )
+                    {
+                        count++;
+                    }
+                }
+            }
+    
+            if ( set.size() > numDupLimit )
+            {
+                BTree tree = convertToBTree( set );
+                return putRaw( key, tree, true );
+            }
+            else
+            {
+                return putRaw( key, set, true );
+            }
         }
-
-        while ( values.hasMore() )
+        
+        if ( storedValues instanceof BTree )
         {
-            Object val = values.next();
-
-            if ( !set.contains( val ) )
+            BTree tree = ( BTree ) storedValues;
+            while ( values.hasMore() )
             {
-                set.add( val );
-                count++;
+                Object val = values.next();
+                
+                if ( insertDupIntoBTree( tree, val ) )
+                {
+                    count++;
+                }
             }
-        }
 
-        // Return the raw TreeSet
-        return putRaw( key, set, true );
+            return putRaw( key, tree, true );
+        }
+        
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
     }
 
 
@@ -596,7 +894,20 @@
      */
     public Object remove( Object key, Object value ) throws NamingException
     {
-        if ( allowsDuplicates )
+        if ( ! allowsDuplicates )
+        {
+            // Remove the value only if it is the same as value.
+            if ( getRaw( key ).equals( value ) )
+            {
+                return removeRaw( key );
+            }
+
+            return null;
+        }
+
+        Object values = getRaw( key );
+        
+        if ( values instanceof TreeSet )
         {
             TreeSet set = ( TreeSet ) getRaw( key );
 
@@ -625,13 +936,36 @@
             return null;
         }
 
-        // Remove the value only if it is the same as value.
-        if ( getRaw( key ).equals( value ) )
-        {
-            return removeRaw( key );
+        // TODO might be nice to add code here that reverts to a TreeSet
+        // if the number of duplicates falls below the numDupLimit value
+        if ( values instanceof BTree )
+        {
+            BTree tree = ( BTree ) values;
+            
+            if ( null == tree )
+            {
+                return null;
+            }
+            
+            if ( removeDupFromBTree( tree, value ) )
+            {
+                if ( tree.size() == 0 )
+                {
+                    removeRaw( tree );
+                }
+                else
+                {
+                    putRaw( key, tree, true );
+                }
+                
+                count--;
+                return value;
+            }
+            
+            return null;
         }
-
-        return null;
+        
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
     }
 
 
@@ -641,8 +975,6 @@
      */
     public Object remove( Object key, NamingEnumeration values ) throws NamingException
     {
-        TreeSet set = null;
-
         /*
          * If we do not allow dupliicates call the single remove using the
          * first value in the enumeration if it exists.  If it does not we
@@ -667,35 +999,65 @@
             return null;
         }
 
-        /*
-         * Here the table allows duplicates so we get the TreeSet from the 
-         * Table holding all the duplicate key values or return null if it
-         * does not exist for key - nothing to do here.
-         */
-        set = ( TreeSet ) getRaw( key );
-        if ( null == set )
-        {
-            return null;
-        }
-
-        /*
-         * So we have a valid TreeSet with values in it.  We check if each value
-         * is in the set and remove it if it is present.  We decrement the 
-         * counter while doing so.
-         */
-        while ( values.hasMore() )
+        Object storedValues = getRaw( key );
+        
+        if ( storedValues instanceof TreeSet )
+        {
+            /*
+             * Here the table allows duplicates so we get the TreeSet from the 
+             * Table holding all the duplicate key values or return null if it
+             * does not exist for key - nothing to do here.
+             */
+            TreeSet set = ( TreeSet ) storedValues;
+            if ( null == set )
+            {
+                return null;
+            }
+    
+            /*
+             * So we have a valid TreeSet with values in it.  We check if each value
+             * is in the set and remove it if it is present.  We decrement the 
+             * counter while doing so.
+             */
+            while ( values.hasMore() )
+            {
+                Object val = values.next();
+    
+                if ( !set.contains( val ) )
+                {
+                    set.remove( val );
+                    count--;
+                }
+            }
+    
+            // Return the raw TreeSet and put the changed one back.
+            return putRaw( key, set, true );
+        }
+        
+        // TODO might be nice to add code here that reverts to a TreeSet
+        // if the number of duplicates falls below the numDupLimit value
+        if ( storedValues instanceof BTree )
         {
-            Object val = values.next();
-
-            if ( !set.contains( val ) )
+            BTree tree = ( BTree ) storedValues;
+            if ( null == tree )
             {
-                set.remove( val );
-                count--;
+                return null;
             }
+            
+            while ( values.hasMore() )
+            {
+                Object val = values.next();
+                
+                if ( removeDupFromBTree( tree, val ) )
+                {
+                    count--;
+                }
+            }
+            
+            return putRaw( key, tree, true );
         }
-
-        // Return the raw TreeSet and put the changed one back.
-        return putRaw( key, set, true );
+        
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
     }
 
 
@@ -728,8 +1090,6 @@
      */
     public NamingEnumeration listValues( Object key ) throws NamingException
     {
-        TreeSet set = null;
-
         if ( !allowsDuplicates )
         {
             Object value = get( key );
@@ -744,43 +1104,61 @@
             }
         }
 
-        set = ( TreeSet ) getRaw( key );
-        if ( null == set )
-        {
-            return new EmptyEnumeration();
-        }
-
-        final Iterator list = set.iterator();
-        return new NamingEnumeration()
+        Object values = getRaw( key );
+        
+        if ( values instanceof TreeSet )
         {
-            public void close()
-            {
-            }
-
-
-            public Object nextElement()
+            TreeSet set = ( TreeSet ) values;
+            if ( null == set )
             {
-                return list.next();
+                return new EmptyEnumeration();
             }
-
-
-            public Object next()
+    
+            final Iterator list = set.iterator();
+            return new NamingEnumeration()
             {
-                return list.next();
-            }
-
-
-            public boolean hasMore()
-            {
-                return list.hasNext();
-            }
-
-
-            public boolean hasMoreElements()
+                public void close()
+                {
+                }
+    
+    
+                public Object nextElement()
+                {
+                    return list.next();
+                }
+    
+    
+                public Object next()
+                {
+                    return list.next();
+                }
+    
+    
+                public boolean hasMore()
+                {
+                    return list.hasNext();
+                }
+    
+    
+                public boolean hasMoreElements()
+                {
+                    return list.hasNext();
+                }
+            };
+        }
+        
+        if ( values instanceof BTree )
+        {
+            BTree tree = ( BTree ) values;
+            if ( null == tree )
             {
-                return list.hasNext();
+                return new EmptyEnumeration();
             }
-        };
+            
+            return new BTreeEnumeration( tree );
+        }
+        
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
     }
 
 
@@ -821,8 +1199,6 @@
      */
     public NamingEnumeration listTuples( Object key ) throws NamingException
     {
-        TreeSet set = null;
-
         // Handle single and zero value returns without duplicates enabled
         if ( !allowsDuplicates )
         {
@@ -838,16 +1214,33 @@
             }
         }
 
-        set = ( TreeSet ) getRaw( key );
-        if ( set == null )
+        Object values = getRaw( key );
+        
+        if ( values instanceof TreeSet )
         {
-            return new EmptyEnumeration();
+            TreeSet set = ( TreeSet ) values;
+            if ( set == null )
+            {
+                return new EmptyEnumeration();
+            }
+    
+            Object[] objs = new Object[set.size()];
+            objs = set.toArray( objs );
+            ArrayIterator iterator = new ArrayIterator( objs );
+            return new TupleEnumeration( key, iterator );
+        }
+        
+        if ( values instanceof BTree )
+        {
+            BTree tree = ( BTree ) values;
+            if ( null == tree )
+            {
+                return new EmptyEnumeration();
+            }
+            return new BTreeTupleEnumeration( tree, key );
         }
 
-        Object[] objs = new Object[set.size()];
-        objs = set.toArray( objs );
-        ArrayIterator iterator = new ArrayIterator( objs );
-        return new TupleEnumeration( key, iterator );
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
     }
 
 
@@ -919,8 +1312,6 @@
      */
     public NamingEnumeration listTuples( Object key, Object val, boolean isGreaterThan ) throws NamingException
     {
-        TreeSet set = null;
-
         if ( !allowsDuplicates )
         {
             Object rval = getRaw( key );
@@ -947,44 +1338,62 @@
             return new EmptyEnumeration();
         }
 
-        set = ( TreeSet ) getRaw( key );
-        if ( set == null )
+        Object values = getRaw( key );
+        
+        if ( values instanceof TreeSet )
         {
-            return new EmptyEnumeration();
-        }
-
-        if ( isGreaterThan )
-        {
-            Object[] objs = new Object[set.size()];
-            objs = set.tailSet( val ).toArray( objs );
-            ArrayIterator iterator = new ArrayIterator( objs );
-            return new TupleEnumeration( key, iterator );
+            TreeSet set = ( TreeSet ) values;
+            if ( set == null )
+            {
+                return new EmptyEnumeration();
+            }
+    
+            if ( isGreaterThan )
+            {
+                Object[] objs = new Object[set.size()];
+                objs = set.tailSet( val ).toArray( objs );
+                ArrayIterator iterator = new ArrayIterator( objs );
+                return new TupleEnumeration( key, iterator );
+            }
+            else
+            {
+                // Get all values from the smallest upto val and put them into
+                // a list.  They will be in ascending order so we need to reverse
+                // the list after adding val which is not included in headSet.
+                SortedSet headset = set.headSet( val );
+                ArrayList list = new ArrayList( set.size() + 1 );
+                list.addAll( headset );
+    
+                // Add largest value (val) if it is in the set.  TreeSet.headSet
+                // does not get val if val is in the set.  So we add it now to
+                // the end of the list.  List is now ascending from smallest to
+                // val
+                if ( set.contains( val ) )
+                {
+                    list.add( val );
+                }
+    
+                // Reverse the list now we have descending values from val to the
+                // smallest value that key has.  Return tuple cursor over list.
+                Collections.reverse( list );
+                return new TupleEnumeration( key, list.iterator() );
+            }
         }
-        else
+        
+        if ( values instanceof BTree )
         {
-            // Get all values from the smallest upto val and put them into
-            // a list.  They will be in ascending order so we need to reverse
-            // the list after adding val which is not included in headSet.
-            SortedSet headset = set.headSet( val );
-            ArrayList list = new ArrayList( set.size() + 1 );
-            list.addAll( headset );
-
-            // Add largest value (val) if it is in the set.  TreeSet.headSet
-            // does not get val if val is in the set.  So we add it now to
-            // the end of the list.  List is now ascending from smallest to
-            // val
-            if ( set.contains( val ) )
-            {
-                list.add( val );
-            }
-
-            // Reverse the list now we have descending values from val to the
-            // smallest value that key has.  Return tuple cursor over list.
-            Collections.reverse( list );
-            return new TupleEnumeration( key, list.iterator() );
+            BTree tree = ( BTree ) values;
+            if ( tree == null )
+            {
+                return new EmptyEnumeration();
+            }
+
+            return new BTreeTupleEnumeration( tree, comparator.getValueComparator(), key, val, isGreaterThan );
         }
-    }
 
+        throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." );
+    }
+    
 
     // ------------------------------------------------------------------------
     // Maintenance Operations 

Added: directory/branches/apacheds/optimization/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeEnumerationTest.java
URL: http://svn.apache.org/viewvc/directory/branches/apacheds/optimization/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeEnumerationTest.java?view=auto&rev=439940
==============================================================================
--- directory/branches/apacheds/optimization/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeEnumerationTest.java (added)
+++ directory/branches/apacheds/optimization/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeEnumerationTest.java Sun Sep  3 22:50:08 2006
@@ -0,0 +1,116 @@
+/*
+ *  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.server.core.partition.impl.btree.jdbm;
+
+
+import java.io.File;
+import java.io.IOException;
+import java.math.BigInteger;
+
+import javax.naming.NamingException;
+
+import jdbm.RecordManager;
+import jdbm.btree.BTree;
+import jdbm.recman.BaseRecordManager;
+
+import org.apache.directory.shared.ldap.util.BigIntegerComparator;
+
+import junit.framework.TestCase;
+
+
+/**
+ * Tests that the BTreeEnumeration functions as expected.
+ * 
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$
+ */
+public class BTreeEnumerationTest extends TestCase
+{
+    private final static byte[] EMPTY_BYTES = new byte[0];
+    private File tempFile = null;
+    private BTree tree = null;
+    private RecordManager rm = null;
+    
+    
+    public void setUp() throws Exception 
+    {
+        tempFile = File.createTempFile( "jdbm", "test" );
+        rm = new BaseRecordManager( tempFile.getAbsolutePath() );
+        tree = BTree.createInstance( rm, new BigIntegerComparator() );
+    }
+    
+
+    public void testEmptyBTree() throws NamingException
+    {
+        BTreeEnumeration bte = new BTreeEnumeration( tree );
+        assertFalse( "enumeration on empty btree should not have elements", bte.hasMore() );
+    }
+    
+    
+    public void testOneElement() throws IOException, NamingException
+    {
+        BigInteger value = new BigInteger( "1" );
+        tree.insert( value, EMPTY_BYTES, true );
+        BTreeEnumeration bte = new BTreeEnumeration( tree );
+        assertTrue( bte.hasMore() );
+        assertEquals( value, bte.next() );
+        assertFalse( "enumeration consumed should not have elements", bte.hasMore() );
+    }
+    
+    
+    public void testManyElements() throws IOException, NamingException
+    {
+        /*
+         * Adding the following values for this test
+         * 1, -
+         * 2, -
+         * 4, -
+         * 5, -
+         */
+        BigInteger value = new BigInteger( "1" );
+        tree.insert( value, EMPTY_BYTES, true );
+        
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+
+        value = value.add( BigInteger.ONE );
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+        
+        BTreeEnumeration bte = new BTreeEnumeration( tree );
+
+        assertTrue( bte.hasMore() );
+        assertEquals( new BigInteger( "1" ), bte.next() );
+
+        assertTrue( bte.hasMore() );
+        assertEquals( new BigInteger( "2" ), bte.next() );
+
+        assertTrue( bte.hasMore() );
+        assertEquals( new BigInteger( "4" ), bte.next() );
+
+        assertTrue( bte.hasMore() );
+        assertEquals( new BigInteger( "5" ), bte.next() );
+
+        assertFalse( "enumeration consumed should not have elements", bte.hasMore() );
+    }
+}

Added: directory/branches/apacheds/optimization/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeTupleEnumerationTest.java
URL: http://svn.apache.org/viewvc/directory/branches/apacheds/optimization/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeTupleEnumerationTest.java?view=auto&rev=439940
==============================================================================
--- directory/branches/apacheds/optimization/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeTupleEnumerationTest.java (added)
+++ directory/branches/apacheds/optimization/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeTupleEnumerationTest.java Sun Sep  3 22:50:08 2006
@@ -0,0 +1,407 @@
+/*
+ *  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.server.core.partition.impl.btree.jdbm;
+
+
+import java.io.File;
+import java.io.IOException;
+import java.math.BigInteger;
+
+import javax.naming.NamingException;
+
+import jdbm.RecordManager;
+import jdbm.btree.BTree;
+import jdbm.recman.BaseRecordManager;
+
+import org.apache.directory.server.core.partition.impl.btree.Tuple;
+import org.apache.directory.shared.ldap.util.BigIntegerComparator;
+
+import junit.framework.TestCase;
+
+
+/**
+ * Tests that the BTreeTupleEnumeration functions as expected.
+ * 
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$
+ */
+public class BTreeTupleEnumerationTest extends TestCase
+{
+    private final static byte[] EMPTY_BYTES = new byte[0];
+    private File tempFile = null;
+    private BTree tree = null;
+    private RecordManager rm = null;
+    
+    
+    public void setUp() throws Exception 
+    {
+        tempFile = File.createTempFile( "jdbm", "test" );
+        rm = new BaseRecordManager( tempFile.getAbsolutePath() );
+        tree = BTree.createInstance( rm, new BigIntegerComparator() );
+    }
+    
+
+    public void testEmptyBTree() throws NamingException
+    {
+        BTreeTupleEnumeration bte = new BTreeTupleEnumeration( tree, BigInteger.ONE );
+        assertFalse( "enumeration on empty btree should not have elements", bte.hasMore() );
+    }
+    
+    
+    public void testOneElement() throws IOException, NamingException
+    {
+        BigInteger value = new BigInteger( "1" );
+        tree.insert( value, EMPTY_BYTES, true );
+        BTreeTupleEnumeration bte = new BTreeTupleEnumeration( tree, BigInteger.ONE );
+        assertTrue( bte.hasMore() );
+        Tuple tuple = ( Tuple ) bte.next();
+        assertEquals( BigInteger.ONE, tuple.getKey() );
+        assertEquals( value, tuple.getValue() );
+        assertFalse( "enumeration consumed should not have elements", bte.hasMore() );
+    }
+    
+    
+    public void testManyElements() throws IOException, NamingException
+    {
+        /*
+         * Adding the following values for this test
+         * 1, -
+         * 2, -
+         * 4, -
+         * 5, -
+         */
+        BigInteger value = new BigInteger( "1" );
+        tree.insert( value, EMPTY_BYTES, true );
+        
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+
+        value = value.add( BigInteger.ONE );
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+        
+        BTreeTupleEnumeration bte = new BTreeTupleEnumeration( tree, BigInteger.ONE );
+        
+        Tuple tuple = ( Tuple ) bte.next();
+        assertTrue( bte.hasMore() );
+        assertEquals( BigInteger.ONE, tuple.getKey() );
+        assertEquals( new BigInteger( "1" ), tuple.getValue() );
+
+        bte.next();
+        assertTrue( bte.hasMore() );
+        assertEquals( BigInteger.ONE, tuple.getKey() );
+        assertEquals( new BigInteger( "2" ), tuple.getValue() );
+
+        bte.next();
+        assertTrue( bte.hasMore() );
+        assertEquals( BigInteger.ONE, tuple.getKey() );
+        assertEquals( new BigInteger( "4" ), tuple.getValue() );
+
+        bte.next();
+        assertEquals( BigInteger.ONE, tuple.getKey() );
+        assertEquals( new BigInteger( "5" ), tuple.getValue() );
+
+        assertFalse( "enumeration consumed should not have elements", bte.hasMore() );
+    }
+    
+    
+    public void testManyElementsLessThanNonExistantValue() throws IOException, NamingException
+    {
+        /*
+         * Adding the following values for this test
+         * 1, -
+         * 2, -
+         * 4, -
+         * 5, -
+         */
+        BigInteger value = new BigInteger( "1" );
+        tree.insert( value, EMPTY_BYTES, true );
+        
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+
+        value = value.add( BigInteger.ONE );
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+        
+        BTreeTupleEnumeration bte = new BTreeTupleEnumeration( tree, new BigIntegerComparator(), 
+            BigInteger.ONE, new BigInteger( "3" ), false );
+        
+        Tuple tuple = ( Tuple ) bte.next();
+        assertTrue( bte.hasMore() );
+        assertEquals( BigInteger.ONE, tuple.getKey() );
+        assertEquals( new BigInteger( "2" ), tuple.getValue() );
+
+        bte.next();
+        assertEquals( BigInteger.ONE, tuple.getKey() );
+        assertEquals( new BigInteger( "1" ), tuple.getValue() );
+
+        assertFalse( "enumeration consumed should not have elements", bte.hasMore() );
+    }
+    
+    
+    public void testManyElementsLessThanLowestValue() throws IOException, NamingException
+    {
+        /*
+         * Adding the following values for this test
+         * 1, -
+         * 2, -
+         * 4, -
+         * 5, -
+         */
+        BigInteger value = new BigInteger( "1" );
+        tree.insert( value, EMPTY_BYTES, true );
+        
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+
+        value = value.add( BigInteger.ONE );
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+        
+        BTreeTupleEnumeration bte = new BTreeTupleEnumeration( tree, new BigIntegerComparator(), 
+            BigInteger.ONE, BigInteger.ZERO, false );
+        
+        assertFalse( "enumeration consumed should not have elements", bte.hasMore() );
+    }
+    
+    
+    public void testManyElementsLessThanAtLowestValue() throws IOException, NamingException
+    {
+        /*
+         * Adding the following values for this test
+         * 1, -
+         * 2, -
+         * 4, -
+         * 5, -
+         */
+        BigInteger value = new BigInteger( "1" );
+        tree.insert( value, EMPTY_BYTES, true );
+        
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+
+        value = value.add( BigInteger.ONE );
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+        
+        BTreeTupleEnumeration bte = new BTreeTupleEnumeration( tree, new BigIntegerComparator(), 
+            BigInteger.ONE, BigInteger.ONE, false );
+        
+        Tuple tuple = ( Tuple ) bte.next();
+        assertEquals( BigInteger.ONE, tuple.getKey() );
+        assertEquals( new BigInteger( "1" ), tuple.getValue() );
+
+        assertFalse( "enumeration consumed should not have elements", bte.hasMore() );
+    }
+    
+    
+    public void testManyElementsGreaterThanNonExistantValue() throws IOException, NamingException
+    {
+        /*
+         * Adding the following values for this test
+         * 1, -
+         * 2, -
+         * 4, -
+         * 5, -
+         */
+        BigInteger value = new BigInteger( "1" );
+        tree.insert( value, EMPTY_BYTES, true );
+        
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+
+        value = value.add( BigInteger.ONE );
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+        
+        BTreeTupleEnumeration bte = new BTreeTupleEnumeration( tree, new BigIntegerComparator(), 
+            BigInteger.ONE, new BigInteger( "3" ), true );
+        
+        Tuple tuple = ( Tuple ) bte.next();
+        assertTrue( bte.hasMore() );
+        assertEquals( BigInteger.ONE, tuple.getKey() );
+        assertEquals( new BigInteger( "4" ), tuple.getValue() );
+
+        bte.next();
+        assertEquals( BigInteger.ONE, tuple.getKey() );
+        assertEquals( new BigInteger( "5" ), tuple.getValue() );
+
+        assertFalse( "enumeration consumed should not have elements", bte.hasMore() );
+    }
+    
+    
+    public void testManyElementsGreaterThanLastValue() throws IOException, NamingException
+    {
+        /*
+         * Adding the following values for this test
+         * 1, -
+         * 2, -
+         * 4, -
+         * 5, -
+         */
+        BigInteger value = new BigInteger( "1" );
+        tree.insert( value, EMPTY_BYTES, true );
+        
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+
+        value = value.add( BigInteger.ONE );
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+        
+        BTreeTupleEnumeration bte = new BTreeTupleEnumeration( tree, new BigIntegerComparator(), 
+            BigInteger.ONE, new BigInteger( "6" ), true );
+        
+        assertFalse( "enumeration consumed should not have elements", bte.hasMore() );
+    }
+    
+    
+    public void testManyElementsGreaterThanAtLastValue() throws IOException, NamingException
+    {
+        /*
+         * Adding the following values for this test
+         * 1, -
+         * 2, -
+         * 4, -
+         * 5, -
+         */
+        BigInteger value = new BigInteger( "1" );
+        tree.insert( value, EMPTY_BYTES, true );
+        
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+
+        value = value.add( BigInteger.ONE );
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+        
+        BTreeTupleEnumeration bte = new BTreeTupleEnumeration( tree, new BigIntegerComparator(), 
+            BigInteger.ONE, new BigInteger( "5" ), true );
+        
+        Tuple tuple = ( Tuple ) bte.next();
+        assertEquals( BigInteger.ONE, tuple.getKey() );
+        assertEquals( new BigInteger( "5" ), tuple.getValue() );
+
+        assertFalse( "enumeration consumed should not have elements", bte.hasMore() );
+    }
+    
+    
+    public void testManyElementsLessThanExistantValue() throws IOException, NamingException
+    {
+        /*
+         * Adding the following values for this test
+         * 1, -
+         * 2, -
+         * 4, -
+         * 5, -
+         */
+        BigInteger value = new BigInteger( "1" );
+        tree.insert( value, EMPTY_BYTES, true );
+        
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+
+        value = value.add( BigInteger.ONE );
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+        
+        BTreeTupleEnumeration bte = new BTreeTupleEnumeration( tree, new BigIntegerComparator(), 
+            BigInteger.ONE, new BigInteger( "4" ), false );
+        
+        Tuple tuple = ( Tuple ) bte.next();
+        assertTrue( bte.hasMore() );
+        assertEquals( BigInteger.ONE, tuple.getKey() );
+        assertEquals( new BigInteger( "4" ), tuple.getValue() );
+
+        bte.next();
+        assertTrue( bte.hasMore() );
+        assertEquals( BigInteger.ONE, tuple.getKey() );
+        assertEquals( new BigInteger( "2" ), tuple.getValue() );
+
+        bte.next();
+        assertEquals( BigInteger.ONE, tuple.getKey() );
+        assertEquals( new BigInteger( "1" ), tuple.getValue() );
+
+        assertFalse( "enumeration consumed should not have elements", bte.hasMore() );
+    }
+    
+    
+    public void testManyElementsGreaterThanExistantValue() throws IOException, NamingException
+    {
+        /*
+         * Adding the following values for this test
+         * 1, -
+         * 2, -
+         * 4, -
+         * 5, -
+         */
+        BigInteger value = new BigInteger( "1" );
+        tree.insert( value, EMPTY_BYTES, true );
+        
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+
+        value = value.add( BigInteger.ONE );
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+
+        value = value.add( BigInteger.ONE );
+        tree.insert( value, EMPTY_BYTES, true );
+        
+        BTreeTupleEnumeration bte = new BTreeTupleEnumeration( tree, new BigIntegerComparator(), 
+            BigInteger.ONE, new BigInteger( "4" ), true );
+        
+        Tuple tuple = ( Tuple ) bte.next();
+        assertTrue( bte.hasMore() );
+        assertEquals( BigInteger.ONE, tuple.getKey() );
+        assertEquals( new BigInteger( "4" ), tuple.getValue() );
+
+        bte.next();
+        assertEquals( BigInteger.ONE, tuple.getKey() );
+        assertEquals( new BigInteger( "5" ), tuple.getValue() );
+
+        assertFalse( "enumeration consumed should not have elements", bte.hasMore() );
+    }
+}

Modified: directory/branches/apacheds/optimization/server-tools/src/main/java/org/apache/directory/server/tools/BaseCommand.java
URL: http://svn.apache.org/viewvc/directory/branches/apacheds/optimization/server-tools/src/main/java/org/apache/directory/server/tools/BaseCommand.java?view=diff&rev=439940&r1=439939&r2=439940
==============================================================================
--- directory/branches/apacheds/optimization/server-tools/src/main/java/org/apache/directory/server/tools/BaseCommand.java (original)
+++ directory/branches/apacheds/optimization/server-tools/src/main/java/org/apache/directory/server/tools/BaseCommand.java Sun Sep  3 22:50:08 2006
@@ -90,6 +90,10 @@
         commands.put( command.getName(), command );
         commandsOrdered.add( command.getName() );
 
+        command = new CapacityTestCommand();
+        commands.put( command.getName(), command );
+        commandsOrdered.add( command.getName() );
+
         Option op = new Option( "i", "install-path", true, "path to installation directory" );
         getGlobal().addOption( op );
         op = new Option( "b", "banner", false, "suppress banner print outs" );

Added: directory/branches/apacheds/optimization/server-tools/src/main/java/org/apache/directory/server/tools/CapacityTestCommand.java
URL: http://svn.apache.org/viewvc/directory/branches/apacheds/optimization/server-tools/src/main/java/org/apache/directory/server/tools/CapacityTestCommand.java?view=auto&rev=439940
==============================================================================
--- directory/branches/apacheds/optimization/server-tools/src/main/java/org/apache/directory/server/tools/CapacityTestCommand.java (added)
+++ directory/branches/apacheds/optimization/server-tools/src/main/java/org/apache/directory/server/tools/CapacityTestCommand.java Sun Sep  3 22:50:08 2006
@@ -0,0 +1,284 @@
+/*
+ *  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.server.tools;
+
+
+import java.io.FileWriter;
+import java.io.PrintWriter;
+import java.util.Hashtable;
+
+import javax.naming.directory.Attribute;
+import javax.naming.directory.Attributes;
+import javax.naming.directory.BasicAttributes;
+import javax.naming.ldap.InitialLdapContext;
+import javax.naming.ldap.LdapContext;
+
+import org.apache.commons.cli.CommandLine;
+import org.apache.commons.cli.Option;
+import org.apache.commons.cli.Options;
+import org.apache.commons.lang.RandomStringUtils;
+import org.apache.directory.daemon.AvailablePortFinder;
+
+
+
+/**
+ * A capacity testing tool.  This command will generate bogus user
+ * entries and add them under a base DN.  It will output a table 
+ * of values mapping the capacity of the partition to the time it
+ * took to add an entry to it.
+ * 
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$
+ */
+public class CapacityTestCommand extends ToolCommand
+{
+    public static final String PORT_RANGE = "(" + AvailablePortFinder.MIN_PORT_NUMBER + ", "
+        + AvailablePortFinder.MAX_PORT_NUMBER + ")";
+
+    private int port = 10389;
+    private String host = "localhost";
+    private String password = "secret";
+    private String baseDn = "ou=users,dc=example,dc=com";
+    
+    
+    public CapacityTestCommand()
+    {
+        super( "capacity" );
+    }
+
+
+    public void execute( CommandLine cmdline ) throws Exception
+    {
+        processOptions( cmdline );
+        getLayout().verifyInstallation();
+        String outputFile = cmdline.getOptionValue( 'f' );
+        PrintWriter out = null;
+
+        if ( outputFile == null )
+        {
+            out = new PrintWriter( System.out );
+        }
+        else
+        {
+            out = new PrintWriter( new FileWriter( outputFile ) );
+        }
+        
+        if ( isDebugEnabled() )
+        {
+            out.println( "Parameters for capacity extended request:" );
+            out.println( "port = " + port );
+            out.println( "host = " + host );
+            out.println( "password = " + password );
+        }
+
+        Hashtable env = new Hashtable();
+        env.put( "java.naming.factory.initial", "com.sun.jndi.ldap.LdapCtxFactory" );
+        env.put( "java.naming.provider.url", "ldap://" + host + ":" + port );
+        env.put( "java.naming.security.principal", "uid=admin,ou=system" );
+        env.put( "java.naming.security.credentials", password );
+        env.put( "java.naming.security.authentication", "simple" );
+
+        LdapContext ctx = new InitialLdapContext( env, null );
+
+        StringBuffer dnBuf = new StringBuffer();
+        StringBuffer outBuf = new StringBuffer();
+        int counter = 0;
+        if ( cmdline.hasOption( "s" ) )
+        {
+            counter = Integer.parseInt( cmdline.getOptionValue( 's' ) ) - 1;
+        }
+        int end = Integer.MAX_VALUE;
+        if ( cmdline.hasOption( "e" ) )
+        {
+            end = Integer.parseInt( cmdline.getOptionValue( 'e' ) );
+        }
+        
+        while ( counter < end )
+        {
+            counter++;
+            Attributes attrs = generateLdif( counter );
+            dnBuf.setLength( 0 );
+            dnBuf.append( "uid=user." ).append( counter ).append( "," ).append( baseDn );
+            
+            long startTime = System.currentTimeMillis();
+            ctx.createSubcontext( dnBuf.toString(), attrs );
+            
+            outBuf.setLength( 0 );
+            outBuf.append( counter ).append( " " ).append( System.currentTimeMillis() - startTime );
+            out.println( outBuf.toString() );
+            out.flush();
+        }
+    }
+    
+    
+    private Attributes generateLdif( int counter )
+    {
+        BasicAttributes attrs = new BasicAttributes( "objectClass", "top", true );
+        Attribute oc = attrs.get( "objectClass" );
+        oc.add( "person" );
+        oc.add( "organizationalPerson" );
+        oc.add( "inetOrgPerson" );
+        
+        attrs.put( "givenName", RandomStringUtils.randomAlphabetic( 6 ) );
+        attrs.put( "sn", RandomStringUtils.randomAlphabetic( 9 ) );
+        attrs.put( "cn", RandomStringUtils.randomAlphabetic( 15 ) );
+        attrs.put( "initials", RandomStringUtils.randomAlphabetic( 2 ) );
+        attrs.put( "mail", RandomStringUtils.randomAlphabetic( 15 ) );
+        attrs.put( "userPassword", "password" );
+        attrs.put( "telephoneNumber", RandomStringUtils.randomNumeric( 10 ) );
+        attrs.put( "homePhone", RandomStringUtils.randomNumeric( 10 ) );
+        attrs.put( "pager", RandomStringUtils.randomNumeric( 10 ) );
+        attrs.put( "mobile", RandomStringUtils.randomNumeric( 10 ) );
+        attrs.put( "employeeNumber", String.valueOf( counter ) );
+        attrs.put( "street", RandomStringUtils.randomAlphabetic( 20 ) );
+        attrs.put( "l", RandomStringUtils.randomAlphabetic( 10 ) );
+        attrs.put( "st", RandomStringUtils.randomAlphabetic( 2 ) );
+        attrs.put( "postalCode", RandomStringUtils.randomAlphabetic( 5 ) );
+        attrs.put( "postalAddress", RandomStringUtils.randomAlphabetic( 20 ) );
+        attrs.put( "description", RandomStringUtils.randomAlphabetic( 20 ) );
+        return attrs;
+    }
+    
+
+    private void processOptions( CommandLine cmd )
+    {
+        if ( isDebugEnabled() )
+        {
+            System.out.println( "Processing options for capacity test ..." );
+        }
+
+        // -------------------------------------------------------------------
+        // figure out and error check the port value
+        // -------------------------------------------------------------------
+
+        if ( cmd.hasOption( 'p' ) ) // - user provided port w/ -p takes precedence
+        {
+            String val = cmd.getOptionValue( 'p' );
+            try
+            {
+                port = Integer.parseInt( val );
+            }
+            catch ( NumberFormatException e )
+            {
+                System.err.println( "port value of '" + val + "' is not a number" );
+                System.exit( 1 );
+            }
+
+            if ( port > AvailablePortFinder.MAX_PORT_NUMBER )
+            {
+                System.err.println( "port value of '" + val + "' is larger than max port number: "
+                    + AvailablePortFinder.MAX_PORT_NUMBER );
+                System.exit( 1 );
+            }
+            else if ( port < AvailablePortFinder.MIN_PORT_NUMBER )
+            {
+                System.err.println( "port value of '" + val + "' is smaller than the minimum port number: "
+                    + AvailablePortFinder.MIN_PORT_NUMBER );
+                System.exit( 1 );
+            }
+
+            if ( isDebugEnabled() )
+            {
+                System.out.println( "port overriden by -p option: " + port );
+            }
+        }
+        else if ( getConfiguration() != null )
+        {
+            port = getConfiguration().getLdapPort();
+
+            if ( isDebugEnabled() )
+            {
+                System.out.println( "port overriden by server.xml configuration: " + port );
+            }
+        }
+        else if ( isDebugEnabled() )
+        {
+            System.out.println( "port set to default: " + port );
+        }
+
+        // -------------------------------------------------------------------
+        // figure out the host value
+        // -------------------------------------------------------------------
+
+        if ( cmd.hasOption( 'h' ) )
+        {
+            host = cmd.getOptionValue( 'h' );
+
+            if ( isDebugEnabled() )
+            {
+                System.out.println( "host overriden by -h option: " + host );
+            }
+        }
+        else if ( isDebugEnabled() )
+        {
+            System.out.println( "host set to default: " + host );
+        }
+
+        // -------------------------------------------------------------------
+        // figure out the password value
+        // -------------------------------------------------------------------
+
+        if ( cmd.hasOption( 'w' ) )
+        {
+            password = cmd.getOptionValue( 'w' );
+
+            if ( isDebugEnabled() )
+            {
+                System.out.println( "password overriden by -w option: " + password );
+            }
+        }
+        else if ( isDebugEnabled() )
+        {
+            System.out.println( "password set to default: " + password );
+        }
+    }
+
+
+    public Options getOptions()
+    {
+        Options opts = new Options();
+        Option op = new Option( "f", "file", true, "file to output the stats to" );
+        op.setRequired( false );
+        opts.addOption( op );
+        op = new Option( "i", "install-path", true, "path to apacheds installation directory" );
+        op.setRequired( true );
+        opts.addOption( op );
+        op = new Option( "h", "host", true, "server host: defaults to localhost" );
+        op.setRequired( false );
+        opts.addOption( op );
+        op = new Option( "p", "port", true, "server port: defaults to 10389 or server.xml specified port" );
+        op.setRequired( false );
+        opts.addOption( op );
+        op = new Option( "w", "password", true, "the apacheds administrator's password: defaults to secret" );
+        op.setRequired( false );
+        opts.addOption( op );
+
+        
+        op = new Option( "s", "start", true, "start on id: number to start on (user.start)" );
+        op.setRequired( false );
+        opts.addOption( op );
+
+        op = new Option( "e", "end", true, "end on id: number to end on (user.end)" );
+        op.setRequired( false );
+        opts.addOption( op );
+
+        return opts;
+    }
+}



Mime
View raw message