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.checkNotNull;
  19 import static com.google.common.base.Preconditions.checkState;
  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 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 = checkNotNull(root);
  54     }
  55
  56     @Override
  57     public void clear() {
  58         boolean success;
  59         do {
  60             final INode<K, V> r = RDCSS_READ_ROOT();
  61             success = RDCSS_ROOT(r, r.gcasRead(this), newRootNode());
  62         } while (!success);
  63     }
  64
  65     @Override
  66     public V put(final K key, final V value) {
  67         final K k = checkNotNull(key);
  68         return toNullable(insertifhc(k, computeHash(k), checkNotNull(value), null));
  69     }
  70
  71     @Override
  72     public V putIfAbsent(final K key, final V value) {
  73         final K k = checkNotNull(key);
  74         return toNullable(insertifhc(k, computeHash(k), checkNotNull(value), ABSENT));
  75     }
  76
  77     @Override
  78     public V remove(final Object key) {
  79         @SuppressWarnings("unchecked")
  80         final K k = (K) checkNotNull(key);
  81         return toNullable(removehc(k, null, computeHash(k)));
  82     }
  83
  84     @SuppressFBWarnings(value = "NP_PARAMETER_MUST_BE_NONNULL_BUT_MARKED_AS_NULLABLE",
  85             justification = "API contract allows null value, but we are not")
  86     @Override
  87     public boolean remove(final Object key, final Object value) {
  88         @SuppressWarnings("unchecked")
  89         final K k = (K) checkNotNull(key);
  90         return removehc(k, checkNotNull(value), computeHash(k)).isPresent();
  91     }
  92
  93     @Override
  94     public boolean replace(final K key, final V oldValue, final V newValue) {
  95         final K k = checkNotNull(key);
  96         return insertifhc(k, computeHash(k), checkNotNull(newValue), checkNotNull(oldValue)).isPresent();
  97     }
  98
  99     @Override
 100     public V replace(final K key, final V value) {
 101         final K k = checkNotNull(key);
 102         return toNullable(insertifhc(k, computeHash(k), checkNotNull(value), PRESENT));
 103     }
 104
 105     @Override
 106     public int size() {
 107         return immutableSnapshot().size();
 108     }
 109
 110     @Override
 111     public ImmutableTrieMap<K, V> immutableSnapshot() {
 112         while (true) {
 113             final INode<K, V> r = RDCSS_READ_ROOT();
 114             final MainNode<K, V> expmain = r.gcasRead(this);
 115             if (RDCSS_ROOT(r, expmain, r.copyToGen (new Gen(), this))) {
 116                 return new ImmutableTrieMap<>(r, equiv());
 117             }
 118
 119             // Tail recursion: return readOnlySnapshot();
 120         }
 121     }
 122
 123     @Override
 124     public MutableTrieMap<K, V> mutableSnapshot() {
 125         while (true) {
 126             final INode<K, V> r = RDCSS_READ_ROOT();
 127             final MainNode<K, V> expmain = r.gcasRead(this);
 128             if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen(), this))) {
 129                 return new MutableTrieMap<>(equiv(), r.copyToGen(new Gen(), this));
 130             }
 131
 132             // Tail recursion: return snapshot();
 133         }
 134     }
 135
 136     @Override
 137     boolean isReadOnly() {
 138         return false;
 139     }
 140
 141     @Override
 142     INode<K, V> RDCSS_READ_ROOT(final boolean abort) {
 143         final Object r = /* READ */ root;
 144         if (r instanceof INode) {
 145             return (INode<K, V>) r;
 146         }
 147
 148         checkState(r instanceof RDCSS_Descriptor, "Unhandled root %s", r);
 149         return RDCSS_Complete(abort);
 150     }
 151
 152     void add(final K key, final V value) {
 153         final K k = checkNotNull(key);
 154         inserthc(k, computeHash(k), checkNotNull(value));
 155     }
 156
 157     private static <K,V> INode<K, V> newRootNode() {
 158         final Gen gen = new Gen();
 159         return new INode<>(gen, new CNode<>(gen));
 160     }
 161
 162     private void inserthc(final K k, final int hc, final V v) {
 163         // TODO: this is called from serialization only, which means we should not be observing any races,
 164         //       hence we should not need to pass down the entire tree, just equality (I think).
 165         final boolean success = RDCSS_READ_ROOT().rec_insert(k, v, hc, 0, null, this);
 166         Verify.verify(success, "Concurrent modification during serialization of map %s", this);
 167     }
 168
 169     private Optional<V> insertifhc(final K k, final int hc, final V v, final Object cond) {
 170         Optional<V> res;
 171         do {
 172             // Keep looping as long as we do not get a reply
 173             res = RDCSS_READ_ROOT().rec_insertif(k, v, hc, cond, 0, null, this);
 174         } while (res == null);
 175
 176         return res;
 177     }
 178
 179     private Optional<V> removehc(final K k, final Object cond, final int hc) {
 180         Optional<V> res;
 181         do {
 182             // Keep looping as long as we do not get a reply
 183             res = RDCSS_READ_ROOT().rec_remove(k, cond, hc, 0, null, this);
 184         } while (res == null);
 185
 186         return res;
 187     }
 188
 189     private boolean CAS_ROOT(final Object ov, final Object nv) {
 190         return ROOT_UPDATER.compareAndSet(this, ov, nv);
 191     }
 192
 193     private boolean RDCSS_ROOT(final INode<K, V> ov, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
 194         final RDCSS_Descriptor<K, V> desc = new RDCSS_Descriptor<> (ov, expectedmain, nv);
 195         if (CAS_ROOT(ov, desc)) {
 196             RDCSS_Complete(false);
 197             return /* READ */desc.committed;
 198         }
 199
 200         return false;
 201     }
 202
 203     private INode<K, V> RDCSS_Complete(final boolean abort) {
 204         while (true) {
 205             final Object r = /* READ */ root;
 206             if (r instanceof INode) {
 207                 return (INode<K, V>) r;
 208             }
 209
 210             checkState(r instanceof RDCSS_Descriptor, "Unhandled root %s", r);
 211             @SuppressWarnings("unchecked")
 212             final RDCSS_Descriptor<K, V> desc = (RDCSS_Descriptor<K, V>) r;
 213             final INode<K, V> ov = desc.old;
 214             final MainNode<K, V> exp = desc.expectedmain;
 215             final INode<K, V> nv = desc.nv;
 216
 217             if (abort) {
 218                 if (CAS_ROOT(desc, ov)) {
 219                     return ov;
 220                 }
 221
 222                 // Tail recursion: return RDCSS_Complete(abort);
 223                 continue;
 224             }
 225
 226             final MainNode<K, V> oldmain = ov.gcasRead(this);
 227             if (oldmain == exp) {
 228                 if (CAS_ROOT(desc, nv)) {
 229                     desc.committed = true;
 230                     return nv;
 231                 }
 232
 233                 // Tail recursion: return RDCSS_Complete(abort);
 234                 continue;
 235             }
 236
 237             if (CAS_ROOT(desc, ov)) {
 238                 return ov;
 239             }
 240
 241             // Tail recursion: return RDCSS_Complete(abort);
 242         }
 243     }
 244
 245     private static final class RDCSS_Descriptor<K, V> {
 246         final INode<K, V> old;
 247         final MainNode<K, V> expectedmain;
 248         final INode<K, V> nv;
 249
 250         volatile boolean committed = false;
 251
 252         RDCSS_Descriptor (final INode<K, V> old, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
 253             this.old = old;
 254             this.expectedmain = expectedmain;
 255             this.nv = nv;
 256         }
 257     }
 258 }