libcxx/test/support/test_allocator.h

   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