Return-Path: Delivered-To: apmail-harmony-dev-archive@www.apache.org Received: (qmail 49820 invoked from network); 15 May 2009 15:57:15 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.3) by minotaur.apache.org with SMTP; 15 May 2009 15:57:15 -0000 Received: (qmail 64104 invoked by uid 500); 15 May 2009 15:57:15 -0000 Delivered-To: apmail-harmony-dev-archive@harmony.apache.org Received: (qmail 64019 invoked by uid 500); 15 May 2009 15:57:15 -0000 Mailing-List: contact dev-help@harmony.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@harmony.apache.org Delivered-To: mailing list dev@harmony.apache.org Received: (qmail 64008 invoked by uid 99); 15 May 2009 15:57:15 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 15 May 2009 15:57:15 +0000 X-ASF-Spam-Status: No, hits=-0.0 required=10.0 tests=SPF_PASS X-Spam-Check-By: apache.org Received-SPF: pass (nike.apache.org: domain of sianjanuary@googlemail.com designates 209.85.218.163 as permitted sender) Received: from [209.85.218.163] (HELO mail-bw0-f163.google.com) (209.85.218.163) by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 15 May 2009 15:57:02 +0000 Received: by bwz7 with SMTP id 7so1924906bwz.36 for ; Fri, 15 May 2009 08:56:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :date:message-id:subject:from:to:content-type :content-transfer-encoding; bh=9Ko3ZOYeB4/TnGOmC1ofv/damWV+hiDyZ5faWAGqzl8=; b=xPCmGVpDeBHKDSo8KkxZADa9Ng5cxwTBM+0ExluCoO9URRSOaB4MGYzk0urghbVQX0 mT9GBX+S4n1Zg2zbENke0NsXP0VqoS58X+EYjcMdf9/9GyrvYxYdYlyUJ0YQ5TTvFGpT m7mF+l3vlMk9uWqEhGNXvVVroq/DjVa5U9T60= DomainKey-Signature: a=rsa-sha1; c=nofws; d=googlemail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type:content-transfer-encoding; b=NseoRSvi5uvNL2DCDvq25ugnQqOGQglgq9k+8pKmrNXOA6xQgRYQNG0F9k5HtWvQ0f t25E8ce6hM0zb7E3euDCtJQaazUv+/JA+PzXO4zccedeJjC4v25Runyq7W5q1D+FYgFD B8jjzcwMuXK6JBBDeIv3ndNogIf5ncmBQS3f8= MIME-Version: 1.0 Received: by 10.223.114.68 with SMTP id d4mr2690305faq.86.1242403001557; Fri, 15 May 2009 08:56:41 -0700 (PDT) In-Reply-To: <5948b71e0905150540o73028b6cqe6112406818d1b41@mail.gmail.com> References: <20090515090828.DA29A2388875@eris.apache.org> <5948b71e0905150536tfd38838r5591a4a32815a012@mail.gmail.com> <5948b71e0905150540o73028b6cqe6112406818d1b41@mail.gmail.com> Date: Fri, 15 May 2009 16:56:41 +0100 Message-ID: Subject: Re: svn commit: r775060 - in /harmony/enhanced/classlib/trunk/modules/luni/src: main/java/java/util/IdentityHashMap.java test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java From: Sian January To: dev@harmony.apache.org Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Virus-Checked: Checked by ClamAV on apache.org Hi Charles, Thanks for explaining the issue a bit better. Your patch looks like it could be a good solution, but I'm wondering if there's a reason why only one array was used in the first place (maybe performance?). It would also be good to have some more tests with a range of large values to check that we do the same as the RI in all situations before making such a big change - as you say, if the previous fix was a workaround for one test case and wasn't right then one test case probably isn't enough. Thanks, Sian 2009/5/15 Charles Lee : > Here is my patch. What about this? > > diff --git modules/luni/src/main/java/java/util/IdentityHashMap.java > modules/luni/src/main/java/java/util/IdentityHashMap.java > index 034ee07..bc26fa5 100644 > --- modules/luni/src/main/java/java/util/IdentityHashMap.java > +++ modules/luni/src/main/java/java/util/IdentityHashMap.java > @@ -44,10 +44,16 @@ public class IdentityHashMap extends > AbstractMap implements > =A0 =A0 private static final long serialVersionUID =3D 818821812835391321= 6L; > > =A0 =A0 /* > - =A0 =A0 * The internal data structure to hold key value pairs This arra= y holds > keys > - =A0 =A0 * and values in an alternating fashion. > + =A0 =A0 * The internal data structure to hold key. This array holds key= s > + =A0 =A0 * in an alternating fashion. > =A0 =A0 =A0*/ > - =A0 =A0transient Object[] elementData; > + =A0 =A0transient Object[] keyData; > + > + =A0 =A0/* > + =A0 =A0 * The internal data structure to hold value. This array holds v= alues > + =A0 =A0 * in an alternating fashion. > + =A0 =A0 */ > + =A0 =A0transient Object[] valueData; > > =A0 =A0 /* Actual number of key-value pairs. */ > =A0 =A0 int size; > @@ -65,7 +71,10 @@ public class IdentityHashMap extends AbstractMap= V> implements > =A0 =A0 private static final int DEFAULT_MAX_SIZE =3D 21; > > =A0 =A0 /* Default load factor of 0.75; */ > - =A0 =A0private static final int loadFactor =3D 7500; > + =A0 =A0private static final int loadFactorNumerator =3D 3; > + =A0 =A0private static final int loadFactorDenominator =3D 4; > + =A0 =A0/* 1610612735 */ > + =A0 =A0private static final int barrier =3D (int)((long)Integer.MAX_VAL= UE * > loadFactorNumerator / loadFactorDenominator); > > =A0 =A0 /* > =A0 =A0 =A0* modification count, to keep track of structural modification= s > between the > @@ -136,10 +145,10 @@ public class IdentityHashMap extends > AbstractMap implements > =A0 =A0 =A0 =A0 } > > =A0 =A0 =A0 =A0 public boolean hasNext() { > - =A0 =A0 =A0 =A0 =A0 =A0while (position < associatedMap.elementData.leng= th) { > + =A0 =A0 =A0 =A0 =A0 =A0while (position < associatedMap.keyData.length) = { > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 // if this is an empty spot, go to the ne= xt one > - =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0if (associatedMap.elementData[position] = =3D=3D null) { > - =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0position +=3D 2; > + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0if (associatedMap.keyData[position] =3D= =3D null) { > + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0position++; > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 } else { > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 return true; > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 } > @@ -162,7 +171,7 @@ public class IdentityHashMap extends > AbstractMap implements > =A0 =A0 =A0 =A0 =A0 =A0 IdentityHashMapEntry result =3D associate= dMap > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 .getEntry(position); > =A0 =A0 =A0 =A0 =A0 =A0 lastPosition =3D position; > - =A0 =A0 =A0 =A0 =A0 =A0position +=3D 2; > + =A0 =A0 =A0 =A0 =A0 =A0position++; > > =A0 =A0 =A0 =A0 =A0 =A0 canRemove =3D true; > =A0 =A0 =A0 =A0 =A0 =A0 return type.get(result); > @@ -175,7 +184,7 @@ public class IdentityHashMap extends > AbstractMap implements > =A0 =A0 =A0 =A0 =A0 =A0 } > > =A0 =A0 =A0 =A0 =A0 =A0 canRemove =3D false; > - =A0 =A0 =A0 =A0 =A0 =A0associatedMap.remove(associatedMap.elementData[l= astPosition]); > + =A0 =A0 =A0 =A0 =A0 =A0associatedMap.remove(associatedMap.keyData[lastP= osition]); > =A0 =A0 =A0 =A0 =A0 =A0 position =3D lastPosition; > =A0 =A0 =A0 =A0 =A0 =A0 expectedModCount++; > =A0 =A0 =A0 =A0 } > @@ -252,7 +261,9 @@ public class IdentityHashMap extends > AbstractMap implements > =A0 =A0 =A0 =A0 if (maxSize >=3D 0) { > =A0 =A0 =A0 =A0 =A0 =A0 this.size =3D 0; > =A0 =A0 =A0 =A0 =A0 =A0 threshold =3D getThreshold(maxSize); > - =A0 =A0 =A0 =A0 =A0 =A0elementData =3D newElementArray(computeElementAr= raySize()); > + =A0 =A0 =A0 =A0 =A0 =A0int length =3D computeElementArraySize(); > + =A0 =A0 =A0 =A0 =A0 =A0keyData =3D new Object[length]; > + =A0 =A0 =A0 =A0 =A0 =A0valueData =3D new Object[length]; > =A0 =A0 =A0 =A0 } else { > =A0 =A0 =A0 =A0 =A0 =A0 throw new IllegalArgumentException(); > =A0 =A0 =A0 =A0 } > @@ -265,18 +276,12 @@ public class IdentityHashMap extends > AbstractMap implements > =A0 =A0 } > > =A0 =A0 private int computeElementArraySize() { > - =A0 =A0 =A0 =A0return (int) (((long) threshold * 10000) / loadFactor) *= 2; > - =A0 =A0} > - > - =A0 =A0/** > - =A0 =A0 * Create a new element array > - =A0 =A0 * > - =A0 =A0 * @param s > - =A0 =A0 * =A0 =A0 =A0 =A0 =A0 =A0the number of elements > - =A0 =A0 * @return Reference to the element array > - =A0 =A0 */ > - =A0 =A0private Object[] newElementArray(int s) { > - =A0 =A0 =A0 =A0return new Object[s]; > + =A0 =A0 =A0 =A0if (threshold >=3D barrier) { > + =A0 =A0 =A0 =A0 =A0 =A0// Could not apply for the factor, we return the= max value > + =A0 =A0 =A0 =A0 =A0 =A0return Integer.MAX_VALUE; > + =A0 =A0 =A0 =A0} else { > + =A0 =A0 =A0 =A0 =A0 =A0return (int) (((long) threshold * loadFactorDeno= minator) / > loadFactorNumerator); > + =A0 =A0 =A0 =A0} > =A0 =A0 } > > =A0 =A0 /** > @@ -307,8 +312,9 @@ public class IdentityHashMap extends > AbstractMap implements > =A0 =A0 @Override > =A0 =A0 public void clear() { > =A0 =A0 =A0 =A0 size =3D 0; > - =A0 =A0 =A0 =A0for (int i =3D 0; i < elementData.length; i++) { > - =A0 =A0 =A0 =A0 =A0 =A0elementData[i] =3D null; > + =A0 =A0 =A0 =A0for (int i =3D 0; i < keyData.length; i++) { > + =A0 =A0 =A0 =A0 =A0 =A0keyData[i] =3D null; > + =A0 =A0 =A0 =A0 =A0 =A0valueData[i] =3D null; > =A0 =A0 =A0 =A0 } > =A0 =A0 =A0 =A0 modCount++; > =A0 =A0 } > @@ -326,8 +332,8 @@ public class IdentityHashMap extends > AbstractMap implements > =A0 =A0 =A0 =A0 =A0 =A0 key =3D NULL_OBJECT; > =A0 =A0 =A0 =A0 } > > - =A0 =A0 =A0 =A0int index =3D findIndex(key, elementData); > - =A0 =A0 =A0 =A0return elementData[index] =3D=3D key; > + =A0 =A0 =A0 =A0int index =3D findIndex(key, keyData); > + =A0 =A0 =A0 =A0return keyData[index] =3D=3D key; > =A0 =A0 } > > =A0 =A0 /** > @@ -345,8 +351,8 @@ public class IdentityHashMap extends > AbstractMap implements > =A0 =A0 =A0 =A0 =A0 =A0 value =3D NULL_OBJECT; > =A0 =A0 =A0 =A0 } > > - =A0 =A0 =A0 =A0for (int i =3D 1; i < elementData.length; i =3D i + 2) { > - =A0 =A0 =A0 =A0 =A0 =A0if (elementData[i] =3D=3D value) { > + =A0 =A0 =A0 =A0for (int i =3D 1; i < valueData.length; i++) { > + =A0 =A0 =A0 =A0 =A0 =A0if (valueData[i] =3D=3D value) { > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 return true; > =A0 =A0 =A0 =A0 =A0 =A0 } > =A0 =A0 =A0 =A0 } > @@ -366,10 +372,10 @@ public class IdentityHashMap extends > AbstractMap implements > =A0 =A0 =A0 =A0 =A0 =A0 key =3D NULL_OBJECT; > =A0 =A0 =A0 =A0 } > > - =A0 =A0 =A0 =A0int index =3D findIndex(key, elementData); > + =A0 =A0 =A0 =A0int index =3D findIndex(key, keyData); > > - =A0 =A0 =A0 =A0if (elementData[index] =3D=3D key) { > - =A0 =A0 =A0 =A0 =A0 =A0Object result =3D elementData[index + 1]; > + =A0 =A0 =A0 =A0if (keyData[index] =3D=3D key) { > + =A0 =A0 =A0 =A0 =A0 =A0Object result =3D valueData[index]; > =A0 =A0 =A0 =A0 =A0 =A0 return massageValue(result); > =A0 =A0 =A0 =A0 } > > @@ -381,8 +387,8 @@ public class IdentityHashMap extends > AbstractMap implements > =A0 =A0 =A0 =A0 =A0 =A0 key =3D NULL_OBJECT; > =A0 =A0 =A0 =A0 } > > - =A0 =A0 =A0 =A0int index =3D findIndex(key, elementData); > - =A0 =A0 =A0 =A0if (elementData[index] =3D=3D key) { > + =A0 =A0 =A0 =A0int index =3D findIndex(key, keyData); > + =A0 =A0 =A0 =A0if (keyData[index] =3D=3D key) { > =A0 =A0 =A0 =A0 =A0 =A0 return getEntry(index); > =A0 =A0 =A0 =A0 } > > @@ -395,8 +401,8 @@ public class IdentityHashMap extends > AbstractMap implements > =A0 =A0 =A0*/ > =A0 =A0 @SuppressWarnings("unchecked") > =A0 =A0 private IdentityHashMapEntry getEntry(int index) { > - =A0 =A0 =A0 =A0Object key =3D elementData[index]; > - =A0 =A0 =A0 =A0Object value =3D elementData[index + 1]; > + =A0 =A0 =A0 =A0Object key =3D keyData[index]; > + =A0 =A0 =A0 =A0Object value =3D valueData[index]; > > =A0 =A0 =A0 =A0 if (key =3D=3D NULL_OBJECT) { > =A0 =A0 =A0 =A0 =A0 =A0 key =3D null; > @@ -424,7 +430,7 @@ public class IdentityHashMap extends > AbstractMap implements > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0*/ > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 break; > =A0 =A0 =A0 =A0 =A0 =A0 } > - =A0 =A0 =A0 =A0 =A0 =A0index =3D (index + 2) % length; > + =A0 =A0 =A0 =A0 =A0 =A0index =3D (index + 1) % length; > =A0 =A0 =A0 =A0 } > =A0 =A0 =A0 =A0 return index; > =A0 =A0 } > @@ -455,24 +461,24 @@ public class IdentityHashMap extends > AbstractMap implements > =A0 =A0 =A0 =A0 =A0 =A0 _value =3D NULL_OBJECT; > =A0 =A0 =A0 =A0 } > > - =A0 =A0 =A0 =A0int index =3D findIndex(_key, elementData); > + =A0 =A0 =A0 =A0int index =3D findIndex(_key, keyData); > > =A0 =A0 =A0 =A0 // if the key doesn't exist in the table > - =A0 =A0 =A0 =A0if (elementData[index] !=3D _key) { > + =A0 =A0 =A0 =A0if (keyData[index] !=3D _key) { > =A0 =A0 =A0 =A0 =A0 =A0 modCount++; > =A0 =A0 =A0 =A0 =A0 =A0 if (++size > threshold) { > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 rehash(); > - =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0index =3D findIndex(_key, elementData); > + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0index =3D findIndex(_key, keyData); > =A0 =A0 =A0 =A0 =A0 =A0 } > > =A0 =A0 =A0 =A0 =A0 =A0 // insert the key and assign the value to null in= itially > - =A0 =A0 =A0 =A0 =A0 =A0elementData[index] =3D _key; > - =A0 =A0 =A0 =A0 =A0 =A0elementData[index + 1] =3D null; > + =A0 =A0 =A0 =A0 =A0 =A0keyData[index] =3D _key; > + =A0 =A0 =A0 =A0 =A0 =A0valueData[index] =3D null; > =A0 =A0 =A0 =A0 } > > =A0 =A0 =A0 =A0 // insert value to where it needs to go, return the old v= alue > - =A0 =A0 =A0 =A0Object result =3D elementData[index + 1]; > - =A0 =A0 =A0 =A0elementData[index + 1] =3D _value; > + =A0 =A0 =A0 =A0Object result =3D valueData[index]; > + =A0 =A0 =A0 =A0valueData[index] =3D _value; > > =A0 =A0 =A0 =A0 return massageValue(result); > =A0 =A0 } > @@ -493,26 +499,29 @@ public class IdentityHashMap extends > AbstractMap implements > =A0 =A0 } > > =A0 =A0 private void rehash() { > - =A0 =A0 =A0 =A0int newlength =3D elementData.length << 1; > + =A0 =A0 =A0 =A0int newlength =3D keyData.length << 1; > =A0 =A0 =A0 =A0 if (newlength =3D=3D 0) { > =A0 =A0 =A0 =A0 =A0 =A0 newlength =3D 1; > =A0 =A0 =A0 =A0 } > - =A0 =A0 =A0 =A0Object[] newData =3D newElementArray(newlength); > - =A0 =A0 =A0 =A0for (int i =3D 0; i < elementData.length; i =3D i + 2) { > - =A0 =A0 =A0 =A0 =A0 =A0Object key =3D elementData[i]; > + =A0 =A0 =A0 =A0Object[] newKeyData =3D new Object[newlength]; > + =A0 =A0 =A0 =A0Object[] newValueData =3D new Object[newlength]; > + =A0 =A0 =A0 =A0for (int i =3D 0; i < keyData.length; i++) { > + =A0 =A0 =A0 =A0 =A0 =A0Object key =3D keyData[i]; > =A0 =A0 =A0 =A0 =A0 =A0 if (key !=3D null) { > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 // if not empty > - =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0int index =3D findIndex(key, newData); > - =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0newData[index] =3D key; > - =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0newData[index + 1] =3D elementData[i + 1= ]; > + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0int index =3D findIndex(key, newKeyData)= ; > + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0newKeyData[index] =3D key; > + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0newValueData[index] =3D valueData[i]; > =A0 =A0 =A0 =A0 =A0 =A0 } > =A0 =A0 =A0 =A0 } > - =A0 =A0 =A0 =A0elementData =3D newData; > + =A0 =A0 =A0 =A0keyData =3D newKeyData; > + =A0 =A0 =A0 =A0valueData =3D newValueData; > =A0 =A0 =A0 =A0 computeMaxSize(); > =A0 =A0 } > > =A0 =A0 private void computeMaxSize() { > - =A0 =A0 =A0 =A0threshold =3D (int) ((long) (elementData.length / 2) * l= oadFactor / > 10000); > + =A0 =A0 =A0 =A0// very weird > + =A0 =A0 =A0 =A0threshold =3D (int) ((long) keyData.length * loadFactorN= umerator / > loadFactorDenominator); > =A0 =A0 } > > =A0 =A0 /** > @@ -532,21 +541,22 @@ public class IdentityHashMap extends > AbstractMap implements > =A0 =A0 =A0 =A0 boolean hashedOk; > =A0 =A0 =A0 =A0 int index, next, hash; > =A0 =A0 =A0 =A0 Object result, object; > - =A0 =A0 =A0 =A0index =3D next =3D findIndex(key, elementData); > + =A0 =A0 =A0 =A0index =3D next =3D findIndex(key, keyData); > > - =A0 =A0 =A0 =A0if (elementData[index] !=3D key) { > + =A0 =A0 =A0 =A0if (keyData[index] !=3D key) { > =A0 =A0 =A0 =A0 =A0 =A0 return null; > =A0 =A0 =A0 =A0 } > > =A0 =A0 =A0 =A0 // store the value for this key > - =A0 =A0 =A0 =A0result =3D elementData[index + 1]; > + =A0 =A0 =A0 =A0result =3D valueData[index]; > > =A0 =A0 =A0 =A0 // shift the following elements up if needed > =A0 =A0 =A0 =A0 // until we reach an empty spot > - =A0 =A0 =A0 =A0int length =3D elementData.length; > + =A0 =A0 =A0 =A0int length =3D keyData.length; > + =A0 =A0 =A0 =A0boolean forward =3D false; > =A0 =A0 =A0 =A0 while (true) { > - =A0 =A0 =A0 =A0 =A0 =A0next =3D (next + 2) % length; > - =A0 =A0 =A0 =A0 =A0 =A0object =3D elementData[next]; > + =A0 =A0 =A0 =A0 =A0 =A0next =3D (next + 1) % length; > + =A0 =A0 =A0 =A0 =A0 =A0object =3D keyData[next]; > =A0 =A0 =A0 =A0 =A0 =A0 if (object =3D=3D null) { > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 break; > =A0 =A0 =A0 =A0 =A0 =A0 } > @@ -559,19 +569,24 @@ public class IdentityHashMap extends > AbstractMap implements > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 hashedOk =3D hashedOk && (hash <=3D next)= ; > =A0 =A0 =A0 =A0 =A0 =A0 } > =A0 =A0 =A0 =A0 =A0 =A0 if (!hashedOk) { > - =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0elementData[index] =3D object; > - =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0elementData[index + 1] =3D elementData[n= ext + 1]; > + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0keyData[index] =3D object; > + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0valueData[index] =3D valueData[next]; > =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 index =3D next; > + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0keyData[next] =3D null; > + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0valueData[next] =3D null; > + =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0forward =3D true; > =A0 =A0 =A0 =A0 =A0 =A0 } > =A0 =A0 =A0 =A0 } > + > + =A0 =A0 =A0 =A0if (!forward) { > + =A0 =A0 =A0 =A0 =A0 =A0// no other has been forwarded, we should delete= the key and > value > + =A0 =A0 =A0 =A0 =A0 =A0keyData[index] =3D null; > + =A0 =A0 =A0 =A0 =A0 =A0valueData[index] =3D null; > + =A0 =A0 =A0 =A0} > > =A0 =A0 =A0 =A0 size--; > =A0 =A0 =A0 =A0 modCount++; > > - =A0 =A0 =A0 =A0// clear both the key and the value > - =A0 =A0 =A0 =A0elementData[index] =3D null; > - =A0 =A0 =A0 =A0elementData[index + 1] =3D null; > - > =A0 =A0 =A0 =A0 return massageValue(result); > =A0 =A0 } > > @@ -783,7 +798,9 @@ public class IdentityHashMap extends > AbstractMap implements > =A0 =A0 =A0 =A0 stream.defaultReadObject(); > =A0 =A0 =A0 =A0 int savedSize =3D stream.readInt(); > =A0 =A0 =A0 =A0 threshold =3D getThreshold(DEFAULT_MAX_SIZE); > - =A0 =A0 =A0 =A0elementData =3D newElementArray(computeElementArraySize(= )); > + =A0 =A0 =A0 =A0int length =3D computeElementArraySize(); > + =A0 =A0 =A0 =A0keyData =3D new Object[length]; > + =A0 =A0 =A0 =A0valueData =3D new Object[length]; > =A0 =A0 =A0 =A0 for (int i =3D savedSize; --i >=3D 0;) { > =A0 =A0 =A0 =A0 =A0 =A0 K key =3D (K) stream.readObject(); > =A0 =A0 =A0 =A0 =A0 =A0 put(key, (V) stream.readObject()); > > > > > On Fri, May 15, 2009 at 8:36 PM, Charles Lee wrot= e: > >> Hi, Sian. >> >> It seems that this patch is a workaround about the testcase. What if our >> user really can malloc Integer.MAX_VALUE memorys to hold the hashmap? An= d >> the size is also not right if we just negate the overflow one, it will c= ause >> the potential problem. >> >> The root cause of this problem is because we just use one buffer to hold >> both key and value. What about using two buffers, split the key and valu= e >> pair into seperate buffers? >> >> >> On Fri, May 15, 2009 at 5:08 PM, wrote: >> >>> Author: sjanuary >>> Date: Fri May 15 09:08:28 2009 >>> New Revision: 775060 >>> >>> URL: http://svn.apache.org/viewvc?rev=3D775060&view=3Drev >>> Log: >>> Apply patch for HARMONY-6204 ([classlib][luni] >>> java.util.IdentityHashMap.(BigNumber) throws a >>> NegativeArraySizeException while RI throws OutOfMemoryError) >>> >>> Modified: >>> >>> =A0harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util= /IdentityHashMap.java >>> >>> =A0harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org= /apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java >>> >>> Modified: >>> harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/Id= entityHashMap.java >>> URL: >>> http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/lu= ni/src/main/java/java/util/IdentityHashMap.java?rev=3D775060&r1=3D775059&r2= =3D775060&view=3Ddiff >>> >>> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D >>> --- >>> harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/Id= entityHashMap.java >>> (original) >>> +++ >>> harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/Id= entityHashMap.java >>> Fri May 15 09:08:28 2009 >>> @@ -267,7 +267,10 @@ >>> =A0 =A0 } >>> >>> =A0 =A0 private int computeElementArraySize() { >>> - =A0 =A0 =A0 =A0return (int) (((long) threshold * 10000) / loadFactor)= * 2; >>> + =A0 =A0 =A0 =A0int arraySize =3D (int) (((long) threshold * 10000) / = loadFactor) * >>> 2; >>> + =A0 =A0 =A0 =A0// ensure arraySize is positive, the above cast from l= ong to int >>> type >>> + =A0 =A0 =A0 =A0// leads to overflow and negative arraySize if thresho= ld is too >>> big >>> + =A0 =A0 =A0 =A0return arraySize < 0 ? -arraySize : arraySize; >>> =A0 =A0 } >>> >>> =A0 =A0 /** >>> >>> Modified: >>> harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/ap= ache/harmony/luni/tests/java/util/IdentityHashMap2Test.java >>> URL: >>> http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/lu= ni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHash= Map2Test.java?rev=3D775060&r1=3D775059&r2=3D775060&view=3Ddiff >>> >>> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D >>> --- >>> harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/ap= ache/harmony/luni/tests/java/util/IdentityHashMap2Test.java >>> (original) >>> +++ >>> harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/ap= ache/harmony/luni/tests/java/util/IdentityHashMap2Test.java >>> Fri May 15 09:08:28 2009 >>> @@ -115,6 +115,15 @@ >>> =A0 =A0 =A0 =A0 assertEquals("Size should be 0", 0, hm2.size()); >>> =A0 =A0 =A0 =A0} >>> >>> + =A0 =A0public void test_IdentityHashMap_Constructor_BigSize() { >>> + =A0 =A0 =A0 =A0try { >>> + =A0 =A0 =A0 =A0 =A0 =A0new IdentityHashMap(Integer.MAX_VALUE); >>> + =A0 =A0 =A0 =A0 =A0 =A0fail("should throw OutOfMemoryError"); >>> + =A0 =A0 =A0 =A0} catch (OutOfMemoryError e) { >>> + =A0 =A0 =A0 =A0 =A0 =A0// Expected >>> + =A0 =A0 =A0 =A0} >>> + =A0 =A0} >>> + >>> =A0 =A0 =A0 =A0/** >>> =A0 =A0 =A0 =A0 * @tests java.util.IdentityHashMap#clear() >>> =A0 =A0 =A0 =A0 */ >>> >>> >>> >> >> >> -- >> Yours sincerely, >> Charles Lee >> >> > > > -- > Yours sincerely, > Charles Lee > --=20 Unless stated otherwise above: IBM United Kingdom Limited - Registered in England and Wales with number 74= 1598. Registered office: PO Box 41, North Harbour, Portsmouth, Hampshire PO6 3AU