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