2
|
1 |
/*
|
5506
|
2 |
* Copyright (c) 1998, 2006, Oracle and/or its affiliates. All rights reserved.
|
2
|
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
|
5506
|
7 |
* published by the Free Software Foundation. Oracle designates this
|
2
|
8 |
* particular file as subject to the "Classpath" exception as provided
|
5506
|
9 |
* by Oracle in the LICENSE file that accompanied this code.
|
2
|
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 |
*
|
5506
|
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.
|
2
|
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 |
*/
|
|
103 |
|
|
104 |
|
|
105 |
public class SoftCache extends AbstractMap implements Map {
|
|
106 |
|
|
107 |
/* The basic idea of this implementation is to maintain an internal HashMap
|
|
108 |
that maps keys to soft references whose referents are the keys' values;
|
|
109 |
the various accessor methods dereference these soft references before
|
|
110 |
returning values. Because we don't have access to the innards of the
|
|
111 |
HashMap, each soft reference must contain the key that maps to it so
|
|
112 |
that the processQueue method can remove keys whose values have been
|
|
113 |
discarded. Thus the HashMap actually maps keys to instances of the
|
|
114 |
ValueCell class, which is a simple extension of the SoftReference class.
|
|
115 |
*/
|
|
116 |
|
|
117 |
|
|
118 |
static private class ValueCell extends SoftReference {
|
|
119 |
static private Object INVALID_KEY = new Object();
|
|
120 |
static private int dropped = 0;
|
|
121 |
private Object key;
|
|
122 |
|
|
123 |
private ValueCell(Object key, Object value, ReferenceQueue queue) {
|
|
124 |
super(value, queue);
|
|
125 |
this.key = key;
|
|
126 |
}
|
|
127 |
|
|
128 |
private static ValueCell create(Object key, Object value,
|
|
129 |
ReferenceQueue queue)
|
|
130 |
{
|
|
131 |
if (value == null) return null;
|
|
132 |
return new ValueCell(key, value, queue);
|
|
133 |
}
|
|
134 |
|
|
135 |
private static Object strip(Object val, boolean drop) {
|
|
136 |
if (val == null) return null;
|
|
137 |
ValueCell vc = (ValueCell)val;
|
|
138 |
Object o = vc.get();
|
|
139 |
if (drop) vc.drop();
|
|
140 |
return o;
|
|
141 |
}
|
|
142 |
|
|
143 |
private boolean isValid() {
|
|
144 |
return (key != INVALID_KEY);
|
|
145 |
}
|
|
146 |
|
|
147 |
private void drop() {
|
|
148 |
super.clear();
|
|
149 |
key = INVALID_KEY;
|
|
150 |
dropped++;
|
|
151 |
}
|
|
152 |
|
|
153 |
}
|
|
154 |
|
|
155 |
|
|
156 |
/* Hash table mapping keys to ValueCells */
|
|
157 |
private Map hash;
|
|
158 |
|
|
159 |
/* Reference queue for cleared ValueCells */
|
|
160 |
private ReferenceQueue queue = new ReferenceQueue();
|
|
161 |
|
|
162 |
|
|
163 |
/* Process any ValueCells that have been cleared and enqueued by the
|
|
164 |
garbage collector. This method should be invoked once by each public
|
|
165 |
mutator in this class. We don't invoke this method in public accessors
|
|
166 |
because that can lead to surprising ConcurrentModificationExceptions.
|
|
167 |
*/
|
|
168 |
private void processQueue() {
|
|
169 |
ValueCell vc;
|
|
170 |
while ((vc = (ValueCell)queue.poll()) != null) {
|
|
171 |
if (vc.isValid()) hash.remove(vc.key);
|
|
172 |
else ValueCell.dropped--;
|
|
173 |
}
|
|
174 |
}
|
|
175 |
|
|
176 |
|
|
177 |
/* -- Constructors -- */
|
|
178 |
|
|
179 |
/**
|
|
180 |
* Construct a new, empty <code>SoftCache</code> with the given
|
|
181 |
* initial capacity and the given load factor.
|
|
182 |
*
|
|
183 |
* @param initialCapacity The initial capacity of the cache
|
|
184 |
*
|
|
185 |
* @param loadFactor A number between 0.0 and 1.0
|
|
186 |
*
|
|
187 |
* @throws IllegalArgumentException If the initial capacity is less than
|
|
188 |
* or equal to zero, or if the load
|
|
189 |
* factor is less than zero
|
|
190 |
*/
|
|
191 |
public SoftCache(int initialCapacity, float loadFactor) {
|
|
192 |
hash = new HashMap(initialCapacity, loadFactor);
|
|
193 |
}
|
|
194 |
|
|
195 |
/**
|
|
196 |
* Construct a new, empty <code>SoftCache</code> with the given
|
|
197 |
* initial capacity and the default load factor.
|
|
198 |
*
|
|
199 |
* @param initialCapacity The initial capacity of the cache
|
|
200 |
*
|
|
201 |
* @throws IllegalArgumentException If the initial capacity is less than
|
|
202 |
* or equal to zero
|
|
203 |
*/
|
|
204 |
public SoftCache(int initialCapacity) {
|
|
205 |
hash = new HashMap(initialCapacity);
|
|
206 |
}
|
|
207 |
|
|
208 |
/**
|
|
209 |
* Construct a new, empty <code>SoftCache</code> with the default
|
|
210 |
* capacity and the default load factor.
|
|
211 |
*/
|
|
212 |
public SoftCache() {
|
|
213 |
hash = new HashMap();
|
|
214 |
}
|
|
215 |
|
|
216 |
|
|
217 |
/* -- Simple queries -- */
|
|
218 |
|
|
219 |
/**
|
|
220 |
* Return the number of key-value mappings in this cache. The time
|
|
221 |
* required by this operation is linear in the size of the map.
|
|
222 |
*/
|
|
223 |
public int size() {
|
|
224 |
return entrySet().size();
|
|
225 |
}
|
|
226 |
|
|
227 |
/**
|
|
228 |
* Return <code>true</code> if this cache contains no key-value mappings.
|
|
229 |
*/
|
|
230 |
public boolean isEmpty() {
|
|
231 |
return entrySet().isEmpty();
|
|
232 |
}
|
|
233 |
|
|
234 |
/**
|
|
235 |
* Return <code>true</code> if this cache contains a mapping for the
|
|
236 |
* specified key. If there is no mapping for the key, this method will not
|
|
237 |
* attempt to construct one by invoking the <code>fill</code> method.
|
|
238 |
*
|
|
239 |
* @param key The key whose presence in the cache is to be tested
|
|
240 |
*/
|
|
241 |
public boolean containsKey(Object key) {
|
|
242 |
return ValueCell.strip(hash.get(key), false) != null;
|
|
243 |
}
|
|
244 |
|
|
245 |
|
|
246 |
/* -- Lookup and modification operations -- */
|
|
247 |
|
|
248 |
/**
|
|
249 |
* Create a value object for the given <code>key</code>. This method is
|
|
250 |
* invoked by the <code>get</code> method when there is no entry for
|
|
251 |
* <code>key</code>. If this method returns a non-<code>null</code> value,
|
|
252 |
* then the cache will be updated to map <code>key</code> to that value,
|
|
253 |
* and that value will be returned by the <code>get</code> method.
|
|
254 |
*
|
|
255 |
* <p> The default implementation of this method simply returns
|
|
256 |
* <code>null</code> for every <code>key</code> value. A subclass may
|
|
257 |
* override this method to provide more useful behavior.
|
|
258 |
*
|
|
259 |
* @param key The key for which a value is to be computed
|
|
260 |
*
|
|
261 |
* @return A value for <code>key</code>, or <code>null</code> if one
|
|
262 |
* could not be computed
|
|
263 |
* @see #get
|
|
264 |
*/
|
|
265 |
protected Object fill(Object key) {
|
|
266 |
return null;
|
|
267 |
}
|
|
268 |
|
|
269 |
/**
|
|
270 |
* Return the value to which this cache maps the specified
|
|
271 |
* <code>key</code>. If the cache does not presently contain a value for
|
|
272 |
* this key, then invoke the <code>fill</code> method in an attempt to
|
|
273 |
* compute such a value. If that method returns a non-<code>null</code>
|
|
274 |
* value, then update the cache and return the new value. Otherwise,
|
|
275 |
* return <code>null</code>.
|
|
276 |
*
|
|
277 |
* <p> Note that because this method may update the cache, it is considered
|
|
278 |
* a mutator and may cause <code>ConcurrentModificationException</code>s to
|
|
279 |
* be thrown if invoked while an iterator is in use.
|
|
280 |
*
|
|
281 |
* @param key The key whose associated value, if any, is to be returned
|
|
282 |
*
|
|
283 |
* @see #fill
|
|
284 |
*/
|
|
285 |
public Object get(Object key) {
|
|
286 |
processQueue();
|
|
287 |
Object v = hash.get(key);
|
|
288 |
if (v == null) {
|
|
289 |
v = fill(key);
|
|
290 |
if (v != null) {
|
|
291 |
hash.put(key, ValueCell.create(key, v, queue));
|
|
292 |
return v;
|
|
293 |
}
|
|
294 |
}
|
|
295 |
return ValueCell.strip(v, false);
|
|
296 |
}
|
|
297 |
|
|
298 |
/**
|
|
299 |
* Update this cache so that the given <code>key</code> maps to the given
|
|
300 |
* <code>value</code>. If the cache previously contained a mapping for
|
|
301 |
* <code>key</code> then that mapping is replaced and the old value is
|
|
302 |
* returned.
|
|
303 |
*
|
|
304 |
* @param key The key that is to be mapped to the given
|
|
305 |
* <code>value</code>
|
|
306 |
* @param value The value to which the given <code>key</code> is to be
|
|
307 |
* mapped
|
|
308 |
*
|
|
309 |
* @return The previous value to which this key was mapped, or
|
|
310 |
* <code>null</code> if if there was no mapping for the key
|
|
311 |
*/
|
|
312 |
public Object put(Object key, Object value) {
|
|
313 |
processQueue();
|
|
314 |
ValueCell vc = ValueCell.create(key, value, queue);
|
|
315 |
return ValueCell.strip(hash.put(key, vc), true);
|
|
316 |
}
|
|
317 |
|
|
318 |
/**
|
|
319 |
* Remove the mapping for the given <code>key</code> from this cache, if
|
|
320 |
* present.
|
|
321 |
*
|
|
322 |
* @param key The key whose mapping is to be removed
|
|
323 |
*
|
|
324 |
* @return The value to which this key was mapped, or <code>null</code> if
|
|
325 |
* there was no mapping for the key
|
|
326 |
*/
|
|
327 |
public Object remove(Object key) {
|
|
328 |
processQueue();
|
|
329 |
return ValueCell.strip(hash.remove(key), true);
|
|
330 |
}
|
|
331 |
|
|
332 |
/**
|
|
333 |
* Remove all mappings from this cache.
|
|
334 |
*/
|
|
335 |
public void clear() {
|
|
336 |
processQueue();
|
|
337 |
hash.clear();
|
|
338 |
}
|
|
339 |
|
|
340 |
|
|
341 |
/* -- Views -- */
|
|
342 |
|
|
343 |
private static boolean valEquals(Object o1, Object o2) {
|
|
344 |
return (o1 == null) ? (o2 == null) : o1.equals(o2);
|
|
345 |
}
|
|
346 |
|
|
347 |
|
|
348 |
/* Internal class for entries.
|
|
349 |
Because it uses SoftCache.this.queue, this class cannot be static.
|
|
350 |
*/
|
|
351 |
private class Entry implements Map.Entry {
|
|
352 |
private Map.Entry ent;
|
|
353 |
private Object value; /* Strong reference to value, to prevent the GC
|
|
354 |
from flushing the value while this Entry
|
|
355 |
exists */
|
|
356 |
|
|
357 |
Entry(Map.Entry ent, Object value) {
|
|
358 |
this.ent = ent;
|
|
359 |
this.value = value;
|
|
360 |
}
|
|
361 |
|
|
362 |
public Object getKey() {
|
|
363 |
return ent.getKey();
|
|
364 |
}
|
|
365 |
|
|
366 |
public Object getValue() {
|
|
367 |
return value;
|
|
368 |
}
|
|
369 |
|
|
370 |
public Object setValue(Object value) {
|
|
371 |
return ent.setValue(ValueCell.create(ent.getKey(), value, queue));
|
|
372 |
}
|
|
373 |
|
|
374 |
public boolean equals(Object o) {
|
|
375 |
if (! (o instanceof Map.Entry)) return false;
|
|
376 |
Map.Entry e = (Map.Entry)o;
|
|
377 |
return (valEquals(ent.getKey(), e.getKey())
|
|
378 |
&& valEquals(value, e.getValue()));
|
|
379 |
}
|
|
380 |
|
|
381 |
public int hashCode() {
|
|
382 |
Object k;
|
|
383 |
return ((((k = getKey()) == null) ? 0 : k.hashCode())
|
|
384 |
^ ((value == null) ? 0 : value.hashCode()));
|
|
385 |
}
|
|
386 |
|
|
387 |
}
|
|
388 |
|
|
389 |
|
|
390 |
/* Internal class for entry sets */
|
|
391 |
private class EntrySet extends AbstractSet {
|
|
392 |
Set hashEntries = hash.entrySet();
|
|
393 |
|
|
394 |
public Iterator iterator() {
|
|
395 |
|
|
396 |
return new Iterator() {
|
|
397 |
Iterator hashIterator = hashEntries.iterator();
|
|
398 |
Entry next = null;
|
|
399 |
|
|
400 |
public boolean hasNext() {
|
|
401 |
while (hashIterator.hasNext()) {
|
|
402 |
Map.Entry ent = (Map.Entry)hashIterator.next();
|
|
403 |
ValueCell vc = (ValueCell)ent.getValue();
|
|
404 |
Object v = null;
|
|
405 |
if ((vc != null) && ((v = vc.get()) == null)) {
|
|
406 |
/* Value has been flushed by GC */
|
|
407 |
continue;
|
|
408 |
}
|
|
409 |
next = new Entry(ent, v);
|
|
410 |
return true;
|
|
411 |
}
|
|
412 |
return false;
|
|
413 |
}
|
|
414 |
|
|
415 |
public Object next() {
|
|
416 |
if ((next == null) && !hasNext())
|
|
417 |
throw new NoSuchElementException();
|
|
418 |
Entry e = next;
|
|
419 |
next = null;
|
|
420 |
return e;
|
|
421 |
}
|
|
422 |
|
|
423 |
public void remove() {
|
|
424 |
hashIterator.remove();
|
|
425 |
}
|
|
426 |
|
|
427 |
};
|
|
428 |
}
|
|
429 |
|
|
430 |
public boolean isEmpty() {
|
|
431 |
return !(iterator().hasNext());
|
|
432 |
}
|
|
433 |
|
|
434 |
public int size() {
|
|
435 |
int j = 0;
|
|
436 |
for (Iterator i = iterator(); i.hasNext(); i.next()) j++;
|
|
437 |
return j;
|
|
438 |
}
|
|
439 |
|
|
440 |
public boolean remove(Object o) {
|
|
441 |
processQueue();
|
|
442 |
if (o instanceof Entry) return hashEntries.remove(((Entry)o).ent);
|
|
443 |
else return false;
|
|
444 |
}
|
|
445 |
|
|
446 |
}
|
|
447 |
|
|
448 |
|
|
449 |
private Set entrySet = null;
|
|
450 |
|
|
451 |
/**
|
|
452 |
* Return a <code>Set</code> view of the mappings in this cache.
|
|
453 |
*/
|
|
454 |
public Set entrySet() {
|
|
455 |
if (entrySet == null) entrySet = new EntrySet();
|
|
456 |
return entrySet;
|
|
457 |
}
|
|
458 |
|
|
459 |
}
|