From 136f1755f17cfe70dfe854e9d886ac0eedf97c19 Mon Sep 17 00:00:00 2001 From: Robert Varga Date: Mon, 21 Dec 2015 18:06:55 +0100 Subject: [PATCH] BUG-4803: fix MutableOffsetMap's insertion order When a pairing backed by the array is removed, the order of pairings would not follow the insertion order. This patch introduces an explicit removal marker object and when the marker is present we defer to newKeys map. Change-Id: Ib27313e0df44754f5219d64126e0ec2a472a503f Signed-off-by: Robert Varga --- .../yangtools/util/MutableOffsetMap.java | 152 +++++++++++++----- .../yangtools/util/OffsetMapTest.java | 26 +-- 2 files changed, 125 insertions(+), 53 deletions(-) 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 820f0ac992..b49b51d493 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 @@ -16,11 +16,11 @@ import java.util.AbstractMap; import java.util.AbstractSet; import java.util.ArrayList; import java.util.Arrays; -import java.util.Collection; 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; @@ -54,12 +54,28 @@ public abstract class MutableOffsetMap extends AbstractMap implement Ordered(final Map offsets, final V[] objects) { super(offsets, objects, new LinkedHashMap()); } + + @Override + Object removedObject() { + return REMOVED; + } + + @Override + UnmodifiableMapPhase modifiedMap(final List keys, final V[] objects) { + return new ImmutableOffsetMap.Ordered<>(OffsetMapCache.orderedOffsets(keys), objects); + } + + @Override + UnmodifiableMapPhase unmodifiedMap(final Map offsets, final V[] objects) { + return new ImmutableOffsetMap.Ordered<>(offsets, objects); + } } private static final Object[] EMPTY_ARRAY = new Object[0]; + private static final Object REMOVED = new Object(); private final Map offsets; private HashMap newKeys; - private V[] objects; + private Object[] objects; private int removed = 0; private transient volatile int modCount; private boolean needClone = true; @@ -103,6 +119,10 @@ public abstract class MutableOffsetMap extends AbstractMap implement return new MutableOffsetMap.Ordered<>(); } + abstract Object removedObject(); + abstract UnmodifiableMapPhase modifiedMap(List keys, V[] objects); + abstract UnmodifiableMapPhase unmodifiedMap(Map offsets, V[] objects); + @Override public final int size() { return offsets.size() + newKeys.size() - removed; @@ -116,13 +136,35 @@ public abstract class MutableOffsetMap extends AbstractMap implement @Override 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.containsKey(key); } @Override 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.get(key); } private void cloneArray() { @@ -135,55 +177,76 @@ public abstract class MutableOffsetMap extends AbstractMap implement } @Override - public V put(final K key, final V value) { + 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++; + 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; + 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; + 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(); cloneArray(); - Arrays.fill(objects, null); + Arrays.fill(objects, removedObject()); removed = objects.length; modCount++; } @@ -196,15 +259,20 @@ public abstract class MutableOffsetMap extends AbstractMap implement @Override public Map toUnmodifiableMap() { - if (newKeys.isEmpty() && removed == 0) { + if (removed == 0 && newKeys.isEmpty()) { // 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.Ordered<>(offsets, objects); + return unmodifiedMap(offsets, values); } final int s = size(); @@ -212,15 +280,16 @@ public abstract class MutableOffsetMap extends AbstractMap implement return ImmutableMap.of(); } if (s == 1) { - return ImmutableMap.copyOf(this); + return SharedSingletonMap.copyOf(this); } // 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()); } } @@ -237,9 +306,11 @@ public abstract class MutableOffsetMap extends AbstractMap implement 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[i++] = v; } } } @@ -251,7 +322,7 @@ public abstract class MutableOffsetMap extends AbstractMap implement values[i++] = v; } - return new ImmutableOffsetMap.Ordered<>(OffsetMapCache.orderedOffsets(keyset), values); + return modifiedMap(keyset, values); } @SuppressWarnings("unchecked") @@ -326,8 +397,8 @@ public abstract class MutableOffsetMap extends AbstractMap implement // Ensure all objects are present for (Entry e : offsets.entrySet()) { - final V v = objects[e.getValue()]; - if (v != null && !v.equals(other.get(e.getKey()))) { + final Object obj = objects[e.getValue()]; + if (obj != null && !REMOVED.equals(obj) && !obj.equals(other.get(e.getKey()))) { return false; } } @@ -454,7 +525,8 @@ public abstract class MutableOffsetMap extends AbstractMap implement 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; } @@ -483,7 +555,7 @@ public abstract class MutableOffsetMap extends AbstractMap implement final Integer offset = offsets.get(currentKey); if (offset != null) { cloneArray(); - objects[offset] = null; + objects[offset] = removedObject(); removed++; } else { newIterator.remove(); diff --git a/common/util/src/test/java/org/opendaylight/yangtools/util/OffsetMapTest.java b/common/util/src/test/java/org/opendaylight/yangtools/util/OffsetMapTest.java index 17a6f2e1ed..578b87bc14 100644 --- a/common/util/src/test/java/org/opendaylight/yangtools/util/OffsetMapTest.java +++ b/common/util/src/test/java/org/opendaylight/yangtools/util/OffsetMapTest.java @@ -15,6 +15,7 @@ import static org.junit.Assert.assertSame; import static org.junit.Assert.assertTrue; import static org.junit.Assert.fail; import com.google.common.collect.ImmutableMap; +import com.google.common.collect.Iterables; import com.google.common.collect.Iterators; import java.io.ByteArrayInputStream; import java.io.ByteArrayOutputStream; @@ -326,14 +327,11 @@ public class OffsetMapTest { mutable.put("k1", "v1"); final ImmutableOffsetMap result = (ImmutableOffsetMap) mutable.toUnmodifiableMap(); - assertEquals(source, result); + assertTrue(source.equals(result)); + assertTrue(result.equals(source)); - // Only offsets should be shared - assertSame(source.offsets(), result.offsets()); - assertNotSame(source.objects(), result.objects()); - - // Iterator order needs to be preserved - assertTrue(Iterators.elementsEqual(source.entrySet().iterator(), result.entrySet().iterator())); + // Iterator order must not be preserved + assertFalse(Iterators.elementsEqual(source.entrySet().iterator(), result.entrySet().iterator())); } @Test @@ -366,7 +364,7 @@ public class OffsetMapTest { final Map result = mutable.toUnmodifiableMap(); // Should devolve to a singleton - assertTrue(result instanceof ImmutableMap); + assertTrue(result instanceof SharedSingletonMap); assertEquals(ImmutableMap.of("k2", "v2"), result); } @@ -404,14 +402,14 @@ public class OffsetMapTest { mutable.put("k3", "v3"); mutable.put("k1", "v1"); - assertEquals(ImmutableMap.of("k3", "v3"), mutable.newKeys()); + assertEquals(ImmutableMap.of("k1", "v1", "k3", "v3"), mutable.newKeys()); final Map result = mutable.toUnmodifiableMap(); assertTrue(result instanceof ImmutableOffsetMap); assertEquals(threeEntryMap, result); assertEquals(result, threeEntryMap); - assertTrue(Iterators.elementsEqual(threeEntryMap.entrySet().iterator(), result.entrySet().iterator())); + assertFalse(Iterators.elementsEqual(threeEntryMap.entrySet().iterator(), result.entrySet().iterator())); } @Test @@ -456,10 +454,12 @@ public class OffsetMapTest { assertFalse(source.needClone()); assertTrue(result.needClone()); - // Creates a immutable view, which shares the array + // Forced copy, no cloning needed, but maps are equal final ImmutableOffsetMap immutable = (ImmutableOffsetMap) source.toUnmodifiableMap(); - assertTrue(source.needClone()); - assertSame(source.array(), immutable.objects()); + assertFalse(source.needClone()); + assertTrue(source.equals(immutable)); + assertTrue(immutable.equals(source)); + assertTrue(Iterables.elementsEqual(source.entrySet(), immutable.entrySet())); } @Test -- 2.36.6