Clover coverage report -
Coverage timestamp: Thu Jul 5 2007 20:02:32 EDT
file stats: LOC: 227   Methods: 18
NCLOC: 158   Classes: 2
 
 Source file Conditionals Statements Methods TOTAL
LFUQueue.java 70% 88.7% 94.4% 85.7%
coverage coverage
 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 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    * LFUQueue EvictionQueue implementation for LFU Policy.
 24    * <p/>
 25    * The queue is sorted in least frequently used order.
 26    *
 27    * @author Daniel Huang (dhuang@jboss.org)
 28    * @version $Revision: 1.6 $
 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    * Return the first node to evict.
 49    * <p/>
 50    * This method will return the least frequently used entry in the queue.
 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    // don't remove directly from the LinkedList otherwise we will incur a O(n) = n
 101    // performance penalty for every removal! In the prune method for LFU, we will iterate the LinkedList through ONCE
 102    // doing a single O(n) = n operation and removal. This is much preferred over running O(n) = n every single time
 103    // remove is called. There is also special logic in the getFirstNodeEntry that will know to check
 104    // the removalQueue before returning.
 105  20773 this.removalQueue.add(ne);
 106    /* if(!evictionList.remove(ne)) {
 107    throw new RuntimeException("");
 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    // provided as friend access for unit testing only.
 166  1 final List<NodeEntry> getEvictionList()
 167    {
 168  1 return this.evictionList;
 169    }
 170   
 171    // provided as friend access for unit testing only.
 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    * Comparator class for LFU.
 184    * <p/>
 185    * This class will sort the eviction queue in the correct eviction order.
 186    * The top of the list should evict before the bottom of the list.
 187    * <p/>
 188    * The sort is based on ascending order of nodeVisits.
 189    * <p/>
 190    * Note: this class has a natural ordering that is inconsistent with equals as defined by the java.lang.Comparator
 191    * contract.
 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