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