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