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