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// template<InputIterator Iter1, InputIterator Iter2>
12// requires HasEqualTo<Iter1::value_type, Iter2::value_type>
13// constexpr bool // constexpr after c++17
14// equal(Iter1 first1, Iter1 last1, Iter2 first2);
15//
16// Introduced in C++14:
17// template<InputIterator Iter1, InputIterator Iter2>
18// constexpr bool // constexpr after c++17
19// equal(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2);
20
21// We test the cartesian product, so we sometimes compare differently signed types
22// ADDITIONAL_COMPILE_FLAGS(gcc-style-warnings): -Wno-sign-compare
23// ADDITIONAL_COMPILE_FLAGS(character-conversion-warnings): -Wno-character-conversion
24
25// MSVC warning C4242: 'argument': conversion from 'int' to 'const _Ty', possible loss of data
26// MSVC warning C4244: 'argument': conversion from 'wchar_t' to 'const _Ty', possible loss of data
27// MSVC warning C4389: '==': signed/unsigned mismatch
28// ADDITIONAL_COMPILE_FLAGS(cl-style-warnings): /wd4242 /wd4244 /wd4389
29// XFAIL: FROZEN-CXX03-HEADERS-FIXME
30
31#include <algorithm>
32#include <cassert>
33#include <functional>
34#include <vector>
35
36#include "sized_allocator.h"
37#include "test_iterators.h"
38#include "test_macros.h"
39#include "type_algorithms.h"
40
41template <class UnderlyingType, class Iter1>
42struct Test {
43 template <class Iter2>
44 TEST_CONSTEXPR_CXX20 void operator()() {
45 UnderlyingType a[] = {0, 1, 2, 3, 4, 5};
46 const unsigned s = sizeof(a) / sizeof(a[0]);
47 UnderlyingType b[s] = {0, 1, 2, 5, 4, 5};
48
49 assert(std::equal(Iter1(a), Iter1(a + s), Iter2(a)));
50 assert(!std::equal(Iter1(a), Iter1(a + s), Iter2(b)));
51
52#if TEST_STD_VER >= 14
53 assert(std::equal(Iter1(a), Iter1(a + s), Iter2(a), std::equal_to<>()));
54 assert(!std::equal(Iter1(a), Iter1(a + s), Iter2(b), std::equal_to<>()));
55
56 assert(std::equal(Iter1(a), Iter1(a + s), Iter2(a), Iter2(a + s)));
57 assert(!std::equal(Iter1(a), Iter1(a + s), Iter2(a), Iter2(a + s - 1)));
58 assert(!std::equal(Iter1(a), Iter1(a + s), Iter2(b), Iter2(b + s)));
59
60 assert(std::equal(Iter1(a), Iter1(a + s), Iter2(a), Iter2(a + s), std::equal_to<>()));
61 assert(!std::equal(Iter1(a), Iter1(a + s), Iter2(a), Iter2(a + s - 1), std::equal_to<>()));
62 assert(!std::equal(Iter1(a), Iter1(a + s), Iter2(b), Iter2(b + s), std::equal_to<>()));
63#endif
64 }
65};
66
67struct TestNarrowingEqualTo {
68 template <class UnderlyingType>
69 TEST_CONSTEXPR_CXX20 void operator()() {
70 TEST_DIAGNOSTIC_PUSH
71 // MSVC warning C4310: cast truncates constant value
72 TEST_MSVC_DIAGNOSTIC_IGNORED(4310)
73
74 UnderlyingType a[] = {
75 UnderlyingType(0x1000),
76 UnderlyingType(0x1001),
77 UnderlyingType(0x1002),
78 UnderlyingType(0x1003),
79 UnderlyingType(0x1004)};
80 UnderlyingType b[] = {
81 UnderlyingType(0x1600),
82 UnderlyingType(0x1601),
83 UnderlyingType(0x1602),
84 UnderlyingType(0x1603),
85 UnderlyingType(0x1604)};
86
87 TEST_DIAGNOSTIC_POP
88
89 assert(std::equal(a, a + 5, b, std::equal_to<char>()));
90#if TEST_STD_VER >= 14
91 assert(std::equal(a, a + 5, b, b + 5, std::equal_to<char>()));
92#endif
93 }
94};
95
96template <class UnderlyingType, class TypeList>
97struct TestIter2 {
98 template <class Iter1>
99 TEST_CONSTEXPR_CXX20 void operator()() {
100 types::for_each(TypeList(), Test<UnderlyingType, Iter1>());
101 }
102};
103
104struct AddressCompare {
105 int i = 0;
106 TEST_CONSTEXPR_CXX20 AddressCompare(int) {}
107
108 operator char() { return static_cast<char>(i); }
109
110 friend TEST_CONSTEXPR_CXX20 bool operator==(const AddressCompare& lhs, const AddressCompare& rhs) {
111 return &lhs == &rhs;
112 }
113
114 friend TEST_CONSTEXPR_CXX20 bool operator!=(const AddressCompare& lhs, const AddressCompare& rhs) {
115 return &lhs != &rhs;
116 }
117};
118
119#if TEST_STD_VER >= 20
120class trivially_equality_comparable {
121public:
122 constexpr trivially_equality_comparable(int i) : i_(i) {}
123 bool operator==(const trivially_equality_comparable&) const = default;
124
125private:
126 int i_;
127};
128
129#endif
130
131template <std::size_t N>
132TEST_CONSTEXPR_CXX20 void test_vector_bool() {
133 std::vector<bool> in(N, false);
134 for (std::size_t i = 0; i < N; i += 2)
135 in[i] = true;
136
137 { // Test equal() with aligned bytes
138 std::vector<bool> out = in;
139 assert(std::equal(in.begin(), in.end(), out.begin()));
140#if TEST_STD_VER >= 14
141 assert(std::equal(in.begin(), in.end(), out.begin(), out.end()));
142#endif
143 }
144
145 { // Test equal() with unaligned bytes
146 std::vector<bool> out(N + 8);
147 std::copy(in.begin(), in.end(), out.begin() + 4);
148 assert(std::equal(in.begin(), in.end(), out.begin() + 4));
149#if TEST_STD_VER >= 14
150 assert(std::equal(in.begin(), in.end(), out.begin() + 4, out.end() - 4));
151#endif
152 }
153}
154
155TEST_CONSTEXPR_CXX20 bool test() {
156 types::for_each(types::cpp17_input_iterator_list<int*>(), TestIter2<int, types::cpp17_input_iterator_list<int*> >());
157 types::for_each(
158 types::cpp17_input_iterator_list<char*>(), TestIter2<char, types::cpp17_input_iterator_list<char*> >());
159 types::for_each(types::cpp17_input_iterator_list<AddressCompare*>(),
160 TestIter2<AddressCompare, types::cpp17_input_iterator_list<AddressCompare*> >());
161
162 types::for_each(types::integral_types(), TestNarrowingEqualTo());
163
164#if TEST_STD_VER >= 20
165 types::for_each(
166 types::cpp17_input_iterator_list<trivially_equality_comparable*>{},
167 TestIter2<trivially_equality_comparable, types::cpp17_input_iterator_list<trivially_equality_comparable*>>{});
168#endif
169
170 { // Test vector<bool>::iterator optimization
171 test_vector_bool<8>();
172 test_vector_bool<19>();
173 test_vector_bool<32>();
174 test_vector_bool<49>();
175 test_vector_bool<64>();
176 test_vector_bool<199>();
177 test_vector_bool<256>();
178 }
179
180 // Make sure std::equal behaves properly with std::vector<bool> iterators with custom size types.
181 // See issue: https://github.com/llvm/llvm-project/issues/126369.
182 {
183 //// Tests for std::equal with aligned bits
184
185 { // Test the first (partial) word for uint8_t
186 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
187 std::vector<bool, Alloc> in(6, true, Alloc(1));
188 std::vector<bool, Alloc> expected(8, true, Alloc(1));
189 assert(std::equal(in.begin() + 4, in.end(), expected.begin() + 4));
190 }
191 { // Test the last word for uint8_t
192 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
193 std::vector<bool, Alloc> in(12, true, Alloc(1));
194 std::vector<bool, Alloc> expected(16, true, Alloc(1));
195 assert(std::equal(in.begin(), in.end(), expected.begin()));
196 }
197 { // Test middle words for uint8_t
198 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
199 std::vector<bool, Alloc> in(24, true, Alloc(1));
200 std::vector<bool, Alloc> expected(29, true, Alloc(1));
201 assert(std::equal(in.begin(), in.end(), expected.begin()));
202 }
203
204 { // Test the first (partial) word for uint16_t
205 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
206 std::vector<bool, Alloc> in(12, true, Alloc(1));
207 std::vector<bool, Alloc> expected(16, true, Alloc(1));
208 assert(std::equal(in.begin() + 4, in.end(), expected.begin() + 4));
209 }
210 { // Test the last word for uint16_t
211 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
212 std::vector<bool, Alloc> in(24, true, Alloc(1));
213 std::vector<bool, Alloc> expected(32, true, Alloc(1));
214 assert(std::equal(in.begin(), in.end(), expected.begin()));
215 }
216 { // Test middle words for uint16_t
217 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
218 std::vector<bool, Alloc> in(48, true, Alloc(1));
219 std::vector<bool, Alloc> expected(55, true, Alloc(1));
220 assert(std::equal(in.begin(), in.end(), expected.begin()));
221 }
222
223 //// Tests for std::equal with unaligned bits
224
225 { // Test the first (partial) word for uint8_t
226 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
227 std::vector<bool, Alloc> in(6, true, Alloc(1));
228 std::vector<bool, Alloc> expected(8, true, Alloc(1));
229 assert(std::equal(in.begin() + 4, in.end(), expected.begin()));
230 }
231 { // Test the last word for uint8_t
232 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
233 std::vector<bool, Alloc> in(4, true, Alloc(1));
234 std::vector<bool, Alloc> expected(8, true, Alloc(1));
235 assert(std::equal(in.begin(), in.end(), expected.begin() + 3));
236 }
237 { // Test middle words for uint8_t
238 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
239 std::vector<bool, Alloc> in(16, true, Alloc(1));
240 std::vector<bool, Alloc> expected(24, true, Alloc(1));
241 assert(std::equal(in.begin(), in.end(), expected.begin() + 4));
242 }
243
244 { // Test the first (partial) word for uint16_t
245 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
246 std::vector<bool, Alloc> in(12, true, Alloc(1));
247 std::vector<bool, Alloc> expected(16, true, Alloc(1));
248 assert(std::equal(in.begin() + 4, in.end(), expected.begin()));
249 }
250 { // Test the last word for uint16_t
251 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
252 std::vector<bool, Alloc> in(12, true, Alloc(1));
253 std::vector<bool, Alloc> expected(16, true, Alloc(1));
254 assert(std::equal(in.begin(), in.end(), expected.begin() + 3));
255 }
256 { // Test the middle words for uint16_t
257 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
258 std::vector<bool, Alloc> in(32, true, Alloc(1));
259 std::vector<bool, Alloc> expected(64, true, Alloc(1));
260 assert(std::equal(in.begin(), in.end(), expected.begin() + 4));
261 }
262 }
263
264 return true;
265}
266
267struct Base {};
268struct Derived : virtual Base {};
269
270struct TestTypes {
271 template <class T>
272 struct Test {
273 template <class U>
274 void operator()() {
275 T a[] = {1, 2, 3, 4, 5, 6};
276 U b[] = {1, 2, 3, 4, 5, 6};
277 assert(std::equal(a, a + 6, b));
278 }
279 };
280
281 template <class T>
282 void operator()() {
283 types::for_each(types::integer_types(), Test<T>());
284 }
285};
286
287int main(int, char**) {
288 test();
289#if TEST_STD_VER >= 20
290 static_assert(test());
291#endif
292
293 types::for_each(types::integer_types(), TestTypes());
294 types::for_each(types::as_pointers<types::cv_qualified_versions<int> >(),
295 TestIter2<int, types::as_pointers<types::cv_qualified_versions<int> > >());
296 types::for_each(types::as_pointers<types::cv_qualified_versions<char> >(),
297 TestIter2<char, types::as_pointers<types::cv_qualified_versions<char> > >());
298
299 {
300 Derived d;
301 Derived* a[] = {&d, nullptr};
302 Base* b[] = {&d, nullptr};
303
304 assert(std::equal(a, a + 2, b));
305#if TEST_STD_VER >= 14
306 assert(std::equal(a, a + 2, b, b + 2));
307#endif
308 }
309
310 return 0;
311}
312

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