directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From akaras...@apache.org
Subject svn commit: r642508 - in /directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl: AndCursor.java NotCursor.java NotEvaluator.java OrCursor.java SubstringCursor.java
Date Sat, 29 Mar 2008 05:34:19 GMT
Author: akarasulu
Date: Fri Mar 28 22:34:18 2008
New Revision: 642508

URL: http://svn.apache.org/viewvc?rev=642508&view=rev
Log:
Adding Cursors and Evaluators for BranchNode expressions ...

 o added new BranchNode Cursors
    - AndCursor
    - NotCursor
 o fixed some typos and a bug in OrCursor and SubstringCursor with available
   property setting on positioning beforeFirst and afterLast
 o added new NotEvaluator
 o removed unnecessary iterator() on OrCursor


Added:
    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/NotCursor.java
    directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/NotEvaluator.java
Modified:
    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

Added: 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=642508&view=auto
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/AndCursor.java
(added)
+++ directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/AndCursor.java
Fri Mar 28 22:34:18 2008
@@ -0,0 +1,212 @@
+/*
+ *  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.server.xdbm.IndexEntry;
+import org.apache.directory.server.core.cursor.AbstractCursor;
+import org.apache.directory.server.core.cursor.Cursor;
+import org.apache.directory.server.core.cursor.InvalidCursorPositionException;
+import org.apache.directory.shared.ldap.filter.ExprNode;
+
+import javax.naming.directory.Attributes;
+import java.util.*;
+
+
+/**
+ * A Cursor returning candidates satisfying a logical conjunction expression.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $$Rev$$
+ */
+public class AndCursor extends AbstractCursor<IndexEntry<?,Attributes>>
+{
+    private static final String UNSUPPORTED_MSG =
+        "AndCursors are not ordered and do not support positioning by element.";
+    private final Cursor<IndexEntry<?,Attributes>> wrapped;
+    private final List<Evaluator<? extends ExprNode, Attributes>> evaluators;
+    private boolean available = false;
+
+
+    public AndCursor( Cursor<IndexEntry<?, Attributes>> wrapped,
+                      List<Evaluator<? extends ExprNode, Attributes>> evaluators
)
+    {
+        this.wrapped = wrapped;
+        this.evaluators = optimize( evaluators );
+    }
+
+
+    public boolean available()
+    {
+        return available;
+    }
+
+
+    public void before( IndexEntry<?, Attributes> element ) throws Exception
+    {
+        throw new UnsupportedOperationException( UNSUPPORTED_MSG );
+    }
+
+
+    public void after( IndexEntry<?, Attributes> element ) throws Exception
+    {
+        throw new UnsupportedOperationException( UNSUPPORTED_MSG );
+    }
+
+
+    public void beforeFirst() throws Exception
+    {
+        wrapped.beforeFirst();
+        available = false;
+    }
+
+
+    public void afterLast() throws Exception
+    {
+        wrapped.afterLast();
+        available = false;
+    }
+
+
+    public boolean first() throws Exception
+    {
+        beforeFirst();
+        return next();
+    }
+
+
+    public boolean last() throws Exception
+    {
+        afterLast();
+        return previous();
+    }
+
+
+    public boolean previous() throws Exception
+    {
+        while ( wrapped.previous() )
+        {
+            IndexEntry<?,Attributes> candidate = wrapped.get();
+            if ( matches( candidate ) )
+            {
+                return available = true;
+            }
+        }
+
+        return available = false;
+    }
+
+
+    public boolean next() throws Exception
+    {
+        while ( wrapped.next() )
+        {
+            IndexEntry<?,Attributes> candidate = wrapped.get();
+            if ( matches( candidate ) )
+            {
+                return available = true;
+            }
+        }
+
+        return available = false;
+    }
+
+
+    public IndexEntry<?, Attributes> get() throws Exception
+    {
+        if ( available )
+        {
+            return wrapped.get();
+        }
+
+        throw new InvalidCursorPositionException( "Cursor has not been positioned yet." );
+    }
+
+
+    public boolean isElementReused()
+    {
+        return wrapped.isElementReused();
+    }
+
+
+    /**
+     * TODO - duplicate code from AndEvaluator just make utility for this and
+     * for the same code in the OrEvaluator once done.
+     *
+     * 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;
+    }
+
+
+    private boolean matches( IndexEntry<?, Attributes> indexEntry ) throws Exception
+    {
+        for ( Evaluator<?,Attributes> evaluator : evaluators )
+        {
+            if ( ! evaluator.evaluate( indexEntry ) )
+            {
+                return false;
+            }
+        }
+
+        return true;
+    }
+}

Added: directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/NotCursor.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/NotCursor.java?rev=642508&view=auto
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/NotCursor.java
(added)
+++ directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/NotCursor.java
Fri Mar 28 22:34:18 2008
@@ -0,0 +1,147 @@
+/*
+ *  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.server.xdbm.IndexEntry;
+import org.apache.directory.server.xdbm.Store;
+import org.apache.directory.server.core.cursor.AbstractCursor;
+import org.apache.directory.server.core.cursor.Cursor;
+import org.apache.directory.server.core.cursor.InvalidCursorPositionException;
+import org.apache.directory.shared.ldap.filter.ExprNode;
+
+import javax.naming.directory.Attributes;
+
+
+/**
+ * A Cursor returning candidates satisfying a logical negation expression.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $$Rev$$
+ */
+public class NotCursor extends AbstractCursor<IndexEntry<?, Attributes>>
+{
+    private static final String UNSUPPORTED_MSG =
+        "NotCursors are not ordered and do not support positioning by element.";
+    private final Cursor<IndexEntry<String,Attributes>> ndnCursor;
+    private final Evaluator<? extends ExprNode, Attributes> childEvaluator;
+    private boolean available = false;
+
+
+    public NotCursor( Store<Attributes> db,
+                      Evaluator<? extends ExprNode, Attributes> childEvaluator ) throws
Exception
+    {
+        this.childEvaluator = childEvaluator;
+        this.ndnCursor = db.getNdnIndex().forwardCursor();
+    }
+
+
+    public boolean available()
+    {
+        return available;
+    }
+
+
+    public void before( IndexEntry<?, Attributes> element ) throws Exception
+    {
+        throw new UnsupportedOperationException( UNSUPPORTED_MSG );
+    }
+
+
+    public void after( IndexEntry<?, Attributes> element ) throws Exception
+    {
+        throw new UnsupportedOperationException( UNSUPPORTED_MSG );
+    }
+
+
+    public void beforeFirst() throws Exception
+    {
+        ndnCursor.beforeFirst();
+        available = false;
+    }
+
+
+    public void afterLast() throws Exception
+    {
+        ndnCursor.afterLast();
+        available = false;
+    }
+
+
+    public boolean first() throws Exception
+    {
+        beforeFirst();
+        return next();
+    }
+
+
+    public boolean last() throws Exception
+    {
+        afterLast();
+        return previous();
+    }
+
+
+    public boolean previous() throws Exception
+    {
+        while ( ndnCursor.previous() )
+        {
+            IndexEntry<?,Attributes> candidate = ndnCursor.get();
+            if ( ! childEvaluator.evaluate( candidate ) )
+            {
+                return available = true;
+            }
+        }
+
+        return available = false;
+    }
+
+
+    public boolean next() throws Exception
+    {
+        while ( ndnCursor.next() )
+        {
+            IndexEntry<?,Attributes> candidate = ndnCursor.get();
+            if ( ! childEvaluator.evaluate( candidate ) )
+            {
+                return available = true;
+            }
+        }
+
+        return available = false;
+    }
+
+
+    public IndexEntry<?, Attributes> get() throws Exception
+    {
+        if ( available )
+        {
+            return ndnCursor.get();
+        }
+
+        throw new InvalidCursorPositionException( "Cursor has not been positioned yet." );
+    }
+
+
+    public boolean isElementReused()
+    {
+        return ndnCursor.isElementReused();
+    }
+}

Added: directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/NotEvaluator.java
URL: http://svn.apache.org/viewvc/directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/NotEvaluator.java?rev=642508&view=auto
==============================================================================
--- directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/NotEvaluator.java
(added)
+++ directory/sandbox/akarasulu/bigbang/apacheds/xdbm-search/src/main/java/org/apache/directory/server/xdbm/search/impl/NotEvaluator.java
Fri Mar 28 22:34:18 2008
@@ -0,0 +1,59 @@
+/*
+ *  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.NotNode;
+import org.apache.directory.shared.ldap.filter.ExprNode;
+import org.apache.directory.server.xdbm.IndexEntry;
+
+import javax.naming.directory.Attributes;
+
+
+/**
+ * An Evaluator for logical negation (NOT) expressions.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $$Rev$$
+ */
+public class NotEvaluator implements Evaluator<NotNode, Attributes>
+{
+    private final NotNode node;
+    private final Evaluator<? extends ExprNode,Attributes> childEvaluator;
+
+
+    public NotEvaluator( NotNode node, Evaluator<? extends ExprNode, Attributes> childEvaluator
)
+    {
+        this.node = node;
+        this.childEvaluator = childEvaluator;
+    }
+
+
+    public boolean evaluate( IndexEntry<?, Attributes> indexEntry ) throws Exception
+    {
+        return ! childEvaluator.evaluate( indexEntry );
+    }
+
+
+    public NotNode getExpression()
+    {
+        return node;
+    }
+}

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=642508&r1=642507&r2=642508&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 22:34:18 2008
@@ -22,14 +22,14 @@
 
 import org.apache.directory.server.core.cursor.Cursor;
 import org.apache.directory.server.core.cursor.AbstractCursor;
-import org.apache.directory.server.core.cursor.CursorIterator;
+import org.apache.directory.server.core.cursor.InvalidCursorPositionException;
 import org.apache.directory.server.xdbm.IndexEntry;
 
 import java.util.*;
 
 
 /**
- * An OR'ing Cursor intended for returning large result sets.
+ * A Cursor returning candidates satisfying a logical disjunction expression.
  *
  * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
  * @version $$Rev$$
@@ -37,7 +37,7 @@
 public class OrCursor<E> extends AbstractCursor<IndexEntry<?,E>>
 {
     private static final String UNSUPPORTED_MSG =
-        "DisjunctionCursors are not ordered and do not support positioning by element.";
+        "OrCursors are not ordered and do not support positioning by element.";
     private final Cursor<IndexEntry<?,E>>[] cursors;
     private final Evaluator[] evaluators;
     private final List<Set<Long>> blacklists;
@@ -86,6 +86,7 @@
     {
         cursorIndex = 0;
         cursors[cursorIndex].beforeFirst();
+        available = false;
     }
 
 
@@ -93,6 +94,7 @@
     {
         cursorIndex = cursors.length - 1;
         cursors[cursorIndex].afterLast();
+        available = false;
     }
 
 
@@ -132,6 +134,7 @@
                 continue;
             }
 
+            //noinspection unchecked
             if ( evaluators[ii].evaluate( indexEntry ) )
             {
                 blacklists.get( ii ).add( indexEntry.getId() );
@@ -211,19 +214,13 @@
             return cursors[cursorIndex].get();
         }
 
-        throw new InvalidPropertiesFormatException( "Cursor has not been positioned." );
+        throw new InvalidCursorPositionException( "Cursor has not been positioned yet." );
     }
 
 
     public boolean isElementReused()
     {
         return cursors[cursorIndex].isElementReused();
-    }
-
-
-    public Iterator<IndexEntry<?, E>> iterator()
-    {
-        return new CursorIterator<IndexEntry<?, E>>( this );
     }
 
 

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=642508&r1=642507&r2=642508&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 22:34:18 2008
@@ -136,12 +136,14 @@
     public void beforeFirst() throws Exception
     {
         wrapped.beforeFirst();
+        available = false;
     }
 
 
     public void afterLast() throws Exception
     {
         wrapped.afterLast();
+        available = false;
     }
 
 



Mime
View raw message