1 /* 2 * Written by Doug Lea with assistance from members of JCP JSR-166 3 * Expert Group and released to the public domain, as explained at 4 * http://creativecommons.org/publicdomain/zero/1.0/ 5 */ 6 7 package java.util.concurrent; 8 9 import java.util.Map; 10 import java.util.Objects; 11 import java.util.function.BiConsumer; 12 import java.util.function.BiFunction; 13 import java.util.function.Function; 14 15 // BEGIN android-note 16 // removed link to collections framework docs 17 // fixed framework docs link to "Collection#optional" 18 // END android-note 19 20 /** 21 * A {@link java.util.Map} providing thread safety and atomicity 22 * guarantees. 23 * 24 * <p>To maintain the specified guarantees, default implementations of 25 * methods including {@link #putIfAbsent} inherited from {@link Map} 26 * must be overridden by implementations of this interface. Similarly, 27 * implementations of the collections returned by methods {@link 28 * #keySet}, {@link #values}, and {@link #entrySet} must override 29 * methods such as {@code removeIf} when necessary to 30 * preserve atomicity guarantees. 31 * 32 * <p>Memory consistency effects: As with other concurrent 33 * collections, actions in a thread prior to placing an object into a 34 * {@code ConcurrentMap} as a key or value 35 * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a> 36 * actions subsequent to the access or removal of that object from 37 * the {@code ConcurrentMap} in another thread. 38 * 39 * @since 1.5 40 * @author Doug Lea 41 * @param <K> the type of keys maintained by this map 42 * @param <V> the type of mapped values 43 */ 44 public interface ConcurrentMap<K,V> extends Map<K,V> { 45 46 /** 47 * {@inheritDoc} 48 * 49 * @implNote This implementation assumes that the ConcurrentMap cannot 50 * contain null values and {@code get()} returning null unambiguously means 51 * the key is absent. Implementations which support null values 52 * <strong>must</strong> override this default implementation. 53 * 54 * @throws ClassCastException {@inheritDoc} 55 * @throws NullPointerException {@inheritDoc} 56 * @since 1.8 57 */ 58 @Override getOrDefault(Object key, V defaultValue)59 default V getOrDefault(Object key, V defaultValue) { 60 V v; 61 return ((v = get(key)) != null) ? v : defaultValue; 62 } 63 64 /** 65 * {@inheritDoc} 66 * 67 * @implSpec The default implementation is equivalent to, for this 68 * {@code map}: 69 * <pre> {@code 70 * for (Map.Entry<K,V> entry : map.entrySet()) { 71 * action.accept(entry.getKey(), entry.getValue()); 72 * }}</pre> 73 * 74 * @implNote The default implementation assumes that 75 * {@code IllegalStateException} thrown by {@code getKey()} or 76 * {@code getValue()} indicates that the entry has been removed and cannot 77 * be processed. Operation continues for subsequent entries. 78 * 79 * @throws NullPointerException {@inheritDoc} 80 * @since 1.8 81 */ 82 @Override forEach(BiConsumer<? super K, ? super V> action)83 default void forEach(BiConsumer<? super K, ? super V> action) { 84 Objects.requireNonNull(action); 85 for (Map.Entry<K,V> entry : entrySet()) { 86 K k; 87 V v; 88 try { 89 k = entry.getKey(); 90 v = entry.getValue(); 91 } catch (IllegalStateException ise) { 92 // this usually means the entry is no longer in the map. 93 continue; 94 } 95 action.accept(k, v); 96 } 97 } 98 99 /** 100 * If the specified key is not already associated 101 * with a value, associates it with the given value. 102 * This is equivalent to, for this {@code map}: 103 * <pre> {@code 104 * if (!map.containsKey(key)) 105 * return map.put(key, value); 106 * else 107 * return map.get(key);}</pre> 108 * 109 * except that the action is performed atomically. 110 * 111 * @implNote This implementation intentionally re-abstracts the 112 * inappropriate default provided in {@code Map}. 113 * 114 * @param key key with which the specified value is to be associated 115 * @param value value to be associated with the specified key 116 * @return the previous value associated with the specified key, or 117 * {@code null} if there was no mapping for the key. 118 * (A {@code null} return can also indicate that the map 119 * previously associated {@code null} with the key, 120 * if the implementation supports null values.) 121 * @throws UnsupportedOperationException if the {@code put} operation 122 * is not supported by this map 123 * @throws ClassCastException if the class of the specified key or value 124 * prevents it from being stored in this map 125 * @throws NullPointerException if the specified key or value is null, 126 * and this map does not permit null keys or values 127 * @throws IllegalArgumentException if some property of the specified key 128 * or value prevents it from being stored in this map 129 */ putIfAbsent(K key, V value)130 V putIfAbsent(K key, V value); 131 132 /** 133 * Removes the entry for a key only if currently mapped to a given value. 134 * This is equivalent to, for this {@code map}: 135 * <pre> {@code 136 * if (map.containsKey(key) 137 * && Objects.equals(map.get(key), value)) { 138 * map.remove(key); 139 * return true; 140 * } else { 141 * return false; 142 * }}</pre> 143 * 144 * except that the action is performed atomically. 145 * 146 * @implNote This implementation intentionally re-abstracts the 147 * inappropriate default provided in {@code Map}. 148 * 149 * @param key key with which the specified value is associated 150 * @param value value expected to be associated with the specified key 151 * @return {@code true} if the value was removed 152 * @throws UnsupportedOperationException if the {@code remove} operation 153 * is not supported by this map 154 * @throws ClassCastException if the key or value is of an inappropriate 155 * type for this map 156 * (<a href="../Collection.html#optional-restrictions">optional</a>) 157 * @throws NullPointerException if the specified key or value is null, 158 * and this map does not permit null keys or values 159 * (<a href="../Collection.html#optional-restrictions">optional</a>) 160 */ remove(Object key, Object value)161 boolean remove(Object key, Object value); 162 163 /** 164 * Replaces the entry for a key only if currently mapped to a given value. 165 * This is equivalent to, for this {@code map}: 166 * <pre> {@code 167 * if (map.containsKey(key) 168 * && Objects.equals(map.get(key), oldValue)) { 169 * map.put(key, newValue); 170 * return true; 171 * } else { 172 * return false; 173 * }}</pre> 174 * 175 * except that the action is performed atomically. 176 * 177 * @implNote This implementation intentionally re-abstracts the 178 * inappropriate default provided in {@code Map}. 179 * 180 * @param key key with which the specified value is associated 181 * @param oldValue value expected to be associated with the specified key 182 * @param newValue value to be associated with the specified key 183 * @return {@code true} if the value was replaced 184 * @throws UnsupportedOperationException if the {@code put} operation 185 * is not supported by this map 186 * @throws ClassCastException if the class of a specified key or value 187 * prevents it from being stored in this map 188 * @throws NullPointerException if a specified key or value is null, 189 * and this map does not permit null keys or values 190 * @throws IllegalArgumentException if some property of a specified key 191 * or value prevents it from being stored in this map 192 */ replace(K key, V oldValue, V newValue)193 boolean replace(K key, V oldValue, V newValue); 194 195 /** 196 * Replaces the entry for a key only if currently mapped to some value. 197 * This is equivalent to, for this {@code map}: 198 * <pre> {@code 199 * if (map.containsKey(key)) 200 * return map.put(key, value); 201 * else 202 * return null;}</pre> 203 * 204 * except that the action is performed atomically. 205 * 206 * @implNote This implementation intentionally re-abstracts the 207 * inappropriate default provided in {@code Map}. 208 * 209 * @param key key with which the specified value is associated 210 * @param value value to be associated with the specified key 211 * @return the previous value associated with the specified key, or 212 * {@code null} if there was no mapping for the key. 213 * (A {@code null} return can also indicate that the map 214 * previously associated {@code null} with the key, 215 * if the implementation supports null values.) 216 * @throws UnsupportedOperationException if the {@code put} operation 217 * is not supported by this map 218 * @throws ClassCastException if the class of the specified key or value 219 * prevents it from being stored in this map 220 * @throws NullPointerException if the specified key or value is null, 221 * and this map does not permit null keys or values 222 * @throws IllegalArgumentException if some property of the specified key 223 * or value prevents it from being stored in this map 224 */ replace(K key, V value)225 V replace(K key, V value); 226 227 /** 228 * {@inheritDoc} 229 * 230 * @implSpec 231 * <p>The default implementation is equivalent to, for this {@code map}: 232 * <pre> {@code 233 * for (Map.Entry<K,V> entry : map.entrySet()) { 234 * K k; 235 * V v; 236 * do { 237 * k = entry.getKey(); 238 * v = entry.getValue(); 239 * } while (!map.replace(k, v, function.apply(k, v))); 240 * }}</pre> 241 * 242 * The default implementation may retry these steps when multiple 243 * threads attempt updates including potentially calling the function 244 * repeatedly for a given key. 245 * 246 * <p>This implementation assumes that the ConcurrentMap cannot contain null 247 * values and {@code get()} returning null unambiguously means the key is 248 * absent. Implementations which support null values <strong>must</strong> 249 * override this default implementation. 250 * 251 * @throws UnsupportedOperationException {@inheritDoc} 252 * @throws NullPointerException {@inheritDoc} 253 * @throws ClassCastException {@inheritDoc} 254 * @throws IllegalArgumentException {@inheritDoc} 255 * @since 1.8 256 */ 257 @Override replaceAll(BiFunction<? super K, ? super V, ? extends V> function)258 default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 259 Objects.requireNonNull(function); 260 forEach((k,v) -> { 261 while (!replace(k, v, function.apply(k, v))) { 262 // v changed or k is gone 263 if ( (v = get(k)) == null) { 264 // k is no longer in the map. 265 break; 266 } 267 } 268 }); 269 } 270 271 /** 272 * {@inheritDoc} 273 * 274 * @implSpec 275 * The default implementation is equivalent to the following steps for this 276 * {@code map}: 277 * 278 * <pre> {@code 279 * V oldValue, newValue; 280 * return ((oldValue = map.get(key)) == null 281 * && (newValue = mappingFunction.apply(key)) != null 282 * && (oldValue = map.putIfAbsent(key, newValue)) == null) 283 * ? newValue 284 * : oldValue;}</pre> 285 * 286 * <p>This implementation assumes that the ConcurrentMap cannot contain null 287 * values and {@code get()} returning null unambiguously means the key is 288 * absent. Implementations which support null values <strong>must</strong> 289 * override this default implementation. 290 * 291 * @throws UnsupportedOperationException {@inheritDoc} 292 * @throws ClassCastException {@inheritDoc} 293 * @throws NullPointerException {@inheritDoc} 294 * @throws IllegalArgumentException {@inheritDoc} 295 * @since 1.8 296 */ 297 @Override computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)298 default V computeIfAbsent(K key, 299 Function<? super K, ? extends V> mappingFunction) { 300 Objects.requireNonNull(mappingFunction); 301 V oldValue, newValue; 302 return ((oldValue = get(key)) == null 303 && (newValue = mappingFunction.apply(key)) != null 304 && (oldValue = putIfAbsent(key, newValue)) == null) 305 ? newValue 306 : oldValue; 307 } 308 309 /** 310 * {@inheritDoc} 311 * 312 * @implSpec 313 * The default implementation is equivalent to performing the following 314 * steps for this {@code map}: 315 * 316 * <pre> {@code 317 * for (V oldValue; (oldValue = map.get(key)) != null; ) { 318 * V newValue = remappingFunction.apply(key, oldValue); 319 * if ((newValue == null) 320 * ? map.remove(key, oldValue) 321 * : map.replace(key, oldValue, newValue)) 322 * return newValue; 323 * } 324 * return null;}</pre> 325 * When multiple threads attempt updates, map operations and the 326 * remapping function may be called multiple times. 327 * 328 * <p>This implementation assumes that the ConcurrentMap cannot contain null 329 * values and {@code get()} returning null unambiguously means the key is 330 * absent. Implementations which support null values <strong>must</strong> 331 * override this default implementation. 332 * 333 * @throws UnsupportedOperationException {@inheritDoc} 334 * @throws ClassCastException {@inheritDoc} 335 * @throws NullPointerException {@inheritDoc} 336 * @throws IllegalArgumentException {@inheritDoc} 337 * @since 1.8 338 */ 339 @Override computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)340 default V computeIfPresent(K key, 341 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 342 Objects.requireNonNull(remappingFunction); 343 for (V oldValue; (oldValue = get(key)) != null; ) { 344 V newValue = remappingFunction.apply(key, oldValue); 345 if ((newValue == null) 346 ? remove(key, oldValue) 347 : replace(key, oldValue, newValue)) 348 return newValue; 349 } 350 return null; 351 } 352 353 /** 354 * {@inheritDoc} 355 * 356 * @implSpec 357 * The default implementation is equivalent to performing the following 358 * steps for this {@code map}: 359 * 360 * <pre> {@code 361 * for (;;) { 362 * V oldValue = map.get(key); 363 * V newValue = remappingFunction.apply(key, oldValue); 364 * if (newValue != null) { 365 * if ((oldValue != null) 366 * ? map.replace(key, oldValue, newValue) 367 * : map.putIfAbsent(key, newValue) == null) 368 * return newValue; 369 * } else if (oldValue == null || map.remove(key, oldValue)) { 370 * return null; 371 * } 372 * }}</pre> 373 * When multiple threads attempt updates, map operations and the 374 * remapping function may be called multiple times. 375 * 376 * <p>This implementation assumes that the ConcurrentMap cannot contain null 377 * values and {@code get()} returning null unambiguously means the key is 378 * absent. Implementations which support null values <strong>must</strong> 379 * override this default implementation. 380 * 381 * @throws UnsupportedOperationException {@inheritDoc} 382 * @throws ClassCastException {@inheritDoc} 383 * @throws NullPointerException {@inheritDoc} 384 * @throws IllegalArgumentException {@inheritDoc} 385 * @since 1.8 386 */ 387 @Override compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)388 default V compute(K key, 389 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 390 retry: for (;;) { 391 V oldValue = get(key); 392 // if putIfAbsent fails, opportunistically use its return value 393 haveOldValue: for (;;) { 394 V newValue = remappingFunction.apply(key, oldValue); 395 if (newValue != null) { 396 if (oldValue != null) { 397 if (replace(key, oldValue, newValue)) 398 return newValue; 399 } 400 else if ((oldValue = putIfAbsent(key, newValue)) == null) 401 return newValue; 402 else continue haveOldValue; 403 } else if (oldValue == null || remove(key, oldValue)) { 404 return null; 405 } 406 continue retry; 407 } 408 } 409 } 410 411 /** 412 * {@inheritDoc} 413 * 414 * @implSpec 415 * The default implementation is equivalent to performing the following 416 * steps for this {@code map}: 417 * 418 * <pre> {@code 419 * for (;;) { 420 * V oldValue = map.get(key); 421 * if (oldValue != null) { 422 * V newValue = remappingFunction.apply(oldValue, value); 423 * if (newValue != null) { 424 * if (map.replace(key, oldValue, newValue)) 425 * return newValue; 426 * } else if (map.remove(key, oldValue)) { 427 * return null; 428 * } 429 * } else if (map.putIfAbsent(key, value) == null) { 430 * return value; 431 * } 432 * }}</pre> 433 * When multiple threads attempt updates, map operations and the 434 * remapping function may be called multiple times. 435 * 436 * <p>This implementation assumes that the ConcurrentMap cannot contain null 437 * values and {@code get()} returning null unambiguously means the key is 438 * absent. Implementations which support null values <strong>must</strong> 439 * override this default implementation. 440 * 441 * @throws UnsupportedOperationException {@inheritDoc} 442 * @throws ClassCastException {@inheritDoc} 443 * @throws NullPointerException {@inheritDoc} 444 * @throws IllegalArgumentException {@inheritDoc} 445 * @since 1.8 446 */ 447 @Override merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)448 default V merge(K key, V value, 449 BiFunction<? super V, ? super V, ? extends V> remappingFunction) { 450 Objects.requireNonNull(remappingFunction); 451 Objects.requireNonNull(value); 452 retry: for (;;) { 453 V oldValue = get(key); 454 // if putIfAbsent fails, opportunistically use its return value 455 haveOldValue: for (;;) { 456 if (oldValue != null) { 457 V newValue = remappingFunction.apply(oldValue, value); 458 if (newValue != null) { 459 if (replace(key, oldValue, newValue)) 460 return newValue; 461 } else if (remove(key, oldValue)) { 462 return null; 463 } 464 continue retry; 465 } else { 466 if ((oldValue = putIfAbsent(key, value)) == null) 467 return value; 468 continue haveOldValue; 469 } 470 } 471 } 472 } 473 } 474