Mercurial > hg > shenandoah-preopenjdk-archive > openjdk8 > jdk
changeset 7296:5223d3228658
8005698: Handle Frequent HashMap Collisions with Balanced Trees
Summary: HashMap bins with many collisions store entries in balanced trees
Reviewed-by: alanb, dl, mduigou
| author | bchristi |
|---|---|
| date | Tue, 04 Jun 2013 10:04:28 +0100 |
| parents | 25cf25fb8c68 |
| children | fad4ef2123ca |
| files | src/share/classes/java/util/HashMap.java src/share/classes/java/util/Hashtable.java src/share/classes/java/util/LinkedHashMap.java src/share/classes/java/util/WeakHashMap.java src/share/classes/sun/misc/Hashing.java test/java/util/Map/CheckRandomHashSeed.java test/java/util/Map/Collisions.java test/java/util/Map/InPlaceOpsCollisions.java test/java/util/Map/TreeBinSplitBackToEntries.java test/java/util/Spliterator/SpliteratorCollisions.java |
| diffstat | 10 files changed, 3482 insertions(+), 431 deletions(-) [+] |
line wrap: on
line diff
--- a/src/share/classes/java/util/HashMap.java Tue Jun 04 09:45:14 2013 +0200 +++ b/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/src/share/classes/java/util/Hashtable.java Tue Jun 04 09:45:14 2013 +0200 +++ b/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/src/share/classes/java/util/LinkedHashMap.java Tue Jun 04 09:45:14 2013 +0200 +++ b/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/src/share/classes/java/util/WeakHashMap.java Tue Jun 04 09:45:14 2013 +0200 +++ b/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/src/share/classes/sun/misc/Hashing.java Tue Jun 04 09:45:14 2013 +0200 +++ b/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/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/test/java/util/Map/Collisions.java Tue Jun 04 09:45:14 2013 +0200 +++ b/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/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/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/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())); + } + +}