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