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
11 // <deque>
12
13 // iterator insert (const_iterator p, size_type n, const value_type& v);
14
15 #include "asan_testing.h"
16 #include <deque>
17 #include <cassert>
18 #include <cstddef>
19
20 #include "test_macros.h"
21 #include "min_allocator.h"
22
23 template <class C>
24 C
make(int size,int start=0)25 make(int size, int start = 0 )
26 {
27 const int b = 4096 / sizeof(int);
28 int init = 0;
29 if (start > 0)
30 {
31 init = (start+1) / b + ((start+1) % b != 0);
32 init *= b;
33 --init;
34 }
35 C c(init, 0);
36 for (int i = 0; i < init-start; ++i)
37 c.pop_back();
38 for (int i = 0; i < size; ++i)
39 c.push_back(i);
40 for (int i = 0; i < start; ++i)
41 c.pop_front();
42 return c;
43 }
44
45 template <class C>
46 void
test(int P,C & c1,int size,int x)47 test(int P, C& c1, int size, int x)
48 {
49 typedef typename C::const_iterator CI;
50 std::size_t c1_osize = c1.size();
51 CI i = c1.insert(c1.begin() + P, size, x);
52 assert(i == c1.begin() + P);
53 assert(c1.size() == c1_osize + size);
54 assert(static_cast<std::size_t>(std::distance(c1.begin(), c1.end())) == c1.size());
55 LIBCPP_ASSERT(is_double_ended_contiguous_container_asan_correct(c1));
56 i = c1.begin();
57 for (int j = 0; j < P; ++j, ++i)
58 assert(*i == j);
59 for (int j = 0; j < size; ++j, ++i)
60 assert(*i == x);
61 for (int j = P; static_cast<std::size_t>(j) < c1_osize; ++j, ++i)
62 assert(*i == j);
63 }
64
65 template <class C>
66 void
testN(int start,int N,int M)67 testN(int start, int N, int M)
68 {
69 for (int i = 0; i <= 3; ++i)
70 {
71 if (0 <= i && i <= N)
72 {
73 C c1 = make<C>(N, start);
74 test(i, c1, M, -10);
75 }
76 }
77 for (int i = M-1; i <= M+1; ++i)
78 {
79 if (0 <= i && i <= N)
80 {
81 C c1 = make<C>(N, start);
82 test(i, c1, M, -10);
83 }
84 }
85 for (int i = N/2-1; i <= N/2+1; ++i)
86 {
87 if (0 <= i && i <= N)
88 {
89 C c1 = make<C>(N, start);
90 test(i, c1, M, -10);
91 }
92 }
93 for (int i = N - M - 1; i <= N - M + 1; ++i)
94 {
95 if (0 <= i && i <= N)
96 {
97 C c1 = make<C>(N, start);
98 test(i, c1, M, -10);
99 }
100 }
101 for (int i = N - 3; i <= N; ++i)
102 {
103 if (0 <= i && i <= N)
104 {
105 C c1 = make<C>(N, start);
106 test(i, c1, M, -10);
107 }
108 }
109 }
110
111 template <class C>
112 void
self_reference_test()113 self_reference_test()
114 {
115 typedef typename C::const_iterator CI;
116 for (int i = 0; i < 20; ++i)
117 {
118 for (int j = 0; j < 20; ++j)
119 {
120 C c = make<C>(20);
121 CI it = c.cbegin() + i;
122 CI jt = c.cbegin() + j;
123 c.insert(it, 5, *jt);
124 assert(c.size() == 25);
125 assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
126 it = c.cbegin();
127 for (int k = 0; k < i; ++k, ++it)
128 assert(*it == k);
129 for (int k = 0; k < 5; ++k, ++it)
130 assert(*it == j);
131 for (int k = i; k < 20; ++k, ++it)
132 assert(*it == k);
133 }
134 }
135 }
136
main(int,char **)137 int main(int, char**)
138 {
139 {
140 int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};
141 const int N = sizeof(rng)/sizeof(rng[0]);
142 for (int i = 0; i < N; ++i)
143 for (int j = 0; j < N; ++j)
144 for (int k = 0; k < N; ++k)
145 testN<std::deque<int> >(rng[i], rng[j], rng[k]);
146 self_reference_test<std::deque<int> >();
147 }
148 #if TEST_STD_VER >= 11
149 {
150 int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};
151 const int N = sizeof(rng)/sizeof(rng[0]);
152 for (int i = 0; i < N; ++i)
153 for (int j = 0; j < N; ++j)
154 for (int k = 0; k < N; ++k)
155 testN<std::deque<int, min_allocator<int>> >(rng[i], rng[j], rng[k]);
156 self_reference_test<std::deque<int, min_allocator<int>> >();
157 }
158 {
159 int rng[] = {0, 1, 2, 3, 1023, 1024, 1025, 2047, 2048, 2049};
160 const int N = sizeof(rng)/sizeof(rng[0]);
161 for (int i = 0; i < N; ++i)
162 for (int j = 0; j < N; ++j)
163 for (int k = 0; k < N; ++k)
164 testN<std::deque<int, safe_allocator<int>> >(rng[i], rng[j], rng[k]);
165 self_reference_test<std::deque<int, safe_allocator<int>> >();
166 }
167 #endif
168
169 return 0;
170 }
171