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