LruCache


1   /*
2    * The contents of this file are subject to the terms 
3    * of the Common Development and Distribution License 
4    * (the License).  You may not use this file except in
5    * compliance with the License.
6    * 
7    * You can obtain a copy of the license at 
8    * https://glassfish.dev.java.net/public/CDDLv1.0.html or
9    * glassfish/bootstrap/legal/CDDLv1.0.txt.
10   * See the License for the specific language governing 
11   * permissions and limitations under the License.
12   * 
13   * When distributing Covered Code, include this CDDL 
14   * Header Notice in each file and include the License file 
15   * at glassfish/bootstrap/legal/CDDLv1.0.txt.  
16   * If applicable, add the following below the CDDL Header, 
17   * with the fields enclosed by brackets [] replaced by
18   * you own identifying information: 
19   * "Portions Copyrighted [year] [name of copyright owner]"
20   * 
21   * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
22   */
23  
24  /**
25   * Copyright 2000-2001 by iPlanet/Sun Microsystems, Inc.,
26   * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
27   * All rights reserved.
28   */
29   
30  package com.sun.appserv.util.cache;
31  
32  import java.util.ArrayList  ;
33  import java.util.Map  ;
34  import java.util.Properties  ;
35  import java.util.ResourceBundle  ;
36  
37  /**
38   * LRUCache
39   * in-memory bounded cache with an LRU list
40   */
41  public class LruCache extends BaseCache {
42  
43      // the item never expires
44      public static final long NO_TIMEOUT = -1;
45  
46      // LRU list
47      protected LruCacheItem head;
48      protected LruCacheItem tail;
49  
50      // the number of times the cache was trimmed
51      protected int trimCount;
52  
53      protected int listSize;
54      protected long timeout = NO_TIMEOUT;
55  
56      protected int defaultMaxEntries = Constants.DEFAULT_MAX_ENTRIES;
57      protected boolean isUnbounded = false;
58  
59      /**
60       * default constructor
61       */
62      public LruCache() { }
63  
64      /**
65       * constructor with specified max entries.
66       * @param defaultMaxEntries specifies the default max entries
67       *        to use when the maxEntries is <= 0.
68       */
69      public LruCache(int defaultMaxEntries) {
70          this.defaultMaxEntries = defaultMaxEntries;
71      }
72  
73      /**
74       * initialize the cache
75       * @param maxEntries maximum number of entries expected in the cache
76       * @param loadFactor the load factor
77       * @param timeout to be used to trim the expired entries
78       * @param props opaque list of properties for a given cache implementation
79       * @throws a generic Exception if the initialization failed
80       */
81      public void init(int maxEntries, long timeout, float loadFactor, Properties   props) {
82  
83          // if the max entries is <= 0 then set the default max entries
84          if (maxEntries <= 0) {
85              maxEntries = defaultMaxEntries;
86  
87              // mark this cache unbounded
88              isUnbounded = true;
89          }
90          setTimeout(timeout);
91  
92          super.init(maxEntries, loadFactor, props);
93      }
94  
95      /**
96       * sets the timeout value
97       * @param timeout to be used to trim the expired entries
98       */
99      public void setTimeout(long timeout) {
100         // accept a positive timeout
101         if (timeout > 0)
102             this.timeout = timeout;
103     }
104 
105     /**
106      * create new item
107      * @param hashCode for the entry
108      * @param key <code>Object</code> key 
109      * @param value <code>Object</code> value
110      * @param size size in bytes of the item
111      * 
112      * subclasses may override to provide their own CacheItem extensions
113      * e.g. one that permits persistence.
114      */
115     protected CacheItem createItem(int hashCode, Object   key, 
116                                         Object   value, int size) {
117         return new LruCacheItem(hashCode, key, value, size);
118     }
119 
120     /**
121      * trim one item from the LRU list
122      * @param currentTime of this operation
123      * @return the item trimmed from cache
124      *
125      * list synchronization is handled by the caller
126      */
127     protected CacheItem trimLru(long currentTime) {
128 
129         LruCacheItem trimItem = tail;
130 
131         if (tail != head) {
132             tail = trimItem.lPrev;
133             if(tail == null) {
134                 //TODO:: print out a warning message here
135                 tail = head = null;
136             } else {
137                 tail.lNext = null;
138                 trimItem.lPrev = null;
139             }
140         } else {
141             tail = head = null;
142         }
143 
144         if (trimItem != null) {
145             trimItem.isTrimmed = true;
146             trimItem.lPrev = null;
147             trimCount++;
148             listSize--;
149         }
150 
151         return trimItem;
152     }
153 
154     /**
155     /**
156      * this item is just added to the cache
157      * @param item <code>CacheItem</code> that was created
158      * @return a overflow item; may be null
159      *
160      * this function checks if adding the new item results in a overflow;
161      * if so, it returns the item to be removed.
162      *
163      * Cache bucket is already synchronized by the caller
164      */
165     protected CacheItem itemAdded(CacheItem item) {
166         boolean updateThreshold = false;
167         CacheItem overflow = null;
168         LruCacheItem lc = (LruCacheItem) item;
169 
170         // set the timestamp
171         lc.lastAccessed = System.currentTimeMillis();
172 
173         // update the LRU
174         synchronized (this) {
175             if (head != null) {
176                 head.lPrev = lc;
177                 lc.lNext = head;
178                 lc.lPrev = null;
179                 head = lc;
180             }
181             else {
182                 head = tail = lc;
183                 lc.lPrev = lc.lNext = null;
184             }
185 
186             listSize++;
187 
188             if (isThresholdReached()) {
189                 if (!isUnbounded) 
190                     overflow = trimLru(lc.lastAccessed);
191                 else
192                     updateThreshold = true;
193             }
194         }
195 
196         // update the base cache threshold if needed
197         if (updateThreshold)
198             super.handleOverflow(); 
199 
200         return overflow;
201     }
202 
203     /**
204      * this item is accessed 
205      * @param item <code>CacheItem</code> accessed
206      *
207      * Cache bucket is already synchronized by the caller
208      */
209     protected void itemAccessed(CacheItem item) {
210         LruCacheItem lc = (LruCacheItem) item;
211 
212         synchronized (this) {
213 
214             // if the item is already trimmed from the LRU list, nothing to do.
215             if (lc.isTrimmed)
216                 return;
217 
218             // update the timestamp
219             lc.lastAccessed = System.currentTimeMillis();
220 
221             LruCacheItem prev = lc.lPrev;
222             LruCacheItem next = lc.lNext;
223             // update the LRU list
224             if (prev != null) {
225                 // put the item at the head of LRU list
226                 lc.lPrev = null;
227                 lc.lNext = head;
228                 head.lPrev = lc;
229                 head = lc;
230     
231                 // patch up the previous neighbors
232                 prev.lNext = next;
233                 if (next != null)
234                     next.lPrev = prev;
235                 else
236                     tail = prev;
237            }
238         }
239     }
240 
241     /**
242      * item value has been refreshed
243      * @param item <code>CacheItem</code> that was refreshed
244      * @param oldSize size of the previous value that was refreshed
245      * Cache bucket is already synchronized by the caller
246      */
247     protected void itemRefreshed(CacheItem item, int oldSize) {
248         itemAccessed(item);   
249     }
250 
251     /**
252      * item value has been removed from the cache
253      * @param item <code>CacheItem</code> that was just removed
254      *
255      * Cache bucket is already synchronized by the caller
256      */
257     protected void itemRemoved(CacheItem item) {
258         LruCacheItem l = (LruCacheItem) item;
259 
260         // remove the item from the LRU list
261         synchronized (this) {
262             LruCacheItem prev = l.lPrev;
263             LruCacheItem next = l.lNext;
264 
265             // if the item is already trimmed from the LRU list, nothing to do.
266             if (l.isTrimmed)
267                 return;
268 
269             // patch up the neighbors and make sure head/tail are correct
270             if (prev != null)
271                 prev.lNext = next;
272             else
273                 head = next;
274 
275             if (next != null)
276                 next.lPrev = prev;
277             else
278                 tail = prev;
279 
280             l.lPrev = l.lNext = null;
281             listSize--;
282         }
283     }
284 
285     /**
286      * trim the expired entries from the cache.
287      * @param maxCount maximum number of invalid entries to trim
288      *        specify Integer.MAX_VALUE to trim all invalid entries
289      * This call is to be scheduled by a thread managed by the container.
290      *
291      * NOTE: this algorithm assumes that all the entries in the cache have
292      * identical timeout (otherwise traversing from tail won't be right).
293      */
294     public void trimExpiredEntries(int maxCount) {
295         
296         int count = 0;
297         LruCacheItem item;
298         long currentTime = System.currentTimeMillis();
299         ArrayList   list = new ArrayList  ();
300 
301         synchronized (this) {
302             // traverse LRU list till we reach a valid item; remove them at once
303             for (item = tail; item != null && count < maxCount;
304                                                 item = item.lPrev) {
305 
306                 if (timeout != NO_TIMEOUT && 
307                     (item.lastAccessed + timeout) <= currentTime) {
308                     item.isTrimmed = true;
309             list.add(item);
310 
311                     count++;
312                 } else
313                     break;
314             }
315 
316             // if there was at least one invalid item then item != tail.
317             if (item != tail) {
318                 if (item != null)
319                     item.lNext = null;
320                 else
321                     head = null;
322 
323                 tail = item;
324             }
325             listSize -= count;
326             trimCount += count;
327         }
328         
329         // trim the items from the BaseCache from the old tail backwards
330         for (int index=list.size()-1; index >= 0; index--) {
331             trimItem((LruCacheItem) list.get(index));
332         }
333     }
334 
335 
336     /**
337      * get generic stats from subclasses 
338      */
339 
340     /**
341      * get the desired statistic counter
342      * @param key to corresponding stat
343      * @return an Object corresponding to the stat
344      * See also: Constant.java for the key
345      */
346     public Object   getStatByName(String   key) {
347         Object   stat = super.getStatByName(key);
348 
349         if (stat == null && key != null) {
350             if (key.equals(Constants.STAT_LRUCACHE_LIST_LENGTH))
351                 stat = new Integer  (listSize);
352             else if (key.equals(Constants.STAT_LRUCACHE_TRIM_COUNT))
353                 stat = new Integer  (trimCount);
354         }
355         return stat;
356     }
357 
358     public Map   getStats() {
359         Map   stats = super.getStats();
360         stats.put(Constants.STAT_LRUCACHE_LIST_LENGTH, new Integer  (listSize));
361         stats.put(Constants.STAT_LRUCACHE_TRIM_COUNT, new Integer  (trimCount));
362 
363         return stats;
364     }
365 
366     /** default CacheItem class implementation  ***/
367     protected static class LruCacheItem extends CacheItem {
368 
369         // double linked LRU list
370         protected LruCacheItem lNext;
371         protected LruCacheItem lPrev;
372         protected boolean isTrimmed;
373         protected long lastAccessed;
374 
375         protected LruCacheItem(int hashCode, Object   key, Object   value, int size) {
376             super(hashCode, key, value, size);
377         }
378     }
379 }
380 
381
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags