1 // Copyright 2018 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #ifndef ABSL_CONTAINER_INTERNAL_TEST_ALLOCATOR_H_
16 #define ABSL_CONTAINER_INTERNAL_TEST_ALLOCATOR_H_
17
18 #include <cassert>
19 #include <cstddef>
20 #include <cstdint>
21 #include <memory>
22 #include <type_traits>
23
24 #include "gtest/gtest.h"
25 #include "absl/base/config.h"
26
27 namespace absl {
28 ABSL_NAMESPACE_BEGIN
29 namespace container_internal {
30
31 // This is a stateful allocator, but the state lives outside of the
32 // allocator (in whatever test is using the allocator). This is odd
33 // but helps in tests where the allocator is propagated into nested
34 // containers - that chain of allocators uses the same state and is
35 // thus easier to query for aggregate allocation information.
36 template <typename T>
37 class CountingAllocator {
38 public:
39 using Allocator = std::allocator<T>;
40 using AllocatorTraits = std::allocator_traits<Allocator>;
41 using value_type = typename AllocatorTraits::value_type;
42 using pointer = typename AllocatorTraits::pointer;
43 using const_pointer = typename AllocatorTraits::const_pointer;
44 using size_type = typename AllocatorTraits::size_type;
45 using difference_type = typename AllocatorTraits::difference_type;
46
47 CountingAllocator() = default;
CountingAllocator(int64_t * bytes_used)48 explicit CountingAllocator(int64_t* bytes_used) : bytes_used_(bytes_used) {}
CountingAllocator(int64_t * bytes_used,int64_t * instance_count)49 CountingAllocator(int64_t* bytes_used, int64_t* instance_count)
50 : bytes_used_(bytes_used), instance_count_(instance_count) {}
51
52 template <typename U>
CountingAllocator(const CountingAllocator<U> & x)53 CountingAllocator(const CountingAllocator<U>& x)
54 : bytes_used_(x.bytes_used_), instance_count_(x.instance_count_) {}
55
56 pointer allocate(
57 size_type n,
58 typename AllocatorTraits::const_void_pointer hint = nullptr) {
59 Allocator allocator;
60 pointer ptr = AllocatorTraits::allocate(allocator, n, hint);
61 if (bytes_used_ != nullptr) {
62 *bytes_used_ += n * sizeof(T);
63 }
64 return ptr;
65 }
66
deallocate(pointer p,size_type n)67 void deallocate(pointer p, size_type n) {
68 Allocator allocator;
69 AllocatorTraits::deallocate(allocator, p, n);
70 if (bytes_used_ != nullptr) {
71 *bytes_used_ -= n * sizeof(T);
72 }
73 }
74
75 template <typename U, typename... Args>
construct(U * p,Args &&...args)76 void construct(U* p, Args&&... args) {
77 Allocator allocator;
78 AllocatorTraits::construct(allocator, p, std::forward<Args>(args)...);
79 if (instance_count_ != nullptr) {
80 *instance_count_ += 1;
81 }
82 }
83
84 template <typename U>
destroy(U * p)85 void destroy(U* p) {
86 Allocator allocator;
87 // Ignore GCC warning bug.
88 #if ABSL_INTERNAL_HAVE_MIN_GNUC_VERSION(12, 0)
89 #pragma GCC diagnostic push
90 #pragma GCC diagnostic ignored "-Wuse-after-free"
91 #endif
92 AllocatorTraits::destroy(allocator, p);
93 #if ABSL_INTERNAL_HAVE_MIN_GNUC_VERSION(12, 0)
94 #pragma GCC diagnostic pop
95 #endif
96 if (instance_count_ != nullptr) {
97 *instance_count_ -= 1;
98 }
99 }
100
101 template <typename U>
102 class rebind {
103 public:
104 using other = CountingAllocator<U>;
105 };
106
107 friend bool operator==(const CountingAllocator& a,
108 const CountingAllocator& b) {
109 return a.bytes_used_ == b.bytes_used_ &&
110 a.instance_count_ == b.instance_count_;
111 }
112
113 friend bool operator!=(const CountingAllocator& a,
114 const CountingAllocator& b) {
115 return !(a == b);
116 }
117
118 int64_t* bytes_used_ = nullptr;
119 int64_t* instance_count_ = nullptr;
120 };
121
122 template <typename T>
123 struct CopyAssignPropagatingCountingAlloc : public CountingAllocator<T> {
124 using propagate_on_container_copy_assignment = std::true_type;
125
126 using Base = CountingAllocator<T>;
127 using Base::Base;
128
129 template <typename U>
CopyAssignPropagatingCountingAllocCopyAssignPropagatingCountingAlloc130 explicit CopyAssignPropagatingCountingAlloc(
131 const CopyAssignPropagatingCountingAlloc<U>& other)
132 : Base(other.bytes_used_, other.instance_count_) {}
133
134 template <typename U>
135 struct rebind {
136 using other = CopyAssignPropagatingCountingAlloc<U>;
137 };
138 };
139
140 template <typename T>
141 struct MoveAssignPropagatingCountingAlloc : public CountingAllocator<T> {
142 using propagate_on_container_move_assignment = std::true_type;
143
144 using Base = CountingAllocator<T>;
145 using Base::Base;
146
147 template <typename U>
MoveAssignPropagatingCountingAllocMoveAssignPropagatingCountingAlloc148 explicit MoveAssignPropagatingCountingAlloc(
149 const MoveAssignPropagatingCountingAlloc<U>& other)
150 : Base(other.bytes_used_, other.instance_count_) {}
151
152 template <typename U>
153 struct rebind {
154 using other = MoveAssignPropagatingCountingAlloc<U>;
155 };
156 };
157
158 template <typename T>
159 struct SwapPropagatingCountingAlloc : public CountingAllocator<T> {
160 using propagate_on_container_swap = std::true_type;
161
162 using Base = CountingAllocator<T>;
163 using Base::Base;
164
165 template <typename U>
SwapPropagatingCountingAllocSwapPropagatingCountingAlloc166 explicit SwapPropagatingCountingAlloc(
167 const SwapPropagatingCountingAlloc<U>& other)
168 : Base(other.bytes_used_, other.instance_count_) {}
169
170 template <typename U>
171 struct rebind {
172 using other = SwapPropagatingCountingAlloc<U>;
173 };
174 };
175
176 // Tries to allocate memory at the minimum alignment even when the default
177 // allocator uses a higher alignment.
178 template <typename T>
179 struct MinimumAlignmentAlloc : std::allocator<T> {
180 MinimumAlignmentAlloc() = default;
181
182 template <typename U>
MinimumAlignmentAllocMinimumAlignmentAlloc183 explicit MinimumAlignmentAlloc(const MinimumAlignmentAlloc<U>& /*other*/) {}
184
185 template <class U>
186 struct rebind {
187 using other = MinimumAlignmentAlloc<U>;
188 };
189
allocateMinimumAlignmentAlloc190 T* allocate(size_t n) {
191 T* ptr = std::allocator<T>::allocate(n + 1);
192 char* cptr = reinterpret_cast<char*>(ptr);
193 cptr += alignof(T);
194 return reinterpret_cast<T*>(cptr);
195 }
196
deallocateMinimumAlignmentAlloc197 void deallocate(T* ptr, size_t n) {
198 char* cptr = reinterpret_cast<char*>(ptr);
199 cptr -= alignof(T);
200 std::allocator<T>::deallocate(reinterpret_cast<T*>(cptr), n + 1);
201 }
202 };
203
IsAssertEnabled()204 inline bool IsAssertEnabled() {
205 // Use an assert with side-effects to figure out if they are actually enabled.
206 bool assert_enabled = false;
207 assert([&]() { // NOLINT
208 assert_enabled = true;
209 return true;
210 }());
211 return assert_enabled;
212 }
213
214 template <template <class Alloc> class Container>
TestCopyAssignAllocPropagation()215 void TestCopyAssignAllocPropagation() {
216 int64_t bytes1 = 0, instances1 = 0, bytes2 = 0, instances2 = 0;
217 CopyAssignPropagatingCountingAlloc<int> allocator1(&bytes1, &instances1);
218 CopyAssignPropagatingCountingAlloc<int> allocator2(&bytes2, &instances2);
219
220 // Test propagating allocator_type.
221 {
222 Container<CopyAssignPropagatingCountingAlloc<int>> c1(allocator1);
223 Container<CopyAssignPropagatingCountingAlloc<int>> c2(allocator2);
224
225 for (int i = 0; i < 100; ++i) c1.insert(i);
226
227 EXPECT_NE(c2.get_allocator(), allocator1);
228 EXPECT_EQ(instances1, 100);
229 EXPECT_EQ(instances2, 0);
230
231 c2 = c1;
232
233 EXPECT_EQ(c2.get_allocator(), allocator1);
234 EXPECT_EQ(instances1, 200);
235 EXPECT_EQ(instances2, 0);
236 }
237 // Test non-propagating allocator_type with different allocators.
238 {
239 Container<CountingAllocator<int>> c1(allocator1), c2(allocator2);
240
241 for (int i = 0; i < 100; ++i) c1.insert(i);
242
243 EXPECT_EQ(c2.get_allocator(), allocator2);
244 EXPECT_EQ(instances1, 100);
245 EXPECT_EQ(instances2, 0);
246
247 c2 = c1;
248
249 EXPECT_EQ(c2.get_allocator(), allocator2);
250 EXPECT_EQ(instances1, 100);
251 EXPECT_EQ(instances2, 100);
252 }
253 EXPECT_EQ(bytes1, 0);
254 EXPECT_EQ(instances1, 0);
255 EXPECT_EQ(bytes2, 0);
256 EXPECT_EQ(instances2, 0);
257 }
258
259 template <template <class Alloc> class Container>
TestMoveAssignAllocPropagation()260 void TestMoveAssignAllocPropagation() {
261 int64_t bytes1 = 0, instances1 = 0, bytes2 = 0, instances2 = 0;
262 MoveAssignPropagatingCountingAlloc<int> allocator1(&bytes1, &instances1);
263 MoveAssignPropagatingCountingAlloc<int> allocator2(&bytes2, &instances2);
264
265 // Test propagating allocator_type.
266 {
267 Container<MoveAssignPropagatingCountingAlloc<int>> c1(allocator1);
268 Container<MoveAssignPropagatingCountingAlloc<int>> c2(allocator2);
269
270 for (int i = 0; i < 100; ++i) c1.insert(i);
271
272 EXPECT_NE(c2.get_allocator(), allocator1);
273 EXPECT_EQ(instances1, 100);
274 EXPECT_EQ(instances2, 0);
275
276 c2 = std::move(c1);
277
278 EXPECT_EQ(c2.get_allocator(), allocator1);
279 EXPECT_EQ(instances1, 100);
280 EXPECT_EQ(instances2, 0);
281 }
282 // Test non-propagating allocator_type with equal allocators.
283 {
284 Container<CountingAllocator<int>> c1(allocator1), c2(allocator1);
285
286 for (int i = 0; i < 100; ++i) c1.insert(i);
287
288 EXPECT_EQ(c2.get_allocator(), allocator1);
289 EXPECT_EQ(instances1, 100);
290 EXPECT_EQ(instances2, 0);
291
292 c2 = std::move(c1);
293
294 EXPECT_EQ(c2.get_allocator(), allocator1);
295 EXPECT_EQ(instances1, 100);
296 EXPECT_EQ(instances2, 0);
297 }
298 // Test non-propagating allocator_type with different allocators.
299 {
300 Container<CountingAllocator<int>> c1(allocator1), c2(allocator2);
301
302 for (int i = 0; i < 100; ++i) c1.insert(i);
303
304 EXPECT_NE(c2.get_allocator(), allocator1);
305 EXPECT_EQ(instances1, 100);
306 EXPECT_EQ(instances2, 0);
307
308 c2 = std::move(c1);
309
310 EXPECT_EQ(c2.get_allocator(), allocator2);
311 EXPECT_LE(instances1, 100); // The values in c1 may or may not have been
312 // destroyed at this point.
313 EXPECT_EQ(instances2, 100);
314 }
315 EXPECT_EQ(bytes1, 0);
316 EXPECT_EQ(instances1, 0);
317 EXPECT_EQ(bytes2, 0);
318 EXPECT_EQ(instances2, 0);
319 }
320
321 template <template <class Alloc> class Container>
TestSwapAllocPropagation()322 void TestSwapAllocPropagation() {
323 int64_t bytes1 = 0, instances1 = 0, bytes2 = 0, instances2 = 0;
324 SwapPropagatingCountingAlloc<int> allocator1(&bytes1, &instances1);
325 SwapPropagatingCountingAlloc<int> allocator2(&bytes2, &instances2);
326
327 // Test propagating allocator_type.
328 {
329 Container<SwapPropagatingCountingAlloc<int>> c1(allocator1), c2(allocator2);
330
331 for (int i = 0; i < 100; ++i) c1.insert(i);
332
333 EXPECT_NE(c2.get_allocator(), allocator1);
334 EXPECT_EQ(instances1, 100);
335 EXPECT_EQ(instances2, 0);
336
337 c2.swap(c1);
338
339 EXPECT_EQ(c2.get_allocator(), allocator1);
340 EXPECT_EQ(instances1, 100);
341 EXPECT_EQ(instances2, 0);
342 }
343 // Test non-propagating allocator_type with equal allocators.
344 {
345 Container<CountingAllocator<int>> c1(allocator1), c2(allocator1);
346
347 for (int i = 0; i < 100; ++i) c1.insert(i);
348
349 EXPECT_EQ(c2.get_allocator(), allocator1);
350 EXPECT_EQ(instances1, 100);
351 EXPECT_EQ(instances2, 0);
352
353 c2.swap(c1);
354
355 EXPECT_EQ(c2.get_allocator(), allocator1);
356 EXPECT_EQ(instances1, 100);
357 EXPECT_EQ(instances2, 0);
358 }
359 // Test non-propagating allocator_type with different allocators.
360 {
361 Container<CountingAllocator<int>> c1(allocator1), c2(allocator2);
362
363 for (int i = 0; i < 100; ++i) c1.insert(i);
364
365 EXPECT_NE(c1.get_allocator(), c2.get_allocator());
366 if (IsAssertEnabled()) {
367 EXPECT_DEATH_IF_SUPPORTED(c2.swap(c1), "");
368 }
369 }
370 EXPECT_EQ(bytes1, 0);
371 EXPECT_EQ(instances1, 0);
372 EXPECT_EQ(bytes2, 0);
373 EXPECT_EQ(instances2, 0);
374 }
375
376 template <template <class Alloc> class Container>
TestAllocPropagation()377 void TestAllocPropagation() {
378 TestCopyAssignAllocPropagation<Container>();
379 TestMoveAssignAllocPropagation<Container>();
380 TestSwapAllocPropagation<Container>();
381 }
382
383 } // namespace container_internal
384 ABSL_NAMESPACE_END
385 } // namespace absl
386
387 #endif // ABSL_CONTAINER_INTERNAL_TEST_ALLOCATOR_H_
388