src/share/classes/java/util/IdentityHashMap.java

*** 1,7 ****
  /*
!  * Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved.
   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   *
   * This code is free software; you can redistribute it and/or modify it
   * under the terms of the GNU General Public License version 2 only, as
   * published by the Free Software Foundation.  Oracle designates this
--- 1,7 ----
  /*
!  * Copyright (c) 2000, 2014, Oracle and/or its affiliates. All rights reserved.
   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   *
   * This code is free software; you can redistribute it and/or modify it
   * under the terms of the GNU General Public License version 2 only, as
   * published by the Free Software Foundation.  Oracle designates this
*** 158,167 ****
--- 158,171 ----
  
      /**
       * The maximum capacity, used if a higher value is implicitly specified
       * by either of the constructors with arguments.
       * MUST be a power of two <= 1<<29.
+      *
+      * In fact, the map can hold no more than MAXIMUM_CAPACITY-1 items
+      * because it has to have at least one slot with the key == null
+      * in order to avoid infinite loops in get(), put(), remove()
       */
      private static final int MAXIMUM_CAPACITY = 1 << 29;
  
      /**
       * The table, resized as necessary. Length MUST always be a power of two.
*** 234,257 ****
       * and MAXIMUM_CAPACITY, inclusive, that is greater than
       * (3 * expectedMaxSize)/2, if such a number exists.  Otherwise
       * returns MAXIMUM_CAPACITY.  If (3 * expectedMaxSize)/2 is negative, it
       * is assumed that overflow has occurred, and MAXIMUM_CAPACITY is returned.
       */
!     private int capacity(int expectedMaxSize) {
!         // Compute min capacity for expectedMaxSize given a load factor of 2/3
!         int minCapacity = (3 * expectedMaxSize)/2;
! 
!         // Compute the appropriate capacity
!         int result;
!         if (minCapacity > MAXIMUM_CAPACITY || minCapacity < 0) {
!             result = MAXIMUM_CAPACITY;
!         } else {
!             result = MINIMUM_CAPACITY;
!             while (result < minCapacity)
!                 result <<= 1;
!         }
!         return result;
      }
  
      /**
       * Initializes object to be an empty map with the specified initial
       * capacity, which is assumed to be a power of two between
--- 238,253 ----
       * and MAXIMUM_CAPACITY, inclusive, that is greater than
       * (3 * expectedMaxSize)/2, if such a number exists.  Otherwise
       * returns MAXIMUM_CAPACITY.  If (3 * expectedMaxSize)/2 is negative, it
       * is assumed that overflow has occurred, and MAXIMUM_CAPACITY is returned.
       */
!     private static int capacity(int expectedMaxSize) {
!         // Doubled minimum capacity given a load factor 2/3
!         int minCapacityX2 = 3 * expectedMaxSize;
!         return (minCapacityX2 >= 2 * MAXIMUM_CAPACITY || minCapacityX2 < 0)
!                 ? MAXIMUM_CAPACITY : (minCapacityX2 <= 2 * MINIMUM_CAPACITY)
!                 ? MINIMUM_CAPACITY : Integer.highestOneBit(minCapacityX2);
      }
  
      /**
       * Initializes object to be an empty map with the specified initial
       * capacity, which is assumed to be a power of two between
*** 443,457 ****
                  return oldValue;
              }
              i = nextKeyIndex(i, len);
          }
  
          modCount++;
          tab[i] = k;
          tab[i + 1] = value;
!         if (++size >= threshold)
!             resize(len); // len == 2 * current capacity.
          return null;
      }
  
      /**
       * Resize the table to hold given capacity.
--- 439,463 ----
                  return oldValue;
              }
              i = nextKeyIndex(i, len);
          }
  
+         if (size >= threshold) {
+             if (size >= MAXIMUM_CAPACITY - 1) {
+                 throw new IllegalStateException("Capacity exhausted.");
+             }
+             modCount++;
+             resize(len); // len == 2 * current capacity.
+             i = hash(k, len);
+             while ((item = tab[i]) != null) {
+                 i = nextKeyIndex(i, len);
+             }
+         }
          modCount++;
          tab[i] = k;
          tab[i + 1] = value;
!         size++;
          return null;
      }
  
      /**
       * Resize the table to hold given capacity.
*** 463,474 ****
          int newLength = newCapacity * 2;
  
          Object[] oldTable = table;
          int oldLength = oldTable.length;
          if (oldLength == 2*MAXIMUM_CAPACITY) { // can't expand any further
-             if (threshold == MAXIMUM_CAPACITY-1)
-                 throw new IllegalStateException("Capacity exhausted.");
              threshold = MAXIMUM_CAPACITY-1;  // Gigantic map!
              return;
          }
          if (oldLength >= newLength)
              return;
--- 469,478 ----
*** 540,550 ****
              }
              if (item == null)
                  return null;
              i = nextKeyIndex(i, len);
          }
- 
      }
  
      /**
       * Removes the specified key-value mapping from the map if it is present.
       *
--- 544,553 ----