// this should only be called from within read-only snapshots
@Override
- int cachedSize(final TrieMap<K, V> ct) {
+ int cachedSize(final TrieMap<?, ?> ct) {
int sz = csize;
if (sz == NO_SIZE) {
// We have not computed the size yet, do that now
// => 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);
+ narr [i] = ((INode<?, ?>) elem).copyToGen(ngen, ct);
} else if (elem != null) {
narr [i] = elem;
}
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) {
- final SNode<K, V> sn = (SNode<K, V>) array[0];
- return sn.copyTombed();
+ return ((SNode<K, V>) array[0]).copyTombed();
}
return this;
}
// 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 +
}
@Override
- int cachedSize(final TrieMap<K, V> ct) {
+ int cachedSize(final TrieMap<?, ?> ct) {
throw new UnsupportedOperationException();
}
this.mainnode = mainnode;
}
- MainNode<K, V> gcasRead(final TrieMap<K, V> ct) {
+ MainNode<K, V> gcasRead(final TrieMap<?, ?> ct) {
return GCAS_READ(ct);
}
- MainNode<K, V> GCAS_READ(final TrieMap<K, V> ct) {
+ private MainNode<K, V> GCAS_READ(final TrieMap<?, ?> ct) {
MainNode<K, V> m = /* READ */ mainnode;
MainNode<K, V> prevval = /* READ */ m.READ_PREV();
if (prevval == null) {
return GCAS_Complete(m, ct);
}
- private MainNode<K, V> GCAS_Complete(MainNode<K, V> m, final TrieMap<K, V> ct) {
+ private MainNode<K, V> GCAS_Complete(MainNode<K, V> m, final TrieMap<?, ?> ct) {
while (true) {
if (m == null) {
return null;
// complete the GCAS
final MainNode<K, V> prev = /* READ */ m.READ_PREV();
- final INode<K, V> ctr = ct.readRoot(true);
+ final Gen rdgen = ct.readRoot(true).gen;
if (prev == null) {
return m;
}
// ==> 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.isReadOnly()) {
+ if (rdgen == gen && !ct.isReadOnly()) {
// try to commit
if (m.CAS_PREV(prev, null)) {
return m;
}
}
- private boolean GCAS(final MainNode<K, V> old, final MainNode<K, V> n, final TrieMap<K, V> ct) {
+ private boolean GCAS(final MainNode<K, V> old, final MainNode<K, V> n, final TrieMap<?, ?> ct) {
n.WRITE_PREV(old);
if (MAINNODE_UPDATER.compareAndSet(this, old, n)) {
GCAS_Complete(n, ct);
return new INode<>(gen, cn);
}
- INode<K, V> copyToGen(final Gen ngen, final TrieMap<K, V> ct) {
+ INode<K, V> copyToGen(final Gen ngen, final TrieMap<?, ?> ct) {
return new INode<>(ngen, GCAS_READ(ct));
}
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, hc), gen);
+ 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) {
/**
* Removes the key associated with the given value.
*
- * @param v
+ * @param cond
* 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
+ * @return null if not successful, an Optional indicating the previous
* value otherwise
*/
- Optional<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 Object cond, 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);
+ return rec_remove(k, cond, 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,
+ private Optional<V> rec_remove(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!
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);
+ res = in.rec_remove(k, cond, 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);
+ res = rec_remove(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) && (v == null || v.equals(sn.v))) {
+ if (sn.hc == hc && ct.equal(sn.k, k) && (cond == null || cond.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);
}
final V value = entry.value();
- if (v != null && !v.equals(value)) {
+ if (cond != null && !cond.equals(value)) {
// Value does not match
return Optional.empty();
}
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);
+ final TNode<?, ?> tn = (TNode<?, ?>) nonlive;
+ final 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);
}
}
- int cachedSize(final TrieMap<K, V> ct) {
- MainNode<K, V> m = GCAS_READ(ct);
- return m.cachedSize(ct);
+ int cachedSize(final TrieMap<?, ?> ct) {
+ return GCAS_READ(ct).cachedSize(ct);
}
// /* this is a quiescent method! */
}
@Override
- int cachedSize(final TrieMap<K, V> ct) {
+ int cachedSize(final TrieMap<?, ?> ct) {
return listmap.size();
}
this.prev = prev;
}
- abstract int cachedSize(TrieMap<K, V> ct);
+ abstract int cachedSize(TrieMap<?, ?> ct);
final boolean CAS_PREV(final MainNode<K, V> oldval, final MainNode<K, V> nval) {
return PREV_UPDATER.compareAndSet(this, oldval, nval);
}
@Override
- int cachedSize(final TrieMap<K, V> ct) {
+ int cachedSize(final TrieMap<?, ?> ct) {
return 1;
}
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.ArrayList;
-import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
* @param <K> the type of keys maintained by this map
* @param <V> the type of mapped values
*/
-@SuppressWarnings({"unchecked", "rawtypes", "unused"})
public final class TrieMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K,V>, Serializable {
+ @SuppressWarnings("rawtypes")
private static final AtomicReferenceFieldUpdater<TrieMap, Object> ROOT_UPDATER =
AtomicReferenceFieldUpdater.newUpdater(TrieMap.class, Object.class, "root");
private static final long serialVersionUID = 1L;
return new INode<>(gen, new CNode<>(gen));
}
- final boolean CAS_ROOT(final Object ov, final Object nv) {
+ private boolean CAS_ROOT(final Object ov, final Object nv) {
checkState(!readOnly, "Attempted to modify a read-only snapshot");
- return ROOT_UPDATER.compareAndSet (this, ov, nv);
+ return ROOT_UPDATER.compareAndSet(this, ov, nv);
+ }
+
+ final INode<K, V> readRoot() {
+ return RDCSS_READ_ROOT(false);
}
// FIXME: abort = false by default
return RDCSS_READ_ROOT(abort);
}
- final INode<K, V> readRoot() {
+ private final INode<K, V> RDCSS_READ_ROOT() {
return RDCSS_READ_ROOT(false);
}
- final INode<K, V> RDCSS_READ_ROOT() {
- return RDCSS_READ_ROOT(false);
- }
-
- final INode<K, V> RDCSS_READ_ROOT(final boolean abort) {
- final Object r = /* READ */root;
+ private final INode<K, V> RDCSS_READ_ROOT(final boolean abort) {
+ final Object r = /* READ */ root;
if (r instanceof INode) {
return (INode<K, V>) r;
}
private INode<K, V> RDCSS_Complete(final boolean abort) {
while (true) {
- final Object r = /* READ */root;
+ final Object r = /* READ */ root;
if (r instanceof INode) {
return (INode<K, V>) r;
}
checkState(r instanceof RDCSS_Descriptor, "Unhandled root %s", r);
+ @SuppressWarnings("unchecked")
final RDCSS_Descriptor<K, V> desc = (RDCSS_Descriptor<K, V>) r;
final INode<K, V> ov = desc.old;
final MainNode<K, V> exp = desc.expectedmain;
private void inserthc(final K k, final int hc, final V v) {
// TODO: this is called from serialization only, which means we should not be observing any races,
// hence we should not need to pass down the entire tree, just equality (I think).
- final INode<K, V> r = RDCSS_READ_ROOT();
- final boolean success = r.rec_insert(k, v, hc, 0, null, this);
+ final boolean success = RDCSS_READ_ROOT().rec_insert(k, v, hc, 0, null, this);
Verify.verify(success, "Concurrent modification during serialization of map %s", this);
}
+ void add(final K key, final V value) {
+ final K k = checkNotNull(key);
+ inserthc(k, computeHash(k), checkNotNull(value));
+ }
+
private Optional<V> insertifhc(final K k, final int hc, final V v, final Object cond) {
Optional<V> res;
do {
return res;
}
+ @SuppressWarnings("unchecked")
private V lookuphc(final K k, final int hc) {
Object res;
do {
return (V) res;
}
- private Optional<V> removehc(final K k, final V v, final int hc) {
+ private Optional<V> removehc(final K k, final Object cond, final int hc) {
Optional<V> res;
do {
// Keep looping as long as we do not get a reply
- res = RDCSS_READ_ROOT().rec_remove(k, v, hc, 0, null, this);
+ res = RDCSS_READ_ROOT().rec_remove(k, cond, hc, 0, null, this);
} while (res == null);
return res;
@Override
public V get(final Object key) {
+ @SuppressWarnings("unchecked")
final K k = (K) checkNotNull(key);
return lookuphc(k, computeHash(k));
}
+ @SuppressWarnings("null")
+ private static <V> V toNullable(final Optional<V> opt) {
+ return opt.orElse(null);
+ }
+
@Override
public V put(final K key, final V value) {
ensureReadWrite();
final K k = checkNotNull(key);
- return insertifhc(k, computeHash(k), checkNotNull(value), null).orElse(null);
- }
-
- void add(final K key, final V value) {
- final K k = checkNotNull(key);
- inserthc(k, computeHash(k), checkNotNull(value));
+ return toNullable(insertifhc(k, computeHash(k), checkNotNull(value), null));
}
@Override
public V remove(final Object key) {
ensureReadWrite();
+ @SuppressWarnings("unchecked")
final K k = (K) checkNotNull(key);
- return removehc(k, (V) null, computeHash(k)).orElse(null);
+ return toNullable(removehc(k, null, computeHash(k)));
}
@Override
public V putIfAbsent(final K key, final V value) {
ensureReadWrite();
final K k = checkNotNull(key);
- return insertifhc(k, computeHash(k), checkNotNull(value), ABSENT).orElse(null);
+ return toNullable(insertifhc(k, computeHash(k), checkNotNull(value), ABSENT));
}
@Override
public boolean remove(final Object key, final Object v) {
ensureReadWrite();
+ @SuppressWarnings("unchecked")
final K k = (K) checkNotNull(key);
- return removehc(k, (V) checkNotNull(v), computeHash(k)).isPresent();
+ return removehc(k, checkNotNull(v), computeHash(k)).isPresent();
}
@Override
public V replace(final K key, final V value) {
ensureReadWrite();
final K k = checkNotNull(key);
- return insertifhc (k, computeHash(k), checkNotNull(value), PRESENT).orElse(null);
+ return toNullable(insertifhc(k, computeHash(k), checkNotNull(value), PRESENT));
}
/***
}
private int cachedSize() {
- INode<K, V> r = RDCSS_READ_ROOT ();
- return r.cachedSize (this);
+ return RDCSS_READ_ROOT().cachedSize (this);
}
@Override
throw new NoSuchElementException();
}
- Entry<K, V> r = null;
+ final Entry<K, V> r;
if (subiter != null) {
- r = subiter.next ();
- checkSubiter ();
+ r = subiter.next();
+ checkSubiter();
} else {
r = current;
- advance ();
+ advance();
}
lastReturned = r;
Entry<K, V> nextEntry(final Entry<K, V> rr) {
return new Entry<K, V>() {
+ @SuppressWarnings("null")
private V updated = null;
@Override
// @inline
void initialize () {
// assert (ct.isReadOnly ());
- INode<K, V> r = ct.RDCSS_READ_ROOT ();
- readin (r);
+ readin(ct.RDCSS_READ_ROOT());
}
void advance () {
}
}
- protected TrieMapIterator<K, V> newIterator (final int _lev, final TrieMap<K, V> _ct, final boolean _mustInit) {
+ protected TrieMapIterator<K, V> newIterator(final int _lev, final TrieMap<K, V> _ct, final boolean _mustInit) {
return new TrieMapIterator<> (_lev, _ct, _mustInit);
}
- protected void dupTo (final TrieMapIterator<K, V> it) {
+ protected void dupTo(final TrieMapIterator<K, V> it) {
it.level = this.level;
it.ct = this.ct;
it.depth = this.depth;
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() {
checkState(lastReturned != null);
if (!(o instanceof Entry)) {
return false;
}
- final Entry<?, ?> e = (Entry<K, V>) o;
+ final Entry<?, ?> e = (Entry<?, ?>) o;
final Object key = e.getKey();
if (key == null) {
return false;
Code Review / yangtools.git / commitdiff