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