summaryrefslogtreecommitdiff
path: root/absl/container/internal/raw_hash_set_test.cc
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container/internal/raw_hash_set_test.cc')
-rw-r--r--absl/container/internal/raw_hash_set_test.cc1961
1 files changed, 1961 insertions, 0 deletions
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
new file mode 100644
index 00000000..f59a19b4
--- /dev/null
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -0,0 +1,1961 @@
+// 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
+//
+// http://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 <array>
+#include <cmath>
+#include <cstdint>
+#include <deque>
+#include <functional>
+#include <memory>
+#include <numeric>
+#include <random>
+#include <string>
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/base/attributes.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 {
+namespace container_internal {
+
+struct RawHashSetTestOnlyAccess {
+ template <typename C>
+ static auto GetSlots(const C& c) -> decltype(c.slots_) {
+ return c.slots_;
+ }
+};
+
+namespace {
+
+using ::testing::DoubleNear;
+using ::testing::ElementsAre;
+using ::testing::Optional;
+using ::testing::Pair;
+using ::testing::UnorderedElementsAre;
+
+TEST(Util, NormalizeCapacity) {
+ constexpr size_t kMinCapacity = Group::kWidth - 1;
+ EXPECT_EQ(kMinCapacity, NormalizeCapacity(0));
+ EXPECT_EQ(kMinCapacity, NormalizeCapacity(1));
+ EXPECT_EQ(kMinCapacity, NormalizeCapacity(2));
+ EXPECT_EQ(kMinCapacity, NormalizeCapacity(kMinCapacity));
+ EXPECT_EQ(kMinCapacity * 2 + 1, NormalizeCapacity(kMinCapacity + 1));
+ EXPECT_EQ(kMinCapacity * 2 + 1, NormalizeCapacity(kMinCapacity + 2));
+}
+
+TEST(Util, probe_seq) {
+ probe_seq<16> seq(0, 127);
+ auto gen = [&]() {
+ size_t res = seq.offset();
+ seq.next();
+ return res;
+ };
+ std::vector<size_t> 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<uint8_t, 8>(0)));
+ EXPECT_TRUE((BitMask<uint8_t, 8>(5)));
+
+ EXPECT_THAT((BitMask<uint8_t, 8>(0)), ElementsAre());
+ EXPECT_THAT((BitMask<uint8_t, 8>(0x1)), ElementsAre(0));
+ EXPECT_THAT((BitMask<uint8_t, 8>(0x2)), ElementsAre(1));
+ EXPECT_THAT((BitMask<uint8_t, 8>(0x3)), ElementsAre(0, 1));
+ EXPECT_THAT((BitMask<uint8_t, 8>(0x4)), ElementsAre(2));
+ EXPECT_THAT((BitMask<uint8_t, 8>(0x5)), ElementsAre(0, 2));
+ EXPECT_THAT((BitMask<uint8_t, 8>(0x55)), ElementsAre(0, 2, 4, 6));
+ EXPECT_THAT((BitMask<uint8_t, 8>(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<uint64_t, 8, 3> b(mask);
+ EXPECT_EQ(*b, 2);
+}
+
+TEST(BitMask, LeadingTrailing) {
+ EXPECT_EQ((BitMask<uint32_t, 16>(0b0001101001000000).LeadingZeros()), 3);
+ EXPECT_EQ((BitMask<uint32_t, 16>(0b0001101001000000).TrailingZeros()), 6);
+
+ EXPECT_EQ((BitMask<uint32_t, 16>(0b0000000000000001).LeadingZeros()), 15);
+ EXPECT_EQ((BitMask<uint32_t, 16>(0b0000000000000001).TrailingZeros()), 0);
+
+ EXPECT_EQ((BitMask<uint32_t, 16>(0b1000000000000000).LeadingZeros()), 0);
+ EXPECT_EQ((BitMask<uint32_t, 16>(0b1000000000000000).TrailingZeros()), 15);
+
+ EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x0000008080808000).LeadingZeros()), 3);
+ EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x0000008080808000).TrailingZeros()), 1);
+
+ EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x0000000000000080).LeadingZeros()), 7);
+ EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x0000000000000080).TrailingZeros()), 0);
+
+ EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x8000000000000000).LeadingZeros()), 0);
+ EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x8000000000000000).TrailingZeros()), 7);
+}
+
+TEST(Group, EmptyGroup) {
+ for (h2_t h = 0; h != 128; ++h) EXPECT_FALSE(Group{EmptyGroup()}.Match(h));
+}
+
+#if SWISSTABLE_HAVE_SSE2
+TEST(Group, Match) {
+ 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));
+}
+
+TEST(Group, MatchEmpty) {
+ 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));
+}
+
+TEST(Group, MatchEmptyOrDeleted) {
+ 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
+TEST(Group, Match) {
+ 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));
+}
+TEST(Group, MatchEmpty) {
+ ctrl_t group[] = {kEmpty, 1, 2, kDeleted, 2, 1, kSentinel, 1};
+ EXPECT_THAT(Group{group}.MatchEmpty(), ElementsAre(0));
+}
+
+TEST(Group, MatchEmptyOrDeleted) {
+ ctrl_t group[] = {kEmpty, 1, 2, kDeleted, 2, 1, kSentinel, 1};
+ EXPECT_THAT(Group{group}.MatchEmptyOrDeleted(), ElementsAre(0, 3));
+}
+#endif
+
+TEST(Batch, DropDeletes) {
+ constexpr size_t kCapacity = 63;
+ constexpr size_t kGroupWidth = container_internal::Group::kWidth;
+ std::vector<ctrl_t> ctrl(kCapacity + 1 + kGroupWidth);
+ ctrl[kCapacity] = kSentinel;
+ std::vector<ctrl_t> 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<ctrl_t> empty_examples = {kEmpty, kDeleted};
+ const std::vector<ctrl_t> full_examples = {0, 1, 2, 3, 5, 9, 127, kSentinel};
+
+ for (ctrl_t empty : empty_examples) {
+ std::vector<ctrl_t> 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<ctrl_t> f(Group::kWidth, empty);
+ f[i] = full;
+ EXPECT_EQ(i, Group{f.data()}.CountLeadingEmptyOrDeleted());
+ }
+ std::vector<ctrl_t> 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 <class F>
+ static auto apply(F&& f, int64_t x) -> decltype(std::forward<F>(f)(x, x)) {
+ return std::forward<F>(f)(x, x);
+ }
+};
+
+class StringPolicy {
+ template <class F, class K, class V,
+ class = typename std::enable_if<
+ std::is_convertible<const K&, absl::string_view>::value>::type>
+ decltype(std::declval<F>()(
+ std::declval<const absl::string_view&>(), std::piecewise_construct,
+ std::declval<std::tuple<K>>(),
+ std::declval<V>())) static apply_impl(F&& f,
+ std::pair<std::tuple<K>, V> p) {
+ const absl::string_view& key = std::get<0>(p.first);
+ return std::forward<F>(f)(key, std::piecewise_construct, std::move(p.first),
+ std::move(p.second));
+ }
+
+ public:
+ struct slot_type {
+ struct ctor {};
+
+ template <class... Ts>
+ slot_type(ctor, Ts&&... ts) : pair(std::forward<Ts>(ts)...) {}
+
+ std::pair<std::string, std::string> pair;
+ };
+
+ using key_type = std::string;
+ using init_type = std::pair<std::string, std::string>;
+
+ template <class allocator_type, class... Args>
+ static void construct(allocator_type* alloc, slot_type* slot, Args... args) {
+ std::allocator_traits<allocator_type>::construct(
+ *alloc, slot, typename slot_type::ctor(), std::forward<Args>(args)...);
+ }
+
+ template <class allocator_type>
+ static void destroy(allocator_type* alloc, slot_type* slot) {
+ std::allocator_traits<allocator_type>::destroy(*alloc, slot);
+ }
+
+ template <class allocator_type>
+ 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<std::string, std::string>& element(slot_type* slot) {
+ return slot->pair;
+ }
+
+ template <class F, class... Args>
+ static auto apply(F&& f, Args&&... args)
+ -> decltype(apply_impl(std::forward<F>(f),
+ PairArgs(std::forward<Args>(args)...))) {
+ return apply_impl(std::forward<F>(f),
+ PairArgs(std::forward<Args>(args)...));
+ }
+};
+
+struct StringHash : absl::Hash<absl::string_view> {
+ using is_transparent = void;
+};
+struct StringEq : std::equal_to<absl::string_view> {
+ using is_transparent = void;
+};
+
+struct StringTable
+ : raw_hash_set<StringPolicy, StringHash, StringEq, std::allocator<int>> {
+ using Base = typename StringTable::raw_hash_set;
+ StringTable() {}
+ using Base::Base;
+};
+
+struct IntTable
+ : raw_hash_set<IntPolicy, container_internal::hash_default_hash<int64_t>,
+ std::equal_to<int64_t>, std::allocator<int64_t>> {
+ using Base = typename IntTable::raw_hash_set;
+ IntTable() {}
+ using Base::Base;
+};
+
+struct BadFastHash {
+ template <class T>
+ size_t operator()(const T&) const {
+ return 0;
+ }
+};
+
+struct BadTable : raw_hash_set<IntPolicy, BadFastHash, std::equal_to<int>,
+ std::allocator<int>> {
+ using Base = typename BadTable::raw_hash_set;
+ BadTable() {}
+ using Base::Base;
+};
+
+TEST(Table, EmptyFunctorOptimization) {
+ static_assert(std::is_empty<std::equal_to<absl::string_view>>::value, "");
+ static_assert(std::is_empty<std::allocator<int>>::value, "");
+
+ struct MockTable {
+ void* ctrl;
+ void* slots;
+ size_t size;
+ size_t capacity;
+ size_t growth_left;
+ };
+ 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<StringPolicy, StatelessHash,
+ std::equal_to<absl::string_view>, std::allocator<int>>));
+
+ EXPECT_EQ(
+ sizeof(MockTable) + sizeof(StatefulHash),
+ sizeof(
+ raw_hash_set<StringPolicy, StatefulHash,
+ std::equal_to<absl::string_view>, std::allocator<int>>));
+}
+
+TEST(Table, Empty) {
+ IntTable t;
+ EXPECT_EQ(0, t.size());
+ EXPECT_TRUE(t.empty());
+}
+
+#ifdef __GNUC__
+template <class T>
+ABSL_ATTRIBUTE_ALWAYS_INLINE inline void DoNotOptimize(const T& v) {
+ asm volatile("" : : "r,m"(v) : "memory");
+}
+#endif
+
+TEST(Table, Prefetch) {
+ IntTable t;
+ t.emplace(1);
+ // Works for both present and absent keys.
+ t.prefetch(1);
+ t.prefetch(2);
+
+ // Do not run in debug mode, when prefetch is not implemented, or when
+ // sanitizers are enabled.
+#if defined(NDEBUG) && defined(__GNUC__) && !defined(ADDRESS_SANITIZER) && \
+ !defined(MEMORY_SANITIZER) && !defined(THREAD_SANITIZER) && \
+ !defined(UNDEFINED_BEHAVIOR_SANITIZER)
+ const auto now = [] { return absl::base_internal::CycleClock::Now(); };
+
+ static constexpr int size = 1000000;
+ for (int i = 0; i < size; ++i) t.insert(i);
+
+ int64_t no_prefetch = 0, prefetch = 0;
+ for (int iter = 0; iter < 10; ++iter) {
+ int64_t time = now();
+ for (int i = 0; i < size; ++i) {
+ DoNotOptimize(t.find(i));
+ }
+ no_prefetch += now() - time;
+
+ time = now();
+ for (int i = 0; i < size; ++i) {
+ t.prefetch(i + 20);
+ DoNotOptimize(t.find(i));
+ }
+ prefetch += now() - time;
+ }
+
+ // no_prefetch is at least 30% slower.
+ EXPECT_GE(1.0 * no_prefetch / prefetch, 1.3);
+#endif
+}
+
+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 <typename T>
+ static void construct(void*, DecomposeType* slot, T&& v) {
+ *slot = DecomposeType(std::forward<T>(v));
+ }
+ static void destroy(void*, DecomposeType*) {}
+ static DecomposeType& element(slot_type* slot) { return *slot; }
+
+ template <class F, class T>
+ static auto apply(F&& f, const T& x) -> decltype(std::forward<F>(f)(x, x)) {
+ return std::forward<F>(f)(x, x);
+ }
+};
+
+template <typename Hash, typename Eq>
+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<DecomposePolicy, Hash, Eq, std::allocator<int>> 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<DecomposeHash, DecomposeEq>(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<TransparentHashIntOverload, DecomposeEq>(true);
+ TestDecompose<TransparentHashIntOverload, TransparentEqIntOverload>(true);
+ TestDecompose<DecomposeHash, TransparentEqIntOverload>(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<IntPolicy, Modulo1000Hash, std::equal_to<int>,
+ std::allocator<int>> {};
+
+// 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 feel upto MaxDensitySize;
+ const size_t kMinFullGroups = 7;
+ std::vector<int> 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<int> 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;
+ for (size_t i = 0; i < max_size; ++i) {
+ t.insert(i);
+ }
+ ASSERT_EQ(capacity, t.capacity());
+ intptr_t original = reinterpret_cast<intptr_t>(&*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<intptr_t>(&*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());
+}
+
+// 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<int64_t> CollectBadMergeKeys(size_t N) {
+ static constexpr int kGroupSize = Group::kWidth - 1;
+
+ auto topk_range = [](size_t b, size_t e, IntTable* t) -> std::vector<int64_t> {
+ for (size_t i = b; i != e; ++i) {
+ t->emplace(i);
+ }
+ std::vector<int64_t> 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<int64_t> 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<size_t> all_probes_histogram;
+ // Ratios total_probe_length/size for every tested table.
+ std::vector<double> 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<size_t>());
+ 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<size_t>(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<double> ProbeNormalizedHistogram() const {
+ double total_elements = std::accumulate(all_probes_histogram.begin(),
+ all_probes_histogram.end(), 0ull);
+ std::vector<double> 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<std::pair<double, double>> pecentile_ratios;
+ std::vector<std::pair<double, double>> 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<size_t, ProbeStats>;
+
+// 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<int64_t>& 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<int64_t>(static_cast<uint64_t>(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>());
+
+ 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 =
+#if 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}}};
+ }
+ break;
+ 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}}};
+ }
+ break;
+ default:
+ ABSL_RAW_LOG(FATAL, "%s", "Unknown Group width");
+ }
+ return {};
+}
+TEST(Table, DISABLED_EnsureNonQuadraticTopNXorSeedByProbeSeqLength) {
+ ProbeStatsPerSize stats;
+ std::vector<size_t> 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<int64_t>& 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<size_t> 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>());
+
+ 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 =
+#if 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}}};
+ }
+ break;
+ 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}}};
+ }
+ break;
+ default:
+ ABSL_RAW_LOG(FATAL, "%s", "Unknown Group width");
+ }
+ return {};
+}
+TEST(Table, DISABLED_EnsureNonQuadraticTopNLinearTransformByProbeSeqLength) {
+ ProbeStatsPerSize stats;
+ std::vector<size_t> 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<std::string, std::string>;
+ struct Q {
+ operator P() const { return {}; }
+ };
+ StringTable t = {P(), Q(), {}, {{}, {}}};
+}
+
+TEST(Table, CopyConstruct) {
+ IntTable t;
+ t.max_load_factor(.321f);
+ t.emplace(0);
+ EXPECT_EQ(1, t.size());
+ {
+ IntTable u(t);
+ EXPECT_EQ(1, u.size());
+ EXPECT_EQ(t.max_load_factor(), u.max_load_factor());
+ EXPECT_THAT(*u.find(0), 0);
+ }
+ {
+ IntTable u{t};
+ EXPECT_EQ(1, u.size());
+ EXPECT_EQ(t.max_load_factor(), u.max_load_factor());
+ EXPECT_THAT(*u.find(0), 0);
+ }
+ {
+ IntTable u = t;
+ EXPECT_EQ(1, u.size());
+ EXPECT_EQ(t.max_load_factor(), u.max_load_factor());
+ EXPECT_THAT(*u.find(0), 0);
+ }
+}
+
+TEST(Table, CopyConstructWithAlloc) {
+ StringTable t;
+ t.max_load_factor(.321f);
+ t.emplace("a", "b");
+ EXPECT_EQ(1, t.size());
+ StringTable u(t, Alloc<std::pair<std::string, std::string>>());
+ EXPECT_EQ(1, u.size());
+ EXPECT_EQ(t.max_load_factor(), u.max_load_factor());
+ EXPECT_THAT(*u.find("a"), Pair("a", "b"));
+}
+
+struct ExplicitAllocIntTable
+ : raw_hash_set<IntPolicy, container_internal::hash_default_hash<int64_t>,
+ std::equal_to<int64_t>, Alloc<int64_t>> {
+ ExplicitAllocIntTable() {}
+};
+
+TEST(Table, AllocWithExplicitCtor) {
+ ExplicitAllocIntTable t;
+ EXPECT_EQ(0, t.size());
+}
+
+TEST(Table, MoveConstruct) {
+ {
+ StringTable t;
+ t.max_load_factor(.321f);
+ const float lf = t.max_load_factor();
+ t.emplace("a", "b");
+ EXPECT_EQ(1, t.size());
+
+ StringTable u(std::move(t));
+ EXPECT_EQ(1, u.size());
+ EXPECT_EQ(lf, u.max_load_factor());
+ EXPECT_THAT(*u.find("a"), Pair("a", "b"));
+ }
+ {
+ StringTable t;
+ t.max_load_factor(.321f);
+ const float lf = t.max_load_factor();
+ t.emplace("a", "b");
+ EXPECT_EQ(1, t.size());
+
+ StringTable u{std::move(t)};
+ EXPECT_EQ(1, u.size());
+ EXPECT_EQ(lf, u.max_load_factor());
+ EXPECT_THAT(*u.find("a"), Pair("a", "b"));
+ }
+ {
+ StringTable t;
+ t.max_load_factor(.321f);
+ const float lf = t.max_load_factor();
+ t.emplace("a", "b");
+ EXPECT_EQ(1, t.size());
+
+ StringTable u = std::move(t);
+ EXPECT_EQ(1, u.size());
+ EXPECT_EQ(lf, u.max_load_factor());
+ EXPECT_THAT(*u.find("a"), Pair("a", "b"));
+ }
+}
+
+TEST(Table, MoveConstructWithAlloc) {
+ StringTable t;
+ t.max_load_factor(.321f);
+ const float lf = t.max_load_factor();
+ t.emplace("a", "b");
+ EXPECT_EQ(1, t.size());
+ StringTable u(std::move(t), Alloc<std::pair<std::string, std::string>>());
+ EXPECT_EQ(1, u.size());
+ EXPECT_EQ(lf, u.max_load_factor());
+ EXPECT_THAT(*u.find("a"), Pair("a", "b"));
+}
+
+TEST(Table, CopyAssign) {
+ StringTable t;
+ t.max_load_factor(.321f);
+ t.emplace("a", "b");
+ EXPECT_EQ(1, t.size());
+ StringTable u;
+ u = t;
+ EXPECT_EQ(1, u.size());
+ EXPECT_EQ(t.max_load_factor(), u.max_load_factor());
+ EXPECT_THAT(*u.find("a"), Pair("a", "b"));
+}
+
+TEST(Table, CopySelfAssign) {
+ StringTable t;
+ t.max_load_factor(.321f);
+ const float lf = t.max_load_factor();
+ t.emplace("a", "b");
+ EXPECT_EQ(1, t.size());
+ t = *&t;
+ EXPECT_EQ(1, t.size());
+ EXPECT_EQ(lf, t.max_load_factor());
+ EXPECT_THAT(*t.find("a"), Pair("a", "b"));
+}
+
+TEST(Table, MoveAssign) {
+ StringTable t;
+ t.max_load_factor(.321f);
+ const float lf = t.max_load_factor();
+ t.emplace("a", "b");
+ EXPECT_EQ(1, t.size());
+ StringTable u;
+ u = std::move(t);
+ EXPECT_EQ(1, u.size());
+ EXPECT_EQ(lf, u.max_load_factor());
+ EXPECT_THAT(*u.find("a"), Pair("a", "b"));
+}
+
+TEST(Table, Equality) {
+ StringTable t;
+ std::vector<std::pair<std::string, std::string>> 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<std::pair<std::string, std::string>> v1 = {{"a", "b"}, {"aa", "bb"}};
+ t.insert(std::begin(v1), std::end(v1));
+ StringTable u;
+ std::vector<std::pair<std::string, std::string>> v2 = {{"a", "a"}, {"aa", "aa"}};
+ u.insert(std::begin(v2), std::end(v2));
+ EXPECT_NE(u, t);
+}
+
+TEST(Table, Equality3) {
+ StringTable t;
+ std::vector<std::pair<std::string, std::string>> v1 = {{"b", "b"}, {"bb", "bb"}};
+ t.insert(std::begin(v1), std::end(v1));
+ StringTable u;
+ std::vector<std::pair<std::string, std::string>> 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<absl::Hash<absl::string_view>>::value);
+ ASSERT_TRUE(std::is_nothrow_copy_constructible<
+ std::equal_to<absl::string_view>>::value);
+ ASSERT_TRUE(std::is_nothrow_copy_constructible<std::allocator<int>>::value);
+ EXPECT_TRUE(std::is_nothrow_move_constructible<StringTable>::value);
+}
+
+TEST(Table, NoThrowMoveAssign) {
+ ASSERT_TRUE(
+ std::is_nothrow_move_assignable<absl::Hash<absl::string_view>>::value);
+ ASSERT_TRUE(
+ std::is_nothrow_move_assignable<std::equal_to<absl::string_view>>::value);
+ ASSERT_TRUE(std::is_nothrow_move_assignable<std::allocator<int>>::value);
+ ASSERT_TRUE(
+ absl::allocator_traits<std::allocator<int>>::is_always_equal::value);
+ EXPECT_TRUE(std::is_nothrow_move_assignable<StringTable>::value);
+}
+
+TEST(Table, NoThrowSwappable) {
+ ASSERT_TRUE(
+ container_internal::IsNoThrowSwappable<absl::Hash<absl::string_view>>());
+ ASSERT_TRUE(container_internal::IsNoThrowSwappable<
+ std::equal_to<absl::string_view>>());
+ ASSERT_TRUE(container_internal::IsNoThrowSwappable<std::allocator<int>>());
+ EXPECT_TRUE(container_internal::IsNoThrowSwappable<StringTable>());
+}
+
+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<IntPolicy, Hash, Eq, Alloc<int64_t>> s{0, 1, 2};
+ // It will convert to int64_t before the query.
+ EXPECT_EQ(1, *s.find(double{1.1}));
+
+ raw_hash_set<IntPolicy, THash, TEq, Alloc<int64_t>> 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 <class Table>
+using CallFind = decltype(std::declval<Table&>().find(17));
+
+template <class Table>
+using CallErase = decltype(std::declval<Table&>().erase(17));
+
+template <class Table>
+using CallExtract = decltype(std::declval<Table&>().extract(17));
+
+template <class Table>
+using CallPrefetch = decltype(std::declval<Table&>().prefetch(17));
+
+template <class Table>
+using CallCount = decltype(std::declval<Table&>().count(17));
+
+template <template <typename> class C, class Table, class = void>
+struct VerifyResultOf : std::false_type {};
+
+template <template <typename> class C, class Table>
+struct VerifyResultOf<C, Table, absl::void_t<C<Table>>> : std::true_type {};
+
+TEST(Table, HeterogeneousLookupOverloads) {
+ using NonTransparentTable =
+ raw_hash_set<StringPolicy, absl::Hash<absl::string_view>,
+ std::equal_to<absl::string_view>, std::allocator<int>>;
+
+ EXPECT_FALSE((VerifyResultOf<CallFind, NonTransparentTable>()));
+ EXPECT_FALSE((VerifyResultOf<CallErase, NonTransparentTable>()));
+ EXPECT_FALSE((VerifyResultOf<CallExtract, NonTransparentTable>()));
+ EXPECT_FALSE((VerifyResultOf<CallPrefetch, NonTransparentTable>()));
+ EXPECT_FALSE((VerifyResultOf<CallCount, NonTransparentTable>()));
+
+ using TransparentTable = raw_hash_set<
+ StringPolicy,
+ absl::container_internal::hash_default_hash<absl::string_view>,
+ absl::container_internal::hash_default_eq<absl::string_view>,
+ std::allocator<int>>;
+
+ EXPECT_TRUE((VerifyResultOf<CallFind, TransparentTable>()));
+ EXPECT_TRUE((VerifyResultOf<CallErase, TransparentTable>()));
+ EXPECT_TRUE((VerifyResultOf<CallExtract, TransparentTable>()));
+ EXPECT_TRUE((VerifyResultOf<CallPrefetch, TransparentTable>()));
+ EXPECT_TRUE((VerifyResultOf<CallCount, TransparentTable>()));
+}
+
+// TODO(alkis): Expand iterator tests.
+TEST(Iterator, IsDefaultConstructible) {
+ StringTable::iterator i;
+ EXPECT_TRUE(i == StringTable::iterator());
+}
+
+TEST(ConstIterator, IsDefaultConstructible) {
+ StringTable::const_iterator i;
+ EXPECT_TRUE(i == StringTable::const_iterator());
+}
+
+TEST(Iterator, ConvertsToConstIterator) {
+ StringTable::iterator i;
+ EXPECT_TRUE(i == StringTable::const_iterator());
+}
+
+TEST(Iterator, Iterates) {
+ IntTable t;
+ for (size_t i = 3; i != 6; ++i) EXPECT_TRUE(t.emplace(i).second);
+ EXPECT_THAT(t, UnorderedElementsAre(3, 4, 5));
+}
+
+TEST(Table, Merge) {
+ StringTable t1, t2;
+ t1.emplace("0", "-0");
+ t1.emplace("1", "-1");
+ t2.emplace("0", "~0");
+ t2.emplace("2", "~2");
+
+ EXPECT_THAT(t1, UnorderedElementsAre(Pair("0", "-0"), Pair("1", "-1")));
+ EXPECT_THAT(t2, UnorderedElementsAre(Pair("0", "~0"), Pair("2", "~2")));
+
+ t1.merge(t2);
+ EXPECT_THAT(t1, UnorderedElementsAre(Pair("0", "-0"), Pair("1", "-1"),
+ Pair("2", "~2")));
+ EXPECT_THAT(t2, UnorderedElementsAre(Pair("0", "~0")));
+}
+
+TEST(Nodes, EmptyNodeType) {
+ using node_type = StringTable::node_type;
+ node_type n;
+ EXPECT_FALSE(n);
+ EXPECT_TRUE(n.empty());
+
+ EXPECT_TRUE((std::is_same<node_type::allocator_type,
+ StringTable::allocator_type>::value));
+}
+
+TEST(Nodes, ExtractInsert) {
+ constexpr char k0[] = "Very long std::string zero.";
+ constexpr char k1[] = "Very long std::string one.";
+ constexpr char k2[] = "Very long std::string two.";
+ StringTable t = {{k0, ""}, {k1, ""}, {k2, ""}};
+ EXPECT_THAT(t,
+ UnorderedElementsAre(Pair(k0, ""), Pair(k1, ""), Pair(k2, "")));
+
+ auto node = t.extract(k0);
+ EXPECT_THAT(t, UnorderedElementsAre(Pair(k1, ""), Pair(k2, "")));
+ EXPECT_TRUE(node);
+ EXPECT_FALSE(node.empty());
+
+ StringTable t2;
+ auto res = t2.insert(std::move(node));
+ EXPECT_TRUE(res.inserted);
+ EXPECT_THAT(*res.position, Pair(k0, ""));
+ EXPECT_FALSE(res.node);
+ EXPECT_THAT(t2, UnorderedElementsAre(Pair(k0, "")));
+
+ // Not there.
+ EXPECT_THAT(t, UnorderedElementsAre(Pair(k1, ""), Pair(k2, "")));
+ node = t.extract("Not there!");
+ EXPECT_THAT(t, UnorderedElementsAre(Pair(k1, ""), Pair(k2, "")));
+ EXPECT_FALSE(node);
+
+ // Inserting nothing.
+ res = t2.insert(std::move(node));
+ EXPECT_FALSE(res.inserted);
+ EXPECT_EQ(res.position, t2.end());
+ EXPECT_FALSE(res.node);
+ EXPECT_THAT(t2, UnorderedElementsAre(Pair(k0, "")));
+
+ t.emplace(k0, "1");
+ node = t.extract(k0);
+
+ // Insert duplicate.
+ res = t2.insert(std::move(node));
+ EXPECT_FALSE(res.inserted);
+ EXPECT_THAT(*res.position, Pair(k0, ""));
+ EXPECT_TRUE(res.node);
+ EXPECT_FALSE(node);
+}
+
+StringTable MakeSimpleTable(size_t size) {
+ StringTable t;
+ for (size_t i = 0; i < size; ++i) t.emplace(std::string(1, 'A' + i), "");
+ return t;
+}
+
+std::string OrderOfIteration(const StringTable& t) {
+ std::string order;
+ for (auto& p : t) order += p.first;
+ return order;
+}
+
+TEST(Table, IterationOrderChangesByInstance) {
+ // Needs to be more than kWidth elements to be able to affect order.
+ const StringTable reference = MakeSimpleTable(20);
+
+ // Since order is non-deterministic we can't just try once and verify.
+ // We'll try until we find that order changed. It should not take many tries
+ // for that.
+ // Important: we have to keep the old tables around. Otherwise tcmalloc will
+ // just give us the same blocks and we would be doing the same order again.
+ std::vector<StringTable> garbage;
+ for (int i = 0; i < 10; ++i) {
+ auto trial = MakeSimpleTable(20);
+ if (OrderOfIteration(trial) != OrderOfIteration(reference)) {
+ // We are done.
+ return;
+ }
+ garbage.push_back(std::move(trial));
+ }
+ FAIL();
+}
+
+TEST(Table, IterationOrderChangesOnRehash) {
+ // Since order is non-deterministic we can't just try once and verify.
+ // We'll try until we find that order changed. It should not take many tries
+ // for that.
+ // Important: we have to keep the old tables around. Otherwise tcmalloc will
+ // just give us the same blocks and we would be doing the same order again.
+ std::vector<StringTable> garbage;
+ for (int i = 0; i < 10; ++i) {
+ // Needs to be more than kWidth elements to be able to affect order.
+ StringTable t = MakeSimpleTable(20);
+ const std::string reference = OrderOfIteration(t);
+ // Force rehash to the same size.
+ t.rehash(0);
+ std::string trial = OrderOfIteration(t);
+ if (trial != reference) {
+ // We are done.
+ return;
+ }
+ garbage.push_back(std::move(t));
+ }
+ FAIL();
+}
+
+TEST(Table, IterationOrderChangesForSmallTables) {
+ // Since order is non-deterministic we can't just try once and verify.
+ // We'll try until we find that order changed.
+ // Important: we have to keep the old tables around. Otherwise tcmalloc will
+ // just give us the same blocks and we would be doing the same order again.
+ StringTable reference_table = MakeSimpleTable(5);
+ const std::string reference = OrderOfIteration(reference_table);
+ std::vector<StringTable> garbage;
+ for (int i = 0; i < 50; ++i) {
+ StringTable t = MakeSimpleTable(5);
+ std::string trial = OrderOfIteration(t);
+ if (trial != reference) {
+ // We are done.
+ return;
+ }
+ garbage.push_back(std::move(t));
+ }
+ FAIL() << "Iteration order remained the same across many attempts.";
+}
+
+// Fill the table to 3 different load factors (min, median, max) and evaluate
+// the percentage of perfect hits using the debug API.
+template <class Table, class AddFn>
+std::vector<double> CollectPerfectRatios(Table t, AddFn add) {
+ using Key = typename Table::key_type;
+
+ // First, fill enough to have a good distribution.
+ constexpr size_t kMinSize = 10000;
+ std::vector<Key> keys;
+ while (t.size() < kMinSize) keys.push_back(add(t));
+ // Then, insert until we reach min load factor.
+ double lf = t.load_factor();
+ while (lf <= t.load_factor()) keys.push_back(add(t));
+
+ // We are now at min load factor. Take a snapshot.
+ size_t perfect = 0;
+ auto update_perfect = [&](Key k) {
+ perfect += GetHashtableDebugNumProbes(t, k) == 0;
+ };
+ for (const auto& k : keys) update_perfect(k);
+
+ std::vector<double> perfect_ratios;
+ // Keep going until we hit max load factor.
+ while (t.load_factor() < .6) {
+ perfect_ratios.push_back(1.0 * perfect / t.size());
+ update_perfect(add(t));
+ }
+ while (t.load_factor() > .5) {
+ perfect_ratios.push_back(1.0 * perfect / t.size());
+ update_perfect(add(t));
+ }
+ return perfect_ratios;
+}
+
+std::vector<std::pair<double, double>> StringTablePefectRatios() {
+ constexpr bool kRandomizesInserts =
+#if 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.986, 0.02}, {0.95, 0.02}, {0.89, 0.02}};
+ } else {
+ return {{0.995, 0.01}, {0.97, 0.01}, {0.89, 0.02}};
+ }
+ break;
+ case 16:
+ if (kRandomizesInserts) {
+ return {{0.973, 0.01}, {0.965, 0.01}, {0.92, 0.02}};
+ } else {
+ return {{0.995, 0.005}, {0.99, 0.005}, {0.94, 0.01}};
+ }
+ break;
+ default:
+ // Ignore anything else.
+ return {};
+ }
+}
+
+// This is almost a change detector, but it allows us to know how we are
+// affecting the probe distribution.
+TEST(Table, EffectiveLoadFactorStrings) {
+ std::vector<double> perfect_ratios =
+ CollectPerfectRatios(StringTable(), [](StringTable& t) {
+ return t.emplace(std::to_string(t.size()), "").first->first;
+ });
+
+ auto ratios = StringTablePefectRatios();
+ if (ratios.empty()) return;
+
+ EXPECT_THAT(perfect_ratios.front(),
+ DoubleNear(ratios[0].first, ratios[0].second));
+ EXPECT_THAT(perfect_ratios[perfect_ratios.size() / 2],
+ DoubleNear(ratios[1].first, ratios[1].second));
+ EXPECT_THAT(perfect_ratios.back(),
+ DoubleNear(ratios[2].first, ratios[2].second));
+}
+
+std::vector<std::pair<double, double>> IntTablePefectRatios() {
+ 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.99, 0.02}, {0.985, 0.02}, {0.95, 0.05}};
+ } else {
+ return {{0.99, 0.01}, {0.99, 0.01}, {0.95, 0.02}};
+ }
+ break;
+ case 16:
+ if (kRandomizesInserts) {
+ return {{0.98, 0.02}, {0.978, 0.02}, {0.96, 0.02}};
+ } else {
+ return {{0.998, 0.003}, {0.995, 0.01}, {0.975, 0.02}};
+ }
+ break;
+ default:
+ // Ignore anything else.
+ return {};
+ }
+}
+
+// This is almost a change detector, but it allows us to know how we are
+// affecting the probe distribution.
+TEST(Table, EffectiveLoadFactorInts) {
+ std::vector<double> perfect_ratios = CollectPerfectRatios(
+ IntTable(), [](IntTable& t) { return *t.emplace(t.size()).first; });
+
+ auto ratios = IntTablePefectRatios();
+ if (ratios.empty()) return;
+
+ EXPECT_THAT(perfect_ratios.front(),
+ DoubleNear(ratios[0].first, ratios[0].second));
+ EXPECT_THAT(perfect_ratios[perfect_ratios.size() / 2],
+ DoubleNear(ratios[1].first, ratios[1].second));
+ EXPECT_THAT(perfect_ratios.back(),
+ DoubleNear(ratios[2].first, ratios[2].second));
+}
+
+// Confirm that we assert if we try to erase() end().
+TEST(Table, EraseOfEndAsserts) {
+ // Use an assert with side-effects to figure out if they are actually enabled.
+ bool assert_enabled = false;
+ assert([&]() {
+ assert_enabled = true;
+ return true;
+ }());
+ if (!assert_enabled) return;
+
+ IntTable t;
+ // Extra simple "regexp" as regexp support is highly varied across platforms.
+ constexpr char kDeathMsg[] = "it != end";
+ EXPECT_DEATH(t.erase(t.end()), kDeathMsg);
+}
+
+#ifdef ADDRESS_SANITIZER
+TEST(Sanitizer, PoisoningUnused) {
+ IntTable t;
+ // Insert something to force an allocation.
+ int64_t& v1 = *t.insert(0).first;
+
+ // Make sure there is something to test.
+ ASSERT_GT(t.capacity(), 1);
+
+ int64_t* slots = RawHashSetTestOnlyAccess::GetSlots(t);
+ for (size_t i = 0; i < t.capacity(); ++i) {
+ EXPECT_EQ(slots + i != &v1, __asan_address_is_poisoned(slots + i));
+ }
+}
+
+TEST(Sanitizer, PoisoningOnErase) {
+ IntTable t;
+ int64_t& v = *t.insert(0).first;
+
+ EXPECT_FALSE(__asan_address_is_poisoned(&v));
+ t.erase(0);
+ EXPECT_TRUE(__asan_address_is_poisoned(&v));
+}
+#endif // ADDRESS_SANITIZER
+
+} // namespace
+} // namespace container_internal
+} // namespace absl