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