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(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     @VisibleForTesting
 257     boolean needClone() {
 258         return needClone;
 259     }
 260
 261     @VisibleForTesting
 262     Object array() {
 263         return objects;
 264     }
 265
 266     @VisibleForTesting
 267     Object newKeys() {
 268         return newKeys;
 269     }
 270
 271     private final class EntrySet extends AbstractSet<Entry<K, V>> {
 272         @Override
 273         public Iterator<Entry<K, V>> iterator() {
 274             return new EntrySetIterator();
 275         }
 276
 277         @Override
 278         public int size() {
 279             return MutableOffsetMap.this.size();
 280         }
 281
 282         @Override
 283         public boolean contains(final Object o) {
 284             if (!(o instanceof Entry)) {
 285                 return false;
 286             }
 287
 288             @SuppressWarnings("unchecked")
 289             final Entry<K,V> e = (Entry<K,V>) o;
 290             if (e.getValue() == null) {
 291                 return false;
 292             }
 293
 294             return e.getValue().equals(MutableOffsetMap.this.get(e.getKey()));
 295         }
 296
 297         @Override
 298         public boolean add(final Entry<K, V> e) {
 299             Preconditions.checkNotNull(e.getValue());
 300             final V p = MutableOffsetMap.this.put(e.getKey(), e.getValue());
 301             return !e.getValue().equals(p);
 302         }
 303
 304         @Override
 305         public boolean remove(final Object o) {
 306             if (!(o instanceof Entry)) {
 307                 return false;
 308             }
 309
 310             @SuppressWarnings("unchecked")
 311             final Entry<K,V> e = (Entry<K,V>) o;
 312             if (e.getValue() == null) {
 313                 return false;
 314             }
 315
 316             final V v = MutableOffsetMap.this.get(e.getKey());
 317             if (e.getValue().equals(v)) {
 318                 MutableOffsetMap.this.remove(e.getKey());
 319                 return true;
 320             }
 321             return false;
 322         }
 323
 324         @Override
 325         public void clear() {
 326             MutableOffsetMap.this.clear();
 327         }
 328     }
 329
 330     private final class EntrySetIterator implements Iterator<Entry<K, V>> {
 331         private final Iterator<Entry<K, Integer>> oldIterator = offsets.entrySet().iterator();
 332         private final Iterator<Entry<K, V>> newIterator = newKeys.entrySet().iterator();
 333         private int expectedModCount = modCount;
 334         private K currentKey, nextKey;
 335
 336         EntrySetIterator() {
 337             calculateNextKey();
 338         }
 339
 340         private void calculateNextKey() {
 341             while (oldIterator.hasNext()) {
 342                 final Entry<K, Integer> e = oldIterator.next();
 343                 if (!NO_VALUE.equals(objects[e.getValue()])) {
 344                     nextKey = e.getKey();
 345                     return;
 346                 }
 347             }
 348
 349             nextKey = newIterator.hasNext() ? newIterator.next().getKey() : null;
 350         }
 351
 352         private void checkModCount() {
 353             if (modCount != expectedModCount) {
 354                 throw new ConcurrentModificationException();
 355             }
 356         }
 357
 358         @Override
 359         public boolean hasNext() {
 360             checkModCount();
 361             return nextKey != null;
 362         }
 363
 364         @Override
 365         public Entry<K, V> next() {
 366             if (nextKey == null) {
 367                 throw new NoSuchElementException();
 368             }
 369
 370             checkModCount();
 371             currentKey = nextKey;
 372             calculateNextKey();
 373
 374             return new SimpleEntry<>(currentKey, get(currentKey));
 375         }
 376
 377         @Override
 378         public void remove() {
 379             Preconditions.checkState(currentKey != null);
 380
 381             checkModCount();
 382             final Integer offset = offsets.get(currentKey);
 383             if (offset != null) {
 384                 cloneArray();
 385                 objects[offset] = NO_VALUE;
 386                 removed++;
 387             } else {
 388                 newIterator.remove();
 389             }
 390
 391             expectedModCount = ++modCount;
 392             currentKey = null;
 393         }
 394     }
 395 }