Source code: com/go/trove/util/IdentityMap.java
1 /* ====================================================================
2 * Trove - Copyright (c) 1997-2000 Walt Disney Internet Group
3 * ====================================================================
4 * The Tea Software License, Version 1.1
5 *
6 * Copyright (c) 2000 Walt Disney Internet Group. All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 *
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in
17 * the documentation and/or other materials provided with the
18 * distribution.
19 *
20 * 3. The end-user documentation included with the redistribution,
21 * if any, must include the following acknowledgment:
22 * "This product includes software developed by the
23 * Walt Disney Internet Group (http://opensource.go.com/)."
24 * Alternately, this acknowledgment may appear in the software itself,
25 * if and wherever such third-party acknowledgments normally appear.
26 *
27 * 4. The names "Tea", "TeaServlet", "Kettle", "Trove" and "BeanDoc" must
28 * not be used to endorse or promote products derived from this
29 * software without prior written permission. For written
30 * permission, please contact opensource@dig.com.
31 *
32 * 5. Products derived from this software may not be called "Tea",
33 * "TeaServlet", "Kettle" or "Trove", nor may "Tea", "TeaServlet",
34 * "Kettle", "Trove" or "BeanDoc" appear in their name, without prior
35 * written permission of the Walt Disney Internet Group.
36 *
37 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
38 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
39 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
40 * DISCLAIMED. IN NO EVENT SHALL THE WALT DISNEY INTERNET GROUP OR ITS
41 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
42 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
43 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
44 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
45 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
46 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
47 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
48 * ====================================================================
49 *
50 * For more information about Tea, please see http://opensource.go.com/.
51 */
52
53 package com.go.trove.util;
54
55 import java.lang.ref.*;
56 import java.util.*;
57
58 /******************************************************************************
59 * An IdentityMap is like WeakHashMap, except it uses a key's identity
60 * hashcode and equals methods. IdentityMap is not thread-safe and must be
61 * wrapped with Collections.synchronizedMap to be made thread-safe. Most of the
62 * implementation for this class is ripped off from java.util.HashMap, but not
63 * java.util.WeakHashMap, in order to acheive greater efficiency.
64 * <p>
65 * The documentation for WeakHashMap states that it is intended primarily
66 * for use with key objects whose equals methods test for object identity
67 * using the == operator. Because WeakHashMap uses a key's own equals and
68 * hashcode methods, it is better suited for implementing methods that behave
69 * like {@link String#intern}. However, because WeakHashMap stongly references
70 * values, {@link Utils#intern Utils.intern} provides a safer intern mechanism.
71 * <p>
72 * In this implementation, all key objects are tested for equality using the
73 * == operator, and null keys are not permitted. IdentityMap is therefore
74 * better suited for "canonicalized" mappings.
75 * <p>
76 * Note: Weakly referenced entries may be automatically removed during
77 * either accessor or mutator operations, possibly causing a concurrent
78 * modification to be detected. Therefore, even if multiple threads are only
79 * accessing this map, be sure to synchronize this map first. Also, do not
80 * rely on the value returned by size() when using an iterator from this map.
81 * The iterators may return less entries than the amount reported by size().
82 *
83 * @author Brian S O'Neill
84 * @version
85 * <!--$$Revision:--> 19 <!-- $-->, <!--$$JustDate:--> 00/12/18 <!-- $-->
86 * @see java.util.WeakHashMap
87 * @see java.util.HashMap
88 */
89 public class IdentityMap extends AbstractMap implements Map, Cloneable {
90 // Types of Iterators
91 static final int KEYS = 0;
92 static final int VALUES = 1;
93 static final int ENTRIES = 2;
94
95 static final Iterator cEmptyHashIterator = new Iterator() {
96 public boolean hasNext() {
97 return false;
98 }
99
100 public Object next() {
101 throw new NoSuchElementException();
102 }
103
104 public void remove() {
105 throw new IllegalStateException();
106 }
107 };
108
109 /**
110 * Test program.
111 */
112 /*
113 public static void main(String[] args) throws Exception {
114 Map map = new IdentityMap();
115 map.put("Hello", "There");
116 for (int i=0; i<1000000; i++) {
117 if (i % 5 == 0) {
118 map.put(new String("Hello"), "Dude");
119 }
120 map.get("Hello");
121 map.get("Stuff");
122 }
123
124 System.out.println(map.containsValue("Dude"));
125 System.out.println(map.get("Hello"));
126
127 System.gc();
128
129 System.out.println(map);
130 System.out.println(map.size());
131
132 System.out.println(map.containsValue("Dude"));
133 System.out.println(map.get("Hello"));
134
135 map.remove("Hello");
136
137 System.out.println(map);
138 System.out.println(map.size());
139
140 System.out.println(map.containsValue("Dude"));
141 System.out.println(map.get("Hello"));
142 }
143 */
144
145 /**
146 * Converts a string to a collection without calling size(). Iterators from
147 * this map may return less entries than the amount reported by size().
148 */
149 static String toString(Collection c) {
150 StringBuffer buf = new StringBuffer();
151 Iterator it = c.iterator();
152 buf.append("[");
153 for (int i = 0; it.hasNext(); i++) {
154 if (i > 0) {
155 buf.append(", ");
156 }
157 buf.append(String.valueOf(it.next()));
158 }
159 buf.append("]");
160 return buf.toString();
161 }
162
163 /**
164 * The hash table data.
165 */
166 private transient Entry mTable[];
167
168 /**
169 * The total number of mappings in the hash table.
170 */
171 private transient int mCount;
172
173 /**
174 * The table is rehashed when its size exceeds this threshold. (The
175 * value of this field is (int)(capacity * loadFactor).)
176 *
177 * @serial
178 */
179 private int mThreshold;
180
181 /**
182 * The load factor for the hashtable.
183 *
184 * @serial
185 */
186 private float mLoadFactor;
187
188 /**
189 * The number of times this HashMap has been structurally modified
190 * Structural modifications are those that change the number of mappings in
191 * the HashMap or otherwise modify its internal structure (e.g.,
192 * rehash). This field is used to make iterators on Collection-views of
193 * the HashMap fail-fast. (See ConcurrentModificationException).
194 */
195 private transient int mModCount = 0;
196
197 // Views
198
199 private transient Set mKeySet = null;
200 private transient Set mEntrySet = null;
201 private transient Collection mValues = null;
202
203 /**
204 * Constructs a new, empty map with the specified initial
205 * capacity and the specified load factor.
206 *
207 * @param initialCapacity the initial capacity of the HashMap.
208 * @param loadFactor the load factor of the HashMap
209 * @throws IllegalArgumentException if the initial capacity is less
210 * than zero, or if the load factor is nonpositive.
211 */
212 public IdentityMap(int initialCapacity, float loadFactor) {
213 if (initialCapacity < 0) {
214 throw new IllegalArgumentException("Illegal Initial Capacity: "+
215 initialCapacity);
216 }
217
218 if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
219 throw new IllegalArgumentException("Illegal Load factor: "+
220 loadFactor);
221 }
222
223 if (initialCapacity == 0) {
224 initialCapacity = 1;
225 }
226
227 mLoadFactor = loadFactor;
228 mTable = new Entry[initialCapacity];
229 mThreshold = (int)(initialCapacity * loadFactor);
230 }
231
232 /**
233 * Constructs a new, empty map with the specified initial capacity
234 * and default load factor, which is <tt>0.75</tt>.
235 *
236 * @param initialCapacity the initial capacity of the HashMap.
237 * @throws IllegalArgumentException if the initial capacity is less
238 * than zero.
239 */
240 public IdentityMap(int initialCapacity) {
241 this(initialCapacity, 0.75f);
242 }
243
244 /**
245 * Constructs a new, empty map with a default capacity and load
246 * factor, which is <tt>0.75</tt>.
247 */
248 public IdentityMap() {
249 this(11, 0.75f);
250 }
251
252 /**
253 * Constructs a new map with the same mappings as the given map. The
254 * map is created with a capacity of twice the number of mappings in
255 * the given map or 11 (whichever is greater), and a default load factor,
256 * which is <tt>0.75</tt>.
257 */
258 public IdentityMap(Map t) {
259 this(Math.max(2 * t.size(), 11), 0.75f);
260 putAll(t);
261 }
262
263 /**
264 * Returns the number of key-value mappings in this map, but this value
265 * may be larger than actual amount of entries produced by an iterator.
266 *
267 * @return the number of key-value mappings in this map.
268 */
269 public int size() {
270 return mCount;
271 }
272
273 /**
274 * Returns <tt>true</tt> if this map contains no key-value mappings.
275 *
276 * @return <tt>true</tt> if this map contains no key-value mappings.
277 */
278 public boolean isEmpty() {
279 return mCount == 0;
280 }
281
282 /**
283 * Returns <tt>true</tt> if this map maps one or more keys to the
284 * specified value.
285 *
286 * @param value value whose presence in this map is to be tested.
287 * @return <tt>true</tt> if this map maps one or more keys to the
288 * specified value.
289 */
290 public boolean containsValue(Object value) {
291 Entry tab[] = mTable;
292
293 if (value == null) {
294 for (int i = tab.length ; i-- > 0 ;) {
295 for (Entry e = tab[i], prev = null; e != null; e = e.mNext) {
296 if (e.getKey() == null) {
297 // Clean up after a cleared Reference.
298 mModCount++;
299 if (prev != null) {
300 prev.mNext = e.mNext;
301 }
302 else {
303 tab[i] = e.mNext;
304 }
305 mCount--;
306 }
307 else if (e.mValue == null) {
308 return true;
309 }
310 else {
311 prev = e;
312 }
313 }
314 }
315 }
316 else {
317 for (int i = tab.length ; i-- > 0 ;) {
318 for (Entry e = tab[i], prev = null; e != null; e = e.mNext) {
319 if (e.getKey() == null) {
320 // Clean up after a cleared Reference.
321 mModCount++;
322 if (prev != null) {
323 prev.mNext = e.mNext;
324 }
325 else {
326 tab[i] = e.mNext;
327 }
328 mCount--;
329 }
330 else if (value.equals(e.mValue)) {
331 return true;
332 }
333 else {
334 prev = e;
335 }
336 }
337 }
338 }
339
340 return false;
341 }
342
343 /**
344 * Returns <tt>true</tt> if this map contains a mapping for the specified
345 * key.
346 *
347 * @return <tt>true</tt> if this map contains a mapping for the specified
348 * key.
349 * @param key key whose presence in this Map is to be tested.
350 */
351 public boolean containsKey(Object key) {
352 if (key == null) {
353 return false;
354 }
355
356 Entry tab[] = mTable;
357 int hash = System.identityHashCode(key);
358 int index = (hash & 0x7FFFFFFF) % tab.length;
359
360 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) {
361 Object entryKey = e.getKey();
362
363 if (entryKey == null) {
364 // Clean up after a cleared Reference.
365 mModCount++;
366 if (prev != null) {
367 prev.mNext = e.mNext;
368 }
369 else {
370 tab[index] = e.mNext;
371 }
372 mCount--;
373 }
374 else if (e.mHash == hash && key == entryKey) {
375 return true;
376 }
377 else {
378 prev = e;
379 }
380 }
381
382 return false;
383 }
384
385 /**
386 * Returns the value to which this map maps the specified key. Returns
387 * <tt>null</tt> if the map contains no mapping for this key. A return
388 * value of <tt>null</tt> does not <i>necessarily</i> indicate that the
389 * map contains no mapping for the key; it's also possible that the map
390 * explicitly maps the key to <tt>null</tt>. The <tt>containsKey</tt>
391 * operation may be used to distinguish these two cases.
392 *
393 * @return the value to which this map maps the specified key.
394 * @param key key whose associated value is to be returned.
395 */
396 public Object get(Object key) {
397 if (key == null) {
398 return null;
399 }
400
401 Entry tab[] = mTable;
402 int hash = System.identityHashCode(key);
403 int index = (hash & 0x7FFFFFFF) % tab.length;
404
405 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) {
406 Object entryKey = e.getKey();
407
408 if (entryKey == null) {
409 // Clean up after a cleared Reference.
410 mModCount++;
411 if (prev != null) {
412 prev.mNext = e.mNext;
413 }
414 else {
415 tab[index] = e.mNext;
416 }
417 mCount--;
418 }
419 else if (e.mHash == hash && key == entryKey) {
420 return e.mValue;
421 }
422 else {
423 prev = e;
424 }
425 }
426
427 return null;
428 }
429
430 /**
431 * Scans the contents of this map, removing all entries that have a
432 * cleared weak key.
433 */
434 private void cleanup() {
435 Entry tab[] = mTable;
436
437 for (int i = tab.length ; i-- > 0 ;) {
438 for (Entry e = tab[i], prev = null; e != null; e = e.mNext) {
439 if (e.getKey() == null) {
440 // Clean up after a cleared Reference.
441 mModCount++;
442 if (prev != null) {
443 prev.mNext = e.mNext;
444 }
445 else {
446 tab[i] = e.mNext;
447 }
448 mCount--;
449 }
450 else {
451 prev = e;
452 }
453 }
454 }
455 }
456
457 /**
458 * Rehashes the contents of this map into a new <tt>HashMap</tt> instance
459 * with a larger capacity. This method is called automatically when the
460 * number of keys in this map exceeds its capacity and load factor.
461 */
462 private void rehash() {
463 int oldCapacity = mTable.length;
464 Entry oldMap[] = mTable;
465
466 int newCapacity = oldCapacity * 2 + 1;
467 Entry newMap[] = new Entry[newCapacity];
468
469 mModCount++;
470 mThreshold = (int)(newCapacity * mLoadFactor);
471 mTable = newMap;
472
473 for (int i = oldCapacity ; i-- > 0 ;) {
474 for (Entry old = oldMap[i] ; old != null ; ) {
475 Entry e = old;
476 old = old.mNext;
477
478 // Only copy entry if its key hasn't been cleared.
479 if (e.getKey() == null) {
480 mCount--;
481 }
482 else {
483 int index = (e.mHash & 0x7FFFFFFF) % newCapacity;
484 e.mNext = newMap[index];
485 newMap[index] = e;
486 }
487 }
488 }
489 }
490
491 /**
492 * Associates the specified value with the specified key in this map.
493 * If the map previously contained a mapping for this key, the old
494 * value is replaced.
495 *
496 * @param key key with which the specified value is to be associated.
497 * @param value value to be associated with the specified key.
498 * @return previous value associated with specified key, or <tt>null</tt>
499 * if there was no mapping for key. A <tt>null</tt> return can
500 * also indicate that the HashMap previously associated
501 * <tt>null</tt> with the specified key.
502 */
503 public Object put(Object key, Object value) {
504 if (key == null) {
505 throw new NullPointerException("Null key is not permitted");
506 }
507
508 // Makes sure the key is not already in the HashMap.
509 Entry tab[] = mTable;
510 int hash = System.identityHashCode(key);
511 int index = (hash & 0x7FFFFFFF) % tab.length;
512
513 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) {
514 Object entryKey = e.getKey();
515
516 if (entryKey == null) {
517 // Clean up after a cleared Reference.
518 mModCount++;
519 if (prev != null) {
520 prev.mNext = e.mNext;
521 }
522 else {
523 tab[index] = e.mNext;
524 }
525 mCount--;
526 }
527 else if (e.mHash == hash && key == entryKey) {
528 Object old = e.mValue;
529 e.mValue = value;
530 return old;
531 }
532 else {
533 prev = e;
534 }
535 }
536
537 mModCount++;
538
539 if (mCount >= mThreshold) {
540 // Cleanup the table if the threshold is exceeded.
541 cleanup();
542 }
543
544 if (mCount >= mThreshold) {
545 // Rehash the table if the threshold is still exceeded.
546 rehash();
547 tab = mTable;
548 index = (hash & 0x7FFFFFFF) % tab.length;
549 }
550
551 // Creates the new entry.
552 Entry e = new Entry(hash, key, value, tab[index]);
553 tab[index] = e;
554 mCount++;
555 return null;
556 }
557
558 /**
559 * Removes the mapping for this key from this map if present.
560 *
561 * @param key key whose mapping is to be removed from the map.
562 * @return previous value associated with specified key, or <tt>null</tt>
563 * if there was no mapping for key. A <tt>null</tt> return can
564 * also indicate that the map previously associated <tt>null</tt>
565 * with the specified key.
566 */
567 public Object remove(Object key) {
568 Entry tab[] = mTable;
569 int hash = System.identityHashCode(key);
570 int index = (hash & 0x7FFFFFFF) % tab.length;
571
572 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) {
573 Object entryKey = e.getKey();
574
575 if (entryKey == null) {
576 // Clean up after a cleared Reference.
577 mModCount++;
578 if (prev != null) {
579 prev.mNext = e.mNext;
580 }
581 else {
582 tab[index] = e.mNext;
583 }
584 mCount--;
585 }
586 else if (e.mHash == hash && key == entryKey) {
587 mModCount++;
588 if (prev != null) {
589 prev.mNext = e.mNext;
590 }
591 else {
592 tab[index] = e.mNext;
593 }
594 mCount--;
595
596 Object oldValue = e.mValue;
597 e.mValue = null;
598 return oldValue;
599 }
600 else {
601 prev = e;
602 }
603 }
604
605 return null;
606 }
607
608 /**
609 * Copies all of the mappings from the specified map to this one.
610 *
611 * These mappings replace any mappings that this map had for any of the
612 * keys currently in the specified Map.
613 *
614 * @param t Mappings to be stored in this map.
615 */
616 public void putAll(Map t) {
617 Iterator i = t.entrySet().iterator();
618 while (i.hasNext()) {
619 Map.Entry e = (Map.Entry) i.next();
620 put(e.getKey(), e.getValue());
621 }
622 }
623
624 /**
625 * Removes all mappings from this map.
626 */
627 public void clear() {
628 Entry tab[] = mTable;
629 mModCount++;
630 for (int index = tab.length; --index >= 0; ) {
631 tab[index] = null;
632 }
633 mCount = 0;
634 }
635
636 /**
637 * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
638 * values themselves are not cloned.
639 *
640 * @return a shallow copy of this map.
641 */
642 public Object clone() {
643 try {
644 IdentityMap t = (IdentityMap)super.clone();
645 t.mTable = new Entry[mTable.length];
646 for (int i = mTable.length ; i-- > 0 ; ) {
647 t.mTable[i] = (mTable[i] != null)
648 ? (Entry)mTable[i].clone() : null;
649 }
650 t.mKeySet = null;
651 t.mEntrySet = null;
652 t.mValues = null;
653 t.mModCount = 0;
654 return t;
655 }
656 catch (CloneNotSupportedException e) {
657 // this shouldn't happen, since we are Cloneable
658 throw new InternalError();
659 }
660 }
661
662 /**
663 * Returns a set view of the keys contained in this map. The set is
664 * backed by the map, so changes to the map are reflected in the set, and
665 * vice-versa. The set supports element removal, which removes the
666 * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
667 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
668 * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
669 * <tt>addAll</tt> operations.
670 *
671 * @return a set view of the keys contained in this map.
672 */
673 public Set keySet() {
674 if (mKeySet == null) {
675 mKeySet = new AbstractSet() {
676 public Iterator iterator() {
677 return getHashIterator(KEYS);
678 }
679 public int size() {
680 return mCount;
681 }
682 public boolean contains(Object o) {
683 return containsKey(o);
684 }
685 public boolean remove(Object o) {
686 return o == null ? false : IdentityMap.this.remove(o) == o;
687 }
688 public void clear() {
689 IdentityMap.this.clear();
690 }
691 public String toString() {
692 return IdentityMap.this.toString(this);
693 }
694 };
695 }
696 return mKeySet;
697 }
698
699 /**
700 * Returns a collection view of the values contained in this map. The
701 * collection is backed by the map, so changes to the map are reflected in
702 * the collection, and vice-versa. The collection supports element
703 * removal, which removes the corresponding mapping from this map, via the
704 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
705 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
706 * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
707 *
708 * @return a collection view of the values contained in this map.
709 */
710 public Collection values() {
711 if (mValues==null) {
712 mValues = new AbstractCollection() {
713 public Iterator iterator() {
714 return getHashIterator(VALUES);
715 }
716 public int size() {
717 return mCount;
718 }
719 public boolean contains(Object o) {
720 return containsValue(o);
721 }
722 public void clear() {
723 IdentityMap.this.clear();
724 }
725 public String toString() {
726 return IdentityMap.this.toString(this);
727 }
728 };
729 }
730 return mValues;
731 }
732
733 /**
734 * Returns a collection view of the mappings contained in this map. Each
735 * element in the returned collection is a <tt>Map.Entry</tt>. The
736 * collection is backed by the map, so changes to the map are reflected in
737 * the collection, and vice-versa. The collection supports element
738 * removal, which removes the corresponding mapping from the map, via the
739 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
740 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
741 * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
742 *
743 * @return a collection view of the mappings contained in this map.
744 * @see Map.Entry
745 */
746 public Set entrySet() {
747 if (mEntrySet==null) {
748 mEntrySet = new AbstractSet() {
749 public Iterator iterator() {
750 return getHashIterator(ENTRIES);
751 }
752
753 public boolean contains(Object o) {
754 if (!(o instanceof Map.Entry)) {
755 return false;
756 }
757 Map.Entry entry = (Map.Entry)o;
758 Object key = entry.getKey();
759
760 Entry tab[] = mTable;
761 int hash = System.identityHashCode(key);
762 int index = (hash & 0x7FFFFFFF) % tab.length;
763
764 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) {
765 Object entryKey = e.getKey();
766
767 if (entryKey == null) {
768 // Clean up after a cleared Reference.
769 mModCount++;
770 if (prev != null) {
771 prev.mNext = e.mNext;
772 }
773 else {
774 tab[index] = e.mNext;
775 }
776 mCount--;
777 }
778 else if (e.mHash == hash && e.identityEquals(entry)) {
779 return true;
780 }
781 else {
782 prev = e;
783 }
784 }
785
786 return false;
787 }
788
789 public boolean remove(Object o) {
790 if (!(o instanceof Map.Entry)) {
791 return false;
792 }
793 Map.Entry entry = (Map.Entry)o;
794 Object key = entry.getKey();
795 Entry tab[] = mTable;
796 int hash = System.identityHashCode(key);
797 int index = (hash & 0x7FFFFFFF) % tab.length;
798
799 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) {
800 Object entryKey = e.getKey();
801
802 if (entryKey == null) {
803 // Clean up after a cleared Reference.
804 mModCount++;
805 if (prev != null) {
806 prev.mNext = e.mNext;
807 }
808 else {
809 tab[index] = e.mNext;
810 }
811 mCount--;
812 }
813 else if (e.mHash == hash && e.identityEquals(entry)) {
814 mModCount++;
815 if (prev != null) {
816 prev.mNext = e.mNext;
817 }
818 else {
819 tab[index] = e.mNext;
820 }
821 mCount--;
822
823 e.mValue = null;
824 return true;
825 }
826 else {
827 prev = e;
828 }
829 }
830 return false;
831 }
832
833 public int size() {
834 return mCount;
835 }
836
837 public void clear() {
838 IdentityMap.this.clear();
839 }
840
841 public String toString() {
842 return IdentityMap.this.toString(this);
843 }
844 };
845 }
846
847 return mEntrySet;
848 }
849
850 public String toString() {
851 StringBuffer buf = new StringBuffer();
852 Iterator it = entrySet().iterator();
853
854 buf.append("{");
855 for (int i = 0; it.hasNext(); i++) {
856 if (i > 0) {
857 buf.append(", ");
858 }
859 Map.Entry e = (Map.Entry)it.next();
860 buf.append(e.getKey() + "=" + e.getValue());
861 }
862 buf.append("}");
863 return buf.toString();
864 }
865
866 private Iterator getHashIterator(int type) {
867 if (mCount == 0) {
868 return cEmptyHashIterator;
869 }
870 else {
871 return new HashIterator(type);
872 }
873 }
874
875 /**
876 * HashMap collision list entry.
877 */
878 private static class Entry extends WeakReference implements Map.Entry {
879 int mHash;
880 Object mValue;
881 Entry mNext;
882
883 Entry(int hash, Object key, Object value, Entry next) {
884 super(key);
885 mHash = hash;
886 mValue = value;
887 mNext = next;
888 }
889
890 protected Object clone() {
891 return new Entry(mHash, getKey(), mValue,
892 (mNext == null ? null : (Entry)mNext.clone()));
893 }
894
895 // Map.Entry Ops
896
897 public Object getKey() {
898 return Entry.this.get();
899 }
900
901 public Object getValue() {
902 return mValue;
903 }
904
905 public Object setValue(Object value) {
906 Object oldValue = mValue;
907 mValue = value;
908 return oldValue;
909 }
910
911 public boolean equals(Object o) {
912 if (!(o instanceof Map.Entry)) {
913 return false;
914 }
915 Map.Entry e = (Map.Entry)o;
916
917 Object key = getKey();
918
919 return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
920 (mValue==null ? e.getValue()==null : mValue.equals(e.getValue()));
921 }
922
923 public boolean identityEquals(Map.Entry e) {
924 return (getKey() == e.getKey()) &&
925 (mValue==null ? e.getValue()==null : mValue.equals(e.getValue()));
926 }
927
928 public int hashCode() {
929 return mHash ^ (mValue==null ? 0 : mValue.hashCode());
930 }
931
932 public String toString() {
933 return getKey() + "=" + mValue;
934 }
935 }
936
937 private class HashIterator implements Iterator {
938 private Entry[] mTable = IdentityMap.this.mTable;
939 private int mIndex = mTable.length;
940 private Entry mEntry;
941 // To ensure that the iterator doesn't return cleared entries, keep a
942 // hard reference to the key. Its existence will prevent the weak
943 // key from being cleared.
944 private Object mEntryKey;
945 private Entry mLastReturned;
946 private int mType;
947
948 /**
949 * The modCount value that the iterator believes that the backing
950 * List should have. If this expectation is violated, the iterator
951 * has detected concurrent modification.
952 */
953 private int expectedModCount = mModCount;
954
955 HashIterator(int type) {
956 mType = type;
957 }
958
959 public boolean hasNext() {
960 while (mEntry == null ||
961 (mEntryKey = mEntry.getKey()) == null) {
962 if (mEntry != null) {
963 // Clean up after a cleared Reference.
964 remove(mEntry);
965 mEntry = mEntry.mNext;
966 }
967 else {
968 if (mIndex <= 0) {
969 return false;
970 }
971 else {
972 mEntry = mTable[--mIndex];
973 }
974 }
975 }
976
977 return true;
978 }
979
980 public Object next() {
981 if (mModCount != expectedModCount) {
982 throw new ConcurrentModificationException();
983 }
984
985 if (!hasNext()) {
986 throw new NoSuchElementException();
987 }
988
989 mLastReturned = mEntry;
990 mEntry = mEntry.mNext;
991
992 return mType == KEYS ? mLastReturned.getKey() :
993 (mType == VALUES ? mLastReturned.getValue() : mLastReturned);
994 }
995
996 public void remove() {
997 if (mLastReturned == null) {
998 throw new IllegalStateException();
999 }
1000 if (mModCount != expectedModCount) {
1001 throw new ConcurrentModificationException();
1002 }
1003 remove(mLastReturned);
1004 mLastReturned = null;
1005 }
1006
1007 private void remove(Entry toRemove) {
1008 Entry[] tab = mTable;
1009 int index = (toRemove.mHash & 0x7FFFFFFF) % tab.length;
1010
1011 for (Entry e = tab[index], prev = null; e != null; e = e.mNext) {
1012 if (e == toRemove) {
1013 mModCount++;
1014 expectedModCount++;
1015 if (prev == null) {
1016 tab[index] = e.mNext;
1017 }
1018 else {
1019 prev.mNext = e.mNext;
1020 }
1021 mCount--;
1022 return;
1023 }
1024 else {
1025 prev = e;
1026 }
1027 }
1028 throw new ConcurrentModificationException();
1029 }
1030 }
1031}