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