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