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

[Remi Forax]

On 06/13/2013 07:28 AM, 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

Hi Mike,

in TreeMap.forEach (and replaceAll), the check for co-modification 
should be done *before* action.accept(...)
and not after because the semantics of the Iterator allows users to 
modify the map (hashmap or treemap)
if it's the last element (so we should not check modCount after the last 
element).
Also the code of forEach inside the loop is basically a hand-inlined 
version of Treemap.successor(),
I wonder if it's not better to use successor() here ?

in Hashtable.replaceAll(), the cast to K and V in function.apply() is 
useless.

otherwise, all other codes are ok for me :)

Rémi



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;

/**
  * <p>Hash table and linked list implementation of the <tt>Map</tt> 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);
+        }
+    }
}