1 /* 2 * Copyright (c) 2000, 2022, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 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.ObjectInputStream; 29 import java.io.ObjectOutputStream; 30 import java.lang.reflect.Array; 31 import java.util.function.BiConsumer; 32 import java.util.function.BiFunction; 33 import java.util.function.Consumer; 34 import jdk.internal.access.SharedSecrets; 35 36 /** 37 * This class implements the {@code Map} interface with a hash table, using 38 * reference-equality in place of object-equality when comparing keys (and 39 * values). In other words, in an {@code IdentityHashMap}, two keys 40 * {@code k1} and {@code k2} are considered equal if and only if 41 * {@code (k1==k2)}. (In normal {@code Map} implementations (like 42 * {@code HashMap}) two keys {@code k1} and {@code k2} are considered equal 43 * if and only if {@code (k1==null ? k2==null : k1.equals(k2))}.) 44 * 45 * <p><b>This class is <i>not</i> a general-purpose {@code Map} 46 * implementation! While this class implements the {@code Map} interface, it 47 * intentionally violates {@code Map's} general contract, which mandates the 48 * use of the {@code equals} method when comparing objects. This class is 49 * designed for use only in the rare cases wherein reference-equality 50 * semantics are required.</b> 51 * 52 * <p>The view collections of this map also have reference-equality semantics 53 * for their elements. See the {@link keySet() keySet}, {@link values() values}, 54 * and {@link entrySet() entrySet} methods for further information. 55 * 56 * <p>A typical use of this class is <i>topology-preserving object graph 57 * transformations</i>, such as serialization or deep-copying. To perform such 58 * a transformation, a program must maintain a "node table" that keeps track 59 * of all the object references that have already been processed. The node 60 * table must not equate distinct objects even if they happen to be equal. 61 * Another typical use of this class is to maintain <i>proxy objects</i>. For 62 * example, a debugging facility might wish to maintain a proxy object for 63 * each object in the program being debugged. 64 * 65 * <p>This class provides all of the optional map operations, and permits 66 * {@code null} values and the {@code null} key. This class makes no 67 * guarantees as to the order of the map; in particular, it does not guarantee 68 * that the order will remain constant over time. 69 * 70 * <p>This class provides constant-time performance for the basic 71 * operations ({@code get} and {@code put}), assuming the system 72 * identity hash function ({@link System#identityHashCode(Object)}) 73 * disperses elements properly among the buckets. 74 * 75 * <p>This class has one tuning parameter (which affects performance but not 76 * semantics): <i>expected maximum size</i>. This parameter is the maximum 77 * number of key-value mappings that the map is expected to hold. Internally, 78 * this parameter is used to determine the number of buckets initially 79 * comprising the hash table. The precise relationship between the expected 80 * maximum size and the number of buckets is unspecified. 81 * 82 * <p>If the size of the map (the number of key-value mappings) sufficiently 83 * exceeds the expected maximum size, the number of buckets is increased. 84 * Increasing the number of buckets ("rehashing") may be fairly expensive, so 85 * it pays to create identity hash maps with a sufficiently large expected 86 * maximum size. On the other hand, iteration over collection views requires 87 * time proportional to the number of buckets in the hash table, so it 88 * pays not to set the expected maximum size too high if you are especially 89 * concerned with iteration performance or memory usage. 90 * 91 * <p><strong>Note that this implementation is not synchronized.</strong> 92 * If multiple threads access an identity hash map concurrently, and at 93 * least one of the threads modifies the map structurally, it <i>must</i> 94 * be synchronized externally. (A structural modification is any operation 95 * that adds or deletes one or more mappings; merely changing the value 96 * associated with a key that an instance already contains is not a 97 * structural modification.) This is typically accomplished by 98 * synchronizing on some object that naturally encapsulates the map. 99 * 100 * If no such object exists, the map should be "wrapped" using the 101 * {@link Collections#synchronizedMap Collections.synchronizedMap} 102 * method. This is best done at creation time, to prevent accidental 103 * unsynchronized access to the map:<pre> 104 * Map m = Collections.synchronizedMap(new IdentityHashMap(...));</pre> 105 * 106 * <p>The iterators returned by the {@code iterator} method of the 107 * collections returned by all of this class's "collection view 108 * methods" are <i>fail-fast</i>: if the map is structurally modified 109 * at any time after the iterator is created, in any way except 110 * through the iterator's own {@code remove} method, the iterator 111 * will throw a {@link ConcurrentModificationException}. Thus, in the 112 * face of concurrent modification, the iterator fails quickly and 113 * cleanly, rather than risking arbitrary, non-deterministic behavior 114 * at an undetermined time in the future. 115 * 116 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 117 * as it is, generally speaking, impossible to make any hard guarantees in the 118 * presence of unsynchronized concurrent modification. Fail-fast iterators 119 * throw {@code ConcurrentModificationException} on a best-effort basis. 120 * Therefore, it would be wrong to write a program that depended on this 121 * exception for its correctness: <i>fail-fast iterators should be used only 122 * to detect bugs.</i> 123 * 124 * <p>This class is a member of the 125 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework"> 126 * Java Collections Framework</a>. 127 * 128 * @implNote 129 * <p>This is a simple <i>linear-probe</i> hash table, 130 * as described for example in texts by Sedgewick and Knuth. The array 131 * contains alternating keys and values, with keys at even indexes and values 132 * at odd indexes. (This arrangement has better locality for large 133 * tables than does using separate arrays.) For many Java implementations 134 * and operation mixes, this class will yield better performance than 135 * {@link HashMap}, which uses <i>chaining</i> rather than linear-probing. 136 * 137 * @param <K> the type of keys maintained by this map 138 * @param <V> the type of mapped values 139 * 140 * @see System#identityHashCode(Object) 141 * @see Object#hashCode() 142 * @see Collection 143 * @see Map 144 * @see HashMap 145 * @see TreeMap 146 * @author Doug Lea and Josh Bloch 147 * @since 1.4 148 */ 149 150 public class IdentityHashMap<K,V> 151 extends AbstractMap<K,V> 152 implements Map<K,V>, java.io.Serializable, Cloneable 153 { 154 /** 155 * The initial capacity used by the no-args constructor. 156 * MUST be a power of two. The value 32 corresponds to the 157 * (specified) expected maximum size of 21, given a load factor 158 * of 2/3. 159 */ 160 private static final int DEFAULT_CAPACITY = 32; 161 162 /** 163 * The minimum capacity, used if a lower value is implicitly specified 164 * by either of the constructors with arguments. The value 4 corresponds 165 * to an expected maximum size of 2, given a load factor of 2/3. 166 * MUST be a power of two. 167 */ 168 private static final int MINIMUM_CAPACITY = 4; 169 170 /** 171 * The maximum capacity, used if a higher value is implicitly specified 172 * by either of the constructors with arguments. 173 * MUST be a power of two <= 1<<29. 174 * 175 * In fact, the map can hold no more than MAXIMUM_CAPACITY-1 items 176 * because it has to have at least one slot with the key == null 177 * in order to avoid infinite loops in get(), put(), remove() 178 */ 179 private static final int MAXIMUM_CAPACITY = 1 << 29; 180 181 /** 182 * The table, resized as necessary. Length MUST always be a power of two. 183 */ 184 transient Object[] table; // non-private to simplify nested class access 185 186 /** 187 * The number of key-value mappings contained in this identity hash map. 188 * 189 * @serial 190 */ 191 int size; 192 193 /** 194 * The number of modifications, to support fast-fail iterators 195 */ 196 transient int modCount; 197 198 /** 199 * Value representing null keys inside tables. 200 */ 201 static final Object NULL_KEY = new Object(); 202 203 /** 204 * Use NULL_KEY for key if it is null. 205 */ maskNull(Object key)206 private static Object maskNull(Object key) { 207 return (key == null ? NULL_KEY : key); 208 } 209 210 /** 211 * Returns internal representation of null key back to caller as null. 212 */ unmaskNull(Object key)213 static final Object unmaskNull(Object key) { 214 return (key == NULL_KEY ? null : key); 215 } 216 217 /** 218 * Constructs a new, empty identity hash map with a default expected 219 * maximum size (21). 220 */ IdentityHashMap()221 public IdentityHashMap() { 222 init(DEFAULT_CAPACITY); 223 } 224 225 /** 226 * Constructs a new, empty map with the specified expected maximum size. 227 * Putting more than the expected number of key-value mappings into 228 * the map may cause the internal data structure to grow, which may be 229 * somewhat time-consuming. 230 * 231 * @param expectedMaxSize the expected maximum size of the map 232 * @throws IllegalArgumentException if {@code expectedMaxSize} is negative 233 */ IdentityHashMap(int expectedMaxSize)234 public IdentityHashMap(int expectedMaxSize) { 235 if (expectedMaxSize < 0) 236 throw new IllegalArgumentException("expectedMaxSize is negative: " 237 + expectedMaxSize); 238 init(capacity(expectedMaxSize)); 239 } 240 241 /** 242 * Returns the appropriate capacity for the given expected maximum size. 243 * Returns the smallest power of two between MINIMUM_CAPACITY and 244 * MAXIMUM_CAPACITY, inclusive, that is greater than (3 * 245 * expectedMaxSize)/2, if such a number exists. Otherwise returns 246 * MAXIMUM_CAPACITY. 247 */ capacity(int expectedMaxSize)248 private static int capacity(int expectedMaxSize) { 249 // assert expectedMaxSize >= 0; 250 return 251 (expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY : 252 (expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY : 253 Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1)); 254 } 255 256 /** 257 * Initializes object to be an empty map with the specified initial 258 * capacity, which is assumed to be a power of two between 259 * MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive. 260 */ init(int initCapacity)261 private void init(int initCapacity) { 262 // assert (initCapacity & -initCapacity) == initCapacity; // power of 2 263 // assert initCapacity >= MINIMUM_CAPACITY; 264 // assert initCapacity <= MAXIMUM_CAPACITY; 265 266 table = new Object[2 * initCapacity]; 267 } 268 269 /** 270 * Constructs a new identity hash map containing the keys-value mappings 271 * in the specified map. 272 * 273 * @param m the map whose mappings are to be placed into this map 274 * @throws NullPointerException if the specified map is null 275 */ IdentityHashMap(Map<? extends K, ? extends V> m)276 public IdentityHashMap(Map<? extends K, ? extends V> m) { 277 // Allow for a bit of growth 278 this((int) ((1 + m.size()) * 1.1)); 279 putAll(m); 280 } 281 282 /** 283 * Returns the number of key-value mappings in this identity hash map. 284 * 285 * @return the number of key-value mappings in this map 286 */ size()287 public int size() { 288 return size; 289 } 290 291 /** 292 * Returns {@code true} if this identity hash map contains no key-value 293 * mappings. 294 * 295 * @return {@code true} if this identity hash map contains no key-value 296 * mappings 297 */ isEmpty()298 public boolean isEmpty() { 299 return size == 0; 300 } 301 302 /** 303 * Returns index for Object x. 304 */ hash(Object x, int length)305 private static int hash(Object x, int length) { 306 int h = System.identityHashCode(x); 307 // Multiply by -254 to use the hash LSB and to ensure index is even 308 return ((h << 1) - (h << 8)) & (length - 1); 309 } 310 311 /** 312 * Circularly traverses table of size len. 313 */ nextKeyIndex(int i, int len)314 private static int nextKeyIndex(int i, int len) { 315 return (i + 2 < len ? i + 2 : 0); 316 } 317 318 /** 319 * Returns the value to which the specified key is mapped, 320 * or {@code null} if this map contains no mapping for the key. 321 * 322 * <p>More formally, if this map contains a mapping from a key 323 * {@code k} to a value {@code v} such that {@code (key == k)}, 324 * then this method returns {@code v}; otherwise it returns 325 * {@code null}. (There can be at most one such mapping.) 326 * 327 * <p>A return value of {@code null} does not <i>necessarily</i> 328 * indicate that the map contains no mapping for the key; it's also 329 * possible that the map explicitly maps the key to {@code null}. 330 * The {@link #containsKey containsKey} operation may be used to 331 * distinguish these two cases. 332 * 333 * @see #put(Object, Object) 334 */ 335 @SuppressWarnings("unchecked") get(Object key)336 public V get(Object key) { 337 Object k = maskNull(key); 338 Object[] tab = table; 339 int len = tab.length; 340 int i = hash(k, len); 341 while (true) { 342 Object item = tab[i]; 343 if (item == k) 344 return (V) tab[i + 1]; 345 if (item == null) 346 return null; 347 i = nextKeyIndex(i, len); 348 } 349 } 350 351 /** 352 * Tests whether the specified object reference is a key in this identity 353 * hash map. Returns {@code true} if and only if this map contains a mapping 354 * with key {@code k} such that {@code (key == k)}. 355 * 356 * @param key possible key 357 * @return {@code true} if the specified object reference is a key 358 * in this map 359 * @see #containsValue(Object) 360 */ containsKey(Object key)361 public boolean containsKey(Object key) { 362 Object k = maskNull(key); 363 Object[] tab = table; 364 int len = tab.length; 365 int i = hash(k, len); 366 while (true) { 367 Object item = tab[i]; 368 if (item == k) 369 return true; 370 if (item == null) 371 return false; 372 i = nextKeyIndex(i, len); 373 } 374 } 375 376 /** 377 * Tests whether the specified object reference is a value in this identity 378 * hash map. Returns {@code true} if and only if this map contains a mapping 379 * with value {@code v} such that {@code (value == v)}. 380 * 381 * @param value value whose presence in this map is to be tested 382 * @return {@code true} if this map maps one or more keys to the 383 * specified object reference 384 * @see #containsKey(Object) 385 */ containsValue(Object value)386 public boolean containsValue(Object value) { 387 Object[] tab = table; 388 for (int i = 1; i < tab.length; i += 2) 389 if (tab[i] == value && tab[i - 1] != null) 390 return true; 391 392 return false; 393 } 394 395 /** 396 * Tests if the specified key-value mapping is in the map. 397 * 398 * @param key possible key 399 * @param value possible value 400 * @return {@code true} if and only if the specified key-value 401 * mapping is in the map 402 */ containsMapping(Object key, Object value)403 private boolean containsMapping(Object key, Object value) { 404 Object k = maskNull(key); 405 Object[] tab = table; 406 int len = tab.length; 407 int i = hash(k, len); 408 while (true) { 409 Object item = tab[i]; 410 if (item == k) 411 return tab[i + 1] == value; 412 if (item == null) 413 return false; 414 i = nextKeyIndex(i, len); 415 } 416 } 417 418 /** 419 * Associates the specified value with the specified key in this identity 420 * hash map. If this map already {@link containsKey(Object) contains} 421 * a mapping for the key, the old value is replaced, otherwise, a new mapping 422 * is inserted into this map. 423 * 424 * @param key the key with which the specified value is to be associated 425 * @param value the value to be associated with the specified key 426 * @return the previous value associated with {@code key}, or 427 * {@code null} if there was no mapping for {@code key}. 428 * (A {@code null} return can also indicate that the map 429 * previously associated {@code null} with {@code key}.) 430 * @see Object#equals(Object) 431 * @see #get(Object) 432 * @see #containsKey(Object) 433 */ put(K key, V value)434 public V put(K key, V value) { 435 final Object k = maskNull(key); 436 437 retryAfterResize: for (;;) { 438 final Object[] tab = table; 439 final int len = tab.length; 440 int i = hash(k, len); 441 442 for (Object item; (item = tab[i]) != null; 443 i = nextKeyIndex(i, len)) { 444 if (item == k) { 445 @SuppressWarnings("unchecked") 446 V oldValue = (V) tab[i + 1]; 447 tab[i + 1] = value; 448 return oldValue; 449 } 450 } 451 452 final int s = size + 1; 453 // Use optimized form of 3 * s. 454 // Next capacity is len, 2 * current capacity. 455 if (s + (s << 1) > len && resize(len)) 456 continue retryAfterResize; 457 458 modCount++; 459 tab[i] = k; 460 tab[i + 1] = value; 461 size = s; 462 return null; 463 } 464 } 465 466 /** 467 * Resizes the table if necessary to hold given capacity. 468 * 469 * @param newCapacity the new capacity, must be a power of two. 470 * @return whether a resize did in fact take place 471 */ resize(int newCapacity)472 private boolean resize(int newCapacity) { 473 // assert (newCapacity & -newCapacity) == newCapacity; // power of 2 474 int newLength = newCapacity * 2; 475 476 Object[] oldTable = table; 477 int oldLength = oldTable.length; 478 if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further 479 if (size == MAXIMUM_CAPACITY - 1) 480 throw new IllegalStateException("Capacity exhausted."); 481 return false; 482 } 483 if (oldLength >= newLength) 484 return false; 485 486 Object[] newTable = new Object[newLength]; 487 488 for (int j = 0; j < oldLength; j += 2) { 489 Object key = oldTable[j]; 490 if (key != null) { 491 Object value = oldTable[j+1]; 492 oldTable[j] = null; 493 oldTable[j+1] = null; 494 int i = hash(key, newLength); 495 while (newTable[i] != null) 496 i = nextKeyIndex(i, newLength); 497 newTable[i] = key; 498 newTable[i + 1] = value; 499 } 500 } 501 table = newTable; 502 return true; 503 } 504 505 /** 506 * Copies all of the mappings from the specified map to this map. 507 * For each mapping in the specified map, if this map already 508 * {@link containsKey(Object) contains} a mapping for the key, 509 * its value is replaced with the value from the specified map; 510 * otherwise, a new mapping is inserted into this map. 511 * 512 * @param m mappings to be stored in this map 513 * @throws NullPointerException if the specified map is null 514 */ putAll(Map<? extends K, ? extends V> m)515 public void putAll(Map<? extends K, ? extends V> m) { 516 int n = m.size(); 517 if (n == 0) 518 return; 519 if (n > size) 520 resize(capacity(n)); // conservatively pre-expand 521 522 for (Entry<? extends K, ? extends V> e : m.entrySet()) 523 put(e.getKey(), e.getValue()); 524 } 525 526 /** 527 * Removes the mapping for this key from this map if present. 528 * The mapping is removed if and only if the mapping has a key 529 * {@code k} such that (key == k). 530 * 531 * @param key key whose mapping is to be removed from the map 532 * @return the previous value associated with {@code key}, or 533 * {@code null} if there was no mapping for {@code key}. 534 * (A {@code null} return can also indicate that the map 535 * previously associated {@code null} with {@code key}.) 536 */ remove(Object key)537 public V remove(Object key) { 538 Object k = maskNull(key); 539 Object[] tab = table; 540 int len = tab.length; 541 int i = hash(k, len); 542 543 while (true) { 544 Object item = tab[i]; 545 if (item == k) { 546 modCount++; 547 size--; 548 @SuppressWarnings("unchecked") 549 V oldValue = (V) tab[i + 1]; 550 tab[i + 1] = null; 551 tab[i] = null; 552 closeDeletion(i); 553 return oldValue; 554 } 555 if (item == null) 556 return null; 557 i = nextKeyIndex(i, len); 558 } 559 } 560 561 /** 562 * Removes the specified key-value mapping from the map if it is present. 563 * 564 * @param key possible key 565 * @param value possible value 566 * @return {@code true} if and only if the specified key-value 567 * mapping was in the map 568 */ removeMapping(Object key, Object value)569 private boolean removeMapping(Object key, Object value) { 570 Object k = maskNull(key); 571 Object[] tab = table; 572 int len = tab.length; 573 int i = hash(k, len); 574 575 while (true) { 576 Object item = tab[i]; 577 if (item == k) { 578 if (tab[i + 1] != value) 579 return false; 580 modCount++; 581 size--; 582 tab[i] = null; 583 tab[i + 1] = null; 584 closeDeletion(i); 585 return true; 586 } 587 if (item == null) 588 return false; 589 i = nextKeyIndex(i, len); 590 } 591 } 592 593 /** 594 * Rehash all possibly-colliding entries following a 595 * deletion. This preserves the linear-probe 596 * collision properties required by get, put, etc. 597 * 598 * @param d the index of a newly empty deleted slot 599 */ closeDeletion(int d)600 private void closeDeletion(int d) { 601 // Adapted from Knuth Section 6.4 Algorithm R 602 Object[] tab = table; 603 int len = tab.length; 604 605 // Look for items to swap into newly vacated slot 606 // starting at index immediately following deletion, 607 // and continuing until a null slot is seen, indicating 608 // the end of a run of possibly-colliding keys. 609 Object item; 610 for (int i = nextKeyIndex(d, len); (item = tab[i]) != null; 611 i = nextKeyIndex(i, len) ) { 612 // The following test triggers if the item at slot i (which 613 // hashes to be at slot r) should take the spot vacated by d. 614 // If so, we swap it in, and then continue with d now at the 615 // newly vacated i. This process will terminate when we hit 616 // the null slot at the end of this run. 617 // The test is messy because we are using a circular table. 618 int r = hash(item, len); 619 if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) { 620 tab[d] = item; 621 tab[d + 1] = tab[i + 1]; 622 tab[i] = null; 623 tab[i + 1] = null; 624 d = i; 625 } 626 } 627 } 628 629 /** 630 * Removes all of the mappings from this map. 631 * The map will be empty after this call returns. 632 */ clear()633 public void clear() { 634 modCount++; 635 Object[] tab = table; 636 for (int i = 0; i < tab.length; i++) 637 tab[i] = null; 638 size = 0; 639 } 640 641 /** 642 * Compares the specified object with this map for equality. Returns 643 * {@code true} if the given object is also a map and the two maps 644 * represent identical object-reference mappings. More formally, this 645 * map is equal to another map {@code m} if and only if 646 * {@code this.entrySet().equals(m.entrySet())}. See the 647 * {@link entrySet() entrySet} method for the specification of equality 648 * of this map's entries. 649 * 650 * <p><b>Owing to the reference-equality-based semantics of this map it is 651 * possible that the symmetry and transitivity requirements of the 652 * {@code Object.equals} contract may be violated if this map is compared 653 * to a normal map. However, the {@code Object.equals} contract is 654 * guaranteed to hold among {@code IdentityHashMap} instances.</b> 655 * 656 * @param o object to be compared for equality with this map 657 * @return {@code true} if the specified object is equal to this map 658 * @see Object#equals(Object) 659 */ equals(Object o)660 public boolean equals(Object o) { 661 if (o == this) { 662 return true; 663 } else if (o instanceof IdentityHashMap<?, ?> m) { 664 if (m.size() != size) 665 return false; 666 667 Object[] tab = m.table; 668 for (int i = 0; i < tab.length; i+=2) { 669 Object k = tab[i]; 670 if (k != null && !containsMapping(k, tab[i + 1])) 671 return false; 672 } 673 return true; 674 } else if (o instanceof Map<?, ?> m) { 675 return entrySet().equals(m.entrySet()); 676 } else { 677 return false; // o is not a Map 678 } 679 } 680 681 /** 682 * Returns the hash code value for this map. The hash code of a map is 683 * defined to be the sum of the hash codes of each entry of this map. 684 * See the {@link entrySet() entrySet} method for a specification of the 685 * hash code of this map's entries. 686 * 687 * <p>This specification ensures that {@code m1.equals(m2)} 688 * implies that {@code m1.hashCode()==m2.hashCode()} for any two 689 * {@code IdentityHashMap} instances {@code m1} and {@code m2}, as 690 * required by the general contract of {@link Object#hashCode}. 691 * 692 * <p><b>Owing to the reference-equality-based semantics of the 693 * {@code Map.Entry} instances in the set returned by this map's 694 * {@code entrySet} method, it is possible that the contractual 695 * requirement of {@code Object.hashCode} mentioned in the previous 696 * paragraph will be violated if one of the two objects being compared is 697 * an {@code IdentityHashMap} instance and the other is a normal map.</b> 698 * 699 * @return the hash code value for this map 700 * @see Object#equals(Object) 701 * @see #equals(Object) 702 */ hashCode()703 public int hashCode() { 704 int result = 0; 705 Object[] tab = table; 706 for (int i = 0; i < tab.length; i +=2) { 707 Object key = tab[i]; 708 if (key != null) { 709 Object k = unmaskNull(key); 710 result += System.identityHashCode(k) ^ 711 System.identityHashCode(tab[i + 1]); 712 } 713 } 714 return result; 715 } 716 717 /** 718 * Returns a shallow copy of this identity hash map: the keys and values 719 * themselves are not cloned. 720 * 721 * @return a shallow copy of this map 722 */ clone()723 public Object clone() { 724 try { 725 IdentityHashMap<?,?> m = (IdentityHashMap<?,?>) super.clone(); 726 m.entrySet = null; 727 m.table = table.clone(); 728 return m; 729 } catch (CloneNotSupportedException e) { 730 throw new InternalError(e); 731 } 732 } 733 734 private abstract class IdentityHashMapIterator<T> implements Iterator<T> { 735 int index = (size != 0 ? 0 : table.length); // current slot. 736 int expectedModCount = modCount; // to support fast-fail 737 int lastReturnedIndex = -1; // to allow remove() 738 boolean indexValid; // To avoid unnecessary next computation 739 Object[] traversalTable = table; // reference to main table or copy 740 hasNext()741 public boolean hasNext() { 742 Object[] tab = traversalTable; 743 for (int i = index; i < tab.length; i+=2) { 744 Object key = tab[i]; 745 if (key != null) { 746 index = i; 747 return indexValid = true; 748 } 749 } 750 index = tab.length; 751 return false; 752 } 753 nextIndex()754 protected int nextIndex() { 755 if (modCount != expectedModCount) 756 throw new ConcurrentModificationException(); 757 if (!indexValid && !hasNext()) 758 throw new NoSuchElementException(); 759 760 indexValid = false; 761 lastReturnedIndex = index; 762 index += 2; 763 return lastReturnedIndex; 764 } 765 remove()766 public void remove() { 767 if (lastReturnedIndex == -1) 768 throw new IllegalStateException(); 769 if (modCount != expectedModCount) 770 throw new ConcurrentModificationException(); 771 772 expectedModCount = ++modCount; 773 int deletedSlot = lastReturnedIndex; 774 lastReturnedIndex = -1; 775 // back up index to revisit new contents after deletion 776 index = deletedSlot; 777 indexValid = false; 778 779 // Removal code proceeds as in closeDeletion except that 780 // it must catch the rare case where an element already 781 // seen is swapped into a vacant slot that will be later 782 // traversed by this iterator. We cannot allow future 783 // next() calls to return it again. The likelihood of 784 // this occurring under 2/3 load factor is very slim, but 785 // when it does happen, we must make a copy of the rest of 786 // the table to use for the rest of the traversal. Since 787 // this can only happen when we are near the end of the table, 788 // even in these rare cases, this is not very expensive in 789 // time or space. 790 791 Object[] tab = traversalTable; 792 int len = tab.length; 793 794 int d = deletedSlot; 795 Object key = tab[d]; 796 tab[d] = null; // vacate the slot 797 tab[d + 1] = null; 798 799 // If traversing a copy, remove in real table. 800 // We can skip gap-closure on copy. 801 if (tab != IdentityHashMap.this.table) { 802 IdentityHashMap.this.remove(key); 803 expectedModCount = modCount; 804 return; 805 } 806 807 size--; 808 809 Object item; 810 for (int i = nextKeyIndex(d, len); (item = tab[i]) != null; 811 i = nextKeyIndex(i, len)) { 812 int r = hash(item, len); 813 // See closeDeletion for explanation of this conditional 814 if ((i < r && (r <= d || d <= i)) || 815 (r <= d && d <= i)) { 816 817 // If we are about to swap an already-seen element 818 // into a slot that may later be returned by next(), 819 // then clone the rest of table for use in future 820 // next() calls. It is OK that our copy will have 821 // a gap in the "wrong" place, since it will never 822 // be used for searching anyway. 823 824 if (i < deletedSlot && d >= deletedSlot && 825 traversalTable == IdentityHashMap.this.table) { 826 int remaining = len - deletedSlot; 827 Object[] newTable = new Object[remaining]; 828 System.arraycopy(tab, deletedSlot, 829 newTable, 0, remaining); 830 traversalTable = newTable; 831 index = 0; 832 } 833 834 tab[d] = item; 835 tab[d + 1] = tab[i + 1]; 836 tab[i] = null; 837 tab[i + 1] = null; 838 d = i; 839 } 840 } 841 } 842 } 843 844 private class KeyIterator extends IdentityHashMapIterator<K> { 845 @SuppressWarnings("unchecked") next()846 public K next() { 847 return (K) unmaskNull(traversalTable[nextIndex()]); 848 } 849 } 850 851 private class ValueIterator extends IdentityHashMapIterator<V> { 852 @SuppressWarnings("unchecked") next()853 public V next() { 854 return (V) traversalTable[nextIndex() + 1]; 855 } 856 } 857 858 private class EntryIterator 859 extends IdentityHashMapIterator<Map.Entry<K,V>> 860 { 861 private Entry lastReturnedEntry; 862 next()863 public Map.Entry<K,V> next() { 864 lastReturnedEntry = new Entry(nextIndex()); 865 return lastReturnedEntry; 866 } 867 remove()868 public void remove() { 869 lastReturnedIndex = 870 ((null == lastReturnedEntry) ? -1 : lastReturnedEntry.index); 871 super.remove(); 872 lastReturnedEntry.index = lastReturnedIndex; 873 lastReturnedEntry = null; 874 } 875 876 private class Entry implements Map.Entry<K,V> { 877 private int index; 878 Entry(int index)879 private Entry(int index) { 880 this.index = index; 881 } 882 883 @SuppressWarnings("unchecked") getKey()884 public K getKey() { 885 checkIndexForEntryUse(); 886 return (K) unmaskNull(traversalTable[index]); 887 } 888 889 @SuppressWarnings("unchecked") getValue()890 public V getValue() { 891 checkIndexForEntryUse(); 892 return (V) traversalTable[index+1]; 893 } 894 895 @SuppressWarnings("unchecked") setValue(V value)896 public V setValue(V value) { 897 checkIndexForEntryUse(); 898 V oldValue = (V) traversalTable[index+1]; 899 traversalTable[index+1] = value; 900 // if shadowing, force into main table 901 if (traversalTable != IdentityHashMap.this.table) 902 put((K) traversalTable[index], value); 903 return oldValue; 904 } 905 equals(Object o)906 public boolean equals(Object o) { 907 if (index < 0) 908 return super.equals(o); 909 910 return o instanceof Map.Entry<?, ?> e 911 && e.getKey() == unmaskNull(traversalTable[index]) 912 && e.getValue() == traversalTable[index+1]; 913 } 914 hashCode()915 public int hashCode() { 916 if (lastReturnedIndex < 0) 917 return super.hashCode(); 918 919 return (System.identityHashCode(unmaskNull(traversalTable[index])) ^ 920 System.identityHashCode(traversalTable[index+1])); 921 } 922 toString()923 public String toString() { 924 if (index < 0) 925 return super.toString(); 926 927 return (unmaskNull(traversalTable[index]) + "=" 928 + traversalTable[index+1]); 929 } 930 checkIndexForEntryUse()931 private void checkIndexForEntryUse() { 932 if (index < 0) 933 throw new IllegalStateException("Entry was removed"); 934 } 935 } 936 } 937 938 // Views 939 940 /** 941 * This field is initialized to contain an instance of the entry set 942 * view the first time this view is requested. The view is stateless, 943 * so there's no reason to create more than one. 944 */ 945 private transient Set<Map.Entry<K,V>> entrySet; 946 947 /** 948 * Returns an identity-based set view of the keys contained in this map. 949 * The set is backed by the map, so changes to the map are reflected in 950 * the set, and vice-versa. If the map is modified while an iteration 951 * over the set is in progress, the results of the iteration are 952 * undefined. The set supports element removal, which removes the 953 * corresponding mapping from the map, via the {@code Iterator.remove}, 954 * {@code Set.remove}, {@code removeAll}, {@code retainAll}, and 955 * {@code clear} methods. It does not support the {@code add} or 956 * {@code addAll} methods. 957 * 958 * <p><b>While the object returned by this method implements the 959 * {@code Set} interface, it does <i>not</i> obey {@code Set's} general 960 * contract. Like its backing map, the set returned by this method 961 * defines element equality as reference-equality rather than 962 * object-equality. This affects the behavior of its {@code contains}, 963 * {@code remove}, {@code containsAll}, {@code equals}, and 964 * {@code hashCode} methods.</b> 965 * 966 * <p><b>The {@code equals} method of the returned set returns {@code true} 967 * only if the specified object is a set containing exactly the same 968 * object references as the returned set. The symmetry and transitivity 969 * requirements of the {@code Object.equals} contract may be violated if 970 * the set returned by this method is compared to a normal set. However, 971 * the {@code Object.equals} contract is guaranteed to hold among sets 972 * returned by this method.</b> 973 * 974 * <p>The {@code hashCode} method of the returned set returns the sum of 975 * the <i>identity hashcodes</i> of the elements in the set, rather than 976 * the sum of their hashcodes. This is mandated by the change in the 977 * semantics of the {@code equals} method, in order to enforce the 978 * general contract of the {@code Object.hashCode} method among sets 979 * returned by this method. 980 * 981 * @return an identity-based set view of the keys contained in this map 982 * @see Object#equals(Object) 983 * @see System#identityHashCode(Object) 984 */ keySet()985 public Set<K> keySet() { 986 Set<K> ks = keySet; 987 if (ks == null) { 988 ks = new KeySet(); 989 keySet = ks; 990 } 991 return ks; 992 } 993 994 private class KeySet extends AbstractSet<K> { iterator()995 public Iterator<K> iterator() { 996 return new KeyIterator(); 997 } size()998 public int size() { 999 return size; 1000 } contains(Object o)1001 public boolean contains(Object o) { 1002 return containsKey(o); 1003 } remove(Object o)1004 public boolean remove(Object o) { 1005 int oldSize = size; 1006 IdentityHashMap.this.remove(o); 1007 return size != oldSize; 1008 } 1009 /* 1010 * Must revert from AbstractSet's impl to AbstractCollection's, as 1011 * the former contains an optimization that results in incorrect 1012 * behavior when c is a smaller "normal" (non-identity-based) Set. 1013 */ removeAll(Collection<?> c)1014 public boolean removeAll(Collection<?> c) { 1015 Objects.requireNonNull(c); 1016 boolean modified = false; 1017 for (Iterator<K> i = iterator(); i.hasNext(); ) { 1018 if (c.contains(i.next())) { 1019 i.remove(); 1020 modified = true; 1021 } 1022 } 1023 return modified; 1024 } clear()1025 public void clear() { 1026 IdentityHashMap.this.clear(); 1027 } hashCode()1028 public int hashCode() { 1029 int result = 0; 1030 for (K key : this) 1031 result += System.identityHashCode(key); 1032 return result; 1033 } toArray()1034 public Object[] toArray() { 1035 return toArray(new Object[0]); 1036 } 1037 @SuppressWarnings("unchecked") toArray(T[] a)1038 public <T> T[] toArray(T[] a) { 1039 int expectedModCount = modCount; 1040 int size = size(); 1041 if (a.length < size) 1042 a = (T[]) Array.newInstance(a.getClass().getComponentType(), size); 1043 Object[] tab = table; 1044 int ti = 0; 1045 for (int si = 0; si < tab.length; si += 2) { 1046 Object key; 1047 if ((key = tab[si]) != null) { // key present ? 1048 // more elements than expected -> concurrent modification from other thread 1049 if (ti >= size) { 1050 throw new ConcurrentModificationException(); 1051 } 1052 a[ti++] = (T) unmaskNull(key); // unmask key 1053 } 1054 } 1055 // fewer elements than expected or concurrent modification from other thread detected 1056 if (ti < size || expectedModCount != modCount) { 1057 throw new ConcurrentModificationException(); 1058 } 1059 // final null marker as per spec 1060 if (ti < a.length) { 1061 a[ti] = null; 1062 } 1063 return a; 1064 } 1065 spliterator()1066 public Spliterator<K> spliterator() { 1067 return new KeySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0); 1068 } 1069 } 1070 1071 /** 1072 * Returns a {@link Collection} view of the values contained in this map. 1073 * The collection is backed by the map, so changes to the map are 1074 * reflected in the collection, and vice-versa. If the map is 1075 * modified while an iteration over the collection is in progress, 1076 * the results of the iteration are undefined. The collection 1077 * supports element removal, which removes the corresponding 1078 * mapping from the map, via the {@code Iterator.remove}, 1079 * {@code Collection.remove}, {@code removeAll}, 1080 * {@code retainAll} and {@code clear} methods. It does not 1081 * support the {@code add} or {@code addAll} methods. 1082 * 1083 * <p><b>While the object returned by this method implements the 1084 * {@code Collection} interface, it does <i>not</i> obey 1085 * {@code Collection's} general contract. Like its backing map, 1086 * the collection returned by this method defines element equality as 1087 * reference-equality rather than object-equality. This affects the 1088 * behavior of its {@code contains}, {@code remove} and 1089 * {@code containsAll} methods.</b> 1090 */ values()1091 public Collection<V> values() { 1092 Collection<V> vs = values; 1093 if (vs == null) { 1094 vs = new Values(); 1095 values = vs; 1096 } 1097 return vs; 1098 } 1099 1100 private class Values extends AbstractCollection<V> { iterator()1101 public Iterator<V> iterator() { 1102 return new ValueIterator(); 1103 } size()1104 public int size() { 1105 return size; 1106 } contains(Object o)1107 public boolean contains(Object o) { 1108 return containsValue(o); 1109 } remove(Object o)1110 public boolean remove(Object o) { 1111 for (Iterator<V> i = iterator(); i.hasNext(); ) { 1112 if (i.next() == o) { 1113 i.remove(); 1114 return true; 1115 } 1116 } 1117 return false; 1118 } clear()1119 public void clear() { 1120 IdentityHashMap.this.clear(); 1121 } toArray()1122 public Object[] toArray() { 1123 return toArray(new Object[0]); 1124 } 1125 @SuppressWarnings("unchecked") toArray(T[] a)1126 public <T> T[] toArray(T[] a) { 1127 int expectedModCount = modCount; 1128 int size = size(); 1129 if (a.length < size) 1130 a = (T[]) Array.newInstance(a.getClass().getComponentType(), size); 1131 Object[] tab = table; 1132 int ti = 0; 1133 for (int si = 0; si < tab.length; si += 2) { 1134 if (tab[si] != null) { // key present ? 1135 // more elements than expected -> concurrent modification from other thread 1136 if (ti >= size) { 1137 throw new ConcurrentModificationException(); 1138 } 1139 a[ti++] = (T) tab[si+1]; // copy value 1140 } 1141 } 1142 // fewer elements than expected or concurrent modification from other thread detected 1143 if (ti < size || expectedModCount != modCount) { 1144 throw new ConcurrentModificationException(); 1145 } 1146 // final null marker as per spec 1147 if (ti < a.length) { 1148 a[ti] = null; 1149 } 1150 return a; 1151 } 1152 spliterator()1153 public Spliterator<V> spliterator() { 1154 return new ValueSpliterator<>(IdentityHashMap.this, 0, -1, 0, 0); 1155 } 1156 } 1157 1158 /** 1159 * Returns a {@link Set} view of the mappings contained in this map. 1160 * Each element in the returned set is a reference-equality-based 1161 * {@code Map.Entry}. The set is backed by the map, so changes 1162 * to the map are reflected in the set, and vice-versa. If the 1163 * map is modified while an iteration over the set is in progress, 1164 * the results of the iteration are undefined. The set supports 1165 * element removal, which removes the corresponding mapping from 1166 * the map, via the {@code Iterator.remove}, {@code Set.remove}, 1167 * {@code removeAll}, {@code retainAll} and {@code clear} 1168 * methods. It does not support the {@code add} or 1169 * {@code addAll} methods. 1170 * 1171 * <p>Like the backing map, the {@code Map.Entry} objects in the set 1172 * returned by this method define key and value equality as 1173 * reference-equality rather than object-equality. This affects the 1174 * behavior of the {@code equals} and {@code hashCode} methods of these 1175 * {@code Map.Entry} objects. A reference-equality based {@code Map.Entry 1176 * e} is equal to an object {@code o} if and only if {@code o} is a 1177 * {@code Map.Entry} and {@code e.getKey()==o.getKey() && 1178 * e.getValue()==o.getValue()}. To accommodate these equals 1179 * semantics, the {@code hashCode} method returns 1180 * {@code System.identityHashCode(e.getKey()) ^ 1181 * System.identityHashCode(e.getValue())}. (While the keys and values 1182 * are compared using reference equality, the {@code Map.Entry} 1183 * objects themselves are not.) 1184 * 1185 * <p><b>Owing to the reference-equality-based semantics of the 1186 * {@code Map.Entry} instances in the set returned by this method, 1187 * it is possible that the symmetry and transitivity requirements of 1188 * the {@link Object#equals(Object)} contract may be violated if any of 1189 * the entries in the set is compared to a normal map entry, or if 1190 * the set returned by this method is compared to a set of normal map 1191 * entries (such as would be returned by a call to this method on a normal 1192 * map). However, the {@code Object.equals} contract is guaranteed to 1193 * hold among identity-based map entries, and among sets of such entries. 1194 * </b> 1195 * 1196 * @return a set view of the identity-mappings contained in this map 1197 */ entrySet()1198 public Set<Map.Entry<K,V>> entrySet() { 1199 Set<Map.Entry<K,V>> es = entrySet; 1200 if (es != null) 1201 return es; 1202 else 1203 return entrySet = new EntrySet(); 1204 } 1205 1206 private class EntrySet extends AbstractSet<Map.Entry<K,V>> { iterator()1207 public Iterator<Map.Entry<K,V>> iterator() { 1208 return new EntryIterator(); 1209 } contains(Object o)1210 public boolean contains(Object o) { 1211 return o instanceof Entry<?, ?> entry 1212 && containsMapping(entry.getKey(), entry.getValue()); 1213 } remove(Object o)1214 public boolean remove(Object o) { 1215 return o instanceof Entry<?, ?> entry 1216 && removeMapping(entry.getKey(), entry.getValue()); 1217 } size()1218 public int size() { 1219 return size; 1220 } clear()1221 public void clear() { 1222 IdentityHashMap.this.clear(); 1223 } 1224 /* 1225 * Must revert from AbstractSet's impl to AbstractCollection's, as 1226 * the former contains an optimization that results in incorrect 1227 * behavior when c is a smaller "normal" (non-identity-based) Set. 1228 */ removeAll(Collection<?> c)1229 public boolean removeAll(Collection<?> c) { 1230 Objects.requireNonNull(c); 1231 boolean modified = false; 1232 for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); ) { 1233 if (c.contains(i.next())) { 1234 i.remove(); 1235 modified = true; 1236 } 1237 } 1238 return modified; 1239 } 1240 toArray()1241 public Object[] toArray() { 1242 return toArray(new Object[0]); 1243 } 1244 1245 @SuppressWarnings("unchecked") toArray(T[] a)1246 public <T> T[] toArray(T[] a) { 1247 int expectedModCount = modCount; 1248 int size = size(); 1249 if (a.length < size) 1250 a = (T[]) Array.newInstance(a.getClass().getComponentType(), size); 1251 Object[] tab = table; 1252 int ti = 0; 1253 for (int si = 0; si < tab.length; si += 2) { 1254 Object key; 1255 if ((key = tab[si]) != null) { // key present ? 1256 // more elements than expected -> concurrent modification from other thread 1257 if (ti >= size) { 1258 throw new ConcurrentModificationException(); 1259 } 1260 a[ti++] = (T) new AbstractMap.SimpleEntry<>(unmaskNull(key), tab[si + 1]); 1261 } 1262 } 1263 // fewer elements than expected or concurrent modification from other thread detected 1264 if (ti < size || expectedModCount != modCount) { 1265 throw new ConcurrentModificationException(); 1266 } 1267 // final null marker as per spec 1268 if (ti < a.length) { 1269 a[ti] = null; 1270 } 1271 return a; 1272 } 1273 spliterator()1274 public Spliterator<Map.Entry<K,V>> spliterator() { 1275 return new EntrySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0); 1276 } 1277 } 1278 1279 @java.io.Serial 1280 private static final long serialVersionUID = 8188218128353913216L; 1281 1282 /** 1283 * Saves the state of the {@code IdentityHashMap} instance to a stream 1284 * (i.e., serializes it). 1285 * 1286 * @serialData The <i>size</i> of the HashMap (the number of key-value 1287 * mappings) ({@code int}), followed by the key (Object) and 1288 * value (Object) for each key-value mapping represented by the 1289 * IdentityHashMap. The key-value mappings are emitted in no 1290 * particular order. 1291 */ 1292 @java.io.Serial writeObject(ObjectOutputStream s)1293 private void writeObject(ObjectOutputStream s) 1294 throws java.io.IOException { 1295 // Write out size (number of mappings) and any hidden stuff 1296 s.defaultWriteObject(); 1297 1298 // Write out size again (maintained for backward compatibility) 1299 s.writeInt(size); 1300 1301 // Write out keys and values (alternating) 1302 Object[] tab = table; 1303 for (int i = 0; i < tab.length; i += 2) { 1304 Object key = tab[i]; 1305 if (key != null) { 1306 s.writeObject(unmaskNull(key)); 1307 s.writeObject(tab[i + 1]); 1308 } 1309 } 1310 } 1311 1312 /** 1313 * Reconstitutes the {@code IdentityHashMap} instance from a stream (i.e., 1314 * deserializes it). 1315 */ 1316 @java.io.Serial readObject(ObjectInputStream s)1317 private void readObject(ObjectInputStream s) 1318 throws java.io.IOException, ClassNotFoundException { 1319 // Size (number of mappings) is written to the stream twice 1320 // Read first size value and ignore it 1321 s.readFields(); 1322 1323 // Read second size value, validate and assign to size field 1324 int size = s.readInt(); 1325 if (size < 0) 1326 throw new java.io.StreamCorruptedException 1327 ("Illegal mappings count: " + size); 1328 int cap = capacity(size); 1329 SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, cap*2); 1330 this.size = size; 1331 init(cap); 1332 1333 // Read the keys and values, and put the mappings in the table 1334 for (int i=0; i<size; i++) { 1335 @SuppressWarnings("unchecked") 1336 K key = (K) s.readObject(); 1337 @SuppressWarnings("unchecked") 1338 V value = (V) s.readObject(); 1339 putForCreate(key, value); 1340 } 1341 } 1342 1343 /** 1344 * The put method for readObject. It does not resize the table, 1345 * update modCount, etc. 1346 */ putForCreate(K key, V value)1347 private void putForCreate(K key, V value) 1348 throws java.io.StreamCorruptedException 1349 { 1350 Object k = maskNull(key); 1351 Object[] tab = table; 1352 int len = tab.length; 1353 int i = hash(k, len); 1354 1355 Object item; 1356 while ( (item = tab[i]) != null) { 1357 if (item == k) 1358 throw new java.io.StreamCorruptedException(); 1359 i = nextKeyIndex(i, len); 1360 } 1361 tab[i] = k; 1362 tab[i + 1] = value; 1363 } 1364 1365 @SuppressWarnings("unchecked") 1366 @Override forEach(BiConsumer<? super K, ? super V> action)1367 public void forEach(BiConsumer<? super K, ? super V> action) { 1368 Objects.requireNonNull(action); 1369 int expectedModCount = modCount; 1370 1371 Object[] t = table; 1372 for (int index = 0; index < t.length; index += 2) { 1373 Object k = t[index]; 1374 if (k != null) { 1375 action.accept((K) unmaskNull(k), (V) t[index + 1]); 1376 } 1377 1378 if (modCount != expectedModCount) { 1379 throw new ConcurrentModificationException(); 1380 } 1381 } 1382 } 1383 1384 @SuppressWarnings("unchecked") 1385 @Override replaceAll(BiFunction<? super K, ? super V, ? extends V> function)1386 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 1387 Objects.requireNonNull(function); 1388 int expectedModCount = modCount; 1389 1390 Object[] t = table; 1391 for (int index = 0; index < t.length; index += 2) { 1392 Object k = t[index]; 1393 if (k != null) { 1394 t[index + 1] = function.apply((K) unmaskNull(k), (V) t[index + 1]); 1395 } 1396 1397 if (modCount != expectedModCount) { 1398 throw new ConcurrentModificationException(); 1399 } 1400 } 1401 } 1402 1403 /** 1404 * {@inheritDoc} 1405 * 1406 * <p>More formally, if this map contains a mapping from a key 1407 * {@code k} to a value {@code v} such that {@code (key == k)} 1408 * and {@code (value == v)}, then this method removes the mapping 1409 * for this key and returns {@code true}; otherwise it returns 1410 * {@code false}. 1411 */ 1412 @Override remove(Object key, Object value)1413 public boolean remove(Object key, Object value) { 1414 return removeMapping(key, value); 1415 } 1416 1417 /** 1418 * {@inheritDoc} 1419 * 1420 * <p>More formally, if this map contains a mapping from a key 1421 * {@code k} to a value {@code v} such that {@code (key == k)} 1422 * and {@code (oldValue == v)}, then this method associates 1423 * {@code k} with {@code newValue} and returns {@code true}; 1424 * otherwise it returns {@code false}. 1425 */ 1426 @Override replace(K key, V oldValue, V newValue)1427 public boolean replace(K key, V oldValue, V newValue) { 1428 Object k = maskNull(key); 1429 Object[] tab = table; 1430 int len = tab.length; 1431 int i = hash(k, len); 1432 1433 while (true) { 1434 Object item = tab[i]; 1435 if (item == k) { 1436 if (tab[i + 1] != oldValue) 1437 return false; 1438 tab[i + 1] = newValue; 1439 return true; 1440 } 1441 if (item == null) 1442 return false; 1443 i = nextKeyIndex(i, len); 1444 } 1445 } 1446 1447 /** 1448 * Similar form as array-based Spliterators, but skips blank elements, 1449 * and guestimates size as decreasing by half per split. 1450 */ 1451 static class IdentityHashMapSpliterator<K,V> { 1452 final IdentityHashMap<K,V> map; 1453 int index; // current index, modified on advance/split 1454 int fence; // -1 until first use; then one past last index 1455 int est; // size estimate 1456 int expectedModCount; // initialized when fence set 1457 IdentityHashMapSpliterator(IdentityHashMap<K,V> map, int origin, int fence, int est, int expectedModCount)1458 IdentityHashMapSpliterator(IdentityHashMap<K,V> map, int origin, 1459 int fence, int est, int expectedModCount) { 1460 this.map = map; 1461 this.index = origin; 1462 this.fence = fence; 1463 this.est = est; 1464 this.expectedModCount = expectedModCount; 1465 } 1466 getFence()1467 final int getFence() { // initialize fence and size on first use 1468 int hi; 1469 if ((hi = fence) < 0) { 1470 est = map.size; 1471 expectedModCount = map.modCount; 1472 hi = fence = map.table.length; 1473 } 1474 return hi; 1475 } 1476 estimateSize()1477 public final long estimateSize() { 1478 getFence(); // force init 1479 return (long) est; 1480 } 1481 } 1482 1483 static final class KeySpliterator<K,V> 1484 extends IdentityHashMapSpliterator<K,V> 1485 implements Spliterator<K> { KeySpliterator(IdentityHashMap<K,V> map, int origin, int fence, int est, int expectedModCount)1486 KeySpliterator(IdentityHashMap<K,V> map, int origin, int fence, int est, 1487 int expectedModCount) { 1488 super(map, origin, fence, est, expectedModCount); 1489 } 1490 trySplit()1491 public KeySpliterator<K,V> trySplit() { 1492 int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1; 1493 return (lo >= mid) ? null : 1494 new KeySpliterator<>(map, lo, index = mid, est >>>= 1, 1495 expectedModCount); 1496 } 1497 1498 @SuppressWarnings("unchecked") forEachRemaining(Consumer<? super K> action)1499 public void forEachRemaining(Consumer<? super K> action) { 1500 if (action == null) 1501 throw new NullPointerException(); 1502 int i, hi, mc; Object key; 1503 IdentityHashMap<K,V> m; Object[] a; 1504 if ((m = map) != null && (a = m.table) != null && 1505 (i = index) >= 0 && (index = hi = getFence()) <= a.length) { 1506 for (; i < hi; i += 2) { 1507 if ((key = a[i]) != null) 1508 action.accept((K)unmaskNull(key)); 1509 } 1510 if (m.modCount == expectedModCount) 1511 return; 1512 } 1513 throw new ConcurrentModificationException(); 1514 } 1515 1516 @SuppressWarnings("unchecked") tryAdvance(Consumer<? super K> action)1517 public boolean tryAdvance(Consumer<? super K> action) { 1518 if (action == null) 1519 throw new NullPointerException(); 1520 Object[] a = map.table; 1521 int hi = getFence(); 1522 while (index < hi) { 1523 Object key = a[index]; 1524 index += 2; 1525 if (key != null) { 1526 action.accept((K)unmaskNull(key)); 1527 if (map.modCount != expectedModCount) 1528 throw new ConcurrentModificationException(); 1529 return true; 1530 } 1531 } 1532 return false; 1533 } 1534 characteristics()1535 public int characteristics() { 1536 return (fence < 0 || est == map.size ? SIZED : 0) | Spliterator.DISTINCT; 1537 } 1538 } 1539 1540 static final class ValueSpliterator<K,V> 1541 extends IdentityHashMapSpliterator<K,V> 1542 implements Spliterator<V> { ValueSpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est, int expectedModCount)1543 ValueSpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est, 1544 int expectedModCount) { 1545 super(m, origin, fence, est, expectedModCount); 1546 } 1547 trySplit()1548 public ValueSpliterator<K,V> trySplit() { 1549 int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1; 1550 return (lo >= mid) ? null : 1551 new ValueSpliterator<>(map, lo, index = mid, est >>>= 1, 1552 expectedModCount); 1553 } 1554 forEachRemaining(Consumer<? super V> action)1555 public void forEachRemaining(Consumer<? super V> action) { 1556 if (action == null) 1557 throw new NullPointerException(); 1558 int i, hi, mc; 1559 IdentityHashMap<K,V> m; Object[] a; 1560 if ((m = map) != null && (a = m.table) != null && 1561 (i = index) >= 0 && (index = hi = getFence()) <= a.length) { 1562 for (; i < hi; i += 2) { 1563 if (a[i] != null) { 1564 @SuppressWarnings("unchecked") V v = (V)a[i+1]; 1565 action.accept(v); 1566 } 1567 } 1568 if (m.modCount == expectedModCount) 1569 return; 1570 } 1571 throw new ConcurrentModificationException(); 1572 } 1573 tryAdvance(Consumer<? super V> action)1574 public boolean tryAdvance(Consumer<? super V> action) { 1575 if (action == null) 1576 throw new NullPointerException(); 1577 Object[] a = map.table; 1578 int hi = getFence(); 1579 while (index < hi) { 1580 Object key = a[index]; 1581 @SuppressWarnings("unchecked") V v = (V)a[index+1]; 1582 index += 2; 1583 if (key != null) { 1584 action.accept(v); 1585 if (map.modCount != expectedModCount) 1586 throw new ConcurrentModificationException(); 1587 return true; 1588 } 1589 } 1590 return false; 1591 } 1592 characteristics()1593 public int characteristics() { 1594 return (fence < 0 || est == map.size ? SIZED : 0); 1595 } 1596 1597 } 1598 1599 static final class EntrySpliterator<K,V> 1600 extends IdentityHashMapSpliterator<K,V> 1601 implements Spliterator<Map.Entry<K,V>> { EntrySpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est, int expectedModCount)1602 EntrySpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est, 1603 int expectedModCount) { 1604 super(m, origin, fence, est, expectedModCount); 1605 } 1606 trySplit()1607 public EntrySpliterator<K,V> trySplit() { 1608 int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1; 1609 return (lo >= mid) ? null : 1610 new EntrySpliterator<>(map, lo, index = mid, est >>>= 1, 1611 expectedModCount); 1612 } 1613 forEachRemaining(Consumer<? super Map.Entry<K, V>> action)1614 public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) { 1615 if (action == null) 1616 throw new NullPointerException(); 1617 int i, hi, mc; 1618 IdentityHashMap<K,V> m; Object[] a; 1619 if ((m = map) != null && (a = m.table) != null && 1620 (i = index) >= 0 && (index = hi = getFence()) <= a.length) { 1621 for (; i < hi; i += 2) { 1622 Object key = a[i]; 1623 if (key != null) { 1624 @SuppressWarnings("unchecked") K k = 1625 (K)unmaskNull(key); 1626 @SuppressWarnings("unchecked") V v = (V)a[i+1]; 1627 action.accept 1628 (new AbstractMap.SimpleImmutableEntry<>(k, v)); 1629 1630 } 1631 } 1632 if (m.modCount == expectedModCount) 1633 return; 1634 } 1635 throw new ConcurrentModificationException(); 1636 } 1637 tryAdvance(Consumer<? super Map.Entry<K,V>> action)1638 public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) { 1639 if (action == null) 1640 throw new NullPointerException(); 1641 Object[] a = map.table; 1642 int hi = getFence(); 1643 while (index < hi) { 1644 Object key = a[index]; 1645 @SuppressWarnings("unchecked") V v = (V)a[index+1]; 1646 index += 2; 1647 if (key != null) { 1648 @SuppressWarnings("unchecked") K k = 1649 (K)unmaskNull(key); 1650 action.accept 1651 (new AbstractMap.SimpleImmutableEntry<>(k, v)); 1652 if (map.modCount != expectedModCount) 1653 throw new ConcurrentModificationException(); 1654 return true; 1655 } 1656 } 1657 return false; 1658 } 1659 characteristics()1660 public int characteristics() { 1661 return (fence < 0 || est == map.size ? SIZED : 0) | Spliterator.DISTINCT; 1662 } 1663 } 1664 1665 } 1666