0N/A/*
2362N/A * Copyright (c) 1998, 2006, Oracle and/or its affiliates. All rights reserved.
0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0N/A *
0N/A * This code is free software; you can redistribute it and/or modify it
0N/A * under the terms of the GNU General Public License version 2 only, as
2362N/A * published by the Free Software Foundation. Oracle designates this
0N/A * particular file as subject to the "Classpath" exception as provided
2362N/A * by Oracle in the LICENSE file that accompanied this code.
0N/A *
0N/A * This code is distributed in the hope that it will be useful, but WITHOUT
0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0N/A * version 2 for more details (a copy is included in the LICENSE file that
0N/A * accompanied this code).
0N/A *
0N/A * You should have received a copy of the GNU General Public License version
0N/A * 2 along with this work; if not, write to the Free Software Foundation,
0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0N/A *
2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
2362N/A * or visit www.oracle.com if you need additional information or have any
2362N/A * questions.
0N/A */
0N/A
0N/Apackage sun.misc;
0N/A
0N/Aimport java.lang.ref.SoftReference;
0N/Aimport java.lang.ref.ReferenceQueue;
0N/A
0N/Aimport java.util.Iterator;
0N/Aimport java.util.Map;
0N/Aimport java.util.AbstractMap;
0N/Aimport java.util.HashMap;
0N/Aimport java.util.Set;
0N/Aimport java.util.AbstractSet;
0N/Aimport java.util.NoSuchElementException;
0N/A
0N/A
0N/A/**
0N/A * A memory-sensitive implementation of the <code>Map</code> interface.
0N/A *
0N/A * <p> A <code>SoftCache</code> object uses {@link java.lang.ref.SoftReference
0N/A * soft references} to implement a memory-sensitive hash map. If the garbage
0N/A * collector determines at a certain point in time that a value object in a
0N/A * <code>SoftCache</code> entry is no longer strongly reachable, then it may
0N/A * remove that entry in order to release the memory occupied by the value
0N/A * object. All <code>SoftCache</code> objects are guaranteed to be completely
0N/A * cleared before the virtual machine will throw an
0N/A * <code>OutOfMemoryError</code>. Because of this automatic clearing feature,
0N/A * the behavior of this class is somewhat different from that of other
0N/A * <code>Map</code> implementations.
0N/A *
0N/A * <p> Both null values and the null key are supported. This class has the
0N/A * same performance characteristics as the <code>HashMap</code> class, and has
0N/A * the same efficiency parameters of <em>initial capacity</em> and <em>load
0N/A * factor</em>.
0N/A *
0N/A * <p> Like most collection classes, this class is not synchronized. A
0N/A * synchronized <code>SoftCache</code> may be constructed using the
0N/A * <code>Collections.synchronizedMap</code> method.
0N/A *
0N/A * <p> In typical usage this class will be subclassed and the <code>fill</code>
0N/A * method will be overridden. When the <code>get</code> method is invoked on a
0N/A * key for which there is no mapping in the cache, it will in turn invoke the
0N/A * <code>fill</code> method on that key in an attempt to construct a
0N/A * corresponding value. If the <code>fill</code> method returns such a value
0N/A * then the cache will be updated and the new value will be returned. Thus,
0N/A * for example, a simple URL-content cache can be constructed as follows:
0N/A *
0N/A * <pre>
0N/A * public class URLCache extends SoftCache {
0N/A * protected Object fill(Object key) {
0N/A * return ((URL)key).getContent();
0N/A * }
0N/A * }
0N/A * </pre>
0N/A *
0N/A * <p> The behavior of the <code>SoftCache</code> class depends in part upon
0N/A * the actions of the garbage collector, so several familiar (though not
0N/A * required) <code>Map</code> invariants do not hold for this class. <p>
0N/A * Because entries are removed from a <code>SoftCache</code> in response to
0N/A * dynamic advice from the garbage collector, a <code>SoftCache</code> may
0N/A * behave as though an unknown thread is silently removing entries. In
0N/A * particular, even if you synchronize on a <code>SoftCache</code> instance and
0N/A * invoke none of its mutator methods, it is possible for the <code>size</code>
0N/A * method to return smaller values over time, for the <code>isEmpty</code>
0N/A * method to return <code>false</code> and then <code>true</code>, for the
0N/A * <code>containsKey</code> method to return <code>true</code> and later
0N/A * <code>false</code> for a given key, for the <code>get</code> method to
0N/A * return a value for a given key but later return <code>null</code>, for the
0N/A * <code>put</code> method to return <code>null</code> and the
0N/A * <code>remove</code> method to return <code>false</code> for a key that
0N/A * previously appeared to be in the map, and for successive examinations of the
0N/A * key set, the value set, and the entry set to yield successively smaller
0N/A * numbers of elements.
0N/A *
0N/A * @author Mark Reinhold
0N/A * @since 1.2
0N/A * @see java.util.HashMap
0N/A * @see java.lang.ref.SoftReference
0N/A */
0N/A
0N/A
0N/Apublic class SoftCache extends AbstractMap implements Map {
0N/A
0N/A /* The basic idea of this implementation is to maintain an internal HashMap
0N/A that maps keys to soft references whose referents are the keys' values;
0N/A the various accessor methods dereference these soft references before
0N/A returning values. Because we don't have access to the innards of the
0N/A HashMap, each soft reference must contain the key that maps to it so
0N/A that the processQueue method can remove keys whose values have been
0N/A discarded. Thus the HashMap actually maps keys to instances of the
0N/A ValueCell class, which is a simple extension of the SoftReference class.
0N/A */
0N/A
0N/A
0N/A static private class ValueCell extends SoftReference {
0N/A static private Object INVALID_KEY = new Object();
0N/A static private int dropped = 0;
0N/A private Object key;
0N/A
0N/A private ValueCell(Object key, Object value, ReferenceQueue queue) {
0N/A super(value, queue);
0N/A this.key = key;
0N/A }
0N/A
0N/A private static ValueCell create(Object key, Object value,
0N/A ReferenceQueue queue)
0N/A {
0N/A if (value == null) return null;
0N/A return new ValueCell(key, value, queue);
0N/A }
0N/A
0N/A private static Object strip(Object val, boolean drop) {
0N/A if (val == null) return null;
0N/A ValueCell vc = (ValueCell)val;
0N/A Object o = vc.get();
0N/A if (drop) vc.drop();
0N/A return o;
0N/A }
0N/A
0N/A private boolean isValid() {
0N/A return (key != INVALID_KEY);
0N/A }
0N/A
0N/A private void drop() {
0N/A super.clear();
0N/A key = INVALID_KEY;
0N/A dropped++;
0N/A }
0N/A
0N/A }
0N/A
0N/A
0N/A /* Hash table mapping keys to ValueCells */
0N/A private Map hash;
0N/A
0N/A /* Reference queue for cleared ValueCells */
0N/A private ReferenceQueue queue = new ReferenceQueue();
0N/A
0N/A
0N/A /* Process any ValueCells that have been cleared and enqueued by the
0N/A garbage collector. This method should be invoked once by each public
0N/A mutator in this class. We don't invoke this method in public accessors
0N/A because that can lead to surprising ConcurrentModificationExceptions.
0N/A */
0N/A private void processQueue() {
0N/A ValueCell vc;
0N/A while ((vc = (ValueCell)queue.poll()) != null) {
0N/A if (vc.isValid()) hash.remove(vc.key);
0N/A else ValueCell.dropped--;
0N/A }
0N/A }
0N/A
0N/A
0N/A /* -- Constructors -- */
0N/A
0N/A /**
0N/A * Construct a new, empty <code>SoftCache</code> with the given
0N/A * initial capacity and the given load factor.
0N/A *
0N/A * @param initialCapacity The initial capacity of the cache
0N/A *
0N/A * @param loadFactor A number between 0.0 and 1.0
0N/A *
0N/A * @throws IllegalArgumentException If the initial capacity is less than
0N/A * or equal to zero, or if the load
0N/A * factor is less than zero
0N/A */
0N/A public SoftCache(int initialCapacity, float loadFactor) {
0N/A hash = new HashMap(initialCapacity, loadFactor);
0N/A }
0N/A
0N/A /**
0N/A * Construct a new, empty <code>SoftCache</code> with the given
0N/A * initial capacity and the default load factor.
0N/A *
0N/A * @param initialCapacity The initial capacity of the cache
0N/A *
0N/A * @throws IllegalArgumentException If the initial capacity is less than
0N/A * or equal to zero
0N/A */
0N/A public SoftCache(int initialCapacity) {
0N/A hash = new HashMap(initialCapacity);
0N/A }
0N/A
0N/A /**
0N/A * Construct a new, empty <code>SoftCache</code> with the default
0N/A * capacity and the default load factor.
0N/A */
0N/A public SoftCache() {
0N/A hash = new HashMap();
0N/A }
0N/A
0N/A
0N/A /* -- Simple queries -- */
0N/A
0N/A /**
0N/A * Return the number of key-value mappings in this cache. The time
0N/A * required by this operation is linear in the size of the map.
0N/A */
0N/A public int size() {
0N/A return entrySet().size();
0N/A }
0N/A
0N/A /**
0N/A * Return <code>true</code> if this cache contains no key-value mappings.
0N/A */
0N/A public boolean isEmpty() {
0N/A return entrySet().isEmpty();
0N/A }
0N/A
0N/A /**
0N/A * Return <code>true</code> if this cache contains a mapping for the
0N/A * specified key. If there is no mapping for the key, this method will not
0N/A * attempt to construct one by invoking the <code>fill</code> method.
0N/A *
0N/A * @param key The key whose presence in the cache is to be tested
0N/A */
0N/A public boolean containsKey(Object key) {
0N/A return ValueCell.strip(hash.get(key), false) != null;
0N/A }
0N/A
0N/A
0N/A /* -- Lookup and modification operations -- */
0N/A
0N/A /**
0N/A * Create a value object for the given <code>key</code>. This method is
0N/A * invoked by the <code>get</code> method when there is no entry for
0N/A * <code>key</code>. If this method returns a non-<code>null</code> value,
0N/A * then the cache will be updated to map <code>key</code> to that value,
0N/A * and that value will be returned by the <code>get</code> method.
0N/A *
0N/A * <p> The default implementation of this method simply returns
0N/A * <code>null</code> for every <code>key</code> value. A subclass may
0N/A * override this method to provide more useful behavior.
0N/A *
0N/A * @param key The key for which a value is to be computed
0N/A *
0N/A * @return A value for <code>key</code>, or <code>null</code> if one
0N/A * could not be computed
0N/A * @see #get
0N/A */
0N/A protected Object fill(Object key) {
0N/A return null;
0N/A }
0N/A
0N/A /**
0N/A * Return the value to which this cache maps the specified
0N/A * <code>key</code>. If the cache does not presently contain a value for
0N/A * this key, then invoke the <code>fill</code> method in an attempt to
0N/A * compute such a value. If that method returns a non-<code>null</code>
0N/A * value, then update the cache and return the new value. Otherwise,
0N/A * return <code>null</code>.
0N/A *
0N/A * <p> Note that because this method may update the cache, it is considered
0N/A * a mutator and may cause <code>ConcurrentModificationException</code>s to
0N/A * be thrown if invoked while an iterator is in use.
0N/A *
0N/A * @param key The key whose associated value, if any, is to be returned
0N/A *
0N/A * @see #fill
0N/A */
0N/A public Object get(Object key) {
0N/A processQueue();
0N/A Object v = hash.get(key);
0N/A if (v == null) {
0N/A v = fill(key);
0N/A if (v != null) {
0N/A hash.put(key, ValueCell.create(key, v, queue));
0N/A return v;
0N/A }
0N/A }
0N/A return ValueCell.strip(v, false);
0N/A }
0N/A
0N/A /**
0N/A * Update this cache so that the given <code>key</code> maps to the given
0N/A * <code>value</code>. If the cache previously contained a mapping for
0N/A * <code>key</code> then that mapping is replaced and the old value is
0N/A * returned.
0N/A *
0N/A * @param key The key that is to be mapped to the given
0N/A * <code>value</code>
0N/A * @param value The value to which the given <code>key</code> is to be
0N/A * mapped
0N/A *
0N/A * @return The previous value to which this key was mapped, or
0N/A * <code>null</code> if if there was no mapping for the key
0N/A */
0N/A public Object put(Object key, Object value) {
0N/A processQueue();
0N/A ValueCell vc = ValueCell.create(key, value, queue);
0N/A return ValueCell.strip(hash.put(key, vc), true);
0N/A }
0N/A
0N/A /**
0N/A * Remove the mapping for the given <code>key</code> from this cache, if
0N/A * present.
0N/A *
0N/A * @param key The key whose mapping is to be removed
0N/A *
0N/A * @return The value to which this key was mapped, or <code>null</code> if
0N/A * there was no mapping for the key
0N/A */
0N/A public Object remove(Object key) {
0N/A processQueue();
0N/A return ValueCell.strip(hash.remove(key), true);
0N/A }
0N/A
0N/A /**
0N/A * Remove all mappings from this cache.
0N/A */
0N/A public void clear() {
0N/A processQueue();
0N/A hash.clear();
0N/A }
0N/A
0N/A
0N/A /* -- Views -- */
0N/A
0N/A private static boolean valEquals(Object o1, Object o2) {
0N/A return (o1 == null) ? (o2 == null) : o1.equals(o2);
0N/A }
0N/A
0N/A
0N/A /* Internal class for entries.
0N/A Because it uses SoftCache.this.queue, this class cannot be static.
0N/A */
0N/A private class Entry implements Map.Entry {
0N/A private Map.Entry ent;
0N/A private Object value; /* Strong reference to value, to prevent the GC
0N/A from flushing the value while this Entry
0N/A exists */
0N/A
0N/A Entry(Map.Entry ent, Object value) {
0N/A this.ent = ent;
0N/A this.value = value;
0N/A }
0N/A
0N/A public Object getKey() {
0N/A return ent.getKey();
0N/A }
0N/A
0N/A public Object getValue() {
0N/A return value;
0N/A }
0N/A
0N/A public Object setValue(Object value) {
0N/A return ent.setValue(ValueCell.create(ent.getKey(), value, queue));
0N/A }
0N/A
0N/A public boolean equals(Object o) {
0N/A if (! (o instanceof Map.Entry)) return false;
0N/A Map.Entry e = (Map.Entry)o;
0N/A return (valEquals(ent.getKey(), e.getKey())
0N/A && valEquals(value, e.getValue()));
0N/A }
0N/A
0N/A public int hashCode() {
0N/A Object k;
0N/A return ((((k = getKey()) == null) ? 0 : k.hashCode())
0N/A ^ ((value == null) ? 0 : value.hashCode()));
0N/A }
0N/A
0N/A }
0N/A
0N/A
0N/A /* Internal class for entry sets */
0N/A private class EntrySet extends AbstractSet {
0N/A Set hashEntries = hash.entrySet();
0N/A
0N/A public Iterator iterator() {
0N/A
0N/A return new Iterator() {
0N/A Iterator hashIterator = hashEntries.iterator();
0N/A Entry next = null;
0N/A
0N/A public boolean hasNext() {
0N/A while (hashIterator.hasNext()) {
0N/A Map.Entry ent = (Map.Entry)hashIterator.next();
0N/A ValueCell vc = (ValueCell)ent.getValue();
0N/A Object v = null;
0N/A if ((vc != null) && ((v = vc.get()) == null)) {
0N/A /* Value has been flushed by GC */
0N/A continue;
0N/A }
0N/A next = new Entry(ent, v);
0N/A return true;
0N/A }
0N/A return false;
0N/A }
0N/A
0N/A public Object next() {
0N/A if ((next == null) && !hasNext())
0N/A throw new NoSuchElementException();
0N/A Entry e = next;
0N/A next = null;
0N/A return e;
0N/A }
0N/A
0N/A public void remove() {
0N/A hashIterator.remove();
0N/A }
0N/A
0N/A };
0N/A }
0N/A
0N/A public boolean isEmpty() {
0N/A return !(iterator().hasNext());
0N/A }
0N/A
0N/A public int size() {
0N/A int j = 0;
0N/A for (Iterator i = iterator(); i.hasNext(); i.next()) j++;
0N/A return j;
0N/A }
0N/A
0N/A public boolean remove(Object o) {
0N/A processQueue();
0N/A if (o instanceof Entry) return hashEntries.remove(((Entry)o).ent);
0N/A else return false;
0N/A }
0N/A
0N/A }
0N/A
0N/A
0N/A private Set entrySet = null;
0N/A
0N/A /**
0N/A * Return a <code>Set</code> view of the mappings in this cache.
0N/A */
0N/A public Set entrySet() {
0N/A if (entrySet == null) entrySet = new EntrySet();
0N/A return entrySet;
0N/A }
0N/A
0N/A}