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 }