001: /*
002: * <copyright>
003: *
004: * Copyright 2002-2004 BBNT Solutions, LLC
005: * under sponsorship of the Defense Advanced Research Projects
006: * Agency (DARPA).
007: *
008: * You can redistribute this software and/or modify it under the
009: * terms of the Cougaar Open Source License as published on the
010: * Cougaar Open Source Website (www.cougaar.org).
011: *
012: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
013: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
014: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
015: * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
016: * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
017: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
018: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
019: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
020: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
021: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
022: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
023: *
024: * </copyright>
025: */
026:
027: package org.cougaar.util;
028:
029: import java.io.Serializable;
030: import java.util.Iterator;
031: import java.util.LinkedHashMap;
032: import java.util.Map;
033:
034: /**
035: * An LRUExpireMap is a simple least-recently-used cache that also
036: * expires entries based on the system time.
037: * <p>
038: * Entries are put in the map with an explicit expiration time. The
039: * cache will not return expired entries and will remove them
040: * automatically. The cache also has a maximum size to limit the
041: * number of non-expired entries.
042: * <p>
043: * The caller must synchronized access on this map.
044: * <p>
045: * If you just want a simple LRU cache then see the javadocs for
046: * <tt>LinkedHashMap</tt>, where you can override the
047: * "removeEldestEntry(..)" method.
048: */
049: public class LRUExpireMap extends LinkedHashMap {
050:
051: /** configuration controller */
052: public interface Config {
053: /** the initial size for the map */
054: int initialSize();
055:
056: /** the maximum cache size */
057: int maxSize();
058:
059: /** the minimal entry lifetime if the get-bypass is used */
060: long minBypassTime();
061: }
062:
063: /** optional observer for logging/statistics */
064: public interface Watcher {
065: /** called upon removal of an expired entry */
066: void noteExpire(Object key, Object value, long putTime,
067: long expireTime);
068:
069: /** called when the non-expired LRU is evicted due to overfill */
070: void noteEvict(Object key, Object value, long putTime,
071: long expireTime);
072:
073: /** called at the end of "trim()" */
074: void noteTrim(int nfreed, int origSize);
075: }
076:
077: protected final Config config;
078: protected final Watcher watcher;
079:
080: public LRUExpireMap(Config config, Watcher watcher) {
081: super (config.initialSize(), 0.75f, true);
082: this .config = config;
083: this .watcher = watcher;
084: }
085:
086: public Object get(Object key) {
087: return get(key, false);
088: }
089:
090: /**
091: * Get a value with an optional "bypass the cache" flag".
092: * <p>
093: * The config's "minBypassTime()" is consulted if the
094: * entry has not expired. This allows the config to
095: * limit the bypass to a fixed time from the "put(..)"
096: * of the entry (e.g. "you can only bypass if the
097: * entry is older than 5 seconds").
098: *
099: * @return the value
100: */
101: public Object get(Object key, boolean bypass) {
102: Expirable eo = (Expirable) getExpirable(key, bypass);
103: return (eo == null ? null : eo.value);
104: }
105:
106: /**
107: * Get the expiration time for an entry.
108: *
109: * @return -1 if the entry is not in the cache or has expired.
110: */
111: public long getExpirationTime(Object key) {
112: Expirable eo = (Expirable) getExpirable(key, false);
113: return (eo == null ? -1 : eo.expireTime);
114: }
115:
116: protected Expirable getExpirable(Object key) {
117: return getExpirable(key, false);
118: }
119:
120: protected Expirable getExpirable(Object key, boolean bypass) {
121: Expirable ret = null;
122: Expirable eo = (Expirable) super .get(key);
123: if (eo != null) {
124: long now = System.currentTimeMillis();
125: if (eo.expireTime < now) {
126: // expired
127: if (watcher != null) {
128: watcher.noteExpire(key, eo.value, eo.putTime,
129: eo.expireTime);
130: }
131: remove(key);
132: } else if (bypass
133: && (eo.putTime + config.minBypassTime() < now)) {
134: // valid, but the user wants to bypass the cache
135: // and this entry has been around for a little while
136: } else {
137: // valid but maybe null
138: ret = eo;
139: }
140: }
141: return ret;
142: }
143:
144: /**
145: * @throws UnsupportedOperationException
146: * Must specify an expiration time
147: */
148: public Object put(Object key, Object value) {
149: throw new UnsupportedOperationException(
150: "Must specify an expiration time");
151: }
152:
153: /**
154: * Put an entry in the cache with an expiration time.
155: * <p>
156: * If it has already expired, this is method removes the old
157: * value (even if it hasn't expired) and ignores the new value.
158: *
159: * @return the old value if one was replaced
160: */
161: public Object put(Object key, Object value, long expireTime) {
162: Expirable oldEO = null;
163: long now = System.currentTimeMillis();
164: if (expireTime <= now) {
165: oldEO = (Expirable) super .remove(key);
166: } else {
167: Expirable eo = new Expirable(value, now, expireTime);
168: oldEO = (Expirable) super .put(key, eo);
169: }
170: return (oldEO == null ? null : oldEO.value);
171: }
172:
173: /**
174: * Called by the LinkedHashMap when an entry is added,
175: * this allows the cache to remove the LRU "eldest" entry.
176: */
177: protected boolean removeEldestEntry(Map.Entry eldest) {
178: // check size
179: int origSize = size();
180: if (origSize < config.maxSize()) {
181: // plenty of room left...
182: return false;
183: }
184: long now = System.currentTimeMillis();
185: // quick-check for an expired eldest
186: Expirable eo = (eldest == null ? (null) : (Expirable) eldest
187: .getValue());
188: if (eo != null && eo.expireTime < now) {
189: // the eldest has expired, so just remove it
190: if (watcher != null) {
191: watcher.noteExpire(eldest.getKey(), eo.value,
192: eo.putTime, eo.expireTime);
193: }
194: return true;
195: }
196: if (trim()) {
197: // removed something, so leave the eldest alone
198: return false;
199: }
200: // remove the eldest entry
201: if (eo != null && watcher != null) {
202: watcher.noteEvict(eldest.getKey(), eo.value, eo.putTime,
203: eo.expireTime);
204: }
205: return true;
206: }
207:
208: /**
209: * Remove all expired entries from the cache.
210: * <p>
211: * This can optionally be called on a periodic timer, but
212: * it's not necessary -- the cache will limit its size based
213: * upon the config's "maxSize()".
214: *
215: * @return true if anything was removed
216: */
217: public boolean trim() {
218: int origSize = size();
219: if (origSize <= 0) {
220: return false;
221: }
222: int nfreed = 0;
223: long now = System.currentTimeMillis();
224: for (Iterator iter = entrySet().iterator(); iter.hasNext();) {
225: Map.Entry me = (Map.Entry) iter.next();
226: Expirable eo = (Expirable) me.getValue();
227: if (eo.expireTime < now) {
228: if (watcher != null) {
229: watcher.noteExpire(me.getKey(), eo.value,
230: eo.putTime, eo.expireTime);
231: }
232: iter.remove();
233: ++nfreed;
234: }
235: }
236: if (watcher != null) {
237: watcher.noteTrim(nfreed, origSize);
238: }
239: return (nfreed > 0);
240: }
241:
242: /**
243: * All entries are of this type.
244: * <p>
245: * Typically this isn't visible, but an iterator
246: * will see it...
247: */
248: public static class Expirable implements Serializable {
249: public final Object value;
250: public final long putTime;
251: public final long expireTime;
252:
253: public Expirable(Object value, long now, long expireTime) {
254: this .value = value;
255: this .putTime = now;
256: this .expireTime = expireTime;
257: if (expireTime <= now) {
258: throw new IllegalArgumentException("Expire time ("
259: + expireTime
260: + ") must be >= to the current time (" + now
261: + ")");
262: }
263: }
264:
265: public String toString() {
266: return "(updated=" + putTime + " expires=" + expireTime
267: + " value=" + value + ")";
268: }
269: }
270:
271: }
|