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.HashSet; 026import java.util.List; 027import java.util.Set; 028 029import org.apache.directory.api.ldap.model.constants.Loggers; 030import org.apache.directory.api.ldap.model.cursor.Cursor; 031import org.apache.directory.api.ldap.model.cursor.CursorException; 032import org.apache.directory.api.ldap.model.cursor.InvalidCursorPositionException; 033import org.apache.directory.api.ldap.model.exception.LdapException; 034import org.apache.directory.api.ldap.model.filter.ExprNode; 035import org.apache.directory.server.core.api.partition.PartitionTxn; 036import org.apache.directory.server.i18n.I18n; 037import org.apache.directory.server.xdbm.AbstractIndexCursor; 038import org.apache.directory.server.xdbm.IndexEntry; 039import org.apache.directory.server.xdbm.search.Evaluator; 040import org.slf4j.Logger; 041import org.slf4j.LoggerFactory; 042 043 044/** 045 * A Cursor returning candidates satisfying a logical disjunction expression. 046 * 047 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 048 */ 049public class OrCursor<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 private static final String UNSUPPORTED_MSG = I18n.err( I18n.ERR_722 ); 058 private final List<Cursor<IndexEntry<V, String>>> cursors; 059 private final List<Evaluator<? extends ExprNode>> evaluators; 060 private final List<Set<String>> blacklists; 061 private int cursorIndex = -1; 062 063 /** The candidate we have fetched in the next/previous call */ 064 private IndexEntry<V, String> prefetched; 065 066 067 /** 068 * Creates a new instance of an OrCursor 069 * 070 * @param partitionTxn The transaction to use 071 * @param cursors The encapsulated Cursors 072 * @param evaluators The list of evaluators associated with the elements 073 */ 074 // TODO - do same evaluator fail fast optimization that we do in AndCursor 075 public OrCursor( PartitionTxn partitionTxn, List<Cursor<IndexEntry<V, String>>> cursors, 076 List<Evaluator<? extends ExprNode>> evaluators ) 077 { 078 if ( IS_DEBUG ) 079 { 080 LOG_CURSOR.debug( "Creating OrCursor {}", this ); 081 } 082 083 if ( cursors.size() <= 1 ) 084 { 085 throw new IllegalArgumentException( I18n.err( I18n.ERR_723 ) ); 086 } 087 088 this.cursors = cursors; 089 this.evaluators = evaluators; 090 this.blacklists = new ArrayList<>(); 091 this.partitionTxn = partitionTxn; 092 093 for ( int i = 0; i < cursors.size(); i++ ) 094 { 095 this.blacklists.add( new HashSet<String>() ); 096 } 097 098 this.cursorIndex = 0; 099 } 100 101 102 /** 103 * {@inheritDoc} 104 */ 105 protected String getUnsupportedMessage() 106 { 107 return UNSUPPORTED_MSG; 108 } 109 110 111 /** 112 * {@inheritDoc} 113 */ 114 public void beforeFirst() throws LdapException, CursorException 115 { 116 checkNotClosed(); 117 cursorIndex = 0; 118 cursors.get( cursorIndex ).beforeFirst(); 119 setAvailable( false ); 120 prefetched = null; 121 } 122 123 124 /** 125 * {@inheritDoc} 126 */ 127 public void afterLast() throws LdapException, CursorException 128 { 129 checkNotClosed(); 130 cursorIndex = cursors.size() - 1; 131 cursors.get( cursorIndex ).afterLast(); 132 setAvailable( false ); 133 prefetched = null; 134 } 135 136 137 /** 138 * {@inheritDoc} 139 */ 140 public boolean first() throws LdapException, CursorException 141 { 142 beforeFirst(); 143 144 return setAvailable( next() ); 145 } 146 147 148 /** 149 * {@inheritDoc} 150 */ 151 public boolean last() throws LdapException, CursorException 152 { 153 afterLast(); 154 155 return setAvailable( previous() ); 156 } 157 158 159 private boolean isBlackListed( String id ) 160 { 161 return blacklists.get( cursorIndex ).contains( id ); 162 } 163 164 165 /** 166 * The first sub-expression Cursor to advance to an entry adds the entry 167 * to the blacklists of other Cursors that might return that entry. 168 * 169 * @param indexEntry the index entry to blacklist 170 * @throws Exception if there are problems accessing underlying db 171 */ 172 private void blackListIfDuplicate( PartitionTxn partitionTxn, IndexEntry<?, String> indexEntry ) throws LdapException 173 { 174 for ( int ii = 0; ii < evaluators.size(); ii++ ) 175 { 176 if ( ii == cursorIndex ) 177 { 178 continue; 179 } 180 181 if ( evaluators.get( ii ).evaluate( partitionTxn, indexEntry ) ) 182 { 183 blacklists.get( ii ).add( indexEntry.getId() ); 184 } 185 } 186 } 187 188 189 /** 190 * {@inheritDoc} 191 */ 192 @Override 193 public boolean previous() throws LdapException, CursorException 194 { 195 while ( cursors.get( cursorIndex ).previous() ) 196 { 197 checkNotClosed(); 198 IndexEntry<V, String> candidate = cursors.get( cursorIndex ).get(); 199 200 if ( !isBlackListed( candidate.getId() ) ) 201 { 202 blackListIfDuplicate( partitionTxn, candidate ); 203 204 prefetched = candidate; 205 return setAvailable( true ); 206 } 207 } 208 209 while ( cursorIndex > 0 ) 210 { 211 checkNotClosed(); 212 cursorIndex--; 213 cursors.get( cursorIndex ).afterLast(); 214 215 while ( cursors.get( cursorIndex ).previous() ) 216 { 217 checkNotClosed(); 218 IndexEntry<V, String> candidate = cursors.get( cursorIndex ).get(); 219 220 if ( !isBlackListed( candidate.getId() ) ) 221 { 222 blackListIfDuplicate( partitionTxn, candidate ); 223 224 prefetched = candidate; 225 return setAvailable( true ); 226 } 227 } 228 } 229 230 prefetched = null; 231 232 return setAvailable( false ); 233 } 234 235 236 /** 237 * {@inheritDoc} 238 */ 239 @Override 240 public boolean next() throws LdapException, CursorException 241 { 242 while ( cursors.get( cursorIndex ).next() ) 243 { 244 checkNotClosed(); 245 IndexEntry<V, String> candidate = cursors.get( cursorIndex ).get(); 246 247 if ( !isBlackListed( candidate.getId() ) ) 248 { 249 blackListIfDuplicate( partitionTxn, candidate ); 250 251 prefetched = candidate; 252 253 return setAvailable( true ); 254 } 255 } 256 257 while ( cursorIndex < cursors.size() - 1 ) 258 { 259 checkNotClosed(); 260 cursorIndex++; 261 cursors.get( cursorIndex ).beforeFirst(); 262 263 while ( cursors.get( cursorIndex ).next() ) 264 { 265 checkNotClosed(); 266 IndexEntry<V, String> candidate = cursors.get( cursorIndex ).get(); 267 268 if ( !isBlackListed( candidate.getId() ) ) 269 { 270 blackListIfDuplicate( partitionTxn, candidate ); 271 272 prefetched = candidate; 273 274 return setAvailable( true ); 275 } 276 } 277 } 278 279 prefetched = null; 280 281 return setAvailable( false ); 282 } 283 284 285 /** 286 * {@inheritDoc} 287 */ 288 public IndexEntry<V, String> get() throws CursorException 289 { 290 checkNotClosed(); 291 292 if ( available() ) 293 { 294 return prefetched; 295 } 296 297 throw new InvalidCursorPositionException( I18n.err( I18n.ERR_708 ) ); 298 } 299 300 301 /** 302 * {@inheritDoc} 303 */ 304 @Override 305 public void close() throws IOException 306 { 307 if ( IS_DEBUG ) 308 { 309 LOG_CURSOR.debug( "Closing OrCursor {}", this ); 310 } 311 312 super.close(); 313 314 for ( Cursor<?> cursor : cursors ) 315 { 316 cursor.close(); 317 } 318 } 319 320 321 /** 322 * {@inheritDoc} 323 */ 324 @Override 325 public void close( Exception cause ) throws IOException 326 { 327 if ( IS_DEBUG ) 328 { 329 LOG_CURSOR.debug( "Closing OrCursor {}", this ); 330 } 331 332 super.close( cause ); 333 334 for ( Cursor<?> cursor : cursors ) 335 { 336 cursor.close( cause ); 337 } 338 } 339 340 341 /** 342 * Dumps the evaluators 343 */ 344 private String dumpEvaluators( String tabs ) 345 { 346 StringBuilder sb = new StringBuilder(); 347 348 for ( Evaluator<? extends ExprNode> evaluator : evaluators ) 349 { 350 sb.append( evaluator.toString( tabs + " >>" ) ); 351 } 352 353 return sb.toString(); 354 } 355 356 357 /** 358 * Dumps the cursors 359 */ 360 private String dumpCursors( String tabs ) 361 { 362 StringBuilder sb = new StringBuilder(); 363 364 for ( Cursor<IndexEntry<V, String>> cursor : cursors ) 365 { 366 sb.append( cursor.toString( tabs + " " ) ); 367 sb.append( "\n" ); 368 } 369 370 return sb.toString(); 371 } 372 373 374 /** 375 * @see Object#toString() 376 */ 377 @Override 378 public String toString( String tabs ) 379 { 380 StringBuilder sb = new StringBuilder(); 381 382 sb.append( tabs ).append( "OrCursor (" ); 383 384 if ( available() ) 385 { 386 sb.append( "available)" ); 387 } 388 else 389 { 390 sb.append( "absent)" ); 391 } 392 393 sb.append( "#" ).append( cursorIndex ).append( " : \n" ); 394 395 if ( ( evaluators != null ) && !evaluators.isEmpty() ) 396 { 397 sb.append( dumpEvaluators( tabs ) ); 398 } 399 400 if ( ( cursors != null ) && !cursors.isEmpty() ) 401 { 402 sb.append( dumpCursors( tabs ) ).append( '\n' ); 403 } 404 405 return sb.toString(); 406 } 407 408 409 /** 410 * @see Object#toString() 411 */ 412 public String toString() 413 { 414 return toString( "" ); 415 } 416}