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 public 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.offsets = m.offsets();
70 this.objects = m.objects();
71 this.newKeys = new LinkedHashMap<>();
74 protected MutableOffsetMap(final MutableOffsetMap<K, V> m) {
75 this.offsets = m.offsets;
76 this.objects = m.objects;
77 this.newKeys = new LinkedHashMap<>(m.newKeys);
78 this.removed = m.removed;
82 public final int size() {
83 return offsets.size() + newKeys.size() - removed;
87 public final boolean isEmpty() {
92 public final boolean containsKey(final Object key) {
93 final Integer offset = offsets.get(key);
95 return newKeys.containsKey(key);
98 return !NO_VALUE.equals(objects[offset]);
102 public final V get(final Object key) {
103 final Integer offset = offsets.get(key);
104 if (offset == null) {
105 return newKeys.get(key);
108 final Object o = objects[offset];
109 if (!NO_VALUE.equals(o)) {
110 @SuppressWarnings("unchecked")
112 return objectToValue(k, o);
118 private void cloneArray() {
121 if (!EMPTY_ARRAY.equals(objects)) {
122 objects = objects.clone();
128 public final V put(final K key, final V value) {
129 Preconditions.checkNotNull(value);
130 final Integer offset = offsets.get(Preconditions.checkNotNull(key));
131 if (offset == null) {
132 final V ret = newKeys.put(key, value);
140 final Object ret = objects[offset];
141 objects[offset] = valueToObject(value);
142 if (NO_VALUE.equals(ret)) {
148 return objectToValue(key, ret);
152 public final V remove(final Object key) {
153 final Integer offset = offsets.get(key);
154 if (offset == null) {
155 final V ret = newKeys.remove(key);
163 final Object ret = objects[offset];
164 objects[offset] = NO_VALUE;
165 if (!NO_VALUE.equals(ret)) {
168 @SuppressWarnings("unchecked")
170 return objectToValue(k, ret);
177 public final void clear() {
181 Arrays.fill(objects, NO_VALUE);
182 removed = objects.length;
188 public final Set<Entry<K, V>> entrySet() {
189 return new EntrySet();
193 public final Map<K, V> toUnmodifiableMap() {
194 if (newKeys.isEmpty() && removed == 0) {
195 // Make sure next modification clones the array, as we leak it to the map we return.
198 * TODO: we could track the ImmutableOffsetMap from which this one was instantiated and if we do not
199 * perform any modifications, just return the original instance. The trade-off is increased complexity
200 * and an additional field in this class.
202 return new ImmutableOffsetMap<>(offsets, objects);
205 final int s = size();
207 return ImmutableMap.of();
210 return ImmutableMap.copyOf(this);
213 // Construct the set of keys
214 final Collection<K> keyset = new ArrayList<>(s);
216 if (removed != offsets.size()) {
217 for (Entry<K, Integer> e : offsets.entrySet()) {
218 if (!NO_VALUE.equals(objects[e.getValue()])) {
219 keyset.add(e.getKey());
224 keyset.addAll(offsets.keySet());
226 keyset.addAll(newKeys.keySet());
228 // Construct the values
229 final Object[] values = new Object[keyset.size()];
232 if (removed != offsets.size()) {
233 for (Entry<K, Integer> e : offsets.entrySet()) {
234 final Object o = objects[e.getValue()];
235 if (!NO_VALUE.equals(o)) {
241 System.arraycopy(objects, 0, values, 0, offsets.size());
244 for (V v : newKeys.values()) {
245 values[i++] = valueToObject(v);
248 return new ImmutableOffsetMap<>(OffsetMapCache.offsetsFor(keyset), values);
252 public MutableOffsetMap<K, V> clone() throws CloneNotSupportedException {
253 return new MutableOffsetMap<K, V>(this);
257 public int hashCode() {
260 for (Entry<K, Integer> e : offsets.entrySet()) {
261 final Object v = objects[e.getValue()];
262 if (!NO_VALUE.equals(v)) {
263 result += e.getKey().hashCode() ^ objectToValue(e.getKey(), v).hashCode();
267 return result + newKeys.hashCode();
271 public boolean equals(final Object o) {
279 if (o instanceof ImmutableOffsetMap) {
280 final ImmutableOffsetMap<?, ?> om = (ImmutableOffsetMap<?, ?>) o;
281 if (newKeys.isEmpty() && offsets == om.offsets() && Arrays.deepEquals(objects, om.objects())) {
284 } else if (o instanceof MutableOffsetMap) {
285 final MutableOffsetMap<?, ?> om = (MutableOffsetMap<?, ?>) o;
286 if (offsets == om.offsets && Arrays.deepEquals(objects, om.objects) && newKeys.equals(om.newKeys)) {
289 } else if (o instanceof Map) {
290 final Map<?, ?> om = (Map<?, ?>)o;
292 // Size and key sets have to match
293 if (size() != om.size() || !keySet().equals(om.keySet())) {
298 // Ensure all newKeys are present. Note newKeys is guaranteed to
299 // not contain null value.
300 for (Entry<K, V> e : newKeys.entrySet()) {
301 if (!e.getValue().equals(om.get(e.getKey()))) {
306 // Ensure all objects are present
307 for (Entry<K, Integer> e : offsets.entrySet()) {
308 final Object obj = objects[e.getValue()];
309 if (!NO_VALUE.equals(obj)) {
310 final V v = objectToValue(e.getKey(), obj);
311 if (!v.equals(om.get(e.getKey()))) {
316 } catch (ClassCastException e) {
317 // Can be thrown by om.get() and indicate we have incompatible key types
328 public final Set<K> keySet() {
333 boolean needClone() {
347 private final class EntrySet extends AbstractSet<Entry<K, V>> {
349 public Iterator<Entry<K, V>> iterator() {
350 return new AbstractSetIterator<Entry<K, V>>() {
352 public Entry<K, V> next() {
353 final K key = nextKey();
354 return new SimpleEntry<>(key, get(key));
361 return MutableOffsetMap.this.size();
365 public boolean contains(final Object o) {
366 if (!(o instanceof Entry)) {
370 @SuppressWarnings("unchecked")
371 final Entry<K,V> e = (Entry<K,V>) o;
372 if (e.getValue() == null) {
376 return e.getValue().equals(MutableOffsetMap.this.get(e.getKey()));
380 public boolean add(final Entry<K, V> e) {
381 Preconditions.checkNotNull(e.getValue());
382 final V p = MutableOffsetMap.this.put(e.getKey(), e.getValue());
383 return !e.getValue().equals(p);
387 public boolean remove(final Object o) {
388 if (!(o instanceof Entry)) {
392 @SuppressWarnings("unchecked")
393 final Entry<K,V> e = (Entry<K,V>) o;
394 if (e.getValue() == null) {
398 final V v = MutableOffsetMap.this.get(e.getKey());
399 if (e.getValue().equals(v)) {
400 MutableOffsetMap.this.remove(e.getKey());
407 public void clear() {
408 MutableOffsetMap.this.clear();
412 private final class KeySet extends AbstractSet<K> {
414 public Iterator<K> iterator() {
415 return new AbstractSetIterator<K>() {
425 return MutableOffsetMap.this.size();
429 private abstract class AbstractSetIterator<E> implements Iterator<E> {
430 private final Iterator<Entry<K, Integer>> oldIterator = offsets.entrySet().iterator();
431 private final Iterator<K> newIterator = newKeys.keySet().iterator();
432 private int expectedModCount = modCount;
433 private K currentKey, nextKey;
435 AbstractSetIterator() {
439 private void updateNextKey() {
440 while (oldIterator.hasNext()) {
441 final Entry<K, Integer> e = oldIterator.next();
442 if (!NO_VALUE.equals(objects[e.getValue()])) {
443 nextKey = e.getKey();
448 nextKey = newIterator.hasNext() ? newIterator.next() : null;
451 private void checkModCount() {
452 if (modCount != expectedModCount) {
453 throw new ConcurrentModificationException();
458 public final boolean hasNext() {
460 return nextKey != null;
464 public final void remove() {
465 Preconditions.checkState(currentKey != null);
468 final Integer offset = offsets.get(currentKey);
469 if (offset != null) {
471 objects[offset] = NO_VALUE;
474 newIterator.remove();
477 expectedModCount = ++modCount;
481 protected final K nextKey() {
482 if (nextKey == null) {
483 throw new NoSuchElementException();
487 currentKey = nextKey;