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