1 /* 2 * Copyright (c) 1998, 2013, 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 <tt>Map</tt> interface, with 38 * <em>weak keys</em>. 39 * An entry in a <tt>WeakHashMap</tt> 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 <tt>Map</tt> 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 <tt>HashMap</tt> 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 <tt>WeakHashMap</tt> 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 * <tt>equals</tt> methods test for object identity using the 59 * <tt>==</tt> 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 * <tt>WeakHashMap</tt> 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 <tt>equals</tt> methods are not based upon object identity, such 64 * as <tt>String</tt> instances. With such recreatable key objects, 65 * however, the automatic removal of <tt>WeakHashMap</tt> entries whose 66 * keys have been discarded may prove to be confusing. 67 * 68 * <p> The behavior of the <tt>WeakHashMap</tt> class depends in part upon 69 * the actions of the garbage collector, so several familiar (though not 70 * required) <tt>Map</tt> invariants do not hold for this class. Because 71 * the garbage collector may discard keys at any time, a 72 * <tt>WeakHashMap</tt> may behave as though an unknown thread is silently 73 * removing entries. In particular, even if you synchronize on a 74 * <tt>WeakHashMap</tt> instance and invoke none of its mutator methods, it 75 * is possible for the <tt>size</tt> method to return smaller values over 76 * time, for the <tt>isEmpty</tt> method to return <tt>false</tt> and 77 * then <tt>true</tt>, for the <tt>containsKey</tt> method to return 78 * <tt>true</tt> and later <tt>false</tt> for a given key, for the 79 * <tt>get</tt> method to return a value for a given key but later return 80 * <tt>null</tt>, for the <tt>put</tt> method to return 81 * <tt>null</tt> and the <tt>remove</tt> method to return 82 * <tt>false</tt> 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 <tt>WeakHashMap</tt> 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 * <tt>WeakHashMap</tt> 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 <tt>WeakHashMap</tt> 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 * <tt>WeakReferences</tt> before 102 * inserting, as in: <tt>m.put(key, new WeakReference(value))</tt>, 103 * and then unwrapping upon each <tt>get</tt>. 104 * 105 * <p>The iterators returned by the <tt>iterator</tt> 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 * <tt>remove</tt> 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 <tt>ConcurrentModificationException</tt> 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}/../technotes/guides/collections/index.html"> 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 private static class Holder { 194 static final boolean USE_HASHSEED; 195 196 static { 197 String hashSeedProp = java.security.AccessController.doPrivileged( 198 new sun.security.action.GetPropertyAction( 199 "jdk.map.useRandomSeed")); 200 boolean localBool = (null != hashSeedProp) 201 ? Boolean.parseBoolean(hashSeedProp) : false; 202 USE_HASHSEED = localBool; 203 } 204 } 205 206 /** 207 * A randomizing value associated with this instance that is applied to 208 * hash code of keys to make hash collisions harder to find. 209 * 210 * Non-final so it can be set lazily, but be sure not to set more than once. 211 */ 212 transient int hashSeed; 213 214 /** 215 * Initialize the hashing mask value. 216 */ 217 final void initHashSeed() { 218 if (sun.misc.VM.isBooted() && Holder.USE_HASHSEED) { 219 // Do not set hashSeed more than once! 220 // assert hashSeed == 0; 221 int seed = ThreadLocalRandom.current().nextInt(); 222 hashSeed = (seed != 0) ? seed : 1; 223 } 224 } 225 226 @SuppressWarnings("unchecked") 227 private Entry<K,V>[] newTable(int n) { 228 return (Entry<K,V>[]) new Entry<?,?>[n]; 229 } 230 231 /** 232 * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial 233 * capacity and the given load factor. 234 * 235 * @param initialCapacity The initial capacity of the <tt>WeakHashMap</tt> 236 * @param loadFactor The load factor of the <tt>WeakHashMap</tt> 237 * @throws IllegalArgumentException if the initial capacity is negative, 238 * or if the load factor is nonpositive. 239 */ 240 public WeakHashMap(int initialCapacity, float loadFactor) { 241 if (initialCapacity < 0) 242 throw new IllegalArgumentException("Illegal Initial Capacity: "+ 243 initialCapacity); 244 if (initialCapacity > MAXIMUM_CAPACITY) 245 initialCapacity = MAXIMUM_CAPACITY; 246 247 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 248 throw new IllegalArgumentException("Illegal Load factor: "+ 249 loadFactor); 250 int capacity = 1; 251 while (capacity < initialCapacity) 252 capacity <<= 1; 253 table = newTable(capacity); 254 this.loadFactor = loadFactor; 255 threshold = (int)(capacity * loadFactor); 256 initHashSeed(); 257 } 258 259 /** 260 * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial 261 * capacity and the default load factor (0.75). 262 * 263 * @param initialCapacity The initial capacity of the <tt>WeakHashMap</tt> 264 * @throws IllegalArgumentException if the initial capacity is negative 265 */ 266 public WeakHashMap(int initialCapacity) { 267 this(initialCapacity, DEFAULT_LOAD_FACTOR); 268 } 269 270 /** 271 * Constructs a new, empty <tt>WeakHashMap</tt> with the default initial 272 * capacity (16) and load factor (0.75). 273 */ 274 public WeakHashMap() { 275 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); 276 } 277 278 /** 279 * Constructs a new <tt>WeakHashMap</tt> with the same mappings as the 280 * specified map. The <tt>WeakHashMap</tt> is created with the default 281 * load factor (0.75) and an initial capacity sufficient to hold the 282 * mappings in the specified map. 283 * 284 * @param m the map whose mappings are to be placed in this map 285 * @throws NullPointerException if the specified map is null 286 * @since 1.3 287 */ 288 public WeakHashMap(Map<? extends K, ? extends V> m) { 289 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, 290 DEFAULT_INITIAL_CAPACITY), 291 DEFAULT_LOAD_FACTOR); 292 putAll(m); 293 } 294 295 // internal utilities 296 297 /** 298 * Value representing null keys inside tables. 299 */ 300 private static final Object NULL_KEY = new Object(); 301 302 /** 303 * Use NULL_KEY for key if it is null. 304 */ 305 private static Object maskNull(Object key) { 306 return (key == null) ? NULL_KEY : key; 307 } 308 309 /** 310 * Returns internal representation of null key back to caller as null. 311 */ 312 static Object unmaskNull(Object key) { 313 return (key == NULL_KEY) ? null : key; 314 } 315 316 /** 317 * Checks for equality of non-null reference x and possibly-null y. By 318 * default uses Object.equals. 319 */ 320 private static boolean eq(Object x, Object y) { 321 return x == y || x.equals(y); 322 } 323 324 /** 325 * Retrieve object hash code and applies a supplemental hash function to the 326 * result hash, which defends against poor quality hash functions. This is 327 * critical because HashMap uses power-of-two length hash tables, that 328 * otherwise encounter collisions for hashCodes that do not differ 329 * in lower bits. 330 */ 331 final int hash(Object k) { 332 int h = hashSeed ^ k.hashCode(); 333 334 // This function ensures that hashCodes that differ only by 335 // constant multiples at each bit position have a bounded 336 // number of collisions (approximately 8 at default load factor). 337 h ^= (h >>> 20) ^ (h >>> 12); 338 return h ^ (h >>> 7) ^ (h >>> 4); 339 } 340 341 /** 342 * Returns index for hash code h. 343 */ 344 private static int indexFor(int h, int length) { 345 return h & (length-1); 346 } 347 348 /** 349 * Expunges stale entries from the table. 350 */ 351 private void expungeStaleEntries() { 352 for (Object x; (x = queue.poll()) != null; ) { 353 synchronized (queue) { 354 @SuppressWarnings("unchecked") 355 Entry<K,V> e = (Entry<K,V>) x; 356 int i = indexFor(e.hash, table.length); 357 358 Entry<K,V> prev = table[i]; 359 Entry<K,V> p = prev; 360 while (p != null) { 361 Entry<K,V> next = p.next; 362 if (p == e) { 363 if (prev == e) 364 table[i] = next; 365 else 366 prev.next = next; 367 // Must not null out e.next; 368 // stale entries may be in use by a HashIterator 369 e.value = null; // Help GC 370 size--; 371 break; 372 } 373 prev = p; 374 p = next; 375 } 376 } 377 } 378 } 379 380 /** 381 * Returns the table after first expunging stale entries. 382 */ 383 private Entry<K,V>[] getTable() { 384 expungeStaleEntries(); 385 return table; 386 } 387 388 /** 389 * Returns the number of key-value mappings in this map. 390 * This result is a snapshot, and may not reflect unprocessed 391 * entries that will be removed before next attempted access 392 * because they are no longer referenced. 393 */ 394 public int size() { 395 if (size == 0) 396 return 0; 397 expungeStaleEntries(); 398 return size; 399 } 400 401 /** 402 * Returns <tt>true</tt> if this map contains no key-value mappings. 403 * This result is a snapshot, and may not reflect unprocessed 404 * entries that will be removed before next attempted access 405 * because they are no longer referenced. 406 */ 407 public boolean isEmpty() { 408 return size() == 0; 409 } 410 411 /** 412 * Returns the value to which the specified key is mapped, 413 * or {@code null} if this map contains no mapping for the key. 414 * 415 * <p>More formally, if this map contains a mapping from a key 416 * {@code k} to a value {@code v} such that {@code (key==null ? k==null : 417 * key.equals(k))}, then this method returns {@code v}; otherwise 418 * it returns {@code null}. (There can be at most one such mapping.) 419 * 420 * <p>A return value of {@code null} does not <i>necessarily</i> 421 * indicate that the map contains no mapping for the key; it's also 422 * possible that the map explicitly maps the key to {@code null}. 423 * The {@link #containsKey containsKey} operation may be used to 424 * distinguish these two cases. 425 * 426 * @see #put(Object, Object) 427 */ 428 public V get(Object key) { 429 Object k = maskNull(key); 430 int h = hash(k); 431 Entry<K,V>[] tab = getTable(); 432 int index = indexFor(h, tab.length); 433 Entry<K,V> e = tab[index]; 434 while (e != null) { 435 if (e.hash == h && eq(k, e.get())) 436 return e.value; 437 e = e.next; 438 } 439 return null; 440 } 441 442 /** 443 * Returns <tt>true</tt> if this map contains a mapping for the 444 * specified key. 445 * 446 * @param key The key whose presence in this map is to be tested 447 * @return <tt>true</tt> if there is a mapping for <tt>key</tt>; 448 * <tt>false</tt> otherwise 449 */ 450 public boolean containsKey(Object key) { 451 return getEntry(key) != null; 452 } 453 454 /** 455 * Returns the entry associated with the specified key in this map. 456 * Returns null if the map contains no mapping for this key. 457 */ 458 Entry<K,V> getEntry(Object key) { 459 Object k = maskNull(key); 460 int h = hash(k); 461 Entry<K,V>[] tab = getTable(); 462 int index = indexFor(h, tab.length); 463 Entry<K,V> e = tab[index]; 464 while (e != null && !(e.hash == h && eq(k, e.get()))) 465 e = e.next; 466 return e; 467 } 468 469 /** 470 * Associates the specified value with the specified key in this map. 471 * If the map previously contained a mapping for this key, the old 472 * value is replaced. 473 * 474 * @param key key with which the specified value is to be associated. 475 * @param value value to be associated with the specified key. 476 * @return the previous value associated with <tt>key</tt>, or 477 * <tt>null</tt> if there was no mapping for <tt>key</tt>. 478 * (A <tt>null</tt> return can also indicate that the map 479 * previously associated <tt>null</tt> with <tt>key</tt>.) 480 */ 481 public V put(K key, V value) { 482 Object k = maskNull(key); 483 int h = hash(k); 484 Entry<K,V>[] tab = getTable(); 485 int i = indexFor(h, tab.length); 486 487 for (Entry<K,V> e = tab[i]; e != null; e = e.next) { 488 if (h == e.hash && eq(k, e.get())) { 489 V oldValue = e.value; 490 if (value != oldValue) 491 e.value = value; 492 return oldValue; 493 } 494 } 495 496 modCount++; 497 Entry<K,V> e = tab[i]; 498 tab[i] = new Entry<>(k, value, queue, h, e); 499 if (++size >= threshold) 500 resize(tab.length * 2); 501 return null; 502 } 503 504 /** 505 * Rehashes the contents of this map into a new array with a 506 * larger capacity. This method is called automatically when the 507 * number of keys in this map reaches its threshold. 508 * 509 * If current capacity is MAXIMUM_CAPACITY, this method does not 510 * resize the map, but sets threshold to Integer.MAX_VALUE. 511 * This has the effect of preventing future calls. 512 * 513 * @param newCapacity the new capacity, MUST be a power of two; 514 * must be greater than current capacity unless current 515 * capacity is MAXIMUM_CAPACITY (in which case value 516 * is irrelevant). 517 */ 518 void resize(int newCapacity) { 519 Entry<K,V>[] oldTable = getTable(); 520 int oldCapacity = oldTable.length; 521 if (oldCapacity == MAXIMUM_CAPACITY) { 522 threshold = Integer.MAX_VALUE; 523 return; 524 } 525 526 Entry<K,V>[] newTable = newTable(newCapacity); 527 transfer(oldTable, newTable); 528 table = newTable; 529 530 /* 531 * If ignoring null elements and processing ref queue caused massive 532 * shrinkage, then restore old table. This should be rare, but avoids 533 * unbounded expansion of garbage-filled tables. 534 */ 535 if (size >= threshold / 2) { 536 threshold = (int)(newCapacity * loadFactor); 537 } else { 538 expungeStaleEntries(); 539 transfer(newTable, oldTable); 540 table = oldTable; 541 } 542 } 543 544 /** Transfers all entries from src to dest tables */ 545 private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) { 546 for (int j = 0; j < src.length; ++j) { 547 Entry<K,V> e = src[j]; 548 src[j] = null; 549 while (e != null) { 550 Entry<K,V> next = e.next; 551 Object key = e.get(); 552 if (key == null) { 553 e.next = null; // Help GC 554 e.value = null; // " " 555 size--; 556 } else { 557 int i = indexFor(e.hash, dest.length); 558 e.next = dest[i]; 559 dest[i] = e; 560 } 561 e = next; 562 } 563 } 564 } 565 566 /** 567 * Copies all of the mappings from the specified map to this map. 568 * These mappings will replace any mappings that this map had for any 569 * of the keys currently in the specified map. 570 * 571 * @param m mappings to be stored in this map. 572 * @throws NullPointerException if the specified map is null. 573 */ 574 public void putAll(Map<? extends K, ? extends V> m) { 575 int numKeysToBeAdded = m.size(); 576 if (numKeysToBeAdded == 0) 577 return; 578 579 /* 580 * Expand the map if the map if the number of mappings to be added 581 * is greater than or equal to threshold. This is conservative; the 582 * obvious condition is (m.size() + size) >= threshold, but this 583 * condition could result in a map with twice the appropriate capacity, 584 * if the keys to be added overlap with the keys already in this map. 585 * By using the conservative calculation, we subject ourself 586 * to at most one extra resize. 587 */ 588 if (numKeysToBeAdded > threshold) { 589 int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1); 590 if (targetCapacity > MAXIMUM_CAPACITY) 591 targetCapacity = MAXIMUM_CAPACITY; 592 int newCapacity = table.length; 593 while (newCapacity < targetCapacity) 594 newCapacity <<= 1; 595 if (newCapacity > table.length) 596 resize(newCapacity); 597 } 598 599 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) 600 put(e.getKey(), e.getValue()); 601 } 602 603 /** 604 * Removes the mapping for a key from this weak hash map if it is present. 605 * More formally, if this map contains a mapping from key <tt>k</tt> to 606 * value <tt>v</tt> such that <code>(key==null ? k==null : 607 * key.equals(k))</code>, that mapping is removed. (The map can contain 608 * at most one such mapping.) 609 * 610 * <p>Returns the value to which this map previously associated the key, 611 * or <tt>null</tt> if the map contained no mapping for the key. A 612 * return value of <tt>null</tt> does not <i>necessarily</i> indicate 613 * that the map contained no mapping for the key; it's also possible 614 * that the map explicitly mapped the key to <tt>null</tt>. 615 * 616 * <p>The map will not contain a mapping for the specified key once the 617 * call returns. 618 * 619 * @param key key whose mapping is to be removed from the map 620 * @return the previous value associated with <tt>key</tt>, or 621 * <tt>null</tt> if there was no mapping for <tt>key</tt> 622 */ 623 public V remove(Object key) { 624 Object k = maskNull(key); 625 int h = hash(k); 626 Entry<K,V>[] tab = getTable(); 627 int i = indexFor(h, tab.length); 628 Entry<K,V> prev = tab[i]; 629 Entry<K,V> e = prev; 630 631 while (e != null) { 632 Entry<K,V> next = e.next; 633 if (h == e.hash && eq(k, e.get())) { 634 modCount++; 635 size--; 636 if (prev == e) 637 tab[i] = next; 638 else 639 prev.next = next; 640 return e.value; 641 } 642 prev = e; 643 e = next; 644 } 645 646 return null; 647 } 648 649 /** Special version of remove needed by Entry set */ 650 boolean removeMapping(Object o) { 651 if (!(o instanceof Map.Entry)) 652 return false; 653 Entry<K,V>[] tab = getTable(); 654 Map.Entry<?,?> entry = (Map.Entry<?,?>)o; 655 Object k = maskNull(entry.getKey()); 656 int h = hash(k); 657 int i = indexFor(h, tab.length); 658 Entry<K,V> prev = tab[i]; 659 Entry<K,V> e = prev; 660 661 while (e != null) { 662 Entry<K,V> next = e.next; 663 if (h == e.hash && e.equals(entry)) { 664 modCount++; 665 size--; 666 if (prev == e) 667 tab[i] = next; 668 else 669 prev.next = next; 670 return true; 671 } 672 prev = e; 673 e = next; 674 } 675 676 return false; 677 } 678 679 /** 680 * Removes all of the mappings from this map. 681 * The map will be empty after this call returns. 682 */ 683 public void clear() { 684 // clear out ref queue. We don't need to expunge entries 685 // since table is getting cleared. 686 while (queue.poll() != null) 687 ; 688 689 modCount++; 690 Arrays.fill(table, null); 691 size = 0; 692 693 // Allocation of array may have caused GC, which may have caused 694 // additional entries to go stale. Removing these entries from the 695 // reference queue will make them eligible for reclamation. 696 while (queue.poll() != null) 697 ; 698 } 699 700 /** 701 * Returns <tt>true</tt> if this map maps one or more keys to the 702 * specified value. 703 * 704 * @param value value whose presence in this map is to be tested 705 * @return <tt>true</tt> if this map maps one or more keys to the 706 * specified value 707 */ 708 public boolean containsValue(Object value) { 709 if (value==null) 710 return containsNullValue(); 711 712 Entry<K,V>[] tab = getTable(); 713 for (int i = tab.length; i-- > 0;) 714 for (Entry<K,V> e = tab[i]; e != null; e = e.next) 715 if (value.equals(e.value)) 716 return true; 717 return false; 718 } 719 720 /** 721 * Special-case code for containsValue with null argument 722 */ 723 private boolean containsNullValue() { 724 Entry<K,V>[] tab = getTable(); 725 for (int i = tab.length; i-- > 0;) 726 for (Entry<K,V> e = tab[i]; e != null; e = e.next) 727 if (e.value==null) 728 return true; 729 return false; 730 } 731 732 /** 733 * The entries in this hash table extend WeakReference, using its main ref 734 * field as the key. 735 */ 736 private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> { 737 V value; 738 final int hash; 739 Entry<K,V> next; 740 741 /** 742 * Creates new entry. 743 */ 744 Entry(Object key, V value, 745 ReferenceQueue<Object> queue, 746 int hash, Entry<K,V> next) { 747 super(key, queue); 748 this.value = value; 749 this.hash = hash; 750 this.next = next; 751 } 752 753 @SuppressWarnings("unchecked") 754 public K getKey() { 755 return (K) WeakHashMap.unmaskNull(get()); 756 } 757 758 public V getValue() { 759 return value; 760 } 761 762 public V setValue(V newValue) { 763 V oldValue = value; 764 value = newValue; 765 return oldValue; 766 } 767 768 public boolean equals(Object o) { 769 if (!(o instanceof Map.Entry)) 770 return false; 771 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 772 K k1 = getKey(); 773 Object k2 = e.getKey(); 774 if (k1 == k2 || (k1 != null && k1.equals(k2))) { 775 V v1 = getValue(); 776 Object v2 = e.getValue(); 777 if (v1 == v2 || (v1 != null && v1.equals(v2))) 778 return true; 779 } 780 return false; 781 } 782 783 public int hashCode() { 784 K k = getKey(); 785 V v = getValue(); 786 return ((k==null ? 0 : k.hashCode()) ^ 787 (v==null ? 0 : v.hashCode())); 788 } 789 790 public String toString() { 791 return getKey() + "=" + getValue(); 792 } 793 } 794 795 private abstract class HashIterator<T> implements Iterator<T> { 796 private int index; 797 private Entry<K,V> entry = null; 798 private Entry<K,V> lastReturned = null; 799 private int expectedModCount = modCount; 800 801 /** 802 * Strong reference needed to avoid disappearance of key 803 * between hasNext and next 804 */ 805 private Object nextKey = null; 806 807 /** 808 * Strong reference needed to avoid disappearance of key 809 * between nextEntry() and any use of the entry 810 */ 811 private Object currentKey = null; 812 813 HashIterator() { 814 index = isEmpty() ? 0 : table.length; 815 } 816 817 public boolean hasNext() { 818 Entry<K,V>[] t = table; 819 820 while (nextKey == null) { 821 Entry<K,V> e = entry; 822 int i = index; 823 while (e == null && i > 0) 824 e = t[--i]; 825 entry = e; 826 index = i; 827 if (e == null) { 828 currentKey = null; 829 return false; 830 } 831 nextKey = e.get(); // hold on to key in strong ref 832 if (nextKey == null) 833 entry = entry.next; 834 } 835 return true; 836 } 837 838 /** The common parts of next() across different types of iterators */ 839 protected Entry<K,V> nextEntry() { 840 if (modCount != expectedModCount) 841 throw new ConcurrentModificationException(); 842 if (nextKey == null && !hasNext()) 843 throw new NoSuchElementException(); 844 845 lastReturned = entry; 846 entry = entry.next; 847 currentKey = nextKey; 848 nextKey = null; 849 return lastReturned; 850 } 851 852 public void remove() { 853 if (lastReturned == null) 854 throw new IllegalStateException(); 855 if (modCount != expectedModCount) 856 throw new ConcurrentModificationException(); 857 858 WeakHashMap.this.remove(currentKey); 859 expectedModCount = modCount; 860 lastReturned = null; 861 currentKey = null; 862 } 863 864 } 865 866 private class ValueIterator extends HashIterator<V> { 867 public V next() { 868 return nextEntry().value; 869 } 870 } 871 872 private class KeyIterator extends HashIterator<K> { 873 public K next() { 874 return nextEntry().getKey(); 875 } 876 } 877 878 private class EntryIterator extends HashIterator<Map.Entry<K,V>> { 879 public Map.Entry<K,V> next() { 880 return nextEntry(); 881 } 882 } 883 884 // Views 885 886 private transient Set<Map.Entry<K,V>> entrySet = null; 887 888 /** 889 * Returns a {@link Set} view of the keys contained in this map. 890 * The set is backed by the map, so changes to the map are 891 * reflected in the set, and vice-versa. If the map is modified 892 * while an iteration over the set is in progress (except through 893 * the iterator's own <tt>remove</tt> operation), the results of 894 * the iteration are undefined. The set supports element removal, 895 * which removes the corresponding mapping from the map, via the 896 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, 897 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> 898 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt> 899 * operations. 900 */ 901 public Set<K> keySet() { 902 Set<K> ks = keySet; 903 return (ks != null ? ks : (keySet = new KeySet())); 904 } 905 906 private class KeySet extends AbstractSet<K> { 907 public Iterator<K> iterator() { 908 return new KeyIterator(); 909 } 910 911 public int size() { 912 return WeakHashMap.this.size(); 913 } 914 915 public boolean contains(Object o) { 916 return containsKey(o); 917 } 918 919 public boolean remove(Object o) { 920 if (containsKey(o)) { 921 WeakHashMap.this.remove(o); 922 return true; 923 } 924 else 925 return false; 926 } 927 928 public void clear() { 929 WeakHashMap.this.clear(); 930 } 931 932 public Spliterator<K> spliterator() { 933 return new KeySpliterator<>(WeakHashMap.this, 0, -1, 0, 0); 934 } 935 } 936 937 /** 938 * Returns a {@link Collection} view of the values contained in this map. 939 * The collection is backed by the map, so changes to the map are 940 * reflected in the collection, and vice-versa. If the map is 941 * modified while an iteration over the collection is in progress 942 * (except through the iterator's own <tt>remove</tt> operation), 943 * the results of the iteration are undefined. The collection 944 * supports element removal, which removes the corresponding 945 * mapping from the map, via the <tt>Iterator.remove</tt>, 946 * <tt>Collection.remove</tt>, <tt>removeAll</tt>, 947 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not 948 * support the <tt>add</tt> or <tt>addAll</tt> operations. 949 */ 950 public Collection<V> values() { 951 Collection<V> vs = values; 952 return (vs != null) ? vs : (values = new Values()); 953 } 954 955 private class Values extends AbstractCollection<V> { 956 public Iterator<V> iterator() { 957 return new ValueIterator(); 958 } 959 960 public int size() { 961 return WeakHashMap.this.size(); 962 } 963 964 public boolean contains(Object o) { 965 return containsValue(o); 966 } 967 968 public void clear() { 969 WeakHashMap.this.clear(); 970 } 971 972 public Spliterator<V> spliterator() { 973 return new ValueSpliterator<>(WeakHashMap.this, 0, -1, 0, 0); 974 } 975 } 976 977 /** 978 * Returns a {@link Set} view of the mappings contained in this map. 979 * The set is backed by the map, so changes to the map are 980 * reflected in the set, and vice-versa. If the map is modified 981 * while an iteration over the set is in progress (except through 982 * the iterator's own <tt>remove</tt> operation, or through the 983 * <tt>setValue</tt> operation on a map entry returned by the 984 * iterator) the results of the iteration are undefined. The set 985 * supports element removal, which removes the corresponding 986 * mapping from the map, via the <tt>Iterator.remove</tt>, 987 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and 988 * <tt>clear</tt> operations. It does not support the 989 * <tt>add</tt> or <tt>addAll</tt> operations. 990 */ 991 public Set<Map.Entry<K,V>> entrySet() { 992 Set<Map.Entry<K,V>> es = entrySet; 993 return es != null ? es : (entrySet = new EntrySet()); 994 } 995 996 private class EntrySet extends AbstractSet<Map.Entry<K,V>> { 997 public Iterator<Map.Entry<K,V>> iterator() { 998 return new EntryIterator(); 999 } 1000 1001 public boolean contains(Object o) { 1002 if (!(o instanceof Map.Entry)) 1003 return false; 1004 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 1005 Entry<K,V> candidate = getEntry(e.getKey()); 1006 return candidate != null && candidate.equals(e); 1007 } 1008 1009 public boolean remove(Object o) { 1010 return removeMapping(o); 1011 } 1012 1013 public int size() { 1014 return WeakHashMap.this.size(); 1015 } 1016 1017 public void clear() { 1018 WeakHashMap.this.clear(); 1019 } 1020 1021 private List<Map.Entry<K,V>> deepCopy() { 1022 List<Map.Entry<K,V>> list = new ArrayList<>(size()); 1023 for (Map.Entry<K,V> e : this) 1024 list.add(new AbstractMap.SimpleEntry<>(e)); 1025 return list; 1026 } 1027 1028 public Object[] toArray() { 1029 return deepCopy().toArray(); 1030 } 1031 1032 public <T> T[] toArray(T[] a) { 1033 return deepCopy().toArray(a); 1034 } 1035 1036 public Spliterator<Map.Entry<K,V>> spliterator() { 1037 return new EntrySpliterator<>(WeakHashMap.this, 0, -1, 0, 0); 1038 } 1039 } 1040 1041 @Override 1042 public void forEach(BiConsumer<? super K, ? super V> action) { 1043 Objects.requireNonNull(action); 1044 int expectedModCount = modCount; 1045 1046 Entry<K, V>[] tab = getTable(); 1047 for (Entry<K, V> entry : tab) { 1048 while (entry != null) { 1049 Object key = entry.get(); 1050 if (key != null) { 1051 action.accept((K)WeakHashMap.unmaskNull(key), entry.value); 1052 } 1053 entry = entry.next; 1054 1055 if (expectedModCount != modCount) { 1056 throw new ConcurrentModificationException(); 1057 } 1058 } 1059 } 1060 } 1061 1062 @Override 1063 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 1064 Objects.requireNonNull(function); 1065 int expectedModCount = modCount; 1066 1067 Entry<K, V>[] tab = getTable();; 1068 for (Entry<K, V> entry : tab) { 1069 while (entry != null) { 1070 Object key = entry.get(); 1071 if (key != null) { 1072 entry.value = function.apply((K)WeakHashMap.unmaskNull(key), entry.value); 1073 } 1074 entry = entry.next; 1075 1076 if (expectedModCount != modCount) { 1077 throw new ConcurrentModificationException(); 1078 } 1079 } 1080 } 1081 } 1082 1083 /** 1084 * Similar form as other hash Spliterators, but skips dead 1085 * elements. 1086 */ 1087 static class WeakHashMapSpliterator<K,V> { 1088 final WeakHashMap<K,V> map; 1089 WeakHashMap.Entry<K,V> current; // current node 1090 int index; // current index, modified on advance/split 1091 int fence; // -1 until first use; then one past last index 1092 int est; // size estimate 1093 int expectedModCount; // for comodification checks 1094 1095 WeakHashMapSpliterator(WeakHashMap<K,V> m, int origin, 1096 int fence, int est, 1097 int expectedModCount) { 1098 this.map = m; 1099 this.index = origin; 1100 this.fence = fence; 1101 this.est = est; 1102 this.expectedModCount = expectedModCount; 1103 } 1104 1105 final int getFence() { // initialize fence and size on first use 1106 int hi; 1107 if ((hi = fence) < 0) { 1108 WeakHashMap<K,V> m = map; 1109 est = m.size(); 1110 expectedModCount = m.modCount; 1111 hi = fence = m.table.length; 1112 } 1113 return hi; 1114 } 1115 1116 public final long estimateSize() { 1117 getFence(); // force init 1118 return (long) est; 1119 } 1120 } 1121 1122 static final class KeySpliterator<K,V> 1123 extends WeakHashMapSpliterator<K,V> 1124 implements Spliterator<K> { 1125 KeySpliterator(WeakHashMap<K,V> m, int origin, int fence, int est, 1126 int expectedModCount) { 1127 super(m, origin, fence, est, expectedModCount); 1128 } 1129 1130 public KeySpliterator<K,V> trySplit() { 1131 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; 1132 return (lo >= mid) ? null : 1133 new KeySpliterator<K,V>(map, lo, index = mid, est >>>= 1, 1134 expectedModCount); 1135 } 1136 1137 public void forEachRemaining(Consumer<? super K> action) { 1138 int i, hi, mc; 1139 if (action == null) 1140 throw new NullPointerException(); 1141 WeakHashMap<K,V> m = map; 1142 WeakHashMap.Entry<K,V>[] tab = m.table; 1143 if ((hi = fence) < 0) { 1144 mc = expectedModCount = m.modCount; 1145 hi = fence = tab.length; 1146 } 1147 else 1148 mc = expectedModCount; 1149 if (tab.length >= hi && (i = index) >= 0 && 1150 (i < (index = hi) || current != null)) { 1151 WeakHashMap.Entry<K,V> p = current; 1152 current = null; // exhaust 1153 do { 1154 if (p == null) 1155 p = tab[i++]; 1156 else { 1157 Object x = p.get(); 1158 p = p.next; 1159 if (x != null) { 1160 @SuppressWarnings("unchecked") K k = 1161 (K) WeakHashMap.unmaskNull(x); 1162 action.accept(k); 1163 } 1164 } 1165 } while (p != null || i < hi); 1166 } 1167 if (m.modCount != mc) 1168 throw new ConcurrentModificationException(); 1169 } 1170 1171 public boolean tryAdvance(Consumer<? super K> action) { 1172 int hi; 1173 if (action == null) 1174 throw new NullPointerException(); 1175 WeakHashMap.Entry<K,V>[] tab = map.table; 1176 if (tab.length >= (hi = getFence()) && index >= 0) { 1177 while (current != null || index < hi) { 1178 if (current == null) 1179 current = tab[index++]; 1180 else { 1181 Object x = current.get(); 1182 current = current.next; 1183 if (x != null) { 1184 @SuppressWarnings("unchecked") K k = 1185 (K) WeakHashMap.unmaskNull(x); 1186 action.accept(k); 1187 if (map.modCount != expectedModCount) 1188 throw new ConcurrentModificationException(); 1189 return true; 1190 } 1191 } 1192 } 1193 } 1194 return false; 1195 } 1196 1197 public int characteristics() { 1198 return Spliterator.DISTINCT; 1199 } 1200 } 1201 1202 static final class ValueSpliterator<K,V> 1203 extends WeakHashMapSpliterator<K,V> 1204 implements Spliterator<V> { 1205 ValueSpliterator(WeakHashMap<K,V> m, int origin, int fence, int est, 1206 int expectedModCount) { 1207 super(m, origin, fence, est, expectedModCount); 1208 } 1209 1210 public ValueSpliterator<K,V> trySplit() { 1211 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; 1212 return (lo >= mid) ? null : 1213 new ValueSpliterator<K,V>(map, lo, index = mid, est >>>= 1, 1214 expectedModCount); 1215 } 1216 1217 public void forEachRemaining(Consumer<? super V> action) { 1218 int i, hi, mc; 1219 if (action == null) 1220 throw new NullPointerException(); 1221 WeakHashMap<K,V> m = map; 1222 WeakHashMap.Entry<K,V>[] tab = m.table; 1223 if ((hi = fence) < 0) { 1224 mc = expectedModCount = m.modCount; 1225 hi = fence = tab.length; 1226 } 1227 else 1228 mc = expectedModCount; 1229 if (tab.length >= hi && (i = index) >= 0 && 1230 (i < (index = hi) || current != null)) { 1231 WeakHashMap.Entry<K,V> p = current; 1232 current = null; // exhaust 1233 do { 1234 if (p == null) 1235 p = tab[i++]; 1236 else { 1237 Object x = p.get(); 1238 V v = p.value; 1239 p = p.next; 1240 if (x != null) 1241 action.accept(v); 1242 } 1243 } while (p != null || i < hi); 1244 } 1245 if (m.modCount != mc) 1246 throw new ConcurrentModificationException(); 1247 } 1248 1249 public boolean tryAdvance(Consumer<? super V> action) { 1250 int hi; 1251 if (action == null) 1252 throw new NullPointerException(); 1253 WeakHashMap.Entry<K,V>[] tab = map.table; 1254 if (tab.length >= (hi = getFence()) && index >= 0) { 1255 while (current != null || index < hi) { 1256 if (current == null) 1257 current = tab[index++]; 1258 else { 1259 Object x = current.get(); 1260 V v = current.value; 1261 current = current.next; 1262 if (x != null) { 1263 action.accept(v); 1264 if (map.modCount != expectedModCount) 1265 throw new ConcurrentModificationException(); 1266 return true; 1267 } 1268 } 1269 } 1270 } 1271 return false; 1272 } 1273 1274 public int characteristics() { 1275 return 0; 1276 } 1277 } 1278 1279 static final class EntrySpliterator<K,V> 1280 extends WeakHashMapSpliterator<K,V> 1281 implements Spliterator<Map.Entry<K,V>> { 1282 EntrySpliterator(WeakHashMap<K,V> m, int origin, int fence, int est, 1283 int expectedModCount) { 1284 super(m, origin, fence, est, expectedModCount); 1285 } 1286 1287 public EntrySpliterator<K,V> trySplit() { 1288 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; 1289 return (lo >= mid) ? null : 1290 new EntrySpliterator<K,V>(map, lo, index = mid, est >>>= 1, 1291 expectedModCount); 1292 } 1293 1294 1295 public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) { 1296 int i, hi, mc; 1297 if (action == null) 1298 throw new NullPointerException(); 1299 WeakHashMap<K,V> m = map; 1300 WeakHashMap.Entry<K,V>[] tab = m.table; 1301 if ((hi = fence) < 0) { 1302 mc = expectedModCount = m.modCount; 1303 hi = fence = tab.length; 1304 } 1305 else 1306 mc = expectedModCount; 1307 if (tab.length >= hi && (i = index) >= 0 && 1308 (i < (index = hi) || current != null)) { 1309 WeakHashMap.Entry<K,V> p = current; 1310 current = null; // exhaust 1311 do { 1312 if (p == null) 1313 p = tab[i++]; 1314 else { 1315 Object x = p.get(); 1316 V v = p.value; 1317 p = p.next; 1318 if (x != null) { 1319 @SuppressWarnings("unchecked") K k = 1320 (K) WeakHashMap.unmaskNull(x); 1321 action.accept 1322 (new AbstractMap.SimpleImmutableEntry<K,V>(k, v)); 1323 } 1324 } 1325 } while (p != null || i < hi); 1326 } 1327 if (m.modCount != mc) 1328 throw new ConcurrentModificationException(); 1329 } 1330 1331 public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) { 1332 int hi; 1333 if (action == null) 1334 throw new NullPointerException(); 1335 WeakHashMap.Entry<K,V>[] tab = map.table; 1336 if (tab.length >= (hi = getFence()) && index >= 0) { 1337 while (current != null || index < hi) { 1338 if (current == null) 1339 current = tab[index++]; 1340 else { 1341 Object x = current.get(); 1342 V v = current.value; 1343 current = current.next; 1344 if (x != null) { 1345 @SuppressWarnings("unchecked") K k = 1346 (K) WeakHashMap.unmaskNull(x); 1347 action.accept 1348 (new AbstractMap.SimpleImmutableEntry<K,V>(k, v)); 1349 if (map.modCount != expectedModCount) 1350 throw new ConcurrentModificationException(); 1351 return true; 1352 } 1353 } 1354 } 1355 } 1356 return false; 1357 } 1358 1359 public int characteristics() { 1360 return Spliterator.DISTINCT; 1361 } 1362 } 1363 1364 }