src/share/classes/java/util/HashMap.java
Print this page
*** 24,33 ****
--- 24,35 ----
*/
package java.util;
import java.io.*;
+ import java.lang.reflect.ParameterizedType;
+ import java.lang.reflect.Type;
import java.util.function.Consumer;
import java.util.function.BiFunction;
import java.util.function.Function;
/**
*** 148,163 ****
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* An empty table instance to share when the table is not inflated.
*/
! static final Entry<?,?>[] EMPTY_TABLE = {};
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
! transient Entry<?,?>[] table = EMPTY_TABLE;
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
--- 150,165 ----
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* An empty table instance to share when the table is not inflated.
*/
! static final Object[] EMPTY_TABLE = {};
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
! transient Object[] table = EMPTY_TABLE;
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
*** 184,221 ****
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;
- private static class Holder {
/**
! *
*/
static final sun.misc.Unsafe UNSAFE;
/**
* Offset of "final" hashSeed field we must set in
* readObject() method.
*/
static final long HASHSEED_OFFSET;
static {
try {
UNSAFE = sun.misc.Unsafe.getUnsafe();
HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
HashMap.class.getDeclaredField("hashSeed"));
} catch (NoSuchFieldException | SecurityException e) {
throw new InternalError("Failed to record hashSeed offset", e);
}
}
}
! /**
* A randomizing value associated with this instance that is applied to
* hash code of keys to make hash collisions harder to find.
*/
! transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
--- 186,817 ----
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;
/**
! * Holds values which can't be initialized until after VM is booted.
*/
+ private static class Holder {
static final sun.misc.Unsafe UNSAFE;
/**
* Offset of "final" hashSeed field we must set in
* readObject() method.
*/
static final long HASHSEED_OFFSET;
+ static final boolean USE_HASHSEED;
+
static {
+ String hashSeedProp = java.security.AccessController.doPrivileged(
+ new sun.security.action.GetPropertyAction(
+ "jdk.map.useRandomSeed"));
+ boolean localBool = (null != hashSeedProp)
+ ? Boolean.parseBoolean(hashSeedProp) : false;
+ USE_HASHSEED = localBool;
+
+ if (USE_HASHSEED) {
try {
UNSAFE = sun.misc.Unsafe.getUnsafe();
HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
HashMap.class.getDeclaredField("hashSeed"));
} catch (NoSuchFieldException | SecurityException e) {
throw new InternalError("Failed to record hashSeed offset", e);
}
+ } else {
+ UNSAFE = null;
+ HASHSEED_OFFSET = 0;
+ }
}
}
! /*
* A randomizing value associated with this instance that is applied to
* hash code of keys to make hash collisions harder to find.
+ *
+ * Non-final so it can be set lazily, but be sure not to set more than once.
+ */
+ transient final int hashSeed;
+
+ /*
+ * TreeBin/TreeNode code from CHM doesn't handle the null key. Store the
+ * null key entry here.
+ */
+ transient Entry<K,V> nullKeyEntry = null;
+
+ /*
+ * In order to improve performance under high hash-collision conditions,
+ * HashMap will switch to storing a bin's entries in a balanced tree
+ * (TreeBin) instead of a linked-list once the number of entries in the bin
+ * passes a certain threshold (TreeBin.TREE_THRESHOLD), if at least one of
+ * the keys in the bin implements Comparable. This technique is borrowed
+ * from ConcurrentHashMap.
+ */
+
+ /*
+ * Code based on CHMv8
+ *
+ * Node type for TreeBin
+ */
+ final static class TreeNode<K,V> {
+ TreeNode parent; // red-black tree links
+ TreeNode left;
+ TreeNode right;
+ TreeNode prev; // needed to unlink next upon deletion
+ boolean red;
+ final HashMap.Entry<K,V> entry;
+
+ TreeNode(HashMap.Entry<K,V> entry, Object next, TreeNode parent) {
+ this.entry = entry;
+ this.entry.next = next;
+ this.parent = parent;
+ }
+ }
+
+ /**
+ * Returns a Class for the given object of the form "class C
+ * implements Comparable<C>", if one exists, else null. See the TreeBin
+ * docs, below, for explanation.
+ */
+ static Class<?> comparableClassFor(Object x) {
+ Class<?> c, s, cmpc; Type[] ts, as; Type t; ParameterizedType p;
+ if ((c = x.getClass()) == String.class) // bypass checks
+ return c;
+ if ((cmpc = Comparable.class).isAssignableFrom(c)) {
+ while (cmpc.isAssignableFrom(s = c.getSuperclass()))
+ c = s; // find topmost comparable class
+ if ((ts = c.getGenericInterfaces()) != null) {
+ for (int i = 0; i < ts.length; ++i) {
+ if (((t = ts[i]) instanceof ParameterizedType) &&
+ ((p = (ParameterizedType)t).getRawType() == cmpc) &&
+ (as = p.getActualTypeArguments()) != null &&
+ as.length == 1 && as[0] == c) // type arg is c
+ return c;
+ }
+ }
+ }
+ return null;
+ }
+
+ /*
+ * Code based on CHMv8
+ *
+ * A specialized form of red-black tree for use in bins
+ * whose size exceeds a threshold.
+ *
+ * TreeBins use a special form of comparison for search and
+ * related operations (which is the main reason we cannot use
+ * existing collections such as TreeMaps). TreeBins contain
+ * Comparable elements, but may contain others, as well as
+ * elements that are Comparable but not necessarily Comparable<T>
+ * for the same T, so we cannot invoke compareTo among them. To
+ * handle this, the tree is ordered primarily by hash value, then
+ * by Comparable.compareTo order if applicable. On lookup at a
+ * node, if elements are not comparable or compare as 0 then both
+ * left and right children may need to be searched in the case of
+ * tied hash values. (This corresponds to the full list search
+ * that would be necessary if all elements were non-Comparable and
+ * had tied hashes.) The red-black balancing code is updated from
+ * pre-jdk-collections
+ * (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
+ * based in turn on Cormen, Leiserson, and Rivest "Introduction to
+ * Algorithms" (CLR).
+ */
+ final class TreeBin {
+ /*
+ * The bin count threshold for using a tree rather than list for a bin. The
+ * value reflects the approximate break-even point for using tree-based
+ * operations.
+ */
+ static final int TREE_THRESHOLD = 16;
+
+ TreeNode<K,V> root; // root of tree
+ TreeNode<K,V> first; // head of next-pointer list
+
+ /*
+ * Split a TreeBin into lo and hi parts and install in given table.
+ *
+ * Existing Entrys are re-used, which maintains the before/after links for
+ * LinkedHashMap.Entry.
+ *
+ * No check for Comparable, though this is the same as CHM.
+ */
+ final void splitTreeBin(Object[] newTable, int i, TreeBin loTree, TreeBin hiTree) {
+ TreeBin oldTree = this;
+ int bit = newTable.length >>> 1;
+ int loCount = 0, hiCount = 0;
+ TreeNode<K,V> e = oldTree.first;
+ TreeNode<K,V> next;
+
+ // This method is called when the table has just increased capacity,
+ // so indexFor() is now taking one additional bit of hash into
+ // account ("bit"). Entries in this TreeBin now belong in one of
+ // two bins, "i" or "i+bit", depending on if the new top bit of the
+ // hash is set. The trees for the two bins are loTree and hiTree.
+ // If either tree ends up containing fewer than TREE_THRESHOLD
+ // entries, it is converted back to a linked list.
+ while (e != null) {
+ // Save entry.next - it will get overwritten in putTreeNode()
+ next = (TreeNode<K,V>)e.entry.next;
+
+ int h = e.entry.hash;
+ K k = (K) e.entry.key;
+ V v = e.entry.value;
+ if ((h & bit) == 0) {
+ ++loCount;
+ // Re-using e.entry
+ loTree.putTreeNode(h, k, v, e.entry);
+ } else {
+ ++hiCount;
+ hiTree.putTreeNode(h, k, v, e.entry);
+ }
+ // Iterate using the saved 'next'
+ e = next;
+ }
+ if (loCount < TREE_THRESHOLD) { // too small, convert back to list
+ HashMap.Entry loEntry = null;
+ TreeNode<K,V> p = loTree.first;
+ while (p != null) {
+ @SuppressWarnings("unchecked")
+ TreeNode<K,V> savedNext = (TreeNode<K,V>) p.entry.next;
+ p.entry.next = loEntry;
+ loEntry = p.entry;
+ p = savedNext;
+ }
+ // assert newTable[i] == null;
+ newTable[i] = loEntry;
+ } else {
+ // assert newTable[i] == null;
+ newTable[i] = loTree;
+ }
+ if (hiCount < TREE_THRESHOLD) { // too small, convert back to list
+ HashMap.Entry hiEntry = null;
+ TreeNode<K,V> p = hiTree.first;
+ while (p != null) {
+ @SuppressWarnings("unchecked")
+ TreeNode<K,V> savedNext = (TreeNode<K,V>) p.entry.next;
+ p.entry.next = hiEntry;
+ hiEntry = p.entry;
+ p = savedNext;
+ }
+ // assert newTable[i + bit] == null;
+ newTable[i + bit] = hiEntry;
+ } else {
+ // assert newTable[i + bit] == null;
+ newTable[i + bit] = hiTree;
+ }
+ }
+
+ /*
+ * Popuplate the TreeBin with entries from the linked list e
+ *
+ * Assumes 'this' is a new/empty TreeBin
+ *
+ * Note: no check for Comparable
+ * Note: I believe this changes iteration order
+ */
+ @SuppressWarnings("unchecked")
+ void populate(HashMap.Entry e) {
+ // assert root == null;
+ // assert first == null;
+ HashMap.Entry next;
+ while (e != null) {
+ // Save entry.next - it will get overwritten in putTreeNode()
+ next = (HashMap.Entry)e.next;
+ // Re-using Entry e will maintain before/after in LinkedHM
+ putTreeNode(e.hash, (K)e.key, (V)e.value, e);
+ // Iterate using the saved 'next'
+ e = next;
+ }
+ }
+
+ /**
+ * Copied from CHMv8
+ * From CLR
+ */
+ private void rotateLeft(TreeNode p) {
+ if (p != null) {
+ TreeNode r = p.right, pp, rl;
+ if ((rl = p.right = r.left) != null) {
+ rl.parent = p;
+ }
+ if ((pp = r.parent = p.parent) == null) {
+ root = r;
+ } else if (pp.left == p) {
+ pp.left = r;
+ } else {
+ pp.right = r;
+ }
+ r.left = p;
+ p.parent = r;
+ }
+ }
+
+ /**
+ * Copied from CHMv8
+ * From CLR
+ */
+ private void rotateRight(TreeNode p) {
+ if (p != null) {
+ TreeNode l = p.left, pp, lr;
+ if ((lr = p.left = l.right) != null) {
+ lr.parent = p;
+ }
+ if ((pp = l.parent = p.parent) == null) {
+ root = l;
+ } else if (pp.right == p) {
+ pp.right = l;
+ } else {
+ pp.left = l;
+ }
+ l.right = p;
+ p.parent = l;
+ }
+ }
+
+ /**
+ * Returns the TreeNode (or null if not found) for the given
+ * key. A front-end for recursive version.
*/
! final TreeNode getTreeNode(int h, K k) {
! return getTreeNode(h, k, root, comparableClassFor(k));
! }
!
! /**
! * Returns the TreeNode (or null if not found) for the given key
! * starting at given root.
! */
! @SuppressWarnings("unchecked")
! final TreeNode getTreeNode (int h, K k, TreeNode p, Class<?> cc) {
! // assert k != null;
! while (p != null) {
! int dir, ph; Object pk;
! if ((ph = p.entry.hash) != h)
! dir = (h < ph) ? -1 : 1;
! else if ((pk = p.entry.key) == k || k.equals(pk))
! return p;
! else if (cc == null || comparableClassFor(pk) != cc ||
! (dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
! // assert pk != null;
! TreeNode r, pl, pr; // check both sides
! if ((pr = p.right) != null &&
! (r = getTreeNode(h, k, pr, cc)) != null)
! return r;
! else if ((pl = p.left) != null)
! dir = -1;
! else // nothing there
! break;
! }
! p = (dir > 0) ? p.right : p.left;
! }
! return null;
! }
!
! /*
! * Finds or adds a node.
! *
! * 'entry' should be used to recycle an existing Entry (e.g. in the case
! * of converting a linked-list bin to a TreeBin).
! * If entry is null, a new Entry will be created for the new TreeNode
! *
! * @return the TreeNode containing the mapping, or null if a new
! * TreeNode was added
! */
! @SuppressWarnings("unchecked")
! TreeNode putTreeNode(int h, K k, V v, HashMap.Entry<K,V> entry) {
! // assert k != null;
! //if (entry != null) {
! // assert h == entry.hash;
! // assert k == entry.key;
! // assert v == entry.value;
! // }
! Class<?> cc = comparableClassFor(k);
! TreeNode pp = root, p = null;
! int dir = 0;
! while (pp != null) { // find existing node or leaf to insert at
! int ph; Object pk;
! p = pp;
! if ((ph = p.entry.hash) != h)
! dir = (h < ph) ? -1 : 1;
! else if ((pk = p.entry.key) == k || k.equals(pk))
! return p;
! else if (cc == null || comparableClassFor(pk) != cc ||
! (dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
! TreeNode r, pr;
! if ((pr = p.right) != null &&
! (r = getTreeNode(h, k, pr, cc)) != null)
! return r;
! else // continue left
! dir = -1;
! }
! pp = (dir > 0) ? p.right : p.left;
! }
!
! // Didn't find the mapping in the tree, so add it
! TreeNode f = first;
! TreeNode x;
! if (entry != null) {
! x = new TreeNode(entry, f, p);
! } else {
! x = new TreeNode(newEntry(h, k, v, null), f, p);
! }
! first = x;
!
! if (p == null) {
! root = x;
! } else { // attach and rebalance; adapted from CLR
! TreeNode xp, xpp;
! if (f != null) {
! f.prev = x;
! }
! if (dir <= 0) {
! p.left = x;
! } else {
! p.right = x;
! }
! x.red = true;
! while (x != null && (xp = x.parent) != null && xp.red
! && (xpp = xp.parent) != null) {
! TreeNode xppl = xpp.left;
! if (xp == xppl) {
! TreeNode y = xpp.right;
! if (y != null && y.red) {
! y.red = false;
! xp.red = false;
! xpp.red = true;
! x = xpp;
! } else {
! if (x == xp.right) {
! rotateLeft(x = xp);
! xpp = (xp = x.parent) == null ? null : xp.parent;
! }
! if (xp != null) {
! xp.red = false;
! if (xpp != null) {
! xpp.red = true;
! rotateRight(xpp);
! }
! }
! }
! } else {
! TreeNode y = xppl;
! if (y != null && y.red) {
! y.red = false;
! xp.red = false;
! xpp.red = true;
! x = xpp;
! } else {
! if (x == xp.left) {
! rotateRight(x = xp);
! xpp = (xp = x.parent) == null ? null : xp.parent;
! }
! if (xp != null) {
! xp.red = false;
! if (xpp != null) {
! xpp.red = true;
! rotateLeft(xpp);
! }
! }
! }
! }
! }
! TreeNode r = root;
! if (r != null && r.red) {
! r.red = false;
! }
! }
! return null;
! }
!
! /*
! * From CHMv8
! *
! * Removes the given node, that must be present before this
! * call. This is messier than typical red-black deletion code
! * because we cannot swap the contents of an interior node
! * with a leaf successor that is pinned by "next" pointers
! * that are accessible independently of lock. So instead we
! * swap the tree linkages.
! */
! final void deleteTreeNode(TreeNode p) {
! TreeNode next = (TreeNode) p.entry.next; // unlink traversal pointers
! TreeNode pred = p.prev;
! if (pred == null) {
! first = next;
! } else {
! pred.entry.next = next;
! }
! if (next != null) {
! next.prev = pred;
! }
! TreeNode replacement;
! TreeNode pl = p.left;
! TreeNode pr = p.right;
! if (pl != null && pr != null) {
! TreeNode s = pr, sl;
! while ((sl = s.left) != null) // find successor
! {
! s = sl;
! }
! boolean c = s.red;
! s.red = p.red;
! p.red = c; // swap colors
! TreeNode sr = s.right;
! TreeNode pp = p.parent;
! if (s == pr) { // p was s's direct parent
! p.parent = s;
! s.right = p;
! } else {
! TreeNode sp = s.parent;
! if ((p.parent = sp) != null) {
! if (s == sp.left) {
! sp.left = p;
! } else {
! sp.right = p;
! }
! }
! if ((s.right = pr) != null) {
! pr.parent = s;
! }
! }
! p.left = null;
! if ((p.right = sr) != null) {
! sr.parent = p;
! }
! if ((s.left = pl) != null) {
! pl.parent = s;
! }
! if ((s.parent = pp) == null) {
! root = s;
! } else if (p == pp.left) {
! pp.left = s;
! } else {
! pp.right = s;
! }
! replacement = sr;
! } else {
! replacement = (pl != null) ? pl : pr;
! }
! TreeNode pp = p.parent;
! if (replacement == null) {
! if (pp == null) {
! root = null;
! return;
! }
! replacement = p;
! } else {
! replacement.parent = pp;
! if (pp == null) {
! root = replacement;
! } else if (p == pp.left) {
! pp.left = replacement;
! } else {
! pp.right = replacement;
! }
! p.left = p.right = p.parent = null;
! }
! if (!p.red) { // rebalance, from CLR
! TreeNode x = replacement;
! while (x != null) {
! TreeNode xp, xpl;
! if (x.red || (xp = x.parent) == null) {
! x.red = false;
! break;
! }
! if (x == (xpl = xp.left)) {
! TreeNode sib = xp.right;
! if (sib != null && sib.red) {
! sib.red = false;
! xp.red = true;
! rotateLeft(xp);
! sib = (xp = x.parent) == null ? null : xp.right;
! }
! if (sib == null) {
! x = xp;
! } else {
! TreeNode sl = sib.left, sr = sib.right;
! if ((sr == null || !sr.red)
! && (sl == null || !sl.red)) {
! sib.red = true;
! x = xp;
! } else {
! if (sr == null || !sr.red) {
! if (sl != null) {
! sl.red = false;
! }
! sib.red = true;
! rotateRight(sib);
! sib = (xp = x.parent) == null ?
! null : xp.right;
! }
! if (sib != null) {
! sib.red = (xp == null) ? false : xp.red;
! if ((sr = sib.right) != null) {
! sr.red = false;
! }
! }
! if (xp != null) {
! xp.red = false;
! rotateLeft(xp);
! }
! x = root;
! }
! }
! } else { // symmetric
! TreeNode sib = xpl;
! if (sib != null && sib.red) {
! sib.red = false;
! xp.red = true;
! rotateRight(xp);
! sib = (xp = x.parent) == null ? null : xp.left;
! }
! if (sib == null) {
! x = xp;
! } else {
! TreeNode sl = sib.left, sr = sib.right;
! if ((sl == null || !sl.red)
! && (sr == null || !sr.red)) {
! sib.red = true;
! x = xp;
! } else {
! if (sl == null || !sl.red) {
! if (sr != null) {
! sr.red = false;
! }
! sib.red = true;
! rotateLeft(sib);
! sib = (xp = x.parent) == null ?
! null : xp.left;
! }
! if (sib != null) {
! sib.red = (xp == null) ? false : xp.red;
! if ((sl = sib.left) != null) {
! sl.red = false;
! }
! }
! if (xp != null) {
! xp.red = false;
! rotateRight(xp);
! }
! x = root;
! }
! }
! }
! }
! }
! if (p == replacement && (pp = p.parent) != null) {
! if (p == pp.left) // detach pointers
! {
! pp.left = null;
! } else if (p == pp.right) {
! pp.right = null;
! }
! p.parent = null;
! }
! }
! }
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
*** 231,243 ****
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
-
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
--- 827,839 ----
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
+ hashSeed = initHashSeed();
init();
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
*** 271,280 ****
--- 867,877 ----
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
+ // assert size == m.size();
}
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
int rounded = number >= MAXIMUM_CAPACITY
*** 292,302 ****
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
! table = new Entry[capacity];
}
// internal utilities
/**
--- 889,899 ----
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
! table = new Object[capacity];
}
// internal utilities
/**
*** 308,328 ****
*/
void init() {
}
/**
* Retrieve object hash code and applies a supplemental hash function to the
* result hash, which defends against poor quality hash functions. This is
* critical because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits.
*/
final int hash(Object k) {
- if (k instanceof String) {
- return ((String) k).hash32();
- }
-
int h = hashSeed ^ k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
--- 905,932 ----
*/
void init() {
}
/**
+ * Return an initial value for the hashSeed, or 0 if the random seed is not
+ * enabled.
+ */
+ final int initHashSeed() {
+ if (sun.misc.VM.isBooted() && Holder.USE_HASHSEED) {
+ return sun.misc.Hashing.randomHashSeed(this);
+ }
+ return 0;
+ }
+
+ /**
* Retrieve object hash code and applies a supplemental hash function to the
* result hash, which defends against poor quality hash functions. This is
* critical because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits.
*/
final int hash(Object k) {
int h = hashSeed ^ k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
*** 407,429 ****
@SuppressWarnings("unchecked")
final Entry<K,V> getEntry(Object key) {
if (isEmpty()) {
return null;
}
! int hash = (key == null) ? 0 : hash(key);
! for (Entry<?,?> e = table[indexFor(hash, table.length)];
! e != null;
! e = e.next) {
Object k;
if (e.hash == hash &&
! ((k = e.key) == key || (key != null && key.equals(k))))
! return (Entry<K,V>)e;
}
return null;
}
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
--- 1011,1049 ----
@SuppressWarnings("unchecked")
final Entry<K,V> getEntry(Object key) {
if (isEmpty()) {
return null;
}
+ if (key == null) {
+ return nullKeyEntry;
+ }
+ int hash = hash(key);
+ int bin = indexFor(hash, table.length);
! if (table[bin] instanceof Entry) {
! Entry<K,V> e = (Entry<K,V>) table[bin];
! for (; e != null; e = (Entry<K,V>)e.next) {
Object k;
if (e.hash == hash &&
! ((k = e.key) == key || key.equals(k))) {
! return e;
! }
! }
! } else if (table[bin] != null) {
! TreeBin e = (TreeBin)table[bin];
! TreeNode p = e.getTreeNode(hash, (K)key);
! if (p != null) {
! // assert p.entry.hash == hash && p.entry.key.equals(key);
! return (Entry<K,V>)p.entry;
! } else {
! return null;
! }
}
return null;
}
+
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
*** 432,511 ****
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
! @SuppressWarnings("unchecked")
! Entry<K,V> e = (Entry<K,V>)table[i];
! for(; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
-
modCount++;
! addEntry(hash, key, value, i);
return null;
}
/**
* Offloaded version of put for null keys
*/
private V putForNullKey(V value) {
! @SuppressWarnings("unchecked")
! Entry<K,V> e = (Entry<K,V>)table[0];
! for(; e != null; e = e.next) {
! if (e.key == null) {
! V oldValue = e.value;
! e.value = value;
! e.recordAccess(this);
return oldValue;
}
- }
modCount++;
! addEntry(0, null, value, 0);
return null;
}
/**
* This method is used instead of put by constructors and
* pseudoconstructors (clone, readObject). It does not resize the table,
! * check for comodification, etc. It calls createEntry rather than
! * addEntry.
*/
private void putForCreate(K key, V value) {
! int hash = null == key ? 0 : hash(key);
int i = indexFor(hash, table.length);
/**
* Look for preexisting entry for key. This will never happen for
* clone or deserialize. It will only happen for construction if the
* input Map is a sorted map whose ordering is inconsistent w/ equals.
*/
! for (@SuppressWarnings("unchecked")
! Entry<?,V> e = (Entry<?,V>)table[i]; e != null; e = e.next) {
Object k;
! if (e.hash == hash &&
! ((k = e.key) == key || (key != null && key.equals(k)))) {
e.value = value;
return;
}
}
! createEntry(hash, key, value, i);
}
private void putAllForCreate(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
putForCreate(e.getKey(), e.getValue());
--- 1052,1192 ----
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
+ @SuppressWarnings("unchecked")
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
! boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
!
! if (table[i] instanceof Entry) {
! // Bin contains ordinary Entries. Search for key in the linked list
! // of entries, counting the number of entries. Only check for
! // TreeBin conversion if the list size is >= TREE_THRESHOLD.
! // (The conversion still may not happen if the table gets resized.)
! int listSize = 0;
! Entry<K,V> e = (Entry<K,V>) table[i];
! for (; e != null; e = (Entry<K,V>)e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
+ listSize++;
+ }
+ // Didn't find, so fall through and call addEntry() to add the
+ // Entry and check for TreeBin conversion.
+ checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
+ } else if (table[i] != null) {
+ TreeBin e = (TreeBin)table[i];
+ TreeNode p = e.putTreeNode(hash, key, value, null);
+ if (p == null) { // putTreeNode() added a new node
+ modCount++;
+ size++;
+ if (size >= threshold) {
+ resize(2 * table.length);
+ }
+ return null;
+ } else { // putTreeNode() found an existing node
+ Entry<K,V> pEntry = (Entry<K,V>)p.entry;
+ V oldVal = pEntry.value;
+ pEntry.value = value;
+ pEntry.recordAccess(this);
+ return oldVal;
+ }
}
modCount++;
! addEntry(hash, key, value, i, checkIfNeedTree);
return null;
}
/**
* Offloaded version of put for null keys
*/
private V putForNullKey(V value) {
! if (nullKeyEntry != null) {
! V oldValue = nullKeyEntry.value;
! nullKeyEntry.value = value;
! nullKeyEntry.recordAccess(this);
return oldValue;
}
modCount++;
! size++; // newEntry() skips size++
! nullKeyEntry = newEntry(0, null, value, null);
return null;
}
+ private void putForCreateNullKey(V value) {
+ // Look for preexisting entry for key. This will never happen for
+ // clone or deserialize. It will only happen for construction if the
+ // input Map is a sorted map whose ordering is inconsistent w/ equals.
+ if (nullKeyEntry != null) {
+ nullKeyEntry.value = value;
+ } else {
+ nullKeyEntry = newEntry(0, null, value, null);
+ size++;
+ }
+ }
+
+
/**
* This method is used instead of put by constructors and
* pseudoconstructors (clone, readObject). It does not resize the table,
! * check for comodification, etc, though it will convert bins to TreeBins
! * as needed. It calls createEntry rather than addEntry.
*/
+ @SuppressWarnings("unchecked")
private void putForCreate(K key, V value) {
! if (null == key) {
! putForCreateNullKey(value);
! return;
! }
! int hash = hash(key);
int i = indexFor(hash, table.length);
+ boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
/**
* Look for preexisting entry for key. This will never happen for
* clone or deserialize. It will only happen for construction if the
* input Map is a sorted map whose ordering is inconsistent w/ equals.
*/
! if (table[i] instanceof Entry) {
! int listSize = 0;
! Entry<K,V> e = (Entry<K,V>) table[i];
! for (; e != null; e = (Entry<K,V>)e.next) {
Object k;
! if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
e.value = value;
return;
}
+ listSize++;
+ }
+ // Didn't find, fall through to createEntry().
+ // Check for conversion to TreeBin done via createEntry().
+ checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
+ } else if (table[i] != null) {
+ TreeBin e = (TreeBin)table[i];
+ TreeNode p = e.putTreeNode(hash, key, value, null);
+ if (p != null) {
+ p.entry.setValue(value); // Found an existing node, set value
+ } else {
+ size++; // Added a new TreeNode, so update size
+ }
+ // don't need modCount++/check for resize - just return
+ return;
}
! createEntry(hash, key, value, i, checkIfNeedTree);
}
private void putAllForCreate(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
putForCreate(e.getKey(), e.getValue());
*** 524,562 ****
* must be greater than current capacity unless current
* capacity is MAXIMUM_CAPACITY (in which case value
* is irrelevant).
*/
void resize(int newCapacity) {
! Entry<?,?>[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
! Entry<?,?>[] newTable = new Entry<?,?>[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* Transfers all entries from current table to newTable.
*/
@SuppressWarnings("unchecked")
! void transfer(Entry<?,?>[] newTable) {
! Entry<?,?>[] src = table;
int newCapacity = newTable.length;
! for (int j = 0; j < src.length; j++ ) {
Entry<K,V> e = (Entry<K,V>) src[j];
! while(null != e) {
! Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = (Entry<K,V>) newTable[i];
newTable[i] = e;
e = next;
}
}
Arrays.fill(table, null);
}
/**
--- 1205,1255 ----
* must be greater than current capacity unless current
* capacity is MAXIMUM_CAPACITY (in which case value
* is irrelevant).
*/
void resize(int newCapacity) {
! Object[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
! Object[] newTable = new Object[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* Transfers all entries from current table to newTable.
+ *
+ * Assumes newTable is larger than table
*/
@SuppressWarnings("unchecked")
! void transfer(Object[] newTable) {
! Object[] src = table;
! // assert newTable.length > src.length : "newTable.length(" +
! // newTable.length + ") expected to be > src.length("+src.length+")";
int newCapacity = newTable.length;
! for (int j = 0; j < src.length; j++) {
! if (src[j] instanceof Entry) {
! // Assume: since wasn't TreeBin before, won't need TreeBin now
Entry<K,V> e = (Entry<K,V>) src[j];
! while (null != e) {
! Entry<K,V> next = (Entry<K,V>)e.next;
int i = indexFor(e.hash, newCapacity);
e.next = (Entry<K,V>) newTable[i];
newTable[i] = e;
e = next;
}
+ } else if (src[j] != null) {
+ TreeBin e = (TreeBin) src[j];
+ TreeBin loTree = new TreeBin();
+ TreeBin hiTree = new TreeBin();
+ e.splitTreeBin(newTable, j, loTree, hiTree);
+ }
}
Arrays.fill(table, null);
}
/**
*** 583,601 ****
* condition could result in a map with twice the appropriate capacity,
* if the keys to be added overlap with the keys already in this map.
* By using the conservative calculation, we subject ourself
* to at most one extra resize.
*/
! if (numKeysToBeAdded > threshold) {
! int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
! if (targetCapacity > MAXIMUM_CAPACITY)
! targetCapacity = MAXIMUM_CAPACITY;
! int newCapacity = table.length;
! while (newCapacity < targetCapacity)
! newCapacity <<= 1;
! if (newCapacity > table.length)
! resize(newCapacity);
}
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
--- 1276,1287 ----
* condition could result in a map with twice the appropriate capacity,
* if the keys to be added overlap with the keys already in this map.
* By using the conservative calculation, we subject ourself
* to at most one extra resize.
*/
! if (numKeysToBeAdded > threshold && table.length < MAXIMUM_CAPACITY) {
! resize(table.length * 2);
}
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
*** 619,662 ****
@Override
public V putIfAbsent(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
! int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
! @SuppressWarnings("unchecked")
! Entry<K,V> e = (Entry<K,V>)table[i];
! for(; e != null; e = e.next) {
if (e.hash == hash && Objects.equals(e.key, key)) {
! if(e.value != null) {
return e.value;
}
e.value = value;
- modCount++;
e.recordAccess(this);
return null;
}
}
!
modCount++;
! addEntry(hash, key, value, i);
return null;
}
@Override
public boolean remove(Object key, Object value) {
if (isEmpty()) {
return false;
}
! int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
@SuppressWarnings("unchecked")
! Entry<K,V> prev = (Entry<K,V>)table[i];
Entry<K,V> e = prev;
-
while (e != null) {
! Entry<K,V> next = e.next;
if (e.hash == hash && Objects.equals(e.key, key)) {
if (!Objects.equals(e.value, value)) {
return false;
}
modCount++;
--- 1305,1391 ----
@Override
public V putIfAbsent(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
! if (key == null) {
! if (nullKeyEntry == null || nullKeyEntry.value == null) {
! putForNullKey(value);
! return null;
! } else {
! return nullKeyEntry.value;
! }
! }
! int hash = hash(key);
int i = indexFor(hash, table.length);
! boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
!
! if (table[i] instanceof Entry) {
! int listSize = 0;
! Entry<K,V> e = (Entry<K,V>) table[i];
! for (; e != null; e = (Entry<K,V>)e.next) {
if (e.hash == hash && Objects.equals(e.key, key)) {
! if (e.value != null) {
return e.value;
}
e.value = value;
e.recordAccess(this);
return null;
}
+ listSize++;
}
! // Didn't find, so fall through and call addEntry() to add the
! // Entry and check for TreeBin conversion.
! checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
! } else if (table[i] != null) {
! TreeBin e = (TreeBin)table[i];
! TreeNode p = e.putTreeNode(hash, key, value, null);
! if (p == null) { // not found, putTreeNode() added a new node
modCount++;
! size++;
! if (size >= threshold) {
! resize(2 * table.length);
! }
! return null;
! } else { // putTreeNode() found an existing node
! Entry<K,V> pEntry = (Entry<K,V>)p.entry;
! V oldVal = pEntry.value;
! if (oldVal == null) { // only replace if maps to null
! pEntry.value = value;
! pEntry.recordAccess(this);
! }
! return oldVal;
! }
! }
! modCount++;
! addEntry(hash, key, value, i, checkIfNeedTree);
return null;
}
@Override
public boolean remove(Object key, Object value) {
if (isEmpty()) {
return false;
}
! if (key == null) {
! if (nullKeyEntry != null &&
! Objects.equals(nullKeyEntry.value, value)) {
! removeNullKey();
! return true;
! }
! return false;
! }
! int hash = hash(key);
int i = indexFor(hash, table.length);
+
+ if (table[i] instanceof Entry) {
@SuppressWarnings("unchecked")
! Entry<K,V> prev = (Entry<K,V>) table[i];
Entry<K,V> e = prev;
while (e != null) {
! @SuppressWarnings("unchecked")
! Entry<K,V> next = (Entry<K,V>) e.next;
if (e.hash == hash && Objects.equals(e.key, key)) {
if (!Objects.equals(e.value, value)) {
return false;
}
modCount++;
*** 669,768 ****
return true;
}
prev = e;
e = next;
}
!
return false;
}
@Override
public boolean replace(K key, V oldValue, V newValue) {
if (isEmpty()) {
return false;
}
! int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
@SuppressWarnings("unchecked")
! Entry<K,V> e = (Entry<K,V>)table[i];
! for (; e != null; e = e.next) {
if (e.hash == hash && Objects.equals(e.key, key) && Objects.equals(e.value, oldValue)) {
e.value = newValue;
e.recordAccess(this);
return true;
}
}
!
return false;
}
@Override
public V replace(K key, V value) {
if (isEmpty()) {
return null;
}
! int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)table[i];
! for (; e != null; e = e.next) {
if (e.hash == hash && Objects.equals(e.key, key)) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
!
! return null;
}
!
! @Override
! public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
! if (table == EMPTY_TABLE) {
! inflateTable(threshold);
}
- int hash = (key == null) ? 0 : hash(key);
- int i = indexFor(hash, table.length);
- @SuppressWarnings("unchecked")
- Entry<K,V> e = (Entry<K,V>)table[i];
- for (; e != null; e = e.next) {
- if (e.hash == hash && Objects.equals(e.key, key)) {
- V oldValue = e.value;
- return oldValue == null ? (e.value = mappingFunction.apply(key)) : oldValue;
}
}
-
V newValue = mappingFunction.apply(key);
! if (newValue != null) {
modCount++;
! addEntry(hash, key, newValue, i);
}
return newValue;
}
@Override
public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
if (isEmpty()) {
return null;
}
! int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
@SuppressWarnings("unchecked")
Entry<K,V> prev = (Entry<K,V>)table[i];
Entry<K,V> e = prev;
-
while (e != null) {
! Entry<K,V> next = e.next;
if (e.hash == hash && Objects.equals(e.key, key)) {
V oldValue = e.value;
if (oldValue == null)
break;
V newValue = remappingFunction.apply(key, oldValue);
- modCount++;
if (newValue == null) {
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
--- 1398,1627 ----
return true;
}
prev = e;
e = next;
}
! } else if (table[i] != null) {
! TreeBin tb = ((TreeBin) table[i]);
! TreeNode p = tb.getTreeNode(hash, (K)key);
! if (p != null) {
! Entry<K,V> pEntry = (Entry<K,V>)p.entry;
! // assert pEntry.key.equals(key);
! if (Objects.equals(pEntry.value, value)) {
! modCount++;
! size--;
! tb.deleteTreeNode(p);
! pEntry.recordRemoval(this);
! if (tb.root == null || tb.first == null) {
! // assert tb.root == null && tb.first == null :
! // "TreeBin.first and root should both be null";
! // TreeBin is now empty, we should blank this bin
! table[i] = null;
! }
! return true;
! }
! }
! }
return false;
}
@Override
public boolean replace(K key, V oldValue, V newValue) {
if (isEmpty()) {
return false;
}
! if (key == null) {
! if (nullKeyEntry != null &&
! Objects.equals(nullKeyEntry.value, oldValue)) {
! putForNullKey(newValue);
! return true;
! }
! return false;
! }
! int hash = hash(key);
int i = indexFor(hash, table.length);
+
+ if (table[i] instanceof Entry) {
@SuppressWarnings("unchecked")
! Entry<K,V> e = (Entry<K,V>) table[i];
! for (; e != null; e = (Entry<K,V>)e.next) {
if (e.hash == hash && Objects.equals(e.key, key) && Objects.equals(e.value, oldValue)) {
e.value = newValue;
e.recordAccess(this);
return true;
}
}
! return false;
! } else if (table[i] != null) {
! TreeBin tb = ((TreeBin) table[i]);
! TreeNode p = tb.getTreeNode(hash, key);
! if (p != null) {
! Entry<K,V> pEntry = (Entry<K,V>)p.entry;
! // assert pEntry.key.equals(key);
! if (Objects.equals(pEntry.value, oldValue)) {
! pEntry.value = newValue;
! pEntry.recordAccess(this);
! return true;
! }
! }
! }
return false;
}
@Override
public V replace(K key, V value) {
if (isEmpty()) {
return null;
}
! if (key == null) {
! if (nullKeyEntry != null) {
! return putForNullKey(value);
! }
! return null;
! }
! int hash = hash(key);
int i = indexFor(hash, table.length);
+ if (table[i] instanceof Entry) {
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)table[i];
! for (; e != null; e = (Entry<K,V>)e.next) {
if (e.hash == hash && Objects.equals(e.key, key)) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
!
! return null;
! } else if (table[i] != null) {
! TreeBin tb = ((TreeBin) table[i]);
! TreeNode p = tb.getTreeNode(hash, key);
! if (p != null) {
! Entry<K,V> pEntry = (Entry<K,V>)p.entry;
! // assert pEntry.key.equals(key);
! V oldValue = pEntry.value;
! pEntry.value = value;
! pEntry.recordAccess(this);
! return oldValue;
! }
! }
! return null;
! }
!
! @Override
! public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
! if (table == EMPTY_TABLE) {
! inflateTable(threshold);
! }
! if (key == null) {
! if (nullKeyEntry == null || nullKeyEntry.value == null) {
! V newValue = mappingFunction.apply(key);
! if (newValue != null) {
! putForNullKey(newValue);
! }
! return newValue;
! }
! return nullKeyEntry.value;
! }
! int hash = hash(key);
! int i = indexFor(hash, table.length);
! boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
!
! if (table[i] instanceof Entry) {
! int listSize = 0;
! @SuppressWarnings("unchecked")
! Entry<K,V> e = (Entry<K,V>)table[i];
! for (; e != null; e = (Entry<K,V>)e.next) {
! if (e.hash == hash && Objects.equals(e.key, key)) {
! V oldValue = e.value;
! if (oldValue == null) {
! V newValue = mappingFunction.apply(key);
! if (newValue != null) {
! e.value = newValue;
! e.recordAccess(this);
! }
! return newValue;
! }
! return oldValue;
! }
! listSize++;
! }
! // Didn't find, fall through to call the mapping function
! checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
! } else if (table[i] != null) {
! TreeBin e = (TreeBin)table[i];
! V value = mappingFunction.apply(key);
! if (value == null) { // Return the existing value, if any
! TreeNode p = e.getTreeNode(hash, key);
! if (p != null) {
! return (V) p.entry.value;
! }
! return null;
! } else { // Put the new value into the Tree, if absent
! TreeNode p = e.putTreeNode(hash, key, value, null);
! if (p == null) { // not found, new node was added
! modCount++;
! size++;
! if (size >= threshold) {
! resize(2 * table.length);
! }
! return value;
! } else { // putTreeNode() found an existing node
! Entry<K,V> pEntry = (Entry<K,V>)p.entry;
! V oldVal = pEntry.value;
! if (oldVal == null) { // only replace if maps to null
! pEntry.value = value;
! pEntry.recordAccess(this);
! return value;
}
! return oldVal;
}
}
}
V newValue = mappingFunction.apply(key);
! if (newValue != null) { // add Entry and check for TreeBin conversion
modCount++;
! addEntry(hash, key, newValue, i, checkIfNeedTree);
}
return newValue;
}
@Override
public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
if (isEmpty()) {
return null;
}
! if (key == null) {
! V oldValue;
! if (nullKeyEntry != null && (oldValue = nullKeyEntry.value) != null) {
! V newValue = remappingFunction.apply(key, oldValue);
! if (newValue != null ) {
! putForNullKey(newValue);
! return newValue;
! } else {
! removeNullKey();
! }
! }
! return null;
! }
! int hash = hash(key);
int i = indexFor(hash, table.length);
+ if (table[i] instanceof Entry) {
@SuppressWarnings("unchecked")
Entry<K,V> prev = (Entry<K,V>)table[i];
Entry<K,V> e = prev;
while (e != null) {
! Entry<K,V> next = (Entry<K,V>)e.next;
if (e.hash == hash && Objects.equals(e.key, key)) {
V oldValue = e.value;
if (oldValue == null)
break;
V newValue = remappingFunction.apply(key, oldValue);
if (newValue == null) {
+ modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
*** 774,806 ****
return newValue;
}
prev = e;
e = next;
}
!
return null;
}
@Override
public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
! int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
@SuppressWarnings("unchecked")
Entry<K,V> prev = (Entry<K,V>)table[i];
Entry<K,V> e = prev;
while (e != null) {
! Entry<K,V> next = e.next;
if (e.hash == hash && Objects.equals(e.key, key)) {
V oldValue = e.value;
V newValue = remappingFunction.apply(key, oldValue);
if (newValue != oldValue) {
- modCount++;
if (newValue == null) {
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
--- 1633,1708 ----
return newValue;
}
prev = e;
e = next;
}
! } else if (table[i] != null) {
! TreeBin tb = (TreeBin)table[i];
! TreeNode p = tb.getTreeNode(hash, key);
! if (p != null) {
! Entry<K,V> pEntry = (Entry<K,V>)p.entry;
! // assert pEntry.key.equals(key);
! V oldValue = pEntry.value;
! if (oldValue != null) {
! V newValue = remappingFunction.apply(key, oldValue);
! if (newValue == null) { // remove mapping
! modCount++;
! size--;
! tb.deleteTreeNode(p);
! pEntry.recordRemoval(this);
! if (tb.root == null || tb.first == null) {
! // assert tb.root == null && tb.first == null :
! // "TreeBin.first and root should both be null";
! // TreeBin is now empty, we should blank this bin
! table[i] = null;
! }
! } else {
! pEntry.value = newValue;
! pEntry.recordAccess(this);
! }
! return newValue;
! }
! }
! }
return null;
}
@Override
public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
! if (key == null) {
! V oldValue = nullKeyEntry == null ? null : nullKeyEntry.value;
! V newValue = remappingFunction.apply(key, oldValue);
! if (newValue != oldValue) {
! if (newValue == null) {
! removeNullKey();
! } else {
! putForNullKey(newValue);
! }
! }
! return newValue;
! }
! int hash = hash(key);
int i = indexFor(hash, table.length);
+ boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
+
+ if (table[i] instanceof Entry) {
+ int listSize = 0;
@SuppressWarnings("unchecked")
Entry<K,V> prev = (Entry<K,V>)table[i];
Entry<K,V> e = prev;
while (e != null) {
! Entry<K,V> next = (Entry<K,V>)e.next;
if (e.hash == hash && Objects.equals(e.key, key)) {
V oldValue = e.value;
V newValue = remappingFunction.apply(key, oldValue);
if (newValue != oldValue) {
if (newValue == null) {
+ modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
*** 812,850 ****
}
return newValue;
}
prev = e;
e = next;
}
V newValue = remappingFunction.apply(key, null);
if (newValue != null) {
modCount++;
! addEntry(hash, key, newValue, i);
}
return newValue;
}
@Override
public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
! int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
@SuppressWarnings("unchecked")
Entry<K,V> prev = (Entry<K,V>)table[i];
Entry<K,V> e = prev;
while (e != null) {
! Entry<K,V> next = e.next;
if (e.hash == hash && Objects.equals(e.key, key)) {
V oldValue = e.value;
! V newValue = remappingFunction.apply(oldValue, value);
! modCount++;
if (newValue == null) {
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
--- 1714,1805 ----
}
return newValue;
}
prev = e;
e = next;
+ listSize++;
+ }
+ checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
+ } else if (table[i] != null) {
+ TreeBin tb = (TreeBin)table[i];
+ TreeNode p = tb.getTreeNode(hash, key);
+ V oldValue = p == null ? null : (V)p.entry.value;
+ V newValue = remappingFunction.apply(key, oldValue);
+ if (newValue != oldValue) {
+ if (newValue == null) {
+ Entry<K,V> pEntry = (Entry<K,V>)p.entry;
+ modCount++;
+ size--;
+ tb.deleteTreeNode(p);
+ pEntry.recordRemoval(this);
+ if (tb.root == null || tb.first == null) {
+ // assert tb.root == null && tb.first == null :
+ // "TreeBin.first and root should both be null";
+ // TreeBin is now empty, we should blank this bin
+ table[i] = null;
+ }
+ } else {
+ if (p != null) { // just update the value
+ Entry<K,V> pEntry = (Entry<K,V>)p.entry;
+ pEntry.value = newValue;
+ pEntry.recordAccess(this);
+ } else { // need to put new node
+ p = tb.putTreeNode(hash, key, newValue, null);
+ // assert p == null; // should have added a new node
+ modCount++;
+ size++;
+ if (size >= threshold) {
+ resize(2 * table.length);
+ }
+ }
+ }
+ }
+ return newValue;
}
V newValue = remappingFunction.apply(key, null);
if (newValue != null) {
modCount++;
! addEntry(hash, key, newValue, i, checkIfNeedTree);
}
return newValue;
}
@Override
public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
! if (key == null) {
! V oldValue = nullKeyEntry == null ? null : nullKeyEntry.value;
! V newValue = oldValue == null ? value : remappingFunction.apply(oldValue, value);
! if (newValue != null) {
! putForNullKey(newValue);
! } else if (nullKeyEntry != null) {
! removeNullKey();
! }
! return newValue;
! }
! int hash = hash(key);
int i = indexFor(hash, table.length);
+ boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
+
+ if (table[i] instanceof Entry) {
+ int listSize = 0;
@SuppressWarnings("unchecked")
Entry<K,V> prev = (Entry<K,V>)table[i];
Entry<K,V> e = prev;
while (e != null) {
! Entry<K,V> next = (Entry<K,V>)e.next;
if (e.hash == hash && Objects.equals(e.key, key)) {
V oldValue = e.value;
! V newValue = (oldValue == null) ? value :
! remappingFunction.apply(oldValue, value);
if (newValue == null) {
+ modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
*** 855,896 ****
}
return newValue;
}
prev = e;
e = next;
}
if (value != null) {
modCount++;
! addEntry(hash, key, value, i);
}
-
return value;
}
// end of optimized implementations of default methods in Map
/**
* Removes and returns the entry associated with the specified key
* in the HashMap. Returns null if the HashMap contains no mapping
* for this key.
*/
final Entry<K,V> removeEntryForKey(Object key) {
if (isEmpty()) {
return null;
}
! int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
@SuppressWarnings("unchecked")
Entry<K,V> prev = (Entry<K,V>)table[i];
Entry<K,V> e = prev;
while (e != null) {
! Entry<K,V> next = e.next;
! Object k;
! if (e.hash == hash &&
! ((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
--- 1810,1903 ----
}
return newValue;
}
prev = e;
e = next;
+ listSize++;
}
+ // Didn't find, so fall through and (maybe) call addEntry() to add
+ // the Entry and check for TreeBin conversion.
+ checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
+ } else if (table[i] != null) {
+ TreeBin tb = (TreeBin)table[i];
+ TreeNode p = tb.getTreeNode(hash, key);
+ V oldValue = p == null ? null : (V)p.entry.value;
+ V newValue = (oldValue == null) ? value :
+ remappingFunction.apply(oldValue, value);
+ if (newValue == null) {
+ if (p != null) {
+ Entry<K,V> pEntry = (Entry<K,V>)p.entry;
+ modCount++;
+ size--;
+ tb.deleteTreeNode(p);
+ pEntry.recordRemoval(this);
+ if (tb.root == null || tb.first == null) {
+ // assert tb.root == null && tb.first == null :
+ // "TreeBin.first and root should both be null";
+ // TreeBin is now empty, we should blank this bin
+ table[i] = null;
+ }
+ }
+ return null;
+ } else if (newValue != oldValue) {
+ if (p != null) { // just update the value
+ Entry<K,V> pEntry = (Entry<K,V>)p.entry;
+ pEntry.value = newValue;
+ pEntry.recordAccess(this);
+ } else { // need to put new node
+ p = tb.putTreeNode(hash, key, newValue, null);
+ // assert p == null; // should have added a new node
+ modCount++;
+ size++;
+ if (size >= threshold) {
+ resize(2 * table.length);
+ }
+ }
+ }
+ return newValue;
+ }
if (value != null) {
modCount++;
! addEntry(hash, key, value, i, checkIfNeedTree);
}
return value;
}
// end of optimized implementations of default methods in Map
/**
* Removes and returns the entry associated with the specified key
* in the HashMap. Returns null if the HashMap contains no mapping
* for this key.
+ *
+ * We don't bother converting TreeBins back to Entry lists if the bin falls
+ * back below TREE_THRESHOLD, but we do clear bins when removing the last
+ * TreeNode in a TreeBin.
*/
final Entry<K,V> removeEntryForKey(Object key) {
if (isEmpty()) {
return null;
}
! if (key == null) {
! if (nullKeyEntry != null) {
! return removeNullKey();
! }
! return null;
! }
! int hash = hash(key);
int i = indexFor(hash, table.length);
+
+ if (table[i] instanceof Entry) {
@SuppressWarnings("unchecked")
Entry<K,V> prev = (Entry<K,V>)table[i];
Entry<K,V> e = prev;
while (e != null) {
! @SuppressWarnings("unchecked")
! Entry<K,V> next = (Entry<K,V>) e.next;
! if (e.hash == hash && Objects.equals(e.key, key)) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
*** 899,910 ****
return e;
}
prev = e;
e = next;
}
!
! return e;
}
/**
* Special version of remove for EntrySet using {@code Map.Entry.equals()}
* for matching.
--- 1906,1935 ----
return e;
}
prev = e;
e = next;
}
! } else if (table[i] != null) {
! TreeBin tb = ((TreeBin) table[i]);
! TreeNode p = tb.getTreeNode(hash, (K)key);
! if (p != null) {
! Entry<K,V> pEntry = (Entry<K,V>)p.entry;
! // assert pEntry.key.equals(key);
! modCount++;
! size--;
! tb.deleteTreeNode(p);
! pEntry.recordRemoval(this);
! if (tb.root == null || tb.first == null) {
! // assert tb.root == null && tb.first == null :
! // "TreeBin.first and root should both be null";
! // TreeBin is now empty, we should blank this bin
! table[i] = null;
! }
! return pEntry;
! }
! }
! return null;
}
/**
* Special version of remove for EntrySet using {@code Map.Entry.equals()}
* for matching.
*** 913,930 ****
if (isEmpty() || !(o instanceof Map.Entry))
return null;
Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
Object key = entry.getKey();
! int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
@SuppressWarnings("unchecked")
Entry<K,V> prev = (Entry<K,V>)table[i];
Entry<K,V> e = prev;
while (e != null) {
! Entry<K,V> next = e.next;
if (e.hash == hash && e.equals(entry)) {
modCount++;
size--;
if (prev == e)
table[i] = next;
--- 1938,1966 ----
if (isEmpty() || !(o instanceof Map.Entry))
return null;
Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
Object key = entry.getKey();
!
! if (key == null) {
! if (entry.equals(nullKeyEntry)) {
! return removeNullKey();
! }
! return null;
! }
!
! int hash = hash(key);
int i = indexFor(hash, table.length);
+
+ if (table[i] instanceof Entry) {
@SuppressWarnings("unchecked")
Entry<K,V> prev = (Entry<K,V>)table[i];
Entry<K,V> e = prev;
while (e != null) {
! @SuppressWarnings("unchecked")
! Entry<K,V> next = (Entry<K,V>)e.next;
if (e.hash == hash && e.equals(entry)) {
modCount++;
size--;
if (prev == e)
table[i] = next;
*** 934,953 ****
return e;
}
prev = e;
e = next;
}
! return e;
}
/**
* Removes all of the mappings from this map.
* The map will be empty after this call returns.
*/
public void clear() {
modCount++;
Arrays.fill(table, null);
size = 0;
}
/**
--- 1970,2027 ----
return e;
}
prev = e;
e = next;
}
+ } else if (table[i] != null) {
+ TreeBin tb = ((TreeBin) table[i]);
+ TreeNode p = tb.getTreeNode(hash, (K)key);
+ if (p != null && p.entry.equals(entry)) {
+ @SuppressWarnings("unchecked")
+ Entry<K,V> pEntry = (Entry<K,V>)p.entry;
+ // assert pEntry.key.equals(key);
+ modCount++;
+ size--;
+ tb.deleteTreeNode(p);
+ pEntry.recordRemoval(this);
+ if (tb.root == null || tb.first == null) {
+ // assert tb.root == null && tb.first == null :
+ // "TreeBin.first and root should both be null";
+ // TreeBin is now empty, we should blank this bin
+ table[i] = null;
+ }
+ return pEntry;
+ }
+ }
+ return null;
+ }
! /*
! * Remove the mapping for the null key, and update internal accounting
! * (size, modcount, recordRemoval, etc).
! *
! * Assumes nullKeyEntry is non-null.
! */
! private Entry<K,V> removeNullKey() {
! // assert nullKeyEntry != null;
! Entry<K,V> retVal = nullKeyEntry;
! modCount++;
! size--;
! retVal.recordRemoval(this);
! nullKeyEntry = null;
! return retVal;
}
/**
* Removes all of the mappings from this map.
* The map will be empty after this call returns.
*/
public void clear() {
modCount++;
+ if (nullKeyEntry != null) {
+ nullKeyEntry = null;
+ }
Arrays.fill(table, null);
size = 0;
}
/**
*** 957,987 ****
* @param value value whose presence in this map is to be tested
* @return <tt>true</tt> if this map maps one or more keys to the
* specified value
*/
public boolean containsValue(Object value) {
! if (value == null)
return containsNullValue();
!
! Entry<?,?>[] tab = table;
! for (int i = 0; i < tab.length; i++)
! for (Entry<?,?> e = tab[i]; e != null; e = e.next)
! if (value.equals(e.value))
return true;
! return false;
}
/**
* Special-case code for containsValue with null argument
*/
private boolean containsNullValue() {
! Entry<?,?>[] tab = table;
! for (int i = 0; i < tab.length; i++)
! for (Entry<?,?> e = tab[i]; e != null; e = e.next)
! if (e.value == null)
return true;
! return false;
}
/**
* Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
* values themselves are not cloned.
--- 2031,2092 ----
* @param value value whose presence in this map is to be tested
* @return <tt>true</tt> if this map maps one or more keys to the
* specified value
*/
public boolean containsValue(Object value) {
! if (value == null) {
return containsNullValue();
! }
! Object[] tab = table;
! for (int i = 0; i < tab.length; i++) {
! if (tab[i] instanceof Entry) {
! Entry<?,?> e = (Entry<?,?>)tab[i];
! for (; e != null; e = (Entry<?,?>)e.next) {
! if (value.equals(e.value)) {
! return true;
! }
! }
! } else if (tab[i] != null) {
! TreeBin e = (TreeBin)tab[i];
! TreeNode p = e.first;
! for (; p != null; p = (TreeNode) p.entry.next) {
! if (value == p.entry.value || value.equals(p.entry.value)) {
return true;
! }
! }
! }
! }
! // Didn't find value in table - could be in nullKeyEntry
! return (nullKeyEntry != null && (value == nullKeyEntry.value ||
! value.equals(nullKeyEntry.value)));
}
/**
* Special-case code for containsValue with null argument
*/
private boolean containsNullValue() {
! Object[] tab = table;
! for (int i = 0; i < tab.length; i++) {
! if (tab[i] instanceof Entry) {
! Entry<K,V> e = (Entry<K,V>)tab[i];
! for (; e != null; e = (Entry<K,V>)e.next) {
! if (e.value == null) {
! return true;
! }
! }
! } else if (tab[i] != null) {
! TreeBin e = (TreeBin)tab[i];
! TreeNode p = e.first;
! for (; p != null; p = (TreeNode) p.entry.next) {
! if (p.entry.value == null) {
return true;
! }
! }
! }
! }
! // Didn't find value in table - could be in nullKeyEntry
! return (nullKeyEntry != null && nullKeyEntry.value == null);
}
/**
* Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
* values themselves are not cloned.
*** 1005,1030 ****
table.length));
}
result.entrySet = null;
result.modCount = 0;
result.size = 0;
result.init();
result.putAllForCreate(this);
return result;
}
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
! Entry<K,V> next;
final int hash;
/**
* Creates new entry.
*/
! Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
--- 2110,2136 ----
table.length));
}
result.entrySet = null;
result.modCount = 0;
result.size = 0;
+ result.nullKeyEntry = null;
result.init();
result.putAllForCreate(this);
return result;
}
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
! Object next; // an Entry, or a TreeNode
final int hash;
/**
* Creates new entry.
*/
! Entry(int h, K k, V v, Object n) {
value = v;
next = n;
key = k;
hash = h;
}
*** 1066,1077 ****
return getKey() + "=" + getValue();
}
/**
* This method is invoked whenever the value in an entry is
! * overwritten by an invocation of put(k,v) for a key k that's already
! * in the HashMap.
*/
void recordAccess(HashMap<K,V> m) {
}
/**
--- 2172,2182 ----
return getKey() + "=" + getValue();
}
/**
* This method is invoked whenever the value in an entry is
! * overwritten for a key that's already in the HashMap.
*/
void recordAccess(HashMap<K,V> m) {
}
/**
*** 1080,1167 ****
*/
void recordRemoval(HashMap<K,V> m) {
}
}
/**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket. It is the responsibility of this
! * method to resize the table if appropriate.
*
* Subclass overrides this to alter the behavior of put method.
*/
! void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
! hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
!
! createEntry(hash, key, value, bucketIndex);
}
/**
! * Like addEntry except that this version is used when creating entries
* as part of Map construction or "pseudo-construction" (cloning,
! * deserialization). This version needn't worry about resizing the table.
*
! * Subclass overrides this to alter the behavior of HashMap(Map),
! * clone, and readObject.
*/
! void createEntry(int hash, K key, V value, int bucketIndex) {
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)table[bucketIndex];
! table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
private abstract class HashIterator<E> implements Iterator<E> {
! Entry<?,?> next; // next entry to return
int expectedModCount; // For fast-fail
int index; // current slot
! Entry<?,?> current; // current entry
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
! Entry<?,?>[] t = table;
! while (index < t.length && (next = t[index++]) == null)
! ;
}
}
public final boolean hasNext() {
return next != null;
}
@SuppressWarnings("unchecked")
final Entry<K,V> nextEntry() {
! if (modCount != expectedModCount)
throw new ConcurrentModificationException();
! Entry<?,?> e = next;
if (e == null)
throw new NoSuchElementException();
! if ((next = e.next) == null) {
! Entry<?,?>[] t = table;
! while (index < t.length && (next = t[index++]) == null)
! ;
}
current = e;
! return (Entry<K,V>)e;
}
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
! Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
}
private final class ValueIterator extends HashIterator<V> {
public V next() {
return nextEntry().value;
--- 2185,2349 ----
*/
void recordRemoval(HashMap<K,V> m) {
}
}
+ void addEntry(int hash, K key, V value, int bucketIndex) {
+ addEntry(hash, key, value, bucketIndex, true);
+ }
+
/**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket. It is the responsibility of this
! * method to resize the table if appropriate. The new entry is then
! * created by calling createEntry().
*
* Subclass overrides this to alter the behavior of put method.
+ *
+ * If checkIfNeedTree is false, it is known that this bucket will not need
+ * to be converted to a TreeBin, so don't bothering checking.
+ *
+ * Assumes key is not null.
*/
! void addEntry(int hash, K key, V value, int bucketIndex, boolean checkIfNeedTree) {
! // assert key != null;
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
! hash = hash(key);
bucketIndex = indexFor(hash, table.length);
}
! createEntry(hash, key, value, bucketIndex, checkIfNeedTree);
}
/**
! * Called by addEntry(), and also used when creating entries
* as part of Map construction or "pseudo-construction" (cloning,
! * deserialization). This version does not check for resizing of the table.
! *
! * This method is responsible for converting a bucket to a TreeBin once
! * TREE_THRESHOLD is reached. However if checkIfNeedTree is false, it is known
! * that this bucket will not need to be converted to a TreeBin, so don't
! * bother checking. The new entry is constructed by calling newEntry().
*
! * Assumes key is not null.
! *
! * Note: buckets already converted to a TreeBin don't call this method, but
! * instead call TreeBin.putTreeNode() to create new entries.
*/
! void createEntry(int hash, K key, V value, int bucketIndex, boolean checkIfNeedTree) {
! // assert key != null;
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)table[bucketIndex];
! table[bucketIndex] = newEntry(hash, key, value, e);
size++;
+
+ if (checkIfNeedTree) {
+ int listSize = 0;
+ for (e = (Entry<K,V>) table[bucketIndex]; e != null; e = (Entry<K,V>)e.next) {
+ listSize++;
+ if (listSize >= TreeBin.TREE_THRESHOLD) { // Convert to TreeBin
+ if (comparableClassFor(key) != null) {
+ TreeBin t = new TreeBin();
+ t.populate((Entry)table[bucketIndex]);
+ table[bucketIndex] = t;
+ }
+ break;
}
+ }
+ }
+ }
+
+ /*
+ * Factory method to create a new Entry object.
+ */
+ Entry<K,V> newEntry(int hash, K key, V value, Object next) {
+ return new HashMap.Entry<>(hash, key, value, next);
+ }
+
private abstract class HashIterator<E> implements Iterator<E> {
! Object next; // next entry to return, an Entry or a TreeNode
int expectedModCount; // For fast-fail
int index; // current slot
! Object current; // current entry, an Entry or a TreeNode
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
! if (nullKeyEntry != null) {
! // assert nullKeyEntry.next == null;
! // This works with nextEntry(): nullKeyEntry isa Entry, and
! // e.next will be null, so we'll hit the findNextBin() call.
! next = nullKeyEntry;
! } else {
! findNextBin();
! }
}
}
public final boolean hasNext() {
return next != null;
}
@SuppressWarnings("unchecked")
final Entry<K,V> nextEntry() {
! if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
! }
! Object e = next;
! Entry<K,V> retVal;
!
if (e == null)
throw new NoSuchElementException();
! if (e instanceof Entry) {
! retVal = (Entry<K,V>)e;
! next = ((Entry<K,V>)e).next;
! } else { // TreeBin
! retVal = (Entry<K,V>)((TreeNode)e).entry;
! next = retVal.next;
! }
!
! if (next == null) { // Move to next bin
! findNextBin();
}
current = e;
! return retVal;
}
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
! K k;
!
! if (current instanceof Entry) {
! k = ((Entry<K,V>)current).key;
! } else {
! k = ((Entry<K,V>)((TreeNode)current).entry).key;
!
! }
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
+
+ /*
+ * Set 'next' to the first entry of the next non-empty bin in the table
+ */
+ private void findNextBin() {
+ // assert next == null;
+ Object[] t = table;
+
+ while (index < t.length && (next = t[index++]) == null)
+ ;
+ if (next instanceof HashMap.TreeBin) { // Point to the first TreeNode
+ next = ((TreeBin) next).first;
+ // assert next != null; // There should be no empty TreeBins
+ }
+ }
}
private final class ValueIterator extends HashIterator<V> {
public V next() {
return nextEntry().value;
*** 1387,1398 ****
--- 2569,2582 ----
throw new InvalidObjectException("Illegal load factor: " +
loadFactor);
}
// set other fields that need values
+ if (Holder.USE_HASHSEED) {
Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
sun.misc.Hashing.randomHashSeed(this));
+ }
table = EMPTY_TABLE;
// Read in number of buckets
s.readInt(); // ignored.
*** 1434,1457 ****
/**
* Standin until HM overhaul; based loosely on Weak and Identity HM.
*/
static class HashMapSpliterator<K,V> {
final HashMap<K,V> map;
! HashMap.Entry<K,V> current; // current node
int index; // current index, modified on advance/split
int fence; // one past last index
int est; // size estimate
int expectedModCount; // for comodification checks
HashMapSpliterator(HashMap<K,V> m, int origin,
int fence, int est,
int expectedModCount) {
this.map = m;
this.index = origin;
this.fence = fence;
this.est = est;
this.expectedModCount = expectedModCount;
}
final int getFence() { // initialize fence and size on first use
int hi;
if ((hi = fence) < 0) {
--- 2618,2648 ----
/**
* Standin until HM overhaul; based loosely on Weak and Identity HM.
*/
static class HashMapSpliterator<K,V> {
final HashMap<K,V> map;
! Object current; // current node, can be Entry or TreeNode
int index; // current index, modified on advance/split
int fence; // one past last index
int est; // size estimate
int expectedModCount; // for comodification checks
+ boolean acceptedNull; // Have we accepted the null key?
+ // Without this, we can't distinguish
+ // between being at the very beginning (and
+ // needing to accept null), or being at the
+ // end of the list in bin 0. In both cases,
+ // current == null && index == 0.
HashMapSpliterator(HashMap<K,V> m, int origin,
int fence, int est,
int expectedModCount) {
this.map = m;
this.index = origin;
this.fence = fence;
this.est = est;
this.expectedModCount = expectedModCount;
+ this.acceptedNull = false;
}
final int getFence() { // initialize fence and size on first use
int hi;
if ((hi = fence) < 0) {
*** 1477,1512 ****
super(m, origin, fence, est, expectedModCount);
}
public KeySpliterator<K,V> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
! return (lo >= mid || current != null) ? null :
! new KeySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
! expectedModCount);
}
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super K> action) {
int i, hi, mc;
if (action == null)
throw new NullPointerException();
HashMap<K,V> m = map;
! HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])m.table;
if ((hi = fence) < 0) {
mc = expectedModCount = m.modCount;
hi = fence = tab.length;
}
else
mc = expectedModCount;
if (tab.length >= hi && (i = index) >= 0 && i < (index = hi)) {
! HashMap.Entry<K,V> p = current;
do {
! if (p == null)
p = tab[i++];
! else {
! action.accept(p.getKey());
! p = p.next;
}
} while (p != null || i < hi);
if (m.modCount != mc)
throw new ConcurrentModificationException();
}
--- 2668,2725 ----
super(m, origin, fence, est, expectedModCount);
}
public KeySpliterator<K,V> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
! if (lo >= mid || current != null) {
! return null;
! } else {
! KeySpliterator<K,V> retVal = new KeySpliterator<K,V>(map, lo,
! index = mid, est >>>= 1, expectedModCount);
! // Only 'this' Spliterator chould check for null.
! retVal.acceptedNull = true;
! return retVal;
! }
}
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super K> action) {
int i, hi, mc;
if (action == null)
throw new NullPointerException();
HashMap<K,V> m = map;
! Object[] tab = m.table;
if ((hi = fence) < 0) {
mc = expectedModCount = m.modCount;
hi = fence = tab.length;
}
else
mc = expectedModCount;
+
+ if (!acceptedNull) {
+ acceptedNull = true;
+ if (m.nullKeyEntry != null) {
+ action.accept(m.nullKeyEntry.key);
+ }
+ }
if (tab.length >= hi && (i = index) >= 0 && i < (index = hi)) {
! Object p = current;
do {
! if (p == null) {
p = tab[i++];
! if (p instanceof HashMap.TreeBin) {
! p = ((HashMap.TreeBin)p).first;
! }
! } else {
! HashMap.Entry<K,V> entry;
! if (p instanceof HashMap.Entry) {
! entry = (HashMap.Entry<K,V>)p;
! } else {
! entry = (HashMap.Entry<K,V>)((TreeNode)p).entry;
! }
! action.accept(entry.key);
! p = entry.next;
}
} while (p != null || i < hi);
if (m.modCount != mc)
throw new ConcurrentModificationException();
}
*** 1515,1532 ****
@SuppressWarnings("unchecked")
public boolean tryAdvance(Consumer<? super K> action) {
int hi;
if (action == null)
throw new NullPointerException();
! HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])map.table;
! if (tab.length >= (hi = getFence()) && index >= 0) {
while (current != null || index < hi) {
! if (current == null)
current = tab[index++];
! else {
! K k = current.getKey();
! current = current.next;
action.accept(k);
if (map.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
--- 2728,2765 ----
@SuppressWarnings("unchecked")
public boolean tryAdvance(Consumer<? super K> action) {
int hi;
if (action == null)
throw new NullPointerException();
! Object[] tab = map.table;
! hi = getFence();
!
! if (!acceptedNull) {
! acceptedNull = true;
! if (map.nullKeyEntry != null) {
! action.accept(map.nullKeyEntry.key);
! if (map.modCount != expectedModCount)
! throw new ConcurrentModificationException();
! return true;
! }
! }
! if (tab.length >= hi && index >= 0) {
while (current != null || index < hi) {
! if (current == null) {
current = tab[index++];
! if (current instanceof HashMap.TreeBin) {
! current = ((HashMap.TreeBin)current).first;
! }
! } else {
! HashMap.Entry<K,V> entry;
! if (current instanceof HashMap.Entry) {
! entry = (HashMap.Entry<K,V>)current;
! } else {
! entry = (HashMap.Entry<K,V>)((TreeNode)current).entry;
! }
! K k = entry.key;
! current = entry.next;
action.accept(k);
if (map.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
*** 1549,1584 ****
super(m, origin, fence, est, expectedModCount);
}
public ValueSpliterator<K,V> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
! return (lo >= mid || current != null) ? null :
! new ValueSpliterator<K,V>(map, lo, index = mid, est >>>= 1,
! expectedModCount);
}
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super V> action) {
int i, hi, mc;
if (action == null)
throw new NullPointerException();
HashMap<K,V> m = map;
! HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])m.table;
if ((hi = fence) < 0) {
mc = expectedModCount = m.modCount;
hi = fence = tab.length;
}
else
mc = expectedModCount;
if (tab.length >= hi && (i = index) >= 0 && i < (index = hi)) {
! HashMap.Entry<K,V> p = current;
do {
! if (p == null)
p = tab[i++];
! else {
! action.accept(p.getValue());
! p = p.next;
}
} while (p != null || i < hi);
if (m.modCount != mc)
throw new ConcurrentModificationException();
}
--- 2782,2839 ----
super(m, origin, fence, est, expectedModCount);
}
public ValueSpliterator<K,V> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
! if (lo >= mid || current != null) {
! return null;
! } else {
! ValueSpliterator<K,V> retVal = new ValueSpliterator<K,V>(map,
! lo, index = mid, est >>>= 1, expectedModCount);
! // Only 'this' Spliterator chould check for null.
! retVal.acceptedNull = true;
! return retVal;
! }
}
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super V> action) {
int i, hi, mc;
if (action == null)
throw new NullPointerException();
HashMap<K,V> m = map;
! Object[] tab = m.table;
if ((hi = fence) < 0) {
mc = expectedModCount = m.modCount;
hi = fence = tab.length;
}
else
mc = expectedModCount;
+
+ if (!acceptedNull) {
+ acceptedNull = true;
+ if (m.nullKeyEntry != null) {
+ action.accept(m.nullKeyEntry.value);
+ }
+ }
if (tab.length >= hi && (i = index) >= 0 && i < (index = hi)) {
! Object p = current;
do {
! if (p == null) {
p = tab[i++];
! if (p instanceof HashMap.TreeBin) {
! p = ((HashMap.TreeBin)p).first;
! }
! } else {
! HashMap.Entry<K,V> entry;
! if (p instanceof HashMap.Entry) {
! entry = (HashMap.Entry<K,V>)p;
! } else {
! entry = (HashMap.Entry<K,V>)((TreeNode)p).entry;
! }
! action.accept(entry.value);
! p = entry.next;
}
} while (p != null || i < hi);
if (m.modCount != mc)
throw new ConcurrentModificationException();
}
*** 1587,1604 ****
@SuppressWarnings("unchecked")
public boolean tryAdvance(Consumer<? super V> action) {
int hi;
if (action == null)
throw new NullPointerException();
! HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])map.table;
! if (tab.length >= (hi = getFence()) && index >= 0) {
while (current != null || index < hi) {
! if (current == null)
current = tab[index++];
! else {
! V v = current.getValue();
! current = current.next;
action.accept(v);
if (map.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
--- 2842,2879 ----
@SuppressWarnings("unchecked")
public boolean tryAdvance(Consumer<? super V> action) {
int hi;
if (action == null)
throw new NullPointerException();
! Object[] tab = map.table;
! hi = getFence();
!
! if (!acceptedNull) {
! acceptedNull = true;
! if (map.nullKeyEntry != null) {
! action.accept(map.nullKeyEntry.value);
! if (map.modCount != expectedModCount)
! throw new ConcurrentModificationException();
! return true;
! }
! }
! if (tab.length >= hi && index >= 0) {
while (current != null || index < hi) {
! if (current == null) {
current = tab[index++];
! if (current instanceof HashMap.TreeBin) {
! current = ((HashMap.TreeBin)current).first;
! }
! } else {
! HashMap.Entry<K,V> entry;
! if (current instanceof HashMap.Entry) {
! entry = (Entry<K,V>)current;
! } else {
! entry = (Entry<K,V>)((TreeNode)current).entry;
! }
! V v = entry.value;
! current = entry.next;
action.accept(v);
if (map.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
*** 1620,1655 ****
super(m, origin, fence, est, expectedModCount);
}
public EntrySpliterator<K,V> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
! return (lo >= mid || current != null) ? null :
! new EntrySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
! expectedModCount);
}
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
int i, hi, mc;
if (action == null)
throw new NullPointerException();
HashMap<K,V> m = map;
! HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])m.table;
if ((hi = fence) < 0) {
mc = expectedModCount = m.modCount;
hi = fence = tab.length;
}
else
mc = expectedModCount;
if (tab.length >= hi && (i = index) >= 0 && i < (index = hi)) {
! HashMap.Entry<K,V> p = current;
do {
! if (p == null)
p = tab[i++];
! else {
! action.accept(p);
! p = p.next;
}
} while (p != null || i < hi);
if (m.modCount != mc)
throw new ConcurrentModificationException();
}
--- 2895,2953 ----
super(m, origin, fence, est, expectedModCount);
}
public EntrySpliterator<K,V> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
! if (lo >= mid || current != null) {
! return null;
! } else {
! EntrySpliterator<K,V> retVal = new EntrySpliterator<K,V>(map,
! lo, index = mid, est >>>= 1, expectedModCount);
! // Only 'this' Spliterator chould check for null.
! retVal.acceptedNull = true;
! return retVal;
! }
}
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
int i, hi, mc;
if (action == null)
throw new NullPointerException();
HashMap<K,V> m = map;
! Object[] tab = m.table;
if ((hi = fence) < 0) {
mc = expectedModCount = m.modCount;
hi = fence = tab.length;
}
else
mc = expectedModCount;
+
+ if (!acceptedNull) {
+ acceptedNull = true;
+ if (m.nullKeyEntry != null) {
+ action.accept(m.nullKeyEntry);
+ }
+ }
if (tab.length >= hi && (i = index) >= 0 && i < (index = hi)) {
! Object p = current;
do {
! if (p == null) {
p = tab[i++];
! if (p instanceof HashMap.TreeBin) {
! p = ((HashMap.TreeBin)p).first;
! }
! } else {
! HashMap.Entry<K,V> entry;
! if (p instanceof HashMap.Entry) {
! entry = (HashMap.Entry<K,V>)p;
! } else {
! entry = (HashMap.Entry<K,V>)((TreeNode)p).entry;
! }
! action.accept(entry);
! p = entry.next;
!
}
} while (p != null || i < hi);
if (m.modCount != mc)
throw new ConcurrentModificationException();
}
*** 1658,1675 ****
@SuppressWarnings("unchecked")
public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
int hi;
if (action == null)
throw new NullPointerException();
! HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])map.table;
! if (tab.length >= (hi = getFence()) && index >= 0) {
while (current != null || index < hi) {
! if (current == null)
current = tab[index++];
! else {
! HashMap.Entry<K,V> e = current;
! current = current.next;
action.accept(e);
if (map.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
--- 2956,2992 ----
@SuppressWarnings("unchecked")
public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
int hi;
if (action == null)
throw new NullPointerException();
! Object[] tab = map.table;
! hi = getFence();
!
! if (!acceptedNull) {
! acceptedNull = true;
! if (map.nullKeyEntry != null) {
! action.accept(map.nullKeyEntry);
! if (map.modCount != expectedModCount)
! throw new ConcurrentModificationException();
! return true;
! }
! }
! if (tab.length >= hi && index >= 0) {
while (current != null || index < hi) {
! if (current == null) {
current = tab[index++];
! if (current instanceof HashMap.TreeBin) {
! current = ((HashMap.TreeBin)current).first;
! }
! } else {
! HashMap.Entry<K,V> e;
! if (current instanceof HashMap.Entry) {
! e = (Entry<K,V>)current;
! } else {
! e = (Entry<K,V>)((TreeNode)current).entry;
! }
! current = e.next;
action.accept(e);
if (map.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}