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