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 }