1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48 package jdbm.helper;
49
50 import java.util.Enumeration;
51 import java.util.Hashtable;
52 import java.util.Vector;
53
54
55
56
57
58
59
60
61
62
63 public class MRU implements CachePolicy {
64
65
66 Hashtable _hash = new Hashtable();
67
68
69
70
71 int _max;
72
73
74
75
76
77 CacheEntry _first;
78
79
80
81
82
83 CacheEntry _last;
84
85
86
87
88
89 Vector listeners = new Vector();
90
91
92
93
94
95 public MRU(int max) {
96 if (max <= 0) {
97 throw new IllegalArgumentException("MRU cache must contain at least one entry");
98 }
99 _max = max;
100 }
101
102
103
104
105
106 public void put(Object key, Object value) throws CacheEvictionException {
107 CacheEntry entry = (CacheEntry)_hash.get(key);
108 if (entry != null) {
109 entry.setValue(value);
110 touchEntry(entry);
111 } else {
112
113 if (_hash.size() == _max) {
114
115 entry = purgeEntry();
116 entry.setKey(key);
117 entry.setValue(value);
118 } else {
119 entry = new CacheEntry(key, value);
120 }
121 addEntry(entry);
122 _hash.put(entry.getKey(), entry);
123 }
124 }
125
126
127
128
129
130 public Object get(Object key) {
131 CacheEntry entry = (CacheEntry)_hash.get(key);
132 if (entry != null) {
133 touchEntry(entry);
134 return entry.getValue();
135 } else {
136 return null;
137 }
138 }
139
140
141
142
143
144 public void remove(Object key) {
145 CacheEntry entry = (CacheEntry)_hash.get(key);
146 if (entry != null) {
147 removeEntry(entry);
148 _hash.remove(entry.getKey());
149 }
150 }
151
152
153
154
155
156 public void removeAll() {
157 _hash = new Hashtable();
158 _first = null;
159 _last = null;
160 }
161
162
163
164
165
166 public Enumeration elements() {
167 return new MRUEnumeration(_hash.elements());
168 }
169
170
171
172
173
174
175 public void addListener(CachePolicyListener listener) {
176 if (listener == null) {
177 throw new IllegalArgumentException("Cannot add null listener.");
178 }
179 if ( ! listeners.contains(listener)) {
180 listeners.addElement(listener);
181 }
182 }
183
184
185
186
187
188
189 public void removeListener(CachePolicyListener listener) {
190 listeners.removeElement(listener);
191 }
192
193
194
195
196 protected void addEntry(CacheEntry entry) {
197 if (_first == null) {
198 _first = entry;
199 _last = entry;
200 } else {
201 _last.setNext(entry);
202 entry.setPrevious(_last);
203 _last = entry;
204 }
205 }
206
207
208
209
210
211 protected void removeEntry(CacheEntry entry) {
212 if (entry == _first) {
213 _first = entry.getNext();
214 }
215 if (_last == entry) {
216 _last = entry.getPrevious();
217 }
218 CacheEntry previous = entry.getPrevious();
219 CacheEntry next = entry.getNext();
220 if (previous != null) {
221 previous.setNext(next);
222 }
223 if (next != null) {
224 next.setPrevious(previous);
225 }
226 entry.setPrevious(null);
227 entry.setNext(null);
228 }
229
230
231
232
233 protected void touchEntry(CacheEntry entry) {
234 if (_last == entry) {
235 return;
236 }
237 removeEntry(entry);
238 addEntry(entry);
239 }
240
241
242
243
244
245
246 protected CacheEntry purgeEntry() throws CacheEvictionException {
247 CacheEntry entry = _first;
248
249
250
251
252 CachePolicyListener listener;
253 for (int i=0; i<listeners.size(); i++) {
254 listener = (CachePolicyListener)listeners.elementAt(i);
255 listener.cacheObjectEvicted(entry.getValue());
256 }
257
258 removeEntry(entry);
259 _hash.remove(entry.getKey());
260
261 entry.setValue(null);
262 return entry;
263 }
264
265 }
266
267
268
269
270 class CacheEntry {
271 private Object _key;
272 private Object _value;
273
274 private CacheEntry _previous;
275 private CacheEntry _next;
276
277 CacheEntry(Object key, Object value) {
278 _key = key;
279 _value = value;
280 }
281
282 Object getKey() {
283 return _key;
284 }
285
286 void setKey(Object obj) {
287 _key = obj;
288 }
289
290 Object getValue() {
291 return _value;
292 }
293
294 void setValue(Object obj) {
295 _value = obj;
296 }
297
298 CacheEntry getPrevious() {
299 return _previous;
300 }
301
302 void setPrevious(CacheEntry entry) {
303 _previous = entry;
304 }
305
306 CacheEntry getNext() {
307 return _next;
308 }
309
310 void setNext(CacheEntry entry) {
311 _next = entry;
312 }
313 }
314
315
316
317
318
319 class MRUEnumeration implements Enumeration {
320 Enumeration _enum;
321
322 MRUEnumeration(Enumeration enume) {
323 _enum = enume;
324 }
325
326 public boolean hasMoreElements() {
327 return _enum.hasMoreElements();
328 }
329
330 public Object nextElement() {
331 CacheEntry entry = (CacheEntry)_enum.nextElement();
332 return entry.getValue();
333 }
334 }