import java.util.Collection;
/**
- * Abstract base class for key set views of a TrieMap
+ * Abstract base class for key set views of a TrieMap.
*
* @author Robert Varga
*
this(gen, 0, EMPTY_ARRAY);
}
- static <K, V> MainNode<K,V> dual(final SNode<K, V> x, final K k, final V v, final int hc, final int lev,
+ static <K, V> MainNode<K,V> dual(final SNode<K, V> x, final K key, final V value, final int hc, final int lev,
final Gen gen) {
- return dual(x, x.hc, new SNode<>(k, v, hc), hc, lev, gen);
+ return dual(x, x.hc, new SNode<>(key, value, hc), hc, lev, gen);
}
private static <K, V> MainNode<K,V> dual(final SNode<K, V> x, final int xhc, final SNode<K, V> y, final int yhc,
CNode<K, V> insertedAt(final int pos, final int flag, final BasicNode nn, final Gen gen) {
int len = array.length;
- int bmp = bitmap;
BasicNode[] narr = new BasicNode[len + 1];
System.arraycopy(array, 0, narr, 0, pos);
narr [pos] = nn;
System.arraycopy(array, pos, narr, pos + 1, len - pos);
- return new CNode<>(gen, bmp | flag, narr);
+ return new CNode<>(gen, bitmap | flag, narr);
}
/**
// }
@Override
- public String toString () {
+ public String toString() {
// val elems = collectLocalElems
// "CNode(sz: %d; %s)".format(elems.size,
// elems.sorted.mkString(", "))
* Number of hash bits consumed in each CNode level.
*/
static final int LEVEL_BITS = 5;
- static {
- verify(LEVEL_BITS == IntMath.log2(BITMAP_BITS, RoundingMode.UNNECESSARY));
- }
/**
* Maximum depth of a TrieMap.
*/
static final int MAX_DEPTH = 7;
+
static {
+ verify(LEVEL_BITS == IntMath.log2(BITMAP_BITS, RoundingMode.UNNECESSARY));
verify(MAX_DEPTH == IntMath.divide(HASH_BITS, LEVEL_BITS, RoundingMode.CEILING));
}
}
*/
interface EntryNode<K, V> extends Entry<K, V> {
@Override
- default public V setValue(final V value) {
+ default V setValue(final V value) {
throw new UnsupportedOperationException();
}
}
return fn.READ_PREV();
}
- // Tail recursion: return GCAS_Complete (/* READ */ mainnode, ct);
+ // Tail recursion: return GCAS_Complete(/* READ */ mainnode, ct);
m = /* READ */ mainnode;
continue;
}
return m;
}
- // Tail recursion: return GCAS_Complete (m, ct);
+ // Tail recursion: return GCAS_Complete(m, ct);
continue;
}
*
* @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 rec_insert(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 rec_insert(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,
return in.rec_insert(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;
}
}
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);
}
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);
+ return GCAS(cn, ncnode, ct);
} else if (m instanceof TNode) {
clean(parent, ct, lev - LEVEL_BITS);
return false;
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 rec_insertif(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,
}
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 (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();
}
String string(final int lev) {
return "INode";
}
-}
\ No newline at end of file
+}
public boolean remove(final Object o) {
throw unsupported();
}
+
@Override
public boolean retainAll(final Collection<?> c) {
throw unsupported();
import java.util.function.Function;
/**
- * An immutable TrieMap
+ * An immutable TrieMap.
*
* @author Robert Varga
*
}
@Override
- public final TrieMap<K, V> mutableSnapshot() {
+ public TrieMap<K, V> mutableSnapshot() {
return new MutableTrieMap<>(equiv(), new INode<>(new Gen(), root.gcasRead(this)));
}
this(LNodeEntries.map(k1, v1, k2, v2), 2);
}
- LNode<K, V> insertChild( final K k, final V v) {
- return new LNode<>(entries.insert(k, v), size + 1);
+ LNode<K, V> insertChild( final K key, final V value) {
+ return new LNode<>(entries.insert(key, value), size + 1);
}
MainNode<K, V> removeChild(final LNodeEntry<K, V> entry, final int hc) {
return new LNode<>(map, size - 1);
}
- MainNode<K, V> replaceChild(final LNodeEntry<K, V> entry, final V v) {
- return new LNode<>(entries.replace(entry, v), size);
+ MainNode<K, V> replaceChild(final LNodeEntry<K, V> entry, final V value) {
+ return new LNode<>(entries.replace(entry, value), size);
}
- LNodeEntry<K, V> get(final Equivalence<? super K> equiv, final K k) {
- return entries.findEntry(equiv, k);
+ LNodeEntry<K, V> get(final Equivalence<? super K> equiv, final K key) {
+ return entries.findEntry(equiv, key);
}
LNodeEntries<K, V> entries() {
import com.google.common.base.VerifyException;
/**
- * Similar to Scala's ListMap, this is a single-linked list of set of map entries. Aside from the Set contract, this
- * class fulfills the requirements for an immutable map entryset.
+ * Similar to Scala's ListMap, this is a single-linked list of set of map entries. Aside from the java.util.Set
+ * contract, this class fulfills the requirements for an immutable map entryset.
*
* @author Robert Varga
*
*/
abstract class LNodeEntries<K, V> extends LNodeEntry<K, V> {
private static final class Single<K, V> extends LNodeEntries<K, V> {
- Single(final K k, final V v) {
- super(k, v);
+ Single(final K key, final V value) {
+ super(key, value);
}
@Override
LNodeEntries<K, V> next;
// Used in remove() only
- Multiple(final LNodeEntries<K, V> e) {
- this(e.getKey(), e.getValue(), null);
+ Multiple(final LNodeEntries<K, V> entry) {
+ this(entry.getKey(), entry.getValue(), null);
}
- Multiple(final K k, final V v, final LNodeEntries<K, V> next) {
- super(k, v);
+ Multiple(final K key, final V value, final LNodeEntries<K, V> next) {
+ super(key, value);
this.next = next;
}
}
}
- LNodeEntries(final K k, final V v) {
- super(k, v);
+ LNodeEntries(final K key, final V value) {
+ super(key, value);
}
static <K,V> LNodeEntries<K, V> map(final K k1, final V v1, final K k2, final V v2) {
return new Multiple<>(key, value, this);
}
- final LNodeEntries<K, V> replace(final LNodeEntry<K, V> entry, final V v) {
+ final LNodeEntries<K, V> replace(final LNodeEntry<K, V> entry, final V value) {
final LNodeEntries<K, V> removed;
- return (removed = remove(entry)) == null ? new Single<>(entry.getKey(), v)
- : new Multiple<>(entry.getKey(), v, removed);
+ return (removed = remove(entry)) == null ? new Single<>(entry.getKey(), value)
+ : new Multiple<>(entry.getKey(), value, removed);
}
final LNodeEntries<K, V> remove(final LNodeEntry<K, V> entry) {
import java.util.Iterator;
import java.util.Map.Entry;
-/***
- * Support for EntrySet operations required by the Map interface
+/**
+ * Support for EntrySet operations required by the Map interface.
*
* @param <K> the type of keys
* @param <V> the type of values
* {@link #setValue(Object)} methods cannot guarantee consistency with the base map and may produce surprising
* results when the map is concurrently modified, either directly or via another entry/iterator.
*
+ * <p>
* The behavior is similar to what Java 8's ConcurrentHashMap does, which is probably the most consistent handling
* of this case without requiring expensive and revalidation.
*/
*
* @implSpec
* This implementation returns the most uptodate value we have observed via this entry. It does not reflect
- * concurrent modifications, nor does it throw {@link IllegalStateException} if the entry is removed.
+ * concurrent modifications, nor does it throw {@link IllegalStateException} if the entry is removed.
*/
@Override
public V getValue() {
*
* @implSpec
* This implementation returns the most uptodate value we have observed via this entry. It does not reflect
- * concurrent modifications, nor does it throw {@link IllegalStateException} if the entry is removed.
+ * concurrent modifications, nor does it throw {@link IllegalStateException} if the entry is removed.
*/
@Override
public V setValue(final V value) {
while (true) {
final INode<K, V> r = RDCSS_READ_ROOT();
final MainNode<K, V> expmain = r.gcasRead(this);
- if (RDCSS_ROOT(r, expmain, r.copyToGen (new Gen(), this))) {
+ if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen(), this))) {
return new ImmutableTrieMap<>(r, equiv());
}
return new INode<>(gen, new CNode<>(gen));
}
- private void inserthc(final K k, final int hc, final V v) {
+ private void inserthc(final K key, final int hc, final V value) {
// 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 boolean success = RDCSS_READ_ROOT().rec_insert(k, v, hc, 0, null, this);
+ final boolean success = RDCSS_READ_ROOT().rec_insert(key, value, hc, 0, null, this);
Verify.verify(success, "Concurrent modification during serialization of map %s", this);
}
- private Optional<V> insertifhc(final K k, final int hc, final V v, final Object cond) {
+ private Optional<V> insertifhc(final K key, final int hc, final V value, final Object cond) {
Optional<V> res;
do {
// Keep looping as long as we do not get a reply
- res = RDCSS_READ_ROOT().rec_insertif(k, v, hc, cond, 0, null, this);
+ res = RDCSS_READ_ROOT().rec_insertif(key, value, hc, cond, 0, null, this);
} while (res == null);
return res;
}
- private Optional<V> removehc(final K k, final Object cond, final int hc) {
+ private Optional<V> removehc(final K key, 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, cond, hc, 0, null, this);
+ res = RDCSS_READ_ROOT().rec_remove(key, cond, hc, 0, null, this);
} while (res == null);
return res;
}
private boolean RDCSS_ROOT(final INode<K, V> ov, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
- final RDCSS_Descriptor<K, V> desc = new RDCSS_Descriptor<> (ov, expectedmain, nv);
+ final RDCSS_Descriptor<K, V> desc = new RDCSS_Descriptor<>(ov, expectedmain, nv);
if (CAS_ROOT(ov, desc)) {
RDCSS_Complete(false);
return /* READ */desc.committed;
volatile boolean committed = false;
- RDCSS_Descriptor (final INode<K, V> old, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
+ RDCSS_Descriptor(final INode<K, V> old, final MainNode<K, V> expectedmain, final INode<K, V> nv) {
this.old = old;
this.expectedmain = expectedmain;
this.nv = nv;
final V v;
final int hc;
- SNode(final K k, final V v, final int hc) {
- this.k = k;
- this.v = v;
+ SNode(final K key, final V value, final int hc) {
+ this.k = key;
+ this.v = value;
this.hc = hc;
}
public String toString() {
return EntryUtil.string(k, v);
}
-}
\ No newline at end of file
+}
final V v;
final int hc;
- TNode (final K k, final V v, final int hc) {
- this.k = k;
- this.v = v;
+ TNode(final K key, final V value, final int hc) {
+ this.k = key;
+ this.v = value;
this.hc = hc;
}
- TNode<K, V> copy () {
+ TNode<K, V> copy() {
return new TNode<>(k, v, hc);
}
- TNode<K, V> copyTombed () {
+ TNode<K, V> copyTombed() {
return new TNode<>(k, v, hc);
}
- SNode<K, V> copyUntombed () {
+ SNode<K, V> copyUntombed() {
return new SNode<>(k, v, hc);
}
public String toString() {
return EntryUtil.string(k, v);
}
-}
\ No newline at end of file
+}
import java.util.Set;
import java.util.concurrent.ConcurrentMap;
-/***
+/**
* This is a port of Scala's TrieMap class from the Scala Collections library. This implementation does not support
* null keys nor null values.
*
* Returns a snapshot of this TrieMap. This operation is lock-free and
* linearizable.
*
+ * <p>
* The snapshot is lazily updated - the first time some branch in the
* snapshot or this TrieMap are accessed, they are rewritten. This means
* that the work of rebuilding both the snapshot and this TrieMap is
* Returns a read-only snapshot of this TrieMap. This operation is lock-free
* and linearizable.
*
+ * <p>
* The snapshot is lazily updated - the first time some branch of this
* TrieMap are accessed, it is rewritten. The work of creating the snapshot
* is thus distributed across subsequent updates and accesses on this
* unlike when calling the `snapshot` method, but the obtained snapshot
* cannot be modified.
*
+ * <p>
* This method is used by other methods such as `size` and `iterator`.
*/
public abstract ImmutableTrieMap<K, V> immutableSnapshot();
/**
* Return an iterator over a TrieMap.
*
+ * <p>
* If this is a read-only snapshot, it would return a read-only iterator.
*
+ * <p>
* If it is the original TrieMap or a non-readonly snapshot, it would return
* an iterator that would allow for updates.
*
- * @return
+ * @return An iterator.
*/
abstract AbstractIterator<K, V> iterator();
/* internal methods provided for subclasses */
/**
- * Return an iterator over a TrieMap.
- * This is a read-only iterator.
+ * Return an iterator over a TrieMap. This is a read-only iterator.
*
- * @return
+ * @return A read-only iterator.
*/
final ImmutableIterator<K, V> immutableIterator() {
return new ImmutableIterator<>(immutableSnapshot());
return opt.orElse(null);
}
- final int computeHash(final K k) {
- return equiv.hash(k);
+ final int computeHash(final K key) {
+ return equiv.hash(key);
}
final Object writeReplace() throws ObjectStreamException {
/* private implementation methods */
@SuppressWarnings("unchecked")
- private V lookuphc(final K k, final int hc) {
+ private V lookuphc(final K key, final int hc) {
Object res;
do {
// Keep looping as long as RESTART is being indicated
- res = RDCSS_READ_ROOT().rec_lookup(k, hc, 0, null, this);
+ res = RDCSS_READ_ROOT().rec_lookup(key, hc, 0, null, this);
} while (res == RESTART);
return (V) res;
public class TestCNodeFlagCollision {
@Test
- public void testCNodeFlagCollision () {
+ public void testCNodeFlagCollision() {
final Map<Integer, Object> map = TrieMap.create();
final Integer z15169 = Integer.valueOf(15169);
final Integer z28336 = Integer.valueOf(28336);
assertSame(z15169, map.get(z15169));
assertNull(map.get(z28336));
- map.put (z28336, z28336);
+ map.put(z28336, z28336);
assertSame(z15169, map.get(z15169));
assertSame(z28336, map.get(z28336));
- map.remove (z15169);
+ map.remove(z15169);
assertNull(map.get(z15169));
assertSame(z28336, map.get(z28336));
- map.remove (z28336);
+ map.remove(z28336);
assertNull(map.get(z15169));
assertNull(map.get(z28336));
public class TestCNodeInsertionIncorrectOrder {
@Test
- public void testCNodeInsertionIncorrectOrder () {
+ public void testCNodeInsertionIncorrectOrder() {
final Map<Integer, Integer> map = TrieMap.create();
final Integer z3884 = Integer.valueOf(3884);
final Integer z4266 = Integer.valueOf(4266);
import org.junit.Test;
public class TestConcurrentMapPutIfAbsent {
- private static final int COUNT = 50*1000;
+ private static final int COUNT = 50 * 1000;
@Test
- public void testConcurrentMapPutIfAbsent () {
+ public void testConcurrentMapPutIfAbsent() {
final ConcurrentMap<Object, Object> map = TrieMap.create();
for (int i = 0; i < COUNT; i++) {
- assertNull(map.putIfAbsent (i, i));
+ assertNull(map.putIfAbsent(i, i));
assertEquals(Integer.valueOf(i), map.putIfAbsent(i, i));
}
}
import org.junit.Test;
public class TestConcurrentMapRemove {
- private static final int COUNT = 50*1000;
+ private static final int COUNT = 50 * 1000;
@Test
- public void testConcurrentMapRemove () {
+ public void testConcurrentMapRemove() {
final ConcurrentMap<Integer, Object> map = TrieMap.create();
for (int i = 128; i < COUNT; i++) {
import org.junit.Test;
public class TestConcurrentMapReplace {
- private static final int COUNT = 50*1000;
+ private static final int COUNT = 50 * 1000;
@Test
- public void testConcurrentMapReplace () {
+ public void testConcurrentMapReplace() {
final ConcurrentMap<Integer, Object> map = TrieMap.create();
for (int i = 0; i < COUNT; i++) {
}
@Test
- public void testDelete () {
+ public void testDelete() {
final TrieMap<Integer, Integer> bt = TrieMap.create();
for (int i = 0; i < 10000; i++) {
assertNull(lookup);
}
- bt.toString ();
+ bt.toString();
}
/**
}
}
- private static void checkAddInsert (final TrieMap<Integer, Integer> bt, final int k) {
+ private static void checkAddInsert(final TrieMap<Integer, Integer> bt, final int k) {
final Integer v = Integer.valueOf(k);
- bt.remove (v);
+ bt.remove(v);
Integer foundV = bt.get(v);
assertNull(foundV);
- assertNull(bt.put (v, v));
+ assertNull(bt.put(v, v));
foundV = bt.get(v);
assertEquals(v, foundV);
public class TestHashCollisions {
@Test
- public void testHashCollisions () {
+ public void testHashCollisions() {
final TrieMap<Object, Object> bt = TrieMap.create();
insertStrings(bt);
removeChars(bt);
}
- private static void insertChars (final TrieMap<Object, Object> bt) {
+ private static void insertChars(final TrieMap<Object, Object> bt) {
assertNull(bt.put('a', 'a'));
assertNull(bt.put('b', 'b'));
assertNull(bt.put('c', 'c'));
assertEquals('e', bt.put('e', 'e'));
}
- private static void insertStrings (final TrieMap<Object, Object> bt) {
+ private static void insertStrings(final TrieMap<Object, Object> bt) {
assertNull(bt.put("a", "a"));
assertNull(bt.put("b", "b"));
assertNull(bt.put("c", "c"));
assertEquals("e", bt.put("e", "e"));
}
- private static void insertBytes (final TrieMap<Object, Object> bt) {
+ private static void insertBytes(final TrieMap<Object, Object> bt) {
for (byte i = 0; i < 128 && i >= 0; i++) {
final Byte bigB = Byte.valueOf(i);
assertNull(bt.put(bigB, bigB));
}
}
- private static void insertInts (final TrieMap<Object, Object> bt) {
+ private static void insertInts(final TrieMap<Object, Object> bt) {
for (int i = 0; i < 128; i++) {
final Integer bigI = Integer.valueOf(i);
assertNull(bt.put(bigI, bigI));
}
}
- private static void removeChars (final TrieMap<Object, Object> bt) {
+ private static void removeChars(final TrieMap<Object, Object> bt) {
assertNotNull(bt.get('a'));
assertNotNull(bt.get('b'));
assertNotNull(bt.get('c'));
assertNull(bt.get('e'));
}
- private static void removeStrings (final TrieMap<Object, Object> bt) {
+ private static void removeStrings(final TrieMap<Object, Object> bt) {
assertNotNull(bt.get("a"));
assertNotNull(bt.get("b"));
assertNotNull(bt.get("c"));
assertNull(bt.get("e"));
}
- private static void removeInts (final TrieMap<Object, Object> bt) {
+ private static void removeInts(final TrieMap<Object, Object> bt) {
for (int i = 0; i < 128; i++) {
final Integer bigI = Integer.valueOf(i);
assertNotNull(bt.get(bigI));
}
}
- private static void removeBytes (final TrieMap<Object, Object> bt) {
+ private static void removeBytes(final TrieMap<Object, Object> bt) {
for (byte i = 0; i < 128 && i >= 0; i++) {
final Byte bigB = Byte.valueOf(i);
assertNotNull(bt.get(bigB));
private static final int COUNT = 50000;
@Test
- public void testHashCollisionsRemoveIterator () {
+ public void testHashCollisionsRemoveIterator() {
final Map<Object, Object> bt = TrieMap.create();
for (int j = 0; j < COUNT; j++) {
bt.put(Integer.valueOf(j), Integer.valueOf(j));
public class TestInsert {
@Test
- public void testInsert () {
+ public void testInsert() {
final TrieMap<Object, Object> bt = TrieMap.create();
assertNull(bt.put("a", "a"));
assertNull(bt.put("b", "b"));
assertNull(bt.put("e", "b"));
for (int i = 0; i < 10000; i++) {
- assertNull(bt.put(Integer.valueOf (i), Integer.valueOf(i)));
+ assertNull(bt.put(Integer.valueOf(i), Integer.valueOf(i)));
final Object lookup = bt.get(Integer.valueOf(i));
assertEquals(Integer.valueOf(i), lookup);
}
public void testMapIterator() {
final Random random = new Random();
- for (int i = 0; i < 60 * 1000; i+= 400 + random.nextInt(400)) {
+ for (int i = 0; i < 60 * 1000; i += 400 + random.nextInt(400)) {
final Map<Integer, Integer> bt = TrieMap.create();
for (int j = 0; j < i; j++) {
assertNull(bt.put(Integer.valueOf(j), Integer.valueOf(j)));
for (Entry<Integer, Integer> e : bt.entrySet()) {
assertSame(e.getValue(), bt.get(e.getKey()));
e.setValue(e.getValue() + 1);
- assertEquals((Object)e.getValue(), e.getKey () + 1);
+ assertEquals((Object)e.getValue(), e.getKey() + 1);
assertEquals(e.getValue(), bt.get(e.getKey()));
e.setValue(e.getValue() - 1);
}
final Iterator<Integer> it = bt.keySet().iterator();
- while(it.hasNext()) {
- final Integer k = it.next ();
+ while (it.hasNext()) {
+ final Integer k = it.next();
assertTrue(bt.containsKey(k));
it.remove();
assertFalse(bt.containsKey(k));
}
- assertEquals(0, bt.size ());
- assertTrue(bt.isEmpty ());
+ assertEquals(0, bt.size());
+ assertTrue(bt.isEmpty());
}
}
public void testMapImmutableIterator() {
final Random random = new Random();
- for (int i = 0; i < 60 * 1000; i+= 400 + random.nextInt(400)) {
+ for (int i = 0; i < 60 * 1000; i += 400 + random.nextInt(400)) {
final Map<Integer, Integer> bt = TrieMap.create();
for (int j = 0; j < i; j++) {
assertNull(bt.put(Integer.valueOf(j), Integer.valueOf(j)));
private static final int COUNT = 50 * 1000;
@Test
- public void testMultiThreadAddDelete () throws InterruptedException {
+ public void testMultiThreadAddDelete() throws InterruptedException {
for (int j = 0; j < RETRIES; j++) {
final Map<Object, Object> bt = TrieMap.create();
}
});
}
- es.shutdown ();
+ es.shutdown();
es.awaitTermination(5, TimeUnit.MINUTES);
}
final ExecutorService es = Executors.newFixedThreadPool(N_THREADS);
for (int i = 0; i < N_THREADS; i++) {
final int threadNo = i;
- es.execute (() -> {
+ es.execute(() -> {
for (int k = 0; k < COUNT; k++) {
if (k % N_THREADS == threadNo) {
- bt.remove (Integer.valueOf (k));
+ bt.remove(Integer.valueOf(k));
}
}
});
}
- es.shutdown ();
+ es.shutdown();
es.awaitTermination(5, TimeUnit.MINUTES);
}
- assertEquals(0, bt.size ());
+ assertEquals(0, bt.size());
assertTrue(bt.isEmpty());
{
- final ExecutorService es = Executors.newFixedThreadPool (N_THREADS);
+ final ExecutorService es = Executors.newFixedThreadPool(N_THREADS);
for (int i = 0; i < N_THREADS; i++) {
final int threadNo = i;
- es.execute (new Runnable () {
+ es.execute(new Runnable() {
@Override
- public void run () {
+ public void run() {
for (int j = 0; j < COUNT; j++) {
if (j % N_THREADS == threadNo) {
- try {
- bt.put (Integer.valueOf (j), Integer.valueOf (j));
- if (!bt.containsKey (Integer.valueOf (j))) {
- System.out.println (j);
- }
- bt.remove (Integer.valueOf (j));
- if (bt.containsKey (Integer.valueOf (j))) {
- System.out.println (-j);
- }
- } catch (Throwable t) {
- t.printStackTrace ();
+ bt.put(Integer.valueOf(j), Integer.valueOf(j));
+ if (!bt.containsKey(Integer.valueOf(j))) {
+ System.out.println(j);
+ }
+ bt.remove(Integer.valueOf(j));
+ if (bt.containsKey(Integer.valueOf(j))) {
+ System.out.println(-j);
}
}
}
}
});
}
- es.shutdown ();
+ es.shutdown();
es.awaitTermination(5, TimeUnit.MINUTES);
}
public class TestMultiThreadInserts {
@Test
- public void testMultiThreadInserts () throws InterruptedException{
+ public void testMultiThreadInserts() throws InterruptedException {
final int nThreads = 2;
final ExecutorService es = Executors.newFixedThreadPool(nThreads);
final TrieMap<Object, Object> bt = TrieMap.create();
for (int i = 0; i < nThreads; i++) {
final int threadNo = i;
- es.execute (() -> {
+ es.execute(() -> {
for (int j = 0; j < 500 * 1000; j++) {
if (j % nThreads == threadNo) {
- bt.put (Integer.valueOf(j), Integer.valueOf(j));
+ bt.put(Integer.valueOf(j), Integer.valueOf(j));
}
}
});
}
- es.shutdown ();
+ es.shutdown();
es.awaitTermination(5, TimeUnit.MINUTES);
for (int j = 0; j < 500 * 1000; j++) {
private static final int NTHREADS = 7;
@Test
- public void testMultiThreadMapIterator () throws InterruptedException {
+ public void testMultiThreadMapIterator() throws InterruptedException {
final Map<Object, Object> bt = TrieMap.create();
for (int j = 0; j < 50 * 1000; j++) {
for (final Object o : getObjects(j)) {
- bt.put (o, o);
+ bt.put(o, o);
}
}
- // System.out.println ("Size of initialized map is " + bt.size ());
+ // System.out.println("Size of initialized map is " + bt.size());
int count = 0;
{
final ExecutorService es = Executors.newFixedThreadPool(NTHREADS);
final ExecutorService es = Executors.newFixedThreadPool(NTHREADS);
for (int i = 0; i < NTHREADS; i++) {
final int threadNo = i;
- es.execute (() -> {
- for (final Iterator<Map.Entry<Object, Object>> it = bt.entrySet ().iterator(); it.hasNext();) {
+ es.execute(() -> {
+ for (final Iterator<Map.Entry<Object, Object>> it = bt.entrySet().iterator(); it.hasNext();) {
final Entry<Object, Object> e = it.next();
- Object key = e.getKey ();
- if (accepts (threadNo, NTHREADS, key)) {
- if (null == bt.get (key)) {
- // System.out.println (key);
+ Object key = e.getKey();
+ if (accepts(threadNo, NTHREADS, key)) {
+ if (null == bt.get(key)) {
+ // System.out.println(key);
}
it.remove();
- if (null != bt.get (key)) {
- // System.out.println (key);
+ if (null != bt.get(key)) {
+ // System.out.println(key);
}
- removed.put (key, key);
+ removed.put(key, key);
}
}
});
es.awaitTermination(5, TimeUnit.MINUTES);
}
- count = 0;
- for (final Object value : bt.keySet ()) {
- value.toString ();
- count++;
- }
- for (final Object o : bt.keySet ()) {
- if (!removed.contains (bt.get (o))) {
- System.out.println ("Not removed: " + o);
- }
- }
- assertEquals(0, count);
- assertEquals(0, bt.size ());
- assertTrue(bt.isEmpty ());
+ count = 0;
+ for (final Object value : bt.keySet()) {
+ value.toString();
+ count++;
+ }
+ for (final Object o : bt.keySet()) {
+ if (!removed.contains(bt.get(o))) {
+ System.out.println("Not removed: " + o);
+ }
+ }
+ assertEquals(0, count);
+ assertEquals(0, bt.size());
+ assertTrue(bt.isEmpty());
}
- protected static boolean accepts (final int threadNo, final int nThreads, final Object key) {
+ protected static boolean accepts(final int threadNo, final int nrThreads, final Object key) {
final int val = getKeyValue(key);
- return val >= 0 ? val % nThreads == threadNo : false;
+ return val >= 0 ? val % nrThreads == threadNo : false;
}
- private static int getKeyValue (final Object key) {
+ private static int getKeyValue(final Object key) {
if (key instanceof Integer) {
return ((Integer) key).intValue();
} else if (key instanceof Character) {
import org.junit.Before;
import org.junit.Test;
-/***
- *
+/**
* Test that read-only iterators do not allow for any updates.
* Test that non read-only iterators allow for updates.
- *
*/
public class TestReadOnlyAndUpdatableIterators {
private static final int MAP_SIZE = 200;
}
@Test
- public void testIterator () {
+ public void testIterator() {
Iterator<Entry<Integer, Integer>> it = bt.iterator();
- it.next().setValue (0);
+ it.next().setValue(0);
it.remove();
// All changes are done on the original map
}
@Test
- public void testSnapshotIterator () {
+ public void testSnapshotIterator() {
TrieMap<Integer, Integer> snapshot = bt.mutableSnapshot();
Iterator<Entry<Integer, Integer>> it = snapshot.iterator();
it.next().setValue(0);
// All changes are done on the snapshot, not on the original map
// Map size should remain unchanged
- assertEquals(MAP_SIZE, bt.size ());
+ assertEquals(MAP_SIZE, bt.size());
// snapshot size was changed
- assertEquals(MAP_SIZE-1, snapshot.size ());
+ assertEquals(MAP_SIZE - 1, snapshot.size());
}
}
Code Review / yangtools.git / commitdiff