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