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
24import java.util.ArrayList;
25import java.util.Collection;
26import java.util.HashMap;
27import java.util.Hashtable;
28import java.util.IdentityHashMap;
29import java.util.Iterator;
30import java.util.LinkedHashMap;
31import java.util.Map;
32import java.util.TreeMap;
33import java.util.WeakHashMap;
34import java.util.concurrent.ConcurrentHashMap;
35import java.util.concurrent.ConcurrentSkipListMap;
36import java.util.function.Supplier;
37
38import org.testng.annotations.DataProvider;
39import static org.testng.Assert.assertTrue;
40import static org.testng.Assert.assertEquals;
41
42public 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}
287