--- a/jdk/src/java.base/share/classes/java/util/concurrent/ConcurrentMap.java Fri Jan 29 11:48:00 2016 -0800
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/ConcurrentMap.java Fri Jan 29 11:49:37 2016 -0800
@@ -301,19 +301,15 @@
*
* @implSpec
* The default implementation is equivalent to the following steps for this
- * {@code map}, then returning the current value or {@code null} if now
- * absent:
+ * {@code map}:
*
* <pre> {@code
- * if (map.get(key) == null) {
- * V newValue = mappingFunction.apply(key);
- * if (newValue != null)
- * return map.putIfAbsent(key, newValue);
- * }}</pre>
- *
- * The default implementation may retry these steps when multiple
- * threads attempt updates including potentially calling the mapping
- * function multiple times.
+ * V oldValue, newValue;
+ * return ((oldValue = map.get(key)) == null
+ * && (newValue = mappingFunction.apply(key)) != null
+ * && (oldValue = map.putIfAbsent(key, newValue)) == null)
+ * ? newValue
+ * : oldValue;}</pre>
*
* <p>This implementation assumes that the ConcurrentMap cannot contain null
* values and {@code get()} returning null unambiguously means the key is
@@ -323,16 +319,19 @@
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
+ * @throws IllegalArgumentException {@inheritDoc}
* @since 1.8
*/
@Override
default V computeIfAbsent(K key,
Function<? super K, ? extends V> mappingFunction) {
Objects.requireNonNull(mappingFunction);
- V v, newValue;
- return ((v = get(key)) == null &&
- (newValue = mappingFunction.apply(key)) != null &&
- (v = putIfAbsent(key, newValue)) == null) ? newValue : v;
+ V oldValue, newValue;
+ return ((oldValue = get(key)) == null
+ && (newValue = mappingFunction.apply(key)) != null
+ && (oldValue = putIfAbsent(key, newValue)) == null)
+ ? newValue
+ : oldValue;
}
/**
@@ -340,22 +339,19 @@
*
* @implSpec
* The default implementation is equivalent to performing the following
- * steps for this {@code map}, then returning the current value or
- * {@code null} if now absent:
+ * steps for this {@code map}:
*
* <pre> {@code
- * if (map.get(key) != null) {
- * V oldValue = map.get(key);
+ * for (V oldValue; (oldValue = map.get(key)) != null; ) {
* V newValue = remappingFunction.apply(key, oldValue);
- * if (newValue != null)
- * map.replace(key, oldValue, newValue);
- * else
- * map.remove(key, oldValue);
- * }}</pre>
- *
- * The default implementation may retry these steps when multiple threads
- * attempt updates including potentially calling the remapping function
- * multiple times.
+ * if ((newValue == null)
+ * ? map.remove(key, oldValue)
+ * : map.replace(key, oldValue, newValue))
+ * return newValue;
+ * }
+ * return null;}</pre>
+ * When multiple threads attempt updates, map operations and the
+ * remapping function may be called multiple times.
*
* <p>This implementation assumes that the ConcurrentMap cannot contain null
* values and {@code get()} returning null unambiguously means the key is
@@ -365,22 +361,21 @@
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
+ * @throws IllegalArgumentException {@inheritDoc}
* @since 1.8
*/
@Override
default V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
- V oldValue;
- while ((oldValue = get(key)) != null) {
+ for (V oldValue; (oldValue = get(key)) != null; ) {
V newValue = remappingFunction.apply(key, oldValue);
- if (newValue != null) {
- if (replace(key, oldValue, newValue))
- return newValue;
- } else if (remove(key, oldValue))
- return null;
+ if ((newValue == null)
+ ? remove(key, oldValue)
+ : replace(key, oldValue, newValue))
+ return newValue;
}
- return oldValue;
+ return null;
}
/**
@@ -388,27 +383,23 @@
*
* @implSpec
* The default implementation is equivalent to performing the following
- * steps for this {@code map}, then returning the current value or
- * {@code null} if absent:
+ * steps for this {@code map}:
*
* <pre> {@code
- * V oldValue = map.get(key);
- * V newValue = remappingFunction.apply(key, oldValue);
- * if (oldValue != null ) {
- * if (newValue != null)
- * map.replace(key, oldValue, newValue);
- * else
- * map.remove(key, oldValue);
- * } else {
- * if (newValue != null)
- * map.putIfAbsent(key, newValue);
- * else
+ * for (;;) {
+ * V oldValue = map.get(key);
+ * V newValue = remappingFunction.apply(key, oldValue);
+ * if (newValue != null) {
+ * if ((oldValue != null)
+ * ? map.replace(key, oldValue, newValue)
+ * : map.putIfAbsent(key, newValue) == null)
+ * return newValue;
+ * } else if (oldValue == null || map.remove(key, oldValue)) {
* return null;
+ * }
* }}</pre>
- *
- * The default implementation may retry these steps when multiple
- * threads attempt updates including potentially calling the remapping
- * function multiple times.
+ * When multiple threads attempt updates, map operations and the
+ * remapping function may be called multiple times.
*
* <p>This implementation assumes that the ConcurrentMap cannot contain null
* values and {@code get()} returning null unambiguously means the key is
@@ -418,50 +409,29 @@
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
+ * @throws IllegalArgumentException {@inheritDoc}
* @since 1.8
*/
@Override
default V compute(K key,
- BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
- Objects.requireNonNull(remappingFunction);
- V oldValue = get(key);
- for (;;) {
- V newValue = remappingFunction.apply(key, oldValue);
- if (newValue == null) {
- // delete mapping
- if (oldValue != null || containsKey(key)) {
- // something to remove
- if (remove(key, oldValue)) {
- // removed the old value as expected
- return null;
+ BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+ retry: for (;;) {
+ V oldValue = get(key);
+ // if putIfAbsent fails, opportunistically use its return value
+ haveOldValue: for (;;) {
+ V newValue = remappingFunction.apply(key, oldValue);
+ if (newValue != null) {
+ if (oldValue != null) {
+ if (replace(key, oldValue, newValue))
+ return newValue;
}
-
- // some other value replaced old value. try again.
- oldValue = get(key);
- } else {
- // nothing to do. Leave things as they were.
+ else if ((oldValue = putIfAbsent(key, newValue)) == null)
+ return newValue;
+ else continue haveOldValue;
+ } else if (oldValue == null || remove(key, oldValue)) {
return null;
}
- } else {
- // add or replace old mapping
- if (oldValue != null) {
- // replace
- if (replace(key, oldValue, newValue)) {
- // replaced as expected.
- return newValue;
- }
-
- // some other value replaced old value. try again.
- oldValue = get(key);
- } else {
- // add (replace if oldValue was null)
- if ((oldValue = putIfAbsent(key, newValue)) == null) {
- // replaced
- return newValue;
- }
-
- // some other value replaced old value. try again.
- }
+ continue retry;
}
}
}
@@ -471,21 +441,25 @@
*
* @implSpec
* The default implementation is equivalent to performing the following
- * steps for this {@code map}, then returning the current value or
- * {@code null} if absent:
+ * steps for this {@code map}:
*
* <pre> {@code
- * V oldValue = map.get(key);
- * V newValue = (oldValue == null) ? value :
- * remappingFunction.apply(oldValue, value);
- * if (newValue == null)
- * map.remove(key);
- * else
- * map.put(key, newValue);}</pre>
- *
- * <p>The default implementation may retry these steps when multiple
- * threads attempt updates including potentially calling the remapping
- * function multiple times.
+ * for (;;) {
+ * V oldValue = map.get(key);
+ * if (oldValue != null) {
+ * V newValue = remappingFunction.apply(oldValue, value);
+ * if (newValue != null) {
+ * if (map.replace(key, oldValue, newValue))
+ * return newValue;
+ * } else if (map.remove(key, oldValue)) {
+ * return null;
+ * }
+ * } else if (map.putIfAbsent(key, value) == null) {
+ * return value;
+ * }
+ * }}</pre>
+ * When multiple threads attempt updates, map operations and the
+ * remapping function may be called multiple times.
*
* <p>This implementation assumes that the ConcurrentMap cannot contain null
* values and {@code get()} returning null unambiguously means the key is
@@ -495,6 +469,7 @@
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
+ * @throws IllegalArgumentException {@inheritDoc}
* @since 1.8
*/
@Override
@@ -502,20 +477,23 @@
BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
Objects.requireNonNull(value);
- V oldValue = get(key);
- for (;;) {
- if (oldValue != null) {
- V newValue = remappingFunction.apply(oldValue, value);
- if (newValue != null) {
- if (replace(key, oldValue, newValue))
- return newValue;
- } else if (remove(key, oldValue)) {
- return null;
- }
- oldValue = get(key);
- } else {
- if ((oldValue = putIfAbsent(key, value)) == null) {
- return value;
+ retry: for (;;) {
+ V oldValue = get(key);
+ // if putIfAbsent fails, opportunistically use its return value
+ haveOldValue: for (;;) {
+ if (oldValue != null) {
+ V newValue = remappingFunction.apply(oldValue, value);
+ if (newValue != null) {
+ if (replace(key, oldValue, newValue))
+ return newValue;
+ } else if (remove(key, oldValue)) {
+ return null;
+ }
+ continue retry;
+ } else {
+ if ((oldValue = putIfAbsent(key, value)) == null)
+ return value;
+ continue haveOldValue;
}
}
}
--- a/jdk/test/java/util/Map/Defaults.java Fri Jan 29 11:48:00 2016 -0800
+++ b/jdk/test/java/util/Map/Defaults.java Fri Jan 29 11:49:37 2016 -0800
@@ -48,11 +48,14 @@
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentSkipListMap;
+import java.util.concurrent.atomic.AtomicBoolean;
import java.util.function.BiFunction;
+import java.util.function.Function;
import java.util.function.Supplier;
import org.testng.annotations.Test;
import org.testng.annotations.DataProvider;
+import static java.util.Objects.requireNonNull;
import static org.testng.Assert.fail;
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertTrue;
@@ -533,6 +536,191 @@
"Should throw NPE");
}
+ /** A function that flipflops between running two other functions. */
+ static <T,U,V> BiFunction<T,U,V> twoStep(AtomicBoolean b,
+ BiFunction<T,U,V> first,
+ BiFunction<T,U,V> second) {
+ return (t, u) -> {
+ boolean bb = b.get();
+ try {
+ return (b.get() ? first : second).apply(t, u);
+ } finally {
+ b.set(!bb);
+ }};
+ }
+
+ /**
+ * Simulates races by modifying the map within the mapping function.
+ */
+ @Test
+ public void testConcurrentMap_computeIfAbsent_racy() {
+ final ConcurrentMap<Long,Long> map = new ImplementsConcurrentMap<>();
+ final Long two = 2L;
+ Function<Long,Long> f, g;
+
+ // race not detected if function returns null
+ f = (k) -> { map.put(two, 42L); return null; };
+ assertNull(map.computeIfAbsent(two, f));
+ assertEquals(42L, (long)map.get(two));
+
+ map.clear();
+ f = (k) -> { map.put(two, 42L); return 86L; };
+ assertEquals(42L, (long)map.computeIfAbsent(two, f));
+ assertEquals(42L, (long)map.get(two));
+
+ // mapping function ignored if value already exists
+ map.put(two, 99L);
+ assertEquals(99L, (long)map.computeIfAbsent(two, f));
+ assertEquals(99L, (long)map.get(two));
+ }
+
+ /**
+ * Simulates races by modifying the map within the remapping function.
+ */
+ @Test
+ public void testConcurrentMap_computeIfPresent_racy() {
+ final AtomicBoolean b = new AtomicBoolean(true);
+ final ConcurrentMap<Long,Long> map = new ImplementsConcurrentMap<>();
+ final Long two = 2L;
+ BiFunction<Long,Long,Long> f, g;
+
+ for (Long val : new Long[] { null, 86L }) {
+ map.clear();
+
+ // Function not invoked if no mapping exists
+ f = (k, v) -> { map.put(two, 42L); return val; };
+ assertNull(map.computeIfPresent(two, f));
+ assertNull(map.get(two));
+
+ map.put(two, 42L);
+ f = (k, v) -> { map.put(two, 86L); return val; };
+ g = (k, v) -> {
+ assertSame(two, k);
+ assertEquals(86L, (long)v);
+ return null;
+ };
+ assertNull(map.computeIfPresent(two, twoStep(b, f, g)));
+ assertFalse(map.containsKey(two));
+ assertTrue(b.get());
+
+ map.put(two, 42L);
+ f = (k, v) -> { map.put(two, 86L); return val; };
+ g = (k, v) -> {
+ assertSame(two, k);
+ assertEquals(86L, (long)v);
+ return 99L;
+ };
+ assertEquals(99L, (long)map.computeIfPresent(two, twoStep(b, f, g)));
+ assertTrue(map.containsKey(two));
+ assertTrue(b.get());
+ }
+ }
+
+ @Test
+ public void testConcurrentMap_compute_simple() {
+ final ConcurrentMap<Long,Long> map = new ImplementsConcurrentMap<>();
+ BiFunction<Long,Long,Long> fun = (k, v) -> ((v == null) ? 0L : k + v);
+ assertEquals(Long.valueOf(0L), map.compute(3L, fun));
+ assertEquals(Long.valueOf(3L), map.compute(3L, fun));
+ assertEquals(Long.valueOf(6L), map.compute(3L, fun));
+ assertNull(map.compute(3L, (k, v) -> null));
+ assertTrue(map.isEmpty());
+
+ assertEquals(Long.valueOf(0L), map.compute(new Long(3L), fun));
+ assertEquals(Long.valueOf(3L), map.compute(new Long(3L), fun));
+ assertEquals(Long.valueOf(6L), map.compute(new Long(3L), fun));
+ assertNull(map.compute(3L, (k, v) -> null));
+ assertTrue(map.isEmpty());
+ }
+
+ /**
+ * Simulates races by modifying the map within the remapping function.
+ */
+ @Test
+ public void testConcurrentMap_compute_racy() {
+ final AtomicBoolean b = new AtomicBoolean(true);
+ final ConcurrentMap<Long,Long> map = new ImplementsConcurrentMap<>();
+ final Long two = 2L;
+ BiFunction<Long,Long,Long> f, g;
+
+ // null -> null is a no-op; race not detected
+ f = (k, v) -> { map.put(two, 42L); return null; };
+ assertNull(map.compute(two, f));
+ assertEquals(42L, (long)map.get(two));
+
+ for (Long val : new Long[] { null, 86L }) {
+ map.clear();
+
+ f = (k, v) -> { map.put(two, 42L); return 86L; };
+ g = (k, v) -> {
+ assertSame(two, k);
+ assertEquals(42L, (long)v);
+ return k + v;
+ };
+ assertEquals(44L, (long)map.compute(two, twoStep(b, f, g)));
+ assertEquals(44L, (long)map.get(two));
+ assertTrue(b.get());
+
+ f = (k, v) -> { map.remove(two); return val; };
+ g = (k, v) -> {
+ assertSame(two, k);
+ assertNull(v);
+ return 44L;
+ };
+ assertEquals(44L, (long)map.compute(two, twoStep(b, f, g)));
+ assertEquals(44L, (long)map.get(two));
+ assertTrue(map.containsKey(two));
+ assertTrue(b.get());
+
+ f = (k, v) -> { map.remove(two); return val; };
+ g = (k, v) -> {
+ assertSame(two, k);
+ assertNull(v);
+ return null;
+ };
+ assertNull(map.compute(two, twoStep(b, f, g)));
+ assertNull(map.get(two));
+ assertFalse(map.containsKey(two));
+ assertTrue(b.get());
+ }
+ }
+
+ /**
+ * Simulates races by modifying the map within the remapping function.
+ */
+ @Test
+ public void testConcurrentMap_merge_racy() {
+ final AtomicBoolean b = new AtomicBoolean(true);
+ final ConcurrentMap<Long,Long> map = new ImplementsConcurrentMap<>();
+ final Long two = 2L;
+ BiFunction<Long,Long,Long> f, g;
+
+ for (Long val : new Long[] { null, 86L }) {
+ map.clear();
+
+ f = (v, w) -> { throw new AssertionError(); };
+ assertEquals(99L, (long)map.merge(two, 99L, f));
+ assertEquals(99L, (long)map.get(two));
+
+ f = (v, w) -> { map.put(two, 42L); return val; };
+ g = (v, w) -> {
+ assertEquals(42L, (long)v);
+ assertEquals(3L, (long)w);
+ return v + w;
+ };
+ assertEquals(45L, (long)map.merge(two, 3L, twoStep(b, f, g)));
+ assertEquals(45L, (long)map.get(two));
+ assertTrue(b.get());
+
+ f = (v, w) -> { map.remove(two); return val; };
+ g = (k, v) -> { throw new AssertionError(); };
+ assertEquals(55L, (long)map.merge(two, 55L, twoStep(b, f, g)));
+ assertEquals(55L, (long)map.get(two));
+ assertTrue(map.containsKey(two));
+ assertFalse(b.get()); b.set(true);
+ }
+ }
+
public enum IntegerEnum {
e0, e1, e2, e3, e4, e5, e6, e7, e8, e9,
@@ -838,13 +1026,13 @@
protected ExtendsAbstractMap(M map) { this.map = map; }
- public Set<Map.Entry<K,V>> entrySet() {
+ @Override public Set<Map.Entry<K,V>> entrySet() {
return new AbstractSet<Map.Entry<K,V>>() {
- public int size() {
+ @Override public int size() {
return map.size();
}
- public Iterator<Map.Entry<K,V>> iterator() {
+ @Override public Iterator<Map.Entry<K,V>> iterator() {
final Iterator<Map.Entry<K,V>> source = map.entrySet().iterator();
return new Iterator<Map.Entry<K,V>>() {
public boolean hasNext() { return source.hasNext(); }
@@ -853,20 +1041,20 @@
};
}
- public boolean add(Map.Entry<K,V> e) {
+ @Override public boolean add(Map.Entry<K,V> e) {
return map.entrySet().add(e);
}
};
}
- public V put(K key, V value) {
+ @Override public V put(K key, V value) {
return map.put(key, value);
}
}
/**
* A simple mutable concurrent map implementation that provides only default
- * implementations of all methods. ie. none of the ConcurrentMap interface
+ * implementations of all methods, i.e. none of the ConcurrentMap interface
* default methods have overridden implementations.
*
* @param <K> Type of keys
@@ -875,14 +1063,26 @@
public static class ImplementsConcurrentMap<K,V> extends ExtendsAbstractMap<ConcurrentMap<K,V>, K, V> implements ConcurrentMap<K,V> {
public ImplementsConcurrentMap() { super(new ConcurrentHashMap<K,V>()); }
- // ConcurrentMap reabstracts these methods
+ // ConcurrentMap reabstracts these methods.
+ //
+ // Unlike ConcurrentHashMap, we have zero tolerance for null values.
- public V replace(K k, V v) { return map.replace(k, v); };
+ @Override public V replace(K k, V v) {
+ return map.replace(requireNonNull(k), requireNonNull(v));
+ }
- public boolean replace(K k, V v, V vv) { return map.replace(k, v, vv); };
+ @Override public boolean replace(K k, V v, V vv) {
+ return map.replace(requireNonNull(k),
+ requireNonNull(v),
+ requireNonNull(vv));
+ }
- public boolean remove(Object k, Object v) { return map.remove(k, v); }
+ @Override public boolean remove(Object k, Object v) {
+ return map.remove(requireNonNull(k), requireNonNull(v));
+ }
- public V putIfAbsent(K k, V v) { return map.putIfAbsent(k, v); }
+ @Override public V putIfAbsent(K k, V v) {
+ return map.putIfAbsent(requireNonNull(k), requireNonNull(v));
+ }
}
}