*/
package org.opendaylight.yangtools.triemap;
-final class CNode<K, V> extends CNodeBase<K, V> {
+import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;
+
+final class CNode<K, V> extends MainNode<K, V> {
+ @SuppressWarnings("rawtypes")
+ private static final AtomicIntegerFieldUpdater<CNode> CSIZE_UPDATER = AtomicIntegerFieldUpdater.newUpdater(
+ CNode.class, "csize");
+
private static final BasicNode[] EMPTY_ARRAY = new BasicNode[0];
+ private static final int NO_SIZE = -1;
final int bitmap;
final BasicNode[] array;
final Gen gen;
- CNode(final Gen gen) {
- this(gen, 0, EMPTY_ARRAY);
- }
+ private volatile int csize = NO_SIZE;
private CNode(final Gen gen, final int bitmap, final BasicNode... array) {
this.bitmap = bitmap;
this.gen = gen;
}
+ CNode(final Gen gen) {
+ this(gen, 0, EMPTY_ARRAY);
+ }
+
+ static <K, V> MainNode<K,V> dual(final SNode<K, V> x, final int xhc, final SNode<K, V> y, final int yhc,
+ final int lev, final Gen gen) {
+ if (lev >= 35) {
+ return new LNode<>(x.k, x.v, y.k, y.v);
+ }
+
+ final int xidx = (xhc >>> lev) & 0x1f;
+ final int yidx = (yhc >>> lev) & 0x1f;
+ final int bmp = (1 << xidx) | (1 << yidx);
+
+ if (xidx == yidx) {
+ INode<K, V> subinode = new INode<>(gen, dual(x, xhc, y, yhc, lev + 5, gen));
+ return new CNode<>(gen, bmp, subinode);
+ }
+
+ return xidx < yidx ? new CNode<>(gen, bmp, x, y) : new CNode<>(gen, bmp, y, x);
+ }
+
// this should only be called from within read-only snapshots
@Override
- int cachedSize(final TrieMap<K, V> ct) {
- final int currsz = READ_SIZE();
- if (currsz != -1) {
- return currsz;
+ int cachedSize(final TrieMap<?, ?> ct) {
+ int sz = csize;
+ if (sz == NO_SIZE) {
+ // We have not computed the size yet, do that now
+ sz = computeSize(ct);
+ if (!CSIZE_UPDATER.compareAndSet(this, NO_SIZE, sz)) {
+ // We have been pre-empted by some else: read the result
+ sz = csize;
+ }
}
- final int sz = computeSize(ct);
- while (READ_SIZE () == -1) {
- CAS_SIZE (-1, sz);
- }
- return READ_SIZE ();
+ return sz;
}
// lends itself towards being parallelizable by choosing
// => 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) {
+ private int computeSize(final TrieMap<?, ?> ct) {
int i = 0;
int sz = 0;
// final int offset = (array.length > 0) ?
if (elem instanceof SNode) {
sz += 1;
} else if (elem instanceof INode) {
- sz += ((INode<K, V>) elem).cachedSize (ct);
+ sz += ((INode<?, ?>) elem).cachedSize(ct);
}
i += 1;
}
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] = ((INode<?, ?>) elem).copyToGen(ngen, ct);
+ } else if (elem != null) {
narr [i] = elem;
}
i += 1;
return new CNode<>(ngen, bitmap, narr);
}
- 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();
- }
-
- return inode;
- }
-
MainNode<K, V> toContracted(final 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;
+ if (array[0] instanceof SNode) {
+ return ((SNode<K, V>) array[0]).copyTombed();
}
- } else {
return this;
}
+
+ return this;
}
// - if the branching factor is 1 for this CNode, and the child
// 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
- MainNode<K, V> toCompressed(final TrieMap<K, V> ct, final int lev, final Gen gen) {
+ MainNode<K, V> toCompressed(final TrieMap<?, ?> ct, final int lev, final Gen gen) {
int bmp = bitmap;
int i = 0;
BasicNode[] arr = array;
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);
+ final INode<?, ?> in = (INode<?, ?>) sub;
+ final MainNode<?, ?> inodemain = in.gcasRead(ct);
assert (inodemain != null);
- tmparray [i] = resurrect (in, inodemain);
+ tmparray [i] = resurrect(in, inodemain);
} else if (sub instanceof SNode) {
tmparray [i] = sub;
}
return new CNode<K, V>(gen, bmp, tmparray).toContracted(lev);
}
+ private static BasicNode resurrect(final INode<?, ?> inode, final MainNode<?, ?> inodemain) {
+ return inodemain instanceof TNode ? ((TNode<?, ?>) inodemain).copyUntombed() : inode;
+ }
+
@Override
String string(final int lev) {
// "CNode %x\n%s".format(bitmap, array.map(_.string(lev +
// elems.sorted.mkString(", "))
return "CNode";
}
-
- static <K, V> MainNode<K,V> dual(final SNode<K, V> x, final int xhc, final SNode<K, V> y, final int yhc,
- final int lev, final Gen gen) {
- 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<>(gen, dual(x, xhc, y, yhc, lev + 5, gen));
- return new CNode<>(gen, bmp, subinode);
- } else {
- if (xidx < yidx) {
- return new CNode<>(gen, bmp, x, y);
- } else {
- return new CNode<>(gen, bmp, y, x);
- }
- }
- } else {
- return new LNode<>(x.k, x.v, y.k, y.v);
- }
- }
}
Code Review / yangtools.git / blobdiff