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. Note that ImmutableMap is not listed here because of its potentially larger keySet overhead.
  84         if (m instanceof ImmutableOffsetMap || m instanceof SharedSingletonMap) {
  85             return m;
  86         }
  87
  88         // Familiar and efficient to copy
  89         if (m instanceof MutableOffsetMap) {
  90             return ((MutableOffsetMap<K, V>) m).toUnmodifiableMap();
  91         }
  92
  93         final int size = m.size();
  94         if (size == 0) {
  95             // Shares a single object
  96             return ImmutableMap.of();
  97         }
  98         if (size == 1) {
  99             // Efficient single-entry implementation
 100             final Entry<K, V> e = m.entrySet().iterator().next();
 101             return SharedSingletonMap.of(e.getKey(), e.getValue());
 102         }
 103
 104         final Map<K, Integer> offsets = OffsetMapCache.offsetsFor(m.keySet());
 105         @SuppressWarnings("unchecked")
 106         final V[] array = (V[]) new Object[offsets.size()];
 107         for (Entry<K, V> e : m.entrySet()) {
 108             array[offsets.get(e.getKey())] = e.getValue();
 109         }
 110
 111         return new ImmutableOffsetMap<>(offsets, array);
 112     }
 113
 114     @Override
 115     public final int size() {
 116         return offsets.size();
 117     }
 118
 119     @Override
 120     public final boolean isEmpty() {
 121         return offsets.isEmpty();
 122     }
 123
 124     @Override
 125     public int hashCode() {
 126         if (hashCode != 0) {
 127             return hashCode;
 128         }
 129
 130         int result = 0;
 131         for (Entry<K, Integer> e : offsets.entrySet()) {
 132             final Object v = objects[e.getValue()];
 133             result += e.getKey().hashCode() ^ objectToValue(e.getKey(), v).hashCode();
 134         }
 135
 136         hashCode = result;
 137         return result;
 138     }
 139
 140     @Override
 141     public boolean equals(final Object o) {
 142         if (o == this) {
 143             return true;
 144         }
 145         if (o == null) {
 146             return false;
 147         }
 148
 149         if (o instanceof ImmutableOffsetMap) {
 150             final ImmutableOffsetMap<?, ?> om = (ImmutableOffsetMap<?, ?>) o;
 151             if (offsets.equals(om.offsets) && Arrays.deepEquals(objects, om.objects)) {
 152                 return true;
 153             }
 154         } else if (o instanceof MutableOffsetMap) {
 155             // Let MutableOffsetMap do the actual work.
 156             return o.equals(this);
 157         } else if (o instanceof Map) {
 158             final Map<?, ?> om = (Map<?, ?>)o;
 159
 160             // Size and key sets have to match
 161             if (size() != om.size() || !keySet().equals(om.keySet())) {
 162                 return false;
 163             }
 164
 165             try {
 166                 // Ensure all objects are present
 167                 for (Entry<K, Integer> e : offsets.entrySet()) {
 168                     final V v = objectToValue(e.getKey(), objects[e.getValue()]);
 169                     if (!v.equals(om.get(e.getKey()))) {
 170                         return false;
 171                     }
 172                 }
 173             } catch (ClassCastException e) {
 174                 // Can be thrown by om.get() and indicate we have incompatible key types
 175                 return false;
 176             }
 177
 178             return true;
 179         }
 180
 181         return false;
 182     }
 183
 184     @Override
 185     public final boolean containsKey(final Object key) {
 186         return offsets.containsKey(key);
 187     }
 188
 189     @Override
 190     public final boolean containsValue(final Object value) {
 191         @SuppressWarnings("unchecked")
 192         final Object obj = valueToObject((V)value);
 193         for (Object o : objects) {
 194             if (Objects.equals(obj, o)) {
 195                 return true;
 196             }
 197         }
 198         return false;
 199     }
 200
 201     @SuppressWarnings("unchecked")
 202     @Override
 203     public final V get(final Object key) {
 204         final Integer offset = offsets.get(key);
 205         if (offset == null) {
 206             return null;
 207         }
 208
 209         return objectToValue((K) key, objects[offset]);
 210     }
 211
 212     @Override
 213     public final V remove(final Object key) {
 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 Set<Entry<K, V>> entrySet() {
 234         return new EntrySet();
 235     }
 236
 237     @Override
 238     public MutableOffsetMap<K, V> toModifiableMap() {
 239         return new MutableOffsetMap<>(this);
 240     }
 241
 242     Map<K, Integer> offsets() {
 243         return offsets;
 244     }
 245
 246     Object[] objects() {
 247         return objects;
 248     }
 249
 250     private final class EntrySet extends AbstractSet<Entry<K, V>> {
 251         @Override
 252         public Iterator<Entry<K, V>> iterator() {
 253             final Iterator<Entry<K, Integer>> it = offsets.entrySet().iterator();
 254
 255             return new UnmodifiableIterator<Entry<K, V>>() {
 256                 @Override
 257                 public boolean hasNext() {
 258                     return it.hasNext();
 259                 }
 260
 261                 @Override
 262                 public Entry<K, V> next() {
 263                     final Entry<K, Integer> e = it.next();
 264                     return new SimpleImmutableEntry<>(e.getKey(), objectToValue(e.getKey(), objects[e.getValue()]));
 265                 }
 266             };
 267         }
 268
 269         @Override
 270         public int size() {
 271             return offsets.size();
 272         }
 273     }
 274
 275     private void writeObject(final ObjectOutputStream out) throws IOException {
 276         out.writeInt(offsets.size());
 277         for (Entry<K, V> e : entrySet()) {
 278             out.writeObject(e.getKey());
 279             out.writeObject(e.getValue());
 280         }
 281     }
 282
 283     private static final Field OFFSETS_FIELD = fieldFor("offsets");
 284     private static final Field ARRAY_FIELD = fieldFor("objects");
 285
 286     private static Field fieldFor(final String name) {
 287         final Field f;
 288         try {
 289             f = ImmutableOffsetMap.class.getDeclaredField(name);
 290         } catch (NoSuchFieldException | SecurityException e) {
 291             throw new IllegalStateException("Failed to lookup field " + name, e);
 292         }
 293
 294         f.setAccessible(true);
 295         return f;
 296     }
 297
 298     private void setField(final Field field, final Object value) throws IOException {
 299         try {
 300             field.set(this, value);
 301         } catch (IllegalArgumentException | IllegalAccessException e) {
 302             throw new IOException("Failed to set field " + field, e);
 303         }
 304     }
 305
 306     @SuppressWarnings("unchecked")
 307     private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
 308         final int s = in.readInt();
 309
 310         final List<K> keys = new ArrayList<>(s);
 311         final V[] values = (V[]) new Object[s];
 312
 313         for (int i = 0; i < s; ++i) {
 314             keys.add((K)in.readObject());
 315             values[i] = (V)in.readObject();
 316         }
 317
 318         setField(OFFSETS_FIELD, OffsetMapCache.offsetsFor(keys));
 319         setField(ARRAY_FIELD, values);
 320     }
 321 }