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