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=2c3ea479a247f4f932aedcc71c6ead4e00676bc8;hb=24d06767f3a0ead8152a745fb05eda1d4a37ba77;hp=820f0ac992acc3635b5e2980cce3fd8f251f536c;hpb=c226b7d37ec0b55ddf13570d40d5c4d826ca34e1;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 820f0ac992..2c3ea479a2 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,68 @@ 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); + } + + @Override + SharedSingletonMap singletonMap() { + return SharedSingletonMap.orderedCopyOf(this); + } + } + + static final class Unordered extends MutableOffsetMap { + Unordered() { + super(new HashMap()); + } + + Unordered(final Map source) { + super(OffsetMapCache.unorderedOffsets(source.keySet()), source, new HashMap()); + } + + Unordered(final Map offsets, final V[] objects) { + super(offsets, objects, new HashMap()); + } + + @Override + Object removedObject() { + return null; + } + + @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)); + } + + @Override + UnmodifiableMapPhase unmodifiedMap(final Map offsets, final V[] objects) { + return new ImmutableOffsetMap.Unordered<>(offsets, objects); + } + + @Override + SharedSingletonMap singletonMap() { + return SharedSingletonMap.unorderedCopyOf(this); + } } 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; @@ -87,22 +143,59 @@ public abstract class MutableOffsetMap extends AbstractMap implement this.needClone = false; } + /** + * @deprecated Use {@link #orderedCopyOf(Map)} or {@link #unorderedCopyOf(Map)} instead. + */ + @Deprecated public static MutableOffsetMap copyOf(final Map m) { - if (m instanceof MutableOffsetMap) { - return ((MutableOffsetMap) m).clone(); + return orderedCopyOf(m); + } + + public static MutableOffsetMap orderedCopyOf(final Map m) { + if (m instanceof Ordered) { + return ((Ordered) m).clone(); } if (m instanceof ImmutableOffsetMap) { final ImmutableOffsetMap om = (ImmutableOffsetMap) m; - return new MutableOffsetMap.Ordered<>(om.offsets(), om.objects()); + return new Ordered<>(om.offsets(), om.objects()); } - return new MutableOffsetMap.Ordered<>(m); + return new Ordered<>(m); } + public static MutableOffsetMap unorderedCopyOf(final Map m) { + if (m instanceof Unordered) { + return ((Unordered) m).clone(); + } + if (m instanceof ImmutableOffsetMap) { + final ImmutableOffsetMap om = (ImmutableOffsetMap) m; + return new Unordered<>(om.offsets(), om.objects()); + } + + return new Unordered<>(m); + } + + /** + * @deprecated Use {@link #ordered()} or {@link #unordered()} instead. + */ + @Deprecated public static MutableOffsetMap of() { + return ordered(); + } + + public static MutableOffsetMap ordered() { return new MutableOffsetMap.Ordered<>(); } + public static MutableOffsetMap unordered() { + return new MutableOffsetMap.Unordered<>(); + } + + abstract Object removedObject(); + abstract UnmodifiableMapPhase modifiedMap(List keys, V[] objects); + abstract UnmodifiableMapPhase unmodifiedMap(Map offsets, V[] objects); + abstract SharedSingletonMap singletonMap(); + @Override public final int size() { return offsets.size() + newKeys.size() - removed; @@ -116,13 +209,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 +250,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 +332,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 +353,16 @@ public abstract class MutableOffsetMap extends AbstractMap 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 (objects[e.getValue()] != null) { + final Object o = objects[e.getValue()]; + if (o != null && !REMOVED.equals(o)) { keyset.add(e.getKey()); } } @@ -237,9 +379,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 +395,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 +470,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 +598,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 +628,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();