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