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