RFR : 8016446 : (m) Add override forEach/replaceAll to HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap (original) (raw)

Remi Forax forax at univ-mlv.fr
Fri Jun 14 23:37:40 UTC 2013

On 06/14/2013 11:57 PM, Mike Duigou wrote:

I have updated the webrev again. In addition to moving the modification checks to be consistently after the operation for the most complete "fast-fail" behaviour I've also slightly enhanced the Map default to detect ISE thrown by setValue as a CME condition.

http://cr.openjdk.java.net/~mduigou/JDK-8016446/2/webrev/ For interference detection the strategy I am advocating is : - serial non-stream operations (Collection.forEach/Iterator.forEachRemaining): per-element post-operation ("fast-fail", "best-efforts"). As Remi has pointed out the failure modes for collection.forEach() and for(:collection) will differ and it is a conscious choice to provide superior fast-fail than to match behaviour.

I don't think this corner case worth to spend more bits in replies, I'm Ok with your arguments ... but because I love to have the last word, could you put superior between quotes :)

- stream terminal operations, both serial and parallel : at completion if at all. Having the serial and parallel stream interference detection behaviours consistent is prioritized over making serial stream behaviour match behaviour of non-stream iteration methods.

yes

Mike

Rémi

On Jun 12 2013, at 22:28 , Mike Duigou wrote:

I have updated my webrev with Remi's improvements and some other improvements to the fast-fail concurrent modification checking.

Revised webrev: http://cr.openjdk.java.net/~mduigou/JDK-8016446/1/webrev/ Mike

On Jun 12 2013, at 15:49 , Remi Forax wrote: On 06/12/2013 11:23 PM, Mike Duigou wrote: Hello all;

This patch adds optimized implementations of Map.forEach and Map.replaceAll to HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap http://cr.openjdk.java.net/~mduigou/JDK-8016446/0/webrev/ The implementations traverse the map more efficiently than the default iterator implementation and sometimes avoid creation of transient Map.Entry instances. The fast-fail behaviour of the default implementation is retained. Mike Hi Mike, funnily I was writing HashMap.forEach/LinkedHashMap.forEach at the same time. (you need also to override forEach in LinkedHashMap because the one you inherits from HashMap doesn't use the linked list of entries). My code is slightly different from yours because I've moved the cases where the item is a red/black tree out of the fast path (the tree is created either if you are unlucky, if hashCode is badly written or if someone forge keys to have collisions) and does the modCount check for each element because a call to the consumer can change the underlying map so you can not do a modCount check only at the end. Rémi Here is the diff. diff -r 6df79b7bae6f src/share/classes/java/util/HashMap.java --- a/src/share/classes/java/util/HashMap.java Wed Jun 12 09:44:34 2013 +0100 +++ b/src/share/classes/java/util/HashMap.java Thu Jun 13 00:46:05 2013 +0200 @@ -28,6 +28,7 @@ import java.io.*; import java.lang.reflect.ParameterizedType; import java.lang.reflect.Type; +import java.util.function.BiConsumer; import java.util.function.Consumer; import java.util.function.BiFunction; import java.util.function.Function; @@ -2615,6 +2616,54 @@ int capacity() { return table.length; } float loadFactor() { return loadFactor; } + + @Override + public void forEach(BiConsumer<? super K, ? super V> action) { + Objects.requireNonNull(action); + final int expectedModCount = modCount; + if (nullKeyEntry != null) { + forEachNullKey(expectedModCount, action); + } + Object[] table = this.table; + for(int index = 0; index < table.length; index++) {_ _+ Object item = table[index];_ _+ if (item == null) {_ _+ continue;_ _+ }_ _+ if (item instanceof HashMap.TreeBin) {_ _+ eachTreeNode(expectedModCount, ((TreeBin)item).first, action);_ _+ continue;_ _+ }_ _+ @SuppressWarnings("unchecked")_ _+ Entry<K,V> entry = (Entry<K,V>)item; + for (;entry != null; entry = (Entry<K,V>)entry.next) { + if (expectedModCount != modCount) { + throw new ConcurrentModificationException(); + } + action.accept(entry.key, entry.value); + } + } + } + + private void eachTreeNode(int expectedModCount, TreeNode<K,V> node, BiConsumer<? super K, ? super V> action) { + while (node != null) { + if (expectedModCount != modCount) { + throw new ConcurrentModificationException(); + } + @SuppressWarnings("unchecked") + Entry<K,V> entry = (Entry<K,V>)node.entry; + action.accept(entry.key, entry.value); + node = (TreeNode<K,V>)entry.next; + } + } + + private void forEachNullKey(int expectedModCount, BiConsumer<? super K, ? super V> action) { + if (expectedModCount != modCount) { + throw new ConcurrentModificationException(); + } + action.accept(null, nullKeyEntry.value); + } + /** * Standin until HM overhaul; based loosely on Weak and Identity HM. */ diff -r 6df79b7bae6f src/share/classes/java/util/LinkedHashMap.java --- a/src/share/classes/java/util/LinkedHashMap.java Wed Jun 12 09:44:34 2013 +0100 +++ b/src/share/classes/java/util/LinkedHashMap.java Thu Jun 13 00:46:05 2013 +0200 @@ -24,7 +24,8 @@ */ package java.util; -import java.io.*; + +import java.util.function.BiConsumer; /** *

Hash table and linked list implementation of the Map interface,

@@ -470,4 +471,16 @@ protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; } + + @Override + public void forEach(BiConsumer<? super K, ? super V> action) { + Objects.requireNonNull(action); + int expectedModCount = modCount; + for (Entry<K,V> entry = header.after; entry != header; entry = entry.after) { + if (expectedModCount != modCount) { + throw new ConcurrentModificationException(); + } + action.accept(entry.key, entry.value); + } + } }

More information about the core-libs-dev mailing list