It's a little disconcerting to still keep finding basic correctness bugs in core Collections classes. Here's a fix (again demonstrating that the Mother Of All Collections Tests is not thorough enough): Review requested from Chris Hegarty, Doug Lea # HG changeset patch # User martin # Date 1208733844 25200 # Node ID fd80580439549ed34473cfa973f34d29f9efd7a6 # Parent 8513593a57f180641d06cf535f1647cb9160f9e0 6691215: (coll) IdentityHashMap.containsValue(null) returns true when null value not present Reviewed-by: Contributed-by: Scott Blum <scottb@google.com> diff --git a/src/share/classes/java/util/IdentityHashMap.java b/src/share/classes/java/util/IdentityHashMap.java --- a/src/share/classes/java/util/IdentityHashMap.java +++ b/src/share/classes/java/util/IdentityHashMap.java @@ -188,7 +188,6 @@ public class IdentityHashMap<K,V> /** * Use NULL_KEY for key if it is null. */ - private static Object maskNull(Object key) { return (key == null ? NULL_KEY : key); } @@ -378,8 +377,8 @@ public class IdentityHashMap<K,V> */ public boolean containsValue(Object value) { Object[] tab = table; - for (int i = 1; i < tab.length; i+= 2) - if (tab[i] == value) + for (int i = 1; i < tab.length; i += 2) + if (tab[i] == value && tab[i - 1] != null) return true; return false; @@ -905,7 +904,6 @@ public class IdentityHashMap<K,V> * view the first time this view is requested. The view is stateless, * so there's no reason to create more than one. */ - private transient Set<Map.Entry<K,V>> entrySet = null; /** diff --git a/test/java/util/Collection/MOAT.java b/test/java/util/Collection/MOAT.java --- a/test/java/util/Collection/MOAT.java +++ b/test/java/util/Collection/MOAT.java @@ -25,7 +25,7 @@ * @test * @bug 6207984 6272521 6192552 6269713 6197726 6260652 5073546 4137464 * 4155650 4216399 4294891 6282555 6318622 6355327 6383475 6420753 - * 6431845 4802633 6570566 6570575 6570631 6570924 6691185 + * 6431845 4802633 6570566 6570575 6570631 6570924 6691185 6691215 * @summary Run many tests on many Collection and Map implementations * @author Martin Buchholz */ @@ -247,6 +247,13 @@ public class MOAT { testEmptySet(m.keySet()); testEmptySet(m.entrySet()); testEmptyCollection(m.values()); + + try { check(! m.containsValue(null)); } + catch (NullPointerException _) { /* OK */ } + try { check(! m.containsKey(null)); } + catch (NullPointerException _) { /* OK */ } + check(! m.containsValue(1)); + check(! m.containsKey(1)); } private static void testImmutableMap(final Map<Integer,Integer> m) { Martin On Sun, Apr 20, 2008 at 3:07 AM, Alan Bateman <Alan.Bateman@sun.com> wrote:
Joshua Bloch wrote:
Folks,
While we're at it, here's another Collections bug discovered recently by a
Googler (Scott Blum). The value of this expression should be false:
new IdentityHashMap().containsValue(null)
Unfortunately, it's true. Looking at the code for containsValue, it's
obvious what's wrong:
/** * Tests whether the specified object reference is a value in this
identity
* hash map. * * @param value value whose presence in this map is to be tested * @return <tt>true</tt> if this map maps one or more keys to the * specified object reference * @see #containsKey(Object) */ public boolean containsValue(Object value) { Object[] tab = table; for (int i = 1; i < tab.length; i+= 2) if (tab[i] == value) return true;
return false; }
Empty entries are masquerading as entries mapping to null. The fix is
easy:
if (tab[i] == value)
becomes:
if (tab[i] == value && tab[i -1] != null)
(Recall that the null key (but not value) is proxied by NULL_KEY.)
Josh
I don't see this in the bug database so I've created the following so that it doesn't get lost: 6691215: (coll) IdentityHashMap.containsValue(null) returns true when null value not present
-Alan.