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 */ 047 package jdbm.helper; 048 049 import java.lang.ref.ReferenceQueue; 050 import java.lang.ref.SoftReference; 051 import java.lang.ref.Reference; 052 import java.util.Enumeration; 053 import java.util.Map; 054 import java.util.HashMap; 055 056 import org.apache.directory.server.i18n.I18n; 057 058 /** 059 * Wraps a deterministic cache policy with a <q>Level-2</q> cache based on 060 * J2SE's {@link SoftReference soft references}. Soft references allow 061 * this cache to keep references to objects until the memory they occupy 062 * is required elsewhere. 063 * <p> 064 * Since the {@link CachePolicy} interface requires an event be fired 065 * when an object is evicted, and the event contains the actual object, 066 * this class cannot be a stand-alone implementation of 067 * <code>CachePolicy</code>. This limitation arises because Java References 068 * does not support notification before references are cleared; nor do 069 * they support reaching soft referents. Therefore, this wrapper cache 070 * aggressively notifies evictions: events are fired when the objects are 071 * evicted from the internal cache. Consequently, the soft cache may return 072 * a non-null object when <code>get( )</code> is called, even if that 073 * object was said to have been evicted. 074 * <p> 075 * The current implementation uses a hash structure for its internal key 076 * to value mappings. 077 * <p> 078 * Note: this component's publicly exposed methods are not threadsafe; 079 * potentially concurrent code should synchronize on the cache instance. 080 * 081 * @author <a href="mailto:dranatunga@users.sourceforge.net">Dilum Ranatunga</a> 082 * @version $Id: SoftCache.java,v 1.1 2003/11/01 13:29:27 dranatunga Exp $ 083 */ 084 public class SoftCache implements CachePolicy { 085 private static final int INITIAL_CAPACITY = 128; 086 private static final float DEFAULT_LOAD_FACTOR = 1.5f; 087 088 private final ReferenceQueue _clearQueue = new ReferenceQueue(); 089 private final CachePolicy _internal; 090 private final Map _cacheMap; 091 092 /** 093 * Creates a soft-reference based L2 cache with a {@link MRU} cache as 094 * the internal (L1) cache. The soft reference cache uses the 095 * default load capacity of 1.5f, which is intended to sacrifice some 096 * performance for space. This compromise is reasonable, since all 097 * {@link #get(Object) get( )s} first try the L1 cache anyway. The 098 * internal MRU is given a capacity of 128 elements. 099 */ 100 public SoftCache() { 101 this(new MRU(INITIAL_CAPACITY)); 102 } 103 104 /** 105 * Creates a soft-reference based L2 cache wrapping the specified 106 * L1 cache. 107 * 108 * @param internal non null internal cache. 109 * @throws NullPointerException if the internal cache is null. 110 */ 111 public SoftCache(CachePolicy internal) throws NullPointerException { 112 this(DEFAULT_LOAD_FACTOR, internal); 113 } 114 115 /** 116 * Creates a soft-reference based L2 cache wrapping the specified 117 * L1 cache. This constructor is somewhat implementation-specific, 118 * so users are encouraged to use {@link #SoftCache(CachePolicy)} 119 * instead. 120 * 121 * @param loadFactor load factor that the soft cache's hash structure 122 * should use. 123 * @param internal non null internal cache. 124 * @throws IllegalArgumentException if the load factor is nonpositive. 125 * @throws NullPointerException if the internal cache is null. 126 */ 127 public SoftCache(float loadFactor, CachePolicy internal) throws IllegalArgumentException, NullPointerException { 128 if (internal == null) { 129 throw new NullPointerException( I18n.err( I18n.ERR_531 ) ); 130 } 131 _internal = internal; 132 _cacheMap = new HashMap(INITIAL_CAPACITY, loadFactor); 133 } 134 135 /** 136 * Adds the specified value to the cache under the specified key. Note 137 * that the object is added to both this and the internal cache. 138 * @param key the (non-null) key to store the object under 139 * @param value the (non-null) object to place in the cache 140 * @throws CacheEvictionException exception that the internal cache 141 * would have experienced while evicting an object it currently 142 * cached. 143 */ 144 public void put(Object key, Object value) throws CacheEvictionException { 145 if (key == null) { 146 throw new IllegalArgumentException( I18n.err( I18n.ERR_532 ) ); 147 } else if (value == null) { 148 throw new IllegalArgumentException( I18n.err( I18n.ERR_533 ) ); 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.poll()) { 256 Object key = ((Entry)r).getKey(); 257 _cacheMap.remove(key); 258 } 259 } 260 261 /** 262 * Value objects we keep in the internal map. This contains the key in 263 * addition to the value, because polling for cleared references 264 * returns these instances, and having access to their corresponding 265 * keys drastically improves the performance of removing the pair 266 * from the map (see {@link SoftCache#removeClearedEntries()}.) 267 */ 268 private static class Entry extends SoftReference { 269 private final Object _key; 270 271 /** 272 * Constructor that uses <code>value</code> as the soft 273 * reference's referent. 274 */ 275 public Entry(Object key, Object value, ReferenceQueue queue) { 276 super(value, queue); 277 _key = key; 278 } 279 280 /** 281 * Gets the key 282 * @return the key associated with this value. 283 */ 284 final Object getKey() { 285 return _key; 286 } 287 288 /** 289 * Gets the value 290 * @return the value; null if it is no longer accessible 291 */ 292 final Object getValue() { 293 return this.get(); 294 } 295 } 296 }