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