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