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