diff options
Diffstat (limited to 'third_party/abseil-cpp/absl/container/internal/btree_container.h')
| -rw-r--r-- | third_party/abseil-cpp/absl/container/internal/btree_container.h | 333 |
1 files changed, 161 insertions, 172 deletions
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 a99668c713..f2e4c3a535 100644 --- a/third_party/abseil-cpp/absl/container/internal/btree_container.h +++ b/third_party/abseil-cpp/absl/container/internal/btree_container.h @@ -20,11 +20,9 @@ #include <iterator> #include <utility> -#include "absl/base/attributes.h" #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 { @@ -52,7 +50,7 @@ class btree_container { using value_type = typename Tree::value_type; using size_type = typename Tree::size_type; using difference_type = typename Tree::difference_type; - using key_compare = typename Tree::original_key_compare; + using key_compare = typename Tree::key_compare; using value_compare = typename Tree::value_compare; using allocator_type = typename Tree::allocator_type; using reference = typename Tree::reference; @@ -70,23 +68,10 @@ class btree_container { explicit btree_container(const key_compare &comp, const allocator_type &alloc = allocator_type()) : tree_(comp, alloc) {} - explicit btree_container(const allocator_type &alloc) - : tree_(key_compare(), alloc) {} - - btree_container(const btree_container &other) - : btree_container(other, absl::allocator_traits<allocator_type>:: - 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<Tree>::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( + btree_container(const btree_container &x) = default; + btree_container(btree_container &&x) noexcept = default; + btree_container &operator=(const btree_container &x) = default; + btree_container &operator=(btree_container &&x) noexcept( std::is_nothrow_move_assignable<Tree>::value) = default; // Iterator routines. @@ -105,11 +90,6 @@ class btree_container { // Lookup routines. template <typename K = key_type> - size_type count(const key_arg<K> &key) const { - auto equal_range = this->equal_range(key); - return std::distance(equal_range.first, equal_range.second); - } - template <typename K = key_type> iterator find(const key_arg<K> &key) { return tree_.find(key); } @@ -158,11 +138,6 @@ class btree_container { iterator erase(const_iterator first, const_iterator last) { return tree_.erase_range(iterator(first), iterator(last)).second; } - template <typename K = key_type> - size_type erase(const key_arg<K> &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) { @@ -176,9 +151,10 @@ class btree_container { return extract(iterator(position)); } + public: // Utility routines. - ABSL_ATTRIBUTE_REINITIALIZES void clear() { tree_.clear(); } - void swap(btree_container &other) { tree_.swap(other.tree_); } + void clear() { tree_.clear(); } + void swap(btree_container &x) { tree_.swap(x.tree_); } void verify() const { tree_.verify(); } // Size routines. @@ -215,7 +191,7 @@ class btree_container { allocator_type get_allocator() const { return tree_.get_allocator(); } // The key comparator used by the btree. - key_compare key_comp() const { return key_compare(tree_.key_comp()); } + key_compare key_comp() const { return tree_.key_comp(); } value_compare value_comp() const { return tree_.value_comp(); } // Support absl::Hash. @@ -248,7 +224,7 @@ class btree_set_container : public btree_container<Tree> { using key_type = typename Tree::key_type; using value_type = typename Tree::value_type; using size_type = typename Tree::size_type; - using key_compare = typename Tree::original_key_compare; + using key_compare = typename Tree::key_compare; using allocator_type = typename Tree::allocator_type; using iterator = typename Tree::iterator; using const_iterator = typename Tree::const_iterator; @@ -259,7 +235,7 @@ class btree_set_container : public btree_container<Tree> { using super_type::super_type; btree_set_container() {} - // Range constructors. + // Range constructor. template <class InputIterator> btree_set_container(InputIterator b, InputIterator e, const key_compare &comp = key_compare(), @@ -267,55 +243,56 @@ class btree_set_container : public btree_container<Tree> { : super_type(comp, alloc) { insert(b, e); } - template <class InputIterator> - btree_set_container(InputIterator b, InputIterator e, - const allocator_type &alloc) - : btree_set_container(b, e, key_compare(), alloc) {} - // Initializer list constructors. + // Initializer list constructor. btree_set_container(std::initializer_list<init_type> init, const key_compare &comp = key_compare(), const allocator_type &alloc = allocator_type()) : btree_set_container(init.begin(), init.end(), comp, alloc) {} - btree_set_container(std::initializer_list<init_type> init, - const allocator_type &alloc) - : btree_set_container(init.begin(), init.end(), alloc) {} + + // Lookup routines. + template <typename K = key_type> + size_type count(const key_arg<K> &key) const { + return this->tree_.count_unique(key); + } // Insertion routines. - std::pair<iterator, bool> insert(const value_type &v) { - return this->tree_.insert_unique(params_type::key(v), v); + std::pair<iterator, bool> insert(const value_type &x) { + return this->tree_.insert_unique(params_type::key(x), x); } - std::pair<iterator, bool> insert(value_type &&v) { - return this->tree_.insert_unique(params_type::key(v), std::move(v)); + std::pair<iterator, bool> insert(value_type &&x) { + return this->tree_.insert_unique(params_type::key(x), std::move(x)); } template <typename... Args> std::pair<iterator, bool> emplace(Args &&... args) { init_type v(std::forward<Args>(args)...); return this->tree_.insert_unique(params_type::key(v), std::move(v)); } - iterator insert(const_iterator hint, const value_type &v) { + iterator insert(const_iterator position, const value_type &x) { return this->tree_ - .insert_hint_unique(iterator(hint), params_type::key(v), v) + .insert_hint_unique(iterator(position), params_type::key(x), x) .first; } - iterator insert(const_iterator hint, value_type &&v) { + iterator insert(const_iterator position, value_type &&x) { return this->tree_ - .insert_hint_unique(iterator(hint), params_type::key(v), std::move(v)) + .insert_hint_unique(iterator(position), params_type::key(x), + std::move(x)) .first; } template <typename... Args> - iterator emplace_hint(const_iterator hint, Args &&... args) { + iterator emplace_hint(const_iterator position, Args &&... args) { init_type v(std::forward<Args>(args)...); return this->tree_ - .insert_hint_unique(iterator(hint), params_type::key(v), std::move(v)) + .insert_hint_unique(iterator(position), params_type::key(v), + std::move(v)) .first; } template <typename InputIterator> void insert(InputIterator b, InputIterator e) { - this->tree_.insert_iterator_unique(b, e, 0); + this->tree_.insert_iterator_unique(b, e); } void insert(std::initializer_list<init_type> init) { - this->tree_.insert_iterator_unique(init.begin(), init.end(), 0); + this->tree_.insert_iterator_unique(init.begin(), init.end()); } insert_return_type insert(node_type &&node) { if (!node) return {this->end(), false, node_type()}; @@ -338,13 +315,18 @@ class btree_set_container : public btree_container<Tree> { return res.first; } + // Deletion routines. + template <typename K = key_type> + size_type erase(const key_arg<K> &key) { + return this->tree_.erase_unique(key); + } + using super_type::erase; + // Node extraction routines. template <typename K = key_type> node_type extract(const key_arg<K> &key) { - const std::pair<iterator, bool> lower_and_equal = - this->tree_.lower_bound_equal(key); - return lower_and_equal.second ? extract(lower_and_equal.first) - : node_type(); + auto it = this->find(key); + return it == this->end() ? node_type() : extract(it); } using super_type::extract; @@ -362,7 +344,7 @@ class btree_set_container : public btree_container<Tree> { int> = 0> void merge(btree_container<T> &src) { // NOLINT for (auto src_it = src.begin(); src_it != src.end();) { - if (insert(std::move(params_type::element(src_it.slot()))).second) { + if (insert(std::move(*src_it)).second) { src_it = src.erase(src_it); } else { ++src_it; @@ -389,7 +371,6 @@ template <typename Tree> class btree_map_container : public btree_set_container<Tree> { using super_type = btree_set_container<Tree>; using params_type = typename Tree::params_type; - friend class BtreeNodePeer; private: template <class K> @@ -399,7 +380,7 @@ class btree_map_container : public btree_set_container<Tree> { using key_type = typename Tree::key_type; using mapped_type = typename params_type::mapped_type; using value_type = typename Tree::value_type; - using key_compare = typename Tree::original_key_compare; + using key_compare = typename Tree::key_compare; using allocator_type = typename Tree::allocator_type; using iterator = typename Tree::iterator; using const_iterator = typename Tree::const_iterator; @@ -411,72 +392,111 @@ class btree_map_container : public btree_set_container<Tree> { // Insertion routines. // Note: the nullptr template arguments and extra `const M&` overloads allow // for supporting bitfield arguments. - template <typename K = key_type, class M> - std::pair<iterator, bool> insert_or_assign(const key_arg<K> &k, - const M &obj) { - return insert_or_assign_impl(k, obj); + // Note: when we call `std::forward<M>(obj)` twice, it's safe because + // insert_unique/insert_hint_unique are guaranteed to not consume `obj` when + // `ret.second` is false. + template <class M> + std::pair<iterator, bool> insert_or_assign(const key_type &k, const M &obj) { + const std::pair<iterator, bool> ret = this->tree_.insert_unique(k, k, obj); + if (!ret.second) ret.first->second = obj; + return ret; } - template <typename K = key_type, class M, K * = nullptr> - std::pair<iterator, bool> insert_or_assign(key_arg<K> &&k, const M &obj) { - return insert_or_assign_impl(std::forward<K>(k), obj); + template <class M, key_type * = nullptr> + std::pair<iterator, bool> insert_or_assign(key_type &&k, const M &obj) { + const std::pair<iterator, bool> ret = + this->tree_.insert_unique(k, std::move(k), obj); + if (!ret.second) ret.first->second = obj; + return ret; } - template <typename K = key_type, class M, M * = nullptr> - std::pair<iterator, bool> insert_or_assign(const key_arg<K> &k, M &&obj) { - return insert_or_assign_impl(k, std::forward<M>(obj)); + template <class M, M * = nullptr> + std::pair<iterator, bool> insert_or_assign(const key_type &k, M &&obj) { + const std::pair<iterator, bool> ret = + this->tree_.insert_unique(k, k, std::forward<M>(obj)); + if (!ret.second) ret.first->second = std::forward<M>(obj); + return ret; } - template <typename K = key_type, class M, K * = nullptr, M * = nullptr> - std::pair<iterator, bool> insert_or_assign(key_arg<K> &&k, M &&obj) { - return insert_or_assign_impl(std::forward<K>(k), std::forward<M>(obj)); + template <class M, key_type * = nullptr, M * = nullptr> + std::pair<iterator, bool> insert_or_assign(key_type &&k, M &&obj) { + const std::pair<iterator, bool> ret = + this->tree_.insert_unique(k, std::move(k), std::forward<M>(obj)); + if (!ret.second) ret.first->second = std::forward<M>(obj); + return ret; } - template <typename K = key_type, class M> - iterator insert_or_assign(const_iterator hint, const key_arg<K> &k, + template <class M> + iterator insert_or_assign(const_iterator position, const key_type &k, const M &obj) { - return insert_or_assign_hint_impl(hint, k, obj); + const std::pair<iterator, bool> ret = + this->tree_.insert_hint_unique(iterator(position), k, k, obj); + if (!ret.second) ret.first->second = obj; + return ret.first; } - template <typename K = key_type, class M, K * = nullptr> - iterator insert_or_assign(const_iterator hint, key_arg<K> &&k, const M &obj) { - return insert_or_assign_hint_impl(hint, std::forward<K>(k), obj); + template <class M, key_type * = nullptr> + iterator insert_or_assign(const_iterator position, key_type &&k, + const M &obj) { + const std::pair<iterator, bool> ret = this->tree_.insert_hint_unique( + iterator(position), k, std::move(k), obj); + if (!ret.second) ret.first->second = obj; + return ret.first; } - template <typename K = key_type, class M, M * = nullptr> - iterator insert_or_assign(const_iterator hint, const key_arg<K> &k, M &&obj) { - return insert_or_assign_hint_impl(hint, k, std::forward<M>(obj)); + template <class M, M * = nullptr> + iterator insert_or_assign(const_iterator position, const key_type &k, + M &&obj) { + const std::pair<iterator, bool> ret = this->tree_.insert_hint_unique( + iterator(position), k, k, std::forward<M>(obj)); + if (!ret.second) ret.first->second = std::forward<M>(obj); + return ret.first; } - template <typename K = key_type, class M, K * = nullptr, M * = nullptr> - iterator insert_or_assign(const_iterator hint, key_arg<K> &&k, M &&obj) { - return insert_or_assign_hint_impl(hint, std::forward<K>(k), - std::forward<M>(obj)); + template <class M, key_type * = nullptr, M * = nullptr> + iterator insert_or_assign(const_iterator position, key_type &&k, M &&obj) { + const std::pair<iterator, bool> ret = this->tree_.insert_hint_unique( + iterator(position), k, std::move(k), std::forward<M>(obj)); + if (!ret.second) ret.first->second = std::forward<M>(obj); + return ret.first; } - - template <typename K = key_type, typename... Args, - typename absl::enable_if_t< - !std::is_convertible<K, const_iterator>::value, int> = 0> - std::pair<iterator, bool> try_emplace(const key_arg<K> &k, Args &&... args) { - return try_emplace_impl(k, std::forward<Args>(args)...); + template <typename... Args> + std::pair<iterator, bool> 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>(args)...)); } - template <typename K = key_type, typename... Args, - typename absl::enable_if_t< - !std::is_convertible<K, const_iterator>::value, int> = 0> - std::pair<iterator, bool> try_emplace(key_arg<K> &&k, Args &&... args) { - return try_emplace_impl(std::forward<K>(k), std::forward<Args>(args)...); + template <typename... Args> + std::pair<iterator, bool> 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>(args)...)); } - template <typename K = key_type, typename... Args> - iterator try_emplace(const_iterator hint, const key_arg<K> &k, + template <typename... Args> + iterator try_emplace(const_iterator hint, const key_type &k, Args &&... args) { - return try_emplace_hint_impl(hint, k, std::forward<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>(args)...)) + .first; } - template <typename K = key_type, typename... Args> - iterator try_emplace(const_iterator hint, key_arg<K> &&k, Args &&... args) { - return try_emplace_hint_impl(hint, std::forward<K>(k), - std::forward<Args>(args)...); + template <typename... Args> + 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>(args)...)) + .first; } - - template <typename K = key_type> - mapped_type &operator[](const key_arg<K> &k) { + mapped_type &operator[](const key_type &k) { return try_emplace(k).first->second; } - template <typename K = key_type> - mapped_type &operator[](key_arg<K> &&k) { - return try_emplace(std::forward<K>(k)).first->second; + mapped_type &operator[](key_type &&k) { + return try_emplace(std::move(k)).first->second; } template <typename K = key_type> @@ -493,40 +513,6 @@ class btree_map_container : public btree_set_container<Tree> { base_internal::ThrowStdOutOfRange("absl::btree_map::at"); return it->second; } - - private: - // Note: when we call `std::forward<M>(obj)` twice, it's safe because - // insert_unique/insert_hint_unique are guaranteed to not consume `obj` when - // `ret.second` is false. - template <class K, class M> - std::pair<iterator, bool> insert_or_assign_impl(K &&k, M &&obj) { - const std::pair<iterator, bool> ret = - this->tree_.insert_unique(k, std::forward<K>(k), std::forward<M>(obj)); - if (!ret.second) ret.first->second = std::forward<M>(obj); - return ret; - } - template <class K, class M> - iterator insert_or_assign_hint_impl(const_iterator hint, K &&k, M &&obj) { - const std::pair<iterator, bool> ret = this->tree_.insert_hint_unique( - iterator(hint), k, std::forward<K>(k), std::forward<M>(obj)); - if (!ret.second) ret.first->second = std::forward<M>(obj); - return ret.first; - } - - template <class K, class... Args> - std::pair<iterator, bool> try_emplace_impl(K &&k, Args &&... args) { - return this->tree_.insert_unique( - k, std::piecewise_construct, std::forward_as_tuple(std::forward<K>(k)), - std::forward_as_tuple(std::forward<Args>(args)...)); - } - template <class K, class... Args> - 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>(k)), - std::forward_as_tuple(std::forward<Args>(args)...)) - .first; - } }; // A common base class for btree_multiset and btree_multimap. @@ -544,7 +530,7 @@ class btree_multiset_container : public btree_container<Tree> { using key_type = typename Tree::key_type; using value_type = typename Tree::value_type; using size_type = typename Tree::size_type; - using key_compare = typename Tree::original_key_compare; + using key_compare = typename Tree::key_compare; using allocator_type = typename Tree::allocator_type; using iterator = typename Tree::iterator; using const_iterator = typename Tree::const_iterator; @@ -554,7 +540,7 @@ class btree_multiset_container : public btree_container<Tree> { using super_type::super_type; btree_multiset_container() {} - // Range constructors. + // Range constructor. template <class InputIterator> btree_multiset_container(InputIterator b, InputIterator e, const key_compare &comp = key_compare(), @@ -562,30 +548,29 @@ class btree_multiset_container : public btree_container<Tree> { : super_type(comp, alloc) { insert(b, e); } - template <class InputIterator> - btree_multiset_container(InputIterator b, InputIterator e, - const allocator_type &alloc) - : btree_multiset_container(b, e, key_compare(), alloc) {} - // Initializer list constructors. + // Initializer list constructor. btree_multiset_container(std::initializer_list<init_type> init, const key_compare &comp = key_compare(), const allocator_type &alloc = allocator_type()) : btree_multiset_container(init.begin(), init.end(), comp, alloc) {} - btree_multiset_container(std::initializer_list<init_type> init, - const allocator_type &alloc) - : btree_multiset_container(init.begin(), init.end(), alloc) {} + + // Lookup routines. + template <typename K = key_type> + size_type count(const key_arg<K> &key) const { + return this->tree_.count_multi(key); + } // 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 value_type &x) { return this->tree_.insert_multi(x); } + iterator insert(value_type &&x) { + return this->tree_.insert_multi(std::move(x)); } - iterator insert(const_iterator hint, const value_type &v) { - return this->tree_.insert_hint_multi(iterator(hint), v); + iterator insert(const_iterator position, const value_type &x) { + return this->tree_.insert_hint_multi(iterator(position), x); } - iterator insert(const_iterator hint, value_type &&v) { - return this->tree_.insert_hint_multi(iterator(hint), std::move(v)); + iterator insert(const_iterator position, value_type &&x) { + return this->tree_.insert_hint_multi(iterator(position), std::move(x)); } template <typename InputIterator> void insert(InputIterator b, InputIterator e) { @@ -599,9 +584,9 @@ class btree_multiset_container : public btree_container<Tree> { return this->tree_.insert_multi(init_type(std::forward<Args>(args)...)); } template <typename... Args> - iterator emplace_hint(const_iterator hint, Args &&... args) { + iterator emplace_hint(const_iterator position, Args &&... args) { return this->tree_.insert_hint_multi( - iterator(hint), init_type(std::forward<Args>(args)...)); + iterator(position), init_type(std::forward<Args>(args)...)); } iterator insert(node_type &&node) { if (!node) return this->end(); @@ -620,13 +605,18 @@ class btree_multiset_container : public btree_container<Tree> { return res; } + // Deletion routines. + template <typename K = key_type> + size_type erase(const key_arg<K> &key) { + return this->tree_.erase_multi(key); + } + using super_type::erase; + // Node extraction routines. template <typename K = key_type> node_type extract(const key_arg<K> &key) { - const std::pair<iterator, bool> lower_and_equal = - this->tree_.lower_bound_equal(key); - return lower_and_equal.second ? extract(lower_and_equal.first) - : node_type(); + auto it = this->find(key); + return it == this->end() ? node_type() : extract(it); } using super_type::extract; @@ -642,9 +632,8 @@ class btree_multiset_container : public btree_container<Tree> { typename T::params_type::is_map_container>>::value, int> = 0> void merge(btree_container<T> &src) { // NOLINT - for (auto src_it = src.begin(), end = src.end(); src_it != end; ++src_it) { - insert(std::move(params_type::element(src_it.slot()))); - } + insert(std::make_move_iterator(src.begin()), + std::make_move_iterator(src.end())); src.clear(); } |