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