1 /*
2 * Copyright (c) 2013, 2017, 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 * @library ../stream/bootlib
28 * @build java.base/java.util.SpliteratorTestHelper
29 * @run testng SpliteratorCollisions
30 * @summary Spliterator traversing and splitting hash maps containing colliding hashes
31 */
32
33 import org.testng.annotations.DataProvider;
34 import org.testng.annotations.Test;
35
36 import java.util.ArrayList;
37 import java.util.Arrays;
38 import java.util.Collection;
39 import java.util.Collections;
40 import java.util.HashMap;
41 import java.util.HashSet;
42 import java.util.LinkedHashMap;
43 import java.util.LinkedHashSet;
44 import java.util.List;
45 import java.util.Map;
46 import java.util.Spliterator;
47 import java.util.SpliteratorTestHelper;
48 import java.util.TreeSet;
49 import java.util.function.Function;
50 import java.util.function.Supplier;
51 import java.util.function.UnaryOperator;
52
53 public class SpliteratorCollisions extends SpliteratorTestHelper {
54
55 private static final List<Integer> SIZES = Arrays.asList(0, 1, 10, 100, 1000);
56
57 private static class SpliteratorDataBuilder<T> {
58 List<Object[]> data;
59 List<T> exp;
60 Map<T, T> mExp;
61
62 SpliteratorDataBuilder(List<Object[]> data, List<T> exp) {
63 this.data = data;
64 this.exp = exp;
65 this.mExp = createMap(exp);
66 }
67
68 Map<T, T> createMap(List<T> l) {
69 Map<T, T> m = new LinkedHashMap<>();
70 for (T t : l) {
71 m.put(t, t);
72 }
73 return m;
74 }
75
76 void add(String description, Collection<?> expected, Supplier<Spliterator<?>> s) {
77 description = joiner(description).toString();
78 data.add(new Object[]{description, expected, s});
79 }
80
81 void add(String description, Supplier<Spliterator<?>> s) {
82 add(description, exp, s);
83 }
84
85 void addCollection(Function<Collection<T>, ? extends Collection<T>> c) {
86 add("new " + c.apply(Collections.<T>emptyList()).getClass().getName() + ".spliterator()",
87 () -> c.apply(exp).spliterator());
88 }
89
90 void addList(Function<Collection<T>, ? extends List<T>> l) {
91 // @@@ If collection is instance of List then add sub-list tests
92 addCollection(l);
93 }
94
95 void addMap(Function<Map<T, T>, ? extends Map<T, T>> m) {
96 String description = "new " + m.apply(Collections.<T, T>emptyMap()).getClass().getName();
97 add(description + ".keySet().spliterator()", () -> m.apply(mExp).keySet().spliterator());
98 add(description + ".values().spliterator()", () -> m.apply(mExp).values().spliterator());
99 add(description + ".entrySet().spliterator()", mExp.entrySet(), () -> m.apply(mExp).entrySet().spliterator());
100 }
101
102 StringBuilder joiner(String description) {
103 return new StringBuilder(description).
104 append(" {").
105 append("size=").append(exp.size()).
106 append("}");
107 }
108 }
109
110 static Object[][] spliteratorDataProvider;
111
112 @DataProvider(name = "HashableIntSpliterator")
113 public static Object[][] spliteratorDataProvider() {
114 if (spliteratorDataProvider != null) {
115 return spliteratorDataProvider;
116 }
117
118 List<Object[]> data = new ArrayList<>();
119 for (int size : SIZES) {
120 List<HashableInteger> exp = listIntRange(size, false);
121 SpliteratorDataBuilder<HashableInteger> db = new SpliteratorDataBuilder<>(data, exp);
122
123 // Maps
124 db.addMap(HashMap::new);
125 db.addMap(LinkedHashMap::new);
126
127 // Collections that use HashMap
128 db.addCollection(HashSet::new);
129 db.addCollection(LinkedHashSet::new);
130 db.addCollection(TreeSet::new);
131 }
132 return spliteratorDataProvider = data.toArray(new Object[0][]);
133 }
134
135 static Object[][] spliteratorDataProviderWithNull;
136
137 @DataProvider(name = "HashableIntSpliteratorWithNull")
138 public static Object[][] spliteratorNullDataProvider() {
139 if (spliteratorDataProviderWithNull != null) {
140 return spliteratorDataProviderWithNull;
141 }
142
143 List<Object[]> data = new ArrayList<>();
144 for (int size : SIZES) {
145 List<HashableInteger> exp = listIntRange(size, true);
146 SpliteratorDataBuilder<HashableInteger> db = new SpliteratorDataBuilder<>(data, exp);
147
148 // Maps
149 db.addMap(HashMap::new);
150 db.addMap(LinkedHashMap::new);
151 // TODO: add this back in if we decide to keep TreeBin in WeakHashMap
152 //db.addMap(WeakHashMap::new);
153
154 // Collections that use HashMap
155 db.addCollection(HashSet::new);
156 db.addCollection(LinkedHashSet::new);
157 // db.addCollection(TreeSet::new);
158
159 }
160 return spliteratorDataProviderWithNull = data.toArray(new Object[0][]);
161 }
162
163 static final class HashableInteger implements Comparable<HashableInteger> {
164
165 final int value;
166 final int hashmask; //yes duplication
167
168 HashableInteger(int value, int hashmask) {
169 this.value = value;
170 this.hashmask = hashmask;
171 }
172
173 @Override
174 public boolean equals(Object obj) {
175 if (obj instanceof HashableInteger) {
176 HashableInteger other = (HashableInteger) obj;
177
178 return other.value == value;
179 }
180
181 return false;
182 }
183
184 @Override
185 public int hashCode() {
186 return value % hashmask;
187 }
188
189 @Override
190 public int compareTo(HashableInteger o) {
191 return value - o.value;
192 }
193
194 @Override
195 public String toString() {
196 return Integer.toString(value);
197 }
198 }
199
200 private static List<HashableInteger> listIntRange(int upTo, boolean withNull) {
201 List<HashableInteger> exp = new ArrayList<>();
202 if (withNull) {
203 exp.add(null);
204 }
205 for (int i = 0; i < upTo; i++) {
206 exp.add(new HashableInteger(i, 10));
207 }
208 return Collections.unmodifiableList(exp);
209 }
210
211 @Test(dataProvider = "HashableIntSpliterator")
212 void testNullPointerException(String description,
213 Collection<HashableInteger> exp,
214 Supplier<Spliterator<HashableInteger>> s) {
215 assertThrowsNPE(() -> s.get().forEachRemaining(null));
216 assertThrowsNPE(() -> s.get().tryAdvance(null));
217 }
218
219 @Test(dataProvider = "HashableIntSpliteratorWithNull")
220 void testNullPointerExceptionWithNull(String description,
221 Collection<HashableInteger> exp,
222 Supplier<Spliterator<HashableInteger>> s) {
223 assertThrowsNPE(() -> s.get().forEachRemaining(null));
224 assertThrowsNPE(() -> s.get().tryAdvance(null));
225 }
226
227
228 @Test(dataProvider = "HashableIntSpliterator")
229 void testForEach(String description,
230 Collection<HashableInteger> exp,
231 Supplier<Spliterator<HashableInteger>> s) {
232 testForEach(exp, s, UnaryOperator.identity());
233 }
234
235 @Test(dataProvider = "HashableIntSpliteratorWithNull")
236 void testForEachWithNull(String description,
237 Collection<HashableInteger> exp,
238 Supplier<Spliterator<HashableInteger>> s) {
239 testForEach(exp, s, UnaryOperator.identity());
240 }
241
242
243 @Test(dataProvider = "HashableIntSpliterator")
244 void testTryAdvance(String description,
245 Collection<HashableInteger> exp,
246 Supplier<Spliterator<HashableInteger>> s) {
247 testTryAdvance(exp, s, UnaryOperator.identity());
248 }
249
250 @Test(dataProvider = "HashableIntSpliteratorWithNull")
251 void testTryAdvanceWithNull(String description,
252 Collection<HashableInteger> exp,
253 Supplier<Spliterator<HashableInteger>> s) {
254 testTryAdvance(exp, s, UnaryOperator.identity());
255 }
256
257 @Test(dataProvider = "HashableIntSpliterator")
258 void testMixedTryAdvanceForEach(String description,
259 Collection<HashableInteger> exp,
260 Supplier<Spliterator<HashableInteger>> s) {
261 testMixedTryAdvanceForEach(exp, s, UnaryOperator.identity());
262 }
263
264 @Test(dataProvider = "HashableIntSpliteratorWithNull")
265 void testMixedTryAdvanceForEachWithNull(String description,
266 Collection<HashableInteger> exp,
267 Supplier<Spliterator<HashableInteger>> s) {
268 testMixedTryAdvanceForEach(exp, s, UnaryOperator.identity());
269 }
270
271 @Test(dataProvider = "HashableIntSpliterator")
272 void testMixedTraverseAndSplit(String description,
273 Collection<HashableInteger> exp,
274 Supplier<Spliterator<HashableInteger>> s) {
275 testMixedTraverseAndSplit(exp, s, UnaryOperator.identity());
276 }
277
278 @Test(dataProvider = "HashableIntSpliteratorWithNull")
279 void testMixedTraverseAndSplitWithNull(String description,
280 Collection<HashableInteger> exp,
281 Supplier<Spliterator<HashableInteger>> s) {
282 testMixedTraverseAndSplit(exp, s, UnaryOperator.identity());
283 }
284
285 @Test(dataProvider = "HashableIntSpliterator")
286 void testSplitAfterFullTraversal(String description,
287 Collection<HashableInteger> exp,
288 Supplier<Spliterator<HashableInteger>> s) {
289 testSplitAfterFullTraversal(s, UnaryOperator.identity());
290 }
291
292 @Test(dataProvider = "HashableIntSpliteratorWithNull")
293 void testSplitAfterFullTraversalWithNull(String description,
294 Collection<HashableInteger> exp,
295 Supplier<Spliterator<HashableInteger>> s) {
296 testSplitAfterFullTraversal(s, UnaryOperator.identity());
297 }
298
299
300 @Test(dataProvider = "HashableIntSpliterator")
301 void testSplitOnce(String description,
302 Collection<HashableInteger> exp,
303 Supplier<Spliterator<HashableInteger>> s) {
304 testSplitOnce(exp, s, UnaryOperator.identity());
305 }
306
307 @Test(dataProvider = "HashableIntSpliteratorWithNull")
308 void testSplitOnceWithNull(String description,
309 Collection<HashableInteger> exp,
310 Supplier<Spliterator<HashableInteger>> s) {
311 testSplitOnce(exp, s, UnaryOperator.identity());
312 }
313
314 @Test(dataProvider = "HashableIntSpliterator")
315 void testSplitSixDeep(String description,
316 Collection<HashableInteger> exp,
317 Supplier<Spliterator<HashableInteger>> s) {
318 testSplitSixDeep(exp, s, UnaryOperator.identity());
319 }
320
321 @Test(dataProvider = "HashableIntSpliteratorWithNull")
322 void testSplitSixDeepWithNull(String description,
323 Collection<HashableInteger> exp,
324 Supplier<Spliterator<HashableInteger>> s) {
325 testSplitSixDeep(exp, s, UnaryOperator.identity());
326 }
327
328 @Test(dataProvider = "HashableIntSpliterator")
329 void testSplitUntilNull(String description,
330 Collection<HashableInteger> exp,
331 Supplier<Spliterator<HashableInteger>> s) {
332 testSplitUntilNull(exp, s, UnaryOperator.identity());
333 }
334
335 @Test(dataProvider = "HashableIntSpliteratorWithNull")
336 void testSplitUntilNullWithNull(String description,
337 Collection<HashableInteger> exp,
338 Supplier<Spliterator<HashableInteger>> s) {
339 testSplitUntilNull(exp, s, UnaryOperator.identity());
340 }
341
342 }