*/
package org.opendaylight.yangtools.triemap;
+import java.util.Optional;
+
final class INode<K, V> extends INodeBase<K, V> {
static final Object KEY_PRESENT = new Object ();
static final Object KEY_ABSENT = new Object ();
MainNode<K, V> prevval = /* READ */ m.READ_PREV();
if (prevval == null) {
return m;
- } else {
- return GCAS_Complete(m, ct);
}
+
+ 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
- final MainNode<K, V> prev = /* READ */ m.READ_PREV();
- INode<K, V> ctr = ct.readRoot(true);
+ }
- if (prev == null) {
- return m;
+ // complete the GCAS
+ final MainNode<K, V> prev = /* READ */ m.READ_PREV();
+ final 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.READ_PREV())) {
+ return fn.READ_PREV();
}
- if (prev instanceof FailedNode) {
- // try to commit to previous value
- FailedNode<K, V> fn = (FailedNode<K, V>) prev;
- if (CAS(m, fn.READ_PREV())) {
- return fn.READ_PREV();
- } else {
- // Tailrec
- // return GCAS_Complete (/* READ */mainnode, ct);
- m = /* READ */ READ();
- continue;
- }
- } else {
- // 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<>(prev));
- return GCAS_Complete(/* READ */ READ(), ct);
- }
+ // Tail recursion: return GCAS_Complete (/* READ */ READ(), ct);
+ m = /* READ */ READ();
+ continue;
+ }
+
+ // 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;
}
+
+ // Tail recursion: return GCAS_Complete (m, ct);
+ continue;
}
+
+ // try to abort
+ m.CAS_PREV(prev, new FailedNode<>(prev));
+
+ // Tail recursion: return GCAS_Complete(/* READ */ READ(), ct);
+ m = /* READ */ READ();
}
}
- 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);
+ private 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.READ_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);
+ return false;
}
private INode<K, V> inode(final MainNode<K, V> cn) {
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!
+ final 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);
+ final CNode<K, V> cn = (CNode<K, V>) m;
+ final int idx = (hc >>> lev) & 0x1f;
+ final int flag = 1 << idx;
+ final int bmp = cn.bitmap;
+ final int mask = flag - 1;
+ final int pos = Integer.bitCount(bmp & mask);
if ((bmp & flag) != 0) {
// 1a) insert below
- BasicNode cnAtPos = cn.array[pos];
+ final BasicNode cnAtPos = cn.array[pos];
if (cnAtPos instanceof INode) {
- INode<K, V> in = (INode<K, V>) cnAtPos;
+ final 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;
- }
}
+ if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
+ // Tail recursion: return rec_insert (k, v, hc, lev, parent, startgen, ct);
+ continue;
+ }
+
+ return false;
} else if (cnAtPos instanceof SNode) {
- SNode<K, V> sn = (SNode<K, V>) cnAtPos;
- if (sn.hc == hc && equal(sn.k, k, ct)) {
- return GCAS (cn, cn.updatedAt(pos, new SNode<>(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);
+ final SNode<K, V> sn = (SNode<K, V>) cnAtPos;
+ if (sn.hc == hc && ct.equal(sn.k, k)) {
+ return GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct);
}
+
+ final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
+ final 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);
+ CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
MainNode<K, V> ncnode = rn.insertedAt(pos, flag, new SNode<> (k, v, hc), gen);
return GCAS (cn, ncnode, ct);
}
LNode<K, V> ln = (LNode<K, V>) m;
MainNode<K, V> nn = ln.inserted(k, v);
return GCAS(ln, nn, ct);
+ } else {
+ throw new IllegalStateException("Unhandled node " + m);
}
throw new RuntimeException ("Should not happen");
* @return null if unsuccessful, Option[V] otherwise (indicating
* previous value bound to the key)
*/
- Option<V> rec_insertif(final K k, final V v, final int hc, final Object cond, final int lev,
+ Optional<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!
+ final 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);
+ final CNode<K, V> cn = (CNode<K, V>) m;
+ final int idx = (hc >>> lev) & 0x1f;
+ final int flag = 1 << idx;
+ final int bmp = cn.bitmap;
+ final int mask = flag - 1;
+ final int pos = Integer.bitCount(bmp & mask);
if ((bmp & flag) != 0) {
// 1a) insert below
- BasicNode cnAtPos = cn.array [pos];
+ final BasicNode cnAtPos = cn.array[pos];
if (cnAtPos instanceof INode) {
- INode<K, V> in = (INode<K, V>) cnAtPos;
+ final 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;
- }
}
+
+ if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
+ // Tail recursion: return rec_insertif (k, v, hc, cond, lev, parent, startgen, ct);
+ continue;
+ }
+
+ return null;
} else if (cnAtPos instanceof SNode) {
- SNode<K, V> sn = (SNode<K, V>) cnAtPos;
+ final 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, hc), gen), ct)) {
- return Option.makeOption(sn.v);
- } else {
- return null;
+ if (sn.hc == hc && ct.equal(sn.k, k)) {
+ if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
+ return Optional.of(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,
+
+ return null;
+ }
+
+ final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
+ final 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;
- }
+ if (GCAS(cn, nn, ct)) {
+ return Optional.empty();
}
+ 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;
- }
+ if (sn.hc == hc && ct.equal(sn.k, k)) {
+ return Optional.of(sn.v);
}
+
+ final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
+ final 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 Optional.empty();
+ }
+
+ return null;
} else if (cond == INode.KEY_PRESENT) {
- if (sn.hc == hc && equal (sn.k, k, ct)) {
+ if (sn.hc == hc && ct.equal(sn.k, k)) {
if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
- return Option.makeOption(sn.v);
- } else {
- return null;
+ return Optional.of(sn.v);
}
-
- }
- else {
- return Option.makeOption();// None;
+ return null;
}
+
+ return Optional.empty();
} else {
- if (sn.hc == hc && equal (sn.k, k, ct) && sn.v == cond) {
- if (GCAS(cn, cn.updatedAt (pos, new SNode<>(k, v, hc), gen), ct)) {
- return Option.makeOption(sn.v);
- } else {
- return null;
+ if (sn.hc == hc && ct.equal(sn.k, k) && cond.equals(sn.v)) {
+ if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
+ return Optional.of(sn.v);
}
+
+ return null;
}
- else {
- return Option.makeOption(); // None
- }
- }
+ return Optional.empty();
+ }
}
} 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, hc), gen);
+ final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
+ final CNode<K, V> ncnode = rn.insertedAt (pos, flag, new SNode<>(k, v, hc), gen);
if (GCAS(cn, ncnode, ct)) {
- return Option.makeOption(); // None
- } else {
- return null;
+ return Optional.empty();
}
+
+ return null;
} else if (cond == INode.KEY_PRESENT) {
- return Option.makeOption(); // None;
- }
- else {
- return Option.makeOption(); // None
+ return Optional.empty();
+ } else {
+ return Optional.empty();
}
} 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;
+ final LNode<K, V> ln = (LNode<K, V>) m;
if (cond == null) {
- Option<V> optv = ln.get(k);
+ final Optional<V> optv = ln.get(k);
if (insertln(ln, k, v, ct)) {
return optv;
- } else {
- return null;
}
+ 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 {
+ final Optional<V> t = ln.get(k);
+ if (t.isPresent()) {
return t;
}
+ if (insertln(ln, k, v, ct)) {
+ return Optional.empty();
+ }
+ return null;
} 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
+ final Optional<V> t = ln.get(k);
+ if (!t.isPresent()) {
+ return t;
}
+ if (insertln(ln, k, v, ct)) {
+ return t;
+ }
+ return null;
} else {
- Option<V> t = ln.get (k);
- if (t != null) {
- if (((Some<V>) t).get() == cond) {
+ final Optional<V> t = ln.get(k);
+ if (t.isPresent()) {
+ if (cond.equals(t.get())) {
if (insertln(ln, k, v, ct)) {
- return new Some<>((V) cond);
- } else {
- return null;
+ // Difference from Scala: we choose to reuse the object returned from LNode,
+ // as the identity of the value does not matter in this call graph.
+ return t;
}
- } else {
- return Option.makeOption ();
+
+ return null;
}
}
+
+ return Optional.empty();
}
+ } else {
+ throw new IllegalStateException("Unhandled node " + m);
}
- // throw new RuntimeException ("Should not happen");
+ throw new RuntimeException("Should never happen");
}
}
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);
+ final LNode<K, V> nn = ln.inserted (k, v);
+ return GCAS(ln, nn, ct);
}
/**
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) {
while (true) {
- MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
+ final 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;
+ final int idx = (hc >>> lev) & 0x1f;
+ final int flag = 1 << idx;
+ final 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;
- }
+ // 1a) bitmap shows no binding
+ return null;
+ }
+
+ // 1b) bitmap contains a value - descend
+ final int pos = (bmp == 0xffffffff) ? idx : Integer.bitCount(bmp & (flag - 1));
+ final BasicNode sub = cn.array[pos];
+ if (sub instanceof INode) {
+ final INode<K, V> in = (INode<K, V>) sub;
+ if (ct.isReadOnly() || (startgen == in.gen)) {
+ return in.rec_lookup(k, hc, lev + 5, this, startgen, ct);
+ }
+
+ if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
+ // Tail recursion: return rec_lookup(k, hc, lev, parent, startgen, ct);
+ continue;
}
+
+ // used to be throw RestartException
+ return RESTART;
+ } else if (sub instanceof SNode) {
+ // 2) singleton node
+ final SNode<K, V> sn = (SNode<K, V>) sub;
+ if (sn.hc == hc && ct.equal(sn.k, k)) {
+ return sn.v;
+ }
+
+ 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 != null) ? ((Option<V>) tmp) : null;
+ return ((LNode<K, V>) m).get(k);
+ } else {
+ throw new IllegalStateException("Unhandled node " + m);
}
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, final K k, final int hc) {
if (ct.nonReadOnly()) {
+ // used to be throw RestartException
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;
- }
+ return RESTART;
+ }
+
+ if (tn.hc == hc && ct.equal(tn.k, k)) {
+ return tn.v;
}
+
+ return null;
}
/**
* Removes the key associated with the given value.
*
* @param v
- * if null, will remove the key irregardless of the value;
+ * if null, will remove the key regardless 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
*/
- Option<V> rec_remove(final K k, final V v, final int hc, final int lev, final INode<K, V> parent,
+ Optional<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) {
- MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
+ final 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;
+ final CNode<K, V> cn = (CNode<K, V>) m;
+ final int idx = (hc >>> lev) & 0x1f;
+ final int bmp = cn.bitmap;
+ final 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);
+ return Optional.empty();
+ }
+
+ final int pos = Integer.bitCount(bmp & (flag - 1));
+ final BasicNode sub = cn.array[pos];
+ Optional<V> res = null;
+ if (sub instanceof INode) {
+ final 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 {
- if (GCAS(cn, cn.renewed (startgen, ct), ct)) {
- res = rec_remove(k, v, hc, lev, parent, startgen, ct);
- } else {
- res = null;
- }
+ 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 if (sub instanceof SNode) {
+ final SNode<K, V> sn = (SNode<K, V>) sub;
+ if (sn.hc == hc && ct.equal(sn.k, k) && (v == null || v.equals(sn.v))) {
+ final MainNode<K, V> ncn = cn.removedAt(pos, flag, gen).toContracted(lev);
+ if (GCAS(cn, ncn, ct)) {
+ res = Optional.of(sn.v);
} else {
- res = Option.makeOption ();
+ res = null;
}
+ } else {
+ res = Optional.empty();
}
+ }
- 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);
- }
- }
+ if (res == null || !res.isPresent()) {
+ return res;
+ }
- return res;
+ if (parent != null) {
+ // never tomb at root
+ final 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;
+ final 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)) {
+ final Optional<V> optv = ln.get(k);
+ final 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;
- }
- }
+
+ return null;
+ }
+
+ final Optional<V> tmp = ln.get(k);
+ if (tmp.isPresent() && v.equals(tmp.get())) {
+ final MainNode<K, V> nn = ln.removed(k, ct);
+ if (GCAS(ln, nn, ct)) {
+ return tmp;
}
+
+ return null;
}
+
+ // Key not found or value does not match: we have not removed anything
+ return Optional.empty();
+ } else {
+ throw new IllegalStateException("Unhandled node " + m);
}
- throw new RuntimeException ("Should not happen");
}
- void cleanParent(final Object nonlive, final INode<K, V> parent, final TrieMap<K, V> ct, final int hc,
+ private 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;
- }
- }
+ final MainNode<K, V> pm = parent.GCAS_READ(ct);
+ if ((!(pm instanceof CNode))) {
+ // parent is no longer a cnode, we're done
+ return;
+ }
+
+ final CNode<K, V> cn = (CNode<K, V>) pm;
+ final int idx = (hc >>> (lev - 5)) & 0x1f;
+ final int bmp = cn.bitmap;
+ final int flag = 1 << idx;
+ if ((bmp & flag) == 0) {
+ // somebody already removed this i-node, we're done
+ return;
+ }
+
+ final int pos = Integer.bitCount(bmp & (flag - 1));
+ final BasicNode sub = cn.array[pos];
+ if (sub == this) {
+ if (nonlive instanceof TNode) {
+ final 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) {
+ // Tail recursion: cleanParent(nonlive, parent, ct, hc, lev, startgen);
+ 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, final int lev) {
- MainNode<K, V> m = nd.GCAS_READ(ct);
+ final MainNode<K, V> m = nd.GCAS_READ(ct);
if (m instanceof CNode) {
- CNode<K, V> cn = (CNode<K, V>) m;
+ final CNode<K, V> cn = (CNode<K, V>) m;
nd.GCAS(cn, cn.toCompressed(ct, lev, gen), ct);
}
}
- boolean isNullInode(final TrieMap<K, V> ct) {
- return GCAS_READ(ct) == null;
- }
-
int cachedSize(final TrieMap<K, V> ct) {
MainNode<K, V> m = GCAS_READ(ct);
return m.cachedSize(ct);