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

[Jonathan Wakely]

On 11/08/20 10:11 +0100, Jonathan Wakely wrote:
>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.

Oops, I meant to reply to the patch with tests of course, not the
original one. Please do commit the tests.