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