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