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 |