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