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 | 683 |
1 files changed, 683 insertions, 0 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 new file mode 100644 index 000000000000..887eda4122f8 --- /dev/null +++ b/third_party/abseil_cpp/absl/container/internal/btree_container.h @@ -0,0 +1,683 @@ +// Copyright 2018 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#ifndef ABSL_CONTAINER_INTERNAL_BTREE_CONTAINER_H_ +#define ABSL_CONTAINER_INTERNAL_BTREE_CONTAINER_H_ + +#include <algorithm> +#include <initializer_list> +#include <iterator> +#include <utility> + +#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 { +ABSL_NAMESPACE_BEGIN +namespace container_internal { + +// A common base class for btree_set, btree_map, btree_multiset, and +// btree_multimap. +template <typename Tree> +class btree_container { + using params_type = typename Tree::params_type; + + protected: + // Alias used for heterogeneous lookup functions. + // `key_arg<K>` evaluates to `K` when the functors are transparent and to + // `key_type` otherwise. It permits template argument deduction on `K` for the + // transparent case. + template <class K> + using key_arg = + typename KeyArg<IsTransparent<typename Tree::key_compare>::value>:: + template type<K, typename Tree::key_type>; + + public: + using key_type = typename Tree::key_type; + 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::key_compare; + using value_compare = typename Tree::value_compare; + using allocator_type = typename Tree::allocator_type; + using reference = typename Tree::reference; + using const_reference = typename Tree::const_reference; + using pointer = typename Tree::pointer; + using const_pointer = typename Tree::const_pointer; + using iterator = typename Tree::iterator; + using const_iterator = typename Tree::const_iterator; + using reverse_iterator = typename Tree::reverse_iterator; + using const_reverse_iterator = typename Tree::const_reverse_iterator; + using node_type = typename Tree::node_handle_type; + + // Constructors/assignments. + btree_container() : tree_(key_compare(), allocator_type()) {} + 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( + std::is_nothrow_move_assignable<Tree>::value) = default; + + // Iterator routines. + iterator begin() { return tree_.begin(); } + const_iterator begin() const { return tree_.begin(); } + const_iterator cbegin() const { return tree_.begin(); } + iterator end() { return tree_.end(); } + const_iterator end() const { return tree_.end(); } + const_iterator cend() const { return tree_.end(); } + reverse_iterator rbegin() { return tree_.rbegin(); } + const_reverse_iterator rbegin() const { return tree_.rbegin(); } + const_reverse_iterator crbegin() const { return tree_.rbegin(); } + reverse_iterator rend() { return tree_.rend(); } + const_reverse_iterator rend() const { return tree_.rend(); } + const_reverse_iterator crend() const { return tree_.rend(); } + + // 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); + } + template <typename K = key_type> + const_iterator find(const key_arg<K> &key) const { + return tree_.find(key); + } + template <typename K = key_type> + bool contains(const key_arg<K> &key) const { + return find(key) != end(); + } + template <typename K = key_type> + iterator lower_bound(const key_arg<K> &key) { + return tree_.lower_bound(key); + } + template <typename K = key_type> + const_iterator lower_bound(const key_arg<K> &key) const { + return tree_.lower_bound(key); + } + template <typename K = key_type> + iterator upper_bound(const key_arg<K> &key) { + return tree_.upper_bound(key); + } + template <typename K = key_type> + const_iterator upper_bound(const key_arg<K> &key) const { + return tree_.upper_bound(key); + } + template <typename K = key_type> + std::pair<iterator, iterator> equal_range(const key_arg<K> &key) { + return tree_.equal_range(key); + } + template <typename K = key_type> + std::pair<const_iterator, const_iterator> equal_range( + const key_arg<K> &key) const { + return tree_.equal_range(key); + } + + // Deletion routines. Note that there is also a deletion routine that is + // specific to btree_set_container/btree_multiset_container. + + // Erase the specified iterator from the btree. The iterator must be valid + // (i.e. not equal to end()). Return an iterator pointing to the node after + // the one that was erased (or end() if none exists). + iterator erase(const_iterator iter) { return tree_.erase(iterator(iter)); } + iterator erase(iterator iter) { return tree_.erase(iter); } + 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) { + // Use Move instead of Transfer, because the rebalancing code expects to + // have a valid object to scribble metadata bits on top of. + auto node = CommonAccess::Move<node_type>(get_allocator(), position.slot()); + erase(position); + return node; + } + node_type extract(const_iterator position) { + return extract(iterator(position)); + } + + // Utility routines. + void clear() { tree_.clear(); } + void swap(btree_container &other) { tree_.swap(other.tree_); } + void verify() const { tree_.verify(); } + + // Size routines. + size_type size() const { return tree_.size(); } + size_type max_size() const { return tree_.max_size(); } + bool empty() const { return tree_.empty(); } + + friend bool operator==(const btree_container &x, const btree_container &y) { + if (x.size() != y.size()) return false; + return std::equal(x.begin(), x.end(), y.begin()); + } + + friend bool operator!=(const btree_container &x, const btree_container &y) { + return !(x == y); + } + + friend bool operator<(const btree_container &x, const btree_container &y) { + return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); + } + + friend bool operator>(const btree_container &x, const btree_container &y) { + return y < x; + } + + friend bool operator<=(const btree_container &x, const btree_container &y) { + return !(y < x); + } + + friend bool operator>=(const btree_container &x, const btree_container &y) { + return !(x < y); + } + + // The allocator used by the btree. + allocator_type get_allocator() const { return tree_.get_allocator(); } + + // The key comparator used by the btree. + key_compare key_comp() const { return tree_.key_comp(); } + value_compare value_comp() const { return tree_.value_comp(); } + + // Support absl::Hash. + template <typename State> + friend State AbslHashValue(State h, const btree_container &b) { + for (const auto &v : b) { + h = State::combine(std::move(h), v); + } + return State::combine(std::move(h), b.size()); + } + + protected: + Tree tree_; +}; + +// A common base class for btree_set and btree_map. +template <typename Tree> +class btree_set_container : public btree_container<Tree> { + using super_type = btree_container<Tree>; + using params_type = typename Tree::params_type; + using init_type = typename params_type::init_type; + using is_key_compare_to = typename params_type::is_key_compare_to; + friend class BtreeNodePeer; + + protected: + template <class K> + using key_arg = typename super_type::template key_arg<K>; + + public: + 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::key_compare; + using allocator_type = typename Tree::allocator_type; + using iterator = typename Tree::iterator; + using const_iterator = typename Tree::const_iterator; + using node_type = typename super_type::node_type; + using insert_return_type = InsertReturnType<iterator, node_type>; + + // Inherit constructors. + using super_type::super_type; + btree_set_container() {} + + // Range constructors. + template <class InputIterator> + btree_set_container(InputIterator b, InputIterator e, + const key_compare &comp = key_compare(), + const allocator_type &alloc = allocator_type()) + : 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. + 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) {} + + // 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(value_type &&v) { + return this->tree_.insert_unique(params_type::key(v), std::move(v)); + } + 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) { + return this->tree_ + .insert_hint_unique(iterator(hint), params_type::key(v), v) + .first; + } + iterator insert(const_iterator hint, value_type &&v) { + return this->tree_ + .insert_hint_unique(iterator(hint), params_type::key(v), std::move(v)) + .first; + } + template <typename... Args> + iterator emplace_hint(const_iterator hint, Args &&... args) { + init_type v(std::forward<Args>(args)...); + return this->tree_ + .insert_hint_unique(iterator(hint), 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); + } + void insert(std::initializer_list<init_type> init) { + 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()}; + std::pair<iterator, bool> res = + this->tree_.insert_unique(params_type::key(CommonAccess::GetSlot(node)), + CommonAccess::GetSlot(node)); + if (res.second) { + CommonAccess::Destroy(&node); + return {res.first, true, node_type()}; + } else { + return {res.first, false, std::move(node)}; + } + } + iterator insert(const_iterator hint, node_type &&node) { + if (!node) return this->end(); + std::pair<iterator, bool> res = this->tree_.insert_hint_unique( + iterator(hint), params_type::key(CommonAccess::GetSlot(node)), + CommonAccess::GetSlot(node)); + if (res.second) CommonAccess::Destroy(&node); + return res.first; + } + + // 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 <typename K = key_type> + node_type extract(const key_arg<K> &key) { + auto it = this->find(key); + return it == this->end() ? node_type() : extract(it); + } + using super_type::extract; + + // Merge routines. + // Moves elements from `src` into `this`. If the element already exists in + // `this`, it is left unmodified in `src`. + template < + typename T, + typename absl::enable_if_t< + absl::conjunction< + std::is_same<value_type, typename T::value_type>, + std::is_same<allocator_type, typename T::allocator_type>, + std::is_same<typename params_type::is_map_container, + typename T::params_type::is_map_container>>::value, + 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) { + src_it = src.erase(src_it); + } else { + ++src_it; + } + } + } + + template < + typename T, + typename absl::enable_if_t< + absl::conjunction< + std::is_same<value_type, typename T::value_type>, + std::is_same<allocator_type, typename T::allocator_type>, + std::is_same<typename params_type::is_map_container, + typename T::params_type::is_map_container>>::value, + int> = 0> + void merge(btree_container<T> &&src) { + merge(src); + } +}; + +// Base class for btree_map. +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> + using key_arg = typename super_type::template key_arg<K>; + + public: + 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::key_compare; + using allocator_type = typename Tree::allocator_type; + using iterator = typename Tree::iterator; + using const_iterator = typename Tree::const_iterator; + + // Inherit constructors. + using super_type::super_type; + btree_map_container() {} + + // 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); + } + 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 <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 <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 <typename K = key_type, class M> + iterator insert_or_assign(const_iterator hint, const key_arg<K> &k, + const M &obj) { + return insert_or_assign_hint_impl(hint, k, obj); + } + 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 <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 <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 <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 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 K = key_type, typename... Args> + iterator try_emplace(const_iterator hint, const key_arg<K> &k, + Args &&... args) { + return try_emplace_hint_impl(hint, k, std::forward<Args>(args)...); + } + 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 K = key_type> + mapped_type &operator[](const key_arg<K> &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; + } + + template <typename K = key_type> + mapped_type &at(const key_arg<K> &key) { + auto it = this->find(key); + if (it == this->end()) + base_internal::ThrowStdOutOfRange("absl::btree_map::at"); + return it->second; + } + template <typename K = key_type> + const mapped_type &at(const key_arg<K> &key) const { + auto it = this->find(key); + if (it == this->end()) + 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. +template <typename Tree> +class btree_multiset_container : public btree_container<Tree> { + using super_type = btree_container<Tree>; + using params_type = typename Tree::params_type; + using init_type = typename params_type::init_type; + using is_key_compare_to = typename params_type::is_key_compare_to; + + template <class K> + using key_arg = typename super_type::template key_arg<K>; + + public: + 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::key_compare; + using allocator_type = typename Tree::allocator_type; + using iterator = typename Tree::iterator; + using const_iterator = typename Tree::const_iterator; + using node_type = typename super_type::node_type; + + // Inherit constructors. + using super_type::super_type; + btree_multiset_container() {} + + // Range constructors. + template <class InputIterator> + btree_multiset_container(InputIterator b, InputIterator e, + const key_compare &comp = key_compare(), + const allocator_type &alloc = allocator_type()) + : 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. + 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) {} + + // 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 hint, const value_type &v) { + return this->tree_.insert_hint_multi(iterator(hint), v); + } + iterator insert(const_iterator hint, value_type &&v) { + return this->tree_.insert_hint_multi(iterator(hint), std::move(v)); + } + template <typename InputIterator> + void insert(InputIterator b, InputIterator e) { + this->tree_.insert_iterator_multi(b, e); + } + void insert(std::initializer_list<init_type> init) { + this->tree_.insert_iterator_multi(init.begin(), init.end()); + } + template <typename... Args> + iterator emplace(Args &&... args) { + return this->tree_.insert_multi(init_type(std::forward<Args>(args)...)); + } + template <typename... Args> + iterator emplace_hint(const_iterator hint, Args &&... args) { + return this->tree_.insert_hint_multi( + iterator(hint), init_type(std::forward<Args>(args)...)); + } + iterator insert(node_type &&node) { + if (!node) return this->end(); + iterator res = + this->tree_.insert_multi(params_type::key(CommonAccess::GetSlot(node)), + CommonAccess::GetSlot(node)); + CommonAccess::Destroy(&node); + return res; + } + iterator insert(const_iterator hint, node_type &&node) { + if (!node) return this->end(); + iterator res = this->tree_.insert_hint_multi( + iterator(hint), + std::move(params_type::element(CommonAccess::GetSlot(node)))); + CommonAccess::Destroy(&node); + return res; + } + + // 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 <typename K = key_type> + node_type extract(const key_arg<K> &key) { + auto it = this->find(key); + return it == this->end() ? node_type() : extract(it); + } + using super_type::extract; + + // Merge routines. + // Moves all elements from `src` into `this`. + template < + typename T, + typename absl::enable_if_t< + absl::conjunction< + std::is_same<value_type, typename T::value_type>, + std::is_same<allocator_type, typename T::allocator_type>, + std::is_same<typename params_type::is_map_container, + 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()))); + } + src.clear(); + } + + template < + typename T, + typename absl::enable_if_t< + absl::conjunction< + std::is_same<value_type, typename T::value_type>, + std::is_same<allocator_type, typename T::allocator_type>, + std::is_same<typename params_type::is_map_container, + typename T::params_type::is_map_container>>::value, + int> = 0> + void merge(btree_container<T> &&src) { + merge(src); + } +}; + +// A base class for btree_multimap. +template <typename Tree> +class btree_multimap_container : public btree_multiset_container<Tree> { + using super_type = btree_multiset_container<Tree>; + using params_type = typename Tree::params_type; + + public: + using mapped_type = typename params_type::mapped_type; + + // Inherit constructors. + using super_type::super_type; + btree_multimap_container() {} +}; + +} // namespace container_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_CONTAINER_INTERNAL_BTREE_CONTAINER_H_ |