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 07:50:21 UTC
svn commit: r642511 - in
/directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl:
AndCursor.java AndEvaluator.java CursorBuilder.java OrCursor.java
SubstringCursor.java
Author: akarasulu
Date: Fri Mar 28 23:50:18 2008
New Revision: 642511
URL: http://svn.apache.org/viewvc?rev=642511&view=rev
Log:
Rigging in logical expression Cursors into CursorBuilder ...
o fixed bug in optimization code for Evaluators where Long scan counts should
be used instead of Integer scan counts
o fixed generics problem in SubstringCursor
o using Lists instead of arrays for child Cursors and Evaluators in the
OrCursor - again this is due to problems with using generics to create
generic arrays
o added code to build following Cursors in CursorBuilder which is still badly
broken and will not compile:
- OrCursor
- AndCursor
- NotCursor
- SubstringCursor
Modified:
directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/AndCursor.java
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/CursorBuilder.java
directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/OrCursor.java
directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/SubstringCursor.java
Modified: directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/AndCursor.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/AndCursor.java?rev=642511&r1=642510&r2=642511&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/AndCursor.java (original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/AndCursor.java Fri Mar 28 23:50:18 2008
@@ -170,8 +170,8 @@
{
public int compare( Evaluator<?, Attributes> e1, Evaluator<?, Attributes> e2 )
{
- int scanCount1 = ( Integer ) e1.getExpression().get( "count" );
- int scanCount2 = ( Integer ) e2.getExpression().get( "count" );
+ long scanCount1 = ( Long ) e1.getExpression().get( "count" );
+ long scanCount2 = ( Long ) e2.getExpression().get( "count" );
if ( scanCount1 == scanCount2 )
{
Modified: 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=642511&r1=642510&r2=642511&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/AndEvaluator.java (original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/AndEvaluator.java Fri Mar 28 23:50:18 2008
@@ -72,8 +72,8 @@
{
public int compare( Evaluator<?, Attributes> e1, Evaluator<?, Attributes> e2 )
{
- int scanCount1 = ( Integer ) e1.getExpression().get( "count" );
- int scanCount2 = ( Integer ) e2.getExpression().get( "count" );
+ long scanCount1 = ( Long ) e1.getExpression().get( "count" );
+ long scanCount2 = ( Long ) e2.getExpression().get( "count" );
if ( scanCount1 == scanCount2 )
{
Modified: directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/CursorBuilder.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/CursorBuilder.java?rev=642511&r1=642510&r2=642511&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/CursorBuilder.java (original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/CursorBuilder.java Fri Mar 28 23:50:18 2008
@@ -21,18 +21,20 @@
import java.util.List;
+import java.util.ArrayList;
import javax.naming.NamingEnumeration;
import javax.naming.NamingException;
import javax.naming.directory.Attributes;
-import org.apache.directory.server.schema.registries.AttributeTypeRegistry;
+import org.apache.directory.server.schema.registries.Registries;
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.Store;
import org.apache.directory.server.core.partition.impl.btree.IndexAssertion;
import org.apache.directory.server.core.partition.impl.btree.IndexAssertionEnumeration;
+import org.apache.directory.server.core.cursor.Cursor;
import org.apache.directory.shared.ldap.NotImplementedException;
import org.apache.directory.shared.ldap.filter.AndNode;
import org.apache.directory.shared.ldap.filter.ApproximateNode;
@@ -56,33 +58,73 @@
* Builds Cursors over candidates that satisfy a filter expression.
*
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
- * @version $Rev$
+ * @version $Rev: 642490 $
*/
-public class CursorBuilder<E>
+public class CursorBuilder
{
- /** The database used by this enumerator */
- private Store<E> db = null;
- /** CursorBuilder flyweight for evaulating filter scope assertions */
- private ScopeCursorBuilder<E> scopeEnumerator;
+ /** The database used by this builder */
+ private Store<Attributes> db = null;
/** Evaluator dependency on a EvaluatorBuilder */
- private EvaluatorBuilder<Attributes> evaluatorBuilder;
+ private EvaluatorBuilder evaluatorBuilder;
+ private final Registries registries;
/**
* Creates an expression tree enumerator.
*
* @param db database used by this enumerator
- * @param evaluatorBuilder
+ * @param evaluatorBuilder the evaluator builder
+ * @param registries the schema registries
*/
- public CursorBuilder(BTreePartition db, AttributeTypeRegistry attributeTypeRegistry,
- EvaluatorBuilder evaluatorBuilder )
+ public CursorBuilder( Store<Attributes> db,
+ EvaluatorBuilder evaluatorBuilder,
+ Registries registries )
{
this.db = db;
this.evaluatorBuilder = evaluatorBuilder;
+ this.registries = registries;
+ }
+
+
+ public Cursor<IndexEntry<?,Attributes>> build( ExprNode node ) throws Exception
+ {
+ switch ( node.getAssertionType() )
+ {
+ /* ---------- LEAF NODE HANDLING ---------- */
+
+ case APPROXIMATE:
+ throw new NotImplementedException();
+ case EQUALITY:
+ throw new NotImplementedException();
+ case GREATEREQ:
+ throw new NotImplementedException();
+ case LESSEQ:
+ throw new NotImplementedException();
+ case PRESENCE:
+ throw new NotImplementedException();
+ case SCOPE:
+ throw new NotImplementedException();
+ case SUBSTRING:
+ return new SubstringCursor( db, ( SubstringEvaluator ) evaluatorBuilder.build( node ) );
+
+ /* ---------- LOGICAL OPERATORS ---------- */
+
+ case AND:
+ return buildAndCursor( ( AndNode ) node );
+ case NOT:
+ return new NotCursor( db, evaluatorBuilder.build( ( ( NotNode ) node).getFirstChild() ) );
+ case OR:
+ return buildOrCursor( ( OrNode ) node );
+
+ /* ---------- NOT IMPLEMENTED ---------- */
- LeafEvaluator leafEvaluator = evaluatorBuilder.getLeafEvaluator();
- scopeEnumerator = new ScopeCursorBuilder( db, leafEvaluator.getScopeEvaluator() );
- substringEnumerator = new SubstringCursorBuilder( db, attributeTypeRegistry, leafEvaluator.getSubstringEvaluator() );
+ case ASSERTION:
+ case EXTENSIBLE:
+ throw new NotImplementedException();
+
+ default:
+ throw new IllegalStateException( "Unknown assertion type: " + node.getAssertionType() );
+ }
}
@@ -171,66 +213,37 @@
/**
- * Creates an enumeration over a disjunction expression branch node.
+ * 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 or registry access failures
*/
- private NamingEnumeration<ForwardIndexEntry> enumDisj( OrNode node ) throws NamingException
+ private Cursor<IndexEntry<?,Attributes>> buildOrCursor( OrNode node ) throws Exception
{
List<ExprNode> children = node.getChildren();
- NamingEnumeration<IndexRecord>[] childEnumerations = new NamingEnumeration[children.size()];
+ List<Cursor<IndexEntry<?,Attributes>>> childCursors = new ArrayList<Cursor<IndexEntry<?,Attributes>>>(children.size());
+ List<Evaluator> childEvaluators = new ArrayList<Evaluator>( children.size() );
- // Recursively create NamingEnumerations for each child expression node
- for ( int ii = 0; ii < childEnumerations.length; ii++ )
+ // Recursively create Cursors and Evaluators for each child expression node
+ for ( ExprNode child : children )
{
- childEnumerations[ii] = enumerate( children.get( ii ) );
+ childCursors.add( build( child ) );
+ childEvaluators.add( evaluatorBuilder.build( child ) );
}
- return new OrCursor( childEnumerations );
+ //noinspection unchecked
+ return new OrCursor( childCursors, childEvaluators );
}
/**
- * Creates an enumeration over a negation expression branch node.
- *
- * @param node a negation expression branch node
- */
- private NamingEnumeration<ForwardIndexEntry> enumNeg( final BranchNode node ) throws NamingException
- {
- NamingEnumeration<ForwardIndexEntry> baseEnumeration = null;
- NamingEnumeration<ForwardIndexEntry> enumeration = null;
-
- try
- {
- baseEnumeration = db.getNdnIndex().listIndices();
- }
- catch ( java.io.IOException e )
- {
- e.printStackTrace(); //To change body of catch statement use File | Settings | File Templates.
- }
-
- IndexAssertion assertion = new IndexAssertion()
- {
- public boolean assertCandidate( IndexEntry rec ) throws NamingException
- {
- // NOTICE THE ! HERE
- // The candidate is valid if it does not pass assertion. A
- // candidate that passes assertion is therefore invalid.
- return !evaluatorBuilder.evaluate( node.getFirstChild(), rec );
- }
- };
-
- enumeration = new IndexAssertionEnumeration( baseEnumeration, assertion, true );
- return enumeration;
- }
-
-
- /**
- * Creates an enumeration over a conjunction expression branch node.
+ * Creates an AndCursor over a conjunction expression branch node.
*
* @param node a conjunction expression branch node
+ * @return Cursor over the conjunction expression
*/
- private NamingEnumeration<ForwardIndexEntry> enumConj( final AndNode node ) throws NamingException
+ private Cursor<IndexEntry<?,Attributes>> buildAndCursor( AndNode node ) throws Exception
{
int minIndex = 0;
long minValue = Long.MAX_VALUE;
@@ -239,8 +252,7 @@
/*
* 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 NamingEnumeration over its
- * expression.
+ * we will use for iteration by creating a Cursor over its expression.
*/
final List<ExprNode> children = node.getChildren();
@@ -256,36 +268,23 @@
}
}
- // Once found we build the child enumeration & the wrapping enum
- final ExprNode minChild = children.get( minIndex );
- IndexAssertion assertion = new IndexAssertion()
+ // Once found we build the child Evaluators minus the one for the minChild
+ ExprNode minChild = children.get( minIndex );
+ List<Evaluator<? extends ExprNode, Attributes>> childEvaluators =
+ new ArrayList<Evaluator<? extends ExprNode, Attributes>>( children.size() - 1 );
+ for ( ExprNode child : children )
{
- public boolean assertCandidate( IndexEntry rec ) throws NamingException
+ if ( child == minChild )
{
- for ( int ii = 0; ii < children.size(); ii++ )
- {
- ExprNode child = children.get( ii );
-
- // Skip the child (with min scan count) chosen for enum
- if ( child == minChild )
- {
- continue;
- }
- else if ( !evaluatorBuilder.evaluate( child, rec ) )
- {
- return false;
- }
- }
-
- return true;
- }
- };
-
- // Do recursive call to build child enumeration then wrap and return
- NamingEnumeration<ForwardIndexEntry> underlying = enumerate( minChild );
- IndexAssertionEnumeration iae;
- iae = new IndexAssertionEnumeration( underlying, assertion );
- return iae;
+ continue;
+ }
+
+ childEvaluators.add( evaluatorBuilder.build( child ) );
+ }
+
+ // Do recursive call to build min child Cursor then create AndCursor
+ Cursor<IndexEntry<?,Attributes>> childCursor = build( minChild );
+ return new AndCursor( childCursor, childEvaluators );
}
Modified: directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/OrCursor.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/OrCursor.java?rev=642511&r1=642510&r2=642511&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/OrCursor.java (original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/OrCursor.java Fri Mar 28 23:50:18 2008
@@ -34,20 +34,21 @@
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
* @version $$Rev$$
*/
-public class OrCursor<E> extends AbstractCursor<IndexEntry<?,E>>
+public class OrCursor<Attributes> extends AbstractCursor<IndexEntry<?,Attributes>>
{
private static final String UNSUPPORTED_MSG =
"OrCursors are not ordered and do not support positioning by element.";
- private final Cursor<IndexEntry<?,E>>[] cursors;
- private final Evaluator[] evaluators;
+ private final List<Cursor<IndexEntry<?,Attributes>>> cursors;
+ private final List<Evaluator> evaluators;
private final List<Set<Long>> blacklists;
private int cursorIndex = -1;
private boolean available = false;
- public OrCursor( Cursor<IndexEntry<?,E>>[] cursors, Evaluator[] evaluators )
+ // TODO - do same evaluator fail fast optimization that we do in AndCursor
+ public OrCursor( List<Cursor<IndexEntry<?,Attributes>>> cursors, List<Evaluator> evaluators )
{
- if ( cursors.length <= 1 )
+ if ( cursors.size() <= 1 )
{
throw new IllegalArgumentException(
"Must have 2 or more sub-expression Cursors for a disjunction" );
@@ -57,7 +58,7 @@
this.evaluators = evaluators;
this.blacklists = new ArrayList<Set<Long>>();
//noinspection ForLoopReplaceableByForEach
- for ( int ii = 0; ii < cursors.length; ii++ )
+ for ( int ii = 0; ii < cursors.size(); ii++ )
{
this.blacklists.add( new HashSet<Long>() );
}
@@ -70,13 +71,13 @@
}
- public void before( IndexEntry<?, E> element ) throws Exception
+ public void before( IndexEntry<?, Attributes> element ) throws Exception
{
throw new UnsupportedOperationException( UNSUPPORTED_MSG );
}
- public void after( IndexEntry<?, E> element ) throws Exception
+ public void after( IndexEntry<?, Attributes> element ) throws Exception
{
throw new UnsupportedOperationException( UNSUPPORTED_MSG );
}
@@ -85,15 +86,15 @@
public void beforeFirst() throws Exception
{
cursorIndex = 0;
- cursors[cursorIndex].beforeFirst();
+ cursors.get( cursorIndex ).beforeFirst();
available = false;
}
public void afterLast() throws Exception
{
- cursorIndex = cursors.length - 1;
- cursors[cursorIndex].afterLast();
+ cursorIndex = cursors.size() - 1;
+ cursors.get( cursorIndex ).afterLast();
available = false;
}
@@ -125,9 +126,9 @@
* @param indexEntry the index entry to blacklist
* @throws Exception if there are problems accessing underlying db
*/
- private void blackListIfDuplicate( IndexEntry<?,E> indexEntry ) throws Exception
+ private void blackListIfDuplicate( IndexEntry<?,Attributes> indexEntry ) throws Exception
{
- for ( int ii = 0; ii < evaluators.length; ii++ )
+ for ( int ii = 0; ii < evaluators.size(); ii++ )
{
if ( ii == cursorIndex )
{
@@ -135,7 +136,7 @@
}
//noinspection unchecked
- if ( evaluators[ii].evaluate( indexEntry ) )
+ if ( evaluators.get( ii ).evaluate( indexEntry ) )
{
blacklists.get( ii ).add( indexEntry.getId() );
}
@@ -145,9 +146,9 @@
public boolean previous() throws Exception
{
- while ( cursors[cursorIndex].previous() )
+ while ( cursors.get( cursorIndex ).previous() )
{
- IndexEntry<?,E> candidate = cursors[cursorIndex].get();
+ IndexEntry<?,Attributes> candidate = cursors.get( cursorIndex ).get();
if ( ! isBlackListed( candidate.getId() ) )
{
blackListIfDuplicate( candidate );
@@ -158,11 +159,11 @@
while ( cursorIndex > 0 )
{
cursorIndex--;
- cursors[cursorIndex].afterLast();
+ cursors.get( cursorIndex ).afterLast();
- while ( cursors[cursorIndex].previous() )
+ while ( cursors.get( cursorIndex ).previous() )
{
- IndexEntry<?,E> candidate = cursors[cursorIndex].get();
+ IndexEntry<?,Attributes> candidate = cursors.get( cursorIndex ).get();
if ( ! isBlackListed( candidate.getId() ) )
{
blackListIfDuplicate( candidate );
@@ -177,9 +178,9 @@
public boolean next() throws Exception
{
- while ( cursors[cursorIndex].next() )
+ while ( cursors.get( cursorIndex ).next() )
{
- IndexEntry<?,E> candidate = cursors[cursorIndex].get();
+ IndexEntry<?,Attributes> candidate = cursors.get( cursorIndex ).get();
if ( ! isBlackListed( candidate.getId() ) )
{
blackListIfDuplicate( candidate );
@@ -187,14 +188,14 @@
}
}
- while ( cursorIndex < cursors.length - 1 )
+ while ( cursorIndex < cursors.size() - 1 )
{
cursorIndex++;
- cursors[cursorIndex].beforeFirst();
+ cursors.get( cursorIndex ).beforeFirst();
- while ( cursors[cursorIndex].next() )
+ while ( cursors.get( cursorIndex ).next() )
{
- IndexEntry<?,E> candidate = cursors[cursorIndex].get();
+ IndexEntry<?,Attributes> candidate = cursors.get( cursorIndex ).get();
if ( ! isBlackListed( candidate.getId() ) )
{
blackListIfDuplicate( candidate );
@@ -207,11 +208,11 @@
}
- public IndexEntry<?, E> get() throws Exception
+ public IndexEntry<?, Attributes> get() throws Exception
{
if ( available )
{
- return cursors[cursorIndex].get();
+ return cursors.get( cursorIndex ).get();
}
throw new InvalidCursorPositionException( "Cursor has not been positioned yet." );
@@ -220,7 +221,7 @@
public boolean isElementReused()
{
- return cursors[cursorIndex].isElementReused();
+ return cursors.get( cursorIndex ).isElementReused();
}
Modified: directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/SubstringCursor.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/SubstringCursor.java?rev=642511&r1=642510&r2=642511&view=diff
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/SubstringCursor.java (original)
+++ directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/SubstringCursor.java Fri Mar 28 23:50:18 2008
@@ -38,7 +38,7 @@
* @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
* @version $$Rev$$
*/
-public class SubstringCursor extends AbstractCursor<IndexEntry<String, Attributes>>
+public class SubstringCursor extends AbstractCursor<IndexEntry<?, Attributes>>
{
private static final String UNSUPPORTED_MSG =
"SubstringCursors may not be ordered and do not support positioning by element.";
@@ -121,13 +121,13 @@
}
- public void before( IndexEntry<String, Attributes> element ) throws Exception
+ public void before( IndexEntry<?, Attributes> element ) throws Exception
{
throw new UnsupportedOperationException( UNSUPPORTED_MSG );
}
- public void after( IndexEntry<String, Attributes> element ) throws Exception
+ public void after( IndexEntry<?, Attributes> element ) throws Exception
{
throw new UnsupportedOperationException( UNSUPPORTED_MSG );
}
@@ -191,7 +191,7 @@
}
- public IndexEntry<String, Attributes> get() throws Exception
+ public IndexEntry<?, Attributes> get() throws Exception
{
if ( available )
{