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