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=4be9ed99cc41f849d8f8e83515bb094c7d763f50;hpb=94ce73de754dde1d931d7d19e6eeb79de997bdef;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 4be9ed99cc..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,21 +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 @@ -33,84 +40,189 @@ import java.util.Set; * * results in source and result sharing the backing objects. * + *

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 class MutableOffsetMap extends AbstractLazyValueMap implements Cloneable, ModifiableMapPhase { +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); + } + + @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<>(); + } + } + + 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); + } + + @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 NO_VALUE = new Object(); - private final Map offsets; - private final Map newKeys; + 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; - public MutableOffsetMap() { - this(Collections.emptySet()); + MutableOffsetMap(final ImmutableMap offsets, final Object[] objects) { + this.offsets = requireNonNull(offsets); + this.objects = requireNonNull(objects); } - protected MutableOffsetMap(final Collection keySet) { - if (!keySet.isEmpty()) { - removed = keySet.size(); - offsets = OffsetMapCache.offsetsFor(keySet); - objects = new Object[removed]; - Arrays.fill(objects, NO_VALUE); - } else { - offsets = ImmutableMap.of(); - objects = EMPTY_ARRAY; - } - - this.newKeys = new LinkedHashMap<>(); + MutableOffsetMap() { + this(ImmutableMap.of(), EMPTY_ARRAY); } - protected MutableOffsetMap(final ImmutableOffsetMap m) { - this(m.offsets(), m.objects()); - } + MutableOffsetMap(final ImmutableMap offsets, final Map source) { + this(offsets, new Object[offsets.size()]); - protected MutableOffsetMap(final Map m) { - this(OffsetMapCache.offsetsFor(m.keySet()), m.values().toArray()); - } + for (Entry e : source.entrySet()) { + objects[offsets.get(e.getKey())] = requireNonNull(e.getValue()); + } - protected MutableOffsetMap(final MutableOffsetMap m) { - this.offsets = m.offsets; - this.objects = m.objects; - this.newKeys = new LinkedHashMap<>(m.newKeys); - this.removed = m.removed; + this.needClone = false; } - private MutableOffsetMap(final Map offsets, final Object[] 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) { - final Object[] objects = new Object[offsets.size()]; - Arrays.fill(objects, NO_VALUE); - - 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 final int size() { - return offsets.size() + newKeys.size() - removed; + return offsets.size() - removed + (newKeys == null ? 0 : newKeys.size()); } @Override @@ -121,34 +233,41 @@ public class MutableOffsetMap extends AbstractLazyValueMap implement @Override public final boolean containsKey(final Object key) { final Integer offset = offsets.get(key); - if (offset == null) { - return newKeys.containsKey(key); + if (offset != null) { + final Object obj = objects[offset]; + if (!REMOVED.equals(obj)) { + return obj != null; + } } - return !NO_VALUE.equals(objects[offset]); + return newKeys != null && newKeys.containsKey(key); } @Override public final V get(final Object key) { final Integer offset = offsets.get(key); - if (offset == null) { - return newKeys.get(key); - } + if (offset != null) { + final Object obj = objects[offset]; - final Object o = objects[offset]; - if (!NO_VALUE.equals(o)) { - @SuppressWarnings("unchecked") - final K k = (K)key; - return objectToValue(k, o); - } else { - return null; + /* + * 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(); } } @@ -156,80 +275,109 @@ public class MutableOffsetMap extends AbstractLazyValueMap implement @Override public final 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++; + 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 Object ret = objects[offset]; - objects[offset] = valueToObject(value); - if (NO_VALUE.equals(ret)) { + if (newKeys == null) { + newKeys = createNewKeys(); + } + final V ret = newKeys.put(key, value); + if (ret == null) { modCount++; - removed--; - return null; } - - return objectToValue(key, ret); + return ret; } @Override 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 Object ret = objects[offset]; - objects[offset] = NO_VALUE; - if (!NO_VALUE.equals(ret)) { - modCount++; - removed++; - @SuppressWarnings("unchecked") - final K k = (K)key; - return objectToValue(k, ret); - } else { + if (newKeys == null) { return null; } + final V ret = newKeys.remove(key); + if (ret != null) { + modCount++; + } + return ret; } @Override public final void clear() { if (size() != 0) { - newKeys.clear(); + if (newKeys != null) { + newKeys.clear(); + } cloneArray(); - Arrays.fill(objects, NO_VALUE); + Arrays.fill(objects, removedObject()); removed = objects.length; modCount++; } } @Override - public final Set> entrySet() { + public final @NonNull Set> entrySet() { return new EntrySet(); } @Override - public final 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(); @@ -237,15 +385,16 @@ public class MutableOffsetMap extends AbstractLazyValueMap implement 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 (!NO_VALUE.equals(objects[e.getValue()])) { + final Object o = objects[e.getValue()]; + if (o != null && !REMOVED.equals(o)) { keyset.add(e.getKey()); } } @@ -253,131 +402,160 @@ public class MutableOffsetMap extends AbstractLazyValueMap implement } else { keyset.addAll(offsets.keySet()); } - keyset.addAll(newKeys.keySet()); + if (newKeys != null) { + keyset.addAll(newKeys.keySet()); + } // Construct the values - final Object[] values = new Object[keyset.size()]; - int i = 0; + @SuppressWarnings("unchecked") + final V[] values = (V[])new Object[keyset.size()]; + int offset = 0; if (removed != 0) { if (removed != offsets.size()) { for (Entry e : offsets.entrySet()) { final Object o = objects[e.getValue()]; - if (!NO_VALUE.equals(o)) { - values[i++] = o; + 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++] = valueToObject(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() { - 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()) { final Object v = objects[e.getValue()]; - if (!NO_VALUE.equals(v)) { - result += e.getKey().hashCode() ^ objectToValue(e.getKey(), v).hashCode(); + if (v != null) { + result += e.getKey().hashCode() ^ v.hashCode(); } } - 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); + } - try { - // Ensure all newKeys are present. Note newKeys is guaranteed to - // not contain null value. + 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 { + 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 Object obj = objects[e.getValue()]; - if (!NO_VALUE.equals(obj)) { - final V v = objectToValue(e.getKey(), obj); - if (!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 final 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(); @@ -392,6 +570,7 @@ public class MutableOffsetMap extends AbstractLazyValueMap implement } @Override + @SuppressWarnings("checkstyle:parameterName") public boolean contains(final Object o) { if (!(o instanceof Entry)) { return false; @@ -407,13 +586,15 @@ public class MutableOffsetMap extends AbstractLazyValueMap 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; @@ -441,8 +622,8 @@ public class MutableOffsetMap extends AbstractLazyValueMap 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(); @@ -458,9 +639,11 @@ public class MutableOffsetMap extends AbstractLazyValueMap 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(); @@ -469,7 +652,8 @@ public class MutableOffsetMap extends AbstractLazyValueMap implement private void updateNextKey() { while (oldIterator.hasNext()) { final Entry e = oldIterator.next(); - if (!NO_VALUE.equals(objects[e.getValue()])) { + final Object obj = objects[e.getValue()]; + if (obj != null && !REMOVED.equals(obj)) { nextKey = e.getKey(); return; } @@ -492,13 +676,12 @@ public class MutableOffsetMap extends AbstractLazyValueMap implement @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] = NO_VALUE; + objects[offset] = removedObject(); removed++; } else { newIterator.remove();