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 com.google.common.annotations.Beta;
11 import com.google.common.annotations.VisibleForTesting;
12 import com.google.common.base.Preconditions;
13 import com.google.common.base.Verify;
14 import com.google.common.collect.ImmutableMap;
15 import java.util.AbstractMap;
16 import java.util.AbstractSet;
17 import java.util.ArrayList;
18 import java.util.Arrays;
19 import java.util.ConcurrentModificationException;
20 import java.util.HashMap;
21 import java.util.Iterator;
22 import java.util.LinkedHashMap;
23 import java.util.List;
25 import java.util.NoSuchElementException;
27 import javax.annotation.Nonnull;
30 * A mutable version of {@link ImmutableOffsetMap}. It inherits the set of mappings from the immutable version and
31 * allows updating/removing existing mappings. New mappings are stored in a dedicated {@link LinkedHashMap} to preserve
32 * insertion order. It also tracks the need to duplicate the backing array, so the sequence of
34 * ImmutableOffsetMap<K, V> source;
35 * ImmutableOffsetMap<K, V> result = source.createMutableClone().immutableCopy();
37 * results in source and result sharing the backing objects.
39 * <p>This map does not support null keys nor values.
41 * @param <K> the type of keys maintained by this map
42 * @param <V> the type of mapped values
45 public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implements Cloneable, ModifiableMapPhase<K, V> {
46 static final class Ordered<K, V> extends MutableOffsetMap<K, V> {
48 super(new LinkedHashMap<>());
51 Ordered(final Map<K, V> source) {
52 super(OffsetMapCache.orderedOffsets(source.keySet()), source, new LinkedHashMap<>());
55 Ordered(final Map<K, Integer> offsets, final V[] objects) {
56 super(offsets, objects, new LinkedHashMap<>());
60 Object removedObject() {
65 UnmodifiableMapPhase<K, V> modifiedMap(final List<K> keys, final V[] objects) {
66 return new ImmutableOffsetMap.Ordered<>(OffsetMapCache.orderedOffsets(keys), objects);
70 UnmodifiableMapPhase<K, V> unmodifiedMap(final Map<K, Integer> offsets, final V[] objects) {
71 return new ImmutableOffsetMap.Ordered<>(offsets, objects);
75 SharedSingletonMap<K, V> singletonMap() {
76 return SharedSingletonMap.orderedCopyOf(this);
80 static final class Unordered<K, V> extends MutableOffsetMap<K, V> {
82 super(new HashMap<>());
85 Unordered(final Map<K, V> source) {
86 super(OffsetMapCache.unorderedOffsets(source.keySet()), source, new HashMap<>());
89 Unordered(final Map<K, Integer> offsets, final V[] objects) {
90 super(offsets, objects, new HashMap<>());
94 Object removedObject() {
99 UnmodifiableMapPhase<K, V> modifiedMap(final List<K> keys, final V[] objects) {
100 final Map<K, Integer> offsets = OffsetMapCache.unorderedOffsets(keys);
101 return new ImmutableOffsetMap.Unordered<>(offsets, OffsetMapCache.adjustedArray(offsets, keys, objects));
105 UnmodifiableMapPhase<K, V> unmodifiedMap(final Map<K, Integer> offsets, final V[] objects) {
106 return new ImmutableOffsetMap.Unordered<>(offsets, objects);
110 SharedSingletonMap<K, V> singletonMap() {
111 return SharedSingletonMap.unorderedCopyOf(this);
115 private static final Object[] EMPTY_ARRAY = new Object[0];
116 private static final Object REMOVED = new Object();
117 private final Map<K, Integer> offsets;
118 private HashMap<K, V> newKeys;
119 private Object[] objects;
120 private int removed = 0;
121 private transient volatile int modCount;
122 private boolean needClone = true;
124 MutableOffsetMap(final Map<K, Integer> offsets, final V[] objects, final HashMap<K, V> newKeys) {
125 Verify.verify(newKeys.isEmpty());
126 this.offsets = Preconditions.checkNotNull(offsets);
127 this.objects = Preconditions.checkNotNull(objects);
128 this.newKeys = Preconditions.checkNotNull(newKeys);
131 @SuppressWarnings("unchecked")
132 MutableOffsetMap(final HashMap<K, V> newKeys) {
133 this(ImmutableMap.of(), (V[]) EMPTY_ARRAY, newKeys);
136 @SuppressWarnings("unchecked")
137 MutableOffsetMap(final Map<K, Integer> offsets, final Map<K, V> source, final HashMap<K, V> newKeys) {
138 this(offsets, (V[]) new Object[offsets.size()], newKeys);
140 for (Entry<K, V> e : source.entrySet()) {
141 objects[offsets.get(e.getKey())] = Preconditions.checkNotNull(e.getValue());
144 this.needClone = false;
147 public static <K, V> MutableOffsetMap<K, V> orderedCopyOf(final Map<K, V> map) {
148 if (map instanceof Ordered) {
149 return ((Ordered<K, V>) map).clone();
151 if (map instanceof ImmutableOffsetMap) {
152 final ImmutableOffsetMap<K, V> om = (ImmutableOffsetMap<K, V>) map;
153 return new Ordered<>(om.offsets(), om.objects());
156 return new Ordered<>(map);
159 public static <K, V> MutableOffsetMap<K, V> unorderedCopyOf(final Map<K, V> map) {
160 if (map instanceof Unordered) {
161 return ((Unordered<K, V>) map).clone();
163 if (map instanceof ImmutableOffsetMap) {
164 final ImmutableOffsetMap<K, V> om = (ImmutableOffsetMap<K, V>) map;
165 return new Unordered<>(om.offsets(), om.objects());
168 return new Unordered<>(map);
171 public static <K, V> MutableOffsetMap<K, V> ordered() {
172 return new MutableOffsetMap.Ordered<>();
175 public static <K, V> MutableOffsetMap<K, V> unordered() {
176 return new MutableOffsetMap.Unordered<>();
179 abstract Object removedObject();
181 abstract UnmodifiableMapPhase<K, V> modifiedMap(List<K> keys, V[] objects);
183 abstract UnmodifiableMapPhase<K, V> unmodifiedMap(Map<K, Integer> offsets, V[] objects);
185 abstract SharedSingletonMap<K, V> singletonMap();
188 public final int size() {
189 return offsets.size() + newKeys.size() - removed;
193 public final boolean isEmpty() {
198 public final boolean containsKey(final Object key) {
199 final Integer offset = offsets.get(key);
200 if (offset != null) {
201 final Object obj = objects[offset];
202 if (!REMOVED.equals(obj)) {
207 return newKeys.containsKey(key);
211 public final V get(final Object key) {
212 final Integer offset = offsets.get(key);
213 if (offset != null) {
214 final Object obj = objects[offset];
217 * This is a bit tricky: Ordered will put REMOVED to removed objects to retain strict insertion order.
218 * Unordered will add null, indicating that the slot may be reused in future. Hence if we see a REMOVED
219 * marker, we need to fall back to checking with new keys.
221 if (!REMOVED.equals(obj)) {
222 @SuppressWarnings("unchecked")
223 final V ret = (V)obj;
228 return newKeys.get(key);
231 private void cloneArray() {
234 if (!EMPTY_ARRAY.equals(objects)) {
235 objects = objects.clone();
241 public final V put(final K key, final V value) {
242 Preconditions.checkNotNull(value);
243 final Integer offset = offsets.get(Preconditions.checkNotNull(key));
244 if (offset != null) {
245 final Object obj = objects[offset];
248 * Put which can potentially replace something in objects. Replacing an object does not cause iterators
249 * to be invalidated and does follow insertion order (since it is not a fresh insert). If the object has
250 * been removed, we fall back to newKeys.
252 if (!REMOVED.equals(obj)) {
253 @SuppressWarnings("unchecked")
254 final V ret = (V)obj;
257 objects[offset] = value;
267 final V ret = newKeys.put(key, value);
275 public final V remove(final Object key) {
276 final Integer offset = offsets.get(key);
277 if (offset != null) {
278 final Object obj = objects[offset];
281 * A previous remove() may have indicated that the objects slot cannot be reused. In that case we need
282 * to fall back to checking with newKeys.
284 if (!REMOVED.equals(obj)) {
287 @SuppressWarnings("unchecked")
288 final V ret = (V)obj;
289 objects[offset] = removedObject();
298 final V ret = newKeys.remove(key);
306 public final void clear() {
310 Arrays.fill(objects, removedObject());
311 removed = objects.length;
318 public final Set<Entry<K, V>> entrySet() {
319 return new EntrySet();
324 public Map<K, V> toUnmodifiableMap() {
325 if (removed == 0 && newKeys.isEmpty()) {
326 // Make sure next modification clones the array, as we leak it to the map we return.
329 // We have ended up with no removed objects, hence this cast is safe
330 @SuppressWarnings("unchecked")
331 final V[] values = (V[])objects;
334 * TODO: we could track the ImmutableOffsetMap from which this one was instantiated and if we do not
335 * perform any modifications, just return the original instance. The trade-off is increased complexity
336 * and an additional field in this class.
338 return unmodifiedMap(offsets, values);
341 final int s = size();
343 return ImmutableMap.of();
346 return singletonMap();
349 // Construct the set of keys
350 final List<K> keyset = new ArrayList<>(s);
352 if (removed != offsets.size()) {
353 for (Entry<K, Integer> e : offsets.entrySet()) {
354 final Object o = objects[e.getValue()];
355 if (o != null && !REMOVED.equals(o)) {
356 keyset.add(e.getKey());
361 keyset.addAll(offsets.keySet());
363 keyset.addAll(newKeys.keySet());
365 // Construct the values
366 @SuppressWarnings("unchecked")
367 final V[] values = (V[])new Object[keyset.size()];
370 if (removed != offsets.size()) {
371 for (Entry<K, Integer> e : offsets.entrySet()) {
372 final Object o = objects[e.getValue()];
373 if (o != null && !REMOVED.equals(o)) {
374 @SuppressWarnings("unchecked")
376 values[offset++] = v;
381 System.arraycopy(objects, 0, values, 0, offsets.size());
382 offset = offsets.size();
384 for (V v : newKeys.values()) {
385 values[offset++] = v;
388 return modifiedMap(keyset, values);
391 @SuppressWarnings("unchecked")
393 public MutableOffsetMap<K, V> clone() {
394 final MutableOffsetMap<K, V> ret;
397 ret = (MutableOffsetMap<K, V>) super.clone();
398 } catch (CloneNotSupportedException e) {
399 throw new IllegalStateException("Clone is expected to work", e);
402 ret.newKeys = (HashMap<K, V>) newKeys.clone();
403 ret.needClone = true;
408 public final int hashCode() {
411 for (Entry<K, Integer> e : offsets.entrySet()) {
412 final Object v = objects[e.getValue()];
414 result += e.getKey().hashCode() ^ v.hashCode();
418 return result + newKeys.hashCode();
422 public final boolean equals(final Object obj) {
426 if (!(obj instanceof Map)) {
430 if (obj instanceof ImmutableOffsetMap) {
431 final ImmutableOffsetMap<?, ?> om = (ImmutableOffsetMap<?, ?>) obj;
433 if (newKeys.isEmpty() && offsets.equals(om.offsets())) {
434 return Arrays.deepEquals(objects, om.objects());
436 } else if (obj instanceof MutableOffsetMap) {
437 final MutableOffsetMap<?, ?> om = (MutableOffsetMap<?, ?>) obj;
439 if (offsets.equals(om.offsets)) {
440 return Arrays.deepEquals(objects, om.objects) && newKeys.equals(om.newKeys);
444 // Fall back to brute map compare
445 final Map<?, ?> other = (Map<?, ?>)obj;
447 // Size and key sets have to match
448 if (size() != other.size() || !keySet().equals(other.keySet())) {
453 // Ensure all newKeys are present. Note newKeys is guaranteed to
454 // not contain null value.
455 for (Entry<K, V> e : newKeys.entrySet()) {
456 if (!e.getValue().equals(other.get(e.getKey()))) {
461 // Ensure all objects are present
462 for (Entry<K, Integer> e : offsets.entrySet()) {
463 final Object val = objects[e.getValue()];
464 if (val != null && !REMOVED.equals(val) && !val.equals(other.get(e.getKey()))) {
468 } catch (ClassCastException e) {
469 // Can be thrown by other.get() and indicate we have incompatible key types
478 public final Set<K> keySet() {
483 final boolean needClone() {
488 final Object array() {
493 final Object newKeys() {
497 private final class EntrySet extends AbstractSet<Entry<K, V>> {
500 public Iterator<Entry<K, V>> iterator() {
501 return new AbstractSetIterator<Entry<K, V>>() {
503 public Entry<K, V> next() {
504 final K key = nextKey();
505 return new SimpleEntry<>(key, get(key));
512 return MutableOffsetMap.this.size();
516 @SuppressWarnings("checkstyle:parameterName")
517 public boolean contains(final Object o) {
518 if (!(o instanceof Entry)) {
522 @SuppressWarnings("unchecked")
523 final Entry<K,V> e = (Entry<K,V>) o;
524 if (e.getValue() == null) {
528 return e.getValue().equals(MutableOffsetMap.this.get(e.getKey()));
532 @SuppressWarnings("checkstyle:parameterName")
533 public boolean add(final Entry<K, V> e) {
534 Preconditions.checkNotNull(e.getValue());
535 final V p = MutableOffsetMap.this.put(e.getKey(), e.getValue());
536 return !e.getValue().equals(p);
540 @SuppressWarnings("checkstyle:parameterName")
541 public boolean remove(final Object o) {
542 if (!(o instanceof Entry)) {
546 @SuppressWarnings("unchecked")
547 final Entry<K,V> e = (Entry<K,V>) o;
548 if (e.getValue() == null) {
552 final V v = MutableOffsetMap.this.get(e.getKey());
553 if (e.getValue().equals(v)) {
554 MutableOffsetMap.this.remove(e.getKey());
561 public void clear() {
562 MutableOffsetMap.this.clear();
566 private final class KeySet extends AbstractSet<K> {
569 public Iterator<K> iterator() {
570 return new AbstractSetIterator<K>() {
580 return MutableOffsetMap.this.size();
584 private abstract class AbstractSetIterator<E> implements Iterator<E> {
585 private final Iterator<Entry<K, Integer>> oldIterator = offsets.entrySet().iterator();
586 private final Iterator<K> newIterator = newKeys.keySet().iterator();
587 private int expectedModCount = modCount;
588 private K currentKey;
591 AbstractSetIterator() {
595 private void updateNextKey() {
596 while (oldIterator.hasNext()) {
597 final Entry<K, Integer> e = oldIterator.next();
598 final Object obj = objects[e.getValue()];
599 if (obj != null && !REMOVED.equals(obj)) {
600 nextKey = e.getKey();
605 nextKey = newIterator.hasNext() ? newIterator.next() : null;
608 private void checkModCount() {
609 if (modCount != expectedModCount) {
610 throw new ConcurrentModificationException();
615 public final boolean hasNext() {
617 return nextKey != null;
621 public final void remove() {
622 Preconditions.checkState(currentKey != null);
625 final Integer offset = offsets.get(currentKey);
626 if (offset != null) {
628 objects[offset] = removedObject();
631 newIterator.remove();
634 expectedModCount = ++modCount;
638 protected final K nextKey() {
639 if (nextKey == null) {
640 throw new NoSuchElementException();
644 currentKey = nextKey;