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 // ADDITIONAL_COMPILE_FLAGS(gcc): -Wno-bool-compare
10 // ADDITIONAL_COMPILE_FLAGS(gcc-style-warnings): -Wno-sign-compare
11 // MSVC warning C4245: conversion from 'int' to 'wchar_t', signed/unsigned mismatch
12 // MSVC warning C4305: truncation from 'int' to 'bool'
13 // MSVC warning C4310: cast truncates constant value
14 // MSVC warning C4389: '==': signed/unsigned mismatch
15 // MSVC warning C4805: '==': unsafe mix of type 'char' and type 'bool' in operation
16 // ADDITIONAL_COMPILE_FLAGS(cl-style-warnings): /wd4245 /wd4305 /wd4310 /wd4389 /wd4805
17
18 // <algorithm>
19
20 // template<InputIterator Iter, class T>
21 // requires HasEqualTo<Iter::value_type, T>
22 // constexpr Iter // constexpr after C++17
23 // find(Iter first, Iter last, const T& value);
24
25 #include <algorithm>
26 #include <cassert>
27 #include <deque>
28 #include <vector>
29 #include <type_traits>
30
31 #include "test_macros.h"
32 #include "test_iterators.h"
33 #include "type_algorithms.h"
34
35 static std::vector<int> comparable_data;
36
37 template <class ArrayT, class CompareT>
38 struct Test {
39 template <class Iter>
operator ()Test40 TEST_CONSTEXPR_CXX20 void operator()() {
41 ArrayT arr[] = {
42 ArrayT(1), ArrayT(2), ArrayT(3), ArrayT(4), ArrayT(5), ArrayT(6), ArrayT(7), ArrayT(8), ArrayT(9), ArrayT(10)};
43
44 static_assert(std::is_same<decltype(std::find(Iter(arr), Iter(arr), 0)), Iter>::value, "");
45
46 { // first element matches
47 Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(1));
48 assert(*iter == ArrayT(1));
49 assert(base(iter) == arr);
50 }
51
52 { // range is empty; return last
53 Iter iter = std::find(Iter(arr), Iter(arr), CompareT(1));
54 assert(base(iter) == arr);
55 }
56
57 { // if multiple elements match, return the first match
58 ArrayT data[] = {
59 ArrayT(1), ArrayT(2), ArrayT(3), ArrayT(4), ArrayT(5), ArrayT(6), ArrayT(7), ArrayT(5), ArrayT(4)};
60 Iter iter = std::find(Iter(std::begin(data)), Iter(std::end(data)), CompareT(5));
61 assert(*iter == ArrayT(5));
62 assert(base(iter) == data + 4);
63 }
64
65 { // some element matches
66 Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(6));
67 assert(*iter == ArrayT(6));
68 assert(base(iter) == arr + 5);
69 }
70
71 { // last element matches
72 Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(10));
73 assert(*iter == ArrayT(10));
74 assert(base(iter) == arr + 9);
75 }
76
77 { // if no element matches, last is returned
78 Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(20));
79 assert(base(iter) == arr + 10);
80 }
81
82 if (!TEST_IS_CONSTANT_EVALUATED)
83 comparable_data.clear();
84 }
85 };
86
87 template <class IndexT>
88 class Comparable {
89 IndexT index_;
90
init_index(IndexT i)91 static IndexT init_index(IndexT i) {
92 IndexT size = static_cast<IndexT>(comparable_data.size());
93 comparable_data.push_back(i);
94 return size;
95 }
96
97 public:
Comparable(IndexT i)98 Comparable(IndexT i) : index_(init_index(i)) {}
99
operator ==(const Comparable & lhs,const Comparable & rhs)100 friend bool operator==(const Comparable& lhs, const Comparable& rhs) {
101 return comparable_data[lhs.index_] == comparable_data[rhs.index_];
102 }
103 };
104
105 #if TEST_STD_VER >= 20
106 template <class ElementT>
107 class TriviallyComparable {
108 ElementT el_;
109
110 public:
TriviallyComparable(ElementT el)111 explicit constexpr TriviallyComparable(ElementT el) : el_(el) {}
112 bool operator==(const TriviallyComparable&) const = default;
113 };
114 #endif
115
116 template <class CompareT>
117 struct TestTypes {
118 template <class T>
operator ()TestTypes119 TEST_CONSTEXPR_CXX20 void operator()() {
120 types::for_each(types::cpp17_input_iterator_list<T*>(), Test<T, CompareT>());
121 }
122 };
123
test_deque()124 void test_deque() {
125 { // empty deque
126 std::deque<int> data;
127 assert(std::find(data.begin(), data.end(), 4) == data.end());
128 }
129
130 { // single element - match
131 std::deque<int> data;
132 data.push_back(4);
133 assert(std::find(data.begin(), data.end(), 4) == data.begin());
134 }
135
136 { // single element - no match
137 std::deque<int> data;
138 data.push_back(3);
139 assert(std::find(data.begin(), data.end(), 4) == data.end());
140 }
141
142 // many elements
143 int sizes[] = {2, 3, 1023, 1024, 1025, 2047, 2048, 2049};
144 for (auto size : sizes) {
145 { // last element match
146 std::deque<int> data;
147 data.resize(size);
148 std::fill(data.begin(), data.end(), 3);
149 data[size - 1] = 4;
150 assert(std::find(data.begin(), data.end(), 4) == data.end() - 1);
151 }
152
153 { // second-last element match
154 std::deque<int> data;
155 data.resize(size);
156 std::fill(data.begin(), data.end(), 3);
157 data[size - 2] = 4;
158 assert(std::find(data.begin(), data.end(), 4) == data.end() - 2);
159 }
160
161 { // no match
162 std::deque<int> data;
163 data.resize(size);
164 std::fill(data.begin(), data.end(), 3);
165 assert(std::find(data.begin(), data.end(), 4) == data.end());
166 }
167 }
168 }
169
170 template <class T>
171 struct TestIntegerPromotions1 {
172 template <class U>
testTestIntegerPromotions1173 TEST_CONSTEXPR_CXX20 void test(T val, U to_find) {
174 bool expect_match = val == to_find;
175 assert(std::find(&val, &val + 1, to_find) == (expect_match ? &val : &val + 1));
176 }
177
178 template <class U>
operator ()TestIntegerPromotions1179 TEST_CONSTEXPR_CXX20 void operator()() {
180 test<U>(0, 0);
181 test<U>(0, 1);
182 test<U>(1, 1);
183 test<U>(0, -1);
184 test<U>(-1, -1);
185 test<U>(0, U(-127));
186 test<U>(T(-127), U(-127));
187 test<U>(T(-128), U(-128));
188 test<U>(T(-129), U(-129));
189 test<U>(T(255), U(255));
190 test<U>(T(256), U(256));
191 test<U>(T(257), U(257));
192 test<U>(0, std::numeric_limits<U>::min());
193 test<U>(T(std::numeric_limits<U>::min()), std::numeric_limits<U>::min());
194 test<U>(0, std::numeric_limits<U>::min() + 1);
195 test<U>(T(std::numeric_limits<U>::min() + 1), std::numeric_limits<U>::min() + 1);
196 test<U>(0, std::numeric_limits<U>::max());
197 test<U>(T(std::numeric_limits<U>::max()), std::numeric_limits<U>::max());
198 test<U>(T(std::numeric_limits<U>::max() - 1), std::numeric_limits<U>::max() - 1);
199 }
200 };
201
202 struct TestIntegerPromotions {
203 template <class T>
operator ()TestIntegerPromotions204 TEST_CONSTEXPR_CXX20 void operator()() {
205 types::for_each(types::integral_types(), TestIntegerPromotions1<T>());
206 }
207 };
208
test()209 TEST_CONSTEXPR_CXX20 bool test() {
210 types::for_each(types::integer_types(), TestTypes<char>());
211 types::for_each(types::integer_types(), TestTypes<int>());
212 types::for_each(types::integer_types(), TestTypes<long long>());
213 #if TEST_STD_VER >= 20
214 Test<TriviallyComparable<char>, TriviallyComparable<char>>().operator()<TriviallyComparable<char>*>();
215 Test<TriviallyComparable<wchar_t>, TriviallyComparable<wchar_t>>().operator()<TriviallyComparable<wchar_t>*>();
216 #endif
217
218 // TODO: Remove the `_LIBCPP_ENABLE_EXPERIMENTAL` check once we have the FTM guarded or views::join isn't
219 // experimental anymore
220 #if TEST_STD_VER >= 20 && (!defined(_LIBCPP_VERSION) || defined(_LIBCPP_ENABLE_EXPERIMENTAL))
221 {
222 std::vector<std::vector<int>> vec = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
223 auto view = vec | std::views::join;
224 assert(std::find(view.begin(), view.end(), 4) == std::next(view.begin(), 3));
225 }
226 #endif
227
228 types::for_each(types::integral_types(), TestIntegerPromotions());
229
230 return true;
231 }
232
main(int,char **)233 int main(int, char**) {
234 test_deque();
235 test();
236 #if TEST_STD_VER >= 20
237 static_assert(test());
238 #endif
239
240 Test<Comparable<char>, Comparable<char> >().operator()<Comparable<char>*>();
241 Test<Comparable<wchar_t>, Comparable<wchar_t> >().operator()<Comparable<wchar_t>*>();
242
243 return 0;
244 }
245