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