1 // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. 2 // Copyright (C) 2005-2016 Daniel James 3 // 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 #ifndef BOOST_UNORDERED_DETAIL_IMPLEMENTATION_HPP 8 #define BOOST_UNORDERED_DETAIL_IMPLEMENTATION_HPP 9 10 #include <boost/config.hpp> 11 #if defined(BOOST_HAS_PRAGMA_ONCE) 12 #pragma once 13 #endif 14 15 #include <boost/assert.hpp> 16 #include <boost/core/no_exceptions_support.hpp> 17 #include <boost/core/pointer_traits.hpp> 18 #include <boost/detail/select_type.hpp> 19 #include <boost/limits.hpp> 20 #include <boost/move/move.hpp> 21 #include <boost/preprocessor/arithmetic/inc.hpp> 22 #include <boost/preprocessor/cat.hpp> 23 #include <boost/preprocessor/repetition/enum.hpp> 24 #include <boost/preprocessor/repetition/enum_binary_params.hpp> 25 #include <boost/preprocessor/repetition/enum_params.hpp> 26 #include <boost/preprocessor/repetition/repeat_from_to.hpp> 27 #include <boost/preprocessor/seq/enum.hpp> 28 #include <boost/preprocessor/seq/size.hpp> 29 #include <boost/swap.hpp> 30 #include <boost/throw_exception.hpp> 31 #include <boost/tuple/tuple.hpp> 32 #include <boost/type_traits/add_lvalue_reference.hpp> 33 #include <boost/type_traits/aligned_storage.hpp> 34 #include <boost/type_traits/alignment_of.hpp> 35 #include <boost/type_traits/integral_constant.hpp> 36 #include <boost/type_traits/is_base_of.hpp> 37 #include <boost/type_traits/is_class.hpp> 38 #include <boost/type_traits/is_empty.hpp> 39 #include <boost/type_traits/is_nothrow_move_assignable.hpp> 40 #include <boost/type_traits/is_nothrow_move_constructible.hpp> 41 #include <boost/type_traits/is_nothrow_swappable.hpp> 42 #include <boost/type_traits/is_same.hpp> 43 #include <boost/type_traits/remove_const.hpp> 44 #include <boost/unordered/detail/fwd.hpp> 45 #include <boost/utility/addressof.hpp> 46 #include <boost/utility/enable_if.hpp> 47 #include <cmath> 48 #include <iterator> 49 #include <stdexcept> 50 #include <utility> 51 52 #if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS) 53 #include <type_traits> 54 #endif 55 56 //////////////////////////////////////////////////////////////////////////////// 57 // Configuration 58 // 59 // Unless documented elsewhere these configuration macros should be considered 60 // an implementation detail, I'll try not to break them, but you never know. 61 62 // Use Sun C++ workarounds 63 // I'm not sure which versions of the compiler require these workarounds, so 64 // I'm just using them of everything older than the current test compilers 65 // (as of May 2017). 66 67 #if !defined(BOOST_UNORDERED_SUN_WORKAROUNDS1) 68 #if BOOST_COMP_SUNPRO && BOOST_COMP_SUNPRO < BOOST_VERSION_NUMBER(5, 20, 0) 69 #define BOOST_UNORDERED_SUN_WORKAROUNDS1 1 70 #else 71 #define BOOST_UNORDERED_SUN_WORKAROUNDS1 0 72 #endif 73 #endif 74 75 // BOOST_UNORDERED_EMPLACE_LIMIT = The maximum number of parameters in 76 // emplace (not including things like hints). Don't set it to a lower value, as 77 // that might break something. 78 79 #if !defined BOOST_UNORDERED_EMPLACE_LIMIT 80 #define BOOST_UNORDERED_EMPLACE_LIMIT 10 81 #endif 82 83 // BOOST_UNORDERED_USE_ALLOCATOR_TRAITS - Pick which version of 84 // allocator_traits to use. 85 // 86 // 0 = Own partial implementation 87 // 1 = std::allocator_traits 88 // 2 = boost::container::allocator_traits 89 90 #if !defined(BOOST_UNORDERED_USE_ALLOCATOR_TRAITS) 91 #if !defined(BOOST_NO_CXX11_ALLOCATOR) 92 #define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 1 93 #elif defined(BOOST_MSVC) 94 #if BOOST_MSVC < 1400 95 // Use container's allocator_traits for older versions of Visual 96 // C++ as I don't test with them. 97 #define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 2 98 #endif 99 #endif 100 #endif 101 102 #if !defined(BOOST_UNORDERED_USE_ALLOCATOR_TRAITS) 103 #define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 0 104 #endif 105 106 // BOOST_UNORDERED_TUPLE_ARGS 107 // 108 // Maximum number of std::tuple members to support, or 0 if std::tuple 109 // isn't avaiable. More are supported when full C++11 is used. 110 111 // Already defined, so do nothing 112 #if defined(BOOST_UNORDERED_TUPLE_ARGS) 113 114 // Assume if we have C++11 tuple it's properly variadic, 115 // and just use a max number of 10 arguments. 116 #elif !defined(BOOST_NO_CXX11_HDR_TUPLE) 117 #define BOOST_UNORDERED_TUPLE_ARGS 10 118 119 // Visual C++ has a decent enough tuple for piecewise construction, 120 // so use that if available, using _VARIADIC_MAX for the maximum 121 // number of parameters. Note that this comes after the check 122 // for a full C++11 tuple. 123 #elif defined(BOOST_MSVC) 124 #if !BOOST_UNORDERED_HAVE_PIECEWISE_CONSTRUCT 125 #define BOOST_UNORDERED_TUPLE_ARGS 0 126 #elif defined(_VARIADIC_MAX) 127 #define BOOST_UNORDERED_TUPLE_ARGS _VARIADIC_MAX 128 #else 129 #define BOOST_UNORDERED_TUPLE_ARGS 5 130 #endif 131 132 // Assume that we don't have std::tuple 133 #else 134 #define BOOST_UNORDERED_TUPLE_ARGS 0 135 #endif 136 137 #if BOOST_UNORDERED_TUPLE_ARGS 138 #include <tuple> 139 #endif 140 141 // BOOST_UNORDERED_CXX11_CONSTRUCTION 142 // 143 // Use C++11 construction, requires variadic arguments, good construct support 144 // in allocator_traits and piecewise construction of std::pair 145 // Otherwise allocators aren't used for construction/destruction 146 147 #if BOOST_UNORDERED_HAVE_PIECEWISE_CONSTRUCT && \ 148 !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) && BOOST_UNORDERED_TUPLE_ARGS 149 #if BOOST_COMP_SUNPRO && BOOST_LIB_STD_GNU 150 // Sun C++ std::pair piecewise construction doesn't seem to be exception safe. 151 // (At least for Sun C++ 12.5 using libstdc++). 152 #define BOOST_UNORDERED_CXX11_CONSTRUCTION 0 153 #elif BOOST_COMP_GNUC && BOOST_COMP_GNUC < BOOST_VERSION_NUMBER(4, 7, 0) 154 // Piecewise construction in GCC 4.6 doesn't work for uncopyable types. 155 #define BOOST_UNORDERED_CXX11_CONSTRUCTION 0 156 #elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 0 && \ 157 !defined(BOOST_NO_SFINAE_EXPR) 158 #define BOOST_UNORDERED_CXX11_CONSTRUCTION 1 159 #elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 1 160 #define BOOST_UNORDERED_CXX11_CONSTRUCTION 1 161 #endif 162 #endif 163 164 #if !defined(BOOST_UNORDERED_CXX11_CONSTRUCTION) 165 #define BOOST_UNORDERED_CXX11_CONSTRUCTION 0 166 #endif 167 168 // BOOST_UNORDERED_SUPPRESS_DEPRECATED 169 // 170 // Define to stop deprecation attributes 171 172 #if defined(BOOST_UNORDERED_SUPPRESS_DEPRECATED) 173 #define BOOST_UNORDERED_DEPRECATED(msg) 174 #endif 175 176 // BOOST_UNORDERED_DEPRECATED 177 // 178 // Wrapper around various depreaction attributes. 179 180 #if defined(__has_cpp_attribute) && \ 181 (!defined(__cplusplus) || __cplusplus >= 201402) 182 #if __has_cpp_attribute(deprecated) && !defined(BOOST_UNORDERED_DEPRECATED) 183 #define BOOST_UNORDERED_DEPRECATED(msg) [[deprecated(msg)]] 184 #endif 185 #endif 186 187 #if !defined(BOOST_UNORDERED_DEPRECATED) 188 #if defined(__GNUC__) && __GNUC__ >= 4 189 #define BOOST_UNORDERED_DEPRECATED(msg) __attribute__((deprecated)) 190 #elif defined(_MSC_VER) && _MSC_VER >= 1400 191 #define BOOST_UNORDERED_DEPRECATED(msg) __declspec(deprecated(msg)) 192 #elif defined(_MSC_VER) && _MSC_VER >= 1310 193 #define BOOST_UNORDERED_DEPRECATED(msg) __declspec(deprecated) 194 #else 195 #define BOOST_UNORDERED_DEPRECATED(msg) 196 #endif 197 #endif 198 199 // BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES 200 201 #if !defined(BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES) 202 #if BOOST_COMP_CLANG && __cplusplus >= 201703 203 #define BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES 1 204 #endif 205 #endif 206 207 #if !defined(BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES) 208 #define BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES 0 209 #endif 210 211 namespace boost { 212 namespace unordered { 213 namespace iterator_detail { 214 template <typename Node> struct iterator; 215 template <typename Node> struct c_iterator; 216 template <typename Node> struct l_iterator; 217 template <typename Node> struct cl_iterator; 218 } 219 } 220 } 221 222 namespace boost { 223 namespace unordered { 224 namespace detail { 225 226 template <typename Types> struct table; 227 template <typename NodePointer> struct bucket; 228 struct ptr_bucket; 229 230 template <typename A, typename T> struct node; 231 template <typename T> struct ptr_node; 232 233 static const float minimum_max_load_factor = 1e-3f; 234 static const std::size_t default_bucket_count = 11; 235 236 struct move_tag 237 { 238 }; 239 240 struct empty_emplace 241 { 242 }; 243 244 struct no_key 245 { no_keyboost::unordered::detail::no_key246 no_key() {} no_keyboost::unordered::detail::no_key247 template <class T> no_key(T const&) {} 248 }; 249 250 namespace func { ignore_unused_variable_warning(T const &)251 template <class T> inline void ignore_unused_variable_warning(T const&) 252 { 253 } 254 } 255 256 ////////////////////////////////////////////////////////////////////////// 257 // iterator SFINAE 258 259 template <typename I> 260 struct is_forward : boost::is_base_of<std::forward_iterator_tag, 261 typename std::iterator_traits<I>::iterator_category> 262 { 263 }; 264 265 template <typename I, typename ReturnType> 266 struct enable_if_forward 267 : boost::enable_if_c<boost::unordered::detail::is_forward<I>::value, 268 ReturnType> 269 { 270 }; 271 272 template <typename I, typename ReturnType> 273 struct disable_if_forward 274 : boost::disable_if_c<boost::unordered::detail::is_forward<I>::value, 275 ReturnType> 276 { 277 }; 278 } 279 } 280 } 281 282 //////////////////////////////////////////////////////////////////////////////// 283 // primes 284 285 // clang-format off 286 #define BOOST_UNORDERED_PRIMES \ 287 (17ul)(29ul)(37ul)(53ul)(67ul)(79ul) \ 288 (97ul)(131ul)(193ul)(257ul)(389ul)(521ul)(769ul) \ 289 (1031ul)(1543ul)(2053ul)(3079ul)(6151ul)(12289ul)(24593ul) \ 290 (49157ul)(98317ul)(196613ul)(393241ul)(786433ul) \ 291 (1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul) \ 292 (50331653ul)(100663319ul)(201326611ul)(402653189ul)(805306457ul) \ 293 (1610612741ul)(3221225473ul)(4294967291ul) 294 // clang-format on 295 296 namespace boost { 297 namespace unordered { 298 namespace detail { 299 template <class T> struct prime_list_template 300 { 301 static std::size_t const value[]; 302 303 #if !BOOST_UNORDERED_SUN_WORKAROUNDS1 304 static std::ptrdiff_t const length; 305 #else 306 static std::ptrdiff_t const length = 307 BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES); 308 #endif 309 }; 310 311 template <class T> 312 std::size_t const prime_list_template<T>::value[] = { 313 BOOST_PP_SEQ_ENUM(BOOST_UNORDERED_PRIMES)}; 314 315 #if !BOOST_UNORDERED_SUN_WORKAROUNDS1 316 template <class T> 317 std::ptrdiff_t const prime_list_template<T>::length = BOOST_PP_SEQ_SIZE( 318 BOOST_UNORDERED_PRIMES); 319 #endif 320 321 #undef BOOST_UNORDERED_PRIMES 322 323 typedef prime_list_template<std::size_t> prime_list; 324 325 // no throw next_prime(std::size_t num)326 inline std::size_t next_prime(std::size_t num) 327 { 328 std::size_t const* const prime_list_begin = prime_list::value; 329 std::size_t const* const prime_list_end = 330 prime_list_begin + prime_list::length; 331 std::size_t const* bound = 332 std::lower_bound(prime_list_begin, prime_list_end, num); 333 if (bound == prime_list_end) 334 bound--; 335 return *bound; 336 } 337 338 // no throw prev_prime(std::size_t num)339 inline std::size_t prev_prime(std::size_t num) 340 { 341 std::size_t const* const prime_list_begin = prime_list::value; 342 std::size_t const* const prime_list_end = 343 prime_list_begin + prime_list::length; 344 std::size_t const* bound = 345 std::upper_bound(prime_list_begin, prime_list_end, num); 346 if (bound != prime_list_begin) 347 bound--; 348 return *bound; 349 } 350 351 ////////////////////////////////////////////////////////////////////////// 352 // insert_size/initial_size 353 354 template <class I> insert_size(I i,I j,typename boost::unordered::detail::enable_if_forward<I,void * >::type=0)355 inline std::size_t insert_size(I i, I j, 356 typename boost::unordered::detail::enable_if_forward<I, void*>::type = 357 0) 358 { 359 return static_cast<std::size_t>(std::distance(i, j)); 360 } 361 362 template <class I> insert_size(I,I,typename boost::unordered::detail::disable_if_forward<I,void * >::type=0)363 inline std::size_t insert_size(I, I, 364 typename boost::unordered::detail::disable_if_forward<I, void*>::type = 365 0) 366 { 367 return 1; 368 } 369 370 template <class I> initial_size(I i,I j,std::size_t num_buckets=boost::unordered::detail::default_bucket_count)371 inline std::size_t initial_size(I i, I j, 372 std::size_t num_buckets = 373 boost::unordered::detail::default_bucket_count) 374 { 375 return (std::max)( 376 boost::unordered::detail::insert_size(i, j), num_buckets); 377 } 378 379 ////////////////////////////////////////////////////////////////////////// 380 // compressed 381 382 template <typename T, int Index> struct compressed_base : private T 383 { compressed_baseboost::unordered::detail::compressed_base384 compressed_base(T const& x) : T(x) {} compressed_baseboost::unordered::detail::compressed_base385 compressed_base(T& x, move_tag) : T(boost::move(x)) {} 386 getboost::unordered::detail::compressed_base387 T& get() { return *this; } getboost::unordered::detail::compressed_base388 T const& get() const { return *this; } 389 }; 390 391 template <typename T, int Index> struct uncompressed_base 392 { uncompressed_baseboost::unordered::detail::uncompressed_base393 uncompressed_base(T const& x) : value_(x) {} uncompressed_baseboost::unordered::detail::uncompressed_base394 uncompressed_base(T& x, move_tag) : value_(boost::move(x)) {} 395 getboost::unordered::detail::uncompressed_base396 T& get() { return value_; } getboost::unordered::detail::uncompressed_base397 T const& get() const { return value_; } 398 399 private: 400 T value_; 401 }; 402 403 template <typename T, int Index> 404 struct generate_base 405 : boost::detail::if_true< 406 boost::is_empty<T>::value>::BOOST_NESTED_TEMPLATE 407 then<boost::unordered::detail::compressed_base<T, Index>, 408 boost::unordered::detail::uncompressed_base<T, Index> > 409 { 410 }; 411 412 template <typename T1, typename T2> 413 struct compressed 414 : private boost::unordered::detail::generate_base<T1, 1>::type, 415 private boost::unordered::detail::generate_base<T2, 2>::type 416 { 417 typedef typename generate_base<T1, 1>::type base1; 418 typedef typename generate_base<T2, 2>::type base2; 419 420 typedef T1 first_type; 421 typedef T2 second_type; 422 firstboost::unordered::detail::compressed423 first_type& first() { return static_cast<base1*>(this)->get(); } 424 firstboost::unordered::detail::compressed425 first_type const& first() const 426 { 427 return static_cast<base1 const*>(this)->get(); 428 } 429 secondboost::unordered::detail::compressed430 second_type& second() { return static_cast<base2*>(this)->get(); } 431 secondboost::unordered::detail::compressed432 second_type const& second() const 433 { 434 return static_cast<base2 const*>(this)->get(); 435 } 436 437 template <typename First, typename Second> compressedboost::unordered::detail::compressed438 compressed(First const& x1, Second const& x2) : base1(x1), base2(x2) 439 { 440 } 441 compressedboost::unordered::detail::compressed442 compressed(compressed const& x) : base1(x.first()), base2(x.second()) {} 443 compressedboost::unordered::detail::compressed444 compressed(compressed& x, move_tag m) 445 : base1(x.first(), m), base2(x.second(), m) 446 { 447 } 448 assignboost::unordered::detail::compressed449 void assign(compressed const& x) 450 { 451 first() = x.first(); 452 second() = x.second(); 453 } 454 move_assignboost::unordered::detail::compressed455 void move_assign(compressed& x) 456 { 457 first() = boost::move(x.first()); 458 second() = boost::move(x.second()); 459 } 460 swapboost::unordered::detail::compressed461 void swap(compressed& x) 462 { 463 boost::swap(first(), x.first()); 464 boost::swap(second(), x.second()); 465 } 466 467 private: 468 // Prevent assignment just to make use of assign or 469 // move_assign explicit. 470 compressed& operator=(compressed const&); 471 }; 472 473 ////////////////////////////////////////////////////////////////////////// 474 // pair_traits 475 // 476 // Used to get the types from a pair without instantiating it. 477 478 template <typename Pair> struct pair_traits 479 { 480 typedef typename Pair::first_type first_type; 481 typedef typename Pair::second_type second_type; 482 }; 483 484 template <typename T1, typename T2> struct pair_traits<std::pair<T1, T2> > 485 { 486 typedef T1 first_type; 487 typedef T2 second_type; 488 }; 489 490 #if defined(BOOST_MSVC) 491 #pragma warning(push) 492 #pragma warning(disable : 4512) // assignment operator could not be generated. 493 #pragma warning(disable : 4345) // behavior change: an object of POD type 494 // constructed with an initializer of the form () 495 // will be default-initialized. 496 #endif 497 498 ////////////////////////////////////////////////////////////////////////// 499 // Bits and pieces for implementing traits 500 501 template <typename T> 502 typename boost::add_lvalue_reference<T>::type make(); 503 struct choice9 504 { 505 typedef char (&type)[9]; 506 }; 507 struct choice8 : choice9 508 { 509 typedef char (&type)[8]; 510 }; 511 struct choice7 : choice8 512 { 513 typedef char (&type)[7]; 514 }; 515 struct choice6 : choice7 516 { 517 typedef char (&type)[6]; 518 }; 519 struct choice5 : choice6 520 { 521 typedef char (&type)[5]; 522 }; 523 struct choice4 : choice5 524 { 525 typedef char (&type)[4]; 526 }; 527 struct choice3 : choice4 528 { 529 typedef char (&type)[3]; 530 }; 531 struct choice2 : choice3 532 { 533 typedef char (&type)[2]; 534 }; 535 struct choice1 : choice2 536 { 537 typedef char (&type)[1]; 538 }; 539 choice1 choose(); 540 541 typedef choice1::type yes_type; 542 typedef choice2::type no_type; 543 544 struct private_type 545 { 546 private_type const& operator,(int) const; 547 }; 548 549 template <typename T> no_type is_private_type(T const&); 550 yes_type is_private_type(private_type const&); 551 552 struct convert_from_anything 553 { 554 template <typename T> convert_from_anything(T const&); 555 }; 556 } 557 } 558 } 559 560 //////////////////////////////////////////////////////////////////////////// 561 // emplace_args 562 // 563 // Either forwarding variadic arguments, or storing the arguments in 564 // emplace_args##n 565 566 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 567 568 #define BOOST_UNORDERED_EMPLACE_TEMPLATE typename... Args 569 #define BOOST_UNORDERED_EMPLACE_ARGS BOOST_FWD_REF(Args)... args 570 #define BOOST_UNORDERED_EMPLACE_FORWARD boost::forward<Args>(args)... 571 572 #else 573 574 #define BOOST_UNORDERED_EMPLACE_TEMPLATE typename Args 575 #define BOOST_UNORDERED_EMPLACE_ARGS Args const& args 576 #define BOOST_UNORDERED_EMPLACE_FORWARD args 577 578 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 579 580 #define BOOST_UNORDERED_EARGS_MEMBER(z, n, _) \ 581 typedef BOOST_FWD_REF(BOOST_PP_CAT(A, n)) BOOST_PP_CAT(Arg, n); \ 582 BOOST_PP_CAT(Arg, n) BOOST_PP_CAT(a, n); 583 584 #else 585 586 #define BOOST_UNORDERED_EARGS_MEMBER(z, n, _) \ 587 typedef typename boost::add_lvalue_reference<BOOST_PP_CAT(A, n)>::type \ 588 BOOST_PP_CAT(Arg, n); \ 589 BOOST_PP_CAT(Arg, n) BOOST_PP_CAT(a, n); 590 591 #endif 592 593 #define BOOST_UNORDERED_FWD_PARAM(z, n, a) \ 594 BOOST_FWD_REF(BOOST_PP_CAT(A, n)) BOOST_PP_CAT(a, n) 595 596 #define BOOST_UNORDERED_CALL_FORWARD(z, i, a) \ 597 boost::forward<BOOST_PP_CAT(A, i)>(BOOST_PP_CAT(a, i)) 598 599 #define BOOST_UNORDERED_EARGS_INIT(z, n, _) \ 600 BOOST_PP_CAT(a, n)(BOOST_PP_CAT(b, n)) 601 602 #define BOOST_UNORDERED_EARGS(z, n, _) \ 603 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ 604 struct BOOST_PP_CAT(emplace_args, n) \ 605 { \ 606 BOOST_PP_REPEAT_##z(n, BOOST_UNORDERED_EARGS_MEMBER, _) BOOST_PP_CAT( \ 607 emplace_args, n)(BOOST_PP_ENUM_BINARY_PARAMS_Z(z, n, Arg, b)) \ 608 : BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_EARGS_INIT, _) \ 609 { \ 610 } \ 611 }; \ 612 \ 613 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ 614 inline BOOST_PP_CAT(emplace_args, n)<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> \ 615 create_emplace_args(BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, b)) \ 616 { \ 617 BOOST_PP_CAT(emplace_args, n)<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> e( \ 618 BOOST_PP_ENUM_PARAMS_Z(z, n, b)); \ 619 return e; \ 620 } 621 622 namespace boost { 623 namespace unordered { 624 namespace detail { 625 template <typename A0> struct emplace_args1 626 { 627 BOOST_UNORDERED_EARGS_MEMBER(1, 0, _) 628 emplace_args1boost::unordered::detail::emplace_args1629 explicit emplace_args1(Arg0 b0) : a0(b0) {} 630 }; 631 632 template <typename A0> create_emplace_args(BOOST_FWD_REF (A0)b0)633 inline emplace_args1<A0> create_emplace_args(BOOST_FWD_REF(A0) b0) 634 { 635 emplace_args1<A0> e(b0); 636 return e; 637 } 638 639 template <typename A0, typename A1> struct emplace_args2 640 { 641 BOOST_UNORDERED_EARGS_MEMBER(1, 0, _) 642 BOOST_UNORDERED_EARGS_MEMBER(1, 1, _) 643 emplace_args2boost::unordered::detail::emplace_args2644 emplace_args2(Arg0 b0, Arg1 b1) : a0(b0), a1(b1) {} 645 }; 646 647 template <typename A0, typename A1> create_emplace_args(BOOST_FWD_REF (A0)b0,BOOST_FWD_REF (A1)b1)648 inline emplace_args2<A0, A1> create_emplace_args( 649 BOOST_FWD_REF(A0) b0, BOOST_FWD_REF(A1) b1) 650 { 651 emplace_args2<A0, A1> e(b0, b1); 652 return e; 653 } 654 655 template <typename A0, typename A1, typename A2> struct emplace_args3 656 { 657 BOOST_UNORDERED_EARGS_MEMBER(1, 0, _) 658 BOOST_UNORDERED_EARGS_MEMBER(1, 1, _) 659 BOOST_UNORDERED_EARGS_MEMBER(1, 2, _) 660 emplace_args3boost::unordered::detail::emplace_args3661 emplace_args3(Arg0 b0, Arg1 b1, Arg2 b2) : a0(b0), a1(b1), a2(b2) {} 662 }; 663 664 template <typename A0, typename A1, typename A2> create_emplace_args(BOOST_FWD_REF (A0)b0,BOOST_FWD_REF (A1)b1,BOOST_FWD_REF (A2)b2)665 inline emplace_args3<A0, A1, A2> create_emplace_args( 666 BOOST_FWD_REF(A0) b0, BOOST_FWD_REF(A1) b1, BOOST_FWD_REF(A2) b2) 667 { 668 emplace_args3<A0, A1, A2> e(b0, b1, b2); 669 return e; 670 } 671 672 BOOST_UNORDERED_EARGS(1, 4, _) 673 BOOST_UNORDERED_EARGS(1, 5, _) 674 BOOST_UNORDERED_EARGS(1, 6, _) 675 BOOST_UNORDERED_EARGS(1, 7, _) 676 BOOST_UNORDERED_EARGS(1, 8, _) 677 BOOST_UNORDERED_EARGS(1, 9, _) 678 BOOST_PP_REPEAT_FROM_TO(10, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT), 679 BOOST_UNORDERED_EARGS, _) 680 } 681 } 682 } 683 684 #undef BOOST_UNORDERED_DEFINE_EMPLACE_ARGS 685 #undef BOOST_UNORDERED_EARGS_MEMBER 686 #undef BOOST_UNORDERED_EARGS_INIT 687 688 #endif 689 690 //////////////////////////////////////////////////////////////////////////////// 691 // 692 // Some utilities for implementing allocator_traits, but useful elsewhere so 693 // they're always defined. 694 695 namespace boost { 696 namespace unordered { 697 namespace detail { 698 699 //////////////////////////////////////////////////////////////////////////// 700 // Integral_constrant, true_type, false_type 701 // 702 // Uses the standard versions if available. 703 704 #if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS) 705 706 using std::integral_constant; 707 using std::true_type; 708 using std::false_type; 709 710 #else 711 712 template <typename T, T Value> struct integral_constant 713 { 714 enum 715 { 716 value = Value 717 }; 718 }; 719 720 typedef boost::unordered::detail::integral_constant<bool, true> true_type; 721 typedef boost::unordered::detail::integral_constant<bool, false> 722 false_type; 723 724 #endif 725 726 //////////////////////////////////////////////////////////////////////////// 727 // Explicitly call a destructor 728 729 #if defined(BOOST_MSVC) 730 #pragma warning(push) 731 #pragma warning(disable : 4100) // unreferenced formal parameter 732 #endif 733 734 namespace func { destroy(T * x)735 template <class T> inline void destroy(T* x) { x->~T(); } 736 } 737 738 #if defined(BOOST_MSVC) 739 #pragma warning(pop) 740 #endif 741 742 ////////////////////////////////////////////////////////////////////////// 743 // value_base 744 // 745 // Space used to store values. 746 747 template <typename ValueType> struct value_base 748 { 749 typedef ValueType value_type; 750 751 typename boost::aligned_storage<sizeof(value_type), 752 boost::alignment_of<value_type>::value>::type data_; 753 value_baseboost::unordered::detail::value_base754 value_base() : data_() {} 755 addressboost::unordered::detail::value_base756 void* address() { return this; } 757 valueboost::unordered::detail::value_base758 value_type& value() { return *(ValueType*)this; } 759 valueboost::unordered::detail::value_base760 value_type const& value() const { return *(ValueType const*)this; } 761 value_ptrboost::unordered::detail::value_base762 value_type* value_ptr() { return (ValueType*)this; } 763 value_ptrboost::unordered::detail::value_base764 value_type const* value_ptr() const { return (ValueType const*)this; } 765 766 private: 767 value_base& operator=(value_base const&); 768 }; 769 770 ////////////////////////////////////////////////////////////////////////// 771 // optional 772 // TODO: Use std::optional when available. 773 774 template <typename T> class optional 775 { 776 BOOST_MOVABLE_BUT_NOT_COPYABLE(optional) 777 778 boost::unordered::detail::value_base<T> value_; 779 bool has_value_; 780 destroy()781 void destroy() 782 { 783 if (has_value_) { 784 boost::unordered::detail::func::destroy(value_.value_ptr()); 785 has_value_ = false; 786 } 787 } 788 move(optional<T> & x)789 void move(optional<T>& x) 790 { 791 BOOST_ASSERT(!has_value_ && x.has_value_); 792 new (value_.value_ptr()) T(boost::move(x.value_.value())); 793 boost::unordered::detail::func::destroy(x.value_.value_ptr()); 794 has_value_ = true; 795 x.has_value_ = false; 796 } 797 798 public: optional()799 optional() BOOST_NOEXCEPT : has_value_(false) {} 800 optional(BOOST_RV_REF (optional<T>)x)801 optional(BOOST_RV_REF(optional<T>) x) : has_value_(false) 802 { 803 if (x.has_value_) { 804 move(x); 805 } 806 } 807 optional(T const & x)808 explicit optional(T const& x) : has_value_(true) 809 { 810 new (value_.value_ptr()) T(x); 811 } 812 operator =(BOOST_RV_REF (optional<T>)x)813 optional& operator=(BOOST_RV_REF(optional<T>) x) 814 { 815 destroy(); 816 if (x.has_value_) { 817 move(x); 818 } 819 return *this; 820 } 821 ~optional()822 ~optional() { destroy(); } 823 has_value() const824 bool has_value() const { return has_value_; } operator *()825 T& operator*() { return value_.value(); } operator *() const826 T const& operator*() const { return value_.value(); } operator ->()827 T* operator->() { return value_.value_ptr(); } operator ->() const828 T const* operator->() const { return value_.value_ptr(); } 829 operator ==(optional<T> const & x)830 bool operator==(optional<T> const& x) 831 { 832 return has_value_ ? x.has_value_ && value_.value() == x.value_.value() 833 : !x.has_value_; 834 } 835 operator !=(optional<T> const & x)836 bool operator!=(optional<T> const& x) { return !((*this) == x); } 837 swap(optional<T> & x)838 void swap(optional<T>& x) 839 { 840 if (has_value_ != x.has_value_) { 841 if (has_value_) { 842 x.move(*this); 843 } else { 844 move(x); 845 } 846 } else if (has_value_) { 847 boost::swap(value_.value(), x.value_.value()); 848 } 849 } 850 swap(optional<T> & x,optional<T> & y)851 friend void swap(optional<T>& x, optional<T>& y) { x.swap(y); } 852 }; 853 } 854 } 855 } 856 857 //////////////////////////////////////////////////////////////////////////// 858 // Expression test mechanism 859 // 860 // When SFINAE expressions are available, define 861 // BOOST_UNORDERED_HAS_FUNCTION which can check if a function call is 862 // supported by a class, otherwise define BOOST_UNORDERED_HAS_MEMBER which 863 // can detect if a class has the specified member, but not that it has the 864 // correct type, this is good enough for a passable impression of 865 // allocator_traits. 866 867 #if !defined(BOOST_NO_SFINAE_EXPR) 868 869 namespace boost { 870 namespace unordered { 871 namespace detail { 872 template <typename T, long unsigned int> struct expr_test; 873 template <typename T> struct expr_test<T, sizeof(char)> : T 874 { 875 }; 876 } 877 } 878 } 879 880 #define BOOST_UNORDERED_CHECK_EXPRESSION(count, result, expression) \ 881 template <typename U> \ 882 static \ 883 typename boost::unordered::detail::expr_test<BOOST_PP_CAT(choice, result), \ 884 sizeof(for_expr_test(((expression), 0)))>::type \ 885 test(BOOST_PP_CAT(choice, count)) 886 887 #define BOOST_UNORDERED_DEFAULT_EXPRESSION(count, result) \ 888 template <typename U> \ 889 static BOOST_PP_CAT(choice, result)::type test(BOOST_PP_CAT(choice, count)) 890 891 #define BOOST_UNORDERED_HAS_FUNCTION(name, thing, args, _) \ 892 struct BOOST_PP_CAT(has_, name) \ 893 { \ 894 template <typename U> static char for_expr_test(U const&); \ 895 BOOST_UNORDERED_CHECK_EXPRESSION( \ 896 1, 1, boost::unordered::detail::make<thing>().name args); \ 897 BOOST_UNORDERED_DEFAULT_EXPRESSION(2, 2); \ 898 \ 899 enum \ 900 { \ 901 value = sizeof(test<T>(choose())) == sizeof(choice1::type) \ 902 }; \ 903 } 904 905 #else 906 907 namespace boost { 908 namespace unordered { 909 namespace detail { 910 template <typename T> struct identity 911 { 912 typedef T type; 913 }; 914 } 915 } 916 } 917 918 #define BOOST_UNORDERED_CHECK_MEMBER(count, result, name, member) \ 919 \ 920 typedef \ 921 typename boost::unordered::detail::identity<member>::type BOOST_PP_CAT( \ 922 check, count); \ 923 \ 924 template <BOOST_PP_CAT(check, count) e> struct BOOST_PP_CAT(test, count) \ 925 { \ 926 typedef BOOST_PP_CAT(choice, result) type; \ 927 }; \ 928 \ 929 template <class U> \ 930 static typename BOOST_PP_CAT(test, count)<&U::name>::type test( \ 931 BOOST_PP_CAT(choice, count)) 932 933 #define BOOST_UNORDERED_DEFAULT_MEMBER(count, result) \ 934 template <class U> \ 935 static BOOST_PP_CAT(choice, result)::type test(BOOST_PP_CAT(choice, count)) 936 937 #define BOOST_UNORDERED_HAS_MEMBER(name) \ 938 struct BOOST_PP_CAT(has_, name) \ 939 { \ 940 struct impl \ 941 { \ 942 struct base_mixin \ 943 { \ 944 int name; \ 945 }; \ 946 struct base : public T, public base_mixin \ 947 { \ 948 }; \ 949 \ 950 BOOST_UNORDERED_CHECK_MEMBER(1, 1, name, int base_mixin::*); \ 951 BOOST_UNORDERED_DEFAULT_MEMBER(2, 2); \ 952 \ 953 enum \ 954 { \ 955 value = sizeof(choice2::type) == sizeof(test<base>(choose())) \ 956 }; \ 957 }; \ 958 \ 959 enum \ 960 { \ 961 value = impl::value \ 962 }; \ 963 } 964 965 #endif 966 967 //////////////////////////////////////////////////////////////////////////// 968 // TRAITS TYPE DETECTION MECHANISM 969 // 970 // Used to implement traits that use a type if present, or a 971 // default otherwise. 972 973 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1400 974 975 #define BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(tname) \ 976 template <typename Tp, typename Default> struct default_type_##tname \ 977 { \ 978 \ 979 template <typename X> \ 980 static choice1::type test(choice1, typename X::tname* = 0); \ 981 \ 982 template <typename X> static choice2::type test(choice2, void* = 0); \ 983 \ 984 struct DefaultWrap \ 985 { \ 986 typedef Default tname; \ 987 }; \ 988 \ 989 enum \ 990 { \ 991 value = (1 == sizeof(test<Tp>(choose()))) \ 992 }; \ 993 \ 994 typedef typename boost::detail::if_true<value>::BOOST_NESTED_TEMPLATE \ 995 then<Tp, DefaultWrap>::type::tname type; \ 996 } 997 998 #else 999 1000 namespace boost { 1001 namespace unordered { 1002 namespace detail { 1003 template <typename T, typename T2> struct sfinae : T2 1004 { 1005 }; 1006 } 1007 } 1008 } 1009 1010 #define BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(tname) \ 1011 template <typename Tp, typename Default> struct default_type_##tname \ 1012 { \ 1013 \ 1014 template <typename X> \ 1015 static typename boost::unordered::detail::sfinae<typename X::tname, \ 1016 choice1>::type test(choice1); \ 1017 \ 1018 template <typename X> static choice2::type test(choice2); \ 1019 \ 1020 struct DefaultWrap \ 1021 { \ 1022 typedef Default tname; \ 1023 }; \ 1024 \ 1025 enum \ 1026 { \ 1027 value = (1 == sizeof(test<Tp>(choose()))) \ 1028 }; \ 1029 \ 1030 typedef typename boost::detail::if_true<value>::BOOST_NESTED_TEMPLATE \ 1031 then<Tp, DefaultWrap>::type::tname type; \ 1032 } 1033 1034 #endif 1035 1036 #define BOOST_UNORDERED_DEFAULT_TYPE(T, tname, arg) \ 1037 typename default_type_##tname<T, arg>::type 1038 1039 //////////////////////////////////////////////////////////////////////////////// 1040 // 1041 // Allocator traits 1042 // 1043 // First our implementation, then later light wrappers around the alternatives 1044 1045 #if BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 0 1046 1047 #include <boost/limits.hpp> 1048 #include <boost/pointer_to_other.hpp> 1049 #include <boost/utility/enable_if.hpp> 1050 1051 namespace boost { 1052 namespace unordered { 1053 namespace detail { 1054 1055 template <typename Alloc, typename T> struct rebind_alloc; 1056 1057 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1058 1059 template <template <typename, typename...> class Alloc, typename U, 1060 typename T, typename... Args> 1061 struct rebind_alloc<Alloc<U, Args...>, T> 1062 { 1063 typedef Alloc<T, Args...> type; 1064 }; 1065 1066 #else 1067 1068 template <template <typename> class Alloc, typename U, typename T> 1069 struct rebind_alloc<Alloc<U>, T> 1070 { 1071 typedef Alloc<T> type; 1072 }; 1073 1074 template <template <typename, typename> class Alloc, typename U, 1075 typename T, typename A0> 1076 struct rebind_alloc<Alloc<U, A0>, T> 1077 { 1078 typedef Alloc<T, A0> type; 1079 }; 1080 1081 template <template <typename, typename, typename> class Alloc, typename U, 1082 typename T, typename A0, typename A1> 1083 struct rebind_alloc<Alloc<U, A0, A1>, T> 1084 { 1085 typedef Alloc<T, A0, A1> type; 1086 }; 1087 1088 #endif 1089 1090 template <typename Alloc, typename T> struct rebind_wrap 1091 { 1092 template <typename X> 1093 static choice1::type test( 1094 choice1, typename X::BOOST_NESTED_TEMPLATE rebind<T>::other* = 0); 1095 template <typename X> static choice2::type test(choice2, void* = 0); 1096 1097 enum 1098 { 1099 value = (1 == sizeof(test<Alloc>(choose()))) 1100 }; 1101 1102 struct fallback 1103 { 1104 template <typename U> struct rebind 1105 { 1106 typedef typename rebind_alloc<Alloc, T>::type other; 1107 }; 1108 }; 1109 1110 typedef 1111 typename boost::detail::if_true<value>::BOOST_NESTED_TEMPLATE then< 1112 Alloc, fallback>::type::BOOST_NESTED_TEMPLATE rebind<T>::other type; 1113 }; 1114 } 1115 } 1116 } 1117 1118 namespace boost { 1119 namespace unordered { 1120 namespace detail { 1121 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(pointer); 1122 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(const_pointer); 1123 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(void_pointer); 1124 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(const_void_pointer); 1125 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(difference_type); 1126 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(size_type); 1127 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT( 1128 propagate_on_container_copy_assignment); 1129 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT( 1130 propagate_on_container_move_assignment); 1131 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(propagate_on_container_swap); 1132 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(is_always_equal); 1133 1134 #if !defined(BOOST_NO_SFINAE_EXPR) 1135 1136 template <typename T> 1137 BOOST_UNORDERED_HAS_FUNCTION( 1138 select_on_container_copy_construction, U const, (), 0); 1139 1140 template <typename T> 1141 BOOST_UNORDERED_HAS_FUNCTION(max_size, U const, (), 0); 1142 1143 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1144 1145 template <typename T, typename ValueType, typename... Args> 1146 BOOST_UNORDERED_HAS_FUNCTION(construct, U, 1147 (boost::unordered::detail::make<ValueType*>(), 1148 boost::unordered::detail::make<Args const>()...), 1149 2); 1150 1151 #else 1152 1153 template <typename T, typename ValueType> 1154 BOOST_UNORDERED_HAS_FUNCTION(construct, U, 1155 (boost::unordered::detail::make<ValueType*>(), 1156 boost::unordered::detail::make<ValueType const>()), 1157 2); 1158 1159 #endif 1160 1161 template <typename T, typename ValueType> 1162 BOOST_UNORDERED_HAS_FUNCTION( 1163 destroy, U, (boost::unordered::detail::make<ValueType*>()), 1); 1164 1165 #else 1166 1167 template <typename T> 1168 BOOST_UNORDERED_HAS_MEMBER(select_on_container_copy_construction); 1169 1170 template <typename T> BOOST_UNORDERED_HAS_MEMBER(max_size); 1171 1172 template <typename T, typename ValueType> 1173 BOOST_UNORDERED_HAS_MEMBER(construct); 1174 1175 template <typename T, typename ValueType> 1176 BOOST_UNORDERED_HAS_MEMBER(destroy); 1177 1178 #endif 1179 } 1180 } 1181 } 1182 1183 namespace boost { 1184 namespace unordered { 1185 namespace detail { 1186 namespace func { 1187 1188 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)1189 inline Alloc call_select_on_container_copy_construction( 1190 const Alloc& rhs, 1191 typename boost::enable_if_c< 1192 boost::unordered::detail::has_select_on_container_copy_construction< 1193 Alloc>::value, 1194 void*>::type = 0) 1195 { 1196 return rhs.select_on_container_copy_construction(); 1197 } 1198 1199 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)1200 inline Alloc call_select_on_container_copy_construction( 1201 const Alloc& rhs, 1202 typename boost::disable_if_c< 1203 boost::unordered::detail::has_select_on_container_copy_construction< 1204 Alloc>::value, 1205 void*>::type = 0) 1206 { 1207 return rhs; 1208 } 1209 1210 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)1211 inline SizeType call_max_size(const Alloc& a, 1212 typename boost::enable_if_c< 1213 boost::unordered::detail::has_max_size<Alloc>::value, void*>::type = 1214 0) 1215 { 1216 return a.max_size(); 1217 } 1218 1219 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)1220 inline SizeType call_max_size(const Alloc&, 1221 typename boost::disable_if_c< 1222 boost::unordered::detail::has_max_size<Alloc>::value, void*>::type = 1223 0) 1224 { 1225 return (std::numeric_limits<SizeType>::max)(); 1226 } 1227 } // namespace func. 1228 } 1229 } 1230 } 1231 1232 namespace boost { 1233 namespace unordered { 1234 namespace detail { 1235 template <typename Alloc> struct allocator_traits 1236 { 1237 typedef Alloc allocator_type; 1238 typedef typename Alloc::value_type value_type; 1239 1240 typedef BOOST_UNORDERED_DEFAULT_TYPE( 1241 Alloc, pointer, value_type*) pointer; 1242 1243 template <typename T> 1244 struct pointer_to_other : boost::pointer_to_other<pointer, T> 1245 { 1246 }; 1247 1248 typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, const_pointer, 1249 typename pointer_to_other<const value_type>::type) const_pointer; 1250 1251 // typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, void_pointer, 1252 // typename pointer_to_other<void>::type) 1253 // void_pointer; 1254 // 1255 // typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, const_void_pointer, 1256 // typename pointer_to_other<const void>::type) 1257 // const_void_pointer; 1258 1259 typedef BOOST_UNORDERED_DEFAULT_TYPE( 1260 Alloc, difference_type, std::ptrdiff_t) difference_type; 1261 1262 typedef BOOST_UNORDERED_DEFAULT_TYPE( 1263 Alloc, size_type, std::size_t) size_type; 1264 1265 #if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) 1266 template <typename T> 1267 using rebind_alloc = typename rebind_wrap<Alloc, T>::type; 1268 1269 template <typename T> 1270 using rebind_traits = 1271 boost::unordered::detail::allocator_traits<rebind_alloc<T> >; 1272 #endif 1273 allocateboost::unordered::detail::allocator_traits1274 static pointer allocate(Alloc& a, size_type n) { return a.allocate(n); } 1275 1276 // I never use this, so I'll just comment it out for now. 1277 // 1278 // static pointer allocate(Alloc& a, size_type n, 1279 // const_void_pointer hint) 1280 // { return DEFAULT_FUNC(allocate, pointer)(a, n, hint); } 1281 deallocateboost::unordered::detail::allocator_traits1282 static void deallocate(Alloc& a, pointer p, size_type n) 1283 { 1284 a.deallocate(p, n); 1285 } 1286 1287 public: 1288 #if BOOST_UNORDERED_CXX11_CONSTRUCTION 1289 1290 template <typename T, typename... Args> 1291 static 1292 typename boost::enable_if_c<boost::unordered::detail::has_construct< 1293 Alloc, T, Args...>::value>::type constructboost::unordered::detail::allocator_traits1294 construct(Alloc& a, T* p, BOOST_FWD_REF(Args)... x) 1295 { 1296 a.construct(p, boost::forward<Args>(x)...); 1297 } 1298 1299 template <typename T, typename... Args> 1300 static 1301 typename boost::disable_if_c<boost::unordered::detail::has_construct< 1302 Alloc, T, Args...>::value>::type constructboost::unordered::detail::allocator_traits1303 construct(Alloc&, T* p, BOOST_FWD_REF(Args)... x) 1304 { 1305 new (static_cast<void*>(p)) T(boost::forward<Args>(x)...); 1306 } 1307 1308 template <typename T> 1309 static typename boost::enable_if_c< 1310 boost::unordered::detail::has_destroy<Alloc, T>::value>::type destroyboost::unordered::detail::allocator_traits1311 destroy(Alloc& a, T* p) 1312 { 1313 a.destroy(p); 1314 } 1315 1316 template <typename T> 1317 static typename boost::disable_if_c< 1318 boost::unordered::detail::has_destroy<Alloc, T>::value>::type destroyboost::unordered::detail::allocator_traits1319 destroy(Alloc&, T* p) 1320 { 1321 boost::unordered::detail::func::destroy(p); 1322 } 1323 1324 #elif !defined(BOOST_NO_SFINAE_EXPR) 1325 1326 template <typename T> 1327 static typename boost::enable_if_c< 1328 boost::unordered::detail::has_construct<Alloc, T>::value>::type 1329 construct(Alloc& a, T* p, T const& x) 1330 { 1331 a.construct(p, x); 1332 } 1333 1334 template <typename T> 1335 static typename boost::disable_if_c< 1336 boost::unordered::detail::has_construct<Alloc, T>::value>::type 1337 construct(Alloc&, T* p, T const& x) 1338 { 1339 new (static_cast<void*>(p)) T(x); 1340 } 1341 1342 template <typename T> 1343 static typename boost::enable_if_c< 1344 boost::unordered::detail::has_destroy<Alloc, T>::value>::type 1345 destroy(Alloc& a, T* p) 1346 { 1347 a.destroy(p); 1348 } 1349 1350 template <typename T> 1351 static typename boost::disable_if_c< 1352 boost::unordered::detail::has_destroy<Alloc, T>::value>::type 1353 destroy(Alloc&, T* p) 1354 { 1355 boost::unordered::detail::func::destroy(p); 1356 } 1357 1358 #else 1359 1360 // If we don't have SFINAE expressions, only call construct for the 1361 // copy constructor for the allocator's value_type - as that's 1362 // the only construct method that old fashioned allocators support. 1363 1364 template <typename T> 1365 static void construct(Alloc& a, T* p, T const& x, 1366 typename boost::enable_if_c< 1367 boost::unordered::detail::has_construct<Alloc, T>::value && 1368 boost::is_same<T, value_type>::value, 1369 void*>::type = 0) 1370 { 1371 a.construct(p, x); 1372 } 1373 1374 template <typename T> 1375 static void construct(Alloc&, T* p, T const& x, 1376 typename boost::disable_if_c< 1377 boost::unordered::detail::has_construct<Alloc, T>::value && 1378 boost::is_same<T, value_type>::value, 1379 void*>::type = 0) 1380 { 1381 new (static_cast<void*>(p)) T(x); 1382 } 1383 1384 template <typename T> 1385 static void destroy(Alloc& a, T* p, 1386 typename boost::enable_if_c< 1387 boost::unordered::detail::has_destroy<Alloc, T>::value && 1388 boost::is_same<T, value_type>::value, 1389 void*>::type = 0) 1390 { 1391 a.destroy(p); 1392 } 1393 1394 template <typename T> 1395 static void destroy(Alloc&, T* p, 1396 typename boost::disable_if_c< 1397 boost::unordered::detail::has_destroy<Alloc, T>::value && 1398 boost::is_same<T, value_type>::value, 1399 void*>::type = 0) 1400 { 1401 boost::unordered::detail::func::destroy(p); 1402 } 1403 1404 #endif 1405 max_sizeboost::unordered::detail::allocator_traits1406 static size_type max_size(const Alloc& a) 1407 { 1408 return boost::unordered::detail::func::call_max_size<size_type>(a); 1409 } 1410 1411 // Allocator propagation on construction 1412 select_on_container_copy_constructionboost::unordered::detail::allocator_traits1413 static Alloc select_on_container_copy_construction(Alloc const& rhs) 1414 { 1415 return boost::unordered::detail::func:: 1416 call_select_on_container_copy_construction(rhs); 1417 } 1418 1419 // Allocator propagation on assignment and swap. 1420 // Return true if lhs is modified. 1421 typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, 1422 propagate_on_container_copy_assignment, 1423 false_type) propagate_on_container_copy_assignment; 1424 typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, 1425 propagate_on_container_move_assignment, 1426 false_type) propagate_on_container_move_assignment; 1427 typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, propagate_on_container_swap, 1428 false_type) propagate_on_container_swap; 1429 1430 typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, is_always_equal, 1431 typename boost::is_empty<Alloc>::type) is_always_equal; 1432 }; 1433 } 1434 } 1435 } 1436 1437 #undef BOOST_UNORDERED_DEFAULT_TYPE_TMPLT 1438 #undef BOOST_UNORDERED_DEFAULT_TYPE 1439 1440 //////////////////////////////////////////////////////////////////////////////// 1441 // 1442 // std::allocator_traits 1443 1444 #elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 1 1445 1446 #include <memory> 1447 1448 namespace boost { 1449 namespace unordered { 1450 namespace detail { 1451 1452 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(is_always_equal); 1453 1454 template <typename Alloc> 1455 struct allocator_traits : std::allocator_traits<Alloc> 1456 { 1457 // As is_always_equal was introduced in C++17, std::allocator_traits 1458 // doesn't always have it. So use it when available, implement it 1459 // ourselves when not. Would be simpler not to bother with 1460 // std::allocator_traits, but I feel like I should try to use 1461 // it where possible. 1462 typedef BOOST_UNORDERED_DEFAULT_TYPE(std::allocator_traits<Alloc>, 1463 is_always_equal, 1464 BOOST_UNORDERED_DEFAULT_TYPE(Alloc, is_always_equal, 1465 typename boost::is_empty<Alloc>::type)) is_always_equal; 1466 }; 1467 1468 template <typename Alloc, typename T> struct rebind_wrap 1469 { 1470 typedef typename std::allocator_traits<Alloc>::template rebind_alloc<T> 1471 type; 1472 }; 1473 } 1474 } 1475 } 1476 1477 //////////////////////////////////////////////////////////////////////////////// 1478 // 1479 // boost::container::allocator_traits 1480 1481 #elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 2 1482 1483 #include <boost/container/allocator_traits.hpp> 1484 1485 namespace boost { 1486 namespace unordered { 1487 namespace detail { 1488 1489 template <typename Alloc> 1490 struct allocator_traits : boost::container::allocator_traits<Alloc> 1491 { 1492 }; 1493 1494 template <typename Alloc, typename T> 1495 struct rebind_wrap : boost::container::allocator_traits< 1496 Alloc>::template portable_rebind_alloc<T> 1497 { 1498 }; 1499 } 1500 } 1501 } 1502 1503 #else 1504 1505 #error "Invalid BOOST_UNORDERED_USE_ALLOCATOR_TRAITS value." 1506 1507 #endif 1508 1509 //////////////////////////////////////////////////////////////////////////// 1510 // Functions used to construct nodes. Emulates variadic construction, 1511 // piecewise construction etc. 1512 1513 //////////////////////////////////////////////////////////////////////////// 1514 // construct_value 1515 // 1516 // Only use allocator_traits::construct, allocator_traits::destroy when full 1517 // C++11 support is available. 1518 1519 #if BOOST_UNORDERED_CXX11_CONSTRUCTION 1520 1521 #define BOOST_UNORDERED_CALL_CONSTRUCT1(Traits, alloc, address, a0) \ 1522 Traits::construct(alloc, address, a0) 1523 #define BOOST_UNORDERED_CALL_DESTROY(Traits, alloc, x) Traits::destroy(alloc, x) 1524 1525 #elif !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1526 1527 namespace boost { 1528 namespace unordered { 1529 namespace detail { 1530 namespace func { 1531 template <typename T, typename... Args> construct_value(T * address,BOOST_FWD_REF (Args)...args)1532 inline void construct_value(T* address, BOOST_FWD_REF(Args)... args) 1533 { 1534 new ((void*)address) T(boost::forward<Args>(args)...); 1535 } 1536 } 1537 } 1538 } 1539 } 1540 1541 #define BOOST_UNORDERED_CALL_CONSTRUCT1(Traits, alloc, address, a0) \ 1542 boost::unordered::detail::func::construct_value(address, a0) 1543 #define BOOST_UNORDERED_CALL_DESTROY(Traits, alloc, x) \ 1544 boost::unordered::detail::func::destroy(x) 1545 1546 #else 1547 1548 namespace boost { 1549 namespace unordered { 1550 namespace detail { 1551 namespace func { construct_value(T * address)1552 template <typename T> inline void construct_value(T* address) 1553 { 1554 new ((void*)address) T(); 1555 } 1556 1557 template <typename T, typename A0> construct_value(T * address,BOOST_FWD_REF (A0)a0)1558 inline void construct_value(T* address, BOOST_FWD_REF(A0) a0) 1559 { 1560 new ((void*)address) T(boost::forward<A0>(a0)); 1561 } 1562 } 1563 } 1564 } 1565 } 1566 1567 #define BOOST_UNORDERED_CALL_CONSTRUCT1(Traits, alloc, address, a0) \ 1568 boost::unordered::detail::func::construct_value(address, a0) 1569 #define BOOST_UNORDERED_CALL_DESTROY(Traits, alloc, x) \ 1570 boost::unordered::detail::func::destroy(x) 1571 1572 #endif 1573 1574 //////////////////////////////////////////////////////////////////////////// 1575 // Construct from tuple 1576 // 1577 // Used to emulate piecewise construction. 1578 1579 #define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(z, n, namespace_) \ 1580 template <typename Alloc, typename T, \ 1581 BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ 1582 void construct_from_tuple(Alloc&, T* ptr, \ 1583 namespace_::tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \ 1584 { \ 1585 new ((void*)ptr) \ 1586 T(BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_)); \ 1587 } 1588 1589 #define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) namespace_::get<n>(x) 1590 1591 // construct_from_tuple for boost::tuple 1592 // The workaround for old Sun compilers comes later in the file. 1593 1594 #if !BOOST_UNORDERED_SUN_WORKAROUNDS1 1595 1596 namespace boost { 1597 namespace unordered { 1598 namespace detail { 1599 namespace func { 1600 template <typename Alloc, typename T> construct_from_tuple(Alloc &,T * ptr,boost::tuple<>)1601 void construct_from_tuple(Alloc&, T* ptr, boost::tuple<>) 1602 { 1603 new ((void*)ptr) T(); 1604 } 1605 1606 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 1, boost) 1607 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 2, boost) 1608 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 3, boost) 1609 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 4, boost) 1610 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 5, boost) 1611 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 6, boost) 1612 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 7, boost) 1613 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 8, boost) 1614 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 9, boost) 1615 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 10, boost) 1616 } 1617 } 1618 } 1619 } 1620 1621 #endif 1622 1623 // construct_from_tuple for std::tuple 1624 1625 #if !BOOST_UNORDERED_CXX11_CONSTRUCTION && BOOST_UNORDERED_TUPLE_ARGS 1626 1627 namespace boost { 1628 namespace unordered { 1629 namespace detail { 1630 namespace func { 1631 template <typename Alloc, typename T> construct_from_tuple(Alloc &,T * ptr,std::tuple<>)1632 void construct_from_tuple(Alloc&, T* ptr, std::tuple<>) 1633 { 1634 new ((void*)ptr) T(); 1635 } 1636 1637 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 1, std) 1638 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 2, std) 1639 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 3, std) 1640 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 4, std) 1641 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 5, std) 1642 1643 #if BOOST_UNORDERED_TUPLE_ARGS >= 6 1644 BOOST_PP_REPEAT_FROM_TO(6, BOOST_PP_INC(BOOST_UNORDERED_TUPLE_ARGS), 1645 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE, std) 1646 #endif 1647 } 1648 } 1649 } 1650 } 1651 1652 #endif 1653 1654 #undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE 1655 #undef BOOST_UNORDERED_GET_TUPLE_ARG 1656 1657 // construct_from_tuple for boost::tuple on old versions of sunpro. 1658 // 1659 // Old versions of Sun C++ had problems with template overloads of 1660 // boost::tuple, so to fix it I added a distinct type for each length to 1661 // the overloads. That means there's no possible ambiguity between the 1662 // different overloads, so that the compiler doesn't get confused 1663 1664 #if BOOST_UNORDERED_SUN_WORKAROUNDS1 1665 1666 #define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(z, n, namespace_) \ 1667 template <typename Alloc, typename T, \ 1668 BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ 1669 void construct_from_tuple_impl(boost::unordered::detail::func::length<n>, \ 1670 Alloc&, T* ptr, \ 1671 namespace_::tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \ 1672 { \ 1673 new ((void*)ptr) \ 1674 T(BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_)); \ 1675 } 1676 1677 #define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) namespace_::get<n>(x) 1678 1679 namespace boost { 1680 namespace unordered { 1681 namespace detail { 1682 namespace func { 1683 template <int N> struct length 1684 { 1685 }; 1686 1687 template <typename Alloc, typename T> construct_from_tuple_impl(boost::unordered::detail::func::length<0>,Alloc &,T * ptr,boost::tuple<>)1688 void construct_from_tuple_impl( 1689 boost::unordered::detail::func::length<0>, Alloc&, T* ptr, 1690 boost::tuple<>) 1691 { 1692 new ((void*)ptr) T(); 1693 } 1694 1695 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 1, boost) 1696 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 2, boost) 1697 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 3, boost) 1698 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 4, boost) 1699 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 5, boost) 1700 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 6, boost) 1701 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 7, boost) 1702 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 8, boost) 1703 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 9, boost) 1704 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 10, boost) 1705 1706 template <typename Alloc, typename T, typename Tuple> construct_from_tuple(Alloc & alloc,T * ptr,Tuple const & x)1707 void construct_from_tuple(Alloc& alloc, T* ptr, Tuple const& x) 1708 { 1709 construct_from_tuple_impl(boost::unordered::detail::func::length< 1710 boost::tuples::length<Tuple>::value>(), 1711 alloc, ptr, x); 1712 } 1713 } 1714 } 1715 } 1716 } 1717 1718 #undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE 1719 #undef BOOST_UNORDERED_GET_TUPLE_ARG 1720 1721 #endif 1722 1723 namespace boost { 1724 namespace unordered { 1725 namespace detail { 1726 namespace func { 1727 //////////////////////////////////////////////////////////////////////// 1728 // Trait to check for piecewise construction. 1729 1730 template <typename A0> struct use_piecewise 1731 { 1732 static choice1::type test( 1733 choice1, boost::unordered::piecewise_construct_t); 1734 1735 static choice2::type test(choice2, ...); 1736 1737 enum 1738 { 1739 value = sizeof(choice1::type) == 1740 sizeof(test(choose(), boost::unordered::detail::make<A0>())) 1741 }; 1742 }; 1743 1744 #if BOOST_UNORDERED_CXX11_CONSTRUCTION 1745 1746 //////////////////////////////////////////////////////////////////////// 1747 // Construct from variadic parameters 1748 1749 template <typename Alloc, typename T, typename... Args> construct_from_args(Alloc & alloc,T * address,BOOST_FWD_REF (Args)...args)1750 inline void construct_from_args( 1751 Alloc& alloc, T* address, BOOST_FWD_REF(Args)... args) 1752 { 1753 boost::unordered::detail::allocator_traits<Alloc>::construct( 1754 alloc, address, boost::forward<Args>(args)...); 1755 } 1756 1757 // For backwards compatibility, implement a special case for 1758 // piecewise_construct with boost::tuple 1759 1760 template <typename A0> struct detect_boost_tuple 1761 { 1762 template <typename T0, typename T1, typename T2, typename T3, 1763 typename T4, typename T5, typename T6, typename T7, typename T8, 1764 typename T9> 1765 static choice1::type test(choice1, 1766 boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> const&); 1767 1768 static choice2::type test(choice2, ...); 1769 1770 enum 1771 { 1772 value = sizeof(choice1::type) == 1773 sizeof(test(choose(), boost::unordered::detail::make<A0>())) 1774 }; 1775 }; 1776 1777 // Special case for piecewise_construct 1778 1779 template <typename Alloc, typename A, typename B, typename A0, 1780 typename A1, typename A2> 1781 inline typename boost::enable_if_c<use_piecewise<A0>::value && 1782 detect_boost_tuple<A1>::value && 1783 detect_boost_tuple<A2>::value, 1784 void>::type construct_from_args(Alloc & alloc,std::pair<A,B> * address,BOOST_FWD_REF (A0),BOOST_FWD_REF (A1)a1,BOOST_FWD_REF (A2)a2)1785 construct_from_args(Alloc& alloc, std::pair<A, B>* address, 1786 BOOST_FWD_REF(A0), BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2) 1787 { 1788 boost::unordered::detail::func::construct_from_tuple( 1789 alloc, boost::addressof(address->first), boost::forward<A1>(a1)); 1790 BOOST_TRY 1791 { 1792 boost::unordered::detail::func::construct_from_tuple( 1793 alloc, boost::addressof(address->second), boost::forward<A2>(a2)); 1794 } 1795 BOOST_CATCH(...) 1796 { 1797 boost::unordered::detail::func::destroy( 1798 boost::addressof(address->first)); 1799 BOOST_RETHROW 1800 } 1801 BOOST_CATCH_END 1802 } 1803 1804 #elif !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1805 1806 //////////////////////////////////////////////////////////////////////// 1807 // Construct from variadic parameters 1808 1809 template <typename Alloc, typename T, typename... Args> construct_from_args(Alloc &,T * address,BOOST_FWD_REF (Args)...args)1810 inline void construct_from_args( 1811 Alloc&, T* address, BOOST_FWD_REF(Args)... args) 1812 { 1813 new ((void*)address) T(boost::forward<Args>(args)...); 1814 } 1815 1816 // Special case for piecewise_construct 1817 1818 template <typename Alloc, typename A, typename B, typename A0, 1819 typename A1, typename A2> 1820 inline typename enable_if<use_piecewise<A0>, void>::type construct_from_args(Alloc & alloc,std::pair<A,B> * address,BOOST_FWD_REF (A0),BOOST_FWD_REF (A1)a1,BOOST_FWD_REF (A2)a2)1821 construct_from_args(Alloc& alloc, std::pair<A, B>* address, 1822 BOOST_FWD_REF(A0), BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2) 1823 { 1824 boost::unordered::detail::func::construct_from_tuple( 1825 alloc, boost::addressof(address->first), boost::forward<A1>(a1)); 1826 BOOST_TRY 1827 { 1828 boost::unordered::detail::func::construct_from_tuple( 1829 alloc, boost::addressof(address->second), boost::forward<A2>(a2)); 1830 } 1831 BOOST_CATCH(...) 1832 { 1833 boost::unordered::detail::func::destroy( 1834 boost::addressof(address->first)); 1835 BOOST_RETHROW 1836 } 1837 BOOST_CATCH_END 1838 } 1839 1840 #else // BOOST_NO_CXX11_VARIADIC_TEMPLATES 1841 1842 //////////////////////////////////////////////////////////////////////// 1843 // Construct from emplace_args 1844 1845 // Explicitly write out first three overloads for the sake of sane 1846 // error messages. 1847 1848 template <typename Alloc, typename T, typename A0> construct_from_args(Alloc &,T * address,emplace_args1<A0> const & args)1849 inline void construct_from_args( 1850 Alloc&, T* address, emplace_args1<A0> const& args) 1851 { 1852 new ((void*)address) T(boost::forward<A0>(args.a0)); 1853 } 1854 1855 template <typename Alloc, typename T, typename A0, typename A1> construct_from_args(Alloc &,T * address,emplace_args2<A0,A1> const & args)1856 inline void construct_from_args( 1857 Alloc&, T* address, emplace_args2<A0, A1> const& args) 1858 { 1859 new ((void*)address) 1860 T(boost::forward<A0>(args.a0), boost::forward<A1>(args.a1)); 1861 } 1862 1863 template <typename Alloc, typename T, typename A0, typename A1, 1864 typename A2> construct_from_args(Alloc &,T * address,emplace_args3<A0,A1,A2> const & args)1865 inline void construct_from_args( 1866 Alloc&, T* address, emplace_args3<A0, A1, A2> const& args) 1867 { 1868 new ((void*)address) T(boost::forward<A0>(args.a0), 1869 boost::forward<A1>(args.a1), boost::forward<A2>(args.a2)); 1870 } 1871 1872 // Use a macro for the rest. 1873 1874 #define BOOST_UNORDERED_CONSTRUCT_IMPL(z, num_params, _) \ 1875 template <typename Alloc, typename T, \ 1876 BOOST_PP_ENUM_PARAMS_Z(z, num_params, typename A)> \ 1877 inline void construct_from_args(Alloc&, T* address, \ 1878 boost::unordered::detail::BOOST_PP_CAT(emplace_args, num_params) < \ 1879 BOOST_PP_ENUM_PARAMS_Z(z, num_params, A) > const& args) \ 1880 { \ 1881 new ((void*)address) \ 1882 T(BOOST_PP_ENUM_##z(num_params, BOOST_UNORDERED_CALL_FORWARD, args.a)); \ 1883 } 1884 1885 BOOST_UNORDERED_CONSTRUCT_IMPL(1, 4, _) 1886 BOOST_UNORDERED_CONSTRUCT_IMPL(1, 5, _) 1887 BOOST_UNORDERED_CONSTRUCT_IMPL(1, 6, _) 1888 BOOST_UNORDERED_CONSTRUCT_IMPL(1, 7, _) 1889 BOOST_UNORDERED_CONSTRUCT_IMPL(1, 8, _) 1890 BOOST_UNORDERED_CONSTRUCT_IMPL(1, 9, _) BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT)1891 BOOST_PP_REPEAT_FROM_TO(10, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT), 1892 BOOST_UNORDERED_CONSTRUCT_IMPL, _) 1893 1894 #undef BOOST_UNORDERED_CONSTRUCT_IMPL 1895 1896 // Construct with piecewise_construct 1897 1898 template <typename Alloc, typename A, typename B, typename A0, 1899 typename A1, typename A2> 1900 inline void construct_from_args(Alloc& alloc, std::pair<A, B>* address, 1901 boost::unordered::detail::emplace_args3<A0, A1, A2> const& args, 1902 typename enable_if<use_piecewise<A0>, void*>::type = 0) 1903 { 1904 boost::unordered::detail::func::construct_from_tuple( 1905 alloc, boost::addressof(address->first), args.a1); 1906 BOOST_TRY 1907 { 1908 boost::unordered::detail::func::construct_from_tuple( 1909 alloc, boost::addressof(address->second), args.a2); 1910 } 1911 BOOST_CATCH(...) 1912 { 1913 boost::unordered::detail::func::destroy( 1914 boost::addressof(address->first)); 1915 BOOST_RETHROW 1916 } 1917 BOOST_CATCH_END 1918 } 1919 1920 #endif // BOOST_NO_CXX11_VARIADIC_TEMPLATES 1921 } 1922 } 1923 } 1924 } 1925 1926 namespace boost { 1927 namespace unordered { 1928 namespace detail { 1929 1930 /////////////////////////////////////////////////////////////////// 1931 // 1932 // Node construction 1933 1934 template <typename NodeAlloc> struct node_constructor 1935 { 1936 typedef NodeAlloc node_allocator; 1937 typedef boost::unordered::detail::allocator_traits<NodeAlloc> 1938 node_allocator_traits; 1939 typedef typename node_allocator_traits::value_type node; 1940 typedef typename node_allocator_traits::pointer node_pointer; 1941 typedef typename node::value_type value_type; 1942 1943 node_allocator& alloc_; 1944 node_pointer node_; 1945 node_constructorboost::unordered::detail::node_constructor1946 node_constructor(node_allocator& n) : alloc_(n), node_() {} 1947 1948 ~node_constructor(); 1949 1950 void create_node(); 1951 1952 // no throw releaseboost::unordered::detail::node_constructor1953 node_pointer release() 1954 { 1955 BOOST_ASSERT(node_); 1956 node_pointer p = node_; 1957 node_ = node_pointer(); 1958 return p; 1959 } 1960 reclaimboost::unordered::detail::node_constructor1961 void reclaim(node_pointer p) 1962 { 1963 BOOST_ASSERT(!node_); 1964 node_ = p; 1965 BOOST_UNORDERED_CALL_DESTROY( 1966 node_allocator_traits, alloc_, node_->value_ptr()); 1967 } 1968 1969 private: 1970 node_constructor(node_constructor const&); 1971 node_constructor& operator=(node_constructor const&); 1972 }; 1973 ~node_constructor()1974 template <typename Alloc> node_constructor<Alloc>::~node_constructor() 1975 { 1976 if (node_) { 1977 boost::unordered::detail::func::destroy(boost::to_address(node_)); 1978 node_allocator_traits::deallocate(alloc_, node_, 1); 1979 } 1980 } 1981 create_node()1982 template <typename Alloc> void node_constructor<Alloc>::create_node() 1983 { 1984 BOOST_ASSERT(!node_); 1985 node_ = node_allocator_traits::allocate(alloc_, 1); 1986 new ((void*)boost::to_address(node_)) node(); 1987 } 1988 1989 template <typename NodeAlloc> struct node_tmp 1990 { 1991 typedef boost::unordered::detail::allocator_traits<NodeAlloc> 1992 node_allocator_traits; 1993 typedef typename node_allocator_traits::pointer node_pointer; 1994 typedef typename node_allocator_traits::value_type node; 1995 1996 NodeAlloc& alloc_; 1997 node_pointer node_; 1998 node_tmpboost::unordered::detail::node_tmp1999 explicit node_tmp(node_pointer n, NodeAlloc& a) : alloc_(a), node_(n) {} 2000 2001 ~node_tmp(); 2002 2003 // no throw releaseboost::unordered::detail::node_tmp2004 node_pointer release() 2005 { 2006 node_pointer p = node_; 2007 node_ = node_pointer(); 2008 return p; 2009 } 2010 }; 2011 ~node_tmp()2012 template <typename Alloc> node_tmp<Alloc>::~node_tmp() 2013 { 2014 if (node_) { 2015 BOOST_UNORDERED_CALL_DESTROY( 2016 node_allocator_traits, alloc_, node_->value_ptr()); 2017 boost::unordered::detail::func::destroy(boost::to_address(node_)); 2018 node_allocator_traits::deallocate(alloc_, node_, 1); 2019 } 2020 } 2021 } 2022 } 2023 } 2024 2025 namespace boost { 2026 namespace unordered { 2027 namespace detail { 2028 namespace func { 2029 2030 // Some nicer construct_node functions, might try to 2031 // improve implementation later. 2032 2033 template <typename Alloc, BOOST_UNORDERED_EMPLACE_TEMPLATE> 2034 inline 2035 typename boost::unordered::detail::allocator_traits<Alloc>::pointer construct_node_from_args(Alloc & alloc,BOOST_UNORDERED_EMPLACE_ARGS)2036 construct_node_from_args(Alloc& alloc, BOOST_UNORDERED_EMPLACE_ARGS) 2037 { 2038 node_constructor<Alloc> a(alloc); 2039 a.create_node(); 2040 construct_from_args( 2041 alloc, a.node_->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD); 2042 return a.release(); 2043 } 2044 2045 template <typename Alloc, typename U> 2046 inline 2047 typename boost::unordered::detail::allocator_traits<Alloc>::pointer construct_node(Alloc & alloc,BOOST_FWD_REF (U)x)2048 construct_node(Alloc& alloc, BOOST_FWD_REF(U) x) 2049 { 2050 node_constructor<Alloc> a(alloc); 2051 a.create_node(); 2052 BOOST_UNORDERED_CALL_CONSTRUCT1( 2053 boost::unordered::detail::allocator_traits<Alloc>, alloc, 2054 a.node_->value_ptr(), boost::forward<U>(x)); 2055 return a.release(); 2056 } 2057 2058 #if BOOST_UNORDERED_CXX11_CONSTRUCTION 2059 2060 template <typename Alloc, typename Key> 2061 inline 2062 typename boost::unordered::detail::allocator_traits<Alloc>::pointer construct_node_pair(Alloc & alloc,BOOST_FWD_REF (Key)k)2063 construct_node_pair(Alloc& alloc, BOOST_FWD_REF(Key) k) 2064 { 2065 node_constructor<Alloc> a(alloc); 2066 a.create_node(); 2067 boost::unordered::detail::allocator_traits<Alloc>::construct(alloc, 2068 a.node_->value_ptr(), std::piecewise_construct, 2069 std::forward_as_tuple(boost::forward<Key>(k)), 2070 std::forward_as_tuple()); 2071 return a.release(); 2072 } 2073 2074 template <typename Alloc, typename Key, typename Mapped> 2075 inline 2076 typename boost::unordered::detail::allocator_traits<Alloc>::pointer construct_node_pair(Alloc & alloc,BOOST_FWD_REF (Key)k,BOOST_FWD_REF (Mapped)m)2077 construct_node_pair( 2078 Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_FWD_REF(Mapped) m) 2079 { 2080 node_constructor<Alloc> a(alloc); 2081 a.create_node(); 2082 boost::unordered::detail::allocator_traits<Alloc>::construct(alloc, 2083 a.node_->value_ptr(), std::piecewise_construct, 2084 std::forward_as_tuple(boost::forward<Key>(k)), 2085 std::forward_as_tuple(boost::forward<Mapped>(m))); 2086 return a.release(); 2087 } 2088 2089 template <typename Alloc, typename Key, typename... Args> 2090 inline 2091 typename boost::unordered::detail::allocator_traits<Alloc>::pointer construct_node_pair_from_args(Alloc & alloc,BOOST_FWD_REF (Key)k,BOOST_FWD_REF (Args)...args)2092 construct_node_pair_from_args( 2093 Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_FWD_REF(Args)... args) 2094 { 2095 node_constructor<Alloc> a(alloc); 2096 a.create_node(); 2097 #if !(BOOST_COMP_CLANG && BOOST_COMP_CLANG < BOOST_VERSION_NUMBER(3, 8, 0) && \ 2098 defined(BOOST_LIBSTDCXX11)) 2099 boost::unordered::detail::allocator_traits<Alloc>::construct(alloc, 2100 a.node_->value_ptr(), std::piecewise_construct, 2101 std::forward_as_tuple(boost::forward<Key>(k)), 2102 std::forward_as_tuple(boost::forward<Args>(args)...)); 2103 #else 2104 // It doesn't seem to be possible to construct a tuple with 3 variadic 2105 // rvalue reference members when using older versions of clang with 2106 // libstdc++, so just use std::make_tuple instead of 2107 // std::forward_as_tuple. 2108 boost::unordered::detail::allocator_traits<Alloc>::construct(alloc, 2109 a.node_->value_ptr(), std::piecewise_construct, 2110 std::forward_as_tuple(boost::forward<Key>(k)), 2111 std::make_tuple(boost::forward<Args>(args)...)); 2112 #endif 2113 return a.release(); 2114 } 2115 2116 #else 2117 2118 template <typename Alloc, typename Key> 2119 inline 2120 typename boost::unordered::detail::allocator_traits<Alloc>::pointer construct_node_pair(Alloc & alloc,BOOST_FWD_REF (Key)k)2121 construct_node_pair(Alloc& alloc, BOOST_FWD_REF(Key) k) 2122 { 2123 node_constructor<Alloc> a(alloc); 2124 a.create_node(); 2125 boost::unordered::detail::func::construct_value( 2126 boost::addressof(a.node_->value_ptr()->first), 2127 boost::forward<Key>(k)); 2128 BOOST_TRY 2129 { 2130 boost::unordered::detail::func::construct_value( 2131 boost::addressof(a.node_->value_ptr()->second)); 2132 } 2133 BOOST_CATCH(...) 2134 { 2135 boost::unordered::detail::func::destroy( 2136 boost::addressof(a.node_->value_ptr()->first)); 2137 BOOST_RETHROW 2138 } 2139 BOOST_CATCH_END 2140 return a.release(); 2141 } 2142 2143 template <typename Alloc, typename Key, typename Mapped> 2144 inline 2145 typename boost::unordered::detail::allocator_traits<Alloc>::pointer construct_node_pair(Alloc & alloc,BOOST_FWD_REF (Key)k,BOOST_FWD_REF (Mapped)m)2146 construct_node_pair( 2147 Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_FWD_REF(Mapped) m) 2148 { 2149 node_constructor<Alloc> a(alloc); 2150 a.create_node(); 2151 boost::unordered::detail::func::construct_value( 2152 boost::addressof(a.node_->value_ptr()->first), 2153 boost::forward<Key>(k)); 2154 BOOST_TRY 2155 { 2156 boost::unordered::detail::func::construct_value( 2157 boost::addressof(a.node_->value_ptr()->second), 2158 boost::forward<Mapped>(m)); 2159 } 2160 BOOST_CATCH(...) 2161 { 2162 boost::unordered::detail::func::destroy( 2163 boost::addressof(a.node_->value_ptr()->first)); 2164 BOOST_RETHROW 2165 } 2166 BOOST_CATCH_END 2167 return a.release(); 2168 } 2169 2170 template <typename Alloc, typename Key, 2171 BOOST_UNORDERED_EMPLACE_TEMPLATE> 2172 inline 2173 typename boost::unordered::detail::allocator_traits<Alloc>::pointer construct_node_pair_from_args(Alloc & alloc,BOOST_FWD_REF (Key)k,BOOST_UNORDERED_EMPLACE_ARGS)2174 construct_node_pair_from_args( 2175 Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_UNORDERED_EMPLACE_ARGS) 2176 { 2177 node_constructor<Alloc> a(alloc); 2178 a.create_node(); 2179 boost::unordered::detail::func::construct_value( 2180 boost::addressof(a.node_->value_ptr()->first), 2181 boost::forward<Key>(k)); 2182 BOOST_TRY 2183 { 2184 boost::unordered::detail::func::construct_from_args(alloc, 2185 boost::addressof(a.node_->value_ptr()->second), 2186 BOOST_UNORDERED_EMPLACE_FORWARD); 2187 } 2188 BOOST_CATCH(...) 2189 { 2190 boost::unordered::detail::func::destroy( 2191 boost::addressof(a.node_->value_ptr()->first)); 2192 BOOST_RETHROW 2193 } 2194 BOOST_CATCH_END 2195 return a.release(); 2196 } 2197 2198 #endif 2199 } 2200 } 2201 } 2202 } 2203 2204 #if defined(BOOST_MSVC) 2205 #pragma warning(pop) 2206 #endif 2207 2208 // The 'iterator_detail' namespace was a misguided attempt at avoiding ADL 2209 // in the detail namespace. It didn't work because the template parameters 2210 // were in detail. I'm not changing it at the moment to be safe. I might 2211 // do in the future if I change the iterator types. 2212 namespace boost { 2213 namespace unordered { 2214 namespace iterator_detail { 2215 2216 ////////////////////////////////////////////////////////////////////////// 2217 // Iterators 2218 // 2219 // all no throw 2220 2221 template <typename Node> struct l_iterator 2222 { 2223 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) 2224 template <typename Node2> 2225 friend struct boost::unordered::iterator_detail::cl_iterator; 2226 2227 private: 2228 #endif 2229 typedef typename Node::node_pointer node_pointer; 2230 node_pointer ptr_; 2231 std::size_t bucket_; 2232 std::size_t bucket_count_; 2233 2234 public: 2235 typedef typename Node::value_type element_type; 2236 typedef typename Node::value_type value_type; 2237 typedef value_type* pointer; 2238 typedef value_type& reference; 2239 typedef std::ptrdiff_t difference_type; 2240 typedef std::forward_iterator_tag iterator_category; 2241 l_iteratorboost::unordered::iterator_detail::l_iterator2242 l_iterator() BOOST_NOEXCEPT : ptr_() {} 2243 l_iteratorboost::unordered::iterator_detail::l_iterator2244 l_iterator(node_pointer n, std::size_t b, std::size_t c) BOOST_NOEXCEPT 2245 : ptr_(n), 2246 bucket_(b), 2247 bucket_count_(c) 2248 { 2249 } 2250 operator *boost::unordered::iterator_detail::l_iterator2251 value_type& operator*() const { return ptr_->value(); } 2252 operator ->boost::unordered::iterator_detail::l_iterator2253 value_type* operator->() const { return ptr_->value_ptr(); } 2254 operator ++boost::unordered::iterator_detail::l_iterator2255 l_iterator& operator++() 2256 { 2257 ptr_ = static_cast<node_pointer>(ptr_->next_); 2258 if (ptr_ && ptr_->get_bucket() != bucket_) 2259 ptr_ = node_pointer(); 2260 return *this; 2261 } 2262 operator ++boost::unordered::iterator_detail::l_iterator2263 l_iterator operator++(int) 2264 { 2265 l_iterator tmp(*this); 2266 ++(*this); 2267 return tmp; 2268 } 2269 operator ==boost::unordered::iterator_detail::l_iterator2270 bool operator==(l_iterator x) const BOOST_NOEXCEPT 2271 { 2272 return ptr_ == x.ptr_; 2273 } 2274 operator !=boost::unordered::iterator_detail::l_iterator2275 bool operator!=(l_iterator x) const BOOST_NOEXCEPT 2276 { 2277 return ptr_ != x.ptr_; 2278 } 2279 }; 2280 2281 template <typename Node> struct cl_iterator 2282 { 2283 friend struct boost::unordered::iterator_detail::l_iterator<Node>; 2284 2285 private: 2286 typedef typename Node::node_pointer node_pointer; 2287 node_pointer ptr_; 2288 std::size_t bucket_; 2289 std::size_t bucket_count_; 2290 2291 public: 2292 typedef typename Node::value_type const element_type; 2293 typedef typename Node::value_type value_type; 2294 typedef value_type const* pointer; 2295 typedef value_type const& reference; 2296 typedef std::ptrdiff_t difference_type; 2297 typedef std::forward_iterator_tag iterator_category; 2298 cl_iteratorboost::unordered::iterator_detail::cl_iterator2299 cl_iterator() BOOST_NOEXCEPT : ptr_() {} 2300 cl_iteratorboost::unordered::iterator_detail::cl_iterator2301 cl_iterator(node_pointer n, std::size_t b, std::size_t c) BOOST_NOEXCEPT 2302 : ptr_(n), 2303 bucket_(b), 2304 bucket_count_(c) 2305 { 2306 } 2307 cl_iteratorboost::unordered::iterator_detail::cl_iterator2308 cl_iterator( 2309 boost::unordered::iterator_detail::l_iterator<Node> const& x) 2310 BOOST_NOEXCEPT : ptr_(x.ptr_), 2311 bucket_(x.bucket_), 2312 bucket_count_(x.bucket_count_) 2313 { 2314 } 2315 operator *boost::unordered::iterator_detail::cl_iterator2316 value_type const& operator*() const { return ptr_->value(); } 2317 operator ->boost::unordered::iterator_detail::cl_iterator2318 value_type const* operator->() const { return ptr_->value_ptr(); } 2319 operator ++boost::unordered::iterator_detail::cl_iterator2320 cl_iterator& operator++() 2321 { 2322 ptr_ = static_cast<node_pointer>(ptr_->next_); 2323 if (ptr_ && ptr_->get_bucket() != bucket_) 2324 ptr_ = node_pointer(); 2325 return *this; 2326 } 2327 operator ++boost::unordered::iterator_detail::cl_iterator2328 cl_iterator operator++(int) 2329 { 2330 cl_iterator tmp(*this); 2331 ++(*this); 2332 return tmp; 2333 } 2334 operator ==(cl_iterator const & x,cl_iterator const & y)2335 friend bool operator==( 2336 cl_iterator const& x, cl_iterator const& y) BOOST_NOEXCEPT 2337 { 2338 return x.ptr_ == y.ptr_; 2339 } 2340 operator !=(cl_iterator const & x,cl_iterator const & y)2341 friend bool operator!=( 2342 cl_iterator const& x, cl_iterator const& y) BOOST_NOEXCEPT 2343 { 2344 return x.ptr_ != y.ptr_; 2345 } 2346 }; 2347 2348 template <typename Node> struct iterator 2349 { 2350 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) 2351 template <typename> 2352 friend struct boost::unordered::iterator_detail::c_iterator; 2353 template <typename> friend struct boost::unordered::detail::table; 2354 2355 private: 2356 #endif 2357 typedef typename Node::node_pointer node_pointer; 2358 node_pointer node_; 2359 2360 public: 2361 typedef typename Node::value_type element_type; 2362 typedef typename Node::value_type value_type; 2363 typedef value_type* pointer; 2364 typedef value_type& reference; 2365 typedef std::ptrdiff_t difference_type; 2366 typedef std::forward_iterator_tag iterator_category; 2367 iteratorboost::unordered::iterator_detail::iterator2368 iterator() BOOST_NOEXCEPT : node_() {} 2369 iteratorboost::unordered::iterator_detail::iterator2370 explicit iterator(typename Node::link_pointer x) BOOST_NOEXCEPT 2371 : node_(static_cast<node_pointer>(x)) 2372 { 2373 } 2374 operator *boost::unordered::iterator_detail::iterator2375 value_type& operator*() const { return node_->value(); } 2376 operator ->boost::unordered::iterator_detail::iterator2377 value_type* operator->() const { return node_->value_ptr(); } 2378 operator ++boost::unordered::iterator_detail::iterator2379 iterator& operator++() 2380 { 2381 node_ = static_cast<node_pointer>(node_->next_); 2382 return *this; 2383 } 2384 operator ++boost::unordered::iterator_detail::iterator2385 iterator operator++(int) 2386 { 2387 iterator tmp(node_); 2388 node_ = static_cast<node_pointer>(node_->next_); 2389 return tmp; 2390 } 2391 operator ==boost::unordered::iterator_detail::iterator2392 bool operator==(iterator const& x) const BOOST_NOEXCEPT 2393 { 2394 return node_ == x.node_; 2395 } 2396 operator !=boost::unordered::iterator_detail::iterator2397 bool operator!=(iterator const& x) const BOOST_NOEXCEPT 2398 { 2399 return node_ != x.node_; 2400 } 2401 }; 2402 2403 template <typename Node> struct c_iterator 2404 { 2405 friend struct boost::unordered::iterator_detail::iterator<Node>; 2406 2407 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) 2408 template <typename> friend struct boost::unordered::detail::table; 2409 2410 private: 2411 #endif 2412 typedef typename Node::node_pointer node_pointer; 2413 typedef boost::unordered::iterator_detail::iterator<Node> n_iterator; 2414 node_pointer node_; 2415 2416 public: 2417 typedef typename Node::value_type const element_type; 2418 typedef typename Node::value_type value_type; 2419 typedef value_type const* pointer; 2420 typedef value_type const& reference; 2421 typedef std::ptrdiff_t difference_type; 2422 typedef std::forward_iterator_tag iterator_category; 2423 c_iteratorboost::unordered::iterator_detail::c_iterator2424 c_iterator() BOOST_NOEXCEPT : node_() {} 2425 c_iteratorboost::unordered::iterator_detail::c_iterator2426 explicit c_iterator(typename Node::link_pointer x) BOOST_NOEXCEPT 2427 : node_(static_cast<node_pointer>(x)) 2428 { 2429 } 2430 c_iteratorboost::unordered::iterator_detail::c_iterator2431 c_iterator(n_iterator const& x) BOOST_NOEXCEPT : node_(x.node_) {} 2432 operator *boost::unordered::iterator_detail::c_iterator2433 value_type const& operator*() const { return node_->value(); } 2434 operator ->boost::unordered::iterator_detail::c_iterator2435 value_type const* operator->() const { return node_->value_ptr(); } 2436 operator ++boost::unordered::iterator_detail::c_iterator2437 c_iterator& operator++() 2438 { 2439 node_ = static_cast<node_pointer>(node_->next_); 2440 return *this; 2441 } 2442 operator ++boost::unordered::iterator_detail::c_iterator2443 c_iterator operator++(int) 2444 { 2445 c_iterator tmp(node_); 2446 node_ = static_cast<node_pointer>(node_->next_); 2447 return tmp; 2448 } 2449 operator ==(c_iterator const & x,c_iterator const & y)2450 friend bool operator==( 2451 c_iterator const& x, c_iterator const& y) BOOST_NOEXCEPT 2452 { 2453 return x.node_ == y.node_; 2454 } 2455 operator !=(c_iterator const & x,c_iterator const & y)2456 friend bool operator!=( 2457 c_iterator const& x, c_iterator const& y) BOOST_NOEXCEPT 2458 { 2459 return x.node_ != y.node_; 2460 } 2461 }; 2462 } 2463 } 2464 } 2465 2466 namespace boost { 2467 namespace unordered { 2468 namespace detail { 2469 2470 /////////////////////////////////////////////////////////////////// 2471 // 2472 // Node Holder 2473 // 2474 // Temporary store for nodes. Deletes any that aren't used. 2475 2476 template <typename NodeAlloc> struct node_holder 2477 { 2478 private: 2479 typedef NodeAlloc node_allocator; 2480 typedef boost::unordered::detail::allocator_traits<NodeAlloc> 2481 node_allocator_traits; 2482 typedef typename node_allocator_traits::value_type node; 2483 typedef typename node_allocator_traits::pointer node_pointer; 2484 typedef typename node::value_type value_type; 2485 typedef typename node::link_pointer link_pointer; 2486 typedef boost::unordered::iterator_detail::iterator<node> iterator; 2487 2488 node_constructor<NodeAlloc> constructor_; 2489 node_pointer nodes_; 2490 2491 public: 2492 template <typename Table> node_holderboost::unordered::detail::node_holder2493 explicit node_holder(Table& b) : constructor_(b.node_alloc()), nodes_() 2494 { 2495 if (b.size_) { 2496 typename Table::link_pointer prev = b.get_previous_start(); 2497 nodes_ = static_cast<node_pointer>(prev->next_); 2498 prev->next_ = link_pointer(); 2499 b.size_ = 0; 2500 } 2501 } 2502 2503 ~node_holder(); 2504 pop_nodeboost::unordered::detail::node_holder2505 node_pointer pop_node() 2506 { 2507 node_pointer n = nodes_; 2508 nodes_ = static_cast<node_pointer>(nodes_->next_); 2509 n->next_ = link_pointer(); 2510 return n; 2511 } 2512 copy_ofboost::unordered::detail::node_holder2513 template <typename T> inline node_pointer copy_of(T const& v) 2514 { 2515 if (nodes_) { 2516 constructor_.reclaim(pop_node()); 2517 } else { 2518 constructor_.create_node(); 2519 } 2520 BOOST_UNORDERED_CALL_CONSTRUCT1(node_allocator_traits, 2521 constructor_.alloc_, constructor_.node_->value_ptr(), v); 2522 return constructor_.release(); 2523 } 2524 move_copy_ofboost::unordered::detail::node_holder2525 template <typename T> inline node_pointer move_copy_of(T& v) 2526 { 2527 if (nodes_) { 2528 constructor_.reclaim(pop_node()); 2529 } else { 2530 constructor_.create_node(); 2531 } 2532 BOOST_UNORDERED_CALL_CONSTRUCT1(node_allocator_traits, 2533 constructor_.alloc_, constructor_.node_->value_ptr(), 2534 boost::move(v)); 2535 return constructor_.release(); 2536 } 2537 beginboost::unordered::detail::node_holder2538 iterator begin() const { return iterator(nodes_); } 2539 }; 2540 ~node_holder()2541 template <typename Alloc> node_holder<Alloc>::~node_holder() 2542 { 2543 while (nodes_) { 2544 node_pointer p = nodes_; 2545 nodes_ = static_cast<node_pointer>(p->next_); 2546 2547 BOOST_UNORDERED_CALL_DESTROY( 2548 node_allocator_traits, constructor_.alloc_, p->value_ptr()); 2549 boost::unordered::detail::func::destroy(boost::to_address(p)); 2550 node_allocator_traits::deallocate(constructor_.alloc_, p, 1); 2551 } 2552 } 2553 2554 /////////////////////////////////////////////////////////////////// 2555 // 2556 // Bucket 2557 2558 template <typename NodePointer> struct bucket 2559 { 2560 typedef NodePointer link_pointer; 2561 link_pointer next_; 2562 bucketboost::unordered::detail::bucket2563 bucket() : next_() {} bucketboost::unordered::detail::bucket2564 bucket(link_pointer n) : next_(n) {} 2565 first_from_startboost::unordered::detail::bucket2566 link_pointer first_from_start() { return next_; } 2567 2568 enum 2569 { 2570 extra_node = true 2571 }; 2572 }; 2573 2574 struct ptr_bucket 2575 { 2576 typedef ptr_bucket* link_pointer; 2577 link_pointer next_; 2578 ptr_bucketboost::unordered::detail::ptr_bucket2579 ptr_bucket() : next_(0) {} ptr_bucketboost::unordered::detail::ptr_bucket2580 ptr_bucket(link_pointer n) : next_(n) {} 2581 first_from_startboost::unordered::detail::ptr_bucket2582 link_pointer first_from_start() { return this; } 2583 2584 enum 2585 { 2586 extra_node = false 2587 }; 2588 }; 2589 2590 /////////////////////////////////////////////////////////////////// 2591 // 2592 // Hash Policy 2593 2594 template <typename SizeT> struct prime_policy 2595 { 2596 template <typename Hash, typename T> apply_hashboost::unordered::detail::prime_policy2597 static inline SizeT apply_hash(Hash const& hf, T const& x) 2598 { 2599 return hf(x); 2600 } 2601 to_bucketboost::unordered::detail::prime_policy2602 static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) 2603 { 2604 return hash % bucket_count; 2605 } 2606 new_bucket_countboost::unordered::detail::prime_policy2607 static inline SizeT new_bucket_count(SizeT min) 2608 { 2609 return boost::unordered::detail::next_prime(min); 2610 } 2611 prev_bucket_countboost::unordered::detail::prime_policy2612 static inline SizeT prev_bucket_count(SizeT max) 2613 { 2614 return boost::unordered::detail::prev_prime(max); 2615 } 2616 }; 2617 2618 template <typename SizeT> struct mix64_policy 2619 { 2620 template <typename Hash, typename T> apply_hashboost::unordered::detail::mix64_policy2621 static inline SizeT apply_hash(Hash const& hf, T const& x) 2622 { 2623 SizeT key = hf(x); 2624 key = (~key) + (key << 21); // key = (key << 21) - key - 1; 2625 key = key ^ (key >> 24); 2626 key = (key + (key << 3)) + (key << 8); // key * 265 2627 key = key ^ (key >> 14); 2628 key = (key + (key << 2)) + (key << 4); // key * 21 2629 key = key ^ (key >> 28); 2630 key = key + (key << 31); 2631 return key; 2632 } 2633 to_bucketboost::unordered::detail::mix64_policy2634 static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) 2635 { 2636 return hash & (bucket_count - 1); 2637 } 2638 new_bucket_countboost::unordered::detail::mix64_policy2639 static inline SizeT new_bucket_count(SizeT min) 2640 { 2641 if (min <= 4) 2642 return 4; 2643 --min; 2644 min |= min >> 1; 2645 min |= min >> 2; 2646 min |= min >> 4; 2647 min |= min >> 8; 2648 min |= min >> 16; 2649 min |= min >> 32; 2650 return min + 1; 2651 } 2652 prev_bucket_countboost::unordered::detail::mix64_policy2653 static inline SizeT prev_bucket_count(SizeT max) 2654 { 2655 max |= max >> 1; 2656 max |= max >> 2; 2657 max |= max >> 4; 2658 max |= max >> 8; 2659 max |= max >> 16; 2660 max |= max >> 32; 2661 return (max >> 1) + 1; 2662 } 2663 }; 2664 2665 template <int digits, int radix> struct pick_policy_impl 2666 { 2667 typedef prime_policy<std::size_t> type; 2668 }; 2669 2670 template <> struct pick_policy_impl<64, 2> 2671 { 2672 typedef mix64_policy<std::size_t> type; 2673 }; 2674 2675 template <typename T> 2676 struct pick_policy2 2677 : pick_policy_impl<std::numeric_limits<std::size_t>::digits, 2678 std::numeric_limits<std::size_t>::radix> 2679 { 2680 }; 2681 2682 // While the mix policy is generally faster, the prime policy is a lot 2683 // faster when a large number consecutive integers are used, because 2684 // there are no collisions. Since that is probably quite common, use 2685 // prime policy for integeral types. But not the smaller ones, as they 2686 // don't have enough unique values for this to be an issue. 2687 2688 template <> struct pick_policy2<int> 2689 { 2690 typedef prime_policy<std::size_t> type; 2691 }; 2692 2693 template <> struct pick_policy2<unsigned int> 2694 { 2695 typedef prime_policy<std::size_t> type; 2696 }; 2697 2698 template <> struct pick_policy2<long> 2699 { 2700 typedef prime_policy<std::size_t> type; 2701 }; 2702 2703 template <> struct pick_policy2<unsigned long> 2704 { 2705 typedef prime_policy<std::size_t> type; 2706 }; 2707 2708 #if !defined(BOOST_NO_LONG_LONG) 2709 template <> struct pick_policy2<boost::long_long_type> 2710 { 2711 typedef prime_policy<std::size_t> type; 2712 }; 2713 2714 template <> struct pick_policy2<boost::ulong_long_type> 2715 { 2716 typedef prime_policy<std::size_t> type; 2717 }; 2718 #endif 2719 2720 template <typename T> 2721 struct pick_policy : pick_policy2<typename boost::remove_cv<T>::type> 2722 { 2723 }; 2724 2725 ////////////////////////////////////////////////////////////////////////// 2726 // Functions 2727 // 2728 // This double buffers the storage for the hash function and key equality 2729 // predicate in order to have exception safe copy/swap. To do so, 2730 // use 'construct_spare' to construct in the spare space, and then when 2731 // ready to use 'switch_functions' to switch to the new functions. 2732 // If an exception is thrown between these two calls, use 2733 // 'cleanup_spare_functions' to destroy the unused constructed functions. 2734 2735 template <class H, class P> class functions 2736 { 2737 public: 2738 static const bool nothrow_move_assignable = 2739 boost::is_nothrow_move_assignable<H>::value && 2740 boost::is_nothrow_move_assignable<P>::value; 2741 static const bool nothrow_move_constructible = 2742 boost::is_nothrow_move_constructible<H>::value && 2743 boost::is_nothrow_move_constructible<P>::value; 2744 static const bool nothrow_swappable = 2745 boost::is_nothrow_swappable<H>::value && 2746 boost::is_nothrow_swappable<P>::value; 2747 2748 private: 2749 functions& operator=(functions const&); 2750 2751 typedef compressed<H, P> function_pair; 2752 2753 typedef typename boost::aligned_storage<sizeof(function_pair), 2754 boost::alignment_of<function_pair>::value>::type aligned_function; 2755 2756 unsigned char current_; // 0/1 - Currently active functions 2757 // +2 - Both constructed 2758 aligned_function funcs_[2]; 2759 2760 public: functions(H const & hf,P const & eq)2761 functions(H const& hf, P const& eq) : current_(0) 2762 { 2763 construct_functions(current_, hf, eq); 2764 } 2765 functions(functions const & bf)2766 functions(functions const& bf) : current_(0) 2767 { 2768 construct_functions(current_, bf.current_functions()); 2769 } 2770 functions(functions & bf,boost::unordered::detail::move_tag)2771 functions(functions& bf, boost::unordered::detail::move_tag) 2772 : current_(0) 2773 { 2774 construct_functions(current_, bf.current_functions(), 2775 boost::unordered::detail::integral_constant<bool, 2776 nothrow_move_constructible>()); 2777 } 2778 ~functions()2779 ~functions() 2780 { 2781 BOOST_ASSERT(!(current_ & 2)); 2782 destroy_functions(current_); 2783 } 2784 hash_function() const2785 H const& hash_function() const { return current_functions().first(); } 2786 key_eq() const2787 P const& key_eq() const { return current_functions().second(); } 2788 current_functions() const2789 function_pair const& current_functions() const 2790 { 2791 return *static_cast<function_pair const*>( 2792 static_cast<void const*>(funcs_[current_ & 1].address())); 2793 } 2794 current_functions()2795 function_pair& current_functions() 2796 { 2797 return *static_cast<function_pair*>( 2798 static_cast<void*>(funcs_[current_ & 1].address())); 2799 } 2800 construct_spare_functions(function_pair const & f)2801 void construct_spare_functions(function_pair const& f) 2802 { 2803 BOOST_ASSERT(!(current_ & 2)); 2804 construct_functions(current_ ^ 1, f); 2805 current_ |= 2; 2806 } 2807 cleanup_spare_functions()2808 void cleanup_spare_functions() 2809 { 2810 if (current_ & 2) { 2811 current_ = static_cast<unsigned char>(current_ & 1); 2812 destroy_functions(current_ ^ 1); 2813 } 2814 } 2815 switch_functions()2816 void switch_functions() 2817 { 2818 BOOST_ASSERT(current_ & 2); 2819 destroy_functions(static_cast<unsigned char>(current_ & 1)); 2820 current_ ^= 3; 2821 } 2822 2823 private: construct_functions(unsigned char which,H const & hf,P const & eq)2824 void construct_functions(unsigned char which, H const& hf, P const& eq) 2825 { 2826 BOOST_ASSERT(!(which & 2)); 2827 new ((void*)&funcs_[which]) function_pair(hf, eq); 2828 } 2829 construct_functions(unsigned char which,function_pair const & f,boost::unordered::detail::false_type=boost::unordered::detail::false_type ())2830 void construct_functions(unsigned char which, function_pair const& f, 2831 boost::unordered::detail::false_type = 2832 boost::unordered::detail::false_type()) 2833 { 2834 BOOST_ASSERT(!(which & 2)); 2835 new ((void*)&funcs_[which]) function_pair(f); 2836 } 2837 construct_functions(unsigned char which,function_pair & f,boost::unordered::detail::true_type)2838 void construct_functions(unsigned char which, function_pair& f, 2839 boost::unordered::detail::true_type) 2840 { 2841 BOOST_ASSERT(!(which & 2)); 2842 new ((void*)&funcs_[which]) 2843 function_pair(f, boost::unordered::detail::move_tag()); 2844 } 2845 destroy_functions(unsigned char which)2846 void destroy_functions(unsigned char which) 2847 { 2848 BOOST_ASSERT(!(which & 2)); 2849 boost::unordered::detail::func::destroy( 2850 (function_pair*)(&funcs_[which])); 2851 } 2852 }; 2853 2854 //////////////////////////////////////////////////////////////////////////// 2855 // rvalue parameters when type can't be a BOOST_RV_REF(T) parameter 2856 // e.g. for int 2857 2858 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 2859 #define BOOST_UNORDERED_RV_REF(T) BOOST_RV_REF(T) 2860 #else 2861 struct please_ignore_this_overload 2862 { 2863 typedef please_ignore_this_overload type; 2864 }; 2865 2866 template <typename T> struct rv_ref_impl 2867 { 2868 typedef BOOST_RV_REF(T) type; 2869 }; 2870 2871 template <typename T> 2872 struct rv_ref 2873 : boost::detail::if_true<boost::is_class<T>::value>:: 2874 BOOST_NESTED_TEMPLATE then<boost::unordered::detail::rv_ref_impl<T>, 2875 please_ignore_this_overload>::type 2876 { 2877 }; 2878 2879 #define BOOST_UNORDERED_RV_REF(T) \ 2880 typename boost::unordered::detail::rv_ref<T>::type 2881 #endif 2882 2883 #if defined(BOOST_MSVC) 2884 #pragma warning(push) 2885 #pragma warning(disable : 4127) // conditional expression is constant 2886 #endif 2887 2888 ////////////////////////////////////////////////////////////////////////// 2889 // convert double to std::size_t 2890 double_to_size(double f)2891 inline std::size_t double_to_size(double f) 2892 { 2893 return f >= static_cast<double>( 2894 (std::numeric_limits<std::size_t>::max)()) 2895 ? (std::numeric_limits<std::size_t>::max)() 2896 : static_cast<std::size_t>(f); 2897 } 2898 2899 template <typename Types> 2900 struct table : boost::unordered::detail::functions<typename Types::hasher, 2901 typename Types::key_equal> 2902 { 2903 private: 2904 table(table const&); 2905 table& operator=(table const&); 2906 2907 public: 2908 typedef typename Types::node node; 2909 typedef typename Types::bucket bucket; 2910 typedef typename Types::hasher hasher; 2911 typedef typename Types::key_equal key_equal; 2912 typedef typename Types::const_key_type const_key_type; 2913 typedef typename Types::extractor extractor; 2914 typedef typename Types::value_type value_type; 2915 typedef typename Types::table table_impl; 2916 typedef typename Types::link_pointer link_pointer; 2917 typedef typename Types::policy policy; 2918 typedef typename Types::iterator iterator; 2919 typedef typename Types::c_iterator c_iterator; 2920 typedef typename Types::l_iterator l_iterator; 2921 typedef typename Types::cl_iterator cl_iterator; 2922 2923 typedef boost::unordered::detail::functions<typename Types::hasher, 2924 typename Types::key_equal> 2925 functions; 2926 2927 typedef typename Types::value_allocator value_allocator; 2928 typedef typename boost::unordered::detail::rebind_wrap<value_allocator, 2929 node>::type node_allocator; 2930 typedef typename boost::unordered::detail::rebind_wrap<value_allocator, 2931 bucket>::type bucket_allocator; 2932 typedef boost::unordered::detail::allocator_traits<node_allocator> 2933 node_allocator_traits; 2934 typedef boost::unordered::detail::allocator_traits<bucket_allocator> 2935 bucket_allocator_traits; 2936 typedef typename node_allocator_traits::pointer node_pointer; 2937 typedef 2938 typename node_allocator_traits::const_pointer const_node_pointer; 2939 typedef typename bucket_allocator_traits::pointer bucket_pointer; 2940 typedef boost::unordered::detail::node_constructor<node_allocator> 2941 node_constructor; 2942 typedef boost::unordered::detail::node_tmp<node_allocator> node_tmp; 2943 2944 typedef std::pair<iterator, bool> emplace_return; 2945 2946 //////////////////////////////////////////////////////////////////////// 2947 // Members 2948 2949 boost::unordered::detail::compressed<bucket_allocator, node_allocator> 2950 allocators_; 2951 std::size_t bucket_count_; 2952 std::size_t size_; 2953 float mlf_; 2954 std::size_t max_load_; 2955 bucket_pointer buckets_; 2956 2957 //////////////////////////////////////////////////////////////////////// 2958 // Data access 2959 get_nodeboost::unordered::detail::table2960 static node_pointer get_node(c_iterator it) { return it.node_; } 2961 next_nodeboost::unordered::detail::table2962 static node_pointer next_node(link_pointer n) 2963 { 2964 return static_cast<node_pointer>(n->next_); 2965 } 2966 next_for_findboost::unordered::detail::table2967 static node_pointer next_for_find(link_pointer n) 2968 { 2969 node_pointer n2 = static_cast<node_pointer>(n); 2970 do { 2971 n2 = next_node(n2); 2972 } while (n2 && !n2->is_first_in_group()); 2973 return n2; 2974 } 2975 next_groupboost::unordered::detail::table2976 node_pointer next_group(node_pointer n) const 2977 { 2978 node_pointer n1 = n; 2979 do { 2980 n1 = next_node(n1); 2981 } while (n1 && !n1->is_first_in_group()); 2982 return n1; 2983 } 2984 group_countboost::unordered::detail::table2985 std::size_t group_count(node_pointer n) const 2986 { 2987 std::size_t x = 0; 2988 node_pointer it = n; 2989 do { 2990 ++x; 2991 it = next_node(it); 2992 } while (it && !it->is_first_in_group()); 2993 2994 return x; 2995 } 2996 node_bucketboost::unordered::detail::table2997 std::size_t node_bucket(node_pointer n) const 2998 { 2999 return n->get_bucket(); 3000 } 3001 bucket_allocboost::unordered::detail::table3002 bucket_allocator const& bucket_alloc() const 3003 { 3004 return allocators_.first(); 3005 } 3006 node_allocboost::unordered::detail::table3007 node_allocator const& node_alloc() const 3008 { 3009 return allocators_.second(); 3010 } 3011 bucket_allocboost::unordered::detail::table3012 bucket_allocator& bucket_alloc() { return allocators_.first(); } 3013 node_allocboost::unordered::detail::table3014 node_allocator& node_alloc() { return allocators_.second(); } 3015 max_bucket_countboost::unordered::detail::table3016 std::size_t max_bucket_count() const 3017 { 3018 // -1 to account for the start bucket. 3019 return policy::prev_bucket_count( 3020 bucket_allocator_traits::max_size(bucket_alloc()) - 1); 3021 } 3022 get_bucket_pointerboost::unordered::detail::table3023 bucket_pointer get_bucket_pointer(std::size_t bucket_index) const 3024 { 3025 BOOST_ASSERT(buckets_); 3026 return buckets_ + static_cast<std::ptrdiff_t>(bucket_index); 3027 } 3028 get_previous_startboost::unordered::detail::table3029 link_pointer get_previous_start() const 3030 { 3031 return get_bucket_pointer(bucket_count_)->first_from_start(); 3032 } 3033 get_previous_startboost::unordered::detail::table3034 link_pointer get_previous_start(std::size_t bucket_index) const 3035 { 3036 return get_bucket_pointer(bucket_index)->next_; 3037 } 3038 beginboost::unordered::detail::table3039 node_pointer begin() const 3040 { 3041 return size_ ? next_node(get_previous_start()) : node_pointer(); 3042 } 3043 beginboost::unordered::detail::table3044 node_pointer begin(std::size_t bucket_index) const 3045 { 3046 if (!size_) 3047 return node_pointer(); 3048 link_pointer prev = get_previous_start(bucket_index); 3049 return prev ? next_node(prev) : node_pointer(); 3050 } 3051 hash_to_bucketboost::unordered::detail::table3052 std::size_t hash_to_bucket(std::size_t hash_value) const 3053 { 3054 return policy::to_bucket(bucket_count_, hash_value); 3055 } 3056 bucket_sizeboost::unordered::detail::table3057 std::size_t bucket_size(std::size_t index) const 3058 { 3059 node_pointer n = begin(index); 3060 if (!n) 3061 return 0; 3062 3063 std::size_t count = 0; 3064 while (n && node_bucket(n) == index) { 3065 ++count; 3066 n = next_node(n); 3067 } 3068 3069 return count; 3070 } 3071 3072 //////////////////////////////////////////////////////////////////////// 3073 // Load methods 3074 recalculate_max_loadboost::unordered::detail::table3075 void recalculate_max_load() 3076 { 3077 using namespace std; 3078 3079 // From 6.3.1/13: 3080 // Only resize when size >= mlf_ * count 3081 max_load_ = buckets_ ? boost::unordered::detail::double_to_size( 3082 ceil(static_cast<double>(mlf_) * 3083 static_cast<double>(bucket_count_))) 3084 : 0; 3085 } 3086 max_load_factorboost::unordered::detail::table3087 void max_load_factor(float z) 3088 { 3089 BOOST_ASSERT(z > 0); 3090 mlf_ = (std::max)(z, minimum_max_load_factor); 3091 recalculate_max_load(); 3092 } 3093 min_buckets_for_sizeboost::unordered::detail::table3094 std::size_t min_buckets_for_size(std::size_t size) const 3095 { 3096 BOOST_ASSERT(mlf_ >= minimum_max_load_factor); 3097 3098 using namespace std; 3099 3100 // From insert/emplace requirements: 3101 // 3102 // size <= mlf_ * count 3103 // => count >= size / mlf_ 3104 // 3105 // Or from rehash post-condition: 3106 // 3107 // count >= size / mlf_ 3108 3109 return policy::new_bucket_count( 3110 boost::unordered::detail::double_to_size( 3111 floor(static_cast<double>(size) / static_cast<double>(mlf_)) + 3112 1)); 3113 } 3114 3115 //////////////////////////////////////////////////////////////////////// 3116 // Constructors 3117 tableboost::unordered::detail::table3118 table(std::size_t num_buckets, hasher const& hf, key_equal const& eq, 3119 node_allocator const& a) 3120 : functions(hf, eq), allocators_(a, a), 3121 bucket_count_(policy::new_bucket_count(num_buckets)), size_(0), 3122 mlf_(1.0f), max_load_(0), buckets_() 3123 { 3124 } 3125 tableboost::unordered::detail::table3126 table(table const& x, node_allocator const& a) 3127 : functions(x), allocators_(a, a), 3128 bucket_count_(x.min_buckets_for_size(x.size_)), size_(0), 3129 mlf_(x.mlf_), max_load_(0), buckets_() 3130 { 3131 } 3132 tableboost::unordered::detail::table3133 table(table& x, boost::unordered::detail::move_tag m) 3134 : functions(x, m), allocators_(x.allocators_, m), 3135 bucket_count_(x.bucket_count_), size_(x.size_), mlf_(x.mlf_), 3136 max_load_(x.max_load_), buckets_(x.buckets_) 3137 { 3138 x.buckets_ = bucket_pointer(); 3139 x.size_ = 0; 3140 x.max_load_ = 0; 3141 } 3142 tableboost::unordered::detail::table3143 table(table& x, node_allocator const& a, 3144 boost::unordered::detail::move_tag m) 3145 : functions(x, m), allocators_(a, a), 3146 bucket_count_(x.bucket_count_), size_(0), mlf_(x.mlf_), 3147 max_load_(0), buckets_() 3148 { 3149 } 3150 3151 //////////////////////////////////////////////////////////////////////// 3152 // Clear buckets and Create buckets 3153 // 3154 // IMPORTANT: If the container already contains any elements, the 3155 // buckets will not contain any links to them. This will 3156 // need to be dealt with, for example by: 3157 // - deleting them 3158 // - putting them in a 'node_holder' for future use 3159 // (as in assignment) 3160 // - placing them in buckets (see rehash_impl) 3161 3162 // Clear the bucket pointers. clear_bucketsboost::unordered::detail::table3163 void clear_buckets() 3164 { 3165 bucket_pointer end = get_bucket_pointer(bucket_count_); 3166 for (bucket_pointer it = buckets_; it != end; ++it) { 3167 it->next_ = node_pointer(); 3168 } 3169 } 3170 3171 // Create container buckets. If the container already contains any 3172 // buckets 3173 // the linked list will be transferred to the new buckets, but none 3174 // of the bucket pointers will be set. See above note. 3175 // 3176 // Strong exception safety. create_bucketsboost::unordered::detail::table3177 void create_buckets(std::size_t new_count) 3178 { 3179 link_pointer dummy_node; 3180 3181 // Construct the new buckets and dummy node, and destroy the old 3182 // buckets 3183 if (buckets_) { 3184 dummy_node = 3185 (buckets_ + static_cast<std::ptrdiff_t>(bucket_count_))->next_; 3186 bucket_pointer new_buckets = 3187 bucket_allocator_traits::allocate(bucket_alloc(), new_count + 1); 3188 destroy_buckets(); 3189 buckets_ = new_buckets; 3190 } else if (bucket::extra_node) { 3191 node_constructor a(node_alloc()); 3192 a.create_node(); 3193 buckets_ = 3194 bucket_allocator_traits::allocate(bucket_alloc(), new_count + 1); 3195 dummy_node = a.release(); 3196 } else { 3197 dummy_node = link_pointer(); 3198 buckets_ = 3199 bucket_allocator_traits::allocate(bucket_alloc(), new_count + 1); 3200 } 3201 3202 // nothrow from here... 3203 bucket_count_ = new_count; 3204 recalculate_max_load(); 3205 3206 bucket_pointer end = 3207 buckets_ + static_cast<std::ptrdiff_t>(new_count); 3208 for (bucket_pointer i = buckets_; i != end; ++i) { 3209 new ((void*)boost::to_address(i)) bucket(); 3210 } 3211 new ((void*)boost::to_address(end)) bucket(dummy_node); 3212 } 3213 3214 //////////////////////////////////////////////////////////////////////// 3215 // Swap and Move 3216 swap_allocatorsboost::unordered::detail::table3217 void swap_allocators(table& other, false_type) 3218 { 3219 boost::unordered::detail::func::ignore_unused_variable_warning(other); 3220 3221 // According to 23.2.1.8, if propagate_on_container_swap is 3222 // false the behaviour is undefined unless the allocators 3223 // are equal. 3224 BOOST_ASSERT(node_alloc() == other.node_alloc()); 3225 } 3226 swap_allocatorsboost::unordered::detail::table3227 void swap_allocators(table& other, true_type) 3228 { 3229 allocators_.swap(other.allocators_); 3230 } 3231 3232 // Not nothrow swappable swapboost::unordered::detail::table3233 void swap(table& x, false_type) 3234 { 3235 if (this == &x) { 3236 return; 3237 } 3238 3239 this->construct_spare_functions(x.current_functions()); 3240 BOOST_TRY { x.construct_spare_functions(this->current_functions()); } 3241 BOOST_CATCH(...) 3242 { 3243 this->cleanup_spare_functions(); 3244 BOOST_RETHROW 3245 } 3246 BOOST_CATCH_END 3247 this->switch_functions(); 3248 x.switch_functions(); 3249 3250 swap_allocators( 3251 x, boost::unordered::detail::integral_constant<bool, 3252 allocator_traits< 3253 node_allocator>::propagate_on_container_swap::value>()); 3254 3255 boost::swap(buckets_, x.buckets_); 3256 boost::swap(bucket_count_, x.bucket_count_); 3257 boost::swap(size_, x.size_); 3258 std::swap(mlf_, x.mlf_); 3259 std::swap(max_load_, x.max_load_); 3260 } 3261 3262 // Nothrow swappable swapboost::unordered::detail::table3263 void swap(table& x, true_type) 3264 { 3265 swap_allocators( 3266 x, boost::unordered::detail::integral_constant<bool, 3267 allocator_traits< 3268 node_allocator>::propagate_on_container_swap::value>()); 3269 3270 boost::swap(buckets_, x.buckets_); 3271 boost::swap(bucket_count_, x.bucket_count_); 3272 boost::swap(size_, x.size_); 3273 std::swap(mlf_, x.mlf_); 3274 std::swap(max_load_, x.max_load_); 3275 this->current_functions().swap(x.current_functions()); 3276 } 3277 3278 // Only swaps the allocators if propagate_on_container_swap. 3279 // If not propagate_on_container_swap and allocators aren't 3280 // equal, behaviour is undefined. swapboost::unordered::detail::table3281 void swap(table& x) 3282 { 3283 BOOST_ASSERT(allocator_traits< 3284 node_allocator>::propagate_on_container_swap::value || 3285 node_alloc() == x.node_alloc()); 3286 swap(x, boost::unordered::detail::integral_constant<bool, 3287 functions::nothrow_swappable>()); 3288 } 3289 3290 // Only call with nodes allocated with the currect allocator, or 3291 // one that is equal to it. (Can't assert because other's 3292 // allocators might have already been moved). move_buckets_fromboost::unordered::detail::table3293 void move_buckets_from(table& other) 3294 { 3295 BOOST_ASSERT(!buckets_); 3296 buckets_ = other.buckets_; 3297 bucket_count_ = other.bucket_count_; 3298 size_ = other.size_; 3299 max_load_ = other.max_load_; 3300 other.buckets_ = bucket_pointer(); 3301 other.size_ = 0; 3302 other.max_load_ = 0; 3303 } 3304 3305 // For use in the constructor when allocators might be different. move_construct_bucketsboost::unordered::detail::table3306 void move_construct_buckets(table& src) 3307 { 3308 if (this->node_alloc() == src.node_alloc()) { 3309 move_buckets_from(src); 3310 } else { 3311 this->create_buckets(this->bucket_count_); 3312 link_pointer prev = this->get_previous_start(); 3313 std::size_t last_bucket = this->bucket_count_; 3314 for (node_pointer n = src.begin(); n; n = next_node(n)) { 3315 std::size_t n_bucket = n->get_bucket(); 3316 if (n_bucket != last_bucket) { 3317 this->get_bucket_pointer(n_bucket)->next_ = prev; 3318 } 3319 node_pointer n2 = boost::unordered::detail::func::construct_node( 3320 this->node_alloc(), boost::move(n->value())); 3321 n2->bucket_info_ = n->bucket_info_; 3322 prev->next_ = n2; 3323 ++size_; 3324 prev = n2; 3325 last_bucket = n_bucket; 3326 } 3327 } 3328 } 3329 3330 //////////////////////////////////////////////////////////////////////// 3331 // Delete/destruct 3332 ~tableboost::unordered::detail::table3333 ~table() { delete_buckets(); } 3334 destroy_nodeboost::unordered::detail::table3335 void destroy_node(node_pointer n) 3336 { 3337 BOOST_UNORDERED_CALL_DESTROY( 3338 node_allocator_traits, node_alloc(), n->value_ptr()); 3339 boost::unordered::detail::func::destroy(boost::to_address(n)); 3340 node_allocator_traits::deallocate(node_alloc(), n, 1); 3341 } 3342 delete_bucketsboost::unordered::detail::table3343 void delete_buckets() 3344 { 3345 if (buckets_) { 3346 node_pointer n = static_cast<node_pointer>( 3347 get_bucket_pointer(bucket_count_)->next_); 3348 3349 if (bucket::extra_node) { 3350 node_pointer next = next_node(n); 3351 boost::unordered::detail::func::destroy(boost::to_address(n)); 3352 node_allocator_traits::deallocate(node_alloc(), n, 1); 3353 n = next; 3354 } 3355 3356 while (n) { 3357 node_pointer next = next_node(n); 3358 destroy_node(n); 3359 n = next; 3360 } 3361 3362 destroy_buckets(); 3363 buckets_ = bucket_pointer(); 3364 max_load_ = 0; 3365 size_ = 0; 3366 } 3367 } 3368 destroy_bucketsboost::unordered::detail::table3369 void destroy_buckets() 3370 { 3371 bucket_pointer end = get_bucket_pointer(bucket_count_ + 1); 3372 for (bucket_pointer it = buckets_; it != end; ++it) { 3373 boost::unordered::detail::func::destroy(boost::to_address(it)); 3374 } 3375 3376 bucket_allocator_traits::deallocate( 3377 bucket_alloc(), buckets_, bucket_count_ + 1); 3378 } 3379 3380 //////////////////////////////////////////////////////////////////////// 3381 // Fix buckets after delete/extract 3382 // 3383 // (prev,next) should mark an open range of nodes in a single bucket 3384 // which 3385 // have either been unlinked, or are about to be. 3386 fix_bucketboost::unordered::detail::table3387 std::size_t fix_bucket( 3388 std::size_t bucket_index, link_pointer prev, node_pointer next) 3389 { 3390 std::size_t bucket_index2 = bucket_index; 3391 3392 if (next) { 3393 bucket_index2 = node_bucket(next); 3394 3395 // If next is in the same bucket, then there's nothing to do. 3396 if (bucket_index == bucket_index2) { 3397 return bucket_index2; 3398 } 3399 3400 // Update the bucket containing next. 3401 get_bucket_pointer(bucket_index2)->next_ = prev; 3402 } 3403 3404 // Check if this bucket is now empty. 3405 bucket_pointer this_bucket = get_bucket_pointer(bucket_index); 3406 if (this_bucket->next_ == prev) { 3407 this_bucket->next_ = link_pointer(); 3408 } 3409 3410 return bucket_index2; 3411 } 3412 3413 //////////////////////////////////////////////////////////////////////// 3414 // Clear 3415 3416 void clear_impl(); 3417 3418 //////////////////////////////////////////////////////////////////////// 3419 // Assignment 3420 3421 template <typename UniqueType> assignboost::unordered::detail::table3422 void assign(table const& x, UniqueType is_unique) 3423 { 3424 if (this != &x) { 3425 assign(x, is_unique, 3426 boost::unordered::detail::integral_constant<bool, 3427 allocator_traits<node_allocator>:: 3428 propagate_on_container_copy_assignment::value>()); 3429 } 3430 } 3431 3432 template <typename UniqueType> assignboost::unordered::detail::table3433 void assign(table const& x, UniqueType is_unique, false_type) 3434 { 3435 // Strong exception safety. 3436 this->construct_spare_functions(x.current_functions()); 3437 BOOST_TRY 3438 { 3439 mlf_ = x.mlf_; 3440 recalculate_max_load(); 3441 3442 if (x.size_ > max_load_) { 3443 create_buckets(min_buckets_for_size(x.size_)); 3444 } else if (size_) { 3445 clear_buckets(); 3446 } 3447 } 3448 BOOST_CATCH(...) 3449 { 3450 this->cleanup_spare_functions(); 3451 BOOST_RETHROW 3452 } 3453 BOOST_CATCH_END 3454 this->switch_functions(); 3455 assign_buckets(x, is_unique); 3456 } 3457 3458 template <typename UniqueType> assignboost::unordered::detail::table3459 void assign(table const& x, UniqueType is_unique, true_type) 3460 { 3461 if (node_alloc() == x.node_alloc()) { 3462 allocators_.assign(x.allocators_); 3463 assign(x, is_unique, false_type()); 3464 } else { 3465 this->construct_spare_functions(x.current_functions()); 3466 this->switch_functions(); 3467 3468 // Delete everything with current allocators before assigning 3469 // the new ones. 3470 delete_buckets(); 3471 allocators_.assign(x.allocators_); 3472 3473 // Copy over other data, all no throw. 3474 mlf_ = x.mlf_; 3475 bucket_count_ = min_buckets_for_size(x.size_); 3476 3477 // Finally copy the elements. 3478 if (x.size_) { 3479 copy_buckets(x, is_unique); 3480 } 3481 } 3482 } 3483 3484 template <typename UniqueType> move_assignboost::unordered::detail::table3485 void move_assign(table& x, UniqueType is_unique) 3486 { 3487 if (this != &x) { 3488 move_assign(x, is_unique, 3489 boost::unordered::detail::integral_constant<bool, 3490 allocator_traits<node_allocator>:: 3491 propagate_on_container_move_assignment::value>()); 3492 } 3493 } 3494 3495 // Propagate allocator 3496 template <typename UniqueType> move_assignboost::unordered::detail::table3497 void move_assign(table& x, UniqueType, true_type) 3498 { 3499 if (!functions::nothrow_move_assignable) { 3500 this->construct_spare_functions(x.current_functions()); 3501 this->switch_functions(); 3502 } else { 3503 this->current_functions().move_assign(x.current_functions()); 3504 } 3505 delete_buckets(); 3506 allocators_.move_assign(x.allocators_); 3507 mlf_ = x.mlf_; 3508 move_buckets_from(x); 3509 } 3510 3511 // Don't propagate allocator 3512 template <typename UniqueType> move_assignboost::unordered::detail::table3513 void move_assign(table& x, UniqueType is_unique, false_type) 3514 { 3515 if (node_alloc() == x.node_alloc()) { 3516 move_assign_equal_alloc(x); 3517 } else { 3518 move_assign_realloc(x, is_unique); 3519 } 3520 } 3521 move_assign_equal_allocboost::unordered::detail::table3522 void move_assign_equal_alloc(table& x) 3523 { 3524 if (!functions::nothrow_move_assignable) { 3525 this->construct_spare_functions(x.current_functions()); 3526 this->switch_functions(); 3527 } else { 3528 this->current_functions().move_assign(x.current_functions()); 3529 } 3530 delete_buckets(); 3531 mlf_ = x.mlf_; 3532 move_buckets_from(x); 3533 } 3534 3535 template <typename UniqueType> move_assign_reallocboost::unordered::detail::table3536 void move_assign_realloc(table& x, UniqueType is_unique) 3537 { 3538 this->construct_spare_functions(x.current_functions()); 3539 BOOST_TRY 3540 { 3541 mlf_ = x.mlf_; 3542 recalculate_max_load(); 3543 3544 if (x.size_ > max_load_) { 3545 create_buckets(min_buckets_for_size(x.size_)); 3546 } else if (size_) { 3547 clear_buckets(); 3548 } 3549 } 3550 BOOST_CATCH(...) 3551 { 3552 this->cleanup_spare_functions(); 3553 BOOST_RETHROW 3554 } 3555 BOOST_CATCH_END 3556 this->switch_functions(); 3557 move_assign_buckets(x, is_unique); 3558 } 3559 3560 // Accessors 3561 get_keyboost::unordered::detail::table3562 const_key_type& get_key(node_pointer n) const 3563 { 3564 return extractor::extract(n->value()); 3565 } 3566 hashboost::unordered::detail::table3567 std::size_t hash(const_key_type& k) const 3568 { 3569 return policy::apply_hash(this->hash_function(), k); 3570 } 3571 3572 // Find Node 3573 find_nodeboost::unordered::detail::table3574 node_pointer find_node(std::size_t key_hash, const_key_type& k) const 3575 { 3576 return this->find_node_impl(key_hash, k, this->key_eq()); 3577 } 3578 find_nodeboost::unordered::detail::table3579 node_pointer find_node(const_key_type& k) const 3580 { 3581 return this->find_node_impl(hash(k), k, this->key_eq()); 3582 } 3583 3584 template <class Key, class Pred> find_node_implboost::unordered::detail::table3585 node_pointer find_node_impl( 3586 std::size_t key_hash, Key const& k, Pred const& eq) const 3587 { 3588 std::size_t bucket_index = this->hash_to_bucket(key_hash); 3589 node_pointer n = this->begin(bucket_index); 3590 3591 for (;;) { 3592 if (!n) 3593 return n; 3594 3595 if (eq(k, this->get_key(n))) { 3596 return n; 3597 } else if (this->node_bucket(n) != bucket_index) { 3598 return node_pointer(); 3599 } 3600 3601 n = next_for_find(n); 3602 } 3603 } 3604 3605 // Find the node before the key, so that it can be erased. find_previous_nodeboost::unordered::detail::table3606 link_pointer find_previous_node( 3607 const_key_type& k, std::size_t bucket_index) 3608 { 3609 link_pointer prev = this->get_previous_start(bucket_index); 3610 if (!prev) { 3611 return prev; 3612 } 3613 3614 for (;;) { 3615 node_pointer n = next_node(prev); 3616 if (!n) { 3617 return link_pointer(); 3618 } else if (n->is_first_in_group()) { 3619 if (node_bucket(n) != bucket_index) { 3620 return link_pointer(); 3621 } else if (this->key_eq()(k, this->get_key(n))) { 3622 return prev; 3623 } 3624 } 3625 prev = n; 3626 } 3627 } 3628 3629 // Extract and erase 3630 extract_by_keyboost::unordered::detail::table3631 inline node_pointer extract_by_key(const_key_type& k) 3632 { 3633 if (!this->size_) { 3634 return node_pointer(); 3635 } 3636 std::size_t key_hash = this->hash(k); 3637 std::size_t bucket_index = this->hash_to_bucket(key_hash); 3638 link_pointer prev = this->find_previous_node(k, bucket_index); 3639 if (!prev) { 3640 return node_pointer(); 3641 } 3642 node_pointer n = next_node(prev); 3643 node_pointer n2 = next_node(n); 3644 if (n2) { 3645 n2->set_first_in_group(); 3646 } 3647 prev->next_ = n2; 3648 --this->size_; 3649 this->fix_bucket(bucket_index, prev, n2); 3650 n->next_ = link_pointer(); 3651 3652 return n; 3653 } 3654 3655 // Reserve and rehash 3656 3657 void reserve_for_insert(std::size_t); 3658 void rehash(std::size_t); 3659 void reserve(std::size_t); 3660 void rehash_impl(std::size_t); 3661 3662 //////////////////////////////////////////////////////////////////////// 3663 // Unique keys 3664 3665 // equals 3666 equals_uniqueboost::unordered::detail::table3667 bool equals_unique(table const& other) const 3668 { 3669 if (this->size_ != other.size_) 3670 return false; 3671 3672 for (node_pointer n1 = this->begin(); n1; n1 = next_node(n1)) { 3673 node_pointer n2 = other.find_node(other.get_key(n1)); 3674 3675 if (!n2 || n1->value() != n2->value()) 3676 return false; 3677 } 3678 3679 return true; 3680 } 3681 3682 // Emplace/Insert 3683 add_node_uniqueboost::unordered::detail::table3684 inline node_pointer add_node_unique( 3685 node_pointer n, std::size_t key_hash) 3686 { 3687 std::size_t bucket_index = this->hash_to_bucket(key_hash); 3688 bucket_pointer b = this->get_bucket_pointer(bucket_index); 3689 3690 n->bucket_info_ = bucket_index; 3691 n->set_first_in_group(); 3692 3693 if (!b->next_) { 3694 link_pointer start_node = this->get_previous_start(); 3695 3696 if (start_node->next_) { 3697 this->get_bucket_pointer(node_bucket(next_node(start_node))) 3698 ->next_ = n; 3699 } 3700 3701 b->next_ = start_node; 3702 n->next_ = start_node->next_; 3703 start_node->next_ = n; 3704 } else { 3705 n->next_ = b->next_->next_; 3706 b->next_->next_ = n; 3707 } 3708 3709 ++this->size_; 3710 return n; 3711 } 3712 resize_and_add_node_uniqueboost::unordered::detail::table3713 inline node_pointer resize_and_add_node_unique( 3714 node_pointer n, std::size_t key_hash) 3715 { 3716 node_tmp b(n, this->node_alloc()); 3717 this->reserve_for_insert(this->size_ + 1); 3718 return this->add_node_unique(b.release(), key_hash); 3719 } 3720 3721 template <BOOST_UNORDERED_EMPLACE_TEMPLATE> emplace_hint_uniqueboost::unordered::detail::table3722 iterator emplace_hint_unique( 3723 c_iterator hint, const_key_type& k, BOOST_UNORDERED_EMPLACE_ARGS) 3724 { 3725 if (hint.node_ && this->key_eq()(k, this->get_key(hint.node_))) { 3726 return iterator(hint.node_); 3727 } else { 3728 return emplace_unique(k, BOOST_UNORDERED_EMPLACE_FORWARD).first; 3729 } 3730 } 3731 3732 template <BOOST_UNORDERED_EMPLACE_TEMPLATE> emplace_uniqueboost::unordered::detail::table3733 emplace_return emplace_unique( 3734 const_key_type& k, BOOST_UNORDERED_EMPLACE_ARGS) 3735 { 3736 std::size_t key_hash = this->hash(k); 3737 node_pointer pos = this->find_node(key_hash, k); 3738 if (pos) { 3739 return emplace_return(iterator(pos), false); 3740 } else { 3741 return emplace_return( 3742 iterator(this->resize_and_add_node_unique( 3743 boost::unordered::detail::func::construct_node_from_args( 3744 this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD), 3745 key_hash)), 3746 true); 3747 } 3748 } 3749 3750 template <BOOST_UNORDERED_EMPLACE_TEMPLATE> emplace_hint_uniqueboost::unordered::detail::table3751 iterator emplace_hint_unique( 3752 c_iterator hint, no_key, BOOST_UNORDERED_EMPLACE_ARGS) 3753 { 3754 node_tmp b(boost::unordered::detail::func::construct_node_from_args( 3755 this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD), 3756 this->node_alloc()); 3757 const_key_type& k = this->get_key(b.node_); 3758 if (hint.node_ && this->key_eq()(k, this->get_key(hint.node_))) { 3759 return iterator(hint.node_); 3760 } 3761 std::size_t key_hash = this->hash(k); 3762 node_pointer pos = this->find_node(key_hash, k); 3763 if (pos) { 3764 return iterator(pos); 3765 } else { 3766 return iterator( 3767 this->resize_and_add_node_unique(b.release(), key_hash)); 3768 } 3769 } 3770 3771 template <BOOST_UNORDERED_EMPLACE_TEMPLATE> emplace_uniqueboost::unordered::detail::table3772 emplace_return emplace_unique(no_key, BOOST_UNORDERED_EMPLACE_ARGS) 3773 { 3774 node_tmp b(boost::unordered::detail::func::construct_node_from_args( 3775 this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD), 3776 this->node_alloc()); 3777 const_key_type& k = this->get_key(b.node_); 3778 std::size_t key_hash = this->hash(k); 3779 node_pointer pos = this->find_node(key_hash, k); 3780 if (pos) { 3781 return emplace_return(iterator(pos), false); 3782 } else { 3783 return emplace_return( 3784 iterator(this->resize_and_add_node_unique(b.release(), key_hash)), 3785 true); 3786 } 3787 } 3788 3789 template <typename Key> try_emplace_uniqueboost::unordered::detail::table3790 emplace_return try_emplace_unique(BOOST_FWD_REF(Key) k) 3791 { 3792 std::size_t key_hash = this->hash(k); 3793 node_pointer pos = this->find_node(key_hash, k); 3794 if (pos) { 3795 return emplace_return(iterator(pos), false); 3796 } else { 3797 return emplace_return( 3798 iterator(this->resize_and_add_node_unique( 3799 boost::unordered::detail::func::construct_node_pair( 3800 this->node_alloc(), boost::forward<Key>(k)), 3801 key_hash)), 3802 true); 3803 } 3804 } 3805 3806 template <typename Key> try_emplace_hint_uniqueboost::unordered::detail::table3807 iterator try_emplace_hint_unique(c_iterator hint, BOOST_FWD_REF(Key) k) 3808 { 3809 if (hint.node_ && this->key_eq()(hint->first, k)) { 3810 return iterator(hint.node_); 3811 } else { 3812 return try_emplace_unique(k).first; 3813 } 3814 } 3815 3816 template <typename Key, BOOST_UNORDERED_EMPLACE_TEMPLATE> try_emplace_uniqueboost::unordered::detail::table3817 emplace_return try_emplace_unique( 3818 BOOST_FWD_REF(Key) k, BOOST_UNORDERED_EMPLACE_ARGS) 3819 { 3820 std::size_t key_hash = this->hash(k); 3821 node_pointer pos = this->find_node(key_hash, k); 3822 if (pos) { 3823 return emplace_return(iterator(pos), false); 3824 } else { 3825 return emplace_return( 3826 iterator(this->resize_and_add_node_unique( 3827 boost::unordered::detail::func::construct_node_pair_from_args( 3828 this->node_alloc(), boost::forward<Key>(k), 3829 BOOST_UNORDERED_EMPLACE_FORWARD), 3830 key_hash)), 3831 true); 3832 } 3833 } 3834 3835 template <typename Key, BOOST_UNORDERED_EMPLACE_TEMPLATE> try_emplace_hint_uniqueboost::unordered::detail::table3836 iterator try_emplace_hint_unique( 3837 c_iterator hint, BOOST_FWD_REF(Key) k, BOOST_UNORDERED_EMPLACE_ARGS) 3838 { 3839 if (hint.node_ && this->key_eq()(hint->first, k)) { 3840 return iterator(hint.node_); 3841 } else { 3842 return try_emplace_unique(k, BOOST_UNORDERED_EMPLACE_FORWARD).first; 3843 } 3844 } 3845 3846 template <typename Key, typename M> insert_or_assign_uniqueboost::unordered::detail::table3847 emplace_return insert_or_assign_unique( 3848 BOOST_FWD_REF(Key) k, BOOST_FWD_REF(M) obj) 3849 { 3850 std::size_t key_hash = this->hash(k); 3851 node_pointer pos = this->find_node(key_hash, k); 3852 3853 if (pos) { 3854 pos->value().second = boost::forward<M>(obj); 3855 return emplace_return(iterator(pos), false); 3856 } else { 3857 return emplace_return( 3858 iterator(this->resize_and_add_node_unique( 3859 boost::unordered::detail::func::construct_node_pair( 3860 this->node_alloc(), boost::forward<Key>(k), 3861 boost::forward<M>(obj)), 3862 key_hash)), 3863 true); 3864 } 3865 } 3866 3867 template <typename NodeType, typename InsertReturnType> move_insert_node_type_uniqueboost::unordered::detail::table3868 void move_insert_node_type_unique( 3869 NodeType& np, InsertReturnType& result) 3870 { 3871 if (np) { 3872 const_key_type& k = this->get_key(np.ptr_); 3873 std::size_t key_hash = this->hash(k); 3874 node_pointer pos = this->find_node(key_hash, k); 3875 3876 if (pos) { 3877 result.node = boost::move(np); 3878 result.position = iterator(pos); 3879 } else { 3880 this->reserve_for_insert(this->size_ + 1); 3881 result.position = 3882 iterator(this->add_node_unique(np.ptr_, key_hash)); 3883 result.inserted = true; 3884 np.ptr_ = node_pointer(); 3885 } 3886 } 3887 } 3888 3889 template <typename NodeType> move_insert_node_type_with_hint_uniqueboost::unordered::detail::table3890 iterator move_insert_node_type_with_hint_unique( 3891 c_iterator hint, NodeType& np) 3892 { 3893 if (!np) { 3894 return iterator(); 3895 } 3896 const_key_type& k = this->get_key(np.ptr_); 3897 if (hint.node_ && this->key_eq()(k, this->get_key(hint.node_))) { 3898 return iterator(hint.node_); 3899 } 3900 std::size_t key_hash = this->hash(k); 3901 node_pointer pos = this->find_node(key_hash, k); 3902 if (!pos) { 3903 this->reserve_for_insert(this->size_ + 1); 3904 pos = this->add_node_unique(np.ptr_, key_hash); 3905 np.ptr_ = node_pointer(); 3906 } 3907 return iterator(pos); 3908 } 3909 3910 template <typename Types2> merge_uniqueboost::unordered::detail::table3911 void merge_unique(boost::unordered::detail::table<Types2>& other) 3912 { 3913 typedef boost::unordered::detail::table<Types2> other_table; 3914 BOOST_STATIC_ASSERT( 3915 (boost::is_same<node, typename other_table::node>::value)); 3916 BOOST_ASSERT(this->node_alloc() == other.node_alloc()); 3917 3918 if (other.size_) { 3919 link_pointer prev = other.get_previous_start(); 3920 3921 while (prev->next_) { 3922 node_pointer n = other_table::next_node(prev); 3923 const_key_type& k = this->get_key(n); 3924 std::size_t key_hash = this->hash(k); 3925 node_pointer pos = this->find_node(key_hash, k); 3926 3927 if (pos) { 3928 prev = n; 3929 } else { 3930 this->reserve_for_insert(this->size_ + 1); 3931 node_pointer n2 = next_node(n); 3932 prev->next_ = n2; 3933 if (n2 && n->is_first_in_group()) { 3934 n2->set_first_in_group(); 3935 } 3936 --other.size_; 3937 other.fix_bucket(other.node_bucket(n), prev, n2); 3938 this->add_node_unique(n, key_hash); 3939 } 3940 } 3941 } 3942 } 3943 3944 //////////////////////////////////////////////////////////////////////// 3945 // Insert range methods 3946 // 3947 // if hash function throws, or inserting > 1 element, basic exception 3948 // safety strong otherwise 3949 3950 template <class InputIt> insert_range_uniqueboost::unordered::detail::table3951 void insert_range_unique(const_key_type& k, InputIt i, InputIt j) 3952 { 3953 insert_range_unique2(k, i, j); 3954 3955 while (++i != j) { 3956 // Note: can't use get_key as '*i' might not be value_type - it 3957 // could be a pair with first_types as key_type without const or 3958 // a different second_type. 3959 insert_range_unique2(extractor::extract(*i), i, j); 3960 } 3961 } 3962 3963 template <class InputIt> insert_range_unique2boost::unordered::detail::table3964 void insert_range_unique2(const_key_type& k, InputIt i, InputIt j) 3965 { 3966 // No side effects in this initial code 3967 std::size_t key_hash = this->hash(k); 3968 node_pointer pos = this->find_node(key_hash, k); 3969 3970 if (!pos) { 3971 node_tmp b(boost::unordered::detail::func::construct_node( 3972 this->node_alloc(), *i), 3973 this->node_alloc()); 3974 if (this->size_ + 1 > this->max_load_) 3975 this->reserve_for_insert( 3976 this->size_ + boost::unordered::detail::insert_size(i, j)); 3977 this->add_node_unique(b.release(), key_hash); 3978 } 3979 } 3980 3981 template <class InputIt> insert_range_uniqueboost::unordered::detail::table3982 void insert_range_unique(no_key, InputIt i, InputIt j) 3983 { 3984 node_constructor a(this->node_alloc()); 3985 3986 do { 3987 if (!a.node_) { 3988 a.create_node(); 3989 } 3990 BOOST_UNORDERED_CALL_CONSTRUCT1( 3991 node_allocator_traits, a.alloc_, a.node_->value_ptr(), *i); 3992 node_tmp b(a.release(), a.alloc_); 3993 3994 const_key_type& k = this->get_key(b.node_); 3995 std::size_t key_hash = this->hash(k); 3996 node_pointer pos = this->find_node(key_hash, k); 3997 3998 if (pos) { 3999 a.reclaim(b.release()); 4000 } else { 4001 // reserve has basic exception safety if the hash function 4002 // throws, strong otherwise. 4003 this->reserve_for_insert(this->size_ + 1); 4004 this->add_node_unique(b.release(), key_hash); 4005 } 4006 } while (++i != j); 4007 } 4008 4009 //////////////////////////////////////////////////////////////////////// 4010 // Extract 4011 extract_by_iterator_uniqueboost::unordered::detail::table4012 inline node_pointer extract_by_iterator_unique(c_iterator i) 4013 { 4014 node_pointer n = i.node_; 4015 BOOST_ASSERT(n); 4016 std::size_t bucket_index = this->node_bucket(n); 4017 link_pointer prev = this->get_previous_start(bucket_index); 4018 while (prev->next_ != n) { 4019 prev = prev->next_; 4020 } 4021 node_pointer n2 = next_node(n); 4022 prev->next_ = n2; 4023 --this->size_; 4024 this->fix_bucket(bucket_index, prev, n2); 4025 n->next_ = link_pointer(); 4026 return n; 4027 } 4028 4029 //////////////////////////////////////////////////////////////////////// 4030 // Erase 4031 // 4032 // no throw 4033 erase_key_uniqueboost::unordered::detail::table4034 std::size_t erase_key_unique(const_key_type& k) 4035 { 4036 if (!this->size_) 4037 return 0; 4038 std::size_t key_hash = this->hash(k); 4039 std::size_t bucket_index = this->hash_to_bucket(key_hash); 4040 link_pointer prev = this->find_previous_node(k, bucket_index); 4041 if (!prev) 4042 return 0; 4043 node_pointer n = next_node(prev); 4044 node_pointer n2 = next_node(n); 4045 prev->next_ = n2; 4046 --size_; 4047 this->fix_bucket(bucket_index, prev, n2); 4048 this->destroy_node(n); 4049 return 1; 4050 } 4051 erase_nodes_uniqueboost::unordered::detail::table4052 void erase_nodes_unique(node_pointer i, node_pointer j) 4053 { 4054 std::size_t bucket_index = this->node_bucket(i); 4055 4056 // Find the node before i. 4057 link_pointer prev = this->get_previous_start(bucket_index); 4058 while (prev->next_ != i) 4059 prev = prev->next_; 4060 4061 // Delete the nodes. 4062 prev->next_ = j; 4063 do { 4064 node_pointer next = next_node(i); 4065 destroy_node(i); 4066 --size_; 4067 bucket_index = this->fix_bucket(bucket_index, prev, next); 4068 i = next; 4069 } while (i != j); 4070 } 4071 4072 //////////////////////////////////////////////////////////////////////// 4073 // fill_buckets_unique 4074 copy_bucketsboost::unordered::detail::table4075 void copy_buckets(table const& src, true_type) 4076 { 4077 this->create_buckets(this->bucket_count_); 4078 4079 for (node_pointer n = src.begin(); n; n = next_node(n)) { 4080 std::size_t key_hash = this->hash(this->get_key(n)); 4081 this->add_node_unique( 4082 boost::unordered::detail::func::construct_node( 4083 this->node_alloc(), n->value()), 4084 key_hash); 4085 } 4086 } 4087 assign_bucketsboost::unordered::detail::table4088 void assign_buckets(table const& src, true_type) 4089 { 4090 node_holder<node_allocator> holder(*this); 4091 for (node_pointer n = src.begin(); n; n = next_node(n)) { 4092 std::size_t key_hash = this->hash(this->get_key(n)); 4093 this->add_node_unique(holder.copy_of(n->value()), key_hash); 4094 } 4095 } 4096 move_assign_bucketsboost::unordered::detail::table4097 void move_assign_buckets(table& src, true_type) 4098 { 4099 node_holder<node_allocator> holder(*this); 4100 for (node_pointer n = src.begin(); n; n = next_node(n)) { 4101 std::size_t key_hash = this->hash(this->get_key(n)); 4102 this->add_node_unique(holder.move_copy_of(n->value()), key_hash); 4103 } 4104 } 4105 4106 //////////////////////////////////////////////////////////////////////// 4107 // Equivalent keys 4108 4109 // Equality 4110 equals_equivboost::unordered::detail::table4111 bool equals_equiv(table const& other) const 4112 { 4113 if (this->size_ != other.size_) 4114 return false; 4115 4116 for (node_pointer n1 = this->begin(); n1;) { 4117 node_pointer n2 = other.find_node(other.get_key(n1)); 4118 if (!n2) 4119 return false; 4120 node_pointer end1 = next_group(n1); 4121 node_pointer end2 = next_group(n2); 4122 if (!group_equals_equiv(n1, end1, n2, end2)) 4123 return false; 4124 n1 = end1; 4125 } 4126 4127 return true; 4128 } 4129 group_equals_equivboost::unordered::detail::table4130 static bool group_equals_equiv(node_pointer n1, node_pointer end1, 4131 node_pointer n2, node_pointer end2) 4132 { 4133 for (;;) { 4134 if (n1->value() != n2->value()) 4135 break; 4136 4137 n1 = next_node(n1); 4138 n2 = next_node(n2); 4139 4140 if (n1 == end1) 4141 return n2 == end2; 4142 if (n2 == end2) 4143 return false; 4144 } 4145 4146 for (node_pointer n1a = n1, n2a = n2;;) { 4147 n1a = next_node(n1a); 4148 n2a = next_node(n2a); 4149 4150 if (n1a == end1) { 4151 if (n2a == end2) 4152 break; 4153 else 4154 return false; 4155 } 4156 4157 if (n2a == end2) 4158 return false; 4159 } 4160 4161 node_pointer start = n1; 4162 for (; n1 != end1; n1 = next_node(n1)) { 4163 value_type const& v = n1->value(); 4164 if (!find_equiv(start, n1, v)) { 4165 std::size_t matches = count_equal_equiv(n2, end2, v); 4166 if (!matches) 4167 return false; 4168 if (matches != 1 + count_equal_equiv(next_node(n1), end1, v)) 4169 return false; 4170 } 4171 } 4172 4173 return true; 4174 } 4175 find_equivboost::unordered::detail::table4176 static bool find_equiv( 4177 node_pointer n, node_pointer end, value_type const& v) 4178 { 4179 for (; n != end; n = next_node(n)) 4180 if (n->value() == v) 4181 return true; 4182 return false; 4183 } 4184 count_equal_equivboost::unordered::detail::table4185 static std::size_t count_equal_equiv( 4186 node_pointer n, node_pointer end, value_type const& v) 4187 { 4188 std::size_t count = 0; 4189 for (; n != end; n = next_node(n)) 4190 if (n->value() == v) 4191 ++count; 4192 return count; 4193 } 4194 4195 // Emplace/Insert 4196 add_node_equivboost::unordered::detail::table4197 inline node_pointer add_node_equiv( 4198 node_pointer n, std::size_t key_hash, node_pointer pos) 4199 { 4200 std::size_t bucket_index = this->hash_to_bucket(key_hash); 4201 n->bucket_info_ = bucket_index; 4202 4203 if (pos) { 4204 n->reset_first_in_group(); 4205 n->next_ = pos->next_; 4206 pos->next_ = n; 4207 if (n->next_) { 4208 std::size_t next_bucket = this->node_bucket(next_node(n)); 4209 if (next_bucket != bucket_index) { 4210 this->get_bucket_pointer(next_bucket)->next_ = n; 4211 } 4212 } 4213 } else { 4214 n->set_first_in_group(); 4215 bucket_pointer b = this->get_bucket_pointer(bucket_index); 4216 4217 if (!b->next_) { 4218 link_pointer start_node = this->get_previous_start(); 4219 4220 if (start_node->next_) { 4221 this 4222 ->get_bucket_pointer(this->node_bucket(next_node(start_node))) 4223 ->next_ = n; 4224 } 4225 4226 b->next_ = start_node; 4227 n->next_ = start_node->next_; 4228 start_node->next_ = n; 4229 } else { 4230 n->next_ = b->next_->next_; 4231 b->next_->next_ = n; 4232 } 4233 } 4234 ++this->size_; 4235 return n; 4236 } 4237 add_using_hint_equivboost::unordered::detail::table4238 inline node_pointer add_using_hint_equiv( 4239 node_pointer n, node_pointer hint) 4240 { 4241 n->bucket_info_ = hint->bucket_info_; 4242 n->reset_first_in_group(); 4243 n->next_ = hint->next_; 4244 hint->next_ = n; 4245 if (n->next_) { 4246 std::size_t next_bucket = this->node_bucket(next_node(n)); 4247 if (next_bucket != this->node_bucket(n)) { 4248 this->get_bucket_pointer(next_bucket)->next_ = n; 4249 } 4250 } 4251 ++this->size_; 4252 return n; 4253 } 4254 emplace_equivboost::unordered::detail::table4255 iterator emplace_equiv(node_pointer n) 4256 { 4257 node_tmp a(n, this->node_alloc()); 4258 const_key_type& k = this->get_key(a.node_); 4259 std::size_t key_hash = this->hash(k); 4260 node_pointer position = this->find_node(key_hash, k); 4261 this->reserve_for_insert(this->size_ + 1); 4262 return iterator( 4263 this->add_node_equiv(a.release(), key_hash, position)); 4264 } 4265 emplace_hint_equivboost::unordered::detail::table4266 iterator emplace_hint_equiv(c_iterator hint, node_pointer n) 4267 { 4268 node_tmp a(n, this->node_alloc()); 4269 const_key_type& k = this->get_key(a.node_); 4270 if (hint.node_ && this->key_eq()(k, this->get_key(hint.node_))) { 4271 this->reserve_for_insert(this->size_ + 1); 4272 return iterator( 4273 this->add_using_hint_equiv(a.release(), hint.node_)); 4274 } else { 4275 std::size_t key_hash = this->hash(k); 4276 node_pointer position = this->find_node(key_hash, k); 4277 this->reserve_for_insert(this->size_ + 1); 4278 return iterator( 4279 this->add_node_equiv(a.release(), key_hash, position)); 4280 } 4281 } 4282 emplace_no_rehash_equivboost::unordered::detail::table4283 void emplace_no_rehash_equiv(node_pointer n) 4284 { 4285 node_tmp a(n, this->node_alloc()); 4286 const_key_type& k = this->get_key(a.node_); 4287 std::size_t key_hash = this->hash(k); 4288 node_pointer position = this->find_node(key_hash, k); 4289 this->add_node_equiv(a.release(), key_hash, position); 4290 } 4291 4292 template <typename NodeType> move_insert_node_type_equivboost::unordered::detail::table4293 iterator move_insert_node_type_equiv(NodeType& np) 4294 { 4295 iterator result; 4296 4297 if (np) { 4298 const_key_type& k = this->get_key(np.ptr_); 4299 std::size_t key_hash = this->hash(k); 4300 node_pointer pos = this->find_node(key_hash, k); 4301 this->reserve_for_insert(this->size_ + 1); 4302 result = iterator(this->add_node_equiv(np.ptr_, key_hash, pos)); 4303 np.ptr_ = node_pointer(); 4304 } 4305 4306 return result; 4307 } 4308 4309 template <typename NodeType> move_insert_node_type_with_hint_equivboost::unordered::detail::table4310 iterator move_insert_node_type_with_hint_equiv( 4311 c_iterator hint, NodeType& np) 4312 { 4313 iterator result; 4314 4315 if (np) { 4316 const_key_type& k = this->get_key(np.ptr_); 4317 4318 if (hint.node_ && this->key_eq()(k, this->get_key(hint.node_))) { 4319 this->reserve_for_insert(this->size_ + 1); 4320 result = 4321 iterator(this->add_using_hint_equiv(np.ptr_, hint.node_)); 4322 } else { 4323 std::size_t key_hash = this->hash(k); 4324 node_pointer pos = this->find_node(key_hash, k); 4325 this->reserve_for_insert(this->size_ + 1); 4326 result = iterator(this->add_node_equiv(np.ptr_, key_hash, pos)); 4327 } 4328 np.ptr_ = node_pointer(); 4329 } 4330 4331 return result; 4332 } 4333 4334 //////////////////////////////////////////////////////////////////////// 4335 // Insert range methods 4336 4337 // if hash function throws, or inserting > 1 element, basic exception 4338 // safety. Strong otherwise 4339 template <class I> insert_range_equivboost::unordered::detail::table4340 void insert_range_equiv(I i, I j, 4341 typename boost::unordered::detail::enable_if_forward<I, void*>::type = 4342 0) 4343 { 4344 if (i == j) 4345 return; 4346 4347 std::size_t distance = static_cast<std::size_t>(std::distance(i, j)); 4348 if (distance == 1) { 4349 emplace_equiv(boost::unordered::detail::func::construct_node( 4350 this->node_alloc(), *i)); 4351 } else { 4352 // Only require basic exception safety here 4353 this->reserve_for_insert(this->size_ + distance); 4354 4355 for (; i != j; ++i) { 4356 emplace_no_rehash_equiv( 4357 boost::unordered::detail::func::construct_node( 4358 this->node_alloc(), *i)); 4359 } 4360 } 4361 } 4362 4363 template <class I> insert_range_equivboost::unordered::detail::table4364 void insert_range_equiv(I i, I j, 4365 typename boost::unordered::detail::disable_if_forward<I, 4366 void*>::type = 0) 4367 { 4368 for (; i != j; ++i) { 4369 emplace_equiv(boost::unordered::detail::func::construct_node( 4370 this->node_alloc(), *i)); 4371 } 4372 } 4373 4374 //////////////////////////////////////////////////////////////////////// 4375 // Extract 4376 extract_by_iterator_equivboost::unordered::detail::table4377 inline node_pointer extract_by_iterator_equiv(c_iterator n) 4378 { 4379 node_pointer i = n.node_; 4380 BOOST_ASSERT(i); 4381 node_pointer j(next_node(i)); 4382 std::size_t bucket_index = this->node_bucket(i); 4383 4384 link_pointer prev = this->get_previous_start(bucket_index); 4385 while (prev->next_ != i) { 4386 prev = next_node(prev); 4387 } 4388 4389 prev->next_ = j; 4390 if (j && i->is_first_in_group()) { 4391 j->set_first_in_group(); 4392 } 4393 --this->size_; 4394 this->fix_bucket(bucket_index, prev, j); 4395 i->next_ = link_pointer(); 4396 4397 return i; 4398 } 4399 4400 //////////////////////////////////////////////////////////////////////// 4401 // Erase 4402 // 4403 // no throw 4404 erase_key_equivboost::unordered::detail::table4405 std::size_t erase_key_equiv(const_key_type& k) 4406 { 4407 if (!this->size_) 4408 return 0; 4409 4410 std::size_t key_hash = this->hash(k); 4411 std::size_t bucket_index = this->hash_to_bucket(key_hash); 4412 link_pointer prev = this->find_previous_node(k, bucket_index); 4413 if (!prev) 4414 return 0; 4415 4416 std::size_t deleted_count = 0; 4417 node_pointer n = next_node(prev); 4418 do { 4419 node_pointer n2 = next_node(n); 4420 destroy_node(n); 4421 ++deleted_count; 4422 n = n2; 4423 } while (n && !n->is_first_in_group()); 4424 size_ -= deleted_count; 4425 prev->next_ = n; 4426 this->fix_bucket(bucket_index, prev, n); 4427 return deleted_count; 4428 } 4429 erase_nodes_equivboost::unordered::detail::table4430 link_pointer erase_nodes_equiv(node_pointer i, node_pointer j) 4431 { 4432 std::size_t bucket_index = this->node_bucket(i); 4433 4434 link_pointer prev = this->get_previous_start(bucket_index); 4435 while (prev->next_ != i) { 4436 prev = next_node(prev); 4437 } 4438 4439 // Delete the nodes. 4440 // Is it inefficient to call fix_bucket for every node? 4441 bool includes_first = false; 4442 prev->next_ = j; 4443 do { 4444 includes_first = includes_first || i->is_first_in_group(); 4445 node_pointer next = next_node(i); 4446 destroy_node(i); 4447 --size_; 4448 bucket_index = this->fix_bucket(bucket_index, prev, next); 4449 i = next; 4450 } while (i != j); 4451 if (j && includes_first) { 4452 j->set_first_in_group(); 4453 } 4454 4455 return prev; 4456 } 4457 4458 //////////////////////////////////////////////////////////////////////// 4459 // fill_buckets 4460 copy_bucketsboost::unordered::detail::table4461 void copy_buckets(table const& src, false_type) 4462 { 4463 this->create_buckets(this->bucket_count_); 4464 4465 for (node_pointer n = src.begin(); n;) { 4466 std::size_t key_hash = this->hash(this->get_key(n)); 4467 node_pointer group_end(next_group(n)); 4468 node_pointer pos = this->add_node_equiv( 4469 boost::unordered::detail::func::construct_node( 4470 this->node_alloc(), n->value()), 4471 key_hash, node_pointer()); 4472 for (n = next_node(n); n != group_end; n = next_node(n)) { 4473 this->add_node_equiv( 4474 boost::unordered::detail::func::construct_node( 4475 this->node_alloc(), n->value()), 4476 key_hash, pos); 4477 } 4478 } 4479 } 4480 assign_bucketsboost::unordered::detail::table4481 void assign_buckets(table const& src, false_type) 4482 { 4483 node_holder<node_allocator> holder(*this); 4484 for (node_pointer n = src.begin(); n;) { 4485 std::size_t key_hash = this->hash(this->get_key(n)); 4486 node_pointer group_end(next_group(n)); 4487 node_pointer pos = this->add_node_equiv( 4488 holder.copy_of(n->value()), key_hash, node_pointer()); 4489 for (n = next_node(n); n != group_end; n = next_node(n)) { 4490 this->add_node_equiv(holder.copy_of(n->value()), key_hash, pos); 4491 } 4492 } 4493 } 4494 move_assign_bucketsboost::unordered::detail::table4495 void move_assign_buckets(table& src, false_type) 4496 { 4497 node_holder<node_allocator> holder(*this); 4498 for (node_pointer n = src.begin(); n;) { 4499 std::size_t key_hash = this->hash(this->get_key(n)); 4500 node_pointer group_end(next_group(n)); 4501 node_pointer pos = this->add_node_equiv( 4502 holder.move_copy_of(n->value()), key_hash, node_pointer()); 4503 for (n = next_node(n); n != group_end; n = next_node(n)) { 4504 this->add_node_equiv( 4505 holder.move_copy_of(n->value()), key_hash, pos); 4506 } 4507 } 4508 } 4509 }; 4510 4511 ////////////////////////////////////////////////////////////////////////// 4512 // Clear 4513 clear_impl()4514 template <typename Types> inline void table<Types>::clear_impl() 4515 { 4516 if (size_) { 4517 bucket_pointer end = get_bucket_pointer(bucket_count_); 4518 for (bucket_pointer it = buckets_; it != end; ++it) { 4519 it->next_ = node_pointer(); 4520 } 4521 4522 link_pointer prev = end->first_from_start(); 4523 node_pointer n = next_node(prev); 4524 prev->next_ = node_pointer(); 4525 size_ = 0; 4526 4527 while (n) { 4528 node_pointer next = next_node(n); 4529 destroy_node(n); 4530 n = next; 4531 } 4532 } 4533 } 4534 4535 ////////////////////////////////////////////////////////////////////////// 4536 // Reserve & Rehash 4537 4538 // basic exception safety 4539 template <typename Types> reserve_for_insert(std::size_t size)4540 inline void table<Types>::reserve_for_insert(std::size_t size) 4541 { 4542 if (!buckets_) { 4543 create_buckets((std::max)(bucket_count_, min_buckets_for_size(size))); 4544 } else if (size > max_load_) { 4545 std::size_t num_buckets = 4546 min_buckets_for_size((std::max)(size, size_ + (size_ >> 1))); 4547 4548 if (num_buckets != bucket_count_) 4549 this->rehash_impl(num_buckets); 4550 } 4551 } 4552 4553 // if hash function throws, basic exception safety 4554 // strong otherwise. 4555 4556 template <typename Types> rehash(std::size_t min_buckets)4557 inline void table<Types>::rehash(std::size_t min_buckets) 4558 { 4559 using namespace std; 4560 4561 if (!size_) { 4562 delete_buckets(); 4563 bucket_count_ = policy::new_bucket_count(min_buckets); 4564 } else { 4565 min_buckets = policy::new_bucket_count((std::max)(min_buckets, 4566 boost::unordered::detail::double_to_size( 4567 floor(static_cast<double>(size_) / static_cast<double>(mlf_))) + 4568 1)); 4569 4570 if (min_buckets != bucket_count_) 4571 this->rehash_impl(min_buckets); 4572 } 4573 } 4574 4575 template <typename Types> rehash_impl(std::size_t num_buckets)4576 inline void table<Types>::rehash_impl(std::size_t num_buckets) 4577 { 4578 BOOST_ASSERT(this->buckets_); 4579 4580 this->create_buckets(num_buckets); 4581 link_pointer prev = this->get_previous_start(); 4582 BOOST_TRY 4583 { 4584 while (prev->next_) { 4585 node_pointer n = next_node(prev); 4586 std::size_t key_hash = this->hash(this->get_key(n)); 4587 std::size_t bucket_index = this->hash_to_bucket(key_hash); 4588 4589 n->bucket_info_ = bucket_index; 4590 n->set_first_in_group(); 4591 4592 // Iterator through the rest of the group of equal nodes, 4593 // setting the bucket. 4594 for (;;) { 4595 node_pointer next = next_node(n); 4596 if (!next || next->is_first_in_group()) { 4597 break; 4598 } 4599 n = next; 4600 n->bucket_info_ = bucket_index; 4601 n->reset_first_in_group(); 4602 } 4603 4604 // n is now the last node in the group 4605 bucket_pointer b = this->get_bucket_pointer(bucket_index); 4606 if (!b->next_) { 4607 b->next_ = prev; 4608 prev = n; 4609 } else { 4610 link_pointer next = n->next_; 4611 n->next_ = b->next_->next_; 4612 b->next_->next_ = prev->next_; 4613 prev->next_ = next; 4614 } 4615 } 4616 } 4617 BOOST_CATCH(...) 4618 { 4619 node_pointer n = next_node(prev); 4620 prev->next_ = node_pointer(); 4621 while (n) { 4622 node_pointer next = next_node(n); 4623 destroy_node(n); 4624 --size_; 4625 n = next; 4626 } 4627 BOOST_RETHROW 4628 } 4629 BOOST_CATCH_END 4630 } 4631 4632 #if defined(BOOST_MSVC) 4633 #pragma warning(pop) 4634 #endif 4635 4636 //////////////////////////////////////////////////////////////////////// 4637 // key extractors 4638 // 4639 // no throw 4640 // 4641 // 'extract_key' is called with the emplace parameters to return a 4642 // key if available or 'no_key' is one isn't and will need to be 4643 // constructed. This could be done by overloading the emplace 4644 // implementation 4645 // for the different cases, but that's a bit tricky on compilers without 4646 // variadic templates. 4647 4648 template <typename Key, typename T> struct is_key 4649 { 4650 template <typename T2> static choice1::type test(T2 const&); 4651 static choice2::type test(Key const&); 4652 4653 enum 4654 { 4655 value = sizeof(test(boost::unordered::detail::make<T>())) == 4656 sizeof(choice2::type) 4657 }; 4658 4659 typedef typename boost::detail::if_true<value>::BOOST_NESTED_TEMPLATE 4660 then<Key const&, no_key>::type type; 4661 }; 4662 4663 template <class ValueType> struct set_extractor 4664 { 4665 typedef ValueType value_type; 4666 typedef ValueType key_type; 4667 extractboost::unordered::detail::set_extractor4668 static key_type const& extract(value_type const& v) { return v; } 4669 extractboost::unordered::detail::set_extractor4670 static key_type const& extract(BOOST_UNORDERED_RV_REF(value_type) v) 4671 { 4672 return v; 4673 } 4674 extractboost::unordered::detail::set_extractor4675 static no_key extract() { return no_key(); } 4676 extractboost::unordered::detail::set_extractor4677 template <class Arg> static no_key extract(Arg const&) 4678 { 4679 return no_key(); 4680 } 4681 4682 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 4683 template <class Arg1, class Arg2, class... Args> extractboost::unordered::detail::set_extractor4684 static no_key extract(Arg1 const&, Arg2 const&, Args const&...) 4685 { 4686 return no_key(); 4687 } 4688 #else 4689 template <class Arg1, class Arg2> extractboost::unordered::detail::set_extractor4690 static no_key extract(Arg1 const&, Arg2 const&) 4691 { 4692 return no_key(); 4693 } 4694 #endif 4695 }; 4696 4697 template <class ValueType> struct map_extractor 4698 { 4699 typedef ValueType value_type; 4700 typedef typename boost::remove_const<typename boost::unordered::detail:: 4701 pair_traits<ValueType>::first_type>::type key_type; 4702 extractboost::unordered::detail::map_extractor4703 static key_type const& extract(value_type const& v) { return v.first; } 4704 4705 template <class Second> extractboost::unordered::detail::map_extractor4706 static key_type const& extract(std::pair<key_type, Second> const& v) 4707 { 4708 return v.first; 4709 } 4710 4711 template <class Second> extractboost::unordered::detail::map_extractor4712 static key_type const& extract( 4713 std::pair<key_type const, Second> const& v) 4714 { 4715 return v.first; 4716 } 4717 4718 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) 4719 template <class Second> extractboost::unordered::detail::map_extractor4720 static key_type const& extract( 4721 boost::rv<std::pair<key_type, Second> > const& v) 4722 { 4723 return v.first; 4724 } 4725 4726 template <class Second> extractboost::unordered::detail::map_extractor4727 static key_type const& extract( 4728 boost::rv<std::pair<key_type const, Second> > const& v) 4729 { 4730 return v.first; 4731 } 4732 #endif 4733 4734 template <class Arg1> extractboost::unordered::detail::map_extractor4735 static key_type const& extract(key_type const& k, Arg1 const&) 4736 { 4737 return k; 4738 } 4739 extractboost::unordered::detail::map_extractor4740 static no_key extract() { return no_key(); } 4741 extractboost::unordered::detail::map_extractor4742 template <class Arg> static no_key extract(Arg const&) 4743 { 4744 return no_key(); 4745 } 4746 4747 template <class Arg1, class Arg2> extractboost::unordered::detail::map_extractor4748 static no_key extract(Arg1 const&, Arg2 const&) 4749 { 4750 return no_key(); 4751 } 4752 4753 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 4754 template <class Arg1, class Arg2, class Arg3, class... Args> extractboost::unordered::detail::map_extractor4755 static no_key extract( 4756 Arg1 const&, Arg2 const&, Arg3 const&, Args const&...) 4757 { 4758 return no_key(); 4759 } 4760 #endif 4761 4762 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 4763 4764 #define BOOST_UNORDERED_KEY_FROM_TUPLE(namespace_) \ 4765 template <typename T2> \ 4766 static no_key extract(boost::unordered::piecewise_construct_t, \ 4767 namespace_ tuple<> const&, T2 const&) \ 4768 { \ 4769 return no_key(); \ 4770 } \ 4771 \ 4772 template <typename T, typename T2> \ 4773 static typename is_key<key_type, T>::type extract( \ 4774 boost::unordered::piecewise_construct_t, namespace_ tuple<T> const& k, \ 4775 T2 const&) \ 4776 { \ 4777 return typename is_key<key_type, T>::type(namespace_ get<0>(k)); \ 4778 } 4779 4780 #else 4781 4782 #define BOOST_UNORDERED_KEY_FROM_TUPLE(namespace_) \ 4783 static no_key extract( \ 4784 boost::unordered::piecewise_construct_t, namespace_ tuple<> const&) \ 4785 { \ 4786 return no_key(); \ 4787 } \ 4788 \ 4789 template <typename T> \ 4790 static typename is_key<key_type, T>::type extract( \ 4791 boost::unordered::piecewise_construct_t, namespace_ tuple<T> const& k) \ 4792 { \ 4793 return typename is_key<key_type, T>::type(namespace_ get<0>(k)); \ 4794 } 4795 4796 #endif 4797 4798 BOOST_UNORDERED_KEY_FROM_TUPLE(boost::) 4799 4800 #if BOOST_UNORDERED_TUPLE_ARGS 4801 BOOST_UNORDERED_KEY_FROM_TUPLE(std::) 4802 #endif 4803 4804 #undef BOOST_UNORDERED_KEY_FROM_TUPLE 4805 }; 4806 4807 //////////////////////////////////////////////////////////////////////// 4808 // Unique nodes 4809 4810 template <typename A, typename T> 4811 struct node : boost::unordered::detail::value_base<T> 4812 { 4813 typedef 4814 typename ::boost::unordered::detail::rebind_wrap<A, node<A, T> >::type 4815 allocator; 4816 typedef typename ::boost::unordered::detail::allocator_traits< 4817 allocator>::pointer node_pointer; 4818 typedef node_pointer link_pointer; 4819 typedef typename ::boost::unordered::detail::rebind_wrap<A, 4820 bucket<node_pointer> >::type bucket_allocator; 4821 typedef typename ::boost::unordered::detail::allocator_traits< 4822 bucket_allocator>::pointer bucket_pointer; 4823 4824 link_pointer next_; 4825 std::size_t bucket_info_; 4826 nodeboost::unordered::detail::node4827 node() : next_(), bucket_info_(0) {} 4828 get_bucketboost::unordered::detail::node4829 std::size_t get_bucket() const 4830 { 4831 return bucket_info_ & ((std::size_t)-1 >> 1); 4832 } 4833 is_first_in_groupboost::unordered::detail::node4834 std::size_t is_first_in_group() const 4835 { 4836 return !(bucket_info_ & ~((std::size_t)-1 >> 1)); 4837 } 4838 set_first_in_groupboost::unordered::detail::node4839 void set_first_in_group() 4840 { 4841 bucket_info_ = bucket_info_ & ((std::size_t)-1 >> 1); 4842 } 4843 reset_first_in_groupboost::unordered::detail::node4844 void reset_first_in_group() 4845 { 4846 bucket_info_ = bucket_info_ | ~((std::size_t)-1 >> 1); 4847 } 4848 4849 private: 4850 node& operator=(node const&); 4851 }; 4852 4853 template <typename T> 4854 struct ptr_node : boost::unordered::detail::ptr_bucket 4855 { 4856 typedef T value_type; 4857 typedef boost::unordered::detail::ptr_bucket bucket_base; 4858 typedef ptr_node<T>* node_pointer; 4859 typedef ptr_bucket* link_pointer; 4860 typedef ptr_bucket* bucket_pointer; 4861 4862 std::size_t bucket_info_; 4863 boost::unordered::detail::value_base<T> value_base_; 4864 ptr_nodeboost::unordered::detail::ptr_node4865 ptr_node() : bucket_base(), bucket_info_(0) {} 4866 addressboost::unordered::detail::ptr_node4867 void* address() { return value_base_.address(); } valueboost::unordered::detail::ptr_node4868 value_type& value() { return value_base_.value(); } value_ptrboost::unordered::detail::ptr_node4869 value_type* value_ptr() { return value_base_.value_ptr(); } 4870 get_bucketboost::unordered::detail::ptr_node4871 std::size_t get_bucket() const 4872 { 4873 return bucket_info_ & ((std::size_t)-1 >> 1); 4874 } 4875 is_first_in_groupboost::unordered::detail::ptr_node4876 std::size_t is_first_in_group() const 4877 { 4878 return !(bucket_info_ & ~((std::size_t)-1 >> 1)); 4879 } 4880 set_first_in_groupboost::unordered::detail::ptr_node4881 void set_first_in_group() 4882 { 4883 bucket_info_ = bucket_info_ & ((std::size_t)-1 >> 1); 4884 } 4885 reset_first_in_groupboost::unordered::detail::ptr_node4886 void reset_first_in_group() 4887 { 4888 bucket_info_ = bucket_info_ | ~((std::size_t)-1 >> 1); 4889 } 4890 4891 private: 4892 ptr_node& operator=(ptr_node const&); 4893 }; 4894 4895 // If the allocator uses raw pointers use ptr_node 4896 // Otherwise use node. 4897 4898 template <typename A, typename T, typename NodePtr, typename BucketPtr> 4899 struct pick_node2 4900 { 4901 typedef boost::unordered::detail::node<A, T> node; 4902 4903 typedef typename boost::unordered::detail::allocator_traits< 4904 typename boost::unordered::detail::rebind_wrap<A, 4905 node>::type>::pointer node_pointer; 4906 4907 typedef boost::unordered::detail::bucket<node_pointer> bucket; 4908 typedef node_pointer link_pointer; 4909 }; 4910 4911 template <typename A, typename T> 4912 struct pick_node2<A, T, boost::unordered::detail::ptr_node<T>*, 4913 boost::unordered::detail::ptr_bucket*> 4914 { 4915 typedef boost::unordered::detail::ptr_node<T> node; 4916 typedef boost::unordered::detail::ptr_bucket bucket; 4917 typedef bucket* link_pointer; 4918 }; 4919 4920 template <typename A, typename T> struct pick_node 4921 { 4922 typedef typename boost::remove_const<T>::type nonconst; 4923 4924 typedef boost::unordered::detail::allocator_traits< 4925 typename boost::unordered::detail::rebind_wrap<A, 4926 boost::unordered::detail::ptr_node<nonconst> >::type> 4927 tentative_node_traits; 4928 4929 typedef boost::unordered::detail::allocator_traits< 4930 typename boost::unordered::detail::rebind_wrap<A, 4931 boost::unordered::detail::ptr_bucket>::type> 4932 tentative_bucket_traits; 4933 4934 typedef pick_node2<A, nonconst, typename tentative_node_traits::pointer, 4935 typename tentative_bucket_traits::pointer> 4936 pick; 4937 4938 typedef typename pick::node node; 4939 typedef typename pick::bucket bucket; 4940 typedef typename pick::link_pointer link_pointer; 4941 }; 4942 } 4943 } 4944 } 4945 4946 #undef BOOST_UNORDERED_EMPLACE_TEMPLATE 4947 #undef BOOST_UNORDERED_EMPLACE_ARGS 4948 #undef BOOST_UNORDERED_EMPLACE_FORWARD 4949 #undef BOOST_UNORDERED_CALL_CONSTRUCT1 4950 #undef BOOST_UNORDERED_CALL_DESTROY 4951 4952 #endif 4953