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