# HG changeset patch # User psandoz # Date 1431420640 -7200 # Node ID 415a5242e04681aeecbf134d09ff110ab8166452 # Parent 376bb53438b79f882a6dcbb517761b31ff05dd1d 8078645: removeIf(filter) in ConcurrentHashMap removes entries for which filter is false Reviewed-by: martin, dholmes Contributed-by: Doug Lea , Paul Sandoz diff -r 376bb53438b7 -r 415a5242e046 jdk/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java --- 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> function) { + if (function == null) throw new NullPointerException(); + Node[] t; + boolean removed = false; + if ((t = table) != null) { + Traverser it = new Traverser(t, t.length, 0, t.length); + for (Node p; (p = it.advance()) != null; ) { + K k = p.key; + V v = p.val; + Map.Entry 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 function) { + if (function == null) throw new NullPointerException(); + Node[] t; + boolean removed = false; + if ((t = table) != null) { + Traverser it = new Traverser(t, t.length, 0, t.length); + for (Node 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 filter) { + return map.removeValueIf(filter); + } + public Spliterator spliterator() { Node[] t; ConcurrentHashMap m = map; @@ -4759,6 +4803,10 @@ return added; } + public boolean removeIf(Predicate> filter) { + return map.removeEntryIf(filter); + } + public final int hashCode() { int h = 0; Node[] t; diff -r 376bb53438b7 -r 415a5242e046 jdk/src/java.base/share/classes/java/util/concurrent/ConcurrentMap.java --- 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. * + *

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. + * *

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 the type of keys maintained by this map * @param the type of mapped values */ -public interface ConcurrentMap extends Map { +public interface ConcurrentMap extends Map { /** * {@inheritDoc} @@ -86,9 +95,9 @@ * @implSpec The default implementation is equivalent to, for this * {@code map}: * 

 {@code
-     * for ((Map.Entry entry : map.entrySet())
-     *     action.accept(entry.getKey(), entry.getValue());
-     * }
+ * for (Map.Entry entry : map.entrySet()) { + * action.accept(entry.getKey(), entry.getValue()); + * }} * * @implNote The default implementation assumes that * {@code IllegalStateException} thrown by {@code getKey()} or @@ -101,13 +110,13 @@ @Override default void forEach(BiConsumer action) { Objects.requireNonNull(action); - for (Map.Entry entry : entrySet()) { + for (Map.Entry 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 - * 
 {@code
+     * with a value, associates it with the given value.
+     * This is equivalent to, for this {@code map}:
+     * 
 {@code
      * if (!map.containsKey(key))
      *   return map.put(key, value);
      * else
-     *   return map.get(key);
-     * }

+     *   return map.get(key);}
* * 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 - * 
 {@code
-     * if (map.containsKey(key) && Objects.equals(map.get(key), value)) {
+     * This is equivalent to, for this {@code map}:
+     * 
 {@code
+     * if (map.containsKey(key)
+     *     && Objects.equals(map.get(key), value)) {
      *   map.remove(key);
      *   return true;
-     * } else
+     * } else {
      *   return false;
-     * }

+     * }}
* * 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 - * 
 {@code
-     * if (map.containsKey(key) && Objects.equals(map.get(key), oldValue)) {
+     * This is equivalent to, for this {@code map}:
+     * 
 {@code
+     * if (map.containsKey(key)
+     *     && Objects.equals(map.get(key), oldValue)) {
      *   map.put(key, newValue);
      *   return true;
-     * } else
+     * } else {
      *   return false;
-     * }

+     * }}
* * 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 - * 
 {@code
-     * if (map.containsKey(key)) {
+     * This is equivalent to, for this {@code map}:
+     * 
 {@code
+     * if (map.containsKey(key))
      *   return map.put(key, value);
-     * } else
-     *   return null;
-     * }

+     * else
+     *   return null;}
* * except that the action is performed atomically. * @@ -249,12 +258,14 @@ * @implSpec *

The default implementation is equivalent to, for this {@code map}: * 

 {@code
-     * for ((Map.Entry entry : map.entrySet())
-     *     do {
-     *        K k = entry.getKey();
-     *        V v = entry.getValue();
-     *     } while(!replace(k, v, function.apply(k, v)));
-     * }
+ * for (Map.Entry entry : map.entrySet()) { + * K k; + * V v; + * do { + * k = entry.getKey(); + * v = entry.getValue(); + * } while (!map.replace(k, v, function.apply(k, v))); + * }} * * 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 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 @@ * * 
 {@code
      * if (map.get(key) == null) {
-     *     V newValue = mappingFunction.apply(key);
-     *     if (newValue != null)
-     *         return map.putIfAbsent(key, newValue);
-     * }
-     * }
+ * V newValue = mappingFunction.apply(key); + * if (newValue != null) + * return map.putIfAbsent(key, newValue); + * }} * * 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: * * 
 {@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);
-     * }
-     * }
+ * V oldValue = map.get(key); + * V newValue = remappingFunction.apply(key, oldValue); + * if (newValue != null) + * map.replace(key, oldValue, newValue); + * else + * map.remove(key, oldValue); + * }} * * The default implementation may retry these steps when multiple threads * attempt updates including potentially calling the remapping function @@ -363,13 +372,13 @@ BiFunction 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; - * } - * } + * if (newValue != null) + * map.putIfAbsent(key, newValue); + * else + * return null; + * }} * * The default implementation may retry these steps when multiple * threads attempt updates including potentially calling the remapping @@ -417,7 +425,7 @@ BiFunction 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 @@ * 
 {@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);
-     * }
+ * map.put(key, newValue);} * *

The default implementation may retry these steps when multiple * threads attempt updates including potentially calling the remapping diff -r 376bb53438b7 -r 415a5242e046 jdk/src/java.base/share/classes/java/util/concurrent/ConcurrentSkipListMap.java --- 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)((SubMap)m).valueIterator(); } + public boolean removeIf(Predicate filter) { + if (filter == null) throw new NullPointerException(); + if (m instanceof ConcurrentSkipListMap) + return ((ConcurrentSkipListMap)m).removeValueIf(filter); + // else use iterator + @SuppressWarnings("unchecked") Iterator> it = + ((SubMap)m).entryIterator(); + boolean removed = false; + while (it.hasNext()) { + Map.Entry e = it.next(); + E v = e.getValue(); + if (filter.test(v) && m.remove(e.getKey(), v)) + removed = true; + } + return removed; + } } static final class EntrySet extends AbstractSet> { @@ -2554,6 +2571,20 @@ return (Spliterator>) ((SubMap)m).entryIterator(); } + public boolean removeIf(Predicate> filter) { + if (filter == null) throw new NullPointerException(); + if (m instanceof ConcurrentSkipListMap) + return ((ConcurrentSkipListMap)m).removeEntryIf(filter); + // else use iterator + Iterator> it = ((SubMap)m).entryIterator(); + boolean removed = false; + while (it.hasNext()) { + Map.Entry 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> function) { + if (function == null) throw new NullPointerException(); + boolean removed = false; + for (Node n = findFirst(); n != null; n = n.next) { + V v; + if ((v = n.getValidValue()) != null) { + K k = n.key; + Map.Entry 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 function) { + if (function == null) throw new NullPointerException(); + boolean removed = false; + for (Node 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 diff -r 376bb53438b7 -r 415a5242e046 jdk/test/java/util/concurrent/ConcurrentMap/ConcurrentRemoveIf.java --- /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,Runnable") + public static Object[][] spliteratorDataProvider() { + List rows = new ArrayList<>(); + + // ConcurrentMap classes to test + Map>> maps = new HashMap<>(); + maps.put("ConcurrentHashMap", ConcurrentHashMap::new); + maps.put("ConcurrentSkipListMap", ConcurrentSkipListMap::new); + + // ConcurrentMap actions + Map>> 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>> navActions = new HashMap<>(); + navActions.put(".headMap()/tailMap().entrySet().removeIf()", + m -> { + ConcurrentMap left = m.headMap(HALF_SIZE, false); + ConcurrentMap 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 left = m.headMap(HALF_SIZE, false); + ConcurrentMap 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 dm = m.descendingMap(); + dm.entrySet().removeIf(e -> e.getValue() == 0); + }); + navActions.put(".descendingMap().values().removeIf()", + m -> { + ConcurrentMap dm = m.descendingMap(); + dm.values().removeIf(v -> v == 0); + }); + + for (Map.Entry>> mapSupplier : maps.entrySet()) { + Supplier> sm = mapSupplier.getValue(); + for (Map.Entry>> action : actions.entrySet()) { + rows.add(new Object[]{ + mapSupplier.getKey() + action.getKey(), + sm, + action.getValue()}); + } + + if (sm.get() instanceof ConcurrentNavigableMap) { + for (Map.Entry>> 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,Runnable") + public void testMap(String desc, Supplier> ms, Consumer> action) + throws InterruptedException { + for (int i = 0; i < K; i++) { + testMap(ms.get(), action); + } + } + + private void testMap(ConcurrentMap map, Consumer> 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 putter = CompletableFuture.runAsync( + awaitOn(threadStarted, () -> fillMap(map, 1)), + executorService); + + // This task performs the map action to remove all 0's from map + CompletableFuture 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 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(); + }; + } +}