aboutsummaryrefslogtreecommitdiff
path: root/absl/container/btree_test.cc
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container/btree_test.cc')
-rw-r--r--absl/container/btree_test.cc368
1 files changed, 326 insertions, 42 deletions
diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index 9386a6b1..72f446b2 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -18,6 +18,7 @@
#include <array>
#include <cstdint>
#include <functional>
+#include <iostream>
#include <iterator>
#include <limits>
#include <map>
@@ -31,6 +32,7 @@
#include "gmock/gmock.h"
#include "gtest/gtest.h"
+#include "absl/algorithm/container.h"
#include "absl/base/internal/raw_logging.h"
#include "absl/base/macros.h"
#include "absl/container/btree_map.h"
@@ -40,10 +42,12 @@
#include "absl/flags/flag.h"
#include "absl/hash/hash_testing.h"
#include "absl/memory/memory.h"
+#include "absl/random/random.h"
#include "absl/strings/str_cat.h"
#include "absl/strings/str_split.h"
#include "absl/strings/string_view.h"
#include "absl/types/compare.h"
+#include "absl/types/optional.h"
ABSL_FLAG(int, test_values, 10000, "The number of values to use for tests");
@@ -72,6 +76,16 @@ void CheckPairEquals(const std::pair<T, U> &x, const std::pair<V, W> &y) {
CheckPairEquals(x.first, y.first);
CheckPairEquals(x.second, y.second);
}
+
+bool IsAssertEnabled() {
+ // Use an assert with side-effects to figure out if they are actually enabled.
+ bool assert_enabled = false;
+ assert([&]() { // NOLINT
+ assert_enabled = true;
+ return true;
+ }());
+ return assert_enabled;
+}
} // namespace
// The base class for a sorted associative container checker. TreeType is the
@@ -1219,8 +1233,10 @@ class BtreeNodePeer {
}
template <typename Btree>
- constexpr static bool UsesGenerations() {
- return Btree::params_type::kEnableGenerations;
+ constexpr static bool FieldTypeEqualsSlotType() {
+ return std::is_same<
+ typename btree_node<typename Btree::params_type>::field_type,
+ typename btree_node<typename Btree::params_type>::slot_type>::value;
}
};
@@ -1449,7 +1465,7 @@ class SizedBtreeSet
using Base = typename SizedBtreeSet::btree_set_container;
public:
- SizedBtreeSet() {}
+ SizedBtreeSet() = default;
using Base::Base;
};
@@ -1467,9 +1483,17 @@ void ExpectOperationCounts(const int expected_moves,
tracker->ResetCopiesMovesSwaps();
}
+#ifdef ABSL_HAVE_ADDRESS_SANITIZER
+constexpr bool kAsan = true;
+#else
+constexpr bool kAsan = false;
+#endif
+
// Note: when the values in this test change, it is expected to have an impact
// on performance.
TEST(Btree, MovesComparisonsCopiesSwapsTracking) {
+ if (kAsan) GTEST_SKIP() << "We do extra operations in ASan mode.";
+
InstanceTracker tracker;
// Note: this is minimum number of values per node.
SizedBtreeSet<MovableOnlyInstance, /*TargetValuesPerNode=*/4> set4;
@@ -1487,10 +1511,9 @@ TEST(Btree, MovesComparisonsCopiesSwapsTracking) {
EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set61)>(), 61);
EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set100)>(), 100);
if (sizeof(void *) == 8) {
- EXPECT_EQ(
- BtreeNodePeer::GetNumSlotsPerNode<absl::btree_set<int32_t>>(),
- // When we have generations, there is one fewer slot.
- BtreeNodePeer::UsesGenerations<absl::btree_set<int32_t>>() ? 60 : 61);
+ EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<absl::btree_set<int32_t>>(),
+ // When we have generations, there is one fewer slot.
+ BtreeGenerationsEnabled() ? 60 : 61);
}
// Test key insertion/deletion in random order.
@@ -1521,6 +1544,8 @@ struct MovableOnlyInstanceThreeWayCompare {
// Note: when the values in this test change, it is expected to have an impact
// on performance.
TEST(Btree, MovesComparisonsCopiesSwapsTrackingThreeWayCompare) {
+ if (kAsan) GTEST_SKIP() << "We do extra operations in ASan mode.";
+
InstanceTracker tracker;
// Note: this is minimum number of values per node.
SizedBtreeSet<MovableOnlyInstance, /*TargetValuesPerNode=*/4,
@@ -1544,10 +1569,9 @@ TEST(Btree, MovesComparisonsCopiesSwapsTrackingThreeWayCompare) {
EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set61)>(), 61);
EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set100)>(), 100);
if (sizeof(void *) == 8) {
- EXPECT_EQ(
- BtreeNodePeer::GetNumSlotsPerNode<absl::btree_set<int32_t>>(),
- // When we have generations, there is one fewer slot.
- BtreeNodePeer::UsesGenerations<absl::btree_set<int32_t>>() ? 60 : 61);
+ EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<absl::btree_set<int32_t>>(),
+ // When we have generations, there is one fewer slot.
+ BtreeGenerationsEnabled() ? 60 : 61);
}
// Test key insertion/deletion in random order.
@@ -1649,10 +1673,9 @@ TEST(Btree, BtreeMultisetEmplace) {
auto iter = s.emplace(value_to_insert);
ASSERT_NE(iter, s.end());
EXPECT_EQ(*iter, value_to_insert);
- auto iter2 = s.emplace(value_to_insert);
- EXPECT_NE(iter2, iter);
- ASSERT_NE(iter2, s.end());
- EXPECT_EQ(*iter2, value_to_insert);
+ iter = s.emplace(value_to_insert);
+ ASSERT_NE(iter, s.end());
+ EXPECT_EQ(*iter, value_to_insert);
auto result = s.equal_range(value_to_insert);
EXPECT_EQ(std::distance(result.first, result.second), 2);
}
@@ -1663,44 +1686,45 @@ TEST(Btree, BtreeMultisetEmplaceHint) {
auto iter = s.emplace(value_to_insert);
ASSERT_NE(iter, s.end());
EXPECT_EQ(*iter, value_to_insert);
- auto emplace_iter = s.emplace_hint(iter, value_to_insert);
- EXPECT_NE(emplace_iter, iter);
- ASSERT_NE(emplace_iter, s.end());
- EXPECT_EQ(*emplace_iter, value_to_insert);
+ iter = s.emplace_hint(iter, value_to_insert);
+ // The new element should be before the previously inserted one.
+ EXPECT_EQ(iter, s.lower_bound(value_to_insert));
+ ASSERT_NE(iter, s.end());
+ EXPECT_EQ(*iter, value_to_insert);
}
TEST(Btree, BtreeMultimapEmplace) {
const int key_to_insert = 123456;
const char value0[] = "a";
- absl::btree_multimap<int, std::string> s;
- auto iter = s.emplace(key_to_insert, value0);
- ASSERT_NE(iter, s.end());
+ absl::btree_multimap<int, std::string> m;
+ auto iter = m.emplace(key_to_insert, value0);
+ ASSERT_NE(iter, m.end());
EXPECT_EQ(iter->first, key_to_insert);
EXPECT_EQ(iter->second, value0);
const char value1[] = "b";
- auto iter2 = s.emplace(key_to_insert, value1);
- EXPECT_NE(iter2, iter);
- ASSERT_NE(iter2, s.end());
- EXPECT_EQ(iter2->first, key_to_insert);
- EXPECT_EQ(iter2->second, value1);
- auto result = s.equal_range(key_to_insert);
+ iter = m.emplace(key_to_insert, value1);
+ ASSERT_NE(iter, m.end());
+ EXPECT_EQ(iter->first, key_to_insert);
+ EXPECT_EQ(iter->second, value1);
+ auto result = m.equal_range(key_to_insert);
EXPECT_EQ(std::distance(result.first, result.second), 2);
}
TEST(Btree, BtreeMultimapEmplaceHint) {
const int key_to_insert = 123456;
const char value0[] = "a";
- absl::btree_multimap<int, std::string> s;
- auto iter = s.emplace(key_to_insert, value0);
- ASSERT_NE(iter, s.end());
+ absl::btree_multimap<int, std::string> m;
+ auto iter = m.emplace(key_to_insert, value0);
+ ASSERT_NE(iter, m.end());
EXPECT_EQ(iter->first, key_to_insert);
EXPECT_EQ(iter->second, value0);
const char value1[] = "b";
- auto emplace_iter = s.emplace_hint(iter, key_to_insert, value1);
- EXPECT_NE(emplace_iter, iter);
- ASSERT_NE(emplace_iter, s.end());
- EXPECT_EQ(emplace_iter->first, key_to_insert);
- EXPECT_EQ(emplace_iter->second, value1);
+ iter = m.emplace_hint(iter, key_to_insert, value1);
+ // The new element should be before the previously inserted one.
+ EXPECT_EQ(iter, m.lower_bound(key_to_insert));
+ ASSERT_NE(iter, m.end());
+ EXPECT_EQ(iter->first, key_to_insert);
+ EXPECT_EQ(iter->second, value1);
}
TEST(Btree, ConstIteratorAccessors) {
@@ -2111,6 +2135,79 @@ TEST(Btree, ExtractMultiMapEquivalentKeys) {
}
}
+TEST(Btree, ExtractAndGetNextSet) {
+ absl::btree_set<int> src = {1, 2, 3, 4, 5};
+ auto it = src.find(3);
+ auto extracted_and_next = src.extract_and_get_next(it);
+ EXPECT_THAT(src, ElementsAre(1, 2, 4, 5));
+ EXPECT_EQ(extracted_and_next.node.value(), 3);
+ EXPECT_EQ(*extracted_and_next.next, 4);
+}
+
+TEST(Btree, ExtractAndGetNextMultiSet) {
+ absl::btree_multiset<int> src = {1, 2, 3, 4, 5};
+ auto it = src.find(3);
+ auto extracted_and_next = src.extract_and_get_next(it);
+ EXPECT_THAT(src, ElementsAre(1, 2, 4, 5));
+ EXPECT_EQ(extracted_and_next.node.value(), 3);
+ EXPECT_EQ(*extracted_and_next.next, 4);
+}
+
+TEST(Btree, ExtractAndGetNextMap) {
+ absl::btree_map<int, int> src = {{1, 2}, {3, 4}, {5, 6}};
+ auto it = src.find(3);
+ auto extracted_and_next = src.extract_and_get_next(it);
+ EXPECT_THAT(src, ElementsAre(Pair(1, 2), Pair(5, 6)));
+ EXPECT_EQ(extracted_and_next.node.key(), 3);
+ EXPECT_EQ(extracted_and_next.node.mapped(), 4);
+ EXPECT_THAT(*extracted_and_next.next, Pair(5, 6));
+}
+
+TEST(Btree, ExtractAndGetNextMultiMap) {
+ absl::btree_multimap<int, int> src = {{1, 2}, {3, 4}, {5, 6}};
+ auto it = src.find(3);
+ auto extracted_and_next = src.extract_and_get_next(it);
+ EXPECT_THAT(src, ElementsAre(Pair(1, 2), Pair(5, 6)));
+ EXPECT_EQ(extracted_and_next.node.key(), 3);
+ EXPECT_EQ(extracted_and_next.node.mapped(), 4);
+ EXPECT_THAT(*extracted_and_next.next, Pair(5, 6));
+}
+
+TEST(Btree, ExtractAndGetNextEndIter) {
+ absl::btree_set<int> src = {1, 2, 3, 4, 5};
+ auto it = src.find(5);
+ auto extracted_and_next = src.extract_and_get_next(it);
+ EXPECT_THAT(src, ElementsAre(1, 2, 3, 4));
+ EXPECT_EQ(extracted_and_next.node.value(), 5);
+ EXPECT_EQ(extracted_and_next.next, src.end());
+}
+
+TEST(Btree, ExtractDoesntCauseExtraMoves) {
+#ifdef _MSC_VER
+ GTEST_SKIP() << "This test fails on MSVC.";
+#endif
+
+ using Set = absl::btree_set<MovableOnlyInstance>;
+ std::array<std::function<void(Set &)>, 3> extracters = {
+ [](Set &s) { auto node = s.extract(s.begin()); },
+ [](Set &s) { auto ret = s.extract_and_get_next(s.begin()); },
+ [](Set &s) { auto node = s.extract(MovableOnlyInstance(0)); }};
+
+ InstanceTracker tracker;
+ for (int i = 0; i < 3; ++i) {
+ Set s;
+ s.insert(MovableOnlyInstance(0));
+ tracker.ResetCopiesMovesSwaps();
+
+ extracters[i](s);
+ // We expect to see exactly 1 move: from the original slot into the
+ // extracted node.
+ EXPECT_EQ(tracker.copies(), 0) << i;
+ EXPECT_EQ(tracker.moves(), 1) << i;
+ EXPECT_EQ(tracker.swaps(), 0) << i;
+ }
+}
+
// For multisets, insert with hint also affects correctness because we need to
// insert immediately before the hint if possible.
struct InsertMultiHintData {
@@ -3003,8 +3100,9 @@ TEST(Btree, ConstructImplicitlyWithUnadaptedComparator) {
absl::btree_set<MultiKey, MultiKeyComp> set = {{}, MultiKeyComp{}};
}
-#ifndef NDEBUG
TEST(Btree, InvalidComparatorsCaught) {
+ if (!IsAssertEnabled()) GTEST_SKIP() << "Assertions not enabled.";
+
{
struct ZeroAlwaysLessCmp {
bool operator()(int lhs, int rhs) const {
@@ -3051,28 +3149,104 @@ TEST(Btree, InvalidComparatorsCaught) {
absl::btree_set<int, ThreeWaySumGreaterZeroCmp> set;
EXPECT_DEATH(set.insert({0, 1, 2}), "lhs_comp_rhs < 0 -> rhs_comp_lhs > 0");
}
+ // Verify that we detect cases of comparators that violate transitivity.
+ // When the comparators below check for the presence of an optional field,
+ // they violate transitivity because instances that have the optional field
+ // compare differently with each other from how they compare with instances
+ // that don't have the optional field.
+ struct ClockTime {
+ absl::optional<int> hour;
+ int minute;
+ };
+ // `comp(a,b) && comp(b,c) && !comp(a,c)` violates transitivity.
+ ClockTime a = {absl::nullopt, 1};
+ ClockTime b = {2, 5};
+ ClockTime c = {6, 0};
+ {
+ struct NonTransitiveTimeCmp {
+ bool operator()(ClockTime lhs, ClockTime rhs) const {
+ if (lhs.hour.has_value() && rhs.hour.has_value() &&
+ *lhs.hour != *rhs.hour) {
+ return *lhs.hour < *rhs.hour;
+ }
+ return lhs.minute < rhs.minute;
+ }
+ };
+ NonTransitiveTimeCmp cmp;
+ ASSERT_TRUE(cmp(a, b) && cmp(b, c) && !cmp(a, c));
+ absl::btree_set<ClockTime, NonTransitiveTimeCmp> set;
+ EXPECT_DEATH(set.insert({a, b, c}), "is_ordered_correctly");
+ absl::btree_multiset<ClockTime, NonTransitiveTimeCmp> mset;
+ EXPECT_DEATH(mset.insert({a, a, b, b, c, c}), "is_ordered_correctly");
+ }
+ {
+ struct ThreeWayNonTransitiveTimeCmp {
+ absl::weak_ordering operator()(ClockTime lhs, ClockTime rhs) const {
+ if (lhs.hour.has_value() && rhs.hour.has_value() &&
+ *lhs.hour != *rhs.hour) {
+ return *lhs.hour < *rhs.hour ? absl::weak_ordering::less
+ : absl::weak_ordering::greater;
+ }
+ return lhs.minute < rhs.minute ? absl::weak_ordering::less
+ : lhs.minute == rhs.minute ? absl::weak_ordering::equivalent
+ : absl::weak_ordering::greater;
+ }
+ };
+ ThreeWayNonTransitiveTimeCmp cmp;
+ ASSERT_TRUE(cmp(a, b) < 0 && cmp(b, c) < 0 && cmp(a, c) > 0);
+ absl::btree_set<ClockTime, ThreeWayNonTransitiveTimeCmp> set;
+ EXPECT_DEATH(set.insert({a, b, c}), "is_ordered_correctly");
+ absl::btree_multiset<ClockTime, ThreeWayNonTransitiveTimeCmp> mset;
+ EXPECT_DEATH(mset.insert({a, a, b, b, c, c}), "is_ordered_correctly");
+ }
+}
+
+TEST(Btree, MutatedKeysCaught) {
+ if (!IsAssertEnabled()) GTEST_SKIP() << "Assertions not enabled.";
+
+ struct IntPtrCmp {
+ bool operator()(int *lhs, int *rhs) const { return *lhs < *rhs; }
+ };
+ {
+ absl::btree_set<int *, IntPtrCmp> set;
+ int arr[] = {0, 1, 2};
+ set.insert({&arr[0], &arr[1], &arr[2]});
+ arr[0] = 100;
+ EXPECT_DEATH(set.insert(&arr[0]), "is_ordered_correctly");
+ }
+ {
+ absl::btree_multiset<int *, IntPtrCmp> set;
+ int arr[] = {0, 1, 2};
+ set.insert({&arr[0], &arr[0], &arr[1], &arr[1], &arr[2], &arr[2]});
+ arr[0] = 100;
+ EXPECT_DEATH(set.insert(&arr[0]), "is_ordered_correctly");
+ }
}
-#endif
#ifndef _MSC_VER
// This test crashes on MSVC.
TEST(Btree, InvalidIteratorUse) {
- if (!BtreeNodePeer::UsesGenerations<absl::btree_set<int>>())
+ if (!BtreeGenerationsEnabled())
GTEST_SKIP() << "Generation validation for iterators is disabled.";
+ // Invalid memory use can trigger heap-use-after-free in ASan or invalidated
+ // iterator assertions.
+ constexpr const char *kInvalidMemoryDeathMessage =
+ "heap-use-after-free|invalidated iterator";
+
{
absl::btree_set<int> set;
for (int i = 0; i < 10; ++i) set.insert(i);
auto it = set.begin();
set.erase(it++);
- EXPECT_DEATH(set.erase(it++), "invalidated iterator");
+ EXPECT_DEATH(set.erase(it++), kInvalidMemoryDeathMessage);
}
{
absl::btree_set<int> set;
for (int i = 0; i < 10; ++i) set.insert(i);
auto it = set.insert(20).first;
set.insert(30);
- EXPECT_DEATH(*it, "invalidated iterator");
+ EXPECT_DEATH(*it, kInvalidMemoryDeathMessage);
}
{
absl::btree_set<int> set;
@@ -3080,7 +3254,15 @@ TEST(Btree, InvalidIteratorUse) {
auto it = set.find(5000);
ASSERT_NE(it, set.end());
set.erase(1);
- EXPECT_DEATH(*it, "invalidated iterator");
+ EXPECT_DEATH(*it, kInvalidMemoryDeathMessage);
+ }
+ {
+ absl::btree_set<int> set;
+ for (int i = 0; i < 10; ++i) set.insert(i);
+ auto it = set.insert(20).first;
+ set.insert(30);
+ EXPECT_DEATH(void(it == set.begin()), kInvalidMemoryDeathMessage);
+ EXPECT_DEATH(void(set.begin() == it), kInvalidMemoryDeathMessage);
}
}
#endif
@@ -3320,6 +3502,108 @@ TEST(Btree, ReusePoisonMemory) {
set.insert(0);
}
+TEST(Btree, IteratorSubtraction) {
+ absl::BitGen bitgen;
+ std::vector<int> vec;
+ // Randomize the set's insertion order so the nodes aren't all full.
+ for (int i = 0; i < 1000000; ++i) vec.push_back(i);
+ absl::c_shuffle(vec, bitgen);
+
+ absl::btree_set<int> set;
+ for (int i : vec) set.insert(i);
+
+ for (int i = 0; i < 1000; ++i) {
+ size_t begin = absl::Uniform(bitgen, 0u, set.size());
+ size_t end = absl::Uniform(bitgen, begin, set.size());
+ ASSERT_EQ(end - begin, set.find(end) - set.find(begin))
+ << begin << " " << end;
+ }
+}
+
+TEST(Btree, DereferencingEndIterator) {
+ if (!IsAssertEnabled()) GTEST_SKIP() << "Assertions not enabled.";
+
+ absl::btree_set<int> set;
+ for (int i = 0; i < 1000; ++i) set.insert(i);
+ EXPECT_DEATH(*set.end(), R"regex(Dereferencing end\(\) iterator)regex");
+}
+
+TEST(Btree, InvalidIteratorComparison) {
+ if (!IsAssertEnabled()) GTEST_SKIP() << "Assertions not enabled.";
+
+ absl::btree_set<int> set1, set2;
+ for (int i = 0; i < 1000; ++i) {
+ set1.insert(i);
+ set2.insert(i);
+ }
+
+ constexpr const char *kValueInitDeathMessage =
+ "Comparing default-constructed iterator with .*non-default-constructed "
+ "iterator";
+ typename absl::btree_set<int>::iterator iter1, iter2;
+ EXPECT_EQ(iter1, iter2);
+ EXPECT_DEATH(void(set1.begin() == iter1), kValueInitDeathMessage);
+ EXPECT_DEATH(void(iter1 == set1.begin()), kValueInitDeathMessage);
+
+ constexpr const char *kDifferentContainerDeathMessage =
+ "Comparing iterators from different containers";
+ iter1 = set1.begin();
+ iter2 = set2.begin();
+ EXPECT_DEATH(void(iter1 == iter2), kDifferentContainerDeathMessage);
+ EXPECT_DEATH(void(iter2 == iter1), kDifferentContainerDeathMessage);
+}
+
+TEST(Btree, InvalidPointerUse) {
+ if (!kAsan)
+ GTEST_SKIP() << "We only detect invalid pointer use in ASan mode.";
+
+ absl::btree_set<int> set;
+ set.insert(0);
+ const int *ptr = &*set.begin();
+ set.insert(1);
+ EXPECT_DEATH(std::cout << *ptr, "heap-use-after-free");
+ size_t slots_per_node = BtreeNodePeer::GetNumSlotsPerNode<decltype(set)>();
+ for (int i = 2; i < slots_per_node - 1; ++i) set.insert(i);
+ ptr = &*set.begin();
+ set.insert(static_cast<int>(slots_per_node));
+ EXPECT_DEATH(std::cout << *ptr, "heap-use-after-free");
+}
+
+template<typename Set>
+void TestBasicFunctionality(Set set) {
+ using value_type = typename Set::value_type;
+ for (int i = 0; i < 100; ++i) { set.insert(value_type(i)); }
+ for (int i = 50; i < 100; ++i) { set.erase(value_type(i)); }
+ auto it = set.begin();
+ for (int i = 0; i < 50; ++i, ++it) {
+ ASSERT_EQ(set.find(value_type(i)), it) << i;
+ }
+}
+
+template<size_t align>
+struct alignas(align) OveralignedKey {
+ explicit OveralignedKey(int i) : key(i) {}
+ bool operator<(const OveralignedKey &other) const { return key < other.key; }
+ int key = 0;
+};
+
+TEST(Btree, OveralignedKey) {
+ // Test basic functionality with both even and odd numbers of slots per node.
+ // The goal here is to detect cases where alignment may be incorrect.
+ TestBasicFunctionality(
+ SizedBtreeSet<OveralignedKey<16>, /*TargetValuesPerNode=*/8>());
+ TestBasicFunctionality(
+ SizedBtreeSet<OveralignedKey<16>, /*TargetValuesPerNode=*/9>());
+}
+
+TEST(Btree, FieldTypeEqualsSlotType) {
+ // This breaks if we try to do layout_type::Pointer<slot_type> because
+ // slot_type is the same as field_type.
+ using set_type = absl::btree_set<uint8_t>;
+ static_assert(BtreeNodePeer::FieldTypeEqualsSlotType<set_type>(), "");
+ TestBasicFunctionality(set_type());
+}
+
} // namespace
} // namespace container_internal
ABSL_NAMESPACE_END
generated by cgit v1.2.3 (git 2.39.1) at 2025-06-11 22:27:07 +0000