From 9336be04a242237cd41a525bedfcf3be1bb55377 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Fri, 3 Dec 2021 10:01:02 -0800 Subject: Export of internal Abseil changes -- e7f53dfbf809812e84770217777f81b6308a3084 by Abseil Team : 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 : Document that absl::FunctionRef does not allocate. PiperOrigin-RevId: 413946831 -- 3308ae571412c4be3cc32d088c6edac98ff2d1ed by Samuel Benzaquen : Internal change PiperOrigin-RevId: 413933619 -- 1617093a730d055edcf7bc04fdd6509783f5f75d by Martijn Vels : Internal Change PiperOrigin-RevId: 413778735 -- 03ad683f059c806a6c8b04f5b79b2662c3df8c73 by Evan Brown : 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 : Cleanup up cord sampling internals PiperOrigin-RevId: 413755011 -- 522da8f9d3e0f11630d89fb41952004742bc335a by Evan Brown : 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 : Import of CCTZ from GitHub. PiperOrigin-RevId: 413735737 GitOrigin-RevId: e7f53dfbf809812e84770217777f81b6308a3084 Change-Id: I4f9f9039ba92831bc48971964aa063244c9fed72 --- absl/container/internal/btree.h | 46 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 46 insertions(+) (limited to 'absl/container/internal/btree.h') 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 friend struct btree_iterator; friend class BtreeNodePeer; + friend struct btree_access; }; template @@ -964,6 +965,7 @@ struct btree_iterator { friend class btree_multiset_container; template 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

::internal_verify(const node_type *node, const key_type *lo, return count; } +struct btree_access { + template + 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 -- cgit v1.2.3