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

Print this page
rev 7313 : 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap
Reviewed-by: forax, duigou
Contributed-by: Mike Duigou <mike.duigou@oracle.com>, Remi Forax <forax@univ-mlv.fr>


  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package java.util;
  27 
  28 import java.io.*;
  29 import java.lang.reflect.Array;


  30 import java.util.function.Consumer;
  31 
  32 /**
  33  * This class implements the <tt>Map</tt> interface with a hash table, using
  34  * reference-equality in place of object-equality when comparing keys (and
  35  * values).  In other words, in an <tt>IdentityHashMap</tt>, two keys
  36  * <tt>k1</tt> and <tt>k2</tt> are considered equal if and only if
  37  * <tt>(k1==k2)</tt>.  (In normal <tt>Map</tt> implementations (like
  38  * <tt>HashMap</tt>) two keys <tt>k1</tt> and <tt>k2</tt> are considered equal
  39  * if and only if <tt>(k1==null ? k2==null : k1.equals(k2))</tt>.)
  40  *
  41  * <p><b>This class is <i>not</i> a general-purpose <tt>Map</tt>
  42  * implementation!  While this class implements the <tt>Map</tt> interface, it
  43  * intentionally violates <tt>Map's</tt> general contract, which mandates the
  44  * use of the <tt>equals</tt> method when comparing objects.  This class is
  45  * designed for use only in the rare cases wherein reference-equality
  46  * semantics are required.</b>
  47  *
  48  * <p>A typical use of this class is <i>topology-preserving object graph
  49  * transformations</i>, such as serialization or deep-copying.  To perform such


1318     /**
1319      * The put method for readObject.  It does not resize the table,
1320      * update modCount, etc.
1321      */
1322     private void putForCreate(K key, V value)
1323         throws IOException
1324     {
1325         Object k = maskNull(key);
1326         Object[] tab = table;
1327         int len = tab.length;
1328         int i = hash(k, len);
1329 
1330         Object item;
1331         while ( (item = tab[i]) != null) {
1332             if (item == k)
1333                 throw new java.io.StreamCorruptedException();
1334             i = nextKeyIndex(i, len);
1335         }
1336         tab[i] = k;
1337         tab[i + 1] = value;
































1338     }
1339 
1340     /**
1341      * Similar form as array-based Spliterators, but skips blank elements,
1342      * and guestimates size as decreasing by half per split.
1343      */
1344     static class IdentityHashMapSpliterator<K,V> {
1345         final IdentityHashMap<K,V> map;
1346         int index;             // current index, modified on advance/split
1347         int fence;             // -1 until first use; then one past last index
1348         int est;               // size estimate
1349         int expectedModCount;  // initialized when fence set
1350 
1351         IdentityHashMapSpliterator(IdentityHashMap<K,V> map, int origin,
1352                                    int fence, int est, int expectedModCount) {
1353             this.map = map;
1354             this.index = origin;
1355             this.fence = fence;
1356             this.est = est;
1357             this.expectedModCount = expectedModCount;




  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package java.util;
  27 
  28 import java.io.*;
  29 import java.lang.reflect.Array;
  30 import java.util.function.BiConsumer;
  31 import java.util.function.BiFunction;
  32 import java.util.function.Consumer;
  33 
  34 /**
  35  * This class implements the <tt>Map</tt> interface with a hash table, using
  36  * reference-equality in place of object-equality when comparing keys (and
  37  * values).  In other words, in an <tt>IdentityHashMap</tt>, two keys
  38  * <tt>k1</tt> and <tt>k2</tt> are considered equal if and only if
  39  * <tt>(k1==k2)</tt>.  (In normal <tt>Map</tt> implementations (like
  40  * <tt>HashMap</tt>) two keys <tt>k1</tt> and <tt>k2</tt> are considered equal
  41  * if and only if <tt>(k1==null ? k2==null : k1.equals(k2))</tt>.)
  42  *
  43  * <p><b>This class is <i>not</i> a general-purpose <tt>Map</tt>
  44  * implementation!  While this class implements the <tt>Map</tt> interface, it
  45  * intentionally violates <tt>Map's</tt> general contract, which mandates the
  46  * use of the <tt>equals</tt> method when comparing objects.  This class is
  47  * designed for use only in the rare cases wherein reference-equality
  48  * semantics are required.</b>
  49  *
  50  * <p>A typical use of this class is <i>topology-preserving object graph
  51  * transformations</i>, such as serialization or deep-copying.  To perform such


1320     /**
1321      * The put method for readObject.  It does not resize the table,
1322      * update modCount, etc.
1323      */
1324     private void putForCreate(K key, V value)
1325         throws IOException
1326     {
1327         Object k = maskNull(key);
1328         Object[] tab = table;
1329         int len = tab.length;
1330         int i = hash(k, len);
1331 
1332         Object item;
1333         while ( (item = tab[i]) != null) {
1334             if (item == k)
1335                 throw new java.io.StreamCorruptedException();
1336             i = nextKeyIndex(i, len);
1337         }
1338         tab[i] = k;
1339         tab[i + 1] = value;
1340     }
1341 
1342     @Override
1343     public void forEach(BiConsumer<? super K, ? super V> action) {
1344         Objects.requireNonNull(action);
1345         int expectedModCount = modCount;
1346 
1347         Object[] t = table;
1348         for (int index = 0; index < t.length; index += 2) {
1349             if (t[index] != null) {
1350                 action.accept((K) unmaskNull(t[index]), (V) t[index + 1]);
1351             }
1352 
1353             if (modCount != expectedModCount)
1354                 throw new ConcurrentModificationException();
1355         }
1356     }
1357 
1358     @Override
1359     public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1360         Objects.requireNonNull(function);
1361         int expectedModCount = modCount;
1362 
1363         Object[] t = table;
1364         for (int index = 0; index < t.length; index += 2) {
1365             if (t[index] != null) {
1366                 t[index + 1] = function.apply((K) unmaskNull(t[index]), (V) t[index + 1]);
1367             }
1368             
1369             if (modCount != expectedModCount)
1370                 throw new ConcurrentModificationException();
1371         }
1372     }
1373 
1374     /**
1375      * Similar form as array-based Spliterators, but skips blank elements,
1376      * and guestimates size as decreasing by half per split.
1377      */
1378     static class IdentityHashMapSpliterator<K,V> {
1379         final IdentityHashMap<K,V> map;
1380         int index;             // current index, modified on advance/split
1381         int fence;             // -1 until first use; then one past last index
1382         int est;               // size estimate
1383         int expectedModCount;  // initialized when fence set
1384 
1385         IdentityHashMapSpliterator(IdentityHashMap<K,V> map, int origin,
1386                                    int fence, int est, int expectedModCount) {
1387             this.map = map;
1388             this.index = origin;
1389             this.fence = fence;
1390             this.est = est;
1391             this.expectedModCount = expectedModCount;