third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/INode.java

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