Source code: com/opencms/flex/util/CmsFlexLruCache.java
1 /*
2 * File : $Source: /usr/local/cvs/opencms/src/com/opencms/flex/util/Attic/CmsFlexLruCache.java,v $
3 * Date : $Date: 2003/02/26 15:19:23 $
4 * Version: $Revision: 1.13 $
5 *
6 * This library is part of OpenCms -
7 * the Open Source Content Mananagement System
8 *
9 * Copyright (C) 2002 - 2003 Alkacon Software (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, 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 com.opencms.flex.util;
33
34 import com.opencms.boot.I_CmsLogChannels;
35 import com.opencms.core.A_OpenCms;
36
37 /**
38 * Implements an LRU (last recently used) cache.<p>
39 *
40 * The idea of this cache to separate the caching policy from the data structure
41 * where the cached objects are stored. The advantage of doing so is, that the CmsFlexLruCache
42 * can identify the last-recently-used object in O(1), whereas you would need at least
43 * O(n) to traverse the data structure that stores the cached objects. Second, you can
44 * easily use the CmsFlexLruCache to get an LRU cache, no matter what data structure is used to
45 * store your objects.
46 * <p>
47 * The cache policy is affected by the "costs" of the objects being cached. Valuable cache costs
48 * might be the byte size of the cached objects for example.
49 * <p>
50 * To add/remove cached objects from the data structure that stores them, the objects have to
51 * implement the methods defined in the interface I_CmsFlexLruCacheObject to be notified when they
52 * are added/removed from the CmsFlexLruCache.
53 *
54 * @see com.opencms.flex.util.I_CmsFlexLruCacheObject
55 * @author Thomas Weckert (t.weckert@alkacon.com)
56 * @version $Revision: 1.13 $
57 */
58 public class CmsFlexLruCache extends java.lang.Object {
59
60 /** The head of the list of double linked LRU cache objects. */
61 private I_CmsFlexLruCacheObject m_ListHead;
62
63 /** The tail of the list of double linked LRU cache objects. */
64 private I_CmsFlexLruCacheObject m_ListTail;
65
66 /** Force a finalization after down-sizing the cache? */
67 private boolean m_ForceFinalization;
68
69 /** The max. sum of costs the cached objects might reach. */
70 private int m_MaxCacheCosts;
71
72 /** The avg. sum of costs the cached objects. */
73 private int m_AvgCacheCosts;
74
75 /** The max. costs of cacheable objects. */
76 private int m_MaxObjectCosts;
77
78 /** The costs of all cached objects. */
79 private int m_ObjectCosts;
80
81 /** The sum of all cached objects. */
82 private int m_ObjectCount;
83
84
85 /**
86 * The constructor with all options.<p>
87 *
88 * @param theMaxCacheCosts the max. cache costs of all cached objects
89 * @param theAvgCacheCosts the avg. cache costs of all cached objects
90 * @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
91 * @param forceFinalization should be true if a system wide garbage collection/finalization is forced after objects were removed from the cache
92 */
93 public CmsFlexLruCache( int theMaxCacheCosts, int theAvgCacheCosts, int theMaxObjectCosts, boolean forceFinalization ) {
94 this.m_ForceFinalization = forceFinalization;
95 this.m_MaxCacheCosts = theMaxCacheCosts;
96 this.m_AvgCacheCosts = theAvgCacheCosts;
97 this.m_MaxObjectCosts = theMaxObjectCosts;
98
99 this.m_ObjectCosts = this.m_ObjectCount = 0;
100 this.m_ListHead = this.m_ListTail = null;
101 }
102
103 /**
104 * Constructor for a LRU cache with forced garbage collection/finalization.<p>
105 *
106 * @param theMaxCacheCosts the max. cache costs of all cached objects
107 * @param theAvgCacheCosts the avg. cache costs of all cached objects
108 * @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
109 */
110 public CmsFlexLruCache( int theMaxCacheCosts, int theAvgCacheCosts, int theMaxObjectCosts ) {
111 this( theMaxCacheCosts, theAvgCacheCosts, theMaxObjectCosts, false );
112 }
113
114 /**
115 * Constructor for a LRU cache with forced garbage collection/finalization, the max. allowed costs of cacheable
116 * objects is 1/4 of the max. costs of all cached objects.<p>
117 *
118 * @param theMaxCacheCosts the max. cache costs of all cached objects
119 * @param theAvgCacheCosts the avg. cache costs of all cached objects
120 */
121 public CmsFlexLruCache( int theMaxCacheCosts, int theAvgCacheCosts ) {
122 this( theMaxCacheCosts, theAvgCacheCosts, theMaxCacheCosts/4, false );
123 }
124
125 /**
126 * Constructor for a LRU cache where the max. allowed costs of cacheable objects is 1/4 of the max. costs of all cached objects.<p>
127 *
128 * @param theMaxCacheCosts the max. cache costs of all cached objects
129 * @param theAvgCacheCosts the avg. cache costs of all cached objects
130 * @param forceFinalization should be true if a system wide garbage collection/finalization is forced after objects were removed from the cache
131 */
132 public CmsFlexLruCache( int theMaxCacheCosts, int theAvgCacheCosts, boolean forceFinalization ) {
133 this( theMaxCacheCosts, theAvgCacheCosts, theMaxCacheCosts/4, forceFinalization );
134 }
135
136 /**
137 * Returns a string representing the current state of the cache.<p>
138 */
139 public String toString() {
140 String objectInfo = "\n";
141
142 objectInfo += "max. cache costs of all cached objects: " + this.m_MaxCacheCosts + "\n";
143 objectInfo += "avg. cache costs of all cached objects: " + this.m_AvgCacheCosts + "\n";
144 objectInfo += "max. cache costs per object: " + this.m_MaxObjectCosts + "\n";
145 objectInfo += "costs of all cached objects: " + this.m_ObjectCosts + "\n";
146 objectInfo += "sum of all cached objects: " + this.m_ObjectCount + "\n";
147
148 if (!this.m_ForceFinalization) {
149 objectInfo += "no ";
150 }
151 objectInfo += "system garbage collection is forced during clean up\n";
152
153 return objectInfo;
154 }
155
156 /**
157 * Adds a new object to this cache.<p>
158 *
159 * If add the same object more than once,
160 * the object is touched instead.<p>
161 *
162 * @param theCacheObject the object being added to the cache
163 * @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
164 */
165 public synchronized boolean add( I_CmsFlexLruCacheObject theCacheObject ) {
166 if (theCacheObject==null) {
167 // null can't be added or touched in the cache
168 return false;
169 }
170
171 // only objects with cache costs < the max. allowed object cache costs can be cached!
172 if ( (this.m_MaxObjectCosts!=-1) && (theCacheObject.getLruCacheCosts()>this.m_MaxObjectCosts) ) {
173 if (I_CmsLogChannels.C_LOGGING && A_OpenCms.isLogging(I_CmsLogChannels.C_FLEX_CACHE))
174 A_OpenCms.log(I_CmsLogChannels.C_FLEX_CACHE, "[FlexLruCache] you are trying to cache objects with cache costs " + theCacheObject.getLruCacheCosts() + " which is bigger than the max. allowed costs " + this.m_MaxObjectCosts );
175 return false;
176 }
177
178 if (!this.isCached(theCacheObject)) {
179 // add the object to the list of all cached objects in the cache
180 this.addHead( theCacheObject );
181 }
182 else {
183 this.touch( theCacheObject );
184 }
185
186 // check if the cache has to trash the last-recently-used objects before adding a new object
187 if (this.m_ObjectCosts>this.m_MaxCacheCosts) {
188 this.gc();
189 }
190
191 return true;
192 }
193
194 /**
195 * Test if a given object resides inside the cache.<p>
196 *
197 * @return true if the object is inside the cache, false otherwise
198 */
199 private boolean isCached( I_CmsFlexLruCacheObject theCacheObject ) {
200 if (theCacheObject==null || this.m_ObjectCount==0) {
201 // the cache is empty or the object is null (which is never cached)
202 return false;
203 }
204
205 if (theCacheObject.getNextLruObject()!=null || theCacheObject.getPreviousLruObject()!=null) {
206 // the object has either a predecessor or successor in the linked
207 // list of all cached objects, so it is inside the cache
208 return true;
209 }
210
211 if (theCacheObject.getNextLruObject()==null && theCacheObject.getPreviousLruObject()==null) {
212 if (this.m_ObjectCount==1 && this.m_ListHead!=null && this.m_ListTail!=null && this.m_ListHead.equals(theCacheObject) && this.m_ListTail.equals(theCacheObject)) {
213 // the object is the one and only object in the cache
214 return true;
215 }
216 }
217
218 return false;
219 }
220
221 /**
222 * Touch an existing object in this cache, in the sense that it's "last-recently-used" state
223 * is updated.<p>
224 *
225 * @param theCacheObject the object being touched
226 */
227 public synchronized boolean touch( I_CmsFlexLruCacheObject theCacheObject ) {
228 if (!this.isCached(theCacheObject)) return false;
229
230 // only objects with cache costs < the max. allowed object cache costs can be cached!
231 if ( (this.m_MaxObjectCosts!=-1) && (theCacheObject.getLruCacheCosts()>this.m_MaxObjectCosts) ) {
232 if (I_CmsLogChannels.C_LOGGING && A_OpenCms.isLogging(I_CmsLogChannels.C_FLEX_CACHE))
233 A_OpenCms.log(I_CmsLogChannels.C_FLEX_CACHE, "[FlexLruCache] you are trying to cache objects with cache costs " + theCacheObject.getLruCacheCosts() + " which is bigger than the max. allowed costs " + this.m_MaxObjectCosts );
234 this.remove( theCacheObject );
235 return false;
236 }
237
238 // set the list pointers correct
239 if (theCacheObject.getNextLruObject()==null) {
240 // case 1: the object is already at the head pos.
241 return true;
242 }
243 else if (theCacheObject.getPreviousLruObject()==null) {
244 // case 2: the object at the tail pos., remove it from the tail to put it to the front as the new head
245 I_CmsFlexLruCacheObject newTail = theCacheObject.getNextLruObject();
246 newTail.setPreviousLruObject( null );
247 this.m_ListTail = newTail;
248 }
249 else {
250 // case 3: the object is somewhere within the list, remove it to put it the front as the new head
251 theCacheObject.getPreviousLruObject().setNextLruObject( theCacheObject.getNextLruObject() );
252 theCacheObject.getNextLruObject().setPreviousLruObject( theCacheObject.getPreviousLruObject() );
253 }
254
255 // set the touched object as the new head in the linked list:
256 I_CmsFlexLruCacheObject oldHead = this.m_ListHead;
257 oldHead.setNextLruObject( theCacheObject );
258 theCacheObject.setNextLruObject( null );
259 theCacheObject.setPreviousLruObject( oldHead );
260 this.m_ListHead = theCacheObject;
261
262 return true;
263 }
264
265 /**
266 * Adds a cache object as the new haed to the list of all cached objects in this cache.<p>
267 *
268 * @param theCacheObject the object being added as the new head to the list of all cached objects
269 */
270 private void addHead( I_CmsFlexLruCacheObject theCacheObject ) {
271 // set the list pointers correct
272 if (this.m_ObjectCount>0) {
273 // there is at least 1 object already in the list
274 I_CmsFlexLruCacheObject oldHead = this.m_ListHead;
275 oldHead.setNextLruObject( theCacheObject );
276 theCacheObject.setPreviousLruObject( oldHead );
277 this.m_ListHead = theCacheObject;
278 }
279 else {
280 // it is the first object to be added to the list
281 this.m_ListTail = this.m_ListHead = theCacheObject;
282 theCacheObject.setPreviousLruObject( null );
283 }
284 theCacheObject.setNextLruObject( null );
285
286 // update cache stats. and notify the cached object
287 this.increaseCache( theCacheObject );
288 }
289
290 /**
291 * Removes an object from the list of all cached objects in this cache,
292 * no matter what position it has inside the list.<p>
293 *
294 * @param theCacheObject the object being removed from the list of all cached objects
295 * @return a reference to the object that was removed
296 */
297 public synchronized I_CmsFlexLruCacheObject remove( I_CmsFlexLruCacheObject theCacheObject ) {
298 if (!this.isCached(theCacheObject)) {
299 // theCacheObject is null or not inside the cache
300 return null;
301 }
302
303 // set the list pointers correct
304 if (theCacheObject.getNextLruObject()==null) {
305 // remove the object from the head pos.
306 I_CmsFlexLruCacheObject newHead = theCacheObject.getPreviousLruObject();
307
308 if (newHead!=null) {
309 // if newHead is null, theCacheObject
310 // was the only object in the cache
311 newHead.setNextLruObject( null );
312 }
313
314 this.m_ListHead = newHead;
315 }
316 else if (theCacheObject.getPreviousLruObject()==null) {
317 // remove the object from the tail pos.
318 I_CmsFlexLruCacheObject newTail = theCacheObject.getNextLruObject();
319
320 if (newTail!=null) {
321 // if newTail is null, theCacheObject
322 // was the only object in the cache
323 newTail.setPreviousLruObject( null );
324 }
325
326 this.m_ListTail = newTail;
327 }
328 else {
329 // remove the object from within the list
330 theCacheObject.getPreviousLruObject().setNextLruObject( theCacheObject.getNextLruObject() );
331 theCacheObject.getNextLruObject().setPreviousLruObject( theCacheObject.getPreviousLruObject() );
332 }
333
334 // update cache stats. and notify the cached object
335 this.decreaseCache( theCacheObject );
336
337 return theCacheObject;
338 }
339
340 /**
341 * Removes the tailing object from the list of all cached objects.<p>
342 */
343 private synchronized void removeTail() {
344 I_CmsFlexLruCacheObject oldTail = null;
345
346 if ((oldTail=this.m_ListTail)!=null) {
347 I_CmsFlexLruCacheObject newTail = oldTail.getNextLruObject();
348
349 // set the list pointers correct
350 if (newTail!=null) {
351 // there are still objects remaining in the list
352 newTail.setPreviousLruObject( null );
353 this.m_ListTail = newTail;
354 }
355 else {
356 // we removed the last object from the list
357 this.m_ListTail = this.m_ListHead = null;
358 }
359
360 // update cache stats. and notify the cached object
361 this.decreaseCache( oldTail );
362 }
363 }
364
365 /**
366 * Decrease this caches statistics
367 * and notify the cached object that it was removed from this cache.<p>
368 *
369 * @param theCacheObject the object being notified that it was removed from the cache
370 */
371 private void decreaseCache( I_CmsFlexLruCacheObject theCacheObject ) {
372 // notify the object that it was now removed from the cache
373 //theCacheObject.notify();
374 theCacheObject.removeFromLruCache();
375
376 // set the list pointers to null
377 theCacheObject.setNextLruObject( null );
378 theCacheObject.setPreviousLruObject( null );
379
380 // update the cache stats.
381 this.m_ObjectCosts -= theCacheObject.getLruCacheCosts();
382 this.m_ObjectCount--;
383 }
384
385 /**
386 * Increase this caches statistics
387 * and notify the cached object that it was added to this cache.<p>
388 *
389 * @param theCacheObject the object being notified that it was added to the cache
390 */
391 private void increaseCache( I_CmsFlexLruCacheObject theCacheObject ) {
392 // notify the object that it was now added to the cache
393 //theCacheObject.notify();
394 theCacheObject.addToLruCache();
395
396 // update the cache stats.
397 this.m_ObjectCosts += theCacheObject.getLruCacheCosts();
398 this.m_ObjectCount++;
399 }
400
401 /**
402 * Removes the last recently used objects from the list of all cached objects as long
403 * as the costs of all cached objects are higher than the allowed avg. costs of the cache.<p>
404 */
405 private void gc() {
406 I_CmsFlexLruCacheObject currentObject = this.m_ListTail;
407 while (currentObject!=null) {
408 if (this.m_ObjectCosts<this.m_AvgCacheCosts) break;
409 currentObject = currentObject.getNextLruObject();
410 this.removeTail();
411 }
412
413 if (m_ForceFinalization) {
414 // force a finalization/system garbage collection optionally
415 Runtime.getRuntime().runFinalization();
416 System.gc();
417 }
418 }
419
420 /**
421 * Returns the count of all cached objects.<p>
422 *
423 * @return the count of all cached objects
424 */
425 public int size() {
426 return this.m_ObjectCount;
427 }
428
429 /**
430 * Clears this cache for finalization.<p>
431 */
432 protected void finalize() throws java.lang.Throwable {
433 this.clear();
434 super.finalize();
435 }
436
437 /**
438 * Removes all cached objects in this cache.<p>
439 */
440 public void clear() {
441 // remove all objects from the linked list from the tail to the head:
442 I_CmsFlexLruCacheObject currentObject = this.m_ListTail;
443 while (currentObject!=null) {
444 currentObject = currentObject.getNextLruObject();
445 this.removeTail();
446 }
447
448 // reset the data structure
449 this.m_ObjectCosts = this.m_ObjectCount = 0;
450 this.m_ListHead = this.m_ListTail = null;
451
452 if (m_ForceFinalization) {
453 // force a finalization/system garbage collection optionally
454 Runtime.getRuntime().runFinalization();
455 System.gc();
456 }
457 }
458
459 /**
460 * Returns the average costs of all cached objects.<p>
461 *
462 * @return the average costs of all cached objects
463 */
464 public int getAvgCacheCosts() {
465 return this.m_AvgCacheCosts;
466 }
467
468 /**
469 * Returns the max costs of all cached objects.<p>
470 *
471 * @return the max costs of all cached objects
472 */
473 public int getMaxCacheCosts() {
474 return this.m_MaxCacheCosts;
475 }
476
477 /**
478 * Returns the max allowed costs per cached object.<p>
479 *
480 * @return the max allowed costs per cached object
481 */
482 public int getMaxObjectCosts() {
483 return this.m_MaxObjectCosts;
484 }
485
486 /**
487 * Returns the current costs of all cached objects.<p>
488 *
489 * @return the current costs of all cached objects
490 */
491 public int getObjectCosts() {
492 return this.m_ObjectCosts;
493 }
494
495 }