1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9// <algorithm>
10
11// UNSUPPORTED: c++03, c++11, c++14, c++17
12
13// template<class T, output_iterator<const T&> O>
14// constexpr O ranges::fill_n(O first, iter_difference_t<O> n, const T& value);
15
16#include <algorithm>
17#include <array>
18#include <cassert>
19#include <ranges>
20#include <string>
21#include <vector>
22
23#include "sized_allocator.h"
24#include "almost_satisfies_types.h"
25#include "test_iterators.h"
26#include "test_macros.h"
27
28template <class Iter>
29concept HasFillN = requires(Iter iter) { std::ranges::fill_n(iter, int{}, int{}); };
30
31struct WrongType {};
32
33static_assert(HasFillN<int*>);
34static_assert(!HasFillN<WrongType*>);
35static_assert(!HasFillN<OutputIteratorNotIndirectlyWritable>);
36static_assert(!HasFillN<OutputIteratorNotInputOrOutputIterator>);
37
38template <class It, class Sent = It>
39constexpr void test_iterators() {
40 { // simple test
41 int a[3];
42 std::same_as<It> decltype(auto) ret = std::ranges::fill_n(It(a), 3, 1);
43 assert(std::all_of(a, a + 3, [](int i) { return i == 1; }));
44 assert(base(ret) == a + 3);
45 }
46
47 { // check that an empty range works
48 std::array<int, 0> a;
49 auto ret = std::ranges::fill_n(It(a.data()), 0, 1);
50 assert(base(ret) == a.data());
51 }
52}
53
54// The `ranges::{fill, fill_n}` algorithms require `vector<bool, Alloc>::iterator` to satisfy
55// the `std::indirectly_writable` concept when used with `vector<bool, Alloc>`, which is only
56// satisfied since C++23.
57#if TEST_STD_VER >= 23
58constexpr bool test_vector_bool(std::size_t N) {
59 { // Test cases validating leading/trailing bits unfilled remain unchanged
60 { // Leading bits are not filled
61 std::vector<bool> in(N, false);
62 std::vector<bool> expected(N, true);
63 expected[0] = expected[1] = false;
64 std::ranges::fill_n(std::ranges::begin(in) + 2, N - 2, true);
65 assert(in == expected);
66 }
67 { // Trailing bits are not filled
68 std::vector<bool> in(N, false);
69 std::vector<bool> expected(N, true);
70 expected[N - 1] = expected[N - 2] = false;
71 std::ranges::fill_n(std::ranges::begin(in), N - 2, true);
72 assert(in == expected);
73 }
74 { // Leading and trailing bits are not filled
75 std::vector<bool> in(N, false);
76 std::vector<bool> expected(N, true);
77 expected[0] = expected[1] = expected[N - 1] = expected[N - 2] = false;
78 std::ranges::fill_n(std::ranges::begin(in) + 2, N - 4, true);
79 assert(in == expected);
80 }
81 }
82
83 { // Test cases with full or partial bytes filled
84 { // Full bytes filled
85 std::vector<bool> in(N, false);
86 std::vector<bool> expected(N, true);
87 std::ranges::fill_n(std::ranges::begin(in), N, true);
88 assert(in == expected);
89 }
90 { // Partial bytes with offset filled
91 std::vector<bool> in(N, false);
92 std::vector<bool> expected(N, true);
93 std::ranges::fill_n(std::ranges::begin(in) + 4, N - 8, true);
94 std::ranges::fill_n(std::ranges::begin(expected), 4, false);
95 std::ranges::fill_n(std::ranges::end(expected) - 4, 4, false);
96 assert(in == expected);
97 }
98 }
99
100 return true;
101}
102#endif
103
104constexpr bool test() {
105 test_iterators<cpp17_output_iterator<int*>, sentinel_wrapper<cpp17_output_iterator<int*>>>();
106 test_iterators<cpp20_output_iterator<int*>, sentinel_wrapper<cpp20_output_iterator<int*>>>();
107 test_iterators<forward_iterator<int*>>();
108 test_iterators<bidirectional_iterator<int*>>();
109 test_iterators<random_access_iterator<int*>>();
110 test_iterators<contiguous_iterator<int*>>();
111 test_iterators<int*>();
112
113 { // check that every element is copied once
114 struct S {
115 bool copied = false;
116 constexpr S& operator=(const S&) {
117 assert(!copied);
118 copied = true;
119 return *this;
120 }
121 };
122
123 S a[5];
124 std::ranges::fill_n(a, 5, S{});
125 assert(std::all_of(a, a + 5, [](S& s) { return s.copied; }));
126 }
127
128 { // check that non-trivially copyable items are copied properly
129 std::array<std::string, 10> a;
130 auto ret = std::ranges::fill_n(a.data(), 10, "long long string so no SSO");
131 assert(ret == a.data() + a.size());
132 assert(std::all_of(a.begin(), a.end(), [](auto& s) { return s == "long long string so no SSO"; }));
133 }
134
135#if TEST_STD_VER >= 23
136 { // Test vector<bool>::iterator optimization
137 assert(test_vector_bool(8));
138 assert(test_vector_bool(19));
139 assert(test_vector_bool(32));
140 assert(test_vector_bool(49));
141 assert(test_vector_bool(64));
142 assert(test_vector_bool(199));
143 assert(test_vector_bool(256));
144
145 // Make sure std::ranges::fill_n behaves properly with std::vector<bool> iterators with custom
146 // size types. See https://github.com/llvm/llvm-project/pull/122410.
147 {
148 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
149 std::vector<bool, Alloc> in(100, false, Alloc(1));
150 std::vector<bool, Alloc> expected(100, true, Alloc(1));
151 std::ranges::fill_n(std::ranges::begin(in), in.size(), true);
152 assert(in == expected);
153 }
154 {
155 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
156 std::vector<bool, Alloc> in(200, false, Alloc(1));
157 std::vector<bool, Alloc> expected(200, true, Alloc(1));
158 std::ranges::fill_n(std::ranges::begin(in), in.size(), true);
159 assert(in == expected);
160 }
161 {
162 using Alloc = sized_allocator<bool, std::uint32_t, std::int32_t>;
163 std::vector<bool, Alloc> in(200, false, Alloc(1));
164 std::vector<bool, Alloc> expected(200, true, Alloc(1));
165 std::ranges::fill_n(std::ranges::begin(in), in.size(), true);
166 assert(in == expected);
167 }
168 {
169 using Alloc = sized_allocator<bool, std::uint64_t, std::int64_t>;
170 std::vector<bool, Alloc> in(200, false, Alloc(1));
171 std::vector<bool, Alloc> expected(200, true, Alloc(1));
172 std::ranges::fill_n(std::ranges::begin(in), in.size(), true);
173 assert(in == expected);
174 }
175 }
176#endif
177
178 return true;
179}
180
181int main(int, char**) {
182 test();
183 static_assert(test());
184
185 return 0;
186}
187

source code of libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill_n.pass.cpp