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


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  * A Map that softly references its values and can be used as a simple cache.
60  * SoftHashMap is not thread-safe and must be wrapped with
61  * Collections.synchronizedMap to be made thread-safe. Most of the
62  * implementation for this class is ripped off from java.util.HashMap
63  * <p>
64  * Note: Softly referenced entries may be automatically removed during
65  * either accessor or mutator operations, possibly causing a concurrent
66  * modification to be detected. Therefore, even if multiple threads are only
67  * accessing this map, be sure to synchronize this map first. Also, do not
68  * rely on the value returned by size() when using an iterator from this map.
69  * The iterators may return less entries than the amount reported by size().
70  *
71  * @author Brian S O'Neill
72  * @version
73  * <!--$$Revision:--> 22 <!-- $-->, <!--$$JustDate:--> 9/07/00 <!-- $-->
74  * @see Cache
75  */
76 public class SoftHashMap extends AbstractMap implements Map, Cloneable {
77     /**
78      * Test program.
79      */
80     /*
81     public static void main(String[] arg) throws Exception {
82         Map cache = new SoftHashMap();
83
84         for (int i = 0, j = 0; i < 100000; i++, j += 15) {
85             if (i % 100 == 0) {
86                 System.out.println("Size = " + cache.size());
87             }
88
89             //Thread.sleep(1);
90
91             Integer key = new Integer(i);
92             Integer value = new Integer(j);
93             
94             cache.put(key, value);
95         }
96       
97         Map.Entry entry = (Map.Entry)cache.entrySet().iterator().next();
98         System.out.println(entry);
99         //entry = null;
100
101         System.out.println(cache);
102
103         int originalSize = cache.size();
104
105         //cache = null;
106
107         for (int i=0; i<100; i++) {
108             System.gc();
109         }
110
111         System.out.println(cache);
112
113         System.out.println(originalSize);
114         System.out.println(cache.size());
115         System.out.println(entry);
116
117         Thread.sleep(1000000);
118     }
119     */
120
121     /**
122      * The hash table data.
123      */
124     private transient Entry mTable[];
125
126     /**
127      * The total number of mappings in the hash table.
128      */
129     private transient int mCount;
130
131     /**
132      * The table is rehashed when its size exceeds this threshold. (The
133      * value of this field is (int)(capacity * loadFactor).)
134      *
135      * @serial
136      */
137     private int mThreshold;
138
139     /**
140      * The load factor for the hashtable.
141      *
142      * @serial
143      */
144     private float mLoadFactor;
145
146     /**
147      * The number of times this HashMap has been structurally modified
148      * Structural modifications are those that change the number of mappings in
149      * the HashMap or otherwise modify its internal structure (e.g.,
150      * rehash). This field is used to make iterators on Collection-views of
151      * the HashMap fail-fast. (See ConcurrentModificationException).
152      */
153     private transient int mModCount = 0;
154
155     // Views
156
157     private transient Set mKeySet = null;
158     private transient Set mEntrySet = null;
159     private transient Collection mValues = null;
160
161     /**
162      * Constructs a new, empty map with the specified initial
163      * capacity and the specified load factor.
164      *
165      * @param initialCapacity the initial capacity of the HashMap.
166      * @param loadFactor the load factor of the HashMap
167      * @throws IllegalArgumentException if the initial capacity is less
168      * than zero, or if the load factor is nonpositive.
169      */
170     public SoftHashMap(int initialCapacity, float loadFactor) {
171         if (initialCapacity < 0) {
172             throw new IllegalArgumentException ("Illegal Initial Capacity: "+
173                                                initialCapacity);
174         }
175
176         if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
177             throw new IllegalArgumentException ("Illegal Load factor: "+
178                                                loadFactor);
179         }
180
181         if (initialCapacity == 0) {
182             initialCapacity = 1;
183         }
184
185         mLoadFactor = loadFactor;
186         mTable = new Entry[initialCapacity];
187         mThreshold = (int)(initialCapacity * loadFactor);
188     }
189     
190     /**
191      * Constructs a new, empty map with the specified initial capacity
192      * and default load factor, which is <tt>0.75</tt>.
193      *
194      * @param initialCapacity the initial capacity of the HashMap.
195      * @throws IllegalArgumentException if the initial capacity is less
196      * than zero.
197      */
198     public SoftHashMap(int initialCapacity) {
199         this(initialCapacity, 0.75f);
200     }
201
202     /**
203      * Constructs a new, empty map with a default capacity and load
204      * factor, which is <tt>0.75</tt>.
205      */
206     public SoftHashMap() {
207         this(11, 0.75f);
208     }
209
210     /**
211      * Constructs a new map with the same mappings as the given map. The
212      * map is created with a capacity of twice the number of mappings in
213      * the given map or 11 (whichever is greater), and a default load factor,
214      * which is <tt>0.75</tt>.
215      */
216     public SoftHashMap(Map t) {
217         this(Math.max(2 * t.size(), 11), 0.75f);
218         putAll(t);
219     }
220
221     /**
222      * Returns the number of key-value mappings in this map, but this value
223      * may be larger than actual amount of entries produced by an iterator.
224      *
225      * @return the number of key-value mappings in this map.
226      */
227     public int size() {
228         return mCount;
229     }
230
231     /**
232      * Returns <tt>true</tt> if this map contains no key-value mappings.
233      *
234      * @return <tt>true</tt> if this map contains no key-value mappings.
235      */
236     public boolean isEmpty() {
237         return mCount == 0;
238     }
239
240     /**
241      * Returns <tt>true</tt> if this map maps one or more keys to the
242      * specified value.
243      *
244      * @param value value whose presence in this map is to be tested.
245      * @return <tt>true</tt> if this map maps one or more keys to the
246      * specified value.
247      */
248     public boolean containsValue(Object value) {
249         if (value == null) {
250             value = new Null();
251         }
252
253         Entry tab[] = mTable;
254         
255         for (int i = tab.length ; i-- > 0 ;) {
256             for (Entry e = tab[i], prev = null; e != null; e = e.mNext) {
257                 Object entryValue = e.getValue();
258
259                 if (entryValue == null) {
260                     // Clean up after a cleared Reference.
261 mModCount++;
262                     if (prev != null) {
263                         prev.mNext = e.mNext;
264                     }
265                     else {
266                         tab[i] = e.mNext;
267                     }
268                     mCount--;
269                 }
270                 else if (value.equals(entryValue)) {
271                     return true;
272                 }
273                 else {
274                     prev = e;
275                 }
276             }
277         }
278
279         return false;
280     }
281
282     /**
283      * Returns <tt>true</tt> if this map contains a mapping for the specified
284      * key.
285      *
286      * @return <tt>true</tt> if this map contains a mapping for the specified
287      * key.
288      * @param key key whose presence in this Map is to be tested.
289      */
290     public boolean containsKey(Object key) {
291         Entry tab[] = mTable;
292
293         if (key != null) {
294             int hash = key.hashCode();
295             int index = (hash & 0x7FFFFFFF) % tab.length;
296             for (Entry e = tab[index], prev = null; e != null; e = e.mNext) {
297                 if (e.getValue() == null) {
298                     // Clean up after a cleared Reference.
299 mModCount++;
300                     if (prev != null) {
301                         prev.mNext = e.mNext;
302                     }
303                     else {
304                         tab[index] = e.mNext;
305                     }
306                     mCount--;
307                 }
308                 else if (e.mHash == hash && key.equals(e.mKey)) {
309                     return true;
310                 }
311                 else {
312                     prev = e;
313                 }
314             }
315         }
316         else {
317             for (Entry e = tab[0], prev = null; e != null; e = e.mNext) {
318                 if (e.getValue() == null) {
319                     // Clean up after a cleared Reference.
320 mModCount++;
321                     if (prev != null) {
322                         prev.mNext = e.mNext;
323                     }
324                     else {
325                         tab[0] = e.mNext;
326                     }
327                     mCount--;
328                 }
329                 else if (e.mKey == null) {
330                     return true;
331                 }
332                 else {
333                     prev = e;
334                 }
335             }
336         }
337
338         return false;
339     }
340
341     /**
342      * Returns the value to which this map maps the specified key. Returns
343      * <tt>null</tt> if the map contains no mapping for this key. A return
344      * value of <tt>null</tt> does not <i>necessarily</i> indicate that the
345      * map contains no mapping for the key; it's also possible that the map
346      * explicitly maps the key to <tt>null</tt>. The <tt>containsKey</tt>
347      * operation may be used to distinguish these two cases.
348      *
349      * @return the value to which this map maps the specified key.
350      * @param key key whose associated value is to be returned.
351      */
352     public Object get(Object key) {
353         Entry tab[] = mTable;
354
355         if (key != null) {
356             int hash = key.hashCode();
357             int index = (hash & 0x7FFFFFFF) % tab.length;
358
359             for (Entry e = tab[index], prev = null; e != null; e = e.mNext) {
360                 Object entryValue = e.getValue();
361
362                 if (entryValue == null) {
363                     // Clean up after a cleared Reference.
364 mModCount++;
365                     if (prev != null) {
366                         prev.mNext = e.mNext;
367                     }
368                     else {
369                         tab[index] = e.mNext;
370                     }
371                     mCount--;
372                 }
373                 else if (e.mHash == hash && key.equals(e.mKey)) {
374                     return (entryValue instanceof Null) ? null : entryValue;
375                 }
376                 else {
377                     prev = e;
378                 }
379             }
380         }
381         else {
382             for (Entry e = tab[0], prev = null; e != null; e = e.mNext) {
383                 Object entryValue = e.getValue();
384
385                 if (entryValue == null) {
386                     // Clean up after a cleared Reference.
387 mModCount++;
388                     if (prev != null) {
389                         prev.mNext = e.mNext;
390                     }
391                     else {
392                         tab[0] = e.mNext;
393                     }
394                     mCount--;
395                 }
396                 else if (e.mKey == null) {
397                     return (entryValue instanceof Null) ? null : entryValue;
398                 }
399                 else {
400                     prev = e;
401                 }
402             }
403         }
404
405         return null;
406     }
407
408     /**
409      * Scans the contents of this map, removing all entries that have a
410      * cleared soft value.
411      */
412     private void cleanup() {
413         Entry tab[] = mTable;
414         
415         for (int i = tab.length ; i-- > 0 ;) {
416             for (Entry e = tab[i], prev = null; e != null; e = e.mNext) {
417                 if (e.getValue() == null) {
418                     // Clean up after a cleared Reference.
419 mModCount++;
420                     if (prev != null) {
421                         prev.mNext = e.mNext;
422                     }
423                     else {
424                         tab[i] = e.mNext;
425                     }
426                     mCount--;
427                 }
428                 else {
429                     prev = e;
430                 }
431             }
432         }
433     }
434
435     /**
436      * Rehashes the contents of this map into a new <tt>HashMap</tt> instance
437      * with a larger capacity. This method is called automatically when the
438      * number of keys in this map exceeds its capacity and load factor.
439      */
440     private void rehash() {
441         int oldCapacity = mTable.length;
442         Entry oldMap[] = mTable;
443         
444         int newCapacity = oldCapacity * 2 + 1;
445         Entry newMap[] = new Entry[newCapacity];
446         
447         mModCount++;
448         mThreshold = (int)(newCapacity * mLoadFactor);
449         mTable = newMap;
450         
451         for (int i = oldCapacity ; i-- > 0 ;) {
452             for (Entry old = oldMap[i] ; old != null ; ) {
453                 Entry e = old;
454                 old = old.mNext;
455
456                 // Only copy entry if its value hasn't been cleared.
457 if (e.getValue() == null) {
458                     mCount--;
459                 }
460                 else {
461                     int index = (e.mHash & 0x7FFFFFFF) % newCapacity;
462                     e.mNext = newMap[index];
463                     newMap[index] = e;
464                 }
465             }
466         }
467     }
468     
469     /**
470      * Associates the specified value with the specified key in this map.
471      * If the map previously contained a mapping for this key, the old
472      * value is replaced.
473      *
474      * @param key key with which the specified value is to be associated.
475      * @param value value to be associated with the specified key.
476      * @return previous value associated with specified key, or <tt>null</tt>
477      * if there was no mapping for key. A <tt>null</tt> return can
478      * also indicate that the HashMap previously associated
479      * <tt>null</tt> with the specified key.
480      */
481     public Object put(Object key, Object value) {
482         if (value == null) {
483             value = new Null();
484         }
485
486         // Makes sure the key is not already in the HashMap.
487 Entry tab[] = mTable;
488         int hash;
489         int index;
490
491         if (key != null) {
492             hash = key.hashCode();
493             index = (hash & 0x7FFFFFFF) % tab.length;
494             for (Entry e = tab[index], prev = null; e != null; e = e.mNext) {
495                 Object entryValue = e.getValue();
496
497                 if (e.getValue() == null) {
498                     // Clean up after a cleared Reference.
499 mModCount++;
500                     if (prev != null) {
501                         prev.mNext = e.mNext;
502                     }
503                     else {
504                         tab[index] = e.mNext;
505                     }
506                     mCount--;
507                 }
508                 else if (e.mHash == hash && key.equals(e.mKey)) {
509                     e.setValue(value);
510                     return (entryValue instanceof Null) ? null : entryValue;
511                 }
512                 else {
513                     prev = e;
514                 }
515             }
516         }
517         else {
518             hash = 0;
519             index = 0;
520             for (Entry e = tab[0], prev = null; e != null; e = e.mNext) {
521                 Object entryValue = e.getValue();
522
523                 if (entryValue == null) {
524                     // Clean up after a cleared Reference.
525 mModCount++;
526                     if (prev != null) {
527                         prev.mNext = e.mNext;
528                     }
529                     else {
530                         tab[0] = e.mNext;
531                     }
532                     mCount--;
533                 }
534                 else if (e.mKey == null) {
535                     e.setValue(value);
536                     return (entryValue instanceof Null) ? null : entryValue;
537                 }
538                 else {
539                     prev = e;
540                 }
541             }
542         }
543
544         mModCount++;
545
546         if (mCount >= mThreshold) {
547             // Cleanup the table if the threshold is exceeded.
548 cleanup();
549         }
550
551         if (mCount >= mThreshold) {
552             // Rehash the table if the threshold is still exceeded.
553 rehash();
554             tab = mTable;
555             index = (hash & 0x7FFFFFFF) % tab.length;
556         }
557         
558         // Creates the new entry.
559 Entry e = new Entry(hash, key, (Object )value, tab[index]);
560         tab[index] = e;
561         mCount++;
562         return null;
563     }
564     
565     /**
566      * Removes the mapping for this key from this map if present.
567      *
568      * @param key key whose mapping is to be removed from the map.
569      * @return previous value associated with specified key, or <tt>null</tt>
570      * if there was no mapping for key. A <tt>null</tt> return can
571      * also indicate that the map previously associated <tt>null</tt>
572      * with the specified key.
573      */
574     public Object remove(Object key) {
575         Entry tab[] = mTable;
576
577         if (key != null) {
578             int hash = key.hashCode();
579             int index = (hash & 0x7FFFFFFF) % tab.length;
580             
581             for (Entry e = tab[index], prev = null; e != null; e = e.mNext) {
582                 Object entryValue = e.getValue();
583
584                 if (entryValue == null) {
585                     // Clean up after a cleared Reference.
586 mModCount++;
587                     if (prev != null) {
588                         prev.mNext = e.mNext;
589                     }
590                     else {
591                         tab[index] = e.mNext;
592                     }
593                     mCount--;
594                 }
595                 else if (e.mHash == hash && key.equals(e.mKey)) {
596                     mModCount++;
597                     if (prev != null) {
598                         prev.mNext = e.mNext;
599                     }
600                     else {
601                         tab[index] = e.mNext;
602                     }
603                     mCount--;
604
605                     e.setValue(null);
606                     return (entryValue instanceof Null) ? null : entryValue;
607                 }
608                 else {
609                     prev = e;
610                 }
611             }
612         }
613         else {
614             for (Entry e = tab[0], prev = null; e != null; e = e.mNext) {
615                 Object entryValue = e.getValue();
616
617                 if (entryValue == null) {
618                     // Clean up after a cleared Reference.
619 mModCount++;
620                     if (prev != null) {
621                         prev.mNext = e.mNext;
622                     }
623                     else {
624                         tab[0] = e.mNext;
625                     }
626                     mCount--;
627                 }
628                 else if (e.mKey == null) {
629                     mModCount++;
630                     if (prev != null) {
631                         prev.mNext = e.mNext;
632                     }
633                     else {
634                         tab[0] = e.mNext;
635                     }
636                     mCount--;
637
638                     e.setValue(null);
639                     return (entryValue instanceof Null) ? null : entryValue;
640                 }
641                 else {
642                     prev = e;
643                 }
644             }
645         }
646
647         return null;
648     }
649     
650     /**
651      * Copies all of the mappings from the specified map to this one.
652      *
653      * These mappings replace any mappings that this map had for any of the
654      * keys currently in the specified Map.
655      *
656      * @param t Mappings to be stored in this map.
657      */
658     public void putAll(Map t) {
659         Iterator i = t.entrySet().iterator();
660         while (i.hasNext()) {
661             Map.Entry e = (Map.Entry) i.next();
662             put(e.getKey(), e.getValue());
663         }
664     }
665
666     /**
667      * Removes all mappings from this map.
668      */
669     public void clear() {
670         Entry tab[] = mTable;
671         mModCount++;
672         for (int index = tab.length; --index >= 0; ) {
673             tab[index] = null;
674         }
675         mCount = 0;
676     }
677
678     /**
679      * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
680      * values themselves are not cloned.
681      *
682      * @return a shallow copy of this map.
683      */
684     public Object clone() {
685         try {
686             SoftHashMap t = (SoftHashMap)super.clone();
687             t.mTable = new Entry[mTable.length];
688             for (int i = mTable.length ; i-- > 0 ; ) {
689                 t.mTable[i] = (mTable[i] != null)
690                     ? (Entry)mTable[i].clone() : null;
691             }
692             t.mKeySet = null;
693             t.mEntrySet = null;
694             t.mValues = null;
695             t.mModCount = 0;
696             return t;
697         }
698         catch (CloneNotSupportedException e) {
699             // this shouldn't happen, since we are Cloneable
700 throw new InternalError ();
701         }
702     }
703     
704     /**
705      * Returns a set view of the keys contained in this map. The set is
706      * backed by the map, so changes to the map are reflected in the set, and
707      * vice-versa. The set supports element removal, which removes the
708      * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
709      * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
710      * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
711      * <tt>addAll</tt> operations.
712      *
713      * @return a set view of the keys contained in this map.
714      */
715     public Set keySet() {
716         if (mKeySet == null) {
717             mKeySet = new AbstractSet() {
718                 public Iterator iterator() {
719                     return getHashIterator(IdentityMap.KEYS);
720                 }
721                 public int size() {
722                     return mCount;
723                 }
724                 public boolean contains(Object o) {
725                     return containsKey(o);
726                 }
727                 public boolean remove(Object o) {
728                     if (o == null) {
729                         if (SoftHashMap.this.containsKey(null)) {
730                             SoftHashMap.this.remove(null);
731                             return true;
732                         }
733                         else {
734                             return false;
735                         }
736                     }
737                     else {
738                         return SoftHashMap.this.remove(o) != null;
739                     }
740                 }
741                 public void clear() {
742                     SoftHashMap.this.clear();
743                 }
744                 public String toString() {
745                     return IdentityMap.toString(this);
746                 }
747             };
748         }
749         return mKeySet;
750     }
751     
752     /**
753      * Returns a collection view of the values contained in this map. The
754      * collection is backed by the map, so changes to the map are reflected in
755      * the collection, and vice-versa. The collection supports element
756      * removal, which removes the corresponding mapping from this map, via the
757      * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
758      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
759      * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
760      *
761      * @return a collection view of the values contained in this map.
762      */
763     public Collection values() {
764         if (mValues==null) {
765             mValues = new AbstractCollection() {
766                 public Iterator iterator() {
767                     return getHashIterator(IdentityMap.VALUES);
768                 }
769                 public int size() {
770                     return mCount;
771                 }
772                 public boolean contains(Object o) {
773                     return containsValue(o);
774                 }
775                 public void clear() {
776                     SoftHashMap.this.clear();
777                 }
778                 public String toString() {
779                     return IdentityMap.toString(this);
780                 }
781             };
782         }
783         return mValues;
784     }
785
786     /**
787      * Returns a collection view of the mappings contained in this map. Each
788      * element in the returned collection is a <tt>Map.Entry</tt>. The
789      * collection is backed by the map, so changes to the map are reflected in
790      * the collection, and vice-versa. The collection supports element
791      * removal, which removes the corresponding mapping from the map, via the
792      * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
793      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
794      * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
795      *
796      * @return a collection view of the mappings contained in this map.
797      * @see Map.Entry
798      */
799     public Set entrySet() {
800         if (mEntrySet==null) {
801             mEntrySet = new AbstractSet() {
802                 public Iterator iterator() {
803                     return getHashIterator(IdentityMap.ENTRIES);
804                 }
805
806                 public boolean contains(Object o) {
807                     if (!(o instanceof Map.Entry)) {
808                         return false;
809                     }
810                     Map.Entry entry = (Map.Entry)o;
811                     Object key = entry.getKey();
812
813                     Entry tab[] = mTable;
814                     int hash = key == null ? 0 : key.hashCode();
815                     int index = (hash & 0x7FFFFFFF) % tab.length;
816
817                     for (Entry e = tab[index], prev = null; e != null; e = e.mNext) {
818                         Object entryValue = e.getValue();
819                         
820                         if (entryValue == null) {
821                             // Clean up after a cleared Reference.
822 mModCount++;
823                             if (prev != null) {
824                                 prev.mNext = e.mNext;
825                             }
826                             else {
827                                 tab[index] = e.mNext;
828                             }
829                             mCount--;
830                         }
831                         else if (e.mHash == hash && e.equals(entry)) {
832                             return true;
833                         }
834                         else {
835                             prev = e;
836                         }
837                     }
838
839                     return false;
840                 }
841
842                 public boolean remove(Object o) {
843                     if (!(o instanceof Map.Entry)) {
844                         return false;
845                     }
846                     Map.Entry entry = (Map.Entry)o;
847                     Object key = entry.getKey();
848                     Entry tab[] = mTable;
849                     int hash = key == null ? 0 : key.hashCode();
850                     int index = (hash & 0x7FFFFFFF) % tab.length;
851
852                     for (Entry e = tab[index], prev = null; e != null; e = e.mNext) {
853                         Object entryValue = e.getValue();
854                         
855                         if (entryValue == null) {
856                             // Clean up after a cleared Reference.
857 mModCount++;
858                             if (prev != null) {
859                                 prev.mNext = e.mNext;
860                             }
861                             else {
862                                 tab[index] = e.mNext;
863                             }
864                             mCount--;
865                         }
866                         else if (e.mHash == hash && e.equals(entry)) {
867                             mModCount++;
868                             if (prev != null) {
869                                 prev.mNext = e.mNext;
870                             }
871                             else {
872                                 tab[index] = e.mNext;
873                             }
874                             mCount--;
875
876                             e.setValue(null);
877                             return true;
878                         }
879                         else {
880                             prev = e;
881                         }
882                     }
883                     return false;
884                 }
885
886                 public int size() {
887                     return mCount;
888                 }
889                 
890                 public void clear() {
891                     SoftHashMap.this.clear();
892                 }
893
894                 public String toString() {
895                     return IdentityMap.toString(this);
896                 }
897             };
898         }
899         
900         return mEntrySet;
901     }
902     
903     public String toString() {
904         StringBuffer buf = new StringBuffer ();
905         Iterator it = entrySet().iterator();
906         
907         buf.append("{");
908         for (int i = 0; it.hasNext(); i++) {
909             if (i > 0) {
910                 buf.append(", ");
911             }
912             Map.Entry e = (Map.Entry)it.next();
913             buf.append(e.getKey() + "=" + e.getValue());
914         }
915         buf.append("}");
916         return buf.toString();
917     }
918
919     private Iterator getHashIterator(int type) {
920         if (mCount == 0) {
921             return IdentityMap.cEmptyHashIterator;
922         }
923         else {
924             return new HashIterator(type);
925         }
926     }
927
928     /**
929      * HashMap collision list entry.
930      */
931     private static class Entry implements Map.Entry {
932         int mHash;
933         Object mKey;
934         Entry mNext;
935         
936         private Reference mValue;
937
938         Entry(int hash, Object key, Object value, Entry next) {
939             mHash = hash;
940             mKey = key;
941             mValue = new SoftReference(value);
942             mNext = next;
943         }
944         
945         private Entry(int hash, Object key, Reference value, Entry next) {
946             mHash = hash;
947             mKey = key;
948             mValue = value;
949             mNext = next;
950         }
951         
952         protected Object clone() {
953             return new Entry(mHash, mKey, (Reference)mValue,
954                              (mNext==null ? null : (Entry)mNext.clone()));
955         }
956         
957         // Map.Entry Ops
958
959         public Object getKey() {
960             return mKey;
961         }
962         
963         public Object getValue() {
964             return mValue.get();
965         }
966         
967         public Object setValue(Object value) {
968             Object oldValue = getValue();
969             if (value == null) {
970                 mValue.clear();
971             }
972             else {
973                 mValue = new SoftReference(value);
974             }
975             return oldValue;
976         }
977         
978         public boolean equals(Object o) {
979             if (!(o instanceof Map.Entry)) {
980                 return false;
981             }
982             Map.Entry e = (Map.Entry)o;
983
984             Object value = getValue();
985             
986             return (mKey==null ? e.getKey()==null : mKey.equals(e.getKey())) &&
987                 (value==null ? e.getValue()==null : value.equals(e.getValue()));
988         }
989
990         public int hashCode() {
991             Object value = getValue();
992             return mHash ^ (value==null ? 0 : value.hashCode());
993         }
994         
995         public String toString() {
996             return mKey + "=" + getValue();
997         }
998     }
999
1000    private class HashIterator implements Iterator {
1001        private Entry[] mTable = SoftHashMap.this.mTable;
1002        private int mIndex = mTable.length;
1003        private Entry mEntry;
1004        // To ensure that the iterator doesn't return cleared entries, keep a
1005 // hard reference to the value. Its existence will prevent the soft
1006 // value from being cleared.
1007 private Object mEntryValue;
1008        private Entry mLastReturned;
1009        private int mType;
1010        
1011        /**
1012         * The modCount value that the iterator believes that the backing
1013         * List should have. If this expectation is violated, the iterator
1014         * has detected concurrent modification.
1015         */
1016        private int expectedModCount = mModCount;
1017        
1018        HashIterator(int type) {
1019            mType = type;
1020        }
1021        
1022        public boolean hasNext() {
1023            while (mEntry == null ||
1024                   (mEntryValue = mEntry.getValue()) == null) {
1025                if (mEntry != null) {
1026                    // Clean up after a cleared Reference.
1027 remove(mEntry);
1028                    mEntry = mEntry.mNext;
1029                }
1030
1031                if (mEntry == null) {
1032                    if (mIndex <= 0) {
1033                        return false;
1034                    }
1035                    else {
1036                        mEntry = mTable[--mIndex];
1037                    }
1038                }
1039            }
1040
1041            return true;
1042        }
1043        
1044        public Object next() {
1045            if (mModCount != expectedModCount) {
1046                throw new ConcurrentModificationException();
1047            }
1048            
1049            if (!hasNext()) {
1050                throw new NoSuchElementException();
1051            }
1052
1053            mLastReturned = mEntry;
1054            mEntry = mEntry.mNext;
1055
1056            if (mType == IdentityMap.KEYS) {
1057                return mLastReturned.getKey();
1058            }
1059            else if (mType == IdentityMap.VALUES) {
1060                Object value = mLastReturned.getValue();
1061                return (value instanceof Null) ? null : value;
1062            }
1063            else {
1064                return mLastReturned;
1065            }
1066        }
1067        
1068        public void remove() {
1069            if (mLastReturned == null) {
1070                throw new IllegalStateException ();
1071            }
1072            if (mModCount != expectedModCount) {
1073                throw new ConcurrentModificationException();
1074            }
1075            remove(mLastReturned);
1076            mLastReturned = null;
1077        }
1078
1079        private void remove(Entry toRemove) {
1080            Entry[] tab = mTable;
1081            int index = (toRemove.mHash & 0x7FFFFFFF) % tab.length;
1082            
1083            for (Entry e = tab[index], prev = null; e != null; e = e.mNext) {
1084                if (e == toRemove) {
1085                    mModCount++;
1086                    expectedModCount++;
1087                    if (prev == null) {
1088                        tab[index] = e.mNext;
1089                    }
1090                    else {
1091                        prev.mNext = e.mNext;
1092                    }
1093                    mCount--;
1094                    return;
1095                }
1096                else {
1097                    prev = e;
1098                }
1099            }
1100            throw new ConcurrentModificationException();
1101        }
1102    }
1103
1104    /**
1105     * This allows null references to be saved into SoftHashMap and allow
1106     * entries to still be garbage collected.
1107     */
1108    static class Null {
1109        public boolean equals(Object other) {
1110            return other == null || other instanceof Null;
1111        }
1112
1113        public String toString() {
1114            return "null";
1115        }
1116    }
1117}
1118

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags