KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > knowgate > cache > ExpireableCache


1 package com.knowgate.cache;
2
3 import com.knowgate.debug.DebugFile;
4
5 import java.util.Hashtable JavaDoc;
6
7 /*
8  * ExpireableCache.java
9  *
10  * Created: Fri Sep 17 09:43:10 1999
11  *
12  * Copyright (C) 2000 Sebastian Schaffert
13  *
14  * This program is free software; you can redistribute it and/or
15  * modify it under the terms of the GNU General Public License
16  * as published by the Free Software Foundation; either version 2
17  * of the License, or (at your option) any later version.
18  *
19  * This program is distributed in the hope that it will be useful,
20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22  * GNU General Public License for more details.
23  *
24  * You should have received a copy of the GNU General Public License
25  * along with this program; if not, write to the Free Software
26  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
27  */

28 /**
29  * This class represents a cache that automatically expires objects when a certain fillness
30  * factor is reached.
31  *
32  * @author Sebastian Schaffert
33  * @version
34  */

35
36 public class ExpireableCache extends Thread JavaDoc {
37
38     protected Hashtable JavaDoc cache;
39     protected MyHeap timestamps;
40
41     protected int capacity;
42     protected float expire_factor;
43
44     protected int hits=0;
45     protected int misses=0;
46
47     protected boolean shutdown=false;
48
49     protected long max_keep_alive;
50
51
52     public ExpireableCache(int capacity, float expire_factor, long max_keep_alive) {
53     super("ExpireableCache");
54     setPriority(MIN_PRIORITY);
55     cache=new Hashtable JavaDoc(capacity);
56     timestamps=new MyHeap(capacity);
57     this.capacity=capacity;
58     this.expire_factor=expire_factor;
59         this.max_keep_alive=max_keep_alive;
60     }
61
62     public ExpireableCache(int capacity) {
63     this(capacity, (float).80, 600000l);
64     }
65
66     /*
67      * Insert an element into the cache
68      */

69     public synchronized void put(Object JavaDoc key, Object JavaDoc value) {
70     /* When the absolute capacity is exceeded, we must clean up */
71     if(cache.size()+1 >= capacity) {
72         expireOver();
73     }
74
75     long l=System.currentTimeMillis();
76     if (cache.containsKey(key)) cache.remove(key);
77         cache.put(key,value);
78     timestamps.remove(key);
79     timestamps.insert(key,l);
80     expireOver();
81     }
82
83     public Object JavaDoc get (Object JavaDoc key) {
84     long l=System.currentTimeMillis();
85     timestamps.remove(key);
86     timestamps.insert(key,l);
87     return cache.get(key);
88     }
89
90
91     public synchronized void remove(Object JavaDoc key) {
92     cache.remove (key);
93     timestamps.remove(key);
94     notifyAll();
95     }
96
97
98     protected synchronized void expireOver() {
99     String JavaDoc nk;
100
101         if (DebugFile.trace) {
102           DebugFile.writeln("Begin ExpireableCache.expireOver()");
103           DebugFile.incIdent();
104           DebugFile.writeln("size before expire = " + String.valueOf(cache.size()));
105           DebugFile.writeln("capacity = " + String.valueOf(capacity));
106           DebugFile.writeln("expire_factor = " + String.valueOf(expire_factor));
107           DebugFile.writeln("expiring over capacity...");
108         }
109
110         // Remove items over capacity limit
111

112         while (cache.size()>=(capacity*expire_factor)) {
113         nk = (String JavaDoc) timestamps.next();
114         cache.remove(nk);
115     } // wend
116

117         // Remove items that have exceeded the keep alive limit
118

119         if (DebugFile.trace) DebugFile.writeln("expiring outdated...");
120
121         if (max_keep_alive>0) {
122           long now = new java.util.Date JavaDoc().getTime();
123
124           while (timestamps.size() > 0) {
125             if (timestamps.peek() + max_keep_alive > now) {
126               nk = (String JavaDoc) timestamps.next();
127               cache.remove(nk);
128             }
129           } // wend
130
} // fi
131

132         if (DebugFile.trace) {
133           DebugFile.writeln("size after expire = " + String.valueOf(cache.size()));
134           DebugFile.decIdent();
135           DebugFile.writeln("End ExpireableCache.expireOver()");
136         }
137     }
138
139     public void setCapacity(int size) {
140     capacity=size;
141     }
142
143     public int getCapacity() {
144     return capacity;
145     }
146
147     public int getUsage() {
148     return cache.size();
149     }
150
151     public int getHits() {
152     return hits;
153     }
154
155     public int getMisses() {
156     return misses;
157     }
158
159     public void hit() {
160     hits++;
161     }
162
163     public void miss() {
164     misses++;
165     }
166
167     public void shutdown() {
168     shutdown=true;
169     }
170
171     // -------------------------------------------------------------------------
172

173     public void run() {
174     while (!shutdown) {
175         try {
176                 // run expireOver once every 2 minutes
177
wait (120000l);
178         } catch(InterruptedException JavaDoc e) {}
179         expireOver();
180     }
181     }
182
183     // -------------------------------------------------------------------------
184

185     /**
186      * Implement a simple heap that just returns the smallest long variable/Object key pair.
187      */

188     protected class MyHeap {
189     int num_entries;
190     long[] values;
191     Object JavaDoc[] keys;
192
193     MyHeap(int capacity) {
194         values=new long[capacity+1];
195         keys=new Object JavaDoc[capacity+1];
196         num_entries=0;
197     }
198
199         public int size () {
200           return num_entries;
201         }
202
203     /**
204      * Insert a key/value pair
205      * Reorganize Heap afterwards
206      */

207     public void insert(Object JavaDoc key, long value) {
208         keys[num_entries]=key;
209         values[num_entries]=value;
210         num_entries++;
211
212         increase(num_entries);
213     }
214
215         /**
216          * Return timestamp with the lowest value.
217          * Does not delete key nor reorganize heap.
218          */

219         public long peek() throws ArrayIndexOutOfBoundsException JavaDoc {
220             if (num_entries<=0)
221               throw new ArrayIndexOutOfBoundsException JavaDoc("ExpireableCache heap is empty");
222
223             return values[0];
224         }
225
226     /**
227      * Return and delete the key with the lowest long value. Reorganize Heap.
228      */

229     public Object JavaDoc next() throws ArrayIndexOutOfBoundsException JavaDoc {
230           if (num_entries<=0)
231             throw new ArrayIndexOutOfBoundsException JavaDoc("ExpireableCache heap is empty");
232
233         Object JavaDoc ret=keys[0];
234         keys[0]=keys[num_entries-1];
235         values[0]=values[num_entries-1];
236         num_entries--;
237
238         decrease(1);
239
240         return ret;
241     }
242
243
244     /**
245      * Remove an Object from the Heap.
246      * Unfortunately not (yet) of very good complexity since we are doing
247      * a simple linear search here.
248      * @param key The key to remove from the heap
249      */

250
251     public void remove (Object JavaDoc key) {
252         for (int i=0; i<num_entries; i++) {
253         if (key.equals(keys[i])) {
254             num_entries--;
255             int cur_pos=i+1;
256             keys[i]=keys[num_entries];
257             decrease(cur_pos);
258             break;
259         } // fi
260
} // next(i)
261
}
262
263     /**
264      * Lift an element in the heap structure
265      * Note that the cur_pos is actually one larger than the position in the array!
266      */

267     protected void increase(int cur_pos) {
268         while(cur_pos > 1 && values[cur_pos-1] < values[cur_pos/2-1]) {
269         Object JavaDoc tmp1=keys[cur_pos/2-1];
270                 keys[cur_pos/2-1]=keys[cur_pos-1];
271                 keys[cur_pos-1]=tmp1;
272         long tmp2=values[cur_pos/2-1];
273                 values[cur_pos/2-1]=values[cur_pos-1];
274                 values[cur_pos-1]=tmp2;
275         cur_pos /= 2;
276         } // wend
277
} // increase
278

279     /**
280      * Lower an element in the heap structure
281      * Note that the cur_pos is actually one larger than the position in the array!
282      */

283     protected void decrease(int cur_pos) {
284         while((cur_pos*2 <= num_entries && values[cur_pos-1] > values[cur_pos*2-1]) ||
285           (cur_pos*2+1 <=num_entries && values[cur_pos-1] > values[cur_pos*2])) {
286         int lesser_son;
287         if(cur_pos*2+1 <= num_entries) {
288             lesser_son=values[cur_pos*2-1]<values[cur_pos*2]?cur_pos*2:cur_pos*2+1;
289         } else {
290             lesser_son=cur_pos*2;
291         }
292         Object JavaDoc tmp1=keys[cur_pos-1];
293                 keys[cur_pos-1]=keys[lesser_son-1];
294                 keys[lesser_son-1]=tmp1;
295         long tmp2=values[cur_pos-1];
296                 values[cur_pos-1]=values[lesser_son-1];
297                 values[lesser_son-1]=tmp2;
298         cur_pos=lesser_son;
299         } // wend
300
} // decrease
301

302     }
303 } // ExpireableCache
304
Popular Tags