|
|||||||||||||||||||
Source file | Conditionals | Statements | Methods | TOTAL | |||||||||||||||
LRUCache.java | 31.2% | 55.8% | 100% | 54.7% |
|
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="mailto:chris@swebtec.com">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 |
|
|