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 ; 9 import java.util.List ; 10 import java.util.Map ; 11 12 13 19 class LfuCache extends AbstractPolicyCache implements ReapableCache 20 { 21 22 private static final Log LOG = new Log(LfuCache.class); 23 private final Map map; 24 private final LinkedList fifo; 25 private final List lrus; 26 private int maxLruBuckets = 0; 27 28 private int lowestNonEmptyLru = 0; 33 34 public LfuCache(String 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 (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 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 userKey, Object 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 break; 175 } 176 } 177 } 178 179 180 String dumpLfuKeys() 182 { 183 184 String dump = null; 185 StringBuffer sb = new StringBuffer (); 186 LinkedListNode node = null; 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 dumpFifoKeys() 212 { 213 214 String dump = null; 215 StringBuffer sb = new StringBuffer (); 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 |