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=ccbc58aa197a18930106c17256b9308732469d8f;hp=8a04f3230784366401ad6e8b1c85831eb893af34;hpb=8f2876d895936b36aba1fc3ec65b18900e559184;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 8a04f32307..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,16 +7,18 @@
  */
 package org.opendaylight.yangtools.util;
 
-import static com.google.common.base.Verify.verify;
+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.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;
@@ -25,7 +27,8 @@ import java.util.List;
 import java.util.Map;
 import java.util.NoSuchElementException;
 import java.util.Set;
-import javax.annotation.Nonnull;
+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
@@ -46,15 +49,14 @@ import javax.annotation.Nonnull;
 public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implements Cloneable, ModifiableMapPhase<K, V> {
     static final class Ordered<K, V> extends MutableOffsetMap<K, V> {
         Ordered() {
-            super(new LinkedHashMap<>());
         }
 
         Ordered(final Map<K, V> source) {
-            super(OffsetMapCache.orderedOffsets(source.keySet()), source, new LinkedHashMap<>());
+            super(OffsetMapCache.orderedOffsets(source.keySet()), source);
         }
 
-        Ordered(final Map<K, Integer> offsets, final V[] objects) {
-            super(offsets, objects, new LinkedHashMap<>());
+        Ordered(final ImmutableMap<K, Integer> offsets, final V[] objects) {
+            super(offsets, objects);
         }
 
         @Override
@@ -63,32 +65,36 @@ public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implement
         }
 
         @Override
-        UnmodifiableMapPhase<K, V> modifiedMap(final List<K> keys, final V[] objects) {
-            return new ImmutableOffsetMap.Ordered<>(OffsetMapCache.orderedOffsets(keys), objects);
+        UnmodifiableMapPhase<K, V> modifiedMap(final List<K> keys, final V[] values) {
+            return new ImmutableOffsetMap.Ordered<>(OffsetMapCache.orderedOffsets(keys), values);
         }
 
         @Override
-        UnmodifiableMapPhase<K, V> unmodifiedMap(final Map<K, Integer> offsets, final V[] objects) {
-            return new ImmutableOffsetMap.Ordered<>(offsets, objects);
+        UnmodifiableMapPhase<K, V> unmodifiedMap(final ImmutableMap<K, Integer> offsetMap, final V[] values) {
+            return new ImmutableOffsetMap.Ordered<>(offsetMap, values);
         }
 
         @Override
         SharedSingletonMap<K, V> singletonMap() {
             return SharedSingletonMap.orderedCopyOf(this);
         }
+
+        @Override
+        HashMap<K, V> createNewKeys() {
+            return new LinkedHashMap<>();
+        }
     }
 
     static final class Unordered<K, V> extends MutableOffsetMap<K, V> {
         Unordered() {
-            super(new HashMap<>());
         }
 
         Unordered(final Map<K, V> source) {
-            super(OffsetMapCache.unorderedOffsets(source.keySet()), source, new HashMap<>());
+            super(OffsetMapCache.unorderedOffsets(source.keySet()), source);
         }
 
-        Unordered(final Map<K, Integer> offsets, final V[] objects) {
-            super(offsets, objects, new HashMap<>());
+        Unordered(final ImmutableMap<K, Integer> offsets, final V[] objects) {
+            super(offsets, objects);
         }
 
         @Override
@@ -97,46 +103,51 @@ public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implement
         }
 
         @Override
-        UnmodifiableMapPhase<K, V> modifiedMap(final List<K> keys, final V[] objects) {
-            final Map<K, Integer> offsets = OffsetMapCache.unorderedOffsets(keys);
-            return new ImmutableOffsetMap.Unordered<>(offsets, OffsetMapCache.adjustedArray(offsets, keys, objects));
+        UnmodifiableMapPhase<K, V> modifiedMap(final List<K> keys, final V[] values) {
+            final ImmutableMap<K, Integer> offsets = OffsetMapCache.unorderedOffsets(keys);
+            return new ImmutableOffsetMap.Unordered<>(offsets, OffsetMapCache.adjustedArray(offsets, keys, values));
         }
 
         @Override
-        UnmodifiableMapPhase<K, V> unmodifiedMap(final Map<K, Integer> offsets, final V[] objects) {
-            return new ImmutableOffsetMap.Unordered<>(offsets, objects);
+        UnmodifiableMapPhase<K, V> unmodifiedMap(final ImmutableMap<K, Integer> offsetMap, final V[] values) {
+            return new ImmutableOffsetMap.Unordered<>(offsetMap, values);
         }
 
         @Override
         SharedSingletonMap<K, V> singletonMap() {
             return SharedSingletonMap.unorderedCopyOf(this);
         }
+
+        @Override
+        HashMap<K, V> createNewKeys() {
+            return new HashMap<>();
+        }
     }
 
     private static final Object[] EMPTY_ARRAY = new Object[0];
     private static final Object REMOVED = new Object();
-    private final Map<K, Integer> offsets;
+
+    private final ImmutableMap<K, Integer> offsets;
     private HashMap<K, V> 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<K, Integer> offsets, final V[] objects, final HashMap<K, V> newKeys) {
-        verify(newKeys.isEmpty());
+    MutableOffsetMap(final ImmutableMap<K, Integer> offsets, final Object[] objects) {
         this.offsets = requireNonNull(offsets);
         this.objects = requireNonNull(objects);
-        this.newKeys = requireNonNull(newKeys);
     }
 
-    @SuppressWarnings("unchecked")
-    MutableOffsetMap(final HashMap<K, V> newKeys) {
-        this(ImmutableMap.of(), (V[]) EMPTY_ARRAY, newKeys);
+    MutableOffsetMap() {
+        this(ImmutableMap.of(), EMPTY_ARRAY);
     }
 
-    @SuppressWarnings("unchecked")
-    MutableOffsetMap(final Map<K, Integer> offsets, final Map<K, V> source, final HashMap<K, V> newKeys) {
-        this(offsets, (V[]) new Object[offsets.size()], newKeys);
+    MutableOffsetMap(final ImmutableMap<K, Integer> offsets, final Map<K, V> source) {
+        this(offsets, new Object[offsets.size()]);
 
         for (Entry<K, V> e : source.entrySet()) {
             objects[offsets.get(e.getKey())] = requireNonNull(e.getValue());
@@ -145,7 +156,14 @@ public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implement
         this.needClone = false;
     }
 
-    public static <K, V> MutableOffsetMap<K, V> orderedCopyOf(final Map<K, V> map) {
+    /**
+     * 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 <K, V> @NonNull MutableOffsetMap<K, V> orderedCopyOf(final Map<K, V> map) {
         if (map instanceof Ordered) {
             return ((Ordered<K, V>) map).clone();
         }
@@ -157,7 +175,14 @@ public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implement
         return new Ordered<>(map);
     }
 
-    public static <K, V> MutableOffsetMap<K, V> unorderedCopyOf(final Map<K, V> map) {
+    /**
+     * 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 <K, V> @NonNull MutableOffsetMap<K, V> unorderedCopyOf(final Map<K, V> map) {
         if (map instanceof Unordered) {
             return ((Unordered<K, V>) map).clone();
         }
@@ -169,25 +194,35 @@ public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implement
         return new Unordered<>(map);
     }
 
-    public static <K, V> MutableOffsetMap<K, V> ordered() {
+    /**
+     * Create an empty {@link MutableOffsetMap} which has an iteration order matching the insertion order.
+     *
+     * @return MutableOffsetMap which preserves insertion order
+     */
+    public static <K, V> @NonNull MutableOffsetMap<K, V> ordered() {
         return new MutableOffsetMap.Ordered<>();
     }
 
-    public static <K, V> MutableOffsetMap<K, V> unordered() {
+    /**
+     * Create an empty {@link MutableOffsetMap} which has unspecified iteration order.
+     *
+     * @return An MutableOffsetMap
+     */
+    public static <K, V> @NonNull MutableOffsetMap<K, V> unordered() {
         return new MutableOffsetMap.Unordered<>();
     }
 
     abstract Object removedObject();
 
-    abstract UnmodifiableMapPhase<K, V> modifiedMap(List<K> keys, V[] objects);
+    abstract UnmodifiableMapPhase<K, V> modifiedMap(List<K> keys, V[] values);
 
-    abstract UnmodifiableMapPhase<K, V> unmodifiedMap(Map<K, Integer> offsets, V[] objects);
+    abstract UnmodifiableMapPhase<K, V> unmodifiedMap(ImmutableMap<K, Integer> offsetMap, V[] values);
 
     abstract SharedSingletonMap<K, V> singletonMap();
 
     @Override
     public final int size() {
-        return offsets.size() + newKeys.size() - removed;
+        return offsets.size() - removed + (newKeys == null ? 0 : newKeys.size());
     }
 
     @Override
@@ -205,7 +240,7 @@ public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implement
             }
         }
 
-        return newKeys.containsKey(key);
+        return newKeys != null && newKeys.containsKey(key);
     }
 
     @Override
@@ -226,13 +261,13 @@ public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> 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();
             }
         }
@@ -265,6 +300,9 @@ public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implement
             }
         }
 
+        if (newKeys == null) {
+            newKeys = createNewKeys();
+        }
         final V ret = newKeys.put(key, value);
         if (ret == null) {
             modCount++;
@@ -296,6 +334,9 @@ public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implement
             }
         }
 
+        if (newKeys == null) {
+            return null;
+        }
         final V ret = newKeys.remove(key);
         if (ret != null) {
             modCount++;
@@ -306,7 +347,9 @@ public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implement
     @Override
     public final void clear() {
         if (size() != 0) {
-            newKeys.clear();
+            if (newKeys != null) {
+                newKeys.clear();
+            }
             cloneArray();
             Arrays.fill(objects, removedObject());
             removed = objects.length;
@@ -314,16 +357,14 @@ public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implement
         }
     }
 
-    @Nonnull
     @Override
-    public final Set<Entry<K, V>> entrySet() {
+    public final @NonNull Set<Entry<K, V>> entrySet() {
         return new EntrySet();
     }
 
-    @Nonnull
     @Override
-    public Map<K, V> toUnmodifiableMap() {
-        if (removed == 0 && newKeys.isEmpty()) {
+    public @NonNull Map<K, V> toUnmodifiableMap() {
+        if (removed == 0 && noNewKeys()) {
             // Make sure next modification clones the array, as we leak it to the map we return.
             needClone = true;
 
@@ -361,7 +402,9 @@ public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implement
         } else {
             keyset.addAll(offsets.keySet());
         }
-        keyset.addAll(newKeys.keySet());
+        if (newKeys != null) {
+            keyset.addAll(newKeys.keySet());
+        }
 
         // Construct the values
         @SuppressWarnings("unchecked")
@@ -382,8 +425,10 @@ public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implement
             System.arraycopy(objects, 0, values, 0, offsets.size());
             offset = offsets.size();
         }
-        for (V v : newKeys.values()) {
-            values[offset++] = v;
+        if (newKeys != null) {
+            for (V v : newKeys.values()) {
+                values[offset++] = v;
+            }
         }
 
         return modifiedMap(keyset, values);
@@ -400,7 +445,7 @@ public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implement
             throw new IllegalStateException("Clone is expected to work", e);
         }
 
-        ret.newKeys = (HashMap<K, V>) newKeys.clone();
+        ret.newKeys = newKeys == null ? null : (HashMap<K, V>) newKeys.clone();
         ret.needClone = true;
         return ret;
     }
@@ -416,7 +461,7 @@ public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implement
             }
         }
 
-        return result + newKeys.hashCode();
+        return newKeys != null ? result + newKeys.hashCode() : result;
     }
 
     @Override
@@ -431,31 +476,38 @@ public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implement
         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 (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<?, ?>)obj;
+        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<K, V> 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<K, V> e : newKeys.entrySet()) {
+                    if (!e.getValue().equals(other.get(e.getKey()))) {
+                        return false;
+                    }
                 }
             }
 
@@ -474,9 +526,8 @@ public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implement
         return true;
     }
 
-    @Nonnull
     @Override
-    public final Set<K> keySet() {
+    public final @NonNull Set<K> keySet() {
         return new KeySet();
     }
 
@@ -492,14 +543,19 @@ public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implement
 
     @VisibleForTesting
     final Object newKeys() {
-        return newKeys;
+        return newKeys != null ? newKeys : ImmutableMap.of();
+    }
+
+    abstract HashMap<K, V> createNewKeys();
+
+    private boolean noNewKeys() {
+        return newKeys == null || newKeys.isEmpty();
     }
 
     private final class EntrySet extends AbstractSet<Entry<K, V>> {
-        @Nonnull
         @Override
-        public Iterator<Entry<K, V>> iterator() {
-            return new AbstractSetIterator<Entry<K, V>>() {
+        public @NonNull Iterator<Entry<K, V>> iterator() {
+            return new AbstractSetIterator<>() {
                 @Override
                 public Entry<K, V> next() {
                     final K key = nextKey();
@@ -565,10 +621,9 @@ public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implement
     }
 
     private final class KeySet extends AbstractSet<K> {
-        @Nonnull
         @Override
-        public Iterator<K> iterator() {
-            return new AbstractSetIterator<K>() {
+        public @NonNull Iterator<K> iterator() {
+            return new AbstractSetIterator<>() {
                 @Override
                 public K next() {
                     return nextKey();
@@ -584,10 +639,11 @@ public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implement
 
     private abstract class AbstractSetIterator<E> implements Iterator<E> {
         private final Iterator<Entry<K, Integer>> oldIterator = offsets.entrySet().iterator();
-        private final Iterator<K> newIterator = newKeys.keySet().iterator();
+        private final Iterator<K> newIterator = newKeys == null ? Collections.emptyIterator()
+                : newKeys.keySet().iterator();
         private int expectedModCount = modCount;
-        private K currentKey;
-        private K nextKey;
+        private @Nullable K currentKey = null;
+        private @Nullable K nextKey;
 
         AbstractSetIterator() {
             updateNextKey();
@@ -620,9 +676,8 @@ public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implement
 
         @Override
         public final void remove() {
-            requireNonNull(currentKey != null);
-
             checkModCount();
+            checkState(currentKey != null);
             final Integer offset = offsets.get(currentKey);
             if (offset != null) {
                 cloneArray();