1/* 2 * Copyright (c) 2016, 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 */ 25package java.lang; 26 27import java.lang.ref.Reference; 28import java.lang.ref.ReferenceQueue; 29import java.lang.ref.WeakReference; 30import java.util.Collection; 31import java.util.Objects; 32import java.util.concurrent.ConcurrentHashMap; 33import java.util.function.BiFunction; 34 35/** 36 * A WeakHashMap-like data structure that uses a pair of weakly-referenced keys 37 * with identity equality semantics to associate a strongly-referenced value. 38 * Unlike WeakHashMap, this data structure is thread-safe. 39 * 40 * @paramthe type of 1st key in key pair 41 * @param the type of 2nd key in key pair 42 * @param <V> the type of value 43 * @author Peter Levart 44 */ 45final class WeakPairMap<K1, K2, V> { 46 47 private final ConcurrentHashMap<Pair<K1, K2>, V> map = new ConcurrentHashMap<>(); 48 private final ReferenceQueue<Object> queue = new ReferenceQueue<>(); 49 50 /** 51 * Tests if the specified pair of keys are associated with a value 52 * in the WeakPairMap. 53 * 54 * @param k1 the 1st of the pair of keys 55 * @param k2 the 2nd of the pair of keys 56 * @return true if and only if the specified key pair is in this WeakPairMap, 57 * as determined by the identity comparison; false otherwise 58 * @throws NullPointerException if any of the specified keys is null 59 */ 60 public boolean containsKeyPair(K1 k1, K2 k2) { 61 expungeStaleAssociations(); 62 return map.containsKey(Pair.lookup(k1, k2)); 63 } 64 65 /** 66 * Returns the value to which the specified pair of keys is mapped, or null 67 * if this WeakPairMap contains no mapping for the key pair. 68 * <p>More formally, if this WeakPairMap contains a mapping from a key pair 69 * {@code (_k1, _k2)} to a value {@code v} such that 70 * {@code k1 == _k1 && k2 == _k2}, then this method returns {@code v}; 71 * otherwise it returns {@code null}. 72 * (There can be at most one such mapping.) 73 * 74 * @param k1 the 1st of the pair of keys for which the mapped value is to 75 * be returned 76 * @param k2 the 2nd of the pair of keys for which the mapped value is to 77 * be returned 78 * @return the value to which the specified key pair is mapped, or null if 79 * this map contains no mapping for the key pair 80 * @throws NullPointerException if any of the specified keys is null 81 */ 82 public V get(K1 k1, K2 k2) { 83 expungeStaleAssociations(); 84 return map.get(Pair.lookup(k1, k2)); 85 } 86 87 /** 88 * Maps the specified key pair to the specified value in this WeakPairMap. 89 * Neither the keys nor the value can be null. 90 * <p>The value can be retrieved by calling the {@link #get} method 91 * with the the same keys (compared by identity). 92 * 93 * @param k1 the 1st of the pair of keys with which the specified value is to 94 * be associated 95 * @param k2 the 2nd of the pair of keys with which the specified value is to 96 * be associated 97 * @param v value to be associated with the specified key pair 98 * @return the previous value associated with key pair, or {@code null} if 99 * there was no mapping for key pair 100 * @throws NullPointerException if any of the specified keys or value is null 101 */ 102 public V put(K1 k1, K2 k2, V v) { 103 expungeStaleAssociations(); 104 return map.put(Pair.weak(k1, k2, queue), v); 105 } 106 107 /** 108 * If the specified key pair is not already associated with a value, 109 * associates it with the given value and returns {@code null}, else does 110 * nothing and returns the currently associated value. 111 * 112 * @param k1 the 1st of the pair of keys with which the specified value is to 113 * be associated 114 * @param k2 the 2nd of the pair of keys with which the specified value is to 115 * be associated 116 * @param v value to be associated with the specified key pair 117 * @return the previous value associated with key pair, or {@code null} if 118 * there was no mapping for key pair 119 * @throws NullPointerException if any of the specified keys or value is null 120 */ 121 public V putIfAbsent(K1 k1, K2 k2, V v) { 122 expungeStaleAssociations(); 123 return map.putIfAbsent(Pair.weak(k1, k2, queue), v); 124 } 125 126 /** 127 * If the specified key pair is not already associated with a value, 128 * attempts to compute its value using the given mapping function 129 * and enters it into this WeakPairMap unless {@code null}. The entire 130 * method invocation is performed atomically, so the function is 131 * applied at most once per key pair. Some attempted update operations 132 * on this WeakPairMap by other threads may be blocked while computation 133 * is in progress, so the computation should be short and simple, 134 * and must not attempt to update any other mappings of this WeakPairMap. 135 * 136 * @param k1 the 1st of the pair of keys with which the 137 * computed value is to be associated 138 * @param k2 the 2nd of the pair of keys with which the 139 * computed value is to be associated 140 * @param mappingFunction the function to compute a value 141 * @return the current (existing or computed) value associated with 142 * the specified key pair, or null if the computed value is null 143 * @throws NullPointerException if any of the specified keys or 144 * mappingFunction is null 145 * @throws IllegalStateException if the computation detectably 146 * attempts a recursive update to this map 147 * that would otherwise never complete 148 * @throws RuntimeException or Error if the mappingFunction does so, in 149 * which case the mapping is left unestablished 150 */ 151 public V computeIfAbsent(K1 k1, K2 k2, 152 BiFunction<? super K1, ? super K2, ? extends V> 153 mappingFunction) { 154 expungeStaleAssociations(); 155 try { 156 return map.computeIfAbsent( 157 Pair.weak(k1, k2, queue), 158 pair -> mappingFunction.apply(pair.first(), pair.second())); 159 } finally { 160 Reference.reachabilityFence(k1); 161 Reference.reachabilityFence(k2); 162 } 163 } 164 165 /** 166 * Returns a {@link Collection} view of the values contained in this 167 * WeakPairMap. The collection is backed by the WeakPairMap, so changes to 168 * the map are reflected in the collection, and vice-versa. The collection 169 * supports element removal, which removes the corresponding 170 * mapping from this map, via the {@code Iterator.remove}, 171 * {@code Collection.remove}, {@code removeAll}, 172 * {@code retainAll}, and {@code clear} operations. It does not 173 * support the {@code add} or {@code addAll} operations. 174 * 175 * @return the collection view 176 */ 177 public Collection<V> values() { 178 expungeStaleAssociations(); 179 return map.values(); 180 } 181 182 /** 183 * Removes associations from this WeakPairMap for which at least one of the 184 * keys in key pair has been found weakly-reachable and corresponding 185 * WeakRefPeer(s) enqueued. Called as part of each public operation. 186 */ 187 private void expungeStaleAssociations() { 188 WeakRefPeer<?> peer; 189 while ((peer = (WeakRefPeer<?>) queue.poll()) != null) { 190 map.remove(peer.weakPair()); 191 } 192 } 193 194 /** 195 * Common interface of both {@link Weak} and {@link Lookup} key pairs. 196 */ 197 private interface Pair<K1, K2> { 198 199 static <K1, K2> Pair<K1, K2> weak(K1 k1, K2 k2, 200 ReferenceQueue<Object> queue) { 201 return new Weak<>(k1, k2, queue); 202 } 203 204 static <K1, K2> Pair<K1, K2> lookup(K1 k1, K2 k2) { 205 return new Lookup<>(k1, k2); 206 } 207 208 /** 209 * @return The 1st of the pair of keys (may be null for {@link Weak} 210 * when it gets cleared) 211 */ 212 K1 first(); 213 214 /** 215 * @return The 2nd of the pair of keys (may be null for {@link Weak} 216 * when it gets cleared) 217 */ 218 K2 second(); 219 220 static int hashCode(Object first, Object second) { 221 // assert first != null && second != null; 222 return System.identityHashCode(first) ^ 223 System.identityHashCode(second); 224 } 225 226 static boolean equals(Object first, Object second, Pair<?, ?> p) { 227 return first != null && second != null && 228 first == p.first() && second == p.second(); 229 } 230 231 /** 232 * A Pair where both keys are weakly-referenced. 233 * It is composed of two instances of {@link WeakRefPeer}s: 234 * <pre>{@code 235 * 236 * +-referent-> [K1] +-referent-> [K2] 237 * | | 238 * +----------------+ +----------------+ 239 * | Pair.Weak <: |-----peer----->| (anonymous) <: | 240 * | WeakRefPeer, | | WeakRefPeer | 241 * | Pair |<--weakPair()--| | 242 * +----------------+ +----------------+ 243 * | ^ 244 * | | 245 * +-weakPair()-+ 246 * 247 * }</pre> 248 * <p> 249 * Pair.Weak is used for CHM keys. Both peers are associated with the 250 * same {@link ReferenceQueue} so when either of their referents 251 * becomes weakly-reachable, the corresponding entries can be 252 * {@link #expungeStaleAssociations() expunged} from the map. 253 */ 254 final class Weak<K1, K2> extends WeakRefPeer<K1> implements Pair<K1, K2> { 255 256 // saved hash so it can be retrieved after the reference is cleared 257 private final int hash; 258 // link to <K2> peer 259 private final WeakRefPeer<K2> peer; 260 261 Weak(K1 k1, K2 k2, ReferenceQueue<Object> queue) { 262 super(k1, queue); 263 hash = Pair.hashCode(k1, k2); 264 peer = new WeakRefPeer<>(k2, queue) { 265 // link back to <K1> peer 266 @Override 267 Weak<?, ?> weakPair() { return Weak.this; } 268 }; 269 } 270 271 @Override 272 Weak<?, ?> weakPair() { 273 return this; 274 } 275 276 @Override 277 public K1 first() { 278 return get(); 279 } 280 281 @Override 282 public K2 second() { 283 return peer.get(); 284 } 285 286 @Override 287 public int hashCode() { 288 return hash; 289 } 290 291 @Override 292 public boolean equals(Object obj) { 293 return this == obj || 294 (obj instanceof Pair && 295 Pair.equals(first(), second(), (Pair<?, ?>) obj)); 296 } 297 } 298 299 /** 300 * Optimized lookup Pair, used as lookup key in methods like 301 * {@link java.util.Map#get(Object)} or 302 * {@link java.util.Map#containsKey(Object)}) where 303 * there is a great chance its allocation is eliminated 304 * by escape analysis when such lookups are inlined by JIT. 305 * All its methods are purposely designed so that 'this' is never 306 * passed to any other method or used as identity. 307 */ 308 final class Lookup<K1, K2> implements Pair<K1, K2> { 309 private final K1 k1; 310 private final K2 k2; 311 312 Lookup(K1 k1, K2 k2) { 313 this.k1 = Objects.requireNonNull(k1); 314 this.k2 = Objects.requireNonNull(k2); 315 } 316 317 @Override 318 public K1 first() { 319 return k1; 320 } 321 322 @Override 323 public K2 second() { 324 return k2; 325 } 326 327 @Override 328 public int hashCode() { 329 return Pair.hashCode(k1, k2); 330 } 331 332 @Override 333 public boolean equals(Object obj) { 334 return obj instanceof Pair && 335 Pair.equals(k1, k2, (Pair<?, ?>) obj); 336 } 337 } 338 } 339 340 /** 341 * Common abstract supertype of a pair of WeakReference peers. 342 */ 343 private static abstract class WeakRefPeer<K> extends WeakReference<K> { 344 345 WeakRefPeer(K k, ReferenceQueue<Object> queue) { 346 super(Objects.requireNonNull(k), queue); 347 } 348 349 /** 350 * @return the {@link Pair.Weak} side of the pair of peers. 351 */ 352 abstract Pair.Weak<?, ?> weakPair(); 353 } 354} 355