276 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// REQUIRES: long_tests10// UNSUPPORTED: GCC-ALWAYS_INLINE-FIXME11 12// This test is super slow, in particular with msan or tsan. In order to avoid timeouts and to13// spend less time waiting for this particular test to complete we compile with optimizations.14// ADDITIONAL_COMPILE_FLAGS(msan): -O115// ADDITIONAL_COMPILE_FLAGS(tsan): -O116 17// <deque>18 19// template <class InputIterator>20// iterator insert (const_iterator p, InputIterator f, InputIterator l);21 22#include "asan_testing.h"23#include <deque>24#include <cassert>25#include <cstddef>26 27#include "test_macros.h"28#include "test_iterators.h"29#include "MoveOnly.h"30#include "test_allocator.h"31#include "min_allocator.h"32 33template <class C>34C make(int size, int start = 0) {35 const int b = 4096 / sizeof(int);36 int init = 0;37 if (start > 0) {38 init = (start + 1) / b + ((start + 1) % b != 0);39 init *= b;40 --init;41 }42 C c(init, 0);43 for (int i = 0; i < init - start; ++i)44 c.pop_back();45 for (int i = 0; i < size; ++i)46 c.push_back(i);47 for (int i = 0; i < start; ++i)48 c.pop_front();49 return c;50}51 52template <class C>53void test(int P, const C& c0, const C& c2) {54 {55 typedef typename C::const_iterator CI;56 typedef cpp17_input_iterator<CI> BCI;57 C c1 = c0;58 std::size_t c1_osize = c1.size();59 CI i = c1.insert(c1.begin() + P, BCI(c2.begin()), BCI(c2.end()));60 assert(i == c1.begin() + P);61 assert(c1.size() == c1_osize + c2.size());62 assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());63 LIBCPP_ASSERT(is_double_ended_contiguous_container_asan_correct(c1));64 LIBCPP_ASSERT(is_double_ended_contiguous_container_asan_correct(c2));65 i = c1.begin();66 for (int j = 0; j < P; ++j, ++i)67 assert(*i == j);68 for (int j = 0; static_cast<std::size_t>(j) < c2.size(); ++j, ++i)69 assert(*i == j);70 for (int j = P; static_cast<std::size_t>(j) < c1_osize; ++j, ++i)71 assert(*i == j);72 }73 {74 typedef typename C::const_iterator CI;75 typedef forward_iterator<CI> BCI;76 C c1 = c0;77 std::size_t c1_osize = c1.size();78 CI i = c1.insert(c1.begin() + P, BCI(c2.begin()), BCI(c2.end()));79 assert(i == c1.begin() + P);80 assert(c1.size() == c1_osize + c2.size());81 assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());82 i = c1.begin();83 for (int j = 0; j < P; ++j, ++i)84 assert(*i == j);85 for (int j = 0; static_cast<std::size_t>(j) < c2.size(); ++j, ++i)86 assert(*i == j);87 for (int j = P; static_cast<std::size_t>(j) < c1_osize; ++j, ++i)88 assert(*i == j);89 }90 {91 typedef typename C::const_iterator CI;92 typedef bidirectional_iterator<CI> BCI;93 C c1 = c0;94 std::size_t c1_osize = c1.size();95 CI i = c1.insert(c1.begin() + P, BCI(c2.begin()), BCI(c2.end()));96 assert(i == c1.begin() + P);97 assert(c1.size() == c1_osize + c2.size());98 assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());99 i = c1.begin();100 for (int j = 0; j < P; ++j, ++i)101 assert(*i == j);102 for (int j = 0; static_cast<std::size_t>(j) < c2.size(); ++j, ++i)103 assert(*i == j);104 for (int j = P; static_cast<std::size_t>(j) < c1_osize; ++j, ++i)105 assert(*i == j);106 }107}108 109template <class C>110void testN(int start, int N, int M) {111 for (int i = 0; i <= 3; ++i) {112 if (0 <= i && i <= N) {113 C c1 = make<C>(N, start);114 C c2 = make<C>(M);115 test(i, c1, c2);116 }117 }118 for (int i = M - 1; i <= M + 1; ++i) {119 if (0 <= i && i <= N) {120 C c1 = make<C>(N, start);121 C c2 = make<C>(M);122 test(i, c1, c2);123 }124 }125 for (int i = N / 2 - 1; i <= N / 2 + 1; ++i) {126 if (0 <= i && i <= N) {127 C c1 = make<C>(N, start);128 C c2 = make<C>(M);129 test(i, c1, c2);130 }131 }132 for (int i = N - M - 1; i <= N - M + 1; ++i) {133 if (0 <= i && i <= N) {134 C c1 = make<C>(N, start);135 C c2 = make<C>(M);136 test(i, c1, c2);137 }138 }139 for (int i = N - M - 1; i <= N - M + 1; ++i) {140 if (0 <= i && i <= N) {141 C c1 = make<C>(N, start);142 C c2 = make<C>(M);143 test(i, c1, c2);144 }145 }146 for (int i = N - 3; i <= N; ++i) {147 if (0 <= i && i <= N) {148 C c1 = make<C>(N, start);149 C c2 = make<C>(M);150 test(i, c1, c2);151 }152 }153}154 155template <class C>156void testI(int P, C& c1, const C& c2) {157 typedef typename C::const_iterator CI;158 typedef cpp17_input_iterator<CI> ICI;159 std::size_t c1_osize = c1.size();160 CI i = c1.insert(c1.begin() + P, ICI(c2.begin()), ICI(c2.end()));161 assert(i == c1.begin() + P);162 assert(c1.size() == c1_osize + c2.size());163 assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());164 LIBCPP_ASSERT(is_double_ended_contiguous_container_asan_correct(c1));165 LIBCPP_ASSERT(is_double_ended_contiguous_container_asan_correct(c2));166 i = c1.begin();167 for (int j = 0; j < P; ++j, ++i)168 assert(*i == j);169 for (int j = 0; static_cast<std::size_t>(j) < c2.size(); ++j, ++i)170 assert(*i == j);171 for (int j = P; static_cast<std::size_t>(j) < c1_osize; ++j, ++i)172 assert(*i == j);173}174 175template <class C>176void testNI(int start, int N, int M) {177 for (int i = 0; i <= 3; ++i) {178 if (0 <= i && i <= N) {179 C c1 = make<C>(N, start);180 C c2 = make<C>(M);181 testI(i, c1, c2);182 }183 }184 for (int i = M - 1; i <= M + 1; ++i) {185 if (0 <= i && i <= N) {186 C c1 = make<C>(N, start);187 C c2 = make<C>(M);188 testI(i, c1, c2);189 }190 }191 for (int i = N / 2 - 1; i <= N / 2 + 1; ++i) {192 if (0 <= i && i <= N) {193 C c1 = make<C>(N, start);194 C c2 = make<C>(M);195 testI(i, c1, c2);196 }197 }198 for (int i = N - M - 1; i <= N - M + 1; ++i) {199 if (0 <= i && i <= N) {200 C c1 = make<C>(N, start);201 C c2 = make<C>(M);202 testI(i, c1, c2);203 }204 }205 for (int i = N - 3; i <= N; ++i) {206 if (0 <= i && i <= N) {207 C c1 = make<C>(N, start);208 C c2 = make<C>(M);209 testI(i, c1, c2);210 }211 }212}213 214template <class C>215void test_move() {216#if TEST_STD_VER >= 11217 C c;218 typedef typename C::const_iterator CI;219 {220 MoveOnly mo(0);221 typedef MoveOnly* I;222 c.insert(c.end(), std::move_iterator<I>(&mo), std::move_iterator<I>(&mo + 1));223 }224 int j = 0;225 for (CI i = c.begin(); i != c.end(); ++i, (void)++j)226 assert(*i == MoveOnly(j));227 {228 MoveOnly mo(1);229 typedef cpp17_input_iterator<MoveOnly*> I;230 c.insert(c.end(), std::move_iterator<I>(I(&mo)), std::move_iterator<I>(I(&mo + 1)));231 }232 j = 0;233 for (CI i = c.begin(); i != c.end(); ++i, (void)++j)234 assert(*i == MoveOnly(j));235#endif236}237 238int main(int, char**) {239 {240 int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};241 const int N = sizeof(rng) / sizeof(rng[0]);242 for (int i = 0; i < N; ++i)243 for (int j = 0; j < N; ++j)244 for (int k = 0; k < N; ++k)245 testN<std::deque<int> >(rng[i], rng[j], rng[k]);246 testNI<std::deque<int> >(1500, 2000, 1000);247#if TEST_STD_VER >= 11248 test_move<std::deque<MoveOnly, limited_allocator<MoveOnly, 2000> > >();249#endif250 }251#if TEST_STD_VER >= 11252 {253 int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};254 const int N = sizeof(rng) / sizeof(rng[0]);255 for (int i = 0; i < N; ++i)256 for (int j = 0; j < N; ++j)257 for (int k = 0; k < N; ++k)258 testN<std::deque<int, min_allocator<int>> >(rng[i], rng[j], rng[k]);259 testNI<std::deque<int> >(1500, 2000, 1000);260 test_move<std::deque<MoveOnly, min_allocator<MoveOnly> > >();261 }262 {263 int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};264 const int N = sizeof(rng) / sizeof(rng[0]);265 for (int i = 0; i < N; ++i)266 for (int j = 0; j < N; ++j)267 for (int k = 0; k < N; ++k)268 testN<std::deque<int, safe_allocator<int>> >(rng[i], rng[j], rng[k]);269 testNI<std::deque<int> >(1500, 2000, 1000);270 test_move<std::deque<MoveOnly, safe_allocator<MoveOnly> > >();271 }272#endif273 274 return 0;275}276