libstdc++: Fix ranges::search_n for random access iterators [PR97828]
authorPatrick Palka <ppalka@redhat.com>
Tue, 17 Nov 2020 15:28:20 +0000 (10:28 -0500)
committerPatrick Palka <ppalka@redhat.com>
Tue, 17 Nov 2020 15:28:20 +0000 (10:28 -0500)
commit8661f4faa875f361cd22a197774c1fa04cd0580b
tree42ebf4b7c01a3d975b557b6148f7dbd269b09bb5
parentd7ab349c44f30bed90b03b45865f6c7c5de1dfd8
libstdc++: Fix ranges::search_n for random access iterators [PR97828]

My ranges transcription of the std::search_n implementation for random
access iterators missed a crucial part of the algorithm which the
existing tests didn't exercise.  When __remainder is less than __count
at the start of an iteration of the outer while loop, it means we're
continuing a partial match of __count - __remainder elements from the
previous iteration.  If at the end of the iteration we don't complete
this partial match, we need to reset __remainder so that it's only
offset by the size of the most recent partial match before starting the
next iteration.

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

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
libstdc++-v3/testsuite/25_algorithms/search_n/97828.cc [new file with mode: 0644]