You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@harmony.apache.org by Charles Lee <li...@gmail.com> on 2009/05/15 14:36:43 UTC
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
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? And
the size is also not right if we just negate the overflow one, it will cause
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 value
pair into seperate buffers?
On Fri, May 15, 2009 at 5:08 PM, <sj...@apache.org> wrote:
> Author: sjanuary
> Date: Fri May 15 09:08:28 2009
> New Revision: 775060
>
> URL: http://svn.apache.org/viewvc?rev=775060&view=rev
> Log:
> Apply patch for HARMONY-6204 ([classlib][luni]
> java.util.IdentityHashMap.<init>(BigNumber) throws a
> NegativeArraySizeException while RI throws OutOfMemoryError)
>
> Modified:
>
> harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java
>
> harmony/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/IdentityHashMap.java
> URL:
> http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java?rev=775060&r1=775059&r2=775060&view=diff
>
> ==============================================================================
> ---
> harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java
> (original)
> +++
> harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java
> Fri May 15 09:08:28 2009
> @@ -267,7 +267,10 @@
> }
>
> private int computeElementArraySize() {
> - return (int) (((long) threshold * 10000) / loadFactor) * 2;
> + int arraySize = (int) (((long) threshold * 10000) / loadFactor) *
> 2;
> + // ensure arraySize is positive, the above cast from long to int
> type
> + // leads to overflow and negative arraySize if threshold is too
> big
> + return arraySize < 0 ? -arraySize : arraySize;
> }
>
> /**
>
> Modified:
> harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java
> URL:
> http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java?rev=775060&r1=775059&r2=775060&view=diff
>
> ==============================================================================
> ---
> harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java
> (original)
> +++
> harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java
> Fri May 15 09:08:28 2009
> @@ -115,6 +115,15 @@
> assertEquals("Size should be 0", 0, hm2.size());
> }
>
> + public void test_IdentityHashMap_Constructor_BigSize() {
> + try {
> + new IdentityHashMap(Integer.MAX_VALUE);
> + fail("should throw OutOfMemoryError");
> + } catch (OutOfMemoryError e) {
> + // Expected
> + }
> + }
> +
> /**
> * @tests java.util.IdentityHashMap#clear()
> */
>
>
>
--
Yours sincerely,
Charles Lee
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
Posted by Charles Lee <li...@gmail.com>.
Agree. I also wonder why we just use one buffer.
On linux 32, with -Xmx1024m, I have tried to new a identity hash map about
the size Integer.MAX_VALUE / 95 by sun 1.6. Bigger size will cause
OutofMemory Exception. I believe with a power machine and 64bit system, we
can create a identity hash map with much bigger size.
According to the original patch, size bitween 805306367 to Integer.MAX_VALUE
will cause overflow, and what we returned is not the right size. Only
raising the OutofMemoryException will make our code right.
On Fri, May 15, 2009 at 11:56 PM, Sian January
<si...@googlemail.com>wrote:
> 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 <li...@gmail.com>:
> > 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<K, V> extends
> > AbstractMap<K, V> implements
> > private static final long serialVersionUID = 8188218128353913216L;
> >
> > /*
> > - * The internal data structure to hold key value pairs This array
> holds
> > keys
> > - * and values in an alternating fashion.
> > + * The internal data structure to hold key. This array holds keys
> > + * in an alternating fashion.
> > */
> > - transient Object[] elementData;
> > + transient Object[] keyData;
> > +
> > + /*
> > + * The internal data structure to hold value. This array holds
> values
> > + * in an alternating fashion.
> > + */
> > + transient Object[] valueData;
> >
> > /* Actual number of key-value pairs. */
> > int size;
> > @@ -65,7 +71,10 @@ public class IdentityHashMap<K, V> extends
> AbstractMap<K,
> > V> implements
> > private static final int DEFAULT_MAX_SIZE = 21;
> >
> > /* Default load factor of 0.75; */
> > - private static final int loadFactor = 7500;
> > + private static final int loadFactorNumerator = 3;
> > + private static final int loadFactorDenominator = 4;
> > + /* 1610612735 */
> > + private static final int barrier = (int)((long)Integer.MAX_VALUE *
> > loadFactorNumerator / loadFactorDenominator);
> >
> > /*
> > * modification count, to keep track of structural modifications
> > between the
> > @@ -136,10 +145,10 @@ public class IdentityHashMap<K, V> extends
> > AbstractMap<K, V> implements
> > }
> >
> > public boolean hasNext() {
> > - while (position < associatedMap.elementData.length) {
> > + while (position < associatedMap.keyData.length) {
> > // if this is an empty spot, go to the next one
> > - if (associatedMap.elementData[position] == null) {
> > - position += 2;
> > + if (associatedMap.keyData[position] == null) {
> > + position++;
> > } else {
> > return true;
> > }
> > @@ -162,7 +171,7 @@ public class IdentityHashMap<K, V> extends
> > AbstractMap<K, V> implements
> > IdentityHashMapEntry<KT, VT> result = associatedMap
> > .getEntry(position);
> > lastPosition = position;
> > - position += 2;
> > + position++;
> >
> > canRemove = true;
> > return type.get(result);
> > @@ -175,7 +184,7 @@ public class IdentityHashMap<K, V> extends
> > AbstractMap<K, V> implements
> > }
> >
> > canRemove = false;
> > -
> associatedMap.remove(associatedMap.elementData[lastPosition]);
> > + associatedMap.remove(associatedMap.keyData[lastPosition]);
> > position = lastPosition;
> > expectedModCount++;
> > }
> > @@ -252,7 +261,9 @@ public class IdentityHashMap<K, V> extends
> > AbstractMap<K, V> implements
> > if (maxSize >= 0) {
> > this.size = 0;
> > threshold = getThreshold(maxSize);
> > - elementData = newElementArray(computeElementArraySize());
> > + int length = computeElementArraySize();
> > + keyData = new Object[length];
> > + valueData = new Object[length];
> > } else {
> > throw new IllegalArgumentException();
> > }
> > @@ -265,18 +276,12 @@ public class IdentityHashMap<K, V> extends
> > AbstractMap<K, V> implements
> > }
> >
> > private int computeElementArraySize() {
> > - return (int) (((long) threshold * 10000) / loadFactor) * 2;
> > - }
> > -
> > - /**
> > - * Create a new element array
> > - *
> > - * @param s
> > - * the number of elements
> > - * @return Reference to the element array
> > - */
> > - private Object[] newElementArray(int s) {
> > - return new Object[s];
> > + if (threshold >= barrier) {
> > + // Could not apply for the factor, we return the max value
> > + return Integer.MAX_VALUE;
> > + } else {
> > + return (int) (((long) threshold * loadFactorDenominator) /
> > loadFactorNumerator);
> > + }
> > }
> >
> > /**
> > @@ -307,8 +312,9 @@ public class IdentityHashMap<K, V> extends
> > AbstractMap<K, V> implements
> > @Override
> > public void clear() {
> > size = 0;
> > - for (int i = 0; i < elementData.length; i++) {
> > - elementData[i] = null;
> > + for (int i = 0; i < keyData.length; i++) {
> > + keyData[i] = null;
> > + valueData[i] = null;
> > }
> > modCount++;
> > }
> > @@ -326,8 +332,8 @@ public class IdentityHashMap<K, V> extends
> > AbstractMap<K, V> implements
> > key = NULL_OBJECT;
> > }
> >
> > - int index = findIndex(key, elementData);
> > - return elementData[index] == key;
> > + int index = findIndex(key, keyData);
> > + return keyData[index] == key;
> > }
> >
> > /**
> > @@ -345,8 +351,8 @@ public class IdentityHashMap<K, V> extends
> > AbstractMap<K, V> implements
> > value = NULL_OBJECT;
> > }
> >
> > - for (int i = 1; i < elementData.length; i = i + 2) {
> > - if (elementData[i] == value) {
> > + for (int i = 1; i < valueData.length; i++) {
> > + if (valueData[i] == value) {
> > return true;
> > }
> > }
> > @@ -366,10 +372,10 @@ public class IdentityHashMap<K, V> extends
> > AbstractMap<K, V> implements
> > key = NULL_OBJECT;
> > }
> >
> > - int index = findIndex(key, elementData);
> > + int index = findIndex(key, keyData);
> >
> > - if (elementData[index] == key) {
> > - Object result = elementData[index + 1];
> > + if (keyData[index] == key) {
> > + Object result = valueData[index];
> > return massageValue(result);
> > }
> >
> > @@ -381,8 +387,8 @@ public class IdentityHashMap<K, V> extends
> > AbstractMap<K, V> implements
> > key = NULL_OBJECT;
> > }
> >
> > - int index = findIndex(key, elementData);
> > - if (elementData[index] == key) {
> > + int index = findIndex(key, keyData);
> > + if (keyData[index] == key) {
> > return getEntry(index);
> > }
> >
> > @@ -395,8 +401,8 @@ public class IdentityHashMap<K, V> extends
> > AbstractMap<K, V> implements
> > */
> > @SuppressWarnings("unchecked")
> > private IdentityHashMapEntry<K, V> getEntry(int index) {
> > - Object key = elementData[index];
> > - Object value = elementData[index + 1];
> > + Object key = keyData[index];
> > + Object value = valueData[index];
> >
> > if (key == NULL_OBJECT) {
> > key = null;
> > @@ -424,7 +430,7 @@ public class IdentityHashMap<K, V> extends
> > AbstractMap<K, V> implements
> > */
> > break;
> > }
> > - index = (index + 2) % length;
> > + index = (index + 1) % length;
> > }
> > return index;
> > }
> > @@ -455,24 +461,24 @@ public class IdentityHashMap<K, V> extends
> > AbstractMap<K, V> implements
> > _value = NULL_OBJECT;
> > }
> >
> > - int index = findIndex(_key, elementData);
> > + int index = findIndex(_key, keyData);
> >
> > // if the key doesn't exist in the table
> > - if (elementData[index] != _key) {
> > + if (keyData[index] != _key) {
> > modCount++;
> > if (++size > threshold) {
> > rehash();
> > - index = findIndex(_key, elementData);
> > + index = findIndex(_key, keyData);
> > }
> >
> > // insert the key and assign the value to null initially
> > - elementData[index] = _key;
> > - elementData[index + 1] = null;
> > + keyData[index] = _key;
> > + valueData[index] = null;
> > }
> >
> > // insert value to where it needs to go, return the old value
> > - Object result = elementData[index + 1];
> > - elementData[index + 1] = _value;
> > + Object result = valueData[index];
> > + valueData[index] = _value;
> >
> > return massageValue(result);
> > }
> > @@ -493,26 +499,29 @@ public class IdentityHashMap<K, V> extends
> > AbstractMap<K, V> implements
> > }
> >
> > private void rehash() {
> > - int newlength = elementData.length << 1;
> > + int newlength = keyData.length << 1;
> > if (newlength == 0) {
> > newlength = 1;
> > }
> > - Object[] newData = newElementArray(newlength);
> > - for (int i = 0; i < elementData.length; i = i + 2) {
> > - Object key = elementData[i];
> > + Object[] newKeyData = new Object[newlength];
> > + Object[] newValueData = new Object[newlength];
> > + for (int i = 0; i < keyData.length; i++) {
> > + Object key = keyData[i];
> > if (key != null) {
> > // if not empty
> > - int index = findIndex(key, newData);
> > - newData[index] = key;
> > - newData[index + 1] = elementData[i + 1];
> > + int index = findIndex(key, newKeyData);
> > + newKeyData[index] = key;
> > + newValueData[index] = valueData[i];
> > }
> > }
> > - elementData = newData;
> > + keyData = newKeyData;
> > + valueData = newValueData;
> > computeMaxSize();
> > }
> >
> > private void computeMaxSize() {
> > - threshold = (int) ((long) (elementData.length / 2) * loadFactor
> /
> > 10000);
> > + // very weird
> > + threshold = (int) ((long) keyData.length * loadFactorNumerator /
> > loadFactorDenominator);
> > }
> >
> > /**
> > @@ -532,21 +541,22 @@ public class IdentityHashMap<K, V> extends
> > AbstractMap<K, V> implements
> > boolean hashedOk;
> > int index, next, hash;
> > Object result, object;
> > - index = next = findIndex(key, elementData);
> > + index = next = findIndex(key, keyData);
> >
> > - if (elementData[index] != key) {
> > + if (keyData[index] != key) {
> > return null;
> > }
> >
> > // store the value for this key
> > - result = elementData[index + 1];
> > + result = valueData[index];
> >
> > // shift the following elements up if needed
> > // until we reach an empty spot
> > - int length = elementData.length;
> > + int length = keyData.length;
> > + boolean forward = false;
> > while (true) {
> > - next = (next + 2) % length;
> > - object = elementData[next];
> > + next = (next + 1) % length;
> > + object = keyData[next];
> > if (object == null) {
> > break;
> > }
> > @@ -559,19 +569,24 @@ public class IdentityHashMap<K, V> extends
> > AbstractMap<K, V> implements
> > hashedOk = hashedOk && (hash <= next);
> > }
> > if (!hashedOk) {
> > - elementData[index] = object;
> > - elementData[index + 1] = elementData[next + 1];
> > + keyData[index] = object;
> > + valueData[index] = valueData[next];
> > index = next;
> > + keyData[next] = null;
> > + valueData[next] = null;
> > + forward = true;
> > }
> > }
> > +
> > + if (!forward) {
> > + // no other has been forwarded, we should delete the key and
> > value
> > + keyData[index] = null;
> > + valueData[index] = null;
> > + }
> >
> > size--;
> > modCount++;
> >
> > - // clear both the key and the value
> > - elementData[index] = null;
> > - elementData[index + 1] = null;
> > -
> > return massageValue(result);
> > }
> >
> > @@ -783,7 +798,9 @@ public class IdentityHashMap<K, V> extends
> > AbstractMap<K, V> implements
> > stream.defaultReadObject();
> > int savedSize = stream.readInt();
> > threshold = getThreshold(DEFAULT_MAX_SIZE);
> > - elementData = newElementArray(computeElementArraySize());
> > + int length = computeElementArraySize();
> > + keyData = new Object[length];
> > + valueData = new Object[length];
> > for (int i = savedSize; --i >= 0;) {
> > K key = (K) stream.readObject();
> > put(key, (V) stream.readObject());
> >
> >
> >
> >
> > On Fri, May 15, 2009 at 8:36 PM, Charles Lee <li...@gmail.com>
> wrote:
> >
> >> 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?
> And
> >> the size is also not right if we just negate the overflow one, it will
> cause
> >> 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
> value
> >> pair into seperate buffers?
> >>
> >>
> >> On Fri, May 15, 2009 at 5:08 PM, <sj...@apache.org> wrote:
> >>
> >>> Author: sjanuary
> >>> Date: Fri May 15 09:08:28 2009
> >>> New Revision: 775060
> >>>
> >>> URL: http://svn.apache.org/viewvc?rev=775060&view=rev
> >>> Log:
> >>> Apply patch for HARMONY-6204 ([classlib][luni]
> >>> java.util.IdentityHashMap.<init>(BigNumber) throws a
> >>> NegativeArraySizeException while RI throws OutOfMemoryError)
> >>>
> >>> Modified:
> >>>
> >>>
> harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java
> >>>
> >>>
> harmony/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/IdentityHashMap.java
> >>> URL:
> >>>
> http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java?rev=775060&r1=775059&r2=775060&view=diff
> >>>
> >>>
> ==============================================================================
> >>> ---
> >>>
> harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java
> >>> (original)
> >>> +++
> >>>
> harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java
> >>> Fri May 15 09:08:28 2009
> >>> @@ -267,7 +267,10 @@
> >>> }
> >>>
> >>> private int computeElementArraySize() {
> >>> - return (int) (((long) threshold * 10000) / loadFactor) * 2;
> >>> + int arraySize = (int) (((long) threshold * 10000) /
> loadFactor) *
> >>> 2;
> >>> + // ensure arraySize is positive, the above cast from long to
> int
> >>> type
> >>> + // leads to overflow and negative arraySize if threshold is
> too
> >>> big
> >>> + return arraySize < 0 ? -arraySize : arraySize;
> >>> }
> >>>
> >>> /**
> >>>
> >>> Modified:
> >>>
> harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java
> >>> URL:
> >>>
> http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java?rev=775060&r1=775059&r2=775060&view=diff
> >>>
> >>>
> ==============================================================================
> >>> ---
> >>>
> harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java
> >>> (original)
> >>> +++
> >>>
> harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java
> >>> Fri May 15 09:08:28 2009
> >>> @@ -115,6 +115,15 @@
> >>> assertEquals("Size should be 0", 0, hm2.size());
> >>> }
> >>>
> >>> + public void test_IdentityHashMap_Constructor_BigSize() {
> >>> + try {
> >>> + new IdentityHashMap(Integer.MAX_VALUE);
> >>> + fail("should throw OutOfMemoryError");
> >>> + } catch (OutOfMemoryError e) {
> >>> + // Expected
> >>> + }
> >>> + }
> >>> +
> >>> /**
> >>> * @tests java.util.IdentityHashMap#clear()
> >>> */
> >>>
> >>>
> >>>
> >>
> >>
> >> --
> >> Yours sincerely,
> >> Charles Lee
> >>
> >>
> >
> >
> > --
> > Yours sincerely,
> > Charles Lee
> >
>
>
>
> --
> Unless stated otherwise above:
> IBM United Kingdom Limited - Registered in England and Wales with number
> 741598.
> Registered office: PO Box 41, North Harbour, Portsmouth, Hampshire PO6 3AU
>
--
Yours sincerely,
Charles Lee
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
Posted by Sian January <si...@googlemail.com>.
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 <li...@gmail.com>:
> 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<K, V> extends
> AbstractMap<K, V> implements
> private static final long serialVersionUID = 8188218128353913216L;
>
> /*
> - * The internal data structure to hold key value pairs This array holds
> keys
> - * and values in an alternating fashion.
> + * The internal data structure to hold key. This array holds keys
> + * in an alternating fashion.
> */
> - transient Object[] elementData;
> + transient Object[] keyData;
> +
> + /*
> + * The internal data structure to hold value. This array holds values
> + * in an alternating fashion.
> + */
> + transient Object[] valueData;
>
> /* Actual number of key-value pairs. */
> int size;
> @@ -65,7 +71,10 @@ public class IdentityHashMap<K, V> extends AbstractMap<K,
> V> implements
> private static final int DEFAULT_MAX_SIZE = 21;
>
> /* Default load factor of 0.75; */
> - private static final int loadFactor = 7500;
> + private static final int loadFactorNumerator = 3;
> + private static final int loadFactorDenominator = 4;
> + /* 1610612735 */
> + private static final int barrier = (int)((long)Integer.MAX_VALUE *
> loadFactorNumerator / loadFactorDenominator);
>
> /*
> * modification count, to keep track of structural modifications
> between the
> @@ -136,10 +145,10 @@ public class IdentityHashMap<K, V> extends
> AbstractMap<K, V> implements
> }
>
> public boolean hasNext() {
> - while (position < associatedMap.elementData.length) {
> + while (position < associatedMap.keyData.length) {
> // if this is an empty spot, go to the next one
> - if (associatedMap.elementData[position] == null) {
> - position += 2;
> + if (associatedMap.keyData[position] == null) {
> + position++;
> } else {
> return true;
> }
> @@ -162,7 +171,7 @@ public class IdentityHashMap<K, V> extends
> AbstractMap<K, V> implements
> IdentityHashMapEntry<KT, VT> result = associatedMap
> .getEntry(position);
> lastPosition = position;
> - position += 2;
> + position++;
>
> canRemove = true;
> return type.get(result);
> @@ -175,7 +184,7 @@ public class IdentityHashMap<K, V> extends
> AbstractMap<K, V> implements
> }
>
> canRemove = false;
> - associatedMap.remove(associatedMap.elementData[lastPosition]);
> + associatedMap.remove(associatedMap.keyData[lastPosition]);
> position = lastPosition;
> expectedModCount++;
> }
> @@ -252,7 +261,9 @@ public class IdentityHashMap<K, V> extends
> AbstractMap<K, V> implements
> if (maxSize >= 0) {
> this.size = 0;
> threshold = getThreshold(maxSize);
> - elementData = newElementArray(computeElementArraySize());
> + int length = computeElementArraySize();
> + keyData = new Object[length];
> + valueData = new Object[length];
> } else {
> throw new IllegalArgumentException();
> }
> @@ -265,18 +276,12 @@ public class IdentityHashMap<K, V> extends
> AbstractMap<K, V> implements
> }
>
> private int computeElementArraySize() {
> - return (int) (((long) threshold * 10000) / loadFactor) * 2;
> - }
> -
> - /**
> - * Create a new element array
> - *
> - * @param s
> - * the number of elements
> - * @return Reference to the element array
> - */
> - private Object[] newElementArray(int s) {
> - return new Object[s];
> + if (threshold >= barrier) {
> + // Could not apply for the factor, we return the max value
> + return Integer.MAX_VALUE;
> + } else {
> + return (int) (((long) threshold * loadFactorDenominator) /
> loadFactorNumerator);
> + }
> }
>
> /**
> @@ -307,8 +312,9 @@ public class IdentityHashMap<K, V> extends
> AbstractMap<K, V> implements
> @Override
> public void clear() {
> size = 0;
> - for (int i = 0; i < elementData.length; i++) {
> - elementData[i] = null;
> + for (int i = 0; i < keyData.length; i++) {
> + keyData[i] = null;
> + valueData[i] = null;
> }
> modCount++;
> }
> @@ -326,8 +332,8 @@ public class IdentityHashMap<K, V> extends
> AbstractMap<K, V> implements
> key = NULL_OBJECT;
> }
>
> - int index = findIndex(key, elementData);
> - return elementData[index] == key;
> + int index = findIndex(key, keyData);
> + return keyData[index] == key;
> }
>
> /**
> @@ -345,8 +351,8 @@ public class IdentityHashMap<K, V> extends
> AbstractMap<K, V> implements
> value = NULL_OBJECT;
> }
>
> - for (int i = 1; i < elementData.length; i = i + 2) {
> - if (elementData[i] == value) {
> + for (int i = 1; i < valueData.length; i++) {
> + if (valueData[i] == value) {
> return true;
> }
> }
> @@ -366,10 +372,10 @@ public class IdentityHashMap<K, V> extends
> AbstractMap<K, V> implements
> key = NULL_OBJECT;
> }
>
> - int index = findIndex(key, elementData);
> + int index = findIndex(key, keyData);
>
> - if (elementData[index] == key) {
> - Object result = elementData[index + 1];
> + if (keyData[index] == key) {
> + Object result = valueData[index];
> return massageValue(result);
> }
>
> @@ -381,8 +387,8 @@ public class IdentityHashMap<K, V> extends
> AbstractMap<K, V> implements
> key = NULL_OBJECT;
> }
>
> - int index = findIndex(key, elementData);
> - if (elementData[index] == key) {
> + int index = findIndex(key, keyData);
> + if (keyData[index] == key) {
> return getEntry(index);
> }
>
> @@ -395,8 +401,8 @@ public class IdentityHashMap<K, V> extends
> AbstractMap<K, V> implements
> */
> @SuppressWarnings("unchecked")
> private IdentityHashMapEntry<K, V> getEntry(int index) {
> - Object key = elementData[index];
> - Object value = elementData[index + 1];
> + Object key = keyData[index];
> + Object value = valueData[index];
>
> if (key == NULL_OBJECT) {
> key = null;
> @@ -424,7 +430,7 @@ public class IdentityHashMap<K, V> extends
> AbstractMap<K, V> implements
> */
> break;
> }
> - index = (index + 2) % length;
> + index = (index + 1) % length;
> }
> return index;
> }
> @@ -455,24 +461,24 @@ public class IdentityHashMap<K, V> extends
> AbstractMap<K, V> implements
> _value = NULL_OBJECT;
> }
>
> - int index = findIndex(_key, elementData);
> + int index = findIndex(_key, keyData);
>
> // if the key doesn't exist in the table
> - if (elementData[index] != _key) {
> + if (keyData[index] != _key) {
> modCount++;
> if (++size > threshold) {
> rehash();
> - index = findIndex(_key, elementData);
> + index = findIndex(_key, keyData);
> }
>
> // insert the key and assign the value to null initially
> - elementData[index] = _key;
> - elementData[index + 1] = null;
> + keyData[index] = _key;
> + valueData[index] = null;
> }
>
> // insert value to where it needs to go, return the old value
> - Object result = elementData[index + 1];
> - elementData[index + 1] = _value;
> + Object result = valueData[index];
> + valueData[index] = _value;
>
> return massageValue(result);
> }
> @@ -493,26 +499,29 @@ public class IdentityHashMap<K, V> extends
> AbstractMap<K, V> implements
> }
>
> private void rehash() {
> - int newlength = elementData.length << 1;
> + int newlength = keyData.length << 1;
> if (newlength == 0) {
> newlength = 1;
> }
> - Object[] newData = newElementArray(newlength);
> - for (int i = 0; i < elementData.length; i = i + 2) {
> - Object key = elementData[i];
> + Object[] newKeyData = new Object[newlength];
> + Object[] newValueData = new Object[newlength];
> + for (int i = 0; i < keyData.length; i++) {
> + Object key = keyData[i];
> if (key != null) {
> // if not empty
> - int index = findIndex(key, newData);
> - newData[index] = key;
> - newData[index + 1] = elementData[i + 1];
> + int index = findIndex(key, newKeyData);
> + newKeyData[index] = key;
> + newValueData[index] = valueData[i];
> }
> }
> - elementData = newData;
> + keyData = newKeyData;
> + valueData = newValueData;
> computeMaxSize();
> }
>
> private void computeMaxSize() {
> - threshold = (int) ((long) (elementData.length / 2) * loadFactor /
> 10000);
> + // very weird
> + threshold = (int) ((long) keyData.length * loadFactorNumerator /
> loadFactorDenominator);
> }
>
> /**
> @@ -532,21 +541,22 @@ public class IdentityHashMap<K, V> extends
> AbstractMap<K, V> implements
> boolean hashedOk;
> int index, next, hash;
> Object result, object;
> - index = next = findIndex(key, elementData);
> + index = next = findIndex(key, keyData);
>
> - if (elementData[index] != key) {
> + if (keyData[index] != key) {
> return null;
> }
>
> // store the value for this key
> - result = elementData[index + 1];
> + result = valueData[index];
>
> // shift the following elements up if needed
> // until we reach an empty spot
> - int length = elementData.length;
> + int length = keyData.length;
> + boolean forward = false;
> while (true) {
> - next = (next + 2) % length;
> - object = elementData[next];
> + next = (next + 1) % length;
> + object = keyData[next];
> if (object == null) {
> break;
> }
> @@ -559,19 +569,24 @@ public class IdentityHashMap<K, V> extends
> AbstractMap<K, V> implements
> hashedOk = hashedOk && (hash <= next);
> }
> if (!hashedOk) {
> - elementData[index] = object;
> - elementData[index + 1] = elementData[next + 1];
> + keyData[index] = object;
> + valueData[index] = valueData[next];
> index = next;
> + keyData[next] = null;
> + valueData[next] = null;
> + forward = true;
> }
> }
> +
> + if (!forward) {
> + // no other has been forwarded, we should delete the key and
> value
> + keyData[index] = null;
> + valueData[index] = null;
> + }
>
> size--;
> modCount++;
>
> - // clear both the key and the value
> - elementData[index] = null;
> - elementData[index + 1] = null;
> -
> return massageValue(result);
> }
>
> @@ -783,7 +798,9 @@ public class IdentityHashMap<K, V> extends
> AbstractMap<K, V> implements
> stream.defaultReadObject();
> int savedSize = stream.readInt();
> threshold = getThreshold(DEFAULT_MAX_SIZE);
> - elementData = newElementArray(computeElementArraySize());
> + int length = computeElementArraySize();
> + keyData = new Object[length];
> + valueData = new Object[length];
> for (int i = savedSize; --i >= 0;) {
> K key = (K) stream.readObject();
> put(key, (V) stream.readObject());
>
>
>
>
> On Fri, May 15, 2009 at 8:36 PM, Charles Lee <li...@gmail.com> wrote:
>
>> 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? And
>> the size is also not right if we just negate the overflow one, it will cause
>> 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 value
>> pair into seperate buffers?
>>
>>
>> On Fri, May 15, 2009 at 5:08 PM, <sj...@apache.org> wrote:
>>
>>> Author: sjanuary
>>> Date: Fri May 15 09:08:28 2009
>>> New Revision: 775060
>>>
>>> URL: http://svn.apache.org/viewvc?rev=775060&view=rev
>>> Log:
>>> Apply patch for HARMONY-6204 ([classlib][luni]
>>> java.util.IdentityHashMap.<init>(BigNumber) throws a
>>> NegativeArraySizeException while RI throws OutOfMemoryError)
>>>
>>> Modified:
>>>
>>> harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java
>>>
>>> harmony/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/IdentityHashMap.java
>>> URL:
>>> http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java?rev=775060&r1=775059&r2=775060&view=diff
>>>
>>> ==============================================================================
>>> ---
>>> harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java
>>> (original)
>>> +++
>>> harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java
>>> Fri May 15 09:08:28 2009
>>> @@ -267,7 +267,10 @@
>>> }
>>>
>>> private int computeElementArraySize() {
>>> - return (int) (((long) threshold * 10000) / loadFactor) * 2;
>>> + int arraySize = (int) (((long) threshold * 10000) / loadFactor) *
>>> 2;
>>> + // ensure arraySize is positive, the above cast from long to int
>>> type
>>> + // leads to overflow and negative arraySize if threshold is too
>>> big
>>> + return arraySize < 0 ? -arraySize : arraySize;
>>> }
>>>
>>> /**
>>>
>>> Modified:
>>> harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java
>>> URL:
>>> http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java?rev=775060&r1=775059&r2=775060&view=diff
>>>
>>> ==============================================================================
>>> ---
>>> harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java
>>> (original)
>>> +++
>>> harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java
>>> Fri May 15 09:08:28 2009
>>> @@ -115,6 +115,15 @@
>>> assertEquals("Size should be 0", 0, hm2.size());
>>> }
>>>
>>> + public void test_IdentityHashMap_Constructor_BigSize() {
>>> + try {
>>> + new IdentityHashMap(Integer.MAX_VALUE);
>>> + fail("should throw OutOfMemoryError");
>>> + } catch (OutOfMemoryError e) {
>>> + // Expected
>>> + }
>>> + }
>>> +
>>> /**
>>> * @tests java.util.IdentityHashMap#clear()
>>> */
>>>
>>>
>>>
>>
>>
>> --
>> Yours sincerely,
>> Charles Lee
>>
>>
>
>
> --
> Yours sincerely,
> Charles Lee
>
--
Unless stated otherwise above:
IBM United Kingdom Limited - Registered in England and Wales with number 741598.
Registered office: PO Box 41, North Harbour, Portsmouth, Hampshire PO6 3AU
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
Posted by Charles Lee <li...@gmail.com>.
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<K, V> extends
AbstractMap<K, V> implements
private static final long serialVersionUID = 8188218128353913216L;
/*
- * The internal data structure to hold key value pairs This array holds
keys
- * and values in an alternating fashion.
+ * The internal data structure to hold key. This array holds keys
+ * in an alternating fashion.
*/
- transient Object[] elementData;
+ transient Object[] keyData;
+
+ /*
+ * The internal data structure to hold value. This array holds values
+ * in an alternating fashion.
+ */
+ transient Object[] valueData;
/* Actual number of key-value pairs. */
int size;
@@ -65,7 +71,10 @@ public class IdentityHashMap<K, V> extends AbstractMap<K,
V> implements
private static final int DEFAULT_MAX_SIZE = 21;
/* Default load factor of 0.75; */
- private static final int loadFactor = 7500;
+ private static final int loadFactorNumerator = 3;
+ private static final int loadFactorDenominator = 4;
+ /* 1610612735 */
+ private static final int barrier = (int)((long)Integer.MAX_VALUE *
loadFactorNumerator / loadFactorDenominator);
/*
* modification count, to keep track of structural modifications
between the
@@ -136,10 +145,10 @@ public class IdentityHashMap<K, V> extends
AbstractMap<K, V> implements
}
public boolean hasNext() {
- while (position < associatedMap.elementData.length) {
+ while (position < associatedMap.keyData.length) {
// if this is an empty spot, go to the next one
- if (associatedMap.elementData[position] == null) {
- position += 2;
+ if (associatedMap.keyData[position] == null) {
+ position++;
} else {
return true;
}
@@ -162,7 +171,7 @@ public class IdentityHashMap<K, V> extends
AbstractMap<K, V> implements
IdentityHashMapEntry<KT, VT> result = associatedMap
.getEntry(position);
lastPosition = position;
- position += 2;
+ position++;
canRemove = true;
return type.get(result);
@@ -175,7 +184,7 @@ public class IdentityHashMap<K, V> extends
AbstractMap<K, V> implements
}
canRemove = false;
- associatedMap.remove(associatedMap.elementData[lastPosition]);
+ associatedMap.remove(associatedMap.keyData[lastPosition]);
position = lastPosition;
expectedModCount++;
}
@@ -252,7 +261,9 @@ public class IdentityHashMap<K, V> extends
AbstractMap<K, V> implements
if (maxSize >= 0) {
this.size = 0;
threshold = getThreshold(maxSize);
- elementData = newElementArray(computeElementArraySize());
+ int length = computeElementArraySize();
+ keyData = new Object[length];
+ valueData = new Object[length];
} else {
throw new IllegalArgumentException();
}
@@ -265,18 +276,12 @@ public class IdentityHashMap<K, V> extends
AbstractMap<K, V> implements
}
private int computeElementArraySize() {
- return (int) (((long) threshold * 10000) / loadFactor) * 2;
- }
-
- /**
- * Create a new element array
- *
- * @param s
- * the number of elements
- * @return Reference to the element array
- */
- private Object[] newElementArray(int s) {
- return new Object[s];
+ if (threshold >= barrier) {
+ // Could not apply for the factor, we return the max value
+ return Integer.MAX_VALUE;
+ } else {
+ return (int) (((long) threshold * loadFactorDenominator) /
loadFactorNumerator);
+ }
}
/**
@@ -307,8 +312,9 @@ public class IdentityHashMap<K, V> extends
AbstractMap<K, V> implements
@Override
public void clear() {
size = 0;
- for (int i = 0; i < elementData.length; i++) {
- elementData[i] = null;
+ for (int i = 0; i < keyData.length; i++) {
+ keyData[i] = null;
+ valueData[i] = null;
}
modCount++;
}
@@ -326,8 +332,8 @@ public class IdentityHashMap<K, V> extends
AbstractMap<K, V> implements
key = NULL_OBJECT;
}
- int index = findIndex(key, elementData);
- return elementData[index] == key;
+ int index = findIndex(key, keyData);
+ return keyData[index] == key;
}
/**
@@ -345,8 +351,8 @@ public class IdentityHashMap<K, V> extends
AbstractMap<K, V> implements
value = NULL_OBJECT;
}
- for (int i = 1; i < elementData.length; i = i + 2) {
- if (elementData[i] == value) {
+ for (int i = 1; i < valueData.length; i++) {
+ if (valueData[i] == value) {
return true;
}
}
@@ -366,10 +372,10 @@ public class IdentityHashMap<K, V> extends
AbstractMap<K, V> implements
key = NULL_OBJECT;
}
- int index = findIndex(key, elementData);
+ int index = findIndex(key, keyData);
- if (elementData[index] == key) {
- Object result = elementData[index + 1];
+ if (keyData[index] == key) {
+ Object result = valueData[index];
return massageValue(result);
}
@@ -381,8 +387,8 @@ public class IdentityHashMap<K, V> extends
AbstractMap<K, V> implements
key = NULL_OBJECT;
}
- int index = findIndex(key, elementData);
- if (elementData[index] == key) {
+ int index = findIndex(key, keyData);
+ if (keyData[index] == key) {
return getEntry(index);
}
@@ -395,8 +401,8 @@ public class IdentityHashMap<K, V> extends
AbstractMap<K, V> implements
*/
@SuppressWarnings("unchecked")
private IdentityHashMapEntry<K, V> getEntry(int index) {
- Object key = elementData[index];
- Object value = elementData[index + 1];
+ Object key = keyData[index];
+ Object value = valueData[index];
if (key == NULL_OBJECT) {
key = null;
@@ -424,7 +430,7 @@ public class IdentityHashMap<K, V> extends
AbstractMap<K, V> implements
*/
break;
}
- index = (index + 2) % length;
+ index = (index + 1) % length;
}
return index;
}
@@ -455,24 +461,24 @@ public class IdentityHashMap<K, V> extends
AbstractMap<K, V> implements
_value = NULL_OBJECT;
}
- int index = findIndex(_key, elementData);
+ int index = findIndex(_key, keyData);
// if the key doesn't exist in the table
- if (elementData[index] != _key) {
+ if (keyData[index] != _key) {
modCount++;
if (++size > threshold) {
rehash();
- index = findIndex(_key, elementData);
+ index = findIndex(_key, keyData);
}
// insert the key and assign the value to null initially
- elementData[index] = _key;
- elementData[index + 1] = null;
+ keyData[index] = _key;
+ valueData[index] = null;
}
// insert value to where it needs to go, return the old value
- Object result = elementData[index + 1];
- elementData[index + 1] = _value;
+ Object result = valueData[index];
+ valueData[index] = _value;
return massageValue(result);
}
@@ -493,26 +499,29 @@ public class IdentityHashMap<K, V> extends
AbstractMap<K, V> implements
}
private void rehash() {
- int newlength = elementData.length << 1;
+ int newlength = keyData.length << 1;
if (newlength == 0) {
newlength = 1;
}
- Object[] newData = newElementArray(newlength);
- for (int i = 0; i < elementData.length; i = i + 2) {
- Object key = elementData[i];
+ Object[] newKeyData = new Object[newlength];
+ Object[] newValueData = new Object[newlength];
+ for (int i = 0; i < keyData.length; i++) {
+ Object key = keyData[i];
if (key != null) {
// if not empty
- int index = findIndex(key, newData);
- newData[index] = key;
- newData[index + 1] = elementData[i + 1];
+ int index = findIndex(key, newKeyData);
+ newKeyData[index] = key;
+ newValueData[index] = valueData[i];
}
}
- elementData = newData;
+ keyData = newKeyData;
+ valueData = newValueData;
computeMaxSize();
}
private void computeMaxSize() {
- threshold = (int) ((long) (elementData.length / 2) * loadFactor /
10000);
+ // very weird
+ threshold = (int) ((long) keyData.length * loadFactorNumerator /
loadFactorDenominator);
}
/**
@@ -532,21 +541,22 @@ public class IdentityHashMap<K, V> extends
AbstractMap<K, V> implements
boolean hashedOk;
int index, next, hash;
Object result, object;
- index = next = findIndex(key, elementData);
+ index = next = findIndex(key, keyData);
- if (elementData[index] != key) {
+ if (keyData[index] != key) {
return null;
}
// store the value for this key
- result = elementData[index + 1];
+ result = valueData[index];
// shift the following elements up if needed
// until we reach an empty spot
- int length = elementData.length;
+ int length = keyData.length;
+ boolean forward = false;
while (true) {
- next = (next + 2) % length;
- object = elementData[next];
+ next = (next + 1) % length;
+ object = keyData[next];
if (object == null) {
break;
}
@@ -559,19 +569,24 @@ public class IdentityHashMap<K, V> extends
AbstractMap<K, V> implements
hashedOk = hashedOk && (hash <= next);
}
if (!hashedOk) {
- elementData[index] = object;
- elementData[index + 1] = elementData[next + 1];
+ keyData[index] = object;
+ valueData[index] = valueData[next];
index = next;
+ keyData[next] = null;
+ valueData[next] = null;
+ forward = true;
}
}
+
+ if (!forward) {
+ // no other has been forwarded, we should delete the key and
value
+ keyData[index] = null;
+ valueData[index] = null;
+ }
size--;
modCount++;
- // clear both the key and the value
- elementData[index] = null;
- elementData[index + 1] = null;
-
return massageValue(result);
}
@@ -783,7 +798,9 @@ public class IdentityHashMap<K, V> extends
AbstractMap<K, V> implements
stream.defaultReadObject();
int savedSize = stream.readInt();
threshold = getThreshold(DEFAULT_MAX_SIZE);
- elementData = newElementArray(computeElementArraySize());
+ int length = computeElementArraySize();
+ keyData = new Object[length];
+ valueData = new Object[length];
for (int i = savedSize; --i >= 0;) {
K key = (K) stream.readObject();
put(key, (V) stream.readObject());
On Fri, May 15, 2009 at 8:36 PM, Charles Lee <li...@gmail.com> wrote:
> 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? And
> the size is also not right if we just negate the overflow one, it will cause
> 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 value
> pair into seperate buffers?
>
>
> On Fri, May 15, 2009 at 5:08 PM, <sj...@apache.org> wrote:
>
>> Author: sjanuary
>> Date: Fri May 15 09:08:28 2009
>> New Revision: 775060
>>
>> URL: http://svn.apache.org/viewvc?rev=775060&view=rev
>> Log:
>> Apply patch for HARMONY-6204 ([classlib][luni]
>> java.util.IdentityHashMap.<init>(BigNumber) throws a
>> NegativeArraySizeException while RI throws OutOfMemoryError)
>>
>> Modified:
>>
>> harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java
>>
>> harmony/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/IdentityHashMap.java
>> URL:
>> http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java?rev=775060&r1=775059&r2=775060&view=diff
>>
>> ==============================================================================
>> ---
>> harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java
>> (original)
>> +++
>> harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/IdentityHashMap.java
>> Fri May 15 09:08:28 2009
>> @@ -267,7 +267,10 @@
>> }
>>
>> private int computeElementArraySize() {
>> - return (int) (((long) threshold * 10000) / loadFactor) * 2;
>> + int arraySize = (int) (((long) threshold * 10000) / loadFactor) *
>> 2;
>> + // ensure arraySize is positive, the above cast from long to int
>> type
>> + // leads to overflow and negative arraySize if threshold is too
>> big
>> + return arraySize < 0 ? -arraySize : arraySize;
>> }
>>
>> /**
>>
>> Modified:
>> harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java
>> URL:
>> http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java?rev=775060&r1=775059&r2=775060&view=diff
>>
>> ==============================================================================
>> ---
>> harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java
>> (original)
>> +++
>> harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/IdentityHashMap2Test.java
>> Fri May 15 09:08:28 2009
>> @@ -115,6 +115,15 @@
>> assertEquals("Size should be 0", 0, hm2.size());
>> }
>>
>> + public void test_IdentityHashMap_Constructor_BigSize() {
>> + try {
>> + new IdentityHashMap(Integer.MAX_VALUE);
>> + fail("should throw OutOfMemoryError");
>> + } catch (OutOfMemoryError e) {
>> + // Expected
>> + }
>> + }
>> +
>> /**
>> * @tests java.util.IdentityHashMap#clear()
>> */
>>
>>
>>
>
>
> --
> Yours sincerely,
> Charles Lee
>
>
--
Yours sincerely,
Charles Lee