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

8 files changed, 184 insertions, 37 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));
     }
   }
diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel
index f3b08de6..1cb5b3e5 100644
--- a/absl/strings/BUILD.bazel
+++ b/absl/strings/BUILD.bazel
@@ -728,6 +728,7 @@ cc_test(
         ":strings",
         "//absl/base:core_headers",
         "//absl/base:dynamic_annotations",
+        "//absl/container:btree",
         "//absl/container:flat_hash_map",
         "//absl/container:node_hash_map",
         "@com_google_googletest//:gtest_main",
diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt
index d01f0f18..d3f1523c 100644
--- a/absl/strings/CMakeLists.txt
+++ b/absl/strings/CMakeLists.txt
@@ -221,9 +221,9 @@ absl_cc_test(
     ${ABSL_TEST_COPTS}
   DEPS
     absl::strings
-    absl::base
     absl::core_headers
     absl::dynamic_annotations
+    absl::btree
     absl::flat_hash_map
     absl::node_hash_map
     gmock_main
diff --git a/absl/strings/internal/str_split_internal.h b/absl/strings/internal/str_split_internal.h
index a2f41c15..17c1bfe8 100644
--- a/absl/strings/internal/str_split_internal.h
+++ b/absl/strings/internal/str_split_internal.h
@@ -32,7 +32,7 @@
 #include <array>
 #include <initializer_list>
 #include <iterator>
-#include <map>
+#include <tuple>
 #include <type_traits>
 #include <utility>
 #include <vector>
@@ -182,6 +182,13 @@ template <typename T>
 struct HasConstIterator<T, absl::void_t<typename T::const_iterator>>
     : std::true_type {};
 
+// HasEmplace<T>::value is true iff there exists a method T::emplace().
+template <typename T, typename = void>
+struct HasEmplace : std::false_type {};
+template <typename T>
+struct HasEmplace<T, absl::void_t<decltype(std::declval<T>().emplace())>>
+    : std::true_type {};
+
 // IsInitializerList<T>::value is true iff T is an std::initializer_list. More
 // details below in Splitter<> where this is used.
 std::false_type IsInitializerListDispatch(...);  // default: No
@@ -372,50 +379,43 @@ class Splitter {
   // value.
   template <typename Container, typename First, typename Second>
   struct ConvertToContainer<Container, std::pair<const First, Second>, true> {
+    using iterator = typename Container::iterator;
+
     Container operator()(const Splitter& splitter) const {
       Container m;
-      typename Container::iterator it;
+      iterator it;
       bool insert = true;
-      for (const auto& sp : splitter) {
+      for (const absl::string_view sv : splitter) {
         if (insert) {
-          it = Inserter<Container>::Insert(&m, First(sp), Second());
+          it = InsertOrEmplace(&m, sv);
         } else {
-          it->second = Second(sp);
+          it->second = Second(sv);
         }
         insert = !insert;
       }
       return m;
     }
 
-    // Inserts the key and value into the given map, returning an iterator to
-    // the inserted item. Specialized for std::map and std::multimap to use
-    // emplace() and adapt emplace()'s return value.
-    template <typename Map>
-    struct Inserter {
-      using M = Map;
-      template <typename... Args>
-      static typename M::iterator Insert(M* m, Args&&... args) {
-        return m->insert(std::make_pair(std::forward<Args>(args)...)).first;
-      }
-    };
-
-    template <typename... Ts>
-    struct Inserter<std::map<Ts...>> {
-      using M = std::map<Ts...>;
-      template <typename... Args>
-      static typename M::iterator Insert(M* m, Args&&... args) {
-        return m->emplace(std::make_pair(std::forward<Args>(args)...)).first;
-      }
-    };
-
-    template <typename... Ts>
-    struct Inserter<std::multimap<Ts...>> {
-      using M = std::multimap<Ts...>;
-      template <typename... Args>
-      static typename M::iterator Insert(M* m, Args&&... args) {
-        return m->emplace(std::make_pair(std::forward<Args>(args)...));
-      }
-    };
+    // Inserts the key and an empty value into the map, returning an iterator to
+    // the inserted item. We use emplace() if available, otherwise insert().
+    template <typename M>
+    static absl::enable_if_t<HasEmplace<M>::value, iterator> InsertOrEmplace(
+        M* m, absl::string_view key) {
+      // Use piecewise_construct to support old versions of gcc in which pair
+      // constructor can't otherwise construct string from string_view.
+      return ToIter(m->emplace(std::piecewise_construct, std::make_tuple(key),
+                               std::tuple<>()));
+    }
+    template <typename M>
+    static absl::enable_if_t<!HasEmplace<M>::value, iterator> InsertOrEmplace(
+        M* m, absl::string_view key) {
+      return ToIter(m->insert(std::make_pair(First(key), Second(""))));
+    }
+
+    static iterator ToIter(std::pair<iterator, bool> pair) {
+      return pair.first;
+    }
+    static iterator ToIter(iterator iter) { return iter; }
   };
 
   StringType text_;
diff --git a/absl/strings/str_split_test.cc b/absl/strings/str_split_test.cc
index 7f7c097f..f472f9ed 100644
--- a/absl/strings/str_split_test.cc
+++ b/absl/strings/str_split_test.cc
@@ -29,6 +29,8 @@
 #include "gtest/gtest.h"
 #include "absl/base/dynamic_annotations.h"
 #include "absl/base/macros.h"
+#include "absl/container/btree_map.h"
+#include "absl/container/btree_set.h"
 #include "absl/container/flat_hash_map.h"
 #include "absl/container/node_hash_map.h"
 #include "absl/strings/numbers.h"
@@ -405,6 +407,10 @@ TEST(Splitter, ConversionOperator) {
   TestConversionOperator<std::set<std::string>>(splitter);
   TestConversionOperator<std::multiset<absl::string_view>>(splitter);
   TestConversionOperator<std::multiset<std::string>>(splitter);
+  TestConversionOperator<absl::btree_set<absl::string_view>>(splitter);
+  TestConversionOperator<absl::btree_set<std::string>>(splitter);
+  TestConversionOperator<absl::btree_multiset<absl::string_view>>(splitter);
+  TestConversionOperator<absl::btree_multiset<std::string>>(splitter);
   TestConversionOperator<std::unordered_set<std::string>>(splitter);
 
   // Tests conversion to map-like objects.
@@ -421,6 +427,22 @@ TEST(Splitter, ConversionOperator) {
   TestMapConversionOperator<std::multimap<std::string, absl::string_view>>(
       splitter);
   TestMapConversionOperator<std::multimap<std::string, std::string>>(splitter);
+  TestMapConversionOperator<
+      absl::btree_map<absl::string_view, absl::string_view>>(splitter);
+  TestMapConversionOperator<absl::btree_map<absl::string_view, std::string>>(
+      splitter);
+  TestMapConversionOperator<absl::btree_map<std::string, absl::string_view>>(
+      splitter);
+  TestMapConversionOperator<absl::btree_map<std::string, std::string>>(
+      splitter);
+  TestMapConversionOperator<
+      absl::btree_multimap<absl::string_view, absl::string_view>>(splitter);
+  TestMapConversionOperator<
+      absl::btree_multimap<absl::string_view, std::string>>(splitter);
+  TestMapConversionOperator<
+      absl::btree_multimap<std::string, absl::string_view>>(splitter);
+  TestMapConversionOperator<absl::btree_multimap<std::string, std::string>>(
+      splitter);
   TestMapConversionOperator<std::unordered_map<std::string, std::string>>(
       splitter);
   TestMapConversionOperator<
diff --git a/absl/synchronization/BUILD.bazel b/absl/synchronization/BUILD.bazel
index 5ce16958..92e2448d 100644
--- a/absl/synchronization/BUILD.bazel
+++ b/absl/synchronization/BUILD.bazel
@@ -136,6 +136,21 @@ cc_test(
     ],
 )
 
+cc_binary(
+    name = "blocking_counter_benchmark",
+    testonly = 1,
+    srcs = ["blocking_counter_benchmark.cc"],
+    copts = ABSL_TEST_COPTS,
+    linkopts = ABSL_DEFAULT_LINKOPTS,
+    tags = ["benchmark"],
+    visibility = ["//visibility:private"],
+    deps = [
+        ":synchronization",
+        ":thread_pool",
+        "@com_github_google_benchmark//:benchmark_main",
+    ],
+)
+
 cc_test(
     name = "graphcycles_test",
     size = "medium",
diff --git a/absl/synchronization/blocking_counter_benchmark.cc b/absl/synchronization/blocking_counter_benchmark.cc
new file mode 100644
index 00000000..b504d1a5
--- /dev/null
+++ b/absl/synchronization/blocking_counter_benchmark.cc
@@ -0,0 +1,83 @@
+// Copyright 2021 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include <limits>
+
+#include "absl/synchronization/blocking_counter.h"
+#include "absl/synchronization/internal/thread_pool.h"
+#include "benchmark/benchmark.h"
+
+namespace {
+
+void BM_BlockingCounter_SingleThread(benchmark::State& state) {
+  for (auto _ : state) {
+    int iterations = state.range(0);
+    absl::BlockingCounter counter{iterations};
+    for (int i = 0; i < iterations; ++i) {
+      counter.DecrementCount();
+    }
+    counter.Wait();
+  }
+}
+BENCHMARK(BM_BlockingCounter_SingleThread)
+    ->ArgName("iterations")
+    ->Arg(2)
+    ->Arg(4)
+    ->Arg(16)
+    ->Arg(64)
+    ->Arg(256);
+
+void BM_BlockingCounter_DecrementCount(benchmark::State& state) {
+  static absl::BlockingCounter* counter =
+      new absl::BlockingCounter{std::numeric_limits<int>::max()};
+  for (auto _ : state) {
+    counter->DecrementCount();
+  }
+}
+BENCHMARK(BM_BlockingCounter_DecrementCount)
+    ->Threads(2)
+    ->Threads(4)
+    ->Threads(6)
+    ->Threads(8)
+    ->Threads(10)
+    ->Threads(12)
+    ->Threads(16)
+    ->Threads(32)
+    ->Threads(64)
+    ->Threads(128);
+
+void BM_BlockingCounter_Wait(benchmark::State& state) {
+  int num_threads = state.range(0);
+  absl::synchronization_internal::ThreadPool pool(num_threads);
+  for (auto _ : state) {
+    absl::BlockingCounter counter{num_threads};
+    pool.Schedule([num_threads, &counter, &pool]() {
+      for (int i = 0; i < num_threads; ++i) {
+        pool.Schedule([&counter]() { counter.DecrementCount(); });
+      }
+    });
+    counter.Wait();
+  }
+}
+BENCHMARK(BM_BlockingCounter_Wait)
+    ->ArgName("threads")
+    ->Arg(2)
+    ->Arg(4)
+    ->Arg(8)
+    ->Arg(16)
+    ->Arg(32)
+    ->Arg(64)
+    ->Arg(128);
+
+}  // namespace