Export of internal Abseil changes

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

Add a parameter pack to absl profile to allow profiles to separate
dynamic data from static data that is available at constructor-time.

Background: `inline_element_size` is effectively constant, but there
is a data race between its initialization and its access. We had fixed that race by making
inline_element_size atomic.  This CL changes `inline_element_size`
back to a non-atomic integer, and provides a way for all profiles to
provide Register()-time values.
PiperOrigin-RevId: 413960559

--
70234c5943f8e37e17c1d9c54d8ed61d39880abf by Chris Kennelly <ckennelly@google.com>:

Document that absl::FunctionRef does not allocate.

PiperOrigin-RevId: 413946831

--
3308ae571412c4be3cc32d088c6edac98ff2d1ed by Samuel Benzaquen <sbenza@google.com>:

Internal change

PiperOrigin-RevId: 413933619

--
1617093a730d055edcf7bc04fdd6509783f5f75d by Martijn Vels <mvels@google.com>:

Internal Change

PiperOrigin-RevId: 413778735

--
03ad683f059c806a6c8b04f5b79b2662c3df8c73 by Evan Brown <ezb@google.com>:

Unify btree erase_if definitions and optimize them so that we only do rebalancing once per leaf node.

PiperOrigin-RevId: 413757280

--
5ba402f70801938178e486617063f01c7862525d by Martijn Vels <mvels@google.com>:

Cleanup up cord sampling internals

PiperOrigin-RevId: 413755011

--
522da8f9d3e0f11630d89fb41952004742bc335a by Evan Brown <ezb@google.com>:

Add b-tree benchmark for erase_if.

Since this benchmark doesn't work for std:: containers before C++20, disable it for them.

PiperOrigin-RevId: 413740844

--
a690ea42de8ed4a761d00235d8b2fb7548ba9732 by Andy Getzendanner <durandal@google.com>:

Import of CCTZ from GitHub.

PiperOrigin-RevId: 413735737
GitOrigin-RevId: e7f53dfbf809812e84770217777f81b6308a3084
Change-Id: I4f9f9039ba92831bc48971964aa063244c9fed72

1 files changed, 46 insertions, 0 deletions

diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index bf65a03d..29603379 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -830,6 +830,7 @@ class btree_node {
   template <typename N, typename R, typename P>
   friend struct btree_iterator;
   friend class BtreeNodePeer;
+  friend struct btree_access;
 };
 
 template <typename Node, typename Reference, typename Pointer>
@@ -964,6 +965,7 @@ struct btree_iterator {
   friend class btree_multiset_container;
   template <typename TreeType, typename CheckerType>
   friend class base_checker;
+  friend struct btree_access;
 
   const key_type &key() const { return node->key(position); }
   slot_type *slot() { return node->slot(position); }
@@ -1336,6 +1338,8 @@ class btree {
   allocator_type get_allocator() const { return allocator(); }
 
  private:
+  friend struct btree_access;
+
   // Internal accessor routines.
   node_type *root() { return root_.template get<2>(); }
   const node_type *root() const { return root_.template get<2>(); }
@@ -2530,6 +2534,48 @@ int btree<P>::internal_verify(const node_type *node, const key_type *lo,
   return count;
 }
 
+struct btree_access {
+  template <typename BtreeContainer, typename Pred>
+  static auto erase_if(BtreeContainer &container, Pred pred)
+      -> typename BtreeContainer::size_type {
+    const auto initial_size = container.size();
+    auto &tree = container.tree_;
+    auto *alloc = tree.mutable_allocator();
+    for (auto it = container.begin(); it != container.end();) {
+      if (!pred(*it)) {
+        ++it;
+        continue;
+      }
+      auto *node = it.node;
+      if (!node->leaf()) {
+        // Handle internal nodes normally.
+        it = container.erase(it);
+        continue;
+      }
+      // If this is a leaf node, then we do all the erases from this node
+      // at once before doing rebalancing.
+
+      // The current position to transfer slots to.
+      int to_pos = it.position;
+      node->value_destroy(it.position, alloc);
+      while (++it.position < node->finish()) {
+        if (pred(*it)) {
+          node->value_destroy(it.position, alloc);
+        } else {
+          node->transfer(node->slot(to_pos++), node->slot(it.position),
+                         alloc);
+        }
+      }
+      const int num_deleted = node->finish() - to_pos;
+      tree.size_ -= num_deleted;
+      node->set_finish(to_pos);
+      it.position = to_pos;
+      it = tree.rebalance_after_delete(it);
+    }
+    return initial_size - container.size();
+  }
+};
+
 }  // namespace container_internal
 ABSL_NAMESPACE_END
 }  // namespace absl