001: /**
002: * JDBM LICENSE v1.00
003: *
004: * Redistribution and use of this software and associated documentation
005: * ("Software"), with or without modification, are permitted provided
006: * that the following conditions are met:
007: *
008: * 1. Redistributions of source code must retain copyright
009: * statements and notices. Redistributions must also contain a
010: * copy of this document.
011: *
012: * 2. Redistributions in binary form must reproduce the
013: * above copyright notice, this list of conditions and the
014: * following disclaimer in the documentation and/or other
015: * materials provided with the distribution.
016: *
017: * 3. The name "JDBM" must not be used to endorse or promote
018: * products derived from this Software without prior written
019: * permission of Cees de Groot. For written permission,
020: * please contact cg@cdegroot.com.
021: *
022: * 4. Products derived from this Software may not be called "JDBM"
023: * nor may "JDBM" appear in their names without prior written
024: * permission of Cees de Groot.
025: *
026: * 5. Due credit should be given to the JDBM Project
027: * (http://jdbm.sourceforge.net/).
028: *
029: * THIS SOFTWARE IS PROVIDED BY THE JDBM PROJECT AND CONTRIBUTORS
030: * ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
031: * NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
032: * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
033: * CEES DE GROOT OR ANY CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
034: * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
035: * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
036: * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
037: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
038: * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
039: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
040: * OF THE POSSIBILITY OF SUCH DAMAGE.
041: *
042: * Copyright 2000 (C) Cees de Groot. All Rights Reserved.
043: * Contributions are Copyright (C) 2000 by their associated contributors.
044: *
045: * $Id
046: */package jdbm.helper;
047:
048: import java.lang.ref.ReferenceQueue;
049: import java.lang.ref.SoftReference;
050: import java.lang.ref.Reference;
051: import java.util.Enumeration;
052: import java.util.Map;
053: import java.util.HashMap;
054:
055: /**
056: * Wraps a deterministic cache policy with a <q>Level-2</q> cache based on
057: * J2SE's {@link SoftReference soft references}. Soft references allow
058: * this cache to keep references to objects until the memory they occupy
059: * is required elsewhere.
060: * <p>
061: * Since the {@link CachePolicy} interface requires an event be fired
062: * when an object is evicted, and the event contains the actual object,
063: * this class cannot be a stand-alone implementation of
064: * <code>CachePolicy</code>. This limitation arises because Java References
065: * does not support notification before references are cleared; nor do
066: * they support reaching soft referents. Therefore, this wrapper cache
067: * aggressively notifies evictions: events are fired when the objects are
068: * evicted from the internal cache. Consequently, the soft cache may return
069: * a non-null object when <code>get( )</code> is called, even if that
070: * object was said to have been evicted.
071: * <p>
072: * The current implementation uses a hash structure for its internal key
073: * to value mappings.
074: * <p>
075: * Note: this component's publicly exposed methods are not threadsafe;
076: * potentially concurrent code should synchronize on the cache instance.
077: *
078: * @author <a href="mailto:dranatunga@users.sourceforge.net">Dilum Ranatunga</a>
079: * @version $Id: SoftCache.java,v 1.1 2003/11/01 13:29:27 dranatunga Exp $
080: */
081: public class SoftCache implements CachePolicy {
082: private static final int INITIAL_CAPACITY = 128;
083: private static final float DEFAULT_LOAD_FACTOR = 1.5f;
084:
085: private final ReferenceQueue _clearQueue = new ReferenceQueue();
086: private final CachePolicy _internal;
087: private final Map _cacheMap;
088:
089: /**
090: * Creates a soft-reference based L2 cache with a {@link MRU} cache as
091: * the internal (L1) cache. The soft reference cache uses the
092: * default load capacity of 1.5f, which is intended to sacrifice some
093: * performance for space. This compromise is reasonable, since all
094: * {@link #get(Object) get( )s} first try the L1 cache anyway. The
095: * internal MRU is given a capacity of 128 elements.
096: */
097: public SoftCache() {
098: this (new MRU(INITIAL_CAPACITY));
099: }
100:
101: /**
102: * Creates a soft-reference based L2 cache wrapping the specified
103: * L1 cache.
104: *
105: * @param internal non null internal cache.
106: * @throws NullPointerException if the internal cache is null.
107: */
108: public SoftCache(CachePolicy internal) throws NullPointerException {
109: this (DEFAULT_LOAD_FACTOR, internal);
110: }
111:
112: /**
113: * Creates a soft-reference based L2 cache wrapping the specified
114: * L1 cache. This constructor is somewhat implementation-specific,
115: * so users are encouraged to use {@link #SoftCache(CachePolicy)}
116: * instead.
117: *
118: * @param loadFactor load factor that the soft cache's hash structure
119: * should use.
120: * @param internal non null internal cache.
121: * @throws IllegalArgumentException if the load factor is nonpositive.
122: * @throws NullPointerException if the internal cache is null.
123: */
124: public SoftCache(float loadFactor, CachePolicy internal)
125: throws IllegalArgumentException, NullPointerException {
126: if (internal == null) {
127: throw new NullPointerException(
128: "Internal cache cannot be null.");
129: }
130: _internal = internal;
131: _cacheMap = new HashMap(INITIAL_CAPACITY, loadFactor);
132: }
133:
134: /**
135: * Adds the specified value to the cache under the specified key. Note
136: * that the object is added to both this and the internal cache.
137: * @param key the (non-null) key to store the object under
138: * @param value the (non-null) object to place in the cache
139: * @throws CacheEvictionException exception that the internal cache
140: * would have experienced while evicting an object it currently
141: * cached.
142: */
143: public void put(Object key, Object value)
144: throws CacheEvictionException {
145: if (key == null) {
146: throw new IllegalArgumentException("key cannot be null.");
147: } else if (value == null) {
148: throw new IllegalArgumentException("value cannot be null.");
149: }
150: _internal.put(key, value);
151: removeClearedEntries();
152: _cacheMap.put(key, new Entry(key, value, _clearQueue));
153: }
154:
155: /**
156: * Gets the object cached under the specified key.
157: * <p>
158: * The cache is looked up in the following manner:
159: * <ol>
160: * <li>The internal (L1) cache is checked. If the object is found, it is
161: * returned.</li>
162: * <li>This (L2) cache is checked. If the object is not found, then
163: * the caller is informed that the object is inaccessible.</li>
164: * <li>Since the object exists in L2, but not in L1, the object is
165: * readded to L1 using {@link CachePolicy#put(Object, Object)}.</li>
166: * <li>If the readding succeeds, the value is returned to caller.</li>
167: * <li>If a cache eviction exception is encountered instead, we
168: * remove the object from L2 and behave as if the object was
169: * inaccessible.</li>
170: * </ol>
171: * @param key the key that the object was stored under.
172: * @return the object stored under the key specified; null if the
173: * object is not (nolonger) accessible via this cache.
174: */
175: public Object get(Object key) {
176: // first try the internal cache.
177: Object value = _internal.get(key);
178: if (value != null) {
179: return value;
180: }
181: // poll and remove cleared references.
182: removeClearedEntries();
183: Entry entry = (Entry) _cacheMap.get(key);
184: if (entry == null) { // object is not in cache.
185: return null;
186: }
187: value = entry.getValue();
188: if (value == null) { // object was in cache, but it was cleared.
189: return null;
190: }
191: // we have the object. so we try to re-insert it into internal cache
192: try {
193: _internal.put(key, value);
194: } catch (CacheEvictionException e) {
195: // if the internal cache causes a fuss, we kick the object out.
196: _cacheMap.remove(key);
197: return null;
198: }
199: return value;
200: }
201:
202: /**
203: * Removes any object stored under the key specified. Note that the
204: * object is removed from both this (L2) and the internal (L1)
205: * cache.
206: * @param key the key whose object should be removed
207: */
208: public void remove(Object key) {
209: _cacheMap.remove(key);
210: _internal.remove(key);
211: }
212:
213: /**
214: * Removes all objects in this (L2) and its internal (L1) cache.
215: */
216: public void removeAll() {
217: _cacheMap.clear();
218: _internal.removeAll();
219: }
220:
221: /**
222: * Gets all the objects stored by the internal (L1) cache.
223: * @return an enumeration of objects in internal cache.
224: */
225: public Enumeration elements() {
226: return _internal.elements();
227: }
228:
229: /**
230: * Adds the specified listener to this cache. Note that the events
231: * fired by this correspond to the <em>internal</em> cache's events.
232: * @param listener the (non-null) listener to add to this policy
233: * @throws IllegalArgumentException if listener is null.
234: */
235: public void addListener(CachePolicyListener listener)
236: throws IllegalArgumentException {
237: _internal.addListener(listener);
238: }
239:
240: /**
241: * Removes a listener that was added earlier.
242: * @param listener the listener to remove.
243: */
244: public void removeListener(CachePolicyListener listener) {
245: _internal.removeListener(listener);
246: }
247:
248: /**
249: * Cleans the mapping structure of any obsolete entries. This is usually
250: * called before insertions and lookups on the mapping structure. The
251: * runtime of this is usually very small, but it can be as expensive as
252: * n * log(n) if a large number of soft references were recently cleared.
253: */
254: private final void removeClearedEntries() {
255: for (Reference r = _clearQueue.poll(); r != null; r = _clearQueue
256: .poll()) {
257: Object key = ((Entry) r).getKey();
258: _cacheMap.remove(key);
259: }
260: }
261:
262: /**
263: * Value objects we keep in the internal map. This contains the key in
264: * addition to the value, because polling for cleared references
265: * returns these instances, and having access to their corresponding
266: * keys drastically improves the performance of removing the pair
267: * from the map (see {@link SoftCache#removeClearedEntries()}.)
268: */
269: private static class Entry extends SoftReference {
270: private final Object _key;
271:
272: /**
273: * Constructor that uses <code>value</code> as the soft
274: * reference's referent.
275: */
276: public Entry(Object key, Object value, ReferenceQueue queue) {
277: super (value, queue);
278: _key = key;
279: }
280:
281: /**
282: * Gets the key
283: * @return the key associated with this value.
284: */
285: final Object getKey() {
286: return _key;
287: }
288:
289: /**
290: * Gets the value
291: * @return the value; null if it is no longer accessible
292: */
293: final Object getValue() {
294: return this.get();
295: }
296: }
297: }
|