common/util/src/main/java/org/opendaylight/yangtools/util/ImmutableOffsetMap.java

   1 /*
   2  * Copyright (c) 2015 Cisco Systems, Inc. and others.  All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8 package org.opendaylight.yangtools.util;
   9
  10 import static com.google.common.base.Preconditions.checkArgument;
  11 import static java.util.Objects.requireNonNull;
  12
  13 import com.google.common.annotations.Beta;
  14 import com.google.common.collect.ImmutableMap;
  15 import com.google.common.collect.UnmodifiableIterator;
  16 import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
  17 import java.io.IOException;
  18 import java.io.ObjectInputStream;
  19 import java.io.ObjectOutputStream;
  20 import java.io.Serializable;
  21 import java.lang.reflect.Field;
  22 import java.util.AbstractMap.SimpleImmutableEntry;
  23 import java.util.AbstractSet;
  24 import java.util.ArrayList;
  25 import java.util.Arrays;
  26 import java.util.Collection;
  27 import java.util.Iterator;
  28 import java.util.List;
  29 import java.util.Map;
  30 import java.util.Set;
  31 import org.eclipse.jdt.annotation.NonNull;
  32 import org.eclipse.jdt.annotation.Nullable;
  33
  34 /**
  35  * Implementation of the {@link Map} interface which stores a set of immutable mappings using a key-to-offset map and
  36  * a backing array. This is useful for situations where the same key set is shared across a multitude of maps, as this
  37  * class uses a global cache to share the key-to-offset mapping.
  38  *
  39  * <p>
  40  * In case the set of keys is statically known, you can use {@link ImmutableOffsetMapTemplate} to efficiently create
  41  * {@link ImmutableOffsetMap} instances.
  42  *
  43  * @param <K> the type of keys maintained by this map
  44  * @param <V> the type of mapped values
  45  */
  46 @Beta
  47 public abstract class ImmutableOffsetMap<K, V> implements UnmodifiableMapPhase<K, V>, Serializable {
  48     static final class Ordered<K, V> extends ImmutableOffsetMap<K, V> {
  49         private static final long serialVersionUID = 1L;
  50
  51         Ordered(final ImmutableMap<K, Integer> offsets, final V[] objects) {
  52             super(offsets, objects);
  53         }
  54
  55         @Override
  56         public @NonNull MutableOffsetMap<K, V> toModifiableMap() {
  57             return MutableOffsetMap.orderedCopyOf(this);
  58         }
  59
  60         @Override
  61         void setFields(final List<K> keys, final V[] values) throws IOException {
  62             setField(this, OFFSETS_FIELD, OffsetMapCache.orderedOffsets(keys));
  63             setField(this, ARRAY_FIELD, values);
  64         }
  65     }
  66
  67     static final class Unordered<K, V> extends ImmutableOffsetMap<K, V> {
  68         private static final long serialVersionUID = 1L;
  69
  70         Unordered(final ImmutableMap<K, Integer> offsets, final V[] objects) {
  71             super(offsets, objects);
  72         }
  73
  74         @Override
  75         public @NonNull MutableOffsetMap<K, V> toModifiableMap() {
  76             return MutableOffsetMap.unorderedCopyOf(this);
  77         }
  78
  79         @Override
  80         void setFields(final List<K> keys, final V[] values) throws IOException {
  81             final Map<K, Integer> newOffsets = OffsetMapCache.unorderedOffsets(keys);
  82
  83             setField(this, OFFSETS_FIELD, newOffsets);
  84             setField(this, ARRAY_FIELD, OffsetMapCache.adjustedArray(newOffsets, keys, values));
  85         }
  86     }
  87
  88     private static final long serialVersionUID = 1L;
  89
  90     private final transient @NonNull ImmutableMap<K, Integer> offsets;
  91     private final transient @NonNull V[] objects;
  92     private transient int hashCode;
  93
  94     /**
  95      * Construct a new instance backed by specified key-to-offset map and array of objects.
  96      *
  97      * @param offsets Key-to-offset map, may not be null
  98      * @param objects Array of value object, may not be null. The array is stored as is, the caller
  99      *              is responsible for ensuring its contents remain unmodified.
 100      */
 101     ImmutableOffsetMap(final ImmutableMap<K, Integer> offsets, final V[] objects) {
 102         this.offsets = requireNonNull(offsets);
 103         this.objects = requireNonNull(objects);
 104         checkArgument(offsets.size() == objects.length);
 105     }
 106
 107     @Override
 108     public abstract @NonNull MutableOffsetMap<K, V> toModifiableMap();
 109
 110     abstract void setFields(List<K> keys, V[] values) throws IOException;
 111
 112     /**
 113      * Create an {@link ImmutableOffsetMap} as a copy of an existing map. This is actually not completely true, as this
 114      * method returns an {@link ImmutableMap} for empty and singleton inputs, as those are more memory-efficient. This
 115      * method also recognizes {@link ImmutableOffsetMap} and {@link SharedSingletonMap} on input, and returns it back
 116      * without doing anything else. It also recognizes {@link MutableOffsetMap} (as returned by
 117      * {@link #toModifiableMap()}) and makes an efficient copy of its contents. All other maps are converted to an
 118      * {@link ImmutableOffsetMap} with the same iteration order as input.
 119      *
 120      * @param <K> the type of keys maintained by the map
 121      * @param <V> the type of mapped values
 122      * @param map Input map, may not be null.
 123      * @return An isolated, immutable copy of the input map
 124      * @throws NullPointerException if {@code map} or any of its elements is null.
 125      */
 126     public static <K, V> @NonNull Map<K, V> orderedCopyOf(final @NonNull Map<K, V> map) {
 127         final Map<K, V> common = commonCopy(map);
 128         if (common != null) {
 129             return common;
 130         }
 131
 132         final int size = map.size();
 133         if (size == 1) {
 134             // Efficient single-entry implementation
 135             final Entry<K, V> e = map.entrySet().iterator().next();
 136             return SharedSingletonMap.orderedOf(e.getKey(), e.getValue());
 137         }
 138
 139         final ImmutableMap<K, Integer> offsets = OffsetMapCache.orderedOffsets(map.keySet());
 140         @SuppressWarnings("unchecked")
 141         final V[] array = (V[]) new Object[offsets.size()];
 142         for (Entry<K, V> e : map.entrySet()) {
 143             array[offsets.get(e.getKey())] = e.getValue();
 144         }
 145
 146         return new Ordered<>(offsets, array);
 147     }
 148
 149     /**
 150      * Create an {@link ImmutableOffsetMap} as a copy of an existing map. This is actually not completely true, as this
 151      * method returns an {@link ImmutableMap} for empty and singleton inputs, as those are more memory-efficient. This
 152      * method also recognizes {@link ImmutableOffsetMap} and {@link SharedSingletonMap} on input, and returns it back
 153      * without doing anything else. It also recognizes {@link MutableOffsetMap} (as returned by
 154      * {@link #toModifiableMap()}) and makes an efficient copy of its contents. All other maps are converted to an
 155      * {@link ImmutableOffsetMap}. Iterator order is not guaranteed to be retained.
 156      *
 157      * @param <K> the type of keys maintained by the map
 158      * @param <V> the type of mapped values
 159      * @param map Input map, may not be null.
 160      * @return An isolated, immutable copy of the input map
 161      * @throws NullPointerException if {@code map} or any of its elements is null.
 162      */
 163     public static <K, V> @NonNull Map<K, V> unorderedCopyOf(final @NonNull Map<K, V> map) {
 164         final Map<K, V> common = commonCopy(map);
 165         if (common != null) {
 166             return common;
 167         }
 168
 169         if (map.size() == 1) {
 170             // Efficient single-entry implementation
 171             final Entry<K, V> e = map.entrySet().iterator().next();
 172             return SharedSingletonMap.unorderedOf(e.getKey(), e.getValue());
 173         }
 174
 175         final ImmutableMap<K, Integer> offsets = OffsetMapCache.unorderedOffsets(map.keySet());
 176         @SuppressWarnings("unchecked")
 177         final V[] array = (V[]) new Object[offsets.size()];
 178         for (Entry<K, V> e : map.entrySet()) {
 179             array[offsets.get(e.getKey())] = e.getValue();
 180         }
 181
 182         return new Unordered<>(offsets, array);
 183     }
 184
 185     private static <K, V> @Nullable Map<K, V> commonCopy(final @NonNull Map<K, V> map) {
 186         // Prevent a copy. Note that ImmutableMap is not listed here because of its potentially larger keySet overhead.
 187         if (map instanceof ImmutableOffsetMap || map instanceof SharedSingletonMap) {
 188             return map;
 189         }
 190
 191         // Familiar and efficient to copy
 192         if (map instanceof MutableOffsetMap) {
 193             return ((MutableOffsetMap<K, V>) map).toUnmodifiableMap();
 194         }
 195
 196         if (map.isEmpty()) {
 197             // Shares a single object
 198             return ImmutableMap.of();
 199         }
 200
 201         return null;
 202     }
 203
 204     @Override
 205     public final int size() {
 206         return offsets.size();
 207     }
 208
 209     @Override
 210     public final boolean isEmpty() {
 211         return offsets.isEmpty();
 212     }
 213
 214     @Override
 215     public final int hashCode() {
 216         if (hashCode != 0) {
 217             return hashCode;
 218         }
 219
 220         int result = 0;
 221         for (Entry<K, Integer> e : offsets.entrySet()) {
 222             result += e.getKey().hashCode() ^ objects[e.getValue()].hashCode();
 223         }
 224
 225         hashCode = result;
 226         return result;
 227     }
 228
 229     @Override
 230     public final boolean equals(final Object obj) {
 231         if (obj == this) {
 232             return true;
 233         }
 234         if (!(obj instanceof Map)) {
 235             return false;
 236         }
 237
 238         if (obj instanceof ImmutableOffsetMap) {
 239             final ImmutableOffsetMap<?, ?> om = (ImmutableOffsetMap<?, ?>) obj;
 240
 241             // If the offset match, the arrays have to match, too
 242             if (offsets.equals(om.offsets)) {
 243                 return Arrays.deepEquals(objects, om.objects);
 244             }
 245         } else if (obj instanceof MutableOffsetMap) {
 246             // Let MutableOffsetMap do the actual work.
 247             return obj.equals(this);
 248         }
 249
 250         final Map<?, ?> other = (Map<?, ?>)obj;
 251
 252         // Size and key sets have to match
 253         if (size() != other.size() || !keySet().equals(other.keySet())) {
 254             return false;
 255         }
 256
 257         try {
 258             // Ensure all objects are present
 259             for (Entry<K, Integer> e : offsets.entrySet()) {
 260                 if (!objects[e.getValue()].equals(other.get(e.getKey()))) {
 261                     return false;
 262                 }
 263             }
 264         } catch (ClassCastException e) {
 265             // Can be thrown by other.get() indicating we have incompatible key types
 266             return false;
 267         }
 268
 269         return true;
 270     }
 271
 272     @Override
 273     public final boolean containsKey(final Object key) {
 274         return offsets.containsKey(key);
 275     }
 276
 277     @Override
 278     public final boolean containsValue(final Object value) {
 279         for (Object o : objects) {
 280             if (value.equals(o)) {
 281                 return true;
 282             }
 283         }
 284         return false;
 285     }
 286
 287     @Override
 288     public final V get(final Object key) {
 289         Integer offset;
 290         return (offset = offsets.get(key)) == null ? null : objects[offset];
 291     }
 292
 293     @Override
 294     public final V remove(final Object key) {
 295         throw new UnsupportedOperationException();
 296     }
 297
 298     @Override
 299     public final V put(final K key, final V value) {
 300         throw new UnsupportedOperationException();
 301     }
 302
 303     @Override
 304     @SuppressWarnings("checkstyle:parameterName")
 305     public final void putAll(final Map<? extends K, ? extends V> m) {
 306         throw new UnsupportedOperationException();
 307     }
 308
 309     @Override
 310     public final void clear() {
 311         throw new UnsupportedOperationException();
 312     }
 313
 314     @Override
 315     public final Set<K> keySet() {
 316         return offsets.keySet();
 317     }
 318
 319     @Override
 320     public final @NonNull Collection<V> values() {
 321         return new ConstantArrayCollection<>(objects);
 322     }
 323
 324     @Override
 325     public final @NonNull Set<Entry<K, V>> entrySet() {
 326         return new EntrySet();
 327     }
 328
 329     @Override
 330     public final String toString() {
 331         final StringBuilder sb = new StringBuilder("{");
 332         final Iterator<K> it = offsets.keySet().iterator();
 333         int offset = 0;
 334         while (it.hasNext()) {
 335             sb.append(it.next()).append('=').append(objects[offset++]);
 336
 337             if (it.hasNext()) {
 338                 sb.append(", ");
 339             }
 340         }
 341
 342         return sb.append('}').toString();
 343     }
 344
 345     final @NonNull ImmutableMap<K, Integer> offsets() {
 346         return offsets;
 347     }
 348
 349     final @NonNull V[] objects() {
 350         return objects;
 351     }
 352
 353     private final class EntrySet extends AbstractSet<Entry<K, V>> {
 354         @Override
 355         public @NonNull Iterator<Entry<K, V>> iterator() {
 356             final Iterator<Entry<K, Integer>> it = offsets.entrySet().iterator();
 357             return new UnmodifiableIterator<>() {
 358                 @Override
 359                 public boolean hasNext() {
 360                     return it.hasNext();
 361                 }
 362
 363                 @Override
 364                 public Entry<K, V> next() {
 365                     final Entry<K, Integer> e = it.next();
 366                     return new SimpleImmutableEntry<>(e.getKey(), objects[e.getValue()]);
 367                 }
 368             };
 369         }
 370
 371         @Override
 372         public int size() {
 373             return offsets.size();
 374         }
 375     }
 376
 377     private void writeObject(final ObjectOutputStream out) throws IOException {
 378         out.writeInt(offsets.size());
 379         for (Entry<K, V> e : entrySet()) {
 380             out.writeObject(e.getKey());
 381             out.writeObject(e.getValue());
 382         }
 383     }
 384
 385     private static final Field OFFSETS_FIELD = fieldFor("offsets");
 386     private static final Field ARRAY_FIELD = fieldFor("objects");
 387
 388     private static @NonNull Field fieldFor(final @NonNull String name) {
 389         final Field f;
 390         try {
 391             f = ImmutableOffsetMap.class.getDeclaredField(name);
 392         } catch (NoSuchFieldException | SecurityException e) {
 393             throw new IllegalStateException("Failed to lookup field " + name, e);
 394         }
 395
 396         f.setAccessible(true);
 397         return f;
 398     }
 399
 400     @SuppressFBWarnings(value = "UPM_UNCALLED_PRIVATE_METHOD",
 401             justification = "https://github.com/spotbugs/spotbugs/issues/811")
 402     private static void setField(final @NonNull ImmutableOffsetMap<?, ?> map, final @NonNull Field field,
 403             final Object value) throws IOException {
 404         try {
 405             field.set(map, value);
 406         } catch (IllegalArgumentException | IllegalAccessException e) {
 407             throw new IOException("Failed to set field " + field, e);
 408         }
 409     }
 410
 411     @SuppressWarnings("unchecked")
 412     private void readObject(final @NonNull ObjectInputStream in) throws IOException, ClassNotFoundException {
 413         final int s = in.readInt();
 414
 415         final List<K> keys = new ArrayList<>(s);
 416         final V[] values = (V[]) new Object[s];
 417
 418         for (int i = 0; i < s; ++i) {
 419             keys.add((K)in.readObject());
 420             values[i] = (V)in.readObject();
 421         }
 422
 423         setFields(keys, values);
 424     }
 425 }