| IdentityHashMap.java |
1 /*
2 * %W% %E%
3 *
4 * Copyright (c) 2006, Oracle and/or its affiliates. All rights reserved.
5 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6 */
7
8 package java.util;
9 import java.io.*;
10
11 /**
12 * This class implements the <tt>Map</tt> interface with a hash table, using
13 * reference-equality in place of object-equality when comparing keys (and
14 * values). In other words, in an <tt>IdentityHashMap</tt>, two keys
15 * <tt>k1</tt> and <tt>k2</tt> are considered equal if and only if
16 * <tt>(k1==k2)</tt>. (In normal <tt>Map</tt> implementations (like
17 * <tt>HashMap</tt>) two keys <tt>k1</tt> and <tt>k2</tt> are considered equal
18 * if and only if <tt>(k1==null ? k2==null : k1.equals(k2))</tt>.)
19 *
20 * <p><b>This class is <i>not</i> a general-purpose <tt>Map</tt>
21 * implementation! While this class implements the <tt>Map</tt> interface, it
22 * intentionally violates <tt>Map's</tt> general contract, which mandates the
23 * use of the <tt>equals</tt> method when comparing objects. This class is
24 * designed for use only in the rare cases wherein reference-equality
25 * semantics are required.</b>
26 *
27 * <p>A typical use of this class is <i>topology-preserving object graph
28 * transformations</i>, such as serialization or deep-copying. To perform such
29 * a transformation, a program must maintain a "node table" that keeps track
30 * of all the object references that have already been processed. The node
31 * table must not equate distinct objects even if they happen to be equal.
32 * Another typical use of this class is to maintain <i>proxy objects</i>. For
33 * example, a debugging facility might wish to maintain a proxy object for
34 * each object in the program being debugged.
35 *
36 * <p>This class provides all of the optional map operations, and permits
37 * <tt>null</tt> values and the <tt>null</tt> key. This class makes no
38 * guarantees as to the order of the map; in particular, it does not guarantee
39 * that the order will remain constant over time.
40 *
41 * <p>This class provides constant-time performance for the basic
42 * operations (<tt>get</tt> and <tt>put</tt>), assuming the system
43 * identity hash function ({@link System#identityHashCode(Object)})
44 * disperses elements properly among the buckets.
45 *
46 * <p>This class has one tuning parameter (which affects performance but not
47 * semantics): <i>expected maximum size</i>. This parameter is the maximum
48 * number of key-value mappings that the map is expected to hold. Internally,
49 * this parameter is used to determine the number of buckets initially
50 * comprising the hash table. The precise relationship between the expected
51 * maximum size and the number of buckets is unspecified.
52 *
53 * <p>If the size of the map (the number of key-value mappings) sufficiently
54 * exceeds the expected maximum size, the number of buckets is increased
55 * Increasing the number of buckets ("rehashing") may be fairly expensive, so
56 * it pays to create identity hash maps with a sufficiently large expected
57 * maximum size. On the other hand, iteration over collection views requires
58 * time proportional to the number of buckets in the hash table, so it
59 * pays not to set the expected maximum size too high if you are especially
60 * concerned with iteration performance or memory usage.
61 *
62 * <p><strong>Note that this implementation is not synchronized.</strong>
63 * If multiple threads access an identity hash map concurrently, and at
64 * least one of the threads modifies the map structurally, it <i>must</i>
65 * be synchronized externally. (A structural modification is any operation
66 * that adds or deletes one or more mappings; merely changing the value
67 * associated with a key that an instance already contains is not a
68 * structural modification.) This is typically accomplished by
69 * synchronizing on some object that naturally encapsulates the map.
70 *
71 * If no such object exists, the map should be "wrapped" using the
72 * {@link Collections#synchronizedMap Collections.synchronizedMap}
73 * method. This is best done at creation time, to prevent accidental
74 * unsynchronized access to the map:<pre>
75 * Map m = Collections.synchronizedMap(new IdentityHashMap(...));</pre>
76 *
77 * <p>The iterators returned by the <tt>iterator</tt> method of the
78 * collections returned by all of this class's "collection view
79 * methods" are <i>fail-fast</i>: if the map is structurally modified
80 * at any time after the iterator is created, in any way except
81 * through the iterator's own <tt>remove</tt> method, the iterator
82 * will throw a {@link ConcurrentModificationException}. Thus, in the
83 * face of concurrent modification, the iterator fails quickly and
84 * cleanly, rather than risking arbitrary, non-deterministic behavior
85 * at an undetermined time in the future.
86 *
87 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
88 * as it is, generally speaking, impossible to make any hard guarantees in the
89 * presence of unsynchronized concurrent modification. Fail-fast iterators
90 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
91 * Therefore, it would be wrong to write a program that depended on this
92 * exception for its correctness: <i>fail-fast iterators should be used only
93 * to detect bugs.</i>
94 *
95 * <p>Implementation note: This is a simple <i>linear-probe</i> hash table,
96 * as described for example in texts by Sedgewick and Knuth. The array
97 * alternates holding keys and values. (This has better locality for large
98 * tables than does using separate arrays.) For many JRE implementations
99 * and operation mixes, this class will yield better performance than
100 * {@link HashMap} (which uses <i>chaining</i> rather than linear-probing).
101 *
102 * <p>This class is a member of the
103 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
104 * Java Collections Framework</a>.
105 *
106 * @see System#identityHashCode(Object)
107 * @see Object#hashCode()
108 * @see Collection
109 * @see Map
110 * @see HashMap
111 * @see TreeMap
112 * @author Doug Lea and Josh Bloch
113 * @since 1.4
114 */
115
116 public class IdentityHashMap<K,V>
117 extends AbstractMap<K,V>
118 implements Map<K,V>, java.io.Serializable, Cloneable
119 {
120 /**
121 * The initial capacity used by the no-args constructor.
122 * MUST be a power of two. The value 32 corresponds to the
123 * (specified) expected maximum size of 21, given a load factor
124 * of 2/3.
125 */
126 private static final int DEFAULT_CAPACITY = 32;
127
128 /**
129 * The minimum capacity, used if a lower value is implicitly specified
130 * by either of the constructors with arguments. The value 4 corresponds
131 * to an expected maximum size of 2, given a load factor of 2/3.
132 * MUST be a power of two.
133 */
134 private static final int MINIMUM_CAPACITY = 4;
135
136 /**
137 * The maximum capacity, used if a higher value is implicitly specified
138 * by either of the constructors with arguments.
139 * MUST be a power of two <= 1<<29.
140 */
141 private static final int MAXIMUM_CAPACITY = 1 << 29;
142
143 /**
144 * The table, resized as necessary. Length MUST always be a power of two.
145 */
146 private transient Object[] table;
147
148 /**
149 * The number of key-value mappings contained in this identity hash map.
150 *
151 * @serial
152 */
153 private int size;
154
155 /**
156 * The number of modifications, to support fast-fail iterators
157 */
158 private transient volatile int modCount;
159
160 /**
161 * The next size value at which to resize (capacity * load factor).
162 */
163 private transient int threshold;
164
165 /**
166 * Value representing null keys inside tables.
167 */
168 private static final Object NULL_KEY = new Object();
169
170 /**
171 * Use NULL_KEY for key if it is null.
172 */
173
174 private static Object maskNull(Object key) {
175 return (key == null ? NULL_KEY : key);
176 }
177
178 /**
179 * Returns internal representation of null key back to caller as null.
180 */
181 private static Object unmaskNull(Object key) {
182 return (key == NULL_KEY ? null : key);
183 }
184
185 /**
186 * Constructs a new, empty identity hash map with a default expected
187 * maximum size (21).
188 */
189 public IdentityHashMap() {
190 init(DEFAULT_CAPACITY);
191 }
192
193 /**
194 * Constructs a new, empty map with the specified expected maximum size.
195 * Putting more than the expected number of key-value mappings into
196 * the map may cause the internal data structure to grow, which may be
197 * somewhat time-consuming.
198 *
199 * @param expectedMaxSize the expected maximum size of the map
200 * @throws IllegalArgumentException if <tt>expectedMaxSize</tt> is negative
201 */
202 public IdentityHashMap(int expectedMaxSize) {
203 if (expectedMaxSize < 0)
204 throw new IllegalArgumentException("expectedMaxSize is negative: "
205 + expectedMaxSize);
206 init(capacity(expectedMaxSize));
207 }
208
209 /**
210 * Returns the appropriate capacity for the specified expected maximum
211 * size. Returns the smallest power of two between MINIMUM_CAPACITY
212 * and MAXIMUM_CAPACITY, inclusive, that is greater than
213 * (3 * expectedMaxSize)/2, if such a number exists. Otherwise
214 * returns MAXIMUM_CAPACITY. If (3 * expectedMaxSize)/2 is negative, it
215 * is assumed that overflow has occurred, and MAXIMUM_CAPACITY is returned.
216 */
217 private int capacity(int expectedMaxSize) {
218 // Compute min capacity for expectedMaxSize given a load factor of 2/3
219 int minCapacity = (3 * expectedMaxSize)/2;
220
221 // Compute the appropriate capacity
222 int result;
223 if (minCapacity > MAXIMUM_CAPACITY || minCapacity < 0) {
224 result = MAXIMUM_CAPACITY;
225 } else {
226 result = MINIMUM_CAPACITY;
227 while (result < minCapacity)
228 result <<= 1;
229 }
230 return result;
231 }
232
233 /**
234 * Initializes object to be an empty map with the specified initial
235 * capacity, which is assumed to be a power of two between
236 * MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
237 */
238 private void init(int initCapacity) {
239 // assert (initCapacity & -initCapacity) == initCapacity; // power of 2
240 // assert initCapacity >= MINIMUM_CAPACITY;
241 // assert initCapacity <= MAXIMUM_CAPACITY;
242
243 threshold = (initCapacity * 2)/3;
244 table = new Object[2 * initCapacity];
245 }
246
247 /**
248 * Constructs a new identity hash map containing the keys-value mappings
249 * in the specified map.
250 *
251 * @param m the map whose mappings are to be placed into this map
252 * @throws NullPointerException if the specified map is null
253 */
254 public IdentityHashMap(Map<? extends K, ? extends V> m) {
255 // Allow for a bit of growth
256 this((int) ((1 + m.size()) * 1.1));
257 putAll(m);
258 }
259
260 /**
261 * Returns the number of key-value mappings in this identity hash map.
262 *
263 * @return the number of key-value mappings in this map
264 */
265 public int size() {
266 return size;
267 }
268
269 /**
270 * Returns <tt>true</tt> if this identity hash map contains no key-value
271 * mappings.
272 *
273 * @return <tt>true</tt> if this identity hash map contains no key-value
274 * mappings
275 */
276 public boolean isEmpty() {
277 return size == 0;
278 }
279
280 /**
281 * Returns index for Object x.
282 */
283 private static int hash(Object x, int length) {
284 int h = System.identityHashCode(x);
285 // Multiply by -127, and left-shift to use least bit as part of hash
286 return ((h << 1) - (h << 8)) & (length - 1);
287 }
288
289 /**
290 * Circularly traverses table of size len.
291 */
292 private static int nextKeyIndex(int i, int len) {
293 return (i + 2 < len ? i + 2 : 0);
294 }
295
296 /**
297 * Returns the value to which the specified key is mapped,
298 * or {@code null} if this map contains no mapping for the key.
299 *
300 * <p>More formally, if this map contains a mapping from a key
301 * {@code k} to a value {@code v} such that {@code (key == k)},
302 * then this method returns {@code v}; otherwise it returns
303 * {@code null}. (There can be at most one such mapping.)
304 *
305 * <p>A return value of {@code null} does not <i>necessarily</i>
306 * indicate that the map contains no mapping for the key; it's also
307 * possible that the map explicitly maps the key to {@code null}.
308 * The {@link #containsKey containsKey} operation may be used to
309 * distinguish these two cases.
310 *
311 * @see #put(Object, Object)
312 */
313 public V get(Object key) {
314 Object k = maskNull(key);
315 Object[] tab = table;
316 int len = tab.length;
317 int i = hash(k, len);
318 while (true) {
319 Object item = tab[i];
320 if (item == k)
321 return (V) tab[i + 1];
322 if (item == null)
323 return null;
324 i = nextKeyIndex(i, len);
325 }
326 }
327
328 /**
329 * Tests whether the specified object reference is a key in this identity
330 * hash map.
331 *
332 * @param key possible key
333 * @return <code>true</code> if the specified object reference is a key
334 * in this map
335 * @see #containsValue(Object)
336 */
337 public boolean containsKey(Object key) {
338 Object k = maskNull(key);
339 Object[] tab = table;
340 int len = tab.length;
341 int i = hash(k, len);
342 while (true) {
343 Object item = tab[i];
344 if (item == k)
345 return true;
346 if (item == null)
347 return false;
348 i = nextKeyIndex(i, len);
349 }
350 }
351
352 /**
353 * Tests whether the specified object reference is a value in this identity
354 * hash map.
355 *
356 * @param value value whose presence in this map is to be tested
357 * @return <tt>true</tt> if this map maps one or more keys to the
358 * specified object reference
359 * @see #containsKey(Object)
360 */
361 public boolean containsValue(Object value) {
362 Object[] tab = table;
363 for (int i = 1; i < tab.length; i += 2)
364 if (tab[i] == value && tab[i - 1] != null)
365 return true;
366
367 return false;
368 }
369
370 /**
371 * Tests if the specified key-value mapping is in the map.
372 *
373 * @param key possible key
374 * @param value possible value
375 * @return <code>true</code> if and only if the specified key-value
376 * mapping is in the map
377 */
378 private boolean containsMapping(Object key, Object value) {
379 Object k = maskNull(key);
380 Object[] tab = table;
381 int len = tab.length;
382 int i = hash(k, len);
383 while (true) {
384 Object item = tab[i];
385 if (item == k)
386 return tab[i + 1] == value;
387 if (item == null)
388 return false;
389 i = nextKeyIndex(i, len);
390 }
391 }
392
393 /**
394 * Associates the specified value with the specified key in this identity
395 * hash map. If the map previously contained a mapping for the key, the
396 * old value is replaced.
397 *
398 * @param key the key with which the specified value is to be associated
399 * @param value the value to be associated with the specified key
400 * @return the previous value associated with <tt>key</tt>, or
401 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
402 * (A <tt>null</tt> return can also indicate that the map
403 * previously associated <tt>null</tt> with <tt>key</tt>.)
404 * @see Object#equals(Object)
405 * @see #get(Object)
406 * @see #containsKey(Object)
407 */
408 public V put(K key, V value) {
409 Object k = maskNull(key);
410 Object[] tab = table;
411 int len = tab.length;
412 int i = hash(k, len);
413
414 Object item;
415 while ( (item = tab[i]) != null) {
416 if (item == k) {
417 V oldValue = (V) tab[i + 1];
418 tab[i + 1] = value;
419 return oldValue;
420 }
421 i = nextKeyIndex(i, len);
422 }
423
424 modCount++;
425 tab[i] = k;
426 tab[i + 1] = value;
427 if (++size >= threshold)
428 resize(len); // len == 2 * current capacity.
429 return null;
430 }
431
432 /**
433 * Resize the table to hold given capacity.
434 *
435 * @param newCapacity the new capacity, must be a power of two.
436 */
437 private void resize(int newCapacity) {
438 // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
439 int newLength = newCapacity * 2;
440
441 Object[] oldTable = table;
442 int oldLength = oldTable.length;
443 if (oldLength == 2*MAXIMUM_CAPACITY) { // can't expand any further
444 if (threshold == MAXIMUM_CAPACITY-1)
445 throw new IllegalStateException("Capacity exhausted.");
446 threshold = MAXIMUM_CAPACITY-1; // Gigantic map!
447 return;
448 }
449 if (oldLength >= newLength)
450 return;
451
452 Object[] newTable = new Object[newLength];
453 threshold = newLength / 3;
454
455 for (int j = 0; j < oldLength; j += 2) {
456 Object key = oldTable[j];
457 if (key != null) {
458 Object value = oldTable[j+1];
459 oldTable[j] = null;
460 oldTable[j+1] = null;
461 int i = hash(key, newLength);
462 while (newTable[i] != null)
463 i = nextKeyIndex(i, newLength);
464 newTable[i] = key;
465 newTable[i + 1] = value;
466 }
467 }
468 table = newTable;
469 }
470
471 /**
472 * Copies all of the mappings from the specified map to this map.
473 * These mappings will replace any mappings that this map had for
474 * any of the keys currently in the specified map.
475 *
476 * @param m mappings to be stored in this map
477 * @throws NullPointerException if the specified map is null
478 */
479 public void putAll(Map<? extends K, ? extends V> m) {
480 int n = m.size();
481 if (n == 0)
482 return;
483 if (n > threshold) // conservatively pre-expand
484 resize(capacity(n));
485
486 for (Entry<? extends K, ? extends V> e : m.entrySet())
487 put(e.getKey(), e.getValue());
488 }
489
490 /**
491 * Removes the mapping for this key from this map if present.
492 *
493 * @param key key whose mapping is to be removed from the map
494 * @return the previous value associated with <tt>key</tt>, or
495 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
496 * (A <tt>null</tt> return can also indicate that the map
497 * previously associated <tt>null</tt> with <tt>key</tt>.)
498 */
499 public V remove(Object key) {
500 Object k = maskNull(key);
501 Object[] tab = table;
502 int len = tab.length;
503 int i = hash(k, len);
504
505 while (true) {
506 Object item = tab[i];
507 if (item == k) {
508 modCount++;
509 size--;
510 V oldValue = (V) tab[i + 1];
511 tab[i + 1] = null;
512 tab[i] = null;
513 closeDeletion(i);
514 return oldValue;
515 }
516 if (item == null)
517 return null;
518 i = nextKeyIndex(i, len);
519 }
520
521 }
522
523 /**
524 * Removes the specified key-value mapping from the map if it is present.
525 *
526 * @param key possible key
527 * @param value possible value
528 * @return <code>true</code> if and only if the specified key-value
529 * mapping was in the map
530 */
531 private boolean removeMapping(Object key, Object value) {
532 Object k = maskNull(key);
533 Object[] tab = table;
534 int len = tab.length;
535 int i = hash(k, len);
536
537 while (true) {
538 Object item = tab[i];
539 if (item == k) {
540 if (tab[i + 1] != value)
541 return false;
542 modCount++;
543 size--;
544 tab[i] = null;
545 tab[i + 1] = null;
546 closeDeletion(i);
547 return true;
548 }
549 if (item == null)
550 return false;
551 i = nextKeyIndex(i, len);
552 }
553 }
554
555 /**
556 * Rehash all possibly-colliding entries following a
557 * deletion. This preserves the linear-probe
558 * collision properties required by get, put, etc.
559 *
560 * @param d the index of a newly empty deleted slot
561 */
562 private void closeDeletion(int d) {
563 // Adapted from Knuth Section 6.4 Algorithm R
564 Object[] tab = table;
565 int len = tab.length;
566
567 // Look for items to swap into newly vacated slot
568 // starting at index immediately following deletion,
569 // and continuing until a null slot is seen, indicating
570 // the end of a run of possibly-colliding keys.
571 Object item;
572 for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
573 i = nextKeyIndex(i, len) ) {
574 // The following test triggers if the item at slot i (which
575 // hashes to be at slot r) should take the spot vacated by d.
576 // If so, we swap it in, and then continue with d now at the
577 // newly vacated i. This process will terminate when we hit
578 // the null slot at the end of this run.
579 // The test is messy because we are using a circular table.
580 int r = hash(item, len);
581 if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
582 tab[d] = item;
583 tab[d + 1] = tab[i + 1];
584 tab[i] = null;
585 tab[i + 1] = null;
586 d = i;
587 }
588 }
589 }
590
591 /**
592 * Removes all of the mappings from this map.
593 * The map will be empty after this call returns.
594 */
595 public void clear() {
596 modCount++;
597 Object[] tab = table;
598 for (int i = 0; i < tab.length; i++)
599 tab[i] = null;
600 size = 0;
601 }
602
603 /**
604 * Compares the specified object with this map for equality. Returns
605 * <tt>true</tt> if the given object is also a map and the two maps
606 * represent identical object-reference mappings. More formally, this
607 * map is equal to another map <tt>m</tt> if and only if
608 * <tt>this.entrySet().equals(m.entrySet())</tt>.
609 *
610 * <p><b>Owing to the reference-equality-based semantics of this map it is
611 * possible that the symmetry and transitivity requirements of the
612 * <tt>Object.equals</tt> contract may be violated if this map is compared
613 * to a normal map. However, the <tt>Object.equals</tt> contract is
614 * guaranteed to hold among <tt>IdentityHashMap</tt> instances.</b>
615 *
616 * @param o object to be compared for equality with this map
617 * @return <tt>true</tt> if the specified object is equal to this map
618 * @see Object#equals(Object)
619 */
620 public boolean equals(Object o) {
621 if (o == this) {
622 return true;
623 } else if (o instanceof IdentityHashMap) {
624 IdentityHashMap m = (IdentityHashMap) o;
625 if (m.size() != size)
626 return false;
627
628 Object[] tab = m.table;
629 for (int i = 0; i < tab.length; i+=2) {
630 Object k = tab[i];
631 if (k != null && !containsMapping(k, tab[i + 1]))
632 return false;
633 }
634 return true;
635 } else if (o instanceof Map) {
636 Map m = (Map)o;
637 return entrySet().equals(m.entrySet());
638 } else {
639 return false; // o is not a Map
640 }
641 }
642
643 /**
644 * Returns the hash code value for this map. The hash code of a map is
645 * defined to be the sum of the hash codes of each entry in the map's
646 * <tt>entrySet()</tt> view. This ensures that <tt>m1.equals(m2)</tt>
647 * implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two
648 * <tt>IdentityHashMap</tt> instances <tt>m1</tt> and <tt>m2</tt>, as
649 * required by the general contract of {@link Object#hashCode}.
650 *
651 * <p><b>Owing to the reference-equality-based semantics of the
652 * <tt>Map.Entry</tt> instances in the set returned by this map's
653 * <tt>entrySet</tt> method, it is possible that the contractual
654 * requirement of <tt>Object.hashCode</tt> mentioned in the previous
655 * paragraph will be violated if one of the two objects being compared is
656 * an <tt>IdentityHashMap</tt> instance and the other is a normal map.</b>
657 *
658 * @return the hash code value for this map
659 * @see Object#equals(Object)
660 * @see #equals(Object)
661 */
662 public int hashCode() {
663 int result = 0;
664 Object[] tab = table;
665 for (int i = 0; i < tab.length; i +=2) {
666 Object key = tab[i];
667 if (key != null) {
668 Object k = unmaskNull(key);
669 result += System.identityHashCode(k) ^
670 System.identityHashCode(tab[i + 1]);
671 }
672 }
673 return result;
674 }
675
676 /**
677 * Returns a shallow copy of this identity hash map: the keys and values
678 * themselves are not cloned.
679 *
680 * @return a shallow copy of this map
681 */
682 public Object clone() {
683 try {
684 IdentityHashMap<K,V> m = (IdentityHashMap<K,V>) super.clone();
685 m.entrySet = null;
686 m.table = (Object[])table.clone();
687 return m;
688 } catch (CloneNotSupportedException e) {
689 throw new InternalError();
690 }
691 }
692
693 private abstract class IdentityHashMapIterator<T> implements Iterator<T> {
694 int index = (size != 0 ? 0 : table.length); // current slot.
695 int expectedModCount = modCount; // to support fast-fail
696 int lastReturnedIndex = -1; // to allow remove()
697 boolean indexValid; // To avoid unnecessary next computation
698 Object[] traversalTable = table; // reference to main table or copy
699
700 public boolean hasNext() {
701 Object[] tab = traversalTable;
702 for (int i = index; i < tab.length; i+=2) {
703 Object key = tab[i];
704 if (key != null) {
705 index = i;
706 return indexValid = true;
707 }
708 }
709 index = tab.length;
710 return false;
711 }
712
713 protected int nextIndex() {
714 if (modCount != expectedModCount)
715 throw new ConcurrentModificationException();
716 if (!indexValid && !hasNext())
717 throw new NoSuchElementException();
718
719 indexValid = false;
720 lastReturnedIndex = index;
721 index += 2;
722 return lastReturnedIndex;
723 }
724
725 public void remove() {
726 if (lastReturnedIndex == -1)
727 throw new IllegalStateException();
728 if (modCount != expectedModCount)
729 throw new ConcurrentModificationException();
730
731 expectedModCount = ++modCount;
732 int deletedSlot = lastReturnedIndex;
733 lastReturnedIndex = -1;
734 size--;
735 // back up index to revisit new contents after deletion
736 index = deletedSlot;
737 indexValid = false;
738
739 // Removal code proceeds as in closeDeletion except that
740 // it must catch the rare case where an element already
741 // seen is swapped into a vacant slot that will be later
742 // traversed by this iterator. We cannot allow future
743 // next() calls to return it again. The likelihood of
744 // this occurring under 2/3 load factor is very slim, but
745 // when it does happen, we must make a copy of the rest of
746 // the table to use for the rest of the traversal. Since
747 // this can only happen when we are near the end of the table,
748 // even in these rare cases, this is not very expensive in
749 // time or space.
750
751 Object[] tab = traversalTable;
752 int len = tab.length;
753
754 int d = deletedSlot;
755 K key = (K) tab[d];
756 tab[d] = null; // vacate the slot
757 tab[d + 1] = null;
758
759 // If traversing a copy, remove in real table.
760 // We can skip gap-closure on copy.
761 if (tab != IdentityHashMap.this.table) {
762 IdentityHashMap.this.remove(key);
763 expectedModCount = modCount;
764 return;
765 }
766
767 Object item;
768 for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
769 i = nextKeyIndex(i, len)) {
770 int r = hash(item, len);
771 // See closeDeletion for explanation of this conditional
772 if ((i < r && (r <= d || d <= i)) ||
773 (r <= d && d <= i)) {
774
775 // If we are about to swap an already-seen element
776 // into a slot that may later be returned by next(),
777 // then clone the rest of table for use in future
778 // next() calls. It is OK that our copy will have
779 // a gap in the "wrong" place, since it will never
780 // be used for searching anyway.
781
782 if (i < deletedSlot && d >= deletedSlot &&
783 traversalTable == IdentityHashMap.this.table) {
784 int remaining = len - deletedSlot;
785 Object[] newTable = new Object[remaining];
786 System.arraycopy(tab, deletedSlot,
787 newTable, 0, remaining);
788 traversalTable = newTable;
789 index = 0;
790 }
791
792 tab[d] = item;
793 tab[d + 1] = tab[i + 1];
794 tab[i] = null;
795 tab[i + 1] = null;
796 d = i;
797 }
798 }
799 }
800 }
801
802 private class KeyIterator extends IdentityHashMapIterator<K> {
803 public K next() {
804 return (K) unmaskNull(traversalTable[nextIndex()]);
805 }
806 }
807
808 private class ValueIterator extends IdentityHashMapIterator<V> {
809 public V next() {
810 return (V) traversalTable[nextIndex() + 1];
811 }
812 }
813
814 /**
815 * Since we don't use Entry objects, we use the Iterator
816 * itself as an entry.
817 */
818 private class EntryIterator
819 extends IdentityHashMapIterator<Map.Entry<K,V>>
820 implements Map.Entry<K,V>
821 {
822 public Map.Entry<K,V> next() {
823 nextIndex();
824 return this;
825 }
826
827 public K getKey() {
828 // Provide a better exception than out of bounds index
829 if (lastReturnedIndex < 0)
830 throw new IllegalStateException("Entry was removed");
831
832 return (K) unmaskNull(traversalTable[lastReturnedIndex]);
833 }
834
835 public V getValue() {
836 // Provide a better exception than out of bounds index
837 if (lastReturnedIndex < 0)
838 throw new IllegalStateException("Entry was removed");
839
840 return (V) traversalTable[lastReturnedIndex+1];
841 }
842
843 public V setValue(V value) {
844 // It would be mean-spirited to proceed here if remove() called
845 if (lastReturnedIndex < 0)
846 throw new IllegalStateException("Entry was removed");
847 V oldValue = (V) traversalTable[lastReturnedIndex+1];
848 traversalTable[lastReturnedIndex+1] = value;
849 // if shadowing, force into main table
850 if (traversalTable != IdentityHashMap.this.table)
851 put((K) traversalTable[lastReturnedIndex], value);
852 return oldValue;
853 }
854
855 public boolean equals(Object o) {
856 if (lastReturnedIndex < 0)
857 return super.equals(o);
858
859 if (!(o instanceof Map.Entry))
860 return false;
861 Map.Entry e = (Map.Entry)o;
862 return e.getKey() == getKey() &&
863 e.getValue() == getValue();
864 }
865
866 public int hashCode() {
867 if (lastReturnedIndex < 0)
868 return super.hashCode();
869
870 return System.identityHashCode(getKey()) ^
871 System.identityHashCode(getValue());
872 }
873
874 public String toString() {
875 if (lastReturnedIndex < 0)
876 return super.toString();
877
878 return getKey() + "=" + getValue();
879 }
880 }
881
882 // Views
883
884 /**
885 * This field is initialized to contain an instance of the entry set
886 * view the first time this view is requested. The view is stateless,
887 * so there's no reason to create more than one.
888 */
889
890 private transient Set<Map.Entry<K,V>> entrySet = null;
891
892 /**
893 * Returns an identity-based set view of the keys contained in this map.
894 * The set is backed by the map, so changes to the map are reflected in
895 * the set, and vice-versa. If the map is modified while an iteration
896 * over the set is in progress, the results of the iteration are
897 * undefined. The set supports element removal, which removes the
898 * corresponding mapping from the map, via the <tt>Iterator.remove</tt>,
899 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
900 * <tt>clear</tt> methods. It does not support the <tt>add</tt> or
901 * <tt>addAll</tt> methods.
902 *
903 * <p><b>While the object returned by this method implements the
904 * <tt>Set</tt> interface, it does <i>not</i> obey <tt>Set's</tt> general
905 * contract. Like its backing map, the set returned by this method
906 * defines element equality as reference-equality rather than
907 * object-equality. This affects the behavior of its <tt>contains</tt>,
908 * <tt>remove</tt>, <tt>containsAll</tt>, <tt>equals</tt>, and
909 * <tt>hashCode</tt> methods.</b>
910 *
911 * <p><b>The <tt>equals</tt> method of the returned set returns <tt>true</tt>
912 * only if the specified object is a set containing exactly the same
913 * object references as the returned set. The symmetry and transitivity
914 * requirements of the <tt>Object.equals</tt> contract may be violated if
915 * the set returned by this method is compared to a normal set. However,
916 * the <tt>Object.equals</tt> contract is guaranteed to hold among sets
917 * returned by this method.</b>
918 *
919 * <p>The <tt>hashCode</tt> method of the returned set returns the sum of
920 * the <i>identity hashcodes</i> of the elements in the set, rather than
921 * the sum of their hashcodes. This is mandated by the change in the
922 * semantics of the <tt>equals</tt> method, in order to enforce the
923 * general contract of the <tt>Object.hashCode</tt> method among sets
924 * returned by this method.
925 *
926 * @return an identity-based set view of the keys contained in this map
927 * @see Object#equals(Object)
928 * @see System#identityHashCode(Object)
929 */
930 public Set<K> keySet() {
931 Set<K> ks = keySet;
932 if (ks != null)
933 return ks;
934 else
935 return keySet = new KeySet();
936 }
937
938 private class KeySet extends AbstractSet<K> {
939 public Iterator<K> iterator() {
940 return new KeyIterator();
941 }
942 public int size() {
943 return size;
944 }
945 public boolean contains(Object o) {
946 return containsKey(o);
947 }
948 public boolean remove(Object o) {
949 int oldSize = size;
950 IdentityHashMap.this.remove(o);
951 return size != oldSize;
952 }
953 /*
954 * Must revert from AbstractSet's impl to AbstractCollection's, as
955 * the former contains an optimization that results in incorrect
956 * behavior when c is a smaller "normal" (non-identity-based) Set.
957 */
958 public boolean removeAll(Collection<?> c) {
959 boolean modified = false;
960 for (Iterator i = iterator(); i.hasNext(); ) {
961 if (c.contains(i.next())) {
962 i.remove();
963 modified = true;
964 }
965 }
966 return modified;
967 }
968 public void clear() {
969 IdentityHashMap.this.clear();
970 }
971 public int hashCode() {
972 int result = 0;
973 for (K key : this)
974 result += System.identityHashCode(key);
975 return result;
976 }
977 }
978
979 /**
980 * Returns a {@link Collection} view of the values contained in this map.
981 * The collection is backed by the map, so changes to the map are
982 * reflected in the collection, and vice-versa. If the map is
983 * modified while an iteration over the collection is in progress,
984 * the results of the iteration are undefined. The collection
985 * supports element removal, which removes the corresponding
986 * mapping from the map, via the <tt>Iterator.remove</tt>,
987 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
988 * <tt>retainAll</tt> and <tt>clear</tt> methods. It does not
989 * support the <tt>add</tt> or <tt>addAll</tt> methods.
990 *
991 * <p><b>While the object returned by this method implements the
992 * <tt>Collection</tt> interface, it does <i>not</i> obey
993 * <tt>Collection's</tt> general contract. Like its backing map,
994 * the collection returned by this method defines element equality as
995 * reference-equality rather than object-equality. This affects the
996 * behavior of its <tt>contains</tt>, <tt>remove</tt> and
997 * <tt>containsAll</tt> methods.</b>
998 */
999 public Collection<V> values() {
1000 Collection<V> vs = values;
1001 if (vs != null)
1002 return vs;
1003 else
1004 return values = new Values();
1005 }
1006
1007 private class Values extends AbstractCollection<V> {
1008 public Iterator<V> iterator() {
1009 return new ValueIterator();
1010 }
1011 public int size() {
1012 return size;
1013 }
1014 public boolean contains(Object o) {
1015 return containsValue(o);
1016 }
1017 public boolean remove(Object o) {
1018 for (Iterator i = iterator(); i.hasNext(); ) {
1019 if (i.next() == o) {
1020 i.remove();
1021 return true;
1022 }
1023 }
1024 return false;
1025 }
1026 public void clear() {
1027 IdentityHashMap.this.clear();
1028 }
1029 }
1030
1031 /**
1032 * Returns a {@link Set} view of the mappings contained in this map.
1033 * Each element in the returned set is a reference-equality-based
1034 * <tt>Map.Entry</tt>. The set is backed by the map, so changes
1035 * to the map are reflected in the set, and vice-versa. If the
1036 * map is modified while an iteration over the set is in progress,
1037 * the results of the iteration are undefined. The set supports
1038 * element removal, which removes the corresponding mapping from
1039 * the map, via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
1040 * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
1041 * methods. It does not support the <tt>add</tt> or
1042 * <tt>addAll</tt> methods.
1043 *
1044 * <p>Like the backing map, the <tt>Map.Entry</tt> objects in the set
1045 * returned by this method define key and value equality as
1046 * reference-equality rather than object-equality. This affects the
1047 * behavior of the <tt>equals</tt> and <tt>hashCode</tt> methods of these
1048 * <tt>Map.Entry</tt> objects. A reference-equality based <tt>Map.Entry
1049 * e</tt> is equal to an object <tt>o</tt> if and only if <tt>o</tt> is a
1050 * <tt>Map.Entry</tt> and <tt>e.getKey()==o.getKey() &&
1051 * e.getValue()==o.getValue()</tt>. To accommodate these equals
1052 * semantics, the <tt>hashCode</tt> method returns
1053 * <tt>System.identityHashCode(e.getKey()) ^
1054 * System.identityHashCode(e.getValue())</tt>.
1055 *
1056 * <p><b>Owing to the reference-equality-based semantics of the
1057 * <tt>Map.Entry</tt> instances in the set returned by this method,
1058 * it is possible that the symmetry and transitivity requirements of
1059 * the {@link Object#equals(Object)} contract may be violated if any of
1060 * the entries in the set is compared to a normal map entry, or if
1061 * the set returned by this method is compared to a set of normal map
1062 * entries (such as would be returned by a call to this method on a normal
1063 * map). However, the <tt>Object.equals</tt> contract is guaranteed to
1064 * hold among identity-based map entries, and among sets of such entries.
1065 * </b>
1066 *
1067 * @return a set view of the identity-mappings contained in this map
1068 */
1069 public Set<Map.Entry<K,V>> entrySet() {
1070 Set<Map.Entry<K,V>> es = entrySet;
1071 if (es != null)
1072 return es;
1073 else
1074 return entrySet = new EntrySet();
1075 }
1076
1077 private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1078 public Iterator<Map.Entry<K,V>> iterator() {
1079 return new EntryIterator();
1080 }
1081 public boolean contains(Object o) {
1082 if (!(o instanceof Map.Entry))
1083 return false;
1084 Map.Entry entry = (Map.Entry)o;
1085 return containsMapping(entry.getKey(), entry.getValue());
1086 }
1087 public boolean remove(Object o) {
1088 if (!(o instanceof Map.Entry))
1089 return false;
1090 Map.Entry entry = (Map.Entry)o;
1091 return removeMapping(entry.getKey(), entry.getValue());
1092 }
1093 public int size() {
1094 return size;
1095 }
1096 public void clear() {
1097 IdentityHashMap.this.clear();
1098 }
1099 /*
1100 * Must revert from AbstractSet's impl to AbstractCollection's, as
1101 * the former contains an optimization that results in incorrect
1102 * behavior when c is a smaller "normal" (non-identity-based) Set.
1103 */
1104 public boolean removeAll(Collection<?> c) {
1105 boolean modified = false;
1106 for (Iterator i = iterator(); i.hasNext(); ) {
1107 if (c.contains(i.next())) {
1108 i.remove();
1109 modified = true;
1110 }
1111 }
1112 return modified;
1113 }
1114
1115 public Object[] toArray() {
1116 int size = size();
1117 Object[] result = new Object[size];
1118 Iterator<Map.Entry<K,V>> it = iterator();
1119 for (int i = 0; i < size; i++)
1120 result[i] = new AbstractMap.SimpleEntry<K,V>(it.next());
1121 return result;
1122 }
1123
1124 @SuppressWarnings("unchecked")
1125 public <T> T[] toArray(T[] a) {
1126 int size = size();
1127 if (a.length < size)
1128 a = (T[])java.lang.reflect.Array
1129 .newInstance(a.getClass().getComponentType(), size);
1130 Iterator<Map.Entry<K,V>> it = iterator();
1131 for (int i = 0; i < size; i++)
1132 a[i] = (T) new AbstractMap.SimpleEntry<K,V>(it.next());
1133 if (a.length > size)
1134 a[size] = null;
1135 return a;
1136 }
1137 }
1138
1139
1140 private static final long serialVersionUID = 8188218128353913216L;
1141
1142 /**
1143 * Save the state of the <tt>IdentityHashMap</tt> instance to a stream
1144 * (i.e., serialize it).
1145 *
1146 * @serialData The <i>size</i> of the HashMap (the number of key-value
1147 * mappings) (<tt>int</tt>), followed by the key (Object) and
1148 * value (Object) for each key-value mapping represented by the
1149 * IdentityHashMap. The key-value mappings are emitted in no
1150 * particular order.
1151 */
1152 private void writeObject(java.io.ObjectOutputStream s)
1153 throws java.io.IOException {
1154 // Write out and any hidden stuff
1155 s.defaultWriteObject();
1156
1157 // Write out size (number of Mappings)
1158 s.writeInt(size);
1159
1160 // Write out keys and values (alternating)
1161 Object[] tab = table;
1162 for (int i = 0; i < tab.length; i += 2) {
1163 Object key = tab[i];
1164 if (key != null) {
1165 s.writeObject(unmaskNull(key));
1166 s.writeObject(tab[i + 1]);
1167 }
1168 }
1169 }
1170
1171 /**
1172 * Reconstitute the <tt>IdentityHashMap</tt> instance from a stream (i.e.,
1173 * deserialize it).
1174 */
1175 private void readObject(java.io.ObjectInputStream s)
1176 throws java.io.IOException, ClassNotFoundException {
1177 // Read in any hidden stuff
1178 s.defaultReadObject();
1179
1180 // Read in size (number of Mappings)
1181 int size = s.readInt();
1182
1183 // Allow for 33% growth (i.e., capacity is >= 2* size()).
1184 init(capacity((size*4)/3));
1185
1186 // Read the keys and values, and put the mappings in the table
1187 for (int i=0; i<size; i++) {
1188 K key = (K) s.readObject();
1189 V value = (V) s.readObject();
1190 putForCreate(key, value);
1191 }
1192 }
1193
1194 /**
1195 * The put method for readObject. It does not resize the table,
1196 * update modCount, etc.
1197 */
1198 private void putForCreate(K key, V value)
1199 throws IOException
1200 {
1201 K k = (K)maskNull(key);
1202 Object[] tab = table;
1203 int len = tab.length;
1204 int i = hash(k, len);
1205
1206 Object item;
1207 while ( (item = tab[i]) != null) {
1208 if (item == k)
1209 throw new java.io.StreamCorruptedException();
1210 i = nextKeyIndex(i, len);
1211 }
1212 tab[i] = k;
1213 tab[i + 1] = value;
1214 }
1215}
1216