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 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 > inhttps://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> > <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> > <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> > <jwakely....@gmail.com> wrote: > > On Thu, 17 Oct 2024 at 20:52, François Dumont <frs.dum...@gmail.com> > <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*> andstd::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>, > butstd::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). > > >
