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<BidirectionalIterator InIter, BidirectionalIterator OutIter>
12// requires OutputIterator<OutIter, InIter::reference>
13// constexpr OutIter // constexpr after C++17
14// copy_backward(InIter first, InIter last, OutIter result);
15
16// XFAIL: FROZEN-CXX03-HEADERS-FIXME
17
18#include <algorithm>
19#include <cassert>
20#include <vector>
21
22#include "sized_allocator.h"
23#include "test_macros.h"
24#include "test_iterators.h"
25#include "type_algorithms.h"
26#include "user_defined_integral.h"
27
28class PaddedBase {
29public:
30 TEST_CONSTEXPR PaddedBase(std::int16_t a, std::int8_t b) : a_(a), b_(b) {}
31
32 std::int16_t a_;
33 std::int8_t b_;
34};
35
36class Derived : public PaddedBase {
37public:
38 TEST_CONSTEXPR Derived(std::int16_t a, std::int8_t b, std::int8_t c) : PaddedBase(a, b), c_(c) {}
39
40 std::int8_t c_;
41};
42
43struct TestIterators {
44 template <class InIter>
45 TEST_CONSTEXPR_CXX20 void operator()() {
46 types::for_each(types::bidirectional_iterator_list<int*>(), TestImpl<InIter>());
47 }
48
49 template <class InIter>
50 struct TestImpl {
51 template <class OutIter>
52 TEST_CONSTEXPR_CXX20 void operator()() {
53 const unsigned N = 1000;
54 int ia[N] = {};
55 for (unsigned i = 0; i < N; ++i)
56 ia[i] = i;
57 int ib[N] = {0};
58
59 OutIter r = std::copy_backward(InIter(ia), InIter(ia + N), OutIter(ib + N));
60 assert(base(r) == ib);
61 for (unsigned i = 0; i < N; ++i)
62 assert(ia[i] == ib[i]);
63 }
64 };
65};
66
67TEST_CONSTEXPR_CXX20 bool test_vector_bool(std::size_t N) {
68 std::vector<bool> in(N, false);
69 for (std::size_t i = 0; i < N; i += 2)
70 in[i] = true;
71
72 { // Test copy_backward with aligned bytes
73 std::vector<bool> out(N);
74 std::copy_backward(first: in.begin(), last: in.end(), result: out.end());
75 assert(in == out);
76 }
77 { // Test copy_backward with unaligned bytes
78 std::vector<bool> out(N + 8);
79 std::copy_backward(first: in.begin(), last: in.end(), result: out.end() - 4);
80 for (std::size_t i = 0; i < N; ++i)
81 assert(out[i + 4] == in[i]);
82 }
83
84 return true;
85}
86
87TEST_CONSTEXPR_CXX20 bool test() {
88 types::for_each(types::bidirectional_iterator_list<const int*>(), TestIterators());
89
90 { // Make sure that padding bits aren't copied
91 Derived src(1, 2, 3);
92 Derived dst(4, 5, 6);
93 std::copy_backward(
94 static_cast<PaddedBase*>(&src), static_cast<PaddedBase*>(&src) + 1, static_cast<PaddedBase*>(&dst) + 1);
95 assert(dst.a_ == 1);
96 assert(dst.b_ == 2);
97 assert(dst.c_ == 6);
98 }
99
100 { // Make sure that overlapping ranges can be copied
101 int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
102 std::copy_backward(first: a, last: a + 7, result: a + 10);
103 int expected[] = {1, 2, 3, 1, 2, 3, 4, 5, 6, 7};
104 assert(std::equal(a, a + 10, expected));
105 }
106
107 { // Test vector<bool>::iterator optimization
108 assert(test_vector_bool(8));
109 assert(test_vector_bool(19));
110 assert(test_vector_bool(32));
111 assert(test_vector_bool(49));
112 assert(test_vector_bool(64));
113 assert(test_vector_bool(199));
114 assert(test_vector_bool(256));
115 }
116
117 // Validate std::copy_backward with std::vector<bool> iterators and custom storage types.
118 // Ensure that assigned bits hold the intended values, while unassigned bits stay unchanged.
119 // Related issue: https://github.com/llvm/llvm-project/issues/131718.
120 {
121 //// Tests for std::copy_backward with aligned bits
122
123 { // Test the first (partial) word for uint8_t
124 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
125 std::vector<bool, Alloc> in(7, false, Alloc(1));
126 std::vector<bool, Alloc> out(8, true, Alloc(1));
127 std::copy_backward(in.begin(), in.begin() + 1, out.begin() + 1);
128 assert(out[0] == false);
129 for (std::size_t i = 1; i < out.size(); ++i)
130 assert(out[i] == true);
131 }
132 { // Test the last (partial) word for uint8_t
133 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
134 std::vector<bool, Alloc> in(8, false, Alloc(1));
135 for (std::size_t i = 0; i < in.size(); i += 2)
136 in[i] = true;
137 std::vector<bool, Alloc> out(8, true, Alloc(1));
138 std::copy_backward(in.end() - 4, in.end(), out.end());
139 for (std::size_t i = 0; i < static_cast<std::size_t>(in.size() - 4); ++i)
140 assert(out[i] == true);
141 for (std::size_t i = in.size() + 4; i < out.size(); ++i)
142 assert(in[i] == out[i]);
143 }
144 { // Test the middle (whole) words for uint8_t
145 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
146 std::vector<bool, Alloc> in(17, false, Alloc(1));
147 for (std::size_t i = 0; i < in.size(); i += 2)
148 in[i] = true;
149 std::vector<bool, Alloc> out(24, true, Alloc(1));
150 std::copy_backward(in.begin(), in.end(), out.begin() + in.size());
151 for (std::size_t i = 0; i < in.size(); ++i)
152 assert(in[i] == out[i]);
153 for (std::size_t i = in.size(); i < out.size(); ++i)
154 assert(out[i] == true);
155 }
156
157 { // Test the first (partial) word for uint16_t
158 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
159 std::vector<bool, Alloc> in(14, false, Alloc(1));
160 std::vector<bool, Alloc> out(16, true, Alloc(1));
161 std::copy_backward(in.begin(), in.begin() + 2, out.begin() + 2);
162 assert(out[0] == false);
163 assert(out[1] == false);
164 for (std::size_t i = 2; i < out.size(); ++i)
165 assert(out[i] == true);
166 }
167 { // Test the last (partial) word for uint16_t
168 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
169 std::vector<bool, Alloc> in(16, false, Alloc(1));
170 for (std::size_t i = 0; i < in.size(); i += 2)
171 in[i] = true;
172 std::vector<bool, Alloc> out(16, true, Alloc(1));
173 std::copy_backward(in.end() - 8, in.end(), out.end());
174 for (std::size_t i = 0; i < static_cast<std::size_t>(in.size() - 8); ++i)
175 assert(out[i] == true);
176 for (std::size_t i = in.size() + 8; i < out.size(); ++i)
177 assert(in[i] == out[i]);
178 }
179 { // Test the middle (whole) words for uint16_t
180 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
181 std::vector<bool, Alloc> in(34, false, Alloc(1));
182 for (std::size_t i = 0; i < in.size(); i += 2)
183 in[i] = true;
184 std::vector<bool, Alloc> out(48, true, Alloc(1));
185 std::copy_backward(in.begin(), in.end(), out.begin() + in.size());
186 for (std::size_t i = 0; i < in.size(); ++i)
187 assert(in[i] == out[i]);
188 for (std::size_t i = in.size(); i < out.size(); ++i)
189 assert(out[i] == true);
190 }
191
192 //// Tests for std::copy_backward with unaligned bits
193
194 { // Test the first (partial) word for uint8_t
195 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
196 std::vector<bool, Alloc> in(8, false, Alloc(1));
197 std::vector<bool, Alloc> out(8, true, Alloc(1));
198 std::copy_backward(in.begin(), in.begin() + 1, out.begin() + 1);
199 assert(out[0] == false);
200 for (std::size_t i = 1; i < out.size(); ++i)
201 assert(out[i] == true);
202 }
203 { // Test the last (partial) word for uint8_t
204 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
205 std::vector<bool, Alloc> in(8, false, Alloc(1));
206 std::vector<bool, Alloc> out(8, true, Alloc(1));
207 std::copy_backward(in.end() - 1, in.end(), out.begin() + 1);
208 assert(out[0] == false);
209 for (std::size_t i = 1; i < out.size(); ++i)
210 assert(out[i] == true);
211 }
212 { // Test the middle (whole) words for uint8_t
213 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
214 std::vector<bool, Alloc> in(16, false, Alloc(1));
215 for (std::size_t i = 0; i < in.size(); i += 2)
216 in[i] = true;
217 std::vector<bool, Alloc> out(17, true, Alloc(1));
218 std::copy_backward(in.begin(), in.end(), out.end());
219 assert(out[0] == true);
220 for (std::size_t i = 0; i < in.size(); ++i)
221 assert(in[i] == out[i + 1]);
222 }
223
224 { // Test the first (partial) word for uint16_t
225 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
226 std::vector<bool, Alloc> in(16, false, Alloc(1));
227 std::vector<bool, Alloc> out(16, true, Alloc(1));
228 std::copy_backward(in.begin(), in.begin() + 2, out.begin() + 2);
229 assert(out[0] == false);
230 assert(out[1] == false);
231 for (std::size_t i = 2; i < out.size(); ++i)
232 assert(out[i] == true);
233 }
234 { // Test the last (partial) word for uint16_t
235 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
236 std::vector<bool, Alloc> in(16, false, Alloc(1));
237 std::vector<bool, Alloc> out(16, true, Alloc(1));
238 std::copy_backward(in.end() - 2, in.end(), out.begin() + 2);
239 assert(out[0] == false);
240 assert(out[1] == false);
241 for (std::size_t i = 2; i < out.size(); ++i)
242 assert(out[i] == true);
243 }
244 { // Test the middle (whole) words for uint16_t
245 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
246 std::vector<bool, Alloc> in(32, false, Alloc(1));
247 for (std::size_t i = 0; i < in.size(); i += 2)
248 in[i] = true;
249 std::vector<bool, Alloc> out(33, true, Alloc(1));
250 std::copy_backward(in.begin(), in.end(), out.end());
251 assert(out[0] == true);
252 for (std::size_t i = 0; i < in.size(); ++i)
253 assert(in[i] == out[i + 1]);
254 }
255 }
256
257 return true;
258}
259
260int main(int, char**) {
261 test();
262
263#if TEST_STD_VER > 17
264 static_assert(test());
265#endif
266
267 return 0;
268}
269

source code of libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/copy_backward.pass.cpp