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