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