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