001: /*
002: * NEMESIS-FORUM.
003: * Copyright (C) 2002 David Laurent(lithium2@free.fr). All rights reserved.
004: *
005: * Copyright (c) 2000 The Apache Software Foundation. All rights reserved.
006: *
007: * Copyright (C) 2001 Yasna.com. All rights reserved.
008: *
009: * Copyright (C) 2000 CoolServlets.com. All rights reserved.
010: *
011: * NEMESIS-FORUM. is free software; you can redistribute it and/or
012: * modify it under the terms of the Apache Software License, Version 1.1,
013: * or (at your option) any later version.
014: *
015: * NEMESIS-FORUM core framework, NEMESIS-FORUM backoffice, NEMESIS-FORUM frontoffice
016: * application are parts of NEMESIS-FORUM and are distributed under
017: * same terms of licence.
018: *
019: *
020: * NEMESIS-FORUM includes software developed by the Apache Software Foundation (http://www.apache.org/)
021: * and software developed by CoolServlets.com (http://www.coolservlets.com).
022: * and software developed by Yasna.com (http://www.yasna.com).
023: *
024: */
025:
026: package org.nemesis.forum.util.cache;
027:
028: import java.util.Collection;
029: import java.util.Collections;
030: import java.util.HashMap;
031:
032: import org.nemesis.forum.util.LinkedList;
033: import org.nemesis.forum.util.LinkedListNode;
034:
035: public class Cache implements Cacheable {
036:
037: /**
038: * One of the major potential bottlenecks of the cache is performing
039: * System.currentTimeMillis() for every cache get operation. Instead,
040: * we maintain a global timestamp that gets updated once a second. This
041: * means that cache expirations can be no more than one second accurate.
042: */
043: protected static long currentTime = System.currentTimeMillis();
044:
045: /**
046: * A cache timer updates the current time once a second in a seperate
047: * thread.
048: */
049: protected static CacheTimer timer = new CacheTimer(1000L);
050:
051: /**
052: * Maintains the hash of cached objects. Hashing provides the best
053: * performance for fast lookups.
054: */
055: protected HashMap cachedObjectsHash;
056:
057: /**
058: * Linked list to maintain order that cache objects are accessed
059: * in, most used to least used.
060: */
061: protected LinkedList lastAccessedList;
062:
063: /**
064: * Linked list to maintain time that cache objects were initially added
065: * to the cache, most recently added to oldest added.
066: */
067: protected LinkedList ageList;
068:
069: /**
070: * Maximum size in bytes that the cache can grow to. Default
071: * maximum size is 128 K.
072: */
073: protected int maxSize = 128 * 1024;
074:
075: /**
076: * Maintains the current size of the cache in bytes.
077: */
078: protected int size = 0;
079:
080: /**
081: * Maximum length of time objects can exist in cache before expiring.
082: * Default is that objects have no maximum lifetime.
083: */
084: protected long maxLifetime = -1;
085:
086: /**
087: * Maintain the number of cache hits and misses. A cache hit occurs every
088: * time the get method is called and the cache contains the requested
089: * object. A cache miss represents the opposite occurence.<p>
090: *
091: * Keeping track of cache hits and misses lets one measure how efficient
092: * the cache is; the higher the percentage of hits, the more efficient.
093: */
094: protected long cacheHits, cacheMisses = 0L;
095:
096: /**
097: * Create a new cache with default values. Default cache size is 128K with
098: * no maximum lifetime.
099: */
100: public Cache() {
101: //Our primary data structure is a hash map. The default capacity of 11
102: //is too small in almost all cases, so we set it bigger.
103: cachedObjectsHash = new HashMap(103);
104:
105: lastAccessedList = new LinkedList();
106: ageList = new LinkedList();
107: }
108:
109: /**
110: * Create a new cache and specify the maximum size for the cache in bytes.
111: * Items added to the cache will have no maximum lifetime.
112: *
113: * @param maxSize the maximum size of the cache in bytes.
114: */
115: public Cache(int maxSize) {
116: this ();
117: this .maxSize = maxSize;
118: }
119:
120: /**
121: * Create a new cache and specify the maximum lifetime of objects. The
122: * time should be specified in milleseconds. The minimum lifetime of any
123: * cache object is 1000 milleseconds (1 second). Additionally, cache
124: * expirations have a 1000 millesecond resolution, which means that all
125: * objects are guaranteed to be expired within 1000 milliseconds of their
126: * maximum lifetime.
127: *
128: * @param maxLifetime the maximum amount of time objects can exist in
129: * cache before being deleted.
130: */
131: public Cache(long maxLifetime) {
132: this ();
133: this .maxLifetime = maxLifetime;
134: }
135:
136: /**
137: * Create a new cache and specify the maximum size of for the cache in
138: * bytes, and the maximum lifetime of objects.
139: *
140: * @param maxSize the maximum size of the cache in bytes.
141: * @param maxLifetime the maximum amount of time objects can exist in
142: * cache before being deleted.
143: */
144: public Cache(int maxSize, long maxLifetime) {
145: this ();
146: this .maxSize = maxSize;
147: this .maxLifetime = maxLifetime;
148: }
149:
150: /**
151: * Returns the current size of the cache in bytes.
152: *
153: * @return the size of the cache in bytes.
154: */
155: public int getSize() {
156: return size;
157: }
158:
159: /**
160: * Returns the maximum size of the cache in bytes. If the cache grows too
161: * large, the least frequently used items will automatically be deleted so
162: * that the cache size doesn't exceed the maximum.
163: *
164: * @return the maximum size of the cache in bytes.
165: */
166: public int getMaxSize() {
167: return maxSize;
168: }
169:
170: /**
171: * Sets the maximum size of the cache in bytes. If the cache grows too
172: * large, the least frequently used items will automatically be deleted so
173: * that the cache size doesn't exceed the maximum.
174: *
175: * @param maxSize the maximum size of the cache in bytes.
176: */
177: public void setMaxSize(int maxSize) {
178: this .maxSize = maxSize;
179: //It's possible that the new max size is smaller than our current cache
180: //size. If so, we need to delete infrequently used items.
181: cullCache();
182: }
183:
184: /**
185: * Returns the number of objects in the cache.
186: *
187: * @return the number of objects in the cache.
188: */
189: public synchronized int getNumElements() {
190: return cachedObjectsHash.size();
191: }
192:
193: /**
194: * Adds a new Cacheable object to the cache. The key must be unique.
195: *
196: * @param key a unique key for the object being put into cache.
197: * @param object the Cacheable object to put into cache.
198: */
199: public synchronized void add(Object key, Cacheable object) {
200:
201: //Don't add an object with the same key multiple times.
202: if (cachedObjectsHash.containsKey(key)) {
203: return;
204: }
205: int objectSize = object.getSize();
206: //If the object is bigger than the entire cache, simply don't add it.
207: if (objectSize > maxSize * .90) {
208: return;
209: }
210: size += objectSize;
211: CacheObject cacheObject = new CacheObject(object, objectSize);
212: cachedObjectsHash.put(key, cacheObject);
213: //Make an entry into the cache order list.
214: LinkedListNode lastAccessedNode = lastAccessedList
215: .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
246: .get(key);
247: if (cacheObject == null) {
248: //The object didn't exist in cache, so increment cache misses.
249: cacheMisses++;
250: return null;
251: }
252:
253: //The object exists in cache, so increment cache hits.
254: cacheHits++;
255:
256: //Remove the object from it's current place in the cache order list,
257: //and re-insert it at the front of the list.
258: cacheObject.lastAccessedListNode.remove();
259: lastAccessedList.addFirst(cacheObject.lastAccessedListNode);
260:
261: return cacheObject.object;
262: }
263:
264: /**
265: * Removes an object from cache.
266: *
267: * @param key the unique key of the object to remove.
268: */
269: public synchronized void remove(Object key) {
270:
271: CacheObject cacheObject = (CacheObject) cachedObjectsHash
272: .get(key);
273: //If the object is not in cache, stop trying to remove it.
274: if (cacheObject == null) {
275: return;
276: }
277: //remove from the hash map
278: cachedObjectsHash.remove(key);
279: //remove from the cache order list
280: cacheObject.lastAccessedListNode.remove();
281: cacheObject.ageListNode.remove();
282: //remove references to linked list nodes
283: cacheObject.ageListNode = null;
284: cacheObject.lastAccessedListNode = null;
285: //removed the object, so subtract its size from the total.
286: size -= cacheObject.size;
287: }
288:
289: /**
290: * Clears the cache of all objects. The size of the cache is reset to 0.
291: */
292: public synchronized void clear() {
293:
294: Object[] keys = cachedObjectsHash.keySet().toArray();
295: for (int i = 0; i < keys.length; i++) {
296: remove(keys[i]);
297: }
298:
299: //Now, reset all containers.
300: cachedObjectsHash.clear();
301: cachedObjectsHash = new HashMap(103);
302: lastAccessedList.clear();
303: lastAccessedList = new LinkedList();
304: ageList.clear();
305: ageList = new LinkedList();
306:
307: size = 0;
308: cacheHits = 0;
309: cacheMisses = 0;
310: }
311:
312: /**
313: * Returns a collection view of the values contained in the cache.
314: * The Collection is unmodifiable to prevent cache integrity issues.
315: *
316: * @return a Collection of the cache entries.
317: */
318: public Collection values() {
319: return Collections.unmodifiableCollection(cachedObjectsHash
320: .values());
321: }
322:
323: /**
324: * Returns the number of cache hits. A cache hit occurs every
325: * time the get method is called and the cache contains the requested
326: * object.<p>
327: *
328: * Keeping track of cache hits and misses lets one measure how efficient
329: * the cache is; the higher the percentage of hits, the more efficient.
330: *
331: * @return the number of cache hits.
332: */
333: public long getCacheHits() {
334: return cacheHits;
335: }
336:
337: /**
338: * Returns the number of cache misses. A cache miss occurs every
339: * time the get method is called and the cache does not contain the
340: * requested object.<p>
341: *
342: * Keeping track of cache hits and misses lets one measure how efficient
343: * the cache is; the higher the percentage of hits, the more efficient.
344: *
345: * @return the number of cache hits.
346: */
347: public long getCacheMisses() {
348: return cacheMisses;
349: }
350:
351: /**
352: * Clears all entries out of cache where the entries are older than the
353: * maximum defined age.
354: */
355: private final void deleteExpiredEntries() {
356: //Check if expiration is turned on.
357: if (maxLifetime <= 0) {
358: return;
359: }
360:
361: //Remove all old entries. To do this, we remove objects from the end
362: //of the linked list until they are no longer too old. We get to avoid
363: //any hash lookups or looking at any more objects than is strictly
364: //neccessary.
365: LinkedListNode node = ageList.getLast();
366: //If there are no entries in the age list, return.
367: if (node == null) {
368: return;
369: }
370:
371: //Determine the expireTime, which is the moment in time that elements
372: //should expire from cache. Then, we can do an easy to check to see
373: //if the expire time is greater than the expire time.
374: long expireTime = currentTime - maxLifetime;
375:
376: while (expireTime > node.timestamp) {
377:
378: //Remove the object
379: remove(node.object);
380:
381: //Get the next node.
382: node = ageList.getLast();
383: //If there are no more entries in the age list, return.
384: if (node == null) {
385: return;
386: }
387: }
388: }
389:
390: /**
391: * Removes objects from cache if the cache is too full. "Too full" is
392: * defined as within 3% of the maximum cache size. Whenever the cache is
393: * is too big, the least frequently used elements are deleted until the
394: * cache is at least 10% empty.
395: */
396: private final void cullCache() {
397: //See if the cache size is within 3% of being too big. If so, clean out
398: //cache until it's 10% free.
399: if (size >= maxSize * .97) {
400: //First, delete any old entries to see how much memory that frees.
401: deleteExpiredEntries();
402: int desiredSize = (int) (maxSize * .90);
403: while (size > desiredSize) {
404: //Get the key and invoke the remove method on it.
405: remove(lastAccessedList.getLast().object);
406: }
407: }
408: }
409: }
|