001: /*
002: * TimeCache.java February 2001
003: *
004: * Copyright (C) 2001, Niall Gallagher <niallg@users.sf.net>
005: *
006: * This library is free software; you can redistribute it and/or
007: * modify it under the terms of the GNU Lesser General Public
008: * License as published by the Free Software Foundation.
009: *
010: * This library is distributed in the hope that it will be useful,
011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
013: * GNU Lesser General Public License for more details.
014: *
015: * You should have received a copy of the GNU Lesser General
016: * Public License along with this library; if not, write to the
017: * Free Software Foundation, Inc., 59 Temple Place, Suite 330,
018: * Boston, MA 02111-1307 USA
019: */
020:
021: package simple.util.cache;
022:
023: import simple.util.schedule.Scheduler;
024: import java.lang.ref.Reference;
025:
026: /**
027: * This is a LRU, Least Recently Used, <code>TimeCache</code> for caching
028: * objects. This ensures that the <code>TimeCache</code> does not allow
029: * too many objects to be cached. This does not account for anything
030: * other than the number of lockable regions, i.e. synchronized Least
031: * Recently Used lists, and the maximum number of items a region can
032: * have before it removes the least recently used objects.
033: * <p>
034: * When objects are cached they can be cached for a specified number of
035: * miliseconds, when this expires then the time cache will remove the
036: * item, this removal is very accurate to the timeout specified for the
037: * object. If no time out is given a default timeout for this is used.
038: * The maximum capacity of the <code>TimeCache</code> is regions * limit,
039: * however this does not provide an exact Least Recently Used semantic
040: * as some regions are likely to have more hits than others.
041: *
042: * @author Niall Gallagher
043: */
044: public class TimeCache {
045:
046: /**
047: * This is the default refresh rate for the cache.
048: */
049: private static final int DEFAULT_TIMEOUT = 60000;
050:
051: /**
052: * This is the default number of regions for the cache.
053: */
054: private static final int DEFAULT_LOCKS = 10;
055:
056: /**
057: * This is the default number of elements per lock.
058: */
059: private static final int DEFAULT_LIMIT = 6;
060:
061: /**
062: * Used by this to dispose of expired objects.
063: */
064: private Scheduler queue;
065:
066: /**
067: * Will use the scheduler to clean this.
068: */
069: private CacheCleaner cleaner;
070:
071: /**
072: * Used to store the lists that store objects.
073: */
074: private CacheList[] list;
075:
076: /**
077: * Default length of time an item can be cached.
078: */
079: private int timeout;
080:
081: /**
082: * This is used to create a <code>TimeCache</code> object for storing
083: * objects. This cache implementation is an Least Recently Used cache
084: * meaning that the Least Recently Used items are removed if the
085: * size of a region grows to large. This has a maximum capacity
086: * of 60, unlikely.
087: */
088: public TimeCache() {
089: this (DEFAULT_LOCKS, DEFAULT_LIMIT);
090: }
091:
092: /**
093: * This is used to create a <code>TimeCache</code> object for storing
094: * objects. This cache implementation is an Least Recently Used cache
095: * meaning that the Least Recently Used items are removed if the
096: * size if the region grows to large. This constructor configures
097: * the <code>TimeCache</code> as specified.
098: *
099: * @param regions number of regions that are synchronized
100: * @param limit the maximum amount of objects per region
101: */
102: public TimeCache(int regions, int limit) {
103: this (regions, limit, DEFAULT_TIMEOUT);
104: }
105:
106: /**
107: * This is a constructor method used by 'this' to specify the
108: * characteristics that the <code>TimeCache</code> may have. This
109: * will allow the max timeout to be specified for the
110: * <code>TimeCache</code>.
111: *
112: * @param regions number of regions that are synchronized
113: * @param limit the maximum amount of objects per region
114: * @param timeout the default timeout peroid for an object
115: */
116: public TimeCache(int regions, int limit, int timeout) {
117: this .queue = new Scheduler();
118: this .cleaner = new CacheCleaner(this , queue);
119: this .timeout = timeout;
120: this .init(regions, limit);
121: }
122:
123: /**
124: * In this <code>TimeCache</code> a region is considered to be an area
125: * within the <code>TimeCache</code> that is synchronized independantly.
126: * This means that if there are two threads accessing the
127: * <code>TimeCache</code>, they can access objects that hash to a different
128: * regions concurrently. This <code>TimeCache</code> maintains an array of
129: * <code>CacheList</code> objects. These are Least Recently Used
130: * lists in the sense that if they reach there maximum capacity they
131: * will drop the most unused items. The limit defines the maximum
132: * capacity of a region i.e. list.
133: *
134: * @param regions number of regions that are synchronized
135: * @param limit the maximum amount of objects per region
136: */
137: private void init(int regions, int limit) {
138: list = new CacheList[regions];
139:
140: for (int i = 0; i < regions; i++) {
141: list[i] = new CacheList(limit);
142: }
143: }
144:
145: /**
146: * This will store the object given in the <code>TimeCache</code>
147: * under the reference specified. The object may exist in the
148: * <code>TimeCache</code> for a limited time only specified by a
149: * timeout.
150: *
151: * @param key this is the key that references the object
152: * @param obj this is the object that is to be stored
153: */
154: public void cache(Object key, Object obj) {
155: int pos = translate(key);
156: list[pos].insert(key, obj);
157: schedule(key, obj, timeout);
158: }
159:
160: /**
161: * This will store the object given in the <code>TimeCache</code>
162: * under the reference specified. The object may exist in the
163: * <code>TimeCache</code> for a limited time only specified by a
164: * timeout.
165: *
166: * @param key this is the key that references the object
167: * @param obj this is the object that is to be stored
168: * @param timeout max amount of time this can be
169: * cached.
170: */
171: public void cache(Object key, Object obj, int timeout) {
172: int pos = translate(key);
173: list[pos].insert(key, obj);
174: schedule(key, obj, timeout);
175: }
176:
177: /**
178: * This is used so that objects that are enqueued into the
179: * <code>TimeCache</code> can be removed after a certain peroid
180: * of time.
181: *
182: * @param key this is the key that references the object
183: * @param obj this is the object that is to be stored
184: * @param timeout max amount of time this can be cached
185: */
186: private void schedule(Object key, Object obj, int timeout) {
187: Reference ref = new CacheReference(key, obj);
188: queue.enqueue(ref, timeout);
189: }
190:
191: /**
192: * This is a simple function that maps an objects hash
193: * code using <code>Object.hashCode</code> into an array
194: * subscript.
195: *
196: * @param key the object that is to be translated
197: *
198: * @return an array subscript into the list
199: */
200: private int translate(Object key) {
201: int hash = key.hashCode();
202: if (hash < 0)
203: hash *= -1;
204: return hash % list.length;
205: }
206:
207: /**
208: * This will search the <code>TimeCache</code> to see if the item
209: * in the time cache. If it is in the cache this will return it.
210: * This provides a very concurrent lookup mechanism, where threads
211: * have less contention for locks, as the key decides which list
212: * to use based on the value of the key hash code.
213: *
214: * @param key this is the key that references the object
215: *
216: * @return the object that is referenced by the key
217: */
218: public Object lookup(Object key) {
219: int pos = translate(key);
220: return list[pos].lookup(key);
221: }
222:
223: /**
224: * This will check to see if an object exists within the
225: * <code>TimeCache</code>. If it exists this returns true else
226: * false.
227: *
228: * @param key this is the key that references the object
229: *
230: * @return a boolean indicating the status of the object
231: */
232: public boolean contains(Object key) {
233: int pos = translate(key);
234: return list[pos].contains(key);
235: }
236:
237: /**
238: * This will remove the object cached using the specified
239: * key. If the object is not stored this does nothing.
240: * This ensures that no reference fot the object is left.
241: *
242: * @param key this is the key that references the object
243: */
244: public Object remove(Object key) {
245: int pos = translate(key);
246: return list[pos].remove(key);
247: }
248:
249: /**
250: * This will remove all items from the <code>TimeCache</code>.
251: * This is used to synchronize the cached objects.
252: */
253: public void clear() {
254: for (int i = 0; i < list.length; i++) {
255: list[i].clear();
256: }
257: }
258: }
|