001: /*
002: * File : $Source: /usr/local/cvs/opencms/src/org/opencms/cache/CmsLruCache.java,v $
003: * Date : $Date: 2008-02-27 12:05:54 $
004: * Version: $Revision: 1.23 $
005: *
006: * This library is part of OpenCms -
007: * the Open Source Content Management System
008: *
009: * Copyright (c) 2002 - 2008 Alkacon Software GmbH (http://www.alkacon.com)
010: *
011: * This library is free software; you can redistribute it and/or
012: * modify it under the terms of the GNU Lesser General Public
013: * License as published by the Free Software Foundation; either
014: * version 2.1 of the License, or (at your option) any later version.
015: *
016: * This library is distributed in the hope that it will be useful,
017: * but WITHOUT ANY WARRANTY; without even the implied warranty of
018: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
019: * Lesser General Public License for more details.
020: *
021: * For further information about Alkacon Software GmbH, please see the
022: * company website: http://www.alkacon.com
023: *
024: * For further information about OpenCms, please see the
025: * project website: http://www.opencms.org
026: *
027: * You should have received a copy of the GNU Lesser General Public
028: * License along with this library; if not, write to the Free Software
029: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
030: */
031:
032: package org.opencms.cache;
033:
034: import org.opencms.main.CmsLog;
035:
036: import org.apache.commons.logging.Log;
037:
038: /**
039: * Implements an LRU (last recently used) cache.<p>
040: *
041: * The idea of this cache is to separate the caching policy from the data structure
042: * where the cached objects are stored. The advantage of doing so is, that the CmsFlexLruCache
043: * can identify the last-recently-used object in O(1), whereas you would need at least
044: * O(n) to traverse the data structure that stores the cached objects. Second, you can
045: * easily use the CmsFlexLruCache to get an LRU cache, no matter what data structure is used to
046: * store your objects.
047: * <p>
048: * The cache policy is affected by the "costs" of the objects being cached. Valuable cache costs
049: * might be the byte size of the cached objects for example.
050: * <p>
051: * To add/remove cached objects from the data structure that stores them, the objects have to
052: * implement the methods defined in the interface I_CmsLruCacheObject to be notified when they
053: * are added/removed from the CmsFlexLruCache.<p>
054: *
055: * @see org.opencms.cache.I_CmsLruCacheObject
056: *
057: * @author Thomas Weckert
058: *
059: * @version $Revision: 1.23 $
060: *
061: * @since 6.0.0
062: */
063: public class CmsLruCache extends java.lang.Object {
064:
065: /** The log object for this class. */
066: private static final Log LOG = CmsLog.getLog(CmsLruCache.class);
067:
068: /** The avg. sum of costs the cached objects. */
069: private int m_avgCacheCosts;
070:
071: /** The head of the list of double linked LRU cache objects. */
072: private I_CmsLruCacheObject m_listHead;
073:
074: /** The tail of the list of double linked LRU cache objects. */
075: private I_CmsLruCacheObject m_listTail;
076:
077: /** The max. sum of costs the cached objects might reach. */
078: private int m_maxCacheCosts;
079:
080: /** The max. costs of cacheable objects. */
081: private int m_maxObjectCosts;
082:
083: /** The costs of all cached objects. */
084: private int m_objectCosts;
085:
086: /** The sum of all cached objects. */
087: private int m_objectCount;
088:
089: /**
090: * The constructor with all options.<p>
091: *
092: * @param theMaxCacheCosts the max. cache costs of all cached objects
093: * @param theAvgCacheCosts the avg. cache costs of all cached objects
094: * @param theMaxObjectCosts the max. allowed cache costs per object. Set theMaxObjectCosts to -1 if you don't want to limit the max. allowed cache costs per object
095: */
096: public CmsLruCache(int theMaxCacheCosts, int theAvgCacheCosts,
097: int theMaxObjectCosts) {
098:
099: m_maxCacheCosts = theMaxCacheCosts;
100: m_avgCacheCosts = theAvgCacheCosts;
101: m_maxObjectCosts = theMaxObjectCosts;
102: }
103:
104: /**
105: * Adds a new object to this cache.<p>
106: *
107: * If add the same object more than once,
108: * the object is touched instead.<p>
109: *
110: * @param theCacheObject the object being added to the cache
111: * @return true if the object was added to the cache, false if the object was denied because its cache costs were higher than the allowed max. cache costs per object
112: */
113: public synchronized boolean add(I_CmsLruCacheObject theCacheObject) {
114:
115: if (theCacheObject == null) {
116: // null can't be added or touched in the cache
117: return false;
118: }
119:
120: // only objects with cache costs < the max. allowed object cache costs can be cached!
121: if ((m_maxObjectCosts != -1)
122: && (theCacheObject.getLruCacheCosts() > m_maxObjectCosts)) {
123: if (LOG.isInfoEnabled()) {
124: LOG.info(Messages.get().getBundle().key(
125: Messages.LOG_CACHE_COSTS_TOO_HIGH_2,
126: new Integer(theCacheObject.getLruCacheCosts()),
127: new Integer(m_maxObjectCosts)));
128: }
129: return false;
130: }
131:
132: if (!isCached(theCacheObject)) {
133: // add the object to the list of all cached objects in the cache
134: addHead(theCacheObject);
135: } else {
136: touch(theCacheObject);
137: }
138:
139: // check if the cache has to trash the last-recently-used objects before adding a new object
140: if (m_objectCosts > m_maxCacheCosts) {
141: gc();
142: }
143:
144: return true;
145: }
146:
147: /**
148: * Removes all cached objects in this cache.<p>
149: */
150: public synchronized void clear() {
151:
152: // remove all objects from the linked list from the tail to the head:
153: I_CmsLruCacheObject currentObject = m_listTail;
154: while (currentObject != null) {
155: currentObject = currentObject.getNextLruObject();
156: removeTail();
157: }
158:
159: // reset the data structure
160: m_objectCosts = 0;
161: m_objectCount = 0;
162: m_listHead = null;
163: m_listTail = null;
164: }
165:
166: /**
167: * Returns the average costs of all cached objects.<p>
168: *
169: * @return the average costs of all cached objects
170: */
171: public int getAvgCacheCosts() {
172:
173: return m_avgCacheCosts;
174: }
175:
176: /**
177: * Returns the max costs of all cached objects.<p>
178: *
179: * @return the max costs of all cached objects
180: */
181: public int getMaxCacheCosts() {
182:
183: return m_maxCacheCosts;
184: }
185:
186: /**
187: * Returns the max allowed costs per cached object.<p>
188: *
189: * @return the max allowed costs per cached object
190: */
191: public int getMaxObjectCosts() {
192:
193: return m_maxObjectCosts;
194: }
195:
196: /**
197: * Returns the current costs of all cached objects.<p>
198: *
199: * @return the current costs of all cached objects
200: */
201: public int getObjectCosts() {
202:
203: return m_objectCosts;
204: }
205:
206: /**
207: * Removes an object from the list of all cached objects in this cache,
208: * no matter what position it has inside the list.<p>
209: *
210: * @param theCacheObject the object being removed from the list of all cached objects
211: * @return a reference to the object that was removed
212: */
213: public synchronized I_CmsLruCacheObject remove(
214: I_CmsLruCacheObject theCacheObject) {
215:
216: if (!isCached(theCacheObject)) {
217: // theCacheObject is null or not inside the cache
218: return null;
219: }
220:
221: // set the list pointers correct
222: if (theCacheObject.getNextLruObject() == null) {
223: // remove the object from the head pos.
224: I_CmsLruCacheObject newHead = theCacheObject
225: .getPreviousLruObject();
226:
227: if (newHead != null) {
228: // if newHead is null, theCacheObject
229: // was the only object in the cache
230: newHead.setNextLruObject(null);
231: }
232:
233: m_listHead = newHead;
234: } else if (theCacheObject.getPreviousLruObject() == null) {
235: // remove the object from the tail pos.
236: I_CmsLruCacheObject newTail = theCacheObject
237: .getNextLruObject();
238:
239: if (newTail != null) {
240: // if newTail is null, theCacheObject
241: // was the only object in the cache
242: newTail.setPreviousLruObject(null);
243: }
244:
245: m_listTail = newTail;
246: } else {
247: // remove the object from within the list
248: theCacheObject.getPreviousLruObject().setNextLruObject(
249: theCacheObject.getNextLruObject());
250: theCacheObject.getNextLruObject().setPreviousLruObject(
251: theCacheObject.getPreviousLruObject());
252: }
253:
254: // update cache stats. and notify the cached object
255: decreaseCache(theCacheObject);
256:
257: return theCacheObject;
258: }
259:
260: /**
261: * Returns the count of all cached objects.<p>
262: *
263: * @return the count of all cached objects
264: */
265: public int size() {
266:
267: return m_objectCount;
268: }
269:
270: /**
271: * Returns a string representing the current state of the cache.<p>
272: * @return a string representing the current state of the cache
273: */
274: public String toString() {
275:
276: StringBuffer buf = new StringBuffer();
277: buf.append("max. costs: " + m_maxCacheCosts).append(", ");
278: buf.append("avg. costs: " + m_avgCacheCosts).append(", ");
279: buf.append("max. costs/object: " + m_maxObjectCosts).append(
280: ", ");
281: buf.append("costs: " + m_objectCosts).append(", ");
282: buf.append("count: " + m_objectCount);
283: return buf.toString();
284: }
285:
286: /**
287: * Touch an existing object in this cache, in the sense that it's "last-recently-used" state
288: * is updated.<p>
289: *
290: * @param theCacheObject the object being touched
291: * @return true if an object was found and touched
292: */
293: public synchronized boolean touch(I_CmsLruCacheObject theCacheObject) {
294:
295: if (!isCached(theCacheObject)) {
296: return false;
297: }
298:
299: // only objects with cache costs < the max. allowed object cache costs can be cached!
300: if ((m_maxObjectCosts != -1)
301: && (theCacheObject.getLruCacheCosts() > m_maxObjectCosts)) {
302: if (LOG.isInfoEnabled()) {
303: LOG.info(Messages.get().getBundle().key(
304: Messages.LOG_CACHE_COSTS_TOO_HIGH_2,
305: new Integer(theCacheObject.getLruCacheCosts()),
306: new Integer(m_maxObjectCosts)));
307: }
308: remove(theCacheObject);
309: return false;
310: }
311:
312: // set the list pointers correct
313: I_CmsLruCacheObject nextObj = theCacheObject.getNextLruObject();
314: if (nextObj == null) {
315: // case 1: the object is already at the head pos.
316: return true;
317: }
318: I_CmsLruCacheObject prevObj = theCacheObject
319: .getPreviousLruObject();
320: if (prevObj == null) {
321: // case 2: the object at the tail pos., remove it from the tail to put it to the front as the new head
322: I_CmsLruCacheObject newTail = nextObj;
323: newTail.setPreviousLruObject(null);
324: m_listTail = newTail;
325: } else {
326: // case 3: the object is somewhere within the list, remove it to put it the front as the new head
327: prevObj.setNextLruObject(nextObj);
328: nextObj.setPreviousLruObject(prevObj);
329: }
330:
331: // set the touched object as the new head in the linked list:
332: I_CmsLruCacheObject oldHead = m_listHead;
333: if (oldHead != null) {
334: oldHead.setNextLruObject(theCacheObject);
335: theCacheObject.setNextLruObject(null);
336: theCacheObject.setPreviousLruObject(oldHead);
337: }
338: m_listHead = theCacheObject;
339:
340: return true;
341: }
342:
343: /**
344: * Clears this cache for finalization.<p>
345: * @throws Throwable if something goes wring
346: */
347: protected void finalize() throws Throwable {
348:
349: try {
350: clear();
351: } catch (Throwable t) {
352: // ignore
353: }
354: super .finalize();
355: }
356:
357: /**
358: * Adds a cache object as the new haed to the list of all cached objects in this cache.<p>
359: *
360: * @param theCacheObject the object being added as the new head to the list of all cached objects
361: */
362: private void addHead(I_CmsLruCacheObject theCacheObject) {
363:
364: // set the list pointers correct
365: if (m_objectCount > 0) {
366: // there is at least 1 object already in the list
367: I_CmsLruCacheObject oldHead = m_listHead;
368: oldHead.setNextLruObject(theCacheObject);
369: theCacheObject.setPreviousLruObject(oldHead);
370: m_listHead = theCacheObject;
371: } else {
372: // it is the first object to be added to the list
373: m_listTail = theCacheObject;
374: m_listHead = theCacheObject;
375: theCacheObject.setPreviousLruObject(null);
376: }
377: theCacheObject.setNextLruObject(null);
378:
379: // update cache stats. and notify the cached object
380: increaseCache(theCacheObject);
381: }
382:
383: /**
384: * Decrease this caches statistics
385: * and notify the cached object that it was removed from this cache.<p>
386: *
387: * @param theCacheObject the object being notified that it was removed from the cache
388: */
389: private void decreaseCache(I_CmsLruCacheObject theCacheObject) {
390:
391: // notify the object that it was now removed from the cache
392: //theCacheObject.notify();
393: theCacheObject.removeFromLruCache();
394:
395: // set the list pointers to null
396: theCacheObject.setNextLruObject(null);
397: theCacheObject.setPreviousLruObject(null);
398:
399: // update the cache stats.
400: m_objectCosts -= theCacheObject.getLruCacheCosts();
401: m_objectCount--;
402: }
403:
404: /**
405: * Removes the last recently used objects from the list of all cached objects as long
406: * as the costs of all cached objects are higher than the allowed avg. costs of the cache.<p>
407: */
408: private void gc() {
409:
410: I_CmsLruCacheObject currentObject = m_listTail;
411: while (currentObject != null) {
412: if (m_objectCosts < m_avgCacheCosts) {
413: break;
414: }
415: currentObject = currentObject.getNextLruObject();
416: removeTail();
417: }
418: }
419:
420: /**
421: * Increase this caches statistics
422: * and notify the cached object that it was added to this cache.<p>
423: *
424: * @param theCacheObject the object being notified that it was added to the cache
425: */
426: private void increaseCache(I_CmsLruCacheObject theCacheObject) {
427:
428: // notify the object that it was now added to the cache
429: //theCacheObject.notify();
430: theCacheObject.addToLruCache();
431:
432: // update the cache stats.
433: m_objectCosts += theCacheObject.getLruCacheCosts();
434: m_objectCount++;
435: }
436:
437: /**
438: * Test if a given object resides inside the cache.<p>
439: *
440: * @param theCacheObject the object to test
441: * @return true if the object is inside the cache, false otherwise
442: */
443: private boolean isCached(I_CmsLruCacheObject theCacheObject) {
444:
445: if ((theCacheObject == null) || (m_objectCount == 0)) {
446: // the cache is empty or the object is null (which is never cached)
447: return false;
448: }
449:
450: I_CmsLruCacheObject nextObj = theCacheObject.getNextLruObject();
451: I_CmsLruCacheObject prevObj = theCacheObject
452: .getPreviousLruObject();
453:
454: if ((nextObj != null) || (prevObj != null)) {
455: // the object has either a predecessor or successor in the linked
456: // list of all cached objects, so it is inside the cache
457: return true;
458: }
459:
460: // both nextObj and preObj are null
461: if ((m_objectCount == 1) && (m_listHead != null)
462: && (m_listTail != null)
463: && m_listHead.equals(theCacheObject)
464: && m_listTail.equals(theCacheObject)) {
465: // the object is the one and only object in the cache
466: return true;
467: }
468:
469: return false;
470: }
471:
472: /**
473: * Removes the tailing object from the list of all cached objects.<p>
474: */
475: private synchronized void removeTail() {
476:
477: I_CmsLruCacheObject oldTail = m_listTail;
478: if (oldTail != null) {
479: I_CmsLruCacheObject newTail = oldTail.getNextLruObject();
480:
481: // set the list pointers correct
482: if (newTail != null) {
483: // there are still objects remaining in the list
484: newTail.setPreviousLruObject(null);
485: m_listTail = newTail;
486: } else {
487: // we removed the last object from the list
488: m_listTail = null;
489: m_listHead = null;
490: }
491:
492: // update cache stats. and notify the cached object
493: decreaseCache(oldTail);
494: }
495: }
496: }
|