8186171: HashMap: Entry.setValue may not work after Iterator.remove() called for previous entries
Reviewed-by: martin, psandoz
--- a/src/java.base/share/classes/java/util/HashMap.java Tue Oct 03 13:41:55 2017 -0700
+++ b/src/java.base/share/classes/java/util/HashMap.java Tue Oct 03 13:45:11 2017 -0700
@@ -490,7 +490,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
@@ -557,7 +557,7 @@
}
/**
- * Implements Map.get and related methods
+ * Implements Map.get and related methods.
*
* @param hash hash for key
* @param key the key
@@ -612,7 +612,7 @@
}
/**
- * Implements Map.put and related methods
+ * Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
@@ -700,7 +700,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) {
@@ -800,7 +800,7 @@
}
/**
- * Implements Map.remove and related methods
+ * Implements Map.remove and related methods.
*
* @param hash hash for key
* @param key the key
@@ -875,7 +875,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)))
@@ -927,7 +927,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);
}
@@ -975,7 +975,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);
}
@@ -1038,7 +1038,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);
}
@@ -1335,7 +1335,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);
}
@@ -1351,7 +1351,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);
}
@@ -1394,9 +1394,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
@@ -1415,8 +1416,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 {
@@ -1445,7 +1449,7 @@
threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
(int)ft : Integer.MAX_VALUE);
@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
@@ -1830,7 +1834,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);
@@ -1951,7 +1955,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;
@@ -2089,8 +2092,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;
}
@@ -2319,7 +2325,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/jdk/java/util/concurrent/tck/ConcurrentHashMapTest.java Tue Oct 03 13:41:55 2017 -0700
+++ b/test/jdk/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.
@@ -45,14 +46,25 @@
import java.util.concurrent.ConcurrentHashMap;
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/jdk/java/util/concurrent/tck/ConcurrentSkipListMapTest.java Tue Oct 03 13:41:55 2017 -0700
+++ b/test/jdk/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/jdk/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/jdk/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/jdk/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/jdk/java/util/concurrent/tck/TreeMapTest.java Tue Oct 03 13:41:55 2017 -0700
+++ b/test/jdk/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()));
}
/**