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: MRU.java,v 1.8 2005/06/25 23:12:31 doomdark Exp $
046     */
047    
048    package jdbm.helper;
049    
050    import java.util.Enumeration;
051    import java.util.Hashtable;
052    import java.util.Vector;
053    
054    import org.apache.directory.server.i18n.I18n;
055    
056    
057    /**
058     *  MRU - Most Recently Used cache policy.
059     *
060     *  Methods are *not* synchronized, so no concurrent access is allowed.
061     *
062     * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
063     * @version $Id: MRU.java,v 1.8 2005/06/25 23:12:31 doomdark Exp $
064     */
065    public class MRU implements CachePolicy 
066    {
067    
068        /** Cached object hashtable */
069        Hashtable _hash = new Hashtable();
070    
071        /**
072         * Maximum number of objects in the cache.
073         */
074        int _max;
075    
076        /**
077         * Beginning of linked-list of cache elements.  First entry is element
078         * which has been used least recently.
079         */
080        CacheEntry _first;
081    
082        /**
083         * End of linked-list of cache elements.  Last entry is element
084         * which has been used most recently.
085         */
086        CacheEntry _last;
087    
088    
089        /**
090         * Cache eviction listeners
091         */
092        Vector listeners = new Vector();
093    
094    
095        /**
096         * Construct an MRU with a given maximum number of objects.
097         */
098        public MRU(int max) {
099            if (max <= 0) {
100                throw new IllegalArgumentException( I18n.err( I18n.ERR_528 ));
101            }
102            _max = max;
103        }
104    
105    
106        /**
107         * Place an object in the cache.
108         */
109        public void put(Object key, Object value) throws CacheEvictionException {
110            CacheEntry entry = (CacheEntry)_hash.get(key);
111            if (entry != null) {
112                entry.setValue(value);
113                touchEntry(entry);
114            } else {
115    
116                if (_hash.size() == _max) {
117                    // purge and recycle entry
118                    entry = purgeEntry();
119                    entry.setKey(key);
120                    entry.setValue(value);
121                } else {
122                    entry = new CacheEntry(key, value);
123                }
124                addEntry(entry);
125                _hash.put(entry.getKey(), entry);
126            }
127        }
128    
129    
130        /**
131         * Obtain an object in the cache
132         */
133        public Object get(Object key) {
134            CacheEntry entry = (CacheEntry)_hash.get(key);
135            if (entry != null) {
136                touchEntry(entry);
137                return entry.getValue();
138            } else {
139                return null;
140            }
141        }
142    
143    
144        /**
145         * Remove an object from the cache
146         */
147        public void remove(Object key) {
148            CacheEntry entry = (CacheEntry)_hash.get(key);
149            if (entry != null) {
150                removeEntry(entry);
151                _hash.remove(entry.getKey());
152            }
153        }
154    
155    
156        /**
157         * Remove all objects from the cache
158         */
159        public void removeAll() {
160            _hash = new Hashtable();
161            _first = null;
162            _last = null;
163        }
164    
165    
166        /**
167         * Enumerate elements' values in the cache
168         */
169        public Enumeration elements() {
170            return new MRUEnumeration(_hash.elements());
171        }
172    
173        /**
174         * Add a listener to this cache policy
175         *
176         * @param listener Listener to add to this policy
177         */
178        public void addListener(CachePolicyListener listener) {
179            if (listener == null) {
180                throw new IllegalArgumentException( I18n.err( I18n.ERR_539 ) );
181            }
182            if ( ! listeners.contains(listener)) {
183                listeners.addElement(listener);
184            }
185        }
186    
187        /**
188         * Remove a listener from this cache policy
189         *
190         * @param listener Listener to remove from this policy
191         */
192        public void removeListener(CachePolicyListener listener) {
193            listeners.removeElement(listener);
194        }
195    
196        /**
197         * Add a CacheEntry.  Entry goes at the end of the list.
198         */
199        protected void addEntry(CacheEntry entry) {
200            if (_first == null) {
201                _first = entry;
202                _last = entry;
203            } else {
204                _last.setNext(entry);
205                entry.setPrevious(_last);
206                _last = entry;
207            }
208        }
209    
210    
211        /**
212         * Remove a CacheEntry from linked list
213         */
214        protected void removeEntry(CacheEntry entry) {
215            if (entry == _first) {
216                _first = entry.getNext();
217            }
218            if (_last == entry) {
219                _last = entry.getPrevious();
220            }
221            CacheEntry previous = entry.getPrevious();
222            CacheEntry next = entry.getNext();
223            if (previous != null) {
224                previous.setNext(next);
225            }
226            if (next != null) {
227                next.setPrevious(previous);
228            }
229            entry.setPrevious(null);
230            entry.setNext(null);
231        }
232    
233        /**
234         * Place entry at the end of linked list -- Most Recently Used
235         */
236        protected void touchEntry(CacheEntry entry) {
237            if (_last == entry) {
238                return;
239            }
240            removeEntry(entry);
241            addEntry(entry);
242        }
243    
244        /**
245         * Purge least recently used object from the cache
246         *
247         * @return recyclable CacheEntry
248         */
249        protected CacheEntry purgeEntry() throws CacheEvictionException {
250            CacheEntry entry = _first;
251    
252            // Notify policy listeners first. if any of them throw an
253            // eviction exception, then the internal data structure
254            // remains untouched.
255            CachePolicyListener listener;
256            for (int i=0; i<listeners.size(); i++) {
257                listener = (CachePolicyListener)listeners.elementAt(i);
258                listener.cacheObjectEvicted(entry.getValue());
259            }
260    
261            removeEntry(entry);
262            _hash.remove(entry.getKey());
263    
264            entry.setValue(null);
265            return entry;
266        }
267    
268    }
269    
270    /**
271     * State information for cache entries.
272     */
273    class CacheEntry {
274        private Object _key;
275        private Object _value;
276    
277        private CacheEntry _previous;
278        private CacheEntry _next;
279    
280        CacheEntry(Object key, Object value) {
281            _key = key;
282            _value = value;
283        }
284    
285        Object getKey() {
286            return _key;
287        }
288    
289        void setKey(Object obj) {
290            _key = obj;
291        }
292    
293        Object getValue() {
294            return _value;
295        }
296    
297        void setValue(Object obj) {
298            _value = obj;
299        }
300    
301        CacheEntry getPrevious() {
302            return _previous;
303        }
304    
305        void setPrevious(CacheEntry entry) {
306            _previous = entry;
307        }
308    
309        CacheEntry getNext() {
310            return _next;
311        }
312    
313        void setNext(CacheEntry entry) {
314            _next = entry;
315        }
316    }
317    
318    /**
319     * Enumeration wrapper to return actual user objects instead of
320     * CacheEntries.
321     */
322    class MRUEnumeration implements Enumeration {
323        Enumeration _enum;
324    
325        MRUEnumeration(Enumeration enume) {
326            _enum = enume;
327        }
328    
329        public boolean hasMoreElements() {
330            return _enum.hasMoreElements();
331        }
332    
333        public Object nextElement() {
334            CacheEntry entry = (CacheEntry)_enum.nextElement();
335            return entry.getValue();
336        }
337    }