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

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