You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by ak...@apache.org on 2006/09/04 07:50:09 UTC
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...
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;
+ }
+}