diff mbox series

[committed] libstdc++: Fix std::find for non-contiguous iterators [PR115799]

Message ID 20240707113009.288827-1-jwakely@redhat.com
State New
Headers show
Series [committed] libstdc++: Fix std::find for non-contiguous iterators [PR115799] | expand

Commit Message

Jonathan Wakely July 7, 2024, 11:29 a.m. UTC 
Tested x86_64-linux. Pushed to trunk.

-- >8 --

The r15-1857 change didn't correctly restrict the new optimization to
contiguous iterators.

libstdc++-v3/ChangeLog:

	PR libstdc++/115799
	* include/bits/stl_algo.h (find): Use 'if constexpr' so that
	memchr optimization is a discarded statement for non-contiguous
	iterators.
	* testsuite/25_algorithms/find/bytes.cc: Check with input
	iterators.
---
 libstdc++-v3/include/bits/stl_algo.h          | 44 +++++++++----------
 .../testsuite/25_algorithms/find/bytes.cc     |  7 +++
 2 files changed, 27 insertions(+), 24 deletions(-)
diff mbox series

Patch

diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 45c3b591326..d250b2e04d4 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -3849,32 +3849,28 @@  _GLIBCXX_BEGIN_NAMESPACE_ALGO
 #if __cpp_if_constexpr && __glibcxx_type_trait_variable_templates
       using _ValT = typename iterator_traits<_InputIterator>::value_type;
       if constexpr (__can_use_memchr_for_find<_ValT, _Tp>)
-	{
-	  // If converting the value to the 1-byte value_type alters its value,
-	  // then it would not be found by std::find using equality comparison.
-	  // We need to check this here, because otherwise something like
-	  // memchr("a", 'a'+256, 1) would give a false positive match.
-	  if (!(static_cast<_ValT>(__val) == __val))
-	    return __last;
-	  else if (!__is_constant_evaluated())
-	    {
-	      const void* __p0 = nullptr;
-	      if constexpr (is_pointer_v<decltype(std::__niter_base(__first))>)
-		__p0 = std::__niter_base(__first);
+	if constexpr (is_pointer_v<decltype(std::__niter_base(__first))>
 #if __cpp_lib_concepts
-	      else if constexpr (contiguous_iterator<_InputIterator>)
-		__p0 = std::to_address(__first);
+			|| contiguous_iterator<_InputIterator>
 #endif
-	      if (__p0)
-		{
-		  const int __ival = static_cast<int>(__val);
-		  if (auto __n = std::distance(__first, __last); __n > 0)
-		    if (auto __p1 = __builtin_memchr(__p0, __ival, __n))
-		      return __first + ((const char*)__p1 - (const char*)__p0);
-		  return __last;
-		}
-	    }
-	}
+		     )
+	  {
+	    // If conversion to the 1-byte value_type alters the value,
+	    // it would not be found by std::find using equality comparison.
+	    // We need to check this here, because otherwise something like
+	    // memchr("a", 'a'+256, 1) would give a false positive match.
+	    if (!(static_cast<_ValT>(__val) == __val))
+	      return __last;
+	    else if (!__is_constant_evaluated())
+	      {
+		const void* __p0 = std::__to_address(__first);
+		const int __ival = static_cast<int>(__val);
+		if (auto __n = std::distance(__first, __last); __n > 0)
+		  if (auto __p1 = __builtin_memchr(__p0, __ival, __n))
+		    return __first + ((const char*)__p1 - (const char*)__p0);
+		return __last;
+	      }
+	  }
 #endif
 
       return std::__find_if(__first, __last,
diff --git a/libstdc++-v3/testsuite/25_algorithms/find/bytes.cc b/libstdc++-v3/testsuite/25_algorithms/find/bytes.cc
index f4ac5d4018d..e1d6c01ab21 100644
--- a/libstdc++-v3/testsuite/25_algorithms/find/bytes.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/find/bytes.cc
@@ -3,6 +3,7 @@ 
 #include <algorithm>
 #include <cstddef> // std::byte
 #include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
 
 // PR libstdc++/88545 made std::find use memchr as an optimization.
 // This test verifies that it didn't change any semantics.
@@ -113,6 +114,12 @@  test_non_characters()
 #endif
 }
 
+void
+test_pr115799c2(__gnu_test::input_iterator_wrapper<char> i)
+{
+  (void) std::find(i, i, 'a');
+}
+
 int main()
 {
   test_char<char>();