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