MultiLruCache


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.text.MessageFormat  ;
33  
34  import java.util.Properties  ;
35  import java.util.Map  ;
36  import java.util.ResourceBundle  ;
37  
38  /**
39   * MultiLruCache -- in-memory bounded LRU cache with multiple LRU lists
40   * Underlying Hashtable is made into logical segments, with each segment
41   * having its own LRU list.
42   */
43  public class MultiLruCache extends BaseCache {
44  
45      /* an array of LRU lists; each element in this array is actually
46       * LruCacheItem[2] with LRU list (lru[0] is head and lru[1] the tail
47       */
48      public static final int LRU_HEAD = 0;
49      public static final int LRU_TAIL = 1;
50      public static final int DEFAULT_HASHTABLE_SEGMENT_SIZE = 4096;
51  
52      int segmentSize;
53      LruCacheItem[][] lists;
54      protected int[] listsLength;
55  
56      int trimCount;
57      int trimIndex;
58      Object   trimIndexLk = new Object  ();
59  
60      /**
61       * initialize the LRU cache
62       * @param maxCapacity maximum number of entries this cache may hold
63       */
64      public void init(int maxCapacity, Properties   props) throws Exception   {
65          super.init(maxCapacity, props);
66  
67          segmentSize = DEFAULT_HASHTABLE_SEGMENT_SIZE;
68  
69          if (props != null) {
70              String   prop = props.getProperty("MultiLRUSegmentSize");
71              if (prop != null) {
72                  try {
73                      segmentSize = Integer.parseInt(prop);
74                  } catch (NumberFormatException   nfe) {}
75              }
76          }
77  
78          // create the array of LRU lists
79          int segments = ((maxBuckets / segmentSize) +
80                          (((maxBuckets % segmentSize) != 0) ? 1 : 0));
81          lists = new LruCacheItem[segments][2];
82          listsLength = new int[lists.length];
83          for (int i = 0; i < lists.length; i++) {
84              lists[i][LRU_HEAD] = null;
85              lists[i][LRU_TAIL] = null;
86  
87              listsLength[i] = 0;
88          }
89      }
90  
91      /**
92       * get the LRU list associated with the index
93       * @param index into the BaseCache hashtable
94       * @return the LRU list to be used
95       */
96      private LruCacheItem[] getLRUList(int index) {
97          int segment = (index/segmentSize);
98          return lists[segment];
99      }
100 
101     /**
102      * create new item
103      * @param hashCode for the entry
104      * @param key <code>Object</code> key 
105      * @param value <code>Object</code> value
106      * @param size size in bytes of the item
107      * 
108      * subclasses may override to provide their own CacheItem extensions
109      * e.g. one that permits persistence.
110      */
111     protected CacheItem createItem(int hashCode, Object   key, 
112                                         Object   value, int size) {
113         return new LruCacheItem(hashCode, key, value, size);
114     }
115 
116     /**
117      * remove an lru item from one of the LRU lists
118      * @param the LRU segment index to trim
119      * @return the item that was successfully trimmed
120      */
121     protected CacheItem trimLru(int segment) {
122         LruCacheItem[] list = lists[segment];
123         LruCacheItem l = null;
124 
125         l = list[LRU_TAIL];
126 
127         list[LRU_TAIL] = l.lPrev;
128         list[LRU_TAIL].lNext = null;
129    
130         l.lPrev = null;
131         listsLength[segment]--;
132             
133         l.isTrimmed = true;
134 
135         trimCount++;
136 
137         return l;
138     }
139 
140     /**
141      * this item is just added to the cache
142      * @param item <code>CacheItem</code> that was created
143      * @return a overflow item; may be null
144      *
145      * Cache bucket is already synchronized by the caller
146      */
147     protected CacheItem itemAdded(CacheItem item) {
148         CacheItem overflow = null;
149         LruCacheItem lc = (LruCacheItem) item;
150 
151         int index = getIndex(item.hashCode());
152         int segment = (index/segmentSize);
153         LruCacheItem[] list = lists[segment];
154 
155         // update the LRU
156         synchronized (list) {
157             if (list[LRU_HEAD] != null) {
158                 list[LRU_HEAD].lPrev = lc;
159                 lc.lNext = list[LRU_HEAD];
160             }
161             else
162                 list[LRU_TAIL] = lc;
163             list[LRU_HEAD] = lc;
164 
165             listsLength[segment]++;
166 
167             if (isThresholdReached()) {
168                 overflow = trimLru(trimIndex);
169                 // go round robin for the next trim
170                 incrementTrimIndex();
171             }
172         }
173 
174         return overflow;
175     }
176 
177     /**
178      * this item is accessed 
179      * @param item <code>CacheItem</code> accessed
180      *
181      * Cache bucket is already synchronized by the caller
182      */
183     protected void itemAccessed(CacheItem item) {
184         int index = getIndex(item.hashCode());
185         int segment = (index/segmentSize);
186         LruCacheItem[] list = lists[segment];
187 
188         LruCacheItem lc = (LruCacheItem) item;
189 
190         // update the LRU list
191         synchronized (list) {
192             LruCacheItem prev = lc.lPrev;
193             LruCacheItem next = lc.lNext;
194 
195             if (prev != null) {
196                 // put the item at the head of LRU list
197                 lc.lPrev = null;
198                 lc.lNext = list[LRU_HEAD];
199                 list[LRU_HEAD].lPrev = lc;
200                 list[LRU_HEAD] = lc;
201     
202                 // patch up the previous neighbors
203                 prev.lNext = next;
204                 if (next != null)
205                     next.lPrev = prev;
206                 else
207                     list[LRU_TAIL] = prev;
208 
209            }
210         }
211     }
212 
213     /**
214      * item value has been refreshed
215      * @param item <code>CacheItem</code> that was refreshed
216      * @param oldSize size of the previous value that was refreshed
217      * Cache bucket is already synchronized by the caller
218      */
219     protected void itemRefreshed(CacheItem item, int oldSize) {
220         itemAccessed(item);   
221     }
222 
223     /**
224      * item value has been removed from the cache
225      * @param item <code>CacheItem</code> that was just removed
226      *
227      * Cache bucket is already synchronized by the caller
228      */
229     protected void itemRemoved(CacheItem item) {
230         LruCacheItem l = (LruCacheItem) item;
231 
232         int index = getIndex(item.hashCode());
233         int segment = (index/segmentSize);
234         LruCacheItem[] list = lists[segment];
235 
236         // remove the item from the LRU list
237         synchronized (list) {
238             // if the item is already trimmed from the LRU list, nothing to do.
239             if (l.isTrimmed)
240                 return;
241 
242             LruCacheItem prev = l.lPrev;
243             LruCacheItem next = l.lNext;
244 
245             // patch up the neighbors and make sure head/tail are correct
246             if (prev != null)
247                 prev.lNext = next;
248             else
249                 list[LRU_HEAD] = next;
250 
251             if (next != null)
252                 next.lPrev = prev;
253             else
254                 list[LRU_TAIL] = prev;
255 
256             listsLength[segment]--;
257         }
258     }
259 
260     /**
261      * cache has reached threshold so trim its size. subclasses are expected
262      * to provide a robust cache replacement algorithm.
263      */
264     protected void handleOverflow() {
265         LruCacheItem l = null;
266 
267     }
268 
269     int getListsLength() {
270         return lists.length;
271     }
272 
273     protected void incrementTrimIndex() {
274         synchronized (trimIndexLk) {
275             trimIndex = (trimIndex + 1) % lists.length;
276         }
277     }
278 
279     /**
280      * get generic stats from subclasses 
281      */
282 
283     /**
284      * get the desired statistic counter
285      * @param key to corresponding stat
286      * @return an Object corresponding to the stat
287      * See also: Constant.java for the key
288      */
289     public Object   getStatByName(String   key) {
290         Object   stat = super.getStatByName(key);
291 
292         if (stat == null && key != null) {
293             if (key.equals(Constants.STAT_MULTILRUCACHE_SEGMENT_SIZE))
294                 stat = new Integer  (segmentSize);
295             else if (key.equals(Constants.STAT_MULTILRUCACHE_TRIM_COUNT))
296                 stat = new Integer  (trimCount);
297             else if (key.equals(Constants.STAT_MULTILRUCACHE_SEGMENT_LIST_LENGTH)) {
298                 stat = new Integer  [lists.length];
299 
300                 for (int i = 0; i < lists.length; i++) {
301                     ((Integer  [])stat)[i] = new Integer  (listsLength[i]);
302                 }
303             }
304         }
305 
306         return stat;
307     }
308 
309     /**
310      * get the stats snapshot
311      * @return a Map of stats
312      * See also: Constant.java for the keys
313      */
314     public Map   getStats() {
315         Map   stats = super.getStats();
316 
317         stats.put(Constants.STAT_MULTILRUCACHE_SEGMENT_SIZE, new Integer  (segmentSize));
318         for (int i = 0; i < lists.length; i++) {
319             stats.put(Constants.STAT_MULTILRUCACHE_SEGMENT_LIST_LENGTH + "[" + i + "]:",
320                             new Integer  (listsLength[i]));
321         }
322         stats.put(Constants.STAT_MULTILRUCACHE_TRIM_COUNT, new Integer  (trimCount));
323         return stats;
324     }
325 
326     /** default CacheItem class implementation  ***/
327     static class LruCacheItem extends BaseCache.CacheItem {
328 
329         // double linked LRU list
330         LruCacheItem lNext;
331         LruCacheItem lPrev;
332         boolean isTrimmed;
333 
334         LruCacheItem(int hashCode, Object   key, Object   value, int size) {
335             super(hashCode, key, value, size);
336         }
337     }
338 }
339
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags