common/util/src/main/java/org/opendaylight/yangtools/util/MutableOffsetMap.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.annotations.VisibleForTesting;
  12 import com.google.common.base.Preconditions;
  13 import com.google.common.base.Verify;
  14 import com.google.common.collect.ImmutableMap;
  15 import java.util.AbstractMap;
  16 import java.util.AbstractSet;
  17 import java.util.ArrayList;
  18 import java.util.Arrays;
  19 import java.util.Collection;
  20 import java.util.ConcurrentModificationException;
  21 import java.util.HashMap;
  22 import java.util.Iterator;
  23 import java.util.LinkedHashMap;
  24 import java.util.Map;
  25 import java.util.NoSuchElementException;
  26 import java.util.Set;
  27
  28 /**
  29  * A mutable version of {@link ImmutableOffsetMap}. It inherits the set of mappings from the immutable version and
  30  * allows updating/removing existing mappings. New mappings are stored in a dedicated {@link LinkedHashMap} to preserve
  31  * insertion order. It also tracks the need to duplicate the backing array, so the sequence of
  32  * <code>
  33  * ImmutableOffsetMap&lt;K, V&gt; source;
  34  * ImmutableOffsetMap&lt;K, V&gt; result = source.createMutableClone().immutableCopy();
  35  * </code>
  36  * results in source and result sharing the backing objects.
  37  *
  38  * This map does not support null keys nor values.
  39  *
  40  * @param <K> the type of keys maintained by this map
  41  * @param <V> the type of mapped values
  42  */
  43 @Beta
  44 public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implements Cloneable, ModifiableMapPhase<K, V> {
  45     static final class Ordered<K, V> extends MutableOffsetMap<K, V> {
  46         Ordered() {
  47             super(new LinkedHashMap<K, V>());
  48         }
  49
  50         Ordered(final Map<K, V> source) {
  51             super(OffsetMapCache.orderedOffsets(source.keySet()), source, new LinkedHashMap<K, V>());
  52         }
  53
  54         Ordered(final Map<K, Integer> offsets, final V[] objects) {
  55             super(offsets, objects, new LinkedHashMap<K, V>());
  56         }
  57     }
  58
  59     private static final Object[] EMPTY_ARRAY = new Object[0];
  60     private final Map<K, Integer> offsets;
  61     private HashMap<K, V> newKeys;
  62     private V[] objects;
  63     private int removed = 0;
  64     private transient volatile int modCount;
  65     private boolean needClone = true;
  66
  67     MutableOffsetMap(final Map<K, Integer> offsets, final V[] objects, final HashMap<K, V> newKeys) {
  68         Verify.verify(newKeys.isEmpty());
  69         this.offsets = Preconditions.checkNotNull(offsets);
  70         this.objects = Preconditions.checkNotNull(objects);
  71         this.newKeys = Preconditions.checkNotNull(newKeys);
  72     }
  73
  74     @SuppressWarnings("unchecked")
  75     MutableOffsetMap(final HashMap<K, V> newKeys) {
  76         this(ImmutableMap.<K, Integer>of(), (V[]) EMPTY_ARRAY, newKeys);
  77     }
  78
  79     @SuppressWarnings("unchecked")
  80     MutableOffsetMap(final Map<K, Integer> offsets, final Map<K, V> source, final HashMap<K, V> newKeys) {
  81         this(offsets, (V[]) new Object[offsets.size()], newKeys);
  82
  83         for (Entry<K, V> e : source.entrySet()) {
  84             objects[offsets.get(e.getKey())] = Preconditions.checkNotNull(e.getValue());
  85         }
  86
  87         this.needClone = false;
  88     }
  89
  90     public static <K, V> MutableOffsetMap<K, V> copyOf(final Map<K, V> m) {
  91         if (m instanceof MutableOffsetMap) {
  92             return ((MutableOffsetMap<K, V>) m).clone();
  93         }
  94         if (m instanceof ImmutableOffsetMap) {
  95             final ImmutableOffsetMap<K, V> om = (ImmutableOffsetMap<K, V>) m;
  96             return new MutableOffsetMap.Ordered<>(om.offsets(), om.objects());
  97         }
  98
  99         return new MutableOffsetMap.Ordered<>(m);
 100     }
 101
 102     public static <K, V> MutableOffsetMap<K, V> of() {
 103         return new MutableOffsetMap.Ordered<>();
 104     }
 105
 106     @Override
 107     public final int size() {
 108         return offsets.size() + newKeys.size() - removed;
 109     }
 110
 111     @Override
 112     public final boolean isEmpty() {
 113         return size() == 0;
 114     }
 115
 116     @Override
 117     public final boolean containsKey(final Object key) {
 118         final Integer offset = offsets.get(key);
 119         return offset == null ? newKeys.containsKey(key) : objects[offset] != null;
 120     }
 121
 122     @Override
 123     public final V get(final Object key) {
 124         final Integer offset = offsets.get(key);
 125         return offset == null ? newKeys.get(key) : objects[offset];
 126     }
 127
 128     private void cloneArray() {
 129         if (needClone) {
 130             needClone = false;
 131             if (!EMPTY_ARRAY.equals(objects)) {
 132                 objects = objects.clone();
 133             }
 134         }
 135     }
 136
 137     @Override
 138     public V put(final K key, final V value) {
 139         Preconditions.checkNotNull(value);
 140         final Integer offset = offsets.get(Preconditions.checkNotNull(key));
 141         if (offset == null) {
 142             final V ret = newKeys.put(key, value);
 143             if (ret == null) {
 144                 modCount++;
 145             }
 146             return ret;
 147         }
 148
 149         cloneArray();
 150         final V ret = objects[offset];
 151         objects[offset] = value;
 152         if (ret == null) {
 153             modCount++;
 154             removed--;
 155         }
 156
 157         return ret;
 158     }
 159
 160     @Override
 161     public V remove(final Object key) {
 162         final Integer offset = offsets.get(key);
 163         if (offset == null) {
 164             final V ret = newKeys.remove(key);
 165             if (ret != null) {
 166                 modCount++;
 167             }
 168             return ret;
 169         }
 170
 171         cloneArray();
 172         final V ret = objects[offset];
 173         objects[offset] = null;
 174         if (ret != null) {
 175             modCount++;
 176             removed++;
 177         }
 178         return ret;
 179     }
 180
 181     @Override
 182     public void clear() {
 183         if (size() != 0) {
 184             newKeys.clear();
 185             cloneArray();
 186             Arrays.fill(objects, null);
 187             removed = objects.length;
 188             modCount++;
 189         }
 190     }
 191
 192     @Override
 193     public final Set<Entry<K, V>> entrySet() {
 194         return new EntrySet();
 195     }
 196
 197     @Override
 198     public Map<K, V> toUnmodifiableMap() {
 199         if (newKeys.isEmpty() && removed == 0) {
 200             // Make sure next modification clones the array, as we leak it to the map we return.
 201             needClone = true;
 202             /*
 203              * TODO: we could track the ImmutableOffsetMap from which this one was instantiated and if we do not
 204              *       perform any modifications, just return the original instance. The trade-off is increased complexity
 205              *       and an additional field in this class.
 206              */
 207             return new ImmutableOffsetMap.Ordered<>(offsets, objects);
 208         }
 209
 210         final int s = size();
 211         if (s == 0) {
 212             return ImmutableMap.of();
 213         }
 214         if (s == 1) {
 215             return ImmutableMap.copyOf(this);
 216         }
 217
 218         // Construct the set of keys
 219         final Collection<K> keyset = new ArrayList<>(s);
 220         if (removed != 0) {
 221             if (removed != offsets.size()) {
 222                 for (Entry<K, Integer> e : offsets.entrySet()) {
 223                     if (objects[e.getValue()] != null) {
 224                         keyset.add(e.getKey());
 225                     }
 226                 }
 227             }
 228         } else {
 229             keyset.addAll(offsets.keySet());
 230         }
 231         keyset.addAll(newKeys.keySet());
 232
 233         // Construct the values
 234         @SuppressWarnings("unchecked")
 235         final V[] values = (V[])new Object[keyset.size()];
 236         int i = 0;
 237         if (removed != 0) {
 238             if (removed != offsets.size()) {
 239                 for (Entry<K, Integer> e : offsets.entrySet()) {
 240                     final V o = objects[e.getValue()];
 241                     if (o != null) {
 242                         values[i++] = o;
 243                     }
 244                 }
 245             }
 246         } else {
 247             System.arraycopy(objects, 0, values, 0, offsets.size());
 248             i = offsets.size();
 249         }
 250         for (V v : newKeys.values()) {
 251             values[i++] = v;
 252         }
 253
 254         return new ImmutableOffsetMap.Ordered<>(OffsetMapCache.orderedOffsets(keyset), values);
 255     }
 256
 257     @SuppressWarnings("unchecked")
 258     @Override
 259     public MutableOffsetMap<K, V> clone() {
 260         final MutableOffsetMap<K, V> ret;
 261
 262         try {
 263             ret = (MutableOffsetMap<K, V>) super.clone();
 264         } catch (CloneNotSupportedException e) {
 265            throw new IllegalStateException("Clone is expected to work", e);
 266         }
 267
 268         ret.newKeys = (HashMap<K, V>) newKeys.clone();
 269         ret.needClone = true;
 270         return ret;
 271     }
 272
 273     @Override
 274     public final int hashCode() {
 275         int result = 0;
 276
 277         for (Entry<K, Integer> e : offsets.entrySet()) {
 278             final Object v = objects[e.getValue()];
 279             if (v != null) {
 280                 result += e.getKey().hashCode() ^ v.hashCode();
 281             }
 282         }
 283
 284         return result + newKeys.hashCode();
 285     }
 286
 287     @Override
 288     public final boolean equals(final Object o) {
 289         if (o == this) {
 290             return true;
 291         }
 292         if (!(o instanceof Map)) {
 293             return false;
 294         }
 295
 296         if (o instanceof ImmutableOffsetMap) {
 297             final ImmutableOffsetMap<?, ?> om = (ImmutableOffsetMap<?, ?>) o;
 298
 299             if (newKeys.isEmpty() && offsets.equals(om.offsets())) {
 300                 return Arrays.deepEquals(objects, om.objects());
 301             }
 302         } else if (o instanceof MutableOffsetMap) {
 303             final MutableOffsetMap<?, ?> om = (MutableOffsetMap<?, ?>) o;
 304
 305             if (offsets.equals(om.offsets)) {
 306                 return Arrays.deepEquals(objects, om.objects) && newKeys.equals(om.newKeys);
 307             }
 308         }
 309
 310         // Fall back to brute map compare
 311         final Map<?, ?> other = (Map<?, ?>)o;
 312
 313         // Size and key sets have to match
 314         if (size() != other.size() || !keySet().equals(other.keySet())) {
 315             return false;
 316         }
 317
 318         try {
 319             // Ensure all newKeys are present. Note newKeys is guaranteed to
 320             // not contain null value.
 321             for (Entry<K, V> e : newKeys.entrySet()) {
 322                 if (!e.getValue().equals(other.get(e.getKey()))) {
 323                     return false;
 324                 }
 325             }
 326
 327             // Ensure all objects are present
 328             for (Entry<K, Integer> e : offsets.entrySet()) {
 329                 final V v = objects[e.getValue()];
 330                 if (v != null && !v.equals(other.get(e.getKey()))) {
 331                     return false;
 332                 }
 333             }
 334         } catch (ClassCastException e) {
 335             // Can be thrown by other.get() and indicate we have incompatible key types
 336             return false;
 337         }
 338
 339         return true;
 340     }
 341
 342     @Override
 343     public final Set<K> keySet() {
 344         return new KeySet();
 345     }
 346
 347     @VisibleForTesting
 348     final boolean needClone() {
 349         return needClone;
 350     }
 351
 352     @VisibleForTesting
 353     final Object array() {
 354         return objects;
 355     }
 356
 357     @VisibleForTesting
 358     final Object newKeys() {
 359         return newKeys;
 360     }
 361
 362     private final class EntrySet extends AbstractSet<Entry<K, V>> {
 363         @Override
 364         public Iterator<Entry<K, V>> iterator() {
 365             return new AbstractSetIterator<Entry<K, V>>() {
 366                 @Override
 367                 public Entry<K, V> next() {
 368                     final K key = nextKey();
 369                     return new SimpleEntry<>(key, get(key));
 370                 }
 371             };
 372         }
 373
 374         @Override
 375         public int size() {
 376             return MutableOffsetMap.this.size();
 377         }
 378
 379         @Override
 380         public boolean contains(final Object o) {
 381             if (!(o instanceof Entry)) {
 382                 return false;
 383             }
 384
 385             @SuppressWarnings("unchecked")
 386             final Entry<K,V> e = (Entry<K,V>) o;
 387             if (e.getValue() == null) {
 388                 return false;
 389             }
 390
 391             return e.getValue().equals(MutableOffsetMap.this.get(e.getKey()));
 392         }
 393
 394         @Override
 395         public boolean add(final Entry<K, V> e) {
 396             Preconditions.checkNotNull(e.getValue());
 397             final V p = MutableOffsetMap.this.put(e.getKey(), e.getValue());
 398             return !e.getValue().equals(p);
 399         }
 400
 401         @Override
 402         public boolean remove(final Object o) {
 403             if (!(o instanceof Entry)) {
 404                 return false;
 405             }
 406
 407             @SuppressWarnings("unchecked")
 408             final Entry<K,V> e = (Entry<K,V>) o;
 409             if (e.getValue() == null) {
 410                 return false;
 411             }
 412
 413             final V v = MutableOffsetMap.this.get(e.getKey());
 414             if (e.getValue().equals(v)) {
 415                 MutableOffsetMap.this.remove(e.getKey());
 416                 return true;
 417             }
 418             return false;
 419         }
 420
 421         @Override
 422         public void clear() {
 423             MutableOffsetMap.this.clear();
 424         }
 425     }
 426
 427     private final class KeySet extends AbstractSet<K> {
 428         @Override
 429         public Iterator<K> iterator() {
 430             return new AbstractSetIterator<K>() {
 431                 @Override
 432                 public K next() {
 433                     return nextKey();
 434                 }
 435             };
 436         }
 437
 438         @Override
 439         public int size() {
 440             return MutableOffsetMap.this.size();
 441         }
 442     }
 443
 444     private abstract class AbstractSetIterator<E> implements Iterator<E> {
 445         private final Iterator<Entry<K, Integer>> oldIterator = offsets.entrySet().iterator();
 446         private final Iterator<K> newIterator = newKeys.keySet().iterator();
 447         private int expectedModCount = modCount;
 448         private K currentKey, nextKey;
 449
 450         AbstractSetIterator() {
 451             updateNextKey();
 452         }
 453
 454         private void updateNextKey() {
 455             while (oldIterator.hasNext()) {
 456                 final Entry<K, Integer> e = oldIterator.next();
 457                 if (objects[e.getValue()] != null) {
 458                     nextKey = e.getKey();
 459                     return;
 460                 }
 461             }
 462
 463             nextKey = newIterator.hasNext() ? newIterator.next() : null;
 464         }
 465
 466         private void checkModCount() {
 467             if (modCount != expectedModCount) {
 468                 throw new ConcurrentModificationException();
 469             }
 470         }
 471
 472         @Override
 473         public final boolean hasNext() {
 474             checkModCount();
 475             return nextKey != null;
 476         }
 477
 478         @Override
 479         public final void remove() {
 480             Preconditions.checkState(currentKey != null);
 481
 482             checkModCount();
 483             final Integer offset = offsets.get(currentKey);
 484             if (offset != null) {
 485                 cloneArray();
 486                 objects[offset] = null;
 487                 removed++;
 488             } else {
 489                 newIterator.remove();
 490             }
 491
 492             expectedModCount = ++modCount;
 493             currentKey = null;
 494         }
 495
 496         protected final K nextKey() {
 497             if (nextKey == null) {
 498                 throw new NoSuchElementException();
 499             }
 500
 501             checkModCount();
 502             currentKey = nextKey;
 503             updateNextKey();
 504
 505             return currentKey;
 506         }
 507     }
 508 }