jdk/src/share/classes/java/util/LinkedHashMap.java
author mduigou
Tue, 18 Jun 2013 16:03:10 -0700
changeset 18280 6c3c0ff49eb5
parent 18156 edb590d448c5
child 19435 9d7530ff42cb
permissions -rw-r--r--
8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap Reviewed-by: forax, mduigou, psandoz Contributed-by: Mike Duigou <mike.duigou@oracle.com>, Remi Forax <forax@univ-mlv.fr>
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
     1
/*
14342
8435a30053c1 7197491: update copyright year to match last edit in jdk8 jdk repository
alanb
parents: 12859
diff changeset
     2
 * Copyright (c) 2000, 2012, Oracle and/or its affiliates. All rights reserved.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
     3
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
90ce3da70b43 Initial load
duke
parents:
diff changeset
     4
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
     5
 * This code is free software; you can redistribute it and/or modify it
90ce3da70b43 Initial load
duke
parents:
diff changeset
     6
 * under the terms of the GNU General Public License version 2 only, as
5506
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
     7
 * published by the Free Software Foundation.  Oracle designates this
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
     8
 * particular file as subject to the "Classpath" exception as provided
5506
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
     9
 * by Oracle in the LICENSE file that accompanied this code.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    10
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    11
 * This code is distributed in the hope that it will be useful, but WITHOUT
90ce3da70b43 Initial load
duke
parents:
diff changeset
    12
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
90ce3da70b43 Initial load
duke
parents:
diff changeset
    13
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
90ce3da70b43 Initial load
duke
parents:
diff changeset
    14
 * version 2 for more details (a copy is included in the LICENSE file that
90ce3da70b43 Initial load
duke
parents:
diff changeset
    15
 * accompanied this code).
90ce3da70b43 Initial load
duke
parents:
diff changeset
    16
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    17
 * You should have received a copy of the GNU General Public License version
90ce3da70b43 Initial load
duke
parents:
diff changeset
    18
 * 2 along with this work; if not, write to the Free Software Foundation,
90ce3da70b43 Initial load
duke
parents:
diff changeset
    19
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    20
 *
5506
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
    21
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
    22
 * or visit www.oracle.com if you need additional information or have any
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
    23
 * questions.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    24
 */
90ce3da70b43 Initial load
duke
parents:
diff changeset
    25
90ce3da70b43 Initial load
duke
parents:
diff changeset
    26
package java.util;
90ce3da70b43 Initial load
duke
parents:
diff changeset
    27
import java.io.*;
18280
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
    28
import java.util.function.BiConsumer;
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
    29
import java.util.function.BiFunction;
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    30
90ce3da70b43 Initial load
duke
parents:
diff changeset
    31
/**
90ce3da70b43 Initial load
duke
parents:
diff changeset
    32
 * <p>Hash table and linked list implementation of the <tt>Map</tt> interface,
90ce3da70b43 Initial load
duke
parents:
diff changeset
    33
 * with predictable iteration order.  This implementation differs from
90ce3da70b43 Initial load
duke
parents:
diff changeset
    34
 * <tt>HashMap</tt> in that it maintains a doubly-linked list running through
90ce3da70b43 Initial load
duke
parents:
diff changeset
    35
 * all of its entries.  This linked list defines the iteration ordering,
90ce3da70b43 Initial load
duke
parents:
diff changeset
    36
 * which is normally the order in which keys were inserted into the map
90ce3da70b43 Initial load
duke
parents:
diff changeset
    37
 * (<i>insertion-order</i>).  Note that insertion order is not affected
90ce3da70b43 Initial load
duke
parents:
diff changeset
    38
 * if a key is <i>re-inserted</i> into the map.  (A key <tt>k</tt> is
90ce3da70b43 Initial load
duke
parents:
diff changeset
    39
 * reinserted into a map <tt>m</tt> if <tt>m.put(k, v)</tt> is invoked when
90ce3da70b43 Initial load
duke
parents:
diff changeset
    40
 * <tt>m.containsKey(k)</tt> would return <tt>true</tt> immediately prior to
90ce3da70b43 Initial load
duke
parents:
diff changeset
    41
 * the invocation.)
90ce3da70b43 Initial load
duke
parents:
diff changeset
    42
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    43
 * <p>This implementation spares its clients from the unspecified, generally
90ce3da70b43 Initial load
duke
parents:
diff changeset
    44
 * chaotic ordering provided by {@link HashMap} (and {@link Hashtable}),
90ce3da70b43 Initial load
duke
parents:
diff changeset
    45
 * without incurring the increased cost associated with {@link TreeMap}.  It
90ce3da70b43 Initial load
duke
parents:
diff changeset
    46
 * can be used to produce a copy of a map that has the same order as the
90ce3da70b43 Initial load
duke
parents:
diff changeset
    47
 * original, regardless of the original map's implementation:
90ce3da70b43 Initial load
duke
parents:
diff changeset
    48
 * <pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
    49
 *     void foo(Map m) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
    50
 *         Map copy = new LinkedHashMap(m);
90ce3da70b43 Initial load
duke
parents:
diff changeset
    51
 *         ...
90ce3da70b43 Initial load
duke
parents:
diff changeset
    52
 *     }
90ce3da70b43 Initial load
duke
parents:
diff changeset
    53
 * </pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
    54
 * This technique is particularly useful if a module takes a map on input,
90ce3da70b43 Initial load
duke
parents:
diff changeset
    55
 * copies it, and later returns results whose order is determined by that of
90ce3da70b43 Initial load
duke
parents:
diff changeset
    56
 * the copy.  (Clients generally appreciate having things returned in the same
90ce3da70b43 Initial load
duke
parents:
diff changeset
    57
 * order they were presented.)
90ce3da70b43 Initial load
duke
parents:
diff changeset
    58
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    59
 * <p>A special {@link #LinkedHashMap(int,float,boolean) constructor} is
17939
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents: 14342
diff changeset
    60
 * provided to create a <tt>LinkedHashMap</tt> whose order of iteration is the
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents: 14342
diff changeset
    61
 * order in which its entries were last accessed, from least-recently accessed
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents: 14342
diff changeset
    62
 * to most-recently (<i>access-order</i>).  This kind of map is well-suited to
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    63
 * building LRU caches.  Invoking the <tt>put</tt> or <tt>get</tt> method
90ce3da70b43 Initial load
duke
parents:
diff changeset
    64
 * results in an access to the corresponding entry (assuming it exists after
90ce3da70b43 Initial load
duke
parents:
diff changeset
    65
 * the invocation completes).  The <tt>putAll</tt> method generates one entry
90ce3da70b43 Initial load
duke
parents:
diff changeset
    66
 * access for each mapping in the specified map, in the order that key-value
90ce3da70b43 Initial load
duke
parents:
diff changeset
    67
 * mappings are provided by the specified map's entry set iterator.  <i>No
90ce3da70b43 Initial load
duke
parents:
diff changeset
    68
 * other methods generate entry accesses.</i> In particular, operations on
90ce3da70b43 Initial load
duke
parents:
diff changeset
    69
 * collection-views do <i>not</i> affect the order of iteration of the backing
90ce3da70b43 Initial load
duke
parents:
diff changeset
    70
 * map.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    71
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    72
 * <p>The {@link #removeEldestEntry(Map.Entry)} method may be overridden to
90ce3da70b43 Initial load
duke
parents:
diff changeset
    73
 * impose a policy for removing stale mappings automatically when new mappings
90ce3da70b43 Initial load
duke
parents:
diff changeset
    74
 * are added to the map.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    75
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    76
 * <p>This class provides all of the optional <tt>Map</tt> operations, and
90ce3da70b43 Initial load
duke
parents:
diff changeset
    77
 * permits null elements.  Like <tt>HashMap</tt>, it provides constant-time
90ce3da70b43 Initial load
duke
parents:
diff changeset
    78
 * performance for the basic operations (<tt>add</tt>, <tt>contains</tt> and
90ce3da70b43 Initial load
duke
parents:
diff changeset
    79
 * <tt>remove</tt>), assuming the hash function disperses elements
90ce3da70b43 Initial load
duke
parents:
diff changeset
    80
 * properly among the buckets.  Performance is likely to be just slightly
90ce3da70b43 Initial load
duke
parents:
diff changeset
    81
 * below that of <tt>HashMap</tt>, due to the added expense of maintaining the
90ce3da70b43 Initial load
duke
parents:
diff changeset
    82
 * linked list, with one exception: Iteration over the collection-views
90ce3da70b43 Initial load
duke
parents:
diff changeset
    83
 * of a <tt>LinkedHashMap</tt> requires time proportional to the <i>size</i>
90ce3da70b43 Initial load
duke
parents:
diff changeset
    84
 * of the map, regardless of its capacity.  Iteration over a <tt>HashMap</tt>
90ce3da70b43 Initial load
duke
parents:
diff changeset
    85
 * is likely to be more expensive, requiring time proportional to its
90ce3da70b43 Initial load
duke
parents:
diff changeset
    86
 * <i>capacity</i>.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    87
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    88
 * <p>A linked hash map has two parameters that affect its performance:
90ce3da70b43 Initial load
duke
parents:
diff changeset
    89
 * <i>initial capacity</i> and <i>load factor</i>.  They are defined precisely
90ce3da70b43 Initial load
duke
parents:
diff changeset
    90
 * as for <tt>HashMap</tt>.  Note, however, that the penalty for choosing an
90ce3da70b43 Initial load
duke
parents:
diff changeset
    91
 * excessively high value for initial capacity is less severe for this class
90ce3da70b43 Initial load
duke
parents:
diff changeset
    92
 * than for <tt>HashMap</tt>, as iteration times for this class are unaffected
90ce3da70b43 Initial load
duke
parents:
diff changeset
    93
 * by capacity.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    94
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    95
 * <p><strong>Note that this implementation is not synchronized.</strong>
90ce3da70b43 Initial load
duke
parents:
diff changeset
    96
 * If multiple threads access a linked hash map concurrently, and at least
90ce3da70b43 Initial load
duke
parents:
diff changeset
    97
 * one of the threads modifies the map structurally, it <em>must</em> be
90ce3da70b43 Initial load
duke
parents:
diff changeset
    98
 * synchronized externally.  This is typically accomplished by
90ce3da70b43 Initial load
duke
parents:
diff changeset
    99
 * synchronizing on some object that naturally encapsulates the map.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   100
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   101
 * If no such object exists, the map should be "wrapped" using the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   102
 * {@link Collections#synchronizedMap Collections.synchronizedMap}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   103
 * method.  This is best done at creation time, to prevent accidental
90ce3da70b43 Initial load
duke
parents:
diff changeset
   104
 * unsynchronized access to the map:<pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   105
 *   Map m = Collections.synchronizedMap(new LinkedHashMap(...));</pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   106
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   107
 * A structural modification is any operation that adds or deletes one or more
90ce3da70b43 Initial load
duke
parents:
diff changeset
   108
 * mappings or, in the case of access-ordered linked hash maps, affects
90ce3da70b43 Initial load
duke
parents:
diff changeset
   109
 * iteration order.  In insertion-ordered linked hash maps, merely changing
90ce3da70b43 Initial load
duke
parents:
diff changeset
   110
 * the value associated with a key that is already contained in the map is not
90ce3da70b43 Initial load
duke
parents:
diff changeset
   111
 * a structural modification.  <strong>In access-ordered linked hash maps,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   112
 * merely querying the map with <tt>get</tt> is a structural
90ce3da70b43 Initial load
duke
parents:
diff changeset
   113
 * modification.</strong>)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   114
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   115
 * <p>The iterators returned by the <tt>iterator</tt> method of the collections
90ce3da70b43 Initial load
duke
parents:
diff changeset
   116
 * returned by all of this class's collection view methods are
90ce3da70b43 Initial load
duke
parents:
diff changeset
   117
 * <em>fail-fast</em>: if the map is structurally modified at any time after
90ce3da70b43 Initial load
duke
parents:
diff changeset
   118
 * the iterator is created, in any way except through the iterator's own
90ce3da70b43 Initial load
duke
parents:
diff changeset
   119
 * <tt>remove</tt> method, the iterator will throw a {@link
90ce3da70b43 Initial load
duke
parents:
diff changeset
   120
 * ConcurrentModificationException}.  Thus, in the face of concurrent
90ce3da70b43 Initial load
duke
parents:
diff changeset
   121
 * modification, the iterator fails quickly and cleanly, rather than risking
90ce3da70b43 Initial load
duke
parents:
diff changeset
   122
 * arbitrary, non-deterministic behavior at an undetermined time in the future.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   123
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   124
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
90ce3da70b43 Initial load
duke
parents:
diff changeset
   125
 * as it is, generally speaking, impossible to make any hard guarantees in the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   126
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
90ce3da70b43 Initial load
duke
parents:
diff changeset
   127
 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   128
 * Therefore, it would be wrong to write a program that depended on this
90ce3da70b43 Initial load
duke
parents:
diff changeset
   129
 * exception for its correctness:   <i>the fail-fast behavior of iterators
90ce3da70b43 Initial load
duke
parents:
diff changeset
   130
 * should be used only to detect bugs.</i>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   131
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   132
 * <p>This class is a member of the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   133
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
90ce3da70b43 Initial load
duke
parents:
diff changeset
   134
 * Java Collections Framework</a>.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   135
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   136
 * @param <K> the type of keys maintained by this map
90ce3da70b43 Initial load
duke
parents:
diff changeset
   137
 * @param <V> the type of mapped values
90ce3da70b43 Initial load
duke
parents:
diff changeset
   138
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   139
 * @author  Josh Bloch
90ce3da70b43 Initial load
duke
parents:
diff changeset
   140
 * @see     Object#hashCode()
90ce3da70b43 Initial load
duke
parents:
diff changeset
   141
 * @see     Collection
90ce3da70b43 Initial load
duke
parents:
diff changeset
   142
 * @see     Map
90ce3da70b43 Initial load
duke
parents:
diff changeset
   143
 * @see     HashMap
90ce3da70b43 Initial load
duke
parents:
diff changeset
   144
 * @see     TreeMap
90ce3da70b43 Initial load
duke
parents:
diff changeset
   145
 * @see     Hashtable
90ce3da70b43 Initial load
duke
parents:
diff changeset
   146
 * @since   1.4
90ce3da70b43 Initial load
duke
parents:
diff changeset
   147
 */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   148
90ce3da70b43 Initial load
duke
parents:
diff changeset
   149
public class LinkedHashMap<K,V>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   150
    extends HashMap<K,V>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   151
    implements Map<K,V>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   152
{
90ce3da70b43 Initial load
duke
parents:
diff changeset
   153
90ce3da70b43 Initial load
duke
parents:
diff changeset
   154
    private static final long serialVersionUID = 3801124242820219131L;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   155
90ce3da70b43 Initial load
duke
parents:
diff changeset
   156
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   157
     * The head of the doubly linked list.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   158
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   159
    private transient Entry<K,V> header;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   160
90ce3da70b43 Initial load
duke
parents:
diff changeset
   161
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   162
     * The iteration ordering method for this linked hash map: <tt>true</tt>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   163
     * for access-order, <tt>false</tt> for insertion-order.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   164
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   165
     * @serial
90ce3da70b43 Initial load
duke
parents:
diff changeset
   166
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   167
    private final boolean accessOrder;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   168
90ce3da70b43 Initial load
duke
parents:
diff changeset
   169
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   170
     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
90ce3da70b43 Initial load
duke
parents:
diff changeset
   171
     * with the specified initial capacity and load factor.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   172
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   173
     * @param  initialCapacity the initial capacity
90ce3da70b43 Initial load
duke
parents:
diff changeset
   174
     * @param  loadFactor      the load factor
90ce3da70b43 Initial load
duke
parents:
diff changeset
   175
     * @throws IllegalArgumentException if the initial capacity is negative
90ce3da70b43 Initial load
duke
parents:
diff changeset
   176
     *         or the load factor is nonpositive
90ce3da70b43 Initial load
duke
parents:
diff changeset
   177
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   178
    public LinkedHashMap(int initialCapacity, float loadFactor) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   179
        super(initialCapacity, loadFactor);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   180
        accessOrder = false;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   181
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   182
90ce3da70b43 Initial load
duke
parents:
diff changeset
   183
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   184
     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
90ce3da70b43 Initial load
duke
parents:
diff changeset
   185
     * with the specified initial capacity and a default load factor (0.75).
90ce3da70b43 Initial load
duke
parents:
diff changeset
   186
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   187
     * @param  initialCapacity the initial capacity
90ce3da70b43 Initial load
duke
parents:
diff changeset
   188
     * @throws IllegalArgumentException if the initial capacity is negative
90ce3da70b43 Initial load
duke
parents:
diff changeset
   189
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   190
    public LinkedHashMap(int initialCapacity) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   191
        super(initialCapacity);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   192
        accessOrder = false;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   193
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   194
90ce3da70b43 Initial load
duke
parents:
diff changeset
   195
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   196
     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
90ce3da70b43 Initial load
duke
parents:
diff changeset
   197
     * with the default initial capacity (16) and load factor (0.75).
90ce3da70b43 Initial load
duke
parents:
diff changeset
   198
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   199
    public LinkedHashMap() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   200
        super();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   201
        accessOrder = false;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   202
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   203
90ce3da70b43 Initial load
duke
parents:
diff changeset
   204
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   205
     * Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with
90ce3da70b43 Initial load
duke
parents:
diff changeset
   206
     * the same mappings as the specified map.  The <tt>LinkedHashMap</tt>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   207
     * instance is created with a default load factor (0.75) and an initial
90ce3da70b43 Initial load
duke
parents:
diff changeset
   208
     * capacity sufficient to hold the mappings in the specified map.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   209
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   210
     * @param  m the map whose mappings are to be placed in this map
90ce3da70b43 Initial load
duke
parents:
diff changeset
   211
     * @throws NullPointerException if the specified map is null
90ce3da70b43 Initial load
duke
parents:
diff changeset
   212
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   213
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   214
        super(m);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   215
        accessOrder = false;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   216
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   217
90ce3da70b43 Initial load
duke
parents:
diff changeset
   218
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   219
     * Constructs an empty <tt>LinkedHashMap</tt> instance with the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   220
     * specified initial capacity, load factor and ordering mode.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   221
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   222
     * @param  initialCapacity the initial capacity
90ce3da70b43 Initial load
duke
parents:
diff changeset
   223
     * @param  loadFactor      the load factor
90ce3da70b43 Initial load
duke
parents:
diff changeset
   224
     * @param  accessOrder     the ordering mode - <tt>true</tt> for
90ce3da70b43 Initial load
duke
parents:
diff changeset
   225
     *         access-order, <tt>false</tt> for insertion-order
90ce3da70b43 Initial load
duke
parents:
diff changeset
   226
     * @throws IllegalArgumentException if the initial capacity is negative
90ce3da70b43 Initial load
duke
parents:
diff changeset
   227
     *         or the load factor is nonpositive
90ce3da70b43 Initial load
duke
parents:
diff changeset
   228
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   229
    public LinkedHashMap(int initialCapacity,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   230
                         float loadFactor,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   231
                         boolean accessOrder) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   232
        super(initialCapacity, loadFactor);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   233
        this.accessOrder = accessOrder;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   234
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   235
90ce3da70b43 Initial load
duke
parents:
diff changeset
   236
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   237
     * Called by superclass constructors and pseudoconstructors (clone,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   238
     * readObject) before any entries are inserted into the map.  Initializes
90ce3da70b43 Initial load
duke
parents:
diff changeset
   239
     * the chain.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   240
     */
12859
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 12448
diff changeset
   241
    @Override
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   242
    void init() {
7803
56bc97d69d93 6880112: Project Coin: Port JDK core library code to use diamond operator
smarks
parents: 5506
diff changeset
   243
        header = new Entry<>(-1, null, null, null);
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   244
        header.before = header.after = header;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   245
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   246
90ce3da70b43 Initial load
duke
parents:
diff changeset
   247
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   248
     * Returns <tt>true</tt> if this map maps one or more keys to the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   249
     * specified value.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   250
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   251
     * @param value value whose presence in this map is to be tested
90ce3da70b43 Initial load
duke
parents:
diff changeset
   252
     * @return <tt>true</tt> if this map maps one or more keys to the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   253
     *         specified value
90ce3da70b43 Initial load
duke
parents:
diff changeset
   254
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   255
    public boolean containsValue(Object value) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   256
        // Overridden to take advantage of faster iterator
90ce3da70b43 Initial load
duke
parents:
diff changeset
   257
        if (value==null) {
12448
b95438b17098 7157893: Warnings Cleanup in java.util.*
khazra
parents: 9035
diff changeset
   258
            for (Entry<?,?> e = header.after; e != header; e = e.after)
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   259
                if (e.value==null)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   260
                    return true;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   261
        } else {
12448
b95438b17098 7157893: Warnings Cleanup in java.util.*
khazra
parents: 9035
diff changeset
   262
            for (Entry<?,?> e = header.after; e != header; e = e.after)
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   263
                if (value.equals(e.value))
90ce3da70b43 Initial load
duke
parents:
diff changeset
   264
                    return true;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   265
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   266
        return false;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   267
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   268
90ce3da70b43 Initial load
duke
parents:
diff changeset
   269
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   270
     * Returns the value to which the specified key is mapped,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   271
     * or {@code null} if this map contains no mapping for the key.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   272
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   273
     * <p>More formally, if this map contains a mapping from a key
90ce3da70b43 Initial load
duke
parents:
diff changeset
   274
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
90ce3da70b43 Initial load
duke
parents:
diff changeset
   275
     * key.equals(k))}, then this method returns {@code v}; otherwise
90ce3da70b43 Initial load
duke
parents:
diff changeset
   276
     * it returns {@code null}.  (There can be at most one such mapping.)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   277
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   278
     * <p>A return value of {@code null} does not <i>necessarily</i>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   279
     * indicate that the map contains no mapping for the key; it's also
90ce3da70b43 Initial load
duke
parents:
diff changeset
   280
     * possible that the map explicitly maps the key to {@code null}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   281
     * The {@link #containsKey containsKey} operation may be used to
90ce3da70b43 Initial load
duke
parents:
diff changeset
   282
     * distinguish these two cases.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   283
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   284
    public V get(Object key) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   285
        Entry<K,V> e = (Entry<K,V>)getEntry(key);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   286
        if (e == null)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   287
            return null;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   288
        e.recordAccess(this);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   289
        return e.value;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   290
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   291
90ce3da70b43 Initial load
duke
parents:
diff changeset
   292
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   293
     * Removes all of the mappings from this map.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   294
     * The map will be empty after this call returns.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   295
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   296
    public void clear() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   297
        super.clear();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   298
        header.before = header.after = header;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   299
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   300
18280
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   301
    @Override
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   302
    public void forEach(BiConsumer<? super K, ? super V> action) {
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   303
        Objects.requireNonNull(action);
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   304
        int expectedModCount = modCount;
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   305
        for (Entry<K, V> entry = header.after; entry != header; entry = entry.after) {
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   306
            action.accept(entry.key, entry.value);
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   307
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   308
            if (expectedModCount != modCount) {
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   309
                throw new ConcurrentModificationException();
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   310
            }
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   311
        }
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   312
    }
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   313
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   314
    @Override
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   315
    public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   316
        Objects.requireNonNull(function);
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   317
        int expectedModCount = modCount;
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   318
        for (Entry<K, V> entry = header.after; entry != header; entry = entry.after) {
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   319
            entry.value = function.apply(entry.key, entry.value);
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   320
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   321
            if (expectedModCount != modCount) {
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   322
                throw new ConcurrentModificationException();
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   323
            }
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   324
        }
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   325
    }
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
   326
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   327
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   328
     * LinkedHashMap entry.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   329
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   330
    private static class Entry<K,V> extends HashMap.Entry<K,V> {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   331
        // These fields comprise the doubly linked list used for iteration.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   332
        Entry<K,V> before, after;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   333
17939
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents: 14342
diff changeset
   334
        Entry(int hash, K key, V value, Object next) {
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   335
            super(hash, key, value, next);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   336
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   337
90ce3da70b43 Initial load
duke
parents:
diff changeset
   338
        /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   339
         * Removes this entry from the linked list.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   340
         */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   341
        private void remove() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   342
            before.after = after;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   343
            after.before = before;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   344
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   345
90ce3da70b43 Initial load
duke
parents:
diff changeset
   346
        /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   347
         * Inserts this entry before the specified existing entry in the list.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   348
         */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   349
        private void addBefore(Entry<K,V> existingEntry) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   350
            after  = existingEntry;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   351
            before = existingEntry.before;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   352
            before.after = this;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   353
            after.before = this;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   354
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   355
90ce3da70b43 Initial load
duke
parents:
diff changeset
   356
        /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   357
         * This method is invoked by the superclass whenever the value
17939
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents: 14342
diff changeset
   358
         * of a pre-existing entry is read by Map.get or modified by Map.put.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   359
         * If the enclosing Map is access-ordered, it moves the entry
90ce3da70b43 Initial load
duke
parents:
diff changeset
   360
         * to the end of the list; otherwise, it does nothing.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   361
         */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   362
        void recordAccess(HashMap<K,V> m) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   363
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   364
            if (lm.accessOrder) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   365
                lm.modCount++;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   366
                remove();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   367
                addBefore(lm.header);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   368
            }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   369
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   370
90ce3da70b43 Initial load
duke
parents:
diff changeset
   371
        void recordRemoval(HashMap<K,V> m) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   372
            remove();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   373
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   374
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   375
90ce3da70b43 Initial load
duke
parents:
diff changeset
   376
    private abstract class LinkedHashIterator<T> implements Iterator<T> {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   377
        Entry<K,V> nextEntry    = header.after;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   378
        Entry<K,V> lastReturned = null;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   379
90ce3da70b43 Initial load
duke
parents:
diff changeset
   380
        /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   381
         * The modCount value that the iterator believes that the backing
90ce3da70b43 Initial load
duke
parents:
diff changeset
   382
         * List should have.  If this expectation is violated, the iterator
90ce3da70b43 Initial load
duke
parents:
diff changeset
   383
         * has detected concurrent modification.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   384
         */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   385
        int expectedModCount = modCount;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   386
90ce3da70b43 Initial load
duke
parents:
diff changeset
   387
        public boolean hasNext() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   388
            return nextEntry != header;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   389
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   390
90ce3da70b43 Initial load
duke
parents:
diff changeset
   391
        public void remove() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   392
            if (lastReturned == null)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   393
                throw new IllegalStateException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   394
            if (modCount != expectedModCount)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   395
                throw new ConcurrentModificationException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   396
90ce3da70b43 Initial load
duke
parents:
diff changeset
   397
            LinkedHashMap.this.remove(lastReturned.key);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   398
            lastReturned = null;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   399
            expectedModCount = modCount;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   400
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   401
90ce3da70b43 Initial load
duke
parents:
diff changeset
   402
        Entry<K,V> nextEntry() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   403
            if (modCount != expectedModCount)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   404
                throw new ConcurrentModificationException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   405
            if (nextEntry == header)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   406
                throw new NoSuchElementException();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   407
90ce3da70b43 Initial load
duke
parents:
diff changeset
   408
            Entry<K,V> e = lastReturned = nextEntry;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   409
            nextEntry = e.after;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   410
            return e;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   411
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   412
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   413
90ce3da70b43 Initial load
duke
parents:
diff changeset
   414
    private class KeyIterator extends LinkedHashIterator<K> {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   415
        public K next() { return nextEntry().getKey(); }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   416
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   417
90ce3da70b43 Initial load
duke
parents:
diff changeset
   418
    private class ValueIterator extends LinkedHashIterator<V> {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   419
        public V next() { return nextEntry().value; }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   420
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   421
90ce3da70b43 Initial load
duke
parents:
diff changeset
   422
    private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   423
        public Map.Entry<K,V> next() { return nextEntry(); }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   424
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   425
90ce3da70b43 Initial load
duke
parents:
diff changeset
   426
    // These Overrides alter the behavior of superclass view iterator() methods
90ce3da70b43 Initial load
duke
parents:
diff changeset
   427
    Iterator<K> newKeyIterator()   { return new KeyIterator();   }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   428
    Iterator<V> newValueIterator() { return new ValueIterator(); }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   429
    Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   430
90ce3da70b43 Initial load
duke
parents:
diff changeset
   431
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   432
     * This override alters behavior of superclass put method. It causes newly
90ce3da70b43 Initial load
duke
parents:
diff changeset
   433
     * allocated entry to get inserted at the end of the linked list and
90ce3da70b43 Initial load
duke
parents:
diff changeset
   434
     * removes the eldest entry if appropriate.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   435
     */
17939
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents: 14342
diff changeset
   436
    @Override
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents: 14342
diff changeset
   437
    void addEntry(int hash, K key, V value, int bucketIndex, boolean checkIfNeedTree) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents: 14342
diff changeset
   438
        super.addEntry(hash, key, value, bucketIndex, checkIfNeedTree);
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   439
12859
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 12448
diff changeset
   440
        // Remove eldest entry if instructed
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   441
        Entry<K,V> eldest = header.after;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   442
        if (removeEldestEntry(eldest)) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   443
            removeEntryForKey(eldest.key);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   444
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   445
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   446
17939
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents: 14342
diff changeset
   447
    /*
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents: 14342
diff changeset
   448
     * Create a new LinkedHashMap.Entry and setup the before/after pointers
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   449
     */
17939
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents: 14342
diff changeset
   450
    @Override
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents: 14342
diff changeset
   451
    HashMap.Entry<K,V> newEntry(int hash, K key, V value, Object next) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents: 14342
diff changeset
   452
        Entry<K,V> newEntry = new Entry<>(hash, key, value, next);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents: 14342
diff changeset
   453
        newEntry.addBefore(header);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees
bchristi
parents: 14342
diff changeset
   454
        return newEntry;
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   455
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   456
90ce3da70b43 Initial load
duke
parents:
diff changeset
   457
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   458
     * Returns <tt>true</tt> if this map should remove its eldest entry.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   459
     * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after
90ce3da70b43 Initial load
duke
parents:
diff changeset
   460
     * inserting a new entry into the map.  It provides the implementor
90ce3da70b43 Initial load
duke
parents:
diff changeset
   461
     * with the opportunity to remove the eldest entry each time a new one
90ce3da70b43 Initial load
duke
parents:
diff changeset
   462
     * is added.  This is useful if the map represents a cache: it allows
90ce3da70b43 Initial load
duke
parents:
diff changeset
   463
     * the map to reduce memory consumption by deleting stale entries.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   464
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   465
     * <p>Sample use: this override will allow the map to grow up to 100
90ce3da70b43 Initial load
duke
parents:
diff changeset
   466
     * entries and then delete the eldest entry each time a new entry is
90ce3da70b43 Initial load
duke
parents:
diff changeset
   467
     * added, maintaining a steady state of 100 entries.
18156
edb590d448c5 8016217: More javadoc warnings
alanb
parents: 17939
diff changeset
   468
     * <pre>{@code
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   469
     *     private static final int MAX_ENTRIES = 100;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   470
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   471
     *     protected boolean removeEldestEntry(Map.Entry eldest) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   472
     *        return size() > MAX_ENTRIES;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   473
     *     }
18156
edb590d448c5 8016217: More javadoc warnings
alanb
parents: 17939
diff changeset
   474
     * }</pre>
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   475
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   476
     * <p>This method typically does not modify the map in any way,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   477
     * instead allowing the map to modify itself as directed by its
90ce3da70b43 Initial load
duke
parents:
diff changeset
   478
     * return value.  It <i>is</i> permitted for this method to modify
90ce3da70b43 Initial load
duke
parents:
diff changeset
   479
     * the map directly, but if it does so, it <i>must</i> return
90ce3da70b43 Initial load
duke
parents:
diff changeset
   480
     * <tt>false</tt> (indicating that the map should not attempt any
90ce3da70b43 Initial load
duke
parents:
diff changeset
   481
     * further modification).  The effects of returning <tt>true</tt>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   482
     * after modifying the map from within this method are unspecified.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   483
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   484
     * <p>This implementation merely returns <tt>false</tt> (so that this
90ce3da70b43 Initial load
duke
parents:
diff changeset
   485
     * map acts like a normal map - the eldest element is never removed).
90ce3da70b43 Initial load
duke
parents:
diff changeset
   486
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   487
     * @param    eldest The least recently inserted entry in the map, or if
90ce3da70b43 Initial load
duke
parents:
diff changeset
   488
     *           this is an access-ordered map, the least recently accessed
90ce3da70b43 Initial load
duke
parents:
diff changeset
   489
     *           entry.  This is the entry that will be removed it this
90ce3da70b43 Initial load
duke
parents:
diff changeset
   490
     *           method returns <tt>true</tt>.  If the map was empty prior
90ce3da70b43 Initial load
duke
parents:
diff changeset
   491
     *           to the <tt>put</tt> or <tt>putAll</tt> invocation resulting
90ce3da70b43 Initial load
duke
parents:
diff changeset
   492
     *           in this invocation, this will be the entry that was just
90ce3da70b43 Initial load
duke
parents:
diff changeset
   493
     *           inserted; in other words, if the map contains a single
90ce3da70b43 Initial load
duke
parents:
diff changeset
   494
     *           entry, the eldest entry is also the newest.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   495
     * @return   <tt>true</tt> if the eldest entry should be removed
90ce3da70b43 Initial load
duke
parents:
diff changeset
   496
     *           from the map; <tt>false</tt> if it should be retained.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   497
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   498
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   499
        return false;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   500
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   501
}