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