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
35make(int size, int start = 0 )
36{
37 const int b = 4096 / sizeof(int);
38 int init = 0;
39 if (start > 0)
40 {
41 init = (start+1) / b + ((start+1) % b != 0);
42 init *= b;
43 --init;
44 }
45 C c(init, 0);
46 for (int i = 0; i < init-start; ++i)
47 c.pop_back();
48 for (int i = 0; i < size; ++i)
49 c.push_back(i);
50 for (int i = 0; i < start; ++i)
51 c.pop_front();
52 return c;
53}
54
55template <class C>
56void
57test(int P, const C& c0, const C& c2)
58{
59 {
60 typedef typename C::const_iterator CI;
61 typedef cpp17_input_iterator<CI> BCI;
62 C c1 = c0;
63 std::size_t c1_osize = c1.size();
64 CI i = c1.insert(c1.begin() + P, BCI(c2.begin()), BCI(c2.end()));
65 assert(i == c1.begin() + P);
66 assert(c1.size() == c1_osize + c2.size());
67 assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
68 LIBCPP_ASSERT(is_double_ended_contiguous_container_asan_correct(c1));
69 LIBCPP_ASSERT(is_double_ended_contiguous_container_asan_correct(c2));
70 i = c1.begin();
71 for (int j = 0; j < P; ++j, ++i)
72 assert(*i == j);
73 for (int j = 0; static_cast<std::size_t>(j) < c2.size(); ++j, ++i)
74 assert(*i == j);
75 for (int j = P; static_cast<std::size_t>(j) < c1_osize; ++j, ++i)
76 assert(*i == j);
77 }
78 {
79 typedef typename C::const_iterator CI;
80 typedef forward_iterator<CI> BCI;
81 C c1 = c0;
82 std::size_t c1_osize = c1.size();
83 CI i = c1.insert(c1.begin() + P, BCI(c2.begin()), BCI(c2.end()));
84 assert(i == c1.begin() + P);
85 assert(c1.size() == c1_osize + c2.size());
86 assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
87 i = c1.begin();
88 for (int j = 0; j < P; ++j, ++i)
89 assert(*i == j);
90 for (int j = 0; static_cast<std::size_t>(j) < c2.size(); ++j, ++i)
91 assert(*i == j);
92 for (int j = P; static_cast<std::size_t>(j) < c1_osize; ++j, ++i)
93 assert(*i == j);
94 }
95 {
96 typedef typename C::const_iterator CI;
97 typedef bidirectional_iterator<CI> BCI;
98 C c1 = c0;
99 std::size_t c1_osize = c1.size();
100 CI i = c1.insert(c1.begin() + P, BCI(c2.begin()), BCI(c2.end()));
101 assert(i == c1.begin() + P);
102 assert(c1.size() == c1_osize + c2.size());
103 assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
104 i = c1.begin();
105 for (int j = 0; j < P; ++j, ++i)
106 assert(*i == j);
107 for (int j = 0; static_cast<std::size_t>(j) < c2.size(); ++j, ++i)
108 assert(*i == j);
109 for (int j = P; static_cast<std::size_t>(j) < c1_osize; ++j, ++i)
110 assert(*i == j);
111 }
112}
113
114template <class C>
115void
116testN(int start, int N, int M)
117{
118 for (int i = 0; i <= 3; ++i)
119 {
120 if (0 <= i && i <= N)
121 {
122 C c1 = make<C>(N, start);
123 C c2 = make<C>(M);
124 test(i, c1, c2);
125 }
126 }
127 for (int i = M-1; i <= M+1; ++i)
128 {
129 if (0 <= i && i <= N)
130 {
131 C c1 = make<C>(N, start);
132 C c2 = make<C>(M);
133 test(i, c1, c2);
134 }
135 }
136 for (int i = N/2-1; i <= N/2+1; ++i)
137 {
138 if (0 <= i && i <= N)
139 {
140 C c1 = make<C>(N, start);
141 C c2 = make<C>(M);
142 test(i, c1, c2);
143 }
144 }
145 for (int i = N - M - 1; i <= N - M + 1; ++i)
146 {
147 if (0 <= i && i <= N)
148 {
149 C c1 = make<C>(N, start);
150 C c2 = make<C>(M);
151 test(i, c1, c2);
152 }
153 }
154 for (int i = N - M - 1; i <= N - M + 1; ++i)
155 {
156 if (0 <= i && i <= N)
157 {
158 C c1 = make<C>(N, start);
159 C c2 = make<C>(M);
160 test(i, c1, c2);
161 }
162 }
163 for (int i = N - 3; i <= N; ++i)
164 {
165 if (0 <= i && i <= N)
166 {
167 C c1 = make<C>(N, start);
168 C c2 = make<C>(M);
169 test(i, c1, c2);
170 }
171 }
172}
173
174template <class C>
175void
176testI(int P, C& c1, const C& c2)
177{
178 typedef typename C::const_iterator CI;
179 typedef cpp17_input_iterator<CI> ICI;
180 std::size_t c1_osize = c1.size();
181 CI i = c1.insert(c1.begin() + P, ICI(c2.begin()), ICI(c2.end()));
182 assert(i == c1.begin() + P);
183 assert(c1.size() == c1_osize + c2.size());
184 assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
185 LIBCPP_ASSERT(is_double_ended_contiguous_container_asan_correct(c1));
186 LIBCPP_ASSERT(is_double_ended_contiguous_container_asan_correct(c2));
187 i = c1.begin();
188 for (int j = 0; j < P; ++j, ++i)
189 assert(*i == j);
190 for (int j = 0; static_cast<std::size_t>(j) < c2.size(); ++j, ++i)
191 assert(*i == j);
192 for (int j = P; static_cast<std::size_t>(j) < c1_osize; ++j, ++i)
193 assert(*i == j);
194}
195
196template <class C>
197void
198testNI(int start, int N, int M)
199{
200 for (int i = 0; i <= 3; ++i)
201 {
202 if (0 <= i && i <= N)
203 {
204 C c1 = make<C>(N, start);
205 C c2 = make<C>(M);
206 testI(i, c1, c2);
207 }
208 }
209 for (int i = M-1; i <= M+1; ++i)
210 {
211 if (0 <= i && i <= N)
212 {
213 C c1 = make<C>(N, start);
214 C c2 = make<C>(M);
215 testI(i, c1, c2);
216 }
217 }
218 for (int i = N/2-1; i <= N/2+1; ++i)
219 {
220 if (0 <= i && i <= N)
221 {
222 C c1 = make<C>(N, start);
223 C c2 = make<C>(M);
224 testI(i, c1, c2);
225 }
226 }
227 for (int i = N - M - 1; i <= N - M + 1; ++i)
228 {
229 if (0 <= i && i <= N)
230 {
231 C c1 = make<C>(N, start);
232 C c2 = make<C>(M);
233 testI(i, c1, c2);
234 }
235 }
236 for (int i = N - 3; i <= N; ++i)
237 {
238 if (0 <= i && i <= N)
239 {
240 C c1 = make<C>(N, start);
241 C c2 = make<C>(M);
242 testI(i, c1, c2);
243 }
244 }
245}
246
247template <class C>
248void
249test_move()
250{
251#if TEST_STD_VER >= 11
252 C c;
253 typedef typename C::const_iterator CI;
254 {
255 MoveOnly mo(0);
256 typedef MoveOnly* I;
257 c.insert(c.end(), std::move_iterator<I>(&mo), std::move_iterator<I>(&mo+1));
258 }
259 int j = 0;
260 for (CI i = c.begin(); i != c.end(); ++i, (void) ++j)
261 assert(*i == MoveOnly(j));
262 {
263 MoveOnly mo(1);
264 typedef cpp17_input_iterator<MoveOnly*> I;
265 c.insert(c.end(), std::move_iterator<I>(I(&mo)), std::move_iterator<I>(I(&mo+1)));
266 }
267 j = 0;
268 for (CI i = c.begin(); i != c.end(); ++i, (void) ++j)
269 assert(*i == MoveOnly(j));
270#endif
271}
272
273int main(int, char**)
274{
275 {
276 int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};
277 const int N = sizeof(rng)/sizeof(rng[0]);
278 for (int i = 0; i < N; ++i)
279 for (int j = 0; j < N; ++j)
280 for (int k = 0; k < N; ++k)
281 testN<std::deque<int> >(start: rng[i], N: rng[j], M: rng[k]);
282 testNI<std::deque<int> >(start: 1500, N: 2000, M: 1000);
283#if TEST_STD_VER >= 11
284 test_move<std::deque<MoveOnly, limited_allocator<MoveOnly, 2000> > >();
285#endif
286 }
287#if TEST_STD_VER >= 11
288 {
289 int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};
290 const int N = sizeof(rng)/sizeof(rng[0]);
291 for (int i = 0; i < N; ++i)
292 for (int j = 0; j < N; ++j)
293 for (int k = 0; k < N; ++k)
294 testN<std::deque<int, min_allocator<int>> >(rng[i], rng[j], rng[k]);
295 testNI<std::deque<int> >(1500, 2000, 1000);
296 test_move<std::deque<MoveOnly, min_allocator<MoveOnly> > >();
297 }
298 {
299 int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};
300 const int N = sizeof(rng)/sizeof(rng[0]);
301 for (int i = 0; i < N; ++i)
302 for (int j = 0; j < N; ++j)
303 for (int k = 0; k < N; ++k)
304 testN<std::deque<int, safe_allocator<int>> >(rng[i], rng[j], rng[k]);
305 testNI<std::deque<int> >(1500, 2000, 1000);
306 test_move<std::deque<MoveOnly, safe_allocator<MoveOnly> > >();
307 }
308#endif
309
310 return 0;
311}
312

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