--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/src/share/classes/java/lang/reflect/WeakCache.java Fri Apr 26 16:09:53 2013 -0700
@@ -0,0 +1,379 @@
+/*
+ * 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);
+
+ // try replacing us with CacheValue (this should always succeed)
+ if (valuesMap.replace(subKey, this, cacheValue)) {
+ // put also in reverseMap
+ reverseMap.put(cacheValue, Boolean.TRUE);
+ } else {
+ 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);
+ }
+ }
+ }
+ }
+}