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