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