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