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