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>
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 
38   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 
47   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 
84   TEST_CONSTEXPR_CXX14 explicit test_allocator(test_allocator_statistics* stats) TEST_NOEXCEPT : stats_(stats) {
85     if (stats_ != nullptr)
86       ++stats_->count;
87   }
88 
89   TEST_CONSTEXPR explicit test_allocator(int data) TEST_NOEXCEPT : data_(data) {}
90 
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 
97   TEST_CONSTEXPR explicit test_allocator(int data, int id) TEST_NOEXCEPT : data_(data), id_(id) {}
98 
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 
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 
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>
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 
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 
144   TEST_CONSTEXPR pointer address(reference x) const { return &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 
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 
165   TEST_CONSTEXPR size_type max_size() const TEST_NOEXCEPT { return UINT_MAX / sizeof(T); }
166 
167   template <class U>
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 
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 
180   TEST_CONSTEXPR int get_data() const { return data_; }
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
208       : data_(i), stats_(stats) {
209     if (stats_ != nullptr) {
210       ++stats_->count;
211     }
212   }
213 
214   TEST_CONSTEXPR_CXX14
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>
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 
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 
234   TEST_CONSTEXPR pointer address(reference x) const { return &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 
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 
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 
289   TEST_CONSTEXPR_CXX14 explicit test_allocator(test_allocator_statistics* stats) TEST_NOEXCEPT : stats_(stats) {}
290 
291   TEST_CONSTEXPR explicit test_allocator(int data) TEST_NOEXCEPT : data_(data) {}
292 
293   TEST_CONSTEXPR explicit test_allocator(int data, test_allocator_statistics* stats) TEST_NOEXCEPT
294       : data_(data), stats_(stats)
295   {}
296 
297   TEST_CONSTEXPR explicit test_allocator(int data, int id) : data_(data), id_(id) {}
298 
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 
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>
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 
312   TEST_CONSTEXPR_CXX20 ~test_allocator() TEST_NOEXCEPT {
313     data_ = test_alloc_base::destructed_value;
314     id_ = test_alloc_base::destructed_value;
315   }
316 
317   TEST_CONSTEXPR int get_id() const { return id_; }
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 
334   TEST_CONSTEXPR_CXX14 other_allocator() {}
335   TEST_CONSTEXPR_CXX14 explicit other_allocator(int i) : data_(i) {}
336 
337   template <class U>
338   TEST_CONSTEXPR_CXX14 other_allocator(const other_allocator<U>& a) : data_(a.data_) {}
339 
340   TEST_CONSTEXPR_CXX20 T* allocate(std::size_t n) { return std::allocator<value_type>().allocate(n); }
341   TEST_CONSTEXPR_CXX20 void deallocate(T* p, std::size_t s) { std::allocator<value_type>().deallocate(p, s); }
342 
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
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>>,
369   TEST_CONSTEXPR Tag_X(Ctor_Tag) {}
370   // CopyInsertable into vector<X, TaggingAllocator<X>>,
371   TEST_CONSTEXPR Tag_X(Ctor_Tag, const Tag_X&) {}
372   // MoveInsertable into vector<X, TaggingAllocator<X>>, and
373   TEST_CONSTEXPR Tag_X(Ctor_Tag, Tag_X&&) {}
374 
375   // EmplaceConstructible into vector<X, TaggingAllocator<X>> from args.
376   template <typename... Args>
377   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>
403   TEST_CONSTEXPR TaggingAllocator(const TaggingAllocator<U>&) {}
404 
405   template <typename... 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>
415   TEST_CONSTEXPR_CXX20 void destroy(U* p) {
416     p->~U();
417   }
418 
419   TEST_CONSTEXPR_CXX20 T* allocate(std::size_t n) { return std::allocator<T>().allocate(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>
429   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>
439   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 
455   TEST_CONSTEXPR_CXX14 thread_unsafe_shared_ptr(const thread_unsafe_shared_ptr& other) : block(other.block) {
456     ++block->ref_count;
457   }
458 
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; }
473   TEST_CONSTEXPR_CXX14 T* get() { return &block->content; }
474   TEST_CONSTEXPR const T* get() const { return &block->content; }
475 
476 private:
477   struct control_block {
478     template <class... Args>
479     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>
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 
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>
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 
534   TEST_CONSTEXPR_CXX20 pointer allocate(size_type n) { return handle_->template allocate<T>(n); }
535   TEST_CONSTEXPR_CXX20 void deallocate(pointer p, size_type n) { handle_->template deallocate<T>(p, n); }
536   TEST_CONSTEXPR size_type max_size() const { return N; }
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