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