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 static com.google.common.base.Preconditions.checkState;
  11 import static com.google.common.base.Verify.verify;
  12 import static java.util.Objects.requireNonNull;
  13
  14 import com.google.common.annotations.Beta;
  15 import com.google.common.annotations.VisibleForTesting;
  16 import com.google.common.collect.ImmutableMap;
  17 import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
  18 import java.util.AbstractMap;
  19 import java.util.AbstractSet;
  20 import java.util.ArrayList;
  21 import java.util.Arrays;
  22 import java.util.ConcurrentModificationException;
  23 import java.util.HashMap;
  24 import java.util.Iterator;
  25 import java.util.LinkedHashMap;
  26 import java.util.List;
  27 import java.util.Map;
  28 import java.util.NoSuchElementException;
  29 import java.util.Set;
  30 import org.eclipse.jdt.annotation.NonNull;
  31 import org.eclipse.jdt.annotation.Nullable;
  32
  33 /**
  34  * A mutable version of {@link ImmutableOffsetMap}. It inherits the set of mappings from the immutable version and
  35  * allows updating/removing existing mappings. New mappings are stored in a dedicated {@link LinkedHashMap} to preserve
  36  * insertion order. It also tracks the need to duplicate the backing array, so the sequence of
  37  * <code>
  38  * ImmutableOffsetMap&lt;K, V&gt; source;
  39  * ImmutableOffsetMap&lt;K, V&gt; result = source.createMutableClone().immutableCopy();
  40  * </code>
  41  * results in source and result sharing the backing objects.
  42  *
  43  * <p>This map does not support null keys nor values.
  44  *
  45  * @param <K> the type of keys maintained by this map
  46  * @param <V> the type of mapped values
  47  */
  48 @Beta
  49 public abstract class MutableOffsetMap<K, V> extends AbstractMap<K, V> implements Cloneable, ModifiableMapPhase<K, V> {
  50     static final class Ordered<K, V> extends MutableOffsetMap<K, V> {
  51         Ordered() {
  52             super(new LinkedHashMap<>());
  53         }
  54
  55         Ordered(final Map<K, V> source) {
  56             super(OffsetMapCache.orderedOffsets(source.keySet()), source, new LinkedHashMap<>());
  57         }
  58
  59         Ordered(final ImmutableMap<K, Integer> offsets, final V[] objects) {
  60             super(offsets, objects, new LinkedHashMap<>());
  61         }
  62
  63         @Override
  64         Object removedObject() {
  65             return REMOVED;
  66         }
  67
  68         @Override
  69         UnmodifiableMapPhase<K, V> modifiedMap(final List<K> keys, final V[] values) {
  70             return new ImmutableOffsetMap.Ordered<>(OffsetMapCache.orderedOffsets(keys), values);
  71         }
  72
  73         @Override
  74         UnmodifiableMapPhase<K, V> unmodifiedMap(final ImmutableMap<K, Integer> offsetMap, final V[] values) {
  75             return new ImmutableOffsetMap.Ordered<>(offsetMap, values);
  76         }
  77
  78         @Override
  79         SharedSingletonMap<K, V> singletonMap() {
  80             return SharedSingletonMap.orderedCopyOf(this);
  81         }
  82     }
  83
  84     static final class Unordered<K, V> extends MutableOffsetMap<K, V> {
  85         Unordered() {
  86             super(new HashMap<>());
  87         }
  88
  89         Unordered(final Map<K, V> source) {
  90             super(OffsetMapCache.unorderedOffsets(source.keySet()), source, new HashMap<>());
  91         }
  92
  93         Unordered(final ImmutableMap<K, Integer> offsets, final V[] objects) {
  94             super(offsets, objects, new HashMap<>());
  95         }
  96
  97         @Override
  98         Object removedObject() {
  99             return null;
 100         }
 101
 102         @Override
 103         UnmodifiableMapPhase<K, V> modifiedMap(final List<K> keys, final V[] values) {
 104             final ImmutableMap<K, Integer> offsets = OffsetMapCache.unorderedOffsets(keys);
 105             return new ImmutableOffsetMap.Unordered<>(offsets, OffsetMapCache.adjustedArray(offsets, keys, values));
 106         }
 107
 108         @Override
 109         UnmodifiableMapPhase<K, V> unmodifiedMap(final ImmutableMap<K, Integer> offsetMap, final V[] values) {
 110             return new ImmutableOffsetMap.Unordered<>(offsetMap, values);
 111         }
 112
 113         @Override
 114         SharedSingletonMap<K, V> singletonMap() {
 115             return SharedSingletonMap.unorderedCopyOf(this);
 116         }
 117     }
 118
 119     private static final Object[] EMPTY_ARRAY = new Object[0];
 120     private static final Object REMOVED = new Object();
 121
 122     private final ImmutableMap<K, Integer> offsets;
 123     private HashMap<K, V> newKeys;
 124     private Object[] objects;
 125     private int removed = 0;
 126
 127     // Fail-fast iterator guard, see java.util.ArrayList for reference.
 128     @SuppressFBWarnings("VO_VOLATILE_INCREMENT")
 129     private transient volatile int modCount;
 130     private boolean needClone = true;
 131
 132     MutableOffsetMap(final ImmutableMap<K, Integer> offsets, final V[] objects, final HashMap<K, V> newKeys) {
 133         verify(newKeys.isEmpty());
 134         this.offsets = requireNonNull(offsets);
 135         this.objects = requireNonNull(objects);
 136         this.newKeys = requireNonNull(newKeys);
 137     }
 138
 139     @SuppressWarnings("unchecked")
 140     MutableOffsetMap(final HashMap<K, V> newKeys) {
 141         this(ImmutableMap.of(), (V[]) EMPTY_ARRAY, newKeys);
 142     }
 143
 144     @SuppressWarnings("unchecked")
 145     MutableOffsetMap(final ImmutableMap<K, Integer> offsets, final Map<K, V> source, final HashMap<K, V> newKeys) {
 146         this(offsets, (V[]) new Object[offsets.size()], newKeys);
 147
 148         for (Entry<K, V> e : source.entrySet()) {
 149             objects[offsets.get(e.getKey())] = requireNonNull(e.getValue());
 150         }
 151
 152         this.needClone = false;
 153     }
 154
 155     /**
 156      * Create a {@link MutableOffsetMap} of the specified map, retaining its iteration order.
 157      *
 158      * @param map input map
 159      * @return MutableOffsetMap with the same iteration order
 160      * @throws NullPointerException if {@code map} is null
 161      */
 162     public static <K, V> @NonNull MutableOffsetMap<K, V> orderedCopyOf(final Map<K, V> map) {
 163         if (map instanceof Ordered) {
 164             return ((Ordered<K, V>) map).clone();
 165         }
 166         if (map instanceof ImmutableOffsetMap) {
 167             final ImmutableOffsetMap<K, V> om = (ImmutableOffsetMap<K, V>) map;
 168             return new Ordered<>(om.offsets(), om.objects());
 169         }
 170
 171         return new Ordered<>(map);
 172     }
 173
 174     /**
 175      * Create a {@link MutableOffsetMap} of the specified map, potentially with a different iteration order.
 176      *
 177      * @param map input map
 178      * @return MutableOffsetMap with undefined iteration order
 179      * @throws NullPointerException if {@code map} is null
 180      */
 181     public static <K, V> @NonNull MutableOffsetMap<K, V> unorderedCopyOf(final Map<K, V> map) {
 182         if (map instanceof Unordered) {
 183             return ((Unordered<K, V>) map).clone();
 184         }
 185         if (map instanceof ImmutableOffsetMap) {
 186             final ImmutableOffsetMap<K, V> om = (ImmutableOffsetMap<K, V>) map;
 187             return new Unordered<>(om.offsets(), om.objects());
 188         }
 189
 190         return new Unordered<>(map);
 191     }
 192
 193     /**
 194      * Create an empty {@link MutableOffsetMap} which has an iteration order matching the insertion order.
 195      *
 196      * @return MutableOffsetMap which preserves insertion order
 197      */
 198     public static <K, V> @NonNull MutableOffsetMap<K, V> ordered() {
 199         return new MutableOffsetMap.Ordered<>();
 200     }
 201
 202     /**
 203      * Create an empty {@link MutableOffsetMap} which has unspecified iteration order.
 204      *
 205      * @return An MutableOffsetMap
 206      */
 207     public static <K, V> @NonNull MutableOffsetMap<K, V> unordered() {
 208         return new MutableOffsetMap.Unordered<>();
 209     }
 210
 211     abstract Object removedObject();
 212
 213     abstract UnmodifiableMapPhase<K, V> modifiedMap(List<K> keys, V[] values);
 214
 215     abstract UnmodifiableMapPhase<K, V> unmodifiedMap(ImmutableMap<K, Integer> offsetMap, V[] values);
 216
 217     abstract SharedSingletonMap<K, V> singletonMap();
 218
 219     @Override
 220     public final int size() {
 221         return offsets.size() + newKeys.size() - removed;
 222     }
 223
 224     @Override
 225     public final boolean isEmpty() {
 226         return size() == 0;
 227     }
 228
 229     @Override
 230     public final boolean containsKey(final Object key) {
 231         final Integer offset = offsets.get(key);
 232         if (offset != null) {
 233             final Object obj = objects[offset];
 234             if (!REMOVED.equals(obj)) {
 235                 return obj != null;
 236             }
 237         }
 238
 239         return newKeys.containsKey(key);
 240     }
 241
 242     @Override
 243     public final V get(final Object key) {
 244         final Integer offset = offsets.get(key);
 245         if (offset != null) {
 246             final Object obj = objects[offset];
 247
 248             /*
 249              * This is a bit tricky:  Ordered will put REMOVED to removed objects to retain strict insertion order.
 250              * Unordered will add null, indicating that the slot may be reused in future. Hence if we see a REMOVED
 251              * marker, we need to fall back to checking with new keys.
 252              */
 253             if (!REMOVED.equals(obj)) {
 254                 @SuppressWarnings("unchecked")
 255                 final V ret = (V)obj;
 256                 return ret;
 257             }
 258         }
 259
 260         return newKeys.get(key);
 261     }
 262
 263     private void cloneArray() {
 264         if (needClone) {
 265             needClone = false;
 266             if (objects.length != 0) {
 267                 objects = objects.clone();
 268             }
 269         }
 270     }
 271
 272     @Override
 273     public final V put(final K key, final V value) {
 274         requireNonNull(value);
 275         final Integer offset = offsets.get(requireNonNull(key));
 276         if (offset != null) {
 277             final Object obj = objects[offset];
 278
 279             /*
 280              * Put which can potentially replace something in objects. Replacing an object does not cause iterators
 281              * to be invalidated and does follow insertion order (since it is not a fresh insert). If the object has
 282              * been removed, we fall back to newKeys.
 283              */
 284             if (!REMOVED.equals(obj)) {
 285                 @SuppressWarnings("unchecked")
 286                 final V ret = (V)obj;
 287
 288                 cloneArray();
 289                 objects[offset] = value;
 290                 if (ret == null) {
 291                     modCount++;
 292                     removed--;
 293                 }
 294
 295                 return ret;
 296             }
 297         }
 298
 299         final V ret = newKeys.put(key, value);
 300         if (ret == null) {
 301             modCount++;
 302         }
 303         return ret;
 304     }
 305
 306     @Override
 307     public final V remove(final Object key) {
 308         final Integer offset = offsets.get(key);
 309         if (offset != null) {
 310             final Object obj = objects[offset];
 311
 312             /*
 313              * A previous remove() may have indicated that the objects slot cannot be reused. In that case we need
 314              * to fall back to checking with newKeys.
 315              */
 316             if (!REMOVED.equals(obj)) {
 317                 cloneArray();
 318
 319                 @SuppressWarnings("unchecked")
 320                 final V ret = (V)obj;
 321                 objects[offset] = removedObject();
 322                 if (ret != null) {
 323                     modCount++;
 324                     removed++;
 325                 }
 326                 return ret;
 327             }
 328         }
 329
 330         final V ret = newKeys.remove(key);
 331         if (ret != null) {
 332             modCount++;
 333         }
 334         return ret;
 335     }
 336
 337     @Override
 338     public final void clear() {
 339         if (size() != 0) {
 340             newKeys.clear();
 341             cloneArray();
 342             Arrays.fill(objects, removedObject());
 343             removed = objects.length;
 344             modCount++;
 345         }
 346     }
 347
 348     @Override
 349     public final @NonNull Set<Entry<K, V>> entrySet() {
 350         return new EntrySet();
 351     }
 352
 353     @Override
 354     public @NonNull Map<K, V> toUnmodifiableMap() {
 355         if (removed == 0 && newKeys.isEmpty()) {
 356             // Make sure next modification clones the array, as we leak it to the map we return.
 357             needClone = true;
 358
 359             // We have ended up with no removed objects, hence this cast is safe
 360             @SuppressWarnings("unchecked")
 361             final V[] values = (V[])objects;
 362
 363             /*
 364              * TODO: we could track the ImmutableOffsetMap from which this one was instantiated and if we do not
 365              *       perform any modifications, just return the original instance. The trade-off is increased complexity
 366              *       and an additional field in this class.
 367              */
 368             return unmodifiedMap(offsets, values);
 369         }
 370
 371         final int s = size();
 372         if (s == 0) {
 373             return ImmutableMap.of();
 374         }
 375         if (s == 1) {
 376             return singletonMap();
 377         }
 378
 379         // Construct the set of keys
 380         final List<K> keyset = new ArrayList<>(s);
 381         if (removed != 0) {
 382             if (removed != offsets.size()) {
 383                 for (Entry<K, Integer> e : offsets.entrySet()) {
 384                     final Object o = objects[e.getValue()];
 385                     if (o != null && !REMOVED.equals(o)) {
 386                         keyset.add(e.getKey());
 387                     }
 388                 }
 389             }
 390         } else {
 391             keyset.addAll(offsets.keySet());
 392         }
 393         keyset.addAll(newKeys.keySet());
 394
 395         // Construct the values
 396         @SuppressWarnings("unchecked")
 397         final V[] values = (V[])new Object[keyset.size()];
 398         int offset = 0;
 399         if (removed != 0) {
 400             if (removed != offsets.size()) {
 401                 for (Entry<K, Integer> e : offsets.entrySet()) {
 402                     final Object o = objects[e.getValue()];
 403                     if (o != null && !REMOVED.equals(o)) {
 404                         @SuppressWarnings("unchecked")
 405                         final V v = (V) o;
 406                         values[offset++] = v;
 407                     }
 408                 }
 409             }
 410         } else {
 411             System.arraycopy(objects, 0, values, 0, offsets.size());
 412             offset = offsets.size();
 413         }
 414         for (V v : newKeys.values()) {
 415             values[offset++] = v;
 416         }
 417
 418         return modifiedMap(keyset, values);
 419     }
 420
 421     @SuppressWarnings("unchecked")
 422     @Override
 423     public MutableOffsetMap<K, V> clone() {
 424         final MutableOffsetMap<K, V> ret;
 425
 426         try {
 427             ret = (MutableOffsetMap<K, V>) super.clone();
 428         } catch (CloneNotSupportedException e) {
 429             throw new IllegalStateException("Clone is expected to work", e);
 430         }
 431
 432         ret.newKeys = (HashMap<K, V>) newKeys.clone();
 433         ret.needClone = true;
 434         return ret;
 435     }
 436
 437     @Override
 438     public final int hashCode() {
 439         int result = 0;
 440
 441         for (Entry<K, Integer> e : offsets.entrySet()) {
 442             final Object v = objects[e.getValue()];
 443             if (v != null) {
 444                 result += e.getKey().hashCode() ^ v.hashCode();
 445             }
 446         }
 447
 448         return result + newKeys.hashCode();
 449     }
 450
 451     @Override
 452     public final boolean equals(final Object obj) {
 453         if (obj == this) {
 454             return true;
 455         }
 456         if (!(obj instanceof Map)) {
 457             return false;
 458         }
 459
 460         if (obj instanceof ImmutableOffsetMap) {
 461             final ImmutableOffsetMap<?, ?> om = (ImmutableOffsetMap<?, ?>) obj;
 462
 463             if (newKeys.isEmpty() && offsets.equals(om.offsets())) {
 464                 return Arrays.deepEquals(objects, om.objects());
 465             }
 466         } else if (obj instanceof MutableOffsetMap) {
 467             final MutableOffsetMap<?, ?> om = (MutableOffsetMap<?, ?>) obj;
 468
 469             if (offsets.equals(om.offsets)) {
 470                 return Arrays.deepEquals(objects, om.objects) && newKeys.equals(om.newKeys);
 471             }
 472         }
 473
 474         // Fall back to brute map compare
 475         final Map<?, ?> other = (Map<?, ?>)obj;
 476
 477         // Size and key sets have to match
 478         if (size() != other.size() || !keySet().equals(other.keySet())) {
 479             return false;
 480         }
 481
 482         try {
 483             // Ensure all newKeys are present. Note newKeys is guaranteed to
 484             // not contain null value.
 485             for (Entry<K, V> e : newKeys.entrySet()) {
 486                 if (!e.getValue().equals(other.get(e.getKey()))) {
 487                     return false;
 488                 }
 489             }
 490
 491             // Ensure all objects are present
 492             for (Entry<K, Integer> e : offsets.entrySet()) {
 493                 final Object val = objects[e.getValue()];
 494                 if (val != null && !REMOVED.equals(val) && !val.equals(other.get(e.getKey()))) {
 495                     return false;
 496                 }
 497             }
 498         } catch (ClassCastException e) {
 499             // Can be thrown by other.get() and indicate we have incompatible key types
 500             return false;
 501         }
 502
 503         return true;
 504     }
 505
 506     @Override
 507     public final @NonNull Set<K> keySet() {
 508         return new KeySet();
 509     }
 510
 511     @VisibleForTesting
 512     final boolean needClone() {
 513         return needClone;
 514     }
 515
 516     @VisibleForTesting
 517     final Object array() {
 518         return objects;
 519     }
 520
 521     @VisibleForTesting
 522     final Object newKeys() {
 523         return newKeys;
 524     }
 525
 526     private final class EntrySet extends AbstractSet<Entry<K, V>> {
 527         @Override
 528         public @NonNull Iterator<Entry<K, V>> iterator() {
 529             return new AbstractSetIterator<Entry<K, V>>() {
 530                 @Override
 531                 public Entry<K, V> next() {
 532                     final K key = nextKey();
 533                     return new SimpleEntry<>(key, get(key));
 534                 }
 535             };
 536         }
 537
 538         @Override
 539         public int size() {
 540             return MutableOffsetMap.this.size();
 541         }
 542
 543         @Override
 544         @SuppressWarnings("checkstyle:parameterName")
 545         public boolean contains(final Object o) {
 546             if (!(o instanceof Entry)) {
 547                 return false;
 548             }
 549
 550             @SuppressWarnings("unchecked")
 551             final Entry<K,V> e = (Entry<K,V>) o;
 552             if (e.getValue() == null) {
 553                 return false;
 554             }
 555
 556             return e.getValue().equals(MutableOffsetMap.this.get(e.getKey()));
 557         }
 558
 559         @Override
 560         @SuppressWarnings("checkstyle:parameterName")
 561         public boolean add(final Entry<K, V> e) {
 562             final V v = requireNonNull(e.getValue());
 563             final V p = MutableOffsetMap.this.put(e.getKey(), v);
 564             return !v.equals(p);
 565         }
 566
 567         @Override
 568         @SuppressWarnings("checkstyle:parameterName")
 569         public boolean remove(final Object o) {
 570             if (!(o instanceof Entry)) {
 571                 return false;
 572             }
 573
 574             @SuppressWarnings("unchecked")
 575             final Entry<K,V> e = (Entry<K,V>) o;
 576             if (e.getValue() == null) {
 577                 return false;
 578             }
 579
 580             final V v = MutableOffsetMap.this.get(e.getKey());
 581             if (e.getValue().equals(v)) {
 582                 MutableOffsetMap.this.remove(e.getKey());
 583                 return true;
 584             }
 585             return false;
 586         }
 587
 588         @Override
 589         public void clear() {
 590             MutableOffsetMap.this.clear();
 591         }
 592     }
 593
 594     private final class KeySet extends AbstractSet<K> {
 595         @Override
 596         public @NonNull Iterator<K> iterator() {
 597             return new AbstractSetIterator<K>() {
 598                 @Override
 599                 public K next() {
 600                     return nextKey();
 601                 }
 602             };
 603         }
 604
 605         @Override
 606         public int size() {
 607             return MutableOffsetMap.this.size();
 608         }
 609     }
 610
 611     private abstract class AbstractSetIterator<E> implements Iterator<E> {
 612         private final Iterator<Entry<K, Integer>> oldIterator = offsets.entrySet().iterator();
 613         private final Iterator<K> newIterator = newKeys.keySet().iterator();
 614         private int expectedModCount = modCount;
 615         private @Nullable K currentKey = null;
 616         private @Nullable K nextKey;
 617
 618         AbstractSetIterator() {
 619             updateNextKey();
 620         }
 621
 622         private void updateNextKey() {
 623             while (oldIterator.hasNext()) {
 624                 final Entry<K, Integer> e = oldIterator.next();
 625                 final Object obj = objects[e.getValue()];
 626                 if (obj != null && !REMOVED.equals(obj)) {
 627                     nextKey = e.getKey();
 628                     return;
 629                 }
 630             }
 631
 632             nextKey = newIterator.hasNext() ? newIterator.next() : null;
 633         }
 634
 635         private void checkModCount() {
 636             if (modCount != expectedModCount) {
 637                 throw new ConcurrentModificationException();
 638             }
 639         }
 640
 641         @Override
 642         public final boolean hasNext() {
 643             checkModCount();
 644             return nextKey != null;
 645         }
 646
 647         @Override
 648         public final void remove() {
 649             checkModCount();
 650             checkState(currentKey != null);
 651             final Integer offset = offsets.get(currentKey);
 652             if (offset != null) {
 653                 cloneArray();
 654                 objects[offset] = removedObject();
 655                 removed++;
 656             } else {
 657                 newIterator.remove();
 658             }
 659
 660             expectedModCount = ++modCount;
 661             currentKey = null;
 662         }
 663
 664         protected final K nextKey() {
 665             if (nextKey == null) {
 666                 throw new NoSuchElementException();
 667             }
 668
 669             checkModCount();
 670             currentKey = nextKey;
 671             updateNextKey();
 672
 673             return currentKey;
 674         }
 675     }
 676 }