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 }