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}