001/* 002 * CDDL HEADER START 003 * 004 * The contents of this file are subject to the terms of the 005 * Common Development and Distribution License, Version 1.0 only 006 * (the "License"). You may not use this file except in compliance 007 * with the License. 008 * 009 * You can obtain a copy of the license at legal-notices/CDDLv1_0.txt 010 * or http://forgerock.org/license/CDDLv1.0.html. 011 * See the License for the specific language governing permissions 012 * and limitations under the License. 013 * 014 * When distributing Covered Code, include this CDDL HEADER in each 015 * file and include the License file at legal-notices/CDDLv1_0.txt. 016 * If applicable, add the following below this CDDL HEADER, with the 017 * fields enclosed by brackets "[]" replaced with your own identifying 018 * information: 019 * Portions Copyright [yyyy] [name of copyright owner] 020 * 021 * CDDL HEADER END 022 * 023 * 024 * Copyright 2009-2010 Sun Microsystems, Inc. 025 * Portions copyright 2012-2015 ForgeRock AS. 026 */ 027 028package org.forgerock.opendj.ldap; 029 030import java.util.Collection; 031import java.util.ConcurrentModificationException; 032import java.util.HashMap; 033import java.util.Iterator; 034import java.util.LinkedHashMap; 035import java.util.Map; 036import java.util.NoSuchElementException; 037 038import org.forgerock.i18n.LocalizedIllegalArgumentException; 039 040import org.forgerock.util.Reject; 041 042/** 043 * An implementation of the {@code Attribute} interface with predictable 044 * iteration order. 045 * <p> 046 * Internally, attribute values are stored in a linked list and it's this list 047 * which defines the iteration ordering, which is the order in which elements 048 * were inserted into the set (insertion-order). This ordering is particularly 049 * useful in LDAP where clients generally appreciate having things returned in 050 * the same order they were presented. 051 * <p> 052 * All operations are supported by this implementation. 053 */ 054public final class LinkedAttribute extends AbstractAttribute { 055 056 private static abstract class Impl { 057 058 abstract boolean add(LinkedAttribute attribute, ByteString value); 059 060 abstract void clear(LinkedAttribute attribute); 061 062 abstract boolean contains(LinkedAttribute attribute, ByteString value); 063 064 boolean containsAll(final LinkedAttribute attribute, final Collection<?> values) { 065 // TODO: could optimize if objects is a LinkedAttribute having the 066 // same equality matching rule. 067 for (final Object value : values) { 068 if (!contains(attribute, ByteString.valueOf(value))) { 069 return false; 070 } 071 } 072 return true; 073 } 074 075 abstract ByteString firstValue(LinkedAttribute attribute); 076 077 abstract Iterator<ByteString> iterator(LinkedAttribute attribute); 078 079 abstract boolean remove(LinkedAttribute attribute, ByteString value); 080 081 abstract <T> boolean retainAll(LinkedAttribute attribute, Collection<T> values, 082 Collection<? super T> missingValues); 083 084 abstract int size(LinkedAttribute attribute); 085 } 086 087 private static final class MultiValueImpl extends Impl { 088 089 @Override 090 boolean add(final LinkedAttribute attribute, final ByteString value) { 091 final ByteString normalizedValue = normalizeValue(attribute, value); 092 return attribute.multipleValues.put(normalizedValue, value) == null; 093 } 094 095 @Override 096 void clear(final LinkedAttribute attribute) { 097 attribute.multipleValues = null; 098 attribute.pimpl = ZERO_VALUE_IMPL; 099 } 100 101 @Override 102 boolean contains(final LinkedAttribute attribute, final ByteString value) { 103 return attribute.multipleValues.containsKey(normalizeValue(attribute, value)); 104 } 105 106 @Override 107 ByteString firstValue(final LinkedAttribute attribute) { 108 return attribute.multipleValues.values().iterator().next(); 109 } 110 111 @Override 112 Iterator<ByteString> iterator(final LinkedAttribute attribute) { 113 return new Iterator<ByteString>() { 114 private Impl expectedImpl = MULTI_VALUE_IMPL; 115 116 private Iterator<ByteString> iterator = attribute.multipleValues.values() 117 .iterator(); 118 119 @Override 120 public boolean hasNext() { 121 return iterator.hasNext(); 122 } 123 124 @Override 125 public ByteString next() { 126 if (attribute.pimpl != expectedImpl) { 127 throw new ConcurrentModificationException(); 128 } else { 129 return iterator.next(); 130 } 131 } 132 133 @Override 134 public void remove() { 135 if (attribute.pimpl != expectedImpl) { 136 throw new ConcurrentModificationException(); 137 } else { 138 iterator.remove(); 139 140 // Resize if we have removed the second to last value. 141 if (attribute.multipleValues != null 142 && attribute.multipleValues.size() == 1) { 143 resize(attribute); 144 iterator = attribute.pimpl.iterator(attribute); 145 } 146 147 // Always update since we may change to single or zero 148 // value 149 // impl. 150 expectedImpl = attribute.pimpl; 151 } 152 } 153 154 }; 155 } 156 157 @Override 158 boolean remove(final LinkedAttribute attribute, final ByteString value) { 159 final ByteString normalizedValue = normalizeValue(attribute, value); 160 if (attribute.multipleValues.remove(normalizedValue) != null) { 161 resize(attribute); 162 return true; 163 } else { 164 return false; 165 } 166 } 167 168 @Override 169 <T> boolean retainAll(final LinkedAttribute attribute, final Collection<T> values, 170 final Collection<? super T> missingValues) { 171 // TODO: could optimize if objects is a LinkedAttribute having the 172 // same equality matching rule. 173 if (values.isEmpty()) { 174 clear(attribute); 175 return true; 176 } 177 178 final Map<ByteString, T> valuesToRetain = new HashMap<>(values.size()); 179 for (final T value : values) { 180 valuesToRetain.put(normalizeValue(attribute, ByteString.valueOf(value)), value); 181 } 182 183 boolean modified = false; 184 final Iterator<ByteString> iterator = attribute.multipleValues.keySet().iterator(); 185 while (iterator.hasNext()) { 186 final ByteString normalizedValue = iterator.next(); 187 if (valuesToRetain.remove(normalizedValue) == null) { 188 modified = true; 189 iterator.remove(); 190 } 191 } 192 193 if (missingValues != null) { 194 missingValues.addAll(valuesToRetain.values()); 195 } 196 197 resize(attribute); 198 199 return modified; 200 } 201 202 @Override 203 int size(final LinkedAttribute attribute) { 204 return attribute.multipleValues.size(); 205 } 206 207 private void resize(final LinkedAttribute attribute) { 208 // May need to resize if initial size estimate was wrong (e.g. all 209 // values in added collection were the same). 210 switch (attribute.multipleValues.size()) { 211 case 0: 212 attribute.multipleValues = null; 213 attribute.pimpl = ZERO_VALUE_IMPL; 214 break; 215 case 1: 216 final Map.Entry<ByteString, ByteString> e = 217 attribute.multipleValues.entrySet().iterator().next(); 218 attribute.singleValue = e.getValue(); 219 attribute.normalizedSingleValue = e.getKey(); 220 attribute.multipleValues = null; 221 attribute.pimpl = SINGLE_VALUE_IMPL; 222 break; 223 default: 224 // Nothing to do. 225 break; 226 } 227 } 228 } 229 230 private static final class SingleValueImpl extends Impl { 231 232 @Override 233 boolean add(final LinkedAttribute attribute, final ByteString value) { 234 final ByteString normalizedValue = normalizeValue(attribute, value); 235 if (attribute.normalizedSingleValue().equals(normalizedValue)) { 236 return false; 237 } 238 239 attribute.multipleValues = new LinkedHashMap<>(2); 240 attribute.multipleValues.put(attribute.normalizedSingleValue, attribute.singleValue); 241 attribute.multipleValues.put(normalizedValue, value); 242 attribute.singleValue = null; 243 attribute.normalizedSingleValue = null; 244 attribute.pimpl = MULTI_VALUE_IMPL; 245 246 return true; 247 } 248 249 @Override 250 void clear(final LinkedAttribute attribute) { 251 attribute.singleValue = null; 252 attribute.normalizedSingleValue = null; 253 attribute.pimpl = ZERO_VALUE_IMPL; 254 } 255 256 @Override 257 boolean contains(final LinkedAttribute attribute, final ByteString value) { 258 final ByteString normalizedValue = normalizeValue(attribute, value); 259 return attribute.normalizedSingleValue().equals(normalizedValue); 260 } 261 262 @Override 263 ByteString firstValue(final LinkedAttribute attribute) { 264 if (attribute.singleValue != null) { 265 return attribute.singleValue; 266 } else { 267 throw new NoSuchElementException(); 268 } 269 } 270 271 @Override 272 Iterator<ByteString> iterator(final LinkedAttribute attribute) { 273 return new Iterator<ByteString>() { 274 private Impl expectedImpl = SINGLE_VALUE_IMPL; 275 276 private boolean hasNext = true; 277 278 @Override 279 public boolean hasNext() { 280 return hasNext; 281 } 282 283 @Override 284 public ByteString next() { 285 if (attribute.pimpl != expectedImpl) { 286 throw new ConcurrentModificationException(); 287 } else if (hasNext) { 288 hasNext = false; 289 return attribute.singleValue; 290 } else { 291 throw new NoSuchElementException(); 292 } 293 } 294 295 @Override 296 public void remove() { 297 if (attribute.pimpl != expectedImpl) { 298 throw new ConcurrentModificationException(); 299 } else if (hasNext || attribute.singleValue == null) { 300 throw new IllegalStateException(); 301 } else { 302 clear(attribute); 303 expectedImpl = attribute.pimpl; 304 } 305 } 306 307 }; 308 } 309 310 @Override 311 boolean remove(final LinkedAttribute attribute, final ByteString value) { 312 if (contains(attribute, value)) { 313 clear(attribute); 314 return true; 315 } else { 316 return false; 317 } 318 } 319 320 @Override 321 <T> boolean retainAll(final LinkedAttribute attribute, final Collection<T> values, 322 final Collection<? super T> missingValues) { 323 // TODO: could optimize if objects is a LinkedAttribute having the 324 // same equality matching rule. 325 if (values.isEmpty()) { 326 clear(attribute); 327 return true; 328 } 329 330 final ByteString normalizedSingleValue = attribute.normalizedSingleValue(); 331 boolean retained = false; 332 for (final T value : values) { 333 final ByteString normalizedValue = 334 normalizeValue(attribute, ByteString.valueOf(value)); 335 if (normalizedSingleValue.equals(normalizedValue)) { 336 if (missingValues == null) { 337 // We can stop now. 338 return false; 339 } 340 retained = true; 341 } else if (missingValues != null) { 342 missingValues.add(value); 343 } 344 } 345 346 if (!retained) { 347 clear(attribute); 348 return true; 349 } else { 350 return false; 351 } 352 } 353 354 @Override 355 int size(final LinkedAttribute attribute) { 356 return 1; 357 } 358 } 359 360 private static final class ZeroValueImpl extends Impl { 361 362 @Override 363 boolean add(final LinkedAttribute attribute, final ByteString value) { 364 attribute.singleValue = value; 365 attribute.pimpl = SINGLE_VALUE_IMPL; 366 return true; 367 } 368 369 @Override 370 void clear(final LinkedAttribute attribute) { 371 // Nothing to do. 372 } 373 374 @Override 375 boolean contains(final LinkedAttribute attribute, final ByteString value) { 376 return false; 377 } 378 379 @Override 380 boolean containsAll(final LinkedAttribute attribute, final Collection<?> values) { 381 return values.isEmpty(); 382 } 383 384 @Override 385 ByteString firstValue(final LinkedAttribute attribute) { 386 throw new NoSuchElementException(); 387 } 388 389 @Override 390 Iterator<ByteString> iterator(final LinkedAttribute attribute) { 391 return new Iterator<ByteString>() { 392 @Override 393 public boolean hasNext() { 394 return false; 395 } 396 397 @Override 398 public ByteString next() { 399 if (attribute.pimpl != ZERO_VALUE_IMPL) { 400 throw new ConcurrentModificationException(); 401 } else { 402 throw new NoSuchElementException(); 403 } 404 } 405 406 @Override 407 public void remove() { 408 if (attribute.pimpl != ZERO_VALUE_IMPL) { 409 throw new ConcurrentModificationException(); 410 } else { 411 throw new IllegalStateException(); 412 } 413 } 414 415 }; 416 } 417 418 @Override 419 boolean remove(final LinkedAttribute attribute, final ByteString value) { 420 return false; 421 } 422 423 @Override 424 <T> boolean retainAll(final LinkedAttribute attribute, final Collection<T> values, 425 final Collection<? super T> missingValues) { 426 if (missingValues != null) { 427 missingValues.addAll(values); 428 } 429 return false; 430 } 431 432 @Override 433 int size(final LinkedAttribute attribute) { 434 return 0; 435 } 436 437 } 438 439 /** 440 * An attribute factory which can be used to create new linked attributes. 441 */ 442 public static final AttributeFactory FACTORY = new AttributeFactory() { 443 @Override 444 public Attribute newAttribute(final AttributeDescription attributeDescription) { 445 return new LinkedAttribute(attributeDescription); 446 } 447 }; 448 449 private static final MultiValueImpl MULTI_VALUE_IMPL = new MultiValueImpl(); 450 private static final SingleValueImpl SINGLE_VALUE_IMPL = new SingleValueImpl(); 451 private static final ZeroValueImpl ZERO_VALUE_IMPL = new ZeroValueImpl(); 452 453 private final AttributeDescription attributeDescription; 454 private Map<ByteString, ByteString> multipleValues; 455 private ByteString normalizedSingleValue; 456 private Impl pimpl = ZERO_VALUE_IMPL; 457 private ByteString singleValue; 458 459 /** 460 * Creates a new attribute having the same attribute description and 461 * attribute values as {@code attribute}. 462 * 463 * @param attribute 464 * The attribute to be copied. 465 * @throws NullPointerException 466 * If {@code attribute} was {@code null}. 467 */ 468 public LinkedAttribute(final Attribute attribute) { 469 this.attributeDescription = attribute.getAttributeDescription(); 470 471 if (attribute instanceof LinkedAttribute) { 472 final LinkedAttribute other = (LinkedAttribute) attribute; 473 this.pimpl = other.pimpl; 474 this.singleValue = other.singleValue; 475 this.normalizedSingleValue = other.normalizedSingleValue; 476 if (other.multipleValues != null) { 477 this.multipleValues = new LinkedHashMap<>(other.multipleValues); 478 } 479 } else { 480 addAll(attribute); 481 } 482 } 483 484 /** 485 * Creates a new attribute having the specified attribute description and no 486 * attribute values. 487 * 488 * @param attributeDescription 489 * The attribute description. 490 * @throws NullPointerException 491 * If {@code attributeDescription} was {@code null}. 492 */ 493 public LinkedAttribute(final AttributeDescription attributeDescription) { 494 Reject.ifNull(attributeDescription); 495 this.attributeDescription = attributeDescription; 496 } 497 498 /** 499 * Creates a new attribute having the specified attribute description and 500 * single attribute value. 501 * <p> 502 * If {@code value} is not an instance of {@code ByteString} then it will be 503 * converted using the {@link ByteString#valueOf(Object)} method. 504 * 505 * @param attributeDescription 506 * The attribute description. 507 * @param value 508 * The single attribute value. 509 * @throws NullPointerException 510 * If {@code attributeDescription} or {@code value} was 511 * {@code null} . 512 */ 513 public LinkedAttribute(final AttributeDescription attributeDescription, final Object value) { 514 this(attributeDescription); 515 add(value); 516 } 517 518 /** 519 * Creates a new attribute having the specified attribute description and 520 * attribute values. 521 * <p> 522 * Any attribute values which are not instances of {@code ByteString} will 523 * be converted using the {@link ByteString#valueOf(Object)} method. 524 * 525 * @param attributeDescription 526 * The attribute description. 527 * @param values 528 * The attribute values. 529 * @throws NullPointerException 530 * If {@code attributeDescription} or {@code values} was 531 * {@code null}. 532 */ 533 public LinkedAttribute(final AttributeDescription attributeDescription, 534 final Object... values) { 535 this(attributeDescription); 536 add(values); 537 } 538 539 /** 540 * Creates a new attribute having the specified attribute description and 541 * attribute values. 542 * <p> 543 * Any attribute values which are not instances of {@code ByteString} will 544 * be converted using the {@link ByteString#valueOf(Object)} method. 545 * 546 * @param attributeDescription 547 * The attribute description. 548 * @param values 549 * The attribute values. 550 * @throws NullPointerException 551 * If {@code attributeDescription} or {@code values} was 552 * {@code null}. 553 */ 554 public LinkedAttribute(final AttributeDescription attributeDescription, 555 final Collection<?> values) { 556 this(attributeDescription); 557 addAll(values, null); 558 } 559 560 /** 561 * Creates a new attribute having the specified attribute description and no 562 * attribute values. The attribute description will be decoded using the 563 * default schema. 564 * 565 * @param attributeDescription 566 * The attribute description. 567 * @throws LocalizedIllegalArgumentException 568 * If {@code attributeDescription} could not be decoded using 569 * the default schema. 570 * @throws NullPointerException 571 * If {@code attributeDescription} was {@code null}. 572 */ 573 public LinkedAttribute(final String attributeDescription) { 574 this(AttributeDescription.valueOf(attributeDescription)); 575 } 576 577 /** 578 * Creates a new attribute having the specified attribute description and 579 * attribute values. The attribute description will be decoded using the 580 * default schema. 581 * <p> 582 * Any attribute values which are not instances of {@code ByteString} will 583 * be converted using the {@link ByteString#valueOf(Object)} method. 584 * 585 * @param attributeDescription 586 * The attribute description. 587 * @param values 588 * The attribute values. 589 * @throws LocalizedIllegalArgumentException 590 * If {@code attributeDescription} could not be decoded using 591 * the default schema. 592 * @throws NullPointerException 593 * If {@code attributeDescription} or {@code values} was 594 * {@code null}. 595 */ 596 public LinkedAttribute(final String attributeDescription, final Collection<?> values) { 597 this(attributeDescription); 598 addAll(values, null); 599 } 600 601 /** 602 * Creates a new attribute having the specified attribute description and 603 * single attribute value. The attribute description will be decoded using 604 * the default schema. 605 * <p> 606 * If {@code value} is not an instance of {@code ByteString} then it will be 607 * converted using the {@link ByteString#valueOf(Object)} method. 608 * 609 * @param attributeDescription 610 * The attribute description. 611 * @param value 612 * The single attribute value. 613 * @throws LocalizedIllegalArgumentException 614 * If {@code attributeDescription} could not be decoded using 615 * the default schema. 616 * @throws NullPointerException 617 * If {@code attributeDescription} or {@code value} was 618 * {@code null} . 619 */ 620 public LinkedAttribute(final String attributeDescription, final Object value) { 621 this(attributeDescription); 622 add(ByteString.valueOf(value)); 623 } 624 625 /** 626 * Creates a new attribute having the specified attribute description and 627 * attribute values. The attribute description will be decoded using the 628 * default schema. 629 * <p> 630 * Any attribute values which are not instances of {@code ByteString} will 631 * be converted using the {@link ByteString#valueOf(Object)} method. 632 * 633 * @param attributeDescription 634 * The attribute description. 635 * @param values 636 * The attribute values. 637 * @throws LocalizedIllegalArgumentException 638 * If {@code attributeDescription} could not be decoded using 639 * the default schema. 640 * @throws NullPointerException 641 * If {@code attributeDescription} or {@code values} was 642 * {@code null}. 643 */ 644 public LinkedAttribute(final String attributeDescription, final Object... values) { 645 this(attributeDescription); 646 add(values); 647 } 648 649 /** {@inheritDoc} */ 650 @Override 651 public boolean add(final ByteString value) { 652 Reject.ifNull(value); 653 return pimpl.add(this, value); 654 } 655 656 /** {@inheritDoc} */ 657 @Override 658 public void clear() { 659 pimpl.clear(this); 660 } 661 662 /** {@inheritDoc} */ 663 @Override 664 public boolean contains(final Object value) { 665 Reject.ifNull(value); 666 return pimpl.contains(this, ByteString.valueOf(value)); 667 } 668 669 /** {@inheritDoc} */ 670 @Override 671 public boolean containsAll(final Collection<?> values) { 672 Reject.ifNull(values); 673 return pimpl.containsAll(this, values); 674 } 675 676 /** {@inheritDoc} */ 677 @Override 678 public ByteString firstValue() { 679 return pimpl.firstValue(this); 680 } 681 682 /** {@inheritDoc} */ 683 @Override 684 public AttributeDescription getAttributeDescription() { 685 return attributeDescription; 686 } 687 688 /** {@inheritDoc} */ 689 @Override 690 public Iterator<ByteString> iterator() { 691 return pimpl.iterator(this); 692 } 693 694 /** {@inheritDoc} */ 695 @Override 696 public boolean remove(final Object value) { 697 Reject.ifNull(value); 698 return pimpl.remove(this, ByteString.valueOf(value)); 699 } 700 701 /** {@inheritDoc} */ 702 @Override 703 public <T> boolean retainAll(final Collection<T> values, 704 final Collection<? super T> missingValues) { 705 Reject.ifNull(values); 706 return pimpl.retainAll(this, values, missingValues); 707 } 708 709 /** {@inheritDoc} */ 710 @Override 711 public int size() { 712 return pimpl.size(this); 713 } 714 715 /** Lazily computes the normalized single value. */ 716 private ByteString normalizedSingleValue() { 717 if (normalizedSingleValue == null) { 718 normalizedSingleValue = normalizeValue(this, singleValue); 719 } 720 return normalizedSingleValue; 721 } 722 723}