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 */
30import java.util.Map;
31import java.util.function.BiFunction;
32import java.util.function.Function;
33import java.util.function.Supplier;
34
35import org.testng.annotations.Test;
36import static org.testng.Assert.assertTrue;
37import static org.testng.Assert.assertFalse;
38import static org.testng.Assert.assertEquals;
39import static org.testng.Assert.assertNull;
40
41public 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}
500