common/util/src/main/java/org/opendaylight/yangtools/util/MutableOffsetMap.java

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