519 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 TEST_ALLOCATOR_H10#define TEST_ALLOCATOR_H11 12#include <type_traits>13#include <new>14#include <memory>15#include <utility>16#include <cstddef>17#include <cstdlib>18#include <climits>19#include <cassert>20 21#include "test_macros.h"22 23template <class Alloc>24TEST_CONSTEXPR_CXX20 inline typename std::allocator_traits<Alloc>::size_type alloc_max_size(Alloc const& a) {25 typedef std::allocator_traits<Alloc> AT;26 return AT::max_size(a);27}28 29struct test_allocator_statistics {30 int time_to_throw = 0;31 int throw_after = INT_MAX;32 int count = 0; // the number of active instances33 int alloc_count = 0; // the number of allocations not deallocating34 int allocated_size = 0; // the size of allocated elements35 int construct_count = 0; // the number of times that ::construct was called36 int destroy_count = 0; // the number of times that ::destroy was called37 int copied = 0;38 int moved = 0;39 int converted = 0;40 41 TEST_CONSTEXPR_CXX14 void clear() {42 assert(count == 0 && "clearing leaking allocator data?");43 count = 0;44 time_to_throw = 0;45 alloc_count = 0;46 allocated_size = 0;47 construct_count = 0;48 destroy_count = 0;49 throw_after = INT_MAX;50 clear_ctor_counters();51 }52 53 TEST_CONSTEXPR_CXX14 void clear_ctor_counters() {54 copied = 0;55 moved = 0;56 converted = 0;57 }58};59 60struct test_alloc_base {61 TEST_CONSTEXPR static const int destructed_value = -1;62 TEST_CONSTEXPR static const int moved_value = INT_MAX;63};64 65template <class T>66class test_allocator {67 int data_ = 0; // participates in equality68 int id_ = 0; // unique identifier, doesn't participate in equality69 test_allocator_statistics* stats_ = nullptr;70 71 template <class U>72 friend class test_allocator;73 74public:75 typedef unsigned size_type;76 typedef int difference_type;77 typedef T value_type;78 typedef value_type* pointer;79 typedef const value_type* const_pointer;80 typedef typename std::add_lvalue_reference<value_type>::type reference;81 typedef typename std::add_lvalue_reference<const value_type>::type const_reference;82 83 template <class U>84 struct rebind {85 typedef test_allocator<U> other;86 };87 88 TEST_CONSTEXPR test_allocator() TEST_NOEXCEPT = default;89 90 TEST_CONSTEXPR_CXX14 explicit test_allocator(test_allocator_statistics* stats) TEST_NOEXCEPT : stats_(stats) {91 if (stats_ != nullptr)92 ++stats_->count;93 }94 95 TEST_CONSTEXPR explicit test_allocator(int data) TEST_NOEXCEPT : data_(data) {}96 97 TEST_CONSTEXPR_CXX14 explicit test_allocator(int data, test_allocator_statistics* stats) TEST_NOEXCEPT98 : data_(data),99 stats_(stats) {100 if (stats != nullptr)101 ++stats_->count;102 }103 104 TEST_CONSTEXPR explicit test_allocator(int data, int id) TEST_NOEXCEPT : data_(data), id_(id) {}105 106 TEST_CONSTEXPR_CXX14 explicit test_allocator(int data, int id, test_allocator_statistics* stats) TEST_NOEXCEPT107 : data_(data),108 id_(id),109 stats_(stats) {110 if (stats_ != nullptr)111 ++stats_->count;112 }113 114 TEST_CONSTEXPR_CXX14 test_allocator(const test_allocator& a) TEST_NOEXCEPT115 : data_(a.data_),116 id_(a.id_),117 stats_(a.stats_) {118 assert(a.data_ != test_alloc_base::destructed_value && a.id_ != test_alloc_base::destructed_value &&119 "copying from destroyed allocator");120 if (stats_ != nullptr) {121 ++stats_->count;122 ++stats_->copied;123 }124 }125 126 TEST_CONSTEXPR_CXX14 test_allocator(test_allocator&& a) TEST_NOEXCEPT : data_(a.data_), id_(a.id_), stats_(a.stats_) {127 if (stats_ != nullptr) {128 ++stats_->count;129 ++stats_->moved;130 }131 assert(a.data_ != test_alloc_base::destructed_value && a.id_ != test_alloc_base::destructed_value &&132 "moving from destroyed allocator");133 a.id_ = test_alloc_base::moved_value;134 }135 136 template <class U>137 TEST_CONSTEXPR_CXX14 test_allocator(const test_allocator<U>& a) TEST_NOEXCEPT138 : data_(a.data_),139 id_(a.id_),140 stats_(a.stats_) {141 if (stats_ != nullptr) {142 ++stats_->count;143 ++stats_->converted;144 }145 }146 147 TEST_CONSTEXPR_CXX20 ~test_allocator() TEST_NOEXCEPT {148 assert(data_ != test_alloc_base::destructed_value);149 assert(id_ != test_alloc_base::destructed_value);150 if (stats_ != nullptr)151 --stats_->count;152 data_ = test_alloc_base::destructed_value;153 id_ = test_alloc_base::destructed_value;154 }155 156 TEST_CONSTEXPR pointer address(reference x) const { return &x; }157 TEST_CONSTEXPR const_pointer address(const_reference x) const { return &x; }158 159 TEST_CONSTEXPR_CXX14 pointer allocate(size_type n, const void* = nullptr) {160 assert(data_ != test_alloc_base::destructed_value);161 if (stats_ != nullptr) {162 if (stats_->time_to_throw >= stats_->throw_after)163 TEST_THROW(std::bad_alloc());164 ++stats_->time_to_throw;165 ++stats_->alloc_count;166 stats_->allocated_size += n;167 }168 return std::allocator<value_type>().allocate(n);169 }170 171 TEST_CONSTEXPR_CXX14 void deallocate(pointer p, size_type s) {172 assert(data_ != test_alloc_base::destructed_value);173 if (stats_ != nullptr) {174 --stats_->alloc_count;175 stats_->allocated_size -= s;176 }177 std::allocator<value_type>().deallocate(p, s);178 }179 180 TEST_CONSTEXPR size_type max_size() const TEST_NOEXCEPT { return UINT_MAX / sizeof(T); }181 182 template <class U>183 TEST_CONSTEXPR_CXX20 void construct(pointer p, U&& val) {184 if (stats_ != nullptr)185 ++stats_->construct_count;186#if TEST_STD_VER > 17187 std::construct_at(std::to_address(p), std::forward<U>(val));188#else189 ::new (static_cast<void*>(p)) T(std::forward<U>(val));190#endif191 }192 193 TEST_CONSTEXPR_CXX14 void destroy(pointer p) {194 if (stats_ != nullptr)195 ++stats_->destroy_count;196 p->~T();197 }198 TEST_CONSTEXPR friend bool operator==(const test_allocator& x, const test_allocator& y) { return x.data_ == y.data_; }199 TEST_CONSTEXPR friend bool operator!=(const test_allocator& x, const test_allocator& y) { return !(x == y); }200 201 TEST_CONSTEXPR int get_data() const { return data_; }202 TEST_CONSTEXPR int get_id() const { return id_; }203};204 205template <>206class test_allocator<void> {207 int data_ = 0;208 int id_ = 0;209 test_allocator_statistics* stats_ = nullptr;210 211 template <class U>212 friend class test_allocator;213 214public:215 typedef unsigned size_type;216 typedef int difference_type;217 typedef void value_type;218 typedef value_type* pointer;219 typedef const value_type* const_pointer;220 221 template <class U>222 struct rebind {223 typedef test_allocator<U> other;224 };225 226 TEST_CONSTEXPR test_allocator() TEST_NOEXCEPT = default;227 228 TEST_CONSTEXPR_CXX14 explicit test_allocator(test_allocator_statistics* stats) TEST_NOEXCEPT : stats_(stats) {}229 230 TEST_CONSTEXPR explicit test_allocator(int data) TEST_NOEXCEPT : data_(data) {}231 232 TEST_CONSTEXPR explicit test_allocator(int data, test_allocator_statistics* stats) TEST_NOEXCEPT233 : data_(data),234 stats_(stats) {}235 236 TEST_CONSTEXPR explicit test_allocator(int data, int id) : data_(data), id_(id) {}237 238 TEST_CONSTEXPR_CXX14 explicit test_allocator(int data, int id, test_allocator_statistics* stats) TEST_NOEXCEPT239 : data_(data),240 id_(id),241 stats_(stats) {}242 243 TEST_CONSTEXPR_CXX14 explicit test_allocator(const test_allocator& a) TEST_NOEXCEPT244 : data_(a.data_),245 id_(a.id_),246 stats_(a.stats_) {}247 248 template <class U>249 TEST_CONSTEXPR_CXX14 test_allocator(const test_allocator<U>& a) TEST_NOEXCEPT250 : data_(a.data_),251 id_(a.id_),252 stats_(a.stats_) {}253 254 TEST_CONSTEXPR_CXX20 ~test_allocator() TEST_NOEXCEPT {255 data_ = test_alloc_base::destructed_value;256 id_ = test_alloc_base::destructed_value;257 }258 259 TEST_CONSTEXPR int get_id() const { return id_; }260 TEST_CONSTEXPR int get_data() const { return data_; }261 262 TEST_CONSTEXPR friend bool operator==(const test_allocator& x, const test_allocator& y) { return x.data_ == y.data_; }263 TEST_CONSTEXPR friend bool operator!=(const test_allocator& x, const test_allocator& y) { return !(x == y); }264};265 266template <class T>267class other_allocator {268 int data_ = -1;269 270 template <class U>271 friend class other_allocator;272 273public:274 typedef T value_type;275 276 TEST_CONSTEXPR_CXX14 other_allocator() {}277 TEST_CONSTEXPR_CXX14 explicit other_allocator(int i) : data_(i) {}278 279 template <class U>280 TEST_CONSTEXPR_CXX14 other_allocator(const other_allocator<U>& a) : data_(a.data_) {}281 282 TEST_CONSTEXPR_CXX20 T* allocate(std::size_t n) { return std::allocator<value_type>().allocate(n); }283 TEST_CONSTEXPR_CXX20 void deallocate(T* p, std::size_t s) { std::allocator<value_type>().deallocate(p, s); }284 285 TEST_CONSTEXPR_CXX14 other_allocator select_on_container_copy_construction() const { return other_allocator(-2); }286 287 TEST_CONSTEXPR_CXX14 friend bool operator==(const other_allocator& x, const other_allocator& y) {288 return x.data_ == y.data_;289 }290 291 TEST_CONSTEXPR_CXX14 friend bool operator!=(const other_allocator& x, const other_allocator& y) { return !(x == y); }292 TEST_CONSTEXPR int get_data() const { return data_; }293 294 typedef std::true_type propagate_on_container_copy_assignment;295 typedef std::true_type propagate_on_container_move_assignment;296 typedef std::true_type propagate_on_container_swap;297 298#if TEST_STD_VER < 11299 std::size_t max_size() const { return UINT_MAX / sizeof(T); }300#endif301};302 303struct Ctor_Tag {};304 305template <typename T>306class TaggingAllocator;307 308struct Tag_X {309 // All constructors must be passed the Tag type.310 311 // DefaultInsertable into vector<X, TaggingAllocator<X>>,312 TEST_CONSTEXPR Tag_X(Ctor_Tag) {}313 // CopyInsertable into vector<X, TaggingAllocator<X>>,314 TEST_CONSTEXPR Tag_X(Ctor_Tag, const Tag_X&) {}315 // MoveInsertable into vector<X, TaggingAllocator<X>>, and316 TEST_CONSTEXPR Tag_X(Ctor_Tag, Tag_X&&) {}317 318 // EmplaceConstructible into vector<X, TaggingAllocator<X>> from args.319 template <typename... Args>320 TEST_CONSTEXPR Tag_X(Ctor_Tag, Args&&...) {}321 322 // not DefaultConstructible, CopyConstructible or MoveConstructible.323 Tag_X() = delete;324 Tag_X(const Tag_X&) = delete;325 Tag_X(Tag_X&&) = delete;326 327 // CopyAssignable.328 TEST_CONSTEXPR_CXX14 Tag_X& operator=(const Tag_X&) { return *this; };329 330 // MoveAssignable.331 TEST_CONSTEXPR_CXX14 Tag_X& operator=(Tag_X&&) { return *this; };332 333private:334 ~Tag_X() = default;335 // Erasable from vector<X, TaggingAllocator<X>>.336 friend class TaggingAllocator<Tag_X>;337};338 339template <typename T>340class TaggingAllocator {341public:342 using value_type = T;343 TaggingAllocator() = default;344 345 template <typename U>346 TEST_CONSTEXPR TaggingAllocator(const TaggingAllocator<U>&) {}347 348 template <typename... Args>349 TEST_CONSTEXPR_CXX20 void construct(Tag_X* p, Args&&... args) {350#if TEST_STD_VER > 17351 std::construct_at(p, Ctor_Tag{}, std::forward<Args>(args)...);352#else353 ::new (static_cast<void*>(p)) Tag_X(Ctor_Tag(), std::forward<Args>(args)...);354#endif355 }356 357 template <typename U>358 TEST_CONSTEXPR_CXX20 void destroy(U* p) {359 p->~U();360 }361 362 TEST_CONSTEXPR_CXX20 T* allocate(std::size_t n) { return std::allocator<T>().allocate(n); }363 TEST_CONSTEXPR_CXX20 void deallocate(T* p, std::size_t n) { std::allocator<T>().deallocate(p, n); }364};365 366template <std::size_t MaxAllocs>367struct limited_alloc_handle {368 std::size_t outstanding_ = 0;369 void* last_alloc_ = nullptr;370 371 template <class T>372 TEST_CONSTEXPR_CXX20 T* allocate(std::size_t N) {373 if (N + outstanding_ > MaxAllocs)374 TEST_THROW(std::bad_alloc());375 auto alloc = std::allocator<T>().allocate(N);376 last_alloc_ = alloc;377 outstanding_ += N;378 return alloc;379 }380 381 template <class T>382 TEST_CONSTEXPR_CXX20 void deallocate(T* ptr, std::size_t N) {383 if (ptr == last_alloc_) {384 last_alloc_ = nullptr;385 assert(outstanding_ >= N);386 outstanding_ -= N;387 }388 std::allocator<T>().deallocate(ptr, N);389 }390};391 392namespace detail {393template <class T>394class thread_unsafe_shared_ptr {395public:396 thread_unsafe_shared_ptr() = default;397 398 TEST_CONSTEXPR_CXX14 thread_unsafe_shared_ptr(const thread_unsafe_shared_ptr& other) : block(other.block) {399 ++block->ref_count;400 }401 402 TEST_CONSTEXPR_CXX20 ~thread_unsafe_shared_ptr() {403 --block->ref_count;404 if (block->ref_count != 0)405 return;406 typedef std::allocator_traits<std::allocator<control_block> > allocator_traits;407 std::allocator<control_block> alloc;408 allocator_traits::destroy(alloc, block);409 allocator_traits::deallocate(alloc, block, 1);410 }411 412 TEST_CONSTEXPR const T& operator*() const { return block->content; }413 TEST_CONSTEXPR const T* operator->() const { return &block->content; }414 TEST_CONSTEXPR_CXX14 T& operator*() { return block->content; }415 TEST_CONSTEXPR_CXX14 T* operator->() { return &block->content; }416 TEST_CONSTEXPR_CXX14 T* get() { return &block->content; }417 TEST_CONSTEXPR const T* get() const { return &block->content; }418 419private:420 struct control_block {421 template <class... Args>422 TEST_CONSTEXPR control_block(Args... args) : content(std::forward<Args>(args)...) {}423 std::size_t ref_count = 1;424 T content;425 };426 427 control_block* block = nullptr;428 429 template <class U, class... Args>430 friend TEST_CONSTEXPR_CXX20 thread_unsafe_shared_ptr<U> make_thread_unsafe_shared(Args...);431};432 433template <class T, class... Args>434TEST_CONSTEXPR_CXX20 thread_unsafe_shared_ptr<T> make_thread_unsafe_shared(Args... args) {435 typedef typename thread_unsafe_shared_ptr<T>::control_block control_block_type;436 typedef std::allocator_traits<std::allocator<control_block_type> > allocator_traits;437 438 thread_unsafe_shared_ptr<T> ptr;439 std::allocator<control_block_type> alloc;440 ptr.block = allocator_traits::allocate(alloc, 1);441 allocator_traits::construct(alloc, ptr.block, std::forward<Args>(args)...);442 443 return ptr;444}445} // namespace detail446 447template <class T, std::size_t N>448class limited_allocator {449 template <class U, std::size_t UN>450 friend class limited_allocator;451 typedef limited_alloc_handle<N> BuffT;452 detail::thread_unsafe_shared_ptr<BuffT> handle_;453 454public:455 typedef T value_type;456 typedef value_type* pointer;457 typedef const value_type* const_pointer;458 typedef value_type& reference;459 typedef const value_type& const_reference;460 typedef std::size_t size_type;461 typedef std::ptrdiff_t difference_type;462 463 template <class U>464 struct rebind {465 typedef limited_allocator<U, N> other;466 };467 468 TEST_CONSTEXPR_CXX20 limited_allocator() : handle_(detail::make_thread_unsafe_shared<BuffT>()) {}469 470 limited_allocator(limited_allocator const&) = default;471 472 template <class U>473 TEST_CONSTEXPR explicit limited_allocator(limited_allocator<U, N> const& other) : handle_(other.handle_) {}474 475 limited_allocator& operator=(const limited_allocator&) = delete;476 477 TEST_CONSTEXPR_CXX20 pointer allocate(size_type n) { return handle_->template allocate<T>(n); }478 TEST_CONSTEXPR_CXX20 void deallocate(pointer p, size_type n) { handle_->template deallocate<T>(p, n); }479 TEST_CONSTEXPR size_type max_size() const { return N; }480 TEST_CONSTEXPR const BuffT* getHandle() const { return handle_.get(); }481};482 483template <class T, class U, std::size_t N>484TEST_CONSTEXPR inline bool operator==(limited_allocator<T, N> const& LHS, limited_allocator<U, N> const& RHS) {485 return LHS.getHandle() == RHS.getHandle();486}487 488template <class T, class U, std::size_t N>489TEST_CONSTEXPR inline bool operator!=(limited_allocator<T, N> const& LHS, limited_allocator<U, N> const& RHS) {490 return !(LHS == RHS);491}492 493// Track the "provenance" of this allocator instance: how many times was494// select_on_container_copy_construction called in order to produce it?495//496template <class T>497struct SocccAllocator {498 using value_type = T;499 500 int count_ = 0;501 explicit SocccAllocator(int i) : count_(i) {}502 503 template <class U>504 SocccAllocator(const SocccAllocator<U>& a) : count_(a.count_) {}505 506 T* allocate(std::size_t n) { return std::allocator<T>().allocate(n); }507 void deallocate(T* p, std::size_t n) { std::allocator<T>().deallocate(p, n); }508 509 SocccAllocator select_on_container_copy_construction() const { return SocccAllocator(count_ + 1); }510 511 bool operator==(const SocccAllocator&) const { return true; }512 513 using propagate_on_container_copy_assignment = std::false_type;514 using propagate_on_container_move_assignment = std::false_type;515 using propagate_on_container_swap = std::false_type;516};517 518#endif // TEST_ALLOCATOR_H519