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 TEST_ALLOCATOR_H 10 #define TEST_ALLOCATOR_H 11 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 23 template <class Alloc> 24 TEST_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 29 struct test_allocator_statistics { 30 int time_to_throw = 0; 31 int throw_after = INT_MAX; 32 int count = 0; // the number of active instances 33 int alloc_count = 0; // the number of allocations not deallocating 34 int allocated_size = 0; // the size of allocated elements 35 int construct_count = 0; // the number of times that ::construct was called 36 int destroy_count = 0; // the number of times that ::destroy was called 37 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 60 struct test_alloc_base { 61 TEST_CONSTEXPR static const int destructed_value = -1; 62 TEST_CONSTEXPR static const int moved_value = INT_MAX; 63 }; 64 65 template <class T> 66 class test_allocator { 67 int data_ = 0; // participates in equality 68 int id_ = 0; // unique identifier, doesn't participate in equality 69 test_allocator_statistics* stats_ = nullptr; 70 71 template <class U> 72 friend class test_allocator; 73 74 public: 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_NOEXCEPT 98 : 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_NOEXCEPT 107 : 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_NOEXCEPT 115 : 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_NOEXCEPT 138 : 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 > 17 187 std::construct_at(std::to_address(p), std::forward<U>(val)); 188 #else 189 ::new (static_cast<void*>(p)) T(std::forward<U>(val)); 190 #endif 191 } 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 205 template <> 206 class 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 214 public: 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_NOEXCEPT 233 : 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_NOEXCEPT 239 : data_(data), 240 id_(id), 241 stats_(stats) {} 242 243 TEST_CONSTEXPR_CXX14 explicit test_allocator(const test_allocator& a) TEST_NOEXCEPT 244 : 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_NOEXCEPT 250 : 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 266 template <class T> 267 class other_allocator { 268 int data_ = -1; 269 270 template <class U> 271 friend class other_allocator; 272 273 public: 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 < 11 299 std::size_t max_size() const { return UINT_MAX / sizeof(T); } 300 #endif 301 }; 302 303 struct Ctor_Tag {}; 304 305 template <typename T> 306 class TaggingAllocator; 307 308 struct 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>>, and 316 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 333 private: 334 ~Tag_X() = default; 335 // Erasable from vector<X, TaggingAllocator<X>>. 336 friend class TaggingAllocator<Tag_X>; 337 }; 338 339 template <typename T> 340 class TaggingAllocator { 341 public: 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 > 17 351 std::construct_at(p, Ctor_Tag{}, std::forward<Args>(args)...); 352 #else 353 ::new (static_cast<void*>(p)) Tag_X(Ctor_Tag(), std::forward<Args>(args)...); 354 #endif 355 } 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 366 template <std::size_t MaxAllocs> 367 struct 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 392 namespace detail { 393 template <class T> 394 class thread_unsafe_shared_ptr { 395 public: 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 419 private: 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 433 template <class T, class... Args> 434 TEST_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 detail 446 447 template <class T, std::size_t N> 448 class 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 454 public: 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 483 template <class T, class U, std::size_t N> 484 TEST_CONSTEXPR inline bool operator==(limited_allocator<T, N> const& LHS, limited_allocator<U, N> const& RHS) { 485 return LHS.getHandle() == RHS.getHandle(); 486 } 487 488 template <class T, class U, std::size_t N> 489 TEST_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 was 494 // select_on_container_copy_construction called in order to produce it? 495 // 496 template <class T> 497 struct 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_H 519