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