1 /*
2 * Copyright (c) 1998, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 import java.lang.ref.WeakReference;
29 import java.lang.ref.ReferenceQueue;
30 import java.util.function.Consumer;
31
32
33 /**
34 * Hash table based implementation of the <tt>Map</tt> interface, with
35 * <em>weak keys</em>.
36 * An entry in a <tt>WeakHashMap</tt> will automatically be removed when
37 * its key is no longer in ordinary use. More precisely, the presence of a
38 * mapping for a given key will not prevent the key from being discarded by the
39 * garbage collector, that is, made finalizable, finalized, and then reclaimed.
40 * When a key has been discarded its entry is effectively removed from the map,
41 * so this class behaves somewhat differently from other <tt>Map</tt>
42 * implementations.
43 *
44 * <p> Both null values and the null key are supported. This class has
45 * performance characteristics similar to those of the <tt>HashMap</tt>
46 * class, and has the same efficiency parameters of <em>initial capacity</em>
47 * and <em>load factor</em>.
48 *
49 * <p> Like most collection classes, this class is not synchronized.
50 * A synchronized <tt>WeakHashMap</tt> may be constructed using the
51 * {@link Collections#synchronizedMap Collections.synchronizedMap}
52 * method.
53 *
54 * <p> This class is intended primarily for use with key objects whose
55 * <tt>equals</tt> methods test for object identity using the
56 * <tt>==</tt> operator. Once such a key is discarded it can never be
57 * recreated, so it is impossible to do a lookup of that key in a
58 * <tt>WeakHashMap</tt> at some later time and be surprised that its entry
59 * has been removed. This class will work perfectly well with key objects
60 * whose <tt>equals</tt> methods are not based upon object identity, such
61 * as <tt>String</tt> instances. With such recreatable key objects,
62 * however, the automatic removal of <tt>WeakHashMap</tt> entries whose
63 * keys have been discarded may prove to be confusing.
64 *
65 * <p> The behavior of the <tt>WeakHashMap</tt> class depends in part upon
66 * the actions of the garbage collector, so several familiar (though not
67 * required) <tt>Map</tt> invariants do not hold for this class. Because
68 * the garbage collector may discard keys at any time, a
69 * <tt>WeakHashMap</tt> may behave as though an unknown thread is silently
70 * removing entries. In particular, even if you synchronize on a
71 * <tt>WeakHashMap</tt> instance and invoke none of its mutator methods, it
72 * is possible for the <tt>size</tt> method to return smaller values over
73 * time, for the <tt>isEmpty</tt> method to return <tt>false</tt> and
74 * then <tt>true</tt>, for the <tt>containsKey</tt> method to return
75 * <tt>true</tt> and later <tt>false</tt> for a given key, for the
76 * <tt>get</tt> method to return a value for a given key but later return
77 * <tt>null</tt>, for the <tt>put</tt> method to return
78 * <tt>null</tt> and the <tt>remove</tt> method to return
79 * <tt>false</tt> for a key that previously appeared to be in the map, and
80 * for successive examinations of the key set, the value collection, and
81 * the entry set to yield successively smaller numbers of elements.
82 *
83 * <p> Each key object in a <tt>WeakHashMap</tt> is stored indirectly as
84 * the referent of a weak reference. Therefore a key will automatically be
85 * removed only after the weak references to it, both inside and outside of the
86 * map, have been cleared by the garbage collector.
87 *
88 * <p> <strong>Implementation note:</strong> The value objects in a
89 * <tt>WeakHashMap</tt> are held by ordinary strong references. Thus care
90 * should be taken to ensure that value objects do not strongly refer to their
91 * own keys, either directly or indirectly, since that will prevent the keys
92 * from being discarded. Note that a value object may refer indirectly to its
93 * key via the <tt>WeakHashMap</tt> itself; that is, a value object may
94 * strongly refer to some other key object whose associated value object, in
95 * turn, strongly refers to the key of the first value object. If the values
96 * in the map do not rely on the map holding strong references to them, one way
97 * to deal with this is to wrap values themselves within
98 * <tt>WeakReferences</tt> before
99 * inserting, as in: <tt>m.put(key, new WeakReference(value))</tt>,
100 * and then unwrapping upon each <tt>get</tt>.
101 *
102 * <p>The iterators returned by the <tt>iterator</tt> method of the collections
103 * returned by all of this class's "collection view methods" are
104 * <i>fail-fast</i>: if the map is structurally modified at any time after the
105 * iterator is created, in any way except through the iterator's own
106 * <tt>remove</tt> method, the iterator will throw a {@link
107 * ConcurrentModificationException}. Thus, in the face of concurrent
108 * modification, the iterator fails quickly and cleanly, rather than risking
109 * arbitrary, non-deterministic behavior at an undetermined time in the future.
110 *
111 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
112 * as it is, generally speaking, impossible to make any hard guarantees in the
113 * presence of unsynchronized concurrent modification. Fail-fast iterators
114 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
115 * Therefore, it would be wrong to write a program that depended on this
116 * exception for its correctness: <i>the fail-fast behavior of iterators
117 * should be used only to detect bugs.</i>
118 *
119 * <p>This class is a member of the
120 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
121 * Java Collections Framework</a>.
122 *
123 * @param <K> the type of keys maintained by this map
124 * @param <V> the type of mapped values
125 *
126 * @author Doug Lea
127 * @author Josh Bloch
128 * @author Mark Reinhold
129 * @since 1.2
130 * @see java.util.HashMap
131 * @see java.lang.ref.WeakReference
132 */
133 public class WeakHashMap<K,V>
134 extends AbstractMap<K,V>
135 implements Map<K,V> {
136
137 /**
138 * The default initial capacity -- MUST be a power of two.
139 */
140 private static final int DEFAULT_INITIAL_CAPACITY = 16;
141
142 /**
143 * The maximum capacity, used if a higher value is implicitly specified
144 * by either of the constructors with arguments.
145 * MUST be a power of two <= 1<<30.
146 */
147 private static final int MAXIMUM_CAPACITY = 1 << 30;
148
149 /**
150 * The load factor used when none specified in constructor.
151 */
152 private static final float DEFAULT_LOAD_FACTOR = 0.75f;
153
154 /**
155 * The table, resized as necessary. Length MUST Always be a power of two.
156 */
157 Entry<K,V>[] table;
158
159 /**
160 * The number of key-value mappings contained in this weak hash map.
161 */
162 private int size;
163
164 /**
165 * The next size value at which to resize (capacity * load factor).
166 */
167 private int threshold;
168
169 /**
170 * The load factor for the hash table.
171 */
172 private final float loadFactor;
173
174 /**
175 * Reference queue for cleared WeakEntries
176 */
177 private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
178
179 /**
180 * The number of times this WeakHashMap has been structurally modified.
181 * Structural modifications are those that change the number of
182 * mappings in the map or otherwise modify its internal structure
183 * (e.g., rehash). This field is used to make iterators on
184 * Collection-views of the map fail-fast.
185 *
186 * @see ConcurrentModificationException
187 */
188 int modCount;
189
190 private static class Holder {
191 static final boolean USE_HASHSEED;
192
193 static {
194 String hashSeedProp = java.security.AccessController.doPrivileged(
195 new sun.security.action.GetPropertyAction(
196 "jdk.map.useRandomSeed"));
197 boolean localBool = (null != hashSeedProp)
198 ? Boolean.parseBoolean(hashSeedProp) : false;
199 USE_HASHSEED = localBool;
200 }
201 }
202
203 /**
204 * A randomizing value associated with this instance that is applied to
205 * hash code of keys to make hash collisions harder to find.
206 *
207 * Non-final so it can be set lazily, but be sure not to set more than once.
208 */
209 transient int hashSeed;
210
211 /**
212 * Initialize the hashing mask value.
213 */
214 final void initHashSeed() {
215 if (sun.misc.VM.isBooted() && Holder.USE_HASHSEED) {
216 // Do not set hashSeed more than once!
217 // assert hashSeed == 0;
218 hashSeed = sun.misc.Hashing.randomHashSeed(this);
219 }
220 }
221
222 @SuppressWarnings("unchecked")
223 private Entry<K,V>[] newTable(int n) {
224 return (Entry<K,V>[]) new Entry<?,?>[n];
225 }
226
227 /**
228 * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial
229 * capacity and the given load factor.
230 *
231 * @param initialCapacity The initial capacity of the <tt>WeakHashMap</tt>
232 * @param loadFactor The load factor of the <tt>WeakHashMap</tt>
233 * @throws IllegalArgumentException if the initial capacity is negative,
234 * or if the load factor is nonpositive.
235 */
236 public WeakHashMap(int initialCapacity, float loadFactor) {
237 if (initialCapacity < 0)
238 throw new IllegalArgumentException("Illegal Initial Capacity: "+
239 initialCapacity);
240 if (initialCapacity > MAXIMUM_CAPACITY)
241 initialCapacity = MAXIMUM_CAPACITY;
242
243 if (loadFactor <= 0 || Float.isNaN(loadFactor))
244 throw new IllegalArgumentException("Illegal Load factor: "+
245 loadFactor);
246 int capacity = 1;
247 while (capacity < initialCapacity)
248 capacity <<= 1;
249 table = newTable(capacity);
250 this.loadFactor = loadFactor;
251 threshold = (int)(capacity * loadFactor);
252 initHashSeed();
253 }
254
255 /**
256 * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial
257 * capacity and the default load factor (0.75).
258 *
259 * @param initialCapacity The initial capacity of the <tt>WeakHashMap</tt>
260 * @throws IllegalArgumentException if the initial capacity is negative
261 */
262 public WeakHashMap(int initialCapacity) {
263 this(initialCapacity, DEFAULT_LOAD_FACTOR);
264 }
265
266 /**
267 * Constructs a new, empty <tt>WeakHashMap</tt> with the default initial
268 * capacity (16) and load factor (0.75).
269 */
270 public WeakHashMap() {
271 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
272 }
273
274 /**
275 * Constructs a new <tt>WeakHashMap</tt> with the same mappings as the
276 * specified map. The <tt>WeakHashMap</tt> is created with the default
277 * load factor (0.75) and an initial capacity sufficient to hold the
278 * mappings in the specified map.
279 *
280 * @param m the map whose mappings are to be placed in this map
281 * @throws NullPointerException if the specified map is null
282 * @since 1.3
283 */
284 public WeakHashMap(Map<? extends K, ? extends V> m) {
285 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
286 DEFAULT_INITIAL_CAPACITY),
287 DEFAULT_LOAD_FACTOR);
288 putAll(m);
289 }
290
291 // internal utilities
292
293 /**
294 * Value representing null keys inside tables.
295 */
296 private static final Object NULL_KEY = new Object();
297
298 /**
299 * Use NULL_KEY for key if it is null.
300 */
301 private static Object maskNull(Object key) {
302 return (key == null) ? NULL_KEY : key;
303 }
304
305 /**
306 * Returns internal representation of null key back to caller as null.
307 */
308 static Object unmaskNull(Object key) {
309 return (key == NULL_KEY) ? null : key;
310 }
311
312 /**
313 * Checks for equality of non-null reference x and possibly-null y. By
314 * default uses Object.equals.
315 */
316 private static boolean eq(Object x, Object y) {
317 return x == y || x.equals(y);
318 }
319
320 /**
321 * Retrieve object hash code and applies a supplemental hash function to the
322 * result hash, which defends against poor quality hash functions. This is
323 * critical because HashMap uses power-of-two length hash tables, that
324 * otherwise encounter collisions for hashCodes that do not differ
325 * in lower bits.
326 */
327 final int hash(Object k) {
328 int h = hashSeed ^ k.hashCode();
329
330 // This function ensures that hashCodes that differ only by
331 // constant multiples at each bit position have a bounded
332 // number of collisions (approximately 8 at default load factor).
333 h ^= (h >>> 20) ^ (h >>> 12);
334 return h ^ (h >>> 7) ^ (h >>> 4);
335 }
336
337 /**
338 * Returns index for hash code h.
339 */
340 private static int indexFor(int h, int length) {
341 return h & (length-1);
342 }
343
344 /**
345 * Expunges stale entries from the table.
346 */
347 private void expungeStaleEntries() {
348 for (Object x; (x = queue.poll()) != null; ) {
349 synchronized (queue) {
350 @SuppressWarnings("unchecked")
351 Entry<K,V> e = (Entry<K,V>) x;
352 int i = indexFor(e.hash, table.length);
353
354 Entry<K,V> prev = table[i];
355 Entry<K,V> p = prev;
356 while (p != null) {
357 Entry<K,V> next = p.next;
358 if (p == e) {
359 if (prev == e)
360 table[i] = next;
361 else
362 prev.next = next;
363 // Must not null out e.next;
364 // stale entries may be in use by a HashIterator
365 e.value = null; // Help GC
366 size--;
367 break;
368 }
369 prev = p;
370 p = next;
371 }
372 }
373 }
374 }
375
376 /**
377 * Returns the table after first expunging stale entries.
378 */
379 private Entry<K,V>[] getTable() {
380 expungeStaleEntries();
381 return table;
382 }
383
384 /**
385 * Returns the number of key-value mappings in this map.
386 * This result is a snapshot, and may not reflect unprocessed
387 * entries that will be removed before next attempted access
388 * because they are no longer referenced.
389 */
390 public int size() {
391 if (size == 0)
392 return 0;
393 expungeStaleEntries();
394 return size;
395 }
396
397 /**
398 * Returns <tt>true</tt> if this map contains no key-value mappings.
399 * This result is a snapshot, and may not reflect unprocessed
400 * entries that will be removed before next attempted access
401 * because they are no longer referenced.
402 */
403 public boolean isEmpty() {
404 return size() == 0;
405 }
406
407 /**
408 * Returns the value to which the specified key is mapped,
409 * or {@code null} if this map contains no mapping for the key.
410 *
411 * <p>More formally, if this map contains a mapping from a key
412 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
413 * key.equals(k))}, then this method returns {@code v}; otherwise
414 * it returns {@code null}. (There can be at most one such mapping.)
415 *
416 * <p>A return value of {@code null} does not <i>necessarily</i>
417 * indicate that the map contains no mapping for the key; it's also
418 * possible that the map explicitly maps the key to {@code null}.
419 * The {@link #containsKey containsKey} operation may be used to
420 * distinguish these two cases.
421 *
422 * @see #put(Object, Object)
423 */
424 public V get(Object key) {
425 Object k = maskNull(key);
426 int h = hash(k);
427 Entry<K,V>[] tab = getTable();
428 int index = indexFor(h, tab.length);
429 Entry<K,V> e = tab[index];
430 while (e != null) {
431 if (e.hash == h && eq(k, e.get()))
432 return e.value;
433 e = e.next;
434 }
435 return null;
436 }
437
438 /**
439 * Returns <tt>true</tt> if this map contains a mapping for the
440 * specified key.
441 *
442 * @param key The key whose presence in this map is to be tested
443 * @return <tt>true</tt> if there is a mapping for <tt>key</tt>;
444 * <tt>false</tt> otherwise
445 */
446 public boolean containsKey(Object key) {
447 return getEntry(key) != null;
448 }
449
450 /**
451 * Returns the entry associated with the specified key in this map.
452 * Returns null if the map contains no mapping for this key.
453 */
454 Entry<K,V> getEntry(Object key) {
455 Object k = maskNull(key);
456 int h = hash(k);
457 Entry<K,V>[] tab = getTable();
458 int index = indexFor(h, tab.length);
459 Entry<K,V> e = tab[index];
460 while (e != null && !(e.hash == h && eq(k, e.get())))
461 e = e.next;
462 return e;
463 }
464
465 /**
466 * Associates the specified value with the specified key in this map.
467 * If the map previously contained a mapping for this key, the old
468 * value is replaced.
469 *
470 * @param key key with which the specified value is to be associated.
471 * @param value value to be associated with the specified key.
472 * @return the previous value associated with <tt>key</tt>, or
473 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
474 * (A <tt>null</tt> return can also indicate that the map
475 * previously associated <tt>null</tt> with <tt>key</tt>.)
476 */
477 public V put(K key, V value) {
478 Object k = maskNull(key);
479 int h = hash(k);
480 Entry<K,V>[] tab = getTable();
481 int i = indexFor(h, tab.length);
482
483 for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
484 if (h == e.hash && eq(k, e.get())) {
485 V oldValue = e.value;
486 if (value != oldValue)
487 e.value = value;
488 return oldValue;
489 }
490 }
491
492 modCount++;
493 Entry<K,V> e = tab[i];
494 tab[i] = new Entry<>(k, value, queue, h, e);
495 if (++size >= threshold)
496 resize(tab.length * 2);
497 return null;
498 }
499
500 /**
501 * Rehashes the contents of this map into a new array with a
502 * larger capacity. This method is called automatically when the
503 * number of keys in this map reaches its threshold.
504 *
505 * If current capacity is MAXIMUM_CAPACITY, this method does not
506 * resize the map, but sets threshold to Integer.MAX_VALUE.
507 * This has the effect of preventing future calls.
508 *
509 * @param newCapacity the new capacity, MUST be a power of two;
510 * must be greater than current capacity unless current
511 * capacity is MAXIMUM_CAPACITY (in which case value
512 * is irrelevant).
513 */
514 void resize(int newCapacity) {
515 Entry<K,V>[] oldTable = getTable();
516 int oldCapacity = oldTable.length;
517 if (oldCapacity == MAXIMUM_CAPACITY) {
518 threshold = Integer.MAX_VALUE;
519 return;
520 }
521
522 Entry<K,V>[] newTable = newTable(newCapacity);
523 transfer(oldTable, newTable);
524 table = newTable;
525
526 /*
527 * If ignoring null elements and processing ref queue caused massive
528 * shrinkage, then restore old table. This should be rare, but avoids
529 * unbounded expansion of garbage-filled tables.
530 */
531 if (size >= threshold / 2) {
532 threshold = (int)(newCapacity * loadFactor);
533 } else {
534 expungeStaleEntries();
535 transfer(newTable, oldTable);
536 table = oldTable;
537 }
538 }
539
540 /** Transfers all entries from src to dest tables */
541 private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
542 for (int j = 0; j < src.length; ++j) {
543 Entry<K,V> e = src[j];
544 src[j] = null;
545 while (e != null) {
546 Entry<K,V> next = e.next;
547 Object key = e.get();
548 if (key == null) {
549 e.next = null; // Help GC
550 e.value = null; // " "
551 size--;
552 } else {
553 int i = indexFor(e.hash, dest.length);
554 e.next = dest[i];
555 dest[i] = e;
556 }
557 e = next;
558 }
559 }
560 }
561
562 /**
563 * Copies all of the mappings from the specified map to this map.
564 * These mappings will replace any mappings that this map had for any
565 * of the keys currently in the specified map.
566 *
567 * @param m mappings to be stored in this map.
568 * @throws NullPointerException if the specified map is null.
569 */
570 public void putAll(Map<? extends K, ? extends V> m) {
571 int numKeysToBeAdded = m.size();
572 if (numKeysToBeAdded == 0)
573 return;
574
575 /*
576 * Expand the map if the map if the number of mappings to be added
577 * is greater than or equal to threshold. This is conservative; the
578 * obvious condition is (m.size() + size) >= threshold, but this
579 * condition could result in a map with twice the appropriate capacity,
580 * if the keys to be added overlap with the keys already in this map.
581 * By using the conservative calculation, we subject ourself
582 * to at most one extra resize.
583 */
584 if (numKeysToBeAdded > threshold) {
585 int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
586 if (targetCapacity > MAXIMUM_CAPACITY)
587 targetCapacity = MAXIMUM_CAPACITY;
588 int newCapacity = table.length;
589 while (newCapacity < targetCapacity)
590 newCapacity <<= 1;
591 if (newCapacity > table.length)
592 resize(newCapacity);
593 }
594
595 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
596 put(e.getKey(), e.getValue());
597 }
598
599 /**
600 * Removes the mapping for a key from this weak hash map if it is present.
601 * More formally, if this map contains a mapping from key <tt>k</tt> to
602 * value <tt>v</tt> such that <code>(key==null ? k==null :
603 * key.equals(k))</code>, that mapping is removed. (The map can contain
604 * at most one such mapping.)
605 *
606 * <p>Returns the value to which this map previously associated the key,
607 * or <tt>null</tt> if the map contained no mapping for the key. A
608 * return value of <tt>null</tt> does not <i>necessarily</i> indicate
609 * that the map contained no mapping for the key; it's also possible
610 * that the map explicitly mapped the key to <tt>null</tt>.
611 *
612 * <p>The map will not contain a mapping for the specified key once the
613 * call returns.
614 *
615 * @param key key whose mapping is to be removed from the map
616 * @return the previous value associated with <tt>key</tt>, or
617 * <tt>null</tt> if there was no mapping for <tt>key</tt>
618 */
619 public V remove(Object key) {
620 Object k = maskNull(key);
621 int h = hash(k);
622 Entry<K,V>[] tab = getTable();
623 int i = indexFor(h, tab.length);
624 Entry<K,V> prev = tab[i];
625 Entry<K,V> e = prev;
626
627 while (e != null) {
628 Entry<K,V> next = e.next;
629 if (h == e.hash && eq(k, e.get())) {
630 modCount++;
631 size--;
632 if (prev == e)
633 tab[i] = next;
634 else
635 prev.next = next;
636 return e.value;
637 }
638 prev = e;
639 e = next;
640 }
641
642 return null;
643 }
644
645 /** Special version of remove needed by Entry set */
646 boolean removeMapping(Object o) {
647 if (!(o instanceof Map.Entry))
648 return false;
649 Entry<K,V>[] tab = getTable();
650 Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
651 Object k = maskNull(entry.getKey());
652 int h = hash(k);
653 int i = indexFor(h, tab.length);
654 Entry<K,V> prev = tab[i];
655 Entry<K,V> e = prev;
656
657 while (e != null) {
658 Entry<K,V> next = e.next;
659 if (h == e.hash && e.equals(entry)) {
660 modCount++;
661 size--;
662 if (prev == e)
663 tab[i] = next;
664 else
665 prev.next = next;
666 return true;
667 }
668 prev = e;
669 e = next;
670 }
671
672 return false;
673 }
674
675 /**
676 * Removes all of the mappings from this map.
677 * The map will be empty after this call returns.
678 */
679 public void clear() {
680 // clear out ref queue. We don't need to expunge entries
681 // since table is getting cleared.
682 while (queue.poll() != null)
683 ;
684
685 modCount++;
686 Arrays.fill(table, null);
687 size = 0;
688
689 // Allocation of array may have caused GC, which may have caused
690 // additional entries to go stale. Removing these entries from the
691 // reference queue will make them eligible for reclamation.
692 while (queue.poll() != null)
693 ;
694 }
695
696 /**
697 * Returns <tt>true</tt> if this map maps one or more keys to the
698 * specified value.
699 *
700 * @param value value whose presence in this map is to be tested
701 * @return <tt>true</tt> if this map maps one or more keys to the
702 * specified value
703 */
704 public boolean containsValue(Object value) {
705 if (value==null)
706 return containsNullValue();
707
708 Entry<K,V>[] tab = getTable();
709 for (int i = tab.length; i-- > 0;)
710 for (Entry<K,V> e = tab[i]; e != null; e = e.next)
711 if (value.equals(e.value))
712 return true;
713 return false;
714 }
715
716 /**
717 * Special-case code for containsValue with null argument
718 */
719 private boolean containsNullValue() {
720 Entry<K,V>[] tab = getTable();
721 for (int i = tab.length; i-- > 0;)
722 for (Entry<K,V> e = tab[i]; e != null; e = e.next)
723 if (e.value==null)
724 return true;
725 return false;
726 }
727
728 /**
729 * The entries in this hash table extend WeakReference, using its main ref
730 * field as the key.
731 */
732 private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
733 V value;
734 final int hash;
735 Entry<K,V> next;
736
737 /**
738 * Creates new entry.
739 */
740 Entry(Object key, V value,
741 ReferenceQueue<Object> queue,
742 int hash, Entry<K,V> next) {
743 super(key, queue);
744 this.value = value;
745 this.hash = hash;
746 this.next = next;
747 }
748
749 @SuppressWarnings("unchecked")
750 public K getKey() {
751 return (K) WeakHashMap.unmaskNull(get());
752 }
753
754 public V getValue() {
755 return value;
756 }
757
758 public V setValue(V newValue) {
759 V oldValue = value;
760 value = newValue;
761 return oldValue;
762 }
763
764 public boolean equals(Object o) {
765 if (!(o instanceof Map.Entry))
766 return false;
767 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
768 K k1 = getKey();
769 Object k2 = e.getKey();
770 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
771 V v1 = getValue();
772 Object v2 = e.getValue();
773 if (v1 == v2 || (v1 != null && v1.equals(v2)))
774 return true;
775 }
776 return false;
777 }
778
779 public int hashCode() {
780 K k = getKey();
781 V v = getValue();
782 return ((k==null ? 0 : k.hashCode()) ^
783 (v==null ? 0 : v.hashCode()));
784 }
785
786 public String toString() {
787 return getKey() + "=" + getValue();
788 }
789 }
790
791 private abstract class HashIterator<T> implements Iterator<T> {
792 private int index;
793 private Entry<K,V> entry = null;
794 private Entry<K,V> lastReturned = null;
795 private int expectedModCount = modCount;
796
797 /**
798 * Strong reference needed to avoid disappearance of key
799 * between hasNext and next
800 */
801 private Object nextKey = null;
802
803 /**
804 * Strong reference needed to avoid disappearance of key
805 * between nextEntry() and any use of the entry
806 */
807 private Object currentKey = null;
808
809 HashIterator() {
810 index = isEmpty() ? 0 : table.length;
811 }
812
813 public boolean hasNext() {
814 Entry<K,V>[] t = table;
815
816 while (nextKey == null) {
817 Entry<K,V> e = entry;
818 int i = index;
819 while (e == null && i > 0)
820 e = t[--i];
821 entry = e;
822 index = i;
823 if (e == null) {
824 currentKey = null;
825 return false;
826 }
827 nextKey = e.get(); // hold on to key in strong ref
828 if (nextKey == null)
829 entry = entry.next;
830 }
831 return true;
832 }
833
834 /** The common parts of next() across different types of iterators */
835 protected Entry<K,V> nextEntry() {
836 if (modCount != expectedModCount)
837 throw new ConcurrentModificationException();
838 if (nextKey == null && !hasNext())
839 throw new NoSuchElementException();
840
841 lastReturned = entry;
842 entry = entry.next;
843 currentKey = nextKey;
844 nextKey = null;
845 return lastReturned;
846 }
847
848 public void remove() {
849 if (lastReturned == null)
850 throw new IllegalStateException();
851 if (modCount != expectedModCount)
852 throw new ConcurrentModificationException();
853
854 WeakHashMap.this.remove(currentKey);
855 expectedModCount = modCount;
856 lastReturned = null;
857 currentKey = null;
858 }
859
860 }
861
862 private class ValueIterator extends HashIterator<V> {
863 public V next() {
864 return nextEntry().value;
865 }
866 }
867
868 private class KeyIterator extends HashIterator<K> {
869 public K next() {
870 return nextEntry().getKey();
871 }
872 }
873
874 private class EntryIterator extends HashIterator<Map.Entry<K,V>> {
875 public Map.Entry<K,V> next() {
876 return nextEntry();
877 }
878 }
879
880 // Views
881
882 private transient Set<Map.Entry<K,V>> entrySet = null;
883
884 /**
885 * Returns a {@link Set} view of the keys contained in this map.
886 * The set is backed by the map, so changes to the map are
887 * reflected in the set, and vice-versa. If the map is modified
888 * while an iteration over the set is in progress (except through
889 * the iterator's own <tt>remove</tt> operation), the results of
890 * the iteration are undefined. The set supports element removal,
891 * which removes the corresponding mapping from the map, via the
892 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
893 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
894 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
895 * operations.
896 */
897 public Set<K> keySet() {
898 Set<K> ks = keySet;
899 return (ks != null ? ks : (keySet = new KeySet()));
900 }
901
902 private class KeySet extends AbstractSet<K> {
903 public Iterator<K> iterator() {
904 return new KeyIterator();
905 }
906
907 public int size() {
908 return WeakHashMap.this.size();
909 }
910
911 public boolean contains(Object o) {
912 return containsKey(o);
913 }
914
915 public boolean remove(Object o) {
916 if (containsKey(o)) {
917 WeakHashMap.this.remove(o);
918 return true;
919 }
920 else
921 return false;
922 }
923
924 public void clear() {
925 WeakHashMap.this.clear();
926 }
927
928 public Spliterator<K> spliterator() {
929 return new KeySpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
930 }
931 }
932
933 /**
934 * Returns a {@link Collection} view of the values contained in this map.
935 * The collection is backed by the map, so changes to the map are
936 * reflected in the collection, and vice-versa. If the map is
937 * modified while an iteration over the collection is in progress
938 * (except through the iterator's own <tt>remove</tt> operation),
939 * the results of the iteration are undefined. The collection
940 * supports element removal, which removes the corresponding
941 * mapping from the map, via the <tt>Iterator.remove</tt>,
942 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
943 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
944 * support the <tt>add</tt> or <tt>addAll</tt> operations.
945 */
946 public Collection<V> values() {
947 Collection<V> vs = values;
948 return (vs != null) ? vs : (values = new Values());
949 }
950
951 private class Values extends AbstractCollection<V> {
952 public Iterator<V> iterator() {
953 return new ValueIterator();
954 }
955
956 public int size() {
957 return WeakHashMap.this.size();
958 }
959
960 public boolean contains(Object o) {
961 return containsValue(o);
962 }
963
964 public void clear() {
965 WeakHashMap.this.clear();
966 }
967
968 public Spliterator<V> spliterator() {
969 return new ValueSpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
970 }
971 }
972
973 /**
974 * Returns a {@link Set} view of the mappings contained in this map.
975 * The set is backed by the map, so changes to the map are
976 * reflected in the set, and vice-versa. If the map is modified
977 * while an iteration over the set is in progress (except through
978 * the iterator's own <tt>remove</tt> operation, or through the
979 * <tt>setValue</tt> operation on a map entry returned by the
980 * iterator) the results of the iteration are undefined. The set
981 * supports element removal, which removes the corresponding
982 * mapping from the map, via the <tt>Iterator.remove</tt>,
983 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
984 * <tt>clear</tt> operations. It does not support the
985 * <tt>add</tt> or <tt>addAll</tt> operations.
986 */
987 public Set<Map.Entry<K,V>> entrySet() {
988 Set<Map.Entry<K,V>> es = entrySet;
989 return es != null ? es : (entrySet = new EntrySet());
990 }
991
992 private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
993 public Iterator<Map.Entry<K,V>> iterator() {
994 return new EntryIterator();
995 }
996
997 public boolean contains(Object o) {
998 if (!(o instanceof Map.Entry))
999 return false;
1000 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1001 Entry<K,V> candidate = getEntry(e.getKey());
1002 return candidate != null && candidate.equals(e);
1003 }
1004
1005 public boolean remove(Object o) {
1006 return removeMapping(o);
1007 }
1008
1009 public int size() {
1010 return WeakHashMap.this.size();
1011 }
1012
1013 public void clear() {
1014 WeakHashMap.this.clear();
1015 }
1016
1017 private List<Map.Entry<K,V>> deepCopy() {
1018 List<Map.Entry<K,V>> list = new ArrayList<>(size());
1019 for (Map.Entry<K,V> e : this)
1020 list.add(new AbstractMap.SimpleEntry<>(e));
1021 return list;
1022 }
1023
1024 public Object[] toArray() {
1025 return deepCopy().toArray();
1026 }
1027
1028 public <T> T[] toArray(T[] a) {
1029 return deepCopy().toArray(a);
1030 }
1031
1032 public Spliterator<Map.Entry<K,V>> spliterator() {
1033 return new EntrySpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
1034 }
1035 }
1036
1037 /**
1038 * Similar form as other hash Spliterators, but skips dead
1039 * elements.
1040 */
1041 static class WeakHashMapSpliterator<K,V> {
1042 final WeakHashMap<K,V> map;
1043 WeakHashMap.Entry<K,V> current; // current node
1044 int index; // current index, modified on advance/split
1045 int fence; // -1 until first use; then one past last index
1046 int est; // size estimate
1047 int expectedModCount; // for comodification checks
1048
1049 WeakHashMapSpliterator(WeakHashMap<K,V> m, int origin,
1050 int fence, int est,
1051 int expectedModCount) {
1052 this.map = m;
1053 this.index = origin;
1054 this.fence = fence;
1055 this.est = est;
1056 this.expectedModCount = expectedModCount;
1057 }
1058
1059 final int getFence() { // initialize fence and size on first use
1060 int hi;
1061 if ((hi = fence) < 0) {
1062 WeakHashMap<K,V> m = map;
1063 est = m.size();
1064 expectedModCount = m.modCount;
1065 hi = fence = m.table.length;
1066 }
1067 return hi;
1068 }
1069
1070 public final long estimateSize() {
1071 getFence(); // force init
1072 return (long) est;
1073 }
1074 }
1075
1076 static final class KeySpliterator<K,V>
1077 extends WeakHashMapSpliterator<K,V>
1078 implements Spliterator<K> {
1079 KeySpliterator(WeakHashMap<K,V> m, int origin, int fence, int est,
1080 int expectedModCount) {
1081 super(m, origin, fence, est, expectedModCount);
1082 }
1083
1084 public KeySpliterator<K,V> trySplit() {
1085 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1086 return (lo >= mid) ? null :
1087 new KeySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
1088 expectedModCount);
1089 }
1090
1091 public void forEachRemaining(Consumer<? super K> action) {
1092 int i, hi, mc;
1093 if (action == null)
1094 throw new NullPointerException();
1095 WeakHashMap<K,V> m = map;
1096 WeakHashMap.Entry<K,V>[] tab = m.table;
1097 if ((hi = fence) < 0) {
1098 mc = expectedModCount = m.modCount;
1099 hi = fence = tab.length;
1100 }
1101 else
1102 mc = expectedModCount;
1103 if (tab.length >= hi && (i = index) >= 0 && i < hi) {
1104 index = hi;
1105 WeakHashMap.Entry<K,V> p = current;
1106 do {
1107 if (p == null)
1108 p = tab[i++];
1109 else {
1110 Object x = p.get();
1111 p = p.next;
1112 if (x != null) {
1113 @SuppressWarnings("unchecked") K k =
1114 (K) WeakHashMap.unmaskNull(x);
1115 action.accept(k);
1116 }
1117 }
1118 } while (p != null || i < hi);
1119 }
1120 if (m.modCount != mc)
1121 throw new ConcurrentModificationException();
1122 }
1123
1124 public boolean tryAdvance(Consumer<? super K> action) {
1125 int hi;
1126 if (action == null)
1127 throw new NullPointerException();
1128 WeakHashMap.Entry<K,V>[] tab = map.table;
1129 if (tab.length >= (hi = getFence()) && index >= 0) {
1130 while (current != null || index < hi) {
1131 if (current == null)
1132 current = tab[index++];
1133 else {
1134 Object x = current.get();
1135 current = current.next;
1136 if (x != null) {
1137 @SuppressWarnings("unchecked") K k =
1138 (K) WeakHashMap.unmaskNull(x);
1139 action.accept(k);
1140 if (map.modCount != expectedModCount)
1141 throw new ConcurrentModificationException();
1142 return true;
1143 }
1144 }
1145 }
1146 }
1147 return false;
1148 }
1149
1150 public int characteristics() {
1151 return Spliterator.DISTINCT;
1152 }
1153 }
1154
1155 static final class ValueSpliterator<K,V>
1156 extends WeakHashMapSpliterator<K,V>
1157 implements Spliterator<V> {
1158 ValueSpliterator(WeakHashMap<K,V> m, int origin, int fence, int est,
1159 int expectedModCount) {
1160 super(m, origin, fence, est, expectedModCount);
1161 }
1162
1163 public ValueSpliterator<K,V> trySplit() {
1164 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1165 return (lo >= mid) ? null :
1166 new ValueSpliterator<K,V>(map, lo, index = mid, est >>>= 1,
1167 expectedModCount);
1168 }
1169
1170 public void forEachRemaining(Consumer<? super V> action) {
1171 int i, hi, mc;
1172 if (action == null)
1173 throw new NullPointerException();
1174 WeakHashMap<K,V> m = map;
1175 WeakHashMap.Entry<K,V>[] tab = m.table;
1176 if ((hi = fence) < 0) {
1177 mc = expectedModCount = m.modCount;
1178 hi = fence = tab.length;
1179 }
1180 else
1181 mc = expectedModCount;
1182 if (tab.length >= hi && (i = index) >= 0 && i < hi) {
1183 index = hi;
1184 WeakHashMap.Entry<K,V> p = current;
1185 do {
1186 if (p == null)
1187 p = tab[i++];
1188 else {
1189 Object x = p.get();
1190 V v = p.value;
1191 p = p.next;
1192 if (x != null)
1193 action.accept(v);
1194 }
1195 } while (p != null || i < hi);
1196 }
1197 if (m.modCount != mc)
1198 throw new ConcurrentModificationException();
1199 }
1200
1201 public boolean tryAdvance(Consumer<? super V> action) {
1202 int hi;
1203 if (action == null)
1204 throw new NullPointerException();
1205 WeakHashMap.Entry<K,V>[] tab = map.table;
1206 if (tab.length >= (hi = getFence()) && index >= 0) {
1207 while (current != null || index < hi) {
1208 if (current == null)
1209 current = tab[index++];
1210 else {
1211 Object x = current.get();
1212 V v = current.value;
1213 current = current.next;
1214 if (x != null) {
1215 action.accept(v);
1216 if (map.modCount != expectedModCount)
1217 throw new ConcurrentModificationException();
1218 return true;
1219 }
1220 }
1221 }
1222 }
1223 return false;
1224 }
1225
1226 public int characteristics() {
1227 return 0;
1228 }
1229 }
1230
1231 static final class EntrySpliterator<K,V>
1232 extends WeakHashMapSpliterator<K,V>
1233 implements Spliterator<Map.Entry<K,V>> {
1234 EntrySpliterator(WeakHashMap<K,V> m, int origin, int fence, int est,
1235 int expectedModCount) {
1236 super(m, origin, fence, est, expectedModCount);
1237 }
1238
1239 public EntrySpliterator<K,V> trySplit() {
1240 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1241 return (lo >= mid) ? null :
1242 new EntrySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
1243 expectedModCount);
1244 }
1245
1246
1247 public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
1248 int i, hi, mc;
1249 if (action == null)
1250 throw new NullPointerException();
1251 WeakHashMap<K,V> m = map;
1252 WeakHashMap.Entry<K,V>[] tab = m.table;
1253 if ((hi = fence) < 0) {
1254 mc = expectedModCount = m.modCount;
1255 hi = fence = tab.length;
1256 }
1257 else
1258 mc = expectedModCount;
1259 if (tab.length >= hi && (i = index) >= 0 && i < hi) {
1260 index = hi;
1261 WeakHashMap.Entry<K,V> p = current;
1262 do {
1263 if (p == null)
1264 p = tab[i++];
1265 else {
1266 Object x = p.get();
1267 V v = p.value;
1268 p = p.next;
1269 if (x != null) {
1270 @SuppressWarnings("unchecked") K k =
1271 (K) WeakHashMap.unmaskNull(x);
1272 action.accept
1273 (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
1274 }
1275 }
1276 } while (p != null || i < hi);
1277 }
1278 if (m.modCount != mc)
1279 throw new ConcurrentModificationException();
1280 }
1281
1282 public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
1283 int hi;
1284 if (action == null)
1285 throw new NullPointerException();
1286 WeakHashMap.Entry<K,V>[] tab = map.table;
1287 if (tab.length >= (hi = getFence()) && index >= 0) {
1288 while (current != null || index < hi) {
1289 if (current == null)
1290 current = tab[index++];
1291 else {
1292 Object x = current.get();
1293 V v = current.value;
1294 current = current.next;
1295 if (x != null) {
1296 @SuppressWarnings("unchecked") K k =
1297 (K) WeakHashMap.unmaskNull(x);
1298 action.accept
1299 (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
1300 if (map.modCount != expectedModCount)
1301 throw new ConcurrentModificationException();
1302 return true;
1303 }
1304 }
1305 }
1306 }
1307 return false;
1308 }
1309
1310 public int characteristics() {
1311 return Spliterator.DISTINCT;
1312 }
1313 }
1314
1315 }