harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Sian January <sianjanu...@googlemail.com>
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
Date Fri, 15 May 2009 15:56:41 GMT
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 <littlee1032@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 <littlee1032@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, <sjanuary@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

Mime
View raw message