directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From akaras...@apache.org
Subject 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
Date Sat, 29 Mar 2008 06:50:21 GMT
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 )
         {



Mime
View raw message