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