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 boolean equal(final K k1, final K k2, final TrieMap<K, V> ct) {
 108         return ct.equality().equiv(k1, k2);
 109     }
 110
 111     private INode<K, V> inode(final MainNode<K, V> cn) {
 112         return new INode<>(gen, cn);
 113     }
 114
 115     INode<K, V> copyToGen(final Gen ngen, final TrieMap<K, V> ct) {
 116         return new INode<>(ngen, GCAS_READ(ct));
 117     }
 118
 119     /**
 120      * Inserts a key value pair, overwriting the old pair if the keys match.
 121      *
 122      * @return true if successful, false otherwise
 123      */
 124     boolean rec_insert(final K k, final V v, final int hc, final int lev, final INode<K, V> parent, final Gen startgen,
 125             final TrieMap<K, V> ct) {
 126         while (true) {
 127             final MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
 128
 129             if (m instanceof CNode) {
 130                 // 1) a multiway node
 131                 final CNode<K, V> cn = (CNode<K, V>) m;
 132                 final int idx = (hc >>> lev) & 0x1f;
 133                 final int flag = 1 << idx;
 134                 final int bmp = cn.bitmap;
 135                 final int mask = flag - 1;
 136                 final int pos = Integer.bitCount(bmp & mask);
 137                 if ((bmp & flag) != 0) {
 138                     // 1a) insert below
 139                     final BasicNode cnAtPos = cn.array[pos];
 140                     if (cnAtPos instanceof INode) {
 141                         final INode<K, V> in = (INode<K, V>) cnAtPos;
 142                         if (startgen == in.gen) {
 143                             return in.rec_insert(k, v, hc, lev + 5, this, startgen, ct);
 144                         }
 145                         if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
 146                             // Tail recursion: return rec_insert (k, v, hc, lev, parent, startgen, ct);
 147                             continue;
 148                         }
 149
 150                         return false;
 151                     } else if (cnAtPos instanceof SNode) {
 152                         final SNode<K, V> sn = (SNode<K, V>) cnAtPos;
 153                         if (sn.hc == hc && equal(sn.k, k, ct)) {
 154                             return GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct);
 155                         }
 156
 157                         final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
 158                         final MainNode<K, V> nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode<>(k, v, hc),
 159                                 hc, lev + 5, gen)), gen);
 160                         return GCAS (cn, nn, ct);
 161                     }
 162                 } else {
 163                     CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
 164                     MainNode<K, V> ncnode = rn.insertedAt(pos, flag, new SNode<> (k, v, hc), gen);
 165                     return GCAS (cn, ncnode, ct);
 166                 }
 167             } else if (m instanceof TNode) {
 168                 clean(parent, ct, lev - 5);
 169                 return false;
 170             } else if (m instanceof LNode) {
 171                 LNode<K, V> ln = (LNode<K, V>) m;
 172                 MainNode<K, V> nn = ln.inserted(k, v);
 173                 return GCAS(ln, nn, ct);
 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     Option<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 && equal(sn.k, k, ct)) {
 224                                 if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
 225                                     return Option.makeOption(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 Option.makeOption(); // None;
 236                             }
 237
 238                             return null;
 239                         } else if (cond == INode.KEY_ABSENT) {
 240                             if (sn.hc == hc && equal(sn.k, k, ct)) {
 241                                 return Option.makeOption(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 Option.makeOption(); // None
 249                             }
 250
 251                             return null;
 252                         } else if (cond == INode.KEY_PRESENT) {
 253                             if (sn.hc == hc && equal(sn.k, k, ct)) {
 254                                 if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
 255                                     return Option.makeOption(sn.v);
 256                                 }
 257                                 return null;
 258                             }
 259
 260                             return Option.makeOption();// None;
 261                         } else {
 262                             if (sn.hc == hc && equal(sn.k, k, ct) && sn.v == cond) {
 263                                 if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
 264                                     return Option.makeOption(sn.v);
 265                                 }
 266
 267                                 return null;
 268                             }
 269
 270                             return Option.makeOption(); // None
 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 Option.makeOption(); // None
 278                     }
 279
 280                     return null;
 281                 } else if (cond == INode.KEY_PRESENT) {
 282                     return Option.makeOption(); // None;
 283                 }
 284                 else {
 285                     return Option.makeOption(); // None
 286                 }
 287             } else if (m instanceof TNode) {
 288                 clean(parent, ct, lev - 5);
 289                 return null;
 290             } else if (m instanceof LNode) {
 291                 // 3) an l-node
 292                 final LNode<K, V> ln = (LNode<K, V>) m;
 293                 if (cond == null) {
 294                     final Option<V> optv = ln.get(k);
 295                     if (insertln(ln, k, v, ct)) {
 296                         return optv;
 297                     }
 298                     return null;
 299                 } else if (cond == INode.KEY_ABSENT) {
 300                     final Option<V> t = ln.get(k);
 301                     if (t != null) {
 302                         return t;
 303                     }
 304                     if (insertln(ln, k, v, ct)) {
 305                         return Option.makeOption();// None
 306                     }
 307                     return null;
 308                 } else if (cond == INode.KEY_PRESENT) {
 309                     final Option<V> t = ln.get(k);
 310                     if (t == null) {
 311                         return null; // None
 312                     }
 313                     if (insertln(ln, k, v, ct)) {
 314                         return t;
 315                     }
 316                     return null;
 317                 } else {
 318                     final Option<V> t = ln.get(k);
 319                     if (t != null) {
 320                         if (((Some<V>) t).get() == cond) {
 321                             if (insertln(ln, k, v, ct)) {
 322                                 return new Some<>((V) cond);
 323                             }
 324
 325                             return null;
 326                         }
 327                         return Option.makeOption();
 328                     }
 329                 }
 330             }
 331
 332             //                throw new RuntimeException ("Should not happen");
 333         }
 334     }
 335
 336     boolean insertln(final LNode<K, V> ln, final K k, final V v, final TrieMap<K, V> ct) {
 337         final LNode<K, V> nn = ln.inserted (k, v);
 338         return GCAS(ln, nn, ct);
 339     }
 340
 341     /**
 342      * Looks up the value associated with the key.
 343      *
 344      * @return null if no value has been found, RESTART if the operation
 345      *         wasn't successful, or any other value otherwise
 346      */
 347     Object rec_lookup(final K k, final int hc, final int lev, final INode<K, V> parent, final Gen startgen,
 348             final TrieMap<K, V> ct) {
 349         while (true) {
 350             final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
 351
 352             if (m instanceof CNode) {
 353                 // 1) a multinode
 354                 final CNode<K, V> cn = (CNode<K, V>) m;
 355                 final int idx = (hc >>> lev) & 0x1f;
 356                 final int flag = 1 << idx;
 357                 final int bmp = cn.bitmap;
 358                 if ((bmp & flag) == 0) {
 359                     // 1a) bitmap shows no binding
 360                     return null;
 361                 }
 362
 363                 // 1b) bitmap contains a value - descend
 364                 final int pos = (bmp == 0xffffffff) ? idx : Integer.bitCount(bmp & (flag - 1));
 365                 final BasicNode sub = cn.array[pos];
 366                 if (sub instanceof INode) {
 367                     final INode<K, V> in = (INode<K, V>) sub;
 368                     if (ct.isReadOnly() || (startgen == in.gen)) {
 369                         return in.rec_lookup(k, hc, lev + 5, this, startgen, ct);
 370                     }
 371
 372                     if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
 373                         // Tail recursion: return rec_lookup(k, hc, lev, parent, startgen, ct);
 374                         continue;
 375                     }
 376
 377                     // used to be throw RestartException
 378                     return RESTART;
 379                 } else if (sub instanceof SNode) {
 380                     // 2) singleton node
 381                     final SNode<K, V> sn = (SNode<K, V>) sub;
 382                     if (sn.hc == hc && equal(sn.k, k, ct)) {
 383                         return sn.v;
 384                     }
 385
 386                     return null;
 387                 }
 388             } else if (m instanceof TNode) {
 389                 // 3) non-live node
 390                 return cleanReadOnly((TNode<K, V>) m, lev, parent, ct, k, hc);
 391             } else if (m instanceof LNode) {
 392                 // 5) an l-node
 393                 return ((LNode<K, V>) m).get(k);
 394             }
 395
 396             throw new RuntimeException ("Should not happen");
 397         }
 398     }
 399
 400     private Object cleanReadOnly(final TNode<K, V> tn, final int lev, final INode<K, V> parent,
 401             final TrieMap<K, V> ct, final K k, final int hc) {
 402         if (ct.nonReadOnly()) {
 403          // used to be throw RestartException
 404             clean(parent, ct, lev - 5);
 405             return RESTART;
 406         }
 407
 408         if (tn.hc == hc && equal(tn.k, k, ct)) {
 409             return tn.v;
 410         }
 411
 412         return null;
 413     }
 414
 415     /**
 416      * Removes the key associated with the given value.
 417      *
 418      * @param v
 419      *            if null, will remove the key regardless of the value;
 420      *            otherwise removes only if binding contains that exact key
 421      *            and value
 422      * @return null if not successful, an Option[V] indicating the previous
 423      *         value otherwise
 424      */
 425     Option<V> rec_remove(final K k, final V v, final int hc, final int lev, final INode<K, V> parent,
 426             final Gen startgen, final TrieMap<K, V> ct) {
 427         final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
 428
 429         if (m instanceof CNode) {
 430             final CNode<K, V> cn = (CNode<K, V>) m;
 431             final int idx = (hc >>> lev) & 0x1f;
 432             final int bmp = cn.bitmap;
 433             final int flag = 1 << idx;
 434             if ((bmp & flag) == 0) {
 435                 return Option.makeOption();
 436             }
 437
 438             final int pos = Integer.bitCount(bmp & (flag - 1));
 439             final BasicNode sub = cn.array[pos];
 440             Option<V> res = null;
 441             if (sub instanceof INode) {
 442                 final INode<K, V> in = (INode<K, V>) sub;
 443                 if (startgen == in.gen) {
 444                     res = in.rec_remove(k, v, hc, lev + 5, this, startgen, ct);
 445                 } else {
 446                     if (GCAS(cn, cn.renewed (startgen, ct), ct)) {
 447                         res = rec_remove(k, v, hc, lev, parent, startgen, ct);
 448                     } else {
 449                         res = null;
 450                     }
 451                 }
 452
 453             } else if (sub instanceof SNode) {
 454                 final SNode<K, V> sn = (SNode<K, V>) sub;
 455                 if (sn.hc == hc && equal(sn.k, k, ct) && (v == null || v.equals(sn.v))) {
 456                     final MainNode<K, V> ncn = cn.removedAt(pos, flag, gen).toContracted(lev);
 457                     if (GCAS(cn, ncn, ct)) {
 458                         res = Option.makeOption(sn.v);
 459                     } else {
 460                         res = null;
 461                     }
 462                 } else {
 463                     res = Option.makeOption ();
 464                 }
 465             }
 466
 467             if (res instanceof None || (res == null)) {
 468                 return res;
 469             }
 470
 471             if (parent != null) {
 472                 // never tomb at root
 473                 final MainNode<K, V> n = GCAS_READ(ct);
 474                 if (n instanceof TNode) {
 475                     cleanParent(n, parent, ct, hc, lev, startgen);
 476                 }
 477             }
 478
 479             return res;
 480         } else if (m instanceof TNode) {
 481             clean(parent, ct, lev - 5);
 482             return null;
 483         } else if (m instanceof LNode) {
 484             final LNode<K, V> ln = (LNode<K, V>) m;
 485             if (v == null) {
 486                 final Option<V> optv = ln.get(k);
 487                 final MainNode<K, V> nn = ln.removed(k, ct);
 488                 if (GCAS(ln, nn, ct)) {
 489                     return optv;
 490                 }
 491
 492                 return null;
 493             }
 494
 495             final Option<V> tmp = ln.get(k);
 496             if (tmp instanceof Some) {
 497                 final Some<V> tmp1 = (Some<V>) tmp;
 498                 if (tmp1.get() == v) {
 499                     final MainNode<K, V> nn = ln.removed(k, ct);
 500                     if (GCAS(ln, nn, ct)) {
 501                         return tmp;
 502                     }
 503
 504                     return null;
 505                 }
 506             }
 507         }
 508         throw new RuntimeException ("Should not happen");
 509     }
 510
 511     private void cleanParent(final Object nonlive, final INode<K, V> parent, final TrieMap<K, V> ct, final int hc,
 512             final int lev, final Gen startgen) {
 513         while (true) {
 514             final MainNode<K, V> pm = parent.GCAS_READ(ct);
 515             if ((!(pm instanceof CNode))) {
 516                 // parent is no longer a cnode, we're done
 517                 return;
 518             }
 519
 520             final CNode<K, V> cn = (CNode<K, V>) pm;
 521             final int idx = (hc >>> (lev - 5)) & 0x1f;
 522             final int bmp = cn.bitmap;
 523             final int flag = 1 << idx;
 524             if ((bmp & flag) == 0) {
 525                 // somebody already removed this i-node, we're done
 526                 return;
 527             }
 528
 529             final int pos = Integer.bitCount(bmp & (flag - 1));
 530             final BasicNode sub = cn.array[pos];
 531             if (sub == this) {
 532                 if (nonlive instanceof TNode) {
 533                     final TNode<K, V> tn = (TNode<K, V>) nonlive;
 534                     MainNode<K, V> ncn = cn.updatedAt(pos, tn.copyUntombed(), gen).toContracted(lev - 5);
 535                     if (!parent.GCAS(cn, ncn, ct)) {
 536                         if (ct.readRoot().gen == startgen) {
 537                             // Tail recursion: cleanParent(nonlive, parent, ct, hc, lev, startgen);
 538                             continue;
 539                         }
 540                     }
 541                 }
 542             }
 543             break;
 544         }
 545     }
 546
 547     private void clean(final INode<K, V> nd, final TrieMap<K, V> ct, final int lev) {
 548         final MainNode<K, V> m = nd.GCAS_READ(ct);
 549         if (m instanceof CNode) {
 550             final CNode<K, V> cn = (CNode<K, V>) m;
 551             nd.GCAS(cn, cn.toCompressed(ct, lev, gen), ct);
 552         }
 553     }
 554
 555     int cachedSize(final TrieMap<K, V> ct) {
 556         MainNode<K, V> m = GCAS_READ(ct);
 557         return m.cachedSize(ct);
 558     }
 559
 560     // /* this is a quiescent method! */
 561     // def string(lev: Int) = "%sINode -> %s".format("  " * lev, mainnode
 562     // match {
 563     // case null => "<null>"
 564     // case tn: TNode[_, _] => "TNode(%s, %s, %d, !)".format(tn.k, tn.v,
 565     // tn.hc)
 566     // case cn: CNode[_, _] => cn.string(lev)
 567     // case ln: LNode[_, _] => ln.string(lev)
 568     // case x => "<elem: %s>".format(x)
 569     // })
 570
 571     @Override
 572     String string(final int lev) {
 573         return "INode";
 574     }
 575 }