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: MRU.java,v 1.8 2005/06/25 23:12:31 doomdark Exp $
46   */
47  
48  package jdbm.helper;
49  
50  import java.util.Enumeration;
51  import java.util.Hashtable;
52  import java.util.Vector;
53  
54  
55  /**
56   *  MRU - Most Recently Used cache policy.
57   *
58   *  Methods are *not* synchronized, so no concurrent access is allowed.
59   *
60   * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
61   * @version $Id: MRU.java,v 1.8 2005/06/25 23:12:31 doomdark Exp $
62   */
63  public class MRU implements CachePolicy {
64  
65      /** Cached object hashtable */
66      Hashtable _hash = new Hashtable();
67  
68      /**
69       * Maximum number of objects in the cache.
70       */
71      int _max;
72  
73      /**
74       * Beginning of linked-list of cache elements.  First entry is element
75       * which has been used least recently.
76       */
77      CacheEntry _first;
78  
79      /**
80       * End of linked-list of cache elements.  Last entry is element
81       * which has been used most recently.
82       */
83      CacheEntry _last;
84  
85  
86      /**
87       * Cache eviction listeners
88       */
89      Vector listeners = new Vector();
90  
91  
92      /**
93       * Construct an MRU with a given maximum number of objects.
94       */
95      public MRU(int max) {
96          if (max <= 0) {
97              throw new IllegalArgumentException("MRU cache must contain at least one entry");
98          }
99          _max = max;
100     }
101 
102 
103     /**
104      * Place an object in the cache.
105      */
106     public void put(Object key, Object value) throws CacheEvictionException {
107         CacheEntry entry = (CacheEntry)_hash.get(key);
108         if (entry != null) {
109             entry.setValue(value);
110             touchEntry(entry);
111         } else {
112 
113             if (_hash.size() == _max) {
114                 // purge and recycle entry
115                 entry = purgeEntry();
116                 entry.setKey(key);
117                 entry.setValue(value);
118             } else {
119                 entry = new CacheEntry(key, value);
120             }
121             addEntry(entry);
122             _hash.put(entry.getKey(), entry);
123         }
124     }
125 
126 
127     /**
128      * Obtain an object in the cache
129      */
130     public Object get(Object key) {
131         CacheEntry entry = (CacheEntry)_hash.get(key);
132         if (entry != null) {
133             touchEntry(entry);
134             return entry.getValue();
135         } else {
136             return null;
137         }
138     }
139 
140 
141     /**
142      * Remove an object from the cache
143      */
144     public void remove(Object key) {
145         CacheEntry entry = (CacheEntry)_hash.get(key);
146         if (entry != null) {
147             removeEntry(entry);
148             _hash.remove(entry.getKey());
149         }
150     }
151 
152 
153     /**
154      * Remove all objects from the cache
155      */
156     public void removeAll() {
157         _hash = new Hashtable();
158         _first = null;
159         _last = null;
160     }
161 
162 
163     /**
164      * Enumerate elements' values in the cache
165      */
166     public Enumeration elements() {
167         return new MRUEnumeration(_hash.elements());
168     }
169 
170     /**
171      * Add a listener to this cache policy
172      *
173      * @param listener Listener to add to this policy
174      */
175     public void addListener(CachePolicyListener listener) {
176         if (listener == null) {
177             throw new IllegalArgumentException("Cannot add null listener.");
178         }
179         if ( ! listeners.contains(listener)) {
180             listeners.addElement(listener);
181         }
182     }
183 
184     /**
185      * Remove a listener from this cache policy
186      *
187      * @param listener Listener to remove from this policy
188      */
189     public void removeListener(CachePolicyListener listener) {
190         listeners.removeElement(listener);
191     }
192 
193     /**
194      * Add a CacheEntry.  Entry goes at the end of the list.
195      */
196     protected void addEntry(CacheEntry entry) {
197         if (_first == null) {
198             _first = entry;
199             _last = entry;
200         } else {
201             _last.setNext(entry);
202             entry.setPrevious(_last);
203             _last = entry;
204         }
205     }
206 
207 
208     /**
209      * Remove a CacheEntry from linked list
210      */
211     protected void removeEntry(CacheEntry entry) {
212         if (entry == _first) {
213             _first = entry.getNext();
214         }
215         if (_last == entry) {
216             _last = entry.getPrevious();
217         }
218         CacheEntry previous = entry.getPrevious();
219         CacheEntry next = entry.getNext();
220         if (previous != null) {
221             previous.setNext(next);
222         }
223         if (next != null) {
224             next.setPrevious(previous);
225         }
226         entry.setPrevious(null);
227         entry.setNext(null);
228     }
229 
230     /**
231      * Place entry at the end of linked list -- Most Recently Used
232      */
233     protected void touchEntry(CacheEntry entry) {
234         if (_last == entry) {
235             return;
236         }
237         removeEntry(entry);
238         addEntry(entry);
239     }
240 
241     /**
242      * Purge least recently used object from the cache
243      *
244      * @return recyclable CacheEntry
245      */
246     protected CacheEntry purgeEntry() throws CacheEvictionException {
247         CacheEntry entry = _first;
248 
249         // Notify policy listeners first. if any of them throw an
250         // eviction exception, then the internal data structure
251         // remains untouched.
252         CachePolicyListener listener;
253         for (int i=0; i<listeners.size(); i++) {
254             listener = (CachePolicyListener)listeners.elementAt(i);
255             listener.cacheObjectEvicted(entry.getValue());
256         }
257 
258         removeEntry(entry);
259         _hash.remove(entry.getKey());
260 
261         entry.setValue(null);
262         return entry;
263     }
264 
265 }
266 
267 /**
268  * State information for cache entries.
269  */
270 class CacheEntry {
271     private Object _key;
272     private Object _value;
273 
274     private CacheEntry _previous;
275     private CacheEntry _next;
276 
277     CacheEntry(Object key, Object value) {
278         _key = key;
279         _value = value;
280     }
281 
282     Object getKey() {
283         return _key;
284     }
285 
286     void setKey(Object obj) {
287         _key = obj;
288     }
289 
290     Object getValue() {
291         return _value;
292     }
293 
294     void setValue(Object obj) {
295         _value = obj;
296     }
297 
298     CacheEntry getPrevious() {
299         return _previous;
300     }
301 
302     void setPrevious(CacheEntry entry) {
303         _previous = entry;
304     }
305 
306     CacheEntry getNext() {
307         return _next;
308     }
309 
310     void setNext(CacheEntry entry) {
311         _next = entry;
312     }
313 }
314 
315 /**
316  * Enumeration wrapper to return actual user objects instead of
317  * CacheEntries.
318  */
319 class MRUEnumeration implements Enumeration {
320     Enumeration _enum;
321 
322     MRUEnumeration(Enumeration enume) {
323         _enum = enume;
324     }
325 
326     public boolean hasMoreElements() {
327         return _enum.hasMoreElements();
328     }
329 
330     public Object nextElement() {
331         CacheEntry entry = (CacheEntry)_enum.nextElement();
332         return entry.getValue();
333     }
334 }