OpenJDK / jdk / hs
changeset 42669:0b8c4fd7cc85
8023898: Consolidate Map tests Collisions and InPlaceOpsCollisions into general Map-based test
Reviewed-by: psandoz
| author | amlu |
|---|---|
| date | Tue, 13 Dec 2016 09:55:38 +0800 |
| parents | 9518a1858a96 |
| children | d833113eb7d7 |
| files | jdk/test/java/util/Map/Collisions.java jdk/test/java/util/Map/InPlaceOpsCollisions.java jdk/test/java/util/Map/MapWithCollisionsProviders.java |
| diffstat | 3 files changed, 664 insertions(+), 815 deletions(-) [+] |
line wrap: on
line diff
--- a/jdk/test/java/util/Map/Collisions.java Mon Dec 12 17:40:54 2016 -0800 +++ b/jdk/test/java/util/Map/Collisions.java Tue Dec 13 09:55:38 2016 +0800 @@ -1,5 +1,5 @@ /* - * Copyright (c) 2012, 2015, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 2012, 2016, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -24,427 +24,155 @@ /* * @test * @bug 7126277 - * @run main Collisions -shortrun + * @run testng/othervm -Dtest.map.collisions.shortrun=true Collisions * @summary Ensure Maps behave well with lots of hashCode() collisions. - * @author Mike Duigou */ -import java.util.*; -import java.util.concurrent.ConcurrentHashMap; -import java.util.concurrent.ConcurrentSkipListMap; +import java.util.BitSet; +import java.util.IdentityHashMap; +import java.util.Iterator; +import java.util.Map; +import java.util.function.Supplier; -public class Collisions { +import org.testng.annotations.Test; +import static org.testng.Assert.assertTrue; +import static org.testng.Assert.assertFalse; +import static org.testng.Assert.assertEquals; +import static org.testng.Assert.assertNotNull; - /** - * Number of elements per map. - */ - private static final int TEST_SIZE = 5000; +public class Collisions extends MapWithCollisionsProviders { - static final class HashableInteger implements Comparable<HashableInteger> { + @Test(dataProvider = "mapsWithObjects") + void testIntegerIteration(String desc, Supplier<Map<IntKey, IntKey>> ms, IntKey val) { + Map<IntKey, IntKey> map = ms.get(); + int mapSize = map.size(); - final int value; - final int hashmask; //yes duplication - - HashableInteger(int value, int hashmask) { - this.value = value; - this.hashmask = hashmask; + BitSet all = new BitSet(mapSize); + for (Map.Entry<IntKey, IntKey> each : map.entrySet()) { + assertFalse(all.get(each.getKey().getValue()), "Iteration: key already seen"); + all.set(each.getKey().getValue()); } - @Override - public boolean equals(Object obj) { - if (obj instanceof HashableInteger) { - HashableInteger other = (HashableInteger) obj; + all.flip(0, mapSize); + assertTrue(all.isEmpty(), "Iteration: some keys not visited"); - return other.value == value; - } - - return false; + for (IntKey each : map.keySet()) { + assertFalse(all.get(each.getValue()), "Iteration: key already seen"); + all.set(each.getValue()); } - @Override - public int hashCode() { - return value % hashmask; - } - - @Override - public int compareTo(HashableInteger o) { - return value - o.value; - } - - @Override - public String toString() { - return Integer.toString(value); - } - } - - private static Object[][] makeTestData(int size) { - HashableInteger UNIQUE_OBJECTS[] = new HashableInteger[size]; - HashableInteger COLLIDING_OBJECTS[] = new HashableInteger[size]; - String UNIQUE_STRINGS[] = new String[size]; - String COLLIDING_STRINGS[] = new String[size]; - - for (int i = 0; i < size; i++) { - UNIQUE_OBJECTS[i] = new HashableInteger(i, Integer.MAX_VALUE); - COLLIDING_OBJECTS[i] = new HashableInteger(i, 10); - UNIQUE_STRINGS[i] = unhash(i); - COLLIDING_STRINGS[i] = (0 == i % 2) - ? UNIQUE_STRINGS[i / 2] - : "\u0000\u0000\u0000\u0000\u0000" + COLLIDING_STRINGS[i - 1]; - } - - return new Object[][] { - new Object[]{"Unique Objects", UNIQUE_OBJECTS}, - new Object[]{"Colliding Objects", COLLIDING_OBJECTS}, - new Object[]{"Unique Strings", UNIQUE_STRINGS}, - new Object[]{"Colliding Strings", COLLIDING_STRINGS} - }; - } - - /** - * Returns a string with a hash equal to the argument. - * - * @return string with a hash equal to the argument. - */ - public static String unhash(int target) { - StringBuilder answer = new StringBuilder(); - if (target < 0) { - // String with hash of Integer.MIN_VALUE, 0x80000000 - answer.append("\\u0915\\u0009\\u001e\\u000c\\u0002"); - - if (target == Integer.MIN_VALUE) { - return answer.toString(); - } - // Find target without sign bit set - target = target & Integer.MAX_VALUE; - } - - unhash0(answer, target); - return answer.toString(); - } - - private static void unhash0(StringBuilder partial, int target) { - int div = target / 31; - int rem = target % 31; - - if (div <= Character.MAX_VALUE) { - if (div != 0) { - partial.append((char) div); - } - partial.append((char) rem); - } else { - unhash0(partial, div); - partial.append((char) rem); - } - } - - private static void realMain(String[] args) throws Throwable { - boolean shortRun = args.length > 0 && args[0].equals("-shortrun"); - - Object[][] mapKeys = makeTestData(shortRun ? (TEST_SIZE / 2) : TEST_SIZE); - - // loop through data sets - for (Object[] keys_desc : mapKeys) { - Map<Object, Object>[] maps = (Map<Object, Object>[]) new Map[]{ - new HashMap<>(), - new Hashtable<>(), - new IdentityHashMap<>(), - new LinkedHashMap<>(), - new TreeMap<>(), - new WeakHashMap<>(), - new ConcurrentHashMap<>(), - new ConcurrentSkipListMap<>() - }; - - // for each map type. - for (Map<Object, Object> map : maps) { - String desc = (String) keys_desc[0]; - Object[] keys = (Object[]) keys_desc[1]; - try { - testMap(map, desc, keys); - } catch(Exception all) { - unexpected("Failed for " + map.getClass().getName() + " with " + desc, all); - } - } - } - } - - private static <T> void testMap(Map<T, T> map, String keys_desc, T[] keys) { - System.out.println(map.getClass() + " : " + keys_desc); - System.out.flush(); - testInsertion(map, keys_desc, keys); - - if (keys[0] instanceof HashableInteger) { - testIntegerIteration((Map<HashableInteger, HashableInteger>) map, (HashableInteger[]) keys); - } else { - testStringIteration((Map<String, String>) map, (String[]) keys); - } - - testContainsKey(map, keys_desc, keys); - - testRemove(map, keys_desc, keys); - - map.clear(); - testInsertion(map, keys_desc, keys); - testKeysIteratorRemove(map, keys_desc, keys); - - map.clear(); - testInsertion(map, keys_desc, keys); - testValuesIteratorRemove(map, keys_desc, keys); - - map.clear(); - testInsertion(map, keys_desc, keys); - testEntriesIteratorRemove(map, keys_desc, keys); - - check(map.isEmpty()); - } - - private static <T> void testInsertion(Map<T, T> map, String keys_desc, T[] keys) { - check(map.size() == 0 && map.isEmpty(), "map empty"); - - for (int i = 0; i < keys.length; i++) { - check(map.size() == i, "insertion: map expected size m%d != i%d", map.size(), i); - check(null == map.put(keys[i], keys[i]), "insertion: put(%s[%d])", keys_desc, i); - check(map.containsKey(keys[i]), "insertion: containsKey(%s[%d])", keys_desc, i); - check(map.containsValue(keys[i]), "insertion: containsValue(%s[%d])", keys_desc, i); - } - - check(map.size() == keys.length, "map expected size m%d != k%d", map.size(), keys.length); - } - - private static void testIntegerIteration(Map<HashableInteger, HashableInteger> map, HashableInteger[] keys) { - check(map.size() == keys.length, "map expected size m%d != k%d", map.size(), keys.length); - - BitSet all = new BitSet(keys.length); - for (Map.Entry<HashableInteger, HashableInteger> each : map.entrySet()) { - check(!all.get(each.getKey().value), "Iteration: key already seen"); - all.set(each.getKey().value); - } - - all.flip(0, keys.length); - check(all.isEmpty(), "Iteration: some keys not visited"); - - for (HashableInteger each : map.keySet()) { - check(!all.get(each.value), "Iteration: key already seen"); - all.set(each.value); - } - - all.flip(0, keys.length); - check(all.isEmpty(), "Iteration: some keys not visited"); + all.flip(0, mapSize); + assertTrue(all.isEmpty(), "Iteration: some keys not visited"); int count = 0; - for (HashableInteger each : map.values()) { + for (IntKey each : map.values()) { count++; } - check(map.size() == count, "Iteration: value count matches size m%d != c%d", map.size(), count); + assertEquals(map.size(), count, + String.format("Iteration: value count matches size m%d != c%d", map.size(), count)); } - private static void testStringIteration(Map<String, String> map, String[] keys) { - check(map.size() == keys.length, "map expected size m%d != k%d", map.size(), keys.length); + @Test(dataProvider = "mapsWithStrings") + void testStringIteration(String desc, Supplier<Map<String, String>> ms, String val) { + Map<String, String> map = ms.get(); + int mapSize = map.size(); - BitSet all = new BitSet(keys.length); + BitSet all = new BitSet(mapSize); for (Map.Entry<String, String> each : map.entrySet()) { String key = each.getKey(); boolean longKey = key.length() > 5; - int index = key.hashCode() + (longKey ? keys.length / 2 : 0); - check(!all.get(index), "key already seen"); + int index = key.hashCode() + (longKey ? mapSize / 2 : 0); + assertFalse(all.get(index), "key already seen"); all.set(index); } - all.flip(0, keys.length); - check(all.isEmpty(), "some keys not visited"); + all.flip(0, mapSize); + assertTrue(all.isEmpty(), "some keys not visited"); for (String each : map.keySet()) { boolean longKey = each.length() > 5; - int index = each.hashCode() + (longKey ? keys.length / 2 : 0); - check(!all.get(index), "key already seen"); + int index = each.hashCode() + (longKey ? mapSize / 2 : 0); + assertFalse(all.get(index), "key already seen"); all.set(index); } - all.flip(0, keys.length); - check(all.isEmpty(), "some keys not visited"); + all.flip(0, mapSize); + assertTrue(all.isEmpty(), "some keys not visited"); int count = 0; for (String each : map.values()) { count++; } - check(map.size() == keys.length, "value count matches size m%d != k%d", map.size(), keys.length); + assertEquals(map.size(), mapSize, + String.format("value count matches size m%d != k%d", map.size(), mapSize)); } - private static <T> void testContainsKey(Map<T, T> map, String keys_desc, T[] keys) { + @Test(dataProvider = "mapsWithObjectsAndStrings") + void testRemove(String desc, Supplier<Map<Object, Object>> ms, Object val) { + Map<Object, Object> map = ms.get(); + Object[] keys = map.keySet().toArray(); + for (int i = 0; i < keys.length; i++) { - T each = keys[i]; - check(map.containsKey(each), "containsKey: %s[%d]%s", keys_desc, i, each); + Object each = keys[i]; + assertNotNull(map.remove(each), + String.format("remove: %s[%d]%s", desc, i, each)); } + + assertTrue(map.size() == 0 && map.isEmpty(), + String.format("remove: map empty. size=%d", map.size())); } - private static <T> void testRemove(Map<T, T> map, String keys_desc, T[] keys) { - check(map.size() == keys.length, "remove: map expected size m%d != k%d", map.size(), keys.length); + @Test(dataProvider = "mapsWithObjectsAndStrings") + void testKeysIteratorRemove(String desc, Supplier<Map<Object, Object>> ms, Object val) { + Map<Object, Object> map = ms.get(); - for (int i = 0; i < keys.length; i++) { - T each = keys[i]; - check(null != map.remove(each), "remove: %s[%d]%s", keys_desc, i, each); + Iterator<Object> each = map.keySet().iterator(); + while (each.hasNext()) { + Object t = each.next(); + each.remove(); + assertFalse(map.containsKey(t), String.format("not removed: %s", each)); } - check(map.size() == 0 && map.isEmpty(), "remove: map empty. size=%d", map.size()); + assertTrue(map.size() == 0 && map.isEmpty(), + String.format("remove: map empty. size=%d", map.size())); } - private static <T> void testKeysIteratorRemove(Map<T, T> map, String keys_desc, T[] keys) { - check(map.size() == keys.length, "remove: map expected size m%d != k%d", map.size(), keys.length); + @Test(dataProvider = "mapsWithObjectsAndStrings") + void testValuesIteratorRemove(String desc, Supplier<Map<Object, Object>> ms, Object val) { + Map<Object, Object> map = ms.get(); - Iterator<T> each = map.keySet().iterator(); + Iterator<Object> each = map.values().iterator(); while (each.hasNext()) { - T t = each.next(); + Object t = each.next(); each.remove(); - check(!map.containsKey(t), "not removed: %s", each); + assertFalse(map.containsValue(t), String.format("not removed: %s", each)); } - check(map.size() == 0 && map.isEmpty(), "remove: map empty. size=%d", map.size()); + assertTrue(map.size() == 0 && map.isEmpty(), + String.format("remove: map empty. size=%d", map.size())); } - private static <T> void testValuesIteratorRemove(Map<T, T> map, String keys_desc, T[] keys) { - check(map.size() == keys.length, "remove: map expected size m%d != k%d", map.size(), keys.length); + @Test(dataProvider = "mapsWithObjectsAndStrings") + void testEntriesIteratorRemove(String desc, Supplier<Map<Object, Object>> ms, Object val) { + Map<Object, Object> map = ms.get(); - Iterator<T> each = map.values().iterator(); + Iterator<Map.Entry<Object, Object>> each = map.entrySet().iterator(); while (each.hasNext()) { - T t = each.next(); + Map.Entry<Object, Object> t = each.next(); + Object key = t.getKey(); + Object value = t.getValue(); each.remove(); - check(!map.containsValue(t), "not removed: %s", each); + assertTrue((map instanceof IdentityHashMap) || !map.entrySet().contains(t), + String.format("not removed: %s", each)); + assertFalse(map.containsKey(key), + String.format("not removed: %s", each)); + assertFalse(map.containsValue(value), + String.format("not removed: %s", each)); } - check(map.size() == 0 && map.isEmpty(), "remove: map empty. size=%d", map.size()); + assertTrue(map.size() == 0 && map.isEmpty(), + String.format("remove: map empty. size=%d", map.size())); } - private static <T> void testEntriesIteratorRemove(Map<T, T> map, String keys_desc, T[] keys) { - check(map.size() == keys.length, "remove: map expected size m%d != k%d", map.size(), keys.length); - - Iterator<Map.Entry<T,T>> each = map.entrySet().iterator(); - while (each.hasNext()) { - Map.Entry<T,T> t = each.next(); - T key = t.getKey(); - T value = t.getValue(); - each.remove(); - check((map instanceof IdentityHashMap) || !map.entrySet().contains(t), "not removed: %s", each); - check(!map.containsKey(key), "not removed: %s", each); - check(!map.containsValue(value), "not removed: %s", each); - } - - check(map.size() == 0 && map.isEmpty(), "remove: map empty. size=%d", map.size()); - } - - //--------------------- Infrastructure --------------------------- - static volatile int passed = 0, failed = 0; - - static void pass() { - passed++; - } - - static void fail() { - failed++; - (new Error("Failure")).printStackTrace(System.err); - } - - static void fail(String msg) { - failed++; - (new Error("Failure: " + msg)).printStackTrace(System.err); - } - - static void abort() { - fail(); - System.exit(1); - } - - static void abort(String msg) { - fail(msg); - System.exit(1); - } - - static void unexpected(String msg, Throwable t) { - System.err.println("Unexpected: " + msg); - unexpected(t); - } - - static void unexpected(Throwable t) { - failed++; - t.printStackTrace(System.err); - } - - static void check(boolean cond) { - if (cond) { - pass(); - } else { - fail(); - } - } - - static void check(boolean cond, String desc) { - if (cond) { - pass(); - } else { - fail(desc); - } - } - - static void check(boolean cond, String fmt, int i) { - if (cond) { - pass(); - } else { - fail(String.format(fmt, i)); - } - } - - static void check(boolean cond, String fmt, Object o) { - if (cond) { - pass(); - } else { - fail(String.format(fmt, o)); - } - } - - static void check(boolean cond, String fmt, int i1, int i2) { - if (cond) { - pass(); - } else { - fail(String.format(fmt, i1, i2)); - } - } - - static void check(boolean cond, String fmt, String s, int i) { - if (cond) { - pass(); - } else { - fail(String.format(fmt, s, i)); - } - } - - static void check(boolean cond, String fmt, String s, int i, Object o) { - if (cond) { - pass(); - } else { - fail(String.format(fmt, s, i, o)); - } - } - - static void equal(Object x, Object y) { - if (Objects.equals(x, y)) { - pass(); - } else { - fail(x + " not equal to " + y); - } - } - - public static void main(String[] args) throws Throwable { - Thread.currentThread().setName(Collisions.class.getName()); -// Thread.currentThread().setPriority(Thread.MAX_PRIORITY); - try { - realMain(args); - } catch (Throwable t) { - unexpected(t); - } - - System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); - if (failed > 0) { - throw new Error("Some tests failed"); - } - } }
--- a/jdk/test/java/util/Map/InPlaceOpsCollisions.java Mon Dec 12 17:40:54 2016 -0800 +++ b/jdk/test/java/util/Map/InPlaceOpsCollisions.java Tue Dec 13 09:55:38 2016 +0800 @@ -1,5 +1,5 @@ /* - * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 2013, 2016, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -24,325 +24,162 @@ /* * @test * @bug 8005698 - * @run main InPlaceOpsCollisions -shortrun + * @run testng/othervm -Dtest.map.collisions.shortrun=true InPlaceOpsCollisions * @summary Ensure overrides of in-place operations in Maps behave well with lots of collisions. - * @author Brent Christian */ -import java.util.*; -import java.util.function.*; +import java.util.Map; +import java.util.function.BiFunction; +import java.util.function.Function; +import java.util.function.Supplier; -public class InPlaceOpsCollisions { +import org.testng.annotations.Test; +import static org.testng.Assert.assertTrue; +import static org.testng.Assert.assertFalse; +import static org.testng.Assert.assertEquals; +import static org.testng.Assert.assertNull; - /** - * Number of elements per map. - */ - private static final int TEST_SIZE = 5000; +public class InPlaceOpsCollisions extends MapWithCollisionsProviders { - static final class HashableInteger implements Comparable<HashableInteger> { + @Test(dataProvider = "mapsWithObjectsAndStrings") + void testPutIfAbsent(String desc, Supplier<Map<Object, Object>> ms, Object val) { + Map<Object, Object> map = ms.get(); + Object[] keys = map.keySet().toArray(); + Object retVal; + removeOddKeys(map, keys); + for (int i = 0; i < keys.length; i++) { + retVal = map.putIfAbsent(keys[i], val); + if (i % 2 == 0) { // even: not absent, not put - final int value; - final int hashmask; //yes duplication - - HashableInteger(int value, int hashmask) { - this.value = value; - this.hashmask = hashmask; + assertEquals(retVal, keys[i], + String.format("putIfAbsent: (%s[%d]) retVal", desc, i)); + assertEquals(keys[i], map.get(keys[i]), + String.format("putIfAbsent: get(%s[%d])", desc, i)); + assertTrue(map.containsValue(keys[i]), + String.format("putIfAbsent: containsValue(%s[%d])", desc, i)); + } else { // odd: absent, was put + assertNull(retVal, + String.format("putIfAbsent: (%s[%d]) retVal", desc, i)); + assertEquals(val, map.get(keys[i]), + String.format("putIfAbsent: get(%s[%d])", desc, i)); + assertFalse(map.containsValue(keys[i]), + String.format("putIfAbsent: !containsValue(%s[%d])", desc, i)); + } + assertTrue(map.containsKey(keys[i]), + String.format("insertion: containsKey(%s[%d])", desc, i)); } - - @Override - public boolean equals(Object obj) { - if (obj instanceof HashableInteger) { - HashableInteger other = (HashableInteger) obj; - - return other.value == value; - } - - return false; - } - - @Override - public int hashCode() { - return value % hashmask; - } - - @Override - public int compareTo(HashableInteger o) { - return value - o.value; - } - - @Override - public String toString() { - return Integer.toString(value); - } + assertEquals(map.size(), keys.length, + String.format("map expected size m%d != k%d", map.size(), keys.length)); } - static HashableInteger EXTRA_INT_VAL; - static String EXTRA_STRING_VAL; - - private static Object[][] makeTestData(int size) { - HashableInteger UNIQUE_OBJECTS[] = new HashableInteger[size]; - HashableInteger COLLIDING_OBJECTS[] = new HashableInteger[size]; - String UNIQUE_STRINGS[] = new String[size]; - String COLLIDING_STRINGS[] = new String[size]; - - for (int i = 0; i < size; i++) { - UNIQUE_OBJECTS[i] = new HashableInteger(i, Integer.MAX_VALUE); - COLLIDING_OBJECTS[i] = new HashableInteger(i, 10); - UNIQUE_STRINGS[i] = unhash(i); - COLLIDING_STRINGS[i] = (0 == i % 2) - ? UNIQUE_STRINGS[i / 2] - : "\u0000\u0000\u0000\u0000\u0000" + COLLIDING_STRINGS[i - 1]; - } - EXTRA_INT_VAL = new HashableInteger(size, Integer.MAX_VALUE); - EXTRA_STRING_VAL = new String ("Extra Value"); - - return new Object[][] { - new Object[]{"Unique Objects", UNIQUE_OBJECTS}, - new Object[]{"Colliding Objects", COLLIDING_OBJECTS}, - new Object[]{"Unique Strings", UNIQUE_STRINGS}, - new Object[]{"Colliding Strings", COLLIDING_STRINGS} - }; - } - - /** - * Returns a string with a hash equal to the argument. - * - * @return string with a hash equal to the argument. - */ - public static String unhash(int target) { - StringBuilder answer = new StringBuilder(); - if (target < 0) { - // String with hash of Integer.MIN_VALUE, 0x80000000 - answer.append("\\u0915\\u0009\\u001e\\u000c\\u0002"); - - if (target == Integer.MIN_VALUE) { - return answer.toString(); - } - // Find target without sign bit set - target = target & Integer.MAX_VALUE; - } - - unhash0(answer, target); - return answer.toString(); - } - - private static void unhash0(StringBuilder partial, int target) { - int div = target / 31; - int rem = target % 31; - - if (div <= Character.MAX_VALUE) { - if (div != 0) { - partial.append((char) div); - } - partial.append((char) rem); - } else { - unhash0(partial, div); - partial.append((char) rem); - } - } - - private static void realMain(String[] args) throws Throwable { - boolean shortRun = args.length > 0 && args[0].equals("-shortrun"); - - Object[][] mapKeys = makeTestData(shortRun ? (TEST_SIZE / 2) : TEST_SIZE); - - // loop through data sets - for (Object[] keys_desc : mapKeys) { - Map<Object, Object>[] maps = (Map<Object, Object>[]) new Map[]{ - new HashMap<>(), - new LinkedHashMap<>(), - }; - - // for each map type. - for (Map<Object, Object> map : maps) { - String desc = (String) keys_desc[0]; - Object[] keys = (Object[]) keys_desc[1]; - try { - testInPlaceOps(map, desc, keys); - } catch(Exception all) { - unexpected("Failed for " + map.getClass().getName() + " with " + desc, all); - } - } - } - } - - private static <T> void testInsertion(Map<T, T> map, String keys_desc, T[] keys) { - check("map empty", (map.size() == 0) && map.isEmpty()); - - for (int i = 0; i < keys.length; i++) { - check(String.format("insertion: map expected size m%d != i%d", map.size(), i), - map.size() == i); - check(String.format("insertion: put(%s[%d])", keys_desc, i), null == map.put(keys[i], keys[i])); - check(String.format("insertion: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i])); - check(String.format("insertion: containsValue(%s[%d])", keys_desc, i), map.containsValue(keys[i])); - } - - check(String.format("map expected size m%d != k%d", map.size(), keys.length), - map.size() == keys.length); - } - - - private static <T> void testInPlaceOps(Map<T, T> map, String keys_desc, T[] keys) { - System.out.println(map.getClass() + " : " + keys_desc + ", testInPlaceOps"); - System.out.flush(); - - testInsertion(map, keys_desc, keys); - testPutIfAbsent(map, keys_desc, keys); - - map.clear(); - testInsertion(map, keys_desc, keys); - testRemoveMapping(map, keys_desc, keys); - - map.clear(); - testInsertion(map, keys_desc, keys); - testReplaceOldValue(map, keys_desc, keys); - - map.clear(); - testInsertion(map, keys_desc, keys); - testReplaceIfMapped(map, keys_desc, keys); - - map.clear(); - testInsertion(map, keys_desc, keys); - testComputeIfAbsent(map, keys_desc, keys, (k) -> getExtraVal(keys[0])); - - map.clear(); - testInsertion(map, keys_desc, keys); - testComputeIfAbsent(map, keys_desc, keys, (k) -> null); - - map.clear(); - testInsertion(map, keys_desc, keys); - testComputeIfPresent(map, keys_desc, keys, (k, v) -> getExtraVal(keys[0])); - - map.clear(); - testInsertion(map, keys_desc, keys); - testComputeIfPresent(map, keys_desc, keys, (k, v) -> null); - - if (!keys_desc.contains("Strings")) { // avoid parseInt() number format error - map.clear(); - testInsertion(map, keys_desc, keys); - testComputeNonNull(map, keys_desc, keys); - } - - map.clear(); - testInsertion(map, keys_desc, keys); - testComputeNull(map, keys_desc, keys); - - if (!keys_desc.contains("Strings")) { // avoid parseInt() number format error - map.clear(); - testInsertion(map, keys_desc, keys); - testMergeNonNull(map, keys_desc, keys); - } - - map.clear(); - testInsertion(map, keys_desc, keys); - testMergeNull(map, keys_desc, keys); - } - - - - private static <T> void testPutIfAbsent(Map<T, T> map, String keys_desc, T[] keys) { - T extraVal = getExtraVal(keys[0]); - T retVal; - removeOddKeys(map, keys); - for (int i = 0; i < keys.length; i++) { - retVal = map.putIfAbsent(keys[i], extraVal); - if (i % 2 == 0) { // even: not absent, not put - check(String.format("putIfAbsent: (%s[%d]) retVal", keys_desc, i), retVal == keys[i]); - check(String.format("putIfAbsent: get(%s[%d])", keys_desc, i), keys[i] == map.get(keys[i])); - check(String.format("putIfAbsent: containsValue(%s[%d])", keys_desc, i), map.containsValue(keys[i])); - } else { // odd: absent, was put - check(String.format("putIfAbsent: (%s[%d]) retVal", keys_desc, i), retVal == null); - check(String.format("putIfAbsent: get(%s[%d])", keys_desc, i), extraVal == map.get(keys[i])); - check(String.format("putIfAbsent: !containsValue(%s[%d])", keys_desc, i), !map.containsValue(keys[i])); - } - check(String.format("insertion: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i])); - } - check(String.format("map expected size m%d != k%d", map.size(), keys.length), - map.size() == keys.length); - } - - private static <T> void testRemoveMapping(Map<T, T> map, String keys_desc, T[] keys) { - T extraVal = getExtraVal(keys[0]); + @Test(dataProvider = "mapsWithObjectsAndStrings") + void testRemoveMapping(String desc, Supplier<Map<Object, Object>> ms, Object val) { + Map<Object, Object> map = ms.get(); + Object[] keys = map.keySet().toArray(); boolean removed; int removes = 0; - remapOddKeys(map, keys); + remapOddKeys(map, keys, val); for (int i = 0; i < keys.length; i++) { removed = map.remove(keys[i], keys[i]); if (i % 2 == 0) { // even: original mapping, should be removed - check(String.format("removeMapping: retVal(%s[%d])", keys_desc, i), removed); - check(String.format("removeMapping: get(%s[%d])", keys_desc, i), null == map.get(keys[i])); - check(String.format("removeMapping: !containsKey(%s[%d])", keys_desc, i), !map.containsKey(keys[i])); - check(String.format("removeMapping: !containsValue(%s[%d])", keys_desc, i), !map.containsValue(keys[i])); + assertTrue(removed, + String.format("removeMapping: retVal(%s[%d])", desc, i)); + assertNull(map.get(keys[i]), + String.format("removeMapping: get(%s[%d])", desc, i)); + assertFalse(map.containsKey(keys[i]), + String.format("removeMapping: !containsKey(%s[%d])", desc, i)); + assertFalse(map.containsValue(keys[i]), + String.format("removeMapping: !containsValue(%s[%d])", desc, i)); removes++; } else { // odd: new mapping, not removed - check(String.format("removeMapping: retVal(%s[%d])", keys_desc, i), !removed); - check(String.format("removeMapping: get(%s[%d])", keys_desc, i), extraVal == map.get(keys[i])); - check(String.format("removeMapping: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i])); - check(String.format("removeMapping: containsValue(%s[%d])", keys_desc, i), map.containsValue(extraVal)); + assertFalse(removed, + String.format("removeMapping: retVal(%s[%d])", desc, i)); + assertEquals(val, map.get(keys[i]), + String.format("removeMapping: get(%s[%d])", desc, i)); + assertTrue(map.containsKey(keys[i]), + String.format("removeMapping: containsKey(%s[%d])", desc, i)); + assertTrue(map.containsValue(val), + String.format("removeMapping: containsValue(%s[%d])", desc, i)); } } - check(String.format("map expected size m%d != k%d", map.size(), keys.length - removes), - map.size() == keys.length - removes); + assertEquals(map.size(), keys.length - removes, + String.format("map expected size m%d != k%d", map.size(), keys.length - removes)); } - private static <T> void testReplaceOldValue(Map<T, T> map, String keys_desc, T[] keys) { - // remap odds to extraVal - // call replace to replace for extraVal, for all keys + @Test(dataProvider = "mapsWithObjectsAndStrings") + void testReplaceOldValue(String desc, Supplier<Map<Object, Object>> ms, Object val) { + // remap odds to val + // call replace to replace for val, for all keys // check that all keys map to value from keys array - T extraVal = getExtraVal(keys[0]); + Map<Object, Object> map = ms.get(); + Object[] keys = map.keySet().toArray(); boolean replaced; - remapOddKeys(map, keys); + remapOddKeys(map, keys, val); for (int i = 0; i < keys.length; i++) { - replaced = map.replace(keys[i], extraVal, keys[i]); + replaced = map.replace(keys[i], val, keys[i]); if (i % 2 == 0) { // even: original mapping, should not be replaced - check(String.format("replaceOldValue: retVal(%s[%d])", keys_desc, i), !replaced); + assertFalse(replaced, + String.format("replaceOldValue: retVal(%s[%d])", desc, i)); } else { // odd: new mapping, should be replaced - check(String.format("replaceOldValue: get(%s[%d])", keys_desc, i), replaced); + assertTrue(replaced, + String.format("replaceOldValue: get(%s[%d])", desc, i)); } - check(String.format("replaceOldValue: get(%s[%d])", keys_desc, i), keys[i] == map.get(keys[i])); - check(String.format("replaceOldValue: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i])); - check(String.format("replaceOldValue: containsValue(%s[%d])", keys_desc, i), map.containsValue(keys[i])); -// removes++; + assertEquals(keys[i], map.get(keys[i]), + String.format("replaceOldValue: get(%s[%d])", desc, i)); + assertTrue(map.containsKey(keys[i]), + String.format("replaceOldValue: containsKey(%s[%d])", desc, i)); + assertTrue(map.containsValue(keys[i]), + String.format("replaceOldValue: containsValue(%s[%d])", desc, i)); } - check(String.format("replaceOldValue: !containsValue(%s[%s])", keys_desc, extraVal.toString()), !map.containsValue(extraVal)); - check(String.format("map expected size m%d != k%d", map.size(), keys.length), - map.size() == keys.length); + assertFalse(map.containsValue(val), + String.format("replaceOldValue: !containsValue(%s[%s])", desc, val)); + assertEquals(map.size(), keys.length, + String.format("map expected size m%d != k%d", map.size(), keys.length)); } - // TODO: Test case for key mapped to null value - private static <T> void testReplaceIfMapped(Map<T, T> map, String keys_desc, T[] keys) { + @Test(dataProvider = "mapsWithObjectsAndStrings") + void testReplaceIfMapped(String desc, Supplier<Map<Object, Object>> ms, Object val) { // remove odd keys // call replace for all keys[] // odd keys should remain absent, even keys should be mapped to EXTRA, no value from keys[] should be in map - T extraVal = getExtraVal(keys[0]); + Map<Object, Object> map = ms.get(); + Object[] keys = map.keySet().toArray(); int expectedSize1 = 0; removeOddKeys(map, keys); int expectedSize2 = map.size(); for (int i = 0; i < keys.length; i++) { - T retVal = map.replace(keys[i], extraVal); + Object retVal = map.replace(keys[i], val); if (i % 2 == 0) { // even: still in map, should be replaced - check(String.format("replaceIfMapped: retVal(%s[%d])", keys_desc, i), retVal == keys[i]); - check(String.format("replaceIfMapped: get(%s[%d])", keys_desc, i), extraVal == map.get(keys[i])); - check(String.format("replaceIfMapped: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i])); + assertEquals(retVal, keys[i], + String.format("replaceIfMapped: retVal(%s[%d])", desc, i)); + assertEquals(val, map.get(keys[i]), + String.format("replaceIfMapped: get(%s[%d])", desc, i)); + assertTrue(map.containsKey(keys[i]), + String.format("replaceIfMapped: containsKey(%s[%d])", desc, i)); expectedSize1++; } else { // odd: was removed, should not be replaced - check(String.format("replaceIfMapped: retVal(%s[%d])", keys_desc, i), retVal == null); - check(String.format("replaceIfMapped: get(%s[%d])", keys_desc, i), null == map.get(keys[i])); - check(String.format("replaceIfMapped: containsKey(%s[%d])", keys_desc, i), !map.containsKey(keys[i])); + assertNull(retVal, + String.format("replaceIfMapped: retVal(%s[%d])", desc, i)); + assertNull(map.get(keys[i]), + String.format("replaceIfMapped: get(%s[%d])", desc, i)); + assertFalse(map.containsKey(keys[i]), + String.format("replaceIfMapped: containsKey(%s[%d])", desc, i)); } - check(String.format("replaceIfMapped: !containsValue(%s[%d])", keys_desc, i), !map.containsValue(keys[i])); + assertFalse(map.containsValue(keys[i]), + String.format("replaceIfMapped: !containsValue(%s[%d])", desc, i)); } - check(String.format("replaceIfMapped: containsValue(%s[%s])", keys_desc, extraVal.toString()), map.containsValue(extraVal)); - check(String.format("map expected size#1 m%d != k%d", map.size(), expectedSize1), - map.size() == expectedSize1); - check(String.format("map expected size#2 m%d != k%d", map.size(), expectedSize2), - map.size() == expectedSize2); + assertTrue(map.containsValue(val), + String.format("replaceIfMapped: containsValue(%s[%s])", desc, val)); + assertEquals(map.size(), expectedSize1, + String.format("map expected size#1 m%d != k%d", map.size(), expectedSize1)); + assertEquals(map.size(), expectedSize2, + String.format("map expected size#2 m%d != k%d", map.size(), expectedSize2)); } - private static <T> void testComputeIfAbsent(Map<T, T> map, String keys_desc, T[] keys, - Function<T,T> mappingFunction) { + private static <T> void testComputeIfAbsent(Map<T, T> map, String desc, T[] keys, + Function<T, T> mappingFunction) { // remove a third of the keys // call computeIfAbsent for all keys, func returns EXTRA // check that removed keys now -> EXTRA, other keys -> original val @@ -353,29 +190,54 @@ for (int i = 0; i < keys.length; i++) { retVal = map.computeIfAbsent(keys[i], mappingFunction); if (i % 3 != 2) { // key present, not computed - check(String.format("computeIfAbsent: (%s[%d]) retVal", keys_desc, i), retVal == keys[i]); - check(String.format("computeIfAbsent: get(%s[%d])", keys_desc, i), keys[i] == map.get(keys[i])); - check(String.format("computeIfAbsent: containsValue(%s[%d])", keys_desc, i), map.containsValue(keys[i])); - check(String.format("insertion: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i])); + assertEquals(retVal, keys[i], + String.format("computeIfAbsent: (%s[%d]) retVal", desc, i)); + assertEquals(keys[i], map.get(keys[i]), + String.format("computeIfAbsent: get(%s[%d])", desc, i)); + assertTrue(map.containsValue(keys[i]), + String.format("computeIfAbsent: containsValue(%s[%d])", desc, i)); + assertTrue(map.containsKey(keys[i]), + String.format("insertion: containsKey(%s[%d])", desc, i)); expectedSize++; } else { // key absent, computed unless function return null - check(String.format("computeIfAbsent: (%s[%d]) retVal", keys_desc, i), retVal == expectedVal); - check(String.format("computeIfAbsent: get(%s[%d])", keys_desc, i), expectedVal == map.get(keys[i])); - check(String.format("computeIfAbsent: !containsValue(%s[%d])", keys_desc, i), !map.containsValue(keys[i])); + assertEquals(retVal, expectedVal, + String.format("computeIfAbsent: (%s[%d]) retVal", desc, i)); + assertEquals(expectedVal, map.get(keys[i]), + String.format("computeIfAbsent: get(%s[%d])", desc, i)); + assertFalse(map.containsValue(keys[i]), + String.format("computeIfAbsent: !containsValue(%s[%d])", desc, i)); // mapping should not be added if function returns null - check(String.format("insertion: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]) != (expectedVal == null)); - if (expectedVal != null) { expectedSize++; } + assertTrue(map.containsKey(keys[i]) != (expectedVal == null), + String.format("insertion: containsKey(%s[%d])", desc, i)); + if (expectedVal != null) { + expectedSize++; + } } } if (expectedVal != null) { - check(String.format("computeIfAbsent: containsValue(%s[%s])", keys_desc, expectedVal), map.containsValue(expectedVal)); + assertTrue(map.containsValue(expectedVal), + String.format("computeIfAbsent: containsValue(%s[%s])", desc, expectedVal)); } - check(String.format("map expected size m%d != k%d", map.size(), expectedSize), - map.size() == expectedSize); + assertEquals(map.size(), expectedSize, + String.format("map expected size m%d != k%d", map.size(), expectedSize)); } - private static <T> void testComputeIfPresent(Map<T, T> map, String keys_desc, T[] keys, - BiFunction<T,T,T> mappingFunction) { + @Test(dataProvider = "mapsWithObjectsAndStrings") + void testComputeIfAbsentNonNull(String desc, Supplier<Map<Object, Object>> ms, Object val) { + Map<Object, Object> map = ms.get(); + Object[] keys = map.keySet().toArray(); + testComputeIfAbsent(map, desc, keys, (k) -> val); + } + + @Test(dataProvider = "mapsWithObjectsAndStrings") + void testComputeIfAbsentNull(String desc, Supplier<Map<Object, Object>> ms, Object val) { + Map<Object, Object> map = ms.get(); + Object[] keys = map.keySet().toArray(); + testComputeIfAbsent(map, desc, keys, (k) -> null); + } + + private static <T> void testComputeIfPresent(Map<T, T> map, String desc, T[] keys, + BiFunction<T, T, T> mappingFunction) { // remove a third of the keys // call testComputeIfPresent for all keys[] // removed keys should remain absent, even keys should be mapped to $RESULT @@ -388,156 +250,205 @@ T retVal = map.computeIfPresent(keys[i], mappingFunction); if (i % 3 != 2) { // key present if (funcResult == null) { // was removed - check(String.format("replaceIfMapped: containsKey(%s[%d])", keys_desc, i), !map.containsKey(keys[i])); + assertFalse(map.containsKey(keys[i]), + String.format("replaceIfMapped: containsKey(%s[%d])", desc, i)); } else { // value was replaced - check(String.format("replaceIfMapped: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i])); + assertTrue(map.containsKey(keys[i]), + String.format("replaceIfMapped: containsKey(%s[%d])", desc, i)); expectedSize1++; } - check(String.format("computeIfPresent: retVal(%s[%s])", keys_desc, i), retVal == funcResult); - check(String.format("replaceIfMapped: get(%s[%d])", keys_desc, i), funcResult == map.get(keys[i])); + assertEquals(retVal, funcResult, + String.format("computeIfPresent: retVal(%s[%s])", desc, i)); + assertEquals(funcResult, map.get(keys[i]), + String.format("replaceIfMapped: get(%s[%d])", desc, i)); } else { // odd: was removed, should not be replaced - check(String.format("replaceIfMapped: retVal(%s[%d])", keys_desc, i), retVal == null); - check(String.format("replaceIfMapped: get(%s[%d])", keys_desc, i), null == map.get(keys[i])); - check(String.format("replaceIfMapped: containsKey(%s[%d])", keys_desc, i), !map.containsKey(keys[i])); + assertNull(retVal, + String.format("replaceIfMapped: retVal(%s[%d])", desc, i)); + assertNull(map.get(keys[i]), + String.format("replaceIfMapped: get(%s[%d])", desc, i)); + assertFalse(map.containsKey(keys[i]), + String.format("replaceIfMapped: containsKey(%s[%d])", desc, i)); } - check(String.format("replaceIfMapped: !containsValue(%s[%d])", keys_desc, i), !map.containsValue(keys[i])); + assertFalse(map.containsValue(keys[i]), + String.format("replaceIfMapped: !containsValue(%s[%d])", desc, i)); } - check(String.format("map expected size#1 m%d != k%d", map.size(), expectedSize1), - map.size() == expectedSize1); + assertEquals(map.size(), expectedSize1, + String.format("map expected size#1 m%d != k%d", map.size(), expectedSize1)); } - private static <T> void testComputeNonNull(Map<T, T> map, String keys_desc, T[] keys) { + @Test(dataProvider = "mapsWithObjectsAndStrings") + void testComputeIfPresentNonNull(String desc, Supplier<Map<Object, Object>> ms, Object val) { + Map<Object, Object> map = ms.get(); + Object[] keys = map.keySet().toArray(); + testComputeIfPresent(map, desc, keys, (k, v) -> val); + } + + @Test(dataProvider = "mapsWithObjectsAndStrings") + void testComputeIfPresentNull(String desc, Supplier<Map<Object, Object>> ms, Object val) { + Map<Object, Object> map = ms.get(); + Object[] keys = map.keySet().toArray(); + testComputeIfPresent(map, desc, keys, (k, v) -> null); + } + + @Test(dataProvider = "hashMapsWithObjects") + void testComputeNonNull(String desc, Supplier<Map<IntKey, IntKey>> ms, IntKey val) { // remove a third of the keys // call compute() for all keys[] // all keys should be present: removed keys -> EXTRA, others to k-1 - BiFunction<T,T,T> mappingFunction = (k, v) -> { - if (v == null) { - return getExtraVal(keys[0]); - } else { - return keys[Integer.parseInt(k.toString()) - 1]; - } - }; - T extraVal = getExtraVal(keys[0]); + Map<IntKey, IntKey> map = ms.get(); + IntKey[] keys = map.keySet().stream().sorted().toArray(IntKey[]::new); + BiFunction<IntKey, IntKey, IntKey> mappingFunction = (k, v) -> { + if (v == null) { + return val; + } else { + return keys[k.getValue() - 1]; + } + }; removeThirdKeys(map, keys); for (int i = 1; i < keys.length; i++) { - T retVal = map.compute(keys[i], mappingFunction); + IntKey retVal = map.compute(keys[i], mappingFunction); if (i % 3 != 2) { // key present, should be mapped to k-1 - check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == keys[i-1]); - check(String.format("compute: get(%s[%d])", keys_desc, i), keys[i-1] == map.get(keys[i])); + assertEquals(retVal, keys[i - 1], + String.format("compute: retVal(%s[%d])", desc, i)); + assertEquals(keys[i - 1], map.get(keys[i]), + String.format("compute: get(%s[%d])", desc, i)); } else { // odd: was removed, should be replaced with EXTRA - check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == extraVal); - check(String.format("compute: get(%s[%d])", keys_desc, i), extraVal == map.get(keys[i])); + assertEquals(retVal, val, + String.format("compute: retVal(%s[%d])", desc, i)); + assertEquals(val, map.get(keys[i]), + String.format("compute: get(%s[%d])", desc, i)); } - check(String.format("compute: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i])); + assertTrue(map.containsKey(keys[i]), + String.format("compute: containsKey(%s[%d])", desc, i)); } - check(String.format("map expected size#1 m%d != k%d", map.size(), keys.length), - map.size() == keys.length); - check(String.format("compute: containsValue(%s[%s])", keys_desc, extraVal.toString()), map.containsValue(extraVal)); - check(String.format("compute: !containsValue(%s,[null])", keys_desc), !map.containsValue(null)); + assertEquals(map.size(), keys.length, + String.format("map expected size#1 m%d != k%d", map.size(), keys.length)); + assertTrue(map.containsValue(val), + String.format("compute: containsValue(%s[%s])", desc, val)); + assertFalse(map.containsValue(null), + String.format("compute: !containsValue(%s,[null])", desc)); } - private static <T> void testComputeNull(Map<T, T> map, String keys_desc, T[] keys) { + @Test(dataProvider = "mapsWithObjectsAndStrings") + void testComputeNull(String desc, Supplier<Map<Object, Object>> ms, Object val) { // remove a third of the keys // call compute() for all keys[] // removed keys should -> EXTRA // for other keys: func returns null, should have no mapping - BiFunction<T,T,T> mappingFunction = (k, v) -> { + Map<Object, Object> map = ms.get(); + Object[] keys = map.keySet().toArray(); + BiFunction<Object, Object, Object> mappingFunction = (k, v) -> { // if absent/null -> EXTRA // if present -> null if (v == null) { - return getExtraVal(keys[0]); + return val; } else { return null; } }; - T extraVal = getExtraVal(keys[0]); int expectedSize = 0; removeThirdKeys(map, keys); for (int i = 0; i < keys.length; i++) { - T retVal = map.compute(keys[i], mappingFunction); + Object retVal = map.compute(keys[i], mappingFunction); if (i % 3 != 2) { // key present, func returned null, should be absent from map - check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == null); - check(String.format("compute: get(%s[%d])", keys_desc, i), null == map.get(keys[i])); - check(String.format("compute: containsKey(%s[%d])", keys_desc, i), !map.containsKey(keys[i])); - check(String.format("compute: containsValue(%s[%s])", keys_desc, i), !map.containsValue(keys[i])); + assertNull(retVal, + String.format("compute: retVal(%s[%d])", desc, i)); + assertNull(map.get(keys[i]), + String.format("compute: get(%s[%d])", desc, i)); + assertFalse(map.containsKey(keys[i]), + String.format("compute: containsKey(%s[%d])", desc, i)); + assertFalse(map.containsValue(keys[i]), + String.format("compute: containsValue(%s[%s])", desc, i)); } else { // odd: was removed, should now be mapped to EXTRA - check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == extraVal); - check(String.format("compute: get(%s[%d])", keys_desc, i), extraVal == map.get(keys[i])); - check(String.format("compute: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i])); + assertEquals(retVal, val, + String.format("compute: retVal(%s[%d])", desc, i)); + assertEquals(val, map.get(keys[i]), + String.format("compute: get(%s[%d])", desc, i)); + assertTrue(map.containsKey(keys[i]), + String.format("compute: containsKey(%s[%d])", desc, i)); expectedSize++; } } - check(String.format("compute: containsValue(%s[%s])", keys_desc, extraVal.toString()), map.containsValue(extraVal)); - check(String.format("map expected size#1 m%d != k%d", map.size(), expectedSize), - map.size() == expectedSize); + assertTrue(map.containsValue(val), + String.format("compute: containsValue(%s[%s])", desc, val)); + assertEquals(map.size(), expectedSize, + String.format("map expected size#1 m%d != k%d", map.size(), expectedSize)); } - private static <T> void testMergeNonNull(Map<T, T> map, String keys_desc, T[] keys) { + @Test(dataProvider = "hashMapsWithObjects") + void testMergeNonNull(String desc, Supplier<Map<IntKey, IntKey>> ms, IntKey val) { // remove a third of the keys // call merge() for all keys[] // all keys should be present: removed keys now -> EXTRA, other keys -> k-1 + Map<IntKey, IntKey> map = ms.get(); + IntKey[] keys = map.keySet().stream().sorted().toArray(IntKey[]::new); // Map to preceding key - BiFunction<T,T,T> mappingFunction = (k, v) -> keys[Integer.parseInt(k.toString()) - 1]; - T extraVal = getExtraVal(keys[0]); + BiFunction<IntKey, IntKey, IntKey> mappingFunction + = (k, v) -> keys[k.getValue() - 1]; removeThirdKeys(map, keys); for (int i = 1; i < keys.length; i++) { - T retVal = map.merge(keys[i], extraVal, mappingFunction); + IntKey retVal = map.merge(keys[i], val, mappingFunction); if (i % 3 != 2) { // key present, should be mapped to k-1 - check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == keys[i-1]); - check(String.format("compute: get(%s[%d])", keys_desc, i), keys[i-1] == map.get(keys[i])); + assertEquals(retVal, keys[i - 1], + String.format("compute: retVal(%s[%d])", desc, i)); + assertEquals(keys[i - 1], map.get(keys[i]), + String.format("compute: get(%s[%d])", desc, i)); } else { // odd: was removed, should be replaced with EXTRA - check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == extraVal); - check(String.format("compute: get(%s[%d])", keys_desc, i), extraVal == map.get(keys[i])); + assertEquals(retVal, val, + String.format("compute: retVal(%s[%d])", desc, i)); + assertEquals(val, map.get(keys[i]), + String.format("compute: get(%s[%d])", desc, i)); } - check(String.format("compute: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i])); + assertTrue(map.containsKey(keys[i]), + String.format("compute: containsKey(%s[%d])", desc, i)); } - check(String.format("map expected size#1 m%d != k%d", map.size(), keys.length), - map.size() == keys.length); - check(String.format("compute: containsValue(%s[%s])", keys_desc, extraVal.toString()), map.containsValue(extraVal)); - check(String.format("compute: !containsValue(%s,[null])", keys_desc), !map.containsValue(null)); - + assertEquals(map.size(), keys.length, + String.format("map expected size#1 m%d != k%d", map.size(), keys.length)); + assertTrue(map.containsValue(val), + String.format("compute: containsValue(%s[%s])", desc, val)); + assertFalse(map.containsValue(null), + String.format("compute: !containsValue(%s,[null])", desc)); } - private static <T> void testMergeNull(Map<T, T> map, String keys_desc, T[] keys) { + @Test(dataProvider = "mapsWithObjectsAndStrings") + void testMergeNull(String desc, Supplier<Map<Object, Object>> ms, Object val) { // remove a third of the keys // call merge() for all keys[] // result: removed keys -> EXTRA, other keys absent - BiFunction<T,T,T> mappingFunction = (k, v) -> null; - T extraVal = getExtraVal(keys[0]); + Map<Object, Object> map = ms.get(); + Object[] keys = map.keySet().toArray(); + BiFunction<Object, Object, Object> mappingFunction = (k, v) -> null; int expectedSize = 0; removeThirdKeys(map, keys); for (int i = 0; i < keys.length; i++) { - T retVal = map.merge(keys[i], extraVal, mappingFunction); + Object retVal = map.merge(keys[i], val, mappingFunction); if (i % 3 != 2) { // key present, func returned null, should be absent from map - check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == null); - check(String.format("compute: get(%s[%d])", keys_desc, i), null == map.get(keys[i])); - check(String.format("compute: containsKey(%s[%d])", keys_desc, i), !map.containsKey(keys[i])); + assertNull(retVal, + String.format("compute: retVal(%s[%d])", desc, i)); + assertNull(map.get(keys[i]), + String.format("compute: get(%s[%d])", desc, i)); + assertFalse(map.containsKey(keys[i]), + String.format("compute: containsKey(%s[%d])", desc, i)); } else { // odd: was removed, should now be mapped to EXTRA - check(String.format("compute: retVal(%s[%d])", keys_desc, i), retVal == extraVal); - check(String.format("compute: get(%s[%d])", keys_desc, i), extraVal == map.get(keys[i])); - check(String.format("compute: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i])); + assertEquals(retVal, val, + String.format("compute: retVal(%s[%d])", desc, i)); + assertEquals(val, map.get(keys[i]), + String.format("compute: get(%s[%d])", desc, i)); + assertTrue(map.containsKey(keys[i]), + String.format("compute: containsKey(%s[%d])", desc, i)); expectedSize++; } - check(String.format("compute: containsValue(%s[%s])", keys_desc, i), !map.containsValue(keys[i])); + assertFalse(map.containsValue(keys[i]), + String.format("compute: containsValue(%s[%s])", desc, i)); } - check(String.format("compute: containsValue(%s[%s])", keys_desc, extraVal.toString()), map.containsValue(extraVal)); - check(String.format("map expected size#1 m%d != k%d", map.size(), expectedSize), - map.size() == expectedSize); - } - - /* - * Return the EXTRA val for the key type being used - */ - private static <T> T getExtraVal(T key) { - if (key instanceof HashableInteger) { - return (T)EXTRA_INT_VAL; - } else { - return (T)EXTRA_STRING_VAL; - } + assertTrue(map.containsValue(val), + String.format("compute: containsValue(%s[%s])", desc, val)); + assertEquals(map.size(), expectedSize, + String.format("map expected size#1 m%d != k%d", map.size(), expectedSize)); } /* @@ -551,8 +462,8 @@ removes++; } } - check(String.format("map expected size m%d != k%d", map.size(), keys.length - removes), - map.size() == keys.length - removes); + assertEquals(map.size(), keys.length - removes, + String.format("map expected size m%d != k%d", map.size(), keys.length - removes)); } /* @@ -570,95 +481,19 @@ removes++; } } - check(String.format("map expected size m%d != k%d", map.size(), keys.length - removes), - map.size() == keys.length - removes); + assertEquals(map.size(), keys.length - removes, + String.format("map expected size m%d != k%d", map.size(), keys.length - removes)); } /* * Re-map the odd-numbered keys to map to the EXTRA value */ - private static <T> void remapOddKeys(Map<T, T> map, /*String keys_desc, */ T[] keys) { - T extraVal = getExtraVal(keys[0]); + private static <T> void remapOddKeys(Map<T, T> map, T[] keys, T val) { for (int i = 0; i < keys.length; i++) { if (i % 2 != 0) { - map.put(keys[i], extraVal); + map.put(keys[i], val); } } } - //--------------------- Infrastructure --------------------------- - static volatile int passed = 0, failed = 0; - - static void pass() { - passed++; - } - - static void fail() { - failed++; - (new Error("Failure")).printStackTrace(System.err); - } - - static void fail(String msg) { - failed++; - (new Error("Failure: " + msg)).printStackTrace(System.err); - } - - static void abort() { - fail(); - System.exit(1); - } - - static void abort(String msg) { - fail(msg); - System.exit(1); - } - - static void unexpected(String msg, Throwable t) { - System.err.println("Unexpected: " + msg); - unexpected(t); - } - - static void unexpected(Throwable t) { - failed++; - t.printStackTrace(System.err); - } - - static void check(boolean cond) { - if (cond) { - pass(); - } else { - fail(); - } - } - - static void check(String desc, boolean cond) { - if (cond) { - pass(); - } else { - fail(desc); - } - } - - static void equal(Object x, Object y) { - if (Objects.equals(x, y)) { - pass(); - } else { - fail(x + " not equal to " + y); - } - } - - public static void main(String[] args) throws Throwable { - Thread.currentThread().setName(Collisions.class.getName()); -// Thread.currentThread().setPriority(Thread.MAX_PRIORITY); - try { - realMain(args); - } catch (Throwable t) { - unexpected(t); - } - - System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); - if (failed > 0) { - throw new Error("Some tests failed"); - } - } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/jdk/test/java/util/Map/MapWithCollisionsProviders.java Tue Dec 13 09:55:38 2016 +0800 @@ -0,0 +1,286 @@ +/* + * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ + +import java.util.ArrayList; +import java.util.Collection; +import java.util.HashMap; +import java.util.Hashtable; +import java.util.IdentityHashMap; +import java.util.Iterator; +import java.util.LinkedHashMap; +import java.util.Map; +import java.util.TreeMap; +import java.util.WeakHashMap; +import java.util.concurrent.ConcurrentHashMap; +import java.util.concurrent.ConcurrentSkipListMap; +import java.util.function.Supplier; + +import org.testng.annotations.DataProvider; +import static org.testng.Assert.assertTrue; +import static org.testng.Assert.assertEquals; + +public class MapWithCollisionsProviders { + + private static final int TEST_SIZE + = Boolean.valueOf(System.getProperty("test.map.collisions.shortrun")) + ? 2500 + : 5000; + + private static final IntKey EXTRA_INTKEY_VAL + = new IntKey(TEST_SIZE, Integer.MAX_VALUE); + + private static final String EXTRA_STRING_VAL = "Extra Value"; + + public static final class IntKey implements Comparable<IntKey> { + + private final int value; + private final int hashmask; //yes duplication + + IntKey(int value, int hashmask) { + this.value = value; + this.hashmask = hashmask; + } + + @Override + public boolean equals(Object obj) { + if (obj instanceof IntKey) { + IntKey other = (IntKey) obj; + + return other.value == value; + } + + return false; + } + + @Override + public int hashCode() { + return value % hashmask; + } + + @Override + public int compareTo(IntKey o) { + return value - o.value; + } + + @Override + public String toString() { + return Integer.toString(value); + } + + public int getValue() { + return value; + } + } + + private static Object[] createUniqueObjectKeys() { + IntKey UNIQUE_OBJECTS[] = new IntKey[TEST_SIZE]; + for (int i = 0; i < TEST_SIZE; i++) { + UNIQUE_OBJECTS[i] = new IntKey(i, Integer.MAX_VALUE); + } + return UNIQUE_OBJECTS; + } + + private static Object[] createUniqueStringKeys() { + String UNIQUE_STRINGS[] = new String[TEST_SIZE]; + for (int i = 0; i < TEST_SIZE; i++) { + UNIQUE_STRINGS[i] = unhash(i); + } + return UNIQUE_STRINGS; + } + + private static Object[] createCollidingObjectKeys() { + IntKey COLLIDING_OBJECTS[] = new IntKey[TEST_SIZE]; + for (int i = 0; i < TEST_SIZE; i++) { + COLLIDING_OBJECTS[i] = new IntKey(i, 10); + } + return COLLIDING_OBJECTS; + } + + private static Object[] createCollidingStringKeys() { + String COLLIDING_STRINGS[] = new String[TEST_SIZE]; + String UNIQUE_STRINGS[] = new String[TEST_SIZE]; + for (int i = 0; i < TEST_SIZE; i++) { + UNIQUE_STRINGS[i] = unhash(i); + COLLIDING_STRINGS[i] = (0 == i % 2) + ? UNIQUE_STRINGS[i / 2] + : "\u0000\u0000\u0000\u0000\u0000" + COLLIDING_STRINGS[i - 1]; + } + return COLLIDING_STRINGS; + } + + /** + * Returns a string with a hash equal to the argument. + * + * @return string with a hash equal to the argument. + */ + private static String unhash(int target) { + StringBuilder answer = new StringBuilder(); + if (target < 0) { + // String with hash of Integer.MIN_VALUE, 0x80000000 + answer.append("\\u0915\\u0009\\u001e\\u000c\\u0002"); + + if (target == Integer.MIN_VALUE) { + return answer.toString(); + } + // Find target without sign bit set + target = target & Integer.MAX_VALUE; + } + + unhash0(answer, target); + return answer.toString(); + } + + private static void unhash0(StringBuilder partial, int target) { + int div = target / 31; + int rem = target % 31; + + if (div <= Character.MAX_VALUE) { + if (div != 0) { + partial.append((char) div); + } + partial.append((char) rem); + } else { + unhash0(partial, div); + partial.append((char) rem); + } + } + + private static <T> Map<T, T> fillMap(Map<T, T> m, T[] keys) { + for (T k : keys) { + m.put(k, k); + assertTrue(m.containsKey(k)); + assertTrue(m.containsValue(k)); + } + assertEquals(m.size(), keys.length); + return m; + } + + private static <T> Supplier<Map<T, T>> createMap(Map<T, T> m, T[] keys) { + return () -> fillMap(m, keys); + } + + private static <T> Object[] createCase(String desc, Map<T, T> m, T[] keys, T val) { + return new Object[]{desc, createMap(m, keys), val}; + } + + private static <T> Collection<Object[]> makeMapsMoreTypes(String desc, + T[] keys, + T val) { + Collection<Object[]> cases = new ArrayList<>(); + cases.add(createCase("Hashtable with " + desc, + new Hashtable<>(), keys, val)); + cases.add(createCase("IdentityHashMap with " + desc, + new IdentityHashMap<>(), keys, val)); + cases.add(createCase("TreeMap with " + desc, + new TreeMap<>(), keys, val)); + cases.add(createCase("WeakHashMap with " + desc, + new WeakHashMap<>(), keys, val)); + cases.add(createCase("ConcurrentHashMap with " + desc, + new ConcurrentHashMap<>(), keys, val)); + cases.add(createCase("ConcurrentSkipListMap with " + desc, + new ConcurrentSkipListMap<>(), keys, val)); + return cases; + } + + private static <T> Collection<Object[]> makeMapsHashMap(String desc, + T[] keys, + T val) { + Collection<Object[]> cases = new ArrayList<>(); + cases.add(createCase("HashMap with " + desc, + new HashMap<>(), keys, val)); + cases.add(createCase("LinkedHashMap with " + desc, + new LinkedHashMap<>(), keys, val)); + return cases; + } + + private static <T> Collection<Object[]> makeMaps(String desc, T[] keys, T val) { + Collection<Object[]> cases = new ArrayList<>(); + cases.addAll(makeMapsHashMap(desc, keys, val)); + cases.addAll(makeMapsMoreTypes(desc, keys, val)); + return cases; + } + + private static <T> Collection<Object[]> makeObjectsCases(String desc, T[] keys) { + return makeMaps(desc, keys, EXTRA_INTKEY_VAL); + } + + private static <T> Collection<Object[]> makeStringsCases(String desc, + T[] keys) { + return makeMaps(desc, keys, EXTRA_STRING_VAL); + } + + private static final Collection<Object[]> mapsWithObjectsCases + = new ArrayList<>() { + { + addAll(makeObjectsCases("unique objects", createUniqueObjectKeys())); + addAll(makeObjectsCases("colliding objects", createCollidingObjectKeys())); + } + }; + + private static final Collection<Object[]> mapsWithStringsCases + = new ArrayList<>() { + { + addAll(makeStringsCases("unique strings", createUniqueStringKeys())); + addAll(makeStringsCases("colliding strings", createCollidingStringKeys())); + } + }; + + private static final Collection<Object[]> mapsWithObjectsAndStringsCases + = new ArrayList<>() { + { + addAll(mapsWithObjectsCases); + addAll(mapsWithStringsCases); + } + }; + + private static final Collection<Object[]> hashMapsWithObjectsCases + = new ArrayList<>() { + { + addAll(makeMapsHashMap("unique objects", + createUniqueObjectKeys(), EXTRA_INTKEY_VAL)); + addAll(makeMapsHashMap("collisions objects", + createCollidingObjectKeys(), EXTRA_INTKEY_VAL)); + } + }; + + @DataProvider + public Iterator<Object[]> mapsWithObjects() { + return mapsWithObjectsCases.iterator(); + } + + @DataProvider + public Iterator<Object[]> mapsWithStrings() { + return mapsWithStringsCases.iterator(); + } + + @DataProvider + public Iterator<Object[]> mapsWithObjectsAndStrings() { + return mapsWithObjectsAndStringsCases.iterator(); + } + + @DataProvider + public Iterator<Object[]> hashMapsWithObjects() { + return hashMapsWithObjectsCases.iterator(); + } + +}