1// -*- C++ -*- 2// Testing allocator for the C++ library testsuite. 3// 4// Copyright (C) 2002-2015 Free Software Foundation, Inc. 5// 6// This file is part of the GNU ISO C++ Library. This library is free 7// software; you can redistribute it and/or modify it under the 8// terms of the GNU General Public License as published by the 9// Free Software Foundation; either version 3, or (at your option) 10// any later version. 11// 12// This library is distributed in the hope that it will be useful, 13// but WITHOUT ANY WARRANTY; without even the implied warranty of 14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15// GNU General Public License for more details. 16// 17// You should have received a copy of the GNU General Public License along 18// with this library; see the file COPYING3. If not see 19// <http://www.gnu.org/licenses/>. 20// 21 22// This file provides an test instrumentation allocator that can be 23// used to verify allocation functionality of standard library 24// containers. 2002.11.25 smw 25 26#ifndef _GLIBCXX_TESTSUITE_ALLOCATOR_H 27#define _GLIBCXX_TESTSUITE_ALLOCATOR_H 28 29#include <tr1/unordered_map> 30#include <bits/move.h> 31#include <ext/pointer.h> 32#include <ext/alloc_traits.h> 33#include <testsuite_hooks.h> 34 35namespace __gnu_test 36{ 37 class tracker_allocator_counter 38 { 39 public: 40 typedef std::size_t size_type; 41 42 static void 43 allocate(size_type blocksize) 44 { allocationCount_ += blocksize; } 45 46 static void 47 construct() { ++constructCount_; } 48 49 static void 50 destroy() { ++destructCount_; } 51 52 static void 53 deallocate(size_type blocksize) 54 { deallocationCount_ += blocksize; } 55 56 static size_type 57 get_allocation_count() { return allocationCount_; } 58 59 static size_type 60 get_deallocation_count() { return deallocationCount_; } 61 62 static int 63 get_construct_count() { return constructCount_; } 64 65 static int 66 get_destruct_count() { return destructCount_; } 67 68 static void 69 reset() 70 { 71 allocationCount_ = 0; 72 deallocationCount_ = 0; 73 constructCount_ = 0; 74 destructCount_ = 0; 75 } 76 77 private: 78 static size_type allocationCount_; 79 static size_type deallocationCount_; 80 static int constructCount_; 81 static int destructCount_; 82 }; 83 84 // Helper to detect inconsistency between type used to instantiate an 85 // allocator and the underlying allocator value_type. 86 template<typename T, typename Alloc, 87 typename = typename Alloc::value_type> 88 struct check_consistent_alloc_value_type; 89 90 template<typename T, typename Alloc> 91 struct check_consistent_alloc_value_type<T, Alloc, T> 92 { typedef T value_type; }; 93 94 // An allocator facade that intercepts allocate/deallocate/construct/destroy 95 // calls and track them through the tracker_allocator_counter class. This 96 // class is templated on the target object type, but tracker isn't. 97 template<typename T, typename Alloc = std::allocator<T> > 98 class tracker_allocator : public Alloc 99 { 100 private: 101 typedef tracker_allocator_counter counter_type; 102 103 typedef __gnu_cxx::__alloc_traits<Alloc> AllocTraits; 104 105 public: 106 typedef typename 107 check_consistent_alloc_value_type<T, Alloc>::value_type value_type; 108 typedef typename AllocTraits::pointer pointer; 109 typedef typename AllocTraits::size_type size_type; 110 111 template<class U> 112 struct rebind 113 { 114 typedef tracker_allocator<U, 115 typename AllocTraits::template rebind<U>::other> other; 116 }; 117 118#if __cplusplus >= 201103L 119 tracker_allocator() = default; 120 tracker_allocator(const tracker_allocator&) = default; 121 tracker_allocator(tracker_allocator&&) = default; 122 123 // Perfect forwarding constructor. 124 template<typename... _Args> 125 tracker_allocator(_Args&&... __args) 126 : Alloc(std::forward<_Args>(__args)...) 127 { } 128#else 129 tracker_allocator() 130 { } 131 132 tracker_allocator(const tracker_allocator&) 133 { } 134 135 ~tracker_allocator() 136 { } 137#endif 138 139 template<class U> 140 tracker_allocator(const tracker_allocator<U, 141 typename AllocTraits::template rebind<U>::other>& alloc) 142 _GLIBCXX_USE_NOEXCEPT 143 : Alloc(alloc) 144 { } 145 146 pointer 147 allocate(size_type n, const void* = 0) 148 { 149 pointer p = AllocTraits::allocate(*this, n); 150 counter_type::allocate(n * sizeof(T)); 151 return p; 152 } 153 154#if __cplusplus >= 201103L 155 template<typename U, typename... Args> 156 void 157 construct(U* p, Args&&... args) 158 { 159 AllocTraits::construct(*this, p, std::forward<Args>(args)...); 160 counter_type::construct(); 161 } 162 163 template<typename U> 164 void 165 destroy(U* p) 166 { 167 AllocTraits::destroy(*this, p); 168 counter_type::destroy(); 169 } 170#else 171 void 172 construct(pointer p, const T& value) 173 { 174 AllocTraits::construct(*this, p, value); 175 counter_type::construct(); 176 } 177 178 void 179 destroy(pointer p) 180 { 181 AllocTraits::destroy(*this, p); 182 counter_type::destroy(); 183 } 184#endif 185 186 void 187 deallocate(pointer p, size_type num) 188 { 189 counter_type::deallocate(num * sizeof(T)); 190 AllocTraits::deallocate(*this, p, num); 191 } 192 193 // Implement swap for underlying allocators that might need it. 194 friend inline void 195 swap(tracker_allocator& a, tracker_allocator& b) 196 { 197 using std::swap; 198 199 Alloc& aa = a; 200 Alloc& ab = b; 201 swap(aa, ab); 202 } 203 }; 204 205 template<class T1, class Alloc1, class T2, class Alloc2> 206 bool 207 operator==(const tracker_allocator<T1, Alloc1>& lhs, 208 const tracker_allocator<T2, Alloc2>& rhs) throw() 209 { 210 const Alloc1& alloc1 = lhs; 211 const Alloc2& alloc2 = rhs; 212 return alloc1 == alloc2; 213 } 214 215 template<class T1, class Alloc1, class T2, class Alloc2> 216 bool 217 operator!=(const tracker_allocator<T1, Alloc1>& lhs, 218 const tracker_allocator<T2, Alloc2>& rhs) throw() 219 { return !(lhs == rhs); } 220 221 bool 222 check_construct_destroy(const char* tag, int expected_c, int expected_d); 223 224 template<typename Alloc> 225 bool 226 check_deallocate_null() 227 { 228 // Let's not core here... 229 Alloc a; 230 a.deallocate(0, 1); 231 a.deallocate(0, 10); 232 return true; 233 } 234 235 template<typename Alloc> 236 bool 237 check_allocate_max_size() 238 { 239 Alloc a; 240 try 241 { 242 a.allocate(a.max_size() + 1); 243 } 244 catch(std::bad_alloc&) 245 { 246 return true; 247 } 248 catch(...) 249 { 250 throw; 251 } 252 throw; 253 } 254 255 // A simple allocator which can be constructed endowed of a given 256 // "personality" (an integer), queried in operator== to simulate the 257 // behavior of realworld "unequal" allocators (i.e., not exploiting 258 // the provision in 20.1.5/4, first bullet). A global unordered_map, 259 // filled at allocation time with (pointer, personality) pairs, is 260 // then consulted to enforce the requirements in Table 32 about 261 // deallocation vs allocator equality. Note that this allocator is 262 // swappable, not copy assignable, consistently with Option 3 of DR 431 263 // (see N1599). 264 struct uneq_allocator_base 265 { 266 typedef std::tr1::unordered_map<void*, int> map_type; 267 268 // Avoid static initialization troubles and/or bad interactions 269 // with tests linking testsuite_allocator.o and playing globally 270 // with operator new/delete. 271 static map_type& 272 get_map() 273 { 274 static map_type alloc_map; 275 return alloc_map; 276 } 277 }; 278 279 template<typename Tp, typename Alloc = std::allocator<Tp> > 280 class uneq_allocator 281 : private uneq_allocator_base, 282 public Alloc 283 { 284 typedef __gnu_cxx::__alloc_traits<Alloc> AllocTraits; 285 286 Alloc& base() { return *this; } 287 const Alloc& base() const { return *this; } 288 void swap_base(Alloc& b) { swap(b, this->base()); } 289 290 public: 291 typedef typename check_consistent_alloc_value_type<Tp, Alloc>::value_type 292 value_type; 293 typedef typename AllocTraits::size_type size_type; 294 typedef typename AllocTraits::pointer pointer; 295 296#if __cplusplus >= 201103L 297 typedef std::true_type propagate_on_container_swap; 298#endif 299 300 template<typename Tp1> 301 struct rebind 302 { 303 typedef uneq_allocator<Tp1, 304 typename AllocTraits::template rebind<Tp1>::other> other; 305 }; 306 307 uneq_allocator() _GLIBCXX_USE_NOEXCEPT 308 : personality(0) { } 309 310 uneq_allocator(int person) _GLIBCXX_USE_NOEXCEPT 311 : personality(person) { } 312 313#if __cplusplus >= 201103L 314 uneq_allocator(const uneq_allocator&) = default; 315 uneq_allocator(uneq_allocator&&) = default; 316#endif 317 318 template<typename Tp1> 319 uneq_allocator(const uneq_allocator<Tp1, 320 typename AllocTraits::template rebind<Tp1>::other>& b) 321 _GLIBCXX_USE_NOEXCEPT 322 : personality(b.get_personality()) { } 323 324 ~uneq_allocator() _GLIBCXX_USE_NOEXCEPT 325 { } 326 327 int get_personality() const { return personality; } 328 329 pointer 330 allocate(size_type n, const void* hint = 0) 331 { 332 pointer p = AllocTraits::allocate(*this, n); 333 334 try 335 { 336 get_map().insert(map_type::value_type(reinterpret_cast<void*>(p), 337 personality)); 338 } 339 catch(...) 340 { 341 AllocTraits::deallocate(*this, p, n); 342 __throw_exception_again; 343 } 344 345 return p; 346 } 347 348 void 349 deallocate(pointer p, size_type n) 350 { 351 bool test __attribute__((unused)) = true; 352 353 VERIFY( p ); 354 355 map_type::iterator it = get_map().find(reinterpret_cast<void*>(p)); 356 VERIFY( it != get_map().end() ); 357 358 // Enforce requirements in Table 32 about deallocation vs 359 // allocator equality. 360 VERIFY( it->second == personality ); 361 362 get_map().erase(it); 363 AllocTraits::deallocate(*this, p, n); 364 } 365 366#if __cplusplus >= 201103L 367 // Not copy assignable... 368 uneq_allocator& 369 operator=(const uneq_allocator&) = delete; 370 371 // ... but still moveable if base allocator is. 372 uneq_allocator& 373 operator=(uneq_allocator&&) = default; 374#else 375 private: 376 // Not assignable... 377 uneq_allocator& 378 operator=(const uneq_allocator&); 379#endif 380 381 private: 382 // ... yet swappable! 383 friend inline void 384 swap(uneq_allocator& a, uneq_allocator& b) 385 { 386 std::swap(a.personality, b.personality); 387 a.swap_base(b); 388 } 389 390 template<typename Tp1> 391 friend inline bool 392 operator==(const uneq_allocator& a, 393 const uneq_allocator<Tp1, 394 typename AllocTraits::template rebind<Tp1>::other>& b) 395 { return a.personality == b.personality; } 396 397 template<typename Tp1> 398 friend inline bool 399 operator!=(const uneq_allocator& a, 400 const uneq_allocator<Tp1, 401 typename AllocTraits::template rebind<Tp1>::other>& b) 402 { return !(a == b); } 403 404 int personality; 405 }; 406 407#if __cplusplus >= 201103L 408 // An uneq_allocator which can be used to test allocator propagation. 409 template<typename Tp, bool Propagate, typename Alloc = std::allocator<Tp>> 410 class propagating_allocator : public uneq_allocator<Tp, Alloc> 411 { 412 typedef __gnu_cxx::__alloc_traits<Alloc> AllocTraits; 413 414 typedef uneq_allocator<Tp, Alloc> base_alloc; 415 base_alloc& base() { return *this; } 416 const base_alloc& base() const { return *this; } 417 void swap_base(base_alloc& b) { swap(b, this->base()); } 418 419 typedef std::integral_constant<bool, Propagate> trait_type; 420 421 public: 422 // default allocator_traits::rebind_alloc would select 423 // uneq_allocator::rebind so we must define rebind here 424 template<typename Up> 425 struct rebind 426 { 427 typedef propagating_allocator<Up, Propagate, 428 typename AllocTraits::template rebind<Up>::other> other; 429 }; 430 431 propagating_allocator(int i) noexcept 432 : base_alloc(i) 433 { } 434 435 template<typename Up> 436 propagating_allocator(const propagating_allocator<Up, Propagate, 437 typename AllocTraits::template rebind<Up>::other>& a) 438 noexcept 439 : base_alloc(a) 440 { } 441 442 propagating_allocator() noexcept = default; 443 444 propagating_allocator(const propagating_allocator&) noexcept = default; 445 446 propagating_allocator& 447 operator=(const propagating_allocator& a) noexcept 448 { 449 static_assert(Propagate, "assigning propagating_allocator<T, true>"); 450 propagating_allocator(a).swap_base(*this); 451 return *this; 452 } 453 454 template<bool P2> 455 propagating_allocator& 456 operator=(const propagating_allocator<Tp, P2, Alloc>& a) noexcept 457 { 458 static_assert(P2, "assigning propagating_allocator<T, true>"); 459 propagating_allocator(a).swap_base(*this); 460 return *this; 461 } 462 463 // postcondition: a.get_personality() == 0 464 propagating_allocator(propagating_allocator&& a) noexcept 465 : base_alloc() 466 { swap_base(a); } 467 468 // postcondition: a.get_personality() == 0 469 propagating_allocator& 470 operator=(propagating_allocator&& a) noexcept 471 { 472 propagating_allocator(std::move(a)).swap_base(*this); 473 return *this; 474 } 475 476 typedef trait_type propagate_on_container_copy_assignment; 477 typedef trait_type propagate_on_container_move_assignment; 478 typedef trait_type propagate_on_container_swap; 479 480 propagating_allocator select_on_container_copy_construction() const 481 { return Propagate ? *this : propagating_allocator(); } 482 }; 483 484 // Class template supporting the minimal interface that satisfies the 485 // Allocator requirements, from example in [allocator.requirements] 486 template <class Tp> 487 struct SimpleAllocator 488 { 489 typedef Tp value_type; 490 491 SimpleAllocator() noexcept { } 492 493 template <class T> 494 SimpleAllocator(const SimpleAllocator<T>& other) { } 495 496 Tp *allocate(std::size_t n) 497 { return std::allocator<Tp>().allocate(n); } 498 499 void deallocate(Tp *p, std::size_t n) 500 { std::allocator<Tp>().deallocate(p, n); } 501 }; 502 503 template <class T, class U> 504 bool operator==(const SimpleAllocator<T>&, const SimpleAllocator<U>&) 505 { return true; } 506 template <class T, class U> 507 bool operator!=(const SimpleAllocator<T>&, const SimpleAllocator<U>&) 508 { return false; } 509 510#endif 511 512 template<typename Tp> 513 struct ExplicitConsAlloc : std::allocator<Tp> 514 { 515 ExplicitConsAlloc() { } 516 517 template<typename Up> 518 explicit 519 ExplicitConsAlloc(const ExplicitConsAlloc<Up>&) { } 520 521 template<typename Up> 522 struct rebind 523 { typedef ExplicitConsAlloc<Up> other; }; 524 }; 525 526#if __cplusplus >= 201103L 527 template<typename Tp> 528 class CustomPointerAlloc : public std::allocator<Tp> 529 { 530 template<typename Up, typename Sp = __gnu_cxx::_Std_pointer_impl<Up>> 531 using Ptr = __gnu_cxx::_Pointer_adapter<Sp>; 532 533 public: 534 CustomPointerAlloc() = default; 535 536 template<typename Up> 537 CustomPointerAlloc(const CustomPointerAlloc<Up>&) { } 538 539 template<typename Up> 540 struct rebind 541 { typedef CustomPointerAlloc<Up> other; }; 542 543 typedef Ptr<Tp> pointer; 544 typedef Ptr<const Tp> const_pointer; 545 typedef Ptr<void> void_pointer; 546 typedef Ptr<const void> const_void_pointer; 547 548 pointer allocate(std::size_t n, pointer = {}) 549 { return pointer(std::allocator<Tp>::allocate(n)); } 550 551 void deallocate(pointer p, std::size_t n) 552 { std::allocator<Tp>::deallocate(std::addressof(*p), n); } 553 }; 554 555 // Utility for use as CRTP base class of custom pointer types 556 template<typename Derived, typename T> 557 struct PointerBase 558 { 559 typedef T element_type; 560 561 // typedefs for iterator_traits 562 typedef T value_type; 563 typedef std::ptrdiff_t difference_type; 564 typedef std::random_access_iterator_tag iterator_category; 565 typedef Derived pointer; 566 typedef T& reference; 567 568 T* value; 569 570 explicit PointerBase(T* p = nullptr) : value(p) { } 571 572 template<typename D, typename U, 573 typename = decltype(static_cast<T*>(std::declval<U*>()))> 574 PointerBase(const PointerBase<D, U>& p) : value(p.value) { } 575 576 T& operator*() const { return *value; } 577 T* operator->() const { return value; } 578 579 Derived& operator++() { ++value; return derived(); } 580 Derived operator++(int) { Derived tmp(derived()); ++value; return tmp; } 581 Derived& operator--() { --value; return derived(); } 582 Derived operator--(int) { Derived tmp(derived()); --value; return tmp; } 583 584 Derived& operator+=(difference_type n) { value += n; return derived(); } 585 Derived& operator-=(difference_type n) { value -= n; return derived(); } 586 587 explicit operator bool() const { return value != nullptr; } 588 589 Derived 590 operator+(difference_type n) const 591 { 592 Derived p(derived()); 593 return p += n; 594 } 595 596 Derived 597 operator-(difference_type n) const 598 { 599 Derived p(derived()); 600 return p -= n; 601 } 602 603 private: 604 Derived& derived() { return static_cast<Derived&>(*this); } 605 }; 606 607 template<typename D, typename T> 608 std::ptrdiff_t operator-(PointerBase<D, T> l, PointerBase<D, T> r) 609 { return l.value - r.value; } 610 611 template<typename D, typename T> 612 bool operator==(PointerBase<D, T> l, PointerBase<D, T> r) 613 { return l.value == r.value; } 614 615 template<typename D, typename T> 616 bool operator!=(PointerBase<D, T> l, PointerBase<D, T> r) 617 { return l.value != r.value; } 618 619 // implementation for void specializations 620 template<typename T> 621 struct PointerBase_void 622 { 623 typedef T element_type; 624 625 // typedefs for iterator_traits 626 typedef T value_type; 627 typedef std::ptrdiff_t difference_type; 628 typedef std::random_access_iterator_tag iterator_category; 629 630 T* value; 631 632 explicit PointerBase_void(T* p = nullptr) : value(p) { } 633 634 template<typename D, typename U, 635 typename = decltype(static_cast<T*>(std::declval<U*>()))> 636 PointerBase_void(const PointerBase<D, U>& p) : value(p.value) { } 637 638 explicit operator bool() const { return value != nullptr; } 639 }; 640 641 template<typename Derived> 642 struct PointerBase<Derived, void> : PointerBase_void<void> 643 { 644 using PointerBase_void::PointerBase_void; 645 typedef Derived pointer; 646 }; 647 648 template<typename Derived> 649 struct PointerBase<Derived, const void> : PointerBase_void<const void> 650 { 651 using PointerBase_void::PointerBase_void; 652 typedef Derived pointer; 653 }; 654#endif 655 656} // namespace __gnu_test 657 658#endif // _GLIBCXX_TESTSUITE_ALLOCATOR_H 659