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.ArrayDeque; 025 026import org.apache.directory.api.ldap.model.constants.Loggers; 027import org.apache.directory.api.ldap.model.cursor.Cursor; 028import org.apache.directory.api.ldap.model.cursor.CursorException; 029import org.apache.directory.api.ldap.model.exception.LdapException; 030import org.apache.directory.api.ldap.model.name.Rdn; 031import org.apache.directory.server.core.api.partition.PartitionTxn; 032import org.apache.directory.server.i18n.I18n; 033import org.apache.directory.server.xdbm.AbstractIndexCursor; 034import org.apache.directory.server.xdbm.IndexEntry; 035import org.apache.directory.server.xdbm.ParentIdAndRdn; 036import org.apache.directory.server.xdbm.Store; 037import org.slf4j.Logger; 038import org.slf4j.LoggerFactory; 039 040 041/** 042 * A Cursor over entries satisfying one level scope constraints with alias 043 * dereferencing considerations when enabled during search. 044 * We use the Rdn index to fetch all the descendants of a given entry. 045 * 046 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 047 */ 048public class DescendantCursor extends AbstractIndexCursor<String> 049{ 050 /** A dedicated log for cursors */ 051 private static final Logger LOG_CURSOR = LoggerFactory.getLogger( Loggers.CURSOR_LOG.getName() ); 052 053 /** Speedup for logs */ 054 private static final boolean IS_DEBUG = LOG_CURSOR.isDebugEnabled(); 055 056 /** Error message for unsupported operations */ 057 private static final String UNSUPPORTED_MSG = I18n.err( I18n.ERR_719 ); 058 059 /** The entry database/store */ 060 private final Store db; 061 062 /** The prefetched element */ 063 private IndexEntry prefetched; 064 065 /** The current Cursor over the entries in the scope of the search base */ 066 private Cursor<IndexEntry<ParentIdAndRdn, String>> currentCursor; 067 068 /** The current Parent ID */ 069 private String currentParentId; 070 071 /** The stack of cursors used to process the depth-first traversal */ 072 private ArrayDeque<Cursor> cursorStack; 073 074 /** The stack of parentIds used to process the depth-first traversal */ 075 private ArrayDeque<String> parentIdStack; 076 077 /** The initial entry ID we are looking descendants for */ 078 private String baseId; 079 080 /** A flag to tell that we are in the top level cursor or not */ 081 private boolean topLevel; 082 083 protected static final boolean TOP_LEVEL = true; 084 protected static final boolean INNER = false; 085 086 087 /** 088 * Creates a Cursor over entries satisfying one level scope criteria. 089 * 090 * @param partitionTxn The transaction to use 091 * @param db the entry store 092 * @param baseId The base ID 093 * @param parentId The parent ID 094 * @param cursor The wrapped cursor 095 */ 096 public DescendantCursor( PartitionTxn partitionTxn, Store db, String baseId, String parentId, 097 Cursor<IndexEntry<ParentIdAndRdn, String>> cursor ) 098 { 099 this( partitionTxn, db, baseId, parentId, cursor, TOP_LEVEL ); 100 } 101 102 103 /** 104 * Creates a Cursor over entries satisfying one level scope criteria. 105 * 106 * @param partitionTxn The transaction to use 107 * @param db the entry store 108 * @param baseId The base ID 109 * @param parentId The parent ID 110 * @param cursor The wrapped cursor 111 * @param topLevel If we are at the top level 112 */ 113 public DescendantCursor( PartitionTxn partitionTxn, Store db, String baseId, String parentId, 114 Cursor<IndexEntry<ParentIdAndRdn, String>> cursor, boolean topLevel ) 115 { 116 this.db = db; 117 currentParentId = parentId; 118 currentCursor = cursor; 119 cursorStack = new ArrayDeque(); 120 parentIdStack = new ArrayDeque(); 121 this.baseId = baseId; 122 this.topLevel = topLevel; 123 this.partitionTxn = partitionTxn; 124 125 if ( IS_DEBUG ) 126 { 127 LOG_CURSOR.debug( "Creating ChildrenCursor {}", this ); 128 } 129 } 130 131 132 /** 133 * {@inheritDoc} 134 */ 135 @Override 136 protected String getUnsupportedMessage() 137 { 138 return UNSUPPORTED_MSG; 139 } 140 141 142 /** 143 * {@inheritDoc} 144 */ 145 @Override 146 public void beforeFirst() throws LdapException, CursorException 147 { 148 checkNotClosed(); 149 setAvailable( false ); 150 } 151 152 153 /** 154 * {@inheritDoc} 155 */ 156 @Override 157 public void afterLast() throws LdapException, CursorException 158 { 159 throw new UnsupportedOperationException( getUnsupportedMessage() ); 160 } 161 162 163 /** 164 * {@inheritDoc} 165 */ 166 @Override 167 public boolean first() throws LdapException, CursorException 168 { 169 beforeFirst(); 170 171 return next(); 172 } 173 174 175 /** 176 * {@inheritDoc} 177 */ 178 @Override 179 public boolean last() throws LdapException, CursorException 180 { 181 throw new UnsupportedOperationException( getUnsupportedMessage() ); 182 } 183 184 185 /** 186 * {@inheritDoc} 187 */ 188 @Override 189 public boolean previous() throws LdapException, CursorException 190 { 191 checkNotClosed(); 192 193 boolean hasPrevious = currentCursor.previous(); 194 195 if ( hasPrevious ) 196 { 197 IndexEntry entry = currentCursor.get(); 198 199 if ( ( ( ParentIdAndRdn ) entry.getTuple().getKey() ).getParentId().equals( currentParentId ) ) 200 { 201 prefetched = entry; 202 return true; 203 } 204 } 205 206 return false; 207 } 208 209 210 /** 211 * {@inheritDoc} 212 */ 213 @Override 214 public boolean next() throws LdapException, CursorException 215 { 216 checkNotClosed(); 217 boolean finished = false; 218 219 while ( !finished ) 220 { 221 boolean hasNext = currentCursor.next(); 222 223 // We will use a depth first approach. The alternative (Breadth-first) would be 224 // too memory consuming. 225 // The idea is to use a ChildrenCursor each time we have an entry with chidren, 226 // and process recursively. 227 if ( hasNext ) 228 { 229 IndexEntry cursorEntry = currentCursor.get(); 230 ParentIdAndRdn parentIdAndRdn = ( ( ParentIdAndRdn ) ( cursorEntry.getKey() ) ); 231 232 // Check that we aren't out of the cursor's limit 233 if ( !parentIdAndRdn.getParentId().equals( currentParentId ) ) 234 { 235 // Ok, we went too far. Unstack the cursor and return 236 finished = cursorStack.isEmpty(); 237 238 if ( !finished ) 239 { 240 try 241 { 242 currentCursor.close(); 243 } 244 catch ( IOException ioe ) 245 { 246 throw new LdapException( ioe.getMessage(), ioe ); 247 } 248 249 currentCursor = cursorStack.pop(); 250 currentParentId = parentIdStack.pop(); 251 } 252 253 // And continue... 254 } 255 else 256 { 257 // We have a candidate, it will be returned. 258 if ( topLevel ) 259 { 260 prefetched = new IndexEntry(); 261 prefetched.setId( cursorEntry.getId() ); 262 prefetched.setKey( baseId ); 263 } 264 else 265 { 266 prefetched = cursorEntry; 267 } 268 269 // Check if the current entry has children or not. 270 if ( parentIdAndRdn.getNbDescendants() > 0 ) 271 { 272 String newParentId = ( String ) cursorEntry.getId(); 273 274 // Yes, then create a new cursor and go down one level 275 Cursor<IndexEntry<ParentIdAndRdn, String>> cursor = db.getRdnIndex().forwardCursor( partitionTxn ); 276 277 IndexEntry<ParentIdAndRdn, String> startingPos = new IndexEntry<>(); 278 startingPos.setKey( new ParentIdAndRdn( newParentId, ( Rdn[] ) null ) ); 279 cursor.before( startingPos ); 280 281 cursorStack.push( currentCursor ); 282 parentIdStack.push( currentParentId ); 283 284 currentCursor = cursor; 285 currentParentId = newParentId; 286 } 287 288 return true; 289 } 290 } 291 else 292 { 293 // The current cursor has been exhausted. Get back to the parent's cursor. 294 finished = cursorStack.isEmpty(); 295 296 if ( !finished ) 297 { 298 try 299 { 300 currentCursor.close(); 301 } 302 catch ( IOException ioe ) 303 { 304 throw new LdapException( ioe.getMessage(), ioe ); 305 } 306 307 currentCursor = cursorStack.pop(); 308 currentParentId = parentIdStack.pop(); 309 } 310 // and continue... 311 } 312 } 313 314 return false; 315 } 316 317 318 /** 319 * {@inheritDoc} 320 */ 321 @Override 322 public IndexEntry<String, String> get() throws CursorException 323 { 324 checkNotClosed(); 325 326 return prefetched; 327 } 328 329 330 /** 331 * {@inheritDoc} 332 */ 333 @Override 334 public void close() throws IOException 335 { 336 if ( IS_DEBUG ) 337 { 338 LOG_CURSOR.debug( "Closing ChildrenCursor {}", this ); 339 } 340 341 // Close the cursors stored in the stack, if we have some 342 for ( Object cursor : cursorStack ) 343 { 344 ( ( Cursor<IndexEntry<?, ?>> ) cursor ).close(); 345 } 346 347 // And finally, close the current cursor 348 currentCursor.close(); 349 350 super.close(); 351 } 352 353 354 /** 355 * {@inheritDoc} 356 */ 357 @Override 358 public void close( Exception cause ) throws IOException 359 { 360 if ( IS_DEBUG ) 361 { 362 LOG_CURSOR.debug( "Closing ChildrenCursor {}", this ); 363 } 364 365 // Close the cursors stored in the stack, if we have some 366 for ( Object cursor : cursorStack ) 367 { 368 ( ( Cursor<IndexEntry<?, ?>> ) cursor ).close( cause ); 369 } 370 371 // And finally, close the current cursor 372 currentCursor.close( cause ); 373 374 super.close( cause ); 375 } 376 377 378 /** 379 * Dumps the cursors 380 */ 381 private String dumpCursors( String tabs ) 382 { 383 StringBuilder sb = new StringBuilder(); 384 385 for ( Object cursor : cursorStack ) 386 { 387 sb.append( ( ( Cursor<IndexEntry<ParentIdAndRdn, String>> ) cursor ).toString( tabs + " " ) ); 388 sb.append( "\n" ); 389 } 390 391 return sb.toString(); 392 } 393 394 395 /** 396 * @see Object#toString() 397 */ 398 @Override 399 public String toString( String tabs ) 400 { 401 StringBuilder sb = new StringBuilder(); 402 403 sb.append( tabs ).append( "DescendantCursor (" ); 404 405 if ( available() ) 406 { 407 sb.append( "available)" ); 408 } 409 else 410 { 411 sb.append( "absent)" ); 412 } 413 414 sb.append( "#baseId<" ).append( baseId ); 415 sb.append( ", " ).append( db ).append( "> :\n" ); 416 417 sb.append( dumpCursors( tabs + " " ) ); 418 419 if ( currentCursor != null ) 420 { 421 sb.append( tabs + " <current>\n" ); 422 sb.append( currentCursor.toString( tabs + " " ) ); 423 } 424 425 return sb.toString(); 426 } 427 428 429 /** 430 * @see Object#toString() 431 */ 432 @Override 433 public String toString() 434 { 435 return toString( "" ); 436 } 437}