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.Verify.verify;
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 java.util.AbstractMap;
17 import java.util.AbstractSet;
18 import java.util.ArrayList;
19 import java.util.Arrays;
20 import java.util.ConcurrentModificationException;
21 import java.util.HashMap;
22 import java.util.Iterator;
23 import java.util.LinkedHashMap;
24 import java.util.List;
26 import java.util.NoSuchElementException;
28 import javax.annotation.Nonnull;
31 * A mutable version of {@link ImmutableOffsetMap}. It inherits the set of mappings from the immutable version and
32 * allows updating/removing existing mappings. New mappings are stored in a dedicated {@link LinkedHashMap} to preserve
33 * insertion order. It also tracks the need to duplicate the backing array, so the sequence of
35 * ImmutableOffsetMap<K, V> source;
36 * ImmutableOffsetMap<K, V> result = source.createMutableClone().immutableCopy();
38 * results in source and result sharing the backing objects.
40 * <p>This map does not support null keys nor values.
42 * @param <K> the type of keys maintained by this map
43 * @param <V> the type of mapped values
46 public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implements Cloneable, ModifiableMapPhase<K, V> {
47 static final class Ordered<K, V> extends MutableOffsetMap<K, V> {
49 super(new LinkedHashMap<>());
52 Ordered(final Map<K, V> source) {
53 super(OffsetMapCache.orderedOffsets(source.keySet()), source, new LinkedHashMap<>());
56 Ordered(final Map<K, Integer> offsets, final V[] objects) {
57 super(offsets, objects, new LinkedHashMap<>());
61 Object removedObject() {
66 UnmodifiableMapPhase<K, V> modifiedMap(final List<K> keys, final V[] values) {
67 return new ImmutableOffsetMap.Ordered<>(OffsetMapCache.orderedOffsets(keys), values);
71 UnmodifiableMapPhase<K, V> unmodifiedMap(final Map<K, Integer> offsetMap, final V[] values) {
72 return new ImmutableOffsetMap.Ordered<>(offsetMap, values);
76 SharedSingletonMap<K, V> singletonMap() {
77 return SharedSingletonMap.orderedCopyOf(this);
81 static final class Unordered<K, V> extends MutableOffsetMap<K, V> {
83 super(new HashMap<>());
86 Unordered(final Map<K, V> source) {
87 super(OffsetMapCache.unorderedOffsets(source.keySet()), source, new HashMap<>());
90 Unordered(final Map<K, Integer> offsets, final V[] objects) {
91 super(offsets, objects, new HashMap<>());
95 Object removedObject() {
100 UnmodifiableMapPhase<K, V> modifiedMap(final List<K> keys, final V[] values) {
101 final Map<K, Integer> offsets = OffsetMapCache.unorderedOffsets(keys);
102 return new ImmutableOffsetMap.Unordered<>(offsets, OffsetMapCache.adjustedArray(offsets, keys, values));
106 UnmodifiableMapPhase<K, V> unmodifiedMap(final Map<K, Integer> offsetMap, final V[] values) {
107 return new ImmutableOffsetMap.Unordered<>(offsetMap, values);
111 SharedSingletonMap<K, V> singletonMap() {
112 return SharedSingletonMap.unorderedCopyOf(this);
116 private static final Object[] EMPTY_ARRAY = new Object[0];
117 private static final Object REMOVED = new Object();
118 private final Map<K, Integer> offsets;
119 private HashMap<K, V> newKeys;
120 private Object[] objects;
121 private int removed = 0;
122 private transient volatile int modCount;
123 private boolean needClone = true;
125 MutableOffsetMap(final Map<K, Integer> offsets, final V[] objects, final HashMap<K, V> newKeys) {
126 verify(newKeys.isEmpty());
127 this.offsets = requireNonNull(offsets);
128 this.objects = requireNonNull(objects);
129 this.newKeys = requireNonNull(newKeys);
132 @SuppressWarnings("unchecked")
133 MutableOffsetMap(final HashMap<K, V> newKeys) {
134 this(ImmutableMap.of(), (V[]) EMPTY_ARRAY, newKeys);
137 @SuppressWarnings("unchecked")
138 MutableOffsetMap(final Map<K, Integer> offsets, final Map<K, V> source, final HashMap<K, V> newKeys) {
139 this(offsets, (V[]) new Object[offsets.size()], newKeys);
141 for (Entry<K, V> e : source.entrySet()) {
142 objects[offsets.get(e.getKey())] = requireNonNull(e.getValue());
145 this.needClone = false;
148 public static <K, V> MutableOffsetMap<K, V> orderedCopyOf(final Map<K, V> map) {
149 if (map instanceof Ordered) {
150 return ((Ordered<K, V>) map).clone();
152 if (map instanceof ImmutableOffsetMap) {
153 final ImmutableOffsetMap<K, V> om = (ImmutableOffsetMap<K, V>) map;
154 return new Ordered<>(om.offsets(), om.objects());
157 return new Ordered<>(map);
160 public static <K, V> MutableOffsetMap<K, V> unorderedCopyOf(final Map<K, V> map) {
161 if (map instanceof Unordered) {
162 return ((Unordered<K, V>) map).clone();
164 if (map instanceof ImmutableOffsetMap) {
165 final ImmutableOffsetMap<K, V> om = (ImmutableOffsetMap<K, V>) map;
166 return new Unordered<>(om.offsets(), om.objects());
169 return new Unordered<>(map);
172 public static <K, V> MutableOffsetMap<K, V> ordered() {
173 return new MutableOffsetMap.Ordered<>();
176 public static <K, V> MutableOffsetMap<K, V> unordered() {
177 return new MutableOffsetMap.Unordered<>();
180 abstract Object removedObject();
182 abstract UnmodifiableMapPhase<K, V> modifiedMap(List<K> keys, V[] values);
184 abstract UnmodifiableMapPhase<K, V> unmodifiedMap(Map<K, Integer> offsetMap, V[] values);
186 abstract SharedSingletonMap<K, V> singletonMap();
189 public final int size() {
190 return offsets.size() + newKeys.size() - removed;
194 public final boolean isEmpty() {
199 public final boolean containsKey(final Object key) {
200 final Integer offset = offsets.get(key);
201 if (offset != null) {
202 final Object obj = objects[offset];
203 if (!REMOVED.equals(obj)) {
208 return newKeys.containsKey(key);
212 public final V get(final Object key) {
213 final Integer offset = offsets.get(key);
214 if (offset != null) {
215 final Object obj = objects[offset];
218 * This is a bit tricky: Ordered will put REMOVED to removed objects to retain strict insertion order.
219 * Unordered will add null, indicating that the slot may be reused in future. Hence if we see a REMOVED
220 * marker, we need to fall back to checking with new keys.
222 if (!REMOVED.equals(obj)) {
223 @SuppressWarnings("unchecked")
224 final V ret = (V)obj;
229 return newKeys.get(key);
232 private void cloneArray() {
235 if (!EMPTY_ARRAY.equals(objects)) {
236 objects = objects.clone();
242 public final V put(final K key, final V value) {
243 requireNonNull(value);
244 final Integer offset = offsets.get(requireNonNull(key));
245 if (offset != null) {
246 final Object obj = objects[offset];
249 * Put which can potentially replace something in objects. Replacing an object does not cause iterators
250 * to be invalidated and does follow insertion order (since it is not a fresh insert). If the object has
251 * been removed, we fall back to newKeys.
253 if (!REMOVED.equals(obj)) {
254 @SuppressWarnings("unchecked")
255 final V ret = (V)obj;
258 objects[offset] = value;
268 final V ret = newKeys.put(key, value);
276 public final V remove(final Object key) {
277 final Integer offset = offsets.get(key);
278 if (offset != null) {
279 final Object obj = objects[offset];
282 * A previous remove() may have indicated that the objects slot cannot be reused. In that case we need
283 * to fall back to checking with newKeys.
285 if (!REMOVED.equals(obj)) {
288 @SuppressWarnings("unchecked")
289 final V ret = (V)obj;
290 objects[offset] = removedObject();
299 final V ret = newKeys.remove(key);
307 public final void clear() {
311 Arrays.fill(objects, removedObject());
312 removed = objects.length;
319 public final Set<Entry<K, V>> entrySet() {
320 return new EntrySet();
325 public Map<K, V> toUnmodifiableMap() {
326 if (removed == 0 && newKeys.isEmpty()) {
327 // Make sure next modification clones the array, as we leak it to the map we return.
330 // We have ended up with no removed objects, hence this cast is safe
331 @SuppressWarnings("unchecked")
332 final V[] values = (V[])objects;
335 * TODO: we could track the ImmutableOffsetMap from which this one was instantiated and if we do not
336 * perform any modifications, just return the original instance. The trade-off is increased complexity
337 * and an additional field in this class.
339 return unmodifiedMap(offsets, values);
342 final int s = size();
344 return ImmutableMap.of();
347 return singletonMap();
350 // Construct the set of keys
351 final List<K> keyset = new ArrayList<>(s);
353 if (removed != offsets.size()) {
354 for (Entry<K, Integer> e : offsets.entrySet()) {
355 final Object o = objects[e.getValue()];
356 if (o != null && !REMOVED.equals(o)) {
357 keyset.add(e.getKey());
362 keyset.addAll(offsets.keySet());
364 keyset.addAll(newKeys.keySet());
366 // Construct the values
367 @SuppressWarnings("unchecked")
368 final V[] values = (V[])new Object[keyset.size()];
371 if (removed != offsets.size()) {
372 for (Entry<K, Integer> e : offsets.entrySet()) {
373 final Object o = objects[e.getValue()];
374 if (o != null && !REMOVED.equals(o)) {
375 @SuppressWarnings("unchecked")
377 values[offset++] = v;
382 System.arraycopy(objects, 0, values, 0, offsets.size());
383 offset = offsets.size();
385 for (V v : newKeys.values()) {
386 values[offset++] = v;
389 return modifiedMap(keyset, values);
392 @SuppressWarnings("unchecked")
394 public MutableOffsetMap<K, V> clone() {
395 final MutableOffsetMap<K, V> ret;
398 ret = (MutableOffsetMap<K, V>) super.clone();
399 } catch (CloneNotSupportedException e) {
400 throw new IllegalStateException("Clone is expected to work", e);
403 ret.newKeys = (HashMap<K, V>) newKeys.clone();
404 ret.needClone = true;
409 public final int hashCode() {
412 for (Entry<K, Integer> e : offsets.entrySet()) {
413 final Object v = objects[e.getValue()];
415 result += e.getKey().hashCode() ^ v.hashCode();
419 return result + newKeys.hashCode();
423 public final boolean equals(final Object obj) {
427 if (!(obj instanceof Map)) {
431 if (obj instanceof ImmutableOffsetMap) {
432 final ImmutableOffsetMap<?, ?> om = (ImmutableOffsetMap<?, ?>) obj;
434 if (newKeys.isEmpty() && offsets.equals(om.offsets())) {
435 return Arrays.deepEquals(objects, om.objects());
437 } else if (obj instanceof MutableOffsetMap) {
438 final MutableOffsetMap<?, ?> om = (MutableOffsetMap<?, ?>) obj;
440 if (offsets.equals(om.offsets)) {
441 return Arrays.deepEquals(objects, om.objects) && newKeys.equals(om.newKeys);
445 // Fall back to brute map compare
446 final Map<?, ?> other = (Map<?, ?>)obj;
448 // Size and key sets have to match
449 if (size() != other.size() || !keySet().equals(other.keySet())) {
454 // Ensure all newKeys are present. Note newKeys is guaranteed to
455 // not contain null value.
456 for (Entry<K, V> e : newKeys.entrySet()) {
457 if (!e.getValue().equals(other.get(e.getKey()))) {
462 // Ensure all objects are present
463 for (Entry<K, Integer> e : offsets.entrySet()) {
464 final Object val = objects[e.getValue()];
465 if (val != null && !REMOVED.equals(val) && !val.equals(other.get(e.getKey()))) {
469 } catch (ClassCastException e) {
470 // Can be thrown by other.get() and indicate we have incompatible key types
479 public final Set<K> keySet() {
484 final boolean needClone() {
489 final Object array() {
494 final Object newKeys() {
498 private final class EntrySet extends AbstractSet<Entry<K, V>> {
501 public Iterator<Entry<K, V>> iterator() {
502 return new AbstractSetIterator<Entry<K, V>>() {
504 public Entry<K, V> next() {
505 final K key = nextKey();
506 return new SimpleEntry<>(key, get(key));
513 return MutableOffsetMap.this.size();
517 @SuppressWarnings("checkstyle:parameterName")
518 public boolean contains(final Object o) {
519 if (!(o instanceof Entry)) {
523 @SuppressWarnings("unchecked")
524 final Entry<K,V> e = (Entry<K,V>) o;
525 if (e.getValue() == null) {
529 return e.getValue().equals(MutableOffsetMap.this.get(e.getKey()));
533 @SuppressWarnings("checkstyle:parameterName")
534 public boolean add(final Entry<K, V> e) {
535 final V v = requireNonNull(e.getValue());
536 final V p = MutableOffsetMap.this.put(e.getKey(), v);
541 @SuppressWarnings("checkstyle:parameterName")
542 public boolean remove(final Object o) {
543 if (!(o instanceof Entry)) {
547 @SuppressWarnings("unchecked")
548 final Entry<K,V> e = (Entry<K,V>) o;
549 if (e.getValue() == null) {
553 final V v = MutableOffsetMap.this.get(e.getKey());
554 if (e.getValue().equals(v)) {
555 MutableOffsetMap.this.remove(e.getKey());
562 public void clear() {
563 MutableOffsetMap.this.clear();
567 private final class KeySet extends AbstractSet<K> {
570 public Iterator<K> iterator() {
571 return new AbstractSetIterator<K>() {
581 return MutableOffsetMap.this.size();
585 private abstract class AbstractSetIterator<E> implements Iterator<E> {
586 private final Iterator<Entry<K, Integer>> oldIterator = offsets.entrySet().iterator();
587 private final Iterator<K> newIterator = newKeys.keySet().iterator();
588 private int expectedModCount = modCount;
589 private K currentKey;
592 AbstractSetIterator() {
596 private void updateNextKey() {
597 while (oldIterator.hasNext()) {
598 final Entry<K, Integer> e = oldIterator.next();
599 final Object obj = objects[e.getValue()];
600 if (obj != null && !REMOVED.equals(obj)) {
601 nextKey = e.getKey();
606 nextKey = newIterator.hasNext() ? newIterator.next() : null;
609 private void checkModCount() {
610 if (modCount != expectedModCount) {
611 throw new ConcurrentModificationException();
616 public final boolean hasNext() {
618 return nextKey != null;
622 public final void remove() {
623 requireNonNull(currentKey != null);
626 final Integer offset = offsets.get(currentKey);
627 if (offset != null) {
629 objects[offset] = removedObject();
632 newIterator.remove();
635 expectedModCount = ++modCount;
639 protected final K nextKey() {
640 if (nextKey == null) {
641 throw new NoSuchElementException();
645 currentKey = nextKey;