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

[Mike Duigou]

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;
> 
> /**
>  * <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);
> +        }
> +    }
> }
> 
>