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.shared.ldap.filter.OrNode;
24  import org.apache.directory.shared.ldap.filter.ExprNode;
25  import org.apache.directory.server.xdbm.IndexEntry;
26  import org.apache.directory.server.xdbm.search.Evaluator;
27  import org.apache.directory.server.core.entry.ServerEntry;
28  
29  import java.util.List;
30  import java.util.ArrayList;
31  import java.util.Collections;
32  import java.util.Comparator;
33  
34  
35  /**
36   * An Evaluator for logical disjunction (OR) expressions.
37   *
38   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
39   * @version $$Rev$$
40   */
41  public class OrEvaluator implements Evaluator<OrNode, ServerEntry>
42  {
43      private final List<Evaluator<? extends ExprNode, ServerEntry>> evaluators;
44  
45      private final OrNode node;
46  
47  
48      public OrEvaluator( OrNode node, List<Evaluator<? extends ExprNode, ServerEntry>> evaluators )
49      {
50          this.node = node;
51          this.evaluators = optimize( evaluators );
52      }
53  
54  
55      /**
56       * Takes a set of Evaluators and copies then sorts them in a new list with
57       * decreasing scan counts on their expression nodes.  This is done to have
58       * the Evaluators with the greatest scan counts which have the highest
59       * probability of accepting a candidate first.  That will increase the
60       * chance of shorting the checks on evaluators early so extra lookups and
61       * comparisons are avoided.
62       *
63       * @param unoptimized the unoptimized list of Evaluators
64       * @return optimized Evaluator list with decreasing scan count ordering
65       */
66      private List<Evaluator<? extends ExprNode,ServerEntry>>
67          optimize( List<Evaluator<? extends ExprNode, ServerEntry>> unoptimized )
68      {
69          List<Evaluator<? extends ExprNode, ServerEntry>> optimized =
70              new ArrayList<Evaluator<? extends ExprNode, ServerEntry>>( unoptimized.size() );
71          optimized.addAll( unoptimized );
72          Collections.sort( optimized, new Comparator<Evaluator<? extends ExprNode,ServerEntry>>()
73          {
74              public int compare( Evaluator<? extends ExprNode, ServerEntry> e1, Evaluator<? extends ExprNode, ServerEntry> e2 )
75              {
76                  long scanCount1 = ( Long ) e1.getExpression().get( "count" );
77                  long scanCount2 = ( Long ) e2.getExpression().get( "count" );
78  
79                  if ( scanCount1 == scanCount2 )
80                  {
81                      return 0;
82                  }
83  
84                  /*
85                   * We want the Evaluator with the largest scan count first
86                   * since this node has the highest probability of accepting,
87                   * or rather the least probability of failing.  That way we
88                   * can short the sub-expression evaluation process.
89                   */
90                  if ( scanCount1 < scanCount2 )
91                  {
92                      return 1;
93                  }
94  
95                  return -1;
96              }
97          });
98  
99          return optimized;
100     }
101 
102 
103     public boolean evaluate( IndexEntry<?, ServerEntry> indexEntry ) throws Exception
104     {
105         for ( Evaluator<?,ServerEntry> evaluator : evaluators )
106         {
107             if ( evaluator.evaluate( indexEntry ) )
108             {
109                 return true;
110             }
111         }
112 
113         return false;
114     }
115 
116 
117     public boolean evaluate( Long id ) throws Exception
118     {
119         for ( Evaluator<?,ServerEntry> evaluator : evaluators )
120         {
121             if ( evaluator.evaluate( id ) )
122             {
123                 return true;
124             }
125         }
126 
127         return false;
128     }
129 
130 
131     public boolean evaluate( ServerEntry entry ) throws Exception
132     {
133         for ( Evaluator<?,ServerEntry> evaluator : evaluators )
134         {
135             if ( evaluator.evaluate( entry ) )
136             {
137                 return true;
138             }
139         }
140 
141         return false;
142     }
143 
144 
145     public OrNode getExpression()
146     {
147         return node;
148     }
149 }