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 } |
|