xref: /llvm-project/libcxx/test/std/containers/sequences/deque/deque.modifiers/insert_iter_iter.pass.cpp (revision f376a3bba1900942f75092a7c2ea100a28e7cbac) 
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 
33 template <class C>
34 C
make(int size,int start=0)35 make(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 
55 template <class C>
56 void
test(int P,const C & c0,const C & c2)57 test(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 
114 template <class C>
115 void
testN(int start,int N,int M)116 testN(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 
174 template <class C>
175 void
testI(int P,C & c1,const C & c2)176 testI(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 
196 template <class C>
197 void
testNI(int start,int N,int M)198 testNI(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 
247 template <class C>
248 void
test_move()249 test_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 
main(int,char **)273 int 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> >(rng[i], rng[j], rng[k]);
282     testNI<std::deque<int> >(1500, 2000, 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