diff options
Diffstat (limited to 'contrib/libc++/include/__tree')
-rw-r--r-- | contrib/libc++/include/__tree | 147 |
1 files changed, 71 insertions, 76 deletions
diff --git a/contrib/libc++/include/__tree b/contrib/libc++/include/__tree index 574e74b..94565bc 100644 --- a/contrib/libc++/include/__tree +++ b/contrib/libc++/include/__tree @@ -548,31 +548,15 @@ template <class _VoidPtr> class __tree_node_base : public __tree_end_node < - typename pointer_traits<_VoidPtr>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<__tree_node_base<_VoidPtr> > -#else - rebind<__tree_node_base<_VoidPtr> >::other -#endif + typename __rebind_pointer<_VoidPtr, __tree_node_base<_VoidPtr> >::type > { __tree_node_base(const __tree_node_base&); __tree_node_base& operator=(const __tree_node_base&); public: - typedef typename pointer_traits<_VoidPtr>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<__tree_node_base> -#else - rebind<__tree_node_base>::other -#endif - pointer; - typedef typename pointer_traits<_VoidPtr>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<const __tree_node_base> -#else - rebind<const __tree_node_base>::other -#endif - const_pointer; + typedef typename __rebind_pointer<_VoidPtr, __tree_node_base>::type pointer; + typedef typename __rebind_pointer<_VoidPtr, const __tree_node_base>::type const_pointer; + typedef __tree_end_node<pointer> base; pointer __right_; @@ -623,13 +607,7 @@ public: typedef _Tp value_type; typedef _DiffType difference_type; typedef value_type& reference; - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<value_type> -#else - rebind<value_type>::other -#endif - pointer; + typedef typename __rebind_pointer<__node_pointer, value_type>::type pointer; _LIBCPP_INLINE_VISIBILITY __tree_iterator() _NOEXCEPT #if _LIBCPP_STD_VER > 11 @@ -694,13 +672,7 @@ public: typedef _Tp value_type; typedef _DiffType difference_type; typedef const value_type& reference; - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<const value_type> -#else - rebind<const value_type>::other -#endif - pointer; + typedef typename __rebind_pointer<__node_pointer, const value_type>::type pointer; _LIBCPP_INLINE_VISIBILITY __tree_const_iterator() _NOEXCEPT #if _LIBCPP_STD_VER > 11 @@ -710,13 +682,8 @@ public: private: typedef typename remove_const<__node>::type __non_const_node; - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<__non_const_node> -#else - rebind<__non_const_node>::other -#endif - __non_const_node_pointer; + typedef typename __rebind_pointer<__node_pointer, __non_const_node>::type + __non_const_node_pointer; typedef __tree_iterator<value_type, __non_const_node_pointer, difference_type> __non_const_iterator; public: @@ -730,14 +697,8 @@ public: _LIBCPP_INLINE_VISIBILITY __tree_const_iterator& operator++() { - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<typename __node::base> -#else - rebind<typename __node::base>::other -#endif - __node_base_pointer; - + typedef typename __rebind_pointer<__node_pointer, typename __node::base>::type + __node_base_pointer; __ptr_ = static_cast<__node_pointer>( __tree_next(static_cast<__node_base_pointer>(__ptr_))); return *this; @@ -749,14 +710,8 @@ public: _LIBCPP_INLINE_VISIBILITY __tree_const_iterator& operator--() { - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<typename __node::base> -#else - rebind<typename __node::base>::other -#endif - __node_base_pointer; - + typedef typename __rebind_pointer<__node_pointer, typename __node::base>::type + __node_base_pointer; __ptr_ = static_cast<__node_pointer>( __tree_prev(static_cast<__node_base_pointer>(__ptr_))); return *this; @@ -810,20 +765,9 @@ public: typedef typename __node_base::pointer __node_base_const_pointer; private: typedef typename __node_base::base __end_node_t; - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<__end_node_t> -#else - rebind<__end_node_t>::other -#endif - __end_node_ptr; - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<__end_node_t> -#else - rebind<__end_node_t>::other -#endif - __end_node_const_ptr; + typedef typename __rebind_pointer<__node_pointer, __end_node_t>::type + __end_node_ptr; + typedef __end_node_ptr __end_node_const_ptr; __node_pointer __begin_node_; __compressed_pair<__end_node_t, __node_allocator> __pair1_; @@ -965,6 +909,13 @@ public: iterator __insert_multi(const value_type& __v); iterator __insert_multi(const_iterator __p, const value_type& __v); +#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + pair<iterator, bool> __insert_unique( value_type&& __v); + iterator __insert_unique(const_iterator __p, value_type&& __v); + iterator __insert_multi( value_type&& __v); + iterator __insert_multi(const_iterator __p, value_type&& __v); +#endif + pair<iterator, bool> __node_insert_unique(__node_pointer __nd); iterator __node_insert_unique(const_iterator __p, __node_pointer __nd); @@ -1118,8 +1069,8 @@ __tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp) template <class _Tp, class _Compare, class _Allocator> __tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a) - : __pair1_(__node_allocator(__a)), - __begin_node_(__node_pointer()), + : __begin_node_(__node_pointer()), + __pair1_(__node_allocator(__a)), __pair3_(0) { __begin_node() = __end_node(); @@ -1128,8 +1079,8 @@ __tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a) template <class _Tp, class _Compare, class _Allocator> __tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp, const allocator_type& __a) - : __pair1_(__node_allocator(__a)), - __begin_node_(__node_pointer()), + : __begin_node_(__node_pointer()), + __pair1_(__node_allocator(__a)), __pair3_(0, __comp) { __begin_node() = __end_node(); @@ -1786,6 +1737,28 @@ __tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p, #endif // _LIBCPP_HAS_NO_VARIADICS template <class _Tp, class _Compare, class _Allocator> +pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> +__tree<_Tp, _Compare, _Allocator>::__insert_unique(value_type&& __v) +{ + __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v)); + pair<iterator, bool> __r = __node_insert_unique(__h.get()); + if (__r.second) + __h.release(); + return __r; +} + +template <class _Tp, class _Compare, class _Allocator> +typename __tree<_Tp, _Compare, _Allocator>::iterator +__tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, value_type&& __v) +{ + __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v)); + iterator __r = __node_insert_unique(__p, __h.get()); + if (__r.__ptr_ == __h.get()) + __h.release(); + return __r; +} + +template <class _Tp, class _Compare, class _Allocator> template <class _Vp> pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> __tree<_Tp, _Compare, _Allocator>::__insert_unique(_Vp&& __v) @@ -1810,6 +1783,28 @@ __tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, _Vp&& __v } template <class _Tp, class _Compare, class _Allocator> +typename __tree<_Tp, _Compare, _Allocator>::iterator +__tree<_Tp, _Compare, _Allocator>::__insert_multi(value_type&& __v) +{ + __node_base_pointer __parent; + __node_base_pointer& __child = __find_leaf_high(__parent, __v); + __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v)); + __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); + return iterator(__h.release()); +} + +template <class _Tp, class _Compare, class _Allocator> +typename __tree<_Tp, _Compare, _Allocator>::iterator +__tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, value_type&& __v) +{ + __node_base_pointer __parent; + __node_base_pointer& __child = __find_leaf(__p, __parent, __v); + __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v)); + __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); + return iterator(__h.release()); +} + +template <class _Tp, class _Compare, class _Allocator> template <class _Vp> typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__insert_multi(_Vp&& __v) @@ -1843,7 +1838,7 @@ __tree<_Tp, _Compare, _Allocator>::__construct_node(const value_type& __v) __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); __h.get_deleter().__value_constructed = true; - return _VSTD::move(__h); // explicitly moved for C++03 + return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 } #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |