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