KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > java > util > WeakHashMap


1 /*
2  * @(#)WeakHashMap.java 1.32 06/06/13
3  *
4  * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
5  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6  */

7
8 package java.util;
9
10 import java.lang.ref.WeakReference JavaDoc;
11 import java.lang.ref.ReferenceQueue JavaDoc;
12
13
14 /**
15  * A hashtable-based <tt>Map</tt> implementation with <em>weak keys</em>.
16  * An entry in a <tt>WeakHashMap</tt> will automatically be removed when
17  * its key is no longer in ordinary use. More precisely, the presence of a
18  * mapping for a given key will not prevent the key from being discarded by the
19  * garbage collector, that is, made finalizable, finalized, and then reclaimed.
20  * When a key has been discarded its entry is effectively removed from the map,
21  * so this class behaves somewhat differently than other <tt>Map</tt>
22  * implementations.
23  *
24  * <p> Both null values and the null key are supported. This class has
25  * performance characteristics similar to those of the <tt>HashMap</tt>
26  * class, and has the same efficiency parameters of <em>initial capacity</em>
27  * and <em>load factor</em>.
28  *
29  * <p> Like most collection classes, this class is not synchronized. A
30  * synchronized <tt>WeakHashMap</tt> may be constructed using the
31  * <tt>Collections.synchronizedMap</tt> method.
32  *
33  * <p> This class is intended primarily for use with key objects whose
34  * <tt>equals</tt> methods test for object identity using the
35  * <tt>==</tt> operator. Once such a key is discarded it can never be
36  * recreated, so it is impossible to do a lookup of that key in a
37  * <tt>WeakHashMap</tt> at some later time and be surprised that its entry
38  * has been removed. This class will work perfectly well with key objects
39  * whose <tt>equals</tt> methods are not based upon object identity, such
40  * as <tt>String</tt> instances. With such recreatable key objects,
41  * however, the automatic removal of <tt>WeakHashMap</tt> entries whose
42  * keys have been discarded may prove to be confusing.
43  *
44  * <p> The behavior of the <tt>WeakHashMap</tt> class depends in part upon
45  * the actions of the garbage collector, so several familiar (though not
46  * required) <tt>Map</tt> invariants do not hold for this class. Because
47  * the garbage collector may discard keys at any time, a
48  * <tt>WeakHashMap</tt> may behave as though an unknown thread is silently
49  * removing entries. In particular, even if you synchronize on a
50  * <tt>WeakHashMap</tt> instance and invoke none of its mutator methods, it
51  * is possible for the <tt>size</tt> method to return smaller values over
52  * time, for the <tt>isEmpty</tt> method to return <tt>false</tt> and
53  * then <tt>true</tt>, for the <tt>containsKey</tt> method to return
54  * <tt>true</tt> and later <tt>false</tt> for a given key, for the
55  * <tt>get</tt> method to return a value for a given key but later return
56  * <tt>null</tt>, for the <tt>put</tt> method to return
57  * <tt>null</tt> and the <tt>remove</tt> method to return
58  * <tt>false</tt> for a key that previously appeared to be in the map, and
59  * for successive examinations of the key set, the value set, and the entry set
60  * to yield successively smaller numbers of elements.
61  *
62  * <p> Each key object in a <tt>WeakHashMap</tt> is stored indirectly as
63  * the referent of a weak reference. Therefore a key will automatically be
64  * removed only after the weak references to it, both inside and outside of the
65  * map, have been cleared by the garbage collector.
66  *
67  * <p> <strong>Implementation note:</strong> The value objects in a
68  * <tt>WeakHashMap</tt> are held by ordinary strong references. Thus care
69  * should be taken to ensure that value objects do not strongly refer to their
70  * own keys, either directly or indirectly, since that will prevent the keys
71  * from being discarded. Note that a value object may refer indirectly to its
72  * key via the <tt>WeakHashMap</tt> itself; that is, a value object may
73  * strongly refer to some other key object whose associated value object, in
74  * turn, strongly refers to the key of the first value object. One way
75  * to deal with this is to wrap values themselves within
76  * <tt>WeakReferences</tt> before
77  * inserting, as in: <tt>m.put(key, new WeakReference(value))</tt>,
78  * and then unwrapping upon each <tt>get</tt>.
79  *
80  * <p>The iterators returned by all of this class's "collection view methods"
81  * are <i>fail-fast</i>: if the map is structurally modified at any time after
82  * the iterator is created, in any way except through the iterator's own
83  * <tt>remove</tt> or <tt>add</tt> methods, the iterator will throw a
84  * <tt>ConcurrentModificationException</tt>. Thus, in the face of concurrent
85  * modification, the iterator fails quickly and cleanly, rather than risking
86  * arbitrary, non-deterministic behavior at an undetermined time in the
87  * future.
88  *
89  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
90  * as it is, generally speaking, impossible to make any hard guarantees in the
91  * presence of unsynchronized concurrent modification. Fail-fast iterators
92  * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
93  * Therefore, it would be wrong to write a program that depended on this
94  * exception for its correctness: <i>the fail-fast behavior of iterators
95  * should be used only to detect bugs.</i>
96  *
97  * <p>This class is a member of the
98  * <a HREF="{@docRoot}/../guide/collections/index.html">
99  * Java Collections Framework</a>.
100  *
101  * @version 1.30, 02/19/04
102  * @author Doug Lea
103  * @author Josh Bloch
104  * @author Mark Reinhold
105  * @since 1.2
106  * @see java.util.HashMap
107  * @see java.lang.ref.WeakReference
108  */

109 public class WeakHashMap<K,V>
110     extends AbstractMap JavaDoc<K,V>
111     implements Map JavaDoc<K,V> {
112
113     /**
114      * The default initial capacity -- MUST be a power of two.
115      */

116     private static final int DEFAULT_INITIAL_CAPACITY = 16;
117
118     /**
119      * The maximum capacity, used if a higher value is implicitly specified
120      * by either of the constructors with arguments.
121      * MUST be a power of two <= 1<<30.
122      */

123     private static final int MAXIMUM_CAPACITY = 1 << 30;
124
125     /**
126      * The load fast used when none specified in constructor.
127      */

128     private static final float DEFAULT_LOAD_FACTOR = 0.75f;
129
130     /**
131      * The table, resized as necessary. Length MUST Always be a power of two.
132      */

133     private Entry[] table;
134
135     /**
136      * The number of key-value mappings contained in this weak hash map.
137      */

138     private int size;
139
140     /**
141      * The next size value at which to resize (capacity * load factor).
142      */

143     private int threshold;
144
145     /**
146      * The load factor for the hash table.
147      */

148     private final float loadFactor;
149
150     /**
151      * Reference queue for cleared WeakEntries
152      */

153     private final ReferenceQueue JavaDoc<K> queue = new ReferenceQueue JavaDoc<K>();
154
155     /**
156      * The number of times this HashMap has been structurally modified
157      * Structural modifications are those that change the number of mappings in
158      * the HashMap or otherwise modify its internal structure (e.g.,
159      * rehash). This field is used to make iterators on Collection-views of
160      * the HashMap fail-fast. (See ConcurrentModificationException).
161      */

162     private volatile int modCount;
163
164     /**
165      * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial
166      * capacity and the given load factor.
167      *
168      * @param initialCapacity The initial capacity of the <tt>WeakHashMap</tt>
169      * @param loadFactor The load factor of the <tt>WeakHashMap</tt>
170      * @throws IllegalArgumentException If the initial capacity is negative,
171      * or if the load factor is nonpositive.
172      */

173     public WeakHashMap(int initialCapacity, float loadFactor) {
174         if (initialCapacity < 0)
175             throw new IllegalArgumentException JavaDoc("Illegal Initial Capacity: "+
176                                                initialCapacity);
177         if (initialCapacity > MAXIMUM_CAPACITY)
178             initialCapacity = MAXIMUM_CAPACITY;
179
180         if (loadFactor <= 0 || Float.isNaN(loadFactor))
181             throw new IllegalArgumentException JavaDoc("Illegal Load factor: "+
182                                                loadFactor);
183         int capacity = 1;
184         while (capacity < initialCapacity)
185             capacity <<= 1;
186         table = new Entry[capacity];
187         this.loadFactor = loadFactor;
188         threshold = (int)(capacity * loadFactor);
189     }
190
191     /**
192      * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial
193      * capacity and the default load factor, which is <tt>0.75</tt>.
194      *
195      * @param initialCapacity The initial capacity of the <tt>WeakHashMap</tt>
196      * @throws IllegalArgumentException If the initial capacity is negative.
197      */

198     public WeakHashMap(int initialCapacity) {
199         this(initialCapacity, DEFAULT_LOAD_FACTOR);
200     }
201
202     /**
203      * Constructs a new, empty <tt>WeakHashMap</tt> with the default initial
204      * capacity (16) and the default load factor (0.75).
205      */

206     public WeakHashMap() {
207         this.loadFactor = DEFAULT_LOAD_FACTOR;
208         threshold = (int)(DEFAULT_INITIAL_CAPACITY);
209         table = new Entry[DEFAULT_INITIAL_CAPACITY];
210     }
211
212     /**
213      * Constructs a new <tt>WeakHashMap</tt> with the same mappings as the
214      * specified <tt>Map</tt>. The <tt>WeakHashMap</tt> is created with
215      * default load factor, which is <tt>0.75</tt> and an initial capacity
216      * sufficient to hold the mappings in the specified <tt>Map</tt>.
217      *
218      * @param t the map whose mappings are to be placed in this map.
219      * @throws NullPointerException if the specified map is null.
220      * @since 1.3
221      */

222     public WeakHashMap(Map JavaDoc<? extends K, ? extends V> t) {
223         this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1, 16),
224              DEFAULT_LOAD_FACTOR);
225         putAll(t);
226     }
227
228     // internal utilities
229

230     /**
231      * Value representing null keys inside tables.
232      */

233     private static final Object JavaDoc NULL_KEY = new Object JavaDoc();
234
235     /**
236      * Use NULL_KEY for key if it is null.
237      */

238     private static Object JavaDoc maskNull(Object JavaDoc key) {
239         return (key == null ? NULL_KEY : key);
240     }
241
242     /**
243      * Return internal representation of null key back to caller as null
244      */

245     private static <K> K unmaskNull(Object JavaDoc key) {
246         return (K) (key == NULL_KEY ? null : key);
247     }
248
249     /**
250      * Check for equality of non-null reference x and possibly-null y. By
251      * default uses Object.equals.
252      */

253     static boolean eq(Object JavaDoc x, Object JavaDoc y) {
254         return x == y || x.equals(y);
255     }
256
257     /**
258      * Return index for hash code h.
259      */

260     static int indexFor(int h, int length) {
261         return h & (length-1);
262     }
263
264     /**
265      * Expunge stale entries from the table.
266      */

267     private void expungeStaleEntries() {
268     Entry<K,V> e;
269         while ( (e = (Entry<K,V>) queue.poll()) != null) {
270             int h = e.hash;
271             int i = indexFor(h, table.length);
272
273             Entry<K,V> prev = table[i];
274             Entry<K,V> p = prev;
275             while (p != null) {
276                 Entry<K,V> next = p.next;
277                 if (p == e) {
278                     if (prev == e)
279                         table[i] = next;
280                     else
281                         prev.next = next;
282                     e.next = null; // Help GC
283
e.value = null; // " "
284
size--;
285                     break;
286                 }
287                 prev = p;
288                 p = next;
289             }
290         }
291     }
292
293     /**
294      * Return the table after first expunging stale entries
295      */

296     private Entry[] getTable() {
297         expungeStaleEntries();
298         return table;
299     }
300
301     /**
302      * Returns the number of key-value mappings in this map.
303      * This result is a snapshot, and may not reflect unprocessed
304      * entries that will be removed before next attempted access
305      * because they are no longer referenced.
306      */

307     public int size() {
308         if (size == 0)
309             return 0;
310         expungeStaleEntries();
311         return size;
312     }
313
314     /**
315      * Returns <tt>true</tt> if this map contains no key-value mappings.
316      * This result is a snapshot, and may not reflect unprocessed
317      * entries that will be removed before next attempted access
318      * because they are no longer referenced.
319      */

320     public boolean isEmpty() {
321         return size() == 0;
322     }
323
324     /**
325      * Returns the value to which the specified key is mapped in this weak
326      * hash map, or <tt>null</tt> if the map contains no mapping for
327      * this key. A return value of <tt>null</tt> does not <i>necessarily</i>
328      * indicate that the map contains no mapping for the key; it is also
329      * possible that the map explicitly maps the key to <tt>null</tt>. The
330      * <tt>containsKey</tt> method may be used to distinguish these two
331      * cases.
332      *
333      * @param key the key whose associated value is to be returned.
334      * @return the value to which this map maps the specified key, or
335      * <tt>null</tt> if the map contains no mapping for this key.
336      * @see #put(Object, Object)
337      */

338     public V get(Object JavaDoc key) {
339         Object JavaDoc k = maskNull(key);
340         int h = HashMap.hash(k);
341         Entry[] tab = getTable();
342         int index = indexFor(h, tab.length);
343         Entry<K,V> e = tab[index];
344         while (e != null) {
345             if (e.hash == h && eq(k, e.get()))
346                 return e.value;
347             e = e.next;
348         }
349         return null;
350     }
351
352     /**
353      * Returns <tt>true</tt> if this map contains a mapping for the
354      * specified key.
355      *
356      * @param key The key whose presence in this map is to be tested
357      * @return <tt>true</tt> if there is a mapping for <tt>key</tt>;
358      * <tt>false</tt> otherwise
359      */

360     public boolean containsKey(Object JavaDoc key) {
361         return getEntry(key) != null;
362     }
363
364     /**
365      * Returns the entry associated with the specified key in the HashMap.
366      * Returns null if the HashMap contains no mapping for this key.
367      */

368     Entry<K,V> getEntry(Object JavaDoc key) {
369         Object JavaDoc k = maskNull(key);
370         int h = HashMap.hash(k);
371         Entry[] tab = getTable();
372         int index = indexFor(h, tab.length);
373         Entry<K,V> e = tab[index];
374         while (e != null && !(e.hash == h && eq(k, e.get())))
375             e = e.next;
376         return e;
377     }
378
379     /**
380      * Associates the specified value with the specified key in this map.
381      * If the map previously contained a mapping for this key, the old
382      * value is replaced.
383      *
384      * @param key key with which the specified value is to be associated.
385      * @param value value to be associated with the specified key.
386      * @return previous value associated with specified key, or <tt>null</tt>
387      * if there was no mapping for key. A <tt>null</tt> return can
388      * also indicate that the HashMap previously associated
389      * <tt>null</tt> with the specified key.
390      */

391     public V put(K key, V value) {
392         K k = (K) maskNull(key);
393         int h = HashMap.hash(k);
394         Entry[] tab = getTable();
395         int i = indexFor(h, tab.length);
396
397         for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
398             if (h == e.hash && eq(k, e.get())) {
399                 V oldValue = e.value;
400                 if (value != oldValue)
401                     e.value = value;
402                 return oldValue;
403             }
404         }
405
406         modCount++;
407     Entry<K,V> e = tab[i];
408         tab[i] = new Entry<K,V>(k, value, queue, h, e);
409         if (++size >= threshold)
410             resize(tab.length * 2);
411         return null;
412     }
413
414     /**
415      * Rehashes the contents of this map into a new array with a
416      * larger capacity. This method is called automatically when the
417      * number of keys in this map reaches its threshold.
418      *
419      * If current capacity is MAXIMUM_CAPACITY, this method does not
420      * resize the map, but sets threshold to Integer.MAX_VALUE.
421      * This has the effect of preventing future calls.
422      *
423      * @param newCapacity the new capacity, MUST be a power of two;
424      * must be greater than current capacity unless current
425      * capacity is MAXIMUM_CAPACITY (in which case value
426      * is irrelevant).
427      */

428     void resize(int newCapacity) {
429         Entry[] oldTable = getTable();
430         int oldCapacity = oldTable.length;
431         if (oldCapacity == MAXIMUM_CAPACITY) {
432             threshold = Integer.MAX_VALUE;
433             return;
434         }
435
436         Entry[] newTable = new Entry[newCapacity];
437         transfer(oldTable, newTable);
438         table = newTable;
439
440         /*
441          * If ignoring null elements and processing ref queue caused massive
442          * shrinkage, then restore old table. This should be rare, but avoids
443          * unbounded expansion of garbage-filled tables.
444          */

445         if (size >= threshold / 2) {
446             threshold = (int)(newCapacity * loadFactor);
447         } else {
448             expungeStaleEntries();
449             transfer(newTable, oldTable);
450             table = oldTable;
451         }
452     }
453
454     /** Transfer all entries from src to dest tables */
455     private void transfer(Entry[] src, Entry[] dest) {
456         for (int j = 0; j < src.length; ++j) {
457             Entry<K,V> e = src[j];
458             src[j] = null;
459             while (e != null) {
460                 Entry<K,V> next = e.next;
461                 Object JavaDoc key = e.get();
462                 if (key == null) {
463                     e.next = null; // Help GC
464
e.value = null; // " "
465
size--;
466                 } else {
467                     int i = indexFor(e.hash, dest.length);
468                     e.next = dest[i];
469                     dest[i] = e;
470                 }
471                 e = next;
472             }
473         }
474     }
475
476     /**
477      * Copies all of the mappings from the specified map to this map These
478      * mappings will replace any mappings that this map had for any of the
479      * keys currently in the specified map.<p>
480      *
481      * @param m mappings to be stored in this map.
482      * @throws NullPointerException if the specified map is null.
483      */

484     public void putAll(Map JavaDoc<? extends K, ? extends V> m) {
485         int numKeysToBeAdded = m.size();
486         if (numKeysToBeAdded == 0)
487             return;
488
489         /*
490          * Expand the map if the map if the number of mappings to be added
491          * is greater than or equal to threshold. This is conservative; the
492          * obvious condition is (m.size() + size) >= threshold, but this
493          * condition could result in a map with twice the appropriate capacity,
494          * if the keys to be added overlap with the keys already in this map.
495          * By using the conservative calculation, we subject ourself
496          * to at most one extra resize.
497          */

498         if (numKeysToBeAdded > threshold) {
499             int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
500             if (targetCapacity > MAXIMUM_CAPACITY)
501                 targetCapacity = MAXIMUM_CAPACITY;
502             int newCapacity = table.length;
503             while (newCapacity < targetCapacity)
504                 newCapacity <<= 1;
505             if (newCapacity > table.length)
506                 resize(newCapacity);
507         }
508
509         for (Iterator JavaDoc<? extends Map.Entry JavaDoc<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
510             Map.Entry JavaDoc<? extends K, ? extends V> e = i.next();
511             put(e.getKey(), e.getValue());
512         }
513     }
514
515     /**
516      * Removes the mapping for this key from this map if present.
517      *
518      * @param key key whose mapping is to be removed from the map.
519      * @return previous value associated with specified key, or <tt>null</tt>
520      * if there was no mapping for key. A <tt>null</tt> return can
521      * also indicate that the map previously associated <tt>null</tt>
522      * with the specified key.
523      */

524     public V remove(Object JavaDoc key) {
525         Object JavaDoc k = maskNull(key);
526         int h = HashMap.hash(k);
527         Entry[] tab = getTable();
528         int i = indexFor(h, tab.length);
529         Entry<K,V> prev = tab[i];
530         Entry<K,V> e = prev;
531
532         while (e != null) {
533             Entry<K,V> next = e.next;
534             if (h == e.hash && eq(k, e.get())) {
535                 modCount++;
536                 size--;
537                 if (prev == e)
538                     tab[i] = next;
539                 else
540                     prev.next = next;
541                 return e.value;
542             }
543             prev = e;
544             e = next;
545         }
546
547         return null;
548     }
549
550
551
552     /** Special version of remove needed by Entry set */
553     Entry<K,V> removeMapping(Object JavaDoc o) {
554         if (!(o instanceof Map.Entry JavaDoc))
555             return null;
556         Entry[] tab = getTable();
557         Map.Entry JavaDoc entry = (Map.Entry JavaDoc)o;
558         Object JavaDoc k = maskNull(entry.getKey());
559         int h = HashMap.hash(k);
560         int i = indexFor(h, tab.length);
561         Entry<K,V> prev = tab[i];
562         Entry<K,V> e = prev;
563
564         while (e != null) {
565             Entry<K,V> next = e.next;
566             if (h == e.hash && e.equals(entry)) {
567                 modCount++;
568                 size--;
569                 if (prev == e)
570                     tab[i] = next;
571                 else
572                     prev.next = next;
573                 return e;
574             }
575             prev = e;
576             e = next;
577         }
578
579         return null;
580     }
581
582     /**
583      * Removes all mappings from this map.
584      */

585     public void clear() {
586         // clear out ref queue. We don't need to expunge entries
587
// since table is getting cleared.
588
while (queue.poll() != null)
589             ;
590
591         modCount++;
592         Entry[] tab = table;
593         for (int i = 0; i < tab.length; ++i)
594             tab[i] = null;
595         size = 0;
596
597         // Allocation of array may have caused GC, which may have caused
598
// additional entries to go stale. Removing these entries from the
599
// reference queue will make them eligible for reclamation.
600
while (queue.poll() != null)
601             ;
602    }
603
604     /**
605      * Returns <tt>true</tt> if this map maps one or more keys to the
606      * specified value.
607      *
608      * @param value value whose presence in this map is to be tested.
609      * @return <tt>true</tt> if this map maps one or more keys to the
610      * specified value.
611      */

612     public boolean containsValue(Object JavaDoc value) {
613     if (value==null)
614             return containsNullValue();
615
616     Entry[] tab = getTable();
617         for (int i = tab.length ; i-- > 0 ;)
618             for (Entry e = tab[i] ; e != null ; e = e.next)
619                 if (value.equals(e.value))
620                     return true;
621     return false;
622     }
623
624     /**
625      * Special-case code for containsValue with null argument
626      */

627     private boolean containsNullValue() {
628     Entry[] tab = getTable();
629         for (int i = tab.length ; i-- > 0 ;)
630             for (Entry e = tab[i] ; e != null ; e = e.next)
631                 if (e.value==null)
632                     return true;
633     return false;
634     }
635
636     /**
637      * The entries in this hash table extend WeakReference, using its main ref
638      * field as the key.
639      */

640     private static class Entry<K,V> extends WeakReference JavaDoc<K> implements Map.Entry JavaDoc<K,V> {
641         private V value;
642         private final int hash;
643         private Entry<K,V> next;
644
645         /**
646          * Create new entry.
647          */

648         Entry(K key, V value,
649           ReferenceQueue JavaDoc<K> queue,
650               int hash, Entry<K,V> next) {
651             super(key, queue);
652             this.value = value;
653             this.hash = hash;
654             this.next = next;
655         }
656
657         public K getKey() {
658             return WeakHashMap.<K>unmaskNull(get());
659         }
660
661         public V getValue() {
662             return value;
663         }
664
665         public V setValue(V newValue) {
666         V oldValue = value;
667             value = newValue;
668             return oldValue;
669         }
670
671         public boolean equals(Object JavaDoc o) {
672             if (!(o instanceof Map.Entry JavaDoc))
673                 return false;
674             Map.Entry JavaDoc e = (Map.Entry JavaDoc)o;
675             Object JavaDoc k1 = getKey();
676             Object JavaDoc k2 = e.getKey();
677             if (k1 == k2 || (k1 != null && k1.equals(k2))) {
678                 Object JavaDoc v1 = getValue();
679                 Object JavaDoc v2 = e.getValue();
680                 if (v1 == v2 || (v1 != null && v1.equals(v2)))
681                     return true;
682             }
683             return false;
684         }
685
686         public int hashCode() {
687             Object JavaDoc k = getKey();
688             Object JavaDoc v = getValue();
689             return ((k==null ? 0 : k.hashCode()) ^
690                      (v==null ? 0 : v.hashCode()));
691         }
692
693         public String JavaDoc toString() {
694             return getKey() + "=" + getValue();
695         }
696     }
697
698     private abstract class HashIterator<T> implements Iterator JavaDoc<T> {
699         int index;
700         Entry<K,V> entry = null;
701         Entry<K,V> lastReturned = null;
702         int expectedModCount = modCount;
703
704         /**
705          * Strong reference needed to avoid disappearance of key
706          * between hasNext and next
707          */

708         Object JavaDoc nextKey = null;
709
710         /**
711          * Strong reference needed to avoid disappearance of key
712          * between nextEntry() and any use of the entry
713          */

714     Object JavaDoc currentKey = null;
715
716         HashIterator() {
717             index = (size() != 0 ? table.length : 0);
718         }
719
720         public boolean hasNext() {
721             Entry[] t = table;
722
723             while (nextKey == null) {
724                 Entry<K,V> e = entry;
725                 int i = index;
726                 while (e == null && i > 0)
727                     e = t[--i];
728                 entry = e;
729                 index = i;
730                 if (e == null) {
731                     currentKey = null;
732                     return false;
733                 }
734                 nextKey = e.get(); // hold on to key in strong ref
735
if (nextKey == null)
736                     entry = entry.next;
737             }
738             return true;
739         }
740
741         /** The common parts of next() across different types of iterators */
742         protected Entry<K,V> nextEntry() {
743             if (modCount != expectedModCount)
744                 throw new ConcurrentModificationException JavaDoc();
745             if (nextKey == null && !hasNext())
746                 throw new NoSuchElementException JavaDoc();
747
748             lastReturned = entry;
749             entry = entry.next;
750             currentKey = nextKey;
751             nextKey = null;
752             return lastReturned;
753         }
754
755         public void remove() {
756             if (lastReturned == null)
757                 throw new IllegalStateException JavaDoc();
758             if (modCount != expectedModCount)
759                 throw new ConcurrentModificationException JavaDoc();
760
761             WeakHashMap.this.remove(currentKey);
762             expectedModCount = modCount;
763             lastReturned = null;
764             currentKey = null;
765         }
766
767     }
768
769     private class ValueIterator extends HashIterator<V> {
770         public V next() {
771             return nextEntry().value;
772         }
773     }
774
775     private class KeyIterator extends HashIterator<K> {
776         public K next() {
777             return nextEntry().getKey();
778         }
779     }
780
781     private class EntryIterator extends HashIterator<Map.Entry JavaDoc<K,V>> {
782         public Map.Entry JavaDoc<K,V> next() {
783             return nextEntry();
784         }
785     }
786
787     // Views
788

789     private transient Set JavaDoc<Map.Entry JavaDoc<K,V>> entrySet = null;
790
791     /**
792      * Returns a set view of the keys contained in this map. The set is
793      * backed by the map, so changes to the map are reflected in the set, and
794      * vice-versa. The set supports element removal, which removes the
795      * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
796      * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
797      * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
798      * <tt>addAll</tt> operations.
799      *
800      * @return a set view of the keys contained in this map.
801      */

802     public Set JavaDoc<K> keySet() {
803         Set JavaDoc<K> ks = keySet;
804         return (ks != null ? ks : (keySet = new KeySet()));
805     }
806
807     private class KeySet extends AbstractSet JavaDoc<K> {
808         public Iterator JavaDoc<K> iterator() {
809             return new KeyIterator();
810         }
811
812         public int size() {
813             return WeakHashMap.this.size();
814         }
815
816         public boolean contains(Object JavaDoc o) {
817             return containsKey(o);
818         }
819
820         public boolean remove(Object JavaDoc o) {
821             if (containsKey(o)) {
822                 WeakHashMap.this.remove(o);
823                 return true;
824             }
825             else
826                 return false;
827         }
828
829         public void clear() {
830             WeakHashMap.this.clear();
831         }
832
833         public Object JavaDoc[] toArray() {
834             Collection JavaDoc<K> c = new ArrayList JavaDoc<K>(size());
835             for (Iterator JavaDoc<K> i = iterator(); i.hasNext(); )
836                 c.add(i.next());
837             return c.toArray();
838         }
839
840         public <T> T[] toArray(T[] a) {
841             Collection JavaDoc<K> c = new ArrayList JavaDoc<K>(size());
842             for (Iterator JavaDoc<K> i = iterator(); i.hasNext(); )
843                 c.add(i.next());
844             return c.toArray(a);
845         }
846     }
847
848     /**
849      * Returns a collection view of the values contained in this map. The
850      * collection is backed by the map, so changes to the map are reflected in
851      * the collection, and vice-versa. The collection supports element
852      * removal, which removes the corresponding mapping from this map, via the
853      * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
854      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
855      * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
856      *
857      * @return a collection view of the values contained in this map.
858      */

859     public Collection JavaDoc<V> values() {
860         Collection JavaDoc<V> vs = values;
861         return (vs != null ? vs : (values = new Values()));
862     }
863
864     private class Values extends AbstractCollection JavaDoc<V> {
865         public Iterator JavaDoc<V> iterator() {
866             return new ValueIterator();
867         }
868
869         public int size() {
870             return WeakHashMap.this.size();
871         }
872
873         public boolean contains(Object JavaDoc o) {
874             return containsValue(o);
875         }
876
877         public void clear() {
878             WeakHashMap.this.clear();
879         }
880
881         public Object JavaDoc[] toArray() {
882             Collection JavaDoc<V> c = new ArrayList JavaDoc<V>(size());
883             for (Iterator JavaDoc<V> i = iterator(); i.hasNext(); )
884                 c.add(i.next());
885             return c.toArray();
886         }
887
888         public <T> T[] toArray(T[] a) {
889             Collection JavaDoc<V> c = new ArrayList JavaDoc<V>(size());
890             for (Iterator JavaDoc<V> i = iterator(); i.hasNext(); )
891                 c.add(i.next());
892             return c.toArray(a);
893         }
894     }
895
896     /**
897      * Returns a collection view of the mappings contained in this map. Each
898      * element in the returned collection is a <tt>Map.Entry</tt>. The
899      * collection is backed by the map, so changes to the map are reflected in
900      * the collection, and vice-versa. The collection supports element
901      * removal, which removes the corresponding mapping from the map, via the
902      * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
903      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
904      * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
905      *
906      * @return a collection view of the mappings contained in this map.
907      * @see Map.Entry
908      */

909     public Set JavaDoc<Map.Entry JavaDoc<K,V>> entrySet() {
910         Set JavaDoc<Map.Entry JavaDoc<K,V>> es = entrySet;
911         return (es != null ? es : (entrySet = new EntrySet()));
912     }
913
914     private class EntrySet extends AbstractSet JavaDoc<Map.Entry JavaDoc<K,V>> {
915         public Iterator JavaDoc<Map.Entry JavaDoc<K,V>> iterator() {
916             return new EntryIterator();
917         }
918
919         public boolean contains(Object JavaDoc o) {
920             if (!(o instanceof Map.Entry JavaDoc))
921                 return false;
922             Map.Entry JavaDoc e = (Map.Entry JavaDoc)o;
923             Object JavaDoc k = e.getKey();
924             Entry candidate = getEntry(e.getKey());
925             return candidate != null && candidate.equals(e);
926         }
927
928         public boolean remove(Object JavaDoc o) {
929             return removeMapping(o) != null;
930         }
931
932         public int size() {
933             return WeakHashMap.this.size();
934         }
935
936         public void clear() {
937             WeakHashMap.this.clear();
938         }
939
940         public Object JavaDoc[] toArray() {
941             Collection JavaDoc<Map.Entry JavaDoc<K,V>> c = new ArrayList JavaDoc<Map.Entry JavaDoc<K,V>>(size());
942             for (Iterator JavaDoc<Map.Entry JavaDoc<K,V>> i = iterator(); i.hasNext(); )
943                 c.add(new AbstractMap.SimpleEntry JavaDoc<K,V>(i.next()));
944             return c.toArray();
945         }
946
947         public <T> T[] toArray(T[] a) {
948             Collection JavaDoc<Map.Entry JavaDoc<K,V>> c = new ArrayList JavaDoc<Map.Entry JavaDoc<K,V>>(size());
949             for (Iterator JavaDoc<Map.Entry JavaDoc<K,V>> i = iterator(); i.hasNext(); )
950                 c.add(new AbstractMap.SimpleEntry JavaDoc<K,V>(i.next()));
951             return c.toArray(a);
952         }
953     }
954 }
955
Popular Tags