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  * @run main/othervm -Djdk.map.randomseed=true InPlaceOpsCollisions -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 }