KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > shiftone > cache > policy > lfu > LfuCache


1 package org.shiftone.cache.policy.lfu;
2
3
4
5 import org.shiftone.cache.util.*;
6 import org.shiftone.cache.util.reaper.ReapableCache;
7
8 import java.util.ArrayList JavaDoc;
9 import java.util.List JavaDoc;
10 import java.util.Map JavaDoc;
11
12
13 /**
14  * Class LfuCache
15  *
16  * @author <a HREF="mailto:jeff@shiftone.org">Jeff Drost</a>
17  * @version $Revision: 1.7 $
18  */

19 class LfuCache extends AbstractPolicyCache implements ReapableCache
20 {
21
22     private static final Log LOG = new Log(LfuCache.class);
23     private final Map JavaDoc map;
24     private final LinkedList fifo;
25     private final List JavaDoc lrus;
26     private int maxLruBuckets = 0;
27
28     // when searching for a node to remove, the lowest lru bucked is checked
29
// then then next, etc etc. In some rare cases, we have extra information that
30
// would allow a higher bucket to be used to start the search.
31
// This is a minor optimizaton.
32
private int lowestNonEmptyLru = 0;
33
34     public LfuCache(String JavaDoc name, long timeoutMilliSeconds, int maxSize)
35     {
36
37         super(name, timeoutMilliSeconds, maxSize);
38
39         map = MapFactory.createMap(maxSize);
40         fifo = new LinkedList();
41         lrus = new ArrayList JavaDoc(5);
42         maxLruBuckets = maxSize * 3;
43     }
44
45
46     protected final LinkedList lru(int numUsageIndex)
47     {
48
49         LinkedList lru = null;
50         int lruIndex = Math.min(maxLruBuckets, numUsageIndex);
51
52         if (lruIndex >= lrus.size())
53         {
54             lru = new LinkedList();
55
56             lrus.add(lruIndex, lru);
57         }
58         else
59         {
60             lru = (LinkedList) lrus.get(lruIndex);
61         }
62
63         return lru;
64     }
65
66
67     public int size()
68     {
69         return map.size();
70     }
71
72
73     protected CacheNode findNodeByKey(Object JavaDoc key)
74     {
75         return (LfuNode) map.get(key);
76     }
77
78
79     protected void revalueNode(CacheNode cacheNode)
80     {
81
82         LfuNode node = (LfuNode) cacheNode;
83         LinkedListNode lln = node.lfuNode;
84         LinkedList currBucket = lru(node.numUsages);
85         LinkedList nextBucket = lru(++node.numUsages);
86
87         currBucket.remove(lln);
88
89         node.lfuNode = nextBucket.addFirst(lln.getValue());
90     }
91
92
93     protected void delete(CacheNode cacheNode)
94     {
95
96         LfuNode node = (LfuNode) cacheNode;
97
98         fifo.remove(node.fifoNode);
99         lru(node.numUsages).remove(node.lfuNode);
100         map.remove(node.key);
101     }
102
103
104     protected LinkedList getLowestNonEmptyLru()
105     {
106
107         LinkedList lru = null;
108
109         for (int i = lowestNonEmptyLru; i < lrus.size(); i++)
110         {
111             lru = lru(i);
112
113             if (lru.size() != 0)
114             {
115                 lowestNonEmptyLru = i;
116
117                 return lru;
118             }
119         }
120
121         return lru;
122     }
123
124
125     protected void removeLeastValuableNode()
126     {
127
128         LinkedList lfu = getLowestNonEmptyLru();
129         LinkedListNode lln = lfu.peekLast();
130         LfuNode node = (LfuNode) lln.getValue();
131
132         delete(node);
133     }
134
135
136     protected CacheNode createNode(Object JavaDoc userKey, Object JavaDoc cacheObject)
137     {
138
139         LfuNode node = null;
140
141         node = new LfuNode();
142         node.key = userKey;
143         node.value = cacheObject;
144         node.fifoNode = fifo.addFirst(node);
145         node.lfuNode = lru(0).addFirst(node);
146         node.timeoutTime = System.currentTimeMillis() + getTimeoutMilliSeconds();
147         lowestNonEmptyLru = 0;
148
149         map.put(userKey, node);
150
151         return node;
152     }
153
154
155     public void removeExpiredElements()
156     {
157
158         LinkedListNode lln = null;
159         LfuNode node = null;
160
161         while ((lln = fifo.peekLast()) != null)
162         {
163             lln = fifo.peekLast();
164             node = (LfuNode) lln.getValue();
165
166             if (node.isExpired())
167             {
168                 delete(node);
169             }
170             else
171             {
172
173                 // not expired.. can stop now
174
break;
175             }
176         }
177     }
178
179
180     //------------------------------------------------------------------------
181
String JavaDoc dumpLfuKeys()
182     {
183
184         String JavaDoc dump = null;
185         StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
186         LinkedListNode node = null; //lfu.peekFirst();
187
LfuNode current = null;
188
189         for (int i = lrus.size() - 1; i >= 0; i--)
190         {
191             node = lru(i).peekFirst();
192
193             while (node != null)
194             {
195                 current = (LfuNode) node.getValue();
196
197                 sb.append(current.key);
198
199                 node = node.getNext();
200             }
201         }
202
203         dump = sb.toString();
204
205         LOG.debug("dumpLfuKeys : " + dump);
206
207         return dump;
208     }
209
210
211     String JavaDoc dumpFifoKeys()
212     {
213
214         String JavaDoc dump = null;
215         StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
216         LinkedListNode node = fifo.peekFirst();
217         LfuNode current = null;
218
219         while (node != null)
220         {
221             current = (LfuNode) node.getValue();
222
223             sb.append(current.key);
224
225             node = node.getNext();
226         }
227
228         dump = sb.toString();
229
230         LOG.debug("dumpFifoKeys : " + dump);
231
232         return dump;
233     }
234 }
235
Popular Tags