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