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.io.*;
29 import java.lang.reflect.Array;
30 import java.util.function.BiConsumer;
31 import java.util.function.BiFunction;
32 import java.util.function.Consumer;
33
34 /**
35 * This class implements the <tt>Map</tt> 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 <tt>IdentityHashMap</tt>, two keys
38 * <tt>k1</tt> and <tt>k2</tt> are considered equal if and only if
39 * <tt>(k1==k2)</tt>. (In normal <tt>Map</tt> implementations (like
40 * <tt>HashMap</tt>) two keys <tt>k1</tt> and <tt>k2</tt> are considered equal
41 * if and only if <tt>(k1==null ? k2==null : k1.equals(k2))</tt>.)
42 *
43 * <p><b>This class is <i>not</i> a general-purpose <tt>Map</tt>
44 * implementation! While this class implements the <tt>Map</tt> interface, it
45 * intentionally violates <tt>Map's</tt> general contract, which mandates the
46 * use of the <tt>equals</tt> 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 * <tt>null</tt> values and the <tt>null</tt> 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 (<tt>get</tt> and <tt>put</tt>), 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 <tt>iterator</tt> 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 <tt>remove</tt> 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 <tt>ConcurrentModificationException</tt> 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}/../technotes/guides/collections/index.html">
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 <tt>expectedMaxSize</tt> is negative
222 */
223 public IdentityHashMap(int expectedMaxSize) {
224 if (expectedMaxSize < 0)
225 throw new IllegalArgumentException("expectedMaxSize is negative: "
226 + expectedMaxSize);
227 init(capacity(expectedMaxSize));
228 }
229
230 /**
231 * Returns the appropriate capacity for the 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. If (3 * expectedMaxSize) is negative, it is assumed
236 * that overflow has occurred, and MAXIMUM_CAPACITY is returned.
237 */
238 private static int capacity(int expectedMaxSize) {
239 // assert expectedMaxSize >= 0;
240 return
241 (expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY :
242 (expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY :
243 Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
244 }
245
246 /**
247 * Initializes object to be an empty map with the specified initial
248 * capacity, which is assumed to be a power of two between
249 * MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
250 */
251 private void init(int initCapacity) {
252 // assert (initCapacity & -initCapacity) == initCapacity; // power of 2
253 // assert initCapacity >= MINIMUM_CAPACITY;
254 // assert initCapacity <= MAXIMUM_CAPACITY;
255
256 table = new Object[2 * initCapacity];
257 }
258
259 /**
260 * Constructs a new identity hash map containing the keys-value mappings
261 * in the specified map.
262 *
263 * @param m the map whose mappings are to be placed into this map
264 * @throws NullPointerException if the specified map is null
265 */
266 public IdentityHashMap(Map<? extends K, ? extends V> m) {
267 // Allow for a bit of growth
268 this((int) ((1 + m.size()) * 1.1));
269 putAll(m);
270 }
271
272 /**
273 * Returns the number of key-value mappings in this identity hash map.
274 *
275 * @return the number of key-value mappings in this map
276 */
277 public int size() {
278 return size;
279 }
280
281 /**
282 * Returns <tt>true</tt> if this identity hash map contains no key-value
283 * mappings.
284 *
285 * @return <tt>true</tt> if this identity hash map contains no key-value
286 * mappings
287 */
288 public boolean isEmpty() {
289 return size == 0;
290 }
291
292 /**
293 * Returns index for Object x.
294 */
295 private static int hash(Object x, int length) {
296 int h = System.identityHashCode(x);
297 // Multiply by -127, and left-shift to use least bit as part of hash
298 return ((h << 1) - (h << 8)) & (length - 1);
299 }
300
301 /**
302 * Circularly traverses table of size len.
303 */
304 private static int nextKeyIndex(int i, int len) {
305 return (i + 2 < len ? i + 2 : 0);
306 }
307
308 /**
309 * Returns the value to which the specified key is mapped,
310 * or {@code null} if this map contains no mapping for the key.
311 *
312 * <p>More formally, if this map contains a mapping from a key
313 * {@code k} to a value {@code v} such that {@code (key == k)},
314 * then this method returns {@code v}; otherwise it returns
315 * {@code null}. (There can be at most one such mapping.)
316 *
317 * <p>A return value of {@code null} does not <i>necessarily</i>
318 * indicate that the map contains no mapping for the key; it's also
319 * possible that the map explicitly maps the key to {@code null}.
320 * The {@link #containsKey containsKey} operation may be used to
321 * distinguish these two cases.
322 *
323 * @see #put(Object, Object)
324 */
325 @SuppressWarnings("unchecked")
326 public V get(Object key) {
327 Object k = maskNull(key);
328 Object[] tab = table;
329 int len = tab.length;
330 int i = hash(k, len);
331 while (true) {
332 Object item = tab[i];
333 if (item == k)
334 return (V) tab[i + 1];
335 if (item == null)
336 return null;
337 i = nextKeyIndex(i, len);
338 }
339 }
340
341 /**
342 * Tests whether the specified object reference is a key in this identity
343 * hash map.
344 *
345 * @param key possible key
346 * @return <code>true</code> if the specified object reference is a key
347 * in this map
348 * @see #containsValue(Object)
349 */
350 public boolean containsKey(Object key) {
351 Object k = maskNull(key);
352 Object[] tab = table;
353 int len = tab.length;
354 int i = hash(k, len);
355 while (true) {
356 Object item = tab[i];
357 if (item == k)
358 return true;
359 if (item == null)
360 return false;
361 i = nextKeyIndex(i, len);
362 }
363 }
364
365 /**
366 * Tests whether the specified object reference is a value in this identity
367 * hash map.
368 *
369 * @param value value whose presence in this map is to be tested
370 * @return <tt>true</tt> if this map maps one or more keys to the
371 * specified object reference
372 * @see #containsKey(Object)
373 */
374 public boolean containsValue(Object value) {
375 Object[] tab = table;
376 for (int i = 1; i < tab.length; i += 2)
377 if (tab[i] == value && tab[i - 1] != null)
378 return true;
379
380 return false;
381 }
382
383 /**
384 * Tests if the specified key-value mapping is in the map.
385 *
386 * @param key possible key
387 * @param value possible value
388 * @return <code>true</code> if and only if the specified key-value
389 * mapping is in the map
390 */
391 private boolean containsMapping(Object key, Object value) {
392 Object k = maskNull(key);
393 Object[] tab = table;
394 int len = tab.length;
395 int i = hash(k, len);
396 while (true) {
397 Object item = tab[i];
398 if (item == k)
399 return tab[i + 1] == value;
400 if (item == null)
401 return false;
402 i = nextKeyIndex(i, len);
403 }
404 }
405
406 /**
407 * Associates the specified value with the specified key in this identity
408 * hash map. If the map previously contained a mapping for the key, the
409 * old value is replaced.
410 *
411 * @param key the key with which the specified value is to be associated
412 * @param value the value to be associated with the specified key
413 * @return the previous value associated with <tt>key</tt>, or
414 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
415 * (A <tt>null</tt> return can also indicate that the map
416 * previously associated <tt>null</tt> with <tt>key</tt>.)
417 * @see Object#equals(Object)
418 * @see #get(Object)
419 * @see #containsKey(Object)
420 */
421 public V put(K key, V value) {
422 Object k = maskNull(key);
423 Object[] tab = table;
424 int len = tab.length;
425 int i = hash(k, len);
426
427 Object item;
428 while ( (item = tab[i]) != null) {
429 if (item == k) {
430 @SuppressWarnings("unchecked")
431 V oldValue = (V) tab[i + 1];
432 tab[i + 1] = value;
433 return oldValue;
434 }
435 i = nextKeyIndex(i, len);
436 }
437
438 if (size == MAXIMUM_CAPACITY - 1)
439 throw new IllegalStateException("Capacity exhausted.");
440
441 if (size >= len / 3 && resize(len)) { // len == 2 * current capacity.
442 tab = table;
443 len = tab.length;
444 i = hash(key, len);
445 while (tab[i] != null)
446 i = nextKeyIndex(i, len);
447 }
448 modCount++;
449 tab[i] = k;
450 tab[i + 1] = value;
451 size++;
452 return null;
453 }
454
455 /**
456 * Resize the table to hold given capacity.
457 *
458 * @param newCapacity the new capacity, must be a power of two.
459 */
460 private boolean resize(int newCapacity) {
461 // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
462 int newLength = newCapacity * 2;
463
464 Object[] oldTable = table;
465 int oldLength = oldTable.length;
466 if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
467 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 > table.length / 3) // conservatively pre-expand
504 resize(capacity(n));
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 <tt>key</tt>, or
515 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
516 * (A <tt>null</tt> return can also indicate that the map
517 * previously associated <tt>null</tt> with <tt>key</tt>.)
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</code> 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 * <tt>true</tt> 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 <tt>m</tt> if and only if
628 * <tt>this.entrySet().equals(m.entrySet())</tt>.
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 * <tt>Object.equals</tt> contract may be violated if this map is compared
633 * to a normal map. However, the <tt>Object.equals</tt> contract is
634 * guaranteed to hold among <tt>IdentityHashMap</tt> instances.</b>
635 *
636 * @param o object to be compared for equality with this map
637 * @return <tt>true</tt> 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 * <tt>entrySet()</tt> view. This ensures that <tt>m1.equals(m2)</tt>
667 * implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two
668 * <tt>IdentityHashMap</tt> instances <tt>m1</tt> and <tt>m2</tt>, 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 * <tt>Map.Entry</tt> instances in the set returned by this map's
673 * <tt>entrySet</tt> method, it is possible that the contractual
674 * requirement of <tt>Object.hashCode</tt> mentioned in the previous
675 * paragraph will be violated if one of the two objects being compared is
676 * an <tt>IdentityHashMap</tt> 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 <tt>Iterator.remove</tt>,
935 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
936 * <tt>clear</tt> methods. It does not support the <tt>add</tt> or
937 * <tt>addAll</tt> methods.
938 *
939 * <p><b>While the object returned by this method implements the
940 * <tt>Set</tt> interface, it does <i>not</i> obey <tt>Set's</tt> 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 <tt>contains</tt>,
944 * <tt>remove</tt>, <tt>containsAll</tt>, <tt>equals</tt>, and
945 * <tt>hashCode</tt> methods.</b>
946 *
947 * <p><b>The <tt>equals</tt> method of the returned set returns <tt>true</tt>
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 <tt>Object.equals</tt> contract may be violated if
951 * the set returned by this method is compared to a normal set. However,
952 * the <tt>Object.equals</tt> contract is guaranteed to hold among sets
953 * returned by this method.</b>
954 *
955 * <p>The <tt>hashCode</tt> 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 <tt>equals</tt> method, in order to enforce the
959 * general contract of the <tt>Object.hashCode</tt> 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 return ks;
970 else
971 return keySet = new KeySet();
972 }
973
974 private class KeySet extends AbstractSet<K> {
975 public Iterator<K> iterator() {
976 return new KeyIterator();
977 }
978 public int size() {
979 return size;
980 }
981 public boolean contains(Object o) {
982 return containsKey(o);
983 }
984 public boolean remove(Object o) {
985 int oldSize = size;
986 IdentityHashMap.this.remove(o);
987 return size != oldSize;
988 }
989 /*
990 * Must revert from AbstractSet's impl to AbstractCollection's, as
991 * the former contains an optimization that results in incorrect
992 * behavior when c is a smaller "normal" (non-identity-based) Set.
993 */
994 public boolean removeAll(Collection<?> c) {
995 Objects.requireNonNull(c);
996 boolean modified = false;
997 for (Iterator<K> i = iterator(); i.hasNext(); ) {
998 if (c.contains(i.next())) {
999 i.remove();
1000 modified = true;
1001 }
1002 }
1003 return modified;
1004 }
1005 public void clear() {
1006 IdentityHashMap.this.clear();
1007 }
1008 public int hashCode() {
1009 int result = 0;
1010 for (K key : this)
1011 result += System.identityHashCode(key);
1012 return result;
1013 }
1014 public Object[] toArray() {
1015 return toArray(new Object[0]);
1016 }
1017 @SuppressWarnings("unchecked")
1018 public <T> T[] toArray(T[] a) {
1019 int expectedModCount = modCount;
1020 int size = size();
1021 if (a.length < size)
1022 a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
1023 Object[] tab = table;
1024 int ti = 0;
1025 for (int si = 0; si < tab.length; si += 2) {
1026 Object key;
1027 if ((key = tab[si]) != null) { // key present ?
1028 // more elements than expected -> concurrent modification from other thread
1029 if (ti >= size) {
1030 throw new ConcurrentModificationException();
1031 }
1032 a[ti++] = (T) unmaskNull(key); // unmask key
1033 }
1034 }
1035 // fewer elements than expected or concurrent modification from other thread detected
1036 if (ti < size || expectedModCount != modCount) {
1037 throw new ConcurrentModificationException();
1038 }
1039 // final null marker as per spec
1040 if (ti < a.length) {
1041 a[ti] = null;
1042 }
1043 return a;
1044 }
1045
1046 public Spliterator<K> spliterator() {
1047 return new KeySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
1048 }
1049 }
1050
1051 /**
1052 * Returns a {@link Collection} view of the values contained in this map.
1053 * The collection is backed by the map, so changes to the map are
1054 * reflected in the collection, and vice-versa. If the map is
1055 * modified while an iteration over the collection is in progress,
1056 * the results of the iteration are undefined. The collection
1057 * supports element removal, which removes the corresponding
1058 * mapping from the map, via the <tt>Iterator.remove</tt>,
1059 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1060 * <tt>retainAll</tt> and <tt>clear</tt> methods. It does not
1061 * support the <tt>add</tt> or <tt>addAll</tt> methods.
1062 *
1063 * <p><b>While the object returned by this method implements the
1064 * <tt>Collection</tt> interface, it does <i>not</i> obey
1065 * <tt>Collection's</tt> general contract. Like its backing map,
1066 * the collection returned by this method defines element equality as
1067 * reference-equality rather than object-equality. This affects the
1068 * behavior of its <tt>contains</tt>, <tt>remove</tt> and
1069 * <tt>containsAll</tt> methods.</b>
1070 */
1071 public Collection<V> values() {
1072 Collection<V> vs = values;
1073 if (vs != null)
1074 return vs;
1075 else
1076 return values = new Values();
1077 }
1078
1079 private class Values extends AbstractCollection<V> {
1080 public Iterator<V> iterator() {
1081 return new ValueIterator();
1082 }
1083 public int size() {
1084 return size;
1085 }
1086 public boolean contains(Object o) {
1087 return containsValue(o);
1088 }
1089 public boolean remove(Object o) {
1090 for (Iterator<V> i = iterator(); i.hasNext(); ) {
1091 if (i.next() == o) {
1092 i.remove();
1093 return true;
1094 }
1095 }
1096 return false;
1097 }
1098 public void clear() {
1099 IdentityHashMap.this.clear();
1100 }
1101 public Object[] toArray() {
1102 return toArray(new Object[0]);
1103 }
1104 @SuppressWarnings("unchecked")
1105 public <T> T[] toArray(T[] a) {
1106 int expectedModCount = modCount;
1107 int size = size();
1108 if (a.length < size)
1109 a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
1110 Object[] tab = table;
1111 int ti = 0;
1112 for (int si = 0; si < tab.length; si += 2) {
1113 if (tab[si] != null) { // key present ?
1114 // more elements than expected -> concurrent modification from other thread
1115 if (ti >= size) {
1116 throw new ConcurrentModificationException();
1117 }
1118 a[ti++] = (T) tab[si+1]; // copy value
1119 }
1120 }
1121 // fewer elements than expected or concurrent modification from other thread detected
1122 if (ti < size || expectedModCount != modCount) {
1123 throw new ConcurrentModificationException();
1124 }
1125 // final null marker as per spec
1126 if (ti < a.length) {
1127 a[ti] = null;
1128 }
1129 return a;
1130 }
1131
1132 public Spliterator<V> spliterator() {
1133 return new ValueSpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
1134 }
1135 }
1136
1137 /**
1138 * Returns a {@link Set} view of the mappings contained in this map.
1139 * Each element in the returned set is a reference-equality-based
1140 * <tt>Map.Entry</tt>. The set is backed by the map, so changes
1141 * to the map are reflected in the set, and vice-versa. If the
1142 * map is modified while an iteration over the set is in progress,
1143 * the results of the iteration are undefined. The set supports
1144 * element removal, which removes the corresponding mapping from
1145 * the map, via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1146 * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
1147 * methods. It does not support the <tt>add</tt> or
1148 * <tt>addAll</tt> methods.
1149 *
1150 * <p>Like the backing map, the <tt>Map.Entry</tt> objects in the set
1151 * returned by this method define key and value equality as
1152 * reference-equality rather than object-equality. This affects the
1153 * behavior of the <tt>equals</tt> and <tt>hashCode</tt> methods of these
1154 * <tt>Map.Entry</tt> objects. A reference-equality based <tt>Map.Entry
1155 * e</tt> is equal to an object <tt>o</tt> if and only if <tt>o</tt> is a
1156 * <tt>Map.Entry</tt> and <tt>e.getKey()==o.getKey() &&
1157 * e.getValue()==o.getValue()</tt>. To accommodate these equals
1158 * semantics, the <tt>hashCode</tt> method returns
1159 * <tt>System.identityHashCode(e.getKey()) ^
1160 * System.identityHashCode(e.getValue())</tt>.
1161 *
1162 * <p><b>Owing to the reference-equality-based semantics of the
1163 * <tt>Map.Entry</tt> instances in the set returned by this method,
1164 * it is possible that the symmetry and transitivity requirements of
1165 * the {@link Object#equals(Object)} contract may be violated if any of
1166 * the entries in the set is compared to a normal map entry, or if
1167 * the set returned by this method is compared to a set of normal map
1168 * entries (such as would be returned by a call to this method on a normal
1169 * map). However, the <tt>Object.equals</tt> contract is guaranteed to
1170 * hold among identity-based map entries, and among sets of such entries.
1171 * </b>
1172 *
1173 * @return a set view of the identity-mappings contained in this map
1174 */
1175 public Set<Map.Entry<K,V>> entrySet() {
1176 Set<Map.Entry<K,V>> es = entrySet;
1177 if (es != null)
1178 return es;
1179 else
1180 return entrySet = new EntrySet();
1181 }
1182
1183 private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1184 public Iterator<Map.Entry<K,V>> iterator() {
1185 return new EntryIterator();
1186 }
1187 public boolean contains(Object o) {
1188 if (!(o instanceof Map.Entry))
1189 return false;
1190 Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
1191 return containsMapping(entry.getKey(), entry.getValue());
1192 }
1193 public boolean remove(Object o) {
1194 if (!(o instanceof Map.Entry))
1195 return false;
1196 Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
1197 return removeMapping(entry.getKey(), entry.getValue());
1198 }
1199 public int size() {
1200 return size;
1201 }
1202 public void clear() {
1203 IdentityHashMap.this.clear();
1204 }
1205 /*
1206 * Must revert from AbstractSet's impl to AbstractCollection's, as
1207 * the former contains an optimization that results in incorrect
1208 * behavior when c is a smaller "normal" (non-identity-based) Set.
1209 */
1210 public boolean removeAll(Collection<?> c) {
1211 Objects.requireNonNull(c);
1212 boolean modified = false;
1213 for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); ) {
1214 if (c.contains(i.next())) {
1215 i.remove();
1216 modified = true;
1217 }
1218 }
1219 return modified;
1220 }
1221
1222 public Object[] toArray() {
1223 return toArray(new Object[0]);
1224 }
1225
1226 @SuppressWarnings("unchecked")
1227 public <T> T[] toArray(T[] a) {
1228 int expectedModCount = modCount;
1229 int size = size();
1230 if (a.length < size)
1231 a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
1232 Object[] tab = table;
1233 int ti = 0;
1234 for (int si = 0; si < tab.length; si += 2) {
1235 Object key;
1236 if ((key = tab[si]) != null) { // key present ?
1237 // more elements than expected -> concurrent modification from other thread
1238 if (ti >= size) {
1239 throw new ConcurrentModificationException();
1240 }
1241 a[ti++] = (T) new AbstractMap.SimpleEntry<>(unmaskNull(key), tab[si + 1]);
1242 }
1243 }
1244 // fewer elements than expected or concurrent modification from other thread detected
1245 if (ti < size || expectedModCount != modCount) {
1246 throw new ConcurrentModificationException();
1247 }
1248 // final null marker as per spec
1249 if (ti < a.length) {
1250 a[ti] = null;
1251 }
1252 return a;
1253 }
1254
1255 public Spliterator<Map.Entry<K,V>> spliterator() {
1256 return new EntrySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
1257 }
1258 }
1259
1260
1261 private static final long serialVersionUID = 8188218128353913216L;
1262
1263 /**
1264 * Save the state of the <tt>IdentityHashMap</tt> instance to a stream
1265 * (i.e., serialize it).
1266 *
1267 * @serialData The <i>size</i> of the HashMap (the number of key-value
1268 * mappings) (<tt>int</tt>), followed by the key (Object) and
1269 * value (Object) for each key-value mapping represented by the
1270 * IdentityHashMap. The key-value mappings are emitted in no
1271 * particular order.
1272 */
1273 private void writeObject(java.io.ObjectOutputStream s)
1274 throws java.io.IOException {
1275 // Write out and any hidden stuff
1276 s.defaultWriteObject();
1277
1278 // Write out size (number of Mappings)
1279 s.writeInt(size);
1280
1281 // Write out keys and values (alternating)
1282 Object[] tab = table;
1283 for (int i = 0; i < tab.length; i += 2) {
1284 Object key = tab[i];
1285 if (key != null) {
1286 s.writeObject(unmaskNull(key));
1287 s.writeObject(tab[i + 1]);
1288 }
1289 }
1290 }
1291
1292 /**
1293 * Reconstitute the <tt>IdentityHashMap</tt> instance from a stream (i.e.,
1294 * deserialize it).
1295 */
1296 private void readObject(java.io.ObjectInputStream s)
1297 throws java.io.IOException, ClassNotFoundException {
1298 // Read in any hidden stuff
1299 s.defaultReadObject();
1300
1301 // Read in size (number of Mappings)
1302 int size = s.readInt();
1303
1304 init(capacity(size));
1305
1306 // Read the keys and values, and put the mappings in the table
1307 for (int i=0; i<size; i++) {
1308 @SuppressWarnings("unchecked")
1309 K key = (K) s.readObject();
1310 @SuppressWarnings("unchecked")
1311 V value = (V) s.readObject();
1312 putForCreate(key, value);
1313 }
1314 }
1315
1316 /**
1317 * The put method for readObject. It does not resize the table,
1318 * update modCount, etc.
1319 */
1320 private void putForCreate(K key, V value)
1321 throws IOException
1322 {
1323 Object k = maskNull(key);
1324 Object[] tab = table;
1325 int len = tab.length;
1326 int i = hash(k, len);
1327
1328 Object item;
1329 while ( (item = tab[i]) != null) {
1330 if (item == k)
1331 throw new java.io.StreamCorruptedException();
1332 i = nextKeyIndex(i, len);
1333 }
1334 tab[i] = k;
1335 tab[i + 1] = value;
1336 }
1337
1338 @SuppressWarnings("unchecked")
1339 @Override
1340 public void forEach(BiConsumer<? super K, ? super V> action) {
1341 Objects.requireNonNull(action);
1342 int expectedModCount = modCount;
1343
1344 Object[] t = table;
1345 for (int index = 0; index < t.length; index += 2) {
1346 Object k = t[index];
1347 if (k != null) {
1348 action.accept((K) unmaskNull(k), (V) t[index + 1]);
1349 }
1350
1351 if (modCount != expectedModCount) {
1352 throw new ConcurrentModificationException();
1353 }
1354 }
1355 }
1356
1357 @SuppressWarnings("unchecked")
1358 @Override
1359 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1360 Objects.requireNonNull(function);
1361 int expectedModCount = modCount;
1362
1363 Object[] t = table;
1364 for (int index = 0; index < t.length; index += 2) {
1365 Object k = t[index];
1366 if (k != null) {
1367 t[index + 1] = function.apply((K) unmaskNull(k), (V) t[index + 1]);
1368 }
1369
1370 if (modCount != expectedModCount) {
1371 throw new ConcurrentModificationException();
1372 }
1373 }
1374 }
1375
1376 /**
1377 * Similar form as array-based Spliterators, but skips blank elements,
1378 * and guestimates size as decreasing by half per split.
1379 */
1380 static class IdentityHashMapSpliterator<K,V> {
1381 final IdentityHashMap<K,V> map;
1382 int index; // current index, modified on advance/split
1383 int fence; // -1 until first use; then one past last index
1384 int est; // size estimate
1385 int expectedModCount; // initialized when fence set
1386
1387 IdentityHashMapSpliterator(IdentityHashMap<K,V> map, int origin,
1388 int fence, int est, int expectedModCount) {
1389 this.map = map;
1390 this.index = origin;
1391 this.fence = fence;
1392 this.est = est;
1393 this.expectedModCount = expectedModCount;
1394 }
1395
1396 final int getFence() { // initialize fence and size on first use
1397 int hi;
1398 if ((hi = fence) < 0) {
1399 est = map.size;
1400 expectedModCount = map.modCount;
1401 hi = fence = map.table.length;
1402 }
1403 return hi;
1404 }
1405
1406 public final long estimateSize() {
1407 getFence(); // force init
1408 return (long) est;
1409 }
1410 }
1411
1412 static final class KeySpliterator<K,V>
1413 extends IdentityHashMapSpliterator<K,V>
1414 implements Spliterator<K> {
1415 KeySpliterator(IdentityHashMap<K,V> map, int origin, int fence, int est,
1416 int expectedModCount) {
1417 super(map, origin, fence, est, expectedModCount);
1418 }
1419
1420 public KeySpliterator<K,V> trySplit() {
1421 int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
1422 return (lo >= mid) ? null :
1423 new KeySpliterator<>(map, lo, index = mid, est >>>= 1,
1424 expectedModCount);
1425 }
1426
1427 @SuppressWarnings("unchecked")
1428 public void forEachRemaining(Consumer<? super K> action) {
1429 if (action == null)
1430 throw new NullPointerException();
1431 int i, hi, mc; Object key;
1432 IdentityHashMap<K,V> m; Object[] a;
1433 if ((m = map) != null && (a = m.table) != null &&
1434 (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
1435 for (; i < hi; i += 2) {
1436 if ((key = a[i]) != null)
1437 action.accept((K)unmaskNull(key));
1438 }
1439 if (m.modCount == expectedModCount)
1440 return;
1441 }
1442 throw new ConcurrentModificationException();
1443 }
1444
1445 @SuppressWarnings("unchecked")
1446 public boolean tryAdvance(Consumer<? super K> action) {
1447 if (action == null)
1448 throw new NullPointerException();
1449 Object[] a = map.table;
1450 int hi = getFence();
1451 while (index < hi) {
1452 Object key = a[index];
1453 index += 2;
1454 if (key != null) {
1455 action.accept((K)unmaskNull(key));
1456 if (map.modCount != expectedModCount)
1457 throw new ConcurrentModificationException();
1458 return true;
1459 }
1460 }
1461 return false;
1462 }
1463
1464 public int characteristics() {
1465 return (fence < 0 || est == map.size ? SIZED : 0) | Spliterator.DISTINCT;
1466 }
1467 }
1468
1469 static final class ValueSpliterator<K,V>
1470 extends IdentityHashMapSpliterator<K,V>
1471 implements Spliterator<V> {
1472 ValueSpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est,
1473 int expectedModCount) {
1474 super(m, origin, fence, est, expectedModCount);
1475 }
1476
1477 public ValueSpliterator<K,V> trySplit() {
1478 int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
1479 return (lo >= mid) ? null :
1480 new ValueSpliterator<>(map, lo, index = mid, est >>>= 1,
1481 expectedModCount);
1482 }
1483
1484 public void forEachRemaining(Consumer<? super V> action) {
1485 if (action == null)
1486 throw new NullPointerException();
1487 int i, hi, mc;
1488 IdentityHashMap<K,V> m; Object[] a;
1489 if ((m = map) != null && (a = m.table) != null &&
1490 (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
1491 for (; i < hi; i += 2) {
1492 if (a[i] != null) {
1493 @SuppressWarnings("unchecked") V v = (V)a[i+1];
1494 action.accept(v);
1495 }
1496 }
1497 if (m.modCount == expectedModCount)
1498 return;
1499 }
1500 throw new ConcurrentModificationException();
1501 }
1502
1503 public boolean tryAdvance(Consumer<? super V> action) {
1504 if (action == null)
1505 throw new NullPointerException();
1506 Object[] a = map.table;
1507 int hi = getFence();
1508 while (index < hi) {
1509 Object key = a[index];
1510 @SuppressWarnings("unchecked") V v = (V)a[index+1];
1511 index += 2;
1512 if (key != null) {
1513 action.accept(v);
1514 if (map.modCount != expectedModCount)
1515 throw new ConcurrentModificationException();
1516 return true;
1517 }
1518 }
1519 return false;
1520 }
1521
1522 public int characteristics() {
1523 return (fence < 0 || est == map.size ? SIZED : 0);
1524 }
1525
1526 }
1527
1528 static final class EntrySpliterator<K,V>
1529 extends IdentityHashMapSpliterator<K,V>
1530 implements Spliterator<Map.Entry<K,V>> {
1531 EntrySpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est,
1532 int expectedModCount) {
1533 super(m, origin, fence, est, expectedModCount);
1534 }
1535
1536 public EntrySpliterator<K,V> trySplit() {
1537 int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
1538 return (lo >= mid) ? null :
1539 new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
1540 expectedModCount);
1541 }
1542
1543 public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
1544 if (action == null)
1545 throw new NullPointerException();
1546 int i, hi, mc;
1547 IdentityHashMap<K,V> m; Object[] a;
1548 if ((m = map) != null && (a = m.table) != null &&
1549 (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
1550 for (; i < hi; i += 2) {
1551 Object key = a[i];
1552 if (key != null) {
1553 @SuppressWarnings("unchecked") K k =
1554 (K)unmaskNull(key);
1555 @SuppressWarnings("unchecked") V v = (V)a[i+1];
1556 action.accept
1557 (new AbstractMap.SimpleImmutableEntry<>(k, v));
1558
1559 }
1560 }
1561 if (m.modCount == expectedModCount)
1562 return;
1563 }
1564 throw new ConcurrentModificationException();
1565 }
1566
1567 public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
1568 if (action == null)
1569 throw new NullPointerException();
1570 Object[] a = map.table;
1571 int hi = getFence();
1572 while (index < hi) {
1573 Object key = a[index];
1574 @SuppressWarnings("unchecked") V v = (V)a[index+1];
1575 index += 2;
1576 if (key != null) {
1577 @SuppressWarnings("unchecked") K k =
1578 (K)unmaskNull(key);
1579 action.accept
1580 (new AbstractMap.SimpleImmutableEntry<>(k, v));
1581 if (map.modCount != expectedModCount)
1582 throw new ConcurrentModificationException();
1583 return true;
1584 }
1585 }
1586 return false;
1587 }
1588
1589 public int characteristics() {
1590 return (fence < 0 || est == map.size ? SIZED : 0) | Spliterator.DISTINCT;
1591 }
1592 }
1593
1594 }