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();