1 /*
2 * Copyright (c) 2000, 2019, 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.access.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 public void clear() {
991 IdentityHashMap.this.clear();
992 }
993 public int hashCode() {
994 int result = 0;
995 for (K key : this)
996 result += System.identityHashCode(key);
997 return result;
998 }
999 public Object[] toArray() {
1000 return toArray(new Object[0]);
1001 }
1002 @SuppressWarnings("unchecked")
1003 public <T> T[] toArray(T[] a) {
1004 int expectedModCount = modCount;
1005 int size = size();
1006 if (a.length < size)
1007 a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
1008 Object[] tab = table;
1009 int ti = 0;
1010 for (int si = 0; si < tab.length; si += 2) {
1011 Object key;
1012 if ((key = tab[si]) != null) { // key present ?
1013 // more elements than expected -> concurrent modification from other thread
1014 if (ti >= size) {
1015 throw new ConcurrentModificationException();
1016 }
1017 a[ti++] = (T) unmaskNull(key); // unmask key
1018 }
1019 }
1020 // fewer elements than expected or concurrent modification from other thread detected
1021 if (ti < size || expectedModCount != modCount) {
1022 throw new ConcurrentModificationException();
1023 }
1024 // final null marker as per spec
1025 if (ti < a.length) {
1026 a[ti] = null;
1027 }
1028 return a;
1029 }
1030
1031 public Spliterator<K> spliterator() {
1032 return new KeySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
1033 }
1034 }
1035
1036 /**
1037 * Returns a {@link Collection} view of the values contained in this map.
1038 * The collection is backed by the map, so changes to the map are
1039 * reflected in the collection, and vice-versa. If the map is
1040 * modified while an iteration over the collection is in progress,
1041 * the results of the iteration are undefined. The collection
1042 * supports element removal, which removes the corresponding
1043 * mapping from the map, via the {@code Iterator.remove},
1044 * {@code Collection.remove}, {@code removeAll},
1045 * {@code retainAll} and {@code clear} methods. It does not
1046 * support the {@code add} or {@code addAll} methods.
1047 *
1048 * <p><b>While the object returned by this method implements the
1049 * {@code Collection} interface, it does <i>not</i> obey
1050 * {@code Collection's} general contract. Like its backing map,
1051 * the collection returned by this method defines element equality as
1052 * reference-equality rather than object-equality. This affects the
1053 * behavior of its {@code contains}, {@code remove} and
1054 * {@code containsAll} methods.</b>
1055 */
1056 public Collection<V> values() {
1057 Collection<V> vs = values;
1058 if (vs == null) {
1059 vs = new Values();
1060 values = vs;
1061 }
1062 return vs;
1063 }
1064
1065 private class Values extends AbstractCollection<V> {
1066 public Iterator<V> iterator() {
1067 return new ValueIterator();
1068 }
1069 public int size() {
1070 return size;
1071 }
1072 public boolean contains(Object o) {
1073 return containsValue(o);
1074 }
1075 public boolean remove(Object o) {
1076 for (Iterator<V> i = iterator(); i.hasNext(); ) {
1077 if (i.next() == o) {
1078 i.remove();
1079 return true;
1080 }
1081 }
1082 return false;
1083 }
1084 public void clear() {
1085 IdentityHashMap.this.clear();
1086 }
1087 public Object[] toArray() {
1088 return toArray(new Object[0]);
1089 }
1090 @SuppressWarnings("unchecked")
1091 public <T> T[] toArray(T[] a) {
1092 int expectedModCount = modCount;
1093 int size = size();
1094 if (a.length < size)
1095 a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
1096 Object[] tab = table;
1097 int ti = 0;
1098 for (int si = 0; si < tab.length; si += 2) {
1099 if (tab[si] != null) { // key present ?
1100 // more elements than expected -> concurrent modification from other thread
1101 if (ti >= size) {
1102 throw new ConcurrentModificationException();
1103 }
1104 a[ti++] = (T) tab[si+1]; // copy value
1105 }
1106 }
1107 // fewer elements than expected or concurrent modification from other thread detected
1108 if (ti < size || expectedModCount != modCount) {
1109 throw new ConcurrentModificationException();
1110 }
1111 // final null marker as per spec
1112 if (ti < a.length) {
1113 a[ti] = null;
1114 }
1115 return a;
1116 }
1117
1118 public Spliterator<V> spliterator() {
1119 return new ValueSpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
1120 }
1121 }
1122
1123 /**
1124 * Returns a {@link Set} view of the mappings contained in this map.
1125 * Each element in the returned set is a reference-equality-based
1126 * {@code Map.Entry}. The set is backed by the map, so changes
1127 * to the map are reflected in the set, and vice-versa. If the
1128 * map is modified while an iteration over the set is in progress,
1129 * the results of the iteration are undefined. The set supports
1130 * element removal, which removes the corresponding mapping from
1131 * the map, via the {@code Iterator.remove}, {@code Set.remove},
1132 * {@code removeAll}, {@code retainAll} and {@code clear}
1133 * methods. It does not support the {@code add} or
1134 * {@code addAll} methods.
1135 *
1136 * <p>Like the backing map, the {@code Map.Entry} objects in the set
1137 * returned by this method define key and value equality as
1138 * reference-equality rather than object-equality. This affects the
1139 * behavior of the {@code equals} and {@code hashCode} methods of these
1140 * {@code Map.Entry} objects. A reference-equality based {@code Map.Entry
1141 * e} is equal to an object {@code o} if and only if {@code o} is a
1142 * {@code Map.Entry} and {@code e.getKey()==o.getKey() &&
1143 * e.getValue()==o.getValue()}. To accommodate these equals
1144 * semantics, the {@code hashCode} method returns
1145 * {@code System.identityHashCode(e.getKey()) ^
1146 * System.identityHashCode(e.getValue())}.
1147 *
1148 * <p><b>Owing to the reference-equality-based semantics of the
1149 * {@code Map.Entry} instances in the set returned by this method,
1150 * it is possible that the symmetry and transitivity requirements of
1151 * the {@link Object#equals(Object)} contract may be violated if any of
1152 * the entries in the set is compared to a normal map entry, or if
1153 * the set returned by this method is compared to a set of normal map
1154 * entries (such as would be returned by a call to this method on a normal
1155 * map). However, the {@code Object.equals} contract is guaranteed to
1156 * hold among identity-based map entries, and among sets of such entries.
1157 * </b>
1158 *
1159 * @return a set view of the identity-mappings contained in this map
1160 */
1161 public Set<Map.Entry<K,V>> entrySet() {
1162 Set<Map.Entry<K,V>> es = entrySet;
1163 if (es != null)
1164 return es;
1165 else
1166 return entrySet = new EntrySet();
1167 }
1168
1169 private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1170 public Iterator<Map.Entry<K,V>> iterator() {
1171 return new EntryIterator();
1172 }
1173 public boolean contains(Object o) {
1174 if (!(o instanceof Map.Entry))
1175 return false;
1176 Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
1177 return containsMapping(entry.getKey(), entry.getValue());
1178 }
1179 public boolean remove(Object o) {
1180 if (!(o instanceof Map.Entry))
1181 return false;
1182 Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
1183 return removeMapping(entry.getKey(), entry.getValue());
1184 }
1185 public int size() {
1186 return size;
1187 }
1188 public void clear() {
1189 IdentityHashMap.this.clear();
1190 }
1191 public Object[] toArray() {
1192 return toArray(new Object[0]);
1193 }
1194
1195 @SuppressWarnings("unchecked")
1196 public <T> T[] toArray(T[] a) {
1197 int expectedModCount = modCount;
1198 int size = size();
1199 if (a.length < size)
1200 a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
1201 Object[] tab = table;
1202 int ti = 0;
1203 for (int si = 0; si < tab.length; si += 2) {
1204 Object key;
1205 if ((key = tab[si]) != null) { // key present ?
1206 // more elements than expected -> concurrent modification from other thread
1207 if (ti >= size) {
1208 throw new ConcurrentModificationException();
1209 }
1210 a[ti++] = (T) new AbstractMap.SimpleEntry<>(unmaskNull(key), tab[si + 1]);
1211 }
1212 }
1213 // fewer elements than expected or concurrent modification from other thread detected
1214 if (ti < size || expectedModCount != modCount) {
1215 throw new ConcurrentModificationException();
1216 }
1217 // final null marker as per spec
1218 if (ti < a.length) {
1219 a[ti] = null;
1220 }
1221 return a;
1222 }
1223
1224 public Spliterator<Map.Entry<K,V>> spliterator() {
1225 return new EntrySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
1226 }
1227 }
1228
1229
1230 private static final long serialVersionUID = 8188218128353913216L;
1231
1232 /**
1233 * Saves the state of the {@code IdentityHashMap} instance to a stream
1234 * (i.e., serializes it).
1235 *
1236 * @serialData The <i>size</i> of the HashMap (the number of key-value
1237 * mappings) ({@code int}), followed by the key (Object) and
1238 * value (Object) for each key-value mapping represented by the
1239 * IdentityHashMap. The key-value mappings are emitted in no
1240 * particular order.
1241 */
1242 private void writeObject(java.io.ObjectOutputStream s)
1243 throws java.io.IOException {
1244 // Write out and any hidden stuff
1245 s.defaultWriteObject();
1246
1247 // Write out size (number of Mappings)
1248 s.writeInt(size);
1249
1250 // Write out keys and values (alternating)
1251 Object[] tab = table;
1252 for (int i = 0; i < tab.length; i += 2) {
1253 Object key = tab[i];
1254 if (key != null) {
1255 s.writeObject(unmaskNull(key));
1256 s.writeObject(tab[i + 1]);
1257 }
1258 }
1259 }
1260
1261 /**
1262 * Reconstitutes the {@code IdentityHashMap} instance from a stream (i.e.,
1263 * deserializes it).
1264 */
1265 private void readObject(java.io.ObjectInputStream s)
1266 throws java.io.IOException, ClassNotFoundException {
1267 // Read in any hidden stuff
1268 s.defaultReadObject();
1269
1270 // Read in size (number of Mappings)
1271 int size = s.readInt();
1272 if (size < 0)
1273 throw new java.io.StreamCorruptedException
1274 ("Illegal mappings count: " + size);
1275 int cap = capacity(size);
1276 SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, cap);
1277 init(cap);
1278
1279 // Read the keys and values, and put the mappings in the table
1280 for (int i=0; i<size; i++) {
1281 @SuppressWarnings("unchecked")
1282 K key = (K) s.readObject();
1283 @SuppressWarnings("unchecked")
1284 V value = (V) s.readObject();
1285 putForCreate(key, value);
1286 }
1287 }
1288
1289 /**
1290 * The put method for readObject. It does not resize the table,
1291 * update modCount, etc.
1292 */
1293 private void putForCreate(K key, V value)
1294 throws java.io.StreamCorruptedException
1295 {
1296 Object k = maskNull(key);
1297 Object[] tab = table;
1298 int len = tab.length;
1299 int i = hash(k, len);
1300
1301 Object item;
1302 while ( (item = tab[i]) != null) {
1303 if (item == k)
1304 throw new java.io.StreamCorruptedException();
1305 i = nextKeyIndex(i, len);
1306 }
1307 tab[i] = k;
1308 tab[i + 1] = value;
1309 }
1310
1311 @SuppressWarnings("unchecked")
1312 @Override
1313 public void forEach(BiConsumer<? super K, ? super V> action) {
1314 Objects.requireNonNull(action);
1315 int expectedModCount = modCount;
1316
1317 Object[] t = table;
1318 for (int index = 0; index < t.length; index += 2) {
1319 Object k = t[index];
1320 if (k != null) {
1321 action.accept((K) unmaskNull(k), (V) t[index + 1]);
1322 }
1323
1324 if (modCount != expectedModCount) {
1325 throw new ConcurrentModificationException();
1326 }
1327 }
1328 }
1329
1330 @SuppressWarnings("unchecked")
1331 @Override
1332 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1333 Objects.requireNonNull(function);
1334 int expectedModCount = modCount;
1335
1336 Object[] t = table;
1337 for (int index = 0; index < t.length; index += 2) {
1338 Object k = t[index];
1339 if (k != null) {
1340 t[index + 1] = function.apply((K) unmaskNull(k), (V) t[index + 1]);
1341 }
1342
1343 if (modCount != expectedModCount) {
1344 throw new ConcurrentModificationException();
1345 }
1346 }
1347 }
1348
1349 /**
1350 * Similar form as array-based Spliterators, but skips blank elements,
1351 * and guestimates size as decreasing by half per split.
1352 */
1353 static class IdentityHashMapSpliterator<K,V> {
1354 final IdentityHashMap<K,V> map;
1355 int index; // current index, modified on advance/split
1356 int fence; // -1 until first use; then one past last index
1357 int est; // size estimate
1358 int expectedModCount; // initialized when fence set
1359
1360 IdentityHashMapSpliterator(IdentityHashMap<K,V> map, int origin,
1361 int fence, int est, int expectedModCount) {
1362 this.map = map;
1363 this.index = origin;
1364 this.fence = fence;
1365 this.est = est;
1366 this.expectedModCount = expectedModCount;
1367 }
1368
1369 final int getFence() { // initialize fence and size on first use
1370 int hi;
1371 if ((hi = fence) < 0) {
1372 est = map.size;
1373 expectedModCount = map.modCount;
1374 hi = fence = map.table.length;
1375 }
1376 return hi;
1377 }
1378
1379 public final long estimateSize() {
1380 getFence(); // force init
1381 return (long) est;
1382 }
1383 }
1384
1385 static final class KeySpliterator<K,V>
1386 extends IdentityHashMapSpliterator<K,V>
1387 implements Spliterator<K> {
1388 KeySpliterator(IdentityHashMap<K,V> map, int origin, int fence, int est,
1389 int expectedModCount) {
1390 super(map, origin, fence, est, expectedModCount);
1391 }
1392
1393 public KeySpliterator<K,V> trySplit() {
1394 int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
1395 return (lo >= mid) ? null :
1396 new KeySpliterator<>(map, lo, index = mid, est >>>= 1,
1397 expectedModCount);
1398 }
1399
1400 @SuppressWarnings("unchecked")
1401 public void forEachRemaining(Consumer<? super K> action) {
1402 if (action == null)
1403 throw new NullPointerException();
1404 int i, hi, mc; Object key;
1405 IdentityHashMap<K,V> m; Object[] a;
1406 if ((m = map) != null && (a = m.table) != null &&
1407 (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
1408 for (; i < hi; i += 2) {
1409 if ((key = a[i]) != null)
1410 action.accept((K)unmaskNull(key));
1411 }
1412 if (m.modCount == expectedModCount)
1413 return;
1414 }
1415 throw new ConcurrentModificationException();
1416 }
1417
1418 @SuppressWarnings("unchecked")
1419 public boolean tryAdvance(Consumer<? super K> action) {
1420 if (action == null)
1421 throw new NullPointerException();
1422 Object[] a = map.table;
1423 int hi = getFence();
1424 while (index < hi) {
1425 Object key = a[index];
1426 index += 2;
1427 if (key != null) {
1428 action.accept((K)unmaskNull(key));
1429 if (map.modCount != expectedModCount)
1430 throw new ConcurrentModificationException();
1431 return true;
1432 }
1433 }
1434 return false;
1435 }
1436
1437 public int characteristics() {
1438 return (fence < 0 || est == map.size ? SIZED : 0) | Spliterator.DISTINCT;
1439 }
1440 }
1441
1442 static final class ValueSpliterator<K,V>
1443 extends IdentityHashMapSpliterator<K,V>
1444 implements Spliterator<V> {
1445 ValueSpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est,
1446 int expectedModCount) {
1447 super(m, origin, fence, est, expectedModCount);
1448 }
1449
1450 public ValueSpliterator<K,V> trySplit() {
1451 int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
1452 return (lo >= mid) ? null :
1453 new ValueSpliterator<>(map, lo, index = mid, est >>>= 1,
1454 expectedModCount);
1455 }
1456
1457 public void forEachRemaining(Consumer<? super V> action) {
1458 if (action == null)
1459 throw new NullPointerException();
1460 int i, hi, mc;
1461 IdentityHashMap<K,V> m; Object[] a;
1462 if ((m = map) != null && (a = m.table) != null &&
1463 (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
1464 for (; i < hi; i += 2) {
1465 if (a[i] != null) {
1466 @SuppressWarnings("unchecked") V v = (V)a[i+1];
1467 action.accept(v);
1468 }
1469 }
1470 if (m.modCount == expectedModCount)
1471 return;
1472 }
1473 throw new ConcurrentModificationException();
1474 }
1475
1476 public boolean tryAdvance(Consumer<? super V> action) {
1477 if (action == null)
1478 throw new NullPointerException();
1479 Object[] a = map.table;
1480 int hi = getFence();
1481 while (index < hi) {
1482 Object key = a[index];
1483 @SuppressWarnings("unchecked") V v = (V)a[index+1];
1484 index += 2;
1485 if (key != null) {
1486 action.accept(v);
1487 if (map.modCount != expectedModCount)
1488 throw new ConcurrentModificationException();
1489 return true;
1490 }
1491 }
1492 return false;
1493 }
1494
1495 public int characteristics() {
1496 return (fence < 0 || est == map.size ? SIZED : 0);
1497 }
1498
1499 }
1500
1501 static final class EntrySpliterator<K,V>
1502 extends IdentityHashMapSpliterator<K,V>
1503 implements Spliterator<Map.Entry<K,V>> {
1504 EntrySpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est,
1505 int expectedModCount) {
1506 super(m, origin, fence, est, expectedModCount);
1507 }
1508
1509 public EntrySpliterator<K,V> trySplit() {
1510 int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
1511 return (lo >= mid) ? null :
1512 new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
1513 expectedModCount);
1514 }
1515
1516 public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
1517 if (action == null)
1518 throw new NullPointerException();
1519 int i, hi, mc;
1520 IdentityHashMap<K,V> m; Object[] a;
1521 if ((m = map) != null && (a = m.table) != null &&
1522 (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
1523 for (; i < hi; i += 2) {
1524 Object key = a[i];
1525 if (key != null) {
1526 @SuppressWarnings("unchecked") K k =
1527 (K)unmaskNull(key);
1528 @SuppressWarnings("unchecked") V v = (V)a[i+1];
1529 action.accept
1530 (new AbstractMap.SimpleImmutableEntry<>(k, v));
1531
1532 }
1533 }
1534 if (m.modCount == expectedModCount)
1535 return;
1536 }
1537 throw new ConcurrentModificationException();
1538 }
1539
1540 public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
1541 if (action == null)
1542 throw new NullPointerException();
1543 Object[] a = map.table;
1544 int hi = getFence();
1545 while (index < hi) {
1546 Object key = a[index];
1547 @SuppressWarnings("unchecked") V v = (V)a[index+1];
1548 index += 2;
1549 if (key != null) {
1550 @SuppressWarnings("unchecked") K k =
1551 (K)unmaskNull(key);
1552 action.accept
1553 (new AbstractMap.SimpleImmutableEntry<>(k, v));
1554 if (map.modCount != expectedModCount)
1555 throw new ConcurrentModificationException();
1556 return true;
1557 }
1558 }
1559 return false;
1560 }
1561
1562 public int characteristics() {
1563 return (fence < 0 || est == map.size ? SIZED : 0) | Spliterator.DISTINCT;
1564 }
1565 }
1566
1567 }