diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -42,8 +42,8 @@ Write,copy_backward,Not assigned,n/a,Not started Write,move,Not assigned,n/a,Not started Write,move_backward,Not assigned,n/a,Not started -Write,fill,Not assigned,n/a,Not started -Write,fill_n,Not assigned,n/a,Not started +Write,fill,Nikolas Klauser,`D123462 `_,✅ +Write,fill_n,Nikolas Klauser,`D123462 `_,✅ Write,transform,Nikolas Klauser,`D122173 `_,✅ Write,generate,Not assigned,n/a,Not started Write,generate_n,Not assigned,n/a,Not started diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -68,6 +68,8 @@ __algorithm/push_heap.h __algorithm/ranges_count.h __algorithm/ranges_count_if.h + __algorithm/ranges_fill.h + __algorithm/ranges_fill_n.h __algorithm/ranges_find.h __algorithm/ranges_find_if.h __algorithm/ranges_find_if_not.h diff --git a/libcxx/include/__algorithm/ranges_fill.h b/libcxx/include/__algorithm/ranges_fill.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_fill.h @@ -0,0 +1,59 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_FILL_H +#define _LIBCPP___ALGORITHM_RANGES_FILL_H + +#include <__algorithm/ranges_fill_n.h> +#include <__config> +#include <__iterator/concepts.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __fill { +struct __fn { +template _Iter, sentinel_for<_Iter> _Sent> +_LIBCPP_HIDE_FROM_ABI constexpr +_Iter operator()(_Iter __first, _Sent __last, const _Type& __value) const { + if constexpr(random_access_iterator<_Iter>) { + return ranges::fill_n(__first, __last - __first, __value); + } else { + for (; __first != __last; ++__first) + *__first = __value; + return __first; + } +} + +template _Range> +_LIBCPP_HIDE_FROM_ABI constexpr +borrowed_iterator_t<_Range> operator()(_Range&& __range, const _Type& __value) const { + return (*this)(ranges::begin(__range), ranges::end(__range), __value); +} +}; +} // namespace __fill + +inline namespace __cpo { + inline constexpr auto fill = __fill::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_FILL_H diff --git a/libcxx/include/__algorithm/ranges_fill_n.h b/libcxx/include/__algorithm/ranges_fill_n.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_fill_n.h @@ -0,0 +1,48 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_FILL_N_H +#define _LIBCPP___ALGORITHM_RANGES_FILL_N_H + +#include <__config> +#include <__iterator/concepts.h> +#include <__iterator/incrementable_traits.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __fill_n { +struct __fn { +template _Iter> +_LIBCPP_HIDE_FROM_ABI constexpr +_Iter operator()(_Iter __first, iter_difference_t<_Iter> __n, const _Type& __value) const { + for (; __n != 0; --__n) { + *__first = __value; + ++__first; + } + return __first; +} +}; +} // namespace __fill_n + +inline namespace __cpo { + inline constexpr auto fill_n = __fill_n::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_FILL_N_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -165,6 +165,15 @@ indirect_unary_predicate, Proj>> Pred> constexpr range_difference_t count_if(R&& r, Pred pred, Proj proj = {}); // since C++20 + + template O> + constexpr O ranges::fill_n(O first, iter_difference_t n, const T& value); // since C++20 + + template O, sentinel_for S> + constexpr O ranges::fill(O first, S last, const T& value); // since C++20 + + template R> + constexpr borrowed_iterator_t ranges::fill(R&& r, const T& value); // since C++20 } constexpr bool // constexpr in C++20 @@ -884,6 +893,8 @@ #include <__algorithm/push_heap.h> #include <__algorithm/ranges_count.h> #include <__algorithm/ranges_count_if.h> +#include <__algorithm/ranges_fill.h> +#include <__algorithm/ranges_fill_n.h> #include <__algorithm/ranges_find.h> #include <__algorithm/ranges_find_if.h> #include <__algorithm/ranges_find_if_not.h> diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap --- a/libcxx/include/module.modulemap +++ b/libcxx/include/module.modulemap @@ -296,6 +296,8 @@ module push_heap { private header "__algorithm/push_heap.h" } module ranges_count { private header "__algorithm/ranges_count.h" } module ranges_count_if { private header "__algorithm/ranges_count_if.h" } + module ranges_fill { private header "__algorithm/ranges_fill.h" } + module ranges_fill_n { private header "__algorithm/ranges_fill_n.h" } module ranges_find { private header "__algorithm/ranges_find.h" } module ranges_find_if { private header "__algorithm/ranges_find_if.h" } module ranges_find_if_not { private header "__algorithm/ranges_find_if_not.h" } diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -105,6 +105,8 @@ #include <__algorithm/push_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/push_heap.h'}} #include <__algorithm/ranges_count.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count.h'}} #include <__algorithm/ranges_count_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count_if.h'}} +#include <__algorithm/ranges_fill.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_fill.h'}} +#include <__algorithm/ranges_fill_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_fill_n.h'}} #include <__algorithm/ranges_find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find.h'}} #include <__algorithm/ranges_find_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_if.h'}} #include <__algorithm/ranges_find_if_not.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_if_not.h'}} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill.pass.cpp @@ -0,0 +1,96 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template O, sentinel_for S> +// constexpr O ranges::fill(O first, S last, const T& value); +// template R> +// constexpr borrowed_iterator_t ranges::fill(R&& r, const T& value); + +#include +#include +#include +#include + +#include "test_iterators.h" + +template +constexpr void test_iterators() { + { // simple test + { + int a[3]; + std::same_as auto ret = std::ranges::fill(It(a), Sent(It(a + 3)), 1); + assert(std::all_of(a, a + 3, [](int i) { return i == 1; })); + assert(base(ret) == a + 3); + } + { + int a[3]; + auto range = std::ranges::subrange(It(a), Sent(It(a + 3))); + std::same_as auto ret = std::ranges::fill(range, 1); + assert(std::all_of(a, a + 3, [](int i) { return i == 1; })); + assert(base(ret) == a + 3); + } + } + + { // check that an empty range works + { + std::array a; + auto ret = std::ranges::fill(It(a.data()), Sent(It(a.data())), 1); + assert(base(ret) == a.data()); + } + { + std::array a; + auto range = std::ranges::subrange(It(a.data()), Sent(It(a.data()))); + auto ret = std::ranges::fill(range, 1); + assert(base(ret) == a.data()); + } + } +} + +constexpr bool test() { + test_iterators, sentinel_wrapper>>(); + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators(); + + { // check that every element is copied once + struct S { + bool copied = false; + constexpr S& operator=(const S&) { + copied = true; + return *this; + } + }; + { + S a[5]; + std::ranges::fill(a, a + 5, S {true}); + assert(std::all_of(a, a + 5, [](S& s) { return s.copied; })); + } + { + S a[5]; + std::ranges::fill(a, S {true}); + assert(std::all_of(a, a + 5, [](S& s) { return s.copied; })); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill_n.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill_n.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill_n.pass.cpp @@ -0,0 +1,71 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template O> +// constexpr O ranges::fill_n(O first, iter_difference_t n, const T& value); + +#include +#include +#include +#include + +#include "test_iterators.h" + +template +constexpr void test_iterators() { + { // simple test + int a[3]; + std::same_as auto ret = std::ranges::fill_n(It(a), 3, 1); + assert(std::all_of(a, a + 3, [](int i) { return i == 1; })); + assert(base(ret) == a + 3); + } + + { // check that an empty range works + std::array a; + auto ret = std::ranges::fill_n(It(a.data()), 0, 1); + assert(base(ret) == a.data()); + } +} + +constexpr bool test() { + test_iterators, sentinel_wrapper>>(); + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators(); + + { // check that every element is copied once + struct S { + bool copied = false; + constexpr S& operator=(const S&) { + copied = true; + return *this; + } + }; + + S a[5]; + std::ranges::fill_n(a, 5, S {true}); + assert(std::all_of(a, a + 5, [](S& s) { return s.copied; })); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +}