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