Return-Path: Delivered-To: apmail-directory-commits-archive@www.apache.org Received: (qmail 22428 invoked from network); 6 Sep 2006 01:05:38 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (209.237.227.199) by minotaur.apache.org with SMTP; 6 Sep 2006 01:05:38 -0000 Received: (qmail 76813 invoked by uid 500); 6 Sep 2006 01:05:38 -0000 Delivered-To: apmail-directory-commits-archive@directory.apache.org Received: (qmail 76784 invoked by uid 500); 6 Sep 2006 01:05:38 -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 76771 invoked by uid 99); 6 Sep 2006 01:05:37 -0000 Received: from asf.osuosl.org (HELO asf.osuosl.org) (140.211.166.49) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 05 Sep 2006 18:05:37 -0700 X-ASF-Spam-Status: No, hits=-8.6 required=10.0 tests=ALL_TRUSTED,INFO_TLD,NO_REAL_NAME X-Spam-Check-By: apache.org Received-SPF: pass (asf.osuosl.org: local policy) Received: from [140.211.166.113] (HELO eris.apache.org) (140.211.166.113) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 05 Sep 2006 18:05:35 -0700 Received: by eris.apache.org (Postfix, from userid 65534) id 066C71A981A; Tue, 5 Sep 2006 18:05:15 -0700 (PDT) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r440551 - in /directory/branches/apacheds/optimization/core/src: main/java/org/apache/directory/server/core/partition/impl/btree/ main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/ test/java/org/apache/directory/server/co... Date: Wed, 06 Sep 2006 01:05:14 -0000 To: commits@directory.apache.org From: akarasulu@apache.org X-Mailer: svnmailer-1.1.0 Message-Id: <20060906010515.066C71A981A@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org X-Spam-Rating: minotaur.apache.org 1.6.2 0/1000/N Author: akarasulu Date: Tue Sep 5 18:05:13 2006 New Revision: 440551 URL: http://svn.apache.org/viewvc?view=rev&rev=440551 Log: more fixes while trying to add BTree redirect for duplicates Added: directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeIterator.java directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeRedirect.java directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/DupsEnumeration.java (contents, props changed) - copied, changed from r439891, directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/DupsEnumeration.java directory/branches/apacheds/optimization/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeIteratorTest.java Removed: directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/DupsEnumeration.java Modified: directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/BTreePartition.java directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/IndexConfiguration.java directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/MutableIndexConfiguration.java directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/NoDupsEnumeration.java directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmIndex.java directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmPartition.java directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTable.java directory/branches/apacheds/optimization/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTableTest.java Modified: directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/BTreePartition.java URL: http://svn.apache.org/viewvc/directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/BTreePartition.java?view=diff&rev=440551&r1=440550&r2=440551 ============================================================================== --- directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/BTreePartition.java (original) +++ directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/BTreePartition.java Tue Sep 5 18:05:13 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/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/IndexConfiguration.java URL: http://svn.apache.org/viewvc/directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/IndexConfiguration.java?view=diff&rev=440551&r1=440550&r2=440551 ============================================================================== --- directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/IndexConfiguration.java (original) +++ directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/IndexConfiguration.java Tue Sep 5 18:05:13 2006 @@ -29,9 +29,12 @@ public class IndexConfiguration { public static final int DEFAULT_INDEX_CACHE_SIZE = 100; + + public static final int DEFAULT_DUPLICATE_LIMIT = 1; 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/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/MutableIndexConfiguration.java URL: http://svn.apache.org/viewvc/directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/MutableIndexConfiguration.java?view=diff&rev=440551&r1=440550&r2=440551 ============================================================================== --- directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/MutableIndexConfiguration.java (original) +++ directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/MutableIndexConfiguration.java Tue Sep 5 18:05:13 2006 @@ -38,4 +38,10 @@ { super.setCacheSize( cacheSize ); } + + + public void setDuplicateLimit( int duplicateLimit ) + { + super.setDuplicateLimit( duplicateLimit ); + } } Modified: directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/NoDupsEnumeration.java URL: http://svn.apache.org/viewvc/directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/NoDupsEnumeration.java?view=diff&rev=440551&r1=440550&r2=440551 ============================================================================== --- directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/NoDupsEnumeration.java (original) +++ directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/NoDupsEnumeration.java Tue Sep 5 18:05:13 2006 @@ -147,7 +147,7 @@ * @return true if this NamingEnumeration is ascending on keys, false * otherwise. */ - boolean doAscendingScan() + public boolean doAscendingScan() { return doAscendingScan; } Added: directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeIterator.java URL: http://svn.apache.org/viewvc/directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeIterator.java?view=auto&rev=440551 ============================================================================== --- directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeIterator.java (added) +++ directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeIterator.java Tue Sep 5 18:05:13 2006 @@ -0,0 +1,123 @@ +/* + * 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.Iterator; +import java.util.NoSuchElementException; + +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 Apache Directory Project + * @version $Rev$ + */ +public class BTreeIterator implements Iterator +{ + private final jdbm.helper.Tuple jdbmTuple = new jdbm.helper.Tuple(); + private TupleBrowser browser; + private boolean success = false; + private boolean doAscending = true; + + + BTreeIterator( BTree tree, boolean doAscending ) throws NamingException + { + this.doAscending = doAscending; + + try + { + if ( doAscending ) + { + browser = tree.browse(); + } + else + { + browser = tree.browse( null ); + } + + 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 ( doAscending ) + { + success = browser.getNext( jdbmTuple ); + } + else + { + success = browser.getPrevious( jdbmTuple ); + } + } + + + public boolean hasNext() + { + return success; + } + + + public Object next() + { + if ( ! success ) + { + throw new NoSuchElementException(); + } + + Object next = jdbmTuple.getKey(); + try + { + prefetch(); + } + catch ( IOException e ) + { + throw new NoSuchElementException( "Failure on btree: " + e.getMessage() ); + } + return next; + } + + + public void remove() + { + throw new UnsupportedOperationException(); + } +} Added: directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeRedirect.java URL: http://svn.apache.org/viewvc/directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeRedirect.java?view=auto&rev=440551 ============================================================================== --- directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeRedirect.java (added) +++ directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeRedirect.java Tue Sep 5 18:05:13 2006 @@ -0,0 +1,53 @@ +/* + * 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.Serializable; + + +/** + * A redirection pointer to another BTree. + * + * @author Apache Directory Project + * @version $Rev$ + */ +public class BTreeRedirect implements Serializable +{ + private static final long serialVersionUID = -4289810071005184834L; + + private Long recId; + + + public BTreeRedirect() + { + } + + + public BTreeRedirect( long recId ) + { + this.recId = new Long( recId ); + } + + + public Long getRecId() + { + return recId; + } +} Copied: directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/DupsEnumeration.java (from r439891, directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/DupsEnumeration.java) URL: http://svn.apache.org/viewvc/directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/DupsEnumeration.java?view=diff&rev=440551&p1=directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/DupsEnumeration.java&r1=439891&p2=directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/DupsEnumeration.java&r2=440551 ============================================================================== --- directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/DupsEnumeration.java (original) +++ directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/DupsEnumeration.java Tue Sep 5 18:05:13 2006 @@ -17,7 +17,7 @@ * under the License. * */ -package org.apache.directory.server.core.partition.impl.btree; +package org.apache.directory.server.core.partition.impl.btree.jdbm; import java.util.ArrayList; @@ -29,6 +29,11 @@ import javax.naming.NamingEnumeration; import javax.naming.NamingException; +import jdbm.btree.BTree; + +import org.apache.directory.server.core.partition.impl.btree.NoDupsEnumeration; +import org.apache.directory.server.core.partition.impl.btree.Tuple; + /** * NamingEnumeration that enumerates over duplicate values nested into a value @@ -65,7 +70,9 @@ */ private Iterator dupIterator; + private JdbmTable table; + // ------------------------------------------------------------------------ // Constructor // ------------------------------------------------------------------------ @@ -77,7 +84,7 @@ * @param list the underlying enumeration * @throws NamingException if there is a problem */ - public DupsEnumeration(NoDupsEnumeration list) throws NamingException + public DupsEnumeration( JdbmTable table, NoDupsEnumeration list ) throws NamingException { underlying = list; @@ -193,26 +200,37 @@ if ( underlying.hasMore() ) { duplicates = ( Tuple ) underlying.next(); - TreeSet set = ( TreeSet ) duplicates.getValue(); - - if ( underlying.doAscendingScan() ) + + Object values = duplicates.getValue(); + + if ( values instanceof TreeSet ) { - dupIterator = set.iterator(); + TreeSet set = ( TreeSet ) duplicates.getValue(); + + if ( underlying.doAscendingScan() ) + { + dupIterator = set.iterator(); + } + else + { + /* + * Need to reverse the list and iterate over the reversed + * list. + * + * TODO This can be optimized by using a ReverseIterator + * over the array list. I don't think there is a way to + * do this on the TreeSet. + */ + ArrayList list = new ArrayList( set.size() ); + list.addAll( set ); + Collections.reverse( list ); + dupIterator = list.iterator(); + } } - else + else if ( values instanceof BTreeRedirect ) { - /* - * Need to reverse the list and iterate over the reversed - * list. - * - * TODO This can be optimized by using a ReverseIterator - * over the array list. I don't think there is a way to - * do this on the TreeSet. - */ - ArrayList list = new ArrayList( set.size() ); - list.addAll( set ); - Collections.reverse( list ); - dupIterator = list.iterator(); + BTree tree = table.getBTree( ( BTreeRedirect ) values ); + dupIterator = new BTreeIterator( tree, underlying.doAscendingScan() ); } } else Propchange: directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/DupsEnumeration.java ------------------------------------------------------------------------------ svn:eol-style = native Propchange: directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/DupsEnumeration.java ------------------------------------------------------------------------------ --- svn:keywords (added) +++ svn:keywords Tue Sep 5 18:05:13 2006 @@ -0,0 +1,4 @@ +Rev +Revision +Date +Id Modified: directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmIndex.java URL: http://svn.apache.org/viewvc/directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmIndex.java?view=diff&rev=440551&r1=440550&r2=440551 ============================================================================== --- directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmIndex.java (original) +++ directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmIndex.java Tue Sep 5 18:05:13 2006 @@ -70,6 +70,8 @@ * will cache values for us. */ private SynchronizedLRUMap keyCache = null; + + private int numDupLimit = 100; // ------------------------------------------------------------------------ @@ -94,7 +96,7 @@ // } - public JdbmIndex( AttributeType attribute, File wkDirPath, int cacheSize ) throws NamingException + public JdbmIndex( AttributeType attribute, File wkDirPath, int cacheSize, int numDupLimit ) throws NamingException { File file = new File( wkDirPath.getPath() + File.separator + attribute.getName() ); this.attribute = attribute; @@ -134,7 +136,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 +144,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/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmPartition.java URL: http://svn.apache.org/viewvc/directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmPartition.java?view=diff&rev=440551&r1=440550&r2=440551 ============================================================================== --- directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmPartition.java (original) +++ directory/branches/apacheds/optimization/core/src/main/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmPartition.java Tue Sep 5 18:05:13 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/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=440551&r1=440550&r2=440551 ============================================================================== --- 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 Tue Sep 5 18:05:13 2006 @@ -23,7 +23,9 @@ import java.io.IOException; import java.util.ArrayList; import java.util.Collections; +import java.util.HashMap; import java.util.Iterator; +import java.util.Map; import java.util.SortedSet; import java.util.TreeSet; @@ -35,7 +37,6 @@ 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.KeyOnlyComparator; import org.apache.directory.server.core.partition.impl.btree.NoDupsEnumeration; import org.apache.directory.server.core.partition.impl.btree.Table; @@ -78,8 +79,11 @@ /** */ private TupleRenderer renderer; - private int numDupLimit = 1; + private int numDupLimit = 100; + private Map duplicateBtrees = new HashMap(); + + // ------------------------------------------------------------------------ // C O N S T R U C T O R // ------------------------------------------------------------------------ @@ -94,9 +98,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; @@ -157,7 +163,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 ) ); } @@ -272,9 +278,9 @@ // Handle the use of a BTree for storing duplicates // ------------------------------------------------------------------- - if ( values instanceof BTree ) + if ( values instanceof BTreeRedirect ) { - return ( ( BTree ) values ).size(); + return getBTree( ( BTreeRedirect ) values ).size(); } throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." ); @@ -289,7 +295,7 @@ return count; } - + // ------------------------------------------------------------------------ // get/has/put/remove Methods and Overloads // ------------------------------------------------------------------------ @@ -325,9 +331,9 @@ } } - if ( values instanceof BTree ) + if ( values instanceof BTreeRedirect ) { - BTree tree = ( BTree ) values; + BTree tree = getBTree( ( BTreeRedirect ) values ); if ( tree.size() == 0 ) { @@ -343,34 +349,6 @@ } - 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, * java.lang.Object, boolean) @@ -439,9 +417,9 @@ return false; } - if ( values instanceof BTree ) + if ( values instanceof BTreeRedirect ) { - BTree tree = ( BTree ) values; + BTree tree = getBTree( ( BTreeRedirect ) values ); if ( tree.size() == 0 ) { return false; @@ -452,48 +430,6 @@ 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 - { - 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; - } - } - } - catch ( IOException e ) - { - LdapNamingException lne = new LdapNamingException( "IO failure while acessing btree: " - + e.getMessage(), ResultCodeEnum.OTHER ); - lne.setRootCause( e ); - throw lne; - } - } /** @@ -621,41 +557,14 @@ return ( ( TreeSet ) values ).contains( value ); } - if ( values instanceof BTree ) + if ( values instanceof BTreeRedirect ) { - return btreeHas( ( BTree ) values, value ); + return btreeHas( getBTree( ( BTreeRedirect ) values ), 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; - } - } - /** * @see Table#has(java.lang.Object) @@ -707,7 +616,8 @@ if ( set.size() > numDupLimit ) { BTree tree = convertToBTree( set ); - replaced = putRaw( key, tree, true ); + BTreeRedirect redirect = new BTreeRedirect( tree.getRecid() ); + replaced = putRaw( key, redirect, true ); } else { @@ -722,77 +632,21 @@ return null; } - if ( values instanceof BTree ) + if ( values instanceof BTreeRedirect ) { - BTree tree = ( BTree ) values; + BTree tree = getBTree( ( BTreeRedirect ) values ); if ( insertDupIntoBTree( tree, value ) ) { count++; - return putRaw( key, tree, true ); + return values; } return null; } throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." ); } - - - 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) @@ -856,7 +710,8 @@ if ( set.size() > numDupLimit ) { BTree tree = convertToBTree( set ); - return putRaw( key, tree, true ); + BTreeRedirect redirect = new BTreeRedirect( tree.getRecid() ); + return putRaw( key, redirect, true ); } else { @@ -864,9 +719,9 @@ } } - if ( storedValues instanceof BTree ) + if ( storedValues instanceof BTreeRedirect ) { - BTree tree = ( BTree ) storedValues; + BTree tree = getBTree( ( BTreeRedirect ) storedValues ); while ( values.hasMore() ) { Object val = values.next(); @@ -877,7 +732,7 @@ } } - return putRaw( key, tree, true ); + return storedValues; } throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." ); @@ -934,19 +789,15 @@ // 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 ) + if ( values instanceof BTreeRedirect ) { - BTree tree = ( BTree ) values; + BTree tree = getBTree( ( BTreeRedirect ) values ); if ( removeDupFromBTree( tree, value ) ) { if ( tree.size() == 0 ) { - removeRaw( tree ); - } - else - { - putRaw( key, tree, true ); + removeRaw( key ); } count--; @@ -1028,9 +879,9 @@ // 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 ) + if ( storedValues instanceof BTreeRedirect ) { - BTree tree = ( BTree ) storedValues; + BTree tree = getBTree( ( BTreeRedirect ) storedValues ); while ( values.hasMore() ) { @@ -1042,7 +893,7 @@ } } - return putRaw( key, tree, true ); + return storedValues; } throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." ); @@ -1074,37 +925,15 @@ return set.first(); } - if ( returned instanceof BTree ) + if ( returned instanceof BTreeRedirect ) { - BTree tree = ( BTree ) returned; + BTree tree = getBTree( ( BTreeRedirect ) returned ); this.count -= tree.size(); removeAll( tree ); } throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." ); } - - - private void removeAll( BTree tree ) throws NamingException - { - jdbm.helper.Tuple jdbmTuple = new jdbm.helper.Tuple(); - TupleBrowser browser; - try - { - browser = tree.browse(); - while( browser.getNext( jdbmTuple ) ) - { - tree.remove( jdbmTuple.getKey() ); - } - } - catch ( IOException e ) - { - LdapNamingException lne = new LdapNamingException( "Failed to remove all keys in BTree", - ResultCodeEnum.OTHER ); - lne.setRootCause( e ); - throw lne; - } - } /** @@ -1169,9 +998,9 @@ }; } - if ( values instanceof BTree ) + if ( values instanceof BTreeRedirect ) { - BTree tree = ( BTree ) values; + BTree tree = getBTree( ( BTreeRedirect ) values ); return new BTreeEnumeration( tree ); } @@ -1204,7 +1033,7 @@ if ( allowsDuplicates ) { - return new DupsEnumeration( ( NoDupsEnumeration ) list ); + return new DupsEnumeration( this, ( NoDupsEnumeration ) list ); } return list; @@ -1247,9 +1076,9 @@ return new TupleEnumeration( key, iterator ); } - if ( values instanceof BTree ) + if ( values instanceof BTreeRedirect ) { - return new BTreeTupleEnumeration( ( BTree ) values, key ); + return new BTreeTupleEnumeration( getBTree( ( BTreeRedirect ) values ), key ); } throw new IllegalStateException( "When using duplicate keys either a TreeSet or BTree is used for values." ); @@ -1311,7 +1140,7 @@ if ( allowsDuplicates ) { - list = new DupsEnumeration( ( NoDupsEnumeration ) list ); + list = new DupsEnumeration( this, ( NoDupsEnumeration ) list ); } return list; @@ -1393,9 +1222,10 @@ } } - if ( values instanceof BTree ) + if ( values instanceof BTreeRedirect ) { - return new BTreeTupleEnumeration( ( BTree ) values, comparator.getValueComparator(), key, val, isGreaterThan ); + 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." ); @@ -1571,4 +1401,203 @@ 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 + { + 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 ) + { + 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; + } + } + + + 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; + } + } + + + private void removeAll( BTree tree ) throws NamingException + { + jdbm.helper.Tuple jdbmTuple = new jdbm.helper.Tuple(); + TupleBrowser browser; + try + { + browser = tree.browse(); + while( browser.getNext( jdbmTuple ) ) + { + tree.remove( jdbmTuple.getKey() ); + } + } + catch ( IOException e ) + { + LdapNamingException lne = new LdapNamingException( "Failed to remove all keys in BTree", + ResultCodeEnum.OTHER ); + lne.setRootCause( e ); + throw lne; + } + } } + Added: directory/branches/apacheds/optimization/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeIteratorTest.java URL: http://svn.apache.org/viewvc/directory/branches/apacheds/optimization/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeIteratorTest.java?view=auto&rev=440551 ============================================================================== --- directory/branches/apacheds/optimization/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeIteratorTest.java (added) +++ directory/branches/apacheds/optimization/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/BTreeIteratorTest.java Tue Sep 5 18:05:13 2006 @@ -0,0 +1,156 @@ +/* + * 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 Apache Directory Project + * @version $Rev$ + */ +public class BTreeIteratorTest 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 + { + BTreeIterator bte = new BTreeIterator( tree, true ); + assertFalse( "iterator on empty btree should not have elements", bte.hasNext() ); + } + + + public void testOneElement() throws IOException, NamingException + { + BigInteger value = new BigInteger( "1" ); + tree.insert( value, EMPTY_BYTES, true ); + BTreeIterator bte = new BTreeIterator( tree, true ); + assertTrue( bte.hasNext() ); + assertEquals( value, bte.next() ); + assertFalse( "iterator consumed should not have elements", bte.hasNext() ); + } + + + 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 ); + + BTreeIterator bte = new BTreeIterator( tree, true ); + + assertTrue( bte.hasNext() ); + assertEquals( new BigInteger( "1" ), bte.next() ); + + assertTrue( bte.hasNext() ); + assertEquals( new BigInteger( "2" ), bte.next() ); + + assertTrue( bte.hasNext() ); + assertEquals( new BigInteger( "4" ), bte.next() ); + + assertTrue( bte.hasNext() ); + assertEquals( new BigInteger( "5" ), bte.next() ); + + assertFalse( "iterator consumed should not have elements", bte.hasNext() ); + } + + + public void testManyElementsReversed() 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 ); + + BTreeIterator bte = new BTreeIterator( tree, false ); + + assertTrue( bte.hasNext() ); + assertEquals( new BigInteger( "5" ), bte.next() ); + + assertTrue( bte.hasNext() ); + assertEquals( new BigInteger( "4" ), bte.next() ); + + assertTrue( bte.hasNext() ); + assertEquals( new BigInteger( "2" ), bte.next() ); + + assertTrue( bte.hasNext() ); + assertEquals( new BigInteger( "1" ), bte.next() ); + + assertFalse( "iterator consumed should not have elements", bte.hasNext() ); + } +} Modified: directory/branches/apacheds/optimization/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTableTest.java URL: http://svn.apache.org/viewvc/directory/branches/apacheds/optimization/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTableTest.java?view=diff&rev=440551&r1=440550&r2=440551 ============================================================================== --- directory/branches/apacheds/optimization/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTableTest.java (original) +++ directory/branches/apacheds/optimization/core/src/test/java/org/apache/directory/server/core/partition/impl/btree/jdbm/JdbmTableTest.java Tue Sep 5 18:05:13 2006 @@ -24,6 +24,7 @@ import java.io.Serializable; import java.math.BigInteger; +import javax.naming.NamingEnumeration; import javax.naming.NamingException; import jdbm.RecordManager; @@ -91,12 +92,26 @@ } - public void testCreateTableWithDups() throws NamingException + public void testReadWriteToTableWithDups() throws NamingException { - JdbmTable table = new JdbmTable( "test", true, rm, comparator ); - for ( BigInteger ii = BigInteger.ZERO; ii.intValue() < 1001; ii = ii.add( BigInteger.ONE ) ) + JdbmTable table = new JdbmTable( "test", true, 10, rm, comparator ); + for ( BigInteger ii = BigInteger.ZERO; ii.intValue() < 12; ii = ii.add( BigInteger.ONE ) ) { table.put( BigInteger.ONE, ii ); + assertTrue( table.has( BigInteger.ONE, ii ) ); + assertEquals( BigInteger.ZERO, table.get( BigInteger.ONE ) ); + assertEquals( ii.intValue() + 1, table.count() ); } + + int counter = 0; + for ( NamingEnumeration values = table.listValues( BigInteger.ONE ); values.hasMore(); /**/ ) + { + System.out.println( counter ); + BigInteger jj = ( BigInteger ) values.next(); + table.remove( BigInteger.ONE, jj ); + counter++; + } + assertEquals( 12, counter ); + assertEquals( 0, table.count() ); } }