Back to index...

	/*
	* Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation. Oracle designates this
	* particular file as subject to the "Classpath" exception as provided
	* by Oracle in the LICENSE file that accompanied this code.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/
	package java.lang.reflect;

	import java.lang.ref.ReferenceQueue;
	import java.lang.ref.WeakReference;
	import java.util.Objects;
	import java.util.concurrent.ConcurrentHashMap;
	import java.util.concurrent.ConcurrentMap;
	import java.util.function.BiFunction;
	import java.util.function.Supplier;

	/**
	* Cache mapping pairs of {@code (key, sub-key) -> value}. Keys and values are
	* weakly but sub-keys are strongly referenced. Keys are passed directly to
	* {@link #get} method which also takes a {@code parameter}. Sub-keys are
	* calculated from keys and parameters using the {@code subKeyFactory} function
	* passed to the constructor. Values are calculated from keys and parameters
	* using the {@code valueFactory} function passed to the constructor.
	* Keys can be {@code null} and are compared by identity while sub-keys returned by
	* {@code subKeyFactory} or values returned by {@code valueFactory}
	* can not be null. Sub-keys are compared using their {@link #equals} method.
	* Entries are expunged from cache lazily on each invocation to {@link #get},
	* {@link #containsValue} or {@link #size} methods when the WeakReferences to
	* keys are cleared. Cleared WeakReferences to individual values don't cause
	* expunging, but such entries are logically treated as non-existent and
	* trigger re-evaluation of {@code valueFactory} on request for their
	* key/subKey.
	*
	* @author Peter Levart
	* @param <K> type of keys
	* @param <P> type of parameters
	* @param <V> type of values
	*/
	final class WeakCache<K, P, V> {

	private final ReferenceQueue<K> refQueue
	= new ReferenceQueue<>();
	// the key type is Object for supporting null key
	private final ConcurrentMap<Object, ConcurrentMap<Object, Supplier<V>>> map
	= new ConcurrentHashMap<>();
	private final ConcurrentMap<Supplier<V>, Boolean> reverseMap
	= new ConcurrentHashMap<>();
	private final BiFunction<K, P, ?> subKeyFactory;
	private final BiFunction<K, P, V> valueFactory;

	/**
	* Construct an instance of {@code WeakCache}
	*
	* @param subKeyFactory a function mapping a pair of
	* {@code (key, parameter) -> sub-key}
	* @param valueFactory a function mapping a pair of
	* {@code (key, parameter) -> value}
	* @throws NullPointerException if {@code subKeyFactory} or
	* {@code valueFactory} is null.
	*/
	public WeakCache(BiFunction<K, P, ?> subKeyFactory,
	BiFunction<K, P, V> valueFactory) {
	this.subKeyFactory = Objects.requireNonNull(subKeyFactory);
	this.valueFactory = Objects.requireNonNull(valueFactory);
	}

	/**
	* Look-up the value through the cache. This always evaluates the
	* {@code subKeyFactory} function and optionally evaluates
	* {@code valueFactory} function if there is no entry in the cache for given
	* pair of (key, subKey) or the entry has already been cleared.
	*
	* @param key possibly null key
	* @param parameter parameter used together with key to create sub-key and
	* value (should not be null)
	* @return the cached value (never null)
	* @throws NullPointerException if {@code parameter} passed in or
	* {@code sub-key} calculated by
	* {@code subKeyFactory} or {@code value}
	* calculated by {@code valueFactory} is null.
	*/
	public V get(K key, P parameter) {
	Objects.requireNonNull(parameter);

	expungeStaleEntries();

	Object cacheKey = CacheKey.valueOf(key, refQueue);

	// lazily install the 2nd level valuesMap for the particular cacheKey
	ConcurrentMap<Object, Supplier<V>> valuesMap = map.get(cacheKey);
	if (valuesMap == null) {
	ConcurrentMap<Object, Supplier<V>> oldValuesMap
	= map.putIfAbsent(cacheKey,
	valuesMap = new ConcurrentHashMap<>());
	if (oldValuesMap != null) {
	valuesMap = oldValuesMap;
	}
	}

	// create subKey and retrieve the possible Supplier<V> stored by that
	// subKey from valuesMap
	Object subKey = Objects.requireNonNull(subKeyFactory.apply(key, parameter));
	Supplier<V> supplier = valuesMap.get(subKey);
	Factory factory = null;

	while (true) {
	if (supplier != null) {
	// supplier might be a Factory or a CacheValue<V> instance
	V value = supplier.get();
	if (value != null) {
	return value;
	}
	}
	// else no supplier in cache
	// or a supplier that returned null (could be a cleared CacheValue
	// or a Factory that wasn't successful in installing the CacheValue)

	// lazily construct a Factory
	if (factory == null) {
	factory = new Factory(key, parameter, subKey, valuesMap);
	}

	if (supplier == null) {
	supplier = valuesMap.putIfAbsent(subKey, factory);
	if (supplier == null) {
	// successfully installed Factory
	supplier = factory;
	}
	// else retry with winning supplier
	} else {
	if (valuesMap.replace(subKey, supplier, factory)) {
	// successfully replaced
	// cleared CacheEntry / unsuccessful Factory
	// with our Factory
	supplier = factory;
	} else {
	// retry with current supplier
	supplier = valuesMap.get(subKey);
	}
	}
	}
	}

	/**
	* Checks whether the specified non-null value is already present in this
	* {@code WeakCache}. The check is made using identity comparison regardless
	* of whether value's class overrides {@link Object#equals} or not.
	*
	* @param value the non-null value to check
	* @return true if given {@code value} is already cached
	* @throws NullPointerException if value is null
	*/
	public boolean containsValue(V value) {
	Objects.requireNonNull(value);

	expungeStaleEntries();
	return reverseMap.containsKey(new LookupValue<>(value));
	}

	/**
	* Returns the current number of cached entries that
	* can decrease over time when keys/values are GC-ed.
	*/
	public int size() {
	expungeStaleEntries();
	return reverseMap.size();
	}

	private void expungeStaleEntries() {
	CacheKey<K> cacheKey;
	while ((cacheKey = (CacheKey<K>)refQueue.poll()) != null) {
	cacheKey.expungeFrom(map, reverseMap);
	}
	}

	/**
	* A factory {@link Supplier} that implements the lazy synchronized
	* construction of the value and installment of it into the cache.
	*/
	private final class Factory implements Supplier<V> {

	private final K key;
	private final P parameter;
	private final Object subKey;
	private final ConcurrentMap<Object, Supplier<V>> valuesMap;

	Factory(K key, P parameter, Object subKey,
	ConcurrentMap<Object, Supplier<V>> valuesMap) {
	this.key = key;
	this.parameter = parameter;
	this.subKey = subKey;
	this.valuesMap = valuesMap;
	}

	@Override
	public synchronized V get() { // serialize access
	// re-check
	Supplier<V> supplier = valuesMap.get(subKey);
	if (supplier != this) {
	// something changed while we were waiting:
	// might be that we were replaced by a CacheValue
	// or were removed because of failure ->
	// return null to signal WeakCache.get() to retry
	// the loop
	return null;
	}
	// else still us (supplier == this)

	// create new value
	V value = null;
	try {
	value = Objects.requireNonNull(valueFactory.apply(key, parameter));
	} finally {
	if (value == null) { // remove us on failure
	valuesMap.remove(subKey, this);
	}
	}
	// the only path to reach here is with non-null value
	assert value != null;

	// wrap value with CacheValue (WeakReference)
	CacheValue<V> cacheValue = new CacheValue<>(value);

	// put into reverseMap
	reverseMap.put(cacheValue, Boolean.TRUE);

	// try replacing us with CacheValue (this should always succeed)
	if (!valuesMap.replace(subKey, this, cacheValue)) {
	throw new AssertionError("Should not reach here");
	}

	// successfully replaced us with new CacheValue -> return the value
	// wrapped by it
	return value;
	}
	}

	/**
	* Common type of value suppliers that are holding a referent.
	* The {@link #equals} and {@link #hashCode} of implementations is defined
	* to compare the referent by identity.
	*/
	private interface Value<V> extends Supplier<V> {}

	/**
	* An optimized {@link Value} used to look-up the value in
	* {@link WeakCache#containsValue} method so that we are not
	* constructing the whole {@link CacheValue} just to look-up the referent.
	*/
	private static final class LookupValue<V> implements Value<V> {
	private final V value;

	LookupValue(V value) {
	this.value = value;
	}

	@Override
	public V get() {
	return value;
	}

	@Override
	public int hashCode() {
	return System.identityHashCode(value); // compare by identity
	}

	@Override
	public boolean equals(Object obj) {
	return obj == this \|\|
	obj instanceof Value &&
	this.value == ((Value<?>) obj).get(); // compare by identity
	}
	}

	/**
	* A {@link Value} that weakly references the referent.
	*/
	private static final class CacheValue<V>
	extends WeakReference<V> implements Value<V>
	{
	private final int hash;

	CacheValue(V value) {
	super(value);
	this.hash = System.identityHashCode(value); // compare by identity
	}

	@Override
	public int hashCode() {
	return hash;
	}

	@Override
	public boolean equals(Object obj) {
	V value;
	return obj == this \|\|
	obj instanceof Value &&
	// cleared CacheValue is only equal to itself
	(value = get()) != null &&
	value == ((Value<?>) obj).get(); // compare by identity
	}
	}

	/**
	* CacheKey containing a weakly referenced {@code key}. It registers
	* itself with the {@code refQueue} so that it can be used to expunge
	* the entry when the {@link WeakReference} is cleared.
	*/
	private static final class CacheKey<K> extends WeakReference<K> {

	// a replacement for null keys
	private static final Object NULL_KEY = new Object();

	static <K> Object valueOf(K key, ReferenceQueue<K> refQueue) {
	return key == null
	// null key means we can't weakly reference it,
	// so we use a NULL_KEY singleton as cache key
	? NULL_KEY
	// non-null key requires wrapping with a WeakReference
	: new CacheKey<>(key, refQueue);
	}

	private final int hash;

	private CacheKey(K key, ReferenceQueue<K> refQueue) {
	super(key, refQueue);
	this.hash = System.identityHashCode(key); // compare by identity
	}

	@Override
	public int hashCode() {
	return hash;
	}

	@Override
	public boolean equals(Object obj) {
	K key;
	return obj == this \|\|
	obj != null &&
	obj.getClass() == this.getClass() &&
	// cleared CacheKey is only equal to itself
	(key = this.get()) != null &&
	// compare key by identity
	key == ((CacheKey<K>) obj).get();
	}

	void expungeFrom(ConcurrentMap<?, ? extends ConcurrentMap<?, ?>> map,
	ConcurrentMap<?, Boolean> reverseMap) {
	// removing just by key is always safe here because after a CacheKey
	// is cleared and enqueue-ed it is only equal to itself
	// (see equals method)...
	ConcurrentMap<?, ?> valuesMap = map.remove(this);
	// remove also from reverseMap if needed
	if (valuesMap != null) {
	for (Object cacheValue : valuesMap.values()) {
	reverseMap.remove(cacheValue);
	}
	}
	}
	}
	}

Back to index...