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}