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> offsets = OffsetMapCache.unorderedOffsets(keys);
  74
  75             setField(this, OFFSETS_FIELD, offsets);
  76             setField(this, ARRAY_FIELD, OffsetMapCache.adjustedArray(offsets, keys, values));
  77         }
  78     }
  79
  80     private static final long serialVersionUID = 1L;
  81
  82     private transient final Map<K, Integer> offsets;
  83     private transient final 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      * @deprecated Use {@link #orderedCopyOf(Map)} or {@link #unorderedCopyOf(Map)} instead.
 115      */
 116     @Deprecated
 117     @Nonnull public static <K, V> Map<K, V> copyOf(@Nonnull final Map<K, V> m) {
 118         return orderedCopyOf(m);
 119     }
 120
 121     /**
 122      * Create an {@link ImmutableOffsetMap} as a copy of an existing map. This is actually not completely true,
 123      * as this method returns an {@link ImmutableMap} for empty and singleton inputs, as those are more memory-efficient.
 124      * This method also recognizes {@link ImmutableOffsetMap} on input, and returns it back without doing anything else.
 125      * It also recognizes {@link MutableOffsetMap} (as returned by {@link #toModifiableMap()}) and makes an efficient
 126      * copy of its contents. All other maps are converted to an {@link ImmutableOffsetMap} with the same iteration
 127      * order as input.
 128      *
 129      * @param m Input map, may not be null.
 130      * @return An isolated, immutable copy of the input map
 131      */
 132     @Nonnull public static <K, V> Map<K, V> orderedCopyOf(@Nonnull final Map<K, V> m) {
 133         // Prevent a copy. Note that ImmutableMap is not listed here because of its potentially larger keySet overhead.
 134         if (m instanceof ImmutableOffsetMap || m instanceof SharedSingletonMap) {
 135             return m;
 136         }
 137
 138         // Familiar and efficient to copy
 139         if (m instanceof MutableOffsetMap) {
 140             return ((MutableOffsetMap<K, V>) m).toUnmodifiableMap();
 141         }
 142
 143         final int size = m.size();
 144         if (size == 0) {
 145             // Shares a single object
 146             return ImmutableMap.of();
 147         }
 148         if (size == 1) {
 149             // Efficient single-entry implementation
 150             final Entry<K, V> e = m.entrySet().iterator().next();
 151             return SharedSingletonMap.orderedOf(e.getKey(), e.getValue());
 152         }
 153
 154         final Map<K, Integer> offsets = OffsetMapCache.orderedOffsets(m.keySet());
 155         @SuppressWarnings("unchecked")
 156         final V[] array = (V[]) new Object[offsets.size()];
 157         for (Entry<K, V> e : m.entrySet()) {
 158             array[offsets.get(e.getKey())] = e.getValue();
 159         }
 160
 161         return new Ordered<>(offsets, array);
 162     }
 163
 164     /**
 165      * Create an {@link ImmutableOffsetMap} as a copy of an existing map. This is actually not completely true,
 166      * as this method returns an {@link ImmutableMap} for empty and singleton inputs, as those are more memory-efficient.
 167      * This method also recognizes {@link ImmutableOffsetMap} on input, and returns it back without doing anything else.
 168      * It also recognizes {@link MutableOffsetMap} (as returned by {@link #toModifiableMap()}) and makes an efficient
 169      * copy of its contents. All other maps are converted to an {@link ImmutableOffsetMap}. Iterator order is not
 170      * guaranteed to be retained.
 171      *
 172      * @param m Input map, may not be null.
 173      * @return An isolated, immutable copy of the input map
 174      */
 175     @Nonnull public static <K, V> Map<K, V> unorderedCopyOf(@Nonnull final Map<K, V> m) {
 176         // Prevent a copy. Note that ImmutableMap is not listed here because of its potentially larger keySet overhead.
 177         if (m instanceof ImmutableOffsetMap || m instanceof SharedSingletonMap) {
 178             return m;
 179         }
 180
 181         // Familiar and efficient to copy
 182         if (m instanceof MutableOffsetMap) {
 183             return ((MutableOffsetMap<K, V>) m).toUnmodifiableMap();
 184         }
 185
 186         final int size = m.size();
 187         if (size == 0) {
 188             // Shares a single object
 189             return ImmutableMap.of();
 190         }
 191         if (size == 1) {
 192             // Efficient single-entry implementation
 193             final Entry<K, V> e = m.entrySet().iterator().next();
 194             return SharedSingletonMap.unorderedOf(e.getKey(), e.getValue());
 195         }
 196
 197         final Map<K, Integer> offsets = OffsetMapCache.unorderedOffsets(m.keySet());
 198         @SuppressWarnings("unchecked")
 199         final V[] array = (V[]) new Object[offsets.size()];
 200         for (Entry<K, V> e : m.entrySet()) {
 201             array[offsets.get(e.getKey())] = e.getValue();
 202         }
 203
 204         return new Unordered<>(offsets, array);
 205     }
 206
 207     @Override
 208     public final int size() {
 209         return offsets.size();
 210     }
 211
 212     @Override
 213     public final boolean isEmpty() {
 214         return offsets.isEmpty();
 215     }
 216
 217     @Override
 218     public final int hashCode() {
 219         if (hashCode != 0) {
 220             return hashCode;
 221         }
 222
 223         int result = 0;
 224         for (Entry<K, Integer> e : offsets.entrySet()) {
 225             result += e.getKey().hashCode() ^ objects[e.getValue()].hashCode();
 226         }
 227
 228         hashCode = result;
 229         return result;
 230     }
 231
 232     @Override
 233     public final boolean equals(final Object o) {
 234         if (o == this) {
 235             return true;
 236         }
 237         if (!(o instanceof Map)) {
 238             return false;
 239         }
 240
 241         if (o instanceof ImmutableOffsetMap) {
 242             final ImmutableOffsetMap<?, ?> om = (ImmutableOffsetMap<?, ?>) o;
 243
 244             // If the offset match, the arrays have to match, too
 245             if (offsets.equals(om.offsets)) {
 246                 return Arrays.deepEquals(objects, om.objects);
 247             }
 248         } else if (o instanceof MutableOffsetMap) {
 249             // Let MutableOffsetMap do the actual work.
 250             return o.equals(this);
 251         }
 252
 253         final Map<?, ?> other = (Map<?, ?>)o;
 254
 255         // Size and key sets have to match
 256         if (size() != other.size() || !keySet().equals(other.keySet())) {
 257             return false;
 258         }
 259
 260         try {
 261             // Ensure all objects are present
 262             for (Entry<K, Integer> e : offsets.entrySet()) {
 263                 if (!objects[e.getValue()].equals(other.get(e.getKey()))) {
 264                     return false;
 265                 }
 266             }
 267         } catch (ClassCastException e) {
 268             // Can be thrown by other.get() indicating we have incompatible key types
 269             return false;
 270         }
 271
 272         return true;
 273     }
 274
 275     @Override
 276     public final boolean containsKey(final Object key) {
 277         return offsets.containsKey(key);
 278     }
 279
 280     @Override
 281     public final boolean containsValue(final Object value) {
 282         for (Object o : objects) {
 283             if (value.equals(o)) {
 284                 return true;
 285             }
 286         }
 287         return false;
 288     }
 289
 290     @Override
 291     public final V get(final Object key) {
 292         final Integer offset = offsets.get(key);
 293         return offset == null ? null : objects[offset];
 294     }
 295
 296     @Override
 297     public final V remove(final Object key) {
 298         throw new UnsupportedOperationException();
 299     }
 300
 301     @Override
 302     public final V put(final K key, final V value) {
 303         throw new UnsupportedOperationException();
 304     }
 305
 306     @Override
 307     public final void putAll(final Map<? extends K, ? extends V> m) {
 308         throw new UnsupportedOperationException();
 309     }
 310
 311     @Override
 312     public final void clear() {
 313         throw new UnsupportedOperationException();
 314     }
 315
 316     @Override
 317     public final Set<K> keySet() {
 318         return offsets.keySet();
 319     }
 320
 321     @Override
 322     public final Collection<V> values() {
 323         return new ConstantArrayCollection<>(objects);
 324     }
 325
 326     @Override
 327     public final Set<Entry<K, V>> entrySet() {
 328         return new EntrySet();
 329     }
 330
 331     @Override
 332     public final String toString() {
 333         final StringBuilder sb = new StringBuilder("{");
 334         final Iterator<K> it = offsets.keySet().iterator();
 335         int i = 0;
 336         while (it.hasNext()) {
 337             sb.append(it.next());
 338             sb.append('=');
 339             sb.append(objects[i++]);
 340
 341             if (it.hasNext()) {
 342                 sb.append(", ");
 343             }
 344         }
 345
 346         return sb.append('}').toString();
 347     }
 348
 349     final Map<K, Integer> offsets() {
 350         return offsets;
 351     }
 352
 353     final V[] objects() {
 354         return objects;
 355     }
 356
 357     private final class EntrySet extends AbstractSet<Entry<K, V>> {
 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) throws IOException {
 406         try {
 407             field.set(map, value);
 408         } catch (IllegalArgumentException | IllegalAccessException e) {
 409             throw new IOException("Failed to set field " + field, e);
 410         }
 411     }
 412
 413     @SuppressWarnings("unchecked")
 414     private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
 415         final int s = in.readInt();
 416
 417         final List<K> keys = new ArrayList<>(s);
 418         final V[] values = (V[]) new Object[s];
 419
 420         for (int i = 0; i < s; ++i) {
 421             keys.add((K)in.readObject());
 422             values[i] = (V)in.readObject();
 423         }
 424
 425         setFields(keys, values);
 426     }
 427 }