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