View Javadoc

1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  You may obtain a copy of the License at
9    *  
10   *    http://www.apache.org/licenses/LICENSE-2.0
11   *  
12   *  Unless required by applicable law or agreed to in writing,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License. 
18   *  
19   */
20  package org.apache.directory.server.xdbm.search.impl;
21  
22  
23  import org.apache.directory.server.xdbm.IndexEntry;
24  import org.apache.directory.server.xdbm.AbstractIndexCursor;
25  import org.apache.directory.server.xdbm.IndexCursor;
26  import org.apache.directory.server.xdbm.search.Evaluator;
27  import org.apache.directory.server.core.cursor.InvalidCursorPositionException;
28  import org.apache.directory.server.core.entry.ServerEntry;
29  import org.apache.directory.shared.ldap.filter.ExprNode;
30  
31  import java.util.*;
32  
33  
34  /**
35   * A Cursor returning candidates satisfying a logical conjunction expression.
36   *
37   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
38   * @version $Rev$
39   */
40  public class AndCursor<V> extends AbstractIndexCursor<V, ServerEntry>
41  {
42      private static final String UNSUPPORTED_MSG =
43          "AndCursors are not ordered and do not support positioning by element.";
44      private final IndexCursor<V,ServerEntry> wrapped;
45      private final List<Evaluator<? extends ExprNode, ServerEntry>> evaluators;
46      private boolean available = false;
47  
48  
49      public AndCursor( IndexCursor<V, ServerEntry> wrapped,
50                        List<Evaluator<? extends ExprNode, ServerEntry>> evaluators )
51      {
52          this.wrapped = wrapped;
53          this.evaluators = optimize( evaluators );
54      }
55  
56  
57      public boolean available()
58      {
59          return available;
60      }
61  
62  
63      public void beforeValue( Long id, V value )
64      {
65          throw new UnsupportedOperationException( UNSUPPORTED_MSG );
66      }
67  
68  
69      public void afterValue( Long id, V value )
70      {
71          throw new UnsupportedOperationException( UNSUPPORTED_MSG );
72      }
73  
74  
75      public void before( IndexEntry<V, ServerEntry> element ) throws Exception
76      {
77          throw new UnsupportedOperationException( UNSUPPORTED_MSG );
78      }
79  
80  
81      public void after( IndexEntry<V, ServerEntry> element ) throws Exception
82      {
83          throw new UnsupportedOperationException( UNSUPPORTED_MSG );
84      }
85  
86  
87      public void beforeFirst() throws Exception
88      {
89          checkNotClosed( "beforeFirst()" );
90          wrapped.beforeFirst();
91          available = false;
92      }
93  
94  
95      public void afterLast() throws Exception
96      {
97          checkNotClosed( "afterLast()" );
98          wrapped.afterLast();
99          available = false;
100     }
101 
102 
103     public boolean first() throws Exception
104     {
105         beforeFirst();
106         return next();
107     }
108 
109 
110     public boolean last() throws Exception
111     {
112         afterLast();
113         return previous();
114     }
115 
116 
117     public boolean previous() throws Exception
118     {
119         while ( wrapped.previous() )
120         {
121             checkNotClosed( "previous()" );
122 
123             IndexEntry<?,ServerEntry> candidate = wrapped.get();
124             if ( matches( candidate ) )
125             {
126                 return available = true;
127             }
128         }
129 
130         return available = false;
131     }
132 
133 
134     public boolean next() throws Exception
135     {
136         while ( wrapped.next() )
137         {
138             checkNotClosed( "next()" );
139             IndexEntry<?,ServerEntry> candidate = wrapped.get();
140             if ( matches( candidate ) )
141             {
142                 return available = true;
143             }
144         }
145 
146         return available = false;
147     }
148 
149 
150     public IndexEntry<V, ServerEntry> get() throws Exception
151     {
152         checkNotClosed( "get()" );
153         if ( available )
154         {
155             return wrapped.get();
156         }
157 
158         throw new InvalidCursorPositionException( "Cursor has not been positioned yet." );
159     }
160 
161 
162     public boolean isElementReused()
163     {
164         return wrapped.isElementReused();
165     }
166 
167 
168     public void close() throws Exception
169     {
170         super.close();
171         wrapped.close();
172     }
173 
174 
175     /**
176      * TODO - duplicate code from AndEvaluator just make utility for this and
177      * for the same code in the OrEvaluator once done.
178      *
179      * Takes a set of Evaluators and copies then sorts them in a new list with
180      * increasing scan counts on their expression nodes.  This is done to have
181      * the Evaluators with the least scan count which have the highest
182      * probability of rejecting a candidate first.  That will increase the
183      * chance of shorting the checks on evaluators early so extra lookups and
184      * comparisons are avoided.
185      *
186      * @param unoptimized the unoptimized list of Evaluators
187      * @return optimized Evaluator list with increasing scan count ordering
188      */
189     private List<Evaluator<? extends ExprNode,ServerEntry>>
190         optimize( List<Evaluator<? extends ExprNode,ServerEntry>> unoptimized )
191     {
192         List<Evaluator<? extends ExprNode,ServerEntry>> optimized =
193             new ArrayList<Evaluator<? extends ExprNode,ServerEntry>>( unoptimized.size() );
194         optimized.addAll( unoptimized );
195         Collections.sort( optimized, new Comparator<Evaluator<?,ServerEntry>>()
196         {
197             public int compare( Evaluator<?, ServerEntry> e1, Evaluator<?, ServerEntry> e2 )
198             {
199                 long scanCount1 = ( Long ) e1.getExpression().get( "count" );
200                 long scanCount2 = ( Long ) e2.getExpression().get( "count" );
201 
202                 if ( scanCount1 == scanCount2 )
203                 {
204                     return 0;
205                 }
206 
207                 /*
208                  * We want the Evaluator with the smallest scan count first
209                  * since this node has the highest probability of failing, or
210                  * rather the least probability of succeeding.  That way we
211                  * can short the sub-expression evaluation process.
212                  */
213                 if ( scanCount1 < scanCount2 )
214                 {
215                     return -1;
216                 }
217 
218                 return 1;
219             }
220         });
221 
222         return optimized;
223     }
224 
225 
226     private boolean matches( IndexEntry<?, ServerEntry> indexEntry ) throws Exception
227     {
228         for ( Evaluator<?,ServerEntry> evaluator : evaluators )
229         {
230             if ( ! evaluator.evaluate( indexEntry ) )
231             {
232                 return false;
233             }
234         }
235 
236         return true;
237     }
238 }