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(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 boolean needClone() {
271 private final class EntrySet extends AbstractSet<Entry<K, V>> {
273 public Iterator<Entry<K, V>> iterator() {
274 return new EntrySetIterator();
279 return MutableOffsetMap.this.size();
283 public boolean contains(final Object o) {
284 if (!(o instanceof Entry)) {
288 @SuppressWarnings("unchecked")
289 final Entry<K,V> e = (Entry<K,V>) o;
290 if (e.getValue() == null) {
294 return e.getValue().equals(MutableOffsetMap.this.get(e.getKey()));
298 public boolean add(final Entry<K, V> e) {
299 Preconditions.checkNotNull(e.getValue());
300 final V p = MutableOffsetMap.this.put(e.getKey(), e.getValue());
301 return !e.getValue().equals(p);
305 public boolean remove(final Object o) {
306 if (!(o instanceof Entry)) {
310 @SuppressWarnings("unchecked")
311 final Entry<K,V> e = (Entry<K,V>) o;
312 if (e.getValue() == null) {
316 final V v = MutableOffsetMap.this.get(e.getKey());
317 if (e.getValue().equals(v)) {
318 MutableOffsetMap.this.remove(e.getKey());
325 public void clear() {
326 MutableOffsetMap.this.clear();
330 private final class EntrySetIterator implements Iterator<Entry<K, V>> {
331 private final Iterator<Entry<K, Integer>> oldIterator = offsets.entrySet().iterator();
332 private final Iterator<Entry<K, V>> newIterator = newKeys.entrySet().iterator();
333 private int expectedModCount = modCount;
334 private K currentKey, nextKey;
340 private void calculateNextKey() {
341 while (oldIterator.hasNext()) {
342 final Entry<K, Integer> e = oldIterator.next();
343 if (!NO_VALUE.equals(objects[e.getValue()])) {
344 nextKey = e.getKey();
349 nextKey = newIterator.hasNext() ? newIterator.next().getKey() : null;
352 private void checkModCount() {
353 if (modCount != expectedModCount) {
354 throw new ConcurrentModificationException();
359 public boolean hasNext() {
361 return nextKey != null;
365 public Entry<K, V> next() {
366 if (nextKey == null) {
367 throw new NoSuchElementException();
371 currentKey = nextKey;
374 return new SimpleEntry<>(currentKey, get(currentKey));
378 public void remove() {
379 Preconditions.checkState(currentKey != null);
382 final Integer offset = offsets.get(currentKey);
383 if (offset != null) {
385 objects[offset] = NO_VALUE;
388 newIterator.remove();
391 expectedModCount = ++modCount;