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 153 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
164 } else { | 164 } else { |
165 EXPECT(set.Present(y)); | 165 EXPECT(set.Present(y)); |
166 } | 166 } |
167 y = y * factor + offset; | 167 y = y * factor + offset; |
168 } | 168 } |
169 } | 169 } |
170 EXPECT_EQ(0u, set.occupancy()); | 170 EXPECT_EQ(0u, set.occupancy()); |
171 } | 171 } |
172 | 172 |
173 | 173 |
174 UNIT_TEST_CASE(Set) { | 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 |
183 } // namespace dart | 226 } // namespace dart |
OLD | NEW |