On Wed, 4 Dec 2024 at 21:50, Jonathan Wakely <jwak...@redhat.com> wrote: > > On 04/12/24 19:27 +0100, François Dumont wrote: > >Hi > > > >I've completed the synchronization with your equivalent PR for > >std::list so here is the updated patch. > > > >PR updated a couple of days ago. > > > >Note that I've started to rework the patch for the same in _Hashtable. > > Great, thanks.
Ugh, gmail completely mangles this mail for me. You can see my comments and questions about changing _Link_type to _Base_ptr here: https://gcc.gnu.org/pipermail/gcc-patches/2024-December/670872.html > >François > > > > > >On 30/11/2024 18:21, Jonathan Wakely wrote: > >> > >> > >>On Sat, 30 Nov 2024, 13:52 François Dumont, <frs.dum...@gmail.com> wrote: > >> > >> Hi > >> > >> I've applied all your comments below and the ones you did on the > >> PR directly. > >> > >> When all new types totally seperated from the legacy types > >> _Rb_tree_node_traits is indeed useless. > >> > >> Regarding _Rb_tree_helpers I got rid of it but move the > >> insert-and-rebalance and rebalance-for-erase function to > >> _Node_traits<>. > >> > >> PR updated: > >> > >> https://forge.sourceware.org/gcc/gcc-TEST/pulls/27 > >> > >> libstdc++: Add fancy pointer support in map and set Support fancy > >> allocator pointer type in std::_Rb_tree<>. In case of fancy > >> pointer type the container is now storing the pointer to > >> __rb_tree::_Node<_ValPtr> as a pointer to > >> __rb_tree::_Node_base<_VoidPtr>. Many methods are adapted to take > >> and return _Base_ptr in place of _Link_type which has been renamed > >> into _Node_ptr. As all node are stored as _Base_ptr have all > >> methods working with this type and remove _Const_Base_ptr and > >> _Const_Node_ptr and all methods associated with it. > >> > >> > >>Sounds good! I'll take another look on Monday. > >> > >> > >> libstdc++-v3/ChangeLog: * include/bits/stl_tree.h > >> [_GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE]: New macro to control usage > >> of the code required to support fancy allocator pointer type. > >> (_Rb_tree_node_base::_Const_Base_ptr): Remove. > >> (_Rb_tree_node_base::_S_minimum, _Rb_tree_node_base::_S_maximum): > >> Remove overloads for _Const_Base_ptr. > >> (_Rb_tree_node_base::_M_base_ptr()): New. > >> (_Rb_tree_node_base::_M_node_ptr<_NodePtr>()): New. > >> (_Rb_tree_node::_Link_type): Rename into... > >> (_Rb_tree_node::_Node_ptr): ...this. (__rb_tree::_Node_base<>): > >> New. (__rb_tree::_Header<>): New. (__rb_tree::_Node<>): New. > >> (_Rb_tree_increment(const _Rb_tree_node_base*)): Remove > >> declaration. (_Rb_tree_decrement(const _Rb_tree_node_base*)): > >> Remove declaration. (_Rb_tree_iterator<>::_Link_type): Rename > >> into... (_Rb_tree_iterator<>::_Node_ptr): ...this. > >> (_Rb_tree_const_iterator<>::_Link_type): Rename into... > >> (_Rb_tree_const_iterator<>::_Node_ptr): ...this. > >> (_Rb_tree_const_iterator<>::_M_const_cast): Remove. > >> (_Rb_tree_const_iterator<>::_M_node): Change type into _Base_ptr. > >> (__rb_tree::_Iterator<>): New. (__rb_tree::_Node_traits<>): New. > >> (_Rb_tree<>::_Node_base, _Rb_tree::_Node_type): New. > >> (_Rb_tree<>::_Link_type): Rename into... (_Rb_tree<>::_Node_ptr): > >> ...this. (_Rb_tree<>::_Const_Base_ptr, > >> _Rb_tree<>::_Const_Node_ptr): Remove. (_Rb_tree<>): Adapt to > >> generalize usage of _Base_ptr in place of former _Link_type now > >> _Node_ptr. (_Rb_tree<>::_M_mbegin): Remove. > >> (_Rb_tree<>::_S_left(_Const_Base_ptr)): Remove. > >> (_Rb_tree<>::_S_right(_Const_Base_ptr)): Remove. > >> (_Rb_tree<>::_S_maximum(_Const_Base_ptr)): Remove. > >> (_Rb_tree<>::_S_minimum(_Const_Base_ptr)): Remove. * > >> testsuite/23_containers/map/allocator/ext_ptr.cc: New test case. * > >> testsuite/23_containers/multimap/allocator/ext_ptr.cc: New test > >> case. * testsuite/23_containers/multiset/allocator/ext_ptr.cc: New > >> test case. * testsuite/23_containers/set/allocator/ext_ptr.cc: New > >> test case. > >> > >> I've tested it in C++98/C++17/C++20 with default > >> _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE and with it 9001. > >> > >> François > >> > >> On 18/11/2024 17:39, Jonathan Wakely wrote: > >>> On 18/11/24 06:57 +0100, François Dumont wrote: > >>>> Hi > >>>> > >>>> Here is a new proposal with all the cleanup regarding _Const_Base_ptr > >>>> that makes support of allocator's fancy pointer type simpler. > >>>> > >>>> Also submitted as PR: > >>>> > >>>> https://forge.sourceware.org/gcc/gcc-TEST/pulls/27 > >>>> > >>>> libstdc++: Add fancy pointer support in map and set > >>>> > >>>> Support fancy allocator pointer type instd::_Rb_tree<>. > >>>> > >>>> In case of fancy pointer type the container is now storing the > >>>> pointer to > >>>> _Rb_tree_pnode<> as a pointer to _Rb_tree_pnode_base<>. > >>>> > >>>> Many methods are adapted to take and return _Base_ptr in place of > >>>> _Link_type > >>>> which has been renamed into _Node_ptr. > >>>> > >>>> As all node are stored as _Base_ptr have all methods working with > >>>> this type > >>>> and remove _Const_Base_ptr and all methods associated to it. > >>>> > >>>> libstdc++-v3/ChangeLog: > >>>> > >>>> * include/bits/stl_set.h (std::set<>::upper_bound<>(const > >>>> _Kt&) const): Fix > >>>> decltype typo to use const_iterator. > >>>> * include/bits/stl_tree.h > >>>> (_Rb_tree_ptr_traits<>): New. > >>>> (_Rb_tree_pnode_base<>): New. > >>>> (_Rb_tree_node_base): Inherit from latter. > >>>> (_Rb_tree_node_base::_Const_Base_ptr): Remove. > >>>> (_Rb_tree_node_base::_S_minimum(_Const_Base_ptr)): Remove. > >>>> (_Rb_tree_node_base::_S_maximum(_Const_Base_ptr)): Remove. > >>>> (_Rb_tree_pheader): New. > >>>> (_Rb_tree_header): Inherit from latter. > >>>> (_Rb_tree_node_val): New. > >>>> (_Rb_tree_node): Inherit from latter. > >>>> (_Rb_tree_pnode): New. > >>>> (_Rb_tree_iterator<>::_Link_type): Rename into... > >>>> (_Rb_tree_iterator<>::_Node_ptr): ...this. > >>>> (_Rb_tree_const_iterator<>::_Link_type): Rename into... > >>>> (_Rb_tree_const_iterator<>::_Node_ptr): ...this. > >>>> (_Rb_tree_const_iterator<>::_M_node): Change type into > >>>> _Base_ptr. > >>>> (_Rb_tree_const_iterator<>::_M_const_cast): Remove. > >>>> (_Rb_tree_helpers<>): New. > >>>> (_Rb_tree_piterator): New. > >>>> (_Rb_tree_const_piterator): New. > >>>> (_Rb_tree_node_traits<>): New. > >>>> (_Rb_tree::_Node_base, _Rb_tree::_Node_type): New. > >>>> (_Rb_tree<>::_Const_Base_ptr): Remove. > >>>> (_Rb_tree): Adapt to generalize usage of _Base_ptr in > >>>> place of _Link_type. > >>>> (_Rb_tree<>::_M_mbegin): Remove. > >>>> (_Rb_tree<>::_S_left(_Const_Base_ptr)): Remove. > >>>> (_Rb_tree<>::_S_right(_Const_Base_ptr)): Remove. > >>>> (_Rb_tree<>::_S_maximum(_Const_Base_ptr)): Remove. > >>>> (_Rb_tree<>::_S_minimum(_Const_Base_ptr)): Remove. > >>>> * testsuite/23_containers/map/allocator/ext_ptr.cc: New > >>>> test case. > >>>> * testsuite/23_containers/multimap/allocator/ext_ptr.cc: > >>>> New test case. > >>>> * testsuite/23_containers/multiset/allocator/ext_ptr.cc: > >>>> New test case. > >>>> * testsuite/23_containers/set/allocator/ext_ptr.cc: New > >>>> test case. > >>>> > >>>> Tested under Linux x64. > >>>> > >>>> > >>>> Note that I've also run the 23_containers tests on map, multimap, > >>>> multiset and set tweaking implementation > >>>> so that new types are being used when C++11 or later even if allocator > >>>> pointer type is a C pointer. > >>> Please take a look at the _GLIBCXX_USE_ALLOC_PTR_xxx macros in > >>> https://gcc.gnu.org/pipermail/gcc-patches/2024-November/669128.html > >>> andhttps://gcc.gnu.org/pipermail/gcc-patches/2024-November/669127.html > >>> Those macros allow the fancy pointer support to be disabled, in case > >>> it will break anything for current users. Maybe more importantly, it > >>> allows the new node types to be used always, even for T*. That means > >>> we can run the entire testsuite using the new nodes without tweaking > >>> the implementation. > >>> > >>> Please consider a _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE macro (or some > >>> other name). > >>> > >>>> Ok to commit ? > >>>> > >>>> François > >>>> > >>>> On 12/11/2024 15:56, Jonathan Wakely wrote: > >>>>> On Mon, 4 Nov 2024 at 21:34, François Dumont<frs.dum...@gmail.com> > >>>>> <mailto:frs.dum...@gmail.com> wrote: > >>>>>> On 04/11/2024 19:45, Jonathan Wakely wrote: > >>>>>>> On Mon, 4 Nov 2024 at 18:30, François Dumont<frs.dum...@gmail.com> > >>>>>>> <mailto:frs.dum...@gmail.com> wrote: > >>>>>>>> On 21/10/2024 06:56, François Dumont wrote: > >>>>>>>> > >>>>>>>> > >>>>>>>> On 17/10/2024 23:11, Jonathan Wakely wrote: > >>>>>>>> > >>>>>>>> > >>>>>>>> > >>>>>>>> On Thu, 17 Oct 2024 at 21:39, Jonathan > >>>>>>>> Wakely<jwakely....@gmail.com> <mailto:jwakely....@gmail.com> wrote: > >>>>>>>>> On Thu, 17 Oct 2024 at 20:52, François > >>>>>>>>> Dumont<frs.dum...@gmail.com> <mailto:frs.dum...@gmail.com> wrote: > >>>>>>>>>> Here is an updated version that compiles, I think, all your > >>>>>>>>>> feedbacks. It's much cleaner indeed. > >>>>>>>>> Thanks, I'll take a look tomorrow. > >>>>>>>>> > >>>>>>>>>> It's also tested in C++98/17/23. > >>>>>>>>>> > >>>>>>>>>> I'm surprised that we do not need to consider > >>>>>>>>>> potentialallocator::const_pointer. > >>>>>>>>> Do you mean consider the case whereAlloc::const_pointer is not > >>>>>>>>> the same type as rebinding 'pointer' to a const element type? > >>>>>>>> Yes, exactly. > >>>>>>>> > >>>>>>>> > >>>>>>>>> We don't need to consider that because we never get a > >>>>>>>>> 'const_pointer' from the allocator, and we never need to pass a > >>>>>>>>> 'const_pointer' to the allocator. The allocator's 'allocate' and > >>>>>>>>> 'deallocate' members both work with the 'pointer' type, so we only > >>>>>>>>> need to use that type when interacting with the allocator. For all > >>>>>>>>> the other uses, such as _Const_Node_ptr, what we need is a > >>>>>>>>> pointer-to-const that's compatible with the allocator's pointer > >>>>>>>>> type. It doesn't actually matter if it's the same type as > >>>>>>>>> allocator_traits<Alloc>::const_pointer, because we don't need > >>>>>>>> Sorry, I sent the email before finishing that thought! > >>>>>>>> > >>>>>>>> ... we don't need to pass a const_pointer to anything, we only > >>>>>>>> need it for the container's own purposes. > >>>>>>>> > >>>>>>>> But thinking about it some more, do we even need a const-pointer > >>>>>>>> for the container? Currently the const_iterator stores a > >>>>>>>> const-pointer, and some members like _M_root() and _M_leftmost() > >>>>>>>> return a const-pointer. But they don't need to. The nodes are all > >>>>>>>> pointed to by a non-const _Base_ptr, none of the storage managed by > >>>>>>>> the container is const. > >>>>>>>> > >>>>>>>> Except _M_impl._M_header in a const context. > >>>>>>>> > >>>>>>>> Using const_cast would result in a similar UB that you fixed on > >>>>>>>> _GLIBCXX_DEBUG containers, no ? > >>>>>>> We only use a pointer to _M_header for the past-the-end iterator, > >>>>>>> which is not dereferenceable. It's OK to do the const_cast, it's > >>>>>>> not > >>>>>>> OK to write something through that pointer/reference if the object > >>>>>>> is > >>>>>>> really const. But you can't write through a past-the-end pointer > >>>>>>> anyway. > >>>>>>> > >>>>>> One last question then to complete this work, is it fine to change > >>>>>> _Rb_tree_const_iterator::_M_node to _Base_ptr ? No abi issue in > >>>>>> doing so ? > >>>>> I thought I'd sent a reply to this question, but I don't see it in > >>>>> the > >>>>> archives, sorry. > >>>>> > >>>>> So changing from _Const_Base_ptr to _Base_ptr? Yes, I think that's > >>>>> OK. > >>>>> > >>>> diff --git a/libstdc++-v3/include/bits/stl_set.h > >>>> b/libstdc++-v3/include/bits/stl_set.h > >>>> index c0eb4dbf65f..3d17626f330 100644 > >>>> --- a/libstdc++-v3/include/bits/stl_set.h > >>>> +++ b/libstdc++-v3/include/bits/stl_set.h > >>>> @@ -875,7 +875,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > >>>> template<typename _Kt> > >>>> auto > >>>> upper_bound(const _Kt& __x) const > >>>> - -> decltype(iterator(_M_t._M_upper_bound_tr(__x))) > >>>> + -> decltype(const_iterator(_M_t._M_upper_bound_tr(__x))) > >>>> { return const_iterator(_M_t._M_upper_bound_tr(__x)); } > >>>> #endif > >>>> ///@} > >>>> diff --git a/libstdc++-v3/include/bits/stl_tree.h > >>>> b/libstdc++-v3/include/bits/stl_tree.h > >>>> index bc27e191e8b..c6cba99726d 100644 > >>>> --- a/libstdc++-v3/include/bits/stl_tree.h > >>>> +++ b/libstdc++-v3/include/bits/stl_tree.h > >>>> @@ -96,44 +96,100 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > >>>> > >>>> enum _Rb_tree_color { _S_red = false, _S_black = true }; > >>>> > >>>> - struct _Rb_tree_node_base > >>>> - { > >>>> - typedef _Rb_tree_node_base* _Base_ptr; > >>>> - typedef const _Rb_tree_node_base* _Const_Base_ptr; > >>>> - > >>>> - _Rb_tree_color _M_color; > >>>> - _Base_ptr _M_parent; > >>>> - _Base_ptr _M_left; > >>>> - _Base_ptr _M_right; > >>>> - > >>>> - static _Base_ptr > >>>> - _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT > >>>> +#if __cplusplus >= 201103L > >>>> + template<typename _Ptr> > >>>> + struct _Rb_tree_ptr_traits > >>>> { > >>>> - while (__x->_M_left != 0) __x = __x->_M_left; > >>>> - return __x; > >>>> - } > >>>> + template<typename _Tp> > >>>> + struct __rebind > >>>> + { using __type = __ptr_rebind<_Ptr, _Tp>; }; > >>> This only seems to be used in one place, can you just use __ptr_rebind > >>> directly in that one place? > >>> > >>>> + > >>>> + template<typename _BasePtr> > >>>> + static _Ptr > >>>> + _S_ptr_to(_BasePtr __this) noexcept > >>>> + { return pointer_traits<_Ptr>::pointer_to(*__this); } > >>> This is also only needed in exactly one place. I avoided needing this > >>> function by adding _M_base_ptr() to the node base classes. > >>> > >>> The whole of this _Rb_tree_ptr_traits class template seems unnecessary > >>> to me. Just inline the code directly into the places it's needed. > >>> You're not optimizing anything by replacing > >>> pointer_traits<T*>::pointer_to with > >>> _Rb_tree_ptr_traits<T*>::_S_ptr_to, it's still a class template > >>> specialization and a function call. > >>> > >>>> + > >>>> + template<typename _BasePtr, typename _UpPtr> > >>>> + static _UpPtr > >>>> + _S_up_ptr_to(_BasePtr __this) noexcept > >>> pointer_to is not guaranteed to be noexcept. > >>> > >>> This appears to be a downcast, i.e. a base-to-derived cast, having > >>> "up" in the name is a bit confusing. > >>> > >>>> + { > >>>> + using __ptr_traits = pointer_traits<_UpPtr>; > >>>> + using __up_type = typename __ptr_traits::element_type; > >>>> + auto __up_this = static_cast<__up_type*>(__this); > >>>> + return __ptr_traits::pointer_to(*__up_this); > >>>> + } > >>>> + }; > >>>> +#else > >>>> + template<typename _Ptr> > >>>> + struct _Rb_tree_ptr_traits; > >>>> +#endif > >>>> > >>>> - static _Const_Base_ptr > >>>> - _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT > >>>> + template<typename _Tp> > >>>> + struct _Rb_tree_ptr_traits<_Tp*> > >>>> { > >>>> - while (__x->_M_left != 0) __x = __x->_M_left; > >>>> - return __x; > >>>> - } > >>>> + template<typename> > >>>> + struct __rebind > >>>> + { typedef _Tp* __type; }; > >>>> + > >>>> + template<typename _BasePtr> > >>>> + static _Tp* > >>>> + _S_ptr_to(_BasePtr __this) _GLIBCXX_NOEXCEPT > >>>> + { return static_cast<_Tp*>(__this); } > >>>> + > >>>> + template<typename _BasePtr, typename _UpPtr> > >>>> + static _UpPtr > >>>> + _S_up_ptr_to(_BasePtr __this) _GLIBCXX_NOEXCEPT > >>>> + { return static_cast<_UpPtr>(__this); } > >>>> + }; > >>>> > >>>> - static _Base_ptr > >>>> - _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT > >>>> + template<typename _BasePtr> > >>>> + struct _Rb_tree_pnode_base > >>>> { > >>>> - while (__x->_M_right != 0) __x = __x->_M_right; > >>>> - return __x; > >>>> - } > >>>> + typedef typename _Rb_tree_ptr_traits<_BasePtr>::template > >>>> + __rebind<_Rb_tree_pnode_base>::__type _Base_ptr; > >>> The names _BasePtr and _Base_ptr are very similar, and confusing. > >>> It looks like sometimes the template argument that is substituted for > >>> _BasePtr is sometimes a derived class (_Rb_tree_node_base) and > >>> sometimes is _ValPtr. It's never a "base" pointer. Please rename it. > >>> > >>>> - static _Const_Base_ptr > >>>> - _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT > >>>> - { > >>>> - while (__x->_M_right != 0) __x = __x->_M_right; > >>>> - return __x; > >>>> - } > >>>> - }; > >>>> + _Base_ptr > >>>> + _M_self_ptr() _GLIBCXX_NOEXCEPT > >>> Why do we need a non-const overload? The const one will work for all > >>> cases, right? > >>> > >>> I added a comment to my list patches pointing out that it's not > >>> const-correct, but is safe as long as only used carefully. > >>> > >>> > >>>> + { return _Rb_tree_ptr_traits<_Base_ptr>::_S_ptr_to(this); } > >>>> + > >>>> + _Base_ptr > >>>> + _M_self_ptr() const _GLIBCXX_NOEXCEPT > >>>> + { > >>>> + _Rb_tree_pnode_base* __self = > >>>> const_cast<_Rb_tree_pnode_base*>(this); > >>>> + return __self->_M_self_ptr(); > >>>> + } > >>>> + > >>>> + template<typename _NodePtr> > >>>> + _NodePtr > >>>> + _M_node_ptr() _GLIBCXX_NOEXCEPT > >>>> + { > >>>> + return _Rb_tree_ptr_traits<_Base_ptr>::template > >>>> + _S_up_ptr_to<_Rb_tree_pnode_base*, _NodePtr>(this); > >>>> + } > >>>> + > >>>> + _Rb_tree_color _M_color; > >>>> + _Base_ptr _M_parent; > >>>> + _Base_ptr _M_left; > >>>> + _Base_ptr _M_right; > >>>> + > >>>> + static _Base_ptr > >>>> + _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT > >>>> + { > >>>> + while (__x->_M_left) __x = __x->_M_left; > >>>> + return __x; > >>>> + } > >>>> + > >>>> + static _Base_ptr > >>>> + _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT > >>>> + { > >>>> + while (__x->_M_right) __x = __x->_M_right; > >>>> + return __x; > >>>> + } > >>>> + }; > >>>> + > >>>> + struct _Rb_tree_node_base > >>>> + : _Rb_tree_pnode_base<_Rb_tree_node_base*> > >>>> + { }; > >>> This approaches means that the existing specializations of RB trees > >>> all get twice as many base classes. I don't see an ABI problem, and it > >>> should generate the same code for optimized builds, but increasing the > >>> inheritance depth and the number of class template instantiations > >>> gives the compiler more work to do, compiling slower, and generating > >>> additional debug info (and maybe RTTI?) > >>> > >>> Please take a look at how I did it for the linked lists, where > >>> specializations for non-fancy pointers, e.g. _List_node<T>, are mostly > >>> unchanged. They don't get any new base classes, just some new typedefs > >>> and new accessors like: > >>> > >>> _Base_ptr _M_base() { return this; } > >>> const _List_node* _M_base() const { return this; } > >>> > >>> The _List_node_traits class template is used bystd::list etc. to > >>> select whether to use _List_node<Alloc::value_type> or > >>> __list::_Node<Alloc::pointer>. All the fancy pointer support is in the > >>> new type hierarchy, __list::_Node_base, __list::_Node, and > >>> __list::_Iterator. The old types like _List_node don't really change. > >>> > >>> I found that using the __list namespace with new types reduced a lot > >>> of confusion I had between the very similar names _List_node and > >>> _List_pnode (or _List_ptr_node, or other names like that). > >>> > >>> Maybe we could call it _List::_Node instead of __list::_Node, so it's > >>> a bit closer to _List_node but still distinguishable (and would > >>> produce very slightly shorter mangled names). I didn't do that, > >>> because our convention is to name impl namespaces as __foo not _Foo. > >>> > >>> That pattern could naturally be extended to __tree::_Node (or > >>> _Tree::_Node) as well. > >>> > >>>> // Helper type offering value initialization guarantee on the > >>>> compare functor. > >>>> template<typename _Key_compare> > >>>> @@ -163,81 +219,108 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > >>>> }; > >>>> > >>>> // Helper type to manage default initialization of node count and > >>>> header. > >>>> - struct _Rb_tree_header > >>>> - { > >>>> - _Rb_tree_node_base _M_header; > >>>> - size_t _M_node_count; // Keeps track of size of tree. > >>>> - > >>>> - _Rb_tree_header() _GLIBCXX_NOEXCEPT > >>>> + template<typename _NodeBase> > >>>> + struct _Rb_tree_pheader > >>>> { > >>>> - _M_header._M_color = _S_red; > >>>> - _M_reset(); > >>>> - } > >>>> + private: > >>>> + typedef typename _NodeBase::_Base_ptr _Base_ptr; > >>>> + > >>>> + public: > >>>> + _NodeBase _M_header; > >>>> + size_t _M_node_count; // Keeps track of size of tree. > >>>> + > >>>> + _Rb_tree_pheader() _GLIBCXX_NOEXCEPT > >>>> + { > >>>> + _M_header._M_color = _S_red; > >>>> + _M_reset(); > >>>> + } > >>>> > >>>> #if __cplusplus >= 201103L > >>>> - _Rb_tree_header(_Rb_tree_header&& __x) noexcept > >>>> - { > >>>> - if (__x._M_header._M_parent != nullptr) > >>>> - _M_move_data(__x); > >>>> - else > >>>> - { > >>>> - _M_header._M_color = _S_red; > >>>> - _M_reset(); > >>>> - } > >>>> - } > >>>> + _Rb_tree_pheader(_Rb_tree_pheader&& __x) noexcept > >>>> + { > >>>> + if (__x._M_header._M_parent) > >>>> + _M_move_data(__x); > >>>> + else > >>>> + { > >>>> + _M_header._M_color = _S_red; > >>>> + _M_reset(); > >>>> + } > >>>> + } > >>>> #endif > >>>> > >>>> - void > >>>> - _M_move_data(_Rb_tree_header& __from) > >>>> - { > >>>> - _M_header._M_color = __from._M_header._M_color; > >>>> - _M_header._M_parent = __from._M_header._M_parent; > >>>> - _M_header._M_left = __from._M_header._M_left; > >>>> - _M_header._M_right = __from._M_header._M_right; > >>>> - _M_header._M_parent->_M_parent = &_M_header; > >>>> - _M_node_count = __from._M_node_count; > >>>> - > >>>> - __from._M_reset(); > >>>> - } > >>>> + void > >>>> + _M_move_data(_Rb_tree_pheader& __from) > >>>> + { > >>>> + _M_header._M_color = __from._M_header._M_color; > >>>> + _M_header._M_parent = __from._M_header._M_parent; > >>>> + _M_header._M_left = __from._M_header._M_left; > >>>> + _M_header._M_right = __from._M_header._M_right; > >>>> + _M_header._M_parent->_M_parent = _M_header._M_self_ptr(); > >>>> + _M_node_count = __from._M_node_count; > >>>> + > >>>> + __from._M_reset(); > >>>> + } > >>>> > >>>> - void > >>>> - _M_reset() > >>>> - { > >>>> - _M_header._M_parent = 0; > >>>> - _M_header._M_left = &_M_header; > >>>> - _M_header._M_right = &_M_header; > >>>> - _M_node_count = 0; > >>>> - } > >>>> - }; > >>>> + void > >>>> + _M_reset() > >>>> + { > >>>> + _M_header._M_parent = _Base_ptr(); > >>>> + _M_header._M_left = _M_header._M_right = _M_header._M_self_ptr(); > >>>> + _M_node_count = 0; > >>>> + } > >>>> + }; > >>>> + > >>>> + struct _Rb_tree_header : _Rb_tree_pheader<_Rb_tree_node_base> > >>>> + { }; > >>>> > >>>> template<typename _Val> > >>>> - struct _Rb_tree_node : public _Rb_tree_node_base > >>>> + struct _Rb_tree_node_val > >>>> { > >>>> - typedef _Rb_tree_node<_Val>* _Link_type; > >>>> - > >>>> #if __cplusplus < 201103L > >>>> _Val _M_value_field; > >>>> > >>>> + __attribute__((__always_inline__)) > >>>> _Val* > >>>> _M_valptr() > >>>> { returnstd::__addressof(_M_value_field); } > >>>> > >>>> + __attribute__((__always_inline__)) > >>>> const _Val* > >>>> _M_valptr() const > >>>> { returnstd::__addressof(_M_value_field); } > >>>> #else > >>>> __gnu_cxx::__aligned_membuf<_Val> _M_storage; > >>> For the new __list::_Node type I took the opportunity to replace > >>> __aligned_membuf with a union { _Val _M_data; }; which is simpler and > >>> produces the same code. We could probably make that change for the > >>> existing node types, I think it's safe, but making it only for the new > >>> _Node type means the old node type isn't affected. > >>> > >>> > >>>> + [[__gnu__::__always_inline__]] > >>>> _Val* > >>>> _M_valptr() > >>>> { return _M_storage._M_ptr(); } > >>>> > >>>> + [[__gnu__::__always_inline__]] > >>>> const _Val* > >>>> _M_valptr() const > >>>> { return _M_storage._M_ptr(); } > >>>> #endif > >>>> }; > >>>> > >>>> + template<typename _Val> > >>>> + struct _Rb_tree_node > >>>> + : _Rb_tree_node_base > >>>> + , _Rb_tree_node_val<_Val> > >>>> + { > >>>> + typedef _Rb_tree_node<_Val>* _Node_ptr; > >>>> + }; > >>>> + > >>>> +#if __cplusplus >= 201103L > >>>> + template<typename _ValPtr> > >>>> + struct _Rb_tree_pnode > >>>> + : _Rb_tree_pnode_base<_ValPtr> > >>> This makes _Rb_tree_pnode_base depend on the value_type, which means > >>> you instantiate a different specialization of _Rb_tree_pnode_base for > >>> every _Rb_tree. There's no point even having a common base class if > >>> every specialization is different. You might as well just put the > >>> _M_parent/_M_left/_M_right pointers in _Rb_tree_pnode directly. > >>> > >>> The point of the node_base class is to have a common base that is not > >>> dependent on the value type, so thatstd::set<int> andstd::set<long> > >>> andstd::set<int, Cmp> all use the same node base. The way this patch > >>> works,std::set<int> will use _Rb_tree_pnode_base<int*> and > >>> std::set<long> will use _Rb_tree_pnode_base<long*>. > >>> > >>> This is why my patch for lists uses __ptr_rebind<_ValPtr, void> as the > >>> template argument to _Node_base, so that they all use > >>> _Node_base<void*>. > >>> > >>> Obviously for a fancy pointer, it will be a different specialization, > >>> sostd::list<int, A<int>> uses _Node_base<A::void_pointer>, but > >>> std::list<long, A<long>> uses the same _Node_base<A::void_pointer>. > >>> > >>>> + , > >>>> _Rb_tree_node_val<typenamestd::pointer_traits<_ValPtr>::element_type> > >>>> + { > >>>> + using _Node_ptr = __ptr_rebind<_ValPtr, _Rb_tree_pnode>; > >>>> + }; > >>>> +#endif > >>>> + > >>>> _GLIBCXX_PURE _Rb_tree_node_base* > >>>> _Rb_tree_increment(_Rb_tree_node_base* __x) throw (); > >>>> > >>> [...] > >>> > >>>> +#if __cplusplus >= 201103L > >>>> + template<typename _ValPtr> > >>>> + struct _Rb_tree_piterator > >>>> + { > >>>> + using __ptr_traits = pointer_traits<_ValPtr>; > >>>> + using value_type = typename __ptr_traits::element_type; > >>>> + using reference = value_type&; > >>>> + using pointer = value_type*; > >>>> + > >>>> + typedef bidirectional_iterator_tag iterator_category; > >>>> + typedef ptrdiff_t difference_type; > >>>> + > >>>> + typedef _Rb_tree_piterator _Self; > >>>> + typedef _Rb_tree_pnode_base<_ValPtr> _Node_base; > >>>> + typedef _Rb_tree_pnode<_ValPtr> _Node_type; > >>>> + typedef typename _Node_type::_Base_ptr _Base_ptr; > >>>> + typedef typename _Node_type::_Node_ptr _Node_ptr; > >>>> + typedef _Rb_tree_helpers<_Node_base> _Tree_helpers; > >>>> + > >>>> + _Rb_tree_piterator() _GLIBCXX_NOEXCEPT > >>>> + : _M_node() { } > >>>> + > >>>> + explicit > >>>> + _Rb_tree_piterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT > >>>> + : _M_node(__x) { } > >>>> + > >>>> + reference > >>>> + operator*() const _GLIBCXX_NOEXCEPT > >>>> + { return *static_cast<_Node_type&>(*_M_node)._M_valptr(); } > >>>> + > >>>> + pointer > >>>> + operator->() const _GLIBCXX_NOEXCEPT > >>>> + { return static_cast<_Node_type&>(*_M_node)._M_valptr(); } > >>>> + > >>>> + _Self& > >>>> + operator++() _GLIBCXX_NOEXCEPT > >>>> + { > >>>> + _M_node = _Tree_helpers::_Increment(_M_node); > >>>> + return *this; > >>>> + } > >>>> + > >>>> + _Self > >>>> + operator++(int) _GLIBCXX_NOEXCEPT > >>>> + { > >>>> + _Self __tmp = *this; > >>>> + _M_node = _Tree_helpers::_Increment(_M_node); > >>>> + return __tmp; > >>>> + } > >>>> + > >>>> + _Self& > >>>> + operator--() _GLIBCXX_NOEXCEPT > >>>> + { > >>>> + _M_node = _Tree_helpers::_Decrement(_M_node); > >>>> + return *this; > >>>> + } > >>>> + > >>>> + _Self > >>>> + operator--(int) _GLIBCXX_NOEXCEPT > >>>> + { > >>>> + _Self __tmp = *this; > >>>> + _M_node = _Tree_helpers::_Decrement(_M_node); > >>>> + return __tmp; > >>>> + } > >>>> + > >>>> + friend bool > >>>> + operator==(const _Self& __x, const _Self& __y) > >>>> _GLIBCXX_NOEXCEPT > >>>> + { return __x._M_node == __y._M_node; } > >>>> + > >>>> +#if ! __cpp_lib_three_way_comparison > >>>> + friend bool > >>>> + operator!=(const _Self& __x, const _Self& __y) > >>>> _GLIBCXX_NOEXCEPT > >>>> + { return __x._M_node != __y._M_node; } > >>>> +#endif > >>>> + > >>>> + _Base_ptr _M_node; > >>>> + }; > >>>> + > >>>> + template<typename _ValPtr> > >>>> + struct _Rb_tree_const_piterator > >>> For the linked lists, I didn't add two new iterator types, just > >>> _Iterator<_Const, _ValPtr> which is used for iterator and > >>> const_iterator. > >>> > >>> It seemed nice not to duplicate the iterator type, since the iterator > >>> and const_iterator are 95% the same. If we don't need to support > >>> C++98, we can write a single iterator implementation. > >>> > >>> If you have a single iterator implementation, you probably don't need > >>> the _Rb_tree_helpers. > >>> > >>> There would still be uses of insert-and-rebalance and > >>> rebalance-for-erase, but those could just be new overloads for fancy > >>> pointers. I don't think we need the _Rb_tree_helpers class template. > >>> > >>> > >>>> + { > >>>> + using __ptr_traits = pointer_traits<_ValPtr>; > >>>> + using value_type = typename __ptr_traits::element_type; > >>>> + using reference = const value_type&; > >>>> + using pointer = const value_type*; > >>>> + > >>>> + typedef _Rb_tree_piterator<_ValPtr> iterator; > >>>> + typedef typenameiterator::_Base_ptr _Base_ptr; > >>>> + > >>>> + typedef bidirectional_iterator_tag iterator_category; > >>>> + typedef ptrdiff_t difference_type; > >>>> + > >>>> + typedef _Rb_tree_const_piterator _Self; > >>>> + typedef _Rb_tree_pnode_base<_ValPtr> _Node_base; > >>>> + typedef _Rb_tree_pnode<_ValPtr> _Node_type; > >>>> + typedef _Rb_tree_helpers<_Node_base> _Tree_helpers; > >>>> + > >>>> + _Rb_tree_const_piterator() _GLIBCXX_NOEXCEPT > >>>> + : _M_node() { } > >>>> + > >>>> + explicit > >>>> + _Rb_tree_const_piterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT > >>>> + : _M_node(__x) { } > >>>> + > >>>> + _Rb_tree_const_piterator(const iterator& __it) > >>>> _GLIBCXX_NOEXCEPT > >>>> + : _M_node(__it._M_node) { } > >>>> + > >>>> + reference > >>>> + operator*() const _GLIBCXX_NOEXCEPT > >>>> + { return *static_cast<_Node_type&>(*_M_node)._M_valptr(); } > >>>> + > >>>> + pointer > >>>> + operator->() const _GLIBCXX_NOEXCEPT > >>>> + { return static_cast<_Node_type&>(*_M_node)._M_valptr(); } > >>>> + > >>>> + _Self& > >>>> + operator++() _GLIBCXX_NOEXCEPT > >>>> + { > >>>> + _M_node = _Tree_helpers::_Increment(_M_node); > >>> You need the iterator increment code here, but you can define it > >>> inline without the _Increment helper. > >>> > >>>> + return *this; > >>>> + } > >>>> + > >>>> + _Self > >>>> + operator++(int) _GLIBCXX_NOEXCEPT > >>>> + { > >>>> + _Self __tmp = *this; > >>>> + _M_node = _Tree_helpers::_Increment(_M_node); > >>> This could just use ++*this. So if there's no separate const iterator > >>> implementation, there's no more use of _Increment. > >>> > >>>> + return __tmp; > >>>> + } > >>>> + > >>>> + _Self& > >>>> + operator--() _GLIBCXX_NOEXCEPT > >>>> + { > >>>> + _M_node = _Tree_helpers::_Decrement(_M_node); > >>>> + return *this; > >>>> + } > >>>> + > >>>> + _Self > >>>> + operator--(int) _GLIBCXX_NOEXCEPT > >>>> + { > >>>> + _Self __tmp = *this; > >>>> + _M_node = _Tree_helpers::_Decrement(_M_node); > >>>> + return __tmp; > >>>> + } > >>>> + > >>>> + friend bool > >>>> + operator==(const _Self& __x, const _Self& __y) > >>>> _GLIBCXX_NOEXCEPT > >>>> + { return __x._M_node == __y._M_node; } > >>>> + > >>>> +#if ! __cpp_lib_three_way_comparison > >>>> + friend bool > >>>> + operator!=(const _Self& __x, const _Self& __y) > >>>> _GLIBCXX_NOEXCEPT > >>>> + { return __x._M_node != __y._M_node; } > >>>> +#endif > >>>> + > >>>> + _Base_ptr _M_node; > >>>> + }; > >>>> +#endif // C++11 > >>>> + > >>>> +#if __cplusplus >= 201103L > >>>> + template<typename _ValPtr> > >>>> + struct _Rb_tree_node_traits > >>>> + { > >>>> + using _Node_base = _Rb_tree_pnode_base<_ValPtr>; > >>>> + using _Node_type = _Rb_tree_pnode<_ValPtr>; > >>>> + using _Header_t = _Rb_tree_pheader<_Node_base>; > >>>> + using _Iterator_t = _Rb_tree_piterator<_ValPtr>; > >>>> + using _Const_iterator_t = _Rb_tree_const_piterator<_ValPtr>; > >>>> + }; > >>>> +#else > >>>> + template<typename _ValPtr> > >>>> + struct _Rb_tree_node_traits; > >>>> +#endif > >>>> + > >>>> + template<typename _Val> > >>>> + struct _Rb_tree_node_traits<_Val*> > >>>> + { > >>>> + typedef _Rb_tree_node_base _Node_base; > >>>> + typedef _Rb_tree_node<_Val> _Node_type; > >>>> + typedef _Rb_tree_header _Header_t; > >>>> + typedef _Rb_tree_iterator<_Val> _Iterator_t; > >>>> + typedef _Rb_tree_const_iterator<_Val> _Const_iterator_t; > >>>> + }; > >>>> > >>>> #if __cplusplus > 201402L > >>>> template<typename _Tree1, typename _Cmp2> > >>>> @@ -424,16 +1068,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > >>>> typename _Compare, typename _Alloc = allocator<_Val> > > >>>> class _Rb_tree > >>>> { > >>>> + typedef typename __gnu_cxx::__alloc_traits<_Alloc>::pointer > >>>> _ValPtr; > >>>> + typedef _Rb_tree_node_traits<_ValPtr> _Node_traits; > >>>> + > >>>> + typedef typename _Node_traits::_Node_base _Node_base; > >>>> + typedef typename _Node_traits::_Node_type _Node_type; > >>>> + > >>>> typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template > >>>> - rebind<_Rb_tree_node<_Val> >::other _Node_allocator; > >>>> + rebind<_Node_type>::other _Node_allocator; > >>>> > >>>> typedef __gnu_cxx::__alloc_traits<_Node_allocator> > >>>> _Alloc_traits; > >>>> > >>>> protected: > >>>> - typedef _Rb_tree_node_base* _Base_ptr; > >>>> - typedef const _Rb_tree_node_base* _Const_Base_ptr; > >>>> - typedef _Rb_tree_node<_Val>* _Link_type; > >>>> - typedef const _Rb_tree_node<_Val>* _Const_Link_type; > >>>> + typedef typename _Node_base::_Base_ptr _Base_ptr; > >>>> + typedef typename _Node_type::_Node_ptr _Node_ptr; > >>> Accessing a member of _Node_type here requires _Node_type to be > >>> complete, which requires _Tp to be complete. That's allowed by the > >>> standard, becausestd::map andstd::set don't support incomplete types > >>> (unlike vector and the linked lists). > >>> > >>> But we don't really ned to instantiate _Node_type here, we could use > >>> _Alloc_traits::pointer instead. > >>> > >>> > >>> [...] > >>> > >>>> @@ -1826,10 +2427,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > >>>> || _M_impl._M_key_compare(_KeyOfValue()(__v), > >>>> _S_key(__p))); > >>>> > >>>> - _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v)); > >>>> + _Base_ptr __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v)); > >>> I think this relies on implicit conversion from _Node_ptr to > >>> _Base_ptr, which is not necessarily possible. It works for the > >>> _Pointer_adapter type in <ext/pointer.h> because it has a > >>> template<typename U> _Pointer_adapter(_Pointer_adapter<U>) constructor > >>> that supports implicit conversions. > >>> > >>> There seems to be a few other places with this problem. Please take a > >>> look at the Pointer type in the new test for my list and forward_list > >>> fancy ptr patches (that Pointer should probably be added to the > >>> testsuite/util/testsuite_allocator.h header for reuse). > >>> > >>> I solved these problems by adding a _M_base_ptr() function to the > >>> node_base type, which means that instead of relying on an implicit > >>> conversion from node_ptr to _Base_ptr you call node_ptr->_M_base_ptr() > >>> to get a _Base_ptr. > >>> > >>>> @@ -2255,7 +2821,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > >>>> } > >>>> else > >>>> // Equivalent keys. > >>>> - return _Res(__pos._M_node, 0); > >>>> + return _Res(__position._M_node, 0); > >>>> } > >>>> > >>>> template<typename _Key, typename _Val, typename _KeyOfValue, > >>>> @@ -2294,11 +2860,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > >>>> _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: > >>>> _M_get_insert_hint_equal_pos(const_iterator __position, const > >>>> key_type& __k) > >>>> { > >>>> - iterator __pos = __position._M_const_cast(); > >>> This removes __pos ... > >>> > >>>> typedef pair<_Base_ptr, _Base_ptr> _Res; > >>>> > >>>> // end() > >>>> - if (__pos._M_node == _M_end()) > >>>> + if (__position._M_node == _M_end()) > >>>> { > >>>> if (size() > 0 > >>>> && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost()))) > >>>> @@ -2306,18 +2871,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > >>>> else > >>>> return _M_get_insert_equal_pos(__k); > >>>> } > >>>> - else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) > >>>> + else if (!_M_impl._M_key_compare(_S_key(__position._M_node), > >>>> __k)) > >>>> { > >>>> // First, try before... > >>>> iterator __before = __pos; > >>> But it's still used here. > >>> > >>>> - if (__pos._M_node == _M_leftmost()) // begin() > >>>> + if (__position._M_node == _M_leftmost()) // begin() > >>>> return _Res(_M_leftmost(), _M_leftmost()); > >>>> else if (!_M_impl._M_key_compare(__k, > >>>> _S_key((--__before)._M_node))) > >>>> { > >>>> if (_S_right(__before._M_node) == 0) > >>>> return _Res(0, __before._M_node); > >>>> else > >>>> - return _Res(__pos._M_node, __pos._M_node); > >>>> + return _Res(__position._M_node, __position._M_node); > >>>> } > >>>> else > >>>> return _M_get_insert_equal_pos(__k); > >>>> @@ -2326,12 +2891,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > >>>> { > >>>> // ... then try after. > >>>> iterator __after = __pos; > >>> And here. > >>> > >>> I think they should both be __position._M_const_cast(). > >>> > >>> > >>>> diff --git > >>>> a/libstdc++-v3/testsuite/23_containers/map/allocator/ext_ptr.cc > >>>> b/libstdc++-v3/testsuite/23_containers/map/allocator/ext_ptr.cc > >>>> new file mode 100644 > >>>> index 00000000000..758beedccfd > >>>> --- /dev/null > >>>> +++ b/libstdc++-v3/testsuite/23_containers/map/allocator/ext_ptr.cc > >>>> @@ -0,0 +1,44 @@ > >>>> +// { dg-do run { target c++11 } } > >>>> + > >>>> +#include <map> > >>>> +#include <memory> > >>>> +#include <testsuite_hooks.h> > >>>> +#include <testsuite_allocator.h> > >>>> + > >>>> +struct T { int i; }; > >>>> + > >>>> +bool operator<(const T& l, const T& r) > >>>> +{ return l.i < r.i; } > >>>> + > >>>> +struct H > >>> This struct H occurs in several tests but seems to be unused. > >>> > >>>> +{ > >>>> +std::size_t > >>>> + operator()(const T& t) const noexcept > >>>> + { return t.i; } > >>>> +}; > >>>> + > >>>> +struct L :std::less<T> > >>>> +{ }; > >>>> + > >>>> +using __gnu_test::CustomPointerAlloc; > >>>> + > >>>> +template classstd::map<T, int, L, > >>>> + CustomPointerAlloc<std::pair<const T, int>>>; > >>>> + > >>>> +void test01() > >>>> +{ > >>>> + typedef CustomPointerAlloc<std::pair<const T, int>> alloc_type; > >>>> + typedefstd::map<T, int, L, alloc_type> test_type; > >>>> + test_type v; > >>>> + v.insert({ T(), 0 }); > >>>> + VERIFY( v.begin()->second == 0 ); > >>>> + VERIFY( ++v.begin() == v.end() ); > >>>> + v.insert({ T { 1 }, 1 }); > >>>> + VERIFY( v.size() == 2 ); > >>>> + VERIFY( v.find(T()) != v.end() ); > >>>> +} > >>>> + > >>>> +int main() > >>>> +{ > >>>> + test01(); > >>>> +} > >>> I'd be interested on your opinion on my patches for fancy pointer > >>> support in the linked lists. I think it's cleaner and requires fewer > >>> changes to the existing specializations. > >>> > >>> My changes can also be disabled by a macro (to avoid breaking any > >>> users who are somehow managing to use allocators-with-fancy-pointers > >>> with RB trees today, which could be useful unless that's completely > >>> broken today), and to be enabled for non-fancy pointers (for test > >>> coverage). > >>> > > >diff --git a/libstdc++-v3/include/bits/stl_tree.h > >b/libstdc++-v3/include/bits/stl_tree.h > >index bc27e191e8b..bed7266c688 100644 > >--- a/libstdc++-v3/include/bits/stl_tree.h > >+++ b/libstdc++-v3/include/bits/stl_tree.h > >@@ -66,6 +66,7 @@ > > #include <bits/allocator.h> > > #include <bits/stl_function.h> > > #include <bits/cpp_type_traits.h> > >+#include <bits/ptr_traits.h> > > #include <ext/alloc_traits.h> > > #if __cplusplus >= 201103L > > # include <ext/aligned_buffer.h> > >@@ -74,6 +75,13 @@ > > # include <bits/node_handle.h> > > #endif > > > >+#if __cplusplus < 201103L > >+# undef _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE > >+# define _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 0 > >+#elif ! defined _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE > >+# define _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE 1 > >+#endif > >+ > > namespace std _GLIBCXX_VISIBILITY(default) > > { > > _GLIBCXX_BEGIN_NAMESPACE_VERSION > >@@ -99,7 +107,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > struct _Rb_tree_node_base > > { > > typedef _Rb_tree_node_base* _Base_ptr; > >- typedef const _Rb_tree_node_base* _Const_Base_ptr; > > > > _Rb_tree_color _M_color; > > _Base_ptr _M_parent; > >@@ -113,13 +120,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > return __x; > > } > > > >- static _Const_Base_ptr > >- _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT > >- { > >- while (__x->_M_left != 0) __x = __x->_M_left; > >- return __x; > >- } > >- > > static _Base_ptr > > _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT > > { > >@@ -127,12 +127,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > return __x; > > } > > > >- static _Const_Base_ptr > >- _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT > >- { > >- while (__x->_M_right != 0) __x = __x->_M_right; > >- return __x; > >- } > >+ // This is not const-correct, but it's only used in a const access path > >+ // by std::_Rb_tree::_M_end() where the pointer is used to initialize a > >+ // const_iterator and so constness is restored. > >+ _Base_ptr > >+ _M_base_ptr() const _GLIBCXX_NOEXCEPT > >+ { return const_cast<_Rb_tree_node_base*>(this); } > >+ > >+ template<typename _NodePtr> > >+ _NodePtr > >+ _M_node_ptr() _GLIBCXX_NOEXCEPT > >+ { return static_cast<_NodePtr>(this); } > > }; > > > > // Helper type offering value initialization guarantee on the compare > > functor. > >@@ -213,7 +218,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > template<typename _Val> > > struct _Rb_tree_node : public _Rb_tree_node_base > > { > >- typedef _Rb_tree_node<_Val>* _Link_type; > >+ typedef _Rb_tree_node<_Val>* _Node_ptr; > > > > #if __cplusplus < 201103L > > _Val _M_value_field; > >@@ -238,18 +243,136 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > #endif > > }; > > > >+#if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE > >+namespace __rb_tree > >+{ > >+ template<typename _VoidPtr> > >+ struct _Node_base > >+ { > >+ using _Base_ptr = __ptr_rebind<_VoidPtr, _Node_base>; > >+ > >+ _Rb_tree_color _M_color; > >+ _Base_ptr _M_parent; > >+ _Base_ptr _M_left; > >+ _Base_ptr _M_right; > >+ > >+ static _Base_ptr > >+ _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT > >+ { > >+ while (__x->_M_left) __x = __x->_M_left; > >+ return __x; > >+ } > >+ > >+ static _Base_ptr > >+ _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT > >+ { > >+ while (__x->_M_right) __x = __x->_M_right; > >+ return __x; > >+ } > >+ > >+ // This is not const-correct, but it's only used in a const access > >path > >+ // by std::_Rb_tree::_M_end() where the pointer is used to initialize > >a > >+ // const_iterator and so constness is restored. > >+ _Base_ptr > >+ _M_base_ptr() const > >+ { > >+ return pointer_traits<_Base_ptr>::pointer_to > >+ (*const_cast<_Node_base*>(this)); > >+ } > >+ > >+ template<typename _NodePtr> > >+ _NodePtr > >+ _M_node_ptr() _GLIBCXX_NOEXCEPT > >+ { > >+ using __ptr_traits = pointer_traits<_NodePtr>; > >+ using __node_type = typename __ptr_traits::element_type; > >+ auto __this = static_cast<__node_type*>(this); > >+ return __ptr_traits::pointer_to(*__this); > >+ } > >+ }; > >+ > >+ // Helper type to manage default initialization of node count and header. > >+ template<typename _NodeBase> > >+ struct _Header > >+ { > >+ private: > >+ using _Base_ptr = typename _NodeBase::_Base_ptr; > >+ > >+ public: > >+ _NodeBase _M_header; > >+ size_t _M_node_count; // Keeps track of size of tree. > >+ > >+ _Header() noexcept > >+ { > >+ _M_header._M_color = _S_red; > >+ _M_reset(); > >+ } > >+ > >+ _Header(_Header&& __x) noexcept > >+ { > >+ if (__x._M_header._M_parent) > >+ _M_move_data(__x); > >+ else > >+ { > >+ _M_header._M_color = _S_red; > >+ _M_reset(); > >+ } > >+ } > >+ > >+ void > >+ _M_move_data(_Header& __from) > >+ { > >+ _M_header._M_color = __from._M_header._M_color; > >+ _M_header._M_parent = __from._M_header._M_parent; > >+ _M_header._M_left = __from._M_header._M_left; > >+ _M_header._M_right = __from._M_header._M_right; > >+ _M_header._M_parent->_M_parent = _M_header._M_base_ptr(); > >+ _M_node_count = __from._M_node_count; > >+ > >+ __from._M_reset(); > >+ } > >+ > >+ void > >+ _M_reset() > >+ { > >+ _M_header._M_parent = _Base_ptr{}; > >+ _M_header._M_left = _M_header._M_right = _M_header._M_base_ptr(); > >+ _M_node_count = 0; > >+ } > >+ }; > >+ > >+ template<typename _ValPtr> > >+ struct _Node : public __rb_tree::_Node_base<__ptr_rebind<_ValPtr, void>> > >+ { > >+ using value_type = typename pointer_traits<_ValPtr>::element_type; > >+ using _Node_ptr = __ptr_rebind<_ValPtr, _Node>; > >+ > >+ union > >+ { > >+ value_type _M_storage; > >+ }; > >+ > >+ _Node() { } > >+ ~_Node() { } > >+ _Node(_Node&&) = delete; > >+ > >+ value_type* > >+ _M_valptr() > >+ { return std::__addressof(_M_storage); } > >+ > >+ value_type const* > >+ _M_valptr() const > >+ { return std::__addressof(_M_storage); } > >+ }; > >+} // namespace __rb_tree > >+#endif > >+ > > _GLIBCXX_PURE _Rb_tree_node_base* > > _Rb_tree_increment(_Rb_tree_node_base* __x) throw (); > > > >- _GLIBCXX_PURE const _Rb_tree_node_base* > >- _Rb_tree_increment(const _Rb_tree_node_base* __x) throw (); > >- > > _GLIBCXX_PURE _Rb_tree_node_base* > > _Rb_tree_decrement(_Rb_tree_node_base* __x) throw (); > > > >- _GLIBCXX_PURE const _Rb_tree_node_base* > >- _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw (); > >- > > template<typename _Tp> > > struct _Rb_tree_iterator > > { > >@@ -260,9 +383,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > typedef bidirectional_iterator_tag iterator_category; > > typedef ptrdiff_t difference_type; > > > >- typedef _Rb_tree_iterator<_Tp> _Self; > > typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; > >- typedef _Rb_tree_node<_Tp>* _Link_type; > >+ typedef _Rb_tree_node<_Tp>* _Node_ptr; > > > > _Rb_tree_iterator() _GLIBCXX_NOEXCEPT > > : _M_node() { } > >@@ -273,49 +395,51 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > > > reference > > operator*() const _GLIBCXX_NOEXCEPT > >- { return *static_cast<_Link_type>(_M_node)->_M_valptr(); } > >+ { return *static_cast<_Node_ptr>(_M_node)->_M_valptr(); } > > > > pointer > > operator->() const _GLIBCXX_NOEXCEPT > >- { return static_cast<_Link_type> (_M_node)->_M_valptr(); } > >+ { return static_cast<_Node_ptr>(_M_node)->_M_valptr(); } > > > >- _Self& > >+ _Rb_tree_iterator& > > operator++() _GLIBCXX_NOEXCEPT > > { > > _M_node = _Rb_tree_increment(_M_node); > > return *this; > > } > > > >- _Self > >+ _Rb_tree_iterator > > operator++(int) _GLIBCXX_NOEXCEPT > > { > >- _Self __tmp = *this; > >+ _Rb_tree_iterator __tmp = *this; > > _M_node = _Rb_tree_increment(_M_node); > > return __tmp; > > } > > > >- _Self& > >+ _Rb_tree_iterator& > > operator--() _GLIBCXX_NOEXCEPT > > { > > _M_node = _Rb_tree_decrement(_M_node); > > return *this; > > } > > > >- _Self > >+ _Rb_tree_iterator > > operator--(int) _GLIBCXX_NOEXCEPT > > { > >- _Self __tmp = *this; > >+ _Rb_tree_iterator __tmp = *this; > > _M_node = _Rb_tree_decrement(_M_node); > > return __tmp; > > } > > > > friend bool > >- operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT > >+ operator==(const _Rb_tree_iterator& __x, > >+ const _Rb_tree_iterator& __y) _GLIBCXX_NOEXCEPT > > { return __x._M_node == __y._M_node; } > > > > #if ! __cpp_lib_three_way_comparison > > friend bool > >- operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT > >+ operator!=(const _Rb_tree_iterator& __x, > >+ const _Rb_tree_iterator& __y) _GLIBCXX_NOEXCEPT > > { return __x._M_node != __y._M_node; } > > #endif > > > >@@ -334,9 +458,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > typedef bidirectional_iterator_tag iterator_category; > > typedef ptrdiff_t difference_type; > > > >- typedef _Rb_tree_const_iterator<_Tp> _Self; > >- typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr; > >- typedef const _Rb_tree_node<_Tp>* _Link_type; > >+ typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; > >+ typedef const _Rb_tree_node<_Tp>* _Node_ptr; > > > > _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT > > : _M_node() { } > >@@ -348,55 +471,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT > > : _M_node(__it._M_node) { } > > > >- iterator > >- _M_const_cast() const _GLIBCXX_NOEXCEPT > >- { return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); > >} > >- > > reference > > operator*() const _GLIBCXX_NOEXCEPT > >- { return *static_cast<_Link_type>(_M_node)->_M_valptr(); } > >+ { return *static_cast<_Node_ptr>(_M_node)->_M_valptr(); } > > > > pointer > > operator->() const _GLIBCXX_NOEXCEPT > >- { return static_cast<_Link_type>(_M_node)->_M_valptr(); } > >+ { return static_cast<_Node_ptr>(_M_node)->_M_valptr(); } > > > >- _Self& > >+ _Rb_tree_const_iterator& > > operator++() _GLIBCXX_NOEXCEPT > > { > > _M_node = _Rb_tree_increment(_M_node); > > return *this; > > } > > > >- _Self > >+ _Rb_tree_const_iterator > > operator++(int) _GLIBCXX_NOEXCEPT > > { > >- _Self __tmp = *this; > >+ _Rb_tree_const_iterator __tmp = *this; > > _M_node = _Rb_tree_increment(_M_node); > > return __tmp; > > } > > > >- _Self& > >+ _Rb_tree_const_iterator& > > operator--() _GLIBCXX_NOEXCEPT > > { > > _M_node = _Rb_tree_decrement(_M_node); > > return *this; > > } > > > >- _Self > >+ _Rb_tree_const_iterator > > operator--(int) _GLIBCXX_NOEXCEPT > > { > >- _Self __tmp = *this; > >+ _Rb_tree_const_iterator __tmp = *this; > > _M_node = _Rb_tree_decrement(_M_node); > > return __tmp; > > } > > > > friend bool > >- operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT > >+ operator==(const _Rb_tree_const_iterator& __x, > >+ const _Rb_tree_const_iterator& __y) _GLIBCXX_NOEXCEPT > > { return __x._M_node == __y._M_node; } > > > > #if ! __cpp_lib_three_way_comparison > > friend bool > >- operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT > >+ operator!=(const _Rb_tree_const_iterator& __x, > >+ const _Rb_tree_const_iterator& __y) _GLIBCXX_NOEXCEPT > > { return __x._M_node != __y._M_node; } > > #endif > > > >@@ -415,6 +536,485 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, > > _Rb_tree_node_base& __header) throw (); > > > >+namespace __rb_tree > >+{ > >+#if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE > >+ template<bool _Const, typename _ValPtr> > >+ struct _Iterator > >+ { > >+ template<typename _Tp> > >+ using __maybe_const = __conditional_t<_Const, const _Tp, _Tp>; > >+ > >+ using __ptr_traits = pointer_traits<_ValPtr>; > >+ using value_type = typename __ptr_traits::element_type; > >+ using reference = __maybe_const<value_type>&; > >+ using pointer = __maybe_const<value_type>*; > >+ > >+ using iterator_category = bidirectional_iterator_tag; > >+ using difference_type = ptrdiff_t; > >+ > >+ using _Node = __rb_tree::_Node<_ValPtr>; > >+ using _Node_base = __rb_tree::_Node_base<__ptr_rebind<_ValPtr, void>>; > >+ using _Base_ptr = typename _Node_base::_Base_ptr; > >+ > >+ _Iterator() _GLIBCXX_NOEXCEPT > >+ : _M_node() { } > >+ > >+ constexpr explicit > >+ _Iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT > >+ : _M_node(__x) { } > >+ > >+#if __cplusplus >= 201103L > >+ _Iterator(const _Iterator&) = default; > >+ _Iterator& operator=(const _Iterator&) = default; > >+#endif > >+ > >+#ifdef __glibcxx_concepts > >+ constexpr > >+ _Iterator(const _Iterator<false, _ValPtr>& __it) requires _Const > >+#else > >+ template<bool _OtherConst, > >+ typename = __enable_if_t<_Const && !_OtherConst>> > >+ constexpr > >+ _Iterator(const _Iterator<_OtherConst, _ValPtr>& __it) > >+#endif > >+ : _M_node(__it._M_node) { } > >+ > >+ [[__nodiscard__]] > >+ reference > >+ operator*() const _GLIBCXX_NOEXCEPT > >+ { return *static_cast<_Node&>(*_M_node)._M_valptr(); } > >+ > >+ [[__nodiscard__]] > >+ pointer > >+ operator->() const _GLIBCXX_NOEXCEPT > >+ { return static_cast<_Node&>(*_M_node)._M_valptr(); } > >+ > >+ _GLIBCXX14_CONSTEXPR _Iterator& > >+ operator++() _GLIBCXX_NOEXCEPT > >+ { > >+ if (_M_node->_M_right) > >+ { > >+ _M_node = _M_node->_M_right; > >+ while (_M_node->_M_left) > >+ _M_node = _M_node->_M_left; > >+ } > >+ else > >+ { > >+ _Base_ptr __y = _M_node->_M_parent; > >+ while (_M_node == __y->_M_right) > >+ { > >+ _M_node = __y; > >+ __y = __y->_M_parent; > >+ } > >+ if (_M_node->_M_right != __y) > >+ _M_node = __y; > >+ } > >+ > >+ return *this; > >+ } > >+ > >+ _GLIBCXX14_CONSTEXPR _Iterator > >+ operator++(int) _GLIBCXX_NOEXCEPT > >+ { > >+ _Iterator __tmp(this->_M_node); > >+ ++*this; > >+ return __tmp; > >+ } > >+ > >+ _GLIBCXX14_CONSTEXPR _Iterator& > >+ operator--() _GLIBCXX_NOEXCEPT > >+ { > >+ if (_M_node->_M_color == _S_red > >+ && _M_node->_M_parent->_M_parent == _M_node) > >+ _M_node = _M_node->_M_right; > >+ else if (_M_node->_M_left) > >+ { > >+ _Base_ptr __y = _M_node->_M_left; > >+ while (__y->_M_right) > >+ __y = __y->_M_right; > >+ _M_node = __y; > >+ } > >+ else > >+ { > >+ _Base_ptr __y = _M_node->_M_parent; > >+ while (_M_node == __y->_M_left) > >+ { > >+ _M_node = __y; > >+ __y = __y->_M_parent; > >+ } > >+ _M_node = __y; > >+ } > >+ return *this; > >+ } > >+ > >+ _GLIBCXX14_CONSTEXPR _Iterator > >+ operator--(int) _GLIBCXX_NOEXCEPT > >+ { > >+ _Iterator __tmp(this->_M_node); > >+ --*this; > >+ return __tmp; > >+ } > >+ > >+ [[__nodiscard__]] > >+ friend bool > >+ operator==(const _Iterator& __x, const _Iterator& __y) > >_GLIBCXX_NOEXCEPT > >+ { return __x._M_node == __y._M_node; } > >+ > >+#if ! __cpp_lib_three_way_comparison > >+ [[__nodiscard__]] > >+ friend bool > >+ operator!=(const _Iterator& __x, const _Iterator& __y) > >_GLIBCXX_NOEXCEPT > >+ { return __x._M_node != __y._M_node; } > >+#endif > >+ > >+ _Base_ptr _M_node; > >+ }; > >+#endif // USE_ALLOC_PTR_FOR_RB_TREE > >+ > >+ // Determine the node and iterator types used by std::_Rb_tree. > >+ template<typename _Val, typename _Ptr> > >+ struct _Node_traits; > >+ > >+#if _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE <= 9000 > >+ // Specialization for the simple case where the allocator's pointer type > >+ // is the same type as value_type*. > >+ // For ABI compatibility we can't change the types used for this case. > >+ template<typename _Val> > >+ struct _Node_traits<_Val, _Val*> > >+ { > >+ typedef _Rb_tree_node<_Val> _Node; > >+ typedef _Rb_tree_node_base _Node_base; > >+ typedef _Rb_tree_header _Header_t; > >+ typedef _Rb_tree_iterator<_Val> _Iterator; > >+ typedef _Rb_tree_const_iterator<_Val> _Const_iterator; > >+ > >+ __attribute__((__nonnull__)) > >+ static void > >+ _S_insert_and_rebalance(const bool __insert_left, > >+ _Node_base* __x, _Node_base* __p, > >+ _Node_base& __header) _GLIBCXX_USE_NOEXCEPT > >+ { > >+ return _Rb_tree_insert_and_rebalance(__insert_left, __x, __p, > >__header); > >+ } > >+ > >+ __attribute__((__nonnull__,__returns_nonnull__)) > >+ static _Node_base* > >+ _S_rebalance_for_erase(_Node_base* const __z, > >+ _Node_base& __header) _GLIBCXX_USE_NOEXCEPT > >+ { return _Rb_tree_rebalance_for_erase(__z, __header); } > >+ }; > >+#endif > >+ > >+#if ! _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE > >+ // Always use the T* specialization. > >+ template<typename _Val, typename _Ptr> > >+ struct _Node_traits > >+ : _Node_traits<_Val, _Val*> > >+ { }; > >+#else > >+ // Primary template used when the allocator uses fancy pointers. > >+ template<typename _Val, typename _ValPtr> > >+ struct _Node_traits > >+ { > >+ using _Node = __rb_tree::_Node<_ValPtr>; > >+ using _Node_base = __rb_tree::_Node_base<__ptr_rebind<_ValPtr, void>>; > >+ using _Header_t = __rb_tree::_Header<_Node_base>; > >+ using _Iterator = __rb_tree::_Iterator<false, _ValPtr>; > >+ using _Const_iterator = __rb_tree::_Iterator<true, _ValPtr>; > >+ > >+ using _Base_ptr = typename _Node_base::_Base_ptr; > >+ > >+ static void > >+ _Rotate_left(_Base_ptr __x, _Base_ptr& __root) > >+ { > >+ const _Base_ptr __y = __x->_M_right; > >+ > >+ __x->_M_right = __y->_M_left; > >+ if (__y->_M_left) > >+ __y->_M_left->_M_parent = __x; > >+ __y->_M_parent = __x->_M_parent; > >+ > >+ if (__x == __root) > >+ __root = __y; > >+ else if (__x == __x->_M_parent->_M_left) > >+ __x->_M_parent->_M_left = __y; > >+ else > >+ __x->_M_parent->_M_right = __y; > >+ __y->_M_left = __x; > >+ __x->_M_parent = __y; > >+ } > >+ > >+ static void > >+ _Rotate_right(_Base_ptr __x, _Base_ptr& __root) > >+ { > >+ const _Base_ptr __y = __x->_M_left; > >+ > >+ __x->_M_left = __y->_M_right; > >+ if (__y->_M_right) > >+ __y->_M_right->_M_parent = __x; > >+ __y->_M_parent = __x->_M_parent; > >+ > >+ if (__x == __root) > >+ __root = __y; > >+ else if (__x == __x->_M_parent->_M_right) > >+ __x->_M_parent->_M_right = __y; > >+ else > >+ __x->_M_parent->_M_left = __y; > >+ __y->_M_right = __x; > >+ __x->_M_parent = __y; > >+ } > >+ > >+ static void > >+ _S_insert_and_rebalance(const bool __insert_left, > >+ _Base_ptr __x, _Base_ptr __p, > >+ _Node_base& __header) > >+ { > >+ _Base_ptr& __root = __header._M_parent; > >+ > >+ // Initialize fields in new node to insert. > >+ __x->_M_parent = __p; > >+ __x->_M_left = __x->_M_right = nullptr; > >+ __x->_M_color = _S_red; > >+ > >+ // Insert. > >+ // Make new node child of parent and maintain root, leftmost and > >+ // rightmost nodes. > >+ // N.B. First node is always inserted left. > >+ if (__insert_left) > >+ { > >+ __p->_M_left = __x; // also makes leftmost = __x when __p == > >&__header > >+ > >+ if (std::__to_address(__p) == std::addressof(__header)) > >+ { > >+ __header._M_parent = __x; > >+ __header._M_right = __x; > >+ } > >+ else if (__p == __header._M_left) > >+ __header._M_left = __x; // maintain leftmost pointing to min > >node > >+ } > >+ else > >+ { > >+ __p->_M_right = __x; > >+ > >+ if (__p == __header._M_right) > >+ __header._M_right = __x; // maintain rightmost pointing to max > >node > >+ } > >+ // Rebalance. > >+ while (__x != __root > >+ && __x->_M_parent->_M_color == _S_red) > >+ { > >+ const _Base_ptr __xpp = __x->_M_parent->_M_parent; > >+ > >+ if (__x->_M_parent == __xpp->_M_left) > >+ { > >+ const _Base_ptr __y = __xpp->_M_right; > >+ if (__y && __y->_M_color == _S_red) > >+ { > >+ __x->_M_parent->_M_color = _S_black; > >+ __y->_M_color = _S_black; > >+ __xpp->_M_color = _S_red; > >+ __x = __xpp; > >+ } > >+ else > >+ { > >+ if (__x == __x->_M_parent->_M_right) > >+ { > >+ __x = __x->_M_parent; > >+ _Rotate_left(__x, __root); > >+ } > >+ __x->_M_parent->_M_color = _S_black; > >+ __xpp->_M_color = _S_red; > >+ _Rotate_right(__xpp, __root); > >+ } > >+ } > >+ else > >+ { > >+ const _Base_ptr __y = __xpp->_M_left; > >+ if (__y && __y->_M_color == _S_red) > >+ { > >+ __x->_M_parent->_M_color = _S_black; > >+ __y->_M_color = _S_black; > >+ __xpp->_M_color = _S_red; > >+ __x = __xpp; > >+ } > >+ else > >+ { > >+ if (__x == __x->_M_parent->_M_left) > >+ { > >+ __x = __x->_M_parent; > >+ _Rotate_right(__x, __root); > >+ } > >+ __x->_M_parent->_M_color = _S_black; > >+ __xpp->_M_color = _S_red; > >+ _Rotate_left(__xpp, __root); > >+ } > >+ } > >+ } > >+ __root->_M_color = _S_black; > >+ } > >+ > >+ static _Base_ptr > >+ _S_rebalance_for_erase(_Base_ptr __z, _Node_base& __header) > >+ { > >+ _Base_ptr& __root = __header._M_parent; > >+ _Base_ptr& __leftmost = __header._M_left; > >+ _Base_ptr& __rightmost = __header._M_right; > >+ _Base_ptr __y = __z; > >+ _Base_ptr __x{}; > >+ _Base_ptr __x_parent{}; > >+ > >+ if (!__y->_M_left) // __z has at most one non-null child. y == z. > >+ __x = __y->_M_right; // __x might be null. > >+ else > >+ if (!__y->_M_right) // __z has exactly one non-null child. y == z. > >+ __x = __y->_M_left; // __x is not null. > >+ else > >+ { > >+ // __z has two non-null children. Set __y to > >+ __y = __y->_M_right; // __z's successor. __x might be null. > >+ while (__y->_M_left) > >+ __y = __y->_M_left; > >+ __x = __y->_M_right; > >+ } > >+ if (__y != __z) > >+ { > >+ // relink y in place of z. y is z's successor > >+ __z->_M_left->_M_parent = __y; > >+ __y->_M_left = __z->_M_left; > >+ if (__y != __z->_M_right) > >+ { > >+ __x_parent = __y->_M_parent; > >+ if (__x) > >+ __x->_M_parent = __y->_M_parent; > >+ __y->_M_parent->_M_left = __x; // __y must be a child of > >_M_left > >+ __y->_M_right = __z->_M_right; > >+ __z->_M_right->_M_parent = __y; > >+ } > >+ else > >+ __x_parent = __y; > >+ if (__root == __z) > >+ __root = __y; > >+ else if (__z->_M_parent->_M_left == __z) > >+ __z->_M_parent->_M_left = __y; > >+ else > >+ __z->_M_parent->_M_right = __y; > >+ __y->_M_parent = __z->_M_parent; > >+ std::swap(__y->_M_color, __z->_M_color); > >+ __y = __z; > >+ // __y now points to node to be actually deleted > >+ } > >+ else > >+ { // __y == __z > >+ __x_parent = __y->_M_parent; > >+ if (__x) > >+ __x->_M_parent = __y->_M_parent; > >+ if (__root == __z) > >+ __root = __x; > >+ else > >+ if (__z->_M_parent->_M_left == __z) > >+ __z->_M_parent->_M_left = __x; > >+ else > >+ __z->_M_parent->_M_right = __x; > >+ if (__leftmost == __z) > >+ { > >+ if (!__z->_M_right) // __z->_M_left must be null also > >+ __leftmost = __z->_M_parent; > >+ // makes __leftmost == _M_header if __z == __root > >+ else > >+ __leftmost = _Node_base::_S_minimum(__x); > >+ } > >+ if (__rightmost == __z) > >+ { > >+ if (__z->_M_left == 0) // __z->_M_right must be null > >also > >+ __rightmost = __z->_M_parent; > >+ // makes __rightmost == _M_header if __z == __root > >+ else // __x == __z->_M_left > >+ __rightmost = _Node_base::_S_maximum(__x); > >+ } > >+ } > >+ if (__y->_M_color != _S_red) > >+ { > >+ while (__x != __root && (__x == 0 || __x->_M_color == _S_black)) > >+ if (__x == __x_parent->_M_left) > >+ { > >+ _Base_ptr __w = __x_parent->_M_right; > >+ if (__w->_M_color == _S_red) > >+ { > >+ __w->_M_color = _S_black; > >+ __x_parent->_M_color = _S_red; > >+ _Rotate_left(__x_parent, __root); > >+ __w = __x_parent->_M_right; > >+ } > >+ if ((!__w->_M_left || __w->_M_left->_M_color == _S_black) && > >+ (!__w->_M_right || __w->_M_right->_M_color == _S_black)) > >+ { > >+ __w->_M_color = _S_red; > >+ __x = __x_parent; > >+ __x_parent = __x_parent->_M_parent; > >+ } > >+ else > >+ { > >+ if (!__w->_M_right || __w->_M_right->_M_color == > >_S_black) > >+ { > >+ __w->_M_left->_M_color = _S_black; > >+ __w->_M_color = _S_red; > >+ _Rotate_right(__w, __root); > >+ __w = __x_parent->_M_right; > >+ } > >+ __w->_M_color = __x_parent->_M_color; > >+ __x_parent->_M_color = _S_black; > >+ if (__w->_M_right) > >+ __w->_M_right->_M_color = _S_black; > >+ _Rotate_left(__x_parent, __root); > >+ break; > >+ } > >+ } > >+ else > >+ { > >+ // same as above, with _M_right <-> _M_left. > >+ _Base_ptr __w = __x_parent->_M_left; > >+ if (__w->_M_color == _S_red) > >+ { > >+ __w->_M_color = _S_black; > >+ __x_parent->_M_color = _S_red; > >+ _Rotate_right(__x_parent, __root); > >+ __w = __x_parent->_M_left; > >+ } > >+ if ((!__w->_M_right || __w->_M_right->_M_color == _S_black) > >&& > >+ (!__w->_M_left || __w->_M_left->_M_color == _S_black)) > >+ { > >+ __w->_M_color = _S_red; > >+ __x = __x_parent; > >+ __x_parent = __x_parent->_M_parent; > >+ } > >+ else > >+ { > >+ if (!__w->_M_left || __w->_M_left->_M_color == _S_black) > >+ { > >+ __w->_M_right->_M_color = _S_black; > >+ __w->_M_color = _S_red; > >+ _Rotate_left(__w, __root); > >+ __w = __x_parent->_M_left; > >+ } > >+ __w->_M_color = __x_parent->_M_color; > >+ __x_parent->_M_color = _S_black; > >+ if (__w->_M_left) > >+ __w->_M_left->_M_color = _S_black; > >+ _Rotate_right(__x_parent, __root); > >+ break; > >+ } > >+ } > >+ if (__x) > >+ __x->_M_color = _S_black; > >+ } > >+ > >+ return __y; > >+ } > >+ }; > >+#endif > >+} // namespace __rb_tree > >+ > > #if __cplusplus > 201402L > > template<typename _Tree1, typename _Cmp2> > > struct _Rb_tree_merge_helper { }; > >@@ -425,15 +1025,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > class _Rb_tree > > { > > typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template > >- rebind<_Rb_tree_node<_Val> >::other _Node_allocator; > >+ rebind<_Val>::other _Val_alloc_type; > >+ > >+ typedef __gnu_cxx::__alloc_traits<_Val_alloc_type> _Val_alloc_traits; > >+ typedef typename _Val_alloc_traits::pointer _ValPtr; > >+ typedef __rb_tree::_Node_traits<_Val, _ValPtr> _Node_traits; > >+ > >+ typedef typename _Node_traits::_Node_base _Node_base; > >+ typedef typename _Node_traits::_Node _Node; > >+ > >+ typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template > >+ rebind<_Node>::other _Node_allocator; > > > >- typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits; > >+ typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Node_alloc_traits; > > > > protected: > >- typedef _Rb_tree_node_base* _Base_ptr; > >- typedef const _Rb_tree_node_base* _Const_Base_ptr; > >- typedef _Rb_tree_node<_Val>* _Link_type; > >- typedef const _Rb_tree_node<_Val>* _Const_Link_type; > >+ typedef typename _Node_base::_Base_ptr _Base_ptr; > >+ typedef typename _Node_alloc_traits::pointer _Node_ptr; > > > > private: > > // Functor recycling a pool of nodes and using allocation once the > > pool > >@@ -445,13 +1053,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > { > > if (_M_root) > > { > >- _M_root->_M_parent = 0; > >+ _M_root->_M_parent = _Base_ptr(); > > > > if (_M_nodes->_M_left) > > _M_nodes = _M_nodes->_M_left; > > } > > else > >- _M_nodes = 0; > >+ _M_nodes = _Base_ptr(); > > } > > > > #if __cplusplus >= 201103L > >@@ -459,13 +1067,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > #endif > > > > ~_Reuse_or_alloc_node() > >- { _M_t._M_erase(static_cast<_Link_type>(_M_root)); } > >+ { _M_t._M_erase(_M_root); } > > > > template<typename _Arg> > >- _Link_type > >+ _Base_ptr > > Changing this from a node pointer to a base pointer seems to weaken > the API. We know it returns a pointer to a node, so can it return the > correct type? > > > operator()(_GLIBCXX_FWDREF(_Arg) __arg) > > { > >- _Link_type __node = static_cast<_Link_type>(_M_extract()); > >+ _Base_ptr __node = _M_extract(); > > if (__node) > > { > > _M_t._M_destroy_node(__node); > >@@ -489,7 +1097,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > { > > if (_M_nodes->_M_right == __node) > > { > >- _M_nodes->_M_right = 0; > >+ _M_nodes->_M_right = _Base_ptr(); > > > > if (_M_nodes->_M_left) > > { > >@@ -503,10 +1111,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > } > > } > > else // __node is on the left. > >- _M_nodes->_M_left = 0; > >+ _M_nodes->_M_left = _Base_ptr(); > > } > > else > >- _M_root = 0; > >+ _M_root = _Base_ptr(); > > > > return __node; > > } > >@@ -524,9 +1132,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > : _M_t(__t) { } > > > > template<typename _Arg> > >- _Link_type > >+ _Base_ptr > > Same comment here. > > > operator()(_GLIBCXX_FWDREF(_Arg) __arg) const > >- { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); } > >+ { > >+ return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); > >+ } > > > > private: > > _Rb_tree& _M_t; > >@@ -556,18 +1166,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > { return allocator_type(_M_get_Node_allocator()); } > > > > protected: > >- _Link_type > >+ _Node_ptr > > _M_get_node() > >- { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); } > >+ { return _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1); } > > > > void > >- _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT > >- { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); } > >+ _M_put_node(_Base_ptr __p) _GLIBCXX_NOEXCEPT > >+ { > >+ _Node_alloc_traits::deallocate > >+ (_M_get_Node_allocator(), __p->template _M_node_ptr<_Node_ptr>(), > >1); > >+ } > > > > #if __cplusplus < 201103L > > void > >- _M_construct_node(_Link_type __node, const value_type& __x) > >+ _M_construct_node(_Base_ptr __p, const value_type& __x) > > And can this be left as _Node_ptr instead of changed to _Base_ptr? > Then it wouldn't need the static_cast, and the callers wouldn't need > to use _M_base_ptr(). > > Logically, it has to be a _Node_ptr or the cast isn't valid anyway. > > There seem to be several places like this where we're giving up > valuable type information by using _base_ptr instead of _Node_ptr. > > Is that really necessary? If we have a _Node_ptr we can always get a > _Base_ptr easily by calling _M_base_ptr(). > > Is it a constness thing, because _M_begin() const was changed to > return _Base_ptr instead of _Const_link_ptr? > > > > { > >+ _Node_ptr __node = static_cast<_Node_ptr>(__p); > > __try > > { get_allocator().construct(__node->_M_valptr(), __x); } > > __catch(...) > >@@ -577,79 +1191,83 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > } > > } > > > >- _Link_type > >+ _Base_ptr > > _M_create_node(const value_type& __x) > > { > >- _Link_type __tmp = _M_get_node(); > >+ _Base_ptr __tmp = _M_get_node()->_M_base_ptr(); > > _M_construct_node(__tmp, __x); > > return __tmp; > > } > > #else > > template<typename... _Args> > > void > >- _M_construct_node(_Link_type __node, _Args&&... __args) > >+ _M_construct_node(_Base_ptr __p, _Args&&... __args) > > { > >+ _Node& __node = static_cast<_Node&>(*__p); > > __try > > { > >- ::new(__node) _Rb_tree_node<_Val>; > >- _Alloc_traits::construct(_M_get_Node_allocator(), > >- __node->_M_valptr(), > >- std::forward<_Args>(__args)...); > >+ ::new(std::__addressof(__node)) _Node; > >+ _Node_alloc_traits::construct(_M_get_Node_allocator(), > >+ __node._M_valptr(), > >+ std::forward<_Args>(__args)...); > > } > > __catch(...) > > { > >- __node->~_Rb_tree_node<_Val>(); > >- _M_put_node(__node); > >+ __node.~_Node(); > >+ _M_put_node(__p); > > __throw_exception_again; > > } > > } > > > > template<typename... _Args> > >- _Link_type > >+ _Base_ptr > > _M_create_node(_Args&&... __args) > > { > >- _Link_type __tmp = _M_get_node(); > >+ _Base_ptr __tmp = _M_get_node()->_M_base_ptr(); > > _M_construct_node(__tmp, std::forward<_Args>(__args)...); > > return __tmp; > > } > > #endif > > > > void > >- _M_destroy_node(_Link_type __p) _GLIBCXX_NOEXCEPT > >+ _M_destroy_node(_Base_ptr __p) _GLIBCXX_NOEXCEPT > > { > > #if __cplusplus < 201103L > >- get_allocator().destroy(__p->_M_valptr()); > >+ get_allocator().destroy(static_cast<_Node_ptr>(__p)->_M_valptr()); > > #else > >- _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr()); > >- __p->~_Rb_tree_node<_Val>(); > >+ _Node& __node = static_cast<_Node&>(*__p); > >+ _Node_alloc_traits::destroy(_M_get_Node_allocator(), > >+ __node._M_valptr()); > >+ __node.~_Node(); > > #endif > > } > > > > void > >- _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT > >+ _M_drop_node(_Base_ptr __p) _GLIBCXX_NOEXCEPT > > { > > _M_destroy_node(__p); > > _M_put_node(__p); > > } > > > > template<bool _MoveValue, typename _NodeGen> > >- _Link_type > >- _M_clone_node(_Link_type __x, _NodeGen& __node_gen) > >+ _Base_ptr > >+ _M_clone_node(_Base_ptr __x, _NodeGen& __node_gen) > > { > > #if __cplusplus >= 201103L > > using _Vp = __conditional_t<_MoveValue, > > value_type&&, > > const value_type&>; > > #endif > >- _Link_type __tmp > >- = __node_gen(_GLIBCXX_FORWARD(_Vp, *__x->_M_valptr())); > >+ _Base_ptr __tmp = __node_gen > >+ (_GLIBCXX_FORWARD(_Vp, *static_cast<_Node&>(*__x)._M_valptr())); > > __tmp->_M_color = __x->_M_color; > >- __tmp->_M_left = 0; > >- __tmp->_M_right = 0; > >+ __tmp->_M_left = __tmp->_M_right = _Base_ptr(); > > return __tmp; > > } > > > > protected: > >+ typedef typename _Node_traits::_Header_t _Header_t; > >+ > > #if _GLIBCXX_INLINE_VERSION > > template<typename _Key_compare> > > #else > >@@ -660,7 +1278,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > struct _Rb_tree_impl > > : public _Node_allocator > > , public _Rb_tree_key_compare<_Key_compare> > >- , public _Rb_tree_header > >+ , public _Header_t > > { > > typedef _Rb_tree_key_compare<_Key_compare> _Base_key_compare; > > > >@@ -672,9 +1290,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > { } > > > > _Rb_tree_impl(const _Rb_tree_impl& __x) > >- : _Node_allocator(_Alloc_traits::_S_select_on_copy(__x)) > >+ : _Node_allocator(_Node_alloc_traits::_S_select_on_copy(__x)) > > , _Base_key_compare(__x._M_key_compare) > >- , _Rb_tree_header() > >+ , _Header_t() > > { } > > > > #if __cplusplus < 201103L > >@@ -694,7 +1312,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a) > > : _Node_allocator(std::move(__a)), > > _Base_key_compare(std::move(__x)), > >- _Rb_tree_header(std::move(__x)) > >+ _Header_t(std::move(__x)) > > { } > > > > _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a) > >@@ -710,7 +1328,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _M_root() _GLIBCXX_NOEXCEPT > > { return this->_M_impl._M_header._M_parent; } > > > >- _Const_Base_ptr > >+ _Base_ptr > > _M_root() const _GLIBCXX_NOEXCEPT > > { return this->_M_impl._M_header._M_parent; } > > > >@@ -718,7 +1336,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _M_leftmost() _GLIBCXX_NOEXCEPT > > { return this->_M_impl._M_header._M_left; } > > > >- _Const_Base_ptr > >+ _Base_ptr > > _M_leftmost() const _GLIBCXX_NOEXCEPT > > { return this->_M_impl._M_header._M_left; } > > > >@@ -726,35 +1344,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _M_rightmost() _GLIBCXX_NOEXCEPT > > { return this->_M_impl._M_header._M_right; } > > > >- _Const_Base_ptr > >+ _Base_ptr > > _M_rightmost() const _GLIBCXX_NOEXCEPT > > { return this->_M_impl._M_header._M_right; } > > > >- _Link_type > >- _M_mbegin() const _GLIBCXX_NOEXCEPT > >- { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } > >- > >- _Link_type > >- _M_begin() _GLIBCXX_NOEXCEPT > >- { return _M_mbegin(); } > >- > >- _Const_Link_type > >+ _Base_ptr > > _M_begin() const _GLIBCXX_NOEXCEPT > >- { > >- return static_cast<_Const_Link_type> > >- (this->_M_impl._M_header._M_parent); > >- } > >+ { return this->_M_impl._M_header._M_parent; } > > > > _Base_ptr > >- _M_end() _GLIBCXX_NOEXCEPT > >- { return &this->_M_impl._M_header; } > >- > >- _Const_Base_ptr > > _M_end() const _GLIBCXX_NOEXCEPT > >- { return &this->_M_impl._M_header; } > >+ { return this->_M_impl._M_header._M_base_ptr(); } > > > > static const _Key& > >- _S_key(_Const_Link_type __x) > >+ _S_key(_Base_ptr __x) > > { > > #if __cplusplus >= 201103L > > // If we're asking for the key we're presumably using the comparison > >@@ -772,48 +1375,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > # endif // C++17 > > #endif // C++11 > > > >- return _KeyOfValue()(*__x->_M_valptr()); > >+ return _KeyOfValue()(*static_cast<const _Node&>(*__x)._M_valptr()); > > } > > > >- static _Link_type > >- _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT > >- { return static_cast<_Link_type>(__x->_M_left); } > >- > >- static _Const_Link_type > >- _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT > >- { return static_cast<_Const_Link_type>(__x->_M_left); } > >- > >- static _Link_type > >- _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT > >- { return static_cast<_Link_type>(__x->_M_right); } > >- > >- static _Const_Link_type > >- _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT > >- { return static_cast<_Const_Link_type>(__x->_M_right); } > >- > >- static const _Key& > >- _S_key(_Const_Base_ptr __x) > >- { return _S_key(static_cast<_Const_Link_type>(__x)); } > >- > > static _Base_ptr > >- _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT > >- { return _Rb_tree_node_base::_S_minimum(__x); } > >- > >- static _Const_Base_ptr > >- _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT > >- { return _Rb_tree_node_base::_S_minimum(__x); } > >+ _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT > >+ { return __x->_M_left; } > > > > static _Base_ptr > >- _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT > >- { return _Rb_tree_node_base::_S_maximum(__x); } > >- > >- static _Const_Base_ptr > >- _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT > >- { return _Rb_tree_node_base::_S_maximum(__x); } > >+ _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT > >+ { return __x->_M_right; } > > > > public: > >- typedef _Rb_tree_iterator<value_type> iterator; > >- typedef _Rb_tree_const_iterator<value_type> const_iterator; > >+ typedef typename _Node_traits::_Iterator iterator; > >+ typedef typename _Node_traits::_Const_iterator const_iterator; > > > > typedef std::reverse_iterator<iterator> reverse_iterator; > > typedef std::reverse_iterator<const_iterator> const_reverse_iterator; > >@@ -846,7 +1421,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&); > > > > iterator > >- _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z); > >+ _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Base_ptr __z); > > > > template<typename _Arg> > > iterator > >@@ -857,10 +1432,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _M_insert_equal_lower(_Arg&& __x); > > > > iterator > >- _M_insert_lower_node(_Base_ptr __p, _Link_type __z); > >+ _M_insert_lower_node(_Base_ptr __p, _Base_ptr __z); > > > > iterator > >- _M_insert_equal_lower_node(_Link_type __z); > >+ _M_insert_equal_lower_node(_Base_ptr __z); > > #else > > template<typename _NodeGen> > > iterator > >@@ -879,22 +1454,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > enum { __as_lvalue, __as_rvalue }; > > > > template<bool _MoveValues, typename _NodeGen> > >- _Link_type > >- _M_copy(_Link_type, _Base_ptr, _NodeGen&); > >+ _Base_ptr > >+ _M_copy(_Base_ptr, _Base_ptr, _NodeGen&); > > > > template<bool _MoveValues, typename _NodeGen> > >- _Link_type > >+ _Base_ptr > > _M_copy(const _Rb_tree& __x, _NodeGen& __gen) > > { > >- _Link_type __root = > >- _M_copy<_MoveValues>(__x._M_mbegin(), _M_end(), __gen); > >- _M_leftmost() = _S_minimum(__root); > >- _M_rightmost() = _S_maximum(__root); > >+ _Base_ptr __root = > >+ _M_copy<_MoveValues>(__x._M_begin(), _M_end(), __gen); > >+ _M_leftmost() = _Node_base::_S_minimum(__root); > >+ _M_rightmost() = _Node_base::_S_maximum(__root); > > _M_impl._M_node_count = __x._M_impl._M_node_count; > > return __root; > > } > > > >- _Link_type > >+ _Base_ptr > > _M_copy(const _Rb_tree& __x) > > { > > _Alloc_node __an(*this); > >@@ -902,22 +1477,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > } > > > > void > >- _M_erase(_Link_type __x); > >+ _M_erase(_Base_ptr __x); > > > >- iterator > >- _M_lower_bound(_Link_type __x, _Base_ptr __y, > >- const _Key& __k); > >- > >- const_iterator > >- _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y, > >+ _Base_ptr > >+ _M_lower_bound(_Base_ptr __x, _Base_ptr __y, > > const _Key& __k) const; > > > >- iterator > >- _M_upper_bound(_Link_type __x, _Base_ptr __y, > >- const _Key& __k); > >- > >- const_iterator > >- _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y, > >+ _Base_ptr > >+ _M_upper_bound(_Base_ptr __x, _Base_ptr __y, > > const _Key& __k) const; > > > > public: > >@@ -935,7 +1502,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _Rb_tree(const _Rb_tree& __x) > > : _M_impl(__x._M_impl) > > { > >- if (__x._M_root() != 0) > >+ if (__x._M_root()) > > _M_root() = _M_copy(__x); > > } > > > >@@ -947,7 +1514,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _Rb_tree(const _Rb_tree& __x, const allocator_type& __a) > > : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a)) > > { > >- if (__x._M_root() != nullptr) > >+ if (__x._M_root()) > > _M_root() = _M_copy(__x); > > } > > > >@@ -966,7 +1533,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type) > > : _M_impl(__x._M_impl._M_key_compare, std::move(__a)) > > { > >- if (__x._M_root() != nullptr) > >+ if (__x._M_root()) > > _M_move_data(__x, false_type{}); > > } > > > >@@ -974,9 +1541,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a) > > noexcept( noexcept( > > _Rb_tree(std::declval<_Rb_tree&&>(), > > std::declval<_Node_allocator&&>(), > >- std::declval<typename _Alloc_traits::is_always_equal>())) ) > >+ std::declval<typename > >_Node_alloc_traits::is_always_equal>())) ) > > : _Rb_tree(std::move(__x), std::move(__a), > >- typename _Alloc_traits::is_always_equal{}) > >+ typename _Node_alloc_traits::is_always_equal{}) > > { } > > #endif > > > >@@ -1001,11 +1568,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > > > iterator > > end() _GLIBCXX_NOEXCEPT > >- { return iterator(&this->_M_impl._M_header); } > >+ { return iterator(_M_end()); } > > > > const_iterator > > end() const _GLIBCXX_NOEXCEPT > >- { return const_iterator(&this->_M_impl._M_header); } > >+ { return const_iterator(_M_end()); } > > > > reverse_iterator > > rbegin() _GLIBCXX_NOEXCEPT > >@@ -1033,7 +1600,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > > > size_type > > max_size() const _GLIBCXX_NOEXCEPT > >- { return _Alloc_traits::max_size(_M_get_Node_allocator()); } > >+ { return _Node_alloc_traits::max_size(_M_get_Node_allocator()); } > > > > void > > swap(_Rb_tree& __t) > >@@ -1194,7 +1761,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > const_iterator __result = __position; > > ++__result; > > _M_erase_aux(__position); > >- return __result._M_const_cast(); > >+ return iterator(__result._M_node); > > } > > > > // LWG 2059. > >@@ -1235,7 +1802,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > erase(const_iterator __first, const_iterator __last) > > { > > _M_erase_aux(__first, __last); > >- return __last._M_const_cast(); > >+ return iterator(__last._M_node); > > } > > #else > > void > >@@ -1266,19 +1833,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > > > iterator > > lower_bound(const key_type& __k) > >- { return _M_lower_bound(_M_begin(), _M_end(), __k); } > >+ { return iterator(_M_lower_bound(_M_begin(), _M_end(), __k)); } > > > > const_iterator > > lower_bound(const key_type& __k) const > >- { return _M_lower_bound(_M_begin(), _M_end(), __k); } > >+ { > >+ return const_iterator > >+ (_M_lower_bound(_M_begin(), _M_end(), __k)); > >+ } > > > > iterator > > upper_bound(const key_type& __k) > >- { return _M_upper_bound(_M_begin(), _M_end(), __k); } > >+ { return iterator(_M_upper_bound(_M_begin(), _M_end(), __k)); } > > > > const_iterator > > upper_bound(const key_type& __k) const > >- { return _M_upper_bound(_M_begin(), _M_end(), __k); } > >+ { > >+ return const_iterator > >+ (_M_upper_bound(_M_begin(), _M_end(), __k)); > >+ } > > > > pair<iterator, iterator> > > equal_range(const key_type& __k); > >@@ -1293,7 +1866,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _M_find_tr(const _Kt& __k) > > { > > const _Rb_tree* __const_this = this; > >- return __const_this->_M_find_tr(__k)._M_const_cast(); > >+ return iterator(__const_this->_M_find_tr(__k)._M_node); > > } > > > > template<typename _Kt, > >@@ -1301,7 +1874,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > const_iterator > > _M_find_tr(const _Kt& __k) const > > { > >- auto __j = _M_lower_bound_tr(__k); > >+ const_iterator __j(_M_lower_bound_tr(__k)); > > if (__j != end() && _M_impl._M_key_compare(__k, > > _S_key(__j._M_node))) > > __j = end(); > > return __j; > >@@ -1318,21 +1891,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > > > template<typename _Kt, > > typename _Req = __has_is_transparent_t<_Compare, _Kt>> > >- iterator > >- _M_lower_bound_tr(const _Kt& __k) > >- { > >- const _Rb_tree* __const_this = this; > >- return __const_this->_M_lower_bound_tr(__k)._M_const_cast(); > >- } > >- > >- template<typename _Kt, > >- typename _Req = __has_is_transparent_t<_Compare, _Kt>> > >- const_iterator > >+ _Base_ptr > > _M_lower_bound_tr(const _Kt& __k) const > > { > > auto __x = _M_begin(); > > auto __y = _M_end(); > >- while (__x != 0) > >+ while (__x) > > if (!_M_impl._M_key_compare(_S_key(__x), __k)) > > { > > __y = __x; > >@@ -1340,26 +1904,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > } > > else > > __x = _S_right(__x); > >- return const_iterator(__y); > >+ return __y; > > } > > > > template<typename _Kt, > > typename _Req = __has_is_transparent_t<_Compare, _Kt>> > >- iterator > >- _M_upper_bound_tr(const _Kt& __k) > >- { > >- const _Rb_tree* __const_this = this; > >- return __const_this->_M_upper_bound_tr(__k)._M_const_cast(); > >- } > >- > >- template<typename _Kt, > >- typename _Req = __has_is_transparent_t<_Compare, _Kt>> > >- const_iterator > >+ _Base_ptr > > _M_upper_bound_tr(const _Kt& __k) const > > { > > auto __x = _M_begin(); > > auto __y = _M_end(); > >- while (__x != 0) > >+ while (__x) > > if (_M_impl._M_key_compare(__k, _S_key(__x))) > > { > > __y = __x; > >@@ -1367,7 +1922,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > } > > else > > __x = _S_right(__x); > >- return const_iterator(__y); > >+ return __y; > > } > > > > template<typename _Kt, > >@@ -1377,7 +1932,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > { > > const _Rb_tree* __const_this = this; > > auto __ret = __const_this->_M_equal_range_tr(__k); > >- return { __ret.first._M_const_cast(), __ret.second._M_const_cast() > >}; > >+ return > >+ { iterator(__ret.first._M_node), iterator(__ret.second._M_node) }; > > } > > > > template<typename _Kt, > >@@ -1385,7 +1941,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > pair<const_iterator, const_iterator> > > _M_equal_range_tr(const _Kt& __k) const > > { > >- auto __low = _M_lower_bound_tr(__k); > >+ const_iterator __low(_M_lower_bound_tr(__k)); > > auto __high = __low; > > auto& __cmp = _M_impl._M_key_compare; > > while (__high != end() && !__cmp(__k, _S_key(__high._M_node))) > >@@ -1401,7 +1957,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > #if __cplusplus >= 201103L > > _Rb_tree& > > operator=(_Rb_tree&&) > >- noexcept(_Alloc_traits::_S_nothrow_move() > >+ noexcept(_Node_alloc_traits::_S_nothrow_move() > > && is_nothrow_move_assignable<_Compare>::value); > > > > template<typename _Iterator> > >@@ -1449,8 +2005,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > auto __res = _M_get_insert_unique_pos(__nh._M_key()); > > if (__res.second) > > { > >- __ret.position > >- = _M_insert_node(__res.first, __res.second, __nh._M_ptr); > >+ __ret.position = _M_insert_node(__res.first, __res.second, > >+ __nh._M_ptr->_M_base_ptr()); > > __nh.release(); > > __ret.inserted = true; > > } > >@@ -1476,9 +2032,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc); > > auto __res = _M_get_insert_equal_pos(__nh._M_key()); > > if (__res.second) > >- __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr); > >+ __ret = _M_insert_node(__res.first, __res.second, > >+ __nh._M_ptr->_M_base_ptr()); > > else > >- __ret = _M_insert_equal_lower_node(__nh._M_ptr); > >+ __ret = _M_insert_equal_lower_node(__nh._M_ptr->_M_base_ptr()); > > __nh.release(); > > } > > return __ret; > >@@ -1497,7 +2054,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > auto __res = _M_get_insert_hint_unique_pos(__hint, __nh._M_key()); > > if (__res.second) > > { > >- __ret = _M_insert_node(__res.first, __res.second, > >__nh._M_ptr); > >+ __ret = _M_insert_node(__res.first, __res.second, > >+ __nh._M_ptr->_M_base_ptr()); > > __nh.release(); > > } > > else > >@@ -1518,9 +2076,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc); > > auto __res = _M_get_insert_hint_equal_pos(__hint, __nh._M_key()); > > if (__res.second) > >- __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr); > >+ __ret = _M_insert_node(__res.first, __res.second, > >+ __nh._M_ptr->_M_base_ptr()); > > else > >- __ret = _M_insert_equal_lower_node(__nh._M_ptr); > >+ __ret = _M_insert_equal_lower_node(__nh._M_ptr->_M_base_ptr()); > > __nh.release(); > > } > > return __ret; > >@@ -1530,10 +2089,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > node_type > > extract(const_iterator __pos) > > { > >- auto __ptr = _Rb_tree_rebalance_for_erase( > >- __pos._M_const_cast()._M_node, _M_impl._M_header); > >+ auto __ptr = _Node_traits::_S_rebalance_for_erase > >+ (__pos._M_node, _M_impl._M_header); > > --_M_impl._M_node_count; > >- return { static_cast<_Link_type>(__ptr), _M_get_Node_allocator() }; > >+ return > >+ { __ptr->template _M_node_ptr<_Node_ptr>(), _M_get_Node_allocator() > >}; > > } > > > > /// Extract a node. > >@@ -1567,11 +2127,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > if (__res.second) > > { > > auto& __src_impl = _Merge_helper::_S_get_impl(__src); > >- auto __ptr = _Rb_tree_rebalance_for_erase( > >- __pos._M_node, __src_impl._M_header); > >+ auto __ptr = _Node_traits::_S_rebalance_for_erase > >+ (__pos._M_node, __src_impl._M_header); > > --__src_impl._M_node_count; > >- _M_insert_node(__res.first, __res.second, > >- static_cast<_Link_type>(__ptr)); > >+ _M_insert_node(__res.first, __res.second, __ptr); > > } > > } > > } > >@@ -1589,11 +2148,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > if (__res.second) > > { > > auto& __src_impl = _Merge_helper::_S_get_impl(__src); > >- auto __ptr = _Rb_tree_rebalance_for_erase( > >- __pos._M_node, __src_impl._M_header); > >+ auto __ptr = _Node_traits::_S_rebalance_for_erase > >+ (__pos._M_node, __src_impl._M_header); > > --__src_impl._M_node_count; > >- _M_insert_node(__res.first, __res.second, > >- static_cast<_Link_type>(__ptr)); > >+ _M_insert_node(__res.first, __res.second, __ptr); > > } > > } > > } > >@@ -1666,7 +2224,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > } > > > > _Rb_tree& _M_t; > >- _Link_type _M_node; > >+ _Base_ptr _M_node; > > }; > > #endif // C++11 > > }; > >@@ -1704,7 +2262,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _M_move_assign(_Rb_tree& __x, true_type) > > { > > clear(); > >- if (__x._M_root() != nullptr) > >+ if (__x._M_root()) > > _M_move_data(__x, true_type()); > > std::__alloc_on_move(_M_get_Node_allocator(), > > __x._M_get_Node_allocator()); > >@@ -1723,7 +2281,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > // structure. > > _Reuse_or_alloc_node __roan(*this); > > _M_impl._M_reset(); > >- if (__x._M_root() != nullptr) > >+ if (__x._M_root()) > > { > > _M_root() = _M_copy<__as_rvalue>(__x, __roan); > > __x.clear(); > >@@ -1735,11 +2293,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& > > _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: > > operator=(_Rb_tree&& __x) > >- noexcept(_Alloc_traits::_S_nothrow_move() > >+ noexcept(_Node_alloc_traits::_S_nothrow_move() > > && is_nothrow_move_assignable<_Compare>::value) > > { > > _M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare); > >- _M_move_assign(__x, > >__bool_constant<_Alloc_traits::_S_nothrow_move()>()); > >+ _M_move_assign(__x, > >+ > >__bool_constant<_Node_alloc_traits::_S_nothrow_move()>()); > > return *this; > > } > > > >@@ -1780,11 +2339,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > { > > // Note that _Key may be a constant type. > > #if __cplusplus >= 201103L > >- if (_Alloc_traits::_S_propagate_on_copy_assign()) > >+ if (_Node_alloc_traits::_S_propagate_on_copy_assign()) > > { > > auto& __this_alloc = this->_M_get_Node_allocator(); > > auto& __that_alloc = __x._M_get_Node_allocator(); > >- if (!_Alloc_traits::_S_always_equal() > >+ if (!_Node_alloc_traits::_S_always_equal() > > && __this_alloc != __that_alloc) > > { > > // Replacement allocator cannot free existing storage, we > > need > >@@ -1798,7 +2357,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _Reuse_or_alloc_node __roan(*this); > > _M_impl._M_reset(); > > _M_impl._M_key_compare = __x._M_impl._M_key_compare; > >- if (__x._M_root() != 0) > >+ if (__x._M_root()) > > _M_root() = _M_copy<__as_lvalue>(__x, __roan); > > } > > > >@@ -1822,14 +2381,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > #endif > > _NodeGen& __node_gen) > > { > >- bool __insert_left = (__x != 0 || __p == _M_end() > >+ bool __insert_left = (__x || __p == _M_end() > > || _M_impl._M_key_compare(_KeyOfValue()(__v), > > _S_key(__p))); > > > >- _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v)); > >+ _Base_ptr __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v)); > > > >- _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, > >- this->_M_impl._M_header); > >+ _Node_traits::_S_insert_and_rebalance > >+ (__insert_left, __z, __p, this->_M_impl._M_header); > > ++_M_impl._M_node_count; > > return iterator(__z); > > } > >@@ -1851,10 +2410,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > || !_M_impl._M_key_compare(_S_key(__p), > > _KeyOfValue()(__v))); > > > >- _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); > >- > >- _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, > >- this->_M_impl._M_header); > >+ _Base_ptr __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); > >+ _Node_traits::_S_insert_and_rebalance > >+ (__insert_left, __z, __p, this->_M_impl._M_header); > > ++_M_impl._M_node_count; > > return iterator(__z); > > } > >@@ -1872,9 +2430,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _M_insert_equal_lower(const _Val& __v) > > #endif > > { > >- _Link_type __x = _M_begin(); > >+ _Base_ptr __x = _M_begin(); > > _Base_ptr __y = _M_end(); > >- while (__x != 0) > >+ while (__x) > > { > > __y = __x; > > __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? > >@@ -1886,12 +2444,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > template<typename _Key, typename _Val, typename _KoV, > > typename _Compare, typename _Alloc> > > template<bool _MoveValues, typename _NodeGen> > >- typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type > >+ typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Base_ptr > > _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: > >- _M_copy(_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen) > >+ _M_copy(_Base_ptr __x, _Base_ptr __p, _NodeGen& __node_gen) > > { > > // Structural copy. __x and __p must be non-null. > >- _Link_type __top = _M_clone_node<_MoveValues>(__x, __node_gen); > >+ _Base_ptr __top = _M_clone_node<_MoveValues>(__x, __node_gen); > > __top->_M_parent = __p; > > > > __try > >@@ -1902,9 +2460,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > __p = __top; > > __x = _S_left(__x); > > > >- while (__x != 0) > >+ while (__x) > > { > >- _Link_type __y = _M_clone_node<_MoveValues>(__x, __node_gen); > >+ _Base_ptr __y = _M_clone_node<_MoveValues>(__x, __node_gen); > > __p->_M_left = __y; > > __y->_M_parent = __p; > > if (__x->_M_right) > >@@ -1926,13 +2484,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > typename _Compare, typename _Alloc> > > void > > _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: > >- _M_erase(_Link_type __x) > >+ _M_erase(_Base_ptr __x) > > { > > // Erase without rebalancing. > >- while (__x != 0) > >+ while (__x) > > { > > _M_erase(_S_right(__x)); > >- _Link_type __y = _S_left(__x); > >+ _Base_ptr __y = _S_left(__x); > > _M_drop_node(__x); > > __x = __y; > > } > >@@ -1941,65 +2499,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > template<typename _Key, typename _Val, typename _KeyOfValue, > > typename _Compare, typename _Alloc> > > typename _Rb_tree<_Key, _Val, _KeyOfValue, > >- _Compare, _Alloc>::iterator > >+ _Compare, _Alloc>::_Base_ptr > > _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: > >- _M_lower_bound(_Link_type __x, _Base_ptr __y, > >- const _Key& __k) > >- { > >- while (__x != 0) > >- if (!_M_impl._M_key_compare(_S_key(__x), __k)) > >- __y = __x, __x = _S_left(__x); > >- else > >- __x = _S_right(__x); > >- return iterator(__y); > >- } > >- > >- template<typename _Key, typename _Val, typename _KeyOfValue, > >- typename _Compare, typename _Alloc> > >- typename _Rb_tree<_Key, _Val, _KeyOfValue, > >- _Compare, _Alloc>::const_iterator > >- _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: > >- _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y, > >+ _M_lower_bound(_Base_ptr __x, _Base_ptr __y, > > const _Key& __k) const > > { > >- while (__x != 0) > >+ while (__x) > > if (!_M_impl._M_key_compare(_S_key(__x), __k)) > > __y = __x, __x = _S_left(__x); > > else > > __x = _S_right(__x); > >- return const_iterator(__y); > >- } > >- > >- template<typename _Key, typename _Val, typename _KeyOfValue, > >- typename _Compare, typename _Alloc> > >- typename _Rb_tree<_Key, _Val, _KeyOfValue, > >- _Compare, _Alloc>::iterator > >- _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: > >- _M_upper_bound(_Link_type __x, _Base_ptr __y, > >- const _Key& __k) > >- { > >- while (__x != 0) > >- if (_M_impl._M_key_compare(__k, _S_key(__x))) > >- __y = __x, __x = _S_left(__x); > >- else > >- __x = _S_right(__x); > >- return iterator(__y); > >+ return __y; > > } > > > > template<typename _Key, typename _Val, typename _KeyOfValue, > > typename _Compare, typename _Alloc> > > typename _Rb_tree<_Key, _Val, _KeyOfValue, > >- _Compare, _Alloc>::const_iterator > >+ _Compare, _Alloc>::_Base_ptr > > _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: > >- _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y, > >+ _M_upper_bound(_Base_ptr __x, _Base_ptr __y, > > const _Key& __k) const > > { > >- while (__x != 0) > >+ while (__x) > > if (_M_impl._M_key_compare(__k, _S_key(__x))) > > __y = __x, __x = _S_left(__x); > > else > > __x = _S_right(__x); > >- return const_iterator(__y); > >+ return __y; > > } > > > > template<typename _Key, typename _Val, typename _KeyOfValue, > >@@ -2011,9 +2537,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: > > equal_range(const _Key& __k) > > { > >- _Link_type __x = _M_begin(); > >+ _Base_ptr __x = _M_begin(); > > _Base_ptr __y = _M_end(); > >- while (__x != 0) > >+ while (__x) > > { > > if (_M_impl._M_key_compare(_S_key(__x), __k)) > > __x = _S_right(__x); > >@@ -2021,13 +2547,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > __y = __x, __x = _S_left(__x); > > else > > { > >- _Link_type __xu(__x); > >+ _Base_ptr __xu(__x); > > _Base_ptr __yu(__y); > > __y = __x, __x = _S_left(__x); > > __xu = _S_right(__xu); > >- return pair<iterator, > >- iterator>(_M_lower_bound(__x, __y, __k), > >- _M_upper_bound(__xu, __yu, __k)); > >+ return make_pair(iterator(_M_lower_bound(__x, __y, __k)), > >+ iterator(_M_upper_bound(__xu, __yu, __k))); > > } > > } > > return pair<iterator, iterator>(iterator(__y), > >@@ -2043,9 +2568,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: > > equal_range(const _Key& __k) const > > { > >- _Const_Link_type __x = _M_begin(); > >- _Const_Base_ptr __y = _M_end(); > >- while (__x != 0) > >+ _Base_ptr __x = _M_begin(); > >+ _Base_ptr __y = _M_end(); > >+ while (__x) > > { > > if (_M_impl._M_key_compare(_S_key(__x), __k)) > > __x = _S_right(__x); > >@@ -2053,13 +2578,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > __y = __x, __x = _S_left(__x); > > else > > { > >- _Const_Link_type __xu(__x); > >- _Const_Base_ptr __yu(__y); > >+ _Base_ptr __xu(__x); > >+ _Base_ptr __yu(__y); > > __y = __x, __x = _S_left(__x); > > __xu = _S_right(__xu); > >- return pair<const_iterator, > >- const_iterator>(_M_lower_bound(__x, __y, __k), > >- _M_upper_bound(__xu, __yu, __k)); > >+ return make_pair(const_iterator(_M_lower_bound(__x, __y, __k)), > >+ const_iterator(_M_upper_bound(__xu, __yu, > >__k))); > > } > > } > > return pair<const_iterator, const_iterator>(const_iterator(__y), > >@@ -2073,12 +2597,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > swap(_Rb_tree& __t) > > _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value) > > { > >- if (_M_root() == 0) > >+ if (!_M_root()) > > { > >- if (__t._M_root() != 0) > >+ if (__t._M_root()) > > _M_impl._M_move_data(__t._M_impl); > > } > >- else if (__t._M_root() == 0) > >+ else if (!__t._M_root()) > > __t._M_impl._M_move_data(_M_impl); > > else > > { > >@@ -2093,8 +2617,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > // No need to swap header's color as it does not change. > > std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); > > > >- _Alloc_traits::_S_on_swap(_M_get_Node_allocator(), > >- __t._M_get_Node_allocator()); > >+ _Node_alloc_traits::_S_on_swap(_M_get_Node_allocator(), > >+ __t._M_get_Node_allocator()); > > } > > > > template<typename _Key, typename _Val, typename _KeyOfValue, > >@@ -2107,10 +2631,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _M_get_insert_unique_pos(const key_type& __k) > > { > > typedef pair<_Base_ptr, _Base_ptr> _Res; > >- _Link_type __x = _M_begin(); > >+ _Base_ptr __x = _M_begin(); > > _Base_ptr __y = _M_end(); > > bool __comp = true; > >- while (__x != 0) > >+ while (__x) > > { > > __y = __x; > > __comp = _M_impl._M_key_compare(__k, _S_key(__x)); > >@@ -2126,7 +2650,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > } > > if (_M_impl._M_key_compare(_S_key(__j._M_node), __k)) > > return _Res(__x, __y); > >- return _Res(__j._M_node, 0); > >+ return _Res(__j._M_node, _Base_ptr()); > > } > > > > template<typename _Key, typename _Val, typename _KeyOfValue, > >@@ -2139,9 +2663,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _M_get_insert_equal_pos(const key_type& __k) > > { > > typedef pair<_Base_ptr, _Base_ptr> _Res; > >- _Link_type __x = _M_begin(); > >+ _Base_ptr __x = _M_begin(); > > _Base_ptr __y = _M_end(); > >- while (__x != 0) > >+ while (__x) > > { > > __y = __x; > > __x = _M_impl._M_key_compare(__k, _S_key(__x)) ? > >@@ -2209,44 +2733,43 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _M_get_insert_hint_unique_pos(const_iterator __position, > > const key_type& __k) > > { > >- iterator __pos = __position._M_const_cast(); > > typedef pair<_Base_ptr, _Base_ptr> _Res; > > > > // end() > >- if (__pos._M_node == _M_end()) > >+ if (__position._M_node == _M_end()) > > { > > if (size() > 0 > > && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k)) > >- return _Res(0, _M_rightmost()); > >+ return _Res(_Base_ptr(), _M_rightmost()); > > else > > return _M_get_insert_unique_pos(__k); > > } > >- else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node))) > >+ else if (_M_impl._M_key_compare(__k, _S_key(__position._M_node))) > > { > > // First, try before... > >- iterator __before = __pos; > >- if (__pos._M_node == _M_leftmost()) // begin() > >+ iterator __before(__position._M_node); > >+ if (__position._M_node == _M_leftmost()) // begin() > > return _Res(_M_leftmost(), _M_leftmost()); > > else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k)) > > { > >- if (_S_right(__before._M_node) == 0) > >- return _Res(0, __before._M_node); > >+ if (!_S_right(__before._M_node)) > >+ return _Res(_Base_ptr(), __before._M_node); > > else > >- return _Res(__pos._M_node, __pos._M_node); > >+ return _Res(__position._M_node, __position._M_node); > > } > > else > > return _M_get_insert_unique_pos(__k); > > } > >- else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) > >+ else if (_M_impl._M_key_compare(_S_key(__position._M_node), __k)) > > { > > // ... then try after. > >- iterator __after = __pos; > >- if (__pos._M_node == _M_rightmost()) > >- return _Res(0, _M_rightmost()); > >+ iterator __after(__position._M_node); > >+ if (__position._M_node == _M_rightmost()) > >+ return _Res(_Base_ptr(), _M_rightmost()); > > else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node))) > > { > >- if (_S_right(__pos._M_node) == 0) > >- return _Res(0, __pos._M_node); > >+ if (!_S_right(__position._M_node)) > >+ return _Res(_Base_ptr(), __position._M_node); > > else > > return _Res(__after._M_node, __after._M_node); > > } > >@@ -2255,7 +2778,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > } > > else > > // Equivalent keys. > >- return _Res(__pos._M_node, 0); > >+ return _Res(__position._M_node, _Base_ptr()); > > } > > > > template<typename _Key, typename _Val, typename _KeyOfValue, > >@@ -2294,30 +2817,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: > > _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& > > __k) > > { > >- iterator __pos = __position._M_const_cast(); > > typedef pair<_Base_ptr, _Base_ptr> _Res; > > > > // end() > >- if (__pos._M_node == _M_end()) > >+ if (__position._M_node == _M_end()) > > { > > if (size() > 0 > > && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost()))) > >- return _Res(0, _M_rightmost()); > >+ return _Res(_Base_ptr(), _M_rightmost()); > > else > > return _M_get_insert_equal_pos(__k); > > } > >- else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) > >+ else if (!_M_impl._M_key_compare(_S_key(__position._M_node), __k)) > > { > > // First, try before... > >- iterator __before = __pos; > >- if (__pos._M_node == _M_leftmost()) // begin() > >+ iterator __before(__position._M_node); > >+ if (__position._M_node == _M_leftmost()) // begin() > > return _Res(_M_leftmost(), _M_leftmost()); > > else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node))) > > { > >- if (_S_right(__before._M_node) == 0) > >- return _Res(0, __before._M_node); > >+ if (!_S_right(__before._M_node)) > >+ return _Res(_Base_ptr(), __before._M_node); > > else > >- return _Res(__pos._M_node, __pos._M_node); > >+ return _Res(__position._M_node, __position._M_node); > > } > > else > > return _M_get_insert_equal_pos(__k); > >@@ -2325,18 +2847,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > else > > { > > // ... then try after. > >- iterator __after = __pos; > >- if (__pos._M_node == _M_rightmost()) > >- return _Res(0, _M_rightmost()); > >+ iterator __after(__position._M_node); > >+ if (__position._M_node == _M_rightmost()) > >+ return _Res(_Base_ptr(), _M_rightmost()); > > else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k)) > > { > >- if (_S_right(__pos._M_node) == 0) > >- return _Res(0, __pos._M_node); > >+ if (!_S_right(__position._M_node)) > >+ return _Res(_Base_ptr(), __position._M_node); > > else > > return _Res(__after._M_node, __after._M_node); > > } > > else > >- return _Res(0, 0); > >+ return _Res(_Base_ptr(), _Base_ptr()); > > } > > } > > > >@@ -2373,15 +2895,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > typename _Compare, typename _Alloc> > > auto > > _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: > >- _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z) > >+ _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Base_ptr __z) > > -> iterator > > { > >- bool __insert_left = (__x != 0 || __p == _M_end() > >+ bool __insert_left = (__x || __p == _M_end() > > || _M_impl._M_key_compare(_S_key(__z), > > _S_key(__p))); > > > >- _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, > >- this->_M_impl._M_header); > >+ _Node_traits::_S_insert_and_rebalance > >+ (__insert_left, __z, __p, this->_M_impl._M_header); > > ++_M_impl._M_node_count; > > return iterator(__z); > > } > >@@ -2390,15 +2912,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > typename _Compare, typename _Alloc> > > auto > > _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: > >- _M_insert_lower_node(_Base_ptr __p, _Link_type __z) > >+ _M_insert_lower_node(_Base_ptr __p, _Base_ptr __z) > > -> iterator > > { > > bool __insert_left = (__p == _M_end() > > || !_M_impl._M_key_compare(_S_key(__p), > > _S_key(__z))); > > > >- _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, > >- this->_M_impl._M_header); > >+ _Node_traits::_S_insert_and_rebalance > >+ (__insert_left, __z, __p, this->_M_impl._M_header); > > ++_M_impl._M_node_count; > > return iterator(__z); > > } > >@@ -2407,12 +2929,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > typename _Compare, typename _Alloc> > > auto > > _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: > >- _M_insert_equal_lower_node(_Link_type __z) > >+ _M_insert_equal_lower_node(_Base_ptr __z) > > -> iterator > > { > >- _Link_type __x = _M_begin(); > >+ _Base_ptr __x = _M_begin(); > > _Base_ptr __y = _M_end(); > >- while (__x != 0) > >+ while (__x) > > { > > __y = __x; > > __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ? > >@@ -2487,10 +3009,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: > > _M_erase_aux(const_iterator __position) > > { > >- _Link_type __y = > >- static_cast<_Link_type>(_Rb_tree_rebalance_for_erase > >- (const_cast<_Base_ptr>(__position._M_node), > >- this->_M_impl._M_header)); > >+ _Base_ptr __y = _Node_traits::_S_rebalance_for_erase > >+ (__position._M_node, this->_M_impl._M_header); > > _M_drop_node(__y); > > --_M_impl._M_node_count; > > } > >@@ -2527,7 +3047,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: > > find(const _Key& __k) > > { > >- iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); > >+ iterator __j(_M_lower_bound(_M_begin(), _M_end(), __k)); > > return (__j == end() > > || _M_impl._M_key_compare(__k, > > _S_key(__j._M_node))) ? end() : __j; > >@@ -2540,7 +3060,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: > > find(const _Key& __k) const > > { > >- const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k); > >+ const_iterator __j(_M_lower_bound(_M_begin(), _M_end(), __k)); > > return (__j == end() > > || _M_impl._M_key_compare(__k, > > _S_key(__j._M_node))) ? end() : __j; > >@@ -2574,9 +3094,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); > > for (const_iterator __it = begin(); __it != end(); ++__it) > > { > >- _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); > >- _Const_Link_type __L = _S_left(__x); > >- _Const_Link_type __R = _S_right(__x); > >+ _Base_ptr __x = __it._M_node; > >+ _Base_ptr __L = _S_left(__x); > >+ _Base_ptr __R = _S_right(__x); > > > > if (__x->_M_color == _S_red) > > if ((__L && __L->_M_color == _S_red) > >@@ -2592,9 +3112,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > return false; > > } > > > >- if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) > >+ if (_M_leftmost() != _Node_base::_S_minimum(_M_root())) > > return false; > >- if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) > >+ if (_M_rightmost() != _Node_base::_S_maximum(_M_root())) > > return false; > > return true; > > } > >diff --git a/libstdc++-v3/testsuite/23_containers/map/allocator/ext_ptr.cc > >b/libstdc++-v3/testsuite/23_containers/map/allocator/ext_ptr.cc > >new file mode 100644 > >index 00000000000..3d83738f86b > >--- /dev/null > >+++ b/libstdc++-v3/testsuite/23_containers/map/allocator/ext_ptr.cc > >@@ -0,0 +1,37 @@ > >+// { dg-do run { target c++11 } } > >+ > >+#include <map> > >+#include <memory> > >+#include <testsuite_hooks.h> > >+#include <testsuite_allocator.h> > >+ > >+struct T { int i; }; > >+ > >+bool operator<(const T& l, const T& r) > >+{ return l.i < r.i; } > >+ > >+struct L : std::less<T> > >+{ }; > >+ > >+using __gnu_test::CustomPointerAlloc; > >+ > >+template class std::map<T, int, L, > >+ CustomPointerAlloc<std::pair<const T, int>>>; > >+ > >+void test01() > >+{ > >+ typedef CustomPointerAlloc<std::pair<const T, int>> alloc_type; > >+ typedef std::map<T, int, L, alloc_type> test_type; > >+ test_type v; > >+ v.insert({ T(), 0 }); > >+ VERIFY( v.begin()->second == 0 ); > >+ VERIFY( ++v.begin() == v.end() ); > >+ v.insert({ T { 1 }, 1 }); > >+ VERIFY( v.size() == 2 ); > >+ VERIFY( v.find(T()) != v.end() ); > >+} > >+ > >+int main() > >+{ > >+ test01(); > >+} > >diff --git > >a/libstdc++-v3/testsuite/23_containers/multimap/allocator/ext_ptr.cc > >b/libstdc++-v3/testsuite/23_containers/multimap/allocator/ext_ptr.cc > >new file mode 100644 > >index 00000000000..41689ef43b7 > >--- /dev/null > >+++ b/libstdc++-v3/testsuite/23_containers/multimap/allocator/ext_ptr.cc > >@@ -0,0 +1,33 @@ > >+// { dg-do run { target c++11 } } > >+ > >+#include <map> > >+#include <memory> > >+#include <testsuite_hooks.h> > >+#include <testsuite_allocator.h> > >+ > >+struct T { int i; }; > >+ > >+bool operator<(const T& l, const T& r) > >+{ return l.i < r.i; } > >+ > >+struct L : std::less<T> > >+{ }; > >+ > >+using __gnu_test::CustomPointerAlloc; > >+ > >+template class std::multimap<T, int, L, > >+ CustomPointerAlloc<std::pair<const T, int>>>; > >+ > >+void test01() > >+{ > >+ typedef CustomPointerAlloc<std::pair<const T, int>> alloc_type; > >+ typedef std::multimap<T, int, L, alloc_type> test_type; > >+ test_type v; > >+ v.insert({ T(), 0 }); > >+ VERIFY( ++v.begin() == v.end() ); > >+} > >+ > >+int main() > >+{ > >+ test01(); > >+} > >diff --git > >a/libstdc++-v3/testsuite/23_containers/multiset/allocator/ext_ptr.cc > >b/libstdc++-v3/testsuite/23_containers/multiset/allocator/ext_ptr.cc > >new file mode 100644 > >index 00000000000..589e6b0a617 > >--- /dev/null > >+++ b/libstdc++-v3/testsuite/23_containers/multiset/allocator/ext_ptr.cc > >@@ -0,0 +1,32 @@ > >+// { dg-do run { target c++11 } } > >+ > >+#include <set> > >+#include <memory> > >+#include <testsuite_hooks.h> > >+#include <testsuite_allocator.h> > >+ > >+struct T { int i; }; > >+ > >+bool operator<(const T& l, const T& r) > >+{ return l.i < r.i; } > >+ > >+struct L : std::less<T> > >+{ }; > >+ > >+using __gnu_test::CustomPointerAlloc; > >+ > >+template class std::multiset<T, L, CustomPointerAlloc<T>>; > >+ > >+void test01() > >+{ > >+ typedef CustomPointerAlloc<T> alloc_type; > >+ typedef std::multiset<T, L, alloc_type> test_type; > >+ test_type v; > >+ v.insert(T()); > >+ VERIFY( ++v.begin() == v.end() ); > >+} > >+ > >+int main() > >+{ > >+ test01(); > >+} > >diff --git a/libstdc++-v3/testsuite/23_containers/set/allocator/ext_ptr.cc > >b/libstdc++-v3/testsuite/23_containers/set/allocator/ext_ptr.cc > >new file mode 100644 > >index 00000000000..bbcf32b20be > >--- /dev/null > >+++ b/libstdc++-v3/testsuite/23_containers/set/allocator/ext_ptr.cc > >@@ -0,0 +1,32 @@ > >+// { dg-do run { target c++11 } } > >+ > >+#include <set> > >+#include <memory> > >+#include <testsuite_hooks.h> > >+#include <testsuite_allocator.h> > >+ > >+struct T { int i; }; > >+ > >+bool operator<(const T& l, const T& r) > >+{ return l.i < r.i; } > >+ > >+struct L : std::less<T> > >+{ }; > >+ > >+using __gnu_test::CustomPointerAlloc; > >+ > >+template class std::set<T, L, CustomPointerAlloc<T>>; > >+ > >+void test01() > >+{ > >+ typedef CustomPointerAlloc<T> alloc_type; > >+ typedef std::set<T, L, alloc_type> test_type; > >+ test_type v; > >+ v.insert(T()); > >+ VERIFY( ++v.begin() == v.end() ); > >+} > >+ > >+int main() > >+{ > >+ test01(); > >+} >
