1 /* 2 * Copyright (c) 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 package test.java.util.Map; 25 26 import java.util.ArrayList; 27 import java.util.Collection; 28 import java.util.HashMap; 29 import java.util.Hashtable; 30 import java.util.IdentityHashMap; 31 import java.util.Iterator; 32 import java.util.LinkedHashMap; 33 import java.util.Map; 34 import java.util.TreeMap; 35 import java.util.WeakHashMap; 36 import java.util.concurrent.ConcurrentHashMap; 37 import java.util.concurrent.ConcurrentSkipListMap; 38 import java.util.function.Supplier; 39 40 import org.testng.annotations.DataProvider; 41 import static org.testng.Assert.assertTrue; 42 import static org.testng.Assert.assertEquals; 43 44 public class MapWithCollisionsProviders { 45 46 private static final int TEST_SIZE 47 = Boolean.valueOf(System.getProperty("test.map.collisions.shortrun")) 48 ? 2500 49 : 5000; 50 51 private static final IntKey EXTRA_INTKEY_VAL 52 = new IntKey(TEST_SIZE, Integer.MAX_VALUE); 53 54 private static final String EXTRA_STRING_VAL = "Extra Value"; 55 56 public static final class IntKey implements Comparable<IntKey> { 57 58 private final int value; 59 private final int hashmask; //yes duplication 60 IntKey(int value, int hashmask)61 IntKey(int value, int hashmask) { 62 this.value = value; 63 this.hashmask = hashmask; 64 } 65 66 @Override equals(Object obj)67 public boolean equals(Object obj) { 68 if (obj instanceof IntKey) { 69 IntKey other = (IntKey) obj; 70 71 return other.value == value; 72 } 73 74 return false; 75 } 76 77 @Override hashCode()78 public int hashCode() { 79 return value % hashmask; 80 } 81 82 @Override compareTo(IntKey o)83 public int compareTo(IntKey o) { 84 return value - o.value; 85 } 86 87 @Override toString()88 public String toString() { 89 return Integer.toString(value); 90 } 91 getValue()92 public int getValue() { 93 return value; 94 } 95 } 96 createUniqueObjectKeys()97 private static Object[] createUniqueObjectKeys() { 98 IntKey UNIQUE_OBJECTS[] = new IntKey[TEST_SIZE]; 99 for (int i = 0; i < TEST_SIZE; i++) { 100 UNIQUE_OBJECTS[i] = new IntKey(i, Integer.MAX_VALUE); 101 } 102 return UNIQUE_OBJECTS; 103 } 104 createUniqueStringKeys()105 private static Object[] createUniqueStringKeys() { 106 String UNIQUE_STRINGS[] = new String[TEST_SIZE]; 107 for (int i = 0; i < TEST_SIZE; i++) { 108 UNIQUE_STRINGS[i] = unhash(i); 109 } 110 return UNIQUE_STRINGS; 111 } 112 createCollidingObjectKeys()113 private static Object[] createCollidingObjectKeys() { 114 IntKey COLLIDING_OBJECTS[] = new IntKey[TEST_SIZE]; 115 for (int i = 0; i < TEST_SIZE; i++) { 116 COLLIDING_OBJECTS[i] = new IntKey(i, 10); 117 } 118 return COLLIDING_OBJECTS; 119 } 120 createCollidingStringKeys()121 private static Object[] createCollidingStringKeys() { 122 String COLLIDING_STRINGS[] = new String[TEST_SIZE]; 123 String UNIQUE_STRINGS[] = new String[TEST_SIZE]; 124 for (int i = 0; i < TEST_SIZE; i++) { 125 UNIQUE_STRINGS[i] = unhash(i); 126 COLLIDING_STRINGS[i] = (0 == i % 2) 127 ? UNIQUE_STRINGS[i / 2] 128 : "\u0000\u0000\u0000\u0000\u0000" + COLLIDING_STRINGS[i - 1]; 129 } 130 return COLLIDING_STRINGS; 131 } 132 133 /** 134 * Returns a string with a hash equal to the argument. 135 * 136 * @return string with a hash equal to the argument. 137 */ unhash(int target)138 private static String unhash(int target) { 139 StringBuilder answer = new StringBuilder(); 140 if (target < 0) { 141 // String with hash of Integer.MIN_VALUE, 0x80000000 142 answer.append("\\u0915\\u0009\\u001e\\u000c\\u0002"); 143 144 if (target == Integer.MIN_VALUE) { 145 return answer.toString(); 146 } 147 // Find target without sign bit set 148 target = target & Integer.MAX_VALUE; 149 } 150 151 unhash0(answer, target); 152 return answer.toString(); 153 } 154 unhash0(StringBuilder partial, int target)155 private static void unhash0(StringBuilder partial, int target) { 156 int div = target / 31; 157 int rem = target % 31; 158 159 if (div <= Character.MAX_VALUE) { 160 if (div != 0) { 161 partial.append((char) div); 162 } 163 partial.append((char) rem); 164 } else { 165 unhash0(partial, div); 166 partial.append((char) rem); 167 } 168 } 169 fillMap(Map<T, T> m, T[] keys)170 private static <T> Map<T, T> fillMap(Map<T, T> m, T[] keys) { 171 for (T k : keys) { 172 m.put(k, k); 173 assertTrue(m.containsKey(k)); 174 assertTrue(m.containsValue(k)); 175 } 176 assertEquals(m.size(), keys.length); 177 return m; 178 } 179 createMap(Map<T, T> m, T[] keys)180 private static <T> Supplier<Map<T, T>> createMap(Map<T, T> m, T[] keys) { 181 return () -> fillMap(m, keys); 182 } 183 createCase(String desc, Map<T, T> m, T[] keys, T val)184 private static <T> Object[] createCase(String desc, Map<T, T> m, T[] keys, T val) { 185 return new Object[]{desc, createMap(m, keys), val}; 186 } 187 makeMapsMoreTypes(String desc, T[] keys, T val)188 private static <T> Collection<Object[]> makeMapsMoreTypes(String desc, 189 T[] keys, 190 T val) { 191 Collection<Object[]> cases = new ArrayList<>(); 192 cases.add(createCase("Hashtable with " + desc, 193 new Hashtable<>(), keys, val)); 194 cases.add(createCase("IdentityHashMap with " + desc, 195 new IdentityHashMap<>(), keys, val)); 196 cases.add(createCase("TreeMap with " + desc, 197 new TreeMap<>(), keys, val)); 198 cases.add(createCase("WeakHashMap with " + desc, 199 new WeakHashMap<>(), keys, val)); 200 cases.add(createCase("ConcurrentHashMap with " + desc, 201 new ConcurrentHashMap<>(), keys, val)); 202 cases.add(createCase("ConcurrentSkipListMap with " + desc, 203 new ConcurrentSkipListMap<>(), keys, val)); 204 return cases; 205 } 206 makeMapsHashMap(String desc, T[] keys, T val)207 private static <T> Collection<Object[]> makeMapsHashMap(String desc, 208 T[] keys, 209 T val) { 210 Collection<Object[]> cases = new ArrayList<>(); 211 cases.add(createCase("HashMap with " + desc, 212 new HashMap<>(), keys, val)); 213 cases.add(createCase("LinkedHashMap with " + desc, 214 new LinkedHashMap<>(), keys, val)); 215 return cases; 216 } 217 makeMaps(String desc, T[] keys, T val)218 private static <T> Collection<Object[]> makeMaps(String desc, T[] keys, T val) { 219 Collection<Object[]> cases = new ArrayList<>(); 220 cases.addAll(makeMapsHashMap(desc, keys, val)); 221 cases.addAll(makeMapsMoreTypes(desc, keys, val)); 222 return cases; 223 } 224 makeObjectsCases(String desc, T[] keys)225 private static <T> Collection<Object[]> makeObjectsCases(String desc, T[] keys) { 226 return makeMaps(desc, keys, EXTRA_INTKEY_VAL); 227 } 228 makeStringsCases(String desc, T[] keys)229 private static <T> Collection<Object[]> makeStringsCases(String desc, 230 T[] keys) { 231 return makeMaps(desc, keys, EXTRA_STRING_VAL); 232 } 233 234 private static final Collection<Object[]> mapsWithObjectsCases 235 = new ArrayList<>() { 236 { 237 addAll(makeObjectsCases("unique objects", createUniqueObjectKeys())); 238 addAll(makeObjectsCases("colliding objects", createCollidingObjectKeys())); 239 } 240 }; 241 242 private static final Collection<Object[]> mapsWithStringsCases 243 = new ArrayList<>() { 244 { 245 addAll(makeStringsCases("unique strings", createUniqueStringKeys())); 246 addAll(makeStringsCases("colliding strings", createCollidingStringKeys())); 247 } 248 }; 249 250 private static final Collection<Object[]> mapsWithObjectsAndStringsCases 251 = new ArrayList<>() { 252 { 253 addAll(mapsWithObjectsCases); 254 addAll(mapsWithStringsCases); 255 } 256 }; 257 258 private static final Collection<Object[]> hashMapsWithObjectsCases 259 = new ArrayList<>() { 260 { 261 addAll(makeMapsHashMap("unique objects", 262 createUniqueObjectKeys(), EXTRA_INTKEY_VAL)); 263 addAll(makeMapsHashMap("collisions objects", 264 createCollidingObjectKeys(), EXTRA_INTKEY_VAL)); 265 } 266 }; 267 268 @DataProvider mapsWithObjects()269 public Iterator<Object[]> mapsWithObjects() { 270 return mapsWithObjectsCases.iterator(); 271 } 272 273 @DataProvider mapsWithStrings()274 public Iterator<Object[]> mapsWithStrings() { 275 return mapsWithStringsCases.iterator(); 276 } 277 278 @DataProvider mapsWithObjectsAndStrings()279 public Iterator<Object[]> mapsWithObjectsAndStrings() { 280 return mapsWithObjectsAndStringsCases.iterator(); 281 } 282 283 @DataProvider hashMapsWithObjects()284 public Iterator<Object[]> hashMapsWithObjects() { 285 return hashMapsWithObjectsCases.iterator(); 286 } 287 288 }