/*
* JBoss, the OpenSource J2EE webOS
*
* Distributable under LGPL license.
* See terms of license at gnu.org.
*/
package org.jboss.cache.eviction;
import org.jboss.cache.Fqn;
import org.jboss.cache.Region;
import org.jboss.cache.RegionManager;
import static org.testng.AssertJUnit.*;
import org.testng.annotations.BeforeMethod;
import org.testng.annotations.Test;
import java.util.Iterator;
/**
* Unit test for LFUAlgorithm.
*
* @author Daniel Huang - dhuang@jboss.org - 10/2005
* @version $Revision: 4836 $
*/
@Test(groups = {"functional"})
public class LFUAlgorithmTest
{
RegionManager regionManager;
LFUAlgorithm algo;
@BeforeMethod(alwaysRun = true)
public void setUp() throws Exception
{
algo = new LFUAlgorithm();
LFUConfiguration config = new LFUConfiguration();
regionManager = new RegionManager();
config.setEvictionPolicyClass(DummyEvictionPolicy.class.getName());
regionManager.getRegion("/a/b", true).setEvictionPolicy(config);
// doesn't this need a cache?!?? :-/
}
public void testMaxNode1()
{
Fqn fqn1 = Fqn.fromString("/a/b/c");
Fqn fqn2 = Fqn.fromString("/a/b/d");
Region region = regionManager.getRegion("/a/b", true);
LFUConfiguration config = new LFUConfiguration();
config.setMaxNodes(0);
config.setMinNodes(20);
region.setEvictionPolicy(config);
region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.ADD_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn2, NodeEventType.ADD_NODE_EVENT));
try
{
algo.process(region);
}
catch (EvictionException e)
{
fail("testMaxNode: process failed " + e);
e.printStackTrace();
}
assertEquals("Queue size should be ", 2, algo.getEvictionQueue().getNumberOfNodes());
}
public void testMaxNode2()
{
Fqn fqn1 = Fqn.fromString("/a/b/c");
Fqn fqn2 = Fqn.fromString("/a/b/d");
Fqn fqn3 = Fqn.fromString("/a/b/e");
Region region = regionManager.getRegion("/a/b", true);
LFUConfiguration config = new LFUConfiguration();
config.setMaxNodes(1);
config.setMinNodes(20);
region.setEvictionPolicy(config);
region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.ADD_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn2, NodeEventType.ADD_NODE_EVENT));
try
{
algo.process(region);
}
catch (EvictionException e)
{
fail("testMaxNode: process failed " + e);
e.printStackTrace();
}
assertEquals("Queue size should be ", 1, algo.getEvictionQueue().getNumberOfNodes());
region.putNodeEvent(new EvictedEventNode(fqn2, NodeEventType.ADD_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn3, NodeEventType.ADD_NODE_EVENT));
try
{
algo.process(region);
}
catch (EvictionException e)
{
fail("testMaxNode: process failed " + e);
e.printStackTrace();
}
assertEquals("Queue size should be ", 1, algo.getEvictionQueue().getNumberOfNodes());
}
// What's this doing here? This should be a stress test, not a functional test. There are no assertions, for
// example. :S - Manik, Nov 06
// public void testMaxNode3() throws Exception
// {
// Region region = regionManager.getRegion("/a/b", true);
// LFUConfiguration config = new LFUConfiguration();
//
// config.setMaxNodes(15000);
// config.setMinNodes(15000);
//
// region.setEvictionPolicy(config);
// for (int i = 0; i < 20000; i++)
// {
// Fqn fqn = Fqn.fromString("/a/b/" + Integer.toString(i));
// region.putNodeEvent(new EvictedEventNode(fqn, NodeEventType.ADD_NODE_EVENT));
//
// if ((i % 2) == 0)
// {
// region.putNodeEvent(new EvictedEventNode(fqn, NodeEventType.VISIT_NODE_EVENT));
// }
// }
//
// algo.process(region);
//// LFUQueue queue = (LFUQueue) algo.evictionQueue;
//// Iterator it = queue.iterate();
//
// }
public void testMinNode1() throws Exception
{
Fqn fqn1 = Fqn.fromString("/a/b/c");
Fqn fqn2 = Fqn.fromString("/a/b/c/d");
Fqn fqn3 = Fqn.fromString("/a/b/c/d/e");
Fqn fqn4 = Fqn.fromString("/a/b/c/d/e/f");
Region region = regionManager.getRegion("/a/b", true);
LFUConfiguration config = (LFUConfiguration) region.getEvictionPolicyConfig();
config.setMaxNodes(0);
config.setMinNodes(2);
region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.ADD_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn2, NodeEventType.ADD_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn3, NodeEventType.ADD_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn4, NodeEventType.ADD_NODE_EVENT));
algo.process(region);
assertEquals("Queue size should be ", 2, algo.getEvictionQueue().getNumberOfNodes());
}
public void testMinNode2() throws Exception
{
Fqn fqn1 = Fqn.fromString("/a/b/c");
Fqn fqn2 = Fqn.fromString("/a/b/d");
Region region = regionManager.getRegion("/a/b", true);
LFUConfiguration config = (LFUConfiguration) region.getEvictionPolicyConfig();
config.setMaxNodes(0);
config.setMinNodes(0);
region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.ADD_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn2, NodeEventType.ADD_NODE_EVENT));
algo.process(region);
assertEquals("Queue size should be ", 0, algo.getEvictionQueue().getNumberOfNodes());
}
public void testEvictionQueueSortOrder1() throws Exception
{
Fqn fqn1 = Fqn.fromString("/a/b/c");
Fqn fqn2 = Fqn.fromString("/a/b/c/d");
Fqn fqn3 = Fqn.fromString("/a/b/c/d/e");
Fqn fqn4 = Fqn.fromString("/a/b/c/d/e/f");
Fqn fqn5 = Fqn.fromString("/a/b/c/d/e/f/g/h");
Fqn fqn6 = Fqn.fromString("/a/b/c/d/e/f/g/h/i");
Fqn fqn7 = Fqn.fromString("/a/b/c/d/e/f/g/h/i/j");
Fqn fqn8 = Fqn.fromString("/a/b/c/d/e/f/g/h/i/j/k");
Fqn fqn9 = Fqn.fromString("/a/b/c/d/e/f/g/h/i/j/k/l");
Fqn fqn10 = Fqn.fromString("/a/b/c/d/e/f/g/h/i/j/k/l/m");
Region region = regionManager.getRegion("/a/b", true);
LFUConfiguration config = (LFUConfiguration) region.getEvictionPolicyConfig();
config.setMaxNodes(0);
config.setMinNodes(100);
region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.ADD_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn2, NodeEventType.ADD_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn3, NodeEventType.ADD_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn4, NodeEventType.ADD_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn5, NodeEventType.ADD_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn6, NodeEventType.ADD_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn7, NodeEventType.ADD_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn8, NodeEventType.ADD_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn9, NodeEventType.ADD_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn10, NodeEventType.ADD_NODE_EVENT));
algo.process(region);
LFUQueue queue = (LFUQueue) algo.evictionQueue;
assertEquals(10, algo.getEvictionQueue().getNumberOfNodes());
Iterator it = queue.iterate();
while (it.hasNext())
{
NodeEntry ne = (NodeEntry) it.next();
System.out.println("Fqn: " + ne.getFqn() + " NodeVisits: " + ne.getNumberOfNodeVisits());
assertEquals(1, ne.getNumberOfNodeVisits());
}
// fqn1 visited 4 additional times.
region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.VISIT_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.VISIT_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.VISIT_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.VISIT_NODE_EVENT));
// fqn2 visited 3 additional times.
region.putNodeEvent(new EvictedEventNode(fqn2, NodeEventType.VISIT_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn2, NodeEventType.VISIT_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn2, NodeEventType.VISIT_NODE_EVENT));
// fqn3 visited 1 additional time.
region.putNodeEvent(new EvictedEventNode(fqn3, NodeEventType.VISIT_NODE_EVENT));
// fqn4 visited 2 additional times.
region.putNodeEvent(new EvictedEventNode(fqn4, NodeEventType.VISIT_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn4, NodeEventType.VISIT_NODE_EVENT));
// fqn9 visited 1 additional time.
region.putNodeEvent(new EvictedEventNode(fqn9, NodeEventType.VISIT_NODE_EVENT));
// fqn10 visited 2 additional times.
region.putNodeEvent(new EvictedEventNode(fqn10, NodeEventType.VISIT_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn10, NodeEventType.VISIT_NODE_EVENT));
algo.process(region);
System.out.println();
System.out.println();
it = queue.iterate();
int count = 0;
while (it.hasNext())
{
count++;
NodeEntry ne = (NodeEntry) it.next();
System.out.println("Fqn: " + ne.getFqn() + " NodeVisits: " + ne.getNumberOfNodeVisits());
if (count == 5 || count == 6)
{
assertEquals(2, ne.getNumberOfNodeVisits());
}
else if (count == 7 || count == 8)
{
assertEquals(3, ne.getNumberOfNodeVisits());
}
else if (count == 9)
{
assertEquals(4, ne.getNumberOfNodeVisits());
}
else if (count == 10)
{
assertEquals(5, ne.getNumberOfNodeVisits());
}
else
{
assertEquals(1, ne.getNumberOfNodeVisits());
}
}
assertEquals(10, algo.getEvictionQueue().getNumberOfNodes());
Fqn fqn11 = Fqn.fromString("/a");
Fqn fqn12 = Fqn.fromString("/a/b");
region.putNodeEvent(new EvictedEventNode(fqn11, NodeEventType.ADD_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn12, NodeEventType.ADD_NODE_EVENT));
algo.process(region);
System.out.println();
System.out.println();
it = queue.iterate();
count = 0;
while (it.hasNext())
{
count++;
NodeEntry ne = (NodeEntry) it.next();
System.out.println("Fqn: " + ne.getFqn() + " NodeVisits: " + ne.getNumberOfNodeVisits());
if (count == 7 || count == 8)
{
assertEquals(2, ne.getNumberOfNodeVisits());
}
else if (count == 9 || count == 10)
{
assertEquals(3, ne.getNumberOfNodeVisits());
}
else if (count == 11)
{
assertEquals(4, ne.getNumberOfNodeVisits());
}
else if (count == 12)
{
assertEquals(5, ne.getNumberOfNodeVisits());
}
else
{
assertEquals(1, ne.getNumberOfNodeVisits());
}
}
assertEquals(12, algo.getEvictionQueue().getNumberOfNodes());
region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.REMOVE_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn11, NodeEventType.REMOVE_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn12, NodeEventType.REMOVE_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn10, NodeEventType.REMOVE_NODE_EVENT));
algo.process(region);
System.out.println();
System.out.println();
it = queue.iterate();
count = 0;
while (it.hasNext())
{
count++;
NodeEntry ne = (NodeEntry) it.next();
System.out.println("Fqn: " + ne.getFqn() + " NodeVisits: " + ne.getNumberOfNodeVisits());
if (count == 5 || count == 6)
{
assertEquals(2, ne.getNumberOfNodeVisits());
}
else if (count == 7)
{
assertEquals(3, ne.getNumberOfNodeVisits());
}
else if (count == 8)
{
assertEquals(4, ne.getNumberOfNodeVisits());
}
else
{
assertEquals(1, ne.getNumberOfNodeVisits());
}
}
assertEquals(8, algo.getEvictionQueue().getNumberOfNodes());
//test add/visit/remove combination
region.putNodeEvent(new EvictedEventNode(fqn11, NodeEventType.ADD_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn11, NodeEventType.VISIT_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn11, NodeEventType.VISIT_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn11, NodeEventType.VISIT_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn11, NodeEventType.VISIT_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn11, NodeEventType.VISIT_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn4, NodeEventType.VISIT_NODE_EVENT));
// purposefully revisit a node that has been removed. assert that it is readded.
region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.VISIT_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn1, NodeEventType.VISIT_NODE_EVENT));
region.putNodeEvent(new EvictedEventNode(fqn3, NodeEventType.REMOVE_NODE_EVENT));
algo.process(region);
System.out.println();
System.out.println();
it = queue.iterate();
count = 0;
while (it.hasNext())
{
count++;
NodeEntry ne = (NodeEntry) it.next();
System.out.println("Fqn: " + ne.getFqn() + " NodeVisits: " + ne.getNumberOfNodeVisits());
if (count == 5 || count == 6)
{
assertEquals(2, ne.getNumberOfNodeVisits());
}
else if (count == 7 || count == 8)
{
assertEquals(4, ne.getNumberOfNodeVisits());
}
else if (count == 9)
{
assertEquals(6, ne.getNumberOfNodeVisits());
}
else
{
assertEquals(1, ne.getNumberOfNodeVisits());
}
}
assertEquals(9, algo.getEvictionQueue().getNumberOfNodes());
}
public void testEvictionQueueSortOrder2() throws Exception
{
Region region = regionManager.getRegion("/a/b", true);
LFUConfiguration config = (LFUConfiguration) region.getEvictionPolicyConfig();
config.setMaxNodes(0);
config.setMinNodes(10000);
for (int i = 0; i < 10000; i++)
{
Fqn fqn = Fqn.fromString("/a/b/" + Integer.toString(i));
region.putNodeEvent(new EvictedEventNode(fqn, NodeEventType.ADD_NODE_EVENT));
}
algo.process(region);
LFUQueue queue = (LFUQueue) algo.evictionQueue;
Iterator it = queue.iterate();
long lastModifiedTimestamp = 0;
while (it.hasNext())
{
NodeEntry ne = (NodeEntry) it.next();
assertTrue(lastModifiedTimestamp <= ne.getModifiedTimeStamp());
lastModifiedTimestamp = ne.getModifiedTimeStamp();
}
for (int i = 0; i < 10000; i++)
{
if ((i % 2) == 0)
{
Fqn fqn = Fqn.fromString("/a/b/" + Integer.toString(i));
region.putNodeEvent(new EvictedEventNode(fqn, NodeEventType.VISIT_NODE_EVENT));
}
}
algo.process(region);
it = queue.iterate();
int count = 0;
lastModifiedTimestamp = 0;
while (it.hasNext())
{
NodeEntry ne = (NodeEntry) it.next();
assertTrue(lastModifiedTimestamp <= ne.getModifiedTimeStamp());
lastModifiedTimestamp = ne.getModifiedTimeStamp();
if (count < 5000)
{
assertEquals(1, ne.getNumberOfNodeVisits());
}
else
{
assertEquals(2, ne.getNumberOfNodeVisits());
}
count++;
}
assertEquals(10000, algo.getEvictionQueue().getNumberOfNodes());
}
}