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