Mailing-List: contact commits-help@directory.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@directory.apache.org
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: svn commit: r760740 - in /directory:
 apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/
 apacheds/branches/ldif-partition/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/
 apache...
Date: Wed, 01 Apr 2009 00:00:27 -0000
To: commits@directory.apache.org
From: akarasulu@apache.org
Message-Id: <20090401000027.ABBEA2388B54@eris.apache.org>

Author: akarasulu
Date: Wed Apr  1 00:00:26 2009
New Revision: 760740

URL: http://svn.apache.org/viewvc?rev=760740&view=rev
Log:
added avl table and cursors

Added:
    directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/KeyTupleAvlCursor.java
    directory/apacheds/branches/ldif-partition/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/
    directory/apacheds/branches/ldif-partition/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/AvlTable.java
    directory/apacheds/branches/ldif-partition/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/AvlTableDupsCursor.java
    directory/apacheds/branches/ldif-partition/ldif-partition/src/test/
    directory/apacheds/branches/ldif-partition/ldif-partition/src/test/java/
    directory/apacheds/branches/ldif-partition/ldif-partition/src/test/java/org/
    directory/apacheds/branches/ldif-partition/ldif-partition/src/test/java/org/apache/
    directory/apacheds/branches/ldif-partition/ldif-partition/src/test/java/org/apache/directory/
    directory/apacheds/branches/ldif-partition/ldif-partition/src/test/java/org/apache/directory/server/
    directory/apacheds/branches/ldif-partition/ldif-partition/src/test/java/org/apache/directory/server/core/
    directory/apacheds/branches/ldif-partition/ldif-partition/src/test/java/org/apache/directory/server/core/partition/
    directory/apacheds/branches/ldif-partition/ldif-partition/src/test/java/org/apache/directory/server/core/partition/ldif/
    directory/apacheds/branches/ldif-partition/ldif-partition/src/test/java/org/apache/directory/server/core/partition/ldif/AvlUsageTest.java
Modified:
    directory/apacheds/branches/ldif-partition/server-xml/src/test/java/org/apache/directory/server/SpringServerTest.java
    directory/project/trunk/resources/dictionary

Added: directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/KeyTupleAvlCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/KeyTupleAvlCursor.java?rev=760740&view=auto
==============================================================================
--- directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/KeyTupleAvlCursor.java (added)
+++ directory/apacheds/branches/ldif-partition/core-avl/src/main/java/org/apache/directory/server/core/avltree/KeyTupleAvlCursor.java Wed Apr  1 00:00:26 2009
@@ -0,0 +1,215 @@
+/*
+ * 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.avltree;
+
+
+import org.apache.directory.server.core.cursor.InvalidCursorPositionException;
+import org.apache.directory.server.xdbm.Tuple;
+import org.apache.directory.server.xdbm.AbstractTupleCursor;
+import org.apache.directory.server.core.avltree.AvlTree;
+import org.apache.directory.server.core.avltree.AvlTreeCursor;
+
+
+/**
+ * Cursor over a set of values for the same key which are store in an in
+ * memory AvlTree.  This Cursor is limited to the same key and it's tuples
+ * will always return the same key.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class KeyTupleAvlCursor<K,V> extends AbstractTupleCursor<K,V>
+{
+    private final AvlTreeCursor<V> wrapped;
+    private final K key;
+
+    private Tuple<K,V> returnedTuple = new Tuple<K,V>();
+    private boolean valueAvailable;
+
+
+    /**
+     * Creates a Cursor over the tuples of an AvlTree.
+     *
+     * @param avlTree the AvlTree to build a Tuple returning Cursor over
+     * @param key the constant key for which values are returned
+     */
+    public KeyTupleAvlCursor( AvlTree<V> avlTree, K key )
+    {
+        this.key = key;
+        this.wrapped = new AvlTreeCursor<V>( avlTree );
+    }
+
+
+    private void clearValue()
+    {
+        returnedTuple.setKey( key );
+        returnedTuple.setValue( null );
+        valueAvailable = false;
+    }
+
+
+    public boolean available()
+    {
+        return valueAvailable;
+    }
+
+
+    public void beforeKey( K key ) throws Exception
+    {
+        throw new UnsupportedOperationException( "This cursor locks down the key so keywise advances are not allowed." );
+    }
+
+
+    public void afterKey( K key ) throws Exception
+    {
+        throw new UnsupportedOperationException( "This cursor locks down the key so keywise advances are not allowed." );
+    }
+
+
+    public void beforeValue( K key, V value ) throws Exception
+    {
+        checkNotClosed( "beforeValue()" );
+        if ( key != null && ! key.equals( this.key ) )
+        {
+            throw new UnsupportedOperationException( "This cursor locks down the key so keywise advances are not allowed." );
+        }
+
+        wrapped.before( value );
+        clearValue();
+    }
+
+
+    public void afterValue( K key, V value ) throws Exception
+    {
+        checkNotClosed( "afterValue()" );
+        if ( key != null && ! key.equals( this.key ) )
+        {
+            throw new UnsupportedOperationException( "This cursor locks down the key so keywise advances are not allowed." );
+        }
+
+        wrapped.after( value );
+        clearValue();
+    }
+
+
+    /**
+     * Positions this Cursor over the same keys before the value of the
+     * supplied element Tuple.  The supplied element Tuple's key is not
+     * considered at all.
+     *
+     * @param element the valueTuple who's value is used to position this Cursor
+     * @throws Exception if there are failures to position the Cursor
+     */
+    public void before( Tuple<K,V> element ) throws Exception
+    {
+        checkNotClosed( "before()" );
+        wrapped.before( element.getValue() );
+        clearValue();
+    }
+
+
+    public void after( Tuple<K,V> element ) throws Exception
+    {
+        checkNotClosed( "after()" );
+        wrapped.after( element.getValue() );
+        clearValue();
+    }
+
+
+    public void beforeFirst() throws Exception
+    {
+        checkNotClosed( "beforeFirst()" );
+        wrapped.beforeFirst();
+        clearValue();
+    }
+
+
+    public void afterLast() throws Exception
+    {
+        checkNotClosed( "afterLast()" );
+        wrapped.afterLast();
+        clearValue();
+    }
+
+
+    public boolean first() throws Exception
+    {
+        beforeFirst();
+        return next();
+    }
+
+
+    public boolean last() throws Exception
+    {
+        afterLast();
+        return previous();
+    }
+
+
+    public boolean previous() throws Exception
+    {
+        checkNotClosed( "previous()" );
+        if ( wrapped.previous() )
+        {
+            returnedTuple.setKey( key );
+            returnedTuple.setValue( wrapped.get() );
+            return valueAvailable = true;
+        }
+        else
+        {
+            clearValue();
+            return false;
+        }
+    }
+
+
+    public boolean next() throws Exception
+    {
+        checkNotClosed( "next()" );
+        if ( wrapped.next() )
+        {
+            returnedTuple.setKey( key );
+            returnedTuple.setValue( wrapped.get() );
+            return valueAvailable = true;
+        }
+        else
+        {
+            clearValue();
+            return false;
+        }
+    }
+
+
+    public Tuple<K,V> get() throws Exception
+    {
+        checkNotClosed( "get()" );
+        if ( valueAvailable )
+        {
+            return returnedTuple;
+        }
+
+        throw new InvalidCursorPositionException();
+    }
+
+
+    public boolean isElementReused()
+    {
+        return true;
+    }
+}
\ No newline at end of file

Added: directory/apacheds/branches/ldif-partition/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/AvlTable.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/ldif-partition/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/AvlTable.java?rev=760740&view=auto
==============================================================================
--- directory/apacheds/branches/ldif-partition/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/AvlTable.java (added)
+++ directory/apacheds/branches/ldif-partition/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/AvlTable.java Wed Apr  1 00:00:26 2009
@@ -0,0 +1,456 @@
+/*
+ *   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.ldif;
+
+
+import java.util.Comparator;
+
+import org.apache.directory.server.core.avltree.AvlTree;
+import org.apache.directory.server.core.avltree.AvlTreeCursor;
+import org.apache.directory.server.core.avltree.AvlTreeMap;
+import org.apache.directory.server.core.avltree.AvlTreeMapNoDupsCursor;
+import org.apache.directory.server.core.avltree.KeyTupleAvlCursor;
+import org.apache.directory.server.core.avltree.LinkedAvlMapNode;
+import org.apache.directory.server.core.cursor.Cursor;
+import org.apache.directory.server.core.cursor.EmptyCursor;
+import org.apache.directory.server.core.cursor.SingletonCursor;
+import org.apache.directory.server.xdbm.Table;
+import org.apache.directory.server.xdbm.Tuple;
+
+
+/**
+ * A Table implementation backed by in memory AVL tree.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class AvlTable<K, V> implements Table<K, V>
+{
+    private final AvlTreeMap<K, V> avl;
+    private final String name;
+    private final Comparator<K> keyComparator;
+    private final Comparator<V> valComparator;
+    private int count;
+    
+    
+    public AvlTable( String name, Comparator<K> keyComparator, Comparator<V> valComparator, boolean dupsEnabled )
+    {
+        this.name = name;
+        this.keyComparator = keyComparator;
+        this.valComparator = valComparator;
+        this.avl = new AvlTreeMap<K, V>( keyComparator, valComparator, dupsEnabled );
+    }
+    
+
+    /**
+     * Does nothing.
+     * 
+     * {@inheritDoc}
+     */
+    public void close() throws Exception
+    {
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    public int count() throws Exception
+    {
+        return count;
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    @SuppressWarnings("unchecked")
+    public int count( K key ) throws Exception
+    {
+        if ( key == null )
+        {
+            return 0;
+        }
+        
+        LinkedAvlMapNode<K, V> node = avl.find( key );
+        if ( node == null )
+        {
+            return 0;
+        }
+        
+        V val = node.getValue();
+        if ( val instanceof AvlTree )
+        {
+            return ( ( AvlTree ) val ).getSize();
+        }
+        
+        return 1;
+    }
+
+   
+    /**
+     * {@inheritDoc}
+     */
+    @SuppressWarnings("unchecked")
+    public V get( K key ) throws Exception
+    {
+        if ( key == null )
+        {
+            return null;
+        }
+        
+        LinkedAvlMapNode<K, V> node = avl.find( key );
+        if ( node == null )
+        {
+            return null;
+        }
+        
+        V val = node.getValue();
+        if ( val instanceof AvlTree )
+        {
+            return ( ( AvlTree<V> ) val ).getFirst().getKey();
+        }
+        
+        return val;
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    public Comparator<K> getKeyComparator()
+    {
+        return keyComparator;
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    public Comparator<V> getValueComparator()
+    {
+        return valComparator;
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    public String getName()
+    {
+        return name;
+    }
+    
+
+    /**
+     * {@inheritDoc}
+     */
+    public int greaterThanCount( K key ) throws Exception
+    {
+        return avl.getSize();
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    public boolean has( K key ) throws Exception
+    {
+        if ( key == null )
+        {
+            return false;
+        }
+        
+        return avl.find( key ) != null;
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    public boolean has( K key, V value ) throws Exception
+    {
+        if ( key == null )
+        {
+            return false;
+        }
+        
+        return avl.find( key, value ) != null;
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    public boolean hasGreaterOrEqual( K key ) throws Exception
+    {
+        if ( key == null )
+        {
+            return false;
+        }
+        
+        return avl.findGreaterOrEqual( key ) != null;
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    @SuppressWarnings("unchecked")
+    public boolean hasGreaterOrEqual( K key, V val ) throws Exception
+    {
+        if ( key == null )
+        {
+            return false;
+        }
+        
+        LinkedAvlMapNode<K, V> node = avl.findGreaterOrEqual( key );
+        if ( node == null )
+        {
+            return false;
+        }
+        
+        if ( node.getValue() instanceof AvlTree )
+        {
+            AvlTree<V> values = ( AvlTree<V> ) node.getValue();
+            return values.findGreaterOrEqual( val ) != null;
+        }
+        
+        return valComparator.compare( node.getValue(), val ) >= 0;
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    public boolean hasLessOrEqual( K key ) throws Exception
+    {
+        if ( key == null )
+        {
+            return false;
+        }
+        
+        return avl.findLessOrEqual( key ) != null;
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    @SuppressWarnings("unchecked")
+    public boolean hasLessOrEqual( K key, V val ) throws Exception
+    {
+        if ( key == null )
+        {
+            return false;
+        }
+        
+        LinkedAvlMapNode<K, V> node = avl.findLessOrEqual( key );
+        if ( node == null )
+        {
+            return false;
+        }
+        
+        if ( node.getValue() instanceof AvlTree )
+        {
+            AvlTree<V> values = ( AvlTree<V> ) node.getValue();
+            return values.findLessOrEqual( val ) != null;
+        }
+        
+        return valComparator.compare( node.getValue(), val ) <= 0;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean isCountExact()
+    {
+        return false;
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    public boolean isDupsEnabled()
+    {
+        return avl.isDupsAllowed();
+    }
+    
+
+    /**
+     * {@inheritDoc}
+     */
+    public int lessThanCount( K key ) throws Exception
+    {
+        return count;
+    }
+    
+
+    /**
+     * {@inheritDoc}
+     */
+    public void put( K key, V value ) throws Exception
+    {
+        if ( key == null || value == null )
+        {
+            return;
+        }
+        
+        if ( avl.insert( key, value ) == null )
+        {
+            count++;
+        }
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    @SuppressWarnings("unchecked")
+    public void remove( K key ) throws Exception
+    {
+        if ( key == null )
+        {
+            return;
+        }
+        
+        if ( ! avl.isDupsAllowed() )
+        {
+            if ( avl.remove( key, null ) != null )
+            {
+                count--;
+            }
+            return;
+        }
+        
+        LinkedAvlMapNode<K, V> node = avl.find( key );
+        if ( node == null )
+        {
+            return;
+        }
+        
+        V value = node.getValue();
+        
+        if ( value instanceof AvlTree )
+        {
+            count -= ( ( AvlTree ) value ).getSize();
+            avl.remove( key, null );
+        }
+        else
+        {
+            avl.remove( key, null );
+            count --;
+        }
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    public void remove( K key, V value ) throws Exception
+    {
+        if ( avl.remove( key, value ) != null )
+        {
+            count--;
+        }
+    }
+    
+    
+    /**
+     * {@inheritDoc}
+     */
+    public Cursor<Tuple<K, V>> cursor() throws Exception
+    {
+        if ( ! avl.isDupsAllowed() )
+        {
+            return new AvlTreeMapNoDupsCursor<K,V>( avl );
+        }
+
+        return new AvlTableDupsCursor<K, V>( this );
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    @SuppressWarnings("unchecked")
+    public Cursor<Tuple<K, V>> cursor( K key ) throws Exception
+    {
+        if ( key == null )
+        {
+            return new EmptyCursor<Tuple<K,V>>();
+        }
+        
+        LinkedAvlMapNode<K, V> node = avl.find( key );
+        if ( node == null )
+        {
+            return new EmptyCursor<Tuple<K,V>>();
+        }
+        
+        V value = node.getValue();
+        if ( value instanceof AvlTree )
+        {
+            return new KeyTupleAvlCursor<K,V>( ( AvlTree<V> ) value, key );
+        }
+        
+        return new SingletonCursor<Tuple<K,V>>( new Tuple<K,V>( key, value ) );
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    @SuppressWarnings("unchecked")
+    public Cursor<V> valueCursor( K key ) throws Exception
+    {
+        if ( key == null )
+        {
+            return new EmptyCursor<V>();
+        }
+        
+        LinkedAvlMapNode<K, V> node = avl.find( key );
+        if ( node == null )
+        {
+            return new EmptyCursor<V>();
+        }
+        
+        V value = node.getValue();
+        if ( value instanceof AvlTree )
+        {
+            return new AvlTreeCursor<V>( ( AvlTree<V> ) value );
+        }
+        
+        return new SingletonCursor<V>( value );
+    }
+
+
+    /**
+     * Returns the internal AvlTreeMap so other classes like Cursors
+     * in the same package can access it.
+     *
+     * @return AvlTreeMap used to store Tuples
+     */
+    AvlTreeMap<K,V> getAvlTreeMap()
+    {
+        return avl;
+    }
+}

Added: directory/apacheds/branches/ldif-partition/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/AvlTableDupsCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/ldif-partition/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/AvlTableDupsCursor.java?rev=760740&view=auto
==============================================================================
--- directory/apacheds/branches/ldif-partition/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/AvlTableDupsCursor.java (added)
+++ directory/apacheds/branches/ldif-partition/ldif-partition/src/main/java/org/apache/directory/server/core/partition/ldif/AvlTableDupsCursor.java Wed Apr  1 00:00:26 2009
@@ -0,0 +1,514 @@
+/*
+ *   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.ldif;
+
+
+import org.apache.directory.server.core.avltree.AvlTree;
+import org.apache.directory.server.core.avltree.AvlTreeCursor;
+import org.apache.directory.server.core.avltree.AvlTreeMapNoDupsCursor;
+import org.apache.directory.server.core.cursor.Cursor;
+import org.apache.directory.server.core.cursor.InvalidCursorPositionException;
+import org.apache.directory.server.core.cursor.SingletonCursor;
+import org.apache.directory.server.xdbm.AbstractTupleCursor;
+import org.apache.directory.server.xdbm.Tuple;
+import org.apache.directory.server.xdbm.TupleCursor;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+
+/**
+ * A Cursor which walks and advance over AvlTables that may contain duplicate
+ * keys with values stored in an AvlTree.  All duplicate keys are traversed 
+ * returning the key and the value in a Tuple.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class AvlTableDupsCursor<K,V> extends AbstractTupleCursor<K, V>
+{
+    private static final Logger LOG = LoggerFactory.getLogger( AvlTableDupsCursor.class.getSimpleName() );
+    
+    /** The AVL backed table this Cursor traverses over. */
+    private final AvlTable<K,V> table;
+    
+    /**
+     * The underlying wrapped cursor which returns Tuples whose values are
+     * either V objects or AvlTree objects.
+     */
+    private final TupleCursor<K,V> wrappedCursor;
+    
+    /**
+     * A Cursor over a set of value objects for the current key held in the
+     * containerTuple.  A new Cursor will be set for each new key as we
+     * traverse.  The Cursor traverses over either a AvlTree object full
+     * of values in a multi-valued key or it traverses over a BTree which
+     * contains the values in the key field of it's Tuples.
+     */
+    private Cursor<V> dupsCursor;
+
+    /** The current Tuple returned from the wrapped cursor. */
+    private final Tuple<K,V> wrappedTuple = new Tuple<K, V>();
+
+    /**
+     * The Tuple that is used to return values via the get() method. This
+     * same Tuple instance will be returned every time.  At different
+     * positions it may return different values for the same key.
+     */
+    private final Tuple<K,V> returnedTuple = new Tuple<K,V>();
+
+    /** Whether or not a value is available when get() is called. */
+    private boolean valueAvailable;
+
+    
+    /**
+     * Creates a new instance of AvlTableDupsCursor.
+     *
+     * @param table the AvlTable to build a Cursor on.
+     */
+    public AvlTableDupsCursor( AvlTable<K,V> table )
+    {
+        this.table = table;
+        this.wrappedCursor = new AvlTreeMapNoDupsCursor<K, V>( table.getAvlTreeMap() );
+        LOG.debug( "Created on table {}", table.getName() );
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean available()
+    {
+        return valueAvailable;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void beforeKey( K key ) throws Exception
+    {
+        beforeValue( key, null );
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    @SuppressWarnings("unchecked")
+    public void beforeValue( K key, V value ) throws Exception
+    {
+        checkNotClosed( "beforeValue()" );
+        wrappedCursor.before( new Tuple<K,V>( key, null ) );
+        
+        if ( wrappedCursor.next() )
+        {
+            wrappedTuple.setBoth( wrappedCursor.get() );
+            
+            if ( wrappedTuple.getValue() instanceof AvlTree )
+            {
+                AvlTree<V> avlTree = ( AvlTree<V> ) wrappedTuple.getValue();
+                dupsCursor = new AvlTreeCursor<V>( avlTree );
+            }
+            else
+            {
+                dupsCursor = new SingletonCursor<V>( wrappedTuple.getValue() );
+            }
+            
+            if ( value == null )
+            {
+                return;
+            }
+    
+            /* 
+             * The cursor over the values is only advanced if we're on the 
+             * same key as the primary cursor.  This is because we want this
+             * method to really position us within a set of duplicate key 
+             * entries at the proper value.
+             */
+            if ( table.getKeyComparator().compare( wrappedTuple.getKey(), key ) == 0 )
+            {
+                dupsCursor.before( value );
+            }
+            
+            return;
+        }
+        
+        clearValue();
+        wrappedTuple.setKey( null );
+        wrappedTuple.setValue( null );
+    }
+    
+
+    /**
+     * {@inheritDoc}
+     */
+    public void afterKey( K key ) throws Exception
+    {
+        afterValue( key, null );
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    @SuppressWarnings("unchecked")
+    public void afterValue( K key, V value ) throws Exception
+    {
+        checkNotClosed( "afterValue()" );
+        /*
+         * There is a subtle difference between after and before handling
+         * with dupicate key values.  Say we have the following tuples:
+         *
+         * (0, 0)
+         * (1, 1)
+         * (1, 2)
+         * (1, 3)
+         * (2, 2)
+         *
+         * If we request an after cursor on (1, 2).  We must make sure that
+         * the container cursor does not advance after the entry with key 1
+         * since this would result in us skip returning (1. 3) on the call to
+         * next which will incorrectly return (2, 2) instead.
+         *
+         * So if the value is null in the element then we don't care about
+         * this obviously since we just want to advance past the duplicate key
+         * values all together.  But when it is not null, then we want to
+         * go right before this key instead of after it.
+         */
+
+        if ( value == null )
+        {
+            wrappedCursor.after( new Tuple<K,V>( key, null ) );
+        }
+        else
+        {
+            wrappedCursor.before( new Tuple<K,V>( key, null ) );
+        }
+
+        if ( wrappedCursor.next() )
+        {
+            wrappedTuple.setBoth( wrappedCursor.get() );
+            V values = wrappedTuple.getValue();
+
+            if ( values instanceof AvlTree )
+            {
+                AvlTree<V> set = ( AvlTree<V> ) values;
+                dupsCursor = new AvlTreeCursor<V>( set );
+            }
+            else
+            {
+                dupsCursor = new SingletonCursor<V>( values );
+            }
+
+            if ( value == null )
+            {
+                return;
+            }
+
+            // only advance the dupsCursor if we're on same key
+            if ( table.getKeyComparator().compare( wrappedTuple.getKey(), key ) == 0 )
+            {
+                dupsCursor.after( value );
+            }
+
+            return;
+        }
+
+        clearValue();
+        wrappedTuple.setKey( null );
+        wrappedTuple.setValue( null );
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    public void after( Tuple<K, V> element ) throws Exception
+    {
+        afterValue( element.getKey(), element.getValue() );
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    public void afterLast() throws Exception
+    {
+        checkNotClosed( "afterLast()" );
+        clearValue();
+        wrappedCursor.afterLast();
+        wrappedTuple.setKey( null );
+        wrappedTuple.setValue( null );
+        dupsCursor = null;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void before( Tuple<K, V> element ) throws Exception
+    {
+        beforeValue( element.getKey(), element.getValue() );
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    public void beforeFirst() throws Exception
+    {
+        checkNotClosed( "beforeFirst()" );
+        clearValue();
+        wrappedCursor.beforeFirst();
+        wrappedTuple.setKey( null );
+        wrappedTuple.setValue( null );
+        dupsCursor = null;
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    @SuppressWarnings("unchecked")
+    public boolean first() throws Exception
+    {
+        checkNotClosed( "first()" );
+        clearValue();
+        dupsCursor = null;
+
+        if ( wrappedCursor.first() )
+        {
+            wrappedTuple.setBoth( wrappedCursor.get() );
+            V values = wrappedTuple.getValue();
+
+            if ( values instanceof AvlTree )
+            {
+                dupsCursor = new AvlTreeCursor<V>( ( AvlTree<V> ) values );
+            }
+            else
+            {
+                dupsCursor = new SingletonCursor<V>( values );
+            }
+
+            /*
+             * Since only tables with duplicate keys enabled use this
+             * cursor, entries must have at least one value, and therefore
+             * call to last() will always return true.
+             */
+            dupsCursor.first();
+            valueAvailable =  true;
+            returnedTuple.setKey( wrappedTuple.getKey() );
+            returnedTuple.setValue( dupsCursor.get() );
+            return true;
+        }
+
+        return false;
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    public Tuple<K, V> get() throws Exception
+    {
+        checkNotClosed( "get()" );
+
+        if ( ! valueAvailable )
+        {
+            throw new InvalidCursorPositionException();
+        }
+
+        return returnedTuple;
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    public boolean isElementReused()
+    {
+        return true;
+    }
+    
+
+    /**
+     * {@inheritDoc}
+     */
+    @SuppressWarnings("unchecked")
+    public boolean last() throws Exception
+    {
+        checkNotClosed( "last()" );
+        clearValue();
+        dupsCursor = null;
+
+        if ( wrappedCursor.last() )
+        {
+            wrappedTuple.setBoth( wrappedCursor.get() );
+            V values = wrappedTuple.getValue();
+
+            if ( values instanceof AvlTree )
+            {
+                dupsCursor = new AvlTreeCursor<V>( ( AvlTree<V> ) values );
+            }
+            else
+            {
+                dupsCursor = new SingletonCursor<V>( values );
+            }
+
+            /*
+             * Since only tables with duplicate keys enabled use this
+             * cursor, entries must have at least one value, and therefore
+             * call to last() will always return true.
+             */
+            dupsCursor.last();
+            valueAvailable = true;
+            returnedTuple.setKey( wrappedTuple.getKey() );
+            returnedTuple.setValue( dupsCursor.get() );
+            return true;
+        }
+
+        return false;
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    @SuppressWarnings("unchecked")
+    public boolean next() throws Exception
+    {
+        checkNotClosed( "next()" );
+        /*
+         * If the cursor over the values of the current key is null or is
+         * extinguished then we need to advance to the next key.
+         */
+        if ( null == dupsCursor || ! dupsCursor.next() )
+        {
+            /*
+             * If the wrappedCursor cursor has more elements we get the next
+             * key/AvlTree Tuple to work with and get a cursor over it.
+             */
+            if ( wrappedCursor.next() )
+            {
+                wrappedTuple.setBoth( wrappedCursor.get() );
+                V values = wrappedTuple.getValue();
+
+                if ( values instanceof AvlTree )
+                {
+                    dupsCursor = new AvlTreeCursor<V>( ( AvlTree<V> ) values );
+                }
+                else
+                {
+                    dupsCursor = new SingletonCursor<V>( values );
+                }
+
+                /*
+                 * Since only tables with duplicate keys enabled use this
+                 * cursor, entries must have at least one value, and therefore
+                 * call to next() after bringing the cursor to beforeFirst()
+                 * will always return true.
+                 */
+                dupsCursor.beforeFirst();
+                dupsCursor.next();
+            }
+            else
+            {
+                dupsCursor = null;
+                return false;
+            }
+        }
+
+        /*
+         * If we get to this point then cursor has more elements and
+         * wrappedTuple holds the Tuple containing the key and the 
+         * AvlTree of values for that key which the Cursor traverses.  All we
+         * need to do is populate our tuple object with the key and the value
+         * in the cursor.
+         */
+        returnedTuple.setKey( wrappedTuple.getKey() );
+        returnedTuple.setValue( dupsCursor.get() );
+        return valueAvailable = true;
+    }
+
+    
+    /**
+     * {@inheritDoc}
+     */
+    @SuppressWarnings("unchecked")
+    public boolean previous() throws Exception
+    {
+        checkNotClosed( "previous()" );
+        /*
+         * If the cursor over the values of the current key is null or is
+         * extinguished then we need to advance to the previous key.
+         */
+        if ( null == dupsCursor || ! dupsCursor.previous() )
+        {
+            /*
+             * If the wrappedCursor cursor has more elements we get the previous
+             * key/AvlTree Tuple to work with and get a cursor over it's
+             * values.
+             */
+            if ( wrappedCursor.previous() )
+            {
+                wrappedTuple.setBoth( wrappedCursor.get() );
+                V values = wrappedTuple.getValue();
+
+                if ( values instanceof AvlTree )
+                {
+                    dupsCursor = new AvlTreeCursor<V>( ( AvlTree<V> ) values );
+                }
+                else
+                {
+                    dupsCursor = new SingletonCursor<V>( values );
+                }
+
+                /*
+                 * Since only tables with duplicate keys enabled use this
+                 * cursor, entries must have at least one value, and therefore
+                 * call to previous() after bringing the cursor to afterLast()
+                 * will always return true.
+                 */
+                dupsCursor.afterLast();
+                dupsCursor.previous();
+            }
+            else
+            {
+                dupsCursor = null;
+                return false;
+            }
+        }
+
+        returnedTuple.setKey( wrappedTuple.getKey() );
+        returnedTuple.setValue( dupsCursor.get() );
+        return valueAvailable = true;
+    }
+
+
+    /**
+     * Clears the returned Tuple and makes sure valueAvailable returns false.
+     */
+    private void clearValue()
+    {
+        returnedTuple.setKey( null );
+        returnedTuple.setValue( null );
+        valueAvailable = false;
+    }
+}

Added: directory/apacheds/branches/ldif-partition/ldif-partition/src/test/java/org/apache/directory/server/core/partition/ldif/AvlUsageTest.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/ldif-partition/ldif-partition/src/test/java/org/apache/directory/server/core/partition/ldif/AvlUsageTest.java?rev=760740&view=auto
==============================================================================
--- directory/apacheds/branches/ldif-partition/ldif-partition/src/test/java/org/apache/directory/server/core/partition/ldif/AvlUsageTest.java (added)
+++ directory/apacheds/branches/ldif-partition/ldif-partition/src/test/java/org/apache/directory/server/core/partition/ldif/AvlUsageTest.java Wed Apr  1 00:00:26 2009
@@ -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.ldif;
+
+
+import java.util.Comparator;
+
+import org.apache.directory.server.core.avltree.AvlTree;
+import org.apache.directory.server.xdbm.Tuple;
+
+import junit.framework.TestCase;
+
+
+/**
+ * TODO AvlUsageTest.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class AvlUsageTest extends TestCase
+{
+    public void testWithTuple()
+    {
+        //AvlTree<Tuple<K,V>> avlTree = new AvlTree<Tuple<K, V>>();
+    }
+    
+    
+    class AvlTupleComparator<K,V> implements Comparator<Tuple<K,V>>
+    {
+        public int compare( Tuple<K,V> arg0, Tuple<K,V> arg1 )
+        {
+            // TODO Auto-generated method stub
+            return 0;
+        }
+    }
+}

Modified: directory/apacheds/branches/ldif-partition/server-xml/src/test/java/org/apache/directory/server/SpringServerTest.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/ldif-partition/server-xml/src/test/java/org/apache/directory/server/SpringServerTest.java?rev=760740&r1=760739&r2=760740&view=diff
==============================================================================
--- directory/apacheds/branches/ldif-partition/server-xml/src/test/java/org/apache/directory/server/SpringServerTest.java (original)
+++ directory/apacheds/branches/ldif-partition/server-xml/src/test/java/org/apache/directory/server/SpringServerTest.java Wed Apr  1 00:00:26 2009
@@ -26,7 +26,6 @@
 import org.apache.directory.server.core.authn.Authenticator;
 import org.apache.directory.server.core.authn.SimpleAuthenticator;
 import org.apache.directory.server.core.authn.StrongAuthenticator;
-import org.apache.directory.server.core.interceptor.Interceptor;
 import org.apache.xbean.spring.context.FileSystemXmlApplicationContext;
 import org.junit.Test;
 import org.springframework.context.ApplicationContext;

Modified: directory/project/trunk/resources/dictionary
URL: http://svn.apache.org/viewvc/directory/project/trunk/resources/dictionary?rev=760740&r1=760739&r2=760740&view=diff
==============================================================================
--- directory/project/trunk/resources/dictionary (original)
+++ directory/project/trunk/resources/dictionary Wed Apr  1 00:00:26 2009
@@ -26,3 +26,4 @@
 Rev
 interceptors
 resusitated
+multi