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