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 /**
191 * A randomizing value associated with this instance that is applied to
192 * hash code of keys to make hash collisions harder to find.
193 */
194 transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
195
196 @SuppressWarnings("unchecked")
197 private Entry<K,V>[] newTable(int n) {
198 return (Entry<K,V>[]) new Entry<?,?>[n];
199 }
200
201 /**
202 * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial
203 * capacity and the given load factor.
204 *
205 * @param initialCapacity The initial capacity of the <tt>WeakHashMap</tt>
206 * @param loadFactor The load factor of the <tt>WeakHashMap</tt>
207 * @throws IllegalArgumentException if the initial capacity is negative,
208 * or if the load factor is nonpositive.
209 */
210 public WeakHashMap(int initialCapacity, float loadFactor) {
211 if (initialCapacity < 0)
212 throw new IllegalArgumentException("Illegal Initial Capacity: "+
213 initialCapacity);
214 if (initialCapacity > MAXIMUM_CAPACITY)
215 initialCapacity = MAXIMUM_CAPACITY;
216
217 if (loadFactor <= 0 || Float.isNaN(loadFactor))
218 throw new IllegalArgumentException("Illegal Load factor: "+
219 loadFactor);
220 int capacity = 1;
221 while (capacity < initialCapacity)
222 capacity <<= 1;
223 table = newTable(capacity);
224 this.loadFactor = loadFactor;
225 threshold = (int)(capacity * loadFactor);
226 }
227
228 /**
229 * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial
230 * capacity and the default load factor (0.75).
231 *
232 * @param initialCapacity The initial capacity of the <tt>WeakHashMap</tt>
233 * @throws IllegalArgumentException if the initial capacity is negative
234 */
235 public WeakHashMap(int initialCapacity) {
236 this(initialCapacity, DEFAULT_LOAD_FACTOR);
237 }
238
239 /**
240 * Constructs a new, empty <tt>WeakHashMap</tt> with the default initial
241 * capacity (16) and load factor (0.75).
242 */
243 public WeakHashMap() {
244 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
245 }
246
247 /**
248 * Constructs a new <tt>WeakHashMap</tt> with the same mappings as the
249 * specified map. The <tt>WeakHashMap</tt> is created with the default
250 * load factor (0.75) and an initial capacity sufficient to hold the
251 * mappings in the specified map.
252 *
253 * @param m the map whose mappings are to be placed in this map
254 * @throws NullPointerException if the specified map is null
255 * @since 1.3
256 */
257 public WeakHashMap(Map<? extends K, ? extends V> m) {
258 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
259 DEFAULT_INITIAL_CAPACITY),
260 DEFAULT_LOAD_FACTOR);
261 putAll(m);
262 }
263
264 // internal utilities
265
266 /**
267 * Value representing null keys inside tables.
268 */
269 private static final Object NULL_KEY = new Object();
270
271 /**
272 * Use NULL_KEY for key if it is null.
273 */
274 private static Object maskNull(Object key) {
275 return (key == null) ? NULL_KEY : key;
276 }
277
278 /**
279 * Returns internal representation of null key back to caller as null.
280 */
281 static Object unmaskNull(Object key) {
282 return (key == NULL_KEY) ? null : key;
283 }
284
285 /**
286 * Checks for equality of non-null reference x and possibly-null y. By
287 * default uses Object.equals.
288 */
289 private static boolean eq(Object x, Object y) {
290 return x == y || x.equals(y);
291 }
292
293 /**
294 * Retrieve object hash code and applies a supplemental hash function to the
295 * result hash, which defends against poor quality hash functions. This is
296 * critical because HashMap uses power-of-two length hash tables, that
297 * otherwise encounter collisions for hashCodes that do not differ
298 * in lower bits.
299 */
300 final int hash(Object k) {
301 if (k instanceof String) {
302 return ((String) k).hash32();
303 }
304 int h = hashSeed ^ k.hashCode();
305
306 // This function ensures that hashCodes that differ only by
307 // constant multiples at each bit position have a bounded
308 // number of collisions (approximately 8 at default load factor).
309 h ^= (h >>> 20) ^ (h >>> 12);
310 return h ^ (h >>> 7) ^ (h >>> 4);
311 }
312
313 /**
314 * Returns index for hash code h.
315 */
316 private static int indexFor(int h, int length) {
317 return h & (length-1);
318 }
319
320 /**
321 * Expunges stale entries from the table.
322 */
323 private void expungeStaleEntries() {
324 for (Object x; (x = queue.poll()) != null; ) {
325 synchronized (queue) {
326 @SuppressWarnings("unchecked")
327 Entry<K,V> e = (Entry<K,V>) x;
328 int i = indexFor(e.hash, table.length);
329
330 Entry<K,V> prev = table[i];
331 Entry<K,V> p = prev;
332 while (p != null) {
333 Entry<K,V> next = p.next;
334 if (p == e) {
335 if (prev == e)
336 table[i] = next;
337 else
338 prev.next = next;
339 // Must not null out e.next;
340 // stale entries may be in use by a HashIterator
341 e.value = null; // Help GC
342 size--;
343 break;
344 }
345 prev = p;
346 p = next;
347 }
348 }
349 }
350 }
351
352 /**
353 * Returns the table after first expunging stale entries.
354 */
355 private Entry<K,V>[] getTable() {
356 expungeStaleEntries();
357 return table;
358 }
359
360 /**
361 * Returns the number of key-value mappings in this map.
362 * This result is a snapshot, and may not reflect unprocessed
363 * entries that will be removed before next attempted access
364 * because they are no longer referenced.
365 */
366 public int size() {
367 if (size == 0)
368 return 0;
369 expungeStaleEntries();
370 return size;
371 }
372
373 /**
374 * Returns <tt>true</tt> if this map contains no key-value mappings.
375 * This result is a snapshot, and may not reflect unprocessed
376 * entries that will be removed before next attempted access
377 * because they are no longer referenced.
378 */
379 public boolean isEmpty() {
380 return size() == 0;
381 }
382
383 /**
384 * Returns the value to which the specified key is mapped,
385 * or {@code null} if this map contains no mapping for the key.
386 *
387 * <p>More formally, if this map contains a mapping from a key
388 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
389 * key.equals(k))}, then this method returns {@code v}; otherwise
390 * it returns {@code null}. (There can be at most one such mapping.)
391 *
392 * <p>A return value of {@code null} does not <i>necessarily</i>
393 * indicate that the map contains no mapping for the key; it's also
394 * possible that the map explicitly maps the key to {@code null}.
395 * The {@link #containsKey containsKey} operation may be used to
396 * distinguish these two cases.
397 *
398 * @see #put(Object, Object)
399 */
400 public V get(Object key) {
401 Object k = maskNull(key);
402 int h = hash(k);
403 Entry<K,V>[] tab = getTable();
404 int index = indexFor(h, tab.length);
405 Entry<K,V> e = tab[index];
406 while (e != null) {
407 if (e.hash == h && eq(k, e.get()))
408 return e.value;
409 e = e.next;
410 }
411 return null;
412 }
413
414 /**
415 * Returns <tt>true</tt> if this map contains a mapping for the
416 * specified key.
417 *
418 * @param key The key whose presence in this map is to be tested
419 * @return <tt>true</tt> if there is a mapping for <tt>key</tt>;
420 * <tt>false</tt> otherwise
421 */
422 public boolean containsKey(Object key) {
423 return getEntry(key) != null;
424 }
425
426 /**
427 * Returns the entry associated with the specified key in this map.
428 * Returns null if the map contains no mapping for this key.
429 */
430 Entry<K,V> getEntry(Object key) {
431 Object k = maskNull(key);
432 int h = hash(k);
433 Entry<K,V>[] tab = getTable();
434 int index = indexFor(h, tab.length);
435 Entry<K,V> e = tab[index];
436 while (e != null && !(e.hash == h && eq(k, e.get())))
437 e = e.next;
438 return e;
439 }
440
441 /**
442 * Associates the specified value with the specified key in this map.
443 * If the map previously contained a mapping for this key, the old
444 * value is replaced.
445 *
446 * @param key key with which the specified value is to be associated.
447 * @param value value to be associated with the specified key.
448 * @return the previous value associated with <tt>key</tt>, or
449 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
450 * (A <tt>null</tt> return can also indicate that the map
451 * previously associated <tt>null</tt> with <tt>key</tt>.)
452 */
453 public V put(K key, V value) {
454 Object k = maskNull(key);
455 int h = hash(k);
456 Entry<K,V>[] tab = getTable();
457 int i = indexFor(h, tab.length);
458
459 for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
460 if (h == e.hash && eq(k, e.get())) {
461 V oldValue = e.value;
462 if (value != oldValue)
463 e.value = value;
464 return oldValue;
465 }
466 }
467
468 modCount++;
469 Entry<K,V> e = tab[i];
470 tab[i] = new Entry<>(k, value, queue, h, e);
471 if (++size >= threshold)
472 resize(tab.length * 2);
473 return null;
474 }
475
476 /**
477 * Rehashes the contents of this map into a new array with a
478 * larger capacity. This method is called automatically when the
479 * number of keys in this map reaches its threshold.
480 *
481 * If current capacity is MAXIMUM_CAPACITY, this method does not
482 * resize the map, but sets threshold to Integer.MAX_VALUE.
483 * This has the effect of preventing future calls.
484 *
485 * @param newCapacity the new capacity, MUST be a power of two;
486 * must be greater than current capacity unless current
487 * capacity is MAXIMUM_CAPACITY (in which case value
488 * is irrelevant).
489 */
490 void resize(int newCapacity) {
491 Entry<K,V>[] oldTable = getTable();
492 int oldCapacity = oldTable.length;
493 if (oldCapacity == MAXIMUM_CAPACITY) {
494 threshold = Integer.MAX_VALUE;
495 return;
496 }
497
498 Entry<K,V>[] newTable = newTable(newCapacity);
499 transfer(oldTable, newTable);
500 table = newTable;
501
502 /*
503 * If ignoring null elements and processing ref queue caused massive
504 * shrinkage, then restore old table. This should be rare, but avoids
505 * unbounded expansion of garbage-filled tables.
506 */
507 if (size >= threshold / 2) {
508 threshold = (int)(newCapacity * loadFactor);
509 } else {
510 expungeStaleEntries();
511 transfer(newTable, oldTable);
512 table = oldTable;
513 }
514 }
515
516 /** Transfers all entries from src to dest tables */
517 private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
518 for (int j = 0; j < src.length; ++j) {
519 Entry<K,V> e = src[j];
520 src[j] = null;
521 while (e != null) {
522 Entry<K,V> next = e.next;
523 Object key = e.get();
524 if (key == null) {
525 e.next = null; // Help GC
526 e.value = null; // " "
527 size--;
528 } else {
529 int i = indexFor(e.hash, dest.length);
530 e.next = dest[i];
531 dest[i] = e;
532 }
533 e = next;
534 }
535 }
536 }
537
538 /**
539 * Copies all of the mappings from the specified map to this map.
540 * These mappings will replace any mappings that this map had for any
541 * of the keys currently in the specified map.
542 *
543 * @param m mappings to be stored in this map.
544 * @throws NullPointerException if the specified map is null.
545 */
546 public void putAll(Map<? extends K, ? extends V> m) {
547 int numKeysToBeAdded = m.size();
548 if (numKeysToBeAdded == 0)
549 return;
550
551 /*
552 * Expand the map if the map if the number of mappings to be added
553 * is greater than or equal to threshold. This is conservative; the
554 * obvious condition is (m.size() + size) >= threshold, but this
555 * condition could result in a map with twice the appropriate capacity,
556 * if the keys to be added overlap with the keys already in this map.
557 * By using the conservative calculation, we subject ourself
558 * to at most one extra resize.
559 */
560 if (numKeysToBeAdded > threshold) {
561 int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
562 if (targetCapacity > MAXIMUM_CAPACITY)
563 targetCapacity = MAXIMUM_CAPACITY;
564 int newCapacity = table.length;
565 while (newCapacity < targetCapacity)
566 newCapacity <<= 1;
567 if (newCapacity > table.length)
568 resize(newCapacity);
569 }
570
571 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
572 put(e.getKey(), e.getValue());
573 }
574
575 /**
576 * Removes the mapping for a key from this weak hash map if it is present.
577 * More formally, if this map contains a mapping from key <tt>k</tt> to
578 * value <tt>v</tt> such that <code>(key==null ? k==null :
579 * key.equals(k))</code>, that mapping is removed. (The map can contain
580 * at most one such mapping.)
581 *
582 * <p>Returns the value to which this map previously associated the key,
583 * or <tt>null</tt> if the map contained no mapping for the key. A
584 * return value of <tt>null</tt> does not <i>necessarily</i> indicate
585 * that the map contained no mapping for the key; it's also possible
586 * that the map explicitly mapped the key to <tt>null</tt>.
587 *
588 * <p>The map will not contain a mapping for the specified key once the
589 * call returns.
590 *
591 * @param key key whose mapping is to be removed from the map
592 * @return the previous value associated with <tt>key</tt>, or
593 * <tt>null</tt> if there was no mapping for <tt>key</tt>
594 */
595 public V remove(Object key) {
596 Object k = maskNull(key);
597 int h = hash(k);
598 Entry<K,V>[] tab = getTable();
599 int i = indexFor(h, tab.length);
600 Entry<K,V> prev = tab[i];
601 Entry<K,V> e = prev;
602
603 while (e != null) {
604 Entry<K,V> next = e.next;
605 if (h == e.hash && eq(k, e.get())) {
606 modCount++;
607 size--;
608 if (prev == e)
609 tab[i] = next;
610 else
611 prev.next = next;
612 return e.value;
613 }
614 prev = e;
615 e = next;
616 }
617
618 return null;
619 }
620
621 /** Special version of remove needed by Entry set */
622 boolean removeMapping(Object o) {
623 if (!(o instanceof Map.Entry))
624 return false;
625 Entry<K,V>[] tab = getTable();
626 Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
627 Object k = maskNull(entry.getKey());
628 int h = hash(k);
629 int i = indexFor(h, tab.length);
630 Entry<K,V> prev = tab[i];
631 Entry<K,V> e = prev;
632
633 while (e != null) {
634 Entry<K,V> next = e.next;
635 if (h == e.hash && e.equals(entry)) {
636 modCount++;
637 size--;
638 if (prev == e)
639 tab[i] = next;
640 else
641 prev.next = next;
642 return true;
643 }
644 prev = e;
645 e = next;
646 }
647
648 return false;
649 }
650
651 /**
652 * Removes all of the mappings from this map.
653 * The map will be empty after this call returns.
654 */
655 public void clear() {
656 // clear out ref queue. We don't need to expunge entries
657 // since table is getting cleared.
658 while (queue.poll() != null)
659 ;
660
661 modCount++;
662 Arrays.fill(table, null);
663 size = 0;
664
665 // Allocation of array may have caused GC, which may have caused
666 // additional entries to go stale. Removing these entries from the
667 // reference queue will make them eligible for reclamation.
668 while (queue.poll() != null)
669 ;
670 }
671
672 /**
673 * Returns <tt>true</tt> if this map maps one or more keys to the
674 * specified value.
675 *
676 * @param value value whose presence in this map is to be tested
677 * @return <tt>true</tt> if this map maps one or more keys to the
678 * specified value
679 */
680 public boolean containsValue(Object value) {
681 if (value==null)
682 return containsNullValue();
683
684 Entry<K,V>[] tab = getTable();
685 for (int i = tab.length; i-- > 0;)
686 for (Entry<K,V> e = tab[i]; e != null; e = e.next)
687 if (value.equals(e.value))
688 return true;
689 return false;
690 }
691
692 /**
693 * Special-case code for containsValue with null argument
694 */
695 private boolean containsNullValue() {
696 Entry<K,V>[] tab = getTable();
697 for (int i = tab.length; i-- > 0;)
698 for (Entry<K,V> e = tab[i]; e != null; e = e.next)
699 if (e.value==null)
700 return true;
701 return false;
702 }
703
704 /**
705 * The entries in this hash table extend WeakReference, using its main ref
706 * field as the key.
707 */
708 private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
709 V value;
710 final int hash;
711 Entry<K,V> next;
712
713 /**
714 * Creates new entry.
715 */
716 Entry(Object key, V value,
717 ReferenceQueue<Object> queue,
718 int hash, Entry<K,V> next) {
719 super(key, queue);
720 this.value = value;
721 this.hash = hash;
722 this.next = next;
723 }
724
725 @SuppressWarnings("unchecked")
726 public K getKey() {
727 return (K) WeakHashMap.unmaskNull(get());
728 }
729
730 public V getValue() {
731 return value;
732 }
733
734 public V setValue(V newValue) {
735 V oldValue = value;
736 value = newValue;
737 return oldValue;
738 }
739
740 public boolean equals(Object o) {
741 if (!(o instanceof Map.Entry))
742 return false;
743 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
744 K k1 = getKey();
745 Object k2 = e.getKey();
746 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
747 V v1 = getValue();
748 Object v2 = e.getValue();
749 if (v1 == v2 || (v1 != null && v1.equals(v2)))
750 return true;
751 }
752 return false;
753 }
754
755 public int hashCode() {
756 K k = getKey();
757 V v = getValue();
758 return ((k==null ? 0 : k.hashCode()) ^
759 (v==null ? 0 : v.hashCode()));
760 }
761
762 public String toString() {
763 return getKey() + "=" + getValue();
764 }
765 }
766
767 private abstract class HashIterator<T> implements Iterator<T> {
768 private int index;
769 private Entry<K,V> entry = null;
770 private Entry<K,V> lastReturned = null;
771 private int expectedModCount = modCount;
772
773 /**
774 * Strong reference needed to avoid disappearance of key
775 * between hasNext and next
776 */
777 private Object nextKey = null;
778
779 /**
780 * Strong reference needed to avoid disappearance of key
781 * between nextEntry() and any use of the entry
782 */
783 private Object currentKey = null;
784
785 HashIterator() {
786 index = isEmpty() ? 0 : table.length;
787 }
788
789 public boolean hasNext() {
790 Entry<K,V>[] t = table;
791
792 while (nextKey == null) {
793 Entry<K,V> e = entry;
794 int i = index;
795 while (e == null && i > 0)
796 e = t[--i];
797 entry = e;
798 index = i;
799 if (e == null) {
800 currentKey = null;
801 return false;
802 }
803 nextKey = e.get(); // hold on to key in strong ref
804 if (nextKey == null)
805 entry = entry.next;
806 }
807 return true;
808 }
809
810 /** The common parts of next() across different types of iterators */
811 protected Entry<K,V> nextEntry() {
812 if (modCount != expectedModCount)
813 throw new ConcurrentModificationException();
814 if (nextKey == null && !hasNext())
815 throw new NoSuchElementException();
816
817 lastReturned = entry;
818 entry = entry.next;
819 currentKey = nextKey;
820 nextKey = null;
821 return lastReturned;
822 }
823
824 public void remove() {
825 if (lastReturned == null)
826 throw new IllegalStateException();
827 if (modCount != expectedModCount)
828 throw new ConcurrentModificationException();
829
830 WeakHashMap.this.remove(currentKey);
831 expectedModCount = modCount;
832 lastReturned = null;
833 currentKey = null;
834 }
835
836 }
837
838 private class ValueIterator extends HashIterator<V> {
839 public V next() {
840 return nextEntry().value;
841 }
842 }
843
844 private class KeyIterator extends HashIterator<K> {
845 public K next() {
846 return nextEntry().getKey();
847 }
848 }
849
850 private class EntryIterator extends HashIterator<Map.Entry<K,V>> {
851 public Map.Entry<K,V> next() {
852 return nextEntry();
853 }
854 }
855
856 // Views
857
858 private transient Set<Map.Entry<K,V>> entrySet = null;
859
860 /**
861 * Returns a {@link Set} view of the keys contained in this map.
862 * The set is backed by the map, so changes to the map are
863 * reflected in the set, and vice-versa. If the map is modified
864 * while an iteration over the set is in progress (except through
865 * the iterator's own <tt>remove</tt> operation), the results of
866 * the iteration are undefined. The set supports element removal,
867 * which removes the corresponding mapping from the map, via the
868 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
869 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
870 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
871 * operations.
872 */
873 public Set<K> keySet() {
874 Set<K> ks = keySet;
875 return (ks != null ? ks : (keySet = new KeySet()));
876 }
877
878 private class KeySet extends AbstractSet<K> {
879 public Iterator<K> iterator() {
880 return new KeyIterator();
881 }
882
883 public int size() {
884 return WeakHashMap.this.size();
885 }
886
887 public boolean contains(Object o) {
888 return containsKey(o);
889 }
890
891 public boolean remove(Object o) {
892 if (containsKey(o)) {
893 WeakHashMap.this.remove(o);
894 return true;
895 }
896 else
897 return false;
898 }
899
900 public void clear() {
901 WeakHashMap.this.clear();
902 }
903
904 public Spliterator<K> spliterator() {
905 return new KeySpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
906 }
907 }
908
909 /**
910 * Returns a {@link Collection} view of the values contained in this map.
911 * The collection is backed by the map, so changes to the map are
912 * reflected in the collection, and vice-versa. If the map is
913 * modified while an iteration over the collection is in progress
914 * (except through the iterator's own <tt>remove</tt> operation),
915 * the results of the iteration are undefined. The collection
916 * supports element removal, which removes the corresponding
917 * mapping from the map, via the <tt>Iterator.remove</tt>,
918 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
919 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
920 * support the <tt>add</tt> or <tt>addAll</tt> operations.
921 */
922 public Collection<V> values() {
923 Collection<V> vs = values;
924 return (vs != null) ? vs : (values = new Values());
925 }
926
927 private class Values extends AbstractCollection<V> {
928 public Iterator<V> iterator() {
929 return new ValueIterator();
930 }
931
932 public int size() {
933 return WeakHashMap.this.size();
934 }
935
936 public boolean contains(Object o) {
937 return containsValue(o);
938 }
939
940 public void clear() {
941 WeakHashMap.this.clear();
942 }
943
944 public Spliterator<V> spliterator() {
945 return new ValueSpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
946 }
947 }
948
949 /**
950 * Returns a {@link Set} view of the mappings contained in this map.
951 * The set is backed by the map, so changes to the map are
952 * reflected in the set, and vice-versa. If the map is modified
953 * while an iteration over the set is in progress (except through
954 * the iterator's own <tt>remove</tt> operation, or through the
955 * <tt>setValue</tt> operation on a map entry returned by the
956 * iterator) the results of the iteration are undefined. The set
957 * supports element removal, which removes the corresponding
958 * mapping from the map, via the <tt>Iterator.remove</tt>,
959 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
960 * <tt>clear</tt> operations. It does not support the
961 * <tt>add</tt> or <tt>addAll</tt> operations.
962 */
963 public Set<Map.Entry<K,V>> entrySet() {
964 Set<Map.Entry<K,V>> es = entrySet;
965 return es != null ? es : (entrySet = new EntrySet());
966 }
967
968 private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
969 public Iterator<Map.Entry<K,V>> iterator() {
970 return new EntryIterator();
971 }
972
973 public boolean contains(Object o) {
974 if (!(o instanceof Map.Entry))
975 return false;
976 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
977 Entry<K,V> candidate = getEntry(e.getKey());
978 return candidate != null && candidate.equals(e);
979 }
980
981 public boolean remove(Object o) {
982 return removeMapping(o);
983 }
984
985 public int size() {
986 return WeakHashMap.this.size();
987 }
988
989 public void clear() {
990 WeakHashMap.this.clear();
991 }
992
993 private List<Map.Entry<K,V>> deepCopy() {
994 List<Map.Entry<K,V>> list = new ArrayList<>(size());
995 for (Map.Entry<K,V> e : this)
996 list.add(new AbstractMap.SimpleEntry<>(e));
997 return list;
998 }
999
1000 public Object[] toArray() {
1001 return deepCopy().toArray();
1002 }
1003
1004 public <T> T[] toArray(T[] a) {
1005 return deepCopy().toArray(a);
1006 }
1007
1008 public Spliterator<Map.Entry<K,V>> spliterator() {
1009 return new EntrySpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
1010 }
1011 }
1012
1013 /**
1014 * Similar form as other hash Spliterators, but skips dead
1015 * elements.
1016 */
1017 static class WeakHashMapSpliterator<K,V> {
1018 final WeakHashMap<K,V> map;
1019 WeakHashMap.Entry<K,V> current; // current node
1020 int index; // current index, modified on advance/split
1021 int fence; // -1 until first use; then one past last index
1022 int est; // size estimate
1023 int expectedModCount; // for comodification checks
1024
1025 WeakHashMapSpliterator(WeakHashMap<K,V> m, int origin,
1026 int fence, int est,
1027 int expectedModCount) {
1028 this.map = m;
1029 this.index = origin;
1030 this.fence = fence;
1031 this.est = est;
1032 this.expectedModCount = expectedModCount;
1033 }
1034
1035 final int getFence() { // initialize fence and size on first use
1036 int hi;
1037 if ((hi = fence) < 0) {
1038 WeakHashMap<K,V> m = map;
1039 est = m.size();
1040 expectedModCount = m.modCount;
1041 hi = fence = m.table.length;
1042 }
1043 return hi;
1044 }
1045
1046 public final long estimateSize() {
1047 getFence(); // force init
1048 return (long) est;
1049 }
1050 }
1051
1052 static final class KeySpliterator<K,V>
1053 extends WeakHashMapSpliterator<K,V>
1054 implements Spliterator<K> {
1055 KeySpliterator(WeakHashMap<K,V> m, int origin, int fence, int est,
1056 int expectedModCount) {
1057 super(m, origin, fence, est, expectedModCount);
1058 }
1059
1060 public KeySpliterator<K,V> trySplit() {
1061 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1062 return (lo >= mid) ? null :
1063 new KeySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
1064 expectedModCount);
1065 }
1066
1067 public void forEachRemaining(Consumer<? super K> action) {
1068 int i, hi, mc;
1069 if (action == null)
1070 throw new NullPointerException();
1071 WeakHashMap<K,V> m = map;
1072 WeakHashMap.Entry<K,V>[] tab = m.table;
1073 if ((hi = fence) < 0) {
1074 mc = expectedModCount = m.modCount;
1075 hi = fence = tab.length;
1076 }
1077 else
1078 mc = expectedModCount;
1079 if (tab.length >= hi && (i = index) >= 0 && i < hi) {
1080 index = hi;
1081 WeakHashMap.Entry<K,V> p = current;
1082 do {
1083 if (p == null)
1084 p = tab[i++];
1085 else {
1086 Object x = p.get();
1087 p = p.next;
1088 if (x != null) {
1089 @SuppressWarnings("unchecked") K k =
1090 (K) WeakHashMap.unmaskNull(x);
1091 action.accept(k);
1092 }
1093 }
1094 } while (p != null || i < hi);
1095 }
1096 if (m.modCount != mc)
1097 throw new ConcurrentModificationException();
1098 }
1099
1100 public boolean tryAdvance(Consumer<? super K> action) {
1101 int hi;
1102 if (action == null)
1103 throw new NullPointerException();
1104 WeakHashMap.Entry<K,V>[] tab = map.table;
1105 if (tab.length >= (hi = getFence()) && index >= 0) {
1106 while (current != null || index < hi) {
1107 if (current == null)
1108 current = tab[index++];
1109 else {
1110 Object x = current.get();
1111 current = current.next;
1112 if (x != null) {
1113 @SuppressWarnings("unchecked") K k =
1114 (K) WeakHashMap.unmaskNull(x);
1115 action.accept(k);
1116 if (map.modCount != expectedModCount)
1117 throw new ConcurrentModificationException();
1118 return true;
1119 }
1120 }
1121 }
1122 }
1123 return false;
1124 }
1125
1126 public int characteristics() {
1127 return Spliterator.DISTINCT;
1128 }
1129 }
1130
1131 static final class ValueSpliterator<K,V>
1132 extends WeakHashMapSpliterator<K,V>
1133 implements Spliterator<V> {
1134 ValueSpliterator(WeakHashMap<K,V> m, int origin, int fence, int est,
1135 int expectedModCount) {
1136 super(m, origin, fence, est, expectedModCount);
1137 }
1138
1139 public ValueSpliterator<K,V> trySplit() {
1140 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1141 return (lo >= mid) ? null :
1142 new ValueSpliterator<K,V>(map, lo, index = mid, est >>>= 1,
1143 expectedModCount);
1144 }
1145
1146 public void forEachRemaining(Consumer<? super V> action) {
1147 int i, hi, mc;
1148 if (action == null)
1149 throw new NullPointerException();
1150 WeakHashMap<K,V> m = map;
1151 WeakHashMap.Entry<K,V>[] tab = m.table;
1152 if ((hi = fence) < 0) {
1153 mc = expectedModCount = m.modCount;
1154 hi = fence = tab.length;
1155 }
1156 else
1157 mc = expectedModCount;
1158 if (tab.length >= hi && (i = index) >= 0 && i < hi) {
1159 index = hi;
1160 WeakHashMap.Entry<K,V> p = current;
1161 do {
1162 if (p == null)
1163 p = tab[i++];
1164 else {
1165 Object x = p.get();
1166 V v = p.value;
1167 p = p.next;
1168 if (x != null)
1169 action.accept(v);
1170 }
1171 } while (p != null || i < hi);
1172 }
1173 if (m.modCount != mc)
1174 throw new ConcurrentModificationException();
1175 }
1176
1177 public boolean tryAdvance(Consumer<? super V> action) {
1178 int hi;
1179 if (action == null)
1180 throw new NullPointerException();
1181 WeakHashMap.Entry<K,V>[] tab = map.table;
1182 if (tab.length >= (hi = getFence()) && index >= 0) {
1183 while (current != null || index < hi) {
1184 if (current == null)
1185 current = tab[index++];
1186 else {
1187 Object x = current.get();
1188 V v = current.value;
1189 current = current.next;
1190 if (x != null) {
1191 action.accept(v);
1192 if (map.modCount != expectedModCount)
1193 throw new ConcurrentModificationException();
1194 return true;
1195 }
1196 }
1197 }
1198 }
1199 return false;
1200 }
1201
1202 public int characteristics() {
1203 return 0;
1204 }
1205 }
1206
1207 static final class EntrySpliterator<K,V>
1208 extends WeakHashMapSpliterator<K,V>
1209 implements Spliterator<Map.Entry<K,V>> {
1210 EntrySpliterator(WeakHashMap<K,V> m, int origin, int fence, int est,
1211 int expectedModCount) {
1212 super(m, origin, fence, est, expectedModCount);
1213 }
1214
1215 public EntrySpliterator<K,V> trySplit() {
1216 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1217 return (lo >= mid) ? null :
1218 new EntrySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
1219 expectedModCount);
1220 }
1221
1222
1223 public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
1224 int i, hi, mc;
1225 if (action == null)
1226 throw new NullPointerException();
1227 WeakHashMap<K,V> m = map;
1228 WeakHashMap.Entry<K,V>[] tab = m.table;
1229 if ((hi = fence) < 0) {
1230 mc = expectedModCount = m.modCount;
1231 hi = fence = tab.length;
1232 }
1233 else
1234 mc = expectedModCount;
1235 if (tab.length >= hi && (i = index) >= 0 && i < hi) {
1236 index = hi;
1237 WeakHashMap.Entry<K,V> p = current;
1238 do {
1239 if (p == null)
1240 p = tab[i++];
1241 else {
1242 Object x = p.get();
1243 V v = p.value;
1244 p = p.next;
1245 if (x != null) {
1246 @SuppressWarnings("unchecked") K k =
1247 (K) WeakHashMap.unmaskNull(x);
1248 action.accept
1249 (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
1250 }
1251 }
1252 } while (p != null || i < hi);
1253 }
1254 if (m.modCount != mc)
1255 throw new ConcurrentModificationException();
1256 }
1257
1258 public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
1259 int hi;
1260 if (action == null)
1261 throw new NullPointerException();
1262 WeakHashMap.Entry<K,V>[] tab = map.table;
1263 if (tab.length >= (hi = getFence()) && index >= 0) {
1264 while (current != null || index < hi) {
1265 if (current == null)
1266 current = tab[index++];
1267 else {
1268 Object x = current.get();
1269 V v = current.value;
1270 current = current.next;
1271 if (x != null) {
1272 @SuppressWarnings("unchecked") K k =
1273 (K) WeakHashMap.unmaskNull(x);
1274 action.accept
1275 (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
1276 if (map.modCount != expectedModCount)
1277 throw new ConcurrentModificationException();
1278 return true;
1279 }
1280 }
1281 }
1282 }
1283 return false;
1284 }
1285
1286 public int characteristics() {
1287 return Spliterator.DISTINCT;
1288 }
1289 }
1290
1291 }