Clover coverage report - Coverage timestamp: do jan 22 2004 21:12:32 CET FRAMES NO FRAMES |
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% |

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 |  |