| /* |
| * 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 |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| |
| /* |
| * @test |
| * @bug 8005698 |
| * @run testng/othervm -Dtest.map.collisions.shortrun=true InPlaceOpsCollisions |
| * @summary Ensure overrides of in-place operations in Maps behave well with lots of collisions. |
| */ |
| import java.util.Map; |
| import java.util.function.BiFunction; |
| import java.util.function.Function; |
| import java.util.function.Supplier; |
| |
| 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; |
| |
| public class InPlaceOpsCollisions extends MapWithCollisionsProviders { |
| |
| @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 |
| |
| 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)); |
| } |
| assertEquals(map.size(), keys.length, |
| String.format("map expected size m%d != k%d", map.size(), keys.length)); |
| } |
| |
| @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, 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 |
| 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 |
| 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)); |
| } |
| } |
| assertEquals(map.size(), keys.length - removes, |
| String.format("map expected size m%d != k%d", map.size(), keys.length - removes)); |
| } |
| |
| @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 |
| Map<Object, Object> map = ms.get(); |
| Object[] keys = map.keySet().toArray(); |
| boolean replaced; |
| remapOddKeys(map, keys, val); |
| |
| for (int i = 0; i < keys.length; i++) { |
| replaced = map.replace(keys[i], val, keys[i]); |
| if (i % 2 == 0) { // even: original mapping, should not be replaced |
| assertFalse(replaced, |
| String.format("replaceOldValue: retVal(%s[%d])", desc, i)); |
| } else { // odd: new mapping, should be replaced |
| assertTrue(replaced, |
| String.format("replaceOldValue: get(%s[%d])", desc, i)); |
| } |
| 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)); |
| } |
| 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)); |
| } |
| |
| @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 |
| 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++) { |
| Object retVal = map.replace(keys[i], val); |
| if (i % 2 == 0) { // even: still in map, should be replaced |
| 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 |
| 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)); |
| } |
| assertFalse(map.containsValue(keys[i]), |
| String.format("replaceIfMapped: !containsValue(%s[%d])", desc, i)); |
| } |
| 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 desc, T[] keys, |
| Function<T, T> mappingFunction) { |
| // remove a third of the keys |
| // call computeIfAbsent for all keys, func returns EXTRA |
| // check that removed keys now -> EXTRA, other keys -> original val |
| T expectedVal = mappingFunction.apply(keys[0]); |
| T retVal; |
| int expectedSize = 0; |
| removeThirdKeys(map, keys); |
| for (int i = 0; i < keys.length; i++) { |
| retVal = map.computeIfAbsent(keys[i], mappingFunction); |
| if (i % 3 != 2) { // key present, not computed |
| 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 |
| 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 |
| assertTrue(map.containsKey(keys[i]) != (expectedVal == null), |
| String.format("insertion: containsKey(%s[%d])", desc, i)); |
| if (expectedVal != null) { |
| expectedSize++; |
| } |
| } |
| } |
| if (expectedVal != null) { |
| assertTrue(map.containsValue(expectedVal), |
| String.format("computeIfAbsent: containsValue(%s[%s])", desc, expectedVal)); |
| } |
| assertEquals(map.size(), expectedSize, |
| String.format("map expected size m%d != k%d", map.size(), expectedSize)); |
| } |
| |
| @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 |
| // no value from keys[] should be in map |
| T funcResult = mappingFunction.apply(keys[0], keys[0]); |
| int expectedSize1 = 0; |
| removeThirdKeys(map, keys); |
| |
| for (int i = 0; i < keys.length; i++) { |
| T retVal = map.computeIfPresent(keys[i], mappingFunction); |
| if (i % 3 != 2) { // key present |
| if (funcResult == null) { // was removed |
| assertFalse(map.containsKey(keys[i]), |
| String.format("replaceIfMapped: containsKey(%s[%d])", desc, i)); |
| } else { // value was replaced |
| assertTrue(map.containsKey(keys[i]), |
| String.format("replaceIfMapped: containsKey(%s[%d])", desc, i)); |
| expectedSize1++; |
| } |
| 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 |
| 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)); |
| } |
| assertFalse(map.containsValue(keys[i]), |
| String.format("replaceIfMapped: !containsValue(%s[%d])", desc, i)); |
| } |
| assertEquals(map.size(), expectedSize1, |
| String.format("map expected size#1 m%d != k%d", map.size(), expectedSize1)); |
| } |
| |
| @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 |
| 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++) { |
| IntKey retVal = map.compute(keys[i], mappingFunction); |
| if (i % 3 != 2) { // key present, should be mapped to k-1 |
| 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 |
| 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)); |
| } |
| 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)); |
| } |
| |
| @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 |
| 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 val; |
| } else { |
| return null; |
| } |
| }; |
| int expectedSize = 0; |
| removeThirdKeys(map, keys); |
| for (int i = 0; i < keys.length; i++) { |
| Object retVal = map.compute(keys[i], mappingFunction); |
| if (i % 3 != 2) { // key present, func returned null, should be absent from map |
| 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 |
| 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++; |
| } |
| } |
| 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)); |
| } |
| |
| @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<IntKey, IntKey, IntKey> mappingFunction |
| = (k, v) -> keys[k.getValue() - 1]; |
| removeThirdKeys(map, keys); |
| for (int i = 1; i < keys.length; i++) { |
| IntKey retVal = map.merge(keys[i], val, mappingFunction); |
| if (i % 3 != 2) { // key present, should be mapped to k-1 |
| 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 |
| 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)); |
| } |
| |
| 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)); |
| } |
| |
| @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 |
| |
| 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++) { |
| Object retVal = map.merge(keys[i], val, mappingFunction); |
| if (i % 3 != 2) { // key present, func returned null, should be absent from map |
| 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 |
| 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++; |
| } |
| assertFalse(map.containsValue(keys[i]), |
| String.format("compute: containsValue(%s[%s])", desc, i)); |
| } |
| 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)); |
| } |
| |
| /* |
| * Remove half of the keys |
| */ |
| private static <T> void removeOddKeys(Map<T, T> map, /*String keys_desc, */ T[] keys) { |
| int removes = 0; |
| for (int i = 0; i < keys.length; i++) { |
| if (i % 2 != 0) { |
| map.remove(keys[i]); |
| removes++; |
| } |
| } |
| assertEquals(map.size(), keys.length - removes, |
| String.format("map expected size m%d != k%d", map.size(), keys.length - removes)); |
| } |
| |
| /* |
| * Remove every third key |
| * This will hopefully leave some removed keys in TreeBins for, e.g., computeIfAbsent |
| * w/ a func that returns null. |
| * |
| * TODO: consider using this in other tests (and maybe adding a remapThirdKeys) |
| */ |
| private static <T> void removeThirdKeys(Map<T, T> map, /*String keys_desc, */ T[] keys) { |
| int removes = 0; |
| for (int i = 0; i < keys.length; i++) { |
| if (i % 3 == 2) { |
| map.remove(keys[i]); |
| removes++; |
| } |
| } |
| 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, T[] keys, T val) { |
| for (int i = 0; i < keys.length; i++) { |
| if (i % 2 != 0) { |
| map.put(keys[i], val); |
| } |
| } |
| } |
| |
| } |