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 }