Re: [PATCH] PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique

[Jonathan Wakely <jwakely@redhat.com>]

On 27/12/19 11:57 +0100, François Dumont wrote:
>Here is the patch to extend DR 526 to forward_list and list remove_if 
>and unique.
>
>As the adopted pattern is simpler I also applied it to the remove methods.
>
>    PR libstdc++/91620
>    * include/bits/forward_list.tcc (forward_list<>::remove): Collect nodes
>    to destroy in an intermediate forward_list.
>    (forward_list<>::remove_if, forward_list<>::unique): Likewise.
>    * include/bits/list.tcc (list<>::remove, list<>::unique): Likewise.
>    (list<>::remove_if): Likewise.
>    * include/debug/forward_list (forward_list<>::_M_erase_after): Remove.
>    (forward_list<>::erase_after): Adapt.
>    (forward_list<>::remove, forward_list<>::remove_if): Collect nodes to
>    destroy in an intermediate forward_list.
>    (forward_list<>::unique): Likewise.
>    * include/debug/list (list<>::remove, list<>::unique): Likewise.
>    (list<>::remove_if): Likewise.
>
>Tested under Linux x86_64 normal and debug modes.
>
>Ok to commit ?
>
>François
>


>diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc
>index 088111e3330..70de7e75a43 100644
>--- a/libstdc++-v3/include/bits/forward_list.tcc
>+++ b/libstdc++-v3/include/bits/forward_list.tcc
>@@ -290,30 +290,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>     remove(const _Tp& __val) -> __remove_return_type
>     {
>       size_type __removed __attribute__((__unused__)) = 0;
>-      _Node_base* __curr = &this->_M_impl._M_head;
>-      _Node_base* __extra = nullptr;
>+      forward_list __to_destroy(get_allocator());
> 
>-      while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
>-	{
>+      auto __prev_it = cbefore_begin();
>+      while (_Node* __tmp = static_cast<_Node*>(__prev_it._M_node->_M_next))
> 	if (*__tmp->_M_valptr() == __val)
> 	  {
>-	      if (__tmp->_M_valptr() != std::__addressof(__val))
>-		{
>-		  this->_M_erase_after(__curr);
>+	    __to_destroy.splice_after(__to_destroy.cbefore_begin(),
>+				      *this, __prev_it);
> 	    _GLIBCXX20_ONLY( __removed++ );
>-		  continue;
> 	  }
> 	else
>-		__extra = __curr;
>-	    }
>-	  __curr = __curr->_M_next;
>-	}
>+	  ++__prev_it;
> 
>-      if (__extra)
>-	{
>-	  this->_M_erase_after(__extra);
>-	  _GLIBCXX20_ONLY( __removed++ );
>-	}
>       return _GLIBCXX20_ONLY( __removed );
>     }
> 
>@@ -324,17 +313,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>       remove_if(_Pred __pred) -> __remove_return_type
>       {
> 	size_type __removed __attribute__((__unused__)) = 0;
>-	_Node_base* __curr = &this->_M_impl._M_head;
>-	while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
>-	  {
>+	forward_list __to_destroy(get_allocator());
>+
>+	auto __prev_it = cbefore_begin();
>+	while (_Node* __tmp = static_cast<_Node*>(__prev_it._M_node->_M_next))
> 	  if (__pred(*__tmp->_M_valptr()))
> 	    {
>-		this->_M_erase_after(__curr);
>+	      __to_destroy.splice_after(__to_destroy.cbefore_begin(),
>+					*this, __prev_it);
> 	      _GLIBCXX20_ONLY( __removed++ );
> 	    }
> 	  else
>-	      __curr = __curr->_M_next;
>-	  }
>+	    ++__prev_it;
>+
> 	return _GLIBCXX20_ONLY( __removed );
>       }
> 
>@@ -348,19 +339,23 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> 	iterator __last = end();
> 	if (__first == __last)
> 	  return _GLIBCXX20_ONLY(0);
>+
>+	forward_list __to_destroy(get_allocator());
> 	size_type __removed __attribute__((__unused__)) = 0;
> 	iterator __next = __first;
> 	while (++__next != __last)
> 	{
> 	  if (__binary_pred(*__first, *__next))
> 	    {
>-	      erase_after(__first);
>+	      __to_destroy.splice_after(__to_destroy.cbefore_begin(),
>+					*this, __first);
> 	      _GLIBCXX20_ONLY( __removed++ );
> 	    }
> 	  else
> 	    __first = __next;
> 	  __next = __first;
> 	}
>+
> 	return _GLIBCXX20_ONLY( __removed );
>       }
> 
>diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc
>index 0ac6654b079..5a6fd5b0824 100644
>--- a/libstdc++-v3/include/bits/list.tcc
>+++ b/libstdc++-v3/include/bits/list.tcc
>@@ -331,10 +331,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>     list<_Tp, _Alloc>::
>     remove(const value_type& __value)
>     {
>+#if !_GLIBCXX_USE_CXX11_ABI
>       size_type __removed __attribute__((__unused__)) = 0;
>+#endif
>+      list __to_destroy(get_allocator());
>       iterator __first = begin();
>       iterator __last = end();
>-      iterator __extra = __last;
>       while (__first != __last)
> 	{
> 	  iterator __next = __first;
>@@ -344,22 +346,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> 	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
> 	      // 526. Is it undefined if a function in the standard changes
> 	      // in parameters?
>-	      if (std::__addressof(*__first) != std::__addressof(__value))
>-		{
>-		  _M_erase(__first);
>+	      __to_destroy.splice(__to_destroy.begin(), *this, __first);
>+#if !_GLIBCXX_USE_CXX11_ABI
> 	      _GLIBCXX20_ONLY( __removed++ );
>+#endif

The point of the _GLIBCXX20_ONLY macro was to avoid cluttering this
function with #ifdef directives. If it's going to be full of #ifdef
now anyway, there's no real benefit to using _GLIBCXX20_ONLY.

This could now be:

#if __cplusplus > 201703L && ! _GLIBCXX_USE_CXX11_ABI
	      __removed++;
#endif

and so on.

> 	    }
>-	      else
>-		__extra = __first;
>-	    }
>+
> 	  __first = __next;
> 	}
>-      if (__extra != __last)
>-	{
>-	  _M_erase(__extra);
>-	  _GLIBCXX20_ONLY( __removed++ );
>-	}
>+
>+#if !_GLIBCXX_USE_CXX11_ABI
> 	return _GLIBCXX20_ONLY( __removed );
>+#else
>+	return _GLIBCXX20_ONLY( __to_destroy.size() );
>+#endif

Although this becomes pretty ugly:

#if __cplusplus > 201703L
# if _GLIBCXX_USE_CXX11_ABI
	return __to_destroy.size();
# else
	return __removed;
# endif
#endif

So maybe _GLIBCXX20_ONLY is still worthwhile.

The other alternative would be to define a new type right at the start
which keeps count if needed:

#if __cplusplus > 201703L && ! _GLIBCXX_USE_CXX11_ABI
   struct _VictimList : list
   {
     void splice(list::iterator __p, list& __x, list::iterator __i)
     {
       list::splice(__p, __x, __i);
       ++_M_size;
     }
     size_type size() const { return _M_size; }
     size_type _M_size = 0;
   } __to_destroy;
#else
   list __to_destroy;
#endif

   // ...

   return _GLIBCXX20_ONLY(__to_destroy.size());

With this the only conditional compilation is at the start of the
function and the one use of _GLIBCXX20_ONLY at the end. The rest of
the function body has no #if or macros at all.

Your patch is OK for master. We can revisit it later to tidy it up.

Thanks.