1 //===----------------------------------------------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is dual licensed under the MIT and the University of Illinois Open
6 // Source Licenses. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #ifndef TEST_ALLOCATOR_H
11 #define TEST_ALLOCATOR_H
12 
13 #include <type_traits>
14 #include <new>
15 #include <memory>
16 #include <cstddef>
17 #include <cstdlib>
18 #include <climits>
19 #include <cassert>
20 
21 #include "test_macros.h"
22 
23 class test_alloc_base
24 {
25 protected:
26     static int time_to_throw;
27 public:
28     static int throw_after;
29     static int count;
30     static int alloc_count;
31 };
32 
33 int test_alloc_base::count = 0;
34 int test_alloc_base::time_to_throw = 0;
35 int test_alloc_base::alloc_count = 0;
36 int test_alloc_base::throw_after = INT_MAX;
37 
38 template <class T>
39 class test_allocator
40     : public test_alloc_base
41 {
42     int data_;
43 
44     template <class U> friend class test_allocator;
45 public:
46 
47     typedef unsigned                                                   size_type;
48     typedef int                                                        difference_type;
49     typedef T                                                          value_type;
50     typedef value_type*                                                pointer;
51     typedef const value_type*                                          const_pointer;
52     typedef typename std::add_lvalue_reference<value_type>::type       reference;
53     typedef typename std::add_lvalue_reference<const value_type>::type const_reference;
54 
55     template <class U> struct rebind {typedef test_allocator<U> other;};
56 
57     test_allocator() throw() : data_(0) {++count;}
58     explicit test_allocator(int i) throw() : data_(i) {++count;}
59     test_allocator(const test_allocator& a) throw()
60         : data_(a.data_) {++count;}
61     template <class U> test_allocator(const test_allocator<U>& a) throw()
62         : data_(a.data_) {++count;}
63     ~test_allocator() throw() {assert(data_ >= 0); --count; data_ = -1;}
64     pointer address(reference x) const {return &x;}
65     const_pointer address(const_reference x) const {return &x;}
66     pointer allocate(size_type n, const void* = 0)
67         {
68             assert(data_ >= 0);
69             if (time_to_throw >= throw_after) {
70 #ifndef TEST_HAS_NO_EXCEPTIONS
71                 throw std::bad_alloc();
72 #else
73                 std::terminate();
74 #endif
75             }
76             ++time_to_throw;
77             ++alloc_count;
78             return (pointer)::operator new(n * sizeof(T));
79         }
80     void deallocate(pointer p, size_type)
81         {assert(data_ >= 0); --alloc_count; ::operator delete((void*)p);}
82     size_type max_size() const throw()
83         {return UINT_MAX / sizeof(T);}
84 #if TEST_STD_VER < 11
85     void construct(pointer p, const T& val)
86         {::new(static_cast<void*>(p)) T(val);}
87 #else
88     template <class U> void construct(pointer p, U&& val)
89         {::new(static_cast<void*>(p)) T(std::forward<U>(val));}
90 #endif
91     void destroy(pointer p)
92         {p->~T();}
93     friend bool operator==(const test_allocator& x, const test_allocator& y)
94         {return x.data_ == y.data_;}
95     friend bool operator!=(const test_allocator& x, const test_allocator& y)
96         {return !(x == y);}
97 };
98 
99 template <class T>
100 class non_default_test_allocator
101     : public test_alloc_base
102 {
103     int data_;
104 
105     template <class U> friend class non_default_test_allocator;
106 public:
107 
108     typedef unsigned                                                   size_type;
109     typedef int                                                        difference_type;
110     typedef T                                                          value_type;
111     typedef value_type*                                                pointer;
112     typedef const value_type*                                          const_pointer;
113     typedef typename std::add_lvalue_reference<value_type>::type       reference;
114     typedef typename std::add_lvalue_reference<const value_type>::type const_reference;
115 
116     template <class U> struct rebind {typedef non_default_test_allocator<U> other;};
117 
118 //    non_default_test_allocator() throw() : data_(0) {++count;}
119     explicit non_default_test_allocator(int i) throw() : data_(i) {++count;}
120     non_default_test_allocator(const non_default_test_allocator& a) throw()
121         : data_(a.data_) {++count;}
122     template <class U> non_default_test_allocator(const non_default_test_allocator<U>& a) throw()
123         : data_(a.data_) {++count;}
124     ~non_default_test_allocator() throw() {assert(data_ >= 0); --count; data_ = -1;}
125     pointer address(reference x) const {return &x;}
126     const_pointer address(const_reference x) const {return &x;}
127     pointer allocate(size_type n, const void* = 0)
128         {
129             assert(data_ >= 0);
130             if (time_to_throw >= throw_after) {
131 #ifndef TEST_HAS_NO_EXCEPTIONS
132                 throw std::bad_alloc();
133 #else
134                 std::terminate();
135 #endif
136             }
137             ++time_to_throw;
138             ++alloc_count;
139             return (pointer)::operator new (n * sizeof(T));
140         }
141     void deallocate(pointer p, size_type)
142         {assert(data_ >= 0); --alloc_count; ::operator delete((void*)p); }
143     size_type max_size() const throw()
144         {return UINT_MAX / sizeof(T);}
145 #if TEST_STD_VER < 11
146     void construct(pointer p, const T& val)
147         {::new(static_cast<void*>(p)) T(val);}
148 #else
149     template <class U> void construct(pointer p, U&& val)
150         {::new(static_cast<void*>(p)) T(std::forward<U>(val));}
151 #endif
152     void destroy(pointer p) {p->~T();}
153 
154     friend bool operator==(const non_default_test_allocator& x, const non_default_test_allocator& y)
155         {return x.data_ == y.data_;}
156     friend bool operator!=(const non_default_test_allocator& x, const non_default_test_allocator& y)
157         {return !(x == y);}
158 };
159 
160 template <>
161 class test_allocator<void>
162     : public test_alloc_base
163 {
164     int data_;
165 
166     template <class U> friend class test_allocator;
167 public:
168 
169     typedef unsigned                                                   size_type;
170     typedef int                                                        difference_type;
171     typedef void                                                       value_type;
172     typedef value_type*                                                pointer;
173     typedef const value_type*                                          const_pointer;
174 
175     template <class U> struct rebind {typedef test_allocator<U> other;};
176 
177     test_allocator() throw() : data_(0) {}
178     explicit test_allocator(int i) throw() : data_(i) {}
179     test_allocator(const test_allocator& a) throw()
180         : data_(a.data_) {}
181     template <class U> test_allocator(const test_allocator<U>& a) throw()
182         : data_(a.data_) {}
183     ~test_allocator() throw() {data_ = -1;}
184 
185     friend bool operator==(const test_allocator& x, const test_allocator& y)
186         {return x.data_ == y.data_;}
187     friend bool operator!=(const test_allocator& x, const test_allocator& y)
188         {return !(x == y);}
189 };
190 
191 template <class T>
192 class other_allocator
193 {
194     int data_;
195 
196     template <class U> friend class other_allocator;
197 
198 public:
199     typedef T value_type;
200 
201     other_allocator() : data_(-1) {}
202     explicit other_allocator(int i) : data_(i) {}
203     template <class U> other_allocator(const other_allocator<U>& a)
204         : data_(a.data_) {}
205     T* allocate(std::size_t n)
206         {return (T*)::operator new(n * sizeof(T));}
207     void deallocate(T* p, std::size_t)
208         {::operator delete((void*)p);}
209 
210     other_allocator select_on_container_copy_construction() const
211         {return other_allocator(-2);}
212 
213     friend bool operator==(const other_allocator& x, const other_allocator& y)
214         {return x.data_ == y.data_;}
215     friend bool operator!=(const other_allocator& x, const other_allocator& y)
216         {return !(x == y);}
217 
218     typedef std::true_type propagate_on_container_copy_assignment;
219     typedef std::true_type propagate_on_container_move_assignment;
220     typedef std::true_type propagate_on_container_swap;
221 
222 #if TEST_STD_VER < 11
223     std::size_t max_size() const
224         {return UINT_MAX / sizeof(T);}
225 #endif
226 
227 };
228 
229 #if TEST_STD_VER >= 11
230 
231 struct Ctor_Tag {};
232 
233 template <typename T> class TaggingAllocator;
234 
235 struct Tag_X {
236   // All constructors must be passed the Tag type.
237 
238   // DefaultInsertable into vector<X, TaggingAllocator<X>>,
239   Tag_X(Ctor_Tag) {}
240   // CopyInsertable into vector<X, TaggingAllocator<X>>,
241   Tag_X(Ctor_Tag, const Tag_X&) {}
242   // MoveInsertable into vector<X, TaggingAllocator<X>>, and
243   Tag_X(Ctor_Tag, Tag_X&&) {}
244 
245   // EmplaceConstructible into vector<X, TaggingAllocator<X>> from args.
246   template<typename... Args>
247   Tag_X(Ctor_Tag, Args&&...) { }
248 
249   // not DefaultConstructible, CopyConstructible or MoveConstructible.
250   Tag_X() = delete;
251   Tag_X(const Tag_X&) = delete;
252   Tag_X(Tag_X&&) = delete;
253 
254   // CopyAssignable.
255   Tag_X& operator=(const Tag_X&) { return *this; }
256 
257   // MoveAssignable.
258   Tag_X& operator=(Tag_X&&) { return *this; }
259 
260 private:
261   // Not Destructible.
262   ~Tag_X() { }
263 
264   // Erasable from vector<X, TaggingAllocator<X>>.
265   friend class TaggingAllocator<Tag_X>;
266 };
267 
268 
269 template<typename T>
270 class TaggingAllocator {
271 public:
272     using value_type = T;
273     TaggingAllocator() = default;
274 
275     template<typename U>
276       TaggingAllocator(const TaggingAllocator<U>&) { }
277 
278     T* allocate(std::size_t n) { return std::allocator<T>{}.allocate(n); }
279 
280     void deallocate(T* p, std::size_t n) { std::allocator<T>{}.deallocate(p, n); }
281 
282     template<typename... Args>
283     void construct(Tag_X* p, Args&&... args)
284     { ::new((void*)p) Tag_X(Ctor_Tag{}, std::forward<Args>(args)...); }
285 
286     template<typename U, typename... Args>
287     void construct(U* p, Args&&... args)
288     { ::new((void*)p) U(std::forward<Args>(args)...); }
289 
290     template<typename U, typename... Args>
291     void destroy(U* p)
292     { p->~U(); }
293 };
294 
295 template<typename T, typename U>
296 bool
297 operator==(const TaggingAllocator<T>&, const TaggingAllocator<U>&)
298 { return true; }
299 
300 template<typename T, typename U>
301 bool
302 operator!=(const TaggingAllocator<T>&, const TaggingAllocator<U>&)
303 { return false; }
304 #endif
305 
306 template <std::size_t MaxAllocs>
307 struct limited_alloc_handle {
308   std::size_t outstanding_;
309   void* last_alloc_;
310 
311   limited_alloc_handle() : outstanding_(0), last_alloc_(nullptr) {}
312 
313   template <class T>
314   T *allocate(std::size_t N) {
315     if (N + outstanding_ > MaxAllocs)
316       TEST_THROW(std::bad_alloc());
317     last_alloc_ = ::operator new(N*sizeof(T));
318     outstanding_ += N;
319     return static_cast<T*>(last_alloc_);
320   }
321 
322   void deallocate(void* ptr, std::size_t N) {
323     if (ptr == last_alloc_) {
324       last_alloc_ = nullptr;
325       assert(outstanding_ >= N);
326       outstanding_ -= N;
327     }
328     ::operator delete(ptr);
329   }
330 };
331 
332 template <class T, std::size_t N>
333 class limited_allocator
334 {
335     template <class U, std::size_t UN> friend class limited_allocator;
336     typedef limited_alloc_handle<N> BuffT;
337     std::shared_ptr<BuffT> handle_;
338 public:
339     typedef T                 value_type;
340     typedef value_type*       pointer;
341     typedef const value_type* const_pointer;
342     typedef value_type&       reference;
343     typedef const value_type& const_reference;
344     typedef std::size_t       size_type;
345     typedef std::ptrdiff_t    difference_type;
346 
347     template <class U> struct rebind { typedef limited_allocator<U, N> other; };
348 
349     limited_allocator() : handle_(new BuffT) {}
350 
351     limited_allocator(limited_allocator const& other) : handle_(other.handle_) {}
352 
353     template <class U>
354     explicit limited_allocator(limited_allocator<U, N> const& other)
355         : handle_(other.handle_) {}
356 
357 private:
358     limited_allocator& operator=(const limited_allocator&);// = delete;
359 
360 public:
361     pointer allocate(size_type n) { return handle_->template allocate<T>(n); }
362     void deallocate(pointer p, size_type n) { handle_->deallocate(p, n); }
363     size_type max_size() const {return N;}
364 
365     BuffT* getHandle() const { return handle_.get(); }
366 };
367 
368 template <class T, class U, std::size_t N>
369 inline bool operator==(limited_allocator<T, N> const& LHS,
370                        limited_allocator<U, N> const& RHS) {
371   return LHS.getHandle() == RHS.getHandle();
372 }
373 
374 template <class T, class U, std::size_t N>
375 inline bool operator!=(limited_allocator<T, N> const& LHS,
376                        limited_allocator<U, N> const& RHS) {
377   return !(LHS == RHS);
378 }
379 
380 
381 #endif  // TEST_ALLOCATOR_H
382