Default associative containers constructors/destructor/assignment

[François Dumont]

On 17/11/2016 18:52, Jonathan Wakely wrote:
>
> On 28/10/16 21:42 +0200, François Dumont wrote:
>
>> +  template<typename _Key_compare>
>> +    struct _Rb_tree_key_compare
>> +    {
>> +      _Key_compare        _M_key_compare;
>> +
>> +      _Rb_tree_key_compare()
>> +      _GLIBCXX_NOEXCEPT_IF(
>> + is_nothrow_default_constructible<_Key_compare>::value)
>> +      : _M_key_compare()
>> +      { }
>> +
>> +      _Rb_tree_key_compare(const _Key_compare& __comp)
>> +      : _M_key_compare(__comp)
>> +      { }
>> +
>> +#if __cplusplus >= 201103L
>> +      _Rb_tree_key_compare(_Rb_tree_key_compare&& __x)
>> + noexcept(is_nothrow_copy_constructible<_Key_compare>::value)
>> +      : _M_key_compare(__x._M_key_compare)
>> +      { }
>> +#endif
>
> This constructor makes the type move-only (i.e.  non-copyable) in
> C++11 and later. It's copyable in C++98. Is that what you want?

I simply consider it was not a problem as, as you noticed, it is not used.

>
> Adding defaulted copy operations would fix that. Even if we don't
> actually need those copy operations, I'm uncomfortable with it being
> copyable in C++98 and non-copyable otherwise.
Ok, I'll add a default copy constructor for consistency like this:

       // Copy constructor added for consistency with C++98 mode.
       _Rb_tree_key_compare(const _Rb_tree_compare&) = default;

>
>> +    void
>> +    _M_reset()
>> +    {
>> +      _M_initialize();
>> +      _M_node_count = 0;
>> +    }
>
> This introduces a small change in behaviour, because _M_reset() now
> does _M_header._M_color = _S_red, which it didn't do before. That
> store is redundant. It could be avoided by just doing the three
> assignments in _M_reset() instead of calling _M_initialize().

I thought it was ok to do this additional operation for the sake of 
reusing _M_initialize(). I was compenciating it by avoiding default 
initialization when there is something to move.

>
> And we could remove _M_initialize() entirely, and remove the redundant
> mem-initializers for _M_node_count (because it's set my _M_reset and
> _M_move_data anyway):
>
>    _Rb_tree_header() _GLIBCXX_NOEXCEPT
>    {
>      _M_reset();
>      _M_header._M_color = _S_red;
>    }
>
> #if __cplusplus >= 201103L
>    _Rb_tree_header(_Rb_tree_header&& __x) noexcept
>    {
>      if (__x._M_header._M_parent != nullptr)
>       _M_move_data(__x);
>      else
>        {
>          _M_reset();
>          _M_header._M_color = _S_red;
>        }
>    }
>
>    void
>    _M_move_data(_Rb_tree_header& __x)
>    {
>      _M_header._M_parent = __x._M_header._M_parent;
>      _M_header._M_left = __x._M_header._M_left;
>      _M_header._M_right = __x._M_header._M_right;
>      _M_header._M_parent->_M_parent = &_M_header;
>      _M_node_count = __x._M_node_count;
>
>      __x._M_reset();
>    }
> #endif
>
>    void
>    _M_reset()
>    {
>      _M_header._M_parent = 0;
>      _M_header._M_left = &_M_header;
>      _M_header._M_right = &_M_header;
>      _M_node_count = 0;
>    }
>
Yes, looks nice, adopted.

Talking about _M_color I just realize that move semantic doesn't copy 
_M_color. Shouldn't we capture it along with all the other _M_header 
information ?

>
>> @@ -599,50 +674,31 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>       // Unused _Is_pod_comparator is kept as it is part of mangled 
>> name.
>>       template<typename _Key_compare,
>>            bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)>
>> -        struct _Rb_tree_impl : public _Node_allocator
>> +        struct _Rb_tree_impl
>> +    : public _Node_allocator
>> +    , public _Rb_tree_key_compare<_Key_compare>
>> +    , public _Rb_tree_header
>
> Do these need to be base classes, rather than data members?
>
> We derive from the allocator to benefit from the empty base-class
> optimization, but that isn't relevant for the _Rb_tree_key_compare and
> _Rb_tree_header types. It *could* be relevant for the comparison
> function, but would be an ABI change. We could do that ABI change
> conditionally, for gnu-versioned-namespace builds, but that's still
> possible using data members (e.g. have a data member that derives from
> the comparison function and contains the header node and/or node count
> members).
>
> Making them data members would simply mean restoring the function
> _Rb_tree_impl::_M_reset() and making it call reset on the member:
>
>     void
>     _M_reset() { _M_header._M_reset(); }
>
> The minor convenience of inheriting this function from a base class
> doesn't seem worth the stronger coupling that comes from using
> inheritance.
>
> Am I missing some other reason that inheritance is used here?

The purpose of this patch is to rely more on compiler especially in 
regards to the noexcept qualifications. This is why I started isolating 
each ressource in its own class in charge of its specificities. And I 
leave to the compiler the work of combining those types. However I also 
wanted to limit the impact of this patch on the _Rb_tree and still be 
able to use things like this->_M_impl._M_node_count or 
this->_M_impl._M_header. So the usage of inheritance.

>
>> -      _Rb_tree_impl(const _Key_compare& __comp, const 
>> _Node_allocator& __a)
>> -      : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
>> -        _M_node_count(0)
>> -      { _M_initialize(); }
>
> Please mention the removal of this constructor in the changelog.
>
>> @@ -1534,19 +1583,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>     void
>>     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
>>     _M_move_data(_Rb_tree& __x, std::true_type)
>> -    {
>> -      _M_root() = __x._M_root();
>> -      _M_leftmost() = __x._M_leftmost();
>> -      _M_rightmost() = __x._M_rightmost();
>> -      _M_root()->_M_parent = _M_end();
>> -
>> -      __x._M_root() = 0;
>> -      __x._M_leftmost() = __x._M_end();
>> -      __x._M_rightmost() = __x._M_end();
>> -
>> -      this->_M_impl._M_node_count = __x._M_impl._M_node_count;
>> -      __x._M_impl._M_node_count = 0;
>> -    }
>> +    { _M_impl._M_move_data(__x._M_impl); }
>
> This function could be moved into the class body, or just have
> 'inline' added to its definition.
>
Ok, adopted in the attached new version of the patch.

Tested under x86_64 Linux, ok to commit ?

For info, I would like to propose another bunch of simplifications of 
_Rb_tree, see other patch attached. Do you want me to propose it in 
another mail ?

François



-------------- next part --------------
A non-text attachment was scrubbed...
Name: default_tree.patch
Type: text/x-patch
Size: 18055 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20161120/1b51fc10/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: rbtree_simplifications.patch
Type: text/x-patch
Size: 3561 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20161120/1b51fc10/attachment-0001.bin>