src/share/classes/java/util/Map.java

Print this page
rev 6845 : 8004518: Add in-place operations to Map
8010122: Add atomic operations to Map
Reviewed-by: darcy, briangoetz, mduigou
Contributed-by: Doug Lea <dl at cs.oswego.edu>, Henry Jen <henry.jen@oracle.com>, Akhil Arora <akhil.arora@oracle.com>, Peter Levart <peter.levart@gmail.com>

@@ -1,7 +1,7 @@
 /*
- * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License version 2 only, as
  * published by the Free Software Foundation.  Oracle designates this

@@ -23,10 +23,14 @@
  * questions.
  */
 
 package java.util;
 
+import java.util.function.BiConsumer;
+import java.util.function.BiFunction;
+import java.util.function.Function;
+
 /**
  * An object that maps keys to values.  A map cannot contain duplicate keys;
  * each key can map to at most one value.
  *
  * <p>This interface takes the place of the <tt>Dictionary</tt> class, which

@@ -473,6 +477,586 @@
      * @see Object#equals(Object)
      * @see #equals(Object)
      */
     int hashCode();
 
+    // Defaultable methods
+
+    /**
+    *  Returns the value to which the specified key is mapped,
+    *  or {@code defaultValue} if this map contains no mapping
+    *  for the key.
+    *
+    * @param key the key whose associated value is to be returned
+    * @return the value to which the specified key is mapped, or
+    * {@code defaultValue} if this map contains no mapping for the key
+    * @throws ClassCastException if the key is of an inappropriate type for
+    * this map
+    * (<a href="Collection.html#optional-restrictions">optional</a>)
+    * @throws NullPointerException if the specified key is null and this map
+    * does not permit null keys
+    * (<a href="Collection.html#optional-restrictions">optional</a>)
+    */
+    default V getOrDefault(Object key, V defaultValue) {
+        V v;
+        return (null != (v = get(key)))
+            ? v
+            : containsKey(key) ? null : defaultValue;
+    }
+
+    /**
+     * Performs the given action on each entry in this map, in the
+     * order entries are returned by an entry set iterator, until all entries
+     * have been processed or the action throws an {@code Exception}.
+     * Exceptions thrown by the action are relayed to the caller.
+     *
+     * <p>The default implementation should be overridden by implementations if
+     * they can provide a more performant implementation than an iterator-based
+     * one.
+     *
+     * <p>The default implementation makes no guarantees about
+     * synchronization or atomicity properties of this method. Any
+     * class overriding this method must specify its concurrency
+     * properties. In particular, all implementations of
+     * subinterface {@link java.util.concurrent.ConcurrentMap}
+     * must ensure that this operation is performed atomically.
+     *
+     * @implSpec
+     * <p>The default implementation is equivalent to, for this {@code map}:
+     * <pre> {@code
+     *     for ((Map.Entry<K, V> entry : map.entrySet())
+     *         action.accept(entry.getKey(), entry.getValue());
+     * }</pre>
+     *
+     * @param action The action to be performed for each entry
+     * @throws NullPointerException if the specified action is null
+     * @since 1.8
+     */
+    default void forEach(BiConsumer<? super K, ? super V> action) {
+        Objects.requireNonNull(action);
+        for (Map.Entry<K, V> entry : entrySet()) {
+            action.accept(entry.getKey(), entry.getValue());
+        }
+    }
+
+    /**
+     * Apply the specified function to each entry in this map, in the
+     * order entries are returned by an entry set iterator, and replacing
+     * each entry's value with the result of calling the function's
+     * {@link BiFunction#apply(Object, Object) BiFunction.apply(K key, V, value)}
+     * method with the current entry's key and value.  Exceptions thrown by the
+     * function are relayed to the caller.
+     *
+     * <p>The default implementation makes no guarantees about
+     * synchronization or atomicity properties of this method. Any
+     * class overriding this method must specify its concurrency
+     * properties. In particular, all implementations of
+     * subinterface {@link java.util.concurrent.ConcurrentMap}
+     * must ensure that this operation is performed atomically.
+     *
+     * @implSpec
+     * <p>The default implementation is equivalent to, for this {@code map}:
+     * <pre> {@code
+     *     for ((Map.Entry<K, V> entry : map.entrySet())
+     *         entry.setValue(function.apply(entry.getKey(), entry.getValue()));
+     * }</pre>
+     *
+     * @param function the function to apply to each entry
+     * @throws UnsupportedOperationException if the <tt>put</tt> operation
+     *         is not supported by this map
+     * @throws ClassCastException if the class of the specified value
+     *         prevents it from being stored in the backing map
+     * @throws NullPointerException if the specified function is null, or the
+     *         specified key or value is null, and this map does not permit null
+     *         keys or values
+     * @throws IllegalArgumentException if some property of the specified key
+     *         or value prevents it from being stored in this map
+     * @throws IllegalStateException implementations may, but are not
+     *         required to, throw this exception if the entry has been
+     *         removed from the backing map.
+     * @since 1.8
+     */
+    default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
+        Objects.requireNonNull(function);
+        for (Map.Entry<K, V> entry : entrySet()) {
+            entry.setValue(function.apply(entry.getKey(), entry.getValue()));
+        }
+    }
+
+    /**
+     * If the specified key is not already associated with a value (or is mapped
+     * to {@code null}) associates it with the given value and returns
+     * {@code null}, else returns the current value.
+     *
+     * <p>The default implementation makes no guarantees about
+     * synchronization or atomicity properties of this method. Any
+     * class overriding this method must specify its concurrency
+     * properties. In particular, all implementations of
+     * subinterface {@link java.util.concurrent.ConcurrentMap}
+     * must ensure that this operation is performed atomically.
+     *
+     * @implSpec
+     * The default implementation is equivalent to, for this {@code
+     * map}:
+     *
+     *  <pre> {@code
+     * if (map.get(key) == null)
+     *   return map.put(key, value);
+     * else
+     *   return map.get(key);}</pre>
+     *
+     * @param key key with which the specified value is to be associated
+     * @param value value to be associated with the specified key
+     * @return the previous value associated with the specified key, or
+     *         <tt>null</tt> if there was no mapping for the key.
+     *         (A <tt>null</tt> return can also indicate that the map
+     *         previously associated <tt>null</tt> with the key,
+     *         if the implementation supports null values.)
+     * @throws UnsupportedOperationException if the <tt>put</tt> operation
+     *         is not supported by this map
+     *         (<a href="Collection.html#optional-restrictions">optional</a>)
+     * @throws ClassCastException if the class of the specified key or value
+     *         prevents it from being stored in this map
+     * @throws NullPointerException if the specified key or value is null,
+     *         and this map does not permit null keys or values
+     * @throws IllegalArgumentException if some property of the specified key
+     *         or value prevents it from being stored in this map
+     * @since 1.8
+     */
+    default V putIfAbsent(K key, V value) {
+        V v = get(key);
+        if(v == null) {
+            if(null != put(key, value)) {
+                throw new ConcurrentModificationException();
+            }
+            return null;
+        } else {
+          return v;
+        }
+    }
+
+    /**
+     * Removes the entry for the specified key only if it is currently
+     * mapped to the specified value.
+     *
+     * <p>The default implementation makes no guarantees about
+     * synchronization or atomicity properties of this method. Any
+     * class overriding this method must specify its concurrency
+     * properties. In particular, all implementations of
+     * subinterface {@link java.util.concurrent.ConcurrentMap}
+     * must ensure that this operation is performed atomically.
+     *
+     * @implSpec
+     * The default implementation is equivalent to, for this {@code map}:
+     *
+     * <pre> {@code
+     * if (map.containsKey(key) && Objects.equals(map.get(key), value)) {
+     *   map.remove(key);
+     *   return true;
+     * } else
+     *   return false;}</pre>
+     *
+     * @param key key with which the specified value is associated
+     * @param value value expected to be associated with the specified key
+     * @return <tt>true</tt> if the value was removed
+     * @throws UnsupportedOperationException if the <tt>remove</tt> operation
+     *         is not supported by this map
+     *         (<a href="Collection.html#optional-restrictions">optional</a>)
+     * @throws ClassCastException if the key or value is of an inappropriate
+     *         type for this map
+     *         (<a href="Collection.html#optional-restrictions">optional</a>)
+     * @throws NullPointerException if the specified key or value is null,
+     *         and this map does not permit null keys or values
+     *         (<a href="Collection.html#optional-restrictions">optional</a>)
+     * @since 1.8
+     */
+    default boolean remove(Object key, Object value) {
+        if (!containsKey(key) || !Objects.equals(get(key), value))
+            return false;
+        remove(key);
+        return true;
+    }
+
+    /**
+     * Replaces the entry for the specified key only if currently
+     * mapped to the specified value.
+     *
+     * <p>The default implementation makes no guarantees about
+     * synchronization or atomicity properties of this method. Any
+     * class overriding this method must specify its concurrency
+     * properties. In particular, all implementations of
+     * subinterface {@link java.util.concurrent.ConcurrentMap}
+     * must ensure that this operation is performed atomically.
+     *
+     * @implSpec
+     * The default implementation is equivalent to, for this {@code map}:
+     *
+     * <pre> {@code
+     * if (map.containsKey(key) && Objects.equals(map.get(key), value)) {
+     *   map.put(key, newValue);
+     *   return true;
+     * } else
+     *   return false;}</pre>
+     *
+     * @param key key with which the specified value is associated
+     * @param oldValue value expected to be associated with the specified key
+     * @param newValue value to be associated with the specified key
+     * @return <tt>true</tt> if the value was replaced
+     * @throws UnsupportedOperationException if the <tt>put</tt> operation
+     *         is not supported by this map
+     *         (<a href="Collection.html#optional-restrictions">optional</a>)
+     * @throws ClassCastException if the class of a specified key or value
+     *         prevents it from being stored in this map
+     * @throws NullPointerException if a specified key or value is null,
+     *         and this map does not permit null keys or values
+     * @throws IllegalArgumentException if some property of a specified key
+     *         or value prevents it from being stored in this map
+     * @since 1.8
+     */
+    default boolean replace(K key, V oldValue, V newValue) {
+        if (!containsKey(key) || !Objects.equals(get(key), oldValue))
+            return false;
+        put(key, newValue);
+        return true;
+    }
+
+    /**
+     * Replaces the entry for the specified key only if it is
+     * currently mapped to some value.
+     *
+     * <p>The default implementation makes no guarantees about
+     * synchronization or atomicity properties of this method. Any
+     * class overriding this method must specify its concurrency
+     * properties. In particular, all implementations of
+     * subinterface {@link java.util.concurrent.ConcurrentMap}
+     * must ensure that this operation is performed atomically.
+     *
+     * @implSpec
+     * The default implementation is equivalent to, for this {@code map}:
+     *
+     * <pre> {@code
+     * if (map.containsKey(key)) {
+     *   return map.put(key, value);
+     * } else
+     *   return null;}</pre>
+     *
+     * @param key key with which the specified value is associated
+     * @param value value to be associated with the specified key
+     * @return the previous value associated with the specified key, or
+     *         <tt>null</tt> if there was no mapping for the key.
+     *         (A <tt>null</tt> return can also indicate that the map
+     *         previously associated <tt>null</tt> with the key,
+     *         if the implementation supports null values.)
+     * @throws UnsupportedOperationException if the <tt>put</tt> operation
+     *         is not supported by this map
+     *         (<a href="Collection.html#optional-restrictions">optional</a>)
+     * @throws ClassCastException if the class of the specified key or value
+     *         prevents it from being stored in this map
+     *         (<a href="Collection.html#optional-restrictions">optional</a>)
+     * @throws NullPointerException if the specified key or value is null,
+     *         and this map does not permit null keys or values
+     * @throws IllegalArgumentException if some property of the specified key
+     *         or value prevents it from being stored in this map
+     * @since 1.8
+     */
+    default V replace(K key, V value) {
+        return containsKey(key) ? put(key, value) : null;
+    }
+
+    /**
+     * If the specified key is not already associated with a value (or
+     * is mapped to {@code null}), attempts to compute its value using
+     * the given mapping function and enters it into this map unless
+     * {@code null}.
+     *
+     * <p>If the function returns {@code null} no mapping is recorded. If
+     * the function itself throws an (unchecked) exception, the
+     * exception is rethrown, and no mapping is recorded.  The most
+     * common usage is to construct a new object serving as an initial
+     * mapped value or memoized result, as in:
+     *
+     * <pre> {@code
+     * map.computeIfAbsent(key, k -> new Value(f(k)));}</pre>
+     *
+     * <p>The default implementation makes no guarantees about
+     * synchronization or atomicity properties of this method or the
+     * application of the mapping function. Any class overriding this
+     * method must specify its concurrency properties.  In particular,
+     * all implementations of subinterface {@link
+     * java.util.concurrent.ConcurrentMap} must document whether the
+     * function is applied once atomically only if the value is not
+     * present.  Any class that permits null values must document
+     * whether and how this method distinguishes absence from null
+     * mappings.
+     *
+     * @implSpec
+     * The default implementation is equivalent to the following
+     * steps for this {@code map}, then returning the current value or
+     * {@code null} if now absent:
+     *
+     * <pre> {@code
+     * if (map.get(key) == null) {
+     *   V newValue = mappingFunction.apply(key);
+     *   if (newValue != null)
+     *      map.putIfAbsent(key, newValue);
+     * }}</pre>
+     *
+     * @param key key with which the specified value is to be associated
+     * @param mappingFunction the function to compute a value
+     * @return the current (existing or computed) value associated with
+     *         the specified key, or null if the computed value is null
+     * @throws NullPointerException if the specified key is null and
+     *         this map does not support null keys, or the
+     *         mappingFunction is null
+     * @throws UnsupportedOperationException if the <tt>put</tt> operation
+     *         is not supported by this map
+     *         (<a href="Collection.html#optional-restrictions">optional</a>)
+     * @throws ClassCastException if the class of the specified key or value
+     *         prevents it from being stored in this map
+     *         (<a href="Collection.html#optional-restrictions">optional</a>)
+     * @since 1.8
+     */
+    default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
+        V v, newValue;
+        return ((v = get(key)) == null &&
+                (newValue = mappingFunction.apply(key)) != null &&
+                (v = putIfAbsent(key, newValue)) == null) ? newValue : v;
+    }
+
+    /**
+     * If the value for the specified key is present and non-null,
+     * attempts to compute a new mapping given the key and its current
+     * mapped value.
+     *
+     * <p>If the function returns {@code null}, the mapping is removed (or
+     * remains absent if initially absent).  If the function itself throws an
+     * (unchecked) exception, the exception is rethrown, and the current mapping
+     * is left unchanged.
+     *
+     * <p>The default implementation makes no guarantees about
+     * synchronization or atomicity properties of this method or the
+     * application of the remapping function. Any class overriding
+     * this method must specify its concurrency properties.  In
+     * particular, all implementations of subinterface {@link
+     * java.util.concurrent.ConcurrentMap} must document whether the
+     * function is applied once atomically only if the value is
+     * present.  Any class that permits null values must document
+     * whether and how this method distinguishes absence from null
+     * mappings.
+     *
+     * @implSpec
+     * The default implementation is equivalent to performing the
+     * following steps for this {@code map}, then returning the
+     * current value or {@code null} if now absent:
+     *
+     * <pre> {@code
+     * if (map.get(key) != null) {
+     *   V oldValue = map.get(key);
+     *   V newValue = remappingFunction.apply(key, oldValue);
+     *   if (newValue != null)
+     *     map.replace(key, oldValue, newValue);
+     *   else
+     *     map.remove(key, oldValue);
+     * }}</pre>
+     *
+     * In concurrent contexts, the default implementation may retry
+     * these steps when multiple threads attempt updates.
+     *
+     * @param key key with which the specified value is to be associated
+     * @param remappingFunction the function to compute a value
+     * @return the new value associated with the specified key, or null if none
+     * @throws NullPointerException if the specified key is null and
+     *         this map does not support null keys, or the
+     *         remappingFunction is null
+     * @throws UnsupportedOperationException if the <tt>put</tt> operation
+     *         is not supported by this map
+     *         (<a href="Collection.html#optional-restrictions">optional</a>)
+     * @throws ClassCastException if the class of the specified key or value
+     *         prevents it from being stored in this map
+     *         (<a href="Collection.html#optional-restrictions">optional</a>)
+     * @since 1.8
+     */
+    default V computeIfPresent(K key,
+                               BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+        V v;
+        while ((v = get(key)) != null) {
+            V newValue = remappingFunction.apply(key, v);
+            if (newValue != null) {
+                if (replace(key, v, newValue))
+                    return newValue;
+            }
+            else if (remove(key, v))
+                return null;
+        }
+        return v;
+    }
+
+    /**
+     * Attempts to compute a mapping for the specified key and its
+     * current mapped value (or {@code null} if there is no current
+     * mapping). For example, to either create or append a {@code
+     * String msg} to a value mapping:
+     *
+     * <pre> {@code
+     * map.compute(key, (k, v) -> (v == null) ? msg : v.concat(msg))}</pre>
+     * (Method {@link #merge} is often simpler to use for such purposes.)
+     *
+     * <p>If the function returns {@code null}, the mapping is removed (or
+     * remains absent if initially absent).  If the function itself throws an
+     * (unchecked) exception, the exception is rethrown, and the current mapping
+     * is left unchanged.
+     *
+     * <p>The default implementation makes no guarantees about
+     * synchronization or atomicity properties of this method or the
+     * application of the remapping function. Any class overriding
+     * this method must specify its concurrency properties.  In
+     * particular, all implementations of subinterface {@link
+     * java.util.concurrent.ConcurrentMap} must document whether the
+     * function is applied exactly once atomically. Any class that
+     * permits null values must document whether and how this method
+     * distinguishes absence from null mappings.
+     *
+     * @implSpec
+     * The default implementation is equivalent to
+     * performing the following steps for this {@code map}, then
+     * returning the current value or {@code null} if absent:
+     *
+     * <pre> {@code
+     * V oldValue = map.get(key);
+     * V newValue = remappingFunction.apply(key, oldValue);
+     * if (newValue != null)
+     *   map.replace(key, oldValue, newValue);
+     * else
+     *   map.remove(key, oldValue);
+     * }</pre>
+     *
+     * In concurrent contexts, the default implementation may retry
+     * these steps when multiple threads attempt updates.
+     *
+     * @param key key with which the specified value is to be associated
+     * @param remappingFunction the function to compute a value
+     * @return the new value associated with the specified key, or null if none
+     * @throws NullPointerException if the specified key is null and
+     *         this map does not support null keys, or the
+     *         remappingFunction is null
+     * @throws UnsupportedOperationException if the <tt>put</tt> operation
+     *         is not supported by this map
+     *         (<a href="Collection.html#optional-restrictions">optional</a>)
+     * @throws ClassCastException if the class of the specified key or value
+     *         prevents it from being stored in this map
+     *         (<a href="Collection.html#optional-restrictions">optional</a>)
+     * @since 1.8
+     */
+    default V compute(K key,
+                      BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+        V oldValue = get(key);
+        for (;;) {
+            V newValue = remappingFunction.apply(key, oldValue);
+            if (oldValue != null) {
+                if (newValue != null) {
+                    if (replace(key, oldValue, newValue))
+                        return newValue;
+                }
+                else if (remove(key, oldValue)) {
+                    return null;
+                }
+                oldValue = get(key);
+            }
+            else {
+                if (newValue != null) {
+                    if ((oldValue = putIfAbsent(key, newValue)) == null)
+                        return newValue;
+                }
+                else
+                    return null;
+            }
+        }
+    }
+
+    /**
+     * If the specified key is not already associated with a
+     * (non-null) value, associates it with the given value.
+     * Otherwise, replaces the value with the results of the given
+     * remapping function, or removes if {@code null}. This method may
+     * be of use when combining multiple mapped values for a key.  For
+     * example. to either create or append a {@code String msg} to a
+     * value mapping:
+     *
+     * <pre> {@code
+     * map.merge(key, msg, String::concat)}</pre>
+     *
+     * <p>If the function returns {@code null}, the mapping is removed (or
+     * remains absent if initially absent).  If the function itself throws an
+     * (unchecked) exception, the exception is rethrown, and the current mapping
+     * is left unchanged.
+     *
+     * <p>The default implementation makes no guarantees about
+     * synchronization or atomicity properties of this method or the
+     * application of the remapping function. Any class overriding
+     * this method must specify its concurrency properties.  In
+     * particular, all implementations of subinterface {@link
+     * java.util.concurrent.ConcurrentMap} must document whether the
+     * function is applied exactly once atomically. Any class that
+     * permits null values must document whether and how this method
+     * distinguishes absence from null mappings.
+     *
+     * @implSpec
+     * The default implementation is equivalent to performing the
+     * following steps for this {@code map}, then returning the
+     * current value or {@code null} if absent:
+     *
+     * <pre> {@code
+     * V oldValue = map.get(key);
+     * V newValue = (oldValue == null) ? value :
+     *              remappingFunction.apply(oldValue, value);
+     * if (newValue == null)
+     *   map.remove(key, oldValue);
+     * else if (oldValue == null)
+     *   map.putIfAbsent(key, newValue);
+     * else
+     *   map.replace(key, oldValue, newValue);
+     * }</pre>
+     *
+     * In concurrent contexts, the default implementation may retry
+     * these steps when multiple threads attempt updates.
+     *
+     * @param key key with which the specified value is to be associated
+     * @param value the value to use if absent
+     * @param remappingFunction the function to recompute a value if present
+     * @return the new value associated with the specified key, or null if none
+     * @throws UnsupportedOperationException if the <tt>put</tt> operation
+     *         is not supported by this map
+     *         (<a href="Collection.html#optional-restrictions">optional</a>)
+     * @throws ClassCastException if the class of the specified key or value
+     *         prevents it from being stored in this map
+     *         (<a href="Collection.html#optional-restrictions">optional</a>)
+     * @throws NullPointerException if the specified key is null and
+     *         this map does not support null keys, or the
+     *         remappingFunction is null
+     * @since 1.8
+     */
+    default V merge(K key, V value,
+                    BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
+        V oldValue = get(key);
+        for (;;) {
+            if (oldValue != null) {
+                V newValue = remappingFunction.apply(oldValue, value);
+                if (newValue != null) {
+                    if (replace(key, oldValue, newValue))
+                        return newValue;
+                }
+                else if (remove(key, oldValue)) {
+                    return null;
+                }
+                oldValue = get(key);
+            }
+            else {
+                if (value != null) {
+                    if ((oldValue = putIfAbsent(key, value)) == null)
+                        return value;
+                }
+                else
+                    return null;
+            }
+        }
+    }
 }