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

Peter Levart peter.levart at gmail.com
Tue Jul 8 12:30:51 UTC 2014

• Previous message: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size
• Next message: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

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 

•     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

• Previous message: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size
• Next message: RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

More information about the core-libs-dev mailing list