1 |
| |
2 |
| |
3 |
| |
4 |
| |
5 |
| |
6 |
| |
7 |
| package org.jboss.cache.eviction; |
8 |
| |
9 |
| import org.jboss.cache.Fqn; |
10 |
| |
11 |
| import java.util.Collections; |
12 |
| import java.util.Comparator; |
13 |
| import java.util.HashMap; |
14 |
| import java.util.HashSet; |
15 |
| import java.util.Iterator; |
16 |
| import java.util.LinkedList; |
17 |
| import java.util.List; |
18 |
| import java.util.Map; |
19 |
| import java.util.NoSuchElementException; |
20 |
| import java.util.Set; |
21 |
| |
22 |
| |
23 |
| |
24 |
| |
25 |
| |
26 |
| |
27 |
| |
28 |
| |
29 |
| |
30 |
| public class LFUQueue implements SortedEvictionQueue |
31 |
| { |
32 |
| private Map<Fqn, NodeEntry> nodeMap; |
33 |
| private LinkedList<NodeEntry> evictionList; |
34 |
| private Comparator<NodeEntry> comparator; |
35 |
| |
36 |
| private Set<NodeEntry> removalQueue; |
37 |
| private int numElements = 0; |
38 |
| |
39 |
23
| LFUQueue()
|
40 |
| { |
41 |
23
| nodeMap = new HashMap<Fqn, NodeEntry>();
|
42 |
23
| comparator = new LFUComparator();
|
43 |
23
| evictionList = new LinkedList<NodeEntry>();
|
44 |
23
| removalQueue = new HashSet<NodeEntry>();
|
45 |
| } |
46 |
| |
47 |
| |
48 |
| |
49 |
| |
50 |
| |
51 |
| |
52 |
16302
| public NodeEntry getFirstNodeEntry()
|
53 |
| { |
54 |
16302
| try
|
55 |
| { |
56 |
16302
| NodeEntry ne;
|
57 |
?
| while ((ne = evictionList.getFirst()) != null)
|
58 |
| { |
59 |
32538
| if (removalQueue.contains(ne))
|
60 |
| { |
61 |
16258
| evictionList.removeFirst();
|
62 |
16258
| removalQueue.remove(ne);
|
63 |
| } |
64 |
| else |
65 |
| { |
66 |
16280
| break;
|
67 |
| } |
68 |
| } |
69 |
16280
| return ne;
|
70 |
| } |
71 |
| catch (NoSuchElementException e) |
72 |
| { |
73 |
| |
74 |
| } |
75 |
| |
76 |
22
| return null;
|
77 |
| } |
78 |
| |
79 |
116945
| public NodeEntry getNodeEntry(Fqn fqn)
|
80 |
| { |
81 |
116945
| return nodeMap.get(fqn);
|
82 |
| } |
83 |
| |
84 |
264
| public NodeEntry getNodeEntry(String fqn)
|
85 |
| { |
86 |
264
| return this.getNodeEntry(Fqn.fromString(fqn));
|
87 |
| } |
88 |
| |
89 |
42054
| public boolean containsNodeEntry(NodeEntry entry)
|
90 |
| { |
91 |
42054
| Fqn fqn = entry.getFqn();
|
92 |
42054
| return this.getNodeEntry(fqn) != null;
|
93 |
| } |
94 |
| |
95 |
20773
| public void removeNodeEntry(NodeEntry entry)
|
96 |
| { |
97 |
20773
| NodeEntry ne = nodeMap.remove(entry.getFqn());
|
98 |
20773
| if (ne != null)
|
99 |
| { |
100 |
| |
101 |
| |
102 |
| |
103 |
| |
104 |
| |
105 |
20773
| this.removalQueue.add(ne);
|
106 |
| |
107 |
| |
108 |
| |
109 |
20773
| this.numElements -= ne.getNumberOfElements();
|
110 |
| } |
111 |
| } |
112 |
| |
113 |
39552
| public void addNodeEntry(NodeEntry entry)
|
114 |
| { |
115 |
39552
| if (!this.containsNodeEntry(entry))
|
116 |
| { |
117 |
39552
| Fqn fqn = entry.getFqn();
|
118 |
39552
| entry.queue = this;
|
119 |
39552
| nodeMap.put(fqn, entry);
|
120 |
39552
| evictionList.add(entry);
|
121 |
39552
| this.numElements += entry.getNumberOfElements();
|
122 |
| } |
123 |
| } |
124 |
| |
125 |
15566
| public int getNumberOfNodes()
|
126 |
| { |
127 |
15566
| return nodeMap.size();
|
128 |
| } |
129 |
| |
130 |
7
| public int getNumberOfElements()
|
131 |
| { |
132 |
7
| return this.numElements;
|
133 |
| } |
134 |
| |
135 |
0
| public void clear()
|
136 |
| { |
137 |
0
| nodeMap.clear();
|
138 |
0
| evictionList.clear();
|
139 |
0
| removalQueue.clear();
|
140 |
0
| this.numElements = 0;
|
141 |
| } |
142 |
| |
143 |
28
| public void resortEvictionQueue()
|
144 |
| { |
145 |
28
| Collections.sort(evictionList, comparator);
|
146 |
| } |
147 |
| |
148 |
3
| public void modifyElementCount(int difference)
|
149 |
| { |
150 |
3
| this.numElements += difference;
|
151 |
| } |
152 |
| |
153 |
43
| void prune()
|
154 |
| { |
155 |
43
| Iterator<NodeEntry> it = this.iterate();
|
156 |
43
| while (it.hasNext() && removalQueue.size() > 0)
|
157 |
| { |
158 |
9014
| if (removalQueue.remove(it.next()))
|
159 |
| { |
160 |
4504
| it.remove();
|
161 |
| } |
162 |
| } |
163 |
| } |
164 |
| |
165 |
| |
166 |
1
| final List<NodeEntry> getEvictionList()
|
167 |
| { |
168 |
1
| return this.evictionList;
|
169 |
| } |
170 |
| |
171 |
| |
172 |
1
| final Set<NodeEntry> getRemovalQueue()
|
173 |
| { |
174 |
1
| return this.removalQueue;
|
175 |
| } |
176 |
| |
177 |
54
| public Iterator<NodeEntry> iterate()
|
178 |
| { |
179 |
54
| return evictionList.iterator();
|
180 |
| } |
181 |
| |
182 |
| |
183 |
| |
184 |
| |
185 |
| |
186 |
| |
187 |
| |
188 |
| |
189 |
| |
190 |
| |
191 |
| |
192 |
| |
193 |
| static class LFUComparator implements Comparator<NodeEntry> |
194 |
| { |
195 |
23
| LFUComparator()
|
196 |
| { |
197 |
| } |
198 |
| |
199 |
212859
| public int compare(NodeEntry ne1, NodeEntry ne2)
|
200 |
| { |
201 |
212859
| if (ne1.equals(ne2))
|
202 |
| { |
203 |
0
| return 0;
|
204 |
| } |
205 |
| |
206 |
212859
| int neNodeHits = ne1.getNumberOfNodeVisits();
|
207 |
212859
| int ne2NodeHits = ne2.getNumberOfNodeVisits();
|
208 |
| |
209 |
212859
| if (neNodeHits > ne2NodeHits)
|
210 |
| { |
211 |
66338
| return 1;
|
212 |
| } |
213 |
146521
| else if (neNodeHits < ne2NodeHits)
|
214 |
| { |
215 |
2192
| return -1;
|
216 |
| } |
217 |
144329
| else if (neNodeHits == ne2NodeHits)
|
218 |
| { |
219 |
144329
| return 0;
|
220 |
| } |
221 |
| |
222 |
0
| throw new RuntimeException("Should never reach this condition");
|
223 |
| } |
224 |
| } |
225 |
| |
226 |
| } |
227 |
| |