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// REQUIRES: long_tests
10// UNSUPPORTED: GCC-ALWAYS_INLINE-FIXME
11
12// This test is super slow, in particular with msan or tsan. In order to avoid timeouts and to
13// spend less time waiting for this particular test to complete we compile with optimizations.
14// ADDITIONAL_COMPILE_FLAGS(msan): -O1
15// ADDITIONAL_COMPILE_FLAGS(tsan): -O1
16
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 >= 11
217 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#endif
236}
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> >(start: rng[i], N: rng[j], M: rng[k]);
246 testNI<std::deque<int> >(start: 1500, N: 2000, M: 1000);
247#if TEST_STD_VER >= 11
248 test_move<std::deque<MoveOnly, limited_allocator<MoveOnly, 2000> > >();
249#endif
250 }
251#if TEST_STD_VER >= 11
252 {
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#endif
273
274 return 0;
275}
276

source code of libcxx/test/std/containers/sequences/deque/deque.modifiers/insert_iter_iter.pass.cpp