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 java.util.List;
24  import java.util.ArrayList;
25  
26  import org.apache.directory.server.xdbm.Store;
27  import org.apache.directory.server.xdbm.IndexCursor;
28  import org.apache.directory.server.xdbm.search.Evaluator;
29  import org.apache.directory.server.core.entry.ServerEntry;
30  import org.apache.directory.shared.ldap.NotImplementedException;
31  import org.apache.directory.shared.ldap.filter.*;
32  
33  
34  /**
35   * Builds Cursors over candidates that satisfy a filter expression.
36   * 
37   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
38   * @version $Rev: 659774 $
39   */
40  public class CursorBuilder
41  {
42      /** The database used by this builder */
43      private Store<ServerEntry> db = null;
44  
45      /** Evaluator dependency on a EvaluatorBuilder */
46      private EvaluatorBuilder evaluatorBuilder;
47  
48  
49      /**
50       * Creates an expression tree enumerator.
51       *
52       * @param db database used by this enumerator
53       * @param evaluatorBuilder the evaluator builder
54       */
55      public CursorBuilder( Store<ServerEntry> db, EvaluatorBuilder evaluatorBuilder )
56      {
57          this.db = db;
58          this.evaluatorBuilder = evaluatorBuilder;
59      }
60  
61  
62      public IndexCursor<?,ServerEntry> build( ExprNode node ) throws Exception
63      {
64          switch ( node.getAssertionType() )
65          {
66              /* ---------- LEAF NODE HANDLING ---------- */
67  
68              case APPROXIMATE:
69                  return new ApproximateCursor( db, ( ApproximateEvaluator ) evaluatorBuilder.build( node ) );
70              case EQUALITY:
71                  return new EqualityCursor( db, ( EqualityEvaluator ) evaluatorBuilder.build( node ) );
72              case GREATEREQ:
73                  return new GreaterEqCursor( db, ( GreaterEqEvaluator ) evaluatorBuilder.build( node ) );
74              case LESSEQ:
75                  return new LessEqCursor( db, ( LessEqEvaluator ) evaluatorBuilder.build( node ) );
76              case PRESENCE:
77                  return new PresenceCursor( db, ( PresenceEvaluator ) evaluatorBuilder.build( node ) );
78              case SCOPE:
79                  if ( ( ( ScopeNode ) node ).getScope() == SearchScope.ONELEVEL )
80                  {
81                      return new OneLevelScopeCursor( db, ( OneLevelScopeEvaluator ) evaluatorBuilder.build( node ) );
82                  }
83                  else
84                  {
85                      return new SubtreeScopeCursor( db, ( SubtreeScopeEvaluator ) evaluatorBuilder.build( node ) );
86                  }
87              case SUBSTRING:
88                  return new SubstringCursor( db, ( SubstringEvaluator ) evaluatorBuilder.build( node ) );
89  
90              /* ---------- LOGICAL OPERATORS ---------- */
91  
92              case AND:
93                  return buildAndCursor( ( AndNode ) node );
94              case NOT:
95                  return new NotCursor( db, evaluatorBuilder.build( ( ( NotNode ) node).getFirstChild() ) );
96              case OR:
97                  return buildOrCursor( ( OrNode ) node );
98  
99              /* ----------  NOT IMPLEMENTED  ---------- */
100 
101             case ASSERTION:
102             case EXTENSIBLE:
103                 throw new NotImplementedException();
104 
105             default:
106                 throw new IllegalStateException( "Unknown assertion type: " + node.getAssertionType() );
107         }
108     }
109 
110 
111     /**
112      * Creates a OrCursor over a disjunction expression branch node.
113      *
114      * @param node the disjunction expression branch node
115      * @return Cursor over candidates satisfying disjunction expression
116      * @throws Exception on db access failures
117      */
118     private IndexCursor<?,ServerEntry> buildOrCursor( OrNode node ) throws Exception
119     {
120         List<ExprNode> children = node.getChildren();
121         List<IndexCursor<?,ServerEntry>> childCursors = new ArrayList<IndexCursor<?,ServerEntry>>( children.size() );
122         List<Evaluator<? extends ExprNode, ServerEntry>> childEvaluators
123             = new ArrayList<Evaluator<? extends ExprNode, ServerEntry>>( children.size() );
124 
125         // Recursively create Cursors and Evaluators for each child expression node
126         for ( ExprNode child : children )
127         {
128             childCursors.add( build( child ) );
129             childEvaluators.add( evaluatorBuilder.build( child ) );
130         }
131 
132         //noinspection unchecked
133         return new OrCursor( childCursors, childEvaluators );
134     }
135 
136 
137     /**
138      * Creates an AndCursor over a conjunction expression branch node.
139      *
140      * @param node a conjunction expression branch node
141      * @return Cursor over the conjunction expression
142      * @throws Exception on db access failures
143      */
144     private IndexCursor<?,ServerEntry> buildAndCursor( AndNode node ) throws Exception
145     {
146         int minIndex = 0;
147         long minValue = Long.MAX_VALUE;
148         //noinspection UnusedAssignment
149         long value = Long.MAX_VALUE;
150 
151         /*
152          * We scan the child nodes of a branch node searching for the child
153          * expression node with the smallest scan count.  This is the child
154          * we will use for iteration by creating a Cursor over its expression.
155          */
156         final List<ExprNode> children = node.getChildren();
157         
158         for ( int ii = 0; ii < children.size(); ii++ )
159         {
160             ExprNode child = children.get( ii );
161             Object count = child.get( "count" );
162             if( count == null )
163             {
164                 continue;
165             }
166             value = ( Long ) count;
167             minValue = Math.min( minValue, value );
168 
169             if ( minValue == value )
170             {
171                 minIndex = ii;
172             }
173         }
174 
175         // Once found we build the child Evaluators minus the one for the minChild
176         ExprNode minChild = children.get( minIndex );
177         List<Evaluator<? extends ExprNode, ServerEntry>> childEvaluators =
178             new ArrayList<Evaluator<? extends ExprNode, ServerEntry>>( children.size() - 1 );
179         for ( ExprNode child : children )
180         {
181             if ( child == minChild )
182             {
183                 continue;
184             }
185 
186             childEvaluators.add( evaluatorBuilder.build( child ) );
187         }
188 
189         // Do recursive call to build min child Cursor then create AndCursor
190         IndexCursor<?,ServerEntry> childCursor = build( minChild );
191         return new AndCursor( childCursor, childEvaluators );
192     }
193 }