001: /*
002: * @(#)WeakHashMap.java 1.19 06/10/10
003: *
004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: *
026: */
027:
028: package java.util;
029:
030: import java.lang.ref.WeakReference;
031: import java.lang.ref.ReferenceQueue;
032:
033: /**
034: * A hashtable-based <tt>Map</tt> implementation with <em>weak keys</em>.
035: * An entry in a <tt>WeakHashMap</tt> will automatically be removed when
036: * its key is no longer in ordinary use. More precisely, the presence of a
037: * mapping for a given key will not prevent the key from being discarded by the
038: * garbage collector, that is, made finalizable, finalized, and then reclaimed.
039: * When a key has been discarded its entry is effectively removed from the map,
040: * so this class behaves somewhat differently than other <tt>Map</tt>
041: * implementations.
042: *
043: * <p> Both null values and the null key are supported. This class has
044: * performance characteristics similar to those of the <tt>HashMap</tt>
045: * class, and has the same efficiency parameters of <em>initial capacity</em>
046: * and <em>load factor</em>.
047: *
048: * <p> Like most collection classes, this class is not synchronized. A
049: * synchronized <tt>WeakHashMap</tt> may be constructed using the
050: * <tt>Collections.synchronizedMap</tt> method.
051: *
052: * <p> This class is intended primarily for use with key objects whose
053: * <tt>equals</tt> methods test for object identity using the
054: * <tt>==</tt> operator. Once such a key is discarded it can never be
055: * recreated, so it is impossible to do a lookup of that key in a
056: * <tt>WeakHashMap</tt> at some later time and be surprised that its entry
057: * has been removed. This class will work perfectly well with key objects
058: * whose <tt>equals</tt> methods are not based upon object identity, such
059: * as <tt>String</tt> instances. With such recreatable key objects,
060: * however, the automatic removal of <tt>WeakHashMap</tt> entries whose
061: * keys have been discarded may prove to be confusing.
062: *
063: * <p> The behavior of the <tt>WeakHashMap</tt> class depends in part upon
064: * the actions of the garbage collector, so several familiar (though not
065: * required) <tt>Map</tt> invariants do not hold for this class. Because
066: * the garbage collector may discard keys at any time, a
067: * <tt>WeakHashMap</tt> may behave as though an unknown thread is silently
068: * removing entries. In particular, even if you synchronize on a
069: * <tt>WeakHashMap</tt> instance and invoke none of its mutator methods, it
070: * is possible for the <tt>size</tt> method to return smaller values over
071: * time, for the <tt>isEmpty</tt> method to return <tt>false</tt> and
072: * then <tt>true</tt>, for the <tt>containsKey</tt> method to return
073: * <tt>true</tt> and later <tt>false</tt> for a given key, for the
074: * <tt>get</tt> method to return a value for a given key but later return
075: * <tt>null</tt>, for the <tt>put</tt> method to return
076: * <tt>null</tt> and the <tt>remove</tt> method to return
077: * <tt>false</tt> for a key that previously appeared to be in the map, and
078: * for successive examinations of the key set, the value set, and the entry set
079: * to yield successively smaller numbers of elements.
080: *
081: * <p> Each key object in a <tt>WeakHashMap</tt> is stored indirectly as
082: * the referent of a weak reference. Therefore a key will automatically be
083: * removed only after the weak references to it, both inside and outside of the
084: * map, have been cleared by the garbage collector.
085: *
086: * <p> <strong>Implementation note:</strong> The value objects in a
087: * <tt>WeakHashMap</tt> are held by ordinary strong references. Thus care
088: * should be taken to ensure that value objects do not strongly refer to their
089: * own keys, either directly or indirectly, since that will prevent the keys
090: * from being discarded. Note that a value object may refer indirectly to its
091: * key via the <tt>WeakHashMap</tt> itself; that is, a value object may
092: * strongly refer to some other key object whose associated value object, in
093: * turn, strongly refers to the key of the first value object. One way
094: * to deal with this is to wrap values themselves within
095: * <tt>WeakReferences</tt> before
096: * inserting, as in: <tt>m.put(key, new WeakReference(value))</tt>,
097: * and then unwrapping upon each <tt>get</tt>.
098: *
099: * <p>The iterators returned by all of this class's "collection view methods"
100: * are <i>fail-fast</i>: if the map is structurally modified at any time after
101: * the iterator is created, in any way except through the iterator's own
102: * <tt>remove</tt> or <tt>add</tt> methods, the iterator will throw a
103: * <tt>ConcurrentModificationException</tt>. Thus, in the face of concurrent
104: * modification, the iterator fails quickly and cleanly, rather than risking
105: * arbitrary, non-deterministic behavior at an undetermined time in the
106: * future.
107: *
108: * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
109: * as it is, generally speaking, impossible to make any hard guarantees in the
110: * presence of unsynchronized concurrent modification. Fail-fast iterators
111: * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
112: * Therefore, it would be wrong to write a program that depended on this
113: * exception for its correctness: <i>the fail-fast behavior of iterators
114: * should be used only to detect bugs.</i>
115: *
116: * <p>This class is a member of the
117: * <a href="{@docRoot}/../guide/collections/index.html">
118: * Java Collections Framework</a>.
119: *
120: * @version 1.19, 10/10/06
121: * @author Doug Lea
122: * @author Josh Bloch
123: * @author Mark Reinhold
124: * @since 1.2
125: * @see java.util.HashMap
126: * @see java.lang.ref.WeakReference
127: */
128: public class WeakHashMap extends AbstractMap implements Map {
129:
130: /**
131: * The default initial capacity -- MUST be a power of two.
132: */
133: private static final int DEFAULT_INITIAL_CAPACITY = 16;
134:
135: /**
136: * The maximum capacity, used if a higher value is implicitly specified
137: * by either of the constructors with arguments.
138: * MUST be a power of two <= 1<<30.
139: */
140: private static final int MAXIMUM_CAPACITY = 1 << 30;
141:
142: /**
143: * The load fast used when none specified in constructor.
144: */
145: private static final float DEFAULT_LOAD_FACTOR = 0.75f;
146:
147: /**
148: * The table, resized as necessary. Length MUST Always be a power of two.
149: */
150: private Entry[] table;
151:
152: /**
153: * The number of key-value mappings contained in this weak hash map.
154: */
155: private int size;
156:
157: /**
158: * The next size value at which to resize (capacity * load factor).
159: */
160: private int threshold;
161:
162: /**
163: * The load factor for the hash table.
164: */
165: private final float loadFactor;
166:
167: /**
168: * Reference queue for cleared WeakEntries
169: */
170: private final ReferenceQueue queue = new ReferenceQueue();
171:
172: /**
173: * The number of times this HashMap has been structurally modified
174: * Structural modifications are those that change the number of mappings in
175: * the HashMap or otherwise modify its internal structure (e.g.,
176: * rehash). This field is used to make iterators on Collection-views of
177: * the HashMap fail-fast. (See ConcurrentModificationException).
178: */
179: private volatile int modCount;
180:
181: /**
182: * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial
183: * capacity and the given load factor.
184: *
185: * @param initialCapacity The initial capacity of the <tt>WeakHashMap</tt>
186: * @param loadFactor The load factor of the <tt>WeakHashMap</tt>
187: * @throws IllegalArgumentException If the initial capacity is negative,
188: * or if the load factor is nonpositive.
189: */
190: public WeakHashMap(int initialCapacity, float loadFactor) {
191: if (initialCapacity < 0)
192: throw new IllegalArgumentException(
193: "Illegal Initial Capacity: " + initialCapacity);
194: if (initialCapacity > MAXIMUM_CAPACITY)
195: initialCapacity = MAXIMUM_CAPACITY;
196:
197: if (loadFactor <= 0 || Float.isNaN(loadFactor))
198: throw new IllegalArgumentException("Illegal Load factor: "
199: + loadFactor);
200: int capacity = 1;
201: while (capacity < initialCapacity)
202: capacity <<= 1;
203: table = new Entry[capacity];
204: this .loadFactor = loadFactor;
205: threshold = (int) (capacity * loadFactor);
206: }
207:
208: /**
209: * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial
210: * capacity and the default load factor, which is <tt>0.75</tt>.
211: *
212: * @param initialCapacity The initial capacity of the <tt>WeakHashMap</tt>
213: * @throws IllegalArgumentException If the initial capacity is negative.
214: */
215: public WeakHashMap(int initialCapacity) {
216: this (initialCapacity, DEFAULT_LOAD_FACTOR);
217: }
218:
219: /**
220: * Constructs a new, empty <tt>WeakHashMap</tt> with the default initial
221: * capacity (16) and the default load factor (0.75).
222: */
223: public WeakHashMap() {
224: this .loadFactor = DEFAULT_LOAD_FACTOR;
225: threshold = (int) (DEFAULT_INITIAL_CAPACITY);
226: table = new Entry[DEFAULT_INITIAL_CAPACITY];
227: }
228:
229: /**
230: * Constructs a new <tt>WeakHashMap</tt> with the same mappings as the
231: * specified <tt>Map</tt>. The <tt>WeakHashMap</tt> is created with
232: * default load factor, which is <tt>0.75</tt> and an initial capacity
233: * sufficient to hold the mappings in the specified <tt>Map</tt>.
234: *
235: * @param t the map whose mappings are to be placed in this map.
236: * @throws NullPointerException if the specified map is null.
237: * @since 1.3
238: */
239: public WeakHashMap(Map t) {
240: this (Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1, 16),
241: DEFAULT_LOAD_FACTOR);
242: putAll(t);
243: }
244:
245: // internal utilities
246:
247: /**
248: * Value representing null keys inside tables.
249: */
250: private static final Object NULL_KEY = new Object();
251:
252: /**
253: * Use NULL_KEY for key if it is null.
254: */
255: private static Object maskNull(Object key) {
256: return (key == null ? NULL_KEY : key);
257: }
258:
259: /**
260: * Return internal representation of null key back to caller as null
261: */
262: private static Object unmaskNull(Object key) {
263: return (key == NULL_KEY ? null : key);
264: }
265:
266: /**
267: * Check for equality of non-null reference x and possibly-null y. By
268: * default uses Object.equals.
269: */
270: static boolean eq(Object x, Object y) {
271: return x == y || x.equals(y);
272: }
273:
274: /**
275: * Return index for hash code h.
276: */
277: static int indexFor(int h, int length) {
278: return h & (length - 1);
279: }
280:
281: /**
282: * Expunge stale entries from the table.
283: */
284: private void expungeStaleEntries() {
285: Object r;
286: while ((r = queue.poll()) != null) {
287: Entry e = (Entry) r;
288: int h = e.hash;
289: int i = indexFor(h, table.length);
290:
291: Entry prev = table[i];
292: Entry p = prev;
293: while (p != null) {
294: Entry next = p.next;
295: if (p == e) {
296: if (prev == e)
297: table[i] = next;
298: else
299: prev.next = next;
300: e.next = null; // Help GC
301: e.value = null; // " "
302: size--;
303: break;
304: }
305: prev = p;
306: p = next;
307: }
308: }
309: }
310:
311: /**
312: * Return the table after first expunging stale entries
313: */
314: private Entry[] getTable() {
315: expungeStaleEntries();
316: return table;
317: }
318:
319: /**
320: * Returns the number of key-value mappings in this map.
321: * This result is a snapshot, and may not reflect unprocessed
322: * entries that will be removed before next attempted access
323: * because they are no longer referenced.
324: */
325: public int size() {
326: if (size == 0)
327: return 0;
328: expungeStaleEntries();
329: return size;
330: }
331:
332: /**
333: * Returns <tt>true</tt> if this map contains no key-value mappings.
334: * This result is a snapshot, and may not reflect unprocessed
335: * entries that will be removed before next attempted access
336: * because they are no longer referenced.
337: */
338: public boolean isEmpty() {
339: return size() == 0;
340: }
341:
342: /**
343: * Returns the value to which the specified key is mapped in this weak
344: * hash map, or <tt>null</tt> if the map contains no mapping for
345: * this key. A return value of <tt>null</tt> does not <i>necessarily</i>
346: * indicate that the map contains no mapping for the key; it is also
347: * possible that the map explicitly maps the key to <tt>null</tt>. The
348: * <tt>containsKey</tt> method may be used to distinguish these two
349: * cases.
350: *
351: * @param key the key whose associated value is to be returned.
352: * @return the value to which this map maps the specified key, or
353: * <tt>null</tt> if the map contains no mapping for this key.
354: * @see #put(Object, Object)
355: */
356: public Object get(Object key) {
357: Object k = maskNull(key);
358: int h = HashMap.hash(k);
359: Entry[] tab = getTable();
360: int index = indexFor(h, tab.length);
361: Entry e = tab[index];
362: while (e != null) {
363: if (e.hash == h && eq(k, e.get()))
364: return e.value;
365: e = e.next;
366: }
367: return null;
368: }
369:
370: /**
371: * Returns <tt>true</tt> if this map contains a mapping for the
372: * specified key.
373: *
374: * @param key The key whose presence in this map is to be tested
375: * @return <tt>true</tt> if there is a mapping for <tt>key</tt>;
376: * <tt>false</tt> otherwise
377: */
378: public boolean containsKey(Object key) {
379: return getEntry(key) != null;
380: }
381:
382: /**
383: * Returns the entry associated with the specified key in the HashMap.
384: * Returns null if the HashMap contains no mapping for this key.
385: */
386: Entry getEntry(Object key) {
387: Object k = maskNull(key);
388: int h = HashMap.hash(k);
389: Entry[] tab = getTable();
390: int index = indexFor(h, tab.length);
391: Entry e = tab[index];
392: while (e != null && !(e.hash == h && eq(k, e.get())))
393: e = e.next;
394: return e;
395: }
396:
397: /**
398: * Associates the specified value with the specified key in this map.
399: * If the map previously contained a mapping for this key, the old
400: * value is replaced.
401: *
402: * @param key key with which the specified value is to be associated.
403: * @param value value to be associated with the specified key.
404: * @return previous value associated with specified key, or <tt>null</tt>
405: * if there was no mapping for key. A <tt>null</tt> return can
406: * also indicate that the HashMap previously associated
407: * <tt>null</tt> with the specified key.
408: */
409: public Object put(Object key, Object value) {
410: Object k = maskNull(key);
411: int h = HashMap.hash(k);
412: Entry[] tab = getTable();
413: int i = indexFor(h, tab.length);
414:
415: for (Entry e = tab[i]; e != null; e = e.next) {
416: if (h == e.hash && eq(k, e.get())) {
417: Object oldValue = e.value;
418: if (value != oldValue)
419: e.value = value;
420: return oldValue;
421: }
422: }
423:
424: modCount++;
425: tab[i] = new Entry(k, value, queue, h, tab[i]);
426: if (++size >= threshold)
427: resize(tab.length * 2);
428: return null;
429: }
430:
431: /**
432: * Rehashes the contents of this map into a new array with a
433: * larger capacity. This method is called automatically when the
434: * number of keys in this map reaches its threshold.
435: *
436: * If current capacity is MAXIMUM_CAPACITY, this method does not
437: * resize the map, but but sets threshold to Integer.MAX_VALUE.
438: * This has the effect of preventing future calls.
439: *
440: * @param newCapacity the new capacity, MUST be a power of two;
441: * must be greater than current capacity unless current
442: * capacity is MAXIMUM_CAPACITY (in which case value
443: * is irrelevant).
444: */
445: void resize(int newCapacity) {
446: Entry[] oldTable = getTable();
447: int oldCapacity = oldTable.length;
448: if (oldCapacity == MAXIMUM_CAPACITY) {
449: threshold = Integer.MAX_VALUE;
450: return;
451: }
452:
453: Entry[] newTable = new Entry[newCapacity];
454: transfer(oldTable, newTable);
455: table = newTable;
456:
457: /*
458: * If ignoring null elements and processing ref queue caused massive
459: * shrinkage, then restore old table. This should be rare, but avoids
460: * unbounded expansion of garbage-filled tables.
461: */
462: if (size >= threshold / 2) {
463: threshold = (int) (newCapacity * loadFactor);
464: } else {
465: expungeStaleEntries();
466: transfer(newTable, oldTable);
467: table = oldTable;
468: }
469: }
470:
471: /** Transfer all entries from src to dest tables */
472: private void transfer(Entry[] src, Entry[] dest) {
473: for (int j = 0; j < src.length; ++j) {
474: Entry e = src[j];
475: src[j] = null;
476: while (e != null) {
477: Entry next = e.next;
478: Object key = e.get();
479: if (key == null) {
480: e.next = null; // Help GC
481: e.value = null; // " "
482: size--;
483: } else {
484: int i = indexFor(e.hash, dest.length);
485: e.next = dest[i];
486: dest[i] = e;
487: }
488: e = next;
489: }
490: }
491: }
492:
493: /**
494: * Copies all of the mappings from the specified map to this map These
495: * mappings will replace any mappings that this map had for any of the
496: * keys currently in the specified map.<p>
497: *
498: * @param m mappings to be stored in this map.
499: * @throws NullPointerException if the specified map is null.
500: */
501: public void putAll(Map m) {
502: int numKeysToBeAdded = m.size();
503: if (numKeysToBeAdded == 0)
504: return;
505:
506: /*
507: * Expand the map if the map if the number of mappings to be added
508: * is greater than or equal to threshold. This is conservative; the
509: * obvious condition is (m.size() + size) >= threshold, but this
510: * condition could result in a map with twice the appropriate capacity,
511: * if the keys to be added overlap with the keys already in this map.
512: * By using the conservative calculation, we subject ourself
513: * to at most one extra resize.
514: */
515: if (numKeysToBeAdded > threshold) {
516: int targetCapacity = (int) (numKeysToBeAdded / loadFactor + 1);
517: if (targetCapacity > MAXIMUM_CAPACITY)
518: targetCapacity = MAXIMUM_CAPACITY;
519: int newCapacity = table.length;
520: while (newCapacity < targetCapacity)
521: newCapacity <<= 1;
522: if (newCapacity > table.length)
523: resize(newCapacity);
524: }
525:
526: for (Iterator i = m.entrySet().iterator(); i.hasNext();) {
527: Map.Entry e = (Map.Entry) i.next();
528: put(e.getKey(), e.getValue());
529: }
530: }
531:
532: /**
533: * Removes the mapping for this key from this map if present.
534: *
535: * @param key key whose mapping is to be removed from the map.
536: * @return previous value associated with specified key, or <tt>null</tt>
537: * if there was no mapping for key. A <tt>null</tt> return can
538: * also indicate that the map previously associated <tt>null</tt>
539: * with the specified key.
540: */
541: public Object remove(Object key) {
542: Object k = maskNull(key);
543: int h = HashMap.hash(k);
544: Entry[] tab = getTable();
545: int i = indexFor(h, tab.length);
546: Entry prev = tab[i];
547: Entry e = prev;
548:
549: while (e != null) {
550: Entry next = e.next;
551: if (h == e.hash && eq(k, e.get())) {
552: modCount++;
553: size--;
554: if (prev == e)
555: tab[i] = next;
556: else
557: prev.next = next;
558: return e.value;
559: }
560: prev = e;
561: e = next;
562: }
563:
564: return null;
565: }
566:
567: /** Special version of remove needed by Entry set */
568: Entry removeMapping(Object o) {
569: if (!(o instanceof Map.Entry))
570: return null;
571: Entry[] tab = getTable();
572: Map.Entry entry = (Map.Entry) o;
573: Object k = maskNull(entry.getKey());
574: int h = HashMap.hash(k);
575: int i = indexFor(h, tab.length);
576: Entry prev = tab[i];
577: Entry e = prev;
578:
579: while (e != null) {
580: Entry next = e.next;
581: if (h == e.hash && e.equals(entry)) {
582: modCount++;
583: size--;
584: if (prev == e)
585: tab[i] = next;
586: else
587: prev.next = next;
588: return e;
589: }
590: prev = e;
591: e = next;
592: }
593:
594: return null;
595: }
596:
597: /**
598: * Removes all mappings from this map.
599: */
600: public void clear() {
601: // clear out ref queue. We don't need to expunge entries
602: // since table is getting cleared.
603: while (queue.poll() != null)
604: ;
605:
606: modCount++;
607: Entry tab[] = table;
608: for (int i = 0; i < tab.length; ++i)
609: tab[i] = null;
610: size = 0;
611:
612: // Allocation of array may have caused GC, which may have caused
613: // additional entries to go stale. Removing these entries from the
614: // reference queue will make them eligible for reclamation.
615: while (queue.poll() != null)
616: ;
617: }
618:
619: /**
620: * Returns <tt>true</tt> if this map maps one or more keys to the
621: * specified value.
622: *
623: * @param value value whose presence in this map is to be tested.
624: * @return <tt>true</tt> if this map maps one or more keys to the
625: * specified value.
626: */
627: public boolean containsValue(Object value) {
628: if (value == null)
629: return containsNullValue();
630:
631: Entry tab[] = getTable();
632: for (int i = tab.length; i-- > 0;)
633: for (Entry e = tab[i]; e != null; e = e.next)
634: if (value.equals(e.value))
635: return true;
636: return false;
637: }
638:
639: /**
640: * Special-case code for containsValue with null argument
641: */
642: private boolean containsNullValue() {
643: Entry tab[] = getTable();
644: for (int i = tab.length; i-- > 0;)
645: for (Entry e = tab[i]; e != null; e = e.next)
646: if (e.value == null)
647: return true;
648: return false;
649: }
650:
651: /**
652: * The entries in this hash table extend WeakReference, using its main ref
653: * field as the key.
654: */
655: private static class Entry extends WeakReference implements
656: Map.Entry {
657: private Object value;
658: private final int hash;
659: private Entry next;
660:
661: /**
662: * Create new entry.
663: */
664: Entry(Object key, Object value, ReferenceQueue queue, int hash,
665: Entry next) {
666: super (key, queue);
667: this .value = value;
668: this .hash = hash;
669: this .next = next;
670: }
671:
672: public Object getKey() {
673: return unmaskNull(get());
674: }
675:
676: public Object getValue() {
677: return value;
678: }
679:
680: public Object setValue(Object newValue) {
681: Object oldValue = value;
682: value = newValue;
683: return oldValue;
684: }
685:
686: public boolean equals(Object o) {
687: if (!(o instanceof Map.Entry))
688: return false;
689: Map.Entry e = (Map.Entry) o;
690: Object k1 = getKey();
691: Object k2 = e.getKey();
692: if (k1 == k2 || (k1 != null && k1.equals(k2))) {
693: Object v1 = getValue();
694: Object v2 = e.getValue();
695: if (v1 == v2 || (v1 != null && v1.equals(v2)))
696: return true;
697: }
698: return false;
699: }
700:
701: public int hashCode() {
702: Object k = getKey();
703: Object v = getValue();
704: return ((k == null ? 0 : k.hashCode()) ^ (v == null ? 0 : v
705: .hashCode()));
706: }
707:
708: public String toString() {
709: return getKey() + "=" + getValue();
710: }
711: }
712:
713: private abstract class HashIterator implements Iterator {
714: int index;
715: Entry entry = null;
716: Entry lastReturned = null;
717: int expectedModCount = modCount;
718:
719: /**
720: * Strong reference needed to avoid disappearance of key
721: * between hasNext and next
722: */
723: Object nextKey = null;
724:
725: /**
726: * Strong reference needed to avoid disappearance of key
727: * between nextEntry() and any use of the entry
728: */
729: Object currentKey = null;
730:
731: HashIterator() {
732: index = (size() != 0 ? table.length : 0);
733: }
734:
735: public boolean hasNext() {
736: Entry[] t = table;
737:
738: while (nextKey == null) {
739: Entry e = entry;
740: int i = index;
741: while (e == null && i > 0)
742: e = t[--i];
743: entry = e;
744: index = i;
745: if (e == null) {
746: currentKey = null;
747: return false;
748: }
749: nextKey = e.get(); // hold on to key in strong ref
750: if (nextKey == null)
751: entry = entry.next;
752: }
753: return true;
754: }
755:
756: /** The common parts of next() across different types of iterators */
757: protected Entry nextEntry() {
758: if (modCount != expectedModCount)
759: throw new ConcurrentModificationException();
760: if (nextKey == null && !hasNext())
761: throw new NoSuchElementException();
762:
763: lastReturned = entry;
764: entry = entry.next;
765: currentKey = nextKey;
766: nextKey = null;
767: return lastReturned;
768: }
769:
770: public void remove() {
771: if (lastReturned == null)
772: throw new IllegalStateException();
773: if (modCount != expectedModCount)
774: throw new ConcurrentModificationException();
775:
776: WeakHashMap.this .remove(currentKey);
777: expectedModCount = modCount;
778: lastReturned = null;
779: currentKey = null;
780: }
781:
782: }
783:
784: private class ValueIterator extends HashIterator {
785: public Object next() {
786: return nextEntry().value;
787: }
788: }
789:
790: private class KeyIterator extends HashIterator {
791: public Object next() {
792: return nextEntry().getKey();
793: }
794: }
795:
796: private class EntryIterator extends HashIterator {
797: public Object next() {
798: return nextEntry();
799: }
800: }
801:
802: // Views
803:
804: private transient Set entrySet = null;
805:
806: /**
807: * Returns a set view of the keys contained in this map. The set is
808: * backed by the map, so changes to the map are reflected in the set, and
809: * vice-versa. The set supports element removal, which removes the
810: * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
811: * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
812: * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
813: * <tt>addAll</tt> operations.
814: *
815: * @return a set view of the keys contained in this map.
816: */
817: public Set keySet() {
818: Set ks = keySet;
819: return (ks != null ? ks : (keySet = new KeySet()));
820: }
821:
822: private class KeySet extends AbstractSet {
823: public Iterator iterator() {
824: return new KeyIterator();
825: }
826:
827: public int size() {
828: return WeakHashMap.this .size();
829: }
830:
831: public boolean contains(Object o) {
832: return containsKey(o);
833: }
834:
835: public boolean remove(Object o) {
836: if (containsKey(o)) {
837: WeakHashMap.this .remove(o);
838: return true;
839: } else
840: return false;
841: }
842:
843: public void clear() {
844: WeakHashMap.this .clear();
845: }
846:
847: public Object[] toArray() {
848: Collection c = new ArrayList(size());
849: for (Iterator i = iterator(); i.hasNext();)
850: c.add(i.next());
851: return c.toArray();
852: }
853:
854: public Object[] toArray(Object a[]) {
855: Collection c = new ArrayList(size());
856: for (Iterator i = iterator(); i.hasNext();)
857: c.add(i.next());
858: return c.toArray(a);
859: }
860: }
861:
862: /**
863: * Returns a collection view of the values contained in this map. The
864: * collection is backed by the map, so changes to the map are reflected in
865: * the collection, and vice-versa. The collection supports element
866: * removal, which removes the corresponding mapping from this map, via the
867: * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
868: * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
869: * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
870: *
871: * @return a collection view of the values contained in this map.
872: */
873: public Collection values() {
874: Collection vs = values;
875: return (vs != null ? vs : (values = new Values()));
876: }
877:
878: private class Values extends AbstractCollection {
879: public Iterator iterator() {
880: return new ValueIterator();
881: }
882:
883: public int size() {
884: return WeakHashMap.this .size();
885: }
886:
887: public boolean contains(Object o) {
888: return containsValue(o);
889: }
890:
891: public void clear() {
892: WeakHashMap.this .clear();
893: }
894:
895: public Object[] toArray() {
896: Collection c = new ArrayList(size());
897: for (Iterator i = iterator(); i.hasNext();)
898: c.add(i.next());
899: return c.toArray();
900: }
901:
902: public Object[] toArray(Object a[]) {
903: Collection c = new ArrayList(size());
904: for (Iterator i = iterator(); i.hasNext();)
905: c.add(i.next());
906: return c.toArray(a);
907: }
908: }
909:
910: /**
911: * Returns a collection view of the mappings contained in this map. Each
912: * element in the returned collection is a <tt>Map.Entry</tt>. The
913: * collection is backed by the map, so changes to the map are reflected in
914: * the collection, and vice-versa. The collection supports element
915: * removal, which removes the corresponding mapping from the map, via the
916: * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
917: * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
918: * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
919: *
920: * @return a collection view of the mappings contained in this map.
921: * @see Map.Entry
922: */
923: public Set entrySet() {
924: Set es = entrySet;
925: return (es != null ? es : (entrySet = new EntrySet()));
926: }
927:
928: private class EntrySet extends AbstractSet {
929: public Iterator iterator() {
930: return new EntryIterator();
931: }
932:
933: public boolean contains(Object o) {
934: if (!(o instanceof Map.Entry))
935: return false;
936: Map.Entry e = (Map.Entry) o;
937: Object k = e.getKey();
938: Entry candidate = getEntry(e.getKey());
939: return candidate != null && candidate.equals(e);
940: }
941:
942: public boolean remove(Object o) {
943: return removeMapping(o) != null;
944: }
945:
946: public int size() {
947: return WeakHashMap.this .size();
948: }
949:
950: public void clear() {
951: WeakHashMap.this .clear();
952: }
953:
954: public Object[] toArray() {
955: Collection c = new ArrayList(size());
956: for (Iterator i = iterator(); i.hasNext();)
957: c
958: .add(new AbstractMap.SimpleEntry((Map.Entry) i
959: .next()));
960: return c.toArray();
961: }
962:
963: public Object[] toArray(Object a[]) {
964: Collection c = new ArrayList(size());
965: for (Iterator i = iterator(); i.hasNext();)
966: c
967: .add(new AbstractMap.SimpleEntry((Map.Entry) i
968: .next()));
969: return c.toArray(a);
970: }
971: }
972: }
|