On Tue, 8 Oct 2024 at 22:50, Jonathan Wakely <jwakely....@gmail.com> wrote:
>
>
> On Thu, 1 Aug 2024 at 18:28, François Dumont <frs.dum...@gmail.com> wrote:
>
>> Hi
>>
>> Here is a proposal to add fancy pointer support in std::_Rb_tree
>> container.
>>
>> As you'll see there are still several usages of
>> pointer_traits<>::pointer_to. The ones in _M_header_ptr() are
>> unavoidable.
>
>
> Yes, those are necessary.
>
> The pointer_to use in _M_const_cast could be simplified by adding a
> _M_self_ptr() member to _Rb_tree_pnode_base:
>
> _Base_ptr
> _M_self_ptr() _GLIBCXX_NOEXCEPT
> { return pointer_traits<_Base_ptr>::pointer_to(*this); }
>
I don't think it's needed (because _M_const_cast is only in C++11 code, I
think?) but you could define that for both C++11 and C++98:
#if __cplusplus
_Base_ptr
_M_self_ptr() noexcept
{ return pointer_traits<_Base_ptr>::pointer_to(*this); }
#else
_Base_ptr _M_self_ptr() { return this; }
#endif
Then this works for both (if you replace the 'auto'):
> _Base_ptr
> _M_self_ptr_nc() const _GLIBCXX_NOEXCEPT
> {
> auto __self = const_cast<_Rb_tree_pnode_base*>(this);
> return __self->_M_self_ptr();
> }
>
> _Const_Base_ptr
> _M_self_ptr() const _GLIBCXX_NOEXCEPT
> { return pointer_traits<_Const_Base_ptr>::pointer_to(*this); }
>
> Then _M_const_cast would do:
>
> return iterator(_M_node->_M_self_ptr_nc());
>
>
>
>> The ones to extract a node or to return a node to the
>> allocator are more questionable. Are they fine ? Is there another way to
>> mimic the static_cast<_Link_type> that can be done on raw pointers with
>> fancy pointers ?
>>
>
> I think you can just do static_cast<_Link_type>(_M_node->_M_self_ptr())
> i.e. convert the _Base_ptr to the derived _Link_type
> (we should really rename _Link_type to _Node_ptr, I keep getting confused
> by the fact that the actual links between nodes are _Base_ptr, so what does
> _Link_type mean now?!)
>
> Alternatively, you could add a _M_node_ptr() to the _Rb_tree_pnode_base
> type:
>
> template<typename _NodeT>
> __ptr_rebind<_BasePtr, _NodeT>
> _M_node_ptr() _GLIBCXX_NOEXCEPT
> {
> auto __node = static_cast<_NodeT*>(this);
> using _Node_ptr = __ptr_rebind<_BasePtr, _NodeT>;
> return pointer_traits<_Node_ptr>::pointer_to(*__node);
> }
>
You could add a C++98 version of this as well:
#if __cplusplus >= 201103L
// as above
#else
template<typename _NodeT>
_NodeT*
_M_node_ptr() _GLIBCXX_NOEXCEPT
{ return static_cast<_Node*>(this); }
#endif
Then the code to deallocate the node would not need to use #if:
_Link_type __np = __p->template _M_node_ptr<_Node_type>();
_Alloc_traits::deallocate(_M_get_Node_allocator(), __np, 1);
> Then:
> auto __np = __p->template _M_node_ptr<_Node_type>()
> _Alloc_traits::deallocate(_M_get_Node_allocator(), __np, 1);
>
>
> Some more general comments:
>
> _Rb_tree_pnode_base and the iterators could just take one template
> argument, and use __ptr_rebind to get the const pointer from the non-const
> pointer. We can add a helper to do that:
>
> template<typename _Ptr> struct __add_const_to_ptr;
> #if __cplusplus >= 201103L
> template<typename _Ptr>
> using __add_const_to_ptr = __ptr_rebind<_Ptr, const typename
> pointer_traits<_Ptr>::element_type>;
> #else
> template<typename _Ptr> struct __add_const_to_ptr;
> template<typename _Tp>
> struct __add_const_to_ptr<_Tp*>
> { typedef const _Tp* __type; };
> #endif
>
> This will let you get the FooCPtr type from the FooPtr type.
>
> A traits class could replace all the __conditional_t uses:
>
> #if __cplusplus >= 201103L
> template<typename _ValPtr>
> struct _Rb_tree_node_traits
> {
> using _Base = _Rb_tree_pnode_base<_ValPtr>;
> using _Node_type = _Rb_tree_pnode<_ValPtr>;
> using _Base_ptr = __ptr_rebind<_ValPtr, _Base>;
> using _Node_ptr = __ptr_rebind<_ValPtr, _Node>;
> using iterator = _Rb_tree_piterator<_ValPtr>;
> using const_iterator = _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 _Base;
> typedef _Rb_tree_node<_Val> _Node_type;
> typedef _Base* _Base_ptr;
> typedef _Node* _Node_ptr;
> typedef _Rb_tree_iterator<_Val> iterator;
> typedef _Rb_tree_const_iterator<_Val> const_iterator;
> };
>
> I think this would get rid of a lot of the #if checks and the
> __conditional_t uses.
>
> Otherwise this looks really good, nice work!
>
>
>>
>> A solution to this (potential) issue would be to:
>>
>> 1. Store _Node_type pointer in the data structure rather than _Node_base
>> pointer. But then _Rb_tree_pheader _M_left/_M_right could not be
>> initialized with a pointer to _M_parent which is only a _Node_base
>> instance. We would then need to init it to nullptr but I haven't check
>> impact on code and more importantly it would be an abi breaking change.
>>
>> 2. Still store _Node_type pointer in the data structure but then make
>> _M_header a _Node_type instance. In this case memory area of the
>> value_type would just be lost bytes.
>>
>>
>> libstdc++: Add fancy pointer support in std::[multi][map/set]
>>
>
> Let's just say "maps and sets" or "RB trees" instead of the more cryptic
> std::[multi][map/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.
>>
>> libstdc++-v3/ChangeLog:
>>
>> * include/bits/stl_tree.h
>> (_Rb_tree_pnode_base<>): New.
>> (_Rb_tree_node_base): Inherit from latter.
>> (_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_helpers): New.
>> (_Rb_tree_piterator): New.
>> (_Rb_tree_const_piterator): New.
>> (_Rb_tree::_Node_base, _Rb_tree::_Node_type): New.
>> (_Rb_tree): Adapt to generalize usage of _Base_ptr in place
>> of _Link_type.
>> * 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.
>>
>> François
>>
>
