Save This Page
1 /*
2 * Copyright (c) 2002-2003 by OpenSymphony
3 * All rights reserved.
4 */
5 package com.opensymphony.oscache.base.algorithm;
6
7 import java.util;
8
9 /**
10 * <p>LRU (Least Recently Used) algorithm for the cache.</p>
11 *
12 * <p>Since release 2.3 this class requires Java 1.4
13 * to use the <code>LinkedHashSet</code>. Use prior OSCache release which
14 * require the Jakarta commons-collections <code>SequencedHashMap</code>
15 * class or the <code>LinkedList</code> class if neither of the above
16 * classes are available.</p>
17 *
18 * <p>No synchronization is required in this class since the
19 * <code>AbstractConcurrentReadCache</code> already takes care of any
20 * synchronization requirements.</p>
21 *
22 * @version $Revision: 427 $
23 * @author <a href="mailto:salaman@teknos.com">Victor Salaman</a>
24 * @author <a href="mailto:fbeauregard@pyxis-tech.com">Francois Beauregard</a>
25 * @author <a href="mailto:abergevin@pyxis-tech.com">Alain Bergevin</a>
26 * @author <a href="mailto:chris@swebtec.com">Chris Miller</a>
27 */
28 public class LRUCache extends AbstractConcurrentReadCache {
29
30 private static final long serialVersionUID = -7379608101794788534L;
31
32 /**
33 * Cache queue containing all cache keys.
34 */
35 private Collection list = new LinkedHashSet();
36
37 /**
38 * A flag indicating whether there is a removal operation in progress.
39 */
40 private volatile boolean removeInProgress = false;
41
42 /**
43 * Constructs an LRU Cache.
44 */
45 public LRUCache() {
46 super();
47 }
48
49 /**
50 * Constructors a LRU Cache of the specified capacity.
51 *
52 * @param capacity The maximum cache capacity.
53 */
54 public LRUCache(int capacity) {
55 this();
56 maxEntries = capacity;
57 }
58
59 /**
60 * An item was retrieved from the list. The LRU implementation moves
61 * the retrieved item's key to the front of the list.
62 *
63 * @param key The cache key of the item that was retrieved.
64 */
65 protected void itemRetrieved(Object key) {
66 // Prevent list operations during remove
67 while (removeInProgress) {
68 try {
69 Thread.sleep(5);
70 } catch (InterruptedException ie) {
71 }
72 }
73
74 // We need to synchronize here because AbstractConcurrentReadCache
75 // doesn't prevent multiple threads from calling this method simultaneously.
76 synchronized (list) {
77 list.remove(key);
78 list.add(key);
79 }
80 }
81
82 /**
83 * An object was put in the cache. This implementation adds/moves the
84 * key to the end of the list.
85 *
86 * @param key The cache key of the item that was put.
87 */
88 protected void itemPut(Object key) {
89 // Since this entry was just accessed, move it to the back of the list.
90 synchronized (list) { // A further fix for CACHE-44
91 list.remove(key);
92 list.add(key);
93 }
94 }
95
96 /**
97 * An item needs to be removed from the cache. The LRU implementation
98 * removes the first element in the list (ie, the item that was least-recently
99 * accessed).
100 *
101 * @return The key of whichever item was removed.
102 */
103 protected Object removeItem() {
104 Object toRemove = null;
105
106 removeInProgress = true;
107 try {
108 while (toRemove == null) {
109 try {
110 toRemove = removeFirst();
111 } catch (Exception e) {
112 // List is empty.
113 // this is theorically possible if we have more than the size concurrent
114 // thread in getItem. Remove completed but add not done yet.
115 // We simply wait for add to complete.
116 do {
117 try {
118 Thread.sleep(5);
119 } catch (InterruptedException ie) {
120 }
121 } while (list.isEmpty());
122 }
123 }
124 } finally {
125 removeInProgress = false;
126 }
127
128 return toRemove;
129 }
130
131 /**
132 * Remove specified key since that object has been removed from the cache.
133 *
134 * @param key The cache key of the item that was removed.
135 */
136 protected void itemRemoved(Object key) {
137 list.remove(key);
138 }
139
140 /**
141 * Removes the first object from the list of keys.
142 *
143 * @return the object that was removed
144 */
145 private Object removeFirst() {
146 Object toRemove = null;
147
148 synchronized (list) { // A further fix for CACHE-44 and CACHE-246
149 Iterator it = list.iterator();
150 toRemove = it.next();
151 it.remove();
152 }
153
154 return toRemove;
155 }
156 }