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