272 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<InputIterator InIter, OutputIterator<auto, InIter::reference> OutIter>12// constexpr OutIter // constexpr after C++1713// copy(InIter first, InIter last, OutIter result);14 15#include <algorithm>16#include <cassert>17#include <vector>18 19#include "sized_allocator.h"20#include "test_macros.h"21#include "test_iterators.h"22#include "type_algorithms.h"23 24class PaddedBase {25public:26 TEST_CONSTEXPR PaddedBase(std::int16_t a, std::int8_t b) : a_(a), b_(b) {}27 28 std::int16_t a_;29 std::int8_t b_;30};31 32class Derived : public PaddedBase {33public:34 TEST_CONSTEXPR Derived(std::int16_t a, std::int8_t b, std::int8_t c) : PaddedBase(a, b), c_(c) {}35 36 std::int8_t c_;37};38 39template <class InIter>40struct Test {41 template <class OutIter>42 TEST_CONSTEXPR_CXX20 void operator()() {43 const unsigned N = 1000;44 int ia[N] = {};45 for (unsigned i = 0; i < N; ++i)46 ia[i] = i;47 int ib[N] = {0};48 49 OutIter r = std::copy(InIter(ia), InIter(ia + N), OutIter(ib));50 assert(base(r) == ib + N);51 for (unsigned i = 0; i < N; ++i)52 assert(ia[i] == ib[i]);53 }54};55 56struct TestInIters {57 template <class InIter>58 TEST_CONSTEXPR_CXX20 void operator()() {59 types::for_each(60 types::concatenate_t<types::cpp17_input_iterator_list<int*>, types::type_list<cpp17_output_iterator<int*> > >(),61 Test<InIter>());62 }63};64 65TEST_CONSTEXPR_CXX20 bool test_vector_bool(std::size_t N) {66 std::vector<bool> in(N, false);67 for (std::size_t i = 0; i < N; i += 2)68 in[i] = true;69 70 { // Test copy with aligned bytes71 std::vector<bool> out(N);72 std::copy(in.begin(), in.end(), out.begin());73 assert(in == out);74 }75 { // Test copy with unaligned bytes76 std::vector<bool> out(N + 8);77 std::copy(in.begin(), in.end(), out.begin() + 4);78 for (std::size_t i = 0; i < N; ++i)79 assert(out[i + 4] == in[i]);80 }81 82 return true;83}84 85TEST_CONSTEXPR_CXX20 bool test() {86 types::for_each(types::cpp17_input_iterator_list<const int*>(), TestInIters());87 88 { // Make sure that padding bits aren't copied89 Derived src(1, 2, 3);90 Derived dst(4, 5, 6);91 std::copy(static_cast<PaddedBase*>(&src), static_cast<PaddedBase*>(&src) + 1, static_cast<PaddedBase*>(&dst));92 assert(dst.a_ == 1);93 assert(dst.b_ == 2);94 assert(dst.c_ == 6);95 }96 { // Make sure that overlapping ranges can be copied97 int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};98 std::copy(a + 3, a + 10, a);99 int expected[] = {4, 5, 6, 7, 8, 9, 10, 8, 9, 10};100 assert(std::equal(a, a + 10, expected));101 }102 103 { // Test vector<bool>::iterator optimization104 assert(test_vector_bool(8));105 assert(test_vector_bool(19));106 assert(test_vector_bool(32));107 assert(test_vector_bool(49));108 assert(test_vector_bool(64));109 assert(test_vector_bool(199));110 assert(test_vector_bool(256));111 }112 113 // Validate std::copy with std::vector<bool> iterators and custom storage types.114 // Ensure that assigned bits hold the intended values, while unassigned bits stay unchanged.115 // Related issue: https://llvm.org/PR131692.116 {117 //// Tests for std::copy with aligned bits118 119 { // Test the first (partial) word for uint8_t120 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;121 std::vector<bool, Alloc> in(8, false, Alloc(1));122 std::vector<bool, Alloc> out(8, true, Alloc(1));123 std::copy(in.begin() + 1, in.begin() + 2, out.begin() + 1); // out[1] = false124 assert(out[1] == false);125 for (std::size_t i = 0; i < out.size(); ++i) // Ensure that unassigned bits remain unchanged126 if (i != 1)127 assert(out[i] == true);128 }129 { // Test the last (partial) word for uint8_t130 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;131 std::vector<bool, Alloc> in(8, false, Alloc(1));132 std::vector<bool, Alloc> out(8, true, Alloc(1));133 std::copy(in.begin(), in.begin() + 1, out.begin()); // out[0] = false134 assert(out[0] == false);135 for (std::size_t i = 1; i < out.size(); ++i) // Ensure that unassigned bits remain unchanged136 assert(out[i] == true);137 }138 { // Test middle (whole) words for uint8_t139 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;140 std::vector<bool, Alloc> in(32, true, Alloc(1));141 for (std::size_t i = 0; i < in.size(); i += 2)142 in[i] = false;143 std::vector<bool, Alloc> out(32, false, Alloc(1));144 std::copy(in.begin() + 4, in.end() - 4, out.begin() + 4);145 for (std::size_t i = 4; i < static_cast<std::size_t>(in.size() - 4); ++i)146 assert(in[i] == out[i]);147 for (std::size_t i = 0; i < 4; ++i)148 assert(out[i] == false);149 for (std::size_t i = 28; i < out.size(); ++i)150 assert(out[i] == false);151 }152 153 { // Test the first (partial) word for uint16_t154 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;155 std::vector<bool, Alloc> in(16, false, Alloc(1));156 std::vector<bool, Alloc> out(16, true, Alloc(1));157 std::copy(in.begin() + 1, in.begin() + 3, out.begin() + 1); // out[1..2] = false158 assert(out[1] == false);159 assert(out[2] == false);160 for (std::size_t i = 0; i < out.size(); ++i) // Ensure that unassigned bits remain unchanged161 if (i != 1 && i != 2)162 assert(out[i] == true);163 }164 { // Test the last (partial) word for uint16_t165 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;166 std::vector<bool, Alloc> in(16, false, Alloc(1));167 std::vector<bool, Alloc> out(16, true, Alloc(1));168 std::copy(in.begin(), in.begin() + 2, out.begin()); // out[0..1] = false169 assert(out[0] == false);170 assert(out[1] == false);171 for (std::size_t i = 2; i < out.size(); ++i) // Ensure that unassigned bits remain unchanged172 assert(out[i] == true);173 }174 { // Test middle (whole) words for uint16_t175 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;176 std::vector<bool, Alloc> in(64, true, Alloc(1));177 for (std::size_t i = 0; i < in.size(); i += 2)178 in[i] = false;179 std::vector<bool, Alloc> out(64, false, Alloc(1));180 std::copy(in.begin() + 8, in.end() - 8, out.begin() + 8);181 for (std::size_t i = 8; i < static_cast<std::size_t>(in.size() - 8); ++i)182 assert(in[i] == out[i]);183 for (std::size_t i = 0; i < 8; ++i)184 assert(out[i] == false);185 for (std::size_t i = static_cast<std::size_t>(out.size() - 8); i < out.size(); ++i)186 assert(out[i] == false);187 }188 189 //// Tests for std::copy with unaligned bits190 191 { // Test the first (partial) word for uint8_t192 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;193 std::vector<bool, Alloc> in(8, false, Alloc(1));194 std::vector<bool, Alloc> out(8, true, Alloc(1));195 std::copy(in.begin() + 7, in.end(), out.begin()); // out[0] = false196 assert(out[0] == false);197 for (std::size_t i = 1; i < out.size(); ++i) // Ensure that unassigned bits remain unchanged198 assert(out[i] == true);199 }200 { // Test the last (partial) word for uint8_t201 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;202 std::vector<bool, Alloc> in(8, false, Alloc(1));203 std::vector<bool, Alloc> out(8, true, Alloc(1));204 std::copy(in.begin(), in.begin() + 1, out.begin() + 2); // out[2] = false205 assert(out[2] == false);206 for (std::size_t i = 1; i < out.size(); ++i) // Ensure that unassigned bits remain unchanged207 if (i != 2)208 assert(out[i] == true);209 }210 { // Test middle (whole) words for uint8_t211 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;212 std::vector<bool, Alloc> in(36, true, Alloc(1));213 for (std::size_t i = 0; i < in.size(); i += 2)214 in[i] = false;215 std::vector<bool, Alloc> out(40, false, Alloc(1));216 std::copy(in.begin(), in.end(), out.begin() + 4);217 for (std::size_t i = 0; i < in.size(); ++i)218 assert(in[i] == out[i + 4]);219 for (std::size_t i = 0; i < 4; ++i)220 assert(out[i] == false);221 }222 223 { // Test the first (partial) word for uint16_t224 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;225 std::vector<bool, Alloc> in(16, false, Alloc(1));226 std::vector<bool, Alloc> out(16, true, Alloc(1));227 std::copy(in.begin() + 14, in.end(), out.begin()); // out[0..1] = false228 assert(out[0] == false);229 assert(out[1] == false);230 for (std::size_t i = 2; i < out.size(); ++i) // Ensure that unassigned bits remain unchanged231 assert(out[i] == true);232 }233 { // Test the last (partial) word for uint16_t234 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;235 std::vector<bool, Alloc> in(16, false, Alloc(1));236 std::vector<bool, Alloc> out(16, true, Alloc(1));237 std::copy(in.begin(), in.begin() + 2, out.begin() + 1); // out[1..2] = false238 assert(out[1] == false);239 assert(out[2] == false);240 for (std::size_t i = 0; i < out.size(); ++i) // Ensure that unassigned bits remain unchanged241 if (i != 1 && i != 2)242 assert(out[i] == true);243 }244 { // Test middle (whole) words for uint16_t245 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;246 std::vector<bool, Alloc> in(72, true, Alloc(1));247 for (std::size_t i = 0; i < in.size(); i += 2)248 in[i] = false;249 std::vector<bool, Alloc> out(80, false, Alloc(1));250 std::copy(in.begin(), in.end(), out.begin() + 4);251 for (std::size_t i = 0; i < in.size(); ++i)252 assert(in[i] == out[i + 4]);253 for (std::size_t i = 0; i < 4; ++i)254 assert(out[i] == false);255 for (std::size_t i = in.size() + 4; i < out.size(); ++i)256 assert(out[i] == false);257 }258 }259 260 return true;261}262 263int main(int, char**) {264 test();265 266#if TEST_STD_VER >= 20267 static_assert(test());268#endif269 270 return 0;271}272