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.core.partition.avl; 021 022 023 import org.apache.directory.server.core.avltree.AvlSingletonOrOrderedSetCursor; 024 import org.apache.directory.server.core.avltree.AvlTree; 025 import org.apache.directory.server.core.avltree.AvlTreeCursor; 026 import org.apache.directory.server.core.avltree.SingletonOrOrderedSet; 027 import org.apache.directory.server.xdbm.AbstractTupleCursor; 028 import org.apache.directory.server.xdbm.Tuple; 029 import org.apache.directory.shared.ldap.cursor.Cursor; 030 import org.apache.directory.shared.ldap.cursor.InvalidCursorPositionException; 031 import org.apache.directory.shared.ldap.cursor.SingletonCursor; 032 import org.slf4j.Logger; 033 import org.slf4j.LoggerFactory; 034 035 036 /** 037 * A Cursor which walks and advance over AvlTables that may contain duplicate 038 * keys with values stored in an AvlTree. All duplicate keys are traversed 039 * returning the key and the value in a Tuple. 040 * 041 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 042 * @version $Rev$, $Date$ 043 */ 044 public class AvlTableDupsCursor<K,V> extends AbstractTupleCursor<K, V> 045 { 046 private static final Logger LOG = LoggerFactory.getLogger( AvlTableDupsCursor.class.getSimpleName() ); 047 048 /** The AVL backed table this Cursor traverses over. */ 049 private final AvlTable<K,V> table; 050 051 /** 052 * The underlying wrapped cursor which returns Tuples whose values are 053 * either V objects or AvlTree objects. 054 */ 055 private final AvlSingletonOrOrderedSetCursor<K, V> wrappedCursor; 056 057 /** 058 * A Cursor over a set of value objects for the current key held in the 059 * containerTuple. A new Cursor will be set for each new key as we 060 * traverse. The Cursor traverses over either a AvlTree object full 061 * of values in a multi-valued key or it traverses over a BTree which 062 * contains the values in the key field of it's Tuples. 063 */ 064 private Cursor<V> dupsCursor; 065 066 /** The current Tuple returned from the wrapped cursor. */ 067 private final Tuple<K,SingletonOrOrderedSet<V>> wrappedTuple = new Tuple<K, SingletonOrOrderedSet<V>>(); 068 069 /** 070 * The Tuple that is used to return values via the get() method. This 071 * same Tuple instance will be returned every time. At different 072 * positions it may return different values for the same key. 073 */ 074 private final Tuple<K,V> returnedTuple = new Tuple<K,V>(); 075 076 /** Whether or not a value is available when get() is called. */ 077 private boolean valueAvailable; 078 079 080 /** 081 * Creates a new instance of AvlTableDupsCursor. 082 * 083 * @param table the AvlTable to build a Cursor on. 084 */ 085 public AvlTableDupsCursor( AvlTable<K,V> table ) 086 { 087 this.table = table; 088 this.wrappedCursor = new AvlSingletonOrOrderedSetCursor<K, V>( table.getAvlTreeMap() ); 089 LOG.debug( "Created on table {}", table.getName() ); 090 } 091 092 093 /** 094 * {@inheritDoc} 095 */ 096 public boolean available() 097 { 098 return valueAvailable; 099 } 100 101 102 /** 103 * {@inheritDoc} 104 */ 105 public void beforeKey( K key ) throws Exception 106 { 107 beforeValue( key, null ); 108 } 109 110 111 /** 112 * {@inheritDoc} 113 */ 114 public void beforeValue( K key, V value ) throws Exception 115 { 116 checkNotClosed( "beforeValue()" ); 117 wrappedCursor.beforeKey( key ); 118 119 if ( wrappedCursor.next() ) 120 { 121 wrappedTuple.setBoth( wrappedCursor.get() ); 122 123 if ( wrappedTuple.getValue().isOrderedSet() ) 124 { 125 AvlTree<V> avlTree = wrappedTuple.getValue().getOrderedSet(); 126 dupsCursor = new AvlTreeCursor<V>( avlTree ); 127 } 128 else 129 { 130 dupsCursor = new SingletonCursor<V>( 131 wrappedTuple.getValue().getSingleton(), wrappedCursor.getValuComparator() ); 132 } 133 134 if ( value == null ) 135 { 136 clearValue(); 137 return; 138 } 139 140 /* 141 * The cursor over the values is only advanced if we're on the 142 * same key as the primary cursor. This is because we want this 143 * method to really position us within a set of duplicate key 144 * entries at the proper value. 145 */ 146 if ( table.getKeyComparator().compare( wrappedTuple.getKey(), key ) == 0 ) 147 { 148 dupsCursor.before( value ); 149 } 150 151 clearValue(); 152 return; 153 } 154 155 clearValue(); 156 wrappedTuple.setKey( null ); 157 wrappedTuple.setValue( null ); 158 } 159 160 161 /** 162 * {@inheritDoc} 163 */ 164 public void afterKey( K key ) throws Exception 165 { 166 afterValue( key, null ); 167 } 168 169 170 /** 171 * {@inheritDoc} 172 */ 173 public void afterValue( K key, V value ) throws Exception 174 { 175 checkNotClosed( "afterValue()" ); 176 /* 177 * There is a subtle difference between after and before handling 178 * with dupicate key values. Say we have the following tuples: 179 * 180 * (0, 0) 181 * (1, 1) 182 * (1, 2) 183 * (1, 3) 184 * (2, 2) 185 * 186 * If we request an after cursor on (1, 2). We must make sure that 187 * the container cursor does not advance after the entry with key 1 188 * since this would result in us skip returning (1. 3) on the call to 189 * next which will incorrectly return (2, 2) instead. 190 * 191 * So if the value is null in the element then we don't care about 192 * this obviously since we just want to advance past the duplicate key 193 * values all together. But when it is not null, then we want to 194 * go right before this key instead of after it. 195 */ 196 197 if ( value == null ) 198 { 199 wrappedCursor.afterKey( key ); 200 } 201 else 202 { 203 wrappedCursor.beforeKey( key ); 204 } 205 206 if ( wrappedCursor.next() ) 207 { 208 wrappedTuple.setBoth( wrappedCursor.get() ); 209 SingletonOrOrderedSet<V> values = wrappedTuple.getValue(); 210 211 if ( values.isOrderedSet() ) 212 { 213 AvlTree<V> set = values.getOrderedSet(); 214 dupsCursor = new AvlTreeCursor<V>( set ); 215 } 216 else 217 { 218 dupsCursor = new SingletonCursor<V>( values.getSingleton(), wrappedCursor.getValuComparator() ); 219 } 220 221 if ( value == null ) 222 { 223 clearValue(); 224 return; 225 } 226 227 // only advance the dupsCursor if we're on same key 228 if ( table.getKeyComparator().compare( wrappedTuple.getKey(), key ) == 0 ) 229 { 230 dupsCursor.after( value ); 231 } 232 233 clearValue(); 234 return; 235 } 236 237 clearValue(); 238 wrappedTuple.setKey( null ); 239 wrappedTuple.setValue( null ); 240 } 241 242 243 /** 244 * {@inheritDoc} 245 */ 246 public void after( Tuple<K, V> element ) throws Exception 247 { 248 afterValue( element.getKey(), element.getValue() ); 249 } 250 251 252 /** 253 * {@inheritDoc} 254 */ 255 public void afterLast() throws Exception 256 { 257 checkNotClosed( "afterLast()" ); 258 clearValue(); 259 wrappedCursor.afterLast(); 260 wrappedTuple.setKey( null ); 261 wrappedTuple.setValue( null ); 262 dupsCursor = null; 263 } 264 265 266 /** 267 * {@inheritDoc} 268 */ 269 public void before( Tuple<K, V> element ) throws Exception 270 { 271 beforeValue( element.getKey(), element.getValue() ); 272 } 273 274 275 /** 276 * {@inheritDoc} 277 */ 278 public void beforeFirst() throws Exception 279 { 280 checkNotClosed( "beforeFirst()" ); 281 clearValue(); 282 wrappedCursor.beforeFirst(); 283 wrappedTuple.setKey( null ); 284 wrappedTuple.setValue( null ); 285 dupsCursor = null; 286 } 287 288 289 /** 290 * {@inheritDoc} 291 */ 292 public boolean first() throws Exception 293 { 294 checkNotClosed( "first()" ); 295 clearValue(); 296 dupsCursor = null; 297 298 if ( wrappedCursor.first() ) 299 { 300 wrappedTuple.setBoth( wrappedCursor.get() ); 301 SingletonOrOrderedSet<V> values = wrappedTuple.getValue(); 302 303 if ( values.isOrderedSet() ) 304 { 305 dupsCursor = new AvlTreeCursor<V>( values.getOrderedSet() ); 306 } 307 else 308 { 309 dupsCursor = new SingletonCursor<V>( values.getSingleton(), wrappedCursor.getValuComparator() ); 310 } 311 312 /* 313 * Since only tables with duplicate keys enabled use this 314 * cursor, entries must have at least one value, and therefore 315 * call to last() will always return true. 316 */ 317 dupsCursor.first(); 318 valueAvailable = true; 319 returnedTuple.setKey( wrappedTuple.getKey() ); 320 returnedTuple.setValue( dupsCursor.get() ); 321 return true; 322 } 323 324 return false; 325 } 326 327 328 /** 329 * {@inheritDoc} 330 */ 331 public Tuple<K, V> get() throws Exception 332 { 333 checkNotClosed( "get()" ); 334 335 if ( ! valueAvailable ) 336 { 337 throw new InvalidCursorPositionException(); 338 } 339 340 return returnedTuple; 341 } 342 343 344 /** 345 * {@inheritDoc} 346 */ 347 public boolean isElementReused() 348 { 349 return true; 350 } 351 352 353 /** 354 * {@inheritDoc} 355 */ 356 public boolean last() throws Exception 357 { 358 checkNotClosed( "last()" ); 359 clearValue(); 360 dupsCursor = null; 361 362 if ( wrappedCursor.last() ) 363 { 364 wrappedTuple.setBoth( wrappedCursor.get() ); 365 SingletonOrOrderedSet<V> values = wrappedTuple.getValue(); 366 367 if ( values.isOrderedSet() ) 368 { 369 dupsCursor = new AvlTreeCursor<V>( values.getOrderedSet() ); 370 } 371 else 372 { 373 dupsCursor = new SingletonCursor<V>( values.getSingleton(), wrappedCursor.getValuComparator() ); 374 } 375 376 /* 377 * Since only tables with duplicate keys enabled use this 378 * cursor, entries must have at least one value, and therefore 379 * call to last() will always return true. 380 */ 381 dupsCursor.last(); 382 valueAvailable = true; 383 returnedTuple.setKey( wrappedTuple.getKey() ); 384 returnedTuple.setValue( dupsCursor.get() ); 385 return true; 386 } 387 388 return false; 389 } 390 391 392 /** 393 * {@inheritDoc} 394 */ 395 public boolean next() throws Exception 396 { 397 checkNotClosed( "next()" ); 398 /* 399 * If the cursor over the values of the current key is null or is 400 * extinguished then we need to advance to the next key. 401 */ 402 if ( null == dupsCursor || ! dupsCursor.next() ) 403 { 404 /* 405 * If the wrappedCursor cursor has more elements we get the next 406 * key/AvlTree Tuple to work with and get a cursor over it. 407 */ 408 if ( wrappedCursor.next() ) 409 { 410 wrappedTuple.setBoth( wrappedCursor.get() ); 411 SingletonOrOrderedSet<V> values = wrappedTuple.getValue(); 412 413 if ( values.isOrderedSet()) 414 { 415 dupsCursor = new AvlTreeCursor<V>( values.getOrderedSet() ); 416 } 417 else 418 { 419 dupsCursor = new SingletonCursor<V>( values.getSingleton(), wrappedCursor.getValuComparator() ); 420 } 421 422 /* 423 * Since only tables with duplicate keys enabled use this 424 * cursor, entries must have at least one value, and therefore 425 * call to next() after bringing the cursor to beforeFirst() 426 * will always return true. 427 */ 428 dupsCursor.beforeFirst(); 429 dupsCursor.next(); 430 } 431 else 432 { 433 dupsCursor = null; 434 return false; 435 } 436 } 437 438 /* 439 * If we get to this point then cursor has more elements and 440 * wrappedTuple holds the Tuple containing the key and the 441 * AvlTree of values for that key which the Cursor traverses. All we 442 * need to do is populate our tuple object with the key and the value 443 * in the cursor. 444 */ 445 returnedTuple.setKey( wrappedTuple.getKey() ); 446 returnedTuple.setValue( dupsCursor.get() ); 447 return valueAvailable = true; 448 } 449 450 451 /** 452 * {@inheritDoc} 453 */ 454 public boolean previous() throws Exception 455 { 456 checkNotClosed( "previous()" ); 457 /* 458 * If the cursor over the values of the current key is null or is 459 * extinguished then we need to advance to the previous key. 460 */ 461 if ( null == dupsCursor || ! dupsCursor.previous() ) 462 { 463 /* 464 * If the wrappedCursor cursor has more elements we get the previous 465 * key/AvlTree Tuple to work with and get a cursor over it's 466 * values. 467 */ 468 if ( wrappedCursor.previous() ) 469 { 470 wrappedTuple.setBoth( wrappedCursor.get() ); 471 SingletonOrOrderedSet<V> values = wrappedTuple.getValue(); 472 473 if ( values.isOrderedSet() ) 474 { 475 dupsCursor = new AvlTreeCursor<V>( values.getOrderedSet() ); 476 } 477 else 478 { 479 dupsCursor = new SingletonCursor<V>( values.getSingleton(), wrappedCursor.getValuComparator() ); 480 } 481 482 /* 483 * Since only tables with duplicate keys enabled use this 484 * cursor, entries must have at least one value, and therefore 485 * call to previous() after bringing the cursor to afterLast() 486 * will always return true. 487 */ 488 dupsCursor.afterLast(); 489 dupsCursor.previous(); 490 } 491 else 492 { 493 dupsCursor = null; 494 return false; 495 } 496 } 497 498 returnedTuple.setKey( wrappedTuple.getKey() ); 499 returnedTuple.setValue( dupsCursor.get() ); 500 return valueAvailable = true; 501 } 502 503 504 /** 505 * Clears the returned Tuple and makes sure valueAvailable returns false. 506 */ 507 private void clearValue() 508 { 509 returnedTuple.setKey( null ); 510 returnedTuple.setValue( null ); 511 valueAvailable = false; 512 } 513 }