1 /*
2 * Copyright (C) 2021 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "perfetto/ext/base/flat_hash_map.h"
18
19 #include <array>
20 #include <functional>
21 #include <random>
22 #include <set>
23 #include <unordered_map>
24
25 #include "perfetto/ext/base/hash.h"
26 #include "test/gtest_and_gmock.h"
27
28 namespace perfetto {
29 namespace base {
30 namespace {
31
32 using ::testing::Types;
33
34 struct CollidingHasher {
operator ()perfetto::base::__anonab38039a0111::CollidingHasher35 size_t operator()(int n) const { return static_cast<size_t>(n % 1000); }
36 };
37
38 template <typename T>
39 class FlatHashMapTest : public testing::Test {
40 public:
41 using Probe = T;
42 };
43
44 using ProbeTypes = Types<LinearProbe, QuadraticHalfProbe, QuadraticProbe>;
45 TYPED_TEST_SUITE(FlatHashMapTest, ProbeTypes, /* trailing ',' for GCC*/);
46
47 struct Key {
48 static int instances;
49
Keyperfetto::base::__anonab38039a0111::Key50 explicit Key(int v) : val(v) {}
~Keyperfetto::base::__anonab38039a0111::Key51 ~Key() { instances--; }
Keyperfetto::base::__anonab38039a0111::Key52 Key(Key&& other) noexcept {
53 val = other.val;
54 other.val = -1;
55 }
operator ==perfetto::base::__anonab38039a0111::Key56 bool operator==(const Key& other) const { return val == other.val; }
57 int val = 0;
58 int id = instances++;
59 };
60
61 struct Value {
62 static int instances;
63
Valueperfetto::base::__anonab38039a0111::Value64 explicit Value(int v = 0) : val(v) {}
~Valueperfetto::base::__anonab38039a0111::Value65 ~Value() { instances--; }
Valueperfetto::base::__anonab38039a0111::Value66 Value(Value&& other) noexcept {
67 val = other.val;
68 other.val = -1;
69 }
70 Value(const Value&) = delete;
71 int val = 0;
72 int id = instances++;
73 };
74
75 struct Hasher {
operator ()perfetto::base::__anonab38039a0111::Hasher76 size_t operator()(const Key& k) const { return static_cast<size_t>(k.val); }
77 };
78
79 int Key::instances = 0;
80 int Value::instances = 0;
81
TYPED_TEST(FlatHashMapTest,NonTrivialKeyValues)82 TYPED_TEST(FlatHashMapTest, NonTrivialKeyValues) {
83 FlatHashMap<Key, Value, Hasher, typename TestFixture::Probe> fmap;
84
85 for (int iteration = 0; iteration < 3; iteration++) {
86 const int kNum = 10;
87 for (int i = 0; i < kNum; i++) {
88 ASSERT_TRUE(fmap.Insert(Key(i), Value(i * 2)).second);
89 Value* value = fmap.Find(Key(i));
90 ASSERT_NE(value, nullptr);
91 ASSERT_EQ(value->val, i * 2);
92 ASSERT_EQ(Key::instances, i + 1);
93 ASSERT_EQ(Value::instances, i + 1);
94 }
95
96 ASSERT_TRUE(fmap.Erase(Key(1)));
97 ASSERT_TRUE(fmap.Erase(Key(5)));
98 ASSERT_TRUE(fmap.Erase(Key(9)));
99
100 ASSERT_EQ(Key::instances, kNum - 3);
101 ASSERT_EQ(Value::instances, kNum - 3);
102
103 FlatHashMap<Key, Value, Hasher, typename TestFixture::Probe> fmap2(
104 std::move(fmap));
105 ASSERT_EQ(fmap.size(), 0u);
106 ASSERT_EQ(fmap2.size(), static_cast<size_t>(kNum - 3));
107
108 ASSERT_EQ(Key::instances, kNum - 3);
109 ASSERT_EQ(Value::instances, kNum - 3);
110
111 // Ensure the moved-from map is usable.
112 fmap.Insert(Key(1), Value(-1));
113 fmap.Insert(Key(5), Value(-5));
114 fmap.Insert(Key(9), Value(-9));
115 ASSERT_EQ(Key::instances, (kNum - 3) + 3);
116 ASSERT_EQ(Value::instances, (kNum - 3) + 3);
117
118 fmap2.Clear();
119 ASSERT_EQ(fmap2.size(), 0u);
120 ASSERT_EQ(fmap.size(), 3u);
121 ASSERT_EQ(Key::instances, 3);
122 ASSERT_EQ(Value::instances, 3);
123 ASSERT_EQ(fmap.Find(Key(1))->val, -1);
124 ASSERT_EQ(fmap.Find(Key(5))->val, -5);
125 ASSERT_EQ(fmap.Find(Key(9))->val, -9);
126
127 fmap = std::move(fmap2);
128 ASSERT_EQ(Key::instances, 0);
129 ASSERT_EQ(Value::instances, 0);
130 ASSERT_EQ(fmap.size(), 0u);
131 }
132
133 // Test that operator[] behaves rationally.
134 fmap = decltype(fmap)(); // Re-assign with a copy constructor.
135 fmap[Key{2}].val = 102;
136 fmap[Key{1}].val = 101;
137 ASSERT_EQ(fmap.Find(Key{2})->val, 102);
138 ASSERT_EQ(fmap.Find(Key{1})->val, 101);
139 fmap[Key{2}].val = 122;
140 ASSERT_EQ(fmap.Find(Key{2})->val, 122);
141 ASSERT_EQ(fmap[Key{1}].val, 101);
142 auto fmap2(std::move(fmap));
143 ASSERT_EQ(fmap[Key{1}].val, 0);
144 ASSERT_EQ(fmap.size(), 1u);
145 }
146
TYPED_TEST(FlatHashMapTest,AllTagsAreValid)147 TYPED_TEST(FlatHashMapTest, AllTagsAreValid) {
148 FlatHashMap<size_t, size_t, base::AlreadyHashed<size_t>,
149 typename TestFixture::Probe>
150 fmap;
151 auto make_key = [](size_t tag) {
152 return tag << ((sizeof(size_t) - 1) * size_t(8));
153 };
154 for (size_t i = 0; i < 256; i++) {
155 size_t key = make_key(i);
156 fmap.Insert(key, i);
157 ASSERT_EQ(fmap.size(), i + 1);
158 }
159 for (size_t i = 0; i < 256; i++) {
160 size_t key = make_key(i);
161 ASSERT_NE(fmap.Find(key), nullptr);
162 ASSERT_EQ(*fmap.Find(key), i);
163 }
164 for (size_t i = 0; i < 256; i++) {
165 size_t key = make_key(i);
166 fmap.Erase(key);
167 ASSERT_EQ(fmap.size(), 255 - i);
168 ASSERT_EQ(fmap.Find(key), nullptr);
169 }
170 }
171
TYPED_TEST(FlatHashMapTest,FillWithTombstones)172 TYPED_TEST(FlatHashMapTest, FillWithTombstones) {
173 FlatHashMap<Key, Value, Hasher, typename TestFixture::Probe> fmap(
174 /*initial_capacity=*/0, /*load_limit_pct=*/100);
175
176 for (int rep = 0; rep < 3; rep++) {
177 for (int i = 0; i < 1024; i++)
178 ASSERT_TRUE(fmap.Insert(Key(i), Value(i)).second);
179
180 ASSERT_EQ(fmap.size(), 1024u);
181 ASSERT_EQ(Key::instances, 1024);
182 ASSERT_EQ(Value::instances, 1024);
183
184 // Erase all entries.
185 for (int i = 0; i < 1024; i++)
186 ASSERT_TRUE(fmap.Erase(Key(i)));
187
188 ASSERT_EQ(fmap.size(), 0u);
189 ASSERT_EQ(Key::instances, 0);
190 ASSERT_EQ(Value::instances, 0);
191 }
192 }
193
TYPED_TEST(FlatHashMapTest,Collisions)194 TYPED_TEST(FlatHashMapTest, Collisions) {
195 FlatHashMap<int, int, CollidingHasher, typename TestFixture::Probe> fmap(
196 /*initial_capacity=*/0, /*load_limit_pct=*/100);
197
198 for (int rep = 0; rep < 3; rep++) {
199 // Insert four values which collide on the same bucket.
200 ASSERT_TRUE(fmap.Insert(1001, 1001).second);
201 ASSERT_TRUE(fmap.Insert(2001, 2001).second);
202 ASSERT_TRUE(fmap.Insert(3001, 3001).second);
203 ASSERT_TRUE(fmap.Insert(4001, 4001).second);
204
205 // Erase the 2nd one, it will create a tombstone.
206 ASSERT_TRUE(fmap.Erase(2001));
207 ASSERT_EQ(fmap.size(), 3u);
208
209 // Insert an entry that exists already, but happens to be located after the
210 // tombstone. Should still fail.
211 ASSERT_FALSE(fmap.Insert(3001, 3001).second);
212 ASSERT_EQ(fmap.size(), 3u);
213
214 ASSERT_TRUE(fmap.Erase(3001));
215 ASSERT_FALSE(fmap.Erase(2001));
216 ASSERT_TRUE(fmap.Erase(4001));
217
218 // The only element left is 101.
219 ASSERT_EQ(fmap.size(), 1u);
220
221 ASSERT_TRUE(fmap.Erase(1001));
222 ASSERT_EQ(fmap.size(), 0u);
223 }
224 }
225
TYPED_TEST(FlatHashMapTest,ProbeVisitsAllSlots)226 TYPED_TEST(FlatHashMapTest, ProbeVisitsAllSlots) {
227 const int kIterations = 1024;
228 FlatHashMap<int, int, CollidingHasher, typename TestFixture::Probe> fmap(
229 /*initial_capacity=*/kIterations, /*load_limit_pct=*/100);
230 for (int i = 0; i < kIterations; i++) {
231 ASSERT_TRUE(fmap.Insert(i, i).second);
232 }
233 // If the hashmap hits an expansion the tests doesn't make sense. This test
234 // makes sense only if we actually saturate all buckets.
235 EXPECT_EQ(fmap.capacity(), static_cast<size_t>(kIterations));
236 }
237
TYPED_TEST(FlatHashMapTest,Iterator)238 TYPED_TEST(FlatHashMapTest, Iterator) {
239 FlatHashMap<int, int, base::AlreadyHashed<int>, typename TestFixture::Probe>
240 fmap;
241
242 auto it = fmap.GetIterator();
243 ASSERT_FALSE(it);
244
245 // Insert 3 values and iterate.
246 ASSERT_TRUE(fmap.Insert(1, 1001).second);
247 ASSERT_TRUE(fmap.Insert(2, 2001).second);
248 ASSERT_TRUE(fmap.Insert(3, 3001).second);
249 it = fmap.GetIterator();
250 for (int i = 1; i <= 3; i++) {
251 ASSERT_TRUE(it);
252 ASSERT_EQ(it.key(), i);
253 ASSERT_EQ(it.value(), i * 1000 + 1);
254 ++it;
255 }
256 ASSERT_FALSE(it);
257
258 // Erase the middle one and iterate.
259 fmap.Erase(2);
260 it = fmap.GetIterator();
261 ASSERT_TRUE(it);
262 ASSERT_EQ(it.key(), 1);
263 ++it;
264 ASSERT_TRUE(it);
265 ASSERT_EQ(it.key(), 3);
266 ++it;
267 ASSERT_FALSE(it);
268
269 // Erase everything and iterate.
270 fmap.Clear();
271 it = fmap.GetIterator();
272 ASSERT_FALSE(it);
273 }
274
275 // Test that Insert() and operator[] don't invalidate pointers if the key exists
276 // already, regardless of the load factor.
TYPED_TEST(FlatHashMapTest,DontRehashIfKeyAlreadyExists)277 TYPED_TEST(FlatHashMapTest, DontRehashIfKeyAlreadyExists) {
278 static constexpr size_t kInitialCapacity = 128;
279 static std::array<size_t, 3> kLimitPct{25, 50, 100};
280
281 for (size_t limit_pct : kLimitPct) {
282 FlatHashMap<size_t, size_t, AlreadyHashed<size_t>,
283 typename TestFixture::Probe>
284 fmap(kInitialCapacity, static_cast<int>(limit_pct));
285
286 const size_t limit = kInitialCapacity * limit_pct / 100u;
287 ASSERT_EQ(fmap.capacity(), kInitialCapacity);
288 std::vector<size_t*> key_ptrs;
289 for (size_t i = 0; i < limit; i++) {
290 auto it_and_ins = fmap.Insert(i, i);
291 ASSERT_TRUE(it_and_ins.second);
292 ASSERT_EQ(fmap.capacity(), kInitialCapacity);
293 key_ptrs.push_back(it_and_ins.first);
294 }
295
296 // Re-insert existing items. It should not cause rehashing.
297 for (size_t i = 0; i < limit; i++) {
298 auto it_and_ins = fmap.Insert(i, i);
299 ASSERT_FALSE(it_and_ins.second);
300 ASSERT_EQ(it_and_ins.first, key_ptrs[i]);
301
302 size_t* key_ptr = &fmap[i];
303 ASSERT_EQ(key_ptr, key_ptrs[i]);
304 ASSERT_EQ(fmap.capacity(), kInitialCapacity);
305 }
306 }
307 }
308
TYPED_TEST(FlatHashMapTest,VsUnorderedMap)309 TYPED_TEST(FlatHashMapTest, VsUnorderedMap) {
310 std::unordered_map<int, int, CollidingHasher> umap;
311 FlatHashMap<int, int, CollidingHasher, typename TestFixture::Probe> fmap;
312 std::minstd_rand0 rng(0);
313
314 for (int rep = 0; rep < 2; rep++) {
315 std::set<int> keys_copy;
316 const int kRange = 1024;
317
318 // Insert some random elements.
319 for (int i = 0; i < kRange; i++) {
320 int key = static_cast<int>(rng()) / 2;
321 int value = key * 2;
322 keys_copy.insert(key);
323 auto it_and_inserted_u = umap.insert({key, value});
324 auto it_and_inserted_f = fmap.Insert(key, value);
325 ASSERT_EQ(it_and_inserted_u.second, it_and_inserted_f.second);
326 ASSERT_EQ(*it_and_inserted_f.first, value);
327 ASSERT_EQ(umap.size(), fmap.size());
328 int* res = fmap.Find(key);
329 ASSERT_NE(res, nullptr);
330 ASSERT_EQ(*res, value);
331 ASSERT_EQ(fmap[key], value); // Test that operator[] behaves like Find().
332 }
333 // Look them up.
334 for (int key : keys_copy) {
335 int* res = fmap.Find(key);
336 ASSERT_NE(res, nullptr);
337 ASSERT_EQ(*res, key * 2);
338 ASSERT_EQ(umap.size(), fmap.size());
339 }
340
341 // Some further deletions / insertions / reinsertions.
342 for (int key : keys_copy) {
343 auto op = rng() % 4;
344
345 if (op < 2) {
346 // With a 50% chance, erase the key.
347 bool erased_u = umap.erase(key) > 0;
348 bool erased_f = fmap.Erase(key);
349 ASSERT_EQ(erased_u, erased_f);
350 } else if (op == 3) {
351 // With a 25% chance, re-insert the same key (should fail).
352 umap.insert({key, 0});
353 ASSERT_FALSE(fmap.Insert(key, 0).second);
354 } else {
355 // With a 25% chance, insert a new key.
356 umap.insert({key + kRange, (key + kRange) * 2});
357 ASSERT_TRUE(fmap.Insert(key + kRange, (key + kRange) * 2).second);
358 }
359
360 ASSERT_EQ(umap.size(), fmap.size());
361 }
362
363 // Re-look up keys. Note some of them might be deleted by the loop above.
364 for (int k : keys_copy) {
365 for (int i = 0; i < 2; i++) {
366 const int key = k + kRange * i;
367 int* res = fmap.Find(key);
368 if (umap.count(key)) {
369 ASSERT_NE(res, nullptr);
370 ASSERT_EQ(*res, key * 2);
371 } else {
372 ASSERT_EQ(res, nullptr);
373 }
374 }
375 }
376
377 fmap.Clear();
378 umap.clear();
379 ASSERT_EQ(fmap.size(), 0u);
380
381 for (int key : keys_copy)
382 ASSERT_EQ(fmap.Find(key), nullptr);
383 }
384 }
385
386 } // namespace
387 } // namespace base
388 } // namespace perfetto
389