001: /**
002: * $RCSfile: Cache.java,v $
003: * $Revision: 1.3 $
004: * $Date: 2006/01/07 00:21:06 $
005: *
006: * Copyright (C) 2000 CoolServlets.com. All rights reserved.
007: *
008: * ===================================================================
009: * The Apache Software License, Version 1.1
010: *
011: * Redistribution and use in source and binary forms, with or without
012: * modification, are permitted provided that the following conditions
013: * are met:
014: *
015: * 1. Redistributions of source code must retain the above copyright
016: * notice, this list of conditions and the following disclaimer.
017: *
018: * 2. Redistributions in binary form must reproduce the above copyright
019: * notice, this list of conditions and the following disclaimer in
020: * the documentation and/or other materials provided with the
021: * distribution.
022: *
023: * 3. The end-user documentation included with the redistribution,
024: * if any, must include the following acknowledgment:
025: * "This product includes software developed by
026: * CoolServlets.com (http://www.Yasna.com)."
027: * Alternately, this acknowledgment may appear in the software itself,
028: * if and wherever such third-party acknowledgments normally appear.
029: *
030: * 4. The names "Jive" and "CoolServlets.com" must not be used to
031: * endorse or promote products derived from this software without
032: * prior written permission. For written permission, please
033: * contact webmaster@Yasna.com.
034: *
035: * 5. Products derived from this software may not be called "Jive",
036: * nor may "Jive" appear in their name, without prior written
037: * permission of CoolServlets.com.
038: *
039: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
040: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
041: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
042: * DISCLAIMED. IN NO EVENT SHALL COOLSERVLETS.COM OR
043: * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
044: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
045: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
046: * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
047: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
048: * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
049: * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
050: * SUCH DAMAGE.
051: * ====================================================================
052: *
053: * This software consists of voluntary contributions made by many
054: * individuals on behalf of CoolServlets.com. For more information
055: * on CoolServlets.com, please see <http://www.Yasna.com>.
056: */package com.Yasna.util;
057:
058: import java.util.*;
059: import com.Yasna.util.LinkedList;
060:
061: /**
062: * General purpose cache implementation. It stores objects associated with
063: * unique keys in memory for fast access. All objects added to the cache must
064: * implement the Cacheable interface, which requires objects to know their
065: * size in memory. This restrictions allows the cache to never grow larger
066: * than a specified amount.<p>
067: *
068: * If the cache does grow too large, objects will be removed such that those
069: * that are accessed least frequently are removed first. Because expiration
070: * happens automatically, the cache makes <b>no</b> gaurantee as to how long
071: * an object will remain in cache after it is put in. The cache will return
072: * null if the requested object is not found.<p>
073: *
074: * Optionally, a maximum lifetime for all objects can be specified. In that
075: * case, objects will be deleted from cache after that amount of time, even
076: * if they are frequently accessed. This feature is useful if objects put in
077: * cache represent data that should be periodically refreshed; for example,
078: * information from a database.<p>
079: *
080: * Cache is optimized for fast data access. The getObject() method has 0(n)
081: * performance regardless of cache size. The other cache operations also
082: * perform quite fast.<p>
083: *
084: * Cache objects are thread safe.<p>
085: *
086: * The algorithm for cache is as follows: a HashMap is maintained for fast
087: * object lookup. Two linked lists are maintained: one keeps objects in the
088: * order they are accessed from cache, the other keeps objects in the order
089: * they were originally added to cache. When objects are added to cache, they
090: * are first wrapped by a CacheObject which maintains the following pieces
091: * of information:<ul>
092: * <li> The size of the object (in bytes).
093: * <li> A pointer to the node in the linked list that maintains accessed
094: * order for the object. Keeping a reference to the node lets us avoid
095: * linear scans of the linked list.
096: * <li> A pointer to the node in the linked list that maintains the age
097: * of the object in cache. Keeping a reference to the node lets us avoid
098: * linear scans of the linked list.</ul>
099: *
100: * To get an object from cache, a hash lookup is performed to get a reference
101: * to the CacheObject that wraps the real object we are looking for.
102: * The object is subsequently moved to the front of the accessed linked list
103: * and any necessary cache cleanups are performed. Cache deletion and expiration
104: * is performed as needed.
105: *
106: * @see Cacheable
107: */
108: public class Cache implements Cacheable {
109:
110: /**
111: * One of the major potential bottlenecks of the cache is performing
112: * System.currentTimeMillis() for every cache get operation. Instead,
113: * we maintain a global timestamp that gets updated once a second. This
114: * means that cache expirations can be no more than one second accurate.
115: */
116: protected static long currentTime = System.currentTimeMillis();
117:
118: /**
119: * A cache timer updates the current time once a second in a seperate
120: * thread.
121: */
122: protected static CacheTimer timer = new CacheTimer(1000L);
123:
124: /**
125: * Maintains the hash of cached objects. Hashing provides the best
126: * performance for fast lookups.
127: */
128: protected HashMap cachedObjectsHash;
129:
130: /**
131: * Linked list to maintain order that cache objects are accessed
132: * in, most used to least used.
133: */
134: protected LinkedList lastAccessedList;
135:
136: /**
137: * Linked list to maintain time that cache objects were initially added
138: * to the cache, most recently added to oldest added.
139: */
140: protected LinkedList ageList;
141:
142: /**
143: * Maximum size in bytes that the cache can grow to. Default
144: * maximum size is 128 K.
145: */
146: protected int maxSize = 128 * 1024;
147:
148: /**
149: * Maintains the current size of the cache in bytes.
150: */
151: protected int size = 0;
152:
153: /**
154: * Maximum length of time objects can exist in cache before expiring.
155: * Default is that objects have no maximum lifetime.
156: */
157: protected long maxLifetime = -1;
158:
159: /**
160: * Maintain the number of cache hits and misses. A cache hit occurs every
161: * time the get method is called and the cache contains the requested
162: * object. A cache miss represents the opposite occurence.<p>
163: *
164: * Keeping track of cache hits and misses lets one measure how efficient
165: * the cache is; the higher the percentage of hits, the more efficient.
166: */
167: protected long cacheHits, cacheMisses = 0L;
168:
169: /**
170: * Create a new cache with default values. Default cache size is 128K with
171: * no maximum lifetime.
172: */
173: public Cache() {
174: //Our primary data structure is a hash map. The default capacity of 11
175: //is too small in almost all cases, so we set it bigger.
176: cachedObjectsHash = new HashMap(103);
177:
178: lastAccessedList = new LinkedList();
179: ageList = new LinkedList();
180: }
181:
182: /**
183: * Create a new cache and specify the maximum size for the cache in bytes.
184: * Items added to the cache will have no maximum lifetime.
185: *
186: * @param maxSize the maximum size of the cache in bytes.
187: */
188: public Cache(int maxSize) {
189: this ();
190: this .maxSize = maxSize;
191: }
192:
193: /**
194: * Create a new cache and specify the maximum lifetime of objects. The
195: * time should be specified in milleseconds. The minimum lifetime of any
196: * cache object is 1000 milleseconds (1 second). Additionally, cache
197: * expirations have a 1000 millesecond resolution, which means that all
198: * objects are guaranteed to be expired within 1000 milliseconds of their
199: * maximum lifetime.
200: *
201: * @param maxLifetime the maximum amount of time objects can exist in
202: * cache before being deleted.
203: */
204: public Cache(long maxLifetime) {
205: this ();
206: this .maxLifetime = maxLifetime;
207: }
208:
209: /**
210: * Create a new cache and specify the maximum size of for the cache in
211: * bytes, and the maximum lifetime of objects.
212: *
213: * @param maxSize the maximum size of the cache in bytes.
214: * @param maxLifetime the maximum amount of time objects can exist in
215: * cache before being deleted.
216: */
217: public Cache(int maxSize, long maxLifetime) {
218: this ();
219: this .maxSize = maxSize;
220: this .maxLifetime = maxLifetime;
221: }
222:
223: /**
224: * Returns the current size of the cache in bytes.
225: *
226: * @return the size of the cache in bytes.
227: */
228: public int getSize() {
229: return size;
230: }
231:
232: /**
233: * Returns the maximum size of the cache in bytes. If the cache grows too
234: * large, the least frequently used items will automatically be deleted so
235: * that the cache size doesn't exceed the maximum.
236: *
237: * @return the maximum size of the cache in bytes.
238: */
239: public int getMaxSize() {
240: return maxSize;
241: }
242:
243: /**
244: * Sets the maximum size of the cache in bytes. If the cache grows too
245: * large, the least frequently used items will automatically be deleted so
246: * that the cache size doesn't exceed the maximum.
247: *
248: * @param maxSize the maximum size of the cache in bytes.
249: */
250: public void setMaxSize(int maxSize) {
251: this .maxSize = maxSize;
252: //It's possible that the new max size is smaller than our current cache
253: //size. If so, we need to delete infrequently used items.
254: cullCache();
255: }
256:
257: /**
258: * Returns the number of objects in the cache.
259: *
260: * @return the number of objects in the cache.
261: */
262: public synchronized int getNumElements() {
263: return cachedObjectsHash.size();
264: }
265:
266: /**
267: * Adds a new Cacheable object to the cache. The key must be unique.
268: *
269: * @param key a unique key for the object being put into cache.
270: * @param object the Cacheable object to put into cache.
271: */
272: public synchronized void add(Object key, Cacheable object) {
273: //DEBUG
274: //System.err.println("Adding object with key " + key + " to hash " + this);
275:
276: //Don't add an object with the same key multiple times.
277: if (cachedObjectsHash.containsKey(key)) {
278: return;
279: }
280: int objectSize = object.getSize();
281: //If the object is bigger than the entire cache, simply don't add it.
282: if (objectSize > maxSize * .90) {
283: return;
284: }
285: size += objectSize;
286: CacheObject cacheObject = new CacheObject(object, objectSize);
287: cachedObjectsHash.put(key, cacheObject);
288: //Make an entry into the cache order list.
289: LinkedListNode lastAccessedNode = lastAccessedList
290: .addFirst(key);
291: //Store the cache order list entry so that we can get back to it
292: //during later lookups.
293: cacheObject.lastAccessedListNode = lastAccessedNode;
294: //Add the object to the age list
295: LinkedListNode ageNode = ageList.addFirst(key);
296: //We make an explicit call to currentTimeMillis() so that total accuracy
297: //of lifetime calculations is better than one second.
298: ageNode.timestamp = System.currentTimeMillis();
299: cacheObject.ageListNode = ageNode;
300:
301: //If cache is too full, remove least used cache entries until it is
302: //not too full.
303: cullCache();
304: }
305:
306: /**
307: * Gets an object from cache. This method will return null under two
308: * conditions:<ul>
309: * <li>The object referenced by the key was never added to cache.
310: * <li>The object referenced by the key has expired from cache.</ul>
311: *
312: * @param key the unique key of the object to get.
313: * @return the Cacheable object corresponding to unique key.
314: */
315: public synchronized Cacheable get(Object key) {
316: //First, clear all entries that have been in cache longer than the
317: //maximum defined age.
318: deleteExpiredEntries();
319:
320: CacheObject cacheObject = (CacheObject) cachedObjectsHash
321: .get(key);
322: if (cacheObject == null) {
323: //The object didn't exist in cache, so increment cache misses.
324: cacheMisses++;
325: return null;
326: }
327:
328: //The object exists in cache, so increment cache hits.
329: cacheHits++;
330:
331: //Remove the object from it's current place in the cache order list,
332: //and re-insert it at the front of the list.
333: cacheObject.lastAccessedListNode.remove();
334: lastAccessedList.addFirst(cacheObject.lastAccessedListNode);
335:
336: return cacheObject.object;
337: }
338:
339: /**
340: * Removes an object from cache.
341: *
342: * @param key the unique key of the object to remove.
343: */
344: public synchronized void remove(Object key) {
345: //DEBUG
346: //System.err.println("Removing object with key: " + key + " from hash " + this);
347:
348: CacheObject cacheObject = (CacheObject) cachedObjectsHash
349: .get(key);
350: //If the object is not in cache, stop trying to remove it.
351: if (cacheObject == null) {
352: return;
353: }
354: //remove from the hash map
355: cachedObjectsHash.remove(key);
356: //remove from the cache order list
357: cacheObject.lastAccessedListNode.remove();
358: cacheObject.ageListNode.remove();
359: //remove references to linked list nodes
360: cacheObject.ageListNode = null;
361: cacheObject.lastAccessedListNode = null;
362: //removed the object, so subtract its size from the total.
363: size -= cacheObject.size;
364: }
365:
366: /**
367: * Clears the cache of all objects. The size of the cache is reset to 0.
368: */
369: public synchronized void clear() {
370: //DEBUG
371: //System.err.println("Clearing cache " + this);
372:
373: Object[] keys = cachedObjectsHash.keySet().toArray();
374: for (int i = 0; i < keys.length; i++) {
375: remove(keys[i]);
376: }
377:
378: //Now, reset all containers.
379: cachedObjectsHash.clear();
380: cachedObjectsHash = new HashMap(103);
381: lastAccessedList.clear();
382: lastAccessedList = new LinkedList();
383: ageList.clear();
384: ageList = new LinkedList();
385:
386: size = 0;
387: cacheHits = 0;
388: cacheMisses = 0;
389: }
390:
391: /**
392: * Returns a collection view of the values contained in the cache.
393: * The Collection is unmodifiable to prevent cache integrity issues.
394: *
395: * @return a Collection of the cache entries.
396: */
397: public Collection values() {
398: return Collections.unmodifiableCollection(cachedObjectsHash
399: .values());
400: }
401:
402: /**
403: * Returns the number of cache hits. A cache hit occurs every
404: * time the get method is called and the cache contains the requested
405: * object.<p>
406: *
407: * Keeping track of cache hits and misses lets one measure how efficient
408: * the cache is; the higher the percentage of hits, the more efficient.
409: *
410: * @return the number of cache hits.
411: */
412: public long getCacheHits() {
413: return cacheHits;
414: }
415:
416: /**
417: * Returns the number of cache misses. A cache miss occurs every
418: * time the get method is called and the cache does not contain the
419: * requested object.<p>
420: *
421: * Keeping track of cache hits and misses lets one measure how efficient
422: * the cache is; the higher the percentage of hits, the more efficient.
423: *
424: * @return the number of cache hits.
425: */
426: public long getCacheMisses() {
427: return cacheMisses;
428: }
429:
430: /**
431: * Clears all entries out of cache where the entries are older than the
432: * maximum defined age.
433: */
434: private final void deleteExpiredEntries() {
435: //Check if expiration is turned on.
436: if (maxLifetime <= 0) {
437: return;
438: }
439:
440: //Remove all old entries. To do this, we remove objects from the end
441: //of the linked list until they are no longer too old. We get to avoid
442: //any hash lookups or looking at any more objects than is strictly
443: //neccessary.
444: LinkedListNode node = ageList.getLast();
445: //If there are no entries in the age list, return.
446: if (node == null) {
447: return;
448: }
449:
450: //Determine the expireTime, which is the moment in time that elements
451: //should expire from cache. Then, we can do an easy to check to see
452: //if the expire time is greater than the expire time.
453: long expireTime = currentTime - maxLifetime;
454:
455: while (expireTime > node.timestamp) {
456: //DEBUG
457: //System.err.println("Object with key " + node.object + " expired.");
458:
459: //Remove the object
460: remove(node.object);
461:
462: //Get the next node.
463: node = ageList.getLast();
464: //If there are no more entries in the age list, return.
465: if (node == null) {
466: return;
467: }
468: }
469: }
470:
471: /**
472: * Removes objects from cache if the cache is too full. "Too full" is
473: * defined as within 3% of the maximum cache size. Whenever the cache is
474: * is too big, the least frequently used elements are deleted until the
475: * cache is at least 10% empty.
476: */
477: private final void cullCache() {
478: //See if the cache size is within 3% of being too big. If so, clean out
479: //cache until it's 10% free.
480: if (size >= maxSize * .97) {
481: //First, delete any old entries to see how much memory that frees.
482: deleteExpiredEntries();
483: int desiredSize = (int) (maxSize * .90);
484: while (size > desiredSize) {
485: //Get the key and invoke the remove method on it.
486: remove(lastAccessedList.getLast().object);
487: }
488: }
489: }
490: }
|