CmsLruCache


1   /*
2    * File   : $Source: /usr/local/cvs/opencms/src/org/opencms/cache/CmsLruCache.java,v $
3    * Date   : $Date: 2006/03/27 14:52:27 $
4    * Version: $Revision: 1.20 $
5    *
6    * This library is part of OpenCms -
7    * the Open Source Content Mananagement System
8    *
9    * Copyright (c) 2005 Alkacon Software GmbH (http://www.alkacon.com)
10   *
11   * This library is free software; you can redistribute it and/or
12   * modify it under the terms of the GNU Lesser General Public
13   * License as published by the Free Software Foundation; either
14   * version 2.1 of the License, or (at your option) any later version.
15   *
16   * This library is distributed in the hope that it will be useful,
17   * but WITHOUT ANY WARRANTY; without even the implied warranty of
18   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19   * Lesser General Public License for more details.
20   *
21   * For further information about Alkacon Software GmbH, please see the
22   * company website: http://www.alkacon.com
23   *
24   * For further information about OpenCms, please see the
25   * project website: http://www.opencms.org
26   * 
27   * You should have received a copy of the GNU Lesser General Public
28   * License along with this library; if not, write to the Free Software
29   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
30   */
31  
32  package org.opencms.cache;
33  
34  import org.opencms.main.CmsLog;
35  
36  import org.apache.commons.logging.Log;
37  
38  /**
39   * Implements an LRU (last recently used) cache.<p>
40   * 
41   * The idea of this cache is to separate the caching policy from the data structure
42   * where the cached objects are stored. The advantage of doing so is, that the CmsFlexLruCache
43   * can identify the last-recently-used object in O(1), whereas you would need at least
44   * O(n) to traverse the data structure that stores the cached objects. Second, you can
45   * easily use the CmsFlexLruCache to get an LRU cache, no matter what data structure is used to
46   * store your objects.
47   * <p>
48   * The cache policy is affected by the "costs" of the objects being cached. Valuable cache costs
49   * might be the byte size of the cached objects for example.
50   * <p>
51   * To add/remove cached objects from the data structure that stores them, the objects have to
52   * implement the methods defined in the interface I_CmsLruCacheObject to be notified when they
53   * are added/removed from the CmsFlexLruCache.<p>
54   *
55   * @see org.opencms.cache.I_CmsLruCacheObject
56   * 
57   * @author Thomas Weckert 
58   * 
59   * @version $Revision: 1.20 $
60   * 
61   * @since 6.0.0
62   */
63  public class CmsLruCache extends java.lang.Object   {
64  
65      /** The log object for this class. */
66      private static final Log LOG = CmsLog.getLog(CmsLruCache.class);
67  
68      /** The avg. sum of costs the cached objects. */
69      private int m_avgCacheCosts;
70  
71      /** The head of the list of double linked LRU cache objects. */
72      private I_CmsLruCacheObject m_listHead;
73  
74      /** The tail of the list of double linked LRU cache objects. */
75      private I_CmsLruCacheObject m_listTail;
76  
77      /** The max. sum of costs the cached objects might reach. */
78      private int m_maxCacheCosts;
79  
80      /** The max. costs of cacheable objects. */
81      private int m_maxObjectCosts;
82  
83      /** The costs of all cached objects. */
84      private int m_objectCosts;
85  
86      /** The sum of all cached objects. */
87      private int m_objectCount;
88  
89      /**
90       * The constructor with all options.<p>
91       *
92       * @param theMaxCacheCosts the max. cache costs of all cached objects
93       * @param theAvgCacheCosts the avg. cache costs of all cached objects
94       * @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
95       */
96      public CmsLruCache(int theMaxCacheCosts, int theAvgCacheCosts, int theMaxObjectCosts) {
97  
98          m_maxCacheCosts = theMaxCacheCosts;
99          m_avgCacheCosts = theAvgCacheCosts;
100         m_maxObjectCosts = theMaxObjectCosts;
101 
102         m_objectCosts = 0;
103         m_objectCount = 0;
104         m_listHead = null;
105         m_listTail = null;
106     }
107 
108     /**
109      * Adds a new object to this cache.<p>
110      * 
111      * If add the same object more than once,
112      * the object is touched instead.<p>
113      *
114      * @param theCacheObject the object being added to the cache
115      * @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
116      */
117     public synchronized boolean add(I_CmsLruCacheObject theCacheObject) {
118 
119         if (theCacheObject == null) {
120             // null can't be added or touched in the cache 
121             return false;
122         }
123 
124         // only objects with cache costs < the max. allowed object cache costs can be cached!
125         if ((m_maxObjectCosts != -1) && (theCacheObject.getLruCacheCosts() > m_maxObjectCosts)) {
126             if (LOG.isInfoEnabled()) {
127                 LOG.info(Messages.get().getBundle().key(
128                     Messages.LOG_CACHE_COSTS_TOO_HIGH_2,
129                     new Integer  (theCacheObject.getLruCacheCosts()),
130                     new Integer  (m_maxObjectCosts)));
131             }
132             return false;
133         }
134 
135         if (!isCached(theCacheObject)) {
136             // add the object to the list of all cached objects in the cache
137             addHead(theCacheObject);
138         } else {
139             touch(theCacheObject);
140         }
141 
142         // check if the cache has to trash the last-recently-used objects before adding a new object
143         if (m_objectCosts > m_maxCacheCosts) {
144             gc();
145         }
146 
147         return true;
148     }
149 
150     /**
151      * Removes all cached objects in this cache.<p>
152      */
153     public void clear() {
154 
155         // remove all objects from the linked list from the tail to the head:
156         I_CmsLruCacheObject currentObject = m_listTail;
157         while (currentObject != null) {
158             currentObject = currentObject.getNextLruObject();
159             removeTail();
160         }
161 
162         // reset the data structure
163         m_objectCosts = 0;
164         m_objectCount = 0;
165         m_listHead = null;
166         m_listTail = null;
167 
168     }
169 
170     /**
171      * Returns the average costs of all cached objects.<p>
172      * 
173      * @return the average costs of all cached objects
174      */
175     public int getAvgCacheCosts() {
176 
177         return m_avgCacheCosts;
178     }
179 
180     /**
181      * Returns the max costs of all cached objects.<p>
182      * 
183      * @return the max costs of all cached objects
184      */
185     public int getMaxCacheCosts() {
186 
187         return m_maxCacheCosts;
188     }
189 
190     /**
191      * Returns the max allowed costs per cached object.<p>
192      * 
193      * @return the max allowed costs per cached object
194      */
195     public int getMaxObjectCosts() {
196 
197         return m_maxObjectCosts;
198     }
199 
200     /**
201      * Returns the current costs of all cached objects.<p>
202      * 
203      * @return the current costs of all cached objects
204      */
205     public int getObjectCosts() {
206 
207         return m_objectCosts;
208     }
209 
210     /**
211      * Removes an object from the list of all cached objects in this cache,
212      * no matter what position it has inside the list.<p>
213      *
214      * @param theCacheObject the object being removed from the list of all cached objects
215      * @return a reference to the object that was removed
216      */
217     public synchronized I_CmsLruCacheObject remove(I_CmsLruCacheObject theCacheObject) {
218 
219         if (!isCached(theCacheObject)) {
220             // theCacheObject is null or not inside the cache
221             return null;
222         }
223 
224         // set the list pointers correct
225         if (theCacheObject.getNextLruObject() == null) {
226             // remove the object from the head pos.
227             I_CmsLruCacheObject newHead = theCacheObject.getPreviousLruObject();
228 
229             if (newHead != null) {
230                 // if newHead is null, theCacheObject 
231                 // was the only object in the cache
232                 newHead.setNextLruObject(null);
233             }
234 
235             m_listHead = newHead;
236         } else if (theCacheObject.getPreviousLruObject() == null) {
237             // remove the object from the tail pos.
238             I_CmsLruCacheObject newTail = theCacheObject.getNextLruObject();
239 
240             if (newTail != null) {
241                 // if newTail is null, theCacheObject 
242                 // was the only object in the cache                
243                 newTail.setPreviousLruObject(null);
244             }
245 
246             m_listTail = newTail;
247         } else {
248             // remove the object from within the list
249             theCacheObject.getPreviousLruObject().setNextLruObject(theCacheObject.getNextLruObject());
250             theCacheObject.getNextLruObject().setPreviousLruObject(theCacheObject.getPreviousLruObject());
251         }
252 
253         // update cache stats. and notify the cached object
254         decreaseCache(theCacheObject);
255 
256         return theCacheObject;
257     }
258 
259     /**
260      * Returns the count of all cached objects.<p>
261      *
262      * @return the count of all cached objects
263      */
264     public int size() {
265 
266         return m_objectCount;
267     }
268 
269     /**
270      * Returns a string representing the current state of the cache.<p>
271      * @return a string representing the current state of the cache
272      */
273     public String   toString() {
274 
275         StringBuffer   buf = new StringBuffer  ();
276         buf.append("max. costs: " + m_maxCacheCosts).append(", ");
277         buf.append("avg. costs: " + m_avgCacheCosts).append(", ");
278         buf.append("max. costs/object: " + m_maxObjectCosts).append(", ");
279         buf.append("costs: " + m_objectCosts).append(", ");
280         buf.append("count: " + m_objectCount);
281         return buf.toString();
282     }
283 
284     /**
285      * Touch an existing object in this cache, in the sense that it's "last-recently-used" state
286      * is updated.<p>
287      *
288      * @param theCacheObject the object being touched
289      * @return true if an object was found and touched
290      */
291     public synchronized boolean touch(I_CmsLruCacheObject theCacheObject) {
292 
293         if (!isCached(theCacheObject)) {
294             return false;
295         }
296 
297         // only objects with cache costs < the max. allowed object cache costs can be cached!
298         if ((m_maxObjectCosts != -1) && (theCacheObject.getLruCacheCosts() > m_maxObjectCosts)) {
299             if (LOG.isInfoEnabled()) {
300                 LOG.info(Messages.get().getBundle().key(
301                     Messages.LOG_CACHE_COSTS_TOO_HIGH_2,
302                     new Integer  (theCacheObject.getLruCacheCosts()),
303                     new Integer  (m_maxObjectCosts)));
304             }
305             remove(theCacheObject);
306             return false;
307         }
308 
309         // set the list pointers correct
310         I_CmsLruCacheObject nextObj = theCacheObject.getNextLruObject();
311         if (nextObj == null) {
312             // case 1: the object is already at the head pos.
313             return true;
314         }
315         I_CmsLruCacheObject prevObj = theCacheObject.getPreviousLruObject();
316         if (prevObj == null) {
317             // case 2: the object at the tail pos., remove it from the tail to put it to the front as the new head
318             I_CmsLruCacheObject newTail = nextObj;
319             newTail.setPreviousLruObject(null);
320             m_listTail = newTail;
321         } else {
322             // case 3: the object is somewhere within the list, remove it to put it the front as the new head
323             prevObj.setNextLruObject(nextObj);
324             nextObj.setPreviousLruObject(prevObj);
325         }
326 
327         // set the touched object as the new head in the linked list:
328         I_CmsLruCacheObject oldHead = m_listHead;
329         if (oldHead != null) {
330             oldHead.setNextLruObject(theCacheObject);
331             theCacheObject.setNextLruObject(null);
332             theCacheObject.setPreviousLruObject(oldHead);
333         }
334         m_listHead = theCacheObject;
335 
336         return true;
337     }
338 
339     /**
340      * Clears this cache for finalization.<p>
341      * @throws Throwable if something goes wring
342      */
343     protected void finalize() throws Throwable   {
344 
345         try {
346             clear();
347         } catch (Throwable   t) {
348             // ignore
349         }
350         super.finalize();
351     }
352 
353     /**
354      * Adds a cache object as the new haed to the list of all cached objects in this cache.<p>
355      *
356      * @param theCacheObject the object being added as the new head to the list of all cached objects
357      */
358     private void addHead(I_CmsLruCacheObject theCacheObject) {
359 
360         // set the list pointers correct
361         if (m_objectCount > 0) {
362             // there is at least 1 object already in the list
363             I_CmsLruCacheObject oldHead = m_listHead;
364             oldHead.setNextLruObject(theCacheObject);
365             theCacheObject.setPreviousLruObject(oldHead);
366             m_listHead = theCacheObject;
367         } else {
368             // it is the first object to be added to the list
369             m_listTail = theCacheObject;
370             m_listHead = theCacheObject;
371             theCacheObject.setPreviousLruObject(null);
372         }
373         theCacheObject.setNextLruObject(null);
374 
375         // update cache stats. and notify the cached object
376         increaseCache(theCacheObject);
377     }
378 
379     /**
380      * Decrease this caches statistics
381      * and notify the cached object that it was removed from this cache.<p>
382      *
383      * @param theCacheObject the object being notified that it was removed from the cache
384      */
385     private void decreaseCache(I_CmsLruCacheObject theCacheObject) {
386 
387         // notify the object that it was now removed from the cache
388         //theCacheObject.notify();
389         theCacheObject.removeFromLruCache();
390 
391         // set the list pointers to null
392         theCacheObject.setNextLruObject(null);
393         theCacheObject.setPreviousLruObject(null);
394 
395         // update the cache stats.
396         m_objectCosts -= theCacheObject.getLruCacheCosts();
397         m_objectCount--;
398     }
399 
400     /**
401      * Removes the last recently used objects from the list of all cached objects as long
402      * as the costs of all cached objects are higher than the allowed avg. costs of the cache.<p>
403      */
404     private void gc() {
405 
406         I_CmsLruCacheObject currentObject = m_listTail;
407         while (currentObject != null) {
408             if (m_objectCosts < m_avgCacheCosts) {
409                 break;
410             }
411             currentObject = currentObject.getNextLruObject();
412             removeTail();
413         }
414 
415     }
416 
417     /**
418      * Increase this caches statistics 
419      * and notify the cached object that it was added to this cache.<p>
420      *
421      * @param theCacheObject the object being notified that it was added to the cache
422      */
423     private void increaseCache(I_CmsLruCacheObject theCacheObject) {
424 
425         // notify the object that it was now added to the cache
426         //theCacheObject.notify();
427         theCacheObject.addToLruCache();
428 
429         // update the cache stats.
430         m_objectCosts += theCacheObject.getLruCacheCosts();
431         m_objectCount++;
432     }
433 
434     /**
435      * Test if a given object resides inside the cache.<p>
436      *
437      * @param theCacheObject the object to test 
438      * @return true if the object is inside the cache, false otherwise
439      */
440     private boolean isCached(I_CmsLruCacheObject theCacheObject) {
441 
442         if (theCacheObject == null || m_objectCount == 0) {
443             // the cache is empty or the object is null (which is never cached)
444             return false;
445         }
446 
447         I_CmsLruCacheObject nextObj = theCacheObject.getNextLruObject();
448         I_CmsLruCacheObject prevObj = theCacheObject.getPreviousLruObject();
449 
450         if ((nextObj != null) || (prevObj != null)) {
451             // the object has either a predecessor or successor in the linked 
452             // list of all cached objects, so it is inside the cache
453             return true;
454         }
455 
456         if ((nextObj == null) && (prevObj == null)) {
457             if ((m_objectCount == 1)
458                 && (m_listHead != null)
459                 && (m_listTail != null)
460                 && m_listHead.equals(theCacheObject)
461                 && m_listTail.equals(theCacheObject)) {
462                 // the object is the one and only object in the cache
463                 return true;
464             }
465         }
466 
467         return false;
468     }
469 
470     /**
471      * Removes the tailing object from the list of all cached objects.<p>
472      */
473     private synchronized void removeTail() {
474 
475         I_CmsLruCacheObject oldTail = m_listTail;
476         if (oldTail != null) {
477             I_CmsLruCacheObject newTail = oldTail.getNextLruObject();
478 
479             // set the list pointers correct
480             if (newTail != null) {
481                 // there are still objects remaining in the list
482                 newTail.setPreviousLruObject(null);
483                 m_listTail = newTail;
484             } else {
485                 // we removed the last object from the list
486                 m_listTail = null;
487                 m_listHead = null;
488             }
489 
490             // update cache stats. and notify the cached object
491             decreaseCache(oldTail);
492         }
493     }
494 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags