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=ccbc58aa197a18930106c17256b9308732469d8f;hp=bbab15649c0a45b21ef3073dd3b1c874551ec2de;hpb=94ce73de754dde1d931d7d19e6eeb79de997bdef;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 bbab15649c..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,43 +7,89 @@ */ 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; import java.io.Serializable; import java.lang.reflect.Field; +import java.util.AbstractMap.SimpleImmutableEntry; import java.util.AbstractSet; import java.util.ArrayList; import java.util.Arrays; +import java.util.Collection; import java.util.Iterator; import java.util.List; import java.util.Map; -import java.util.Objects; 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. * - * This map supports creation of value objects on the fly. To achieve that, subclasses should override {@link #valueToObject(Object)}, - * {@link #objectToValue(Object, Object)}, {@link #clone()} and {@link #toModifiableMap()} methods. + *

+ * In case the set of keys is statically known, you can use {@link ImmutableOffsetMapTemplate} to efficiently create + * {@link ImmutableOffsetMap} instances. * * @param the type of keys maintained by this map * @param the type of mapped values */ @Beta -public class ImmutableOffsetMap extends AbstractLazyValueMap implements UnmodifiableMapPhase, Serializable { +public abstract class ImmutableOffsetMap implements UnmodifiableMapPhase, Serializable { + static final class Ordered extends ImmutableOffsetMap { + private static final long serialVersionUID = 1L; + + Ordered(final ImmutableMap offsets, final V[] objects) { + super(offsets, objects); + } + + @Override + public @NonNull MutableOffsetMap toModifiableMap() { + return MutableOffsetMap.orderedCopyOf(this); + } + + @Override + void setFields(final List keys, final V[] values) throws IOException { + setField(this, OFFSETS_FIELD, OffsetMapCache.orderedOffsets(keys)); + setField(this, ARRAY_FIELD, values); + } + } + + static final class Unordered extends ImmutableOffsetMap { + private static final long serialVersionUID = 1L; + + Unordered(final ImmutableMap offsets, final V[] objects) { + super(offsets, objects); + } + + @Override + public @NonNull MutableOffsetMap toModifiableMap() { + return MutableOffsetMap.unorderedCopyOf(this); + } + + @Override + void setFields(final List keys, final V[] values) throws IOException { + final Map 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 offsets; - private final Object[] objects; - private int hashCode; + private final transient @NonNull ImmutableMap 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. @@ -52,63 +98,107 @@ public class ImmutableOffsetMap extends AbstractLazyValueMap impleme * @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 offsets, @Nonnull final Object[] objects) { - this.offsets = Preconditions.checkNotNull(offsets); - this.objects = Preconditions.checkNotNull(objects); - Preconditions.checkArgument(offsets.size() == objects.length); + ImmutableOffsetMap(final ImmutableMap offsets, final V[] objects) { + this.offsets = requireNonNull(offsets); + this.objects = requireNonNull(objects); + checkArgument(offsets.size() == objects.length); } + @Override + public abstract @NonNull MutableOffsetMap toModifiableMap(); + + abstract void setFields(List keys, V[] values) throws IOException; + /** - * Construct a new instance based on some other instance. + * 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 Instance to share data with, may not be null. + * @param the type of keys maintained by the map + * @param 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. */ - protected ImmutableOffsetMap(@Nonnull final ImmutableOffsetMap m) { - this.offsets = m.offsets; - this.objects = m.objects; + public static @NonNull Map orderedCopyOf(final @NonNull Map map) { + final Map common = commonCopy(map); + if (common != null) { + return common; + } + + final int size = map.size(); + if (size == 1) { + // Efficient single-entry implementation + final Entry e = map.entrySet().iterator().next(); + return SharedSingletonMap.orderedOf(e.getKey(), e.getValue()); + } + + final ImmutableMap offsets = OffsetMapCache.orderedOffsets(map.keySet()); + @SuppressWarnings("unchecked") + final V[] array = (V[]) new Object[offsets.size()]; + for (Entry e : map.entrySet()) { + array[offsets.get(e.getKey())] = e.getValue(); + } + + 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} 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}. Iterator order is not guaranteed to be retained. * - * @param m Input map, may not be null. + * @param the type of keys maintained by the map + * @param 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 Map copyOf(@Nonnull final Map 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 @NonNull Map unorderedCopyOf(final @NonNull Map map) { + final Map common = commonCopy(map); + if (common != null) { + return common; } - // Familiar and efficient to copy - if (m instanceof MutableOffsetMap) { - return ((MutableOffsetMap) m).toUnmodifiableMap(); - } - - final int size = m.size(); - if (size == 0) { - // Shares a single object - return ImmutableMap.of(); - } - if (size == 1) { + if (map.size() == 1) { // Efficient single-entry implementation - final Entry e = m.entrySet().iterator().next(); - return SharedSingletonMap.of(e.getKey(), e.getValue()); + final Entry e = map.entrySet().iterator().next(); + return SharedSingletonMap.unorderedOf(e.getKey(), e.getValue()); } - final Map offsets = OffsetMapCache.offsetsFor(m.keySet()); + final ImmutableMap offsets = OffsetMapCache.unorderedOffsets(map.keySet()); @SuppressWarnings("unchecked") final V[] array = (V[]) new Object[offsets.size()]; - for (Entry e : m.entrySet()) { + for (Entry e : map.entrySet()) { array[offsets.get(e.getKey())] = e.getValue(); } - return new ImmutableOffsetMap<>(offsets, array); + return new Unordered<>(offsets, array); + } + + private static @Nullable Map commonCopy(final @NonNull Map 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) map).toUnmodifiableMap(); + } + + if (map.isEmpty()) { + // Shares a single object + return ImmutableMap.of(); + } + + return null; } @Override @@ -122,15 +212,14 @@ public class ImmutableOffsetMap extends AbstractLazyValueMap impleme } @Override - public int hashCode() { + public final int hashCode() { if (hashCode != 0) { return hashCode; } int result = 0; for (Entry e : offsets.entrySet()) { - final Object v = objects[e.getValue()]; - result += e.getKey().hashCode() ^ objectToValue(e.getKey(), v).hashCode(); + result += e.getKey().hashCode() ^ objects[e.getValue()].hashCode(); } hashCode = result; @@ -138,47 +227,46 @@ public class ImmutableOffsetMap extends AbstractLazyValueMap impleme } @Override - public boolean equals(final Object o) { - if (o == this) { + public final boolean equals(final Object obj) { + if (obj == this) { return true; } - if (o == null) { + if (!(obj instanceof Map)) { return false; } - if (o instanceof ImmutableOffsetMap) { - final ImmutableOffsetMap om = (ImmutableOffsetMap) o; - if (offsets.equals(om.offsets) && Arrays.deepEquals(objects, om.objects)) { - return true; + 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); - } else if (o instanceof Map) { - final Map om = (Map)o; + return obj.equals(this); + } - // Size and key sets have to match - if (size() != om.size() || !keySet().equals(om.keySet())) { - return false; - } + final Map other = (Map)obj; + + // Size and key sets have to match + if (size() != other.size() || !keySet().equals(other.keySet())) { + return false; + } - try { - // Ensure all objects are present - for (Entry e : offsets.entrySet()) { - final V v = objectToValue(e.getKey(), objects[e.getValue()]); - if (!v.equals(om.get(e.getKey()))) { - return false; - } + try { + // Ensure all objects are present + for (Entry e : offsets.entrySet()) { + if (!objects[e.getValue()].equals(other.get(e.getKey()))) { + return false; } - } catch (ClassCastException e) { - // Can be thrown by om.get() and indicate we have incompatible key types - return false; } - - return true; + } catch (ClassCastException e) { + // Can be thrown by other.get() indicating we have incompatible key types + return false; } - return false; + return true; } @Override @@ -188,25 +276,18 @@ public class ImmutableOffsetMap extends AbstractLazyValueMap impleme @Override public final boolean containsValue(final Object value) { - @SuppressWarnings("unchecked") - final Object obj = valueToObject((V)value); for (Object o : objects) { - if (Objects.equals(obj, o)) { + if (value.equals(o)) { return true; } } return false; } - @SuppressWarnings("unchecked") @Override public final V get(final Object key) { - final Integer offset = offsets.get(key); - if (offset == null) { - return null; - } - - return objectToValue((K) key, objects[offset]); + Integer offset; + return (offset = offsets.get(key)) == null ? null : objects[offset]; } @Override @@ -215,6 +296,12 @@ public class ImmutableOffsetMap extends AbstractLazyValueMap impleme } @Override + public final V put(final K key, final V value) { + throw new UnsupportedOperationException(); + } + + @Override + @SuppressWarnings("checkstyle:parameterName") public final void putAll(final Map m) { throw new UnsupportedOperationException(); } @@ -230,29 +317,44 @@ public class ImmutableOffsetMap extends AbstractLazyValueMap impleme } @Override - public final Set> entrySet() { + public final @NonNull Collection values() { + return new ConstantArrayCollection<>(objects); + } + + @Override + public final @NonNull Set> entrySet() { return new EntrySet(); } @Override - public MutableOffsetMap toModifiableMap() { - return new MutableOffsetMap<>(this); + public final String toString() { + final StringBuilder sb = new StringBuilder("{"); + final Iterator it = offsets.keySet().iterator(); + int offset = 0; + while (it.hasNext()) { + sb.append(it.next()).append('=').append(objects[offset++]); + + if (it.hasNext()) { + sb.append(", "); + } + } + + return sb.append('}').toString(); } - Map offsets() { + final @NonNull ImmutableMap offsets() { return offsets; } - Object[] objects() { + final @NonNull V[] objects() { return objects; } private final class EntrySet extends AbstractSet> { @Override - public Iterator> iterator() { + public @NonNull Iterator> iterator() { final Iterator> it = offsets.entrySet().iterator(); - - return new UnmodifiableIterator>() { + return new UnmodifiableIterator<>() { @Override public boolean hasNext() { return it.hasNext(); @@ -261,7 +363,7 @@ public class ImmutableOffsetMap extends AbstractLazyValueMap impleme @Override public Entry next() { final Entry e = it.next(); - return new SimpleImmutableEntry<>(e.getKey(), objectToValue(e.getKey(), objects[e.getValue()])); + return new SimpleImmutableEntry<>(e.getKey(), objects[e.getValue()]); } }; } @@ -283,7 +385,7 @@ public class ImmutableOffsetMap extends AbstractLazyValueMap impleme 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); @@ -295,16 +397,19 @@ public class ImmutableOffsetMap extends AbstractLazyValueMap impleme 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 keys = new ArrayList<>(s); @@ -315,7 +420,6 @@ public class ImmutableOffsetMap extends AbstractLazyValueMap impleme values[i] = (V)in.readObject(); } - setField(OFFSETS_FIELD, OffsetMapCache.offsetsFor(keys)); - setField(ARRAY_FIELD, values); + setFields(keys, values); } }