001: /*
002: * @(#)SoftCache.java 1.12 06/10/10
003: *
004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: *
026: */
027:
028: package sun.misc;
029:
030: import java.lang.ref.SoftReference;
031: import java.lang.ref.ReferenceQueue;
032:
033: import java.util.Iterator;
034: import java.util.Map;
035: import java.util.AbstractMap;
036: import java.util.HashMap;
037: import java.util.Set;
038: import java.util.AbstractSet;
039: import java.util.NoSuchElementException;
040:
041: /**
042: * A memory-sensitive implementation of the <code>Map</code> interface.
043: *
044: * <p> A <code>SoftCache</code> object uses {@link java.lang.ref.SoftReference
045: * soft references} to implement a memory-sensitive hash map. If the garbage
046: * collector determines at a certain point in time that a value object in a
047: * <code>SoftCache</code> entry is no longer strongly reachable, then it may
048: * remove that entry in order to release the memory occupied by the value
049: * object. All <code>SoftCache</code> objects are guaranteed to be completely
050: * cleared before the virtual machine will throw an
051: * <code>OutOfMemoryError</code>. Because of this automatic clearing feature,
052: * the behavior of this class is somewhat different from that of other
053: * <code>Map</code> implementations.
054: *
055: * <p> Both null values and the null key are supported. This class has the
056: * same performance characteristics as the <code>HashMap</code> class, and has
057: * the same efficiency parameters of <em>initial capacity</em> and <em>load
058: * factor</em>.
059: *
060: * <p> Like most collection classes, this class is not synchronized. A
061: * synchronized <code>SoftCache</code> may be constructed using the
062: * <code>Collections.synchronizedMap</code> method.
063: *
064: * <p> In typical usage this class will be subclassed and the <code>fill</code>
065: * method will be overridden. When the <code>get</code> method is invoked on a
066: * key for which there is no mapping in the cache, it will in turn invoke the
067: * <code>fill</code> method on that key in an attempt to construct a
068: * corresponding value. If the <code>fill</code> method returns such a value
069: * then the cache will be updated and the new value will be returned. Thus,
070: * for example, a simple URL-content cache can be constructed as follows:
071: *
072: * <pre>
073: * public class URLCache extends SoftCache {
074: * protected Object fill(Object key) {
075: * return ((URL)key).getContent();
076: * }
077: * }
078: * </pre>
079: *
080: * <p> The behavior of the <code>SoftCache</code> class depends in part upon
081: * the actions of the garbage collector, so several familiar (though not
082: * required) <code>Map</code> invariants do not hold for this class. <p>
083: * Because entries are removed from a <code>SoftCache</code> in response to
084: * dynamic advice from the garbage collector, a <code>SoftCache</code> may
085: * behave as though an unknown thread is silently removing entries. In
086: * particular, even if you synchronize on a <code>SoftCache</code> instance and
087: * invoke none of its mutator methods, it is possible for the <code>size</code>
088: * method to return smaller values over time, for the <code>isEmpty</code>
089: * method to return <code>false</code> and then <code>true</code>, for the
090: * <code>containsKey</code> method to return <code>true</code> and later
091: * <code>false</code> for a given key, for the <code>get</code> method to
092: * return a value for a given key but later return <code>null</code>, for the
093: * <code>put</code> method to return <code>null</code> and the
094: * <code>remove</code> method to return <code>false</code> for a key that
095: * previously appeared to be in the map, and for successive examinations of the
096: * key set, the value set, and the entry set to yield successively smaller
097: * numbers of elements.
098: *
099: * @version 1.4, 00/02/02
100: * @author Mark Reinhold
101: * @since JDK1.2
102: * @see java.util.HashMap
103: * @see java.lang.ref.SoftReference
104: */
105:
106: public class SoftCache extends AbstractMap implements Map {
107:
108: /* The basic idea of this implementation is to maintain an internal HashMap
109: that maps keys to soft references whose referents are the keys' values;
110: the various accessor methods dereference these soft references before
111: returning values. Because we don't have access to the innards of the
112: HashMap, each soft reference must contain the key that maps to it so
113: that the processQueue method can remove keys whose values have been
114: discarded. Thus the HashMap actually maps keys to instances of the
115: ValueCell class, which is a simple extension of the SoftReference class.
116: */
117:
118: static private class ValueCell extends SoftReference {
119: static private Object INVALID_KEY = new Object();
120: static private int dropped = 0;
121: private Object key;
122:
123: private ValueCell(Object key, Object value, ReferenceQueue queue) {
124: super (value, queue);
125: this .key = key;
126: }
127:
128: private static ValueCell create(Object key, Object value,
129: ReferenceQueue queue) {
130: if (value == null)
131: return null;
132: return new ValueCell(key, value, queue);
133: }
134:
135: private static Object strip(Object val, boolean drop) {
136: if (val == null)
137: return null;
138: ValueCell vc = (ValueCell) val;
139: Object o = vc.get();
140: if (drop)
141: vc.drop();
142: return o;
143: }
144:
145: private boolean isValid() {
146: return (key != INVALID_KEY);
147: }
148:
149: private void drop() {
150: super .clear();
151: key = INVALID_KEY;
152: dropped++;
153: }
154:
155: }
156:
157: /* Hash table mapping keys to ValueCells */
158: private Map hash;
159:
160: /* Reference queue for cleared ValueCells */
161: private ReferenceQueue queue = new ReferenceQueue();
162:
163: /* Process any ValueCells that have been cleared and enqueued by the
164: garbage collector. This method should be invoked once by each public
165: mutator in this class. We don't invoke this method in public accessors
166: because that can lead to surprising ConcurrentModificationExceptions.
167: */
168: private void processQueue() {
169: ValueCell vc;
170: while ((vc = (ValueCell) queue.poll()) != null) {
171: if (vc.isValid())
172: hash.remove(vc.key);
173: else
174: ValueCell.dropped--;
175: }
176: }
177:
178: /* -- Constructors -- */
179:
180: /**
181: * Construct a new, empty <code>SoftCache</code> with the given
182: * initial capacity and the given load factor.
183: *
184: * @param initialCapacity The initial capacity of the cache
185: *
186: * @param loadFactor A number between 0.0 and 1.0
187: *
188: * @throws IllegalArgumentException If the initial capacity is less than
189: * or equal to zero, or if the load
190: * factor is less than zero
191: */
192: public SoftCache(int initialCapacity, float loadFactor) {
193: hash = new HashMap(initialCapacity, loadFactor);
194: }
195:
196: /**
197: * Construct a new, empty <code>SoftCache</code> with the given
198: * initial capacity and the default load factor.
199: *
200: * @param initialCapacity The initial capacity of the cache
201: *
202: * @throws IllegalArgumentException If the initial capacity is less than
203: * or equal to zero
204: */
205: public SoftCache(int initialCapacity) {
206: hash = new HashMap(initialCapacity);
207: }
208:
209: /**
210: * Construct a new, empty <code>SoftCache</code> with the default
211: * capacity and the default load factor.
212: */
213: public SoftCache() {
214: hash = new HashMap();
215: }
216:
217: /* -- Simple queries -- */
218:
219: /**
220: * Return the number of key-value mappings in this cache. The time
221: * required by this operation is linear in the size of the map.
222: */
223: public int size() {
224: return entrySet().size();
225: }
226:
227: /**
228: * Return <code>true</code> if this cache contains no key-value mappings.
229: */
230: public boolean isEmpty() {
231: return entrySet().isEmpty();
232: }
233:
234: /**
235: * Return <code>true</code> if this cache contains a mapping for the
236: * specified key. If there is no mapping for the key, this method will not
237: * attempt to construct one by invoking the <code>fill</code> method.
238: *
239: * @param key The key whose presence in the cache is to be tested
240: */
241: public boolean containsKey(Object key) {
242: return ValueCell.strip(hash.get(key), false) != null;
243: }
244:
245: /* -- Lookup and modification operations -- */
246:
247: /**
248: * Create a value object for the given <code>key</code>. This method is
249: * invoked by the <code>get</code> method when there is no entry for
250: * <code>key</code>. If this method returns a non-<code>null</code> value,
251: * then the cache will be updated to map <code>key</code> to that value,
252: * and that value will be returned by the <code>get</code> method.
253: *
254: * <p> The default implementation of this method simply returns
255: * <code>null</code> for every <code>key</code> value. A subclass may
256: * override this method to provide more useful behavior.
257: *
258: * @param key The key for which a value is to be computed
259: *
260: * @return A value for <code>key</code>, or <code>null</code> if one
261: * could not be computed
262: * @see #get
263: */
264: protected Object fill(Object key) {
265: return null;
266: }
267:
268: /**
269: * Return the value to which this cache maps the specified
270: * <code>key</code>. If the cache does not presently contain a value for
271: * this key, then invoke the <code>fill</code> method in an attempt to
272: * compute such a value. If that method returns a non-<code>null</code>
273: * value, then update the cache and return the new value. Otherwise,
274: * return <code>null</code>.
275: *
276: * <p> Note that because this method may update the cache, it is considered
277: * a mutator and may cause <code>ConcurrentModificationException</code>s to
278: * be thrown if invoked while an iterator is in use.
279: *
280: * @param key The key whose associated value, if any, is to be returned
281: *
282: * @see #fill
283: */
284: public Object get(Object key) {
285: processQueue();
286: Object v = hash.get(key);
287: if (v == null) {
288: v = fill(key);
289: if (v != null) {
290: hash.put(key, ValueCell.create(key, v, queue));
291: return v;
292: }
293: }
294: return ValueCell.strip(v, false);
295: }
296:
297: /**
298: * Update this cache so that the given <code>key</code> maps to the given
299: * <code>value</code>. If the cache previously contained a mapping for
300: * <code>key</code> then that mapping is replaced and the old value is
301: * returned.
302: *
303: * @param key The key that is to be mapped to the given
304: * <code>value</code>
305: * @param value The value to which the given <code>key</code> is to be
306: * mapped
307: *
308: * @return The previous value to which this key was mapped, or
309: * <code>null</code> if if there was no mapping for the key
310: */
311: public Object put(Object key, Object value) {
312: processQueue();
313: ValueCell vc = ValueCell.create(key, value, queue);
314: return ValueCell.strip(hash.put(key, vc), true);
315: }
316:
317: /**
318: * Remove the mapping for the given <code>key</code> from this cache, if
319: * present.
320: *
321: * @param key The key whose mapping is to be removed
322: *
323: * @return The value to which this key was mapped, or <code>null</code> if
324: * there was no mapping for the key
325: */
326: public Object remove(Object key) {
327: processQueue();
328: return ValueCell.strip(hash.remove(key), true);
329: }
330:
331: /**
332: * Remove all mappings from this cache.
333: */
334: public void clear() {
335: processQueue();
336: hash.clear();
337: }
338:
339: /* -- Views -- */
340:
341: private static boolean valEquals(Object o1, Object o2) {
342: return (o1 == null) ? (o2 == null) : o1.equals(o2);
343: }
344:
345: /* Internal class for entries.
346: Because it uses SoftCache.this.queue, this class cannot be static.
347: */
348: private class Entry implements Map.Entry {
349: private Map.Entry ent;
350: private Object value; /* Strong reference to value, to prevent the GC
351: from flushing the value while this Entry
352: exists */
353:
354: Entry(Map.Entry ent, Object value) {
355: this .ent = ent;
356: this .value = value;
357: }
358:
359: public Object getKey() {
360: return ent.getKey();
361: }
362:
363: public Object getValue() {
364: return value;
365: }
366:
367: public Object setValue(Object value) {
368: return ent.setValue(ValueCell.create(ent.getKey(), value,
369: queue));
370: }
371:
372: public boolean equals(Object o) {
373: if (!(o instanceof Map.Entry))
374: return false;
375: Map.Entry e = (Map.Entry) o;
376: return (valEquals(ent.getKey(), e.getKey()) && valEquals(
377: value, e.getValue()));
378: }
379:
380: public int hashCode() {
381: Object k;
382: return ((((k = getKey()) == null) ? 0 : k.hashCode()) ^ ((value == null) ? 0
383: : value.hashCode()));
384: }
385:
386: }
387:
388: /* Internal class for entry sets */
389: private class EntrySet extends AbstractSet {
390: Set hashEntries = hash.entrySet();
391:
392: public Iterator iterator() {
393:
394: return new Iterator() {
395: Iterator hashIterator = hashEntries.iterator();
396: Entry next = null;
397:
398: public boolean hasNext() {
399: while (hashIterator.hasNext()) {
400: Map.Entry ent = (Map.Entry) hashIterator.next();
401: ValueCell vc = (ValueCell) ent.getValue();
402: Object v = null;
403: if ((vc != null) && ((v = vc.get()) == null)) {
404: /* Value has been flushed by GC */
405: continue;
406: }
407: next = new Entry(ent, v);
408: return true;
409: }
410: return false;
411: }
412:
413: public Object next() {
414: if ((next == null) && !hasNext())
415: throw new NoSuchElementException();
416: Entry e = next;
417: next = null;
418: return e;
419: }
420:
421: public void remove() {
422: hashIterator.remove();
423: }
424:
425: };
426: }
427:
428: public boolean isEmpty() {
429: return !(iterator().hasNext());
430: }
431:
432: public int size() {
433: int j = 0;
434: for (Iterator i = iterator(); i.hasNext(); i.next())
435: j++;
436: return j;
437: }
438:
439: public boolean remove(Object o) {
440: processQueue();
441: if (o instanceof Entry)
442: return hashEntries.remove(((Entry) o).ent);
443: else
444: return false;
445: }
446:
447: }
448:
449: private Set entrySet = null;
450:
451: /**
452: * Return a <code>Set</code> view of the mappings in this cache.
453: */
454: public Set entrySet() {
455: if (entrySet == null)
456: entrySet = new EntrySet();
457: return entrySet;
458: }
459:
460: }
|