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); }
_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);
}
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
>
