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.collect.ImmutableMap;
  15 import com.google.common.collect.UnmodifiableIterator;
  16 import java.io.Serializable;
  17 import java.util.AbstractMap.SimpleImmutableEntry;
  18 import java.util.AbstractSet;
  19 import java.util.Arrays;
  20 import java.util.Collection;
  21 import java.util.Iterator;
  22 import java.util.Map;
  23 import java.util.Set;
  24 import org.eclipse.jdt.annotation.NonNull;
  25 import org.eclipse.jdt.annotation.Nullable;
  26
  27 /**
  28  * Implementation of the {@link Map} interface which stores a set of immutable mappings using a key-to-offset map and
  29  * a backing array. This is useful for situations where the same key set is shared across a multitude of maps, as this
  30  * class uses a global cache to share the key-to-offset mapping.
  31  *
  32  * <p>
  33  * In case the set of keys is statically known, you can use {@link ImmutableOffsetMapTemplate} to efficiently create
  34  * {@link ImmutableOffsetMap} instances.
  35  *
  36  * @param <K> the type of keys maintained by this map
  37  * @param <V> the type of mapped values
  38  */
  39 public abstract sealed class ImmutableOffsetMap<K, V> implements UnmodifiableMapPhase<K, V>, Serializable {
  40     static final class Ordered<K, V> extends ImmutableOffsetMap<K, V> {
  41         @java.io.Serial
  42         private static final long serialVersionUID = 1L;
  43
  44         Ordered(final ImmutableMap<K, Integer> offsets, final V[] objects) {
  45             super(offsets, objects);
  46         }
  47
  48         @Override
  49         public MutableOffsetMap<K, V> toModifiableMap() {
  50             return MutableOffsetMap.orderedCopyOf(this);
  51         }
  52
  53         @Override
  54         Object writeReplace() {
  55             return new OIOMv1(this);
  56         }
  57     }
  58
  59     static final class Unordered<K, V> extends ImmutableOffsetMap<K, V> {
  60         @java.io.Serial
  61         private static final long serialVersionUID = 1L;
  62
  63         Unordered(final ImmutableMap<K, Integer> offsets, final V[] objects) {
  64             super(offsets, objects);
  65         }
  66
  67         @Override
  68         public MutableOffsetMap<K, V> toModifiableMap() {
  69             return MutableOffsetMap.unorderedCopyOf(this);
  70         }
  71
  72         @Override
  73         Object writeReplace() {
  74             return new UIOMv1(this);
  75         }
  76     }
  77
  78     @java.io.Serial
  79     private static final long serialVersionUID = 1L;
  80
  81     private final @NonNull ImmutableMap<K, Integer> offsets;
  82     private final @NonNull V[] objects;
  83     private transient int hashCode;
  84
  85     /**
  86      * Construct a new instance backed by specified key-to-offset map and array of objects.
  87      *
  88      * @param offsets Key-to-offset map, may not be null
  89      * @param objects Array of value object, may not be null. The array is stored as is, the caller
  90      *              is responsible for ensuring its contents remain unmodified.
  91      */
  92     private ImmutableOffsetMap(final ImmutableMap<K, Integer> offsets, final V[] objects) {
  93         this.offsets = requireNonNull(offsets);
  94         this.objects = requireNonNull(objects);
  95         checkArgument(offsets.size() == objects.length);
  96     }
  97
  98     @Override
  99     public abstract @NonNull MutableOffsetMap<K, V> toModifiableMap();
 100
 101     /**
 102      * Create an {@link ImmutableOffsetMap} as a copy of an existing map. This is actually not completely true, as this
 103      * method returns an {@link ImmutableMap} for empty and singleton inputs, as those are more memory-efficient. This
 104      * method also recognizes {@link ImmutableOffsetMap} and {@link SharedSingletonMap} on input, and returns it back
 105      * without doing anything else. It also recognizes {@link MutableOffsetMap} (as returned by
 106      * {@link #toModifiableMap()}) and makes an efficient copy of its contents. All other maps are converted to an
 107      * {@link ImmutableOffsetMap} with the same iteration order as input.
 108      *
 109      * @param <K> the type of keys maintained by the map
 110      * @param <V> the type of mapped values
 111      * @param map Input map, may not be null.
 112      * @return An isolated, immutable copy of the input map
 113      * @throws NullPointerException if {@code map} or any of its elements is null.
 114      */
 115     public static <K, V> @NonNull Map<K, V> orderedCopyOf(final @NonNull Map<K, V> map) {
 116         final Map<K, V> common = commonCopy(map);
 117         if (common != null) {
 118             return common;
 119         }
 120
 121         final int size = map.size();
 122         if (size == 1) {
 123             // Efficient single-entry implementation
 124             final Entry<K, V> e = map.entrySet().iterator().next();
 125             return SharedSingletonMap.orderedOf(e.getKey(), e.getValue());
 126         }
 127
 128         final ImmutableMap<K, Integer> offsets = OffsetMapCache.orderedOffsets(map.keySet());
 129         return new Ordered<>(offsets, createArray(offsets, map));
 130     }
 131
 132     /**
 133      * Create an {@link ImmutableOffsetMap} as a copy of an existing map. This is actually not completely true, as this
 134      * method returns an {@link ImmutableMap} for empty and singleton inputs, as those are more memory-efficient. This
 135      * method also recognizes {@link ImmutableOffsetMap} and {@link SharedSingletonMap} on input, and returns it back
 136      * without doing anything else. It also recognizes {@link MutableOffsetMap} (as returned by
 137      * {@link #toModifiableMap()}) and makes an efficient copy of its contents. All other maps are converted to an
 138      * {@link ImmutableOffsetMap}. Iterator order is not guaranteed to be retained.
 139      *
 140      * @param <K> the type of keys maintained by the map
 141      * @param <V> the type of mapped values
 142      * @param map Input map, may not be null.
 143      * @return An isolated, immutable copy of the input map
 144      * @throws NullPointerException if {@code map} or any of its elements is null.
 145      */
 146     public static <K, V> @NonNull Map<K, V> unorderedCopyOf(final @NonNull Map<K, V> map) {
 147         final Map<K, V> common = commonCopy(map);
 148         if (common != null) {
 149             return common;
 150         }
 151
 152         if (map.size() == 1) {
 153             // Efficient single-entry implementation
 154             final Entry<K, V> e = map.entrySet().iterator().next();
 155             return SharedSingletonMap.unorderedOf(e.getKey(), e.getValue());
 156         }
 157
 158         final ImmutableMap<K, Integer> offsets = OffsetMapCache.unorderedOffsets(map.keySet());
 159         return new Unordered<>(offsets, createArray(offsets, map));
 160     }
 161
 162     private static <K, V> V[] createArray(final ImmutableMap<K, Integer> offsets, final Map<K, V> map) {
 163         @SuppressWarnings("unchecked")
 164         final V[] array = (V[]) new Object[offsets.size()];
 165         for (Entry<K, V> e : map.entrySet()) {
 166             array[verifyNotNull(offsets.get(e.getKey()))] = e.getValue();
 167         }
 168         return array;
 169     }
 170
 171     private static <K, V> @Nullable Map<K, V> commonCopy(final @NonNull Map<K, V> map) {
 172         // Prevent a copy. Note that ImmutableMap is not listed here because of its potentially larger keySet overhead.
 173         if (map instanceof ImmutableOffsetMap || map instanceof SharedSingletonMap) {
 174             return map;
 175         }
 176
 177         // Familiar and efficient to copy
 178         if (map instanceof MutableOffsetMap<K, V> mop) {
 179             return mop.toUnmodifiableMap();
 180         }
 181
 182         if (map.isEmpty()) {
 183             // Shares a single object
 184             return ImmutableMap.of();
 185         }
 186
 187         return null;
 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 obj) {
 217         if (obj == this) {
 218             return true;
 219         }
 220         if (!(obj instanceof Map<?, ?> other)) {
 221             return false;
 222         }
 223
 224         if (obj instanceof ImmutableOffsetMap<?, ?> om) {
 225             // If the offset match, the arrays have to match, too
 226             if (offsets.equals(om.offsets)) {
 227                 return Arrays.deepEquals(objects, om.objects);
 228             }
 229         } else if (obj instanceof MutableOffsetMap) {
 230             // Let MutableOffsetMap do the actual work.
 231             return obj.equals(this);
 232         }
 233
 234         // Size and key sets have to match
 235         if (size() != other.size() || !keySet().equals(other.keySet())) {
 236             return false;
 237         }
 238
 239         try {
 240             // Ensure all objects are present
 241             for (Entry<K, Integer> e : offsets.entrySet()) {
 242                 if (!objects[e.getValue()].equals(other.get(e.getKey()))) {
 243                     return false;
 244                 }
 245             }
 246         } catch (ClassCastException e) {
 247             // Can be thrown by other.get() indicating we have incompatible key types
 248             return false;
 249         }
 250
 251         return true;
 252     }
 253
 254     @Override
 255     public final boolean containsKey(final Object key) {
 256         return offsets.containsKey(key);
 257     }
 258
 259     @Override
 260     public final boolean containsValue(final Object value) {
 261         for (Object o : objects) {
 262             if (value.equals(o)) {
 263                 return true;
 264             }
 265         }
 266         return false;
 267     }
 268
 269     @Override
 270     public final V get(final Object key) {
 271         Integer offset;
 272         return (offset = offsets.get(key)) == null ? null : objects[offset];
 273     }
 274
 275     @Override
 276     public final V remove(final Object key) {
 277         throw new UnsupportedOperationException();
 278     }
 279
 280     @Override
 281     public final V put(final K key, final V value) {
 282         throw new UnsupportedOperationException();
 283     }
 284
 285     @Override
 286     @SuppressWarnings("checkstyle:parameterName")
 287     public final void putAll(final Map<? extends K, ? extends V> m) {
 288         throw new UnsupportedOperationException();
 289     }
 290
 291     @Override
 292     public final void clear() {
 293         throw new UnsupportedOperationException();
 294     }
 295
 296     @Override
 297     public final Set<K> keySet() {
 298         return offsets.keySet();
 299     }
 300
 301     @Override
 302     public final @NonNull Collection<V> values() {
 303         return new ConstantArrayCollection<>(objects);
 304     }
 305
 306     @Override
 307     public final @NonNull Set<Entry<K, V>> entrySet() {
 308         return new EntrySet();
 309     }
 310
 311     @Override
 312     public final String toString() {
 313         final StringBuilder sb = new StringBuilder("{");
 314         final Iterator<K> it = offsets.keySet().iterator();
 315         int offset = 0;
 316         while (it.hasNext()) {
 317             sb.append(it.next()).append('=').append(objects[offset++]);
 318
 319             if (it.hasNext()) {
 320                 sb.append(", ");
 321             }
 322         }
 323
 324         return sb.append('}').toString();
 325     }
 326
 327     final @NonNull ImmutableMap<K, Integer> offsets() {
 328         return offsets;
 329     }
 330
 331     final @NonNull V[] objects() {
 332         return objects;
 333     }
 334
 335     private final class EntrySet extends AbstractSet<Entry<K, V>> {
 336         @Override
 337         public @NonNull Iterator<Entry<K, V>> iterator() {
 338             final Iterator<Entry<K, Integer>> it = offsets.entrySet().iterator();
 339             return new UnmodifiableIterator<>() {
 340                 @Override
 341                 public boolean hasNext() {
 342                     return it.hasNext();
 343                 }
 344
 345                 @Override
 346                 public Entry<K, V> next() {
 347                     final Entry<K, Integer> e = it.next();
 348                     return new SimpleImmutableEntry<>(e.getKey(), objects[e.getValue()]);
 349                 }
 350             };
 351         }
 352
 353         @Override
 354         public int size() {
 355             return offsets.size();
 356         }
 357     }
 358
 359     @java.io.Serial
 360     abstract Object writeReplace();
 361 }