From 082c006c04343a78d87b6c6ab3608c25d6213c3f Mon Sep 17 00:00:00 2001 From: Vincent Ambo Date: Sat, 21 Nov 2020 14:43:54 +0100 Subject: merge(3p/absl): subtree merge of Abseil up to e19260f ... notably, this includes Abseil's own StatusOr type, which conflicted with our implementation (that was taken from TensorFlow). Change-Id: Ie7d6764b64055caaeb8dc7b6b9d066291e6b538f --- .../absl/container/internal/btree_container.h | 293 +++++++++++---------- 1 file changed, 152 insertions(+), 141 deletions(-) (limited to 'third_party/abseil_cpp/absl/container/internal/btree_container.h') diff --git a/third_party/abseil_cpp/absl/container/internal/btree_container.h b/third_party/abseil_cpp/absl/container/internal/btree_container.h index 734c90ef3d9c..887eda4122f8 100644 --- a/third_party/abseil_cpp/absl/container/internal/btree_container.h +++ b/third_party/abseil_cpp/absl/container/internal/btree_container.h @@ -23,6 +23,7 @@ #include "absl/base/internal/throw_delegate.h" #include "absl/container/internal/btree.h" // IWYU pragma: export #include "absl/container/internal/common.h" +#include "absl/memory/memory.h" #include "absl/meta/type_traits.h" namespace absl { @@ -68,8 +69,21 @@ class btree_container { explicit btree_container(const key_compare &comp, const allocator_type &alloc = allocator_type()) : tree_(comp, alloc) {} - btree_container(const btree_container &other) = default; - btree_container(btree_container &&other) noexcept = default; + explicit btree_container(const allocator_type &alloc) + : tree_(key_compare(), alloc) {} + + btree_container(const btree_container &other) + : btree_container(other, absl::allocator_traits:: + select_on_container_copy_construction( + other.get_allocator())) {} + btree_container(const btree_container &other, const allocator_type &alloc) + : tree_(other.tree_, alloc) {} + + btree_container(btree_container &&other) noexcept( + std::is_nothrow_move_constructible::value) = default; + btree_container(btree_container &&other, const allocator_type &alloc) + : tree_(std::move(other.tree_), alloc) {} + btree_container &operator=(const btree_container &other) = default; btree_container &operator=(btree_container &&other) noexcept( std::is_nothrow_move_assignable::value) = default; @@ -90,6 +104,11 @@ class btree_container { // Lookup routines. template + size_type count(const key_arg &key) const { + auto equal_range = this->equal_range(key); + return std::distance(equal_range.first, equal_range.second); + } + template iterator find(const key_arg &key) { return tree_.find(key); } @@ -138,6 +157,11 @@ class btree_container { iterator erase(const_iterator first, const_iterator last) { return tree_.erase_range(iterator(first), iterator(last)).second; } + template + size_type erase(const key_arg &key) { + auto equal_range = this->equal_range(key); + return tree_.erase_range(equal_range.first, equal_range.second).first; + } // Extract routines. node_type extract(iterator position) { @@ -151,7 +175,6 @@ class btree_container { return extract(iterator(position)); } - public: // Utility routines. void clear() { tree_.clear(); } void swap(btree_container &other) { tree_.swap(other.tree_); } @@ -235,7 +258,7 @@ class btree_set_container : public btree_container { using super_type::super_type; btree_set_container() {} - // Range constructor. + // Range constructors. template btree_set_container(InputIterator b, InputIterator e, const key_compare &comp = key_compare(), @@ -243,18 +266,19 @@ class btree_set_container : public btree_container { : super_type(comp, alloc) { insert(b, e); } + template + btree_set_container(InputIterator b, InputIterator e, + const allocator_type &alloc) + : btree_set_container(b, e, key_compare(), alloc) {} - // Initializer list constructor. + // Initializer list constructors. btree_set_container(std::initializer_list init, const key_compare &comp = key_compare(), const allocator_type &alloc = allocator_type()) : btree_set_container(init.begin(), init.end(), comp, alloc) {} - - // Lookup routines. - template - size_type count(const key_arg &key) const { - return this->tree_.count_unique(key); - } + btree_set_container(std::initializer_list init, + const allocator_type &alloc) + : btree_set_container(init.begin(), init.end(), alloc) {} // Insertion routines. std::pair insert(const value_type &v) { @@ -268,31 +292,29 @@ class btree_set_container : public btree_container { init_type v(std::forward(args)...); return this->tree_.insert_unique(params_type::key(v), std::move(v)); } - iterator insert(const_iterator position, const value_type &v) { + iterator insert(const_iterator hint, const value_type &v) { return this->tree_ - .insert_hint_unique(iterator(position), params_type::key(v), v) + .insert_hint_unique(iterator(hint), params_type::key(v), v) .first; } - iterator insert(const_iterator position, value_type &&v) { + iterator insert(const_iterator hint, value_type &&v) { return this->tree_ - .insert_hint_unique(iterator(position), params_type::key(v), - std::move(v)) + .insert_hint_unique(iterator(hint), params_type::key(v), std::move(v)) .first; } template - iterator emplace_hint(const_iterator position, Args &&... args) { + iterator emplace_hint(const_iterator hint, Args &&... args) { init_type v(std::forward(args)...); return this->tree_ - .insert_hint_unique(iterator(position), params_type::key(v), - std::move(v)) + .insert_hint_unique(iterator(hint), params_type::key(v), std::move(v)) .first; } template void insert(InputIterator b, InputIterator e) { - this->tree_.insert_iterator_unique(b, e); + this->tree_.insert_iterator_unique(b, e, 0); } void insert(std::initializer_list init) { - this->tree_.insert_iterator_unique(init.begin(), init.end()); + this->tree_.insert_iterator_unique(init.begin(), init.end(), 0); } insert_return_type insert(node_type &&node) { if (!node) return {this->end(), false, node_type()}; @@ -315,14 +337,10 @@ class btree_set_container : public btree_container { return res.first; } - // Deletion routines. - template - size_type erase(const key_arg &key) { - return this->tree_.erase_unique(key); - } - using super_type::erase; - // Node extraction routines. + // TODO(ezb): when the comparator is heterogeneous and has different + // equivalence classes for different lookup types, we should extract the first + // equivalent value if there are multiple. template node_type extract(const key_arg &key) { auto it = this->find(key); @@ -344,7 +362,7 @@ class btree_set_container : public btree_container { int> = 0> void merge(btree_container &src) { // NOLINT for (auto src_it = src.begin(); src_it != src.end();) { - if (insert(std::move(*src_it)).second) { + if (insert(std::move(params_type::element(src_it.slot()))).second) { src_it = src.erase(src_it); } else { ++src_it; @@ -371,6 +389,7 @@ template class btree_map_container : public btree_set_container { using super_type = btree_set_container; using params_type = typename Tree::params_type; + friend class BtreeNodePeer; private: template @@ -392,111 +411,72 @@ class btree_map_container : public btree_set_container { // Insertion routines. // Note: the nullptr template arguments and extra `const M&` overloads allow // for supporting bitfield arguments. - // Note: when we call `std::forward(obj)` twice, it's safe because - // insert_unique/insert_hint_unique are guaranteed to not consume `obj` when - // `ret.second` is false. - template - std::pair insert_or_assign(const key_type &k, const M &obj) { - const std::pair ret = this->tree_.insert_unique(k, k, obj); - if (!ret.second) ret.first->second = obj; - return ret; + template + std::pair insert_or_assign(const key_arg &k, + const M &obj) { + return insert_or_assign_impl(k, obj); } - template - std::pair insert_or_assign(key_type &&k, const M &obj) { - const std::pair ret = - this->tree_.insert_unique(k, std::move(k), obj); - if (!ret.second) ret.first->second = obj; - return ret; + template + std::pair insert_or_assign(key_arg &&k, const M &obj) { + return insert_or_assign_impl(std::forward(k), obj); } - template - std::pair insert_or_assign(const key_type &k, M &&obj) { - const std::pair ret = - this->tree_.insert_unique(k, k, std::forward(obj)); - if (!ret.second) ret.first->second = std::forward(obj); - return ret; + template + std::pair insert_or_assign(const key_arg &k, M &&obj) { + return insert_or_assign_impl(k, std::forward(obj)); } - template - std::pair insert_or_assign(key_type &&k, M &&obj) { - const std::pair ret = - this->tree_.insert_unique(k, std::move(k), std::forward(obj)); - if (!ret.second) ret.first->second = std::forward(obj); - return ret; + template + std::pair insert_or_assign(key_arg &&k, M &&obj) { + return insert_or_assign_impl(std::forward(k), std::forward(obj)); } - template - iterator insert_or_assign(const_iterator position, const key_type &k, + template + iterator insert_or_assign(const_iterator hint, const key_arg &k, const M &obj) { - const std::pair ret = - this->tree_.insert_hint_unique(iterator(position), k, k, obj); - if (!ret.second) ret.first->second = obj; - return ret.first; + return insert_or_assign_hint_impl(hint, k, obj); } - template - iterator insert_or_assign(const_iterator position, key_type &&k, - const M &obj) { - const std::pair ret = this->tree_.insert_hint_unique( - iterator(position), k, std::move(k), obj); - if (!ret.second) ret.first->second = obj; - return ret.first; + template + iterator insert_or_assign(const_iterator hint, key_arg &&k, const M &obj) { + return insert_or_assign_hint_impl(hint, std::forward(k), obj); } - template - iterator insert_or_assign(const_iterator position, const key_type &k, - M &&obj) { - const std::pair ret = this->tree_.insert_hint_unique( - iterator(position), k, k, std::forward(obj)); - if (!ret.second) ret.first->second = std::forward(obj); - return ret.first; + template + iterator insert_or_assign(const_iterator hint, const key_arg &k, M &&obj) { + return insert_or_assign_hint_impl(hint, k, std::forward(obj)); } - template - iterator insert_or_assign(const_iterator position, key_type &&k, M &&obj) { - const std::pair ret = this->tree_.insert_hint_unique( - iterator(position), k, std::move(k), std::forward(obj)); - if (!ret.second) ret.first->second = std::forward(obj); - return ret.first; + template + iterator insert_or_assign(const_iterator hint, key_arg &&k, M &&obj) { + return insert_or_assign_hint_impl(hint, std::forward(k), + std::forward(obj)); } - template - std::pair try_emplace(const key_type &k, Args &&... args) { - return this->tree_.insert_unique( - k, std::piecewise_construct, std::forward_as_tuple(k), - std::forward_as_tuple(std::forward(args)...)); + + template ::value, int> = 0> + std::pair try_emplace(const key_arg &k, Args &&... args) { + return try_emplace_impl(k, std::forward(args)...); } - template - std::pair try_emplace(key_type &&k, Args &&... args) { - // Note: `key_ref` exists to avoid a ClangTidy warning about moving from `k` - // and then using `k` unsequenced. This is safe because the move is into a - // forwarding reference and insert_unique guarantees that `key` is never - // referenced after consuming `args`. - const key_type &key_ref = k; - return this->tree_.insert_unique( - key_ref, std::piecewise_construct, std::forward_as_tuple(std::move(k)), - std::forward_as_tuple(std::forward(args)...)); + template ::value, int> = 0> + std::pair try_emplace(key_arg &&k, Args &&... args) { + return try_emplace_impl(std::forward(k), std::forward(args)...); } - template - iterator try_emplace(const_iterator hint, const key_type &k, + template + iterator try_emplace(const_iterator hint, const key_arg &k, Args &&... args) { - return this->tree_ - .insert_hint_unique(iterator(hint), k, std::piecewise_construct, - std::forward_as_tuple(k), - std::forward_as_tuple(std::forward(args)...)) - .first; + return try_emplace_hint_impl(hint, k, std::forward(args)...); } - template - iterator try_emplace(const_iterator hint, key_type &&k, Args &&... args) { - // Note: `key_ref` exists to avoid a ClangTidy warning about moving from `k` - // and then using `k` unsequenced. This is safe because the move is into a - // forwarding reference and insert_hint_unique guarantees that `key` is - // never referenced after consuming `args`. - const key_type &key_ref = k; - return this->tree_ - .insert_hint_unique(iterator(hint), key_ref, std::piecewise_construct, - std::forward_as_tuple(std::move(k)), - std::forward_as_tuple(std::forward(args)...)) - .first; + template + iterator try_emplace(const_iterator hint, key_arg &&k, Args &&... args) { + return try_emplace_hint_impl(hint, std::forward(k), + std::forward(args)...); } - mapped_type &operator[](const key_type &k) { + + template + mapped_type &operator[](const key_arg &k) { return try_emplace(k).first->second; } - mapped_type &operator[](key_type &&k) { - return try_emplace(std::move(k)).first->second; + template + mapped_type &operator[](key_arg &&k) { + return try_emplace(std::forward(k)).first->second; } template @@ -513,6 +493,40 @@ class btree_map_container : public btree_set_container { base_internal::ThrowStdOutOfRange("absl::btree_map::at"); return it->second; } + + private: + // Note: when we call `std::forward(obj)` twice, it's safe because + // insert_unique/insert_hint_unique are guaranteed to not consume `obj` when + // `ret.second` is false. + template + std::pair insert_or_assign_impl(K &&k, M &&obj) { + const std::pair ret = + this->tree_.insert_unique(k, std::forward(k), std::forward(obj)); + if (!ret.second) ret.first->second = std::forward(obj); + return ret; + } + template + iterator insert_or_assign_hint_impl(const_iterator hint, K &&k, M &&obj) { + const std::pair ret = this->tree_.insert_hint_unique( + iterator(hint), k, std::forward(k), std::forward(obj)); + if (!ret.second) ret.first->second = std::forward(obj); + return ret.first; + } + + template + std::pair try_emplace_impl(K &&k, Args &&... args) { + return this->tree_.insert_unique( + k, std::piecewise_construct, std::forward_as_tuple(std::forward(k)), + std::forward_as_tuple(std::forward(args)...)); + } + template + iterator try_emplace_hint_impl(const_iterator hint, K &&k, Args &&... args) { + return this->tree_ + .insert_hint_unique(iterator(hint), k, std::piecewise_construct, + std::forward_as_tuple(std::forward(k)), + std::forward_as_tuple(std::forward(args)...)) + .first; + } }; // A common base class for btree_multiset and btree_multimap. @@ -540,7 +554,7 @@ class btree_multiset_container : public btree_container { using super_type::super_type; btree_multiset_container() {} - // Range constructor. + // Range constructors. template btree_multiset_container(InputIterator b, InputIterator e, const key_compare &comp = key_compare(), @@ -548,29 +562,30 @@ class btree_multiset_container : public btree_container { : super_type(comp, alloc) { insert(b, e); } + template + btree_multiset_container(InputIterator b, InputIterator e, + const allocator_type &alloc) + : btree_multiset_container(b, e, key_compare(), alloc) {} - // Initializer list constructor. + // Initializer list constructors. btree_multiset_container(std::initializer_list init, const key_compare &comp = key_compare(), const allocator_type &alloc = allocator_type()) : btree_multiset_container(init.begin(), init.end(), comp, alloc) {} - - // Lookup routines. - template - size_type count(const key_arg &key) const { - return this->tree_.count_multi(key); - } + btree_multiset_container(std::initializer_list init, + const allocator_type &alloc) + : btree_multiset_container(init.begin(), init.end(), alloc) {} // Insertion routines. iterator insert(const value_type &v) { return this->tree_.insert_multi(v); } iterator insert(value_type &&v) { return this->tree_.insert_multi(std::move(v)); } - iterator insert(const_iterator position, const value_type &v) { - return this->tree_.insert_hint_multi(iterator(position), v); + iterator insert(const_iterator hint, const value_type &v) { + return this->tree_.insert_hint_multi(iterator(hint), v); } - iterator insert(const_iterator position, value_type &&v) { - return this->tree_.insert_hint_multi(iterator(position), std::move(v)); + iterator insert(const_iterator hint, value_type &&v) { + return this->tree_.insert_hint_multi(iterator(hint), std::move(v)); } template void insert(InputIterator b, InputIterator e) { @@ -584,9 +599,9 @@ class btree_multiset_container : public btree_container { return this->tree_.insert_multi(init_type(std::forward(args)...)); } template - iterator emplace_hint(const_iterator position, Args &&... args) { + iterator emplace_hint(const_iterator hint, Args &&... args) { return this->tree_.insert_hint_multi( - iterator(position), init_type(std::forward(args)...)); + iterator(hint), init_type(std::forward(args)...)); } iterator insert(node_type &&node) { if (!node) return this->end(); @@ -605,14 +620,9 @@ class btree_multiset_container : public btree_container { return res; } - // Deletion routines. - template - size_type erase(const key_arg &key) { - return this->tree_.erase_multi(key); - } - using super_type::erase; - // Node extraction routines. + // TODO(ezb): we are supposed to extract the first equivalent key if there are + // multiple, but this isn't guaranteed to extract the first one. template node_type extract(const key_arg &key) { auto it = this->find(key); @@ -632,8 +642,9 @@ class btree_multiset_container : public btree_container { typename T::params_type::is_map_container>>::value, int> = 0> void merge(btree_container &src) { // NOLINT - insert(std::make_move_iterator(src.begin()), - std::make_move_iterator(src.end())); + for (auto src_it = src.begin(), end = src.end(); src_it != end; ++src_it) { + insert(std::move(params_type::element(src_it.slot()))); + } src.clear(); } -- cgit 1.4.1