United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
Bug ID: JDK-6197726 (coll) IdentityHashMap.entrySet().toArray(T[] a) is incorrectly implemented
JDK-6197726 : (coll) IdentityHashMap.entrySet().toArray(T[] a) is incorrectly implemented

Details
Type:
Bug
Submit Date:
2004-11-19
Status:
Closed
Updated Date:
2012-10-08
Project Name:
JDK
Resolved Date:
2005-09-04
Component:
core-libs
OS:
solaris_9,generic,windows_xp
Sub-Component:
java.util:collections
CPU:
x86,sparc,generic
Priority:
P3
Resolution:
Fixed
Affected Versions:
5.0,6
Fixed Versions:

Related Reports
Backport:
Duplicate:
Relates:
Relates:
Relates:
Relates:

Sub Tasks

Description
FULL PRODUCT VERSION :
java version "1.5.0"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0-b64)
Java HotSpot(TM) Client VM (build 1.5.0-b64, mixed mode, sharing)

ADDITIONAL OS VERSION INFORMATION :
XP SP2

A DESCRIPTION OF THE PROBLEM :
(inbound IdentityHashMap ip)

int sz = ip.size();
Object [] entries = new Object[sz];
ip.entrySet().toArray(entries);

Entries contains nulls, even though there is room for entries in the given array.

Look at the implementation, we find this:

public <T> T[] toArray(T[] a) {
	    return (T[])toArray(); // !!!!
        }

Seems like it was never implemented, and a placeholder was left.


STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
run code above

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
entries array should contain Map.Entry objects, not nulls.

ACTUAL -
entries array contains only nulls, as it is never written to.

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
IdentityHashMap im = new IdentityHashMap();
im.put(im,im);
Object [] o = new Object[1];
im.entrySet().toArray(o);


---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
never call toArray(object [])

                                    

Comments
EVALUATION

toArray() could indeed be more efficient and, more importantly,
toArray(T[]) is not completely implemented.

###@###.### 2005-06-15 18:25:51 GMT
                                     
2005-06-15
EVALUATION

I independently found this while examining 

5031890 (coll spec) Collection toArray() does not specify empty collection behavior

I have a nice test framework for testing this kind of stuff more globally,
and have been working on toArray before, so I'm taking ownership of this bug.
                                     
2005-08-06
SUGGESTED FIX

--- /u/martin/ws/mustang/src/share/classes/java/util/IdentityHashMap.java	2004-08-27 15:54:50.658979000 -0700
+++ /u/martin/ws/toArray/src/share/classes/java/util/IdentityHashMap.java	2005-08-07 22:56:46.405135000 -0700
@@ -1109,13 +1109,26 @@
         }
 
         public Object[] toArray() {
-            List<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size());
-            for (Map.Entry<K,V> e : this)
-                c.add(new AbstractMap.SimpleEntry<K,V>(e));
-            return c.toArray();
+	    int size = size();
+	    Object[] result = new Object[size];
+	    Iterator<Map.Entry<K,V>> it = iterator();
+	    for (int i=0; i < size; i++)
+		result[i] = new AbstractMap.SimpleEntry<K,V>(it.next());
+	    return result;
         }
         public <T> T[] toArray(T[] a) {
-	    return (T[])toArray(); // !!!!
+	    int size = size();
+	    if (a.length < size)
+		a = (T[])java.lang.reflect.Array
+		    .newInstance(a.getClass().getComponentType(), size);
+
+	    Iterator<Map.Entry<K,V>> it = iterator();
+	    Object[] result = a;
+	    for (int i=0; i<size; i++)
+		result[i] = new AbstractMap.SimpleEntry<K,V>(it.next());
+	    if (a.length > size)
+		a[size] = null;
+	    return a;
         }
     }
 
--- /u/martin/ws/mustang/test/java/util/IdentityHashMap/ToArray.java	2004-08-27 16:19:49.069257000 -0700
+++ /u/martin/ws/toArray/test/java/util/IdentityHashMap/ToArray.java	2005-08-07 22:56:46.955474000 -0700
@@ -1,16 +1,19 @@
 /*
- * @test    1.1 01/08/06
- * @bug     4485486
- * @summary IdentityHashMap's lack of internal entry objects caused the 
- *          inherited (AbstractMap) version of toArray to return garbage
- *          when called on the entrySet view.
- * @author  Josh Bloch
+ * @test    1.2 05/08/07
+ * @bug     4485486 6197726
+ * @summary IdentityHashMap's entrySet toArray tests
+ * @author  Josh Bloch, Martin Buchholz
  */
 
 import java.util.*;
 
 public class ToArray {
     public static void main(String[] args) {
+	//----------------------------------------------------------------
+	// IdentityHashMap's lack of internal entry objects caused
+	// the inherited (AbstractMap) version of toArray to
+	// return garbage when called on the entrySet view.
+	//----------------------------------------------------------------
         Map m = new IdentityHashMap();
         m.put("french", "connection");
         m.put("polish", "sausage");
@@ -20,5 +23,28 @@
 
         mArray[0].toString();
         mArray[1].toString();
+
+	//----------------------------------------------------------------
+	// IdentityHashMap.entrySet().toArray(T[] a) used to simply
+	// return toArray() !
+	//----------------------------------------------------------------
+	IdentityHashMap<Integer,Integer> map
+	    = new IdentityHashMap<Integer,Integer>();
+	Set<Map.Entry<Integer,Integer>> es = map.entrySet();
+	if (es.toArray().length != 0)
+	    throw new Error("non-empty");
+	if (es.toArray(new Object[]{Boolean.TRUE})[0] != null)
+	    throw new Error("non-null");
+	map.put(7,49);
+	if (es.toArray().length != 1)
+	    throw new Error("length");
+	Object[] x = es.toArray(new Object[]{Boolean.TRUE, Boolean.TRUE});
+	if (x[1] != null)
+	    throw new Error("non-null");
+	Map.Entry e = (Map.Entry) x[0];
+	if (! e.getKey().equals(new Integer(7)))
+	    throw new Error("bad key");
+	if (! e.getValue().equals(new Integer(49)))
+	    throw new Error("bad value");
     }
 }
--- /u/martin/ws/mustang/src/share/classes/java/util/ArrayList.java	2005-06-08 14:05:18.407383000 -0700
+++ /u/martin/ws/toArray/src/share/classes/java/util/ArrayList.java	2005-08-14 18:17:17.878695000 -0700
@@ -132,9 +132,8 @@
     public ArrayList(Collection<? extends E> c) {
         size = c.size();
         // Allow 10% room for growth
-        elementData = (E[])new Object[
-                      (int)Math.min((size*110L)/100,Integer.MAX_VALUE)]; 
-        c.toArray(elementData);
+	int capacity = (int) Math.min((size*110L)/100, Integer.MAX_VALUE);
+        elementData = (E[]) c.toArray(new Object[capacity]);
     }
 
     /**
                                     
2005-08-08
EVALUATION

Doug Lea suggested changing ArrayList(Collection) constructor to
make it slightly more robust in the sense that the code would work 
if the argument was any other collection class
having the same bug as IdentityHashMap.  
(Collection classes often get copied and modified)
                                     
2005-08-15
EVALUATION

The deeper problem of returning the same object on each call to next()
is being addressed via 6312706.  Most of the obvious manifestations
of that behavior are being fixed here.
                                     
2005-08-18



Hardware and Software, Engineered to Work Together