directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From akaras...@apache.org
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 GMT
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 <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @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 <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @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 <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @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() );
     }
 }



Mime
View raw message