001 /*
002 * Copyright 2001-2004 The Apache Software Foundation
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016 package org.apache.commons.cache;
017
018 import java.util.HashMap;
019 import java.util.ArrayList;
020 import java.util.NoSuchElementException;
021 import java.io.Serializable;
022 import java.io.ObjectInputStream;
023 import java.io.IOException;
024 import java.io.NotActiveException;
025 import org.apache.commons.cache.adt.Listable;
026 import org.apache.commons.cache.adt.WListableObject;
027
028 /**
029 * tk.
030 * @version $Id: LRUEvictionPolicy.java 155435 2005-02-26 13:17:27Z dirkv $
031 * @author Rodney Waldhoff
032 */
033 public class LRUEvictionPolicy implements EvictionPolicy, StorageListener, RetrievalListener, CachedObjectIterator {
034 transient protected HashMap _hash = new HashMap();
035 transient protected WListableObject _leastRecent = null;
036 transient protected WListableObject _mostRecent = null;
037 transient protected WListableObject _current = null;
038
039 protected boolean _canRemove = false;
040 public Cache _cache = null;
041 protected int _objsbetweennaps;
042 protected long _sleeptimemillis;
043
044 public LRUEvictionPolicy() {
045 this(StaleObjectEvictor.DEFAULT_OBJECTS_BETWEEN_NAPS,StaleObjectEvictor.DEFAULT_SLEEP_TIME_MILLIS);
046 }
047
048 public LRUEvictionPolicy(int objsbetweennaps, long sleeptimemillis) {
049 _objsbetweennaps = objsbetweennaps;
050 _sleeptimemillis = sleeptimemillis;
051 Thread t = new Thread(new StaleObjectEvictor(this,_objsbetweennaps,_sleeptimemillis));
052 t.setDaemon(true);
053 t.start();
054 }
055
056 private void writeObject(java.io.ObjectOutputStream out) throws IOException {
057 out.defaultWriteObject();
058 WListableObject cur = _leastRecent;
059 while(null != cur) {
060 out.writeObject(cur.getValue());
061 cur =(WListableObject)(cur.getNext());
062 }
063 out.writeObject(null);
064 }
065
066 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
067 try {
068 in.defaultReadObject();
069 _hash = new HashMap();
070 for(;;) {
071 Object obj = in.readObject();
072 if(null == obj) {
073 break;
074 } else {
075 WListableObject temp = new WListableObject(obj,_mostRecent,null);
076 if(null == _leastRecent) {
077 _leastRecent = temp;
078 _current = temp;
079 }
080 if(null != _mostRecent) {
081 _mostRecent.setNext(temp);
082 }
083 _mostRecent = temp;
084 _hash.put(((CachedObjectInfo)obj).getKey(),_mostRecent);
085 }
086 }
087
088 Thread t = new Thread(new StaleObjectEvictor(this,_objsbetweennaps,_sleeptimemillis));
089 t.setDaemon(true);
090 t.start();
091 } catch(NotActiveException e) {
092 e.printStackTrace();
093 }
094 }
095
096 protected synchronized void addToList(WListableObject cur) {
097 if(null == _mostRecent) {
098 _mostRecent = cur;
099 _leastRecent = cur;
100 } else {
101 _mostRecent.setNext(cur);
102 cur.setPrev(_mostRecent);
103 _mostRecent = cur;
104 }
105 }
106
107 protected synchronized void removeFromList(WListableObject cur) {
108 // post condition: cur.next and cur.prev are both null
109 if(_current == cur) {
110 _current = (WListableObject)(_current.getPrev());
111 _canRemove = false;
112 }
113 if(cur.hasPrev()) {
114 if(cur.hasNext()) {
115 cur.getPrev().setNext(cur.getNext());
116 cur.getNext().setPrev(cur.getPrev());
117 cur.setNext(null);
118 cur.setPrev(null);
119 } else {
120 // else cur is the most recent and cur.next is null
121 _mostRecent = (WListableObject)(cur.getPrev());
122 cur.getPrev().setNext(null);
123 cur.setPrev(null);
124 }
125 } else {
126 // else cur is the least recent and cur.prev is null
127 _leastRecent = (WListableObject)(cur.getNext());
128 if(cur.hasNext()) {
129 cur.getNext().setPrev(null);
130 cur.setNext(null);
131 } else {
132 // else cur is both least and most recent
133 // and both next and prev are null
134 _leastRecent = null;
135 _mostRecent = null;
136 }
137 }
138 }
139
140
141 public synchronized boolean hasNext() {
142 return (null != _mostRecent);
143 }
144
145 public synchronized CachedObjectInfo getNext() throws NoSuchElementException {
146 if(null != _current) {
147 _current = (WListableObject)(_current.getNext());
148 }
149 if(null == _current) { _current = _leastRecent; }
150 if(null == _current) {
151 throw new NoSuchElementException();
152 } else {
153 _canRemove = true;
154 return (CachedObjectInfo)(_current.getValue());
155 }
156 }
157
158 public synchronized Object next() throws NoSuchElementException {
159 return getNext();
160 }
161
162 public void remove() throws NoSuchElementException, IllegalStateException {
163 // grab a lock on _cache first, since _cache may try to grab a lock on this
164 synchronized(_cache) {
165 synchronized(this) {
166 if(null == _current) {
167 throw new IllegalStateException();
168 }
169 if(_canRemove) {
170 _cache.clear( ((CachedObjectInfo)(_current.getValue())).getKey() );
171 } else {
172 throw new IllegalStateException();
173 }
174 }
175 }
176 }
177
178
179 /** Sets my cache. */
180 public void setCache(Cache c) {
181 if(null != _cache) {
182 Object mutex = _cache;
183 synchronized(mutex) {
184 synchronized(c) {
185 synchronized(this) {
186 unsetCache();
187 _cache = c;
188 _cache.registerRetrievalListener(this);
189 _cache.registerStorageListener(this);
190 }
191 }
192 }
193 } else {
194 synchronized(c) {
195 synchronized(this) {
196 _cache = c;
197 _cache.registerRetrievalListener(this);
198 _cache.registerStorageListener(this);
199 }
200 }
201 }
202 }
203
204 /** Unsets my cache. */
205 public void unsetCache() {
206 if(null != _cache) {
207 Object mutex = _cache;
208 synchronized(mutex) {
209 synchronized(this) {
210 _cache.unregisterRetrievalListener(this);
211 _cache.unregisterStorageListener(this);
212 _cache = null;
213 }
214 }
215 }
216 }
217
218 public void storeRequested(Serializable key, Serializable val, Long expiresAt, Long cost, Serializable group) { }
219
220 public void notStored(Serializable key, Serializable val, Long expiresAt, Long cost, Serializable group) { }
221
222 public synchronized void stored(Serializable key, Serializable val, Long expiresAt, Long cost, Serializable group) {
223 WListableObject cur = (WListableObject)(_hash.get(key));
224 if(null == cur) {
225 cur = new WListableObject(new CachedObjectInfoImpl(key,expiresAt,cost));
226 addToList(cur);
227 _hash.put(key,cur);
228 } else {
229 removeFromList(cur);
230 addToList(cur);
231 }
232 }
233
234 public synchronized void cleared(Serializable key) {
235 WListableObject cur = (WListableObject)(_hash.get(key));
236 if(cur != null) {
237 removeFromList(cur);
238 _hash.remove(key);
239 }
240 }
241
242 public synchronized void cleared() {
243 _hash.clear();
244 _mostRecent = null;
245 _leastRecent = null;
246 _current = null;
247 }
248
249 public void retrieveRequested(Serializable key) {
250 }
251
252 public synchronized void retrieved(Serializable key) {
253 WListableObject cur = (WListableObject)(_hash.get(key));
254 if(null == cur) {
255 cur = new WListableObject(new CachedObjectInfoImpl(key,null,null));
256 addToList(cur);
257 _hash.put(key,cur);
258 } else {
259 removeFromList(cur);
260 addToList(cur);
261 }
262 }
263
264 public void notRetrieved(Serializable key) {
265 }
266
267 public synchronized Serializable getEvictionCandidate() {
268 try {
269 return ((CachedObjectInfoImpl)(_leastRecent.getValue())).getKey();
270 } catch(NullPointerException e) {
271 return null;
272 }
273 }
274
275 public synchronized Serializable[] getEvictionCandidates(int n) {
276 ArrayList v = new ArrayList(n);
277 WListableObject c = _leastRecent;
278 while(n-- > 0) {
279 if(null != c) {
280 v.add(((CachedObjectInfoImpl)(c.getValue())).getKey());
281 c = (WListableObject)(c.getNext());
282 } else {
283 break;
284 }
285 }
286 return (Serializable[])(v.toArray(new Serializable[0]));
287 }
288
289 public synchronized String toString() {
290 StringBuffer buf = new StringBuffer();
291 WListableObject c = _leastRecent;
292 while(c != null) {
293 if(c.hasPrev()) {
294 buf.append(", ");
295 }
296 buf.append(c.getValue());
297 c = (WListableObject)(c.getNext());
298 }
299 return buf.toString();
300 }
301 }