/*

* Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved.

* ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*/

package java.util;

import java.io.*;

import java.lang.reflect.Array;

import java.util.function.BiConsumer;

import java.util.function.BiFunction;

import java.util.function.Consumer;

/**

* This class implements the <tt>Map</tt> interface with a hash table, using

* reference-equality in place of object-equality when comparing keys (and

* values). In other words, in an <tt>IdentityHashMap</tt>, two keys

* <tt>k1</tt> and <tt>k2</tt> are considered equal if and only if

* <tt>(k1==k2)</tt>. (In normal <tt>Map</tt> implementations (like

* <tt>HashMap</tt>) two keys <tt>k1</tt> and <tt>k2</tt> are considered equal

* if and only if <tt>(k1==null ? k2==null : k1.equals(k2))</tt>.)

*

* <p><b>This class is <i>not</i> a general-purpose <tt>Map</tt>

* implementation! While this class implements the <tt>Map</tt> interface, it

* intentionally violates <tt>Map's</tt> general contract, which mandates the

* use of the <tt>equals</tt> method when comparing objects. This class is

* designed for use only in the rare cases wherein reference-equality

* semantics are required.</b>

*

* <p>A typical use of this class is <i>topology-preserving object graph

* transformations</i>, such as serialization or deep-copying. To perform such

* a transformation, a program must maintain a "node table" that keeps track

* of all the object references that have already been processed. The node

* table must not equate distinct objects even if they happen to be equal.

* Another typical use of this class is to maintain <i>proxy objects</i>. For

* example, a debugging facility might wish to maintain a proxy object for

* each object in the program being debugged.

*

* <p>This class provides all of the optional map operations, and permits

* <tt>null</tt> values and the <tt>null</tt> key. This class makes no

* guarantees as to the order of the map; in particular, it does not guarantee

* that the order will remain constant over time.

*

* <p>This class provides constant-time performance for the basic

* operations (<tt>get</tt> and <tt>put</tt>), assuming the system

* identity hash function ({@link System#identityHashCode(Object)})

* disperses elements properly among the buckets.

*

* <p>This class has one tuning parameter (which affects performance but not

* semantics): <i>expected maximum size</i>. This parameter is the maximum

* number of key-value mappings that the map is expected to hold. Internally,

* this parameter is used to determine the number of buckets initially

* comprising the hash table. The precise relationship between the expected

* maximum size and the number of buckets is unspecified.

*

* <p>If the size of the map (the number of key-value mappings) sufficiently

* exceeds the expected maximum size, the number of buckets is increased

* Increasing the number of buckets ("rehashing") may be fairly expensive, so

* it pays to create identity hash maps with a sufficiently large expected

* maximum size. On the other hand, iteration over collection views requires

* time proportional to the number of buckets in the hash table, so it

* pays not to set the expected maximum size too high if you are especially

* concerned with iteration performance or memory usage.

*

* <p><strong>Note that this implementation is not synchronized.</strong>

* If multiple threads access an identity hash map concurrently, and at

* least one of the threads modifies the map structurally, it <i>must</i>

* be synchronized externally. (A structural modification is any operation

* that adds or deletes one or more mappings; merely changing the value

* associated with a key that an instance already contains is not a

* structural modification.) This is typically accomplished by

* synchronizing on some object that naturally encapsulates the map.

*

* If no such object exists, the map should be "wrapped" using the

* {@link Collections#synchronizedMap Collections.synchronizedMap}

* method. This is best done at creation time, to prevent accidental

* unsynchronized access to the map:<pre>

* Map m = Collections.synchronizedMap(new IdentityHashMap(...));</pre>

*

* <p>The iterators returned by the <tt>iterator</tt> method of the

* collections returned by all of this class's "collection view

* methods" are <i>fail-fast</i>: if the map is structurally modified

* at any time after the iterator is created, in any way except

* through the iterator's own <tt>remove</tt> method, the iterator

* will throw a {@link ConcurrentModificationException}. Thus, in the

* face of concurrent modification, the iterator fails quickly and

* cleanly, rather than risking arbitrary, non-deterministic behavior

* at an undetermined time in the future.

*

* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed

* as it is, generally speaking, impossible to make any hard guarantees in the

* presence of unsynchronized concurrent modification. Fail-fast iterators

* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.

* Therefore, it would be wrong to write a program that depended on this

* exception for its correctness: <i>fail-fast iterators should be used only

* to detect bugs.</i>

*

* <p>Implementation note: This is a simple <i>linear-probe</i> hash table,

* as described for example in texts by Sedgewick and Knuth. The array

* alternates holding keys and values. (This has better locality for large

* tables than does using separate arrays.) For many JRE implementations

* and operation mixes, this class will yield better performance than

* {@link HashMap} (which uses <i>chaining</i> rather than linear-probing).

*

* <p>This class is a member of the

* <a href="{@docRoot}/../technotes/guides/collections/index.html">

* Java Collections Framework</a>.

*

* @see System#identityHashCode(Object)

* @see Object#hashCode()

* @see Collection

* @see Map

* @see HashMap

* @see TreeMap

* @author Doug Lea and Josh Bloch

* @since 1.4

*/

public class IdentityHashMap<K,V>

extends AbstractMap<K,V>

implements Map<K,V>, java.io.Serializable, Cloneable

{

/**

* The initial capacity used by the no-args constructor.

* MUST be a power of two. The value 32 corresponds to the

* (specified) expected maximum size of 21, given a load factor

* of 2/3.

*/

private static final int DEFAULT_CAPACITY = 32;

/**

* The minimum capacity, used if a lower value is implicitly specified

* by either of the constructors with arguments. The value 4 corresponds

* to an expected maximum size of 2, given a load factor of 2/3.

* MUST be a power of two.

*/

private static final int MINIMUM_CAPACITY = 4;

/**

* The maximum capacity, used if a higher value is implicitly specified

* by either of the constructors with arguments.

* MUST be a power of two <= 1<<29.

*/

private static final int MAXIMUM_CAPACITY = 1 << 29;

/**

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

*/

transient Object[] table; // non-private to simplify nested class access

/**

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

*

* @serial

*/

int size;

/**

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

*/

transient int modCount;

/**

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

*/

private transient int threshold;

/**

* Value representing null keys inside tables.

*/

static final Object NULL_KEY = new Object();

/**

* Use NULL_KEY for key if it is null.

*/

private static Object maskNull(Object key) {

return (key == null ? NULL_KEY : key);

}

/**

* Returns internal representation of null key back to caller as null.

*/

static final Object unmaskNull(Object key) {

return (key == NULL_KEY ? null : key);

}

/**

* Constructs a new, empty identity hash map with a default expected

* maximum size (21).

*/

public IdentityHashMap() {

init(DEFAULT_CAPACITY);

}

/**

* Constructs a new, empty map with the specified expected maximum size.

* Putting more than the expected number of key-value mappings into

* the map may cause the internal data structure to grow, which may be

* somewhat time-consuming.

*

* @param expectedMaxSize the expected maximum size of the map

* @throws IllegalArgumentException if <tt>expectedMaxSize</tt> is negative

*/

public IdentityHashMap(int expectedMaxSize) {

if (expectedMaxSize < 0)

throw new IllegalArgumentException("expectedMaxSize is negative: "

+ expectedMaxSize);

init(capacity(expectedMaxSize));

}

/**

* Returns the appropriate capacity for the 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)

*/

@SuppressWarnings("unchecked")

public V get(Object key) {

Object k = maskNull(key);

Object[] tab = table;

int len = tab.length;

int i = hash(k, len);

while (true) {

Object item = tab[i];

if (item == k)

return (V) tab[i + 1];

if (item == null)

return null;

i = nextKeyIndex(i, len);

}

}

/**

* Tests whether the specified object reference is a key in this identity

* hash map.

*

* @param key possible key

* @return <code>true</code> if the specified object reference is a key

* in this map

* @see #containsValue(Object)

*/

public boolean containsKey(Object key) {

Object k = maskNull(key);

Object[] tab = table;

int len = tab.length;

int i = hash(k, len);

while (true) {

Object item = tab[i];

if (item == k)

return true;

if (item == null)

return false;

i = nextKeyIndex(i, len);

}

}

/**

* Tests whether the specified object reference is a value in this identity

* hash map.

*

* @param value value whose presence in this map is to be tested

* @return <tt>true</tt> if this map maps one or more keys to the

* specified object reference

* @see #containsKey(Object)

*/

public boolean containsValue(Object value) {

Object[] tab = table;

for (int i = 1; i < tab.length; i += 2)

if (tab[i] == value && tab[i - 1] != null)

return true;

return false;

}

/**

* Tests if the specified key-value mapping is in the map.

*

* @param key possible key

* @param value possible value

* @return <code>true</code> if and only if the specified key-value

* mapping is in the map

*/

private boolean containsMapping(Object key, Object value) {

Object k = maskNull(key);

Object[] tab = table;

int len = tab.length;

int i = hash(k, len);

while (true) {

Object item = tab[i];

if (item == k)

return tab[i + 1] == value;

if (item == null)

return false;

i = nextKeyIndex(i, len);

}

}

/**

* Associates the specified value with the specified key in this identity

* hash map. If the map previously contained a mapping for the key, the

* old value is replaced.

*

* @param key the key with which the specified value is to be associated

* @param value the value to be associated with the specified key

* @return the previous value associated with <tt>key</tt>, or

* <tt>null</tt> if there was no mapping for <tt>key</tt>.

* (A <tt>null</tt> return can also indicate that the map

* previously associated <tt>null</tt> with <tt>key</tt>.)

* @see Object#equals(Object)

* @see #get(Object)

* @see #containsKey(Object)

*/

public V put(K key, V value) {

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

@SuppressWarnings("unchecked")

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

@SuppressWarnings("unchecked")

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

tab[i + 1] = null;

tab[i] = null;

closeDeletion(i);

return oldValue;

}

if (item == null)

return null;

i = nextKeyIndex(i, len);

}

}

/**

* Removes the specified key-value mapping from the map if it is present.

*

* @param key possible key

* @param value possible value

* @return <code>true</code> if and only if the specified key-value

* mapping was in the map

*/

private boolean removeMapping(Object key, Object value) {

Object k = maskNull(key);

Object[] tab = table;

int len = tab.length;

int i = hash(k, len);

while (true) {

Object item = tab[i];

if (item == k) {

if (tab[i + 1] != value)

return false;

modCount++;

size--;

tab[i] = null;

tab[i + 1] = null;

closeDeletion(i);

return true;

}

if (item == null)

return false;

i = nextKeyIndex(i, len);

}

}

/**

* Rehash all possibly-colliding entries following a

* deletion. This preserves the linear-probe

* collision properties required by get, put, etc.

*

* @param d the index of a newly empty deleted slot

*/

private void closeDeletion(int d) {

// Adapted from Knuth Section 6.4 Algorithm R

Object[] tab = table;

int len = tab.length;

// Look for items to swap into newly vacated slot

// starting at index immediately following deletion,

// and continuing until a null slot is seen, indicating

// the end of a run of possibly-colliding keys.

Object item;

for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;

i = nextKeyIndex(i, len) ) {

// The following test triggers if the item at slot i (which

// hashes to be at slot r) should take the spot vacated by d.

// If so, we swap it in, and then continue with d now at the

// newly vacated i. This process will terminate when we hit

// the null slot at the end of this run.

// The test is messy because we are using a circular table.

int r = hash(item, len);

if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {

tab[d] = item;

tab[d + 1] = tab[i + 1];

tab[i] = null;

tab[i + 1] = null;

d = i;

}

}

}

/**

* Removes all of the mappings from this map.

* The map will be empty after this call returns.

*/

public void clear() {

modCount++;

Object[] tab = table;

for (int i = 0; i < tab.length; i++)

tab[i] = null;

size = 0;

}

/**

* Compares the specified object with this map for equality. Returns

* <tt>true</tt> if the given object is also a map and the two maps

* represent identical object-reference mappings. More formally, this

* map is equal to another map <tt>m</tt> if and only if

* <tt>this.entrySet().equals(m.entrySet())</tt>.

*

* <p><b>Owing to the reference-equality-based semantics of this map it is

* possible that the symmetry and transitivity requirements of the

* <tt>Object.equals</tt> contract may be violated if this map is compared

* to a normal map. However, the <tt>Object.equals</tt> contract is

* guaranteed to hold among <tt>IdentityHashMap</tt> instances.</b>

*

* @param o object to be compared for equality with this map

* @return <tt>true</tt> if the specified object is equal to this map

* @see Object#equals(Object)

*/

public boolean equals(Object o) {

if (o == this) {

return true;

} else if (o instanceof IdentityHashMap) {

IdentityHashMap<?,?> m = (IdentityHashMap<?,?>) o;

if (m.size() != size)

return false;

Object[] tab = m.table;

for (int i = 0; i < tab.length; i+=2) {

Object k = tab[i];

if (k != null && !containsMapping(k, tab[i + 1]))

return false;

}

return true;

} else if (o instanceof Map) {

Map<?,?> m = (Map<?,?>)o;

return entrySet().equals(m.entrySet());

} else {

return false; // o is not a Map

}

}

/**

* Returns the hash code value for this map. The hash code of a map is

* defined to be the sum of the hash codes of each entry in the map's

* <tt>entrySet()</tt> view. This ensures that <tt>m1.equals(m2)</tt>

* implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two

* <tt>IdentityHashMap</tt> instances <tt>m1</tt> and <tt>m2</tt>, as

* required by the general contract of {@link Object#hashCode}.

*

* <p><b>Owing to the reference-equality-based semantics of the

* <tt>Map.Entry</tt> instances in the set returned by this map's

* <tt>entrySet</tt> method, it is possible that the contractual

* requirement of <tt>Object.hashCode</tt> mentioned in the previous

* paragraph will be violated if one of the two objects being compared is

* an <tt>IdentityHashMap</tt> instance and the other is a normal map.</b>

*

* @return the hash code value for this map

* @see Object#equals(Object)

* @see #equals(Object)

*/

public int hashCode() {

int result = 0;

Object[] tab = table;

for (int i = 0; i < tab.length; i +=2) {

Object key = tab[i];

if (key != null) {

Object k = unmaskNull(key);

result += System.identityHashCode(k) ^

System.identityHashCode(tab[i + 1]);

}

}

return result;

}

/**

* Returns a shallow copy of this identity hash map: the keys and values

* themselves are not cloned.

*

* @return a shallow copy of this map

*/

public Object clone() {

try {

IdentityHashMap<?,?> m = (IdentityHashMap<?,?>) super.clone();

m.entrySet = null;

m.table = table.clone();

return m;

} catch (CloneNotSupportedException e) {

throw new InternalError(e);

}

}

private abstract class IdentityHashMapIterator<T> implements Iterator<T> {

int index = (size != 0 ? 0 : table.length); // current slot.

int expectedModCount = modCount; // to support fast-fail

int lastReturnedIndex = -1; // to allow remove()

boolean indexValid; // To avoid unnecessary next computation

Object[] traversalTable = table; // reference to main table or copy

public boolean hasNext() {

Object[] tab = traversalTable;

for (int i = index; i < tab.length; i+=2) {

Object key = tab[i];

if (key != null) {

index = i;

return indexValid = true;

}

}

index = tab.length;

return false;

}

protected int nextIndex() {

if (modCount != expectedModCount)

throw new ConcurrentModificationException();

if (!indexValid && !hasNext())

throw new NoSuchElementException();

indexValid = false;

lastReturnedIndex = index;

index += 2;

return lastReturnedIndex;

}

public void remove() {

if (lastReturnedIndex == -1)

throw new IllegalStateException();

if (modCount != expectedModCount)

throw new ConcurrentModificationException();

expectedModCount = ++modCount;

int deletedSlot = lastReturnedIndex;

lastReturnedIndex = -1;

// back up index to revisit new contents after deletion

index = deletedSlot;

indexValid = false;

// Removal code proceeds as in closeDeletion except that

// it must catch the rare case where an element already

// seen is swapped into a vacant slot that will be later

// traversed by this iterator. We cannot allow future

// next() calls to return it again. The likelihood of

// this occurring under 2/3 load factor is very slim, but

// when it does happen, we must make a copy of the rest of

// the table to use for the rest of the traversal. Since

// this can only happen when we are near the end of the table,

// even in these rare cases, this is not very expensive in

// time or space.

Object[] tab = traversalTable;

int len = tab.length;

int d = deletedSlot;

Object key = tab[d];

tab[d] = null; // vacate the slot

tab[d + 1] = null;

// If traversing a copy, remove in real table.

// We can skip gap-closure on copy.

if (tab != IdentityHashMap.this.table) {

IdentityHashMap.this.remove(key);

expectedModCount = modCount;

return;

}

size--;

Object item;

for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;

i = nextKeyIndex(i, len)) {

int r = hash(item, len);

// See closeDeletion for explanation of this conditional

if ((i < r && (r <= d || d <= i)) ||

(r <= d && d <= i)) {

// If we are about to swap an already-seen element

// into a slot that may later be returned by next(),

// then clone the rest of table for use in future

// next() calls. It is OK that our copy will have

// a gap in the "wrong" place, since it will never

// be used for searching anyway.

if (i < deletedSlot && d >= deletedSlot &&

traversalTable == IdentityHashMap.this.table) {

int remaining = len - deletedSlot;

Object[] newTable = new Object[remaining];

System.arraycopy(tab, deletedSlot,

newTable, 0, remaining);

traversalTable = newTable;

index = 0;

}

tab[d] = item;

tab[d + 1] = tab[i + 1];

tab[i] = null;

tab[i + 1] = null;

d = i;

}

}

}

}

private class KeyIterator extends IdentityHashMapIterator<K> {

@SuppressWarnings("unchecked")

public K next() {

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

}

}

private class ValueIterator extends IdentityHashMapIterator<V> {

@SuppressWarnings("unchecked")

public V next() {

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

}

}

private class EntryIterator

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

{

private Entry lastReturnedEntry = 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;

}

@SuppressWarnings("unchecked")

public K getKey() {

checkIndexForEntryUse();

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

}

@SuppressWarnings("unchecked")

public V getValue() {

checkIndexForEntryUse();

return (V) traversalTable[index+1];

}

@SuppressWarnings("unchecked")

public V setValue(V value) {

checkIndexForEntryUse();

V oldValue = (V) traversalTable[index+1];

traversalTable[index+1] = value;

// if shadowing, force into main table

if (traversalTable != IdentityHashMap.this.table)

put((K) traversalTable[index], value);

return oldValue;

}

public boolean equals(Object o) {

if (index < 0)

return super.equals(o);

if (!(o instanceof Map.Entry))

return false;

Map.Entry<?,?> e = (Map.Entry<?,?>)o;

return (e.getKey() == unmaskNull(traversalTable[index]) &&

e.getValue() == traversalTable[index+1]);

}

public int hashCode() {

if (lastReturnedIndex < 0)

return super.hashCode();

return (System.identityHashCode(unmaskNull(traversalTable[index])) ^

System.identityHashCode(traversalTable[index+1]));

}

public String toString() {

if (index < 0)

return super.toString();

return (unmaskNull(traversalTable[index]) + "="

+ traversalTable[index+1]);

}

private void checkIndexForEntryUse() {

if (index < 0)

throw new IllegalStateException("Entry was removed");

}

}

}

// Views

/**

* This field is initialized to contain an instance of the entry set

* view the first time this view is requested. The view is stateless,

* so there's no reason to create more than one.

*/

private transient Set<Map.Entry<K,V>> entrySet = 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) {

Objects.requireNonNull(c);