1 /* |
|
2 * Copyright (c) 1998, 2014, Oracle and/or its affiliates. All rights reserved. |
|
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
|
4 * |
|
5 * This code is free software; you can redistribute it and/or modify it |
|
6 * under the terms of the GNU General Public License version 2 only, as |
|
7 * published by the Free Software Foundation. Oracle designates this |
|
8 * particular file as subject to the "Classpath" exception as provided |
|
9 * by Oracle in the LICENSE file that accompanied this code. |
|
10 * |
|
11 * This code is distributed in the hope that it will be useful, but WITHOUT |
|
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
|
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
|
14 * version 2 for more details (a copy is included in the LICENSE file that |
|
15 * accompanied this code). |
|
16 * |
|
17 * You should have received a copy of the GNU General Public License version |
|
18 * 2 along with this work; if not, write to the Free Software Foundation, |
|
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
|
20 * |
|
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
22 * or visit www.oracle.com if you need additional information or have any |
|
23 * questions. |
|
24 */ |
|
25 |
|
26 package sun.misc; |
|
27 |
|
28 import java.lang.ref.SoftReference; |
|
29 import java.lang.ref.ReferenceQueue; |
|
30 |
|
31 import java.util.Iterator; |
|
32 import java.util.Map; |
|
33 import java.util.AbstractMap; |
|
34 import java.util.HashMap; |
|
35 import java.util.Set; |
|
36 import java.util.AbstractSet; |
|
37 import java.util.NoSuchElementException; |
|
38 |
|
39 |
|
40 /** |
|
41 * A memory-sensitive implementation of the <code>Map</code> interface. |
|
42 * |
|
43 * <p> A <code>SoftCache</code> object uses {@link java.lang.ref.SoftReference |
|
44 * soft references} to implement a memory-sensitive hash map. If the garbage |
|
45 * collector determines at a certain point in time that a value object in a |
|
46 * <code>SoftCache</code> entry is no longer strongly reachable, then it may |
|
47 * remove that entry in order to release the memory occupied by the value |
|
48 * object. All <code>SoftCache</code> objects are guaranteed to be completely |
|
49 * cleared before the virtual machine will throw an |
|
50 * <code>OutOfMemoryError</code>. Because of this automatic clearing feature, |
|
51 * the behavior of this class is somewhat different from that of other |
|
52 * <code>Map</code> implementations. |
|
53 * |
|
54 * <p> Both null values and the null key are supported. This class has the |
|
55 * same performance characteristics as the <code>HashMap</code> class, and has |
|
56 * the same efficiency parameters of <em>initial capacity</em> and <em>load |
|
57 * factor</em>. |
|
58 * |
|
59 * <p> Like most collection classes, this class is not synchronized. A |
|
60 * synchronized <code>SoftCache</code> may be constructed using the |
|
61 * <code>Collections.synchronizedMap</code> method. |
|
62 * |
|
63 * <p> In typical usage this class will be subclassed and the <code>fill</code> |
|
64 * method will be overridden. When the <code>get</code> method is invoked on a |
|
65 * key for which there is no mapping in the cache, it will in turn invoke the |
|
66 * <code>fill</code> method on that key in an attempt to construct a |
|
67 * corresponding value. If the <code>fill</code> method returns such a value |
|
68 * then the cache will be updated and the new value will be returned. Thus, |
|
69 * for example, a simple URL-content cache can be constructed as follows: |
|
70 * |
|
71 * <pre> |
|
72 * public class URLCache extends SoftCache { |
|
73 * protected Object fill(Object key) { |
|
74 * return ((URL)key).getContent(); |
|
75 * } |
|
76 * } |
|
77 * </pre> |
|
78 * |
|
79 * <p> The behavior of the <code>SoftCache</code> class depends in part upon |
|
80 * the actions of the garbage collector, so several familiar (though not |
|
81 * required) <code>Map</code> invariants do not hold for this class. <p> |
|
82 * Because entries are removed from a <code>SoftCache</code> in response to |
|
83 * dynamic advice from the garbage collector, a <code>SoftCache</code> may |
|
84 * behave as though an unknown thread is silently removing entries. In |
|
85 * particular, even if you synchronize on a <code>SoftCache</code> instance and |
|
86 * invoke none of its mutator methods, it is possible for the <code>size</code> |
|
87 * method to return smaller values over time, for the <code>isEmpty</code> |
|
88 * method to return <code>false</code> and then <code>true</code>, for the |
|
89 * <code>containsKey</code> method to return <code>true</code> and later |
|
90 * <code>false</code> for a given key, for the <code>get</code> method to |
|
91 * return a value for a given key but later return <code>null</code>, for the |
|
92 * <code>put</code> method to return <code>null</code> and the |
|
93 * <code>remove</code> method to return <code>false</code> for a key that |
|
94 * previously appeared to be in the map, and for successive examinations of the |
|
95 * key set, the value set, and the entry set to yield successively smaller |
|
96 * numbers of elements. |
|
97 * |
|
98 * @author Mark Reinhold |
|
99 * @since 1.2 |
|
100 * @see java.util.HashMap |
|
101 * @see java.lang.ref.SoftReference |
|
102 * @deprecated No direct replacement; {@link java.util.WeakHashMap} |
|
103 * addresses a related by different use-case. |
|
104 */ |
|
105 |
|
106 @Deprecated |
|
107 public class SoftCache extends AbstractMap<Object, Object> implements Map<Object, Object> { |
|
108 |
|
109 /* The basic idea of this implementation is to maintain an internal HashMap |
|
110 that maps keys to soft references whose referents are the keys' values; |
|
111 the various accessor methods dereference these soft references before |
|
112 returning values. Because we don't have access to the innards of the |
|
113 HashMap, each soft reference must contain the key that maps to it so |
|
114 that the processQueue method can remove keys whose values have been |
|
115 discarded. Thus the HashMap actually maps keys to instances of the |
|
116 ValueCell class, which is a simple extension of the SoftReference class. |
|
117 */ |
|
118 |
|
119 |
|
120 private static class ValueCell extends SoftReference<Object> { |
|
121 private static Object INVALID_KEY = new Object(); |
|
122 private static int dropped = 0; |
|
123 private Object key; |
|
124 |
|
125 private ValueCell(Object key, Object value, ReferenceQueue<Object> queue) { |
|
126 super(value, queue); |
|
127 this.key = key; |
|
128 } |
|
129 |
|
130 private static ValueCell create(Object key, Object value, |
|
131 ReferenceQueue<Object> queue) |
|
132 { |
|
133 if (value == null) return null; |
|
134 return new ValueCell(key, value, queue); |
|
135 } |
|
136 |
|
137 private static Object strip(Object val, boolean drop) { |
|
138 if (val == null) return null; |
|
139 ValueCell vc = (ValueCell)val; |
|
140 Object o = vc.get(); |
|
141 if (drop) vc.drop(); |
|
142 return o; |
|
143 } |
|
144 |
|
145 private boolean isValid() { |
|
146 return (key != INVALID_KEY); |
|
147 } |
|
148 |
|
149 private void drop() { |
|
150 super.clear(); |
|
151 key = INVALID_KEY; |
|
152 dropped++; |
|
153 } |
|
154 |
|
155 } |
|
156 |
|
157 |
|
158 /* Hash table mapping keys to ValueCells */ |
|
159 private Map<Object, Object> hash; |
|
160 |
|
161 /* Reference queue for cleared ValueCells */ |
|
162 private ReferenceQueue<Object> queue = new ReferenceQueue<>(); |
|
163 |
|
164 |
|
165 /* Process any ValueCells that have been cleared and enqueued by the |
|
166 garbage collector. This method should be invoked once by each public |
|
167 mutator in this class. We don't invoke this method in public accessors |
|
168 because that can lead to surprising ConcurrentModificationExceptions. |
|
169 */ |
|
170 private void processQueue() { |
|
171 ValueCell vc; |
|
172 while ((vc = (ValueCell)queue.poll()) != null) { |
|
173 if (vc.isValid()) hash.remove(vc.key); |
|
174 else ValueCell.dropped--; |
|
175 } |
|
176 } |
|
177 |
|
178 |
|
179 /* -- Constructors -- */ |
|
180 |
|
181 /** |
|
182 * Construct a new, empty <code>SoftCache</code> with the given |
|
183 * initial capacity and the given load factor. |
|
184 * |
|
185 * @param initialCapacity The initial capacity of the cache |
|
186 * |
|
187 * @param loadFactor A number between 0.0 and 1.0 |
|
188 * |
|
189 * @throws IllegalArgumentException If the initial capacity is less than |
|
190 * or equal to zero, or if the load |
|
191 * factor is less than zero |
|
192 */ |
|
193 public SoftCache(int initialCapacity, float loadFactor) { |
|
194 hash = new HashMap<>(initialCapacity, loadFactor); |
|
195 } |
|
196 |
|
197 /** |
|
198 * Construct a new, empty <code>SoftCache</code> with the given |
|
199 * initial capacity and the default load factor. |
|
200 * |
|
201 * @param initialCapacity The initial capacity of the cache |
|
202 * |
|
203 * @throws IllegalArgumentException If the initial capacity is less than |
|
204 * or equal to zero |
|
205 */ |
|
206 public SoftCache(int initialCapacity) { |
|
207 hash = new HashMap<>(initialCapacity); |
|
208 } |
|
209 |
|
210 /** |
|
211 * Construct a new, empty <code>SoftCache</code> with the default |
|
212 * capacity and the default load factor. |
|
213 */ |
|
214 public SoftCache() { |
|
215 hash = new HashMap<>(); |
|
216 } |
|
217 |
|
218 |
|
219 /* -- Simple queries -- */ |
|
220 |
|
221 /** |
|
222 * Return the number of key-value mappings in this cache. The time |
|
223 * required by this operation is linear in the size of the map. |
|
224 */ |
|
225 public int size() { |
|
226 return entrySet().size(); |
|
227 } |
|
228 |
|
229 /** |
|
230 * Return <code>true</code> if this cache contains no key-value mappings. |
|
231 */ |
|
232 public boolean isEmpty() { |
|
233 return entrySet().isEmpty(); |
|
234 } |
|
235 |
|
236 /** |
|
237 * Return <code>true</code> if this cache contains a mapping for the |
|
238 * specified key. If there is no mapping for the key, this method will not |
|
239 * attempt to construct one by invoking the <code>fill</code> method. |
|
240 * |
|
241 * @param key The key whose presence in the cache is to be tested |
|
242 */ |
|
243 public boolean containsKey(Object key) { |
|
244 return ValueCell.strip(hash.get(key), false) != null; |
|
245 } |
|
246 |
|
247 |
|
248 /* -- Lookup and modification operations -- */ |
|
249 |
|
250 /** |
|
251 * Create a value object for the given <code>key</code>. This method is |
|
252 * invoked by the <code>get</code> method when there is no entry for |
|
253 * <code>key</code>. If this method returns a non-<code>null</code> value, |
|
254 * then the cache will be updated to map <code>key</code> to that value, |
|
255 * and that value will be returned by the <code>get</code> method. |
|
256 * |
|
257 * <p> The default implementation of this method simply returns |
|
258 * <code>null</code> for every <code>key</code> value. A subclass may |
|
259 * override this method to provide more useful behavior. |
|
260 * |
|
261 * @param key The key for which a value is to be computed |
|
262 * |
|
263 * @return A value for <code>key</code>, or <code>null</code> if one |
|
264 * could not be computed |
|
265 * @see #get |
|
266 */ |
|
267 protected Object fill(Object key) { |
|
268 return null; |
|
269 } |
|
270 |
|
271 /** |
|
272 * Return the value to which this cache maps the specified |
|
273 * <code>key</code>. If the cache does not presently contain a value for |
|
274 * this key, then invoke the <code>fill</code> method in an attempt to |
|
275 * compute such a value. If that method returns a non-<code>null</code> |
|
276 * value, then update the cache and return the new value. Otherwise, |
|
277 * return <code>null</code>. |
|
278 * |
|
279 * <p> Note that because this method may update the cache, it is considered |
|
280 * a mutator and may cause <code>ConcurrentModificationException</code>s to |
|
281 * be thrown if invoked while an iterator is in use. |
|
282 * |
|
283 * @param key The key whose associated value, if any, is to be returned |
|
284 * |
|
285 * @see #fill |
|
286 */ |
|
287 public Object get(Object key) { |
|
288 processQueue(); |
|
289 Object v = hash.get(key); |
|
290 if (v == null) { |
|
291 v = fill(key); |
|
292 if (v != null) { |
|
293 hash.put(key, ValueCell.create(key, v, queue)); |
|
294 return v; |
|
295 } |
|
296 } |
|
297 return ValueCell.strip(v, false); |
|
298 } |
|
299 |
|
300 /** |
|
301 * Update this cache so that the given <code>key</code> maps to the given |
|
302 * <code>value</code>. If the cache previously contained a mapping for |
|
303 * <code>key</code> then that mapping is replaced and the old value is |
|
304 * returned. |
|
305 * |
|
306 * @param key The key that is to be mapped to the given |
|
307 * <code>value</code> |
|
308 * @param value The value to which the given <code>key</code> is to be |
|
309 * mapped |
|
310 * |
|
311 * @return The previous value to which this key was mapped, or |
|
312 * <code>null</code> if there was no mapping for the key |
|
313 */ |
|
314 public Object put(Object key, Object value) { |
|
315 processQueue(); |
|
316 ValueCell vc = ValueCell.create(key, value, queue); |
|
317 return ValueCell.strip(hash.put(key, vc), true); |
|
318 } |
|
319 |
|
320 /** |
|
321 * Remove the mapping for the given <code>key</code> from this cache, if |
|
322 * present. |
|
323 * |
|
324 * @param key The key whose mapping is to be removed |
|
325 * |
|
326 * @return The value to which this key was mapped, or <code>null</code> if |
|
327 * there was no mapping for the key |
|
328 */ |
|
329 public Object remove(Object key) { |
|
330 processQueue(); |
|
331 return ValueCell.strip(hash.remove(key), true); |
|
332 } |
|
333 |
|
334 /** |
|
335 * Remove all mappings from this cache. |
|
336 */ |
|
337 public void clear() { |
|
338 processQueue(); |
|
339 hash.clear(); |
|
340 } |
|
341 |
|
342 |
|
343 /* -- Views -- */ |
|
344 |
|
345 private static boolean valEquals(Object o1, Object o2) { |
|
346 return (o1 == null) ? (o2 == null) : o1.equals(o2); |
|
347 } |
|
348 |
|
349 |
|
350 /* Internal class for entries. |
|
351 Because it uses SoftCache.this.queue, this class cannot be static. |
|
352 */ |
|
353 private class Entry implements Map.Entry<Object, Object> { |
|
354 private Map.Entry<Object, Object> ent; |
|
355 private Object value; /* Strong reference to value, to prevent the GC |
|
356 from flushing the value while this Entry |
|
357 exists */ |
|
358 |
|
359 Entry(Map.Entry<Object, Object> ent, Object value) { |
|
360 this.ent = ent; |
|
361 this.value = value; |
|
362 } |
|
363 |
|
364 public Object getKey() { |
|
365 return ent.getKey(); |
|
366 } |
|
367 |
|
368 public Object getValue() { |
|
369 return value; |
|
370 } |
|
371 |
|
372 public Object setValue(Object value) { |
|
373 return ent.setValue(ValueCell.create(ent.getKey(), value, queue)); |
|
374 } |
|
375 |
|
376 @SuppressWarnings("unchecked") |
|
377 public boolean equals(Object o) { |
|
378 if (! (o instanceof Map.Entry)) return false; |
|
379 Map.Entry<Object, Object> e = (Map.Entry<Object, Object>)o; |
|
380 return (valEquals(ent.getKey(), e.getKey()) |
|
381 && valEquals(value, e.getValue())); |
|
382 } |
|
383 |
|
384 public int hashCode() { |
|
385 Object k; |
|
386 return ((((k = getKey()) == null) ? 0 : k.hashCode()) |
|
387 ^ ((value == null) ? 0 : value.hashCode())); |
|
388 } |
|
389 |
|
390 } |
|
391 |
|
392 |
|
393 /* Internal class for entry sets */ |
|
394 private class EntrySet extends AbstractSet<Map.Entry<Object, Object>> { |
|
395 Set<Map.Entry<Object, Object>> hashEntries = hash.entrySet(); |
|
396 |
|
397 public Iterator<Map.Entry<Object, Object>> iterator() { |
|
398 |
|
399 return new Iterator<Map.Entry<Object, Object>>() { |
|
400 Iterator<Map.Entry<Object, Object>> hashIterator = hashEntries.iterator(); |
|
401 Entry next = null; |
|
402 |
|
403 public boolean hasNext() { |
|
404 while (hashIterator.hasNext()) { |
|
405 Map.Entry<Object, Object> ent = hashIterator.next(); |
|
406 ValueCell vc = (ValueCell)ent.getValue(); |
|
407 Object v = null; |
|
408 if ((vc != null) && ((v = vc.get()) == null)) { |
|
409 /* Value has been flushed by GC */ |
|
410 continue; |
|
411 } |
|
412 next = new Entry(ent, v); |
|
413 return true; |
|
414 } |
|
415 return false; |
|
416 } |
|
417 |
|
418 public Map.Entry<Object, Object> next() { |
|
419 if ((next == null) && !hasNext()) |
|
420 throw new NoSuchElementException(); |
|
421 Entry e = next; |
|
422 next = null; |
|
423 return e; |
|
424 } |
|
425 |
|
426 public void remove() { |
|
427 hashIterator.remove(); |
|
428 } |
|
429 |
|
430 }; |
|
431 } |
|
432 |
|
433 public boolean isEmpty() { |
|
434 return !(iterator().hasNext()); |
|
435 } |
|
436 |
|
437 public int size() { |
|
438 int j = 0; |
|
439 for (Iterator<Map.Entry<Object, Object>> i = iterator(); i.hasNext(); i.next()) j++; |
|
440 return j; |
|
441 } |
|
442 |
|
443 public boolean remove(Object o) { |
|
444 processQueue(); |
|
445 if (o instanceof Entry) return hashEntries.remove(((Entry)o).ent); |
|
446 else return false; |
|
447 } |
|
448 |
|
449 } |
|
450 |
|
451 |
|
452 private Set<Map.Entry<Object, Object>> entrySet = null; |
|
453 |
|
454 /** |
|
455 * Return a <code>Set</code> view of the mappings in this cache. |
|
456 */ |
|
457 public Set<Map.Entry<Object, Object>> entrySet() { |
|
458 if (entrySet == null) entrySet = new EntrySet(); |
|
459 return entrySet; |
|
460 } |
|
461 |
|
462 } |
|