1 files changed, 73 insertions, 17 deletions

diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index 48f70cb..ea73f03 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) {