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