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