001 package railo.commons.util.mod; 002 import java.lang.ref.ReferenceQueue; 003 import java.lang.ref.WeakReference; 004 import java.util.ArrayList; 005 import java.util.Arrays; 006 import java.util.Collection; 007 import java.util.ConcurrentModificationException; 008 import java.util.Iterator; 009 import java.util.List; 010 import java.util.Map; 011 import java.util.NoSuchElementException; 012 import java.util.Set; 013 014 import railo.runtime.exp.PageException; 015 016 public class WeakHashMapPro<K,V> 017 extends AbstractMapPro<K,V> 018 implements MapPro<K,V> { 019 020 /** 021 * The default initial capacity -- MUST be a power of two. 022 */ 023 private static final int DEFAULT_INITIAL_CAPACITY = 16; 024 025 /** 026 * The maximum capacity, used if a higher value is implicitly specified 027 * by either of the constructors with arguments. 028 * MUST be a power of two <= 1<<30. 029 */ 030 private static final int MAXIMUM_CAPACITY = 1 << 30; 031 032 /** 033 * The load factor used when none specified in constructor. 034 */ 035 private static final float DEFAULT_LOAD_FACTOR = 0.75f; 036 037 /** 038 * The table, resized as necessary. Length MUST Always be a power of two. 039 */ 040 Entry<K,V>[] table; 041 042 /** 043 * The number of key-value mappings contained in this weak hash map. 044 */ 045 private int size; 046 047 /** 048 * The next size value at which to resize (capacity * load factor). 049 */ 050 private int threshold; 051 052 /** 053 * The load factor for the hash table. 054 */ 055 private final float loadFactor; 056 057 /** 058 * Reference queue for cleared WeakEntries 059 */ 060 private final ReferenceQueue<Object> queue = new ReferenceQueue<Object>(); 061 062 063 int modCount; 064 065 /** 066 * The default threshold of map capacity above which alternative hashing is 067 * used for String keys. Alternative hashing reduces the incidence of 068 * collisions due to weak hash code calculation for String keys. 069 * <p/> 070 * This value may be overridden by defining the system property 071 * {@code jdk.map.althashing.threshold}. A property value of {@code 1} 072 * forces alternative hashing to be used at all times whereas 073 * {@code -1} value ensures that alternative hashing is never used. 074 */ 075 static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE; 076 077 /** 078 * holds values which can't be initialized until after VM is booted. 079 */ 080 private static class Holder { 081 082 /** 083 * Table capacity above which to switch to use alternative hashing. 084 */ 085 static final int ALTERNATIVE_HASHING_THRESHOLD; 086 087 static { 088 String altThreshold = java.security.AccessController.doPrivileged( 089 new sun.security.action.GetPropertyAction( 090 "jdk.map.althashing.threshold")); 091 092 int threshold; 093 try { 094 threshold = (null != altThreshold) 095 ? Integer.parseInt(altThreshold) 096 : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT; 097 098 // disable alternative hashing if -1 099 if (threshold == -1) { 100 threshold = Integer.MAX_VALUE; 101 } 102 103 if (threshold < 0) { 104 throw new IllegalArgumentException("value must be positive integer."); 105 } 106 } catch(IllegalArgumentException failed) { 107 throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed); 108 } 109 ALTERNATIVE_HASHING_THRESHOLD = threshold; 110 } 111 } 112 113 /** 114 * If {@code true} then perform alternate hashing to reduce the incidence of 115 * collisions due to weak hash code calculation. 116 */ 117 transient final boolean useAltHashing=false; 118 119 /** 120 * A randomizing value associated with this instance that is applied to 121 * hash code of keys to make hash collisions harder to find. 122 */ 123 transient final int hashSeed = Hashing.randomHashSeed(this); 124 125 @SuppressWarnings("unchecked") 126 private Entry<K,V>[] newTable(int n) { 127 return new Entry[n]; 128 } 129 130 /** 131 * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial 132 * capacity and the given load factor. 133 * 134 * @param initialCapacity The initial capacity of the <tt>WeakHashMap</tt> 135 * @param loadFactor The load factor of the <tt>WeakHashMap</tt> 136 * @throws IllegalArgumentException if the initial capacity is negative, 137 * or if the load factor is nonpositive. 138 */ 139 public WeakHashMapPro(int initialCapacity, float loadFactor) { 140 if (initialCapacity < 0) 141 throw new IllegalArgumentException("Illegal Initial Capacity: "+ 142 initialCapacity); 143 if (initialCapacity > MAXIMUM_CAPACITY) 144 initialCapacity = MAXIMUM_CAPACITY; 145 146 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 147 throw new IllegalArgumentException("Illegal Load factor: "+ 148 loadFactor); 149 int capacity = 1; 150 while (capacity < initialCapacity) 151 capacity <<= 1; 152 table = newTable(capacity); 153 this.loadFactor = loadFactor; 154 threshold = (int)(capacity * loadFactor); 155 //useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); 156 } 157 158 /** 159 * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial 160 * capacity and the default load factor (0.75). 161 * 162 * @param initialCapacity The initial capacity of the <tt>WeakHashMap</tt> 163 * @throws IllegalArgumentException if the initial capacity is negative 164 */ 165 public WeakHashMapPro(int initialCapacity) { 166 this(initialCapacity, DEFAULT_LOAD_FACTOR); 167 } 168 169 /** 170 * Constructs a new, empty <tt>WeakHashMap</tt> with the default initial 171 * capacity (16) and load factor (0.75). 172 */ 173 public WeakHashMapPro() { 174 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); 175 } 176 177 /** 178 * Constructs a new <tt>WeakHashMap</tt> with the same mappings as the 179 * specified map. The <tt>WeakHashMap</tt> is created with the default 180 * load factor (0.75) and an initial capacity sufficient to hold the 181 * mappings in the specified map. 182 * 183 * @param m the map whose mappings are to be placed in this map 184 * @throws NullPointerException if the specified map is null 185 * @since 1.3 186 */ 187 public WeakHashMapPro(Map<? extends K, ? extends V> m) { 188 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, 189 DEFAULT_INITIAL_CAPACITY), 190 DEFAULT_LOAD_FACTOR); 191 putAll(m); 192 } 193 194 // internal utilities 195 196 /** 197 * Value representing null keys inside tables. 198 */ 199 private static final Object NULL_KEY = new Object(); 200 201 /** 202 * Use NULL_KEY for key if it is null. 203 */ 204 private static Object maskNull(Object key) { 205 return (key == null) ? NULL_KEY : key; 206 } 207 208 /** 209 * Returns internal representation of null key back to caller as null. 210 */ 211 static Object unmaskNull(Object key) { 212 return (key == NULL_KEY) ? null : key; 213 } 214 215 /** 216 * Checks for equality of non-null reference x and possibly-null y. By 217 * default uses Object.equals. 218 */ 219 private static boolean eq(Object x, Object y) { 220 return x == y || x.equals(y); 221 } 222 223 /** 224 * Retrieve object hash code and applies a supplemental hash function to the 225 * result hash, which defends against poor quality hash functions. This is 226 * critical because HashMap uses power-of-two length hash tables, that 227 * otherwise encounter collisions for hashCodes that do not differ 228 * in lower bits. 229 */ 230 int hash(Object k) { 231 232 int h; 233 /*if (useAltHashing) { 234 h = hashSeed; 235 if (k instanceof String) { 236 return Hashing.stringHash32((String) k); 237 } 238 h ^= k.hashCode(); 239 240 } else { 241 h = k.hashCode(); 242 }*/ 243 h = k.hashCode(); 244 245 // This function ensures that hashCodes that differ only by 246 // constant multiples at each bit position have a bounded 247 // number of collisions (approximately 8 at default load factor). 248 h ^= (h >>> 20) ^ (h >>> 12); 249 return h ^ (h >>> 7) ^ (h >>> 4); 250 } 251 252 /** 253 * Returns index for hash code h. 254 */ 255 private static int indexFor(int h, int length) { 256 return h & (length-1); 257 } 258 259 /** 260 * Expunges stale entries from the table. 261 */ 262 private void expungeStaleEntries() { 263 for (Object x; (x = queue.poll()) != null; ) { 264 synchronized (queue) { 265 @SuppressWarnings("unchecked") 266 Entry<K,V> e = (Entry<K,V>) x; 267 int i = indexFor(e.hash, table.length); 268 269 Entry<K,V> prev = table[i]; 270 Entry<K,V> p = prev; 271 while (p != null) { 272 Entry<K,V> next = p.next; 273 if (p == e) { 274 if (prev == e) 275 table[i] = next; 276 else 277 prev.next = next; 278 // Must not null out e.next; 279 // stale entries may be in use by a HashIterator 280 e.value = null; // Help GC 281 size--; 282 break; 283 } 284 prev = p; 285 p = next; 286 } 287 } 288 } 289 } 290 291 /** 292 * Returns the table after first expunging stale entries. 293 */ 294 private Entry<K,V>[] getTable() { 295 expungeStaleEntries(); 296 return table; 297 } 298 299 /** 300 * Returns the number of key-value mappings in this map. 301 * This result is a snapshot, and may not reflect unprocessed 302 * entries that will be removed before next attempted access 303 * because they are no longer referenced. 304 */ 305 public int size() { 306 if (size == 0) 307 return 0; 308 expungeStaleEntries(); 309 return size; 310 } 311 312 /** 313 * Returns <tt>true</tt> if this map contains no key-value mappings. 314 * This result is a snapshot, and may not reflect unprocessed 315 * entries that will be removed before next attempted access 316 * because they are no longer referenced. 317 */ 318 public boolean isEmpty() { 319 return size() == 0; 320 } 321 322 @Override 323 public V get(Object key) { 324 Object k = maskNull(key); 325 int h = hash(k); 326 Entry<K,V>[] tab = getTable(); 327 int index = indexFor(h, tab.length); 328 Entry<K,V> e = tab[index]; 329 while (e != null) { 330 if (e.hash == h && eq(k, e.get())) 331 return e.value; 332 e = e.next; 333 } 334 return null; 335 } 336 337 public V g(K key) throws PageException { 338 Object k = maskNull(key); 339 int h = hash(k); 340 Entry<K,V>[] tab = getTable(); 341 int index = indexFor(h, tab.length); 342 Entry<K,V> e = tab[index]; 343 while (e != null) { 344 if (e.hash == h && eq(k, e.get())) 345 return e.value; 346 e = e.next; 347 } 348 throw invalidKey(this,key,false); 349 } 350 351 public V g(K key, V defaultValue) { 352 Object k = maskNull(key); 353 int h = hash(k); 354 Entry<K,V>[] tab = getTable(); 355 int index = indexFor(h, tab.length); 356 Entry<K,V> e = tab[index]; 357 while (e != null) { 358 if (e.hash == h && eq(k, e.get())) 359 return e.value; 360 e = e.next; 361 } 362 return defaultValue; 363 } 364 365 /** 366 * Returns <tt>true</tt> if this map contains a mapping for the 367 * specified key. 368 * 369 * @param key The key whose presence in this map is to be tested 370 * @return <tt>true</tt> if there is a mapping for <tt>key</tt>; 371 * <tt>false</tt> otherwise 372 */ 373 public boolean containsKey(Object key) { 374 return getEntry(key) != null; 375 } 376 377 /** 378 * Returns the entry associated with the specified key in this map. 379 * Returns null if the map contains no mapping for this key. 380 */ 381 Entry<K,V> getEntry(Object key) { 382 Object k = maskNull(key); 383 int h = hash(k); 384 Entry<K,V>[] tab = getTable(); 385 int index = indexFor(h, tab.length); 386 Entry<K,V> e = tab[index]; 387 while (e != null && !(e.hash == h && eq(k, e.get()))) 388 e = e.next; 389 return e; 390 } 391 392 /** 393 * Associates the specified value with the specified key in this map. 394 * If the map previously contained a mapping for this key, the old 395 * value is replaced. 396 * 397 * @param key key with which the specified value is to be associated. 398 * @param value value to be associated with the specified key. 399 * @return the previous value associated with <tt>key</tt>, or 400 * <tt>null</tt> if there was no mapping for <tt>key</tt>. 401 * (A <tt>null</tt> return can also indicate that the map 402 * previously associated <tt>null</tt> with <tt>key</tt>.) 403 */ 404 public V put(K key, V value) { 405 Object k = maskNull(key); 406 int h = hash(k); 407 Entry<K,V>[] tab = getTable(); 408 int i = indexFor(h, tab.length); 409 410 for (Entry<K,V> e = tab[i]; e != null; e = e.next) { 411 if (h == e.hash && eq(k, e.get())) { 412 V oldValue = e.value; 413 if (value != oldValue) 414 e.value = value; 415 return oldValue; 416 } 417 } 418 419 modCount++; 420 Entry<K,V> e = tab[i]; 421 tab[i] = new Entry<K,V>(k, value, queue, h, e); 422 if (++size >= threshold) 423 resize(tab.length * 2); 424 return null; 425 } 426 427 /** 428 * Rehashes the contents of this map into a new array with a 429 * larger capacity. This method is called automatically when the 430 * number of keys in this map reaches its threshold. 431 * 432 * If current capacity is MAXIMUM_CAPACITY, this method does not 433 * resize the map, but sets threshold to Integer.MAX_VALUE. 434 * This has the effect of preventing future calls. 435 * 436 * @param newCapacity the new capacity, MUST be a power of two; 437 * must be greater than current capacity unless current 438 * capacity is MAXIMUM_CAPACITY (in which case value 439 * is irrelevant). 440 */ 441 void resize(int newCapacity) { 442 Entry<K,V>[] oldTable = getTable(); 443 int oldCapacity = oldTable.length; 444 if (oldCapacity == MAXIMUM_CAPACITY) { 445 threshold = Integer.MAX_VALUE; 446 return; 447 } 448 449 Entry<K,V>[] newTable = newTable(newCapacity); 450 boolean oldAltHashing = useAltHashing; 451 //useAltHashing |= sun.misc.VM.isBooted() && (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); 452 boolean rehash = oldAltHashing ^ useAltHashing; 453 transfer(oldTable, newTable, rehash); 454 table = newTable; 455 456 /* 457 * If ignoring null elements and processing ref queue caused massive 458 * shrinkage, then restore old table. This should be rare, but avoids 459 * unbounded expansion of garbage-filled tables. 460 */ 461 if (size >= threshold / 2) { 462 threshold = (int)(newCapacity * loadFactor); 463 } else { 464 expungeStaleEntries(); 465 transfer(newTable, oldTable, false); 466 table = oldTable; 467 } 468 } 469 470 /** Transfers all entries from src to dest tables */ 471 private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest, boolean rehash) { 472 for (int j = 0; j < src.length; ++j) { 473 Entry<K,V> e = src[j]; 474 src[j] = null; 475 while (e != null) { 476 Entry<K,V> next = e.next; 477 Object key = e.get(); 478 if (key == null) { 479 e.next = null; // Help GC 480 e.value = null; // " " 481 size--; 482 } else { 483 if (rehash) { 484 e.hash = hash(key); 485 } 486 int i = indexFor(e.hash, dest.length); 487 e.next = dest[i]; 488 dest[i] = e; 489 } 490 e = next; 491 } 492 } 493 } 494 495 /** 496 * Copies all of the mappings from the specified map to this map. 497 * These mappings will replace any mappings that this map had for any 498 * of the keys currently in the specified map. 499 * 500 * @param m mappings to be stored in this map. 501 * @throws NullPointerException if the specified map is null. 502 */ 503 public void putAll(Map<? extends K, ? extends V> m) { 504 int numKeysToBeAdded = m.size(); 505 if (numKeysToBeAdded == 0) 506 return; 507 508 /* 509 * Expand the map if the map if the number of mappings to be added 510 * is greater than or equal to threshold. This is conservative; the 511 * obvious condition is (m.size() + size) >= threshold, but this 512 * condition could result in a map with twice the appropriate capacity, 513 * if the keys to be added overlap with the keys already in this map. 514 * By using the conservative calculation, we subject ourself 515 * to at most one extra resize. 516 */ 517 if (numKeysToBeAdded > threshold) { 518 int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1); 519 if (targetCapacity > MAXIMUM_CAPACITY) 520 targetCapacity = MAXIMUM_CAPACITY; 521 int newCapacity = table.length; 522 while (newCapacity < targetCapacity) 523 newCapacity <<= 1; 524 if (newCapacity > table.length) 525 resize(newCapacity); 526 } 527 528 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) 529 put(e.getKey(), e.getValue()); 530 } 531 532 /** 533 * Removes the mapping for a key from this weak hash map if it is present. 534 * More formally, if this map contains a mapping from key <tt>k</tt> to 535 * value <tt>v</tt> such that <code>(key==null ? k==null : 536 * key.equals(k))</code>, that mapping is removed. (The map can contain 537 * at most one such mapping.) 538 * 539 * <p>Returns the value to which this map previously associated the key, 540 * or <tt>null</tt> if the map contained no mapping for the key. A 541 * return value of <tt>null</tt> does not <i>necessarily</i> indicate 542 * that the map contained no mapping for the key; it's also possible 543 * that the map explicitly mapped the key to <tt>null</tt>. 544 * 545 * <p>The map will not contain a mapping for the specified key once the 546 * call returns. 547 * 548 * @param key key whose mapping is to be removed from the map 549 * @return the previous value associated with <tt>key</tt>, or 550 * <tt>null</tt> if there was no mapping for <tt>key</tt> 551 */ 552 public V remove(Object key) { 553 Object k = maskNull(key); 554 int h = hash(k); 555 Entry<K,V>[] tab = getTable(); 556 int i = indexFor(h, tab.length); 557 Entry<K,V> prev = tab[i]; 558 Entry<K,V> e = prev; 559 560 while (e != null) { 561 Entry<K,V> next = e.next; 562 if (h == e.hash && eq(k, e.get())) { 563 modCount++; 564 size--; 565 if (prev == e) 566 tab[i] = next; 567 else 568 prev.next = next; 569 return e.value; 570 } 571 prev = e; 572 e = next; 573 } 574 return null; 575 } 576 577 public V r(K key) throws PageException { 578 Object k = maskNull(key); 579 int h = hash(k); 580 Entry<K,V>[] tab = getTable(); 581 int i = indexFor(h, tab.length); 582 Entry<K,V> prev = tab[i]; 583 Entry<K,V> e = prev; 584 585 while (e != null) { 586 Entry<K,V> next = e.next; 587 if (h == e.hash && eq(k, e.get())) { 588 modCount++; 589 size--; 590 if (prev == e) 591 tab[i] = next; 592 else 593 prev.next = next; 594 return e.value; 595 } 596 prev = e; 597 e = next; 598 } 599 throw invalidKey(this, key, true); 600 } 601 602 public V r(K key, V defaultValue) { 603 Object k = maskNull(key); 604 int h = hash(k); 605 Entry<K,V>[] tab = getTable(); 606 int i = indexFor(h, tab.length); 607 Entry<K,V> prev = tab[i]; 608 Entry<K,V> e = prev; 609 610 while (e != null) { 611 Entry<K,V> next = e.next; 612 if (h == e.hash && eq(k, e.get())) { 613 modCount++; 614 size--; 615 if (prev == e) 616 tab[i] = next; 617 else 618 prev.next = next; 619 return e.value; 620 } 621 prev = e; 622 e = next; 623 } 624 return defaultValue; 625 } 626 627 /** Special version of remove needed by Entry set */ 628 boolean removeMapping(Object o) { 629 if (!(o instanceof Map.Entry)) 630 return false; 631 Entry<K,V>[] tab = getTable(); 632 Map.Entry<?,?> entry = (Map.Entry<?,?>)o; 633 Object k = maskNull(entry.getKey()); 634 int h = hash(k); 635 int i = indexFor(h, tab.length); 636 Entry<K,V> prev = tab[i]; 637 Entry<K,V> e = prev; 638 639 while (e != null) { 640 Entry<K,V> next = e.next; 641 if (h == e.hash && e.equals(entry)) { 642 modCount++; 643 size--; 644 if (prev == e) 645 tab[i] = next; 646 else 647 prev.next = next; 648 return true; 649 } 650 prev = e; 651 e = next; 652 } 653 654 return false; 655 } 656 657 /** 658 * Removes all of the mappings from this map. 659 * The map will be empty after this call returns. 660 */ 661 public void clear() { 662 // clear out ref queue. We don't need to expunge entries 663 // since table is getting cleared. 664 while (queue.poll() != null) 665 ; 666 667 modCount++; 668 Arrays.fill(table, null); 669 size = 0; 670 671 // Allocation of array may have caused GC, which may have caused 672 // additional entries to go stale. Removing these entries from the 673 // reference queue will make them eligible for reclamation. 674 while (queue.poll() != null) 675 ; 676 } 677 678 /** 679 * Returns <tt>true</tt> if this map maps one or more keys to the 680 * specified value. 681 * 682 * @param value value whose presence in this map is to be tested 683 * @return <tt>true</tt> if this map maps one or more keys to the 684 * specified value 685 */ 686 public boolean containsValue(Object value) { 687 if (value==null) 688 return containsNullValue(); 689 690 Entry<K,V>[] tab = getTable(); 691 for (int i = tab.length; i-- > 0;) 692 for (Entry<K,V> e = tab[i]; e != null; e = e.next) 693 if (value.equals(e.value)) 694 return true; 695 return false; 696 } 697 698 /** 699 * Special-case code for containsValue with null argument 700 */ 701 private boolean containsNullValue() { 702 Entry<K,V>[] tab = getTable(); 703 for (int i = tab.length; i-- > 0;) 704 for (Entry<K,V> e = tab[i]; e != null; e = e.next) 705 if (e.value==null) 706 return true; 707 return false; 708 } 709 710 /** 711 * The entries in this hash table extend WeakReference, using its main ref 712 * field as the key. 713 */ 714 private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> { 715 V value; 716 int hash; 717 Entry<K,V> next; 718 719 /** 720 * Creates new entry. 721 */ 722 Entry(Object key, V value, 723 ReferenceQueue<Object> queue, 724 int hash, Entry<K,V> next) { 725 super(key, queue); 726 this.value = value; 727 this.hash = hash; 728 this.next = next; 729 } 730 731 @SuppressWarnings("unchecked") 732 public K getKey() { 733 return (K) WeakHashMapPro.unmaskNull(get()); 734 } 735 736 public V getValue() { 737 return value; 738 } 739 740 public V setValue(V newValue) { 741 V oldValue = value; 742 value = newValue; 743 return oldValue; 744 } 745 746 public boolean equals(Object o) { 747 if (!(o instanceof Map.Entry)) 748 return false; 749 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 750 K k1 = getKey(); 751 Object k2 = e.getKey(); 752 if (k1 == k2 || (k1 != null && k1.equals(k2))) { 753 V v1 = getValue(); 754 Object v2 = e.getValue(); 755 if (v1 == v2 || (v1 != null && v1.equals(v2))) 756 return true; 757 } 758 return false; 759 } 760 761 public int hashCode() { 762 K k = getKey(); 763 V v = getValue(); 764 return ((k==null ? 0 : k.hashCode()) ^ 765 (v==null ? 0 : v.hashCode())); 766 } 767 768 public String toString() { 769 return getKey() + "=" + getValue(); 770 } 771 } 772 773 private abstract class HashIterator<T> implements Iterator<T> { 774 private int index; 775 private Entry<K,V> entry = null; 776 private Entry<K,V> lastReturned = null; 777 private int expectedModCount = modCount; 778 779 /** 780 * Strong reference needed to avoid disappearance of key 781 * between hasNext and next 782 */ 783 private Object nextKey = null; 784 785 /** 786 * Strong reference needed to avoid disappearance of key 787 * between nextEntry() and any use of the entry 788 */ 789 private Object currentKey = null; 790 791 HashIterator() { 792 index = isEmpty() ? 0 : table.length; 793 } 794 795 public boolean hasNext() { 796 Entry<K,V>[] t = table; 797 798 while (nextKey == null) { 799 Entry<K,V> e = entry; 800 int i = index; 801 while (e == null && i > 0) 802 e = t[--i]; 803 entry = e; 804 index = i; 805 if (e == null) { 806 currentKey = null; 807 return false; 808 } 809 nextKey = e.get(); // hold on to key in strong ref 810 if (nextKey == null) 811 entry = entry.next; 812 } 813 return true; 814 } 815 816 /** The common parts of next() across different types of iterators */ 817 protected Entry<K,V> nextEntry() { 818 if (modCount != expectedModCount) 819 throw new ConcurrentModificationException(); 820 if (nextKey == null && !hasNext()) 821 throw new NoSuchElementException(); 822 823 lastReturned = entry; 824 entry = entry.next; 825 currentKey = nextKey; 826 nextKey = null; 827 return lastReturned; 828 } 829 830 public void remove() { 831 if (lastReturned == null) 832 throw new IllegalStateException(); 833 if (modCount != expectedModCount) 834 throw new ConcurrentModificationException(); 835 836 WeakHashMapPro.this.remove(currentKey); 837 expectedModCount = modCount; 838 lastReturned = null; 839 currentKey = null; 840 } 841 842 } 843 844 private class ValueIterator extends HashIterator<V> { 845 public V next() { 846 return nextEntry().value; 847 } 848 } 849 850 private class KeyIterator extends HashIterator<K> { 851 public K next() { 852 return nextEntry().getKey(); 853 } 854 } 855 856 private class EntryIterator extends HashIterator<Map.Entry<K,V>> { 857 public Map.Entry<K,V> next() { 858 return nextEntry(); 859 } 860 } 861 862 // Views 863 864 private transient Set<Map.Entry<K,V>> entrySet = null; 865 866 /** 867 * Returns a {@link Set} view of the keys contained in this map. 868 * The set is backed by the map, so changes to the map are 869 * reflected in the set, and vice-versa. If the map is modified 870 * while an iteration over the set is in progress (except through 871 * the iterator's own <tt>remove</tt> operation), the results of 872 * the iteration are undefined. The set supports element removal, 873 * which removes the corresponding mapping from the map, via the 874 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, 875 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> 876 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt> 877 * operations. 878 */ 879 public Set<K> keySet() { 880 Set<K> ks = keySet; 881 return (ks != null ? ks : (keySet = new KeySet())); 882 } 883 884 private class KeySet extends AbstractSet<K> { 885 public Iterator<K> iterator() { 886 return new KeyIterator(); 887 } 888 889 public int size() { 890 return WeakHashMapPro.this.size(); 891 } 892 893 public boolean contains(Object o) { 894 return containsKey(o); 895 } 896 897 public boolean remove(Object o) { 898 if (containsKey(o)) { 899 WeakHashMapPro.this.remove(o); 900 return true; 901 } 902 return false; 903 } 904 905 public void clear() { 906 WeakHashMapPro.this.clear(); 907 } 908 } 909 910 /** 911 * Returns a {@link Collection} view of the values contained in this map. 912 * The collection is backed by the map, so changes to the map are 913 * reflected in the collection, and vice-versa. If the map is 914 * modified while an iteration over the collection is in progress 915 * (except through the iterator's own <tt>remove</tt> operation), 916 * the results of the iteration are undefined. The collection 917 * supports element removal, which removes the corresponding 918 * mapping from the map, via the <tt>Iterator.remove</tt>, 919 * <tt>Collection.remove</tt>, <tt>removeAll</tt>, 920 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not 921 * support the <tt>add</tt> or <tt>addAll</tt> operations. 922 */ 923 public Collection<V> values() { 924 Collection<V> vs = values; 925 return (vs != null) ? vs : (values = new Values()); 926 } 927 928 private class Values extends AbstractCollection<V> { 929 public Iterator<V> iterator() { 930 return new ValueIterator(); 931 } 932 933 public int size() { 934 return WeakHashMapPro.this.size(); 935 } 936 937 public boolean contains(Object o) { 938 return containsValue(o); 939 } 940 941 public void clear() { 942 WeakHashMapPro.this.clear(); 943 } 944 } 945 946 /** 947 * Returns a {@link Set} view of the mappings contained in this map. 948 * The set is backed by the map, so changes to the map are 949 * reflected in the set, and vice-versa. If the map is modified 950 * while an iteration over the set is in progress (except through 951 * the iterator's own <tt>remove</tt> operation, or through the 952 * <tt>setValue</tt> operation on a map entry returned by the 953 * iterator) the results of the iteration are undefined. The set 954 * supports element removal, which removes the corresponding 955 * mapping from the map, via the <tt>Iterator.remove</tt>, 956 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and 957 * <tt>clear</tt> operations. It does not support the 958 * <tt>add</tt> or <tt>addAll</tt> operations. 959 */ 960 public Set<Map.Entry<K,V>> entrySet() { 961 Set<Map.Entry<K,V>> es = entrySet; 962 return es != null ? es : (entrySet = new EntrySet()); 963 } 964 965 private class EntrySet extends AbstractSet<Map.Entry<K,V>> { 966 public Iterator<Map.Entry<K,V>> iterator() { 967 return new EntryIterator(); 968 } 969 970 public boolean contains(Object o) { 971 if (!(o instanceof Map.Entry)) 972 return false; 973 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 974 Entry<K,V> candidate = getEntry(e.getKey()); 975 return candidate != null && candidate.equals(e); 976 } 977 978 public boolean remove(Object o) { 979 return removeMapping(o); 980 } 981 982 public int size() { 983 return WeakHashMapPro.this.size(); 984 } 985 986 public void clear() { 987 WeakHashMapPro.this.clear(); 988 } 989 990 private List<Map.Entry<K,V>> deepCopy() { 991 List<Map.Entry<K,V>> list = new ArrayList<Map.Entry<K,V>>(size()); 992 for (Map.Entry<K,V> e : this) 993 list.add(new AbstractMapPro.SimpleEntry<K,V>(e)); 994 return list; 995 } 996 997 public Object[] toArray() { 998 return deepCopy().toArray(); 999 } 1000 1001 public <T> T[] toArray(T[] a) { 1002 return deepCopy().toArray(a); 1003 } 1004 } 1005 }