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