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