1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 package org.apache.commons.collections;
17
18 import java.io.IOException;
19 import java.io.ObjectInputStream;
20 import java.io.ObjectOutputStream;
21 import java.lang.ref.Reference;
22 import java.lang.ref.ReferenceQueue;
23 import java.lang.ref.SoftReference;
24 import java.lang.ref.WeakReference;
25 import java.util.AbstractCollection;
26 import java.util.AbstractMap;
27 import java.util.AbstractSet;
28 import java.util.ArrayList;
29 import java.util.Arrays;
30 import java.util.Collection;
31 import java.util.ConcurrentModificationException;
32 import java.util.Iterator;
33 import java.util.Map;
34 import java.util.NoSuchElementException;
35 import java.util.Set;
36
37 import org.apache.commons.collections.keyvalue.DefaultMapEntry;
38
39 /**
40 * Hash-based {@link Map} implementation that allows
41 * mappings to be removed by the garbage collector.<p>
42 *
43 * When you construct a <code>ReferenceMap</code>, you can
44 * specify what kind of references are used to store the
45 * map's keys and values. If non-hard references are
46 * used, then the garbage collector can remove mappings
47 * if a key or value becomes unreachable, or if the
48 * JVM's memory is running low. For information on how
49 * the different reference types behave, see
50 * {@link Reference}.<p>
51 *
52 * Different types of references can be specified for keys
53 * and values. The keys can be configured to be weak but
54 * the values hard, in which case this class will behave
55 * like a <a href="http://java.sun.com/j2se/1.4/docs/api/java/util/WeakHashMap.html">
56 * <code>WeakHashMap</code></a>. However, you
57 * can also specify hard keys and weak values, or any other
58 * combination. The default constructor uses hard keys
59 * and soft values, providing a memory-sensitive cache.<p>
60 *
61 * The algorithms used are basically the same as those
62 * in {@link java.util.HashMap}. In particular, you
63 * can specify a load factor and capacity to suit your
64 * needs. All optional {@link Map} operations are
65 * supported.<p>
66 *
67 * However, this {@link Map} implementation does <I>not</I>
68 * allow null elements. Attempting to add a null key or
69 * or a null value to the map will raise a
70 * <code>NullPointerException</code>.<p>
71 *
72 * As usual, this implementation is not synchronized. You
73 * can use {@link java.util.Collections#synchronizedMap} to
74 * provide synchronized access to a <code>ReferenceMap</code>.
75 *
76 * @see java.lang.ref.Reference
77 *
78 * @deprecated Moved to map subpackage. Due to be removed in v4.0.
79 * @since Commons Collections 2.1
80 * @version $Revision: 1.1 $ $Date: 2004/05/10 19:52:42 $
81 *
82 * @author Paul Jack
83 */
84 public class ReferenceMap extends AbstractMap {
85
86 /**
87 * For serialization.
88 */
89 final private static long serialVersionUID = -3370601314380922368L;
90
91
92 /**
93 * Constant indicating that hard references should be used.
94 */
95 final public static int HARD = 0;
96
97
98 /**
99 * Constant indicating that soft references should be used.
100 */
101 final public static int SOFT = 1;
102
103
104 /**
105 * Constant indicating that weak references should be used.
106 */
107 final public static int WEAK = 2;
108
109
110
111
112
113 /**
114 * The reference type for keys. Must be HARD, SOFT, WEAK.
115 * Note: I originally marked this field as final, but then this class
116 * didn't compile under JDK1.2.2.
117 * @serial
118 */
119 private int keyType;
120
121
122 /**
123 * The reference type for values. Must be HARD, SOFT, WEAK.
124 * Note: I originally marked this field as final, but then this class
125 * didn't compile under JDK1.2.2.
126 * @serial
127 */
128 private int valueType;
129
130
131 /**
132 * The threshold variable is calculated by multiplying
133 * table.length and loadFactor.
134 * Note: I originally marked this field as final, but then this class
135 * didn't compile under JDK1.2.2.
136 * @serial
137 */
138 private float loadFactor;
139
140 /**
141 * Should the value be automatically purged when the associated key has been collected?
142 */
143 private boolean purgeValues = false;
144
145
146
147
148 /**
149 * ReferenceQueue used to eliminate stale mappings.
150 * See purge.
151 */
152 private transient ReferenceQueue queue = new ReferenceQueue();
153
154
155 /**
156 * The hash table. Its length is always a power of two.
157 */
158 private transient Entry[] table;
159
160
161 /**
162 * Number of mappings in this map.
163 */
164 private transient int size;
165
166
167 /**
168 * When size reaches threshold, the map is resized.
169 * See resize().
170 */
171 private transient int threshold;
172
173
174 /**
175 * Number of times this map has been modified.
176 */
177 private transient volatile int modCount;
178
179
180 /**
181 * Cached key set. May be null if key set is never accessed.
182 */
183 private transient Set keySet;
184
185
186 /**
187 * Cached entry set. May be null if entry set is never accessed.
188 */
189 private transient Set entrySet;
190
191
192 /**
193 * Cached values. May be null if values() is never accessed.
194 */
195 private transient Collection values;
196
197
198 /**
199 * Constructs a new <code>ReferenceMap</code> that will
200 * use hard references to keys and soft references to values.
201 */
202 public ReferenceMap() {
203 this(HARD, SOFT);
204 }
205
206 /**
207 * Constructs a new <code>ReferenceMap</code> that will
208 * use the specified types of references.
209 *
210 * @param keyType the type of reference to use for keys;
211 * must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
212 * @param valueType the type of reference to use for values;
213 * must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
214 * @param purgeValues should the value be automatically purged when the
215 * key is garbage collected
216 */
217 public ReferenceMap(int keyType, int valueType, boolean purgeValues) {
218 this(keyType, valueType);
219 this.purgeValues = purgeValues;
220 }
221
222 /**
223 * Constructs a new <code>ReferenceMap</code> that will
224 * use the specified types of references.
225 *
226 * @param keyType the type of reference to use for keys;
227 * must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
228 * @param valueType the type of reference to use for values;
229 * must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
230 */
231 public ReferenceMap(int keyType, int valueType) {
232 this(keyType, valueType, 16, 0.75f);
233 }
234
235 /**
236 * Constructs a new <code>ReferenceMap</code> with the
237 * specified reference types, load factor and initial
238 * capacity.
239 *
240 * @param keyType the type of reference to use for keys;
241 * must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
242 * @param valueType the type of reference to use for values;
243 * must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
244 * @param capacity the initial capacity for the map
245 * @param loadFactor the load factor for the map
246 * @param purgeValues should the value be automatically purged when the
247 * key is garbage collected
248 */
249 public ReferenceMap(
250 int keyType,
251 int valueType,
252 int capacity,
253 float loadFactor,
254 boolean purgeValues) {
255 this(keyType, valueType, capacity, loadFactor);
256 this.purgeValues = purgeValues;
257 }
258
259 /**
260 * Constructs a new <code>ReferenceMap</code> with the
261 * specified reference types, load factor and initial
262 * capacity.
263 *
264 * @param keyType the type of reference to use for keys;
265 * must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
266 * @param valueType the type of reference to use for values;
267 * must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
268 * @param capacity the initial capacity for the map
269 * @param loadFactor the load factor for the map
270 */
271 public ReferenceMap(int keyType, int valueType, int capacity, float loadFactor) {
272 super();
273
274 verify("keyType", keyType);
275 verify("valueType", valueType);
276
277 if (capacity <= 0) {
278 throw new IllegalArgumentException("capacity must be positive");
279 }
280 if ((loadFactor <= 0.0f) || (loadFactor >= 1.0f)) {
281 throw new IllegalArgumentException("Load factor must be greater than 0 and less than 1.");
282 }
283
284 this.keyType = keyType;
285 this.valueType = valueType;
286
287 int v = 1;
288 while (v < capacity) v *= 2;
289
290 this.table = new Entry[v];
291 this.loadFactor = loadFactor;
292 this.threshold = (int)(v * loadFactor);
293 }
294
295
296
297 private static void verify(String name, int type) {
298 if ((type < HARD) || (type > WEAK)) {
299 throw new IllegalArgumentException(name +
300 " must be HARD, SOFT, WEAK.");
301 }
302 }
303
304
305 /**
306 * Writes this object to the given output stream.
307 *
308 * @param out the output stream to write to
309 * @throws IOException if the stream raises it
310 */
311 private void writeObject(ObjectOutputStream out) throws IOException {
312 out.defaultWriteObject();
313 out.writeInt(table.length);
314
315
316
317
318 for (Iterator iter = entrySet().iterator(); iter.hasNext();) {
319 Map.Entry entry = (Map.Entry)iter.next();
320 out.writeObject(entry.getKey());
321 out.writeObject(entry.getValue());
322 }
323 out.writeObject(null);
324 }
325
326
327 /**
328 * Reads the contents of this object from the given input stream.
329 *
330 * @param inp the input stream to read from
331 * @throws IOException if the stream raises it
332 * @throws ClassNotFoundException if the stream raises it
333 */
334 private void readObject(ObjectInputStream inp) throws IOException, ClassNotFoundException {
335 inp.defaultReadObject();
336 table = new Entry[inp.readInt()];
337 threshold = (int)(table.length * loadFactor);
338 queue = new ReferenceQueue();
339 Object key = inp.readObject();
340 while (key != null) {
341 Object value = inp.readObject();
342 put(key, value);
343 key = inp.readObject();
344 }
345 }
346
347
348 /**
349 * Constructs a reference of the given type to the given
350 * referent. The reference is registered with the queue
351 * for later purging.
352 *
353 * @param type HARD, SOFT or WEAK
354 * @param referent the object to refer to
355 * @param hash the hash code of the <I>key</I> of the mapping;
356 * this number might be different from referent.hashCode() if
357 * the referent represents a value and not a key
358 */
359 private Object toReference(int type, Object referent, int hash) {
360 switch (type) {
361 case HARD: return referent;
362 case SOFT: return new SoftRef(hash, referent, queue);
363 case WEAK: return new WeakRef(hash, referent, queue);
364 default: throw new Error();
365 }
366 }
367
368
369 /**
370 * Returns the entry associated with the given key.
371 *
372 * @param key the key of the entry to look up
373 * @return the entry associated with that key, or null
374 * if the key is not in this map
375 */
376 private Entry getEntry(Object key) {
377 if (key == null) return null;
378 int hash = key.hashCode();
379 int index = indexFor(hash);
380 for (Entry entry = table[index]; entry != null; entry = entry.next) {
381 if ((entry.hash == hash) && key.equals(entry.getKey())) {
382 return entry;
383 }
384 }
385 return null;
386 }
387
388
389 /**
390 * Converts the given hash code into an index into the
391 * hash table.
392 */
393 private int indexFor(int hash) {
394
395 hash += ~(hash << 15);
396 hash ^= (hash >>> 10);
397 hash += (hash << 3);
398 hash ^= (hash >>> 6);
399 hash += ~(hash << 11);
400 hash ^= (hash >>> 16);
401 return hash & (table.length - 1);
402 }
403
404
405
406 /**
407 * Resizes this hash table by doubling its capacity.
408 * This is an expensive operation, as entries must
409 * be copied from the old smaller table to the new
410 * bigger table.
411 */
412 private void resize() {
413 Entry[] old = table;
414 table = new Entry[old.length * 2];
415
416 for (int i = 0; i < old.length; i++) {
417 Entry next = old[i];
418 while (next != null) {
419 Entry entry = next;
420 next = next.next;
421 int index = indexFor(entry.hash);
422 entry.next = table[index];
423 table[index] = entry;
424 }
425 old[i] = null;
426 }
427 threshold = (int)(table.length * loadFactor);
428 }
429
430
431
432 /**
433 * Purges stale mappings from this map.
434 * <p>
435 * Ordinarily, stale mappings are only removed during
436 * a write operation, although this method is called for both
437 * read and write operations to maintain a consistent state.
438 * <p>
439 * Note that this method is not synchronized! Special
440 * care must be taken if, for instance, you want stale
441 * mappings to be removed on a periodic basis by some
442 * background thread.
443 */
444 private void purge() {
445 Reference ref = queue.poll();
446 while (ref != null) {
447 purge(ref);
448 ref = queue.poll();
449 }
450 }
451
452
453 private void purge(Reference ref) {
454
455
456
457 int hash = ref.hashCode();
458 int index = indexFor(hash);
459 Entry previous = null;
460 Entry entry = table[index];
461 while (entry != null) {
462 if (entry.purge(ref)) {
463 if (previous == null) table[index] = entry.next;
464 else previous.next = entry.next;
465 this.size--;
466 return;
467 }
468 previous = entry;
469 entry = entry.next;
470 }
471
472 }
473
474
475 /**
476 * Returns the size of this map.
477 *
478 * @return the size of this map
479 */
480 public int size() {
481 purge();
482 return size;
483 }
484
485
486 /**
487 * Returns <code>true</code> if this map is empty.
488 *
489 * @return <code>true</code> if this map is empty
490 */
491 public boolean isEmpty() {
492 purge();
493 return size == 0;
494 }
495
496
497 /**
498 * Returns <code>true</code> if this map contains the given key.
499 *
500 * @return true if the given key is in this map
501 */
502 public boolean containsKey(Object key) {
503 purge();
504 Entry entry = getEntry(key);
505 if (entry == null) return false;
506 return entry.getValue() != null;
507 }
508
509
510 /**
511 * Returns the value associated with the given key, if any.
512 *
513 * @return the value associated with the given key, or <code>null</code>
514 * if the key maps to no value
515 */
516 public Object get(Object key) {
517 purge();
518 Entry entry = getEntry(key);
519 if (entry == null) return null;
520 return entry.getValue();
521 }
522
523
524 /**
525 * Associates the given key with the given value.<p>
526 * Neither the key nor the value may be null.
527 *
528 * @param key the key of the mapping
529 * @param value the value of the mapping
530 * @return the last value associated with that key, or
531 * null if no value was associated with the key
532 * @throws NullPointerException if either the key or value
533 * is null
534 */
535 public Object put(Object key, Object value) {
536 if (key == null) throw new NullPointerException("null keys not allowed");
537 if (value == null) throw new NullPointerException("null values not allowed");
538
539 purge();
540 if (size + 1 > threshold) resize();
541
542 int hash = key.hashCode();
543 int index = indexFor(hash);
544 Entry entry = table[index];
545 while (entry != null) {
546 if ((hash == entry.hash) && key.equals(entry.getKey())) {
547 Object result = entry.getValue();
548 entry.setValue(value);
549 return result;
550 }
551 entry = entry.next;
552 }
553 this.size++;
554 modCount++;
555 key = toReference(keyType, key, hash);
556 value = toReference(valueType, value, hash);
557 table[index] = new Entry(key, hash, value, table[index]);
558 return null;
559 }
560
561
562 /**
563 * Removes the key and its associated value from this map.
564 *
565 * @param key the key to remove
566 * @return the value associated with that key, or null if
567 * the key was not in the map
568 */
569 public Object remove(Object key) {
570 if (key == null) return null;
571 purge();
572 int hash = key.hashCode();
573 int index = indexFor(hash);
574 Entry previous = null;
575 Entry entry = table[index];
576 while (entry != null) {
577 if ((hash == entry.hash) && key.equals(entry.getKey())) {
578 if (previous == null) table[index] = entry.next;
579 else previous.next = entry.next;
580 this.size--;
581 modCount++;
582 return entry.getValue();
583 }
584 previous = entry;
585 entry = entry.next;
586 }
587 return null;
588 }
589
590
591 /**
592 * Clears this map.
593 */
594 public void clear() {
595 Arrays.fill(table, null);
596 size = 0;
597 while (queue.poll() != null);
598 }
599
600
601 /**
602 * Returns a set view of this map's entries.
603 *
604 * @return a set view of this map's entries
605 */
606 public Set entrySet() {
607 if (entrySet != null) {
608 return entrySet;
609 }
610 entrySet = new AbstractSet() {
611 public int size() {
612 return ReferenceMap.this.size();
613 }
614
615 public void clear() {
616 ReferenceMap.this.clear();
617 }
618
619 public boolean contains(Object o) {
620 if (o == null) return false;
621 if (!(o instanceof Map.Entry)) return false;
622 Map.Entry e = (Map.Entry)o;
623 Entry e2 = getEntry(e.getKey());
624 return (e2 != null) && e.equals(e2);
625 }
626
627 public boolean remove(Object o) {
628 boolean r = contains(o);
629 if (r) {
630 Map.Entry e = (Map.Entry)o;
631 ReferenceMap.this.remove(e.getKey());
632 }
633 return r;
634 }
635
636 public Iterator iterator() {
637 return new EntryIterator();
638 }
639
640 public Object[] toArray() {
641 return toArray(new Object[0]);
642 }
643
644 public Object[] toArray(Object[] arr) {
645 ArrayList list = new ArrayList();
646 Iterator iterator = iterator();
647 while (iterator.hasNext()) {
648 Entry e = (Entry)iterator.next();
649 list.add(new DefaultMapEntry(e.getKey(), e.getValue()));
650 }
651 return list.toArray(arr);
652 }
653 };
654 return entrySet;
655 }
656
657
658 /**
659 * Returns a set view of this map's keys.
660 *
661 * @return a set view of this map's keys
662 */
663 public Set keySet() {
664 if (keySet != null) return keySet;
665 keySet = new AbstractSet() {
666 public int size() {
667 return ReferenceMap.this.size();
668 }
669
670 public Iterator iterator() {
671 return new KeyIterator();
672 }
673
674 public boolean contains(Object o) {
675 return containsKey(o);
676 }
677
678
679 public boolean remove(Object o) {
680 Object r = ReferenceMap.this.remove(o);
681 return r != null;
682 }
683
684 public void clear() {
685 ReferenceMap.this.clear();
686 }
687
688 public Object[] toArray() {
689 return toArray(new Object[0]);
690 }
691
692 public Object[] toArray(Object[] array) {
693 Collection c = new ArrayList(size());
694 for (Iterator it = iterator(); it.hasNext(); ) {
695 c.add(it.next());
696 }
697 return c.toArray(array);
698 }
699 };
700 return keySet;
701 }
702
703
704 /**
705 * Returns a collection view of this map's values.
706 *
707 * @return a collection view of this map's values.
708 */
709 public Collection values() {
710 if (values != null) return values;
711 values = new AbstractCollection() {
712 public int size() {
713 return ReferenceMap.this.size();
714 }
715
716 public void clear() {
717 ReferenceMap.this.clear();
718 }
719
720 public Iterator iterator() {
721 return new ValueIterator();
722 }
723
724 public Object[] toArray() {
725 return toArray(new Object[0]);
726 }
727
728 public Object[] toArray(Object[] array) {
729 Collection c = new ArrayList(size());
730 for (Iterator it = iterator(); it.hasNext(); ) {
731 c.add(it.next());
732 }
733 return c.toArray(array);
734 }
735 };
736 return values;
737 }
738
739
740
741
742 private class Entry implements Map.Entry, KeyValue {
743
744 Object key;
745 Object value;
746 int hash;
747 Entry next;
748
749
750 public Entry(Object key, int hash, Object value, Entry next) {
751 this.key = key;
752 this.hash = hash;
753 this.value = value;
754 this.next = next;
755 }
756
757
758 public Object getKey() {
759 return (keyType > HARD) ? ((Reference)key).get() : key;
760 }
761
762
763 public Object getValue() {
764 return (valueType > HARD) ? ((Reference)value).get() : value;
765 }
766
767
768 public Object setValue(Object object) {
769 Object old = getValue();
770 if (valueType > HARD) ((Reference)value).clear();
771 value = toReference(valueType, object, hash);
772 return old;
773 }
774
775
776 public boolean equals(Object o) {
777 if (o == null) return false;
778 if (o == this) return true;
779 if (!(o instanceof Map.Entry)) return false;
780
781 Map.Entry entry = (Map.Entry)o;
782 Object key = entry.getKey();
783 Object value = entry.getValue();
784 if ((key == null) || (value == null)) return false;
785 return key.equals(getKey()) && value.equals(getValue());
786 }
787
788
789 public int hashCode() {
790 Object v = getValue();
791 return hash ^ ((v == null) ? 0 : v.hashCode());
792 }
793
794
795 public String toString() {
796 return getKey() + "=" + getValue();
797 }
798
799
800 boolean purge(Reference ref) {
801 boolean r = (keyType > HARD) && (key == ref);
802 r = r || ((valueType > HARD) && (value == ref));
803 if (r) {
804 if (keyType > HARD) ((Reference)key).clear();
805 if (valueType > HARD) {
806 ((Reference)value).clear();
807 } else if (purgeValues) {
808 value = null;
809 }
810 }
811 return r;
812 }
813 }
814
815
816 private class EntryIterator implements Iterator {
817
818 int index;
819 Entry entry;
820 Entry previous;
821
822
823
824
825 Object nextKey, nextValue;
826 Object currentKey, currentValue;
827
828 int expectedModCount;
829
830
831 public EntryIterator() {
832 index = (size() != 0 ? table.length : 0);
833
834
835 expectedModCount = modCount;
836 }
837
838
839 public boolean hasNext() {
840 checkMod();
841 while (nextNull()) {
842 Entry e = entry;
843 int i = index;
844 while ((e == null) && (i > 0)) {
845 i--;
846 e = table[i];
847 }
848 entry = e;
849 index = i;
850 if (e == null) {
851 currentKey = null;
852 currentValue = null;
853 return false;
854 }
855 nextKey = e.getKey();
856 nextValue = e.getValue();
857 if (nextNull()) entry = entry.next;
858 }
859 return true;
860 }
861
862
863 private void checkMod() {
864 if (modCount != expectedModCount) {
865 throw new ConcurrentModificationException();
866 }
867 }
868
869
870 private boolean nextNull() {
871 return (nextKey == null) || (nextValue == null);
872 }
873
874 protected Entry nextEntry() {
875 checkMod();
876 if (nextNull() && !hasNext()) throw new NoSuchElementException();
877 previous = entry;
878 entry = entry.next;
879 currentKey = nextKey;
880 currentValue = nextValue;
881 nextKey = null;
882 nextValue = null;
883 return previous;
884 }
885
886
887 public Object next() {
888 return nextEntry();
889 }
890
891
892 public void remove() {
893 checkMod();
894 if (previous == null) throw new IllegalStateException();
895 ReferenceMap.this.remove(currentKey);
896 previous = null;
897 currentKey = null;
898 currentValue = null;
899 expectedModCount = modCount;
900 }
901
902 }
903
904
905 private class ValueIterator extends EntryIterator {
906 public Object next() {
907 return nextEntry().getValue();
908 }
909 }
910
911
912 private class KeyIterator extends EntryIterator {
913 public Object next() {
914 return nextEntry().getKey();
915 }
916 }
917
918
919
920
921
922
923
924
925 private static class SoftRef extends SoftReference {
926 private int hash;
927
928
929 public SoftRef(int hash, Object r, ReferenceQueue q) {
930 super(r, q);
931 this.hash = hash;
932 }
933
934
935 public int hashCode() {
936 return hash;
937 }
938 }
939
940
941 private static class WeakRef extends WeakReference {
942 private int hash;
943
944
945 public WeakRef(int hash, Object r, ReferenceQueue q) {
946 super(r, q);
947 this.hash = hash;
948 }
949
950
951 public int hashCode() {
952 return hash;
953 }
954 }
955
956
957 }