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