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