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     MutableEntrySet<K, V> createEntrySet() {
 138         // FIXME: it would be nice to have a ReadWriteTrieMap with read-only iterator
 139         //        if (readOnlyEntrySet) return ImmutableEntrySet(this);
 140         return new MutableEntrySet<>(this);
 141     }
 142
 143     @Override
 144     MutableKeySet<K> createKeySet() {
 145         return new MutableKeySet<>(this);
 146     }
 147
 148     @Override
 149     MutableIterator<K, V> iterator() {
 150         return new MutableIterator<>(this);
 151     }
 152
 153     @Override
 154     boolean isReadOnly() {
 155         return false;
 156     }
 157
 158     @Override
 159     INode<K, V> RDCSS_READ_ROOT(final boolean abort) {
 160         final Object r = /* READ */ root;
 161         if (r instanceof INode) {
 162             return (INode<K, V>) r;
 163         }
 164
 165         checkState(r instanceof RDCSS_Descriptor, "Unhandled root %s", r);
 166         return RDCSS_Complete(abort);
 167     }
 168
 169     void add(final K key, final V value) {
 170         final K k = checkNotNull(key);
 171         inserthc(k, computeHash(k), checkNotNull(value));
 172     }
 173
 174     private static <K,V> INode<K, V> newRootNode() {
 175         final Gen gen = new Gen();
 176         return new INode<>(gen, new CNode<>(gen));
 177     }
 178
 179     private void inserthc(final K key, final int hc, final V value) {
 180         // TODO: this is called from serialization only, which means we should not be observing any races,
 181         //       hence we should not need to pass down the entire tree, just equality (I think).
 182         final boolean success = RDCSS_READ_ROOT().rec_insert(key, value, hc, 0, null, this);
 183         Verify.verify(success, "Concurrent modification during serialization of map %s", this);
 184     }
 185
 186     private Optional<V> insertifhc(final K key, final int hc, final V value, final Object cond) {
 187         Optional<V> res;
 188         do {
 189             // Keep looping as long as we do not get a reply
 190             res = RDCSS_READ_ROOT().rec_insertif(key, value, hc, cond, 0, null, this);
 191         } while (res == null);
 192
 193         return res;
 194     }
 195
 196     private Optional<V> removehc(final K key, final Object cond, final int hc) {
 197         Optional<V> res;
 198         do {
 199             // Keep looping as long as we do not get a reply
 200             res = RDCSS_READ_ROOT().rec_remove(key, cond, hc, 0, null, this);
 201         } while (res == null);
 202
 203         return res;
 204     }
 205
 206     private boolean CAS_ROOT(final Object ov, final Object nv) {
 207         return ROOT_UPDATER.compareAndSet(this, ov, nv);
 208     }
 209
 210     private boolean RDCSS_ROOT(final INode<K, V> ov, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
 211         final RDCSS_Descriptor<K, V> desc = new RDCSS_Descriptor<>(ov, expectedmain, nv);
 212         if (CAS_ROOT(ov, desc)) {
 213             RDCSS_Complete(false);
 214             return /* READ */desc.committed;
 215         }
 216
 217         return false;
 218     }
 219
 220     private INode<K, V> RDCSS_Complete(final boolean abort) {
 221         while (true) {
 222             final Object r = /* READ */ root;
 223             if (r instanceof INode) {
 224                 return (INode<K, V>) r;
 225             }
 226
 227             checkState(r instanceof RDCSS_Descriptor, "Unhandled root %s", r);
 228             @SuppressWarnings("unchecked")
 229             final RDCSS_Descriptor<K, V> desc = (RDCSS_Descriptor<K, V>) r;
 230             final INode<K, V> ov = desc.old;
 231             final MainNode<K, V> exp = desc.expectedmain;
 232             final INode<K, V> nv = desc.nv;
 233
 234             if (abort) {
 235                 if (CAS_ROOT(desc, ov)) {
 236                     return ov;
 237                 }
 238
 239                 // Tail recursion: return RDCSS_Complete(abort);
 240                 continue;
 241             }
 242
 243             final MainNode<K, V> oldmain = ov.gcasRead(this);
 244             if (oldmain == exp) {
 245                 if (CAS_ROOT(desc, nv)) {
 246                     desc.committed = true;
 247                     return nv;
 248                 }
 249
 250                 // Tail recursion: return RDCSS_Complete(abort);
 251                 continue;
 252             }
 253
 254             if (CAS_ROOT(desc, ov)) {
 255                 return ov;
 256             }
 257
 258             // Tail recursion: return RDCSS_Complete(abort);
 259         }
 260     }
 261
 262     private static final class RDCSS_Descriptor<K, V> {
 263         final INode<K, V> old;
 264         final MainNode<K, V> expectedmain;
 265         final INode<K, V> nv;
 266
 267         volatile boolean committed = false;
 268
 269         RDCSS_Descriptor(final INode<K, V> old, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
 270             this.old = old;
 271             this.expectedmain = expectedmain;
 272             this.nv = nv;
 273         }
 274     }
 275 }