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