J. Duke | 319a3b9 | 2007-12-01 00:00:00 +0000 | [diff] [blame^] | 1 | /* |
| 2 | * Copyright 1998-2006 Sun Microsystems, Inc. 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. Sun designates this |
| 8 | * particular file as subject to the "Classpath" exception as provided |
| 9 | * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
| 22 | * CA 95054 USA or visit www.sun.com if you need additional information or |
| 23 | * have any 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 | */ |
| 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 | } |