1 /*
2 * Copyright (c) 2023, 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
26 package jdk.internal.util;
27
28 import java.lang.ref.Reference;
29 import java.lang.ref.ReferenceQueue;
30 import java.lang.ref.SoftReference;
31 import java.lang.ref.WeakReference;
32 import java.util.AbstractMap;
33 import java.util.Collection;
34 import java.util.HashMap;
35 import java.util.Objects;
36 import java.util.Map;
37 import java.util.Set;
38 import java.util.concurrent.ConcurrentHashMap;
39 import java.util.function.Supplier;
40 import java.util.function.UnaryOperator;
41 import java.util.stream.Collectors;
42 import java.util.stream.Stream;
43
44 import jdk.internal.access.SharedSecrets;
45
46 /**
47 * This class provides management of {@link Map maps} where it is desirable to
48 * remove entries automatically when the key is garbage collected. This is
49 * accomplished by using a backing map where the keys are either a
50 * {@link WeakReference} or a {@link SoftReference}.
51 * <p>
52 * To create a {@link ReferencedKeyMap} the user must provide a {@link Supplier}
53 * of the backing map and whether {@link WeakReference} or
54 * {@link SoftReference} is to be used.
55 *
56 * {@snippet :
57 * // Use HashMap and WeakReference
58 * Map<Long, String> map = ReferencedKeyMap.create(false, HashMap::new);
59 * map.put(10_000_000L, "a");
60 * map.put(10_000_001L, "b");
61 * map.put(10_000_002L, "c");
62 * map.put(10_000_003L, "d");
63 * map.put(10_000_004L, "e");
64 *
65 * // Use ConcurrentHashMap and SoftReference
66 * map = ReferencedKeyMap.create(true, ConcurrentHashMap::new);
67 * map.put(20_000_000L, "v");
68 * map.put(20_000_001L, "w");
69 * map.put(20_000_002L, "x");
70 * map.put(20_000_003L, "y");
71 * map.put(20_000_004L, "z");
72 * }
73 *
74 * @implNote Care must be given that the backing map does replacement by
75 * replacing the value in the map entry instead of deleting the old entry and
76 * adding a new entry, otherwise replaced entries may end up with a strongly
77 * referenced key. {@link HashMap} and {@link ConcurrentHashMap} are known
78 * to be safe.
79 *
80 * @param <K> the type of keys maintained by this map
81 * @param <V> the type of mapped values
82 *
83 * @since 21
84 */
85 public final class ReferencedKeyMap<K, V> implements Map<K, V> {
86 /**
87 * true if {@link SoftReference} keys are to be used,
88 * {@link WeakReference} otherwise.
89 */
90 private final boolean isSoft;
91
92 /**
93 * Backing {@link Map}.
94 */
95 private final Map<ReferenceKey<K>, V> map;
96
97 /**
98 * {@link ReferenceQueue} for cleaning up entries.
99 */
100 private final ReferenceQueue<K> stale;
101
102 /**
103 * Private constructor.
104 *
105 * @param isSoft true if {@link SoftReference} keys are to
106 * be used, {@link WeakReference} otherwise.
107 * @param map backing map
108 * @param stale {@link ReferenceQueue} for cleaning up entries
109 */
110 private ReferencedKeyMap(boolean isSoft, Map<ReferenceKey<K>, V> map, ReferenceQueue<K> stale) {
111 this.isSoft = isSoft;
112 this.map = map;
113 this.stale = stale;
114 }
115
116 /**
117 * Create a new {@link ReferencedKeyMap} map.
118 *
119 * @param isSoft true if {@link SoftReference} keys are to
120 * be used, {@link WeakReference} otherwise.
121 * @param supplier {@link Supplier} of the backing map
122 *
123 * @return a new map with {@link Reference} keys
124 *
125 * @param <K> the type of keys maintained by the new map
126 * @param <V> the type of mapped values
127 */
128 public static <K, V> ReferencedKeyMap<K, V>
129 create(boolean isSoft, Supplier<Map<ReferenceKey<K>, V>> supplier) {
130 return create(isSoft, false, supplier);
131 }
132
133 /**
134 * Create a new {@link ReferencedKeyMap} map.
135 *
136 * @param isSoft true if {@link SoftReference} keys are to
137 * be used, {@link WeakReference} otherwise.
138 * @param useNativeQueue true if uses NativeReferenceQueue
139 * otherwise use {@link ReferenceQueue}.
140 * @param supplier {@link Supplier} of the backing map
141 *
142 * @return a new map with {@link Reference} keys
143 *
144 * @param <K> the type of keys maintained by the new map
145 * @param <V> the type of mapped values
146 */
147 public static <K, V> ReferencedKeyMap<K, V>
148 create(boolean isSoft, boolean useNativeQueue, Supplier<Map<ReferenceKey<K>, V>> supplier) {
149 return new ReferencedKeyMap<K, V>(isSoft, supplier.get(),
150 useNativeQueue ? SharedSecrets.getJavaLangRefAccess().newNativeReferenceQueue()
151 : new ReferenceQueue<>()
152 );
153 }
154
155 /**
156 * {@return a key suitable for a map entry}
157 *
158 * @param key unwrapped key
159 */
160 @SuppressWarnings("unchecked")
161 private ReferenceKey<K> entryKey(Object key) {
162 if (isSoft) {
163 return new SoftReferenceKey<>((K)key, stale);
164 } else {
165 return new WeakReferenceKey<>((K)key, stale);
166 }
167 }
168
169 /**
170 * {@return a key suitable for lookup}
171 *
172 * @param key unwrapped key
173 */
174 @SuppressWarnings("unchecked")
175 private ReferenceKey<K> lookupKey(Object key) {
176 return new StrongReferenceKey<>((K)key);
177 }
178
179 @Override
180 public int size() {
181 removeStaleReferences();
182 return map.size();
183 }
184
185 @Override
186 public boolean isEmpty() {
187 removeStaleReferences();
188 return map.isEmpty();
189 }
190
191 @Override
192 public boolean containsKey(Object key) {
193 Objects.requireNonNull(key, "key must not be null");
194 removeStaleReferences();
195 return map.containsKey(lookupKey(key));
196 }
197
198 @Override
199 public boolean containsValue(Object value) {
200 Objects.requireNonNull(value, "value must not be null");
201 removeStaleReferences();
202 return map.containsValue(value);
203 }
204
205 @Override
206 public V get(Object key) {
207 Objects.requireNonNull(key, "key must not be null");
208 removeStaleReferences();
209 return map.get(lookupKey(key));
210 }
211
212 @Override
213 public V put(K key, V newValue) {
214 Objects.requireNonNull(key, "key must not be null");
215 Objects.requireNonNull(newValue, "value must not be null");
216 removeStaleReferences();
217 ReferenceKey<K> entryKey = entryKey(key);
218 // If {@code put} returns non-null then was actually a {@code replace}
219 // and older key was used. In that case the new key was not used and the
220 // reference marked stale.
221 V oldValue = map.put(entryKey, newValue);
222 if (oldValue != null) {
223 entryKey.unused();
224 }
225 return oldValue;
226 }
227
228 @Override
229 public V remove(Object key) {
230 // Rely on gc to clean up old key.
231 return map.remove(lookupKey(key));
232 }
233
234 @Override
235 public void putAll(Map<? extends K, ? extends V> m) {
236 removeStaleReferences();
237 for (Entry<? extends K, ? extends V> entry : m.entrySet()) {
238 K key = entry.getKey();
239 V value = entry.getValue();
240 put(key, value);
241 }
242 }
243
244 @Override
245 public void clear() {
246 removeStaleReferences();
247 // Rely on gc to clean up old keys.
248 map.clear();
249 }
250
251 /**
252 * Common routine for collecting the current set of keys.
253 *
254 * @return {@link Stream} of valid keys (unwrapped)
255 */
256 private Stream<K> filterKeySet() {
257 return map.keySet()
258 .stream()
259 .map(ReferenceKey::get)
260 .filter(Objects::nonNull);
261 }
262
263 @Override
264 public Set<K> keySet() {
265 removeStaleReferences();
266 return filterKeySet().collect(Collectors.toSet());
267 }
268
269 @Override
270 public Collection<V> values() {
271 removeStaleReferences();
272 return map.values();
273 }
274
275 @Override
276 public Set<Entry<K, V>> entrySet() {
277 removeStaleReferences();
278 return filterKeySet()
279 .map(k -> new AbstractMap.SimpleEntry<>(k, get(k)))
280 .collect(Collectors.toSet());
281 }
282
283 @Override
284 public V putIfAbsent(K key, V newValue) {
285 removeStaleReferences();
286 ReferenceKey<K> entryKey = entryKey(key);
287 // If {@code putIfAbsent} returns non-null then was actually a
288 // {@code replace} and older key was used. In that case the new key was
289 // not used and the reference marked stale.
290 V oldValue = map.putIfAbsent(entryKey, newValue);
291 if (oldValue != null) {
292 entryKey.unused();
293 }
294 return oldValue;
295 }
296
297 @Override
298 public boolean remove(Object key, Object value) {
299 // Rely on gc to clean up old key.
300 return map.remove(lookupKey(key), value);
301 }
302
303 @Override
304 public boolean replace(K key, V oldValue, V newValue) {
305 removeStaleReferences();
306 // If replace is successful then the older key will be used and the
307 // lookup key will suffice.
308 return map.replace(lookupKey(key), oldValue, newValue);
309 }
310
311 @Override
312 public V replace(K key, V value) {
313 removeStaleReferences();
314 // If replace is successful then the older key will be used and the
315 // lookup key will suffice.
316 return map.replace(lookupKey(key), value);
317 }
318
319 @Override
320 public String toString() {
321 removeStaleReferences();
322 return filterKeySet()
323 .map(k -> k + "=" + get(k))
324 .collect(Collectors.joining(", ", "{", "}"));
325 }
326
327 /**
328 * Removes enqueued weak references from map.
329 */
330 public void removeStaleReferences() {
331 while (true) {
332 Object key = stale.poll();
333 if (key == null) {
334 break;
335 }
336 map.remove(key);
337 }
338 }
339
340 /**
341 * Puts an entry where the key and the value are the same. Used for
342 * interning values in a set.
343 *
344 * @implNote Requires a {@link ReferencedKeyMap} whose {@code V} type
345 * is a {@code ReferenceKey<K>}. Otherwise, a {@link ClassCastException} will
346 * be thrown.
347 *
348 * @param setMap {@link ReferencedKeyMap} where interning takes place
349 * @param key key to add
350 *
351 * @param <T> type of key
352 *
353 * @return the old key instance if found otherwise the new key instance
354 *
355 * @throws ClassCastException if {@code V} is not {@code EntryKey<T>}
356 */
357 static <T> T intern(ReferencedKeyMap<T, ReferenceKey<T>> setMap, T key) {
358 T value = existingKey(setMap, key);
359 if (value != null) {
360 return value;
361 }
362 return internKey(setMap, key);
363 }
364
365 /**
366 * Puts an entry where the key and the value are the same. Used for
367 * interning values in a set.
368 *
369 * @implNote Requires a {@link ReferencedKeyMap} whose {@code V} type
370 * is a {@code ReferenceKey<K>}. Otherwise, a {@link ClassCastException} will
371 * be thrown.
372 *
373 * @param setMap {@link ReferencedKeyMap} where interning takes place
374 * @param key key to add
375 * @param interner operation to apply to key before adding to map
376 *
377 * @param <T> type of key
378 *
379 * @return the old key instance if found otherwise the new key instance
380 *
381 * @throws ClassCastException if {@code V} is not {@code EntryKey<T>}
382 *
383 * @implNote This version of intern should not be called during phase1
384 * using a lambda. Use an UnaryOperator instance instead.
385 */
386 static <T> T intern(ReferencedKeyMap<T, ReferenceKey<T>> setMap, T key, UnaryOperator<T> interner) {
387 T value = existingKey(setMap, key);
388 if (value != null) {
389 return value;
390 }
391 key = interner.apply(key);
392 return internKey(setMap, key);
393 }
394
395 /**
396 * Check if the key already exists in the map.
397 *
398 * @param setMap {@link ReferencedKeyMap} where interning takes place
399 * @param key key to test
400 *
401 * @param <T> type of key
402 *
403 * @return key if found otherwise null
404 */
405 private static <T> T existingKey(ReferencedKeyMap<T, ReferenceKey<T>> setMap, T key) {
406 setMap.removeStaleReferences();
407 ReferenceKey<T> entryKey = setMap.get(setMap.lookupKey(key));
408 return entryKey != null ? entryKey.get() : null;
409 }
410
411 /**
412 * Attempt to add key to map.
413 *
414 * @param setMap {@link ReferencedKeyMap} where interning takes place
415 * @param key key to add
416 *
417 * @param <T> type of key
418 *
419 * @return the old key instance if found otherwise the new key instance
420 */
421 private static <T> T internKey(ReferencedKeyMap<T, ReferenceKey<T>> setMap, T key) {
422 ReferenceKey<T> entryKey = setMap.entryKey(key);
423 T interned;
424 do {
425 setMap.removeStaleReferences();
426 ReferenceKey<T> existing = setMap.map.putIfAbsent(entryKey, entryKey);
427 if (existing == null) {
428 return key;
429 } else {
430 // If {@code putIfAbsent} returns non-null then was actually a
431 // {@code replace} and older key was used. In that case the new
432 // key was not used and the reference marked stale.
433 interned = existing.get();
434 if (interned != null) {
435 entryKey.unused();
436 }
437 }
438 } while (interned == null);
439 return interned;
440 }
441
442
443 /**
444 * Attempt to add key to map if absent.
445 *
446 * @param setMap {@link ReferencedKeyMap} where interning takes place
447 * @param key key to add
448 *
449 * @param <T> type of key
450 *
451 * @return true if the key was added
452 */
453 static <T> boolean internAddKey(ReferencedKeyMap<T, ReferenceKey<T>> setMap, T key) {
454 ReferenceKey<T> entryKey = setMap.entryKey(key);
455 setMap.removeStaleReferences();
456 ReferenceKey<T> existing = setMap.map.putIfAbsent(entryKey, entryKey);
457 if (existing == null) {
458 return true;
459 } else {
460 // If {@code putIfAbsent} returns non-null then was actually a
461 // {@code replace} and older key was used. In that case the new
462 // key was not used and the reference marked stale.
463 entryKey.unused();
464 return false;
465 }
466 }
467
468 }