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 <[email protected]>: > 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 <[email protected]> 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, <[email protected]> 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
