001: package org.shiftone.cache.policy.lfu;
002:
003: import org.shiftone.cache.util.*;
004: import org.shiftone.cache.util.reaper.ReapableCache;
005:
006: import java.util.ArrayList;
007: import java.util.List;
008: import java.util.Map;
009:
010: /**
011: * Class LfuCache
012: *
013: * @author <a href="mailto:jeff@shiftone.org">Jeff Drost</a>
014: * @version $Revision: 1.7 $
015: */
016: class LfuCache extends AbstractPolicyCache implements ReapableCache {
017:
018: private static final Log LOG = new Log(LfuCache.class);
019: private final Map map;
020: private final LinkedList fifo;
021: private final List lrus;
022: private int maxLruBuckets = 0;
023:
024: // when searching for a node to remove, the lowest lru bucked is checked
025: // then then next, etc etc. In some rare cases, we have extra information that
026: // would allow a higher bucket to be used to start the search.
027: // This is a minor optimizaton.
028: private int lowestNonEmptyLru = 0;
029:
030: public LfuCache(String name, long timeoutMilliSeconds, int maxSize) {
031:
032: super (name, timeoutMilliSeconds, maxSize);
033:
034: map = MapFactory.createMap(maxSize);
035: fifo = new LinkedList();
036: lrus = new ArrayList(5);
037: maxLruBuckets = maxSize * 3;
038: }
039:
040: protected final LinkedList lru(int numUsageIndex) {
041:
042: LinkedList lru = null;
043: int lruIndex = Math.min(maxLruBuckets, numUsageIndex);
044:
045: if (lruIndex >= lrus.size()) {
046: lru = new LinkedList();
047:
048: lrus.add(lruIndex, lru);
049: } else {
050: lru = (LinkedList) lrus.get(lruIndex);
051: }
052:
053: return lru;
054: }
055:
056: public int size() {
057: return map.size();
058: }
059:
060: protected CacheNode findNodeByKey(Object key) {
061: return (LfuNode) map.get(key);
062: }
063:
064: protected void revalueNode(CacheNode cacheNode) {
065:
066: LfuNode node = (LfuNode) cacheNode;
067: LinkedListNode lln = node.lfuNode;
068: LinkedList currBucket = lru(node.numUsages);
069: LinkedList nextBucket = lru(++node.numUsages);
070:
071: currBucket.remove(lln);
072:
073: node.lfuNode = nextBucket.addFirst(lln.getValue());
074: }
075:
076: protected void delete(CacheNode cacheNode) {
077:
078: LfuNode node = (LfuNode) cacheNode;
079:
080: fifo.remove(node.fifoNode);
081: lru(node.numUsages).remove(node.lfuNode);
082: map.remove(node.key);
083: }
084:
085: protected LinkedList getLowestNonEmptyLru() {
086:
087: LinkedList lru = null;
088:
089: for (int i = lowestNonEmptyLru; i < lrus.size(); i++) {
090: lru = lru(i);
091:
092: if (lru.size() != 0) {
093: lowestNonEmptyLru = i;
094:
095: return lru;
096: }
097: }
098:
099: return lru;
100: }
101:
102: protected void removeLeastValuableNode() {
103:
104: LinkedList lfu = getLowestNonEmptyLru();
105: LinkedListNode lln = lfu.peekLast();
106: LfuNode node = (LfuNode) lln.getValue();
107:
108: delete(node);
109: }
110:
111: protected CacheNode createNode(Object userKey, Object cacheObject) {
112:
113: LfuNode node = null;
114:
115: node = new LfuNode();
116: node.key = userKey;
117: node.value = cacheObject;
118: node.fifoNode = fifo.addFirst(node);
119: node.lfuNode = lru(0).addFirst(node);
120: node.timeoutTime = System.currentTimeMillis()
121: + getTimeoutMilliSeconds();
122: lowestNonEmptyLru = 0;
123:
124: map.put(userKey, node);
125:
126: return node;
127: }
128:
129: public void removeExpiredElements() {
130:
131: LinkedListNode lln = null;
132: LfuNode node = null;
133:
134: while ((lln = fifo.peekLast()) != null) {
135: lln = fifo.peekLast();
136: node = (LfuNode) lln.getValue();
137:
138: if (node.isExpired()) {
139: delete(node);
140: } else {
141:
142: // not expired.. can stop now
143: break;
144: }
145: }
146: }
147:
148: //------------------------------------------------------------------------
149: String dumpLfuKeys() {
150:
151: String dump = null;
152: StringBuffer sb = new StringBuffer();
153: LinkedListNode node = null; //lfu.peekFirst();
154: LfuNode current = null;
155:
156: for (int i = lrus.size() - 1; i >= 0; i--) {
157: node = lru(i).peekFirst();
158:
159: while (node != null) {
160: current = (LfuNode) node.getValue();
161:
162: sb.append(current.key);
163:
164: node = node.getNext();
165: }
166: }
167:
168: dump = sb.toString();
169:
170: LOG.debug("dumpLfuKeys : " + dump);
171:
172: return dump;
173: }
174:
175: String dumpFifoKeys() {
176:
177: String dump = null;
178: StringBuffer sb = new StringBuffer();
179: LinkedListNode node = fifo.peekFirst();
180: LfuNode current = null;
181:
182: while (node != null) {
183: current = (LfuNode) node.getValue();
184:
185: sb.append(current.key);
186:
187: node = node.getNext();
188: }
189:
190: dump = sb.toString();
191:
192: LOG.debug("dumpFifoKeys : " + dump);
193:
194: return dump;
195: }
196: }
|