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.copyOf(this);
  50         }
  51
  52         @Override
  53         Map<K, Integer> resolveKeys(final List<K> keys) {
  54             return OffsetMapCache.orderedOffsets(keys);
  55         }
  56     }
  57
  58     private static final long serialVersionUID = 1L;
  59
  60     private final Map<K, Integer> offsets;
  61     private final V[] objects;
  62     private int hashCode;
  63
  64     /**
  65      * Construct a new instance backed by specified key-to-offset map and array of objects.
  66      *
  67      * @param offsets Key-to-offset map, may not be null
  68      * @param objects Array of value object, may not be null. The array is stored as is, the caller
  69      *              is responsible for ensuring its contents remain unmodified.
  70      */
  71     ImmutableOffsetMap(@Nonnull final Map<K, Integer> offsets, @Nonnull final V[] objects) {
  72         this.offsets = Preconditions.checkNotNull(offsets);
  73         this.objects = Preconditions.checkNotNull(objects);
  74         Preconditions.checkArgument(offsets.size() == objects.length);
  75     }
  76
  77     @Override
  78     public abstract MutableOffsetMap<K, V> toModifiableMap();
  79
  80     abstract Map<K, Integer> resolveKeys(List<K> keys);
  81
  82     /**
  83      * Create an {@link ImmutableOffsetMap} as a copy of an existing map. This is actually not completely true,
  84      * as this method returns an {@link ImmutableMap} for empty and singleton inputs, as those are more memory-efficient.
  85      * This method also recognizes {@link ImmutableOffsetMap} on input, and returns it back without doing anything else.
  86      * It also recognizes {@link MutableOffsetMap} (as returned by {@link #toModifiableMap()}) and makes an efficient
  87      * copy of its contents. All other maps are converted to an {@link ImmutableOffsetMap} with the same iteration
  88      * order as input.
  89      *
  90      * @param m Input map, may not be null.
  91      * @return An isolated, immutable copy of the input map
  92      */
  93     @Nonnull public static <K, V> Map<K, V> copyOf(@Nonnull final Map<K, V> m) {
  94         // Prevent a copy. Note that ImmutableMap is not listed here because of its potentially larger keySet overhead.
  95         if (m instanceof ImmutableOffsetMap || m instanceof SharedSingletonMap) {
  96             return m;
  97         }
  98
  99         // Familiar and efficient to copy
 100         if (m instanceof MutableOffsetMap) {
 101             return ((MutableOffsetMap<K, V>) m).toUnmodifiableMap();
 102         }
 103
 104         final int size = m.size();
 105         if (size == 0) {
 106             // Shares a single object
 107             return ImmutableMap.of();
 108         }
 109         if (size == 1) {
 110             // Efficient single-entry implementation
 111             final Entry<K, V> e = m.entrySet().iterator().next();
 112             return SharedSingletonMap.of(e.getKey(), e.getValue());
 113         }
 114
 115         final Map<K, Integer> offsets = OffsetMapCache.orderedOffsets(m.keySet());
 116         @SuppressWarnings("unchecked")
 117         final V[] array = (V[]) new Object[offsets.size()];
 118         for (Entry<K, V> e : m.entrySet()) {
 119             array[offsets.get(e.getKey())] = e.getValue();
 120         }
 121
 122         return new Ordered<>(offsets, array);
 123     }
 124
 125     @Override
 126     public final int size() {
 127         return offsets.size();
 128     }
 129
 130     @Override
 131     public final boolean isEmpty() {
 132         return offsets.isEmpty();
 133     }
 134
 135     @Override
 136     public final int hashCode() {
 137         if (hashCode != 0) {
 138             return hashCode;
 139         }
 140
 141         int result = 0;
 142         for (Entry<K, Integer> e : offsets.entrySet()) {
 143             result += e.getKey().hashCode() ^ objects[e.getValue()].hashCode();
 144         }
 145
 146         hashCode = result;
 147         return result;
 148     }
 149
 150     @Override
 151     public final boolean equals(final Object o) {
 152         if (o == this) {
 153             return true;
 154         }
 155         if (!(o instanceof Map)) {
 156             return false;
 157         }
 158
 159         if (o instanceof ImmutableOffsetMap) {
 160             final ImmutableOffsetMap<?, ?> om = (ImmutableOffsetMap<?, ?>) o;
 161
 162             // If the offset match, the arrays have to match, too
 163             if (offsets.equals(om.offsets)) {
 164                 return Arrays.deepEquals(objects, om.objects);
 165             }
 166         } else if (o instanceof MutableOffsetMap) {
 167             // Let MutableOffsetMap do the actual work.
 168             return o.equals(this);
 169         }
 170
 171         final Map<?, ?> other = (Map<?, ?>)o;
 172
 173         // Size and key sets have to match
 174         if (size() != other.size() || !keySet().equals(other.keySet())) {
 175             return false;
 176         }
 177
 178         try {
 179             // Ensure all objects are present
 180             for (Entry<K, Integer> e : offsets.entrySet()) {
 181                 if (!objects[e.getValue()].equals(other.get(e.getKey()))) {
 182                     return false;
 183                 }
 184             }
 185         } catch (ClassCastException e) {
 186             // Can be thrown by other.get() indicating we have incompatible key types
 187             return false;
 188         }
 189
 190         return true;
 191     }
 192
 193     @Override
 194     public final boolean containsKey(final Object key) {
 195         return offsets.containsKey(key);
 196     }
 197
 198     @Override
 199     public final boolean containsValue(final Object value) {
 200         for (Object o : objects) {
 201             if (value.equals(o)) {
 202                 return true;
 203             }
 204         }
 205         return false;
 206     }
 207
 208     @Override
 209     public final V get(final Object key) {
 210         final Integer offset = offsets.get(key);
 211         return offset == null ? null : objects[offset];
 212     }
 213
 214     @Override
 215     public final V remove(final Object key) {
 216         throw new UnsupportedOperationException();
 217     }
 218
 219     @Override
 220     public final V put(final K key, final V value) {
 221         throw new UnsupportedOperationException();
 222     }
 223
 224     @Override
 225     public final void putAll(final Map<? extends K, ? extends V> m) {
 226         throw new UnsupportedOperationException();
 227     }
 228
 229     @Override
 230     public final void clear() {
 231         throw new UnsupportedOperationException();
 232     }
 233
 234     @Override
 235     public final Set<K> keySet() {
 236         return offsets.keySet();
 237     }
 238
 239     @Override
 240     public final Collection<V> values() {
 241         return new ConstantArrayCollection<>(objects);
 242     }
 243
 244     @Override
 245     public final Set<Entry<K, V>> entrySet() {
 246         return new EntrySet();
 247     }
 248
 249     @Override
 250     public final String toString() {
 251         final StringBuilder sb = new StringBuilder("{");
 252         final Iterator<K> it = offsets.keySet().iterator();
 253         int i = 0;
 254         while (it.hasNext()) {
 255             sb.append(it.next());
 256             sb.append('=');
 257             sb.append(objects[i++]);
 258
 259             if (it.hasNext()) {
 260                 sb.append(", ");
 261             }
 262         }
 263
 264         return sb.append('}').toString();
 265     }
 266
 267     final Map<K, Integer> offsets() {
 268         return offsets;
 269     }
 270
 271     final V[] objects() {
 272         return objects;
 273     }
 274
 275     private final class EntrySet extends AbstractSet<Entry<K, V>> {
 276         @Override
 277         public Iterator<Entry<K, V>> iterator() {
 278             final Iterator<Entry<K, Integer>> it = offsets.entrySet().iterator();
 279
 280             return new UnmodifiableIterator<Entry<K, V>>() {
 281                 @Override
 282                 public boolean hasNext() {
 283                     return it.hasNext();
 284                 }
 285
 286                 @Override
 287                 public Entry<K, V> next() {
 288                     final Entry<K, Integer> e = it.next();
 289                     return new SimpleImmutableEntry<>(e.getKey(), objects[e.getValue()]);
 290                 }
 291             };
 292         }
 293
 294         @Override
 295         public int size() {
 296             return offsets.size();
 297         }
 298     }
 299
 300     private void writeObject(final ObjectOutputStream out) throws IOException {
 301         out.writeInt(offsets.size());
 302         for (Entry<K, V> e : entrySet()) {
 303             out.writeObject(e.getKey());
 304             out.writeObject(e.getValue());
 305         }
 306     }
 307
 308     private static final Field OFFSETS_FIELD = fieldFor("offsets");
 309     private static final Field ARRAY_FIELD = fieldFor("objects");
 310
 311     private static Field fieldFor(final String name) {
 312         final Field f;
 313         try {
 314             f = ImmutableOffsetMap.class.getDeclaredField(name);
 315         } catch (NoSuchFieldException | SecurityException e) {
 316             throw new IllegalStateException("Failed to lookup field " + name, e);
 317         }
 318
 319         f.setAccessible(true);
 320         return f;
 321     }
 322
 323     private void setField(final Field field, final Object value) throws IOException {
 324         try {
 325             field.set(this, value);
 326         } catch (IllegalArgumentException | IllegalAccessException e) {
 327             throw new IOException("Failed to set field " + field, e);
 328         }
 329     }
 330
 331     @SuppressWarnings("unchecked")
 332     private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
 333         final int s = in.readInt();
 334
 335         final List<K> keys = new ArrayList<>(s);
 336         final V[] values = (V[]) new Object[s];
 337
 338         for (int i = 0; i < s; ++i) {
 339             keys.add((K)in.readObject());
 340             values[i] = (V)in.readObject();
 341         }
 342
 343         setField(OFFSETS_FIELD, resolveKeys(keys));
 344         setField(ARRAY_FIELD, values);
 345     }
 346 }