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 }