public inbox for libstdc++@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH] libstdc++: Fix ranges::search_n for random access iterators [PR97828]
@ 2020-11-16 20:25 Patrick Palka
  2020-11-17 13:32 ` Jonathan Wakely
  0 siblings, 1 reply; 2+ messages in thread
From: Patrick Palka @ 2020-11-16 20:25 UTC (permalink / raw)
  To: gcc-patches; +Cc: libstdc++, Patrick Palka

My ranges transcription of the std::search_n implementation for random
access iterators missed a crucial part of the algorithm which the tests
unfortunately didn't catch.  When __remainder is less than __count at
the start of an iteration of the outer while loop, it means we're
continuing a run of __count - __remainder identical elements from the
previous iteration in which the backwards scan got interrupted by the
predicate failing.  If the backwards scan gets interrupted again at this
next iteration, we need to reset __remainder so that it's offset only by
the size the most recent run of identical elements, rather than by the
sum of all the (disjoint) runs.

This patch fixes this appropriately, mirroring how it's done in the
corresponding std::search_n implementation.

Tested on x86_64-pc-linux-gnu, does this look OK for trunk and the 10
branch?

libstdc++-v3/ChangeLog:

	PR libstdc++/97828
	* include/bits/ranges_algo.h (__search_n_fn::operator()): Check
	random_access_iterator before using the backtracking
	implementation.  When the backwards scan fails prematurely,
	reset __remainder appropriately.
	* testsuite/25_algorithms/search_n/97828.cc: New test.
---
 libstdc++-v3/include/bits/ranges_algo.h       |  4 +-
 .../testsuite/25_algorithms/search_n/97828.cc | 58 +++++++++++++++++++
 2 files changed, 61 insertions(+), 1 deletion(-)
 create mode 100644 libstdc++-v3/testsuite/25_algorithms/search_n/97828.cc

diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index f1a4cc24c0d..3905fe44fb2 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -579,7 +579,8 @@ namespace ranges
 	      }
 	  }
 
-	if constexpr (sized_sentinel_for<_Sent, _Iter>)
+	if constexpr (sized_sentinel_for<_Sent, _Iter>
+		      && random_access_iterator<_Iter>)
 	  {
 	    auto __tail_size = __last - __first;
 	    auto __remainder = __count;
@@ -594,6 +595,7 @@ namespace ranges
 		    if (--__remainder == 0)
 		      return {__first - __count, __first};
 		  }
+		__remainder = __count + 1 - (__first - __backtrack);
 	      }
 	    auto __i = __first + __tail_size;
 	    return {__i, __i};
diff --git a/libstdc++-v3/testsuite/25_algorithms/search_n/97828.cc b/libstdc++-v3/testsuite/25_algorithms/search_n/97828.cc
new file mode 100644
index 00000000000..f692369cd3d
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/search_n/97828.cc
@@ -0,0 +1,58 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do run { target c++2a } }
+
+// PR libstdc++/97828
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_sized_range;
+using __gnu_test::forward_iterator_wrapper;
+using __gnu_test::random_access_iterator_wrapper;
+
+template<template<typename> typename Wrapper>
+void
+test01()
+{
+  int x[] = {0,42,42,0,42,42,42};
+  test_sized_range<int, Wrapper> rx(x);
+  auto res = std::ranges::search_n(rx, 3, 42);
+  VERIFY( res.begin().ptr == x+4 && res.end().ptr == x+7 );
+}
+
+template<template<typename> typename Wrapper>
+void
+test02()
+{
+  int x[] = {0,42,42,0,42};
+  test_sized_range<int, Wrapper> rx(x);
+  auto res = std::ranges::search_n(rx, 3, 42);
+  VERIFY( res.begin().ptr == x+5 && res.end().ptr == x+5 );
+}
+
+int
+main()
+{
+  test01<forward_iterator_wrapper>();
+  test01<random_access_iterator_wrapper>();
+  test02<forward_iterator_wrapper>();
+  test02<random_access_iterator_wrapper>();
+}
-- 
2.29.2.260.ge31aba42fb


^ permalink raw reply	[flat|nested] 2+ messages in thread

* Re: [PATCH] libstdc++: Fix ranges::search_n for random access iterators [PR97828]
  2020-11-16 20:25 [PATCH] libstdc++: Fix ranges::search_n for random access iterators [PR97828] Patrick Palka
@ 2020-11-17 13:32 ` Jonathan Wakely
  0 siblings, 0 replies; 2+ messages in thread
From: Jonathan Wakely @ 2020-11-17 13:32 UTC (permalink / raw)
  To: Patrick Palka; +Cc: gcc-patches, libstdc++

On 16/11/20 15:25 -0500, Patrick Palka via Libstdc++ wrote:
>My ranges transcription of the std::search_n implementation for random
>access iterators missed a crucial part of the algorithm which the tests
>unfortunately didn't catch.  When __remainder is less than __count at
>the start of an iteration of the outer while loop, it means we're
>continuing a run of __count - __remainder identical elements from the
>previous iteration in which the backwards scan got interrupted by the
>predicate failing.  If the backwards scan gets interrupted again at this
>next iteration, we need to reset __remainder so that it's offset only by
>the size the most recent run of identical elements, rather than by the
>sum of all the (disjoint) runs.
>
>This patch fixes this appropriately, mirroring how it's done in the
>corresponding std::search_n implementation.
>
>Tested on x86_64-pc-linux-gnu, does this look OK for trunk and the 10
>branch?

OK, thanks.


^ permalink raw reply	[flat|nested] 2+ messages in thread

end of thread, other threads:[~2020-11-17 13:32 UTC | newest]

Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-11-16 20:25 [PATCH] libstdc++: Fix ranges::search_n for random access iterators [PR97828] Patrick Palka
2020-11-17 13:32 ` Jonathan Wakely

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).