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