001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 * 019 */ 020 package org.apache.directory.server.xdbm.search.impl; 021 022 023 import java.util.ArrayList; 024 import java.util.Collections; 025 import java.util.Comparator; 026 import java.util.List; 027 028 import org.apache.directory.server.xdbm.IndexEntry; 029 import org.apache.directory.server.xdbm.AbstractIndexCursor; 030 import org.apache.directory.server.xdbm.IndexCursor; 031 import org.apache.directory.server.xdbm.search.Evaluator; 032 import org.apache.directory.server.i18n.I18n; 033 import org.apache.directory.shared.ldap.cursor.InvalidCursorPositionException; 034 import org.apache.directory.shared.ldap.entry.ServerEntry; 035 import org.apache.directory.shared.ldap.filter.ExprNode; 036 037 038 /** 039 * A Cursor returning candidates satisfying a logical conjunction expression. 040 * 041 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 042 * @version $Rev$ 043 */ 044 public class AndCursor<V, ID> extends AbstractIndexCursor<V, ServerEntry, ID> 045 { 046 private static final String UNSUPPORTED_MSG = I18n.err( I18n.ERR_707 ); 047 private final IndexCursor<V, ServerEntry, ID> wrapped; 048 private final List<Evaluator<? extends ExprNode, ServerEntry, ID>> evaluators; 049 private boolean available = false; 050 051 052 public AndCursor( IndexCursor<V, ServerEntry, ID> wrapped, 053 List<Evaluator<? extends ExprNode, ServerEntry, ID>> evaluators ) 054 { 055 this.wrapped = wrapped; 056 this.evaluators = optimize( evaluators ); 057 } 058 059 060 public boolean available() 061 { 062 return available; 063 } 064 065 066 public void beforeValue( ID id, V value ) 067 { 068 throw new UnsupportedOperationException( UNSUPPORTED_MSG ); 069 } 070 071 072 public void afterValue( ID id, V value ) 073 { 074 throw new UnsupportedOperationException( UNSUPPORTED_MSG ); 075 } 076 077 078 public void before( IndexEntry<V, ServerEntry, ID> element ) throws Exception 079 { 080 throw new UnsupportedOperationException( UNSUPPORTED_MSG ); 081 } 082 083 084 public void after( IndexEntry<V, ServerEntry, ID> element ) throws Exception 085 { 086 throw new UnsupportedOperationException( UNSUPPORTED_MSG ); 087 } 088 089 090 public void beforeFirst() throws Exception 091 { 092 checkNotClosed( "beforeFirst()" ); 093 wrapped.beforeFirst(); 094 available = false; 095 } 096 097 098 public void afterLast() throws Exception 099 { 100 checkNotClosed( "afterLast()" ); 101 wrapped.afterLast(); 102 available = false; 103 } 104 105 106 public boolean first() throws Exception 107 { 108 beforeFirst(); 109 return next(); 110 } 111 112 113 public boolean last() throws Exception 114 { 115 afterLast(); 116 return previous(); 117 } 118 119 120 public boolean previous() throws Exception 121 { 122 while ( wrapped.previous() ) 123 { 124 checkNotClosed( "previous()" ); 125 126 IndexEntry<?, ServerEntry, ID> candidate = wrapped.get(); 127 if ( matches( candidate ) ) 128 { 129 return available = true; 130 } 131 } 132 133 return available = false; 134 } 135 136 137 public boolean next() throws Exception 138 { 139 while ( wrapped.next() ) 140 { 141 checkNotClosed( "next()" ); 142 IndexEntry<?, ServerEntry, ID> candidate = wrapped.get(); 143 if ( matches( candidate ) ) 144 { 145 return available = true; 146 } 147 } 148 149 return available = false; 150 } 151 152 153 public IndexEntry<V, ServerEntry, ID> get() throws Exception 154 { 155 checkNotClosed( "get()" ); 156 if ( available ) 157 { 158 return wrapped.get(); 159 } 160 161 throw new InvalidCursorPositionException( I18n.err( I18n.ERR_708 ) ); 162 } 163 164 165 public boolean isElementReused() 166 { 167 return wrapped.isElementReused(); 168 } 169 170 171 public void close() throws Exception 172 { 173 super.close(); 174 wrapped.close(); 175 } 176 177 178 /** 179 * TODO - duplicate code from AndEvaluator just make utility for this and 180 * for the same code in the OrEvaluator once done. 181 * 182 * Takes a set of Evaluators and copies then sorts them in a new list with 183 * increasing scan counts on their expression nodes. This is done to have 184 * the Evaluators with the least scan count which have the highest 185 * probability of rejecting a candidate first. That will increase the 186 * chance of shorting the checks on evaluators early so extra lookups and 187 * comparisons are avoided. 188 * 189 * @param unoptimized the unoptimized list of Evaluators 190 * @return optimized Evaluator list with increasing scan count ordering 191 */ 192 private List<Evaluator<? extends ExprNode, ServerEntry, ID>> optimize( 193 List<Evaluator<? extends ExprNode, ServerEntry, ID>> unoptimized ) 194 { 195 List<Evaluator<? extends ExprNode, ServerEntry, ID>> optimized = new ArrayList<Evaluator<? extends ExprNode, ServerEntry, ID>>( 196 unoptimized.size() ); 197 optimized.addAll( unoptimized ); 198 199 Collections.sort( optimized, new Comparator<Evaluator<?, ServerEntry, ID>>() 200 { 201 public int compare( Evaluator<?, ServerEntry, ID> e1, Evaluator<?, ServerEntry, ID> e2 ) 202 { 203 long scanCount1 = ( Long ) e1.getExpression().get( "count" ); 204 long scanCount2 = ( Long ) e2.getExpression().get( "count" ); 205 206 if ( scanCount1 == scanCount2 ) 207 { 208 return 0; 209 } 210 211 /* 212 * We want the Evaluator with the smallest scan count first 213 * since this node has the highest probability of failing, or 214 * rather the least probability of succeeding. That way we 215 * can short the sub-expression evaluation process. 216 */ 217 if ( scanCount1 < scanCount2 ) 218 { 219 return -1; 220 } 221 222 return 1; 223 } 224 } ); 225 226 return optimized; 227 } 228 229 230 private boolean matches( IndexEntry<?, ServerEntry, ID> indexEntry ) throws Exception 231 { 232 for ( Evaluator<?, ServerEntry, ID> evaluator : evaluators ) 233 { 234 if ( !evaluator.evaluate( indexEntry ) ) 235 { 236 return false; 237 } 238 } 239 240 return true; 241 } 242 }