directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1389184 [8/13] - in /directory/apacheds/trunk: core-annotations/src/main/java/org/apache/directory/server/core/factory/ core-api/src/main/java/org/apache/directory/server/core/api/ core-api/src/main/java/org/apache/directory/server/core/ap...
Date Mon, 24 Sep 2012 02:17:20 GMT
Added: directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/DescendantCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/DescendantCursor.java?rev=1389184&view=auto
==============================================================================
--- directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/DescendantCursor.java (added)
+++ directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/DescendantCursor.java Mon Sep 24 02:17:13 2012
@@ -0,0 +1,365 @@
+/*
+ *  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.xdbm.search.cursor;
+
+
+import org.apache.commons.collections.ArrayStack;
+import org.apache.directory.server.i18n.I18n;
+import org.apache.directory.server.xdbm.AbstractIndexCursor;
+import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.ParentIdAndRdn;
+import org.apache.directory.server.xdbm.Store;
+import org.apache.directory.shared.ldap.model.cursor.Cursor;
+import org.apache.directory.shared.ldap.model.name.Rdn;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+
+/**
+ * A Cursor over entries satisfying one level scope constraints with alias
+ * dereferencing considerations when enabled during search.
+ * We use the Rdn index to fetch all the descendants of a given entry.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class DescendantCursor extends AbstractIndexCursor<String>
+{
+    /** A dedicated log for cursors */
+    private static final Logger LOG_CURSOR = LoggerFactory.getLogger( "CURSOR" );
+
+    /** Error message for unsupported operations */
+    private static final String UNSUPPORTED_MSG = I18n.err( I18n.ERR_719 );
+
+    /** The entry database/store */
+    private final Store db;
+
+    /** The prefetched element */
+    private IndexEntry prefetched;
+
+    /** The current Cursor over the entries in the scope of the search base */
+    private Cursor<IndexEntry<ParentIdAndRdn, String>> currentCursor;
+
+    /** The current Parent ID */
+    private String currentParentId;
+
+    /** The stack of cursors used to process the depth-first traversal */
+    private ArrayStack cursorStack;
+
+    /** The stack of parentIds used to process the depth-first traversal */
+    private ArrayStack parentIdStack;
+
+    /** The initial entry ID we are looking descendants for */
+    private String baseId;
+
+    /** A flag to tell that we are in the top level cursor or not */
+    private boolean topLevel;
+
+    protected static final boolean TOP_LEVEL = true;
+    protected static final boolean INNER = false;
+
+
+    /**
+     * Creates a Cursor over entries satisfying one level scope criteria.
+     *
+     * @param db the entry store
+     * @param evaluator an IndexEntry (candidate) evaluator
+     * @throws Exception on db access failures
+     */
+    public DescendantCursor( Store db, String baseId, String parentId,
+        Cursor<IndexEntry<ParentIdAndRdn, String>> cursor )
+        throws Exception
+    {
+        this( db, baseId, parentId, cursor, TOP_LEVEL );
+    }
+
+
+    /**
+     * Creates a Cursor over entries satisfying one level scope criteria.
+     *
+     * @param db the entry store
+     * @param evaluator an IndexEntry (candidate) evaluator
+     * @throws Exception on db access failures
+     */
+    public DescendantCursor( Store db, String baseId, String parentId,
+        Cursor<IndexEntry<ParentIdAndRdn, String>> cursor,
+        boolean topLevel )
+        throws Exception
+    {
+        this.db = db;
+        currentParentId = parentId;
+        currentCursor = cursor;
+        cursorStack = new ArrayStack();
+        parentIdStack = new ArrayStack();
+        this.baseId = baseId;
+        this.topLevel = topLevel;
+        LOG_CURSOR.debug( "Creating ChildrenCursor {}", this );
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    protected String getUnsupportedMessage()
+    {
+        return UNSUPPORTED_MSG;
+    }
+
+
+    public void beforeFirst() throws Exception
+    {
+        checkNotClosed( "beforeFirst()" );
+        setAvailable( false );
+    }
+
+
+    public void afterLast() throws Exception
+    {
+        throw new UnsupportedOperationException( getUnsupportedMessage() );
+    }
+
+
+    public boolean first() throws Exception
+    {
+        beforeFirst();
+
+        return next();
+    }
+
+
+    public boolean last() throws Exception
+    {
+        throw new UnsupportedOperationException( getUnsupportedMessage() );
+    }
+
+
+    public boolean previous() throws Exception
+    {
+        checkNotClosed( "next()" );
+
+        boolean hasPrevious = currentCursor.previous();
+
+        if ( hasPrevious )
+        {
+            IndexEntry entry = currentCursor.get();
+
+            if ( ( ( ParentIdAndRdn ) entry.getTuple().getKey() ).getParentId().equals( currentParentId ) )
+            {
+                prefetched = entry;
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean next() throws Exception
+    {
+        checkNotClosed( "next()" );
+        boolean finished = false;
+
+        while ( !finished )
+        {
+            boolean hasNext = currentCursor.next();
+
+            // We will use a depth first approach. The alternative (Breadth-first) would be
+            // too memory consuming. 
+            // The idea is to use a ChildrenCursor each time we have an entry with chidren, 
+            // and process recursively.
+            if ( hasNext )
+            {
+                IndexEntry cursorEntry = currentCursor.get();
+                ParentIdAndRdn parentIdAndRdn = ( ( ParentIdAndRdn ) ( cursorEntry.getKey() ) );
+
+                // Check that we aren't out of the cursor's limit
+                if ( !parentIdAndRdn.getParentId().equals( currentParentId ) )
+                {
+                    // Ok, we went too far. Unstack the cursor and return
+                    finished = cursorStack.size() == 0;
+
+                    if ( !finished )
+                    {
+                        currentCursor.close();
+                        currentCursor = ( Cursor<IndexEntry<ParentIdAndRdn, String>> ) cursorStack.pop();
+                        currentParentId = ( String ) parentIdStack.pop();
+                    }
+
+                    // And continue...
+                }
+                else
+                {
+                    // We have a candidate, it will be returned.
+                    if ( topLevel )
+                    {
+                        prefetched = new IndexEntry();
+                        prefetched.setId( cursorEntry.getId() );
+                        prefetched.setKey( baseId );
+                    }
+                    else
+                    {
+                        prefetched = cursorEntry;
+                    }
+
+                    // Check if the current entry has children or not.
+                    if ( parentIdAndRdn.getNbDescendants() > 0 )
+                    {
+                        String newParentId = ( String ) cursorEntry.getId();
+
+                        // Yes, then create a new cursor and go down one level
+                        Cursor<IndexEntry<ParentIdAndRdn, String>> cursor = db.getRdnIndex().forwardCursor();
+
+                        IndexEntry<ParentIdAndRdn, String> startingPos = new IndexEntry<ParentIdAndRdn, String>();
+                        startingPos.setKey( new ParentIdAndRdn( newParentId, ( Rdn[] ) null ) );
+                        cursor.before( startingPos );
+
+                        cursorStack.push( currentCursor );
+                        parentIdStack.push( currentParentId );
+
+                        currentCursor = cursor;
+                        currentParentId = newParentId;
+                    }
+
+                    return true;
+                }
+            }
+            else
+            {
+                // The current cursor has been exhausted. Get back to the parent's cursor.
+                finished = cursorStack.size() == 0;
+
+                if ( !finished )
+                {
+                    currentCursor.close();
+                    currentCursor = ( Cursor<IndexEntry<ParentIdAndRdn, String>> ) cursorStack.pop();
+                    currentParentId = ( String ) parentIdStack.pop();
+                }
+                // and continue...
+            }
+        }
+
+        return false;
+    }
+
+
+    public IndexEntry<String, String> get() throws Exception
+    {
+        checkNotClosed( "get()" );
+
+        return prefetched;
+    }
+
+
+    @Override
+    public void close() throws Exception
+    {
+        LOG_CURSOR.debug( "Closing ChildrenCursor {}", this );
+
+        // Close the cursors stored in the stack, if we have some
+        for ( Object cursor : cursorStack )
+        {
+            ( ( Cursor<IndexEntry<?, ?>> ) cursor ).close();
+        }
+
+        // And finally, close the current cursor
+        currentCursor.close();
+
+        super.close();
+    }
+
+
+    @Override
+    public void close( Exception cause ) throws Exception
+    {
+        LOG_CURSOR.debug( "Closing ChildrenCursor {}", this );
+
+        // Close the cursors stored in the stack, if we have some
+        for ( Object cursor : cursorStack )
+        {
+            ( ( Cursor<IndexEntry<?, ?>> ) cursor ).close( cause );
+        }
+
+        // And finally, close the current cursor
+        currentCursor.close( cause );
+
+        super.close( cause );
+    }
+
+
+    /**
+     * Dumps the cursors
+     */
+    private String dumpCursors( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        for ( Object cursor : cursorStack )
+        {
+            sb.append( ( ( Cursor<IndexEntry<ParentIdAndRdn, String>> ) cursor ).toString( tabs + "  " ) );
+            sb.append( "\n" );
+        }
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( tabs ).append( "DescendantCursor (" );
+
+        if ( available() )
+        {
+            sb.append( "available)" );
+        }
+        else
+        {
+            sb.append( "absent)" );
+        }
+
+        sb.append( "#baseId<" ).append( baseId );
+        sb.append( ", " ).append( db ).append( "> :\n" );
+
+        sb.append( dumpCursors( tabs + "  " ) );
+
+        if ( currentCursor != null )
+        {
+            sb.append( tabs + "  <current>\n" );
+            sb.append( currentCursor.toString( tabs + "    " ) );
+        }
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return toString( "" );
+    }
+}
\ No newline at end of file

Added: directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/EqualityCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/EqualityCursor.java?rev=1389184&view=auto
==============================================================================
--- directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/EqualityCursor.java (added)
+++ directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/EqualityCursor.java Mon Sep 24 02:17:13 2012
@@ -0,0 +1,370 @@
+/*
+ *  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.xdbm.search.cursor;
+
+
+import org.apache.directory.server.i18n.I18n;
+import org.apache.directory.server.xdbm.AbstractIndexCursor;
+import org.apache.directory.server.xdbm.Index;
+import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.Store;
+import org.apache.directory.server.xdbm.search.evaluator.EqualityEvaluator;
+import org.apache.directory.shared.ldap.model.cursor.Cursor;
+import org.apache.directory.shared.ldap.model.cursor.InvalidCursorPositionException;
+import org.apache.directory.shared.ldap.model.entry.Entry;
+import org.apache.directory.shared.ldap.model.entry.Value;
+import org.apache.directory.shared.ldap.model.schema.AttributeType;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+
+/**
+ * A Cursor over entry candidates matching an equality assertion filter.  This
+ * Cursor operates in two modes.  The first is when an index exists for the
+ * attribute the equality assertion is built on.  The second is when the user
+ * index for the assertion attribute does not exist.  Different Cursors are
+ * used in each of these cases where the other remains null.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class EqualityCursor<V> extends AbstractIndexCursor<V>
+{
+    /** A dedicated log for cursors */
+    private static final Logger LOG_CURSOR = LoggerFactory.getLogger( "CURSOR" );
+
+    /** The message for unsupported operations */
+    private static final String UNSUPPORTED_MSG = I18n.err( I18n.ERR_714 );
+
+    /** An equality evaluator for candidates */
+    private final EqualityEvaluator<V> equalityEvaluator;
+
+    /** Cursor over attribute entry matching filter: set when index present */
+    private final Cursor<IndexEntry<V, String>> userIdxCursor;
+
+    /** NDN Cursor on all entries in  (set when no index on user attribute) */
+    private final Cursor<IndexEntry<String, String>> uuidIdxCursor;
+
+
+    /**
+     * Creates a new instance of an EqualityCursor
+     * @param store The store
+     * @param equalityEvaluator The EqualityEvaluator
+     * @throws Exception If the creation failed
+     */
+    @SuppressWarnings("unchecked")
+    public EqualityCursor( Store store, EqualityEvaluator<V> equalityEvaluator ) throws Exception
+    {
+        LOG_CURSOR.debug( "Creating EqualityCursor {}", this );
+        this.equalityEvaluator = equalityEvaluator;
+
+        AttributeType attributeType = equalityEvaluator.getExpression().getAttributeType();
+        Value<V> value = equalityEvaluator.getExpression().getValue();
+
+        if ( store.hasIndexOn( attributeType ) )
+        {
+            Index<V, Entry, String> userIndex = ( Index<V, Entry, String> ) store.getIndex( attributeType );
+            userIdxCursor = userIndex.forwardCursor( value.getValue() );
+            uuidIdxCursor = null;
+        }
+        else
+        {
+            uuidIdxCursor = new AllEntriesCursor( store );
+            userIdxCursor = null;
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    protected String getUnsupportedMessage()
+    {
+        return UNSUPPORTED_MSG;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean available()
+    {
+        if ( userIdxCursor != null )
+        {
+            return userIdxCursor.available();
+        }
+
+        return super.available();
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void before( IndexEntry<V, String> element ) throws Exception
+    {
+        checkNotClosed( "before()" );
+
+        if ( userIdxCursor != null )
+        {
+            userIdxCursor.before( element );
+        }
+        else
+        {
+            super.before( element );
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void after( IndexEntry<V, String> element ) throws Exception
+    {
+        checkNotClosed( "after()" );
+
+        if ( userIdxCursor != null )
+        {
+            userIdxCursor.after( element );
+        }
+        else
+        {
+            super.after( element );
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void beforeFirst() throws Exception
+    {
+        checkNotClosed( "beforeFirst()" );
+
+        if ( userIdxCursor != null )
+        {
+            userIdxCursor.beforeFirst();
+        }
+        else
+        {
+            uuidIdxCursor.beforeFirst();
+        }
+
+        setAvailable( false );
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void afterLast() throws Exception
+    {
+        checkNotClosed( "afterLast()" );
+
+        if ( userIdxCursor != null )
+        {
+            userIdxCursor.afterLast();
+        }
+        else
+        {
+            uuidIdxCursor.afterLast();
+        }
+
+        setAvailable( false );
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean first() throws Exception
+    {
+        beforeFirst();
+
+        return next();
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean last() throws Exception
+    {
+        afterLast();
+
+        return previous();
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean previous() throws Exception
+    {
+        if ( userIdxCursor != null )
+        {
+            return userIdxCursor.previous();
+        }
+
+        while ( uuidIdxCursor.previous() )
+        {
+            checkNotClosed( "previous()" );
+            IndexEntry<?, String> candidate = uuidIdxCursor.get();
+
+            if ( equalityEvaluator.evaluate( candidate ) )
+            {
+                return setAvailable( true );
+            }
+        }
+
+        return setAvailable( false );
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean next() throws Exception
+    {
+        if ( userIdxCursor != null )
+        {
+            return userIdxCursor.next();
+        }
+
+        while ( uuidIdxCursor.next() )
+        {
+            checkNotClosed( "next()" );
+            IndexEntry<?, String> candidate = uuidIdxCursor.get();
+
+            if ( equalityEvaluator.evaluate( candidate ) )
+            {
+                return setAvailable( true );
+            }
+        }
+
+        return setAvailable( false );
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    @SuppressWarnings("unchecked")
+    public IndexEntry<V, String> get() throws Exception
+    {
+        checkNotClosed( "get()" );
+
+        if ( userIdxCursor != null )
+        {
+            return userIdxCursor.get();
+        }
+
+        if ( available() )
+        {
+            return ( IndexEntry<V, String> ) uuidIdxCursor.get();
+        }
+
+        throw new InvalidCursorPositionException( I18n.err( I18n.ERR_708 ) );
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void close() throws Exception
+    {
+        LOG_CURSOR.debug( "Closing EqualityCursor {}", this );
+        super.close();
+
+        if ( userIdxCursor != null )
+        {
+            userIdxCursor.close();
+        }
+        else
+        {
+            uuidIdxCursor.close();
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void close( Exception cause ) throws Exception
+    {
+        LOG_CURSOR.debug( "Closing EqualityCursor {}", this );
+        super.close( cause );
+
+        if ( userIdxCursor != null )
+        {
+            userIdxCursor.close( cause );
+        }
+        else
+        {
+            uuidIdxCursor.close( cause );
+        }
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( tabs ).append( "EqualityCursor (" );
+
+        if ( available() )
+        {
+            sb.append( "available)" );
+        }
+        else
+        {
+            sb.append( "absent)" );
+        }
+
+        sb.append( " :\n" );
+
+        sb.append( tabs + "  >>" ).append( equalityEvaluator );
+
+        if ( userIdxCursor != null )
+        {
+            sb.append( tabs + "  <user>\n" );
+            sb.append( userIdxCursor.toString( tabs + "    " ) );
+        }
+
+        if ( uuidIdxCursor != null )
+        {
+            sb.append( tabs + "  <uuid>\n" );
+            sb.append( uuidIdxCursor.toString( tabs + "  " ) );
+        }
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return toString( "" );
+    }
+}

Added: directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/GreaterEqCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/GreaterEqCursor.java?rev=1389184&view=auto
==============================================================================
--- directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/GreaterEqCursor.java (added)
+++ directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/GreaterEqCursor.java Mon Sep 24 02:17:13 2012
@@ -0,0 +1,439 @@
+/*
+ *  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.xdbm.search.cursor;
+
+
+import org.apache.directory.server.i18n.I18n;
+import org.apache.directory.server.xdbm.AbstractIndexCursor;
+import org.apache.directory.server.xdbm.Index;
+import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.Store;
+import org.apache.directory.server.xdbm.search.evaluator.GreaterEqEvaluator;
+import org.apache.directory.shared.ldap.model.cursor.Cursor;
+import org.apache.directory.shared.ldap.model.cursor.InvalidCursorPositionException;
+import org.apache.directory.shared.ldap.model.entry.Entry;
+import org.apache.directory.shared.ldap.model.schema.AttributeType;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+
+/**
+ * A Cursor over entry candidates matching a GreaterEq assertion filter.  This
+ * Cursor operates in two modes.  The first is when an index exists for the
+ * attribute the assertion is built on.  The second is when the user index for
+ * the assertion attribute does not exist.  Different Cursors are used in each
+ * of these cases where the other remains null.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class GreaterEqCursor<V> extends AbstractIndexCursor<V>
+{
+    /** A dedicated log for cursors */
+    private static final Logger LOG_CURSOR = LoggerFactory.getLogger( "CURSOR" );
+
+    private static final String UNSUPPORTED_MSG = "GreaterEqCursors only support positioning by element when a user index exists on the asserted attribute.";
+
+    /** An greater eq evaluator for candidates */
+    private final GreaterEqEvaluator<V> greaterEqEvaluator;
+
+    /** Cursor over attribute entry matching filter: set when index present */
+    private final Cursor<IndexEntry<V, String>> userIdxCursor;
+
+    /** NDN Cursor on all entries in  (set when no index on user attribute) */
+    private final Cursor<IndexEntry<String, String>> uuidIdxCursor;
+
+    /**
+     * Used to store indexEntry from uuidCandidate so it can be saved after
+     * call to evaluate() which changes the value so it's not referring to
+     * the NDN but to the value of the attribute instead.
+     */
+    private IndexEntry<String, String> uuidCandidate;
+
+
+    /**
+     * Creates a new instance of an GreaterEqCursor
+     * @param store The store
+     * @param equalityEvaluator The GreaterEqEvaluator
+     * @throws Exception If the creation failed
+     */
+    @SuppressWarnings("unchecked")
+    public GreaterEqCursor( Store store, GreaterEqEvaluator<V> greaterEqEvaluator ) throws Exception
+    {
+        LOG_CURSOR.debug( "Creating GreaterEqCursor {}", this );
+        this.greaterEqEvaluator = greaterEqEvaluator;
+
+        AttributeType attributeType = greaterEqEvaluator.getExpression().getAttributeType();
+
+        if ( store.hasIndexOn( attributeType ) )
+        {
+            userIdxCursor = ( ( Index<V, Entry, String> ) store.getIndex( attributeType ) ).forwardCursor();
+            uuidIdxCursor = null;
+        }
+        else
+        {
+            uuidIdxCursor = new AllEntriesCursor( store );
+            userIdxCursor = null;
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    protected String getUnsupportedMessage()
+    {
+        return UNSUPPORTED_MSG;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void before( IndexEntry<V, String> element ) throws Exception
+    {
+        checkNotClosed( "before()" );
+
+        if ( userIdxCursor != null )
+        {
+            /*
+             * First we need to check and make sure this element is within
+             * bounds as mandated by the assertion node.  To do so we compare
+             * it's value with the value of the node.  If it is smaller or
+             * equal to this lower bound then we simply position the
+             * userIdxCursor before the first element.  Otherwise we let the
+             * underlying userIdx Cursor position the element.
+             */
+            if ( greaterEqEvaluator.getComparator().compare( element.getKey(),
+                greaterEqEvaluator.getExpression().getValue().getValue() ) <= 0 )
+            {
+                beforeFirst();
+                return;
+            }
+
+            userIdxCursor.before( element );
+            setAvailable( false );
+        }
+        else
+        {
+            super.before( element );
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void after( IndexEntry<V, String> element ) throws Exception
+    {
+        checkNotClosed( "after()" );
+
+        if ( userIdxCursor != null )
+        {
+            int comparedValue = greaterEqEvaluator.getComparator().compare( element.getKey(),
+                greaterEqEvaluator.getExpression().getValue().getValue() );
+
+            /*
+             * First we need to check and make sure this element is within
+             * bounds as mandated by the assertion node.  To do so we compare
+             * it's value with the value of the node.  If it is equal to this
+             * lower bound then we simply position the userIdxCursor after
+             * this first node.  If it is less than this value then we
+             * position the Cursor before the first entry.
+             */
+            if ( comparedValue == 0 )
+            {
+                userIdxCursor.after( element );
+                setAvailable( false );
+
+                return;
+            }
+
+            if ( comparedValue < 0 )
+            {
+                beforeFirst();
+
+                return;
+            }
+
+            // Element is in the valid range as specified by assertion
+            userIdxCursor.after( element );
+            setAvailable( false );
+        }
+        else
+        {
+            super.after( element );
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    @SuppressWarnings("unchecked")
+    public void beforeFirst() throws Exception
+    {
+        checkNotClosed( "beforeFirst()" );
+
+        if ( userIdxCursor != null )
+        {
+            IndexEntry<V, String> advanceTo = new IndexEntry<V, String>();
+            advanceTo.setKey( ( V ) greaterEqEvaluator.getExpression().getValue().getValue() );
+            userIdxCursor.before( advanceTo );
+        }
+        else
+        {
+            uuidIdxCursor.beforeFirst();
+            uuidCandidate = null;
+        }
+
+        setAvailable( false );
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void afterLast() throws Exception
+    {
+        checkNotClosed( "afterLast()" );
+
+        if ( userIdxCursor != null )
+        {
+            userIdxCursor.afterLast();
+        }
+        else
+        {
+            uuidIdxCursor.afterLast();
+            uuidCandidate = null;
+        }
+
+        setAvailable( false );
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean first() throws Exception
+    {
+        beforeFirst();
+
+        return next();
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean last() throws Exception
+    {
+        afterLast();
+
+        return previous();
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean previous() throws Exception
+    {
+        checkNotClosed( "previous()" );
+
+        if ( userIdxCursor != null )
+        {
+            /*
+             * We have to check and make sure the previous value complies by
+             * being greater than or eq to the expression node's value
+             */
+            while ( userIdxCursor.previous() )
+            {
+                checkNotClosed( "previous()" );
+                IndexEntry<?, String> candidate = userIdxCursor.get();
+
+                if ( greaterEqEvaluator.getComparator().compare( candidate.getKey(),
+                    greaterEqEvaluator.getExpression().getValue().getValue() ) >= 0 )
+                {
+                    return setAvailable( true );
+                }
+            }
+
+            return setAvailable( false );
+        }
+
+        while ( uuidIdxCursor.previous() )
+        {
+            checkNotClosed( "previous()" );
+            uuidCandidate = uuidIdxCursor.get();
+
+            if ( greaterEqEvaluator.evaluate( uuidCandidate ) )
+            {
+                return setAvailable( true );
+            }
+        }
+
+        return setAvailable( false );
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean next() throws Exception
+    {
+        checkNotClosed( "next()" );
+
+        if ( userIdxCursor != null )
+        {
+            /*
+             * No need to do the same check that is done in previous() since
+             * values are increasing with calls to next().
+             */
+            return setAvailable( userIdxCursor.next() );
+        }
+
+        while ( uuidIdxCursor.next() )
+        {
+            checkNotClosed( "next()" );
+            uuidCandidate = uuidIdxCursor.get();
+
+            if ( greaterEqEvaluator.evaluate( uuidCandidate ) )
+            {
+                return setAvailable( true );
+            }
+        }
+
+        return setAvailable( false );
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    @SuppressWarnings("unchecked")
+    public IndexEntry<V, String> get() throws Exception
+    {
+        checkNotClosed( "get()" );
+
+        if ( userIdxCursor != null )
+        {
+            if ( available() )
+            {
+                return userIdxCursor.get();
+            }
+
+            throw new InvalidCursorPositionException( I18n.err( I18n.ERR_708 ) );
+        }
+
+        if ( available() )
+        {
+            return ( IndexEntry<V, String> ) uuidCandidate;
+        }
+
+        throw new InvalidCursorPositionException( I18n.err( I18n.ERR_708 ) );
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void close() throws Exception
+    {
+        LOG_CURSOR.debug( "Closing GreaterEqCursor {}", this );
+        super.close();
+
+        if ( userIdxCursor != null )
+        {
+            userIdxCursor.close();
+        }
+        else
+        {
+            uuidIdxCursor.close();
+            uuidCandidate = null;
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void close( Exception cause ) throws Exception
+    {
+        LOG_CURSOR.debug( "Closing GreaterEqCursor {}", this );
+        super.close( cause );
+
+        if ( userIdxCursor != null )
+        {
+            userIdxCursor.close( cause );
+        }
+        else
+        {
+            uuidIdxCursor.close( cause );
+            uuidCandidate = null;
+        }
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( tabs ).append( "GreaterEqCursor (" );
+
+        if ( available() )
+        {
+            sb.append( "available)" );
+        }
+        else
+        {
+            sb.append( "absent)" );
+        }
+
+        sb.append( "#candidate<" ).append( uuidCandidate ).append( ">:\n" );
+
+        sb.append( tabs + "  >>" ).append( greaterEqEvaluator ).append( '\n' );
+
+        if ( userIdxCursor != null )
+        {
+            sb.append( tabs + "  <user>\n" );
+            sb.append( userIdxCursor.toString( tabs + "    " ) );
+        }
+
+        if ( uuidIdxCursor != null )
+        {
+            sb.append( tabs + "  <uuid>\n" );
+            sb.append( uuidIdxCursor.toString( tabs + "  " ) );
+        }
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return toString( "" );
+    }
+}
\ No newline at end of file

Added: directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/LessEqCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/LessEqCursor.java?rev=1389184&view=auto
==============================================================================
--- directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/LessEqCursor.java (added)
+++ directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/LessEqCursor.java Mon Sep 24 02:17:13 2012
@@ -0,0 +1,423 @@
+/*
+ *  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.xdbm.search.cursor;
+
+
+import org.apache.directory.server.i18n.I18n;
+import org.apache.directory.server.xdbm.AbstractIndexCursor;
+import org.apache.directory.server.xdbm.Index;
+import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.Store;
+import org.apache.directory.server.xdbm.search.evaluator.LessEqEvaluator;
+import org.apache.directory.shared.ldap.model.cursor.Cursor;
+import org.apache.directory.shared.ldap.model.cursor.InvalidCursorPositionException;
+import org.apache.directory.shared.ldap.model.entry.Entry;
+import org.apache.directory.shared.ldap.model.schema.AttributeType;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+
+/**
+ * A Cursor over entry candidates matching a LessEq assertion filter.  This
+ * Cursor operates in two modes.  The first is when an index exists for the
+ * attribute the assertion is built on.  The second is when the user index for
+ * the assertion attribute does not exist.  Different Cursors are used in each
+ * of these cases where the other remains null.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class LessEqCursor<V> extends AbstractIndexCursor<V>
+{
+    /** A dedicated log for cursors */
+    private static final Logger LOG_CURSOR = LoggerFactory.getLogger( "CURSOR" );
+
+    private static final String UNSUPPORTED_MSG = I18n.err( I18n.ERR_716 );
+
+    /** An less eq evaluator for candidates */
+    private final LessEqEvaluator<V> lessEqEvaluator;
+
+    /** Cursor over attribute entry matching filter: set when index present */
+    private final Cursor<IndexEntry<V, String>> userIdxCursor;
+
+    /** NDN Cursor on all entries in  (set when no index on user attribute) */
+    private final Cursor<IndexEntry<String, String>> uuidIdxCursor;
+
+    /**
+     * Used to store indexEntry from uudCandidate so it can be saved after
+     * call to evaluate() which changes the value so it's not referring to
+     * the String but to the value of the attribute instead.
+     */
+    private IndexEntry<String, String> uuidCandidate;
+
+
+    @SuppressWarnings("unchecked")
+    public LessEqCursor( Store store, LessEqEvaluator<V> lessEqEvaluator ) throws Exception
+    {
+        LOG_CURSOR.debug( "Creating LessEqCursor {}", this );
+        this.lessEqEvaluator = lessEqEvaluator;
+
+        AttributeType attributeType = lessEqEvaluator.getExpression().getAttributeType();
+
+        if ( store.hasIndexOn( attributeType ) )
+        {
+            userIdxCursor = ( ( Index<V, Entry, String> ) store.getIndex( attributeType ) ).forwardCursor();
+            uuidIdxCursor = null;
+        }
+        else
+        {
+            uuidIdxCursor = new AllEntriesCursor( store );
+            userIdxCursor = null;
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    protected String getUnsupportedMessage()
+    {
+        return UNSUPPORTED_MSG;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void before( IndexEntry<V, String> element ) throws Exception
+    {
+        checkNotClosed( "before()" );
+
+        if ( userIdxCursor != null )
+        {
+            /*
+             * First we need to check and make sure this element is within
+             * bounds as mandated by the assertion node.  To do so we compare
+             * it's value with the value of the expression node.  If the
+             * element's value is greater than this upper bound then we
+             * position the userIdxCursor after the last node.
+             *
+             * If the element's value is equal to this upper bound then we
+             * position the userIdxCursor right before the last node.
+             *
+             * If the element's value is smaller, then we delegate to the
+             * before() method of the userIdxCursor.
+             */
+            int compareValue = lessEqEvaluator.getComparator().compare( element.getKey(),
+                lessEqEvaluator.getExpression().getValue().getValue() );
+
+            if ( compareValue > 0 )
+            {
+                afterLast();
+                return;
+            }
+            else if ( compareValue == 0 )
+            {
+                last();
+                previous();
+                setAvailable( false );
+                return;
+            }
+
+            userIdxCursor.before( element );
+            setAvailable( false );
+        }
+        else
+        {
+            super.before( element );
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void after( IndexEntry<V, String> element ) throws Exception
+    {
+        checkNotClosed( "after()" );
+
+        if ( userIdxCursor != null )
+        {
+            int comparedValue = lessEqEvaluator.getComparator().compare( element.getKey(),
+                lessEqEvaluator.getExpression().getValue().getValue() );
+
+            /*
+             * First we need to check and make sure this element is within
+             * bounds as mandated by the assertion node.  To do so we compare
+             * it's value with the value of the expression node.
+             *
+             * If the element's value is equal to or greater than this upper
+             * bound then we position the userIdxCursor after the last node.
+             *
+             * If the element's value is smaller, then we delegate to the
+             * after() method of the userIdxCursor.
+             */
+            if ( comparedValue >= 0 )
+            {
+                afterLast();
+                return;
+            }
+
+            // Element is in the valid range as specified by assertion
+            userIdxCursor.after( element );
+            setAvailable( false );
+        }
+        else
+        {
+            super.after( element );
+        }
+    }
+
+
+    public void beforeFirst() throws Exception
+    {
+        checkNotClosed( "beforeFirst()" );
+        if ( userIdxCursor != null )
+        {
+            userIdxCursor.beforeFirst();
+        }
+        else
+        {
+            uuidIdxCursor.beforeFirst();
+            uuidCandidate = null;
+        }
+
+        setAvailable( false );
+    }
+
+
+    public void afterLast() throws Exception
+    {
+        checkNotClosed( "afterLast()" );
+        if ( userIdxCursor != null )
+        {
+            IndexEntry<V, String> advanceTo = new IndexEntry<V, String>();
+            //noinspection unchecked
+            advanceTo.setKey( lessEqEvaluator.getExpression().getValue().getValue() );
+            userIdxCursor.after( advanceTo );
+        }
+        else
+        {
+            uuidIdxCursor.afterLast();
+            uuidCandidate = null;
+        }
+
+        setAvailable( false );
+    }
+
+
+    public boolean first() throws Exception
+    {
+        beforeFirst();
+        return next();
+    }
+
+
+    public boolean last() throws Exception
+    {
+        afterLast();
+        return previous();
+    }
+
+
+    public boolean previous() throws Exception
+    {
+        checkNotClosed( "previous()" );
+
+        if ( userIdxCursor != null )
+        {
+            /*
+             * No need to do the same check that is done in next() since
+             * values are decreasing with calls to previous().  We will
+             * always have lesser values.
+             */
+            return setAvailable( userIdxCursor.previous() );
+        }
+
+        while ( uuidIdxCursor.previous() )
+        {
+            checkNotClosed( "previous()" );
+            uuidCandidate = uuidIdxCursor.get();
+
+            if ( lessEqEvaluator.evaluate( uuidCandidate ) )
+            {
+                return setAvailable( true );
+            }
+            else
+            {
+                uuidCandidate = null;
+            }
+        }
+
+        return setAvailable( false );
+    }
+
+
+    public boolean next() throws Exception
+    {
+        checkNotClosed( "next()" );
+
+        if ( userIdxCursor != null )
+        {
+            /*
+             * We have to check and make sure the next value complies by
+             * being less than or eq to the expression node's value.  We need
+             * to do this since values are increasing and we must limit to our
+             * upper bound.
+             */
+            while ( userIdxCursor.next() )
+            {
+                checkNotClosed( "next()" );
+                IndexEntry<?, String> candidate = userIdxCursor.get();
+
+                if ( lessEqEvaluator.getComparator().compare( candidate.getKey(),
+                    lessEqEvaluator.getExpression().getValue().getValue() ) <= 0 )
+                {
+                    return setAvailable( true );
+                }
+            }
+
+            return setAvailable( false );
+        }
+
+        while ( uuidIdxCursor.next() )
+        {
+            checkNotClosed( "next()" );
+            uuidCandidate = uuidIdxCursor.get();
+
+            if ( lessEqEvaluator.evaluate( uuidCandidate ) )
+            {
+                return setAvailable( true );
+            }
+            else
+            {
+                uuidCandidate = null;
+            }
+        }
+
+        return setAvailable( false );
+    }
+
+
+    public IndexEntry<V, String> get() throws Exception
+    {
+        checkNotClosed( "get()" );
+
+        if ( userIdxCursor != null )
+        {
+            if ( available() )
+            {
+                return userIdxCursor.get();
+            }
+
+            throw new InvalidCursorPositionException( I18n.err( I18n.ERR_708 ) );
+        }
+
+        if ( available() )
+        {
+            return ( IndexEntry<V, String> ) uuidCandidate;
+        }
+
+        throw new InvalidCursorPositionException( I18n.err( I18n.ERR_708 ) );
+    }
+
+
+    public void close() throws Exception
+    {
+        LOG_CURSOR.debug( "Closing LessEqCursor {}", this );
+        super.close();
+
+        if ( userIdxCursor != null )
+        {
+            userIdxCursor.close();
+        }
+        else
+        {
+            uuidIdxCursor.close();
+            uuidCandidate = null;
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void close( Exception cause ) throws Exception
+    {
+        LOG_CURSOR.debug( "Closing LessEqCursor {}", this );
+        super.close( cause );
+
+        if ( userIdxCursor != null )
+        {
+            userIdxCursor.close( cause );
+        }
+        else
+        {
+            uuidIdxCursor.close( cause );
+            uuidCandidate = null;
+        }
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( tabs ).append( "LessEqCursor (" );
+
+        if ( available() )
+        {
+            sb.append( "available)" );
+        }
+        else
+        {
+            sb.append( "absent)" );
+        }
+
+        sb.append( "#candidate<" ).append( uuidCandidate ).append( ">:\n" );
+
+        sb.append( tabs + "  >>" ).append( lessEqEvaluator ).append( '\n' );
+
+        if ( userIdxCursor != null )
+        {
+            sb.append( tabs + "  <user>\n" );
+            sb.append( userIdxCursor.toString( tabs + "    " ) );
+        }
+
+        if ( uuidIdxCursor != null )
+        {
+            sb.append( tabs + "  <uuid>\n" );
+            sb.append( uuidIdxCursor.toString( tabs + "  " ) );
+        }
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return toString( "" );
+    }
+}
\ No newline at end of file

Added: directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/NotCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/NotCursor.java?rev=1389184&view=auto
==============================================================================
--- directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/NotCursor.java (added)
+++ directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/NotCursor.java Mon Sep 24 02:17:13 2012
@@ -0,0 +1,197 @@
+/*
+ *  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.xdbm.search.cursor;
+
+
+import org.apache.directory.server.i18n.I18n;
+import org.apache.directory.server.xdbm.AbstractIndexCursor;
+import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.Store;
+import org.apache.directory.server.xdbm.search.Evaluator;
+import org.apache.directory.shared.ldap.model.cursor.InvalidCursorPositionException;
+import org.apache.directory.shared.ldap.model.filter.ExprNode;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+
+/**
+ * A Cursor returning candidates satisfying a logical negation expression.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class NotCursor<V> extends AbstractIndexCursor<V>
+{
+    /** A dedicated log for cursors */
+    private static final Logger LOG_CURSOR = LoggerFactory.getLogger( "CURSOR" );
+
+    private static final String UNSUPPORTED_MSG = I18n.err( I18n.ERR_718 );
+    private final AllEntriesCursor uuidCursor;
+    private final Evaluator<? extends ExprNode> childEvaluator;
+
+
+    @SuppressWarnings("unchecked")
+    public NotCursor( Store store, Evaluator<? extends ExprNode> childEvaluator )
+        throws Exception
+    {
+        LOG_CURSOR.debug( "Creating NotCursor {}", this );
+        this.childEvaluator = childEvaluator;
+        this.uuidCursor = new AllEntriesCursor( store );
+
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    protected String getUnsupportedMessage()
+    {
+        return UNSUPPORTED_MSG;
+    }
+
+
+    public void beforeFirst() throws Exception
+    {
+        checkNotClosed( "beforeFirst()" );
+        uuidCursor.beforeFirst();
+        setAvailable( false );
+    }
+
+
+    public void afterLast() throws Exception
+    {
+        checkNotClosed( "afterLast()" );
+        uuidCursor.afterLast();
+        setAvailable( false );
+    }
+
+
+    public boolean first() throws Exception
+    {
+        beforeFirst();
+
+        return next();
+    }
+
+
+    public boolean last() throws Exception
+    {
+        afterLast();
+
+        return previous();
+    }
+
+
+    public boolean previous() throws Exception
+    {
+        while ( uuidCursor.previous() )
+        {
+            checkNotClosed( "previous()" );
+            IndexEntry<?, String> candidate = uuidCursor.get();
+
+            if ( !childEvaluator.evaluate( candidate ) )
+            {
+                return setAvailable( true );
+            }
+        }
+
+        return setAvailable( false );
+    }
+
+
+    public boolean next() throws Exception
+    {
+        while ( uuidCursor.next() )
+        {
+            checkNotClosed( "next()" );
+            IndexEntry<?, String> candidate = uuidCursor.get();
+
+            if ( !childEvaluator.evaluate( candidate ) )
+            {
+                return setAvailable( true );
+            }
+        }
+
+        return setAvailable( false );
+    }
+
+
+    public IndexEntry<V, String> get() throws Exception
+    {
+        checkNotClosed( "get()" );
+
+        if ( available() )
+        {
+            return ( IndexEntry<V, String> ) uuidCursor.get();
+        }
+
+        throw new InvalidCursorPositionException( I18n.err( I18n.ERR_708 ) );
+    }
+
+
+    public void close() throws Exception
+    {
+        LOG_CURSOR.debug( "Closing NotCursor {}", this );
+        super.close();
+        uuidCursor.close();
+    }
+
+
+    public void close( Exception cause ) throws Exception
+    {
+        LOG_CURSOR.debug( "Closing NotCursor {}", this );
+        super.close( cause );
+        uuidCursor.close( cause );
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( tabs ).append( "NotCursor (" );
+
+        if ( available() )
+        {
+            sb.append( "available)" );
+        }
+        else
+        {
+            sb.append( "absent)" );
+        }
+
+        sb.append( tabs + "  >>" ).append( childEvaluator ).append( '\n' );
+
+        sb.append( uuidCursor.toString( tabs + "    " ) );
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return toString( "" );
+    }
+}

Added: directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/OrCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/OrCursor.java?rev=1389184&view=auto
==============================================================================
--- directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/OrCursor.java (added)
+++ directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/OrCursor.java Mon Sep 24 02:17:13 2012
@@ -0,0 +1,357 @@
+/*
+ *  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.xdbm.search.cursor;
+
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+import org.apache.directory.server.i18n.I18n;
+import org.apache.directory.server.xdbm.AbstractIndexCursor;
+import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.search.Evaluator;
+import org.apache.directory.shared.ldap.model.cursor.Cursor;
+import org.apache.directory.shared.ldap.model.cursor.InvalidCursorPositionException;
+import org.apache.directory.shared.ldap.model.filter.ExprNode;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+
+/**
+ * A Cursor returning candidates satisfying a logical disjunction expression.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class OrCursor<V> extends AbstractIndexCursor<V>
+{
+    /** A dedicated log for cursors */
+    private static final Logger LOG_CURSOR = LoggerFactory.getLogger( "CURSOR" );
+
+    private static final String UNSUPPORTED_MSG = I18n.err( I18n.ERR_722 );
+    private final List<Cursor<IndexEntry<V, String>>> cursors;
+    private final List<Evaluator<? extends ExprNode>> evaluators;
+    private final List<Set<String>> blacklists;
+    private int cursorIndex = -1;
+
+    /** The candidate we have fetched in the next/previous call */
+    private IndexEntry<V, String> prefetched;
+
+
+    // TODO - do same evaluator fail fast optimization that we do in AndCursor
+    public OrCursor( List<Cursor<IndexEntry<V, String>>> cursors,
+        List<Evaluator<? extends ExprNode>> evaluators )
+    {
+        LOG_CURSOR.debug( "Creating OrCursor {}", this );
+
+        if ( cursors.size() <= 1 )
+        {
+            throw new IllegalArgumentException( I18n.err( I18n.ERR_723 ) );
+        }
+
+        this.cursors = cursors;
+        this.evaluators = evaluators;
+        this.blacklists = new ArrayList<Set<String>>();
+
+        for ( int i = 0; i < cursors.size(); i++ )
+        {
+            this.blacklists.add( new HashSet<String>() );
+        }
+
+        this.cursorIndex = 0;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    protected String getUnsupportedMessage()
+    {
+        return UNSUPPORTED_MSG;
+    }
+
+
+    public void beforeFirst() throws Exception
+    {
+        checkNotClosed( "beforeFirst()" );
+        cursorIndex = 0;
+        cursors.get( cursorIndex ).beforeFirst();
+        setAvailable( false );
+        prefetched = null;
+    }
+
+
+    public void afterLast() throws Exception
+    {
+        checkNotClosed( "afterLast()" );
+        cursorIndex = cursors.size() - 1;
+        cursors.get( cursorIndex ).afterLast();
+        setAvailable( false );
+        prefetched = null;
+    }
+
+
+    public boolean first() throws Exception
+    {
+        beforeFirst();
+
+        return setAvailable( next() );
+    }
+
+
+    public boolean last() throws Exception
+    {
+        afterLast();
+
+        return setAvailable( previous() );
+    }
+
+
+    private boolean isBlackListed( String id )
+    {
+        return blacklists.get( cursorIndex ).contains( id );
+    }
+
+
+    /**
+     * The first sub-expression Cursor to advance to an entry adds the entry
+     * to the blacklists of other Cursors that might return that entry.
+     *
+     * @param indexEntry the index entry to blacklist
+     * @throws Exception if there are problems accessing underlying db
+     */
+    private void blackListIfDuplicate( IndexEntry<?, String> indexEntry ) throws Exception
+    {
+        for ( int ii = 0; ii < evaluators.size(); ii++ )
+        {
+            if ( ii == cursorIndex )
+            {
+                continue;
+            }
+
+            if ( evaluators.get( ii ).evaluate( indexEntry ) )
+            {
+                blacklists.get( ii ).add( indexEntry.getId() );
+            }
+        }
+    }
+
+
+    public boolean previous() throws Exception
+    {
+        while ( cursors.get( cursorIndex ).previous() )
+        {
+            checkNotClosed( "previous()" );
+            IndexEntry<V, String> candidate = cursors.get( cursorIndex ).get();
+
+            if ( !isBlackListed( candidate.getId() ) )
+            {
+                blackListIfDuplicate( candidate );
+
+                prefetched = candidate;
+                return setAvailable( true );
+            }
+        }
+
+        while ( cursorIndex > 0 )
+        {
+            checkNotClosed( "previous()" );
+            cursorIndex--;
+            cursors.get( cursorIndex ).afterLast();
+
+            while ( cursors.get( cursorIndex ).previous() )
+            {
+                checkNotClosed( "previous()" );
+                IndexEntry<V, String> candidate = cursors.get( cursorIndex ).get();
+
+                if ( !isBlackListed( candidate.getId() ) )
+                {
+                    blackListIfDuplicate( candidate );
+
+                    prefetched = candidate;
+                    return setAvailable( true );
+                }
+            }
+        }
+
+        prefetched = null;
+
+        return setAvailable( false );
+    }
+
+
+    public boolean next() throws Exception
+    {
+        while ( cursors.get( cursorIndex ).next() )
+        {
+            checkNotClosed( "next()" );
+            IndexEntry<V, String> candidate = cursors.get( cursorIndex ).get();
+
+            if ( !isBlackListed( candidate.getId() ) )
+            {
+                blackListIfDuplicate( candidate );
+
+                prefetched = candidate;
+
+                return setAvailable( true );
+            }
+        }
+
+        while ( cursorIndex < cursors.size() - 1 )
+        {
+            checkNotClosed( "previous()" );
+            cursorIndex++;
+            cursors.get( cursorIndex ).beforeFirst();
+
+            while ( cursors.get( cursorIndex ).next() )
+            {
+                checkNotClosed( "previous()" );
+                IndexEntry<V, String> candidate = cursors.get( cursorIndex ).get();
+
+                if ( !isBlackListed( candidate.getId() ) )
+                {
+                    blackListIfDuplicate( candidate );
+
+                    prefetched = candidate;
+
+                    return setAvailable( true );
+                }
+            }
+        }
+
+        prefetched = null;
+
+        return setAvailable( false );
+    }
+
+
+    public IndexEntry<V, String> get() throws Exception
+    {
+        checkNotClosed( "get()" );
+
+        if ( available() )
+        {
+            return prefetched;
+        }
+
+        throw new InvalidCursorPositionException( I18n.err( I18n.ERR_708 ) );
+    }
+
+
+    public void close() throws Exception
+    {
+        LOG_CURSOR.debug( "Closing OrCursor {}", this );
+        super.close();
+
+        for ( Cursor<?> cursor : cursors )
+        {
+            cursor.close();
+        }
+    }
+
+
+    public void close( Exception cause ) throws Exception
+    {
+        LOG_CURSOR.debug( "Closing OrCursor {}", this );
+        super.close( cause );
+
+        for ( Cursor<?> cursor : cursors )
+        {
+            cursor.close( cause );
+        }
+    }
+
+
+    /**
+     * Dumps the evaluators
+     */
+    private String dumpEvaluators( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        for ( Evaluator<? extends ExprNode> evaluator : evaluators )
+        {
+            sb.append( evaluator.toString( tabs + "  >>" ) );
+        }
+
+        return sb.toString();
+    }
+
+
+    /**
+     * Dumps the cursors
+     */
+    private String dumpCursors( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        for ( Cursor<IndexEntry<V, String>> cursor : cursors )
+        {
+            sb.append( cursor.toString( tabs + "  " ) );
+            sb.append( "\n" );
+        }
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( tabs ).append( "OrCursor (" );
+
+        if ( available() )
+        {
+            sb.append( "available)" );
+        }
+        else
+        {
+            sb.append( "absent)" );
+        }
+
+        sb.append( "#" ).append( cursorIndex ).append( " : \n" );
+
+        if ( ( evaluators != null ) && ( evaluators.size() > 0 ) )
+        {
+            sb.append( dumpEvaluators( tabs ) );
+        }
+
+        if ( ( cursors != null ) && ( cursors.size() > 0 ) )
+        {
+            sb.append( dumpCursors( tabs ) ).append( '\n' );
+        }
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return toString( "" );
+    }
+}
\ No newline at end of file

Added: directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/PresenceCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/PresenceCursor.java?rev=1389184&view=auto
==============================================================================
--- directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/PresenceCursor.java (added)
+++ directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/PresenceCursor.java Mon Sep 24 02:17:13 2012
@@ -0,0 +1,353 @@
+/*
+ *  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.xdbm.search.cursor;
+
+
+import org.apache.directory.server.i18n.I18n;
+import org.apache.directory.server.xdbm.AbstractIndexCursor;
+import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.Store;
+import org.apache.directory.server.xdbm.search.evaluator.PresenceEvaluator;
+import org.apache.directory.shared.ldap.model.cursor.Cursor;
+import org.apache.directory.shared.ldap.model.cursor.InvalidCursorPositionException;
+import org.apache.directory.shared.ldap.model.schema.AttributeType;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+
+/**
+ * A returning candidates satisfying an attribute presence expression.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class PresenceCursor extends AbstractIndexCursor<String>
+{
+    /** A dedicated log for cursors */
+    private static final Logger LOG_CURSOR = LoggerFactory.getLogger( "CURSOR" );
+
+    private static final String UNSUPPORTED_MSG = I18n.err( I18n.ERR_724 );
+    private final Cursor<IndexEntry<String, String>> uuidCursor;
+    private final Cursor<IndexEntry<String, String>> presenceCursor;
+    private final PresenceEvaluator presenceEvaluator;
+
+    /** The prefetched entry, if it's a valid one */
+    private IndexEntry<String, String> prefetched;
+
+
+    public PresenceCursor( Store store, PresenceEvaluator presenceEvaluator ) throws Exception
+    {
+        LOG_CURSOR.debug( "Creating PresenceCursor {}", this );
+        this.presenceEvaluator = presenceEvaluator;
+        AttributeType type = presenceEvaluator.getAttributeType();
+
+        // we don't maintain a presence index for objectClass, and entryCSN
+        // as it doesn't make sense because every entry has such an attribute
+        // instead for those attributes and all un-indexed attributes we use the ndn index
+        if ( store.hasUserIndexOn( type ) )
+        {
+            presenceCursor = store.getPresenceIndex().forwardCursor( type.getOid() );
+            uuidCursor = null;
+        }
+        else
+        {
+            presenceCursor = null;
+            uuidCursor = new AllEntriesCursor( store );
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    protected String getUnsupportedMessage()
+    {
+        return UNSUPPORTED_MSG;
+    }
+
+
+    public boolean available()
+    {
+        if ( presenceCursor != null )
+        {
+            return presenceCursor.available();
+        }
+
+        return super.available();
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void before( IndexEntry<String, String> element ) throws Exception
+    {
+        checkNotClosed( "before()" );
+
+        if ( presenceCursor != null )
+        {
+            presenceCursor.before( element );
+
+            return;
+        }
+
+        super.before( element );
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void after( IndexEntry<String, String> element ) throws Exception
+    {
+        checkNotClosed( "after()" );
+
+        if ( presenceCursor != null )
+        {
+            presenceCursor.after( element );
+
+            return;
+        }
+
+        super.after( element );
+    }
+
+
+    public void beforeFirst() throws Exception
+    {
+        checkNotClosed( "beforeFirst()" );
+
+        if ( presenceCursor != null )
+        {
+            presenceCursor.beforeFirst();
+
+            return;
+        }
+
+        uuidCursor.beforeFirst();
+        setAvailable( false );
+    }
+
+
+    public void afterLast() throws Exception
+    {
+        checkNotClosed( "afterLast()" );
+
+        if ( presenceCursor != null )
+        {
+            presenceCursor.afterLast();
+            return;
+        }
+
+        uuidCursor.afterLast();
+        setAvailable( false );
+    }
+
+
+    public boolean first() throws Exception
+    {
+        checkNotClosed( "first()" );
+        if ( presenceCursor != null )
+        {
+            return presenceCursor.first();
+        }
+
+        beforeFirst();
+        return next();
+    }
+
+
+    public boolean last() throws Exception
+    {
+        checkNotClosed( "last()" );
+
+        if ( presenceCursor != null )
+        {
+            return presenceCursor.last();
+        }
+
+        afterLast();
+
+        return previous();
+    }
+
+
+    public boolean previous() throws Exception
+    {
+        checkNotClosed( "previous()" );
+
+        if ( presenceCursor != null )
+        {
+            return presenceCursor.previous();
+        }
+
+        while ( uuidCursor.previous() )
+        {
+            checkNotClosed( "previous()" );
+            IndexEntry<?, String> candidate = uuidCursor.get();
+
+            if ( presenceEvaluator.evaluate( candidate ) )
+            {
+                return setAvailable( true );
+            }
+        }
+
+        return setAvailable( false );
+    }
+
+
+    public boolean next() throws Exception
+    {
+        checkNotClosed( "next()" );
+
+        if ( presenceCursor != null )
+        {
+            return presenceCursor.next();
+        }
+
+        while ( uuidCursor.next() )
+        {
+            checkNotClosed( "next()" );
+            IndexEntry<String, String> candidate = uuidCursor.get();
+
+            if ( presenceEvaluator.evaluate( candidate ) )
+            {
+                prefetched = candidate;
+
+                return setAvailable( true );
+            }
+        }
+
+        return setAvailable( false );
+    }
+
+
+    public IndexEntry<String, String> get() throws Exception
+    {
+        checkNotClosed( "get()" );
+
+        if ( presenceCursor != null )
+        {
+            if ( presenceCursor.available() )
+            {
+                return presenceCursor.get();
+            }
+
+            throw new InvalidCursorPositionException( I18n.err( I18n.ERR_708 ) );
+        }
+
+        if ( available() )
+        {
+            if ( prefetched == null )
+            {
+                prefetched = uuidCursor.get();
+            }
+
+            /*
+             * The value of NDN indices is the normalized dn and we want the
+             * value to be the value of the attribute in question.  So we will
+             * set that accordingly here.
+             */
+            prefetched.setKey( presenceEvaluator.getAttributeType().getOid() );
+
+            return prefetched;
+        }
+
+        throw new InvalidCursorPositionException( I18n.err( I18n.ERR_708 ) );
+    }
+
+
+    public void close() throws Exception
+    {
+        LOG_CURSOR.debug( "Closing PresenceCursor {}", this );
+        super.close();
+
+        if ( presenceCursor != null )
+        {
+            presenceCursor.close();
+        }
+        else
+        {
+            uuidCursor.close();
+        }
+    }
+
+
+    public void close( Exception cause ) throws Exception
+    {
+        LOG_CURSOR.debug( "Closing PresenceCursor {}", this );
+        super.close( cause );
+
+        if ( presenceCursor != null )
+        {
+            presenceCursor.close( cause );
+        }
+        else
+        {
+            uuidCursor.close( cause );
+        }
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( tabs ).append( "PresenceCursor (" );
+
+        if ( available() )
+        {
+            sb.append( "available)" );
+        }
+        else
+        {
+            sb.append( "absent)" );
+        }
+
+        sb.append( " :\n" );
+
+        sb.append( tabs + "  >>" ).append( presenceEvaluator ).append( '\n' );
+
+        if ( presenceCursor != null )
+        {
+            sb.append( tabs + "  <presence>\n" );
+            sb.append( presenceCursor.toString( tabs + "    " ) );
+        }
+
+        if ( uuidCursor != null )
+        {
+            sb.append( tabs + "  <uuid>\n" );
+            sb.append( uuidCursor.toString( tabs + "  " ) );
+        }
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return toString( "" );
+    }
+}

Added: directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/SubstringCursor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/SubstringCursor.java?rev=1389184&view=auto
==============================================================================
--- directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/SubstringCursor.java (added)
+++ directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/cursor/SubstringCursor.java Mon Sep 24 02:17:13 2012
@@ -0,0 +1,277 @@
+/*
+ *  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.xdbm.search.cursor;
+
+
+import org.apache.directory.server.i18n.I18n;
+import org.apache.directory.server.xdbm.AbstractIndexCursor;
+import org.apache.directory.server.xdbm.Index;
+import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.Store;
+import org.apache.directory.server.xdbm.search.evaluator.SubstringEvaluator;
+import org.apache.directory.shared.ldap.model.cursor.Cursor;
+import org.apache.directory.shared.ldap.model.cursor.InvalidCursorPositionException;
+import org.apache.directory.shared.ldap.model.entry.Entry;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+
+/**
+ * A Cursor traversing candidates matching a Substring assertion expression.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class SubstringCursor extends AbstractIndexCursor<String>
+{
+    /** A dedicated log for cursors */
+    private static final Logger LOG_CURSOR = LoggerFactory.getLogger( "CURSOR" );
+
+    private static final String UNSUPPORTED_MSG = I18n.err( I18n.ERR_725 );
+    private final boolean hasIndex;
+    private final Cursor<IndexEntry<String, String>> wrapped;
+    private final SubstringEvaluator evaluator;
+    private final IndexEntry<String, String> indexEntry = new IndexEntry<String, String>();
+
+
+    @SuppressWarnings("unchecked")
+    public SubstringCursor( Store store, final SubstringEvaluator substringEvaluator )
+        throws Exception
+    {
+        LOG_CURSOR.debug( "Creating SubstringCursor {}", this );
+        evaluator = substringEvaluator;
+        hasIndex = store.hasIndexOn( evaluator.getExpression().getAttributeType() );
+
+        if ( hasIndex )
+        {
+            wrapped = ( ( Index<String, Entry, String> ) store.getIndex( evaluator.getExpression().getAttributeType() ) )
+                .forwardCursor();
+        }
+        else
+        {
+            /*
+             * There is no index on the attribute here.  We have no choice but
+             * to perform a full table scan but need to leverage an index for the
+             * wrapped Cursor.  We know that all entries are listed under
+             * the ndn index and so this will enumerate over all entries.  The
+             * substringEvaluator is used in an assertion to constrain the
+             * result set to only those entries matching the pattern.  The
+             * substringEvaluator handles all the details of normalization and
+             * knows to use it, when it itself detects the lack of an index on
+             * the node's attribute.
+             */
+            wrapped = new AllEntriesCursor( store );
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    protected String getUnsupportedMessage()
+    {
+        return UNSUPPORTED_MSG;
+    }
+
+
+    public void beforeFirst() throws Exception
+    {
+        checkNotClosed( "beforeFirst()" );
+        if ( evaluator.getExpression().getInitial() != null && hasIndex )
+        {
+            IndexEntry<String, String> indexEntry = new IndexEntry<String, String>();
+            indexEntry.setKey( evaluator.getExpression().getInitial() );
+            wrapped.before( indexEntry );
+        }
+        else
+        {
+            wrapped.beforeFirst();
+        }
+
+        clear();
+    }
+
+
+    private void clear()
+    {
+        setAvailable( false );
+        indexEntry.setEntry( null );
+        indexEntry.setId( null );
+        indexEntry.setKey( null );
+    }
+
+
+    public void afterLast() throws Exception
+    {
+        checkNotClosed( "afterLast()" );
+
+        // to keep the cursor always *after* the last matched tuple
+        // This fixes an issue if the last matched tuple is also the last record present in the
+        // index. In this case the wrapped cursor is positioning on the last tuple instead of positioning after that
+        wrapped.afterLast();
+        clear();
+    }
+
+
+    public boolean first() throws Exception
+    {
+        beforeFirst();
+        return next();
+    }
+
+
+    private boolean evaluateCandidate( IndexEntry<String, String> indexEntry ) throws Exception
+    {
+        if ( hasIndex )
+        {
+            String key = indexEntry.getKey();
+            return evaluator.getPattern().matcher( key ).matches();
+        }
+        else
+        {
+            return evaluator.evaluate( indexEntry );
+        }
+    }
+
+
+    public boolean last() throws Exception
+    {
+        afterLast();
+        return previous();
+    }
+
+
+    public boolean previous() throws Exception
+    {
+        while ( wrapped.previous() )
+        {
+            checkNotClosed( "previous()" );
+            IndexEntry<String, String> entry = wrapped.get();
+
+            if ( evaluateCandidate( entry ) )
+            {
+                setAvailable( true );
+                this.indexEntry.setId( entry.getId() );
+                this.indexEntry.setKey( entry.getKey() );
+                this.indexEntry.setEntry( entry.getEntry() );
+                return true;
+            }
+        }
+
+        clear();
+        return false;
+    }
+
+
+    public boolean next() throws Exception
+    {
+        while ( wrapped.next() )
+        {
+            checkNotClosed( "next()" );
+            IndexEntry<String, String> entry = wrapped.get();
+
+            if ( evaluateCandidate( entry ) )
+            {
+                setAvailable( true );
+                this.indexEntry.setId( entry.getId() );
+                this.indexEntry.setKey( entry.getKey() );
+                this.indexEntry.setEntry( entry.getEntry() );
+
+                return true;
+            }
+        }
+
+        clear();
+        return false;
+    }
+
+
+    public IndexEntry<String, String> get() throws Exception
+    {
+        checkNotClosed( "get()" );
+
+        if ( available() )
+        {
+            return indexEntry;
+        }
+
+        throw new InvalidCursorPositionException( I18n.err( I18n.ERR_708 ) );
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void close() throws Exception
+    {
+        LOG_CURSOR.debug( "Closing SubstringCursor {}", this );
+        super.close();
+        wrapped.close();
+        clear();
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public void close( Exception cause ) throws Exception
+    {
+        LOG_CURSOR.debug( "Closing SubstringCursor {}", this );
+        super.close( cause );
+        wrapped.close( cause );
+        clear();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( tabs ).append( "SubstringCursor (" );
+
+        if ( available() )
+        {
+            sb.append( "available)" );
+        }
+        else
+        {
+            sb.append( "absent)" );
+        }
+
+        sb.append( "#index<" ).append( hasIndex ).append( "> :\n" );
+
+        sb.append( tabs + "  >>" ).append( evaluator ).append( '\n' );
+
+        sb.append( wrapped.toString( tabs + "    " ) );
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return toString( "" );
+    }
+}

Added: directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/AndEvaluator.java
URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/AndEvaluator.java?rev=1389184&view=auto
==============================================================================
--- directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/AndEvaluator.java (added)
+++ directory/apacheds/trunk/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/evaluator/AndEvaluator.java Mon Sep 24 02:17:13 2012
@@ -0,0 +1,169 @@
+/*
+ *  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.xdbm.search.evaluator;
+
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+
+import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.search.Evaluator;
+import org.apache.directory.server.xdbm.search.impl.ScanCountComparator;
+import org.apache.directory.shared.ldap.model.entry.Entry;
+import org.apache.directory.shared.ldap.model.filter.AndNode;
+import org.apache.directory.shared.ldap.model.filter.ExprNode;
+
+
+/**
+ * An Evaluator for logical conjunction (AND) expressions.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class AndEvaluator implements Evaluator<AndNode>
+{
+    /** The list of evaluators associated with each of the children */
+    private final List<Evaluator<? extends ExprNode>> evaluators;
+
+    /** The AndNode */
+    private final AndNode node;
+
+
+    /**
+     * Creates an instance of AndEvaluator
+     * @param node The And Node
+     * @param evaluators The list of evaluators for all the contaned nodes
+     */
+    public AndEvaluator( AndNode node, List<Evaluator<? extends ExprNode>> evaluators )
+    {
+        this.node = node;
+        this.evaluators = optimize( evaluators );
+    }
+
+
+    /**
+     * Takes a set of Evaluators and copies then sorts them in a new list with
+     * increasing scan counts on their expression nodes.  This is done to have
+     * the Evaluators with the least scan count which have the highest
+     * probability of rejecting a candidate first.  That will increase the
+     * chance of shorting the checks on evaluators early so extra lookups and
+     * comparisons are avoided.
+     *
+     * @param unoptimized the unoptimized list of Evaluators
+     * @return optimized Evaluator list with increasing scan count ordering
+     */
+    private List<Evaluator<? extends ExprNode>> optimize(
+        List<Evaluator<? extends ExprNode>> unoptimized )
+    {
+        List<Evaluator<? extends ExprNode>> optimized = new ArrayList<Evaluator<? extends ExprNode>>(
+            unoptimized.size() );
+        optimized.addAll( unoptimized );
+
+        Collections.sort( optimized, new ScanCountComparator() );
+
+        return optimized;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean evaluate( Entry entry ) throws Exception
+    {
+        for ( Evaluator<?> evaluator : evaluators )
+        {
+            if ( !evaluator.evaluate( entry ) )
+            {
+                return false;
+            }
+        }
+
+        return true;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public boolean evaluate( IndexEntry<?, String> indexEntry ) throws Exception
+    {
+        for ( Evaluator<?> evaluator : evaluators )
+        {
+            if ( !evaluator.evaluate( indexEntry ) )
+            {
+                return false;
+            }
+        }
+
+        return true;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public AndNode getExpression()
+    {
+        return node;
+    }
+
+
+    /**
+     * Dumps the evaluators
+     */
+    private String dumpEvaluators( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        for ( Evaluator<? extends ExprNode> evaluator : evaluators )
+        {
+            sb.append( evaluator.toString( tabs + "  " ) );
+        }
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString( String tabs )
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( tabs ).append( "AndEvaluator : " ).append( node ).append( "\n" );
+
+        if ( ( evaluators != null ) && ( evaluators.size() > 0 ) )
+        {
+            sb.append( dumpEvaluators( tabs + "  " ) ).append( "\n" );
+        }
+
+        return sb.toString();
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        return toString( "" );
+    }
+}



Mime
View raw message