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