Source code

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