From 5bf048b8425cc0a342e4647932de19e25ffd6ad7 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Mon, 26 Oct 2020 09:50:44 -0700 Subject: Export of internal Abseil changes -- 730bb88bee556aa11fa19aa33e1434cb6fa78985 by Evan Brown : Support missing allocator-related constructors in b-tree. See [reference](https://en.cppreference.com/w/cpp/container/set/set). Also use allocator_traits::select_on_container_copy_construction() to get allocator for copy construction. PiperOrigin-RevId: 339058322 -- b6cc121689ae3e452d1db2d66122cb198d25142b by Derek Mauro : Fix more sign-compare warnings PiperOrigin-RevId: 339057920 -- 0e2c62da1dcaf6529abab952bdcc96c6de2d9506 by Abseil Team : Add missing include PiperOrigin-RevId: 339054753 -- d5a9ec2d1e40fe6359e720942e4955009ee415ec by Derek Mauro : Stop disabling sign-compare warnings for non-test targets. Our users complain about these. This does not catch issues in header-only libraries (like btree.h) but we may work on those in the future PiperOrigin-RevId: 338967089 -- 0c062c542a4c61ea0f65d25811827c0858e3adde by Abseil Team : Improve cache-locality for ThreadIdentity and PerThreadSynch. This is a change based on an observation in RPC benchmarks that shows significant cycles being spent in waking up a thread, 99.8% of which was on cache misses. Investigating this a bit more, it turns out to be due to sharing the cache line with the waiter state. To fix this issue, the following changes are introduced: - Reorder fields in PerThreadSync so that it fits in a single cache line The size of this structure was 80 bytes before this change. Note: Manually inspected all booleans to make sure they are not modified by multiple threads concurrently. PiperOrigin-RevId: 338852058 -- a90d6f2b2346385017e32dd8ae1b5ca691a5863f by Derek Mauro : Delete GCC 4.9 test script. It is no longer supported PiperOrigin-RevId: 338779452 -- 7274008d4757e88869110be9db39d03d911ae2b5 by Abseil Team : Fix the usage example in which SetFlag should take a pointer. PiperOrigin-RevId: 338744529 GitOrigin-RevId: 730bb88bee556aa11fa19aa33e1434cb6fa78985 Change-Id: Iff99594c4022e60e482a392d334b376c7ae8883e --- absl/container/internal/btree.h | 42 ++++++++++++++++++++++------------------- 1 file changed, 23 insertions(+), 19 deletions(-) (limited to 'absl/container/internal/btree.h') diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h index a82b5177..8547d68e 100644 --- a/absl/container/internal/btree.h +++ b/absl/container/internal/btree.h @@ -1141,21 +1141,35 @@ class btree { // before this method is called. This method is used in copy construction, // copy assignment, and move assignment. template - void copy_or_move_values_in_order(Btree *other); + void copy_or_move_values_in_order(Btree &other); // Validates that various assumptions/requirements are true at compile time. constexpr static bool static_assert_validation(); public: - btree(const key_compare &comp, const allocator_type &alloc); + btree(const key_compare &comp, const allocator_type &alloc) + : root_(comp, alloc, EmptyNode()), rightmost_(EmptyNode()), size_(0) {} - btree(const btree &other); + btree(const btree &other) : btree(other, other.allocator()) {} + btree(const btree &other, const allocator_type &alloc) + : btree(other.key_comp(), alloc) { + copy_or_move_values_in_order(other); + } btree(btree &&other) noexcept : root_(std::move(other.root_)), rightmost_(absl::exchange(other.rightmost_, EmptyNode())), size_(absl::exchange(other.size_, 0)) { other.mutable_root() = EmptyNode(); } + btree(btree &&other, const allocator_type &alloc) + : btree(other.key_comp(), alloc) { + if (alloc == other.allocator()) { + swap(other); + } else { + // Move values from `other` one at a time when allocators are different. + copy_or_move_values_in_order(other); + } + } ~btree() { // Put static_asserts in destructor to avoid triggering them before the type @@ -1851,7 +1865,7 @@ void btree_iterator::decrement_slow() { // btree methods template template -void btree

::copy_or_move_values_in_order(Btree *other) { +void btree

::copy_or_move_values_in_order(Btree &other) { static_assert(std::is_same::value || std::is_same::value, "Btree type must be same or const."); @@ -1859,11 +1873,11 @@ void btree

::copy_or_move_values_in_order(Btree *other) { // We can avoid key comparisons because we know the order of the // values is the same order we'll store them in. - auto iter = other->begin(); - if (iter == other->end()) return; + auto iter = other.begin(); + if (iter == other.end()) return; insert_multi(maybe_move_from_iterator(iter)); ++iter; - for (; iter != other->end(); ++iter) { + for (; iter != other.end(); ++iter) { // If the btree is not empty, we can just insert the new value at the end // of the tree. internal_emplace(end(), maybe_move_from_iterator(iter)); @@ -1901,16 +1915,6 @@ constexpr bool btree

::static_assert_validation() { return true; } -template -btree

::btree(const key_compare &comp, const allocator_type &alloc) - : root_(comp, alloc, EmptyNode()), rightmost_(EmptyNode()), size_(0) {} - -template -btree

::btree(const btree &other) - : btree(other.key_comp(), other.allocator()) { - copy_or_move_values_in_order(&other); -} - template template auto btree

::equal_range(const K &key) -> std::pair { @@ -2068,7 +2072,7 @@ auto btree

::operator=(const btree &other) -> btree & { *mutable_allocator() = other.allocator(); } - copy_or_move_values_in_order(&other); + copy_or_move_values_in_order(other); } return *this; } @@ -2098,7 +2102,7 @@ auto btree

::operator=(btree &&other) noexcept -> btree & { // comparator while moving the values so we can't swap the key // comparators. *mutable_key_comp() = other.key_comp(); - copy_or_move_values_in_order(&other); + copy_or_move_values_in_order(other); } } } -- cgit v1.2.3