Clover coverage report -
Coverage timestamp: So Nov 6 2005 14:19:51 CET
file stats: LOC: 232   Methods: 7
NCLOC: 107   Classes: 1
 
 Source file Conditionals Statements Methods TOTAL
LRUCache.java 31,2% 55,6% 100% 54,5%
coverage coverage
 1    /*
 2    * Copyright (c) 2002-2003 by OpenSymphony
 3    * All rights reserved.
 4    */
 5    package com.opensymphony.oscache.base.algorithm;
 6   
 7    import com.opensymphony.oscache.util.ClassLoaderUtil;
 8   
 9    import org.apache.commons.collections.SequencedHashMap;
 10    import org.apache.commons.logging.Log;
 11    import org.apache.commons.logging.LogFactory;
 12   
 13    import java.util.*;
 14   
 15    /**
 16    * <p>LRU (Least Recently Used) algorithm for the cache.</p>
 17    *
 18    * <p>This class tries to provide the best possible performance by first
 19    * attempting to use the JDK 1.4.x <code>LinkedHashSet</code> class,
 20    * followed by the Jakarta commons-collections <code>SequencedHashMap</code>
 21    * class, and finally resorting to the <code>LinkedList</code> class if
 22    * neither of the above classes are available. If this class has to revert
 23    * to using a <code>LinkedList</code> a warning is logged since the performance
 24    * penalty can be severe.</p>
 25    *
 26    * <p>No synchronization is required in this class since the
 27    * <code>AbstractConcurrentReadCache</code> already takes care of any
 28    * synchronization requirements.</p>
 29    *
 30    * @version $Revision: 1.1 $
 31    * @author <a href="mailto:salaman@teknos.com">Victor Salaman</a>
 32    * @author <a href="mailto:fbeauregard@pyxis-tech.com">Francois Beauregard</a>
 33    * @author <a href="mailto:abergevin@pyxis-tech.com">Alain Bergevin</a>
 34    * @author <a href="&#109;a&#105;&#108;&#116;&#111;:chris&#64;swebtec.&#99;&#111;&#109;">Chris Miller</a>
 35    */
 36    public class LRUCache extends AbstractConcurrentReadCache {
 37    private static final Log log = LogFactory.getLog(LRUCache.class);
 38   
 39    /**
 40    * Cache queue containing all cache keys.
 41    */
 42    private Collection list;
 43   
 44    /**
 45    * Jakarta commons collections unfortunately doesn't provide us with an ordered
 46    * hash set, so we have to use their ordered map instead.
 47    */
 48    private Map map;
 49   
 50    /**
 51    * A flag indicating if we are using a List for the key collection. This happens
 52    * when we're running under JDK 1.3 or lower and there is no commons-collections
 53    * in the classpath.
 54    */
 55    private boolean isList = false;
 56   
 57    /**
 58    * A flag indicating if we are using a Map for the key collection. This happens
 59    * when we're running under JDK 1.3 and commons-collections is available.
 60    */
 61    private boolean isMap = false;
 62   
 63    /**
 64    * A flag indicating if we are using a Set for the key collection. This happens
 65    * when we're running under JDK 1.4 and is the best case scenario.
 66    */
 67    private boolean isSet = false;
 68   
 69    /**
 70    * A flag indicating whether there is a removal operation in progress.
 71    */
 72    private volatile boolean removeInProgress = false;
 73   
 74    /**
 75    * Constructs an LRU Cache.
 76    */
 77  60 public LRUCache() {
 78  60 super();
 79   
 80    // Decide if we're running under JRE 1.4+. If so we can use a LinkedHashSet
 81    // instead of a LinkedList for a big performance boost when removing elements.
 82  60 try {
 83  60 ClassLoaderUtil.loadClass("java.util.LinkedHashSet", this.getClass());
 84  60 list = new LinkedHashSet();
 85  60 isSet = true;
 86    } catch (ClassNotFoundException e) {
 87    // There's no LinkedHashSet available so we'll try for the jakarta-collections
 88    // SequencedHashMap instead [CACHE-47]
 89  0 try {
 90  0 ClassLoaderUtil.loadClass("org.apache.commons.collections.SequencedHashMap", this.getClass());
 91  0 map = new SequencedHashMap();
 92  0 isMap = true;
 93    } catch (ClassNotFoundException e1) {
 94    // OK, time to get all inefficient and resort to a LinkedList. We log this
 95    // as a warning since it potentially can have a big impact.
 96  0 log.warn("When using the LRUCache under JRE 1.3.x, commons-collections.jar should be added to your classpath to increase OSCache's performance.");
 97  0 list = new LinkedList();
 98  0 isList = true;
 99    }
 100    }
 101    }
 102   
 103    /**
 104    * Constructors a LRU Cache of the specified capacity.
 105    *
 106    * @param capacity The maximum cache capacity.
 107    */
 108  36 public LRUCache(int capacity) {
 109  36 this();
 110  36 maxEntries = capacity;
 111    }
 112   
 113    /**
 114    * An item was retrieved from the list. The LRU implementation moves
 115    * the retrieved item's key to the front of the list.
 116    *
 117    * @param key The cache key of the item that was retrieved.
 118    */
 119  8258 protected void itemRetrieved(Object key) {
 120    // Prevent list operations during remove
 121  8258 while (removeInProgress) {
 122  0 try {
 123  0 Thread.sleep(5);
 124    } catch (InterruptedException ie) {
 125    }
 126    }
 127   
 128    // We need to synchronize here because AbstractConcurrentReadCache
 129    // doesn't prevent multiple threads from calling this method simultaneously.
 130  8258 if (isMap) {
 131  0 synchronized (map) {
 132  0 map.remove(key);
 133  0 map.put(key, Boolean.TRUE);
 134    }
 135    } else {
 136  8258 synchronized (list) {
 137  8258 list.remove(key);
 138  8258 list.add(key);
 139    }
 140    }
 141    }
 142   
 143    /**
 144    * An object was put in the cache. This implementation adds/moves the
 145    * key to the end of the list.
 146    *
 147    * @param key The cache key of the item that was put.
 148    */
 149  12303 protected void itemPut(Object key) {
 150    // Since this entry was just accessed, move it to the back of the list.
 151  12303 if (isMap) {
 152  0 synchronized (map) { // A further fix for CACHE-44
 153  0 map.remove(key);
 154  0 map.put(key, Boolean.TRUE);
 155    }
 156    } else {
 157  12303 synchronized (list) { // A further fix for CACHE-44
 158  12303 list.remove(key);
 159  12303 list.add(key);
 160    }
 161    }
 162    }
 163   
 164    /**
 165    * An item needs to be removed from the cache. The LRU implementation
 166    * removes the first element in the list (ie, the item that was least-recently
 167    * accessed).
 168    *
 169    * @return The key of whichever item was removed.
 170    */
 171  7228 protected Object removeItem() {
 172  7228 removeInProgress = true;
 173   
 174  7228 Object toRemove;
 175   
 176  7228 try {
 177  7228 toRemove = removeFirst();
 178    } catch (Exception e) {
 179    // List is empty.
 180    // this is theorically possible if we have more than the size concurrent
 181    // thread in getItem. Remove completed but add not done yet.
 182    // We simply wait for add to complete.
 183  0 do {
 184  0 try {
 185  0 Thread.sleep(5);
 186    } catch (InterruptedException ie) {
 187    }
 188  0 } while (isMap ? (map.size() == 0) : (list.size() == 0));
 189   
 190  0 toRemove = removeFirst();
 191    }
 192   
 193  7228 removeInProgress = false;
 194   
 195  7228 return toRemove;
 196    }
 197   
 198    /**
 199    * Remove specified key since that object has been removed from the cache.
 200    *
 201    * @param key The cache key of the item that was removed.
 202    */
 203  90 protected void itemRemoved(Object key) {
 204  90 if (isMap) {
 205  0 map.remove(key);
 206    } else {
 207  90 list.remove(key);
 208    }
 209    }
 210   
 211    /**
 212    * Removes the first object from the list of keys.
 213    *
 214    * @return the object that was removed
 215    */
 216  7228 private Object removeFirst() {
 217  7228 Object toRemove;
 218   
 219  7228 if (isSet) {
 220  7228 Iterator it = list.iterator();
 221  7228 toRemove = it.next();
 222  7228 it.remove();
 223  0 } else if (isMap) {
 224  0 toRemove = ((SequencedHashMap) map).getFirstKey();
 225  0 map.remove(toRemove);
 226    } else {
 227  0 toRemove = ((List) list).remove(0);
 228    }
 229   
 230  7228 return toRemove;
 231    }
 232    }