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