--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/src/java.base/share/classes/java/util/IdentityHashMap.java Sun Aug 17 15:54:13 2014 +0100
@@ -0,0 +1,1595 @@
+/*
+ * Copyright (c) 2000, 2014, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation. Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+package java.util;
+
+import java.lang.reflect.Array;
+import java.util.function.BiConsumer;
+import java.util.function.BiFunction;
+import java.util.function.Consumer;
+
+/**
+ * This class implements the <tt>Map</tt> interface with a hash table, using
+ * reference-equality in place of object-equality when comparing keys (and
+ * values). In other words, in an <tt>IdentityHashMap</tt>, two keys
+ * <tt>k1</tt> and <tt>k2</tt> are considered equal if and only if
+ * <tt>(k1==k2)</tt>. (In normal <tt>Map</tt> implementations (like
+ * <tt>HashMap</tt>) two keys <tt>k1</tt> and <tt>k2</tt> are considered equal
+ * if and only if <tt>(k1==null ? k2==null : k1.equals(k2))</tt>.)
+ *
+ * <p><b>This class is <i>not</i> a general-purpose <tt>Map</tt>
+ * implementation! While this class implements the <tt>Map</tt> interface, it
+ * intentionally violates <tt>Map's</tt> general contract, which mandates the
+ * use of the <tt>equals</tt> method when comparing objects. This class is
+ * designed for use only in the rare cases wherein reference-equality
+ * semantics are required.</b>
+ *
+ * <p>A typical use of this class is <i>topology-preserving object graph
+ * transformations</i>, such as serialization or deep-copying. To perform such
+ * a transformation, a program must maintain a "node table" that keeps track
+ * of all the object references that have already been processed. The node
+ * table must not equate distinct objects even if they happen to be equal.
+ * Another typical use of this class is to maintain <i>proxy objects</i>. For
+ * example, a debugging facility might wish to maintain a proxy object for
+ * each object in the program being debugged.
+ *
+ * <p>This class provides all of the optional map operations, and permits
+ * <tt>null</tt> values and the <tt>null</tt> key. This class makes no
+ * guarantees as to the order of the map; in particular, it does not guarantee
+ * that the order will remain constant over time.
+ *
+ * <p>This class provides constant-time performance for the basic
+ * operations (<tt>get</tt> and <tt>put</tt>), assuming the system
+ * identity hash function ({@link System#identityHashCode(Object)})
+ * disperses elements properly among the buckets.
+ *
+ * <p>This class has one tuning parameter (which affects performance but not
+ * semantics): <i>expected maximum size</i>. This parameter is the maximum
+ * number of key-value mappings that the map is expected to hold. Internally,
+ * this parameter is used to determine the number of buckets initially
+ * comprising the hash table. The precise relationship between the expected
+ * maximum size and the number of buckets is unspecified.
+ *
+ * <p>If the size of the map (the number of key-value mappings) sufficiently
+ * exceeds the expected maximum size, the number of buckets is increased.
+ * Increasing the number of buckets ("rehashing") may be fairly expensive, so
+ * it pays to create identity hash maps with a sufficiently large expected
+ * maximum size. On the other hand, iteration over collection views requires
+ * time proportional to the number of buckets in the hash table, so it
+ * pays not to set the expected maximum size too high if you are especially
+ * concerned with iteration performance or memory usage.
+ *
+ * <p><strong>Note that this implementation is not synchronized.</strong>
+ * If multiple threads access an identity hash map concurrently, and at
+ * least one of the threads modifies the map structurally, it <i>must</i>
+ * be synchronized externally. (A structural modification is any operation
+ * that adds or deletes one or more mappings; merely changing the value
+ * associated with a key that an instance already contains is not a
+ * structural modification.) This is typically accomplished by
+ * synchronizing on some object that naturally encapsulates the map.
+ *
+ * If no such object exists, the map should be "wrapped" using the
+ * {@link Collections#synchronizedMap Collections.synchronizedMap}
+ * method. This is best done at creation time, to prevent accidental
+ * unsynchronized access to the map:<pre>
+ * Map m = Collections.synchronizedMap(new IdentityHashMap(...));</pre>
+ *
+ * <p>The iterators returned by the <tt>iterator</tt> method of the
+ * collections returned by all of this class's "collection view
+ * methods" are <i>fail-fast</i>: if the map is structurally modified
+ * at any time after the iterator is created, in any way except
+ * through the iterator's own <tt>remove</tt> method, the iterator
+ * will throw a {@link ConcurrentModificationException}. Thus, in the
+ * face of concurrent modification, the iterator fails quickly and
+ * cleanly, rather than risking arbitrary, non-deterministic behavior
+ * at an undetermined time in the future.
+ *
+ * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
+ * as it is, generally speaking, impossible to make any hard guarantees in the
+ * presence of unsynchronized concurrent modification. Fail-fast iterators
+ * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
+ * Therefore, it would be wrong to write a program that depended on this
+ * exception for its correctness: <i>fail-fast iterators should be used only
+ * to detect bugs.</i>
+ *
+ * <p>Implementation note: This is a simple <i>linear-probe</i> hash table,
+ * as described for example in texts by Sedgewick and Knuth. The array
+ * alternates holding keys and values. (This has better locality for large
+ * tables than does using separate arrays.) For many JRE implementations
+ * and operation mixes, this class will yield better performance than
+ * {@link HashMap} (which uses <i>chaining</i> rather than linear-probing).
+ *
+ * <p>This class is a member of the
+ * <a href="{@docRoot}/../technotes/guides/collections/index.html">
+ * Java Collections Framework</a>.
+ *
+ * @see System#identityHashCode(Object)
+ * @see Object#hashCode()
+ * @see Collection
+ * @see Map
+ * @see HashMap
+ * @see TreeMap
+ * @author Doug Lea and Josh Bloch
+ * @since 1.4
+ */
+
+public class IdentityHashMap<K,V>
+ extends AbstractMap<K,V>
+ implements Map<K,V>, java.io.Serializable, Cloneable
+{
+ /**
+ * The initial capacity used by the no-args constructor.
+ * MUST be a power of two. The value 32 corresponds to the
+ * (specified) expected maximum size of 21, given a load factor
+ * of 2/3.
+ */
+ private static final int DEFAULT_CAPACITY = 32;
+
+ /**
+ * The minimum capacity, used if a lower value is implicitly specified
+ * by either of the constructors with arguments. The value 4 corresponds
+ * to an expected maximum size of 2, given a load factor of 2/3.
+ * MUST be a power of two.
+ */
+ private static final int MINIMUM_CAPACITY = 4;
+
+ /**
+ * The maximum capacity, used if a higher value is implicitly specified
+ * by either of the constructors with arguments.
+ * MUST be a power of two <= 1<<29.
+ *
+ * In fact, the map can hold no more than MAXIMUM_CAPACITY-1 items
+ * because it has to have at least one slot with the key == null
+ * in order to avoid infinite loops in get(), put(), remove()
+ */
+ private static final int MAXIMUM_CAPACITY = 1 << 29;
+
+ /**
+ * The table, resized as necessary. Length MUST always be a power of two.
+ */
+ transient Object[] table; // non-private to simplify nested class access
+
+ /**
+ * The number of key-value mappings contained in this identity hash map.
+ *
+ * @serial
+ */
+ int size;
+
+ /**
+ * The number of modifications, to support fast-fail iterators
+ */
+ transient int modCount;
+
+ /**
+ * Value representing null keys inside tables.
+ */
+ static final Object NULL_KEY = new Object();
+
+ /**
+ * Use NULL_KEY for key if it is null.
+ */
+ private static Object maskNull(Object key) {
+ return (key == null ? NULL_KEY : key);
+ }
+
+ /**
+ * Returns internal representation of null key back to caller as null.
+ */
+ static final Object unmaskNull(Object key) {
+ return (key == NULL_KEY ? null : key);
+ }
+
+ /**
+ * Constructs a new, empty identity hash map with a default expected
+ * maximum size (21).
+ */
+ public IdentityHashMap() {
+ init(DEFAULT_CAPACITY);
+ }
+
+ /**
+ * Constructs a new, empty map with the specified expected maximum size.
+ * Putting more than the expected number of key-value mappings into
+ * the map may cause the internal data structure to grow, which may be
+ * somewhat time-consuming.
+ *
+ * @param expectedMaxSize the expected maximum size of the map
+ * @throws IllegalArgumentException if <tt>expectedMaxSize</tt> is negative
+ */
+ public IdentityHashMap(int expectedMaxSize) {
+ if (expectedMaxSize < 0)
+ throw new IllegalArgumentException("expectedMaxSize is negative: "
+ + expectedMaxSize);
+ init(capacity(expectedMaxSize));
+ }
+
+ /**
+ * Returns the appropriate capacity for the given expected maximum size.
+ * Returns the smallest power of two between MINIMUM_CAPACITY and
+ * MAXIMUM_CAPACITY, inclusive, that is greater than (3 *
+ * expectedMaxSize)/2, if such a number exists. Otherwise returns
+ * MAXIMUM_CAPACITY.
+ */
+ private static int capacity(int expectedMaxSize) {
+ // assert expectedMaxSize >= 0;
+ return
+ (expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY :
+ (expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY :
+ Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
+ }
+
+ /**
+ * Initializes object to be an empty map with the specified initial
+ * capacity, which is assumed to be a power of two between
+ * MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
+ */
+ private void init(int initCapacity) {
+ // assert (initCapacity & -initCapacity) == initCapacity; // power of 2
+ // assert initCapacity >= MINIMUM_CAPACITY;
+ // assert initCapacity <= MAXIMUM_CAPACITY;
+
+ table = new Object[2 * initCapacity];
+ }
+
+ /**
+ * Constructs a new identity hash map containing the keys-value mappings
+ * in the specified map.
+ *
+ * @param m the map whose mappings are to be placed into this map
+ * @throws NullPointerException if the specified map is null
+ */
+ public IdentityHashMap(Map<? extends K, ? extends V> m) {
+ // Allow for a bit of growth
+ this((int) ((1 + m.size()) * 1.1));
+ putAll(m);
+ }
+
+ /**
+ * Returns the number of key-value mappings in this identity hash map.
+ *
+ * @return the number of key-value mappings in this map
+ */
+ public int size() {
+ return size;
+ }
+
+ /**
+ * Returns <tt>true</tt> if this identity hash map contains no key-value
+ * mappings.
+ *
+ * @return <tt>true</tt> if this identity hash map contains no key-value
+ * mappings
+ */
+ public boolean isEmpty() {
+ return size == 0;
+ }
+
+ /**
+ * Returns index for Object x.
+ */
+ private static int hash(Object x, int length) {
+ int h = System.identityHashCode(x);
+ // Multiply by -127, and left-shift to use least bit as part of hash
+ return ((h << 1) - (h << 8)) & (length - 1);
+ }
+
+ /**
+ * Circularly traverses table of size len.
+ */
+ private static int nextKeyIndex(int i, int len) {
+ return (i + 2 < len ? i + 2 : 0);
+ }
+
+ /**
+ * Returns the value to which the specified key is mapped,
+ * or {@code null} if this map contains no mapping for the key.
+ *
+ * <p>More formally, if this map contains a mapping from a key
+ * {@code k} to a value {@code v} such that {@code (key == k)},
+ * then this method returns {@code v}; otherwise it returns
+ * {@code null}. (There can be at most one such mapping.)
+ *
+ * <p>A return value of {@code null} does not <i>necessarily</i>
+ * indicate that the map contains no mapping for the key; it's also
+ * possible that the map explicitly maps the key to {@code null}.
+ * The {@link #containsKey containsKey} operation may be used to
+ * distinguish these two cases.
+ *
+ * @see #put(Object, Object)
+ */
+ @SuppressWarnings("unchecked")
+ public V get(Object key) {
+ Object k = maskNull(key);
+ Object[] tab = table;
+ int len = tab.length;
+ int i = hash(k, len);
+ while (true) {
+ Object item = tab[i];
+ if (item == k)
+ return (V) tab[i + 1];
+ if (item == null)
+ return null;
+ i = nextKeyIndex(i, len);
+ }
+ }
+
+ /**
+ * Tests whether the specified object reference is a key in this identity
+ * hash map.
+ *
+ * @param key possible key
+ * @return <code>true</code> if the specified object reference is a key
+ * in this map
+ * @see #containsValue(Object)
+ */
+ public boolean containsKey(Object key) {
+ Object k = maskNull(key);
+ Object[] tab = table;
+ int len = tab.length;
+ int i = hash(k, len);
+ while (true) {
+ Object item = tab[i];
+ if (item == k)
+ return true;
+ if (item == null)
+ return false;
+ i = nextKeyIndex(i, len);
+ }
+ }
+
+ /**
+ * Tests whether the specified object reference is a value in this identity
+ * hash map.
+ *
+ * @param value value whose presence in this map is to be tested
+ * @return <tt>true</tt> if this map maps one or more keys to the
+ * specified object reference
+ * @see #containsKey(Object)
+ */
+ public boolean containsValue(Object value) {
+ Object[] tab = table;
+ for (int i = 1; i < tab.length; i += 2)
+ if (tab[i] == value && tab[i - 1] != null)
+ return true;
+
+ return false;
+ }
+
+ /**
+ * Tests if the specified key-value mapping is in the map.
+ *
+ * @param key possible key
+ * @param value possible value
+ * @return <code>true</code> if and only if the specified key-value
+ * mapping is in the map
+ */
+ private boolean containsMapping(Object key, Object value) {
+ Object k = maskNull(key);
+ Object[] tab = table;
+ int len = tab.length;
+ int i = hash(k, len);
+ while (true) {
+ Object item = tab[i];
+ if (item == k)
+ return tab[i + 1] == value;
+ if (item == null)
+ return false;
+ i = nextKeyIndex(i, len);
+ }
+ }
+
+ /**
+ * Associates the specified value with the specified key in this identity
+ * hash map. If the map previously contained a mapping for the key, the
+ * old value is replaced.
+ *
+ * @param key the key with which the specified value is to be associated
+ * @param value the value to be associated with the specified key
+ * @return the previous value associated with <tt>key</tt>, or
+ * <tt>null</tt> if there was no mapping for <tt>key</tt>.
+ * (A <tt>null</tt> return can also indicate that the map
+ * previously associated <tt>null</tt> with <tt>key</tt>.)
+ * @see Object#equals(Object)
+ * @see #get(Object)
+ * @see #containsKey(Object)
+ */
+ public V put(K key, V value) {
+ final Object k = maskNull(key);
+
+ retryAfterResize: for (;;) {
+ final Object[] tab = table;
+ final int len = tab.length;
+ int i = hash(k, len);
+
+ for (Object item; (item = tab[i]) != null;
+ i = nextKeyIndex(i, len)) {
+ if (item == k) {
+ @SuppressWarnings("unchecked")
+ V oldValue = (V) tab[i + 1];
+ tab[i + 1] = value;
+ return oldValue;
+ }
+ }
+
+ final int s = size + 1;
+ // Use optimized form of 3 * s.
+ // Next capacity is len, 2 * current capacity.
+ if (s + (s << 1) > len && resize(len))
+ continue retryAfterResize;
+
+ modCount++;
+ tab[i] = k;
+ tab[i + 1] = value;
+ size = s;
+ return null;
+ }
+ }
+
+ /**
+ * Resizes the table if necessary to hold given capacity.
+ *
+ * @param newCapacity the new capacity, must be a power of two.
+ * @return whether a resize did in fact take place
+ */
+ private boolean resize(int newCapacity) {
+ // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
+ int newLength = newCapacity * 2;
+
+ Object[] oldTable = table;
+ int oldLength = oldTable.length;
+ if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
+ if (size == MAXIMUM_CAPACITY - 1)
+ throw new IllegalStateException("Capacity exhausted.");
+ return false;
+ }
+ if (oldLength >= newLength)
+ return false;
+
+ Object[] newTable = new Object[newLength];
+
+ for (int j = 0; j < oldLength; j += 2) {
+ Object key = oldTable[j];
+ if (key != null) {
+ Object value = oldTable[j+1];
+ oldTable[j] = null;
+ oldTable[j+1] = null;
+ int i = hash(key, newLength);
+ while (newTable[i] != null)
+ i = nextKeyIndex(i, newLength);
+ newTable[i] = key;
+ newTable[i + 1] = value;
+ }
+ }
+ table = newTable;
+ return true;
+ }
+
+ /**
+ * Copies all of the mappings from the specified map to this map.
+ * These mappings will replace any mappings that this map had for
+ * any of the keys currently in the specified map.
+ *
+ * @param m mappings to be stored in this map
+ * @throws NullPointerException if the specified map is null
+ */
+ public void putAll(Map<? extends K, ? extends V> m) {
+ int n = m.size();
+ if (n == 0)
+ return;
+ if (n > size)
+ resize(capacity(n)); // conservatively pre-expand
+
+ for (Entry<? extends K, ? extends V> e : m.entrySet())
+ put(e.getKey(), e.getValue());
+ }
+
+ /**
+ * Removes the mapping for this key from this map if present.
+ *
+ * @param key key whose mapping is to be removed from the map
+ * @return the previous value associated with <tt>key</tt>, or
+ * <tt>null</tt> if there was no mapping for <tt>key</tt>.
+ * (A <tt>null</tt> return can also indicate that the map
+ * previously associated <tt>null</tt> with <tt>key</tt>.)
+ */
+ public V remove(Object key) {
+ Object k = maskNull(key);
+ Object[] tab = table;
+ int len = tab.length;
+ int i = hash(k, len);
+
+ while (true) {
+ Object item = tab[i];
+ if (item == k) {
+ modCount++;
+ size--;
+ @SuppressWarnings("unchecked")
+ V oldValue = (V) tab[i + 1];
+ tab[i + 1] = null;
+ tab[i] = null;
+ closeDeletion(i);
+ return oldValue;
+ }
+ if (item == null)
+ return null;
+ i = nextKeyIndex(i, len);
+ }
+ }
+
+ /**
+ * Removes the specified key-value mapping from the map if it is present.
+ *
+ * @param key possible key
+ * @param value possible value
+ * @return <code>true</code> if and only if the specified key-value
+ * mapping was in the map
+ */
+ private boolean removeMapping(Object key, Object value) {
+ Object k = maskNull(key);
+ Object[] tab = table;
+ int len = tab.length;
+ int i = hash(k, len);
+
+ while (true) {
+ Object item = tab[i];
+ if (item == k) {
+ if (tab[i + 1] != value)
+ return false;
+ modCount++;
+ size--;
+ tab[i] = null;
+ tab[i + 1] = null;
+ closeDeletion(i);
+ return true;
+ }
+ if (item == null)
+ return false;
+ i = nextKeyIndex(i, len);
+ }
+ }
+
+ /**
+ * Rehash all possibly-colliding entries following a
+ * deletion. This preserves the linear-probe
+ * collision properties required by get, put, etc.
+ *
+ * @param d the index of a newly empty deleted slot
+ */
+ private void closeDeletion(int d) {
+ // Adapted from Knuth Section 6.4 Algorithm R
+ Object[] tab = table;
+ int len = tab.length;
+
+ // Look for items to swap into newly vacated slot
+ // starting at index immediately following deletion,
+ // and continuing until a null slot is seen, indicating
+ // the end of a run of possibly-colliding keys.
+ Object item;
+ for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
+ i = nextKeyIndex(i, len) ) {
+ // The following test triggers if the item at slot i (which
+ // hashes to be at slot r) should take the spot vacated by d.
+ // If so, we swap it in, and then continue with d now at the
+ // newly vacated i. This process will terminate when we hit
+ // the null slot at the end of this run.
+ // The test is messy because we are using a circular table.
+ int r = hash(item, len);
+ if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
+ tab[d] = item;
+ tab[d + 1] = tab[i + 1];
+ tab[i] = null;
+ tab[i + 1] = null;
+ d = i;
+ }
+ }
+ }
+
+ /**
+ * Removes all of the mappings from this map.
+ * The map will be empty after this call returns.
+ */
+ public void clear() {
+ modCount++;
+ Object[] tab = table;
+ for (int i = 0; i < tab.length; i++)
+ tab[i] = null;
+ size = 0;
+ }
+
+ /**
+ * Compares the specified object with this map for equality. Returns
+ * <tt>true</tt> if the given object is also a map and the two maps
+ * represent identical object-reference mappings. More formally, this
+ * map is equal to another map <tt>m</tt> if and only if
+ * <tt>this.entrySet().equals(m.entrySet())</tt>.
+ *
+ * <p><b>Owing to the reference-equality-based semantics of this map it is
+ * possible that the symmetry and transitivity requirements of the
+ * <tt>Object.equals</tt> contract may be violated if this map is compared
+ * to a normal map. However, the <tt>Object.equals</tt> contract is
+ * guaranteed to hold among <tt>IdentityHashMap</tt> instances.</b>
+ *
+ * @param o object to be compared for equality with this map
+ * @return <tt>true</tt> if the specified object is equal to this map
+ * @see Object#equals(Object)
+ */
+ public boolean equals(Object o) {
+ if (o == this) {
+ return true;
+ } else if (o instanceof IdentityHashMap) {
+ IdentityHashMap<?,?> m = (IdentityHashMap<?,?>) o;
+ if (m.size() != size)
+ return false;
+
+ Object[] tab = m.table;
+ for (int i = 0; i < tab.length; i+=2) {
+ Object k = tab[i];
+ if (k != null && !containsMapping(k, tab[i + 1]))
+ return false;
+ }
+ return true;
+ } else if (o instanceof Map) {
+ Map<?,?> m = (Map<?,?>)o;
+ return entrySet().equals(m.entrySet());
+ } else {
+ return false; // o is not a Map
+ }
+ }
+
+ /**
+ * Returns the hash code value for this map. The hash code of a map is
+ * defined to be the sum of the hash codes of each entry in the map's
+ * <tt>entrySet()</tt> view. This ensures that <tt>m1.equals(m2)</tt>
+ * implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two
+ * <tt>IdentityHashMap</tt> instances <tt>m1</tt> and <tt>m2</tt>, as
+ * required by the general contract of {@link Object#hashCode}.
+ *
+ * <p><b>Owing to the reference-equality-based semantics of the
+ * <tt>Map.Entry</tt> instances in the set returned by this map's
+ * <tt>entrySet</tt> method, it is possible that the contractual
+ * requirement of <tt>Object.hashCode</tt> mentioned in the previous
+ * paragraph will be violated if one of the two objects being compared is
+ * an <tt>IdentityHashMap</tt> instance and the other is a normal map.</b>
+ *
+ * @return the hash code value for this map
+ * @see Object#equals(Object)
+ * @see #equals(Object)
+ */
+ public int hashCode() {
+ int result = 0;
+ Object[] tab = table;
+ for (int i = 0; i < tab.length; i +=2) {
+ Object key = tab[i];
+ if (key != null) {
+ Object k = unmaskNull(key);
+ result += System.identityHashCode(k) ^
+ System.identityHashCode(tab[i + 1]);
+ }
+ }
+ return result;
+ }
+
+ /**
+ * Returns a shallow copy of this identity hash map: the keys and values
+ * themselves are not cloned.
+ *
+ * @return a shallow copy of this map
+ */
+ public Object clone() {
+ try {
+ IdentityHashMap<?,?> m = (IdentityHashMap<?,?>) super.clone();
+ m.entrySet = null;
+ m.table = table.clone();
+ return m;
+ } catch (CloneNotSupportedException e) {
+ throw new InternalError(e);
+ }
+ }
+
+ private abstract class IdentityHashMapIterator<T> implements Iterator<T> {
+ int index = (size != 0 ? 0 : table.length); // current slot.
+ int expectedModCount = modCount; // to support fast-fail
+ int lastReturnedIndex = -1; // to allow remove()
+ boolean indexValid; // To avoid unnecessary next computation
+ Object[] traversalTable = table; // reference to main table or copy
+
+ public boolean hasNext() {
+ Object[] tab = traversalTable;
+ for (int i = index; i < tab.length; i+=2) {
+ Object key = tab[i];
+ if (key != null) {
+ index = i;
+ return indexValid = true;
+ }
+ }
+ index = tab.length;
+ return false;
+ }
+
+ protected int nextIndex() {
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ if (!indexValid && !hasNext())
+ throw new NoSuchElementException();
+
+ indexValid = false;
+ lastReturnedIndex = index;
+ index += 2;
+ return lastReturnedIndex;
+ }
+
+ public void remove() {
+ if (lastReturnedIndex == -1)
+ throw new IllegalStateException();
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+
+ expectedModCount = ++modCount;
+ int deletedSlot = lastReturnedIndex;
+ lastReturnedIndex = -1;
+ // back up index to revisit new contents after deletion
+ index = deletedSlot;
+ indexValid = false;
+
+ // Removal code proceeds as in closeDeletion except that
+ // it must catch the rare case where an element already
+ // seen is swapped into a vacant slot that will be later
+ // traversed by this iterator. We cannot allow future
+ // next() calls to return it again. The likelihood of
+ // this occurring under 2/3 load factor is very slim, but
+ // when it does happen, we must make a copy of the rest of
+ // the table to use for the rest of the traversal. Since
+ // this can only happen when we are near the end of the table,
+ // even in these rare cases, this is not very expensive in
+ // time or space.
+
+ Object[] tab = traversalTable;
+ int len = tab.length;
+
+ int d = deletedSlot;
+ Object key = tab[d];
+ tab[d] = null; // vacate the slot
+ tab[d + 1] = null;
+
+ // If traversing a copy, remove in real table.
+ // We can skip gap-closure on copy.
+ if (tab != IdentityHashMap.this.table) {
+ IdentityHashMap.this.remove(key);
+ expectedModCount = modCount;
+ return;
+ }
+
+ size--;
+
+ Object item;
+ for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
+ i = nextKeyIndex(i, len)) {
+ int r = hash(item, len);
+ // See closeDeletion for explanation of this conditional
+ if ((i < r && (r <= d || d <= i)) ||
+ (r <= d && d <= i)) {
+
+ // If we are about to swap an already-seen element
+ // into a slot that may later be returned by next(),
+ // then clone the rest of table for use in future
+ // next() calls. It is OK that our copy will have
+ // a gap in the "wrong" place, since it will never
+ // be used for searching anyway.
+
+ if (i < deletedSlot && d >= deletedSlot &&
+ traversalTable == IdentityHashMap.this.table) {
+ int remaining = len - deletedSlot;
+ Object[] newTable = new Object[remaining];
+ System.arraycopy(tab, deletedSlot,
+ newTable, 0, remaining);
+ traversalTable = newTable;
+ index = 0;
+ }
+
+ tab[d] = item;
+ tab[d + 1] = tab[i + 1];
+ tab[i] = null;
+ tab[i + 1] = null;
+ d = i;
+ }
+ }
+ }
+ }
+
+ private class KeyIterator extends IdentityHashMapIterator<K> {
+ @SuppressWarnings("unchecked")
+ public K next() {
+ return (K) unmaskNull(traversalTable[nextIndex()]);
+ }
+ }
+
+ private class ValueIterator extends IdentityHashMapIterator<V> {
+ @SuppressWarnings("unchecked")
+ public V next() {
+ return (V) traversalTable[nextIndex() + 1];
+ }
+ }
+
+ private class EntryIterator
+ extends IdentityHashMapIterator<Map.Entry<K,V>>
+ {
+ private Entry lastReturnedEntry;
+
+ public Map.Entry<K,V> next() {
+ lastReturnedEntry = new Entry(nextIndex());
+ return lastReturnedEntry;
+ }
+
+ public void remove() {
+ lastReturnedIndex =
+ ((null == lastReturnedEntry) ? -1 : lastReturnedEntry.index);
+ super.remove();
+ lastReturnedEntry.index = lastReturnedIndex;
+ lastReturnedEntry = null;
+ }
+
+ private class Entry implements Map.Entry<K,V> {
+ private int index;
+
+ private Entry(int index) {
+ this.index = index;
+ }
+
+ @SuppressWarnings("unchecked")
+ public K getKey() {
+ checkIndexForEntryUse();
+ return (K) unmaskNull(traversalTable[index]);
+ }
+
+ @SuppressWarnings("unchecked")
+ public V getValue() {
+ checkIndexForEntryUse();
+ return (V) traversalTable[index+1];
+ }
+
+ @SuppressWarnings("unchecked")
+ public V setValue(V value) {
+ checkIndexForEntryUse();
+ V oldValue = (V) traversalTable[index+1];
+ traversalTable[index+1] = value;
+ // if shadowing, force into main table
+ if (traversalTable != IdentityHashMap.this.table)
+ put((K) traversalTable[index], value);
+ return oldValue;
+ }
+
+ public boolean equals(Object o) {
+ if (index < 0)
+ return super.equals(o);
+
+ if (!(o instanceof Map.Entry))
+ return false;
+ Map.Entry<?,?> e = (Map.Entry<?,?>)o;
+ return (e.getKey() == unmaskNull(traversalTable[index]) &&
+ e.getValue() == traversalTable[index+1]);
+ }
+
+ public int hashCode() {
+ if (lastReturnedIndex < 0)
+ return super.hashCode();
+
+ return (System.identityHashCode(unmaskNull(traversalTable[index])) ^
+ System.identityHashCode(traversalTable[index+1]));
+ }
+
+ public String toString() {
+ if (index < 0)
+ return super.toString();
+
+ return (unmaskNull(traversalTable[index]) + "="
+ + traversalTable[index+1]);
+ }
+
+ private void checkIndexForEntryUse() {
+ if (index < 0)
+ throw new IllegalStateException("Entry was removed");
+ }
+ }
+ }
+
+ // Views
+
+ /**
+ * This field is initialized to contain an instance of the entry set
+ * view the first time this view is requested. The view is stateless,
+ * so there's no reason to create more than one.
+ */
+ private transient Set<Map.Entry<K,V>> entrySet;
+
+ /**
+ * Returns an identity-based set view of the keys contained in this map.
+ * The set is backed by the map, so changes to the map are reflected in
+ * the set, and vice-versa. If the map is modified while an iteration
+ * over the set is in progress, the results of the iteration are
+ * undefined. The set supports element removal, which removes the
+ * corresponding mapping from the map, via the <tt>Iterator.remove</tt>,
+ * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
+ * <tt>clear</tt> methods. It does not support the <tt>add</tt> or
+ * <tt>addAll</tt> methods.
+ *
+ * <p><b>While the object returned by this method implements the
+ * <tt>Set</tt> interface, it does <i>not</i> obey <tt>Set's</tt> general
+ * contract. Like its backing map, the set returned by this method
+ * defines element equality as reference-equality rather than
+ * object-equality. This affects the behavior of its <tt>contains</tt>,
+ * <tt>remove</tt>, <tt>containsAll</tt>, <tt>equals</tt>, and
+ * <tt>hashCode</tt> methods.</b>
+ *
+ * <p><b>The <tt>equals</tt> method of the returned set returns <tt>true</tt>
+ * only if the specified object is a set containing exactly the same
+ * object references as the returned set. The symmetry and transitivity
+ * requirements of the <tt>Object.equals</tt> contract may be violated if
+ * the set returned by this method is compared to a normal set. However,
+ * the <tt>Object.equals</tt> contract is guaranteed to hold among sets
+ * returned by this method.</b>
+ *
+ * <p>The <tt>hashCode</tt> method of the returned set returns the sum of
+ * the <i>identity hashcodes</i> of the elements in the set, rather than
+ * the sum of their hashcodes. This is mandated by the change in the
+ * semantics of the <tt>equals</tt> method, in order to enforce the
+ * general contract of the <tt>Object.hashCode</tt> method among sets
+ * returned by this method.
+ *
+ * @return an identity-based set view of the keys contained in this map
+ * @see Object#equals(Object)
+ * @see System#identityHashCode(Object)
+ */
+ public Set<K> keySet() {
+ Set<K> ks = keySet;
+ if (ks != null)
+ return ks;
+ else
+ return keySet = new KeySet();
+ }
+
+ private class KeySet extends AbstractSet<K> {
+ public Iterator<K> iterator() {
+ return new KeyIterator();
+ }
+ public int size() {
+ return size;
+ }
+ public boolean contains(Object o) {
+ return containsKey(o);
+ }
+ public boolean remove(Object o) {
+ int oldSize = size;
+ IdentityHashMap.this.remove(o);
+ return size != oldSize;
+ }
+ /*
+ * Must revert from AbstractSet's impl to AbstractCollection's, as
+ * the former contains an optimization that results in incorrect
+ * behavior when c is a smaller "normal" (non-identity-based) Set.
+ */
+ public boolean removeAll(Collection<?> c) {
+ Objects.requireNonNull(c);
+ boolean modified = false;
+ for (Iterator<K> i = iterator(); i.hasNext(); ) {
+ if (c.contains(i.next())) {
+ i.remove();
+ modified = true;
+ }
+ }
+ return modified;
+ }
+ public void clear() {
+ IdentityHashMap.this.clear();
+ }
+ public int hashCode() {
+ int result = 0;
+ for (K key : this)
+ result += System.identityHashCode(key);
+ return result;
+ }
+ public Object[] toArray() {
+ return toArray(new Object[0]);
+ }
+ @SuppressWarnings("unchecked")
+ public <T> T[] toArray(T[] a) {
+ int expectedModCount = modCount;
+ int size = size();
+ if (a.length < size)
+ a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
+ Object[] tab = table;
+ int ti = 0;
+ for (int si = 0; si < tab.length; si += 2) {
+ Object key;
+ if ((key = tab[si]) != null) { // key present ?
+ // more elements than expected -> concurrent modification from other thread
+ if (ti >= size) {
+ throw new ConcurrentModificationException();
+ }
+ a[ti++] = (T) unmaskNull(key); // unmask key
+ }
+ }
+ // fewer elements than expected or concurrent modification from other thread detected
+ if (ti < size || expectedModCount != modCount) {
+ throw new ConcurrentModificationException();
+ }
+ // final null marker as per spec
+ if (ti < a.length) {
+ a[ti] = null;
+ }
+ return a;
+ }
+
+ public Spliterator<K> spliterator() {
+ return new KeySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
+ }
+ }
+
+ /**
+ * Returns a {@link Collection} view of the values contained in this map.
+ * The collection is backed by the map, so changes to the map are
+ * reflected in the collection, and vice-versa. If the map is
+ * modified while an iteration over the collection is in progress,
+ * the results of the iteration are undefined. The collection
+ * supports element removal, which removes the corresponding
+ * mapping from the map, via the <tt>Iterator.remove</tt>,
+ * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
+ * <tt>retainAll</tt> and <tt>clear</tt> methods. It does not
+ * support the <tt>add</tt> or <tt>addAll</tt> methods.
+ *
+ * <p><b>While the object returned by this method implements the
+ * <tt>Collection</tt> interface, it does <i>not</i> obey
+ * <tt>Collection's</tt> general contract. Like its backing map,
+ * the collection returned by this method defines element equality as
+ * reference-equality rather than object-equality. This affects the
+ * behavior of its <tt>contains</tt>, <tt>remove</tt> and
+ * <tt>containsAll</tt> methods.</b>
+ */
+ public Collection<V> values() {
+ Collection<V> vs = values;
+ if (vs != null)
+ return vs;
+ else
+ return values = new Values();
+ }
+
+ private class Values extends AbstractCollection<V> {
+ public Iterator<V> iterator() {
+ return new ValueIterator();
+ }
+ public int size() {
+ return size;
+ }
+ public boolean contains(Object o) {
+ return containsValue(o);
+ }
+ public boolean remove(Object o) {
+ for (Iterator<V> i = iterator(); i.hasNext(); ) {
+ if (i.next() == o) {
+ i.remove();
+ return true;
+ }
+ }
+ return false;
+ }
+ public void clear() {
+ IdentityHashMap.this.clear();
+ }
+ public Object[] toArray() {
+ return toArray(new Object[0]);
+ }
+ @SuppressWarnings("unchecked")
+ public <T> T[] toArray(T[] a) {
+ int expectedModCount = modCount;
+ int size = size();
+ if (a.length < size)
+ a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
+ Object[] tab = table;
+ int ti = 0;
+ for (int si = 0; si < tab.length; si += 2) {
+ if (tab[si] != null) { // key present ?
+ // more elements than expected -> concurrent modification from other thread
+ if (ti >= size) {
+ throw new ConcurrentModificationException();
+ }
+ a[ti++] = (T) tab[si+1]; // copy value
+ }
+ }
+ // fewer elements than expected or concurrent modification from other thread detected
+ if (ti < size || expectedModCount != modCount) {
+ throw new ConcurrentModificationException();
+ }
+ // final null marker as per spec
+ if (ti < a.length) {
+ a[ti] = null;
+ }
+ return a;
+ }
+
+ public Spliterator<V> spliterator() {
+ return new ValueSpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
+ }
+ }
+
+ /**
+ * Returns a {@link Set} view of the mappings contained in this map.
+ * Each element in the returned set is a reference-equality-based
+ * <tt>Map.Entry</tt>. The set is backed by the map, so changes
+ * to the map are reflected in the set, and vice-versa. If the
+ * map is modified while an iteration over the set is in progress,
+ * the results of the iteration are undefined. The set supports
+ * element removal, which removes the corresponding mapping from
+ * the map, via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
+ * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
+ * methods. It does not support the <tt>add</tt> or
+ * <tt>addAll</tt> methods.
+ *
+ * <p>Like the backing map, the <tt>Map.Entry</tt> objects in the set
+ * returned by this method define key and value equality as
+ * reference-equality rather than object-equality. This affects the
+ * behavior of the <tt>equals</tt> and <tt>hashCode</tt> methods of these
+ * <tt>Map.Entry</tt> objects. A reference-equality based <tt>Map.Entry
+ * e</tt> is equal to an object <tt>o</tt> if and only if <tt>o</tt> is a
+ * <tt>Map.Entry</tt> and <tt>e.getKey()==o.getKey() &&
+ * e.getValue()==o.getValue()</tt>. To accommodate these equals
+ * semantics, the <tt>hashCode</tt> method returns
+ * <tt>System.identityHashCode(e.getKey()) ^
+ * System.identityHashCode(e.getValue())</tt>.
+ *
+ * <p><b>Owing to the reference-equality-based semantics of the
+ * <tt>Map.Entry</tt> instances in the set returned by this method,
+ * it is possible that the symmetry and transitivity requirements of
+ * the {@link Object#equals(Object)} contract may be violated if any of
+ * the entries in the set is compared to a normal map entry, or if
+ * the set returned by this method is compared to a set of normal map
+ * entries (such as would be returned by a call to this method on a normal
+ * map). However, the <tt>Object.equals</tt> contract is guaranteed to
+ * hold among identity-based map entries, and among sets of such entries.
+ * </b>
+ *
+ * @return a set view of the identity-mappings contained in this map
+ */
+ public Set<Map.Entry<K,V>> entrySet() {
+ Set<Map.Entry<K,V>> es = entrySet;
+ if (es != null)
+ return es;
+ else
+ return entrySet = new EntrySet();
+ }
+
+ private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
+ public Iterator<Map.Entry<K,V>> iterator() {
+ return new EntryIterator();
+ }
+ public boolean contains(Object o) {
+ if (!(o instanceof Map.Entry))
+ return false;
+ Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
+ return containsMapping(entry.getKey(), entry.getValue());
+ }
+ public boolean remove(Object o) {
+ if (!(o instanceof Map.Entry))
+ return false;
+ Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
+ return removeMapping(entry.getKey(), entry.getValue());
+ }
+ public int size() {
+ return size;
+ }
+ public void clear() {
+ IdentityHashMap.this.clear();
+ }
+ /*
+ * Must revert from AbstractSet's impl to AbstractCollection's, as
+ * the former contains an optimization that results in incorrect
+ * behavior when c is a smaller "normal" (non-identity-based) Set.
+ */
+ public boolean removeAll(Collection<?> c) {
+ Objects.requireNonNull(c);
+ boolean modified = false;
+ for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); ) {
+ if (c.contains(i.next())) {
+ i.remove();
+ modified = true;
+ }
+ }
+ return modified;
+ }
+
+ public Object[] toArray() {
+ return toArray(new Object[0]);
+ }
+
+ @SuppressWarnings("unchecked")
+ public <T> T[] toArray(T[] a) {
+ int expectedModCount = modCount;
+ int size = size();
+ if (a.length < size)
+ a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
+ Object[] tab = table;
+ int ti = 0;
+ for (int si = 0; si < tab.length; si += 2) {
+ Object key;
+ if ((key = tab[si]) != null) { // key present ?
+ // more elements than expected -> concurrent modification from other thread
+ if (ti >= size) {
+ throw new ConcurrentModificationException();
+ }
+ a[ti++] = (T) new AbstractMap.SimpleEntry<>(unmaskNull(key), tab[si + 1]);
+ }
+ }
+ // fewer elements than expected or concurrent modification from other thread detected
+ if (ti < size || expectedModCount != modCount) {
+ throw new ConcurrentModificationException();
+ }
+ // final null marker as per spec
+ if (ti < a.length) {
+ a[ti] = null;
+ }
+ return a;
+ }
+
+ public Spliterator<Map.Entry<K,V>> spliterator() {
+ return new EntrySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
+ }
+ }
+
+
+ private static final long serialVersionUID = 8188218128353913216L;
+
+ /**
+ * Saves the state of the <tt>IdentityHashMap</tt> instance to a stream
+ * (i.e., serializes it).
+ *
+ * @serialData The <i>size</i> of the HashMap (the number of key-value
+ * mappings) (<tt>int</tt>), followed by the key (Object) and
+ * value (Object) for each key-value mapping represented by the
+ * IdentityHashMap. The key-value mappings are emitted in no
+ * particular order.
+ */
+ private void writeObject(java.io.ObjectOutputStream s)
+ throws java.io.IOException {
+ // Write out and any hidden stuff
+ s.defaultWriteObject();
+
+ // Write out size (number of Mappings)
+ s.writeInt(size);
+
+ // Write out keys and values (alternating)
+ Object[] tab = table;
+ for (int i = 0; i < tab.length; i += 2) {
+ Object key = tab[i];
+ if (key != null) {
+ s.writeObject(unmaskNull(key));
+ s.writeObject(tab[i + 1]);
+ }
+ }
+ }
+
+ /**
+ * Reconstitutes the <tt>IdentityHashMap</tt> instance from a stream (i.e.,
+ * deserializes it).
+ */
+ private void readObject(java.io.ObjectInputStream s)
+ throws java.io.IOException, ClassNotFoundException {
+ // Read in any hidden stuff
+ s.defaultReadObject();
+
+ // Read in size (number of Mappings)
+ int size = s.readInt();
+ if (size < 0)
+ throw new java.io.StreamCorruptedException
+ ("Illegal mappings count: " + size);
+ init(capacity(size));
+
+ // Read the keys and values, and put the mappings in the table
+ for (int i=0; i<size; i++) {
+ @SuppressWarnings("unchecked")
+ K key = (K) s.readObject();
+ @SuppressWarnings("unchecked")
+ V value = (V) s.readObject();
+ putForCreate(key, value);
+ }
+ }
+
+ /**
+ * The put method for readObject. It does not resize the table,
+ * update modCount, etc.
+ */
+ private void putForCreate(K key, V value)
+ throws java.io.StreamCorruptedException
+ {
+ Object k = maskNull(key);
+ Object[] tab = table;
+ int len = tab.length;
+ int i = hash(k, len);
+
+ Object item;
+ while ( (item = tab[i]) != null) {
+ if (item == k)
+ throw new java.io.StreamCorruptedException();
+ i = nextKeyIndex(i, len);
+ }
+ tab[i] = k;
+ tab[i + 1] = value;
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public void forEach(BiConsumer<? super K, ? super V> action) {
+ Objects.requireNonNull(action);
+ int expectedModCount = modCount;
+
+ Object[] t = table;
+ for (int index = 0; index < t.length; index += 2) {
+ Object k = t[index];
+ if (k != null) {
+ action.accept((K) unmaskNull(k), (V) t[index + 1]);
+ }
+
+ if (modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
+ Objects.requireNonNull(function);
+ int expectedModCount = modCount;
+
+ Object[] t = table;
+ for (int index = 0; index < t.length; index += 2) {
+ Object k = t[index];
+ if (k != null) {
+ t[index + 1] = function.apply((K) unmaskNull(k), (V) t[index + 1]);
+ }
+
+ if (modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
+ }
+ }
+
+ /**
+ * Similar form as array-based Spliterators, but skips blank elements,
+ * and guestimates size as decreasing by half per split.
+ */
+ static class IdentityHashMapSpliterator<K,V> {
+ final IdentityHashMap<K,V> map;
+ int index; // current index, modified on advance/split
+ int fence; // -1 until first use; then one past last index
+ int est; // size estimate
+ int expectedModCount; // initialized when fence set
+
+ IdentityHashMapSpliterator(IdentityHashMap<K,V> map, int origin,
+ int fence, int est, int expectedModCount) {
+ this.map = map;
+ this.index = origin;
+ this.fence = fence;
+ this.est = est;
+ this.expectedModCount = expectedModCount;
+ }
+
+ final int getFence() { // initialize fence and size on first use
+ int hi;
+ if ((hi = fence) < 0) {
+ est = map.size;
+ expectedModCount = map.modCount;
+ hi = fence = map.table.length;
+ }
+ return hi;
+ }
+
+ public final long estimateSize() {
+ getFence(); // force init
+ return (long) est;
+ }
+ }
+
+ static final class KeySpliterator<K,V>
+ extends IdentityHashMapSpliterator<K,V>
+ implements Spliterator<K> {
+ KeySpliterator(IdentityHashMap<K,V> map, int origin, int fence, int est,
+ int expectedModCount) {
+ super(map, origin, fence, est, expectedModCount);
+ }
+
+ public KeySpliterator<K,V> trySplit() {
+ int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
+ return (lo >= mid) ? null :
+ new KeySpliterator<>(map, lo, index = mid, est >>>= 1,
+ expectedModCount);
+ }
+
+ @SuppressWarnings("unchecked")
+ public void forEachRemaining(Consumer<? super K> action) {
+ if (action == null)
+ throw new NullPointerException();
+ int i, hi, mc; Object key;
+ IdentityHashMap<K,V> m; Object[] a;
+ if ((m = map) != null && (a = m.table) != null &&
+ (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
+ for (; i < hi; i += 2) {
+ if ((key = a[i]) != null)
+ action.accept((K)unmaskNull(key));
+ }
+ if (m.modCount == expectedModCount)
+ return;
+ }
+ throw new ConcurrentModificationException();
+ }
+
+ @SuppressWarnings("unchecked")
+ public boolean tryAdvance(Consumer<? super K> action) {
+ if (action == null)
+ throw new NullPointerException();
+ Object[] a = map.table;
+ int hi = getFence();
+ while (index < hi) {
+ Object key = a[index];
+ index += 2;
+ if (key != null) {
+ action.accept((K)unmaskNull(key));
+ if (map.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public int characteristics() {
+ return (fence < 0 || est == map.size ? SIZED : 0) | Spliterator.DISTINCT;
+ }
+ }
+
+ static final class ValueSpliterator<K,V>
+ extends IdentityHashMapSpliterator<K,V>
+ implements Spliterator<V> {
+ ValueSpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est,
+ int expectedModCount) {
+ super(m, origin, fence, est, expectedModCount);
+ }
+
+ public ValueSpliterator<K,V> trySplit() {
+ int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
+ return (lo >= mid) ? null :
+ new ValueSpliterator<>(map, lo, index = mid, est >>>= 1,
+ expectedModCount);
+ }
+
+ public void forEachRemaining(Consumer<? super V> action) {
+ if (action == null)
+ throw new NullPointerException();
+ int i, hi, mc;
+ IdentityHashMap<K,V> m; Object[] a;
+ if ((m = map) != null && (a = m.table) != null &&
+ (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
+ for (; i < hi; i += 2) {
+ if (a[i] != null) {
+ @SuppressWarnings("unchecked") V v = (V)a[i+1];
+ action.accept(v);
+ }
+ }
+ if (m.modCount == expectedModCount)
+ return;
+ }
+ throw new ConcurrentModificationException();
+ }
+
+ public boolean tryAdvance(Consumer<? super V> action) {
+ if (action == null)
+ throw new NullPointerException();
+ Object[] a = map.table;
+ int hi = getFence();
+ while (index < hi) {
+ Object key = a[index];
+ @SuppressWarnings("unchecked") V v = (V)a[index+1];
+ index += 2;
+ if (key != null) {
+ action.accept(v);
+ if (map.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public int characteristics() {
+ return (fence < 0 || est == map.size ? SIZED : 0);
+ }
+
+ }
+
+ static final class EntrySpliterator<K,V>
+ extends IdentityHashMapSpliterator<K,V>
+ implements Spliterator<Map.Entry<K,V>> {
+ EntrySpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est,
+ int expectedModCount) {
+ super(m, origin, fence, est, expectedModCount);
+ }
+
+ public EntrySpliterator<K,V> trySplit() {
+ int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
+ return (lo >= mid) ? null :
+ new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
+ expectedModCount);
+ }
+
+ public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
+ if (action == null)
+ throw new NullPointerException();
+ int i, hi, mc;
+ IdentityHashMap<K,V> m; Object[] a;
+ if ((m = map) != null && (a = m.table) != null &&
+ (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
+ for (; i < hi; i += 2) {
+ Object key = a[i];
+ if (key != null) {
+ @SuppressWarnings("unchecked") K k =
+ (K)unmaskNull(key);
+ @SuppressWarnings("unchecked") V v = (V)a[i+1];
+ action.accept
+ (new AbstractMap.SimpleImmutableEntry<>(k, v));
+
+ }
+ }
+ if (m.modCount == expectedModCount)
+ return;
+ }
+ throw new ConcurrentModificationException();
+ }
+
+ public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
+ if (action == null)
+ throw new NullPointerException();
+ Object[] a = map.table;
+ int hi = getFence();
+ while (index < hi) {
+ Object key = a[index];
+ @SuppressWarnings("unchecked") V v = (V)a[index+1];
+ index += 2;
+ if (key != null) {
+ @SuppressWarnings("unchecked") K k =
+ (K)unmaskNull(key);
+ action.accept
+ (new AbstractMap.SimpleImmutableEntry<>(k, v));
+ if (map.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public int characteristics() {
+ return (fence < 0 || est == map.size ? SIZED : 0) | Spliterator.DISTINCT;
+ }
+ }
+
+}