2 * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved.
4 * This program and the accompanying materials are made available under the
5 * terms of the Eclipse Public License v1.0 which accompanies this distribution,
6 * and is available at http://www.eclipse.org/legal/epl-v10.html
8 package org.opendaylight.yangtools.util;
10 import static com.google.common.base.Preconditions.checkState;
11 import static java.util.Objects.requireNonNull;
13 import com.google.common.annotations.Beta;
14 import com.google.common.annotations.VisibleForTesting;
15 import com.google.common.collect.ImmutableMap;
16 import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
17 import java.util.AbstractMap;
18 import java.util.AbstractSet;
19 import java.util.ArrayList;
20 import java.util.Arrays;
21 import java.util.Collections;
22 import java.util.ConcurrentModificationException;
23 import java.util.HashMap;
24 import java.util.Iterator;
25 import java.util.LinkedHashMap;
26 import java.util.List;
28 import java.util.NoSuchElementException;
30 import org.eclipse.jdt.annotation.NonNull;
31 import org.eclipse.jdt.annotation.Nullable;
34 * A mutable version of {@link ImmutableOffsetMap}. It inherits the set of mappings from the immutable version and
35 * allows updating/removing existing mappings. New mappings are stored in a dedicated {@link LinkedHashMap} to preserve
36 * insertion order. It also tracks the need to duplicate the backing array, so the sequence of
38 * ImmutableOffsetMap<K, V> source;
39 * ImmutableOffsetMap<K, V> result = source.createMutableClone().immutableCopy();
41 * results in source and result sharing the backing objects.
43 * <p>This map does not support null keys nor values.
45 * @param <K> the type of keys maintained by this map
46 * @param <V> the type of mapped values
49 public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implements Cloneable, ModifiableMapPhase<K, V> {
50 static final class Ordered<K, V> extends MutableOffsetMap<K, V> {
54 Ordered(final Map<K, V> source) {
55 super(OffsetMapCache.orderedOffsets(source.keySet()), source);
58 Ordered(final ImmutableMap<K, Integer> offsets, final V[] objects) {
59 super(offsets, objects);
63 Object removedObject() {
68 UnmodifiableMapPhase<K, V> modifiedMap(final List<K> keys, final V[] values) {
69 return new ImmutableOffsetMap.Ordered<>(OffsetMapCache.orderedOffsets(keys), values);
73 UnmodifiableMapPhase<K, V> unmodifiedMap(final ImmutableMap<K, Integer> offsetMap, final V[] values) {
74 return new ImmutableOffsetMap.Ordered<>(offsetMap, values);
78 SharedSingletonMap<K, V> singletonMap() {
79 return SharedSingletonMap.orderedCopyOf(this);
83 HashMap<K, V> createNewKeys() {
84 return new LinkedHashMap<>();
88 static final class Unordered<K, V> extends MutableOffsetMap<K, V> {
92 Unordered(final Map<K, V> source) {
93 super(OffsetMapCache.unorderedOffsets(source.keySet()), source);
96 Unordered(final ImmutableMap<K, Integer> offsets, final V[] objects) {
97 super(offsets, objects);
101 Object removedObject() {
106 UnmodifiableMapPhase<K, V> modifiedMap(final List<K> keys, final V[] values) {
107 final ImmutableMap<K, Integer> offsets = OffsetMapCache.unorderedOffsets(keys);
108 return new ImmutableOffsetMap.Unordered<>(offsets, OffsetMapCache.adjustedArray(offsets, keys, values));
112 UnmodifiableMapPhase<K, V> unmodifiedMap(final ImmutableMap<K, Integer> offsetMap, final V[] values) {
113 return new ImmutableOffsetMap.Unordered<>(offsetMap, values);
117 SharedSingletonMap<K, V> singletonMap() {
118 return SharedSingletonMap.unorderedCopyOf(this);
122 HashMap<K, V> createNewKeys() {
123 return new HashMap<>();
127 private static final Object[] EMPTY_ARRAY = new Object[0];
128 private static final Object REMOVED = new Object();
130 private final ImmutableMap<K, Integer> offsets;
131 private HashMap<K, V> newKeys;
132 private Object[] objects;
133 private int removed = 0;
135 // Fail-fast iterator guard, see java.util.ArrayList for reference.
136 @SuppressFBWarnings("VO_VOLATILE_INCREMENT")
137 private transient volatile int modCount;
138 private boolean needClone = true;
140 MutableOffsetMap(final ImmutableMap<K, Integer> offsets, final Object[] objects) {
141 this.offsets = requireNonNull(offsets);
142 this.objects = requireNonNull(objects);
146 this(ImmutableMap.of(), EMPTY_ARRAY);
149 MutableOffsetMap(final ImmutableMap<K, Integer> offsets, final Map<K, V> source) {
150 this(offsets, new Object[offsets.size()]);
152 for (Entry<K, V> e : source.entrySet()) {
153 objects[offsets.get(e.getKey())] = requireNonNull(e.getValue());
156 this.needClone = false;
160 * Create a {@link MutableOffsetMap} of the specified map, retaining its iteration order.
162 * @param map input map
163 * @return MutableOffsetMap with the same iteration order
164 * @throws NullPointerException if {@code map} is null
166 public static <K, V> @NonNull MutableOffsetMap<K, V> orderedCopyOf(final Map<K, V> map) {
167 if (map instanceof Ordered) {
168 return ((Ordered<K, V>) map).clone();
170 if (map instanceof ImmutableOffsetMap) {
171 final ImmutableOffsetMap<K, V> om = (ImmutableOffsetMap<K, V>) map;
172 return new Ordered<>(om.offsets(), om.objects());
175 return new Ordered<>(map);
179 * Create a {@link MutableOffsetMap} of the specified map, potentially with a different iteration order.
181 * @param map input map
182 * @return MutableOffsetMap with undefined iteration order
183 * @throws NullPointerException if {@code map} is null
185 public static <K, V> @NonNull MutableOffsetMap<K, V> unorderedCopyOf(final Map<K, V> map) {
186 if (map instanceof Unordered) {
187 return ((Unordered<K, V>) map).clone();
189 if (map instanceof ImmutableOffsetMap) {
190 final ImmutableOffsetMap<K, V> om = (ImmutableOffsetMap<K, V>) map;
191 return new Unordered<>(om.offsets(), om.objects());
194 return new Unordered<>(map);
198 * Create an empty {@link MutableOffsetMap} which has an iteration order matching the insertion order.
200 * @return MutableOffsetMap which preserves insertion order
202 public static <K, V> @NonNull MutableOffsetMap<K, V> ordered() {
203 return new MutableOffsetMap.Ordered<>();
207 * Create an empty {@link MutableOffsetMap} which has unspecified iteration order.
209 * @return An MutableOffsetMap
211 public static <K, V> @NonNull MutableOffsetMap<K, V> unordered() {
212 return new MutableOffsetMap.Unordered<>();
215 abstract Object removedObject();
217 abstract UnmodifiableMapPhase<K, V> modifiedMap(List<K> keys, V[] values);
219 abstract UnmodifiableMapPhase<K, V> unmodifiedMap(ImmutableMap<K, Integer> offsetMap, V[] values);
221 abstract SharedSingletonMap<K, V> singletonMap();
224 public final int size() {
225 return offsets.size() - removed + (newKeys == null ? 0 : newKeys.size());
229 public final boolean isEmpty() {
234 public final boolean containsKey(final Object key) {
235 final Integer offset = offsets.get(key);
236 if (offset != null) {
237 final Object obj = objects[offset];
238 if (!REMOVED.equals(obj)) {
243 return newKeys != null && newKeys.containsKey(key);
247 public final V get(final Object key) {
248 final Integer offset = offsets.get(key);
249 if (offset != null) {
250 final Object obj = objects[offset];
253 * This is a bit tricky: Ordered will put REMOVED to removed objects to retain strict insertion order.
254 * Unordered will add null, indicating that the slot may be reused in future. Hence if we see a REMOVED
255 * marker, we need to fall back to checking with new keys.
257 if (!REMOVED.equals(obj)) {
258 @SuppressWarnings("unchecked")
259 final V ret = (V)obj;
264 return newKeys == null ? null : newKeys.get(key);
267 private void cloneArray() {
270 if (objects.length != 0) {
271 objects = objects.clone();
277 public final V put(final K key, final V value) {
278 requireNonNull(value);
279 final Integer offset = offsets.get(requireNonNull(key));
280 if (offset != null) {
281 final Object obj = objects[offset];
284 * Put which can potentially replace something in objects. Replacing an object does not cause iterators
285 * to be invalidated and does follow insertion order (since it is not a fresh insert). If the object has
286 * been removed, we fall back to newKeys.
288 if (!REMOVED.equals(obj)) {
289 @SuppressWarnings("unchecked")
290 final V ret = (V)obj;
293 objects[offset] = value;
303 if (newKeys == null) {
304 newKeys = createNewKeys();
306 final V ret = newKeys.put(key, value);
314 public final V remove(final Object key) {
315 final Integer offset = offsets.get(key);
316 if (offset != null) {
317 final Object obj = objects[offset];
320 * A previous remove() may have indicated that the objects slot cannot be reused. In that case we need
321 * to fall back to checking with newKeys.
323 if (!REMOVED.equals(obj)) {
326 @SuppressWarnings("unchecked")
327 final V ret = (V)obj;
328 objects[offset] = removedObject();
337 if (newKeys == null) {
340 final V ret = newKeys.remove(key);
348 public final void clear() {
350 if (newKeys != null) {
354 Arrays.fill(objects, removedObject());
355 removed = objects.length;
361 public final @NonNull Set<Entry<K, V>> entrySet() {
362 return new EntrySet();
366 public @NonNull Map<K, V> toUnmodifiableMap() {
367 if (removed == 0 && noNewKeys()) {
368 // Make sure next modification clones the array, as we leak it to the map we return.
371 // We have ended up with no removed objects, hence this cast is safe
372 @SuppressWarnings("unchecked")
373 final V[] values = (V[])objects;
376 * TODO: we could track the ImmutableOffsetMap from which this one was instantiated and if we do not
377 * perform any modifications, just return the original instance. The trade-off is increased complexity
378 * and an additional field in this class.
380 return unmodifiedMap(offsets, values);
383 final int s = size();
385 return ImmutableMap.of();
388 return singletonMap();
391 // Construct the set of keys
392 final List<K> keyset = new ArrayList<>(s);
394 if (removed != offsets.size()) {
395 for (Entry<K, Integer> e : offsets.entrySet()) {
396 final Object o = objects[e.getValue()];
397 if (o != null && !REMOVED.equals(o)) {
398 keyset.add(e.getKey());
403 keyset.addAll(offsets.keySet());
405 if (newKeys != null) {
406 keyset.addAll(newKeys.keySet());
409 // Construct the values
410 @SuppressWarnings("unchecked")
411 final V[] values = (V[])new Object[keyset.size()];
414 if (removed != offsets.size()) {
415 for (Entry<K, Integer> e : offsets.entrySet()) {
416 final Object o = objects[e.getValue()];
417 if (o != null && !REMOVED.equals(o)) {
418 @SuppressWarnings("unchecked")
420 values[offset++] = v;
425 System.arraycopy(objects, 0, values, 0, offsets.size());
426 offset = offsets.size();
428 if (newKeys != null) {
429 for (V v : newKeys.values()) {
430 values[offset++] = v;
434 return modifiedMap(keyset, values);
437 @SuppressWarnings("unchecked")
439 public MutableOffsetMap<K, V> clone() {
440 final MutableOffsetMap<K, V> ret;
443 ret = (MutableOffsetMap<K, V>) super.clone();
444 } catch (CloneNotSupportedException e) {
445 throw new IllegalStateException("Clone is expected to work", e);
448 ret.newKeys = newKeys == null ? null : (HashMap<K, V>) newKeys.clone();
449 ret.needClone = true;
454 public final int hashCode() {
457 for (Entry<K, Integer> e : offsets.entrySet()) {
458 final Object v = objects[e.getValue()];
460 result += e.getKey().hashCode() ^ v.hashCode();
464 return newKeys != null ? result + newKeys.hashCode() : result;
468 public final boolean equals(final Object obj) {
472 if (!(obj instanceof Map)) {
476 if (obj instanceof ImmutableOffsetMap) {
477 final ImmutableOffsetMap<?, ?> om = (ImmutableOffsetMap<?, ?>) obj;
479 if (noNewKeys() && offsets.equals(om.offsets())) {
480 return Arrays.deepEquals(objects, om.objects());
482 } else if (obj instanceof MutableOffsetMap) {
483 final MutableOffsetMap<?, ?> om = (MutableOffsetMap<?, ?>) obj;
485 if (offsets.equals(om.offsets)) {
486 return Arrays.deepEquals(objects, om.objects) && equalNewKeys(om);
490 // Fall back to brute map compare
491 return mapEquals((Map<?, ?>)obj);
494 private boolean equalNewKeys(final MutableOffsetMap<?, ?> other) {
495 return noNewKeys() ? other.noNewKeys() : newKeys.equals(other.newKeys());
498 private boolean mapEquals(final Map<?, ?> other) {
499 // Size and key sets have to match
500 if (size() != other.size() || !keySet().equals(other.keySet())) {
505 if (newKeys != null) {
506 // Ensure all newKeys are present. Note newKeys is guaranteed to not contain a null value.
507 for (Entry<K, V> e : newKeys.entrySet()) {
508 if (!e.getValue().equals(other.get(e.getKey()))) {
514 // Ensure all objects are present
515 for (Entry<K, Integer> e : offsets.entrySet()) {
516 final Object val = objects[e.getValue()];
517 if (val != null && !REMOVED.equals(val) && !val.equals(other.get(e.getKey()))) {
521 } catch (ClassCastException e) {
522 // Can be thrown by other.get() and indicate we have incompatible key types
530 public final @NonNull Set<K> keySet() {
535 final boolean needClone() {
540 final Object array() {
545 final Object newKeys() {
546 return newKeys != null ? newKeys : ImmutableMap.of();
549 abstract HashMap<K, V> createNewKeys();
551 private boolean noNewKeys() {
552 return newKeys == null || newKeys.isEmpty();
555 private final class EntrySet extends AbstractSet<Entry<K, V>> {
557 public @NonNull Iterator<Entry<K, V>> iterator() {
558 return new AbstractSetIterator<Entry<K, V>>() {
560 public Entry<K, V> next() {
561 final K key = nextKey();
562 return new SimpleEntry<>(key, get(key));
569 return MutableOffsetMap.this.size();
573 @SuppressWarnings("checkstyle:parameterName")
574 public boolean contains(final Object o) {
575 if (!(o instanceof Entry)) {
579 @SuppressWarnings("unchecked")
580 final Entry<K,V> e = (Entry<K,V>) o;
581 if (e.getValue() == null) {
585 return e.getValue().equals(MutableOffsetMap.this.get(e.getKey()));
589 @SuppressWarnings("checkstyle:parameterName")
590 public boolean add(final Entry<K, V> e) {
591 final V v = requireNonNull(e.getValue());
592 final V p = MutableOffsetMap.this.put(e.getKey(), v);
597 @SuppressWarnings("checkstyle:parameterName")
598 public boolean remove(final Object o) {
599 if (!(o instanceof Entry)) {
603 @SuppressWarnings("unchecked")
604 final Entry<K,V> e = (Entry<K,V>) o;
605 if (e.getValue() == null) {
609 final V v = MutableOffsetMap.this.get(e.getKey());
610 if (e.getValue().equals(v)) {
611 MutableOffsetMap.this.remove(e.getKey());
618 public void clear() {
619 MutableOffsetMap.this.clear();
623 private final class KeySet extends AbstractSet<K> {
625 public @NonNull Iterator<K> iterator() {
626 return new AbstractSetIterator<K>() {
636 return MutableOffsetMap.this.size();
640 private abstract class AbstractSetIterator<E> implements Iterator<E> {
641 private final Iterator<Entry<K, Integer>> oldIterator = offsets.entrySet().iterator();
642 private final Iterator<K> newIterator = newKeys == null ? Collections.emptyIterator()
643 : newKeys.keySet().iterator();
644 private int expectedModCount = modCount;
645 private @Nullable K currentKey = null;
646 private @Nullable K nextKey;
648 AbstractSetIterator() {
652 private void updateNextKey() {
653 while (oldIterator.hasNext()) {
654 final Entry<K, Integer> e = oldIterator.next();
655 final Object obj = objects[e.getValue()];
656 if (obj != null && !REMOVED.equals(obj)) {
657 nextKey = e.getKey();
662 nextKey = newIterator.hasNext() ? newIterator.next() : null;
665 private void checkModCount() {
666 if (modCount != expectedModCount) {
667 throw new ConcurrentModificationException();
672 public final boolean hasNext() {
674 return nextKey != null;
678 public final void remove() {
680 checkState(currentKey != null);
681 final Integer offset = offsets.get(currentKey);
682 if (offset != null) {
684 objects[offset] = removedObject();
687 newIterator.remove();
690 expectedModCount = ++modCount;
694 protected final K nextKey() {
695 if (nextKey == null) {
696 throw new NoSuchElementException();
700 currentKey = nextKey;