From 5aa5d282eac56a21e74611c1cdbaa97bb5db2dca Mon Sep 17 00:00:00 2001 From: Vincent Ambo Date: Tue, 8 Feb 2022 02:05:36 +0300 Subject: chore(3p/abseil_cpp): unvendor abseil_cpp we weren't actually using these sources anymore, okay? Change-Id: If701571d9716de308d3512e1eb22c35db0877a66 Reviewed-on: https://cl.tvl.fyi/c/depot/+/5248 Tested-by: BuildkiteCI Reviewed-by: grfn Autosubmit: tazjin --- .../absl/container/internal/raw_hash_set_test.cc | 1893 -------------------- 1 file changed, 1893 deletions(-) delete mode 100644 third_party/abseil_cpp/absl/container/internal/raw_hash_set_test.cc (limited to 'third_party/abseil_cpp/absl/container/internal/raw_hash_set_test.cc') diff --git a/third_party/abseil_cpp/absl/container/internal/raw_hash_set_test.cc b/third_party/abseil_cpp/absl/container/internal/raw_hash_set_test.cc deleted file mode 100644 index 33d2773de302..000000000000 --- a/third_party/abseil_cpp/absl/container/internal/raw_hash_set_test.cc +++ /dev/null @@ -1,1893 +0,0 @@ -// Copyright 2018 The Abseil Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// https://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -#include "absl/container/internal/raw_hash_set.h" - -#include -#include -#include -#include -#include -#include -#include -#include - -#include "gmock/gmock.h" -#include "gtest/gtest.h" -#include "absl/base/attributes.h" -#include "absl/base/config.h" -#include "absl/base/internal/cycleclock.h" -#include "absl/base/internal/raw_logging.h" -#include "absl/container/internal/container_memory.h" -#include "absl/container/internal/hash_function_defaults.h" -#include "absl/container/internal/hash_policy_testing.h" -#include "absl/container/internal/hashtable_debug.h" -#include "absl/strings/string_view.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace container_internal { - -struct RawHashSetTestOnlyAccess { - template - static auto GetSlots(const C& c) -> decltype(c.slots_) { - return c.slots_; - } -}; - -namespace { - -using ::testing::DoubleNear; -using ::testing::ElementsAre; -using ::testing::Ge; -using ::testing::Lt; -using ::testing::Optional; -using ::testing::Pair; -using ::testing::UnorderedElementsAre; - -TEST(Util, NormalizeCapacity) { - EXPECT_EQ(1, NormalizeCapacity(0)); - EXPECT_EQ(1, NormalizeCapacity(1)); - EXPECT_EQ(3, NormalizeCapacity(2)); - EXPECT_EQ(3, NormalizeCapacity(3)); - EXPECT_EQ(7, NormalizeCapacity(4)); - EXPECT_EQ(7, NormalizeCapacity(7)); - EXPECT_EQ(15, NormalizeCapacity(8)); - EXPECT_EQ(15, NormalizeCapacity(15)); - EXPECT_EQ(15 * 2 + 1, NormalizeCapacity(15 + 1)); - EXPECT_EQ(15 * 2 + 1, NormalizeCapacity(15 + 2)); -} - -TEST(Util, GrowthAndCapacity) { - // Verify that GrowthToCapacity gives the minimum capacity that has enough - // growth. - for (size_t growth = 0; growth < 10000; ++growth) { - SCOPED_TRACE(growth); - size_t capacity = NormalizeCapacity(GrowthToLowerboundCapacity(growth)); - // The capacity is large enough for `growth` - EXPECT_THAT(CapacityToGrowth(capacity), Ge(growth)); - if (growth != 0 && capacity > 1) { - // There is no smaller capacity that works. - EXPECT_THAT(CapacityToGrowth(capacity / 2), Lt(growth)); - } - } - - for (size_t capacity = Group::kWidth - 1; capacity < 10000; - capacity = 2 * capacity + 1) { - SCOPED_TRACE(capacity); - size_t growth = CapacityToGrowth(capacity); - EXPECT_THAT(growth, Lt(capacity)); - EXPECT_LE(GrowthToLowerboundCapacity(growth), capacity); - EXPECT_EQ(NormalizeCapacity(GrowthToLowerboundCapacity(growth)), capacity); - } -} - -TEST(Util, probe_seq) { - probe_seq<16> seq(0, 127); - auto gen = [&]() { - size_t res = seq.offset(); - seq.next(); - return res; - }; - std::vector offsets(8); - std::generate_n(offsets.begin(), 8, gen); - EXPECT_THAT(offsets, ElementsAre(0, 16, 48, 96, 32, 112, 80, 64)); - seq = probe_seq<16>(128, 127); - std::generate_n(offsets.begin(), 8, gen); - EXPECT_THAT(offsets, ElementsAre(0, 16, 48, 96, 32, 112, 80, 64)); -} - -TEST(BitMask, Smoke) { - EXPECT_FALSE((BitMask(0))); - EXPECT_TRUE((BitMask(5))); - - EXPECT_THAT((BitMask(0)), ElementsAre()); - EXPECT_THAT((BitMask(0x1)), ElementsAre(0)); - EXPECT_THAT((BitMask(0x2)), ElementsAre(1)); - EXPECT_THAT((BitMask(0x3)), ElementsAre(0, 1)); - EXPECT_THAT((BitMask(0x4)), ElementsAre(2)); - EXPECT_THAT((BitMask(0x5)), ElementsAre(0, 2)); - EXPECT_THAT((BitMask(0x55)), ElementsAre(0, 2, 4, 6)); - EXPECT_THAT((BitMask(0xAA)), ElementsAre(1, 3, 5, 7)); -} - -TEST(BitMask, WithShift) { - // See the non-SSE version of Group for details on what this math is for. - uint64_t ctrl = 0x1716151413121110; - uint64_t hash = 0x12; - constexpr uint64_t msbs = 0x8080808080808080ULL; - constexpr uint64_t lsbs = 0x0101010101010101ULL; - auto x = ctrl ^ (lsbs * hash); - uint64_t mask = (x - lsbs) & ~x & msbs; - EXPECT_EQ(0x0000000080800000, mask); - - BitMask b(mask); - EXPECT_EQ(*b, 2); -} - -TEST(BitMask, LeadingTrailing) { - EXPECT_EQ((BitMask(0x00001a40).LeadingZeros()), 3); - EXPECT_EQ((BitMask(0x00001a40).TrailingZeros()), 6); - - EXPECT_EQ((BitMask(0x00000001).LeadingZeros()), 15); - EXPECT_EQ((BitMask(0x00000001).TrailingZeros()), 0); - - EXPECT_EQ((BitMask(0x00008000).LeadingZeros()), 0); - EXPECT_EQ((BitMask(0x00008000).TrailingZeros()), 15); - - EXPECT_EQ((BitMask(0x0000008080808000).LeadingZeros()), 3); - EXPECT_EQ((BitMask(0x0000008080808000).TrailingZeros()), 1); - - EXPECT_EQ((BitMask(0x0000000000000080).LeadingZeros()), 7); - EXPECT_EQ((BitMask(0x0000000000000080).TrailingZeros()), 0); - - EXPECT_EQ((BitMask(0x8000000000000000).LeadingZeros()), 0); - EXPECT_EQ((BitMask(0x8000000000000000).TrailingZeros()), 7); -} - -TEST(Group, EmptyGroup) { - for (h2_t h = 0; h != 128; ++h) EXPECT_FALSE(Group{EmptyGroup()}.Match(h)); -} - -TEST(Group, Match) { - if (Group::kWidth == 16) { - ctrl_t group[] = {kEmpty, 1, kDeleted, 3, kEmpty, 5, kSentinel, 7, - 7, 5, 3, 1, 1, 1, 1, 1}; - EXPECT_THAT(Group{group}.Match(0), ElementsAre()); - EXPECT_THAT(Group{group}.Match(1), ElementsAre(1, 11, 12, 13, 14, 15)); - EXPECT_THAT(Group{group}.Match(3), ElementsAre(3, 10)); - EXPECT_THAT(Group{group}.Match(5), ElementsAre(5, 9)); - EXPECT_THAT(Group{group}.Match(7), ElementsAre(7, 8)); - } else if (Group::kWidth == 8) { - ctrl_t group[] = {kEmpty, 1, 2, kDeleted, 2, 1, kSentinel, 1}; - EXPECT_THAT(Group{group}.Match(0), ElementsAre()); - EXPECT_THAT(Group{group}.Match(1), ElementsAre(1, 5, 7)); - EXPECT_THAT(Group{group}.Match(2), ElementsAre(2, 4)); - } else { - FAIL() << "No test coverage for Group::kWidth==" << Group::kWidth; - } -} - -TEST(Group, MatchEmpty) { - if (Group::kWidth == 16) { - ctrl_t group[] = {kEmpty, 1, kDeleted, 3, kEmpty, 5, kSentinel, 7, - 7, 5, 3, 1, 1, 1, 1, 1}; - EXPECT_THAT(Group{group}.MatchEmpty(), ElementsAre(0, 4)); - } else if (Group::kWidth == 8) { - ctrl_t group[] = {kEmpty, 1, 2, kDeleted, 2, 1, kSentinel, 1}; - EXPECT_THAT(Group{group}.MatchEmpty(), ElementsAre(0)); - } else { - FAIL() << "No test coverage for Group::kWidth==" << Group::kWidth; - } -} - -TEST(Group, MatchEmptyOrDeleted) { - if (Group::kWidth == 16) { - ctrl_t group[] = {kEmpty, 1, kDeleted, 3, kEmpty, 5, kSentinel, 7, - 7, 5, 3, 1, 1, 1, 1, 1}; - EXPECT_THAT(Group{group}.MatchEmptyOrDeleted(), ElementsAre(0, 2, 4)); - } else if (Group::kWidth == 8) { - ctrl_t group[] = {kEmpty, 1, 2, kDeleted, 2, 1, kSentinel, 1}; - EXPECT_THAT(Group{group}.MatchEmptyOrDeleted(), ElementsAre(0, 3)); - } else { - FAIL() << "No test coverage for Group::kWidth==" << Group::kWidth; - } -} - -TEST(Batch, DropDeletes) { - constexpr size_t kCapacity = 63; - constexpr size_t kGroupWidth = container_internal::Group::kWidth; - std::vector ctrl(kCapacity + 1 + kGroupWidth); - ctrl[kCapacity] = kSentinel; - std::vector pattern = {kEmpty, 2, kDeleted, 2, kEmpty, 1, kDeleted}; - for (size_t i = 0; i != kCapacity; ++i) { - ctrl[i] = pattern[i % pattern.size()]; - if (i < kGroupWidth - 1) - ctrl[i + kCapacity + 1] = pattern[i % pattern.size()]; - } - ConvertDeletedToEmptyAndFullToDeleted(ctrl.data(), kCapacity); - ASSERT_EQ(ctrl[kCapacity], kSentinel); - for (size_t i = 0; i < kCapacity + 1 + kGroupWidth; ++i) { - ctrl_t expected = pattern[i % (kCapacity + 1) % pattern.size()]; - if (i == kCapacity) expected = kSentinel; - if (expected == kDeleted) expected = kEmpty; - if (IsFull(expected)) expected = kDeleted; - EXPECT_EQ(ctrl[i], expected) - << i << " " << int{pattern[i % pattern.size()]}; - } -} - -TEST(Group, CountLeadingEmptyOrDeleted) { - const std::vector empty_examples = {kEmpty, kDeleted}; - const std::vector full_examples = {0, 1, 2, 3, 5, 9, 127, kSentinel}; - - for (ctrl_t empty : empty_examples) { - std::vector e(Group::kWidth, empty); - EXPECT_EQ(Group::kWidth, Group{e.data()}.CountLeadingEmptyOrDeleted()); - for (ctrl_t full : full_examples) { - for (size_t i = 0; i != Group::kWidth; ++i) { - std::vector f(Group::kWidth, empty); - f[i] = full; - EXPECT_EQ(i, Group{f.data()}.CountLeadingEmptyOrDeleted()); - } - std::vector f(Group::kWidth, empty); - f[Group::kWidth * 2 / 3] = full; - f[Group::kWidth / 2] = full; - EXPECT_EQ( - Group::kWidth / 2, Group{f.data()}.CountLeadingEmptyOrDeleted()); - } - } -} - -struct IntPolicy { - using slot_type = int64_t; - using key_type = int64_t; - using init_type = int64_t; - - static void construct(void*, int64_t* slot, int64_t v) { *slot = v; } - static void destroy(void*, int64_t*) {} - static void transfer(void*, int64_t* new_slot, int64_t* old_slot) { - *new_slot = *old_slot; - } - - static int64_t& element(slot_type* slot) { return *slot; } - - template - static auto apply(F&& f, int64_t x) -> decltype(std::forward(f)(x, x)) { - return std::forward(f)(x, x); - } -}; - -class StringPolicy { - template ::value>::type> - decltype(std::declval()( - std::declval(), std::piecewise_construct, - std::declval>(), - std::declval())) static apply_impl(F&& f, - std::pair, V> p) { - const absl::string_view& key = std::get<0>(p.first); - return std::forward(f)(key, std::piecewise_construct, std::move(p.first), - std::move(p.second)); - } - - public: - struct slot_type { - struct ctor {}; - - template - slot_type(ctor, Ts&&... ts) : pair(std::forward(ts)...) {} - - std::pair pair; - }; - - using key_type = std::string; - using init_type = std::pair; - - template - static void construct(allocator_type* alloc, slot_type* slot, Args... args) { - std::allocator_traits::construct( - *alloc, slot, typename slot_type::ctor(), std::forward(args)...); - } - - template - static void destroy(allocator_type* alloc, slot_type* slot) { - std::allocator_traits::destroy(*alloc, slot); - } - - template - static void transfer(allocator_type* alloc, slot_type* new_slot, - slot_type* old_slot) { - construct(alloc, new_slot, std::move(old_slot->pair)); - destroy(alloc, old_slot); - } - - static std::pair& element(slot_type* slot) { - return slot->pair; - } - - template - static auto apply(F&& f, Args&&... args) - -> decltype(apply_impl(std::forward(f), - PairArgs(std::forward(args)...))) { - return apply_impl(std::forward(f), - PairArgs(std::forward(args)...)); - } -}; - -struct StringHash : absl::Hash { - using is_transparent = void; -}; -struct StringEq : std::equal_to { - using is_transparent = void; -}; - -struct StringTable - : raw_hash_set> { - using Base = typename StringTable::raw_hash_set; - StringTable() {} - using Base::Base; -}; - -struct IntTable - : raw_hash_set, - std::equal_to, std::allocator> { - using Base = typename IntTable::raw_hash_set; - using Base::Base; -}; - -template -struct CustomAlloc : std::allocator { - CustomAlloc() {} - - template - CustomAlloc(const CustomAlloc& other) {} - - template struct rebind { - using other = CustomAlloc; - }; -}; - -struct CustomAllocIntTable - : raw_hash_set, - std::equal_to, CustomAlloc> { - using Base = typename CustomAllocIntTable::raw_hash_set; - using Base::Base; -}; - -struct BadFastHash { - template - size_t operator()(const T&) const { - return 0; - } -}; - -struct BadTable : raw_hash_set, - std::allocator> { - using Base = typename BadTable::raw_hash_set; - BadTable() {} - using Base::Base; -}; - -TEST(Table, EmptyFunctorOptimization) { - static_assert(std::is_empty>::value, ""); - static_assert(std::is_empty>::value, ""); - - struct MockTable { - void* ctrl; - void* slots; - size_t size; - size_t capacity; - size_t growth_left; - void* infoz; - }; - struct StatelessHash { - size_t operator()(absl::string_view) const { return 0; } - }; - struct StatefulHash : StatelessHash { - size_t dummy; - }; - - EXPECT_EQ( - sizeof(MockTable), - sizeof( - raw_hash_set, std::allocator>)); - - EXPECT_EQ( - sizeof(MockTable) + sizeof(StatefulHash), - sizeof( - raw_hash_set, std::allocator>)); -} - -TEST(Table, Empty) { - IntTable t; - EXPECT_EQ(0, t.size()); - EXPECT_TRUE(t.empty()); -} - -TEST(Table, LookupEmpty) { - IntTable t; - auto it = t.find(0); - EXPECT_TRUE(it == t.end()); -} - -TEST(Table, Insert1) { - IntTable t; - EXPECT_TRUE(t.find(0) == t.end()); - auto res = t.emplace(0); - EXPECT_TRUE(res.second); - EXPECT_THAT(*res.first, 0); - EXPECT_EQ(1, t.size()); - EXPECT_THAT(*t.find(0), 0); -} - -TEST(Table, Insert2) { - IntTable t; - EXPECT_TRUE(t.find(0) == t.end()); - auto res = t.emplace(0); - EXPECT_TRUE(res.second); - EXPECT_THAT(*res.first, 0); - EXPECT_EQ(1, t.size()); - EXPECT_TRUE(t.find(1) == t.end()); - res = t.emplace(1); - EXPECT_TRUE(res.second); - EXPECT_THAT(*res.first, 1); - EXPECT_EQ(2, t.size()); - EXPECT_THAT(*t.find(0), 0); - EXPECT_THAT(*t.find(1), 1); -} - -TEST(Table, InsertCollision) { - BadTable t; - EXPECT_TRUE(t.find(1) == t.end()); - auto res = t.emplace(1); - EXPECT_TRUE(res.second); - EXPECT_THAT(*res.first, 1); - EXPECT_EQ(1, t.size()); - - EXPECT_TRUE(t.find(2) == t.end()); - res = t.emplace(2); - EXPECT_THAT(*res.first, 2); - EXPECT_TRUE(res.second); - EXPECT_EQ(2, t.size()); - - EXPECT_THAT(*t.find(1), 1); - EXPECT_THAT(*t.find(2), 2); -} - -// Test that we do not add existent element in case we need to search through -// many groups with deleted elements -TEST(Table, InsertCollisionAndFindAfterDelete) { - BadTable t; // all elements go to the same group. - // Have at least 2 groups with Group::kWidth collisions - // plus some extra collisions in the last group. - constexpr size_t kNumInserts = Group::kWidth * 2 + 5; - for (size_t i = 0; i < kNumInserts; ++i) { - auto res = t.emplace(i); - EXPECT_TRUE(res.second); - EXPECT_THAT(*res.first, i); - EXPECT_EQ(i + 1, t.size()); - } - - // Remove elements one by one and check - // that we still can find all other elements. - for (size_t i = 0; i < kNumInserts; ++i) { - EXPECT_EQ(1, t.erase(i)) << i; - for (size_t j = i + 1; j < kNumInserts; ++j) { - EXPECT_THAT(*t.find(j), j); - auto res = t.emplace(j); - EXPECT_FALSE(res.second) << i << " " << j; - EXPECT_THAT(*res.first, j); - EXPECT_EQ(kNumInserts - i - 1, t.size()); - } - } - EXPECT_TRUE(t.empty()); -} - -TEST(Table, LazyEmplace) { - StringTable t; - bool called = false; - auto it = t.lazy_emplace("abc", [&](const StringTable::constructor& f) { - called = true; - f("abc", "ABC"); - }); - EXPECT_TRUE(called); - EXPECT_THAT(*it, Pair("abc", "ABC")); - called = false; - it = t.lazy_emplace("abc", [&](const StringTable::constructor& f) { - called = true; - f("abc", "DEF"); - }); - EXPECT_FALSE(called); - EXPECT_THAT(*it, Pair("abc", "ABC")); -} - -TEST(Table, ContainsEmpty) { - IntTable t; - - EXPECT_FALSE(t.contains(0)); -} - -TEST(Table, Contains1) { - IntTable t; - - EXPECT_TRUE(t.insert(0).second); - EXPECT_TRUE(t.contains(0)); - EXPECT_FALSE(t.contains(1)); - - EXPECT_EQ(1, t.erase(0)); - EXPECT_FALSE(t.contains(0)); -} - -TEST(Table, Contains2) { - IntTable t; - - EXPECT_TRUE(t.insert(0).second); - EXPECT_TRUE(t.contains(0)); - EXPECT_FALSE(t.contains(1)); - - t.clear(); - EXPECT_FALSE(t.contains(0)); -} - -int decompose_constructed; -struct DecomposeType { - DecomposeType(int i) : i(i) { // NOLINT - ++decompose_constructed; - } - - explicit DecomposeType(const char* d) : DecomposeType(*d) {} - - int i; -}; - -struct DecomposeHash { - using is_transparent = void; - size_t operator()(DecomposeType a) const { return a.i; } - size_t operator()(int a) const { return a; } - size_t operator()(const char* a) const { return *a; } -}; - -struct DecomposeEq { - using is_transparent = void; - bool operator()(DecomposeType a, DecomposeType b) const { return a.i == b.i; } - bool operator()(DecomposeType a, int b) const { return a.i == b; } - bool operator()(DecomposeType a, const char* b) const { return a.i == *b; } -}; - -struct DecomposePolicy { - using slot_type = DecomposeType; - using key_type = DecomposeType; - using init_type = DecomposeType; - - template - static void construct(void*, DecomposeType* slot, T&& v) { - *slot = DecomposeType(std::forward(v)); - } - static void destroy(void*, DecomposeType*) {} - static DecomposeType& element(slot_type* slot) { return *slot; } - - template - static auto apply(F&& f, const T& x) -> decltype(std::forward(f)(x, x)) { - return std::forward(f)(x, x); - } -}; - -template -void TestDecompose(bool construct_three) { - DecomposeType elem{0}; - const int one = 1; - const char* three_p = "3"; - const auto& three = three_p; - - raw_hash_set> set1; - - decompose_constructed = 0; - int expected_constructed = 0; - EXPECT_EQ(expected_constructed, decompose_constructed); - set1.insert(elem); - EXPECT_EQ(expected_constructed, decompose_constructed); - set1.insert(1); - EXPECT_EQ(++expected_constructed, decompose_constructed); - set1.emplace("3"); - EXPECT_EQ(++expected_constructed, decompose_constructed); - EXPECT_EQ(expected_constructed, decompose_constructed); - - { // insert(T&&) - set1.insert(1); - EXPECT_EQ(expected_constructed, decompose_constructed); - } - - { // insert(const T&) - set1.insert(one); - EXPECT_EQ(expected_constructed, decompose_constructed); - } - - { // insert(hint, T&&) - set1.insert(set1.begin(), 1); - EXPECT_EQ(expected_constructed, decompose_constructed); - } - - { // insert(hint, const T&) - set1.insert(set1.begin(), one); - EXPECT_EQ(expected_constructed, decompose_constructed); - } - - { // emplace(...) - set1.emplace(1); - EXPECT_EQ(expected_constructed, decompose_constructed); - set1.emplace("3"); - expected_constructed += construct_three; - EXPECT_EQ(expected_constructed, decompose_constructed); - set1.emplace(one); - EXPECT_EQ(expected_constructed, decompose_constructed); - set1.emplace(three); - expected_constructed += construct_three; - EXPECT_EQ(expected_constructed, decompose_constructed); - } - - { // emplace_hint(...) - set1.emplace_hint(set1.begin(), 1); - EXPECT_EQ(expected_constructed, decompose_constructed); - set1.emplace_hint(set1.begin(), "3"); - expected_constructed += construct_three; - EXPECT_EQ(expected_constructed, decompose_constructed); - set1.emplace_hint(set1.begin(), one); - EXPECT_EQ(expected_constructed, decompose_constructed); - set1.emplace_hint(set1.begin(), three); - expected_constructed += construct_three; - EXPECT_EQ(expected_constructed, decompose_constructed); - } -} - -TEST(Table, Decompose) { - TestDecompose(false); - - struct TransparentHashIntOverload { - size_t operator()(DecomposeType a) const { return a.i; } - size_t operator()(int a) const { return a; } - }; - struct TransparentEqIntOverload { - bool operator()(DecomposeType a, DecomposeType b) const { - return a.i == b.i; - } - bool operator()(DecomposeType a, int b) const { return a.i == b; } - }; - TestDecompose(true); - TestDecompose(true); - TestDecompose(true); -} - -// Returns the largest m such that a table with m elements has the same number -// of buckets as a table with n elements. -size_t MaxDensitySize(size_t n) { - IntTable t; - t.reserve(n); - for (size_t i = 0; i != n; ++i) t.emplace(i); - const size_t c = t.bucket_count(); - while (c == t.bucket_count()) t.emplace(n++); - return t.size() - 1; -} - -struct Modulo1000Hash { - size_t operator()(int x) const { return x % 1000; } -}; - -struct Modulo1000HashTable - : public raw_hash_set, - std::allocator> {}; - -// Test that rehash with no resize happen in case of many deleted slots. -TEST(Table, RehashWithNoResize) { - Modulo1000HashTable t; - // Adding the same length (and the same hash) strings - // to have at least kMinFullGroups groups - // with Group::kWidth collisions. Then fill up to MaxDensitySize; - const size_t kMinFullGroups = 7; - std::vector keys; - for (size_t i = 0; i < MaxDensitySize(Group::kWidth * kMinFullGroups); ++i) { - int k = i * 1000; - t.emplace(k); - keys.push_back(k); - } - const size_t capacity = t.capacity(); - - // Remove elements from all groups except the first and the last one. - // All elements removed from full groups will be marked as kDeleted. - const size_t erase_begin = Group::kWidth / 2; - const size_t erase_end = (t.size() / Group::kWidth - 1) * Group::kWidth; - for (size_t i = erase_begin; i < erase_end; ++i) { - EXPECT_EQ(1, t.erase(keys[i])) << i; - } - keys.erase(keys.begin() + erase_begin, keys.begin() + erase_end); - - auto last_key = keys.back(); - size_t last_key_num_probes = GetHashtableDebugNumProbes(t, last_key); - - // Make sure that we have to make a lot of probes for last key. - ASSERT_GT(last_key_num_probes, kMinFullGroups); - - int x = 1; - // Insert and erase one element, before inplace rehash happen. - while (last_key_num_probes == GetHashtableDebugNumProbes(t, last_key)) { - t.emplace(x); - ASSERT_EQ(capacity, t.capacity()); - // All elements should be there. - ASSERT_TRUE(t.find(x) != t.end()) << x; - for (const auto& k : keys) { - ASSERT_TRUE(t.find(k) != t.end()) << k; - } - t.erase(x); - ++x; - } -} - -TEST(Table, InsertEraseStressTest) { - IntTable t; - const size_t kMinElementCount = 250; - std::deque keys; - size_t i = 0; - for (; i < MaxDensitySize(kMinElementCount); ++i) { - t.emplace(i); - keys.push_back(i); - } - const size_t kNumIterations = 1000000; - for (; i < kNumIterations; ++i) { - ASSERT_EQ(1, t.erase(keys.front())); - keys.pop_front(); - t.emplace(i); - keys.push_back(i); - } -} - -TEST(Table, InsertOverloads) { - StringTable t; - // These should all trigger the insert(init_type) overload. - t.insert({{}, {}}); - t.insert({"ABC", {}}); - t.insert({"DEF", "!!!"}); - - EXPECT_THAT(t, UnorderedElementsAre(Pair("", ""), Pair("ABC", ""), - Pair("DEF", "!!!"))); -} - -TEST(Table, LargeTable) { - IntTable t; - for (int64_t i = 0; i != 100000; ++i) t.emplace(i << 40); - for (int64_t i = 0; i != 100000; ++i) ASSERT_EQ(i << 40, *t.find(i << 40)); -} - -// Timeout if copy is quadratic as it was in Rust. -TEST(Table, EnsureNonQuadraticAsInRust) { - static const size_t kLargeSize = 1 << 15; - - IntTable t; - for (size_t i = 0; i != kLargeSize; ++i) { - t.insert(i); - } - - // If this is quadratic, the test will timeout. - IntTable t2; - for (const auto& entry : t) t2.insert(entry); -} - -TEST(Table, ClearBug) { - IntTable t; - constexpr size_t capacity = container_internal::Group::kWidth - 1; - constexpr size_t max_size = capacity / 2 + 1; - for (size_t i = 0; i < max_size; ++i) { - t.insert(i); - } - ASSERT_EQ(capacity, t.capacity()); - intptr_t original = reinterpret_cast(&*t.find(2)); - t.clear(); - ASSERT_EQ(capacity, t.capacity()); - for (size_t i = 0; i < max_size; ++i) { - t.insert(i); - } - ASSERT_EQ(capacity, t.capacity()); - intptr_t second = reinterpret_cast(&*t.find(2)); - // We are checking that original and second are close enough to each other - // that they are probably still in the same group. This is not strictly - // guaranteed. - EXPECT_LT(std::abs(original - second), - capacity * sizeof(IntTable::value_type)); -} - -TEST(Table, Erase) { - IntTable t; - EXPECT_TRUE(t.find(0) == t.end()); - auto res = t.emplace(0); - EXPECT_TRUE(res.second); - EXPECT_EQ(1, t.size()); - t.erase(res.first); - EXPECT_EQ(0, t.size()); - EXPECT_TRUE(t.find(0) == t.end()); -} - -TEST(Table, EraseMaintainsValidIterator) { - IntTable t; - const int kNumElements = 100; - for (int i = 0; i < kNumElements; i ++) { - EXPECT_TRUE(t.emplace(i).second); - } - EXPECT_EQ(t.size(), kNumElements); - - int num_erase_calls = 0; - auto it = t.begin(); - while (it != t.end()) { - t.erase(it++); - num_erase_calls++; - } - - EXPECT_TRUE(t.empty()); - EXPECT_EQ(num_erase_calls, kNumElements); -} - -// Collect N bad keys by following algorithm: -// 1. Create an empty table and reserve it to 2 * N. -// 2. Insert N random elements. -// 3. Take first Group::kWidth - 1 to bad_keys array. -// 4. Clear the table without resize. -// 5. Go to point 2 while N keys not collected -std::vector CollectBadMergeKeys(size_t N) { - static constexpr int kGroupSize = Group::kWidth - 1; - - auto topk_range = [](size_t b, size_t e, - IntTable* t) -> std::vector { - for (size_t i = b; i != e; ++i) { - t->emplace(i); - } - std::vector res; - res.reserve(kGroupSize); - auto it = t->begin(); - for (size_t i = b; i != e && i != b + kGroupSize; ++i, ++it) { - res.push_back(*it); - } - return res; - }; - - std::vector bad_keys; - bad_keys.reserve(N); - IntTable t; - t.reserve(N * 2); - - for (size_t b = 0; bad_keys.size() < N; b += N) { - auto keys = topk_range(b, b + N, &t); - bad_keys.insert(bad_keys.end(), keys.begin(), keys.end()); - t.erase(t.begin(), t.end()); - EXPECT_TRUE(t.empty()); - } - return bad_keys; -} - -struct ProbeStats { - // Number of elements with specific probe length over all tested tables. - std::vector all_probes_histogram; - // Ratios total_probe_length/size for every tested table. - std::vector single_table_ratios; - - friend ProbeStats operator+(const ProbeStats& a, const ProbeStats& b) { - ProbeStats res = a; - res.all_probes_histogram.resize(std::max(res.all_probes_histogram.size(), - b.all_probes_histogram.size())); - std::transform(b.all_probes_histogram.begin(), b.all_probes_histogram.end(), - res.all_probes_histogram.begin(), - res.all_probes_histogram.begin(), std::plus()); - res.single_table_ratios.insert(res.single_table_ratios.end(), - b.single_table_ratios.begin(), - b.single_table_ratios.end()); - return res; - } - - // Average ratio total_probe_length/size over tables. - double AvgRatio() const { - return std::accumulate(single_table_ratios.begin(), - single_table_ratios.end(), 0.0) / - single_table_ratios.size(); - } - - // Maximum ratio total_probe_length/size over tables. - double MaxRatio() const { - return *std::max_element(single_table_ratios.begin(), - single_table_ratios.end()); - } - - // Percentile ratio total_probe_length/size over tables. - double PercentileRatio(double Percentile = 0.95) const { - auto r = single_table_ratios; - auto mid = r.begin() + static_cast(r.size() * Percentile); - if (mid != r.end()) { - std::nth_element(r.begin(), mid, r.end()); - return *mid; - } else { - return MaxRatio(); - } - } - - // Maximum probe length over all elements and all tables. - size_t MaxProbe() const { return all_probes_histogram.size(); } - - // Fraction of elements with specified probe length. - std::vector ProbeNormalizedHistogram() const { - double total_elements = std::accumulate(all_probes_histogram.begin(), - all_probes_histogram.end(), 0ull); - std::vector res; - for (size_t p : all_probes_histogram) { - res.push_back(p / total_elements); - } - return res; - } - - size_t PercentileProbe(double Percentile = 0.99) const { - size_t idx = 0; - for (double p : ProbeNormalizedHistogram()) { - if (Percentile > p) { - Percentile -= p; - ++idx; - } else { - return idx; - } - } - return idx; - } - - friend std::ostream& operator<<(std::ostream& out, const ProbeStats& s) { - out << "{AvgRatio:" << s.AvgRatio() << ", MaxRatio:" << s.MaxRatio() - << ", PercentileRatio:" << s.PercentileRatio() - << ", MaxProbe:" << s.MaxProbe() << ", Probes=["; - for (double p : s.ProbeNormalizedHistogram()) { - out << p << ","; - } - out << "]}"; - - return out; - } -}; - -struct ExpectedStats { - double avg_ratio; - double max_ratio; - std::vector> pecentile_ratios; - std::vector> pecentile_probes; - - friend std::ostream& operator<<(std::ostream& out, const ExpectedStats& s) { - out << "{AvgRatio:" << s.avg_ratio << ", MaxRatio:" << s.max_ratio - << ", PercentileRatios: ["; - for (auto el : s.pecentile_ratios) { - out << el.first << ":" << el.second << ", "; - } - out << "], PercentileProbes: ["; - for (auto el : s.pecentile_probes) { - out << el.first << ":" << el.second << ", "; - } - out << "]}"; - - return out; - } -}; - -void VerifyStats(size_t size, const ExpectedStats& exp, - const ProbeStats& stats) { - EXPECT_LT(stats.AvgRatio(), exp.avg_ratio) << size << " " << stats; - EXPECT_LT(stats.MaxRatio(), exp.max_ratio) << size << " " << stats; - for (auto pr : exp.pecentile_ratios) { - EXPECT_LE(stats.PercentileRatio(pr.first), pr.second) - << size << " " << pr.first << " " << stats; - } - - for (auto pr : exp.pecentile_probes) { - EXPECT_LE(stats.PercentileProbe(pr.first), pr.second) - << size << " " << pr.first << " " << stats; - } -} - -using ProbeStatsPerSize = std::map; - -// Collect total ProbeStats on num_iters iterations of the following algorithm: -// 1. Create new table and reserve it to keys.size() * 2 -// 2. Insert all keys xored with seed -// 3. Collect ProbeStats from final table. -ProbeStats CollectProbeStatsOnKeysXoredWithSeed( - const std::vector& keys, size_t num_iters) { - const size_t reserve_size = keys.size() * 2; - - ProbeStats stats; - - int64_t seed = 0x71b1a19b907d6e33; - while (num_iters--) { - seed = static_cast(static_cast(seed) * 17 + 13); - IntTable t1; - t1.reserve(reserve_size); - for (const auto& key : keys) { - t1.emplace(key ^ seed); - } - - auto probe_histogram = GetHashtableDebugNumProbesHistogram(t1); - stats.all_probes_histogram.resize( - std::max(stats.all_probes_histogram.size(), probe_histogram.size())); - std::transform(probe_histogram.begin(), probe_histogram.end(), - stats.all_probes_histogram.begin(), - stats.all_probes_histogram.begin(), std::plus()); - - size_t total_probe_seq_length = 0; - for (size_t i = 0; i < probe_histogram.size(); ++i) { - total_probe_seq_length += i * probe_histogram[i]; - } - stats.single_table_ratios.push_back(total_probe_seq_length * 1.0 / - keys.size()); - t1.erase(t1.begin(), t1.end()); - } - return stats; -} - -ExpectedStats XorSeedExpectedStats() { - constexpr bool kRandomizesInserts = -#ifdef NDEBUG - false; -#else // NDEBUG - true; -#endif // NDEBUG - - // The effective load factor is larger in non-opt mode because we insert - // elements out of order. - switch (container_internal::Group::kWidth) { - case 8: - if (kRandomizesInserts) { - return {0.05, - 1.0, - {{0.95, 0.5}}, - {{0.95, 0}, {0.99, 2}, {0.999, 4}, {0.9999, 10}}}; - } else { - return {0.05, - 2.0, - {{0.95, 0.1}}, - {{0.95, 0}, {0.99, 2}, {0.999, 4}, {0.9999, 10}}}; - } - case 16: - if (kRandomizesInserts) { - return {0.1, - 1.0, - {{0.95, 0.1}}, - {{0.95, 0}, {0.99, 1}, {0.999, 8}, {0.9999, 15}}}; - } else { - return {0.05, - 1.0, - {{0.95, 0.05}}, - {{0.95, 0}, {0.99, 1}, {0.999, 4}, {0.9999, 10}}}; - } - } - ABSL_RAW_LOG(FATAL, "%s", "Unknown Group width"); - return {}; -} - -TEST(Table, DISABLED_EnsureNonQuadraticTopNXorSeedByProbeSeqLength) { - ProbeStatsPerSize stats; - std::vector sizes = {Group::kWidth << 5, Group::kWidth << 10}; - for (size_t size : sizes) { - stats[size] = - CollectProbeStatsOnKeysXoredWithSeed(CollectBadMergeKeys(size), 200); - } - auto expected = XorSeedExpectedStats(); - for (size_t size : sizes) { - auto& stat = stats[size]; - VerifyStats(size, expected, stat); - } -} - -// Collect total ProbeStats on num_iters iterations of the following algorithm: -// 1. Create new table -// 2. Select 10% of keys and insert 10 elements key * 17 + j * 13 -// 3. Collect ProbeStats from final table -ProbeStats CollectProbeStatsOnLinearlyTransformedKeys( - const std::vector& keys, size_t num_iters) { - ProbeStats stats; - - std::random_device rd; - std::mt19937 rng(rd()); - auto linear_transform = [](size_t x, size_t y) { return x * 17 + y * 13; }; - std::uniform_int_distribution dist(0, keys.size()-1); - while (num_iters--) { - IntTable t1; - size_t num_keys = keys.size() / 10; - size_t start = dist(rng); - for (size_t i = 0; i != num_keys; ++i) { - for (size_t j = 0; j != 10; ++j) { - t1.emplace(linear_transform(keys[(i + start) % keys.size()], j)); - } - } - - auto probe_histogram = GetHashtableDebugNumProbesHistogram(t1); - stats.all_probes_histogram.resize( - std::max(stats.all_probes_histogram.size(), probe_histogram.size())); - std::transform(probe_histogram.begin(), probe_histogram.end(), - stats.all_probes_histogram.begin(), - stats.all_probes_histogram.begin(), std::plus()); - - size_t total_probe_seq_length = 0; - for (size_t i = 0; i < probe_histogram.size(); ++i) { - total_probe_seq_length += i * probe_histogram[i]; - } - stats.single_table_ratios.push_back(total_probe_seq_length * 1.0 / - t1.size()); - t1.erase(t1.begin(), t1.end()); - } - return stats; -} - -ExpectedStats LinearTransformExpectedStats() { - constexpr bool kRandomizesInserts = -#ifdef NDEBUG - false; -#else // NDEBUG - true; -#endif // NDEBUG - - // The effective load factor is larger in non-opt mode because we insert - // elements out of order. - switch (container_internal::Group::kWidth) { - case 8: - if (kRandomizesInserts) { - return {0.1, - 0.5, - {{0.95, 0.3}}, - {{0.95, 0}, {0.99, 1}, {0.999, 8}, {0.9999, 15}}}; - } else { - return {0.15, - 0.5, - {{0.95, 0.3}}, - {{0.95, 0}, {0.99, 3}, {0.999, 15}, {0.9999, 25}}}; - } - case 16: - if (kRandomizesInserts) { - return {0.1, - 0.4, - {{0.95, 0.3}}, - {{0.95, 0}, {0.99, 1}, {0.999, 8}, {0.9999, 15}}}; - } else { - return {0.05, - 0.2, - {{0.95, 0.1}}, - {{0.95, 0}, {0.99, 1}, {0.999, 6}, {0.9999, 10}}}; - } - } - ABSL_RAW_LOG(FATAL, "%s", "Unknown Group width"); - return {}; -} - -TEST(Table, DISABLED_EnsureNonQuadraticTopNLinearTransformByProbeSeqLength) { - ProbeStatsPerSize stats; - std::vector sizes = {Group::kWidth << 5, Group::kWidth << 10}; - for (size_t size : sizes) { - stats[size] = CollectProbeStatsOnLinearlyTransformedKeys( - CollectBadMergeKeys(size), 300); - } - auto expected = LinearTransformExpectedStats(); - for (size_t size : sizes) { - auto& stat = stats[size]; - VerifyStats(size, expected, stat); - } -} - -TEST(Table, EraseCollision) { - BadTable t; - - // 1 2 3 - t.emplace(1); - t.emplace(2); - t.emplace(3); - EXPECT_THAT(*t.find(1), 1); - EXPECT_THAT(*t.find(2), 2); - EXPECT_THAT(*t.find(3), 3); - EXPECT_EQ(3, t.size()); - - // 1 DELETED 3 - t.erase(t.find(2)); - EXPECT_THAT(*t.find(1), 1); - EXPECT_TRUE(t.find(2) == t.end()); - EXPECT_THAT(*t.find(3), 3); - EXPECT_EQ(2, t.size()); - - // DELETED DELETED 3 - t.erase(t.find(1)); - EXPECT_TRUE(t.find(1) == t.end()); - EXPECT_TRUE(t.find(2) == t.end()); - EXPECT_THAT(*t.find(3), 3); - EXPECT_EQ(1, t.size()); - - // DELETED DELETED DELETED - t.erase(t.find(3)); - EXPECT_TRUE(t.find(1) == t.end()); - EXPECT_TRUE(t.find(2) == t.end()); - EXPECT_TRUE(t.find(3) == t.end()); - EXPECT_EQ(0, t.size()); -} - -TEST(Table, EraseInsertProbing) { - BadTable t(100); - - // 1 2 3 4 - t.emplace(1); - t.emplace(2); - t.emplace(3); - t.emplace(4); - - // 1 DELETED 3 DELETED - t.erase(t.find(2)); - t.erase(t.find(4)); - - // 1 10 3 11 12 - t.emplace(10); - t.emplace(11); - t.emplace(12); - - EXPECT_EQ(5, t.size()); - EXPECT_THAT(t, UnorderedElementsAre(1, 10, 3, 11, 12)); -} - -TEST(Table, Clear) { - IntTable t; - EXPECT_TRUE(t.find(0) == t.end()); - t.clear(); - EXPECT_TRUE(t.find(0) == t.end()); - auto res = t.emplace(0); - EXPECT_TRUE(res.second); - EXPECT_EQ(1, t.size()); - t.clear(); - EXPECT_EQ(0, t.size()); - EXPECT_TRUE(t.find(0) == t.end()); -} - -TEST(Table, Swap) { - IntTable t; - EXPECT_TRUE(t.find(0) == t.end()); - auto res = t.emplace(0); - EXPECT_TRUE(res.second); - EXPECT_EQ(1, t.size()); - IntTable u; - t.swap(u); - EXPECT_EQ(0, t.size()); - EXPECT_EQ(1, u.size()); - EXPECT_TRUE(t.find(0) == t.end()); - EXPECT_THAT(*u.find(0), 0); -} - -TEST(Table, Rehash) { - IntTable t; - EXPECT_TRUE(t.find(0) == t.end()); - t.emplace(0); - t.emplace(1); - EXPECT_EQ(2, t.size()); - t.rehash(128); - EXPECT_EQ(2, t.size()); - EXPECT_THAT(*t.find(0), 0); - EXPECT_THAT(*t.find(1), 1); -} - -TEST(Table, RehashDoesNotRehashWhenNotNecessary) { - IntTable t; - t.emplace(0); - t.emplace(1); - auto* p = &*t.find(0); - t.rehash(1); - EXPECT_EQ(p, &*t.find(0)); -} - -TEST(Table, RehashZeroDoesNotAllocateOnEmptyTable) { - IntTable t; - t.rehash(0); - EXPECT_EQ(0, t.bucket_count()); -} - -TEST(Table, RehashZeroDeallocatesEmptyTable) { - IntTable t; - t.emplace(0); - t.clear(); - EXPECT_NE(0, t.bucket_count()); - t.rehash(0); - EXPECT_EQ(0, t.bucket_count()); -} - -TEST(Table, RehashZeroForcesRehash) { - IntTable t; - t.emplace(0); - t.emplace(1); - auto* p = &*t.find(0); - t.rehash(0); - EXPECT_NE(p, &*t.find(0)); -} - -TEST(Table, ConstructFromInitList) { - using P = std::pair; - struct Q { - operator P() const { return {}; } - }; - StringTable t = {P(), Q(), {}, {{}, {}}}; -} - -TEST(Table, CopyConstruct) { - IntTable t; - t.emplace(0); - EXPECT_EQ(1, t.size()); - { - IntTable u(t); - EXPECT_EQ(1, u.size()); - EXPECT_THAT(*u.find(0), 0); - } - { - IntTable u{t}; - EXPECT_EQ(1, u.size()); - EXPECT_THAT(*u.find(0), 0); - } - { - IntTable u = t; - EXPECT_EQ(1, u.size()); - EXPECT_THAT(*u.find(0), 0); - } -} - -TEST(Table, CopyConstructWithAlloc) { - StringTable t; - t.emplace("a", "b"); - EXPECT_EQ(1, t.size()); - StringTable u(t, Alloc>()); - EXPECT_EQ(1, u.size()); - EXPECT_THAT(*u.find("a"), Pair("a", "b")); -} - -struct ExplicitAllocIntTable - : raw_hash_set, - std::equal_to, Alloc> { - ExplicitAllocIntTable() {} -}; - -TEST(Table, AllocWithExplicitCtor) { - ExplicitAllocIntTable t; - EXPECT_EQ(0, t.size()); -} - -TEST(Table, MoveConstruct) { - { - StringTable t; - t.emplace("a", "b"); - EXPECT_EQ(1, t.size()); - - StringTable u(std::move(t)); - EXPECT_EQ(1, u.size()); - EXPECT_THAT(*u.find("a"), Pair("a", "b")); - } - { - StringTable t; - t.emplace("a", "b"); - EXPECT_EQ(1, t.size()); - - StringTable u{std::move(t)}; - EXPECT_EQ(1, u.size()); - EXPECT_THAT(*u.find("a"), Pair("a", "b")); - } - { - StringTable t; - t.emplace("a", "b"); - EXPECT_EQ(1, t.size()); - - StringTable u = std::move(t); - EXPECT_EQ(1, u.size()); - EXPECT_THAT(*u.find("a"), Pair("a", "b")); - } -} - -TEST(Table, MoveConstructWithAlloc) { - StringTable t; - t.emplace("a", "b"); - EXPECT_EQ(1, t.size()); - StringTable u(std::move(t), Alloc>()); - EXPECT_EQ(1, u.size()); - EXPECT_THAT(*u.find("a"), Pair("a", "b")); -} - -TEST(Table, CopyAssign) { - StringTable t; - t.emplace("a", "b"); - EXPECT_EQ(1, t.size()); - StringTable u; - u = t; - EXPECT_EQ(1, u.size()); - EXPECT_THAT(*u.find("a"), Pair("a", "b")); -} - -TEST(Table, CopySelfAssign) { - StringTable t; - t.emplace("a", "b"); - EXPECT_EQ(1, t.size()); - t = *&t; - EXPECT_EQ(1, t.size()); - EXPECT_THAT(*t.find("a"), Pair("a", "b")); -} - -TEST(Table, MoveAssign) { - StringTable t; - t.emplace("a", "b"); - EXPECT_EQ(1, t.size()); - StringTable u; - u = std::move(t); - EXPECT_EQ(1, u.size()); - EXPECT_THAT(*u.find("a"), Pair("a", "b")); -} - -TEST(Table, Equality) { - StringTable t; - std::vector> v = {{"a", "b"}, - {"aa", "bb"}}; - t.insert(std::begin(v), std::end(v)); - StringTable u = t; - EXPECT_EQ(u, t); -} - -TEST(Table, Equality2) { - StringTable t; - std::vector> v1 = {{"a", "b"}, - {"aa", "bb"}}; - t.insert(std::begin(v1), std::end(v1)); - StringTable u; - std::vector> v2 = {{"a", "a"}, - {"aa", "aa"}}; - u.insert(std::begin(v2), std::end(v2)); - EXPECT_NE(u, t); -} - -TEST(Table, Equality3) { - StringTable t; - std::vector> v1 = {{"b", "b"}, - {"bb", "bb"}}; - t.insert(std::begin(v1), std::end(v1)); - StringTable u; - std::vector> v2 = {{"a", "a"}, - {"aa", "aa"}}; - u.insert(std::begin(v2), std::end(v2)); - EXPECT_NE(u, t); -} - -TEST(Table, NumDeletedRegression) { - IntTable t; - t.emplace(0); - t.erase(t.find(0)); - // construct over a deleted slot. - t.emplace(0); - t.clear(); -} - -TEST(Table, FindFullDeletedRegression) { - IntTable t; - for (int i = 0; i < 1000; ++i) { - t.emplace(i); - t.erase(t.find(i)); - } - EXPECT_EQ(0, t.size()); -} - -TEST(Table, ReplacingDeletedSlotDoesNotRehash) { - size_t n; - { - // Compute n such that n is the maximum number of elements before rehash. - IntTable t; - t.emplace(0); - size_t c = t.bucket_count(); - for (n = 1; c == t.bucket_count(); ++n) t.emplace(n); - --n; - } - IntTable t; - t.rehash(n); - const size_t c = t.bucket_count(); - for (size_t i = 0; i != n; ++i) t.emplace(i); - EXPECT_EQ(c, t.bucket_count()) << "rehashing threshold = " << n; - t.erase(0); - t.emplace(0); - EXPECT_EQ(c, t.bucket_count()) << "rehashing threshold = " << n; -} - -TEST(Table, NoThrowMoveConstruct) { - ASSERT_TRUE( - std::is_nothrow_copy_constructible>::value); - ASSERT_TRUE(std::is_nothrow_copy_constructible< - std::equal_to>::value); - ASSERT_TRUE(std::is_nothrow_copy_constructible>::value); - EXPECT_TRUE(std::is_nothrow_move_constructible::value); -} - -TEST(Table, NoThrowMoveAssign) { - ASSERT_TRUE( - std::is_nothrow_move_assignable>::value); - ASSERT_TRUE( - std::is_nothrow_move_assignable>::value); - ASSERT_TRUE(std::is_nothrow_move_assignable>::value); - ASSERT_TRUE( - absl::allocator_traits>::is_always_equal::value); - EXPECT_TRUE(std::is_nothrow_move_assignable::value); -} - -TEST(Table, NoThrowSwappable) { - ASSERT_TRUE( - container_internal::IsNoThrowSwappable>()); - ASSERT_TRUE(container_internal::IsNoThrowSwappable< - std::equal_to>()); - ASSERT_TRUE(container_internal::IsNoThrowSwappable>()); - EXPECT_TRUE(container_internal::IsNoThrowSwappable()); -} - -TEST(Table, HeterogeneousLookup) { - struct Hash { - size_t operator()(int64_t i) const { return i; } - size_t operator()(double i) const { - ADD_FAILURE(); - return i; - } - }; - struct Eq { - bool operator()(int64_t a, int64_t b) const { return a == b; } - bool operator()(double a, int64_t b) const { - ADD_FAILURE(); - return a == b; - } - bool operator()(int64_t a, double b) const { - ADD_FAILURE(); - return a == b; - } - bool operator()(double a, double b) const { - ADD_FAILURE(); - return a == b; - } - }; - - struct THash { - using is_transparent = void; - size_t operator()(int64_t i) const { return i; } - size_t operator()(double i) const { return i; } - }; - struct TEq { - using is_transparent = void; - bool operator()(int64_t a, int64_t b) const { return a == b; } - bool operator()(double a, int64_t b) const { return a == b; } - bool operator()(int64_t a, double b) const { return a == b; } - bool operator()(double a, double b) const { return a == b; } - }; - - raw_hash_set> s{0, 1, 2}; - // It will convert to int64_t before the query. - EXPECT_EQ(1, *s.find(double{1.1})); - - raw_hash_set> ts{0, 1, 2}; - // It will try to use the double, and fail to find the object. - EXPECT_TRUE(ts.find(1.1) == ts.end()); -} - -template -using CallFind = decltype(std::declval().find(17)); - -template -using CallErase = decltype(std::declval().erase(17)); - -template -using CallExtract = decltype(std::declval().extract(17)); - -template -using CallPrefetch = decltype(std::declval().prefetch(17)); - -template -using CallCount = decltype(std::declval().count(17)); - -template