Clover coverage report -

Coverage timestamp: So Nov 6 2005 14:19:51 CET

FRAMES NO FRAMES

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%

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="mailto:chris@swebtec.com">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		}