1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/emul/compact/src/main/java/java/util/IdentityHashMap.java Sat Sep 07 13:51:24 2013 +0200
1.3 @@ -0,0 +1,1243 @@
1.4 +/*
1.5 + * Copyright (c) 2000, 2011, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation. Oracle designates this
1.11 + * particular file as subject to the "Classpath" exception as provided
1.12 + * by Oracle in the LICENSE file that accompanied this code.
1.13 + *
1.14 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.15 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.16 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.17 + * version 2 for more details (a copy is included in the LICENSE file that
1.18 + * accompanied this code).
1.19 + *
1.20 + * You should have received a copy of the GNU General Public License version
1.21 + * 2 along with this work; if not, write to the Free Software Foundation,
1.22 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.23 + *
1.24 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.25 + * or visit www.oracle.com if you need additional information or have any
1.26 + * questions.
1.27 + */
1.28 +
1.29 +package java.util;
1.30 +import java.io.*;
1.31 +
1.32 +/**
1.33 + * This class implements the <tt>Map</tt> interface with a hash table, using
1.34 + * reference-equality in place of object-equality when comparing keys (and
1.35 + * values). In other words, in an <tt>IdentityHashMap</tt>, two keys
1.36 + * <tt>k1</tt> and <tt>k2</tt> are considered equal if and only if
1.37 + * <tt>(k1==k2)</tt>. (In normal <tt>Map</tt> implementations (like
1.38 + * <tt>HashMap</tt>) two keys <tt>k1</tt> and <tt>k2</tt> are considered equal
1.39 + * if and only if <tt>(k1==null ? k2==null : k1.equals(k2))</tt>.)
1.40 + *
1.41 + * <p><b>This class is <i>not</i> a general-purpose <tt>Map</tt>
1.42 + * implementation! While this class implements the <tt>Map</tt> interface, it
1.43 + * intentionally violates <tt>Map's</tt> general contract, which mandates the
1.44 + * use of the <tt>equals</tt> method when comparing objects. This class is
1.45 + * designed for use only in the rare cases wherein reference-equality
1.46 + * semantics are required.</b>
1.47 + *
1.48 + * <p>A typical use of this class is <i>topology-preserving object graph
1.49 + * transformations</i>, such as serialization or deep-copying. To perform such
1.50 + * a transformation, a program must maintain a "node table" that keeps track
1.51 + * of all the object references that have already been processed. The node
1.52 + * table must not equate distinct objects even if they happen to be equal.
1.53 + * Another typical use of this class is to maintain <i>proxy objects</i>. For
1.54 + * example, a debugging facility might wish to maintain a proxy object for
1.55 + * each object in the program being debugged.
1.56 + *
1.57 + * <p>This class provides all of the optional map operations, and permits
1.58 + * <tt>null</tt> values and the <tt>null</tt> key. This class makes no
1.59 + * guarantees as to the order of the map; in particular, it does not guarantee
1.60 + * that the order will remain constant over time.
1.61 + *
1.62 + * <p>This class provides constant-time performance for the basic
1.63 + * operations (<tt>get</tt> and <tt>put</tt>), assuming the system
1.64 + * identity hash function ({@link System#identityHashCode(Object)})
1.65 + * disperses elements properly among the buckets.
1.66 + *
1.67 + * <p>This class has one tuning parameter (which affects performance but not
1.68 + * semantics): <i>expected maximum size</i>. This parameter is the maximum
1.69 + * number of key-value mappings that the map is expected to hold. Internally,
1.70 + * this parameter is used to determine the number of buckets initially
1.71 + * comprising the hash table. The precise relationship between the expected
1.72 + * maximum size and the number of buckets is unspecified.
1.73 + *
1.74 + * <p>If the size of the map (the number of key-value mappings) sufficiently
1.75 + * exceeds the expected maximum size, the number of buckets is increased
1.76 + * Increasing the number of buckets ("rehashing") may be fairly expensive, so
1.77 + * it pays to create identity hash maps with a sufficiently large expected
1.78 + * maximum size. On the other hand, iteration over collection views requires
1.79 + * time proportional to the number of buckets in the hash table, so it
1.80 + * pays not to set the expected maximum size too high if you are especially
1.81 + * concerned with iteration performance or memory usage.
1.82 + *
1.83 + * <p><strong>Note that this implementation is not synchronized.</strong>
1.84 + * If multiple threads access an identity hash map concurrently, and at
1.85 + * least one of the threads modifies the map structurally, it <i>must</i>
1.86 + * be synchronized externally. (A structural modification is any operation
1.87 + * that adds or deletes one or more mappings; merely changing the value
1.88 + * associated with a key that an instance already contains is not a
1.89 + * structural modification.) This is typically accomplished by
1.90 + * synchronizing on some object that naturally encapsulates the map.
1.91 + *
1.92 + * If no such object exists, the map should be "wrapped" using the
1.93 + * {@link Collections#synchronizedMap Collections.synchronizedMap}
1.94 + * method. This is best done at creation time, to prevent accidental
1.95 + * unsynchronized access to the map:<pre>
1.96 + * Map m = Collections.synchronizedMap(new IdentityHashMap(...));</pre>
1.97 + *
1.98 + * <p>The iterators returned by the <tt>iterator</tt> method of the
1.99 + * collections returned by all of this class's "collection view
1.100 + * methods" are <i>fail-fast</i>: if the map is structurally modified
1.101 + * at any time after the iterator is created, in any way except
1.102 + * through the iterator's own <tt>remove</tt> method, the iterator
1.103 + * will throw a {@link ConcurrentModificationException}. Thus, in the
1.104 + * face of concurrent modification, the iterator fails quickly and
1.105 + * cleanly, rather than risking arbitrary, non-deterministic behavior
1.106 + * at an undetermined time in the future.
1.107 + *
1.108 + * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
1.109 + * as it is, generally speaking, impossible to make any hard guarantees in the
1.110 + * presence of unsynchronized concurrent modification. Fail-fast iterators
1.111 + * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
1.112 + * Therefore, it would be wrong to write a program that depended on this
1.113 + * exception for its correctness: <i>fail-fast iterators should be used only
1.114 + * to detect bugs.</i>
1.115 + *
1.116 + * <p>Implementation note: This is a simple <i>linear-probe</i> hash table,
1.117 + * as described for example in texts by Sedgewick and Knuth. The array
1.118 + * alternates holding keys and values. (This has better locality for large
1.119 + * tables than does using separate arrays.) For many JRE implementations
1.120 + * and operation mixes, this class will yield better performance than
1.121 + * {@link HashMap} (which uses <i>chaining</i> rather than linear-probing).
1.122 + *
1.123 + * <p>This class is a member of the
1.124 + * <a href="{@docRoot}/../technotes/guides/collections/index.html">
1.125 + * Java Collections Framework</a>.
1.126 + *
1.127 + * @see System#identityHashCode(Object)
1.128 + * @see Object#hashCode()
1.129 + * @see Collection
1.130 + * @see Map
1.131 + * @see HashMap
1.132 + * @see TreeMap
1.133 + * @author Doug Lea and Josh Bloch
1.134 + * @since 1.4
1.135 + */
1.136 +
1.137 +public class IdentityHashMap<K,V>
1.138 + extends AbstractMap<K,V>
1.139 + implements Map<K,V>, java.io.Serializable, Cloneable
1.140 +{
1.141 + /**
1.142 + * The initial capacity used by the no-args constructor.
1.143 + * MUST be a power of two. The value 32 corresponds to the
1.144 + * (specified) expected maximum size of 21, given a load factor
1.145 + * of 2/3.
1.146 + */
1.147 + private static final int DEFAULT_CAPACITY = 32;
1.148 +
1.149 + /**
1.150 + * The minimum capacity, used if a lower value is implicitly specified
1.151 + * by either of the constructors with arguments. The value 4 corresponds
1.152 + * to an expected maximum size of 2, given a load factor of 2/3.
1.153 + * MUST be a power of two.
1.154 + */
1.155 + private static final int MINIMUM_CAPACITY = 4;
1.156 +
1.157 + /**
1.158 + * The maximum capacity, used if a higher value is implicitly specified
1.159 + * by either of the constructors with arguments.
1.160 + * MUST be a power of two <= 1<<29.
1.161 + */
1.162 + private static final int MAXIMUM_CAPACITY = 1 << 29;
1.163 +
1.164 + /**
1.165 + * The table, resized as necessary. Length MUST always be a power of two.
1.166 + */
1.167 + private transient Object[] table;
1.168 +
1.169 + /**
1.170 + * The number of key-value mappings contained in this identity hash map.
1.171 + *
1.172 + * @serial
1.173 + */
1.174 + private int size;
1.175 +
1.176 + /**
1.177 + * The number of modifications, to support fast-fail iterators
1.178 + */
1.179 + private transient int modCount;
1.180 +
1.181 + /**
1.182 + * The next size value at which to resize (capacity * load factor).
1.183 + */
1.184 + private transient int threshold;
1.185 +
1.186 + /**
1.187 + * Value representing null keys inside tables.
1.188 + */
1.189 + private static final Object NULL_KEY = new Object();
1.190 +
1.191 + /**
1.192 + * Use NULL_KEY for key if it is null.
1.193 + */
1.194 + private static Object maskNull(Object key) {
1.195 + return (key == null ? NULL_KEY : key);
1.196 + }
1.197 +
1.198 + /**
1.199 + * Returns internal representation of null key back to caller as null.
1.200 + */
1.201 + private static Object unmaskNull(Object key) {
1.202 + return (key == NULL_KEY ? null : key);
1.203 + }
1.204 +
1.205 + /**
1.206 + * Constructs a new, empty identity hash map with a default expected
1.207 + * maximum size (21).
1.208 + */
1.209 + public IdentityHashMap() {
1.210 + init(DEFAULT_CAPACITY);
1.211 + }
1.212 +
1.213 + /**
1.214 + * Constructs a new, empty map with the specified expected maximum size.
1.215 + * Putting more than the expected number of key-value mappings into
1.216 + * the map may cause the internal data structure to grow, which may be
1.217 + * somewhat time-consuming.
1.218 + *
1.219 + * @param expectedMaxSize the expected maximum size of the map
1.220 + * @throws IllegalArgumentException if <tt>expectedMaxSize</tt> is negative
1.221 + */
1.222 + public IdentityHashMap(int expectedMaxSize) {
1.223 + if (expectedMaxSize < 0)
1.224 + throw new IllegalArgumentException("expectedMaxSize is negative: "
1.225 + + expectedMaxSize);
1.226 + init(capacity(expectedMaxSize));
1.227 + }
1.228 +
1.229 + /**
1.230 + * Returns the appropriate capacity for the specified expected maximum
1.231 + * size. Returns the smallest power of two between MINIMUM_CAPACITY
1.232 + * and MAXIMUM_CAPACITY, inclusive, that is greater than
1.233 + * (3 * expectedMaxSize)/2, if such a number exists. Otherwise
1.234 + * returns MAXIMUM_CAPACITY. If (3 * expectedMaxSize)/2 is negative, it
1.235 + * is assumed that overflow has occurred, and MAXIMUM_CAPACITY is returned.
1.236 + */
1.237 + private int capacity(int expectedMaxSize) {
1.238 + // Compute min capacity for expectedMaxSize given a load factor of 2/3
1.239 + int minCapacity = (3 * expectedMaxSize)/2;
1.240 +
1.241 + // Compute the appropriate capacity
1.242 + int result;
1.243 + if (minCapacity > MAXIMUM_CAPACITY || minCapacity < 0) {
1.244 + result = MAXIMUM_CAPACITY;
1.245 + } else {
1.246 + result = MINIMUM_CAPACITY;
1.247 + while (result < minCapacity)
1.248 + result <<= 1;
1.249 + }
1.250 + return result;
1.251 + }
1.252 +
1.253 + /**
1.254 + * Initializes object to be an empty map with the specified initial
1.255 + * capacity, which is assumed to be a power of two between
1.256 + * MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
1.257 + */
1.258 + private void init(int initCapacity) {
1.259 + // assert (initCapacity & -initCapacity) == initCapacity; // power of 2
1.260 + // assert initCapacity >= MINIMUM_CAPACITY;
1.261 + // assert initCapacity <= MAXIMUM_CAPACITY;
1.262 +
1.263 + threshold = (initCapacity * 2)/3;
1.264 + table = new Object[2 * initCapacity];
1.265 + }
1.266 +
1.267 + /**
1.268 + * Constructs a new identity hash map containing the keys-value mappings
1.269 + * in the specified map.
1.270 + *
1.271 + * @param m the map whose mappings are to be placed into this map
1.272 + * @throws NullPointerException if the specified map is null
1.273 + */
1.274 + public IdentityHashMap(Map<? extends K, ? extends V> m) {
1.275 + // Allow for a bit of growth
1.276 + this((int) ((1 + m.size()) * 1.1));
1.277 + putAll(m);
1.278 + }
1.279 +
1.280 + /**
1.281 + * Returns the number of key-value mappings in this identity hash map.
1.282 + *
1.283 + * @return the number of key-value mappings in this map
1.284 + */
1.285 + public int size() {
1.286 + return size;
1.287 + }
1.288 +
1.289 + /**
1.290 + * Returns <tt>true</tt> if this identity hash map contains no key-value
1.291 + * mappings.
1.292 + *
1.293 + * @return <tt>true</tt> if this identity hash map contains no key-value
1.294 + * mappings
1.295 + */
1.296 + public boolean isEmpty() {
1.297 + return size == 0;
1.298 + }
1.299 +
1.300 + /**
1.301 + * Returns index for Object x.
1.302 + */
1.303 + private static int hash(Object x, int length) {
1.304 + int h = System.identityHashCode(x);
1.305 + // Multiply by -127, and left-shift to use least bit as part of hash
1.306 + return ((h << 1) - (h << 8)) & (length - 1);
1.307 + }
1.308 +
1.309 + /**
1.310 + * Circularly traverses table of size len.
1.311 + */
1.312 + private static int nextKeyIndex(int i, int len) {
1.313 + return (i + 2 < len ? i + 2 : 0);
1.314 + }
1.315 +
1.316 + /**
1.317 + * Returns the value to which the specified key is mapped,
1.318 + * or {@code null} if this map contains no mapping for the key.
1.319 + *
1.320 + * <p>More formally, if this map contains a mapping from a key
1.321 + * {@code k} to a value {@code v} such that {@code (key == k)},
1.322 + * then this method returns {@code v}; otherwise it returns
1.323 + * {@code null}. (There can be at most one such mapping.)
1.324 + *
1.325 + * <p>A return value of {@code null} does not <i>necessarily</i>
1.326 + * indicate that the map contains no mapping for the key; it's also
1.327 + * possible that the map explicitly maps the key to {@code null}.
1.328 + * The {@link #containsKey containsKey} operation may be used to
1.329 + * distinguish these two cases.
1.330 + *
1.331 + * @see #put(Object, Object)
1.332 + */
1.333 + public V get(Object key) {
1.334 + Object k = maskNull(key);
1.335 + Object[] tab = table;
1.336 + int len = tab.length;
1.337 + int i = hash(k, len);
1.338 + while (true) {
1.339 + Object item = tab[i];
1.340 + if (item == k)
1.341 + return (V) tab[i + 1];
1.342 + if (item == null)
1.343 + return null;
1.344 + i = nextKeyIndex(i, len);
1.345 + }
1.346 + }
1.347 +
1.348 + /**
1.349 + * Tests whether the specified object reference is a key in this identity
1.350 + * hash map.
1.351 + *
1.352 + * @param key possible key
1.353 + * @return <code>true</code> if the specified object reference is a key
1.354 + * in this map
1.355 + * @see #containsValue(Object)
1.356 + */
1.357 + public boolean containsKey(Object key) {
1.358 + Object k = maskNull(key);
1.359 + Object[] tab = table;
1.360 + int len = tab.length;
1.361 + int i = hash(k, len);
1.362 + while (true) {
1.363 + Object item = tab[i];
1.364 + if (item == k)
1.365 + return true;
1.366 + if (item == null)
1.367 + return false;
1.368 + i = nextKeyIndex(i, len);
1.369 + }
1.370 + }
1.371 +
1.372 + /**
1.373 + * Tests whether the specified object reference is a value in this identity
1.374 + * hash map.
1.375 + *
1.376 + * @param value value whose presence in this map is to be tested
1.377 + * @return <tt>true</tt> if this map maps one or more keys to the
1.378 + * specified object reference
1.379 + * @see #containsKey(Object)
1.380 + */
1.381 + public boolean containsValue(Object value) {
1.382 + Object[] tab = table;
1.383 + for (int i = 1; i < tab.length; i += 2)
1.384 + if (tab[i] == value && tab[i - 1] != null)
1.385 + return true;
1.386 +
1.387 + return false;
1.388 + }
1.389 +
1.390 + /**
1.391 + * Tests if the specified key-value mapping is in the map.
1.392 + *
1.393 + * @param key possible key
1.394 + * @param value possible value
1.395 + * @return <code>true</code> if and only if the specified key-value
1.396 + * mapping is in the map
1.397 + */
1.398 + private boolean containsMapping(Object key, Object value) {
1.399 + Object k = maskNull(key);
1.400 + Object[] tab = table;
1.401 + int len = tab.length;
1.402 + int i = hash(k, len);
1.403 + while (true) {
1.404 + Object item = tab[i];
1.405 + if (item == k)
1.406 + return tab[i + 1] == value;
1.407 + if (item == null)
1.408 + return false;
1.409 + i = nextKeyIndex(i, len);
1.410 + }
1.411 + }
1.412 +
1.413 + /**
1.414 + * Associates the specified value with the specified key in this identity
1.415 + * hash map. If the map previously contained a mapping for the key, the
1.416 + * old value is replaced.
1.417 + *
1.418 + * @param key the key with which the specified value is to be associated
1.419 + * @param value the value to be associated with the specified key
1.420 + * @return the previous value associated with <tt>key</tt>, or
1.421 + * <tt>null</tt> if there was no mapping for <tt>key</tt>.
1.422 + * (A <tt>null</tt> return can also indicate that the map
1.423 + * previously associated <tt>null</tt> with <tt>key</tt>.)
1.424 + * @see Object#equals(Object)
1.425 + * @see #get(Object)
1.426 + * @see #containsKey(Object)
1.427 + */
1.428 + public V put(K key, V value) {
1.429 + Object k = maskNull(key);
1.430 + Object[] tab = table;
1.431 + int len = tab.length;
1.432 + int i = hash(k, len);
1.433 +
1.434 + Object item;
1.435 + while ( (item = tab[i]) != null) {
1.436 + if (item == k) {
1.437 + V oldValue = (V) tab[i + 1];
1.438 + tab[i + 1] = value;
1.439 + return oldValue;
1.440 + }
1.441 + i = nextKeyIndex(i, len);
1.442 + }
1.443 +
1.444 + modCount++;
1.445 + tab[i] = k;
1.446 + tab[i + 1] = value;
1.447 + if (++size >= threshold)
1.448 + resize(len); // len == 2 * current capacity.
1.449 + return null;
1.450 + }
1.451 +
1.452 + /**
1.453 + * Resize the table to hold given capacity.
1.454 + *
1.455 + * @param newCapacity the new capacity, must be a power of two.
1.456 + */
1.457 + private void resize(int newCapacity) {
1.458 + // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
1.459 + int newLength = newCapacity * 2;
1.460 +
1.461 + Object[] oldTable = table;
1.462 + int oldLength = oldTable.length;
1.463 + if (oldLength == 2*MAXIMUM_CAPACITY) { // can't expand any further
1.464 + if (threshold == MAXIMUM_CAPACITY-1)
1.465 + throw new IllegalStateException("Capacity exhausted.");
1.466 + threshold = MAXIMUM_CAPACITY-1; // Gigantic map!
1.467 + return;
1.468 + }
1.469 + if (oldLength >= newLength)
1.470 + return;
1.471 +
1.472 + Object[] newTable = new Object[newLength];
1.473 + threshold = newLength / 3;
1.474 +
1.475 + for (int j = 0; j < oldLength; j += 2) {
1.476 + Object key = oldTable[j];
1.477 + if (key != null) {
1.478 + Object value = oldTable[j+1];
1.479 + oldTable[j] = null;
1.480 + oldTable[j+1] = null;
1.481 + int i = hash(key, newLength);
1.482 + while (newTable[i] != null)
1.483 + i = nextKeyIndex(i, newLength);
1.484 + newTable[i] = key;
1.485 + newTable[i + 1] = value;
1.486 + }
1.487 + }
1.488 + table = newTable;
1.489 + }
1.490 +
1.491 + /**
1.492 + * Copies all of the mappings from the specified map to this map.
1.493 + * These mappings will replace any mappings that this map had for
1.494 + * any of the keys currently in the specified map.
1.495 + *
1.496 + * @param m mappings to be stored in this map
1.497 + * @throws NullPointerException if the specified map is null
1.498 + */
1.499 + public void putAll(Map<? extends K, ? extends V> m) {
1.500 + int n = m.size();
1.501 + if (n == 0)
1.502 + return;
1.503 + if (n > threshold) // conservatively pre-expand
1.504 + resize(capacity(n));
1.505 +
1.506 + for (Entry<? extends K, ? extends V> e : m.entrySet())
1.507 + put(e.getKey(), e.getValue());
1.508 + }
1.509 +
1.510 + /**
1.511 + * Removes the mapping for this key from this map if present.
1.512 + *
1.513 + * @param key key whose mapping is to be removed from the map
1.514 + * @return the previous value associated with <tt>key</tt>, or
1.515 + * <tt>null</tt> if there was no mapping for <tt>key</tt>.
1.516 + * (A <tt>null</tt> return can also indicate that the map
1.517 + * previously associated <tt>null</tt> with <tt>key</tt>.)
1.518 + */
1.519 + public V remove(Object key) {
1.520 + Object k = maskNull(key);
1.521 + Object[] tab = table;
1.522 + int len = tab.length;
1.523 + int i = hash(k, len);
1.524 +
1.525 + while (true) {
1.526 + Object item = tab[i];
1.527 + if (item == k) {
1.528 + modCount++;
1.529 + size--;
1.530 + V oldValue = (V) tab[i + 1];
1.531 + tab[i + 1] = null;
1.532 + tab[i] = null;
1.533 + closeDeletion(i);
1.534 + return oldValue;
1.535 + }
1.536 + if (item == null)
1.537 + return null;
1.538 + i = nextKeyIndex(i, len);
1.539 + }
1.540 +
1.541 + }
1.542 +
1.543 + /**
1.544 + * Removes the specified key-value mapping from the map if it is present.
1.545 + *
1.546 + * @param key possible key
1.547 + * @param value possible value
1.548 + * @return <code>true</code> if and only if the specified key-value
1.549 + * mapping was in the map
1.550 + */
1.551 + private boolean removeMapping(Object key, Object value) {
1.552 + Object k = maskNull(key);
1.553 + Object[] tab = table;
1.554 + int len = tab.length;
1.555 + int i = hash(k, len);
1.556 +
1.557 + while (true) {
1.558 + Object item = tab[i];
1.559 + if (item == k) {
1.560 + if (tab[i + 1] != value)
1.561 + return false;
1.562 + modCount++;
1.563 + size--;
1.564 + tab[i] = null;
1.565 + tab[i + 1] = null;
1.566 + closeDeletion(i);
1.567 + return true;
1.568 + }
1.569 + if (item == null)
1.570 + return false;
1.571 + i = nextKeyIndex(i, len);
1.572 + }
1.573 + }
1.574 +
1.575 + /**
1.576 + * Rehash all possibly-colliding entries following a
1.577 + * deletion. This preserves the linear-probe
1.578 + * collision properties required by get, put, etc.
1.579 + *
1.580 + * @param d the index of a newly empty deleted slot
1.581 + */
1.582 + private void closeDeletion(int d) {
1.583 + // Adapted from Knuth Section 6.4 Algorithm R
1.584 + Object[] tab = table;
1.585 + int len = tab.length;
1.586 +
1.587 + // Look for items to swap into newly vacated slot
1.588 + // starting at index immediately following deletion,
1.589 + // and continuing until a null slot is seen, indicating
1.590 + // the end of a run of possibly-colliding keys.
1.591 + Object item;
1.592 + for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
1.593 + i = nextKeyIndex(i, len) ) {
1.594 + // The following test triggers if the item at slot i (which
1.595 + // hashes to be at slot r) should take the spot vacated by d.
1.596 + // If so, we swap it in, and then continue with d now at the
1.597 + // newly vacated i. This process will terminate when we hit
1.598 + // the null slot at the end of this run.
1.599 + // The test is messy because we are using a circular table.
1.600 + int r = hash(item, len);
1.601 + if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
1.602 + tab[d] = item;
1.603 + tab[d + 1] = tab[i + 1];
1.604 + tab[i] = null;
1.605 + tab[i + 1] = null;
1.606 + d = i;
1.607 + }
1.608 + }
1.609 + }
1.610 +
1.611 + /**
1.612 + * Removes all of the mappings from this map.
1.613 + * The map will be empty after this call returns.
1.614 + */
1.615 + public void clear() {
1.616 + modCount++;
1.617 + Object[] tab = table;
1.618 + for (int i = 0; i < tab.length; i++)
1.619 + tab[i] = null;
1.620 + size = 0;
1.621 + }
1.622 +
1.623 + /**
1.624 + * Compares the specified object with this map for equality. Returns
1.625 + * <tt>true</tt> if the given object is also a map and the two maps
1.626 + * represent identical object-reference mappings. More formally, this
1.627 + * map is equal to another map <tt>m</tt> if and only if
1.628 + * <tt>this.entrySet().equals(m.entrySet())</tt>.
1.629 + *
1.630 + * <p><b>Owing to the reference-equality-based semantics of this map it is
1.631 + * possible that the symmetry and transitivity requirements of the
1.632 + * <tt>Object.equals</tt> contract may be violated if this map is compared
1.633 + * to a normal map. However, the <tt>Object.equals</tt> contract is
1.634 + * guaranteed to hold among <tt>IdentityHashMap</tt> instances.</b>
1.635 + *
1.636 + * @param o object to be compared for equality with this map
1.637 + * @return <tt>true</tt> if the specified object is equal to this map
1.638 + * @see Object#equals(Object)
1.639 + */
1.640 + public boolean equals(Object o) {
1.641 + if (o == this) {
1.642 + return true;
1.643 + } else if (o instanceof IdentityHashMap) {
1.644 + IdentityHashMap m = (IdentityHashMap) o;
1.645 + if (m.size() != size)
1.646 + return false;
1.647 +
1.648 + Object[] tab = m.table;
1.649 + for (int i = 0; i < tab.length; i+=2) {
1.650 + Object k = tab[i];
1.651 + if (k != null && !containsMapping(k, tab[i + 1]))
1.652 + return false;
1.653 + }
1.654 + return true;
1.655 + } else if (o instanceof Map) {
1.656 + Map m = (Map)o;
1.657 + return entrySet().equals(m.entrySet());
1.658 + } else {
1.659 + return false; // o is not a Map
1.660 + }
1.661 + }
1.662 +
1.663 + /**
1.664 + * Returns the hash code value for this map. The hash code of a map is
1.665 + * defined to be the sum of the hash codes of each entry in the map's
1.666 + * <tt>entrySet()</tt> view. This ensures that <tt>m1.equals(m2)</tt>
1.667 + * implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two
1.668 + * <tt>IdentityHashMap</tt> instances <tt>m1</tt> and <tt>m2</tt>, as
1.669 + * required by the general contract of {@link Object#hashCode}.
1.670 + *
1.671 + * <p><b>Owing to the reference-equality-based semantics of the
1.672 + * <tt>Map.Entry</tt> instances in the set returned by this map's
1.673 + * <tt>entrySet</tt> method, it is possible that the contractual
1.674 + * requirement of <tt>Object.hashCode</tt> mentioned in the previous
1.675 + * paragraph will be violated if one of the two objects being compared is
1.676 + * an <tt>IdentityHashMap</tt> instance and the other is a normal map.</b>
1.677 + *
1.678 + * @return the hash code value for this map
1.679 + * @see Object#equals(Object)
1.680 + * @see #equals(Object)
1.681 + */
1.682 + public int hashCode() {
1.683 + int result = 0;
1.684 + Object[] tab = table;
1.685 + for (int i = 0; i < tab.length; i +=2) {
1.686 + Object key = tab[i];
1.687 + if (key != null) {
1.688 + Object k = unmaskNull(key);
1.689 + result += System.identityHashCode(k) ^
1.690 + System.identityHashCode(tab[i + 1]);
1.691 + }
1.692 + }
1.693 + return result;
1.694 + }
1.695 +
1.696 + /**
1.697 + * Returns a shallow copy of this identity hash map: the keys and values
1.698 + * themselves are not cloned.
1.699 + *
1.700 + * @return a shallow copy of this map
1.701 + */
1.702 + public Object clone() {
1.703 + try {
1.704 + IdentityHashMap<K,V> m = (IdentityHashMap<K,V>) super.clone();
1.705 + m.entrySet = null;
1.706 + m.table = table.clone();
1.707 + return m;
1.708 + } catch (CloneNotSupportedException e) {
1.709 + throw new InternalError();
1.710 + }
1.711 + }
1.712 +
1.713 + private abstract class IdentityHashMapIterator<T> implements Iterator<T> {
1.714 + int index = (size != 0 ? 0 : table.length); // current slot.
1.715 + int expectedModCount = modCount; // to support fast-fail
1.716 + int lastReturnedIndex = -1; // to allow remove()
1.717 + boolean indexValid; // To avoid unnecessary next computation
1.718 + Object[] traversalTable = table; // reference to main table or copy
1.719 +
1.720 + public boolean hasNext() {
1.721 + Object[] tab = traversalTable;
1.722 + for (int i = index; i < tab.length; i+=2) {
1.723 + Object key = tab[i];
1.724 + if (key != null) {
1.725 + index = i;
1.726 + return indexValid = true;
1.727 + }
1.728 + }
1.729 + index = tab.length;
1.730 + return false;
1.731 + }
1.732 +
1.733 + protected int nextIndex() {
1.734 + if (modCount != expectedModCount)
1.735 + throw new ConcurrentModificationException();
1.736 + if (!indexValid && !hasNext())
1.737 + throw new NoSuchElementException();
1.738 +
1.739 + indexValid = false;
1.740 + lastReturnedIndex = index;
1.741 + index += 2;
1.742 + return lastReturnedIndex;
1.743 + }
1.744 +
1.745 + public void remove() {
1.746 + if (lastReturnedIndex == -1)
1.747 + throw new IllegalStateException();
1.748 + if (modCount != expectedModCount)
1.749 + throw new ConcurrentModificationException();
1.750 +
1.751 + expectedModCount = ++modCount;
1.752 + int deletedSlot = lastReturnedIndex;
1.753 + lastReturnedIndex = -1;
1.754 + // back up index to revisit new contents after deletion
1.755 + index = deletedSlot;
1.756 + indexValid = false;
1.757 +
1.758 + // Removal code proceeds as in closeDeletion except that
1.759 + // it must catch the rare case where an element already
1.760 + // seen is swapped into a vacant slot that will be later
1.761 + // traversed by this iterator. We cannot allow future
1.762 + // next() calls to return it again. The likelihood of
1.763 + // this occurring under 2/3 load factor is very slim, but
1.764 + // when it does happen, we must make a copy of the rest of
1.765 + // the table to use for the rest of the traversal. Since
1.766 + // this can only happen when we are near the end of the table,
1.767 + // even in these rare cases, this is not very expensive in
1.768 + // time or space.
1.769 +
1.770 + Object[] tab = traversalTable;
1.771 + int len = tab.length;
1.772 +
1.773 + int d = deletedSlot;
1.774 + K key = (K) tab[d];
1.775 + tab[d] = null; // vacate the slot
1.776 + tab[d + 1] = null;
1.777 +
1.778 + // If traversing a copy, remove in real table.
1.779 + // We can skip gap-closure on copy.
1.780 + if (tab != IdentityHashMap.this.table) {
1.781 + IdentityHashMap.this.remove(key);
1.782 + expectedModCount = modCount;
1.783 + return;
1.784 + }
1.785 +
1.786 + size--;
1.787 +
1.788 + Object item;
1.789 + for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
1.790 + i = nextKeyIndex(i, len)) {
1.791 + int r = hash(item, len);
1.792 + // See closeDeletion for explanation of this conditional
1.793 + if ((i < r && (r <= d || d <= i)) ||
1.794 + (r <= d && d <= i)) {
1.795 +
1.796 + // If we are about to swap an already-seen element
1.797 + // into a slot that may later be returned by next(),
1.798 + // then clone the rest of table for use in future
1.799 + // next() calls. It is OK that our copy will have
1.800 + // a gap in the "wrong" place, since it will never
1.801 + // be used for searching anyway.
1.802 +
1.803 + if (i < deletedSlot && d >= deletedSlot &&
1.804 + traversalTable == IdentityHashMap.this.table) {
1.805 + int remaining = len - deletedSlot;
1.806 + Object[] newTable = new Object[remaining];
1.807 + System.arraycopy(tab, deletedSlot,
1.808 + newTable, 0, remaining);
1.809 + traversalTable = newTable;
1.810 + index = 0;
1.811 + }
1.812 +
1.813 + tab[d] = item;
1.814 + tab[d + 1] = tab[i + 1];
1.815 + tab[i] = null;
1.816 + tab[i + 1] = null;
1.817 + d = i;
1.818 + }
1.819 + }
1.820 + }
1.821 + }
1.822 +
1.823 + private class KeyIterator extends IdentityHashMapIterator<K> {
1.824 + public K next() {
1.825 + return (K) unmaskNull(traversalTable[nextIndex()]);
1.826 + }
1.827 + }
1.828 +
1.829 + private class ValueIterator extends IdentityHashMapIterator<V> {
1.830 + public V next() {
1.831 + return (V) traversalTable[nextIndex() + 1];
1.832 + }
1.833 + }
1.834 +
1.835 + private class EntryIterator
1.836 + extends IdentityHashMapIterator<Map.Entry<K,V>>
1.837 + {
1.838 + private Entry lastReturnedEntry = null;
1.839 +
1.840 + public Map.Entry<K,V> next() {
1.841 + lastReturnedEntry = new Entry(nextIndex());
1.842 + return lastReturnedEntry;
1.843 + }
1.844 +
1.845 + public void remove() {
1.846 + lastReturnedIndex =
1.847 + ((null == lastReturnedEntry) ? -1 : lastReturnedEntry.index);
1.848 + super.remove();
1.849 + lastReturnedEntry.index = lastReturnedIndex;
1.850 + lastReturnedEntry = null;
1.851 + }
1.852 +
1.853 + private class Entry implements Map.Entry<K,V> {
1.854 + private int index;
1.855 +
1.856 + private Entry(int index) {
1.857 + this.index = index;
1.858 + }
1.859 +
1.860 + public K getKey() {
1.861 + checkIndexForEntryUse();
1.862 + return (K) unmaskNull(traversalTable[index]);
1.863 + }
1.864 +
1.865 + public V getValue() {
1.866 + checkIndexForEntryUse();
1.867 + return (V) traversalTable[index+1];
1.868 + }
1.869 +
1.870 + public V setValue(V value) {
1.871 + checkIndexForEntryUse();
1.872 + V oldValue = (V) traversalTable[index+1];
1.873 + traversalTable[index+1] = value;
1.874 + // if shadowing, force into main table
1.875 + if (traversalTable != IdentityHashMap.this.table)
1.876 + put((K) traversalTable[index], value);
1.877 + return oldValue;
1.878 + }
1.879 +
1.880 + public boolean equals(Object o) {
1.881 + if (index < 0)
1.882 + return super.equals(o);
1.883 +
1.884 + if (!(o instanceof Map.Entry))
1.885 + return false;
1.886 + Map.Entry e = (Map.Entry)o;
1.887 + return (e.getKey() == unmaskNull(traversalTable[index]) &&
1.888 + e.getValue() == traversalTable[index+1]);
1.889 + }
1.890 +
1.891 + public int hashCode() {
1.892 + if (lastReturnedIndex < 0)
1.893 + return super.hashCode();
1.894 +
1.895 + return (System.identityHashCode(unmaskNull(traversalTable[index])) ^
1.896 + System.identityHashCode(traversalTable[index+1]));
1.897 + }
1.898 +
1.899 + public String toString() {
1.900 + if (index < 0)
1.901 + return super.toString();
1.902 +
1.903 + return (unmaskNull(traversalTable[index]) + "="
1.904 + + traversalTable[index+1]);
1.905 + }
1.906 +
1.907 + private void checkIndexForEntryUse() {
1.908 + if (index < 0)
1.909 + throw new IllegalStateException("Entry was removed");
1.910 + }
1.911 + }
1.912 + }
1.913 +
1.914 + // Views
1.915 +
1.916 + /**
1.917 + * This field is initialized to contain an instance of the entry set
1.918 + * view the first time this view is requested. The view is stateless,
1.919 + * so there's no reason to create more than one.
1.920 + */
1.921 + private transient Set<Map.Entry<K,V>> entrySet = null;
1.922 +
1.923 + /**
1.924 + * Returns an identity-based set view of the keys contained in this map.
1.925 + * The set is backed by the map, so changes to the map are reflected in
1.926 + * the set, and vice-versa. If the map is modified while an iteration
1.927 + * over the set is in progress, the results of the iteration are
1.928 + * undefined. The set supports element removal, which removes the
1.929 + * corresponding mapping from the map, via the <tt>Iterator.remove</tt>,
1.930 + * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
1.931 + * <tt>clear</tt> methods. It does not support the <tt>add</tt> or
1.932 + * <tt>addAll</tt> methods.
1.933 + *
1.934 + * <p><b>While the object returned by this method implements the
1.935 + * <tt>Set</tt> interface, it does <i>not</i> obey <tt>Set's</tt> general
1.936 + * contract. Like its backing map, the set returned by this method
1.937 + * defines element equality as reference-equality rather than
1.938 + * object-equality. This affects the behavior of its <tt>contains</tt>,
1.939 + * <tt>remove</tt>, <tt>containsAll</tt>, <tt>equals</tt>, and
1.940 + * <tt>hashCode</tt> methods.</b>
1.941 + *
1.942 + * <p><b>The <tt>equals</tt> method of the returned set returns <tt>true</tt>
1.943 + * only if the specified object is a set containing exactly the same
1.944 + * object references as the returned set. The symmetry and transitivity
1.945 + * requirements of the <tt>Object.equals</tt> contract may be violated if
1.946 + * the set returned by this method is compared to a normal set. However,
1.947 + * the <tt>Object.equals</tt> contract is guaranteed to hold among sets
1.948 + * returned by this method.</b>
1.949 + *
1.950 + * <p>The <tt>hashCode</tt> method of the returned set returns the sum of
1.951 + * the <i>identity hashcodes</i> of the elements in the set, rather than
1.952 + * the sum of their hashcodes. This is mandated by the change in the
1.953 + * semantics of the <tt>equals</tt> method, in order to enforce the
1.954 + * general contract of the <tt>Object.hashCode</tt> method among sets
1.955 + * returned by this method.
1.956 + *
1.957 + * @return an identity-based set view of the keys contained in this map
1.958 + * @see Object#equals(Object)
1.959 + * @see System#identityHashCode(Object)
1.960 + */
1.961 + public Set<K> keySet() {
1.962 + Set<K> ks = keySet;
1.963 + if (ks != null)
1.964 + return ks;
1.965 + else
1.966 + return keySet = new KeySet();
1.967 + }
1.968 +
1.969 + private class KeySet extends AbstractSet<K> {
1.970 + public Iterator<K> iterator() {
1.971 + return new KeyIterator();
1.972 + }
1.973 + public int size() {
1.974 + return size;
1.975 + }
1.976 + public boolean contains(Object o) {
1.977 + return containsKey(o);
1.978 + }
1.979 + public boolean remove(Object o) {
1.980 + int oldSize = size;
1.981 + IdentityHashMap.this.remove(o);
1.982 + return size != oldSize;
1.983 + }
1.984 + /*
1.985 + * Must revert from AbstractSet's impl to AbstractCollection's, as
1.986 + * the former contains an optimization that results in incorrect
1.987 + * behavior when c is a smaller "normal" (non-identity-based) Set.
1.988 + */
1.989 + public boolean removeAll(Collection<?> c) {
1.990 + boolean modified = false;
1.991 + for (Iterator<K> i = iterator(); i.hasNext(); ) {
1.992 + if (c.contains(i.next())) {
1.993 + i.remove();
1.994 + modified = true;
1.995 + }
1.996 + }
1.997 + return modified;
1.998 + }
1.999 + public void clear() {
1.1000 + IdentityHashMap.this.clear();
1.1001 + }
1.1002 + public int hashCode() {
1.1003 + int result = 0;
1.1004 + for (K key : this)
1.1005 + result += System.identityHashCode(key);
1.1006 + return result;
1.1007 + }
1.1008 + }
1.1009 +
1.1010 + /**
1.1011 + * Returns a {@link Collection} view of the values contained in this map.
1.1012 + * The collection is backed by the map, so changes to the map are
1.1013 + * reflected in the collection, and vice-versa. If the map is
1.1014 + * modified while an iteration over the collection is in progress,
1.1015 + * the results of the iteration are undefined. The collection
1.1016 + * supports element removal, which removes the corresponding
1.1017 + * mapping from the map, via the <tt>Iterator.remove</tt>,
1.1018 + * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
1.1019 + * <tt>retainAll</tt> and <tt>clear</tt> methods. It does not
1.1020 + * support the <tt>add</tt> or <tt>addAll</tt> methods.
1.1021 + *
1.1022 + * <p><b>While the object returned by this method implements the
1.1023 + * <tt>Collection</tt> interface, it does <i>not</i> obey
1.1024 + * <tt>Collection's</tt> general contract. Like its backing map,
1.1025 + * the collection returned by this method defines element equality as
1.1026 + * reference-equality rather than object-equality. This affects the
1.1027 + * behavior of its <tt>contains</tt>, <tt>remove</tt> and
1.1028 + * <tt>containsAll</tt> methods.</b>
1.1029 + */
1.1030 + public Collection<V> values() {
1.1031 + Collection<V> vs = values;
1.1032 + if (vs != null)
1.1033 + return vs;
1.1034 + else
1.1035 + return values = new Values();
1.1036 + }
1.1037 +
1.1038 + private class Values extends AbstractCollection<V> {
1.1039 + public Iterator<V> iterator() {
1.1040 + return new ValueIterator();
1.1041 + }
1.1042 + public int size() {
1.1043 + return size;
1.1044 + }
1.1045 + public boolean contains(Object o) {
1.1046 + return containsValue(o);
1.1047 + }
1.1048 + public boolean remove(Object o) {
1.1049 + for (Iterator<V> i = iterator(); i.hasNext(); ) {
1.1050 + if (i.next() == o) {
1.1051 + i.remove();
1.1052 + return true;
1.1053 + }
1.1054 + }
1.1055 + return false;
1.1056 + }
1.1057 + public void clear() {
1.1058 + IdentityHashMap.this.clear();
1.1059 + }
1.1060 + }
1.1061 +
1.1062 + /**
1.1063 + * Returns a {@link Set} view of the mappings contained in this map.
1.1064 + * Each element in the returned set is a reference-equality-based
1.1065 + * <tt>Map.Entry</tt>. The set is backed by the map, so changes
1.1066 + * to the map are reflected in the set, and vice-versa. If the
1.1067 + * map is modified while an iteration over the set is in progress,
1.1068 + * the results of the iteration are undefined. The set supports
1.1069 + * element removal, which removes the corresponding mapping from
1.1070 + * the map, via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1.1071 + * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
1.1072 + * methods. It does not support the <tt>add</tt> or
1.1073 + * <tt>addAll</tt> methods.
1.1074 + *
1.1075 + * <p>Like the backing map, the <tt>Map.Entry</tt> objects in the set
1.1076 + * returned by this method define key and value equality as
1.1077 + * reference-equality rather than object-equality. This affects the
1.1078 + * behavior of the <tt>equals</tt> and <tt>hashCode</tt> methods of these
1.1079 + * <tt>Map.Entry</tt> objects. A reference-equality based <tt>Map.Entry
1.1080 + * e</tt> is equal to an object <tt>o</tt> if and only if <tt>o</tt> is a
1.1081 + * <tt>Map.Entry</tt> and <tt>e.getKey()==o.getKey() &&
1.1082 + * e.getValue()==o.getValue()</tt>. To accommodate these equals
1.1083 + * semantics, the <tt>hashCode</tt> method returns
1.1084 + * <tt>System.identityHashCode(e.getKey()) ^
1.1085 + * System.identityHashCode(e.getValue())</tt>.
1.1086 + *
1.1087 + * <p><b>Owing to the reference-equality-based semantics of the
1.1088 + * <tt>Map.Entry</tt> instances in the set returned by this method,
1.1089 + * it is possible that the symmetry and transitivity requirements of
1.1090 + * the {@link Object#equals(Object)} contract may be violated if any of
1.1091 + * the entries in the set is compared to a normal map entry, or if
1.1092 + * the set returned by this method is compared to a set of normal map
1.1093 + * entries (such as would be returned by a call to this method on a normal
1.1094 + * map). However, the <tt>Object.equals</tt> contract is guaranteed to
1.1095 + * hold among identity-based map entries, and among sets of such entries.
1.1096 + * </b>
1.1097 + *
1.1098 + * @return a set view of the identity-mappings contained in this map
1.1099 + */
1.1100 + public Set<Map.Entry<K,V>> entrySet() {
1.1101 + Set<Map.Entry<K,V>> es = entrySet;
1.1102 + if (es != null)
1.1103 + return es;
1.1104 + else
1.1105 + return entrySet = new EntrySet();
1.1106 + }
1.1107 +
1.1108 + private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1.1109 + public Iterator<Map.Entry<K,V>> iterator() {
1.1110 + return new EntryIterator();
1.1111 + }
1.1112 + public boolean contains(Object o) {
1.1113 + if (!(o instanceof Map.Entry))
1.1114 + return false;
1.1115 + Map.Entry entry = (Map.Entry)o;
1.1116 + return containsMapping(entry.getKey(), entry.getValue());
1.1117 + }
1.1118 + public boolean remove(Object o) {
1.1119 + if (!(o instanceof Map.Entry))
1.1120 + return false;
1.1121 + Map.Entry entry = (Map.Entry)o;
1.1122 + return removeMapping(entry.getKey(), entry.getValue());
1.1123 + }
1.1124 + public int size() {
1.1125 + return size;
1.1126 + }
1.1127 + public void clear() {
1.1128 + IdentityHashMap.this.clear();
1.1129 + }
1.1130 + /*
1.1131 + * Must revert from AbstractSet's impl to AbstractCollection's, as
1.1132 + * the former contains an optimization that results in incorrect
1.1133 + * behavior when c is a smaller "normal" (non-identity-based) Set.
1.1134 + */
1.1135 + public boolean removeAll(Collection<?> c) {
1.1136 + boolean modified = false;
1.1137 + for (Iterator<Map.Entry<K,V>> i = iterator(); i.hasNext(); ) {
1.1138 + if (c.contains(i.next())) {
1.1139 + i.remove();
1.1140 + modified = true;
1.1141 + }
1.1142 + }
1.1143 + return modified;
1.1144 + }
1.1145 +
1.1146 + public Object[] toArray() {
1.1147 + int size = size();
1.1148 + Object[] result = new Object[size];
1.1149 + Iterator<Map.Entry<K,V>> it = iterator();
1.1150 + for (int i = 0; i < size; i++)
1.1151 + result[i] = new AbstractMap.SimpleEntry<>(it.next());
1.1152 + return result;
1.1153 + }
1.1154 +
1.1155 + @SuppressWarnings("unchecked")
1.1156 + public <T> T[] toArray(T[] a) {
1.1157 + int size = size();
1.1158 + if (a.length < size)
1.1159 + a = (T[])java.lang.reflect.Array
1.1160 + .newInstance(a.getClass().getComponentType(), size);
1.1161 + Iterator<Map.Entry<K,V>> it = iterator();
1.1162 + for (int i = 0; i < size; i++)
1.1163 + a[i] = (T) new AbstractMap.SimpleEntry<>(it.next());
1.1164 + if (a.length > size)
1.1165 + a[size] = null;
1.1166 + return a;
1.1167 + }
1.1168 + }
1.1169 +
1.1170 +
1.1171 + private static final long serialVersionUID = 8188218128353913216L;
1.1172 +
1.1173 + /**
1.1174 + * Save the state of the <tt>IdentityHashMap</tt> instance to a stream
1.1175 + * (i.e., serialize it).
1.1176 + *
1.1177 + * @serialData The <i>size</i> of the HashMap (the number of key-value
1.1178 + * mappings) (<tt>int</tt>), followed by the key (Object) and
1.1179 + * value (Object) for each key-value mapping represented by the
1.1180 + * IdentityHashMap. The key-value mappings are emitted in no
1.1181 + * particular order.
1.1182 + */
1.1183 + private void writeObject(java.io.ObjectOutputStream s)
1.1184 + throws java.io.IOException {
1.1185 + // Write out and any hidden stuff
1.1186 + s.defaultWriteObject();
1.1187 +
1.1188 + // Write out size (number of Mappings)
1.1189 + s.writeInt(size);
1.1190 +
1.1191 + // Write out keys and values (alternating)
1.1192 + Object[] tab = table;
1.1193 + for (int i = 0; i < tab.length; i += 2) {
1.1194 + Object key = tab[i];
1.1195 + if (key != null) {
1.1196 + s.writeObject(unmaskNull(key));
1.1197 + s.writeObject(tab[i + 1]);
1.1198 + }
1.1199 + }
1.1200 + }
1.1201 +
1.1202 + /**
1.1203 + * Reconstitute the <tt>IdentityHashMap</tt> instance from a stream (i.e.,
1.1204 + * deserialize it).
1.1205 + */
1.1206 + private void readObject(java.io.ObjectInputStream s)
1.1207 + throws java.io.IOException, ClassNotFoundException {
1.1208 + // Read in any hidden stuff
1.1209 + s.defaultReadObject();
1.1210 +
1.1211 + // Read in size (number of Mappings)
1.1212 + int size = s.readInt();
1.1213 +
1.1214 + // Allow for 33% growth (i.e., capacity is >= 2* size()).
1.1215 + init(capacity((size*4)/3));
1.1216 +
1.1217 + // Read the keys and values, and put the mappings in the table
1.1218 + for (int i=0; i<size; i++) {
1.1219 + K key = (K) s.readObject();
1.1220 + V value = (V) s.readObject();
1.1221 + putForCreate(key, value);
1.1222 + }
1.1223 + }
1.1224 +
1.1225 + /**
1.1226 + * The put method for readObject. It does not resize the table,
1.1227 + * update modCount, etc.
1.1228 + */
1.1229 + private void putForCreate(K key, V value)
1.1230 + throws IOException
1.1231 + {
1.1232 + K k = (K)maskNull(key);
1.1233 + Object[] tab = table;
1.1234 + int len = tab.length;
1.1235 + int i = hash(k, len);
1.1236 +
1.1237 + Object item;
1.1238 + while ( (item = tab[i]) != null) {
1.1239 + if (item == k)
1.1240 + throw new java.io.StreamCorruptedException();
1.1241 + i = nextKeyIndex(i, len);
1.1242 + }
1.1243 + tab[i] = k;
1.1244 + tab[i + 1] = value;
1.1245 + }
1.1246 +}