1 /*
2 * Copyright (c) 2012, 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 7126277
27 * @run main Collisions -shortrun
28 * @run main/othervm -Djdk.map.althashing.threshold=0 Collisions -shortrun
29 * @summary Ensure Maps behave well with lots of hashCode() collisions.
30 * @author Mike Duigou
31 */
32 import java.util.*;
33 import java.util.concurrent.ConcurrentHashMap;
34 import java.util.concurrent.ConcurrentSkipListMap;
35
36 public class Collisions {
37
38 /**
39 * Number of elements per map.
40 */
41 private static final int TEST_SIZE = 5000;
42
43 final static class HashableInteger implements Comparable<HashableInteger> {
44
45 final int value;
46 final int hashmask; //yes duplication
47
48 HashableInteger(int value, int hashmask) {
49 this.value = value;
50 this.hashmask = hashmask;
51 }
52
53 @Override
54 public boolean equals(Object obj) {
55 if (obj instanceof HashableInteger) {
56 HashableInteger other = (HashableInteger) obj;
60
61 return false;
62 }
63
64 @Override
65 public int hashCode() {
66 return value % hashmask;
67 }
68
69 @Override
70 public int compareTo(HashableInteger o) {
71 return value - o.value;
72 }
73
74 @Override
75 public String toString() {
76 return Integer.toString(value);
77 }
78 }
79
80 private static Object[][] makeTestData(int size) {
81 HashableInteger UNIQUE_OBJECTS[] = new HashableInteger[size];
82 HashableInteger COLLIDING_OBJECTS[] = new HashableInteger[size];
83 String UNIQUE_STRINGS[] = new String[size];
84 String COLLIDING_STRINGS[] = new String[size];
85
86 for (int i = 0; i < size; i++) {
87 UNIQUE_OBJECTS[i] = new HashableInteger(i, Integer.MAX_VALUE);
88 COLLIDING_OBJECTS[i] = new HashableInteger(i, 10);
89 UNIQUE_STRINGS[i] = unhash(i);
90 COLLIDING_STRINGS[i] = (0 == i % 2)
91 ? UNIQUE_STRINGS[i / 2]
92 : "\u0000\u0000\u0000\u0000\u0000" + COLLIDING_STRINGS[i - 1];
93 }
94
95 return new Object[][] {
96 new Object[]{"Unique Objects", UNIQUE_OBJECTS},
97 new Object[]{"Colliding Objects", COLLIDING_OBJECTS},
98 new Object[]{"Unique Strings", UNIQUE_STRINGS},
99 new Object[]{"Colliding Strings", COLLIDING_STRINGS}
100 };
101 }
102
103 /**
104 * Returns a string with a hash equal to the argument.
105 *
106 * @return string with a hash equal to the argument.
107 */
108 public static String unhash(int target) {
109 StringBuilder answer = new StringBuilder();
110 if (target < 0) {
111 // String with hash of Integer.MIN_VALUE, 0x80000000
112 answer.append("\\u0915\\u0009\\u001e\\u000c\\u0002");
113
129 if (div <= Character.MAX_VALUE) {
130 if (div != 0) {
131 partial.append((char) div);
132 }
133 partial.append((char) rem);
134 } else {
135 unhash0(partial, div);
136 partial.append((char) rem);
137 }
138 }
139
140 private static void realMain(String[] args) throws Throwable {
141 boolean shortRun = args.length > 0 && args[0].equals("-shortrun");
142
143 Object[][] mapKeys = makeTestData(shortRun ? (TEST_SIZE / 2) : TEST_SIZE);
144
145 // loop through data sets
146 for (Object[] keys_desc : mapKeys) {
147 Map<Object, Object>[] maps = (Map<Object, Object>[]) new Map[]{
148 new HashMap<>(),
149 new Hashtable<>(),
150 new IdentityHashMap<>(),
151 new LinkedHashMap<>(),
152 new TreeMap<>(),
153 new WeakHashMap<>(),
154 new ConcurrentHashMap<>(),
155 new ConcurrentSkipListMap<>()
156 };
157
158 // for each map type.
159 for (Map<Object, Object> map : maps) {
160 String desc = (String) keys_desc[0];
161 Object[] keys = (Object[]) keys_desc[1];
162 try {
163 testMap(map, desc, keys);
164 } catch(Exception all) {
165 unexpected("Failed for " + map.getClass().getName() + " with " + desc, all);
166 }
167 }
168 }
169 }
170
171 private static <T> void testMap(Map<T, T> map, String keys_desc, T[] keys) {
172 System.out.println(map.getClass() + " : " + keys_desc);
173 System.out.flush();
174 testInsertion(map, keys_desc, keys);
175
176 if (keys[0] instanceof HashableInteger) {
177 testIntegerIteration((Map<HashableInteger, HashableInteger>) map, (HashableInteger[]) keys);
178 } else {
179 testStringIteration((Map<String, String>) map, (String[]) keys);
180 }
181
182 testContainsKey(map, keys_desc, keys);
183
184 testRemove(map, keys_desc, keys);
185
186 map.clear();
187 testInsertion(map, keys_desc, keys);
188 testKeysIteratorRemove(map, keys_desc, keys);
189
190 map.clear();
191 testInsertion(map, keys_desc, keys);
192 testValuesIteratorRemove(map, keys_desc, keys);
193
194 map.clear();
195 testInsertion(map, keys_desc, keys);
196 testEntriesIteratorRemove(map, keys_desc, keys);
197
198 check(map.isEmpty());
199 }
200
201 private static <T> void testInsertion(Map<T, T> map, String keys_desc, T[] keys) {
202 check("map empty", (map.size() == 0) && map.isEmpty());
203
204 for (int i = 0; i < keys.length; i++) {
205 check(String.format("insertion: map expected size m%d != i%d", map.size(), i),
206 map.size() == i);
207 check(String.format("insertion: put(%s[%d])", keys_desc, i), null == map.put(keys[i], keys[i]));
208 check(String.format("insertion: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
209 check(String.format("insertion: containsValue(%s[%d])", keys_desc, i), map.containsValue(keys[i]));
210 }
211
212 check(String.format("map expected size m%d != k%d", map.size(), keys.length),
213 map.size() == keys.length);
214 }
215
216 private static void testIntegerIteration(Map<HashableInteger, HashableInteger> map, HashableInteger[] keys) {
217 check(String.format("map expected size m%d != k%d", map.size(), keys.length),
218 map.size() == keys.length);
219
220 BitSet all = new BitSet(keys.length);
221 for (Map.Entry<HashableInteger, HashableInteger> each : map.entrySet()) {
222 check("Iteration: key already seen", !all.get(each.getKey().value));
223 all.set(each.getKey().value);
224 }
225
226 all.flip(0, keys.length);
227 check("Iteration: some keys not visited", all.isEmpty());
228
229 for (HashableInteger each : map.keySet()) {
230 check("Iteration: key already seen", !all.get(each.value));
231 all.set(each.value);
232 }
233
234 all.flip(0, keys.length);
235 check("Iteration: some keys not visited", all.isEmpty());
236
237 int count = 0;
238 for (HashableInteger each : map.values()) {
239 count++;
240 }
241
242 check(String.format("Iteration: value count matches size m%d != c%d", map.size(), count),
243 map.size() == count);
244 }
245
246 private static void testStringIteration(Map<String, String> map, String[] keys) {
247 check(String.format("map expected size m%d != k%d", map.size(), keys.length),
248 map.size() == keys.length);
249
250 BitSet all = new BitSet(keys.length);
251 for (Map.Entry<String, String> each : map.entrySet()) {
252 String key = each.getKey();
253 boolean longKey = key.length() > 5;
254 int index = key.hashCode() + (longKey ? keys.length / 2 : 0);
255 check("key already seen", !all.get(index));
256 all.set(index);
257 }
258
259 all.flip(0, keys.length);
260 check("some keys not visited", all.isEmpty());
261
262 for (String each : map.keySet()) {
263 boolean longKey = each.length() > 5;
264 int index = each.hashCode() + (longKey ? keys.length / 2 : 0);
265 check("key already seen", !all.get(index));
266 all.set(index);
267 }
268
269 all.flip(0, keys.length);
270 check("some keys not visited", all.isEmpty());
271
272 int count = 0;
273 for (String each : map.values()) {
274 count++;
275 }
276
277 check(String.format("value count matches size m%d != k%d", map.size(), keys.length),
278 map.size() == keys.length);
279 }
280
281 private static <T> void testContainsKey(Map<T, T> map, String keys_desc, T[] keys) {
282 for (int i = 0; i < keys.length; i++) {
283 T each = keys[i];
284 check("containsKey: " + keys_desc + "[" + i + "]" + each, map.containsKey(each));
285 }
286 }
287
288 private static <T> void testRemove(Map<T, T> map, String keys_desc, T[] keys) {
289 check(String.format("remove: map expected size m%d != k%d", map.size(), keys.length),
290 map.size() == keys.length);
291
292 for (int i = 0; i < keys.length; i++) {
293 T each = keys[i];
294 check("remove: " + keys_desc + "[" + i + "]" + each, null != map.remove(each));
295 }
296
297 check(String.format("remove: map empty. size=%d", map.size()),
298 (map.size() == 0) && map.isEmpty());
299 }
300
301 private static <T> void testKeysIteratorRemove(Map<T, T> map, String keys_desc, T[] keys) {
302 check(String.format("remove: map expected size m%d != k%d", map.size(), keys.length),
303 map.size() == keys.length);
304
305 Iterator<T> each = map.keySet().iterator();
306 while (each.hasNext()) {
307 T t = each.next();
308 each.remove();
309 check("not removed: " + each, !map.containsKey(t) );
310 }
311
312 check(String.format("remove: map empty. size=%d", map.size()),
313 (map.size() == 0) && map.isEmpty());
314 }
315
316 private static <T> void testValuesIteratorRemove(Map<T, T> map, String keys_desc, T[] keys) {
317 check(String.format("remove: map expected size m%d != k%d", map.size(), keys.length),
318 map.size() == keys.length);
319
320 Iterator<T> each = map.values().iterator();
321 while (each.hasNext()) {
322 T t = each.next();
323 each.remove();
324 check("not removed: " + each, !map.containsValue(t) );
325 }
326
327 check(String.format("remove: map empty. size=%d", map.size()),
328 (map.size() == 0) && map.isEmpty());
329 }
330
331 private static <T> void testEntriesIteratorRemove(Map<T, T> map, String keys_desc, T[] keys) {
332 check(String.format("remove: map expected size m%d != k%d", map.size(), keys.length),
333 map.size() == keys.length);
334
335 Iterator<Map.Entry<T,T>> each = map.entrySet().iterator();
336 while (each.hasNext()) {
337 Map.Entry<T,T> t = each.next();
338 T key = t.getKey();
339 T value = t.getValue();
340 each.remove();
341 check("not removed: " + each, (map instanceof IdentityHashMap) || !map.entrySet().contains(t) );
342 check("not removed: " + each, !map.containsKey(key) );
343 check("not removed: " + each, !map.containsValue(value));
344 }
345
346 check(String.format("remove: map empty. size=%d", map.size()),
347 (map.size() == 0) && map.isEmpty());
348 }
349
350 //--------------------- Infrastructure ---------------------------
351 static volatile int passed = 0, failed = 0;
352
353 static void pass() {
354 passed++;
355 }
356
357 static void fail() {
358 failed++;
359 (new Error("Failure")).printStackTrace(System.err);
360 }
361
362 static void fail(String msg) {
363 failed++;
364 (new Error("Failure: " + msg)).printStackTrace(System.err);
365 }
366
367 static void abort() {
|
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;
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
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() {
|