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