directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From akaras...@apache.org
Subject svn commit: r642506 - in /directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl: AndEvaluator.java ExpressionEvaluatorBuilder.java OrEvaluator.java ScopeCursorBuilder.java
Date Sat, 29 Mar 2008 04:47:34 GMT
Author: akarasulu
Date: Fri Mar 28 21:47:29 2008
New Revision: 642506

URL: http://svn.apache.org/viewvc?rev=642506&view=rev
Log:
More Evaluator related work ...

 o added new evaluators
    - OrEvaluator
    - AndEvaluator
 o removed ScopeCursorBuilder which is outdated 
 o modified ExpressionEvaluatorBuilder to build AND and OR node evaluators


Added:
    directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/AndEvaluator.java
    directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/OrEvaluator.java
Removed:
    directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/ScopeCursorBuilder.java
Modified:
    directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/ExpressionEvaluatorBuilder.java

Added: directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/AndEvaluator.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/AndEvaluator.java?rev=642506&view=auto
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/AndEvaluator.java
(added)
+++ directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/AndEvaluator.java
Fri Mar 28 21:47:29 2008
@@ -0,0 +1,120 @@
+/*
+ *  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.impl;
+
+
+import org.apache.directory.shared.ldap.filter.AndNode;
+import org.apache.directory.shared.ldap.filter.ExprNode;
+import org.apache.directory.server.xdbm.IndexEntry;
+
+import javax.naming.directory.Attributes;
+import java.util.List;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+
+
+/**
+ * An Evaluator for logical conjunction (AND) expressions.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $$Rev$$
+ */
+public class AndEvaluator implements Evaluator<AndNode,Attributes>
+{
+    private final List<Evaluator<? extends ExprNode,Attributes>> evaluators;
+
+    private final AndNode node;
+
+
+    public AndEvaluator( AndNode node, List<Evaluator<? extends ExprNode, Attributes>>
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,Attributes>>
+        optimize( List<Evaluator<? extends ExprNode,Attributes>> unoptimized
)
+    {
+        List<Evaluator<? extends ExprNode,Attributes>> optimized =
+            new ArrayList<Evaluator<? extends ExprNode,Attributes>>( unoptimized.size()
);
+        optimized.addAll( unoptimized );
+        Collections.sort( optimized, new Comparator<Evaluator<?,Attributes>>()
+        {
+            public int compare( Evaluator<?, Attributes> e1, Evaluator<?, Attributes>
e2 )
+            {
+                int scanCount1 = ( Integer ) e1.getExpression().get( "count" );
+                int scanCount2 = ( Integer ) e2.getExpression().get( "count" );
+
+                if ( scanCount1 == scanCount2 )
+                {
+                    return 0;
+                }
+
+                /*
+                 * We want the Evaluator with the smallest scan count first
+                 * since this node has the highest probability of failing, or
+                 * rather the least probability of succeeding.  That way we
+                 * can short the sub-expression evaluation process.
+                 */
+                if ( scanCount1 < scanCount2 )
+                {
+                    return -1;
+                }
+
+                return 1;
+            }
+        });
+
+        return optimized;
+    }
+
+
+    public boolean evaluate( IndexEntry<?, Attributes> indexEntry ) throws Exception
+    {
+        for ( Evaluator<?,Attributes> evaluator : evaluators )
+        {
+            if ( ! evaluator.evaluate( indexEntry ) )
+            {
+                return false;
+            }
+        }
+
+        return true;
+    }
+
+
+    public AndNode getExpression()
+    {
+        return node;
+    }
+}

Modified: directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/ExpressionEvaluatorBuilder.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/ExpressionEvaluatorBuilder.java?rev=642506&r1=642505&r2=642506&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/ExpressionEvaluatorBuilder.java
(original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/ExpressionEvaluatorBuilder.java
Fri Mar 28 21:47:29 2008
@@ -27,6 +27,9 @@
 import org.apache.directory.shared.ldap.filter.*;
 import org.apache.directory.shared.ldap.NotImplementedException;
 
+import java.util.List;
+import java.util.ArrayList;
+
 
 /**
  * Top level filter expression evaluator builder implemenation.
@@ -91,11 +94,11 @@
                 /* ---------- LOGICAL OPERATORS ---------- */
 
             case AND:
-                throw new NotImplementedException();
+                return buildAndEvaluator( ( AndNode ) node );
             case NOT:
                 throw new NotImplementedException();
             case OR:
-                throw new NotImplementedException();
+                return buildOrEvaluator( ( OrNode ) node );
 
                 /* ----------  NOT IMPLEMENTED  ---------- */
 
@@ -146,5 +149,31 @@
 //        {
 //                throw new NamingException( "Unrecognized branch node operator: " + bnode
);
 //        }
+    }
+
+
+    AndEvaluator buildAndEvaluator( AndNode node ) throws Exception
+    {
+        List<ExprNode> children = node.getChildren();
+        List<Evaluator<? extends ExprNode,Attributes>> evaluators =
+            new ArrayList<Evaluator<? extends ExprNode,Attributes>>( children.size()
);
+        for ( ExprNode child : children )
+        {
+            evaluators.add( build( child ) );
+        }
+        return new AndEvaluator( node, evaluators );
+    }
+
+
+    OrEvaluator buildOrEvaluator( OrNode node ) throws Exception
+    {
+        List<ExprNode> children = node.getChildren();
+        List<Evaluator<? extends ExprNode,Attributes>> evaluators =
+            new ArrayList<Evaluator<? extends ExprNode,Attributes>>( children.size()
);
+        for ( ExprNode child : children )
+        {
+            evaluators.add( build( child ) );
+        }
+        return new OrEvaluator( node, evaluators );
     }
 }

Added: directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/OrEvaluator.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/OrEvaluator.java?rev=642506&view=auto
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/OrEvaluator.java
(added)
+++ directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/OrEvaluator.java
Fri Mar 28 21:47:29 2008
@@ -0,0 +1,120 @@
+/*
+ *  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.impl;
+
+
+import org.apache.directory.shared.ldap.filter.OrNode;
+import org.apache.directory.shared.ldap.filter.ExprNode;
+import org.apache.directory.server.xdbm.IndexEntry;
+
+import javax.naming.directory.Attributes;
+import java.util.List;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+
+
+/**
+ * An Evaluator for logical disjunction (OR) expressions.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $$Rev$$
+ */
+public class OrEvaluator implements Evaluator<OrNode,Attributes>
+{
+    private final List<Evaluator<? extends ExprNode, Attributes>> evaluators;
+
+    private final OrNode node;
+
+
+    public OrEvaluator( OrNode node, List<Evaluator<? extends ExprNode, Attributes>>
evaluators )
+    {
+        this.node = node;
+        this.evaluators = optimize( evaluators );
+    }
+
+
+    /**
+     * Takes a set of Evaluators and copies then sorts them in a new list with
+     * decreasing scan counts on their expression nodes.  This is done to have
+     * the Evaluators with the greatest scan counts which have the highest
+     * probability of accepting 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 decreasing scan count ordering
+     */
+    private List<Evaluator<? extends ExprNode,Attributes>>
+        optimize( List<Evaluator<? extends ExprNode, Attributes>> unoptimized
)
+    {
+        List<Evaluator<? extends ExprNode, Attributes>> optimized =
+            new ArrayList<Evaluator<? extends ExprNode, Attributes>>( unoptimized.size()
);
+        optimized.addAll( unoptimized );
+        Collections.sort( optimized, new Comparator<Evaluator<? extends ExprNode,Attributes>>()
+        {
+            public int compare( Evaluator<? extends ExprNode, Attributes> e1, Evaluator<?
extends ExprNode, Attributes> e2 )
+            {
+                int scanCount1 = ( Integer ) e1.getExpression().get( "count" );
+                int scanCount2 = ( Integer ) e2.getExpression().get( "count" );
+
+                if ( scanCount1 == scanCount2 )
+                {
+                    return 0;
+                }
+
+                /*
+                 * We want the Evaluator with the largest scan count first
+                 * since this node has the highest probability of accepting,
+                 * or rather the least probability of failing.  That way we
+                 * can short the sub-expression evaluation process.
+                 */
+                if ( scanCount1 < scanCount2 )
+                {
+                    return 1;
+                }
+
+                return -1;
+            }
+        });
+
+        return optimized;
+    }
+
+
+    public boolean evaluate( IndexEntry<?, Attributes> indexEntry ) throws Exception
+    {
+        for ( Evaluator<?,Attributes> evaluator : evaluators )
+        {
+            if ( evaluator.evaluate( indexEntry ) )
+            {
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+
+    public OrNode getExpression()
+    {
+        return node;
+    }
+}
\ No newline at end of file



Mime
View raw message