518 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef MIN_ALLOCATOR_H10#define MIN_ALLOCATOR_H11 12#include <cassert>13#include <climits>14#include <cstddef>15#include <cstdlib>16#include <iterator>17#include <memory>18#include <new>19#include <type_traits>20#include <cstring>21 22#include "test_macros.h"23 24template <class T>25class bare_allocator {26public:27 typedef T value_type;28 29 bare_allocator() TEST_NOEXCEPT {}30 31 template <class U>32 bare_allocator(bare_allocator<U>) TEST_NOEXCEPT {}33 34 T* allocate(std::size_t n) { return static_cast<T*>(::operator new(n * sizeof(T))); }35 36 void deallocate(T* p, std::size_t) { return ::operator delete(static_cast<void*>(p)); }37 38 friend bool operator==(bare_allocator, bare_allocator) { return true; }39 friend bool operator!=(bare_allocator x, bare_allocator y) { return !(x == y); }40};41 42template <class T>43class no_default_allocator {44#if TEST_STD_VER >= 1145 no_default_allocator() = delete;46#else47 no_default_allocator();48#endif49 struct construct_tag {};50 TEST_CONSTEXPR_CXX20 explicit no_default_allocator(construct_tag) {}51 52public:53 TEST_CONSTEXPR_CXX20 static no_default_allocator create() {54 construct_tag tag;55 return no_default_allocator(tag);56 }57 58public:59 typedef T value_type;60 61 template <class U>62 TEST_CONSTEXPR_CXX20 no_default_allocator(no_default_allocator<U>) TEST_NOEXCEPT {}63 64 TEST_CONSTEXPR_CXX20 T* allocate(std::size_t n) { return static_cast<T*>(std::allocator<T>().allocate(n)); }65 66 TEST_CONSTEXPR_CXX20 void deallocate(T* p, std::size_t n) { std::allocator<T>().deallocate(p, n); }67 68 friend TEST_CONSTEXPR bool operator==(no_default_allocator, no_default_allocator) { return true; }69 friend TEST_CONSTEXPR bool operator!=(no_default_allocator x, no_default_allocator y) { return !(x == y); }70};71 72struct malloc_allocator_base {73 static std::size_t outstanding_bytes;74 static std::size_t alloc_count;75 static std::size_t dealloc_count;76 static bool disable_default_constructor;77 78 static std::size_t outstanding_alloc() {79 assert(alloc_count >= dealloc_count);80 return (alloc_count - dealloc_count);81 }82 83 static void reset() {84 assert(outstanding_alloc() == 0);85 disable_default_constructor = false;86 outstanding_bytes = 0;87 alloc_count = 0;88 dealloc_count = 0;89 }90};91 92size_t malloc_allocator_base::outstanding_bytes = 0;93size_t malloc_allocator_base::alloc_count = 0;94size_t malloc_allocator_base::dealloc_count = 0;95bool malloc_allocator_base::disable_default_constructor = false;96 97template <class T>98class malloc_allocator : public malloc_allocator_base {99public:100 typedef T value_type;101 102 malloc_allocator() TEST_NOEXCEPT { assert(!disable_default_constructor); }103 104 template <class U>105 malloc_allocator(malloc_allocator<U>) TEST_NOEXCEPT {}106 107 T* allocate(std::size_t n) {108 const std::size_t nbytes = n * sizeof(T);109 ++alloc_count;110 outstanding_bytes += nbytes;111 return static_cast<T*>(std::malloc(nbytes));112 }113 114 void deallocate(T* p, std::size_t n) {115 const std::size_t nbytes = n * sizeof(T);116 ++dealloc_count;117 outstanding_bytes -= nbytes;118 std::free(static_cast<void*>(p));119 }120 121 friend bool operator==(malloc_allocator, malloc_allocator) { return true; }122 friend bool operator!=(malloc_allocator x, malloc_allocator y) { return !(x == y); }123};124 125template <class T>126struct cpp03_allocator : bare_allocator<T> {127 typedef T value_type;128 typedef value_type* pointer;129 130 static bool construct_called;131 132 // Returned value is not used but it's not prohibited.133 pointer construct(pointer p, const value_type& val) {134 ::new (p) value_type(val);135 construct_called = true;136 return p;137 }138 139 std::size_t max_size() const { return UINT_MAX / sizeof(T); }140};141template <class T>142bool cpp03_allocator<T>::construct_called = false;143 144template <class T>145struct cpp03_overload_allocator : bare_allocator<T> {146 typedef T value_type;147 typedef value_type* pointer;148 149 static bool construct_called;150 151 void construct(pointer p, const value_type& val) { construct(p, val, std::is_class<T>()); }152 void construct(pointer p, const value_type& val, std::true_type) {153 ::new (p) value_type(val);154 construct_called = true;155 }156 void construct(pointer p, const value_type& val, std::false_type) {157 ::new (p) value_type(val);158 construct_called = true;159 }160 161 std::size_t max_size() const { return UINT_MAX / sizeof(T); }162};163template <class T>164bool cpp03_overload_allocator<T>::construct_called = false;165 166template <class T, class = std::integral_constant<std::size_t, 0> >167class min_pointer;168template <class T, class ID>169class min_pointer<const T, ID>;170template <class ID>171class min_pointer<void, ID>;172template <class ID>173class min_pointer<const void, ID>;174template <class T>175class min_allocator;176 177template <class ID>178class min_pointer<const void, ID> {179 const void* ptr_;180 181public:182 min_pointer() TEST_NOEXCEPT = default;183 min_pointer(std::nullptr_t) TEST_NOEXCEPT : ptr_(nullptr) {}184 template <class T>185 min_pointer(min_pointer<T, ID> p) TEST_NOEXCEPT : ptr_(p.ptr_) {}186 187 explicit operator bool() const { return ptr_ != nullptr; }188 189 friend bool operator==(min_pointer x, min_pointer y) { return x.ptr_ == y.ptr_; }190 friend bool operator!=(min_pointer x, min_pointer y) { return !(x == y); }191 template <class U, class XID>192 friend class min_pointer;193};194 195template <class ID>196class min_pointer<void, ID> {197 void* ptr_;198 199public:200 min_pointer() TEST_NOEXCEPT = default;201 TEST_CONSTEXPR_CXX14 min_pointer(std::nullptr_t) TEST_NOEXCEPT : ptr_(nullptr) {}202 template <class T, class = typename std::enable_if< !std::is_const<T>::value >::type >203 TEST_CONSTEXPR_CXX14 min_pointer(min_pointer<T, ID> p) TEST_NOEXCEPT : ptr_(p.ptr_) {}204 205 TEST_CONSTEXPR_CXX14 explicit operator bool() const { return ptr_ != nullptr; }206 207 TEST_CONSTEXPR_CXX14 friend bool operator==(min_pointer x, min_pointer y) { return x.ptr_ == y.ptr_; }208 TEST_CONSTEXPR_CXX14 friend bool operator!=(min_pointer x, min_pointer y) { return !(x == y); }209 template <class U, class XID>210 friend class min_pointer;211};212 213template <class T, class ID>214class min_pointer {215 T* ptr_;216 217 TEST_CONSTEXPR_CXX14 explicit min_pointer(T* p) TEST_NOEXCEPT : ptr_(p) {}218 219public:220 min_pointer() TEST_NOEXCEPT = default;221 TEST_CONSTEXPR_CXX14 min_pointer(std::nullptr_t) TEST_NOEXCEPT : ptr_(nullptr) {}222 TEST_CONSTEXPR_CXX14 explicit min_pointer(min_pointer<void, ID> p) TEST_NOEXCEPT : ptr_(static_cast<T*>(p.ptr_)) {}223 224 TEST_CONSTEXPR_CXX14 explicit operator bool() const { return ptr_ != nullptr; }225 226 typedef std::ptrdiff_t difference_type;227 typedef T& reference;228 typedef T* pointer;229 typedef T value_type;230 typedef std::random_access_iterator_tag iterator_category;231 232 TEST_CONSTEXPR_CXX14 reference operator*() const { return *ptr_; }233 TEST_CONSTEXPR_CXX14 pointer operator->() const { return ptr_; }234 235 TEST_CONSTEXPR_CXX14 min_pointer& operator++() {236 ++ptr_;237 return *this;238 }239 TEST_CONSTEXPR_CXX14 min_pointer operator++(int) {240 min_pointer tmp(*this);241 ++ptr_;242 return tmp;243 }244 245 TEST_CONSTEXPR_CXX14 min_pointer& operator--() {246 --ptr_;247 return *this;248 }249 TEST_CONSTEXPR_CXX14 min_pointer operator--(int) {250 min_pointer tmp(*this);251 --ptr_;252 return tmp;253 }254 255 TEST_CONSTEXPR_CXX14 min_pointer& operator+=(difference_type n) {256 ptr_ += n;257 return *this;258 }259 TEST_CONSTEXPR_CXX14 min_pointer& operator-=(difference_type n) {260 ptr_ -= n;261 return *this;262 }263 264 TEST_CONSTEXPR_CXX14 min_pointer operator+(difference_type n) const {265 min_pointer tmp(*this);266 tmp += n;267 return tmp;268 }269 270 friend TEST_CONSTEXPR_CXX14 min_pointer operator+(difference_type n, min_pointer x) { return x + n; }271 272 TEST_CONSTEXPR_CXX14 min_pointer operator-(difference_type n) const {273 min_pointer tmp(*this);274 tmp -= n;275 return tmp;276 }277 278 friend TEST_CONSTEXPR_CXX14 difference_type operator-(min_pointer x, min_pointer y) { return x.ptr_ - y.ptr_; }279 280 TEST_CONSTEXPR_CXX14 reference operator[](difference_type n) const { return ptr_[n]; }281 282 friend TEST_CONSTEXPR_CXX14 bool operator<(min_pointer x, min_pointer y) { return x.ptr_ < y.ptr_; }283 friend TEST_CONSTEXPR_CXX14 bool operator>(min_pointer x, min_pointer y) { return y < x; }284 friend TEST_CONSTEXPR_CXX14 bool operator<=(min_pointer x, min_pointer y) { return !(y < x); }285 friend TEST_CONSTEXPR_CXX14 bool operator>=(min_pointer x, min_pointer y) { return !(x < y); }286 287 static TEST_CONSTEXPR_CXX14 min_pointer pointer_to(T& t) { return min_pointer(std::addressof(t)); }288 289 friend TEST_CONSTEXPR_CXX14 bool operator==(min_pointer x, min_pointer y) { return x.ptr_ == y.ptr_; }290 friend TEST_CONSTEXPR_CXX14 bool operator!=(min_pointer x, min_pointer y) { return !(x == y); }291 template <class U, class XID>292 friend class min_pointer;293 template <class U>294 friend class min_allocator;295};296 297template <class T, class ID>298class min_pointer<const T, ID> {299 const T* ptr_;300 301 TEST_CONSTEXPR_CXX14 explicit min_pointer(const T* p) : ptr_(p) {}302 303public:304 min_pointer() TEST_NOEXCEPT = default;305 TEST_CONSTEXPR_CXX14 min_pointer(std::nullptr_t) : ptr_(nullptr) {}306 TEST_CONSTEXPR_CXX14 min_pointer(min_pointer<T, ID> p) : ptr_(p.ptr_) {}307 TEST_CONSTEXPR_CXX14 explicit min_pointer(min_pointer<const void, ID> p) : ptr_(static_cast<const T*>(p.ptr_)) {}308 309 TEST_CONSTEXPR_CXX14 explicit operator bool() const { return ptr_ != nullptr; }310 311 typedef std::ptrdiff_t difference_type;312 typedef const T& reference;313 typedef const T* pointer;314 typedef const T value_type;315 typedef std::random_access_iterator_tag iterator_category;316 317 TEST_CONSTEXPR_CXX14 reference operator*() const { return *ptr_; }318 TEST_CONSTEXPR_CXX14 pointer operator->() const { return ptr_; }319 320 TEST_CONSTEXPR_CXX14 min_pointer& operator++() {321 ++ptr_;322 return *this;323 }324 TEST_CONSTEXPR_CXX14 min_pointer operator++(int) {325 min_pointer tmp(*this);326 ++ptr_;327 return tmp;328 }329 330 TEST_CONSTEXPR_CXX14 min_pointer& operator--() {331 --ptr_;332 return *this;333 }334 TEST_CONSTEXPR_CXX14 min_pointer operator--(int) {335 min_pointer tmp(*this);336 --ptr_;337 return tmp;338 }339 340 TEST_CONSTEXPR_CXX14 min_pointer& operator+=(difference_type n) {341 ptr_ += n;342 return *this;343 }344 TEST_CONSTEXPR_CXX14 min_pointer& operator-=(difference_type n) {345 ptr_ -= n;346 return *this;347 }348 349 TEST_CONSTEXPR_CXX14 min_pointer operator+(difference_type n) const {350 min_pointer tmp(*this);351 tmp += n;352 return tmp;353 }354 355 friend TEST_CONSTEXPR_CXX14 min_pointer operator+(difference_type n, min_pointer x) { return x + n; }356 357 TEST_CONSTEXPR_CXX14 min_pointer operator-(difference_type n) const {358 min_pointer tmp(*this);359 tmp -= n;360 return tmp;361 }362 363 friend TEST_CONSTEXPR_CXX14 difference_type operator-(min_pointer x, min_pointer y) { return x.ptr_ - y.ptr_; }364 365 TEST_CONSTEXPR_CXX14 reference operator[](difference_type n) const { return ptr_[n]; }366 367 friend TEST_CONSTEXPR_CXX14 bool operator<(min_pointer x, min_pointer y) { return x.ptr_ < y.ptr_; }368 friend TEST_CONSTEXPR_CXX14 bool operator>(min_pointer x, min_pointer y) { return y < x; }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 !(x < y); }371 372 static TEST_CONSTEXPR_CXX14 min_pointer pointer_to(const T& t) { return min_pointer(std::addressof(t)); }373 374 friend TEST_CONSTEXPR_CXX14 bool operator==(min_pointer x, min_pointer y) { return x.ptr_ == y.ptr_; }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, std::nullptr_t) { return x.ptr_ == nullptr; }377 friend TEST_CONSTEXPR_CXX14 bool operator!=(min_pointer x, std::nullptr_t) { return x.ptr_ != nullptr; }378 friend TEST_CONSTEXPR_CXX14 bool operator==(std::nullptr_t, min_pointer x) { return x.ptr_ == nullptr; }379 friend TEST_CONSTEXPR_CXX14 bool operator!=(std::nullptr_t, min_pointer x) { return x.ptr_ != nullptr; }380 template <class U, class XID>381 friend class min_pointer;382};383 384template <class T>385class min_allocator {386public:387 typedef T value_type;388 typedef min_pointer<T> pointer;389 390 min_allocator() = default;391 template <class U>392 TEST_CONSTEXPR_CXX20 min_allocator(min_allocator<U>) {}393 394 TEST_CONSTEXPR_CXX20 pointer allocate(std::size_t n) { return pointer(std::allocator<T>().allocate(n)); }395 396 TEST_CONSTEXPR_CXX20 void deallocate(pointer p, std::size_t n) { std::allocator<T>().deallocate(p.ptr_, n); }397 398 TEST_CONSTEXPR_CXX20 friend bool operator==(min_allocator, min_allocator) { return true; }399 TEST_CONSTEXPR_CXX20 friend bool operator!=(min_allocator x, min_allocator y) { return !(x == y); }400};401 402template <class T>403class complete_type_allocator {404public:405 using value_type = T;406 407 // Make sure that value_type is a complete when min_allocator is instantiated408 static_assert(TEST_ALIGNOF(value_type) != 0, "");409 410 TEST_CONSTEXPR_CXX20 complete_type_allocator() TEST_NOEXCEPT {}411 412 template <class U>413 TEST_CONSTEXPR_CXX20 explicit complete_type_allocator(complete_type_allocator<U>) TEST_NOEXCEPT {}414 415 TEST_CONSTEXPR_CXX20 T* allocate(std::size_t n) { return static_cast<T*>(std::allocator<T>().allocate(n)); }416 417 TEST_CONSTEXPR_CXX20 void deallocate(T* p, std::size_t n) { std::allocator<T>().deallocate(p, n); }418 419 TEST_CONSTEXPR_CXX20 friend bool operator==(complete_type_allocator, complete_type_allocator) { return true; }420 TEST_CONSTEXPR_CXX20 friend bool operator!=(complete_type_allocator, complete_type_allocator) { return false; }421};422 423template <class T>424class explicit_allocator425{426public:427 typedef T value_type;428 429 TEST_CONSTEXPR_CXX20 explicit_allocator() TEST_NOEXCEPT {}430 431 template <class U>432 TEST_CONSTEXPR_CXX20 explicit explicit_allocator(explicit_allocator<U>) TEST_NOEXCEPT {}433 434 TEST_CONSTEXPR_CXX20 T* allocate(std::size_t n) { return static_cast<T*>(std::allocator<T>().allocate(n)); }435 436 TEST_CONSTEXPR_CXX20 void deallocate(T* p, std::size_t n) { std::allocator<T>().deallocate(p, n); }437 438 TEST_CONSTEXPR_CXX20 friend bool operator==(explicit_allocator, explicit_allocator) { return true; }439 TEST_CONSTEXPR_CXX20 friend bool operator!=(explicit_allocator x, explicit_allocator y) { return !(x == y); }440};441 442template <class T>443class unaligned_allocator {444public:445 static_assert(TEST_ALIGNOF(T) == 1, "Type T cannot be created on unaligned address (UB)");446 typedef T value_type;447 448 TEST_CONSTEXPR_CXX20 unaligned_allocator() TEST_NOEXCEPT {}449 450 template <class U>451 TEST_CONSTEXPR_CXX20 explicit unaligned_allocator(unaligned_allocator<U>) TEST_NOEXCEPT {}452 453 TEST_CONSTEXPR_CXX20 T* allocate(std::size_t n) { return std::allocator<T>().allocate(n + 1) + 1; }454 455 TEST_CONSTEXPR_CXX20 void deallocate(T* p, std::size_t n) { std::allocator<T>().deallocate(p - 1, n + 1); }456 457 TEST_CONSTEXPR_CXX20 friend bool operator==(unaligned_allocator, unaligned_allocator) { return true; }458 TEST_CONSTEXPR_CXX20 friend bool operator!=(unaligned_allocator x, unaligned_allocator y) { return !(x == y); }459};460 461template <class T>462class safe_allocator {463public:464 typedef T value_type;465 466 TEST_CONSTEXPR_CXX20 safe_allocator() TEST_NOEXCEPT {}467 468 template <class U>469 TEST_CONSTEXPR_CXX20 safe_allocator(safe_allocator<U>) TEST_NOEXCEPT {}470 471 TEST_CONSTEXPR_CXX20 T* allocate(std::size_t n) {472 T* memory = std::allocator<T>().allocate(n);473 if (!TEST_IS_CONSTANT_EVALUATED)474 std::memset(static_cast<void*>(memory), 0, sizeof(T) * n);475 476 return memory;477 }478 479 TEST_CONSTEXPR_CXX20 void deallocate(T* p, std::size_t n) {480 if (!TEST_IS_CONSTANT_EVALUATED)481 DoNotOptimize(std::memset(static_cast<void*>(p), 0, sizeof(T) * n));482 std::allocator<T>().deallocate(p, n);483 }484 485 TEST_CONSTEXPR_CXX20 friend bool operator==(safe_allocator, safe_allocator) { return true; }486 TEST_CONSTEXPR_CXX20 friend bool operator!=(safe_allocator x, safe_allocator y) { return !(x == y); }487};488 489template <std::size_t MaxSize, class T>490struct tiny_size_allocator {491 using value_type = T;492 using size_type = unsigned;493 494 template <class U>495 struct rebind {496 using other = tiny_size_allocator<MaxSize, U>;497 };498 499 tiny_size_allocator() = default;500 501 template <class U>502 TEST_CONSTEXPR_CXX20 tiny_size_allocator(tiny_size_allocator<MaxSize, U>) {}503 504 TEST_CONSTEXPR_CXX20 T* allocate(std::size_t n) {505 assert(n <= MaxSize);506 return std::allocator<T>().allocate(n);507 }508 509 TEST_CONSTEXPR_CXX20 void deallocate(T* ptr, std::size_t n) { std::allocator<T>().deallocate(ptr, n); }510 511 TEST_CONSTEXPR_CXX20 size_type max_size() const { return MaxSize; }512 513 friend bool operator==(tiny_size_allocator, tiny_size_allocator) { return true; }514 friend bool operator!=(tiny_size_allocator, tiny_size_allocator) { return false; }515};516 517#endif // MIN_ALLOCATOR_H518