/*

  * Copyright (c) 2000, 2011, 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.io.*;

 /**

  * 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.

      */

     private static final int MAXIMUM_CAPACITY = 1 << 29;

     /**

      * The table, resized as necessary. Length MUST always be a power of two.

      */

     private transient Object[] table;

     /**

      * The number of key-value mappings contained in this identity hash map.

      *

      * @serial

      */

     private int size;

     /**

      * The number of modifications, to support fast-fail iterators

      */

     private transient int modCount;

     /**

      * The next size value at which to resize (capacity * load factor).

      */

     private transient int threshold;

     /**

      * Value representing null keys inside tables.

      */

     private 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.

      */

     private static 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 specified 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.  If (3 * expectedMaxSize)/2 is negative, it

      * is assumed that overflow has occurred, and MAXIMUM_CAPACITY is returned.

      */

     private int capacity(int expectedMaxSize) {

         // Compute min capacity for expectedMaxSize given a load factor of 2/3

         int minCapacity = (3 * expectedMaxSize)/2;

         // Compute the appropriate capacity

         int result;

         if (minCapacity > MAXIMUM_CAPACITY || minCapacity < 0) {

             result = MAXIMUM_CAPACITY;

         } else {

             result = MINIMUM_CAPACITY;

             while (result < minCapacity)

                 result <<= 1;

         }

         return result;

     }

     /**

      * 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;

         threshold = (initCapacity * 2)/3;

         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)

      */

     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) {

         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) {

                 V oldValue = (V) tab[i + 1];

                 tab[i + 1] = value;

                 return oldValue;

             }

             i = nextKeyIndex(i, len);

         }

         modCount++;

         tab[i] = k;

         tab[i + 1] = value;

         if (++size >= threshold)

             resize(len); // len == 2 * current capacity.

         return null;

     }

     /**

      * Resize the table to hold given capacity.

      *

      * @param newCapacity the new capacity, must be a power of two.

      */

     private void 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 (threshold == MAXIMUM_CAPACITY-1)

                 throw new IllegalStateException("Capacity exhausted.");

             threshold = MAXIMUM_CAPACITY-1;  // Gigantic map!

             return;

         }

         if (oldLength >= newLength)

             return;

         Object[] newTable = new Object[newLength];

         threshold = newLength / 3;

         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;

     }

     /**

      * 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 > threshold) // conservatively pre-expand

             resize(capacity(n));

         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--;

                 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<K,V> m = (IdentityHashMap<K,V>) super.clone();

             m.entrySet = null;

             m.table = table.clone();

             return m;

         } catch (CloneNotSupportedException e) {

             throw new InternalError();

         }

     }

     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;

             K key = (K) 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> {

         public K next() {

             return (K) unmaskNull(traversalTable[nextIndex()]);

         }

     }

     private class ValueIterator extends IdentityHashMapIterator<V> {

         public V next() {

             return (V) traversalTable[nextIndex() + 1];

         }

     }

     private class EntryIterator

         extends IdentityHashMapIterator<Map.Entry<K,V>>

     {

         private Entry lastReturnedEntry = null;

         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;

             }

             public K getKey() {

                 checkIndexForEntryUse();

                 return (K) unmaskNull(traversalTable[index]);

             }

             public V getValue() {

                 checkIndexForEntryUse();

                 return (V) traversalTable[index+1];

             }

             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 = null;

     /**

      * 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) {

             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;

         }

     }

     /**

      * 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();

         }

     }

     /**

      * 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() &amp;&amp;

      * 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) {

             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() {

             int size = size();

             Object[] result = new Object[size];

             Iterator<Map.Entry<K,V>> it = iterator();

             for (int i = 0; i < size; i++)

                 result[i] = new AbstractMap.SimpleEntry<>(it.next());

             return result;

         }

         @SuppressWarnings("unchecked")

         public <T> T[] toArray(T[] a) {

             int size = size();

             if (a.length < size)

                 a = (T[])java.lang.reflect.Array

                     .newInstance(a.getClass().getComponentType(), size);

             Iterator<Map.Entry<K,V>> it = iterator();

             for (int i = 0; i < size; i++)

                 a[i] = (T) new AbstractMap.SimpleEntry<>(it.next());

             if (a.length > size)

                 a[size] = null;

             return a;

         }

     }

     private static final long serialVersionUID = 8188218128353913216L;

     /**

      * Save the state of the <tt>IdentityHashMap</tt> instance to a stream

      * (i.e., serialize 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]);

             }

         }

     }

     /**

      * Reconstitute the <tt>IdentityHashMap</tt> instance from a stream (i.e.,

      * deserialize 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();

         // Allow for 33% growth (i.e., capacity is >= 2* size()).

         init(capacity((size*4)/3));

         // Read the keys and values, and put the mappings in the table

         for (int i=0; i<size; i++) {

             K key = (K) s.readObject();

             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 IOException

     {

         K k = (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;

     }

 }