1 // Allocator traits -*- C++ -*- 2 3 // Copyright (C) 2011-2019 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file bits/alloc_traits.h 26 * This is an internal header file, included by other library headers. 27 * Do not attempt to use it directly. @headername{memory} 28 */ 29 30 #ifndef _ALLOC_TRAITS_H 31 #define _ALLOC_TRAITS_H 1 32 33 #if __cplusplus >= 201103L 34 35 #include <bits/memoryfwd.h> 36 #include <bits/ptr_traits.h> 37 #include <ext/numeric_traits.h> 38 39 #define __cpp_lib_allocator_traits_is_always_equal 201411 40 41 namespace std _GLIBCXX_VISIBILITY(default) 42 { 43 _GLIBCXX_BEGIN_NAMESPACE_VERSION 44 45 struct __allocator_traits_base 46 { 47 template<typename _Tp, typename _Up, typename = void> 48 struct __rebind : __replace_first_arg<_Tp, _Up> { }; 49 50 template<typename _Tp, typename _Up> 51 struct __rebind<_Tp, _Up, 52 __void_t<typename _Tp::template rebind<_Up>::other>> 53 { using type = typename _Tp::template rebind<_Up>::other; }; 54 55 protected: 56 template<typename _Tp> 57 using __pointer = typename _Tp::pointer; 58 template<typename _Tp> 59 using __c_pointer = typename _Tp::const_pointer; 60 template<typename _Tp> 61 using __v_pointer = typename _Tp::void_pointer; 62 template<typename _Tp> 63 using __cv_pointer = typename _Tp::const_void_pointer; 64 template<typename _Tp> 65 using __pocca = typename _Tp::propagate_on_container_copy_assignment; 66 template<typename _Tp> 67 using __pocma = typename _Tp::propagate_on_container_move_assignment; 68 template<typename _Tp> 69 using __pocs = typename _Tp::propagate_on_container_swap; 70 template<typename _Tp> 71 using __equal = typename _Tp::is_always_equal; 72 }; 73 74 template<typename _Alloc, typename _Up> 75 using __alloc_rebind 76 = typename __allocator_traits_base::template __rebind<_Alloc, _Up>::type; 77 78 /** 79 * @brief Uniform interface to all allocator types. 80 * @ingroup allocators 81 */ 82 template<typename _Alloc> 83 struct allocator_traits : __allocator_traits_base 84 { 85 /// The allocator type 86 typedef _Alloc allocator_type; 87 /// The allocated type 88 typedef typename _Alloc::value_type value_type; 89 90 /** 91 * @brief The allocator's pointer type. 92 * 93 * @c Alloc::pointer if that type exists, otherwise @c value_type* 94 */ 95 using pointer = __detected_or_t<value_type*, __pointer, _Alloc>; 96 97 private: 98 // Select _Func<_Alloc> or pointer_traits<pointer>::rebind<_Tp> 99 template<template<typename> class _Func, typename _Tp, typename = void> 100 struct _Ptr 101 { 102 using type = typename pointer_traits<pointer>::template rebind<_Tp>; 103 }; 104 105 template<template<typename> class _Func, typename _Tp> 106 struct _Ptr<_Func, _Tp, __void_t<_Func<_Alloc>>> 107 { 108 using type = _Func<_Alloc>; 109 }; 110 111 // Select _A2::difference_type or pointer_traits<_Ptr>::difference_type 112 template<typename _A2, typename _PtrT, typename = void> 113 struct _Diff 114 { using type = typename pointer_traits<_PtrT>::difference_type; }; 115 116 template<typename _A2, typename _PtrT> 117 struct _Diff<_A2, _PtrT, __void_t<typename _A2::difference_type>> 118 { using type = typename _A2::difference_type; }; 119 120 // Select _A2::size_type or make_unsigned<_DiffT>::type 121 template<typename _A2, typename _DiffT, typename = void> 122 struct _Size : make_unsigned<_DiffT> { }; 123 124 template<typename _A2, typename _DiffT> 125 struct _Size<_A2, _DiffT, __void_t<typename _A2::size_type>> 126 { using type = typename _A2::size_type; }; 127 128 public: 129 /** 130 * @brief The allocator's const pointer type. 131 * 132 * @c Alloc::const_pointer if that type exists, otherwise 133 * <tt> pointer_traits<pointer>::rebind<const value_type> </tt> 134 */ 135 using const_pointer = typename _Ptr<__c_pointer, const value_type>::type; 136 137 /** 138 * @brief The allocator's void pointer type. 139 * 140 * @c Alloc::void_pointer if that type exists, otherwise 141 * <tt> pointer_traits<pointer>::rebind<void> </tt> 142 */ 143 using void_pointer = typename _Ptr<__v_pointer, void>::type; 144 145 /** 146 * @brief The allocator's const void pointer type. 147 * 148 * @c Alloc::const_void_pointer if that type exists, otherwise 149 * <tt> pointer_traits<pointer>::rebind<const void> </tt> 150 */ 151 using const_void_pointer = typename _Ptr<__cv_pointer, const void>::type; 152 153 /** 154 * @brief The allocator's difference type 155 * 156 * @c Alloc::difference_type if that type exists, otherwise 157 * <tt> pointer_traits<pointer>::difference_type </tt> 158 */ 159 using difference_type = typename _Diff<_Alloc, pointer>::type; 160 161 /** 162 * @brief The allocator's size type 163 * 164 * @c Alloc::size_type if that type exists, otherwise 165 * <tt> make_unsigned<difference_type>::type </tt> 166 */ 167 using size_type = typename _Size<_Alloc, difference_type>::type; 168 169 /** 170 * @brief How the allocator is propagated on copy assignment 171 * 172 * @c Alloc::propagate_on_container_copy_assignment if that type exists, 173 * otherwise @c false_type 174 */ 175 using propagate_on_container_copy_assignment 176 = __detected_or_t<false_type, __pocca, _Alloc>; 177 178 /** 179 * @brief How the allocator is propagated on move assignment 180 * 181 * @c Alloc::propagate_on_container_move_assignment if that type exists, 182 * otherwise @c false_type 183 */ 184 using propagate_on_container_move_assignment 185 = __detected_or_t<false_type, __pocma, _Alloc>; 186 187 /** 188 * @brief How the allocator is propagated on swap 189 * 190 * @c Alloc::propagate_on_container_swap if that type exists, 191 * otherwise @c false_type 192 */ 193 using propagate_on_container_swap 194 = __detected_or_t<false_type, __pocs, _Alloc>; 195 196 /** 197 * @brief Whether all instances of the allocator type compare equal. 198 * 199 * @c Alloc::is_always_equal if that type exists, 200 * otherwise @c is_empty<Alloc>::type 201 */ 202 using is_always_equal 203 = __detected_or_t<typename is_empty<_Alloc>::type, __equal, _Alloc>; 204 205 template<typename _Tp> 206 using rebind_alloc = __alloc_rebind<_Alloc, _Tp>; 207 template<typename _Tp> 208 using rebind_traits = allocator_traits<rebind_alloc<_Tp>>; 209 210 private: 211 template<typename _Alloc2> 212 static auto 213 _S_allocate(_Alloc2& __a, size_type __n, const_void_pointer __hint, int) 214 -> decltype(__a.allocate(__n, __hint)) 215 { return __a.allocate(__n, __hint); } 216 217 template<typename _Alloc2> 218 static pointer 219 _S_allocate(_Alloc2& __a, size_type __n, const_void_pointer, ...) 220 { return __a.allocate(__n); } 221 222 template<typename _Tp, typename... _Args> 223 struct __construct_helper 224 { 225 template<typename _Alloc2, 226 typename = decltype(std::declval<_Alloc2*>()->construct( 227 std::declval<_Tp*>(), std::declval<_Args>()...))> 228 static true_type __test(int); 229 230 template<typename> 231 static false_type __test(...); 232 233 using type = decltype(__test<_Alloc>(0)); 234 }; 235 236 template<typename _Tp, typename... _Args> 237 using __has_construct 238 = typename __construct_helper<_Tp, _Args...>::type; 239 240 template<typename _Tp, typename... _Args> 241 static _Require<__has_construct<_Tp, _Args...>> 242 _S_construct(_Alloc& __a, _Tp* __p, _Args&&... __args) 243 noexcept(noexcept(__a.construct(__p, std::forward<_Args>(__args)...))) 244 { __a.construct(__p, std::forward<_Args>(__args)...); } 245 246 template<typename _Tp, typename... _Args> 247 static 248 _Require<__and_<__not_<__has_construct<_Tp, _Args...>>, 249 is_constructible<_Tp, _Args...>>> 250 _S_construct(_Alloc&, _Tp* __p, _Args&&... __args) 251 noexcept(noexcept(::new((void*)__p) 252 _Tp(std::forward<_Args>(__args)...))) 253 { ::new((void*)__p) _Tp(std::forward<_Args>(__args)...); } 254 255 template<typename _Alloc2, typename _Tp> 256 static auto 257 _S_destroy(_Alloc2& __a, _Tp* __p, int) 258 noexcept(noexcept(__a.destroy(__p))) 259 -> decltype(__a.destroy(__p)) 260 { __a.destroy(__p); } 261 262 template<typename _Alloc2, typename _Tp> 263 static void 264 _S_destroy(_Alloc2&, _Tp* __p, ...) 265 noexcept(noexcept(__p->~_Tp())) 266 { __p->~_Tp(); } 267 268 template<typename _Alloc2> 269 static auto 270 _S_max_size(_Alloc2& __a, int) 271 -> decltype(__a.max_size()) 272 { return __a.max_size(); } 273 274 template<typename _Alloc2> 275 static size_type 276 _S_max_size(_Alloc2&, ...) 277 { 278 // _GLIBCXX_RESOLVE_LIB_DEFECTS 279 // 2466. allocator_traits::max_size() default behavior is incorrect 280 return __gnu_cxx::__numeric_traits<size_type>::__max 281 / sizeof(value_type); 282 } 283 284 template<typename _Alloc2> 285 static auto 286 _S_select(_Alloc2& __a, int) 287 -> decltype(__a.select_on_container_copy_construction()) 288 { return __a.select_on_container_copy_construction(); } 289 290 template<typename _Alloc2> 291 static _Alloc2 292 _S_select(_Alloc2& __a, ...) 293 { return __a; } 294 295 public: 296 297 /** 298 * @brief Allocate memory. 299 * @param __a An allocator. 300 * @param __n The number of objects to allocate space for. 301 * 302 * Calls @c a.allocate(n) 303 */ 304 _GLIBCXX_NODISCARD static pointer 305 allocate(_Alloc& __a, size_type __n) 306 { return __a.allocate(__n); } 307 308 /** 309 * @brief Allocate memory. 310 * @param __a An allocator. 311 * @param __n The number of objects to allocate space for. 312 * @param __hint Aid to locality. 313 * @return Memory of suitable size and alignment for @a n objects 314 * of type @c value_type 315 * 316 * Returns <tt> a.allocate(n, hint) </tt> if that expression is 317 * well-formed, otherwise returns @c a.allocate(n) 318 */ 319 _GLIBCXX_NODISCARD static pointer 320 allocate(_Alloc& __a, size_type __n, const_void_pointer __hint) 321 { return _S_allocate(__a, __n, __hint, 0); } 322 323 /** 324 * @brief Deallocate memory. 325 * @param __a An allocator. 326 * @param __p Pointer to the memory to deallocate. 327 * @param __n The number of objects space was allocated for. 328 * 329 * Calls <tt> a.deallocate(p, n) </tt> 330 */ 331 static void 332 deallocate(_Alloc& __a, pointer __p, size_type __n) 333 { __a.deallocate(__p, __n); } 334 335 /** 336 * @brief Construct an object of type @a _Tp 337 * @param __a An allocator. 338 * @param __p Pointer to memory of suitable size and alignment for Tp 339 * @param __args Constructor arguments. 340 * 341 * Calls <tt> __a.construct(__p, std::forward<Args>(__args)...) </tt> 342 * if that expression is well-formed, otherwise uses placement-new 343 * to construct an object of type @a _Tp at location @a __p from the 344 * arguments @a __args... 345 */ 346 template<typename _Tp, typename... _Args> 347 static auto construct(_Alloc& __a, _Tp* __p, _Args&&... __args) 348 noexcept(noexcept(_S_construct(__a, __p, 349 std::forward<_Args>(__args)...))) 350 -> decltype(_S_construct(__a, __p, std::forward<_Args>(__args)...)) 351 { _S_construct(__a, __p, std::forward<_Args>(__args)...); } 352 353 /** 354 * @brief Destroy an object of type @a _Tp 355 * @param __a An allocator. 356 * @param __p Pointer to the object to destroy 357 * 358 * Calls @c __a.destroy(__p) if that expression is well-formed, 359 * otherwise calls @c __p->~_Tp() 360 */ 361 template<typename _Tp> 362 static void destroy(_Alloc& __a, _Tp* __p) 363 noexcept(noexcept(_S_destroy(__a, __p, 0))) 364 { _S_destroy(__a, __p, 0); } 365 366 /** 367 * @brief The maximum supported allocation size 368 * @param __a An allocator. 369 * @return @c __a.max_size() or @c numeric_limits<size_type>::max() 370 * 371 * Returns @c __a.max_size() if that expression is well-formed, 372 * otherwise returns @c numeric_limits<size_type>::max() 373 */ 374 static size_type max_size(const _Alloc& __a) noexcept 375 { return _S_max_size(__a, 0); } 376 377 /** 378 * @brief Obtain an allocator to use when copying a container. 379 * @param __rhs An allocator. 380 * @return @c __rhs.select_on_container_copy_construction() or @a __rhs 381 * 382 * Returns @c __rhs.select_on_container_copy_construction() if that 383 * expression is well-formed, otherwise returns @a __rhs 384 */ 385 static _Alloc 386 select_on_container_copy_construction(const _Alloc& __rhs) 387 { return _S_select(__rhs, 0); } 388 }; 389 390 /// Partial specialization for std::allocator. 391 template<typename _Tp> 392 struct allocator_traits<allocator<_Tp>> 393 { 394 /// The allocator type 395 using allocator_type = allocator<_Tp>; 396 /// The allocated type 397 using value_type = _Tp; 398 399 /// The allocator's pointer type. 400 using pointer = _Tp*; 401 402 /// The allocator's const pointer type. 403 using const_pointer = const _Tp*; 404 405 /// The allocator's void pointer type. 406 using void_pointer = void*; 407 408 /// The allocator's const void pointer type. 409 using const_void_pointer = const void*; 410 411 /// The allocator's difference type 412 using difference_type = std::ptrdiff_t; 413 414 /// The allocator's size type 415 using size_type = std::size_t; 416 417 /// How the allocator is propagated on copy assignment 418 using propagate_on_container_copy_assignment = false_type; 419 420 /// How the allocator is propagated on move assignment 421 using propagate_on_container_move_assignment = true_type; 422 423 /// How the allocator is propagated on swap 424 using propagate_on_container_swap = false_type; 425 426 /// Whether all instances of the allocator type compare equal. 427 using is_always_equal = true_type; 428 429 template<typename _Up> 430 using rebind_alloc = allocator<_Up>; 431 432 template<typename _Up> 433 using rebind_traits = allocator_traits<allocator<_Up>>; 434 435 /** 436 * @brief Allocate memory. 437 * @param __a An allocator. 438 * @param __n The number of objects to allocate space for. 439 * 440 * Calls @c a.allocate(n) 441 */ 442 _GLIBCXX_NODISCARD static pointer 443 allocate(allocator_type& __a, size_type __n) 444 { return __a.allocate(__n); } 445 446 /** 447 * @brief Allocate memory. 448 * @param __a An allocator. 449 * @param __n The number of objects to allocate space for. 450 * @param __hint Aid to locality. 451 * @return Memory of suitable size and alignment for @a n objects 452 * of type @c value_type 453 * 454 * Returns <tt> a.allocate(n, hint) </tt> 455 */ 456 _GLIBCXX_NODISCARD static pointer 457 allocate(allocator_type& __a, size_type __n, const_void_pointer __hint) 458 { return __a.allocate(__n, __hint); } 459 460 /** 461 * @brief Deallocate memory. 462 * @param __a An allocator. 463 * @param __p Pointer to the memory to deallocate. 464 * @param __n The number of objects space was allocated for. 465 * 466 * Calls <tt> a.deallocate(p, n) </tt> 467 */ 468 static void 469 deallocate(allocator_type& __a, pointer __p, size_type __n) 470 { __a.deallocate(__p, __n); } 471 472 /** 473 * @brief Construct an object of type @a _Up 474 * @param __a An allocator. 475 * @param __p Pointer to memory of suitable size and alignment for Tp 476 * @param __args Constructor arguments. 477 * 478 * Calls <tt> __a.construct(__p, std::forward<Args>(__args)...) </tt> 479 */ 480 template<typename _Up, typename... _Args> 481 static void 482 construct(allocator_type& __a, _Up* __p, _Args&&... __args) 483 noexcept(noexcept(__a.construct(__p, std::forward<_Args>(__args)...))) 484 { __a.construct(__p, std::forward<_Args>(__args)...); } 485 486 /** 487 * @brief Destroy an object of type @a _Up 488 * @param __a An allocator. 489 * @param __p Pointer to the object to destroy 490 * 491 * Calls @c __a.destroy(__p). 492 */ 493 template<typename _Up> 494 static void 495 destroy(allocator_type& __a, _Up* __p) 496 noexcept(noexcept(__a.destroy(__p))) 497 { __a.destroy(__p); } 498 499 /** 500 * @brief The maximum supported allocation size 501 * @param __a An allocator. 502 * @return @c __a.max_size() 503 */ 504 static size_type 505 max_size(const allocator_type& __a) noexcept 506 { return __a.max_size(); } 507 508 /** 509 * @brief Obtain an allocator to use when copying a container. 510 * @param __rhs An allocator. 511 * @return @c __rhs 512 */ 513 static allocator_type 514 select_on_container_copy_construction(const allocator_type& __rhs) 515 { return __rhs; } 516 }; 517 518 519 template<typename _Alloc> 520 inline void 521 __do_alloc_on_copy(_Alloc& __one, const _Alloc& __two, true_type) 522 { __one = __two; } 523 524 template<typename _Alloc> 525 inline void 526 __do_alloc_on_copy(_Alloc&, const _Alloc&, false_type) 527 { } 528 529 template<typename _Alloc> 530 inline void __alloc_on_copy(_Alloc& __one, const _Alloc& __two) 531 { 532 typedef allocator_traits<_Alloc> __traits; 533 typedef typename __traits::propagate_on_container_copy_assignment __pocca; 534 __do_alloc_on_copy(__one, __two, __pocca()); 535 } 536 537 template<typename _Alloc> 538 inline _Alloc __alloc_on_copy(const _Alloc& __a) 539 { 540 typedef allocator_traits<_Alloc> __traits; 541 return __traits::select_on_container_copy_construction(__a); 542 } 543 544 template<typename _Alloc> 545 inline void __do_alloc_on_move(_Alloc& __one, _Alloc& __two, true_type) 546 { __one = std::move(__two); } 547 548 template<typename _Alloc> 549 inline void __do_alloc_on_move(_Alloc&, _Alloc&, false_type) 550 { } 551 552 template<typename _Alloc> 553 inline void __alloc_on_move(_Alloc& __one, _Alloc& __two) 554 { 555 typedef allocator_traits<_Alloc> __traits; 556 typedef typename __traits::propagate_on_container_move_assignment __pocma; 557 __do_alloc_on_move(__one, __two, __pocma()); 558 } 559 560 template<typename _Alloc> 561 inline void __do_alloc_on_swap(_Alloc& __one, _Alloc& __two, true_type) 562 { 563 using std::swap; 564 swap(__one, __two); 565 } 566 567 template<typename _Alloc> 568 inline void __do_alloc_on_swap(_Alloc&, _Alloc&, false_type) 569 { } 570 571 template<typename _Alloc> 572 inline void __alloc_on_swap(_Alloc& __one, _Alloc& __two) 573 { 574 typedef allocator_traits<_Alloc> __traits; 575 typedef typename __traits::propagate_on_container_swap __pocs; 576 __do_alloc_on_swap(__one, __two, __pocs()); 577 } 578 579 template<typename _Alloc, typename _Tp, 580 typename _ValueT = __remove_cvref_t<typename _Alloc::value_type>, 581 typename = void> 582 struct __is_alloc_insertable_impl 583 : false_type 584 { }; 585 586 template<typename _Alloc, typename _Tp, typename _ValueT> 587 struct __is_alloc_insertable_impl<_Alloc, _Tp, _ValueT, 588 __void_t<decltype(allocator_traits<_Alloc>::construct( 589 std::declval<_Alloc&>(), std::declval<_ValueT*>(), 590 std::declval<_Tp>()))>> 591 : true_type 592 { }; 593 594 // true if _Alloc::value_type is CopyInsertable into containers using _Alloc 595 // (might be wrong if _Alloc::construct exists but is not constrained, 596 // i.e. actually trying to use it would still be invalid. Use with caution.) 597 template<typename _Alloc> 598 struct __is_copy_insertable 599 : __is_alloc_insertable_impl<_Alloc, 600 typename _Alloc::value_type const&>::type 601 { }; 602 603 // std::allocator<_Tp> just requires CopyConstructible 604 template<typename _Tp> 605 struct __is_copy_insertable<allocator<_Tp>> 606 : is_copy_constructible<_Tp> 607 { }; 608 609 // true if _Alloc::value_type is MoveInsertable into containers using _Alloc 610 // (might be wrong if _Alloc::construct exists but is not constrained, 611 // i.e. actually trying to use it would still be invalid. Use with caution.) 612 template<typename _Alloc> 613 struct __is_move_insertable 614 : __is_alloc_insertable_impl<_Alloc, typename _Alloc::value_type>::type 615 { }; 616 617 // std::allocator<_Tp> just requires MoveConstructible 618 template<typename _Tp> 619 struct __is_move_insertable<allocator<_Tp>> 620 : is_move_constructible<_Tp> 621 { }; 622 623 // Trait to detect Allocator-like types. 624 template<typename _Alloc, typename = void> 625 struct __is_allocator : false_type { }; 626 627 template<typename _Alloc> 628 struct __is_allocator<_Alloc, 629 __void_t<typename _Alloc::value_type, 630 decltype(std::declval<_Alloc&>().allocate(size_t{}))>> 631 : true_type { }; 632 633 template<typename _Alloc> 634 using _RequireAllocator 635 = typename enable_if<__is_allocator<_Alloc>::value, _Alloc>::type; 636 637 template<typename _Alloc> 638 using _RequireNotAllocator 639 = typename enable_if<!__is_allocator<_Alloc>::value, _Alloc>::type; 640 641 _GLIBCXX_END_NAMESPACE_VERSION 642 } // namespace std 643 #endif // C++11 644 #endif // _ALLOC_TRAITS_H 645