Flutter Engine
The Flutter Engine
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
i
int i
Definition: fl_socket_accessible.cc:18
value
uint8_t value
Definition: fl_standard_message_codec.cc:36
hash_map.h
x
double x
Definition: mouse-input-test.cc:82
dart_profiler_symbols.p
p
Definition: dart_profiler_symbols.py:55
dart
Definition: dart_vm.cc:33
dart::uword
uintptr_t uword
Definition: globals.h:501
dart::TEST_CASE
TEST_CASE(DirectoryCurrent)
Definition: directory_test.cc:18
dart::FinalizeHash
uint32_t FinalizeHash(uint32_t hash, intptr_t hashbits=kBitsPerInt32)
Definition: hash.h:20
flutter::set
DEF_SWITCHES_START aot vmservice shared library Name of the *so containing AOT compiled Dart assets for launching the service isolate vm snapshot The VM snapshot data that will be memory mapped as read only SnapshotAssetPath must be present isolate snapshot The isolate snapshot data that will be memory mapped as read only SnapshotAssetPath must be present cache dir Path to the cache directory This is different from the persistent_cache_path in embedder which is used for Skia shader cache icu native lib Path to the library file that exports the ICU data vm service The hostname IP address on which the Dart VM Service should be served If not set
Definition: switches.h:76
import_conformance_tests.values
tuple values
Definition: import_conformance_tests.py:49
skvx::map
SI auto map(std::index_sequence< I... >, Fn &&fn, const Args &... args) -> skvx::Vec< sizeof...(I), decltype(fn(args[0]...))>
Definition: SkVx.h:680
unit_test.h
ARRAY_SIZE
#define ARRAY_SIZE(array)
Definition: globals.h:72
Generated on Sun Jun 23 2024 21:55:41 for Flutter Engine by doxygen 1.9.4