OLD | NEW |
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, 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 #include "platform/assert.h" | 5 #include "platform/assert.h" |
6 #include "platform/globals.h" | 6 #include "platform/globals.h" |
7 #include "platform/hashmap.h" | 7 #include "platform/hashmap.h" |
8 #include "vm/unit_test.h" | 8 #include "vm/unit_test.h" |
9 | 9 |
10 namespace dart { | 10 namespace dart { |
(...skipping 162 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
173 | 173 |
174 UNIT_TEST_CASE(HashMap_Basic) { | 174 UNIT_TEST_CASE(HashMap_Basic) { |
175 TestSet(WordHash, 100); | 175 TestSet(WordHash, 100); |
176 TestSet(Hash, 100); | 176 TestSet(Hash, 100); |
177 TestSet(CollisionHash1, 50); | 177 TestSet(CollisionHash1, 50); |
178 TestSet(CollisionHash2, 50); | 178 TestSet(CollisionHash2, 50); |
179 TestSet(CollisionHash3, 50); | 179 TestSet(CollisionHash3, 50); |
180 TestSet(CollisionHash4, 50); | 180 TestSet(CollisionHash4, 50); |
181 } | 181 } |
182 | 182 |
183 | |
184 UNIT_TEST_CASE(HashMap_RemoveDuringIteration) { | |
185 class Utils { | |
186 public: | |
187 static bool MatchFun(void* key1, void* key2) { return key1 == key2; } | |
188 static void* Key(intptr_t i) { return reinterpret_cast<void*>(i); } | |
189 static void* Value(intptr_t i) { return reinterpret_cast<void*>(i); } | |
190 static uint32_t HashCode(intptr_t key) { return 1; } | |
191 }; | |
192 | |
193 HashMap map(Utils::MatchFun, 8); | |
194 | |
195 // Add 6 (1, 1), ..., (6, 60) entries to the map all with a hashcode of 1 | |
196 // (i.e. have all keys have collinding hashcode). | |
197 // | |
198 // This causes the probing position in the hashmap to be 1 and open-addressing | |
199 // with linear probing will fill in the slots towards the right | |
200 // (i.e. from 1..6). | |
201 for (intptr_t i = 1; i <= 6 /* avoid rehash at 7 */; i++) { | |
202 HashMap::Entry* entry = map.Lookup(Utils::Key(i), Utils::HashCode(i), true); | |
203 entry->value = Utils::Value(10 * i); | |
204 } | |
205 | |
206 // Now we iterate over all elements and delete the current element. Since all | |
207 // our entries have a colliding hashcode of 1, each deletion will cause all | |
208 // following elements to be left-rotated by 1. | |
209 intptr_t i = 0; | |
210 HashMap::Entry* current = map.Start(); | |
211 while (current != NULL) { | |
212 i++; | |
213 EXPECT_EQ(Utils::Key(i), current->key); | |
214 EXPECT_EQ(Utils::Value(10 * i), current->value); | |
215 | |
216 // Every 2nd element we keep to hit the left-rotation case only sometimes. | |
217 if (i % 2 == 0) { | |
218 current = map.Remove(current); | |
219 } else { | |
220 current = map.Next(current); | |
221 } | |
222 } | |
223 EXPECT_EQ(6, i); | |
224 } | |
225 | |
226 } // namespace dart | 183 } // namespace dart |
OLD | NEW |