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