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