8078645: removeIf(filter) in ConcurrentHashMap removes entries for which filter is false
Reviewed-by: martin, dholmes
Contributed-by: Doug Lea <dl@cs.oswego.edu>, Paul Sandoz <paul.sandoz@oracle.com>
--- a/jdk/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java Mon May 11 17:54:03 2015 -0700
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java Tue May 12 10:50:40 2015 +0200
@@ -64,6 +64,7 @@
import java.util.function.Function;
import java.util.function.IntBinaryOperator;
import java.util.function.LongBinaryOperator;
+import java.util.function.Predicate;
import java.util.function.ToDoubleBiFunction;
import java.util.function.ToDoubleFunction;
import java.util.function.ToIntBiFunction;
@@ -1619,6 +1620,45 @@
}
/**
+ * Helper method for EntrySet.removeIf
+ */
+ boolean removeEntryIf(Predicate<? super Entry<K, V>> function) {
+ if (function == null) throw new NullPointerException();
+ Node<K,V>[] t;
+ boolean removed = false;
+ if ((t = table) != null) {
+ Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
+ for (Node<K,V> p; (p = it.advance()) != null; ) {
+ K k = p.key;
+ V v = p.val;
+ Map.Entry<K,V> e = new AbstractMap.SimpleImmutableEntry<>(k, v);
+ if (function.test(e) && replaceNode(k, null, v) != null)
+ removed = true;
+ }
+ }
+ return removed;
+ }
+
+ /**
+ * Helper method for Values.removeIf
+ */
+ boolean removeValueIf(Predicate<? super V> function) {
+ if (function == null) throw new NullPointerException();
+ Node<K,V>[] t;
+ boolean removed = false;
+ if ((t = table) != null) {
+ Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);
+ for (Node<K,V> p; (p = it.advance()) != null; ) {
+ K k = p.key;
+ V v = p.val;
+ if (function.test(v) && replaceNode(k, null, v) != null)
+ removed = true;
+ }
+ }
+ return removed;
+ }
+
+ /**
* If the specified key is not already associated with a value,
* attempts to compute its value using the given mapping function
* and enters it into this map unless {@code null}. The entire
@@ -4690,6 +4730,10 @@
throw new UnsupportedOperationException();
}
+ public boolean removeIf(Predicate<? super V> filter) {
+ return map.removeValueIf(filter);
+ }
+
public Spliterator<V> spliterator() {
Node<K,V>[] t;
ConcurrentHashMap<K,V> m = map;
@@ -4759,6 +4803,10 @@
return added;
}
+ public boolean removeIf(Predicate<? super Entry<K, V>> filter) {
+ return map.removeEntryIf(filter);
+ }
+
public final int hashCode() {
int h = 0;
Node<K,V>[] t;
--- a/jdk/src/java.base/share/classes/java/util/concurrent/ConcurrentMap.java Mon May 11 17:54:03 2015 -0700
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/ConcurrentMap.java Tue May 12 10:50:40 2015 +0200
@@ -34,6 +34,7 @@
*/
package java.util.concurrent;
+
import java.util.Map;
import java.util.Objects;
import java.util.function.BiConsumer;
@@ -44,6 +45,14 @@
* A {@link java.util.Map} providing thread safety and atomicity
* guarantees.
*
+ * <p>To maintain the specified guarantees, default implementations of
+ * methods including {@link #putIfAbsent} inherited from {@link Map}
+ * must be overridden by implementations of this interface. Similarly,
+ * implementations of the collections returned by methods {@link
+ * #keySet}, {@link #values}, and {@link #entrySet} must override
+ * methods such as {@code removeIf} when necessary to
+ * preserve atomicity guarantees.
+ *
* <p>Memory consistency effects: As with other concurrent
* collections, actions in a thread prior to placing an object into a
* {@code ConcurrentMap} as a key or value
@@ -60,7 +69,7 @@
* @param <K> the type of keys maintained by this map
* @param <V> the type of mapped values
*/
-public interface ConcurrentMap<K, V> extends Map<K, V> {
+public interface ConcurrentMap<K,V> extends Map<K,V> {
/**
* {@inheritDoc}
@@ -86,9 +95,9 @@
* @implSpec The default implementation is equivalent to, for this
* {@code map}:
* <pre> {@code
- * for ((Map.Entry<K, V> entry : map.entrySet())
- * action.accept(entry.getKey(), entry.getValue());
- * }</pre>
+ * for (Map.Entry<K,V> entry : map.entrySet()) {
+ * action.accept(entry.getKey(), entry.getValue());
+ * }}</pre>
*
* @implNote The default implementation assumes that
* {@code IllegalStateException} thrown by {@code getKey()} or
@@ -101,13 +110,13 @@
@Override
default void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
- for (Map.Entry<K, V> entry : entrySet()) {
+ for (Map.Entry<K,V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
- } catch(IllegalStateException ise) {
+ } catch (IllegalStateException ise) {
// this usually means the entry is no longer in the map.
continue;
}
@@ -117,14 +126,13 @@
/**
* If the specified key is not already associated
- * with a value, associate it with the given value.
- * This is equivalent to
- * <pre> {@code
+ * with a value, associates it with the given value.
+ * This is equivalent to, for this {@code map}:
+ * <pre> {@code
* if (!map.containsKey(key))
* return map.put(key, value);
* else
- * return map.get(key);
- * }</pre>
+ * return map.get(key);}</pre>
*
* except that the action is performed atomically.
*
@@ -147,18 +155,19 @@
* @throws IllegalArgumentException if some property of the specified key
* or value prevents it from being stored in this map
*/
- V putIfAbsent(K key, V value);
+ V putIfAbsent(K key, V value);
/**
* Removes the entry for a key only if currently mapped to a given value.
- * This is equivalent to
- * <pre> {@code
- * if (map.containsKey(key) && Objects.equals(map.get(key), value)) {
+ * This is equivalent to, for this {@code map}:
+ * <pre> {@code
+ * if (map.containsKey(key)
+ * && Objects.equals(map.get(key), value)) {
* map.remove(key);
* return true;
- * } else
+ * } else {
* return false;
- * }</pre>
+ * }}</pre>
*
* except that the action is performed atomically.
*
@@ -181,14 +190,15 @@
/**
* Replaces the entry for a key only if currently mapped to a given value.
- * This is equivalent to
- * <pre> {@code
- * if (map.containsKey(key) && Objects.equals(map.get(key), oldValue)) {
+ * This is equivalent to, for this {@code map}:
+ * <pre> {@code
+ * if (map.containsKey(key)
+ * && Objects.equals(map.get(key), oldValue)) {
* map.put(key, newValue);
* return true;
- * } else
+ * } else {
* return false;
- * }</pre>
+ * }}</pre>
*
* except that the action is performed atomically.
*
@@ -212,13 +222,12 @@
/**
* Replaces the entry for a key only if currently mapped to some value.
- * This is equivalent to
- * <pre> {@code
- * if (map.containsKey(key)) {
+ * This is equivalent to, for this {@code map}:
+ * <pre> {@code
+ * if (map.containsKey(key))
* return map.put(key, value);
- * } else
- * return null;
- * }</pre>
+ * else
+ * return null;}</pre>
*
* except that the action is performed atomically.
*
@@ -249,12 +258,14 @@
* @implSpec
* <p>The default implementation is equivalent to, for this {@code map}:
* <pre> {@code
- * for ((Map.Entry<K, V> entry : map.entrySet())
- * do {
- * K k = entry.getKey();
- * V v = entry.getValue();
- * } while(!replace(k, v, function.apply(k, v)));
- * }</pre>
+ * for (Map.Entry<K,V> entry : map.entrySet()) {
+ * K k;
+ * V v;
+ * do {
+ * k = entry.getKey();
+ * v = entry.getValue();
+ * } while (!map.replace(k, v, function.apply(k, v)));
+ * }}</pre>
*
* The default implementation may retry these steps when multiple
* threads attempt updates including potentially calling the function
@@ -275,7 +286,7 @@
default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
Objects.requireNonNull(function);
forEach((k,v) -> {
- while(!replace(k, v, function.apply(k, v))) {
+ while (!replace(k, v, function.apply(k, v))) {
// v changed or k is gone
if ( (v = get(k)) == null) {
// k is no longer in the map.
@@ -295,11 +306,10 @@
*
* <pre> {@code
* if (map.get(key) == null) {
- * V newValue = mappingFunction.apply(key);
- * if (newValue != null)
- * return map.putIfAbsent(key, newValue);
- * }
- * }</pre>
+ * 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
@@ -331,18 +341,17 @@
* @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. :
+ * {@code null} if now absent:
*
* <pre> {@code
* if (map.get(key) != null) {
- * V oldValue = map.get(key);
- * V newValue = remappingFunction.apply(key, oldValue);
- * if (newValue != null)
- * map.replace(key, oldValue, newValue);
- * else
- * map.remove(key, oldValue);
- * }
- * }</pre>
+ * V oldValue = map.get(key);
+ * 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
@@ -363,13 +372,13 @@
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue;
- while((oldValue = get(key)) != null) {
+ while ((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;
+ return null;
}
return oldValue;
}
@@ -386,17 +395,16 @@
* 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);
+ * if (newValue != null)
+ * map.replace(key, oldValue, newValue);
+ * else
+ * map.remove(key, oldValue);
* } else {
- * if (newValue != null)
- * map.putIfAbsent(key, newValue);
- * else
- * return null;
- * }
- * }</pre>
+ * if (newValue != null)
+ * map.putIfAbsent(key, newValue);
+ * else
+ * return null;
+ * }}</pre>
*
* The default implementation may retry these steps when multiple
* threads attempt updates including potentially calling the remapping
@@ -417,7 +425,7 @@
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue = get(key);
- for(;;) {
+ for (;;) {
V newValue = remappingFunction.apply(key, oldValue);
if (newValue == null) {
// delete mapping
@@ -458,7 +466,6 @@
}
}
-
/**
* {@inheritDoc}
*
@@ -470,12 +477,11 @@
* <pre> {@code
* V oldValue = map.get(key);
* V newValue = (oldValue == null) ? value :
- * remappingFunction.apply(oldValue, value);
+ * remappingFunction.apply(oldValue, value);
* if (newValue == null)
- * map.remove(key);
+ * map.remove(key);
* else
- * map.put(key, newValue);
- * }</pre>
+ * map.put(key, newValue);}</pre>
*
* <p>The default implementation may retry these steps when multiple
* threads attempt updates including potentially calling the remapping
--- a/jdk/src/java.base/share/classes/java/util/concurrent/ConcurrentSkipListMap.java Mon May 11 17:54:03 2015 -0700
+++ b/jdk/src/java.base/share/classes/java/util/concurrent/ConcurrentSkipListMap.java Tue May 12 10:50:40 2015 +0200
@@ -58,6 +58,7 @@
import java.util.function.Consumer;
import java.util.function.BiConsumer;
import java.util.function.Function;
+import java.util.function.Predicate;
/**
* A scalable concurrent {@link ConcurrentNavigableMap} implementation.
@@ -2492,6 +2493,22 @@
else
return (Spliterator<E>)((SubMap<?,E>)m).valueIterator();
}
+ public boolean removeIf(Predicate<? super E> filter) {
+ if (filter == null) throw new NullPointerException();
+ if (m instanceof ConcurrentSkipListMap)
+ return ((ConcurrentSkipListMap<?,E>)m).removeValueIf(filter);
+ // else use iterator
+ @SuppressWarnings("unchecked") Iterator<Map.Entry<Object,E>> it =
+ ((SubMap<Object,E>)m).entryIterator();
+ boolean removed = false;
+ while (it.hasNext()) {
+ Map.Entry<Object,E> e = it.next();
+ E v = e.getValue();
+ if (filter.test(v) && m.remove(e.getKey(), v))
+ removed = true;
+ }
+ return removed;
+ }
}
static final class EntrySet<K1,V1> extends AbstractSet<Map.Entry<K1,V1>> {
@@ -2554,6 +2571,20 @@
return (Spliterator<Map.Entry<K1,V1>>)
((SubMap<K1,V1>)m).entryIterator();
}
+ public boolean removeIf(Predicate<? super Entry<K1, V1>> filter) {
+ if (filter == null) throw new NullPointerException();
+ if (m instanceof ConcurrentSkipListMap)
+ return ((ConcurrentSkipListMap<K1,V1>)m).removeEntryIf(filter);
+ // else use iterator
+ Iterator<Map.Entry<K1,V1>> it = ((SubMap<K1,V1>)m).entryIterator();
+ boolean removed = false;
+ while (it.hasNext()) {
+ Map.Entry<K1,V1> e = it.next();
+ if (filter.test(e) && m.remove(e.getKey(), e.getValue()))
+ removed = true;
+ }
+ return removed;
+ }
}
/**
@@ -3267,6 +3298,41 @@
}
/**
+ * Helper method for EntrySet.removeIf
+ */
+ boolean removeEntryIf(Predicate<? super Entry<K, V>> function) {
+ if (function == null) throw new NullPointerException();
+ boolean removed = false;
+ for (Node<K,V> n = findFirst(); n != null; n = n.next) {
+ V v;
+ if ((v = n.getValidValue()) != null) {
+ K k = n.key;
+ Map.Entry<K,V> e = new AbstractMap.SimpleImmutableEntry<>(k, v);
+ if (function.test(e) && remove(k, v))
+ removed = true;
+ }
+ }
+ return removed;
+ }
+
+ /**
+ * Helper method for Values.removeIf
+ */
+ boolean removeValueIf(Predicate<? super V> function) {
+ if (function == null) throw new NullPointerException();
+ boolean removed = false;
+ for (Node<K,V> n = findFirst(); n != null; n = n.next) {
+ V v;
+ if ((v = n.getValidValue()) != null) {
+ K k = n.key;
+ if (function.test(v) && remove(k, v))
+ removed = true;
+ }
+ }
+ return removed;
+ }
+
+ /**
* Base class providing common structure for Spliterators.
* (Although not all that much common functionality; as usual for
* view classes, details annoyingly vary in key, value, and entry
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/concurrent/ConcurrentMap/ConcurrentRemoveIf.java Tue May 12 10:50:40 2015 +0200
@@ -0,0 +1,176 @@
+/*
+ * Copyright (c) 2015, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * @test
+ * @run testng ConcurrentRemoveIf
+ * @bug 8078645
+ * @summary Test removeIf on views of concurrent maps
+ */
+
+import org.testng.Assert;
+import org.testng.annotations.AfterClass;
+import org.testng.annotations.DataProvider;
+import org.testng.annotations.Test;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.concurrent.CompletableFuture;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ConcurrentMap;
+import java.util.concurrent.ConcurrentNavigableMap;
+import java.util.concurrent.ConcurrentSkipListMap;
+import java.util.concurrent.CyclicBarrier;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Executors;
+import java.util.function.Consumer;
+import java.util.function.Supplier;
+
+@Test
+public class ConcurrentRemoveIf {
+ static final int K = 100;
+ static final int SIZE = 1000;
+ static final int HALF_SIZE = SIZE / 2;
+
+ @DataProvider(name = "String,Supplier<ConcurrentMap>,Runnable")
+ public static Object[][] spliteratorDataProvider() {
+ List<Object[]> rows = new ArrayList<>();
+
+ // ConcurrentMap classes to test
+ Map<String, Supplier<ConcurrentMap<Integer, Integer>>> maps = new HashMap<>();
+ maps.put("ConcurrentHashMap", ConcurrentHashMap::new);
+ maps.put("ConcurrentSkipListMap", ConcurrentSkipListMap::new);
+
+ // ConcurrentMap actions
+ Map<String, Consumer<ConcurrentMap<Integer, Integer>>> actions = new HashMap<>();
+ actions.put(".entrySet().removeIf()", m -> m.entrySet().removeIf(e -> e.getValue() == 0));
+ actions.put(".values().removeIf()", m -> m.values().removeIf(v -> v == 0));
+
+ // ConcurrentNavigableMap actions
+ Map<String, Consumer<ConcurrentNavigableMap<Integer, Integer>>> navActions = new HashMap<>();
+ navActions.put(".headMap()/tailMap().entrySet().removeIf()",
+ m -> {
+ ConcurrentMap<Integer, Integer> left = m.headMap(HALF_SIZE, false);
+ ConcurrentMap<Integer, Integer> right = m.tailMap(HALF_SIZE, true);
+ left.entrySet().removeIf(e -> e.getValue() == 0);
+ right.entrySet().removeIf(e -> e.getValue() == 0);
+ });
+ navActions.put(".headMap()/tailMap().values().removeIf()",
+ m -> {
+ ConcurrentMap<Integer, Integer> left = m.headMap(HALF_SIZE, false);
+ ConcurrentMap<Integer, Integer> right = m.tailMap(HALF_SIZE, true);
+ left.values().removeIf(v -> v == 0);
+ right.values().removeIf(v -> v == 0);
+ });
+ navActions.put(".descendingMap().entrySet().removeIf()",
+ m -> {
+ ConcurrentMap<Integer, Integer> dm = m.descendingMap();
+ dm.entrySet().removeIf(e -> e.getValue() == 0);
+ });
+ navActions.put(".descendingMap().values().removeIf()",
+ m -> {
+ ConcurrentMap<Integer, Integer> dm = m.descendingMap();
+ dm.values().removeIf(v -> v == 0);
+ });
+
+ for (Map.Entry<String, Supplier<ConcurrentMap<Integer, Integer>>> mapSupplier : maps.entrySet()) {
+ Supplier<ConcurrentMap<Integer, Integer>> sm = mapSupplier.getValue();
+ for (Map.Entry<String, Consumer<ConcurrentMap<Integer, Integer>>> action : actions.entrySet()) {
+ rows.add(new Object[]{
+ mapSupplier.getKey() + action.getKey(),
+ sm,
+ action.getValue()});
+ }
+
+ if (sm.get() instanceof ConcurrentNavigableMap) {
+ for (Map.Entry<String, Consumer<ConcurrentNavigableMap<Integer, Integer>>> action : navActions.entrySet()) {
+ rows.add(new Object[]{
+ mapSupplier.getKey() + action.getKey(),
+ sm,
+ action.getValue()});
+ }
+ }
+ }
+
+ return rows.toArray(new Object[0][]);
+ }
+
+ ExecutorService executorService = Executors.newCachedThreadPool();
+
+ @AfterClass
+ public void after() {
+ executorService.shutdown();
+ }
+
+ @Test(dataProvider = "String,Supplier<ConcurrentMap>,Runnable")
+ public void testMap(String desc, Supplier<ConcurrentMap<Integer, Integer>> ms, Consumer<ConcurrentMap<Integer, Integer>> action)
+ throws InterruptedException {
+ for (int i = 0; i < K; i++) {
+ testMap(ms.get(), action);
+ }
+ }
+
+ private void testMap(ConcurrentMap<Integer, Integer> map, Consumer<ConcurrentMap<Integer, Integer>> action)
+ throws InterruptedException {
+ // put 0's
+ fillMap(map, 0);
+
+ // To start working simultaneously
+ CyclicBarrier threadStarted = new CyclicBarrier(2);
+
+ // This task put 1's into map
+ CompletableFuture<Void> putter = CompletableFuture.runAsync(
+ awaitOn(threadStarted, () -> fillMap(map, 1)),
+ executorService);
+
+ // This task performs the map action to remove all 0's from map
+ CompletableFuture<Void> remover = CompletableFuture.runAsync(
+ awaitOn(threadStarted, () -> action.accept(map)),
+ executorService);
+
+ // Wait for both tasks to complete
+ CompletableFuture.allOf(putter, remover).join();
+
+ Assert.assertEquals(map.size(), SIZE, "Map size incorrect");
+ }
+
+ static void fillMap(ConcurrentMap<Integer, Integer> map, int value) {
+ for (int i = 0; i < SIZE; i++) {
+ map.put(i, value);
+ }
+ }
+
+ static Runnable awaitOn(CyclicBarrier threadStarted, Runnable r) {
+ return () -> {
+ try {
+ threadStarted.await();
+ }
+ catch (Exception e) {
+ throw new RuntimeException(e);
+ }
+ r.run();
+ };
+ }
+}