harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Charles Lee <littlee1...@gmail.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 12:40:21 GMT
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

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message