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