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 // UNSUPPORTED: c++03
10
11 // <deque>
12
13 // Test how deque manages the spare blocks it keeps. The exact values it tests
14 // for are not always important, but are sometimes needed to ensure the container
15 // resizes or shrinks at the correct time.
16
17 #include <deque>
18 #include <cassert>
19 #include <cstdio>
20 #include <memory>
21 #include <queue>
22 #include <stack>
23 #include <string>
24
25 #include "min_allocator.h"
26 #include "assert_macros.h"
27
28 template <class Adaptor>
29 struct ContainerAdaptor : public Adaptor {
30 using Adaptor::Adaptor;
GetContainerContainerAdaptor31 typename Adaptor::container_type& GetContainer() { return Adaptor::c; }
32 };
33
34 template <class Deque>
print(const Deque & d)35 static void print(const Deque& d) {
36 std::printf("%zu : __front_spare() == %zu"
37 " : __back_spare() == %zu"
38 " : __capacity() == %zu"
39 " : bytes allocated == %zu\n",
40 d.size(), d.__front_spare(), d.__back_spare(), d.__capacity(),
41 malloc_allocator_base::outstanding_bytes);
42 }
43
44 template <class T>
45 using Deque = std::deque<T, malloc_allocator<T> >;
46
47 template <class T>
48 using BlockSize = std::__deque_block_size<T, std::ptrdiff_t>;
49
50 struct LargeT {
51 LargeT() = default;
52 char buff[256] = {};
53 };
54 static_assert(BlockSize<LargeT>::value == 16, "");
55
56 const auto& AllocBytes = malloc_allocator_base::outstanding_bytes;
57
58 template <class Deque>
59 struct PrintOnFailure {
PrintOnFailurePrintOnFailure60 explicit PrintOnFailure(Deque const& deque) : deque_(&deque) {}
operator ()PrintOnFailure61 void operator()() const { print(*deque_); }
62 private:
63 const Deque* deque_;
64
65 PrintOnFailure(PrintOnFailure const&) = delete;
66 };
67
68
push_back()69 static void push_back() {
70 const auto BS = BlockSize<LargeT>::value;
71 std::unique_ptr<Deque<LargeT>> dp(new Deque<LargeT>);
72 auto& d = *dp;
73 PrintOnFailure<Deque<LargeT>> on_fail(d);
74
75 // Test nothing is allocated after default construction.
76 {
77 TEST_REQUIRE(d.size() == 0, on_fail);
78 TEST_REQUIRE(d.__capacity() == 0, on_fail);
79 TEST_REQUIRE(d.__block_count() == 0, on_fail);
80 }
81 // First push back allocates one block.
82 d.push_back({});
83 {
84 TEST_REQUIRE(d.size() == 1, on_fail);
85 TEST_REQUIRE(d.__front_spare() == 0, on_fail);
86 TEST_REQUIRE(d.__back_spare() == 14, on_fail);
87 TEST_REQUIRE(d.__back_spare_blocks() == 0, on_fail);
88 TEST_REQUIRE(d.__capacity() == BS - 1, on_fail);
89 TEST_REQUIRE(d.__block_count() == 1, on_fail);
90 }
91
92 d.push_back({});
93 {
94 TEST_REQUIRE(d.size() == 2, on_fail);
95 TEST_REQUIRE(d.__front_spare() == 0, on_fail);
96 TEST_REQUIRE(d.__back_spare() == 13, on_fail);
97 TEST_REQUIRE(d.__back_spare_blocks() == 0, on_fail);
98 }
99 // Push back until we need a new block.
100 for (int RemainingCap = d.__capacity() - d.size(); RemainingCap >= 0; --RemainingCap)
101 d.push_back({});
102 {
103 TEST_REQUIRE(d.__block_count() == 2, on_fail);
104 TEST_REQUIRE(d.__front_spare_blocks() == 0, on_fail);
105 TEST_REQUIRE(d.__back_spare_blocks() == 0, on_fail);
106 TEST_REQUIRE(d.__back_spare() == 15, on_fail);
107 }
108
109 // Remove the only element in the new block. Test that we keep the empty
110 // block as a spare.
111 d.pop_back();
112 {
113 TEST_REQUIRE(d.__block_count() == 2, on_fail);
114 TEST_REQUIRE(d.__front_spare_blocks() == 0, on_fail);
115 TEST_REQUIRE(d.__back_spare_blocks() == 1, on_fail);
116 TEST_REQUIRE(d.__back_spare() == 16, on_fail);
117 }
118
119 // Pop back again, keep the spare.
120 d.pop_back();
121 {
122 TEST_REQUIRE(d.__block_count() == 2, on_fail);
123 TEST_REQUIRE(d.__front_spare() == 0, on_fail);
124 TEST_REQUIRE(d.__back_spare() == 17, on_fail);
125 TEST_REQUIRE(d.__back_spare_blocks() == 1, on_fail);
126 }
127
128 dp.reset();
129 TEST_REQUIRE(AllocBytes == 0, on_fail);
130 }
131
push_front()132 static void push_front() {
133 std::unique_ptr<Deque<LargeT>> dp(new Deque<LargeT>);
134 auto& d = *dp;
135 PrintOnFailure<Deque<LargeT>> on_fail(d);
136
137 // Test nothing is allocated after default construction.
138 {
139 TEST_REQUIRE(d.size() == 0, on_fail);
140 TEST_REQUIRE(d.__capacity() == 0, on_fail);
141 TEST_REQUIRE(d.__block_count() == 0, on_fail);
142 }
143 // First push front allocates one block, and we start the sequence in the
144 // middle.
145 d.push_front({});
146 {
147 TEST_REQUIRE(d.size() == 1, on_fail);
148 TEST_REQUIRE(d.__front_spare() == 7, on_fail);
149 TEST_REQUIRE(d.__back_spare() == 7, on_fail);
150 TEST_REQUIRE(d.__front_spare_blocks() == 0, on_fail);
151 TEST_REQUIRE(d.__back_spare_blocks() == 0, on_fail);
152 TEST_REQUIRE(d.__block_count() == 1, on_fail);
153 }
154
155 d.push_front({});
156 {
157 TEST_REQUIRE(d.size() == 2, on_fail);
158 TEST_REQUIRE(d.__front_spare() == 6, on_fail);
159 TEST_REQUIRE(d.__back_spare() == 7, on_fail);
160 TEST_REQUIRE(d.__front_spare_blocks() == 0, on_fail);
161 TEST_REQUIRE(d.__back_spare_blocks() == 0, on_fail);
162 }
163 // Push front until we need a new block.
164 for (int RemainingCap = d.__front_spare(); RemainingCap >= 0; --RemainingCap)
165 d.push_front({});
166 {
167 TEST_REQUIRE(d.__block_count() == 2, on_fail);
168 TEST_REQUIRE(d.__front_spare() == 15, on_fail);
169 TEST_REQUIRE(d.__back_spare() == 7, on_fail);
170 TEST_REQUIRE(d.__front_spare_blocks() == 0, on_fail);
171 TEST_REQUIRE(d.__back_spare_blocks() == 0, on_fail);
172 }
173
174 // Remove the only element in the new block. Test that we keep the empty
175 // block as a spare.
176 d.pop_front();
177 {
178 TEST_REQUIRE(d.__block_count() == 2, on_fail);
179 TEST_REQUIRE(d.__front_spare_blocks() == 1, on_fail);
180 TEST_REQUIRE(d.__back_spare_blocks() == 0, on_fail);
181 TEST_REQUIRE(d.__back_spare() == 7, on_fail);
182 }
183
184 // Pop back again, keep the spare.
185 d.pop_front();
186 {
187 TEST_REQUIRE(d.__block_count() == 2, on_fail);
188 TEST_REQUIRE(d.__front_spare_blocks() == 1, on_fail);
189 TEST_REQUIRE(d.__back_spare() == 7, on_fail);
190 }
191
192 dp.reset();
193 TEST_REQUIRE(AllocBytes == 0, on_fail);
194 }
195
std_queue()196 static void std_queue() {
197 using D = Deque<LargeT>;
198 using Queue = std::queue<LargeT, D>;
199 ContainerAdaptor<Queue> CA;
200 const D& d = CA.GetContainer();
201 Queue &q = CA;
202 PrintOnFailure<Deque<LargeT>> on_fail(d);
203
204 while (d.__block_count() < 4)
205 q.push({});
206 {
207 TEST_REQUIRE(d.__block_count() == 4, on_fail);
208 TEST_REQUIRE(d.__front_spare() == 0, on_fail);
209 TEST_REQUIRE(d.__back_spare() == 15, on_fail);
210 TEST_REQUIRE(d.__back_spare_blocks() == 0, on_fail);
211 }
212 while (d.__back_spare()) {
213 q.push({});
214 }
215 {
216 TEST_REQUIRE(d.__block_count() == 4, on_fail);
217 TEST_REQUIRE(d.__front_spare() == 0, on_fail);
218 TEST_REQUIRE(d.__back_spare() == 0, on_fail);
219 }
220 q.pop();
221 {
222 TEST_REQUIRE(d.__block_count() == 4, on_fail);
223 TEST_REQUIRE(d.__front_spare() == 1, on_fail);
224 TEST_REQUIRE(d.__back_spare() == 0, on_fail);
225 }
226
227 // Pop until we create a spare block at the front.
228 while (d.__front_spare() <= 15)
229 q.pop();
230
231 {
232 TEST_REQUIRE(d.__block_count() == 4, on_fail);
233 TEST_REQUIRE(d.__front_spare_blocks() == 1, on_fail);
234 TEST_REQUIRE(d.__front_spare() == 16, on_fail);
235 TEST_REQUIRE(d.__back_spare() == 0, on_fail);
236 }
237
238 // Push at the end -- should re-use new spare block at front
239 q.push({});
240
241 {
242 TEST_REQUIRE(d.__block_count() == 4, on_fail);
243 TEST_REQUIRE(d.__front_spare_blocks() == 0, on_fail);
244 TEST_REQUIRE(d.__front_spare() == 0, on_fail);
245 TEST_REQUIRE(d.__back_spare() == 15, on_fail);
246 }
247 while (!q.empty()) {
248 q.pop();
249 TEST_REQUIRE(d.__front_spare_blocks() + d.__back_spare_blocks() <= 2, on_fail);
250 }
251
252 // The empty state has two blocks
253 {
254 TEST_REQUIRE(d.__front_spare() == 16, on_fail);
255 TEST_REQUIRE(d.__back_spare() == 15, on_fail);
256 TEST_REQUIRE(d.__capacity() == 31, on_fail);
257 }
258 }
259
pop_front_push_back()260 static void pop_front_push_back() {
261 Deque<char> d(32 * 1024, 'a');
262 bool take_from_front = true;
263 while (d.size() > 0) {
264 if (take_from_front) {
265 d.pop_front();
266 take_from_front = false;
267 } else {
268 d.pop_back();
269 take_from_front = true;
270 }
271 if (d.size() % 1000 == 0 || d.size() < 50) {
272 print(d);
273 }
274 }
275 }
276
main(int,char **)277 int main(int, char**) {
278 push_back();
279 push_front();
280 std_queue();
281 pop_front_push_back();
282
283 return 0;
284 }
285