--- /dev/null
+package com.romix.scala.collection.concurrent;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+import java.lang.reflect.Field;
+import java.util.AbstractMap;
+import java.util.AbstractSet;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.concurrent.ConcurrentMap;
+import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
+import com.romix.scala.None;
+import com.romix.scala.Option;
+import com.romix.scala.Some;
+
+/***
+ * This is a port of Scala's TrieMap class from the Scala Collections library.
+ *
+ * @author Roman Levenstein <romixlev@gmail.com>
+ *
+ * @param <K>
+ * @param <V>
+ */
+@SuppressWarnings({"unchecked", "rawtypes", "unused"})
+public class TrieMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K,V>, Serializable {
+ private static final AtomicReferenceFieldUpdater<TrieMap, Object> ROOT_UPDATER = AtomicReferenceFieldUpdater.newUpdater(TrieMap.class, Object.class, "root");
+ private static final long serialVersionUID = 1L;
+ private static final Field READONLY_FIELD;
+ private static final TrieMap EMPTY = new TrieMap();
+
+ static {
+ final Field f;
+ try {
+ f = TrieMap.class.getDeclaredField("readOnly");
+ } catch (NoSuchFieldException e) {
+ throw new ExceptionInInitializerError(e);
+ } catch (SecurityException e) {
+ throw new ExceptionInInitializerError(e);
+ }
+ f.setAccessible(true);
+ READONLY_FIELD = f;
+ }
+
+ /**
+ * EntrySet
+ */
+ private transient final EntrySet entrySet = new EntrySet ();
+
+ public static <K,V> TrieMap<K,V> empty () {
+ return EMPTY;
+ }
+
+ // static class MangledHashing<K> extends Hashing<K> {
+ // int hash(K k) {
+ // return util.hashing.byteswap32(k);
+ // }
+ // }
+
+ static class INode<K, V> extends INodeBase<K, V> {
+ static final Object KEY_PRESENT = new Object ();
+ static final Object KEY_ABSENT = new Object ();
+
+ static <K,V> INode<K,V> newRootNode () {
+ Gen gen = new Gen ();
+ CNode<K, V> cn = new CNode<K, V> (0, new BasicNode[] {}, gen);
+ return new INode<K,V>(cn, gen);
+ }
+
+ public INode (MainNode<K, V> bn, Gen g) {
+ super (g);
+ WRITE (bn);
+ }
+
+ public INode (Gen g) {
+ this (null, g);
+ }
+
+ final void WRITE (final MainNode<K, V> nval) {
+ INodeBase.updater.set (this, nval);
+ }
+
+ final boolean CAS (final MainNode<K, V> old, final MainNode<K, V> n) {
+ return INodeBase.updater.compareAndSet (this, old, n);
+ }
+
+ final MainNode<K, V> gcasRead (final TrieMap<K, V> ct) {
+ return GCAS_READ (ct);
+ }
+
+ final MainNode<K, V> GCAS_READ (TrieMap<K, V> ct) {
+ MainNode<K, V> m = /* READ */mainnode;
+ MainNode<K, V> prevval = /* READ */m.prev;
+ if (prevval == null)
+ return m;
+ else
+ return GCAS_Complete (m, ct);
+ }
+
+ private MainNode<K, V> GCAS_Complete (MainNode<K, V> m, final TrieMap<K, V> ct) {
+ while (true) {
+ if (m == null)
+ return null;
+ else {
+ // complete the GCAS
+ MainNode<K, V> prev = /* READ */m.prev;
+ INode<K, V> ctr = ct.readRoot (true);
+
+ if (prev == null)
+ return m;
+
+ if (prev instanceof FailedNode) {
+ // try to commit to previous value
+ FailedNode<K, V> fn = (FailedNode<K, V>) prev;
+ if (CAS (m, fn.prev))
+ return fn.prev;
+ else {
+ // Tailrec
+ // return GCAS_Complete (/* READ */mainnode, ct);
+ m = /* READ */mainnode;
+ continue;
+ }
+ } else if (prev instanceof MainNode) {
+ // Assume that you've read the root from the generation
+ // G.
+ // Assume that the snapshot algorithm is correct.
+ // ==> you can only reach nodes in generations <= G.
+ // ==> `gen` is <= G.
+ // We know that `ctr.gen` is >= G.
+ // ==> if `ctr.gen` = `gen` then they are both equal to
+ // G.
+ // ==> otherwise, we know that either `ctr.gen` > G,
+ // `gen` <
+ // G,
+ // or both
+ if ((ctr.gen == gen) && ct.nonReadOnly ()) {
+ // try to commit
+ if (m.CAS_PREV (prev, null))
+ return m;
+ else {
+ // return GCAS_Complete (m, ct);
+ // tailrec
+ continue;
+ }
+ } else {
+ // try to abort
+ m.CAS_PREV (prev, new FailedNode<K, V> (prev));
+ return GCAS_Complete (/* READ */mainnode, ct);
+ }
+ }
+ }
+ throw new RuntimeException ("Should not happen");
+ }
+ }
+
+ final boolean GCAS (final MainNode<K, V> old, final MainNode<K, V> n, final TrieMap<K, V> ct) {
+ n.WRITE_PREV (old);
+ if (CAS (old, n)) {
+ GCAS_Complete (n, ct);
+ return /* READ */n.prev == null;
+ } else
+ return false;
+ }
+
+ private boolean equal (final K k1, final K k2, final TrieMap<K, V> ct) {
+ return ct.equality ().equiv (k1, k2);
+ }
+
+ private INode<K, V> inode (final MainNode<K, V> cn) {
+ INode<K, V> nin = new INode<K, V> (gen);
+ nin.WRITE (cn);
+ return nin;
+ }
+
+ final INode<K, V> copyToGen (final Gen ngen, final TrieMap<K, V> ct) {
+ INode<K, V> nin = new INode<K, V> (ngen);
+ MainNode<K, V> main = GCAS_READ (ct);
+ nin.WRITE (main);
+ return nin;
+ }
+
+ /**
+ * Inserts a key value pair, overwriting the old pair if the keys match.
+ *
+ * @return true if successful, false otherwise
+ */
+ 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) {
+ while (true) {
+ MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
+
+ if (m instanceof CNode) {
+ // 1) a multiway node
+ CNode<K, V> cn = (CNode<K, V>) m;
+ int idx = (hc >>> lev) & 0x1f;
+ int flag = 1 << idx;
+ int bmp = cn.bitmap;
+ int mask = flag - 1;
+ int pos = Integer.bitCount (bmp & mask);
+ if ((bmp & flag) != 0) {
+ // 1a) insert below
+ BasicNode cnAtPos = cn.array [pos];
+ if (cnAtPos instanceof INode) {
+ INode<K, V> in = (INode<K, V>) cnAtPos;
+ if (startgen == in.gen)
+ return in.rec_insert (k, v, hc, lev + 5, this, startgen, ct);
+ else {
+ if (GCAS (cn, cn.renewed (startgen, ct), ct)) {
+ // return rec_insert (k, v, hc, lev, parent,
+ // startgen, ct);
+ // tailrec
+ continue;
+ } else
+ return false;
+ }
+ } else if (cnAtPos instanceof SNode) {
+ SNode<K, V> sn = (SNode<K, V>) cnAtPos;
+ if (sn.hc == hc && equal ((K) sn.k, k, ct))
+ return GCAS (cn, cn.updatedAt (pos, new SNode<K, V> (k, v, hc), gen), ct);
+ else {
+ CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
+ MainNode<K, V> nn = rn.updatedAt (pos, inode (CNode.dual (sn, sn.hc, new SNode (k, v, hc), hc, lev + 5, gen)), gen);
+ return GCAS (cn, nn, ct);
+ }
+ }
+ } else {
+ CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
+ MainNode<K, V> ncnode = rn.insertedAt (pos, flag, new SNode<K, V> (k, v, hc), gen);
+ return GCAS (cn, ncnode, ct);
+ }
+ } else if (m instanceof TNode) {
+ clean (parent, ct, lev - 5);
+ return false;
+ } else if (m instanceof LNode) {
+ LNode<K, V> ln = (LNode<K, V>) m;
+ MainNode<K, V> nn = ln.inserted (k, v);
+ return GCAS (ln, nn, ct);
+ }
+
+ throw new RuntimeException ("Should not happen");
+ }
+ }
+
+ /**
+ * Inserts a new key value pair, given that a specific condition is met.
+ *
+ * @param cond
+ * null - don't care if the key was there
+ * KEY_ABSENT - key wasn't there
+ * KEY_PRESENT - key was there
+ * other value `v` - key must be bound to `v`
+ * @return null if unsuccessful, Option[V] otherwise (indicating
+ * previous value bound to the key)
+ */
+ 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) {
+ while (true) {
+ MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
+
+ if (m instanceof CNode) {
+ // 1) a multiway node
+ CNode<K, V> cn = (CNode<K, V>) m;
+ int idx = (hc >>> lev) & 0x1f;
+ int flag = 1 << idx;
+ int bmp = cn.bitmap;
+ int mask = flag - 1;
+ int pos = Integer.bitCount (bmp & mask);
+
+ if ((bmp & flag) != 0) {
+ // 1a) insert below
+ BasicNode cnAtPos = cn.array [pos];
+ if (cnAtPos instanceof INode) {
+ INode<K, V> in = (INode<K, V>) cnAtPos;
+ if (startgen == in.gen)
+ return in.rec_insertif (k, v, hc, cond, lev + 5, this, startgen, ct);
+ else {
+ if (GCAS (cn, cn.renewed (startgen, ct), ct)) {
+ // return rec_insertif (k, v, hc, cond, lev,
+ // parent, startgen, ct);
+ // tailrec
+ continue;
+ } else
+ return null;
+ }
+ } else if (cnAtPos instanceof SNode) {
+ SNode<K, V> sn = (SNode<K, V>) cnAtPos;
+ if (cond == null) {
+ if (sn.hc == hc && equal (sn.k, k, ct)) {
+ if (GCAS (cn, cn.updatedAt (pos, new SNode<K, V> (k, v, hc), gen), ct))
+ return Option.makeOption(sn.v);
+ else
+ return null;
+ } else {
+ CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
+ MainNode<K, V> nn = rn.updatedAt (pos, inode (CNode.dual (sn, sn.hc, new SNode (k, v, hc), hc, lev + 5, gen)), gen);
+ if (GCAS (cn, nn, ct))
+ return Option.makeOption(); // None;
+ else
+ return null;
+ }
+
+ } else if (cond == INode.KEY_ABSENT) {
+ if (sn.hc == hc && equal (sn.k, k, ct))
+ return Option.makeOption(sn.v);
+ else {
+ CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
+ MainNode<K, V> nn = rn.updatedAt (pos, inode (CNode.dual (sn, sn.hc, new SNode (k, v, hc), hc, lev + 5, gen)), gen);
+ if (GCAS (cn, nn, ct))
+ return Option.makeOption (); // None
+ else
+ return null;
+ }
+ } else if (cond == INode.KEY_PRESENT) {
+ if (sn.hc == hc && equal (sn.k, k, ct)) {
+ if (GCAS (cn, cn.updatedAt (pos, new SNode<K, V> (k, v, hc), gen), ct))
+ return Option.makeOption (sn.v);
+ else
+ return null;
+
+ } else
+ return Option.makeOption ();// None;
+ } else {
+ if (sn.hc == hc && equal (sn.k, k, ct) && sn.v == cond) {
+ if (GCAS (cn, cn.updatedAt (pos, new SNode<K, V> (k, v, hc), gen), ct))
+ return Option.makeOption (sn.v);
+ else
+ return null;
+ } else
+ return Option.makeOption (); // None
+ }
+
+ }
+ } else if (cond == null || cond == INode.KEY_ABSENT) {
+ CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed (gen, ct);
+ CNode<K, V> ncnode = rn.insertedAt (pos, flag, new SNode<K, V> (k, v, hc), gen);
+ if (GCAS (cn, ncnode, ct))
+ return Option.makeOption ();// None
+ else
+ return null;
+ } else if (cond == INode.KEY_PRESENT) {
+ return Option.makeOption ();// None;
+ } else
+ return Option.makeOption (); // None
+ } else if (m instanceof TNode) {
+ clean (parent, ct, lev - 5);
+ return null;
+ } else if (m instanceof LNode) {
+ // 3) an l-node
+ LNode<K, V> ln = (LNode<K, V>) m;
+ if (cond == null) {
+ Option<V> optv = ln.get (k);
+ if (insertln (ln, k, v, ct))
+ return optv;
+ else
+ return null;
+ } else if (cond == INode.KEY_ABSENT) {
+ Option<V> t = ln.get (k);
+ if (t == null) {
+ if (insertln (ln, k, v, ct))
+ return Option.makeOption ();// None
+ else
+ return null;
+ } else
+ return t;
+ } else if (cond == INode.KEY_PRESENT) {
+ Option<V> t = ln.get (k);
+ if (t != null) {
+ if (insertln (ln, k, v, ct))
+ return t;
+ else
+ return null;
+ } else
+ return null; // None
+ } else {
+ Option<V> t = ln.get (k);
+ if (t != null) {
+ if (((Some<V>) t).get () == cond) {
+ if (insertln (ln, k, v, ct))
+ return new Some<V> ((V) cond);
+ else
+ return null;
+
+ } else
+ return Option.makeOption ();
+ }
+ }
+ }
+
+// throw new RuntimeException ("Should not happen");
+ }
+ }
+
+ final boolean insertln (final LNode<K, V> ln, final K k, final V v, final TrieMap<K, V> ct) {
+ LNode<K, V> nn = ln.inserted (k, v);
+ return GCAS (ln, nn, ct);
+ }
+
+ /**
+ * Looks up the value associated with the key.
+ *
+ * @return null if no value has been found, RESTART if the operation
+ * wasn't successful, or any other value otherwise
+ */
+ final Object rec_lookup (final K k, final int hc, int lev, INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
+ while (true) {
+ MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
+
+ if (m instanceof CNode) {
+ // 1) a multinode
+ final CNode<K, V> cn = (CNode<K, V>) m;
+ int idx = (hc >>> lev) & 0x1f;
+ int flag = 1 << idx;
+ int bmp = cn.bitmap;
+ if ((bmp & flag) == 0)
+ return null; // 1a) bitmap shows no binding
+ else { // 1b) bitmap contains a value - descend
+ int pos = (bmp == 0xffffffff) ? idx : Integer.bitCount (bmp & (flag - 1));
+ final BasicNode sub = cn.array [pos];
+ if (sub instanceof INode) {
+ INode<K, V> in = (INode<K, V>) sub;
+ if (ct.isReadOnly () || (startgen == ((INodeBase<K, V>) sub).gen))
+ return in.rec_lookup (k, hc, lev + 5, this, startgen, ct);
+ else {
+ if (GCAS (cn, cn.renewed (startgen, ct), ct)) {
+ // return rec_lookup (k, hc, lev, parent,
+ // startgen, ct);
+ // Tailrec
+ continue;
+ } else
+ return RESTART; // used to be throw
+ // RestartException
+ }
+ } else if (sub instanceof SNode) {
+ // 2) singleton node
+ SNode<K, V> sn = (SNode<K, V>) sub;
+ if (((SNode) sub).hc == hc && equal (sn.k, k, ct))
+ return sn.v;
+ else
+ return null;
+ }
+ }
+ } else if (m instanceof TNode) {
+ // 3) non-live node
+ return cleanReadOnly ((TNode<K, V>) m, lev, parent, ct, k, hc);
+ } else if (m instanceof LNode) {
+ // 5) an l-node
+ Option<V> tmp = ((LNode<K, V>) m).get (k);
+ return (tmp instanceof Option) ? ((Option<V>) tmp) : null;
+ }
+
+ throw new RuntimeException ("Should not happen");
+ }
+ }
+
+ private Object cleanReadOnly (final TNode<K, V> tn, final int lev, final INode<K, V> parent, final TrieMap<K, V> ct, K k, int hc) {
+ if (ct.nonReadOnly ()) {
+ clean (parent, ct, lev - 5);
+ return RESTART; // used to be throw RestartException
+ } else {
+ if (tn.hc == hc && equal(tn.k, k, ct))
+ return tn.v;
+ else
+ return null;
+ }
+ }
+
+ /**
+ * Removes the key associated with the given value.
+ *
+ * @param v
+ * if null, will remove the key irregardless of the value;
+ * otherwise removes only if binding contains that exact key
+ * and value
+ * @return null if not successful, an Option[V] indicating the previous
+ * value otherwise
+ */
+ final Option<V> rec_remove (K k, V v, int hc, int lev, final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
+ MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
+
+ if (m instanceof CNode) {
+ CNode<K, V> cn = (CNode<K, V>) m;
+ int idx = (hc >>> lev) & 0x1f;
+ int bmp = cn.bitmap;
+ int flag = 1 << idx;
+ if ((bmp & flag) == 0)
+ return Option.makeOption ();
+ else {
+ int pos = Integer.bitCount (bmp & (flag - 1));
+ BasicNode sub = cn.array [pos];
+ Option<V> res = null;
+ if (sub instanceof INode) {
+ INode<K, V> in = (INode<K, V>) sub;
+ if (startgen == in.gen)
+ res = in.rec_remove (k, v, hc, lev + 5, this, startgen, ct);
+ else {
+ if (GCAS (cn, cn.renewed (startgen, ct), ct))
+ res = rec_remove (k, v, hc, lev, parent, startgen, ct);
+ else
+ res = null;
+ }
+
+ } else if (sub instanceof SNode) {
+ SNode<K, V> sn = (SNode<K, V>) sub;
+ if (sn.hc == hc && equal (sn.k, k, ct) && (v == null || v.equals(sn.v))) {
+ MainNode<K, V> ncn = cn.removedAt (pos, flag, gen).toContracted (lev);
+ if (GCAS (cn, ncn, ct))
+ res = Option.makeOption (sn.v);
+ else
+ res = null;
+ } else
+ res = Option.makeOption ();
+ }
+
+ if (res instanceof None || (res == null))
+ return res;
+ else {
+ if (parent != null) { // never tomb at root
+ MainNode<K, V> n = GCAS_READ (ct);
+ if (n instanceof TNode)
+ cleanParent (n, parent, ct, hc, lev, startgen);
+ }
+
+ return res;
+ }
+ }
+ } else if (m instanceof TNode) {
+ clean (parent, ct, lev - 5);
+ return null;
+ } else if (m instanceof LNode) {
+ LNode<K, V> ln = (LNode<K, V>) m;
+ if (v == null) {
+ Option<V> optv = ln.get (k);
+ MainNode<K, V> nn = ln.removed (k, ct);
+ if (GCAS (ln, nn, ct))
+ return optv;
+ else
+ return null;
+ } else {
+ Option<V> tmp = ln.get (k);
+ if (tmp instanceof Some) {
+ Some<V> tmp1 = (Some<V>) tmp;
+ if (tmp1.get () == v) {
+ MainNode<K, V> nn = ln.removed (k, ct);
+ if (GCAS (ln, nn, ct))
+ return tmp;
+ else
+ return null;
+ }
+ }
+ }
+ }
+ throw new RuntimeException ("Should not happen");
+ }
+
+ void cleanParent (final Object nonlive, final INode<K, V> parent, final TrieMap<K, V> ct, final int hc, final int lev, final Gen startgen) {
+ while (true) {
+ MainNode<K, V> pm = parent.GCAS_READ (ct);
+ if (pm instanceof CNode) {
+ CNode<K, V> cn = (CNode<K, V>) pm;
+ int idx = (hc >>> (lev - 5)) & 0x1f;
+ int bmp = cn.bitmap;
+ int flag = 1 << idx;
+ if ((bmp & flag) == 0) {
+ } // somebody already removed this i-node, we're done
+ else {
+ int pos = Integer.bitCount (bmp & (flag - 1));
+ BasicNode sub = cn.array [pos];
+ if (sub == this) {
+ if (nonlive instanceof TNode) {
+ TNode<K, V> tn = (TNode<K, V>) nonlive;
+ MainNode<K, V> ncn = cn.updatedAt (pos, tn.copyUntombed (), gen).toContracted (lev - 5);
+ if (!parent.GCAS (cn, ncn, ct))
+ if (ct.readRoot ().gen == startgen) {
+ // cleanParent (nonlive, parent, ct, hc,
+ // lev, startgen);
+ // tailrec
+ continue;
+ }
+ }
+ }
+ }
+ } else {
+ // parent is no longer a cnode, we're done
+ }
+ break;
+ }
+ }
+
+ private void clean (final INode<K, V> nd, final TrieMap<K, V> ct, int lev) {
+ MainNode<K, V> m = nd.GCAS_READ (ct);
+ if (m instanceof CNode) {
+ CNode<K, V> cn = (CNode<K, V>) m;
+ nd.GCAS (cn, cn.toCompressed (ct, lev, gen), ct);
+ }
+ }
+
+ final boolean isNullInode (final TrieMap<K, V> ct) {
+ return GCAS_READ (ct) == null;
+ }
+
+ final int cachedSize (final TrieMap<K, V> ct) {
+ MainNode<K, V> m = GCAS_READ (ct);
+ return m.cachedSize (ct);
+ }
+
+ // /* this is a quiescent method! */
+ // def string(lev: Int) = "%sINode -> %s".format(" " * lev, mainnode
+ // match {
+ // case null => "<null>"
+ // case tn: TNode[_, _] => "TNode(%s, %s, %d, !)".format(tn.k, tn.v,
+ // tn.hc)
+ // case cn: CNode[_, _] => cn.string(lev)
+ // case ln: LNode[_, _] => ln.string(lev)
+ // case x => "<elem: %s>".format(x)
+ // })
+
+ public String string (int lev) {
+ return "INode";
+ }
+
+ }
+
+ private static final class FailedNode<K, V> extends MainNode<K, V> {
+ MainNode<K, V> p;
+
+ FailedNode (final MainNode<K, V> p) {
+ this.p = p;
+ WRITE_PREV (p);
+ }
+
+ public String string (int lev) {
+ throw new UnsupportedOperationException ();
+ }
+
+ public int cachedSize (Object ct) {
+ throw new UnsupportedOperationException ();
+ }
+
+ public String toString () {
+ return String.format ("FailedNode(%s)", p);
+ }
+ }
+
+ private interface KVNode<K, V> {
+ Map.Entry<K, V> kvPair ();
+ }
+
+ private static final class SNode<K, V> extends BasicNode implements KVNode<K, V> {
+ final K k;
+ final V v;
+ final int hc;
+
+ SNode (final K k, final V v, final int hc) {
+ this.k = k;
+ this.v = v;
+ this.hc = hc;
+ }
+
+ final SNode<K, V> copy() {
+ return new SNode<K, V> (k, v, hc);
+ }
+
+ final TNode<K, V> copyTombed () {
+ return new TNode<K, V> (k, v, hc);
+ }
+
+ final SNode<K, V> copyUntombed () {
+ return new SNode<K, V> (k, v, hc);
+ }
+
+ final public Map.Entry<K, V> kvPair () {
+ return new Pair<K, V> (k, v);
+ }
+
+ final public String string (int lev) {
+ // (" " * lev) + "SNode(%s, %s, %x)".format(k, v, hc);
+ return "SNode";
+ }
+ }
+
+ private static final class TNode<K, V> extends MainNode<K, V> implements KVNode<K, V> {
+ final K k;
+ final V v;
+ final int hc;
+
+ TNode (final K k, final V v, final int hc) {
+ this.k = k;
+ this.v = v;
+ this.hc = hc;
+ }
+
+ final TNode<K, V> copy () {
+ return new TNode<K, V> (k, v, hc);
+ }
+
+ final TNode<K, V> copyTombed () {
+ return new TNode<K, V> (k, v, hc);
+ }
+
+ final SNode<K, V> copyUntombed () {
+ return new SNode<K, V> (k, v, hc);
+ }
+
+ final public Pair<K, V> kvPair () {
+ return new Pair<K, V> (k, v);
+ }
+
+ final public int cachedSize (Object ct) {
+ return 1;
+ }
+
+ final public String string (int lev) {
+ // (" " * lev) + "TNode(%s, %s, %x, !)".format(k, v, hc);
+ return "TNode";
+ }
+ }
+
+ private final static class LNode<K, V> extends MainNode<K, V> {
+ final ListMap<K, V> listmap;
+
+ public LNode (final ListMap<K, V> listmap) {
+ this.listmap = listmap;
+ }
+
+ public LNode(K k, V v) {
+ this (ListMap.map (k, v));
+ }
+
+ public LNode (K k1, V v1, K k2, V v2) {
+ this (ListMap.map (k1, v1, k2, v2));
+ }
+
+ LNode<K, V> inserted (K k, V v) {
+ return new LNode<K, V> (listmap.add (k, v));
+ }
+
+ MainNode<K, V> removed (K k, final TrieMap<K, V> ct) {
+ ListMap<K, V> updmap = listmap.remove (k);
+ if (updmap.size () > 1)
+ return new LNode<K, V> (updmap);
+ else {
+ Entry<K, V> kv = updmap.iterator ().next ();
+ // create it tombed so that it gets compressed on subsequent
+ // accesses
+ return new TNode<K, V> (kv.getKey (), kv.getValue (), ct.computeHash (kv.getKey ()));
+ }
+ }
+
+ Option<V> get (K k) {
+ return listmap.get (k);
+ }
+
+ public int cachedSize (Object ct) {
+ return listmap.size ();
+ }
+
+ public String string (int lev) {
+ // (" " * lev) + "LNode(%s)".format(listmap.mkString(", "))
+ return "LNode";
+ }
+ }
+
+ private static final class CNode<K, V> extends CNodeBase<K, V> {
+
+ final int bitmap;
+ final BasicNode[] array;
+ final Gen gen;
+
+ CNode (final int bitmap, final BasicNode[] array, final Gen gen) {
+ this.bitmap = bitmap;
+ this.array = array;
+ this.gen = gen;
+ }
+
+ // this should only be called from within read-only snapshots
+ final public int cachedSize (Object ct) {
+ int currsz = READ_SIZE ();
+ if (currsz != -1)
+ return currsz;
+ else {
+ int sz = computeSize ((TrieMap<K, V>) ct);
+ while (READ_SIZE () == -1)
+ CAS_SIZE (-1, sz);
+ return READ_SIZE ();
+ }
+ }
+
+ // lends itself towards being parallelizable by choosing
+ // a random starting offset in the array
+ // => if there are concurrent size computations, they start
+ // at different positions, so they are more likely to
+ // to be independent
+ private int computeSize (final TrieMap<K, V> ct) {
+ int i = 0;
+ int sz = 0;
+ // final int offset = (array.length > 0) ?
+ // // util.Random.nextInt(array.length) /* <-- benchmarks show that
+ // // this causes observable contention */
+ // scala.concurrent.forkjoin.ThreadLocalRandom.current.nextInt (0,
+ // array.length)
+ // : 0;
+
+ final int offset = 0;
+ while (i < array.length) {
+ int pos = (i + offset) % array.length;
+ BasicNode elem = array [pos];
+ if (elem instanceof SNode)
+ sz += 1;
+ else if (elem instanceof INode)
+ sz += ((INode<K, V>) elem).cachedSize (ct);
+ i += 1;
+ }
+ return sz;
+ }
+
+ final CNode<K, V> updatedAt (int pos, final BasicNode nn, final Gen gen) {
+ int len = array.length;
+ BasicNode[] narr = new BasicNode[len];
+ System.arraycopy (array, 0, narr, 0, len);
+ narr [pos] = nn;
+ return new CNode<K, V> (bitmap, narr, gen);
+ }
+
+ final CNode<K, V> removedAt (int pos, int flag, final Gen gen) {
+ BasicNode[] arr = array;
+ int len = arr.length;
+ BasicNode[] narr = new BasicNode[len - 1];
+ System.arraycopy (arr, 0, narr, 0, pos);
+ System.arraycopy (arr, pos + 1, narr, pos, len - pos - 1);
+ return new CNode<K, V> (bitmap ^ flag, narr, gen);
+ }
+
+ final CNode<K, V> insertedAt (int pos, int flag, final BasicNode nn, final Gen gen) {
+ int len = array.length;
+ int bmp = bitmap;
+ BasicNode[] narr = new BasicNode[len + 1];
+ System.arraycopy (array, 0, narr, 0, pos);
+ narr [pos] = nn;
+ System.arraycopy (array, pos, narr, pos + 1, len - pos);
+ return new CNode<K, V> (bmp | flag, narr, gen);
+ }
+
+ /**
+ * Returns a copy of this cnode such that all the i-nodes below it are
+ * copied to the specified generation `ngen`.
+ */
+ final CNode<K, V> renewed (final Gen ngen, final TrieMap<K, V> ct) {
+ int i = 0;
+ BasicNode[] arr = array;
+ int len = arr.length;
+ BasicNode[] narr = new BasicNode[len];
+ while (i < len) {
+ BasicNode elem = arr [i];
+ if (elem instanceof INode) {
+ INode<K, V> in = (INode<K, V>) elem;
+ narr [i] = in.copyToGen (ngen, ct);
+ } else if (elem instanceof BasicNode)
+ narr [i] = elem;
+ i += 1;
+ }
+ return new CNode<K, V> (bitmap, narr, ngen);
+ }
+
+ private BasicNode resurrect (final INode<K, V> inode, final Object inodemain) {
+ if (inodemain instanceof TNode) {
+ TNode<K, V> tn = (TNode<K, V>) inodemain;
+ return tn.copyUntombed ();
+ } else
+ return inode;
+ }
+
+ final MainNode<K, V> toContracted (int lev) {
+ if (array.length == 1 && lev > 0) {
+ if (array [0] instanceof SNode) {
+ SNode<K, V> sn = (SNode<K, V>) array [0];
+ return sn.copyTombed ();
+ } else
+ return this;
+
+ } else
+ return this;
+ }
+
+ // - if the branching factor is 1 for this CNode, and the child
+ // is a tombed SNode, returns its tombed version
+ // - otherwise, if there is at least one non-null node below,
+ // returns the version of this node with at least some null-inodes
+ // removed (those existing when the op began)
+ // - if there are only null-i-nodes below, returns null
+ final MainNode<K, V> toCompressed (final TrieMap<K, V> ct, int lev, Gen gen) {
+ int bmp = bitmap;
+ int i = 0;
+ BasicNode[] arr = array;
+ BasicNode[] tmparray = new BasicNode[arr.length];
+ while (i < arr.length) { // construct new bitmap
+ BasicNode sub = arr [i];
+ if (sub instanceof INode) {
+ INode<K, V> in = (INode<K, V>) sub;
+ MainNode<K, V> inodemain = in.gcasRead (ct);
+ assert (inodemain != null);
+ tmparray [i] = resurrect (in, inodemain);
+ } else if (sub instanceof SNode) {
+ tmparray [i] = sub;
+ }
+ i += 1;
+ }
+
+ return new CNode<K, V> (bmp, tmparray, gen).toContracted (lev);
+ }
+
+ public String string (int lev) {
+ // "CNode %x\n%s".format(bitmap, array.map(_.string(lev +
+ // 1)).mkString("\n"));
+ return "CNode";
+ }
+
+ /*
+ * quiescently consistent - don't call concurrently to anything
+ * involving a GCAS!!
+ */
+ // protected Seq<K,V> collectElems() {
+ // array flatMap {
+ // case sn: SNode[K, V] => Some(sn.kvPair)
+ // case in: INode[K, V] => in.mainnode match {
+ // case tn: TNode[K, V] => Some(tn.kvPair)
+ // case ln: LNode[K, V] => ln.listmap.toList
+ // case cn: CNode[K, V] => cn.collectElems
+ // }
+ // }
+ // }
+
+ // protected Seq<String> collectLocalElems() {
+ // // array flatMap {
+ // // case sn: SNode[K, V] => Some(sn.kvPair._2.toString)
+ // // case in: INode[K, V] => Some(in.toString.drop(14) + "(" + in.gen +
+ // ")")
+ // // }
+ // return null;
+ // }
+
+ public String toString () {
+ // val elems = collectLocalElems
+ // "CNode(sz: %d; %s)".format(elems.size,
+ // elems.sorted.mkString(", "))
+ return "CNode";
+ }
+
+ static <K, V> MainNode<K,V> dual (final SNode<K, V> x, int xhc, final SNode<K, V> y, int yhc, int lev, Gen gen) {
+ if (lev < 35) {
+ int xidx = (xhc >>> lev) & 0x1f;
+ int yidx = (yhc >>> lev) & 0x1f;
+ int bmp = (1 << xidx) | (1 << yidx);
+
+ if (xidx == yidx) {
+ INode<K, V> subinode = new INode<K, V> (gen);// (TrieMap.inodeupdater)
+ subinode.mainnode = dual (x, xhc, y, yhc, lev + 5, gen);
+ return new CNode<K, V> (bmp, new BasicNode[] { subinode }, gen);
+ } else {
+ if (xidx < yidx)
+ return new CNode<K, V> (bmp, new BasicNode[] { x, y }, gen);
+ else
+ return new CNode<K, V> (bmp, new BasicNode[] { y, x }, gen);
+ }
+ } else {
+ return new LNode<K, V> (x.k, x.v, y.k, y.v);
+ }
+ }
+
+ }
+
+ private static class RDCSS_Descriptor<K, V> {
+ INode<K, V> old;
+ MainNode<K, V> expectedmain;
+ INode<K, V> nv;
+ volatile boolean committed = false;
+
+ public RDCSS_Descriptor (final INode<K, V> old, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
+ this.old = old;
+ this.expectedmain = expectedmain;
+ this.nv = nv;
+ }
+
+ }
+
+ private static class Equiv<K> implements Serializable {
+ private static final long serialVersionUID = 1L;
+
+ public boolean equiv (K k1, K k2) {
+ return k1.equals (k2);
+ }
+
+ static Equiv universal = new Equiv ();
+ }
+
+ private static interface Hashing<K> extends Serializable {
+ public int hash (K k);
+ }
+
+ static class Default<K> implements Hashing<K> {
+ private static final long serialVersionUID = 1L;
+
+ public int hash (K k) {
+ int h = k.hashCode ();
+ // This function ensures that hashCodes that differ only by
+ // constant multiples at each bit position have a bounded
+ // number of collisions (approximately 8 at default load factor).
+ h ^= (h >>> 20) ^ (h >>> 12);
+ h ^= (h >>> 7) ^ (h >>> 4);
+ return h;
+ }
+ }
+
+ private final Hashing<K> hashingobj;
+ private final Equiv<K> equalityobj;
+
+ Hashing<K> hashing () {
+ return hashingobj;
+ }
+
+ Equiv<K> equality () {
+ return equalityobj;
+ }
+
+ private transient volatile Object root;
+ private final transient boolean readOnly;
+
+ TrieMap (final Hashing<K> hashf, final Equiv<K> ef, final boolean readOnly) {
+ this.hashingobj = hashf;
+ this.equalityobj = ef;
+ this.readOnly = readOnly;
+ }
+
+ TrieMap (final Object r, final Hashing<K> hashf, final Equiv<K> ef, boolean readOnly) {
+ this(hashf, ef, readOnly);
+ this.root = r;
+ }
+
+ public TrieMap (final Hashing<K> hashf, final Equiv<K> ef) {
+ this(INode.newRootNode(), hashf, ef, false);
+ }
+
+ public TrieMap () {
+ this (new Default<K> (), Equiv.universal);
+ }
+
+ /* internal methods */
+
+ // private void writeObject(java.io.ObjectOutputStream out) {
+ // out.writeObject(hashf);
+ // out.writeObject(ef);
+ //
+ // Iterator it = iterator();
+ // while (it.hasNext) {
+ // val (k, v) = it.next();
+ // out.writeObject(k);
+ // out.writeObject(v);
+ // }
+ // out.writeObject(TrieMapSerializationEnd);
+ // }
+ //
+ // private TrieMap readObject(java.io.ObjectInputStream in) {
+ // root = INode.newRootNode();
+ // rootupdater = AtomicReferenceFieldUpdater.newUpdater(TrieMap.class,
+ // Object.class, "root");
+ //
+ // hashingobj = in.readObject();
+ // equalityobj = in.readObject();
+ //
+ // Object obj = null;
+ // do {
+ // obj = in.readObject();
+ // if (obj != TrieMapSerializationEnd) {
+ // K k = (K)obj;
+ // V = (V)in.readObject();
+ // update(k, v);
+ // }
+ // } while (obj != TrieMapSerializationEnd);
+ // }
+
+ final boolean CAS_ROOT (Object ov, Object nv) {
+ if (isReadOnly()) {
+ throw new IllegalStateException("Attempted to modify a read-only snapshot");
+ }
+ return ROOT_UPDATER.compareAndSet (this, ov, nv);
+ }
+
+ // FIXME: abort = false by default
+ final INode<K, V> readRoot (boolean abort) {
+ return RDCSS_READ_ROOT (abort);
+ }
+
+ final INode<K, V> readRoot () {
+ return RDCSS_READ_ROOT (false);
+ }
+
+ final INode<K, V> RDCSS_READ_ROOT () {
+ return RDCSS_READ_ROOT (false);
+ }
+
+ final INode<K, V> RDCSS_READ_ROOT (boolean abort) {
+ Object r = /* READ */root;
+ if (r instanceof INode)
+ return (INode<K, V>) r;
+ else if (r instanceof RDCSS_Descriptor) {
+ return RDCSS_Complete (abort);
+ }
+ throw new RuntimeException ("Should not happen");
+ }
+
+ private final INode<K, V> RDCSS_Complete (final boolean abort) {
+ while (true) {
+ Object v = /* READ */root;
+ if (v instanceof INode)
+ return (INode<K, V>) v;
+ else if (v instanceof RDCSS_Descriptor) {
+ RDCSS_Descriptor<K, V> desc = (RDCSS_Descriptor<K, V>) v;
+ INode<K, V> ov = desc.old;
+ MainNode<K, V> exp = desc.expectedmain;
+ INode<K, V> nv = desc.nv;
+
+ if (abort) {
+ if (CAS_ROOT (desc, ov))
+ return ov;
+ else {
+ // return RDCSS_Complete (abort);
+ // tailrec
+ continue;
+ }
+ } else {
+ MainNode<K, V> oldmain = ov.gcasRead (this);
+ if (oldmain == exp) {
+ if (CAS_ROOT (desc, nv)) {
+ desc.committed = true;
+ return nv;
+ } else {
+ // return RDCSS_Complete (abort);
+ // tailrec
+ continue;
+ }
+ } else {
+ if (CAS_ROOT (desc, ov))
+ return ov;
+ else {
+ // return RDCSS_Complete (abort);
+ // tailrec
+ continue;
+
+ }
+ }
+ }
+ }
+
+ throw new RuntimeException ("Should not happen");
+ }
+ }
+
+ private boolean RDCSS_ROOT (final INode<K, V> ov, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
+ RDCSS_Descriptor<K, V> desc = new RDCSS_Descriptor<K, V> (ov, expectedmain, nv);
+ if (CAS_ROOT (ov, desc)) {
+ RDCSS_Complete (false);
+ return /* READ */desc.committed;
+ } else
+ return false;
+ }
+
+ private void inserthc (final K k, final int hc, final V v) {
+ while (true) {
+ INode<K, V> r = RDCSS_READ_ROOT ();
+ if (!r.rec_insert (k, v, hc, 0, null, r.gen, this)) {
+ // inserthc (k, hc, v);
+ // tailrec
+ continue;
+ }
+ break;
+ }
+ }
+
+ private Option<V> insertifhc (final K k, final int hc, final V v, final Object cond) {
+ while (true) {
+ INode<K, V> r = RDCSS_READ_ROOT ();
+
+ Option<V> ret = r.rec_insertif (k, v, hc, cond, 0, null, r.gen, this);
+ if (ret == null) {
+ // return insertifhc (k, hc, v, cond);
+ // tailrec
+ continue;
+ } else
+ return ret;
+ }
+ }
+
+ private Object lookuphc (final K k, final int hc) {
+ while (true) {
+ INode<K, V> r = RDCSS_READ_ROOT ();
+ Object res = r.rec_lookup (k, hc, 0, null, r.gen, this);
+ if (res == INodeBase.RESTART) {
+ // return lookuphc (k, hc);
+ // tailrec
+ continue;
+ } else
+ return res;
+ }
+ }
+
+ private Option<V> removehc (final K k, final V v, final int hc) {
+ while (true) {
+ INode<K, V> r = RDCSS_READ_ROOT ();
+ Option<V> res = r.rec_remove (k, v, hc, 0, null, r.gen, this);
+ if (res != null)
+ return res;
+ else {
+ // return removehc (k, v, hc);
+ // tailrec
+ continue;
+ }
+ }
+ }
+
+ /**
+ * Ensure this instance is read-write, throw UnsupportedOperationException
+ * otherwise. Used by Map-type methods for quick check.
+ */
+ private void ensureReadWrite() {
+ if (isReadOnly()) {
+ throw new UnsupportedOperationException("Attempted to modify a read-only view");
+ }
+ }
+
+ public String string () {
+ // RDCSS_READ_ROOT().string(0);
+ return "Root";
+ }
+
+ /* public methods */
+
+ // public Seq<V> seq() {
+ // return this;
+ // }
+
+ // override def par = new ParTrieMap(this)
+
+ // static TrieMap empty() {
+ // return new TrieMap();
+ // }
+
+ final boolean isReadOnly () {
+ return readOnly;
+ }
+
+ final boolean nonReadOnly () {
+ return !readOnly;
+ }
+
+ /**
+ * Returns a snapshot of this TrieMap. This operation is lock-free and
+ * linearizable.
+ *
+ * The snapshot is lazily updated - the first time some branch in the
+ * snapshot or this TrieMap are accessed, they are rewritten. This means
+ * that the work of rebuilding both the snapshot and this TrieMap is
+ * distributed across all the threads doing updates or accesses subsequent
+ * to the snapshot creation.
+ */
+
+ final public TrieMap<K, V> snapshot () {
+ while (true) {
+ INode<K, V> r = RDCSS_READ_ROOT ();
+ final MainNode<K, V> expmain = r.gcasRead (this);
+ if (RDCSS_ROOT (r, expmain, r.copyToGen (new Gen (), this)))
+ return new TrieMap<K, V> (r.copyToGen (new Gen (), this), hashing (), equality (), readOnly);
+ else {
+ // return snapshot ();
+ // tailrec
+ continue;
+ }
+ }
+ }
+
+ /**
+ * Returns a read-only snapshot of this TrieMap. This operation is lock-free
+ * and linearizable.
+ *
+ * The snapshot is lazily updated - the first time some branch of this
+ * TrieMap are accessed, it is rewritten. The work of creating the snapshot
+ * is thus distributed across subsequent updates and accesses on this
+ * TrieMap by all threads. Note that the snapshot itself is never rewritten
+ * unlike when calling the `snapshot` method, but the obtained snapshot
+ * cannot be modified.
+ *
+ * This method is used by other methods such as `size` and `iterator`.
+ */
+ final public TrieMap<K, V> readOnlySnapshot () {
+ // Is it a snapshot of a read-only snapshot?
+ if(!nonReadOnly ())
+ return this;
+
+ while (true) {
+ INode<K, V> r = RDCSS_READ_ROOT ();
+ MainNode<K, V> expmain = r.gcasRead (this);
+ if (RDCSS_ROOT (r, expmain, r.copyToGen (new Gen (), this)))
+ return new TrieMap<K, V> (r, hashing (), equality (), true);
+ else {
+ // return readOnlySnapshot ();
+ continue;
+ }
+ }
+ }
+
+ final public void clear () {
+ while (true) {
+ INode<K, V> r = RDCSS_READ_ROOT ();
+ if (!RDCSS_ROOT (r, r.gcasRead (this), INode.<K, V>newRootNode ())) {
+ continue;
+ }else{
+ return;
+ }
+ }
+ }
+
+ // @inline
+ int computeHash (K k) {
+ return hashingobj.hash (k);
+ }
+
+ final V lookup (K k) {
+ int hc = computeHash (k);
+// return (V) lookuphc (k, hc);
+ Object o = lookuphc (k, hc);
+ if(o instanceof Some) {
+ return ((Some<V>)o).get ();
+ } else if(o instanceof None)
+ return null;
+ else
+ return (V)o;
+ }
+
+ final V apply (K k) {
+ int hc = computeHash (k);
+ Object res = lookuphc (k, hc);
+ if (res == null)
+ throw new NoSuchElementException ();
+ else
+ return (V) res;
+ }
+
+// final public Option<V> get (K k) {
+// int hc = computeHash (k);
+// return Option.makeOption ((V)lookuphc (k, hc));
+// }
+
+ final public V get (Object k) {
+ return lookup((K)k);
+ }
+
+ final public Option<V> putOpt(Object key, Object value) {
+ int hc = computeHash ((K)key);
+ return insertifhc ((K)key, hc, (V)value, null);
+ }
+
+ @Override
+ final public V put (Object key, Object value) {
+ ensureReadWrite();
+ int hc = computeHash ((K)key);
+ Option<V> ov = insertifhc ((K)key, hc, (V)value, null);
+ if(ov instanceof Some) {
+ Some<V> sv = (Some<V>)ov;
+ return sv.get ();
+ } else
+ return null;
+ }
+
+ final public void update (K k, V v) {
+ int hc = computeHash (k);
+ inserthc (k, hc, v);
+ }
+
+ final public TrieMap<K, V> add (K k, V v) {
+ update (k, v);
+ return this;
+ }
+
+ final Option<V> removeOpt (K k) {
+ int hc = computeHash (k);
+ return removehc (k, (V) null, hc);
+ }
+
+ @Override
+ final public V remove (Object k) {
+ ensureReadWrite();
+ int hc = computeHash ((K)k);
+ Option<V> ov = removehc ((K)k, (V) null, hc);
+ if(ov instanceof Some) {
+ Some<V> sv = (Some<V>)ov;
+ return sv.get();
+ } else
+ return null;
+ }
+
+// final public TrieMap<K, V> remove (Object k) {
+// removeOpt ((K)k);
+// return this;
+// }
+
+ final public Option<V> putIfAbsentOpt (K k, V v) {
+ int hc = computeHash (k);
+ return insertifhc (k, hc, v, INode.KEY_ABSENT);
+ }
+
+ @Override
+ final public V putIfAbsent (Object k, Object v) {
+ ensureReadWrite();
+ int hc = computeHash ((K)k);
+ Option<V> ov = insertifhc ((K)k, hc, (V)v, INode.KEY_ABSENT);
+ if(ov instanceof Some) {
+ Some<V> sv = (Some<V>)ov;
+ return sv.get();
+ } else
+ return null;
+ }
+
+ @Override
+ public boolean remove (Object k, Object v) {
+ ensureReadWrite();
+ int hc = computeHash ((K)k);
+ return removehc ((K)k, (V)v, hc).nonEmpty ();
+ }
+
+ @Override
+ public boolean replace (K k, V oldvalue, V newvalue) {
+ ensureReadWrite();
+ int hc = computeHash (k);
+ return insertifhc (k, hc, newvalue, (Object) oldvalue).nonEmpty ();
+ }
+
+ public Option<V> replaceOpt (K k, V v) {
+ int hc = computeHash (k);
+ return insertifhc (k, hc, v, INode.KEY_PRESENT);
+ }
+
+ @Override
+ public V replace (Object k, Object v) {
+ ensureReadWrite();
+ int hc = computeHash ((K)k);
+ Option<V> ov = insertifhc ((K)k, hc, (V)v, INode.KEY_PRESENT);
+ if(ov instanceof Some) {
+ Some<V> sv = (Some<V>)ov;
+ return sv.get();
+ } else
+ return null;
+ }
+
+ /***
+ * Return an iterator over a TrieMap.
+ *
+ * If this is a read-only snapshot, it would return a read-only iterator.
+ *
+ * If it is the original TrieMap or a non-readonly snapshot, it would return
+ * an iterator that would allow for updates.
+ *
+ * @return
+ */
+ public Iterator<Map.Entry<K, V>> iterator () {
+ if (!nonReadOnly ())
+ return readOnlySnapshot ().readOnlyIterator ();
+ else
+ return new TrieMapIterator<K, V> (0, this);
+ }
+
+ /***
+ * Return an iterator over a TrieMap.
+ * This is a read-only iterator.
+ *
+ * @return
+ */
+ public Iterator<Map.Entry<K, V>> readOnlyIterator () {
+ if (nonReadOnly ())
+ return readOnlySnapshot ().readOnlyIterator ();
+ else
+ return new TrieMapReadOnlyIterator<K, V> (0, this);
+ }
+
+ private int cachedSize () {
+ INode<K, V> r = RDCSS_READ_ROOT ();
+ return r.cachedSize (this);
+ }
+
+ public int size () {
+ if (nonReadOnly ())
+ return readOnlySnapshot ().size ();
+ else
+ return cachedSize ();
+ }
+
+ String stringPrefix () {
+ return "TrieMap";
+ }
+
+ /***
+ * This iterator is a read-only one and does not allow for any update
+ * operations on the underlying data structure.
+ *
+ * @param <K>
+ * @param <V>
+ */
+ private static class TrieMapReadOnlyIterator<K, V> extends TrieMapIterator<K, V> {
+ TrieMapReadOnlyIterator (int level, final TrieMap<K, V> ct, boolean mustInit) {
+ super (level, ct, mustInit);
+ }
+
+ TrieMapReadOnlyIterator (int level, TrieMap<K, V> ct) {
+ this (level, ct, true);
+ }
+ void initialize () {
+ assert (ct.isReadOnly ());
+ super.initialize ();
+ }
+
+ public void remove () {
+ throw new UnsupportedOperationException ("Operation not supported for read-only iterators");
+ }
+
+ Map.Entry<K, V> nextEntry(final Map.Entry<K, V> rr) {
+ // Return non-updatable entry
+ return rr;
+ }
+ }
+
+ private static class TrieMapIterator<K, V> implements java.util.Iterator<Map.Entry<K, V>> {
+ private int level;
+ protected TrieMap<K, V> ct;
+ private final boolean mustInit;
+ private BasicNode[][] stack = new BasicNode[7][];
+ private int[] stackpos = new int[7];
+ private int depth = -1;
+ private Iterator<Map.Entry<K, V>> subiter = null;
+ private KVNode<K, V> current = null;
+ private Map.Entry<K, V> lastReturned = null;
+
+ TrieMapIterator (int level, final TrieMap<K, V> ct, boolean mustInit) {
+ this.level = level;
+ this.ct = ct;
+ this.mustInit = mustInit;
+ if (this.mustInit)
+ initialize ();
+ }
+
+ TrieMapIterator (int level, TrieMap<K, V> ct) {
+ this (level, ct, true);
+ }
+
+
+ public boolean hasNext () {
+ return (current != null) || (subiter != null);
+ }
+
+ public Map.Entry<K, V> next () {
+ if (hasNext ()) {
+ Map.Entry<K, V> r = null;
+ if (subiter != null) {
+ r = subiter.next ();
+ checkSubiter ();
+ } else {
+ r = current.kvPair ();
+ advance ();
+ }
+
+ lastReturned = r;
+ if(r instanceof Map.Entry) {
+ final Map.Entry<K, V> rr = (Map.Entry<K, V>)r;
+ return nextEntry(rr);
+ }
+ return r;
+ } else {
+ // return Iterator.empty ().next ();
+ return null;
+ }
+ }
+
+ Map.Entry<K, V> nextEntry(final Map.Entry<K, V> rr) {
+ return new Map.Entry<K, V>() {
+ private V updated = null;
+
+ @Override
+ public K getKey () {
+ return rr.getKey ();
+ }
+
+ @Override
+ public V getValue () {
+ return (updated == null)?rr.getValue (): updated;
+ }
+
+ @Override
+ public V setValue (V value) {
+ updated = value;
+ return ct.replace (getKey (), value);
+ }
+ };
+ }
+
+ private void readin (INode<K, V> in) {
+ MainNode<K, V> m = in.gcasRead (ct);
+ if (m instanceof CNode) {
+ CNode<K, V> cn = (CNode<K, V>) m;
+ depth += 1;
+ stack [depth] = cn.array;
+ stackpos [depth] = -1;
+ advance ();
+ } else if (m instanceof TNode) {
+ current = (TNode<K, V>) m;
+ } else if (m instanceof LNode) {
+ subiter = ((LNode<K, V>) m).listmap.iterator ();
+ checkSubiter ();
+ } else if (m == null) {
+ current = null;
+ }
+ }
+
+ // @inline
+ private void checkSubiter () {
+ if (!subiter.hasNext ()) {
+ subiter = null;
+ advance ();
+ }
+ }
+
+ // @inline
+ void initialize () {
+// assert (ct.isReadOnly ());
+ INode<K, V> r = ct.RDCSS_READ_ROOT ();
+ readin (r);
+ }
+
+ void advance () {
+ if (depth >= 0) {
+ int npos = stackpos [depth] + 1;
+ if (npos < stack [depth].length) {
+ stackpos [depth] = npos;
+ BasicNode elem = stack [depth] [npos];
+ if (elem instanceof SNode) {
+ current = (SNode<K, V>) elem;
+ } else if (elem instanceof INode) {
+ readin ((INode<K, V>) elem);
+ }
+ } else {
+ depth -= 1;
+ advance ();
+ }
+ } else
+ current = null;
+ }
+
+ protected TrieMapIterator<K, V> newIterator (int _lev, TrieMap<K, V> _ct, boolean _mustInit) {
+ return new TrieMapIterator<K, V> (_lev, _ct, _mustInit);
+ }
+
+ protected void dupTo (TrieMapIterator<K, V> it) {
+ it.level = this.level;
+ it.ct = this.ct;
+ it.depth = this.depth;
+ it.current = this.current;
+
+ // these need a deep copy
+ System.arraycopy (this.stack, 0, it.stack, 0, 7);
+ System.arraycopy (this.stackpos, 0, it.stackpos, 0, 7);
+
+ // this one needs to be evaluated
+ if (this.subiter == null)
+ it.subiter = null;
+ else {
+ List<Map.Entry<K, V>> lst = toList (this.subiter);
+ this.subiter = lst.iterator ();
+ it.subiter = lst.iterator ();
+ }
+ }
+
+ // /** Returns a sequence of iterators over subsets of this iterator.
+ // * It's used to ease the implementation of splitters for a parallel
+ // version of the TrieMap.
+ // */
+ // protected def subdivide(): Seq[Iterator[(K, V)]] = if (subiter ne
+ // null) {
+ // // the case where an LNode is being iterated
+ // val it = subiter
+ // subiter = null
+ // advance()
+ // this.level += 1
+ // Seq(it, this)
+ // } else if (depth == -1) {
+ // this.level += 1
+ // Seq(this)
+ // } else {
+ // var d = 0
+ // while (d <= depth) {
+ // val rem = stack(d).length - 1 - stackpos(d)
+ // if (rem > 0) {
+ // val (arr1, arr2) = stack(d).drop(stackpos(d) + 1).splitAt(rem / 2)
+ // stack(d) = arr1
+ // stackpos(d) = -1
+ // val it = newIterator(level + 1, ct, false)
+ // it.stack(0) = arr2
+ // it.stackpos(0) = -1
+ // it.depth = 0
+ // it.advance() // <-- fix it
+ // this.level += 1
+ // return Seq(this, it)
+ // }
+ // d += 1
+ // }
+ // this.level += 1
+ // Seq(this)
+ // }
+
+ private List<Entry<K, V>> toList (Iterator<Entry<K, V>> it) {
+ ArrayList<Entry<K, V>> list = new ArrayList<Map.Entry<K, V>> ();
+ while (it.hasNext ()) {
+ list.add (it.next ());
+ }
+ return list;
+ }
+
+ void printDebug () {
+ System.out.println ("ctrie iterator");
+ System.out.println (Arrays.toString (stackpos));
+ System.out.println ("depth: " + depth);
+ System.out.println ("curr.: " + current);
+ // System.out.println(stack.mkString("\n"));
+ }
+
+ @Override
+ public void remove () {
+ if (lastReturned != null) {
+ ct.remove (lastReturned.getKey ());
+ lastReturned = null;
+ } else
+ throw new IllegalStateException();
+ }
+
+ }
+
+ /** Only used for ctrie serialization. */
+ // @SerialVersionUID(0L - 7237891413820527142L)
+ private static long TrieMapSerializationEnd = 0L - 7237891413820527142L;
+
+
+ public boolean containsKey (Object key) {
+ return lookup ((K) key) != null;
+ }
+
+
+ @Override
+ public Set<Map.Entry<K, V>> entrySet () {
+ return entrySet;
+ }
+
+ /***
+ * Support for EntrySet operations required by the Map interface
+ *
+ */
+ final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
+
+ @Override
+ public Iterator<Map.Entry<K, V>> iterator () {
+ return TrieMap.this.iterator ();
+ }
+
+ @Override
+ public final boolean contains (final Object o) {
+ if (!(o instanceof Map.Entry)) {
+ return false;
+ }
+ final Map.Entry<K, V> e = (Map.Entry<K, V>) o;
+ final K k = e.getKey ();
+ final V v = lookup (k);
+ return v != null;
+ }
+
+ @Override
+ public final boolean remove (final Object o) {
+ if (!(o instanceof Map.Entry)) {
+ return false;
+ }
+ final Map.Entry<K, V> e = (Map.Entry<K, V>) o;
+ final K k = e.getKey ();
+ return null != TrieMap.this.remove (k);
+ }
+
+ @Override
+ public final int size () {
+ int size = 0;
+ for (final Iterator<?> i = iterator (); i.hasNext (); i.next ()) {
+ size++;
+ }
+ return size;
+ }
+
+ @Override
+ public final void clear () {
+ TrieMap.this.clear ();
+ }
+ }
+
+ private void readObject(ObjectInputStream inputStream) throws IOException, ClassNotFoundException {
+ inputStream.defaultReadObject();
+ this.root = INode.newRootNode();
+
+ final boolean ro = inputStream.readBoolean();
+ final int size = inputStream.readInt();
+ for (int i = 0; i < size; ++i) {
+ final K key = (K)inputStream.readObject();
+ final V value = (V)inputStream.readObject();
+ add(key, value);
+ }
+
+ // Propagate the read-only bit
+ try {
+ READONLY_FIELD.setBoolean(this, ro);
+ } catch (IllegalAccessException e) {
+ throw new IOException("Failed to set read-only flag", e);
+ }
+ }
+
+ private void writeObject(ObjectOutputStream outputStream) throws IOException {
+ outputStream.defaultWriteObject();
+
+ final Map<K, V> ro = readOnlySnapshot();
+ outputStream.writeBoolean(isReadOnly());
+ outputStream.writeInt(ro.size());
+
+ for (Entry<K, V> e : ro.entrySet()) {
+ outputStream.writeObject(e.getKey());
+ outputStream.writeObject(e.getValue());
+ }
+ }
+}
Code Review / yangtools.git / commitdiff