src/share/classes/java/util/LinkedHashMap.java

Print this page
rev 7360 : 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap
Reviewed-by: forax, duigou, psandoz
Contributed-by: Mike Duigou <mike.duigou@oracle.com>, Remi Forax <forax@univ-mlv.fr>


   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package java.util;
  27 import java.io.*;


  28 
  29 /**
  30  * <p>Hash table and linked list implementation of the <tt>Map</tt> interface,
  31  * with predictable iteration order.  This implementation differs from
  32  * <tt>HashMap</tt> in that it maintains a doubly-linked list running through
  33  * all of its entries.  This linked list defines the iteration ordering,
  34  * which is normally the order in which keys were inserted into the map
  35  * (<i>insertion-order</i>).  Note that insertion order is not affected
  36  * if a key is <i>re-inserted</i> into the map.  (A key <tt>k</tt> is
  37  * reinserted into a map <tt>m</tt> if <tt>m.put(k, v)</tt> is invoked when
  38  * <tt>m.containsKey(k)</tt> would return <tt>true</tt> immediately prior to
  39  * the invocation.)
  40  *
  41  * <p>This implementation spares its clients from the unspecified, generally
  42  * chaotic ordering provided by {@link HashMap} (and {@link Hashtable}),
  43  * without incurring the increased cost associated with {@link TreeMap}.  It
  44  * can be used to produce a copy of a map that has the same order as the
  45  * original, regardless of the original map's implementation:
  46  * <pre>
  47  *     void foo(Map m) {


 277      * indicate that the map contains no mapping for the key; it's also
 278      * possible that the map explicitly maps the key to {@code null}.
 279      * The {@link #containsKey containsKey} operation may be used to
 280      * distinguish these two cases.
 281      */
 282     public V get(Object key) {
 283         Entry<K,V> e = (Entry<K,V>)getEntry(key);
 284         if (e == null)
 285             return null;
 286         e.recordAccess(this);
 287         return e.value;
 288     }
 289 
 290     /**
 291      * Removes all of the mappings from this map.
 292      * The map will be empty after this call returns.
 293      */
 294     public void clear() {
 295         super.clear();
 296         header.before = header.after = header;


























 297     }
 298 
 299     /**
 300      * LinkedHashMap entry.
 301      */
 302     private static class Entry<K,V> extends HashMap.Entry<K,V> {
 303         // These fields comprise the doubly linked list used for iteration.
 304         Entry<K,V> before, after;
 305 
 306         Entry(int hash, K key, V value, Object next) {
 307             super(hash, key, value, next);
 308         }
 309 
 310         /**
 311          * Removes this entry from the linked list.
 312          */
 313         private void remove() {
 314             before.after = after;
 315             after.before = before;
 316         }




   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package java.util;
  27 import java.io.*;
  28 import java.util.function.BiConsumer;
  29 import java.util.function.BiFunction;
  30 
  31 /**
  32  * <p>Hash table and linked list implementation of the <tt>Map</tt> interface,
  33  * with predictable iteration order.  This implementation differs from
  34  * <tt>HashMap</tt> in that it maintains a doubly-linked list running through
  35  * all of its entries.  This linked list defines the iteration ordering,
  36  * which is normally the order in which keys were inserted into the map
  37  * (<i>insertion-order</i>).  Note that insertion order is not affected
  38  * if a key is <i>re-inserted</i> into the map.  (A key <tt>k</tt> is
  39  * reinserted into a map <tt>m</tt> if <tt>m.put(k, v)</tt> is invoked when
  40  * <tt>m.containsKey(k)</tt> would return <tt>true</tt> immediately prior to
  41  * the invocation.)
  42  *
  43  * <p>This implementation spares its clients from the unspecified, generally
  44  * chaotic ordering provided by {@link HashMap} (and {@link Hashtable}),
  45  * without incurring the increased cost associated with {@link TreeMap}.  It
  46  * can be used to produce a copy of a map that has the same order as the
  47  * original, regardless of the original map's implementation:
  48  * <pre>
  49  *     void foo(Map m) {


 279      * indicate that the map contains no mapping for the key; it's also
 280      * possible that the map explicitly maps the key to {@code null}.
 281      * The {@link #containsKey containsKey} operation may be used to
 282      * distinguish these two cases.
 283      */
 284     public V get(Object key) {
 285         Entry<K,V> e = (Entry<K,V>)getEntry(key);
 286         if (e == null)
 287             return null;
 288         e.recordAccess(this);
 289         return e.value;
 290     }
 291 
 292     /**
 293      * Removes all of the mappings from this map.
 294      * The map will be empty after this call returns.
 295      */
 296     public void clear() {
 297         super.clear();
 298         header.before = header.after = header;
 299     }
 300 
 301     @Override
 302     public void forEach(BiConsumer<? super K, ? super V> action) {
 303         Objects.requireNonNull(action);
 304         int expectedModCount = modCount;
 305         for (Entry<K, V> entry = header.after; entry != header; entry = entry.after) {
 306             action.accept(entry.key, entry.value);
 307 
 308             if (expectedModCount != modCount) {
 309                 throw new ConcurrentModificationException();
 310             }
 311         }
 312     }
 313 
 314     @Override
 315     public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
 316         Objects.requireNonNull(function);
 317         int expectedModCount = modCount;
 318         for (Entry<K, V> entry = header.after; entry != header; entry = entry.after) {
 319             entry.value = function.apply(entry.key, entry.value);
 320 
 321             if (expectedModCount != modCount) {
 322                 throw new ConcurrentModificationException();
 323             }
 324         }
 325     }
 326 
 327     /**
 328      * LinkedHashMap entry.
 329      */
 330     private static class Entry<K,V> extends HashMap.Entry<K,V> {
 331         // These fields comprise the doubly linked list used for iteration.
 332         Entry<K,V> before, after;
 333 
 334         Entry(int hash, K key, V value, Object next) {
 335             super(hash, key, value, next);
 336         }
 337 
 338         /**
 339          * Removes this entry from the linked list.
 340          */
 341         private void remove() {
 342             before.after = after;
 343             after.before = before;
 344         }