X-Git-Url: https://oss.titaniummirror.com/gitweb?a=blobdiff_plain;f=libjava%2Fjava%2Futil%2FWeakHashMap.java;fp=libjava%2Fjava%2Futil%2FWeakHashMap.java;h=0000000000000000000000000000000000000000;hb=6fed43773c9b0ce596dca5686f37ac3fc0fa11c0;hp=8c55ae0a553a53ef888a40a6f88db411d00ac912;hpb=27b11d56b743098deb193d510b337ba22dc52e5c;p=msp430-gcc.git diff --git a/libjava/java/util/WeakHashMap.java b/libjava/java/util/WeakHashMap.java deleted file mode 100644 index 8c55ae0a..00000000 --- a/libjava/java/util/WeakHashMap.java +++ /dev/null @@ -1,873 +0,0 @@ -/* java.util.WeakHashMap -- a hashtable that keeps only weak references - to its keys, allowing the virtual machine to reclaim them - Copyright (C) 1999, 2000, 2001, 2002 Free Software Foundation, Inc. - -This file is part of GNU Classpath. - -GNU Classpath is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2, or (at your option) -any later version. - -GNU Classpath is distributed in the hope that it will be useful, but -WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -General Public License for more details. - -You should have received a copy of the GNU General Public License -along with GNU Classpath; see the file COPYING. If not, write to the -Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA -02111-1307 USA. - -Linking this library statically or dynamically with other modules is -making a combined work based on this library. Thus, the terms and -conditions of the GNU General Public License cover the whole -combination. - -As a special exception, the copyright holders of this library give you -permission to link this library with independent modules to produce an -executable, regardless of the license terms of these independent -modules, and to copy and distribute the resulting executable under -terms of your choice, provided that you also meet, for each linked -independent module, the terms and conditions of the license of that -module. An independent module is a module which is not derived from -or based on this library. If you modify this library, you may extend -this exception to your version of the library, but you are not -obligated to do so. If you do not wish to do so, delete this -exception statement from your version. */ - - -package java.util; - -import java.lang.ref.WeakReference; -import java.lang.ref.ReferenceQueue; - -/** - * A weak hash map has only weak references to the key. This means - * that it allows the key to be garbage collected if they are not used - * otherwise. If this happens, the weak hash map will eventually - * remove the whole entry from this map.
- * - * A weak hash map makes most sense, if the keys doesn't override the - * equals-method: If there is no other reference to the - * key nobody can ever look up the key in this table and so the entry - * can be removed. This table also works, if the equals - * method is overloaded, e.g. with Strings as keys, but you should be - * prepared that some entries disappear spontaneously.
- * - * You should also be prepared that this hash map behaves very - * strange: The size of this map may spontaneously shrink (even if you - * use a synchronized map and synchronize it); it behaves as if - * another thread removes entries from this table without - * synchronizations. The entry set returned by entrySet - * has similar phenomenons: The size may spontaneously shrink, or an - * entry, that was in the set before, suddenly disappears.
- * - * A weak hash map is not meant for caches; use a normal map, with - * soft references as values instead, or try {@link LinkedHashMap}.
- * - * The weak hash map supports null values and null keys. The null key - * is never deleted from the map (except explictly of course). - * The performance of the methods are similar to that of a hash map.
- * - * The value objects are strongly referenced by this table. So if a - * value object maintains a strong reference to the key (either direct - * or indirect) the key will never be removed from this map. According - * to Sun, this problem may be fixed in a future release. It is not - * possible to do it with the jdk 1.2 reference model, though. - * - * @author Jochen Hoenicke - * @author Eric Blake - * @see HashMap - * @see WeakReference - * @see LinkedHashMap - * @since 1.2 - * @status updated to 1.4 - */ -public class WeakHashMap extends AbstractMap implements Map -{ - /** - * The default capacity for an instance of HashMap. - * Sun's documentation mildly suggests that this (11) is the correct - * value. - */ - private static final int DEFAULT_CAPACITY = 11; - - /** - * The default load factor of a HashMap. - */ - private static final float DEFAULT_LOAD_FACTOR = 0.75F; - - /** - * This is used instead of the key value null. It is needed - * to distinguish between an null key and a removed key. - */ - // Package visible for use by nested classes. - static final Object NULL_KEY = new Object() - { - /** - * Sets the hashCode to 0, since that's what null would map to. - * @return the hash code 0 - */ - public int hashCode() - { - return 0; - } - - /** - * Compares this key to the given object. Normally, an object should - * NEVER compare equal to null, but since we don't publicize NULL_VALUE, - * it saves bytecode to do so here. - * @return true iff o is this or null - */ - public boolean equals(Object o) - { - return null == o || this == o; - } - }; - - /** - * The reference queue where our buckets (which are WeakReferences) are - * registered to. - */ - private final ReferenceQueue queue; - - /** - * The number of entries in this hash map. - */ - // Package visible for use by nested classes. - int size; - - /** - * The load factor of this WeakHashMap. This is the maximum ratio of - * size versus number of buckets. If size grows the number of buckets - * must grow, too. - */ - private float loadFactor; - - /** - * The rounded product of the capacity (i.e. number of buckets) and - * the load factor. When the number of elements exceeds the - * threshold, the HashMap calls 
rehash()
. - */ - private int threshold; - - /** - * The number of structural modifications. This is used by - * iterators, to see if they should fail. This doesn't count - * the silent key removals, when a weak reference is cleared - * by the garbage collection. Instead the iterators must make - * sure to have strong references to the entries they rely on. - */ - // Package visible for use by nested classes. - int modCount; - - /** - * The entry set. There is only one instance per hashmap, namely - * theEntrySet. Note that the entry set may silently shrink, just - * like the WeakHashMap. - */ - private final class WeakEntrySet extends AbstractSet - { - /** - * Non-private constructor to reduce bytecode emitted. - */ - WeakEntrySet() - { - } - - /** - * Returns the size of this set. - * - * @return the set size - */ - public int size() - { - return size; - } - - /** - * Returns an iterator for all entries. - * - * @return an Entry iterator - */ - public Iterator iterator() - { - return new Iterator() - { - /** - * The entry that was returned by the last - * next() call. This is also the entry whose - * bucket should be removed by the remove call.
- * - * It is null, if the next method wasn't - * called yet, or if the entry was already removed.
- * - * Remembering this entry here will also prevent it from - * being removed under us, since the entry strongly refers - * to the key. - */ - WeakBucket.WeakEntry lastEntry; - - /** - * The entry that will be returned by the next - * next() call. It is null if there - * is no further entry.
- * - * Remembering this entry here will also prevent it from - * being removed under us, since the entry strongly refers - * to the key. - */ - WeakBucket.WeakEntry nextEntry = findNext(null); - - /** - * The known number of modification to the list, if it differs - * from the real number, we throw an exception. - */ - int knownMod = modCount; - - /** - * Check the known number of modification to the number of - * modifications of the table. If it differs from the real - * number, we throw an exception. - * @throws ConcurrentModificationException if the number - * of modifications doesn't match. - */ - private void checkMod() - { - // This method will get inlined. - cleanQueue(); - if (knownMod != modCount) - throw new ConcurrentModificationException(); - } - - /** - * Get a strong reference to the next entry after - * lastBucket. - * @param lastEntry the previous bucket, or null if we should - * get the first entry. - * @return the next entry. - */ - private WeakBucket.WeakEntry findNext(WeakBucket.WeakEntry lastEntry) - { - int slot; - WeakBucket nextBucket; - if (lastEntry != null) - { - nextBucket = lastEntry.getBucket().next; - slot = lastEntry.getBucket().slot; - } - else - { - nextBucket = buckets[0]; - slot = 0; - } - - while (true) - { - while (nextBucket != null) - { - WeakBucket.WeakEntry entry = nextBucket.getEntry(); - if (entry != null) - // This is the next entry. - return entry; - - // Entry was cleared, try next. - nextBucket = nextBucket.next; - } - - slot++; - if (slot == buckets.length) - // No more buckets, we are through. - return null; - - nextBucket = buckets[slot]; - } - } - - /** - * Checks if there are more entries. - * @return true, iff there are more elements. - * @throws ConcurrentModificationException if the hash map was - * modified. - */ - public boolean hasNext() - { - checkMod(); - return nextEntry != null; - } - - /** - * Returns the next entry. - * @return the next entry. - * @throws ConcurrentModificationException if the hash map was - * modified. - * @throws NoSuchElementException if there is no entry. - */ - public Object next() - { - checkMod(); - if (nextEntry == null) - throw new NoSuchElementException(); - lastEntry = nextEntry; - nextEntry = findNext(lastEntry); - return lastEntry; - } - - /** - * Removes the last returned entry from this set. This will - * also remove the bucket of the underlying weak hash map. - * @throws ConcurrentModificationException if the hash map was - * modified. - * @throws IllegalStateException if next() was - * never called or the element was already removed. - */ - public void remove() - { - checkMod(); - if (lastEntry == null) - throw new IllegalStateException(); - modCount++; - internalRemove(lastEntry.getBucket()); - lastEntry = null; - knownMod++; - } - }; - } - } - - /** - * A bucket is a weak reference to the key, that contains a strong - * reference to the value, a pointer to the next bucket and its slot - * number.
- * - * It would be cleaner to have a WeakReference as field, instead of - * extending it, but if a weak reference gets cleared, we only get - * the weak reference (by queue.poll) and wouldn't know where to - * look for this reference in the hashtable, to remove that entry. - * - * @author Jochen Hoenicke - */ - private static class WeakBucket extends WeakReference - { - /** - * The value of this entry. The key is stored in the weak - * reference that we extend. - */ - Object value; - - /** - * The next bucket describing another entry that uses the same - * slot. - */ - WeakBucket next; - - /** - * The slot of this entry. This should be - * 
-     *  Math.abs(key.hashCode() % buckets.length)
-     *
- * But since the key may be silently removed we have to remember - * the slot number. - * If this bucket was removed the slot is -1. This marker will - * prevent the bucket from being removed twice. - */ - int slot; - - /** - * Creates a new bucket for the given key/value pair and the specified - * slot. - * @param key the key - * @param queue the queue the weak reference belongs to - * @param value the value - * @param slot the slot. This must match the slot where this bucket - * will be enqueued. - */ - public WeakBucket(Object key, ReferenceQueue queue, Object value, - int slot) - { - super(key, queue); - this.value = value; - this.slot = slot; - } - - /** - * This class gives the Entry representation of the - * current bucket. It also keeps a strong reference to the - * key; bad things may happen otherwise. - */ - class WeakEntry implements Map.Entry - { - /** - * The strong ref to the key. - */ - Object key; - - /** - * Creates a new entry for the key. - * @param key the key - */ - public WeakEntry(Object key) - { - this.key = key; - } - - /** - * Returns the underlying bucket. - * @return the owning bucket - */ - public WeakBucket getBucket() - { - return WeakBucket.this; - } - - /** - * Returns the key. - * @return the key - */ - public Object getKey() - { - return key == NULL_KEY ? null : key; - } - - /** - * Returns the value. - * @return the value - */ - public Object getValue() - { - return value; - } - - /** - * This changes the value. This change takes place in - * the underlying hash map. - * @param newVal the new value - * @return the old value - */ - public Object setValue(Object newVal) - { - Object oldVal = value; - value = newVal; - return oldVal; - } - - /** - * The hashCode as specified in the Entry interface. - * @return the hash code - */ - public int hashCode() - { - return key.hashCode() ^ WeakHashMap.hashCode(value); - } - - /** - * The equals method as specified in the Entry interface. - * @param o the object to compare to - * @return true iff o represents the same key/value pair - */ - public boolean equals(Object o) - { - if (o instanceof Map.Entry) - { - Map.Entry e = (Map.Entry) o; - return key.equals(e.getKey()) - && WeakHashMap.equals(value, e.getValue()); - } - return false; - } - - public String toString() - { - return key + "=" + value; - } - } - - /** - * This returns the entry stored in this bucket, or null, if the - * bucket got cleared in the mean time. - * @return the Entry for this bucket, if it exists - */ - WeakEntry getEntry() - { - final Object key = this.get(); - if (key == null) - return null; - return new WeakEntry(key); - } - } - - /** - * The entry set returned by entrySet(). - */ - private final WeakEntrySet theEntrySet; - - /** - * The hash buckets. These are linked lists. - */ - private WeakBucket[] buckets; - - /** - * Creates a new weak hash map with default load factor and default - * capacity. - */ - public WeakHashMap() - { - this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR); - } - - /** - * Creates a new weak hash map with default load factor and the given - * capacity. - * @param initialCapacity the initial capacity - * @throws IllegalArgumentException if initialCapacity is negative - */ - public WeakHashMap(int initialCapacity) - { - this(initialCapacity, DEFAULT_LOAD_FACTOR); - } - - /** - * Creates a new weak hash map with the given initial capacity and - * load factor. - * @param initialCapacity the initial capacity. - * @param loadFactor the load factor (see class description of HashMap). - * @throws IllegalArgumentException if initialCapacity is negative, or - * loadFactor is non-positive - */ - public WeakHashMap(int initialCapacity, float loadFactor) - { - // Check loadFactor for NaN as well. - if (initialCapacity < 0 || ! (loadFactor > 0)) - throw new IllegalArgumentException(); - this.loadFactor = loadFactor; - threshold = (int) (initialCapacity * loadFactor); - theEntrySet = new WeakEntrySet(); - queue = new ReferenceQueue(); - buckets = new WeakBucket[initialCapacity]; - } - - /** - * Construct a new WeakHashMap with the same mappings as the given map. - * The WeakHashMap has a default load factor of 0.75. - * - * @param m the map to copy - * @throws NullPointerException if m is null - * @since 1.3 - */ - public WeakHashMap(Map m) - { - this(m.size(), DEFAULT_LOAD_FACTOR); - putAll(m); - } - - /** - * Simply hashes a non-null Object to its array index. - * @param key the key to hash - * @return its slot number - */ - private int hash(Object key) - { - return Math.abs(key.hashCode() % buckets.length); - } - - /** - * Cleans the reference queue. This will poll all references (which - * are WeakBuckets) from the queue and remove them from this map. - * This will not change modCount, even if it modifies the map. The - * iterators have to make sure that nothing bad happens.
- * - * Currently the iterator maintains a strong reference to the key, so - * that is no problem. - */ - // Package visible for use by nested classes. - void cleanQueue() - { - Object bucket = queue.poll(); - while (bucket != null) - { - internalRemove((WeakBucket) bucket); - bucket = queue.poll(); - } - } - - /** - * Rehashes this hashtable. This will be called by the - * add() method if the size grows beyond the threshold. - * It will grow the bucket size at least by factor two and allocates - * new buckets. - */ - private void rehash() - { - WeakBucket[] oldBuckets = buckets; - int newsize = buckets.length * 2 + 1; // XXX should be prime. - threshold = (int) (newsize * loadFactor); - buckets = new WeakBucket[newsize]; - - // Now we have to insert the buckets again. - for (int i = 0; i < oldBuckets.length; i++) - { - WeakBucket bucket = oldBuckets[i]; - WeakBucket nextBucket; - while (bucket != null) - { - nextBucket = bucket.next; - - Object key = bucket.get(); - if (key == null) - { - // This bucket should be removed; it is probably - // already on the reference queue. We don't insert it - // at all, and mark it as cleared. - bucket.slot = -1; - size--; - } - else - { - // Add this bucket to its new slot. - int slot = hash(key); - bucket.slot = slot; - bucket.next = buckets[slot]; - buckets[slot] = bucket; - } - bucket = nextBucket; - } - } - } - - /** - * Finds the entry corresponding to key. Since it returns an Entry - * it will also prevent the key from being removed under us. - * @param key the key, may be null - * @return The WeakBucket.WeakEntry or null, if the key wasn't found. - */ - private WeakBucket.WeakEntry internalGet(Object key) - { - if (key == null) - key = NULL_KEY; - int slot = hash(key); - WeakBucket bucket = buckets[slot]; - while (bucket != null) - { - WeakBucket.WeakEntry entry = bucket.getEntry(); - if (entry != null && key.equals(entry.key)) - return entry; - - bucket = bucket.next; - } - return null; - } - - /** - * Adds a new key/value pair to the hash map. - * @param key the key. This mustn't exists in the map. It may be null. - * @param value the value. - */ - private void internalAdd(Object key, Object value) - { - if (key == null) - key = NULL_KEY; - int slot = hash(key); - WeakBucket bucket = new WeakBucket(key, queue, value, slot); - bucket.next = buckets[slot]; - buckets[slot] = bucket; - size++; - } - - /** - * Removes a bucket from this hash map, if it wasn't removed before - * (e.g. one time through rehashing and one time through reference queue) - * @param bucket the bucket to remove. - */ - private void internalRemove(WeakBucket bucket) - { - int slot = bucket.slot; - if (slot == -1) - // This bucket was already removed. - return; - - // Mark the bucket as removed. This is necessary, since the - // bucket may be enqueued later by the garbage collection, and - // internalRemove will be called a second time. - bucket.slot = -1; - if (buckets[slot] == bucket) - buckets[slot] = bucket.next; - else - { - WeakBucket prev = buckets[slot]; - /* This may throw a NullPointerException. It shouldn't but if - * a race condition occurred (two threads removing the same - * bucket at the same time) it may happen.
- * But with race condition many much worse things may happen - * anyway. - */ - while (prev.next != bucket) - prev = prev.next; - prev.next = bucket.next; - } - size--; - } - - /** - * Returns the size of this hash map. Note that the size() may shrink - * spontaneously, if the some of the keys were only weakly reachable. - * @return the number of entries in this hash map. - */ - public int size() - { - cleanQueue(); - return size; - } - - /** - * Tells if the map is empty. Note that the result may change - * spontanously, if all of the keys were only weakly reachable. - * @return true, iff the map is empty. - */ - public boolean isEmpty() - { - cleanQueue(); - return size == 0; - } - - /** - * Tells if the map contains the given key. Note that the result - * may change spontanously, if the key was only weakly - * reachable. - * @param key the key to look for - * @return true, iff the map contains an entry for the given key. - */ - public boolean containsKey(Object key) - { - cleanQueue(); - return internalGet(key) != null; - } - - /** - * Gets the value the key is mapped to. - * @return the value the key was mapped to. It returns null if - * the key wasn't in this map, or if the mapped value was - * explicitly set to null. - */ - public Object get(Object key) - { - cleanQueue(); - WeakBucket.WeakEntry entry = internalGet(key); - return entry == null ? null : entry.getValue(); - } - - /** - * Adds a new key/value mapping to this map. - * @param key the key, may be null - * @param value the value, may be null - * @return the value the key was mapped to previously. It returns - * null if the key wasn't in this map, or if the mapped value - * was explicitly set to null. - */ - public Object put(Object key, Object value) - { - cleanQueue(); - WeakBucket.WeakEntry entry = internalGet(key); - if (entry != null) - return entry.setValue(value); - - modCount++; - if (size >= threshold) - rehash(); - - internalAdd(key, value); - return null; - } - - /** - * Removes the key and the corresponding value from this map. - * @param key the key. This may be null. - * @return the value the key was mapped to previously. It returns - * null if the key wasn't in this map, or if the mapped value was - * explicitly set to null. - */ - public Object remove(Object key) - { - cleanQueue(); - WeakBucket.WeakEntry entry = internalGet(key); - if (entry == null) - return null; - - modCount++; - internalRemove(entry.getBucket()); - return entry.getValue(); - } - - /** - * Returns a set representation of the entries in this map. This - * set will not have strong references to the keys, so they can be - * silently removed. The returned set has therefore the same - * strange behaviour (shrinking size(), disappearing entries) as - * this weak hash map. - * @return a set representation of the entries. - */ - public Set entrySet() - { - cleanQueue(); - return theEntrySet; - } - - /** - * Clears all entries from this map. - */ - public void clear() - { - super.clear(); - } - - /** - * Returns true if the map contains at least one key which points to - * the specified object as a value. Note that the result - * may change spontanously, if its key was only weakly reachable. - * @param value the value to search for - * @return true if it is found in the set. - */ - public boolean containsValue(Object value) - { - cleanQueue(); - return super.containsValue(value); - } - - /** - * Returns a set representation of the keys in this map. This - * set will not have strong references to the keys, so they can be - * silently removed. The returned set has therefore the same - * strange behaviour (shrinking size(), disappearing entries) as - * this weak hash map. - * @return a set representation of the keys. - */ - public Set keySet() - { - cleanQueue(); - return super.keySet(); - } - - /** - * Puts all of the mappings from the given map into this one. If the - * key already exists in this map, its value is replaced. - * @param m the map to copy in - */ - public void putAll(Map m) - { - super.putAll(m); - } - - /** - * Returns a collection representation of the values in this map. This - * collection will not have strong references to the keys, so mappings - * can be silently removed. The returned collection has therefore the same - * strange behaviour (shrinking size(), disappearing entries) as - * this weak hash map. - * @return a collection representation of the values. - */ - public Collection values() - { - cleanQueue(); - return super.values(); - } -}