1 /*

     2  * Copyright (c) 2013, 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 package java.lang.reflect;

    26 

    27 import java.lang.ref.ReferenceQueue;

    28 import java.lang.ref.WeakReference;

    29 import java.util.Objects;

    30 import java.util.concurrent.ConcurrentHashMap;

    31 import java.util.concurrent.ConcurrentMap;

    32 import java.util.function.BiFunction;

    33 import java.util.function.Supplier;

    34 

    35 /**

    36  * Cache mapping pairs of {@code (key, sub-key) -> value}. Keys and values are

    37  * weakly but sub-keys are strongly referenced.  Keys are passed directly to

    38  * {@link #get} method which also takes a {@code parameter}. Sub-keys are

    39  * calculated from keys and parameters using the {@code subKeyFactory} function

    40  * passed to the constructor. Values are calculated from keys and parameters

    41  * using the {@code valueFactory} function passed to the constructor.

    42  * Keys can be {@code null} and are compared by identity while sub-keys returned by

    43  * {@code subKeyFactory} or values returned by {@code valueFactory}

    44  * can not be null. Sub-keys are compared using their {@link #equals} method.

    45  * Entries are expunged from cache lazily on each invocation to {@link #get},

    46  * {@link #containsValue} or {@link #size} methods when the WeakReferences to

    47  * keys are cleared. Cleared WeakReferences to individual values don't cause

    48  * expunging, but such entries are logically treated as non-existent and

    49  * trigger re-evaluation of {@code valueFactory} on request for their

    50  * key/subKey.

    51  *

    52  * @author Peter Levart

    53  * @param <K> type of keys

    54  * @param <P> type of parameters

    55  * @param <V> type of values

    56  */

    57 final class WeakCache<K, P, V> {

    58 

    59     private final ReferenceQueue<K> refQueue

    60         = new ReferenceQueue<>();

    61     // the key type is Object for supporting null key

    62     private final ConcurrentMap<Object, ConcurrentMap<Object, Supplier<V>>> map

    63         = new ConcurrentHashMap<>();

    64     private final ConcurrentMap<Supplier<V>, Boolean> reverseMap

    65         = new ConcurrentHashMap<>();

    66     private final BiFunction<K, P, ?> subKeyFactory;

    67     private final BiFunction<K, P, V> valueFactory;

    68 

    69     /**

    70      * Construct an instance of {@code WeakCache}

    71      *

    72      * @param subKeyFactory a function mapping a pair of

    73      *                      {@code (key, parameter) -> sub-key}

    74      * @param valueFactory  a function mapping a pair of

    75      *                      {@code (key, parameter) -> value}

    76      * @throws NullPointerException if {@code subKeyFactory} or

    77      *                              {@code valueFactory} is null.

    78      */

    79     public WeakCache(BiFunction<K, P, ?> subKeyFactory,

    80                      BiFunction<K, P, V> valueFactory) {

    81         this.subKeyFactory = Objects.requireNonNull(subKeyFactory);

    82         this.valueFactory = Objects.requireNonNull(valueFactory);

    83     }

    84 

    85     /**

    86      * Look-up the value through the cache. This always evaluates the

    87      * {@code subKeyFactory} function and optionally evaluates

    88      * {@code valueFactory} function if there is no entry in the cache for given

    89      * pair of (key, subKey) or the entry has already been cleared.

    90      *

    91      * @param key       possibly null key

    92      * @param parameter parameter used together with key to create sub-key and

    93      *                  value (should not be null)

    94      * @return the cached value (never null)

    95      * @throws NullPointerException if {@code parameter} passed in or

    96      *                              {@code sub-key} calculated by

    97      *                              {@code subKeyFactory} or {@code value}

    98      *                              calculated by {@code valueFactory} is null.

    99      */

   100     public V get(K key, P parameter) {

   101         Objects.requireNonNull(parameter);

   102 

   103         expungeStaleEntries();

   104 

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

   106 

   107         // lazily install the 2nd level valuesMap for the particular cacheKey

   108         ConcurrentMap<Object, Supplier<V>> valuesMap = map.get(cacheKey);

   109         if (valuesMap == null) {

   110             ConcurrentMap<Object, Supplier<V>> oldValuesMap

   111                 = map.putIfAbsent(cacheKey,

   112                                   valuesMap = new ConcurrentHashMap<>());

   113             if (oldValuesMap != null) {

   114                 valuesMap = oldValuesMap;

   115             }

   116         }

   117 

   118         // create subKey and retrieve the possible Supplier<V> stored by that

   119         // subKey from valuesMap

   120         Object subKey = Objects.requireNonNull(subKeyFactory.apply(key, parameter));

   121         Supplier<V> supplier = valuesMap.get(subKey);

   122         Factory factory = null;

   123 

   124         while (true) {

   125             if (supplier != null) {

   126                 // supplier might be a Factory or a CacheValue<V> instance

   127                 V value = supplier.get();

   128                 if (value != null) {

   129                     return value;

   130                 }

   131             }

   132             // else no supplier in cache

   133             // or a supplier that returned null (could be a cleared CacheValue

   134             // or a Factory that wasn't successful in installing the CacheValue)

   135 

   136             // lazily construct a Factory

   137             if (factory == null) {

   138                 factory = new Factory(key, parameter, subKey, valuesMap);

   139             }

   140 

   141             if (supplier == null) {

   142                 supplier = valuesMap.putIfAbsent(subKey, factory);

   143                 if (supplier == null) {

   144                     // successfully installed Factory

   145                     supplier = factory;

   146                 }

   147                 // else retry with winning supplier

   148             } else {

   149                 if (valuesMap.replace(subKey, supplier, factory)) {

   150                     // successfully replaced

   151                     // cleared CacheEntry / unsuccessful Factory

   152                     // with our Factory

   153                     supplier = factory;

   154                 } else {

   155                     // retry with current supplier

   156                     supplier = valuesMap.get(subKey);

   157                 }

   158             }

   159         }

   160     }

   161 

   162     /**

   163      * Checks whether the specified non-null value is already present in this

   164      * {@code WeakCache}. The check is made using identity comparison regardless

   165      * of whether value's class overrides {@link Object#equals} or not.

   166      *

   167      * @param value the non-null value to check

   168      * @return true if given {@code value} is already cached

   169      * @throws NullPointerException if value is null

   170      */

   171     public boolean containsValue(V value) {

   172         Objects.requireNonNull(value);

   173 

   174         expungeStaleEntries();

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

   176     }

   177 

   178     /**

   179      * Returns the current number of cached entries that

   180      * can decrease over time when keys/values are GC-ed.

   181      */

   182     public int size() {

   183         expungeStaleEntries();

   184         return reverseMap.size();

   185     }

   186 

   187     private void expungeStaleEntries() {

   188         CacheKey<K> cacheKey;

   189         while ((cacheKey = (CacheKey<K>)refQueue.poll()) != null) {

   190             cacheKey.expungeFrom(map, reverseMap);

   191         }

   192     }

   193 

   194     /**

   195      * A factory {@link Supplier} that implements the lazy synchronized

   196      * construction of the value and installment of it into the cache.

   197      */

   198     private final class Factory implements Supplier<V> {

   199 

   200         private final K key;

   201         private final P parameter;

   202         private final Object subKey;

   203         private final ConcurrentMap<Object, Supplier<V>> valuesMap;

   204 

   205         Factory(K key, P parameter, Object subKey,

   206                 ConcurrentMap<Object, Supplier<V>> valuesMap) {

   207             this.key = key;

   208             this.parameter = parameter;

   209             this.subKey = subKey;

   210             this.valuesMap = valuesMap;

   211         }

   212 

   213         @Override

   214         public synchronized V get() { // serialize access

   215             // re-check

   216             Supplier<V> supplier = valuesMap.get(subKey);

   217             if (supplier != this) {

   218                 // something changed while we were waiting:

   219                 // might be that we were replaced by a CacheValue

   220                 // or were removed because of failure ->

   221                 // return null to signal WeakCache.get() to retry

   222                 // the loop

   223                 return null;

   224             }

   225             // else still us (supplier == this)

   226 

   227             // create new value

   228             V value = null;

   229             try {

   230                 value = Objects.requireNonNull(valueFactory.apply(key, parameter));

   231             } finally {

   232                 if (value == null) { // remove us on failure

   233                     valuesMap.remove(subKey, this);

   234                 }

   235             }

   236             // the only path to reach here is with non-null value

   237             assert value != null;

   238 

   239             // wrap value with CacheValue (WeakReference)

   240             CacheValue<V> cacheValue = new CacheValue<>(value);

   241 

   242             // try replacing us with CacheValue (this should always succeed)

   243             if (valuesMap.replace(subKey, this, cacheValue)) {

   244                 // put also in reverseMap

   245                 reverseMap.put(cacheValue, Boolean.TRUE);

   246             } else {

   247                 throw new AssertionError("Should not reach here");

   248             }

   249 

   250             // successfully replaced us with new CacheValue -> return the value

   251             // wrapped by it

   252             return value;

   253         }

   254     }

   255 

   256     /**

   257      * Common type of value suppliers that are holding a referent.

   258      * The {@link #equals} and {@link #hashCode} of implementations is defined

   259      * to compare the referent by identity.

   260      */

   261     private interface Value<V> extends Supplier<V> {}

   262 

   263     /**

   264      * An optimized {@link Value} used to look-up the value in

   265      * {@link WeakCache#containsValue} method so that we are not

   266      * constructing the whole {@link CacheValue} just to look-up the referent.

   267      */

   268     private static final class LookupValue<V> implements Value<V> {

   269         private final V value;

   270 

   271         LookupValue(V value) {

   272             this.value = value;

   273         }

   274 

   275         @Override

   276         public V get() {

   277             return value;

   278         }

   279 

   280         @Override

   281         public int hashCode() {

   282             return System.identityHashCode(value); // compare by identity

   283         }

   284 

   285         @Override

   286         public boolean equals(Object obj) {

   287             return obj == this ||

   288                    obj instanceof Value &&

   289                    this.value == ((Value<?>) obj).get();  // compare by identity

   290         }

   291     }

   292 

   293     /**

   294      * A {@link Value} that weakly references the referent.

   295      */

   296     private static final class CacheValue<V>

   297         extends WeakReference<V> implements Value<V>

   298     {

   299         private final int hash;

   300 

   301         CacheValue(V value) {

   302             super(value);

   303             this.hash = System.identityHashCode(value); // compare by identity

   304         }

   305 

   306         @Override

   307         public int hashCode() {

   308             return hash;

   309         }

   310 

   311         @Override

   312         public boolean equals(Object obj) {

   313             V value;

   314             return obj == this ||

   315                    obj instanceof Value &&

   316                    // cleared CacheValue is only equal to itself

   317                    (value = get()) != null &&

   318                    value == ((Value<?>) obj).get(); // compare by identity

   319         }

   320     }

   321 

   322     /**

   323      * CacheKey containing a weakly referenced {@code key}. It registers

   324      * itself with the {@code refQueue} so that it can be used to expunge

   325      * the entry when the {@link WeakReference} is cleared.

   326      */

   327     private static final class CacheKey<K> extends WeakReference<K> {

   328 

   329         // a replacement for null keys

   330         private static final Object NULL_KEY = new Object();

   331 

   332         static <K> Object valueOf(K key, ReferenceQueue<K> refQueue) {

   333             return key == null

   334                    // null key means we can't weakly reference it,

   335                    // so we use a NULL_KEY singleton as cache key

   336                    ? NULL_KEY

   337                    // non-null key requires wrapping with a WeakReference

   338                    : new CacheKey<>(key, refQueue);

   339         }

   340 

   341         private final int hash;

   342 

   343         private CacheKey(K key, ReferenceQueue<K> refQueue) {

   344             super(key, refQueue);

   345             this.hash = System.identityHashCode(key);  // compare by identity

   346         }

   347 

   348         @Override

   349         public int hashCode() {

   350             return hash;

   351         }

   352 

   353         @Override

   354         public boolean equals(Object obj) {

   355             K key;

   356             return obj == this ||

   357                    obj != null &&

   358                    obj.getClass() == this.getClass() &&

   359                    // cleared CacheKey is only equal to itself

   360                    (key = this.get()) != null &&

   361                    // compare key by identity

   362                    key == ((CacheKey<K>) obj).get();

   363         }

   364 

   365         void expungeFrom(ConcurrentMap<?, ? extends ConcurrentMap<?, ?>> map,

   366                          ConcurrentMap<?, Boolean> reverseMap) {

   367             // removing just by key is always safe here because after a CacheKey

   368             // is cleared and enqueue-ed it is only equal to itself

   369             // (see equals method)...

   370             ConcurrentMap<?, ?> valuesMap = map.remove(this);

   371             // remove also from reverseMap if needed

   372             if (valuesMap != null) {

   373                 for (Object cacheValue : valuesMap.values()) {

   374                     reverseMap.remove(cacheValue);

   375                 }

   376             }

   377         }

   378     }

   379 }