1 2 // Copyright 2005-2011 Daniel James. 3 // Copyright 2009 Pablo Halpern. 4 // Distributed under the Boost Software License, Version 1.0. (See accompanying 5 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 6 7 // See http://www.boost.org/libs/unordered for documentation 8 9 #ifndef BOOST_UNORDERED_ALLOCATE_HPP 10 #define BOOST_UNORDERED_ALLOCATE_HPP 11 12 #include <boost/config.hpp> 13 #if defined(BOOST_HAS_PRAGMA_ONCE) 14 #pragma once 15 #endif 16 17 #include <boost/unordered/detail/fwd.hpp> 18 #include <boost/move/move.hpp> 19 #include <boost/preprocessor/cat.hpp> 20 #include <boost/preprocessor/inc.hpp> 21 #include <boost/preprocessor/dec.hpp> 22 #include <boost/preprocessor/repetition/enum.hpp> 23 #include <boost/preprocessor/repetition/enum_params.hpp> 24 #include <boost/preprocessor/repetition/enum_binary_params.hpp> 25 #include <boost/preprocessor/repetition/repeat_from_to.hpp> 26 #include <boost/type_traits/is_class.hpp> 27 #include <boost/type_traits/add_lvalue_reference.hpp> 28 #include <boost/tuple/tuple.hpp> 29 #include <boost/utility/enable_if.hpp> 30 #include <boost/utility/addressof.hpp> 31 #include <boost/detail/select_type.hpp> 32 #include <boost/assert.hpp> 33 #include <utility> 34 35 #if !defined(BOOST_NO_CXX11_HDR_TUPLE) 36 #include <tuple> 37 #endif 38 39 #if defined(BOOST_MSVC) 40 #pragma warning(push) 41 #pragma warning(disable:4512) // assignment operator could not be generated. 42 #pragma warning(disable:4345) // behavior change: an object of POD type 43 // constructed with an initializer of the form () 44 // will be default-initialized. 45 #endif 46 47 #define BOOST_UNORDERED_EMPLACE_LIMIT 10 48 49 namespace boost { namespace unordered { namespace detail { 50 51 //////////////////////////////////////////////////////////////////////////// 52 // Bits and pieces for implementing traits 53 54 template <typename T> typename boost::add_lvalue_reference<T>::type make(); 55 struct choice9 { typedef char (&type)[9]; }; 56 struct choice8 : choice9 { typedef char (&type)[8]; }; 57 struct choice7 : choice8 { typedef char (&type)[7]; }; 58 struct choice6 : choice7 { typedef char (&type)[6]; }; 59 struct choice5 : choice6 { typedef char (&type)[5]; }; 60 struct choice4 : choice5 { typedef char (&type)[4]; }; 61 struct choice3 : choice4 { typedef char (&type)[3]; }; 62 struct choice2 : choice3 { typedef char (&type)[2]; }; 63 struct choice1 : choice2 { typedef char (&type)[1]; }; 64 choice1 choose(); 65 66 typedef choice1::type yes_type; 67 typedef choice2::type no_type; 68 69 struct private_type 70 { 71 private_type const &operator,(int) const; 72 }; 73 74 template <typename T> 75 no_type is_private_type(T const&); 76 yes_type is_private_type(private_type const&); 77 78 struct convert_from_anything { 79 template <typename T> 80 convert_from_anything(T const&); 81 }; 82 83 //////////////////////////////////////////////////////////////////////////// 84 // emplace_args 85 // 86 // Either forwarding variadic arguments, or storing the arguments in 87 // emplace_args##n 88 89 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 90 91 #define BOOST_UNORDERED_EMPLACE_TEMPLATE typename... Args 92 #define BOOST_UNORDERED_EMPLACE_ARGS BOOST_FWD_REF(Args)... args 93 #define BOOST_UNORDERED_EMPLACE_FORWARD boost::forward<Args>(args)... 94 95 #define BOOST_UNORDERED_EMPLACE_ARGS1(a0) a0 96 #define BOOST_UNORDERED_EMPLACE_ARGS2(a0, a1) a0, a1 97 #define BOOST_UNORDERED_EMPLACE_ARGS3(a0, a1, a2) a0, a1, a2 98 99 #else 100 101 #define BOOST_UNORDERED_EMPLACE_TEMPLATE typename Args 102 #define BOOST_UNORDERED_EMPLACE_ARGS Args const& args 103 #define BOOST_UNORDERED_EMPLACE_FORWARD args 104 105 #define BOOST_UNORDERED_FWD_PARAM(z, n, a) \ 106 BOOST_FWD_REF(BOOST_PP_CAT(A, n)) BOOST_PP_CAT(a, n) 107 108 #define BOOST_UNORDERED_CALL_FORWARD(z, i, a) \ 109 boost::forward<BOOST_PP_CAT(A,i)>(BOOST_PP_CAT(a,i)) 110 111 #define BOOST_UNORDERED_EARGS(z, n, _) \ 112 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ 113 struct BOOST_PP_CAT(emplace_args, n) \ 114 { \ 115 BOOST_PP_REPEAT_##z(n, BOOST_UNORDERED_EARGS_MEMBER, _) \ 116 BOOST_PP_CAT(emplace_args, n) ( \ 117 BOOST_PP_ENUM_BINARY_PARAMS_Z(z, n, Arg, b) \ 118 ) : BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_EARGS_INIT, _) \ 119 {} \ 120 \ 121 }; \ 122 \ 123 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ 124 inline BOOST_PP_CAT(emplace_args, n) < \ 125 BOOST_PP_ENUM_PARAMS_Z(z, n, A) \ 126 > create_emplace_args( \ 127 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, b) \ 128 ) \ 129 { \ 130 BOOST_PP_CAT(emplace_args, n) < \ 131 BOOST_PP_ENUM_PARAMS_Z(z, n, A) \ 132 > e(BOOST_PP_ENUM_PARAMS_Z(z, n, b)); \ 133 return e; \ 134 } 135 136 #define BOOST_UNORDERED_EMPLACE_ARGS1 create_emplace_args 137 #define BOOST_UNORDERED_EMPLACE_ARGS2 create_emplace_args 138 #define BOOST_UNORDERED_EMPLACE_ARGS3 create_emplace_args 139 140 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 141 142 #define BOOST_UNORDERED_EARGS_MEMBER(z, n, _) \ 143 typedef BOOST_FWD_REF(BOOST_PP_CAT(A, n)) BOOST_PP_CAT(Arg, n); \ 144 BOOST_PP_CAT(Arg, n) BOOST_PP_CAT(a, n); 145 146 #define BOOST_UNORDERED_EARGS_INIT(z, n, _) \ 147 BOOST_PP_CAT(a, n)( \ 148 boost::forward<BOOST_PP_CAT(A,n)>(BOOST_PP_CAT(b, n))) 149 150 #else 151 152 #define BOOST_UNORDERED_EARGS_MEMBER(z, n, _) \ 153 typedef typename boost::add_lvalue_reference<BOOST_PP_CAT(A, n)>::type \ 154 BOOST_PP_CAT(Arg, n); \ 155 BOOST_PP_CAT(Arg, n) BOOST_PP_CAT(a, n); 156 157 #define BOOST_UNORDERED_EARGS_INIT(z, n, _) \ 158 BOOST_PP_CAT(a, n)(BOOST_PP_CAT(b, n)) 159 160 #endif 161 162 BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, BOOST_UNORDERED_EARGS, 163 _) 164 165 #undef BOOST_UNORDERED_DEFINE_EMPLACE_ARGS 166 #undef BOOST_UNORDERED_EARGS_MEMBER 167 #undef BOOST_UNORDERED_EARGS_INIT 168 169 #endif 170 171 }}} 172 173 //////////////////////////////////////////////////////////////////////////////// 174 // 175 // Pick which version of allocator_traits to use 176 // 177 // 0 = Own partial implementation 178 // 1 = std::allocator_traits 179 // 2 = boost::container::allocator_traits 180 181 #if !defined(BOOST_UNORDERED_USE_ALLOCATOR_TRAITS) 182 # if defined(__GXX_EXPERIMENTAL_CXX0X__) && \ 183 (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 7)) 184 # define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 0 185 # elif defined(BOOST_MSVC) 186 # if BOOST_MSVC < 1400 187 // Use container's allocator_traits for older versions of Visual 188 // C++ as I don't test with them. 189 # define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 2 190 # endif 191 # endif 192 #endif 193 194 #if !defined(BOOST_UNORDERED_USE_ALLOCATOR_TRAITS) 195 # define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 0 196 #endif 197 198 //////////////////////////////////////////////////////////////////////////////// 199 // 200 // Some utilities for implementing allocator_traits, but useful elsewhere so 201 // they're always defined. 202 203 #if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS) 204 # include <type_traits> 205 #endif 206 207 namespace boost { namespace unordered { namespace detail { 208 209 //////////////////////////////////////////////////////////////////////////// 210 // Integral_constrant, true_type, false_type 211 // 212 // Uses the standard versions if available. 213 214 #if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS) 215 216 using std::integral_constant; 217 using std::true_type; 218 using std::false_type; 219 220 #else 221 222 template <typename T, T Value> 223 struct integral_constant { enum { value = Value }; }; 224 225 typedef boost::unordered::detail::integral_constant<bool, true> true_type; 226 typedef boost::unordered::detail::integral_constant<bool, false> false_type; 227 228 #endif 229 230 //////////////////////////////////////////////////////////////////////////// 231 // Explicitly call a destructor 232 233 #if defined(BOOST_MSVC) 234 #pragma warning(push) 235 #pragma warning(disable:4100) // unreferenced formal parameter 236 #endif 237 238 namespace func { 239 template <class T> destroy(T * x)240 inline void destroy(T* x) { 241 x->~T(); 242 } 243 } 244 245 #if defined(BOOST_MSVC) 246 #pragma warning(pop) 247 #endif 248 249 //////////////////////////////////////////////////////////////////////////// 250 // Expression test mechanism 251 // 252 // When SFINAE expressions are available, define 253 // BOOST_UNORDERED_HAS_FUNCTION which can check if a function call is 254 // supported by a class, otherwise define BOOST_UNORDERED_HAS_MEMBER which 255 // can detect if a class has the specified member, but not that it has the 256 // correct type, this is good enough for a passable impression of 257 // allocator_traits. 258 259 #if !defined(BOOST_NO_SFINAE_EXPR) 260 261 template <typename T, unsigned int> struct expr_test; 262 template <typename T> struct expr_test<T, sizeof(char)> : T {}; 263 264 # define BOOST_UNORDERED_CHECK_EXPRESSION(count, result, expression) \ 265 template <typename U> \ 266 static typename boost::unordered::detail::expr_test< \ 267 BOOST_PP_CAT(choice, result), \ 268 sizeof(for_expr_test(( \ 269 (expression), \ 270 0)))>::type test( \ 271 BOOST_PP_CAT(choice, count)) 272 273 # define BOOST_UNORDERED_DEFAULT_EXPRESSION(count, result) \ 274 template <typename U> \ 275 static BOOST_PP_CAT(choice, result)::type test( \ 276 BOOST_PP_CAT(choice, count)) 277 278 # define BOOST_UNORDERED_HAS_FUNCTION(name, thing, args, _) \ 279 struct BOOST_PP_CAT(has_, name) \ 280 { \ 281 template <typename U> static char for_expr_test(U const&); \ 282 BOOST_UNORDERED_CHECK_EXPRESSION(1, 1, \ 283 boost::unordered::detail::make< thing >().name args); \ 284 BOOST_UNORDERED_DEFAULT_EXPRESSION(2, 2); \ 285 \ 286 enum { value = sizeof(test<T>(choose())) == sizeof(choice1::type) };\ 287 } 288 289 #else 290 291 template <typename T> struct identity { typedef T type; }; 292 293 # define BOOST_UNORDERED_CHECK_MEMBER(count, result, name, member) \ 294 \ 295 typedef typename boost::unordered::detail::identity<member>::type \ 296 BOOST_PP_CAT(check, count); \ 297 \ 298 template <BOOST_PP_CAT(check, count) e> \ 299 struct BOOST_PP_CAT(test, count) { \ 300 typedef BOOST_PP_CAT(choice, result) type; \ 301 }; \ 302 \ 303 template <class U> static typename \ 304 BOOST_PP_CAT(test, count)<&U::name>::type \ 305 test(BOOST_PP_CAT(choice, count)) 306 307 # define BOOST_UNORDERED_DEFAULT_MEMBER(count, result) \ 308 template <class U> static BOOST_PP_CAT(choice, result)::type \ 309 test(BOOST_PP_CAT(choice, count)) 310 311 # define BOOST_UNORDERED_HAS_MEMBER(name) \ 312 struct BOOST_PP_CAT(has_, name) \ 313 { \ 314 struct impl { \ 315 struct base_mixin { int name; }; \ 316 struct base : public T, public base_mixin {}; \ 317 \ 318 BOOST_UNORDERED_CHECK_MEMBER(1, 1, name, int base_mixin::*); \ 319 BOOST_UNORDERED_DEFAULT_MEMBER(2, 2); \ 320 \ 321 enum { value = sizeof(choice2::type) == \ 322 sizeof(test<base>(choose())) \ 323 }; \ 324 }; \ 325 \ 326 enum { value = impl::value }; \ 327 } 328 329 #endif 330 331 }}} 332 333 //////////////////////////////////////////////////////////////////////////////// 334 // 335 // Allocator traits 336 // 337 // First our implementation, then later light wrappers around the alternatives 338 339 #if BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 0 340 341 # include <boost/limits.hpp> 342 # include <boost/utility/enable_if.hpp> 343 # include <boost/pointer_to_other.hpp> 344 # if defined(BOOST_NO_SFINAE_EXPR) 345 # include <boost/type_traits/is_same.hpp> 346 # endif 347 348 # if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) && \ 349 !defined(BOOST_NO_SFINAE_EXPR) 350 # define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 1 351 # else 352 # define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 0 353 # endif 354 355 namespace boost { namespace unordered { namespace detail { 356 357 // TODO: Does this match std::allocator_traits<Alloc>::rebind_alloc<T>? 358 template <typename Alloc, typename T> 359 struct rebind_wrap 360 { 361 typedef typename Alloc::BOOST_NESTED_TEMPLATE rebind<T>::other type; 362 }; 363 364 # if defined(BOOST_MSVC) && BOOST_MSVC <= 1400 365 366 # define BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(tname) \ 367 template <typename Tp, typename Default> \ 368 struct default_type_ ## tname { \ 369 \ 370 template <typename X> \ 371 static choice1::type test(choice1, typename X::tname* = 0); \ 372 \ 373 template <typename X> \ 374 static choice2::type test(choice2, void* = 0); \ 375 \ 376 struct DefaultWrap { typedef Default tname; }; \ 377 \ 378 enum { value = (1 == sizeof(test<Tp>(choose()))) }; \ 379 \ 380 typedef typename boost::detail::if_true<value>:: \ 381 BOOST_NESTED_TEMPLATE then<Tp, DefaultWrap> \ 382 ::type::tname type; \ 383 } 384 385 # else 386 387 template <typename T, typename T2> 388 struct sfinae : T2 {}; 389 390 # define BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(tname) \ 391 template <typename Tp, typename Default> \ 392 struct default_type_ ## tname { \ 393 \ 394 template <typename X> \ 395 static typename boost::unordered::detail::sfinae< \ 396 typename X::tname, choice1>::type \ 397 test(choice1); \ 398 \ 399 template <typename X> \ 400 static choice2::type test(choice2); \ 401 \ 402 struct DefaultWrap { typedef Default tname; }; \ 403 \ 404 enum { value = (1 == sizeof(test<Tp>(choose()))) }; \ 405 \ 406 typedef typename boost::detail::if_true<value>:: \ 407 BOOST_NESTED_TEMPLATE then<Tp, DefaultWrap> \ 408 ::type::tname type; \ 409 } 410 411 # endif 412 413 # define BOOST_UNORDERED_DEFAULT_TYPE(T,tname, arg) \ 414 typename default_type_ ## tname<T, arg>::type 415 416 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(pointer); 417 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(const_pointer); 418 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(void_pointer); 419 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(const_void_pointer); 420 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(difference_type); 421 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(size_type); 422 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(propagate_on_container_copy_assignment); 423 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(propagate_on_container_move_assignment); 424 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(propagate_on_container_swap); 425 426 # if !defined(BOOST_NO_SFINAE_EXPR) 427 428 template <typename T> 429 BOOST_UNORDERED_HAS_FUNCTION( 430 select_on_container_copy_construction, U const, (), 0 431 ); 432 433 template <typename T> 434 BOOST_UNORDERED_HAS_FUNCTION( 435 max_size, U const, (), 0 436 ); 437 438 # if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 439 440 template <typename T, typename ValueType, typename... Args> 441 BOOST_UNORDERED_HAS_FUNCTION( 442 construct, U, ( 443 boost::unordered::detail::make<ValueType*>(), 444 boost::unordered::detail::make<Args const>()...), 2 445 ); 446 447 # else 448 449 template <typename T, typename ValueType> 450 BOOST_UNORDERED_HAS_FUNCTION( 451 construct, U, ( 452 boost::unordered::detail::make<ValueType*>(), 453 boost::unordered::detail::make<ValueType const>()), 2 454 ); 455 456 # endif 457 458 template <typename T, typename ValueType> 459 BOOST_UNORDERED_HAS_FUNCTION( 460 destroy, U, (boost::unordered::detail::make<ValueType*>()), 1 461 ); 462 463 # else 464 465 template <typename T> 466 BOOST_UNORDERED_HAS_MEMBER(select_on_container_copy_construction); 467 468 template <typename T> 469 BOOST_UNORDERED_HAS_MEMBER(max_size); 470 471 template <typename T, typename ValueType> 472 BOOST_UNORDERED_HAS_MEMBER(construct); 473 474 template <typename T, typename ValueType> 475 BOOST_UNORDERED_HAS_MEMBER(destroy); 476 477 # endif 478 479 namespace func 480 { 481 482 template <typename Alloc> call_select_on_container_copy_construction(const Alloc & rhs,typename boost::enable_if_c<boost::unordered::detail::has_select_on_container_copy_construction<Alloc>::value,void * >::type=0)483 inline Alloc call_select_on_container_copy_construction(const Alloc& rhs, 484 typename boost::enable_if_c< 485 boost::unordered::detail:: 486 has_select_on_container_copy_construction<Alloc>::value, void* 487 >::type = 0) 488 { 489 return rhs.select_on_container_copy_construction(); 490 } 491 492 template <typename Alloc> call_select_on_container_copy_construction(const Alloc & rhs,typename boost::disable_if_c<boost::unordered::detail::has_select_on_container_copy_construction<Alloc>::value,void * >::type=0)493 inline Alloc call_select_on_container_copy_construction(const Alloc& rhs, 494 typename boost::disable_if_c< 495 boost::unordered::detail:: 496 has_select_on_container_copy_construction<Alloc>::value, void* 497 >::type = 0) 498 { 499 return rhs; 500 } 501 502 template <typename SizeType, typename Alloc> call_max_size(const Alloc & a,typename boost::enable_if_c<boost::unordered::detail::has_max_size<Alloc>::value,void * >::type=0)503 inline SizeType call_max_size(const Alloc& a, 504 typename boost::enable_if_c< 505 boost::unordered::detail::has_max_size<Alloc>::value, void* 506 >::type = 0) 507 { 508 return a.max_size(); 509 } 510 511 template <typename SizeType, typename Alloc> call_max_size(const Alloc &,typename boost::disable_if_c<boost::unordered::detail::has_max_size<Alloc>::value,void * >::type=0)512 inline SizeType call_max_size(const Alloc&, typename boost::disable_if_c< 513 boost::unordered::detail::has_max_size<Alloc>::value, void* 514 >::type = 0) 515 { 516 return (std::numeric_limits<SizeType>::max)(); 517 } 518 519 } // namespace func. 520 521 template <typename Alloc> 522 struct allocator_traits 523 { 524 typedef Alloc allocator_type; 525 typedef typename Alloc::value_type value_type; 526 527 typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, pointer, value_type*) 528 pointer; 529 530 template <typename T> 531 struct pointer_to_other : boost::pointer_to_other<pointer, T> {}; 532 533 typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, const_pointer, 534 typename pointer_to_other<const value_type>::type) 535 const_pointer; 536 537 //typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, void_pointer, 538 // typename pointer_to_other<void>::type) 539 // void_pointer; 540 // 541 //typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, const_void_pointer, 542 // typename pointer_to_other<const void>::type) 543 // const_void_pointer; 544 545 typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, difference_type, 546 std::ptrdiff_t) difference_type; 547 548 typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, size_type, std::size_t) 549 size_type; 550 551 // TODO: rebind_alloc and rebind_traits 552 allocateboost::unordered::detail::allocator_traits553 static pointer allocate(Alloc& a, size_type n) 554 { return a.allocate(n); } 555 556 // I never use this, so I'll just comment it out for now. 557 // 558 //static pointer allocate(Alloc& a, size_type n, 559 // const_void_pointer hint) 560 // { return DEFAULT_FUNC(allocate, pointer)(a, n, hint); } 561 deallocateboost::unordered::detail::allocator_traits562 static void deallocate(Alloc& a, pointer p, size_type n) 563 { a.deallocate(p, n); } 564 565 public: 566 567 # if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 568 569 template <typename T, typename... Args> 570 static typename boost::enable_if_c< 571 boost::unordered::detail::has_construct<Alloc, T, Args...> 572 ::value>::type constructboost::unordered::detail::allocator_traits573 construct(Alloc& a, T* p, BOOST_FWD_REF(Args)... x) 574 { 575 a.construct(p, boost::forward<Args>(x)...); 576 } 577 578 template <typename T, typename... Args> 579 static typename boost::disable_if_c< 580 boost::unordered::detail::has_construct<Alloc, T, Args...> 581 ::value>::type constructboost::unordered::detail::allocator_traits582 construct(Alloc&, T* p, BOOST_FWD_REF(Args)... x) 583 { 584 new ((void*) p) T(boost::forward<Args>(x)...); 585 } 586 587 template <typename T> 588 static typename boost::enable_if_c< 589 boost::unordered::detail::has_destroy<Alloc, T>::value>::type destroyboost::unordered::detail::allocator_traits590 destroy(Alloc& a, T* p) 591 { 592 a.destroy(p); 593 } 594 595 template <typename T> 596 static typename boost::disable_if_c< 597 boost::unordered::detail::has_destroy<Alloc, T>::value>::type destroyboost::unordered::detail::allocator_traits598 destroy(Alloc&, T* p) 599 { 600 boost::unordered::detail::func::destroy(p); 601 } 602 603 # elif !defined(BOOST_NO_SFINAE_EXPR) 604 605 template <typename T> 606 static typename boost::enable_if_c< 607 boost::unordered::detail::has_construct<Alloc, T>::value>::type 608 construct(Alloc& a, T* p, T const& x) 609 { 610 a.construct(p, x); 611 } 612 613 template <typename T> 614 static typename boost::disable_if_c< 615 boost::unordered::detail::has_construct<Alloc, T>::value>::type 616 construct(Alloc&, T* p, T const& x) 617 { 618 new ((void*) p) T(x); 619 } 620 621 template <typename T> 622 static typename boost::enable_if_c< 623 boost::unordered::detail::has_destroy<Alloc, T>::value>::type 624 destroy(Alloc& a, T* p) 625 { 626 a.destroy(p); 627 } 628 629 template <typename T> 630 static typename boost::disable_if_c< 631 boost::unordered::detail::has_destroy<Alloc, T>::value>::type 632 destroy(Alloc&, T* p) 633 { 634 boost::unordered::detail::func::destroy(p); 635 } 636 637 # else 638 639 // If we don't have SFINAE expressions, only call construct for the 640 // copy constructor for the allocator's value_type - as that's 641 // the only construct method that old fashioned allocators support. 642 643 template <typename T> 644 static void construct(Alloc& a, T* p, T const& x, 645 typename boost::enable_if_c< 646 boost::unordered::detail::has_construct<Alloc, T>::value && 647 boost::is_same<T, value_type>::value, 648 void*>::type = 0) 649 { 650 a.construct(p, x); 651 } 652 653 template <typename T> 654 static void construct(Alloc&, T* p, T const& x, 655 typename boost::disable_if_c< 656 boost::unordered::detail::has_construct<Alloc, T>::value && 657 boost::is_same<T, value_type>::value, 658 void*>::type = 0) 659 { 660 new ((void*) p) T(x); 661 } 662 663 template <typename T> 664 static void destroy(Alloc& a, T* p, 665 typename boost::enable_if_c< 666 boost::unordered::detail::has_destroy<Alloc, T>::value && 667 boost::is_same<T, value_type>::value, 668 void*>::type = 0) 669 { 670 a.destroy(p); 671 } 672 673 template <typename T> 674 static void destroy(Alloc&, T* p, 675 typename boost::disable_if_c< 676 boost::unordered::detail::has_destroy<Alloc, T>::value && 677 boost::is_same<T, value_type>::value, 678 void*>::type = 0) 679 { 680 boost::unordered::detail::func::destroy(p); 681 } 682 683 # endif 684 max_sizeboost::unordered::detail::allocator_traits685 static size_type max_size(const Alloc& a) 686 { 687 return boost::unordered::detail::func:: 688 call_max_size<size_type>(a); 689 } 690 691 // Allocator propagation on construction 692 select_on_container_copy_constructionboost::unordered::detail::allocator_traits693 static Alloc select_on_container_copy_construction(Alloc const& rhs) 694 { 695 return boost::unordered::detail::func:: 696 call_select_on_container_copy_construction(rhs); 697 } 698 699 // Allocator propagation on assignment and swap. 700 // Return true if lhs is modified. 701 typedef BOOST_UNORDERED_DEFAULT_TYPE( 702 Alloc, propagate_on_container_copy_assignment, false_type) 703 propagate_on_container_copy_assignment; 704 typedef BOOST_UNORDERED_DEFAULT_TYPE( 705 Alloc,propagate_on_container_move_assignment, false_type) 706 propagate_on_container_move_assignment; 707 typedef BOOST_UNORDERED_DEFAULT_TYPE( 708 Alloc,propagate_on_container_swap,false_type) 709 propagate_on_container_swap; 710 }; 711 }}} 712 713 # undef BOOST_UNORDERED_DEFAULT_TYPE_TMPLT 714 # undef BOOST_UNORDERED_DEFAULT_TYPE 715 716 //////////////////////////////////////////////////////////////////////////////// 717 // 718 // std::allocator_traits 719 720 #elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 1 721 722 # include <memory> 723 724 # define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 1 725 726 namespace boost { namespace unordered { namespace detail { 727 728 template <typename Alloc> 729 struct allocator_traits : std::allocator_traits<Alloc> {}; 730 731 template <typename Alloc, typename T> 732 struct rebind_wrap 733 { 734 typedef typename std::allocator_traits<Alloc>:: 735 template rebind_alloc<T> type; 736 }; 737 }}} 738 739 //////////////////////////////////////////////////////////////////////////////// 740 // 741 // boost::container::allocator_traits 742 743 #elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 2 744 745 # include <boost/container/allocator_traits.hpp> 746 747 # define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 0 748 749 namespace boost { namespace unordered { namespace detail { 750 751 template <typename Alloc> 752 struct allocator_traits : 753 boost::container::allocator_traits<Alloc> {}; 754 755 template <typename Alloc, typename T> 756 struct rebind_wrap : 757 boost::container::allocator_traits<Alloc>:: 758 template portable_rebind_alloc<T> 759 {}; 760 761 }}} 762 763 #else 764 765 #error "Invalid BOOST_UNORDERED_USE_ALLOCATOR_TRAITS value." 766 767 #endif 768 769 770 namespace boost { namespace unordered { namespace detail { namespace func { 771 772 //////////////////////////////////////////////////////////////////////////// 773 // call_construct 774 775 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 776 777 # if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 778 779 template <typename Alloc, typename T, typename... Args> call_construct(Alloc & alloc,T * address,BOOST_FWD_REF (Args)...args)780 inline void call_construct(Alloc& alloc, T* address, 781 BOOST_FWD_REF(Args)... args) 782 { 783 boost::unordered::detail::allocator_traits<Alloc>::construct(alloc, 784 address, boost::forward<Args>(args)...); 785 } 786 787 template <typename Alloc, typename T> destroy_value_impl(Alloc & alloc,T * x)788 inline void destroy_value_impl(Alloc& alloc, T* x) { 789 boost::unordered::detail::allocator_traits<Alloc>::destroy(alloc, x); 790 } 791 792 793 # else 794 795 template <typename Alloc, typename T, typename... Args> 796 inline void call_construct(Alloc&, T* address, 797 BOOST_FWD_REF(Args)... args) 798 { 799 new((void*) address) T(boost::forward<Args>(args)...); 800 } 801 802 template <typename Alloc, typename T> 803 inline void destroy_value_impl(Alloc&, T* x) { 804 boost::unordered::detail::func::destroy(x); 805 } 806 807 808 # endif 809 810 #else 811 812 template <typename Alloc, typename T> 813 inline void destroy_value_impl(Alloc&, T* x) { 814 boost::unordered::detail::func::destroy(x); 815 } 816 817 #endif 818 819 //////////////////////////////////////////////////////////////////////////// 820 // Construct from tuple 821 // 822 // Used for piecewise construction. 823 824 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 825 826 # define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(n, namespace_) \ 827 template<typename Alloc, typename T> \ 828 void construct_from_tuple(Alloc& alloc, T* ptr, namespace_ tuple<>) \ 829 { \ 830 boost::unordered::detail::func::call_construct(alloc, ptr); \ 831 } \ 832 \ 833 BOOST_PP_REPEAT_FROM_TO(1, n, \ 834 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL, namespace_) 835 836 # define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL(z, n, namespace_) \ 837 template<typename Alloc, typename T, \ 838 BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ 839 void construct_from_tuple(Alloc& alloc, T* ptr, \ 840 namespace_ tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \ 841 { \ 842 boost::unordered::detail::func::call_construct(alloc, ptr, \ 843 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_) \ 844 ); \ 845 } 846 847 # define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) \ 848 namespace_ get<n>(x) 849 850 #elif !defined(__SUNPRO_CC) 851 852 # define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(n, namespace_) \ 853 template<typename Alloc, typename T> \ 854 void construct_from_tuple(Alloc&, T* ptr, namespace_ tuple<>) \ 855 { \ 856 new ((void*) ptr) T(); \ 857 } \ 858 \ 859 BOOST_PP_REPEAT_FROM_TO(1, n, \ 860 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL, namespace_) 861 862 # define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL(z, n, namespace_) \ 863 template<typename Alloc, typename T, \ 864 BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ 865 void construct_from_tuple(Alloc&, T* ptr, \ 866 namespace_ tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \ 867 { \ 868 new ((void*) ptr) T( \ 869 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_) \ 870 ); \ 871 } 872 873 # define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) \ 874 namespace_ get<n>(x) 875 876 #else 877 878 template <int N> struct length {}; 879 880 # define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(n, namespace_) \ 881 template<typename Alloc, typename T> \ 882 void construct_from_tuple_impl( \ 883 boost::unordered::detail::func::length<0>, Alloc&, T* ptr, \ 884 namespace_ tuple<>) \ 885 { \ 886 new ((void*) ptr) T(); \ 887 } \ 888 \ 889 BOOST_PP_REPEAT_FROM_TO(1, n, \ 890 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL, namespace_) 891 892 # define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL(z, n, namespace_) \ 893 template<typename Alloc, typename T, \ 894 BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ 895 void construct_from_tuple_impl( \ 896 boost::unordered::detail::func::length<n>, Alloc&, T* ptr, \ 897 namespace_ tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \ 898 { \ 899 new ((void*) ptr) T( \ 900 BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_) \ 901 ); \ 902 } 903 904 # define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) \ 905 namespace_ get<n>(x) 906 907 #endif 908 909 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(10, boost::) 910 911 #if !defined(__SUNPRO_CC) && !defined(BOOST_NO_CXX11_HDR_TUPLE) 912 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(10, std::) 913 #endif 914 915 #undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE 916 #undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL 917 #undef BOOST_UNORDERED_GET_TUPLE_ARG 918 919 #if defined(__SUNPRO_CC) 920 921 template <typename Alloc, typename T, typename Tuple> construct_from_tuple(Alloc & alloc,T * ptr,Tuple const & x)922 void construct_from_tuple(Alloc& alloc, T* ptr, Tuple const& x) 923 { 924 construct_from_tuple_impl( 925 boost::unordered::detail::func::length< 926 boost::tuples::length<Tuple>::value>(), 927 alloc, ptr, x); 928 } 929 930 #endif 931 932 //////////////////////////////////////////////////////////////////////////// 933 // Trait to check for piecewise construction. 934 935 template <typename A0> 936 struct use_piecewise { 937 static choice1::type test(choice1, 938 boost::unordered::piecewise_construct_t); 939 940 static choice2::type test(choice2, ...); 941 942 enum { value = sizeof(choice1::type) == 943 sizeof(test(choose(), boost::unordered::detail::make<A0>())) }; 944 }; 945 946 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 947 948 //////////////////////////////////////////////////////////////////////////// 949 // Construct from variadic parameters 950 951 // For the standard pair constructor. 952 953 template <typename Alloc, typename T, typename... Args> construct_value_impl(Alloc & alloc,T * address,BOOST_FWD_REF (Args)...args)954 inline void construct_value_impl(Alloc& alloc, T* address, 955 BOOST_FWD_REF(Args)... args) 956 { 957 boost::unordered::detail::func::call_construct(alloc, 958 address, boost::forward<Args>(args)...); 959 } 960 961 // Special case for piece_construct 962 // 963 // TODO: When possible, it might be better to use std::pair's 964 // constructor for std::piece_construct with std::tuple. 965 966 template <typename Alloc, typename A, typename B, 967 typename A0, typename A1, typename A2> 968 inline typename enable_if<use_piecewise<A0>, void>::type construct_value_impl(Alloc & alloc,std::pair<A,B> * address,BOOST_FWD_REF (A0),BOOST_FWD_REF (A1)a1,BOOST_FWD_REF (A2)a2)969 construct_value_impl(Alloc& alloc, std::pair<A, B>* address, 970 BOOST_FWD_REF(A0), BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2) 971 { 972 boost::unordered::detail::func::construct_from_tuple(alloc, 973 boost::addressof(address->first), boost::forward<A1>(a1)); 974 boost::unordered::detail::func::construct_from_tuple(alloc, 975 boost::addressof(address->second), boost::forward<A2>(a2)); 976 } 977 978 #else // BOOST_NO_CXX11_VARIADIC_TEMPLATES 979 980 //////////////////////////////////////////////////////////////////////////////// 981 // Construct from emplace_args 982 983 // Explicitly write out first three overloads for the sake of sane 984 // error messages. 985 986 template <typename Alloc, typename T, typename A0> construct_value_impl(Alloc &,T * address,emplace_args1<A0> const & args)987 inline void construct_value_impl(Alloc&, T* address, 988 emplace_args1<A0> const& args) 989 { 990 new((void*) address) T(boost::forward<A0>(args.a0)); 991 } 992 993 template <typename Alloc, typename T, typename A0, typename A1> construct_value_impl(Alloc &,T * address,emplace_args2<A0,A1> const & args)994 inline void construct_value_impl(Alloc&, T* address, 995 emplace_args2<A0, A1> const& args) 996 { 997 new((void*) address) T( 998 boost::forward<A0>(args.a0), 999 boost::forward<A1>(args.a1) 1000 ); 1001 } 1002 1003 template <typename Alloc, typename T, typename A0, typename A1, typename A2> construct_value_impl(Alloc &,T * address,emplace_args3<A0,A1,A2> const & args)1004 inline void construct_value_impl(Alloc&, T* address, 1005 emplace_args3<A0, A1, A2> const& args) 1006 { 1007 new((void*) address) T( 1008 boost::forward<A0>(args.a0), 1009 boost::forward<A1>(args.a1), 1010 boost::forward<A2>(args.a2) 1011 ); 1012 } 1013 1014 // Use a macro for the rest. 1015 1016 #define BOOST_UNORDERED_CONSTRUCT_IMPL(z, num_params, _) \ 1017 template < \ 1018 typename Alloc, typename T, \ 1019 BOOST_PP_ENUM_PARAMS_Z(z, num_params, typename A) \ 1020 > \ 1021 inline void construct_value_impl(Alloc&, T* address, \ 1022 boost::unordered::detail::BOOST_PP_CAT(emplace_args,num_params) < \ 1023 BOOST_PP_ENUM_PARAMS_Z(z, num_params, A) \ 1024 > const& args) \ 1025 { \ 1026 new((void*) address) T( \ 1027 BOOST_PP_ENUM_##z(num_params, BOOST_UNORDERED_CALL_FORWARD, \ 1028 args.a)); \ 1029 } 1030 1031 BOOST_PP_REPEAT_FROM_TO(4, BOOST_UNORDERED_EMPLACE_LIMIT, 1032 BOOST_UNORDERED_CONSTRUCT_IMPL, _) 1033 1034 #undef BOOST_UNORDERED_CONSTRUCT_IMPL 1035 1036 // Construct with piece_construct 1037 1038 template <typename Alloc, typename A, typename B, 1039 typename A0, typename A1, typename A2> construct_value_impl(Alloc & alloc,std::pair<A,B> * address,boost::unordered::detail::emplace_args3<A0,A1,A2> const & args,typename enable_if<use_piecewise<A0>,void * >::type=0)1040 inline void construct_value_impl(Alloc& alloc, std::pair<A, B>* address, 1041 boost::unordered::detail::emplace_args3<A0, A1, A2> const& args, 1042 typename enable_if<use_piecewise<A0>, void*>::type = 0) 1043 { 1044 boost::unordered::detail::func::construct_from_tuple(alloc, 1045 boost::addressof(address->first), args.a1); 1046 boost::unordered::detail::func::construct_from_tuple(alloc, 1047 boost::addressof(address->second), args.a2); 1048 } 1049 1050 #endif // BOOST_NO_CXX11_VARIADIC_TEMPLATES 1051 1052 }}}} 1053 1054 namespace boost { namespace unordered { namespace detail { 1055 1056 //////////////////////////////////////////////////////////////////////////// 1057 // 1058 // array_constructor 1059 // 1060 // Allocate and construct an array in an exception safe manner, and 1061 // clean up if an exception is thrown before the container takes charge 1062 // of it. 1063 1064 template <typename Allocator> 1065 struct array_constructor 1066 { 1067 typedef boost::unordered::detail::allocator_traits<Allocator> traits; 1068 typedef typename traits::pointer pointer; 1069 1070 Allocator& alloc_; 1071 pointer ptr_; 1072 pointer constructed_; 1073 std::size_t length_; 1074 array_constructorboost::unordered::detail::array_constructor1075 array_constructor(Allocator& a) 1076 : alloc_(a), ptr_(), constructed_(), length_(0) 1077 { 1078 constructed_ = pointer(); 1079 ptr_ = pointer(); 1080 } 1081 ~array_constructorboost::unordered::detail::array_constructor1082 ~array_constructor() { 1083 if (ptr_) { 1084 for(pointer p = ptr_; p != constructed_; ++p) { 1085 boost::unordered::detail::func::destroy( 1086 boost::addressof(*p)); 1087 } 1088 1089 traits::deallocate(alloc_, ptr_, length_); 1090 } 1091 } 1092 1093 template <typename V> constructboost::unordered::detail::array_constructor1094 void construct(V const& v, std::size_t l) 1095 { 1096 BOOST_ASSERT(!ptr_); 1097 length_ = l; 1098 ptr_ = traits::allocate(alloc_, length_); 1099 pointer end = ptr_ + static_cast<std::ptrdiff_t>(length_); 1100 for(constructed_ = ptr_; constructed_ != end; ++constructed_) { 1101 new ((void*) boost::addressof(*constructed_)) V(v); 1102 } 1103 } 1104 getboost::unordered::detail::array_constructor1105 pointer get() const 1106 { 1107 return ptr_; 1108 } 1109 releaseboost::unordered::detail::array_constructor1110 pointer release() 1111 { 1112 pointer p(ptr_); 1113 ptr_ = pointer(); 1114 return p; 1115 } 1116 1117 private: 1118 1119 array_constructor(array_constructor const&); 1120 array_constructor& operator=(array_constructor const&); 1121 }; 1122 }}} 1123 1124 #if defined(BOOST_MSVC) 1125 #pragma warning(pop) 1126 #endif 1127 1128 #endif 1129