third-party/triemap/src/main/java/com/romix/scala/collection/concurrent/TrieMap.java

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