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
33 /**
34 * Cache mapping pairs of {@code (key, sub-key) -> value}. Keys and values are
35 * weakly but sub-keys are strongly referenced. Keys are passed directly to
36 * {@link #get} method which also takes a {@code parameter}. Sub-keys are
37 * calculated from keys and parameters using the {@code subKeyFactory} function
38 * passed to the constructor. Values are calculated from keys and parameters
39 * using the {@code valueFactory} function passed to the constructor.
40 * Keys can be {@code null} and are compared by identity while sub-keys returned by
41 * {@code subKeyFactory} or values returned by {@code valueFactory}
42 * can not be null. Sub-keys are compared using their {@link #equals} method.
43 * Entries are expunged from cache lazily on each invocation to {@link #get},
44 * {@link #containsValue} or {@link #size} methods when the WeakReferences to
45 * keys are cleared. Cleared WeakReferences to individual values don't cause
46 * expunging, but such entries are logically treated as non-existent and
47 * trigger re-evaluation of {@code valueFactory} on request for their
48 * key/subKey.
49 *
50 * @author Peter Levart
51 * @param <K> type of keys
52 * @param <P> type of parameters
53 * @param <V> type of values
54 */
55 final class WeakCache<K, P, V> {
56
57 interface BiFunction<T, U, R> {
58
59 /**
60 * Applies this function to the given arguments.
61 *
62 * @param t the first function argument
63 * @param u the second function argument
64 * @return the function result
65 */
66 R apply(T t, U u);
67 }
68
69 interface Supplier<T> {
70 T get();
71 }
72
73 private final ReferenceQueue<K> refQueue
74 = new ReferenceQueue<>();
75 // the key type is Object for supporting null key
76 private final ConcurrentMap<Object, ConcurrentMap<Object, Supplier<V>>> map
77 = new ConcurrentHashMap<>();
78 private final ConcurrentMap<Supplier<V>, Boolean> reverseMap
79 = new ConcurrentHashMap<>();
80 private final BiFunction<K, P, ?> subKeyFactory;
81 private final BiFunction<K, P, V> valueFactory;
82
83 /**
84 * Construct an instance of {@code WeakCache}
85 *
86 * @param subKeyFactory a function mapping a pair of
87 * {@code (key, parameter) -> sub-key}
88 * @param valueFactory a function mapping a pair of
89 * {@code (key, parameter) -> value}
90 * @throws NullPointerException if {@code subKeyFactory} or
91 * {@code valueFactory} is null.
92 */
93 public WeakCache(BiFunction<K, P, ?> subKeyFactory,
94 BiFunction<K, P, V> valueFactory) {
95 this.subKeyFactory = Objects.requireNonNull(subKeyFactory);
96 this.valueFactory = Objects.requireNonNull(valueFactory);
97 }
98
99 /**
100 * Look-up the value through the cache. This always evaluates the
101 * {@code subKeyFactory} function and optionally evaluates
102 * {@code valueFactory} function if there is no entry in the cache for given
103 * pair of (key, subKey) or the entry has already been cleared.
104 *
105 * @param key possibly null key
106 * @param parameter parameter used together with key to create sub-key and
107 * value (should not be null)
108 * @return the cached value (never null)
109 * @throws NullPointerException if {@code parameter} passed in or
110 * {@code sub-key} calculated by
111 * {@code subKeyFactory} or {@code value}
112 * calculated by {@code valueFactory} is null.
113 */
114 public V get(K key, P parameter) {
115 Objects.requireNonNull(parameter);
116
117 expungeStaleEntries();
118
119 Object cacheKey = CacheKey.valueOf(key, refQueue);
120
121 // lazily install the 2nd level valuesMap for the particular cacheKey
122 ConcurrentMap<Object, Supplier<V>> valuesMap = map.get(cacheKey);
123 if (valuesMap == null) {
124 ConcurrentMap<Object, Supplier<V>> oldValuesMap
125 = map.putIfAbsent(cacheKey,
126 valuesMap = new ConcurrentHashMap<>());
127 if (oldValuesMap != null) {
128 valuesMap = oldValuesMap;
129 }
130 }
131
132 // create subKey and retrieve the possible Supplier<V> stored by that
133 // subKey from valuesMap
134 Object subKey = Objects.requireNonNull(subKeyFactory.apply(key, parameter));
135 Supplier<V> supplier = valuesMap.get(subKey);
136 Factory factory = null;
137
138 while (true) {
139 if (supplier != null) {
140 // supplier might be a Factory or a CacheValue<V> instance
141 V value = supplier.get();
142 if (value != null) {
143 return value;
144 }
145 }
146 // else no supplier in cache
147 // or a supplier that returned null (could be a cleared CacheValue
148 // or a Factory that wasn't successful in installing the CacheValue)
149
150 // lazily construct a Factory
151 if (factory == null) {
152 factory = new Factory(key, parameter, subKey, valuesMap);
153 }
154
155 if (supplier == null) {
156 supplier = valuesMap.putIfAbsent(subKey, factory);
157 if (supplier == null) {
158 // successfully installed Factory
159 supplier = factory;
160 }
161 // else retry with winning supplier
162 } else {
163 if (valuesMap.replace(subKey, supplier, factory)) {
164 // successfully replaced
165 // cleared CacheEntry / unsuccessful Factory
166 // with our Factory
167 supplier = factory;
168 } else {
169 // retry with current supplier
170 supplier = valuesMap.get(subKey);
171 }
172 }
173 }
174 }
175
176 /**
177 * Checks whether the specified non-null value is already present in this
178 * {@code WeakCache}. The check is made using identity comparison regardless
179 * of whether value's class overrides {@link Object#equals} or not.
180 *
181 * @param value the non-null value to check
182 * @return true if given {@code value} is already cached
183 * @throws NullPointerException if value is null
184 */
185 public boolean containsValue(V value) {
186 Objects.requireNonNull(value);
187
188 expungeStaleEntries();
189 return reverseMap.containsKey(new LookupValue<>(value));
190 }
191
192 /**
193 * Returns the current number of cached entries that
194 * can decrease over time when keys/values are GC-ed.
195 */
196 public int size() {
197 expungeStaleEntries();
198 return reverseMap.size();
199 }
200
201 private void expungeStaleEntries() {
202 CacheKey<K> cacheKey;
203 while ((cacheKey = (CacheKey<K>)refQueue.poll()) != null) {
204 cacheKey.expungeFrom(map, reverseMap);
205 }
206 }
207
208 /**
209 * A factory {@link Supplier} that implements the lazy synchronized
210 * construction of the value and installment of it into the cache.
211 */
212 private final class Factory implements Supplier<V> {
213
214 private final K key;
215 private final P parameter;
216 private final Object subKey;
217 private final ConcurrentMap<Object, Supplier<V>> valuesMap;
218
219 Factory(K key, P parameter, Object subKey,
220 ConcurrentMap<Object, Supplier<V>> valuesMap) {
221 this.key = key;
222 this.parameter = parameter;
223 this.subKey = subKey;
224 this.valuesMap = valuesMap;
225 }
226
227 @Override
228 public synchronized V get() { // serialize access
229 // re-check
230 Supplier<V> supplier = valuesMap.get(subKey);
231 if (supplier != this) {
232 // something changed while we were waiting:
233 // might be that we were replaced by a CacheValue
234 // or were removed because of failure ->
235 // return null to signal WeakCache.get() to retry
236 // the loop
237 return null;
238 }
239 // else still us (supplier == this)
240
241 // create new value
242 V value = null;
243 try {
244 value = Objects.requireNonNull(valueFactory.apply(key, parameter));
245 } finally {
246 if (value == null) { // remove us on failure
247 valuesMap.remove(subKey, this);
248 }
249 }
250 // the only path to reach here is with non-null value
251 assert value != null;
252
253 // wrap value with CacheValue (WeakReference)
254 CacheValue<V> cacheValue = new CacheValue<>(value);
255
256 // try replacing us with CacheValue (this should always succeed)
257 if (valuesMap.replace(subKey, this, cacheValue)) {
258 // put also in reverseMap
259 reverseMap.put(cacheValue, Boolean.TRUE);
260 } else {
261 throw new AssertionError("Should not reach here");
262 }
263
264 // successfully replaced us with new CacheValue -> return the value
265 // wrapped by it
266 return value;
267 }
268 }
269
270 /**
271 * Common type of value suppliers that are holding a referent.
272 * The {@link #equals} and {@link #hashCode} of implementations is defined
273 * to compare the referent by identity.
274 */
275 private interface Value<V> extends Supplier<V> {}
276
277 /**
278 * An optimized {@link Value} used to look-up the value in
279 * {@link WeakCache#containsValue} method so that we are not
280 * constructing the whole {@link CacheValue} just to look-up the referent.
281 */
282 private static final class LookupValue<V> implements Value<V> {
283 private final V value;
284
285 LookupValue(V value) {
286 this.value = value;
287 }
288
289 @Override
290 public V get() {
291 return value;
292 }
293
294 @Override
295 public int hashCode() {
296 return System.identityHashCode(value); // compare by identity
297 }
298
299 @Override
300 public boolean equals(Object obj) {
301 return obj == this ||
302 obj instanceof Value &&
303 this.value == ((Value<?>) obj).get(); // compare by identity
304 }
305 }
306
307 /**
308 * A {@link Value} that weakly references the referent.
309 */
310 private static final class CacheValue<V>
311 extends WeakReference<V> implements Value<V>
312 {
313 private final int hash;
314
315 CacheValue(V value) {
316 super(value);
317 this.hash = System.identityHashCode(value); // compare by identity
318 }
319
320 @Override
321 public int hashCode() {
322 return hash;
323 }
324
325 @Override
326 public boolean equals(Object obj) {
327 V value;
328 return obj == this ||
329 obj instanceof Value &&
330 // cleared CacheValue is only equal to itself
331 (value = get()) != null &&
332 value == ((Value<?>) obj).get(); // compare by identity
333 }
334 }
335
336 /**
337 * CacheKey containing a weakly referenced {@code key}. It registers
338 * itself with the {@code refQueue} so that it can be used to expunge
339 * the entry when the {@link WeakReference} is cleared.
340 */
341 private static final class CacheKey<K> extends WeakReference<K> {
342
343 // a replacement for null keys
344 private static final Object NULL_KEY = new Object();
345
346 static <K> Object valueOf(K key, ReferenceQueue<K> refQueue) {
347 return key == null
348 // null key means we can't weakly reference it,
349 // so we use a NULL_KEY singleton as cache key
350 ? NULL_KEY
351 // non-null key requires wrapping with a WeakReference
352 : new CacheKey<>(key, refQueue);
353 }
354
355 private final int hash;
356
357 private CacheKey(K key, ReferenceQueue<K> refQueue) {
358 super(key, refQueue);
359 this.hash = System.identityHashCode(key); // compare by identity
360 }
361
362 @Override
363 public int hashCode() {
364 return hash;
365 }
366
367 @Override
368 public boolean equals(Object obj) {
369 K key;
370 return obj == this ||
371 obj != null &&
372 obj.getClass() == this.getClass() &&
373 // cleared CacheKey is only equal to itself
374 (key = this.get()) != null &&
375 // compare key by identity
376 key == ((CacheKey<K>) obj).get();
377 }
378
379 void expungeFrom(ConcurrentMap<?, ? extends ConcurrentMap<?, ?>> map,
380 ConcurrentMap<?, Boolean> reverseMap) {
381 // removing just by key is always safe here because after a CacheKey
382 // is cleared and enqueue-ed it is only equal to itself
383 // (see equals method)...
384 ConcurrentMap<?, ?> valuesMap = map.remove(this);
385 // remove also from reverseMap if needed
386 if (valuesMap != null) {
387 for (Object cacheValue : valuesMap.values()) {
388 reverseMap.remove(cacheValue);
389 }
390 }
391 }
392 }
393 }