176 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// UNSUPPORTED: c++03 && !stdlib=libc++10 11// <algorithm>12 13// template<BidirectionalIterator InIter, BidirectionalIterator OutIter>14// requires OutputIterator<OutIter, RvalueOf<InIter::reference>::type>15// OutIter16// move_backward(InIter first, InIter last, OutIter result);17 18#include <algorithm>19#include <cassert>20#include <iterator>21#include <memory>22#include <vector>23 24#include "MoveOnly.h"25#include "test_iterators.h"26#include "test_macros.h"27#include "type_algorithms.h"28 29class PaddedBase {30public:31 TEST_CONSTEXPR PaddedBase(std::int16_t a, std::int8_t b) : a_(a), b_(b) {}32 33 std::int16_t a_;34 std::int8_t b_;35};36 37class Derived : public PaddedBase {38public:39 TEST_CONSTEXPR Derived(std::int16_t a, std::int8_t b, std::int8_t c) : PaddedBase(a, b), c_(c) {}40 41 std::int8_t c_;42};43 44template <class InIter>45struct Test {46 template <class OutIter>47 TEST_CONSTEXPR_CXX20 void operator()() {48 const unsigned N = 1000;49 int ia[N] = {};50 for (unsigned i = 0; i < N; ++i)51 ia[i] = i;52 int ib[N] = {0};53 54 OutIter r = std::move_backward(InIter(ia), InIter(ia + N), OutIter(ib + N));55 assert(base(r) == ib);56 for (unsigned i = 0; i < N; ++i)57 assert(ia[i] == ib[i]);58 }59};60 61struct TestOutIters {62 template <class InIter>63 TEST_CONSTEXPR_CXX20 void operator()() {64 types::for_each(types::concatenate_t<types::bidirectional_iterator_list<int*> >(), Test<InIter>());65 }66};67 68template <class InIter>69struct Test1 {70 template <class OutIter>71 TEST_CONSTEXPR_CXX23 void operator()() {72 const unsigned N = 100;73 std::unique_ptr<int> ia[N];74 for (unsigned i = 0; i < N; ++i)75 ia[i].reset(new int(i));76 std::unique_ptr<int> ib[N];77 78 OutIter r = std::move_backward(InIter(ia), InIter(ia + N), OutIter(ib + N));79 assert(base(r) == ib);80 for (unsigned i = 0; i < N; ++i)81 assert(*ib[i] == static_cast<int>(i));82 }83};84 85struct Test1OutIters {86 template <class InIter>87 TEST_CONSTEXPR_CXX23 void operator()() {88 types::for_each(89 types::concatenate_t<types::bidirectional_iterator_list<std::unique_ptr<int>*> >(), Test1<InIter>());90 }91};92 93TEST_CONSTEXPR_CXX20 bool test_vector_bool(std::size_t N) {94 std::vector<bool> v(N, false);95 for (std::size_t i = 0; i < N; i += 2)96 v[i] = true;97 98 { // Test move_backward with aligned bytes99 std::vector<bool> in(v);100 std::vector<bool> out(N);101 std::move_backward(in.begin(), in.end(), out.end());102 assert(out == v);103 }104 { // Test move_backward with unaligned bytes105 std::vector<bool> in(v);106 std::vector<bool> out(N);107 std::move_backward(in.begin(), in.end() - 4, out.end());108 for (std::size_t i = 0; i < N - 4; ++i)109 assert(out[i + 4] == v[i]);110 }111 112 return true;113}114 115TEST_CONSTEXPR_CXX20 bool test() {116 types::for_each(types::bidirectional_iterator_list<int*>(), TestOutIters());117 if (TEST_STD_AT_LEAST_23_OR_RUNTIME_EVALUATED)118 types::for_each(types::bidirectional_iterator_list<std::unique_ptr<int>*>(), Test1OutIters());119 { // Make sure that padding bits aren't copied120 Derived src(1, 2, 3);121 Derived dst(4, 5, 6);122 std::move_backward(123 static_cast<PaddedBase*>(&src), static_cast<PaddedBase*>(&src) + 1, static_cast<PaddedBase*>(&dst) + 1);124 assert(dst.a_ == 1);125 assert(dst.b_ == 2);126 assert(dst.c_ == 6);127 }128 { // Make sure that overlapping ranges can be copied129 int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};130 std::move_backward(a, a + 7, a + 10);131 int expected[] = {1, 2, 3, 1, 2, 3, 4, 5, 6, 7};132 assert(std::equal(a, a + 10, expected));133 }134 { // Make sure that the algorithm works with move-only types135 // When non-trivial136 {137 MoveOnly from[3] = {1, 2, 3};138 MoveOnly to[3] = {};139 std::move_backward(std::begin(from), std::end(from), std::end(to));140 assert(to[0] == MoveOnly(1));141 assert(to[1] == MoveOnly(2));142 assert(to[2] == MoveOnly(3));143 }144 // When trivial145 {146 TrivialMoveOnly from[3] = {1, 2, 3};147 TrivialMoveOnly to[3] = {};148 std::move_backward(std::begin(from), std::end(from), std::end(to));149 assert(to[0] == TrivialMoveOnly(1));150 assert(to[1] == TrivialMoveOnly(2));151 assert(to[2] == TrivialMoveOnly(3));152 }153 }154 155 { // Test vector<bool>::iterator optimization156 assert(test_vector_bool(8));157 assert(test_vector_bool(19));158 assert(test_vector_bool(32));159 assert(test_vector_bool(49));160 assert(test_vector_bool(64));161 assert(test_vector_bool(199));162 assert(test_vector_bool(256));163 }164 165 return true;166}167 168int main(int, char**) {169 test();170#if TEST_STD_VER >= 20171 static_assert(test());172#endif173 174 return 0;175}176