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