1 /*
   2  * Copyright (c) 2013, 2014, 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     @SuppressWarnings("unchecked") // refQueue.poll actually returns CacheKey<K>
 188     private void expungeStaleEntries() {
 189         CacheKey<K> cacheKey;
 190         while ((cacheKey = (CacheKey<K>)refQueue.poll()) != null) {
 191             cacheKey.expungeFrom(map, reverseMap);
 192         }
 193     }
 194 
 195     /**
 196      * A factory {@link Supplier} that implements the lazy synchronized
 197      * construction of the value and installment of it into the cache.
 198      */
 199     private final class Factory implements Supplier<V> {
 200 
 201         private final K key;
 202         private final P parameter;
 203         private final Object subKey;
 204         private final ConcurrentMap<Object, Supplier<V>> valuesMap;
 205 
 206         Factory(K key, P parameter, Object subKey,
 207                 ConcurrentMap<Object, Supplier<V>> valuesMap) {
 208             this.key = key;
 209             this.parameter = parameter;
 210             this.subKey = subKey;
 211             this.valuesMap = valuesMap;
 212         }
 213 
 214         @Override
 215         public synchronized V get() { // serialize access
 216             // re-check
 217             Supplier<V> supplier = valuesMap.get(subKey);
 218             if (supplier != this) {
 219                 // something changed while we were waiting:
 220                 // might be that we were replaced by a CacheValue
 221                 // or were removed because of failure ->
 222                 // return null to signal WeakCache.get() to retry
 223                 // the loop
 224                 return null;
 225             }
 226             // else still us (supplier == this)
 227 
 228             // create new value
 229             V value = null;
 230             try {
 231                 value = Objects.requireNonNull(valueFactory.apply(key, parameter));
 232             } finally {
 233                 if (value == null) { // remove us on failure
 234                     valuesMap.remove(subKey, this);
 235                 }
 236             }
 237             // the only path to reach here is with non-null value
 238             assert value != null;
 239 
 240             // wrap value with CacheValue (WeakReference)
 241             CacheValue<V> cacheValue = new CacheValue<>(value);
 242 
 243             // try replacing us with CacheValue (this should always succeed)
 244             if (valuesMap.replace(subKey, this, cacheValue)) {
 245                 // put also in reverseMap
 246                 reverseMap.put(cacheValue, Boolean.TRUE);
 247             } else {
 248                 throw new AssertionError("Should not reach here");
 249             }
 250 
 251             // successfully replaced us with new CacheValue -> return the value
 252             // wrapped by it
 253             return value;
 254         }
 255     }
 256 
 257     /**
 258      * Common type of value suppliers that are holding a referent.
 259      * The {@link #equals} and {@link #hashCode} of implementations is defined
 260      * to compare the referent by identity.
 261      */
 262     private interface Value<V> extends Supplier<V> {}
 263 
 264     /**
 265      * An optimized {@link Value} used to look-up the value in
 266      * {@link WeakCache#containsValue} method so that we are not
 267      * constructing the whole {@link CacheValue} just to look-up the referent.
 268      */
 269     private static final class LookupValue<V> implements Value<V> {
 270         private final V value;
 271 
 272         LookupValue(V value) {
 273             this.value = value;
 274         }
 275 
 276         @Override
 277         public V get() {
 278             return value;
 279         }
 280 
 281         @Override
 282         public int hashCode() {
 283             return System.identityHashCode(value); // compare by identity
 284         }
 285 
 286         @Override
 287         public boolean equals(Object obj) {
 288             return obj == this ||
 289                    obj instanceof Value &&
 290                    this.value == ((Value<?>) obj).get();  // compare by identity
 291         }
 292     }
 293 
 294     /**
 295      * A {@link Value} that weakly references the referent.
 296      */
 297     private static final class CacheValue<V>
 298         extends WeakReference<V> implements Value<V>
 299     {
 300         private final int hash;
 301 
 302         CacheValue(V value) {
 303             super(value);
 304             this.hash = System.identityHashCode(value); // compare by identity
 305         }
 306 
 307         @Override
 308         public int hashCode() {
 309             return hash;
 310         }
 311 
 312         @Override
 313         public boolean equals(Object obj) {
 314             V value;
 315             return obj == this ||
 316                    obj instanceof Value &&
 317                    // cleared CacheValue is only equal to itself
 318                    (value = get()) != null &&
 319                    value == ((Value<?>) obj).get(); // compare by identity
 320         }
 321     }
 322 
 323     /**
 324      * CacheKey containing a weakly referenced {@code key}. It registers
 325      * itself with the {@code refQueue} so that it can be used to expunge
 326      * the entry when the {@link WeakReference} is cleared.
 327      */
 328     private static final class CacheKey<K> extends WeakReference<K> {
 329 
 330         // a replacement for null keys
 331         private static final Object NULL_KEY = new Object();
 332 
 333         static <K> Object valueOf(K key, ReferenceQueue<K> refQueue) {
 334             return key == null
 335                    // null key means we can't weakly reference it,
 336                    // so we use a NULL_KEY singleton as cache key
 337                    ? NULL_KEY
 338                    // non-null key requires wrapping with a WeakReference
 339                    : new CacheKey<>(key, refQueue);
 340         }
 341 
 342         private final int hash;
 343 
 344         private CacheKey(K key, ReferenceQueue<K> refQueue) {
 345             super(key, refQueue);
 346             this.hash = System.identityHashCode(key);  // compare by identity
 347         }
 348 
 349         @Override
 350         public int hashCode() {
 351             return hash;
 352         }
 353 
 354         @Override
 355         @SuppressWarnings("unchecked")
 356         public boolean equals(Object obj) {
 357             K key;
 358             return obj == this ||
 359                    obj != null &&
 360                    obj.getClass() == this.getClass() &&
 361                    // cleared CacheKey is only equal to itself
 362                    (key = this.get()) != null &&
 363                    // compare key by identity
 364                    key == ((CacheKey<K>) obj).get(); // Cast is safe from getClass check
 365         }
 366 
 367         void expungeFrom(ConcurrentMap<?, ? extends ConcurrentMap<?, ?>> map,
 368                          ConcurrentMap<?, Boolean> reverseMap) {
 369             // removing just by key is always safe here because after a CacheKey
 370             // is cleared and enqueue-ed it is only equal to itself
 371             // (see equals method)...
 372             ConcurrentMap<?, ?> valuesMap = map.remove(this);
 373             // remove also from reverseMap if needed
 374             if (valuesMap != null) {
 375                 for (Object cacheValue : valuesMap.values()) {
 376                     reverseMap.remove(cacheValue);
 377                 }
 378             }
 379         }
 380     }
 381 }