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// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=20000000
14// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-ops-limit): -fconstexpr-ops-limit=80000000
15
16// template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity>
17// requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
18// constexpr iter_difference_t<I>
19// ranges::count(I first, S last, const T& value, Proj proj = {});
20// template<input_range R, class T, class Proj = identity>
21// requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
22// constexpr range_difference_t<R>
23// ranges::count(R&& r, const T& value, Proj proj = {});
24
25#include <algorithm>
26#include <array>
27#include <cassert>
28#include <cstddef>
29#include <ranges>
30#include <vector>
31
32#include "sized_allocator.h"
33#include "almost_satisfies_types.h"
34#include "test_iterators.h"
35
36struct NotEqualityComparable {
37 bool operator==(NotEqualityComparable&&) const;
38 bool operator==(NotEqualityComparable&) const;
39 bool operator==(const NotEqualityComparable&&) const;
40};
41
42template <class It, class Sent = It>
43concept HasCountIt = requires(It it, Sent sent) { std::ranges::count(it, sent, *it); };
44static_assert(HasCountIt<int*>);
45static_assert(!HasCountIt<NotEqualityComparable*>);
46static_assert(!HasCountIt<InputIteratorNotDerivedFrom>);
47static_assert(!HasCountIt<InputIteratorNotIndirectlyReadable>);
48static_assert(!HasCountIt<InputIteratorNotInputOrOutputIterator>);
49static_assert(!HasCountIt<cpp20_input_iterator<int*>, SentinelForNotSemiregular>);
50static_assert(!HasCountIt<cpp20_input_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>);
51
52static_assert(!HasCountIt<int*, int>);
53static_assert(!HasCountIt<int, int*>);
54
55template <class Range, class ValT>
56concept HasCountR = requires(Range r) { std::ranges::count(r, ValT{}); };
57static_assert(HasCountR<std::array<int, 1>, int>);
58static_assert(!HasCountR<int, int>);
59static_assert(!HasCountR<std::array<NotEqualityComparable, 1>, NotEqualityComparable>);
60static_assert(!HasCountR<InputRangeNotDerivedFrom, int>);
61static_assert(!HasCountR<InputRangeNotIndirectlyReadable, int>);
62static_assert(!HasCountR<InputRangeNotInputOrOutputIterator, int>);
63static_assert(!HasCountR<InputRangeNotSentinelSemiregular, int>);
64static_assert(!HasCountR<InputRangeNotSentinelEqualityComparableWith, int>);
65
66template <class It, class Sent = It>
67constexpr void test_iterators() {
68 {
69 // simple test
70 {
71 int a[] = {1, 2, 3, 4};
72 std::same_as<std::ptrdiff_t> auto ret = std::ranges::count(It(a), Sent(It(a + 4)), 3);
73 assert(ret == 1);
74 }
75 {
76 int a[] = {1, 2, 3, 4};
77 auto range = std::ranges::subrange(It(a), Sent(It(a + 4)));
78 std::same_as<std::ptrdiff_t> auto ret = std::ranges::count(range, 3);
79 assert(ret == 1);
80 }
81 }
82
83 {
84 // check that an empty range works
85 {
86 std::array<int, 0> a = {};
87 auto ret = std::ranges::count(It(a.data()), Sent(It(a.data() + a.size())), 1);
88 assert(ret == 0);
89 }
90 {
91 std::array<int, 0> a = {};
92 auto range = std::ranges::subrange(It(a.data()), Sent(It(a.data() + a.size())));
93 auto ret = std::ranges::count(range, 1);
94 assert(ret == 0);
95 }
96 }
97
98 {
99 // check that a range with a single element works
100 {
101 std::array a = {2};
102 auto ret = std::ranges::count(It(a.data()), Sent(It(a.data() + a.size())), 2);
103 assert(ret == 1);
104 }
105 {
106 std::array a = {2};
107 auto range = std::ranges::subrange(It(a.data()), Sent(It(a.data() + a.size())));
108 auto ret = std::ranges::count(range, 2);
109 assert(ret == 1);
110 }
111 }
112
113 {
114 // check that 0 is returned with no match
115 {
116 std::array a = {1, 1, 1};
117 auto ret = std::ranges::count(It(a.data()), Sent(It(a.data() + a.size())), 0);
118 assert(ret == 0);
119 }
120 {
121 std::array a = {1, 1, 1};
122 auto range = std::ranges::subrange(It(a.data()), Sent(It(a.data() + a.size())));
123 auto ret = std::ranges::count(range, 0);
124 assert(ret == 0);
125 }
126 }
127
128 {
129 // check that more than one element is counted
130 {
131 std::array a = {3, 3, 4, 3, 3};
132 auto ret = std::ranges::count(It(a.data()), Sent(It(a.data() + a.size())), 3);
133 assert(ret == 4);
134 }
135 {
136 std::array a = {3, 3, 4, 3, 3};
137 auto range = std::ranges::subrange(It(a.data()), Sent(It(a.data() + a.size())));
138 auto ret = std::ranges::count(range, 3);
139 assert(ret == 4);
140 }
141 }
142
143 {
144 // check that all elements are counted
145 {
146 std::array a = {5, 5, 5, 5};
147 auto ret = std::ranges::count(It(a.data()), Sent(It(a.data() + a.size())), 5);
148 assert(ret == 4);
149 }
150 {
151 std::array a = {5, 5, 5, 5};
152 auto range = std::ranges::subrange(It(a.data()), Sent(It(a.data() + a.size())));
153 auto ret = std::ranges::count(range, 5);
154 assert(ret == 4);
155 }
156 }
157}
158
159constexpr bool test() {
160 test_iterators<int*>();
161 test_iterators<const int*>();
162 test_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
163 test_iterators<bidirectional_iterator<int*>>();
164 test_iterators<forward_iterator<int*>>();
165 test_iterators<random_access_iterator<int*>>();
166 test_iterators<contiguous_iterator<int*>>();
167
168 {
169 // check that projections are used properly and that they are called with the iterator directly
170 {
171 int a[] = {1, 2, 3, 4};
172 auto ret = std::ranges::count(a, a + 4, a + 3, [](int& i) { return &i; });
173 assert(ret == 1);
174 }
175 {
176 int a[] = {1, 2, 3, 4};
177 auto ret = std::ranges::count(a, a + 3, [](int& i) { return &i; });
178 assert(ret == 1);
179 }
180 }
181
182 {
183 // check that std::invoke is used
184 struct S {
185 int i;
186 };
187 S a[] = {S{.i: 1}, S{.i: 3}, S{.i: 2}};
188 std::same_as<std::ptrdiff_t> auto ret = std::ranges::count(a, 4, &S::i);
189 assert(ret == 0);
190 }
191
192 {
193 // count invocations of the projection
194 {
195 int a[] = {1, 2, 3, 4};
196 int projection_count = 0;
197 auto ret = std::ranges::count(a, a + 4, 2, [&](int i) {
198 ++projection_count;
199 return i;
200 });
201 assert(ret == 1);
202 assert(projection_count == 4);
203 }
204 {
205 int a[] = {1, 2, 3, 4};
206 int projection_count = 0;
207 auto ret = std::ranges::count(a, 2, [&](int i) {
208 ++projection_count;
209 return i;
210 });
211 assert(ret == 1);
212 assert(projection_count == 4);
213 }
214 }
215
216 {
217 // check that an immobile type works
218 struct NonMovable {
219 NonMovable(const NonMovable&) = delete;
220 NonMovable(NonMovable&&) = delete;
221 constexpr NonMovable(int i_) : i(i_) {}
222 int i;
223
224 bool operator==(const NonMovable&) const = default;
225 };
226 {
227 NonMovable a[] = {9, 8, 4, 3};
228 auto ret = std::ranges::count(a, a + 4, NonMovable(8));
229 assert(ret == 1);
230 }
231 {
232 NonMovable a[] = {9, 8, 4, 3};
233 auto ret = std::ranges::count(a, NonMovable(8));
234 assert(ret == 1);
235 }
236 }
237
238 {
239 // check that difference_type is used
240 struct DiffTypeIterator {
241 using difference_type = signed char;
242 using value_type = int;
243
244 int* it = nullptr;
245
246 constexpr DiffTypeIterator() = default;
247 constexpr DiffTypeIterator(int* i) : it(i) {}
248
249 constexpr int& operator*() const { return *it; }
250 constexpr DiffTypeIterator& operator++() {
251 ++it;
252 return *this;
253 }
254 constexpr void operator++(int) { ++it; }
255
256 bool operator==(const DiffTypeIterator&) const = default;
257 };
258
259 {
260 int a[] = {5, 5, 4, 3, 2, 1};
261 std::same_as<signed char> decltype(auto) ret =
262 std::ranges::count(DiffTypeIterator(a), DiffTypeIterator(a + 6), 4);
263 assert(ret == 1);
264 }
265 {
266 int a[] = {5, 5, 4, 3, 2, 1};
267 auto range = std::ranges::subrange(DiffTypeIterator(a), DiffTypeIterator(a + 6));
268 std::same_as<signed char> decltype(auto) ret = std::ranges::count(range, 4);
269 assert(ret == 1);
270 }
271 }
272
273 // Tests for std::count with std::vector<bool>::iterator optimizations.
274 {
275 { // check that vector<bool>::iterator optimization works as expected
276 std::vector<bool> vec(256 + 64);
277 for (ptrdiff_t i = 0; i != 256; ++i) {
278 for (size_t offset = 0; offset != 64; ++offset) {
279 std::fill(first: vec.begin(), last: vec.end(), value: false);
280 std::fill(first: vec.begin() + offset, last: vec.begin() + i + offset, value: true);
281 assert(std::ranges::count(vec.begin() + offset, vec.begin() + offset + 256, true) == i);
282 assert(std::ranges::count(vec.begin() + offset, vec.begin() + offset + 256, false) == 256 - i);
283 }
284 }
285 }
286
287 // Fix std::ranges::count for std::vector<bool> with small storage types, e.g., std::uint16_t, unsigned short.
288 // See https://github.com/llvm/llvm-project/issues/122528
289 {
290 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
291 std::vector<bool, Alloc> in(100, true, Alloc(1));
292 assert(std::ranges::count(in, true) == 100);
293 }
294 {
295 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
296 std::vector<bool, Alloc> in(199, true, Alloc(1));
297 assert(std::ranges::count(in, true) == 199);
298 }
299 {
300 using Alloc = sized_allocator<bool, unsigned short, short>;
301 std::vector<bool, Alloc> in(200, true, Alloc(1));
302 assert(std::ranges::count(in, true) == 200);
303 }
304 {
305 using Alloc = sized_allocator<bool, std::uint32_t, std::int32_t>;
306 std::vector<bool, Alloc> in(205, true, Alloc(1));
307 assert(std::ranges::count(in, true) == 205);
308 }
309 {
310 using Alloc = sized_allocator<bool, std::uint64_t, std::int64_t>;
311 std::vector<bool, Alloc> in(257, true, Alloc(1));
312 assert(std::ranges::count(in, true) == 257);
313 }
314 }
315
316 return true;
317}
318
319int main(int, char**) {
320 test();
321 static_assert(test());
322
323 return 0;
324}
325

source code of libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count.pass.cpp