KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > nemesis > forum > util > cache > Cache


1 /*
2  * NEMESIS-FORUM.
3  * Copyright (C) 2002 David Laurent(lithium2@free.fr). All rights reserved.
4  *
5  * Copyright (c) 2000 The Apache Software Foundation. All rights reserved.
6  *
7  * Copyright (C) 2001 Yasna.com. All rights reserved.
8  *
9  * Copyright (C) 2000 CoolServlets.com. All rights reserved.
10  *
11  * NEMESIS-FORUM. is free software; you can redistribute it and/or
12  * modify it under the terms of the Apache Software License, Version 1.1,
13  * or (at your option) any later version.
14  *
15  * NEMESIS-FORUM core framework, NEMESIS-FORUM backoffice, NEMESIS-FORUM frontoffice
16  * application are parts of NEMESIS-FORUM and are distributed under
17  * same terms of licence.
18  *
19  *
20  * NEMESIS-FORUM includes software developed by the Apache Software Foundation (http://www.apache.org/)
21  * and software developed by CoolServlets.com (http://www.coolservlets.com).
22  * and software developed by Yasna.com (http://www.yasna.com).
23  *
24  */

25
26 package org.nemesis.forum.util.cache;
27
28 import java.util.Collection JavaDoc;
29 import java.util.Collections JavaDoc;
30 import java.util.HashMap JavaDoc;
31
32 import org.nemesis.forum.util.LinkedList;
33 import org.nemesis.forum.util.LinkedListNode;
34
35
36 public class Cache implements Cacheable {
37
38     /**
39      * One of the major potential bottlenecks of the cache is performing
40      * System.currentTimeMillis() for every cache get operation. Instead,
41      * we maintain a global timestamp that gets updated once a second. This
42      * means that cache expirations can be no more than one second accurate.
43      */

44     protected static long currentTime = System.currentTimeMillis();
45
46     /**
47      * A cache timer updates the current time once a second in a seperate
48      * thread.
49      */

50     protected static CacheTimer timer = new CacheTimer(1000L);
51
52     /**
53      * Maintains the hash of cached objects. Hashing provides the best
54      * performance for fast lookups.
55      */

56     protected HashMap JavaDoc cachedObjectsHash;
57
58     /**
59      * Linked list to maintain order that cache objects are accessed
60      * in, most used to least used.
61      */

62     protected LinkedList lastAccessedList;
63
64     /**
65      * Linked list to maintain time that cache objects were initially added
66      * to the cache, most recently added to oldest added.
67      */

68     protected LinkedList ageList;
69
70     /**
71      * Maximum size in bytes that the cache can grow to. Default
72      * maximum size is 128 K.
73      */

74     protected int maxSize = 128 * 1024;
75
76     /**
77      * Maintains the current size of the cache in bytes.
78      */

79     protected int size = 0;
80
81     /**
82      * Maximum length of time objects can exist in cache before expiring.
83      * Default is that objects have no maximum lifetime.
84      */

85     protected long maxLifetime = -1;
86
87     /**
88      * Maintain the number of cache hits and misses. A cache hit occurs every
89      * time the get method is called and the cache contains the requested
90      * object. A cache miss represents the opposite occurence.<p>
91      *
92      * Keeping track of cache hits and misses lets one measure how efficient
93      * the cache is; the higher the percentage of hits, the more efficient.
94      */

95     protected long cacheHits, cacheMisses = 0L;
96
97     /**
98      * Create a new cache with default values. Default cache size is 128K with
99      * no maximum lifetime.
100      */

101     public Cache() {
102         //Our primary data structure is a hash map. The default capacity of 11
103
//is too small in almost all cases, so we set it bigger.
104
cachedObjectsHash = new HashMap JavaDoc(103);
105
106         lastAccessedList = new LinkedList();
107         ageList = new LinkedList();
108     }
109
110     /**
111      * Create a new cache and specify the maximum size for the cache in bytes.
112      * Items added to the cache will have no maximum lifetime.
113      *
114      * @param maxSize the maximum size of the cache in bytes.
115      */

116     public Cache(int maxSize) {
117         this();
118         this.maxSize = maxSize;
119     }
120
121     /**
122      * Create a new cache and specify the maximum lifetime of objects. The
123      * time should be specified in milleseconds. The minimum lifetime of any
124      * cache object is 1000 milleseconds (1 second). Additionally, cache
125      * expirations have a 1000 millesecond resolution, which means that all
126      * objects are guaranteed to be expired within 1000 milliseconds of their
127      * maximum lifetime.
128      *
129      * @param maxLifetime the maximum amount of time objects can exist in
130      * cache before being deleted.
131      */

132     public Cache(long maxLifetime) {
133         this();
134         this.maxLifetime = maxLifetime;
135     }
136
137     /**
138      * Create a new cache and specify the maximum size of for the cache in
139      * bytes, and the maximum lifetime of objects.
140      *
141      * @param maxSize the maximum size of the cache in bytes.
142      * @param maxLifetime the maximum amount of time objects can exist in
143      * cache before being deleted.
144      */

145     public Cache(int maxSize, long maxLifetime) {
146         this();
147         this.maxSize = maxSize;
148         this.maxLifetime = maxLifetime;
149     }
150
151     /**
152      * Returns the current size of the cache in bytes.
153      *
154      * @return the size of the cache in bytes.
155      */

156     public int getSize() {
157         return size;
158     }
159
160     /**
161      * Returns the maximum size of the cache in bytes. If the cache grows too
162      * large, the least frequently used items will automatically be deleted so
163      * that the cache size doesn't exceed the maximum.
164      *
165      * @return the maximum size of the cache in bytes.
166      */

167     public int getMaxSize() {
168         return maxSize;
169     }
170
171     /**
172      * Sets the maximum size of the cache in bytes. If the cache grows too
173      * large, the least frequently used items will automatically be deleted so
174      * that the cache size doesn't exceed the maximum.
175      *
176      * @param maxSize the maximum size of the cache in bytes.
177      */

178     public void setMaxSize(int maxSize) {
179         this.maxSize = maxSize;
180         //It's possible that the new max size is smaller than our current cache
181
//size. If so, we need to delete infrequently used items.
182
cullCache();
183     }
184
185     /**
186      * Returns the number of objects in the cache.
187      *
188      * @return the number of objects in the cache.
189      */

190     public synchronized int getNumElements() {
191         return cachedObjectsHash.size();
192     }
193
194     /**
195      * Adds a new Cacheable object to the cache. The key must be unique.
196      *
197      * @param key a unique key for the object being put into cache.
198      * @param object the Cacheable object to put into cache.
199      */

200     public synchronized void add(Object JavaDoc key, Cacheable object) {
201         
202         //Don't add an object with the same key multiple times.
203
if (cachedObjectsHash.containsKey(key)) {
204             return;
205         }
206         int objectSize = object.getSize();
207         //If the object is bigger than the entire cache, simply don't add it.
208
if (objectSize > maxSize * .90) {
209             return;
210         }
211         size += objectSize;
212         CacheObject cacheObject = new CacheObject(object, objectSize);
213         cachedObjectsHash.put(key, cacheObject);
214         //Make an entry into the cache order list.
215
LinkedListNode lastAccessedNode = lastAccessedList.addFirst(key);
216         //Store the cache order list entry so that we can get back to it
217
//during later lookups.
218
cacheObject.lastAccessedListNode = lastAccessedNode;
219         //Add the object to the age list
220
LinkedListNode ageNode = ageList.addFirst(key);
221         //We make an explicit call to currentTimeMillis() so that total accuracy
222
//of lifetime calculations is better than one second.
223
ageNode.timestamp = System.currentTimeMillis();
224         cacheObject.ageListNode = ageNode;
225
226         //If cache is too full, remove least used cache entries until it is
227
//not too full.
228
cullCache();
229     }
230
231     /**
232      * Gets an object from cache. This method will return null under two
233      * conditions:<ul>
234      * <li>The object referenced by the key was never added to cache.
235      * <li>The object referenced by the key has expired from cache.</ul>
236      *
237      * @param key the unique key of the object to get.
238      * @return the Cacheable object corresponding to unique key.
239      */

240     public synchronized Cacheable get(Object JavaDoc key) {
241         //First, clear all entries that have been in cache longer than the
242
//maximum defined age.
243
deleteExpiredEntries();
244
245         CacheObject cacheObject = (CacheObject) cachedObjectsHash.get(key);
246         if (cacheObject == null) {
247             //The object didn't exist in cache, so increment cache misses.
248
cacheMisses++;
249             return null;
250         }
251
252         //The object exists in cache, so increment cache hits.
253
cacheHits++;
254
255         //Remove the object from it's current place in the cache order list,
256
//and re-insert it at the front of the list.
257
cacheObject.lastAccessedListNode.remove();
258         lastAccessedList.addFirst(cacheObject.lastAccessedListNode);
259
260         return cacheObject.object;
261     }
262
263     /**
264      * Removes an object from cache.
265      *
266      * @param key the unique key of the object to remove.
267      */

268     public synchronized void remove(Object JavaDoc key) {
269         
270         CacheObject cacheObject = (CacheObject) cachedObjectsHash.get(key);
271         //If the object is not in cache, stop trying to remove it.
272
if (cacheObject == null) {
273             return;
274         }
275         //remove from the hash map
276
cachedObjectsHash.remove(key);
277         //remove from the cache order list
278
cacheObject.lastAccessedListNode.remove();
279         cacheObject.ageListNode.remove();
280         //remove references to linked list nodes
281
cacheObject.ageListNode = null;
282         cacheObject.lastAccessedListNode = null;
283         //removed the object, so subtract its size from the total.
284
size -= cacheObject.size;
285     }
286
287     /**
288      * Clears the cache of all objects. The size of the cache is reset to 0.
289      */

290     public synchronized void clear() {
291         
292         Object JavaDoc[] keys = cachedObjectsHash.keySet().toArray();
293         for (int i = 0; i < keys.length; i++) {
294             remove(keys[i]);
295         }
296
297         //Now, reset all containers.
298
cachedObjectsHash.clear();
299         cachedObjectsHash = new HashMap JavaDoc(103);
300         lastAccessedList.clear();
301         lastAccessedList = new LinkedList();
302         ageList.clear();
303         ageList = new LinkedList();
304
305         size = 0;
306         cacheHits = 0;
307         cacheMisses = 0;
308     }
309
310     /**
311      * Returns a collection view of the values contained in the cache.
312      * The Collection is unmodifiable to prevent cache integrity issues.
313      *
314      * @return a Collection of the cache entries.
315      */

316     public Collection JavaDoc values() {
317         return Collections.unmodifiableCollection(cachedObjectsHash.values());
318     }
319
320     /**
321      * Returns the number of cache hits. A cache hit occurs every
322      * time the get method is called and the cache contains the requested
323      * object.<p>
324      *
325      * Keeping track of cache hits and misses lets one measure how efficient
326      * the cache is; the higher the percentage of hits, the more efficient.
327      *
328      * @return the number of cache hits.
329      */

330     public long getCacheHits() {
331         return cacheHits;
332     }
333
334     /**
335      * Returns the number of cache misses. A cache miss occurs every
336      * time the get method is called and the cache does not contain the
337      * requested object.<p>
338      *
339      * Keeping track of cache hits and misses lets one measure how efficient
340      * the cache is; the higher the percentage of hits, the more efficient.
341      *
342      * @return the number of cache hits.
343      */

344     public long getCacheMisses() {
345         return cacheMisses;
346     }
347
348     /**
349      * Clears all entries out of cache where the entries are older than the
350      * maximum defined age.
351      */

352     private final void deleteExpiredEntries() {
353         //Check if expiration is turned on.
354
if (maxLifetime <= 0) {
355             return;
356         }
357
358         //Remove all old entries. To do this, we remove objects from the end
359
//of the linked list until they are no longer too old. We get to avoid
360
//any hash lookups or looking at any more objects than is strictly
361
//neccessary.
362
LinkedListNode node = ageList.getLast();
363         //If there are no entries in the age list, return.
364
if (node == null) {
365             return;
366         }
367
368         //Determine the expireTime, which is the moment in time that elements
369
//should expire from cache. Then, we can do an easy to check to see
370
//if the expire time is greater than the expire time.
371
long expireTime = currentTime - maxLifetime;
372
373         while (expireTime > node.timestamp) {
374             
375             //Remove the object
376
remove(node.object);
377
378             //Get the next node.
379
node = ageList.getLast();
380             //If there are no more entries in the age list, return.
381
if (node == null) {
382                 return;
383             }
384         }
385     }
386
387     /**
388      * Removes objects from cache if the cache is too full. "Too full" is
389      * defined as within 3% of the maximum cache size. Whenever the cache is
390      * is too big, the least frequently used elements are deleted until the
391      * cache is at least 10% empty.
392      */

393     private final void cullCache() {
394         //See if the cache size is within 3% of being too big. If so, clean out
395
//cache until it's 10% free.
396
if (size >= maxSize * .97) {
397             //First, delete any old entries to see how much memory that frees.
398
deleteExpiredEntries();
399             int desiredSize = (int) (maxSize * .90);
400             while (size > desiredSize) {
401                 //Get the key and invoke the remove method on it.
402
remove(lastAccessedList.getLast().object);
403             }
404         }
405     }
406 }
407
Popular Tags