KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > jodd > cache > LFUCache


1 // Copyright (c) 2003-2007, Jodd Team (jodd.sf.net). All Rights Reserved.
2
3 package jodd.cache;
4
5 import java.util.*;
6
7 /**
8  * LFU (least frequently used) cache.
9  *
10  * <p>
11  * Frequency of use data is kept on all items. The most frequently used items are kept in the cache.
12  * Because of the bookkeeping requirements, cache access overhead increases logarithmically with cache size.
13  * The advantage is that long term usage patterns are captured well, incidentally making the algorithm scan resistant;
14  * the disadvantage, besides the larger access overhead, is that the algorithm doesn't adapt quickly to changing
15  * usage patterns, and in particular doesn't help with temporally clustered accesses.<br>
16  * Summary for LFU: not fast, captures frequency of use, scan resistant.
17  */
18 public class LFUCache extends AbstractCacheMap {
19
20     public LFUCache(int maxSize) {
21         this(maxSize, 0);
22     }
23
24     public LFUCache(int maxSize, long timeout) {
25         this.cacheSize = maxSize;
26         this.timeout = timeout;
27         cacheMap = new HashMap(maxSize + 1);
28     }
29
30
31     // ---------------------------------------------------------------- prune
32
33     /**
34      * Prunes expired and, if cache is still full, the LFU element from the cache.
35      * On LFU removal, access count is normalized to value which had removed object.
36      * Returns the number of removed objects.
37      */
38     public synchronized int prune() {
39         int count = 0;
40         CacheObject comin = null;
41         Iterator values = cacheMap.values().iterator();
42         while (values.hasNext()) {
43             CacheObject co = (CacheObject) values.next();
44             if (co.isExpired() == true) {
45                 values.remove();
46                 count++;
47                 continue;
48             }
49             
50             if (comin == null) {
51                 comin = co;
52             } else {
53                 if (co.accessCount < comin.accessCount) {
54                     comin = co;
55                 }
56             }
57         }
58
59         if (isFull() == false) {
60             return count;
61         }
62         if (comin != null) {
63             values = cacheMap.values().iterator();
64             while (values.hasNext()) {
65                 CacheObject co = (CacheObject) values.next();
66                 co.accessCount -= comin.accessCount;
67                 if (co.accessCount <= 0) {
68                     values.remove();
69                     count++;
70                 }
71             }
72         }
73         return count;
74     }
75
76 }
77
Popular Tags