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