1 |
| |
2 |
| |
3 |
| |
4 |
| |
5 |
| |
6 |
| |
7 |
| package org.jboss.cache.eviction; |
8 |
| |
9 |
| import junit.framework.TestCase; |
10 |
| |
11 |
| import java.util.ArrayList; |
12 |
| import java.util.Collections; |
13 |
| import java.util.Comparator; |
14 |
| import java.util.HashMap; |
15 |
| import java.util.Iterator; |
16 |
| import java.util.List; |
17 |
| import java.util.Map; |
18 |
| import java.util.Set; |
19 |
| |
20 |
| |
21 |
| |
22 |
| |
23 |
| |
24 |
| |
25 |
| |
26 |
| public class LFUQueueTest extends TestCase |
27 |
| { |
28 |
| private LFUQueue queue; |
29 |
| |
30 |
4
| public void setUp() throws Exception
|
31 |
| { |
32 |
4
| super.setUp();
|
33 |
4
| queue = new LFUQueue();
|
34 |
| } |
35 |
| |
36 |
4
| public void tearDown() throws Exception
|
37 |
| { |
38 |
4
| super.tearDown();
|
39 |
| } |
40 |
| |
41 |
1
| public void testQueue() throws Exception
|
42 |
| { |
43 |
1
| NodeEntry ne;
|
44 |
1
| for (int i = 0; i < 500; i++)
|
45 |
| { |
46 |
500
| ne = new NodeEntry("/a/b/c/" + Integer.toString(i));
|
47 |
500
| queue.addNodeEntry(ne);
|
48 |
| } |
49 |
| |
50 |
1
| queue.resortEvictionQueue();
|
51 |
| |
52 |
1
| assertEquals(500, queue.getNumberOfNodes());
|
53 |
1
| assertTrue(queue.containsNodeEntry(new NodeEntry("/a/b/c/250")));
|
54 |
| |
55 |
1
| NodeEntry ne275 = queue.getNodeEntry("/a/b/c/275");
|
56 |
1
| assertEquals("/a/b/c/275", ne275.getFqn().toString());
|
57 |
| |
58 |
| |
59 |
1
| Iterator it = queue.iterate();
|
60 |
1
| int k = 0;
|
61 |
1
| while (it.hasNext())
|
62 |
| { |
63 |
500
| ne = (NodeEntry) it.next();
|
64 |
500
| assertEquals("/a/b/c/" + Integer.toString(k), ne.getFqn().toString());
|
65 |
500
| if (k % 2 == 0)
|
66 |
| { |
67 |
250
| ne.setNumberOfNodeVisits(ne.getNumberOfNodeVisits() + 1);
|
68 |
| } |
69 |
500
| k++;
|
70 |
| } |
71 |
| |
72 |
1
| queue.resortEvictionQueue();
|
73 |
| |
74 |
1
| assertEquals("/a/b/c/1", queue.getFirstNodeEntry().getFqn().toString());
|
75 |
| |
76 |
| |
77 |
1
| it = queue.iterate();
|
78 |
1
| k = 0;
|
79 |
1
| while (it.hasNext())
|
80 |
| { |
81 |
500
| ne = (NodeEntry) it.next();
|
82 |
500
| if (k < 250)
|
83 |
| { |
84 |
250
| assertEquals(0, ne.getNumberOfNodeVisits());
|
85 |
| } |
86 |
| else |
87 |
| { |
88 |
250
| assertEquals(1, ne.getNumberOfNodeVisits());
|
89 |
| } |
90 |
500
| k++;
|
91 |
| } |
92 |
| |
93 |
1
| k = 0;
|
94 |
?
| while ((ne = queue.getFirstNodeEntry()) != null)
|
95 |
| { |
96 |
251
| if (k == 250)
|
97 |
| { |
98 |
1
| break;
|
99 |
| } |
100 |
250
| queue.removeNodeEntry(ne);
|
101 |
250
| k++;
|
102 |
| } |
103 |
| |
104 |
1
| assertEquals(250, queue.getNumberOfNodes());
|
105 |
| |
106 |
1
| assertFalse(queue.containsNodeEntry(new NodeEntry("/a/b/c/275")));
|
107 |
1
| assertNull(queue.getNodeEntry("/a/b/c/275"));
|
108 |
| |
109 |
1
| for (int i = 0; i < 500; i++)
|
110 |
| { |
111 |
500
| if (i % 2 == 0)
|
112 |
| { |
113 |
250
| ne = queue.getNodeEntry("/a/b/c/" + Integer.toString(i));
|
114 |
250
| assertEquals(1, ne.getNumberOfNodeVisits());
|
115 |
250
| if (i > 250)
|
116 |
| { |
117 |
124
| ne.setNumberOfNodeVisits(ne.getNumberOfNodeVisits() + 1);
|
118 |
| } |
119 |
| } |
120 |
| } |
121 |
| |
122 |
1
| queue.resortEvictionQueue();
|
123 |
1
| assertEquals(250, queue.getNumberOfNodes());
|
124 |
| |
125 |
1
| k = 0;
|
126 |
1
| it = queue.iterate();
|
127 |
1
| while (it.hasNext())
|
128 |
| { |
129 |
250
| ne = (NodeEntry) it.next();
|
130 |
250
| if (k <= 125)
|
131 |
| { |
132 |
126
| assertEquals(1, ne.getNumberOfNodeVisits());
|
133 |
| } |
134 |
| else |
135 |
| { |
136 |
124
| assertEquals(2, ne.getNumberOfNodeVisits());
|
137 |
| } |
138 |
250
| k++;
|
139 |
| } |
140 |
| |
141 |
| } |
142 |
| |
143 |
1
| public void testPrune() throws Exception
|
144 |
| { |
145 |
1
| for (int i = 0; i < 5000; i++)
|
146 |
| { |
147 |
5000
| queue.addNodeEntry(new NodeEntry("/a/b/c/" + Integer.toString(i)));
|
148 |
| } |
149 |
| |
150 |
1
| NodeEntry ne;
|
151 |
1
| Iterator it = queue.iterate();
|
152 |
1
| int i = 0;
|
153 |
1
| while (it.hasNext())
|
154 |
| { |
155 |
5000
| ne = (NodeEntry) it.next();
|
156 |
5000
| if (i % 2 == 0)
|
157 |
| { |
158 |
2500
| queue.removeNodeEntry(ne);
|
159 |
| } |
160 |
5000
| i++;
|
161 |
| } |
162 |
| |
163 |
1
| assertEquals(2500, queue.getNumberOfNodes());
|
164 |
| |
165 |
1
| Set removalQueue = queue.getRemovalQueue();
|
166 |
1
| List evictionList = queue.getEvictionList();
|
167 |
| |
168 |
1
| assertEquals(2500, removalQueue.size());
|
169 |
| |
170 |
1
| it = removalQueue.iterator();
|
171 |
1
| while (it.hasNext())
|
172 |
| { |
173 |
2500
| ne = (NodeEntry) it.next();
|
174 |
2500
| int currentIndex = Integer.parseInt((String) ne.getFqn().get(3));
|
175 |
2500
| assertEquals(0, currentIndex % 2);
|
176 |
| |
177 |
2500
| assertFalse(queue.containsNodeEntry(ne));
|
178 |
2500
| assertNull(queue.getNodeEntry(ne.getFqn()));
|
179 |
2500
| assertTrue(evictionList.contains(ne));
|
180 |
| } |
181 |
| |
182 |
1
| assertEquals(5000, evictionList.size());
|
183 |
| |
184 |
1
| queue.prune();
|
185 |
| |
186 |
1
| assertEquals(0, removalQueue.size());
|
187 |
1
| assertEquals(2500, evictionList.size());
|
188 |
| } |
189 |
| |
190 |
1
| public void testGetFirstNodeEntry() throws Exception
|
191 |
| { |
192 |
1
| for (int i = 0; i < 500; i++)
|
193 |
| { |
194 |
500
| NodeEntry ne = new NodeEntry("/a/b/c/" + Integer.toString(i));
|
195 |
500
| queue.addNodeEntry(ne);
|
196 |
500
| if (i % 2 == 0)
|
197 |
| { |
198 |
250
| ne.setNumberOfNodeVisits(2);
|
199 |
| } |
200 |
| } |
201 |
| |
202 |
1
| queue.resortEvictionQueue();
|
203 |
| |
204 |
1
| NodeEntry ne;
|
205 |
1
| int count = 0;
|
206 |
?
| while ((ne = queue.getFirstNodeEntry()) != null)
|
207 |
| { |
208 |
500
| if (count < 250)
|
209 |
| { |
210 |
250
| assertEquals(0, ne.getNumberOfNodeVisits());
|
211 |
| } |
212 |
| else |
213 |
| { |
214 |
250
| assertEquals(2, ne.getNumberOfNodeVisits());
|
215 |
| } |
216 |
500
| queue.removeNodeEntry(ne);
|
217 |
500
| count++;
|
218 |
| } |
219 |
| |
220 |
1
| assertEquals(0, queue.getNumberOfNodes());
|
221 |
| } |
222 |
| |
223 |
| |
224 |
0
| public void xtestBinarySearch() throws Exception
|
225 |
| { |
226 |
0
| Comparator comp = new LFUQueue.LFUComparator();
|
227 |
0
| ArrayList l = new ArrayList();
|
228 |
0
| Map m = new HashMap();
|
229 |
0
| for (int i = 0; i < 100000; i++)
|
230 |
| { |
231 |
0
| NodeEntry ne = new NodeEntry("/a/b/c/foo_" + Integer.toString(i));
|
232 |
0
| m.put(ne.getFqn(), ne);
|
233 |
0
| l.add(ne);
|
234 |
| } |
235 |
| |
236 |
0
| Collections.sort(l, comp);
|
237 |
| |
238 |
| |
239 |
| |
240 |
0
| assertEquals(m.size(), l.size());
|
241 |
| |
242 |
0
| for (int i = 99999; i >= 0; i--)
|
243 |
| { |
244 |
0
| NodeEntry mapNe = (NodeEntry) m.get("/a/b/c/foo_" + Integer.toString(i));
|
245 |
0
| int searchIndex = Collections.binarySearch(l, mapNe, comp);
|
246 |
0
| assertTrue(searchIndex >= 0);
|
247 |
0
| NodeEntry mapNe2 = (NodeEntry) m.remove("/a/b/c/foo_" + Integer.toString(i));
|
248 |
0
| int searchIndex2 = Collections.binarySearch(l, mapNe2, comp);
|
249 |
0
| assertTrue(searchIndex2 >= 0);
|
250 |
| |
251 |
0
| assertEquals(searchIndex, searchIndex2);
|
252 |
| |
253 |
| |
254 |
0
| for (int k = 0; k < 5; k++)
|
255 |
| { |
256 |
0
| NodeEntry ne = (NodeEntry) l.get(searchIndex);
|
257 |
0
| searchIndex2 = Collections.binarySearch(l, ne, comp);
|
258 |
0
| assertEquals(searchIndex, searchIndex2);
|
259 |
| } |
260 |
| |
261 |
0
| l.remove(searchIndex);
|
262 |
| } |
263 |
| |
264 |
0
| assertEquals(0, m.size());
|
265 |
0
| assertEquals(0, l.size());
|
266 |
| } |
267 |
| |
268 |
1
| public void testNumElements() throws Exception
|
269 |
| { |
270 |
1
| LFUQueue queue = new LFUQueue();
|
271 |
| |
272 |
1
| NodeEntry ne = new NodeEntry("/a/b/c");
|
273 |
1
| ne.setNumberOfElements(50);
|
274 |
1
| queue.addNodeEntry(ne);
|
275 |
| |
276 |
1
| assertEquals(50, queue.getNumberOfElements());
|
277 |
1
| assertEquals(1, queue.getNumberOfNodes());
|
278 |
| |
279 |
1
| queue.removeNodeEntry(ne);
|
280 |
1
| assertEquals(0, queue.getNumberOfElements());
|
281 |
| |
282 |
1
| for (int i = 0; i < 10; i++)
|
283 |
| { |
284 |
10
| ne = new NodeEntry("/a/b/c/" + Integer.toString(i));
|
285 |
10
| ne.setNumberOfElements(i);
|
286 |
10
| queue.addNodeEntry(ne);
|
287 |
| } |
288 |
| |
289 |
1
| assertEquals(45, queue.getNumberOfElements());
|
290 |
1
| assertEquals(10, queue.getNumberOfNodes());
|
291 |
| |
292 |
1
| ne = queue.getNodeEntry("/a/b/c/0");
|
293 |
1
| assertNotNull(ne);
|
294 |
1
| assertEquals(0, ne.getNumberOfElements());
|
295 |
1
| ne.setNumberOfElements(500);
|
296 |
| |
297 |
1
| assertEquals(545, queue.getNumberOfElements());
|
298 |
1
| ne = queue.getNodeEntry("/a/b/c/0");
|
299 |
1
| assertEquals(500, ne.getNumberOfElements());
|
300 |
| |
301 |
1
| queue.resortEvictionQueue();
|
302 |
| |
303 |
1
| ne = queue.getNodeEntry("/a/b/c/1");
|
304 |
1
| assertNotNull(ne);
|
305 |
1
| assertEquals(1, ne.getNumberOfElements());
|
306 |
| |
307 |
1
| queue.resortEvictionQueue();
|
308 |
1
| ne.setNumberOfElements(2);
|
309 |
1
| queue.resortEvictionQueue();
|
310 |
1
| assertEquals(546, queue.getNumberOfElements());
|
311 |
| |
312 |
1
| queue.removeNodeEntry(ne);
|
313 |
| |
314 |
1
| assertEquals(544, queue.getNumberOfElements());
|
315 |
1
| assertEquals(9, queue.getNumberOfNodes());
|
316 |
| |
317 |
1
| queue.removeNodeEntry(queue.getNodeEntry("/a/b/c/0"));
|
318 |
| |
319 |
1
| for (int i = 2; i < 10; i++)
|
320 |
| { |
321 |
8
| ne = queue.getNodeEntry("/a/b/c/" + Integer.toString(i));
|
322 |
8
| assertEquals(i, ne.getNumberOfElements());
|
323 |
8
| queue.removeNodeEntry(ne);
|
324 |
| } |
325 |
| |
326 |
1
| assertEquals(0, queue.getNumberOfNodes());
|
327 |
1
| assertEquals(0, queue.getNumberOfElements());
|
328 |
| |
329 |
| } |
330 |
| |
331 |
| } |