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