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") newTable(int n)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 */ WeakHashMap(int initialCapacity, float loadFactor)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 */ WeakHashMap(int initialCapacity)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 */ WeakHashMap()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 */ WeakHashMap(Map<? extends K, ? extends V> m)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 */ maskNull(Object key)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 */ unmaskNull(Object key)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 */ eq(Object x, Object y)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 */ hash(Object k)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 */ indexFor(int h, int length)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 */ expungeStaleEntries()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 */ getTable()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 */ size()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 */ isEmpty()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 */ get(Object key)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 */ containsKey(Object key)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 */ getEntry(Object key)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 */ put(K key, V value)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 */ resize(int newCapacity)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 */ transfer(Entry<K,V>[] src, Entry<K,V>[] dest)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 */ putAll(Map<? extends K, ? extends V> m)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 */ remove(Object key)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 */ removeMapping(Object o)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 */ clear()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 */ containsValue(Object value)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 */ containsNullValue()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 */ Entry(Object key, V value, ReferenceQueue<Object> queue, int hash, Entry<K,V> next)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") getKey()721 public K getKey() { 722 return (K) WeakHashMap.unmaskNull(get()); 723 } 724 getValue()725 public V getValue() { 726 return value; 727 } 728 setValue(V newValue)729 public V setValue(V newValue) { 730 V oldValue = value; 731 value = newValue; 732 return oldValue; 733 } 734 equals(Object o)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 hashCode()750 public int hashCode() { 751 K k = getKey(); 752 V v = getValue(); 753 return Objects.hashCode(k) ^ Objects.hashCode(v); 754 } 755 toString()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 HashIterator()779 HashIterator() { 780 index = isEmpty() ? 0 : table.length; 781 } 782 hasNext()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 */ nextEntry()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 remove()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> { next()833 public V next() { 834 return nextEntry().value; 835 } 836 } 837 838 private class KeyIterator extends HashIterator<K> { next()839 public K next() { 840 return nextEntry().getKey(); 841 } 842 } 843 844 private class EntryIterator extends HashIterator<Map.Entry<K,V>> { next()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 */ keySet()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> { iterator()877 public Iterator<K> iterator() { 878 return new KeyIterator(); 879 } 880 size()881 public int size() { 882 return WeakHashMap.this.size(); 883 } 884 contains(Object o)885 public boolean contains(Object o) { 886 return containsKey(o); 887 } 888 remove(Object o)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 clear()898 public void clear() { 899 WeakHashMap.this.clear(); 900 } 901 spliterator()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 */ values()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> { iterator()930 public Iterator<V> iterator() { 931 return new ValueIterator(); 932 } 933 size()934 public int size() { 935 return WeakHashMap.this.size(); 936 } 937 contains(Object o)938 public boolean contains(Object o) { 939 return containsValue(o); 940 } 941 clear()942 public void clear() { 943 WeakHashMap.this.clear(); 944 } 945 spliterator()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 */ entrySet()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>> { iterator()971 public Iterator<Map.Entry<K,V>> iterator() { 972 return new EntryIterator(); 973 } 974 contains(Object o)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 remove(Object o)983 public boolean remove(Object o) { 984 return removeMapping(o); 985 } 986 size()987 public int size() { 988 return WeakHashMap.this.size(); 989 } 990 clear()991 public void clear() { 992 WeakHashMap.this.clear(); 993 } 994 deepCopy()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 toArray()1002 public Object[] toArray() { 1003 return deepCopy().toArray(); 1004 } 1005 toArray(T[] a)1006 public <T> T[] toArray(T[] a) { 1007 return deepCopy().toArray(a); 1008 } 1009 spliterator()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 forEach(BiConsumer<? super K, ? super V> action)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 replaceAll(BiFunction<? super K, ? super V, ? extends V> function)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 WeakHashMapSpliterator(WeakHashMap<K,V> m, int origin, int fence, int est, int expectedModCount)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 getFence()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 estimateSize()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> { KeySpliterator(WeakHashMap<K,V> m, int origin, int fence, int est, int expectedModCount)1101 KeySpliterator(WeakHashMap<K,V> m, int origin, int fence, int est, 1102 int expectedModCount) { 1103 super(m, origin, fence, est, expectedModCount); 1104 } 1105 trySplit()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 forEachRemaining(Consumer<? super K> action)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 tryAdvance(Consumer<? super K> action)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 characteristics()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> { ValueSpliterator(WeakHashMap<K,V> m, int origin, int fence, int est, int expectedModCount)1181 ValueSpliterator(WeakHashMap<K,V> m, int origin, int fence, int est, 1182 int expectedModCount) { 1183 super(m, origin, fence, est, expectedModCount); 1184 } 1185 trySplit()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 forEachRemaining(Consumer<? super V> action)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 tryAdvance(Consumer<? super V> action)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 characteristics()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>> { EntrySpliterator(WeakHashMap<K,V> m, int origin, int fence, int est, int expectedModCount)1258 EntrySpliterator(WeakHashMap<K,V> m, int origin, int fence, int est, 1259 int expectedModCount) { 1260 super(m, origin, fence, est, expectedModCount); 1261 } 1262 trySplit()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 forEachRemaining(Consumer<? super Map.Entry<K, V>> action)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 tryAdvance(Consumer<? super Map.Entry<K,V>> action)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 characteristics()1335 public int characteristics() { 1336 return Spliterator.DISTINCT; 1337 } 1338 } 1339 1340 } 1341