diff options
Diffstat (limited to 'third_party/abseil_cpp/absl/container/btree_test.cc')
| -rw-r--r-- | third_party/abseil_cpp/absl/container/btree_test.cc | 461 |
1 files changed, 439 insertions, 22 deletions
diff --git a/third_party/abseil_cpp/absl/container/btree_test.cc b/third_party/abseil_cpp/absl/container/btree_test.cc index bbdb5f42a621..9b1b6436c7ca 100644 --- a/third_party/abseil_cpp/absl/container/btree_test.cc +++ b/third_party/abseil_cpp/absl/container/btree_test.cc @@ -15,6 +15,7 @@ #include "absl/container/btree_test.h" #include <cstdint> +#include <limits> #include <map> #include <memory> #include <stdexcept> @@ -52,7 +53,9 @@ using ::absl::test_internal::MovableOnlyInstance; using ::testing::ElementsAre; using ::testing::ElementsAreArray; using ::testing::IsEmpty; +using ::testing::IsNull; using ::testing::Pair; +using ::testing::SizeIs; template <typename T, typename U> void CheckPairEquals(const T &x, const U &y) { @@ -1180,6 +1183,103 @@ TEST(Btree, RangeCtorSanity) { EXPECT_EQ(1, tmap.size()); } +} // namespace + +class BtreeNodePeer { + public: + // Yields the size of a leaf node with a specific number of values. + template <typename ValueType> + constexpr static size_t GetTargetNodeSize(size_t target_values_per_node) { + return btree_node< + set_params<ValueType, std::less<ValueType>, std::allocator<ValueType>, + /*TargetNodeSize=*/256, // This parameter isn't used here. + /*Multi=*/false>>::SizeWithNValues(target_values_per_node); + } + + // Yields the number of values in a (non-root) leaf node for this btree. + template <typename Btree> + constexpr static size_t GetNumValuesPerNode() { + return btree_node<typename Btree::params_type>::kNodeValues; + } + + template <typename Btree> + constexpr static size_t GetMaxFieldType() { + return std::numeric_limits< + typename btree_node<typename Btree::params_type>::field_type>::max(); + } + + template <typename Btree> + constexpr static bool UsesLinearNodeSearch() { + return btree_node<typename Btree::params_type>::use_linear_search::value; + } +}; + +namespace { + +class BtreeMapTest : public ::testing::Test { + public: + struct Key {}; + struct Cmp { + template <typename T> + bool operator()(T, T) const { + return false; + } + }; + + struct KeyLin { + using absl_btree_prefer_linear_node_search = std::true_type; + }; + struct CmpLin : Cmp { + using absl_btree_prefer_linear_node_search = std::true_type; + }; + + struct KeyBin { + using absl_btree_prefer_linear_node_search = std::false_type; + }; + struct CmpBin : Cmp { + using absl_btree_prefer_linear_node_search = std::false_type; + }; + + template <typename K, typename C> + static bool IsLinear() { + return BtreeNodePeer::UsesLinearNodeSearch<absl::btree_map<K, int, C>>(); + } +}; + +TEST_F(BtreeMapTest, TestLinearSearchPreferredForKeyLinearViaAlias) { + // Test requesting linear search by directly exporting an alias. + EXPECT_FALSE((IsLinear<Key, Cmp>())); + EXPECT_TRUE((IsLinear<KeyLin, Cmp>())); + EXPECT_TRUE((IsLinear<Key, CmpLin>())); + EXPECT_TRUE((IsLinear<KeyLin, CmpLin>())); +} + +TEST_F(BtreeMapTest, LinearChoiceTree) { + // Cmp has precedence, and is forcing binary + EXPECT_FALSE((IsLinear<Key, CmpBin>())); + EXPECT_FALSE((IsLinear<KeyLin, CmpBin>())); + EXPECT_FALSE((IsLinear<KeyBin, CmpBin>())); + EXPECT_FALSE((IsLinear<int, CmpBin>())); + EXPECT_FALSE((IsLinear<std::string, CmpBin>())); + // Cmp has precedence, and is forcing linear + EXPECT_TRUE((IsLinear<Key, CmpLin>())); + EXPECT_TRUE((IsLinear<KeyLin, CmpLin>())); + EXPECT_TRUE((IsLinear<KeyBin, CmpLin>())); + EXPECT_TRUE((IsLinear<int, CmpLin>())); + EXPECT_TRUE((IsLinear<std::string, CmpLin>())); + // Cmp has no preference, Key determines linear vs binary. + EXPECT_FALSE((IsLinear<Key, Cmp>())); + EXPECT_TRUE((IsLinear<KeyLin, Cmp>())); + EXPECT_FALSE((IsLinear<KeyBin, Cmp>())); + // arithmetic key w/ std::less or std::greater: linear + EXPECT_TRUE((IsLinear<int, std::less<int>>())); + EXPECT_TRUE((IsLinear<double, std::greater<double>>())); + // arithmetic key w/ custom compare: binary + EXPECT_FALSE((IsLinear<int, Cmp>())); + // non-arithmetic key: binary + EXPECT_FALSE((IsLinear<std::string, std::less<std::string>>())); +} + TEST(Btree, BtreeMapCanHoldMoveOnlyTypes) { absl::btree_map<std::string, std::unique_ptr<std::string>> m; @@ -1325,28 +1425,6 @@ TEST(Btree, RValueInsert) { EXPECT_EQ(tracker.swaps(), 0); } -} // namespace - -class BtreeNodePeer { - public: - // Yields the size of a leaf node with a specific number of values. - template <typename ValueType> - constexpr static size_t GetTargetNodeSize(size_t target_values_per_node) { - return btree_node< - set_params<ValueType, std::less<ValueType>, std::allocator<ValueType>, - /*TargetNodeSize=*/256, // This parameter isn't used here. - /*Multi=*/false>>::SizeWithNValues(target_values_per_node); - } - - // Yields the number of values in a (non-root) leaf node for this set. - template <typename Set> - constexpr static size_t GetNumValuesPerNode() { - return btree_node<typename Set::params_type>::kNodeValues; - } -}; - -namespace { - // A btree set with a specific number of values per node. template <typename Key, int TargetValuesPerNode, typename Cmp = std::less<Key>> class SizedBtreeSet @@ -2101,6 +2179,31 @@ TEST(Btree, MergeIntoMultiMapsWithDifferentComparators) { Pair(4, 1), Pair(4, 4), Pair(5, 5))); } +TEST(Btree, MergeIntoSetMovableOnly) { + absl::btree_set<MovableOnlyInstance> src; + src.insert(MovableOnlyInstance(1)); + absl::btree_multiset<MovableOnlyInstance> dst1; + dst1.insert(MovableOnlyInstance(2)); + absl::btree_set<MovableOnlyInstance> dst2; + + // Test merge into multiset. + dst1.merge(src); + + EXPECT_TRUE(src.empty()); + // ElementsAre/ElementsAreArray don't work with move-only types. + ASSERT_THAT(dst1, SizeIs(2)); + EXPECT_EQ(*dst1.begin(), MovableOnlyInstance(1)); + EXPECT_EQ(*std::next(dst1.begin()), MovableOnlyInstance(2)); + + // Test merge into set. + dst2.merge(dst1); + + EXPECT_TRUE(dst1.empty()); + ASSERT_THAT(dst2, SizeIs(2)); + EXPECT_EQ(*dst2.begin(), MovableOnlyInstance(1)); + EXPECT_EQ(*std::next(dst2.begin()), MovableOnlyInstance(2)); +} + struct KeyCompareToWeakOrdering { template <typename T> absl::weak_ordering operator()(const T &a, const T &b) const { @@ -2404,6 +2507,320 @@ TEST(Btree, BitfieldArgument) { m[n]; } +TEST(Btree, SetRangeConstructorAndInsertSupportExplicitConversionComparable) { + const absl::string_view names[] = {"n1", "n2"}; + + absl::btree_set<std::string> name_set1{std::begin(names), std::end(names)}; + EXPECT_THAT(name_set1, ElementsAreArray(names)); + + absl::btree_set<std::string> name_set2; + name_set2.insert(std::begin(names), std::end(names)); + EXPECT_THAT(name_set2, ElementsAreArray(names)); +} + +// A type that is explicitly convertible from int and counts constructor calls. +struct ConstructorCounted { + explicit ConstructorCounted(int i) : i(i) { ++constructor_calls; } + bool operator==(int other) const { return i == other; } + + int i; + static int constructor_calls; +}; +int ConstructorCounted::constructor_calls = 0; + +struct ConstructorCountedCompare { + bool operator()(int a, const ConstructorCounted &b) const { return a < b.i; } + bool operator()(const ConstructorCounted &a, int b) const { return a.i < b; } + bool operator()(const ConstructorCounted &a, + const ConstructorCounted &b) const { + return a.i < b.i; + } + using is_transparent = void; +}; + +TEST(Btree, + SetRangeConstructorAndInsertExplicitConvComparableLimitConstruction) { + const int i[] = {0, 1, 1}; + ConstructorCounted::constructor_calls = 0; + + absl::btree_set<ConstructorCounted, ConstructorCountedCompare> set{ + std::begin(i), std::end(i)}; + EXPECT_THAT(set, ElementsAre(0, 1)); + EXPECT_EQ(ConstructorCounted::constructor_calls, 2); + + set.insert(std::begin(i), std::end(i)); + EXPECT_THAT(set, ElementsAre(0, 1)); + EXPECT_EQ(ConstructorCounted::constructor_calls, 2); +} + +TEST(Btree, + SetRangeConstructorAndInsertSupportExplicitConversionNonComparable) { + const int i[] = {0, 1}; + + absl::btree_set<std::vector<void *>> s1{std::begin(i), std::end(i)}; + EXPECT_THAT(s1, ElementsAre(IsEmpty(), ElementsAre(IsNull()))); + + absl::btree_set<std::vector<void *>> s2; + s2.insert(std::begin(i), std::end(i)); + EXPECT_THAT(s2, ElementsAre(IsEmpty(), ElementsAre(IsNull()))); +} + +// libstdc++ included with GCC 4.9 has a bug in the std::pair constructors that +// prevents explicit conversions between pair types. +// We only run this test for the libstdc++ from GCC 7 or newer because we can't +// reliably check the libstdc++ version prior to that release. +#if !defined(__GLIBCXX__) || \ + (defined(_GLIBCXX_RELEASE) && _GLIBCXX_RELEASE >= 7) +TEST(Btree, MapRangeConstructorAndInsertSupportExplicitConversionComparable) { + const std::pair<absl::string_view, int> names[] = {{"n1", 1}, {"n2", 2}}; + + absl::btree_map<std::string, int> name_map1{std::begin(names), + std::end(names)}; + EXPECT_THAT(name_map1, ElementsAre(Pair("n1", 1), Pair("n2", 2))); + + absl::btree_map<std::string, int> name_map2; + name_map2.insert(std::begin(names), std::end(names)); + EXPECT_THAT(name_map2, ElementsAre(Pair("n1", 1), Pair("n2", 2))); +} + +TEST(Btree, + MapRangeConstructorAndInsertExplicitConvComparableLimitConstruction) { + const std::pair<int, int> i[] = {{0, 1}, {1, 2}, {1, 3}}; + ConstructorCounted::constructor_calls = 0; + + absl::btree_map<ConstructorCounted, int, ConstructorCountedCompare> map{ + std::begin(i), std::end(i)}; + EXPECT_THAT(map, ElementsAre(Pair(0, 1), Pair(1, 2))); + EXPECT_EQ(ConstructorCounted::constructor_calls, 2); + + map.insert(std::begin(i), std::end(i)); + EXPECT_THAT(map, ElementsAre(Pair(0, 1), Pair(1, 2))); + EXPECT_EQ(ConstructorCounted::constructor_calls, 2); +} + +TEST(Btree, + MapRangeConstructorAndInsertSupportExplicitConversionNonComparable) { + const std::pair<int, int> i[] = {{0, 1}, {1, 2}}; + + absl::btree_map<std::vector<void *>, int> m1{std::begin(i), std::end(i)}; + EXPECT_THAT(m1, + ElementsAre(Pair(IsEmpty(), 1), Pair(ElementsAre(IsNull()), 2))); + + absl::btree_map<std::vector<void *>, int> m2; + m2.insert(std::begin(i), std::end(i)); + EXPECT_THAT(m2, + ElementsAre(Pair(IsEmpty(), 1), Pair(ElementsAre(IsNull()), 2))); +} + +TEST(Btree, HeterogeneousTryEmplace) { + absl::btree_map<std::string, int> m; + std::string s = "key"; + absl::string_view sv = s; + m.try_emplace(sv, 1); + EXPECT_EQ(m[s], 1); + + m.try_emplace(m.end(), sv, 2); + EXPECT_EQ(m[s], 1); +} + +TEST(Btree, HeterogeneousOperatorMapped) { + absl::btree_map<std::string, int> m; + std::string s = "key"; + absl::string_view sv = s; + m[sv] = 1; + EXPECT_EQ(m[s], 1); + + m[sv] = 2; + EXPECT_EQ(m[s], 2); +} + +TEST(Btree, HeterogeneousInsertOrAssign) { + absl::btree_map<std::string, int> m; + std::string s = "key"; + absl::string_view sv = s; + m.insert_or_assign(sv, 1); + EXPECT_EQ(m[s], 1); + + m.insert_or_assign(m.end(), sv, 2); + EXPECT_EQ(m[s], 2); +} +#endif + +// This test requires std::launder for mutable key access in node handles. +#if defined(__cpp_lib_launder) && __cpp_lib_launder >= 201606 +TEST(Btree, NodeHandleMutableKeyAccess) { + { + absl::btree_map<std::string, std::string> map; + + map["key1"] = "mapped"; + + auto nh = map.extract(map.begin()); + nh.key().resize(3); + map.insert(std::move(nh)); + + EXPECT_THAT(map, ElementsAre(Pair("key", "mapped"))); + } + // Also for multimap. + { + absl::btree_multimap<std::string, std::string> map; + + map.emplace("key1", "mapped"); + + auto nh = map.extract(map.begin()); + nh.key().resize(3); + map.insert(std::move(nh)); + + EXPECT_THAT(map, ElementsAre(Pair("key", "mapped"))); + } +} +#endif + +struct MultiKey { + int i1; + int i2; +}; + +bool operator==(const MultiKey a, const MultiKey b) { + return a.i1 == b.i1 && a.i2 == b.i2; +} + +// A heterogeneous comparator that has different equivalence classes for +// different lookup types. +struct MultiKeyComp { + using is_transparent = void; + bool operator()(const MultiKey a, const MultiKey b) const { + if (a.i1 != b.i1) return a.i1 < b.i1; + return a.i2 < b.i2; + } + bool operator()(const int a, const MultiKey b) const { return a < b.i1; } + bool operator()(const MultiKey a, const int b) const { return a.i1 < b; } +}; + +TEST(Btree, MultiKeyEqualRange) { + absl::btree_set<MultiKey, MultiKeyComp> set; + + for (int i = 0; i < 100; ++i) { + for (int j = 0; j < 100; ++j) { + set.insert({i, j}); + } + } + + for (int i = 0; i < 100; ++i) { + auto equal_range = set.equal_range(i); + EXPECT_EQ(equal_range.first->i1, i); + EXPECT_EQ(equal_range.first->i2, 0); + EXPECT_EQ(std::distance(equal_range.first, equal_range.second), 100) << i; + } +} + +TEST(Btree, MultiKeyErase) { + absl::btree_set<MultiKey, MultiKeyComp> set = { + {1, 1}, {2, 1}, {2, 2}, {3, 1}}; + EXPECT_EQ(set.erase(2), 2); + EXPECT_THAT(set, ElementsAre(MultiKey{1, 1}, MultiKey{3, 1})); +} + +TEST(Btree, MultiKeyCount) { + const absl::btree_set<MultiKey, MultiKeyComp> set = { + {1, 1}, {2, 1}, {2, 2}, {3, 1}}; + EXPECT_EQ(set.count(2), 2); +} + +TEST(Btree, AllocConstructor) { + using Alloc = CountingAllocator<int>; + using Set = absl::btree_set<int, std::less<int>, Alloc>; + int64_t bytes_used = 0; + Alloc alloc(&bytes_used); + Set set(alloc); + + set.insert({1, 2, 3}); + + EXPECT_THAT(set, ElementsAre(1, 2, 3)); + EXPECT_GT(bytes_used, set.size() * sizeof(int)); +} + +TEST(Btree, AllocInitializerListConstructor) { + using Alloc = CountingAllocator<int>; + using Set = absl::btree_set<int, std::less<int>, Alloc>; + int64_t bytes_used = 0; + Alloc alloc(&bytes_used); + Set set({1, 2, 3}, alloc); + + EXPECT_THAT(set, ElementsAre(1, 2, 3)); + EXPECT_GT(bytes_used, set.size() * sizeof(int)); +} + +TEST(Btree, AllocRangeConstructor) { + using Alloc = CountingAllocator<int>; + using Set = absl::btree_set<int, std::less<int>, Alloc>; + int64_t bytes_used = 0; + Alloc alloc(&bytes_used); + std::vector<int> v = {1, 2, 3}; + Set set(v.begin(), v.end(), alloc); + + EXPECT_THAT(set, ElementsAre(1, 2, 3)); + EXPECT_GT(bytes_used, set.size() * sizeof(int)); +} + +TEST(Btree, AllocCopyConstructor) { + using Alloc = CountingAllocator<int>; + using Set = absl::btree_set<int, std::less<int>, Alloc>; + int64_t bytes_used1 = 0; + Alloc alloc1(&bytes_used1); + Set set1(alloc1); + + set1.insert({1, 2, 3}); + + int64_t bytes_used2 = 0; + Alloc alloc2(&bytes_used2); + Set set2(set1, alloc2); + + EXPECT_THAT(set1, ElementsAre(1, 2, 3)); + EXPECT_THAT(set2, ElementsAre(1, 2, 3)); + EXPECT_GT(bytes_used1, set1.size() * sizeof(int)); + EXPECT_EQ(bytes_used1, bytes_used2); +} + +TEST(Btree, AllocMoveConstructor_SameAlloc) { + using Alloc = CountingAllocator<int>; + using Set = absl::btree_set<int, std::less<int>, Alloc>; + int64_t bytes_used = 0; + Alloc alloc(&bytes_used); + Set set1(alloc); + + set1.insert({1, 2, 3}); + + const int64_t original_bytes_used = bytes_used; + EXPECT_GT(original_bytes_used, set1.size() * sizeof(int)); + + Set set2(std::move(set1), alloc); + + EXPECT_THAT(set2, ElementsAre(1, 2, 3)); + EXPECT_EQ(bytes_used, original_bytes_used); +} + +TEST(Btree, AllocMoveConstructor_DifferentAlloc) { + using Alloc = CountingAllocator<int>; + using Set = absl::btree_set<int, std::less<int>, Alloc>; + int64_t bytes_used1 = 0; + Alloc alloc1(&bytes_used1); + Set set1(alloc1); + + set1.insert({1, 2, 3}); + + const int64_t original_bytes_used = bytes_used1; + EXPECT_GT(original_bytes_used, set1.size() * sizeof(int)); + + int64_t bytes_used2 = 0; + Alloc alloc2(&bytes_used2); + Set set2(std::move(set1), alloc2); + + EXPECT_THAT(set2, ElementsAre(1, 2, 3)); + // We didn't free these bytes allocated by `set1` yet. + EXPECT_EQ(bytes_used1, original_bytes_used); + EXPECT_EQ(bytes_used2, original_bytes_used); +} + } // namespace } // namespace container_internal ABSL_NAMESPACE_END |