*/
package org.opendaylight.yangtools.triemap;
-final class INode<K, V> extends INodeBase<K, V> {
- static final Object KEY_PRESENT = new Object ();
- static final Object KEY_ABSENT = new Object ();
+import static org.opendaylight.yangtools.triemap.LookupResult.RESTART;
+import static org.opendaylight.yangtools.triemap.PresencePredicate.ABSENT;
+import static org.opendaylight.yangtools.triemap.PresencePredicate.PRESENT;
- /**
- * Virtual result for lookup methods indicating that the lookup needs to be restarted. This is a faster version
- * of throwing a checked exception to control the restart.
- */
- static final Object RESTART = new Object();
+import java.util.Optional;
+import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
+
+final class INode<K, V> extends BasicNode {
+ @SuppressWarnings("rawtypes")
+ private static final AtomicReferenceFieldUpdater<INode, MainNode> MAINNODE_UPDATER =
+ AtomicReferenceFieldUpdater.newUpdater(INode.class, MainNode.class, "mainnode");
+
+ private final Gen gen;
+
+ private volatile MainNode<K, V> mainnode;
- INode(final Gen gen, final MainNode<K, V> bn) {
- super(gen, bn);
+ INode(final Gen gen, final MainNode<K, V> mainnode) {
+ this.gen = gen;
+ this.mainnode = mainnode;
}
MainNode<K, V> gcasRead(final TrieMap<K, V> ct) {
}
MainNode<K, V> GCAS_READ(final TrieMap<K, V> ct) {
- MainNode<K, V> m = /* READ */ READ();
+ MainNode<K, V> m = /* READ */ mainnode;
MainNode<K, V> prevval = /* READ */ m.READ_PREV();
if (prevval == 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())) {
+ if (MAINNODE_UPDATER.compareAndSet(this, m, fn.READ_PREV())) {
return fn.READ_PREV();
}
- // Tail recursion: return GCAS_Complete (/* READ */ READ(), ct);
- m = /* READ */ READ();
+ // Tail recursion: return GCAS_Complete (/* READ */ mainnode, ct);
+ m = /* READ */ mainnode;
continue;
}
// ==> 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()) {
+ if (ctr.gen == gen && !ct.isReadOnly()) {
// try to commit
if (m.CAS_PREV(prev, null)) {
return m;
// try to abort
m.CAS_PREV(prev, new FailedNode<>(prev));
- // Tail recursion: return GCAS_Complete(/* READ */ READ(), ct);
- m = /* READ */ READ();
+ // Tail recursion: return GCAS_Complete(/* READ */ mainnode, ct);
+ m = /* READ */ mainnode;
}
}
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)) {
+ if (MAINNODE_UPDATER.compareAndSet(this, old, n)) {
GCAS_Complete(n, ct);
return /* READ */ n.READ_PREV() == null;
}
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) {
return new INode<>(gen, cn);
}
*
* @return true if successful, false otherwise
*/
- boolean rec_insert(final K k, final V v, final int hc, final int lev, final INode<K, V> parent, final Gen startgen,
+ boolean rec_insert(final K k, final V v, final int hc, final int lev, final INode<K, V> parent,
final TrieMap<K, V> ct) {
+ return rec_insert(k, v, hc, lev, parent, gen, ct);
+ }
+
+ private 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) {
final MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
return false;
} else if (cnAtPos instanceof SNode) {
final SNode<K, V> sn = (SNode<K, V>) cnAtPos;
- if (sn.hc == hc && equal(sn.k, k, ct)) {
+ if (sn.hc == hc && ct.equal(sn.k, k)) {
return GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), 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 TrieMap<K, V> ct) {
+ return rec_insertif(k, v, hc, cond, lev, parent, gen, ct);
+ }
+
+ private 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) {
final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
} else if (cnAtPos instanceof SNode) {
final SNode<K, V> sn = (SNode<K, V>) cnAtPos;
if (cond == null) {
- 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);
+ return Optional.of(sn.v);
}
return null;
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;
+ 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 if (cond == ABSENT) {
+ 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 Option.makeOption(); // None
+ return Optional.empty();
}
return null;
- } else if (cond == INode.KEY_PRESENT) {
- if (sn.hc == hc && equal(sn.k, k, ct)) {
+ } else if (cond == PRESENT) {
+ 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);
+ return Optional.of(sn.v);
}
return null;
}
- return Option.makeOption();// None;
+ return Optional.empty();
} else {
- if (sn.hc == hc && equal(sn.k, k, ct) && sn.v == cond) {
+ 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 Option.makeOption(sn.v);
+ return Optional.of(sn.v);
}
return null;
}
- return Option.makeOption(); // None
+ return Optional.empty();
}
}
- } else if (cond == null || cond == INode.KEY_ABSENT) {
+ } else if (cond == null || cond == ABSENT) {
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
+ return Optional.empty();
}
return null;
- } else if (cond == INode.KEY_PRESENT) {
- return Option.makeOption(); // None;
- }
- else {
- return Option.makeOption(); // None
+ } else {
+ return Optional.empty();
}
} else if (m instanceof TNode) {
clean(parent, ct, lev - 5);
// 3) an l-node
final LNode<K, V> ln = (LNode<K, V>) m;
if (cond == null) {
- final Option<V> optv = ln.get(k);
+ final Optional<V> optv = ln.get(k);
if (insertln(ln, k, v, ct)) {
return optv;
}
return null;
- } else if (cond == INode.KEY_ABSENT) {
- final Option<V> t = ln.get(k);
- if (t != null) {
+ } else if (cond == ABSENT) {
+ final Optional<V> t = ln.get(k);
+ if (t.isPresent()) {
return t;
}
if (insertln(ln, k, v, ct)) {
- return Option.makeOption();// None
+ return Optional.empty();
}
return null;
- } else if (cond == INode.KEY_PRESENT) {
- final Option<V> t = ln.get(k);
- if (t == null) {
- return null; // None
+ } else if (cond == PRESENT) {
+ final Optional<V> t = ln.get(k);
+ if (!t.isPresent()) {
+ return t;
}
if (insertln(ln, k, v, ct)) {
return t;
}
return null;
} else {
- final 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);
+ // 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;
}
return null;
}
- return Option.makeOption();
}
+
+ return Optional.empty();
}
+ } else {
+ throw new IllegalStateException("Unhandled node " + m);
}
- // throw new RuntimeException ("Should not happen");
+ throw new RuntimeException("Should never happen");
}
}
* @return null if no value has been found, RESTART if the operation
* wasn't successful, or any other value otherwise
*/
- Object rec_lookup(final K k, final int hc, final int lev, final INode<K, V> parent, final Gen startgen,
+ Object rec_lookup(final K k, final int hc, final int lev, final INode<K, V> parent, final TrieMap<K, V> ct) {
+ return rec_lookup(k, hc, lev, parent, gen, ct);
+ }
+
+ private 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) {
final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
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 && equal(sn.k, k, ct)) {
+ if (sn.hc == hc && ct.equal(sn.k, k)) {
return sn.v;
}
return cleanReadOnly((TNode<K, V>) m, lev, parent, ct, k, hc);
} else if (m instanceof LNode) {
// 5) an l-node
- return ((LNode<K, V>) m).get(k);
+ return ((LNode<K, V>) m).get(k).orElse(null);
+ } 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;
- }
+ if (ct.isReadOnly()) {
+ if (tn.hc == hc && ct.equal(tn.k, k)) {
+ return tn.v;
+ }
- if (tn.hc == hc && equal(tn.k, k, ct)) {
- return tn.v;
+ return null;
}
- return null;
+ clean(parent, ct, lev - 5);
+ return RESTART;
}
/**
* @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 TrieMap<K, V> ct) {
+ return rec_remove(k, v, hc, lev, parent, gen, ct);
+ }
+
+ private 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) {
final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
final int bmp = cn.bitmap;
final int flag = 1 << idx;
if ((bmp & flag) == 0) {
- return Option.makeOption();
+ return Optional.empty();
}
final int pos = Integer.bitCount(bmp & (flag - 1));
final BasicNode sub = cn.array[pos];
- Option<V> res = null;
+ Optional<V> res = null;
if (sub instanceof INode) {
final INode<K, V> in = (INode<K, V>) sub;
if (startgen == in.gen) {
} else if (sub instanceof SNode) {
final SNode<K, V> sn = (SNode<K, V>) sub;
- if (sn.hc == hc && equal(sn.k, k, ct) && (v == null || v.equals(sn.v))) {
+ 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 = Option.makeOption(sn.v);
+ res = Optional.of(sn.v);
} else {
res = null;
}
} else {
- res = Option.makeOption ();
+ res = Optional.empty();
}
}
- if (res instanceof None || (res == null)) {
+ if (res == null || !res.isPresent()) {
return res;
}
} else if (m instanceof LNode) {
final LNode<K, V> ln = (LNode<K, V>) m;
if (v == null) {
- final Option<V> optv = ln.get(k);
+ final Optional<V> optv = ln.get(k);
final MainNode<K, V> nn = ln.removed(k, ct);
if (GCAS(ln, nn, ct)) {
return optv;
return null;
}
- final Option<V> tmp = ln.get(k);
- if (tmp instanceof Some) {
- final Some<V> tmp1 = (Some<V>) tmp;
- if (tmp1.get() == v) {
- final MainNode<K, V> nn = ln.removed(k, ct);
- if (GCAS(ln, nn, ct)) {
- return tmp;
- }
-
- 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");
}
private void cleanParent(final Object nonlive, final INode<K, V> parent, final TrieMap<K, V> ct, final int hc,
Code Review / yangtools.git / blobdiff