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