Return-Path: Delivered-To: apmail-directory-commits-archive@www.apache.org Received: (qmail 36182 invoked from network); 12 Sep 2006 17:48:03 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (209.237.227.199) by minotaur.apache.org with SMTP; 12 Sep 2006 17:48:03 -0000 Received: (qmail 99452 invoked by uid 500); 12 Sep 2006 17:48:02 -0000 Delivered-To: apmail-directory-commits-archive@directory.apache.org Received: (qmail 99409 invoked by uid 500); 12 Sep 2006 17:48:02 -0000 Mailing-List: contact commits-help@directory.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@directory.apache.org Delivered-To: mailing list commits@directory.apache.org Received: (qmail 99388 invoked by uid 99); 12 Sep 2006 17:48:02 -0000 Received: from idunn.apache.osuosl.org (HELO idunn.apache.osuosl.org) (140.211.166.84) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 12 Sep 2006 10:48:02 -0700 Authentication-Results: idunn.apache.osuosl.org smtp.mail=akarasulu@apache.org; spf=permerror X-ASF-Spam-Status: No, hits=-9.8 required=5.0 tests=ALL_TRUSTED,NO_REAL_NAME Received-SPF: error (idunn.apache.osuosl.org: domain apache.org from 140.211.166.113 cause and error) Received: from ([140.211.166.113:62484] helo=eris.apache.org) by idunn.apache.osuosl.org (ecelerity 2.1 r(10620)) with ESMTP id 0D/51-03642-AD2F6054 for ; Tue, 12 Sep 2006 10:48:11 -0700 Received: by eris.apache.org (Postfix, from userid 65534) id E41551A981D; Tue, 12 Sep 2006 10:47:54 -0700 (PDT) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r442657 - in /directory/trunks: ./ apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/ apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/ apacheds/core/src/test/java/org/ap... Date: Tue, 12 Sep 2006 17:47:54 -0000 To: commits@directory.apache.org From: akarasulu@apache.org X-Mailer: svnmailer-1.1.0 Message-Id: <20060912174754.E41551A981D@eris.apache.org> X-Spam-Rating: minotaur.apache.org 1.6.2 0/1000/N Author: akarasulu Date: Tue Sep 12 10:47:52 2006 New Revision: 442657 URL: http://svn.apache.org/viewvc?view=rev&rev=442657 Log: merging btree index optiimization branch into 1.0 branch Added: directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeEnumeration.java - copied unchanged from r442612, directory/branches/apacheds/optimization2/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeEnumeration.java directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeIterator.java - copied unchanged from r442612, directory/branches/apacheds/optimization2/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeIterator.java directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeRedirect.java - copied unchanged from r442612, directory/branches/apacheds/optimization2/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeRedirect.java directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeTupleEnumeration.java - copied unchanged from r442612, directory/branches/apacheds/optimization2/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeTupleEnumeration.java directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/DupsEnumeration.java - copied unchanged from r442612, directory/branches/apacheds/optimization2/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/DupsEnumeration.java directory/trunks/apacheds/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeEnumerationTest.java - copied unchanged from r442612, directory/branches/apacheds/optimization2/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeEnumerationTest.java directory/trunks/apacheds/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeIteratorTest.java - copied unchanged from r442612, directory/branches/apacheds/optimization2/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeIteratorTest.java directory/trunks/apacheds/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeTupleEnumerationTest.java - copied unchanged from r442612, directory/branches/apacheds/optimization2/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeTupleEnumerationTest.java directory/trunks/apacheds/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTableDupsBTreeTest.java - copied unchanged from r442612, directory/branches/apacheds/optimization2/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTableDupsBTreeTest.java directory/trunks/apacheds/server-tools/src/main/java/org/apache/directory/server/tools/CapacityTestCommand.java - copied, changed from r442612, directory/branches/apacheds/optimization2/server-tools/src/main/java/org/apache/directory/server/tools/CapacityTestCommand.java Removed: directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/DupsEnumeration.java Modified: directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/BTreePartition.java directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/DefaultOptimizer.java directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/IndexConfiguration.java directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/MutableIndexConfiguration.java directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/NoDupsEnumeration.java directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmIndex.java directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmPartition.java directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTable.java directory/trunks/apacheds/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTableDupsTreeSetTest.java directory/trunks/apacheds/server-tools/src/main/java/org/apache/directory/server/tools/BaseCommand.java directory/trunks/apacheds/server-tools/src/main/java/org/apache/directory/server/tools/commands/dumpcmd/DumpCommandExecutor.java directory/trunks/pom.xml Modified: directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/BTreePartition.java URL: http://svn.apache.org/viewvc/directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/BTreePartition.java?view=diff&rev=442657&r1=442656&r2=442657 ============================================================================== --- directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/BTreePartition.java (original) +++ directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/BTreePartition.java Tue Sep 12 10:47:52 2006 @@ -172,6 +172,7 @@ Object nextObject = ii.next(); String name = null; int cacheSize = IndexConfiguration.DEFAULT_INDEX_CACHE_SIZE; + int numDupLimit = IndexConfiguration.DEFAULT_DUPLICATE_LIMIT; // no custom cacheSize info is available so default sticks if ( nextObject instanceof String ) @@ -186,10 +187,12 @@ IndexConfiguration indexConfiguration = ( IndexConfiguration ) nextObject; name = indexConfiguration.getAttributeId(); cacheSize = indexConfiguration.getCacheSize(); + numDupLimit = indexConfiguration.getDuplicateLimit(); if ( cacheSize <= 0 ) { - log.warn( "Cache size {} for index on attribute is null or negative. Using default value.", new Integer(cacheSize), name ); + log.warn( "Cache size {} for index on attribute is null or negative. Using default value.", + new Integer(cacheSize), name ); cacheSize = IndexConfiguration.DEFAULT_INDEX_CACHE_SIZE; } else @@ -197,6 +200,18 @@ log.info( "Using cache size of {} for index on attribute {}", new Integer( cacheSize ), name ); } + + if ( cacheSize <= 0 ) + { + log.warn( "Duplicate limit {} for index on attribute is null or negative. Using default value.", + new Integer(numDupLimit), name ); + cacheSize = IndexConfiguration.DEFAULT_INDEX_CACHE_SIZE; + } + else + { + log.info( "Using duplicate limit of {} for index on attribute {}", + new Integer( numDupLimit ), name ); + } } String oid = oidRegistry.getOid( name ); @@ -207,37 +222,37 @@ { if ( oid.equals( Oid.EXISTANCE ) ) { - setExistanceIndexOn( type, cacheSize ); + setExistanceIndexOn( type, cacheSize, numDupLimit ); customAddedSystemIndices.add( Oid.EXISTANCE ); } else if ( oid.equals( Oid.HIERARCHY ) ) { - setHierarchyIndexOn( type, cacheSize ); + setHierarchyIndexOn( type, cacheSize, numDupLimit ); customAddedSystemIndices.add( Oid.HIERARCHY ); } else if ( oid.equals( Oid.UPDN ) ) { - setUpdnIndexOn( type, cacheSize ); + setUpdnIndexOn( type, cacheSize, numDupLimit ); customAddedSystemIndices.add( Oid.UPDN ); } else if ( oid.equals( Oid.NDN ) ) { - setNdnIndexOn( type, cacheSize ); + setNdnIndexOn( type, cacheSize, numDupLimit ); customAddedSystemIndices.add( Oid.NDN ); } else if ( oid.equals( Oid.ONEALIAS ) ) { - setOneAliasIndexOn( type, cacheSize ); + setOneAliasIndexOn( type, cacheSize, numDupLimit ); customAddedSystemIndices.add( Oid.ONEALIAS ); } else if ( oid.equals( Oid.SUBALIAS ) ) { - setSubAliasIndexOn( type, cacheSize ); + setSubAliasIndexOn( type, cacheSize, numDupLimit ); customAddedSystemIndices.add( Oid.SUBALIAS); } else if ( oid.equals( Oid.ALIAS ) ) { - setAliasIndexOn( type, cacheSize ); + setAliasIndexOn( type, cacheSize, numDupLimit ); customAddedSystemIndices.add( Oid.ALIAS ); } else @@ -247,7 +262,7 @@ } else { - addIndexOn( type, cacheSize ); + addIndexOn( type, cacheSize, numDupLimit ); } } @@ -269,31 +284,38 @@ new Integer( IndexConfiguration.DEFAULT_INDEX_CACHE_SIZE ), systemIndexName ); if ( systemIndexName.equals( Oid.EXISTANCE ) ) { - setExistanceIndexOn( type, IndexConfiguration.DEFAULT_INDEX_CACHE_SIZE ); + setExistanceIndexOn( type, IndexConfiguration.DEFAULT_INDEX_CACHE_SIZE, + IndexConfiguration.DEFAULT_DUPLICATE_LIMIT ); } else if ( systemIndexName.equals( Oid.HIERARCHY ) ) { - setHierarchyIndexOn( type, IndexConfiguration.DEFAULT_INDEX_CACHE_SIZE ); + setHierarchyIndexOn( type, IndexConfiguration.DEFAULT_INDEX_CACHE_SIZE, + IndexConfiguration.DEFAULT_DUPLICATE_LIMIT ); } else if ( systemIndexName.equals( Oid.UPDN ) ) { - setUpdnIndexOn( type, IndexConfiguration.DEFAULT_INDEX_CACHE_SIZE ); + setUpdnIndexOn( type, IndexConfiguration.DEFAULT_INDEX_CACHE_SIZE, + IndexConfiguration.DEFAULT_DUPLICATE_LIMIT ); } else if ( systemIndexName.equals( Oid.NDN ) ) { - setNdnIndexOn( type, IndexConfiguration.DEFAULT_INDEX_CACHE_SIZE ); + setNdnIndexOn( type, IndexConfiguration.DEFAULT_INDEX_CACHE_SIZE, + IndexConfiguration.DEFAULT_DUPLICATE_LIMIT ); } else if ( systemIndexName.equals( Oid.ONEALIAS ) ) { - setOneAliasIndexOn( type, IndexConfiguration.DEFAULT_INDEX_CACHE_SIZE ); + setOneAliasIndexOn( type, IndexConfiguration.DEFAULT_INDEX_CACHE_SIZE, + IndexConfiguration.DEFAULT_DUPLICATE_LIMIT ); } else if ( systemIndexName.equals( Oid.SUBALIAS ) ) { - setSubAliasIndexOn( type, IndexConfiguration.DEFAULT_INDEX_CACHE_SIZE ); + setSubAliasIndexOn( type, IndexConfiguration.DEFAULT_INDEX_CACHE_SIZE, + IndexConfiguration.DEFAULT_DUPLICATE_LIMIT ); } else if ( systemIndexName.equals( Oid.ALIAS ) ) { - setAliasIndexOn( type, IndexConfiguration.DEFAULT_INDEX_CACHE_SIZE ); + setAliasIndexOn( type, IndexConfiguration.DEFAULT_INDEX_CACHE_SIZE, + IndexConfiguration.DEFAULT_DUPLICATE_LIMIT ); } else { @@ -460,7 +482,7 @@ // Index Operations // ------------------------------------------------------------------------ - public abstract void addIndexOn( AttributeType attribute, int cacheSize ) throws NamingException; + public abstract void addIndexOn( AttributeType attribute, int cacheSize, int numDupLimit ) throws NamingException; public abstract boolean hasUserIndexOn( String attribute ) throws NamingException; @@ -534,7 +556,7 @@ * * @param attrType the index on the ALIAS_ATTRIBUTE */ - public abstract void setAliasIndexOn( AttributeType attrType, int cacheSize ) throws NamingException; + public abstract void setAliasIndexOn( AttributeType attrType, int cacheSize, int numDupLimit ) throws NamingException; /** @@ -542,7 +564,7 @@ * * @param attrType the attribute existance Index */ - public abstract void setExistanceIndexOn( AttributeType attrType, int cacheSize ) throws NamingException; + public abstract void setExistanceIndexOn( AttributeType attrType, int cacheSize, int numDupLimit ) throws NamingException; /** @@ -550,7 +572,7 @@ * * @param attrType the hierarchy Index */ - public abstract void setHierarchyIndexOn( AttributeType attrType, int cacheSize ) throws NamingException; + public abstract void setHierarchyIndexOn( AttributeType attrType, int cacheSize, int numDupLimit ) throws NamingException; /** @@ -558,7 +580,7 @@ * * @param attrType the updn Index */ - public abstract void setUpdnIndexOn( AttributeType attrType, int cacheSize ) throws NamingException; + public abstract void setUpdnIndexOn( AttributeType attrType, int cacheSize, int numDupLimit ) throws NamingException; /** @@ -566,7 +588,7 @@ * * @param attrType the ndn Index */ - public abstract void setNdnIndexOn( AttributeType attrType, int cacheSize ) throws NamingException; + public abstract void setNdnIndexOn( AttributeType attrType, int cacheSize, int numDupLimit ) throws NamingException; /** @@ -576,7 +598,7 @@ * * @param attrType a one level alias index */ - public abstract void setOneAliasIndexOn( AttributeType attrType, int cacheSize ) throws NamingException; + public abstract void setOneAliasIndexOn( AttributeType attrType, int cacheSize, int numDupLimit ) throws NamingException; /** @@ -586,7 +608,7 @@ * * @param attrType a subtree alias index */ - public abstract void setSubAliasIndexOn( AttributeType attrType, int cacheSize ) throws NamingException; + public abstract void setSubAliasIndexOn( AttributeType attrType, int cacheSize, int numDupLimit ) throws NamingException; public abstract Index getUserIndex( String attribute ) throws IndexNotFoundException; Modified: directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/DefaultOptimizer.java URL: http://svn.apache.org/viewvc/directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/DefaultOptimizer.java?view=diff&rev=442657&r1=442656&r2=442657 ============================================================================== --- directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/DefaultOptimizer.java (original) +++ directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/DefaultOptimizer.java Tue Sep 12 10:47:52 2006 @@ -178,7 +178,7 @@ */ private BigInteger getConjunctionScan( BranchNode node ) throws NamingException { - BigInteger count = BigInteger.valueOf( Integer.MAX_VALUE ); + BigInteger count = MAX; ArrayList children = node.getChildren(); for ( int ii = 0; ii < children.size(); ii++ ) @@ -243,6 +243,12 @@ ExprNode child = ( ExprNode ) children.get( ii ); annotate( child ); total = total.add( ( BigInteger ) child.get( "count" ) ); + } + + // we don't want values bigger than Integer.MAX_VALUE + if ( total.compareTo( MAX ) > 0 ) + { + total = MAX; } return total; Modified: directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/IndexConfiguration.java URL: http://svn.apache.org/viewvc/directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/IndexConfiguration.java?view=diff&rev=442657&r1=442656&r2=442657 ============================================================================== --- directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/IndexConfiguration.java (original) +++ directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/IndexConfiguration.java Tue Sep 12 10:47:52 2006 @@ -29,9 +29,12 @@ public class IndexConfiguration { public static final int DEFAULT_INDEX_CACHE_SIZE = 100; + + public static final int DEFAULT_DUPLICATE_LIMIT = 512; private String attributeId; private int cacheSize = DEFAULT_INDEX_CACHE_SIZE; + private int duplicateLimit = DEFAULT_DUPLICATE_LIMIT; protected void setAttributeId( String attributeId ) @@ -52,9 +55,21 @@ } + protected void setDuplicateLimit( int duplicateLimit ) + { + this.duplicateLimit = duplicateLimit; + } + + public int getCacheSize() { return cacheSize; + } + + + public int getDuplicateLimit() + { + return duplicateLimit; } Modified: directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/MutableIndexConfiguration.java URL: http://svn.apache.org/viewvc/directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/MutableIndexConfiguration.java?view=diff&rev=442657&r1=442656&r2=442657 ============================================================================== --- directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/MutableIndexConfiguration.java (original) +++ directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/MutableIndexConfiguration.java Tue Sep 12 10:47:52 2006 @@ -38,4 +38,10 @@ { super.setCacheSize( cacheSize ); } + + + public void setDuplicateLimit( int duplicateLimit ) + { + super.setDuplicateLimit( duplicateLimit ); + } } Modified: directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/NoDupsEnumeration.java URL: http://svn.apache.org/viewvc/directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/NoDupsEnumeration.java?view=diff&rev=442657&r1=442656&r2=442657 ============================================================================== --- directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/NoDupsEnumeration.java (original) +++ directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/NoDupsEnumeration.java Tue Sep 12 10:47:52 2006 @@ -147,7 +147,7 @@ * @return true if this NamingEnumeration is ascending on keys, false * otherwise. */ - boolean doAscendingScan() + public boolean doAscendingScan() { return doAscendingScan; } Modified: directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmIndex.java URL: http://svn.apache.org/viewvc/directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmIndex.java?view=diff&rev=442657&r1=442656&r2=442657 ============================================================================== --- directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmIndex.java (original) +++ directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmIndex.java Tue Sep 12 10:47:52 2006 @@ -38,6 +38,7 @@ import org.apache.directory.server.core.ServerUtils; import org.apache.directory.server.core.partition.impl.btree.Index; import org.apache.directory.server.core.partition.impl.btree.IndexComparator; +import org.apache.directory.server.core.partition.impl.btree.IndexConfiguration; import org.apache.directory.server.core.partition.impl.btree.IndexEnumeration; import org.apache.directory.server.core.schema.SerializableComparator; import org.apache.directory.shared.ldap.schema.AttributeType; @@ -70,6 +71,8 @@ * will cache values for us. */ private SynchronizedLRUMap keyCache = null; + + private int numDupLimit = IndexConfiguration.DEFAULT_DUPLICATE_LIMIT; // ------------------------------------------------------------------------ @@ -94,8 +97,9 @@ // } - public JdbmIndex( AttributeType attribute, File wkDirPath, int cacheSize ) throws NamingException + public JdbmIndex( AttributeType attribute, File wkDirPath, int cacheSize, int numDupLimit ) throws NamingException { + this.numDupLimit = numDupLimit; File file = new File( wkDirPath.getPath() + File.separator + attribute.getName() ); this.attribute = attribute; keyCache = new SynchronizedLRUMap( cacheSize ); @@ -134,7 +138,7 @@ * primary keys. A value for an attribute can occur several times in * different entries so the forward map can have more than one value. */ - forward = new JdbmTable( attribute.getName() + FORWARD_BTREE, true, recMan, new IndexComparator( comp, true ) ); + forward = new JdbmTable( attribute.getName() + FORWARD_BTREE, true, numDupLimit, recMan, new IndexComparator( comp, true ) ); /* * Now the reverse map stores the primary key into the master table as @@ -142,7 +146,7 @@ * is single valued according to its specification based on a schema * then duplicate keys should not be allowed within the reverse table. */ - reverse = new JdbmTable( attribute.getName() + REVERSE_BTREE, !attribute.isSingleValue(), recMan, + reverse = new JdbmTable( attribute.getName() + REVERSE_BTREE, !attribute.isSingleValue(), numDupLimit, recMan, new IndexComparator( comp, false ) ); } Modified: directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmPartition.java URL: http://svn.apache.org/viewvc/directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmPartition.java?view=diff&rev=442657&r1=442656&r2=442657 ============================================================================== --- directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmPartition.java (original) +++ directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmPartition.java Tue Sep 12 10:47:52 2006 @@ -325,9 +325,9 @@ // I N D E X M E T H O D S // ------------------------------------------------------------------------ - public void addIndexOn( AttributeType spec, int cacheSize ) throws NamingException + public void addIndexOn( AttributeType spec, int cacheSize, int numDupLimit ) throws NamingException { - Index idx = new JdbmIndex( spec, workingDirectory, cacheSize ); + Index idx = new JdbmIndex( spec, workingDirectory, cacheSize, numDupLimit ); indices.put( spec.getOid(), idx ); } @@ -338,7 +338,7 @@ } - public void setExistanceIndexOn( AttributeType attrType, int cacheSize ) throws NamingException + public void setExistanceIndexOn( AttributeType attrType, int cacheSize, int numDupLimit ) throws NamingException { if ( existanceIdx != null ) { @@ -346,7 +346,7 @@ throw e; } - existanceIdx = new JdbmIndex( attrType, workingDirectory, cacheSize ); + existanceIdx = new JdbmIndex( attrType, workingDirectory, cacheSize, numDupLimit ); sysIndices.put( attrType.getOid(), existanceIdx ); } @@ -357,7 +357,7 @@ } - public void setHierarchyIndexOn( AttributeType attrType, int cacheSize ) throws NamingException + public void setHierarchyIndexOn( AttributeType attrType, int cacheSize, int numDupLimit ) throws NamingException { if ( hierarchyIdx != null ) { @@ -365,7 +365,7 @@ throw e; } - hierarchyIdx = new JdbmIndex( attrType, workingDirectory, cacheSize ); + hierarchyIdx = new JdbmIndex( attrType, workingDirectory, cacheSize, numDupLimit ); sysIndices.put( attrType.getOid(), hierarchyIdx ); } @@ -376,7 +376,7 @@ } - public void setAliasIndexOn( AttributeType attrType, int cacheSize ) throws NamingException + public void setAliasIndexOn( AttributeType attrType, int cacheSize, int numDupLimit ) throws NamingException { if ( aliasIdx != null ) { @@ -384,7 +384,7 @@ throw e; } - aliasIdx = new JdbmIndex( attrType, workingDirectory, cacheSize ); + aliasIdx = new JdbmIndex( attrType, workingDirectory, cacheSize, numDupLimit ); sysIndices.put( attrType.getOid(), aliasIdx ); } @@ -395,7 +395,7 @@ } - public void setOneAliasIndexOn( AttributeType attrType, int cacheSize ) throws NamingException + public void setOneAliasIndexOn( AttributeType attrType, int cacheSize, int numDupLimit ) throws NamingException { if ( oneAliasIdx != null ) { @@ -403,7 +403,7 @@ throw e; } - oneAliasIdx = new JdbmIndex( attrType, workingDirectory, cacheSize ); + oneAliasIdx = new JdbmIndex( attrType, workingDirectory, cacheSize, numDupLimit ); sysIndices.put( attrType.getOid(), oneAliasIdx ); } @@ -414,7 +414,7 @@ } - public void setSubAliasIndexOn( AttributeType attrType, int cacheSize ) throws NamingException + public void setSubAliasIndexOn( AttributeType attrType, int cacheSize, int numDupLimit ) throws NamingException { if ( subAliasIdx != null ) { @@ -422,7 +422,7 @@ throw e; } - subAliasIdx = new JdbmIndex( attrType, workingDirectory, cacheSize ); + subAliasIdx = new JdbmIndex( attrType, workingDirectory, cacheSize, numDupLimit ); sysIndices.put( attrType.getOid(), subAliasIdx ); } @@ -433,7 +433,7 @@ } - public void setUpdnIndexOn( AttributeType attrType, int cacheSize ) throws NamingException + public void setUpdnIndexOn( AttributeType attrType, int cacheSize, int numDupLimit ) throws NamingException { if ( updnIdx != null ) { @@ -441,7 +441,7 @@ throw e; } - updnIdx = new JdbmIndex( attrType, workingDirectory, cacheSize ); + updnIdx = new JdbmIndex( attrType, workingDirectory, cacheSize, numDupLimit ); sysIndices.put( attrType.getOid(), updnIdx ); } @@ -452,7 +452,7 @@ } - public void setNdnIndexOn( AttributeType attrType, int cacheSize ) throws NamingException + public void setNdnIndexOn( AttributeType attrType, int cacheSize, int numDupLimit ) throws NamingException { if ( ndnIdx != null ) { @@ -460,7 +460,7 @@ throw e; } - ndnIdx = new JdbmIndex( attrType, workingDirectory, cacheSize ); + ndnIdx = new JdbmIndex( attrType, workingDirectory, cacheSize, numDupLimit ); sysIndices.put( attrType.getOid(), ndnIdx ); } Modified: directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTable.java URL: http://svn.apache.org/viewvc/directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTable.java?view=diff&rev=442657&r1=442656&r2=442657 ============================================================================== --- directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTable.java (original) +++ directory/trunks/apacheds/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTable.java Tue Sep 12 10:47:52 2006 @@ -23,8 +23,10 @@ import java.io.IOException; import java.util.ArrayList; import java.util.Collections; +import java.util.HashMap; import java.util.Iterator; import java.util.Set; +import java.util.Map; import java.util.SortedSet; import java.util.TreeSet; @@ -36,7 +38,7 @@ import jdbm.helper.TupleBrowser; import org.apache.commons.collections.iterators.ArrayIterator; -import org.apache.directory.server.core.partition.impl.btree.DupsEnumeration; +import org.apache.directory.server.core.partition.impl.btree.IndexConfiguration; import org.apache.directory.server.core.partition.impl.btree.KeyOnlyComparator; import org.apache.directory.server.core.partition.impl.btree.NoDupsEnumeration; import org.apache.directory.server.core.partition.impl.btree.Table; @@ -46,6 +48,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; @@ -77,7 +81,11 @@ /** */ private TupleRenderer renderer; + private int numDupLimit = IndexConfiguration.DEFAULT_DUPLICATE_LIMIT; + private Map duplicateBtrees = new HashMap(); + + // ------------------------------------------------------------------------ // C O N S T R U C T O R // ------------------------------------------------------------------------ @@ -92,9 +100,11 @@ * @param comparator a tuple comparator * @throws NamingException if the table's file cannot be created */ - public JdbmTable( String name, boolean allowsDuplicates, RecordManager manager, TupleComparator comparator ) + public JdbmTable( String name, boolean allowsDuplicates, int numDupLimit, + RecordManager manager, TupleComparator comparator ) throws NamingException { + this.numDupLimit = numDupLimit; this.name = name; this.recMan = manager; this.comparator = comparator; @@ -155,7 +165,7 @@ */ public JdbmTable( String name, RecordManager manager, SerializableComparator keyComparator ) throws NamingException { - this( name, false, manager, new KeyOnlyComparator( keyComparator ) ); + this( name, false, Integer.MAX_VALUE, manager, new KeyOnlyComparator( keyComparator ) ); } @@ -251,14 +261,32 @@ } } - TreeSet set = ( TreeSet ) getRaw( key ); + Object values = getRaw( key ); + + if ( values == null ) + { + return 0; + } + + // ------------------------------------------------------------------- + // Handle the use of a TreeSet for storing duplicates + // ------------------------------------------------------------------- - if ( set != null ) + if ( values instanceof TreeSet ) { - return set.size(); + return ( ( TreeSet ) values ).size(); } - return 0; + // ------------------------------------------------------------------- + // Handle the use of a BTree for storing duplicates + // ------------------------------------------------------------------- + + if ( values instanceof BTreeRedirect ) + { + return getBTree( ( BTreeRedirect ) values ).size(); + } + + throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." ); } @@ -270,7 +298,7 @@ return count; } - + // ------------------------------------------------------------------------ // get/has/put/remove Methods and Overloads // ------------------------------------------------------------------------ @@ -280,10 +308,23 @@ */ public Object get( Object key ) throws NamingException { - if ( allowsDuplicates ) + if ( ! allowsDuplicates ) { - TreeSet set = ( TreeSet ) getRaw( key ); - if ( null == set || set.size() == 0 ) + return getRaw( key ); + } + + Object values = getRaw( key ); + + if ( values == null ) + { + return null; + } + + if ( values instanceof TreeSet ) + { + TreeSet set = ( TreeSet ) values; + + if ( set.size() == 0 ) { return null; } @@ -293,20 +334,30 @@ } } - Object value = getRaw( key ); - return value; + if ( values instanceof BTreeRedirect ) + { + BTree tree = getBTree( ( BTreeRedirect ) values ); + + if ( 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." ); } - + /** * @see Table#has(java.lang.Object, * java.lang.Object, boolean) */ public boolean has( Object key, Object val, boolean isGreaterThan ) throws NamingException { - TreeSet set = null; - SortedSet subset = null; - if ( !allowsDuplicates ) { Object rval = getRaw( key ); @@ -316,17 +367,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; @@ -335,30 +386,54 @@ return false; } - set = ( TreeSet ) getRaw( key ); - - if ( null == set || set.size() == 0 ) + Object values = getRaw( key ); + + if ( values == null ) { return false; } - - if ( isGreaterThan ) + + if ( values instanceof TreeSet ) { - subset = set.tailSet( val ); + TreeSet set = ( TreeSet ) values; + SortedSet subset = null; + + if ( 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; } - else + + if ( values instanceof BTreeRedirect ) { - subset = set.headSet( val ); - } + BTree tree = getBTree( ( BTreeRedirect ) values ); + if ( tree.size() == 0 ) + { + return false; + } - if ( subset.size() > 0 || set.contains( val ) ) - { - return true; + return btreeHas( tree, val, isGreaterThan ); } - - return false; + + throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." ); } - + /** * @see Table#has(java.lang.Object, boolean) @@ -461,28 +536,38 @@ */ 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 obj = getRaw( key ); - - if ( null == obj ) + + Object values = getRaw( key ); + + if ( values == null ) { return false; } - - return obj.equals( value ); + + if ( values instanceof TreeSet ) + { + return ( ( TreeSet ) values ).contains( value ); + } + + if ( values instanceof BTreeRedirect ) + { + return btreeHas( getBTree( ( BTreeRedirect ) values ), value ); + } + + throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." ); } - + /** * @see Table#has(java.lang.Object) @@ -501,35 +586,69 @@ { Object replaced = null; - if ( allowsDuplicates ) + if ( ! allowsDuplicates ) { - TreeSet set = ( TreeSet ) getRaw( key ); + replaced = putRaw( key, value, true ); - if ( null == set ) + if ( null == replaced ) { - set = new TreeSet( comparator.getValueComparator() ); + count++; } - else if ( set.contains( value ) ) + + return replaced; + } + + Object values = getRaw( key ); + + if ( values == null ) + { + values = new TreeSet( comparator.getValueComparator() ); + } + + if ( values instanceof TreeSet ) + { + TreeSet set = ( TreeSet ) values; + + if ( set.contains( value ) ) { return value; } - - set.add( value ); - putRaw( key, set, true ); - count++; + + boolean addSuccessful = set.add( value ); + + if ( set.size() > numDupLimit ) + { + BTree tree = convertToBTree( set ); + BTreeRedirect redirect = new BTreeRedirect( tree.getRecid() ); + replaced = putRaw( key, redirect, true ); + } + else + { + replaced = putRaw( key, set, true ); + } + + if ( addSuccessful ) + { + count++; + return replaced; + } return null; } - - replaced = putRaw( key, value, true ); - - if ( null == replaced ) + + if ( values instanceof BTreeRedirect ) { - count++; + BTree tree = getBTree( ( BTreeRedirect ) values ); + if ( insertDupIntoBTree( tree, value ) ) + { + count++; + return values; + } + return null; } - - return replaced; + + throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." ); } - + /** * @see Table#put(java.lang.Object, @@ -537,8 +656,6 @@ */ 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 @@ -563,32 +680,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 ) + Object storedValues = getRaw( key ); + + if ( storedValues == null ) { - set = new TreeSet( comparator.getValueComparator() ); + storedValues = new TreeSet( comparator.getValueComparator() ); } - - while ( values.hasMore() ) + + if ( storedValues instanceof TreeSet ) { - Object val = values.next(); - - if ( !set.contains( val ) ) + /* + * 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; + while ( values.hasMore() ) + { + Object val = values.next(); + + if ( !set.contains( val ) ) + { + boolean isAddSuccessful = set.add( val ); + if ( isAddSuccessful ) + { + count++; + } + } + } + + if ( set.size() > numDupLimit ) { - set.add( val ); - count++; + BTree tree = convertToBTree( set ); + BTreeRedirect redirect = new BTreeRedirect( tree.getRecid() ); + return putRaw( key, redirect, true ); + } + else + { + return putRaw( key, set, true ); } } + + if ( storedValues instanceof BTreeRedirect ) + { + BTree tree = getBTree( ( BTreeRedirect ) storedValues ); + while ( values.hasMore() ) + { + Object val = values.next(); + + if ( insertDupIntoBTree( tree, val ) ) + { + count++; + } + } - // Return the raw TreeSet - return putRaw( key, set, true ); + return storedValues; + } + + throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." ); } @@ -598,15 +748,32 @@ */ public Object remove( Object key, Object value ) throws NamingException { - if ( allowsDuplicates ) + if ( ! allowsDuplicates ) { - TreeSet set = ( TreeSet ) getRaw( key ); - - if ( null == set ) + Object oldValue = getRaw( key ); + + // Remove the value only if it is the same as value. + if ( oldValue != null && oldValue.equals( value ) ) { - return null; + removeRaw( key ); + count--; + return oldValue; } + return null; + } + + Object values = getRaw( key ); + + if ( values == null ) + { + return null; + } + + if ( values instanceof TreeSet ) + { + TreeSet set = ( TreeSet ) values; + // If removal succeeds then remove if set is empty else replace it if ( set.remove( value ) ) { @@ -627,17 +794,27 @@ return null; } - Object oldValue = getRaw( key ); - - // Remove the value only if it is the same as value. - if ( oldValue != null && oldValue.equals( value ) ) + // 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 BTreeRedirect ) { - removeRaw( key ); - count--; - return oldValue; + BTree tree = getBTree( ( BTreeRedirect ) values ); + + if ( removeDupFromBTree( tree, value ) ) + { + if ( tree.size() == 0 ) + { + removeRaw( key ); + } + + count--; + return value; + } + + return null; } - - return null; + + throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." ); } @@ -647,8 +824,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 @@ -673,43 +848,75 @@ 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 ) + Object storedValues = getRaw( key ); + + if ( storedValues == null ) { 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. - */ - Object firstValue = null; - while ( values.hasMore() ) + + if ( storedValues instanceof TreeSet ) { - Object val = values.next(); - - // get the first value - if ( firstValue == null ) - { - firstValue = val; - } + /* + * 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; + + /* + * 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. + */ + Object firstValue = null; + while ( values.hasMore() ) + { + Object val = values.next(); + + // get the first value + if ( firstValue == null ) + { + firstValue = val; + } - if ( set.contains( val ) ) - { - set.remove( val ); - count--; + if ( set.contains( val ) ) + { + set.remove( val ); + count--; + } } + + // Return the raw TreeSet and put the changed one back. + putRaw( key, set, true ); + return firstValue; } - - // Return the raw TreeSet and put the changed one back. - putRaw( key, set, true ); - return firstValue; + + // 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 BTreeRedirect ) + { + BTree tree = getBTree( ( BTreeRedirect ) storedValues ); + Object first = null; + while ( values.hasMore() ) + { + Object val = values.next(); + + if ( removeDupFromBTree( tree, val ) ) + { + count--; + + if ( first == null ) + { + first = val; + } + } + } + + return first; + } + + throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." ); } @@ -725,15 +932,27 @@ return null; } - if ( allowsDuplicates ) + if ( ! allowsDuplicates ) + { + this.count--; + return returned; + } + + if ( returned instanceof TreeSet ) { TreeSet set = ( TreeSet ) returned; this.count -= set.size(); return set.first(); } - - this.count--; - return returned; + + if ( returned instanceof BTreeRedirect ) + { + BTree tree = getBTree( ( BTreeRedirect ) returned ); + this.count -= tree.size(); + return removeAll( tree ); + } + + throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." ); } @@ -742,8 +961,6 @@ */ public NamingEnumeration listValues( Object key ) throws NamingException { - TreeSet set = null; - if ( !allowsDuplicates ) { Object value = get( key ); @@ -758,43 +975,56 @@ } } - set = ( TreeSet ) getRaw( key ); - if ( null == set ) + Object values = getRaw( key ); + + if ( values == null ) { return new EmptyEnumeration(); } - - final Iterator list = set.iterator(); - return new NamingEnumeration() + + if ( values instanceof TreeSet ) { - public void close() - { - } - - - public Object nextElement() + TreeSet set = ( TreeSet ) values; + final Iterator list = set.iterator(); + return new NamingEnumeration() { - return list.next(); - } - - - public Object next() - { - return list.next(); - } - - - public boolean hasMore() - { - return list.hasNext(); - } - - - public boolean hasMoreElements() - { - return list.hasNext(); - } - }; + 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 BTreeRedirect ) + { + BTree tree = getBTree( ( BTreeRedirect ) values ); + return new BTreeEnumeration( tree ); + } + + throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." ); } @@ -823,7 +1053,7 @@ if ( allowsDuplicates ) { - return new DupsEnumeration( ( NoDupsEnumeration ) list ); + return new DupsEnumeration( this, ( NoDupsEnumeration ) list ); } return list; @@ -835,8 +1065,6 @@ */ public NamingEnumeration listTuples( Object key ) throws NamingException { - TreeSet set = null; - // Handle single and zero value returns without duplicates enabled if ( !allowsDuplicates ) { @@ -852,16 +1080,28 @@ } } - set = ( TreeSet ) getRaw( key ); - if ( set == null ) + Object values = getRaw( key ); + + if ( values == null ) { return new EmptyEnumeration(); } + + if ( values instanceof TreeSet ) + { + TreeSet set = ( TreeSet ) values; + Object[] objs = new Object[set.size()]; + objs = set.toArray( objs ); + ArrayIterator iterator = new ArrayIterator( objs ); + return new TupleEnumeration( key, iterator ); + } + + if ( values instanceof BTreeRedirect ) + { + return new BTreeTupleEnumeration( getBTree( ( BTreeRedirect ) values ), 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." ); } @@ -920,7 +1160,7 @@ if ( allowsDuplicates ) { - list = new DupsEnumeration( ( NoDupsEnumeration ) list ); + list = new DupsEnumeration( this, ( NoDupsEnumeration ) list ); } return list; @@ -933,8 +1173,6 @@ */ public NamingEnumeration listTuples( Object key, Object val, boolean isGreaterThan ) throws NamingException { - TreeSet set = null; - if ( !allowsDuplicates ) { throw new UnsupportedOperationException( "Cannot list tuples over duplicates on table that " + @@ -963,51 +1201,65 @@ // return new EmptyEnumeration(); } - set = ( TreeSet ) getRaw( key ); - if ( set == null ) + Object values = getRaw( key ); + + if ( values == null ) { return new EmptyEnumeration(); } - if ( isGreaterThan ) + if ( values instanceof TreeSet ) { - Set tailSet = set.tailSet( val ); - - if ( tailSet.isEmpty() ) + TreeSet set = ( TreeSet ) values; + + if ( isGreaterThan ) { - return new EmptyEnumeration(); + Set tailSet = set.tailSet( val ); + + if ( tailSet.isEmpty() ) + { + return new EmptyEnumeration(); + } + + Object[] objs = new Object[tailSet.size()]; + objs = tailSet.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( headset.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() ); } - - Object[] objs = new Object[tailSet.size()]; - objs = tailSet.toArray( objs ); - ArrayIterator iterator = new ArrayIterator( objs ); - return new TupleEnumeration( key, iterator ); } - else + + if ( values instanceof BTreeRedirect ) { - // 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( headset.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() ); + return new BTreeTupleEnumeration( getBTree( ( BTreeRedirect ) values ), + comparator.getValueComparator(), key, val, isGreaterThan ); } - } + throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." ); + } + // ------------------------------------------------------------------------ // Maintenance Operations @@ -1173,4 +1425,231 @@ return val; } + + + BTree getBTree( BTreeRedirect redirect ) throws NamingException + { + if ( duplicateBtrees.containsKey( redirect.getRecId() ) ) + { + return ( BTree ) duplicateBtrees.get( redirect.getRecId() ); + } + + try + { + BTree tree = BTree.load( recMan, redirect.getRecId().longValue() ); + duplicateBtrees.put( redirect.getRecId(), tree ); + return tree; + } + catch ( IOException e ) + { + LdapNamingException lne = new LdapNamingException( "Failed to load btree", + ResultCodeEnum.OTHER ); + lne.setRootCause( e ); + throw lne; + } + } + + + 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; + } + } + + + private boolean btreeHas( BTree tree, Object key, boolean isGreaterThan ) throws NamingException + { + jdbm.helper.Tuple tuple = new jdbm.helper.Tuple(); + + try + { + 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 + { + /* + * Calls to getPrevious() will return a lower key even + * if there exists a key equal to the one searched + * for. Since isGreaterThan when false really means + * 'less than or equal to' we must check to see if + * the key in front is equal to the key argument provided. + */ + success = browser.getNext( tuple ); + if ( success ) + { + Object biggerKey = tuple.getKey(); + if ( comparator.compareValue( key, biggerKey ) == 0 ) + { + return true; + } + } + return false; + } + } + } + catch ( IOException e ) + { + LdapNamingException lne = new LdapNamingException( "IO failure while acessing btree: " + + e.getMessage(), ResultCodeEnum.OTHER ); + lne.setRootCause( e ); + throw lne; + } + } + + + 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 ) + { + if ( comparator.compareValue( key, tuple.getKey() ) == 0 ) + { + return true; + } + } + + return false; + } + catch ( IOException e ) + { + LdapNamingException lne = new LdapNamingException( "IO failure while acessing btree: " + + e.getMessage(), ResultCodeEnum.OTHER ); + lne.setRootCause( e ); + throw lne; + } + } + + + 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 = null; + if ( tree.find( value ) != null ) + { + 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; + } + } + + + private Object removeAll( BTree tree ) throws NamingException + { + Object first = null; + jdbm.helper.Tuple jdbmTuple = new jdbm.helper.Tuple(); + TupleBrowser browser; + try + { + browser = tree.browse(); + while( browser.getNext( jdbmTuple ) ) + { + tree.remove( jdbmTuple.getKey() ); + if ( first == null ) + { + first = jdbmTuple.getKey(); + } + } + } + catch ( IOException e ) + { + LdapNamingException lne = new LdapNamingException( "Failed to remove all keys in BTree", + ResultCodeEnum.OTHER ); + lne.setRootCause( e ); + throw lne; + } + + return first; + } } + Modified: directory/trunks/apacheds/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTableDupsTreeSetTest.java URL: http://svn.apache.org/viewvc/directory/trunks/apacheds/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTableDupsTreeSetTest.java?view=diff&rev=442657&r1=442656&r2=442657 ============================================================================== --- directory/trunks/apacheds/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTableDupsTreeSetTest.java (original) +++ directory/trunks/apacheds/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTableDupsTreeSetTest.java Tue Sep 12 10:47:52 2006 @@ -108,7 +108,7 @@ rm = new BaseRecordManager( tempFile.getAbsolutePath() ); // make sure the table never uses a btree for duplicates - table = new JdbmTable( "test", true, rm, comparator ); + table = new JdbmTable( "test", true, Integer.MAX_VALUE, rm, comparator ); for ( BigInteger ii = BigInteger.ZERO; ii.intValue() < 3; ii = ii.add( BigInteger.ONE ) ) { Modified: directory/trunks/apacheds/server-tools/src/main/java/org/apache/directory/server/tools/BaseCommand.java URL: http://svn.apache.org/viewvc/directory/trunks/apacheds/server-tools/src/main/java/org/apache/directory/server/tools/BaseCommand.java?view=diff&rev=442657&r1=442656&r2=442657 ============================================================================== --- directory/trunks/apacheds/server-tools/src/main/java/org/apache/directory/server/tools/BaseCommand.java (original) +++ directory/trunks/apacheds/server-tools/src/main/java/org/apache/directory/server/tools/BaseCommand.java Tue Sep 12 10:47:52 2006 @@ -110,6 +110,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" ); Copied: directory/trunks/apacheds/server-tools/src/main/java/org/apache/directory/server/tools/CapacityTestCommand.java (from r442612, directory/branches/apacheds/optimization2/server-tools/src/main/java/org/apache/directory/server/tools/CapacityTestCommand.java) URL: http://svn.apache.org/viewvc/directory/trunks/apacheds/server-tools/src/main/java/org/apache/directory/server/tools/CapacityTestCommand.java?view=diff&rev=442657&p1=directory/branches/apacheds/optimization2/server-tools/src/main/java/org/apache/directory/server/tools/CapacityTestCommand.java&r1=442612&p2=directory/trunks/apacheds/server-tools/src/main/java/org/apache/directory/server/tools/CapacityTestCommand.java&r2=442657 ============================================================================== --- directory/branches/apacheds/optimization2/server-tools/src/main/java/org/apache/directory/server/tools/CapacityTestCommand.java (original) +++ directory/trunks/apacheds/server-tools/src/main/java/org/apache/directory/server/tools/CapacityTestCommand.java Tue Sep 12 10:47:52 2006 @@ -47,7 +47,7 @@ * @author Apache Directory Project * @version $Rev$ */ -public class CapacityTestCommand extends ToolCommand +public class CapacityTestCommand extends BaseToolCommand { public static final String PORT_RANGE = "(" + AvailablePortFinder.MIN_PORT_NUMBER + ", " + AvailablePortFinder.MAX_PORT_NUMBER + ")"; @@ -67,7 +67,7 @@ public void execute( CommandLine cmdline ) throws Exception { processOptions( cmdline ); - getLayout().verifyInstallation(); +// getLayout().verifyInstallation(); String outputFile = cmdline.getOptionValue( 'f' ); PrintWriter out = null; @@ -199,15 +199,15 @@ 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 ( 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 ); Modified: directory/trunks/apacheds/server-tools/src/main/java/org/apache/directory/server/tools/commands/dumpcmd/DumpCommandExecutor.java URL: http://svn.apache.org/viewvc/directory/trunks/apacheds/server-tools/src/main/java/org/apache/directory/server/tools/commands/dumpcmd/DumpCommandExecutor.java?view=diff&rev=442657&r1=442656&r2=442657 ============================================================================== --- directory/trunks/apacheds/server-tools/src/main/java/org/apache/directory/server/tools/commands/dumpcmd/DumpCommandExecutor.java (original) +++ directory/trunks/apacheds/server-tools/src/main/java/org/apache/directory/server/tools/commands/dumpcmd/DumpCommandExecutor.java Tue Sep 12 10:47:52 2006 @@ -308,7 +308,7 @@ JdbmMasterTable master = new JdbmMasterTable( recMan ); AttributeType attributeType = bootstrapRegistries.getAttributeTypeRegistry().lookup( "apacheUpdn" ); - JdbmIndex idIndex = new JdbmIndex( attributeType, partitionDirectory, 1000 ); + JdbmIndex idIndex = new JdbmIndex( attributeType, partitionDirectory, 1000, 1000 ); out.println( "#---------------------" ); NamingEnumeration list = master.listTuples(); Modified: directory/trunks/pom.xml URL: http://svn.apache.org/viewvc/directory/trunks/pom.xml?view=diff&rev=442657&r1=442656&r2=442657 ============================================================================== --- directory/trunks/pom.xml (original) +++ directory/trunks/pom.xml Tue Sep 12 10:47:52 2006 @@ -47,7 +47,7 @@ snapshots snapshot plugins - http://snapshots.maven.codehaus.org/maven2 + http://snapshots.repository.codehaus.org apache.snapshots