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