KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > opensymphony > oscache > base > algorithm > LRUCache


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