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