Java > Open Source Codes > com > go > trove > util > IdentityMap


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}
1032

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags