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 class test_alloc_base {
30 protected:
31   static int time_to_throw;
32 
33 public:
34   static int throw_after;
35   static int count;
36   static int alloc_count;
37   static int copied;
38   static int moved;
39   static int converted;
40 
41   const static int destructed_value = -1;
42   const static int default_value = 0;
43   const static int moved_value = INT_MAX;
44 
45   static void clear() {
46     assert(count == 0 && "clearing leaking allocator data?");
47     count = 0;
48     time_to_throw = 0;
49     alloc_count = 0;
50     throw_after = INT_MAX;
51     clear_ctor_counters();
52   }
53 
54   static void clear_ctor_counters() {
55     copied = 0;
56     moved = 0;
57     converted = 0;
58   }
59 };
60 
61 int test_alloc_base::count = 0;
62 int test_alloc_base::time_to_throw = 0;
63 int test_alloc_base::alloc_count = 0;
64 int test_alloc_base::throw_after = INT_MAX;
65 int test_alloc_base::copied = 0;
66 int test_alloc_base::moved = 0;
67 int test_alloc_base::converted = 0;
68 
69 template <class T>
70 class test_allocator : public test_alloc_base {
71   int data_; // participates in equality
72   int id_;   // unique identifier, doesn't participate in equality
73   template <class U>
74   friend class test_allocator;
75 
76 public:
77   typedef unsigned size_type;
78   typedef int difference_type;
79   typedef T value_type;
80   typedef value_type* pointer;
81   typedef const value_type* const_pointer;
82   typedef typename std::add_lvalue_reference<value_type>::type reference;
83   typedef typename std::add_lvalue_reference<const value_type>::type const_reference;
84 
85   template <class U>
86   struct rebind {
87     typedef test_allocator<U> other;
88   };
89 
90   test_allocator() TEST_NOEXCEPT : data_(0), id_(0) { ++count; }
91   explicit test_allocator(int i, int id = 0) TEST_NOEXCEPT : data_(i), id_(id) { ++count; }
92   test_allocator(const test_allocator& a) TEST_NOEXCEPT : data_(a.data_), id_(a.id_) {
93     ++count;
94     ++copied;
95     assert(a.data_ != destructed_value && a.id_ != destructed_value && "copying from destroyed allocator");
96   }
97 #if TEST_STD_VER >= 11
98   test_allocator(test_allocator&& a) TEST_NOEXCEPT : data_(a.data_), id_(a.id_) {
99     ++count;
100     ++moved;
101     assert(a.data_ != destructed_value && a.id_ != destructed_value && "moving from destroyed allocator");
102     a.data_ = moved_value;
103     a.id_ = moved_value;
104   }
105 #endif
106   template <class U>
107   test_allocator(const test_allocator<U>& a) TEST_NOEXCEPT : data_(a.data_), id_(a.id_) {
108     ++count;
109     ++converted;
110   }
111   ~test_allocator() TEST_NOEXCEPT {
112     assert(data_ >= 0);
113     assert(id_ >= 0);
114     --count;
115     data_ = destructed_value;
116     id_ = destructed_value;
117   }
118   pointer address(reference x) const { return &x; }
119   const_pointer address(const_reference x) const { return &x; }
120   pointer allocate(size_type n, const void* = 0) {
121     assert(data_ >= 0);
122     if (time_to_throw >= throw_after) {
123 #ifndef TEST_HAS_NO_EXCEPTIONS
124       throw std::bad_alloc();
125 #else
126       std::terminate();
127 #endif
128     }
129     ++time_to_throw;
130     ++alloc_count;
131     return (pointer)::operator new(n * sizeof(T));
132   }
133   void deallocate(pointer p, size_type) {
134     assert(data_ >= 0);
135     --alloc_count;
136     ::operator delete((void*)p);
137   }
138   size_type max_size() const TEST_NOEXCEPT { return UINT_MAX / sizeof(T); }
139 #if TEST_STD_VER < 11
140   void construct(pointer p, const T& val) { ::new (static_cast<void*>(p)) T(val); }
141 #else
142   template <class U>
143   void construct(pointer p, U&& val) {
144     ::new (static_cast<void*>(p)) T(std::forward<U>(val));
145   }
146 #endif
147   void destroy(pointer p) { p->~T(); }
148   friend bool operator==(const test_allocator& x, const test_allocator& y) { return x.data_ == y.data_; }
149   friend bool operator!=(const test_allocator& x, const test_allocator& y) { return !(x == y); }
150 
151   int get_data() const { return data_; }
152   int get_id() const { return id_; }
153 };
154 
155 template <class T>
156 class non_default_test_allocator : public test_alloc_base {
157   int data_;
158 
159   template <class U>
160   friend class non_default_test_allocator;
161 
162 public:
163   typedef unsigned size_type;
164   typedef int difference_type;
165   typedef T value_type;
166   typedef value_type* pointer;
167   typedef const value_type* const_pointer;
168   typedef typename std::add_lvalue_reference<value_type>::type reference;
169   typedef typename std::add_lvalue_reference<const value_type>::type const_reference;
170 
171   template <class U>
172   struct rebind {
173     typedef non_default_test_allocator<U> other;
174   };
175 
176   //    non_default_test_allocator() TEST_NOEXCEPT : data_(0) {++count;}
177   explicit non_default_test_allocator(int i) TEST_NOEXCEPT : data_(i) { ++count; }
178   non_default_test_allocator(const non_default_test_allocator& a) TEST_NOEXCEPT : data_(a.data_) { ++count; }
179   template <class U>
180   non_default_test_allocator(const non_default_test_allocator<U>& a) TEST_NOEXCEPT : data_(a.data_) {
181     ++count;
182   }
183   ~non_default_test_allocator() TEST_NOEXCEPT {
184     assert(data_ >= 0);
185     --count;
186     data_ = -1;
187   }
188   pointer address(reference x) const { return &x; }
189   const_pointer address(const_reference x) const { return &x; }
190   pointer allocate(size_type n, const void* = 0) {
191     assert(data_ >= 0);
192     if (time_to_throw >= throw_after) {
193 #ifndef TEST_HAS_NO_EXCEPTIONS
194       throw std::bad_alloc();
195 #else
196       std::terminate();
197 #endif
198     }
199     ++time_to_throw;
200     ++alloc_count;
201     return (pointer)::operator new(n * sizeof(T));
202   }
203   void deallocate(pointer p, size_type) {
204     assert(data_ >= 0);
205     --alloc_count;
206     ::operator delete((void*)p);
207   }
208   size_type max_size() const TEST_NOEXCEPT { return UINT_MAX / sizeof(T); }
209 #if TEST_STD_VER < 11
210   void construct(pointer p, const T& val) { ::new (static_cast<void*>(p)) T(val); }
211 #else
212   template <class U>
213   void construct(pointer p, U&& val) {
214     ::new (static_cast<void*>(p)) T(std::forward<U>(val));
215   }
216 #endif
217   void destroy(pointer p) { p->~T(); }
218 
219   friend bool operator==(const non_default_test_allocator& x, const non_default_test_allocator& y) {
220     return x.data_ == y.data_;
221   }
222   friend bool operator!=(const non_default_test_allocator& x, const non_default_test_allocator& y) { return !(x == y); }
223 };
224 
225 template <>
226 class test_allocator<void> : public test_alloc_base {
227   int data_;
228   int id_;
229 
230   template <class U>
231   friend class test_allocator;
232 
233 public:
234   typedef unsigned size_type;
235   typedef int difference_type;
236   typedef void value_type;
237   typedef value_type* pointer;
238   typedef const value_type* const_pointer;
239 
240   template <class U>
241   struct rebind {
242     typedef test_allocator<U> other;
243   };
244 
245   test_allocator() TEST_NOEXCEPT : data_(0), id_(0) {}
246   explicit test_allocator(int i, int id = 0) TEST_NOEXCEPT : data_(i), id_(id) {}
247   test_allocator(const test_allocator& a) TEST_NOEXCEPT : data_(a.data_), id_(a.id_) {}
248   template <class U>
249   test_allocator(const test_allocator<U>& a) TEST_NOEXCEPT : data_(a.data_), id_(a.id_) {}
250   ~test_allocator() TEST_NOEXCEPT {
251     data_ = -1;
252     id_ = -1;
253   }
254 
255   int get_id() const { return id_; }
256   int get_data() const { return data_; }
257 
258   friend bool operator==(const test_allocator& x, const test_allocator& y) { return x.data_ == y.data_; }
259   friend bool operator!=(const test_allocator& x, const test_allocator& y) { return !(x == y); }
260 };
261 
262 template <class T>
263 class other_allocator {
264   int data_;
265 
266   template <class U>
267   friend class other_allocator;
268 
269 public:
270   typedef T value_type;
271 
272   other_allocator() : data_(-1) {}
273   explicit other_allocator(int i) : data_(i) {}
274   template <class U>
275   other_allocator(const other_allocator<U>& a) : data_(a.data_) {}
276   T* allocate(std::size_t n) { return (T*)::operator new(n * sizeof(T)); }
277   void deallocate(T* p, std::size_t) { ::operator delete((void*)p); }
278 
279   other_allocator select_on_container_copy_construction() const { return other_allocator(-2); }
280 
281   friend bool operator==(const other_allocator& x, const other_allocator& y) { return x.data_ == y.data_; }
282   friend bool operator!=(const other_allocator& x, const other_allocator& y) { return !(x == y); }
283 
284   typedef std::true_type propagate_on_container_copy_assignment;
285   typedef std::true_type propagate_on_container_move_assignment;
286   typedef std::true_type propagate_on_container_swap;
287 
288 #if TEST_STD_VER < 11
289   std::size_t max_size() const { return UINT_MAX / sizeof(T); }
290 #endif
291 };
292 
293 #if TEST_STD_VER >= 11
294 
295 struct Ctor_Tag {};
296 
297 template <typename T>
298 class TaggingAllocator;
299 
300 struct Tag_X {
301   // All constructors must be passed the Tag type.
302 
303   // DefaultInsertable into vector<X, TaggingAllocator<X>>,
304   Tag_X(Ctor_Tag) {}
305   // CopyInsertable into vector<X, TaggingAllocator<X>>,
306   Tag_X(Ctor_Tag, const Tag_X&) {}
307   // MoveInsertable into vector<X, TaggingAllocator<X>>, and
308   Tag_X(Ctor_Tag, Tag_X&&) {}
309 
310   // EmplaceConstructible into vector<X, TaggingAllocator<X>> from args.
311   template <typename... Args>
312   Tag_X(Ctor_Tag, Args&&...) {}
313 
314   // not DefaultConstructible, CopyConstructible or MoveConstructible.
315   Tag_X() = delete;
316   Tag_X(const Tag_X&) = delete;
317   Tag_X(Tag_X&&) = delete;
318 
319   // CopyAssignable.
320   Tag_X& operator=(const Tag_X&) { return *this; }
321 
322   // MoveAssignable.
323   Tag_X& operator=(Tag_X&&) { return *this; }
324 
325 private:
326   // Not Destructible.
327   ~Tag_X() {}
328 
329   // Erasable from vector<X, TaggingAllocator<X>>.
330   friend class TaggingAllocator<Tag_X>;
331 };
332 
333 template <typename T>
334 class TaggingAllocator {
335 public:
336   using value_type = T;
337   TaggingAllocator() = default;
338 
339   template <typename U>
340   TaggingAllocator(const TaggingAllocator<U>&) {}
341 
342   T* allocate(std::size_t n) { return std::allocator<T>{}.allocate(n); }
343 
344   void deallocate(T* p, std::size_t n) { std::allocator<T>{}.deallocate(p, n); }
345 
346   template <typename... Args>
347   void construct(Tag_X* p, Args&&... args) {
348     ::new ((void*)p) Tag_X(Ctor_Tag{}, std::forward<Args>(args)...);
349   }
350 
351   template <typename U, typename... Args>
352   void construct(U* p, Args&&... args) {
353     ::new ((void*)p) U(std::forward<Args>(args)...);
354   }
355 
356   template <typename U, typename... Args>
357   void destroy(U* p) {
358     p->~U();
359   }
360 };
361 
362 template <typename T, typename U>
363 bool operator==(const TaggingAllocator<T>&, const TaggingAllocator<U>&) {
364   return true;
365 }
366 
367 template <typename T, typename U>
368 bool operator!=(const TaggingAllocator<T>&, const TaggingAllocator<U>&) {
369   return false;
370 }
371 #endif
372 
373 template <std::size_t MaxAllocs>
374 struct limited_alloc_handle {
375   std::size_t outstanding_;
376   void* last_alloc_;
377 
378   limited_alloc_handle() : outstanding_(0), last_alloc_(nullptr) {}
379 
380   template <class T>
381   T* allocate(std::size_t N) {
382     if (N + outstanding_ > MaxAllocs)
383       TEST_THROW(std::bad_alloc());
384     last_alloc_ = ::operator new(N * sizeof(T));
385     outstanding_ += N;
386     return static_cast<T*>(last_alloc_);
387   }
388 
389   void deallocate(void* ptr, std::size_t N) {
390     if (ptr == last_alloc_) {
391       last_alloc_ = nullptr;
392       assert(outstanding_ >= N);
393       outstanding_ -= N;
394     }
395     ::operator delete(ptr);
396   }
397 };
398 
399 template <class T, std::size_t N>
400 class limited_allocator {
401   template <class U, std::size_t UN>
402   friend class limited_allocator;
403   typedef limited_alloc_handle<N> BuffT;
404   std::shared_ptr<BuffT> handle_;
405 
406 public:
407   typedef T value_type;
408   typedef value_type* pointer;
409   typedef const value_type* const_pointer;
410   typedef value_type& reference;
411   typedef const value_type& const_reference;
412   typedef std::size_t size_type;
413   typedef std::ptrdiff_t difference_type;
414 
415   template <class U>
416   struct rebind {
417     typedef limited_allocator<U, N> other;
418   };
419 
420   limited_allocator() : handle_(new BuffT) {}
421 
422   limited_allocator(limited_allocator const& other) : handle_(other.handle_) {}
423 
424   template <class U>
425   explicit limited_allocator(limited_allocator<U, N> const& other) : handle_(other.handle_) {}
426 
427   limited_allocator& operator=(const limited_allocator&) = delete;
428 
429   pointer allocate(size_type n) { return handle_->template allocate<T>(n); }
430   void deallocate(pointer p, size_type n) { handle_->deallocate(p, n); }
431   size_type max_size() const { return N; }
432 
433   BuffT* getHandle() const { return handle_.get(); }
434 };
435 
436 template <class T, class U, std::size_t N>
437 inline bool operator==(limited_allocator<T, N> const& LHS, limited_allocator<U, N> const& RHS) {
438   return LHS.getHandle() == RHS.getHandle();
439 }
440 
441 template <class T, class U, std::size_t N>
442 inline bool operator!=(limited_allocator<T, N> const& LHS, limited_allocator<U, N> const& RHS) {
443   return !(LHS == RHS);
444 }
445 
446 #endif // TEST_ALLOCATOR_H
447