Flutter Engine
The Flutter Engine
Loading...
Searching...
No Matches
hash_map_test.cc
Go to the documentation of this 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
3// BSD-style license that can be found in the LICENSE file.
4
5#include "vm/hash_map.h"
6#include "platform/assert.h"
7#include "vm/unit_test.h"
8
9namespace dart {
10
11class TestValue {
12 public:
13 explicit TestValue(intptr_t x) : x_(x) {}
14 // FinalizeHash is used here to provide coverage for FinalizeHash(...)
15 // function.
16 uword Hash() const { return FinalizeHash(static_cast<uint32_t>(x_) & 1); }
17 bool Equals(const TestValue& other) { return x_ == other.x_; }
18
19 private:
20 intptr_t x_;
21};
22
23TEST_CASE(DirectChainedHashMap) {
24 DirectChainedHashMap<PointerSetKeyValueTrait<TestValue>> map;
25 EXPECT(map.IsEmpty());
26 TestValue v1(0);
27 TestValue v2(1);
28 TestValue v3(0);
29 map.Insert(&v1);
30 EXPECT(map.LookupValue(&v1) == &v1);
31 map.Insert(&v2);
32 EXPECT(map.LookupValue(&v1) == &v1);
33 EXPECT(map.LookupValue(&v2) == &v2);
34 EXPECT(map.LookupValue(&v3) == &v1);
35 EXPECT(map.Remove(&v1));
36 EXPECT(map.Lookup(&v1) == nullptr);
37 map.Insert(&v1);
38 DirectChainedHashMap<PointerSetKeyValueTrait<TestValue>> map2(map);
39 EXPECT(map2.LookupValue(&v1) == &v1);
40 EXPECT(map2.LookupValue(&v2) == &v2);
41 EXPECT(map2.LookupValue(&v3) == &v1);
42}
43
44TEST_CASE(DirectChainedHashMapInsertRemove) {
45 DirectChainedHashMap<PointerSetKeyValueTrait<TestValue>> map;
46 EXPECT(map.IsEmpty());
47 TestValue v1(1);
48 TestValue v2(3); // Note: v1, v2, v3 should have the same hash.
49 TestValue v3(5);
50
51 // Start with adding and removing the same element.
52 map.Insert(&v1);
53 EXPECT(map.LookupValue(&v1) == &v1);
54 EXPECT(map.Remove(&v1));
55 EXPECT(map.Lookup(&v1) == nullptr);
56
57 // Inserting v2 first should put it at the head of the list.
58 map.Insert(&v2);
59 map.Insert(&v1);
60 EXPECT(map.LookupValue(&v2) == &v2);
61 EXPECT(map.LookupValue(&v1) == &v1);
62
63 // Check to see if removing the head of the list causes issues.
64 EXPECT(map.Remove(&v2));
65 EXPECT(map.Lookup(&v2) == nullptr);
66 EXPECT(map.LookupValue(&v1) == &v1);
67
68 // Reinsert v2, which will place it at the back of the hash map list.
69 map.Insert(&v2);
70 EXPECT(map.LookupValue(&v2) == &v2);
71
72 // Remove from the back of the hash map list.
73 EXPECT(map.Remove(&v2));
74 EXPECT(map.Lookup(&v2) == nullptr);
75 EXPECT(map.Remove(&v1));
76 EXPECT(map.Lookup(&v1) == nullptr);
77
78 // Check to see that removing an invalid element returns false.
79 EXPECT(!map.Remove(&v1));
80
81 // One last case: remove from the middle of a hash map list.
82 map.Insert(&v1);
83 map.Insert(&v2);
84 map.Insert(&v3);
85
86 EXPECT(map.LookupValue(&v1) == &v1);
87 EXPECT(map.LookupValue(&v2) == &v2);
88 EXPECT(map.LookupValue(&v3) == &v3);
89
90 EXPECT(map.Remove(&v2));
91 EXPECT(map.LookupValue(&v1) == &v1);
92 EXPECT(map.Lookup(&v2) == nullptr);
93 EXPECT(map.LookupValue(&v3) == &v3);
94
95 EXPECT(map.Remove(&v1));
96 EXPECT(map.Remove(&v3));
97
98 EXPECT(map.IsEmpty());
99}
100
101TEST_CASE(MallocDirectChainedHashMap) {
102 MallocDirectChainedHashMap<PointerSetKeyValueTrait<TestValue>> map;
103 EXPECT(map.IsEmpty());
104 TestValue v1(0);
105 TestValue v2(1);
106 TestValue v3(0);
107 map.Insert(&v1);
108 EXPECT(map.LookupValue(&v1) == &v1);
109 map.Insert(&v2);
110 EXPECT(map.LookupValue(&v1) == &v1);
111 EXPECT(map.LookupValue(&v2) == &v2);
112 EXPECT(map.LookupValue(&v3) == &v1);
113 MallocDirectChainedHashMap<PointerSetKeyValueTrait<TestValue>> map2(map);
114 EXPECT(map2.LookupValue(&v1) == &v1);
115 EXPECT(map2.LookupValue(&v2) == &v2);
116 EXPECT(map2.LookupValue(&v3) == &v1);
117}
118
119TEST_CASE(ZoneDirectChainedHashMap) {
120 auto zone = thread->zone();
121 auto const map = new (zone)
122 ZoneDirectChainedHashMap<PointerSetKeyValueTrait<TestValue>>(zone);
123 EXPECT(map->IsEmpty());
124 TestValue v1(0);
125 TestValue v2(1);
126 TestValue v3(0);
127 map->Insert(&v1);
128 EXPECT(map->LookupValue(&v1) == &v1);
129 map->Insert(&v2);
130 EXPECT(map->LookupValue(&v1) == &v1);
131 EXPECT(map->LookupValue(&v2) == &v2);
132 EXPECT(map->LookupValue(&v3) == &v1);
133}
134
135class IntptrPair {
136 public:
137 IntptrPair() : first_(-1), second_(-1) {}
138 IntptrPair(intptr_t first, intptr_t second)
139 : first_(first), second_(second) {}
140
141 intptr_t first() const { return first_; }
142 intptr_t second() const { return second_; }
143
144 bool operator==(const IntptrPair& other) {
145 return (first_ == other.first_) && (second_ == other.second_);
146 }
147
148 bool operator!=(const IntptrPair& other) {
149 return (first_ != other.first_) || (second_ != other.second_);
150 }
151
152 private:
153 intptr_t first_;
154 intptr_t second_;
155};
156
157TEST_CASE(DirectChainedHashMapIterator) {
158 IntptrPair p1(1, 1);
159 IntptrPair p2(2, 2);
160 IntptrPair p3(3, 3);
161 IntptrPair p4(4, 4);
162 IntptrPair p5(5, 5);
163 DirectChainedHashMap<NumbersKeyValueTrait<IntptrPair>> map;
164 EXPECT(map.IsEmpty());
165 DirectChainedHashMap<NumbersKeyValueTrait<IntptrPair>>::Iterator it =
166 map.GetIterator();
167 EXPECT(it.Next() == nullptr);
168 it.Reset();
169
170 map.Insert(p1);
171 EXPECT(*it.Next() == p1);
172 it.Reset();
173
174 map.Insert(p2);
175 map.Insert(p3);
176 map.Insert(p4);
177 map.Insert(p5);
178 intptr_t count = 0;
179 intptr_t sum = 0;
180 while (true) {
181 IntptrPair* p = it.Next();
182 if (p == nullptr) {
183 break;
184 }
185 count++;
186 sum += p->second();
187 }
188
189 EXPECT(count == 5);
190 EXPECT(sum == 15);
191}
192
193TEST_CASE(DirectChainedHashMapIteratorWithCollisionInLastBucket) {
194 intptr_t values[] = {65, 325, 329, 73, 396, 207, 215, 93, 227, 39,
195 431, 112, 176, 313, 188, 317, 61, 127, 447};
196 IntMap<intptr_t> map;
197
198 for (intptr_t value : values) {
199 map.Insert(value, value);
200 }
201
202 bool visited[ARRAY_SIZE(values)] = {};
203 intptr_t count = 0;
204 auto it = map.GetIterator();
205 for (auto* p = it.Next(); p != nullptr; p = it.Next()) {
206 ++count;
207 bool found = false;
208 intptr_t i = 0;
209 for (intptr_t v : values) {
210 if (v == p->key) {
211 EXPECT(v == p->value);
212 EXPECT(!visited[i]);
213 visited[i] = true;
214 found = true;
215 break;
216 }
217 ++i;
218 }
219 EXPECT(found);
220 }
221 EXPECT(count == ARRAY_SIZE(values));
222 for (bool is_visited : visited) {
223 EXPECT(is_visited);
224 }
225}
226
227TEST_CASE(ZoneCStringSet) {
228 auto zone = thread->zone();
229
230 const char* const kConst1 = "test";
231 const char* const kConst2 = "test 2";
232
233 char* const str1 = OS::SCreate(zone, "%s", kConst1);
234 char* const str2 = OS::SCreate(zone, "%s", kConst2);
235 char* const str3 = OS::SCreate(zone, "%s", kConst1);
236
237 // Make sure these strings are pointer-distinct, but C-string-equal.
238 EXPECT_NE(str1, str3);
239 EXPECT_STREQ(str1, str3);
240
241 auto const set = new (zone) ZoneCStringSet(zone);
242 EXPECT(set->IsEmpty());
243
244 set->Insert(str1);
245 EXPECT_NOTNULL(set->Lookup(str1));
246 EXPECT_NULLPTR(set->Lookup(str2));
247 EXPECT_NOTNULL(set->Lookup(str3));
248
249 set->Insert(str2);
250 EXPECT_NOTNULL(set->Lookup(str1));
251 EXPECT_NOTNULL(set->Lookup(str2));
252 EXPECT_NOTNULL(set->Lookup(str3));
253
254 EXPECT(set->Remove(str3));
255 EXPECT_NULLPTR(set->Lookup(str1));
256 EXPECT_NOTNULL(set->Lookup(str2));
257 EXPECT_NULLPTR(set->Lookup(str3));
258
259 EXPECT(!set->Remove(str3));
260 EXPECT(set->Remove(str2));
261 EXPECT(set->IsEmpty());
262}
263
264TEST_CASE(CStringIntMap) {
265 const char* const kConst1 = "test";
266 const char* const kConst2 = "test 2";
267
268 char* const str1 = OS::SCreate(nullptr, "%s", kConst1);
269 char* const str2 = OS::SCreate(nullptr, "%s", kConst2);
270 char* const str3 = OS::SCreate(nullptr, "%s", kConst1);
271
272 // Make sure these strings are pointer-distinct, but C-string-equal.
273 EXPECT_NE(str1, str3);
274 EXPECT_STREQ(str1, str3);
275
276 const intptr_t i1 = 1;
277 const intptr_t i2 = 2;
278
279 CStringIntMap map;
280 EXPECT(map.IsEmpty());
281
282 map.Insert({str1, i1});
283 EXPECT_NOTNULL(map.Lookup(str1));
284 EXPECT_EQ(i1, map.LookupValue(str1));
285 EXPECT_NULLPTR(map.Lookup(str2));
286 EXPECT_NOTNULL(map.Lookup(str3));
287 EXPECT_EQ(i1, map.LookupValue(str3));
288
289 map.Insert({str2, i2});
290 EXPECT_NOTNULL(map.Lookup(str1));
291 EXPECT_EQ(i1, map.LookupValue(str1));
292 EXPECT_NOTNULL(map.Lookup(str2));
293 EXPECT_EQ(i2, map.LookupValue(str2));
294 EXPECT_NOTNULL(map.Lookup(str3));
295 EXPECT_EQ(i1, map.LookupValue(str3));
296
297 EXPECT(map.Remove(str3));
298 EXPECT_NULLPTR(map.Lookup(str1));
299 EXPECT_NOTNULL(map.Lookup(str2));
300 EXPECT_EQ(i2, map.LookupValue(str2));
301 EXPECT_NULLPTR(map.Lookup(str3));
302
303 EXPECT(!map.Remove(str3));
304 EXPECT(map.Remove(str2));
305 EXPECT(map.IsEmpty());
306
307 free(str3);
308 free(str2);
309 free(str1);
310}
311
312TEST_CASE(CStringIntMapUpdate) {
313 const char* const kConst1 = "test";
314 const char* const kConst2 = "test 2";
315
316 char* str1 = OS::SCreate(nullptr, "%s", kConst1);
317 char* str2 = OS::SCreate(nullptr, "%s", kConst2);
318 char* str3 = OS::SCreate(nullptr, "%s", kConst1);
319 char* str4 = OS::SCreate(nullptr, "%s", kConst1); // Only used for lookup.
320
321 // Make sure these strings are pointer-distinct, but C-string-equal.
322 EXPECT_NE(str1, str3);
323 EXPECT_NE(str1, str4);
324 EXPECT_NE(str3, str4);
325 EXPECT_STREQ(str1, str3);
326 EXPECT_STREQ(str1, str4);
327
328 CStringIntMapKeyValueTrait::Pair p1{str1, 1};
329 CStringIntMapKeyValueTrait::Pair p2{str2, 2};
330 CStringIntMapKeyValueTrait::Pair p3{str3, 3};
331
332 CStringIntMap map;
333 EXPECT(map.IsEmpty());
334
335 map.Update(p1);
336 EXPECT_NOTNULL(map.Lookup(str1));
337 EXPECT_EQ(p1.value, map.LookupValue(str1));
338 EXPECT_NULLPTR(map.Lookup(str2));
339 EXPECT_NOTNULL(map.Lookup(str3));
340 EXPECT_EQ(p1.value, map.LookupValue(str3));
341 EXPECT_NOTNULL(map.Lookup(str4));
342 EXPECT_EQ(p1.value, map.LookupValue(str4));
343
344 map.Update(p2);
345 EXPECT_NOTNULL(map.Lookup(str1));
346 EXPECT_EQ(p1.value, map.LookupValue(str1));
347 EXPECT_NOTNULL(map.Lookup(str2));
348 EXPECT_EQ(p2.value, map.LookupValue(str2));
349 EXPECT_NOTNULL(map.Lookup(str3));
350 EXPECT_EQ(p1.value, map.LookupValue(str3));
351 EXPECT_NOTNULL(map.Lookup(str4));
352 EXPECT_EQ(p1.value, map.LookupValue(str4));
353
354 // Check Lookup after Update.
355 map.Update(p3);
356 EXPECT_NOTNULL(map.Lookup(str1));
357 EXPECT_EQ(p3.value, map.LookupValue(str1));
358 EXPECT_NOTNULL(map.Lookup(str2));
359 EXPECT_EQ(p2.value, map.LookupValue(str2));
360 EXPECT_NOTNULL(map.Lookup(str3));
361 EXPECT_EQ(p3.value, map.LookupValue(str3));
362 EXPECT_NOTNULL(map.Lookup(str4));
363 EXPECT_EQ(p3.value, map.LookupValue(str4));
364
365 // Check that single Remove after only Updates ensures Lookup fails after.
366 EXPECT(map.Remove(str3));
367 EXPECT_NULLPTR(map.Lookup(str1));
368 EXPECT_NOTNULL(map.Lookup(str2));
369 EXPECT_EQ(p2.value, map.LookupValue(str2));
370 EXPECT_NULLPTR(map.Lookup(str3));
371 EXPECT_NULLPTR(map.Lookup(str4));
372
373 EXPECT(!map.Remove(str3));
374 EXPECT(map.Remove(str2));
375 EXPECT(map.IsEmpty());
376
377 // Quick double-check that these weren't side-effected by the implementation
378 // of hash maps (p1 especially).
379 EXPECT_EQ(str1, p1.key);
380 EXPECT_EQ(1, p1.value);
381 EXPECT_EQ(str2, p2.key);
382 EXPECT_EQ(2, p2.value);
383 EXPECT_EQ(str3, p3.key);
384 EXPECT_EQ(3, p3.value);
385
386 free(str4);
387 free(str3);
388 free(str2);
389 free(str1);
390}
391
392} // namespace dart
count
int count
Definition FontMgrTest.cpp:50
EXPECT
#define EXPECT(type, expectedAlignment, expectedSize)
Definition UniformOffsetCalculatorTest.cpp:33
v2
Vec2Value v2
Definition Vec2KeyframeAnimator.cpp:40
dart::BaseDirectChainedHashMap::LookupValue
KeyValueTrait::Value LookupValue(typename KeyValueTrait::Key key) const
Definition hash_map.h:159
dart::IntptrPair::operator!=
bool operator!=(const IntptrPair &other)
Definition hash_map_test.cc:148
dart::IntptrPair::first
intptr_t first() const
Definition hash_map_test.cc:141
dart::IntptrPair::operator==
bool operator==(const IntptrPair &other)
Definition hash_map_test.cc:144
dart::IntptrPair::second
intptr_t second() const
Definition hash_map_test.cc:142
dart::IntptrPair::IntptrPair
IntptrPair(intptr_t first, intptr_t second)
Definition hash_map_test.cc:138
dart::OS::SCreate
static char * SCreate(Zone *zone, const char *format,...) PRINTF_ATTRIBUTE(2
dart::TestValue::Hash
uword Hash() const
Definition hash_map_test.cc:16
dart::TestValue::Equals
bool Equals(const TestValue &other)
Definition hash_map_test.cc:17
dart::TestValue::TestValue
TestValue(intptr_t x)
Definition hash_map_test.cc:13
value
uint8_t value
Definition fl_standard_message_codec.cc:36
hash_map.h
x
double x
Definition mouse-input-test.cc:82
dart::uword
uintptr_t uword
Definition globals.h:501
dart::FinalizeHash
uint32_t FinalizeHash(uint32_t hash, intptr_t hashbits=kBitsPerInt32)
Definition hash.h:20
unit_test.h
TEST_CASE
#define TEST_CASE(name)
Definition unit_test.h:85
ARRAY_SIZE
#define ARRAY_SIZE(array)
Definition globals.h:72
Generated on Fri Apr 26 2024 06:15:06 for Flutter Engine by doxygen 1.9.8