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 MIN_ALLOCATOR_H
10 #define MIN_ALLOCATOR_H
11 
12 #include <cstddef>
13 #include <cstdlib>
14 #include <cstddef>
15 #include <cassert>
16 #include <climits>
17 #include <iterator>
18 #include <memory>
19 
20 #include "test_macros.h"
21 
22 template <class T>
23 class bare_allocator
24 {
25 public:
26     typedef T value_type;
27 
bare_allocator()28     bare_allocator() TEST_NOEXCEPT {}
29 
30     template <class U>
bare_allocator(bare_allocator<U>)31     bare_allocator(bare_allocator<U>) TEST_NOEXCEPT {}
32 
allocate(std::size_t n)33     T* allocate(std::size_t n)
34     {
35         return static_cast<T*>(::operator new(n*sizeof(T)));
36     }
37 
deallocate(T * p,std::size_t)38     void deallocate(T* p, std::size_t)
39     {
40         return ::operator delete(static_cast<void*>(p));
41     }
42 
43     friend bool operator==(bare_allocator, bare_allocator) {return true;}
44     friend bool operator!=(bare_allocator x, bare_allocator y) {return !(x == y);}
45 };
46 
47 
48 template <class T>
49 class no_default_allocator
50 {
51 #if TEST_STD_VER >= 11
52     no_default_allocator() = delete;
53 #else
54     no_default_allocator();
55 #endif
56     struct construct_tag {};
no_default_allocator(construct_tag)57     explicit no_default_allocator(construct_tag) {}
58 
59 public:
create()60     static no_default_allocator create() {
61       construct_tag tag;
62       return no_default_allocator(tag);
63     }
64 
65 public:
66     typedef T value_type;
67 
68     template <class U>
no_default_allocator(no_default_allocator<U>)69     no_default_allocator(no_default_allocator<U>) TEST_NOEXCEPT {}
70 
allocate(std::size_t n)71     T* allocate(std::size_t n)
72     {
73         return static_cast<T*>(::operator new(n*sizeof(T)));
74     }
75 
deallocate(T * p,std::size_t)76     void deallocate(T* p, std::size_t)
77     {
78         return ::operator delete(static_cast<void*>(p));
79     }
80 
81     friend bool operator==(no_default_allocator, no_default_allocator) {return true;}
82     friend bool operator!=(no_default_allocator x, no_default_allocator y) {return !(x == y);}
83 };
84 
85 struct malloc_allocator_base {
86     static size_t outstanding_bytes;
87     static size_t alloc_count;
88     static size_t dealloc_count;
89     static bool disable_default_constructor;
90 
outstanding_allocmalloc_allocator_base91     static size_t outstanding_alloc() {
92       assert(alloc_count >= dealloc_count);
93       return (alloc_count - dealloc_count);
94     }
95 
resetmalloc_allocator_base96     static void reset() {
97         assert(outstanding_alloc() == 0);
98         disable_default_constructor = false;
99         outstanding_bytes = 0;
100         alloc_count = 0;
101         dealloc_count = 0;
102     }
103 };
104 
105 size_t malloc_allocator_base::outstanding_bytes = 0;
106 size_t malloc_allocator_base::alloc_count = 0;
107 size_t malloc_allocator_base::dealloc_count = 0;
108 bool malloc_allocator_base::disable_default_constructor = false;
109 
110 
111 template <class T>
112 class malloc_allocator : public malloc_allocator_base
113 {
114 public:
115     typedef T value_type;
116 
malloc_allocator()117     malloc_allocator() TEST_NOEXCEPT { assert(!disable_default_constructor); }
118 
119     template <class U>
malloc_allocator(malloc_allocator<U>)120     malloc_allocator(malloc_allocator<U>) TEST_NOEXCEPT {}
121 
allocate(std::size_t n)122     T* allocate(std::size_t n)
123     {
124         const size_t nbytes = n*sizeof(T);
125         ++alloc_count;
126         outstanding_bytes += nbytes;
127         return static_cast<T*>(std::malloc(nbytes));
128     }
129 
deallocate(T * p,std::size_t n)130     void deallocate(T* p, std::size_t n)
131     {
132         const size_t nbytes = n*sizeof(T);
133         ++dealloc_count;
134         outstanding_bytes -= nbytes;
135         std::free(static_cast<void*>(p));
136     }
137 
138     friend bool operator==(malloc_allocator, malloc_allocator) {return true;}
139     friend bool operator!=(malloc_allocator x, malloc_allocator y) {return !(x == y);}
140 };
141 
142 template <class T>
143 struct cpp03_allocator : bare_allocator<T>
144 {
145     typedef T value_type;
146     typedef value_type* pointer;
147 
148     static bool construct_called;
149 
150     // Returned value is not used but it's not prohibited.
constructcpp03_allocator151     pointer construct(pointer p, const value_type& val)
152     {
153         ::new(p) value_type(val);
154         construct_called = true;
155         return p;
156     }
157 
max_sizecpp03_allocator158     std::size_t max_size() const
159     {
160         return UINT_MAX / sizeof(T);
161     }
162 };
163 template <class T> bool cpp03_allocator<T>::construct_called = false;
164 
165 template <class T>
166 struct cpp03_overload_allocator : bare_allocator<T>
167 {
168     typedef T value_type;
169     typedef value_type* pointer;
170 
171     static bool construct_called;
172 
constructcpp03_overload_allocator173     void construct(pointer p, const value_type& val)
174     {
175         construct(p, val, std::is_class<T>());
176     }
constructcpp03_overload_allocator177     void construct(pointer p, const value_type& val, std::true_type)
178     {
179         ::new(p) value_type(val);
180         construct_called = true;
181     }
constructcpp03_overload_allocator182     void construct(pointer p, const value_type& val, std::false_type)
183     {
184         ::new(p) value_type(val);
185         construct_called = true;
186     }
187 
max_sizecpp03_overload_allocator188     std::size_t max_size() const
189     {
190         return UINT_MAX / sizeof(T);
191     }
192 };
193 template <class T> bool cpp03_overload_allocator<T>::construct_called = false;
194 
195 template <class T, class = std::integral_constant<size_t, 0> > class min_pointer;
196 template <class T, class ID> class min_pointer<const T, ID>;
197 template <class ID> class min_pointer<void, ID>;
198 template <class ID> class min_pointer<const void, ID>;
199 template <class T> class min_allocator;
200 
201 template <class ID>
202 class min_pointer<const void, ID>
203 {
204     const void* ptr_;
205 public:
206     min_pointer() TEST_NOEXCEPT = default;
min_pointer(std::nullptr_t)207     min_pointer(std::nullptr_t) TEST_NOEXCEPT : ptr_(nullptr) {}
208     template <class T>
min_pointer(min_pointer<T,ID> p)209     min_pointer(min_pointer<T, ID> p) TEST_NOEXCEPT : ptr_(p.ptr_) {}
210 
211     explicit operator bool() const {return ptr_ != nullptr;}
212 
213     friend bool operator==(min_pointer x, min_pointer y) {return x.ptr_ == y.ptr_;}
214     friend bool operator!=(min_pointer x, min_pointer y) {return !(x == y);}
215     template <class U, class XID> friend class min_pointer;
216 };
217 
218 template <class ID>
219 class min_pointer<void, ID>
220 {
221     void* ptr_;
222 public:
223     min_pointer() TEST_NOEXCEPT = default;
min_pointer(std::nullptr_t)224     TEST_CONSTEXPR_CXX14 min_pointer(std::nullptr_t) TEST_NOEXCEPT : ptr_(nullptr) {}
225     template <class T,
226               class = typename std::enable_if
227                        <
228                             !std::is_const<T>::value
229                        >::type
230              >
min_pointer(min_pointer<T,ID> p)231     TEST_CONSTEXPR_CXX14 min_pointer(min_pointer<T, ID> p) TEST_NOEXCEPT : ptr_(p.ptr_) {}
232 
233     TEST_CONSTEXPR_CXX14 explicit operator bool() const {return ptr_ != nullptr;}
234 
235     TEST_CONSTEXPR_CXX14 friend bool operator==(min_pointer x, min_pointer y) {return x.ptr_ == y.ptr_;}
236     TEST_CONSTEXPR_CXX14 friend bool operator!=(min_pointer x, min_pointer y) {return !(x == y);}
237     template <class U, class XID> friend class min_pointer;
238 };
239 
240 template <class T, class ID>
241 class min_pointer
242 {
243     T* ptr_;
244 
min_pointer(T * p)245     TEST_CONSTEXPR_CXX14 explicit min_pointer(T* p) TEST_NOEXCEPT : ptr_(p) {}
246 public:
247     min_pointer() TEST_NOEXCEPT = default;
min_pointer(std::nullptr_t)248     TEST_CONSTEXPR_CXX14 min_pointer(std::nullptr_t) TEST_NOEXCEPT : ptr_(nullptr) {}
min_pointer(min_pointer<void,ID> p)249     TEST_CONSTEXPR_CXX14 explicit min_pointer(min_pointer<void, ID> p) TEST_NOEXCEPT : ptr_(static_cast<T*>(p.ptr_)) {}
250 
251     TEST_CONSTEXPR_CXX14 explicit operator bool() const {return ptr_ != nullptr;}
252 
253     typedef std::ptrdiff_t difference_type;
254     typedef T& reference;
255     typedef T* pointer;
256     typedef T value_type;
257     typedef std::random_access_iterator_tag iterator_category;
258 
259     TEST_CONSTEXPR_CXX14 reference operator*() const {return *ptr_;}
260     TEST_CONSTEXPR_CXX14 pointer operator->() const {return ptr_;}
261 
262     TEST_CONSTEXPR_CXX14 min_pointer& operator++() {++ptr_; return *this;}
263     TEST_CONSTEXPR_CXX14 min_pointer operator++(int) {min_pointer tmp(*this); ++ptr_; return tmp;}
264 
265     TEST_CONSTEXPR_CXX14 min_pointer& operator--() {--ptr_; return *this;}
266     TEST_CONSTEXPR_CXX14 min_pointer operator--(int) {min_pointer tmp(*this); --ptr_; return tmp;}
267 
268     TEST_CONSTEXPR_CXX14 min_pointer& operator+=(difference_type n) {ptr_ += n; return *this;}
269     TEST_CONSTEXPR_CXX14 min_pointer& operator-=(difference_type n) {ptr_ -= n; return *this;}
270 
271     TEST_CONSTEXPR_CXX14 min_pointer operator+(difference_type n) const
272     {
273         min_pointer tmp(*this);
274         tmp += n;
275         return tmp;
276     }
277 
278     friend TEST_CONSTEXPR_CXX14 min_pointer operator+(difference_type n, min_pointer x)
279     {
280         return x + n;
281     }
282 
283     TEST_CONSTEXPR_CXX14 min_pointer operator-(difference_type n) const
284     {
285         min_pointer tmp(*this);
286         tmp -= n;
287         return tmp;
288     }
289 
290     friend TEST_CONSTEXPR_CXX14 difference_type operator-(min_pointer x, min_pointer y)
291     {
292         return x.ptr_ - y.ptr_;
293     }
294 
295     TEST_CONSTEXPR_CXX14 reference operator[](difference_type n) const {return ptr_[n];}
296 
297     friend TEST_CONSTEXPR_CXX14 bool operator< (min_pointer x, min_pointer y) {return x.ptr_ < y.ptr_;}
298     friend TEST_CONSTEXPR_CXX14 bool operator> (min_pointer x, min_pointer y) {return y < x;}
299     friend TEST_CONSTEXPR_CXX14 bool operator<=(min_pointer x, min_pointer y) {return !(y < x);}
300     friend TEST_CONSTEXPR_CXX14 bool operator>=(min_pointer x, min_pointer y) {return !(x < y);}
301 
pointer_to(T & t)302     static TEST_CONSTEXPR_CXX14 min_pointer pointer_to(T& t) {return min_pointer(std::addressof(t));}
303 
304     friend TEST_CONSTEXPR_CXX14 bool operator==(min_pointer x, min_pointer y) {return x.ptr_ == y.ptr_;}
305     friend TEST_CONSTEXPR_CXX14 bool operator!=(min_pointer x, min_pointer y) {return !(x == y);}
306     template <class U, class XID> friend class min_pointer;
307     template <class U> friend class min_allocator;
308 };
309 
310 template <class T, class ID>
311 class min_pointer<const T, ID>
312 {
313     const T* ptr_;
314 
min_pointer(const T * p)315     TEST_CONSTEXPR_CXX14 explicit min_pointer(const T* p) : ptr_(p) {}
316 public:
317     min_pointer() TEST_NOEXCEPT = default;
min_pointer(std::nullptr_t)318     TEST_CONSTEXPR_CXX14 min_pointer(std::nullptr_t) : ptr_(nullptr) {}
min_pointer(min_pointer<T,ID> p)319     TEST_CONSTEXPR_CXX14 min_pointer(min_pointer<T, ID> p) : ptr_(p.ptr_) {}
min_pointer(min_pointer<const void,ID> p)320     TEST_CONSTEXPR_CXX14 explicit min_pointer(min_pointer<const void, ID> p) : ptr_(static_cast<const T*>(p.ptr_)) {}
321 
322     TEST_CONSTEXPR_CXX14 explicit operator bool() const {return ptr_ != nullptr;}
323 
324     typedef std::ptrdiff_t difference_type;
325     typedef const T& reference;
326     typedef const T* pointer;
327     typedef const T value_type;
328     typedef std::random_access_iterator_tag iterator_category;
329 
330     TEST_CONSTEXPR_CXX14 reference operator*() const {return *ptr_;}
331     TEST_CONSTEXPR_CXX14 pointer operator->() const {return ptr_;}
332 
333     TEST_CONSTEXPR_CXX14 min_pointer& operator++() {++ptr_; return *this;}
334     TEST_CONSTEXPR_CXX14 min_pointer operator++(int) {min_pointer tmp(*this); ++ptr_; return tmp;}
335 
336     TEST_CONSTEXPR_CXX14 min_pointer& operator--() {--ptr_; return *this;}
337     TEST_CONSTEXPR_CXX14 min_pointer operator--(int) {min_pointer tmp(*this); --ptr_; return tmp;}
338 
339     TEST_CONSTEXPR_CXX14 min_pointer& operator+=(difference_type n) {ptr_ += n; return *this;}
340     TEST_CONSTEXPR_CXX14 min_pointer& operator-=(difference_type n) {ptr_ -= n; return *this;}
341 
342     TEST_CONSTEXPR_CXX14 min_pointer operator+(difference_type n) const
343     {
344         min_pointer tmp(*this);
345         tmp += n;
346         return tmp;
347     }
348 
349     friend TEST_CONSTEXPR_CXX14 min_pointer operator+(difference_type n, min_pointer x)
350     {
351         return x + n;
352     }
353 
354     TEST_CONSTEXPR_CXX14 min_pointer operator-(difference_type n) const
355     {
356         min_pointer tmp(*this);
357         tmp -= n;
358         return tmp;
359     }
360 
361     friend TEST_CONSTEXPR_CXX14 difference_type operator-(min_pointer x, min_pointer y)
362     {
363         return x.ptr_ - y.ptr_;
364     }
365 
366     TEST_CONSTEXPR_CXX14 reference operator[](difference_type n) const {return ptr_[n];}
367 
368     friend TEST_CONSTEXPR_CXX14 bool operator< (min_pointer x, min_pointer y) {return x.ptr_ < y.ptr_;}
369     friend TEST_CONSTEXPR_CXX14 bool operator> (min_pointer x, min_pointer y) {return y < x;}
370     friend TEST_CONSTEXPR_CXX14 bool operator<=(min_pointer x, min_pointer y) {return !(y < x);}
371     friend TEST_CONSTEXPR_CXX14 bool operator>=(min_pointer x, min_pointer y) {return !(x < y);}
372 
pointer_to(const T & t)373     static TEST_CONSTEXPR_CXX14 min_pointer pointer_to(const T& t) {return min_pointer(std::addressof(t));}
374 
375     friend TEST_CONSTEXPR_CXX14 bool operator==(min_pointer x, min_pointer y) {return x.ptr_ == y.ptr_;}
376     friend TEST_CONSTEXPR_CXX14 bool operator!=(min_pointer x, min_pointer y) {return x.ptr_ != y.ptr_;}
377     friend TEST_CONSTEXPR_CXX14 bool operator==(min_pointer x, std::nullptr_t) {return x.ptr_ == nullptr;}
378     friend TEST_CONSTEXPR_CXX14 bool operator!=(min_pointer x, std::nullptr_t) {return x.ptr_ != nullptr;}
379     friend TEST_CONSTEXPR_CXX14 bool operator==(std::nullptr_t, min_pointer x) {return x.ptr_ == nullptr;}
380     friend TEST_CONSTEXPR_CXX14 bool operator!=(std::nullptr_t, min_pointer x) {return x.ptr_ != nullptr;}
381     template <class U, class XID> friend class min_pointer;
382 };
383 
384 template <class T>
385 class min_allocator
386 {
387 public:
388     typedef T value_type;
389     typedef min_pointer<T> pointer;
390 
391     min_allocator() = default;
392     template <class U>
min_allocator(min_allocator<U>)393     TEST_CONSTEXPR_CXX20 min_allocator(min_allocator<U>) {}
394 
allocate(std::ptrdiff_t n)395     TEST_CONSTEXPR_CXX20 pointer allocate(std::ptrdiff_t n)
396     {
397         return pointer(std::allocator<T>().allocate(n));
398     }
399 
deallocate(pointer p,std::ptrdiff_t n)400     TEST_CONSTEXPR_CXX20 void deallocate(pointer p, std::ptrdiff_t n)
401     {
402         std::allocator<T>().deallocate(p.ptr_, n);
403     }
404 
405     TEST_CONSTEXPR_CXX20 friend bool operator==(min_allocator, min_allocator) {return true;}
406     TEST_CONSTEXPR_CXX20 friend bool operator!=(min_allocator x, min_allocator y) {return !(x == y);}
407 };
408 
409 template <class T>
410 class explicit_allocator
411 {
412 public:
413     typedef T value_type;
414 
explicit_allocator()415     TEST_CONSTEXPR_CXX20 explicit_allocator() TEST_NOEXCEPT {}
416 
417     template <class U>
explicit_allocator(explicit_allocator<U>)418     TEST_CONSTEXPR_CXX20 explicit explicit_allocator(explicit_allocator<U>) TEST_NOEXCEPT {}
419 
allocate(std::size_t n)420     TEST_CONSTEXPR_CXX20 T* allocate(std::size_t n)
421     {
422         return static_cast<T*>(std::allocator<T>().allocate(n));
423     }
424 
deallocate(T * p,std::size_t n)425     TEST_CONSTEXPR_CXX20 void deallocate(T* p, std::size_t n)
426     {
427         std::allocator<T>().deallocate(p, n);
428     }
429 
430     TEST_CONSTEXPR_CXX20 friend bool operator==(explicit_allocator, explicit_allocator) {return true;}
431     TEST_CONSTEXPR_CXX20 friend bool operator!=(explicit_allocator x, explicit_allocator y) {return !(x == y);}
432 };
433 
434 #endif // MIN_ALLOCATOR_H
435