X-Git-Url: https://git.opendaylight.org/gerrit/gitweb?a=blobdiff_plain;f=common%2Futil%2Fsrc%2Fmain%2Fjava%2Forg%2Fopendaylight%2Fyangtools%2Futil%2FMutableOffsetMap.java;h=60f52396de4abe8e3231a1d9f75322fe44a6622f;hb=4f66528ebcf1603108218b8ebf48147d8ed3ad38;hp=dee904fbe7ff0ef52ac99d763d4c59cf450fbe61;hpb=6b5d20f6513bc3e6e5db4a2058ee81308edaa9c8;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 dee904fbe7..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,15 +7,18 @@ */ 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.base.Verify; 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.Collections; import java.util.ConcurrentModificationException; import java.util.HashMap; import java.util.Iterator; @@ -24,6 +27,8 @@ 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 @@ -35,7 +40,7 @@ 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 @@ -44,15 +49,14 @@ import java.util.Set; public abstract class MutableOffsetMap extends AbstractMap implements Cloneable, ModifiableMapPhase { static final class Ordered extends MutableOffsetMap { Ordered() { - super(new LinkedHashMap<>()); } Ordered(final Map source) { - super(OffsetMapCache.orderedOffsets(source.keySet()), source, new LinkedHashMap<>()); + super(OffsetMapCache.orderedOffsets(source.keySet()), source); } - Ordered(final Map offsets, final V[] objects) { - super(offsets, objects, new LinkedHashMap<>()); + Ordered(final ImmutableMap offsets, final V[] objects) { + super(offsets, objects); } @Override @@ -61,32 +65,36 @@ public abstract class MutableOffsetMap extends AbstractMap implement } @Override - UnmodifiableMapPhase modifiedMap(final List keys, final V[] objects) { - return new ImmutableOffsetMap.Ordered<>(OffsetMapCache.orderedOffsets(keys), objects); + UnmodifiableMapPhase modifiedMap(final List keys, final V[] values) { + return new ImmutableOffsetMap.Ordered<>(OffsetMapCache.orderedOffsets(keys), values); } @Override - UnmodifiableMapPhase unmodifiedMap(final Map offsets, final V[] objects) { - return new ImmutableOffsetMap.Ordered<>(offsets, objects); + 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<>(); + } } static final class Unordered extends MutableOffsetMap { Unordered() { - super(new HashMap<>()); } Unordered(final Map source) { - super(OffsetMapCache.unorderedOffsets(source.keySet()), source, new HashMap<>()); + super(OffsetMapCache.unorderedOffsets(source.keySet()), source); } - Unordered(final Map offsets, final V[] objects) { - super(offsets, objects, new HashMap<>()); + Unordered(final ImmutableMap offsets, final V[] objects) { + super(offsets, objects); } @Override @@ -95,94 +103,126 @@ public abstract class MutableOffsetMap extends AbstractMap implement } @Override - UnmodifiableMapPhase modifiedMap(final List keys, final V[] objects) { - final Map offsets = OffsetMapCache.unorderedOffsets(keys); - return new ImmutableOffsetMap.Unordered<>(offsets, OffsetMapCache.adjustedArray(offsets, keys, objects)); + 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 Map offsets, final V[] objects) { - return new ImmutableOffsetMap.Unordered<>(offsets, objects); + UnmodifiableMapPhase unmodifiedMap(final ImmutableMap offsetMap, final V[] values) { + return new ImmutableOffsetMap.Unordered<>(offsetMap, values); } @Override SharedSingletonMap singletonMap() { return SharedSingletonMap.unorderedCopyOf(this); } + + @Override + HashMap createNewKeys() { + return new HashMap<>(); + } } private static final Object[] EMPTY_ARRAY = new Object[0]; private static final Object REMOVED = new Object(); - private final Map offsets; + + 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 Map offsets, final V[] objects, final HashMap newKeys) { - Verify.verify(newKeys.isEmpty()); - this.offsets = Preconditions.checkNotNull(offsets); - this.objects = Preconditions.checkNotNull(objects); - this.newKeys = Preconditions.checkNotNull(newKeys); + MutableOffsetMap(final ImmutableMap offsets, final Object[] objects) { + this.offsets = requireNonNull(offsets); + this.objects = requireNonNull(objects); } - @SuppressWarnings("unchecked") - MutableOffsetMap(final HashMap newKeys) { - this(ImmutableMap.of(), (V[]) EMPTY_ARRAY, newKeys); + MutableOffsetMap() { + this(ImmutableMap.of(), EMPTY_ARRAY); } - @SuppressWarnings("unchecked") - MutableOffsetMap(final Map offsets, final Map source, final HashMap newKeys) { - this(offsets, (V[]) new Object[offsets.size()], newKeys); + MutableOffsetMap(final ImmutableMap offsets, final Map source) { + this(offsets, new Object[offsets.size()]); for (Entry e : source.entrySet()) { - objects[offsets.get(e.getKey())] = Preconditions.checkNotNull(e.getValue()); + objects[offsets.get(e.getKey())] = requireNonNull(e.getValue()); } this.needClone = false; } - public static MutableOffsetMap orderedCopyOf(final Map m) { - if (m instanceof Ordered) { - return ((Ordered) m).clone(); - } - if (m instanceof ImmutableOffsetMap) { - final ImmutableOffsetMap om = (ImmutableOffsetMap) m; + /** + * 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<>(m); + return new Ordered<>(map); } - public static MutableOffsetMap unorderedCopyOf(final Map m) { - if (m instanceof Unordered) { - return ((Unordered) m).clone(); - } - if (m instanceof ImmutableOffsetMap) { - final ImmutableOffsetMap om = (ImmutableOffsetMap) m; + /** + * 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 (map instanceof ImmutableOffsetMap) { + final ImmutableOffsetMap om = (ImmutableOffsetMap) map; return new Unordered<>(om.offsets(), om.objects()); } - return new Unordered<>(m); + return new Unordered<>(map); } - public static MutableOffsetMap ordered() { + /** + * 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 unordered() { + /** + * 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[] objects); - abstract UnmodifiableMapPhase unmodifiedMap(Map offsets, V[] objects); + + abstract UnmodifiableMapPhase modifiedMap(List keys, V[] values); + + abstract UnmodifiableMapPhase unmodifiedMap(ImmutableMap offsetMap, V[] values); + abstract SharedSingletonMap singletonMap(); @Override public final int size() { - return offsets.size() + newKeys.size() - removed; + return offsets.size() - removed + (newKeys == null ? 0 : newKeys.size()); } @Override @@ -200,7 +240,7 @@ public abstract class MutableOffsetMap extends AbstractMap implement } } - return newKeys.containsKey(key); + return newKeys != null && newKeys.containsKey(key); } @Override @@ -221,13 +261,13 @@ public abstract class MutableOffsetMap extends AbstractMap implement } } - return newKeys.get(key); + 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(); } } @@ -235,8 +275,8 @@ public abstract class MutableOffsetMap extends AbstractMap implement @Override public final V put(final K key, final V value) { - Preconditions.checkNotNull(value); - final Integer offset = offsets.get(Preconditions.checkNotNull(key)); + requireNonNull(value); + final Integer offset = offsets.get(requireNonNull(key)); if (offset != null) { final Object obj = objects[offset]; @@ -260,6 +300,9 @@ public abstract class MutableOffsetMap extends AbstractMap implement } } + if (newKeys == null) { + newKeys = createNewKeys(); + } final V ret = newKeys.put(key, value); if (ret == null) { modCount++; @@ -291,6 +334,9 @@ public abstract class MutableOffsetMap extends AbstractMap implement } } + if (newKeys == null) { + return null; + } final V ret = newKeys.remove(key); if (ret != null) { modCount++; @@ -301,7 +347,9 @@ public abstract class MutableOffsetMap extends AbstractMap implement @Override public final void clear() { if (size() != 0) { - newKeys.clear(); + if (newKeys != null) { + newKeys.clear(); + } cloneArray(); Arrays.fill(objects, removedObject()); removed = objects.length; @@ -310,13 +358,13 @@ public abstract class MutableOffsetMap extends AbstractMap implement } @Override - public final Set> entrySet() { + public final @NonNull Set> entrySet() { return new EntrySet(); } @Override - public Map toUnmodifiableMap() { - if (removed == 0 && newKeys.isEmpty()) { + 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; @@ -354,12 +402,14 @@ public abstract class MutableOffsetMap extends AbstractMap implement } 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()) { @@ -367,16 +417,18 @@ public abstract class MutableOffsetMap extends AbstractMap implement if (o != null && !REMOVED.equals(o)) { @SuppressWarnings("unchecked") final V v = (V) o; - values[i++] = v; + 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 modifiedMap(keyset, values); @@ -390,10 +442,10 @@ public abstract class MutableOffsetMap extends AbstractMap implement try { ret = (MutableOffsetMap) super.clone(); } catch (CloneNotSupportedException e) { - throw new IllegalStateException("Clone is expected to work", e); + throw new IllegalStateException("Clone is expected to work", e); } - ret.newKeys = (HashMap) newKeys.clone(); + ret.newKeys = newKeys == null ? null : (HashMap) newKeys.clone(); ret.needClone = true; return ret; } @@ -409,53 +461,60 @@ public abstract class MutableOffsetMap extends AbstractMap implement } } - return result + newKeys.hashCode(); + return newKeys != null ? result + newKeys.hashCode() : result; } @Override - public final boolean equals(final Object o) { - if (o == this) { + public final boolean equals(final Object obj) { + if (obj == this) { return true; } - if (!(o instanceof Map)) { + if (!(obj instanceof Map)) { return false; } - if (o instanceof ImmutableOffsetMap) { - final ImmutableOffsetMap om = (ImmutableOffsetMap) o; + if (obj instanceof ImmutableOffsetMap) { + final ImmutableOffsetMap om = (ImmutableOffsetMap) obj; - if (newKeys.isEmpty() && offsets.equals(om.offsets())) { + if (noNewKeys() && offsets.equals(om.offsets())) { return Arrays.deepEquals(objects, om.objects()); } - } else if (o instanceof MutableOffsetMap) { - final MutableOffsetMap om = (MutableOffsetMap) o; + } else if (obj instanceof MutableOffsetMap) { + final MutableOffsetMap om = (MutableOffsetMap) obj; if (offsets.equals(om.offsets)) { - return Arrays.deepEquals(objects, om.objects) && newKeys.equals(om.newKeys); + return Arrays.deepEquals(objects, om.objects) && equalNewKeys(om); } } // Fall back to brute map compare - final Map other = (Map)o; + return mapEquals((Map)obj); + } + + private boolean equalNewKeys(final MutableOffsetMap other) { + return noNewKeys() ? other.noNewKeys() : newKeys.equals(other.newKeys()); + } + private boolean mapEquals(final Map other) { // Size and key sets have to match if (size() != other.size() || !keySet().equals(other.keySet())) { return false; } try { - // Ensure all newKeys are present. Note newKeys is guaranteed to - // not contain null value. - for (Entry e : newKeys.entrySet()) { - if (!e.getValue().equals(other.get(e.getKey()))) { - return false; + 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(other.get(e.getKey()))) { + return false; + } } } // Ensure all objects are present for (Entry e : offsets.entrySet()) { - final Object obj = objects[e.getValue()]; - if (obj != null && !REMOVED.equals(obj) && !obj.equals(other.get(e.getKey()))) { + final Object val = objects[e.getValue()]; + if (val != null && !REMOVED.equals(val) && !val.equals(other.get(e.getKey()))) { return false; } } @@ -468,7 +527,7 @@ public abstract class MutableOffsetMap extends AbstractMap implement } @Override - public final Set keySet() { + public final @NonNull Set keySet() { return new KeySet(); } @@ -484,13 +543,19 @@ public abstract class MutableOffsetMap extends AbstractMap implement @VisibleForTesting final Object newKeys() { - return 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(); @@ -505,6 +570,7 @@ public abstract class MutableOffsetMap extends AbstractMap implement } @Override + @SuppressWarnings("checkstyle:parameterName") public boolean contains(final Object o) { if (!(o instanceof Entry)) { return false; @@ -520,13 +586,15 @@ public abstract class MutableOffsetMap extends AbstractMap implement } @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; @@ -554,8 +622,8 @@ public abstract class MutableOffsetMap extends AbstractMap implement 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(); @@ -571,9 +639,11 @@ public abstract class MutableOffsetMap extends AbstractMap implement 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(); @@ -606,9 +676,8 @@ public abstract class MutableOffsetMap extends AbstractMap implement @Override public final void remove() { - Preconditions.checkState(currentKey != null); - checkModCount(); + checkState(currentKey != null); final Integer offset = offsets.get(currentKey); if (offset != null) { cloneArray();