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