Export of internal Abseil changes

--
daf5a2b9ab3507ad5fb9aebe9165933f33098b83 by Abseil Team <absl-team@google.com>:

Absl flat containers reserve enough space even in the presence of tombstones.

PiperOrigin-RevId: 372339945

--
9a61504867ba0eccc5046d7333090fbe3439cdd9 by Abseil Team <absl-team@google.com>:

Add benchmark for BlockingCounter

PiperOrigin-RevId: 372246068

--
91ee87e6de09fc62970667ee52654c9dcf7c478d by Evan Brown <ezb@google.com>:

In absl::StrSplit, support btree_multimap, and other non-std::multimap-multimaps by supporting any map type that returns iterator from insert().

Also:
- Use emplace() instead of insert() when available, not just for std::(multi)map - we can potentially change some string copies to moves this way.
- We no longer need the Insert class so remove it.
PiperOrigin-RevId: 372209653
GitOrigin-RevId: daf5a2b9ab3507ad5fb9aebe9165933f33098b83
Change-Id: I83098fde4a722cd4b682f024d3bfa56c613f960c

2 files changed, 28 insertions, 2 deletions

diff --git a/absl/container/flat_hash_map_test.cc b/absl/container/flat_hash_map_test.cc
index 89ec60c9..8dda1d35 100644
--- a/absl/container/flat_hash_map_test.cc
+++ b/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/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 8615de8b..b23e0078 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -1323,8 +1323,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));
     }
   }