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
