Re: Fix tree containers debug mode C++11 allocator awareness

[François Dumont <frs dot dumont at gmail dot com>]

On 12/22/2013 09:55 PM, François Dumont wrote:
> On 12/22/2013 12:51 PM, Jonathan Wakely wrote:
> > On 21 December 2013 08:51, François Dumont wrote:
> > > Any feedback for this proposal ?
> > It looks good but I don't have time to review it fully yet, please be 
> > patient.
> >
> > I'm more concerned about your comment about the non-debug mode
> > implementation being incorrect, could you provide more details?
> > .
>     That's not a big issue. The constructor taking a rvalue reference 
> and an allocator doesn't take care about safe iterators. They should 
> be swap like in the move constructor when allocator is equivalent and 
> invalidated if we have not been able to move memory. I plan to submit 
> a patch to fix all implementations the same way at once but I can 
> include it in this patch if you prefer.

Following agreement given here:

http://gcc.gnu.org/ml/libstdc++/2014-01/msg00066.html

Attached patch applied.

Profile mode will need the same kind of patch too.

2014-01-13  François Dumont  <fdumont@gcc.gnu.org>

    * include/debug/set.h (set): Implement C++11 allocator-aware
    container requirements.
    * include/debug/map.h (map): Likewise.
    * include/debug/multiset.h (multiset): Likewise.
    * include/debug/multimap.h (multimap): Likewise.
    * include/debug/set.h (set::operator=(set&&)): Add noexcept and
    fix implementation regarding management of safe iterators.
    * include/debug/map.h (map::operator=(map&&)): Likewise.
    * include/debug/multiset.h (multiset::operator=(multiset&&)): Likewise.
    * include/debug/multimap.h (multimap::operator=(multimap&&)):
    Likewise.
    * include/debug/set.h (set::operator=(std::initializer_list<>)):
    Rely on the same operator from normal mode.
    * include/debug/map.h (map::operator=(std::initializer_list<>)):
    Likewise.
    * include/debug/multiset.h
    (multiset::operator=(std::initializer_list<>)): Likewise.
    * include/debug/multimap.h
    (multimap::operator=(std::initializer_list<>)): Likewise.
    * include/debug/set.h (set::swap(set&)): Add noexcept
    specification, add allocator equality check.
    * include/debug/map.h (map::swap(map&)): Likewise.
    * include/debug/multiset.h (multiset::swap(multiset&)): Likewise.
    * include/debug/multimap.h (multimap::swap(multimap&)): Likewise.

François

Index: include/debug/set.h
===================================================================
--- include/debug/set.h	(revision 206587)
+++ include/debug/set.h	(working copy)
@@ -49,6 +49,10 @@
       typedef typename _Base::const_iterator _Base_const_iterator;
       typedef typename _Base::iterator _Base_iterator;
       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
+#if __cplusplus >= 201103L
+      typedef __gnu_cxx::__alloc_traits<typename
+					_Base::allocator_type> _Alloc_traits;
+#endif
     public:
       // types:
       typedef _Key				    key_type;
@@ -101,6 +105,28 @@
 	  const _Compare& __comp = _Compare(),
 	  const allocator_type& __a = allocator_type())
       : _Base(__l, __comp, __a) { }
+
+      explicit
+      set(const allocator_type& __a)
+      : _Base(__a) { }
+
+      set(const set& __x, const allocator_type& __a)
+      : _Base(__x, __a) { }
+
+      set(set&& __x, const allocator_type& __a)
+      : _Base(std::move(__x._M_base()), __a) { }
+
+      set(initializer_list<value_type> __l, const allocator_type& __a)
+	: _Base(__l, __a)
+      { }
+
+      template<typename _InputIterator>
+        set(_InputIterator __first, _InputIterator __last,
+	    const allocator_type& __a)
+	: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
+								     __last)),
+		__gnu_debug::__base(__last), __a)
+        { }
 #endif
 
       ~set() _GLIBCXX_NOEXCEPT { }
@@ -108,7 +134,7 @@
       set&
       operator=(const set& __x)
       {
-	*static_cast<_Base*>(this) = __x;
+	_M_base() = __x;
 	this->_M_invalidate_all();
 	return *this;
       }
@@ -116,20 +142,25 @@
 #if __cplusplus >= 201103L
       set&
       operator=(set&& __x)
+      noexcept(_Alloc_traits::_S_nothrow_move())
       {
-	// NB: DR 1204.
-	// NB: DR 675.
 	__glibcxx_check_self_move_assign(__x);
-	clear();
-	swap(__x);
+	bool xfer_memory = _Alloc_traits::_S_propagate_on_move_assign()
+	    || __x.get_allocator() == this->get_allocator();
+	_M_base() = std::move(__x._M_base());
+	if (xfer_memory)
+	  this->_M_swap(__x);
+	else
+	  this->_M_invalidate_all();
+	__x._M_invalidate_all();
 	return *this;
       }
 
       set&
       operator=(initializer_list<value_type> __l)
       {
-	this->clear();
-	this->insert(__l);
+	_M_base() = __l;
+	this->_M_invalidate_all();
 	return *this;
       }
 #endif
@@ -337,7 +368,14 @@
 
       void
       swap(set& __x)
+#if __cplusplus >= 201103L
+      noexcept(_Alloc_traits::_S_nothrow_swap())
+#endif
       {
+#if __cplusplus >= 201103L
+	if (!_Alloc_traits::_S_propagate_on_swap())
+	  __glibcxx_check_equal_allocs(__x);
+#endif
 	_Base::swap(__x);
 	this->_M_swap(__x);
       }
Index: include/debug/map.h
===================================================================
--- include/debug/map.h	(revision 206587)
+++ include/debug/map.h	(working copy)
@@ -49,6 +49,11 @@
       typedef typename _Base::const_iterator _Base_const_iterator;
       typedef typename _Base::iterator _Base_iterator;
       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
+
+#if __cplusplus >= 201103L
+      typedef __gnu_cxx::__alloc_traits<typename
+					_Base::allocator_type> _Alloc_traits;
+#endif
     public:
       // types:
       typedef _Key                                  key_type;
@@ -101,6 +106,27 @@
 	  const _Compare& __c = _Compare(),
 	  const allocator_type& __a = allocator_type())
       : _Base(__l, __c, __a) { }
+
+      explicit
+      map(const allocator_type& __a)
+      : _Base(__a) { }
+
+      map(const map& __m, const allocator_type& __a)
+      : _Base(__m, __a) { }
+
+      map(map&& __m, const allocator_type& __a)
+      : _Base(std::move(__m._M_base()), __a) { }
+
+      map(initializer_list<value_type> __l, const allocator_type& __a)
+      : _Base(__l, __a) { }
+
+      template<typename _InputIterator>
+        map(_InputIterator __first, _InputIterator __last,
+	    const allocator_type& __a)
+	  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
+								       __last)),
+		  __gnu_debug::__base(__last), __a)
+	{ }
 #endif
 
       ~map() _GLIBCXX_NOEXCEPT { }
@@ -108,7 +134,7 @@
       map&
       operator=(const map& __x)
       {
-	*static_cast<_Base*>(this) = __x;
+	_M_base() = __x;
 	this->_M_invalidate_all();
 	return *this;
       }
@@ -116,20 +142,25 @@
 #if __cplusplus >= 201103L
       map&
       operator=(map&& __x)
+      noexcept(_Alloc_traits::_S_nothrow_move())
       {
-	// NB: DR 1204.
-	// NB: DR 675.
 	__glibcxx_check_self_move_assign(__x);
-	clear();
-	swap(__x);
+	bool xfer_memory = _Alloc_traits::_S_propagate_on_move_assign()
+	    || __x.get_allocator() == this->get_allocator();
+	_M_base() = std::move(__x._M_base());
+	if (xfer_memory)
+	  this->_M_swap(__x);
+	else
+	  this->_M_invalidate_all();
+	__x._M_invalidate_all();
 	return *this;
       }
 
       map&
       operator=(initializer_list<value_type> __l)
       {
-	this->clear();
-	this->insert(__l);
+	_M_base() = __l;
+	this->_M_invalidate_all();
 	return *this;
       }
 #endif
@@ -360,7 +391,14 @@
 
       void
       swap(map& __x)
+#if __cplusplus >= 201103L
+      noexcept(_Alloc_traits::_S_nothrow_swap())
+#endif
       {
+#if __cplusplus >= 201103L
+	if (!_Alloc_traits::_S_propagate_on_swap())
+	  __glibcxx_check_equal_allocs(__x);
+#endif
 	_Base::swap(__x);
 	this->_M_swap(__x);
       }
Index: include/debug/multiset.h
===================================================================
--- include/debug/multiset.h	(revision 206587)
+++ include/debug/multiset.h	(working copy)
@@ -49,6 +49,11 @@
       typedef typename _Base::const_iterator _Base_const_iterator;
       typedef typename _Base::iterator _Base_iterator;
       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
+
+#if __cplusplus >= 201103L
+      typedef __gnu_cxx::__alloc_traits<typename
+					_Base::allocator_type> _Alloc_traits;
+#endif
     public:
       // types:
       typedef _Key				     key_type;
@@ -101,6 +106,28 @@
 	       const _Compare& __comp = _Compare(),
 	       const allocator_type& __a = allocator_type())
       : _Base(__l, __comp, __a) { }
+
+      explicit
+      multiset(const allocator_type& __a)
+      : _Base(__a) { }
+
+      multiset(const multiset& __m, const allocator_type& __a)
+      : _Base(__m, __a) { }
+
+      multiset(multiset&& __m, const allocator_type& __a)
+      : _Base(std::move(__m._M_base()), __a) { }
+
+      multiset(initializer_list<value_type> __l, const allocator_type& __a)
+	: _Base(__l, __a)
+      { }
+
+      template<typename _InputIterator>
+        multiset(_InputIterator __first, _InputIterator __last,
+		 const allocator_type& __a)
+	  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
+								       __last)),
+		  __gnu_debug::__base(__last), __a)
+        { }
 #endif
 
       ~multiset() _GLIBCXX_NOEXCEPT { }
@@ -108,7 +135,7 @@
       multiset&
       operator=(const multiset& __x)
       {
-	*static_cast<_Base*>(this) = __x;
+	_M_base() = __x;
 	this->_M_invalidate_all();
 	return *this;
       }
@@ -116,20 +143,25 @@
 #if __cplusplus >= 201103L
       multiset&
       operator=(multiset&& __x)
+      noexcept(_Alloc_traits::_S_nothrow_move())
       {
-	// NB: DR 1204.
-	// NB: DR 675.
 	__glibcxx_check_self_move_assign(__x);
-	clear();
-	swap(__x);
+	bool xfer_memory = _Alloc_traits::_S_propagate_on_move_assign()
+	    || __x.get_allocator() == this->get_allocator();
+	_M_base() = std::move(__x._M_base());
+	if (xfer_memory)
+	  this->_M_swap(__x);
+	else
+	  this->_M_invalidate_all();
+	__x._M_invalidate_all();
 	return *this;
       }
 
       multiset&
       operator=(initializer_list<value_type> __l)
       {
-	this->clear();
-	this->insert(__l);
+	_M_base() = __l;
+	this->_M_invalidate_all();
 	return *this;
       }
 #endif
@@ -328,7 +360,14 @@
 
       void
       swap(multiset& __x)
+#if __cplusplus >= 201103L
+      noexcept(_Alloc_traits::_S_nothrow_swap())
+#endif
       {
+#if __cplusplus >= 201103L
+	if (!_Alloc_traits::_S_propagate_on_swap())
+	  __glibcxx_check_equal_allocs(__x);
+#endif
 	_Base::swap(__x);
 	this->_M_swap(__x);
       }
Index: include/debug/multimap.h
===================================================================
--- include/debug/multimap.h	(revision 206587)
+++ include/debug/multimap.h	(working copy)
@@ -50,6 +50,11 @@
       typedef typename _Base::const_iterator _Base_const_iterator;
       typedef typename _Base::iterator _Base_iterator;
       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
+
+#if __cplusplus >= 201103L
+      typedef __gnu_cxx::__alloc_traits<typename
+					_Base::allocator_type> _Alloc_traits;
+#endif
     public:
       // types:
       typedef _Key				     key_type;
@@ -102,6 +107,28 @@
 	       const _Compare& __c = _Compare(),
 	       const allocator_type& __a = allocator_type())
       : _Base(__l, __c, __a) { }
+
+      explicit
+      multimap(const allocator_type& __a)
+      : _Base(__a) { }
+
+      multimap(const multimap& __m, const allocator_type& __a)
+      : _Base(__m, __a) { }
+
+      multimap(multimap&& __m, const allocator_type& __a)
+      : _Base(std::move(__m._M_base()), __a) { }
+
+      multimap(initializer_list<value_type> __l, const allocator_type& __a)
+      : _Base(__l, __a)
+      { }
+
+      template<typename _InputIterator>
+        multimap(_InputIterator __first, _InputIterator __last,
+		 const allocator_type& __a)
+	: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
+								     __last)),
+		__gnu_debug::__base(__last), __a)
+      { }
 #endif
 
       ~multimap() _GLIBCXX_NOEXCEPT { }
@@ -109,7 +136,7 @@
       multimap&
       operator=(const multimap& __x)
       {
-	*static_cast<_Base*>(this) = __x;
+	_M_base() = __x;
 	this->_M_invalidate_all();
 	return *this;
       }
@@ -117,20 +144,25 @@
 #if __cplusplus >= 201103L
       multimap&
       operator=(multimap&& __x)
+      noexcept(_Alloc_traits::_S_nothrow_move())
       {
-	// NB: DR 1204.
-	// NB: DR 675.
 	__glibcxx_check_self_move_assign(__x);
-	clear();
-	swap(__x);
+	bool xfer_memory = _Alloc_traits::_S_propagate_on_move_assign()
+	    || __x.get_allocator() == this->get_allocator();
+	_M_base() = std::move(__x._M_base());
+	if (xfer_memory)
+	  this->_M_swap(__x);
+	else
+	  this->_M_invalidate_all();
+	__x._M_invalidate_all();
 	return *this;
       }
 
       multimap&
       operator=(initializer_list<value_type> __l)
       {
-	this->clear();
-	this->insert(__l);
+	_M_base() = __l;
+	this->_M_invalidate_all();
 	return *this;
       }
 #endif
@@ -343,7 +375,14 @@
 
       void
       swap(multimap& __x)
+#if __cplusplus >= 201103L
+      noexcept(_Alloc_traits::_S_nothrow_swap())
+#endif
       {
+#if __cplusplus >= 201103L
+	if (!_Alloc_traits::_S_propagate_on_swap())
+	  __glibcxx_check_equal_allocs(__x);
+#endif
 	_Base::swap(__x);
 	this->_M_swap(__x);
       }