summaryrefslogtreecommitdiff
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.cc90
1 files changed, 73 insertions, 17 deletions
diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index 48f70cb0..ea73f032 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -45,6 +45,7 @@ namespace absl {
namespace container_internal {
namespace {
+using ::absl::test_internal::CopyableMovableInstance;
using ::absl::test_internal::InstanceTracker;
using ::absl::test_internal::MovableOnlyInstance;
using ::testing::ElementsAre;
@@ -1823,25 +1824,80 @@ TEST(Btree, ExtractAndInsertNodeHandleSet) {
EXPECT_EQ(res.node.value(), 3);
}
-struct Deref {
- bool operator()(const std::unique_ptr<int> &lhs,
- const std::unique_ptr<int> &rhs) const {
- return *lhs < *rhs;
+template <typename Set>
+void TestExtractWithTrackingForSet() {
+ InstanceTracker tracker;
+ {
+ Set s;
+ // Add enough elements to make sure we test internal nodes too.
+ const size_t kSize = 1000;
+ while (s.size() < kSize) {
+ s.insert(MovableOnlyInstance(s.size()));
+ }
+ for (int i = 0; i < kSize; ++i) {
+ // Extract with key
+ auto nh = s.extract(MovableOnlyInstance(i));
+ EXPECT_EQ(s.size(), kSize - 1);
+ EXPECT_EQ(nh.value().value(), i);
+ // Insert with node
+ s.insert(std::move(nh));
+ EXPECT_EQ(s.size(), kSize);
+
+ // Extract with iterator
+ auto it = s.find(MovableOnlyInstance(i));
+ nh = s.extract(it);
+ EXPECT_EQ(s.size(), kSize - 1);
+ EXPECT_EQ(nh.value().value(), i);
+ // Insert with node and hint
+ s.insert(s.begin(), std::move(nh));
+ EXPECT_EQ(s.size(), kSize);
+ }
}
-};
+ EXPECT_EQ(0, tracker.instances());
+}
+
+template <typename Map>
+void TestExtractWithTrackingForMap() {
+ InstanceTracker tracker;
+ {
+ Map m;
+ // Add enough elements to make sure we test internal nodes too.
+ const size_t kSize = 1000;
+ while (m.size() < kSize) {
+ m.insert(
+ {CopyableMovableInstance(m.size()), MovableOnlyInstance(m.size())});
+ }
+ for (int i = 0; i < kSize; ++i) {
+ // Extract with key
+ auto nh = m.extract(CopyableMovableInstance(i));
+ EXPECT_EQ(m.size(), kSize - 1);
+ EXPECT_EQ(nh.key().value(), i);
+ EXPECT_EQ(nh.mapped().value(), i);
+ // Insert with node
+ m.insert(std::move(nh));
+ EXPECT_EQ(m.size(), kSize);
+
+ // Extract with iterator
+ auto it = m.find(CopyableMovableInstance(i));
+ nh = m.extract(it);
+ EXPECT_EQ(m.size(), kSize - 1);
+ EXPECT_EQ(nh.key().value(), i);
+ EXPECT_EQ(nh.mapped().value(), i);
+ // Insert with node and hint
+ m.insert(m.begin(), std::move(nh));
+ EXPECT_EQ(m.size(), kSize);
+ }
+ }
+ EXPECT_EQ(0, tracker.instances());
+}
-TEST(Btree, ExtractWithUniquePtr) {
- absl::btree_set<std::unique_ptr<int>, Deref> s;
- s.insert(absl::make_unique<int>(1));
- s.insert(absl::make_unique<int>(2));
- s.insert(absl::make_unique<int>(3));
- s.insert(absl::make_unique<int>(4));
- s.insert(absl::make_unique<int>(5));
- auto nh = s.extract(s.find(absl::make_unique<int>(3)));
- EXPECT_EQ(s.size(), 4);
- EXPECT_EQ(*nh.value(), 3);
- s.insert(std::move(nh));
- EXPECT_EQ(s.size(), 5);
+TEST(Btree, ExtractTracking) {
+ TestExtractWithTrackingForSet<absl::btree_set<MovableOnlyInstance>>();
+ TestExtractWithTrackingForSet<absl::btree_multiset<MovableOnlyInstance>>();
+ TestExtractWithTrackingForMap<
+ absl::btree_map<CopyableMovableInstance, MovableOnlyInstance>>();
+ TestExtractWithTrackingForMap<
+ absl::btree_multimap<CopyableMovableInstance, MovableOnlyInstance>>();
}
TEST(Btree, ExtractAndInsertNodeHandleMultiSet) {