1 /**
2 * JDBM LICENSE v1.00
3 *
4 * Redistribution and use of this software and associated documentation
5 * ("Software"), with or without modification, are permitted provided
6 * that the following conditions are met:
7 *
8 * 1. Redistributions of source code must retain copyright
9 * statements and notices. Redistributions must also contain a
10 * copy of this document.
11 *
12 * 2. Redistributions in binary form must reproduce the
13 * above copyright notice, this list of conditions and the
14 * following disclaimer in the documentation and/or other
15 * materials provided with the distribution.
16 *
17 * 3. The name "JDBM" must not be used to endorse or promote
18 * products derived from this Software without prior written
19 * permission of Cees de Groot. For written permission,
20 * please contact cg@cdegroot.com.
21 *
22 * 4. Products derived from this Software may not be called "JDBM"
23 * nor may "JDBM" appear in their names without prior written
24 * permission of Cees de Groot.
25 *
26 * 5. Due credit should be given to the JDBM Project
27 * (http://jdbm.sourceforge.net/).
28 *
29 * THIS SOFTWARE IS PROVIDED BY THE JDBM PROJECT AND CONTRIBUTORS
30 * ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
31 * NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
32 * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
33 * CEES DE GROOT OR ANY CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
34 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
35 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
36 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
37 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
38 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
39 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
40 * OF THE POSSIBILITY OF SUCH DAMAGE.
41 *
42 * Copyright 2000 (C) Cees de Groot. All Rights Reserved.
43 * Contributions are Copyright (C) 2000 by their associated contributors.
44 *
45 * $Id
46 */
47 package jdbm.helper;
48
49 import java.lang.ref.ReferenceQueue;
50 import java.lang.ref.SoftReference;
51 import java.lang.ref.Reference;
52 import java.util.Enumeration;
53 import java.util.Map;
54 import java.util.HashMap;
55
56 /**
57 * Wraps a deterministic cache policy with a <q>Level-2</q> cache based on
58 * J2SE's {@link SoftReference soft references}. Soft references allow
59 * this cache to keep references to objects until the memory they occupy
60 * is required elsewhere.
61 * <p>
62 * Since the {@link CachePolicy} interface requires an event be fired
63 * when an object is evicted, and the event contains the actual object,
64 * this class cannot be a stand-alone implementation of
65 * <code>CachePolicy</code>. This limitation arises because Java References
66 * does not support notification before references are cleared; nor do
67 * they support reaching soft referents. Therefore, this wrapper cache
68 * aggressively notifies evictions: events are fired when the objects are
69 * evicted from the internal cache. Consequently, the soft cache may return
70 * a non-null object when <code>get( )</code> is called, even if that
71 * object was said to have been evicted.
72 * <p>
73 * The current implementation uses a hash structure for its internal key
74 * to value mappings.
75 * <p>
76 * Note: this component's publicly exposed methods are not threadsafe;
77 * potentially concurrent code should synchronize on the cache instance.
78 *
79 * @author <a href="mailto:dranatunga@users.sourceforge.net">Dilum Ranatunga</a>
80 * @version $Id: SoftCache.java,v 1.1 2003/11/01 13:29:27 dranatunga Exp $
81 */
82 public class SoftCache implements CachePolicy {
83 private static final int INITIAL_CAPACITY = 128;
84 private static final float DEFAULT_LOAD_FACTOR = 1.5f;
85
86 private final ReferenceQueue _clearQueue = new ReferenceQueue();
87 private final CachePolicy _internal;
88 private final Map _cacheMap;
89
90 /**
91 * Creates a soft-reference based L2 cache with a {@link MRU} cache as
92 * the internal (L1) cache. The soft reference cache uses the
93 * default load capacity of 1.5f, which is intended to sacrifice some
94 * performance for space. This compromise is reasonable, since all
95 * {@link #get(Object) get( )s} first try the L1 cache anyway. The
96 * internal MRU is given a capacity of 128 elements.
97 */
98 public SoftCache() {
99 this(new MRU(INITIAL_CAPACITY));
100 }
101
102 /**
103 * Creates a soft-reference based L2 cache wrapping the specified
104 * L1 cache.
105 *
106 * @param internal non null internal cache.
107 * @throws NullPointerException if the internal cache is null.
108 */
109 public SoftCache(CachePolicy internal) throws NullPointerException {
110 this(DEFAULT_LOAD_FACTOR, internal);
111 }
112
113 /**
114 * Creates a soft-reference based L2 cache wrapping the specified
115 * L1 cache. This constructor is somewhat implementation-specific,
116 * so users are encouraged to use {@link #SoftCache(CachePolicy)}
117 * instead.
118 *
119 * @param loadFactor load factor that the soft cache's hash structure
120 * should use.
121 * @param internal non null internal cache.
122 * @throws IllegalArgumentException if the load factor is nonpositive.
123 * @throws NullPointerException if the internal cache is null.
124 */
125 public SoftCache(float loadFactor, CachePolicy internal) throws IllegalArgumentException, NullPointerException {
126 if (internal == null) {
127 throw new NullPointerException("Internal cache cannot be null.");
128 }
129 _internal = internal;
130 _cacheMap = new HashMap(INITIAL_CAPACITY, loadFactor);
131 }
132
133 /**
134 * Adds the specified value to the cache under the specified key. Note
135 * that the object is added to both this and the internal cache.
136 * @param key the (non-null) key to store the object under
137 * @param value the (non-null) object to place in the cache
138 * @throws CacheEvictionException exception that the internal cache
139 * would have experienced while evicting an object it currently
140 * cached.
141 */
142 public void put(Object key, Object value) throws CacheEvictionException {
143 if (key == null) {
144 throw new IllegalArgumentException("key cannot be null.");
145 } else if (value == null) {
146 throw new IllegalArgumentException("value cannot be null.");
147 }
148 _internal.put(key, value);
149 removeClearedEntries();
150 _cacheMap.put(key, new Entry(key, value, _clearQueue));
151 }
152
153 /**
154 * Gets the object cached under the specified key.
155 * <p>
156 * The cache is looked up in the following manner:
157 * <ol>
158 * <li>The internal (L1) cache is checked. If the object is found, it is
159 * returned.</li>
160 * <li>This (L2) cache is checked. If the object is not found, then
161 * the caller is informed that the object is inaccessible.</li>
162 * <li>Since the object exists in L2, but not in L1, the object is
163 * readded to L1 using {@link CachePolicy#put(Object, Object)}.</li>
164 * <li>If the readding succeeds, the value is returned to caller.</li>
165 * <li>If a cache eviction exception is encountered instead, we
166 * remove the object from L2 and behave as if the object was
167 * inaccessible.</li>
168 * </ol>
169 * @param key the key that the object was stored under.
170 * @return the object stored under the key specified; null if the
171 * object is not (nolonger) accessible via this cache.
172 */
173 public Object get(Object key) {
174 // first try the internal cache.
175 Object value = _internal.get(key);
176 if (value != null) {
177 return value;
178 }
179 // poll and remove cleared references.
180 removeClearedEntries();
181 Entry entry = (Entry)_cacheMap.get(key);
182 if (entry == null) { // object is not in cache.
183 return null;
184 }
185 value = entry.getValue();
186 if (value == null) { // object was in cache, but it was cleared.
187 return null;
188 }
189 // we have the object. so we try to re-insert it into internal cache
190 try {
191 _internal.put(key, value);
192 } catch (CacheEvictionException e) {
193 // if the internal cache causes a fuss, we kick the object out.
194 _cacheMap.remove(key);
195 return null;
196 }
197 return value;
198 }
199
200 /**
201 * Removes any object stored under the key specified. Note that the
202 * object is removed from both this (L2) and the internal (L1)
203 * cache.
204 * @param key the key whose object should be removed
205 */
206 public void remove(Object key) {
207 _cacheMap.remove(key);
208 _internal.remove(key);
209 }
210
211 /**
212 * Removes all objects in this (L2) and its internal (L1) cache.
213 */
214 public void removeAll() {
215 _cacheMap.clear();
216 _internal.removeAll();
217 }
218
219 /**
220 * Gets all the objects stored by the internal (L1) cache.
221 * @return an enumeration of objects in internal cache.
222 */
223 public Enumeration elements() {
224 return _internal.elements();
225 }
226
227 /**
228 * Adds the specified listener to this cache. Note that the events
229 * fired by this correspond to the <em>internal</em> cache's events.
230 * @param listener the (non-null) listener to add to this policy
231 * @throws IllegalArgumentException if listener is null.
232 */
233 public void addListener(CachePolicyListener listener)
234 throws IllegalArgumentException {
235 _internal.addListener(listener);
236 }
237
238 /**
239 * Removes a listener that was added earlier.
240 * @param listener the listener to remove.
241 */
242 public void removeListener(CachePolicyListener listener) {
243 _internal.removeListener(listener);
244 }
245
246 /**
247 * Cleans the mapping structure of any obsolete entries. This is usually
248 * called before insertions and lookups on the mapping structure. The
249 * runtime of this is usually very small, but it can be as expensive as
250 * n * log(n) if a large number of soft references were recently cleared.
251 */
252 private final void removeClearedEntries() {
253 for (Reference r = _clearQueue.poll(); r != null; r = _clearQueue.poll()) {
254 Object key = ((Entry)r).getKey();
255 _cacheMap.remove(key);
256 }
257 }
258
259 /**
260 * Value objects we keep in the internal map. This contains the key in
261 * addition to the value, because polling for cleared references
262 * returns these instances, and having access to their corresponding
263 * keys drastically improves the performance of removing the pair
264 * from the map (see {@link SoftCache#removeClearedEntries()}.)
265 */
266 private static class Entry extends SoftReference {
267 private final Object _key;
268
269 /**
270 * Constructor that uses <code>value</code> as the soft
271 * reference's referent.
272 */
273 public Entry(Object key, Object value, ReferenceQueue queue) {
274 super(value, queue);
275 _key = key;
276 }
277
278 /**
279 * Gets the key
280 * @return the key associated with this value.
281 */
282 final Object getKey() {
283 return _key;
284 }
285
286 /**
287 * Gets the value
288 * @return the value; null if it is no longer accessible
289 */
290 final Object getValue() {
291 return this.get();
292 }
293 }
294 }