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