| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | |
| 2 // for details. All rights reserved. Use of this source code is governed by a | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 // | |
| 5 // VMOptions= | |
| 6 // VMOptions=--use_internal_hash_map | |
| 7 | |
| 8 // Tests of hash map behavior, with focus in iteration and concurrent | |
| 9 // modification errors. | |
| 10 | |
| 11 library hash_map2_test; | |
| 12 | |
| 13 import "package:expect/expect.dart"; | |
| 14 import 'dart:collection'; | |
| 15 | |
| 16 testMap(Map newMap(), Map newMapFrom(Map map)) { | |
| 17 Map gen(int from, int to) { | |
| 18 Map map = new LinkedHashMap(); | |
| 19 for (int i = from; i < to; i++) map[i] = i; | |
| 20 return map; | |
| 21 } | |
| 22 | |
| 23 bool odd(int n) => (n & 1) == 1; | |
| 24 bool even(int n) => (n & 1) == 0; | |
| 25 void addAll(Map toMap, Map fromMap) { | |
| 26 fromMap.forEach((k, v) { | |
| 27 toMap[k] = v; | |
| 28 }); | |
| 29 } | |
| 30 | |
| 31 { | |
| 32 // Test growing to largish capacity. | |
| 33 Map map = newMap(); | |
| 34 | |
| 35 for (int i = 0; i < 256; i++) { | |
| 36 map[i] = i; | |
| 37 } | |
| 38 addAll(map, gen(256, 512)); | |
| 39 addAll(map, newMapFrom(gen(512, 1000))); | |
| 40 Expect.equals(1000, map.length); | |
| 41 | |
| 42 // Remove half. | |
| 43 for (int i = 0; i < 1000; i += 2) map.remove(i); | |
| 44 Expect.equals(500, map.length); | |
| 45 Expect.isFalse(map.keys.any(even)); | |
| 46 Expect.isTrue(map.keys.every(odd)); | |
| 47 | |
| 48 // Re-add all. | |
| 49 addAll(map, gen(0, 1000)); | |
| 50 Expect.equals(1000, map.length); | |
| 51 } | |
| 52 | |
| 53 { | |
| 54 // Test having many deleted elements. | |
| 55 Map map = newMap(); | |
| 56 map[0] = 0; | |
| 57 for (int i = 0; i < 1000; i++) { | |
| 58 map[i + 1] = i + 1; | |
| 59 map.remove(i); | |
| 60 Expect.equals(1, map.length); | |
| 61 } | |
| 62 } | |
| 63 | |
| 64 { | |
| 65 // Test having many elements with same hashCode | |
| 66 Map map = newMap(); | |
| 67 for (int i = 0; i < 1000; i++) { | |
| 68 map[new BadHashCode()] = 0; | |
| 69 } | |
| 70 Expect.equals(1000, map.length); | |
| 71 } | |
| 72 | |
| 73 { | |
| 74 // Check concurrent modification | |
| 75 Map map = newMap() | |
| 76 ..[0] = 0 | |
| 77 ..[1] = 1; | |
| 78 | |
| 79 { | |
| 80 // Test adding before a moveNext. | |
| 81 Iterator iter = map.keys.iterator; | |
| 82 iter.moveNext(); | |
| 83 map[1] = 9; // Updating existing key isn't a modification. | |
| 84 iter.moveNext(); | |
| 85 map[2] = 2; | |
| 86 Expect.throws(iter.moveNext, (e) => e is Error); | |
| 87 } | |
| 88 | |
| 89 { | |
| 90 // Test adding after last element. | |
| 91 Iterator iter = map.keys.iterator; | |
| 92 Expect.equals(3, map.length); | |
| 93 iter.moveNext(); | |
| 94 iter.moveNext(); | |
| 95 iter.moveNext(); | |
| 96 map[3] = 3; | |
| 97 Expect.throws(iter.moveNext, (e) => e is Error); | |
| 98 } | |
| 99 | |
| 100 { | |
| 101 // Test removing during iteration. | |
| 102 Iterator iter = map.keys.iterator; | |
| 103 iter.moveNext(); | |
| 104 map.remove(1000); // Not a modification if it's not there. | |
| 105 iter.moveNext(); | |
| 106 int n = iter.current; | |
| 107 map.remove(n); | |
| 108 // Removing doesn't change current. | |
| 109 Expect.equals(n, iter.current); | |
| 110 Expect.throws(iter.moveNext, (e) => e is Error); | |
| 111 } | |
| 112 | |
| 113 { | |
| 114 // Test removing after last element. | |
| 115 Iterator iter = map.keys.iterator; | |
| 116 Expect.equals(3, map.length); | |
| 117 iter.moveNext(); | |
| 118 iter.moveNext(); | |
| 119 iter.moveNext(); | |
| 120 int n = iter.current; | |
| 121 map.remove(n); | |
| 122 // Removing doesn't change current. | |
| 123 Expect.equals(n, iter.current); | |
| 124 Expect.throws(iter.moveNext, (e) => e is Error); | |
| 125 } | |
| 126 | |
| 127 { | |
| 128 // Test that updating value of existing key doesn't cause concurrent | |
| 129 // modification error. | |
| 130 Iterator iter = map.keys.iterator; | |
| 131 Expect.equals(2, map.length); | |
| 132 iter.moveNext(); | |
| 133 int n = iter.current; | |
| 134 map[n] = n * 2; | |
| 135 iter.moveNext(); | |
| 136 Expect.equals(map[iter.current], iter.current); | |
| 137 } | |
| 138 | |
| 139 { | |
| 140 // Test that modification during putIfAbsent is not an error. | |
| 141 map.putIfAbsent(4, () { | |
| 142 map[5] = 5; | |
| 143 map[4] = -1; | |
| 144 return 4; | |
| 145 }); | |
| 146 Expect.equals(4, map[4]); | |
| 147 Expect.equals(5, map[5]); | |
| 148 } | |
| 149 | |
| 150 { | |
| 151 // Check adding many existing keys isn't considered modification. | |
| 152 Map map2 = newMap(); | |
| 153 for (var key in map.keys) { | |
| 154 map2[key] = map[key] + 1; | |
| 155 } | |
| 156 Iterator iter = map.keys.iterator; | |
| 157 addAll(map, map2); | |
| 158 // Shouldn't throw. | |
| 159 iter.moveNext(); | |
| 160 } | |
| 161 } | |
| 162 | |
| 163 { | |
| 164 // Regression test for bug in putIfAbsent where adding an element | |
| 165 // that make the table grow, can be lost. | |
| 166 Map map = newMap(); | |
| 167 map.putIfAbsent("S", () => 0); | |
| 168 map.putIfAbsent("T", () => 0); | |
| 169 map.putIfAbsent("U", () => 0); | |
| 170 map.putIfAbsent("C", () => 0); | |
| 171 map.putIfAbsent("a", () => 0); | |
| 172 map.putIfAbsent("b", () => 0); | |
| 173 map.putIfAbsent("n", () => 0); | |
| 174 Expect.isTrue(map.containsKey("n")); | |
| 175 } | |
| 176 | |
| 177 { | |
| 178 // Check that putIfAbsent works just as well as put. | |
| 179 Map map = newMap(); | |
| 180 for (int i = 0; i < 128; i++) { | |
| 181 map.putIfAbsent(i, () => i); | |
| 182 Expect.isTrue(map.containsKey(i)); | |
| 183 map.putIfAbsent(i >> 1, () => -1); // Never triggers. | |
| 184 } | |
| 185 for (int i = 0; i < 128; i++) { | |
| 186 Expect.equals(i, map[i]); | |
| 187 } | |
| 188 } | |
| 189 | |
| 190 { | |
| 191 // Check that updating existing elements is not a modification. | |
| 192 // This must be the case even if the underlying data structure is | |
| 193 // nearly full. | |
| 194 for (int i = 1; i < 128; i++) { | |
| 195 // Create maps of different sizes, some of which should be | |
| 196 // at a limit of the underlying data structure. | |
| 197 Map map = newMapFrom(gen(0, i)); | |
| 198 | |
| 199 // ForEach-iteration. | |
| 200 map.forEach((key, v) { | |
| 201 Expect.equals(key, map[key]); | |
| 202 map[key] = key + 1; | |
| 203 map.remove(1000); // Removing something not there. | |
| 204 map.putIfAbsent(key, () => Expect.fail("SHOULD NOT BE ABSENT")); | |
| 205 // Doesn't cause ConcurrentModificationError. | |
| 206 }); | |
| 207 | |
| 208 // for-in iteration. | |
| 209 for (int key in map.keys) { | |
| 210 Expect.equals(key + 1, map[key]); | |
| 211 map[key] = map[key] + 1; | |
| 212 map.remove(1000); // Removing something not there. | |
| 213 map.putIfAbsent(key, () => Expect.fail("SHOULD NOT BE ABSENT")); | |
| 214 // Doesn't cause ConcurrentModificationError. | |
| 215 } | |
| 216 | |
| 217 // Raw iterator. | |
| 218 Iterator iter = map.keys.iterator; | |
| 219 for (int key = 0; key < i; key++) { | |
| 220 Expect.equals(key + 2, map[key]); | |
| 221 map[key] = key + 3; | |
| 222 map.remove(1000); // Removing something not there. | |
| 223 map.putIfAbsent(key, () => Expect.fail("SHOULD NOT BE ABSENT")); | |
| 224 // Doesn't cause ConcurrentModificationError on the moveNext. | |
| 225 } | |
| 226 iter.moveNext(); // Should not throw. | |
| 227 | |
| 228 // Remove a lot of elements, which can cause a re-tabulation. | |
| 229 for (int key = 1; key < i; key++) { | |
| 230 Expect.equals(key + 3, map[key]); | |
| 231 map.remove(key); | |
| 232 } | |
| 233 iter = map.keys.iterator; | |
| 234 map[0] = 2; | |
| 235 iter.moveNext(); // Should not throw. | |
| 236 } | |
| 237 } | |
| 238 | |
| 239 { | |
| 240 // Check that null can be in the map. | |
| 241 Map map = newMap(); | |
| 242 map[null] = 0; | |
| 243 Expect.equals(1, map.length); | |
| 244 Expect.isTrue(map.containsKey(null)); | |
| 245 Expect.isNull(map.keys.first); | |
| 246 Expect.isNull(map.keys.last); | |
| 247 map[null] = 1; | |
| 248 Expect.equals(1, map.length); | |
| 249 Expect.isTrue(map.containsKey(null)); | |
| 250 map.remove(null); | |
| 251 Expect.isTrue(map.isEmpty); | |
| 252 Expect.isFalse(map.containsKey(null)); | |
| 253 | |
| 254 // Created using map.from. | |
| 255 map = newMapFrom(new Map()..[null] = 0); | |
| 256 Expect.equals(1, map.length); | |
| 257 Expect.isTrue(map.containsKey(null)); | |
| 258 Expect.isNull(map.keys.first); | |
| 259 Expect.isNull(map.keys.last); | |
| 260 map[null] = 1; | |
| 261 Expect.equals(1, map.length); | |
| 262 Expect.isTrue(map.containsKey(null)); | |
| 263 map.remove(null); | |
| 264 Expect.isTrue(map.isEmpty); | |
| 265 Expect.isFalse(map.containsKey(null)); | |
| 266 | |
| 267 Map fromMap = new Map(); | |
| 268 fromMap[1] = 0; | |
| 269 fromMap[2] = 0; | |
| 270 fromMap[3] = 0; | |
| 271 fromMap[null] = 0; | |
| 272 fromMap[4] = 0; | |
| 273 fromMap[5] = 0; | |
| 274 fromMap[6] = 0; | |
| 275 Expect.equals(7, fromMap.length); | |
| 276 | |
| 277 // map that grows with null in it. | |
| 278 map = newMapFrom(fromMap); | |
| 279 Expect.equals(7, map.length); | |
| 280 for (int i = 7; i < 128; i++) { | |
| 281 map[i] = 0; | |
| 282 } | |
| 283 Expect.equals(128, map.length); | |
| 284 Expect.isTrue(map.containsKey(null)); | |
| 285 map[null] = 1; | |
| 286 Expect.equals(128, map.length); | |
| 287 Expect.isTrue(map.containsKey(null)); | |
| 288 map.remove(null); | |
| 289 Expect.equals(127, map.length); | |
| 290 Expect.isFalse(map.containsKey(null)); | |
| 291 } | |
| 292 } | |
| 293 | |
| 294 void main() { | |
| 295 Expect.isTrue(new HashMap<int, String>() is Map<int, String>); | |
| 296 Expect.isTrue(new LinkedHashMap<int, String>() is Map<int, String>); | |
| 297 Expect.isTrue(new HashMap<String, int>.from({}) is Map<String, int>); | |
| 298 Expect.isTrue(new LinkedHashMap<String, int>.from({}) is Map<String, int>); | |
| 299 Expect.isTrue(<String, int>{} is Map<String, int>); | |
| 300 Expect.isTrue(const <String, int>{} is Map<String, int>); | |
| 301 | |
| 302 testMap(() => new HashMap(), (m) => new HashMap.from(m)); | |
| 303 testMap(() => new LinkedHashMap(), (m) => new LinkedHashMap.from(m)); | |
| 304 } | |
| 305 | |
| 306 class BadHashCode { | |
| 307 static int idCounter = 0; | |
| 308 final int id; | |
| 309 BadHashCode() : id = idCounter++; | |
| 310 int get hashCode => 42; | |
| 311 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2989643002:
Migrate test block 8 to Dart 2.0. (Closed)
