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

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