ceph/src/boost/boost/unordered/detail/implementation.hpp

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