diff options
Diffstat (limited to 'third_party/abseil-cpp/absl/container')
14 files changed, 387 insertions, 140 deletions
diff --git a/third_party/abseil-cpp/absl/container/CMakeLists.txt b/third_party/abseil-cpp/absl/container/CMakeLists.txt index 2d7d0e65f2..91c4015437 100644 --- a/third_party/abseil-cpp/absl/container/CMakeLists.txt +++ b/third_party/abseil-cpp/absl/container/CMakeLists.txt @@ -80,7 +80,7 @@ absl_cc_test( absl::strings absl::test_instance_tracker absl::type_traits - gmock_main + GTest::gmock_main ) absl_cc_library( @@ -109,7 +109,7 @@ absl_cc_test( absl::optional absl::test_instance_tracker absl::utility - gmock_main + GTest::gmock_main ) absl_cc_library( @@ -144,7 +144,7 @@ absl_cc_test( absl::exception_testing absl::hash_testing absl::memory - gmock_main + GTest::gmock_main ) absl_cc_test( @@ -158,7 +158,7 @@ absl_cc_test( absl::fixed_array absl::config absl::exception_safety_testing - gmock_main + GTest::gmock_main ) absl_cc_library( @@ -222,7 +222,7 @@ absl_cc_test( absl::memory absl::raw_logging_internal absl::strings - gmock_main + GTest::gmock_main ) absl_cc_test( @@ -236,7 +236,7 @@ absl_cc_test( absl::inlined_vector absl::config absl::exception_safety_testing - gmock_main + GTest::gmock_main ) absl_cc_library( @@ -262,7 +262,7 @@ absl_cc_test( ${ABSL_TEST_COPTS} DEPS absl::test_instance_tracker - gmock_main + GTest::gmock_main ) absl_cc_library( @@ -297,7 +297,7 @@ absl_cc_test( absl::unordered_map_modifiers_test absl::any absl::raw_logging_internal - gmock_main + GTest::gmock_main ) absl_cc_library( @@ -335,7 +335,7 @@ absl_cc_test( absl::memory absl::raw_logging_internal absl::strings - gmock_main + GTest::gmock_main ) absl_cc_library( @@ -370,7 +370,7 @@ absl_cc_test( absl::unordered_map_lookup_test absl::unordered_map_members_test absl::unordered_map_modifiers_test - gmock_main + GTest::gmock_main ) absl_cc_library( @@ -404,7 +404,7 @@ absl_cc_test( absl::unordered_set_lookup_test absl::unordered_set_members_test absl::unordered_set_modifiers_test - gmock_main + GTest::gmock_main ) absl_cc_library( @@ -433,7 +433,7 @@ absl_cc_test( absl::container_memory absl::strings absl::test_instance_tracker - gmock_main + GTest::gmock_main ) absl_cc_library( @@ -465,7 +465,7 @@ absl_cc_test( absl::hash absl::random_random absl::strings - gmock_main + GTest::gmock_main ) absl_cc_library( @@ -507,7 +507,7 @@ absl_cc_test( ${ABSL_TEST_COPTS} DEPS absl::hash_policy_testing - gmock_main + GTest::gmock_main ) absl_cc_library( @@ -531,7 +531,7 @@ absl_cc_test( ${ABSL_TEST_COPTS} DEPS absl::hash_policy_traits - gmock_main + GTest::gmock_main ) absl_cc_library( @@ -561,7 +561,7 @@ absl_cc_test( DEPS absl::hashtablez_sampler absl::have_sse - gmock_main + GTest::gmock_main ) absl_cc_library( @@ -618,7 +618,7 @@ absl_cc_test( DEPS absl::hash_policy_traits absl::node_hash_policy - gmock_main + GTest::gmock_main ) absl_cc_library( @@ -693,7 +693,7 @@ absl_cc_test( absl::core_headers absl::raw_logging_internal absl::strings - gmock_main + GTest::gmock_main ) absl_cc_test( @@ -707,7 +707,7 @@ absl_cc_test( absl::raw_hash_set absl::tracked absl::core_headers - gmock_main + GTest::gmock_main ) absl_cc_library( @@ -740,7 +740,7 @@ absl_cc_test( absl::core_headers absl::raw_logging_internal absl::span - gmock_main + GTest::gmock_main ) absl_cc_library( @@ -765,7 +765,7 @@ absl_cc_library( DEPS absl::hash_generator_testing absl::hash_policy_testing - gmock + GTest::gmock TESTONLY ) @@ -779,7 +779,7 @@ absl_cc_library( DEPS absl::hash_generator_testing absl::hash_policy_testing - gmock + GTest::gmock TESTONLY ) @@ -792,7 +792,7 @@ absl_cc_library( ${ABSL_TEST_COPTS} DEPS absl::type_traits - gmock + GTest::gmock TESTONLY ) @@ -806,7 +806,7 @@ absl_cc_library( DEPS absl::hash_generator_testing absl::hash_policy_testing - gmock + GTest::gmock TESTONLY ) @@ -820,7 +820,7 @@ absl_cc_library( DEPS absl::hash_generator_testing absl::hash_policy_testing - gmock + GTest::gmock TESTONLY ) @@ -834,7 +834,7 @@ absl_cc_library( DEPS absl::hash_generator_testing absl::hash_policy_testing - gmock + GTest::gmock TESTONLY ) @@ -847,7 +847,7 @@ absl_cc_library( ${ABSL_TEST_COPTS} DEPS absl::type_traits - gmock + GTest::gmock TESTONLY ) @@ -861,7 +861,7 @@ absl_cc_library( DEPS absl::hash_generator_testing absl::hash_policy_testing - gmock + GTest::gmock TESTONLY ) @@ -877,7 +877,7 @@ absl_cc_test( absl::unordered_set_lookup_test absl::unordered_set_members_test absl::unordered_set_modifiers_test - gmock_main + GTest::gmock_main ) absl_cc_test( @@ -892,5 +892,5 @@ absl_cc_test( absl::unordered_map_lookup_test absl::unordered_map_members_test absl::unordered_map_modifiers_test - gmock_main + GTest::gmock_main ) diff --git a/third_party/abseil-cpp/absl/container/btree_test.cc b/third_party/abseil-cpp/absl/container/btree_test.cc index 74337df2c1..d5d79151aa 100644 --- a/third_party/abseil-cpp/absl/container/btree_test.cc +++ b/third_party/abseil-cpp/absl/container/btree_test.cc @@ -1708,10 +1708,25 @@ TEST(Btree, StrSplitCompatible) { EXPECT_EQ(split_set, expected_set); } -// We can't use EXPECT_EQ/etc. to compare absl::weak_ordering because they -// convert literal 0 to int and absl::weak_ordering can only be compared with -// literal 0. Defining this function allows for avoiding ClangTidy warnings. -bool Identity(const bool b) { return b; } +TEST(Btree, KeyComp) { + absl::btree_set<int> s; + EXPECT_TRUE(s.key_comp()(1, 2)); + EXPECT_FALSE(s.key_comp()(2, 2)); + EXPECT_FALSE(s.key_comp()(2, 1)); + + absl::btree_map<int, int> m1; + EXPECT_TRUE(m1.key_comp()(1, 2)); + EXPECT_FALSE(m1.key_comp()(2, 2)); + EXPECT_FALSE(m1.key_comp()(2, 1)); + + // Even though we internally adapt the comparator of `m2` to be three-way and + // heterogeneous, the comparator we expose through key_comp() is the original + // unadapted comparator. + absl::btree_map<std::string, int> m2; + EXPECT_TRUE(m2.key_comp()("a", "b")); + EXPECT_FALSE(m2.key_comp()("b", "b")); + EXPECT_FALSE(m2.key_comp()("b", "a")); +} TEST(Btree, ValueComp) { absl::btree_set<int> s; @@ -1724,13 +1739,13 @@ TEST(Btree, ValueComp) { EXPECT_FALSE(m1.value_comp()(std::make_pair(2, 0), std::make_pair(2, 0))); EXPECT_FALSE(m1.value_comp()(std::make_pair(2, 0), std::make_pair(1, 0))); + // Even though we internally adapt the comparator of `m2` to be three-way and + // heterogeneous, the comparator we expose through value_comp() is based on + // the original unadapted comparator. absl::btree_map<std::string, int> m2; - EXPECT_TRUE(Identity( - m2.value_comp()(std::make_pair("a", 0), std::make_pair("b", 0)) < 0)); - EXPECT_TRUE(Identity( - m2.value_comp()(std::make_pair("b", 0), std::make_pair("b", 0)) == 0)); - EXPECT_TRUE(Identity( - m2.value_comp()(std::make_pair("b", 0), std::make_pair("a", 0)) > 0)); + EXPECT_TRUE(m2.value_comp()(std::make_pair("a", 0), std::make_pair("b", 0))); + EXPECT_FALSE(m2.value_comp()(std::make_pair("b", 0), std::make_pair("b", 0))); + EXPECT_FALSE(m2.value_comp()(std::make_pair("b", 0), std::make_pair("a", 0))); } TEST(Btree, DefaultConstruction) { @@ -2893,6 +2908,46 @@ TEST(Btree, AllocMoveConstructor_DifferentAlloc) { EXPECT_EQ(bytes_used2, original_bytes_used); } +bool IntCmp(const int a, const int b) { return a < b; } + +TEST(Btree, SupportsFunctionPtrComparator) { + absl::btree_set<int, decltype(IntCmp) *> set(IntCmp); + set.insert({1, 2, 3}); + EXPECT_THAT(set, ElementsAre(1, 2, 3)); + EXPECT_TRUE(set.key_comp()(1, 2)); + EXPECT_TRUE(set.value_comp()(1, 2)); + + absl::btree_map<int, int, decltype(IntCmp) *> map(&IntCmp); + map[1] = 1; + EXPECT_THAT(map, ElementsAre(Pair(1, 1))); + EXPECT_TRUE(map.key_comp()(1, 2)); + EXPECT_TRUE(map.value_comp()(std::make_pair(1, 1), std::make_pair(2, 2))); +} + +template <typename Compare> +struct TransparentPassThroughComp { + using is_transparent = void; + + // This will fail compilation if we attempt a comparison that Compare does not + // support, and the failure will happen inside the function implementation so + // it can't be avoided by using SFINAE on this comparator. + template <typename T, typename U> + bool operator()(const T &lhs, const U &rhs) const { + return Compare()(lhs, rhs); + } +}; + +TEST(Btree, + SupportsTransparentComparatorThatDoesNotImplementAllVisibleOperators) { + absl::btree_set<MultiKey, TransparentPassThroughComp<MultiKeyComp>> set; + set.insert(MultiKey{1, 2}); + EXPECT_TRUE(set.contains(1)); +} + +TEST(Btree, ConstructImplicitlyWithUnadaptedComparator) { + absl::btree_set<MultiKey, MultiKeyComp> set = {{}, MultiKeyComp{}}; +} + } // namespace } // namespace container_internal ABSL_NAMESPACE_END diff --git a/third_party/abseil-cpp/absl/container/flat_hash_map_test.cc b/third_party/abseil-cpp/absl/container/flat_hash_map_test.cc index 89ec60c916..8dda1d3539 100644 --- a/third_party/abseil-cpp/absl/container/flat_hash_map_test.cc +++ b/third_party/abseil-cpp/absl/container/flat_hash_map_test.cc @@ -282,6 +282,32 @@ TEST(FlatHashMap, NodeHandleMutableKeyAccess) { } #endif +TEST(FlatHashMap, Reserve) { + // Verify that if we reserve(size() + n) then we can perform n insertions + // without a rehash, i.e., without invalidating any references. + for (size_t trial = 0; trial < 20; ++trial) { + for (size_t initial = 3; initial < 100; ++initial) { + // Fill in `initial` entries, then erase 2 of them, then reserve space for + // two inserts and check for reference stability while doing the inserts. + flat_hash_map<size_t, size_t> map; + for (size_t i = 0; i < initial; ++i) { + map[i] = i; + } + map.erase(0); + map.erase(1); + map.reserve(map.size() + 2); + size_t& a2 = map[2]; + // In the event of a failure, asan will complain in one of these two + // assignments. + map[initial] = a2; + map[initial + 1] = a2; + // Fail even when not under asan: + size_t& a2new = map[2]; + EXPECT_EQ(&a2, &a2new); + } + } +} + } // namespace } // namespace container_internal ABSL_NAMESPACE_END diff --git a/third_party/abseil-cpp/absl/container/internal/btree.h b/third_party/abseil-cpp/absl/container/internal/btree.h index 00444a5397..f636c5fc73 100644 --- a/third_party/abseil-cpp/absl/container/internal/btree.h +++ b/third_party/abseil-cpp/absl/container/internal/btree.h @@ -88,7 +88,12 @@ struct StringBtreeDefaultLess { // Compatibility constructor. StringBtreeDefaultLess(std::less<std::string>) {} // NOLINT - StringBtreeDefaultLess(std::less<string_view>) {} // NOLINT + StringBtreeDefaultLess(std::less<absl::string_view>) {} // NOLINT + + // Allow converting to std::less for use in key_comp()/value_comp(). + explicit operator std::less<std::string>() const { return {}; } + explicit operator std::less<absl::string_view>() const { return {}; } + explicit operator std::less<absl::Cord>() const { return {}; } absl::weak_ordering operator()(absl::string_view lhs, absl::string_view rhs) const { @@ -115,7 +120,12 @@ struct StringBtreeDefaultGreater { StringBtreeDefaultGreater() = default; StringBtreeDefaultGreater(std::greater<std::string>) {} // NOLINT - StringBtreeDefaultGreater(std::greater<string_view>) {} // NOLINT + StringBtreeDefaultGreater(std::greater<absl::string_view>) {} // NOLINT + + // Allow converting to std::greater for use in key_comp()/value_comp(). + explicit operator std::greater<std::string>() const { return {}; } + explicit operator std::greater<absl::string_view>() const { return {}; } + explicit operator std::greater<absl::Cord>() const { return {}; } absl::weak_ordering operator()(absl::string_view lhs, absl::string_view rhs) const { @@ -217,6 +227,8 @@ struct prefers_linear_node_search< template <typename Key, typename Compare, typename Alloc, int TargetNodeSize, bool Multi, typename SlotPolicy> struct common_params { + using original_key_compare = Compare; + // If Compare is a common comparator for a string-like type, then we adapt it // to use heterogeneous lookup and to be a key-compare-to comparator. using key_compare = typename key_compare_to_adapter<Compare>::type; @@ -317,16 +329,21 @@ struct map_params : common_params<Key, Compare, Alloc, TargetNodeSize, Multi, using value_type = typename super_type::value_type; using init_type = typename super_type::init_type; - using key_compare = typename super_type::key_compare; - // Inherit from key_compare for empty base class optimization. - struct value_compare : private key_compare { - value_compare() = default; - explicit value_compare(const key_compare &cmp) : key_compare(cmp) {} + using original_key_compare = typename super_type::original_key_compare; + // Reference: https://en.cppreference.com/w/cpp/container/map/value_compare + class value_compare { + template <typename Params> + friend class btree; - template <typename T, typename U> - auto operator()(const T &left, const U &right) const - -> decltype(std::declval<key_compare>()(left.first, right.first)) { - return key_compare::operator()(left.first, right.first); + protected: + explicit value_compare(original_key_compare c) : comp(std::move(c)) {} + + original_key_compare comp; // NOLINT + + public: + auto operator()(const value_type &lhs, const value_type &rhs) const + -> decltype(comp(lhs.first, rhs.first)) { + return comp(lhs.first, rhs.first); } }; using is_map_container = std::true_type; @@ -392,7 +409,8 @@ struct set_params : common_params<Key, Compare, Alloc, TargetNodeSize, Multi, set_slot_policy<Key>> { using value_type = Key; using slot_type = typename set_params::common_params::slot_type; - using value_compare = typename set_params::common_params::key_compare; + using value_compare = + typename set_params::common_params::original_key_compare; using is_map_container = std::false_type; template <typename V> @@ -484,8 +502,8 @@ class btree_node { std::is_same<std::greater<key_type>, key_compare>::value)>; - // This class is organized by gtl::Layout as if it had the following - // structure: + // This class is organized by absl::container_internal::Layout as if it had + // the following structure: // // A pointer to the node's parent. // btree_node *parent; // @@ -579,10 +597,10 @@ class btree_node { }; // Leaves can have less than kNodeSlots values. - constexpr static layout_type LeafLayout(const int slots = kNodeSlots) { + constexpr static layout_type LeafLayout(const int slot_count = kNodeSlots) { return layout_type(/*parent*/ 1, /*position, start, finish, max_count*/ 4, - /*slots*/ slots, + /*slots*/ slot_count, /*children*/ 0); } constexpr static layout_type InternalLayout() { @@ -591,8 +609,8 @@ class btree_node { /*slots*/ kNodeSlots, /*children*/ kNodeSlots + 1); } - constexpr static size_type LeafSize(const int slots = kNodeSlots) { - return LeafLayout(slots).AllocSize(); + constexpr static size_type LeafSize(const int slot_count = kNodeSlots) { + return LeafLayout(slot_count).AllocSize(); } constexpr static size_type InternalSize() { return InternalLayout().AllocSize(); @@ -1129,6 +1147,7 @@ class btree { using size_type = typename Params::size_type; using difference_type = typename Params::difference_type; using key_compare = typename Params::key_compare; + using original_key_compare = typename Params::original_key_compare; using value_compare = typename Params::value_compare; using allocator_type = typename Params::allocator_type; using reference = typename Params::reference; @@ -1338,7 +1357,9 @@ class btree { return compare_internal::compare_result_as_less_than(key_comp()(a, b)); } - value_compare value_comp() const { return value_compare(key_comp()); } + value_compare value_comp() const { + return value_compare(original_key_compare(key_comp())); + } // Verifies the structure of the btree. void verify() const; diff --git a/third_party/abseil-cpp/absl/container/internal/btree_container.h b/third_party/abseil-cpp/absl/container/internal/btree_container.h index 03be708e4f..a99668c713 100644 --- a/third_party/abseil-cpp/absl/container/internal/btree_container.h +++ b/third_party/abseil-cpp/absl/container/internal/btree_container.h @@ -20,6 +20,7 @@ #include <iterator> #include <utility> +#include "absl/base/attributes.h" #include "absl/base/internal/throw_delegate.h" #include "absl/container/internal/btree.h" // IWYU pragma: export #include "absl/container/internal/common.h" @@ -51,7 +52,7 @@ class btree_container { using value_type = typename Tree::value_type; using size_type = typename Tree::size_type; using difference_type = typename Tree::difference_type; - using key_compare = typename Tree::key_compare; + using key_compare = typename Tree::original_key_compare; using value_compare = typename Tree::value_compare; using allocator_type = typename Tree::allocator_type; using reference = typename Tree::reference; @@ -176,7 +177,7 @@ class btree_container { } // Utility routines. - void clear() { tree_.clear(); } + ABSL_ATTRIBUTE_REINITIALIZES void clear() { tree_.clear(); } void swap(btree_container &other) { tree_.swap(other.tree_); } void verify() const { tree_.verify(); } @@ -214,7 +215,7 @@ class btree_container { allocator_type get_allocator() const { return tree_.get_allocator(); } // The key comparator used by the btree. - key_compare key_comp() const { return tree_.key_comp(); } + key_compare key_comp() const { return key_compare(tree_.key_comp()); } value_compare value_comp() const { return tree_.value_comp(); } // Support absl::Hash. @@ -247,7 +248,7 @@ class btree_set_container : public btree_container<Tree> { using key_type = typename Tree::key_type; using value_type = typename Tree::value_type; using size_type = typename Tree::size_type; - using key_compare = typename Tree::key_compare; + using key_compare = typename Tree::original_key_compare; using allocator_type = typename Tree::allocator_type; using iterator = typename Tree::iterator; using const_iterator = typename Tree::const_iterator; @@ -398,7 +399,7 @@ class btree_map_container : public btree_set_container<Tree> { using key_type = typename Tree::key_type; using mapped_type = typename params_type::mapped_type; using value_type = typename Tree::value_type; - using key_compare = typename Tree::key_compare; + using key_compare = typename Tree::original_key_compare; using allocator_type = typename Tree::allocator_type; using iterator = typename Tree::iterator; using const_iterator = typename Tree::const_iterator; @@ -543,7 +544,7 @@ class btree_multiset_container : public btree_container<Tree> { using key_type = typename Tree::key_type; using value_type = typename Tree::value_type; using size_type = typename Tree::size_type; - using key_compare = typename Tree::key_compare; + using key_compare = typename Tree::original_key_compare; using allocator_type = typename Tree::allocator_type; using iterator = typename Tree::iterator; using const_iterator = typename Tree::const_iterator; diff --git a/third_party/abseil-cpp/absl/container/internal/hash_generator_testing.h b/third_party/abseil-cpp/absl/container/internal/hash_generator_testing.h index 6869fe45e8..f1f555a5c1 100644 --- a/third_party/abseil-cpp/absl/container/internal/hash_generator_testing.h +++ b/third_party/abseil-cpp/absl/container/internal/hash_generator_testing.h @@ -21,11 +21,13 @@ #include <stdint.h> #include <algorithm> +#include <cassert> #include <iosfwd> #include <random> #include <tuple> #include <type_traits> #include <utility> +#include <vector> #include "absl/container/internal/hash_policy_testing.h" #include "absl/memory/memory.h" @@ -153,6 +155,25 @@ using GeneratedType = decltype( typename Container::value_type, typename Container::key_type>::type>&>()()); +// Naive wrapper that performs a linear search of previous values. +// Beware this is O(SQR), which is reasonable for smaller kMaxValues. +template <class T, size_t kMaxValues = 64, class E = void> +struct UniqueGenerator { + Generator<T, E> gen; + std::vector<T> values; + + T operator()() { + assert(values.size() < kMaxValues); + for (;;) { + T value = gen(); + if (std::find(values.begin(), values.end(), value) == values.end()) { + values.push_back(value); + return value; + } + } + } +}; + } // namespace hash_internal } // namespace container_internal ABSL_NAMESPACE_END diff --git a/third_party/abseil-cpp/absl/container/internal/inlined_vector.h b/third_party/abseil-cpp/absl/container/internal/inlined_vector.h index b8aec45b79..49822af0b7 100644 --- a/third_party/abseil-cpp/absl/container/internal/inlined_vector.h +++ b/third_party/abseil-cpp/absl/container/internal/inlined_vector.h @@ -36,6 +36,7 @@ namespace inlined_vector_internal { // GCC does not deal very well with the below code #if !defined(__clang__) && defined(__GNUC__) #pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Warray-bounds" #pragma GCC diagnostic ignored "-Wmaybe-uninitialized" #endif @@ -955,7 +956,7 @@ auto Storage<T, N, A>::Swap(Storage* other_storage_ptr) -> void { swap(*GetAllocPtr(), *other_storage_ptr->GetAllocPtr()); } -// End ignore "maybe-uninitialized" +// End ignore "array-bounds" and "maybe-uninitialized" #if !defined(__clang__) && defined(__GNUC__) #pragma GCC diagnostic pop #endif diff --git a/third_party/abseil-cpp/absl/container/internal/layout.h b/third_party/abseil-cpp/absl/container/internal/layout.h index 2336783315..a59a243059 100644 --- a/third_party/abseil-cpp/absl/container/internal/layout.h +++ b/third_party/abseil-cpp/absl/container/internal/layout.h @@ -404,7 +404,7 @@ class LayoutImpl<std::tuple<Elements...>, absl::index_sequence<SizeSeq...>, constexpr size_t Offset() const { static_assert(N < NumOffsets, "Index out of bounds"); return adl_barrier::Align( - Offset<N - 1>() + SizeOf<ElementType<N - 1>>() * size_[N - 1], + Offset<N - 1>() + SizeOf<ElementType<N - 1>>::value * size_[N - 1], ElementAlignment<N>::value); } @@ -597,7 +597,7 @@ class LayoutImpl<std::tuple<Elements...>, absl::index_sequence<SizeSeq...>, constexpr size_t AllocSize() const { static_assert(NumTypes == NumSizes, "You must specify sizes of all fields"); return Offset<NumTypes - 1>() + - SizeOf<ElementType<NumTypes - 1>>() * size_[NumTypes - 1]; + SizeOf<ElementType<NumTypes - 1>>::value * size_[NumTypes - 1]; } // If built with --config=asan, poisons padding bytes (if any) in the @@ -621,7 +621,7 @@ class LayoutImpl<std::tuple<Elements...>, absl::index_sequence<SizeSeq...>, // The `if` is an optimization. It doesn't affect the observable behaviour. if (ElementAlignment<N - 1>::value % ElementAlignment<N>::value) { size_t start = - Offset<N - 1>() + SizeOf<ElementType<N - 1>>() * size_[N - 1]; + Offset<N - 1>() + SizeOf<ElementType<N - 1>>::value * size_[N - 1]; ASAN_POISON_MEMORY_REGION(p + start, Offset<N>() - start); } #endif @@ -645,7 +645,7 @@ class LayoutImpl<std::tuple<Elements...>, absl::index_sequence<SizeSeq...>, // produce "unsigned*" where another produces "unsigned int *". std::string DebugString() const { const auto offsets = Offsets(); - const size_t sizes[] = {SizeOf<ElementType<OffsetSeq>>()...}; + const size_t sizes[] = {SizeOf<ElementType<OffsetSeq>>::value...}; const std::string types[] = { adl_barrier::TypeName<ElementType<OffsetSeq>>()...}; std::string res = absl::StrCat("@0", types[0], "(", sizes[0], ")"); diff --git a/third_party/abseil-cpp/absl/container/internal/raw_hash_map.h b/third_party/abseil-cpp/absl/container/internal/raw_hash_map.h index 0a02757ddf..c7df2efc62 100644 --- a/third_party/abseil-cpp/absl/container/internal/raw_hash_map.h +++ b/third_party/abseil-cpp/absl/container/internal/raw_hash_map.h @@ -51,8 +51,9 @@ class raw_hash_map : public raw_hash_set<Policy, Hash, Eq, Alloc> { using key_arg = typename KeyArgImpl::template type<K, key_type>; static_assert(!std::is_reference<key_type>::value, ""); - // TODO(alkis): remove this assertion and verify that reference mapped_type is - // supported. + + // TODO(b/187807849): Evaluate whether to support reference mapped_type and + // remove this assertion if/when it is supported. static_assert(!std::is_reference<mapped_type>::value, ""); using iterator = typename raw_hash_map::raw_hash_set::iterator; diff --git a/third_party/abseil-cpp/absl/container/internal/raw_hash_set.h b/third_party/abseil-cpp/absl/container/internal/raw_hash_set.h index 80fc2cba3f..aa78265ca1 100644 --- a/third_party/abseil-cpp/absl/container/internal/raw_hash_set.h +++ b/third_party/abseil-cpp/absl/container/internal/raw_hash_set.h @@ -628,7 +628,9 @@ class raw_hash_set { static Layout MakeLayout(size_t capacity) { assert(IsValidCapacity(capacity)); - return Layout(capacity + Group::kWidth + 1, capacity); + // The extra control bytes are for 1 sentinel byte followed by + // `Group::kWidth - 1` bytes that are cloned from the beginning. + return Layout(capacity + Group::kWidth, capacity); } using AllocTraits = absl::allocator_traits<allocator_type>; @@ -792,7 +794,8 @@ class raw_hash_set { explicit raw_hash_set(size_t bucket_count, const hasher& hash = hasher(), const key_equal& eq = key_equal(), const allocator_type& alloc = allocator_type()) - : ctrl_(EmptyGroup()), settings_(0, hash, eq, alloc) { + : ctrl_(EmptyGroup()), + settings_(0, HashtablezInfoHandle(), hash, eq, alloc) { if (bucket_count) { capacity_ = NormalizeCapacity(bucket_count); initialize_slots(); @@ -903,7 +906,7 @@ class raw_hash_set { auto target = find_first_non_full(ctrl_, hash, capacity_); set_ctrl(target.offset, H2(hash)); emplace_at(target.offset, v); - infoz_.RecordInsert(hash, target.probe_length); + infoz().RecordInsert(hash, target.probe_length); } size_ = that.size(); growth_left() -= that.size(); @@ -917,28 +920,27 @@ class raw_hash_set { slots_(absl::exchange(that.slots_, nullptr)), size_(absl::exchange(that.size_, 0)), capacity_(absl::exchange(that.capacity_, 0)), - infoz_(absl::exchange(that.infoz_, HashtablezInfoHandle())), // Hash, equality and allocator are copied instead of moved because // `that` must be left valid. If Hash is std::function<Key>, moving it // would create a nullptr functor that cannot be called. - settings_(that.settings_) { - // growth_left was copied above, reset the one from `that`. - that.growth_left() = 0; - } + settings_(absl::exchange(that.growth_left(), 0), + absl::exchange(that.infoz(), HashtablezInfoHandle()), + that.hash_ref(), that.eq_ref(), that.alloc_ref()) {} raw_hash_set(raw_hash_set&& that, const allocator_type& a) : ctrl_(EmptyGroup()), slots_(nullptr), size_(0), capacity_(0), - settings_(0, that.hash_ref(), that.eq_ref(), a) { + settings_(0, HashtablezInfoHandle(), that.hash_ref(), that.eq_ref(), + a) { if (a == that.alloc_ref()) { std::swap(ctrl_, that.ctrl_); std::swap(slots_, that.slots_); std::swap(size_, that.size_); std::swap(capacity_, that.capacity_); std::swap(growth_left(), that.growth_left()); - std::swap(infoz_, that.infoz_); + std::swap(infoz(), that.infoz()); } else { reserve(that.size()); // Note: this will copy elements of dense_set and unordered_set instead of @@ -1009,7 +1011,7 @@ class raw_hash_set { reset_growth_left(); } assert(empty()); - infoz_.RecordStorageChanged(0, capacity_); + infoz().RecordStorageChanged(0, capacity_); } // This overload kicks in when the argument is an rvalue of insertable and @@ -1301,7 +1303,7 @@ class raw_hash_set { swap(growth_left(), that.growth_left()); swap(hash_ref(), that.hash_ref()); swap(eq_ref(), that.eq_ref()); - swap(infoz_, that.infoz_); + swap(infoz(), that.infoz()); SwapAlloc(alloc_ref(), that.alloc_ref(), typename AllocTraits::propagate_on_container_swap{}); } @@ -1310,7 +1312,7 @@ class raw_hash_set { if (n == 0 && capacity_ == 0) return; if (n == 0 && size_ == 0) { destroy_slots(); - infoz_.RecordStorageChanged(0, 0); + infoz().RecordStorageChanged(0, 0); return; } // bitor is a faster way of doing `max` here. We will round up to the next @@ -1323,8 +1325,8 @@ class raw_hash_set { } void reserve(size_t n) { - size_t m = GrowthToLowerboundCapacity(n); - if (m > capacity_) { + if (n > size() + growth_left()) { + size_t m = GrowthToLowerboundCapacity(n); resize(NormalizeCapacity(m)); } } @@ -1528,7 +1530,7 @@ class raw_hash_set { set_ctrl(index, was_never_full ? kEmpty : kDeleted); growth_left() += was_never_full; - infoz_.RecordErase(); + infoz().RecordErase(); } void initialize_slots() { @@ -1545,17 +1547,17 @@ class raw_hash_set { // bound more carefully. if (std::is_same<SlotAlloc, std::allocator<slot_type>>::value && slots_ == nullptr) { - infoz_ = Sample(); + infoz() = Sample(); } auto layout = MakeLayout(capacity_); char* mem = static_cast<char*>( Allocate<Layout::Alignment()>(&alloc_ref(), layout.AllocSize())); - ctrl_ = reinterpret_cast<ctrl_t*>(layout.template Pointer<0>(mem)); + ctrl_ = layout.template Pointer<0>(mem); slots_ = layout.template Pointer<1>(mem); reset_ctrl(); reset_growth_left(); - infoz_.RecordStorageChanged(size_, capacity_); + infoz().RecordStorageChanged(size_, capacity_); } void destroy_slots() { @@ -1603,7 +1605,7 @@ class raw_hash_set { Deallocate<Layout::Alignment()>(&alloc_ref(), old_ctrl, layout.AllocSize()); } - infoz_.RecordRehash(total_probe_length); + infoz().RecordRehash(total_probe_length); } void drop_deletes_without_resize() ABSL_ATTRIBUTE_NOINLINE { @@ -1669,7 +1671,7 @@ class raw_hash_set { } } reset_growth_left(); - infoz_.RecordRehash(total_probe_length); + infoz().RecordRehash(total_probe_length); } void rehash_and_grow_if_necessary() { @@ -1743,7 +1745,7 @@ class raw_hash_set { ++size_; growth_left() -= IsEmpty(ctrl_[target.offset]); set_ctrl(target.offset, H2(hash)); - infoz_.RecordInsert(hash, target.probe_length); + infoz().RecordInsert(hash, target.probe_length); return target.offset; } @@ -1782,8 +1784,8 @@ class raw_hash_set { growth_left() = CapacityToGrowth(capacity()) - size_; } - // Sets the control byte, and if `i < Group::kWidth`, set the cloned byte at - // the end too. + // Sets the control byte, and if `i < Group::kWidth - 1`, set the cloned byte + // at the end too. void set_ctrl(size_t i, ctrl_t h) { assert(i < capacity_); @@ -1794,32 +1796,35 @@ class raw_hash_set { } ctrl_[i] = h; - ctrl_[((i - Group::kWidth) & capacity_) + 1 + - ((Group::kWidth - 1) & capacity_)] = h; + constexpr size_t kClonedBytes = Group::kWidth - 1; + ctrl_[((i - kClonedBytes) & capacity_) + (kClonedBytes & capacity_)] = h; } size_t& growth_left() { return settings_.template get<0>(); } - hasher& hash_ref() { return settings_.template get<1>(); } - const hasher& hash_ref() const { return settings_.template get<1>(); } - key_equal& eq_ref() { return settings_.template get<2>(); } - const key_equal& eq_ref() const { return settings_.template get<2>(); } - allocator_type& alloc_ref() { return settings_.template get<3>(); } + HashtablezInfoHandle& infoz() { return settings_.template get<1>(); } + + hasher& hash_ref() { return settings_.template get<2>(); } + const hasher& hash_ref() const { return settings_.template get<2>(); } + key_equal& eq_ref() { return settings_.template get<3>(); } + const key_equal& eq_ref() const { return settings_.template get<3>(); } + allocator_type& alloc_ref() { return settings_.template get<4>(); } const allocator_type& alloc_ref() const { - return settings_.template get<3>(); + return settings_.template get<4>(); } // TODO(alkis): Investigate removing some of these fields: // - ctrl/slots can be derived from each other // - size can be moved into the slot array - ctrl_t* ctrl_ = EmptyGroup(); // [(capacity + 1) * ctrl_t] + ctrl_t* ctrl_ = EmptyGroup(); // [(capacity + Group::kWidth) * ctrl_t] slot_type* slots_ = nullptr; // [capacity * slot_type] size_t size_ = 0; // number of full slots size_t capacity_ = 0; // total number of slots - HashtablezInfoHandle infoz_; - absl::container_internal::CompressedTuple<size_t /* growth_left */, hasher, + absl::container_internal::CompressedTuple<size_t /* growth_left */, + HashtablezInfoHandle, hasher, key_equal, allocator_type> - settings_{0, hasher{}, key_equal{}, allocator_type{}}; + settings_{0, HashtablezInfoHandle{}, hasher{}, key_equal{}, + allocator_type{}}; }; // Erases all elements that satisfy the predicate `pred` from the container `c`. 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 index 81c4b47c04..af882ef49f 100644 --- 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 @@ -419,6 +419,13 @@ TEST(Table, EmptyFunctorOptimization) { size_t growth_left; void* infoz; }; + struct MockTableInfozDisabled { + 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; } }; @@ -426,17 +433,27 @@ TEST(Table, EmptyFunctorOptimization) { size_t dummy; }; - EXPECT_EQ( - sizeof(MockTable), - sizeof( - raw_hash_set<StringPolicy, StatelessHash, - std::equal_to<absl::string_view>, std::allocator<int>>)); + if (std::is_empty<HashtablezInfoHandle>::value) { + EXPECT_EQ(sizeof(MockTableInfozDisabled), + sizeof(raw_hash_set<StringPolicy, StatelessHash, + std::equal_to<absl::string_view>, + std::allocator<int>>)); + + EXPECT_EQ(sizeof(MockTableInfozDisabled) + sizeof(StatefulHash), + sizeof(raw_hash_set<StringPolicy, StatefulHash, + std::equal_to<absl::string_view>, + std::allocator<int>>)); + } else { + 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>>)); + EXPECT_EQ(sizeof(MockTable) + sizeof(StatefulHash), + sizeof(raw_hash_set<StringPolicy, StatefulHash, + std::equal_to<absl::string_view>, + std::allocator<int>>)); + } } TEST(Table, Empty) { @@ -524,6 +541,37 @@ TEST(Table, InsertCollisionAndFindAfterDelete) { EXPECT_TRUE(t.empty()); } +TEST(Table, InsertWithinCapacity) { + IntTable t; + t.reserve(10); + const size_t original_capacity = t.capacity(); + const auto addr = [&](int i) { + return reinterpret_cast<uintptr_t>(&*t.find(i)); + }; + // Inserting an element does not change capacity. + t.insert(0); + EXPECT_THAT(t.capacity(), original_capacity); + const uintptr_t original_addr_0 = addr(0); + // Inserting another element does not rehash. + t.insert(1); + EXPECT_THAT(t.capacity(), original_capacity); + EXPECT_THAT(addr(0), original_addr_0); + // Inserting lots of duplicate elements does not rehash. + for (int i = 0; i < 100; ++i) { + t.insert(i % 10); + } + EXPECT_THAT(t.capacity(), original_capacity); + EXPECT_THAT(addr(0), original_addr_0); + // Inserting a range of duplicate elements does not rehash. + std::vector<int> dup_range; + for (int i = 0; i < 100; ++i) { + dup_range.push_back(i % 10); + } + t.insert(dup_range.begin(), dup_range.end()); + EXPECT_THAT(t.capacity(), original_capacity); + EXPECT_THAT(addr(0), original_addr_0); +} + TEST(Table, LazyEmplace) { StringTable t; bool called = false; diff --git a/third_party/abseil-cpp/absl/container/internal/unordered_map_constructor_test.h b/third_party/abseil-cpp/absl/container/internal/unordered_map_constructor_test.h index 3f90ad7ca8..c1d20f3c52 100644 --- a/third_party/abseil-cpp/absl/container/internal/unordered_map_constructor_test.h +++ b/third_party/abseil-cpp/absl/container/internal/unordered_map_constructor_test.h @@ -179,7 +179,7 @@ TYPED_TEST_P(ConstructorTest, InputIteratorBucketHashEqualAlloc) { A alloc(0); std::vector<T> values; std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + hash_internal::UniqueGenerator<T>()); TypeParam m(values.begin(), values.end(), 123, hasher, equal, alloc); EXPECT_EQ(m.hash_function(), hasher); EXPECT_EQ(m.key_eq(), equal); @@ -198,7 +198,7 @@ void InputIteratorBucketAllocTest(std::true_type) { A alloc(0); std::vector<T> values; std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + hash_internal::UniqueGenerator<T>()); TypeParam m(values.begin(), values.end(), 123, alloc); EXPECT_EQ(m.get_allocator(), alloc); EXPECT_THAT(items(m), ::testing::UnorderedElementsAreArray(values)); @@ -221,7 +221,7 @@ void InputIteratorBucketHashAllocTest(std::true_type) { A alloc(0); std::vector<T> values; std::generate_n(std::back_inserter(values), 10, - hash_internal::Generator<T>()); + hash_internal::UniqueGenerator<T>()); TypeParam m(values.begin(), values.end(), 123, hasher, alloc); EXPECT_EQ(m.hash_function(), hasher); EXPECT_EQ(m.get_allocator(), alloc); @@ -241,8 +241,9 @@ TYPED_TEST_P(ConstructorTest, CopyConstructor) { H hasher; E equal; A alloc(0); + hash_internal::UniqueGenerator<T> gen; TypeParam m(123, hasher, equal, alloc); - for (size_t i = 0; i != 10; ++i) m.insert(hash_internal::Generator<T>()()); + for (size_t i = 0; i != 10; ++i) m.insert(gen()); TypeParam n(m); EXPECT_EQ(m.hash_function(), n.hash_function()); EXPECT_EQ(m.key_eq(), n.key_eq()); @@ -262,8 +263,9 @@ void CopyConstructorAllocTest(std::true_type) { H hasher; E equal; A alloc(0); + hash_internal::UniqueGenerator<T> gen; TypeParam m(123, hasher, equal, alloc); - for (size_t i = 0; i != 10; ++i) m.insert(hash_internal::Generator<T>()()); + for (size_t i = 0; i != 10; ++i) m.insert(gen()); TypeParam n(m, A(11)); EXPECT_EQ(m.hash_function(), n.hash_function()); EXPECT_EQ(m.key_eq(), n.key_eq()); @@ -285,8 +287,9 @@ TYPED_TEST_P(ConstructorTest, MoveConstructor) { H hasher; E equal; A alloc(0); + hash_internal::UniqueGenerator<T> gen; TypeParam m(123, hasher, equal, alloc); - for (size_t i = 0; i != 10; ++i) m.insert(hash_internal::Generator<T>()()); + for (size_t i = 0; i != 10; ++i) m.insert(gen()); TypeParam t(m); TypeParam n(std::move(t)); EXPECT_EQ(m.hash_function(), n.hash_function()); @@ -307,8 +310,9 @@ void MoveConstructorAllocTest(std::true_type) { H hasher; E equal; A alloc(0); + hash_internal::UniqueGenerator<T> gen; TypeParam m(123, hasher, equal, alloc); - for (size_t i = 0; i != 10; ++i) m.insert(hash_internal::Generator<T>()()); + for (size_t i = 0; i != 10; ++i) m.insert(gen()); TypeParam t(m); TypeParam n(std::move(t), A(1)); EXPECT_EQ(m.hash_function(), n.hash_function()); @@ -325,7 +329,7 @@ TYPED_TEST_P(ConstructorTest, MoveConstructorAlloc) { TYPED_TEST_P(ConstructorTest, InitializerListBucketHashEqualAlloc) { using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::Generator<T> gen; + hash_internal::UniqueGenerator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; using H = typename TypeParam::hasher; using E = typename TypeParam::key_equal; @@ -348,7 +352,7 @@ template <typename TypeParam> void InitializerListBucketAllocTest(std::true_type) { using T = hash_internal::GeneratedType<TypeParam>; using A = typename TypeParam::allocator_type; - hash_internal::Generator<T> gen; + hash_internal::UniqueGenerator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; A alloc(0); TypeParam m(values, 123, alloc); @@ -371,7 +375,7 @@ void InitializerListBucketHashAllocTest(std::true_type) { using A = typename TypeParam::allocator_type; H hasher; A alloc(0); - hash_internal::Generator<T> gen; + hash_internal::UniqueGenerator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; TypeParam m(values, 123, hasher, alloc); EXPECT_EQ(m.hash_function(), hasher); @@ -392,7 +396,7 @@ TYPED_TEST_P(ConstructorTest, Assignment) { H hasher; E equal; A alloc(0); - hash_internal::Generator<T> gen; + hash_internal::UniqueGenerator<T> gen; TypeParam m({gen(), gen(), gen()}, 123, hasher, equal, alloc); TypeParam n; n = m; @@ -412,7 +416,7 @@ TYPED_TEST_P(ConstructorTest, MoveAssignment) { H hasher; E equal; A alloc(0); - hash_internal::Generator<T> gen; + hash_internal::UniqueGenerator<T> gen; TypeParam m({gen(), gen(), gen()}, 123, hasher, equal, alloc); TypeParam t(m); TypeParam n; @@ -424,7 +428,7 @@ TYPED_TEST_P(ConstructorTest, MoveAssignment) { TYPED_TEST_P(ConstructorTest, AssignmentFromInitializerList) { using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::Generator<T> gen; + hash_internal::UniqueGenerator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; TypeParam m; m = values; @@ -433,7 +437,7 @@ TYPED_TEST_P(ConstructorTest, AssignmentFromInitializerList) { TYPED_TEST_P(ConstructorTest, AssignmentOverwritesExisting) { using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::Generator<T> gen; + hash_internal::UniqueGenerator<T> gen; TypeParam m({gen(), gen(), gen()}); TypeParam n({gen()}); n = m; @@ -442,7 +446,7 @@ TYPED_TEST_P(ConstructorTest, AssignmentOverwritesExisting) { TYPED_TEST_P(ConstructorTest, MoveAssignmentOverwritesExisting) { using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::Generator<T> gen; + hash_internal::UniqueGenerator<T> gen; TypeParam m({gen(), gen(), gen()}); TypeParam t(m); TypeParam n({gen()}); @@ -452,7 +456,7 @@ TYPED_TEST_P(ConstructorTest, MoveAssignmentOverwritesExisting) { TYPED_TEST_P(ConstructorTest, AssignmentFromInitializerListOverwritesExisting) { using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::Generator<T> gen; + hash_internal::UniqueGenerator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; TypeParam m; m = values; @@ -461,7 +465,7 @@ TYPED_TEST_P(ConstructorTest, AssignmentFromInitializerListOverwritesExisting) { TYPED_TEST_P(ConstructorTest, AssignmentOnSelf) { using T = hash_internal::GeneratedType<TypeParam>; - hash_internal::Generator<T> gen; + hash_internal::UniqueGenerator<T> gen; std::initializer_list<T> values = {gen(), gen(), gen(), gen(), gen()}; TypeParam m(values); m = *&m; // Avoid -Wself-assign diff --git a/third_party/abseil-cpp/absl/container/internal/unordered_map_modifiers_test.h b/third_party/abseil-cpp/absl/container/internal/unordered_map_modifiers_test.h index 8c9ca779a4..d3543936f7 100644 --- a/third_party/abseil-cpp/absl/container/internal/unordered_map_modifiers_test.h +++ b/third_party/abseil-cpp/absl/container/internal/unordered_map_modifiers_test.h @@ -81,6 +81,38 @@ TYPED_TEST_P(ModifiersTest, InsertRange) { ASSERT_THAT(items(m), ::testing::UnorderedElementsAreArray(values)); } +TYPED_TEST_P(ModifiersTest, InsertWithinCapacity) { + using T = hash_internal::GeneratedType<TypeParam>; + using V = typename TypeParam::mapped_type; + T val = hash_internal::Generator<T>()(); + TypeParam m; + m.reserve(10); + const size_t original_capacity = m.bucket_count(); + m.insert(val); + EXPECT_EQ(m.bucket_count(), original_capacity); + T val2 = {val.first, hash_internal::Generator<V>()()}; + m.insert(val2); + EXPECT_EQ(m.bucket_count(), original_capacity); +} + +TYPED_TEST_P(ModifiersTest, InsertRangeWithinCapacity) { +#if !defined(__GLIBCXX__) + using T = hash_internal::GeneratedType<TypeParam>; + std::vector<T> base_values; + std::generate_n(std::back_inserter(base_values), 10, + hash_internal::Generator<T>()); + std::vector<T> values; + while (values.size() != 100) { + std::copy_n(base_values.begin(), 10, std::back_inserter(values)); + } + TypeParam m; + m.reserve(10); + const size_t original_capacity = m.bucket_count(); + m.insert(values.begin(), values.end()); + EXPECT_EQ(m.bucket_count(), original_capacity); +#endif +} + TYPED_TEST_P(ModifiersTest, InsertOrAssign) { #ifdef UNORDERED_MAP_CXX17 using std::get; @@ -266,9 +298,10 @@ TYPED_TEST_P(ModifiersTest, Swap) { // TODO(alkis): Write tests for merge. REGISTER_TYPED_TEST_CASE_P(ModifiersTest, Clear, Insert, InsertHint, - InsertRange, InsertOrAssign, InsertOrAssignHint, - Emplace, EmplaceHint, TryEmplace, TryEmplaceHint, - Erase, EraseRange, EraseKey, Swap); + InsertRange, InsertWithinCapacity, + InsertRangeWithinCapacity, InsertOrAssign, + InsertOrAssignHint, Emplace, EmplaceHint, TryEmplace, + TryEmplaceHint, Erase, EraseRange, EraseKey, Swap); template <typename Type> struct is_unique_ptr : std::false_type {}; diff --git a/third_party/abseil-cpp/absl/container/internal/unordered_set_modifiers_test.h b/third_party/abseil-cpp/absl/container/internal/unordered_set_modifiers_test.h index 26be58d99f..6e473e45da 100644 --- a/third_party/abseil-cpp/absl/container/internal/unordered_set_modifiers_test.h +++ b/third_party/abseil-cpp/absl/container/internal/unordered_set_modifiers_test.h @@ -74,6 +74,36 @@ TYPED_TEST_P(ModifiersTest, InsertRange) { ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values)); } +TYPED_TEST_P(ModifiersTest, InsertWithinCapacity) { + using T = hash_internal::GeneratedType<TypeParam>; + T val = hash_internal::Generator<T>()(); + TypeParam m; + m.reserve(10); + const size_t original_capacity = m.bucket_count(); + m.insert(val); + EXPECT_EQ(m.bucket_count(), original_capacity); + m.insert(val); + EXPECT_EQ(m.bucket_count(), original_capacity); +} + +TYPED_TEST_P(ModifiersTest, InsertRangeWithinCapacity) { +#if !defined(__GLIBCXX__) + using T = hash_internal::GeneratedType<TypeParam>; + std::vector<T> base_values; + std::generate_n(std::back_inserter(base_values), 10, + hash_internal::Generator<T>()); + std::vector<T> values; + while (values.size() != 100) { + values.insert(values.end(), base_values.begin(), base_values.end()); + } + TypeParam m; + m.reserve(10); + const size_t original_capacity = m.bucket_count(); + m.insert(values.begin(), values.end()); + EXPECT_EQ(m.bucket_count(), original_capacity); +#endif +} + TYPED_TEST_P(ModifiersTest, Emplace) { using T = hash_internal::GeneratedType<TypeParam>; T val = hash_internal::Generator<T>()(); @@ -180,8 +210,9 @@ TYPED_TEST_P(ModifiersTest, Swap) { // TODO(alkis): Write tests for merge. REGISTER_TYPED_TEST_CASE_P(ModifiersTest, Clear, Insert, InsertHint, - InsertRange, Emplace, EmplaceHint, Erase, EraseRange, - EraseKey, Swap); + InsertRange, InsertWithinCapacity, + InsertRangeWithinCapacity, Emplace, EmplaceHint, + Erase, EraseRange, EraseKey, Swap); } // namespace container_internal ABSL_NAMESPACE_END |