001: /*
002: * Copyright (c) 2002-2003 by OpenSymphony
003: * All rights reserved.
004: */
005: package com.opensymphony.oscache.base.algorithm;
006:
007: import java.util.*;
008:
009: /**
010: * <p>LRU (Least Recently Used) algorithm for the cache.</p>
011: *
012: * <p>Since release 2.3 this class requires Java 1.4
013: * to use the <code>LinkedHashSet</code>. Use prior OSCache release which
014: * require the Jakarta commons-collections <code>SequencedHashMap</code>
015: * class or the <code>LinkedList</code> class if neither of the above
016: * classes are available.</p>
017: *
018: * <p>No synchronization is required in this class since the
019: * <code>AbstractConcurrentReadCache</code> already takes care of any
020: * synchronization requirements.</p>
021: *
022: * @version $Revision: 427 $
023: * @author <a href="mailto:salaman@teknos.com">Victor Salaman</a>
024: * @author <a href="mailto:fbeauregard@pyxis-tech.com">Francois Beauregard</a>
025: * @author <a href="mailto:abergevin@pyxis-tech.com">Alain Bergevin</a>
026: * @author <a href="mailto:chris@swebtec.com">Chris Miller</a>
027: */
028: public class LRUCache extends AbstractConcurrentReadCache {
029:
030: private static final long serialVersionUID = -7379608101794788534L;
031:
032: /**
033: * Cache queue containing all cache keys.
034: */
035: private Collection list = new LinkedHashSet();
036:
037: /**
038: * A flag indicating whether there is a removal operation in progress.
039: */
040: private volatile boolean removeInProgress = false;
041:
042: /**
043: * Constructs an LRU Cache.
044: */
045: public LRUCache() {
046: super ();
047: }
048:
049: /**
050: * Constructors a LRU Cache of the specified capacity.
051: *
052: * @param capacity The maximum cache capacity.
053: */
054: public LRUCache(int capacity) {
055: this ();
056: maxEntries = capacity;
057: }
058:
059: /**
060: * An item was retrieved from the list. The LRU implementation moves
061: * the retrieved item's key to the front of the list.
062: *
063: * @param key The cache key of the item that was retrieved.
064: */
065: protected void itemRetrieved(Object key) {
066: // Prevent list operations during remove
067: while (removeInProgress) {
068: try {
069: Thread.sleep(5);
070: } catch (InterruptedException ie) {
071: }
072: }
073:
074: // We need to synchronize here because AbstractConcurrentReadCache
075: // doesn't prevent multiple threads from calling this method simultaneously.
076: synchronized (list) {
077: list.remove(key);
078: list.add(key);
079: }
080: }
081:
082: /**
083: * An object was put in the cache. This implementation adds/moves the
084: * key to the end of the list.
085: *
086: * @param key The cache key of the item that was put.
087: */
088: protected void itemPut(Object key) {
089: // Since this entry was just accessed, move it to the back of the list.
090: synchronized (list) { // A further fix for CACHE-44
091: list.remove(key);
092: list.add(key);
093: }
094: }
095:
096: /**
097: * An item needs to be removed from the cache. The LRU implementation
098: * removes the first element in the list (ie, the item that was least-recently
099: * 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: }
|