third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/INode.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 org.opendaylight.yangtools.triemap.LookupResult.RESTART;
  19 import static org.opendaylight.yangtools.triemap.PresencePredicate.ABSENT;
  20 import static org.opendaylight.yangtools.triemap.PresencePredicate.PRESENT;
  21
  22 import java.util.Optional;
  23 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
  24
  25 final class INode<K, V> extends BasicNode {
  26     @SuppressWarnings("rawtypes")
  27     private static final AtomicReferenceFieldUpdater<INode, MainNode> MAINNODE_UPDATER =
  28             AtomicReferenceFieldUpdater.newUpdater(INode.class, MainNode.class, "mainnode");
  29
  30     private final Gen gen;
  31
  32     private volatile MainNode<K, V> mainnode;
  33
  34     INode(final Gen gen, final MainNode<K, V> mainnode) {
  35         this.gen = gen;
  36         this.mainnode = mainnode;
  37     }
  38
  39     MainNode<K, V> gcasRead(final TrieMap<?, ?> ct) {
  40         return GCAS_READ(ct);
  41     }
  42
  43     private MainNode<K, V> GCAS_READ(final TrieMap<?, ?> ct) {
  44         MainNode<K, V> m = /* READ */ mainnode;
  45         MainNode<K, V> prevval = /* READ */ m.READ_PREV();
  46         if (prevval == null) {
  47             return m;
  48         }
  49
  50         return GCAS_Complete(m, ct);
  51     }
  52
  53     private MainNode<K, V> GCAS_Complete(MainNode<K, V> m, final TrieMap<?, ?> ct) {
  54         while (true) {
  55             if (m == null) {
  56                 return null;
  57             }
  58
  59             // complete the GCAS
  60             final MainNode<K, V> prev = /* READ */ m.READ_PREV();
  61             final Gen rdgen = ct.readRoot(true).gen;
  62             if (prev == null) {
  63                 return m;
  64             }
  65
  66             if (prev instanceof FailedNode) {
  67                 // try to commit to previous value
  68                 FailedNode<K, V> fn = (FailedNode<K, V>) prev;
  69                 if (MAINNODE_UPDATER.compareAndSet(this, m, fn.READ_PREV())) {
  70                     return fn.READ_PREV();
  71                 }
  72
  73                 // Tail recursion: return GCAS_Complete (/* READ */ mainnode, ct);
  74                 m = /* READ */ mainnode;
  75                 continue;
  76             }
  77
  78             // Assume that you've read the root from the generation G.
  79             // Assume that the snapshot algorithm is correct.
  80             // ==> you can only reach nodes in generations <= G.
  81             // ==> `gen` is <= G.
  82             // We know that `ctr.gen` is >= G.
  83             // ==> if `ctr.gen` = `gen` then they are both equal to G.
  84             // ==> otherwise, we know that either `ctr.gen` > G, `gen` < G,
  85             // or both
  86             if (rdgen == gen && !ct.isReadOnly()) {
  87                 // try to commit
  88                 if (m.CAS_PREV(prev, null)) {
  89                     return m;
  90                 }
  91
  92                 // Tail recursion: return GCAS_Complete (m, ct);
  93                 continue;
  94             }
  95
  96             // try to abort
  97             m.CAS_PREV(prev, new FailedNode<>(prev));
  98
  99             // Tail recursion: return GCAS_Complete(/* READ */ mainnode, ct);
 100             m = /* READ */ mainnode;
 101         }
 102     }
 103
 104     private boolean GCAS(final MainNode<K, V> old, final MainNode<K, V> n, final TrieMap<?, ?> ct) {
 105         n.WRITE_PREV(old);
 106         if (MAINNODE_UPDATER.compareAndSet(this, old, n)) {
 107             GCAS_Complete(n, ct);
 108             return /* READ */ n.READ_PREV() == null;
 109         }
 110
 111         return false;
 112     }
 113
 114     private INode<K, V> inode(final MainNode<K, V> cn) {
 115         return new INode<>(gen, cn);
 116     }
 117
 118     INode<K, V> copyToGen(final Gen ngen, final TrieMap<?, ?> ct) {
 119         return new INode<>(ngen, GCAS_READ(ct));
 120     }
 121
 122     /**
 123      * Inserts a key value pair, overwriting the old pair if the keys match.
 124      *
 125      * @return true if successful, false otherwise
 126      */
 127     boolean rec_insert(final K k, final V v, final int hc, final int lev, final INode<K, V> parent,
 128             final TrieMap<K, V> ct) {
 129         return rec_insert(k, v, hc, lev, parent, gen, ct);
 130     }
 131
 132     private boolean rec_insert(final K k, final V v, final int hc, final int lev, final INode<K, V> parent,
 133             final Gen startgen, final TrieMap<K, V> ct) {
 134         while (true) {
 135             final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
 136
 137             if (m instanceof CNode) {
 138                 // 1) a multiway node
 139                 final CNode<K, V> cn = (CNode<K, V>) m;
 140                 final int idx = (hc >>> lev) & 0x1f;
 141                 final int flag = 1 << idx;
 142                 final int bmp = cn.bitmap;
 143                 final int mask = flag - 1;
 144                 final int pos = Integer.bitCount(bmp & mask);
 145
 146                 if ((bmp & flag) != 0) {
 147                     // 1a) insert below
 148                     final BasicNode cnAtPos = cn.array[pos];
 149                     if (cnAtPos instanceof INode) {
 150                         final INode<K, V> in = (INode<K, V>) cnAtPos;
 151                         if (startgen == in.gen) {
 152                             return in.rec_insert(k, v, hc, lev + 5, this, startgen, ct);
 153                         }
 154                         if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
 155                             // Tail recursion: return rec_insert (k, v, hc, lev, parent, startgen, ct);
 156                             continue;
 157                         }
 158
 159                         return false;
 160                     } else if (cnAtPos instanceof SNode) {
 161                         final SNode<K, V> sn = (SNode<K, V>) cnAtPos;
 162                         if (sn.hc == hc && ct.equal(sn.k, k)) {
 163                             return GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct);
 164                         }
 165
 166                         final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
 167                         final MainNode<K, V> nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode<>(k, v, hc),
 168                                 hc, lev + 5, gen)), gen);
 169                         return GCAS (cn, nn, ct);
 170                     }
 171                 } else {
 172                     final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
 173                     final MainNode<K, V> ncnode = rn.insertedAt(pos, flag, new SNode<>(k, v, hc), gen);
 174                     return GCAS (cn, ncnode, ct);
 175                 }
 176             } else if (m instanceof TNode) {
 177                 clean(parent, ct, lev - 5);
 178                 return false;
 179             } else if (m instanceof LNode) {
 180                 final LNode<K, V> ln = (LNode<K, V>) m;
 181                 final LNodeEntry<K, V> entry = ln.get(ct.equiv(), k);
 182                 return entry != null ? replaceln(ln, entry, v, ct) : insertln(ln, k, v, ct);
 183             } else {
 184                 throw new IllegalStateException("Unhandled node " + m);
 185             }
 186
 187             throw new RuntimeException ("Should not happen");
 188         }
 189     }
 190
 191     /**
 192      * Inserts a new key value pair, given that a specific condition is met.
 193      *
 194      * @param cond
 195      *            null - don't care if the key was there
 196      *            KEY_ABSENT - key wasn't there
 197      *            KEY_PRESENT - key was there
 198      *            other value `v` - key must be bound to `v`
 199      * @return null if unsuccessful, Option[V] otherwise (indicating
 200      *         previous value bound to the key)
 201      */
 202     Optional<V> rec_insertif(final K k, final V v, final int hc, final Object cond, final int lev,
 203             final INode<K, V> parent, final TrieMap<K, V> ct) {
 204         return rec_insertif(k, v, hc, cond, lev, parent, gen, ct);
 205     }
 206
 207     private Optional<V> insertDual(final TrieMap<K, V> ct, final CNode<K, V> cn, final int pos, final SNode<K, V> sn,
 208             final K k, final V v, final int hc, final int lev) {
 209         final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
 210         final MainNode<K, V> nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode<>(k, v, hc),
 211             hc, lev + 5, gen)), gen);
 212         return GCAS(cn, nn, ct) ? Optional.empty() : null;
 213     }
 214
 215     private Optional<V> rec_insertif(final K k, final V v, final int hc, final Object cond, final int lev,
 216             final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
 217         while (true) {
 218             final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
 219
 220             if (m instanceof CNode) {
 221                 // 1) a multiway node
 222                 final CNode<K, V> cn = (CNode<K, V>) m;
 223                 final int idx = (hc >>> lev) & 0x1f;
 224                 final int flag = 1 << idx;
 225                 final int bmp = cn.bitmap;
 226                 final int mask = flag - 1;
 227                 final int pos = Integer.bitCount(bmp & mask);
 228
 229                 if ((bmp & flag) != 0) {
 230                     // 1a) insert below
 231                     final BasicNode cnAtPos = cn.array[pos];
 232                     if (cnAtPos instanceof INode) {
 233                         final INode<K, V> in = (INode<K, V>) cnAtPos;
 234                         if (startgen == in.gen) {
 235                             return in.rec_insertif(k, v, hc, cond, lev + 5, this, startgen, ct);
 236                         }
 237
 238                         if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
 239                             // Tail recursion: return rec_insertif (k, v, hc, cond, lev, parent, startgen, ct);
 240                             continue;
 241                         }
 242
 243                         return null;
 244                     } else if (cnAtPos instanceof SNode) {
 245                         final SNode<K, V> sn = (SNode<K, V>) cnAtPos;
 246                         if (cond == null) {
 247                             if (sn.hc == hc && ct.equal(sn.k, k)) {
 248                                 if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
 249                                     return Optional.of(sn.v);
 250                                 }
 251
 252                                 return null;
 253                             }
 254
 255                             return insertDual(ct, cn, pos, sn, k, v, hc, lev);
 256                         } else if (cond == ABSENT) {
 257                             if (sn.hc == hc && ct.equal(sn.k, k)) {
 258                                 return Optional.of(sn.v);
 259                             }
 260
 261                             return insertDual(ct, cn, pos, sn, k, v, hc, lev);
 262                         } else if (cond == PRESENT) {
 263                             if (sn.hc == hc && ct.equal(sn.k, k)) {
 264                                 if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
 265                                     return Optional.of(sn.v);
 266                                 }
 267                                 return null;
 268                             }
 269
 270                             return Optional.empty();
 271                         } else {
 272                             if (sn.hc == hc && ct.equal(sn.k, k) && cond.equals(sn.v)) {
 273                                 if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
 274                                     return Optional.of(sn.v);
 275                                 }
 276
 277                                 return null;
 278                             }
 279
 280                             return Optional.empty();
 281                         }
 282                     }
 283                 } else if (cond == null || cond == ABSENT) {
 284                     final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
 285                     final CNode<K, V> ncnode = rn.insertedAt (pos, flag, new SNode<>(k, v, hc), gen);
 286                     if (GCAS(cn, ncnode, ct)) {
 287                         return Optional.empty();
 288                     }
 289
 290                     return null;
 291                 } else {
 292                     return Optional.empty();
 293                 }
 294             } else if (m instanceof TNode) {
 295                 clean(parent, ct, lev - 5);
 296                 return null;
 297             } else if (m instanceof LNode) {
 298                 // 3) an l-node
 299                 final LNode<K, V> ln = (LNode<K, V>) m;
 300                 final LNodeEntry<K, V> entry = ln.get(ct.equiv(), k);
 301
 302                 if (cond == null) {
 303                     if (entry != null) {
 304                         return replaceln(ln, entry, v, ct) ? Optional.of(entry.value()) : null;
 305                     }
 306
 307                     return insertln(ln, k, v, ct) ? Optional.empty() : null;
 308                 } else if (cond == ABSENT) {
 309                     if (entry != null) {
 310                         return Optional.of(entry.value());
 311                     }
 312
 313                     return insertln(ln, k, v, ct) ? Optional.empty() : null;
 314                 } else if (cond == PRESENT) {
 315                     if (entry == null) {
 316                         return Optional.empty();
 317                     }
 318
 319                     return replaceln(ln, entry, v, ct) ? Optional.of(entry.value()) : null;
 320                 } else {
 321                     if (entry == null || !cond.equals(entry.value())) {
 322                         return Optional.empty();
 323                     }
 324
 325                     return replaceln(ln, entry, v, ct) ? Optional.of(entry.value()) : null;
 326                 }
 327             } else {
 328                 throw new IllegalStateException("Unhandled node " + m);
 329             }
 330
 331             throw new RuntimeException("Should never happen");
 332         }
 333     }
 334
 335     private boolean insertln(final LNode<K, V> ln, final K k, final V v, final TrieMap<K, V> ct) {
 336         return GCAS(ln, ln.insertChild(k, v), ct);
 337     }
 338
 339     private boolean replaceln(final LNode<K, V> ln, final LNodeEntry<K, V> entry, final V v, final TrieMap<K, V> ct) {
 340         return GCAS(ln, ln.replaceChild(entry, v), ct);
 341     }
 342
 343     /**
 344      * Looks up the value associated with the key.
 345      *
 346      * @return null if no value has been found, RESTART if the operation
 347      *         wasn't successful, or any other value otherwise
 348      */
 349     Object rec_lookup(final K k, final int hc, final int lev, final INode<K, V> parent, final TrieMap<K, V> ct) {
 350         return rec_lookup(k, hc, lev, parent, gen, ct);
 351     }
 352
 353     private Object rec_lookup(final K k, final int hc, final int lev, final INode<K, V> parent, final Gen startgen,
 354             final TrieMap<K, V> ct) {
 355         while (true) {
 356             final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
 357
 358             if (m instanceof CNode) {
 359                 // 1) a multinode
 360                 final CNode<K, V> cn = (CNode<K, V>) m;
 361                 final int idx = (hc >>> lev) & 0x1f;
 362                 final int flag = 1 << idx;
 363                 final int bmp = cn.bitmap;
 364
 365                 if ((bmp & flag) == 0) {
 366                     // 1a) bitmap shows no binding
 367                     return null;
 368                 }
 369
 370                 // 1b) bitmap contains a value - descend
 371                 final int pos = (bmp == 0xffffffff) ? idx : Integer.bitCount(bmp & (flag - 1));
 372                 final BasicNode sub = cn.array[pos];
 373                 if (sub instanceof INode) {
 374                     final INode<K, V> in = (INode<K, V>) sub;
 375                     if (ct.isReadOnly() || (startgen == in.gen)) {
 376                         return in.rec_lookup(k, hc, lev + 5, this, startgen, ct);
 377                     }
 378
 379                     if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
 380                         // Tail recursion: return rec_lookup(k, hc, lev, parent, startgen, ct);
 381                         continue;
 382                     }
 383
 384                     return RESTART;
 385                 } else if (sub instanceof SNode) {
 386                     // 2) singleton node
 387                     final SNode<K, V> sn = (SNode<K, V>) sub;
 388                     if (sn.hc == hc && ct.equal(sn.k, k)) {
 389                         return sn.v;
 390                     }
 391
 392                     return null;
 393                 }
 394             } else if (m instanceof TNode) {
 395                 // 3) non-live node
 396                 return cleanReadOnly((TNode<K, V>) m, lev, parent, ct, k, hc);
 397             } else if (m instanceof LNode) {
 398                 // 5) an l-node
 399                 final LNodeEntry<K, V> entry = ((LNode<K, V>) m).get(ct.equiv(), k);
 400                 return entry != null ? entry.value() : null;
 401             } else {
 402                 throw new IllegalStateException("Unhandled node " + m);
 403             }
 404
 405             throw new RuntimeException ("Should not happen");
 406         }
 407     }
 408
 409     private Object cleanReadOnly(final TNode<K, V> tn, final int lev, final INode<K, V> parent,
 410             final TrieMap<K, V> ct, final K k, final int hc) {
 411         if (ct.isReadOnly()) {
 412             if (tn.hc == hc && ct.equal(tn.k, k)) {
 413                 return tn.v;
 414             }
 415
 416             return null;
 417         }
 418
 419         clean(parent, ct, lev - 5);
 420         return RESTART;
 421     }
 422
 423     /**
 424      * Removes the key associated with the given value.
 425      *
 426      * @param cond
 427      *            if null, will remove the key regardless of the value;
 428      *            otherwise removes only if binding contains that exact key
 429      *            and value
 430      * @return null if not successful, an Optional indicating the previous
 431      *         value otherwise
 432      */
 433     Optional<V> rec_remove(final K k, final Object cond, final int hc, final int lev, final INode<K, V> parent,
 434             final TrieMap<K, V> ct) {
 435         return rec_remove(k, cond, hc, lev, parent, gen, ct);
 436     }
 437
 438     private Optional<V> rec_remove(final K k, final Object cond, final int hc, final int lev, final INode<K, V> parent,
 439             final Gen startgen, final TrieMap<K, V> ct) {
 440         final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
 441
 442         if (m instanceof CNode) {
 443             final CNode<K, V> cn = (CNode<K, V>) m;
 444             final int idx = (hc >>> lev) & 0x1f;
 445             final int bmp = cn.bitmap;
 446             final int flag = 1 << idx;
 447             if ((bmp & flag) == 0) {
 448                 return Optional.empty();
 449             }
 450
 451             final int pos = Integer.bitCount(bmp & (flag - 1));
 452             final BasicNode sub = cn.array[pos];
 453             Optional<V> res = null;
 454             if (sub instanceof INode) {
 455                 final INode<K, V> in = (INode<K, V>) sub;
 456                 if (startgen == in.gen) {
 457                     res = in.rec_remove(k, cond, hc, lev + 5, this, startgen, ct);
 458                 } else {
 459                     if (GCAS(cn, cn.renewed (startgen, ct), ct)) {
 460                         res = rec_remove(k, cond, hc, lev, parent, startgen, ct);
 461                     } else {
 462                         res = null;
 463                     }
 464                 }
 465
 466             } else if (sub instanceof SNode) {
 467                 final SNode<K, V> sn = (SNode<K, V>) sub;
 468                 if (sn.hc == hc && ct.equal(sn.k, k) && (cond == null || cond.equals(sn.v))) {
 469                     final MainNode<K, V> ncn = cn.removedAt(pos, flag, gen).toContracted(lev);
 470                     if (GCAS(cn, ncn, ct)) {
 471                         res = Optional.of(sn.v);
 472                     } else {
 473                         res = null;
 474                     }
 475                 } else {
 476                     res = Optional.empty();
 477                 }
 478             }
 479
 480             if (res == null || !res.isPresent()) {
 481                 return res;
 482             }
 483
 484             if (parent != null) {
 485                 // never tomb at root
 486                 final MainNode<K, V> n = GCAS_READ(ct);
 487                 if (n instanceof TNode) {
 488                     cleanParent(n, parent, ct, hc, lev, startgen);
 489                 }
 490             }
 491
 492             return res;
 493         } else if (m instanceof TNode) {
 494             clean(parent, ct, lev - 5);
 495             return null;
 496         } else if (m instanceof LNode) {
 497             final LNode<K, V> ln = (LNode<K, V>) m;
 498             final LNodeEntry<K, V> entry = ln.get(ct.equiv(), k);
 499             if (entry == null) {
 500                 // Key was not found, hence no modification is needed
 501                 return Optional.empty();
 502             }
 503
 504             final V value = entry.value();
 505             if (cond != null && !cond.equals(value)) {
 506                 // Value does not match
 507                 return Optional.empty();
 508             }
 509
 510             return GCAS(ln, ln.removeChild(entry, hc), ct) ? Optional.of(value) : null;
 511         } else {
 512             throw new IllegalStateException("Unhandled node " + m);
 513         }
 514     }
 515
 516     private void cleanParent(final Object nonlive, final INode<K, V> parent, final TrieMap<K, V> ct, final int hc,
 517             final int lev, final Gen startgen) {
 518         while (true) {
 519             final MainNode<K, V> pm = parent.GCAS_READ(ct);
 520             if ((!(pm instanceof CNode))) {
 521                 // parent is no longer a cnode, we're done
 522                 return;
 523             }
 524
 525             final CNode<K, V> cn = (CNode<K, V>) pm;
 526             final int idx = (hc >>> (lev - 5)) & 0x1f;
 527             final int bmp = cn.bitmap;
 528             final int flag = 1 << idx;
 529             if ((bmp & flag) == 0) {
 530                 // somebody already removed this i-node, we're done
 531                 return;
 532             }
 533
 534             final int pos = Integer.bitCount(bmp & (flag - 1));
 535             final BasicNode sub = cn.array[pos];
 536             if (sub == this) {
 537                 if (nonlive instanceof TNode) {
 538                     final TNode<?, ?> tn = (TNode<?, ?>) nonlive;
 539                     final MainNode<K, V> ncn = cn.updatedAt(pos, tn.copyUntombed(), gen).toContracted(lev - 5);
 540                     if (!parent.GCAS(cn, ncn, ct)) {
 541                         if (ct.readRoot().gen == startgen) {
 542                             // Tail recursion: cleanParent(nonlive, parent, ct, hc, lev, startgen);
 543                             continue;
 544                         }
 545                     }
 546                 }
 547             }
 548             break;
 549         }
 550     }
 551
 552     private void clean(final INode<K, V> nd, final TrieMap<K, V> ct, final int lev) {
 553         final MainNode<K, V> m = nd.GCAS_READ(ct);
 554         if (m instanceof CNode) {
 555             final CNode<K, V> cn = (CNode<K, V>) m;
 556             nd.GCAS(cn, cn.toCompressed(ct, lev, gen), ct);
 557         }
 558     }
 559
 560     int cachedSize(final TrieMap<?, ?> ct) {
 561         return GCAS_READ(ct).cachedSize(ct);
 562     }
 563
 564     // /* this is a quiescent method! */
 565     // def string(lev: Int) = "%sINode -> %s".format("  " * lev, mainnode
 566     // match {
 567     // case null => "<null>"
 568     // case tn: TNode[_, _] => "TNode(%s, %s, %d, !)".format(tn.k, tn.v,
 569     // tn.hc)
 570     // case cn: CNode[_, _] => cn.string(lev)
 571     // case ln: LNode[_, _] => ln.string(lev)
 572     // case x => "<elem: %s>".format(x)
 573     // })
 574
 575     @Override
 576     String string(final int lev) {
 577         return "INode";
 578     }
 579 }