KickJava   Java API By Example, From Geeks To Geeks.

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


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 junit.framework.Test;
10 import junit.framework.TestCase;
11 import junit.framework.TestSuite;
12 import org.jboss.cache.CacheImpl;
13 import org.jboss.cache.Fqn;
14 import org.jboss.cache.Region;
15 import org.jboss.cache.RegionManager;
16
17 import java.util.Iterator JavaDoc;
18
19 /**
20  * Unit test for LFUAlgorithm.
21  *
22  * @author Daniel Huang - dhuang@jboss.org - 10/2005
23  * @version $Revision: 1.7 $
24  */
25 public class LFUAlgorithmTest extends TestCase
26 {
27
28    RegionManager regionManager;
29    LFUAlgorithm algo;
30
31    public LFUAlgorithmTest(String JavaDoc s)
32    {
33       super(s);
34    }
35
36    public void setUp() throws Exception JavaDoc
37    {
38       super.setUp();
39
40       algo = new LFUAlgorithm();
41       LFUConfiguration config = new LFUConfiguration();
42       regionManager = new RegionManager(new CacheImpl());
43       config.setEvictionPolicyClass(DummyEvictionPolicy.class.getName());
44       regionManager.getRegion("/a/b", true).setEvictionPolicy(config);
45       // doesn't this need a cache?!?? :-/
46
47    }
48
49    public void tearDown() throws Exception JavaDoc
50    {
51       super.tearDown();
52    }
53
54    public void testMaxNode1()
55    {
56       Fqn fqn1 = Fqn.fromString("/a/b/c");
57       Fqn fqn2 = Fqn.fromString("/a/b/d");
58       Region region = regionManager.getRegion("/a/b", true);
59       LFUConfiguration config = new LFUConfiguration();
60       config.setMaxNodes(0);
61       config.setMinNodes(20);
62       region.setEvictionPolicy(config);
63       region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.ADD_NODE_EVENT));
64       region.putNodeEvent(new EvictedEventNode(fqn2, NodeEventType.ADD_NODE_EVENT));
65       try
66       {
67          algo.process(region);
68       }
69       catch (EvictionException e)
70       {
71          fail("testMaxNode: process failed " + e);
72          e.printStackTrace();
73       }
74       assertEquals("Queue size should be ", 2, algo.getEvictionQueue().getNumberOfNodes());
75
76    }
77
78    public void testMaxNode2()
79    {
80       Fqn fqn1 = Fqn.fromString("/a/b/c");
81       Fqn fqn2 = Fqn.fromString("/a/b/d");
82       Fqn fqn3 = Fqn.fromString("/a/b/e");
83       Region region = regionManager.getRegion("/a/b", true);
84       LFUConfiguration config = new LFUConfiguration();
85       config.setMaxNodes(1);
86       config.setMinNodes(20);
87       region.setEvictionPolicy(config);
88       region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.ADD_NODE_EVENT));
89       region.putNodeEvent(new EvictedEventNode(fqn2, NodeEventType.ADD_NODE_EVENT));
90
91       try
92       {
93          algo.process(region);
94       }
95       catch (EvictionException e)
96       {
97          fail("testMaxNode: process failed " + e);
98          e.printStackTrace();
99       }
100       assertEquals("Queue size should be ", 1, algo.getEvictionQueue().getNumberOfNodes());
101
102       region.putNodeEvent(new EvictedEventNode(fqn2, NodeEventType.ADD_NODE_EVENT));
103       region.putNodeEvent(new EvictedEventNode(fqn3, NodeEventType.ADD_NODE_EVENT));
104
105
106       try
107       {
108          algo.process(region);
109       }
110       catch (EvictionException e)
111       {
112          fail("testMaxNode: process failed " + e);
113          e.printStackTrace();
114       }
115       assertEquals("Queue size should be ", 1, algo.getEvictionQueue().getNumberOfNodes());
116    }
117
118    // What's this doing here? This should be a stress test, not a functional test. There are no assertions, for
119 // example. :S - Manik, Nov 06
120
121 // public void testMaxNode3() throws Exception
122 // {
123 // Region region = regionManager.getRegion("/a/b", true);
124 // LFUConfiguration config = new LFUConfiguration();
125 //
126 // config.setMaxNodes(15000);
127 // config.setMinNodes(15000);
128 //
129 // region.setEvictionPolicy(config);
130 // for (int i = 0; i < 20000; i++)
131 // {
132 // Fqn fqn = Fqn.fromString("/a/b/" + Integer.toString(i));
133 // region.putNodeEvent(new EvictedEventNode(fqn, NodeEventType.ADD_NODE_EVENT));
134 //
135 // if ((i % 2) == 0)
136 // {
137 // region.putNodeEvent(new EvictedEventNode(fqn, NodeEventType.VISIT_NODE_EVENT));
138 // }
139 // }
140 //
141 // algo.process(region);
142 //// LFUQueue queue = (LFUQueue) algo.evictionQueue;
143 //// Iterator it = queue.iterate();
144 //
145 // }
146
147    public void testMinNode1() throws Exception JavaDoc
148    {
149       Fqn fqn1 = Fqn.fromString("/a/b/c");
150       Fqn fqn2 = Fqn.fromString("/a/b/c/d");
151       Fqn fqn3 = Fqn.fromString("/a/b/c/d/e");
152       Fqn fqn4 = Fqn.fromString("/a/b/c/d/e/f");
153
154       Region region = regionManager.getRegion("/a/b", true);
155       LFUConfiguration config = (LFUConfiguration) region.getEvictionPolicyConfig();
156
157       config.setMaxNodes(0);
158       config.setMinNodes(2);
159
160       region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.ADD_NODE_EVENT));
161       region.putNodeEvent(new EvictedEventNode(fqn2, NodeEventType.ADD_NODE_EVENT));
162       region.putNodeEvent(new EvictedEventNode(fqn3, NodeEventType.ADD_NODE_EVENT));
163       region.putNodeEvent(new EvictedEventNode(fqn4, NodeEventType.ADD_NODE_EVENT));
164
165       algo.process(region);
166
167       assertEquals("Queue size should be ", 2, algo.getEvictionQueue().getNumberOfNodes());
168    }
169
170    public void testMinNode2() throws Exception JavaDoc
171    {
172       Fqn fqn1 = Fqn.fromString("/a/b/c");
173       Fqn fqn2 = Fqn.fromString("/a/b/d");
174
175       Region region = regionManager.getRegion("/a/b", true);
176       LFUConfiguration config = (LFUConfiguration) region.getEvictionPolicyConfig();
177
178       config.setMaxNodes(0);
179       config.setMinNodes(0);
180
181       region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.ADD_NODE_EVENT));
182       region.putNodeEvent(new EvictedEventNode(fqn2, NodeEventType.ADD_NODE_EVENT));
183
184       algo.process(region);
185
186       assertEquals("Queue size should be ", 0, algo.getEvictionQueue().getNumberOfNodes());
187    }
188
189    public void testEvictionQueueSortOrder1() throws Exception JavaDoc
190    {
191       Fqn fqn1 = Fqn.fromString("/a/b/c");
192       Fqn fqn2 = Fqn.fromString("/a/b/c/d");
193       Fqn fqn3 = Fqn.fromString("/a/b/c/d/e");
194       Fqn fqn4 = Fqn.fromString("/a/b/c/d/e/f");
195       Fqn fqn5 = Fqn.fromString("/a/b/c/d/e/f/g/h");
196       Fqn fqn6 = Fqn.fromString("/a/b/c/d/e/f/g/h/i");
197       Fqn fqn7 = Fqn.fromString("/a/b/c/d/e/f/g/h/i/j");
198       Fqn fqn8 = Fqn.fromString("/a/b/c/d/e/f/g/h/i/j/k");
199       Fqn fqn9 = Fqn.fromString("/a/b/c/d/e/f/g/h/i/j/k/l");
200       Fqn fqn10 = Fqn.fromString("/a/b/c/d/e/f/g/h/i/j/k/l/m");
201
202
203       Region region = regionManager.getRegion("/a/b", true);
204       LFUConfiguration config = (LFUConfiguration) region.getEvictionPolicyConfig();
205       config.setMaxNodes(0);
206       config.setMinNodes(100);
207
208       region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.ADD_NODE_EVENT));
209       region.putNodeEvent(new EvictedEventNode(fqn2, NodeEventType.ADD_NODE_EVENT));
210       region.putNodeEvent(new EvictedEventNode(fqn3, NodeEventType.ADD_NODE_EVENT));
211       region.putNodeEvent(new EvictedEventNode(fqn4, NodeEventType.ADD_NODE_EVENT));
212       region.putNodeEvent(new EvictedEventNode(fqn5, NodeEventType.ADD_NODE_EVENT));
213       region.putNodeEvent(new EvictedEventNode(fqn6, NodeEventType.ADD_NODE_EVENT));
214       region.putNodeEvent(new EvictedEventNode(fqn7, NodeEventType.ADD_NODE_EVENT));
215       region.putNodeEvent(new EvictedEventNode(fqn8, NodeEventType.ADD_NODE_EVENT));
216       region.putNodeEvent(new EvictedEventNode(fqn9, NodeEventType.ADD_NODE_EVENT));
217       region.putNodeEvent(new EvictedEventNode(fqn10, NodeEventType.ADD_NODE_EVENT));
218
219       algo.process(region);
220       LFUQueue queue = (LFUQueue) algo.evictionQueue;
221       assertEquals(10, algo.getEvictionQueue().getNumberOfNodes());
222       Iterator JavaDoc it = queue.iterate();
223
224       while (it.hasNext())
225       {
226          NodeEntry ne = (NodeEntry) it.next();
227          System.out.println("Fqn: " + ne.getFqn() + " NodeVisits: " + ne.getNumberOfNodeVisits());
228          assertEquals(1, ne.getNumberOfNodeVisits());
229       }
230
231       // fqn1 visited 4 additional times.
232 region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.VISIT_NODE_EVENT));
233       region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.VISIT_NODE_EVENT));
234       region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.VISIT_NODE_EVENT));
235       region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.VISIT_NODE_EVENT));
236
237       // fqn2 visited 3 additional times.
238 region.putNodeEvent(new EvictedEventNode(fqn2, NodeEventType.VISIT_NODE_EVENT));
239       region.putNodeEvent(new EvictedEventNode(fqn2, NodeEventType.VISIT_NODE_EVENT));
240       region.putNodeEvent(new EvictedEventNode(fqn2, NodeEventType.VISIT_NODE_EVENT));
241
242       // fqn3 visited 1 additional time.
243 region.putNodeEvent(new EvictedEventNode(fqn3, NodeEventType.VISIT_NODE_EVENT));
244
245       // fqn4 visited 2 additional times.
246 region.putNodeEvent(new EvictedEventNode(fqn4, NodeEventType.VISIT_NODE_EVENT));
247       region.putNodeEvent(new EvictedEventNode(fqn4, NodeEventType.VISIT_NODE_EVENT));
248
249       // fqn9 visited 1 additional time.
250 region.putNodeEvent(new EvictedEventNode(fqn9, NodeEventType.VISIT_NODE_EVENT));
251
252       // fqn10 visited 2 additional times.
253 region.putNodeEvent(new EvictedEventNode(fqn10, NodeEventType.VISIT_NODE_EVENT));
254       region.putNodeEvent(new EvictedEventNode(fqn10, NodeEventType.VISIT_NODE_EVENT));
255
256       algo.process(region);
257       System.out.println();
258       System.out.println();
259
260       it = queue.iterate();
261       int count = 0;
262       while (it.hasNext())
263       {
264          count++;
265          NodeEntry ne = (NodeEntry) it.next();
266          System.out.println("Fqn: " + ne.getFqn() + " NodeVisits: " + ne.getNumberOfNodeVisits());
267          if (count == 5 || count == 6)
268          {
269             assertEquals(2, ne.getNumberOfNodeVisits());
270          }
271          else if (count == 7 || count == 8)
272          {
273             assertEquals(3, ne.getNumberOfNodeVisits());
274          }
275          else if (count == 9)
276          {
277             assertEquals(4, ne.getNumberOfNodeVisits());
278          }
279          else if (count == 10)
280          {
281             assertEquals(5, ne.getNumberOfNodeVisits());
282          }
283          else
284          {
285             assertEquals(1, ne.getNumberOfNodeVisits());
286          }
287       }
288
289
290       assertEquals(10, algo.getEvictionQueue().getNumberOfNodes());
291
292       Fqn fqn11 = Fqn.fromString("/a");
293       Fqn fqn12 = Fqn.fromString("/a/b");
294
295       region.putNodeEvent(new EvictedEventNode(fqn11, NodeEventType.ADD_NODE_EVENT));
296       region.putNodeEvent(new EvictedEventNode(fqn12, NodeEventType.ADD_NODE_EVENT));
297
298       algo.process(region);
299       System.out.println();
300       System.out.println();
301
302       it = queue.iterate();
303       count = 0;
304       while (it.hasNext())
305       {
306          count++;
307          NodeEntry ne = (NodeEntry) it.next();
308          System.out.println("Fqn: " + ne.getFqn() + " NodeVisits: " + ne.getNumberOfNodeVisits());
309          if (count == 7 || count == 8)
310          {
311             assertEquals(2, ne.getNumberOfNodeVisits());
312          }
313          else if (count == 9 || count == 10)
314          {
315             assertEquals(3, ne.getNumberOfNodeVisits());
316          }
317          else if (count == 11)
318          {
319             assertEquals(4, ne.getNumberOfNodeVisits());
320          }
321          else if (count == 12)
322          {
323             assertEquals(5, ne.getNumberOfNodeVisits());
324          }
325          else
326          {
327             assertEquals(1, ne.getNumberOfNodeVisits());
328          }
329       }
330
331       assertEquals(12, algo.getEvictionQueue().getNumberOfNodes());
332
333       region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.REMOVE_NODE_EVENT));
334       region.putNodeEvent(new EvictedEventNode(fqn11, NodeEventType.REMOVE_NODE_EVENT));
335       region.putNodeEvent(new EvictedEventNode(fqn12, NodeEventType.REMOVE_NODE_EVENT));
336       region.putNodeEvent(new EvictedEventNode(fqn10, NodeEventType.REMOVE_NODE_EVENT));
337
338       algo.process(region);
339
340       System.out.println();
341       System.out.println();
342       it = queue.iterate();
343       count = 0;
344       while (it.hasNext())
345       {
346          count++;
347          NodeEntry ne = (NodeEntry) it.next();
348          System.out.println("Fqn: " + ne.getFqn() + " NodeVisits: " + ne.getNumberOfNodeVisits());
349          if (count == 5 || count == 6)
350          {
351             assertEquals(2, ne.getNumberOfNodeVisits());
352          }
353          else if (count == 7)
354          {
355             assertEquals(3, ne.getNumberOfNodeVisits());
356          }
357          else if (count == 8)
358          {
359             assertEquals(4, ne.getNumberOfNodeVisits());
360          }
361          else
362          {
363             assertEquals(1, ne.getNumberOfNodeVisits());
364          }
365       }
366
367       assertEquals(8, algo.getEvictionQueue().getNumberOfNodes());
368
369       //test add/visit/remove combination
370 region.putNodeEvent(new EvictedEventNode(fqn11, NodeEventType.ADD_NODE_EVENT));
371       region.putNodeEvent(new EvictedEventNode(fqn11, NodeEventType.VISIT_NODE_EVENT));
372       region.putNodeEvent(new EvictedEventNode(fqn11, NodeEventType.VISIT_NODE_EVENT));
373       region.putNodeEvent(new EvictedEventNode(fqn11, NodeEventType.VISIT_NODE_EVENT));
374       region.putNodeEvent(new EvictedEventNode(fqn11, NodeEventType.VISIT_NODE_EVENT));
375       region.putNodeEvent(new EvictedEventNode(fqn11, NodeEventType.VISIT_NODE_EVENT));
376       region.putNodeEvent(new EvictedEventNode(fqn4, NodeEventType.VISIT_NODE_EVENT));
377
378       // purposefully revisit a node that has been removed. assert that it is readded.
379 region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.VISIT_NODE_EVENT));
380       region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.VISIT_NODE_EVENT));
381
382       region.putNodeEvent(new EvictedEventNode(fqn3, NodeEventType.REMOVE_NODE_EVENT));
383
384
385       algo.process(region);
386
387       System.out.println();
388       System.out.println();
389       it = queue.iterate();
390       count = 0;
391       while (it.hasNext())
392       {
393          count++;
394          NodeEntry ne = (NodeEntry) it.next();
395          System.out.println("Fqn: " + ne.getFqn() + " NodeVisits: " + ne.getNumberOfNodeVisits());
396          if (count == 5 || count == 6)
397          {
398             assertEquals(2, ne.getNumberOfNodeVisits());
399          }
400          else if (count == 7 || count == 8)
401          {
402             assertEquals(4, ne.getNumberOfNodeVisits());
403          }
404          else if (count == 9)
405          {
406             assertEquals(6, ne.getNumberOfNodeVisits());
407          }
408          else
409          {
410             assertEquals(1, ne.getNumberOfNodeVisits());
411          }
412       }
413       assertEquals(9, algo.getEvictionQueue().getNumberOfNodes());
414    }
415
416    public void testEvictionQueueSortOrder2() throws Exception JavaDoc
417    {
418       Region region = regionManager.getRegion("/a/b", true);
419       LFUConfiguration config = (LFUConfiguration) region.getEvictionPolicyConfig();
420
421       config.setMaxNodes(0);
422       config.setMinNodes(10000);
423       for (int i = 0; i < 10000; i++)
424       {
425          Fqn fqn = Fqn.fromString("/a/b/" + Integer.toString(i));
426          region.putNodeEvent(new EvictedEventNode(fqn, NodeEventType.ADD_NODE_EVENT));
427       }
428
429       algo.process(region);
430       LFUQueue queue = (LFUQueue) algo.evictionQueue;
431       Iterator JavaDoc it = queue.iterate();
432
433       long lastModifiedTimestamp = 0;
434       while (it.hasNext())
435       {
436          NodeEntry ne = (NodeEntry) it.next();
437          assertTrue(lastModifiedTimestamp <= ne.getModifiedTimeStamp());
438          lastModifiedTimestamp = ne.getModifiedTimeStamp();
439       }
440
441       for (int i = 0; i < 10000; i++)
442       {
443          if ((i % 2) == 0)
444          {
445             Fqn fqn = Fqn.fromString("/a/b/" + Integer.toString(i));
446             region.putNodeEvent(new EvictedEventNode(fqn, NodeEventType.VISIT_NODE_EVENT));
447          }
448       }
449
450       algo.process(region);
451
452       it = queue.iterate();
453       int count = 0;
454       lastModifiedTimestamp = 0;
455       while (it.hasNext())
456       {
457          NodeEntry ne = (NodeEntry) it.next();
458          assertTrue(lastModifiedTimestamp <= ne.getModifiedTimeStamp());
459          lastModifiedTimestamp = ne.getModifiedTimeStamp();
460
461          if (count < 5000)
462          {
463             assertEquals(1, ne.getNumberOfNodeVisits());
464          }
465          else
466          {
467             assertEquals(2, ne.getNumberOfNodeVisits());
468          }
469          count++;
470
471       }
472
473       assertEquals(10000, algo.getEvictionQueue().getNumberOfNodes());
474    }
475
476    public static Test suite()
477    {
478       return new TestSuite(LFUAlgorithmTest.class);
479    }
480
481    public static void main(String JavaDoc[] args)
482    {
483       junit.textui.TestRunner.run(suite());
484    }
485
486 }
487
Popular Tags