269 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// template<BidirectionalIterator InIter, BidirectionalIterator OutIter>12// requires OutputIterator<OutIter, InIter::reference>13// constexpr OutIter // constexpr after C++1714// copy_backward(InIter first, InIter last, OutIter result);15 16// XFAIL: FROZEN-CXX03-HEADERS-FIXME17 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 bytes73 std::vector<bool> out(N);74 std::copy_backward(in.begin(), in.end(), out.end());75 assert(in == out);76 }77 { // Test copy_backward with unaligned bytes78 std::vector<bool> out(N + 8);79 std::copy_backward(in.begin(), in.end(), 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 copied91 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 copied101 int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};102 std::copy_backward(a, a + 7, 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 optimization108 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://llvm.org/PR131718.120 {121 //// Tests for std::copy_backward with aligned bits122 123 { // Test the first (partial) word for uint8_t124 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_t133 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_t145 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_t158 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_t168 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_t180 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 bits193 194 { // Test the first (partial) word for uint8_t195 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_t204 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_t213 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_t225 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_t235 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_t245 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 > 17264 static_assert(test());265#endif266 267 return 0;268}269