View Javadoc

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 }