public inbox for libstdc++-cvs@sourceware.org help / color / mirror / Atom feed
From: Patrick Palka <ppalka@gcc.gnu.org> To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org Subject: [gcc r10-9036] libstdc++: Fix ranges::search_n for random access iterators [PR97828] Date: Tue, 17 Nov 2020 16:28:51 +0000 (GMT) [thread overview] Message-ID: <20201117162851.AE003386F001@sourceware.org> (raw) https://gcc.gnu.org/g:04cb64dadb5c115b4ad093ff92c3f5a0a87ef15f commit r10-9036-g04cb64dadb5c115b4ad093ff92c3f5a0a87ef15f Author: Patrick Palka <ppalka@redhat.com> Date: Tue Nov 17 10:28:20 2020 -0500 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. (cherry picked from commit 8661f4faa875f361cd22a197774c1fa04cd0580b) Diff: --- libstdc++-v3/include/bits/ranges_algo.h | 4 +- .../testsuite/25_algorithms/search_n/97828.cc | 58 ++++++++++++++++++++++ 2 files changed, 61 insertions(+), 1 deletion(-) diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index 4d4f7401615..095730974cd 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -578,7 +578,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; @@ -593,6 +594,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>(); +}
reply other threads:[~2020-11-17 16:28 UTC|newest] Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20201117162851.AE003386F001@sourceware.org \ --to=ppalka@gcc.gnu.org \ --cc=gcc-cvs@gcc.gnu.org \ --cc=libstdc++-cvs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
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).