import static org.opendaylight.yangtools.triemap.PresencePredicate.ABSENT;
import static org.opendaylight.yangtools.triemap.PresencePredicate.PRESENT;
+import com.google.common.base.VerifyException;
import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
import java.util.Optional;
import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
private MainNode<K, V> GCAS_READ(final TrieMap<?, ?> ct) {
MainNode<K, V> m = /* READ */ mainnode;
- MainNode<K, V> prevval = /* READ */ m.READ_PREV();
+ MainNode<K, V> prevval = /* READ */ m.readPrev();
if (prevval == null) {
return m;
}
return GCAS_Complete(m, ct);
}
- private MainNode<K, V> GCAS_Complete(MainNode<K, V> m, final TrieMap<?, ?> ct) {
- while (true) {
- if (m == null) {
- return null;
- }
-
+ private MainNode<K, V> GCAS_Complete(final MainNode<K, V> oldmain, final TrieMap<?, ?> ct) {
+ MainNode<K, V> m = oldmain;
+ while (m != null) {
// complete the GCAS
- final MainNode<K, V> prev = /* READ */ m.READ_PREV();
- final Gen rdgen = ct.readRoot(true).gen;
+ final MainNode<K, V> prev = /* READ */ m.readPrev();
+ final INode<?, ?> 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 (MAINNODE_UPDATER.compareAndSet(this, m, fn.READ_PREV())) {
- return fn.READ_PREV();
+ if (MAINNODE_UPDATER.compareAndSet(this, m, fn.readPrev())) {
+ return fn.readPrev();
}
- // Tail recursion: return GCAS_Complete (/* READ */ mainnode, ct);
+ // 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 (rdgen == gen && !ct.isReadOnly()) {
+ if (ctr.gen == gen && !ct.isReadOnly()) {
// try to commit
- if (m.CAS_PREV(prev, null)) {
+ if (m.casPrev(prev, null)) {
return m;
}
- // Tail recursion: return GCAS_Complete (m, ct);
+ // Tail recursion: return GCAS_Complete(m, ct);
continue;
}
// try to abort
- m.CAS_PREV(prev, new FailedNode<>(prev));
+ m.casPrev(prev, new FailedNode<>(prev));
// Tail recursion: return GCAS_Complete(/* READ */ mainnode, ct);
m = /* READ */ mainnode;
}
+
+ return null;
}
private boolean GCAS(final MainNode<K, V> old, final MainNode<K, V> n, final TrieMap<?, ?> ct) {
- n.WRITE_PREV(old);
+ n.writePrev(old);
if (MAINNODE_UPDATER.compareAndSet(this, old, n)) {
GCAS_Complete(n, ct);
- return /* READ */ n.READ_PREV() == null;
+ return /* READ */ n.readPrev() == null;
}
return false;
*
* @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,
+ boolean recInsert(final K key, final V value, 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);
+ return recInsert(key, value, 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,
+ private boolean recInsert(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!
+ final MainNode<K, V> m = GCAS_READ(ct);
if (m instanceof CNode) {
// 1) a multiway node
if (cnAtPos instanceof INode) {
final INode<K, V> in = (INode<K, V>) cnAtPos;
if (startgen == in.gen) {
- return in.rec_insert(k, v, hc, lev + LEVEL_BITS, this, startgen, ct);
+ return in.recInsert(k, v, hc, lev + LEVEL_BITS, this, startgen, ct);
}
if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
- // Tail recursion: return rec_insert (k, v, hc, lev, parent, startgen, ct);
+ // Tail recursion: return rec_insert(k, v, hc, lev, parent, startgen, ct);
continue;
}
return false;
} else if (cnAtPos instanceof SNode) {
final SNode<K, V> sn = (SNode<K, V>) cnAtPos;
- if (sn.hc == hc && ct.equal(sn.k, k)) {
+ if (sn.hc == hc && ct.equal(sn.key, 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, k, v, hc, lev + LEVEL_BITS, gen)), gen);
- return GCAS (cn, nn, ct);
+ final MainNode<K, V> nn = rn.updatedAt(pos, inode(
+ CNode.dual(sn, k, v, hc, lev + LEVEL_BITS, gen)), gen);
+ return GCAS(cn, nn, ct);
+ } else {
+ throw CNode.invalidElement(cnAtPos);
}
- } else {
- final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
- final MainNode<K, V> ncnode = rn.insertedAt(pos, flag, new SNode<>(k, v, hc), gen);
- return GCAS (cn, ncnode, ct);
}
+
+ final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
+ final MainNode<K, V> ncnode = rn.insertedAt(pos, flag, new SNode<>(k, v, hc), gen);
+ return GCAS(cn, ncnode, ct);
} else if (m instanceof TNode) {
clean(parent, ct, lev - LEVEL_BITS);
return false;
final LNodeEntry<K, V> entry = ln.get(ct.equiv(), k);
return entry != null ? replaceln(ln, entry, v, ct) : insertln(ln, k, v, ct);
} else {
- throw new IllegalStateException("Unhandled node " + m);
+ throw invalidElement(m);
}
-
- throw new RuntimeException ("Should not happen");
}
}
+ private static VerifyException invalidElement(final BasicNode elem) {
+ throw new VerifyException("An INode can host only a CNode, a TNode or an LNode, not " + elem);
+ }
+
+ @SuppressFBWarnings(value = "NP_OPTIONAL_RETURN_NULL",
+ justification = "Returning null Optional indicates the need to restart.")
+ private Optional<V> insertDual(final TrieMap<K, V> ct, final CNode<K, V> cn, final int pos, final SNode<K, V> sn,
+ final K k, final V v, final int hc, final int lev) {
+ 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, k, v, hc, lev + LEVEL_BITS, gen)), gen);
+ return GCAS(cn, nn, ct) ? Optional.empty() : null;
+ }
+
/**
* Inserts a new key value pair, given that a specific condition is met.
*
* @return null if unsuccessful, Option[V] otherwise (indicating
* previous value bound to the key)
*/
- Optional<V> rec_insertif(final K k, final V v, final int hc, final Object cond, final int lev,
+ Optional<V> recInsertIf(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);
+ return recInsertIf(k, v, hc, cond, lev, parent, gen, ct);
}
@SuppressFBWarnings(value = "NP_OPTIONAL_RETURN_NULL",
justification = "Returning null Optional indicates the need to restart.")
- private Optional<V> insertDual(final TrieMap<K, V> ct, final CNode<K, V> cn, final int pos, final SNode<K, V> sn,
- final K k, final V v, final int hc, final int lev) {
- 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, k, v, hc, lev + LEVEL_BITS, gen)), gen);
- return GCAS(cn, nn, ct) ? Optional.empty() : null;
- }
-
- @SuppressFBWarnings(value = "NP_OPTIONAL_RETURN_NULL",
- justification = "Returning null Optional indicates the need to restart.")
- private Optional<V> rec_insertif(final K k, final V v, final int hc, final Object cond, final int lev,
+ private Optional<V> recInsertIf(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!
+ final MainNode<K, V> m = GCAS_READ(ct);
if (m instanceof CNode) {
// 1) a multiway node
if (cnAtPos instanceof INode) {
final INode<K, V> in = (INode<K, V>) cnAtPos;
if (startgen == in.gen) {
- return in.rec_insertif(k, v, hc, cond, lev + LEVEL_BITS, this, startgen, ct);
+ return in.recInsertIf(k, v, hc, cond, lev + LEVEL_BITS, this, startgen, ct);
}
if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
- // Tail recursion: return rec_insertif (k, v, hc, cond, lev, parent, startgen, ct);
+ // Tail recursion: return rec_insertif(k, v, hc, cond, lev, parent, startgen, ct);
continue;
}
} else if (cnAtPos instanceof SNode) {
final SNode<K, V> sn = (SNode<K, V>) cnAtPos;
if (cond == null) {
- if (sn.hc == hc && ct.equal(sn.k, k)) {
+ if (sn.hc == hc && ct.equal(sn.key, k)) {
if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
- return Optional.of(sn.v);
+ return Optional.of(sn.value);
}
return null;
return insertDual(ct, cn, pos, sn, k, v, hc, lev);
} else if (cond == ABSENT) {
- if (sn.hc == hc && ct.equal(sn.k, k)) {
- return Optional.of(sn.v);
+ if (sn.hc == hc && ct.equal(sn.key, k)) {
+ return Optional.of(sn.value);
}
return insertDual(ct, cn, pos, sn, k, v, hc, lev);
} else if (cond == PRESENT) {
- if (sn.hc == hc && ct.equal(sn.k, k)) {
+ if (sn.hc == hc && ct.equal(sn.key, k)) {
if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
- return Optional.of(sn.v);
+ return Optional.of(sn.value);
}
return null;
}
return Optional.empty();
} else {
- if (sn.hc == hc && ct.equal(sn.k, k) && cond.equals(sn.v)) {
+ if (sn.hc == hc && ct.equal(sn.key, k) && cond.equals(sn.value)) {
if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
- return Optional.of(sn.v);
+ return Optional.of(sn.value);
}
return null;
return Optional.empty();
}
+ } else {
+ throw CNode.invalidElement(cnAtPos);
}
} 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);
+ final CNode<K, V> ncnode = rn.insertedAt(pos, flag, new SNode<>(k, v, hc), gen);
if (GCAS(cn, ncnode, ct)) {
return Optional.empty();
}
return replaceln(ln, entry, v, ct) ? Optional.of(entry.getValue()) : null;
}
} else {
- throw new IllegalStateException("Unhandled node " + m);
+ throw invalidElement(m);
}
-
- 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 TrieMap<K, V> ct) {
- return rec_lookup(k, hc, lev, parent, gen, ct);
+ Object recLookup(final K k, final int hc, final int lev, final INode<K, V> parent, final TrieMap<K, V> ct) {
+ return recLookup(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,
+ private Object recLookup(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!
+ final MainNode<K, V> m = GCAS_READ(ct);
if (m instanceof CNode) {
// 1) a multinode
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 + LEVEL_BITS, this, startgen, ct);
+ return in.recLookup(k, hc, lev + LEVEL_BITS, this, startgen, ct);
}
if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
} 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;
+ if (sn.hc == hc && ct.equal(sn.key, k)) {
+ return sn.value;
}
return null;
+ } else {
+ throw CNode.invalidElement(sub);
}
} else if (m instanceof TNode) {
// 3) non-live node
final LNodeEntry<K, V> entry = ((LNode<K, V>) m).get(ct.equiv(), k);
return entry != null ? entry.getValue() : null;
} else {
- throw new IllegalStateException("Unhandled node " + m);
+ throw invalidElement(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.isReadOnly()) {
- if (tn.hc == hc && ct.equal(tn.k, k)) {
- return tn.v;
+ if (tn.hc == hc && ct.equal(tn.key, k)) {
+ return tn.value;
}
return null;
* @return null if not successful, an Optional indicating the previous
* value otherwise
*/
- Optional<V> rec_remove(final K k, final Object cond, final int hc, final int lev, final INode<K, V> parent,
+ Optional<V> recRemove(final K k, final Object cond, final int hc, final int lev, final INode<K, V> parent,
final TrieMap<K, V> ct) {
- return rec_remove(k, cond, hc, lev, parent, gen, ct);
+ return recRemove(k, cond, hc, lev, parent, gen, ct);
}
@SuppressFBWarnings(value = "NP_OPTIONAL_RETURN_NULL",
justification = "Returning null Optional indicates the need to restart.")
- private Optional<V> rec_remove(final K k, final Object cond, final int hc, final int lev, final INode<K, V> parent,
+ private Optional<V> recRemove(final K k, final Object cond, 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 MainNode<K, V> m = GCAS_READ(ct);
if (m instanceof CNode) {
final CNode<K, V> cn = (CNode<K, V>) m;
final int pos = Integer.bitCount(bmp & (flag - 1));
final BasicNode sub = cn.array[pos];
- Optional<V> res = null;
+ final Optional<V> res;
if (sub instanceof INode) {
final INode<K, V> in = (INode<K, V>) sub;
if (startgen == in.gen) {
- res = in.rec_remove(k, cond, hc, lev + LEVEL_BITS, this, startgen, ct);
+ res = in.recRemove(k, cond, hc, lev + LEVEL_BITS, this, startgen, ct);
} else {
- if (GCAS(cn, cn.renewed (startgen, ct), ct)) {
- res = rec_remove(k, cond, hc, lev, parent, startgen, ct);
+ if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
+ res = recRemove(k, cond, hc, lev, parent, startgen, ct);
} 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) && (cond == null || cond.equals(sn.v))) {
+ if (sn.hc == hc && ct.equal(sn.key, k) && (cond == null || cond.equals(sn.value))) {
final MainNode<K, V> ncn = cn.removedAt(pos, flag, gen).toContracted(lev);
if (GCAS(cn, ncn, ct)) {
- res = Optional.of(sn.v);
+ res = Optional.of(sn.value);
} else {
res = null;
}
} else {
res = Optional.empty();
}
+ } else {
+ throw CNode.invalidElement(sub);
}
if (res == null || !res.isPresent()) {
return GCAS(ln, ln.removeChild(entry, hc), ct) ? Optional.of(value) : null;
} else {
- throw new IllegalStateException("Unhandled node " + m);
+ throw invalidElement(m);
}
}
final int pos = Integer.bitCount(bmp & (flag - 1));
final BasicNode sub = cn.array[pos];
- if (sub == this) {
- if (nonlive instanceof TNode) {
- final TNode<?, ?> tn = (TNode<?, ?>) nonlive;
- final MainNode<K, V> ncn = cn.updatedAt(pos, tn.copyUntombed(), gen).toContracted(lev - LEVEL_BITS);
- if (!parent.GCAS(cn, ncn, ct)) {
- if (ct.readRoot().gen == startgen) {
- // Tail recursion: cleanParent(nonlive, parent, ct, hc, lev, startgen);
- continue;
- }
+ if (sub == this && nonlive instanceof TNode) {
+ final TNode<?, ?> tn = (TNode<?, ?>) nonlive;
+ final MainNode<K, V> ncn = cn.updatedAt(pos, tn.copyUntombed(), gen).toContracted(lev - LEVEL_BITS);
+ if (!parent.GCAS(cn, ncn, ct)) {
+ if (ct.readRoot().gen == startgen) {
+ // Tail recursion: cleanParent(nonlive, parent, ct, hc, lev, startgen);
+ continue;
}
}
}
int size(final ImmutableTrieMap<?, ?> ct) {
return GCAS_READ(ct).size(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)
- // })
-
- @Override
- String string(final int lev) {
- return "INode";
- }
-}
\ No newline at end of file
+}