Save This Page
Home » openjdk-7 » sun » misc » [javadoc | source]
    1   /*
    2    * Copyright (c) 1998, 2006, 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    */
  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   }

Save This Page
Home » openjdk-7 » sun » misc » [javadoc | source]