--- a/jdk/src/share/classes/java/util/HashMap.java Tue Jun 04 09:45:14 2013 +0200
+++ b/jdk/src/share/classes/java/util/HashMap.java Tue Jun 04 10:04:28 2013 +0100
@@ -26,6 +26,8 @@
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;
@@ -126,7 +128,7 @@
*/
public class HashMap<K,V>
- extends AbstractMap<K,V>
+ extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
@@ -150,12 +152,12 @@
/**
* An empty table instance to share when the table is not inflated.
*/
- static final Entry<?,?>[] EMPTY_TABLE = {};
+ static final Object[] EMPTY_TABLE = {};
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
- transient Entry<?,?>[] table = EMPTY_TABLE;
+ transient Object[] table = EMPTY_TABLE;
/**
* The number of key-value mappings contained in this map.
@@ -186,10 +188,10 @@
*/
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;
/**
@@ -198,22 +200,616 @@
*/
static final long HASHSEED_OFFSET;
+ static final boolean USE_HASHSEED;
+
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);
+ 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 = sun.misc.Hashing.randomHashSeed(this);
+ 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
@@ -233,9 +829,9 @@
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
-
this.loadFactor = loadFactor;
threshold = initialCapacity;
+ hashSeed = initHashSeed();
init();
}
@@ -269,10 +865,11 @@
*/
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
- DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
+ DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
+ // assert size == m.size();
}
private static int roundUpToPowerOf2(int number) {
@@ -294,7 +891,7 @@
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
- table = new Entry[capacity];
+ table = new Object[capacity];
}
// internal utilities
@@ -310,17 +907,24 @@
}
/**
+ * 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
+ * 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
@@ -409,19 +1013,35 @@
if (isEmpty()) {
return null;
}
+ if (key == null) {
+ return nullKeyEntry;
+ }
+ int hash = hash(key);
+ int bin = indexFor(hash, table.length);
- 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;
+ 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
@@ -434,28 +1054,57 @@
* (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)
+ 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;
+ 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);
+ addEntry(hash, key, value, i, checkIfNeedTree);
return null;
}
@@ -463,47 +1112,79 @@
* 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;
- }
+ if (nullKeyEntry != null) {
+ V oldValue = nullKeyEntry.value;
+ nullKeyEntry.value = value;
+ nullKeyEntry.recordAccess(this);
+ return oldValue;
}
modCount++;
- addEntry(0, null, value, 0);
+ 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. It calls createEntry rather than
- * addEntry.
+ * 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) {
- int hash = null == key ? 0 : hash(key);
+ 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.
*/
- 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;
+ 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);
+ createEntry(hash, key, value, i, checkIfNeedTree);
}
private void putAllForCreate(Map<? extends K, ? extends V> m) {
@@ -526,14 +1207,14 @@
* is irrelevant).
*/
void resize(int newCapacity) {
- Entry<?,?>[] oldTable = table;
+ Object[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
- Entry<?,?>[] newTable = new Entry<?,?>[newCapacity];
+ Object[] newTable = new Object[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
@@ -541,19 +1222,31 @@
/**
* Transfers all entries from current table to newTable.
+ *
+ * Assumes newTable is larger than table
*/
@SuppressWarnings("unchecked")
- void transfer(Entry<?,?>[] newTable) {
- Entry<?,?>[] src = table;
+ 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++ ) {
- 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;
+ 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);
@@ -585,20 +1278,13 @@
* 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);
+ 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());
- }
+ }
/**
* Removes the mapping for the specified key from this map if present.
@@ -621,24 +1307,57 @@
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);
+ 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);
+ addEntry(hash, key, value, i, checkIfNeedTree);
return null;
}
@@ -647,31 +1366,61 @@
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++;
- size--;
- if (prev == e)
- table[i] = next;
- else
- prev.next = next;
- e.recordRemoval(this);
+ if (key == null) {
+ if (nullKeyEntry != null &&
+ Objects.equals(nullKeyEntry.value, value)) {
+ removeNullKey();
return true;
}
- prev = e;
- e = next;
+ 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++;
+ size--;
+ if (prev == e)
+ table[i] = next;
+ else
+ prev.next = next;
+ e.recordRemoval(this);
+ 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;
}
@@ -680,39 +1429,82 @@
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);
+ 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
+ @Override
public V replace(K key, V value) {
if (isEmpty()) {
return null;
}
- int hash = (key == null) ? 0 : hash(key);
+ if (key == null) {
+ if (nullKeyEntry != null) {
+ return putForNullKey(value);
+ }
+ return null;
+ }
+ 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) {
- if (e.hash == hash && Objects.equals(e.key, key)) {
- V oldValue = e.value;
- e.value = value;
- e.recordAccess(this);
+ 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;
}
@@ -721,21 +1513,75 @@
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
- int hash = (key == null) ? 0 : hash(key);
+ 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);
- @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;
+ 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) {
+ if (newValue != null) { // add Entry and check for TreeBin conversion
modCount++;
- addEntry(hash, key, newValue, i);
+ addEntry(hash, key, newValue, i, checkIfNeedTree);
}
return newValue;
@@ -746,59 +1592,34 @@
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;
+ if (key == null) {
+ V oldValue;
+ if (nullKeyEntry != null && (oldValue = nullKeyEntry.value) != null) {
V newValue = remappingFunction.apply(key, oldValue);
- modCount++;
- if (newValue == null) {
- size--;
- if (prev == e)
- table[i] = next;
- else
- prev.next = next;
- e.recordRemoval(this);
+ if (newValue != null ) {
+ putForNullKey(newValue);
+ return newValue;
} else {
- e.value = newValue;
- e.recordAccess(this);
+ removeNullKey();
}
- 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);
+ return null;
}
- int hash = (key == null) ? 0 : hash(key);
+ int hash = 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 (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;
@@ -809,17 +1630,136 @@
e.value = newValue;
e.recordAccess(this);
}
+ return newValue;
}
- 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);
+ }
}
- prev = e;
- e = next;
+ 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;
+ e.recordRemoval(this);
+ } else {
+ e.value = newValue;
+ e.recordAccess(this);
+ }
+ }
+ 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);
+ addEntry(hash, key, newValue, i, checkIfNeedTree);
}
return newValue;
@@ -830,40 +1770,96 @@
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
- int hash = (key == null) ? 0 : hash(key);
+ 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);
- @SuppressWarnings("unchecked")
- Entry<K,V> prev = (Entry<K,V>)table[i];
- Entry<K,V> e = prev;
+ 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 = 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) {
+ 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;
+ e.recordRemoval(this);
+ } else {
+ e.value = newValue;
+ e.recordAccess(this);
+ }
+ 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--;
- if (prev == e)
- table[i] = next;
- else
- prev.next = next;
- e.recordRemoval(this);
- } else {
- e.value = newValue;
- e.recordAccess(this);
+ 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 newValue;
+ 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);
+ }
+ }
}
- prev = e;
- e = next;
+ return newValue;
}
-
if (value != null) {
modCount++;
- addEntry(hash, key, value, i);
+ addEntry(hash, key, value, i, checkIfNeedTree);
}
-
return value;
}
@@ -873,36 +1869,65 @@
* 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;
}
- int hash = (key == null) ? 0 : hash(key);
+ if (key == null) {
+ if (nullKeyEntry != null) {
+ return removeNullKey();
+ }
+ return null;
+ }
+ int hash = hash(key);
int i = indexFor(hash, table.length);
- @SuppressWarnings("unchecked")
+
+ if (table[i] instanceof Entry) {
+ @SuppressWarnings("unchecked")
Entry<K,V> prev = (Entry<K,V>)table[i];
- Entry<K,V> e = prev;
+ 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)))) {
+ 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
+ prev.next = next;
+ e.recordRemoval(this);
+ 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--;
- if (prev == e)
- table[i] = next;
- else
- prev.next = next;
- e.recordRemoval(this);
- return e;
+ 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;
}
- prev = e;
- e = next;
}
-
- return e;
+ return null;
}
/**
@@ -915,29 +1940,75 @@
Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
Object key = entry.getKey();
- int hash = (key == null) ? 0 : hash(key);
+
+ if (key == null) {
+ if (entry.equals(nullKeyEntry)) {
+ return removeNullKey();
+ }
+ return null;
+ }
+
+ int hash = hash(key);
int i = indexFor(hash, table.length);
- @SuppressWarnings("unchecked")
- Entry<K,V> prev = (Entry<K,V>)table[i];
- Entry<K,V> e = prev;
+
+ 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 = e.next;
- if (e.hash == hash && e.equals(entry)) {
+ 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;
+ else
+ prev.next = next;
+ e.recordRemoval(this);
+ 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--;
- if (prev == e)
- table[i] = next;
- else
- prev.next = next;
- e.recordRemoval(this);
- return e;
+ 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;
}
- prev = e;
- e = next;
}
+ return null;
+ }
- return e;
+ /*
+ * 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;
}
/**
@@ -946,6 +2017,9 @@
*/
public void clear() {
modCount++;
+ if (nullKeyEntry != null) {
+ nullKeyEntry = null;
+ }
Arrays.fill(table, null);
size = 0;
}
@@ -959,27 +2033,58 @@
* specified value
*/
public boolean containsValue(Object value) {
- if (value == null)
+ 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;
+ }
+ 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() {
- 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;
+ 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);
}
/**
@@ -1007,6 +2112,7 @@
result.entrySet = null;
result.modCount = 0;
result.size = 0;
+ result.nullKeyEntry = null;
result.init();
result.putAllForCreate(this);
@@ -1016,13 +2122,13 @@
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
- Entry<K,V> next;
+ Object next; // an Entry, or a TreeNode
final int hash;
/**
* Creates new entry.
*/
- Entry(int h, K k, V v, Entry<K,V> n) {
+ Entry(int h, K k, V v, Object n) {
value = v;
next = n;
key = k;
@@ -1054,7 +2160,7 @@
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
- }
+ }
return false;
}
@@ -1068,8 +2174,7 @@
/**
* 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.
+ * overwritten for a key that's already in the HashMap.
*/
void recordAccess(HashMap<K,V> m) {
}
@@ -1082,50 +2187,96 @@
}
}
+ 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.
+ * 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) {
+ 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 = (null != key) ? hash(key) : 0;
+ hash = hash(key);
bucketIndex = indexFor(hash, table.length);
}
-
- createEntry(hash, key, value, bucketIndex);
+ createEntry(hash, key, value, bucketIndex, checkIfNeedTree);
}
/**
- * Like addEntry except that this version is used when creating entries
+ * Called by addEntry(), and also used when creating entries
* as part of Map construction or "pseudo-construction" (cloning,
- * deserialization). This version needn't worry about resizing the table.
+ * deserialization). This version does not check for resizing of the table.
*
- * Subclass overrides this to alter the behavior of HashMap(Map),
- * clone, and readObject.
+ * 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) {
+ 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] = new Entry<>(hash, key, value, e);
+ 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> {
- Entry<?,?> next; // next entry to return
+ Object next; // next entry to return, an Entry or a TreeNode
int expectedModCount; // For fast-fail
int index; // current slot
- Entry<?,?> current; // current entry
+ Object current; // current entry, an Entry or a TreeNode
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
- Entry<?,?>[] t = table;
- while (index < t.length && (next = t[index++]) == null)
- ;
+ 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();
+ }
}
}
@@ -1135,19 +2286,28 @@
@SuppressWarnings("unchecked")
final Entry<K,V> nextEntry() {
- if (modCount != expectedModCount)
+ if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
- Entry<?,?> e = next;
+ }
+ Object e = next;
+ Entry<K,V> retVal;
+
if (e == null)
throw new NoSuchElementException();
- if ((next = e.next) == null) {
- Entry<?,?>[] t = table;
- while (index < t.length && (next = t[index++]) == null)
- ;
+ 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 (Entry<K,V>)e;
+ return retVal;
}
public void remove() {
@@ -1155,11 +2315,33 @@
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
- Object k = current.key;
+ 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> {
@@ -1357,7 +2539,7 @@
if (table==EMPTY_TABLE) {
s.writeInt(roundUpToPowerOf2(threshold));
} else {
- s.writeInt(table.length);
+ s.writeInt(table.length);
}
// Write out size (number of Mappings)
@@ -1389,8 +2571,10 @@
}
// set other fields that need values
- Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
- sun.misc.Hashing.randomHashSeed(this));
+ if (Holder.USE_HASHSEED) {
+ Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
+ sun.misc.Hashing.randomHashSeed(this));
+ }
table = EMPTY_TABLE;
// Read in number of buckets
@@ -1404,9 +2588,9 @@
// capacity chosen by number of mappings and desired load (if >= 0.25)
int capacity = (int) Math.min(
- mappings * Math.min(1 / loadFactor, 4.0f),
- // we have limits...
- HashMap.MAXIMUM_CAPACITY);
+ mappings * Math.min(1 / loadFactor, 4.0f),
+ // we have limits...
+ HashMap.MAXIMUM_CAPACITY);
// allocate the bucket array;
if (mappings > 0) {
@@ -1420,9 +2604,9 @@
// Read the keys and values, and put the mappings in the HashMap
for (int i=0; i<mappings; i++) {
@SuppressWarnings("unchecked")
- K key = (K) s.readObject();
+ K key = (K) s.readObject();
@SuppressWarnings("unchecked")
- V value = (V) s.readObject();
+ V value = (V) s.readObject();
putForCreate(key, value);
}
}
@@ -1436,11 +2620,17 @@
*/
static class HashMapSpliterator<K,V> {
final HashMap<K,V> map;
- HashMap.Entry<K,V> current; // current node
+ 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,
@@ -1450,6 +2640,7 @@
this.fence = fence;
this.est = est;
this.expectedModCount = expectedModCount;
+ this.acceptedNull = false;
}
final int getFence() { // initialize fence and size on first use
@@ -1479,9 +2670,15 @@
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);
+ 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")
@@ -1490,21 +2687,37 @@
if (action == null)
throw new NullPointerException();
HashMap<K,V> m = map;
- HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])m.table;
+ 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)) {
- HashMap.Entry<K,V> p = current;
+ Object p = current;
do {
- if (p == null)
+ if (p == null) {
p = tab[i++];
- else {
- action.accept(p.getKey());
- p = p.next;
+ 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)
@@ -1517,14 +2730,34 @@
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) {
+ 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)
+ if (current == null) {
current = tab[index++];
- else {
- K k = current.getKey();
- current = current.next;
+ 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();
@@ -1551,9 +2784,15 @@
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);
+ 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")
@@ -1562,21 +2801,37 @@
if (action == null)
throw new NullPointerException();
HashMap<K,V> m = map;
- HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])m.table;
+ 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)) {
- HashMap.Entry<K,V> p = current;
+ Object p = current;
do {
- if (p == null)
+ if (p == null) {
p = tab[i++];
- else {
- action.accept(p.getValue());
- p = p.next;
+ 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)
@@ -1589,14 +2844,34 @@
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) {
+ 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)
+ if (current == null) {
current = tab[index++];
- else {
- V v = current.getValue();
- current = current.next;
+ 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();
@@ -1622,9 +2897,15 @@
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);
+ 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")
@@ -1633,21 +2914,38 @@
if (action == null)
throw new NullPointerException();
HashMap<K,V> m = map;
- HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])m.table;
+ 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)) {
- HashMap.Entry<K,V> p = current;
+ Object p = current;
do {
- if (p == null)
+ if (p == null) {
p = tab[i++];
- else {
- action.accept(p);
- p = p.next;
+ 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)
@@ -1660,14 +2958,33 @@
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) {
+ 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)
+ if (current == null) {
current = tab[index++];
- else {
- HashMap.Entry<K,V> e = current;
- current = current.next;
+ 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();