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 #ifndef TEST_ALLOCATOR_H
10 #define TEST_ALLOCATOR_H
11
12 #include <type_traits>
13 #include <new>
14 #include <memory>
15 #include <utility>
16 #include <cstddef>
17 #include <cstdlib>
18 #include <climits>
19 #include <cassert>
20
21 #include "test_macros.h"
22
23 template <class Alloc>
alloc_max_size(Alloc const & a)24 TEST_CONSTEXPR_CXX20 inline typename std::allocator_traits<Alloc>::size_type alloc_max_size(Alloc const& a) {
25 typedef std::allocator_traits<Alloc> AT;
26 return AT::max_size(a);
27 }
28
29 struct test_allocator_statistics {
30 int time_to_throw = 0;
31 int throw_after = INT_MAX;
32 int count = 0; // the number of active instances
33 int alloc_count = 0; // the number of allocations not deallocating
34 int allocated_size = 0; // the size of allocated elements
35 int construct_count = 0; // the number of times that ::construct was called
36 int destroy_count = 0; // the number of times that ::destroy was called
37 int copied = 0;
38 int moved = 0;
39 int converted = 0;
40
cleartest_allocator_statistics41 TEST_CONSTEXPR_CXX14 void clear() {
42 assert(count == 0 && "clearing leaking allocator data?");
43 count = 0;
44 time_to_throw = 0;
45 alloc_count = 0;
46 allocated_size = 0;
47 construct_count = 0;
48 destroy_count = 0;
49 throw_after = INT_MAX;
50 clear_ctor_counters();
51 }
52
clear_ctor_counterstest_allocator_statistics53 TEST_CONSTEXPR_CXX14 void clear_ctor_counters() {
54 copied = 0;
55 moved = 0;
56 converted = 0;
57 }
58 };
59
60 struct test_alloc_base {
61 TEST_CONSTEXPR static const int destructed_value = -1;
62 TEST_CONSTEXPR static const int moved_value = INT_MAX;
63 };
64
65 template <class T>
66 class test_allocator {
67 int data_ = 0; // participates in equality
68 int id_ = 0; // unique identifier, doesn't participate in equality
69 test_allocator_statistics* stats_ = nullptr;
70
71 template <class U>
72 friend class test_allocator;
73
74 public:
75 typedef unsigned size_type;
76 typedef int difference_type;
77 typedef T value_type;
78 typedef value_type* pointer;
79 typedef const value_type* const_pointer;
80 typedef typename std::add_lvalue_reference<value_type>::type reference;
81 typedef typename std::add_lvalue_reference<const value_type>::type const_reference;
82
83 template <class U>
84 struct rebind {
85 typedef test_allocator<U> other;
86 };
87
88 TEST_CONSTEXPR test_allocator() TEST_NOEXCEPT = default;
89
test_allocator(test_allocator_statistics * stats)90 TEST_CONSTEXPR_CXX14 explicit test_allocator(test_allocator_statistics* stats) TEST_NOEXCEPT : stats_(stats) {
91 if (stats_ != nullptr)
92 ++stats_->count;
93 }
94
test_allocator(int data)95 TEST_CONSTEXPR explicit test_allocator(int data) TEST_NOEXCEPT : data_(data) {}
96
test_allocator(int data,test_allocator_statistics * stats)97 TEST_CONSTEXPR_CXX14 explicit test_allocator(int data, test_allocator_statistics* stats) TEST_NOEXCEPT
98 : data_(data), stats_(stats) {
99 if (stats != nullptr)
100 ++stats_->count;
101 }
102
test_allocator(int data,int id)103 TEST_CONSTEXPR explicit test_allocator(int data, int id) TEST_NOEXCEPT : data_(data), id_(id) {}
104
test_allocator(int data,int id,test_allocator_statistics * stats)105 TEST_CONSTEXPR_CXX14 explicit test_allocator(int data, int id, test_allocator_statistics* stats) TEST_NOEXCEPT
106 : data_(data), id_(id), stats_(stats) {
107 if (stats_ != nullptr)
108 ++stats_->count;
109 }
110
test_allocator(const test_allocator & a)111 TEST_CONSTEXPR_CXX14 test_allocator(const test_allocator& a) TEST_NOEXCEPT
112 : data_(a.data_), id_(a.id_), stats_(a.stats_) {
113 assert(a.data_ != test_alloc_base::destructed_value && a.id_ != test_alloc_base::destructed_value &&
114 "copying from destroyed allocator");
115 if (stats_ != nullptr) {
116 ++stats_->count;
117 ++stats_->copied;
118 }
119 }
120
test_allocator(test_allocator && a)121 TEST_CONSTEXPR_CXX14 test_allocator(test_allocator&& a) TEST_NOEXCEPT : data_(a.data_), id_(a.id_), stats_(a.stats_) {
122 if (stats_ != nullptr) {
123 ++stats_->count;
124 ++stats_->moved;
125 }
126 assert(a.data_ != test_alloc_base::destructed_value && a.id_ != test_alloc_base::destructed_value &&
127 "moving from destroyed allocator");
128 a.data_ = test_alloc_base::moved_value;
129 a.id_ = test_alloc_base::moved_value;
130 }
131
132 template <class U>
test_allocator(const test_allocator<U> & a)133 TEST_CONSTEXPR_CXX14 test_allocator(const test_allocator<U>& a) TEST_NOEXCEPT
134 : data_(a.data_), id_(a.id_), stats_(a.stats_) {
135 if (stats_ != nullptr) {
136 ++stats_->count;
137 ++stats_->converted;
138 }
139 }
140
~test_allocator()141 TEST_CONSTEXPR_CXX20 ~test_allocator() TEST_NOEXCEPT {
142 assert(data_ != test_alloc_base::destructed_value);
143 assert(id_ != test_alloc_base::destructed_value);
144 if (stats_ != nullptr)
145 --stats_->count;
146 data_ = test_alloc_base::destructed_value;
147 id_ = test_alloc_base::destructed_value;
148 }
149
address(reference x)150 TEST_CONSTEXPR pointer address(reference x) const { return &x; }
address(const_reference x)151 TEST_CONSTEXPR const_pointer address(const_reference x) const { return &x; }
152
153 TEST_CONSTEXPR_CXX14 pointer allocate(size_type n, const void* = nullptr) {
154 assert(data_ != test_alloc_base::destructed_value);
155 if (stats_ != nullptr) {
156 if (stats_->time_to_throw >= stats_->throw_after)
157 TEST_THROW(std::bad_alloc());
158 ++stats_->time_to_throw;
159 ++stats_->alloc_count;
160 stats_->allocated_size += n;
161 }
162 return std::allocator<value_type>().allocate(n);
163 }
164
deallocate(pointer p,size_type s)165 TEST_CONSTEXPR_CXX14 void deallocate(pointer p, size_type s) {
166 assert(data_ != test_alloc_base::destructed_value);
167 if (stats_ != nullptr) {
168 --stats_->alloc_count;
169 stats_->allocated_size -= s;
170 }
171 std::allocator<value_type>().deallocate(p, s);
172 }
173
max_size()174 TEST_CONSTEXPR size_type max_size() const TEST_NOEXCEPT { return UINT_MAX / sizeof(T); }
175
176 template <class U>
construct(pointer p,U && val)177 TEST_CONSTEXPR_CXX20 void construct(pointer p, U&& val) {
178 if (stats_ != nullptr)
179 ++stats_->construct_count;
180 #if TEST_STD_VER > 17
181 std::construct_at(std::to_address(p), std::forward<U>(val));
182 #else
183 ::new (static_cast<void*>(p)) T(std::forward<U>(val));
184 #endif
185 }
186
destroy(pointer p)187 TEST_CONSTEXPR_CXX14 void destroy(pointer p) {
188 if (stats_ != nullptr)
189 ++stats_->destroy_count;
190 p->~T();
191 }
192 TEST_CONSTEXPR friend bool operator==(const test_allocator& x, const test_allocator& y) { return x.data_ == y.data_; }
193 TEST_CONSTEXPR friend bool operator!=(const test_allocator& x, const test_allocator& y) { return !(x == y); }
194
get_data()195 TEST_CONSTEXPR int get_data() const { return data_; }
get_id()196 TEST_CONSTEXPR int get_id() const { return id_; }
197 };
198
199 template <>
200 class test_allocator<void> {
201 int data_ = 0;
202 int id_ = 0;
203 test_allocator_statistics* stats_ = nullptr;
204
205 template <class U>
206 friend class test_allocator;
207
208 public:
209 typedef unsigned size_type;
210 typedef int difference_type;
211 typedef void value_type;
212 typedef value_type* pointer;
213 typedef const value_type* const_pointer;
214
215 template <class U>
216 struct rebind {
217 typedef test_allocator<U> other;
218 };
219
220 TEST_CONSTEXPR test_allocator() TEST_NOEXCEPT = default;
221
test_allocator(test_allocator_statistics * stats)222 TEST_CONSTEXPR_CXX14 explicit test_allocator(test_allocator_statistics* stats) TEST_NOEXCEPT : stats_(stats) {}
223
test_allocator(int data)224 TEST_CONSTEXPR explicit test_allocator(int data) TEST_NOEXCEPT : data_(data) {}
225
test_allocator(int data,test_allocator_statistics * stats)226 TEST_CONSTEXPR explicit test_allocator(int data, test_allocator_statistics* stats) TEST_NOEXCEPT
227 : data_(data), stats_(stats)
228 {}
229
test_allocator(int data,int id)230 TEST_CONSTEXPR explicit test_allocator(int data, int id) : data_(data), id_(id) {}
231
test_allocator(int data,int id,test_allocator_statistics * stats)232 TEST_CONSTEXPR_CXX14 explicit test_allocator(int data, int id, test_allocator_statistics* stats) TEST_NOEXCEPT
233 : data_(data), id_(id), stats_(stats)
234 {}
235
test_allocator(const test_allocator & a)236 TEST_CONSTEXPR_CXX14 explicit test_allocator(const test_allocator& a) TEST_NOEXCEPT
237 : data_(a.data_), id_(a.id_), stats_(a.stats_)
238 {}
239
240 template <class U>
test_allocator(const test_allocator<U> & a)241 TEST_CONSTEXPR_CXX14 test_allocator(const test_allocator<U>& a) TEST_NOEXCEPT
242 : data_(a.data_), id_(a.id_), stats_(a.stats_)
243 {}
244
~test_allocator()245 TEST_CONSTEXPR_CXX20 ~test_allocator() TEST_NOEXCEPT {
246 data_ = test_alloc_base::destructed_value;
247 id_ = test_alloc_base::destructed_value;
248 }
249
get_id()250 TEST_CONSTEXPR int get_id() const { return id_; }
get_data()251 TEST_CONSTEXPR int get_data() const { return data_; }
252
253 TEST_CONSTEXPR friend bool operator==(const test_allocator& x, const test_allocator& y) { return x.data_ == y.data_; }
254 TEST_CONSTEXPR friend bool operator!=(const test_allocator& x, const test_allocator& y) { return !(x == y); }
255 };
256
257 template <class T>
258 class other_allocator {
259 int data_ = -1;
260
261 template <class U>
262 friend class other_allocator;
263
264 public:
265 typedef T value_type;
266
other_allocator()267 TEST_CONSTEXPR_CXX14 other_allocator() {}
other_allocator(int i)268 TEST_CONSTEXPR_CXX14 explicit other_allocator(int i) : data_(i) {}
269
270 template <class U>
other_allocator(const other_allocator<U> & a)271 TEST_CONSTEXPR_CXX14 other_allocator(const other_allocator<U>& a) : data_(a.data_) {}
272
allocate(std::size_t n)273 TEST_CONSTEXPR_CXX20 T* allocate(std::size_t n) { return std::allocator<value_type>().allocate(n); }
deallocate(T * p,std::size_t s)274 TEST_CONSTEXPR_CXX20 void deallocate(T* p, std::size_t s) { std::allocator<value_type>().deallocate(p, s); }
275
select_on_container_copy_construction()276 TEST_CONSTEXPR_CXX14 other_allocator select_on_container_copy_construction() const { return other_allocator(-2); }
277
278 TEST_CONSTEXPR_CXX14 friend bool operator==(const other_allocator& x, const other_allocator& y) {
279 return x.data_ == y.data_;
280 }
281
282 TEST_CONSTEXPR_CXX14 friend bool operator!=(const other_allocator& x, const other_allocator& y) { return !(x == y); }
get_data()283 TEST_CONSTEXPR int get_data() const { return data_; }
284
285 typedef std::true_type propagate_on_container_copy_assignment;
286 typedef std::true_type propagate_on_container_move_assignment;
287 typedef std::true_type propagate_on_container_swap;
288
289 #if TEST_STD_VER < 11
max_size()290 std::size_t max_size() const { return UINT_MAX / sizeof(T); }
291 #endif
292 };
293
294 struct Ctor_Tag {};
295
296 template <typename T>
297 class TaggingAllocator;
298
299 struct Tag_X {
300 // All constructors must be passed the Tag type.
301
302 // DefaultInsertable into vector<X, TaggingAllocator<X>>,
Tag_XTag_X303 TEST_CONSTEXPR Tag_X(Ctor_Tag) {}
304 // CopyInsertable into vector<X, TaggingAllocator<X>>,
Tag_XTag_X305 TEST_CONSTEXPR Tag_X(Ctor_Tag, const Tag_X&) {}
306 // MoveInsertable into vector<X, TaggingAllocator<X>>, and
Tag_XTag_X307 TEST_CONSTEXPR Tag_X(Ctor_Tag, Tag_X&&) {}
308
309 // EmplaceConstructible into vector<X, TaggingAllocator<X>> from args.
310 template <typename... Args>
Tag_XTag_X311 TEST_CONSTEXPR Tag_X(Ctor_Tag, Args&&...) {}
312
313 // not DefaultConstructible, CopyConstructible or MoveConstructible.
314 Tag_X() = delete;
315 Tag_X(const Tag_X&) = delete;
316 Tag_X(Tag_X&&) = delete;
317
318 // CopyAssignable.
319 TEST_CONSTEXPR_CXX14 Tag_X& operator=(const Tag_X&) { return *this; };
320
321 // MoveAssignable.
322 TEST_CONSTEXPR_CXX14 Tag_X& operator=(Tag_X&&) { return *this; };
323
324 private:
325 ~Tag_X() = default;
326 // Erasable from vector<X, TaggingAllocator<X>>.
327 friend class TaggingAllocator<Tag_X>;
328 };
329
330 template <typename T>
331 class TaggingAllocator {
332 public:
333 using value_type = T;
334 TaggingAllocator() = default;
335
336 template <typename U>
TaggingAllocator(const TaggingAllocator<U> &)337 TEST_CONSTEXPR TaggingAllocator(const TaggingAllocator<U>&) {}
338
339 template <typename... Args>
construct(Tag_X * p,Args &&...args)340 TEST_CONSTEXPR_CXX20 void construct(Tag_X* p, Args&&... args) {
341 #if TEST_STD_VER > 17
342 std::construct_at(p, Ctor_Tag{}, std::forward<Args>(args)...);
343 #else
344 ::new (static_cast<void*>(p)) Tag_X(Ctor_Tag(), std::forward<Args>(args)...);
345 #endif
346 }
347
348 template <typename U>
destroy(U * p)349 TEST_CONSTEXPR_CXX20 void destroy(U* p) {
350 p->~U();
351 }
352
allocate(std::size_t n)353 TEST_CONSTEXPR_CXX20 T* allocate(std::size_t n) { return std::allocator<T>().allocate(n); }
deallocate(T * p,std::size_t n)354 TEST_CONSTEXPR_CXX20 void deallocate(T* p, std::size_t n) { std::allocator<T>().deallocate(p, n); }
355 };
356
357 template <std::size_t MaxAllocs>
358 struct limited_alloc_handle {
359 std::size_t outstanding_ = 0;
360 void* last_alloc_ = nullptr;
361
362 template <class T>
allocatelimited_alloc_handle363 TEST_CONSTEXPR_CXX20 T* allocate(std::size_t N) {
364 if (N + outstanding_ > MaxAllocs)
365 TEST_THROW(std::bad_alloc());
366 auto alloc = std::allocator<T>().allocate(N);
367 last_alloc_ = alloc;
368 outstanding_ += N;
369 return alloc;
370 }
371
372 template <class T>
deallocatelimited_alloc_handle373 TEST_CONSTEXPR_CXX20 void deallocate(T* ptr, std::size_t N) {
374 if (ptr == last_alloc_) {
375 last_alloc_ = nullptr;
376 assert(outstanding_ >= N);
377 outstanding_ -= N;
378 }
379 std::allocator<T>().deallocate(ptr, N);
380 }
381 };
382
383 namespace detail {
384 template <class T>
385 class thread_unsafe_shared_ptr {
386 public:
387 thread_unsafe_shared_ptr() = default;
388
thread_unsafe_shared_ptr(const thread_unsafe_shared_ptr & other)389 TEST_CONSTEXPR_CXX14 thread_unsafe_shared_ptr(const thread_unsafe_shared_ptr& other) : block(other.block) {
390 ++block->ref_count;
391 }
392
~thread_unsafe_shared_ptr()393 TEST_CONSTEXPR_CXX20 ~thread_unsafe_shared_ptr() {
394 --block->ref_count;
395 if (block->ref_count != 0)
396 return;
397 typedef std::allocator_traits<std::allocator<control_block> > allocator_traits;
398 std::allocator<control_block> alloc;
399 allocator_traits::destroy(alloc, block);
400 allocator_traits::deallocate(alloc, block, 1);
401 }
402
403 TEST_CONSTEXPR const T& operator*() const { return block->content; }
404 TEST_CONSTEXPR const T* operator->() const { return &block->content; }
405 TEST_CONSTEXPR_CXX14 T& operator*() { return block->content; }
406 TEST_CONSTEXPR_CXX14 T* operator->() { return &block->content; }
get()407 TEST_CONSTEXPR_CXX14 T* get() { return &block->content; }
get()408 TEST_CONSTEXPR const T* get() const { return &block->content; }
409
410 private:
411 struct control_block {
412 template <class... Args>
control_blockcontrol_block413 TEST_CONSTEXPR control_block(Args... args) : content(std::forward<Args>(args)...) {}
414 std::size_t ref_count = 1;
415 T content;
416 };
417
418 control_block* block = nullptr;
419
420 template <class U, class... Args>
421 friend TEST_CONSTEXPR_CXX20 thread_unsafe_shared_ptr<U> make_thread_unsafe_shared(Args...);
422 };
423
424 template <class T, class... Args>
make_thread_unsafe_shared(Args...args)425 TEST_CONSTEXPR_CXX20 thread_unsafe_shared_ptr<T> make_thread_unsafe_shared(Args... args) {
426 typedef typename thread_unsafe_shared_ptr<T>::control_block control_block_type;
427 typedef std::allocator_traits<std::allocator<control_block_type> > allocator_traits;
428
429 thread_unsafe_shared_ptr<T> ptr;
430 std::allocator<control_block_type> alloc;
431 ptr.block = allocator_traits::allocate(alloc, 1);
432 allocator_traits::construct(alloc, ptr.block, std::forward<Args>(args)...);
433
434 return ptr;
435 }
436 } // namespace detail
437
438 template <class T, std::size_t N>
439 class limited_allocator {
440 template <class U, std::size_t UN>
441 friend class limited_allocator;
442 typedef limited_alloc_handle<N> BuffT;
443 detail::thread_unsafe_shared_ptr<BuffT> handle_;
444
445 public:
446 typedef T value_type;
447 typedef value_type* pointer;
448 typedef const value_type* const_pointer;
449 typedef value_type& reference;
450 typedef const value_type& const_reference;
451 typedef std::size_t size_type;
452 typedef std::ptrdiff_t difference_type;
453
454 template <class U>
455 struct rebind {
456 typedef limited_allocator<U, N> other;
457 };
458
limited_allocator()459 TEST_CONSTEXPR_CXX20 limited_allocator() : handle_(detail::make_thread_unsafe_shared<BuffT>()) {}
460
461 limited_allocator(limited_allocator const&) = default;
462
463 template <class U>
limited_allocator(limited_allocator<U,N> const & other)464 TEST_CONSTEXPR explicit limited_allocator(limited_allocator<U, N> const& other) : handle_(other.handle_) {}
465
466 limited_allocator& operator=(const limited_allocator&) = delete;
467
allocate(size_type n)468 TEST_CONSTEXPR_CXX20 pointer allocate(size_type n) { return handle_->template allocate<T>(n); }
deallocate(pointer p,size_type n)469 TEST_CONSTEXPR_CXX20 void deallocate(pointer p, size_type n) { handle_->template deallocate<T>(p, n); }
max_size()470 TEST_CONSTEXPR size_type max_size() const { return N; }
getHandle()471 TEST_CONSTEXPR BuffT* getHandle() const { return handle_.get(); }
472 };
473
474 template <class T, class U, std::size_t N>
475 TEST_CONSTEXPR inline bool operator==(limited_allocator<T, N> const& LHS, limited_allocator<U, N> const& RHS) {
476 return LHS.getHandle() == RHS.getHandle();
477 }
478
479 template <class T, class U, std::size_t N>
480 TEST_CONSTEXPR inline bool operator!=(limited_allocator<T, N> const& LHS, limited_allocator<U, N> const& RHS) {
481 return !(LHS == RHS);
482 }
483
484 // Track the "provenance" of this allocator instance: how many times was
485 // select_on_container_copy_construction called in order to produce it?
486 //
487 template <class T>
488 struct SocccAllocator {
489 using value_type = T;
490
491 int count_ = 0;
SocccAllocatorSocccAllocator492 explicit SocccAllocator(int i) : count_(i) {}
493
494 template <class U>
SocccAllocatorSocccAllocator495 SocccAllocator(const SocccAllocator<U>& a) : count_(a.count_) {}
496
allocateSocccAllocator497 T* allocate(std::size_t n) { return std::allocator<T>().allocate(n); }
deallocateSocccAllocator498 void deallocate(T* p, std::size_t n) { std::allocator<T>().deallocate(p, n); }
499
select_on_container_copy_constructionSocccAllocator500 SocccAllocator select_on_container_copy_construction() const { return SocccAllocator(count_ + 1); }
501
502 bool operator==(const SocccAllocator&) const { return true; }
503
504 using propagate_on_container_copy_assignment = std::false_type;
505 using propagate_on_container_move_assignment = std::false_type;
506 using propagate_on_container_swap = std::false_type;
507 };
508
509 #endif // TEST_ALLOCATOR_H
510