001: /* CVS ID: $Id: ExpireableCache.java,v 1.1.1.1 2002/10/02 18:42:48 wastl Exp $ */
002: package net.wastl.webmail.misc;
003:
004: import java.util.*;
005:
006: /*
007: * ExpireableCache.java
008: *
009: * Created: Fri Sep 17 09:43:10 1999
010: *
011: * Copyright (C) 2000 Sebastian Schaffert
012: *
013: * This program is free software; you can redistribute it and/or
014: * modify it under the terms of the GNU General Public License
015: * as published by the Free Software Foundation; either version 2
016: * of the License, or (at your option) any later version.
017: *
018: * This program is distributed in the hope that it will be useful,
019: * but WITHOUT ANY WARRANTY; without even the implied warranty of
020: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
021: * GNU General Public License for more details.
022: *
023: * You should have received a copy of the GNU General Public License
024: * along with this program; if not, write to the Free Software
025: * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
026: */
027: /**
028: * This class represents a cache that automatically expires objects when a certain fillness
029: * factor is reached.
030: *
031: * @author Sebastian Schaffert
032: * @version
033: */
034:
035: public class ExpireableCache extends Thread {
036:
037: protected Hashtable cache;
038: protected MyHeap timestamps;
039:
040: protected int capacity;
041: protected float expire_factor;
042:
043: protected int hits = 0;
044: protected int misses = 0;
045:
046: protected boolean shutdown = false;
047:
048: public ExpireableCache(int capacity, float expire_factor) {
049: super ("ExpireableCache");
050: setPriority(MIN_PRIORITY);
051: cache = new Hashtable(capacity);
052: timestamps = new MyHeap(capacity);
053: this .capacity = capacity;
054: this .expire_factor = expire_factor;
055: }
056:
057: public ExpireableCache(int capacity) {
058: this (capacity, (float) .90);
059: }
060:
061: /*
062: * Insert an element into the cache
063: */
064: public synchronized void put(Object key, Object value) {
065: /* When the absolute capacity is exceeded, we must clean up */
066: if (cache.size() + 1 >= capacity) {
067: expireOver();
068: }
069:
070: long l = System.currentTimeMillis();
071: cache.put(key, value);
072: timestamps.remove(key);
073: timestamps.insert(key, l);
074: expireOver();
075: }
076:
077: public Object get(Object key) {
078: long l = System.currentTimeMillis();
079: timestamps.remove(key);
080: timestamps.insert(key, l);
081: return cache.get(key);
082: }
083:
084: public synchronized void remove(Object key) {
085: cache.remove(key);
086: timestamps.remove(key);
087: notifyAll();
088: }
089:
090: protected synchronized void expireOver() {
091: while (cache.size() >= (capacity * expire_factor)) {
092: String nk = (String) timestamps.next();
093: cache.remove(nk);
094: }
095: }
096:
097: public void setCapacity(int size) {
098: capacity = size;
099: }
100:
101: public int getCapacity() {
102: return capacity;
103: }
104:
105: public int getUsage() {
106: return cache.size();
107: }
108:
109: public int getHits() {
110: return hits;
111: }
112:
113: public int getMisses() {
114: return misses;
115: }
116:
117: public void hit() {
118: hits++;
119: }
120:
121: public void miss() {
122: misses++;
123: }
124:
125: public void shutdown() {
126: shutdown = true;
127: }
128:
129: public void run() {
130: while (!shutdown) {
131: try {
132: wait(10000);
133: } catch (InterruptedException e) {
134: }
135: expireOver();
136: }
137: }
138:
139: /**
140: * Implement a simple heap that just returns the smallest long variable/Object key pair.
141: */
142: protected class MyHeap {
143: int num_entries;
144: long[] values;
145: Object[] keys;
146:
147: MyHeap(int capacity) {
148: values = new long[capacity + 1];
149: keys = new Object[capacity + 1];
150: num_entries = 0;
151: }
152:
153: /**
154: * Insert a key/value pair
155: * Reorganize Heap afterwards
156: */
157: public void insert(Object key, long value) {
158: keys[num_entries] = key;
159: values[num_entries] = value;
160: num_entries++;
161:
162: increase(num_entries);
163: }
164:
165: /**
166: * Return and delete the key with the lowest long value. Reorganize Heap.
167: */
168: public Object next() {
169: Object ret = keys[0];
170: keys[0] = keys[num_entries - 1];
171: values[0] = values[num_entries - 1];
172: num_entries--;
173:
174: decrease(1);
175:
176: return ret;
177: }
178:
179: /**
180: * Remove an Object from the Heap.
181: * Unfortunately not (yet) of very good complexity since we are doing
182: * a simple linear search here.
183: * @param key The key to remove from the heap
184: */
185: public void remove(Object key) {
186: for (int i = 0; i < num_entries; i++) {
187: if (key.equals(keys[i])) {
188: num_entries--;
189: int cur_pos = i + 1;
190: keys[i] = keys[num_entries];
191: decrease(cur_pos);
192: break;
193: }
194: }
195: }
196:
197: /**
198: * Lift an element in the heap structure
199: * Note that the cur_pos is actually one larger than the position in the array!
200: */
201: protected void increase(int cur_pos) {
202: while (cur_pos > 1
203: && values[cur_pos - 1] < values[cur_pos / 2 - 1]) {
204: Object tmp1 = keys[cur_pos / 2 - 1];
205: keys[cur_pos / 2 - 1] = keys[cur_pos - 1];
206: keys[cur_pos - 1] = tmp1;
207: long tmp2 = values[cur_pos / 2 - 1];
208: values[cur_pos / 2 - 1] = values[cur_pos - 1];
209: values[cur_pos - 1] = tmp2;
210: cur_pos /= 2;
211: }
212: }
213:
214: /**
215: * Lower an element in the heap structure
216: * Note that the cur_pos is actually one larger than the position in the array!
217: */
218: protected void decrease(int cur_pos) {
219: while ((cur_pos * 2 <= num_entries && values[cur_pos - 1] > values[cur_pos * 2 - 1])
220: || (cur_pos * 2 + 1 <= num_entries && values[cur_pos - 1] > values[cur_pos * 2])) {
221: int lesser_son;
222: if (cur_pos * 2 + 1 <= num_entries) {
223: lesser_son = values[cur_pos * 2 - 1] < values[cur_pos * 2] ? cur_pos * 2
224: : cur_pos * 2 + 1;
225: } else {
226: lesser_son = cur_pos * 2;
227: }
228: Object tmp1 = keys[cur_pos - 1];
229: keys[cur_pos - 1] = keys[lesser_son - 1];
230: keys[lesser_son - 1] = tmp1;
231: long tmp2 = values[cur_pos - 1];
232: values[cur_pos - 1] = values[lesser_son - 1];
233: values[lesser_son - 1] = tmp2;
234: cur_pos = lesser_son;
235: }
236: }
237:
238: }
239: } // ExpireableCache
|