1 // Allocator traits -*- C++ -*- 2 3 // Copyright (C) 2011, 2012, 2013 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 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 34 35 #include <bits/ptr_traits.h> 36 #include <ext/numeric_traits.h> 37 38 namespace std _GLIBCXX_VISIBILITY(default) 39 { 40 _GLIBCXX_BEGIN_NAMESPACE_VERSION 41 42 template<typename _Tp> 43 class allocator; 44 45 template<typename _Alloc, typename _Tp> 46 class __alloctr_rebind_helper 47 { 48 template<typename _Alloc2, typename _Tp2> 49 static constexpr bool 50 _S_chk(typename _Alloc2::template rebind<_Tp2>::other*) 51 { return true; } 52 53 template<typename, typename> 54 static constexpr bool 55 _S_chk(...) 56 { return false; } 57 58 public: 59 static const bool __value = _S_chk<_Alloc, _Tp>(nullptr); 60 }; 61 62 template<typename _Alloc, typename _Tp> 63 const bool __alloctr_rebind_helper<_Alloc, _Tp>::__value; 64 65 template<typename _Alloc, typename _Tp, 66 bool = __alloctr_rebind_helper<_Alloc, _Tp>::__value> 67 struct __alloctr_rebind; 68 69 template<typename _Alloc, typename _Tp> 70 struct __alloctr_rebind<_Alloc, _Tp, true> 71 { 72 typedef typename _Alloc::template rebind<_Tp>::other __type; 73 }; 74 75 template<template<typename, typename...> class _Alloc, typename _Tp, 76 typename _Up, typename... _Args> 77 struct __alloctr_rebind<_Alloc<_Up, _Args...>, _Tp, false> 78 { 79 typedef _Alloc<_Tp, _Args...> __type; 80 }; 81 82 /** 83 * @brief Uniform interface to all allocator types. 84 * @ingroup allocators 85 */ 86 template<typename _Alloc> 87 struct allocator_traits 88 { 89 /// The allocator type 90 typedef _Alloc allocator_type; 91 /// The allocated type 92 typedef typename _Alloc::value_type value_type; 93 94 #define _GLIBCXX_ALLOC_TR_NESTED_TYPE(_NTYPE, _ALT) \ 95 private: \ 96 template<typename _Tp> \ 97 static typename _Tp::_NTYPE _S_##_NTYPE##_helper(_Tp*); \ 98 static _ALT _S_##_NTYPE##_helper(...); \ 99 typedef decltype(_S_##_NTYPE##_helper((_Alloc*)0)) __##_NTYPE; \ 100 public: 101 102 _GLIBCXX_ALLOC_TR_NESTED_TYPE(pointer, value_type*) 103 104 /** 105 * @brief The allocator's pointer type. 106 * 107 * @c Alloc::pointer if that type exists, otherwise @c value_type* 108 */ 109 typedef __pointer pointer; 110 111 _GLIBCXX_ALLOC_TR_NESTED_TYPE(const_pointer, 112 typename pointer_traits<pointer>::template rebind<const value_type>) 113 114 /** 115 * @brief The allocator's const pointer type. 116 * 117 * @c Alloc::const_pointer if that type exists, otherwise 118 * <tt> pointer_traits<pointer>::rebind<const value_type> </tt> 119 */ 120 typedef __const_pointer const_pointer; 121 122 _GLIBCXX_ALLOC_TR_NESTED_TYPE(void_pointer, 123 typename pointer_traits<pointer>::template rebind<void>) 124 125 /** 126 * @brief The allocator's void pointer type. 127 * 128 * @c Alloc::void_pointer if that type exists, otherwise 129 * <tt> pointer_traits<pointer>::rebind<void> </tt> 130 */ 131 typedef __void_pointer void_pointer; 132 133 _GLIBCXX_ALLOC_TR_NESTED_TYPE(const_void_pointer, 134 typename pointer_traits<pointer>::template rebind<const void>) 135 136 /** 137 * @brief The allocator's const void pointer type. 138 * 139 * @c Alloc::const_void_pointer if that type exists, otherwise 140 * <tt> pointer_traits<pointer>::rebind<const void> </tt> 141 */ 142 typedef __const_void_pointer const_void_pointer; 143 144 _GLIBCXX_ALLOC_TR_NESTED_TYPE(difference_type, 145 typename pointer_traits<pointer>::difference_type) 146 147 /** 148 * @brief The allocator's difference type 149 * 150 * @c Alloc::difference_type if that type exists, otherwise 151 * <tt> pointer_traits<pointer>::difference_type </tt> 152 */ 153 typedef __difference_type difference_type; 154 155 _GLIBCXX_ALLOC_TR_NESTED_TYPE(size_type, 156 typename make_unsigned<difference_type>::type) 157 158 /** 159 * @brief The allocator's size type 160 * 161 * @c Alloc::size_type if that type exists, otherwise 162 * <tt> make_unsigned<difference_type>::type </tt> 163 */ 164 typedef __size_type size_type; 165 166 _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_copy_assignment, 167 false_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 typedef __propagate_on_container_copy_assignment 176 propagate_on_container_copy_assignment; 177 178 _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_move_assignment, 179 false_type) 180 181 /** 182 * @brief How the allocator is propagated on move assignment 183 * 184 * @c Alloc::propagate_on_container_move_assignment if that type exists, 185 * otherwise @c false_type 186 */ 187 typedef __propagate_on_container_move_assignment 188 propagate_on_container_move_assignment; 189 190 _GLIBCXX_ALLOC_TR_NESTED_TYPE(propagate_on_container_swap, 191 false_type) 192 193 /** 194 * @brief How the allocator is propagated on swap 195 * 196 * @c Alloc::propagate_on_container_swap if that type exists, 197 * otherwise @c false_type 198 */ 199 typedef __propagate_on_container_swap propagate_on_container_swap; 200 201 #undef _GLIBCXX_ALLOC_TR_NESTED_TYPE 202 203 template<typename _Tp> 204 using rebind_alloc = typename __alloctr_rebind<_Alloc, _Tp>::__type; 205 template<typename _Tp> 206 using rebind_traits = allocator_traits<rebind_alloc<_Tp>>; 207 208 private: 209 template<typename _Alloc2> 210 struct __allocate_helper 211 { 212 template<typename _Alloc3, 213 typename = decltype(std::declval<_Alloc3*>()->allocate( 214 std::declval<size_type>(), 215 std::declval<const_void_pointer>()))> 216 static true_type __test(int); 217 218 template<typename> 219 static false_type __test(...); 220 221 typedef decltype(__test<_Alloc>(0)) type; 222 static const bool value = type::value; 223 }; 224 225 template<typename _Alloc2> 226 static typename 227 enable_if<__allocate_helper<_Alloc2>::value, pointer>::type 228 _S_allocate(_Alloc2& __a, size_type __n, const_void_pointer __hint) 229 { return __a.allocate(__n, __hint); } 230 231 template<typename _Alloc2> 232 static typename 233 enable_if<!__allocate_helper<_Alloc2>::value, pointer>::type 234 _S_allocate(_Alloc2& __a, size_type __n, ...) 235 { return __a.allocate(__n); } 236 237 template<typename _Tp, typename... _Args> 238 struct __construct_helper 239 { 240 template<typename _Alloc2, 241 typename = decltype(std::declval<_Alloc2*>()->construct( 242 std::declval<_Tp*>(), std::declval<_Args>()...))> 243 static true_type __test(int); 244 245 template<typename> 246 static false_type __test(...); 247 248 typedef decltype(__test<_Alloc>(0)) type; 249 static const bool value = type::value; 250 }; 251 252 template<typename _Tp, typename... _Args> 253 static typename 254 enable_if<__construct_helper<_Tp, _Args...>::value, void>::type 255 _S_construct(_Alloc& __a, _Tp* __p, _Args&&... __args) 256 { __a.construct(__p, std::forward<_Args>(__args)...); } 257 258 template<typename _Tp, typename... _Args> 259 static typename 260 enable_if<__and_<__not_<__construct_helper<_Tp, _Args...>>, 261 is_constructible<_Tp, _Args...>>::value, void>::type 262 _S_construct(_Alloc&, _Tp* __p, _Args&&... __args) 263 { ::new((void*)__p) _Tp(std::forward<_Args>(__args)...); } 264 265 template<typename _Tp> 266 struct __destroy_helper 267 { 268 template<typename _Alloc2, 269 typename = decltype(std::declval<_Alloc2*>()->destroy( 270 std::declval<_Tp*>()))> 271 static true_type __test(int); 272 273 template<typename> 274 static false_type __test(...); 275 276 typedef decltype(__test<_Alloc>(0)) type; 277 static const bool value = type::value; 278 }; 279 280 template<typename _Tp> 281 static typename enable_if<__destroy_helper<_Tp>::value, void>::type 282 _S_destroy(_Alloc& __a, _Tp* __p) 283 { __a.destroy(__p); } 284 285 template<typename _Tp> 286 static typename enable_if<!__destroy_helper<_Tp>::value, void>::type 287 _S_destroy(_Alloc&, _Tp* __p) 288 { __p->~_Tp(); } 289 290 template<typename _Alloc2> 291 struct __maxsize_helper 292 { 293 template<typename _Alloc3, 294 typename = decltype(std::declval<_Alloc3*>()->max_size())> 295 static true_type __test(int); 296 297 template<typename> 298 static false_type __test(...); 299 300 typedef decltype(__test<_Alloc2>(0)) type; 301 static const bool value = type::value; 302 }; 303 304 template<typename _Alloc2> 305 static typename 306 enable_if<__maxsize_helper<_Alloc2>::value, size_type>::type 307 _S_max_size(_Alloc2& __a) 308 { return __a.max_size(); } 309 310 template<typename _Alloc2> 311 static typename 312 enable_if<!__maxsize_helper<_Alloc2>::value, size_type>::type 313 _S_max_size(_Alloc2&) 314 { return __gnu_cxx::__numeric_traits<size_type>::__max; } 315 316 template<typename _Alloc2> 317 struct __select_helper 318 { 319 template<typename _Alloc3, typename 320 = decltype(std::declval<_Alloc3*>() 321 ->select_on_container_copy_construction())> 322 static true_type __test(int); 323 324 template<typename> 325 static false_type __test(...); 326 327 typedef decltype(__test<_Alloc2>(0)) type; 328 static const bool value = type::value; 329 }; 330 template<typename _Alloc2> 331 static typename 332 enable_if<__select_helper<_Alloc2>::value, _Alloc2>::type 333 _S_select(_Alloc2& __a) 334 { return __a.select_on_container_copy_construction(); } 335 336 template<typename _Alloc2> 337 static typename 338 enable_if<!__select_helper<_Alloc2>::value, _Alloc2>::type 339 _S_select(_Alloc2& __a) 340 { return __a; } 341 342 public: 343 344 /** 345 * @brief Allocate memory. 346 * @param __a An allocator. 347 * @param __n The number of objects to allocate space for. 348 * 349 * Calls @c a.allocate(n) 350 */ 351 static pointer 352 allocate(_Alloc& __a, size_type __n) 353 { return __a.allocate(__n); } 354 355 /** 356 * @brief Allocate memory. 357 * @param __a An allocator. 358 * @param __n The number of objects to allocate space for. 359 * @param __hint Aid to locality. 360 * @return Memory of suitable size and alignment for @a n objects 361 * of type @c value_type 362 * 363 * Returns <tt> a.allocate(n, hint) </tt> if that expression is 364 * well-formed, otherwise returns @c a.allocate(n) 365 */ 366 static pointer 367 allocate(_Alloc& __a, size_type __n, const_void_pointer __hint) 368 { return _S_allocate(__a, __n, __hint); } 369 370 /** 371 * @brief Deallocate memory. 372 * @param __a An allocator. 373 * @param __p Pointer to the memory to deallocate. 374 * @param __n The number of objects space was allocated for. 375 * 376 * Calls <tt> a.deallocate(p, n) </tt> 377 */ 378 static void deallocate(_Alloc& __a, pointer __p, size_type __n) 379 { __a.deallocate(__p, __n); } 380 381 /** 382 * @brief Construct an object of type @a _Tp 383 * @param __a An allocator. 384 * @param __p Pointer to memory of suitable size and alignment for Tp 385 * @param __args Constructor arguments. 386 * 387 * Calls <tt> __a.construct(__p, std::forward<Args>(__args)...) </tt> 388 * if that expression is well-formed, otherwise uses placement-new 389 * to construct an object of type @a _Tp at location @a __p from the 390 * arguments @a __args... 391 */ 392 template<typename _Tp, typename... _Args> 393 static auto construct(_Alloc& __a, _Tp* __p, _Args&&... __args) 394 -> decltype(_S_construct(__a, __p, std::forward<_Args>(__args)...)) 395 { _S_construct(__a, __p, std::forward<_Args>(__args)...); } 396 397 /** 398 * @brief Destroy an object of type @a _Tp 399 * @param __a An allocator. 400 * @param __p Pointer to the object to destroy 401 * 402 * Calls @c __a.destroy(__p) if that expression is well-formed, 403 * otherwise calls @c __p->~_Tp() 404 */ 405 template <class _Tp> 406 static void destroy(_Alloc& __a, _Tp* __p) 407 { _S_destroy(__a, __p); } 408 409 /** 410 * @brief The maximum supported allocation size 411 * @param __a An allocator. 412 * @return @c __a.max_size() or @c numeric_limits<size_type>::max() 413 * 414 * Returns @c __a.max_size() if that expression is well-formed, 415 * otherwise returns @c numeric_limits<size_type>::max() 416 */ 417 static size_type max_size(const _Alloc& __a) 418 { return _S_max_size(__a); } 419 420 /** 421 * @brief Obtain an allocator to use when copying a container. 422 * @param __rhs An allocator. 423 * @return @c __rhs.select_on_container_copy_construction() or @a __rhs 424 * 425 * Returns @c __rhs.select_on_container_copy_construction() if that 426 * expression is well-formed, otherwise returns @a __rhs 427 */ 428 static _Alloc 429 select_on_container_copy_construction(const _Alloc& __rhs) 430 { return _S_select(__rhs); } 431 }; 432 433 template<typename _Alloc> 434 template<typename _Alloc2> 435 const bool allocator_traits<_Alloc>::__allocate_helper<_Alloc2>::value; 436 437 template<typename _Alloc> 438 template<typename _Tp, typename... _Args> 439 const bool 440 allocator_traits<_Alloc>::__construct_helper<_Tp, _Args...>::value; 441 442 template<typename _Alloc> 443 template<typename _Tp> 444 const bool allocator_traits<_Alloc>::__destroy_helper<_Tp>::value; 445 446 template<typename _Alloc> 447 template<typename _Alloc2> 448 const bool allocator_traits<_Alloc>::__maxsize_helper<_Alloc2>::value; 449 450 template<typename _Alloc> 451 template<typename _Alloc2> 452 const bool allocator_traits<_Alloc>::__select_helper<_Alloc2>::value; 453 454 template<typename _Alloc> 455 inline void 456 __do_alloc_on_copy(_Alloc& __one, const _Alloc& __two, true_type) 457 { __one = __two; } 458 459 template<typename _Alloc> 460 inline void 461 __do_alloc_on_copy(_Alloc&, const _Alloc&, false_type) 462 { } 463 464 template<typename _Alloc> 465 inline void __alloc_on_copy(_Alloc& __one, const _Alloc& __two) 466 { 467 typedef allocator_traits<_Alloc> __traits; 468 typedef typename __traits::propagate_on_container_copy_assignment __pocca; 469 __do_alloc_on_copy(__one, __two, __pocca()); 470 } 471 472 template<typename _Alloc> 473 inline _Alloc __alloc_on_copy(const _Alloc& __a) 474 { 475 typedef allocator_traits<_Alloc> __traits; 476 return __traits::select_on_container_copy_construction(__a); 477 } 478 479 template<typename _Alloc> 480 inline void __do_alloc_on_move(_Alloc& __one, _Alloc& __two, true_type) 481 { __one = std::move(__two); } 482 483 template<typename _Alloc> 484 inline void __do_alloc_on_move(_Alloc&, _Alloc&, false_type) 485 { } 486 487 template<typename _Alloc> 488 inline void __alloc_on_move(_Alloc& __one, _Alloc& __two) 489 { 490 typedef allocator_traits<_Alloc> __traits; 491 typedef typename __traits::propagate_on_container_move_assignment __pocma; 492 __do_alloc_on_move(__one, __two, __pocma()); 493 } 494 495 template<typename _Alloc> 496 inline void __do_alloc_on_swap(_Alloc& __one, _Alloc& __two, true_type) 497 { 498 using std::swap; 499 swap(__one, __two); 500 } 501 502 template<typename _Alloc> 503 inline void __do_alloc_on_swap(_Alloc&, _Alloc&, false_type) 504 { } 505 506 template<typename _Alloc> 507 inline void __alloc_on_swap(_Alloc& __one, _Alloc& __two) 508 { 509 typedef allocator_traits<_Alloc> __traits; 510 typedef typename __traits::propagate_on_container_swap __pocs; 511 __do_alloc_on_swap(__one, __two, __pocs()); 512 } 513 514 template<typename _Alloc> 515 class __is_copy_insertable_impl 516 { 517 typedef allocator_traits<_Alloc> _Traits; 518 519 template<typename _Up, typename 520 = decltype(_Traits::construct(std::declval<_Alloc&>(), 521 std::declval<_Up*>(), 522 std::declval<const _Up&>()))> 523 static true_type 524 _M_select(int); 525 526 template<typename _Up> 527 static false_type 528 _M_select(...); 529 530 public: 531 typedef decltype(_M_select<typename _Alloc::value_type>(0)) type; 532 }; 533 534 // true if _Alloc::value_type is CopyInsertable into containers using _Alloc 535 template<typename _Alloc> 536 struct __is_copy_insertable 537 : __is_copy_insertable_impl<_Alloc>::type 538 { }; 539 540 // std::allocator<_Tp> just requires CopyConstructible 541 template<typename _Tp> 542 struct __is_copy_insertable<allocator<_Tp>> 543 : is_copy_constructible<_Tp> 544 { }; 545 546 // Used to allow copy construction of unordered containers 547 template<bool> struct __allow_copy_cons { }; 548 549 // Used to delete copy constructor of unordered containers 550 template<> 551 struct __allow_copy_cons<false> 552 { 553 __allow_copy_cons() = default; 554 __allow_copy_cons(const __allow_copy_cons&) = delete; 555 __allow_copy_cons(__allow_copy_cons&&) = default; 556 __allow_copy_cons& operator=(const __allow_copy_cons&) = default; 557 __allow_copy_cons& operator=(__allow_copy_cons&&) = default; 558 }; 559 560 template<typename _Alloc> 561 using __check_copy_constructible 562 = __allow_copy_cons<__is_copy_insertable<_Alloc>::value>; 563 564 _GLIBCXX_END_NAMESPACE_VERSION 565 } // namespace std 566 567 #endif 568 #endif 569