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