258 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9// <algorithm>10 11// template<class Iter, IntegralLike Size, class T>12// requires OutputIterator<Iter, const T&>13// constexpr OutputIterator // constexpr after C++1714// fill_n(Iter first, Size n, const T& value);15 16#include <algorithm>17#include <array>18#include <cassert>19#include <cstddef>20#include <deque>21#include <ranges>22#include <vector>23 24#include "sized_allocator.h"25#include "test_macros.h"26#include "test_iterators.h"27#include "type_algorithms.h"28#include "user_defined_integral.h"29 30typedef UserDefinedIntegral<unsigned> UDI;31 32template <class Iter, class Container>33TEST_CONSTEXPR_CXX20 void34test(Container in, size_t from, size_t n, typename Container::value_type value, Container expected) {35 Iter it = std::fill_n(Iter(in.data() + from), UDI(n), value);36 assert(base(it) == in.data() + from + n);37 assert(in == expected);38}39 40template <class T>41struct Test {42 template <class Iter>43 TEST_CONSTEXPR_CXX20 void operator()() {44 {45 std::array<T, 4> in = {1, 2, 3, 4};46 std::array<T, 4> expected = {5, 5, 5, 5};47 test<Iter>(in, 0, 4, 5, expected);48 }49 {50 std::array<T, 4> in = {1, 2, 3, 4};51 std::array<T, 4> expected = {1, 5, 5, 4};52 test<Iter>(in, 1, 2, 5, expected);53 }54 }55};56 57struct source {58 TEST_CONSTEXPR source() = default;59 TEST_CONSTEXPR_CXX20 operator int() const { return 1; }60};61 62class CharWrapper {63 char a_;64 65public:66 TEST_CONSTEXPR CharWrapper() : a_('a') {};67 TEST_CONSTEXPR explicit CharWrapper(char a) : a_(a) {}68 TEST_CONSTEXPR operator unsigned char() const { return 'b'; }69 70 TEST_CONSTEXPR friend bool operator==(const CharWrapper& x, const CharWrapper& y) { return x.a_ == y.a_; }71};72 73struct CharTransformer {74 TEST_CONSTEXPR CharTransformer() : c(0) {}75 TEST_CONSTEXPR CharTransformer(char xc) : c(xc + 1) {}76 char c;77};78 79struct CharUnionStorage {80 union {81 unsigned char a;82 unsigned char b;83 };84};85 86TEST_CONSTEXPR_CXX20 bool test_vector_bool(std::size_t N) {87 { // Test cases validating leading/trailing bits unfilled remain unchanged88 { // Leading bits are not filled89 std::vector<bool> in(N, false);90 std::vector<bool> expected(N, true);91 expected[0] = expected[1] = false;92 std::fill_n(in.begin() + 2, N - 2, true);93 assert(in == expected);94 }95 { // Trailing bits are not filled96 std::vector<bool> in(N, false);97 std::vector<bool> expected(N, true);98 expected[N - 1] = expected[N - 2] = false;99 std::fill_n(in.begin(), N - 2, true);100 assert(in == expected);101 }102 { // Leading and trailing bits are not filled103 std::vector<bool> in(N, false);104 std::vector<bool> expected(N, true);105 expected[0] = expected[1] = expected[N - 1] = expected[N - 2] = false;106 std::fill_n(in.begin() + 2, N - 4, true);107 assert(in == expected);108 }109 }110 111 { // Test cases with full or partial bytes filled112 { // Full bytes filled113 std::vector<bool> in(N, false);114 std::vector<bool> expected(N, true);115 std::fill_n(in.begin(), N, true);116 assert(in == expected);117 }118 { // Partial bytes with offset filled119 std::vector<bool> in(N, false);120 std::vector<bool> expected(N, true);121 std::fill_n(in.begin() + 4, N - 8, true);122 std::fill_n(expected.begin(), 4, false);123 std::fill_n(expected.end() - 4, 4, false);124 assert(in == expected);125 }126 }127 128 return true;129}130 131/*TEST_CONSTEXPR_CXX26*/ void test_deque() { // TODO: Mark as TEST_CONSTEXPR_CXX26 once std::deque is constexpr132 std::deque<int> in(20);133 std::deque<int> expected(in.size(), 42);134 std::fill_n(in.begin(), in.size(), 42);135 assert(in == expected);136}137 138TEST_CONSTEXPR_CXX20 bool test() {139 types::for_each(types::forward_iterator_list<char*>(), Test<char>());140 types::for_each(types::forward_iterator_list<int*>(), Test<int>());141 142 { // Test with int arrays143 {144 int a[4] = {};145 assert(std::fill_n(a, UDI(4), static_cast<char>(1)) == a + 4);146 assert(a[0] == 1 && a[1] == 1 && a[2] == 1 && a[3] == 1);147 }148#if TEST_STD_VER >= 11149 {150 const std::size_t N = 5;151 int ib[] = {0, 0, 0, 0, 0, 0}; // one bigger than N152 153 auto it = std::fill_n(std::begin(ib), N, 5);154 assert(it == (std::begin(ib) + N) && std::all_of(std::begin(ib), it, [](int a) { return a == 5; }) &&155 *it == 0 // don't overwrite the last value in the output array156 );157 }158#endif159 }160 161 { // Test with struct arrays162 {163 CharWrapper a[3];164 assert(std::fill_n(&a[0], UDI(3), CharWrapper('a')) == a + 3);165 assert(a[0] == CharWrapper('a'));166 assert(a[1] == CharWrapper('a'));167 assert(a[2] == CharWrapper('a'));168 }169 {170 CharTransformer b[4] = {};171 assert(std::fill_n(b, UDI(4), static_cast<char>(10)) == b + 4);172 assert(b[0].c == 11);173 assert(b[1].c == 11);174 assert(b[2].c == 11);175 assert(b[3].c == 11);176 }177 {178 CharUnionStorage foo[5];179 std::fill_n(&foo[0], UDI(5), CharUnionStorage());180 }181 }182 183 { // Test with an int array and struct source184 int a[4] = {};185 assert(std::fill_n(a, UDI(4), source()) == a + 4);186 assert(a[0] == 1);187 assert(a[1] == 1);188 assert(a[2] == 1);189 assert(a[3] == 1);190 }191 192 { // Test vector<bool>::iterator optimization193 assert(test_vector_bool(8));194 assert(test_vector_bool(19));195 assert(test_vector_bool(32));196 assert(test_vector_bool(49));197 assert(test_vector_bool(64));198 assert(test_vector_bool(199));199 assert(test_vector_bool(256));200 201 // Make sure std::fill_n behaves properly with std::vector<bool> iterators with custom size types.202 // See https://github.com/llvm/llvm-project/pull/122410.203 {204 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;205 std::vector<bool, Alloc> in(100, false, Alloc(1));206 std::vector<bool, Alloc> expected(100, true, Alloc(1));207 std::fill_n(in.begin(), in.size(), true);208 assert(in == expected);209 }210 {211 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;212 std::vector<bool, Alloc> in(200, false, Alloc(1));213 std::vector<bool, Alloc> expected(200, true, Alloc(1));214 std::fill_n(in.begin(), in.size(), true);215 assert(in == expected);216 }217 {218 using Alloc = sized_allocator<bool, std::uint32_t, std::int32_t>;219 std::vector<bool, Alloc> in(200, false, Alloc(1));220 std::vector<bool, Alloc> expected(200, true, Alloc(1));221 std::fill_n(in.begin(), in.size(), true);222 assert(in == expected);223 }224 {225 using Alloc = sized_allocator<bool, std::uint64_t, std::int64_t>;226 std::vector<bool, Alloc> in(200, false, Alloc(1));227 std::vector<bool, Alloc> expected(200, true, Alloc(1));228 std::fill_n(in.begin(), in.size(), true);229 assert(in == expected);230 }231 }232 233 if (!TEST_IS_CONSTANT_EVALUATED) // TODO: Use TEST_STD_AT_LEAST_26_OR_RUNTIME_EVALUATED when std::deque is made constexpr234 test_deque();235 236#if TEST_STD_VER >= 20237 {238 std::vector<std::vector<int>> v{{1, 2}, {1, 2, 3}, {}, {3, 4, 5}, {6}, {7, 8, 9, 6}, {0, 1, 2, 3, 0, 1, 2}};239 auto jv = std::ranges::join_view(v);240 std::fill_n(jv.begin(), std::distance(jv.begin(), jv.end()), 42);241 for (const auto& vec : v)242 for (auto n : vec)243 assert(n == 42);244 }245#endif246 247 return true;248}249 250int main(int, char**) {251 test();252#if TEST_STD_VER >= 20253 static_assert(test());254#endif255 256 return 0;257}258