X-Git-Url: https://git.opendaylight.org/gerrit/gitweb?a=blobdiff_plain;f=common%2Futil%2Fsrc%2Fmain%2Fjava%2Forg%2Fopendaylight%2Fyangtools%2Futil%2FImmutableOffsetMap.java;h=66b20fbdf1ec9be8cdb47ef557bc897be1b08d38;hb=refs%2Fchanges%2F71%2F99871%2F2;hp=2dec7ad70949a1ad8cbe591c7e361bc9c26daf1f;hpb=e7aa654c5595fc308af003cd77ff70d176788aa8;p=yangtools.git

diff --git a/common/util/src/main/java/org/opendaylight/yangtools/util/ImmutableOffsetMap.java b/common/util/src/main/java/org/opendaylight/yangtools/util/ImmutableOffsetMap.java
index 2dec7ad709..66b20fbdf1 100644
--- a/common/util/src/main/java/org/opendaylight/yangtools/util/ImmutableOffsetMap.java
+++ b/common/util/src/main/java/org/opendaylight/yangtools/util/ImmutableOffsetMap.java
@@ -7,10 +7,13 @@
  */
 package org.opendaylight.yangtools.util;
 
+import static com.google.common.base.Preconditions.checkArgument;
+import static java.util.Objects.requireNonNull;
+
 import com.google.common.annotations.Beta;
-import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.UnmodifiableIterator;
+import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
 import java.io.IOException;
 import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
@@ -25,13 +28,18 @@ import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
-import javax.annotation.Nonnull;
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.jdt.annotation.Nullable;
 
 /**
  * Implementation of the {@link Map} interface which stores a set of immutable mappings using a key-to-offset map and
  * a backing array. This is useful for situations where the same key set is shared across a multitude of maps, as this
  * class uses a global cache to share the key-to-offset mapping.
  *
+ * <p>
+ * In case the set of keys is statically known, you can use {@link ImmutableOffsetMapTemplate} to efficiently create
+ * {@link ImmutableOffsetMap} instances.
+ *
  * @param <K> the type of keys maintained by this map
  * @param <V> the type of mapped values
  */
@@ -40,21 +48,48 @@ public abstract class ImmutableOffsetMap<K, V> implements UnmodifiableMapPhase<K
     static final class Ordered<K, V> extends ImmutableOffsetMap<K, V> {
         private static final long serialVersionUID = 1L;
 
-        Ordered(final Map<K, Integer> offsets, final V[] objects) {
+        Ordered(final ImmutableMap<K, Integer> offsets, final V[] objects) {
             super(offsets, objects);
         }
 
         @Override
-        public MutableOffsetMap<K, V> toModifiableMap() {
-            return MutableOffsetMap.copyOf(this);
+        public @NonNull MutableOffsetMap<K, V> toModifiableMap() {
+            return MutableOffsetMap.orderedCopyOf(this);
+        }
+
+        @Override
+        void setFields(final List<K> keys, final V[] values) throws IOException {
+            setField(this, OFFSETS_FIELD, OffsetMapCache.orderedOffsets(keys));
+            setField(this, ARRAY_FIELD, values);
+        }
+    }
+
+    static final class Unordered<K, V> extends ImmutableOffsetMap<K, V> {
+        private static final long serialVersionUID = 1L;
+
+        Unordered(final ImmutableMap<K, Integer> offsets, final V[] objects) {
+            super(offsets, objects);
+        }
+
+        @Override
+        public @NonNull MutableOffsetMap<K, V> toModifiableMap() {
+            return MutableOffsetMap.unorderedCopyOf(this);
+        }
+
+        @Override
+        void setFields(final List<K> keys, final V[] values) throws IOException {
+            final Map<K, Integer> newOffsets = OffsetMapCache.unorderedOffsets(keys);
+
+            setField(this, OFFSETS_FIELD, newOffsets);
+            setField(this, ARRAY_FIELD, OffsetMapCache.adjustedArray(newOffsets, keys, values));
         }
     }
 
     private static final long serialVersionUID = 1L;
 
-    private final Map<K, Integer> offsets;
-    private final V[] objects;
-    private int hashCode;
+    private final transient @NonNull ImmutableMap<K, Integer> offsets;
+    private final transient @NonNull V[] objects;
+    private transient int hashCode;
 
     /**
      * Construct a new instance backed by specified key-to-offset map and array of objects.
@@ -63,56 +98,107 @@ public abstract class ImmutableOffsetMap<K, V> implements UnmodifiableMapPhase<K
      * @param objects Array of value object, may not be null. The array is stored as is, the caller
      *              is responsible for ensuring its contents remain unmodified.
      */
-    ImmutableOffsetMap(@Nonnull final Map<K, Integer> offsets, @Nonnull final V[] objects) {
-        this.offsets = Preconditions.checkNotNull(offsets);
-        this.objects = Preconditions.checkNotNull(objects);
-        Preconditions.checkArgument(offsets.size() == objects.length);
+    ImmutableOffsetMap(final ImmutableMap<K, Integer> offsets, final V[] objects) {
+        this.offsets = requireNonNull(offsets);
+        this.objects = requireNonNull(objects);
+        checkArgument(offsets.size() == objects.length);
     }
 
     @Override
-    public abstract MutableOffsetMap<K, V> toModifiableMap();
+    public abstract @NonNull MutableOffsetMap<K, V> toModifiableMap();
+
+    abstract void setFields(List<K> keys, V[] values) throws IOException;
 
     /**
-     * Create an {@link ImmutableOffsetMap} as a copy of an existing map. This is actually not completely true,
-     * as this method returns an {@link ImmutableMap} for empty and singleton inputs, as those are more memory-efficient.
-     * This method also recognizes {@link ImmutableOffsetMap} on input, and returns it back without doing anything else.
-     * It also recognizes {@link MutableOffsetMap} (as returned by {@link #toModifiableMap()}) and makes an efficient
-     * copy of its contents. All other maps are converted to an {@link ImmutableOffsetMap} with the same iteration
-     * order as input.
+     * Create an {@link ImmutableOffsetMap} as a copy of an existing map. This is actually not completely true, as this
+     * method returns an {@link ImmutableMap} for empty and singleton inputs, as those are more memory-efficient. This
+     * method also recognizes {@link ImmutableOffsetMap} and {@link SharedSingletonMap} on input, and returns it back
+     * without doing anything else. It also recognizes {@link MutableOffsetMap} (as returned by
+     * {@link #toModifiableMap()}) and makes an efficient copy of its contents. All other maps are converted to an
+     * {@link ImmutableOffsetMap} with the same iteration order as input.
      *
-     * @param m Input map, may not be null.
+     * @param <K> the type of keys maintained by the map
+     * @param <V> the type of mapped values
+     * @param map Input map, may not be null.
      * @return An isolated, immutable copy of the input map
+     * @throws NullPointerException if {@code map} or any of its elements is null.
      */
-    @Nonnull public static <K, V> Map<K, V> copyOf(@Nonnull final Map<K, V> m) {
-        // Prevent a copy. Note that ImmutableMap is not listed here because of its potentially larger keySet overhead.
-        if (m instanceof ImmutableOffsetMap || m instanceof SharedSingletonMap) {
-            return m;
+    public static <K, V> @NonNull Map<K, V> orderedCopyOf(final @NonNull Map<K, V> map) {
+        final Map<K, V> common = commonCopy(map);
+        if (common != null) {
+            return common;
         }
 
-        // Familiar and efficient to copy
-        if (m instanceof MutableOffsetMap) {
-            return ((MutableOffsetMap<K, V>) m).toUnmodifiableMap();
+        final int size = map.size();
+        if (size == 1) {
+            // Efficient single-entry implementation
+            final Entry<K, V> e = map.entrySet().iterator().next();
+            return SharedSingletonMap.orderedOf(e.getKey(), e.getValue());
         }
 
-        final int size = m.size();
-        if (size == 0) {
-            // Shares a single object
-            return ImmutableMap.of();
+        final ImmutableMap<K, Integer> offsets = OffsetMapCache.orderedOffsets(map.keySet());
+        @SuppressWarnings("unchecked")
+        final V[] array = (V[]) new Object[offsets.size()];
+        for (Entry<K, V> e : map.entrySet()) {
+            array[offsets.get(e.getKey())] = e.getValue();
         }
-        if (size == 1) {
+
+        return new Ordered<>(offsets, array);
+    }
+
+    /**
+     * Create an {@link ImmutableOffsetMap} as a copy of an existing map. This is actually not completely true, as this
+     * method returns an {@link ImmutableMap} for empty and singleton inputs, as those are more memory-efficient. This
+     * method also recognizes {@link ImmutableOffsetMap} and {@link SharedSingletonMap} on input, and returns it back
+     * without doing anything else. It also recognizes {@link MutableOffsetMap} (as returned by
+     * {@link #toModifiableMap()}) and makes an efficient copy of its contents. All other maps are converted to an
+     * {@link ImmutableOffsetMap}. Iterator order is not guaranteed to be retained.
+     *
+     * @param <K> the type of keys maintained by the map
+     * @param <V> the type of mapped values
+     * @param map Input map, may not be null.
+     * @return An isolated, immutable copy of the input map
+     * @throws NullPointerException if {@code map} or any of its elements is null.
+     */
+    public static <K, V> @NonNull Map<K, V> unorderedCopyOf(final @NonNull Map<K, V> map) {
+        final Map<K, V> common = commonCopy(map);
+        if (common != null) {
+            return common;
+        }
+
+        if (map.size() == 1) {
             // Efficient single-entry implementation
-            final Entry<K, V> e = m.entrySet().iterator().next();
-            return SharedSingletonMap.of(e.getKey(), e.getValue());
+            final Entry<K, V> e = map.entrySet().iterator().next();
+            return SharedSingletonMap.unorderedOf(e.getKey(), e.getValue());
         }
 
-        final Map<K, Integer> offsets = OffsetMapCache.offsetsFor(m.keySet());
+        final ImmutableMap<K, Integer> offsets = OffsetMapCache.unorderedOffsets(map.keySet());
         @SuppressWarnings("unchecked")
         final V[] array = (V[]) new Object[offsets.size()];
-        for (Entry<K, V> e : m.entrySet()) {
+        for (Entry<K, V> e : map.entrySet()) {
             array[offsets.get(e.getKey())] = e.getValue();
         }
 
-        return new Ordered<>(offsets, array);
+        return new Unordered<>(offsets, array);
+    }
+
+    private static <K, V> @Nullable Map<K, V> commonCopy(final @NonNull Map<K, V> map) {
+        // Prevent a copy. Note that ImmutableMap is not listed here because of its potentially larger keySet overhead.
+        if (map instanceof ImmutableOffsetMap || map instanceof SharedSingletonMap) {
+            return map;
+        }
+
+        // Familiar and efficient to copy
+        if (map instanceof MutableOffsetMap) {
+            return ((MutableOffsetMap<K, V>) map).toUnmodifiableMap();
+        }
+
+        if (map.isEmpty()) {
+            // Shares a single object
+            return ImmutableMap.of();
+        }
+
+        return null;
     }
 
     @Override
@@ -141,27 +227,27 @@ public abstract class ImmutableOffsetMap<K, V> implements UnmodifiableMapPhase<K
     }
 
     @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 the offset match, the arrays have to match, too
             if (offsets.equals(om.offsets)) {
                 return Arrays.deepEquals(objects, om.objects);
             }
-        } else if (o instanceof MutableOffsetMap) {
+        } else if (obj instanceof MutableOffsetMap) {
             // Let MutableOffsetMap do the actual work.
-            return o.equals(this);
+            return obj.equals(this);
         }
 
-        final Map<?, ?> other = (Map<?, ?>)o;
+        final Map<?, ?> other = (Map<?, ?>)obj;
 
         // Size and key sets have to match
         if (size() != other.size() || !keySet().equals(other.keySet())) {
@@ -200,8 +286,8 @@ public abstract class ImmutableOffsetMap<K, V> implements UnmodifiableMapPhase<K
 
     @Override
     public final V get(final Object key) {
-        final Integer offset = offsets.get(key);
-        return offset == null ? null : objects[offset];
+        Integer offset;
+        return (offset = offsets.get(key)) == null ? null : objects[offset];
     }
 
     @Override
@@ -215,6 +301,7 @@ public abstract class ImmutableOffsetMap<K, V> implements UnmodifiableMapPhase<K
     }
 
     @Override
+    @SuppressWarnings("checkstyle:parameterName")
     public final void putAll(final Map<? extends K, ? extends V> m) {
         throw new UnsupportedOperationException();
     }
@@ -230,12 +317,12 @@ public abstract class ImmutableOffsetMap<K, V> implements UnmodifiableMapPhase<K
     }
 
     @Override
-    public final Collection<V> values() {
+    public final @NonNull Collection<V> values() {
         return new ConstantArrayCollection<>(objects);
     }
 
     @Override
-    public final Set<Entry<K, V>> entrySet() {
+    public final @NonNull Set<Entry<K, V>> entrySet() {
         return new EntrySet();
     }
 
@@ -243,11 +330,9 @@ public abstract class ImmutableOffsetMap<K, V> implements UnmodifiableMapPhase<K
     public final String toString() {
         final StringBuilder sb = new StringBuilder("{");
         final Iterator<K> it = offsets.keySet().iterator();
-        int i = 0;
+        int offset = 0;
         while (it.hasNext()) {
-            sb.append(it.next());
-            sb.append('=');
-            sb.append(objects[i++]);
+            sb.append(it.next()).append('=').append(objects[offset++]);
 
             if (it.hasNext()) {
                 sb.append(", ");
@@ -257,20 +342,19 @@ public abstract class ImmutableOffsetMap<K, V> implements UnmodifiableMapPhase<K
         return sb.append('}').toString();
     }
 
-    final Map<K, Integer> offsets() {
+    final @NonNull ImmutableMap<K, Integer> offsets() {
         return offsets;
     }
 
-    final V[] objects() {
+    final @NonNull V[] objects() {
         return objects;
     }
 
     private final class EntrySet extends AbstractSet<Entry<K, V>> {
         @Override
-        public Iterator<Entry<K, V>> iterator() {
+        public @NonNull Iterator<Entry<K, V>> iterator() {
             final Iterator<Entry<K, Integer>> it = offsets.entrySet().iterator();
-
-            return new UnmodifiableIterator<Entry<K, V>>() {
+            return new UnmodifiableIterator<>() {
                 @Override
                 public boolean hasNext() {
                     return it.hasNext();
@@ -301,7 +385,7 @@ public abstract class ImmutableOffsetMap<K, V> implements UnmodifiableMapPhase<K
     private static final Field OFFSETS_FIELD = fieldFor("offsets");
     private static final Field ARRAY_FIELD = fieldFor("objects");
 
-    private static Field fieldFor(final String name) {
+    private static @NonNull Field fieldFor(final @NonNull String name) {
         final Field f;
         try {
             f = ImmutableOffsetMap.class.getDeclaredField(name);
@@ -313,16 +397,19 @@ public abstract class ImmutableOffsetMap<K, V> implements UnmodifiableMapPhase<K
         return f;
     }
 
-    private void setField(final Field field, final Object value) throws IOException {
+    @SuppressFBWarnings(value = "UPM_UNCALLED_PRIVATE_METHOD",
+            justification = "https://github.com/spotbugs/spotbugs/issues/811")
+    private static void setField(final @NonNull ImmutableOffsetMap<?, ?> map, final @NonNull Field field,
+            final Object value) throws IOException {
         try {
-            field.set(this, value);
+            field.set(map, value);
         } catch (IllegalArgumentException | IllegalAccessException e) {
             throw new IOException("Failed to set field " + field, e);
         }
     }
 
     @SuppressWarnings("unchecked")
-    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
+    private void readObject(final @NonNull ObjectInputStream in) throws IOException, ClassNotFoundException {
         final int s = in.readInt();
 
         final List<K> keys = new ArrayList<>(s);
@@ -333,7 +420,6 @@ public abstract class ImmutableOffsetMap<K, V> implements UnmodifiableMapPhase<K
             values[i] = (V)in.readObject();
         }
 
-        setField(OFFSETS_FIELD, OffsetMapCache.offsetsFor(keys));
-        setField(ARRAY_FIELD, values);
+        setFields(keys, values);
     }
 }