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