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.collect.ImmutableMap;
  14 import java.util.AbstractSet;
  15 import java.util.ArrayList;
  16 import java.util.Arrays;
  17 import java.util.Collection;
  18 import java.util.Collections;
  19 import java.util.ConcurrentModificationException;
  20 import java.util.Iterator;
  21 import java.util.LinkedHashMap;
  22 import java.util.Map;
  23 import java.util.NoSuchElementException;
  24 import java.util.Set;
  25
  26 /**
  27  * A mutable version of {@link ImmutableOffsetMap}. It inherits the set of mappings from the immutable version and
  28  * allows updating/removing existing mappings. New mappings are stored in a dedicated {@link LinkedHashMap} to preserve
  29  * insertion order. It also tracks the need to duplicate the backing array, so the sequence of
  30  * <code>
  31  * ImmutableOffsetMap&lt;K, V&gt; source;
  32  * ImmutableOffsetMap&lt;K, V&gt; result = source.createMutableClone().immutableCopy();
  33  * </code>
  34  * results in source and result sharing the backing objects.
  35  *
  36  * @param <K> the type of keys maintained by this map
  37  * @param <V> the type of mapped values
  38  */
  39 @Beta
  40 public class MutableOffsetMap<K, V> extends AbstractLazyValueMap<K, V> implements Cloneable, ModifiableMapPhase<K, V> {
  41     private static final Object[] EMPTY_ARRAY = new Object[0];
  42     private static final Object NO_VALUE = new Object();
  43     private final Map<K, Integer> offsets;
  44     private final Map<K, V> newKeys;
  45     private Object[] objects;
  46     private int removed = 0;
  47     private transient volatile int modCount;
  48     private boolean needClone = true;
  49
  50     public MutableOffsetMap() {
  51         this(Collections.<K>emptySet());
  52     }
  53
  54     public MutableOffsetMap(final Collection<K> keySet) {
  55         if (!keySet.isEmpty()) {
  56             removed = keySet.size();
  57             offsets = OffsetMapCache.offsetsFor(keySet);
  58             objects = new Object[removed];
  59             Arrays.fill(objects, NO_VALUE);
  60         } else {
  61             offsets = ImmutableMap.of();
  62             objects = EMPTY_ARRAY;
  63         }
  64
  65         this.newKeys = new LinkedHashMap<>();
  66     }
  67
  68     protected MutableOffsetMap(final ImmutableOffsetMap<K, V> m) {
  69         this.offsets = m.offsets();
  70         this.objects = m.objects();
  71         this.newKeys = new LinkedHashMap<>();
  72     }
  73
  74     protected MutableOffsetMap(final MutableOffsetMap<K, V> m) {
  75         this.offsets = m.offsets;
  76         this.objects = m.objects;
  77         this.newKeys = new LinkedHashMap<>(m.newKeys);
  78         this.removed = m.removed;
  79     }
  80
  81     @Override
  82     public final int size() {
  83         return offsets.size() + newKeys.size() - removed;
  84     }
  85
  86     @Override
  87     public final boolean isEmpty() {
  88         return size() == 0;
  89     }
  90
  91     @Override
  92     public final boolean containsKey(final Object key) {
  93         final Integer offset = offsets.get(key);
  94         if (offset == null) {
  95             return newKeys.containsKey(key);
  96         }
  97
  98         return !NO_VALUE.equals(objects[offset]);
  99     }
 100
 101     @Override
 102     public final V get(final Object key) {
 103         final Integer offset = offsets.get(key);
 104         if (offset == null) {
 105             return newKeys.get(key);
 106         }
 107
 108         final Object o = objects[offset];
 109         if (!NO_VALUE.equals(o)) {
 110             @SuppressWarnings("unchecked")
 111             final K k = (K)key;
 112             return objectToValue(k, o);
 113         } else {
 114             return null;
 115         }
 116     }
 117
 118     private void cloneArray() {
 119         if (needClone) {
 120             needClone = false;
 121             if (!EMPTY_ARRAY.equals(objects)) {
 122                 objects = objects.clone();
 123             }
 124         }
 125     }
 126
 127     @Override
 128     public final V put(final K key, final V value) {
 129         Preconditions.checkNotNull(value);
 130         final Integer offset = offsets.get(Preconditions.checkNotNull(key));
 131         if (offset == null) {
 132             final V ret = newKeys.put(key, value);
 133             if (ret == null) {
 134                 modCount++;
 135             }
 136             return ret;
 137         }
 138
 139         cloneArray();
 140         final Object ret = objects[offset];
 141         objects[offset] = valueToObject(value);
 142         if (NO_VALUE.equals(ret)) {
 143             modCount++;
 144             removed--;
 145             return null;
 146         }
 147
 148         return objectToValue(key, ret);
 149     }
 150
 151     @Override
 152     public final V remove(final Object key) {
 153         final Integer offset = offsets.get(key);
 154         if (offset == null) {
 155             final V ret = newKeys.remove(key);
 156             if (ret != null) {
 157                 modCount++;
 158             }
 159             return ret;
 160         }
 161
 162         cloneArray();
 163         final Object ret = objects[offset];
 164         objects[offset] = NO_VALUE;
 165         if (!NO_VALUE.equals(ret)) {
 166             modCount++;
 167             removed++;
 168             @SuppressWarnings("unchecked")
 169             final K k = (K)key;
 170             return objectToValue(k, ret);
 171         } else {
 172             return null;
 173         }
 174     }
 175
 176     @Override
 177     public final void clear() {
 178         if (size() != 0) {
 179             newKeys.clear();
 180             cloneArray();
 181             Arrays.fill(objects, NO_VALUE);
 182             removed = objects.length;
 183             modCount++;
 184         }
 185     }
 186
 187     @Override
 188     public final Set<Entry<K, V>> entrySet() {
 189         return new EntrySet();
 190     }
 191
 192     @Override
 193     public final Map<K, V> toUnmodifiableMap() {
 194         if (newKeys.isEmpty() && removed == 0) {
 195             // Make sure next modification clones the array, as we leak it to the map we return.
 196             needClone = true;
 197             /*
 198              * TODO: we could track the ImmutableOffsetMap from which this one was instantiated and if we do not
 199              *       perform any modifications, just return the original instance. The trade-off is increased complexity
 200              *       and an additional field in this class.
 201              */
 202             return new ImmutableOffsetMap<>(offsets, objects);
 203         }
 204
 205         final int s = size();
 206         if (s == 0) {
 207             return ImmutableMap.of();
 208         }
 209         if (s == 1) {
 210             return ImmutableMap.copyOf(this);
 211         }
 212
 213         // Construct the set of keys
 214         final Collection<K> keyset = new ArrayList<>(s);
 215         if (removed != 0) {
 216             if (removed != offsets.size()) {
 217                 for (Entry<K, Integer> e : offsets.entrySet()) {
 218                     if (!NO_VALUE.equals(objects[e.getValue()])) {
 219                         keyset.add(e.getKey());
 220                     }
 221                 }
 222             }
 223         } else {
 224             keyset.addAll(offsets.keySet());
 225         }
 226         keyset.addAll(newKeys.keySet());
 227
 228         // Construct the values
 229         final Object[] values = new Object[keyset.size()];
 230         int i = 0;
 231         if (removed != 0) {
 232             if (removed != offsets.size()) {
 233                 for (Entry<K, Integer> e : offsets.entrySet()) {
 234                     final Object o = objects[e.getValue()];
 235                     if (!NO_VALUE.equals(o)) {
 236                         values[i++] = o;
 237                     }
 238                 }
 239             }
 240         } else {
 241             System.arraycopy(objects, 0, values, 0, offsets.size());
 242             i = offsets.size();
 243         }
 244         for (V v : newKeys.values()) {
 245             values[i++] = valueToObject(v);
 246         }
 247
 248         return new ImmutableOffsetMap<>(OffsetMapCache.offsetsFor(keyset), values);
 249     }
 250
 251     @Override
 252     public MutableOffsetMap<K, V> clone() throws CloneNotSupportedException {
 253         return new MutableOffsetMap<K, V>(this);
 254     }
 255
 256     @Override
 257     public boolean equals(final Object o) {
 258         if (o == this) {
 259             return true;
 260         }
 261         if (o == null) {
 262             return false;
 263         }
 264
 265         if (o instanceof ImmutableOffsetMap) {
 266             final ImmutableOffsetMap<?, ?> om = (ImmutableOffsetMap<?, ?>) o;
 267             if (newKeys.isEmpty() && offsets == om.offsets() && Arrays.deepEquals(objects, om.objects())) {
 268                 return true;
 269             }
 270         } else if (o instanceof MutableOffsetMap) {
 271             final MutableOffsetMap<?, ?> om = (MutableOffsetMap<?, ?>) o;
 272             if (offsets == om.offsets && Arrays.deepEquals(objects, om.objects) && newKeys.equals(om.newKeys)) {
 273                 return true;
 274             }
 275         } else if (o instanceof Map) {
 276             final Map<?, ?> om = (Map<?, ?>)o;
 277
 278             // Size and key sets have to match
 279             if (size() != om.size() || !keySet().equals(om.keySet())) {
 280                 return false;
 281             }
 282
 283             try {
 284                 // Ensure all newKeys are present. Note newKeys is guaranteed to
 285                 // not contain null value.
 286                 for (Entry<K, V> e : newKeys.entrySet()) {
 287                     if (!e.getValue().equals(om.get(e.getKey()))) {
 288                         return false;
 289                     }
 290                 }
 291
 292                 // Ensure all objects are present
 293                 for (Entry<K, Integer> e : offsets.entrySet()) {
 294                     final Object obj = objects[e.getValue()];
 295                     if (!NO_VALUE.equals(obj)) {
 296                         final V v = objectToValue(e.getKey(), obj);
 297                         if (!v.equals(om.get(e.getKey()))) {
 298                             return false;
 299                         }
 300                     }
 301                 }
 302             } catch (ClassCastException e) {
 303                 // Can be thrown by om.get() and indicate we have incompatible key types
 304                 return false;
 305             }
 306
 307             return true;
 308         }
 309
 310         return false;
 311     }
 312
 313     @Override
 314     public final Set<K> keySet() {
 315         return new KeySet();
 316     }
 317
 318     @VisibleForTesting
 319     boolean needClone() {
 320         return needClone;
 321     }
 322
 323     @VisibleForTesting
 324     Object array() {
 325         return objects;
 326     }
 327
 328     @VisibleForTesting
 329     Object newKeys() {
 330         return newKeys;
 331     }
 332
 333     private final class EntrySet extends AbstractSet<Entry<K, V>> {
 334         @Override
 335         public Iterator<Entry<K, V>> iterator() {
 336             return new AbstractSetIterator<Entry<K, V>>() {
 337                 @Override
 338                 public Entry<K, V> next() {
 339                     final K key = nextKey();
 340                     return new SimpleEntry<>(key, get(key));
 341                 }
 342             };
 343         }
 344
 345         @Override
 346         public int size() {
 347             return MutableOffsetMap.this.size();
 348         }
 349
 350         @Override
 351         public boolean contains(final Object o) {
 352             if (!(o instanceof Entry)) {
 353                 return false;
 354             }
 355
 356             @SuppressWarnings("unchecked")
 357             final Entry<K,V> e = (Entry<K,V>) o;
 358             if (e.getValue() == null) {
 359                 return false;
 360             }
 361
 362             return e.getValue().equals(MutableOffsetMap.this.get(e.getKey()));
 363         }
 364
 365         @Override
 366         public boolean add(final Entry<K, V> e) {
 367             Preconditions.checkNotNull(e.getValue());
 368             final V p = MutableOffsetMap.this.put(e.getKey(), e.getValue());
 369             return !e.getValue().equals(p);
 370         }
 371
 372         @Override
 373         public boolean remove(final Object o) {
 374             if (!(o instanceof Entry)) {
 375                 return false;
 376             }
 377
 378             @SuppressWarnings("unchecked")
 379             final Entry<K,V> e = (Entry<K,V>) o;
 380             if (e.getValue() == null) {
 381                 return false;
 382             }
 383
 384             final V v = MutableOffsetMap.this.get(e.getKey());
 385             if (e.getValue().equals(v)) {
 386                 MutableOffsetMap.this.remove(e.getKey());
 387                 return true;
 388             }
 389             return false;
 390         }
 391
 392         @Override
 393         public void clear() {
 394             MutableOffsetMap.this.clear();
 395         }
 396     }
 397
 398     private final class KeySet extends AbstractSet<K> {
 399         @Override
 400         public Iterator<K> iterator() {
 401             return new AbstractSetIterator<K>() {
 402                 @Override
 403                 public K next() {
 404                     return nextKey();
 405                 }
 406             };
 407         }
 408
 409         @Override
 410         public int size() {
 411             return MutableOffsetMap.this.size();
 412         }
 413     }
 414
 415     private abstract class AbstractSetIterator<E> implements Iterator<E> {
 416         private final Iterator<Entry<K, Integer>> oldIterator = offsets.entrySet().iterator();
 417         private final Iterator<K> newIterator = newKeys.keySet().iterator();
 418         private int expectedModCount = modCount;
 419         private K currentKey, nextKey;
 420
 421         AbstractSetIterator() {
 422             updateNextKey();
 423         }
 424
 425         private void updateNextKey() {
 426             while (oldIterator.hasNext()) {
 427                 final Entry<K, Integer> e = oldIterator.next();
 428                 if (!NO_VALUE.equals(objects[e.getValue()])) {
 429                     nextKey = e.getKey();
 430                     return;
 431                 }
 432             }
 433
 434             nextKey = newIterator.hasNext() ? newIterator.next() : null;
 435         }
 436
 437         private void checkModCount() {
 438             if (modCount != expectedModCount) {
 439                 throw new ConcurrentModificationException();
 440             }
 441         }
 442
 443         @Override
 444         public final boolean hasNext() {
 445             checkModCount();
 446             return nextKey != null;
 447         }
 448
 449         @Override
 450         public final void remove() {
 451             Preconditions.checkState(currentKey != null);
 452
 453             checkModCount();
 454             final Integer offset = offsets.get(currentKey);
 455             if (offset != null) {
 456                 cloneArray();
 457                 objects[offset] = NO_VALUE;
 458                 removed++;
 459             } else {
 460                 newIterator.remove();
 461             }
 462
 463             expectedModCount = ++modCount;
 464             currentKey = null;
 465         }
 466
 467         protected final K nextKey() {
 468             if (nextKey == null) {
 469                 throw new NoSuchElementException();
 470             }
 471
 472             checkModCount();
 473             currentKey = nextKey;
 474             updateNextKey();
 475
 476             return currentKey;
 477         }
 478     }
 479 }