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