Clover coverage report -
Coverage timestamp: do jan 22 2004 21:12:32 CET
file stats: LOC: 233   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.3 $
 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  40
     public LRUCache() {
 78  40
         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  40
         try {
 83  40
             ClassLoaderUtil.loadClass("java.util.LinkedHashSet", this.getClass());
 84  40
             list = new LinkedHashSet();
 85  40
             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  34
     public LRUCache(int capacity) {
 109  34
         this();
 110  34
         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  250
     protected void itemRetrieved(Object key) {
 120   
         // Prevent list operations during remove
 121  250
         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  250
         if (isMap) {
 131  0
             synchronized (map) {
 132  0
                 map.remove(key);
 133  0
                 map.put(key, Boolean.TRUE);
 134   
             }
 135   
         } else {
 136  250
             synchronized (list) {
 137  250
                 list.remove(key);
 138  250
                 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  242
     protected void itemPut(Object key) {
 150   
         // Since this entry was just accessed, move it to the back of the list.
 151  242
         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  242
             synchronized (list) { // A further fix for CACHE-44
 158  242
                 list.remove(key);
 159  242
                 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  15
     protected Object removeItem() {
 172  15
         removeInProgress = true;
 173   
 
 174  15
         Object toRemove;
 175   
 
 176  15
         try {
 177  15
             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  15
         removeInProgress = false;
 194   
 
 195  15
         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  51
     protected void itemRemoved(Object key) {
 204  51
         if (isMap) {
 205  0
             map.remove(key);
 206   
         } else {
 207  51
             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  15
     private Object removeFirst() {
 217  15
         Object toRemove;
 218   
 
 219  15
         if (isSet) {
 220  15
             Iterator it = list.iterator();
 221  15
             toRemove = it.next();
 222  15
             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  15
         return toRemove;
 231   
     }
 232   
 }
 233