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