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  ;
29  import java.util.Collections  ;
30  import java.util.HashMap  ;
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   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  (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   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   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   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  [] 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  (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   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
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags