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