diff mbox

Default associative containers constructors/destructor/assignment

Message ID 22ae1824-80d7-0875-7693-67660414b428@gmail.com
State New
Headers show

Commit Message

François Dumont Nov. 20, 2016, 6:14 p.m. UTC 
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

Comments

Jonathan Wakely Dec. 6, 2016, 11:54 a.m. UTC | #1 
On 20/11/16 19:14 +0100, François Dumont wrote:
>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 ?


Is it needed? I think the current code does the right thing, doesn't
it? I'd prefer not to change it without a testcase showing why we need
to.

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


OK.

I think I've convinced myself that using inheritance here can't alter
the layout in any way (I was worried about reuse of tail padding, for
example).

>Tested under x86_64 Linux, ok to commit ?


OK for trunk.

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


The patch is safe enough for stage 3, so please go ahead and commit
that one too, but we need to stop refactoring these things now. Any
more changes like this need to wait for stage 1.

Thanks for this work.
François Dumont Dec. 8, 2016, 8:40 p.m. UTC | #2 
On 06/12/2016 12:54, Jonathan Wakely wrote:
> On 20/11/16 19:14 +0100, François Dumont wrote:

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

>

> Is it needed? I think the current code does the right thing, doesn't

> it? I'd prefer not to change it without a testcase showing why we need

> to.


I was hoping you knew it. So I kept it unchanged and will add to my TODO 
to check this.

Committed now.

François
Jonathan Wakely Dec. 9, 2016, 9:34 a.m. UTC | #3 
On 08/12/16 21:40 +0100, François Dumont wrote:
>On 06/12/2016 12:54, Jonathan Wakely wrote:

>>On 20/11/16 19:14 +0100, François Dumont wrote:

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

>>

>>Is it needed? I think the current code does the right thing, doesn't

>>it? I'd prefer not to change it without a testcase showing why we need

>>to.

>

>I was hoping you knew it. So I kept it unchanged and will add to my 

>TODO to check this.


I think it's OK already :-)

>Committed now.


Thanks!
diff mbox

Patch

diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index 8de5e31..1bfbfa7 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -861,11 +861,22 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_Link_type
 	_M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&);
 
+      template<typename _NodeGen>
+	_Link_type
+	_M_copy(const _Rb_tree& __x, _NodeGen& __gen)
+	{
+	  _Link_type __root = _M_copy(__x._M_begin(), _M_end(), __gen);
+	  _M_leftmost() = _S_minimum(__root);
+	  _M_rightmost() = _S_maximum(__root);
+	  _M_impl._M_node_count = __x._M_impl._M_node_count;
+	  return __root;
+	}
+
       _Link_type
-      _M_copy(_Const_Link_type __x, _Base_ptr __p)
+      _M_copy(const _Rb_tree& __x)
       {
 	_Alloc_node __an(*this);
-	return _M_copy(__x, __p, __an);
+	return _M_copy(__x, __an);
       }
 
       void
@@ -903,12 +914,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       : _M_impl(__x._M_impl)
       {
 	if (__x._M_root() != 0)
-	  {
-	    _M_root() = _M_copy(__x._M_begin(), _M_end());
-	    _M_leftmost() = _S_minimum(_M_root());
-	    _M_rightmost() = _S_maximum(_M_root());
-	    _M_impl._M_node_count = __x._M_impl._M_node_count;
-	  }
+	  _M_root() = _M_copy(__x);
       }
 
 #if __cplusplus >= 201103L
@@ -920,12 +926,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
       {
 	if (__x._M_root() != nullptr)
-	  {
-	    _M_root() = _M_copy(__x._M_begin(), _M_end());
-	    _M_leftmost() = _S_minimum(_M_root());
-	    _M_rightmost() = _S_maximum(_M_root());
-	    _M_impl._M_node_count = __x._M_impl._M_node_count;
-	  }
+	  _M_root() = _M_copy(__x);
       }
 
       _Rb_tree(_Rb_tree&&) = default;
@@ -1595,10 +1596,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      auto& __val = const_cast<value_type&>(__cval);
 	      return __an(std::move_if_noexcept(__val));
 	    };
-	  _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
-	  _M_leftmost() = _S_minimum(_M_root());
-	  _M_rightmost() = _S_maximum(_M_root());
-	  _M_impl._M_node_count = __x._M_impl._M_node_count;
+	  _M_root() = _M_copy(__x, __lbd);
 	}
     }
 
@@ -1636,10 +1634,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      auto& __val = const_cast<value_type&>(__cval);
 	      return __roan(std::move_if_noexcept(__val));
 	    };
-	  _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
-	  _M_leftmost() = _S_minimum(_M_root());
-	  _M_rightmost() = _S_maximum(_M_root());
-	  _M_impl._M_node_count = __x._M_impl._M_node_count;
+	  _M_root() = _M_copy(__x, __lbd);
 	  __x.clear();
 	}
     }
@@ -1653,10 +1648,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	     && is_nothrow_move_assignable<_Compare>::value)
     {
       _M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare);
-      constexpr bool __move_storage =
-	  _Alloc_traits::_S_propagate_on_move_assign()
-	  || _Alloc_traits::_S_always_equal();
-      _M_move_assign(__x, __bool_constant<__move_storage>());
+      _M_move_assign(__x, __bool_constant<_Alloc_traits::_S_nothrow_move()>());
       return *this;
     }
 
@@ -1716,12 +1708,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  _M_impl._M_reset();
 	  _M_impl._M_key_compare = __x._M_impl._M_key_compare;
 	  if (__x._M_root() != 0)
-	    {
-	      _M_root() = _M_copy(__x._M_begin(), _M_end(), __roan);
-	      _M_leftmost() = _S_minimum(_M_root());
-	      _M_rightmost() = _S_maximum(_M_root());
-	      _M_impl._M_node_count = __x._M_impl._M_node_count;
-	    }
+	    _M_root() = _M_copy(__x, __roan);
 	}
 
       return *this;