Source code: com/go/trove/util/SoftHashMap.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 * 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}