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