1 /* 2 * Copyright (c) 2013, 2016, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24 /* 25 * @test 26 * @bug 8005698 27 * @run testng/othervm -Dtest.map.collisions.shortrun=true InPlaceOpsCollisions 28 * @summary Ensure overrides of in-place operations in Maps behave well with lots of collisions. 29 */ 30 import java.util.Map; 31 import java.util.function.BiFunction; 32 import java.util.function.Function; 33 import java.util.function.Supplier; 34 35 import org.testng.annotations.Test; 36 import static org.testng.Assert.assertTrue; 37 import static org.testng.Assert.assertFalse; 38 import static org.testng.Assert.assertEquals; 39 import static org.testng.Assert.assertNull; 40 41 public class InPlaceOpsCollisions extends MapWithCollisionsProviders { 42 43 @Test(dataProvider = "mapsWithObjectsAndStrings") 44 void testPutIfAbsent(String desc, Supplier<Map<Object, Object>> ms, Object val) { 45 Map<Object, Object> map = ms.get(); 46 Object[] keys = map.keySet().toArray(); 47 Object retVal; 48 removeOddKeys(map, keys); 49 for (int i = 0; i < keys.length; i++) { 50 retVal = map.putIfAbsent(keys[i], val); 51 if (i % 2 == 0) { // even: not absent, not put 52 53 assertEquals(retVal, keys[i], 54 String.format("putIfAbsent: (%s[%d]) retVal", desc, i)); 55 assertEquals(keys[i], map.get(keys[i]), 56 String.format("putIfAbsent: get(%s[%d])", desc, i)); 57 assertTrue(map.containsValue(keys[i]), 58 String.format("putIfAbsent: containsValue(%s[%d])", desc, i)); 59 } else { // odd: absent, was put 60 assertNull(retVal, 61 String.format("putIfAbsent: (%s[%d]) retVal", desc, i)); 62 assertEquals(val, map.get(keys[i]), 63 String.format("putIfAbsent: get(%s[%d])", desc, i)); 64 assertFalse(map.containsValue(keys[i]), 65 String.format("putIfAbsent: !containsValue(%s[%d])", desc, i)); 66 } 67 assertTrue(map.containsKey(keys[i]), 68 String.format("insertion: containsKey(%s[%d])", desc, i)); 69 } 70 assertEquals(map.size(), keys.length, 71 String.format("map expected size m%d != k%d", map.size(), keys.length)); 72 } 73 74 @Test(dataProvider = "mapsWithObjectsAndStrings") 75 void testRemoveMapping(String desc, Supplier<Map<Object, Object>> ms, Object val) { 76 Map<Object, Object> map = ms.get(); 77 Object[] keys = map.keySet().toArray(); 78 boolean removed; 79 int removes = 0; 80 remapOddKeys(map, keys, val); 81 for (int i = 0; i < keys.length; i++) { 82 removed = map.remove(keys[i], keys[i]); 83 if (i % 2 == 0) { // even: original mapping, should be removed 84 assertTrue(removed, 85 String.format("removeMapping: retVal(%s[%d])", desc, i)); 86 assertNull(map.get(keys[i]), 87 String.format("removeMapping: get(%s[%d])", desc, i)); 88 assertFalse(map.containsKey(keys[i]), 89 String.format("removeMapping: !containsKey(%s[%d])", desc, i)); 90 assertFalse(map.containsValue(keys[i]), 91 String.format("removeMapping: !containsValue(%s[%d])", desc, i)); 92 removes++; 93 } else { // odd: new mapping, not removed 94 assertFalse(removed, 95 String.format("removeMapping: retVal(%s[%d])", desc, i)); 96 assertEquals(val, map.get(keys[i]), 97 String.format("removeMapping: get(%s[%d])", desc, i)); 98 assertTrue(map.containsKey(keys[i]), 99 String.format("removeMapping: containsKey(%s[%d])", desc, i)); 100 assertTrue(map.containsValue(val), 101 String.format("removeMapping: containsValue(%s[%d])", desc, i)); 102 } 103 } 104 assertEquals(map.size(), keys.length - removes, 105 String.format("map expected size m%d != k%d", map.size(), keys.length - removes)); 106 } 107 108 @Test(dataProvider = "mapsWithObjectsAndStrings") 109 void testReplaceOldValue(String desc, Supplier<Map<Object, Object>> ms, Object val) { 110 // remap odds to val 111 // call replace to replace for val, for all keys 112 // check that all keys map to value from keys array 113 Map<Object, Object> map = ms.get(); 114 Object[] keys = map.keySet().toArray(); 115 boolean replaced; 116 remapOddKeys(map, keys, val); 117 118 for (int i = 0; i < keys.length; i++) { 119 replaced = map.replace(keys[i], val, keys[i]); 120 if (i % 2 == 0) { // even: original mapping, should not be replaced 121 assertFalse(replaced, 122 String.format("replaceOldValue: retVal(%s[%d])", desc, i)); 123 } else { // odd: new mapping, should be replaced 124 assertTrue(replaced, 125 String.format("replaceOldValue: get(%s[%d])", desc, i)); 126 } 127 assertEquals(keys[i], map.get(keys[i]), 128 String.format("replaceOldValue: get(%s[%d])", desc, i)); 129 assertTrue(map.containsKey(keys[i]), 130 String.format("replaceOldValue: containsKey(%s[%d])", desc, i)); 131 assertTrue(map.containsValue(keys[i]), 132 String.format("replaceOldValue: containsValue(%s[%d])", desc, i)); 133 } 134 assertFalse(map.containsValue(val), 135 String.format("replaceOldValue: !containsValue(%s[%s])", desc, val)); 136 assertEquals(map.size(), keys.length, 137 String.format("map expected size m%d != k%d", map.size(), keys.length)); 138 } 139 140 @Test(dataProvider = "mapsWithObjectsAndStrings") 141 void testReplaceIfMapped(String desc, Supplier<Map<Object, Object>> ms, Object val) { 142 // remove odd keys 143 // call replace for all keys[] 144 // odd keys should remain absent, even keys should be mapped to EXTRA, no value from keys[] should be in map 145 Map<Object, Object> map = ms.get(); 146 Object[] keys = map.keySet().toArray(); 147 int expectedSize1 = 0; 148 removeOddKeys(map, keys); 149 int expectedSize2 = map.size(); 150 151 for (int i = 0; i < keys.length; i++) { 152 Object retVal = map.replace(keys[i], val); 153 if (i % 2 == 0) { // even: still in map, should be replaced 154 assertEquals(retVal, keys[i], 155 String.format("replaceIfMapped: retVal(%s[%d])", desc, i)); 156 assertEquals(val, map.get(keys[i]), 157 String.format("replaceIfMapped: get(%s[%d])", desc, i)); 158 assertTrue(map.containsKey(keys[i]), 159 String.format("replaceIfMapped: containsKey(%s[%d])", desc, i)); 160 expectedSize1++; 161 } else { // odd: was removed, should not be replaced 162 assertNull(retVal, 163 String.format("replaceIfMapped: retVal(%s[%d])", desc, i)); 164 assertNull(map.get(keys[i]), 165 String.format("replaceIfMapped: get(%s[%d])", desc, i)); 166 assertFalse(map.containsKey(keys[i]), 167 String.format("replaceIfMapped: containsKey(%s[%d])", desc, i)); 168 } 169 assertFalse(map.containsValue(keys[i]), 170 String.format("replaceIfMapped: !containsValue(%s[%d])", desc, i)); 171 } 172 assertTrue(map.containsValue(val), 173 String.format("replaceIfMapped: containsValue(%s[%s])", desc, val)); 174 assertEquals(map.size(), expectedSize1, 175 String.format("map expected size#1 m%d != k%d", map.size(), expectedSize1)); 176 assertEquals(map.size(), expectedSize2, 177 String.format("map expected size#2 m%d != k%d", map.size(), expectedSize2)); 178 179 } 180 181 private static <T> void testComputeIfAbsent(Map<T, T> map, String desc, T[] keys, 182 Function<T, T> mappingFunction) { 183 // remove a third of the keys 184 // call computeIfAbsent for all keys, func returns EXTRA 185 // check that removed keys now -> EXTRA, other keys -> original val 186 T expectedVal = mappingFunction.apply(keys[0]); 187 T retVal; 188 int expectedSize = 0; 189 removeThirdKeys(map, keys); 190 for (int i = 0; i < keys.length; i++) { 191 retVal = map.computeIfAbsent(keys[i], mappingFunction); 192 if (i % 3 != 2) { // key present, not computed 193 assertEquals(retVal, keys[i], 194 String.format("computeIfAbsent: (%s[%d]) retVal", desc, i)); 195 assertEquals(keys[i], map.get(keys[i]), 196 String.format("computeIfAbsent: get(%s[%d])", desc, i)); 197 assertTrue(map.containsValue(keys[i]), 198 String.format("computeIfAbsent: containsValue(%s[%d])", desc, i)); 199 assertTrue(map.containsKey(keys[i]), 200 String.format("insertion: containsKey(%s[%d])", desc, i)); 201 expectedSize++; 202 } else { // key absent, computed unless function return null 203 assertEquals(retVal, expectedVal, 204 String.format("computeIfAbsent: (%s[%d]) retVal", desc, i)); 205 assertEquals(expectedVal, map.get(keys[i]), 206 String.format("computeIfAbsent: get(%s[%d])", desc, i)); 207 assertFalse(map.containsValue(keys[i]), 208 String.format("computeIfAbsent: !containsValue(%s[%d])", desc, i)); 209 // mapping should not be added if function returns null 210 assertTrue(map.containsKey(keys[i]) != (expectedVal == null), 211 String.format("insertion: containsKey(%s[%d])", desc, i)); 212 if (expectedVal != null) { 213 expectedSize++; 214 } 215 } 216 } 217 if (expectedVal != null) { 218 assertTrue(map.containsValue(expectedVal), 219 String.format("computeIfAbsent: containsValue(%s[%s])", desc, expectedVal)); 220 } 221 assertEquals(map.size(), expectedSize, 222 String.format("map expected size m%d != k%d", map.size(), expectedSize)); 223 } 224 225 @Test(dataProvider = "mapsWithObjectsAndStrings") 226 void testComputeIfAbsentNonNull(String desc, Supplier<Map<Object, Object>> ms, Object val) { 227 Map<Object, Object> map = ms.get(); 228 Object[] keys = map.keySet().toArray(); 229 testComputeIfAbsent(map, desc, keys, (k) -> val); 230 } 231 232 @Test(dataProvider = "mapsWithObjectsAndStrings") 233 void testComputeIfAbsentNull(String desc, Supplier<Map<Object, Object>> ms, Object val) { 234 Map<Object, Object> map = ms.get(); 235 Object[] keys = map.keySet().toArray(); 236 testComputeIfAbsent(map, desc, keys, (k) -> null); 237 } 238 239 private static <T> void testComputeIfPresent(Map<T, T> map, String desc, T[] keys, 240 BiFunction<T, T, T> mappingFunction) { 241 // remove a third of the keys 242 // call testComputeIfPresent for all keys[] 243 // removed keys should remain absent, even keys should be mapped to $RESULT 244 // no value from keys[] should be in map 245 T funcResult = mappingFunction.apply(keys[0], keys[0]); 246 int expectedSize1 = 0; 247 removeThirdKeys(map, keys); 248 249 for (int i = 0; i < keys.length; i++) { 250 T retVal = map.computeIfPresent(keys[i], mappingFunction); 251 if (i % 3 != 2) { // key present 252 if (funcResult == null) { // was removed 253 assertFalse(map.containsKey(keys[i]), 254 String.format("replaceIfMapped: containsKey(%s[%d])", desc, i)); 255 } else { // value was replaced 256 assertTrue(map.containsKey(keys[i]), 257 String.format("replaceIfMapped: containsKey(%s[%d])", desc, i)); 258 expectedSize1++; 259 } 260 assertEquals(retVal, funcResult, 261 String.format("computeIfPresent: retVal(%s[%s])", desc, i)); 262 assertEquals(funcResult, map.get(keys[i]), 263 String.format("replaceIfMapped: get(%s[%d])", desc, i)); 264 265 } else { // odd: was removed, should not be replaced 266 assertNull(retVal, 267 String.format("replaceIfMapped: retVal(%s[%d])", desc, i)); 268 assertNull(map.get(keys[i]), 269 String.format("replaceIfMapped: get(%s[%d])", desc, i)); 270 assertFalse(map.containsKey(keys[i]), 271 String.format("replaceIfMapped: containsKey(%s[%d])", desc, i)); 272 } 273 assertFalse(map.containsValue(keys[i]), 274 String.format("replaceIfMapped: !containsValue(%s[%d])", desc, i)); 275 } 276 assertEquals(map.size(), expectedSize1, 277 String.format("map expected size#1 m%d != k%d", map.size(), expectedSize1)); 278 } 279 280 @Test(dataProvider = "mapsWithObjectsAndStrings") 281 void testComputeIfPresentNonNull(String desc, Supplier<Map<Object, Object>> ms, Object val) { 282 Map<Object, Object> map = ms.get(); 283 Object[] keys = map.keySet().toArray(); 284 testComputeIfPresent(map, desc, keys, (k, v) -> val); 285 } 286 287 @Test(dataProvider = "mapsWithObjectsAndStrings") 288 void testComputeIfPresentNull(String desc, Supplier<Map<Object, Object>> ms, Object val) { 289 Map<Object, Object> map = ms.get(); 290 Object[] keys = map.keySet().toArray(); 291 testComputeIfPresent(map, desc, keys, (k, v) -> null); 292 } 293 294 @Test(dataProvider = "hashMapsWithObjects") 295 void testComputeNonNull(String desc, Supplier<Map<IntKey, IntKey>> ms, IntKey val) { 296 // remove a third of the keys 297 // call compute() for all keys[] 298 // all keys should be present: removed keys -> EXTRA, others to k-1 299 Map<IntKey, IntKey> map = ms.get(); 300 IntKey[] keys = map.keySet().stream().sorted().toArray(IntKey[]::new); 301 BiFunction<IntKey, IntKey, IntKey> mappingFunction = (k, v) -> { 302 if (v == null) { 303 return val; 304 } else { 305 return keys[k.getValue() - 1]; 306 } 307 }; 308 removeThirdKeys(map, keys); 309 for (int i = 1; i < keys.length; i++) { 310 IntKey retVal = map.compute(keys[i], mappingFunction); 311 if (i % 3 != 2) { // key present, should be mapped to k-1 312 assertEquals(retVal, keys[i - 1], 313 String.format("compute: retVal(%s[%d])", desc, i)); 314 assertEquals(keys[i - 1], map.get(keys[i]), 315 String.format("compute: get(%s[%d])", desc, i)); 316 } else { // odd: was removed, should be replaced with EXTRA 317 assertEquals(retVal, val, 318 String.format("compute: retVal(%s[%d])", desc, i)); 319 assertEquals(val, map.get(keys[i]), 320 String.format("compute: get(%s[%d])", desc, i)); 321 } 322 assertTrue(map.containsKey(keys[i]), 323 String.format("compute: containsKey(%s[%d])", desc, i)); 324 } 325 assertEquals(map.size(), keys.length, 326 String.format("map expected size#1 m%d != k%d", map.size(), keys.length)); 327 assertTrue(map.containsValue(val), 328 String.format("compute: containsValue(%s[%s])", desc, val)); 329 assertFalse(map.containsValue(null), 330 String.format("compute: !containsValue(%s,[null])", desc)); 331 } 332 333 @Test(dataProvider = "mapsWithObjectsAndStrings") 334 void testComputeNull(String desc, Supplier<Map<Object, Object>> ms, Object val) { 335 // remove a third of the keys 336 // call compute() for all keys[] 337 // removed keys should -> EXTRA 338 // for other keys: func returns null, should have no mapping 339 Map<Object, Object> map = ms.get(); 340 Object[] keys = map.keySet().toArray(); 341 BiFunction<Object, Object, Object> mappingFunction = (k, v) -> { 342 // if absent/null -> EXTRA 343 // if present -> null 344 if (v == null) { 345 return val; 346 } else { 347 return null; 348 } 349 }; 350 int expectedSize = 0; 351 removeThirdKeys(map, keys); 352 for (int i = 0; i < keys.length; i++) { 353 Object retVal = map.compute(keys[i], mappingFunction); 354 if (i % 3 != 2) { // key present, func returned null, should be absent from map 355 assertNull(retVal, 356 String.format("compute: retVal(%s[%d])", desc, i)); 357 assertNull(map.get(keys[i]), 358 String.format("compute: get(%s[%d])", desc, i)); 359 assertFalse(map.containsKey(keys[i]), 360 String.format("compute: containsKey(%s[%d])", desc, i)); 361 assertFalse(map.containsValue(keys[i]), 362 String.format("compute: containsValue(%s[%s])", desc, i)); 363 } else { // odd: was removed, should now be mapped to EXTRA 364 assertEquals(retVal, val, 365 String.format("compute: retVal(%s[%d])", desc, i)); 366 assertEquals(val, map.get(keys[i]), 367 String.format("compute: get(%s[%d])", desc, i)); 368 assertTrue(map.containsKey(keys[i]), 369 String.format("compute: containsKey(%s[%d])", desc, i)); 370 expectedSize++; 371 } 372 } 373 assertTrue(map.containsValue(val), 374 String.format("compute: containsValue(%s[%s])", desc, val)); 375 assertEquals(map.size(), expectedSize, 376 String.format("map expected size#1 m%d != k%d", map.size(), expectedSize)); 377 } 378 379 @Test(dataProvider = "hashMapsWithObjects") 380 void testMergeNonNull(String desc, Supplier<Map<IntKey, IntKey>> ms, IntKey val) { 381 // remove a third of the keys 382 // call merge() for all keys[] 383 // all keys should be present: removed keys now -> EXTRA, other keys -> k-1 384 Map<IntKey, IntKey> map = ms.get(); 385 IntKey[] keys = map.keySet().stream().sorted().toArray(IntKey[]::new); 386 387 // Map to preceding key 388 BiFunction<IntKey, IntKey, IntKey> mappingFunction 389 = (k, v) -> keys[k.getValue() - 1]; 390 removeThirdKeys(map, keys); 391 for (int i = 1; i < keys.length; i++) { 392 IntKey retVal = map.merge(keys[i], val, mappingFunction); 393 if (i % 3 != 2) { // key present, should be mapped to k-1 394 assertEquals(retVal, keys[i - 1], 395 String.format("compute: retVal(%s[%d])", desc, i)); 396 assertEquals(keys[i - 1], map.get(keys[i]), 397 String.format("compute: get(%s[%d])", desc, i)); 398 } else { // odd: was removed, should be replaced with EXTRA 399 assertEquals(retVal, val, 400 String.format("compute: retVal(%s[%d])", desc, i)); 401 assertEquals(val, map.get(keys[i]), 402 String.format("compute: get(%s[%d])", desc, i)); 403 } 404 assertTrue(map.containsKey(keys[i]), 405 String.format("compute: containsKey(%s[%d])", desc, i)); 406 } 407 408 assertEquals(map.size(), keys.length, 409 String.format("map expected size#1 m%d != k%d", map.size(), keys.length)); 410 assertTrue(map.containsValue(val), 411 String.format("compute: containsValue(%s[%s])", desc, val)); 412 assertFalse(map.containsValue(null), 413 String.format("compute: !containsValue(%s,[null])", desc)); 414 } 415 416 @Test(dataProvider = "mapsWithObjectsAndStrings") 417 void testMergeNull(String desc, Supplier<Map<Object, Object>> ms, Object val) { 418 // remove a third of the keys 419 // call merge() for all keys[] 420 // result: removed keys -> EXTRA, other keys absent 421 422 Map<Object, Object> map = ms.get(); 423 Object[] keys = map.keySet().toArray(); 424 BiFunction<Object, Object, Object> mappingFunction = (k, v) -> null; 425 int expectedSize = 0; 426 removeThirdKeys(map, keys); 427 for (int i = 0; i < keys.length; i++) { 428 Object retVal = map.merge(keys[i], val, mappingFunction); 429 if (i % 3 != 2) { // key present, func returned null, should be absent from map 430 assertNull(retVal, 431 String.format("compute: retVal(%s[%d])", desc, i)); 432 assertNull(map.get(keys[i]), 433 String.format("compute: get(%s[%d])", desc, i)); 434 assertFalse(map.containsKey(keys[i]), 435 String.format("compute: containsKey(%s[%d])", desc, i)); 436 } else { // odd: was removed, should now be mapped to EXTRA 437 assertEquals(retVal, val, 438 String.format("compute: retVal(%s[%d])", desc, i)); 439 assertEquals(val, map.get(keys[i]), 440 String.format("compute: get(%s[%d])", desc, i)); 441 assertTrue(map.containsKey(keys[i]), 442 String.format("compute: containsKey(%s[%d])", desc, i)); 443 expectedSize++; 444 } 445 assertFalse(map.containsValue(keys[i]), 446 String.format("compute: containsValue(%s[%s])", desc, i)); 447 } 448 assertTrue(map.containsValue(val), 449 String.format("compute: containsValue(%s[%s])", desc, val)); 450 assertEquals(map.size(), expectedSize, 451 String.format("map expected size#1 m%d != k%d", map.size(), expectedSize)); 452 } 453 454 /* 455 * Remove half of the keys 456 */ 457 private static <T> void removeOddKeys(Map<T, T> map, /*String keys_desc, */ T[] keys) { 458 int removes = 0; 459 for (int i = 0; i < keys.length; i++) { 460 if (i % 2 != 0) { 461 map.remove(keys[i]); 462 removes++; 463 } 464 } 465 assertEquals(map.size(), keys.length - removes, 466 String.format("map expected size m%d != k%d", map.size(), keys.length - removes)); 467 } 468 469 /* 470 * Remove every third key 471 * This will hopefully leave some removed keys in TreeBins for, e.g., computeIfAbsent 472 * w/ a func that returns null. 473 * 474 * TODO: consider using this in other tests (and maybe adding a remapThirdKeys) 475 */ 476 private static <T> void removeThirdKeys(Map<T, T> map, /*String keys_desc, */ T[] keys) { 477 int removes = 0; 478 for (int i = 0; i < keys.length; i++) { 479 if (i % 3 == 2) { 480 map.remove(keys[i]); 481 removes++; 482 } 483 } 484 assertEquals(map.size(), keys.length - removes, 485 String.format("map expected size m%d != k%d", map.size(), keys.length - removes)); 486 } 487 488 /* 489 * Re-map the odd-numbered keys to map to the EXTRA value 490 */ 491 private static <T> void remapOddKeys(Map<T, T> map, T[] keys, T val) { 492 for (int i = 0; i < keys.length; i++) { 493 if (i % 2 != 0) { 494 map.put(keys[i], val); 495 } 496 } 497 } 498 499 }