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

   1 package org.opendaylight.yangtools.triemap;
   2
   3 import java.io.IOException;
   4 import java.io.ObjectInputStream;
   5 import java.io.ObjectOutputStream;
   6 import java.io.Serializable;
   7 import java.lang.reflect.Field;
   8 import java.util.AbstractMap;
   9 import java.util.AbstractSet;
  10 import java.util.ArrayList;
  11 import java.util.Arrays;
  12 import java.util.Iterator;
  13 import java.util.List;
  14 import java.util.Map;
  15 import java.util.NoSuchElementException;
  16 import java.util.Set;
  17 import java.util.concurrent.ConcurrentMap;
  18 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
  19
  20 /***
  21  * This is a port of Scala's TrieMap class from the Scala Collections library.
  22  *
  23  * @author Roman Levenstein &lt;romixlev@gmail.com&gt;
  24  *
  25  * @param <K>
  26  * @param <V>
  27  */
  28 @SuppressWarnings({"unchecked", "rawtypes", "unused"})
  29 public class TrieMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K,V>, Serializable {
  30     private static final AtomicReferenceFieldUpdater<TrieMap, Object> ROOT_UPDATER = AtomicReferenceFieldUpdater.newUpdater(TrieMap.class, Object.class, "root");
  31     private static final long serialVersionUID = 1L;
  32     private static final Field READONLY_FIELD;
  33     private static final TrieMap EMPTY = new TrieMap();
  34
  35     static {
  36         final Field f;
  37         try {
  38             f = TrieMap.class.getDeclaredField("readOnly");
  39         } catch (NoSuchFieldException e) {
  40             throw new ExceptionInInitializerError(e);
  41         } catch (SecurityException e) {
  42             throw new ExceptionInInitializerError(e);
  43         }
  44         f.setAccessible(true);
  45         READONLY_FIELD = f;
  46     }
  47
  48     /**
  49      * EntrySet
  50      */
  51     private transient final EntrySet entrySet = new EntrySet ();
  52
  53     public static <K,V> TrieMap<K,V> empty () {
  54         return EMPTY;
  55     }
  56
  57     // static class MangledHashing<K> extends Hashing<K> {
  58     // int hash(K k) {
  59     // return util.hashing.byteswap32(k);
  60     // }
  61     // }
  62
  63     static class INode<K, V> extends INodeBase<K, V> {
  64         static final Object KEY_PRESENT = new Object ();
  65         static final Object KEY_ABSENT = new Object ();
  66
  67         static <K,V> INode<K,V> newRootNode () {
  68             Gen gen = new Gen ();
  69             CNode<K, V> cn = new CNode<> (0, new BasicNode[] {}, gen);
  70             return new INode<>(cn, gen);
  71         }
  72
  73         public INode (final MainNode<K, V> bn, final Gen g) {
  74             super (g);
  75             WRITE (bn);
  76         }
  77
  78         public INode (final Gen g) {
  79             this (null, g);
  80         }
  81
  82         final void WRITE (final MainNode<K, V> nval) {
  83             INodeBase.updater.set (this, nval);
  84         }
  85
  86         final boolean CAS (final MainNode<K, V> old, final MainNode<K, V> n) {
  87             return INodeBase.updater.compareAndSet (this, old, n);
  88         }
  89
  90         final MainNode<K, V> gcasRead (final TrieMap<K, V> ct) {
  91             return GCAS_READ (ct);
  92         }
  93
  94         final MainNode<K, V> GCAS_READ (final TrieMap<K, V> ct) {
  95             MainNode<K, V> m = /* READ */mainnode;
  96             MainNode<K, V> prevval = /* READ */m.prev;
  97             if (prevval == null) {
  98                 return m;
  99             } else {
 100                 return GCAS_Complete (m, ct);
 101             }
 102         }
 103
 104         private MainNode<K, V> GCAS_Complete (MainNode<K, V> m, final TrieMap<K, V> ct) {
 105             while (true) {
 106                 if (m == null) {
 107                     return null;
 108                 } else {
 109                     // complete the GCAS
 110                     MainNode<K, V> prev = /* READ */m.prev;
 111                     INode<K, V> ctr = ct.readRoot (true);
 112
 113                     if (prev == null) {
 114                         return m;
 115                     }
 116
 117                     if (prev instanceof FailedNode) {
 118                         // try to commit to previous value
 119                         FailedNode<K, V> fn = (FailedNode<K, V>) prev;
 120                         if (CAS (m, fn.prev)) {
 121                             return fn.prev;
 122                         } else {
 123                             // Tailrec
 124                             // return GCAS_Complete (/* READ */mainnode, ct);
 125                             m = /* READ */mainnode;
 126                             continue;
 127                         }
 128                     } else if (prev instanceof MainNode) {
 129                         // Assume that you've read the root from the generation
 130                         // G.
 131                         // Assume that the snapshot algorithm is correct.
 132                         // ==> you can only reach nodes in generations <= G.
 133                         // ==> `gen` is <= G.
 134                         // We know that `ctr.gen` is >= G.
 135                         // ==> if `ctr.gen` = `gen` then they are both equal to
 136                         // G.
 137                         // ==> otherwise, we know that either `ctr.gen` > G,
 138                         // `gen` <
 139                         // G,
 140                         // or both
 141                         if ((ctr.gen == gen) && ct.nonReadOnly ()) {
 142                             // try to commit
 143                             if (m.CAS_PREV (prev, null)) {
 144                                 return m;
 145                             } else {
 146                                 // return GCAS_Complete (m, ct);
 147                                 // tailrec
 148                                 continue;
 149                             }
 150                         } else {
 151                             // try to abort
 152                             m.CAS_PREV (prev, new FailedNode<> (prev));
 153                             return GCAS_Complete (/* READ */mainnode, ct);
 154                         }
 155                     }
 156                 }
 157                 throw new RuntimeException ("Should not happen");
 158             }
 159         }
 160
 161         final boolean GCAS (final MainNode<K, V> old, final MainNode<K, V> n, final TrieMap<K, V> ct) {
 162             n.WRITE_PREV (old);
 163             if (CAS (old, n)) {
 164                 GCAS_Complete (n, ct);
 165                 return /* READ */n.prev == null;
 166             } else {
 167                 return false;
 168             }
 169         }
 170
 171         private boolean equal (final K k1, final K k2, final TrieMap<K, V> ct) {
 172             return ct.equality ().equiv (k1, k2);
 173         }
 174
 175         private INode<K, V> inode (final MainNode<K, V> cn) {
 176             INode<K, V> nin = new INode<> (gen);
 177             nin.WRITE (cn);
 178             return nin;
 179         }
 180
 181         final INode<K, V> copyToGen (final Gen ngen, final TrieMap<K, V> ct) {
 182             INode<K, V> nin = new INode<> (ngen);
 183             MainNode<K, V> main = GCAS_READ (ct);
 184             nin.WRITE (main);
 185             return nin;
 186         }
 187
 188         /**
 189          * Inserts a key value pair, overwriting the old pair if the keys match.
 190          *
 191          * @return true if successful, false otherwise
 192          */
 193         final boolean rec_insert (final K k, final V v, final int hc, final int lev, final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
 194             while (true) {
 195                 MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
 196
 197                 if (m instanceof CNode) {
 198                     // 1) a multiway node
 199                     CNode<K, V> cn = (CNode<K, V>) m;
 200                     int idx = (hc >>> lev) & 0x1f;
 201                     int flag = 1 << idx;
 202                     int bmp = cn.bitmap;
 203                     int mask = flag - 1;
 204                     int pos = Integer.bitCount (bmp & mask);
 205                     if ((bmp & flag) != 0) {
 206                         // 1a) insert below
 207                         BasicNode cnAtPos = cn.array [pos];
 208                         if (cnAtPos instanceof INode) {
 209                             INode<K, V> in = (INode<K, V>) cnAtPos;
 210                             if (startgen == in.gen) {
 211                                 return in.rec_insert (k, v, hc, lev + 5, this, startgen, ct);
 212                             } else {
 213                                 if (GCAS (cn, cn.renewed (startgen, ct), ct)) {
 214                                     // return rec_insert (k, v, hc, lev, parent,
 215                                     // startgen, ct);
 216                                     // tailrec
 217                                     continue;
 218                                 } else {
 219                                     return false;
 220                                 }
 221                             }
 222                         } else if (cnAtPos instanceof SNode) {
 223                             SNode<K, V> sn = (SNode<K, V>) cnAtPos;
 224                             if (sn.hc == hc && equal (sn.k, k, ct)) {
 225                                 return GCAS (cn, cn.updatedAt (pos, new SNode<> (k, v, hc), gen), ct);
 226                             } else {
 227                                 CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
 228                                 MainNode<K, V> nn = rn.updatedAt (pos, inode (CNode.dual (sn, sn.hc, new SNode (k, v, hc), hc, lev + 5, gen)), gen);
 229                                 return GCAS (cn, nn, ct);
 230                             }
 231                         }
 232                     } else {
 233                         CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
 234                         MainNode<K, V> ncnode = rn.insertedAt (pos, flag, new SNode<> (k, v, hc), gen);
 235                         return GCAS (cn, ncnode, ct);
 236                     }
 237                 } else if (m instanceof TNode) {
 238                     clean (parent, ct, lev - 5);
 239                     return false;
 240                 } else if (m instanceof LNode) {
 241                     LNode<K, V> ln = (LNode<K, V>) m;
 242                     MainNode<K, V> nn = ln.inserted (k, v);
 243                     return GCAS (ln, nn, ct);
 244                 }
 245
 246                 throw new RuntimeException ("Should not happen");
 247             }
 248         }
 249
 250         /**
 251          * Inserts a new key value pair, given that a specific condition is met.
 252          *
 253          * @param cond
 254          *            null - don't care if the key was there
 255          *            KEY_ABSENT - key wasn't there
 256          *            KEY_PRESENT - key was there
 257          *            other value `v` - key must be bound to `v`
 258          * @return null if unsuccessful, Option[V] otherwise (indicating
 259          *         previous value bound to the key)
 260          */
 261         final Option<V> rec_insertif (final K k, final V v, final int hc, final Object cond, final int lev, final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
 262             while (true) {
 263                 MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
 264
 265                 if (m instanceof CNode) {
 266                     // 1) a multiway node
 267                     CNode<K, V> cn = (CNode<K, V>) m;
 268                     int idx = (hc >>> lev) & 0x1f;
 269                     int flag = 1 << idx;
 270                     int bmp = cn.bitmap;
 271                     int mask = flag - 1;
 272                     int pos = Integer.bitCount (bmp & mask);
 273
 274                     if ((bmp & flag) != 0) {
 275                         // 1a) insert below
 276                         BasicNode cnAtPos = cn.array [pos];
 277                         if (cnAtPos instanceof INode) {
 278                             INode<K, V> in = (INode<K, V>) cnAtPos;
 279                             if (startgen == in.gen) {
 280                                 return in.rec_insertif (k, v, hc, cond, lev + 5, this, startgen, ct);
 281                             } else {
 282                                 if (GCAS (cn, cn.renewed (startgen, ct), ct)) {
 283                                     // return rec_insertif (k, v, hc, cond, lev,
 284                                     // parent, startgen, ct);
 285                                     // tailrec
 286                                     continue;
 287                                 } else {
 288                                     return null;
 289                                 }
 290                             }
 291                         } else if (cnAtPos instanceof SNode) {
 292                             SNode<K, V> sn = (SNode<K, V>) cnAtPos;
 293                             if (cond == null) {
 294                                 if (sn.hc == hc && equal (sn.k, k, ct)) {
 295                                     if (GCAS (cn, cn.updatedAt (pos, new SNode<> (k, v, hc), gen), ct)) {
 296                                         return Option.makeOption(sn.v);
 297                                     } else {
 298                                         return null;
 299                                     }
 300                                 } else {
 301                                     CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
 302                                     MainNode<K, V> nn = rn.updatedAt (pos, inode (CNode.dual (sn, sn.hc, new SNode (k, v, hc), hc, lev + 5, gen)), gen);
 303                                     if (GCAS (cn, nn, ct)) {
 304                                         return Option.makeOption(); // None;
 305                                     } else {
 306                                         return null;
 307                                     }
 308                                 }
 309
 310                             } else if (cond == INode.KEY_ABSENT) {
 311                                 if (sn.hc == hc && equal (sn.k, k, ct)) {
 312                                     return Option.makeOption(sn.v);
 313                                 } else {
 314                                     CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
 315                                     MainNode<K, V> nn = rn.updatedAt (pos, inode (CNode.dual (sn, sn.hc, new SNode (k, v, hc), hc, lev + 5, gen)), gen);
 316                                     if (GCAS (cn, nn, ct)) {
 317                                         return Option.makeOption (); // None
 318                                     } else {
 319                                         return null;
 320                                     }
 321                                 }
 322                             } else if (cond == INode.KEY_PRESENT) {
 323                                 if (sn.hc == hc && equal (sn.k, k, ct)) {
 324                                     if (GCAS (cn, cn.updatedAt (pos, new SNode<> (k, v, hc), gen), ct)) {
 325                                         return Option.makeOption (sn.v);
 326                                     } else {
 327                                         return null;
 328                                     }
 329
 330                                 }
 331                                 else {
 332                                     return Option.makeOption ();// None;
 333                                 }
 334                             } else {
 335                                 if (sn.hc == hc && equal (sn.k, k, ct) && sn.v == cond) {
 336                                     if (GCAS (cn, cn.updatedAt (pos, new SNode<> (k, v, hc), gen), ct)) {
 337                                         return Option.makeOption (sn.v);
 338                                     } else {
 339                                         return null;
 340                                     }
 341                                 }
 342                                 else {
 343                                     return Option.makeOption (); // None
 344                                 }
 345                             }
 346
 347                         }
 348                     } else if (cond == null || cond == INode.KEY_ABSENT) {
 349                         CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
 350                         CNode<K, V> ncnode = rn.insertedAt (pos, flag, new SNode<> (k, v, hc), gen);
 351                         if (GCAS (cn, ncnode, ct)) {
 352                             return Option.makeOption ();// None
 353                         } else {
 354                             return null;
 355                         }
 356                     } else if (cond == INode.KEY_PRESENT) {
 357                         return Option.makeOption ();// None;
 358                     }
 359                     else {
 360                         return Option.makeOption (); // None
 361                     }
 362                 } else if (m instanceof TNode) {
 363                     clean (parent, ct, lev - 5);
 364                     return null;
 365                 } else if (m instanceof LNode) {
 366                     // 3) an l-node
 367                     LNode<K, V> ln = (LNode<K, V>) m;
 368                     if (cond == null) {
 369                         Option<V> optv = ln.get (k);
 370                         if (insertln (ln, k, v, ct)) {
 371                             return optv;
 372                         } else {
 373                             return null;
 374                         }
 375                     } else if (cond == INode.KEY_ABSENT) {
 376                         Option<V> t = ln.get (k);
 377                         if (t == null) {
 378                             if (insertln (ln, k, v, ct)) {
 379                                 return Option.makeOption ();// None
 380                             } else {
 381                                 return null;
 382                             }
 383                         } else {
 384                             return t;
 385                         }
 386                     } else if (cond == INode.KEY_PRESENT) {
 387                         Option<V> t = ln.get (k);
 388                         if (t != null) {
 389                             if (insertln (ln, k, v, ct)) {
 390                                 return t;
 391                             } else {
 392                                 return null;
 393                             }
 394                         }
 395                         else {
 396                             return null; // None
 397                         }
 398                     } else {
 399                         Option<V> t = ln.get (k);
 400                         if (t != null) {
 401                             if (((Some<V>) t).get () == cond) {
 402                                 if (insertln (ln, k, v, ct)) {
 403                                     return new Some<> ((V) cond);
 404                                 } else {
 405                                     return null;
 406                                 }
 407
 408                             } else {
 409                                 return Option.makeOption ();
 410                             }
 411                         }
 412                     }
 413                 }
 414
 415 //                throw new RuntimeException ("Should not happen");
 416             }
 417         }
 418
 419         final boolean insertln (final LNode<K, V> ln, final K k, final V v, final TrieMap<K, V> ct) {
 420             LNode<K, V> nn = ln.inserted (k, v);
 421             return GCAS (ln, nn, ct);
 422         }
 423
 424         /**
 425          * Looks up the value associated with the key.
 426          *
 427          * @return null if no value has been found, RESTART if the operation
 428          *         wasn't successful, or any other value otherwise
 429          */
 430         final Object rec_lookup (final K k, final int hc, final int lev, final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
 431             while (true) {
 432                 MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
 433
 434                 if (m instanceof CNode) {
 435                     // 1) a multinode
 436                     final CNode<K, V> cn = (CNode<K, V>) m;
 437                     int idx = (hc >>> lev) & 0x1f;
 438                     int flag = 1 << idx;
 439                     int bmp = cn.bitmap;
 440                     if ((bmp & flag) == 0) {
 441                         return null; // 1a) bitmap shows no binding
 442                     } else { // 1b) bitmap contains a value - descend
 443                         int pos = (bmp == 0xffffffff) ? idx : Integer.bitCount (bmp & (flag - 1));
 444                         final BasicNode sub = cn.array [pos];
 445                         if (sub instanceof INode) {
 446                             INode<K, V> in = (INode<K, V>) sub;
 447                             if (ct.isReadOnly () || (startgen == ((INodeBase<K, V>) sub).gen)) {
 448                                 return in.rec_lookup (k, hc, lev + 5, this, startgen, ct);
 449                             } else {
 450                                 if (GCAS (cn, cn.renewed (startgen, ct), ct)) {
 451                                     // return rec_lookup (k, hc, lev, parent,
 452                                     // startgen, ct);
 453                                     // Tailrec
 454                                     continue;
 455                                 }
 456                                 else {
 457                                     return RESTART; // used to be throw
 458                                                     // RestartException
 459                                 }
 460                             }
 461                         } else if (sub instanceof SNode) {
 462                             // 2) singleton node
 463                             SNode<K, V> sn = (SNode<K, V>) sub;
 464                             if (((SNode) sub).hc == hc && equal (sn.k, k, ct)) {
 465                                 return sn.v;
 466                             } else {
 467                                 return null;
 468                             }
 469                         }
 470                     }
 471                 } else if (m instanceof TNode) {
 472                     // 3) non-live node
 473                     return cleanReadOnly ((TNode<K, V>) m, lev, parent, ct, k, hc);
 474                 } else if (m instanceof LNode) {
 475                     // 5) an l-node
 476                     Option<V> tmp = ((LNode<K, V>) m).get (k);
 477                     return (tmp instanceof Option) ? ((Option<V>) tmp) : null;
 478                 }
 479
 480                 throw new RuntimeException ("Should not happen");
 481             }
 482         }
 483
 484         private Object cleanReadOnly (final TNode<K, V> tn, final int lev, final INode<K, V> parent, final TrieMap<K, V> ct, final K k, final int hc) {
 485             if (ct.nonReadOnly ()) {
 486                 clean (parent, ct, lev - 5);
 487                 return RESTART; // used to be throw RestartException
 488             } else {
 489                 if (tn.hc == hc && equal(tn.k, k, ct)) {
 490                     return tn.v;
 491                 } else {
 492                     return null;
 493                 }
 494             }
 495         }
 496
 497         /**
 498          * Removes the key associated with the given value.
 499          *
 500          * @param v
 501          *            if null, will remove the key irregardless of the value;
 502          *            otherwise removes only if binding contains that exact key
 503          *            and value
 504          * @return null if not successful, an Option[V] indicating the previous
 505          *         value otherwise
 506          */
 507         final Option<V> rec_remove (final K k, final V v, final int hc, final int lev, final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
 508             MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
 509
 510             if (m instanceof CNode) {
 511                 CNode<K, V> cn = (CNode<K, V>) m;
 512                 int idx = (hc >>> lev) & 0x1f;
 513                 int bmp = cn.bitmap;
 514                 int flag = 1 << idx;
 515                 if ((bmp & flag) == 0) {
 516                     return Option.makeOption ();
 517                 } else {
 518                     int pos = Integer.bitCount (bmp & (flag - 1));
 519                     BasicNode sub = cn.array [pos];
 520                     Option<V> res = null;
 521                     if (sub instanceof INode) {
 522                         INode<K, V> in = (INode<K, V>) sub;
 523                         if (startgen == in.gen) {
 524                             res = in.rec_remove (k, v, hc, lev + 5, this, startgen, ct);
 525                         } else {
 526                             if (GCAS (cn, cn.renewed (startgen, ct), ct)) {
 527                                 res = rec_remove (k, v, hc, lev, parent, startgen, ct);
 528                             } else {
 529                                 res = null;
 530                             }
 531                         }
 532
 533                     } else if (sub instanceof SNode) {
 534                         SNode<K, V> sn = (SNode<K, V>) sub;
 535                         if (sn.hc == hc && equal (sn.k, k, ct) && (v == null || v.equals(sn.v))) {
 536                             MainNode<K, V> ncn = cn.removedAt (pos, flag, gen).toContracted (lev);
 537                             if (GCAS (cn, ncn, ct)) {
 538                                 res = Option.makeOption (sn.v);
 539                             } else {
 540                                 res = null;
 541                             }
 542                         } else {
 543                             res = Option.makeOption ();
 544                         }
 545                     }
 546
 547                     if (res instanceof None || (res == null)) {
 548                         return res;
 549                     } else {
 550                         if (parent != null) { // never tomb at root
 551                             MainNode<K, V> n = GCAS_READ (ct);
 552                             if (n instanceof TNode) {
 553                                 cleanParent (n, parent, ct, hc, lev, startgen);
 554                             }
 555                         }
 556
 557                         return res;
 558                     }
 559                 }
 560             } else if (m instanceof TNode) {
 561                 clean (parent, ct, lev - 5);
 562                 return null;
 563             } else if (m instanceof LNode) {
 564                 LNode<K, V> ln = (LNode<K, V>) m;
 565                 if (v == null) {
 566                     Option<V> optv = ln.get (k);
 567                     MainNode<K, V> nn = ln.removed (k, ct);
 568                     if (GCAS (ln, nn, ct)) {
 569                         return optv;
 570                     } else {
 571                         return null;
 572                     }
 573                 } else {
 574                     Option<V> tmp = ln.get (k);
 575                     if (tmp instanceof Some) {
 576                         Some<V> tmp1 = (Some<V>) tmp;
 577                         if (tmp1.get () == v) {
 578                             MainNode<K, V> nn = ln.removed (k, ct);
 579                             if (GCAS (ln, nn, ct)) {
 580                                 return tmp;
 581                             } else {
 582                                 return null;
 583                             }
 584                         }
 585                     }
 586                 }
 587             }
 588             throw new RuntimeException ("Should not happen");
 589         }
 590
 591         void cleanParent (final Object nonlive, final INode<K, V> parent, final TrieMap<K, V> ct, final int hc, final int lev, final Gen startgen) {
 592             while (true) {
 593                 MainNode<K, V> pm = parent.GCAS_READ (ct);
 594                 if (pm instanceof CNode) {
 595                     CNode<K, V> cn = (CNode<K, V>) pm;
 596                     int idx = (hc >>> (lev - 5)) & 0x1f;
 597                     int bmp = cn.bitmap;
 598                     int flag = 1 << idx;
 599                     if ((bmp & flag) == 0) {
 600                     } // somebody already removed this i-node, we're done
 601                     else {
 602                         int pos = Integer.bitCount (bmp & (flag - 1));
 603                         BasicNode sub = cn.array [pos];
 604                         if (sub == this) {
 605                             if (nonlive instanceof TNode) {
 606                                 TNode<K, V> tn = (TNode<K, V>) nonlive;
 607                                 MainNode<K, V> ncn = cn.updatedAt (pos, tn.copyUntombed (), gen).toContracted (lev - 5);
 608                                 if (!parent.GCAS (cn, ncn, ct)) {
 609                                     if (ct.readRoot ().gen == startgen) {
 610                                         // cleanParent (nonlive, parent, ct, hc,
 611                                         // lev, startgen);
 612                                         // tailrec
 613                                         continue;
 614                                     }
 615                                 }
 616                             }
 617                         }
 618                     }
 619                 } else {
 620                     // parent is no longer a cnode, we're done
 621                 }
 622                 break;
 623             }
 624         }
 625
 626         private void clean (final INode<K, V> nd, final TrieMap<K, V> ct, final int lev) {
 627             MainNode<K, V> m = nd.GCAS_READ (ct);
 628             if (m instanceof CNode) {
 629                 CNode<K, V> cn = (CNode<K, V>) m;
 630                 nd.GCAS (cn, cn.toCompressed (ct, lev, gen), ct);
 631             }
 632         }
 633
 634         final boolean isNullInode (final TrieMap<K, V> ct) {
 635             return GCAS_READ (ct) == null;
 636         }
 637
 638         final int cachedSize (final TrieMap<K, V> ct) {
 639             MainNode<K, V> m = GCAS_READ (ct);
 640             return m.cachedSize (ct);
 641         }
 642
 643         // /* this is a quiescent method! */
 644         // def string(lev: Int) = "%sINode -> %s".format("  " * lev, mainnode
 645         // match {
 646         // case null => "<null>"
 647         // case tn: TNode[_, _] => "TNode(%s, %s, %d, !)".format(tn.k, tn.v,
 648         // tn.hc)
 649         // case cn: CNode[_, _] => cn.string(lev)
 650         // case ln: LNode[_, _] => ln.string(lev)
 651         // case x => "<elem: %s>".format(x)
 652         // })
 653
 654         @Override
 655         public String string (final int lev) {
 656             return "INode";
 657         }
 658
 659     }
 660
 661     private static final class FailedNode<K, V> extends MainNode<K, V> {
 662         MainNode<K, V> p;
 663
 664         FailedNode (final MainNode<K, V> p) {
 665             this.p = p;
 666             WRITE_PREV (p);
 667         }
 668
 669         @Override
 670         public String string (final int lev) {
 671             throw new UnsupportedOperationException ();
 672         }
 673
 674         @Override
 675         public int cachedSize (final Object ct) {
 676             throw new UnsupportedOperationException ();
 677         }
 678
 679         @Override
 680         public String toString () {
 681             return String.format ("FailedNode(%s)", p);
 682         }
 683     }
 684
 685     private interface KVNode<K, V> {
 686         Map.Entry<K, V> kvPair ();
 687     }
 688
 689     private static final class SNode<K, V> extends BasicNode implements KVNode<K, V> {
 690         final K k;
 691         final V v;
 692         final int hc;
 693
 694         SNode (final K k, final V v, final int hc) {
 695             this.k = k;
 696             this.v = v;
 697             this.hc = hc;
 698         }
 699
 700         final SNode<K, V> copy() {
 701             return new SNode<> (k, v, hc);
 702         }
 703
 704         final TNode<K, V> copyTombed () {
 705             return new TNode<> (k, v, hc);
 706         }
 707
 708         final SNode<K, V> copyUntombed () {
 709             return new SNode<> (k, v, hc);
 710         }
 711
 712         @Override
 713         final public Map.Entry<K, V> kvPair () {
 714             return new SimpleImmutableEntry<> (k, v);
 715         }
 716
 717         @Override
 718         final public String string (final int lev) {
 719             // ("  " * lev) + "SNode(%s, %s, %x)".format(k, v, hc);
 720             return "SNode";
 721         }
 722     }
 723
 724     private static final class TNode<K, V> extends MainNode<K, V> implements KVNode<K, V> {
 725         final K k;
 726         final V v;
 727         final int hc;
 728
 729         TNode (final K k, final V v, final int hc) {
 730             this.k = k;
 731             this.v = v;
 732             this.hc = hc;
 733         }
 734
 735         final TNode<K, V> copy () {
 736             return new TNode<> (k, v, hc);
 737         }
 738
 739         final TNode<K, V> copyTombed () {
 740             return new TNode<> (k, v, hc);
 741         }
 742
 743         final SNode<K, V> copyUntombed () {
 744             return new SNode<> (k, v, hc);
 745         }
 746
 747         @Override
 748         final public Map.Entry<K, V> kvPair () {
 749             return new SimpleImmutableEntry<> (k, v);
 750         }
 751
 752         @Override
 753         final public int cachedSize (final Object ct) {
 754             return 1;
 755         }
 756
 757         @Override
 758         final public String string (final int lev) {
 759             // ("  " * lev) + "TNode(%s, %s, %x, !)".format(k, v, hc);
 760             return "TNode";
 761         }
 762     }
 763
 764     private final static class LNode<K, V> extends MainNode<K, V> {
 765         final ListMap<K, V> listmap;
 766
 767         public LNode (final ListMap<K, V> listmap) {
 768             this.listmap = listmap;
 769         }
 770
 771         public LNode(final K k, final V v) {
 772             this (ListMap.map (k, v));
 773         }
 774
 775         public LNode (final K k1, final V v1, final K k2, final V v2) {
 776             this (ListMap.map (k1, v1, k2, v2));
 777         }
 778
 779         LNode<K, V> inserted (final K k, final V v) {
 780             return new LNode<> (listmap.add (k, v));
 781         }
 782
 783         MainNode<K, V> removed (final K k, final TrieMap<K, V> ct) {
 784             ListMap<K, V> updmap = listmap.remove (k);
 785             if (updmap.size () > 1) {
 786                 return new LNode<> (updmap);
 787             } else {
 788                 Entry<K, V> kv = updmap.iterator ().next ();
 789                 // create it tombed so that it gets compressed on subsequent
 790                 // accesses
 791                 return new TNode<> (kv.getKey (), kv.getValue (), ct.computeHash (kv.getKey ()));
 792             }
 793         }
 794
 795         Option<V> get (final K k) {
 796             return listmap.get (k);
 797         }
 798
 799         @Override
 800         public int cachedSize (final Object ct) {
 801             return listmap.size ();
 802         }
 803
 804         @Override
 805         public String string (final int lev) {
 806             // (" " * lev) + "LNode(%s)".format(listmap.mkString(", "))
 807             return "LNode";
 808         }
 809     }
 810
 811     private static final class CNode<K, V> extends CNodeBase<K, V> {
 812
 813         final int bitmap;
 814         final BasicNode[] array;
 815         final Gen gen;
 816
 817         CNode (final int bitmap, final BasicNode[] array, final Gen gen) {
 818             this.bitmap = bitmap;
 819             this.array = array;
 820             this.gen = gen;
 821         }
 822
 823         // this should only be called from within read-only snapshots
 824         @Override
 825         final public int cachedSize (final Object ct) {
 826             int currsz = READ_SIZE ();
 827             if (currsz != -1) {
 828                 return currsz;
 829             } else {
 830                 int sz = computeSize ((TrieMap<K, V>) ct);
 831                 while (READ_SIZE () == -1) {
 832                     CAS_SIZE (-1, sz);
 833                 }
 834                 return READ_SIZE ();
 835             }
 836         }
 837
 838         // lends itself towards being parallelizable by choosing
 839         // a random starting offset in the array
 840         // => if there are concurrent size computations, they start
 841         // at different positions, so they are more likely to
 842         // to be independent
 843         private int computeSize (final TrieMap<K, V> ct) {
 844             int i = 0;
 845             int sz = 0;
 846             // final int offset = (array.length > 0) ?
 847             // // util.Random.nextInt(array.length) /* <-- benchmarks show that
 848             // // this causes observable contention */
 849             // scala.concurrent.forkjoin.ThreadLocalRandom.current.nextInt (0,
 850             // array.length)
 851             // : 0;
 852
 853             final int offset = 0;
 854             while (i < array.length) {
 855                 int pos = (i + offset) % array.length;
 856                 BasicNode elem = array [pos];
 857                 if (elem instanceof SNode) {
 858                     sz += 1;
 859                 } else if (elem instanceof INode) {
 860                     sz += ((INode<K, V>) elem).cachedSize (ct);
 861                 }
 862                 i += 1;
 863             }
 864             return sz;
 865         }
 866
 867         final CNode<K, V> updatedAt (final int pos, final BasicNode nn, final Gen gen) {
 868             int len = array.length;
 869             BasicNode[] narr = new BasicNode[len];
 870             System.arraycopy (array, 0, narr, 0, len);
 871             narr [pos] = nn;
 872             return new CNode<> (bitmap, narr, gen);
 873         }
 874
 875         final CNode<K, V> removedAt (final int pos, final int flag, final Gen gen) {
 876             BasicNode[] arr = array;
 877             int len = arr.length;
 878             BasicNode[] narr = new BasicNode[len - 1];
 879             System.arraycopy (arr, 0, narr, 0, pos);
 880             System.arraycopy (arr, pos + 1, narr, pos, len - pos - 1);
 881             return new CNode<> (bitmap ^ flag, narr, gen);
 882         }
 883
 884         final CNode<K, V> insertedAt (final int pos, final int flag, final BasicNode nn, final Gen gen) {
 885             int len = array.length;
 886             int bmp = bitmap;
 887             BasicNode[] narr = new BasicNode[len + 1];
 888             System.arraycopy (array, 0, narr, 0, pos);
 889             narr [pos] = nn;
 890             System.arraycopy (array, pos, narr, pos + 1, len - pos);
 891             return new CNode<> (bmp | flag, narr, gen);
 892         }
 893
 894         /**
 895          * Returns a copy of this cnode such that all the i-nodes below it are
 896          * copied to the specified generation `ngen`.
 897          */
 898         final CNode<K, V> renewed (final Gen ngen, final TrieMap<K, V> ct) {
 899             int i = 0;
 900             BasicNode[] arr = array;
 901             int len = arr.length;
 902             BasicNode[] narr = new BasicNode[len];
 903             while (i < len) {
 904                 BasicNode elem = arr [i];
 905                 if (elem instanceof INode) {
 906                     INode<K, V> in = (INode<K, V>) elem;
 907                     narr [i] = in.copyToGen (ngen, ct);
 908                 } else if (elem instanceof BasicNode) {
 909                     narr [i] = elem;
 910                 }
 911                 i += 1;
 912             }
 913             return new CNode<> (bitmap, narr, ngen);
 914         }
 915
 916         private BasicNode resurrect (final INode<K, V> inode, final Object inodemain) {
 917             if (inodemain instanceof TNode) {
 918                 TNode<K, V> tn = (TNode<K, V>) inodemain;
 919                 return tn.copyUntombed ();
 920             } else {
 921                 return inode;
 922             }
 923         }
 924
 925         final MainNode<K, V> toContracted (final int lev) {
 926             if (array.length == 1 && lev > 0) {
 927                 if (array [0] instanceof SNode) {
 928                     SNode<K, V> sn = (SNode<K, V>) array [0];
 929                     return sn.copyTombed ();
 930                 } else {
 931                     return this;
 932                 }
 933
 934             } else {
 935                 return this;
 936             }
 937         }
 938
 939         // - if the branching factor is 1 for this CNode, and the child
 940         // is a tombed SNode, returns its tombed version
 941         // - otherwise, if there is at least one non-null node below,
 942         // returns the version of this node with at least some null-inodes
 943         // removed (those existing when the op began)
 944         // - if there are only null-i-nodes below, returns null
 945         final MainNode<K, V> toCompressed (final TrieMap<K, V> ct, final int lev, final Gen gen) {
 946             int bmp = bitmap;
 947             int i = 0;
 948             BasicNode[] arr = array;
 949             BasicNode[] tmparray = new BasicNode[arr.length];
 950             while (i < arr.length) { // construct new bitmap
 951                 BasicNode sub = arr [i];
 952                 if (sub instanceof INode) {
 953                     INode<K, V> in = (INode<K, V>) sub;
 954                     MainNode<K, V> inodemain = in.gcasRead (ct);
 955                     assert (inodemain != null);
 956                     tmparray [i] = resurrect (in, inodemain);
 957                 } else if (sub instanceof SNode) {
 958                     tmparray [i] = sub;
 959                 }
 960                 i += 1;
 961             }
 962
 963             return new CNode<K, V> (bmp, tmparray, gen).toContracted (lev);
 964         }
 965
 966         @Override
 967         public String string (final int lev) {
 968             // "CNode %x\n%s".format(bitmap, array.map(_.string(lev +
 969             // 1)).mkString("\n"));
 970             return "CNode";
 971         }
 972
 973         /*
 974          * quiescently consistent - don't call concurrently to anything
 975          * involving a GCAS!!
 976          */
 977         // protected Seq<K,V> collectElems() {
 978         // array flatMap {
 979         // case sn: SNode[K, V] => Some(sn.kvPair)
 980         // case in: INode[K, V] => in.mainnode match {
 981         // case tn: TNode[K, V] => Some(tn.kvPair)
 982         // case ln: LNode[K, V] => ln.listmap.toList
 983         // case cn: CNode[K, V] => cn.collectElems
 984         // }
 985         // }
 986         // }
 987
 988         // protected Seq<String> collectLocalElems() {
 989         // // array flatMap {
 990         // // case sn: SNode[K, V] => Some(sn.kvPair._2.toString)
 991         // // case in: INode[K, V] => Some(in.toString.drop(14) + "(" + in.gen +
 992         // ")")
 993         // // }
 994         // return null;
 995         // }
 996
 997         @Override
 998         public String toString () {
 999             // val elems = collectLocalElems
1000             // "CNode(sz: %d; %s)".format(elems.size,
1001             // elems.sorted.mkString(", "))
1002             return "CNode";
1003         }
1004
1005         static <K, V> MainNode<K,V> dual (final SNode<K, V> x, final int xhc, final SNode<K, V> y, final int yhc, final int lev, final Gen gen) {
1006             if (lev < 35) {
1007                 int xidx = (xhc >>> lev) & 0x1f;
1008                 int yidx = (yhc >>> lev) & 0x1f;
1009                 int bmp = (1 << xidx) | (1 << yidx);
1010
1011                 if (xidx == yidx) {
1012                     INode<K, V> subinode = new INode<> (gen);// (TrieMap.inodeupdater)
1013                     subinode.mainnode = dual (x, xhc, y, yhc, lev + 5, gen);
1014                     return new CNode<> (bmp, new BasicNode[] { subinode }, gen);
1015                 } else {
1016                     if (xidx < yidx) {
1017                         return new CNode<> (bmp, new BasicNode[] { x, y }, gen);
1018                     } else {
1019                         return new CNode<> (bmp, new BasicNode[] { y, x }, gen);
1020                     }
1021                 }
1022             } else {
1023                 return new LNode<> (x.k, x.v, y.k, y.v);
1024             }
1025         }
1026
1027     }
1028
1029     private static class RDCSS_Descriptor<K, V> {
1030         INode<K, V> old;
1031         MainNode<K, V> expectedmain;
1032         INode<K, V> nv;
1033         volatile boolean committed = false;
1034
1035         public RDCSS_Descriptor (final INode<K, V> old, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
1036             this.old = old;
1037             this.expectedmain = expectedmain;
1038             this.nv = nv;
1039         }
1040
1041     }
1042
1043     private static class Equiv<K> implements Serializable {
1044         private static final long serialVersionUID = 1L;
1045
1046         public boolean equiv (final K k1, final K k2) {
1047             return k1.equals (k2);
1048         }
1049
1050         static Equiv universal = new Equiv ();
1051     }
1052
1053     private static interface Hashing<K> extends Serializable {
1054         public int hash (K k);
1055     }
1056
1057     static class Default<K> implements Hashing<K> {
1058         private static final long serialVersionUID = 1L;
1059
1060         @Override
1061         public int hash (final K k) {
1062             int h = k.hashCode ();
1063             // This function ensures that hashCodes that differ only by
1064             // constant multiples at each bit position have a bounded
1065             // number of collisions (approximately 8 at default load factor).
1066             h ^= (h >>> 20) ^ (h >>> 12);
1067             h ^= (h >>> 7) ^ (h >>> 4);
1068             return h;
1069         }
1070     }
1071
1072     private final Hashing<K> hashingobj;
1073     private final Equiv<K> equalityobj;
1074
1075     Hashing<K> hashing () {
1076         return hashingobj;
1077     }
1078
1079     Equiv<K> equality () {
1080         return equalityobj;
1081     }
1082
1083     private transient volatile Object root;
1084     private final transient boolean readOnly;
1085
1086     TrieMap (final Hashing<K> hashf, final Equiv<K> ef, final boolean readOnly) {
1087         this.hashingobj = hashf;
1088         this.equalityobj = ef;
1089         this.readOnly = readOnly;
1090     }
1091
1092     TrieMap (final Object r, final Hashing<K> hashf, final Equiv<K> ef, final boolean readOnly) {
1093         this(hashf, ef, readOnly);
1094         this.root = r;
1095     }
1096
1097     public TrieMap (final Hashing<K> hashf, final Equiv<K> ef) {
1098         this(INode.newRootNode(), hashf, ef, false);
1099     }
1100
1101     public TrieMap () {
1102         this (new Default<K> (), Equiv.universal);
1103     }
1104
1105     /* internal methods */
1106
1107     // private void writeObject(java.io.ObjectOutputStream out) {
1108     // out.writeObject(hashf);
1109     // out.writeObject(ef);
1110     //
1111     // Iterator it = iterator();
1112     // while (it.hasNext) {
1113     // val (k, v) = it.next();
1114     // out.writeObject(k);
1115     // out.writeObject(v);
1116     // }
1117     // out.writeObject(TrieMapSerializationEnd);
1118     // }
1119     //
1120     // private TrieMap readObject(java.io.ObjectInputStream in) {
1121     // root = INode.newRootNode();
1122     // rootupdater = AtomicReferenceFieldUpdater.newUpdater(TrieMap.class,
1123     // Object.class, "root");
1124     //
1125     // hashingobj = in.readObject();
1126     // equalityobj = in.readObject();
1127     //
1128     // Object obj = null;
1129     // do {
1130     // obj = in.readObject();
1131     // if (obj != TrieMapSerializationEnd) {
1132     // K k = (K)obj;
1133     // V = (V)in.readObject();
1134     // update(k, v);
1135     // }
1136     // } while (obj != TrieMapSerializationEnd);
1137     // }
1138
1139     final boolean CAS_ROOT (final Object ov, final Object nv) {
1140         if (isReadOnly()) {
1141             throw new IllegalStateException("Attempted to modify a read-only snapshot");
1142         }
1143         return ROOT_UPDATER.compareAndSet (this, ov, nv);
1144     }
1145
1146     // FIXME: abort = false by default
1147     final INode<K, V> readRoot (final boolean abort) {
1148         return RDCSS_READ_ROOT (abort);
1149     }
1150
1151     final INode<K, V> readRoot () {
1152         return RDCSS_READ_ROOT (false);
1153     }
1154
1155     final INode<K, V> RDCSS_READ_ROOT () {
1156         return RDCSS_READ_ROOT (false);
1157     }
1158
1159     final INode<K, V> RDCSS_READ_ROOT (final boolean abort) {
1160         Object r = /* READ */root;
1161         if (r instanceof INode) {
1162             return (INode<K, V>) r;
1163         } else if (r instanceof RDCSS_Descriptor) {
1164             return RDCSS_Complete (abort);
1165         }
1166         throw new RuntimeException ("Should not happen");
1167     }
1168
1169     private final INode<K, V> RDCSS_Complete (final boolean abort) {
1170         while (true) {
1171             Object v = /* READ */root;
1172             if (v instanceof INode) {
1173                 return (INode<K, V>) v;
1174             } else if (v instanceof RDCSS_Descriptor) {
1175                 RDCSS_Descriptor<K, V> desc = (RDCSS_Descriptor<K, V>) v;
1176                 INode<K, V> ov = desc.old;
1177                 MainNode<K, V> exp = desc.expectedmain;
1178                 INode<K, V> nv = desc.nv;
1179
1180                 if (abort) {
1181                     if (CAS_ROOT (desc, ov)) {
1182                         return ov;
1183                     } else {
1184                         // return RDCSS_Complete (abort);
1185                         // tailrec
1186                         continue;
1187                     }
1188                 } else {
1189                     MainNode<K, V> oldmain = ov.gcasRead (this);
1190                     if (oldmain == exp) {
1191                         if (CAS_ROOT (desc, nv)) {
1192                             desc.committed = true;
1193                             return nv;
1194                         } else {
1195                             // return RDCSS_Complete (abort);
1196                             // tailrec
1197                             continue;
1198                         }
1199                     } else {
1200                         if (CAS_ROOT (desc, ov)) {
1201                             return ov;
1202                         } else {
1203                             // return RDCSS_Complete (abort);
1204                             // tailrec
1205                             continue;
1206
1207                         }
1208                     }
1209                 }
1210             }
1211
1212             throw new RuntimeException ("Should not happen");
1213         }
1214     }
1215
1216     private boolean RDCSS_ROOT (final INode<K, V> ov, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
1217         RDCSS_Descriptor<K, V> desc = new RDCSS_Descriptor<> (ov, expectedmain, nv);
1218         if (CAS_ROOT (ov, desc)) {
1219             RDCSS_Complete (false);
1220             return /* READ */desc.committed;
1221         } else {
1222             return false;
1223         }
1224     }
1225
1226     private void inserthc (final K k, final int hc, final V v) {
1227         while (true) {
1228             INode<K, V> r = RDCSS_READ_ROOT ();
1229             if (!r.rec_insert (k, v, hc, 0, null, r.gen, this)) {
1230                 // inserthc (k, hc, v);
1231                 // tailrec
1232                 continue;
1233             }
1234             break;
1235         }
1236     }
1237
1238     private Option<V> insertifhc (final K k, final int hc, final V v, final Object cond) {
1239         while (true) {
1240             INode<K, V> r = RDCSS_READ_ROOT ();
1241
1242             Option<V> ret = r.rec_insertif (k, v, hc, cond, 0, null, r.gen, this);
1243             if (ret == null) {
1244                 // return insertifhc (k, hc, v, cond);
1245                 // tailrec
1246                 continue;
1247             } else {
1248                 return ret;
1249             }
1250         }
1251     }
1252
1253     private Object lookuphc (final K k, final int hc) {
1254         while (true) {
1255             INode<K, V> r = RDCSS_READ_ROOT ();
1256             Object res = r.rec_lookup (k, hc, 0, null, r.gen, this);
1257             if (res == INodeBase.RESTART) {
1258                 // return lookuphc (k, hc);
1259                 // tailrec
1260                 continue;
1261             } else {
1262                 return res;
1263             }
1264         }
1265     }
1266
1267     private Option<V> removehc (final K k, final V v, final int hc) {
1268         while (true) {
1269             INode<K, V> r = RDCSS_READ_ROOT ();
1270             Option<V> res = r.rec_remove (k, v, hc, 0, null, r.gen, this);
1271             if (res != null) {
1272                 return res;
1273             } else {
1274                 // return removehc (k, v, hc);
1275                 // tailrec
1276                 continue;
1277             }
1278         }
1279     }
1280
1281     /**
1282      * Ensure this instance is read-write, throw UnsupportedOperationException
1283      * otherwise. Used by Map-type methods for quick check.
1284      */
1285     private void ensureReadWrite() {
1286         if (isReadOnly()) {
1287             throw new UnsupportedOperationException("Attempted to modify a read-only view");
1288         }
1289     }
1290
1291     public String string () {
1292         // RDCSS_READ_ROOT().string(0);
1293         return "Root";
1294     }
1295
1296     /* public methods */
1297
1298     // public Seq<V> seq() {
1299     // return this;
1300     // }
1301
1302     // override def par = new ParTrieMap(this)
1303
1304     // static TrieMap empty() {
1305     // return new TrieMap();
1306     // }
1307
1308     final boolean isReadOnly () {
1309         return readOnly;
1310     }
1311
1312     final boolean nonReadOnly () {
1313         return !readOnly;
1314     }
1315
1316     /**
1317      * Returns a snapshot of this TrieMap. This operation is lock-free and
1318      * linearizable.
1319      *
1320      * The snapshot is lazily updated - the first time some branch in the
1321      * snapshot or this TrieMap are accessed, they are rewritten. This means
1322      * that the work of rebuilding both the snapshot and this TrieMap is
1323      * distributed across all the threads doing updates or accesses subsequent
1324      * to the snapshot creation.
1325      */
1326
1327     final public TrieMap<K, V> snapshot () {
1328         while (true) {
1329             INode<K, V> r = RDCSS_READ_ROOT ();
1330             final MainNode<K, V> expmain = r.gcasRead (this);
1331             if (RDCSS_ROOT (r, expmain, r.copyToGen (new Gen (), this))) {
1332                 return new TrieMap<> (r.copyToGen (new Gen (), this), hashing (), equality (), readOnly);
1333             } else {
1334                 // return snapshot ();
1335                 // tailrec
1336                 continue;
1337             }
1338         }
1339     }
1340
1341     /**
1342      * Returns a read-only snapshot of this TrieMap. This operation is lock-free
1343      * and linearizable.
1344      *
1345      * The snapshot is lazily updated - the first time some branch of this
1346      * TrieMap are accessed, it is rewritten. The work of creating the snapshot
1347      * is thus distributed across subsequent updates and accesses on this
1348      * TrieMap by all threads. Note that the snapshot itself is never rewritten
1349      * unlike when calling the `snapshot` method, but the obtained snapshot
1350      * cannot be modified.
1351      *
1352      * This method is used by other methods such as `size` and `iterator`.
1353      */
1354     final public TrieMap<K, V> readOnlySnapshot () {
1355         // Is it a snapshot of a read-only snapshot?
1356         if(!nonReadOnly ()) {
1357             return this;
1358         }
1359
1360         while (true) {
1361             INode<K, V> r = RDCSS_READ_ROOT ();
1362             MainNode<K, V> expmain = r.gcasRead (this);
1363             if (RDCSS_ROOT (r, expmain, r.copyToGen (new Gen (), this))) {
1364                 return new TrieMap<> (r, hashing (), equality (), true);
1365             } else {
1366                 // return readOnlySnapshot ();
1367                 continue;
1368             }
1369         }
1370     }
1371
1372     @Override
1373     final public void clear () {
1374         while (true) {
1375             INode<K, V> r = RDCSS_READ_ROOT ();
1376             if (!RDCSS_ROOT (r, r.gcasRead (this), INode.<K, V>newRootNode ())) {
1377                 continue;
1378             }else{
1379                 return;
1380             }
1381         }
1382     }
1383
1384     // @inline
1385     int computeHash (final K k) {
1386         return hashingobj.hash (k);
1387     }
1388
1389     final V lookup (final K k) {
1390         int hc = computeHash (k);
1391 //        return (V) lookuphc (k, hc);
1392         Object o = lookuphc (k, hc);
1393         if(o instanceof Some) {
1394             return ((Some<V>)o).get ();
1395         } else if(o instanceof None) {
1396             return null;
1397         } else {
1398             return (V)o;
1399         }
1400     }
1401
1402     final V apply (final K k) {
1403         int hc = computeHash (k);
1404         Object res = lookuphc (k, hc);
1405         if (res == null) {
1406             throw new NoSuchElementException ();
1407         } else {
1408             return (V) res;
1409         }
1410     }
1411
1412 //    final public Option<V> get (K k) {
1413 //        int hc = computeHash (k);
1414 //        return Option.makeOption ((V)lookuphc (k, hc));
1415 //    }
1416
1417     @Override
1418     final public V get (final Object k) {
1419         return lookup((K)k);
1420     }
1421
1422     final public Option<V> putOpt(final Object key, final Object value) {
1423         int hc = computeHash ((K)key);
1424         return insertifhc ((K)key, hc, (V)value, null);
1425     }
1426
1427     @Override
1428     final public V put (final Object key, final Object value) {
1429         ensureReadWrite();
1430         int hc = computeHash ((K)key);
1431         Option<V> ov = insertifhc ((K)key, hc, (V)value, null);
1432         if(ov instanceof Some) {
1433             Some<V> sv = (Some<V>)ov;
1434             return sv.get ();
1435         } else {
1436             return null;
1437         }
1438     }
1439
1440     final public void update (final K k, final V v) {
1441         int hc = computeHash (k);
1442         inserthc (k, hc, v);
1443     }
1444
1445     final public TrieMap<K, V> add (final K k, final V v) {
1446         update (k, v);
1447         return this;
1448     }
1449
1450     final Option<V> removeOpt (final K k) {
1451         int hc = computeHash (k);
1452         return removehc (k, (V) null, hc);
1453     }
1454
1455     @Override
1456     final public V remove (final Object k) {
1457         ensureReadWrite();
1458         int hc = computeHash ((K)k);
1459         Option<V> ov = removehc ((K)k, (V) null, hc);
1460         if(ov instanceof Some) {
1461             Some<V> sv = (Some<V>)ov;
1462             return sv.get();
1463         } else {
1464             return null;
1465         }
1466     }
1467
1468 //    final public TrieMap<K, V> remove (Object k) {
1469 //        removeOpt ((K)k);
1470 //        return this;
1471 //    }
1472
1473     final public Option<V> putIfAbsentOpt (final K k, final V v) {
1474         int hc = computeHash (k);
1475         return insertifhc (k, hc, v, INode.KEY_ABSENT);
1476     }
1477
1478     @Override
1479     final public V putIfAbsent (final Object k, final Object v) {
1480         ensureReadWrite();
1481         int hc = computeHash ((K)k);
1482         Option<V> ov = insertifhc ((K)k, hc, (V)v, INode.KEY_ABSENT);
1483         if(ov instanceof Some) {
1484             Some<V> sv = (Some<V>)ov;
1485             return sv.get();
1486         } else {
1487             return null;
1488         }
1489     }
1490
1491     @Override
1492     public boolean remove (final Object k, final Object v) {
1493         ensureReadWrite();
1494         int hc = computeHash ((K)k);
1495         return removehc ((K)k, (V)v, hc).nonEmpty ();
1496     }
1497
1498     @Override
1499     public boolean replace (final K k, final V oldvalue, final V newvalue) {
1500         ensureReadWrite();
1501         int hc = computeHash (k);
1502         return insertifhc (k, hc, newvalue, oldvalue).nonEmpty ();
1503     }
1504
1505     public Option<V> replaceOpt (final K k, final V v) {
1506         int hc = computeHash (k);
1507         return insertifhc (k, hc, v, INode.KEY_PRESENT);
1508     }
1509
1510     @Override
1511     public V replace (final Object k, final Object v) {
1512         ensureReadWrite();
1513         int hc = computeHash ((K)k);
1514         Option<V> ov = insertifhc ((K)k, hc, (V)v, INode.KEY_PRESENT);
1515         if(ov instanceof Some) {
1516             Some<V> sv = (Some<V>)ov;
1517             return sv.get();
1518         } else {
1519             return null;
1520         }
1521     }
1522
1523     /***
1524      * Return an iterator over a TrieMap.
1525      *
1526      * If this is a read-only snapshot, it would return a read-only iterator.
1527      *
1528      * If it is the original TrieMap or a non-readonly snapshot, it would return
1529      * an iterator that would allow for updates.
1530      *
1531      * @return
1532      */
1533     public Iterator<Map.Entry<K, V>> iterator () {
1534         if (!nonReadOnly ()) {
1535             return readOnlySnapshot ().readOnlyIterator ();
1536         } else {
1537             return new TrieMapIterator<> (0, this);
1538         }
1539     }
1540
1541     /***
1542      * Return an iterator over a TrieMap.
1543      * This is a read-only iterator.
1544      *
1545      * @return
1546      */
1547     public Iterator<Map.Entry<K, V>> readOnlyIterator () {
1548         if (nonReadOnly ()) {
1549             return readOnlySnapshot ().readOnlyIterator ();
1550         } else {
1551             return new TrieMapReadOnlyIterator<> (0, this);
1552         }
1553     }
1554
1555     private int cachedSize () {
1556         INode<K, V> r = RDCSS_READ_ROOT ();
1557         return r.cachedSize (this);
1558     }
1559
1560     @Override
1561     public int size () {
1562         if (nonReadOnly ()) {
1563             return readOnlySnapshot ().size ();
1564         } else {
1565             return cachedSize ();
1566         }
1567     }
1568
1569     String stringPrefix () {
1570         return "TrieMap";
1571     }
1572
1573     /***
1574      * This iterator is a read-only one and does not allow for any update
1575      * operations on the underlying data structure.
1576      *
1577      * @param <K>
1578      * @param <V>
1579      */
1580     private static class TrieMapReadOnlyIterator<K, V> extends TrieMapIterator<K, V> {
1581         TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
1582             super (level, ct, mustInit);
1583         }
1584
1585         TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct) {
1586             this (level, ct, true);
1587         }
1588         @Override
1589         void initialize () {
1590             assert (ct.isReadOnly ());
1591             super.initialize ();
1592         }
1593
1594         @Override
1595         public void remove () {
1596             throw new UnsupportedOperationException ("Operation not supported for read-only iterators");
1597         }
1598
1599         @Override
1600         Map.Entry<K, V> nextEntry(final Map.Entry<K, V> rr) {
1601             // Return non-updatable entry
1602             return rr;
1603         }
1604     }
1605
1606     private static class TrieMapIterator<K, V> implements java.util.Iterator<Map.Entry<K, V>> {
1607         private int level;
1608         protected TrieMap<K, V> ct;
1609         private final boolean mustInit;
1610         private final BasicNode[][] stack = new BasicNode[7][];
1611         private final int[] stackpos = new int[7];
1612         private int depth = -1;
1613         private Iterator<Map.Entry<K, V>> subiter = null;
1614         private KVNode<K, V> current = null;
1615         private Map.Entry<K, V> lastReturned = null;
1616
1617         TrieMapIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
1618             this.level = level;
1619             this.ct = ct;
1620             this.mustInit = mustInit;
1621             if (this.mustInit) {
1622                 initialize ();
1623             }
1624         }
1625
1626         TrieMapIterator (final int level, final TrieMap<K, V> ct) {
1627             this (level, ct, true);
1628         }
1629
1630
1631         @Override
1632         public boolean hasNext () {
1633             return (current != null) || (subiter != null);
1634         }
1635
1636         @Override
1637         public Map.Entry<K, V> next () {
1638             if (hasNext ()) {
1639                 Map.Entry<K, V> r = null;
1640                 if (subiter != null) {
1641                     r = subiter.next ();
1642                     checkSubiter ();
1643                 } else {
1644                     r = current.kvPair ();
1645                     advance ();
1646                 }
1647
1648                 lastReturned = r;
1649                 if(r instanceof Map.Entry) {
1650                     final Map.Entry<K, V> rr = r;
1651                     return nextEntry(rr);
1652                 }
1653                 return r;
1654             } else {
1655                 // return Iterator.empty ().next ();
1656                 return null;
1657             }
1658         }
1659
1660         Map.Entry<K, V> nextEntry(final Map.Entry<K, V> rr) {
1661             return new Map.Entry<K, V>() {
1662                 private V updated = null;
1663
1664                 @Override
1665                 public K getKey () {
1666                     return rr.getKey ();
1667                 }
1668
1669                 @Override
1670                 public V getValue () {
1671                     return (updated == null)?rr.getValue (): updated;
1672                 }
1673
1674                 @Override
1675                 public V setValue (final V value) {
1676                     updated = value;
1677                     return ct.replace (getKey (), value);
1678                 }
1679             };
1680         }
1681
1682         private void readin (final INode<K, V> in) {
1683             MainNode<K, V> m = in.gcasRead (ct);
1684             if (m instanceof CNode) {
1685                 CNode<K, V> cn = (CNode<K, V>) m;
1686                 depth += 1;
1687                 stack [depth] = cn.array;
1688                 stackpos [depth] = -1;
1689                 advance ();
1690             } else if (m instanceof TNode) {
1691                 current = (TNode<K, V>) m;
1692             } else if (m instanceof LNode) {
1693                 subiter = ((LNode<K, V>) m).listmap.iterator ();
1694                 checkSubiter ();
1695             } else if (m == null) {
1696                 current = null;
1697             }
1698         }
1699
1700         // @inline
1701         private void checkSubiter () {
1702             if (!subiter.hasNext ()) {
1703                 subiter = null;
1704                 advance ();
1705             }
1706         }
1707
1708         // @inline
1709         void initialize () {
1710 //            assert (ct.isReadOnly ());
1711             INode<K, V> r = ct.RDCSS_READ_ROOT ();
1712             readin (r);
1713         }
1714
1715         void advance () {
1716             if (depth >= 0) {
1717                 int npos = stackpos [depth] + 1;
1718                 if (npos < stack [depth].length) {
1719                     stackpos [depth] = npos;
1720                     BasicNode elem = stack [depth] [npos];
1721                     if (elem instanceof SNode) {
1722                         current = (SNode<K, V>) elem;
1723                     } else if (elem instanceof INode) {
1724                         readin ((INode<K, V>) elem);
1725                     }
1726                 } else {
1727                     depth -= 1;
1728                     advance ();
1729                 }
1730             } else {
1731                 current = null;
1732             }
1733         }
1734
1735         protected TrieMapIterator<K, V> newIterator (final int _lev, final TrieMap<K, V> _ct, final boolean _mustInit) {
1736             return new TrieMapIterator<> (_lev, _ct, _mustInit);
1737         }
1738
1739         protected void dupTo (final TrieMapIterator<K, V> it) {
1740             it.level = this.level;
1741             it.ct = this.ct;
1742             it.depth = this.depth;
1743             it.current = this.current;
1744
1745             // these need a deep copy
1746             System.arraycopy (this.stack, 0, it.stack, 0, 7);
1747             System.arraycopy (this.stackpos, 0, it.stackpos, 0, 7);
1748
1749             // this one needs to be evaluated
1750             if (this.subiter == null) {
1751                 it.subiter = null;
1752             } else {
1753                 List<Map.Entry<K, V>> lst = toList (this.subiter);
1754                 this.subiter = lst.iterator ();
1755                 it.subiter = lst.iterator ();
1756             }
1757         }
1758
1759         // /** Returns a sequence of iterators over subsets of this iterator.
1760         // * It's used to ease the implementation of splitters for a parallel
1761         // version of the TrieMap.
1762         // */
1763         // protected def subdivide(): Seq[Iterator[(K, V)]] = if (subiter ne
1764         // null) {
1765         // // the case where an LNode is being iterated
1766         // val it = subiter
1767         // subiter = null
1768         // advance()
1769         // this.level += 1
1770         // Seq(it, this)
1771         // } else if (depth == -1) {
1772         // this.level += 1
1773         // Seq(this)
1774         // } else {
1775         // var d = 0
1776         // while (d <= depth) {
1777         // val rem = stack(d).length - 1 - stackpos(d)
1778         // if (rem > 0) {
1779         // val (arr1, arr2) = stack(d).drop(stackpos(d) + 1).splitAt(rem / 2)
1780         // stack(d) = arr1
1781         // stackpos(d) = -1
1782         // val it = newIterator(level + 1, ct, false)
1783         // it.stack(0) = arr2
1784         // it.stackpos(0) = -1
1785         // it.depth = 0
1786         // it.advance() // <-- fix it
1787         // this.level += 1
1788         // return Seq(this, it)
1789         // }
1790         // d += 1
1791         // }
1792         // this.level += 1
1793         // Seq(this)
1794         // }
1795
1796         private List<Entry<K, V>> toList (final Iterator<Entry<K, V>> it) {
1797             ArrayList<Entry<K, V>> list = new ArrayList<> ();
1798             while (it.hasNext ()) {
1799                 list.add (it.next ());
1800             }
1801             return list;
1802         }
1803
1804         void printDebug () {
1805             System.out.println ("ctrie iterator");
1806             System.out.println (Arrays.toString (stackpos));
1807             System.out.println ("depth: " + depth);
1808             System.out.println ("curr.: " + current);
1809             // System.out.println(stack.mkString("\n"));
1810         }
1811
1812         @Override
1813         public void remove () {
1814             if (lastReturned != null) {
1815                 ct.remove (lastReturned.getKey ());
1816                 lastReturned = null;
1817             } else {
1818                 throw new IllegalStateException();
1819             }
1820         }
1821
1822     }
1823
1824     /** Only used for ctrie serialization. */
1825     // @SerialVersionUID(0L - 7237891413820527142L)
1826     private static long TrieMapSerializationEnd = 0L - 7237891413820527142L;
1827
1828
1829     @Override
1830     public boolean containsKey (final Object key) {
1831         return lookup ((K) key) != null;
1832     }
1833
1834
1835     @Override
1836     public Set<Map.Entry<K, V>> entrySet () {
1837         return entrySet;
1838     }
1839
1840     /***
1841      * Support for EntrySet operations required by the Map interface
1842      *
1843      */
1844     final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
1845
1846         @Override
1847         public Iterator<Map.Entry<K, V>> iterator () {
1848             return TrieMap.this.iterator ();
1849         }
1850
1851         @Override
1852         public final boolean contains (final Object o) {
1853             if (!(o instanceof Map.Entry)) {
1854                 return false;
1855             }
1856             final Map.Entry<K, V> e = (Map.Entry<K, V>) o;
1857             final K k = e.getKey ();
1858             final V v = lookup (k);
1859             return v != null;
1860         }
1861
1862         @Override
1863         public final boolean remove (final Object o) {
1864             if (!(o instanceof Map.Entry)) {
1865                 return false;
1866             }
1867             final Map.Entry<K, V> e = (Map.Entry<K, V>) o;
1868             final K k = e.getKey ();
1869             return null != TrieMap.this.remove (k);
1870         }
1871
1872         @Override
1873         public final int size () {
1874             int size = 0;
1875             for (final Iterator<?> i = iterator (); i.hasNext (); i.next ()) {
1876                 size++;
1877             }
1878             return size;
1879         }
1880
1881         @Override
1882         public final void clear () {
1883             TrieMap.this.clear ();
1884         }
1885     }
1886
1887     private void readObject(final ObjectInputStream inputStream) throws IOException, ClassNotFoundException {
1888         inputStream.defaultReadObject();
1889         this.root = INode.newRootNode();
1890
1891         final boolean ro = inputStream.readBoolean();
1892         final int size = inputStream.readInt();
1893         for (int i = 0; i < size; ++i) {
1894             final K key = (K)inputStream.readObject();
1895             final V value = (V)inputStream.readObject();
1896             add(key, value);
1897         }
1898
1899         // Propagate the read-only bit
1900         try {
1901             READONLY_FIELD.setBoolean(this, ro);
1902         } catch (IllegalAccessException e) {
1903             throw new IOException("Failed to set read-only flag", e);
1904         }
1905     }
1906
1907     private void writeObject(final ObjectOutputStream outputStream) throws IOException {
1908         outputStream.defaultWriteObject();
1909
1910         final Map<K, V> ro = readOnlySnapshot();
1911         outputStream.writeBoolean(isReadOnly());
1912         outputStream.writeInt(ro.size());
1913
1914         for (Entry<K, V> e : ro.entrySet()) {
1915             outputStream.writeObject(e.getKey());
1916             outputStream.writeObject(e.getValue());
1917         }
1918     }
1919 }