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

[Jonathan Wakely]

On 11/06/14 21:56 +0200, François Dumont wrote:
>    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.


I suppose it's OK for now, and we can change it later if we need it to
work with other  allocators.


>>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.

Yes, I think it's better to define them inside _Rb_tree rather than
having separate templates in namespace std which are not general
purpose or useful anywhere except _Rb_tree.

(I find the fragmented _Hashtable design quite confusing!)

>>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.

You could delete the functions for C++11 only - that would probably be
good enough to catch any accidental misuse.

>>
>>>+      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.

If you declare the lambda 'mutable' then it's allowed to modify its
captures.


>>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 :-)

OK thanks :-)

I went through the rest of the patch and it is fine - I like the
overall change very much, it's a good improvement, so we definitely
want to apply a revised patch. Thanks for working on it.