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