001: package com.knowgate.cache;
002:
003: import com.knowgate.debug.DebugFile;
004:
005: import java.util.Hashtable;
006:
007: /*
008: * ExpireableCache.java
009: *
010: * Created: Fri Sep 17 09:43:10 1999
011: *
012: * Copyright (C) 2000 Sebastian Schaffert
013: *
014: * This program is free software; you can redistribute it and/or
015: * modify it under the terms of the GNU General Public License
016: * as published by the Free Software Foundation; either version 2
017: * of the License, or (at your option) any later version.
018: *
019: * This program is distributed in the hope that it will be useful,
020: * but WITHOUT ANY WARRANTY; without even the implied warranty of
021: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
022: * GNU General Public License for more details.
023: *
024: * You should have received a copy of the GNU General Public License
025: * along with this program; if not, write to the Free Software
026: * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
027: */
028: /**
029: * This class represents a cache that automatically expires objects when a certain fillness
030: * factor is reached.
031: *
032: * @author Sebastian Schaffert
033: * @version
034: */
035:
036: public class ExpireableCache extends Thread {
037:
038: protected Hashtable cache;
039: protected MyHeap timestamps;
040:
041: protected int capacity;
042: protected float expire_factor;
043:
044: protected int hits = 0;
045: protected int misses = 0;
046:
047: protected boolean shutdown = false;
048:
049: protected long max_keep_alive;
050:
051: public ExpireableCache(int capacity, float expire_factor,
052: long max_keep_alive) {
053: super ("ExpireableCache");
054: setPriority(MIN_PRIORITY);
055: cache = new Hashtable(capacity);
056: timestamps = new MyHeap(capacity);
057: this .capacity = capacity;
058: this .expire_factor = expire_factor;
059: this .max_keep_alive = max_keep_alive;
060: }
061:
062: public ExpireableCache(int capacity) {
063: this (capacity, (float) .80, 600000l);
064: }
065:
066: /*
067: * Insert an element into the cache
068: */
069: public synchronized void put(Object key, Object value) {
070: /* When the absolute capacity is exceeded, we must clean up */
071: if (cache.size() + 1 >= capacity) {
072: expireOver();
073: }
074:
075: long l = System.currentTimeMillis();
076: if (cache.containsKey(key))
077: cache.remove(key);
078: cache.put(key, value);
079: timestamps.remove(key);
080: timestamps.insert(key, l);
081: expireOver();
082: }
083:
084: public Object get(Object key) {
085: long l = System.currentTimeMillis();
086: timestamps.remove(key);
087: timestamps.insert(key, l);
088: return cache.get(key);
089: }
090:
091: public synchronized void remove(Object key) {
092: cache.remove(key);
093: timestamps.remove(key);
094: notifyAll();
095: }
096:
097: protected synchronized void expireOver() {
098: String nk;
099:
100: if (DebugFile.trace) {
101: DebugFile.writeln("Begin ExpireableCache.expireOver()");
102: DebugFile.incIdent();
103: DebugFile.writeln("size before expire = "
104: + String.valueOf(cache.size()));
105: DebugFile.writeln("capacity = " + String.valueOf(capacity));
106: DebugFile.writeln("expire_factor = "
107: + String.valueOf(expire_factor));
108: DebugFile.writeln("expiring over capacity...");
109: }
110:
111: // Remove items over capacity limit
112:
113: while (cache.size() >= (capacity * expire_factor)) {
114: nk = (String) timestamps.next();
115: cache.remove(nk);
116: } // wend
117:
118: // Remove items that have exceeded the keep alive limit
119:
120: if (DebugFile.trace)
121: DebugFile.writeln("expiring outdated...");
122:
123: if (max_keep_alive > 0) {
124: long now = new java.util.Date().getTime();
125:
126: while (timestamps.size() > 0) {
127: if (timestamps.peek() + max_keep_alive > now) {
128: nk = (String) timestamps.next();
129: cache.remove(nk);
130: }
131: } // wend
132: } // fi
133:
134: if (DebugFile.trace) {
135: DebugFile.writeln("size after expire = "
136: + String.valueOf(cache.size()));
137: DebugFile.decIdent();
138: DebugFile.writeln("End ExpireableCache.expireOver()");
139: }
140: }
141:
142: public void setCapacity(int size) {
143: capacity = size;
144: }
145:
146: public int getCapacity() {
147: return capacity;
148: }
149:
150: public int getUsage() {
151: return cache.size();
152: }
153:
154: public int getHits() {
155: return hits;
156: }
157:
158: public int getMisses() {
159: return misses;
160: }
161:
162: public void hit() {
163: hits++;
164: }
165:
166: public void miss() {
167: misses++;
168: }
169:
170: public void shutdown() {
171: shutdown = true;
172: }
173:
174: // -------------------------------------------------------------------------
175:
176: public void run() {
177: while (!shutdown) {
178: try {
179: // run expireOver once every 2 minutes
180: wait(120000l);
181: } catch (InterruptedException e) {
182: }
183: expireOver();
184: }
185: }
186:
187: // -------------------------------------------------------------------------
188:
189: /**
190: * Implement a simple heap that just returns the smallest long variable/Object key pair.
191: */
192: protected class MyHeap {
193: int num_entries;
194: long[] values;
195: Object[] keys;
196:
197: MyHeap(int capacity) {
198: values = new long[capacity + 1];
199: keys = new Object[capacity + 1];
200: num_entries = 0;
201: }
202:
203: public int size() {
204: return num_entries;
205: }
206:
207: /**
208: * Insert a key/value pair
209: * Reorganize Heap afterwards
210: */
211: public void insert(Object key, long value) {
212: keys[num_entries] = key;
213: values[num_entries] = value;
214: num_entries++;
215:
216: increase(num_entries);
217: }
218:
219: /**
220: * Return timestamp with the lowest value.
221: * Does not delete key nor reorganize heap.
222: */
223: public long peek() throws ArrayIndexOutOfBoundsException {
224: if (num_entries <= 0)
225: throw new ArrayIndexOutOfBoundsException(
226: "ExpireableCache heap is empty");
227:
228: return values[0];
229: }
230:
231: /**
232: * Return and delete the key with the lowest long value. Reorganize Heap.
233: */
234: public Object next() throws ArrayIndexOutOfBoundsException {
235: if (num_entries <= 0)
236: throw new ArrayIndexOutOfBoundsException(
237: "ExpireableCache heap is empty");
238:
239: Object ret = keys[0];
240: keys[0] = keys[num_entries - 1];
241: values[0] = values[num_entries - 1];
242: num_entries--;
243:
244: decrease(1);
245:
246: return ret;
247: }
248:
249: /**
250: * Remove an Object from the Heap.
251: * Unfortunately not (yet) of very good complexity since we are doing
252: * a simple linear search here.
253: * @param key The key to remove from the heap
254: */
255:
256: public void remove(Object key) {
257: for (int i = 0; i < num_entries; i++) {
258: if (key.equals(keys[i])) {
259: num_entries--;
260: int cur_pos = i + 1;
261: keys[i] = keys[num_entries];
262: decrease(cur_pos);
263: break;
264: } // fi
265: } // next(i)
266: }
267:
268: /**
269: * Lift an element in the heap structure
270: * Note that the cur_pos is actually one larger than the position in the array!
271: */
272: protected void increase(int cur_pos) {
273: while (cur_pos > 1
274: && values[cur_pos - 1] < values[cur_pos / 2 - 1]) {
275: Object tmp1 = keys[cur_pos / 2 - 1];
276: keys[cur_pos / 2 - 1] = keys[cur_pos - 1];
277: keys[cur_pos - 1] = tmp1;
278: long tmp2 = values[cur_pos / 2 - 1];
279: values[cur_pos / 2 - 1] = values[cur_pos - 1];
280: values[cur_pos - 1] = tmp2;
281: cur_pos /= 2;
282: } // wend
283: } // increase
284:
285: /**
286: * Lower an element in the heap structure
287: * Note that the cur_pos is actually one larger than the position in the array!
288: */
289: protected void decrease(int cur_pos) {
290: while ((cur_pos * 2 <= num_entries && values[cur_pos - 1] > values[cur_pos * 2 - 1])
291: || (cur_pos * 2 + 1 <= num_entries && values[cur_pos - 1] > values[cur_pos * 2])) {
292: int lesser_son;
293: if (cur_pos * 2 + 1 <= num_entries) {
294: lesser_son = values[cur_pos * 2 - 1] < values[cur_pos * 2] ? cur_pos * 2
295: : cur_pos * 2 + 1;
296: } else {
297: lesser_son = cur_pos * 2;
298: }
299: Object tmp1 = keys[cur_pos - 1];
300: keys[cur_pos - 1] = keys[lesser_son - 1];
301: keys[lesser_son - 1] = tmp1;
302: long tmp2 = values[cur_pos - 1];
303: values[cur_pos - 1] = values[lesser_son - 1];
304: values[lesser_son - 1] = tmp2;
305: cur_pos = lesser_son;
306: } // wend
307: } // decrease
308:
309: }
310: } // ExpireableCache
|