1 package org.opendaylight.yangtools.triemap;
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;
15 import java.util.NoSuchElementException;
17 import java.util.concurrent.ConcurrentMap;
18 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
21 * This is a port of Scala's TrieMap class from the Scala Collections library.
23 * @author Roman Levenstein <romixlev@gmail.com>
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();
38 f = TrieMap.class.getDeclaredField("readOnly");
39 } catch (NoSuchFieldException e) {
40 throw new ExceptionInInitializerError(e);
41 } catch (SecurityException e) {
42 throw new ExceptionInInitializerError(e);
44 f.setAccessible(true);
51 private transient final EntrySet entrySet = new EntrySet ();
53 public static <K,V> TrieMap<K,V> empty () {
57 // static class MangledHashing<K> extends Hashing<K> {
59 // return util.hashing.byteswap32(k);
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 ();
67 static <K,V> INode<K,V> newRootNode () {
69 CNode<K, V> cn = new CNode<> (0, new BasicNode[] {}, gen);
70 return new INode<>(cn, gen);
73 public INode (final MainNode<K, V> bn, final Gen g) {
78 public INode (final Gen g) {
82 final void WRITE (final MainNode<K, V> nval) {
83 INodeBase.updater.set (this, nval);
86 final boolean CAS (final MainNode<K, V> old, final MainNode<K, V> n) {
87 return INodeBase.updater.compareAndSet (this, old, n);
90 final MainNode<K, V> gcasRead (final TrieMap<K, V> ct) {
91 return GCAS_READ (ct);
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) {
100 return GCAS_Complete (m, ct);
104 private MainNode<K, V> GCAS_Complete (MainNode<K, V> m, final TrieMap<K, V> ct) {
110 MainNode<K, V> prev = /* READ */m.prev;
111 INode<K, V> ctr = ct.readRoot (true);
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)) {
124 // return GCAS_Complete (/* READ */mainnode, ct);
125 m = /* READ */mainnode;
128 } else if (prev instanceof MainNode) {
129 // Assume that you've read the root from the generation
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
137 // ==> otherwise, we know that either `ctr.gen` > G,
141 if ((ctr.gen == gen) && ct.nonReadOnly ()) {
143 if (m.CAS_PREV (prev, null)) {
146 // return GCAS_Complete (m, ct);
152 m.CAS_PREV (prev, new FailedNode<> (prev));
153 return GCAS_Complete (/* READ */mainnode, ct);
157 throw new RuntimeException ("Should not happen");
161 final boolean GCAS (final MainNode<K, V> old, final MainNode<K, V> n, final TrieMap<K, V> ct) {
164 GCAS_Complete (n, ct);
165 return /* READ */n.prev == null;
171 private boolean equal (final K k1, final K k2, final TrieMap<K, V> ct) {
172 return ct.equality ().equiv (k1, k2);
175 private INode<K, V> inode (final MainNode<K, V> cn) {
176 INode<K, V> nin = new INode<> (gen);
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);
189 * Inserts a key value pair, overwriting the old pair if the keys match.
191 * @return true if successful, false otherwise
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) {
195 MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
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;
204 int pos = Integer.bitCount (bmp & mask);
205 if ((bmp & flag) != 0) {
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);
213 if (GCAS (cn, cn.renewed (startgen, ct), ct)) {
214 // return rec_insert (k, v, hc, lev, parent,
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);
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);
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);
237 } else if (m instanceof TNode) {
238 clean (parent, ct, lev - 5);
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);
246 throw new RuntimeException ("Should not happen");
251 * Inserts a new key value pair, given that a specific condition is met.
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)
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) {
263 MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
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;
272 int pos = Integer.bitCount (bmp & mask);
274 if ((bmp & flag) != 0) {
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);
282 if (GCAS (cn, cn.renewed (startgen, ct), ct)) {
283 // return rec_insertif (k, v, hc, cond, lev,
284 // parent, startgen, ct);
291 } else if (cnAtPos instanceof SNode) {
292 SNode<K, V> sn = (SNode<K, V>) cnAtPos;
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);
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;
310 } else if (cond == INode.KEY_ABSENT) {
311 if (sn.hc == hc && equal (sn.k, k, ct)) {
312 return Option.makeOption(sn.v);
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
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);
332 return Option.makeOption ();// None;
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);
343 return Option.makeOption (); // None
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
356 } else if (cond == INode.KEY_PRESENT) {
357 return Option.makeOption ();// None;
360 return Option.makeOption (); // None
362 } else if (m instanceof TNode) {
363 clean (parent, ct, lev - 5);
365 } else if (m instanceof LNode) {
367 LNode<K, V> ln = (LNode<K, V>) m;
369 Option<V> optv = ln.get (k);
370 if (insertln (ln, k, v, ct)) {
375 } else if (cond == INode.KEY_ABSENT) {
376 Option<V> t = ln.get (k);
378 if (insertln (ln, k, v, ct)) {
379 return Option.makeOption ();// None
386 } else if (cond == INode.KEY_PRESENT) {
387 Option<V> t = ln.get (k);
389 if (insertln (ln, k, v, ct)) {
399 Option<V> t = ln.get (k);
401 if (((Some<V>) t).get () == cond) {
402 if (insertln (ln, k, v, ct)) {
403 return new Some<> ((V) cond);
409 return Option.makeOption ();
415 // throw new RuntimeException ("Should not happen");
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);
425 * Looks up the value associated with the key.
427 * @return null if no value has been found, RESTART if the operation
428 * wasn't successful, or any other value otherwise
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) {
432 MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
434 if (m instanceof CNode) {
436 final CNode<K, V> cn = (CNode<K, V>) m;
437 int idx = (hc >>> lev) & 0x1f;
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);
450 if (GCAS (cn, cn.renewed (startgen, ct), ct)) {
451 // return rec_lookup (k, hc, lev, parent,
457 return RESTART; // used to be throw
461 } else if (sub instanceof SNode) {
463 SNode<K, V> sn = (SNode<K, V>) sub;
464 if (((SNode) sub).hc == hc && equal (sn.k, k, ct)) {
471 } else if (m instanceof TNode) {
473 return cleanReadOnly ((TNode<K, V>) m, lev, parent, ct, k, hc);
474 } else if (m instanceof LNode) {
476 Option<V> tmp = ((LNode<K, V>) m).get (k);
477 return (tmp instanceof Option) ? ((Option<V>) tmp) : null;
480 throw new RuntimeException ("Should not happen");
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
489 if (tn.hc == hc && equal(tn.k, k, ct)) {
498 * Removes the key associated with the given value.
501 * if null, will remove the key irregardless of the value;
502 * otherwise removes only if binding contains that exact key
504 * @return null if not successful, an Option[V] indicating the previous
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!
510 if (m instanceof CNode) {
511 CNode<K, V> cn = (CNode<K, V>) m;
512 int idx = (hc >>> lev) & 0x1f;
515 if ((bmp & flag) == 0) {
516 return Option.makeOption ();
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);
526 if (GCAS (cn, cn.renewed (startgen, ct), ct)) {
527 res = rec_remove (k, v, hc, lev, parent, startgen, ct);
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);
543 res = Option.makeOption ();
547 if (res instanceof None || (res == null)) {
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);
560 } else if (m instanceof TNode) {
561 clean (parent, ct, lev - 5);
563 } else if (m instanceof LNode) {
564 LNode<K, V> ln = (LNode<K, V>) m;
566 Option<V> optv = ln.get (k);
567 MainNode<K, V> nn = ln.removed (k, ct);
568 if (GCAS (ln, nn, ct)) {
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)) {
588 throw new RuntimeException ("Should not happen");
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) {
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;
599 if ((bmp & flag) == 0) {
600 } // somebody already removed this i-node, we're done
602 int pos = Integer.bitCount (bmp & (flag - 1));
603 BasicNode sub = cn.array [pos];
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,
620 // parent is no longer a cnode, we're done
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);
634 final boolean isNullInode (final TrieMap<K, V> ct) {
635 return GCAS_READ (ct) == null;
638 final int cachedSize (final TrieMap<K, V> ct) {
639 MainNode<K, V> m = GCAS_READ (ct);
640 return m.cachedSize (ct);
643 // /* this is a quiescent method! */
644 // def string(lev: Int) = "%sINode -> %s".format(" " * lev, mainnode
646 // case null => "<null>"
647 // case tn: TNode[_, _] => "TNode(%s, %s, %d, !)".format(tn.k, tn.v,
649 // case cn: CNode[_, _] => cn.string(lev)
650 // case ln: LNode[_, _] => ln.string(lev)
651 // case x => "<elem: %s>".format(x)
655 public String string (final int lev) {
661 private static final class FailedNode<K, V> extends MainNode<K, V> {
664 FailedNode (final MainNode<K, V> p) {
670 public String string (final int lev) {
671 throw new UnsupportedOperationException ();
675 public int cachedSize (final Object ct) {
676 throw new UnsupportedOperationException ();
680 public String toString () {
681 return String.format ("FailedNode(%s)", p);
685 private interface KVNode<K, V> {
686 Map.Entry<K, V> kvPair ();
689 private static final class SNode<K, V> extends BasicNode implements KVNode<K, V> {
694 SNode (final K k, final V v, final int hc) {
700 final SNode<K, V> copy() {
701 return new SNode<> (k, v, hc);
704 final TNode<K, V> copyTombed () {
705 return new TNode<> (k, v, hc);
708 final SNode<K, V> copyUntombed () {
709 return new SNode<> (k, v, hc);
713 final public Map.Entry<K, V> kvPair () {
714 return new SimpleImmutableEntry<> (k, v);
718 final public String string (final int lev) {
719 // (" " * lev) + "SNode(%s, %s, %x)".format(k, v, hc);
724 private static final class TNode<K, V> extends MainNode<K, V> implements KVNode<K, V> {
729 TNode (final K k, final V v, final int hc) {
735 final TNode<K, V> copy () {
736 return new TNode<> (k, v, hc);
739 final TNode<K, V> copyTombed () {
740 return new TNode<> (k, v, hc);
743 final SNode<K, V> copyUntombed () {
744 return new SNode<> (k, v, hc);
748 final public Map.Entry<K, V> kvPair () {
749 return new SimpleImmutableEntry<> (k, v);
753 final public int cachedSize (final Object ct) {
758 final public String string (final int lev) {
759 // (" " * lev) + "TNode(%s, %s, %x, !)".format(k, v, hc);
764 private final static class LNode<K, V> extends MainNode<K, V> {
765 final ListMap<K, V> listmap;
767 public LNode (final ListMap<K, V> listmap) {
768 this.listmap = listmap;
771 public LNode(final K k, final V v) {
772 this (ListMap.map (k, v));
775 public LNode (final K k1, final V v1, final K k2, final V v2) {
776 this (ListMap.map (k1, v1, k2, v2));
779 LNode<K, V> inserted (final K k, final V v) {
780 return new LNode<> (listmap.add (k, v));
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);
788 Entry<K, V> kv = updmap.iterator ().next ();
789 // create it tombed so that it gets compressed on subsequent
791 return new TNode<> (kv.getKey (), kv.getValue (), ct.computeHash (kv.getKey ()));
795 Option<V> get (final K k) {
796 return listmap.get (k);
800 public int cachedSize (final Object ct) {
801 return listmap.size ();
805 public String string (final int lev) {
806 // (" " * lev) + "LNode(%s)".format(listmap.mkString(", "))
811 private static final class CNode<K, V> extends CNodeBase<K, V> {
814 final BasicNode[] array;
817 CNode (final int bitmap, final BasicNode[] array, final Gen gen) {
818 this.bitmap = bitmap;
823 // this should only be called from within read-only snapshots
825 final public int cachedSize (final Object ct) {
826 int currsz = READ_SIZE ();
830 int sz = computeSize ((TrieMap<K, V>) ct);
831 while (READ_SIZE () == -1) {
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
843 private int computeSize (final TrieMap<K, V> ct) {
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,
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) {
859 } else if (elem instanceof INode) {
860 sz += ((INode<K, V>) elem).cachedSize (ct);
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);
872 return new CNode<> (bitmap, narr, gen);
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);
884 final CNode<K, V> insertedAt (final int pos, final int flag, final BasicNode nn, final Gen gen) {
885 int len = array.length;
887 BasicNode[] narr = new BasicNode[len + 1];
888 System.arraycopy (array, 0, narr, 0, pos);
890 System.arraycopy (array, pos, narr, pos + 1, len - pos);
891 return new CNode<> (bmp | flag, narr, gen);
895 * Returns a copy of this cnode such that all the i-nodes below it are
896 * copied to the specified generation `ngen`.
898 final CNode<K, V> renewed (final Gen ngen, final TrieMap<K, V> ct) {
900 BasicNode[] arr = array;
901 int len = arr.length;
902 BasicNode[] narr = new BasicNode[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) {
913 return new CNode<> (bitmap, narr, ngen);
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 ();
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 ();
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) {
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) {
963 return new CNode<K, V> (bmp, tmparray, gen).toContracted (lev);
967 public String string (final int lev) {
968 // "CNode %x\n%s".format(bitmap, array.map(_.string(lev +
969 // 1)).mkString("\n"));
974 * quiescently consistent - don't call concurrently to anything
977 // protected Seq<K,V> collectElems() {
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
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 +
998 public String toString () {
999 // val elems = collectLocalElems
1000 // "CNode(sz: %d; %s)".format(elems.size,
1001 // elems.sorted.mkString(", "))
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) {
1007 int xidx = (xhc >>> lev) & 0x1f;
1008 int yidx = (yhc >>> lev) & 0x1f;
1009 int bmp = (1 << xidx) | (1 << 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);
1017 return new CNode<> (bmp, new BasicNode[] { x, y }, gen);
1019 return new CNode<> (bmp, new BasicNode[] { y, x }, gen);
1023 return new LNode<> (x.k, x.v, y.k, y.v);
1029 private static class RDCSS_Descriptor<K, V> {
1031 MainNode<K, V> expectedmain;
1033 volatile boolean committed = false;
1035 public RDCSS_Descriptor (final INode<K, V> old, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
1037 this.expectedmain = expectedmain;
1043 private static class Equiv<K> implements Serializable {
1044 private static final long serialVersionUID = 1L;
1046 public boolean equiv (final K k1, final K k2) {
1047 return k1.equals (k2);
1050 static Equiv universal = new Equiv ();
1053 private static interface Hashing<K> extends Serializable {
1054 public int hash (K k);
1057 static class Default<K> implements Hashing<K> {
1058 private static final long serialVersionUID = 1L;
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);
1072 private final Hashing<K> hashingobj;
1073 private final Equiv<K> equalityobj;
1075 Hashing<K> hashing () {
1079 Equiv<K> equality () {
1083 private transient volatile Object root;
1084 private final transient boolean readOnly;
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;
1092 TrieMap (final Object r, final Hashing<K> hashf, final Equiv<K> ef, final boolean readOnly) {
1093 this(hashf, ef, readOnly);
1097 public TrieMap (final Hashing<K> hashf, final Equiv<K> ef) {
1098 this(INode.newRootNode(), hashf, ef, false);
1102 this (new Default<K> (), Equiv.universal);
1105 /* internal methods */
1107 // private void writeObject(java.io.ObjectOutputStream out) {
1108 // out.writeObject(hashf);
1109 // out.writeObject(ef);
1111 // Iterator it = iterator();
1112 // while (it.hasNext) {
1113 // val (k, v) = it.next();
1114 // out.writeObject(k);
1115 // out.writeObject(v);
1117 // out.writeObject(TrieMapSerializationEnd);
1120 // private TrieMap readObject(java.io.ObjectInputStream in) {
1121 // root = INode.newRootNode();
1122 // rootupdater = AtomicReferenceFieldUpdater.newUpdater(TrieMap.class,
1123 // Object.class, "root");
1125 // hashingobj = in.readObject();
1126 // equalityobj = in.readObject();
1128 // Object obj = null;
1130 // obj = in.readObject();
1131 // if (obj != TrieMapSerializationEnd) {
1133 // V = (V)in.readObject();
1136 // } while (obj != TrieMapSerializationEnd);
1139 final boolean CAS_ROOT (final Object ov, final Object nv) {
1141 throw new IllegalStateException("Attempted to modify a read-only snapshot");
1143 return ROOT_UPDATER.compareAndSet (this, ov, nv);
1146 // FIXME: abort = false by default
1147 final INode<K, V> readRoot (final boolean abort) {
1148 return RDCSS_READ_ROOT (abort);
1151 final INode<K, V> readRoot () {
1152 return RDCSS_READ_ROOT (false);
1155 final INode<K, V> RDCSS_READ_ROOT () {
1156 return RDCSS_READ_ROOT (false);
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);
1166 throw new RuntimeException ("Should not happen");
1169 private final INode<K, V> RDCSS_Complete (final boolean abort) {
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;
1181 if (CAS_ROOT (desc, ov)) {
1184 // return RDCSS_Complete (abort);
1189 MainNode<K, V> oldmain = ov.gcasRead (this);
1190 if (oldmain == exp) {
1191 if (CAS_ROOT (desc, nv)) {
1192 desc.committed = true;
1195 // return RDCSS_Complete (abort);
1200 if (CAS_ROOT (desc, ov)) {
1203 // return RDCSS_Complete (abort);
1212 throw new RuntimeException ("Should not happen");
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;
1226 private void inserthc (final K k, final int hc, final V v) {
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);
1238 private Option<V> insertifhc (final K k, final int hc, final V v, final Object cond) {
1240 INode<K, V> r = RDCSS_READ_ROOT ();
1242 Option<V> ret = r.rec_insertif (k, v, hc, cond, 0, null, r.gen, this);
1244 // return insertifhc (k, hc, v, cond);
1253 private Object lookuphc (final K k, final int hc) {
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);
1267 private Option<V> removehc (final K k, final V v, final int hc) {
1269 INode<K, V> r = RDCSS_READ_ROOT ();
1270 Option<V> res = r.rec_remove (k, v, hc, 0, null, r.gen, this);
1274 // return removehc (k, v, hc);
1282 * Ensure this instance is read-write, throw UnsupportedOperationException
1283 * otherwise. Used by Map-type methods for quick check.
1285 private void ensureReadWrite() {
1287 throw new UnsupportedOperationException("Attempted to modify a read-only view");
1291 public String string () {
1292 // RDCSS_READ_ROOT().string(0);
1296 /* public methods */
1298 // public Seq<V> seq() {
1302 // override def par = new ParTrieMap(this)
1304 // static TrieMap empty() {
1305 // return new TrieMap();
1308 final boolean isReadOnly () {
1312 final boolean nonReadOnly () {
1317 * Returns a snapshot of this TrieMap. This operation is lock-free and
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.
1327 final public TrieMap<K, V> snapshot () {
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);
1334 // return snapshot ();
1342 * Returns a read-only snapshot of this TrieMap. This operation is lock-free
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.
1352 * This method is used by other methods such as `size` and `iterator`.
1354 final public TrieMap<K, V> readOnlySnapshot () {
1355 // Is it a snapshot of a read-only snapshot?
1356 if(!nonReadOnly ()) {
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);
1366 // return readOnlySnapshot ();
1373 final public void clear () {
1375 INode<K, V> r = RDCSS_READ_ROOT ();
1376 if (!RDCSS_ROOT (r, r.gcasRead (this), INode.<K, V>newRootNode ())) {
1385 int computeHash (final K k) {
1386 return hashingobj.hash (k);
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) {
1402 final V apply (final K k) {
1403 int hc = computeHash (k);
1404 Object res = lookuphc (k, hc);
1406 throw new NoSuchElementException ();
1412 // final public Option<V> get (K k) {
1413 // int hc = computeHash (k);
1414 // return Option.makeOption ((V)lookuphc (k, hc));
1418 final public V get (final Object k) {
1419 return lookup((K)k);
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);
1428 final public V put (final Object key, final Object value) {
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;
1440 final public void update (final K k, final V v) {
1441 int hc = computeHash (k);
1442 inserthc (k, hc, v);
1445 final public TrieMap<K, V> add (final K k, final V v) {
1450 final Option<V> removeOpt (final K k) {
1451 int hc = computeHash (k);
1452 return removehc (k, (V) null, hc);
1456 final public V remove (final Object k) {
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;
1468 // final public TrieMap<K, V> remove (Object k) {
1469 // removeOpt ((K)k);
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);
1479 final public V putIfAbsent (final Object k, final Object v) {
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;
1492 public boolean remove (final Object k, final Object v) {
1494 int hc = computeHash ((K)k);
1495 return removehc ((K)k, (V)v, hc).nonEmpty ();
1499 public boolean replace (final K k, final V oldvalue, final V newvalue) {
1501 int hc = computeHash (k);
1502 return insertifhc (k, hc, newvalue, oldvalue).nonEmpty ();
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);
1511 public V replace (final Object k, final Object v) {
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;
1524 * Return an iterator over a TrieMap.
1526 * If this is a read-only snapshot, it would return a read-only iterator.
1528 * If it is the original TrieMap or a non-readonly snapshot, it would return
1529 * an iterator that would allow for updates.
1533 public Iterator<Map.Entry<K, V>> iterator () {
1534 if (!nonReadOnly ()) {
1535 return readOnlySnapshot ().readOnlyIterator ();
1537 return new TrieMapIterator<> (0, this);
1542 * Return an iterator over a TrieMap.
1543 * This is a read-only iterator.
1547 public Iterator<Map.Entry<K, V>> readOnlyIterator () {
1548 if (nonReadOnly ()) {
1549 return readOnlySnapshot ().readOnlyIterator ();
1551 return new TrieMapReadOnlyIterator<> (0, this);
1555 private int cachedSize () {
1556 INode<K, V> r = RDCSS_READ_ROOT ();
1557 return r.cachedSize (this);
1561 public int size () {
1562 if (nonReadOnly ()) {
1563 return readOnlySnapshot ().size ();
1565 return cachedSize ();
1569 String stringPrefix () {
1574 * This iterator is a read-only one and does not allow for any update
1575 * operations on the underlying data structure.
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);
1585 TrieMapReadOnlyIterator (final int level, final TrieMap<K, V> ct) {
1586 this (level, ct, true);
1589 void initialize () {
1590 assert (ct.isReadOnly ());
1591 super.initialize ();
1595 public void remove () {
1596 throw new UnsupportedOperationException ("Operation not supported for read-only iterators");
1600 Map.Entry<K, V> nextEntry(final Map.Entry<K, V> rr) {
1601 // Return non-updatable entry
1606 private static class TrieMapIterator<K, V> implements java.util.Iterator<Map.Entry<K, V>> {
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;
1617 TrieMapIterator (final int level, final TrieMap<K, V> ct, final boolean mustInit) {
1620 this.mustInit = mustInit;
1621 if (this.mustInit) {
1626 TrieMapIterator (final int level, final TrieMap<K, V> ct) {
1627 this (level, ct, true);
1632 public boolean hasNext () {
1633 return (current != null) || (subiter != null);
1637 public Map.Entry<K, V> next () {
1639 Map.Entry<K, V> r = null;
1640 if (subiter != null) {
1641 r = subiter.next ();
1644 r = current.kvPair ();
1649 if(r instanceof Map.Entry) {
1650 final Map.Entry<K, V> rr = r;
1651 return nextEntry(rr);
1655 // return Iterator.empty ().next ();
1660 Map.Entry<K, V> nextEntry(final Map.Entry<K, V> rr) {
1661 return new Map.Entry<K, V>() {
1662 private V updated = null;
1665 public K getKey () {
1666 return rr.getKey ();
1670 public V getValue () {
1671 return (updated == null)?rr.getValue (): updated;
1675 public V setValue (final V value) {
1677 return ct.replace (getKey (), value);
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;
1687 stack [depth] = cn.array;
1688 stackpos [depth] = -1;
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 ();
1695 } else if (m == null) {
1701 private void checkSubiter () {
1702 if (!subiter.hasNext ()) {
1709 void initialize () {
1710 // assert (ct.isReadOnly ());
1711 INode<K, V> r = ct.RDCSS_READ_ROOT ();
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);
1735 protected TrieMapIterator<K, V> newIterator (final int _lev, final TrieMap<K, V> _ct, final boolean _mustInit) {
1736 return new TrieMapIterator<> (_lev, _ct, _mustInit);
1739 protected void dupTo (final TrieMapIterator<K, V> it) {
1740 it.level = this.level;
1742 it.depth = this.depth;
1743 it.current = this.current;
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);
1749 // this one needs to be evaluated
1750 if (this.subiter == null) {
1753 List<Map.Entry<K, V>> lst = toList (this.subiter);
1754 this.subiter = lst.iterator ();
1755 it.subiter = lst.iterator ();
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.
1763 // protected def subdivide(): Seq[Iterator[(K, V)]] = if (subiter ne
1765 // // the case where an LNode is being iterated
1771 // } else if (depth == -1) {
1776 // while (d <= depth) {
1777 // val rem = stack(d).length - 1 - stackpos(d)
1779 // val (arr1, arr2) = stack(d).drop(stackpos(d) + 1).splitAt(rem / 2)
1782 // val it = newIterator(level + 1, ct, false)
1783 // it.stack(0) = arr2
1784 // it.stackpos(0) = -1
1786 // it.advance() // <-- fix it
1788 // return Seq(this, it)
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 ());
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"));
1813 public void remove () {
1814 if (lastReturned != null) {
1815 ct.remove (lastReturned.getKey ());
1816 lastReturned = null;
1818 throw new IllegalStateException();
1824 /** Only used for ctrie serialization. */
1825 // @SerialVersionUID(0L - 7237891413820527142L)
1826 private static long TrieMapSerializationEnd = 0L - 7237891413820527142L;
1830 public boolean containsKey (final Object key) {
1831 return lookup ((K) key) != null;
1836 public Set<Map.Entry<K, V>> entrySet () {
1841 * Support for EntrySet operations required by the Map interface
1844 final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
1847 public Iterator<Map.Entry<K, V>> iterator () {
1848 return TrieMap.this.iterator ();
1852 public final boolean contains (final Object o) {
1853 if (!(o instanceof Map.Entry)) {
1856 final Map.Entry<K, V> e = (Map.Entry<K, V>) o;
1857 final K k = e.getKey ();
1858 final V v = lookup (k);
1863 public final boolean remove (final Object o) {
1864 if (!(o instanceof Map.Entry)) {
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);
1873 public final int size () {
1875 for (final Iterator<?> i = iterator (); i.hasNext (); i.next ()) {
1882 public final void clear () {
1883 TrieMap.this.clear ();
1887 private void readObject(final ObjectInputStream inputStream) throws IOException, ClassNotFoundException {
1888 inputStream.defaultReadObject();
1889 this.root = INode.newRootNode();
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();
1899 // Propagate the read-only bit
1901 READONLY_FIELD.setBoolean(this, ro);
1902 } catch (IllegalAccessException e) {
1903 throw new IOException("Failed to set read-only flag", e);
1907 private void writeObject(final ObjectOutputStream outputStream) throws IOException {
1908 outputStream.defaultWriteObject();
1910 final Map<K, V> ro = readOnlySnapshot();
1911 outputStream.writeBoolean(isReadOnly());
1912 outputStream.writeInt(ro.size());
1914 for (Entry<K, V> e : ro.entrySet()) {
1915 outputStream.writeObject(e.getKey());
1916 outputStream.writeObject(e.getValue());