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 }