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 }