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