001 /*
002 *
003 * $Revision: 15000 $ $Date: 2009-03-24 16:42:03 +0100 (Tue, 24 Mar 2009) $
004 *
005 * This file is part of *** M y C o R e ***
006 * See http://www.mycore.de/ for details.
007 *
008 * This program is free software; you can use it, redistribute it
009 * and / or modify it under the terms of the GNU General Public License
010 * (GPL) as published by the Free Software Foundation; either version 2
011 * of the License or (at your option) any later version.
012 *
013 * This program is distributed in the hope that it will be useful, but
014 * WITHOUT ANY WARRANTY; without even the implied warranty of
015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
016 * GNU General Public License for more details.
017 *
018 * You should have received a copy of the GNU General Public License
019 * along with this program, in a file called gpl.txt or license.txt.
020 * If not, write to the Free Software Foundation Inc.,
021 * 59 Temple Place - Suite 330, Boston, MA 02111-1307 USA
022 */
023
024 package org.mycore.common;
025
026 import java.util.Collections;
027 import java.util.Hashtable;
028 import java.util.List;
029
030 import org.mycore.services.mbeans.MCRJMXBridge;
031
032 /**
033 * Instances of this class can be used as object cache. Each MCRCache has a
034 * certain capacity, the maximum number of objects the cache will hold. When the
035 * cache is full and another object is put into the cache, the cache will
036 * discard the least recently used object to get place for the new object. The
037 * cache will always hold the most recently used objects by updating its
038 * internal structure whenever an object is get from the cache or put into the
039 * cache. The cache also provides methods for getting the current cache hit rate
040 * and fill rate. Like in a hashtable, an MCRCache uses a unique key for each
041 * object.
042 *
043 * @see java.util.Hashtable
044 *
045 * @author Frank Lützenkirchen
046 * @version $Revision: 15000 $ $Date: 2009-03-24 16:42:03 +0100 (Tue, 24 Mar 2009) $
047 */
048 public class MCRCache {
049 /**
050 * For each object in the cache, there is one MCRCacheEntry object
051 * encapsulating it. The cache uses a double-linked list of MCRCacheEntries
052 * and holds references to the most and least recently used entry.
053 */
054 class MCRCacheEntry {
055 /** The entry before this one, more often used than this entry */
056 MCRCacheEntry before;
057
058 /** The entry after this one, less often used than this entry */
059 MCRCacheEntry after;
060
061 /** The key for this object, to be used for removing the object */
062 Object key;
063
064 /** The timestamp when this object was placed in the cache */
065 long time;
066
067 /** The stored object encapsulated by this entry */
068 Object object;
069 }
070
071 /** The most recently used object * */
072 protected MCRCacheEntry mru;
073
074 /** The least recently used object * */
075 protected MCRCacheEntry lru;
076
077 /** A hashtable for looking up a cached object by a given key */
078 protected Hashtable<Object,MCRCacheEntry> index = new Hashtable<Object,MCRCacheEntry>();
079
080 /** The number of requests to get an object from this cache */
081 protected long gets = 0;
082
083 /** The number of hits, where a requested object really was in the cache */
084 protected long hits = 0;
085
086 /** The number of objects currently stored in the cache */
087 protected int size = 0;
088
089 /** The maximum number of objects that the cache can hold */
090 protected int capacity;
091
092 /** Tch type string for the MCRCacheJMXBridge */
093 protected String type;
094
095 /** The constructor */
096 private MCRCache(){};
097
098 /**
099 * Creates a new cache with a given capacity.
100 *
101 * @param capacity
102 * the maximum number of objects this cache will hold
103 * @param type the type string for MCRCacheJMXBridge
104 */
105 public MCRCache(int capacity, String type) {
106 setCapacity(capacity);
107 this.type=type;
108 Object mbean = new MCRCacheManager(this);
109 MCRJMXBridge.register(mbean, "MCRCache", type);
110 }
111
112 /**
113 * Puts an object into the cache, storing it under the given key. If the
114 * cache is already full, the least recently used object will be removed
115 * from the cache first. If the cache already contains an entry under the
116 * key provided, this entry is replaced.
117 *
118 * @param key
119 * the non-null key to store the object under
120 * @param obj
121 * the non-null object to be put into the cache
122 */
123 public synchronized void put(Object key, Object obj) {
124 if (key == null) {
125 throw new MCRUsageException("The value of the argument key is null.");
126 }
127 if (obj == null) {
128 throw new MCRUsageException("The value of the argument obj is null.");
129 }
130
131 if (capacity == 0) {
132 return;
133 }
134
135 if (index.containsKey(key)) {
136 remove(key);
137 }
138
139 if (isFull()) {
140 remove(lru.key);
141 }
142
143 MCRCacheEntry added = new MCRCacheEntry();
144 added.object = obj;
145 added.key = key;
146 added.time = System.currentTimeMillis();
147 index.put(key, added);
148
149 if (isEmpty()) {
150 lru = mru = added;
151 } else {
152 added.before = mru;
153 mru.after = added;
154 }
155
156 size++;
157 mru = added;
158 }
159
160 /**
161 * Removes an object from the cache for the given key.
162 *
163 * @param key
164 * the key for the object you want to remove from this cache
165 */
166 public synchronized void remove(Object key) {
167 if (key == null) {
168 throw new MCRUsageException("The value of the argument key is null.");
169 }
170
171 if (!index.containsKey(key)) {
172 return;
173 }
174
175 MCRCacheEntry removed = (MCRCacheEntry) (index.get(key));
176
177 if (removed == lru) {
178 lru = removed.after;
179 } else {
180 removed.before.after = removed.after;
181 }
182
183 if (removed == mru) {
184 mru = removed.before;
185 } else {
186 removed.after.before = removed.before;
187 }
188
189 removed.object = null;
190 removed.key = null;
191 removed.time = 0;
192 removed.before = null;
193 removed.after = null;
194 index.remove(key);
195 size--;
196 }
197
198 /**
199 * Returns an object from the cache for the given key, or null if there
200 * currently is no object in the cache with this key.
201 *
202 * @param key
203 * the key for the object you want to get from this cache
204 * @return the cached object, or null
205 */
206 public synchronized Object get(Object key) {
207 if (key == null) {
208 throw new MCRUsageException("The value of the argument key is null.");
209 }
210
211 gets++;
212
213 if (!index.containsKey(key)) {
214 return null;
215 }
216
217 hits++;
218
219 MCRCacheEntry found = (MCRCacheEntry) (index.get(key));
220
221 if (found != mru) {
222 found.after.before = found.before;
223
224 if (found == lru) {
225 lru = found.after;
226 } else {
227 found.before.after = found.after;
228 }
229
230 found.after = null;
231 found.before = mru;
232 mru.after = found;
233 mru = found;
234 }
235
236 return found.object;
237 }
238
239 /**
240 * Returns an object from the cache for the given key, but only if the cache
241 * entry is not older than the given timestamp. If there currently is no
242 * object in the cache with this key, null is returned. If the cache entry
243 * is older than the timestamp, the entry is removed from the cache and null
244 * is returned.
245 *
246 * @param key
247 * the key for the object you want to get from this cache
248 * @param time
249 * the timestamp to check that the cache entry is up to date
250 * @return the cached object, or null
251 */
252 public synchronized Object getIfUpToDate(Object key, long time) {
253 Object value = get(key);
254
255 if (value == null) {
256 return null;
257 }
258
259 MCRCacheEntry found = (MCRCacheEntry) (index.get(key));
260
261 if (found.time >= time) {
262 return value;
263 }
264
265 remove(key);
266
267 return null;
268 }
269
270 /**
271 * Returns the number of objects currently cached.
272 *
273 * @return the number of objects currently cached
274 */
275 public synchronized int getCurrentSize() {
276 return size;
277 }
278
279 /**
280 * Returns the capacity of this cache. This is the maximum number of objects
281 * this cache will hold at a time.
282 *
283 * @return the capacity of this cache
284 */
285 public synchronized int getCapacity() {
286 return capacity;
287 }
288
289 /**
290 * Changes the capacity of this cache. This is the maximum number of objects
291 * that will be cached at a time. If the new capacity is smaller than the
292 * current number of objects in the cache, the least recently used objects
293 * will be removed from the cache.
294 *
295 * @param capacity
296 * the maximum number of objects this cache will hold
297 */
298 public synchronized void setCapacity(int capacity) {
299 if (capacity < 0) {
300 throw new MCRUsageException("The cache capacity must be >= 0.");
301 }
302
303 while (size > capacity)
304 remove(lru.key);
305
306 this.capacity = capacity;
307 }
308
309 /**
310 * Returns true if this cache is full.
311 *
312 * @return true if this cache is full
313 */
314 public synchronized boolean isFull() {
315 return (size == capacity);
316 }
317
318 /**
319 * Returns true if this cache is empty.
320 *
321 * @return true if this cache is empty
322 */
323 public synchronized boolean isEmpty() {
324 return (size == 0);
325 }
326
327 /**
328 * Returns the fill rate of this cache. This is the current number of
329 * objects in the cache diveded by its capacity.
330 *
331 * @return the fill rate of this cache as double value
332 */
333 public synchronized double getFillRate() {
334 return ((capacity == 0) ? 1.0 : ((double) size / (double) capacity));
335 }
336
337 /**
338 * Returns the hit rate of this cache. This is the number of successful hits
339 * divided by the total number of get requests so far. Using this ratio can
340 * help finding the appropriate cache capacity.
341 *
342 * @return the hit rate of this cache as double value
343 */
344 public synchronized double getHitRate() {
345 return ((gets == 0) ? 1.0 : ((double) hits / (double) gets));
346 }
347
348 /**
349 * Clears the cache by removing all entries from the cache
350 */
351 public synchronized void clear() {
352 index = new Hashtable<Object,MCRCacheEntry>();
353 size = 0;
354 mru = lru = null;
355 }
356
357 /**
358 * Returns a String containing information about cache capacity, size,
359 * current fill rate and hit rate. Useful for testing and debugging.
360 */
361 public String toString() {
362 StringBuffer sb = new StringBuffer();
363 sb.append("Cache capacity: ").append(capacity).append("\n");
364 sb.append("Cache size: ").append(size).append("\n");
365 sb.append("Cache fill rate: ").append(getFillRate()).append("\n");
366 sb.append("Cache hit rate: ").append(getHitRate());
367
368 return sb.toString();
369 }
370
371 /**
372 * A small sample program for testing this class.
373 */
374 public static void main(String[] args) {
375 MCRCache cache = new MCRCache(4, "Small Sample Program");
376 System.out.println(cache);
377 cache.put("a", "Anton");
378 cache.put("b", "Bohnen");
379 cache.put("c", "Cache");
380 System.out.println(cache);
381 cache.get("d");
382 cache.get("c");
383 cache.put("d", "Dieter");
384 cache.put("e", "Egon");
385 cache.put("f", "Frank");
386 cache.get("c");
387 System.out.println(cache);
388 }
389
390 public void close() {
391 MCRJMXBridge.unregister("MCRCache", this.type);
392 clear();
393 }
394
395
396 /**
397 * Returns an iterable list of keys to the cached objects.
398 */
399 public List<Object> keys(){
400 return Collections.list(index.keys());
401 }
402 }