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.AbstractSet;
  20 import java.util.ArrayList;
  21 import java.util.Arrays;
  22 import java.util.Iterator;
  23 import java.util.List;
  24 import java.util.Map;
  25 import java.util.Objects;
  26 import java.util.Set;
  27 import javax.annotation.Nonnull;
  28
  29 /**
  30  * Implementation of the {@link Map} interface which stores a set of immutable mappings using a key-to-offset map and
  31  * a backing array. This is useful for situations where the same key set is shared across a multitude of maps, as this
  32  * class uses a global cache to share the key-to-offset mapping.
  33  *
  34  * This map supports creation of value objects on the fly. To achieve that, subclasses should override {@link #valueToObject(Object)},
  35  * {@link #objectToValue(Object, Object)}, {@link #clone()} and {@link #toModifiableMap()} methods.
  36  *
  37  * @param <K> the type of keys maintained by this map
  38  * @param <V> the type of mapped values
  39  */
  40 @Beta
  41 public class ImmutableOffsetMap<K, V> extends AbstractLazyValueMap<K, V> implements UnmodifiableMapPhase<K, V>, Serializable {
  42     private static final long serialVersionUID = 1L;
  43
  44     private final Map<K, Integer> offsets;
  45     private final Object[] objects;
  46     private int hashCode;
  47
  48     /**
  49      * Construct a new instance backed by specified key-to-offset map and array of objects.
  50      *
  51      * @param offsets Key-to-offset map, may not be null
  52      * @param objects Array of value object, may not be null. The array is stored as is, the caller
  53      *              is responsible for ensuring its contents remain unmodified.
  54      */
  55     ImmutableOffsetMap(@Nonnull final Map<K, Integer> offsets, @Nonnull final Object[] objects) {
  56         this.offsets = Preconditions.checkNotNull(offsets);
  57         this.objects = Preconditions.checkNotNull(objects);
  58         Preconditions.checkArgument(offsets.size() == objects.length);
  59     }
  60
  61     /**
  62      * Construct a new instance based on some other instance.
  63      *
  64      * @param m Instance to share data with, may not be null.
  65      */
  66     protected ImmutableOffsetMap(@Nonnull final ImmutableOffsetMap<K, V> m) {
  67         this.offsets = m.offsets;
  68         this.objects = m.objects;
  69     }
  70
  71     /**
  72      * Create an {@link ImmutableOffsetMap} as a copy of an existing map. This is actually not completely true,
  73      * as this method returns an {@link ImmutableMap} for empty and singleton inputs, as those are more memory-efficient.
  74      * This method also recognizes {@link ImmutableOffsetMap} on input, and returns it back without doing anything else.
  75      * It also recognizes {@link MutableOffsetMap} (as returned by {@link #toModifiableMap()}) and makes an efficient
  76      * copy of its contents. All other maps are converted to an {@link ImmutableOffsetMap} with the same iteration
  77      * order as input.
  78      *
  79      * @param m Input map, may not be null.
  80      * @return An isolated, immutable copy of the input map
  81      */
  82     @Nonnull public static <K, V> Map<K, V> copyOf(@Nonnull final Map<K, V> m) {
  83         // Prevent a copy
  84         if (m instanceof ImmutableOffsetMap) {
  85             return m;
  86         }
  87
  88         // Better-packed
  89         final int size = m.size();
  90         if (size == 0) {
  91             return ImmutableMap.of();
  92         }
  93         if (size == 1) {
  94             return ImmutableMap.copyOf(m);
  95         }
  96
  97         // Familiar and efficient
  98         if (m instanceof MutableOffsetMap) {
  99             return ((MutableOffsetMap<K, V>) m).toUnmodifiableMap();
 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 final int size() {
 114         return offsets.size();
 115     }
 116
 117     @Override
 118     public final 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             final Object v = objects[e.getValue()];
 131             result += e.getKey().hashCode() ^ objectToValue(e.getKey(), v).hashCode();
 132         }
 133
 134         hashCode = result;
 135         return result;
 136     }
 137
 138     @Override
 139     public boolean equals(final Object o) {
 140         if (o == this) {
 141             return true;
 142         }
 143         if (o == null) {
 144             return false;
 145         }
 146
 147         if (o instanceof ImmutableOffsetMap) {
 148             final ImmutableOffsetMap<?, ?> om = (ImmutableOffsetMap<?, ?>) o;
 149             if (offsets.equals(om.offsets) && Arrays.deepEquals(objects, om.objects)) {
 150                 return true;
 151             }
 152         } else if (o instanceof MutableOffsetMap) {
 153             // Let MutableOffsetMap do the actual work.
 154             return o.equals(this);
 155         } else if (o instanceof Map) {
 156             final Map<?, ?> om = (Map<?, ?>)o;
 157
 158             // Size and key sets have to match
 159             if (size() != om.size() || !keySet().equals(om.keySet())) {
 160                 return false;
 161             }
 162
 163             try {
 164                 // Ensure all objects are present
 165                 for (Entry<K, Integer> e : offsets.entrySet()) {
 166                     final V v = objectToValue(e.getKey(), objects[e.getValue()]);
 167                     if (!v.equals(om.get(e.getKey()))) {
 168                         return false;
 169                     }
 170                 }
 171             } catch (ClassCastException e) {
 172                 // Can be thrown by om.get() and indicate we have incompatible key types
 173                 return false;
 174             }
 175
 176             return true;
 177         }
 178
 179         return false;
 180     }
 181
 182     @Override
 183     public final boolean containsKey(final Object key) {
 184         return offsets.containsKey(key);
 185     }
 186
 187     @Override
 188     public final boolean containsValue(final Object value) {
 189         @SuppressWarnings("unchecked")
 190         final Object obj = valueToObject((V)value);
 191         for (Object o : objects) {
 192             if (Objects.equals(obj, o)) {
 193                 return true;
 194             }
 195         }
 196         return false;
 197     }
 198
 199     @SuppressWarnings("unchecked")
 200     @Override
 201     public final V get(final Object key) {
 202         final Integer offset = offsets.get(key);
 203         if (offset == null) {
 204             return null;
 205         }
 206
 207         return objectToValue((K) key, objects[offset]);
 208     }
 209
 210     @Override
 211     public final V remove(final Object key) {
 212         throw new UnsupportedOperationException();
 213     }
 214
 215     @Override
 216     public final void putAll(final Map<? extends K, ? extends V> m) {
 217         throw new UnsupportedOperationException();
 218     }
 219
 220     @Override
 221     public final void clear() {
 222         throw new UnsupportedOperationException();
 223     }
 224
 225     @Override
 226     public final Set<K> keySet() {
 227         return offsets.keySet();
 228     }
 229
 230     @Override
 231     public final Set<Entry<K, V>> entrySet() {
 232         return new EntrySet();
 233     }
 234
 235     @Override
 236     public MutableOffsetMap<K, V> toModifiableMap() {
 237         return new MutableOffsetMap<>(this);
 238     }
 239
 240     Map<K, Integer> offsets() {
 241         return offsets;
 242     }
 243
 244     Object[] objects() {
 245         return objects;
 246     }
 247
 248     private final class EntrySet extends AbstractSet<Entry<K, V>> {
 249         @Override
 250         public Iterator<Entry<K, V>> iterator() {
 251             final Iterator<Entry<K, Integer>> it = offsets.entrySet().iterator();
 252
 253             return new UnmodifiableIterator<Entry<K, V>>() {
 254                 @Override
 255                 public boolean hasNext() {
 256                     return it.hasNext();
 257                 }
 258
 259                 @Override
 260                 public Entry<K, V> next() {
 261                     final Entry<K, Integer> e = it.next();
 262                     return new SimpleImmutableEntry<>(e.getKey(), objectToValue(e.getKey(), objects[e.getValue()]));
 263                 }
 264             };
 265         }
 266
 267         @Override
 268         public int size() {
 269             return offsets.size();
 270         }
 271     }
 272
 273     private void writeObject(final ObjectOutputStream out) throws IOException {
 274         out.writeInt(offsets.size());
 275         for (Entry<K, V> e : entrySet()) {
 276             out.writeObject(e.getKey());
 277             out.writeObject(e.getValue());
 278         }
 279     }
 280
 281     private static final Field OFFSETS_FIELD = fieldFor("offsets");
 282     private static final Field ARRAY_FIELD = fieldFor("objects");
 283
 284     private static Field fieldFor(final String name) {
 285         final Field f;
 286         try {
 287             f = ImmutableOffsetMap.class.getDeclaredField(name);
 288         } catch (NoSuchFieldException | SecurityException e) {
 289             throw new IllegalStateException("Failed to lookup field " + name, e);
 290         }
 291
 292         f.setAccessible(true);
 293         return f;
 294     }
 295
 296     private void setField(final Field field, final Object value) throws IOException {
 297         try {
 298             field.set(this, value);
 299         } catch (IllegalArgumentException | IllegalAccessException e) {
 300             throw new IOException("Failed to set field " + field, e);
 301         }
 302     }
 303
 304     @SuppressWarnings("unchecked")
 305     private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
 306         final int s = in.readInt();
 307
 308         final List<K> keys = new ArrayList<>(s);
 309         final V[] values = (V[]) new Object[s];
 310
 311         for (int i = 0; i < s; ++i) {
 312             keys.add((K)in.readObject());
 313             values[i] = (V)in.readObject();
 314         }
 315
 316         setField(OFFSETS_FIELD, OffsetMapCache.offsetsFor(keys));
 317         setField(ARRAY_FIELD, values);
 318     }
 319 }