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