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