Debian Codegraph @

tests/raw_hash_set_test.cc

raw
1 // Copyright 2018 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 // define this so that the "IterationOrderChanges" tests pass
16 #define PHMAP_NON_DETERMINISTIC 1
17
18 #include "parallel_hashmap/phmap.h"
19 //#include "container_memory.h"
20 //#include "hash_function_defaults.h"
21 #include "hash_policy_testing.h"
22 #include "hashtable_debug.h"
23
24 #include <cmath>
25 #include <cstdint>
26 #include <deque>
27 #include <functional>
28 #include <memory>
29 #include <numeric>
30 #include <random>
31 #include <string>
32
33 #ifdef _MSC_VER
34 #pragma warning(disable : 4018 4244 4702)
35 #endif // _MSC_VER
36
37 #if PHMAP_HAVE_STD_STRING_VIEW
38 #include <string_view>
39 #endif
40
41 #include "gmock/gmock.h"
42 #include "gtest/gtest.h"
43
44 namespace phmap {
45 namespace priv {
46
47 struct RawHashSetTestOnlyAccess {
48 template <typename C>
49 static auto GetSlots(const C& c) -> decltype(c.slots_) {
50 return c.slots_;
51 }
52 };
53
54 namespace {
55
56 using ::testing::DoubleNear;
57 using ::testing::ElementsAre;
58 using ::testing::Ge;
59 using ::testing::Lt;
60 using ::testing::Optional;
61 using ::testing::Pair;
62 using ::testing::UnorderedElementsAre;
63
64 TEST(Util, NormalizeCapacity) {
65 EXPECT_EQ(1, NormalizeCapacity(0));
66 EXPECT_EQ(1, NormalizeCapacity(1));
67 EXPECT_EQ(3, NormalizeCapacity(2));
68 EXPECT_EQ(3, NormalizeCapacity(3));
69 EXPECT_EQ(7, NormalizeCapacity(4));
70 EXPECT_EQ(7, NormalizeCapacity(7));
71 EXPECT_EQ(15, NormalizeCapacity(8));
72 EXPECT_EQ(15, NormalizeCapacity(15));
73 EXPECT_EQ(15 * 2 + 1, NormalizeCapacity(15 + 1));
74 EXPECT_EQ(15 * 2 + 1, NormalizeCapacity(15 + 2));
75 }
76
77 TEST(Util, GrowthAndCapacity) {
78 // Verify that GrowthToCapacity gives the minimum capacity that has enough
79 // growth.
80 for (size_t growth = 0; growth < 10000; ++growth) {
81 SCOPED_TRACE(growth);
82 size_t capacity = NormalizeCapacity(GrowthToLowerboundCapacity(growth));
83 // The capacity is large enough for `growth`
84 EXPECT_THAT(CapacityToGrowth(capacity), Ge(growth));
85 if (growth != 0 && capacity > 1) {
86 // There is no smaller capacity that works.
87 EXPECT_THAT(CapacityToGrowth(capacity / 2), Lt(growth));
88 }
89 }
90
91 for (size_t capacity = Group::kWidth - 1; capacity < 10000;
92 capacity = 2 * capacity + 1) {
93 SCOPED_TRACE(capacity);
94 size_t growth = CapacityToGrowth(capacity);
95 EXPECT_THAT(growth, Lt(capacity));
96 EXPECT_LE(GrowthToLowerboundCapacity(growth), capacity);
97 EXPECT_EQ(NormalizeCapacity(GrowthToLowerboundCapacity(growth)), capacity);
98 }
99 }
100
101 TEST(Util, probe_seq) {
102 probe_seq<16> seq(0, 127);
103 auto gen = [&]() {
104 size_t res = seq.offset();
105 seq.next();
106 return res;
107 };
108 std::vector<size_t> offsets(8);
109 std::generate_n(offsets.begin(), 8, gen);
110 EXPECT_THAT(offsets, ElementsAre(0, 16, 48, 96, 32, 112, 80, 64));
111 seq = probe_seq<16>(128, 127);
112 std::generate_n(offsets.begin(), 8, gen);
113 EXPECT_THAT(offsets, ElementsAre(0, 16, 48, 96, 32, 112, 80, 64));
114 }
115
116 TEST(BitMask, Smoke) {
117 EXPECT_FALSE((BitMask<uint8_t, 8>(0)));
118 EXPECT_TRUE((BitMask<uint8_t, 8>(5)));
119
120 EXPECT_THAT((BitMask<uint8_t, 8>(0)), ElementsAre());
121 EXPECT_THAT((BitMask<uint8_t, 8>(0x1)), ElementsAre(0));
122 EXPECT_THAT((BitMask<uint8_t, 8>(0x2)), ElementsAre(1));
123 EXPECT_THAT((BitMask<uint8_t, 8>(0x3)), ElementsAre(0, 1));
124 EXPECT_THAT((BitMask<uint8_t, 8>(0x4)), ElementsAre(2));
125 EXPECT_THAT((BitMask<uint8_t, 8>(0x5)), ElementsAre(0, 2));
126 EXPECT_THAT((BitMask<uint8_t, 8>(0x55)), ElementsAre(0, 2, 4, 6));
127 EXPECT_THAT((BitMask<uint8_t, 8>(0xAA)), ElementsAre(1, 3, 5, 7));
128 }
129
130 TEST(BitMask, WithShift) {
131 // See the non-SSE version of Group for details on what this math is for.
132 uint64_t ctrl = 0x1716151413121110;
133 uint64_t hash = 0x12;
134 constexpr uint64_t msbs = 0x8080808080808080ULL;
135 constexpr uint64_t lsbs = 0x0101010101010101ULL;
136 auto x = ctrl ^ (lsbs * hash);
137 uint64_t mask = (x - lsbs) & ~x & msbs;
138 EXPECT_EQ(0x0000000080800000, mask);
139
140 BitMask<uint64_t, 8, 3> b(mask);
141 EXPECT_EQ(*b, 2u);
142 }
143
144 TEST(BitMask, LeadingTrailing) {
145 EXPECT_EQ((BitMask<uint32_t, 16>(0x00001a40).LeadingZeros()), 3u);
146 EXPECT_EQ((BitMask<uint32_t, 16>(0x00001a40).TrailingZeros()), 6u);
147
148 EXPECT_EQ((BitMask<uint32_t, 16>(0x00000001).LeadingZeros()), 15u);
149 EXPECT_EQ((BitMask<uint32_t, 16>(0x00000001).TrailingZeros()), 0u);
150
151 EXPECT_EQ((BitMask<uint32_t, 16>(0x00008000).LeadingZeros()), 0u);
152 EXPECT_EQ((BitMask<uint32_t, 16>(0x00008000).TrailingZeros()), 15u);
153
154 EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x0000008080808000).LeadingZeros()), 3u);
155 EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x0000008080808000).TrailingZeros()), 1u);
156
157 EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x0000000000000080).LeadingZeros()), 7u);
158 EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x0000000000000080).TrailingZeros()), 0u);
159
160 EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x8000000000000000).LeadingZeros()), 0u);
161 EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x8000000000000000).TrailingZeros()), 7u);
162 }
163
164 TEST(Group, EmptyGroup) {
165 for (h2_t h = 0; h != 128; ++h) EXPECT_FALSE(Group{EmptyGroup<std::true_type>()}.Match(h));
166 }
167
168 TEST(Group, Match) {
169 PHMAP_IF_CONSTEXPR (Group::kWidth == 16) {
170 ctrl_t group[] = {kEmpty, 1, kDeleted, 3, kEmpty, 5, kSentinel, 7,
171 7, 5, 3, 1, 1, 1, 1, 1};
172 EXPECT_THAT(Group{group}.Match(0), ElementsAre());
173 EXPECT_THAT(Group{group}.Match(1), ElementsAre(1, 11, 12, 13, 14, 15));
174 EXPECT_THAT(Group{group}.Match(3), ElementsAre(3, 10));
175 EXPECT_THAT(Group{group}.Match(5), ElementsAre(5, 9));
176 EXPECT_THAT(Group{group}.Match(7), ElementsAre(7, 8));
177 } else PHMAP_IF_CONSTEXPR (Group::kWidth == 8) {
178 ctrl_t group[] = {kEmpty, 1, 2, kDeleted, 2, 1, kSentinel, 1};
179 EXPECT_THAT(Group{group}.Match(0), ElementsAre());
180 EXPECT_THAT(Group{group}.Match(1), ElementsAre(1, 5, 7));
181 EXPECT_THAT(Group{group}.Match(2), ElementsAre(2, 4));
182 } else {
183 FAIL() << "No test coverage for Group::kWidth==" << Group::kWidth;
184 }
185 }
186
187 TEST(Group, MatchEmpty) {
188 PHMAP_IF_CONSTEXPR (Group::kWidth == 16) {
189 ctrl_t group[] = {kEmpty, 1, kDeleted, 3, kEmpty, 5, kSentinel, 7,
190 7, 5, 3, 1, 1, 1, 1, 1};
191 EXPECT_THAT(Group{group}.MatchEmpty(), ElementsAre(0, 4));
192 } else PHMAP_IF_CONSTEXPR (Group::kWidth == 8) {
193 ctrl_t group[] = {kEmpty, 1, 2, kDeleted, 2, 1, kSentinel, 1};
194 EXPECT_THAT(Group{group}.MatchEmpty(), ElementsAre(0));
195 } else {
196 FAIL() << "No test coverage for Group::kWidth==" << Group::kWidth;
197 }
198 }
199
200 TEST(Group, MatchEmptyOrDeleted) {
201 PHMAP_IF_CONSTEXPR (Group::kWidth == 16) {
202 ctrl_t group[] = {kEmpty, 1, kDeleted, 3, kEmpty, 5, kSentinel, 7,
203 7, 5, 3, 1, 1, 1, 1, 1};
204 EXPECT_THAT(Group{group}.MatchEmptyOrDeleted(), ElementsAre(0, 2, 4));
205 } else PHMAP_IF_CONSTEXPR (Group::kWidth == 8) {
206 ctrl_t group[] = {kEmpty, 1, 2, kDeleted, 2, 1, kSentinel, 1};
207 EXPECT_THAT(Group{group}.MatchEmptyOrDeleted(), ElementsAre(0, 3));
208 } else {
209 FAIL() << "No test coverage for Group::kWidth==" << Group::kWidth;
210 }
211 }
212
213 TEST(Batch, DropDeletes) {
214 constexpr size_t kCapacity = 63;
215 constexpr size_t kGroupWidth = priv::Group::kWidth;
216 std::vector<ctrl_t> ctrl(kCapacity + 1 + kGroupWidth);
217 ctrl[kCapacity] = kSentinel;
218 std::vector<ctrl_t> pattern = {kEmpty, 2, kDeleted, 2, kEmpty, 1, kDeleted};
219 for (size_t i = 0; i != kCapacity; ++i) {
220 ctrl[i] = pattern[i % pattern.size()];
221 if (i < kGroupWidth - 1)
222 ctrl[i + kCapacity + 1] = pattern[i % pattern.size()];
223 }
224 ConvertDeletedToEmptyAndFullToDeleted(ctrl.data(), kCapacity);
225 ASSERT_EQ(ctrl[kCapacity], kSentinel);
226 for (size_t i = 0; i < kCapacity + 1 + kGroupWidth; ++i) {
227 ctrl_t expected = pattern[i % (kCapacity + 1) % pattern.size()];
228 if (i == kCapacity) expected = kSentinel;
229 if (expected == kDeleted) expected = kEmpty;
230 if (IsFull(expected)) expected = kDeleted;
231 EXPECT_EQ(ctrl[i], expected)
232 << i << " " << int{pattern[i % pattern.size()]};
233 }
234 }
235
236 TEST(Group, CountLeadingEmptyOrDeleted) {
237 const std::vector<ctrl_t> empty_examples = {kEmpty, kDeleted};
238 const std::vector<ctrl_t> full_examples = {0, 1, 2, 3, 5, 9, 127, kSentinel};
239
240 for (ctrl_t empty : empty_examples) {
241 std::vector<ctrl_t> e(Group::kWidth, empty);
242 EXPECT_EQ(Group::kWidth, (int)Group{e.data()}.CountLeadingEmptyOrDeleted());
243 for (ctrl_t full : full_examples) {
244 for (size_t i = 0; i != Group::kWidth; ++i) {
245 std::vector<ctrl_t> f(Group::kWidth, empty);
246 f[i] = full;
247 EXPECT_EQ(i, Group{f.data()}.CountLeadingEmptyOrDeleted());
248 }
249 std::vector<ctrl_t> f(Group::kWidth, empty);
250 f[Group::kWidth * 2 / 3] = full;
251 f[Group::kWidth / 2] = full;
252 EXPECT_EQ(
253 Group::kWidth / 2, (int)Group{f.data()}.CountLeadingEmptyOrDeleted());
254 }
255 }
256 }
257
258 struct IntPolicy {
259 using slot_type = int64_t;
260 using key_type = int64_t;
261 using init_type = int64_t;
262 using is_flat = std::false_type;
263
264 static void construct(void*, int64_t* slot, int64_t v) { *slot = v; }
265 static void destroy(void*, int64_t*) {}
266 static void transfer(void*, int64_t* new_slot, int64_t* old_slot) {
267 *new_slot = *old_slot;
268 }
269
270 static int64_t& element(slot_type* slot) { return *slot; }
271
272 template <class F>
273 static auto apply(F&& f, int64_t x) -> decltype(std::forward<F>(f)(x, x)) {
274 return std::forward<F>(f)(x, x);
275 }
276 };
277
278 #if PHMAP_HAVE_STD_STRING_VIEW
279 class StringPolicy {
280 template <class F, class K, class V,
281 class = typename std::enable_if<
282 std::is_convertible<const K&, std::string_view>::value>::type>
283 decltype(std::declval<F>()(
284 std::declval<const std::string_view&>(), std::piecewise_construct,
285 std::declval<std::tuple<K>>(),
286 std::declval<V>())) static apply_impl(F&& f,
287 std::pair<std::tuple<K>, V> p) {
288 const std::string_view& key = std::get<0>(p.first);
289 return std::forward<F>(f)(key, std::piecewise_construct, std::move(p.first),
290 std::move(p.second));
291 }
292
293 public:
294 struct slot_type {
295 struct ctor {};
296
297 template <class... Ts>
298 slot_type(ctor, Ts&&... ts) : pair(std::forward<Ts>(ts)...) {}
299
300 std::pair<std::string, std::string> pair;
301 };
302
303 using key_type = std::string;
304 using init_type = std::pair<std::string, std::string>;
305 using is_flat = std::false_type;
306
307 template <class allocator_type, class... Args>
308 static void construct(allocator_type* alloc, slot_type* slot, Args... args) {
309 std::allocator_traits<allocator_type>::construct(
310 *alloc, slot, typename slot_type::ctor(), std::forward<Args>(args)...);
311 }
312
313 template <class allocator_type>
314 static void destroy(allocator_type* alloc, slot_type* slot) {
315 std::allocator_traits<allocator_type>::destroy(*alloc, slot);
316 }
317
318 template <class allocator_type>
319 static void transfer(allocator_type* alloc, slot_type* new_slot,
320 slot_type* old_slot) {
321 construct(alloc, new_slot, std::move(old_slot->pair));
322 destroy(alloc, old_slot);
323 }
324
325 static std::pair<std::string, std::string>& element(slot_type* slot) {
326 return slot->pair;
327 }
328
329 template <class F, class... Args>
330 static auto apply(F&& f, Args&&... args)
331 -> decltype(apply_impl(std::forward<F>(f),
332 PairArgs(std::forward<Args>(args)...))) {
333 return apply_impl(std::forward<F>(f),
334 PairArgs(std::forward<Args>(args)...));
335 }
336 };
337
338 struct StringHash : phmap::Hash<std::string_view> {
339 using is_transparent = void;
340 };
341 struct StringEq : std::equal_to<std::string_view> {
342 using is_transparent = void;
343 };
344
345 struct StringTable
346 : raw_hash_set<StringPolicy, StringHash, StringEq, std::allocator<int>> {
347 using Base = typename StringTable::raw_hash_set;
348 StringTable() {}
349 using Base::Base;
350 };
351 #endif
352
353 struct IntTable
354 : raw_hash_set<IntPolicy, priv::hash_default_hash<int64_t>,
355 std::equal_to<int64_t>, std::allocator<int64_t>> {
356 using Base = typename IntTable::raw_hash_set;
357 IntTable() {}
358 using Base::Base;
359 };
360
361 template <typename T>
362 struct CustomAlloc : std::allocator<T> {
363 CustomAlloc() {}
364
365 template <typename U>
366 CustomAlloc(const CustomAlloc<U>& ) {}
367
368 template<class U> struct rebind {
369 using other = CustomAlloc<U>;
370 };
371 };
372
373 struct CustomAllocIntTable
374 : raw_hash_set<IntPolicy, priv::hash_default_hash<int64_t>,
375 std::equal_to<int64_t>, CustomAlloc<int64_t>> {
376 using Base = typename CustomAllocIntTable::raw_hash_set;
377 using Base::Base;
378 };
379
380 struct BadFastHash {
381 template <class T>
382 size_t operator()(const T&) const {
383 return 0;
384 }
385 };
386
387 struct BadTable : raw_hash_set<IntPolicy, BadFastHash, std::equal_to<int>,
388 std::allocator<int>> {
389 using Base = typename BadTable::raw_hash_set;
390 BadTable() {}
391 using Base::Base;
392 };
393
394 TEST(Table, Empty) {
395 IntTable t;
396 EXPECT_EQ(0, t.size());
397 EXPECT_TRUE(t.empty());
398 }
399
400 #ifdef __GNUC__
401 template <class T>
402 PHMAP_ATTRIBUTE_ALWAYS_INLINE inline void DoNotOptimize(const T& v) {
403 asm volatile("" : : "r,m"(v) : "memory");
404 }
405 #endif
406
407 TEST(Table, Prefetch) {
408 IntTable t;
409 t.emplace(1);
410 // Works for both present and absent keys.
411 t.prefetch(1);
412 t.prefetch(2);
413
414 // Do not run in debug mode, when prefetch is not implemented, or when
415 // sanitizers are enabled.
416 #if 0 && defined(NDEBUG) && defined(__GNUC__) && defined(__x86_64__) && \
417 !defined(ADDRESS_SANITIZER) && !defined(MEMORY_SANITIZER) && \
418 !defined(THREAD_SANITIZER) && !defined(UNDEFINED_BEHAVIOR_SANITIZER)&& \
419 !defined(__EMSCRIPTEN__)
420 const auto now = [] { return phmap::base_internal::CycleClock::Now(); };
421
422 // Make size enough to not fit in L2 cache (16.7 Mb)
423 static constexpr int size = 1 << 22;
424 for (int i = 0; i < size; ++i) t.insert(i);
425
426 int64_t no_prefetch = 0, prefetch = 0;
427 for (int iter = 0; iter < 10; ++iter) {
428 int64_t time = now();
429 for (int i = 0; i < size; ++i) {
430 DoNotOptimize(t.find(i));
431 }
432 no_prefetch += now() - time;
433
434 time = now();
435 for (int i = 0; i < size; ++i) {
436 t.prefetch(i + 20);
437 DoNotOptimize(t.find(i));
438 }
439 prefetch += now() - time;
440 }
441
442 // no_prefetch is at least 30% slower.
443 EXPECT_GE(1.0 * no_prefetch / prefetch, 1.3);
444 #endif
445 }
446
447 TEST(Table, LookupEmpty) {
448 IntTable t;
449 auto it = t.find(0);
450 EXPECT_TRUE(it == t.end());
451 }
452
453 TEST(Table, Insert1) {
454 IntTable t;
455 EXPECT_TRUE(t.find(0) == t.end());
456 auto res = t.emplace(0);
457 EXPECT_TRUE(res.second);
458 EXPECT_THAT(*res.first, 0);
459 EXPECT_EQ(1, t.size());
460 EXPECT_THAT(*t.find(0), 0);
461 }
462
463 TEST(Table, Insert2) {
464 IntTable t;
465 EXPECT_TRUE(t.find(0) == t.end());
466 auto res = t.emplace(0);
467 EXPECT_TRUE(res.second);
468 EXPECT_THAT(*res.first, 0);
469 EXPECT_EQ(1, t.size());
470 EXPECT_TRUE(t.find(1) == t.end());
471 res = t.emplace(1);
472 EXPECT_TRUE(res.second);
473 EXPECT_THAT(*res.first, 1);
474 EXPECT_EQ(2, t.size());
475 EXPECT_THAT(*t.find(0), 0);
476 EXPECT_THAT(*t.find(1), 1);
477 }
478
479 TEST(Table, InsertCollision) {
480 BadTable t;
481 EXPECT_TRUE(t.find(1) == t.end());
482 auto res = t.emplace(1);
483 EXPECT_TRUE(res.second);
484 EXPECT_THAT(*res.first, 1);
485 EXPECT_EQ(1, t.size());
486
487 EXPECT_TRUE(t.find(2) == t.end());
488 res = t.emplace(2);
489 EXPECT_THAT(*res.first, 2);
490 EXPECT_TRUE(res.second);
491 EXPECT_EQ(2, t.size());
492
493 EXPECT_THAT(*t.find(1), 1);
494 EXPECT_THAT(*t.find(2), 2);
495 }
496
497 // Test that we do not add existent element in case we need to search through
498 // many groups with deleted elements
499 TEST(Table, InsertCollisionAndFindAfterDelete) {
500 BadTable t; // all elements go to the same group.
501 // Have at least 2 groups with Group::kWidth collisions
502 // plus some extra collisions in the last group.
503 constexpr size_t kNumInserts = Group::kWidth * 2 + 5;
504 for (size_t i = 0; i < kNumInserts; ++i) {
505 auto res = t.emplace(i);
506 EXPECT_TRUE(res.second);
507 EXPECT_THAT(*res.first, i);
508 EXPECT_EQ(i + 1, t.size());
509 }
510
511 // Remove elements one by one and check
512 // that we still can find all other elements.
513 for (size_t i = 0; i < kNumInserts; ++i) {
514 EXPECT_EQ(1, t.erase(i)) << i;
515 for (size_t j = i + 1; j < kNumInserts; ++j) {
516 EXPECT_THAT(*t.find(j), j);
517 auto res = t.emplace(j);
518 EXPECT_FALSE(res.second) << i << " " << j;
519 EXPECT_THAT(*res.first, j);
520 EXPECT_EQ(kNumInserts - i - 1, t.size());
521 }
522 }
523 EXPECT_TRUE(t.empty());
524 }
525
526 #if PHMAP_HAVE_STD_STRING_VIEW
527 TEST(Table, LazyEmplace) {
528 StringTable t;
529 bool called = false;
530 auto it = t.lazy_emplace("abc", [&](const StringTable::constructor& f) {
531 called = true;
532 f("abc", "ABC");
533 });
534 EXPECT_TRUE(called);
535 EXPECT_THAT(*it, Pair("abc", "ABC"));
536 called = false;
537 it = t.lazy_emplace("abc", [&](const StringTable::constructor& f) {
538 called = true;
539 f("abc", "DEF");
540 });
541 EXPECT_FALSE(called);
542 EXPECT_THAT(*it, Pair("abc", "ABC"));
543 }
544 #endif
545
546 TEST(Table, ContainsEmpty) {
547 IntTable t;
548
549 EXPECT_FALSE(t.contains(0));
550 }
551
552 TEST(Table, Contains1) {
553 IntTable t;
554
555 EXPECT_TRUE(t.insert(0).second);
556 EXPECT_TRUE(t.contains(0));
557 EXPECT_FALSE(t.contains(1));
558
559 EXPECT_EQ(1, t.erase(0));
560 EXPECT_FALSE(t.contains(0));
561 }
562
563 TEST(Table, Contains2) {
564 IntTable t;
565
566 EXPECT_TRUE(t.insert(0).second);
567 EXPECT_TRUE(t.contains(0));
568 EXPECT_FALSE(t.contains(1));
569
570 t.clear();
571 EXPECT_FALSE(t.contains(0));
572 }
573
574 int decompose_constructed;
575 struct DecomposeType {
576 DecomposeType(int i_) : i(i_) { // NOLINT
577 ++decompose_constructed;
578 }
579
580 explicit DecomposeType(const char* d) : DecomposeType(*d) {}
581
582 int i;
583 };
584
585 struct DecomposeHash {
586 using is_transparent = void;
587 size_t operator()(DecomposeType a) const { return a.i; }
588 size_t operator()(int a) const { return a; }
589 size_t operator()(const char* a) const { return *a; }
590 };
591
592 struct DecomposeEq {
593 using is_transparent = void;
594 bool operator()(DecomposeType a, DecomposeType b) const { return a.i == b.i; }
595 bool operator()(DecomposeType a, int b) const { return a.i == b; }
596 bool operator()(DecomposeType a, const char* b) const { return a.i == *b; }
597 };
598
599 struct DecomposePolicy {
600 using slot_type = DecomposeType;
601 using key_type = DecomposeType;
602 using init_type = DecomposeType;
603 using is_flat = std::false_type;
604
605 template <typename T>
606 static void construct(void*, DecomposeType* slot, T&& v) {
607 *slot = DecomposeType(std::forward<T>(v));
608 }
609 static void destroy(void*, DecomposeType*) {}
610 static DecomposeType& element(slot_type* slot) { return *slot; }
611
612 template <class F, class T>
613 static auto apply(F&& f, const T& x) -> decltype(std::forward<F>(f)(x, x)) {
614 return std::forward<F>(f)(x, x);
615 }
616 };
617
618 template <typename Hash, typename Eq>
619 void TestDecompose(bool construct_three) {
620 DecomposeType elem{0};
621 const int one = 1;
622 const char* three_p = "3";
623 const auto& three = three_p;
624
625 raw_hash_set<DecomposePolicy, Hash, Eq, std::allocator<int>> set1;
626
627 decompose_constructed = 0;
628 int expected_constructed = 0;
629 EXPECT_EQ(expected_constructed, decompose_constructed);
630 set1.insert(elem);
631 EXPECT_EQ(expected_constructed, decompose_constructed);
632 set1.insert(1);
633 EXPECT_EQ(++expected_constructed, decompose_constructed);
634 set1.emplace("3");
635 EXPECT_EQ(++expected_constructed, decompose_constructed);
636 EXPECT_EQ(expected_constructed, decompose_constructed);
637
638 { // insert(T&&)
639 set1.insert(1);
640 EXPECT_EQ(expected_constructed, decompose_constructed);
641 }
642
643 { // insert(const T&)
644 set1.insert(one);
645 EXPECT_EQ(expected_constructed, decompose_constructed);
646 }
647
648 { // insert(hint, T&&)
649 set1.insert(set1.begin(), 1);
650 EXPECT_EQ(expected_constructed, decompose_constructed);
651 }
652
653 { // insert(hint, const T&)
654 set1.insert(set1.begin(), one);
655 EXPECT_EQ(expected_constructed, decompose_constructed);
656 }
657
658 { // emplace(...)
659 set1.emplace(1);
660 EXPECT_EQ(expected_constructed, decompose_constructed);
661 set1.emplace("3");
662 expected_constructed += construct_three;
663 EXPECT_EQ(expected_constructed, decompose_constructed);
664 set1.emplace(one);
665 EXPECT_EQ(expected_constructed, decompose_constructed);
666 set1.emplace(three);
667 expected_constructed += construct_three;
668 EXPECT_EQ(expected_constructed, decompose_constructed);
669 }
670
671 { // emplace_hint(...)
672 set1.emplace_hint(set1.begin(), 1);
673 EXPECT_EQ(expected_constructed, decompose_constructed);
674 set1.emplace_hint(set1.begin(), "3");
675 expected_constructed += construct_three;
676 EXPECT_EQ(expected_constructed, decompose_constructed);
677 set1.emplace_hint(set1.begin(), one);
678 EXPECT_EQ(expected_constructed, decompose_constructed);
679 set1.emplace_hint(set1.begin(), three);
680 expected_constructed += construct_three;
681 EXPECT_EQ(expected_constructed, decompose_constructed);
682 }
683 }
684
685 TEST(Table, Decompose) {
686 TestDecompose<DecomposeHash, DecomposeEq>(false);
687
688 struct TransparentHashIntOverload {
689 size_t operator()(DecomposeType a) const { return a.i; }
690 size_t operator()(int a) const { return a; }
691 };
692 struct TransparentEqIntOverload {
693 bool operator()(DecomposeType a, DecomposeType b) const {
694 return a.i == b.i;
695 }
696 bool operator()(DecomposeType a, int b) const { return a.i == b; }
697 };
698 TestDecompose<TransparentHashIntOverload, DecomposeEq>(true);
699 TestDecompose<TransparentHashIntOverload, TransparentEqIntOverload>(true);
700 TestDecompose<DecomposeHash, TransparentEqIntOverload>(true);
701 }
702
703 // Returns the largest m such that a table with m elements has the same number
704 // of buckets as a table with n elements.
705 size_t MaxDensitySize(size_t n) {
706 IntTable t;
707 t.reserve(n);
708 for (size_t i = 0; i != n; ++i) t.emplace(i);
709 const size_t c = t.bucket_count();
710 while (c == t.bucket_count()) t.emplace(n++);
711 return t.size() - 1;
712 }
713
714 #if 0
715 struct Modulo1000Hash {
716 size_t operator()(int x) const { return x % 1000; }
717 };
718
719 struct Modulo1000HashTable
720 : public raw_hash_set<IntPolicy, Modulo1000Hash, std::equal_to<int>,
721 std::allocator<int>> {};
722
723 // Test that rehash with no resize happen in case of many deleted slots.
724 TEST(Table, RehashWithNoResize) {
725 Modulo1000HashTable t;
726 // Adding the same length (and the same hash) strings
727 // to have at least kMinFullGroups groups
728 // with Group::kWidth collisions. Then fill up to MaxDensitySize;
729 const size_t kMinFullGroups = 7;
730 std::vector<int> keys;
731 for (size_t i = 0; i < MaxDensitySize(Group::kWidth * kMinFullGroups); ++i) {
732 int k = (int)i * 1000;
733 t.emplace(k);
734 keys.push_back(k);
735 }
736 const size_t capacity = t.capacity();
737
738 // Remove elements from all groups except the first and the last one.
739 // All elements removed from full groups will be marked as kDeleted.
740 const size_t erase_begin = Group::kWidth / 2;
741 const size_t erase_end = (t.size() / Group::kWidth - 1) * Group::kWidth;
742 for (size_t i = erase_begin; i < erase_end; ++i) {
743 EXPECT_EQ(1, t.erase(keys[i])) << i;
744 }
745 keys.erase(keys.begin() + erase_begin, keys.begin() + erase_end);
746
747 auto last_key = keys.back();
748 size_t last_key_num_probes = GetHashtableDebugNumProbes(t, last_key);
749
750 // Make sure that we have to make a lot of probes for last key.
751 ASSERT_GT(last_key_num_probes, kMinFullGroups);
752
753 int x = 1;
754 // Insert and erase one element, before inplace rehash happen.
755 while (last_key_num_probes == GetHashtableDebugNumProbes(t, last_key)) {
756 t.emplace(x);
757 ASSERT_EQ(capacity, t.capacity());
758 // All elements should be there.
759 ASSERT_TRUE(t.find(x) != t.end()) << x;
760 for (const auto& k : keys) {
761 ASSERT_TRUE(t.find(k) != t.end()) << k;
762 }
763 t.erase(x);
764 ++x;
765 }
766 }
767 #endif
768
769 TEST(Table, InsertEraseStressTest) {
770 IntTable t;
771 const size_t kMinElementCount = 250;
772 std::deque<size_t> keys;
773 size_t i = 0;
774 for (; i < MaxDensitySize(kMinElementCount); ++i) {
775 t.emplace(i);
776 keys.push_back(i);
777 }
778 const size_t kNumIterations = 1000000;
779 for (; i < kNumIterations; ++i) {
780 ASSERT_EQ(1, t.erase(keys.front()));
781 keys.pop_front();
782 t.emplace(i);
783 keys.push_back(i);
784 }
785 }
786
787 #if PHMAP_HAVE_STD_STRING_VIEW
788 TEST(Table, InsertOverloads) {
789 StringTable t;
790 // These should all trigger the insert(init_type) overload.
791 t.insert({{}, {}});
792 t.insert({"ABC", {}});
793 t.insert({"DEF", "!!!"});
794
795 EXPECT_THAT(t, UnorderedElementsAre(Pair("", ""), Pair("ABC", ""),
796 Pair("DEF", "!!!")));
797 }
798 #endif
799
800 TEST(Table, LargeTable) {
801 IntTable t;
802 for (int64_t i = 0; i != 100000; ++i) t.emplace(i << 40);
803 for (int64_t i = 0; i != 100000; ++i) ASSERT_EQ(i << 40, *t.find(i << 40));
804 }
805
806 // Timeout if copy is quadratic as it was in Rust.
807 TEST(Table, EnsureNonQuadraticAsInRust) {
808 static const size_t kLargeSize = 1 << 15;
809
810 IntTable t;
811 for (size_t i = 0; i != kLargeSize; ++i) {
812 t.insert(i);
813 }
814
815 // If this is quadratic, the test will timeout.
816 IntTable t2;
817 for (const auto& entry : t) t2.insert(entry);
818 }
819
820 TEST(Table, ClearBug) {
821 IntTable t;
822 constexpr size_t capacity = priv::Group::kWidth - 1;
823 constexpr size_t max_size = capacity / 2 + 1;
824 for (size_t i = 0; i < max_size; ++i) {
825 t.insert(i);
826 }
827 ASSERT_EQ(capacity, t.capacity());
828 intptr_t original = reinterpret_cast<intptr_t>(&*t.find(2));
829 t.clear();
830 ASSERT_EQ(capacity, t.capacity());
831 for (size_t i = 0; i < max_size; ++i) {
832 t.insert(i);
833 }
834 ASSERT_EQ(capacity, t.capacity());
835 intptr_t second = reinterpret_cast<intptr_t>(&*t.find(2));
836 // We are checking that original and second are close enough to each other
837 // that they are probably still in the same group. This is not strictly
838 // guaranteed.
839 EXPECT_LT(std::abs(original - second),
840 capacity * sizeof(IntTable::value_type));
841 }
842
843 TEST(Table, Erase) {
844 IntTable t;
845 EXPECT_TRUE(t.find(0) == t.end());
846 auto res = t.emplace(0);
847 EXPECT_TRUE(res.second);
848 EXPECT_EQ(1, t.size());
849 t.erase(res.first);
850 EXPECT_EQ(0, t.size());
851 EXPECT_TRUE(t.find(0) == t.end());
852 }
853
854 TEST(Table, EraseMaintainsValidIterator) {
855 IntTable t;
856 const int kNumElements = 100;
857 for (int i = 0; i < kNumElements; i ++) {
858 EXPECT_TRUE(t.emplace(i).second);
859 }
860 EXPECT_EQ(t.size(), kNumElements);
861
862 int num_erase_calls = 0;
863 auto it = t.begin();
864 while (it != t.end()) {
865 t.erase(it++);
866 num_erase_calls++;
867 }
868
869 EXPECT_TRUE(t.empty());
870 EXPECT_EQ(num_erase_calls, kNumElements);
871 }
872
873 // Collect N bad keys by following algorithm:
874 // 1. Create an empty table and reserve it to 2 * N.
875 // 2. Insert N random elements.
876 // 3. Take first Group::kWidth - 1 to bad_keys array.
877 // 4. Clear the table without resize.
878 // 5. Go to point 2 while N keys not collected
879 std::vector<int64_t> CollectBadMergeKeys(size_t N) {
880 static constexpr int kGroupSize = Group::kWidth - 1;
881
882 auto topk_range = [](size_t b, size_t e, IntTable* t) -> std::vector<int64_t> {
883 for (size_t i = b; i != e; ++i) {
884 t->emplace(i);
885 }
886 std::vector<int64_t> res;
887 res.reserve(kGroupSize);
888 auto it = t->begin();
889 for (size_t i = b; i != e && i != b + kGroupSize; ++i, ++it) {
890 res.push_back(*it);
891 }
892 return res;
893 };
894
895 std::vector<int64_t> bad_keys;
896 bad_keys.reserve(N);
897 IntTable t;
898 t.reserve(N * 2);
899
900 for (size_t b = 0; bad_keys.size() < N; b += N) {
901 auto keys = topk_range(b, b + N, &t);
902 bad_keys.insert(bad_keys.end(), keys.begin(), keys.end());
903 t.erase(t.begin(), t.end());
904 EXPECT_TRUE(t.empty());
905 }
906 return bad_keys;
907 }
908
909 struct ProbeStats {
910 // Number of elements with specific probe length over all tested tables.
911 std::vector<size_t> all_probes_histogram;
912 // Ratios total_probe_length/size for every tested table.
913 std::vector<double> single_table_ratios;
914
915 friend ProbeStats operator+(const ProbeStats& a, const ProbeStats& b) {
916 ProbeStats res = a;
917 res.all_probes_histogram.resize(std::max(res.all_probes_histogram.size(),
918 b.all_probes_histogram.size()));
919 std::transform(b.all_probes_histogram.begin(), b.all_probes_histogram.end(),
920 res.all_probes_histogram.begin(),
921 res.all_probes_histogram.begin(), std::plus<size_t>());
922 res.single_table_ratios.insert(res.single_table_ratios.end(),
923 b.single_table_ratios.begin(),
924 b.single_table_ratios.end());
925 return res;
926 }
927
928 // Average ratio total_probe_length/size over tables.
929 double AvgRatio() const {
930 return std::accumulate(single_table_ratios.begin(),
931 single_table_ratios.end(), 0.0) /
932 single_table_ratios.size();
933 }
934
935 // Maximum ratio total_probe_length/size over tables.
936 double MaxRatio() const {
937 return *std::max_element(single_table_ratios.begin(),
938 single_table_ratios.end());
939 }
940
941 // Percentile ratio total_probe_length/size over tables.
942 double PercentileRatio(double Percentile = 0.95) const {
943 auto r = single_table_ratios;
944 auto mid = r.begin() + static_cast<size_t>(r.size() * Percentile);
945 if (mid != r.end()) {
946 std::nth_element(r.begin(), mid, r.end());
947 return *mid;
948 } else {
949 return MaxRatio();
950 }
951 }
952
953 // Maximum probe length over all elements and all tables.
954 size_t MaxProbe() const { return all_probes_histogram.size(); }
955
956 // Fraction of elements with specified probe length.
957 std::vector<double> ProbeNormalizedHistogram() const {
958 double total_elements = (double)std::accumulate(all_probes_histogram.begin(),
959 all_probes_histogram.end(), 0ull);
960 std::vector<double> res;
961 for (size_t p : all_probes_histogram) {
962 res.push_back(p / total_elements);
963 }
964 return res;
965 }
966
967 size_t PercentileProbe(double Percentile = 0.99) const {
968 size_t idx = 0;
969 for (double p : ProbeNormalizedHistogram()) {
970 if (Percentile > p) {
971 Percentile -= p;
972 ++idx;
973 } else {
974 return idx;
975 }
976 }
977 return idx;
978 }
979
980 friend std::ostream& operator<<(std::ostream& out, const ProbeStats& s) {
981 out << "{AvgRatio:" << s.AvgRatio() << ", MaxRatio:" << s.MaxRatio()
982 << ", PercentileRatio:" << s.PercentileRatio()
983 << ", MaxProbe:" << s.MaxProbe() << ", Probes=[";
984 for (double p : s.ProbeNormalizedHistogram()) {
985 out << p << ",";
986 }
987 out << "]}";
988
989 return out;
990 }
991 };
992
993 struct ExpectedStats {
994 double avg_ratio;
995 double max_ratio;
996 std::vector<std::pair<double, double>> pecentile_ratios;
997 std::vector<std::pair<double, double>> pecentile_probes;
998
999 friend std::ostream& operator<<(std::ostream& out, const ExpectedStats& s) {
1000 out << "{AvgRatio:" << s.avg_ratio << ", MaxRatio:" << s.max_ratio
1001 << ", PercentileRatios: [";
1002 for (auto el : s.pecentile_ratios) {
1003 out << el.first << ":" << el.second << ", ";
1004 }
1005 out << "], PercentileProbes: [";
1006 for (auto el : s.pecentile_probes) {
1007 out << el.first << ":" << el.second << ", ";
1008 }
1009 out << "]}";
1010
1011 return out;
1012 }
1013 };
1014
1015 void VerifyStats(size_t size, const ExpectedStats& exp,
1016 const ProbeStats& stats) {
1017 EXPECT_LT(stats.AvgRatio(), exp.avg_ratio) << size << " " << stats;
1018 EXPECT_LT(stats.MaxRatio(), exp.max_ratio) << size << " " << stats;
1019 for (auto pr : exp.pecentile_ratios) {
1020 EXPECT_LE(stats.PercentileRatio(pr.first), pr.second)
1021 << size << " " << pr.first << " " << stats;
1022 }
1023
1024 for (auto pr : exp.pecentile_probes) {
1025 EXPECT_LE(stats.PercentileProbe(pr.first), pr.second)
1026 << size << " " << pr.first << " " << stats;
1027 }
1028 }
1029
1030 using ProbeStatsPerSize = std::map<size_t, ProbeStats>;
1031
1032 // Collect total ProbeStats on num_iters iterations of the following algorithm:
1033 // 1. Create new table and reserve it to keys.size() * 2
1034 // 2. Insert all keys xored with seed
1035 // 3. Collect ProbeStats from final table.
1036 ProbeStats CollectProbeStatsOnKeysXoredWithSeed(const std::vector<int64_t>& keys,
1037 size_t num_iters) {
1038 const size_t reserve_size = keys.size() * 2;
1039
1040 ProbeStats stats;
1041
1042 int64_t seed = 0x71b1a19b907d6e33;
1043 while (num_iters--) {
1044 seed = static_cast<int64_t>(static_cast<uint64_t>(seed) * 17 + 13);
1045 IntTable t1;
1046 t1.reserve(reserve_size);
1047 for (const auto& key : keys) {
1048 t1.emplace(key ^ seed);
1049 }
1050
1051 auto probe_histogram = GetHashtableDebugNumProbesHistogram(t1);
1052 stats.all_probes_histogram.resize(
1053 std::max(stats.all_probes_histogram.size(), probe_histogram.size()));
1054 std::transform(probe_histogram.begin(), probe_histogram.end(),
1055 stats.all_probes_histogram.begin(),
1056 stats.all_probes_histogram.begin(), std::plus<size_t>());
1057
1058 size_t total_probe_seq_length = 0;
1059 for (size_t i = 0; i < probe_histogram.size(); ++i) {
1060 total_probe_seq_length += i * probe_histogram[i];
1061 }
1062 stats.single_table_ratios.push_back(total_probe_seq_length * 1.0 /
1063 keys.size());
1064 t1.erase(t1.begin(), t1.end());
1065 }
1066 return stats;
1067 }
1068
1069 #if defined(__GNUC__) && !defined(__clang__)
1070 #pragma GCC diagnostic push
1071 #pragma GCC diagnostic ignored "-Wswitch"
1072 #endif
1073
1074 ExpectedStats XorSeedExpectedStats() {
1075 constexpr bool kRandomizesInserts =
1076 #ifdef NDEBUG
1077 false;
1078 #else // NDEBUG
1079 true;
1080 #endif // NDEBUG
1081
1082 // The effective load factor is larger in non-opt mode because we insert
1083 // elements out of order.
1084 PHMAP_IF_CONSTEXPR (priv::Group::kWidth == 8) {
1085 if (kRandomizesInserts) {
1086 return {0.05,
1087 1.0,
1088 {{0.95, 0.5}},
1089 {{0.95, 0}, {0.99, 2}, {0.999, 4}, {0.9999, 10}}};
1090 } else {
1091 return {0.05,
1092 2.0,
1093 {{0.95, 0.1}},
1094 {{0.95, 0}, {0.99, 2}, {0.999, 4}, {0.9999, 10}}};
1095 }
1096 }
1097 else {
1098 if (kRandomizesInserts) {
1099 return {0.1,
1100 1.0,
1101 {{0.95, 0.1}},
1102 {{0.95, 0}, {0.99, 1}, {0.999, 8}, {0.9999, 15}}};
1103 } else {
1104 return {0.05,
1105 1.0,
1106 {{0.95, 0.05}},
1107 {{0.95, 0}, {0.99, 1}, {0.999, 4}, {0.9999, 10}}};
1108 }
1109 }
1110 //PHMAP_RAW_LOG(FATAL, "%s", "Unknown Group width");
1111 return {};
1112 }
1113
1114 #if defined(__GNUC__) && !defined(__clang__)
1115 #pragma GCC diagnostic pop
1116 #endif
1117
1118
1119 TEST(Table, DISABLED_EnsureNonQuadraticTopNXorSeedByProbeSeqLength) {
1120 ProbeStatsPerSize stats;
1121 std::vector<size_t> sizes = {Group::kWidth << 5, Group::kWidth << 10};
1122 for (size_t size : sizes) {
1123 stats[size] =
1124 CollectProbeStatsOnKeysXoredWithSeed(CollectBadMergeKeys(size), 200);
1125 }
1126 auto expected = XorSeedExpectedStats();
1127 for (size_t size : sizes) {
1128 auto& stat = stats[size];
1129 VerifyStats(size, expected, stat);
1130 }
1131 }
1132
1133 // Collect total ProbeStats on num_iters iterations of the following algorithm:
1134 // 1. Create new table
1135 // 2. Select 10% of keys and insert 10 elements key * 17 + j * 13
1136 // 3. Collect ProbeStats from final table
1137 ProbeStats CollectProbeStatsOnLinearlyTransformedKeys(
1138 const std::vector<int64_t>& keys, size_t num_iters) {
1139 ProbeStats stats;
1140
1141 std::random_device rd;
1142 std::mt19937 rng(rd());
1143 auto linear_transform = [](size_t x, size_t y) { return x * 17 + y * 13; };
1144 std::uniform_int_distribution<size_t> dist(0, keys.size()-1);
1145 while (num_iters--) {
1146 IntTable t1;
1147 size_t num_keys = keys.size() / 10;
1148 size_t start = dist(rng);
1149 for (size_t i = 0; i != num_keys; ++i) {
1150 for (size_t j = 0; j != 10; ++j) {
1151 t1.emplace(linear_transform(keys[(i + start) % keys.size()], j));
1152 }
1153 }
1154
1155 auto probe_histogram = GetHashtableDebugNumProbesHistogram(t1);
1156 stats.all_probes_histogram.resize(
1157 std::max(stats.all_probes_histogram.size(), probe_histogram.size()));
1158 std::transform(probe_histogram.begin(), probe_histogram.end(),
1159 stats.all_probes_histogram.begin(),
1160 stats.all_probes_histogram.begin(), std::plus<size_t>());
1161
1162 size_t total_probe_seq_length = 0;
1163 for (size_t i = 0; i < probe_histogram.size(); ++i) {
1164 total_probe_seq_length += i * probe_histogram[i];
1165 }
1166 stats.single_table_ratios.push_back(total_probe_seq_length * 1.0 /
1167 t1.size());
1168 t1.erase(t1.begin(), t1.end());
1169 }
1170 return stats;
1171 }
1172
1173 #if defined(__GNUC__) && !defined(__clang__)
1174 #pragma GCC diagnostic push
1175 #pragma GCC diagnostic ignored "-Wswitch"
1176 #endif
1177
1178 ExpectedStats LinearTransformExpectedStats() {
1179 constexpr bool kRandomizesInserts =
1180 #ifdef NDEBUG
1181 false;
1182 #else // NDEBUG
1183 true;
1184 #endif // NDEBUG
1185
1186 // The effective load factor is larger in non-opt mode because we insert
1187 // elements out of order.
1188 PHMAP_IF_CONSTEXPR (priv::Group::kWidth == 8) {
1189 if (kRandomizesInserts) {
1190 return {0.1,
1191 0.5,
1192 {{0.95, 0.3}},
1193 {{0.95, 0}, {0.99, 1}, {0.999, 8}, {0.9999, 15}}};
1194 } else {
1195 return {0.15,
1196 0.5,
1197 {{0.95, 0.3}},
1198 {{0.95, 0}, {0.99, 3}, {0.999, 15}, {0.9999, 25}}};
1199 }
1200 } else {
1201 if (kRandomizesInserts) {
1202 return {0.1,
1203 0.4,
1204 {{0.95, 0.3}},
1205 {{0.95, 0}, {0.99, 1}, {0.999, 8}, {0.9999, 15}}};
1206 } else {
1207 return {0.05,
1208 0.2,
1209 {{0.95, 0.1}},
1210 {{0.95, 0}, {0.99, 1}, {0.999, 6}, {0.9999, 10}}};
1211 }
1212 }
1213 //PHMAP_RAW_LOG(FATAL, "%s", "Unknown Group width");
1214 return {};
1215 }
1216
1217 #if defined(__GNUC__) && !defined(__clang__)
1218 #pragma GCC diagnostic pop
1219 #endif
1220
1221 TEST(Table, DISABLED_EnsureNonQuadraticTopNLinearTransformByProbeSeqLength) {
1222 ProbeStatsPerSize stats;
1223 std::vector<size_t> sizes = {Group::kWidth << 5, Group::kWidth << 10};
1224 for (size_t size : sizes) {
1225 stats[size] = CollectProbeStatsOnLinearlyTransformedKeys(
1226 CollectBadMergeKeys(size), 300);
1227 }
1228 auto expected = LinearTransformExpectedStats();
1229 for (size_t size : sizes) {
1230 auto& stat = stats[size];
1231 VerifyStats(size, expected, stat);
1232 }
1233 }
1234
1235 TEST(Table, EraseCollision) {
1236 BadTable t;
1237
1238 // 1 2 3
1239 t.emplace(1);
1240 t.emplace(2);
1241 t.emplace(3);
1242 EXPECT_THAT(*t.find(1), 1);
1243 EXPECT_THAT(*t.find(2), 2);
1244 EXPECT_THAT(*t.find(3), 3);
1245 EXPECT_EQ(3, t.size());
1246
1247 // 1 DELETED 3
1248 t.erase(t.find(2));
1249 EXPECT_THAT(*t.find(1), 1);
1250 EXPECT_TRUE(t.find(2) == t.end());
1251 EXPECT_THAT(*t.find(3), 3);
1252 EXPECT_EQ(2, t.size());
1253
1254 // DELETED DELETED 3
1255 t.erase(t.find(1));
1256 EXPECT_TRUE(t.find(1) == t.end());
1257 EXPECT_TRUE(t.find(2) == t.end());
1258 EXPECT_THAT(*t.find(3), 3);
1259 EXPECT_EQ(1, t.size());
1260
1261 // DELETED DELETED DELETED
1262 t.erase(t.find(3));
1263 EXPECT_TRUE(t.find(1) == t.end());
1264 EXPECT_TRUE(t.find(2) == t.end());
1265 EXPECT_TRUE(t.find(3) == t.end());
1266 EXPECT_EQ(0, t.size());
1267 }
1268
1269 TEST(Table, EraseInsertProbing) {
1270 BadTable t(100);
1271
1272 // 1 2 3 4
1273 t.emplace(1);
1274 t.emplace(2);
1275 t.emplace(3);
1276 t.emplace(4);
1277
1278 // 1 DELETED 3 DELETED
1279 t.erase(t.find(2));
1280 t.erase(t.find(4));
1281
1282 // 1 10 3 11 12
1283 t.emplace(10);
1284 t.emplace(11);
1285 t.emplace(12);
1286
1287 EXPECT_EQ(5, t.size());
1288 EXPECT_THAT(t, UnorderedElementsAre(1, 10, 3, 11, 12));
1289 }
1290
1291 TEST(Table, Clear) {
1292 IntTable t;
1293 EXPECT_TRUE(t.find(0) == t.end());
1294 t.clear();
1295 EXPECT_TRUE(t.find(0) == t.end());
1296 auto res = t.emplace(0);
1297 EXPECT_TRUE(res.second);
1298 EXPECT_EQ(1, t.size());
1299 t.clear();
1300 EXPECT_EQ(0, t.size());
1301 EXPECT_TRUE(t.find(0) == t.end());
1302 }
1303
1304 TEST(Table, Swap) {
1305 IntTable t;
1306 EXPECT_TRUE(t.find(0) == t.end());
1307 auto res = t.emplace(0);
1308 EXPECT_TRUE(res.second);
1309 EXPECT_EQ(1, t.size());
1310 IntTable u;
1311 t.swap(u);
1312 EXPECT_EQ(0, t.size());
1313 EXPECT_EQ(1, u.size());
1314 EXPECT_TRUE(t.find(0) == t.end());
1315 EXPECT_THAT(*u.find(0), 0);
1316 }
1317
1318 TEST(Table, Rehash) {
1319 IntTable t;
1320 EXPECT_TRUE(t.find(0) == t.end());
1321 t.emplace(0);
1322 t.emplace(1);
1323 EXPECT_EQ(2, t.size());
1324 t.rehash(128);
1325 EXPECT_EQ(2, t.size());
1326 EXPECT_THAT(*t.find(0), 0);
1327 EXPECT_THAT(*t.find(1), 1);
1328 }
1329
1330 TEST(Table, RehashDoesNotRehashWhenNotNecessary) {
1331 IntTable t;
1332 t.emplace(0);
1333 t.emplace(1);
1334 auto* p = &*t.find(0);
1335 t.rehash(1);
1336 EXPECT_EQ(p, &*t.find(0));
1337 }
1338
1339 TEST(Table, RehashZeroDoesNotAllocateOnEmptyTable) {
1340 IntTable t;
1341 t.rehash(0);
1342 EXPECT_EQ(0, t.bucket_count());
1343 }
1344
1345 TEST(Table, RehashZeroDeallocatesEmptyTable) {
1346 IntTable t;
1347 t.emplace(0);
1348 t.clear();
1349 EXPECT_NE(0, t.bucket_count());
1350 t.rehash(0);
1351 EXPECT_EQ(0, t.bucket_count());
1352 }
1353
1354 TEST(Table, RehashZeroForcesRehash) {
1355 IntTable t;
1356 t.emplace(0);
1357 t.emplace(1);
1358 auto* p = &*t.find(0);
1359 t.rehash(0);
1360 EXPECT_NE(p, &*t.find(0));
1361 }
1362
1363 #if PHMAP_HAVE_STD_STRING_VIEW
1364 TEST(Table, ConstructFromInitList) {
1365 using P = std::pair<std::string, std::string>;
1366 struct Q {
1367 operator P() const { return {}; }
1368 };
1369 StringTable t = {P(), Q(), {}, {{}, {}}};
1370 }
1371 #endif
1372
1373 TEST(Table, CopyConstruct) {
1374 IntTable t;
1375 t.emplace(0);
1376 EXPECT_EQ(1, t.size());
1377 {
1378 IntTable u(t);
1379 EXPECT_EQ(1, u.size());
1380 EXPECT_THAT(*u.find(0), 0);
1381 }
1382 {
1383 IntTable u{t};
1384 EXPECT_EQ(1, u.size());
1385 EXPECT_THAT(*u.find(0), 0);
1386 }
1387 {
1388 IntTable u = t;
1389 EXPECT_EQ(1, u.size());
1390 EXPECT_THAT(*u.find(0), 0);
1391 }
1392 }
1393
1394 #if PHMAP_HAVE_STD_STRING_VIEW
1395 TEST(Table, CopyConstructWithAlloc) {
1396 StringTable t;
1397 t.emplace("a", "b");
1398 EXPECT_EQ(1, t.size());
1399 StringTable u(t, Alloc<std::pair<std::string, std::string>>());
1400 EXPECT_EQ(1, u.size());
1401 EXPECT_THAT(*u.find("a"), Pair("a", "b"));
1402 }
1403
1404 struct ExplicitAllocIntTable
1405 : raw_hash_set<IntPolicy, priv::hash_default_hash<int64_t>,
1406 std::equal_to<int64_t>, Alloc<int64_t>> {
1407 ExplicitAllocIntTable() {}
1408 };
1409
1410 TEST(Table, AllocWithExplicitCtor) {
1411 ExplicitAllocIntTable t;
1412 EXPECT_EQ(0, t.size());
1413 }
1414
1415 TEST(Table, MoveConstruct) {
1416 {
1417 StringTable t;
1418 t.emplace("a", "b");
1419 EXPECT_EQ(1, t.size());
1420
1421 StringTable u(std::move(t));
1422 EXPECT_EQ(1, u.size());
1423 EXPECT_THAT(*u.find("a"), Pair("a", "b"));
1424 }
1425 {
1426 StringTable t;
1427 t.emplace("a", "b");
1428 EXPECT_EQ(1, t.size());
1429
1430 StringTable u{std::move(t)};
1431 EXPECT_EQ(1, u.size());
1432 EXPECT_THAT(*u.find("a"), Pair("a", "b"));
1433 }
1434 {
1435 StringTable t;
1436 t.emplace("a", "b");
1437 EXPECT_EQ(1, t.size());
1438
1439 StringTable u = std::move(t);
1440 EXPECT_EQ(1, u.size());
1441 EXPECT_THAT(*u.find("a"), Pair("a", "b"));
1442 }
1443 }
1444
1445 TEST(Table, MoveConstructWithAlloc) {
1446 StringTable t;
1447 t.emplace("a", "b");
1448 EXPECT_EQ(1, t.size());
1449 StringTable u(std::move(t), Alloc<std::pair<std::string, std::string>>());
1450 EXPECT_EQ(1, u.size());
1451 EXPECT_THAT(*u.find("a"), Pair("a", "b"));
1452 }
1453
1454 TEST(Table, CopyAssign) {
1455 StringTable t;
1456 t.emplace("a", "b");
1457 EXPECT_EQ(1, t.size());
1458 StringTable u;
1459 u = t;
1460 EXPECT_EQ(1, u.size());
1461 EXPECT_THAT(*u.find("a"), Pair("a", "b"));
1462 }
1463
1464 TEST(Table, CopySelfAssign) {
1465 StringTable t;
1466 t.emplace("a", "b");
1467 EXPECT_EQ(1, t.size());
1468 t = *&t;
1469 EXPECT_EQ(1, t.size());
1470 EXPECT_THAT(*t.find("a"), Pair("a", "b"));
1471 }
1472
1473 TEST(Table, MoveAssign) {
1474 StringTable t;
1475 t.emplace("a", "b");
1476 EXPECT_EQ(1, t.size());
1477 StringTable u;
1478 u = std::move(t);
1479 EXPECT_EQ(1, u.size());
1480 EXPECT_THAT(*u.find("a"), Pair("a", "b"));
1481 }
1482
1483 TEST(Table, Equality) {
1484 StringTable t;
1485 std::vector<std::pair<std::string, std::string>> v = {{"a", "b"},
1486 {"aa", "bb"}};
1487 t.insert(std::begin(v), std::end(v));
1488 StringTable u = t;
1489 EXPECT_EQ(u, t);
1490 }
1491
1492 TEST(Table, Equality2) {
1493 StringTable t;
1494 std::vector<std::pair<std::string, std::string>> v1 = {{"a", "b"},
1495 {"aa", "bb"}};
1496 t.insert(std::begin(v1), std::end(v1));
1497 StringTable u;
1498 std::vector<std::pair<std::string, std::string>> v2 = {{"a", "a"},
1499 {"aa", "aa"}};
1500 u.insert(std::begin(v2), std::end(v2));
1501 EXPECT_NE(u, t);
1502 }
1503
1504 TEST(Table, Equality3) {
1505 StringTable t;
1506 std::vector<std::pair<std::string, std::string>> v1 = {{"b", "b"},
1507 {"bb", "bb"}};
1508 t.insert(std::begin(v1), std::end(v1));
1509 StringTable u;
1510 std::vector<std::pair<std::string, std::string>> v2 = {{"a", "a"},
1511 {"aa", "aa"}};
1512 u.insert(std::begin(v2), std::end(v2));
1513 EXPECT_NE(u, t);
1514 }
1515 #endif
1516
1517 TEST(Table, NumDeletedRegression) {
1518 IntTable t;
1519 t.emplace(0);
1520 t.erase(t.find(0));
1521 // construct over a deleted slot.
1522 t.emplace(0);
1523 t.clear();
1524 }
1525
1526 TEST(Table, FindFullDeletedRegression) {
1527 IntTable t;
1528 for (int i = 0; i < 1000; ++i) {
1529 t.emplace(i);
1530 t.erase(t.find(i));
1531 }
1532 EXPECT_EQ(0, t.size());
1533 }
1534
1535 TEST(Table, ReplacingDeletedSlotDoesNotRehash) {
1536 size_t n;
1537 {
1538 // Compute n such that n is the maximum number of elements before rehash.
1539 IntTable t;
1540 t.emplace(0);
1541 size_t c = t.bucket_count();
1542 for (n = 1; c == t.bucket_count(); ++n) t.emplace(n);
1543 --n;
1544 }
1545 IntTable t;
1546 t.rehash(n);
1547 const size_t c = t.bucket_count();
1548 for (size_t i = 0; i != n; ++i) t.emplace(i);
1549 EXPECT_EQ(c, t.bucket_count()) << "rehashing threshold = " << n;
1550 t.erase(0);
1551 t.emplace(0);
1552 EXPECT_EQ(c, t.bucket_count()) << "rehashing threshold = " << n;
1553 }
1554
1555 #if PHMAP_HAVE_STD_STRING_VIEW
1556 TEST(Table, NoThrowMoveConstruct) {
1557 ASSERT_TRUE(
1558 std::is_nothrow_copy_constructible<phmap::Hash<std::string_view>>::value);
1559 ASSERT_TRUE(std::is_nothrow_copy_constructible<
1560 std::equal_to<std::string_view>>::value);
1561 ASSERT_TRUE(std::is_nothrow_copy_constructible<std::allocator<int>>::value);
1562 EXPECT_TRUE(std::is_nothrow_move_constructible<StringTable>::value);
1563 }
1564
1565 TEST(Table, NoThrowMoveAssign) {
1566 ASSERT_TRUE(
1567 std::is_nothrow_move_assignable<phmap::Hash<std::string_view>>::value);
1568 ASSERT_TRUE(
1569 std::is_nothrow_move_assignable<std::equal_to<std::string_view>>::value);
1570 ASSERT_TRUE(std::is_nothrow_move_assignable<std::allocator<int>>::value);
1571 ASSERT_TRUE(
1572 phmap::allocator_traits<std::allocator<int>>::is_always_equal::value);
1573 EXPECT_TRUE(std::is_nothrow_move_assignable<StringTable>::value);
1574 }
1575
1576 TEST(Table, NoThrowSwappable) {
1577 ASSERT_TRUE(
1578 priv::IsNoThrowSwappable<phmap::Hash<std::string_view>>());
1579 ASSERT_TRUE(priv::IsNoThrowSwappable<
1580 std::equal_to<std::string_view>>());
1581 ASSERT_TRUE(priv::IsNoThrowSwappable<std::allocator<int>>());
1582 EXPECT_TRUE(priv::IsNoThrowSwappable<StringTable>());
1583 }
1584 #endif
1585
1586 TEST(Table, HeterogeneousLookup) {
1587 struct Hash {
1588 size_t operator()(int64_t i) const { return i; }
1589 size_t operator()(double i) const {
1590 ADD_FAILURE();
1591 return (size_t)i;
1592 }
1593 };
1594 struct Eq {
1595 bool operator()(int64_t a, int64_t b) const { return a == b; }
1596 bool operator()(double a, int64_t b) const {
1597 ADD_FAILURE();
1598 return a == b;
1599 }
1600 bool operator()(int64_t a, double b) const {
1601 ADD_FAILURE();
1602 return a == b;
1603 }
1604 bool operator()(double a, double b) const {
1605 ADD_FAILURE();
1606 return a == b;
1607 }
1608 };
1609
1610 struct THash {
1611 using is_transparent = void;
1612 size_t operator()(int64_t i) const { return i; }
1613 size_t operator()(double i) const { return (size_t)i; }
1614 };
1615 struct TEq {
1616 using is_transparent = void;
1617 bool operator()(int64_t a, int64_t b) const { return a == b; }
1618 bool operator()(double a, int64_t b) const { return a == b; }
1619 bool operator()(int64_t a, double b) const { return a == b; }
1620 bool operator()(double a, double b) const { return a == b; }
1621 };
1622
1623 raw_hash_set<IntPolicy, Hash, Eq, Alloc<int64_t>> s{0, 1, 2};
1624 // It will convert to int64_t before the query.
1625 EXPECT_EQ(1, *s.find((int)double{1.1}));
1626
1627 raw_hash_set<IntPolicy, THash, TEq, Alloc<int64_t>> ts{0, 1, 2};
1628 // It will try to use the double, and fail to find the object.
1629 EXPECT_TRUE(ts.find(1.1) == ts.end());
1630 }
1631
1632 template <class Table>
1633 using CallFind = decltype(std::declval<Table&>().find(17));
1634
1635 template <class Table>
1636 using CallErase = decltype(std::declval<Table&>().erase(17));
1637
1638 template <class Table>
1639 using CallExtract = decltype(std::declval<Table&>().extract(17));
1640
1641 template <class Table>
1642 using CallPrefetch = decltype(std::declval<Table&>().prefetch(17));
1643
1644 template <class Table>
1645 using CallCount = decltype(std::declval<Table&>().count(17));
1646
1647 template <template <typename> class C, class Table, class = void>
1648 struct VerifyResultOf : std::false_type {};
1649
1650 template <template <typename> class C, class Table>
1651 struct VerifyResultOf<C, Table, phmap::void_t<C<Table>>> : std::true_type {};
1652
1653 #if PHMAP_HAVE_STD_STRING_VIEW
1654 TEST(Table, HeterogeneousLookupOverloads) {
1655 using NonTransparentTable =
1656 raw_hash_set<StringPolicy, phmap::Hash<std::string_view>,
1657 std::equal_to<std::string_view>, std::allocator<int>>;
1658
1659 EXPECT_FALSE((VerifyResultOf<CallFind, NonTransparentTable>()));
1660 EXPECT_FALSE((VerifyResultOf<CallErase, NonTransparentTable>()));
1661 EXPECT_FALSE((VerifyResultOf<CallExtract, NonTransparentTable>()));
1662 EXPECT_FALSE((VerifyResultOf<CallPrefetch, NonTransparentTable>()));
1663 EXPECT_FALSE((VerifyResultOf<CallCount, NonTransparentTable>()));
1664
1665 using TransparentTable = raw_hash_set<
1666 StringPolicy,
1667 phmap::priv::hash_default_hash<std::string_view>,
1668 phmap::priv::hash_default_eq<std::string_view>,
1669 std::allocator<int>>;
1670
1671 EXPECT_TRUE((VerifyResultOf<CallFind, TransparentTable>()));
1672 EXPECT_TRUE((VerifyResultOf<CallErase, TransparentTable>()));
1673 EXPECT_TRUE((VerifyResultOf<CallExtract, TransparentTable>()));
1674 EXPECT_TRUE((VerifyResultOf<CallPrefetch, TransparentTable>()));
1675 EXPECT_TRUE((VerifyResultOf<CallCount, TransparentTable>()));
1676 }
1677
1678 // TODO(alkis): Expand iterator tests.
1679 TEST(Iterator, IsDefaultConstructible) {
1680 StringTable::iterator i;
1681 EXPECT_TRUE(i == StringTable::iterator());
1682 }
1683
1684 TEST(ConstIterator, IsDefaultConstructible) {
1685 StringTable::const_iterator i;
1686 EXPECT_TRUE(i == StringTable::const_iterator());
1687 }
1688
1689 TEST(Iterator, ConvertsToConstIterator) {
1690 StringTable::iterator i;
1691 EXPECT_TRUE(i == StringTable::const_iterator());
1692 }
1693
1694 TEST(Iterator, Iterates) {
1695 IntTable t;
1696 for (size_t i = 3; i != 6; ++i) EXPECT_TRUE(t.emplace(i).second);
1697 EXPECT_THAT(t, UnorderedElementsAre(3, 4, 5));
1698 }
1699
1700 TEST(Table, Merge) {
1701 StringTable t1, t2;
1702 t1.emplace("0", "-0");
1703 t1.emplace("1", "-1");
1704 t2.emplace("0", "~0");
1705 t2.emplace("2", "~2");
1706
1707 EXPECT_THAT(t1, UnorderedElementsAre(Pair("0", "-0"), Pair("1", "-1")));
1708 EXPECT_THAT(t2, UnorderedElementsAre(Pair("0", "~0"), Pair("2", "~2")));
1709
1710 t1.merge(t2);
1711 EXPECT_THAT(t1, UnorderedElementsAre(Pair("0", "-0"), Pair("1", "-1"),
1712 Pair("2", "~2")));
1713 EXPECT_THAT(t2, UnorderedElementsAre(Pair("0", "~0")));
1714 }
1715
1716 TEST(Nodes, EmptyNodeType) {
1717 using node_type = StringTable::node_type;
1718 node_type n;
1719 EXPECT_FALSE(n);
1720 EXPECT_TRUE(n.empty());
1721
1722 EXPECT_TRUE((std::is_same<node_type::allocator_type,
1723 StringTable::allocator_type>::value));
1724 }
1725
1726 TEST(Nodes, ExtractInsert) {
1727 constexpr char k0[] = "Very long std::string zero.";
1728 constexpr char k1[] = "Very long std::string one.";
1729 constexpr char k2[] = "Very long std::string two.";
1730 StringTable t = {{k0, ""}, {k1, ""}, {k2, ""}};
1731 EXPECT_THAT(t,
1732 UnorderedElementsAre(Pair(k0, ""), Pair(k1, ""), Pair(k2, "")));
1733
1734 auto node = t.extract(k0);
1735 EXPECT_THAT(t, UnorderedElementsAre(Pair(k1, ""), Pair(k2, "")));
1736 EXPECT_TRUE(node);
1737 EXPECT_FALSE(node.empty());
1738
1739 StringTable t2;
1740 StringTable::insert_return_type res = t2.insert(std::move(node));
1741 EXPECT_TRUE(res.inserted);
1742 EXPECT_THAT(*res.position, Pair(k0, ""));
1743 EXPECT_FALSE(res.node);
1744 EXPECT_THAT(t2, UnorderedElementsAre(Pair(k0, "")));
1745
1746 // Not there.
1747 EXPECT_THAT(t, UnorderedElementsAre(Pair(k1, ""), Pair(k2, "")));
1748 node = t.extract("Not there!");
1749 EXPECT_THAT(t, UnorderedElementsAre(Pair(k1, ""), Pair(k2, "")));
1750 EXPECT_FALSE(node);
1751
1752 // Inserting nothing.
1753 res = t2.insert(std::move(node));
1754 EXPECT_FALSE(res.inserted);
1755 EXPECT_EQ(res.position, t2.end());
1756 EXPECT_FALSE(res.node);
1757 EXPECT_THAT(t2, UnorderedElementsAre(Pair(k0, "")));
1758
1759 t.emplace(k0, "1");
1760 node = t.extract(k0);
1761
1762 // Insert duplicate.
1763 res = t2.insert(std::move(node));
1764 EXPECT_FALSE(res.inserted);
1765 EXPECT_THAT(*res.position, Pair(k0, ""));
1766 EXPECT_TRUE(res.node);
1767 EXPECT_FALSE(node);
1768 }
1769
1770 #endif
1771
1772 IntTable MakeSimpleTable(size_t size) {
1773 IntTable t;
1774 while (t.size() < size) t.insert(t.size());
1775 return t;
1776 }
1777
1778 std::vector<int> OrderOfIteration(const IntTable& t) {
1779 return {t.begin(), t.end()};
1780 }
1781
1782 // These IterationOrderChanges tests depend on non-deterministic behavior.
1783 // We are injecting non-determinism from the pointer of the table, but do so in
1784 // a way that only the page matters. We have to retry enough times to make sure
1785 // we are touching different memory pages to cause the ordering to change.
1786 // We also need to keep the old tables around to avoid getting the same memory
1787 // blocks over and over.
1788 // not randomizing in phmap
1789 TEST(Table, IterationOrderChangesByInstance) {
1790 for (size_t size : {2, 6, 12, 20}) {
1791 const auto reference_table = MakeSimpleTable(size);
1792 const auto reference = OrderOfIteration(reference_table);
1793
1794 std::vector<IntTable> tables;
1795 bool found_difference = false;
1796 for (int i = 0; !found_difference && i < 5000; ++i) {
1797 tables.push_back(MakeSimpleTable(size));
1798 found_difference = OrderOfIteration(tables.back()) != reference;
1799 }
1800 if (!found_difference) {
1801 FAIL()
1802 << "Iteration order remained the same across many attempts with size "
1803 << size;
1804 }
1805 }
1806 }
1807
1808 // not randomizing in phmap
1809 TEST(Table, IterationOrderChangesOnRehash) {
1810 std::vector<IntTable> garbage;
1811 for (int i = 0; i < 5000; ++i) {
1812 auto t = MakeSimpleTable(20);
1813 const auto reference = OrderOfIteration(t);
1814 // Force rehash to the same size.
1815 t.rehash(0);
1816 auto trial = OrderOfIteration(t);
1817 if (trial != reference) {
1818 // We are done.
1819 return;
1820 }
1821 garbage.push_back(std::move(t));
1822 }
1823 FAIL() << "Iteration order remained the same across many attempts.";
1824 }
1825
1826 // Verify that pointers are invalidated as soon as a second element is inserted.
1827 // This prevents dependency on pointer stability on small tables.
1828 TEST(Table, UnstablePointers) {
1829 IntTable table;
1830
1831 const auto addr = [&](int i) {
1832 return reinterpret_cast<uintptr_t>(&*table.find(i));
1833 };
1834
1835 table.insert(0);
1836 const uintptr_t old_ptr = addr(0);
1837
1838 // This causes a rehash.
1839 table.insert(1);
1840
1841 EXPECT_NE(old_ptr, addr(0));
1842 }
1843
1844 // Confirm that we assert if we try to erase() end().
1845 TEST(TableDeathTest, EraseOfEndAsserts) {
1846 // Use an assert with side-effects to figure out if they are actually enabled.
1847 bool assert_enabled = false;
1848 assert([&]() {
1849 assert_enabled = true;
1850 return true;
1851 }());
1852 if (!assert_enabled) return;
1853
1854 IntTable t;
1855 // Extra simple "regexp" as regexp support is highly varied across platforms.
1856 constexpr char kDeathMsg[] = "it != end";
1857 EXPECT_DEATH_IF_SUPPORTED(t.erase(t.end()), kDeathMsg);
1858 }
1859
1860 // [greg] did not implement HashtablezSampler in header only phmap.h
1861 TEST(RawHashSamplerTest, DISABLED_Sample) {
1862 // Enable the feature even if the prod default is off.
1863 SetHashtablezEnabled(true);
1864 SetHashtablezSampleParameter(100);
1865
1866 auto& sampler = HashtablezSampler::Global();
1867 size_t start_size = 0;
1868 start_size += sampler.Iterate([&](const HashtablezInfo&) { ++start_size; });
1869
1870 std::vector<IntTable> tables;
1871 for (int i = 0; i < 1000000; ++i) {
1872 tables.emplace_back();
1873 tables.back().insert(1);
1874 }
1875 size_t end_size = 0;
1876 end_size += sampler.Iterate([&](const HashtablezInfo&) { ++end_size; });
1877
1878 EXPECT_NEAR((end_size - start_size) / static_cast<double>(tables.size()),
1879 0.01, 0.005);
1880 }
1881
1882 TEST(RawHashSamplerTest, DoNotSampleCustomAllocators) {
1883 // Enable the feature even if the prod default is off.
1884 SetHashtablezEnabled(true);
1885 SetHashtablezSampleParameter(100);
1886
1887 auto& sampler = HashtablezSampler::Global();
1888 size_t start_size = 0;
1889 start_size += sampler.Iterate([&](const HashtablezInfo&) { ++start_size; });
1890
1891 std::vector<CustomAllocIntTable> tables;
1892 for (int i = 0; i < 1000000; ++i) {
1893 tables.emplace_back();
1894 tables.back().insert(1);
1895 }
1896 size_t end_size = 0;
1897 end_size += sampler.Iterate([&](const HashtablezInfo&) { ++end_size; });
1898
1899 EXPECT_NEAR((end_size - start_size) / static_cast<double>(tables.size()),
1900 0.00, 0.001);
1901 }
1902
1903 #ifdef ADDRESS_SANITIZER
1904 TEST(Sanitizer, PoisoningUnused) {
1905 IntTable t;
1906 t.reserve(5);
1907 // Insert something to force an allocation.
1908 int64_t& v1 = *t.insert(0).first;
1909
1910 // Make sure there is something to test.
1911 ASSERT_GT(t.capacity(), 1);
1912
1913 int64_t* slots = RawHashSetTestOnlyAccess::GetSlots(t);
1914 for (size_t i = 0; i < t.capacity(); ++i) {
1915 EXPECT_EQ(slots + i != &v1, __asan_address_is_poisoned(slots + i));
1916 }
1917 }
1918
1919 TEST(Sanitizer, PoisoningOnErase) {
1920 IntTable t;
1921 int64_t& v = *t.insert(0).first;
1922
1923 EXPECT_FALSE(__asan_address_is_poisoned(&v));
1924 t.erase(0);
1925 EXPECT_TRUE(__asan_address_is_poisoned(&v));
1926 }
1927 #endif // ADDRESS_SANITIZER
1928
1929 } // namespace
1930 } // namespace priv
1931 } // namespace phmap