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