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 com.google.common.base.Verify.verifyNotNull;
  12 import static java.util.Objects.requireNonNull;
  13
  14 import com.google.common.annotations.Beta;
  15 import com.google.common.collect.ImmutableMap;
  16 import com.google.common.collect.UnmodifiableIterator;
  17 import java.io.IOException;
  18 import java.io.ObjectInputStream;
  19 import java.io.ObjectOutputStream;
  20 import java.io.Serial;
  21 import java.io.Serializable;
  22 import java.lang.reflect.Field;
  23 import java.util.AbstractMap.SimpleImmutableEntry;
  24 import java.util.AbstractSet;
  25 import java.util.ArrayList;
  26 import java.util.Arrays;
  27 import java.util.Collection;
  28 import java.util.Iterator;
  29 import java.util.List;
  30 import java.util.Map;
  31 import java.util.Set;
  32 import org.eclipse.jdt.annotation.NonNull;
  33 import org.eclipse.jdt.annotation.Nullable;
  34
  35 /**
  36  * Implementation of the {@link Map} interface which stores a set of immutable mappings using a key-to-offset map and
  37  * a backing array. This is useful for situations where the same key set is shared across a multitude of maps, as this
  38  * class uses a global cache to share the key-to-offset mapping.
  39  *
  40  * <p>
  41  * In case the set of keys is statically known, you can use {@link ImmutableOffsetMapTemplate} to efficiently create
  42  * {@link ImmutableOffsetMap} instances.
  43  *
  44  * @param <K> the type of keys maintained by this map
  45  * @param <V> the type of mapped values
  46  */
  47 @Beta
  48 public abstract sealed class ImmutableOffsetMap<K, V> implements UnmodifiableMapPhase<K, V>, Serializable {
  49     static final class Ordered<K, V> extends ImmutableOffsetMap<K, V> {
  50         @Serial
  51         private static final long serialVersionUID = 1L;
  52
  53         Ordered(final ImmutableMap<K, Integer> offsets, final V[] objects) {
  54             super(offsets, objects);
  55         }
  56
  57         @Override
  58         public MutableOffsetMap<K, V> toModifiableMap() {
  59             return MutableOffsetMap.orderedCopyOf(this);
  60         }
  61
  62         @Override
  63         void setFields(final List<K> keys, final V[] values) throws IOException {
  64             setField(this, OFFSETS_FIELD, OffsetMapCache.orderedOffsets(keys));
  65             setField(this, ARRAY_FIELD, values);
  66         }
  67     }
  68
  69     static final class Unordered<K, V> extends ImmutableOffsetMap<K, V> {
  70         @Serial
  71         private static final long serialVersionUID = 1L;
  72
  73         Unordered(final ImmutableMap<K, Integer> offsets, final V[] objects) {
  74             super(offsets, objects);
  75         }
  76
  77         @Override
  78         public MutableOffsetMap<K, V> toModifiableMap() {
  79             return MutableOffsetMap.unorderedCopyOf(this);
  80         }
  81
  82         @Override
  83         void setFields(final List<K> keys, final V[] values) throws IOException {
  84             final Map<K, Integer> newOffsets = OffsetMapCache.unorderedOffsets(keys);
  85
  86             setField(this, OFFSETS_FIELD, newOffsets);
  87             setField(this, ARRAY_FIELD, OffsetMapCache.adjustedArray(newOffsets, keys, values));
  88         }
  89     }
  90
  91     @Serial
  92     private static final long serialVersionUID = 1L;
  93
  94     private final transient @NonNull ImmutableMap<K, Integer> offsets;
  95     private final transient @NonNull V[] objects;
  96     private transient int hashCode;
  97
  98     /**
  99      * Construct a new instance backed by specified key-to-offset map and array of objects.
 100      *
 101      * @param offsets Key-to-offset map, may not be null
 102      * @param objects Array of value object, may not be null. The array is stored as is, the caller
 103      *              is responsible for ensuring its contents remain unmodified.
 104      */
 105     private ImmutableOffsetMap(final ImmutableMap<K, Integer> offsets, final V[] objects) {
 106         this.offsets = requireNonNull(offsets);
 107         this.objects = requireNonNull(objects);
 108         checkArgument(offsets.size() == objects.length);
 109     }
 110
 111     @Override
 112     public abstract @NonNull MutableOffsetMap<K, V> toModifiableMap();
 113
 114     abstract void setFields(List<K> keys, V[] values) throws IOException;
 115
 116     /**
 117      * Create an {@link ImmutableOffsetMap} as a copy of an existing map. This is actually not completely true, as this
 118      * method returns an {@link ImmutableMap} for empty and singleton inputs, as those are more memory-efficient. This
 119      * method also recognizes {@link ImmutableOffsetMap} and {@link SharedSingletonMap} on input, and returns it back
 120      * without doing anything else. It also recognizes {@link MutableOffsetMap} (as returned by
 121      * {@link #toModifiableMap()}) and makes an efficient copy of its contents. All other maps are converted to an
 122      * {@link ImmutableOffsetMap} with the same iteration order as input.
 123      *
 124      * @param <K> the type of keys maintained by the map
 125      * @param <V> the type of mapped values
 126      * @param map Input map, may not be null.
 127      * @return An isolated, immutable copy of the input map
 128      * @throws NullPointerException if {@code map} or any of its elements is null.
 129      */
 130     public static <K, V> @NonNull Map<K, V> orderedCopyOf(final @NonNull Map<K, V> map) {
 131         final Map<K, V> common = commonCopy(map);
 132         if (common != null) {
 133             return common;
 134         }
 135
 136         final int size = map.size();
 137         if (size == 1) {
 138             // Efficient single-entry implementation
 139             final Entry<K, V> e = map.entrySet().iterator().next();
 140             return SharedSingletonMap.orderedOf(e.getKey(), e.getValue());
 141         }
 142
 143         final ImmutableMap<K, Integer> offsets = OffsetMapCache.orderedOffsets(map.keySet());
 144         return new Ordered<>(offsets, createArray(offsets, map));
 145     }
 146
 147     /**
 148      * Create an {@link ImmutableOffsetMap} as a copy of an existing map. This is actually not completely true, as this
 149      * method returns an {@link ImmutableMap} for empty and singleton inputs, as those are more memory-efficient. This
 150      * method also recognizes {@link ImmutableOffsetMap} and {@link SharedSingletonMap} on input, and returns it back
 151      * without doing anything else. It also recognizes {@link MutableOffsetMap} (as returned by
 152      * {@link #toModifiableMap()}) and makes an efficient copy of its contents. All other maps are converted to an
 153      * {@link ImmutableOffsetMap}. Iterator order is not guaranteed to be retained.
 154      *
 155      * @param <K> the type of keys maintained by the map
 156      * @param <V> the type of mapped values
 157      * @param map Input map, may not be null.
 158      * @return An isolated, immutable copy of the input map
 159      * @throws NullPointerException if {@code map} or any of its elements is null.
 160      */
 161     public static <K, V> @NonNull Map<K, V> unorderedCopyOf(final @NonNull Map<K, V> map) {
 162         final Map<K, V> common = commonCopy(map);
 163         if (common != null) {
 164             return common;
 165         }
 166
 167         if (map.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 ImmutableMap<K, Integer> offsets = OffsetMapCache.unorderedOffsets(map.keySet());
 174         return new Unordered<>(offsets, createArray(offsets, map));
 175     }
 176
 177     private static <K, V> V[] createArray(final ImmutableMap<K, Integer> offsets, final Map<K, V> map) {
 178         @SuppressWarnings("unchecked")
 179         final V[] array = (V[]) new Object[offsets.size()];
 180         for (Entry<K, V> e : map.entrySet()) {
 181             array[verifyNotNull(offsets.get(e.getKey()))] = e.getValue();
 182         }
 183         return array;
 184     }
 185
 186     private static <K, V> @Nullable Map<K, V> commonCopy(final @NonNull Map<K, V> map) {
 187         // Prevent a copy. Note that ImmutableMap is not listed here because of its potentially larger keySet overhead.
 188         if (map instanceof ImmutableOffsetMap || map instanceof SharedSingletonMap) {
 189             return map;
 190         }
 191
 192         // Familiar and efficient to copy
 193         if (map instanceof MutableOffsetMap<K, V> mop) {
 194             return mop.toUnmodifiableMap();
 195         }
 196
 197         if (map.isEmpty()) {
 198             // Shares a single object
 199             return ImmutableMap.of();
 200         }
 201
 202         return null;
 203     }
 204
 205     @Override
 206     public final int size() {
 207         return offsets.size();
 208     }
 209
 210     @Override
 211     public final boolean isEmpty() {
 212         return offsets.isEmpty();
 213     }
 214
 215     @Override
 216     public final int hashCode() {
 217         if (hashCode != 0) {
 218             return hashCode;
 219         }
 220
 221         int result = 0;
 222         for (Entry<K, Integer> e : offsets.entrySet()) {
 223             result += e.getKey().hashCode() ^ objects[e.getValue()].hashCode();
 224         }
 225
 226         hashCode = result;
 227         return result;
 228     }
 229
 230     @Override
 231     public final boolean equals(final Object obj) {
 232         if (obj == this) {
 233             return true;
 234         }
 235         if (!(obj instanceof Map<?, ?> other)) {
 236             return false;
 237         }
 238
 239         if (obj instanceof ImmutableOffsetMap<?, ?> om) {
 240             // If the offset match, the arrays have to match, too
 241             if (offsets.equals(om.offsets)) {
 242                 return Arrays.deepEquals(objects, om.objects);
 243             }
 244         } else if (obj instanceof MutableOffsetMap) {
 245             // Let MutableOffsetMap do the actual work.
 246             return obj.equals(this);
 247         }
 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         Integer offset;
 287         return (offset = offsets.get(key)) == 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(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     @Override
 317     public final @NonNull Collection<V> values() {
 318         return new ConstantArrayCollection<>(objects);
 319     }
 320
 321     @Override
 322     public final @NonNull Set<Entry<K, V>> entrySet() {
 323         return new EntrySet();
 324     }
 325
 326     @Override
 327     public final String toString() {
 328         final StringBuilder sb = new StringBuilder("{");
 329         final Iterator<K> it = offsets.keySet().iterator();
 330         int offset = 0;
 331         while (it.hasNext()) {
 332             sb.append(it.next()).append('=').append(objects[offset++]);
 333
 334             if (it.hasNext()) {
 335                 sb.append(", ");
 336             }
 337         }
 338
 339         return sb.append('}').toString();
 340     }
 341
 342     final @NonNull ImmutableMap<K, Integer> offsets() {
 343         return offsets;
 344     }
 345
 346     final @NonNull V[] objects() {
 347         return objects;
 348     }
 349
 350     private final class EntrySet extends AbstractSet<Entry<K, V>> {
 351         @Override
 352         public @NonNull Iterator<Entry<K, V>> iterator() {
 353             final Iterator<Entry<K, Integer>> it = offsets.entrySet().iterator();
 354             return new UnmodifiableIterator<>() {
 355                 @Override
 356                 public boolean hasNext() {
 357                     return it.hasNext();
 358                 }
 359
 360                 @Override
 361                 public Entry<K, V> next() {
 362                     final Entry<K, Integer> e = it.next();
 363                     return new SimpleImmutableEntry<>(e.getKey(), objects[e.getValue()]);
 364                 }
 365             };
 366         }
 367
 368         @Override
 369         public int size() {
 370             return offsets.size();
 371         }
 372     }
 373
 374     @Serial
 375     private void writeObject(final ObjectOutputStream out) throws IOException {
 376         out.writeInt(offsets.size());
 377         for (Entry<K, V> e : entrySet()) {
 378             out.writeObject(e.getKey());
 379             out.writeObject(e.getValue());
 380         }
 381     }
 382
 383     // FIXME: this is ugly, use an Externalizable proxy
 384     private static final Field OFFSETS_FIELD = fieldFor("offsets");
 385     private static final Field ARRAY_FIELD = fieldFor("objects");
 386
 387     private static @NonNull Field fieldFor(final @NonNull String name) {
 388         final Field f;
 389         try {
 390             f = ImmutableOffsetMap.class.getDeclaredField(name);
 391         } catch (NoSuchFieldException | SecurityException e) {
 392             throw new IllegalStateException("Failed to lookup field " + name, e);
 393         }
 394
 395         f.setAccessible(true);
 396         return f;
 397     }
 398
 399     private static void setField(final @NonNull ImmutableOffsetMap<?, ?> map, final @NonNull Field field,
 400             final Object value) throws IOException {
 401         try {
 402             field.set(map, value);
 403         } catch (IllegalArgumentException | IllegalAccessException e) {
 404             throw new IOException("Failed to set field " + field, e);
 405         }
 406     }
 407
 408     @Serial
 409     @SuppressWarnings("unchecked")
 410     private void readObject(final @NonNull 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 }