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 in std::_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 and https://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> 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> 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> >>>>>wrote: >>>>>> >>>>>>On Thu, 17 Oct 2024 at 20:52, François Dumont <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 potential >>>>>>>allocator::const_pointer. >>>>>>Do you mean consider the case where Alloc::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 by std::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() > { return std::__addressof(_M_value_field); } > >+ __attribute__((__always_inline__)) > const _Val* > _M_valptr() const > { return std::__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 that std::set<int> and std::set<long> and std::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, so std::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<typename std::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 typename iterator::_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, because std::map and std::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 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(); >+} 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).
