KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jboss > cache > eviction > LFUQueue


1 /*
2  * JBoss, the OpenSource J2EE webOS
3  *
4  * Distributable under LGPL license.
5  * See terms of license at gnu.org.
6  */
7 package org.jboss.cache.eviction;
8
9 import org.jboss.cache.Fqn;
10
11 import java.util.Collections JavaDoc;
12 import java.util.Comparator JavaDoc;
13 import java.util.HashMap JavaDoc;
14 import java.util.HashSet JavaDoc;
15 import java.util.Iterator JavaDoc;
16 import java.util.LinkedList JavaDoc;
17 import java.util.List JavaDoc;
18 import java.util.Map JavaDoc;
19 import java.util.NoSuchElementException JavaDoc;
20 import java.util.Set JavaDoc;
21
22 /**
23  * LFUQueue EvictionQueue implementation for LFU Policy.
24  * <p/>
25  * The queue is sorted in least frequently used order.
26  *
27  * @author Daniel Huang (dhuang@jboss.org)
28  * @version $Revision: 1.5 $
29  */
30 public class LFUQueue implements SortedEvictionQueue
31 {
32    private Map JavaDoc nodeMap;
33    private LinkedList JavaDoc evictionList;
34    private Comparator JavaDoc comparator;
35
36    private Set JavaDoc removalQueue;
37    private int numElements = 0;
38
39    LFUQueue()
40    {
41       nodeMap = new HashMap JavaDoc();
42       comparator = new LFUComparator();
43       evictionList = new LinkedList JavaDoc();
44       removalQueue = new HashSet JavaDoc();
45    }
46
47    /**
48     * Return the first node to evict.
49     * <p/>
50     * This method will return the least frequently used entry in the queue.
51     */
52    public NodeEntry getFirstNodeEntry()
53    {
54       try
55       {
56          NodeEntry ne;
57          while ((ne = (NodeEntry) evictionList.getFirst()) != null)
58          {
59             if (removalQueue.contains(ne))
60             {
61                evictionList.removeFirst();
62                removalQueue.remove(ne);
63             }
64             else
65             {
66                break;
67             }
68          }
69          return ne;
70       }
71       catch (NoSuchElementException JavaDoc e)
72       {
73          //
74 }
75
76       return null;
77    }
78
79    public NodeEntry getNodeEntry(Fqn fqn)
80    {
81       return (NodeEntry) nodeMap.get(fqn);
82    }
83
84    public NodeEntry getNodeEntry(String JavaDoc fqn)
85    {
86       return this.getNodeEntry(Fqn.fromString(fqn));
87    }
88
89    public boolean containsNodeEntry(NodeEntry entry)
90    {
91       Fqn fqn = entry.getFqn();
92       return this.getNodeEntry(fqn) != null;
93    }
94
95    public void removeNodeEntry(NodeEntry entry)
96    {
97       NodeEntry ne = (NodeEntry) nodeMap.remove(entry.getFqn());
98       if (ne != null)
99       {
100          // don't remove directly from the LinkedList otherwise we will incur a O(n) = n
101 // performance penalty for every removal! In the prune method for LFU, we will iterate the LinkedList through ONCE
102 // doing a single O(n) = n operation and removal. This is much preferred over running O(n) = n every single time
103 // remove is called. There is also special logic in the getFirstNodeEntry that will know to check
104 // the removalQueue before returning.
105 this.removalQueue.add(ne);
106 /* if(!evictionList.remove(ne)) {
107             throw new RuntimeException("");
108          } */
109          this.numElements -= ne.getNumberOfElements();
110       }
111    }
112
113    public void addNodeEntry(NodeEntry entry)
114    {
115       if (!this.containsNodeEntry(entry))
116       {
117          Fqn fqn = entry.getFqn();
118          entry.queue = this;
119          nodeMap.put(fqn, entry);
120          evictionList.add(entry);
121          this.numElements += entry.getNumberOfElements();
122       }
123    }
124
125    public int getNumberOfNodes()
126    {
127       return nodeMap.size();
128    }
129
130    public int getNumberOfElements()
131    {
132       return this.numElements;
133    }
134
135    public void clear()
136    {
137       nodeMap.clear();
138       evictionList.clear();
139       removalQueue.clear();
140       this.numElements = 0;
141    }
142
143    public void resortEvictionQueue()
144    {
145       Collections.sort(evictionList, comparator);
146    }
147
148    public void modifyElementCount(int difference)
149    {
150       this.numElements += difference;
151    }
152
153    void prune()
154    {
155       Iterator JavaDoc it = this.iterate();
156       while (it.hasNext() && removalQueue.size() > 0)
157       {
158          if (removalQueue.remove(it.next()))
159          {
160             it.remove();
161          }
162       }
163    }
164
165    // provided as friend access for unit testing only.
166 final List JavaDoc getEvictionList()
167    {
168       return this.evictionList;
169    }
170
171    // provided as friend access for unit testing only.
172 final Set JavaDoc getRemovalQueue()
173    {
174       return this.removalQueue;
175    }
176
177    public Iterator JavaDoc iterate()
178    {
179       return evictionList.iterator();
180    }
181
182    /**
183     * Comparator class for LFU.
184     * <p/>
185     * This class will sort the eviction queue in the correct eviction order.
186     * The top of the list should evict before the bottom of the list.
187     * <p/>
188     * The sort is based on ascending order of nodeVisits.
189     * <p/>
190     * Note: this class has a natural ordering that is inconsistent with equals as defined by the java.lang.Comparator
191     * contract.
192     */
193    static class LFUComparator implements Comparator JavaDoc
194    {
195       LFUComparator()
196       {
197       }
198
199       public int compare(Object JavaDoc o, Object JavaDoc o1)
200       {
201          if (o.equals(o1))
202          {
203             return 0;
204          }
205          NodeEntry ne = (NodeEntry) o;
206          NodeEntry ne2 = (NodeEntry) o1;
207
208          int neNodeHits = ne.getNumberOfNodeVisits();
209          int ne2NodeHits = ne2.getNumberOfNodeVisits();
210
211          if (neNodeHits > ne2NodeHits)
212          {
213             return 1;
214          }
215          else if (neNodeHits < ne2NodeHits)
216          {
217             return -1;
218          }
219          else if (neNodeHits == ne2NodeHits)
220          {
221             return 0;
222          }
223
224          throw new RuntimeException JavaDoc("Should never reach this condition");
225       }
226    }
227
228 }
229
230
Popular Tags