X-Git-Url: https://git.opendaylight.org/gerrit/gitweb?a=blobdiff_plain;ds=sidebyside;f=common%2Futil%2Fsrc%2Fmain%2Fjava%2Forg%2Fopendaylight%2Fyangtools%2Futil%2FMutableOffsetMap.java;h=60f52396de4abe8e3231a1d9f75322fe44a6622f;hb=ccbc58aa197a18930106c17256b9308732469d8f;hp=014a59f1c3f2172a2936bab41659676ed76bf27e;hpb=b5baf0c5df8e298a4c50197038c2dd2a6d71abb1;p=yangtools.git diff --git a/common/util/src/main/java/org/opendaylight/yangtools/util/MutableOffsetMap.java b/common/util/src/main/java/org/opendaylight/yangtools/util/MutableOffsetMap.java index 014a59f1c3..60f52396de 100644 --- a/common/util/src/main/java/org/opendaylight/yangtools/util/MutableOffsetMap.java +++ b/common/util/src/main/java/org/opendaylight/yangtools/util/MutableOffsetMap.java @@ -7,22 +7,28 @@ */ package org.opendaylight.yangtools.util; +import static com.google.common.base.Preconditions.checkState; +import static java.util.Objects.requireNonNull; + import com.google.common.annotations.Beta; import com.google.common.annotations.VisibleForTesting; -import com.google.common.base.Preconditions; import com.google.common.collect.ImmutableMap; +import edu.umd.cs.findbugs.annotations.SuppressFBWarnings; import java.util.AbstractMap; import java.util.AbstractSet; import java.util.ArrayList; import java.util.Arrays; -import java.util.Collection; import java.util.Collections; import java.util.ConcurrentModificationException; +import java.util.HashMap; import java.util.Iterator; import java.util.LinkedHashMap; +import java.util.List; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; +import org.eclipse.jdt.annotation.NonNull; +import org.eclipse.jdt.annotation.Nullable; /** * A mutable version of {@link ImmutableOffsetMap}. It inherits the set of mappings from the immutable version and @@ -34,184 +40,344 @@ import java.util.Set; * * results in source and result sharing the backing objects. * - * This map does not support null keys nor values. + *

This map does not support null keys nor values. * * @param the type of keys maintained by this map * @param the type of mapped values */ @Beta -public final class MutableOffsetMap extends AbstractMap implements Cloneable, ModifiableMapPhase { - private static final Object[] EMPTY_ARRAY = new Object[0]; - private final Map offsets; - private final Map newKeys; - private V[] objects; - private int removed = 0; - private transient volatile int modCount; - private boolean needClone = true; +public abstract class MutableOffsetMap extends AbstractMap implements Cloneable, ModifiableMapPhase { + static final class Ordered extends MutableOffsetMap { + Ordered() { + } + + Ordered(final Map source) { + super(OffsetMapCache.orderedOffsets(source.keySet()), source); + } + + Ordered(final ImmutableMap offsets, final V[] objects) { + super(offsets, objects); + } + + @Override + Object removedObject() { + return REMOVED; + } + + @Override + UnmodifiableMapPhase modifiedMap(final List keys, final V[] values) { + return new ImmutableOffsetMap.Ordered<>(OffsetMapCache.orderedOffsets(keys), values); + } - public MutableOffsetMap() { - this(Collections.emptySet()); + @Override + UnmodifiableMapPhase unmodifiedMap(final ImmutableMap offsetMap, final V[] values) { + return new ImmutableOffsetMap.Ordered<>(offsetMap, values); + } + + @Override + SharedSingletonMap singletonMap() { + return SharedSingletonMap.orderedCopyOf(this); + } + + @Override + HashMap createNewKeys() { + return new LinkedHashMap<>(); + } } - @SuppressWarnings("unchecked") - protected MutableOffsetMap(final Collection keySet) { - if (!keySet.isEmpty()) { - removed = keySet.size(); - offsets = OffsetMapCache.offsetsFor(keySet); - objects = (V[])new Object[removed]; - } else { - offsets = ImmutableMap.of(); - objects = (V[])EMPTY_ARRAY; + static final class Unordered extends MutableOffsetMap { + Unordered() { + } + + Unordered(final Map source) { + super(OffsetMapCache.unorderedOffsets(source.keySet()), source); + } + + Unordered(final ImmutableMap offsets, final V[] objects) { + super(offsets, objects); + } + + @Override + Object removedObject() { + return null; + } + + @Override + UnmodifiableMapPhase modifiedMap(final List keys, final V[] values) { + final ImmutableMap offsets = OffsetMapCache.unorderedOffsets(keys); + return new ImmutableOffsetMap.Unordered<>(offsets, OffsetMapCache.adjustedArray(offsets, keys, values)); + } + + @Override + UnmodifiableMapPhase unmodifiedMap(final ImmutableMap offsetMap, final V[] values) { + return new ImmutableOffsetMap.Unordered<>(offsetMap, values); } - this.newKeys = new LinkedHashMap<>(); + @Override + SharedSingletonMap singletonMap() { + return SharedSingletonMap.unorderedCopyOf(this); + } + + @Override + HashMap createNewKeys() { + return new HashMap<>(); + } } - protected MutableOffsetMap(final ImmutableOffsetMap m) { - this(m.offsets(), m.objects()); + private static final Object[] EMPTY_ARRAY = new Object[0]; + private static final Object REMOVED = new Object(); + + private final ImmutableMap offsets; + private HashMap newKeys; + private Object[] objects; + private int removed = 0; + + // Fail-fast iterator guard, see java.util.ArrayList for reference. + @SuppressFBWarnings("VO_VOLATILE_INCREMENT") + private transient volatile int modCount; + private boolean needClone = true; + + MutableOffsetMap(final ImmutableMap offsets, final Object[] objects) { + this.offsets = requireNonNull(offsets); + this.objects = requireNonNull(objects); } - @SuppressWarnings("unchecked") - protected MutableOffsetMap(final Map m) { - this(OffsetMapCache.offsetsFor(m.keySet()), (V[])m.values().toArray()); + MutableOffsetMap() { + this(ImmutableMap.of(), EMPTY_ARRAY); } - protected MutableOffsetMap(final MutableOffsetMap m) { - this.offsets = m.offsets; - this.objects = m.objects; - this.newKeys = new LinkedHashMap<>(m.newKeys); - this.removed = m.removed; + MutableOffsetMap(final ImmutableMap offsets, final Map source) { + this(offsets, new Object[offsets.size()]); + + for (Entry e : source.entrySet()) { + objects[offsets.get(e.getKey())] = requireNonNull(e.getValue()); + } + + this.needClone = false; } - private MutableOffsetMap(final Map offsets, final V[] objects) { - this.offsets = Preconditions.checkNotNull(offsets); - this.objects = Preconditions.checkNotNull(objects); - this.newKeys = new LinkedHashMap<>(); + /** + * Create a {@link MutableOffsetMap} of the specified map, retaining its iteration order. + * + * @param map input map + * @return MutableOffsetMap with the same iteration order + * @throws NullPointerException if {@code map} is null + */ + public static @NonNull MutableOffsetMap orderedCopyOf(final Map map) { + if (map instanceof Ordered) { + return ((Ordered) map).clone(); + } + if (map instanceof ImmutableOffsetMap) { + final ImmutableOffsetMap om = (ImmutableOffsetMap) map; + return new Ordered<>(om.offsets(), om.objects()); + } + + return new Ordered<>(map); } - public static MutableOffsetMap copyOf(final Map m) { - if (m instanceof MutableOffsetMap) { - return ((MutableOffsetMap) m).clone(); + /** + * Create a {@link MutableOffsetMap} of the specified map, potentially with a different iteration order. + * + * @param map input map + * @return MutableOffsetMap with undefined iteration order + * @throws NullPointerException if {@code map} is null + */ + public static @NonNull MutableOffsetMap unorderedCopyOf(final Map map) { + if (map instanceof Unordered) { + return ((Unordered) map).clone(); } - if (m instanceof ImmutableOffsetMap) { - return ((ImmutableOffsetMap) m).toModifiableMap(); + if (map instanceof ImmutableOffsetMap) { + final ImmutableOffsetMap om = (ImmutableOffsetMap) map; + return new Unordered<>(om.offsets(), om.objects()); } - return new MutableOffsetMap<>(m); + return new Unordered<>(map); } - public static MutableOffsetMap forOffsets(final Map offsets) { - @SuppressWarnings("unchecked") - final V[] objects = (V[]) new Object[offsets.size()]; - return new MutableOffsetMap<>(offsets, objects); + /** + * Create an empty {@link MutableOffsetMap} which has an iteration order matching the insertion order. + * + * @return MutableOffsetMap which preserves insertion order + */ + public static @NonNull MutableOffsetMap ordered() { + return new MutableOffsetMap.Ordered<>(); } - public static MutableOffsetMap forKeySet(final Collection keySet) { - return forOffsets(OffsetMapCache.offsetsFor(keySet)); + /** + * Create an empty {@link MutableOffsetMap} which has unspecified iteration order. + * + * @return An MutableOffsetMap + */ + public static @NonNull MutableOffsetMap unordered() { + return new MutableOffsetMap.Unordered<>(); } + abstract Object removedObject(); + + abstract UnmodifiableMapPhase modifiedMap(List keys, V[] values); + + abstract UnmodifiableMapPhase unmodifiedMap(ImmutableMap offsetMap, V[] values); + + abstract SharedSingletonMap singletonMap(); + @Override - public int size() { - return offsets.size() + newKeys.size() - removed; + public final int size() { + return offsets.size() - removed + (newKeys == null ? 0 : newKeys.size()); } @Override - public boolean isEmpty() { + public final boolean isEmpty() { return size() == 0; } @Override - public boolean containsKey(final Object key) { + public final boolean containsKey(final Object key) { final Integer offset = offsets.get(key); - return offset == null ? newKeys.containsKey(key) : objects[offset] != null; + if (offset != null) { + final Object obj = objects[offset]; + if (!REMOVED.equals(obj)) { + return obj != null; + } + } + + return newKeys != null && newKeys.containsKey(key); } @Override - public V get(final Object key) { + public final V get(final Object key) { final Integer offset = offsets.get(key); - return offset == null ? newKeys.get(key) : objects[offset]; + if (offset != null) { + final Object obj = objects[offset]; + + /* + * This is a bit tricky: Ordered will put REMOVED to removed objects to retain strict insertion order. + * Unordered will add null, indicating that the slot may be reused in future. Hence if we see a REMOVED + * marker, we need to fall back to checking with new keys. + */ + if (!REMOVED.equals(obj)) { + @SuppressWarnings("unchecked") + final V ret = (V)obj; + return ret; + } + } + + return newKeys == null ? null : newKeys.get(key); } private void cloneArray() { if (needClone) { needClone = false; - if (!EMPTY_ARRAY.equals(objects)) { + if (objects.length != 0) { objects = objects.clone(); } } } @Override - public V put(final K key, final V value) { - Preconditions.checkNotNull(value); - final Integer offset = offsets.get(Preconditions.checkNotNull(key)); - if (offset == null) { - final V ret = newKeys.put(key, value); - if (ret == null) { - modCount++; + public final V put(final K key, final V value) { + requireNonNull(value); + final Integer offset = offsets.get(requireNonNull(key)); + if (offset != null) { + final Object obj = objects[offset]; + + /* + * Put which can potentially replace something in objects. Replacing an object does not cause iterators + * to be invalidated and does follow insertion order (since it is not a fresh insert). If the object has + * been removed, we fall back to newKeys. + */ + if (!REMOVED.equals(obj)) { + @SuppressWarnings("unchecked") + final V ret = (V)obj; + + cloneArray(); + objects[offset] = value; + if (ret == null) { + modCount++; + removed--; + } + + return ret; } - return ret; } - cloneArray(); - final V ret = objects[offset]; - objects[offset] = value; + if (newKeys == null) { + newKeys = createNewKeys(); + } + final V ret = newKeys.put(key, value); if (ret == null) { modCount++; - removed--; } - return ret; } @Override - public V remove(final Object key) { + public final V remove(final Object key) { final Integer offset = offsets.get(key); - if (offset == null) { - final V ret = newKeys.remove(key); - if (ret != null) { - modCount++; + if (offset != null) { + final Object obj = objects[offset]; + + /* + * A previous remove() may have indicated that the objects slot cannot be reused. In that case we need + * to fall back to checking with newKeys. + */ + if (!REMOVED.equals(obj)) { + cloneArray(); + + @SuppressWarnings("unchecked") + final V ret = (V)obj; + objects[offset] = removedObject(); + if (ret != null) { + modCount++; + removed++; + } + return ret; } - return ret; } - cloneArray(); - final V ret = objects[offset]; - objects[offset] = null; + if (newKeys == null) { + return null; + } + final V ret = newKeys.remove(key); if (ret != null) { modCount++; - removed++; } return ret; } @Override - public void clear() { + public final void clear() { if (size() != 0) { - newKeys.clear(); + if (newKeys != null) { + newKeys.clear(); + } cloneArray(); - Arrays.fill(objects, null); + Arrays.fill(objects, removedObject()); removed = objects.length; modCount++; } } @Override - public Set> entrySet() { + public final @NonNull Set> entrySet() { return new EntrySet(); } @Override - public Map toUnmodifiableMap() { - if (newKeys.isEmpty() && removed == 0) { + public @NonNull Map toUnmodifiableMap() { + if (removed == 0 && noNewKeys()) { // Make sure next modification clones the array, as we leak it to the map we return. needClone = true; + + // We have ended up with no removed objects, hence this cast is safe + @SuppressWarnings("unchecked") + final V[] values = (V[])objects; + /* * TODO: we could track the ImmutableOffsetMap from which this one was instantiated and if we do not * perform any modifications, just return the original instance. The trade-off is increased complexity * and an additional field in this class. */ - return new ImmutableOffsetMap<>(offsets, objects); + return unmodifiedMap(offsets, values); } final int s = size(); @@ -219,15 +385,16 @@ public final class MutableOffsetMap extends AbstractMap implements C return ImmutableMap.of(); } if (s == 1) { - return ImmutableMap.copyOf(this); + return singletonMap(); } // Construct the set of keys - final Collection keyset = new ArrayList<>(s); + final List keyset = new ArrayList<>(s); if (removed != 0) { if (removed != offsets.size()) { for (Entry e : offsets.entrySet()) { - if (objects[e.getValue()] != null) { + final Object o = objects[e.getValue()]; + if (o != null && !REMOVED.equals(o)) { keyset.add(e.getKey()); } } @@ -235,40 +402,56 @@ public final class MutableOffsetMap extends AbstractMap implements C } else { keyset.addAll(offsets.keySet()); } - keyset.addAll(newKeys.keySet()); + if (newKeys != null) { + keyset.addAll(newKeys.keySet()); + } // Construct the values @SuppressWarnings("unchecked") final V[] values = (V[])new Object[keyset.size()]; - int i = 0; + int offset = 0; if (removed != 0) { if (removed != offsets.size()) { for (Entry e : offsets.entrySet()) { - final V o = objects[e.getValue()]; - if (o != null) { - values[i++] = o; + final Object o = objects[e.getValue()]; + if (o != null && !REMOVED.equals(o)) { + @SuppressWarnings("unchecked") + final V v = (V) o; + values[offset++] = v; } } } } else { System.arraycopy(objects, 0, values, 0, offsets.size()); - i = offsets.size(); + offset = offsets.size(); } - for (V v : newKeys.values()) { - values[i++] = v; + if (newKeys != null) { + for (V v : newKeys.values()) { + values[offset++] = v; + } } - return new ImmutableOffsetMap<>(OffsetMapCache.offsetsFor(keyset), values); + return modifiedMap(keyset, values); } + @SuppressWarnings("unchecked") @Override public MutableOffsetMap clone() { - // FIXME: super.clone() - return new MutableOffsetMap(this); + final MutableOffsetMap ret; + + try { + ret = (MutableOffsetMap) super.clone(); + } catch (CloneNotSupportedException e) { + throw new IllegalStateException("Clone is expected to work", e); + } + + ret.newKeys = newKeys == null ? null : (HashMap) newKeys.clone(); + ret.needClone = true; + return ret; } @Override - public int hashCode() { + public final int hashCode() { int result = 0; for (Entry e : offsets.entrySet()) { @@ -278,87 +461,101 @@ public final class MutableOffsetMap extends AbstractMap implements C } } - return result + newKeys.hashCode(); + return newKeys != null ? result + newKeys.hashCode() : result; } @Override - public boolean equals(final Object o) { - if (o == this) { + public final boolean equals(final Object obj) { + if (obj == this) { return true; } - if (o == null) { + if (!(obj instanceof Map)) { return false; } - if (o instanceof ImmutableOffsetMap) { - final ImmutableOffsetMap om = (ImmutableOffsetMap) o; - if (newKeys.isEmpty() && offsets == om.offsets() && Arrays.deepEquals(objects, om.objects())) { - return true; - } - } else if (o instanceof MutableOffsetMap) { - final MutableOffsetMap om = (MutableOffsetMap) o; - if (offsets == om.offsets && Arrays.deepEquals(objects, om.objects) && newKeys.equals(om.newKeys)) { - return true; + if (obj instanceof ImmutableOffsetMap) { + final ImmutableOffsetMap om = (ImmutableOffsetMap) obj; + + if (noNewKeys() && offsets.equals(om.offsets())) { + return Arrays.deepEquals(objects, om.objects()); } - } else if (o instanceof Map) { - final Map om = (Map)o; + } else if (obj instanceof MutableOffsetMap) { + final MutableOffsetMap om = (MutableOffsetMap) obj; - // Size and key sets have to match - if (size() != om.size() || !keySet().equals(om.keySet())) { - return false; + if (offsets.equals(om.offsets)) { + return Arrays.deepEquals(objects, om.objects) && equalNewKeys(om); } + } + + // Fall back to brute map compare + return mapEquals((Map)obj); + } + + private boolean equalNewKeys(final MutableOffsetMap other) { + return noNewKeys() ? other.noNewKeys() : newKeys.equals(other.newKeys()); + } - try { - // Ensure all newKeys are present. Note newKeys is guaranteed to - // not contain null value. + private boolean mapEquals(final Map other) { + // Size and key sets have to match + if (size() != other.size() || !keySet().equals(other.keySet())) { + return false; + } + + try { + if (newKeys != null) { + // Ensure all newKeys are present. Note newKeys is guaranteed to not contain a null value. for (Entry e : newKeys.entrySet()) { - if (!e.getValue().equals(om.get(e.getKey()))) { + if (!e.getValue().equals(other.get(e.getKey()))) { return false; } } + } - // Ensure all objects are present - for (Entry e : offsets.entrySet()) { - final V v = objects[e.getValue()]; - if (v != null && !v.equals(om.get(e.getKey()))) { - return false; - } + // Ensure all objects are present + for (Entry e : offsets.entrySet()) { + final Object val = objects[e.getValue()]; + if (val != null && !REMOVED.equals(val) && !val.equals(other.get(e.getKey()))) { + return false; } - } catch (ClassCastException e) { - // Can be thrown by om.get() and indicate we have incompatible key types - return false; } - - return true; + } catch (ClassCastException e) { + // Can be thrown by other.get() and indicate we have incompatible key types + return false; } - return false; + return true; } @Override - public Set keySet() { + public final @NonNull Set keySet() { return new KeySet(); } @VisibleForTesting - boolean needClone() { + final boolean needClone() { return needClone; } @VisibleForTesting - Object array() { + final Object array() { return objects; } @VisibleForTesting - Object newKeys() { - return newKeys; + final Object newKeys() { + return newKeys != null ? newKeys : ImmutableMap.of(); + } + + abstract HashMap createNewKeys(); + + private boolean noNewKeys() { + return newKeys == null || newKeys.isEmpty(); } private final class EntrySet extends AbstractSet> { @Override - public Iterator> iterator() { - return new AbstractSetIterator>() { + public @NonNull Iterator> iterator() { + return new AbstractSetIterator<>() { @Override public Entry next() { final K key = nextKey(); @@ -373,6 +570,7 @@ public final class MutableOffsetMap extends AbstractMap implements C } @Override + @SuppressWarnings("checkstyle:parameterName") public boolean contains(final Object o) { if (!(o instanceof Entry)) { return false; @@ -388,13 +586,15 @@ public final class MutableOffsetMap extends AbstractMap implements C } @Override + @SuppressWarnings("checkstyle:parameterName") public boolean add(final Entry e) { - Preconditions.checkNotNull(e.getValue()); - final V p = MutableOffsetMap.this.put(e.getKey(), e.getValue()); - return !e.getValue().equals(p); + final V v = requireNonNull(e.getValue()); + final V p = MutableOffsetMap.this.put(e.getKey(), v); + return !v.equals(p); } @Override + @SuppressWarnings("checkstyle:parameterName") public boolean remove(final Object o) { if (!(o instanceof Entry)) { return false; @@ -422,8 +622,8 @@ public final class MutableOffsetMap extends AbstractMap implements C private final class KeySet extends AbstractSet { @Override - public Iterator iterator() { - return new AbstractSetIterator() { + public @NonNull Iterator iterator() { + return new AbstractSetIterator<>() { @Override public K next() { return nextKey(); @@ -439,9 +639,11 @@ public final class MutableOffsetMap extends AbstractMap implements C private abstract class AbstractSetIterator implements Iterator { private final Iterator> oldIterator = offsets.entrySet().iterator(); - private final Iterator newIterator = newKeys.keySet().iterator(); + private final Iterator newIterator = newKeys == null ? Collections.emptyIterator() + : newKeys.keySet().iterator(); private int expectedModCount = modCount; - private K currentKey, nextKey; + private @Nullable K currentKey = null; + private @Nullable K nextKey; AbstractSetIterator() { updateNextKey(); @@ -450,7 +652,8 @@ public final class MutableOffsetMap extends AbstractMap implements C private void updateNextKey() { while (oldIterator.hasNext()) { final Entry e = oldIterator.next(); - if (objects[e.getValue()] != null) { + final Object obj = objects[e.getValue()]; + if (obj != null && !REMOVED.equals(obj)) { nextKey = e.getKey(); return; } @@ -473,13 +676,12 @@ public final class MutableOffsetMap extends AbstractMap implements C @Override public final void remove() { - Preconditions.checkState(currentKey != null); - checkModCount(); + checkState(currentKey != null); final Integer offset = offsets.get(currentKey); if (offset != null) { cloneArray(); - objects[offset] = null; + objects[offset] = removedObject(); removed++; } else { newIterator.remove();