diff options
Diffstat (limited to 'libcxx/include/__tree')
| -rw-r--r-- | libcxx/include/__tree | 463 |
1 files changed, 194 insertions, 269 deletions
diff --git a/libcxx/include/__tree b/libcxx/include/__tree index 74b20d5..3ad2129 100644 --- a/libcxx/include/__tree +++ b/libcxx/include/__tree @@ -13,9 +13,7 @@ #include <__algorithm/min.h> #include <__assert> #include <__config> -#include <__fwd/map.h> #include <__fwd/pair.h> -#include <__fwd/set.h> #include <__iterator/distance.h> #include <__iterator/iterator_traits.h> #include <__iterator/next.h> @@ -25,23 +23,21 @@ #include <__memory/pointer_traits.h> #include <__memory/swap_allocator.h> #include <__memory/unique_ptr.h> -#include <__type_traits/can_extract_key.h> #include <__type_traits/copy_cvref.h> #include <__type_traits/enable_if.h> #include <__type_traits/invoke.h> -#include <__type_traits/is_const.h> #include <__type_traits/is_constructible.h> #include <__type_traits/is_nothrow_assignable.h> #include <__type_traits/is_nothrow_constructible.h> #include <__type_traits/is_same.h> +#include <__type_traits/is_specialization.h> #include <__type_traits/is_swappable.h> #include <__type_traits/remove_const.h> -#include <__type_traits/remove_const_ref.h> -#include <__type_traits/remove_cvref.h> #include <__utility/forward.h> #include <__utility/move.h> #include <__utility/pair.h> #include <__utility/swap.h> +#include <__utility/try_key_extraction.h> #include <limits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -51,14 +47,31 @@ _LIBCPP_PUSH_MACROS #include <__undef_macros> -_LIBCPP_BEGIN_NAMESPACE_STD +_LIBCPP_DIAGNOSTIC_PUSH +// GCC complains about the backslashes at the end, see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=121528 +_LIBCPP_GCC_DIAGNOSTIC_IGNORED("-Wcomment") +// __tree is a red-black-tree implementation used for the associative containers (i.e. (multi)map/set). It stores +// - (1) a pointer to the node with the smallest (i.e. leftmost) element, namely __begin_node_ +// - (2) the number of nodes in the tree, namely __size_ +// - (3) a pointer to the root of the tree, namely __end_node_ +// +// Storing (1) and (2) is required to allow for constant time lookups. A tree looks like this in memory: +// +// __end_node_ +// | +// root +// / \ +// l1 r1 +// / \ / \ +// ... ... ... ... +// +// All nodes except __end_node_ have a __left_ and __right_ pointer as well as a __parent_ pointer. +// __end_node_ only contains a __left_ pointer, which points to the root of the tree. +// This layout allows for iteration through the tree without a need for special handling of the end node. See +// __tree_next_iter and __tree_prev_iter for more details. +_LIBCPP_DIAGNOSTIC_POP -template <class _Tp, class _Compare, class _Allocator> -class __tree; -template <class _Tp, class _NodePtr, class _DiffType> -class __tree_iterator; -template <class _Tp, class _ConstNodePtr, class _DiffType> -class __tree_const_iterator; +_LIBCPP_BEGIN_NAMESPACE_STD template <class _Pointer> class __tree_end_node; @@ -70,13 +83,6 @@ class __tree_node; template <class _Key, class _Value> struct __value_type; -template <class _Allocator> -class __map_node_destructor; -template <class _TreeIterator> -class __map_iterator; -template <class _TreeIterator> -class __map_const_iterator; - /* _NodePtr algorithms @@ -185,6 +191,11 @@ _LIBCPP_HIDE_FROM_ABI _NodePtr __tree_next(_NodePtr __x) _NOEXCEPT { return __x->__parent_unsafe(); } +// __tree_next_iter and __tree_prev_iter implement iteration through the tree. The order is as follows: +// left sub-tree -> node -> right sub-tree. When the right-most node of a sub-tree is reached, we walk up the tree until +// we find a node where we were in the left sub-tree. We are _always_ in a left sub-tree, since the __end_node_ points +// to the actual root of the tree through a __left_ pointer. Incrementing the end() pointer is UB, so we can assume that +// never happens. template <class _EndNodePtr, class _NodePtr> inline _LIBCPP_HIDE_FROM_ABI _EndNodePtr __tree_next_iter(_NodePtr __x) _NOEXCEPT { _LIBCPP_ASSERT_INTERNAL(__x != nullptr, "node shouldn't be null"); @@ -494,16 +505,7 @@ _LIBCPP_HIDE_FROM_ABI void __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEP // node traits template <class _Tp> -struct __is_tree_value_type_imp : false_type {}; - -template <class _Key, class _Value> -struct __is_tree_value_type_imp<__value_type<_Key, _Value> > : true_type {}; - -template <class... _Args> -struct __is_tree_value_type : false_type {}; - -template <class _One> -struct __is_tree_value_type<_One> : __is_tree_value_type_imp<__remove_cvref_t<_One> > {}; +inline const bool __is_tree_value_type_v = __is_specialization_v<_Tp, __value_type>; template <class _Tp> struct __get_tree_key_type { @@ -580,8 +582,10 @@ class _LIBCPP_STANDALONE_DEBUG __tree_node : public __tree_node_base<_VoidPtr> { public: using __node_value_type _LIBCPP_NODEBUG = __get_node_value_type_t<_Tp>; +private: __node_value_type __value_; +public: _LIBCPP_HIDE_FROM_ABI __node_value_type& __get_value() { return __value_; } ~__tree_node() = delete; @@ -612,7 +616,7 @@ public: _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT { if (__value_constructed) - __alloc_traits::destroy(__na_, std::addressof(__p->__value_)); + __alloc_traits::destroy(__na_, std::addressof(__p->__get_value())); if (__p) __alloc_traits::deallocate(__na_, __p, 1); } @@ -648,8 +652,10 @@ public: _LIBCPP_HIDE_FROM_ABI __tree_iterator() _NOEXCEPT : __ptr_(nullptr) {} - _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_np()->__value_; } - _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__get_np()->__value_); } + _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_np()->__get_value(); } + _LIBCPP_HIDE_FROM_ABI pointer operator->() const { + return pointer_traits<pointer>::pointer_to(__get_np()->__get_value()); + } _LIBCPP_HIDE_FROM_ABI __tree_iterator& operator++() { __ptr_ = std::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_)); @@ -686,16 +692,6 @@ private: friend class __tree; template <class, class, class> friend class __tree_const_iterator; - template <class> - friend class __map_iterator; - template <class, class, class, class> - friend class map; - template <class, class, class, class> - friend class multimap; - template <class, class, class> - friend class set; - template <class, class, class> - friend class multiset; }; template <class _Tp, class _NodePtr, class _DiffType> @@ -709,22 +705,21 @@ class __tree_const_iterator { __end_node_pointer __ptr_; public: - using iterator_category = bidirectional_iterator_tag; - using value_type = __get_node_value_type_t<_Tp>; - using difference_type = _DiffType; - using reference = const value_type&; - using pointer = __rebind_pointer_t<_NodePtr, const value_type>; + using iterator_category = bidirectional_iterator_tag; + using value_type = __get_node_value_type_t<_Tp>; + using difference_type = _DiffType; + using reference = const value_type&; + using pointer = __rebind_pointer_t<_NodePtr, const value_type>; + using __non_const_iterator _LIBCPP_NODEBUG = __tree_iterator<_Tp, __node_pointer, difference_type>; _LIBCPP_HIDE_FROM_ABI __tree_const_iterator() _NOEXCEPT : __ptr_(nullptr) {} -private: - typedef __tree_iterator<_Tp, __node_pointer, difference_type> __non_const_iterator; - -public: _LIBCPP_HIDE_FROM_ABI __tree_const_iterator(__non_const_iterator __p) _NOEXCEPT : __ptr_(__p.__ptr_) {} - _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_np()->__value_; } - _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__get_np()->__value_); } + _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __get_np()->__get_value(); } + _LIBCPP_HIDE_FROM_ABI pointer operator->() const { + return pointer_traits<pointer>::pointer_to(__get_np()->__get_value()); + } _LIBCPP_HIDE_FROM_ABI __tree_const_iterator& operator++() { __ptr_ = std::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_)); @@ -762,16 +757,6 @@ private: template <class, class, class> friend class __tree; - template <class, class, class, class> - friend class map; - template <class, class, class, class> - friend class multimap; - template <class, class, class> - friend class set; - template <class, class, class> - friend class multiset; - template <class> - friend class __map_const_iterator; }; template <class _Tp, class _Compare> @@ -915,111 +900,126 @@ public: _NOEXCEPT_(__is_nothrow_swappable_v<value_compare>); #endif - template <class _Key, class... _Args> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args&&... __args); - template <class _Key, class... _Args> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&&...); - - template <class... _Args> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_impl(_Args&&... __args); - - template <class... _Args> - _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique_impl(const_iterator __p, _Args&&... __args); - template <class... _Args> _LIBCPP_HIDE_FROM_ABI iterator __emplace_multi(_Args&&... __args); template <class... _Args> _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); - template <class _Pp> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Pp&& __x) { - return __emplace_unique_extract_key(std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>()); - } - - template <class _First, - class _Second, - __enable_if_t<__can_extract_map_key<_First, key_type, value_type>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_First&& __f, _Second&& __s) { - return __emplace_unique_key_args(__f, std::forward<_First>(__f), std::forward<_Second>(__s)); - } - template <class... _Args> _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Args&&... __args) { - return __emplace_unique_impl(std::forward<_Args>(__args)...); - } - - template <class _Pp> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) { - return __emplace_unique_impl(std::forward<_Pp>(__x)); - } - - template <class _Pp> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) { - return __emplace_unique_key_args(__x, std::forward<_Pp>(__x)); - } - - template <class _Pp> - _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) { - return __emplace_unique_key_args(__x.first, std::forward<_Pp>(__x)); - } - - template <class _Pp> - _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _Pp&& __x) { - return __emplace_hint_unique_extract_key(__p, std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>()); - } - - template <class _First, - class _Second, - __enable_if_t<__can_extract_map_key<_First, key_type, value_type>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _First&& __f, _Second&& __s) { - return __emplace_hint_unique_key_args(__p, __f, std::forward<_First>(__f), std::forward<_Second>(__s)).first; + return std::__try_key_extraction<key_type>( + [this](const key_type& __key, _Args&&... __args2) { + __end_node_pointer __parent; + __node_base_pointer& __child = __find_equal(__parent, __key); + __node_pointer __r = static_cast<__node_pointer>(__child); + bool __inserted = false; + if (__child == nullptr) { + __node_holder __h = __construct_node(std::forward<_Args>(__args2)...); + __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); + __r = __h.release(); + __inserted = true; + } + return pair<iterator, bool>(iterator(__r), __inserted); + }, + [this](_Args&&... __args2) { + __node_holder __h = __construct_node(std::forward<_Args>(__args2)...); + __end_node_pointer __parent; + __node_base_pointer& __child = __find_equal(__parent, __h->__get_value()); + __node_pointer __r = static_cast<__node_pointer>(__child); + bool __inserted = false; + if (__child == nullptr) { + __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); + __r = __h.release(); + __inserted = true; + } + return pair<iterator, bool>(iterator(__r), __inserted); + }, + std::forward<_Args>(__args)...); } template <class... _Args> - _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args) { - return __emplace_hint_unique_impl(__p, std::forward<_Args>(__args)...); - } - - template <class _Pp> - _LIBCPP_HIDE_FROM_ABI iterator - __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_fail_tag) { - return __emplace_hint_unique_impl(__p, std::forward<_Pp>(__x)); - } - - template <class _Pp> - _LIBCPP_HIDE_FROM_ABI iterator - __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_self_tag) { - return __emplace_hint_unique_key_args(__p, __x, std::forward<_Pp>(__x)).first; - } - - template <class _Pp> - _LIBCPP_HIDE_FROM_ABI iterator - __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_first_tag) { - return __emplace_hint_unique_key_args(__p, __x.first, std::forward<_Pp>(__x)).first; + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_hint_unique(const_iterator __p, _Args&&... __args) { + return std::__try_key_extraction<key_type>( + [this, __p](const key_type& __key, _Args&&... __args2) { + __end_node_pointer __parent; + __node_base_pointer __dummy; + __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __key); + __node_pointer __r = static_cast<__node_pointer>(__child); + bool __inserted = false; + if (__child == nullptr) { + __node_holder __h = __construct_node(std::forward<_Args>(__args2)...); + __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); + __r = __h.release(); + __inserted = true; + } + return pair<iterator, bool>(iterator(__r), __inserted); + }, + [this, __p](_Args&&... __args2) { + __node_holder __h = __construct_node(std::forward<_Args>(__args2)...); + __end_node_pointer __parent; + __node_base_pointer __dummy; + __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __h->__get_value()); + __node_pointer __r = static_cast<__node_pointer>(__child); + if (__child == nullptr) { + __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); + __r = __h.release(); + } + return pair<iterator, bool>(iterator(__r), __child == nullptr); + }, + std::forward<_Args>(__args)...); } - template <class _ValueT = _Tp, __enable_if_t<__is_tree_value_type<_ValueT>::value, int> = 0> + template <class _ValueT = _Tp, __enable_if_t<__is_tree_value_type_v<_ValueT>, int> = 0> _LIBCPP_HIDE_FROM_ABI void __insert_unique_from_orphaned_node(const_iterator __p, __get_node_value_type_t<_Tp>&& __value) { __emplace_hint_unique(__p, const_cast<key_type&&>(__value.first), std::move(__value.second)); } - template <class _ValueT = _Tp, __enable_if_t<!__is_tree_value_type<_ValueT>::value, int> = 0> + template <class _ValueT = _Tp, __enable_if_t<!__is_tree_value_type_v<_ValueT>, int> = 0> _LIBCPP_HIDE_FROM_ABI void __insert_unique_from_orphaned_node(const_iterator __p, _Tp&& __value) { __emplace_hint_unique(__p, std::move(__value)); } - template <class _ValueT = _Tp, __enable_if_t<__is_tree_value_type<_ValueT>::value, int> = 0> + template <class _ValueT = _Tp, __enable_if_t<__is_tree_value_type_v<_ValueT>, int> = 0> _LIBCPP_HIDE_FROM_ABI void __insert_multi_from_orphaned_node(const_iterator __p, value_type&& __value) { __emplace_hint_multi(__p, const_cast<key_type&&>(__value.first), std::move(__value.second)); } - template <class _ValueT = _Tp, __enable_if_t<!__is_tree_value_type<_ValueT>::value, int> = 0> + template <class _ValueT = _Tp, __enable_if_t<!__is_tree_value_type_v<_ValueT>, int> = 0> _LIBCPP_HIDE_FROM_ABI void __insert_multi_from_orphaned_node(const_iterator __p, _Tp&& __value) { __emplace_hint_multi(__p, std::move(__value)); } + template <class _InIter, class _Sent> + _LIBCPP_HIDE_FROM_ABI void __insert_range_multi(_InIter __first, _Sent __last) { + if (__first == __last) + return; + + if (__root() == nullptr) { // Make sure we always have a root node + __insert_node_at( + __end_node(), __end_node()->__left_, static_cast<__node_base_pointer>(__construct_node(*__first).release())); + ++__first; + } + + auto __max_node = static_cast<__node_pointer>(std::__tree_max(static_cast<__node_base_pointer>(__root()))); + + for (; __first != __last; ++__first) { + __node_holder __nd = __construct_node(*__first); + // Always check the max node first. This optimizes for sorted ranges inserted at the end. + if (!value_comp()(__nd->__get_value(), __max_node->__get_value())) { // __node >= __max_val + __insert_node_at(static_cast<__end_node_pointer>(__max_node), + __max_node->__right_, + static_cast<__node_base_pointer>(__nd.get())); + __max_node = __nd.release(); + } else { + __end_node_pointer __parent; + __node_base_pointer& __child = __find_leaf_high(__parent, __nd->__get_value()); + __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd.release())); + } + } + } + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __node_assign_unique(const value_type& __v, __node_pointer __dest); _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(__node_pointer __nd); @@ -1059,9 +1059,22 @@ public: __insert_node_at(__end_node_pointer __parent, __node_base_pointer& __child, __node_base_pointer __new_node) _NOEXCEPT; template <class _Key> - _LIBCPP_HIDE_FROM_ABI iterator find(const _Key& __v); + _LIBCPP_HIDE_FROM_ABI iterator find(const _Key& __key) { + __end_node_pointer __parent; + __node_base_pointer __match = __find_equal(__parent, __key); + if (__match == nullptr) + return end(); + return iterator(static_cast<__node_pointer>(__match)); + } + template <class _Key> - _LIBCPP_HIDE_FROM_ABI const_iterator find(const _Key& __v) const; + _LIBCPP_HIDE_FROM_ABI const_iterator find(const _Key& __key) const { + __end_node_pointer __parent; + __node_base_pointer __match = __find_equal(__parent, __key); + if (__match == nullptr) + return end(); + return const_iterator(static_cast<__node_pointer>(__match)); + } template <class _Key> _LIBCPP_HIDE_FROM_ABI size_type __count_unique(const _Key& __k) const; @@ -1162,7 +1175,7 @@ private: } _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__tree&, false_type) _NOEXCEPT {} - template <class _From, class _ValueT = _Tp, __enable_if_t<__is_tree_value_type<_ValueT>::value, int> = 0> + template <class _From, class _ValueT = _Tp, __enable_if_t<__is_tree_value_type_v<_ValueT>, int> = 0> _LIBCPP_HIDE_FROM_ABI static void __assign_value(__get_node_value_type_t<value_type>& __lhs, _From&& __rhs) { using __key_type = __remove_const_t<typename value_type::first_type>; @@ -1172,7 +1185,7 @@ private: __lhs.second = std::forward<_From>(__rhs).second; } - template <class _To, class _From, class _ValueT = _Tp, __enable_if_t<!__is_tree_value_type<_ValueT>::value, int> = 0> + template <class _To, class _From, class _ValueT = _Tp, __enable_if_t<!__is_tree_value_type_v<_ValueT>, int> = 0> _LIBCPP_HIDE_FROM_ABI static void __assign_value(_To& __lhs, _From&& __rhs) { __lhs = std::forward<_From>(__rhs); } @@ -1234,7 +1247,7 @@ private: auto __right = __ptr->__right_; - __node_traits::destroy(__alloc_, std::addressof(__ptr->__value_)); + __node_traits::destroy(__alloc_, std::addressof(__ptr->__get_value())); __node_traits::deallocate(__alloc_, __ptr, 1); (*this)(static_cast<__node_pointer>(__right)); @@ -1253,7 +1266,7 @@ private: if (!__src) return nullptr; - __node_holder __new_node = __construct_node(__src->__value_); + __node_holder __new_node = __construct_node(__src->__get_value()); unique_ptr<__node, __tree_deleter> __left( __copy_construct_tree(static_cast<__node_pointer>(__src->__left_)), __node_alloc_); @@ -1284,7 +1297,7 @@ private: return nullptr; } - __assign_value(__dest->__value_, __src->__value_); + __assign_value(__dest->__get_value(), __src->__get_value()); __dest->__is_black_ = __src->__is_black_; // If we already have a left node in the destination tree, reuse it and copy-assign recursively @@ -1425,7 +1438,7 @@ void __tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _ if (__size_ != 0) { _DetachedTreeCache __cache(this); for (; __cache.__get() && __first != __last; ++__first) { - __assign_value(__cache.__get()->__value_, *__first); + __assign_value(__cache.__get()->__get_value(), *__first); __node_insert_multi(__cache.__get()); __cache.__advance(); } @@ -1517,13 +1530,13 @@ void __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type) { if (__size_ != 0) { _DetachedTreeCache __cache(this); while (__cache.__get() != nullptr && __t.__size_ != 0) { - __assign_value(__cache.__get()->__value_, std::move(__t.remove(__t.begin())->__value_)); + __assign_value(__cache.__get()->__get_value(), std::move(__t.remove(__t.begin())->__get_value())); __node_insert_multi(__cache.__get()); __cache.__advance(); } } while (__t.__size_ != 0) { - __insert_multi_from_orphaned_node(__e, std::move(__t.remove(__t.begin())->__value_)); + __insert_multi_from_orphaned_node(__e, std::move(__t.remove(__t.begin())->__get_value())); } } } @@ -1591,7 +1604,7 @@ __tree<_Tp, _Compare, _Allocator>::__find_leaf_low(__end_node_pointer& __parent, __node_pointer __nd = __root(); if (__nd != nullptr) { while (true) { - if (value_comp()(__nd->__value_, __v)) { + if (value_comp()(__nd->__get_value(), __v)) { if (__nd->__right_ != nullptr) __nd = static_cast<__node_pointer>(__nd->__right_); else { @@ -1621,7 +1634,7 @@ __tree<_Tp, _Compare, _Allocator>::__find_leaf_high(__end_node_pointer& __parent __node_pointer __nd = __root(); if (__nd != nullptr) { while (true) { - if (value_comp()(__v, __nd->__value_)) { + if (value_comp()(__v, __nd->__get_value())) { if (__nd->__left_ != nullptr) __nd = static_cast<__node_pointer>(__nd->__left_); else { @@ -1684,7 +1697,7 @@ __tree<_Tp, _Compare, _Allocator>::__find_equal(__end_node_pointer& __parent, co __node_base_pointer* __nd_ptr = __root_ptr(); if (__nd != nullptr) { while (true) { - if (value_comp()(__v, __nd->__value_)) { + if (value_comp()(__v, __nd->__get_value())) { if (__nd->__left_ != nullptr) { __nd_ptr = std::addressof(__nd->__left_); __nd = static_cast<__node_pointer>(__nd->__left_); @@ -1692,7 +1705,7 @@ __tree<_Tp, _Compare, _Allocator>::__find_equal(__end_node_pointer& __parent, co __parent = static_cast<__end_node_pointer>(__nd); return __parent->__left_; } - } else if (value_comp()(__nd->__value_, __v)) { + } else if (value_comp()(__nd->__get_value(), __v)) { if (__nd->__right_ != nullptr) { __nd_ptr = std::addressof(__nd->__right_); __nd = static_cast<__node_pointer>(__nd->__right_); @@ -1775,92 +1788,23 @@ void __tree<_Tp, _Compare, _Allocator>::__insert_node_at( } template <class _Tp, class _Compare, class _Allocator> -template <class _Key, class... _Args> -pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> -__tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) { - __end_node_pointer __parent; - __node_base_pointer& __child = __find_equal(__parent, __k); - __node_pointer __r = static_cast<__node_pointer>(__child); - bool __inserted = false; - if (__child == nullptr) { - __node_holder __h = __construct_node(std::forward<_Args>(__args)...); - __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); - __r = __h.release(); - __inserted = true; - } - return pair<iterator, bool>(iterator(__r), __inserted); -} - -template <class _Tp, class _Compare, class _Allocator> -template <class _Key, class... _Args> -pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> -__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args( - const_iterator __p, _Key const& __k, _Args&&... __args) { - __end_node_pointer __parent; - __node_base_pointer __dummy; - __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __k); - __node_pointer __r = static_cast<__node_pointer>(__child); - bool __inserted = false; - if (__child == nullptr) { - __node_holder __h = __construct_node(std::forward<_Args>(__args)...); - __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); - __r = __h.release(); - __inserted = true; - } - return pair<iterator, bool>(iterator(__r), __inserted); -} - -template <class _Tp, class _Compare, class _Allocator> template <class... _Args> typename __tree<_Tp, _Compare, _Allocator>::__node_holder __tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&&... __args) { __node_allocator& __na = __node_alloc(); __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, std::addressof(__h->__value_), std::forward<_Args>(__args)...); + __node_traits::construct(__na, std::addressof(__h->__get_value()), std::forward<_Args>(__args)...); __h.get_deleter().__value_constructed = true; return __h; } template <class _Tp, class _Compare, class _Allocator> template <class... _Args> -pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> -__tree<_Tp, _Compare, _Allocator>::__emplace_unique_impl(_Args&&... __args) { - __node_holder __h = __construct_node(std::forward<_Args>(__args)...); - __end_node_pointer __parent; - __node_base_pointer& __child = __find_equal(__parent, __h->__value_); - __node_pointer __r = static_cast<__node_pointer>(__child); - bool __inserted = false; - if (__child == nullptr) { - __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); - __r = __h.release(); - __inserted = true; - } - return pair<iterator, bool>(iterator(__r), __inserted); -} - -template <class _Tp, class _Compare, class _Allocator> -template <class... _Args> -typename __tree<_Tp, _Compare, _Allocator>::iterator -__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_impl(const_iterator __p, _Args&&... __args) { - __node_holder __h = __construct_node(std::forward<_Args>(__args)...); - __end_node_pointer __parent; - __node_base_pointer __dummy; - __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __h->__value_); - __node_pointer __r = static_cast<__node_pointer>(__child); - if (__child == nullptr) { - __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); - __r = __h.release(); - } - return iterator(__r); -} - -template <class _Tp, class _Compare, class _Allocator> -template <class... _Args> typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args) { __node_holder __h = __construct_node(std::forward<_Args>(__args)...); __end_node_pointer __parent; - __node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_); + __node_base_pointer& __child = __find_leaf_high(__parent, __h->__get_value()); __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); return iterator(static_cast<__node_pointer>(__h.release())); } @@ -1871,7 +1815,7 @@ typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p, _Args&&... __args) { __node_holder __h = __construct_node(std::forward<_Args>(__args)...); __end_node_pointer __parent; - __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_); + __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__get_value()); __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); return iterator(static_cast<__node_pointer>(__h.release())); } @@ -1884,7 +1828,7 @@ __tree<_Tp, _Compare, _Allocator>::__node_assign_unique(const value_type& __v, _ __node_pointer __r = static_cast<__node_pointer>(__child); bool __inserted = false; if (__child == nullptr) { - __assign_value(__nd->__value_, __v); + __assign_value(__nd->__get_value(), __v); __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); __r = __nd; __inserted = true; @@ -1896,7 +1840,7 @@ template <class _Tp, class _Compare, class _Allocator> typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd) { __end_node_pointer __parent; - __node_base_pointer& __child = __find_leaf_high(__parent, __nd->__value_); + __node_base_pointer& __child = __find_leaf_high(__parent, __nd->__get_value()); __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); return iterator(__nd); } @@ -1905,7 +1849,7 @@ template <class _Tp, class _Compare, class _Allocator> typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p, __node_pointer __nd) { __end_node_pointer __parent; - __node_base_pointer& __child = __find_leaf(__p, __parent, __nd->__value_); + __node_base_pointer& __child = __find_leaf(__p, __parent, __nd->__get_value()); __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); return iterator(__nd); } @@ -1932,7 +1876,7 @@ __tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(_NodeHandle&& __n __node_pointer __ptr = __nh.__ptr_; __end_node_pointer __parent; - __node_base_pointer& __child = __find_equal(__parent, __ptr->__value_); + __node_base_pointer& __child = __find_equal(__parent, __ptr->__get_value()); if (__child != nullptr) return _InsertReturnType{iterator(static_cast<__node_pointer>(__child)), false, std::move(__nh)}; @@ -1951,7 +1895,7 @@ __tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(const_iterator __ __node_pointer __ptr = __nh.__ptr_; __end_node_pointer __parent; __node_base_pointer __dummy; - __node_base_pointer& __child = __find_equal(__hint, __parent, __dummy, __ptr->__value_); + __node_base_pointer& __child = __find_equal(__hint, __parent, __dummy, __ptr->__get_value()); __node_pointer __r = static_cast<__node_pointer>(__child); if (__child == nullptr) { __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr)); @@ -1986,7 +1930,7 @@ _LIBCPP_HIDE_FROM_ABI void __tree<_Tp, _Compare, _Allocator>::__node_handle_merg for (typename _Tree::iterator __i = __source.begin(); __i != __source.end();) { __node_pointer __src_ptr = __i.__get_np(); __end_node_pointer __parent; - __node_base_pointer& __child = __find_equal(__parent, __src_ptr->__value_); + __node_base_pointer& __child = __find_equal(__parent, __src_ptr->__get_value()); ++__i; if (__child != nullptr) continue; @@ -2003,7 +1947,7 @@ __tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(_NodeHandle&& __nh return end(); __node_pointer __ptr = __nh.__ptr_; __end_node_pointer __parent; - __node_base_pointer& __child = __find_leaf_high(__parent, __ptr->__value_); + __node_base_pointer& __child = __find_leaf_high(__parent, __ptr->__get_value()); __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr)); __nh.__release_ptr(); return iterator(__ptr); @@ -2018,7 +1962,7 @@ __tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(const_iterator __h __node_pointer __ptr = __nh.__ptr_; __end_node_pointer __parent; - __node_base_pointer& __child = __find_leaf(__hint, __parent, __ptr->__value_); + __node_base_pointer& __child = __find_leaf(__hint, __parent, __ptr->__get_value()); __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr)); __nh.__release_ptr(); return iterator(__ptr); @@ -2032,7 +1976,7 @@ _LIBCPP_HIDE_FROM_ABI void __tree<_Tp, _Compare, _Allocator>::__node_handle_merg for (typename _Tree::iterator __i = __source.begin(); __i != __source.end();) { __node_pointer __src_ptr = __i.__get_np(); __end_node_pointer __parent; - __node_base_pointer& __child = __find_leaf_high(__parent, __src_ptr->__value_); + __node_base_pointer& __child = __find_leaf_high(__parent, __src_ptr->__get_value()); ++__i; __source.__remove_node_pointer(__src_ptr); __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__src_ptr)); @@ -2083,32 +2027,13 @@ __tree<_Tp, _Compare, _Allocator>::__erase_multi(const _Key& __k) { template <class _Tp, class _Compare, class _Allocator> template <class _Key> -typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) { - iterator __p = __lower_bound(__v, __root(), __end_node()); - if (__p != end() && !value_comp()(__v, *__p)) - return __p; - return end(); -} - -template <class _Tp, class _Compare, class _Allocator> -template <class _Key> -typename __tree<_Tp, _Compare, _Allocator>::const_iterator -__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) const { - const_iterator __p = __lower_bound(__v, __root(), __end_node()); - if (__p != end() && !value_comp()(__v, *__p)) - return __p; - return end(); -} - -template <class _Tp, class _Compare, class _Allocator> -template <class _Key> typename __tree<_Tp, _Compare, _Allocator>::size_type __tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const { __node_pointer __rt = __root(); while (__rt != nullptr) { - if (value_comp()(__k, __rt->__value_)) { + if (value_comp()(__k, __rt->__get_value())) { __rt = static_cast<__node_pointer>(__rt->__left_); - } else if (value_comp()(__rt->__value_, __k)) + } else if (value_comp()(__rt->__get_value(), __k)) __rt = static_cast<__node_pointer>(__rt->__right_); else return 1; @@ -2123,10 +2048,10 @@ __tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const { __end_node_pointer __result = __end_node(); __node_pointer __rt = __root(); while (__rt != nullptr) { - if (value_comp()(__k, __rt->__value_)) { + if (value_comp()(__k, __rt->__get_value())) { __result = static_cast<__end_node_pointer>(__rt); __rt = static_cast<__node_pointer>(__rt->__left_); - } else if (value_comp()(__rt->__value_, __k)) + } else if (value_comp()(__rt->__get_value(), __k)) __rt = static_cast<__node_pointer>(__rt->__right_); else return std::distance( @@ -2141,7 +2066,7 @@ template <class _Key> typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, __node_pointer __root, __end_node_pointer __result) { while (__root != nullptr) { - if (!value_comp()(__root->__value_, __v)) { + if (!value_comp()(__root->__get_value(), __v)) { __result = static_cast<__end_node_pointer>(__root); __root = static_cast<__node_pointer>(__root->__left_); } else @@ -2155,7 +2080,7 @@ template <class _Key> typename __tree<_Tp, _Compare, _Allocator>::const_iterator __tree<_Tp, _Compare, _Allocator>::__lower_bound( const _Key& __v, __node_pointer __root, __end_node_pointer __result) const { while (__root != nullptr) { - if (!value_comp()(__root->__value_, __v)) { + if (!value_comp()(__root->__get_value(), __v)) { __result = static_cast<__end_node_pointer>(__root); __root = static_cast<__node_pointer>(__root->__left_); } else @@ -2169,7 +2094,7 @@ template <class _Key> typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, __node_pointer __root, __end_node_pointer __result) { while (__root != nullptr) { - if (value_comp()(__v, __root->__value_)) { + if (value_comp()(__v, __root->__get_value())) { __result = static_cast<__end_node_pointer>(__root); __root = static_cast<__node_pointer>(__root->__left_); } else @@ -2183,7 +2108,7 @@ template <class _Key> typename __tree<_Tp, _Compare, _Allocator>::const_iterator __tree<_Tp, _Compare, _Allocator>::__upper_bound( const _Key& __v, __node_pointer __root, __end_node_pointer __result) const { while (__root != nullptr) { - if (value_comp()(__v, __root->__value_)) { + if (value_comp()(__v, __root->__get_value())) { __result = static_cast<__end_node_pointer>(__root); __root = static_cast<__node_pointer>(__root->__left_); } else @@ -2200,10 +2125,10 @@ __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) { __end_node_pointer __result = __end_node(); __node_pointer __rt = __root(); while (__rt != nullptr) { - if (value_comp()(__k, __rt->__value_)) { + if (value_comp()(__k, __rt->__get_value())) { __result = static_cast<__end_node_pointer>(__rt); __rt = static_cast<__node_pointer>(__rt->__left_); - } else if (value_comp()(__rt->__value_, __k)) + } else if (value_comp()(__rt->__get_value(), __k)) __rt = static_cast<__node_pointer>(__rt->__right_); else return _Pp(iterator(__rt), @@ -2222,10 +2147,10 @@ __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const { __end_node_pointer __result = __end_node(); __node_pointer __rt = __root(); while (__rt != nullptr) { - if (value_comp()(__k, __rt->__value_)) { + if (value_comp()(__k, __rt->__get_value())) { __result = static_cast<__end_node_pointer>(__rt); __rt = static_cast<__node_pointer>(__rt->__left_); - } else if (value_comp()(__rt->__value_, __k)) + } else if (value_comp()(__rt->__get_value(), __k)) __rt = static_cast<__node_pointer>(__rt->__right_); else return _Pp( @@ -2244,10 +2169,10 @@ __tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) { __end_node_pointer __result = __end_node(); __node_pointer __rt = __root(); while (__rt != nullptr) { - if (value_comp()(__k, __rt->__value_)) { + if (value_comp()(__k, __rt->__get_value())) { __result = static_cast<__end_node_pointer>(__rt); __rt = static_cast<__node_pointer>(__rt->__left_); - } else if (value_comp()(__rt->__value_, __k)) + } else if (value_comp()(__rt->__get_value(), __k)) __rt = static_cast<__node_pointer>(__rt->__right_); else return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__end_node_pointer>(__rt)), @@ -2265,10 +2190,10 @@ __tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const { __end_node_pointer __result = __end_node(); __node_pointer __rt = __root(); while (__rt != nullptr) { - if (value_comp()(__k, __rt->__value_)) { + if (value_comp()(__k, __rt->__get_value())) { __result = static_cast<__end_node_pointer>(__rt); __rt = static_cast<__node_pointer>(__rt->__left_); - } else if (value_comp()(__rt->__value_, __k)) + } else if (value_comp()(__rt->__get_value(), __k)) __rt = static_cast<__node_pointer>(__rt->__right_); else return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__end_node_pointer>(__rt)), |