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 */ 020package org.apache.directory.server.xdbm.search.cursor; 021 022 023import java.io.IOException; 024import java.util.ArrayList; 025import java.util.Collections; 026import java.util.List; 027 028import org.apache.directory.api.ldap.model.constants.Loggers; 029import org.apache.directory.api.ldap.model.cursor.Cursor; 030import org.apache.directory.api.ldap.model.cursor.CursorException; 031import org.apache.directory.api.ldap.model.cursor.InvalidCursorPositionException; 032import org.apache.directory.api.ldap.model.exception.LdapException; 033import org.apache.directory.api.ldap.model.filter.ExprNode; 034import org.apache.directory.server.core.api.partition.PartitionTxn; 035import org.apache.directory.server.i18n.I18n; 036import org.apache.directory.server.xdbm.AbstractIndexCursor; 037import org.apache.directory.server.xdbm.IndexEntry; 038import org.apache.directory.server.xdbm.search.Evaluator; 039import org.apache.directory.server.xdbm.search.impl.ScanCountComparator; 040import org.slf4j.Logger; 041import org.slf4j.LoggerFactory; 042 043 044/** 045 * A Cursor returning candidates satisfying a logical conjunction expression. 046 * 047 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 048 */ 049public class AndCursor<V> extends AbstractIndexCursor<V> 050{ 051 /** A dedicated log for cursors */ 052 private static final Logger LOG_CURSOR = LoggerFactory.getLogger( Loggers.CURSOR_LOG.getName() ); 053 054 /** Speedup for logs */ 055 private static final boolean IS_DEBUG = LOG_CURSOR.isDebugEnabled(); 056 057 /** The message for unsupported operations */ 058 private static final String UNSUPPORTED_MSG = I18n.err( I18n.ERR_707 ); 059 060 /** */ 061 private final Cursor<IndexEntry<V, String>> wrapped; 062 063 /** The evaluators used for the members of the And filter */ 064 private final List<Evaluator<? extends ExprNode>> evaluators; 065 066 067 /** 068 * Creates an instance of a AndCursor. It wraps an index cursor and the list 069 * of evaluators associated with all the elements connected by the And. 070 * 071 * @param partitionTxn The transaction to use 072 * @param wrapped The encapsulated IndexCursor 073 * @param evaluators The list of evaluators associated with the elements 074 */ 075 public AndCursor( PartitionTxn partitionTxn, Cursor<IndexEntry<V, String>> wrapped, 076 List<Evaluator<? extends ExprNode>> evaluators ) 077 { 078 if ( IS_DEBUG ) 079 { 080 LOG_CURSOR.debug( "Creating AndCursor {}", this ); 081 } 082 083 this.wrapped = wrapped; 084 this.evaluators = optimize( evaluators ); 085 this.partitionTxn = partitionTxn; 086 } 087 088 089 /** 090 * {@inheritDoc} 091 */ 092 protected String getUnsupportedMessage() 093 { 094 return UNSUPPORTED_MSG; 095 } 096 097 098 /** 099 * {@inheritDoc} 100 */ 101 public void beforeFirst() throws LdapException, CursorException 102 { 103 checkNotClosed(); 104 wrapped.beforeFirst(); 105 setAvailable( false ); 106 } 107 108 109 /** 110 * {@inheritDoc} 111 */ 112 public void afterLast() throws LdapException, CursorException 113 { 114 checkNotClosed(); 115 wrapped.afterLast(); 116 setAvailable( false ); 117 } 118 119 120 /** 121 * {@inheritDoc} 122 */ 123 public boolean first() throws LdapException, CursorException 124 { 125 beforeFirst(); 126 127 return next(); 128 } 129 130 131 /** 132 * {@inheritDoc} 133 */ 134 public boolean last() throws LdapException, CursorException 135 { 136 afterLast(); 137 138 return previous(); 139 } 140 141 142 /** 143 * {@inheritDoc} 144 */ 145 public boolean previous( PartitionTxn partitionTxn ) throws LdapException, CursorException 146 { 147 while ( wrapped.previous() ) 148 { 149 checkNotClosed(); 150 151 IndexEntry<V, String> candidate = wrapped.get(); 152 153 if ( matches( partitionTxn, candidate ) ) 154 { 155 return setAvailable( true ); 156 } 157 } 158 159 return setAvailable( false ); 160 } 161 162 163 /** 164 * {@inheritDoc} 165 */ 166 public boolean next( PartitionTxn partitionTxn ) throws LdapException, CursorException 167 { 168 while ( wrapped.next() ) 169 { 170 checkNotClosed(); 171 IndexEntry<V, String> candidate = wrapped.get(); 172 173 if ( matches( partitionTxn, candidate ) ) 174 { 175 return setAvailable( true ); 176 } 177 } 178 179 return setAvailable( false ); 180 } 181 182 183 /** 184 * {@inheritDoc} 185 */ 186 public IndexEntry<V, String> get() throws CursorException 187 { 188 checkNotClosed(); 189 190 if ( available() ) 191 { 192 return wrapped.get(); 193 } 194 195 throw new InvalidCursorPositionException( I18n.err( I18n.ERR_708 ) ); 196 } 197 198 199 /** 200 * {@inheritDoc} 201 */ 202 @Override 203 public void close() throws IOException 204 { 205 if ( IS_DEBUG ) 206 { 207 LOG_CURSOR.debug( "Closing AndCursor {}", this ); 208 } 209 210 super.close(); 211 wrapped.close(); 212 } 213 214 215 /** 216 * {@inheritDoc} 217 */ 218 @Override 219 public void close( Exception cause ) throws IOException 220 { 221 if ( IS_DEBUG ) 222 { 223 LOG_CURSOR.debug( "Closing AndCursor {}", this ); 224 } 225 226 super.close( cause ); 227 wrapped.close( cause ); 228 } 229 230 231 /** 232 * Takes a set of Evaluators and copies then sorts them in a new list with 233 * increasing scan counts on their expression nodes. This is done to have 234 * the Evaluators with the least scan count which have the highest 235 * probability of rejecting a candidate first. That will increase the 236 * chance of shorting the checks on evaluators early so extra lookups and 237 * comparisons are avoided. 238 * 239 * @param unoptimized the unoptimized list of Evaluators 240 * @return optimized Evaluator list with increasing scan count ordering 241 */ 242 private List<Evaluator<? extends ExprNode>> optimize( 243 List<Evaluator<? extends ExprNode>> unoptimized ) 244 { 245 List<Evaluator<? extends ExprNode>> optimized = new ArrayList<>( 246 unoptimized.size() ); 247 optimized.addAll( unoptimized ); 248 249 Collections.sort( optimized, new ScanCountComparator() ); 250 251 return optimized; 252 } 253 254 255 /** 256 * Checks if the entry is a valid candidate by using the evaluators. 257 */ 258 private boolean matches( PartitionTxn partitionTxn, IndexEntry<V, String> indexEntry ) throws LdapException 259 { 260 for ( Evaluator<?> evaluator : evaluators ) 261 { 262 if ( !evaluator.evaluate( partitionTxn, indexEntry ) ) 263 { 264 return false; 265 } 266 } 267 268 return true; 269 } 270 271 272 /** 273 * Dumps the evaluators 274 */ 275 private String dumpEvaluators( String tabs ) 276 { 277 StringBuilder sb = new StringBuilder(); 278 279 for ( Evaluator<? extends ExprNode> evaluator : evaluators ) 280 { 281 sb.append( evaluator.toString( tabs + " >>" ) ); 282 } 283 284 return sb.toString(); 285 } 286 287 288 /** 289 * @see Object#toString() 290 */ 291 @Override 292 public String toString( String tabs ) 293 { 294 StringBuilder sb = new StringBuilder(); 295 296 sb.append( tabs ).append( "AndCursor (" ); 297 298 if ( available() ) 299 { 300 sb.append( "available) :\n" ); 301 } 302 else 303 { 304 sb.append( "absent) :\n" ); 305 } 306 307 if ( ( evaluators != null ) && !evaluators.isEmpty() ) 308 { 309 sb.append( dumpEvaluators( tabs ) ); 310 } 311 312 sb.append( wrapped.toString( tabs + " " ) ); 313 314 return sb.toString(); 315 } 316 317 318 /** 319 * @see Object#toString() 320 */ 321 public String toString() 322 { 323 return toString( "" ); 324 } 325}