third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/MutableTrieMap.java

   1 /*
   2  * (C) Copyright 2016 Pantheon Technologies, s.r.o. and others.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 package org.opendaylight.yangtools.triemap;
  17
  18 import static com.google.common.base.Preconditions.checkState;
  19 import static java.util.Objects.requireNonNull;
  20 import static org.opendaylight.yangtools.triemap.PresencePredicate.ABSENT;
  21 import static org.opendaylight.yangtools.triemap.PresencePredicate.PRESENT;
  22
  23 import com.google.common.annotations.Beta;
  24 import com.google.common.base.Verify;
  25 import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
  26 import java.util.Optional;
  27 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
  28
  29 /**
  30  * A mutable TrieMap.
  31  *
  32  * @author Robert Varga
  33  *
  34  * @param <K> the type of keys maintained by this map
  35  * @param <V> the type of mapped values
  36  */
  37 @Beta
  38 public final class MutableTrieMap<K, V> extends TrieMap<K, V> {
  39     private static final long serialVersionUID = 1L;
  40
  41     @SuppressWarnings("rawtypes")
  42     private static final AtomicReferenceFieldUpdater<MutableTrieMap, Object> ROOT_UPDATER =
  43             AtomicReferenceFieldUpdater.newUpdater(MutableTrieMap.class, Object.class, "root");
  44
  45     private volatile Object root;
  46
  47     MutableTrieMap(final Equivalence<? super K> equiv) {
  48         this(equiv, newRootNode());
  49     }
  50
  51     MutableTrieMap(final Equivalence<? super K> equiv, final INode<K, V> root) {
  52         super(equiv);
  53         this.root = requireNonNull(root);
  54     }
  55
  56     @Override
  57     public void clear() {
  58         INode<K, V> r;
  59         do {
  60             r = RDCSS_READ_ROOT();
  61         } while (!RDCSS_ROOT(r, r.gcasRead(this), newRootNode()));
  62     }
  63
  64     @Override
  65     public V put(final K key, final V value) {
  66         final K k = requireNonNull(key);
  67         return toNullable(insertifhc(k, computeHash(k), requireNonNull(value), null));
  68     }
  69
  70     @Override
  71     public V putIfAbsent(final K key, final V value) {
  72         final K k = requireNonNull(key);
  73         return toNullable(insertifhc(k, computeHash(k), requireNonNull(value), ABSENT));
  74     }
  75
  76     @Override
  77     public V remove(final Object key) {
  78         @SuppressWarnings("unchecked")
  79         final K k = (K) requireNonNull(key);
  80         return toNullable(removehc(k, null, computeHash(k)));
  81     }
  82
  83     @SuppressFBWarnings(value = "NP_PARAMETER_MUST_BE_NONNULL_BUT_MARKED_AS_NULLABLE",
  84             justification = "API contract allows null value, but we do not")
  85     @Override
  86     public boolean remove(final Object key, final Object value) {
  87         @SuppressWarnings("unchecked")
  88         final K k = (K) requireNonNull(key);
  89         return removehc(k, requireNonNull(value), computeHash(k)).isPresent();
  90     }
  91
  92     @Override
  93     public boolean replace(final K key, final V oldValue, final V newValue) {
  94         final K k = requireNonNull(key);
  95         return insertifhc(k, computeHash(k), requireNonNull(newValue), requireNonNull(oldValue)).isPresent();
  96     }
  97
  98     @Override
  99     public V replace(final K key, final V value) {
 100         final K k = requireNonNull(key);
 101         return toNullable(insertifhc(k, computeHash(k), requireNonNull(value), PRESENT));
 102     }
 103
 104     @Override
 105     public int size() {
 106         return immutableSnapshot().size();
 107     }
 108
 109     private INode<K, V> snapshot() {
 110         INode<K, V> r;
 111         do {
 112             r = RDCSS_READ_ROOT();
 113         } while (!RDCSS_ROOT(r, r.gcasRead(this), r.copyToGen(new Gen(), this)));
 114
 115         return r;
 116     }
 117
 118     @Override
 119     public ImmutableTrieMap<K, V> immutableSnapshot() {
 120         return new ImmutableTrieMap<>(snapshot(), equiv());
 121     }
 122
 123     @Override
 124     public MutableTrieMap<K, V> mutableSnapshot() {
 125         return new MutableTrieMap<>(equiv(), snapshot().copyToGen(new Gen(), this));
 126     }
 127
 128     @Override
 129     MutableEntrySet<K, V> createEntrySet() {
 130         // FIXME: it would be nice to have a ReadWriteTrieMap with read-only iterator
 131         //        if (readOnlyEntrySet) return ImmutableEntrySet(this);
 132         return new MutableEntrySet<>(this);
 133     }
 134
 135     @Override
 136     MutableKeySet<K> createKeySet() {
 137         return new MutableKeySet<>(this);
 138     }
 139
 140     @Override
 141     MutableIterator<K, V> iterator() {
 142         return new MutableIterator<>(this);
 143     }
 144
 145     @Override
 146     boolean isReadOnly() {
 147         return false;
 148     }
 149
 150     @Override
 151     @SuppressWarnings("unchecked")
 152     INode<K, V> RDCSS_READ_ROOT(final boolean abort) {
 153         final Object r = /* READ */ root;
 154         if (r instanceof INode) {
 155             return (INode<K, V>) r;
 156         }
 157
 158         checkState(r instanceof RDCSS_Descriptor, "Unhandled root %s", r);
 159         return RDCSS_Complete(abort);
 160     }
 161
 162     void add(final K key, final V value) {
 163         final K k = requireNonNull(key);
 164         inserthc(k, computeHash(k), requireNonNull(value));
 165     }
 166
 167     private static <K,V> INode<K, V> newRootNode() {
 168         final Gen gen = new Gen();
 169         return new INode<>(gen, new CNode<>(gen));
 170     }
 171
 172     private void inserthc(final K key, final int hc, final V value) {
 173         // TODO: this is called from serialization only, which means we should not be observing any races,
 174         //       hence we should not need to pass down the entire tree, just equality (I think).
 175         final boolean success = RDCSS_READ_ROOT().recInsert(key, value, hc, 0, null, this);
 176         Verify.verify(success, "Concurrent modification during serialization of map %s", this);
 177     }
 178
 179     private Optional<V> insertifhc(final K key, final int hc, final V value, final Object cond) {
 180         Optional<V> res;
 181         do {
 182             // Keep looping as long as we do not get a reply
 183             res = RDCSS_READ_ROOT().recInsertIf(key, value, hc, cond, 0, null, this);
 184         } while (res == null);
 185
 186         return res;
 187     }
 188
 189     private Optional<V> removehc(final K key, final Object cond, final int hc) {
 190         Optional<V> res;
 191         do {
 192             // Keep looping as long as we do not get a reply
 193             res = RDCSS_READ_ROOT().recRemove(key, cond, hc, 0, null, this);
 194         } while (res == null);
 195
 196         return res;
 197     }
 198
 199     private boolean CAS_ROOT(final Object ov, final Object nv) {
 200         return ROOT_UPDATER.compareAndSet(this, ov, nv);
 201     }
 202
 203     private boolean RDCSS_ROOT(final INode<K, V> ov, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
 204         final RDCSS_Descriptor<K, V> desc = new RDCSS_Descriptor<>(ov, expectedmain, nv);
 205         if (CAS_ROOT(ov, desc)) {
 206             RDCSS_Complete(false);
 207             return /* READ */desc.committed;
 208         }
 209
 210         return false;
 211     }
 212
 213     @SuppressWarnings("unchecked")
 214     private INode<K, V> RDCSS_Complete(final boolean abort) {
 215         while (true) {
 216             final Object r = /* READ */ root;
 217             if (r instanceof INode) {
 218                 return (INode<K, V>) r;
 219             }
 220
 221             checkState(r instanceof RDCSS_Descriptor, "Unhandled root %s", r);
 222             final RDCSS_Descriptor<K, V> desc = (RDCSS_Descriptor<K, V>) r;
 223             final INode<K, V> ov = desc.old;
 224             final MainNode<K, V> exp = desc.expectedmain;
 225             final INode<K, V> nv = desc.nv;
 226
 227             if (abort) {
 228                 if (CAS_ROOT(desc, ov)) {
 229                     return ov;
 230                 }
 231
 232                 // Tail recursion: return RDCSS_Complete(abort);
 233                 continue;
 234             }
 235
 236             final MainNode<K, V> oldmain = ov.gcasRead(this);
 237             if (oldmain == exp) {
 238                 if (CAS_ROOT(desc, nv)) {
 239                     desc.committed = true;
 240                     return nv;
 241                 }
 242
 243                 // Tail recursion: return RDCSS_Complete(abort);
 244                 continue;
 245             }
 246
 247             if (CAS_ROOT(desc, ov)) {
 248                 return ov;
 249             }
 250
 251             // Tail recursion: return RDCSS_Complete(abort);
 252         }
 253     }
 254
 255     private static final class RDCSS_Descriptor<K, V> {
 256         final INode<K, V> old;
 257         final MainNode<K, V> expectedmain;
 258         final INode<K, V> nv;
 259
 260         volatile boolean committed = false;
 261
 262         RDCSS_Descriptor(final INode<K, V> old, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
 263             this.old = old;
 264             this.expectedmain = expectedmain;
 265             this.nv = nv;
 266         }
 267     }
 268 }