[patch] libstdc++/29988 Rb_Tree reuse allocated nodes

[François Dumont]

     For the testsuite allocator I though that for an internal allocator 
used in our tests it was ok. But alright, I will make it better and 
compatible with SimpleAllocator.


On 11/06/2014 14:02, Jonathan Wakely wrote:
>> Index: include/bits/stl_tree.h
>> ===================================================================
>> --- include/bits/stl_tree.h    (revision 211388)
>> +++ include/bits/stl_tree.h    (working copy)
>> @@ -330,6 +330,111 @@
>>                const _Rb_tree_const_iterator<_Val>& __y) 
>> _GLIBCXX_NOEXCEPT
>>     { return __x._M_node != __y._M_node; }
>>
>> +  // Functor recycling a pool of nodes and using allocation once the 
>> pool is
>> +  // empty.
>> +  template<typename _RbTree>
>> +    struct _Rb_tree_reuse_or_alloc_node
>> +    {
>
> Is there a reason to define this and _Rb_tree_alloc_node as
> namespace-scope class templates, rather than non-template members of
> _Rb_tree?
     Just to limit amount of code within _Rb_tree. I wanted to do 
something like in _Hashtable where many code is isolated in different 
types aggregated to build the final _Hashtable type. But it looks like 
you prefer it nested so I will do so.
>
> They wouldn't need to be friends if they were members, and you
> wouldn't need a typedef for _Rb_tree_alloc_node<_Rb_tree> because it
> would just be called _Rb_tree_alloc_node.
>
>> +    private:
>> +      typedef _RbTree __rb_tree;
>
> This typedef doesn't seem useful, it's only used once and is more
> characters than "_RbTree". If the class was a member of _Rb_tree it
> could just use that name.
>
>> +      typedef _Rb_tree_node<typename _RbTree::value_type> __node_type;
>
> If it was a member the value_type name would be in scope.
>
>> +    public:
>> +      _Rb_tree_reuse_or_alloc_node(const _Rb_tree_node_base& __header,
>> +                   __rb_tree& __t)
>> +    : _M_root(__header._M_parent), _M_nodes(__header._M_right), 
>> _M_t(__t)
>> +      {
>> +    if (_M_root)
>> +      _M_root->_M_parent = 0;
>> +    else
>> +      _M_nodes = 0;
>> +      }
>> +
>> +      ~_Rb_tree_reuse_or_alloc_node()
>> +      { _M_t._M_erase(static_cast<__node_type*>(_M_root)); }
>
> This type needs to be non-copyable, or unintentional copies would
> erase all the nodes and leave nothing to be reused (which might be
> difficult to detect as it would only affect performance, not
> correctness).
     Yes, sure, like in the equivalent _Hashtable types. I guess I 
didn't do so here because we might not be in c++11 so it is not as 
convenient to forbid its usage.
>
>
>> +      template<typename _Arg>
>> +    __node_type*
>> +#if __cplusplus < 201103L
>> +    operator()(const _Arg& __arg) const
>> +#else
>> +    operator()(_Arg&& __arg) const
>> +#endif
>
> Does this need to be const?
>
> I don't think it does (if you change the function templates taking a
> const _NodeGen& to take _NodeGen& instead).

Sometimes I used lambdas, I am not sure but I think it forced me to take 
functors as const lvalue reference and so the const qualification on the 
operator.

>
> That means the members of this type don't need to be 'mutable'.
>
>
>> +      typedef _Rb_tree_node_base __node_base;
>
> I'm not sure this typedef is useful either, it just means an extra
> name to remember when reading the code, when _Rb_tree_node_base is
> already in scope and probably understood by readers of the code.
>
>> +      mutable __node_base* _M_root;
>> +      mutable __node_base* _M_nodes;
>
> These members should be of type _Rb_tree::_Base_ptr, not __node_base*,
> because that's the type _Rb_tree::_M_right is declared as.
>
> I have a work-in-progress patch to make _Rb_tree use
> allocator_traits<_Node_allocator>::pointer for _Link_type, which
> might not be the same type as _Rb_tree_node<Val>*, so it is important
> to consistently use the _Base_ptr and _Link_type typedefs not the
> underlying types they refer to (because those underlying types are
> going to change soon).
>
>> +      _RbTree& _M_t;
>> +    };
>> +
>> +  // Functor similar to the previous one but without any pool of 
>> node to recycle.
>> +  template<typename _RbTree>
>> +    struct _Rb_tree_alloc_node
>
> Again, I think this should be a member of _Rb_tree.
>
>> +    {
>> +    private:
>> +      typedef _Rb_tree_node<typename _RbTree::value_type> __node_type;
>
> This typedef should be removed.
>
>> +
>> +    public:
>> +      _Rb_tree_alloc_node(_RbTree& __t)
>> +    : _M_t(__t) { }
>> +
>> +      template<typename _Arg>
>> +    __node_type*
>
> This function should return _Rb_tree::_Link_type because that's what
> _M_create_node returns.
>
>> +#if __cplusplus < 201103L
>> +    operator()(const _Arg& __arg) const
>> +#else
>> +    operator()(_Arg&& __arg) const
>> +#endif
>> +    { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
>> @@ -349,6 +454,12 @@
>>         rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
>>
>>       typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
>> +      template<typename _RT>
>> +    friend struct _Rb_tree_alloc_node;
>> +      typedef _Rb_tree_alloc_node<_Rb_tree> __alloc_node_t;
>> +      template<typename _RT>
>> +    friend struct _Rb_tree_reuse_or_alloc_node;
>> +      typedef _Rb_tree_reuse_or_alloc_node<_Rb_tree> 
>> __reuse_or_alloc_node_t;
>
> These friend declarations and typedefs become unnecessary.
>
>> @@ -389,44 +500,55 @@
>>       { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
>>
>> #if __cplusplus < 201103L
>> -      _Link_type
>> -      _M_create_node(const value_type& __x)
>> +      void
>> +      _M_construct_node(_Link_type __node, const value_type& __x)
>>       {
>> -    _Link_type __tmp = _M_get_node();
>>     __try
>> -      { get_allocator().construct(__tmp->_M_valptr(), __x); }
>> +      { get_allocator().construct(__node->_M_valptr(), __x); }
>>     __catch(...)
>>       {
>> -        _M_put_node(__tmp);
>> +        _M_put_node(__node);
>>         __throw_exception_again;
>>       }
>> +      }
>> +
>> +      _Link_type
>> +      _M_create_node(const value_type& __x)
>> +      {
>> +    _Link_type __tmp = _M_get_node();
>> +    _M_construct_node(__tmp, __x);
>>     return __tmp;
>>       }
>>
>>       void
>>       _M_destroy_node(_Link_type __p)
>> -      {
>> -    get_allocator().destroy(__p->_M_valptr());
>> -    _M_put_node(__p);
>> -      }
>> +      { get_allocator().destroy(__p->_M_valptr()); }
>> #else
>>       template<typename... _Args>
>> -        _Link_type
>> -        _M_create_node(_Args&&... __args)
>> +    void
>> +    _M_construct_node(_Link_type __node, _Args&&... __args)
>>     {
>> -      _Link_type __tmp = _M_get_node();
>>       __try
>>         {
>> -          ::new(__tmp) _Rb_tree_node<_Val>;
>> +          ::new(__node) _Rb_tree_node<_Val>();
>
> This should not be value-initialized.
>
> In C++11 all that does is zero out the __aligned_buffer's
> uninitialized storage, which is a waste of time as we're about to
> overwrite it anyway in the construct().  If you have a large
> value_type (e.g. std::map<int, std::array<double,1000>>) the redundant
> initialization has a measurable cost and we've had bug reports for
> similar code.
Sorry, didn't know about this one, I will revert it then.
>> @@ -514,11 +651,11 @@
>>       { return this->_M_impl._M_header._M_right; }
>>
>>       _Link_type
>> -      _M_begin() _GLIBCXX_NOEXCEPT
>> +      _M_begin() const _GLIBCXX_NOEXCEPT
>>       { return 
>> static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
>
> What's the purpose of this change?
> Although it can be 'const' it is consistent with the usual
> begin()/end() functions that the functions returning a mutable iterator
> are non-const and the functions returning a constant iterator are const.
>
>>       _Const_Link_type
>> -      _M_begin() const _GLIBCXX_NOEXCEPT
>> +      _M_cbegin() const _GLIBCXX_NOEXCEPT
>>       {
>>     return static_cast<_Const_Link_type>
>>       (this->_M_impl._M_header._M_parent);
>> @@ -529,7 +666,7 @@
>>       { return reinterpret_cast<_Link_type>(&this->_M_impl._M_header); }
>>
>>       _Const_Link_type
>> -      _M_end() const _GLIBCXX_NOEXCEPT
>> +      _M_cend() const _GLIBCXX_NOEXCEPT
>>       { return 
>> reinterpret_cast<_Const_Link_type>(&this->_M_impl._M_header); }
>>
>>       static const_reference
>
> I'm not very comfortable with this renaming.
>
> Having consistent _M_begin() functions allows using them in template
> code that doesn't care if it's using the const or non-const version.
>
>
I will try to remember why I did those :-)

Thanks for feedback.

François