RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

[Peter Levart]

On 07/08/2014 02:20 PM, Peter Levart wrote:
> That's right. Not in put(). But in putAll() it can overflow, since the 
> argument Map can be of any size that fits in int... So here's my 3rd 
> variation of Martin's latest version:
>
> http://cr.openjdk.java.net/~plevart/jdk9-dev/IdentityHashMap/webrev.03/
>
Another bug in my part 8-( I should've used the null-masked 'k' instead 
of 'key' in the index re-compute block:

http://cr.openjdk.java.net/~plevart/jdk9-dev/IdentityHashMap/webrev.04/

And diff to Martin's patch:

*** src/share/classes/java/util/IdentityHashMap.java.mb 2014-07-08 
12:37:57.267916926 +0200
--- src/share/classes/java/util/IdentityHashMap.java    2014-07-08 
14:23:25.141249319 +0200
***************
*** 437,449 ****

           if (size == MAXIMUM_CAPACITY - 1)
               throw new IllegalStateException("Capacity exhausted.");
           modCount++;
           tab[i] = k;
           tab[i + 1] = value;
           size++;
-         int x = size + (size << 1); // Optimized form of 3 * size
-         if (x > len)
-             resize(len); // len == 2 * current capacity.
           return null;
       }

--- 437,455 ----

           if (size == MAXIMUM_CAPACITY - 1)
               throw new IllegalStateException("Capacity exhausted.");
+
+         int x = size + (size << 1) + 3; // Optimized form of 3 * (size 
+ 1)
+         if (x > len && resize(len)) { // len == 2 * current capacity.
+             tab = table;
+             len = tab.length;
+             i = hash(k, len);
+             while (tab[i] != null)
+                 i = nextKeyIndex(i, len);
+         }
           modCount++;
           tab[i] = k;
           tab[i + 1] = value;
           size++;
           return null;
       }

***************
*** 452,468 ****
        *
        * @param newCapacity the new capacity, must be a power of two.
        */
!     private void resize(int newCapacity) {
           // assert (newCapacity & -newCapacity) == newCapacity; // 
power of 2
-         int newLength = newCapacity * 2;

           Object[] oldTable = table;
           int oldLength = oldTable.length;
           if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any 
further
!             return;
           }
           if (oldLength >= newLength)
!             return;

           Object[] newTable = new Object[newLength];

--- 458,474 ----
        *
        * @param newCapacity the new capacity, must be a power of two.
        */
!     private boolean resize(int newCapacity) {
           // assert (newCapacity & -newCapacity) == newCapacity; // 
power of 2

           Object[] oldTable = table;
           int oldLength = oldTable.length;
           if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any 
further
!             return false;
           }
+         int newLength = newCapacity * 2;
           if (oldLength >= newLength)
!             return false;

           Object[] newTable = new Object[newLength];

***************
*** 480,485 ****
--- 486,492 ----
               }
           }
           table = newTable;
+         return true;
       }

       /**
***************
*** 494,500 ****
           int n = m.size();
           if (n == 0)
               return;
!         if (n + (n << 1) > table.length) // conservatively pre-expand
               resize(capacity(n));

           for (Entry<? extends K, ? extends V> e : m.entrySet())
--- 501,507 ----
           int n = m.size();
           if (n == 0)
               return;
!         if (n > table.length / 3) // conservatively pre-expand
               resize(capacity(n));

           for (Entry<? extends K, ? extends V> e : m.entrySet())


Regards, Peter