Clover coverage report -
Coverage timestamp: Sat Feb 28 2004 21:40:56 EST
file stats: LOC: 231   Methods: 7
NCLOC: 103   Classes: 1
 
 Source file Conditionals Statements Methods TOTAL
LRUCache.java 31.2% 55.8% 100% 54.7%
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.2 $
 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 transient 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  34
     public LRUCache() {
 78  34
         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  34
         try {
 83  34
             ClassLoaderUtil.loadClass("java.util.LinkedHashSet", this.getClass());
 84  34
             list = new LinkedHashSet();
 85  34
             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  28
     public LRUCache(int capacity) {
 109  28
         this();
 110  28
         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  6371
     protected void itemRetrieved(Object key) {
 120   
         // Prevent list operations during remove
 121  6371
         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  6371
         if (isMap) {
 131  0
             synchronized (map) {
 132  0
                 map.remove(key);
 133  0
                 map.put(key, Boolean.TRUE);
 134   
             }
 135   
         } else {
 136  6371
             synchronized (list) {
 137  6371
                 list.remove(key);
 138  6371
                 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  3406
     protected void itemPut(Object key) {
 150   
         // Since this entry was just accessed, move it to the back of the list.
 151   
         // No need to sync here because AbstractConcurrentReadCache only allows
 152   
         // one put to occur at a time.
 153  3406
         if (isMap) {
 154  0
             map.remove(key);
 155  0
             map.put(key, Boolean.TRUE);
 156   
         } else {
 157  3406
             list.remove(key);
 158  3406
             list.add(key);
 159   
         }
 160   
     }
 161   
 
 162   
     /**
 163   
      * An item needs to be removed from the cache. The LRU implementation
 164   
      * removes the first element in the list (ie, the item that was least-recently
 165   
      * accessed).
 166   
      *
 167   
      * @return The key of whichever item was removed.
 168   
      */
 169  15
     protected Object removeItem() {
 170  15
         removeInProgress = true;
 171   
 
 172  15
         Object toRemove;
 173   
 
 174  15
         try {
 175  15
             toRemove = removeFirst();
 176   
         } catch (Exception e) {
 177   
             // List is empty.
 178   
             // this is theorically possible if we have more than the size concurrent
 179   
             // thread in getItem. Remove completed but add not done yet.
 180   
             // We simply wait for add to complete.
 181  0
             do {
 182  0
                 try {
 183  0
                     Thread.sleep(5);
 184   
                 } catch (InterruptedException ie) {
 185   
                 }
 186  0
             } while (isMap ? (map.size() == 0) : (list.size() == 0));
 187   
 
 188  0
             toRemove = removeFirst();
 189   
         }
 190   
 
 191  15
         removeInProgress = false;
 192   
 
 193  15
         return toRemove;
 194   
     }
 195   
 
 196   
     /**
 197   
      * Remove specified key since that object has been removed from the cache.
 198   
      *
 199   
      * @param key The cache key of the item that was removed.
 200   
      */
 201  51
     protected void itemRemoved(Object key) {
 202  51
         if (isMap) {
 203  0
             map.remove(key);
 204   
         } else {
 205  51
             list.remove(key);
 206   
         }
 207   
     }
 208   
 
 209   
     /**
 210   
      * Removes the first object from the list of keys.
 211   
      *
 212   
      * @return the object that was removed
 213   
      */
 214  15
     private Object removeFirst() {
 215  15
         Object toRemove;
 216   
 
 217  15
         if (isSet) {
 218  15
             Iterator it = list.iterator();
 219  15
             toRemove = it.next();
 220  15
             it.remove();
 221  0
         } else if (isMap) {
 222  0
             toRemove = ((SequencedHashMap) map).getFirstKey();
 223  0
             map.remove(toRemove);
 224   
         } else {
 225  0
             toRemove = ((List) list).remove(0);
 226   
         }
 227   
 
 228  15
         return toRemove;
 229   
     }
 230   
 }
 231