jdk-sandbox: jdk/test/java/util/Map/InPlaceOpsCollisions.java@bd750ec19d82 (annotated)

12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	1	/*
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	2	* Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	3	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	4	*
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	5	* This code is free software; you can redistribute it and/or modify it
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	6	* under the terms of the GNU General Public License version 2 only, as
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	7	* published by the Free Software Foundation.
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	8	*
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	9	* This code is distributed in the hope that it will be useful, but WITHOUT
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	10	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	11	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	12	* version 2 for more details (a copy is included in the LICENSE file that
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	13	* accompanied this code).
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	14	*
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	15	* You should have received a copy of the GNU General Public License version
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	16	* 2 along with this work; if not, write to the Free Software Foundation,
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	17	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	18	*
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	19	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	20	* or visit www.oracle.com if you need additional information or have any
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	21	* questions.
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	22	*/
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	23
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	24	/*
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	25	* @test
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	26	* @bug 8005698
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	27	* @run main InPlaceOpsCollisions -shortrun
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	28	* @run main/othervm -Djdk.map.randomseed=true InPlaceOpsCollisions -shortrun
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	29	* @summary Ensure overrides of in-place operations in Maps behave well with lots of collisions.
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	30	* @author Brent Christian
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	31	*/
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	32	import java.util.*;
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	33	import java.util.function.*;
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	34
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	35	public class InPlaceOpsCollisions {
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	36
13805 29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	37	/**
29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	38	* Number of elements per map.
29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	39	*/
29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	40	private static final int TEST_SIZE = 5000;
29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	41
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	42	final static class HashableInteger implements Comparable<HashableInteger> {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	43
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	44	final int value;
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	45	final int hashmask; //yes duplication
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	46
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	47	HashableInteger(int value, int hashmask) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	48	this.value = value;
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	49	this.hashmask = hashmask;
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	50	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	51
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	52	@Override
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	53	public boolean equals(Object obj) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	54	if (obj instanceof HashableInteger) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	55	HashableInteger other = (HashableInteger) obj;
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	56
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	57	return other.value == value;
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	58	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	59
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	60	return false;
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	61	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	62
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	63	@Override
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	64	public int hashCode() {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	65	return value % hashmask;
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	66	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	67
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	68	@Override
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	69	public int compareTo(HashableInteger o) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	70	return value - o.value;
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	71	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	72
13805 29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	73	@Override
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	74	public String toString() {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	75	return Integer.toString(value);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	76	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	77	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	78
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	79	static HashableInteger EXTRA_INT_VAL;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	80	static String EXTRA_STRING_VAL;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	81
13805 29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	82	private static Object[][] makeTestData(int size) {
29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	83	HashableInteger UNIQUE_OBJECTS[] = new HashableInteger[size];
29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	84	HashableInteger COLLIDING_OBJECTS[] = new HashableInteger[size];
29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	85	String UNIQUE_STRINGS[] = new String[size];
29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	86	String COLLIDING_STRINGS[] = new String[size];
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	87
13805 29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	88	for (int i = 0; i < size; i++) {
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	89	UNIQUE_OBJECTS[i] = new HashableInteger(i, Integer.MAX_VALUE);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	90	COLLIDING_OBJECTS[i] = new HashableInteger(i, 10);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	91	UNIQUE_STRINGS[i] = unhash(i);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	92	COLLIDING_STRINGS[i] = (0 == i % 2)
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	93	? UNIQUE_STRINGS[i / 2]
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	94	: "\u0000\u0000\u0000\u0000\u0000" + COLLIDING_STRINGS[i - 1];
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	95	}
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	96	EXTRA_INT_VAL = new HashableInteger(size, Integer.MAX_VALUE);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	97	EXTRA_STRING_VAL = new String ("Extra Value");
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	98
13805 29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	99	return new Object[][] {
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	100	new Object[]{"Unique Objects", UNIQUE_OBJECTS},
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	101	new Object[]{"Colliding Objects", COLLIDING_OBJECTS},
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	102	new Object[]{"Unique Strings", UNIQUE_STRINGS},
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	103	new Object[]{"Colliding Strings", COLLIDING_STRINGS}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	104	};
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	105	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	106
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	107	/**
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	108	* Returns a string with a hash equal to the argument.
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	109	*
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	110	* @return string with a hash equal to the argument.
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	111	*/
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	112	public static String unhash(int target) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	113	StringBuilder answer = new StringBuilder();
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	114	if (target < 0) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	115	// String with hash of Integer.MIN_VALUE, 0x80000000
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	116	answer.append("\\u0915\\u0009\\u001e\\u000c\\u0002");
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	117
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	118	if (target == Integer.MIN_VALUE) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	119	return answer.toString();
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	120	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	121	// Find target without sign bit set
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	122	target = target & Integer.MAX_VALUE;
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	123	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	124
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	125	unhash0(answer, target);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	126	return answer.toString();
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	127	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	128
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	129	private static void unhash0(StringBuilder partial, int target) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	130	int div = target / 31;
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	131	int rem = target % 31;
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	132
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	133	if (div <= Character.MAX_VALUE) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	134	if (div != 0) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	135	partial.append((char) div);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	136	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	137	partial.append((char) rem);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	138	} else {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	139	unhash0(partial, div);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	140	partial.append((char) rem);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	141	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	142	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	143
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	144	private static void realMain(String[] args) throws Throwable {
13805 29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	145	boolean shortRun = args.length > 0 && args[0].equals("-shortrun");
29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	146
29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	147	Object[][] mapKeys = makeTestData(shortRun ? (TEST_SIZE / 2) : TEST_SIZE);
29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	148
29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	149	// loop through data sets
29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	150	for (Object[] keys_desc : mapKeys) {
29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	151	Map<Object, Object>[] maps = (Map<Object, Object>[]) new Map[]{
29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	152	new HashMap<>(),
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	153	new LinkedHashMap<>(),
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	154	};
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	155
13805 29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	156	// for each map type.
29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	157	for (Map<Object, Object> map : maps) {
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	158	String desc = (String) keys_desc[0];
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	159	Object[] keys = (Object[]) keys_desc[1];
13025 e070f58ad775 7175758: Improve unit test of Map iterators and Iterator.remove() mduigou parents: 12859 diff changeset	160	try {
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	161	testInPlaceOps(map, desc, keys);
13025 e070f58ad775 7175758: Improve unit test of Map iterators and Iterator.remove() mduigou parents: 12859 diff changeset	162	} catch(Exception all) {
e070f58ad775 7175758: Improve unit test of Map iterators and Iterator.remove() mduigou parents: 12859 diff changeset	163	unexpected("Failed for " + map.getClass().getName() + " with " + desc, all);
e070f58ad775 7175758: Improve unit test of Map iterators and Iterator.remove() mduigou parents: 12859 diff changeset	164	}
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	165	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	166	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	167	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	168
13025 e070f58ad775 7175758: Improve unit test of Map iterators and Iterator.remove() mduigou parents: 12859 diff changeset	169	private static <T> void testInsertion(Map<T, T> map, String keys_desc, T[] keys) {
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	170	check("map empty", (map.size() == 0) && map.isEmpty());
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	171
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	172	for (int i = 0; i < keys.length; i++) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	173	check(String.format("insertion: map expected size m%d != i%d", map.size(), i),
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	174	map.size() == i);
13025 e070f58ad775 7175758: Improve unit test of Map iterators and Iterator.remove() mduigou parents: 12859 diff changeset	175	check(String.format("insertion: put(%s[%d])", keys_desc, i), null == map.put(keys[i], keys[i]));
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	176	check(String.format("insertion: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
13025 e070f58ad775 7175758: Improve unit test of Map iterators and Iterator.remove() mduigou parents: 12859 diff changeset	177	check(String.format("insertion: containsValue(%s[%d])", keys_desc, i), map.containsValue(keys[i]));
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	178	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	179
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	180	check(String.format("map expected size m%d != k%d", map.size(), keys.length),
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	181	map.size() == keys.length);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	182	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	183
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	184
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	185	private static <T> void testInPlaceOps(Map<T, T> map, String keys_desc, T[] keys) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	186	System.out.println(map.getClass() + " : " + keys_desc + ", testInPlaceOps");
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	187	System.out.flush();
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	188
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	189	testInsertion(map, keys_desc, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	190	testPutIfAbsent(map, keys_desc, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	191
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	192	map.clear();
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	193	testInsertion(map, keys_desc, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	194	testRemoveMapping(map, keys_desc, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	195
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	196	map.clear();
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	197	testInsertion(map, keys_desc, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	198	testReplaceOldValue(map, keys_desc, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	199
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	200	map.clear();
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	201	testInsertion(map, keys_desc, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	202	testReplaceIfMapped(map, keys_desc, keys);
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	203
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	204	map.clear();
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	205	testInsertion(map, keys_desc, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	206	testComputeIfAbsent(map, keys_desc, keys, (k) -> getExtraVal(keys[0]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	207
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	208	map.clear();
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	209	testInsertion(map, keys_desc, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	210	testComputeIfAbsent(map, keys_desc, keys, (k) -> null);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	211
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	212	map.clear();
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	213	testInsertion(map, keys_desc, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	214	testComputeIfPresent(map, keys_desc, keys, (k, v) -> getExtraVal(keys[0]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	215
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	216	map.clear();
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	217	testInsertion(map, keys_desc, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	218	testComputeIfPresent(map, keys_desc, keys, (k, v) -> null);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	219
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	220	if (!keys_desc.contains("Strings")) { // avoid parseInt() number format error
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	221	map.clear();
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	222	testInsertion(map, keys_desc, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	223	testComputeNonNull(map, keys_desc, keys);
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	224	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	225
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	226	map.clear();
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	227	testInsertion(map, keys_desc, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	228	testComputeNull(map, keys_desc, keys);
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	229
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	230	if (!keys_desc.contains("Strings")) { // avoid parseInt() number format error
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	231	map.clear();
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	232	testInsertion(map, keys_desc, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	233	testMergeNonNull(map, keys_desc, keys);
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	234	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	235
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	236	map.clear();
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	237	testInsertion(map, keys_desc, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	238	testMergeNull(map, keys_desc, keys);
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	239	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	240
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	241
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	242
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	243	private static <T> void testPutIfAbsent(Map<T, T> map, String keys_desc, T[] keys) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	244	T extraVal = getExtraVal(keys[0]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	245	T retVal;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	246	removeOddKeys(map, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	247	for (int i = 0; i < keys.length; i++) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	248	retVal = map.putIfAbsent(keys[i], extraVal);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	249	if (i % 2 == 0) { // even: not absent, not put
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	250	check(String.format("putIfAbsent: (%s[%d]) retVal", keys_desc, i), retVal == keys[i]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	251	check(String.format("putIfAbsent: get(%s[%d])", keys_desc, i), keys[i] == map.get(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	252	check(String.format("putIfAbsent: containsValue(%s[%d])", keys_desc, i), map.containsValue(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	253	} else { // odd: absent, was put
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	254	check(String.format("putIfAbsent: (%s[%d]) retVal", keys_desc, i), retVal == null);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	255	check(String.format("putIfAbsent: get(%s[%d])", keys_desc, i), extraVal == map.get(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	256	check(String.format("putIfAbsent: !containsValue(%s[%d])", keys_desc, i), !map.containsValue(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	257	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	258	check(String.format("insertion: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	259	}
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	260	check(String.format("map expected size m%d != k%d", map.size(), keys.length),
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	261	map.size() == keys.length);
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	262	}
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	263
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	264	private static <T> void testRemoveMapping(Map<T, T> map, String keys_desc, T[] keys) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	265	T extraVal = getExtraVal(keys[0]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	266	boolean removed;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	267	int removes = 0;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	268	remapOddKeys(map, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	269	for (int i = 0; i < keys.length; i++) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	270	removed = map.remove(keys[i], keys[i]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	271	if (i % 2 == 0) { // even: original mapping, should be removed
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	272	check(String.format("removeMapping: retVal(%s[%d])", keys_desc, i), removed);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	273	check(String.format("removeMapping: get(%s[%d])", keys_desc, i), null == map.get(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	274	check(String.format("removeMapping: !containsKey(%s[%d])", keys_desc, i), !map.containsKey(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	275	check(String.format("removeMapping: !containsValue(%s[%d])", keys_desc, i), !map.containsValue(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	276	removes++;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	277	} else { // odd: new mapping, not removed
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	278	check(String.format("removeMapping: retVal(%s[%d])", keys_desc, i), !removed);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	279	check(String.format("removeMapping: get(%s[%d])", keys_desc, i), extraVal == map.get(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	280	check(String.format("removeMapping: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	281	check(String.format("removeMapping: containsValue(%s[%d])", keys_desc, i), map.containsValue(extraVal));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	282	}
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	283	}
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	284	check(String.format("map expected size m%d != k%d", map.size(), keys.length - removes),
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	285	map.size() == keys.length - removes);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	286	}
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	287
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	288	private static <T> void testReplaceOldValue(Map<T, T> map, String keys_desc, T[] keys) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	289	// remap odds to extraVal
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	290	// call replace to replace for extraVal, for all keys
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	291	// check that all keys map to value from keys array
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	292	T extraVal = getExtraVal(keys[0]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	293	boolean replaced;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	294	remapOddKeys(map, keys);
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	295
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	296	for (int i = 0; i < keys.length; i++) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	297	replaced = map.replace(keys[i], extraVal, keys[i]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	298	if (i % 2 == 0) { // even: original mapping, should not be replaced
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	299	check(String.format("replaceOldValue: retVal(%s[%d])", keys_desc, i), !replaced);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	300	} else { // odd: new mapping, should be replaced
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	301	check(String.format("replaceOldValue: get(%s[%d])", keys_desc, i), replaced);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	302	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	303	check(String.format("replaceOldValue: get(%s[%d])", keys_desc, i), keys[i] == map.get(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	304	check(String.format("replaceOldValue: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	305	check(String.format("replaceOldValue: containsValue(%s[%d])", keys_desc, i), map.containsValue(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	306	// removes++;
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	307	}
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	308	check(String.format("replaceOldValue: !containsValue(%s[%s])", keys_desc, extraVal.toString()), !map.containsValue(extraVal));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	309	check(String.format("map expected size m%d != k%d", map.size(), keys.length),
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	310	map.size() == keys.length);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	311	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	312
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	313	// TODO: Test case for key mapped to null value
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	314	private static <T> void testReplaceIfMapped(Map<T, T> map, String keys_desc, T[] keys) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	315	// remove odd keys
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	316	// call replace for all keys[]
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	317	// odd keys should remain absent, even keys should be mapped to EXTRA, no value from keys[] should be in map
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	318	T extraVal = getExtraVal(keys[0]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	319	int expectedSize1 = 0;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	320	removeOddKeys(map, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	321	int expectedSize2 = map.size();
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	322
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	323	for (int i = 0; i < keys.length; i++) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	324	T retVal = map.replace(keys[i], extraVal);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	325	if (i % 2 == 0) { // even: still in map, should be replaced
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	326	check(String.format("replaceIfMapped: retVal(%s[%d])", keys_desc, i), retVal == keys[i]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	327	check(String.format("replaceIfMapped: get(%s[%d])", keys_desc, i), extraVal == map.get(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	328	check(String.format("replaceIfMapped: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	329	expectedSize1++;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	330	} else { // odd: was removed, should not be replaced
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	331	check(String.format("replaceIfMapped: retVal(%s[%d])", keys_desc, i), retVal == null);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	332	check(String.format("replaceIfMapped: get(%s[%d])", keys_desc, i), null == map.get(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	333	check(String.format("replaceIfMapped: containsKey(%s[%d])", keys_desc, i), !map.containsKey(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	334	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	335	check(String.format("replaceIfMapped: !containsValue(%s[%d])", keys_desc, i), !map.containsValue(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	336	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	337	check(String.format("replaceIfMapped: containsValue(%s[%s])", keys_desc, extraVal.toString()), map.containsValue(extraVal));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	338	check(String.format("map expected size#1 m%d != k%d", map.size(), expectedSize1),
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	339	map.size() == expectedSize1);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	340	check(String.format("map expected size#2 m%d != k%d", map.size(), expectedSize2),
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	341	map.size() == expectedSize2);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	342
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	343	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	344
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	345	private static <T> void testComputeIfAbsent(Map<T, T> map, String keys_desc, T[] keys,
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	346	Function<T,T> mappingFunction) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	347	// remove a third of the keys
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	348	// call computeIfAbsent for all keys, func returns EXTRA
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	349	// check that removed keys now -> EXTRA, other keys -> original val
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	350	T expectedVal = mappingFunction.apply(keys[0]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	351	T retVal;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	352	int expectedSize = 0;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	353	removeThirdKeys(map, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	354	for (int i = 0; i < keys.length; i++) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	355	retVal = map.computeIfAbsent(keys[i], mappingFunction);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	356	if (i % 3 != 2) { // key present, not computed
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	357	check(String.format("computeIfAbsent: (%s[%d]) retVal", keys_desc, i), retVal == keys[i]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	358	check(String.format("computeIfAbsent: get(%s[%d])", keys_desc, i), keys[i] == map.get(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	359	check(String.format("computeIfAbsent: containsValue(%s[%d])", keys_desc, i), map.containsValue(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	360	check(String.format("insertion: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	361	expectedSize++;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	362	} else { // key absent, computed unless function return null
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	363	check(String.format("computeIfAbsent: (%s[%d]) retVal", keys_desc, i), retVal == expectedVal);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	364	check(String.format("computeIfAbsent: get(%s[%d])", keys_desc, i), expectedVal == map.get(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	365	check(String.format("computeIfAbsent: !containsValue(%s[%d])", keys_desc, i), !map.containsValue(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	366	// mapping should not be added if function returns null
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	367	check(String.format("insertion: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]) != (expectedVal == null));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	368	if (expectedVal != null) { expectedSize++; }
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	369	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	370	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	371	if (expectedVal != null) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	372	check(String.format("computeIfAbsent: containsValue(%s[%s])", keys_desc, expectedVal), map.containsValue(expectedVal));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	373	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	374	check(String.format("map expected size m%d != k%d", map.size(), expectedSize),
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	375	map.size() == expectedSize);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	376	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	377
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	378	private static <T> void testComputeIfPresent(Map<T, T> map, String keys_desc, T[] keys,
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	379	BiFunction<T,T,T> mappingFunction) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	380	// remove a third of the keys
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	381	// call testComputeIfPresent for all keys[]
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	382	// removed keys should remain absent, even keys should be mapped to $RESULT
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	383	// no value from keys[] should be in map
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	384	T funcResult = mappingFunction.apply(keys[0], keys[0]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	385	int expectedSize1 = 0;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	386	removeThirdKeys(map, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	387
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	388	for (int i = 0; i < keys.length; i++) {
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	389	T retVal = map.computeIfPresent(keys[i], mappingFunction);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	390	if (i % 3 != 2) { // key present
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	391	if (funcResult == null) { // was removed
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	392	check(String.format("replaceIfMapped: containsKey(%s[%d])", keys_desc, i), !map.containsKey(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	393	} else { // value was replaced
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	394	check(String.format("replaceIfMapped: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	395	expectedSize1++;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	396	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	397	check(String.format("computeIfPresent: retVal(%s[%s])", keys_desc, i), retVal == funcResult);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	398	check(String.format("replaceIfMapped: get(%s[%d])", keys_desc, i), funcResult == map.get(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	399
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	400	} else { // odd: was removed, should not be replaced
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	401	check(String.format("replaceIfMapped: retVal(%s[%d])", keys_desc, i), retVal == null);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	402	check(String.format("replaceIfMapped: get(%s[%d])", keys_desc, i), null == map.get(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	403	check(String.format("replaceIfMapped: containsKey(%s[%d])", keys_desc, i), !map.containsKey(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	404	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	405	check(String.format("replaceIfMapped: !containsValue(%s[%d])", keys_desc, i), !map.containsValue(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	406	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	407	check(String.format("map expected size#1 m%d != k%d", map.size(), expectedSize1),
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	408	map.size() == expectedSize1);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	409	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	410
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	411	private static <T> void testComputeNonNull(Map<T, T> map, String keys_desc, T[] keys) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	412	// remove a third of the keys
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	413	// call compute() for all keys[]
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	414	// all keys should be present: removed keys -> EXTRA, others to k-1
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	415	BiFunction<T,T,T> mappingFunction = (k, v) -> {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	416	if (v == null) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	417	return getExtraVal(keys[0]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	418	} else {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	419	return keys[Integer.parseInt(k.toString()) - 1];
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	420	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	421	};
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	422	T extraVal = getExtraVal(keys[0]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	423	removeThirdKeys(map, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	424	for (int i = 1; i < keys.length; i++) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	425	T retVal = map.compute(keys[i], mappingFunction);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	426	if (i % 3 != 2) { // key present, should be mapped to k-1
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	427	check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == keys[i-1]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	428	check(String.format("compute: get(%s[%d])", keys_desc, i), keys[i-1] == map.get(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	429	} else { // odd: was removed, should be replaced with EXTRA
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	430	check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == extraVal);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	431	check(String.format("compute: get(%s[%d])", keys_desc, i), extraVal == map.get(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	432	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	433	check(String.format("compute: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	434	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	435	check(String.format("map expected size#1 m%d != k%d", map.size(), keys.length),
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	436	map.size() == keys.length);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	437	check(String.format("compute: containsValue(%s[%s])", keys_desc, extraVal.toString()), map.containsValue(extraVal));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	438	check(String.format("compute: !containsValue(%s,[null])", keys_desc), !map.containsValue(null));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	439	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	440
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	441	private static <T> void testComputeNull(Map<T, T> map, String keys_desc, T[] keys) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	442	// remove a third of the keys
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	443	// call compute() for all keys[]
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	444	// removed keys should -> EXTRA
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	445	// for other keys: func returns null, should have no mapping
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	446	BiFunction<T,T,T> mappingFunction = (k, v) -> {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	447	// if absent/null -> EXTRA
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	448	// if present -> null
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	449	if (v == null) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	450	return getExtraVal(keys[0]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	451	} else {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	452	return null;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	453	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	454	};
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	455	T extraVal = getExtraVal(keys[0]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	456	int expectedSize = 0;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	457	removeThirdKeys(map, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	458	for (int i = 0; i < keys.length; i++) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	459	T retVal = map.compute(keys[i], mappingFunction);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	460	if (i % 3 != 2) { // key present, func returned null, should be absent from map
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	461	check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == null);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	462	check(String.format("compute: get(%s[%d])", keys_desc, i), null == map.get(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	463	check(String.format("compute: containsKey(%s[%d])", keys_desc, i), !map.containsKey(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	464	check(String.format("compute: containsValue(%s[%s])", keys_desc, i), !map.containsValue(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	465	} else { // odd: was removed, should now be mapped to EXTRA
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	466	check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == extraVal);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	467	check(String.format("compute: get(%s[%d])", keys_desc, i), extraVal == map.get(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	468	check(String.format("compute: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	469	expectedSize++;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	470	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	471	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	472	check(String.format("compute: containsValue(%s[%s])", keys_desc, extraVal.toString()), map.containsValue(extraVal));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	473	check(String.format("map expected size#1 m%d != k%d", map.size(), expectedSize),
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	474	map.size() == expectedSize);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	475	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	476
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	477	private static <T> void testMergeNonNull(Map<T, T> map, String keys_desc, T[] keys) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	478	// remove a third of the keys
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	479	// call merge() for all keys[]
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	480	// all keys should be present: removed keys now -> EXTRA, other keys -> k-1
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	481
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	482	// Map to preceding key
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	483	BiFunction<T,T,T> mappingFunction = (k, v) -> keys[Integer.parseInt(k.toString()) - 1];
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	484	T extraVal = getExtraVal(keys[0]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	485	removeThirdKeys(map, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	486	for (int i = 1; i < keys.length; i++) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	487	T retVal = map.merge(keys[i], extraVal, mappingFunction);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	488	if (i % 3 != 2) { // key present, should be mapped to k-1
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	489	check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == keys[i-1]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	490	check(String.format("compute: get(%s[%d])", keys_desc, i), keys[i-1] == map.get(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	491	} else { // odd: was removed, should be replaced with EXTRA
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	492	check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == extraVal);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	493	check(String.format("compute: get(%s[%d])", keys_desc, i), extraVal == map.get(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	494	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	495	check(String.format("compute: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	496	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	497
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	498	check(String.format("map expected size#1 m%d != k%d", map.size(), keys.length),
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	499	map.size() == keys.length);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	500	check(String.format("compute: containsValue(%s[%s])", keys_desc, extraVal.toString()), map.containsValue(extraVal));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	501	check(String.format("compute: !containsValue(%s,[null])", keys_desc), !map.containsValue(null));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	502
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	503	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	504
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	505	private static <T> void testMergeNull(Map<T, T> map, String keys_desc, T[] keys) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	506	// remove a third of the keys
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	507	// call merge() for all keys[]
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	508	// result: removed keys -> EXTRA, other keys absent
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	509
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	510	BiFunction<T,T,T> mappingFunction = (k, v) -> null;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	511	T extraVal = getExtraVal(keys[0]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	512	int expectedSize = 0;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	513	removeThirdKeys(map, keys);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	514	for (int i = 0; i < keys.length; i++) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	515	T retVal = map.merge(keys[i], extraVal, mappingFunction);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	516	if (i % 3 != 2) { // key present, func returned null, should be absent from map
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	517	check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == null);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	518	check(String.format("compute: get(%s[%d])", keys_desc, i), null == map.get(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	519	check(String.format("compute: containsKey(%s[%d])", keys_desc, i), !map.containsKey(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	520	} else { // odd: was removed, should now be mapped to EXTRA
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	521	check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == extraVal);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	522	check(String.format("compute: get(%s[%d])", keys_desc, i), extraVal == map.get(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	523	check(String.format("compute: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	524	expectedSize++;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	525	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	526	check(String.format("compute: containsValue(%s[%s])", keys_desc, i), !map.containsValue(keys[i]));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	527	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	528	check(String.format("compute: containsValue(%s[%s])", keys_desc, extraVal.toString()), map.containsValue(extraVal));
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	529	check(String.format("map expected size#1 m%d != k%d", map.size(), expectedSize),
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	530	map.size() == expectedSize);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	531	}
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	532
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	533	/*
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	534	* Return the EXTRA val for the key type being used
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	535	*/
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	536	private static <T> T getExtraVal(T key) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	537	if (key instanceof HashableInteger) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	538	return (T)EXTRA_INT_VAL;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	539	} else {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	540	return (T)EXTRA_STRING_VAL;
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	541	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	542	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	543
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	544	/*
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	545	* Remove half of the keys
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	546	*/
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	547	private static <T> void removeOddKeys(Map<T, T> map, /String keys_desc, / T[] keys) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	548	int removes = 0;
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	549	for (int i = 0; i < keys.length; i++) {
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	550	if (i % 2 != 0) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	551	map.remove(keys[i]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	552	removes++;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	553	}
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	554	}
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	555	check(String.format("map expected size m%d != k%d", map.size(), keys.length - removes),
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	556	map.size() == keys.length - removes);
13025 e070f58ad775 7175758: Improve unit test of Map iterators and Iterator.remove() mduigou parents: 12859 diff changeset	557	}
e070f58ad775 7175758: Improve unit test of Map iterators and Iterator.remove() mduigou parents: 12859 diff changeset	558
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	559	/*
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	560	* Remove every third key
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	561	* This will hopefully leave some removed keys in TreeBins for, e.g., computeIfAbsent
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	562	* w/ a func that returns null.
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	563	*
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	564	* TODO: consider using this in other tests (and maybe adding a remapThirdKeys)
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	565	*/
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	566	private static <T> void removeThirdKeys(Map<T, T> map, /String keys_desc, / T[] keys) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	567	int removes = 0;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	568	for (int i = 0; i < keys.length; i++) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	569	if (i % 3 == 2) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	570	map.remove(keys[i]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	571	removes++;
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	572	}
13025 e070f58ad775 7175758: Improve unit test of Map iterators and Iterator.remove() mduigou parents: 12859 diff changeset	573	}
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	574	check(String.format("map expected size m%d != k%d", map.size(), keys.length - removes),
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	575	map.size() == keys.length - removes);
13025 e070f58ad775 7175758: Improve unit test of Map iterators and Iterator.remove() mduigou parents: 12859 diff changeset	576	}
e070f58ad775 7175758: Improve unit test of Map iterators and Iterator.remove() mduigou parents: 12859 diff changeset	577
17939 bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	578	/*
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	579	* Re-map the odd-numbered keys to map to the EXTRA value
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	580	*/
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	581	private static <T> void remapOddKeys(Map<T, T> map, /String keys_desc, / T[] keys) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	582	T extraVal = getExtraVal(keys[0]);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	583	for (int i = 0; i < keys.length; i++) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	584	if (i % 2 != 0) {
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	585	map.put(keys[i], extraVal);
bd750ec19d82 8005698: Handle Frequent HashMap Collisions with Balanced Trees bchristi parents: 13817 diff changeset	586	}
13025 e070f58ad775 7175758: Improve unit test of Map iterators and Iterator.remove() mduigou parents: 12859 diff changeset	587	}
e070f58ad775 7175758: Improve unit test of Map iterators and Iterator.remove() mduigou parents: 12859 diff changeset	588	}
e070f58ad775 7175758: Improve unit test of Map iterators and Iterator.remove() mduigou parents: 12859 diff changeset	589
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	590	//--------------------- Infrastructure ---------------------------
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	591	static volatile int passed = 0, failed = 0;
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	592
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	593	static void pass() {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	594	passed++;
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	595	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	596
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	597	static void fail() {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	598	failed++;
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	599	(new Error("Failure")).printStackTrace(System.err);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	600	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	601
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	602	static void fail(String msg) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	603	failed++;
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	604	(new Error("Failure: " + msg)).printStackTrace(System.err);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	605	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	606
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	607	static void abort() {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	608	fail();
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	609	System.exit(1);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	610	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	611
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	612	static void abort(String msg) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	613	fail(msg);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	614	System.exit(1);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	615	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	616
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	617	static void unexpected(String msg, Throwable t) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	618	System.err.println("Unexpected: " + msg);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	619	unexpected(t);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	620	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	621
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	622	static void unexpected(Throwable t) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	623	failed++;
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	624	t.printStackTrace(System.err);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	625	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	626
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	627	static void check(boolean cond) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	628	if (cond) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	629	pass();
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	630	} else {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	631	fail();
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	632	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	633	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	634
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	635	static void check(String desc, boolean cond) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	636	if (cond) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	637	pass();
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	638	} else {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	639	fail(desc);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	640	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	641	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	642
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	643	static void equal(Object x, Object y) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	644	if (Objects.equals(x, y)) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	645	pass();
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	646	} else {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	647	fail(x + " not equal to " + y);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	648	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	649	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	650
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	651	public static void main(String[] args) throws Throwable {
13805 29e474ceeddc 7189926: Reduce test size for default run. Add additional run enabling alternative hashing. mduigou parents: 13025 diff changeset	652	Thread.currentThread().setName(Collisions.class.getName());
12859 c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	653	// Thread.currentThread().setPriority(Thread.MAX_PRIORITY);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	654	try {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	655	realMain(args);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	656	} catch (Throwable t) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	657	unexpected(t);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	658	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	659
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	660	System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	661	if (failed > 0) {
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	662	throw new Error("Some tests failed");
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	663	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	664	}
c44b88bb9b5e 7126277: Alternative String hashing implementation mduigou parents: diff changeset	665	}

author	bchristi
	Tue, 04 Jun 2013 10:04:28 +0100
changeset 17939	bd750ec19d82
parent 13817	jdk/test/java/util/Map/Collisions.java@23f16430801a
child 19806	dda89341ee2d
permissions	-rw-r--r--