1 /* WeakHashMap -- a hashtable that keeps only weak references
2 to its keys, allowing the virtual machine to reclaim them
3 Copyright (C) 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
5 This file is part of GNU Classpath.
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)
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.
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., 59 Temple Place, Suite 330, Boston, MA
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
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. */
42 import java
.lang
.ref
.WeakReference
;
43 import java
.lang
.ref
.ReferenceQueue
;
46 * A weak hash map has only weak references to the key. This means that it
47 * allows the key to be garbage collected if it is not used otherwise. If
48 * this happens, the entry will eventually disappear from the map,
51 * <p>A weak hash map makes most sense when the keys doesn't override the
52 * <code>equals</code> method: If there is no other reference to the
53 * key nobody can ever look up the key in this table and so the entry
54 * can be removed. This table also works when the <code>equals</code>
55 * method is overloaded, such as String keys, but you should be prepared
56 * to deal with some entries disappearing spontaneously.
58 * <p>Other strange behaviors to be aware of: The size of this map may
59 * spontaneously shrink (even if you use a synchronized map and synchronize
60 * it); it behaves as if another thread removes entries from this table
61 * without synchronization. The entry set returned by <code>entrySet</code>
62 * has similar phenomenons: The size may spontaneously shrink, or an
63 * entry, that was in the set before, suddenly disappears.
65 * <p>A weak hash map is not meant for caches; use a normal map, with
66 * soft references as values instead, or try {@link LinkedHashMap}.
68 * <p>The weak hash map supports null values and null keys. The null key
69 * is never deleted from the map (except explictly of course). The
70 * performance of the methods are similar to that of a hash map.
72 * <p>The value objects are strongly referenced by this table. So if a
73 * value object maintains a strong reference to the key (either direct
74 * or indirect) the key will never be removed from this map. According
75 * to Sun, this problem may be fixed in a future release. It is not
76 * possible to do it with the jdk 1.2 reference model, though.
78 * @author Jochen Hoenicke
79 * @author Eric Blake (ebb9@email.byu.edu)
85 * @status updated to 1.4
87 public class WeakHashMap
extends AbstractMap
implements Map
89 // WARNING: WeakHashMap is a CORE class in the bootstrap cycle. See the
90 // comments in vm/reference/java/lang/Runtime for implications of this fact.
93 * The default capacity for an instance of HashMap.
94 * Sun's documentation mildly suggests that this (11) is the correct
97 private static final int DEFAULT_CAPACITY
= 11;
100 * The default load factor of a HashMap.
102 private static final float DEFAULT_LOAD_FACTOR
= 0.75F
;
105 * This is used instead of the key value <i>null</i>. It is needed
106 * to distinguish between an null key and a removed key.
108 // Package visible for use by nested classes.
109 static final Object NULL_KEY
= new Object()
112 * Sets the hashCode to 0, since that's what null would map to.
113 * @return the hash code 0
115 public int hashCode()
121 * Compares this key to the given object. Normally, an object should
122 * NEVER compare equal to null, but since we don't publicize NULL_VALUE,
123 * it saves bytecode to do so here.
124 * @return true iff o is this or null
126 public boolean equals(Object o
)
128 return null == o
|| this == o
;
133 * The reference queue where our buckets (which are WeakReferences) are
136 private final ReferenceQueue queue
;
139 * The number of entries in this hash map.
141 // Package visible for use by nested classes.
145 * The load factor of this WeakHashMap. This is the maximum ratio of
146 * size versus number of buckets. If size grows the number of buckets
149 private float loadFactor
;
152 * The rounded product of the capacity (i.e. number of buckets) and
153 * the load factor. When the number of elements exceeds the
154 * threshold, the HashMap calls <code>rehash()</code>.
156 private int threshold
;
159 * The number of structural modifications. This is used by
160 * iterators, to see if they should fail. This doesn't count
161 * the silent key removals, when a weak reference is cleared
162 * by the garbage collection. Instead the iterators must make
163 * sure to have strong references to the entries they rely on.
165 // Package visible for use by nested classes.
169 * The entry set. There is only one instance per hashmap, namely
170 * theEntrySet. Note that the entry set may silently shrink, just
171 * like the WeakHashMap.
173 private final class WeakEntrySet
extends AbstractSet
176 * Non-private constructor to reduce bytecode emitted.
183 * Returns the size of this set.
185 * @return the set size
193 * Returns an iterator for all entries.
195 * @return an Entry iterator
197 public Iterator
iterator()
199 return new Iterator()
202 * The entry that was returned by the last
203 * <code>next()</code> call. This is also the entry whose
204 * bucket should be removed by the <code>remove</code> call. <br>
206 * It is null, if the <code>next</code> method wasn't
207 * called yet, or if the entry was already removed. <br>
209 * Remembering this entry here will also prevent it from
210 * being removed under us, since the entry strongly refers
213 WeakBucket
.WeakEntry lastEntry
;
216 * The entry that will be returned by the next
217 * <code>next()</code> call. It is <code>null</code> if there
218 * is no further entry. <br>
220 * Remembering this entry here will also prevent it from
221 * being removed under us, since the entry strongly refers
224 WeakBucket
.WeakEntry nextEntry
= findNext(null);
227 * The known number of modification to the list, if it differs
228 * from the real number, we throw an exception.
230 int knownMod
= modCount
;
233 * Check the known number of modification to the number of
234 * modifications of the table. If it differs from the real
235 * number, we throw an exception.
236 * @throws ConcurrentModificationException if the number
237 * of modifications doesn't match.
239 private void checkMod()
241 // This method will get inlined.
243 if (knownMod
!= modCount
)
244 throw new ConcurrentModificationException();
248 * Get a strong reference to the next entry after
250 * @param lastEntry the previous bucket, or null if we should
251 * get the first entry.
252 * @return the next entry.
254 private WeakBucket
.WeakEntry
findNext(WeakBucket
.WeakEntry lastEntry
)
257 WeakBucket nextBucket
;
258 if (lastEntry
!= null)
260 nextBucket
= lastEntry
.getBucket().next
;
261 slot
= lastEntry
.getBucket().slot
;
265 nextBucket
= buckets
[0];
271 while (nextBucket
!= null)
273 WeakBucket
.WeakEntry entry
= nextBucket
.getEntry();
275 // This is the next entry.
278 // Entry was cleared, try next.
279 nextBucket
= nextBucket
.next
;
283 if (slot
== buckets
.length
)
284 // No more buckets, we are through.
287 nextBucket
= buckets
[slot
];
292 * Checks if there are more entries.
293 * @return true, iff there are more elements.
294 * @throws ConcurrentModificationException if the hash map was
297 public boolean hasNext()
300 return nextEntry
!= null;
304 * Returns the next entry.
305 * @return the next entry.
306 * @throws ConcurrentModificationException if the hash map was
308 * @throws NoSuchElementException if there is no entry.
313 if (nextEntry
== null)
314 throw new NoSuchElementException();
315 lastEntry
= nextEntry
;
316 nextEntry
= findNext(lastEntry
);
321 * Removes the last returned entry from this set. This will
322 * also remove the bucket of the underlying weak hash map.
323 * @throws ConcurrentModificationException if the hash map was
325 * @throws IllegalStateException if <code>next()</code> was
326 * never called or the element was already removed.
331 if (lastEntry
== null)
332 throw new IllegalStateException();
334 internalRemove(lastEntry
.getBucket());
343 * A bucket is a weak reference to the key, that contains a strong
344 * reference to the value, a pointer to the next bucket and its slot
347 * It would be cleaner to have a WeakReference as field, instead of
348 * extending it, but if a weak reference gets cleared, we only get
349 * the weak reference (by queue.poll) and wouldn't know where to
350 * look for this reference in the hashtable, to remove that entry.
352 * @author Jochen Hoenicke
354 private static class WeakBucket
extends WeakReference
357 * The value of this entry. The key is stored in the weak
358 * reference that we extend.
363 * The next bucket describing another entry that uses the same
369 * The slot of this entry. This should be
370 * <code>Math.abs(key.hashCode() % buckets.length)</code>.
372 * But since the key may be silently removed we have to remember
375 * If this bucket was removed the slot is -1. This marker will
376 * prevent the bucket from being removed twice.
381 * Creates a new bucket for the given key/value pair and the specified
384 * @param queue the queue the weak reference belongs to
385 * @param value the value
386 * @param slot the slot. This must match the slot where this bucket
389 public WeakBucket(Object key
, ReferenceQueue queue
, Object value
,
398 * This class gives the <code>Entry</code> representation of the
399 * current bucket. It also keeps a strong reference to the
400 * key; bad things may happen otherwise.
402 class WeakEntry
implements Map
.Entry
405 * The strong ref to the key.
410 * Creates a new entry for the key.
413 public WeakEntry(Object key
)
419 * Returns the underlying bucket.
420 * @return the owning bucket
422 public WeakBucket
getBucket()
424 return WeakBucket
.this;
431 public Object
getKey()
433 return key
== NULL_KEY ?
null : key
;
440 public Object
getValue()
446 * This changes the value. This change takes place in
447 * the underlying hash map.
448 * @param newVal the new value
449 * @return the old value
451 public Object
setValue(Object newVal
)
453 Object oldVal
= value
;
459 * The hashCode as specified in the Entry interface.
460 * @return the hash code
462 public int hashCode()
464 return key
.hashCode() ^ WeakHashMap
.hashCode(value
);
468 * The equals method as specified in the Entry interface.
469 * @param o the object to compare to
470 * @return true iff o represents the same key/value pair
472 public boolean equals(Object o
)
474 if (o
instanceof Map
.Entry
)
476 Map
.Entry e
= (Map
.Entry
) o
;
477 return key
.equals(e
.getKey())
478 && WeakHashMap
.equals(value
, e
.getValue());
483 public String
toString()
485 return key
+ "=" + value
;
490 * This returns the entry stored in this bucket, or null, if the
491 * bucket got cleared in the mean time.
492 * @return the Entry for this bucket, if it exists
496 final Object key
= this.get();
499 return new WeakEntry(key
);
504 * The entry set returned by <code>entrySet()</code>.
506 private final WeakEntrySet theEntrySet
;
509 * The hash buckets. These are linked lists. Package visible for use in
512 WeakBucket
[] buckets
;
515 * Creates a new weak hash map with default load factor and default
520 this(DEFAULT_CAPACITY
, DEFAULT_LOAD_FACTOR
);
524 * Creates a new weak hash map with default load factor and the given
526 * @param initialCapacity the initial capacity
527 * @throws IllegalArgumentException if initialCapacity is negative
529 public WeakHashMap(int initialCapacity
)
531 this(initialCapacity
, DEFAULT_LOAD_FACTOR
);
535 * Creates a new weak hash map with the given initial capacity and
537 * @param initialCapacity the initial capacity.
538 * @param loadFactor the load factor (see class description of HashMap).
539 * @throws IllegalArgumentException if initialCapacity is negative, or
540 * loadFactor is non-positive
542 public WeakHashMap(int initialCapacity
, float loadFactor
)
544 // Check loadFactor for NaN as well.
545 if (initialCapacity
< 0 || ! (loadFactor
> 0))
546 throw new IllegalArgumentException();
547 this.loadFactor
= loadFactor
;
548 threshold
= (int) (initialCapacity
* loadFactor
);
549 theEntrySet
= new WeakEntrySet();
550 queue
= new ReferenceQueue();
551 buckets
= new WeakBucket
[initialCapacity
];
555 * Construct a new WeakHashMap with the same mappings as the given map.
556 * The WeakHashMap has a default load factor of 0.75.
558 * @param m the map to copy
559 * @throws NullPointerException if m is null
562 public WeakHashMap(Map m
)
564 this(m
.size(), DEFAULT_LOAD_FACTOR
);
569 * Simply hashes a non-null Object to its array index.
570 * @param key the key to hash
571 * @return its slot number
573 private int hash(Object key
)
575 return Math
.abs(key
.hashCode() % buckets
.length
);
579 * Cleans the reference queue. This will poll all references (which
580 * are WeakBuckets) from the queue and remove them from this map.
581 * This will not change modCount, even if it modifies the map. The
582 * iterators have to make sure that nothing bad happens. <br>
584 * Currently the iterator maintains a strong reference to the key, so
585 * that is no problem.
587 // Package visible for use by nested classes.
590 Object bucket
= queue
.poll();
591 while (bucket
!= null)
593 internalRemove((WeakBucket
) bucket
);
594 bucket
= queue
.poll();
599 * Rehashes this hashtable. This will be called by the
600 * <code>add()</code> method if the size grows beyond the threshold.
601 * It will grow the bucket size at least by factor two and allocates
604 private void rehash()
606 WeakBucket
[] oldBuckets
= buckets
;
607 int newsize
= buckets
.length
* 2 + 1; // XXX should be prime.
608 threshold
= (int) (newsize
* loadFactor
);
609 buckets
= new WeakBucket
[newsize
];
611 // Now we have to insert the buckets again.
612 for (int i
= 0; i
< oldBuckets
.length
; i
++)
614 WeakBucket bucket
= oldBuckets
[i
];
615 WeakBucket nextBucket
;
616 while (bucket
!= null)
618 nextBucket
= bucket
.next
;
620 Object key
= bucket
.get();
623 // This bucket should be removed; it is probably
624 // already on the reference queue. We don't insert it
625 // at all, and mark it as cleared.
631 // Add this bucket to its new slot.
632 int slot
= hash(key
);
634 bucket
.next
= buckets
[slot
];
635 buckets
[slot
] = bucket
;
643 * Finds the entry corresponding to key. Since it returns an Entry
644 * it will also prevent the key from being removed under us.
645 * @param key the key, may be null
646 * @return The WeakBucket.WeakEntry or null, if the key wasn't found.
648 private WeakBucket
.WeakEntry
internalGet(Object key
)
652 int slot
= hash(key
);
653 WeakBucket bucket
= buckets
[slot
];
654 while (bucket
!= null)
656 WeakBucket
.WeakEntry entry
= bucket
.getEntry();
657 if (entry
!= null && key
.equals(entry
.key
))
660 bucket
= bucket
.next
;
666 * Adds a new key/value pair to the hash map.
667 * @param key the key. This mustn't exists in the map. It may be null.
668 * @param value the value.
670 private void internalAdd(Object key
, Object value
)
674 int slot
= hash(key
);
675 WeakBucket bucket
= new WeakBucket(key
, queue
, value
, slot
);
676 bucket
.next
= buckets
[slot
];
677 buckets
[slot
] = bucket
;
682 * Removes a bucket from this hash map, if it wasn't removed before
683 * (e.g. one time through rehashing and one time through reference queue).
684 * Package visible for use in nested classes.
686 * @param bucket the bucket to remove.
688 void internalRemove(WeakBucket bucket
)
690 int slot
= bucket
.slot
;
692 // This bucket was already removed.
695 // Mark the bucket as removed. This is necessary, since the
696 // bucket may be enqueued later by the garbage collection, and
697 // internalRemove will be called a second time.
699 if (buckets
[slot
] == bucket
)
700 buckets
[slot
] = bucket
.next
;
703 WeakBucket prev
= buckets
[slot
];
704 /* This may throw a NullPointerException. It shouldn't but if
705 * a race condition occurred (two threads removing the same
706 * bucket at the same time) it may happen. <br>
707 * But with race condition many much worse things may happen
710 while (prev
.next
!= bucket
)
712 prev
.next
= bucket
.next
;
718 * Returns the size of this hash map. Note that the size() may shrink
719 * spontaneously, if the some of the keys were only weakly reachable.
720 * @return the number of entries in this hash map.
729 * Tells if the map is empty. Note that the result may change
730 * spontanously, if all of the keys were only weakly reachable.
731 * @return true, iff the map is empty.
733 public boolean isEmpty()
740 * Tells if the map contains the given key. Note that the result
741 * may change spontanously, if the key was only weakly
743 * @param key the key to look for
744 * @return true, iff the map contains an entry for the given key.
746 public boolean containsKey(Object key
)
749 return internalGet(key
) != null;
753 * Gets the value the key is mapped to.
754 * @return the value the key was mapped to. It returns null if
755 * the key wasn't in this map, or if the mapped value was
756 * explicitly set to null.
758 public Object
get(Object key
)
761 WeakBucket
.WeakEntry entry
= internalGet(key
);
762 return entry
== null ?
null : entry
.getValue();
766 * Adds a new key/value mapping to this map.
767 * @param key the key, may be null
768 * @param value the value, may be null
769 * @return the value the key was mapped to previously. It returns
770 * null if the key wasn't in this map, or if the mapped value
771 * was explicitly set to null.
773 public Object
put(Object key
, Object value
)
776 WeakBucket
.WeakEntry entry
= internalGet(key
);
778 return entry
.setValue(value
);
781 if (size
>= threshold
)
784 internalAdd(key
, value
);
789 * Removes the key and the corresponding value from this map.
790 * @param key the key. This may be null.
791 * @return the value the key was mapped to previously. It returns
792 * null if the key wasn't in this map, or if the mapped value was
793 * explicitly set to null.
795 public Object
remove(Object key
)
798 WeakBucket
.WeakEntry entry
= internalGet(key
);
803 internalRemove(entry
.getBucket());
804 return entry
.getValue();
808 * Returns a set representation of the entries in this map. This
809 * set will not have strong references to the keys, so they can be
810 * silently removed. The returned set has therefore the same
811 * strange behaviour (shrinking size(), disappearing entries) as
812 * this weak hash map.
813 * @return a set representation of the entries.
815 public Set
entrySet()
822 * Clears all entries from this map.
830 * Returns true if the map contains at least one key which points to
831 * the specified object as a value. Note that the result
832 * may change spontanously, if its key was only weakly reachable.
833 * @param value the value to search for
834 * @return true if it is found in the set.
836 public boolean containsValue(Object value
)
839 return super.containsValue(value
);
843 * Returns a set representation of the keys in this map. This
844 * set will not have strong references to the keys, so they can be
845 * silently removed. The returned set has therefore the same
846 * strange behaviour (shrinking size(), disappearing entries) as
847 * this weak hash map.
848 * @return a set representation of the keys.
853 return super.keySet();
857 * Puts all of the mappings from the given map into this one. If the
858 * key already exists in this map, its value is replaced.
859 * @param m the map to copy in
861 public void putAll(Map m
)
867 * Returns a collection representation of the values in this map. This
868 * collection will not have strong references to the keys, so mappings
869 * can be silently removed. The returned collection has therefore the same
870 * strange behaviour (shrinking size(), disappearing entries) as
871 * this weak hash map.
872 * @return a collection representation of the values.
874 public Collection
values()
877 return super.values();
879 } // class WeakHashMap