8005698: Handle Frequent HashMap Collisions with Balanced Trees
Summary: HashMap bins with many collisions store entries in balanced trees
Reviewed-by: alanb, dl, mduigou
--- 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();
--- a/jdk/src/share/classes/java/util/Hashtable.java Tue Jun 04 09:45:14 2013 +0200
+++ b/jdk/src/share/classes/java/util/Hashtable.java Tue Jun 04 10:04:28 2013 +0100
@@ -180,13 +180,27 @@
*/
static final long HASHSEED_OFFSET;
+ static final boolean USE_HASHSEED;
+
static {
- try {
- UNSAFE = sun.misc.Unsafe.getUnsafe();
- HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
- Hashtable.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(
+ Hashtable.class.getDeclaredField("hashSeed"));
+ } catch (NoSuchFieldException | SecurityException e) {
+ throw new InternalError("Failed to record hashSeed offset", e);
+ }
+ } else {
+ UNSAFE = null;
+ HASHSEED_OFFSET = 0;
}
}
}
@@ -194,21 +208,24 @@
/**
* 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;
+
+ /**
+ * 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;
+ }
private 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).
- h ^= (h >>> 20) ^ (h >>> 12);
- return h ^ (h >>> 7) ^ (h >>> 4);
+ return hashSeed ^ k.hashCode();
}
/**
@@ -232,6 +249,7 @@
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
+ hashSeed = initHashSeed();
}
/**
@@ -1187,8 +1205,10 @@
s.defaultReadObject();
// set hashMask
- 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));
+ }
// Read the original length of the array and number of elements
int origlength = s.readInt();
--- a/jdk/src/share/classes/java/util/LinkedHashMap.java Tue Jun 04 09:45:14 2013 +0200
+++ b/jdk/src/share/classes/java/util/LinkedHashMap.java Tue Jun 04 10:04:28 2013 +0100
@@ -55,9 +55,9 @@
* order they were presented.)
*
* <p>A special {@link #LinkedHashMap(int,float,boolean) constructor} is
- * provided to create a linked hash map whose order of iteration is the order
- * in which its entries were last accessed, from least-recently accessed to
- * most-recently (<i>access-order</i>). This kind of map is well-suited to
+ * provided to create a <tt>LinkedHashMap</tt> whose order of iteration is the
+ * order in which its entries were last accessed, from least-recently accessed
+ * to most-recently (<i>access-order</i>). This kind of map is well-suited to
* building LRU caches. Invoking the <tt>put</tt> or <tt>get</tt> method
* results in an access to the corresponding entry (assuming it exists after
* the invocation completes). The <tt>putAll</tt> method generates one entry
@@ -243,23 +243,6 @@
}
/**
- * Transfers all entries to new table array. This method is called
- * by superclass resize. It is overridden for performance, as it is
- * faster to iterate using our linked list.
- */
- @Override
- @SuppressWarnings("unchecked")
- void transfer(HashMap.Entry[] newTable) {
- int newCapacity = newTable.length;
- for (Entry<K,V> e = header.after; e != header; e = e.after) {
- int index = indexFor(e.hash, newCapacity);
- e.next = (HashMap.Entry<K,V>)newTable[index];
- newTable[index] = e;
- }
- }
-
-
- /**
* Returns <tt>true</tt> if this map maps one or more keys to the
* specified value.
*
@@ -320,7 +303,7 @@
// These fields comprise the doubly linked list used for iteration.
Entry<K,V> before, after;
- Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
+ Entry(int hash, K key, V value, Object next) {
super(hash, key, value, next);
}
@@ -344,7 +327,7 @@
/**
* This method is invoked by the superclass whenever the value
- * of a pre-existing entry is read by Map.get or modified by Map.set.
+ * of a pre-existing entry is read by Map.get or modified by Map.put.
* If the enclosing Map is access-ordered, it moves the entry
* to the end of the list; otherwise, it does nothing.
*/
@@ -422,8 +405,9 @@
* allocated entry to get inserted at the end of the linked list and
* removes the eldest entry if appropriate.
*/
- void addEntry(int hash, K key, V value, int bucketIndex) {
- super.addEntry(hash, key, value, bucketIndex);
+ @Override
+ void addEntry(int hash, K key, V value, int bucketIndex, boolean checkIfNeedTree) {
+ super.addEntry(hash, key, value, bucketIndex, checkIfNeedTree);
// Remove eldest entry if instructed
Entry<K,V> eldest = header.after;
@@ -432,17 +416,14 @@
}
}
- /**
- * This override differs from addEntry in that it doesn't resize the
- * table or remove the eldest entry.
+ /*
+ * Create a new LinkedHashMap.Entry and setup the before/after pointers
*/
- void createEntry(int hash, K key, V value, int bucketIndex) {
- @SuppressWarnings("unchecked")
- HashMap.Entry<K,V> old = (HashMap.Entry<K,V>)table[bucketIndex];
- Entry<K,V> e = new Entry<>(hash, key, value, old);
- table[bucketIndex] = e;
- e.addBefore(header);
- size++;
+ @Override
+ HashMap.Entry<K,V> newEntry(int hash, K key, V value, Object next) {
+ Entry<K,V> newEntry = new Entry<>(hash, key, value, next);
+ newEntry.addBefore(header);
+ return newEntry;
}
/**
--- a/jdk/src/share/classes/java/util/WeakHashMap.java Tue Jun 04 09:45:14 2013 +0200
+++ b/jdk/src/share/classes/java/util/WeakHashMap.java Tue Jun 04 10:04:28 2013 +0100
@@ -187,11 +187,37 @@
*/
int modCount;
+ private static class Holder {
+ 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;
+ }
+ }
+
/**
* 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 int hashSeed;
+
+ /**
+ * Initialize the hashing mask value.
+ */
+ final void initHashSeed() {
+ if (sun.misc.VM.isBooted() && Holder.USE_HASHSEED) {
+ // Do not set hashSeed more than once!
+ // assert hashSeed == 0;
+ hashSeed = sun.misc.Hashing.randomHashSeed(this);
+ }
+ }
@SuppressWarnings("unchecked")
private Entry<K,V>[] newTable(int n) {
@@ -223,6 +249,7 @@
table = newTable(capacity);
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
+ initHashSeed();
}
/**
@@ -298,10 +325,7 @@
* in lower bits.
*/
final int hash(Object k) {
- if (k instanceof String) {
- return ((String) k).hash32();
- }
- int h = hashSeed ^ k.hashCode();
+ int h = hashSeed ^ k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
--- a/jdk/src/share/classes/sun/misc/Hashing.java Tue Jun 04 09:45:14 2013 +0200
+++ b/jdk/src/share/classes/sun/misc/Hashing.java Tue Jun 04 10:04:28 2013 +0100
@@ -24,7 +24,7 @@
*/
package sun.misc;
-import java.util.Random;
+import java.util.concurrent.ThreadLocalRandom;
/**
* Hashing utilities.
@@ -207,28 +207,16 @@
}
/**
- * Holds references to things that can't be initialized until after VM
- * is fully booted.
+ * Return a non-zero 32-bit pseudo random value. The {@code instance} object
+ * may be used as part of the value.
+ *
+ * @param instance an object to use if desired in choosing value.
+ * @return a non-zero 32-bit pseudo random value.
*/
- private static class Holder {
-
- /**
- * Used for generating per-instance hash seeds.
- *
- * We try to improve upon the default seeding.
- */
- static final Random SEED_MAKER = new Random(
- Double.doubleToRawLongBits(Math.random())
- ^ System.identityHashCode(Hashing.class)
- ^ System.currentTimeMillis()
- ^ System.nanoTime()
- ^ Runtime.getRuntime().freeMemory());
- }
-
public static int randomHashSeed(Object instance) {
int seed;
if (sun.misc.VM.isBooted()) {
- seed = Holder.SEED_MAKER.nextInt();
+ seed = ThreadLocalRandom.current().nextInt();
} else {
// lower quality "random" seed value--still better than zero and not
// not practically reversible.
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/Map/CheckRandomHashSeed.java Tue Jun 04 10:04:28 2013 +0100
@@ -0,0 +1,93 @@
+/*
+ * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/**
+ * @test
+ * @bug 8005698
+ * @summary Check operation of jdk.map.useRandomSeed property
+ * @run main CheckRandomHashSeed
+ * @run main/othervm -Djdk.map.useRandomSeed=false CheckRandomHashSeed
+ * @run main/othervm -Djdk.map.useRandomSeed=bogus CheckRandomHashSeed
+ * @run main/othervm -Djdk.map.useRandomSeed=true CheckRandomHashSeed true
+ * @author Brent Christian
+ */
+import java.lang.reflect.Field;
+import java.util.Map;
+import java.util.HashMap;
+import java.util.LinkedHashMap;
+import java.util.Hashtable;
+import java.util.WeakHashMap;
+
+public class CheckRandomHashSeed {
+ private final static String PROP_NAME = "jdk.map.useRandomSeed";
+ static boolean expectRandom = false;
+
+ public static void main(String[] args) {
+ if (args.length > 0 && args[0].equals("true")) {
+ expectRandom = true;
+ }
+ String hashSeedProp = System.getProperty(PROP_NAME);
+ boolean propSet = (null != hashSeedProp)
+ ? Boolean.parseBoolean(hashSeedProp) : false;
+ if (expectRandom != propSet) {
+ throw new Error("Error in test setup: " + (expectRandom ? "" : "not " ) + "expecting random hashSeed, but " + PROP_NAME + " is " + (propSet ? "" : "not ") + "enabled");
+ }
+
+ testMap(new HashMap());
+ testMap(new LinkedHashMap());
+ testMap(new WeakHashMap());
+ testMap(new Hashtable());
+ }
+
+ private static void testMap(Map map) {
+ int hashSeed = getHashSeed(map);
+ boolean hashSeedIsZero = (hashSeed == 0);
+
+ if (expectRandom != hashSeedIsZero) {
+ System.out.println("Test passed for " + map.getClass().getSimpleName() + " - expectRandom: " + expectRandom + ", hashSeed: " + hashSeed);
+ } else {
+ throw new Error ("Test FAILED for " + map.getClass().getSimpleName() + " - expectRandom: " + expectRandom + ", hashSeed: " + hashSeed);
+ }
+ }
+
+ private static int getHashSeed(Map map) {
+ try {
+ if (map instanceof HashMap || map instanceof LinkedHashMap) {
+ map.put("Key", "Value");
+ Field hashSeedField = HashMap.class.getDeclaredField("hashSeed");
+ hashSeedField.setAccessible(true);
+ int hashSeed = hashSeedField.getInt(map);
+ return hashSeed;
+ } else {
+ map.put("Key", "Value");
+ Field hashSeedField = map.getClass().getDeclaredField("hashSeed");
+ hashSeedField.setAccessible(true);
+ int hashSeed = hashSeedField.getInt(map);
+ return hashSeed;
+ }
+ } catch(Exception e) {
+ e.printStackTrace();
+ throw new Error(e);
+ }
+ }
+}
--- a/jdk/test/java/util/Map/Collisions.java Tue Jun 04 09:45:14 2013 +0200
+++ b/jdk/test/java/util/Map/Collisions.java Tue Jun 04 10:04:28 2013 +0100
@@ -26,6 +26,7 @@
* @bug 7126277
* @run main Collisions -shortrun
* @run main/othervm -Djdk.map.althashing.threshold=0 Collisions -shortrun
+ * @run main/othervm -Djdk.map.useRandomSeed=true Collisions -shortrun
* @summary Ensure Maps behave well with lots of hashCode() collisions.
* @author Mike Duigou
*/
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/Map/InPlaceOpsCollisions.java Tue Jun 04 10:04:28 2013 +0100
@@ -0,0 +1,665 @@
+/*
+ * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * @test
+ * @bug 8005698
+ * @run main InPlaceOpsCollisions -shortrun
+ * @run main/othervm -Djdk.map.randomseed=true InPlaceOpsCollisions -shortrun
+ * @summary Ensure overrides of in-place operations in Maps behave well with lots of collisions.
+ * @author Brent Christian
+ */
+import java.util.*;
+import java.util.function.*;
+
+public class InPlaceOpsCollisions {
+
+ /**
+ * Number of elements per map.
+ */
+ private static final int TEST_SIZE = 5000;
+
+ final static class HashableInteger implements Comparable<HashableInteger> {
+
+ final int value;
+ final int hashmask; //yes duplication
+
+ HashableInteger(int value, int hashmask) {
+ this.value = value;
+ this.hashmask = hashmask;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (obj instanceof HashableInteger) {
+ HashableInteger other = (HashableInteger) obj;
+
+ return other.value == value;
+ }
+
+ return false;
+ }
+
+ @Override
+ public int hashCode() {
+ return value % hashmask;
+ }
+
+ @Override
+ public int compareTo(HashableInteger o) {
+ return value - o.value;
+ }
+
+ @Override
+ public String toString() {
+ return Integer.toString(value);
+ }
+ }
+
+ static HashableInteger EXTRA_INT_VAL;
+ static String EXTRA_STRING_VAL;
+
+ private static Object[][] makeTestData(int size) {
+ HashableInteger UNIQUE_OBJECTS[] = new HashableInteger[size];
+ HashableInteger COLLIDING_OBJECTS[] = new HashableInteger[size];
+ String UNIQUE_STRINGS[] = new String[size];
+ String COLLIDING_STRINGS[] = new String[size];
+
+ for (int i = 0; i < size; i++) {
+ UNIQUE_OBJECTS[i] = new HashableInteger(i, Integer.MAX_VALUE);
+ COLLIDING_OBJECTS[i] = new HashableInteger(i, 10);
+ UNIQUE_STRINGS[i] = unhash(i);
+ COLLIDING_STRINGS[i] = (0 == i % 2)
+ ? UNIQUE_STRINGS[i / 2]
+ : "\u0000\u0000\u0000\u0000\u0000" + COLLIDING_STRINGS[i - 1];
+ }
+ EXTRA_INT_VAL = new HashableInteger(size, Integer.MAX_VALUE);
+ EXTRA_STRING_VAL = new String ("Extra Value");
+
+ return new Object[][] {
+ new Object[]{"Unique Objects", UNIQUE_OBJECTS},
+ new Object[]{"Colliding Objects", COLLIDING_OBJECTS},
+ new Object[]{"Unique Strings", UNIQUE_STRINGS},
+ new Object[]{"Colliding Strings", COLLIDING_STRINGS}
+ };
+ }
+
+ /**
+ * Returns a string with a hash equal to the argument.
+ *
+ * @return string with a hash equal to the argument.
+ */
+ public static String unhash(int target) {
+ StringBuilder answer = new StringBuilder();
+ if (target < 0) {
+ // String with hash of Integer.MIN_VALUE, 0x80000000
+ answer.append("\\u0915\\u0009\\u001e\\u000c\\u0002");
+
+ if (target == Integer.MIN_VALUE) {
+ return answer.toString();
+ }
+ // Find target without sign bit set
+ target = target & Integer.MAX_VALUE;
+ }
+
+ unhash0(answer, target);
+ return answer.toString();
+ }
+
+ private static void unhash0(StringBuilder partial, int target) {
+ int div = target / 31;
+ int rem = target % 31;
+
+ if (div <= Character.MAX_VALUE) {
+ if (div != 0) {
+ partial.append((char) div);
+ }
+ partial.append((char) rem);
+ } else {
+ unhash0(partial, div);
+ partial.append((char) rem);
+ }
+ }
+
+ private static void realMain(String[] args) throws Throwable {
+ boolean shortRun = args.length > 0 && args[0].equals("-shortrun");
+
+ Object[][] mapKeys = makeTestData(shortRun ? (TEST_SIZE / 2) : TEST_SIZE);
+
+ // loop through data sets
+ for (Object[] keys_desc : mapKeys) {
+ Map<Object, Object>[] maps = (Map<Object, Object>[]) new Map[]{
+ new HashMap<>(),
+ new LinkedHashMap<>(),
+ };
+
+ // for each map type.
+ for (Map<Object, Object> map : maps) {
+ String desc = (String) keys_desc[0];
+ Object[] keys = (Object[]) keys_desc[1];
+ try {
+ testInPlaceOps(map, desc, keys);
+ } catch(Exception all) {
+ unexpected("Failed for " + map.getClass().getName() + " with " + desc, all);
+ }
+ }
+ }
+ }
+
+ private static <T> void testInsertion(Map<T, T> map, String keys_desc, T[] keys) {
+ check("map empty", (map.size() == 0) && map.isEmpty());
+
+ for (int i = 0; i < keys.length; i++) {
+ check(String.format("insertion: map expected size m%d != i%d", map.size(), i),
+ map.size() == i);
+ check(String.format("insertion: put(%s[%d])", keys_desc, i), null == map.put(keys[i], keys[i]));
+ check(String.format("insertion: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
+ check(String.format("insertion: containsValue(%s[%d])", keys_desc, i), map.containsValue(keys[i]));
+ }
+
+ check(String.format("map expected size m%d != k%d", map.size(), keys.length),
+ map.size() == keys.length);
+ }
+
+
+ private static <T> void testInPlaceOps(Map<T, T> map, String keys_desc, T[] keys) {
+ System.out.println(map.getClass() + " : " + keys_desc + ", testInPlaceOps");
+ System.out.flush();
+
+ testInsertion(map, keys_desc, keys);
+ testPutIfAbsent(map, keys_desc, keys);
+
+ map.clear();
+ testInsertion(map, keys_desc, keys);
+ testRemoveMapping(map, keys_desc, keys);
+
+ map.clear();
+ testInsertion(map, keys_desc, keys);
+ testReplaceOldValue(map, keys_desc, keys);
+
+ map.clear();
+ testInsertion(map, keys_desc, keys);
+ testReplaceIfMapped(map, keys_desc, keys);
+
+ map.clear();
+ testInsertion(map, keys_desc, keys);
+ testComputeIfAbsent(map, keys_desc, keys, (k) -> getExtraVal(keys[0]));
+
+ map.clear();
+ testInsertion(map, keys_desc, keys);
+ testComputeIfAbsent(map, keys_desc, keys, (k) -> null);
+
+ map.clear();
+ testInsertion(map, keys_desc, keys);
+ testComputeIfPresent(map, keys_desc, keys, (k, v) -> getExtraVal(keys[0]));
+
+ map.clear();
+ testInsertion(map, keys_desc, keys);
+ testComputeIfPresent(map, keys_desc, keys, (k, v) -> null);
+
+ if (!keys_desc.contains("Strings")) { // avoid parseInt() number format error
+ map.clear();
+ testInsertion(map, keys_desc, keys);
+ testComputeNonNull(map, keys_desc, keys);
+ }
+
+ map.clear();
+ testInsertion(map, keys_desc, keys);
+ testComputeNull(map, keys_desc, keys);
+
+ if (!keys_desc.contains("Strings")) { // avoid parseInt() number format error
+ map.clear();
+ testInsertion(map, keys_desc, keys);
+ testMergeNonNull(map, keys_desc, keys);
+ }
+
+ map.clear();
+ testInsertion(map, keys_desc, keys);
+ testMergeNull(map, keys_desc, keys);
+ }
+
+
+
+ private static <T> void testPutIfAbsent(Map<T, T> map, String keys_desc, T[] keys) {
+ T extraVal = getExtraVal(keys[0]);
+ T retVal;
+ removeOddKeys(map, keys);
+ for (int i = 0; i < keys.length; i++) {
+ retVal = map.putIfAbsent(keys[i], extraVal);
+ if (i % 2 == 0) { // even: not absent, not put
+ check(String.format("putIfAbsent: (%s[%d]) retVal", keys_desc, i), retVal == keys[i]);
+ check(String.format("putIfAbsent: get(%s[%d])", keys_desc, i), keys[i] == map.get(keys[i]));
+ check(String.format("putIfAbsent: containsValue(%s[%d])", keys_desc, i), map.containsValue(keys[i]));
+ } else { // odd: absent, was put
+ check(String.format("putIfAbsent: (%s[%d]) retVal", keys_desc, i), retVal == null);
+ check(String.format("putIfAbsent: get(%s[%d])", keys_desc, i), extraVal == map.get(keys[i]));
+ check(String.format("putIfAbsent: !containsValue(%s[%d])", keys_desc, i), !map.containsValue(keys[i]));
+ }
+ check(String.format("insertion: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
+ }
+ check(String.format("map expected size m%d != k%d", map.size(), keys.length),
+ map.size() == keys.length);
+ }
+
+ private static <T> void testRemoveMapping(Map<T, T> map, String keys_desc, T[] keys) {
+ T extraVal = getExtraVal(keys[0]);
+ boolean removed;
+ int removes = 0;
+ remapOddKeys(map, keys);
+ for (int i = 0; i < keys.length; i++) {
+ removed = map.remove(keys[i], keys[i]);
+ if (i % 2 == 0) { // even: original mapping, should be removed
+ check(String.format("removeMapping: retVal(%s[%d])", keys_desc, i), removed);
+ check(String.format("removeMapping: get(%s[%d])", keys_desc, i), null == map.get(keys[i]));
+ check(String.format("removeMapping: !containsKey(%s[%d])", keys_desc, i), !map.containsKey(keys[i]));
+ check(String.format("removeMapping: !containsValue(%s[%d])", keys_desc, i), !map.containsValue(keys[i]));
+ removes++;
+ } else { // odd: new mapping, not removed
+ check(String.format("removeMapping: retVal(%s[%d])", keys_desc, i), !removed);
+ check(String.format("removeMapping: get(%s[%d])", keys_desc, i), extraVal == map.get(keys[i]));
+ check(String.format("removeMapping: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
+ check(String.format("removeMapping: containsValue(%s[%d])", keys_desc, i), map.containsValue(extraVal));
+ }
+ }
+ check(String.format("map expected size m%d != k%d", map.size(), keys.length - removes),
+ map.size() == keys.length - removes);
+ }
+
+ private static <T> void testReplaceOldValue(Map<T, T> map, String keys_desc, T[] keys) {
+ // remap odds to extraVal
+ // call replace to replace for extraVal, for all keys
+ // check that all keys map to value from keys array
+ T extraVal = getExtraVal(keys[0]);
+ boolean replaced;
+ remapOddKeys(map, keys);
+
+ for (int i = 0; i < keys.length; i++) {
+ replaced = map.replace(keys[i], extraVal, keys[i]);
+ if (i % 2 == 0) { // even: original mapping, should not be replaced
+ check(String.format("replaceOldValue: retVal(%s[%d])", keys_desc, i), !replaced);
+ } else { // odd: new mapping, should be replaced
+ check(String.format("replaceOldValue: get(%s[%d])", keys_desc, i), replaced);
+ }
+ check(String.format("replaceOldValue: get(%s[%d])", keys_desc, i), keys[i] == map.get(keys[i]));
+ check(String.format("replaceOldValue: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
+ check(String.format("replaceOldValue: containsValue(%s[%d])", keys_desc, i), map.containsValue(keys[i]));
+// removes++;
+ }
+ check(String.format("replaceOldValue: !containsValue(%s[%s])", keys_desc, extraVal.toString()), !map.containsValue(extraVal));
+ check(String.format("map expected size m%d != k%d", map.size(), keys.length),
+ map.size() == keys.length);
+ }
+
+ // TODO: Test case for key mapped to null value
+ private static <T> void testReplaceIfMapped(Map<T, T> map, String keys_desc, T[] keys) {
+ // remove odd keys
+ // call replace for all keys[]
+ // odd keys should remain absent, even keys should be mapped to EXTRA, no value from keys[] should be in map
+ T extraVal = getExtraVal(keys[0]);
+ int expectedSize1 = 0;
+ removeOddKeys(map, keys);
+ int expectedSize2 = map.size();
+
+ for (int i = 0; i < keys.length; i++) {
+ T retVal = map.replace(keys[i], extraVal);
+ if (i % 2 == 0) { // even: still in map, should be replaced
+ check(String.format("replaceIfMapped: retVal(%s[%d])", keys_desc, i), retVal == keys[i]);
+ check(String.format("replaceIfMapped: get(%s[%d])", keys_desc, i), extraVal == map.get(keys[i]));
+ check(String.format("replaceIfMapped: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
+ expectedSize1++;
+ } else { // odd: was removed, should not be replaced
+ check(String.format("replaceIfMapped: retVal(%s[%d])", keys_desc, i), retVal == null);
+ check(String.format("replaceIfMapped: get(%s[%d])", keys_desc, i), null == map.get(keys[i]));
+ check(String.format("replaceIfMapped: containsKey(%s[%d])", keys_desc, i), !map.containsKey(keys[i]));
+ }
+ check(String.format("replaceIfMapped: !containsValue(%s[%d])", keys_desc, i), !map.containsValue(keys[i]));
+ }
+ check(String.format("replaceIfMapped: containsValue(%s[%s])", keys_desc, extraVal.toString()), map.containsValue(extraVal));
+ check(String.format("map expected size#1 m%d != k%d", map.size(), expectedSize1),
+ map.size() == expectedSize1);
+ check(String.format("map expected size#2 m%d != k%d", map.size(), expectedSize2),
+ map.size() == expectedSize2);
+
+ }
+
+ private static <T> void testComputeIfAbsent(Map<T, T> map, String keys_desc, T[] keys,
+ Function<T,T> mappingFunction) {
+ // remove a third of the keys
+ // call computeIfAbsent for all keys, func returns EXTRA
+ // check that removed keys now -> EXTRA, other keys -> original val
+ T expectedVal = mappingFunction.apply(keys[0]);
+ T retVal;
+ int expectedSize = 0;
+ removeThirdKeys(map, keys);
+ for (int i = 0; i < keys.length; i++) {
+ retVal = map.computeIfAbsent(keys[i], mappingFunction);
+ if (i % 3 != 2) { // key present, not computed
+ check(String.format("computeIfAbsent: (%s[%d]) retVal", keys_desc, i), retVal == keys[i]);
+ check(String.format("computeIfAbsent: get(%s[%d])", keys_desc, i), keys[i] == map.get(keys[i]));
+ check(String.format("computeIfAbsent: containsValue(%s[%d])", keys_desc, i), map.containsValue(keys[i]));
+ check(String.format("insertion: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
+ expectedSize++;
+ } else { // key absent, computed unless function return null
+ check(String.format("computeIfAbsent: (%s[%d]) retVal", keys_desc, i), retVal == expectedVal);
+ check(String.format("computeIfAbsent: get(%s[%d])", keys_desc, i), expectedVal == map.get(keys[i]));
+ check(String.format("computeIfAbsent: !containsValue(%s[%d])", keys_desc, i), !map.containsValue(keys[i]));
+ // mapping should not be added if function returns null
+ check(String.format("insertion: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]) != (expectedVal == null));
+ if (expectedVal != null) { expectedSize++; }
+ }
+ }
+ if (expectedVal != null) {
+ check(String.format("computeIfAbsent: containsValue(%s[%s])", keys_desc, expectedVal), map.containsValue(expectedVal));
+ }
+ check(String.format("map expected size m%d != k%d", map.size(), expectedSize),
+ map.size() == expectedSize);
+ }
+
+ private static <T> void testComputeIfPresent(Map<T, T> map, String keys_desc, T[] keys,
+ BiFunction<T,T,T> mappingFunction) {
+ // remove a third of the keys
+ // call testComputeIfPresent for all keys[]
+ // removed keys should remain absent, even keys should be mapped to $RESULT
+ // no value from keys[] should be in map
+ T funcResult = mappingFunction.apply(keys[0], keys[0]);
+ int expectedSize1 = 0;
+ removeThirdKeys(map, keys);
+
+ for (int i = 0; i < keys.length; i++) {
+ T retVal = map.computeIfPresent(keys[i], mappingFunction);
+ if (i % 3 != 2) { // key present
+ if (funcResult == null) { // was removed
+ check(String.format("replaceIfMapped: containsKey(%s[%d])", keys_desc, i), !map.containsKey(keys[i]));
+ } else { // value was replaced
+ check(String.format("replaceIfMapped: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
+ expectedSize1++;
+ }
+ check(String.format("computeIfPresent: retVal(%s[%s])", keys_desc, i), retVal == funcResult);
+ check(String.format("replaceIfMapped: get(%s[%d])", keys_desc, i), funcResult == map.get(keys[i]));
+
+ } else { // odd: was removed, should not be replaced
+ check(String.format("replaceIfMapped: retVal(%s[%d])", keys_desc, i), retVal == null);
+ check(String.format("replaceIfMapped: get(%s[%d])", keys_desc, i), null == map.get(keys[i]));
+ check(String.format("replaceIfMapped: containsKey(%s[%d])", keys_desc, i), !map.containsKey(keys[i]));
+ }
+ check(String.format("replaceIfMapped: !containsValue(%s[%d])", keys_desc, i), !map.containsValue(keys[i]));
+ }
+ check(String.format("map expected size#1 m%d != k%d", map.size(), expectedSize1),
+ map.size() == expectedSize1);
+ }
+
+ private static <T> void testComputeNonNull(Map<T, T> map, String keys_desc, T[] keys) {
+ // remove a third of the keys
+ // call compute() for all keys[]
+ // all keys should be present: removed keys -> EXTRA, others to k-1
+ BiFunction<T,T,T> mappingFunction = (k, v) -> {
+ if (v == null) {
+ return getExtraVal(keys[0]);
+ } else {
+ return keys[Integer.parseInt(k.toString()) - 1];
+ }
+ };
+ T extraVal = getExtraVal(keys[0]);
+ removeThirdKeys(map, keys);
+ for (int i = 1; i < keys.length; i++) {
+ T retVal = map.compute(keys[i], mappingFunction);
+ if (i % 3 != 2) { // key present, should be mapped to k-1
+ check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == keys[i-1]);
+ check(String.format("compute: get(%s[%d])", keys_desc, i), keys[i-1] == map.get(keys[i]));
+ } else { // odd: was removed, should be replaced with EXTRA
+ check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == extraVal);
+ check(String.format("compute: get(%s[%d])", keys_desc, i), extraVal == map.get(keys[i]));
+ }
+ check(String.format("compute: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
+ }
+ check(String.format("map expected size#1 m%d != k%d", map.size(), keys.length),
+ map.size() == keys.length);
+ check(String.format("compute: containsValue(%s[%s])", keys_desc, extraVal.toString()), map.containsValue(extraVal));
+ check(String.format("compute: !containsValue(%s,[null])", keys_desc), !map.containsValue(null));
+ }
+
+ private static <T> void testComputeNull(Map<T, T> map, String keys_desc, T[] keys) {
+ // remove a third of the keys
+ // call compute() for all keys[]
+ // removed keys should -> EXTRA
+ // for other keys: func returns null, should have no mapping
+ BiFunction<T,T,T> mappingFunction = (k, v) -> {
+ // if absent/null -> EXTRA
+ // if present -> null
+ if (v == null) {
+ return getExtraVal(keys[0]);
+ } else {
+ return null;
+ }
+ };
+ T extraVal = getExtraVal(keys[0]);
+ int expectedSize = 0;
+ removeThirdKeys(map, keys);
+ for (int i = 0; i < keys.length; i++) {
+ T retVal = map.compute(keys[i], mappingFunction);
+ if (i % 3 != 2) { // key present, func returned null, should be absent from map
+ check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == null);
+ check(String.format("compute: get(%s[%d])", keys_desc, i), null == map.get(keys[i]));
+ check(String.format("compute: containsKey(%s[%d])", keys_desc, i), !map.containsKey(keys[i]));
+ check(String.format("compute: containsValue(%s[%s])", keys_desc, i), !map.containsValue(keys[i]));
+ } else { // odd: was removed, should now be mapped to EXTRA
+ check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == extraVal);
+ check(String.format("compute: get(%s[%d])", keys_desc, i), extraVal == map.get(keys[i]));
+ check(String.format("compute: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
+ expectedSize++;
+ }
+ }
+ check(String.format("compute: containsValue(%s[%s])", keys_desc, extraVal.toString()), map.containsValue(extraVal));
+ check(String.format("map expected size#1 m%d != k%d", map.size(), expectedSize),
+ map.size() == expectedSize);
+ }
+
+ private static <T> void testMergeNonNull(Map<T, T> map, String keys_desc, T[] keys) {
+ // remove a third of the keys
+ // call merge() for all keys[]
+ // all keys should be present: removed keys now -> EXTRA, other keys -> k-1
+
+ // Map to preceding key
+ BiFunction<T,T,T> mappingFunction = (k, v) -> keys[Integer.parseInt(k.toString()) - 1];
+ T extraVal = getExtraVal(keys[0]);
+ removeThirdKeys(map, keys);
+ for (int i = 1; i < keys.length; i++) {
+ T retVal = map.merge(keys[i], extraVal, mappingFunction);
+ if (i % 3 != 2) { // key present, should be mapped to k-1
+ check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == keys[i-1]);
+ check(String.format("compute: get(%s[%d])", keys_desc, i), keys[i-1] == map.get(keys[i]));
+ } else { // odd: was removed, should be replaced with EXTRA
+ check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == extraVal);
+ check(String.format("compute: get(%s[%d])", keys_desc, i), extraVal == map.get(keys[i]));
+ }
+ check(String.format("compute: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
+ }
+
+ check(String.format("map expected size#1 m%d != k%d", map.size(), keys.length),
+ map.size() == keys.length);
+ check(String.format("compute: containsValue(%s[%s])", keys_desc, extraVal.toString()), map.containsValue(extraVal));
+ check(String.format("compute: !containsValue(%s,[null])", keys_desc), !map.containsValue(null));
+
+ }
+
+ private static <T> void testMergeNull(Map<T, T> map, String keys_desc, T[] keys) {
+ // remove a third of the keys
+ // call merge() for all keys[]
+ // result: removed keys -> EXTRA, other keys absent
+
+ BiFunction<T,T,T> mappingFunction = (k, v) -> null;
+ T extraVal = getExtraVal(keys[0]);
+ int expectedSize = 0;
+ removeThirdKeys(map, keys);
+ for (int i = 0; i < keys.length; i++) {
+ T retVal = map.merge(keys[i], extraVal, mappingFunction);
+ if (i % 3 != 2) { // key present, func returned null, should be absent from map
+ check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == null);
+ check(String.format("compute: get(%s[%d])", keys_desc, i), null == map.get(keys[i]));
+ check(String.format("compute: containsKey(%s[%d])", keys_desc, i), !map.containsKey(keys[i]));
+ } else { // odd: was removed, should now be mapped to EXTRA
+ check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == extraVal);
+ check(String.format("compute: get(%s[%d])", keys_desc, i), extraVal == map.get(keys[i]));
+ check(String.format("compute: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
+ expectedSize++;
+ }
+ check(String.format("compute: containsValue(%s[%s])", keys_desc, i), !map.containsValue(keys[i]));
+ }
+ check(String.format("compute: containsValue(%s[%s])", keys_desc, extraVal.toString()), map.containsValue(extraVal));
+ check(String.format("map expected size#1 m%d != k%d", map.size(), expectedSize),
+ map.size() == expectedSize);
+ }
+
+ /*
+ * Return the EXTRA val for the key type being used
+ */
+ private static <T> T getExtraVal(T key) {
+ if (key instanceof HashableInteger) {
+ return (T)EXTRA_INT_VAL;
+ } else {
+ return (T)EXTRA_STRING_VAL;
+ }
+ }
+
+ /*
+ * Remove half of the keys
+ */
+ private static <T> void removeOddKeys(Map<T, T> map, /*String keys_desc, */ T[] keys) {
+ int removes = 0;
+ for (int i = 0; i < keys.length; i++) {
+ if (i % 2 != 0) {
+ map.remove(keys[i]);
+ removes++;
+ }
+ }
+ check(String.format("map expected size m%d != k%d", map.size(), keys.length - removes),
+ map.size() == keys.length - removes);
+ }
+
+ /*
+ * Remove every third key
+ * This will hopefully leave some removed keys in TreeBins for, e.g., computeIfAbsent
+ * w/ a func that returns null.
+ *
+ * TODO: consider using this in other tests (and maybe adding a remapThirdKeys)
+ */
+ private static <T> void removeThirdKeys(Map<T, T> map, /*String keys_desc, */ T[] keys) {
+ int removes = 0;
+ for (int i = 0; i < keys.length; i++) {
+ if (i % 3 == 2) {
+ map.remove(keys[i]);
+ removes++;
+ }
+ }
+ check(String.format("map expected size m%d != k%d", map.size(), keys.length - removes),
+ map.size() == keys.length - removes);
+ }
+
+ /*
+ * Re-map the odd-numbered keys to map to the EXTRA value
+ */
+ private static <T> void remapOddKeys(Map<T, T> map, /*String keys_desc, */ T[] keys) {
+ T extraVal = getExtraVal(keys[0]);
+ for (int i = 0; i < keys.length; i++) {
+ if (i % 2 != 0) {
+ map.put(keys[i], extraVal);
+ }
+ }
+ }
+
+ //--------------------- Infrastructure ---------------------------
+ static volatile int passed = 0, failed = 0;
+
+ static void pass() {
+ passed++;
+ }
+
+ static void fail() {
+ failed++;
+ (new Error("Failure")).printStackTrace(System.err);
+ }
+
+ static void fail(String msg) {
+ failed++;
+ (new Error("Failure: " + msg)).printStackTrace(System.err);
+ }
+
+ static void abort() {
+ fail();
+ System.exit(1);
+ }
+
+ static void abort(String msg) {
+ fail(msg);
+ System.exit(1);
+ }
+
+ static void unexpected(String msg, Throwable t) {
+ System.err.println("Unexpected: " + msg);
+ unexpected(t);
+ }
+
+ static void unexpected(Throwable t) {
+ failed++;
+ t.printStackTrace(System.err);
+ }
+
+ static void check(boolean cond) {
+ if (cond) {
+ pass();
+ } else {
+ fail();
+ }
+ }
+
+ static void check(String desc, boolean cond) {
+ if (cond) {
+ pass();
+ } else {
+ fail(desc);
+ }
+ }
+
+ static void equal(Object x, Object y) {
+ if (Objects.equals(x, y)) {
+ pass();
+ } else {
+ fail(x + " not equal to " + y);
+ }
+ }
+
+ public static void main(String[] args) throws Throwable {
+ Thread.currentThread().setName(Collisions.class.getName());
+// Thread.currentThread().setPriority(Thread.MAX_PRIORITY);
+ try {
+ realMain(args);
+ } catch (Throwable t) {
+ unexpected(t);
+ }
+
+ System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
+ if (failed > 0) {
+ throw new Error("Some tests failed");
+ }
+ }
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/Map/TreeBinSplitBackToEntries.java Tue Jun 04 10:04:28 2013 +0100
@@ -0,0 +1,255 @@
+/*
+ * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+import java.util.*;
+import java.lang.reflect.Field;
+
+/*
+ * @test
+ * @bug 8005698
+ * @summary Test the case where TreeBin.splitTreeBin() converts a bin back to an Entry list
+ * @run main TreeBinSplitBackToEntries unused
+ * @author Brent Christian
+ */
+
+public class TreeBinSplitBackToEntries {
+ private static int EXPECTED_TREE_THRESHOLD = 16;
+
+ // Easiest if this covers one bit higher then 'bit' in splitTreeBin() on the
+ // call where the TreeBin is converted back to an Entry list
+ private static int HASHMASK = 0x7F;
+ private static boolean verbose = false;
+ private static boolean fastFail = false;
+ private static boolean failed = false;
+
+ static void printlnIfVerbose(String msg) {
+ if (verbose) {System.out.println(msg); }
+ }
+
+ public static void main(String[] args) {
+ for (String arg : args) {
+ switch(arg) {
+ case "-verbose":
+ verbose = true;
+ break;
+ case "-fastfail":
+ fastFail = true;
+ break;
+ }
+ }
+ checkTreeThreshold();
+ testMapHiTree();
+ testMapLoTree();
+ if (failed) {
+ System.out.println("Test Failed");
+ System.exit(1);
+ } else {
+ System.out.println("Test Passed");
+ }
+ }
+
+ public static void checkTreeThreshold() {
+ int threshold = -1;
+ try {
+ Class treeBinClass = Class.forName("java.util.HashMap$TreeBin");
+ Field treeThreshold = treeBinClass.getDeclaredField("TREE_THRESHOLD");
+ treeThreshold.setAccessible(true);
+ threshold = treeThreshold.getInt(treeBinClass);
+ } catch (ClassNotFoundException|NoSuchFieldException|IllegalAccessException e) {
+ e.printStackTrace();
+ throw new Error("Problem accessing TreeBin.TREE_THRESHOLD", e);
+ }
+ check("Expected TREE_THRESHOLD: " + EXPECTED_TREE_THRESHOLD +", found: " + threshold,
+ threshold == EXPECTED_TREE_THRESHOLD);
+ printlnIfVerbose("TREE_THRESHOLD: " + threshold);
+ }
+
+ public static void testMapHiTree() {
+ Object[][] mapKeys = makeHiTreeTestData();
+ testMapsForKeys(mapKeys, "hiTree");
+ }
+
+ public static void testMapLoTree() {
+ Object[][] mapKeys = makeLoTreeTestData();
+
+ testMapsForKeys(mapKeys, "loTree");
+ }
+
+ public static void testMapsForKeys(Object[][] mapKeys, String desc) {
+ // loop through data sets
+ for (Object[] keys_desc : mapKeys) {
+ Map<Object, Object>[] maps = (Map<Object, Object>[]) new Map[]{
+ new HashMap<>(4, 0.8f),
+ new LinkedHashMap<>(4, 0.8f),
+ };
+ // for each map type.
+ for (Map<Object, Object> map : maps) {
+ Object[] keys = (Object[]) keys_desc[1];
+ System.out.println(desc + ": testPutThenGet() for " + map.getClass());
+ testPutThenGet(map, keys);
+ }
+ }
+ }
+
+ private static <T> void testPutThenGet(Map<T, T> map, T[] keys) {
+ for (T key : keys) {
+ printlnIfVerbose("put()ing 0x" + Integer.toHexString(Integer.parseInt(key.toString())) + ", hashCode=" + Integer.toHexString(key.hashCode()));
+ map.put(key, key);
+ }
+ for (T key : keys) {
+ check("key: 0x" + Integer.toHexString(Integer.parseInt(key.toString())) + " not found in resulting " + map.getClass().getSimpleName(), map.get(key) != null);
+ }
+ }
+
+ /* Data to force a non-empty loTree in TreeBin.splitTreeBin() to be converted back
+ * into an Entry list
+ */
+ private static Object[][] makeLoTreeTestData() {
+ HashableInteger COLLIDING_OBJECTS[] = new HashableInteger[] {
+ new HashableInteger( 0x23, HASHMASK),
+ new HashableInteger( 0x123, HASHMASK),
+ new HashableInteger( 0x323, HASHMASK),
+ new HashableInteger( 0x523, HASHMASK),
+
+ new HashableInteger( 0x723, HASHMASK),
+ new HashableInteger( 0x923, HASHMASK),
+ new HashableInteger( 0xB23, HASHMASK),
+ new HashableInteger( 0xD23, HASHMASK),
+
+ new HashableInteger( 0xF23, HASHMASK),
+ new HashableInteger( 0xF123, HASHMASK),
+ new HashableInteger( 0x1023, HASHMASK),
+ new HashableInteger( 0x1123, HASHMASK),
+
+ new HashableInteger( 0x1323, HASHMASK),
+ new HashableInteger( 0x1523, HASHMASK),
+ new HashableInteger( 0x1723, HASHMASK),
+ new HashableInteger( 0x1923, HASHMASK),
+
+ new HashableInteger( 0x1B23, HASHMASK),
+ new HashableInteger( 0x1D23, HASHMASK),
+ new HashableInteger( 0x3123, HASHMASK),
+ new HashableInteger( 0x3323, HASHMASK),
+ new HashableInteger( 0x3523, HASHMASK),
+
+ new HashableInteger( 0x3723, HASHMASK),
+ new HashableInteger( 0x1001, HASHMASK),
+ new HashableInteger( 0x4001, HASHMASK),
+ new HashableInteger( 0x1, HASHMASK),
+ };
+ return new Object[][] {
+ new Object[]{"Colliding Objects", COLLIDING_OBJECTS},
+ };
+ }
+
+ /* Data to force the hiTree in TreeBin.splitTreeBin() to be converted back
+ * into an Entry list
+ */
+ private static Object[][] makeHiTreeTestData() {
+ HashableInteger COLLIDING_OBJECTS[] = new HashableInteger[] {
+ new HashableInteger( 0x1, HASHMASK),
+ new HashableInteger( 0x101, HASHMASK),
+ new HashableInteger( 0x301, HASHMASK),
+ new HashableInteger( 0x501, HASHMASK),
+ new HashableInteger( 0x701, HASHMASK),
+
+ new HashableInteger( 0x1001, HASHMASK),
+ new HashableInteger( 0x1101, HASHMASK),
+ new HashableInteger( 0x1301, HASHMASK),
+
+ new HashableInteger( 0x1501, HASHMASK),
+ new HashableInteger( 0x1701, HASHMASK),
+ new HashableInteger( 0x4001, HASHMASK),
+ new HashableInteger( 0x4101, HASHMASK),
+ new HashableInteger( 0x4301, HASHMASK),
+
+ new HashableInteger( 0x4501, HASHMASK),
+ new HashableInteger( 0x4701, HASHMASK),
+ new HashableInteger( 0x8001, HASHMASK),
+ new HashableInteger( 0x8101, HASHMASK),
+
+
+ new HashableInteger( 0x8301, HASHMASK),
+ new HashableInteger( 0x8501, HASHMASK),
+ new HashableInteger( 0x8701, HASHMASK),
+ new HashableInteger( 0x9001, HASHMASK),
+
+ new HashableInteger( 0x23, HASHMASK),
+ new HashableInteger( 0x123, HASHMASK),
+ new HashableInteger( 0x323, HASHMASK),
+ new HashableInteger( 0x523, HASHMASK),
+ };
+ return new Object[][] {
+ new Object[]{"Colliding Objects", COLLIDING_OBJECTS},
+ };
+ }
+
+ static void check(String desc, boolean cond) {
+ if (!cond) {
+ fail(desc);
+ }
+ }
+
+ static void fail(String msg) {
+ failed = true;
+ (new Error("Failure: " + msg)).printStackTrace(System.err);
+ if (fastFail) {
+ System.exit(1);
+ }
+ }
+
+ final static class HashableInteger implements Comparable<HashableInteger> {
+ final int value;
+ final int hashmask; //yes duplication
+
+ HashableInteger(int value, int hashmask) {
+ this.value = value;
+ this.hashmask = hashmask;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (obj instanceof HashableInteger) {
+ HashableInteger other = (HashableInteger) obj;
+ return other.value == value;
+ }
+ return false;
+ }
+
+ @Override
+ public int hashCode() {
+ // This version ANDs the mask
+ return value & hashmask;
+ }
+
+ @Override
+ public int compareTo(HashableInteger o) {
+ return value - o.value;
+ }
+
+ @Override
+ public String toString() {
+ return Integer.toString(value);
+ }
+ }
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/Spliterator/SpliteratorCollisions.java Tue Jun 04 10:04:28 2013 +0100
@@ -0,0 +1,707 @@
+/*
+ * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/**
+ * @test
+ * @bug 8005698
+ * @run testng SpliteratorCollisions
+ * @summary Spliterator traversing and splitting hash maps containing colliding hashes
+ * @author Brent Christian
+ */
+
+import org.testng.annotations.DataProvider;
+import org.testng.annotations.Test;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Deque;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Spliterator;
+import java.util.TreeSet;
+import java.util.function.Consumer;
+import java.util.function.Function;
+import java.util.function.LongConsumer;
+import java.util.function.Supplier;
+import java.util.function.UnaryOperator;
+
+import static org.testng.Assert.*;
+import static org.testng.Assert.assertEquals;
+
+@Test
+public class SpliteratorCollisions {
+
+ private static List<Integer> SIZES = Arrays.asList(0, 1, 10, 100, 1000);
+
+ private static class SpliteratorDataBuilder<T> {
+ List<Object[]> data;
+ List<T> exp;
+ Map<T, T> mExp;
+
+ SpliteratorDataBuilder(List<Object[]> data, List<T> exp) {
+ this.data = data;
+ this.exp = exp;
+ this.mExp = createMap(exp);
+ }
+
+ Map<T, T> createMap(List<T> l) {
+ Map<T, T> m = new LinkedHashMap<>();
+ for (T t : l) {
+ m.put(t, t);
+ }
+ return m;
+ }
+
+ void add(String description, Collection<?> expected, Supplier<Spliterator<?>> s) {
+ description = joiner(description).toString();
+ data.add(new Object[]{description, expected, s});
+ }
+
+ void add(String description, Supplier<Spliterator<?>> s) {
+ add(description, exp, s);
+ }
+
+ void addCollection(Function<Collection<T>, ? extends Collection<T>> c) {
+ add("new " + c.apply(Collections.<T>emptyList()).getClass().getName() + ".spliterator()",
+ () -> c.apply(exp).spliterator());
+ }
+
+ void addList(Function<Collection<T>, ? extends List<T>> l) {
+ // @@@ If collection is instance of List then add sub-list tests
+ addCollection(l);
+ }
+
+ void addMap(Function<Map<T, T>, ? extends Map<T, T>> m) {
+ String description = "new " + m.apply(Collections.<T, T>emptyMap()).getClass().getName();
+ add(description + ".keySet().spliterator()", () -> m.apply(mExp).keySet().spliterator());
+ add(description + ".values().spliterator()", () -> m.apply(mExp).values().spliterator());
+ add(description + ".entrySet().spliterator()", mExp.entrySet(), () -> m.apply(mExp).entrySet().spliterator());
+ }
+
+ StringBuilder joiner(String description) {
+ return new StringBuilder(description).
+ append(" {").
+ append("size=").append(exp.size()).
+ append("}");
+ }
+ }
+
+ static Object[][] spliteratorDataProvider;
+
+ @DataProvider(name = "HashableIntSpliterator")
+ public static Object[][] spliteratorDataProvider() {
+ if (spliteratorDataProvider != null) {
+ return spliteratorDataProvider;
+ }
+
+ List<Object[]> data = new ArrayList<>();
+ for (int size : SIZES) {
+ List<HashableInteger> exp = listIntRange(size, false);
+ SpliteratorDataBuilder<HashableInteger> db = new SpliteratorDataBuilder<>(data, exp);
+
+ // Maps
+ db.addMap(HashMap::new);
+ db.addMap(LinkedHashMap::new);
+
+ // Collections that use HashMap
+ db.addCollection(HashSet::new);
+ db.addCollection(LinkedHashSet::new);
+ db.addCollection(TreeSet::new);
+ }
+ return spliteratorDataProvider = data.toArray(new Object[0][]);
+ }
+
+ static Object[][] spliteratorDataProviderWithNull;
+
+ @DataProvider(name = "HashableIntSpliteratorWithNull")
+ public static Object[][] spliteratorNullDataProvider() {
+ if (spliteratorDataProviderWithNull != null) {
+ return spliteratorDataProviderWithNull;
+ }
+
+ List<Object[]> data = new ArrayList<>();
+ for (int size : SIZES) {
+ List<HashableInteger> exp = listIntRange(size, true);
+ exp.add(0, null);
+ SpliteratorDataBuilder<HashableInteger> db = new SpliteratorDataBuilder<>(data, exp);
+
+ // Maps
+ db.addMap(HashMap::new);
+ db.addMap(LinkedHashMap::new);
+ // TODO: add this back in if we decide to keep TreeBin in WeakHashMap
+ //db.addMap(WeakHashMap::new);
+
+ // Collections that use HashMap
+ db.addCollection(HashSet::new);
+ db.addCollection(LinkedHashSet::new);
+// db.addCollection(TreeSet::new);
+
+ }
+ return spliteratorDataProviderWithNull = data.toArray(new Object[0][]);
+ }
+
+ final static class HashableInteger implements Comparable<HashableInteger> {
+
+ final int value;
+ final int hashmask; //yes duplication
+
+ HashableInteger(int value, int hashmask) {
+ this.value = value;
+ this.hashmask = hashmask;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (obj instanceof HashableInteger) {
+ HashableInteger other = (HashableInteger) obj;
+
+ return other.value == value;
+ }
+
+ return false;
+ }
+
+ @Override
+ public int hashCode() {
+ return value % hashmask;
+ }
+
+ @Override
+ public int compareTo(HashableInteger o) {
+ return value - o.value;
+ }
+
+ @Override
+ public String toString() {
+ return Integer.toString(value);
+ }
+ }
+
+ private static List<HashableInteger> listIntRange(int upTo, boolean withNull) {
+ List<HashableInteger> exp = new ArrayList<>();
+ if (withNull) {
+ exp.add(null);
+ }
+ for (int i = 0; i < upTo; i++) {
+ exp.add(new HashableInteger(i, 10));
+ }
+ return Collections.unmodifiableList(exp);
+ }
+
+ @Test(dataProvider = "HashableIntSpliterator")
+ @SuppressWarnings({"unchecked", "rawtypes"})
+ public void testNullPointerException(String description, Collection exp, Supplier<Spliterator> s) {
+ executeAndCatch(NullPointerException.class, () -> s.get().forEachRemaining(null));
+ executeAndCatch(NullPointerException.class, () -> s.get().tryAdvance(null));
+ }
+
+ @Test(dataProvider = "HashableIntSpliteratorWithNull")
+ @SuppressWarnings({"unchecked", "rawtypes"})
+ public void testNullPointerExceptionWithNull(String description, Collection exp, Supplier<Spliterator> s) {
+ executeAndCatch(NullPointerException.class, () -> s.get().forEachRemaining(null));
+ executeAndCatch(NullPointerException.class, () -> s.get().tryAdvance(null));
+ }
+
+
+ @Test(dataProvider = "HashableIntSpliterator")
+ @SuppressWarnings({"unchecked", "rawtypes"})
+ public void testForEach(String description, Collection exp, Supplier<Spliterator> s) {
+ testForEach(exp, s, (Consumer<Object> b) -> b);
+ }
+
+ @Test(dataProvider = "HashableIntSpliteratorWithNull")
+ @SuppressWarnings({"unchecked", "rawtypes"})
+ public void testForEachWithNull(String description, Collection exp, Supplier<Spliterator> s) {
+ testForEach(exp, s, (Consumer<Object> b) -> b);
+ }
+
+
+ @Test(dataProvider = "HashableIntSpliterator")
+ @SuppressWarnings({"unchecked", "rawtypes"})
+ public void testTryAdvance(String description, Collection exp, Supplier<Spliterator> s) {
+ testTryAdvance(exp, s, (Consumer<Object> b) -> b);
+ }
+
+ @Test(dataProvider = "HashableIntSpliteratorWithNull")
+ @SuppressWarnings({"unchecked", "rawtypes"})
+ public void testTryAdvanceWithNull(String description, Collection exp, Supplier<Spliterator> s) {
+ testTryAdvance(exp, s, (Consumer<Object> b) -> b);
+ }
+
+/* skip this test until 8013649 is fixed
+ @Test(dataProvider = "HashableIntSpliterator")
+ @SuppressWarnings({"unchecked", "rawtypes"})
+ public void testMixedTryAdvanceForEach(String description, Collection exp, Supplier<Spliterator> s) {
+ testMixedTryAdvanceForEach(exp, s, (Consumer<Object> b) -> b);
+ }
+
+ @Test(dataProvider = "HashableIntSpliteratorWithNull")
+ @SuppressWarnings({"unchecked", "rawtypes"})
+ public void testMixedTryAdvanceForEachWithNull(String description, Collection exp, Supplier<Spliterator> s) {
+ testMixedTryAdvanceForEach(exp, s, (Consumer<Object> b) -> b);
+ }
+*/
+
+ @Test(dataProvider = "HashableIntSpliterator")
+ @SuppressWarnings({"unchecked", "rawtypes"})
+ public void testSplitAfterFullTraversal(String description, Collection exp, Supplier<Spliterator> s) {
+ testSplitAfterFullTraversal(s, (Consumer<Object> b) -> b);
+ }
+
+ @Test(dataProvider = "HashableIntSpliteratorWithNull")
+ @SuppressWarnings({"unchecked", "rawtypes"})
+ public void testSplitAfterFullTraversalWithNull(String description, Collection exp, Supplier<Spliterator> s) {
+ testSplitAfterFullTraversal(s, (Consumer<Object> b) -> b);
+ }
+
+
+ @Test(dataProvider = "HashableIntSpliterator")
+ @SuppressWarnings({"unchecked", "rawtypes"})
+ public void testSplitOnce(String description, Collection exp, Supplier<Spliterator> s) {
+ testSplitOnce(exp, s, (Consumer<Object> b) -> b);
+ }
+
+ @Test(dataProvider = "HashableIntSpliteratorWithNull")
+ @SuppressWarnings({"unchecked", "rawtypes"})
+ public void testSplitOnceWithNull(String description, Collection exp, Supplier<Spliterator> s) {
+ testSplitOnce(exp, s, (Consumer<Object> b) -> b);
+ }
+
+ @Test(dataProvider = "HashableIntSpliterator")
+ @SuppressWarnings({"unchecked", "rawtypes"})
+ public void testSplitSixDeep(String description, Collection exp, Supplier<Spliterator> s) {
+ testSplitSixDeep(exp, s, (Consumer<Object> b) -> b);
+ }
+
+ @Test(dataProvider = "HashableIntSpliteratorWithNull")
+ @SuppressWarnings({"unchecked", "rawtypes"})
+ public void testSplitSixDeepWithNull(String description, Collection exp, Supplier<Spliterator> s) {
+ testSplitSixDeep(exp, s, (Consumer<Object> b) -> b);
+ }
+
+ @Test(dataProvider = "HashableIntSpliterator")
+ @SuppressWarnings({"unchecked", "rawtypes"})
+ public void testSplitUntilNull(String description, Collection exp, Supplier<Spliterator> s) {
+ testSplitUntilNull(exp, s, (Consumer<Object> b) -> b);
+ }
+
+ @Test(dataProvider = "HashableIntSpliteratorWithNull")
+ @SuppressWarnings({"unchecked", "rawtypes"})
+ public void testSplitUntilNullWithNull(String description, Collection exp, Supplier<Spliterator> s) {
+ testSplitUntilNull(exp, s, (Consumer<Object> b) -> b);
+ }
+
+ private static <T, S extends Spliterator<T>> void testForEach(
+ Collection<T> exp,
+ Supplier<S> supplier,
+ UnaryOperator<Consumer<T>> boxingAdapter) {
+ S spliterator = supplier.get();
+ long sizeIfKnown = spliterator.getExactSizeIfKnown();
+ boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED);
+
+ ArrayList<T> fromForEach = new ArrayList<>();
+ spliterator = supplier.get();
+ Consumer<T> addToFromForEach = boxingAdapter.apply(fromForEach::add);
+ spliterator.forEachRemaining(addToFromForEach);
+
+ // Assert that forEach now produces no elements
+ spliterator.forEachRemaining(boxingAdapter.apply(e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e)));
+ // Assert that tryAdvance now produce no elements
+ spliterator.tryAdvance(boxingAdapter.apply(e -> fail("Spliterator.tryAdvance produced an element after spliterator exhausted: " + e)));
+
+ // assert that size, tryAdvance, and forEach are consistent
+ if (sizeIfKnown >= 0) {
+ assertEquals(sizeIfKnown, exp.size());
+ }
+ if (exp.contains(null)) {
+ assertTrue(fromForEach.contains(null));
+ }
+ assertEquals(fromForEach.size(), exp.size());
+
+ assertContents(fromForEach, exp, isOrdered);
+ }
+
+ private static <T, S extends Spliterator<T>> void testTryAdvance(
+ Collection<T> exp,
+ Supplier<S> supplier,
+ UnaryOperator<Consumer<T>> boxingAdapter) {
+ S spliterator = supplier.get();
+ long sizeIfKnown = spliterator.getExactSizeIfKnown();
+ boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED);
+
+ spliterator = supplier.get();
+ ArrayList<T> fromTryAdvance = new ArrayList<>();
+ Consumer<T> addToFromTryAdvance = boxingAdapter.apply(fromTryAdvance::add);
+ while (spliterator.tryAdvance(addToFromTryAdvance)) { }
+
+ // Assert that forEach now produces no elements
+ spliterator.forEachRemaining(boxingAdapter.apply(e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e)));
+ // Assert that tryAdvance now produce no elements
+ spliterator.tryAdvance(boxingAdapter.apply(e -> fail("Spliterator.tryAdvance produced an element after spliterator exhausted: " + e)));
+
+ // assert that size, tryAdvance, and forEach are consistent
+ if (sizeIfKnown >= 0) {
+ assertEquals(sizeIfKnown, exp.size());
+ }
+ assertEquals(fromTryAdvance.size(), exp.size());
+
+ assertContents(fromTryAdvance, exp, isOrdered);
+ }
+
+ private static <T, S extends Spliterator<T>> void testMixedTryAdvanceForEach(
+ Collection<T> exp,
+ Supplier<S> supplier,
+ UnaryOperator<Consumer<T>> boxingAdapter) {
+ S spliterator = supplier.get();
+ long sizeIfKnown = spliterator.getExactSizeIfKnown();
+ boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED);
+
+ // tryAdvance first few elements, then forEach rest
+ ArrayList<T> dest = new ArrayList<>();
+ spliterator = supplier.get();
+ Consumer<T> addToDest = boxingAdapter.apply(dest::add);
+ for (int i = 0; i < 10 && spliterator.tryAdvance(addToDest); i++) { }
+ spliterator.forEachRemaining(addToDest);
+
+ // Assert that forEach now produces no elements
+ spliterator.forEachRemaining(boxingAdapter.apply(e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e)));
+ // Assert that tryAdvance now produce no elements
+ spliterator.tryAdvance(boxingAdapter.apply(e -> fail("Spliterator.tryAdvance produced an element after spliterator exhausted: " + e)));
+
+ if (sizeIfKnown >= 0) {
+ assertEquals(sizeIfKnown, dest.size());
+ }
+ assertEquals(dest.size(), exp.size());
+
+ if (isOrdered) {
+ assertEquals(dest, exp);
+ }
+ else {
+ assertContentsUnordered(dest, exp);
+ }
+ }
+
+ private static <T, S extends Spliterator<T>> void testSplitAfterFullTraversal(
+ Supplier<S> supplier,
+ UnaryOperator<Consumer<T>> boxingAdapter) {
+ // Full traversal using tryAdvance
+ Spliterator<T> spliterator = supplier.get();
+ while (spliterator.tryAdvance(boxingAdapter.apply(e -> { }))) { }
+ Spliterator<T> split = spliterator.trySplit();
+ assertNull(split);
+
+ // Full traversal using forEach
+ spliterator = supplier.get();
+ spliterator.forEachRemaining(boxingAdapter.apply(e -> {
+ }));
+ split = spliterator.trySplit();
+ assertNull(split);
+
+ // Full traversal using tryAdvance then forEach
+ spliterator = supplier.get();
+ spliterator.tryAdvance(boxingAdapter.apply(e -> { }));
+ spliterator.forEachRemaining(boxingAdapter.apply(e -> {
+ }));
+ split = spliterator.trySplit();
+ assertNull(split);
+ }
+
+ private static <T, S extends Spliterator<T>> void testSplitOnce(
+ Collection<T> exp,
+ Supplier<S> supplier,
+ UnaryOperator<Consumer<T>> boxingAdapter) {
+ S spliterator = supplier.get();
+ long sizeIfKnown = spliterator.getExactSizeIfKnown();
+ boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED);
+
+ ArrayList<T> fromSplit = new ArrayList<>();
+ Spliterator<T> s1 = supplier.get();
+ Spliterator<T> s2 = s1.trySplit();
+ long s1Size = s1.getExactSizeIfKnown();
+ long s2Size = (s2 != null) ? s2.getExactSizeIfKnown() : 0;
+
+ Consumer<T> addToFromSplit = boxingAdapter.apply(fromSplit::add);
+ if (s2 != null)
+ s2.forEachRemaining(addToFromSplit);
+ s1.forEachRemaining(addToFromSplit);
+
+ if (sizeIfKnown >= 0) {
+ assertEquals(sizeIfKnown, fromSplit.size());
+ if (s1Size >= 0 && s2Size >= 0)
+ assertEquals(sizeIfKnown, s1Size + s2Size);
+ }
+ assertContents(fromSplit, exp, isOrdered);
+ }
+
+ private static <T, S extends Spliterator<T>> void testSplitSixDeep(
+ Collection<T> exp,
+ Supplier<S> supplier,
+ UnaryOperator<Consumer<T>> boxingAdapter) {
+ S spliterator = supplier.get();
+ boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED);
+
+ for (int depth=0; depth < 6; depth++) {
+ List<T> dest = new ArrayList<>();
+ spliterator = supplier.get();
+
+ assertSpliterator(spliterator);
+
+ // verify splitting with forEach
+ visit(depth, 0, dest, spliterator, boxingAdapter, spliterator.characteristics(), false);
+ assertContents(dest, exp, isOrdered);
+
+ // verify splitting with tryAdvance
+ dest.clear();
+ spliterator = supplier.get();
+ visit(depth, 0, dest, spliterator, boxingAdapter, spliterator.characteristics(), true);
+ assertContents(dest, exp, isOrdered);
+ }
+ }
+
+ private static <T, S extends Spliterator<T>> void visit(int depth, int curLevel,
+ List<T> dest, S spliterator, UnaryOperator<Consumer<T>> boxingAdapter,
+ int rootCharacteristics, boolean useTryAdvance) {
+ if (curLevel < depth) {
+ long beforeSize = spliterator.getExactSizeIfKnown();
+ Spliterator<T> split = spliterator.trySplit();
+ if (split != null) {
+ assertSpliterator(split, rootCharacteristics);
+ assertSpliterator(spliterator, rootCharacteristics);
+
+ if ((rootCharacteristics & Spliterator.SUBSIZED) != 0 &&
+ (rootCharacteristics & Spliterator.SIZED) != 0) {
+ assertEquals(beforeSize, split.estimateSize() + spliterator.estimateSize());
+ }
+ visit(depth, curLevel + 1, dest, split, boxingAdapter, rootCharacteristics, useTryAdvance);
+ }
+ visit(depth, curLevel + 1, dest, spliterator, boxingAdapter, rootCharacteristics, useTryAdvance);
+ }
+ else {
+ long sizeIfKnown = spliterator.getExactSizeIfKnown();
+ if (useTryAdvance) {
+ Consumer<T> addToDest = boxingAdapter.apply(dest::add);
+ int count = 0;
+ while (spliterator.tryAdvance(addToDest)) {
+ ++count;
+ }
+
+ if (sizeIfKnown >= 0)
+ assertEquals(sizeIfKnown, count);
+
+ // Assert that forEach now produces no elements
+ spliterator.forEachRemaining(boxingAdapter.apply(e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e)));
+
+ Spliterator<T> split = spliterator.trySplit();
+ assertNull(split);
+ }
+ else {
+ List<T> leafDest = new ArrayList<>();
+ Consumer<T> addToLeafDest = boxingAdapter.apply(leafDest::add);
+ spliterator.forEachRemaining(addToLeafDest);
+
+ if (sizeIfKnown >= 0)
+ assertEquals(sizeIfKnown, leafDest.size());
+
+ // Assert that forEach now produces no elements
+ spliterator.tryAdvance(boxingAdapter.apply(e -> fail("Spliterator.tryAdvance produced an element after spliterator exhausted: " + e)));
+
+ Spliterator<T> split = spliterator.trySplit();
+ assertNull(split);
+
+ dest.addAll(leafDest);
+ }
+ }
+ }
+
+ private static <T, S extends Spliterator<T>> void testSplitUntilNull(
+ Collection<T> exp,
+ Supplier<S> supplier,
+ UnaryOperator<Consumer<T>> boxingAdapter) {
+ Spliterator<T> s = supplier.get();
+ boolean isOrdered = s.hasCharacteristics(Spliterator.ORDERED);
+ assertSpliterator(s);
+
+ List<T> splits = new ArrayList<>();
+ Consumer<T> c = boxingAdapter.apply(splits::add);
+
+ testSplitUntilNull(new SplitNode<T>(c, s));
+ assertContents(splits, exp, isOrdered);
+ }
+
+ private static class SplitNode<T> {
+ // Constant for every node
+ final Consumer<T> c;
+ final int rootCharacteristics;
+
+ final Spliterator<T> s;
+
+ SplitNode(Consumer<T> c, Spliterator<T> s) {
+ this(c, s.characteristics(), s);
+ }
+
+ private SplitNode(Consumer<T> c, int rootCharacteristics, Spliterator<T> s) {
+ this.c = c;
+ this.rootCharacteristics = rootCharacteristics;
+ this.s = s;
+ }
+
+ SplitNode<T> fromSplit(Spliterator<T> split) {
+ return new SplitNode<>(c, rootCharacteristics, split);
+ }
+ }
+
+ /**
+ * Set the maximum stack capacity to 0.25MB. This should be more than enough to detect a bad spliterator
+ * while not unduly disrupting test infrastructure given the test data sizes that are used are small.
+ * Note that j.u.c.ForkJoinPool sets the max queue size to 64M (1 << 26).
+ */
+ private static final int MAXIMUM_STACK_CAPACITY = 1 << 18; // 0.25MB
+
+ private static <T> void testSplitUntilNull(SplitNode<T> e) {
+ // Use an explicit stack to avoid a StackOverflowException when testing a Spliterator
+ // that when repeatedly split produces a right-balanced (and maybe degenerate) tree, or
+ // for a spliterator that is badly behaved.
+ Deque<SplitNode<T>> stack = new ArrayDeque<>();
+ stack.push(e);
+
+ int iteration = 0;
+ while (!stack.isEmpty()) {
+ assertTrue(iteration++ < MAXIMUM_STACK_CAPACITY, "Exceeded maximum stack modification count of 1 << 18");
+
+ e = stack.pop();
+ Spliterator<T> parentAndRightSplit = e.s;
+
+ long parentEstimateSize = parentAndRightSplit.estimateSize();
+ assertTrue(parentEstimateSize >= 0,
+ String.format("Split size estimate %d < 0", parentEstimateSize));
+
+ long parentSize = parentAndRightSplit.getExactSizeIfKnown();
+ Spliterator<T> leftSplit = parentAndRightSplit.trySplit();
+ if (leftSplit == null) {
+ parentAndRightSplit.forEachRemaining(e.c);
+ continue;
+ }
+
+ assertSpliterator(leftSplit, e.rootCharacteristics);
+ assertSpliterator(parentAndRightSplit, e.rootCharacteristics);
+
+ if (parentEstimateSize != Long.MAX_VALUE && leftSplit.estimateSize() > 0 && parentAndRightSplit.estimateSize() > 0) {
+ assertTrue(leftSplit.estimateSize() < parentEstimateSize,
+ String.format("Left split size estimate %d >= parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
+ assertTrue(parentAndRightSplit.estimateSize() < parentEstimateSize,
+ String.format("Right split size estimate %d >= parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
+ }
+ else {
+ assertTrue(leftSplit.estimateSize() <= parentEstimateSize,
+ String.format("Left split size estimate %d > parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
+ assertTrue(parentAndRightSplit.estimateSize() <= parentEstimateSize,
+ String.format("Right split size estimate %d > parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
+ }
+
+ long leftSize = leftSplit.getExactSizeIfKnown();
+ long rightSize = parentAndRightSplit.getExactSizeIfKnown();
+ if (parentSize >= 0 && leftSize >= 0 && rightSize >= 0)
+ assertEquals(parentSize, leftSize + rightSize,
+ String.format("exact left split size %d + exact right split size %d != parent exact split size %d",
+ leftSize, rightSize, parentSize));
+
+ // Add right side to stack first so left side is popped off first
+ stack.push(e.fromSplit(parentAndRightSplit));
+ stack.push(e.fromSplit(leftSplit));
+ }
+ }
+
+ private static void assertSpliterator(Spliterator<?> s, int rootCharacteristics) {
+ if ((rootCharacteristics & Spliterator.SUBSIZED) != 0) {
+ assertTrue(s.hasCharacteristics(Spliterator.SUBSIZED),
+ "Child split is not SUBSIZED when root split is SUBSIZED");
+ }
+ assertSpliterator(s);
+ }
+
+ private static void assertSpliterator(Spliterator<?> s) {
+ if (s.hasCharacteristics(Spliterator.SUBSIZED)) {
+ assertTrue(s.hasCharacteristics(Spliterator.SIZED));
+ }
+ if (s.hasCharacteristics(Spliterator.SIZED)) {
+ assertTrue(s.estimateSize() != Long.MAX_VALUE);
+ assertTrue(s.getExactSizeIfKnown() >= 0);
+ }
+ try {
+ s.getComparator();
+ assertTrue(s.hasCharacteristics(Spliterator.SORTED));
+ } catch (IllegalStateException e) {
+ assertFalse(s.hasCharacteristics(Spliterator.SORTED));
+ }
+ }
+
+ private static<T> void assertContents(Collection<T> actual, Collection<T> expected, boolean isOrdered) {
+ if (isOrdered) {
+ assertEquals(actual, expected);
+ }
+ else {
+ assertContentsUnordered(actual, expected);
+ }
+ }
+
+ private static<T> void assertContentsUnordered(Iterable<T> actual, Iterable<T> expected) {
+ assertEquals(toBoxedMultiset(actual), toBoxedMultiset(expected));
+ }
+
+ private static <T> Map<T, HashableInteger> toBoxedMultiset(Iterable<T> c) {
+ Map<T, HashableInteger> result = new HashMap<>();
+ c.forEach((Consumer) e -> {
+ if (result.containsKey((T)e)) {
+ result.put((T)e, new HashableInteger(((HashableInteger)result.get(e)).value + 1, 10));
+ } else {
+ result.put((T)e, new HashableInteger(1, 10));
+ }
+ });
+ return result;
+ }
+
+ private void executeAndCatch(Class<? extends Exception> expected, Runnable r) {
+ Exception caught = null;
+ try {
+ r.run();
+ }
+ catch (Exception e) {
+ caught = e;
+ }
+
+ assertNotNull(caught,
+ String.format("No Exception was thrown, expected an Exception of %s to be thrown",
+ expected.getName()));
+ assertTrue(expected.isInstance(caught),
+ String.format("Exception thrown %s not an instance of %s",
+ caught.getClass().getName(), expected.getName()));
+ }
+
+}