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    }