| Frames | No Frames |
1: /* WeakIdentityHashMap -- an identity hashtable that keeps only weak references 2: to its keys, allowing the virtual machine to reclaim them 3: Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2006 Free Software Foundation, Inc. 4: 5: This file is part of GNU Classpath. 6: 7: GNU Classpath is free software; you can redistribute it and/or modify 8: it under the terms of the GNU General Public License as published by 9: the Free Software Foundation; either version 2, or (at your option) 10: any later version. 11: 12: GNU Classpath is distributed in the hope that it will be useful, but 13: WITHOUT ANY WARRANTY; without even the implied warranty of 14: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15: General Public License for more details. 16: 17: You should have received a copy of the GNU General Public License 18: along with GNU Classpath; see the file COPYING. If not, write to the 19: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 20: 02110-1301 USA. 21: 22: Linking this library statically or dynamically with other modules is 23: making a combined work based on this library. Thus, the terms and 24: conditions of the GNU General Public License cover the whole 25: combination. 26: 27: As a special exception, the copyright holders of this library give you 28: permission to link this library with independent modules to produce an 29: executable, regardless of the license terms of these independent 30: modules, and to copy and distribute the resulting executable under 31: terms of your choice, provided that you also meet, for each linked 32: independent module, the terms and conditions of the license of that 33: module. An independent module is a module which is not derived from 34: or based on this library. If you modify this library, you may extend 35: this exception to your version of the library, but you are not 36: obligated to do so. If you do not wish to do so, delete this 37: exception statement from your version. */ 38: 39: 40: package gnu.java.util; 41: 42: import java.lang.ref.ReferenceQueue; 43: import java.lang.ref.WeakReference; 44: import java.util.AbstractMap; 45: import java.util.AbstractSet; 46: import java.util.Collection; 47: import java.util.ConcurrentModificationException; 48: import java.util.Iterator; 49: import java.util.Map; 50: import java.util.NoSuchElementException; 51: import java.util.Set; 52: 53: /** 54: * A weak hash map has only weak references to the key. This means that it 55: * allows the key to be garbage collected if it is not used otherwise. If 56: * this happens, the entry will eventually disappear from the map, 57: * asynchronously. 58: * 59: * <p>Other strange behaviors to be aware of: The size of this map may 60: * spontaneously shrink (even if you use a synchronized map and synchronize 61: * it); it behaves as if another thread removes entries from this table 62: * without synchronization. The entry set returned by <code>entrySet</code> 63: * has similar phenomenons: The size may spontaneously shrink, or an 64: * entry, that was in the set before, suddenly disappears. 65: * 66: * <p>A weak hash map is not meant for caches; use a normal map, with 67: * soft references as values instead, or try {@link LinkedHashMap}. 68: * 69: * <p>The weak hash map supports null values and null keys. The null key 70: * is never deleted from the map (except explictly of course). The 71: * performance of the methods are similar to that of a hash map. 72: * 73: * <p>The value objects are strongly referenced by this table. So if a 74: * value object maintains a strong reference to the key (either direct 75: * or indirect) the key will never be removed from this map. According 76: * to Sun, this problem may be fixed in a future release. It is not 77: * possible to do it with the jdk 1.2 reference model, though. 78: * 79: * @author Jochen Hoenicke 80: * @author Eric Blake (ebb9@email.byu.edu) 81: * @author Jeroen Frijters 82: * 83: * @see HashMap 84: * @see WeakReference 85: * @see WeakHashMap 86: * @see IdentityHashMap 87: * @see LinkedHashMap 88: */ 89: public class WeakIdentityHashMap extends AbstractMap implements Map 90: { 91: /** 92: * The default capacity for an instance of HashMap. 93: * Sun's documentation mildly suggests that this (11) is the correct 94: * value. 95: */ 96: private static final int DEFAULT_CAPACITY = 11; 97: 98: /** 99: * The default load factor of a HashMap. 100: */ 101: private static final float DEFAULT_LOAD_FACTOR = 0.75F; 102: 103: /** 104: * This is used instead of the key value <i>null</i>. It is needed 105: * to distinguish between an null key and a removed key. 106: */ 107: // Package visible for use by nested classes. 108: static final Object NULL_KEY = new Object(); 109: 110: /** 111: * The reference queue where our buckets (which are WeakReferences) are 112: * registered to. 113: */ 114: private final ReferenceQueue queue; 115: 116: /** 117: * The number of entries in this hash map. 118: */ 119: // Package visible for use by nested classes. 120: int size; 121: 122: /** 123: * The load factor of this WeakIdentityHashMap. This is the maximum ratio of 124: * size versus number of buckets. If size grows the number of buckets 125: * must grow, too. 126: */ 127: private float loadFactor; 128: 129: /** 130: * The rounded product of the capacity (i.e. number of buckets) and 131: * the load factor. When the number of elements exceeds the 132: * threshold, the HashMap calls <code>rehash()</code>. 133: */ 134: private int threshold; 135: 136: /** 137: * The number of structural modifications. This is used by 138: * iterators, to see if they should fail. This doesn't count 139: * the silent key removals, when a weak reference is cleared 140: * by the garbage collection. Instead the iterators must make 141: * sure to have strong references to the entries they rely on. 142: */ 143: // Package visible for use by nested classes. 144: int modCount; 145: 146: /** 147: * The entry set. There is only one instance per hashmap, namely 148: * theEntrySet. Note that the entry set may silently shrink, just 149: * like the WeakIdentityHashMap. 150: */ 151: private final class WeakEntrySet extends AbstractSet 152: { 153: /** 154: * Non-private constructor to reduce bytecode emitted. 155: */ 156: WeakEntrySet() 157: { 158: } 159: 160: /** 161: * Returns the size of this set. 162: * 163: * @return the set size 164: */ 165: public int size() 166: { 167: return size; 168: } 169: 170: /** 171: * Returns an iterator for all entries. 172: * 173: * @return an Entry iterator 174: */ 175: public Iterator iterator() 176: { 177: return new Iterator() 178: { 179: /** 180: * The entry that was returned by the last 181: * <code>next()</code> call. This is also the entry whose 182: * bucket should be removed by the <code>remove</code> call. <br> 183: * 184: * It is null, if the <code>next</code> method wasn't 185: * called yet, or if the entry was already removed. <br> 186: * 187: * Remembering this entry here will also prevent it from 188: * being removed under us, since the entry strongly refers 189: * to the key. 190: */ 191: WeakBucket.WeakEntry lastEntry; 192: 193: /** 194: * The entry that will be returned by the next 195: * <code>next()</code> call. It is <code>null</code> if there 196: * is no further entry. <br> 197: * 198: * Remembering this entry here will also prevent it from 199: * being removed under us, since the entry strongly refers 200: * to the key. 201: */ 202: WeakBucket.WeakEntry nextEntry = findNext(null); 203: 204: /** 205: * The known number of modification to the list, if it differs 206: * from the real number, we throw an exception. 207: */ 208: int knownMod = modCount; 209: 210: /** 211: * Check the known number of modification to the number of 212: * modifications of the table. If it differs from the real 213: * number, we throw an exception. 214: * @throws ConcurrentModificationException if the number 215: * of modifications doesn't match. 216: */ 217: private void checkMod() 218: { 219: // This method will get inlined. 220: cleanQueue(); 221: if (knownMod != modCount) 222: throw new ConcurrentModificationException(knownMod + " != " 223: + modCount); 224: } 225: 226: /** 227: * Get a strong reference to the next entry after 228: * lastBucket. 229: * @param lastEntry the previous bucket, or null if we should 230: * get the first entry. 231: * @return the next entry. 232: */ 233: private WeakBucket.WeakEntry findNext(WeakBucket.WeakEntry lastEntry) 234: { 235: int slot; 236: WeakBucket nextBucket; 237: if (lastEntry != null) 238: { 239: nextBucket = lastEntry.getBucket().next; 240: slot = lastEntry.getBucket().slot; 241: } 242: else 243: { 244: nextBucket = buckets[0]; 245: slot = 0; 246: } 247: 248: while (true) 249: { 250: while (nextBucket != null) 251: { 252: WeakBucket.WeakEntry entry = nextBucket.getEntry(); 253: if (entry != null) 254: // This is the next entry. 255: return entry; 256: 257: // Entry was cleared, try next. 258: nextBucket = nextBucket.next; 259: } 260: 261: slot++; 262: if (slot == buckets.length) 263: // No more buckets, we are through. 264: return null; 265: 266: nextBucket = buckets[slot]; 267: } 268: } 269: 270: /** 271: * Checks if there are more entries. 272: * @return true, iff there are more elements. 273: * @throws ConcurrentModificationException if the hash map was 274: * modified. 275: */ 276: public boolean hasNext() 277: { 278: checkMod(); 279: return nextEntry != null; 280: } 281: 282: /** 283: * Returns the next entry. 284: * @return the next entry. 285: * @throws ConcurrentModificationException if the hash map was 286: * modified. 287: * @throws NoSuchElementException if there is no entry. 288: */ 289: public Object next() 290: { 291: checkMod(); 292: if (nextEntry == null) 293: throw new NoSuchElementException(); 294: lastEntry = nextEntry; 295: nextEntry = findNext(lastEntry); 296: return lastEntry; 297: } 298: 299: /** 300: * Removes the last returned entry from this set. This will 301: * also remove the bucket of the underlying weak hash map. 302: * @throws ConcurrentModificationException if the hash map was 303: * modified. 304: * @throws IllegalStateException if <code>next()</code> was 305: * never called or the element was already removed. 306: */ 307: public void remove() 308: { 309: checkMod(); 310: if (lastEntry == null) 311: throw new IllegalStateException(); 312: modCount++; 313: internalRemove(lastEntry.getBucket()); 314: lastEntry = null; 315: knownMod++; 316: } 317: }; 318: } 319: } 320: 321: /** 322: * A bucket is a weak reference to the key, that contains a strong 323: * reference to the value, a pointer to the next bucket and its slot 324: * number. <br> 325: * 326: * It would be cleaner to have a WeakReference as field, instead of 327: * extending it, but if a weak reference gets cleared, we only get 328: * the weak reference (by queue.poll) and wouldn't know where to 329: * look for this reference in the hashtable, to remove that entry. 330: * 331: * @author Jochen Hoenicke 332: */ 333: private static class WeakBucket extends WeakReference 334: { 335: /** 336: * The value of this entry. The key is stored in the weak 337: * reference that we extend. 338: */ 339: Object value; 340: 341: /** 342: * The next bucket describing another entry that uses the same 343: * slot. 344: */ 345: WeakBucket next; 346: 347: /** 348: * The slot of this entry. This should be 349: * <code>Math.abs(key.hashCode() % buckets.length)</code>. 350: * 351: * But since the key may be silently removed we have to remember 352: * the slot number. 353: * 354: * If this bucket was removed the slot is -1. This marker will 355: * prevent the bucket from being removed twice. 356: */ 357: int slot; 358: 359: /** 360: * Creates a new bucket for the given key/value pair and the specified 361: * slot. 362: * @param key the key 363: * @param queue the queue the weak reference belongs to 364: * @param value the value 365: * @param slot the slot. This must match the slot where this bucket 366: * will be enqueued. 367: */ 368: public WeakBucket(Object key, ReferenceQueue queue, Object value, 369: int slot) 370: { 371: super(key, queue); 372: this.value = value; 373: this.slot = slot; 374: } 375: 376: /** 377: * This class gives the <code>Entry</code> representation of the 378: * current bucket. It also keeps a strong reference to the 379: * key; bad things may happen otherwise. 380: */ 381: class WeakEntry implements Map.Entry 382: { 383: /** 384: * The strong ref to the key. 385: */ 386: Object key; 387: 388: /** 389: * Creates a new entry for the key. 390: * @param key the key 391: */ 392: public WeakEntry(Object key) 393: { 394: this.key = key; 395: } 396: 397: /** 398: * Returns the underlying bucket. 399: * @return the owning bucket 400: */ 401: public WeakBucket getBucket() 402: { 403: return WeakBucket.this; 404: } 405: 406: /** 407: * Returns the key. 408: * @return the key 409: */ 410: public Object getKey() 411: { 412: return key == NULL_KEY ? null : key; 413: } 414: 415: /** 416: * Returns the value. 417: * @return the value 418: */ 419: public Object getValue() 420: { 421: return value; 422: } 423: 424: /** 425: * This changes the value. This change takes place in 426: * the underlying hash map. 427: * @param newVal the new value 428: * @return the old value 429: */ 430: public Object setValue(Object newVal) 431: { 432: Object oldVal = value; 433: value = newVal; 434: return oldVal; 435: } 436: 437: /** 438: * The hashCode as specified in the Entry interface. 439: * @return the hash code 440: */ 441: public int hashCode() 442: { 443: return System.identityHashCode(key) 444: ^ (value == null ? 0 : value.hashCode()); 445: } 446: 447: /** 448: * The equals method as specified in the Entry interface. 449: * @param o the object to compare to 450: * @return true iff o represents the same key/value pair 451: */ 452: public boolean equals(Object o) 453: { 454: if (o instanceof Map.Entry) 455: { 456: Map.Entry e = (Map.Entry) o; 457: return getKey() == e.getKey() 458: && (value == null ? e.getValue() == null 459: : value.equals(e.getValue())); 460: } 461: return false; 462: } 463: 464: public String toString() 465: { 466: return getKey() + "=" + value; 467: } 468: } 469: 470: /** 471: * This returns the entry stored in this bucket, or null, if the 472: * bucket got cleared in the mean time. 473: * @return the Entry for this bucket, if it exists 474: */ 475: WeakEntry getEntry() 476: { 477: final Object key = this.get(); 478: if (key == null) 479: return null; 480: return new WeakEntry(key); 481: } 482: } 483: 484: /** 485: * The entry set returned by <code>entrySet()</code>. 486: */ 487: private final WeakEntrySet theEntrySet; 488: 489: /** 490: * The hash buckets. These are linked lists. Package visible for use in 491: * nested classes. 492: */ 493: WeakBucket[] buckets; 494: 495: /** 496: * Creates a new weak hash map with default load factor and default 497: * capacity. 498: */ 499: public WeakIdentityHashMap() 500: { 501: this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR); 502: } 503: 504: /** 505: * Creates a new weak hash map with default load factor and the given 506: * capacity. 507: * @param initialCapacity the initial capacity 508: * @throws IllegalArgumentException if initialCapacity is negative 509: */ 510: public WeakIdentityHashMap(int initialCapacity) 511: { 512: this(initialCapacity, DEFAULT_LOAD_FACTOR); 513: } 514: 515: /** 516: * Creates a new weak hash map with the given initial capacity and 517: * load factor. 518: * @param initialCapacity the initial capacity. 519: * @param loadFactor the load factor (see class description of HashMap). 520: * @throws IllegalArgumentException if initialCapacity is negative, or 521: * loadFactor is non-positive 522: */ 523: public WeakIdentityHashMap(int initialCapacity, float loadFactor) 524: { 525: // Check loadFactor for NaN as well. 526: if (initialCapacity < 0 || ! (loadFactor > 0)) 527: throw new IllegalArgumentException(); 528: if (initialCapacity == 0) 529: initialCapacity = 1; 530: this.loadFactor = loadFactor; 531: threshold = (int) (initialCapacity * loadFactor); 532: theEntrySet = new WeakEntrySet(); 533: queue = new ReferenceQueue(); 534: buckets = new WeakBucket[initialCapacity]; 535: } 536: 537: /** 538: * Construct a new WeakIdentityHashMap with the same mappings as the given map. 539: * The WeakIdentityHashMap has a default load factor of 0.75. 540: * 541: * @param m the map to copy 542: * @throws NullPointerException if m is null 543: * @since 1.3 544: */ 545: public WeakIdentityHashMap(Map m) 546: { 547: this(m.size(), DEFAULT_LOAD_FACTOR); 548: putAll(m); 549: } 550: 551: /** 552: * Simply hashes a non-null Object to its array index. 553: * @param key the key to hash 554: * @return its slot number 555: */ 556: private int hash(Object key) 557: { 558: return Math.abs(System.identityHashCode(key) % buckets.length); 559: } 560: 561: /** 562: * Cleans the reference queue. This will poll all references (which 563: * are WeakBuckets) from the queue and remove them from this map. 564: * This will not change modCount, even if it modifies the map. The 565: * iterators have to make sure that nothing bad happens. <br> 566: * 567: * Currently the iterator maintains a strong reference to the key, so 568: * that is no problem. 569: */ 570: // Package visible for use by nested classes. 571: void cleanQueue() 572: { 573: Object bucket = queue.poll(); 574: while (bucket != null) 575: { 576: internalRemove((WeakBucket) bucket); 577: bucket = queue.poll(); 578: } 579: } 580: 581: /** 582: * Rehashes this hashtable. This will be called by the 583: * <code>add()</code> method if the size grows beyond the threshold. 584: * It will grow the bucket size at least by factor two and allocates 585: * new buckets. 586: */ 587: private void rehash() 588: { 589: WeakBucket[] oldBuckets = buckets; 590: int newsize = buckets.length * 2 + 1; // XXX should be prime. 591: threshold = (int) (newsize * loadFactor); 592: buckets = new WeakBucket[newsize]; 593: 594: // Now we have to insert the buckets again. 595: for (int i = 0; i < oldBuckets.length; i++) 596: { 597: WeakBucket bucket = oldBuckets[i]; 598: WeakBucket nextBucket; 599: while (bucket != null) 600: { 601: nextBucket = bucket.next; 602: 603: Object key = bucket.get(); 604: if (key == null) 605: { 606: // This bucket should be removed; it is probably 607: // already on the reference queue. We don't insert it 608: // at all, and mark it as cleared. 609: bucket.slot = -1; 610: size--; 611: } 612: else 613: { 614: // Add this bucket to its new slot. 615: int slot = hash(key); 616: bucket.slot = slot; 617: bucket.next = buckets[slot]; 618: buckets[slot] = bucket; 619: } 620: bucket = nextBucket; 621: } 622: } 623: } 624: 625: /** 626: * Finds the entry corresponding to key. Since it returns an Entry 627: * it will also prevent the key from being removed under us. 628: * @param key the key, may be null 629: * @return The WeakBucket.WeakEntry or null, if the key wasn't found. 630: */ 631: private WeakBucket.WeakEntry internalGet(Object key) 632: { 633: if (key == null) 634: key = NULL_KEY; 635: int slot = hash(key); 636: WeakBucket bucket = buckets[slot]; 637: while (bucket != null) 638: { 639: WeakBucket.WeakEntry entry = bucket.getEntry(); 640: if (entry != null && key == entry.key) 641: return entry; 642: 643: bucket = bucket.next; 644: } 645: return null; 646: } 647: 648: /** 649: * Adds a new key/value pair to the hash map. 650: * @param key the key. This mustn't exists in the map. It may be null. 651: * @param value the value. 652: */ 653: private void internalAdd(Object key, Object value) 654: { 655: if (key == null) 656: key = NULL_KEY; 657: int slot = hash(key); 658: WeakBucket bucket = new WeakBucket(key, queue, value, slot); 659: bucket.next = buckets[slot]; 660: buckets[slot] = bucket; 661: size++; 662: } 663: 664: /** 665: * Removes a bucket from this hash map, if it wasn't removed before 666: * (e.g. one time through rehashing and one time through reference queue). 667: * Package visible for use in nested classes. 668: * 669: * @param bucket the bucket to remove. 670: */ 671: void internalRemove(WeakBucket bucket) 672: { 673: int slot = bucket.slot; 674: if (slot == -1) 675: // This bucket was already removed. 676: return; 677: 678: // Mark the bucket as removed. This is necessary, since the 679: // bucket may be enqueued later by the garbage collection, and 680: // internalRemove will be called a second time. 681: bucket.slot = -1; 682: 683: WeakBucket prev = null; 684: WeakBucket next = buckets[slot]; 685: while (next != bucket) 686: { 687: if (next == null) 688: throw new InternalError("WeakIdentityHashMap in inconsistent state"); 689: prev = next; 690: next = prev.next; 691: } 692: if (prev == null) 693: buckets[slot] = bucket.next; 694: else 695: prev.next = bucket.next; 696: 697: size--; 698: } 699: 700: /** 701: * Returns the size of this hash map. Note that the size() may shrink 702: * spontaneously, if the some of the keys were only weakly reachable. 703: * @return the number of entries in this hash map. 704: */ 705: public int size() 706: { 707: cleanQueue(); 708: return size; 709: } 710: 711: /** 712: * Tells if the map is empty. Note that the result may change 713: * spontanously, if all of the keys were only weakly reachable. 714: * @return true, iff the map is empty. 715: */ 716: public boolean isEmpty() 717: { 718: cleanQueue(); 719: return size == 0; 720: } 721: 722: /** 723: * Tells if the map contains the given key. Note that the result 724: * may change spontanously, if the key was only weakly 725: * reachable. 726: * @param key the key to look for 727: * @return true, iff the map contains an entry for the given key. 728: */ 729: public boolean containsKey(Object key) 730: { 731: cleanQueue(); 732: return internalGet(key) != null; 733: } 734: 735: /** 736: * Gets the value the key is mapped to. 737: * @return the value the key was mapped to. It returns null if 738: * the key wasn't in this map, or if the mapped value was 739: * explicitly set to null. 740: */ 741: public Object get(Object key) 742: { 743: cleanQueue(); 744: WeakBucket.WeakEntry entry = internalGet(key); 745: return entry == null ? null : entry.getValue(); 746: } 747: 748: /** 749: * Adds a new key/value mapping to this map. 750: * @param key the key, may be null 751: * @param value the value, may be null 752: * @return the value the key was mapped to previously. It returns 753: * null if the key wasn't in this map, or if the mapped value 754: * was explicitly set to null. 755: */ 756: public Object put(Object key, Object value) 757: { 758: cleanQueue(); 759: WeakBucket.WeakEntry entry = internalGet(key); 760: if (entry != null) 761: return entry.setValue(value); 762: 763: modCount++; 764: if (size >= threshold) 765: rehash(); 766: 767: internalAdd(key, value); 768: return null; 769: } 770: 771: /** 772: * Removes the key and the corresponding value from this map. 773: * @param key the key. This may be null. 774: * @return the value the key was mapped to previously. It returns 775: * null if the key wasn't in this map, or if the mapped value was 776: * explicitly set to null. 777: */ 778: public Object remove(Object key) 779: { 780: cleanQueue(); 781: WeakBucket.WeakEntry entry = internalGet(key); 782: if (entry == null) 783: return null; 784: 785: modCount++; 786: internalRemove(entry.getBucket()); 787: return entry.getValue(); 788: } 789: 790: /** 791: * Returns a set representation of the entries in this map. This 792: * set will not have strong references to the keys, so they can be 793: * silently removed. The returned set has therefore the same 794: * strange behaviour (shrinking size(), disappearing entries) as 795: * this weak hash map. 796: * @return a set representation of the entries. 797: */ 798: public Set entrySet() 799: { 800: cleanQueue(); 801: return theEntrySet; 802: } 803: 804: /** 805: * Clears all entries from this map. 806: */ 807: public void clear() 808: { 809: super.clear(); 810: } 811: 812: /** 813: * Returns true if the map contains at least one key which points to 814: * the specified object as a value. Note that the result 815: * may change spontanously, if its key was only weakly reachable. 816: * @param value the value to search for 817: * @return true if it is found in the set. 818: */ 819: public boolean containsValue(Object value) 820: { 821: cleanQueue(); 822: return super.containsValue(value); 823: } 824: 825: /** 826: * Returns a set representation of the keys in this map. This 827: * set will not have strong references to the keys, so they can be 828: * silently removed. The returned set has therefore the same 829: * strange behaviour (shrinking size(), disappearing entries) as 830: * this weak hash map. 831: * @return a set representation of the keys. 832: */ 833: public Set keySet() 834: { 835: cleanQueue(); 836: return super.keySet(); 837: } 838: 839: /** 840: * Puts all of the mappings from the given map into this one. If the 841: * key already exists in this map, its value is replaced. 842: * @param m the map to copy in 843: */ 844: public void putAll(Map m) 845: { 846: super.putAll(m); 847: } 848: 849: /** 850: * Returns a collection representation of the values in this map. This 851: * collection will not have strong references to the keys, so mappings 852: * can be silently removed. The returned collection has therefore the same 853: * strange behaviour (shrinking size(), disappearing entries) as 854: * this weak hash map. 855: * @return a collection representation of the values. 856: */ 857: public Collection values() 858: { 859: cleanQueue(); 860: return super.values(); 861: } 862: } // class WeakIdentityHashMap