1 /*
2 * Copyright (c) 2017, 2018, 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 package jdk.internal.vm.compiler.collections.test;
42
43 import java.util.Arrays;
44 import java.util.Collection;
45 import java.util.Iterator;
46 import java.util.LinkedHashMap;
47 import java.util.Objects;
48 import java.util.Random;
49
50 import jdk.internal.vm.compiler.collections.EconomicMap;
51 import jdk.internal.vm.compiler.collections.Equivalence;
52 import jdk.internal.vm.compiler.collections.MapCursor;
53 import jdk.internal.vm.compiler.collections.UnmodifiableMapCursor;
54 import org.junit.Assert;
55 import org.junit.Test;
56 import org.junit.runner.RunWith;
57 import org.junit.runners.Parameterized;
58 import org.junit.runners.Parameterized.Parameter;
59 import org.junit.runners.Parameterized.Parameters;
60
61 @RunWith(Parameterized.class)
62 public class EconomicMapLargeTest {
63
64 @Parameter(value = 0) public EconomicMap<Object, Object> testMap;
65 @Parameter(value = 1) public EconomicMap<Object, Object> referenceMap;
66 @Parameter(value = 2) public String name;
67
68 @Parameters(name = "{2}")
69 public static Collection<Object[]> data() {
70 return Arrays.asList(new Object[]{EconomicMap.create(Equivalence.DEFAULT), EconomicMap.create(Equivalence.DEFAULT), "EconomicMap"},
71 new Object[]{EconomicMap.create(Equivalence.IDENTITY), EconomicMap.create(Equivalence.IDENTITY), "EconomicMap(IDENTITY)"},
72 new Object[]{EconomicMap.create(Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE), EconomicMap.create(Equivalence.IDENTITY_WITH_SYSTEM_HASHCODE),
73 "EconomicMap(IDENTITY_WITH_SYSTEM_HASHCODE)"},
74 new Object[]{EconomicMap.create(Equivalence.DEFAULT), EconomicMap.wrapMap(new LinkedHashMap<>()), "EconomicMap<->wrapMap"},
75 new Object[]{EconomicMap.wrapMap(new LinkedHashMap<>()), EconomicMap.wrapMap(new LinkedHashMap<>()), "wrapMap"});
76 }
77
78 private static int[] createRandomRange(Random random, int count) {
79 int[] result = new int[count];
80 for (int i = 0; i < count; ++i) {
81 int range = random.nextInt(14);
82 if (range == 0 || range > 10) {
83 range = Integer.MAX_VALUE;
84 } else if (range == 10) {
85 range = 100;
86 }
87 result[i] = range;
88 }
89 return result;
90 }
91
92 private static final class BadHashClass {
93 private int value;
94
95 BadHashClass(int randomInt) {
96 this.value = randomInt;
97 }
98
99 @Override
100 public int hashCode() {
101 return 0;
102 }
103
104 @Override
105 public boolean equals(Object other) {
106 if (other instanceof BadHashClass) {
107 BadHashClass badHashClass = (BadHashClass) other;
108 return badHashClass.value == value;
109 }
110 return false;
111 }
112 }
113
114 interface MapAction {
115 Object perform(EconomicMap<Object, Object> map, int randomInt);
116 }
117
118 static final Object EXISTING_VALUE = new Object();
119
120 static final MapAction[] INCREASE_ACTIONS = new MapAction[]{
121 (map, randomInt) -> map.put(randomInt, "value"),
122 (map, randomInt) -> map.get(randomInt)
123 };
124
125 static final MapAction[] ACTIONS = new MapAction[]{
126 (map, randomInt) -> map.removeKey(randomInt),
127 (map, randomInt) -> map.put(randomInt, "value"),
128 (map, randomInt) -> map.put(randomInt, null),
129 (map, randomInt) -> map.put(EXISTING_VALUE, randomInt),
130 (map, randomInt) -> {
131 if (randomInt == 0) {
132 map.clear();
133 }
134 return map.isEmpty();
135 },
136 (map, randomInt) -> map.containsKey(randomInt),
137 (map, randomInt) -> map.get(randomInt),
138 (map, randomInt) -> map.put(new BadHashClass(randomInt), "unique"),
139 (map, randomInt) -> {
140 if (randomInt == 0) {
141 map.replaceAll((key, value) -> Objects.toString(value) + "!");
142 }
143 return map.isEmpty();
144 }
145
146 };
147
148 @Test
149 public void testVeryLarge() {
150 testMap.clear();
151 referenceMap.clear();
152
153 Random random = new Random(0);
154 for (int i = 0; i < 200000; ++i) {
155 for (int j = 0; j < INCREASE_ACTIONS.length; ++j) {
156 int nextInt = random.nextInt(10000000);
157 MapAction action = INCREASE_ACTIONS[j];
158 Object result = action.perform(testMap, nextInt);
159 Object referenceResult = action.perform(referenceMap, nextInt);
160 Assert.assertEquals(result, referenceResult);
161 }
162 }
163 }
164
165 /**
166 * Tests a sequence of random operations on the map.
167 */
168 @Test
169 public void testAddRemove() {
170 testMap.clear();
171 referenceMap.clear();
172
173 for (int seed = 0; seed < 10; ++seed) {
174 Random random = new Random(seed);
175 int[] ranges = createRandomRange(random, ACTIONS.length);
176 int value = random.nextInt(10000);
177 for (int i = 0; i < value; ++i) {
178 for (int j = 0; j < ACTIONS.length; ++j) {
179 if (random.nextInt(ranges[j]) == 0) {
180 int nextInt = random.nextInt(100);
181 MapAction action = ACTIONS[j];
182 Object result = action.perform(testMap, nextInt);
183 Object referenceResult = action.perform(referenceMap, nextInt);
184 Assert.assertEquals(result, referenceResult);
185 if (j % 100 == 0) {
186 checkEquality(testMap, referenceMap);
187 }
188 }
189 }
190
191 if (random.nextInt(20) == 0) {
192 removeElement(random.nextInt(100), testMap, referenceMap);
193 }
194 }
195 }
196 }
197
198 private static void removeElement(int index, EconomicMap<?, ?> map, EconomicMap<?, ?> referenceMap) {
199 Assert.assertEquals(referenceMap.size(), map.size());
200 MapCursor<?, ?> cursor = map.getEntries();
201 MapCursor<?, ?> referenceCursor = referenceMap.getEntries();
202 int z = 0;
203 while (cursor.advance()) {
204 Assert.assertTrue(referenceCursor.advance());
205 Assert.assertEquals(referenceCursor.getKey(), cursor.getKey());
206 Assert.assertEquals(referenceCursor.getValue(), cursor.getValue());
207 if (index == z) {
208 cursor.remove();
209 referenceCursor.remove();
210 }
211 ++z;
212 }
213
214 Assert.assertFalse(referenceCursor.advance());
215 }
216
217 private static void checkEquality(EconomicMap<?, ?> map, EconomicMap<?, ?> referenceMap) {
218 Assert.assertEquals(referenceMap.size(), map.size());
219
220 // Check entries.
221 UnmodifiableMapCursor<?, ?> cursor = map.getEntries();
222 UnmodifiableMapCursor<?, ?> referenceCursor = referenceMap.getEntries();
223 while (cursor.advance()) {
224 Assert.assertTrue(referenceCursor.advance());
225 Assert.assertEquals(referenceCursor.getKey(), cursor.getKey());
226 Assert.assertEquals(referenceCursor.getValue(), cursor.getValue());
227 }
228
229 // Check keys.
230 Iterator<?> iterator = map.getKeys().iterator();
231 Iterator<?> referenceIterator = referenceMap.getKeys().iterator();
232 while (iterator.hasNext()) {
233 Assert.assertTrue(referenceIterator.hasNext());
234 Assert.assertEquals(iterator.next(), referenceIterator.next());
235 }
236
237 // Check values.
238 iterator = map.getValues().iterator();
239 referenceIterator = referenceMap.getValues().iterator();
240 while (iterator.hasNext()) {
241 Assert.assertTrue(referenceIterator.hasNext());
242 Assert.assertEquals(iterator.next(), referenceIterator.next());
243 }
244 Assert.assertFalse(referenceIterator.hasNext());
245 }
246
247 }