You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by ak...@apache.org on 2008/03/29 05:47:34 UTC
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
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