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