directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From elecha...@apache.org
Subject svn commit: r1381944 - in /directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server: core/partition/impl/btree/ xdbm/ xdbm/search/ xdbm/search/impl/
Date Fri, 07 Sep 2012 09:25:05 GMT
Author: elecharny
Date: Fri Sep  7 09:25:05 2012
New Revision: 1381944

URL: http://svn.apache.org/viewvc?rev=1381944&view=rev
Log:
Decoupled the backend search result from the front end processing : we now return a set of UUID candidates which is fully computed in the SearchEngine, and the frontEnd is looping on the UUID, fetching the entries from the MasterTable. This allow the locks to be released fast.

Added:
    directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/PartitionSearchResult.java
Modified:
    directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/AbstractBTreePartition.java
    directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/EntryCursorAdaptor.java
    directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/IndexCursorAdaptor.java
    directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/ForwardIndexEntry.java
    directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/CursorBuilder.java
    directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/DefaultSearchEngine.java

Modified: directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/AbstractBTreePartition.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/AbstractBTreePartition.java?rev=1381944&r1=1381943&r2=1381944&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/AbstractBTreePartition.java (original)
+++ directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/AbstractBTreePartition.java Fri Sep  7 09:25:05 2012
@@ -57,11 +57,12 @@ import org.apache.directory.server.xdbm.
 import org.apache.directory.server.xdbm.ParentIdAndRdn;
 import org.apache.directory.server.xdbm.Store;
 import org.apache.directory.server.xdbm.search.Optimizer;
+import org.apache.directory.server.xdbm.search.PartitionSearchResult;
 import org.apache.directory.server.xdbm.search.SearchEngine;
 import org.apache.directory.server.xdbm.search.cursor.ChildrenCursor;
+import org.apache.directory.server.xdbm.search.evaluator.PassThroughEvaluator;
 import org.apache.directory.shared.ldap.model.constants.SchemaConstants;
 import org.apache.directory.shared.ldap.model.cursor.Cursor;
-import org.apache.directory.shared.ldap.model.cursor.SetCursor;
 import org.apache.directory.shared.ldap.model.entry.Attribute;
 import org.apache.directory.shared.ldap.model.entry.Entry;
 import org.apache.directory.shared.ldap.model.entry.Modification;
@@ -917,16 +918,43 @@ public abstract class AbstractBTreeParti
      */
     public EntryFilteringCursor list( ListOperationContext listContext ) throws LdapException
     {
-        return new BaseEntryFilteringCursor(
-            new EntryCursorAdaptor( this,
-                list( getEntryId( listContext.getDn() ) ) ), listContext );
+        return list( getEntryId( listContext.getDn() ), listContext );
     }
 
 
     /**
      * {@inheritDoc}
      */
-    public final Cursor<IndexEntry<String, String>> list( String id ) throws LdapException
+    public Cursor<IndexEntry<String, String>> list( String id ) throws LdapException
+    {
+        try
+        {
+            Cursor<IndexEntry<ParentIdAndRdn, String>> cursor = rdnIdx.forwardCursor();
+
+            IndexEntry<ParentIdAndRdn, String> startingPos = new ForwardIndexEntry<ParentIdAndRdn, String>();
+            startingPos.setKey( new ParentIdAndRdn( id, ( Rdn[] ) null ) );
+            cursor.before( startingPos );
+
+            dumpRdnIdx();
+
+            PartitionSearchResult searchResult = new PartitionSearchResult();
+            Set<IndexEntry<String, String>> resultSet = new HashSet<IndexEntry<String, String>>();
+
+            Cursor<IndexEntry<String, String>> childrenCursor = new ChildrenCursor( this, id, cursor );
+
+            return childrenCursor;
+        }
+        catch ( Exception e )
+        {
+            throw new LdapOperationErrorException( e.getMessage(), e );
+        }
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    public final EntryFilteringCursor list( String id, ListOperationContext listContext ) throws LdapException
     {
         try
         {
@@ -940,7 +968,22 @@ public abstract class AbstractBTreeParti
 
             dumpRdnIdx();
 
-            return new ChildrenCursor( this, id, cursor );
+            PartitionSearchResult searchResult = new PartitionSearchResult();
+            Set<IndexEntry<String, String>> resultSet = new HashSet<IndexEntry<String, String>>();
+
+            Cursor<IndexEntry<String, String>> childrenCursor = new ChildrenCursor( this, id, cursor );
+
+            while ( childrenCursor.next() )
+            {
+                IndexEntry<String, String> element = childrenCursor.get();
+                resultSet.add( element );
+            }
+
+            searchResult.setResultSet( resultSet );
+            searchResult.setEvaluator( new PassThroughEvaluator( this ) );
+
+            return new BaseEntryFilteringCursor( new EntryCursorAdaptor( this, searchResult ),
+                listContext );
         }
         catch ( Exception e )
         {
@@ -964,11 +1007,10 @@ public abstract class AbstractBTreeParti
             AliasDerefMode derefMode = searchContext.getAliasDerefMode();
             ExprNode filter = searchContext.getFilter();
 
-            Set<IndexEntry<String, String>> result = searchEngine.buildResultSet( dn, derefMode, filter, scope );
-
-            Cursor underlying = new SetCursor<IndexEntry<String, String>>( result );
+            PartitionSearchResult searchResult = searchEngine.computeResult( dn, derefMode, filter, scope );
 
-            return new BaseEntryFilteringCursor( new EntryCursorAdaptor( this, underlying ), searchContext );
+            return new BaseEntryFilteringCursor( new EntryCursorAdaptor( this, searchResult ),
+                searchContext );
         }
         catch ( LdapException le )
         {

Modified: directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/EntryCursorAdaptor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/EntryCursorAdaptor.java?rev=1381944&r1=1381943&r2=1381944&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/EntryCursorAdaptor.java (original)
+++ directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/EntryCursorAdaptor.java Fri Sep  7 09:25:05 2012
@@ -21,10 +21,13 @@ package org.apache.directory.server.core
 
 
 import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.search.Evaluator;
+import org.apache.directory.server.xdbm.search.PartitionSearchResult;
 import org.apache.directory.shared.ldap.model.cursor.AbstractCursor;
 import org.apache.directory.shared.ldap.model.cursor.ClosureMonitor;
 import org.apache.directory.shared.ldap.model.cursor.Cursor;
 import org.apache.directory.shared.ldap.model.entry.Entry;
+import org.apache.directory.shared.ldap.model.filter.ExprNode;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
@@ -41,13 +44,15 @@ public class EntryCursorAdaptor extends 
 
     private final AbstractBTreePartition db;
     private final Cursor<IndexEntry<String, String>> indexCursor;
+    private final Evaluator<? extends ExprNode> evaluator;
 
 
-    public EntryCursorAdaptor( AbstractBTreePartition db, Cursor<IndexEntry<String, String>> indexCursor )
+    public EntryCursorAdaptor( AbstractBTreePartition db, PartitionSearchResult searchResult )
     {
         LOG_CURSOR.debug( "Creating EntryCursorAdaptor {}", this );
         this.db = db;
-        this.indexCursor = indexCursor;
+        indexCursor = searchResult.getResultSet();
+        evaluator = searchResult.getEvaluator();
     }
 
 
@@ -138,13 +143,12 @@ public class EntryCursorAdaptor extends 
     {
         IndexEntry<String, String> indexEntry = indexCursor.get();
 
-        if ( indexEntry.getEntry() == null )
+        if ( evaluator.evaluate( indexEntry ) )
         {
-            Entry entry = db.lookup( indexEntry.getId() );
-            indexEntry.setEntry( entry );
+            return indexEntry.getEntry();
         }
 
-        return indexEntry.getEntry();
+        return null;
     }
 
 

Modified: directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/IndexCursorAdaptor.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/IndexCursorAdaptor.java?rev=1381944&r1=1381943&r2=1381944&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/IndexCursorAdaptor.java (original)
+++ directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/core/partition/impl/btree/IndexCursorAdaptor.java Fri Sep  7 09:25:05 2012
@@ -63,7 +63,6 @@ public class IndexCursorAdaptor<K> exten
     @SuppressWarnings("unchecked")
     public IndexCursorAdaptor( Cursor<Tuple> wrappedCursor, boolean forwardIndex )
     {
-        LOG_CURSOR.debug( "Creating IndexCursorAdaptor {}", this );
         this.wrappedCursor = wrappedCursor;
 
         if ( forwardIndex )
@@ -76,6 +75,8 @@ public class IndexCursorAdaptor<K> exten
             forwardEntry = null;
             reverseEntry = new ReverseIndexEntry<K, String>();
         }
+
+        LOG_CURSOR.debug( "Creating IndexCursorAdaptor {}", this );
     }
 
 

Modified: directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/ForwardIndexEntry.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/ForwardIndexEntry.java?rev=1381944&r1=1381943&r2=1381944&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/ForwardIndexEntry.java (original)
+++ directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/ForwardIndexEntry.java Fri Sep  7 09:25:05 2012
@@ -130,6 +130,45 @@ public class ForwardIndexEntry<K, ID> ex
     }
 
 
+    public int hashCode()
+    {
+        if ( getId() == null )
+        {
+            return 0;
+        }
+
+        return getId().hashCode();
+    }
+
+
+    public boolean equals( IndexEntry<K, ID> that )
+    {
+        if ( that == this )
+        {
+            return true;
+        }
+
+        if ( !( that instanceof ForwardIndexEntry ) )
+        {
+            return false;
+        }
+
+        ForwardIndexEntry<K, ID> thatIndexEntry = ( ForwardIndexEntry<K, ID> ) that;
+
+        if ( thatIndexEntry.getId() == null )
+        {
+            return getId() == null;
+        }
+
+        if ( thatIndexEntry.getId().equals( getId() ) )
+        {
+            return true;
+        }
+
+        return false;
+    }
+
+
     /**
      * {@inheritDoc}
      */

Added: directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/PartitionSearchResult.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/PartitionSearchResult.java?rev=1381944&view=auto
==============================================================================
--- directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/PartitionSearchResult.java (added)
+++ directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/PartitionSearchResult.java Fri Sep  7 09:25:05 2012
@@ -0,0 +1,138 @@
+/*
+ *   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;
+
+
+import java.util.Set;
+
+import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.shared.ldap.model.cursor.SetCursor;
+import org.apache.directory.shared.ldap.model.filter.ExprNode;
+
+
+/**
+ * A class containing the result of a search :
+ * <ul>
+ * <li>A set of cadidate UUIDs</li>
+ * <li>A hierarchy of evaualtors to use to validate the candidates</li>
+ * </ul>
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class PartitionSearchResult
+{
+    /** The set of candidate UUIDs selected by the search */
+    private SetCursor<IndexEntry<String, String>> resultSet;
+
+    /** The evaluator to validate the candidates */
+    private Evaluator<? extends ExprNode> evaluator;
+
+
+    /**
+     * Create a PartitionSearchResult instance
+     */
+    public PartitionSearchResult()
+    {
+    }
+
+
+    /**
+     * @return the resultSet
+     */
+    public SetCursor<IndexEntry<String, String>> getResultSet()
+    {
+        return resultSet;
+    }
+
+
+    /**
+     * @param resultSet the resultSet to set
+     */
+    public void setResultSet( Set<IndexEntry<String, String>> set )
+    {
+        resultSet = new SetCursor<IndexEntry<String, String>>( set );
+    }
+
+
+    /**
+     * @return the evaluator
+     */
+    public Evaluator<? extends ExprNode> getEvaluator()
+    {
+        return evaluator;
+    }
+
+
+    /**
+     * @param evaluator the evaluator to set
+     */
+    public void setEvaluator( Evaluator<? extends ExprNode> evaluator )
+    {
+        this.evaluator = evaluator;
+    }
+
+
+    /**
+     * @see Object#toString()
+     */
+    public String toString()
+    {
+        StringBuilder sb = new StringBuilder();
+
+        sb.append( "Search result : \n" );
+        sb.append( evaluator );
+
+        if ( resultSet == null )
+        {
+            sb.append( "No UUID found" );
+        }
+        else
+        {
+            sb.append( '{' );
+            boolean isFirst = true;
+
+            try
+            {
+                while ( resultSet.next() )
+                {
+                    if ( isFirst )
+                    {
+                        isFirst = false;
+                    }
+                    else
+                    {
+                        sb.append( ", " );
+                    }
+
+                    sb.append( resultSet.get().getId() );
+                }
+
+                resultSet.beforeFirst();
+            }
+            catch ( Exception e )
+            {
+                // Nothing we can do...
+            }
+
+            sb.append( '}' );
+        }
+
+        return sb.toString();
+    }
+}

Modified: directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/CursorBuilder.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/CursorBuilder.java?rev=1381944&r1=1381943&r2=1381944&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/CursorBuilder.java (original)
+++ directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/CursorBuilder.java Fri Sep  7 09:25:05 2012
@@ -20,41 +20,42 @@
 package org.apache.directory.server.xdbm.search.impl;
 
 
-import java.util.ArrayList;
 import java.util.List;
+import java.util.Set;
+import java.util.regex.Pattern;
 
+import org.apache.directory.server.core.api.partition.Partition;
 import org.apache.directory.server.i18n.I18n;
-import org.apache.directory.server.xdbm.EmptyIndexCursor;
+import org.apache.directory.server.xdbm.ForwardIndexEntry;
+import org.apache.directory.server.xdbm.Index;
 import org.apache.directory.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.ParentIdAndRdn;
+import org.apache.directory.server.xdbm.SingletonIndexCursor;
 import org.apache.directory.server.xdbm.Store;
-import org.apache.directory.server.xdbm.search.Evaluator;
-import org.apache.directory.server.xdbm.search.cursor.AndCursor;
 import org.apache.directory.server.xdbm.search.cursor.ApproximateCursor;
-import org.apache.directory.server.xdbm.search.cursor.EqualityCursor;
-import org.apache.directory.server.xdbm.search.cursor.GreaterEqCursor;
-import org.apache.directory.server.xdbm.search.cursor.LessEqCursor;
-import org.apache.directory.server.xdbm.search.cursor.NotCursor;
-import org.apache.directory.server.xdbm.search.cursor.OneLevelScopeCursor;
-import org.apache.directory.server.xdbm.search.cursor.OrCursor;
-import org.apache.directory.server.xdbm.search.cursor.PresenceCursor;
-import org.apache.directory.server.xdbm.search.cursor.SubstringCursor;
-import org.apache.directory.server.xdbm.search.cursor.SubtreeScopeCursor;
+import org.apache.directory.server.xdbm.search.cursor.ChildrenCursor;
+import org.apache.directory.server.xdbm.search.cursor.DescendantCursor;
 import org.apache.directory.server.xdbm.search.evaluator.ApproximateEvaluator;
-import org.apache.directory.server.xdbm.search.evaluator.EqualityEvaluator;
-import org.apache.directory.server.xdbm.search.evaluator.GreaterEqEvaluator;
-import org.apache.directory.server.xdbm.search.evaluator.LessEqEvaluator;
-import org.apache.directory.server.xdbm.search.evaluator.OneLevelScopeEvaluator;
-import org.apache.directory.server.xdbm.search.evaluator.PresenceEvaluator;
-import org.apache.directory.server.xdbm.search.evaluator.SubstringEvaluator;
-import org.apache.directory.server.xdbm.search.evaluator.SubtreeScopeEvaluator;
 import org.apache.directory.shared.ldap.model.cursor.Cursor;
 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.filter.AndNode;
+import org.apache.directory.shared.ldap.model.filter.ApproximateNode;
+import org.apache.directory.shared.ldap.model.filter.EqualityNode;
 import org.apache.directory.shared.ldap.model.filter.ExprNode;
+import org.apache.directory.shared.ldap.model.filter.GreaterEqNode;
+import org.apache.directory.shared.ldap.model.filter.LessEqNode;
 import org.apache.directory.shared.ldap.model.filter.NotNode;
 import org.apache.directory.shared.ldap.model.filter.OrNode;
+import org.apache.directory.shared.ldap.model.filter.PresenceNode;
 import org.apache.directory.shared.ldap.model.filter.ScopeNode;
+import org.apache.directory.shared.ldap.model.filter.SubstringNode;
 import org.apache.directory.shared.ldap.model.message.SearchScope;
+import org.apache.directory.shared.ldap.model.name.Rdn;
+import org.apache.directory.shared.ldap.model.schema.AttributeType;
+import org.apache.directory.shared.ldap.model.schema.MatchingRule;
+import org.apache.directory.shared.ldap.model.schema.Normalizer;
+import org.apache.directory.shared.ldap.model.schema.normalizers.NoOpNormalizer;
 import org.apache.directory.shared.util.exception.NotImplementedException;
 
 
@@ -85,13 +86,13 @@ public class CursorBuilder
     }
 
 
-    public <T> Cursor<IndexEntry<?, String>> build( ExprNode node ) throws Exception
+    public <T> long build( ExprNode node, Set<String> uuidSet ) throws Exception
     {
         Object count = node.get( "count" );
 
         if ( ( count != null ) && ( ( Long ) count ) == 0L )
         {
-            return ( Cursor ) new EmptyIndexCursor<T>();
+            return 0;
         }
 
         switch ( node.getAssertionType() )
@@ -99,62 +100,44 @@ public class CursorBuilder
         /* ---------- LEAF NODE HANDLING ---------- */
 
             case APPROXIMATE:
-                return ( Cursor ) new ApproximateCursor<T>( db,
-                    ( ApproximateEvaluator<T> ) evaluatorBuilder
-                        .build( node ) );
+                return computeApproximate( ( ApproximateNode<T> ) node, uuidSet );
 
             case EQUALITY:
-                return ( Cursor ) new EqualityCursor<T>( db,
-                    ( EqualityEvaluator<T> ) evaluatorBuilder
-                        .build( node ) );
+                return computeEquality( ( EqualityNode<T> ) node, uuidSet );
 
             case GREATEREQ:
-                return ( Cursor ) new GreaterEqCursor<T>( db,
-                    ( GreaterEqEvaluator<T> ) evaluatorBuilder
-                        .build( node ) );
+                return computeGreaterEq( ( GreaterEqNode<T> ) node, uuidSet );
 
             case LESSEQ:
-                return ( Cursor ) new LessEqCursor<T>( db,
-                    ( LessEqEvaluator<T> ) evaluatorBuilder
-                        .build( node ) );
+                return computeLessEq( ( LessEqNode<T> ) node, uuidSet );
 
             case PRESENCE:
-                return ( Cursor ) new PresenceCursor( db,
-                    ( PresenceEvaluator ) evaluatorBuilder
-                        .build( node ) );
+                return computePresence( ( PresenceNode ) node, uuidSet );
 
             case SCOPE:
-                if ( ( ( ScopeNode ) node ).getScope() == SearchScope.ONELEVEL )
+                if ( ( ( ScopeNode<String> ) node ).getScope() == SearchScope.ONELEVEL )
                 {
-                    return ( Cursor ) new OneLevelScopeCursor(
-                        db,
-                        ( OneLevelScopeEvaluator<Entry> ) evaluatorBuilder
-                            .build( node ) );
+                    return computeOneLevelScope( ( ScopeNode<String> ) node, uuidSet );
                 }
                 else
                 {
-                    return ( Cursor ) new SubtreeScopeCursor(
-                        db,
-                        ( SubtreeScopeEvaluator ) evaluatorBuilder
-                            .build( node ) );
+                    return computeSubLevelScope( ( ScopeNode<String> ) node, uuidSet );
                 }
 
             case SUBSTRING:
-                return ( Cursor ) new SubstringCursor( db,
-                    ( SubstringEvaluator ) evaluatorBuilder
-                        .build( node ) );
+                return computeSubstring( ( SubstringNode ) node, uuidSet );
 
                 /* ---------- LOGICAL OPERATORS ---------- */
 
             case AND:
-                return buildAndCursor( ( AndNode ) node );
+                return computeAnd( ( AndNode ) node, uuidSet );
 
             case NOT:
-                return ( Cursor ) new NotCursor<String>( db, evaluatorBuilder.build( ( ( NotNode ) node )
-                    .getFirstChild() ) );
+                // Always return infinite, except if the resulting eva 
+                return computeNot( ( NotNode ) node, uuidSet );
 
             case OR:
-                return buildOrCursor( ( OrNode ) node );
+                return computeOr( ( OrNode ) node, uuidSet );
 
                 /* ----------  NOT IMPLEMENTED  ---------- */
 
@@ -169,19 +152,427 @@ public class CursorBuilder
 
 
     /**
+     * Computes the set of candidates for an Approximate filter. We will feed the set only if
+     * we have an index for the AT.
+     */
+
+    private <T> long computeApproximate( ApproximateNode<T> node, Set<String> uuidSet )
+        throws Exception
+    {
+        ApproximateCursor<T> cursor = new ApproximateCursor<T>( db,
+            ( ApproximateEvaluator<T> ) evaluatorBuilder
+                .build( node ) );
+
+        int nbResults = 0;
+
+        while ( cursor.next() )
+        {
+            IndexEntry<T, String> indexEntry = cursor.get();
+
+            String uuid = indexEntry.getId();
+
+            if ( !uuidSet.contains( uuid ) )
+            {
+                uuidSet.add( uuid );
+                nbResults++;
+            }
+        }
+
+        cursor.close();
+
+        return nbResults;
+    }
+
+
+    /**
+     * Computes the set of candidates for an Equality filter. We will feed the set only if
+     * we have an index for the AT.
+     */
+    private <T> long computeEquality( EqualityNode<T> node, Set<String> uuidSet )
+        throws Exception
+    {
+        AttributeType attributeType = node.getAttributeType();
+        Value<T> value = node.getValue();
+        int nbResults = 0;
+
+        // Fetch all the UUIDs if we have an index
+        if ( db.hasIndexOn( attributeType ) )
+        {
+            // Get the cursor using the index
+            Index<T, Entry, String> userIndex = ( Index<T, Entry, String> ) db.getIndex( attributeType );
+            Cursor<IndexEntry<T, String>> userIdxCursor = userIndex.forwardCursor( value.getValue() );
+
+            // And loop on it
+            while ( userIdxCursor.next() )
+            {
+                IndexEntry<T, String> indexEntry = userIdxCursor.get();
+
+                String uuid = indexEntry.getId();
+
+                if ( !uuidSet.contains( uuid ) )
+                {
+                    // The UUID is not present in the Set, we add it
+                    uuidSet.add( uuid );
+                    nbResults++;
+                }
+            }
+
+            userIdxCursor.close();
+        }
+        else
+        {
+            // No index, we will have to do a full scan
+            return Long.MAX_VALUE;
+        }
+
+        return nbResults;
+    }
+
+
+    /**
+     * Computes the set of candidates for an GreateEq filter. We will feed the set only if
+     * we have an index for the AT.
+     */
+    private <T> long computeGreaterEq( GreaterEqNode<T> node, Set<String> uuidSet )
+        throws Exception
+    {
+        AttributeType attributeType = node.getAttributeType();
+        Value<T> value = node.getValue();
+        int nbResults = 0;
+
+        // Fetch all the UUIDs if we have an index
+        if ( db.hasIndexOn( attributeType ) )
+        {
+            // Get the cursor using the index
+            Index<T, Entry, String> userIndex = ( Index<T, Entry, String> ) db.getIndex( attributeType );
+            Cursor<IndexEntry<T, String>> userIdxCursor = userIndex.forwardCursor();
+
+            // Position the index on the element we should start from
+            IndexEntry<T, String> indexEntry = new ForwardIndexEntry<T, String>();
+            indexEntry.setKey( value.getValue() );
+
+            userIdxCursor.before( indexEntry );
+
+            // And loop on it
+            while ( userIdxCursor.next() )
+            {
+                indexEntry = userIdxCursor.get();
+
+                String uuid = indexEntry.getId();
+
+                if ( !uuidSet.contains( uuid ) )
+                {
+                    // The UUID is not present in the Set, we add it
+                    uuidSet.add( uuid );
+                    nbResults++;
+                }
+            }
+
+            userIdxCursor.close();
+        }
+        else
+        {
+            // No index, we will have to do a full scan
+            return Long.MAX_VALUE;
+        }
+
+        return nbResults;
+    }
+
+
+    /**
+     * Computes the set of candidates for an LessEq filter. We will feed the set only if
+     * we have an index for the AT.
+     */
+    private <T> long computeLessEq( LessEqNode<T> node, Set<String> uuidSet )
+        throws Exception
+    {
+        AttributeType attributeType = node.getAttributeType();
+        Value<T> value = node.getValue();
+        int nbResults = 0;
+
+        // Fetch all the UUIDs if we have an index
+        if ( db.hasIndexOn( attributeType ) )
+        {
+            // Get the cursor using the index
+            Index<T, Entry, String> userIndex = ( Index<T, Entry, String> ) db.getIndex( attributeType );
+            Cursor<IndexEntry<T, String>> userIdxCursor = userIndex.forwardCursor();
+
+            // Position the index on the element we should start from
+            IndexEntry<T, String> indexEntry = new ForwardIndexEntry<T, String>();
+            indexEntry.setKey( value.getValue() );
+
+            userIdxCursor.after( indexEntry );
+
+            // And loop on it
+            while ( userIdxCursor.previous() )
+            {
+                indexEntry = userIdxCursor.get();
+
+                String uuid = indexEntry.getId();
+
+                if ( !uuidSet.contains( uuid ) )
+                {
+                    // The UUID is not present in the Set, we add it
+                    uuidSet.add( uuid );
+                    nbResults++;
+                }
+            }
+
+            userIdxCursor.close();
+        }
+        else
+        {
+            // No index, we will have to do a full scan
+            return Long.MAX_VALUE;
+        }
+
+        return nbResults;
+    }
+
+
+    /**
+     * Computes the set of candidates for a Presence filter. We will feed the set only if
+     * we have an index for the AT.
+     */
+    private <T> long computePresence( PresenceNode node, Set<String> uuidSet )
+        throws Exception
+    {
+        AttributeType attributeType = node.getAttributeType();
+        int nbResults = 0;
+
+        // Fetch all the UUIDs if we have an index
+        if ( db.hasIndexOn( attributeType ) )
+        {
+            // Get the cursor using the index
+            Cursor<IndexEntry<String, String>> presenceCursor = db.getPresenceIndex().forwardCursor(
+                attributeType.getOid() );
+
+            // Position the index on the element we should start from
+            IndexEntry<String, String> indexEntry = new ForwardIndexEntry<String, String>();
+
+            // And loop on it
+            while ( presenceCursor.next() )
+            {
+                indexEntry = presenceCursor.get();
+
+                String uuid = indexEntry.getId();
+
+                if ( !uuidSet.contains( uuid ) )
+                {
+                    // The UUID is not present in the Set, we add it
+                    uuidSet.add( uuid );
+                    nbResults++;
+                }
+            }
+
+            presenceCursor.close();
+        }
+        else
+        {
+            // No index, we will have to do a full scan
+            return Long.MAX_VALUE;
+        }
+
+        return nbResults;
+    }
+
+
+    /**
+     * Computes the set of candidates for a OneLevelScope filter. We will feed the set only if
+     * we have an index for the AT.
+     */
+    private long computeOneLevelScope( ScopeNode<String> node, Set<String> uuidSet )
+        throws Exception
+    {
+        int nbResults = 0;
+
+        // We use the RdnIndex to get all the entries from a starting point
+        // and below up to the number of children
+        Cursor<IndexEntry<ParentIdAndRdn, String>> rdnCursor = db.getRdnIndex().forwardCursor();
+
+        IndexEntry<ParentIdAndRdn, String> startingPos = new ForwardIndexEntry<ParentIdAndRdn, String>();
+        startingPos.setKey( new ParentIdAndRdn( node.getBaseId(), ( Rdn[] ) null ) );
+        rdnCursor.before( startingPos );
+
+        Cursor<IndexEntry<String, String>> scopeCursor = new ChildrenCursor( db, node.getBaseId(), rdnCursor );
+
+        // Fetch all the UUIDs if we have an index
+        // And loop on it
+        while ( scopeCursor.next() )
+        {
+            IndexEntry<String, String> indexEntry = scopeCursor.get();
+
+            String uuid = indexEntry.getId();
+
+            if ( !uuidSet.contains( uuid ) )
+            {
+                // The UUID is not present in the Set, we add it
+                uuidSet.add( uuid );
+                nbResults++;
+            }
+        }
+
+        scopeCursor.close();
+
+        return nbResults;
+    }
+
+
+    /**
+     * Computes the set of candidates for a SubLevelScope filter. We will feed the set only if
+     * we have an index for the AT.
+     */
+    private long computeSubLevelScope( ScopeNode<String> node, Set<String> uuidSet )
+        throws Exception
+    {
+        // If we are searching from the partition DN, better get out.
+        String contextEntryId = db.getEntryId( ( ( Partition ) db ).getSuffixDn() );
+
+        if ( node.getBaseId() == contextEntryId )
+        {
+            return Long.MAX_VALUE;
+        }
+
+        int nbResults = 0;
+
+        // We use the RdnIndex to get all the entries from a starting point
+        // and below up to the number of descendant
+        String baseId = node.getBaseId();
+        ParentIdAndRdn parentIdAndRdn = db.getRdnIndex().reverseLookup( baseId );
+        IndexEntry<ParentIdAndRdn, String> startingPos = new ForwardIndexEntry<ParentIdAndRdn, String>();
+
+        startingPos.setKey( parentIdAndRdn );
+        startingPos.setId( baseId );
+
+        Cursor<IndexEntry<ParentIdAndRdn, String>> rdnCursor = new SingletonIndexCursor<ParentIdAndRdn>(
+            startingPos );
+        String parentId = parentIdAndRdn.getParentId();
+
+        Cursor<IndexEntry<String, String>> scopeCursor = new DescendantCursor( db, baseId, parentId, rdnCursor );
+
+        // Fetch all the UUIDs if we have an index
+        // And loop on it
+        while ( scopeCursor.next() )
+        {
+            IndexEntry<String, String> indexEntry = scopeCursor.get();
+
+            String uuid = indexEntry.getId();
+
+            if ( !uuidSet.contains( uuid ) )
+            {
+                // The UUID is not present in the Set, we add it
+                uuidSet.add( uuid );
+                nbResults++;
+            }
+        }
+
+        scopeCursor.close();
+
+        return nbResults;
+    }
+
+
+    /**
+     * Computes the set of candidates for an Substring filter. We will feed the set only if
+     * we have an index for the AT.
+     */
+    private long computeSubstring( SubstringNode node, Set<String> uuidSet )
+        throws Exception
+    {
+        AttributeType attributeType = node.getAttributeType();
+
+        // Fetch all the UUIDs if we have an index
+        if ( db.hasIndexOn( attributeType ) )
+        {
+            Index<String, Entry, String> userIndex = ( ( Index<String, Entry, String> ) db.getIndex( attributeType ) );
+            Cursor<IndexEntry<String, String>> cursor = userIndex.forwardCursor();
+
+            // Position the index on the element we should start from
+            IndexEntry<String, String> indexEntry = new ForwardIndexEntry<String, String>();
+            indexEntry.setKey( node.getInitial() );
+
+            cursor.before( indexEntry );
+            int nbResults = 0;
+
+            MatchingRule rule = attributeType.getSubstring();
+
+            if ( rule == null )
+            {
+                rule = attributeType.getEquality();
+            }
+
+            Normalizer normalizer;
+            Pattern regexp;
+
+            if ( rule != null )
+            {
+                normalizer = rule.getNormalizer();
+            }
+            else
+            {
+                normalizer = new NoOpNormalizer( attributeType.getSyntaxOid() );
+            }
+
+            // compile the regular expression to search for a matching attribute
+            // if the attributeType is humanReadable
+            if ( attributeType.getSyntax().isHumanReadable() )
+            {
+                regexp = node.getRegex( normalizer );
+            }
+            else
+            {
+                regexp = null;
+            }
+
+            // And loop on it
+            while ( cursor.next() )
+            {
+                indexEntry = cursor.get();
+
+                String key = indexEntry.getKey();
+
+                if ( !regexp.matcher( key ).matches() )
+                {
+                    cursor.close();
+
+                    return nbResults;
+                }
+
+                String uuid = indexEntry.getId();
+
+                if ( !uuidSet.contains( uuid ) )
+                {
+                    // The UUID is not present in the Set, we add it
+                    uuidSet.add( uuid );
+                    nbResults++;
+                }
+            }
+
+            cursor.close();
+
+            return nbResults;
+        }
+        else
+        {
+            // No index, we will have to do a full scan
+            return Long.MAX_VALUE;
+        }
+    }
+
+
+    /**
      * Creates a OrCursor over a disjunction expression branch node.
      *
      * @param node the disjunction expression branch node
      * @return Cursor over candidates satisfying disjunction expression
      * @throws Exception on db access failures
      */
-    private <T> Cursor<IndexEntry<?, String>> buildOrCursor( OrNode node ) throws Exception
+    private <T> long computeOr( OrNode node, Set<String> uuidSet ) throws Exception
     {
         List<ExprNode> children = node.getChildren();
-        List<Cursor<IndexEntry<?, String>>> childCursors = new ArrayList<Cursor<IndexEntry<?, String>>>(
-            children.size() );
-        List<Evaluator<? extends ExprNode>> childEvaluators = new ArrayList<Evaluator<? extends ExprNode>>(
-            children.size() );
+
+        long nbOrResults = 0;
 
         // Recursively create Cursors and Evaluators for each child expression node
         for ( ExprNode child : children )
@@ -190,37 +581,34 @@ public class CursorBuilder
 
             if ( ( count != null ) && ( ( Long ) count == 0L ) )
             {
-                // We can skip the cursor, it will not return any candidate
-                continue;
+                long countLong = ( Long ) count;
+
+                if ( countLong == 0 )
+                {
+                    // We can skip the cursor, it will not return any candidate
+                    continue;
+                }
+                else if ( countLong == Long.MAX_VALUE )
+                {
+                    // We can stop here, we will anyway do a full scan
+                    return countLong;
+                }
             }
 
-            Cursor<IndexEntry<?, String>> childCursor = build( child );
+            long nbResults = build( child, uuidSet );
 
-            if ( childCursor instanceof EmptyIndexCursor )
+            if ( nbResults == Long.MAX_VALUE )
             {
-                // We can skip it
-                continue;
+                // We can stop here, we will anyway do a full scan
+                return nbResults;
+            }
+            else
+            {
+                nbOrResults += nbResults;
             }
-
-            childCursors.add( childCursor );
-            childEvaluators.add( evaluatorBuilder.build( child ) );
         }
 
-        int size = childCursors.size();
-
-        switch ( size )
-        {
-            case 0:
-                // All the cursor return 0, return an empty cursor
-                return ( Cursor ) new EmptyIndexCursor<T>();
-
-            case 1:
-                // W can just return the remaining cursor
-                return childCursors.get( 0 );
-
-            default:
-                return new OrCursor( childCursors, childEvaluators );
-        }
+        return nbOrResults;
     }
 
 
@@ -231,7 +619,7 @@ public class CursorBuilder
      * @return Cursor over the conjunction expression
      * @throws Exception on db access failures
      */
-    private <T> Cursor<IndexEntry<?, String>> buildAndCursor( AndNode node ) throws Exception
+    private long computeAnd( AndNode node, Set<String> uuidSet ) throws Exception
     {
         int minIndex = 0;
         long minValue = Long.MAX_VALUE;
@@ -240,7 +628,7 @@ public class CursorBuilder
         /*
          * We scan the child nodes of a branch node searching for the child
          * expression node with the smallest scan count.  This is the child
-         * we will use for iteration by creating a Cursor over its expression.
+         * we will use for iteration
          */
         final List<ExprNode> children = node.getChildren();
 
@@ -259,7 +647,7 @@ public class CursorBuilder
             if ( value == 0L )
             {
                 // No need to go any further : we won't have matching candidates anyway
-                return ( Cursor ) new EmptyIndexCursor<T>();
+                return 0L;
             }
 
             if ( value < minValue )
@@ -269,30 +657,41 @@ public class CursorBuilder
             }
         }
 
-        // Once found we build the child Evaluators minus the one for the minChild
+        // Once found we return the number of candidates for this child
         ExprNode minChild = children.get( minIndex );
-        List<Evaluator<? extends ExprNode>> childEvaluators = new ArrayList<Evaluator<? extends ExprNode>>(
-            children.size() - 1 );
+        long nbResults = build( minChild, uuidSet );
+
+        return nbResults;
+    }
+
+
+    /**
+     * Creates an AndCursor over a conjunction expression branch node.
+     *
+     * @param node a conjunction expression branch node
+     * @return Cursor over the conjunction expression
+     * @throws Exception on db access failures
+     */
+    private long computeNot( NotNode node, Set<String> uuidSet ) throws Exception
+    {
+        final List<ExprNode> children = node.getChildren();
 
-        // Do recursive call to build min child Cursor then create AndCursor
-        Cursor<IndexEntry<?, String>> childCursor = build( minChild );
+        ExprNode child = children.get( 0 );
+        Object count = child.get( "count" );
 
-        if ( childCursor instanceof EmptyIndexCursor )
+        if ( count == null )
         {
-            // We can return directly : the And will not select any candidate
-            return childCursor;
+            return Long.MAX_VALUE;
         }
 
-        for ( ExprNode child : children )
-        {
-            if ( child == minChild )
-            {
-                continue;
-            }
+        long value = ( Long ) count;
 
-            childEvaluators.add( evaluatorBuilder.build( child ) );
+        if ( value == Long.MAX_VALUE )
+        {
+            // No need to go any further : we won't have matching candidates anyway
+            return 0L;
         }
 
-        return new AndCursor( childCursor, childEvaluators );
+        return Long.MAX_VALUE;
     }
 }

Modified: directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/DefaultSearchEngine.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/DefaultSearchEngine.java?rev=1381944&r1=1381943&r2=1381944&view=diff
==============================================================================
--- directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/DefaultSearchEngine.java (original)
+++ directory/apacheds/branches/apacheds-mvbt/xdbm-partition/src/main/java/org/apache/directory/server/xdbm/search/impl/DefaultSearchEngine.java Fri Sep  7 09:25:05 2012
@@ -24,12 +24,14 @@ import java.util.HashSet;
 import java.util.Set;
 
 import org.apache.directory.server.core.api.partition.Partition;
+import org.apache.directory.server.core.partition.impl.btree.IndexCursorAdaptor;
 import org.apache.directory.server.i18n.I18n;
 import org.apache.directory.server.xdbm.ForwardIndexEntry;
 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.server.xdbm.search.Optimizer;
+import org.apache.directory.server.xdbm.search.PartitionSearchResult;
 import org.apache.directory.server.xdbm.search.SearchEngine;
 import org.apache.directory.shared.ldap.model.cursor.Cursor;
 import org.apache.directory.shared.ldap.model.entry.Entry;
@@ -100,20 +102,21 @@ public class DefaultSearchEngine impleme
     /**
      * {@inheritDoc}
      */
-    public Set<IndexEntry<String, String>> buildResultSet( Dn base, AliasDerefMode aliasDerefMode, ExprNode filter,
+    public PartitionSearchResult computeResult( Dn base, AliasDerefMode aliasDerefMode, ExprNode filter,
         SearchScope scope ) throws Exception
     {
         Dn effectiveBase;
         String baseId = db.getEntryId( base );
-        Set<IndexEntry<String, String>> result = new HashSet<IndexEntry<String, String>>();
+        PartitionSearchResult searchSet = new PartitionSearchResult();
+        Set<IndexEntry<String, String>> resultSet = new HashSet<IndexEntry<String, String>>();
 
         // Check that we have an entry, otherwise we can immediately get out
         if ( baseId == null )
         {
             if ( ( ( Partition ) db ).getSuffixDn().equals( base ) )
             {
-                // The context entry is not created yet, return an empty cursor
-                return result;
+                // The context entry is not created yet, return an empty result
+                return searchSet;
             }
             else
             {
@@ -177,13 +180,12 @@ public class DefaultSearchEngine impleme
             }
 
             indexEntry.setEntry( entry );
+            resultSet.add( indexEntry );
 
-            if ( evaluator.evaluate( indexEntry ) )
-            {
-                result.add( indexEntry );
-            }
+            searchSet.setEvaluator( evaluator );
+            searchSet.setResultSet( resultSet );
 
-            return result;
+            return searchSet;
         }
 
         // Add the scope node using the effective base to the filter
@@ -194,16 +196,44 @@ public class DefaultSearchEngine impleme
 
         // Annotate the node with the optimizer and return search enumeration.
         optimizer.annotate( root );
+        Evaluator<? extends ExprNode> evaluator = evaluatorBuilder.build( root );
 
-        Cursor<IndexEntry<Object, String>> cursor = ( Cursor ) cursorBuilder.build( root );
+        Set<String> uuidSet = new HashSet<String>();
 
-        while ( cursor.next() )
+        long nbResults = cursorBuilder.build( root, uuidSet );
+
+        if ( nbResults < Long.MAX_VALUE )
+        {
+            for ( String uuid : uuidSet )
+            {
+                ForwardIndexEntry<String, String> indexEntry = new ForwardIndexEntry<String, String>();
+                indexEntry.setId( uuid );
+                resultSet.add( indexEntry );
+            }
+        }
+        else
         {
-            IndexEntry indexEntry = cursor.get();
-            result.add( indexEntry );
+            // Full scan : use the MasterTable
+            Cursor<IndexEntry<String, String>> cursor = new IndexCursorAdaptor( db.getMasterTable().cursor(), true );
+
+            while ( cursor.next() )
+            {
+                IndexEntry<String, String> indexEntry = cursor.get();
+
+                // Here, the indexEntry contains a <UUID, Entry> tuple. Convert it to <UUID, UUID> 
+                ForwardIndexEntry<String, String> forwardIndexEntry = new ForwardIndexEntry<String, String>();
+                forwardIndexEntry.setKey( indexEntry.getKey() );
+                forwardIndexEntry.setId( indexEntry.getKey() );
+                forwardIndexEntry.setEntry( ( Entry ) indexEntry.getTuple().getValue() );
+
+                resultSet.add( forwardIndexEntry );
+            }
         }
 
-        return result;
+        searchSet.setEvaluator( evaluator );
+        searchSet.setResultSet( resultSet );
+
+        return searchSet;
     }
 
 



Mime
View raw message