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     static private class ValueCell extends SoftReference<Object> {
 121         static private Object INVALID_KEY = new Object();
 122         static private 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 }