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