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