changeset 17462:2c580c0bc54b

8186171: HashMap: Entry.setValue may not work after Iterator.remove() called for previous entries Reviewed-by: martin, psandoz
author dl
date Tue, 03 Oct 2017 13:45:11 -0700
parents b7cbf8fbe796
children d54486c189e5
files src/java.base/share/classes/java/util/HashMap.java test/java/util/concurrent/tck/ConcurrentHashMapTest.java test/java/util/concurrent/tck/ConcurrentSkipListMapTest.java test/java/util/concurrent/tck/HashMapTest.java test/java/util/concurrent/tck/MapImplementation.java test/java/util/concurrent/tck/MapTest.java test/java/util/concurrent/tck/TreeMapTest.java
diffstat 7 files changed, 350 insertions(+), 29 deletions(-) [+]
line wrap: on
line diff
--- a/src/java.base/share/classes/java/util/HashMap.java	Thu Nov 09 16:10:46 2017 -0800
+++ b/src/java.base/share/classes/java/util/HashMap.java	Tue Oct 03 13:45:11 2017 -0700
@@ -491,7 +491,7 @@
     }
 
     /**
-     * Implements Map.putAll and Map constructor
+     * Implements Map.putAll and Map constructor.
      *
      * @param m the map
      * @param evict false when initially constructing this map, else
@@ -558,7 +558,7 @@
     }
 
     /**
-     * Implements Map.get and related methods
+     * Implements Map.get and related methods.
      *
      * @param hash hash for key
      * @param key the key
@@ -613,7 +613,7 @@
     }
 
     /**
-     * Implements Map.put and related methods
+     * Implements Map.put and related methods.
      *
      * @param hash hash for key
      * @param key the key
@@ -701,7 +701,7 @@
         }
         threshold = newThr;
         @SuppressWarnings({"rawtypes","unchecked"})
-            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
+        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
         table = newTab;
         if (oldTab != null) {
             for (int j = 0; j < oldCap; ++j) {
@@ -801,7 +801,7 @@
     }
 
     /**
-     * Implements Map.remove and related methods
+     * Implements Map.remove and related methods.
      *
      * @param hash hash for key
      * @param key the key
@@ -876,7 +876,7 @@
     public boolean containsValue(Object value) {
         Node<K,V>[] tab; V v;
         if ((tab = table) != null && size > 0) {
-            for (Node<K, V> e : tab) {
+            for (Node<K,V> e : tab) {
                 for (; e != null; e = e.next) {
                     if ((v = e.value) == value ||
                         (value != null && value.equals(v)))
@@ -928,7 +928,7 @@
                 throw new NullPointerException();
             if (size > 0 && (tab = table) != null) {
                 int mc = modCount;
-                for (Node<K, V> e : tab) {
+                for (Node<K,V> e : tab) {
                     for (; e != null; e = e.next)
                         action.accept(e.key);
                 }
@@ -976,7 +976,7 @@
                 throw new NullPointerException();
             if (size > 0 && (tab = table) != null) {
                 int mc = modCount;
-                for (Node<K, V> e : tab) {
+                for (Node<K,V> e : tab) {
                     for (; e != null; e = e.next)
                         action.accept(e.value);
                 }
@@ -1039,7 +1039,7 @@
                 throw new NullPointerException();
             if (size > 0 && (tab = table) != null) {
                 int mc = modCount;
-                for (Node<K, V> e : tab) {
+                for (Node<K,V> e : tab) {
                     for (; e != null; e = e.next)
                         action.accept(e);
                 }
@@ -1336,7 +1336,7 @@
             throw new NullPointerException();
         if (size > 0 && (tab = table) != null) {
             int mc = modCount;
-            for (Node<K, V> e : tab) {
+            for (Node<K,V> e : tab) {
                 for (; e != null; e = e.next)
                     action.accept(e.key, e.value);
             }
@@ -1352,7 +1352,7 @@
             throw new NullPointerException();
         if (size > 0 && (tab = table) != null) {
             int mc = modCount;
-            for (Node<K, V> e : tab) {
+            for (Node<K,V> e : tab) {
                 for (; e != null; e = e.next) {
                     e.value = function.apply(e.key, e.value);
                 }
@@ -1395,9 +1395,10 @@
     }
 
     /**
-     * Save the state of the {@code HashMap} instance to a stream (i.e.,
-     * serialize it).
+     * Saves this map to a stream (that is, serializes it).
      *
+     * @param s the stream
+     * @throws IOException if an I/O error occurs
      * @serialData The <i>capacity</i> of the HashMap (the length of the
      *             bucket array) is emitted (int), followed by the
      *             <i>size</i> (an int, the number of key-value
@@ -1416,8 +1417,11 @@
     }
 
     /**
-     * Reconstitute the {@code HashMap} instance from a stream (i.e.,
-     * deserialize it).
+     * Reconstitutes this map from a stream (that is, deserializes it).
+     * @param s the stream
+     * @throws ClassNotFoundException if the class of a serialized object
+     *         could not be found
+     * @throws IOException if an I/O error occurs
      */
     private void readObject(java.io.ObjectInputStream s)
         throws IOException, ClassNotFoundException {
@@ -1450,7 +1454,7 @@
             // what we're actually creating.
             SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Map.Entry[].class, cap);
             @SuppressWarnings({"rawtypes","unchecked"})
-                Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
+            Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
             table = tab;
 
             // Read the keys and values, and put the mappings in the HashMap
@@ -1835,7 +1839,7 @@
     void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
         Node<K,V>[] tab;
         if (size > 0 && (tab = table) != null) {
-            for (Node<K, V> e : tab) {
+            for (Node<K,V> e : tab) {
                 for (; e != null; e = e.next) {
                     s.writeObject(e.key);
                     s.writeObject(e.value);
@@ -1956,7 +1960,6 @@
 
         /**
          * Forms tree of the nodes linked from this node.
-         * @return root of tree
          */
         final void treeify(Node<K,V>[] tab) {
             TreeNode<K,V> root = null;
@@ -2094,8 +2097,11 @@
                 return;
             if (root.parent != null)
                 root = root.root();
-            if (root == null || root.right == null ||
-                (rl = root.left) == null || rl.left == null) {
+            if (root == null
+                || (movable
+                    && (root.right == null
+                        || (rl = root.left) == null
+                        || rl.left == null))) {
                 tab[index] = first.untreeify(map);  // too small
                 return;
             }
@@ -2324,7 +2330,7 @@
 
         static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x) {
-            for (TreeNode<K,V> xp, xpl, xpr;;)  {
+            for (TreeNode<K,V> xp, xpl, xpr;;) {
                 if (x == null || x == root)
                     return root;
                 else if ((xp = x.parent) == null) {
--- a/test/java/util/concurrent/tck/ConcurrentHashMapTest.java	Thu Nov 09 16:10:46 2017 -0800
+++ b/test/java/util/concurrent/tck/ConcurrentHashMapTest.java	Tue Oct 03 13:45:11 2017 -0700
@@ -26,8 +26,9 @@
  * However, the following notice accompanied the original version of this
  * file:
  *
- * Written by Doug Lea with assistance from members of JCP JSR-166
- * Expert Group and released to the public domain, as explained at
+ * Written by Doug Lea and Martin Buchholz with assistance from
+ * members of JCP JSR-166 Expert Group and released to the public
+ * domain, as explained at
  * http://creativecommons.org/publicdomain/zero/1.0/
  * Other contributors include Andrew Wright, Jeffrey Hayes,
  * Pat Fisher, Mike Judd.
@@ -47,14 +48,25 @@
 import java.util.concurrent.Executors;
 
 import junit.framework.Test;
-import junit.framework.TestSuite;
 
 public class ConcurrentHashMapTest extends JSR166TestCase {
     public static void main(String[] args) {
         main(suite(), args);
     }
     public static Test suite() {
-        return new TestSuite(ConcurrentHashMapTest.class);
+        class Implementation implements MapImplementation {
+            public Class<?> klazz() { return ConcurrentHashMap.class; }
+            public Map emptyMap() { return new ConcurrentHashMap(); }
+            public Object makeKey(int i) { return i; }
+            public Object makeValue(int i) { return i; }
+            public boolean isConcurrent() { return true; }
+            public boolean permitsNullKeys() { return false; }
+            public boolean permitsNullValues() { return false; }
+            public boolean supportsSetValue() { return true; }
+        }
+        return newTestSuite(
+            ConcurrentHashMapTest.class,
+            MapTest.testSuite(new Implementation()));
     }
 
     /**
--- a/test/java/util/concurrent/tck/ConcurrentSkipListMapTest.java	Thu Nov 09 16:10:46 2017 -0800
+++ b/test/java/util/concurrent/tck/ConcurrentSkipListMapTest.java	Tue Oct 03 13:45:11 2017 -0700
@@ -45,14 +45,25 @@
 import java.util.concurrent.ConcurrentSkipListMap;
 
 import junit.framework.Test;
-import junit.framework.TestSuite;
 
 public class ConcurrentSkipListMapTest extends JSR166TestCase {
     public static void main(String[] args) {
         main(suite(), args);
     }
     public static Test suite() {
-        return new TestSuite(ConcurrentSkipListMapTest.class);
+        class Implementation implements MapImplementation {
+            public Class<?> klazz() { return ConcurrentSkipListMap.class; }
+            public Map emptyMap() { return new ConcurrentSkipListMap(); }
+            public Object makeKey(int i) { return i; }
+            public Object makeValue(int i) { return i; }
+            public boolean isConcurrent() { return true; }
+            public boolean permitsNullKeys() { return false; }
+            public boolean permitsNullValues() { return false; }
+            public boolean supportsSetValue() { return false; }
+        }
+        return newTestSuite(
+            ConcurrentSkipListMapTest.class,
+            MapTest.testSuite(new Implementation()));
     }
 
     /**
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/java/util/concurrent/tck/HashMapTest.java	Tue Oct 03 13:45:11 2017 -0700
@@ -0,0 +1,60 @@
+/*
+ * 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.
+ */
+
+/*
+ * This file is available under and governed by the GNU General Public
+ * License version 2 only, as published by the Free Software Foundation.
+ * However, the following notice accompanied the original version of this
+ * file:
+ *
+ * Written by Doug Lea and Martin Buchholz with assistance from
+ * members of JCP JSR-166 Expert Group and released to the public
+ * domain, as explained at
+ * http://creativecommons.org/publicdomain/zero/1.0/
+ */
+
+import java.util.HashMap;
+import java.util.Map;
+
+import junit.framework.Test;
+
+public class HashMapTest extends JSR166TestCase {
+    public static void main(String[] args) {
+        main(suite(), args);
+    }
+
+    public static Test suite() {
+        class Implementation implements MapImplementation {
+            public Class<?> klazz() { return HashMap.class; }
+            public Map emptyMap() { return new HashMap(); }
+            public Object makeKey(int i) { return i; }
+            public Object makeValue(int i) { return i; }
+            public boolean isConcurrent() { return false; }
+            public boolean permitsNullKeys() { return true; }
+            public boolean permitsNullValues() { return true; }
+            public boolean supportsSetValue() { return true; }
+        }
+        return newTestSuite(
+            // HashMapTest.class,
+            MapTest.testSuite(new Implementation()));
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/java/util/concurrent/tck/MapImplementation.java	Tue Oct 03 13:45:11 2017 -0700
@@ -0,0 +1,49 @@
+/*
+ * 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.
+ */
+
+/*
+ * This file is available under and governed by the GNU General Public
+ * License version 2 only, as published by the Free Software Foundation.
+ * However, the following notice accompanied the original version of this
+ * file:
+ *
+ * Written by Doug Lea and Martin Buchholz with assistance from
+ * members of JCP JSR-166 Expert Group and released to the public
+ * domain, as explained at
+ * http://creativecommons.org/publicdomain/zero/1.0/
+ */
+
+import java.util.Map;
+
+/** Allows tests to work with different Map implementations. */
+public interface MapImplementation {
+    /** Returns the Map implementation class. */
+    public Class<?> klazz();
+    /** Returns an empty map. */
+    public Map emptyMap();
+    public Object makeKey(int i);
+    public Object makeValue(int i);
+    public boolean isConcurrent();
+    public boolean permitsNullKeys();
+    public boolean permitsNullValues();
+    public boolean supportsSetValue();
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/java/util/concurrent/tck/MapTest.java	Tue Oct 03 13:45:11 2017 -0700
@@ -0,0 +1,172 @@
+/*
+ * 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.
+ */
+
+/*
+ * This file is available under and governed by the GNU General Public
+ * License version 2 only, as published by the Free Software Foundation.
+ * However, the following notice accompanied the original version of this
+ * file:
+ *
+ * Written by Doug Lea and Martin Buchholz with assistance from
+ * members of JCP JSR-166 Expert Group and released to the public
+ * domain, as explained at
+ * http://creativecommons.org/publicdomain/zero/1.0/
+ */
+
+import junit.framework.Test;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.concurrent.ThreadLocalRandom;
+
+/**
+ * Contains tests applicable to all Map implementations.
+ */
+public class MapTest extends JSR166TestCase {
+    final MapImplementation impl;
+
+    /** Tests are parameterized by a Map implementation. */
+    MapTest(MapImplementation impl, String methodName) {
+        super(methodName);
+        this.impl = impl;
+    }
+
+    public static Test testSuite(MapImplementation impl) {
+        return newTestSuite(
+            parameterizedTestSuite(MapTest.class,
+                                   MapImplementation.class,
+                                   impl));
+    }
+
+    public void testImplSanity() {
+        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        {
+            Map m = impl.emptyMap();
+            assertTrue(m.isEmpty());
+            assertEquals(0, m.size());
+            Object k = impl.makeKey(rnd.nextInt());
+            Object v = impl.makeValue(rnd.nextInt());
+            m.put(k, v);
+            assertFalse(m.isEmpty());
+            assertEquals(1, m.size());
+            assertTrue(m.containsKey(k));
+            assertTrue(m.containsValue(v));
+        }
+        {
+            Map m = impl.emptyMap();
+            Object v = impl.makeValue(rnd.nextInt());
+            if (impl.permitsNullKeys()) {
+                m.put(null, v);
+                assertTrue(m.containsKey(null));
+                assertTrue(m.containsValue(v));
+            } else {
+                assertThrows(NullPointerException.class, () -> m.put(null, v));
+            }
+        }
+        {
+            Map m = impl.emptyMap();
+            Object k = impl.makeKey(rnd.nextInt());
+            if (impl.permitsNullValues()) {
+                m.put(k, null);
+                assertTrue(m.containsKey(k));
+                assertTrue(m.containsValue(null));
+            } else {
+                assertThrows(NullPointerException.class, () -> m.put(k, null));
+            }
+        }
+        {
+            Map m = impl.emptyMap();
+            Object k = impl.makeKey(rnd.nextInt());
+            Object v1 = impl.makeValue(rnd.nextInt());
+            Object v2 = impl.makeValue(rnd.nextInt());
+            m.put(k, v1);
+            if (impl.supportsSetValue()) {
+                ((Map.Entry)(m.entrySet().iterator().next())).setValue(v2);
+                assertSame(v2, m.get(k));
+                assertTrue(m.containsKey(k));
+                assertTrue(m.containsValue(v2));
+                assertFalse(m.containsValue(v1));
+            } else {
+                assertThrows(UnsupportedOperationException.class,
+                             () -> ((Map.Entry)(m.entrySet().iterator().next())).setValue(v2));
+            }
+        }
+    }
+
+    /**
+     * Tests and extends the scenario reported in
+     * https://bugs.openjdk.java.net/browse/JDK-8186171
+     * HashMap: Entry.setValue may not work after Iterator.remove() called for previous entries
+     * ant -Djsr166.tckTestClass=HashMapTest -Djsr166.methodFilter=testBug8186171 -Djsr166.runsPerTest=1000 tck
+     */
+    public void testBug8186171() {
+        if (!impl.supportsSetValue()) return;
+        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        final boolean permitsNullValues = impl.permitsNullValues();
+        final Object v1 = (permitsNullValues && rnd.nextBoolean())
+            ? null : impl.makeValue(1);
+        final Object v2 = (permitsNullValues && rnd.nextBoolean() && v1 != null)
+            ? null : impl.makeValue(2);
+
+        /** If true, always lands in first bucket in hash tables. */
+        final boolean poorHash = rnd.nextBoolean();
+        class Key implements Comparable<Key> {
+            final int i;
+            Key(int i) { this.i = i; }
+            public int hashCode() { return poorHash ? 0 : super.hashCode(); }
+            public int compareTo(Key x) {
+                return Integer.compare(this.i, x.i);
+            }
+        }
+
+        // Both HashMap and ConcurrentHashMap have:
+        // TREEIFY_THRESHOLD = 8; UNTREEIFY_THRESHOLD = 6;
+        final int size = rnd.nextInt(1, 25);
+
+        List<Key> keys = new ArrayList<>();
+        for (int i = size; i-->0; ) keys.add(new Key(i));
+        Key keyToFrob = keys.get(rnd.nextInt(keys.size()));
+
+        Map<Key, Object> m = impl.emptyMap();
+        for (Key key : keys) m.put(key, v1);
+
+        for (Iterator<Map.Entry<Key, Object>> it = m.entrySet().iterator();
+             it.hasNext(); ) {
+            Map.Entry<Key, Object> entry = it.next();
+            if (entry.getKey() == keyToFrob)
+                entry.setValue(v2); // does this have the expected effect?
+            else
+                it.remove();
+        }
+
+        assertFalse(m.containsValue(v1));
+        assertTrue(m.containsValue(v2));
+        assertTrue(m.containsKey(keyToFrob));
+        assertEquals(1, m.size());
+    }
+
+//     public void testFailsIntentionallyForDebugging() {
+//         fail(impl.klazz().getSimpleName());
+//     }
+}
--- a/test/java/util/concurrent/tck/TreeMapTest.java	Thu Nov 09 16:10:46 2017 -0800
+++ b/test/java/util/concurrent/tck/TreeMapTest.java	Tue Oct 03 13:45:11 2017 -0700
@@ -44,14 +44,25 @@
 import java.util.TreeMap;
 
 import junit.framework.Test;
-import junit.framework.TestSuite;
 
 public class TreeMapTest extends JSR166TestCase {
     public static void main(String[] args) {
         main(suite(), args);
     }
     public static Test suite() {
-        return new TestSuite(TreeMapTest.class);
+        class Implementation implements MapImplementation {
+            public Class<?> klazz() { return TreeMap.class; }
+            public Map emptyMap() { return new TreeMap(); }
+            public Object makeKey(int i) { return i; }
+            public Object makeValue(int i) { return i; }
+            public boolean isConcurrent() { return false; }
+            public boolean permitsNullKeys() { return false; }
+            public boolean permitsNullValues() { return true; }
+            public boolean supportsSetValue() { return true; }
+        }
+        return newTestSuite(
+            TreeMapTest.class,
+            MapTest.testSuite(new Implementation()));
     }
 
     /**