source: trunk/src/gcc/libjava/java/util/WeakHashMap.java@ 819

Last change on this file since 819 was 2, checked in by bird, 23 years ago

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