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 }