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 /lib/testlibrary/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 SpliteratorDataBuilder(List<Object[]> data, List<T> exp)62 SpliteratorDataBuilder(List<Object[]> data, List<T> exp) { 63 this.data = data; 64 this.exp = exp; 65 this.mExp = createMap(exp); 66 } 67 createMap(List<T> l)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 add(String description, Collection<?> expected, Supplier<Spliterator<?>> s)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 add(String description, Supplier<Spliterator<?>> s)81 void add(String description, Supplier<Spliterator<?>> s) { 82 add(description, exp, s); 83 } 84 addCollection(Function<Collection<T>, ? extends Collection<T>> c)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 addList(Function<Collection<T>, ? extends List<T>> l)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 addMap(Function<Map<T, T>, ? extends Map<T, T>> m)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 joiner(String description)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") spliteratorDataProvider()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") spliteratorNullDataProvider()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 HashableInteger(int value, int hashmask)168 HashableInteger(int value, int hashmask) { 169 this.value = value; 170 this.hashmask = hashmask; 171 } 172 173 @Override equals(Object obj)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 hashCode()185 public int hashCode() { 186 return value % hashmask; 187 } 188 189 @Override compareTo(HashableInteger o)190 public int compareTo(HashableInteger o) { 191 return value - o.value; 192 } 193 194 @Override toString()195 public String toString() { 196 return Integer.toString(value); 197 } 198 } 199 listIntRange(int upTo, boolean withNull)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") testNullPointerException(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)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") testNullPointerExceptionWithNull(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)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") testForEach(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)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") testForEachWithNull(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)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") testTryAdvance(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)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") testTryAdvanceWithNull(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)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") testMixedTryAdvanceForEach(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)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") testMixedTryAdvanceForEachWithNull(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)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") testMixedTraverseAndSplit(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)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") testMixedTraverseAndSplitWithNull(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)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") testSplitAfterFullTraversal(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)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") testSplitAfterFullTraversalWithNull(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)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") testSplitOnce(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)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") testSplitOnceWithNull(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)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") testSplitSixDeep(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)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") testSplitSixDeepWithNull(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)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") testSplitUntilNull(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)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") testSplitUntilNullWithNull(String description, Collection<HashableInteger> exp, Supplier<Spliterator<HashableInteger>> s)336 void testSplitUntilNullWithNull(String description, 337 Collection<HashableInteger> exp, 338 Supplier<Spliterator<HashableInteger>> s) { 339 testSplitUntilNull(exp, s, UnaryOperator.identity()); 340 } 341 342 } 343