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.collect.ImmutableMap;
14 import java.util.AbstractSet;
15 import java.util.ArrayList;
16 import java.util.Arrays;
17 import java.util.Collection;
18 import java.util.Collections;
19 import java.util.ConcurrentModificationException;
20 import java.util.Iterator;
21 import java.util.LinkedHashMap;
23 import java.util.NoSuchElementException;
27 * A mutable version of {@link ImmutableOffsetMap}. It inherits the set of mappings from the immutable version and
28 * allows updating/removing existing mappings. New mappings are stored in a dedicated {@link LinkedHashMap} to preserve
29 * insertion order. It also tracks the need to duplicate the backing array, so the sequence of
31 * ImmutableOffsetMap<K, V> source;
32 * ImmutableOffsetMap<K, V> result = source.createMutableClone().immutableCopy();
34 * results in source and result sharing the backing objects.
36 * @param <K> the type of keys maintained by this map
37 * @param <V> the type of mapped values
40 public class MutableOffsetMap<K, V> extends AbstractLazyValueMap<K, V> implements Cloneable, ModifiableMapPhase<K, V> {
41 private static final Object[] EMPTY_ARRAY = new Object[0];
42 private static final Object NO_VALUE = new Object();
43 private final Map<K, Integer> offsets;
44 private final Map<K, V> newKeys;
45 private Object[] objects;
46 private int removed = 0;
47 private transient volatile int modCount;
48 private boolean needClone = true;
50 public MutableOffsetMap() {
51 this(Collections.<K>emptySet());
54 protected MutableOffsetMap(final Collection<K> keySet) {
55 if (!keySet.isEmpty()) {
56 removed = keySet.size();
57 offsets = OffsetMapCache.offsetsFor(keySet);
58 objects = new Object[removed];
59 Arrays.fill(objects, NO_VALUE);
61 offsets = ImmutableMap.of();
62 objects = EMPTY_ARRAY;
65 this.newKeys = new LinkedHashMap<>();
68 protected MutableOffsetMap(final ImmutableOffsetMap<K, V> m) {
69 this(m.offsets(), m.objects());
72 protected MutableOffsetMap(final Map<K, V> m) {
73 this(OffsetMapCache.offsetsFor(m.keySet()), m.values().toArray());
76 protected MutableOffsetMap(final MutableOffsetMap<K, V> m) {
77 this.offsets = m.offsets;
78 this.objects = m.objects;
79 this.newKeys = new LinkedHashMap<>(m.newKeys);
80 this.removed = m.removed;
83 private MutableOffsetMap(final Map<K, Integer> offsets, final Object[] objects) {
84 this.offsets = Preconditions.checkNotNull(offsets);
85 this.objects = Preconditions.checkNotNull(objects);
86 this.newKeys = new LinkedHashMap<>();
89 public static <K, V> MutableOffsetMap<K, V> copyOf(final Map<K, V> m) {
90 if (m instanceof MutableOffsetMap) {
91 return ((MutableOffsetMap<K, V>) m).clone();
93 if (m instanceof ImmutableOffsetMap) {
94 return ((ImmutableOffsetMap<K, V>) m).toModifiableMap();
97 return new MutableOffsetMap<>(m);
100 public static <K, V> MutableOffsetMap<K, V> forOffsets(final Map<K, Integer> offsets) {
101 final Object[] objects = new Object[offsets.size()];
102 Arrays.fill(objects, NO_VALUE);
104 return new MutableOffsetMap<>(offsets, objects);
107 public static <K, V> MutableOffsetMap<K, V> forKeySet(final Collection<K> keySet) {
108 return forOffsets(OffsetMapCache.offsetsFor(keySet));
112 public final int size() {
113 return offsets.size() + newKeys.size() - removed;
117 public final boolean isEmpty() {
122 public final boolean containsKey(final Object key) {
123 final Integer offset = offsets.get(key);
124 if (offset == null) {
125 return newKeys.containsKey(key);
128 return !NO_VALUE.equals(objects[offset]);
132 public final V get(final Object key) {
133 final Integer offset = offsets.get(key);
134 if (offset == null) {
135 return newKeys.get(key);
138 final Object o = objects[offset];
139 if (!NO_VALUE.equals(o)) {
140 @SuppressWarnings("unchecked")
142 return objectToValue(k, o);
148 private void cloneArray() {
151 if (!EMPTY_ARRAY.equals(objects)) {
152 objects = objects.clone();
158 public final V put(final K key, final V value) {
159 Preconditions.checkNotNull(value);
160 final Integer offset = offsets.get(Preconditions.checkNotNull(key));
161 if (offset == null) {
162 final V ret = newKeys.put(key, value);
170 final Object ret = objects[offset];
171 objects[offset] = valueToObject(value);
172 if (NO_VALUE.equals(ret)) {
178 return objectToValue(key, ret);
182 public final V remove(final Object key) {
183 final Integer offset = offsets.get(key);
184 if (offset == null) {
185 final V ret = newKeys.remove(key);
193 final Object ret = objects[offset];
194 objects[offset] = NO_VALUE;
195 if (!NO_VALUE.equals(ret)) {
198 @SuppressWarnings("unchecked")
200 return objectToValue(k, ret);
207 public final void clear() {
211 Arrays.fill(objects, NO_VALUE);
212 removed = objects.length;
218 public final Set<Entry<K, V>> entrySet() {
219 return new EntrySet();
223 public final Map<K, V> toUnmodifiableMap() {
224 if (newKeys.isEmpty() && removed == 0) {
225 // Make sure next modification clones the array, as we leak it to the map we return.
228 * TODO: we could track the ImmutableOffsetMap from which this one was instantiated and if we do not
229 * perform any modifications, just return the original instance. The trade-off is increased complexity
230 * and an additional field in this class.
232 return new ImmutableOffsetMap<>(offsets, objects);
235 final int s = size();
237 return ImmutableMap.of();
240 return ImmutableMap.copyOf(this);
243 // Construct the set of keys
244 final Collection<K> keyset = new ArrayList<>(s);
246 if (removed != offsets.size()) {
247 for (Entry<K, Integer> e : offsets.entrySet()) {
248 if (!NO_VALUE.equals(objects[e.getValue()])) {
249 keyset.add(e.getKey());
254 keyset.addAll(offsets.keySet());
256 keyset.addAll(newKeys.keySet());
258 // Construct the values
259 final Object[] values = new Object[keyset.size()];
262 if (removed != offsets.size()) {
263 for (Entry<K, Integer> e : offsets.entrySet()) {
264 final Object o = objects[e.getValue()];
265 if (!NO_VALUE.equals(o)) {
271 System.arraycopy(objects, 0, values, 0, offsets.size());
274 for (V v : newKeys.values()) {
275 values[i++] = valueToObject(v);
278 return new ImmutableOffsetMap<>(OffsetMapCache.offsetsFor(keyset), values);
282 public MutableOffsetMap<K, V> clone() {
283 return new MutableOffsetMap<K, V>(this);
287 public int hashCode() {
290 for (Entry<K, Integer> e : offsets.entrySet()) {
291 final Object v = objects[e.getValue()];
292 if (!NO_VALUE.equals(v)) {
293 result += e.getKey().hashCode() ^ objectToValue(e.getKey(), v).hashCode();
297 return result + newKeys.hashCode();
301 public boolean equals(final Object o) {
309 if (o instanceof ImmutableOffsetMap) {
310 final ImmutableOffsetMap<?, ?> om = (ImmutableOffsetMap<?, ?>) o;
311 if (newKeys.isEmpty() && offsets == om.offsets() && Arrays.deepEquals(objects, om.objects())) {
314 } else if (o instanceof MutableOffsetMap) {
315 final MutableOffsetMap<?, ?> om = (MutableOffsetMap<?, ?>) o;
316 if (offsets == om.offsets && Arrays.deepEquals(objects, om.objects) && newKeys.equals(om.newKeys)) {
319 } else if (o instanceof Map) {
320 final Map<?, ?> om = (Map<?, ?>)o;
322 // Size and key sets have to match
323 if (size() != om.size() || !keySet().equals(om.keySet())) {
328 // Ensure all newKeys are present. Note newKeys is guaranteed to
329 // not contain null value.
330 for (Entry<K, V> e : newKeys.entrySet()) {
331 if (!e.getValue().equals(om.get(e.getKey()))) {
336 // Ensure all objects are present
337 for (Entry<K, Integer> e : offsets.entrySet()) {
338 final Object obj = objects[e.getValue()];
339 if (!NO_VALUE.equals(obj)) {
340 final V v = objectToValue(e.getKey(), obj);
341 if (!v.equals(om.get(e.getKey()))) {
346 } catch (ClassCastException e) {
347 // Can be thrown by om.get() and indicate we have incompatible key types
358 public final Set<K> keySet() {
363 boolean needClone() {
377 private final class EntrySet extends AbstractSet<Entry<K, V>> {
379 public Iterator<Entry<K, V>> iterator() {
380 return new AbstractSetIterator<Entry<K, V>>() {
382 public Entry<K, V> next() {
383 final K key = nextKey();
384 return new SimpleEntry<>(key, get(key));
391 return MutableOffsetMap.this.size();
395 public boolean contains(final Object o) {
396 if (!(o instanceof Entry)) {
400 @SuppressWarnings("unchecked")
401 final Entry<K,V> e = (Entry<K,V>) o;
402 if (e.getValue() == null) {
406 return e.getValue().equals(MutableOffsetMap.this.get(e.getKey()));
410 public boolean add(final Entry<K, V> e) {
411 Preconditions.checkNotNull(e.getValue());
412 final V p = MutableOffsetMap.this.put(e.getKey(), e.getValue());
413 return !e.getValue().equals(p);
417 public boolean remove(final Object o) {
418 if (!(o instanceof Entry)) {
422 @SuppressWarnings("unchecked")
423 final Entry<K,V> e = (Entry<K,V>) o;
424 if (e.getValue() == null) {
428 final V v = MutableOffsetMap.this.get(e.getKey());
429 if (e.getValue().equals(v)) {
430 MutableOffsetMap.this.remove(e.getKey());
437 public void clear() {
438 MutableOffsetMap.this.clear();
442 private final class KeySet extends AbstractSet<K> {
444 public Iterator<K> iterator() {
445 return new AbstractSetIterator<K>() {
455 return MutableOffsetMap.this.size();
459 private abstract class AbstractSetIterator<E> implements Iterator<E> {
460 private final Iterator<Entry<K, Integer>> oldIterator = offsets.entrySet().iterator();
461 private final Iterator<K> newIterator = newKeys.keySet().iterator();
462 private int expectedModCount = modCount;
463 private K currentKey, nextKey;
465 AbstractSetIterator() {
469 private void updateNextKey() {
470 while (oldIterator.hasNext()) {
471 final Entry<K, Integer> e = oldIterator.next();
472 if (!NO_VALUE.equals(objects[e.getValue()])) {
473 nextKey = e.getKey();
478 nextKey = newIterator.hasNext() ? newIterator.next() : null;
481 private void checkModCount() {
482 if (modCount != expectedModCount) {
483 throw new ConcurrentModificationException();
488 public final boolean hasNext() {
490 return nextKey != null;
494 public final void remove() {
495 Preconditions.checkState(currentKey != null);
498 final Integer offset = offsets.get(currentKey);
499 if (offset != null) {
501 objects[offset] = NO_VALUE;
504 newIterator.remove();
507 expectedModCount = ++modCount;
511 protected final K nextKey() {
512 if (nextKey == null) {
513 throw new NoSuchElementException();
517 currentKey = nextKey;