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             }
 171
 172             throw new RuntimeException ("Should not happen");
 173         }
 174     }
 175
 176     /**
 177      * Inserts a new key value pair, given that a specific condition is met.
 178      *
 179      * @param cond
 180      *            null - don't care if the key was there
 181      *            KEY_ABSENT - key wasn't there
 182      *            KEY_PRESENT - key was there
 183      *            other value `v` - key must be bound to `v`
 184      * @return null if unsuccessful, Option[V] otherwise (indicating
 185      *         previous value bound to the key)
 186      */
 187     Option<V> rec_insertif(final K k, final V v, final int hc, final Object cond, final int lev,
 188             final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
 189         while (true) {
 190             final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
 191
 192             if (m instanceof CNode) {
 193                 // 1) a multiway node
 194                 final CNode<K, V> cn = (CNode<K, V>) m;
 195                 final int idx = (hc >>> lev) & 0x1f;
 196                 final int flag = 1 << idx;
 197                 final int bmp = cn.bitmap;
 198                 final int mask = flag - 1;
 199                 final int pos = Integer.bitCount(bmp & mask);
 200
 201                 if ((bmp & flag) != 0) {
 202                     // 1a) insert below
 203                     final BasicNode cnAtPos = cn.array[pos];
 204                     if (cnAtPos instanceof INode) {
 205                         final INode<K, V> in = (INode<K, V>) cnAtPos;
 206                         if (startgen == in.gen) {
 207                             return in.rec_insertif(k, v, hc, cond, lev + 5, this, startgen, ct);
 208                         }
 209
 210                         if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
 211                             // Tail recursion: return rec_insertif (k, v, hc, cond, lev, parent, startgen, ct);
 212                             continue;
 213                         }
 214
 215                         return null;
 216                     } else if (cnAtPos instanceof SNode) {
 217                         final SNode<K, V> sn = (SNode<K, V>) cnAtPos;
 218                         if (cond == null) {
 219                             if (sn.hc == hc && ct.equal(sn.k, k)) {
 220                                 if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
 221                                     return Option.makeOption(sn.v);
 222                                 }
 223
 224                                 return null;
 225                             }
 226
 227                             final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
 228                             final MainNode<K, V> nn = rn.updatedAt(pos, inode (CNode.dual(sn, sn.hc,
 229                                     new SNode<>(k, v, hc), hc, lev + 5, gen)), gen);
 230                             if (GCAS(cn, nn, ct)) {
 231                                 return Option.makeOption(); // None;
 232                             }
 233
 234                             return null;
 235                         } else if (cond == INode.KEY_ABSENT) {
 236                             if (sn.hc == hc && ct.equal(sn.k, k)) {
 237                                 return Option.makeOption(sn.v);
 238                             }
 239
 240                             final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
 241                             final MainNode<K, V> nn = rn.updatedAt(pos, inode (CNode.dual(sn, sn.hc,
 242                                 new SNode<>(k, v, hc), hc, lev + 5, gen)), gen);
 243                             if (GCAS(cn, nn, ct)) {
 244                                 return Option.makeOption(); // None
 245                             }
 246
 247                             return null;
 248                         } else if (cond == INode.KEY_PRESENT) {
 249                             if (sn.hc == hc && ct.equal(sn.k, k)) {
 250                                 if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
 251                                     return Option.makeOption(sn.v);
 252                                 }
 253                                 return null;
 254                             }
 255
 256                             return Option.makeOption();// None;
 257                         } else {
 258                             if (sn.hc == hc && ct.equal(sn.k, k) && sn.v == cond) {
 259                                 if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
 260                                     return Option.makeOption(sn.v);
 261                                 }
 262
 263                                 return null;
 264                             }
 265
 266                             return Option.makeOption(); // None
 267                         }
 268                     }
 269                 } else if (cond == null || cond == INode.KEY_ABSENT) {
 270                     final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
 271                     final CNode<K, V> ncnode = rn.insertedAt (pos, flag, new SNode<>(k, v, hc), gen);
 272                     if (GCAS(cn, ncnode, ct)) {
 273                         return Option.makeOption(); // None
 274                     }
 275
 276                     return null;
 277                 } else if (cond == INode.KEY_PRESENT) {
 278                     return Option.makeOption(); // None;
 279                 }
 280                 else {
 281                     return Option.makeOption(); // None
 282                 }
 283             } else if (m instanceof TNode) {
 284                 clean(parent, ct, lev - 5);
 285                 return null;
 286             } else if (m instanceof LNode) {
 287                 // 3) an l-node
 288                 final LNode<K, V> ln = (LNode<K, V>) m;
 289                 if (cond == null) {
 290                     final Option<V> optv = ln.get(k);
 291                     if (insertln(ln, k, v, ct)) {
 292                         return optv;
 293                     }
 294                     return null;
 295                 } else if (cond == INode.KEY_ABSENT) {
 296                     final Option<V> t = ln.get(k);
 297                     if (t != null) {
 298                         return t;
 299                     }
 300                     if (insertln(ln, k, v, ct)) {
 301                         return Option.makeOption();// None
 302                     }
 303                     return null;
 304                 } else if (cond == INode.KEY_PRESENT) {
 305                     final Option<V> t = ln.get(k);
 306                     if (t == null) {
 307                         return null; // None
 308                     }
 309                     if (insertln(ln, k, v, ct)) {
 310                         return t;
 311                     }
 312                     return null;
 313                 } else {
 314                     final Option<V> t = ln.get(k);
 315                     if (t != null) {
 316                         if (((Some<V>) t).get() == cond) {
 317                             if (insertln(ln, k, v, ct)) {
 318                                 return new Some<>((V) cond);
 319                             }
 320
 321                             return null;
 322                         }
 323                         return Option.makeOption();
 324                     }
 325                 }
 326             }
 327
 328             //                throw new RuntimeException ("Should not happen");
 329         }
 330     }
 331
 332     boolean insertln(final LNode<K, V> ln, final K k, final V v, final TrieMap<K, V> ct) {
 333         final LNode<K, V> nn = ln.inserted (k, v);
 334         return GCAS(ln, nn, ct);
 335     }
 336
 337     /**
 338      * Looks up the value associated with the key.
 339      *
 340      * @return null if no value has been found, RESTART if the operation
 341      *         wasn't successful, or any other value otherwise
 342      */
 343     Object rec_lookup(final K k, final int hc, final int lev, final INode<K, V> parent, final Gen startgen,
 344             final TrieMap<K, V> ct) {
 345         while (true) {
 346             final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
 347
 348             if (m instanceof CNode) {
 349                 // 1) a multinode
 350                 final CNode<K, V> cn = (CNode<K, V>) m;
 351                 final int idx = (hc >>> lev) & 0x1f;
 352                 final int flag = 1 << idx;
 353                 final int bmp = cn.bitmap;
 354                 if ((bmp & flag) == 0) {
 355                     // 1a) bitmap shows no binding
 356                     return null;
 357                 }
 358
 359                 // 1b) bitmap contains a value - descend
 360                 final int pos = (bmp == 0xffffffff) ? idx : Integer.bitCount(bmp & (flag - 1));
 361                 final BasicNode sub = cn.array[pos];
 362                 if (sub instanceof INode) {
 363                     final INode<K, V> in = (INode<K, V>) sub;
 364                     if (ct.isReadOnly() || (startgen == in.gen)) {
 365                         return in.rec_lookup(k, hc, lev + 5, this, startgen, ct);
 366                     }
 367
 368                     if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
 369                         // Tail recursion: return rec_lookup(k, hc, lev, parent, startgen, ct);
 370                         continue;
 371                     }
 372
 373                     // used to be throw RestartException
 374                     return RESTART;
 375                 } else if (sub instanceof SNode) {
 376                     // 2) singleton node
 377                     final SNode<K, V> sn = (SNode<K, V>) sub;
 378                     if (sn.hc == hc && ct.equal(sn.k, k)) {
 379                         return sn.v;
 380                     }
 381
 382                     return null;
 383                 }
 384             } else if (m instanceof TNode) {
 385                 // 3) non-live node
 386                 return cleanReadOnly((TNode<K, V>) m, lev, parent, ct, k, hc);
 387             } else if (m instanceof LNode) {
 388                 // 5) an l-node
 389                 return ((LNode<K, V>) m).get(k);
 390             }
 391
 392             throw new RuntimeException ("Should not happen");
 393         }
 394     }
 395
 396     private Object cleanReadOnly(final TNode<K, V> tn, final int lev, final INode<K, V> parent,
 397             final TrieMap<K, V> ct, final K k, final int hc) {
 398         if (ct.nonReadOnly()) {
 399          // used to be throw RestartException
 400             clean(parent, ct, lev - 5);
 401             return RESTART;
 402         }
 403
 404         if (tn.hc == hc && ct.equal(tn.k, k)) {
 405             return tn.v;
 406         }
 407
 408         return null;
 409     }
 410
 411     /**
 412      * Removes the key associated with the given value.
 413      *
 414      * @param v
 415      *            if null, will remove the key regardless of the value;
 416      *            otherwise removes only if binding contains that exact key
 417      *            and value
 418      * @return null if not successful, an Option[V] indicating the previous
 419      *         value otherwise
 420      */
 421     Option<V> rec_remove(final K k, final V v, final int hc, final int lev, final INode<K, V> parent,
 422             final Gen startgen, final TrieMap<K, V> ct) {
 423         final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
 424
 425         if (m instanceof CNode) {
 426             final CNode<K, V> cn = (CNode<K, V>) m;
 427             final int idx = (hc >>> lev) & 0x1f;
 428             final int bmp = cn.bitmap;
 429             final int flag = 1 << idx;
 430             if ((bmp & flag) == 0) {
 431                 return Option.makeOption();
 432             }
 433
 434             final int pos = Integer.bitCount(bmp & (flag - 1));
 435             final BasicNode sub = cn.array[pos];
 436             Option<V> res = null;
 437             if (sub instanceof INode) {
 438                 final INode<K, V> in = (INode<K, V>) sub;
 439                 if (startgen == in.gen) {
 440                     res = in.rec_remove(k, v, hc, lev + 5, this, startgen, ct);
 441                 } else {
 442                     if (GCAS(cn, cn.renewed (startgen, ct), ct)) {
 443                         res = rec_remove(k, v, hc, lev, parent, startgen, ct);
 444                     } else {
 445                         res = null;
 446                     }
 447                 }
 448
 449             } else if (sub instanceof SNode) {
 450                 final SNode<K, V> sn = (SNode<K, V>) sub;
 451                 if (sn.hc == hc && ct.equal(sn.k, k) && (v == null || v.equals(sn.v))) {
 452                     final MainNode<K, V> ncn = cn.removedAt(pos, flag, gen).toContracted(lev);
 453                     if (GCAS(cn, ncn, ct)) {
 454                         res = Option.makeOption(sn.v);
 455                     } else {
 456                         res = null;
 457                     }
 458                 } else {
 459                     res = Option.makeOption ();
 460                 }
 461             }
 462
 463             if (res instanceof None || (res == null)) {
 464                 return res;
 465             }
 466
 467             if (parent != null) {
 468                 // never tomb at root
 469                 final MainNode<K, V> n = GCAS_READ(ct);
 470                 if (n instanceof TNode) {
 471                     cleanParent(n, parent, ct, hc, lev, startgen);
 472                 }
 473             }
 474
 475             return res;
 476         } else if (m instanceof TNode) {
 477             clean(parent, ct, lev - 5);
 478             return null;
 479         } else if (m instanceof LNode) {
 480             final LNode<K, V> ln = (LNode<K, V>) m;
 481             if (v == null) {
 482                 final Option<V> optv = ln.get(k);
 483                 final MainNode<K, V> nn = ln.removed(k, ct);
 484                 if (GCAS(ln, nn, ct)) {
 485                     return optv;
 486                 }
 487
 488                 return null;
 489             }
 490
 491             final Option<V> tmp = ln.get(k);
 492             if (tmp instanceof Some) {
 493                 final Some<V> tmp1 = (Some<V>) tmp;
 494                 if (tmp1.get() == v) {
 495                     final MainNode<K, V> nn = ln.removed(k, ct);
 496                     if (GCAS(ln, nn, ct)) {
 497                         return tmp;
 498                     }
 499
 500                     return null;
 501                 }
 502             }
 503         }
 504         throw new RuntimeException ("Should not happen");
 505     }
 506
 507     private void cleanParent(final Object nonlive, final INode<K, V> parent, final TrieMap<K, V> ct, final int hc,
 508             final int lev, final Gen startgen) {
 509         while (true) {
 510             final MainNode<K, V> pm = parent.GCAS_READ(ct);
 511             if ((!(pm instanceof CNode))) {
 512                 // parent is no longer a cnode, we're done
 513                 return;
 514             }
 515
 516             final CNode<K, V> cn = (CNode<K, V>) pm;
 517             final int idx = (hc >>> (lev - 5)) & 0x1f;
 518             final int bmp = cn.bitmap;
 519             final int flag = 1 << idx;
 520             if ((bmp & flag) == 0) {
 521                 // somebody already removed this i-node, we're done
 522                 return;
 523             }
 524
 525             final int pos = Integer.bitCount(bmp & (flag - 1));
 526             final BasicNode sub = cn.array[pos];
 527             if (sub == this) {
 528                 if (nonlive instanceof TNode) {
 529                     final TNode<K, V> tn = (TNode<K, V>) nonlive;
 530                     MainNode<K, V> ncn = cn.updatedAt(pos, tn.copyUntombed(), gen).toContracted(lev - 5);
 531                     if (!parent.GCAS(cn, ncn, ct)) {
 532                         if (ct.readRoot().gen == startgen) {
 533                             // Tail recursion: cleanParent(nonlive, parent, ct, hc, lev, startgen);
 534                             continue;
 535                         }
 536                     }
 537                 }
 538             }
 539             break;
 540         }
 541     }
 542
 543     private void clean(final INode<K, V> nd, final TrieMap<K, V> ct, final int lev) {
 544         final MainNode<K, V> m = nd.GCAS_READ(ct);
 545         if (m instanceof CNode) {
 546             final CNode<K, V> cn = (CNode<K, V>) m;
 547             nd.GCAS(cn, cn.toCompressed(ct, lev, gen), ct);
 548         }
 549     }
 550
 551     int cachedSize(final TrieMap<K, V> ct) {
 552         MainNode<K, V> m = GCAS_READ(ct);
 553         return m.cachedSize(ct);
 554     }
 555
 556     // /* this is a quiescent method! */
 557     // def string(lev: Int) = "%sINode -> %s".format("  " * lev, mainnode
 558     // match {
 559     // case null => "<null>"
 560     // case tn: TNode[_, _] => "TNode(%s, %s, %d, !)".format(tn.k, tn.v,
 561     // tn.hc)
 562     // case cn: CNode[_, _] => cn.string(lev)
 563     // case ln: LNode[_, _] => ln.string(lev)
 564     // case x => "<elem: %s>".format(x)
 565     // })
 566
 567     @Override
 568     String string(final int lev) {
 569         return "INode";
 570     }
 571 }