boost/unordered/detail/implementation.hpp
// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. // Copyright (C) 2005-2016 Daniel James // // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) #ifndef BOOST_UNORDERED_DETAIL_IMPLEMENTATION_HPP #define BOOST_UNORDERED_DETAIL_IMPLEMENTATION_HPP #include <boost/config.hpp> #if defined(BOOST_HAS_PRAGMA_ONCE) #pragma once #endif #include <boost/assert.hpp> #include <boost/core/no_exceptions_support.hpp> #include <boost/core/pointer_traits.hpp> #include <boost/detail/select_type.hpp> #include <boost/limits.hpp> #include <boost/move/move.hpp> #include <boost/preprocessor/arithmetic/inc.hpp> #include <boost/preprocessor/cat.hpp> #include <boost/preprocessor/repetition/enum.hpp> #include <boost/preprocessor/repetition/enum_binary_params.hpp> #include <boost/preprocessor/repetition/enum_params.hpp> #include <boost/preprocessor/repetition/repeat_from_to.hpp> #include <boost/preprocessor/seq/enum.hpp> #include <boost/preprocessor/seq/size.hpp> #include <boost/swap.hpp> #include <boost/throw_exception.hpp> #include <boost/tuple/tuple.hpp> #include <boost/type_traits/add_lvalue_reference.hpp> #include <boost/type_traits/aligned_storage.hpp> #include <boost/type_traits/alignment_of.hpp> #include <boost/type_traits/integral_constant.hpp> #include <boost/type_traits/is_base_of.hpp> #include <boost/type_traits/is_class.hpp> #include <boost/type_traits/is_empty.hpp> #include <boost/type_traits/is_nothrow_move_assignable.hpp> #include <boost/type_traits/is_nothrow_move_constructible.hpp> #include <boost/type_traits/is_nothrow_swappable.hpp> #include <boost/type_traits/is_same.hpp> #include <boost/type_traits/remove_const.hpp> #include <boost/unordered/detail/fwd.hpp> #include <boost/utility/addressof.hpp> #include <boost/utility/enable_if.hpp> #include <cmath> #include <iterator> #include <stdexcept> #include <utility> #if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS) #include <type_traits> #endif //////////////////////////////////////////////////////////////////////////////// // Configuration // // Unless documented elsewhere these configuration macros should be considered // an implementation detail, I'll try not to break them, but you never know. // Use Sun C++ workarounds // I'm not sure which versions of the compiler require these workarounds, so // I'm just using them of everything older than the current test compilers // (as of May 2017). #if !defined(BOOST_UNORDERED_SUN_WORKAROUNDS1) #if BOOST_COMP_SUNPRO && BOOST_COMP_SUNPRO < BOOST_VERSION_NUMBER(5, 20, 0) #define BOOST_UNORDERED_SUN_WORKAROUNDS1 1 #else #define BOOST_UNORDERED_SUN_WORKAROUNDS1 0 #endif #endif // BOOST_UNORDERED_EMPLACE_LIMIT = The maximum number of parameters in // emplace (not including things like hints). Don't set it to a lower value, as // that might break something. #if !defined BOOST_UNORDERED_EMPLACE_LIMIT #define BOOST_UNORDERED_EMPLACE_LIMIT 10 #endif // BOOST_UNORDERED_USE_ALLOCATOR_TRAITS - Pick which version of // allocator_traits to use. // // 0 = Own partial implementation // 1 = std::allocator_traits // 2 = boost::container::allocator_traits #if !defined(BOOST_UNORDERED_USE_ALLOCATOR_TRAITS) #if !defined(BOOST_NO_CXX11_ALLOCATOR) #define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 1 #elif defined(BOOST_MSVC) #if BOOST_MSVC < 1400 // Use container's allocator_traits for older versions of Visual // C++ as I don't test with them. #define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 2 #endif #endif #endif #if !defined(BOOST_UNORDERED_USE_ALLOCATOR_TRAITS) #define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 0 #endif // BOOST_UNORDERED_TUPLE_ARGS // // Maximum number of std::tuple members to support, or 0 if std::tuple // isn't avaiable. More are supported when full C++11 is used. // Already defined, so do nothing #if defined(BOOST_UNORDERED_TUPLE_ARGS) // Assume if we have C++11 tuple it's properly variadic, // and just use a max number of 10 arguments. #elif !defined(BOOST_NO_CXX11_HDR_TUPLE) #define BOOST_UNORDERED_TUPLE_ARGS 10 // Visual C++ has a decent enough tuple for piecewise construction, // so use that if available, using _VARIADIC_MAX for the maximum // number of parameters. Note that this comes after the check // for a full C++11 tuple. #elif defined(BOOST_MSVC) #if !BOOST_UNORDERED_HAVE_PIECEWISE_CONSTRUCT #define BOOST_UNORDERED_TUPLE_ARGS 0 #elif defined(_VARIADIC_MAX) #define BOOST_UNORDERED_TUPLE_ARGS _VARIADIC_MAX #else #define BOOST_UNORDERED_TUPLE_ARGS 5 #endif // Assume that we don't have std::tuple #else #define BOOST_UNORDERED_TUPLE_ARGS 0 #endif #if BOOST_UNORDERED_TUPLE_ARGS #include <tuple> #endif // BOOST_UNORDERED_CXX11_CONSTRUCTION // // Use C++11 construction, requires variadic arguments, good construct support // in allocator_traits and piecewise construction of std::pair // Otherwise allocators aren't used for construction/destruction #if BOOST_UNORDERED_HAVE_PIECEWISE_CONSTRUCT && \ !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) && BOOST_UNORDERED_TUPLE_ARGS #if BOOST_COMP_SUNPRO && BOOST_LIB_STD_GNU // Sun C++ std::pair piecewise construction doesn't seem to be exception safe. // (At least for Sun C++ 12.5 using libstdc++). #define BOOST_UNORDERED_CXX11_CONSTRUCTION 0 #elif BOOST_COMP_GNUC && BOOST_COMP_GNUC < BOOST_VERSION_NUMBER(4, 7, 0) // Piecewise construction in GCC 4.6 doesn't work for uncopyable types. #define BOOST_UNORDERED_CXX11_CONSTRUCTION 0 #elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 0 && \ !defined(BOOST_NO_SFINAE_EXPR) #define BOOST_UNORDERED_CXX11_CONSTRUCTION 1 #elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 1 #define BOOST_UNORDERED_CXX11_CONSTRUCTION 1 #endif #endif #if !defined(BOOST_UNORDERED_CXX11_CONSTRUCTION) #define BOOST_UNORDERED_CXX11_CONSTRUCTION 0 #endif // BOOST_UNORDERED_SUPPRESS_DEPRECATED // // Define to stop deprecation attributes #if defined(BOOST_UNORDERED_SUPPRESS_DEPRECATED) #define BOOST_UNORDERED_DEPRECATED(msg) #endif // BOOST_UNORDERED_DEPRECATED // // Wrapper around various depreaction attributes. #if defined(__has_cpp_attribute) && \ (!defined(__cplusplus) || __cplusplus >= 201402) #if __has_cpp_attribute(deprecated) && !defined(BOOST_UNORDERED_DEPRECATED) #define BOOST_UNORDERED_DEPRECATED(msg) [[deprecated(msg)]] #endif #endif #if !defined(BOOST_UNORDERED_DEPRECATED) #if defined(__GNUC__) && __GNUC__ >= 4 #define BOOST_UNORDERED_DEPRECATED(msg) __attribute__((deprecated)) #elif defined(_MSC_VER) && _MSC_VER >= 1400 #define BOOST_UNORDERED_DEPRECATED(msg) __declspec(deprecated(msg)) #elif defined(_MSC_VER) && _MSC_VER >= 1310 #define BOOST_UNORDERED_DEPRECATED(msg) __declspec(deprecated) #else #define BOOST_UNORDERED_DEPRECATED(msg) #endif #endif // BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES #if !defined(BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES) #if BOOST_COMP_CLANG && __cplusplus >= 201703 #define BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES 1 #endif #endif #if !defined(BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES) #define BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES 0 #endif namespace boost { namespace unordered { namespace iterator_detail { template <typename Node> struct iterator; template <typename Node> struct c_iterator; template <typename Node> struct l_iterator; template <typename Node> struct cl_iterator; } } } namespace boost { namespace unordered { namespace detail { template <typename Types> struct table; template <typename NodePointer> struct bucket; struct ptr_bucket; template <typename A, typename T> struct node; template <typename T> struct ptr_node; static const float minimum_max_load_factor = 1e-3f; static const std::size_t default_bucket_count = 11; struct move_tag { }; struct empty_emplace { }; struct no_key { no_key() {} template <class T> no_key(T const&) {} }; namespace func { template <class T> inline void ignore_unused_variable_warning(T const&) { } } ////////////////////////////////////////////////////////////////////////// // iterator SFINAE template <typename I> struct is_forward : boost::is_base_of<std::forward_iterator_tag, typename std::iterator_traits<I>::iterator_category> { }; template <typename I, typename ReturnType> struct enable_if_forward : boost::enable_if_c<boost::unordered::detail::is_forward<I>::value, ReturnType> { }; template <typename I, typename ReturnType> struct disable_if_forward : boost::disable_if_c<boost::unordered::detail::is_forward<I>::value, ReturnType> { }; } } } //////////////////////////////////////////////////////////////////////////////// // primes // clang-format off #define BOOST_UNORDERED_PRIMES \ (17ul)(29ul)(37ul)(53ul)(67ul)(79ul) \ (97ul)(131ul)(193ul)(257ul)(389ul)(521ul)(769ul) \ (1031ul)(1543ul)(2053ul)(3079ul)(6151ul)(12289ul)(24593ul) \ (49157ul)(98317ul)(196613ul)(393241ul)(786433ul) \ (1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul) \ (50331653ul)(100663319ul)(201326611ul)(402653189ul)(805306457ul) \ (1610612741ul)(3221225473ul)(4294967291ul) // clang-format on namespace boost { namespace unordered { namespace detail { template <class T> struct prime_list_template { static std::size_t const value[]; #if !BOOST_UNORDERED_SUN_WORKAROUNDS1 static std::ptrdiff_t const length; #else static std::ptrdiff_t const length = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES); #endif }; template <class T> std::size_t const prime_list_template<T>::value[] = { BOOST_PP_SEQ_ENUM(BOOST_UNORDERED_PRIMES)}; #if !BOOST_UNORDERED_SUN_WORKAROUNDS1 template <class T> std::ptrdiff_t const prime_list_template<T>::length = BOOST_PP_SEQ_SIZE( BOOST_UNORDERED_PRIMES); #endif #undef BOOST_UNORDERED_PRIMES typedef prime_list_template<std::size_t> prime_list; // no throw inline std::size_t next_prime(std::size_t num) { std::size_t const* const prime_list_begin = prime_list::value; std::size_t const* const prime_list_end = prime_list_begin + prime_list::length; std::size_t const* bound = std::lower_bound(prime_list_begin, prime_list_end, num); if (bound == prime_list_end) bound--; return *bound; } // no throw inline std::size_t prev_prime(std::size_t num) { std::size_t const* const prime_list_begin = prime_list::value; std::size_t const* const prime_list_end = prime_list_begin + prime_list::length; std::size_t const* bound = std::upper_bound(prime_list_begin, prime_list_end, num); if (bound != prime_list_begin) bound--; return *bound; } ////////////////////////////////////////////////////////////////////////// // insert_size/initial_size template <class I> inline std::size_t insert_size(I i, I j, typename boost::unordered::detail::enable_if_forward<I, void*>::type = 0) { return static_cast<std::size_t>(std::distance(i, j)); } template <class I> inline std::size_t insert_size(I, I, typename boost::unordered::detail::disable_if_forward<I, void*>::type = 0) { return 1; } template <class I> inline std::size_t initial_size(I i, I j, std::size_t num_buckets = boost::unordered::detail::default_bucket_count) { return (std::max)( boost::unordered::detail::insert_size(i, j), num_buckets); } ////////////////////////////////////////////////////////////////////////// // compressed template <typename T, int Index> struct compressed_base : private T { compressed_base(T const& x) : T(x) {} compressed_base(T& x, move_tag) : T(boost::move(x)) {} T& get() { return *this; } T const& get() const { return *this; } }; template <typename T, int Index> struct uncompressed_base { uncompressed_base(T const& x) : value_(x) {} uncompressed_base(T& x, move_tag) : value_(boost::move(x)) {} T& get() { return value_; } T const& get() const { return value_; } private: T value_; }; template <typename T, int Index> struct generate_base : boost::detail::if_true< boost::is_empty<T>::value>::BOOST_NESTED_TEMPLATE then<boost::unordered::detail::compressed_base<T, Index>, boost::unordered::detail::uncompressed_base<T, Index> > { }; template <typename T1, typename T2> struct compressed : private boost::unordered::detail::generate_base<T1, 1>::type, private boost::unordered::detail::generate_base<T2, 2>::type { typedef typename generate_base<T1, 1>::type base1; typedef typename generate_base<T2, 2>::type base2; typedef T1 first_type; typedef T2 second_type; first_type& first() { return static_cast<base1*>(this)->get(); } first_type const& first() const { return static_cast<base1 const*>(this)->get(); } second_type& second() { return static_cast<base2*>(this)->get(); } second_type const& second() const { return static_cast<base2 const*>(this)->get(); } template <typename First, typename Second> compressed(First const& x1, Second const& x2) : base1(x1), base2(x2) { } compressed(compressed const& x) : base1(x.first()), base2(x.second()) {} compressed(compressed& x, move_tag m) : base1(x.first(), m), base2(x.second(), m) { } void assign(compressed const& x) { first() = x.first(); second() = x.second(); } void move_assign(compressed& x) { first() = boost::move(x.first()); second() = boost::move(x.second()); } void swap(compressed& x) { boost::swap(first(), x.first()); boost::swap(second(), x.second()); } private: // Prevent assignment just to make use of assign or // move_assign explicit. compressed& operator=(compressed const&); }; ////////////////////////////////////////////////////////////////////////// // pair_traits // // Used to get the types from a pair without instantiating it. template <typename Pair> struct pair_traits { typedef typename Pair::first_type first_type; typedef typename Pair::second_type second_type; }; template <typename T1, typename T2> struct pair_traits<std::pair<T1, T2> > { typedef T1 first_type; typedef T2 second_type; }; #if defined(BOOST_MSVC) #pragma warning(push) #pragma warning(disable : 4512) // assignment operator could not be generated. #pragma warning(disable : 4345) // behavior change: an object of POD type // constructed with an initializer of the form () // will be default-initialized. #endif ////////////////////////////////////////////////////////////////////////// // Bits and pieces for implementing traits template <typename T> typename boost::add_lvalue_reference<T>::type make(); struct choice9 { typedef char (&type)[9]; }; struct choice8 : choice9 { typedef char (&type)[8]; }; struct choice7 : choice8 { typedef char (&type)[7]; }; struct choice6 : choice7 { typedef char (&type)[6]; }; struct choice5 : choice6 { typedef char (&type)[5]; }; struct choice4 : choice5 { typedef char (&type)[4]; }; struct choice3 : choice4 { typedef char (&type)[3]; }; struct choice2 : choice3 { typedef char (&type)[2]; }; struct choice1 : choice2 { typedef char (&type)[1]; }; choice1 choose(); typedef choice1::type yes_type; typedef choice2::type no_type; struct private_type { private_type const& operator,(int) const; }; template <typename T> no_type is_private_type(T const&); yes_type is_private_type(private_type const&); struct convert_from_anything { template <typename T> convert_from_anything(T const&); }; } } } //////////////////////////////////////////////////////////////////////////// // emplace_args // // Either forwarding variadic arguments, or storing the arguments in // emplace_args##n #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) #define BOOST_UNORDERED_EMPLACE_TEMPLATE typename... Args #define BOOST_UNORDERED_EMPLACE_ARGS BOOST_FWD_REF(Args)... args #define BOOST_UNORDERED_EMPLACE_FORWARD boost::forward<Args>(args)... #else #define BOOST_UNORDERED_EMPLACE_TEMPLATE typename Args #define BOOST_UNORDERED_EMPLACE_ARGS Args const& args #define BOOST_UNORDERED_EMPLACE_FORWARD args #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) #define BOOST_UNORDERED_EARGS_MEMBER(z, n, _) \ typedef BOOST_FWD_REF(BOOST_PP_CAT(A, n)) BOOST_PP_CAT(Arg, n); \ BOOST_PP_CAT(Arg, n) BOOST_PP_CAT(a, n); #else #define BOOST_UNORDERED_EARGS_MEMBER(z, n, _) \ typedef typename boost::add_lvalue_reference<BOOST_PP_CAT(A, n)>::type \ BOOST_PP_CAT(Arg, n); \ BOOST_PP_CAT(Arg, n) BOOST_PP_CAT(a, n); #endif #define BOOST_UNORDERED_FWD_PARAM(z, n, a) \ BOOST_FWD_REF(BOOST_PP_CAT(A, n)) BOOST_PP_CAT(a, n) #define BOOST_UNORDERED_CALL_FORWARD(z, i, a) \ boost::forward<BOOST_PP_CAT(A, i)>(BOOST_PP_CAT(a, i)) #define BOOST_UNORDERED_EARGS_INIT(z, n, _) \ BOOST_PP_CAT(a, n)(BOOST_PP_CAT(b, n)) #define BOOST_UNORDERED_EARGS(z, n, _) \ template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ struct BOOST_PP_CAT(emplace_args, n) \ { \ BOOST_PP_REPEAT_##z(n, BOOST_UNORDERED_EARGS_MEMBER, _) BOOST_PP_CAT( \ emplace_args, n)(BOOST_PP_ENUM_BINARY_PARAMS_Z(z, n, Arg, b)) \ : BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_EARGS_INIT, _) \ { \ } \ }; \ \ template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ inline BOOST_PP_CAT(emplace_args, n)<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> \ create_emplace_args(BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, b)) \ { \ BOOST_PP_CAT(emplace_args, n)<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> e( \ BOOST_PP_ENUM_PARAMS_Z(z, n, b)); \ return e; \ } namespace boost { namespace unordered { namespace detail { template <typename A0> struct emplace_args1 { BOOST_UNORDERED_EARGS_MEMBER(1, 0, _) explicit emplace_args1(Arg0 b0) : a0(b0) {} }; template <typename A0> inline emplace_args1<A0> create_emplace_args(BOOST_FWD_REF(A0) b0) { emplace_args1<A0> e(b0); return e; } template <typename A0, typename A1> struct emplace_args2 { BOOST_UNORDERED_EARGS_MEMBER(1, 0, _) BOOST_UNORDERED_EARGS_MEMBER(1, 1, _) emplace_args2(Arg0 b0, Arg1 b1) : a0(b0), a1(b1) {} }; template <typename A0, typename A1> inline emplace_args2<A0, A1> create_emplace_args( BOOST_FWD_REF(A0) b0, BOOST_FWD_REF(A1) b1) { emplace_args2<A0, A1> e(b0, b1); return e; } template <typename A0, typename A1, typename A2> struct emplace_args3 { BOOST_UNORDERED_EARGS_MEMBER(1, 0, _) BOOST_UNORDERED_EARGS_MEMBER(1, 1, _) BOOST_UNORDERED_EARGS_MEMBER(1, 2, _) emplace_args3(Arg0 b0, Arg1 b1, Arg2 b2) : a0(b0), a1(b1), a2(b2) {} }; template <typename A0, typename A1, typename A2> inline emplace_args3<A0, A1, A2> create_emplace_args( BOOST_FWD_REF(A0) b0, BOOST_FWD_REF(A1) b1, BOOST_FWD_REF(A2) b2) { emplace_args3<A0, A1, A2> e(b0, b1, b2); return e; } BOOST_UNORDERED_EARGS(1, 4, _) BOOST_UNORDERED_EARGS(1, 5, _) BOOST_UNORDERED_EARGS(1, 6, _) BOOST_UNORDERED_EARGS(1, 7, _) BOOST_UNORDERED_EARGS(1, 8, _) BOOST_UNORDERED_EARGS(1, 9, _) BOOST_PP_REPEAT_FROM_TO(10, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT), BOOST_UNORDERED_EARGS, _) } } } #undef BOOST_UNORDERED_DEFINE_EMPLACE_ARGS #undef BOOST_UNORDERED_EARGS_MEMBER #undef BOOST_UNORDERED_EARGS_INIT #endif //////////////////////////////////////////////////////////////////////////////// // // Some utilities for implementing allocator_traits, but useful elsewhere so // they're always defined. namespace boost { namespace unordered { namespace detail { //////////////////////////////////////////////////////////////////////////// // Integral_constrant, true_type, false_type // // Uses the standard versions if available. #if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS) using std::integral_constant; using std::true_type; using std::false_type; #else template <typename T, T Value> struct integral_constant { enum { value = Value }; }; typedef boost::unordered::detail::integral_constant<bool, true> true_type; typedef boost::unordered::detail::integral_constant<bool, false> false_type; #endif //////////////////////////////////////////////////////////////////////////// // Explicitly call a destructor #if defined(BOOST_MSVC) #pragma warning(push) #pragma warning(disable : 4100) // unreferenced formal parameter #endif namespace func { template <class T> inline void destroy(T* x) { x->~T(); } } #if defined(BOOST_MSVC) #pragma warning(pop) #endif ////////////////////////////////////////////////////////////////////////// // value_base // // Space used to store values. template <typename ValueType> struct value_base { typedef ValueType value_type; typename boost::aligned_storage<sizeof(value_type), boost::alignment_of<value_type>::value>::type data_; value_base() : data_() {} void* address() { return this; } value_type& value() { return *(ValueType*)this; } value_type const& value() const { return *(ValueType const*)this; } value_type* value_ptr() { return (ValueType*)this; } value_type const* value_ptr() const { return (ValueType const*)this; } private: value_base& operator=(value_base const&); }; ////////////////////////////////////////////////////////////////////////// // optional // TODO: Use std::optional when available. template <typename T> class optional { BOOST_MOVABLE_BUT_NOT_COPYABLE(optional) boost::unordered::detail::value_base<T> value_; bool has_value_; void destroy() { if (has_value_) { boost::unordered::detail::func::destroy(value_.value_ptr()); has_value_ = false; } } void move(optional<T>& x) { BOOST_ASSERT(!has_value_ && x.has_value_); new (value_.value_ptr()) T(boost::move(x.value_.value())); boost::unordered::detail::func::destroy(x.value_.value_ptr()); has_value_ = true; x.has_value_ = false; } public: optional() BOOST_NOEXCEPT : has_value_(false) {} optional(BOOST_RV_REF(optional<T>) x) : has_value_(false) { if (x.has_value_) { move(x); } } explicit optional(T const& x) : has_value_(true) { new (value_.value_ptr()) T(x); } optional& operator=(BOOST_RV_REF(optional<T>) x) { destroy(); if (x.has_value_) { move(x); } return *this; } ~optional() { destroy(); } bool has_value() const { return has_value_; } T& operator*() { return value_.value(); } T const& operator*() const { return value_.value(); } T* operator->() { return value_.value_ptr(); } T const* operator->() const { return value_.value_ptr(); } bool operator==(optional<T> const& x) { return has_value_ ? x.has_value_ && value_.value() == x.value_.value() : !x.has_value_; } bool operator!=(optional<T> const& x) { return !((*this) == x); } void swap(optional<T>& x) { if (has_value_ != x.has_value_) { if (has_value_) { x.move(*this); } else { move(x); } } else if (has_value_) { boost::swap(value_.value(), x.value_.value()); } } friend void swap(optional<T>& x, optional<T>& y) { x.swap(y); } }; } } } //////////////////////////////////////////////////////////////////////////// // Expression test mechanism // // When SFINAE expressions are available, define // BOOST_UNORDERED_HAS_FUNCTION which can check if a function call is // supported by a class, otherwise define BOOST_UNORDERED_HAS_MEMBER which // can detect if a class has the specified member, but not that it has the // correct type, this is good enough for a passable impression of // allocator_traits. #if !defined(BOOST_NO_SFINAE_EXPR) namespace boost { namespace unordered { namespace detail { template <typename T, long unsigned int> struct expr_test; template <typename T> struct expr_test<T, sizeof(char)> : T { }; } } } #define BOOST_UNORDERED_CHECK_EXPRESSION(count, result, expression) \ template <typename U> \ static \ typename boost::unordered::detail::expr_test<BOOST_PP_CAT(choice, result), \ sizeof(for_expr_test(((expression), 0)))>::type \ test(BOOST_PP_CAT(choice, count)) #define BOOST_UNORDERED_DEFAULT_EXPRESSION(count, result) \ template <typename U> \ static BOOST_PP_CAT(choice, result)::type test(BOOST_PP_CAT(choice, count)) #define BOOST_UNORDERED_HAS_FUNCTION(name, thing, args, _) \ struct BOOST_PP_CAT(has_, name) \ { \ template <typename U> static char for_expr_test(U const&); \ BOOST_UNORDERED_CHECK_EXPRESSION( \ 1, 1, boost::unordered::detail::make<thing>().name args); \ BOOST_UNORDERED_DEFAULT_EXPRESSION(2, 2); \ \ enum \ { \ value = sizeof(test<T>(choose())) == sizeof(choice1::type) \ }; \ } #else namespace boost { namespace unordered { namespace detail { template <typename T> struct identity { typedef T type; }; } } } #define BOOST_UNORDERED_CHECK_MEMBER(count, result, name, member) \ \ typedef \ typename boost::unordered::detail::identity<member>::type BOOST_PP_CAT( \ check, count); \ \ template <BOOST_PP_CAT(check, count) e> struct BOOST_PP_CAT(test, count) \ { \ typedef BOOST_PP_CAT(choice, result) type; \ }; \ \ template <class U> \ static typename BOOST_PP_CAT(test, count)<&U::name>::type test( \ BOOST_PP_CAT(choice, count)) #define BOOST_UNORDERED_DEFAULT_MEMBER(count, result) \ template <class U> \ static BOOST_PP_CAT(choice, result)::type test(BOOST_PP_CAT(choice, count)) #define BOOST_UNORDERED_HAS_MEMBER(name) \ struct BOOST_PP_CAT(has_, name) \ { \ struct impl \ { \ struct base_mixin \ { \ int name; \ }; \ struct base : public T, public base_mixin \ { \ }; \ \ BOOST_UNORDERED_CHECK_MEMBER(1, 1, name, int base_mixin::*); \ BOOST_UNORDERED_DEFAULT_MEMBER(2, 2); \ \ enum \ { \ value = sizeof(choice2::type) == sizeof(test<base>(choose())) \ }; \ }; \ \ enum \ { \ value = impl::value \ }; \ } #endif //////////////////////////////////////////////////////////////////////////// // TRAITS TYPE DETECTION MECHANISM // // Used to implement traits that use a type if present, or a // default otherwise. #if defined(BOOST_MSVC) && BOOST_MSVC <= 1400 #define BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(tname) \ template <typename Tp, typename Default> struct default_type_##tname \ { \ \ template <typename X> \ static choice1::type test(choice1, typename X::tname* = 0); \ \ template <typename X> static choice2::type test(choice2, void* = 0); \ \ struct DefaultWrap \ { \ typedef Default tname; \ }; \ \ enum \ { \ value = (1 == sizeof(test<Tp>(choose()))) \ }; \ \ typedef typename boost::detail::if_true<value>::BOOST_NESTED_TEMPLATE \ then<Tp, DefaultWrap>::type::tname type; \ } #else namespace boost { namespace unordered { namespace detail { template <typename T, typename T2> struct sfinae : T2 { }; } } } #define BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(tname) \ template <typename Tp, typename Default> struct default_type_##tname \ { \ \ template <typename X> \ static typename boost::unordered::detail::sfinae<typename X::tname, \ choice1>::type test(choice1); \ \ template <typename X> static choice2::type test(choice2); \ \ struct DefaultWrap \ { \ typedef Default tname; \ }; \ \ enum \ { \ value = (1 == sizeof(test<Tp>(choose()))) \ }; \ \ typedef typename boost::detail::if_true<value>::BOOST_NESTED_TEMPLATE \ then<Tp, DefaultWrap>::type::tname type; \ } #endif #define BOOST_UNORDERED_DEFAULT_TYPE(T, tname, arg) \ typename default_type_##tname<T, arg>::type //////////////////////////////////////////////////////////////////////////////// // // Allocator traits // // First our implementation, then later light wrappers around the alternatives #if BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 0 #include <boost/limits.hpp> #include <boost/pointer_to_other.hpp> #include <boost/utility/enable_if.hpp> namespace boost { namespace unordered { namespace detail { template <typename Alloc, typename T> struct rebind_alloc; #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) template <template <typename, typename...> class Alloc, typename U, typename T, typename... Args> struct rebind_alloc<Alloc<U, Args...>, T> { typedef Alloc<T, Args...> type; }; #else template <template <typename> class Alloc, typename U, typename T> struct rebind_alloc<Alloc<U>, T> { typedef Alloc<T> type; }; template <template <typename, typename> class Alloc, typename U, typename T, typename A0> struct rebind_alloc<Alloc<U, A0>, T> { typedef Alloc<T, A0> type; }; template <template <typename, typename, typename> class Alloc, typename U, typename T, typename A0, typename A1> struct rebind_alloc<Alloc<U, A0, A1>, T> { typedef Alloc<T, A0, A1> type; }; #endif template <typename Alloc, typename T> struct rebind_wrap { template <typename X> static choice1::type test( choice1, typename X::BOOST_NESTED_TEMPLATE rebind<T>::other* = 0); template <typename X> static choice2::type test(choice2, void* = 0); enum { value = (1 == sizeof(test<Alloc>(choose()))) }; struct fallback { template <typename U> struct rebind { typedef typename rebind_alloc<Alloc, T>::type other; }; }; typedef typename boost::detail::if_true<value>::BOOST_NESTED_TEMPLATE then< Alloc, fallback>::type::BOOST_NESTED_TEMPLATE rebind<T>::other type; }; } } } namespace boost { namespace unordered { namespace detail { BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(pointer); BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(const_pointer); BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(void_pointer); BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(const_void_pointer); BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(difference_type); BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(size_type); BOOST_UNORDERED_DEFAULT_TYPE_TMPLT( propagate_on_container_copy_assignment); BOOST_UNORDERED_DEFAULT_TYPE_TMPLT( propagate_on_container_move_assignment); BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(propagate_on_container_swap); BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(is_always_equal); #if !defined(BOOST_NO_SFINAE_EXPR) template <typename T> BOOST_UNORDERED_HAS_FUNCTION( select_on_container_copy_construction, U const, (), 0); template <typename T> BOOST_UNORDERED_HAS_FUNCTION(max_size, U const, (), 0); #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) template <typename T, typename ValueType, typename... Args> BOOST_UNORDERED_HAS_FUNCTION(construct, U, (boost::unordered::detail::make<ValueType*>(), boost::unordered::detail::make<Args const>()...), 2); #else template <typename T, typename ValueType> BOOST_UNORDERED_HAS_FUNCTION(construct, U, (boost::unordered::detail::make<ValueType*>(), boost::unordered::detail::make<ValueType const>()), 2); #endif template <typename T, typename ValueType> BOOST_UNORDERED_HAS_FUNCTION( destroy, U, (boost::unordered::detail::make<ValueType*>()), 1); #else template <typename T> BOOST_UNORDERED_HAS_MEMBER(select_on_container_copy_construction); template <typename T> BOOST_UNORDERED_HAS_MEMBER(max_size); template <typename T, typename ValueType> BOOST_UNORDERED_HAS_MEMBER(construct); template <typename T, typename ValueType> BOOST_UNORDERED_HAS_MEMBER(destroy); #endif } } } namespace boost { namespace unordered { namespace detail { namespace func { template <typename Alloc> inline Alloc call_select_on_container_copy_construction( const Alloc& rhs, typename boost::enable_if_c< boost::unordered::detail::has_select_on_container_copy_construction< Alloc>::value, void*>::type = 0) { return rhs.select_on_container_copy_construction(); } template <typename Alloc> inline Alloc call_select_on_container_copy_construction( const Alloc& rhs, typename boost::disable_if_c< boost::unordered::detail::has_select_on_container_copy_construction< Alloc>::value, void*>::type = 0) { return rhs; } template <typename SizeType, typename Alloc> inline SizeType call_max_size(const Alloc& a, typename boost::enable_if_c< boost::unordered::detail::has_max_size<Alloc>::value, void*>::type = 0) { return a.max_size(); } template <typename SizeType, typename Alloc> inline SizeType call_max_size(const Alloc&, typename boost::disable_if_c< boost::unordered::detail::has_max_size<Alloc>::value, void*>::type = 0) { return (std::numeric_limits<SizeType>::max)(); } } // namespace func. } } } namespace boost { namespace unordered { namespace detail { template <typename Alloc> struct allocator_traits { typedef Alloc allocator_type; typedef typename Alloc::value_type value_type; typedef BOOST_UNORDERED_DEFAULT_TYPE( Alloc, pointer, value_type*) pointer; template <typename T> struct pointer_to_other : boost::pointer_to_other<pointer, T> { }; typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, const_pointer, typename pointer_to_other<const value_type>::type) const_pointer; // typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, void_pointer, // typename pointer_to_other<void>::type) // void_pointer; // // typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, const_void_pointer, // typename pointer_to_other<const void>::type) // const_void_pointer; typedef BOOST_UNORDERED_DEFAULT_TYPE( Alloc, difference_type, std::ptrdiff_t) difference_type; typedef BOOST_UNORDERED_DEFAULT_TYPE( Alloc, size_type, std::size_t) size_type; #if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) template <typename T> using rebind_alloc = typename rebind_wrap<Alloc, T>::type; template <typename T> using rebind_traits = boost::unordered::detail::allocator_traits<rebind_alloc<T> >; #endif static pointer allocate(Alloc& a, size_type n) { return a.allocate(n); } // I never use this, so I'll just comment it out for now. // // static pointer allocate(Alloc& a, size_type n, // const_void_pointer hint) // { return DEFAULT_FUNC(allocate, pointer)(a, n, hint); } static void deallocate(Alloc& a, pointer p, size_type n) { a.deallocate(p, n); } public: #if BOOST_UNORDERED_CXX11_CONSTRUCTION template <typename T, typename... Args> static typename boost::enable_if_c<boost::unordered::detail::has_construct< Alloc, T, Args...>::value>::type construct(Alloc& a, T* p, BOOST_FWD_REF(Args)... x) { a.construct(p, boost::forward<Args>(x)...); } template <typename T, typename... Args> static typename boost::disable_if_c<boost::unordered::detail::has_construct< Alloc, T, Args...>::value>::type construct(Alloc&, T* p, BOOST_FWD_REF(Args)... x) { new (static_cast<void*>(p)) T(boost::forward<Args>(x)...); } template <typename T> static typename boost::enable_if_c< boost::unordered::detail::has_destroy<Alloc, T>::value>::type destroy(Alloc& a, T* p) { a.destroy(p); } template <typename T> static typename boost::disable_if_c< boost::unordered::detail::has_destroy<Alloc, T>::value>::type destroy(Alloc&, T* p) { boost::unordered::detail::func::destroy(p); } #elif !defined(BOOST_NO_SFINAE_EXPR) template <typename T> static typename boost::enable_if_c< boost::unordered::detail::has_construct<Alloc, T>::value>::type construct(Alloc& a, T* p, T const& x) { a.construct(p, x); } template <typename T> static typename boost::disable_if_c< boost::unordered::detail::has_construct<Alloc, T>::value>::type construct(Alloc&, T* p, T const& x) { new (static_cast<void*>(p)) T(x); } template <typename T> static typename boost::enable_if_c< boost::unordered::detail::has_destroy<Alloc, T>::value>::type destroy(Alloc& a, T* p) { a.destroy(p); } template <typename T> static typename boost::disable_if_c< boost::unordered::detail::has_destroy<Alloc, T>::value>::type destroy(Alloc&, T* p) { boost::unordered::detail::func::destroy(p); } #else // If we don't have SFINAE expressions, only call construct for the // copy constructor for the allocator's value_type - as that's // the only construct method that old fashioned allocators support. template <typename T> static void construct(Alloc& a, T* p, T const& x, typename boost::enable_if_c< boost::unordered::detail::has_construct<Alloc, T>::value && boost::is_same<T, value_type>::value, void*>::type = 0) { a.construct(p, x); } template <typename T> static void construct(Alloc&, T* p, T const& x, typename boost::disable_if_c< boost::unordered::detail::has_construct<Alloc, T>::value && boost::is_same<T, value_type>::value, void*>::type = 0) { new (static_cast<void*>(p)) T(x); } template <typename T> static void destroy(Alloc& a, T* p, typename boost::enable_if_c< boost::unordered::detail::has_destroy<Alloc, T>::value && boost::is_same<T, value_type>::value, void*>::type = 0) { a.destroy(p); } template <typename T> static void destroy(Alloc&, T* p, typename boost::disable_if_c< boost::unordered::detail::has_destroy<Alloc, T>::value && boost::is_same<T, value_type>::value, void*>::type = 0) { boost::unordered::detail::func::destroy(p); } #endif static size_type max_size(const Alloc& a) { return boost::unordered::detail::func::call_max_size<size_type>(a); } // Allocator propagation on construction static Alloc select_on_container_copy_construction(Alloc const& rhs) { return boost::unordered::detail::func:: call_select_on_container_copy_construction(rhs); } // Allocator propagation on assignment and swap. // Return true if lhs is modified. typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, propagate_on_container_copy_assignment, false_type) propagate_on_container_copy_assignment; typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, propagate_on_container_move_assignment, false_type) propagate_on_container_move_assignment; typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, propagate_on_container_swap, false_type) propagate_on_container_swap; typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, is_always_equal, typename boost::is_empty<Alloc>::type) is_always_equal; }; } } } #undef BOOST_UNORDERED_DEFAULT_TYPE_TMPLT #undef BOOST_UNORDERED_DEFAULT_TYPE //////////////////////////////////////////////////////////////////////////////// // // std::allocator_traits #elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 1 #include <memory> namespace boost { namespace unordered { namespace detail { BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(is_always_equal); template <typename Alloc> struct allocator_traits : std::allocator_traits<Alloc> { // As is_always_equal was introduced in C++17, std::allocator_traits // doesn't always have it. So use it when available, implement it // ourselves when not. Would be simpler not to bother with // std::allocator_traits, but I feel like I should try to use // it where possible. typedef BOOST_UNORDERED_DEFAULT_TYPE(std::allocator_traits<Alloc>, is_always_equal, BOOST_UNORDERED_DEFAULT_TYPE(Alloc, is_always_equal, typename boost::is_empty<Alloc>::type)) is_always_equal; }; template <typename Alloc, typename T> struct rebind_wrap { typedef typename std::allocator_traits<Alloc>::template rebind_alloc<T> type; }; } } } //////////////////////////////////////////////////////////////////////////////// // // boost::container::allocator_traits #elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 2 #include <boost/container/allocator_traits.hpp> namespace boost { namespace unordered { namespace detail { template <typename Alloc> struct allocator_traits : boost::container::allocator_traits<Alloc> { }; template <typename Alloc, typename T> struct rebind_wrap : boost::container::allocator_traits< Alloc>::template portable_rebind_alloc<T> { }; } } } #else #error "Invalid BOOST_UNORDERED_USE_ALLOCATOR_TRAITS value." #endif //////////////////////////////////////////////////////////////////////////// // Functions used to construct nodes. Emulates variadic construction, // piecewise construction etc. //////////////////////////////////////////////////////////////////////////// // construct_value // // Only use allocator_traits::construct, allocator_traits::destroy when full // C++11 support is available. #if BOOST_UNORDERED_CXX11_CONSTRUCTION #define BOOST_UNORDERED_CALL_CONSTRUCT1(Traits, alloc, address, a0) \ Traits::construct(alloc, address, a0) #define BOOST_UNORDERED_CALL_DESTROY(Traits, alloc, x) Traits::destroy(alloc, x) #elif !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) namespace boost { namespace unordered { namespace detail { namespace func { template <typename T, typename... Args> inline void construct_value(T* address, BOOST_FWD_REF(Args)... args) { new ((void*)address) T(boost::forward<Args>(args)...); } } } } } #define BOOST_UNORDERED_CALL_CONSTRUCT1(Traits, alloc, address, a0) \ boost::unordered::detail::func::construct_value(address, a0) #define BOOST_UNORDERED_CALL_DESTROY(Traits, alloc, x) \ boost::unordered::detail::func::destroy(x) #else namespace boost { namespace unordered { namespace detail { namespace func { template <typename T> inline void construct_value(T* address) { new ((void*)address) T(); } template <typename T, typename A0> inline void construct_value(T* address, BOOST_FWD_REF(A0) a0) { new ((void*)address) T(boost::forward<A0>(a0)); } } } } } #define BOOST_UNORDERED_CALL_CONSTRUCT1(Traits, alloc, address, a0) \ boost::unordered::detail::func::construct_value(address, a0) #define BOOST_UNORDERED_CALL_DESTROY(Traits, alloc, x) \ boost::unordered::detail::func::destroy(x) #endif //////////////////////////////////////////////////////////////////////////// // Construct from tuple // // Used to emulate piecewise construction. #define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(z, n, namespace_) \ template <typename Alloc, typename T, \ BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ void construct_from_tuple(Alloc&, T* ptr, \ namespace_::tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \ { \ new ((void*)ptr) \ T(BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_)); \ } #define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) namespace_::get<n>(x) // construct_from_tuple for boost::tuple // The workaround for old Sun compilers comes later in the file. #if !BOOST_UNORDERED_SUN_WORKAROUNDS1 namespace boost { namespace unordered { namespace detail { namespace func { template <typename Alloc, typename T> void construct_from_tuple(Alloc&, T* ptr, boost::tuple<>) { new ((void*)ptr) T(); } BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 1, boost) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 2, boost) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 3, boost) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 4, boost) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 5, boost) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 6, boost) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 7, boost) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 8, boost) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 9, boost) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 10, boost) } } } } #endif // construct_from_tuple for std::tuple #if !BOOST_UNORDERED_CXX11_CONSTRUCTION && BOOST_UNORDERED_TUPLE_ARGS namespace boost { namespace unordered { namespace detail { namespace func { template <typename Alloc, typename T> void construct_from_tuple(Alloc&, T* ptr, std::tuple<>) { new ((void*)ptr) T(); } BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 1, std) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 2, std) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 3, std) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 4, std) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 5, std) #if BOOST_UNORDERED_TUPLE_ARGS >= 6 BOOST_PP_REPEAT_FROM_TO(6, BOOST_PP_INC(BOOST_UNORDERED_TUPLE_ARGS), BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE, std) #endif } } } } #endif #undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE #undef BOOST_UNORDERED_GET_TUPLE_ARG // construct_from_tuple for boost::tuple on old versions of sunpro. // // Old versions of Sun C++ had problems with template overloads of // boost::tuple, so to fix it I added a distinct type for each length to // the overloads. That means there's no possible ambiguity between the // different overloads, so that the compiler doesn't get confused #if BOOST_UNORDERED_SUN_WORKAROUNDS1 #define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(z, n, namespace_) \ template <typename Alloc, typename T, \ BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ void construct_from_tuple_impl(boost::unordered::detail::func::length<n>, \ Alloc&, T* ptr, \ namespace_::tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \ { \ new ((void*)ptr) \ T(BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_)); \ } #define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) namespace_::get<n>(x) namespace boost { namespace unordered { namespace detail { namespace func { template <int N> struct length { }; template <typename Alloc, typename T> void construct_from_tuple_impl( boost::unordered::detail::func::length<0>, Alloc&, T* ptr, boost::tuple<>) { new ((void*)ptr) T(); } BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 1, boost) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 2, boost) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 3, boost) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 4, boost) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 5, boost) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 6, boost) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 7, boost) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 8, boost) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 9, boost) BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 10, boost) template <typename Alloc, typename T, typename Tuple> void construct_from_tuple(Alloc& alloc, T* ptr, Tuple const& x) { construct_from_tuple_impl(boost::unordered::detail::func::length< boost::tuples::length<Tuple>::value>(), alloc, ptr, x); } } } } } #undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE #undef BOOST_UNORDERED_GET_TUPLE_ARG #endif namespace boost { namespace unordered { namespace detail { namespace func { //////////////////////////////////////////////////////////////////////// // Trait to check for piecewise construction. template <typename A0> struct use_piecewise { static choice1::type test( choice1, boost::unordered::piecewise_construct_t); static choice2::type test(choice2, ...); enum { value = sizeof(choice1::type) == sizeof(test(choose(), boost::unordered::detail::make<A0>())) }; }; #if BOOST_UNORDERED_CXX11_CONSTRUCTION //////////////////////////////////////////////////////////////////////// // Construct from variadic parameters template <typename Alloc, typename T, typename... Args> inline void construct_from_args( Alloc& alloc, T* address, BOOST_FWD_REF(Args)... args) { boost::unordered::detail::allocator_traits<Alloc>::construct( alloc, address, boost::forward<Args>(args)...); } // For backwards compatibility, implement a special case for // piecewise_construct with boost::tuple template <typename A0> struct detect_boost_tuple { template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9> static choice1::type test(choice1, boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> const&); static choice2::type test(choice2, ...); enum { value = sizeof(choice1::type) == sizeof(test(choose(), boost::unordered::detail::make<A0>())) }; }; // Special case for piecewise_construct template <typename Alloc, typename A, typename B, typename A0, typename A1, typename A2> inline typename boost::enable_if_c<use_piecewise<A0>::value && detect_boost_tuple<A1>::value && detect_boost_tuple<A2>::value, void>::type construct_from_args(Alloc& alloc, std::pair<A, B>* address, BOOST_FWD_REF(A0), BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2) { boost::unordered::detail::func::construct_from_tuple( alloc, boost::addressof(address->first), boost::forward<A1>(a1)); BOOST_TRY { boost::unordered::detail::func::construct_from_tuple( alloc, boost::addressof(address->second), boost::forward<A2>(a2)); } BOOST_CATCH(...) { boost::unordered::detail::func::destroy( boost::addressof(address->first)); BOOST_RETHROW } BOOST_CATCH_END } #elif !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) //////////////////////////////////////////////////////////////////////// // Construct from variadic parameters template <typename Alloc, typename T, typename... Args> inline void construct_from_args( Alloc&, T* address, BOOST_FWD_REF(Args)... args) { new ((void*)address) T(boost::forward<Args>(args)...); } // Special case for piecewise_construct template <typename Alloc, typename A, typename B, typename A0, typename A1, typename A2> inline typename enable_if<use_piecewise<A0>, void>::type construct_from_args(Alloc& alloc, std::pair<A, B>* address, BOOST_FWD_REF(A0), BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2) { boost::unordered::detail::func::construct_from_tuple( alloc, boost::addressof(address->first), boost::forward<A1>(a1)); BOOST_TRY { boost::unordered::detail::func::construct_from_tuple( alloc, boost::addressof(address->second), boost::forward<A2>(a2)); } BOOST_CATCH(...) { boost::unordered::detail::func::destroy( boost::addressof(address->first)); BOOST_RETHROW } BOOST_CATCH_END } #else // BOOST_NO_CXX11_VARIADIC_TEMPLATES //////////////////////////////////////////////////////////////////////// // Construct from emplace_args // Explicitly write out first three overloads for the sake of sane // error messages. template <typename Alloc, typename T, typename A0> inline void construct_from_args( Alloc&, T* address, emplace_args1<A0> const& args) { new ((void*)address) T(boost::forward<A0>(args.a0)); } template <typename Alloc, typename T, typename A0, typename A1> inline void construct_from_args( Alloc&, T* address, emplace_args2<A0, A1> const& args) { new ((void*)address) T(boost::forward<A0>(args.a0), boost::forward<A1>(args.a1)); } template <typename Alloc, typename T, typename A0, typename A1, typename A2> inline void construct_from_args( Alloc&, T* address, emplace_args3<A0, A1, A2> const& args) { new ((void*)address) T(boost::forward<A0>(args.a0), boost::forward<A1>(args.a1), boost::forward<A2>(args.a2)); } // Use a macro for the rest. #define BOOST_UNORDERED_CONSTRUCT_IMPL(z, num_params, _) \ template <typename Alloc, typename T, \ BOOST_PP_ENUM_PARAMS_Z(z, num_params, typename A)> \ inline void construct_from_args(Alloc&, T* address, \ boost::unordered::detail::BOOST_PP_CAT(emplace_args, num_params) < \ BOOST_PP_ENUM_PARAMS_Z(z, num_params, A) > const& args) \ { \ new ((void*)address) \ T(BOOST_PP_ENUM_##z(num_params, BOOST_UNORDERED_CALL_FORWARD, args.a)); \ } BOOST_UNORDERED_CONSTRUCT_IMPL(1, 4, _) BOOST_UNORDERED_CONSTRUCT_IMPL(1, 5, _) BOOST_UNORDERED_CONSTRUCT_IMPL(1, 6, _) BOOST_UNORDERED_CONSTRUCT_IMPL(1, 7, _) BOOST_UNORDERED_CONSTRUCT_IMPL(1, 8, _) BOOST_UNORDERED_CONSTRUCT_IMPL(1, 9, _) BOOST_PP_REPEAT_FROM_TO(10, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT), BOOST_UNORDERED_CONSTRUCT_IMPL, _) #undef BOOST_UNORDERED_CONSTRUCT_IMPL // Construct with piecewise_construct template <typename Alloc, typename A, typename B, typename A0, typename A1, typename A2> inline void construct_from_args(Alloc& alloc, std::pair<A, B>* address, boost::unordered::detail::emplace_args3<A0, A1, A2> const& args, typename enable_if<use_piecewise<A0>, void*>::type = 0) { boost::unordered::detail::func::construct_from_tuple( alloc, boost::addressof(address->first), args.a1); BOOST_TRY { boost::unordered::detail::func::construct_from_tuple( alloc, boost::addressof(address->second), args.a2); } BOOST_CATCH(...) { boost::unordered::detail::func::destroy( boost::addressof(address->first)); BOOST_RETHROW } BOOST_CATCH_END } #endif // BOOST_NO_CXX11_VARIADIC_TEMPLATES } } } } namespace boost { namespace unordered { namespace detail { /////////////////////////////////////////////////////////////////// // // Node construction template <typename NodeAlloc> struct node_constructor { typedef NodeAlloc node_allocator; typedef boost::unordered::detail::allocator_traits<NodeAlloc> node_allocator_traits; typedef typename node_allocator_traits::value_type node; typedef typename node_allocator_traits::pointer node_pointer; typedef typename node::value_type value_type; node_allocator& alloc_; node_pointer node_; node_constructor(node_allocator& n) : alloc_(n), node_() {} ~node_constructor(); void create_node(); // no throw node_pointer release() { BOOST_ASSERT(node_); node_pointer p = node_; node_ = node_pointer(); return p; } void reclaim(node_pointer p) { BOOST_ASSERT(!node_); node_ = p; BOOST_UNORDERED_CALL_DESTROY( node_allocator_traits, alloc_, node_->value_ptr()); } private: node_constructor(node_constructor const&); node_constructor& operator=(node_constructor const&); }; template <typename Alloc> node_constructor<Alloc>::~node_constructor() { if (node_) { boost::unordered::detail::func::destroy(boost::to_address(node_)); node_allocator_traits::deallocate(alloc_, node_, 1); } } template <typename Alloc> void node_constructor<Alloc>::create_node() { BOOST_ASSERT(!node_); node_ = node_allocator_traits::allocate(alloc_, 1); new ((void*)boost::to_address(node_)) node(); } template <typename NodeAlloc> struct node_tmp { typedef boost::unordered::detail::allocator_traits<NodeAlloc> node_allocator_traits; typedef typename node_allocator_traits::pointer node_pointer; typedef typename node_allocator_traits::value_type node; NodeAlloc& alloc_; node_pointer node_; explicit node_tmp(node_pointer n, NodeAlloc& a) : alloc_(a), node_(n) {} ~node_tmp(); // no throw node_pointer release() { node_pointer p = node_; node_ = node_pointer(); return p; } }; template <typename Alloc> node_tmp<Alloc>::~node_tmp() { if (node_) { BOOST_UNORDERED_CALL_DESTROY( node_allocator_traits, alloc_, node_->value_ptr()); boost::unordered::detail::func::destroy(boost::to_address(node_)); node_allocator_traits::deallocate(alloc_, node_, 1); } } } } } namespace boost { namespace unordered { namespace detail { namespace func { // Some nicer construct_node functions, might try to // improve implementation later. template <typename Alloc, BOOST_UNORDERED_EMPLACE_TEMPLATE> inline typename boost::unordered::detail::allocator_traits<Alloc>::pointer construct_node_from_args(Alloc& alloc, BOOST_UNORDERED_EMPLACE_ARGS) { node_constructor<Alloc> a(alloc); a.create_node(); construct_from_args( alloc, a.node_->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD); return a.release(); } template <typename Alloc, typename U> inline typename boost::unordered::detail::allocator_traits<Alloc>::pointer construct_node(Alloc& alloc, BOOST_FWD_REF(U) x) { node_constructor<Alloc> a(alloc); a.create_node(); BOOST_UNORDERED_CALL_CONSTRUCT1( boost::unordered::detail::allocator_traits<Alloc>, alloc, a.node_->value_ptr(), boost::forward<U>(x)); return a.release(); } #if BOOST_UNORDERED_CXX11_CONSTRUCTION template <typename Alloc, typename Key> inline typename boost::unordered::detail::allocator_traits<Alloc>::pointer construct_node_pair(Alloc& alloc, BOOST_FWD_REF(Key) k) { node_constructor<Alloc> a(alloc); a.create_node(); boost::unordered::detail::allocator_traits<Alloc>::construct(alloc, a.node_->value_ptr(), std::piecewise_construct, std::forward_as_tuple(boost::forward<Key>(k)), std::forward_as_tuple()); return a.release(); } template <typename Alloc, typename Key, typename Mapped> inline typename boost::unordered::detail::allocator_traits<Alloc>::pointer construct_node_pair( Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_FWD_REF(Mapped) m) { node_constructor<Alloc> a(alloc); a.create_node(); boost::unordered::detail::allocator_traits<Alloc>::construct(alloc, a.node_->value_ptr(), std::piecewise_construct, std::forward_as_tuple(boost::forward<Key>(k)), std::forward_as_tuple(boost::forward<Mapped>(m))); return a.release(); } template <typename Alloc, typename Key, typename... Args> inline typename boost::unordered::detail::allocator_traits<Alloc>::pointer construct_node_pair_from_args( Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_FWD_REF(Args)... args) { node_constructor<Alloc> a(alloc); a.create_node(); #if !(BOOST_COMP_CLANG && BOOST_COMP_CLANG < BOOST_VERSION_NUMBER(3, 8, 0) && \ defined(BOOST_LIBSTDCXX11)) boost::unordered::detail::allocator_traits<Alloc>::construct(alloc, a.node_->value_ptr(), std::piecewise_construct, std::forward_as_tuple(boost::forward<Key>(k)), std::forward_as_tuple(boost::forward<Args>(args)...)); #else // It doesn't seem to be possible to construct a tuple with 3 variadic // rvalue reference members when using older versions of clang with // libstdc++, so just use std::make_tuple instead of // std::forward_as_tuple. boost::unordered::detail::allocator_traits<Alloc>::construct(alloc, a.node_->value_ptr(), std::piecewise_construct, std::forward_as_tuple(boost::forward<Key>(k)), std::make_tuple(boost::forward<Args>(args)...)); #endif return a.release(); } #else template <typename Alloc, typename Key> inline typename boost::unordered::detail::allocator_traits<Alloc>::pointer construct_node_pair(Alloc& alloc, BOOST_FWD_REF(Key) k) { node_constructor<Alloc> a(alloc); a.create_node(); boost::unordered::detail::func::construct_value( boost::addressof(a.node_->value_ptr()->first), boost::forward<Key>(k)); BOOST_TRY { boost::unordered::detail::func::construct_value( boost::addressof(a.node_->value_ptr()->second)); } BOOST_CATCH(...) { boost::unordered::detail::func::destroy( boost::addressof(a.node_->value_ptr()->first)); BOOST_RETHROW } BOOST_CATCH_END return a.release(); } template <typename Alloc, typename Key, typename Mapped> inline typename boost::unordered::detail::allocator_traits<Alloc>::pointer construct_node_pair( Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_FWD_REF(Mapped) m) { node_constructor<Alloc> a(alloc); a.create_node(); boost::unordered::detail::func::construct_value( boost::addressof(a.node_->value_ptr()->first), boost::forward<Key>(k)); BOOST_TRY { boost::unordered::detail::func::construct_value( boost::addressof(a.node_->value_ptr()->second), boost::forward<Mapped>(m)); } BOOST_CATCH(...) { boost::unordered::detail::func::destroy( boost::addressof(a.node_->value_ptr()->first)); BOOST_RETHROW } BOOST_CATCH_END return a.release(); } template <typename Alloc, typename Key, BOOST_UNORDERED_EMPLACE_TEMPLATE> inline typename boost::unordered::detail::allocator_traits<Alloc>::pointer construct_node_pair_from_args( Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_UNORDERED_EMPLACE_ARGS) { node_constructor<Alloc> a(alloc); a.create_node(); boost::unordered::detail::func::construct_value( boost::addressof(a.node_->value_ptr()->first), boost::forward<Key>(k)); BOOST_TRY { boost::unordered::detail::func::construct_from_args(alloc, boost::addressof(a.node_->value_ptr()->second), BOOST_UNORDERED_EMPLACE_FORWARD); } BOOST_CATCH(...) { boost::unordered::detail::func::destroy( boost::addressof(a.node_->value_ptr()->first)); BOOST_RETHROW } BOOST_CATCH_END return a.release(); } #endif } } } } #if defined(BOOST_MSVC) #pragma warning(pop) #endif // The 'iterator_detail' namespace was a misguided attempt at avoiding ADL // in the detail namespace. It didn't work because the template parameters // were in detail. I'm not changing it at the moment to be safe. I might // do in the future if I change the iterator types. namespace boost { namespace unordered { namespace iterator_detail { ////////////////////////////////////////////////////////////////////////// // Iterators // // all no throw template <typename Node> struct l_iterator { #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) template <typename Node2> friend struct boost::unordered::iterator_detail::cl_iterator; private: #endif typedef typename Node::node_pointer node_pointer; node_pointer ptr_; std::size_t bucket_; std::size_t bucket_count_; public: typedef typename Node::value_type element_type; typedef typename Node::value_type value_type; typedef value_type* pointer; typedef value_type& reference; typedef std::ptrdiff_t difference_type; typedef std::forward_iterator_tag iterator_category; l_iterator() BOOST_NOEXCEPT : ptr_() {} l_iterator(node_pointer n, std::size_t b, std::size_t c) BOOST_NOEXCEPT : ptr_(n), bucket_(b), bucket_count_(c) { } value_type& operator*() const { return ptr_->value(); } value_type* operator->() const { return ptr_->value_ptr(); } l_iterator& operator++() { ptr_ = static_cast<node_pointer>(ptr_->next_); if (ptr_ && ptr_->get_bucket() != bucket_) ptr_ = node_pointer(); return *this; } l_iterator operator++(int) { l_iterator tmp(*this); ++(*this); return tmp; } bool operator==(l_iterator x) const BOOST_NOEXCEPT { return ptr_ == x.ptr_; } bool operator!=(l_iterator x) const BOOST_NOEXCEPT { return ptr_ != x.ptr_; } }; template <typename Node> struct cl_iterator { friend struct boost::unordered::iterator_detail::l_iterator<Node>; private: typedef typename Node::node_pointer node_pointer; node_pointer ptr_; std::size_t bucket_; std::size_t bucket_count_; public: typedef typename Node::value_type const element_type; typedef typename Node::value_type value_type; typedef value_type const* pointer; typedef value_type const& reference; typedef std::ptrdiff_t difference_type; typedef std::forward_iterator_tag iterator_category; cl_iterator() BOOST_NOEXCEPT : ptr_() {} cl_iterator(node_pointer n, std::size_t b, std::size_t c) BOOST_NOEXCEPT : ptr_(n), bucket_(b), bucket_count_(c) { } cl_iterator( boost::unordered::iterator_detail::l_iterator<Node> const& x) BOOST_NOEXCEPT : ptr_(x.ptr_), bucket_(x.bucket_), bucket_count_(x.bucket_count_) { } value_type const& operator*() const { return ptr_->value(); } value_type const* operator->() const { return ptr_->value_ptr(); } cl_iterator& operator++() { ptr_ = static_cast<node_pointer>(ptr_->next_); if (ptr_ && ptr_->get_bucket() != bucket_) ptr_ = node_pointer(); return *this; } cl_iterator operator++(int) { cl_iterator tmp(*this); ++(*this); return tmp; } friend bool operator==( cl_iterator const& x, cl_iterator const& y) BOOST_NOEXCEPT { return x.ptr_ == y.ptr_; } friend bool operator!=( cl_iterator const& x, cl_iterator const& y) BOOST_NOEXCEPT { return x.ptr_ != y.ptr_; } }; template <typename Node> struct iterator { #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) template <typename> friend struct boost::unordered::iterator_detail::c_iterator; template <typename> friend struct boost::unordered::detail::table; private: #endif typedef typename Node::node_pointer node_pointer; node_pointer node_; public: typedef typename Node::value_type element_type; typedef typename Node::value_type value_type; typedef value_type* pointer; typedef value_type& reference; typedef std::ptrdiff_t difference_type; typedef std::forward_iterator_tag iterator_category; iterator() BOOST_NOEXCEPT : node_() {} explicit iterator(typename Node::link_pointer x) BOOST_NOEXCEPT : node_(static_cast<node_pointer>(x)) { } value_type& operator*() const { return node_->value(); } value_type* operator->() const { return node_->value_ptr(); } iterator& operator++() { node_ = static_cast<node_pointer>(node_->next_); return *this; } iterator operator++(int) { iterator tmp(node_); node_ = static_cast<node_pointer>(node_->next_); return tmp; } bool operator==(iterator const& x) const BOOST_NOEXCEPT { return node_ == x.node_; } bool operator!=(iterator const& x) const BOOST_NOEXCEPT { return node_ != x.node_; } }; template <typename Node> struct c_iterator { friend struct boost::unordered::iterator_detail::iterator<Node>; #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) template <typename> friend struct boost::unordered::detail::table; private: #endif typedef typename Node::node_pointer node_pointer; typedef boost::unordered::iterator_detail::iterator<Node> n_iterator; node_pointer node_; public: typedef typename Node::value_type const element_type; typedef typename Node::value_type value_type; typedef value_type const* pointer; typedef value_type const& reference; typedef std::ptrdiff_t difference_type; typedef std::forward_iterator_tag iterator_category; c_iterator() BOOST_NOEXCEPT : node_() {} explicit c_iterator(typename Node::link_pointer x) BOOST_NOEXCEPT : node_(static_cast<node_pointer>(x)) { } c_iterator(n_iterator const& x) BOOST_NOEXCEPT : node_(x.node_) {} value_type const& operator*() const { return node_->value(); } value_type const* operator->() const { return node_->value_ptr(); } c_iterator& operator++() { node_ = static_cast<node_pointer>(node_->next_); return *this; } c_iterator operator++(int) { c_iterator tmp(node_); node_ = static_cast<node_pointer>(node_->next_); return tmp; } friend bool operator==( c_iterator const& x, c_iterator const& y) BOOST_NOEXCEPT { return x.node_ == y.node_; } friend bool operator!=( c_iterator const& x, c_iterator const& y) BOOST_NOEXCEPT { return x.node_ != y.node_; } }; } } } namespace boost { namespace unordered { namespace detail { /////////////////////////////////////////////////////////////////// // // Node Holder // // Temporary store for nodes. Deletes any that aren't used. template <typename NodeAlloc> struct node_holder { private: typedef NodeAlloc node_allocator; typedef boost::unordered::detail::allocator_traits<NodeAlloc> node_allocator_traits; typedef typename node_allocator_traits::value_type node; typedef typename node_allocator_traits::pointer node_pointer; typedef typename node::value_type value_type; typedef typename node::link_pointer link_pointer; typedef boost::unordered::iterator_detail::iterator<node> iterator; node_constructor<NodeAlloc> constructor_; node_pointer nodes_; public: template <typename Table> explicit node_holder(Table& b) : constructor_(b.node_alloc()), nodes_() { if (b.size_) { typename Table::link_pointer prev = b.get_previous_start(); nodes_ = static_cast<node_pointer>(prev->next_); prev->next_ = link_pointer(); b.size_ = 0; } } ~node_holder(); node_pointer pop_node() { node_pointer n = nodes_; nodes_ = static_cast<node_pointer>(nodes_->next_); n->next_ = link_pointer(); return n; } template <typename T> inline node_pointer copy_of(T const& v) { if (nodes_) { constructor_.reclaim(pop_node()); } else { constructor_.create_node(); } BOOST_UNORDERED_CALL_CONSTRUCT1(node_allocator_traits, constructor_.alloc_, constructor_.node_->value_ptr(), v); return constructor_.release(); } template <typename T> inline node_pointer move_copy_of(T& v) { if (nodes_) { constructor_.reclaim(pop_node()); } else { constructor_.create_node(); } BOOST_UNORDERED_CALL_CONSTRUCT1(node_allocator_traits, constructor_.alloc_, constructor_.node_->value_ptr(), boost::move(v)); return constructor_.release(); } iterator begin() const { return iterator(nodes_); } }; template <typename Alloc> node_holder<Alloc>::~node_holder() { while (nodes_) { node_pointer p = nodes_; nodes_ = static_cast<node_pointer>(p->next_); BOOST_UNORDERED_CALL_DESTROY( node_allocator_traits, constructor_.alloc_, p->value_ptr()); boost::unordered::detail::func::destroy(boost::to_address(p)); node_allocator_traits::deallocate(constructor_.alloc_, p, 1); } } /////////////////////////////////////////////////////////////////// // // Bucket template <typename NodePointer> struct bucket { typedef NodePointer link_pointer; link_pointer next_; bucket() : next_() {} bucket(link_pointer n) : next_(n) {} link_pointer first_from_start() { return next_; } enum { extra_node = true }; }; struct ptr_bucket { typedef ptr_bucket* link_pointer; link_pointer next_; ptr_bucket() : next_(0) {} ptr_bucket(link_pointer n) : next_(n) {} link_pointer first_from_start() { return this; } enum { extra_node = false }; }; /////////////////////////////////////////////////////////////////// // // Hash Policy template <typename SizeT> struct prime_policy { template <typename Hash, typename T> static inline SizeT apply_hash(Hash const& hf, T const& x) { return hf(x); } static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) { return hash % bucket_count; } static inline SizeT new_bucket_count(SizeT min) { return boost::unordered::detail::next_prime(min); } static inline SizeT prev_bucket_count(SizeT max) { return boost::unordered::detail::prev_prime(max); } }; template <typename SizeT> struct mix64_policy { template <typename Hash, typename T> static inline SizeT apply_hash(Hash const& hf, T const& x) { SizeT key = hf(x); key = (~key) + (key << 21); // key = (key << 21) - key - 1; key = key ^ (key >> 24); key = (key + (key << 3)) + (key << 8); // key * 265 key = key ^ (key >> 14); key = (key + (key << 2)) + (key << 4); // key * 21 key = key ^ (key >> 28); key = key + (key << 31); return key; } static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) { return hash & (bucket_count - 1); } static inline SizeT new_bucket_count(SizeT min) { if (min <= 4) return 4; --min; min |= min >> 1; min |= min >> 2; min |= min >> 4; min |= min >> 8; min |= min >> 16; min |= min >> 32; return min + 1; } static inline SizeT prev_bucket_count(SizeT max) { max |= max >> 1; max |= max >> 2; max |= max >> 4; max |= max >> 8; max |= max >> 16; max |= max >> 32; return (max >> 1) + 1; } }; template <int digits, int radix> struct pick_policy_impl { typedef prime_policy<std::size_t> type; }; template <> struct pick_policy_impl<64, 2> { typedef mix64_policy<std::size_t> type; }; template <typename T> struct pick_policy2 : pick_policy_impl<std::numeric_limits<std::size_t>::digits, std::numeric_limits<std::size_t>::radix> { }; // While the mix policy is generally faster, the prime policy is a lot // faster when a large number consecutive integers are used, because // there are no collisions. Since that is probably quite common, use // prime policy for integeral types. But not the smaller ones, as they // don't have enough unique values for this to be an issue. template <> struct pick_policy2<int> { typedef prime_policy<std::size_t> type; }; template <> struct pick_policy2<unsigned int> { typedef prime_policy<std::size_t> type; }; template <> struct pick_policy2<long> { typedef prime_policy<std::size_t> type; }; template <> struct pick_policy2<unsigned long> { typedef prime_policy<std::size_t> type; }; #if !defined(BOOST_NO_LONG_LONG) template <> struct pick_policy2<boost::long_long_type> { typedef prime_policy<std::size_t> type; }; template <> struct pick_policy2<boost::ulong_long_type> { typedef prime_policy<std::size_t> type; }; #endif template <typename T> struct pick_policy : pick_policy2<typename boost::remove_cv<T>::type> { }; ////////////////////////////////////////////////////////////////////////// // Functions // // This double buffers the storage for the hash function and key equality // predicate in order to have exception safe copy/swap. To do so, // use 'construct_spare' to construct in the spare space, and then when // ready to use 'switch_functions' to switch to the new functions. // If an exception is thrown between these two calls, use // 'cleanup_spare_functions' to destroy the unused constructed functions. template <class H, class P> class functions { public: static const bool nothrow_move_assignable = boost::is_nothrow_move_assignable<H>::value && boost::is_nothrow_move_assignable<P>::value; static const bool nothrow_move_constructible = boost::is_nothrow_move_constructible<H>::value && boost::is_nothrow_move_constructible<P>::value; static const bool nothrow_swappable = boost::is_nothrow_swappable<H>::value && boost::is_nothrow_swappable<P>::value; private: functions& operator=(functions const&); typedef compressed<H, P> function_pair; typedef typename boost::aligned_storage<sizeof(function_pair), boost::alignment_of<function_pair>::value>::type aligned_function; unsigned char current_; // 0/1 - Currently active functions // +2 - Both constructed aligned_function funcs_[2]; public: functions(H const& hf, P const& eq) : current_(0) { construct_functions(current_, hf, eq); } functions(functions const& bf) : current_(0) { construct_functions(current_, bf.current_functions()); } functions(functions& bf, boost::unordered::detail::move_tag) : current_(0) { construct_functions(current_, bf.current_functions(), boost::unordered::detail::integral_constant<bool, nothrow_move_constructible>()); } ~functions() { BOOST_ASSERT(!(current_ & 2)); destroy_functions(current_); } H const& hash_function() const { return current_functions().first(); } P const& key_eq() const { return current_functions().second(); } function_pair const& current_functions() const { return *static_cast<function_pair const*>( static_cast<void const*>(funcs_[current_ & 1].address())); } function_pair& current_functions() { return *static_cast<function_pair*>( static_cast<void*>(funcs_[current_ & 1].address())); } void construct_spare_functions(function_pair const& f) { BOOST_ASSERT(!(current_ & 2)); construct_functions(current_ ^ 1, f); current_ |= 2; } void cleanup_spare_functions() { if (current_ & 2) { current_ = static_cast<unsigned char>(current_ & 1); destroy_functions(current_ ^ 1); } } void switch_functions() { BOOST_ASSERT(current_ & 2); destroy_functions(static_cast<unsigned char>(current_ & 1)); current_ ^= 3; } private: void construct_functions(unsigned char which, H const& hf, P const& eq) { BOOST_ASSERT(!(which & 2)); new ((void*)&funcs_[which]) function_pair(hf, eq); } void construct_functions(unsigned char which, function_pair const& f, boost::unordered::detail::false_type = boost::unordered::detail::false_type()) { BOOST_ASSERT(!(which & 2)); new ((void*)&funcs_[which]) function_pair(f); } void construct_functions(unsigned char which, function_pair& f, boost::unordered::detail::true_type) { BOOST_ASSERT(!(which & 2)); new ((void*)&funcs_[which]) function_pair(f, boost::unordered::detail::move_tag()); } void destroy_functions(unsigned char which) { BOOST_ASSERT(!(which & 2)); boost::unordered::detail::func::destroy( (function_pair*)(&funcs_[which])); } }; //////////////////////////////////////////////////////////////////////////// // rvalue parameters when type can't be a BOOST_RV_REF(T) parameter // e.g. for int #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) #define BOOST_UNORDERED_RV_REF(T) BOOST_RV_REF(T) #else struct please_ignore_this_overload { typedef please_ignore_this_overload type; }; template <typename T> struct rv_ref_impl { typedef BOOST_RV_REF(T) type; }; template <typename T> struct rv_ref : boost::detail::if_true<boost::is_class<T>::value>:: BOOST_NESTED_TEMPLATE then<boost::unordered::detail::rv_ref_impl<T>, please_ignore_this_overload>::type { }; #define BOOST_UNORDERED_RV_REF(T) \ typename boost::unordered::detail::rv_ref<T>::type #endif #if defined(BOOST_MSVC) #pragma warning(push) #pragma warning(disable : 4127) // conditional expression is constant #endif ////////////////////////////////////////////////////////////////////////// // convert double to std::size_t inline std::size_t double_to_size(double f) { return f >= static_cast<double>( (std::numeric_limits<std::size_t>::max)()) ? (std::numeric_limits<std::size_t>::max)() : static_cast<std::size_t>(f); } template <typename Types> struct table : boost::unordered::detail::functions<typename Types::hasher, typename Types::key_equal> { private: table(table const&); table& operator=(table const&); public: typedef typename Types::node node; typedef typename Types::bucket bucket; typedef typename Types::hasher hasher; typedef typename Types::key_equal key_equal; typedef typename Types::const_key_type const_key_type; typedef typename Types::extractor extractor; typedef typename Types::value_type value_type; typedef typename Types::table table_impl; typedef typename Types::link_pointer link_pointer; typedef typename Types::policy policy; typedef typename Types::iterator iterator; typedef typename Types::c_iterator c_iterator; typedef typename Types::l_iterator l_iterator; typedef typename Types::cl_iterator cl_iterator; typedef boost::unordered::detail::functions<typename Types::hasher, typename Types::key_equal> functions; typedef typename Types::value_allocator value_allocator; typedef typename boost::unordered::detail::rebind_wrap<value_allocator, node>::type node_allocator; typedef typename boost::unordered::detail::rebind_wrap<value_allocator, bucket>::type bucket_allocator; typedef boost::unordered::detail::allocator_traits<node_allocator> node_allocator_traits; typedef boost::unordered::detail::allocator_traits<bucket_allocator> bucket_allocator_traits; typedef typename node_allocator_traits::pointer node_pointer; typedef typename node_allocator_traits::const_pointer const_node_pointer; typedef typename bucket_allocator_traits::pointer bucket_pointer; typedef boost::unordered::detail::node_constructor<node_allocator> node_constructor; typedef boost::unordered::detail::node_tmp<node_allocator> node_tmp; typedef std::pair<iterator, bool> emplace_return; //////////////////////////////////////////////////////////////////////// // Members boost::unordered::detail::compressed<bucket_allocator, node_allocator> allocators_; std::size_t bucket_count_; std::size_t size_; float mlf_; std::size_t max_load_; bucket_pointer buckets_; //////////////////////////////////////////////////////////////////////// // Data access static node_pointer get_node(c_iterator it) { return it.node_; } static node_pointer next_node(link_pointer n) { return static_cast<node_pointer>(n->next_); } static node_pointer next_for_find(link_pointer n) { node_pointer n2 = static_cast<node_pointer>(n); do { n2 = next_node(n2); } while (n2 && !n2->is_first_in_group()); return n2; } node_pointer next_group(node_pointer n) const { node_pointer n1 = n; do { n1 = next_node(n1); } while (n1 && !n1->is_first_in_group()); return n1; } std::size_t group_count(node_pointer n) const { std::size_t x = 0; node_pointer it = n; do { ++x; it = next_node(it); } while (it && !it->is_first_in_group()); return x; } std::size_t node_bucket(node_pointer n) const { return n->get_bucket(); } bucket_allocator const& bucket_alloc() const { return allocators_.first(); } node_allocator const& node_alloc() const { return allocators_.second(); } bucket_allocator& bucket_alloc() { return allocators_.first(); } node_allocator& node_alloc() { return allocators_.second(); } std::size_t max_bucket_count() const { // -1 to account for the start bucket. return policy::prev_bucket_count( bucket_allocator_traits::max_size(bucket_alloc()) - 1); } bucket_pointer get_bucket_pointer(std::size_t bucket_index) const { BOOST_ASSERT(buckets_); return buckets_ + static_cast<std::ptrdiff_t>(bucket_index); } link_pointer get_previous_start() const { return get_bucket_pointer(bucket_count_)->first_from_start(); } link_pointer get_previous_start(std::size_t bucket_index) const { return get_bucket_pointer(bucket_index)->next_; } node_pointer begin() const { return size_ ? next_node(get_previous_start()) : node_pointer(); } node_pointer begin(std::size_t bucket_index) const { if (!size_) return node_pointer(); link_pointer prev = get_previous_start(bucket_index); return prev ? next_node(prev) : node_pointer(); } std::size_t hash_to_bucket(std::size_t hash_value) const { return policy::to_bucket(bucket_count_, hash_value); } std::size_t bucket_size(std::size_t index) const { node_pointer n = begin(index); if (!n) return 0; std::size_t count = 0; while (n && node_bucket(n) == index) { ++count; n = next_node(n); } return count; } //////////////////////////////////////////////////////////////////////// // Load methods void recalculate_max_load() { using namespace std; // From 6.3.1/13: // Only resize when size >= mlf_ * count max_load_ = buckets_ ? boost::unordered::detail::double_to_size( ceil(static_cast<double>(mlf_) * static_cast<double>(bucket_count_))) : 0; } void max_load_factor(float z) { BOOST_ASSERT(z > 0); mlf_ = (std::max)(z, minimum_max_load_factor); recalculate_max_load(); } std::size_t min_buckets_for_size(std::size_t size) const { BOOST_ASSERT(mlf_ >= minimum_max_load_factor); using namespace std; // From insert/emplace requirements: // // size <= mlf_ * count // => count >= size / mlf_ // // Or from rehash post-condition: // // count >= size / mlf_ return policy::new_bucket_count( boost::unordered::detail::double_to_size( floor(static_cast<double>(size) / static_cast<double>(mlf_)) + 1)); } //////////////////////////////////////////////////////////////////////// // Constructors table(std::size_t num_buckets, hasher const& hf, key_equal const& eq, node_allocator const& a) : functions(hf, eq), allocators_(a, a), bucket_count_(policy::new_bucket_count(num_buckets)), size_(0), mlf_(1.0f), max_load_(0), buckets_() { } table(table const& x, node_allocator const& a) : functions(x), allocators_(a, a), bucket_count_(x.min_buckets_for_size(x.size_)), size_(0), mlf_(x.mlf_), max_load_(0), buckets_() { } table(table& x, boost::unordered::detail::move_tag m) : functions(x, m), allocators_(x.allocators_, m), bucket_count_(x.bucket_count_), size_(x.size_), mlf_(x.mlf_), max_load_(x.max_load_), buckets_(x.buckets_) { x.buckets_ = bucket_pointer(); x.size_ = 0; x.max_load_ = 0; } table(table& x, node_allocator const& a, boost::unordered::detail::move_tag m) : functions(x, m), allocators_(a, a), bucket_count_(x.bucket_count_), size_(0), mlf_(x.mlf_), max_load_(0), buckets_() { } //////////////////////////////////////////////////////////////////////// // Clear buckets and Create buckets // // IMPORTANT: If the container already contains any elements, the // buckets will not contain any links to them. This will // need to be dealt with, for example by: // - deleting them // - putting them in a 'node_holder' for future use // (as in assignment) // - placing them in buckets (see rehash_impl) // Clear the bucket pointers. void clear_buckets() { bucket_pointer end = get_bucket_pointer(bucket_count_); for (bucket_pointer it = buckets_; it != end; ++it) { it->next_ = node_pointer(); } } // Create container buckets. If the container already contains any // buckets // the linked list will be transferred to the new buckets, but none // of the bucket pointers will be set. See above note. // // Strong exception safety. void create_buckets(std::size_t new_count) { link_pointer dummy_node; // Construct the new buckets and dummy node, and destroy the old // buckets if (buckets_) { dummy_node = (buckets_ + static_cast<std::ptrdiff_t>(bucket_count_))->next_; bucket_pointer new_buckets = bucket_allocator_traits::allocate(bucket_alloc(), new_count + 1); destroy_buckets(); buckets_ = new_buckets; } else if (bucket::extra_node) { node_constructor a(node_alloc()); a.create_node(); buckets_ = bucket_allocator_traits::allocate(bucket_alloc(), new_count + 1); dummy_node = a.release(); } else { dummy_node = link_pointer(); buckets_ = bucket_allocator_traits::allocate(bucket_alloc(), new_count + 1); } // nothrow from here... bucket_count_ = new_count; recalculate_max_load(); bucket_pointer end = buckets_ + static_cast<std::ptrdiff_t>(new_count); for (bucket_pointer i = buckets_; i != end; ++i) { new ((void*)boost::to_address(i)) bucket(); } new ((void*)boost::to_address(end)) bucket(dummy_node); } //////////////////////////////////////////////////////////////////////// // Swap and Move void swap_allocators(table& other, false_type) { boost::unordered::detail::func::ignore_unused_variable_warning(other); // According to 23.2.1.8, if propagate_on_container_swap is // false the behaviour is undefined unless the allocators // are equal. BOOST_ASSERT(node_alloc() == other.node_alloc()); } void swap_allocators(table& other, true_type) { allocators_.swap(other.allocators_); } // Not nothrow swappable void swap(table& x, false_type) { if (this == &x) { return; } this->construct_spare_functions(x.current_functions()); BOOST_TRY { x.construct_spare_functions(this->current_functions()); } BOOST_CATCH(...) { this->cleanup_spare_functions(); BOOST_RETHROW } BOOST_CATCH_END this->switch_functions(); x.switch_functions(); swap_allocators( x, boost::unordered::detail::integral_constant<bool, allocator_traits< node_allocator>::propagate_on_container_swap::value>()); boost::swap(buckets_, x.buckets_); boost::swap(bucket_count_, x.bucket_count_); boost::swap(size_, x.size_); std::swap(mlf_, x.mlf_); std::swap(max_load_, x.max_load_); } // Nothrow swappable void swap(table& x, true_type) { swap_allocators( x, boost::unordered::detail::integral_constant<bool, allocator_traits< node_allocator>::propagate_on_container_swap::value>()); boost::swap(buckets_, x.buckets_); boost::swap(bucket_count_, x.bucket_count_); boost::swap(size_, x.size_); std::swap(mlf_, x.mlf_); std::swap(max_load_, x.max_load_); this->current_functions().swap(x.current_functions()); } // Only swaps the allocators if propagate_on_container_swap. // If not propagate_on_container_swap and allocators aren't // equal, behaviour is undefined. void swap(table& x) { BOOST_ASSERT(allocator_traits< node_allocator>::propagate_on_container_swap::value || node_alloc() == x.node_alloc()); swap(x, boost::unordered::detail::integral_constant<bool, functions::nothrow_swappable>()); } // Only call with nodes allocated with the currect allocator, or // one that is equal to it. (Can't assert because other's // allocators might have already been moved). void move_buckets_from(table& other) { BOOST_ASSERT(!buckets_); buckets_ = other.buckets_; bucket_count_ = other.bucket_count_; size_ = other.size_; max_load_ = other.max_load_; other.buckets_ = bucket_pointer(); other.size_ = 0; other.max_load_ = 0; } // For use in the constructor when allocators might be different. void move_construct_buckets(table& src) { if (this->node_alloc() == src.node_alloc()) { move_buckets_from(src); } else { this->create_buckets(this->bucket_count_); link_pointer prev = this->get_previous_start(); std::size_t last_bucket = this->bucket_count_; for (node_pointer n = src.begin(); n; n = next_node(n)) { std::size_t n_bucket = n->get_bucket(); if (n_bucket != last_bucket) { this->get_bucket_pointer(n_bucket)->next_ = prev; } node_pointer n2 = boost::unordered::detail::func::construct_node( this->node_alloc(), boost::move(n->value())); n2->bucket_info_ = n->bucket_info_; prev->next_ = n2; ++size_; prev = n2; last_bucket = n_bucket; } } } //////////////////////////////////////////////////////////////////////// // Delete/destruct ~table() { delete_buckets(); } void destroy_node(node_pointer n) { BOOST_UNORDERED_CALL_DESTROY( node_allocator_traits, node_alloc(), n->value_ptr()); boost::unordered::detail::func::destroy(boost::to_address(n)); node_allocator_traits::deallocate(node_alloc(), n, 1); } void delete_buckets() { if (buckets_) { node_pointer n = static_cast<node_pointer>( get_bucket_pointer(bucket_count_)->next_); if (bucket::extra_node) { node_pointer next = next_node(n); boost::unordered::detail::func::destroy(boost::to_address(n)); node_allocator_traits::deallocate(node_alloc(), n, 1); n = next; } while (n) { node_pointer next = next_node(n); destroy_node(n); n = next; } destroy_buckets(); buckets_ = bucket_pointer(); max_load_ = 0; size_ = 0; } } void destroy_buckets() { bucket_pointer end = get_bucket_pointer(bucket_count_ + 1); for (bucket_pointer it = buckets_; it != end; ++it) { boost::unordered::detail::func::destroy(boost::to_address(it)); } bucket_allocator_traits::deallocate( bucket_alloc(), buckets_, bucket_count_ + 1); } //////////////////////////////////////////////////////////////////////// // Fix buckets after delete/extract // // (prev,next) should mark an open range of nodes in a single bucket // which // have either been unlinked, or are about to be. std::size_t fix_bucket( std::size_t bucket_index, link_pointer prev, node_pointer next) { std::size_t bucket_index2 = bucket_index; if (next) { bucket_index2 = node_bucket(next); // If next is in the same bucket, then there's nothing to do. if (bucket_index == bucket_index2) { return bucket_index2; } // Update the bucket containing next. get_bucket_pointer(bucket_index2)->next_ = prev; } // Check if this bucket is now empty. bucket_pointer this_bucket = get_bucket_pointer(bucket_index); if (this_bucket->next_ == prev) { this_bucket->next_ = link_pointer(); } return bucket_index2; } //////////////////////////////////////////////////////////////////////// // Clear void clear_impl(); //////////////////////////////////////////////////////////////////////// // Assignment template <typename UniqueType> void assign(table const& x, UniqueType is_unique) { if (this != &x) { assign(x, is_unique, boost::unordered::detail::integral_constant<bool, allocator_traits<node_allocator>:: propagate_on_container_copy_assignment::value>()); } } template <typename UniqueType> void assign(table const& x, UniqueType is_unique, false_type) { // Strong exception safety. this->construct_spare_functions(x.current_functions()); BOOST_TRY { mlf_ = x.mlf_; recalculate_max_load(); if (x.size_ > max_load_) { create_buckets(min_buckets_for_size(x.size_)); } else if (size_) { clear_buckets(); } } BOOST_CATCH(...) { this->cleanup_spare_functions(); BOOST_RETHROW } BOOST_CATCH_END this->switch_functions(); assign_buckets(x, is_unique); } template <typename UniqueType> void assign(table const& x, UniqueType is_unique, true_type) { if (node_alloc() == x.node_alloc()) { allocators_.assign(x.allocators_); assign(x, is_unique, false_type()); } else { this->construct_spare_functions(x.current_functions()); this->switch_functions(); // Delete everything with current allocators before assigning // the new ones. delete_buckets(); allocators_.assign(x.allocators_); // Copy over other data, all no throw. mlf_ = x.mlf_; bucket_count_ = min_buckets_for_size(x.size_); // Finally copy the elements. if (x.size_) { copy_buckets(x, is_unique); } } } template <typename UniqueType> void move_assign(table& x, UniqueType is_unique) { if (this != &x) { move_assign(x, is_unique, boost::unordered::detail::integral_constant<bool, allocator_traits<node_allocator>:: propagate_on_container_move_assignment::value>()); } } // Propagate allocator template <typename UniqueType> void move_assign(table& x, UniqueType, true_type) { if (!functions::nothrow_move_assignable) { this->construct_spare_functions(x.current_functions()); this->switch_functions(); } else { this->current_functions().move_assign(x.current_functions()); } delete_buckets(); allocators_.move_assign(x.allocators_); mlf_ = x.mlf_; move_buckets_from(x); } // Don't propagate allocator template <typename UniqueType> void move_assign(table& x, UniqueType is_unique, false_type) { if (node_alloc() == x.node_alloc()) { move_assign_equal_alloc(x); } else { move_assign_realloc(x, is_unique); } } void move_assign_equal_alloc(table& x) { if (!functions::nothrow_move_assignable) { this->construct_spare_functions(x.current_functions()); this->switch_functions(); } else { this->current_functions().move_assign(x.current_functions()); } delete_buckets(); mlf_ = x.mlf_; move_buckets_from(x); } template <typename UniqueType> void move_assign_realloc(table& x, UniqueType is_unique) { this->construct_spare_functions(x.current_functions()); BOOST_TRY { mlf_ = x.mlf_; recalculate_max_load(); if (x.size_ > max_load_) { create_buckets(min_buckets_for_size(x.size_)); } else if (size_) { clear_buckets(); } } BOOST_CATCH(...) { this->cleanup_spare_functions(); BOOST_RETHROW } BOOST_CATCH_END this->switch_functions(); move_assign_buckets(x, is_unique); } // Accessors const_key_type& get_key(node_pointer n) const { return extractor::extract(n->value()); } std::size_t hash(const_key_type& k) const { return policy::apply_hash(this->hash_function(), k); } // Find Node node_pointer find_node(std::size_t key_hash, const_key_type& k) const { return this->find_node_impl(key_hash, k, this->key_eq()); } node_pointer find_node(const_key_type& k) const { return this->find_node_impl(hash(k), k, this->key_eq()); } template <class Key, class Pred> node_pointer find_node_impl( std::size_t key_hash, Key const& k, Pred const& eq) const { std::size_t bucket_index = this->hash_to_bucket(key_hash); node_pointer n = this->begin(bucket_index); for (;;) { if (!n) return n; if (eq(k, this->get_key(n))) { return n; } else if (this->node_bucket(n) != bucket_index) { return node_pointer(); } n = next_for_find(n); } } // Find the node before the key, so that it can be erased. link_pointer find_previous_node( const_key_type& k, std::size_t bucket_index) { link_pointer prev = this->get_previous_start(bucket_index); if (!prev) { return prev; } for (;;) { node_pointer n = next_node(prev); if (!n) { return link_pointer(); } else if (n->is_first_in_group()) { if (node_bucket(n) != bucket_index) { return link_pointer(); } else if (this->key_eq()(k, this->get_key(n))) { return prev; } } prev = n; } } // Extract and erase inline node_pointer extract_by_key(const_key_type& k) { if (!this->size_) { return node_pointer(); } std::size_t key_hash = this->hash(k); std::size_t bucket_index = this->hash_to_bucket(key_hash); link_pointer prev = this->find_previous_node(k, bucket_index); if (!prev) { return node_pointer(); } node_pointer n = next_node(prev); node_pointer n2 = next_node(n); if (n2) { n2->set_first_in_group(); } prev->next_ = n2; --this->size_; this->fix_bucket(bucket_index, prev, n2); n->next_ = link_pointer(); return n; } // Reserve and rehash void reserve_for_insert(std::size_t); void rehash(std::size_t); void reserve(std::size_t); void rehash_impl(std::size_t); //////////////////////////////////////////////////////////////////////// // Unique keys // equals bool equals_unique(table const& other) const { if (this->size_ != other.size_) return false; for (node_pointer n1 = this->begin(); n1; n1 = next_node(n1)) { node_pointer n2 = other.find_node(other.get_key(n1)); if (!n2 || n1->value() != n2->value()) return false; } return true; } // Emplace/Insert inline node_pointer add_node_unique( node_pointer n, std::size_t key_hash) { std::size_t bucket_index = this->hash_to_bucket(key_hash); bucket_pointer b = this->get_bucket_pointer(bucket_index); n->bucket_info_ = bucket_index; n->set_first_in_group(); if (!b->next_) { link_pointer start_node = this->get_previous_start(); if (start_node->next_) { this->get_bucket_pointer(node_bucket(next_node(start_node))) ->next_ = n; } b->next_ = start_node; n->next_ = start_node->next_; start_node->next_ = n; } else { n->next_ = b->next_->next_; b->next_->next_ = n; } ++this->size_; return n; } inline node_pointer resize_and_add_node_unique( node_pointer n, std::size_t key_hash) { node_tmp b(n, this->node_alloc()); this->reserve_for_insert(this->size_ + 1); return this->add_node_unique(b.release(), key_hash); } template <BOOST_UNORDERED_EMPLACE_TEMPLATE> iterator emplace_hint_unique( c_iterator hint, const_key_type& k, BOOST_UNORDERED_EMPLACE_ARGS) { if (hint.node_ && this->key_eq()(k, this->get_key(hint.node_))) { return iterator(hint.node_); } else { return emplace_unique(k, BOOST_UNORDERED_EMPLACE_FORWARD).first; } } template <BOOST_UNORDERED_EMPLACE_TEMPLATE> emplace_return emplace_unique( const_key_type& k, BOOST_UNORDERED_EMPLACE_ARGS) { std::size_t key_hash = this->hash(k); node_pointer pos = this->find_node(key_hash, k); if (pos) { return emplace_return(iterator(pos), false); } else { return emplace_return( iterator(this->resize_and_add_node_unique( boost::unordered::detail::func::construct_node_from_args( this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD), key_hash)), true); } } template <BOOST_UNORDERED_EMPLACE_TEMPLATE> iterator emplace_hint_unique( c_iterator hint, no_key, BOOST_UNORDERED_EMPLACE_ARGS) { node_tmp b(boost::unordered::detail::func::construct_node_from_args( this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD), this->node_alloc()); const_key_type& k = this->get_key(b.node_); if (hint.node_ && this->key_eq()(k, this->get_key(hint.node_))) { return iterator(hint.node_); } std::size_t key_hash = this->hash(k); node_pointer pos = this->find_node(key_hash, k); if (pos) { return iterator(pos); } else { return iterator( this->resize_and_add_node_unique(b.release(), key_hash)); } } template <BOOST_UNORDERED_EMPLACE_TEMPLATE> emplace_return emplace_unique(no_key, BOOST_UNORDERED_EMPLACE_ARGS) { node_tmp b(boost::unordered::detail::func::construct_node_from_args( this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD), this->node_alloc()); const_key_type& k = this->get_key(b.node_); std::size_t key_hash = this->hash(k); node_pointer pos = this->find_node(key_hash, k); if (pos) { return emplace_return(iterator(pos), false); } else { return emplace_return( iterator(this->resize_and_add_node_unique(b.release(), key_hash)), true); } } template <typename Key> emplace_return try_emplace_unique(BOOST_FWD_REF(Key) k) { std::size_t key_hash = this->hash(k); node_pointer pos = this->find_node(key_hash, k); if (pos) { return emplace_return(iterator(pos), false); } else { return emplace_return( iterator(this->resize_and_add_node_unique( boost::unordered::detail::func::construct_node_pair( this->node_alloc(), boost::forward<Key>(k)), key_hash)), true); } } template <typename Key> iterator try_emplace_hint_unique(c_iterator hint, BOOST_FWD_REF(Key) k) { if (hint.node_ && this->key_eq()(hint->first, k)) { return iterator(hint.node_); } else { return try_emplace_unique(k).first; } } template <typename Key, BOOST_UNORDERED_EMPLACE_TEMPLATE> emplace_return try_emplace_unique( BOOST_FWD_REF(Key) k, BOOST_UNORDERED_EMPLACE_ARGS) { std::size_t key_hash = this->hash(k); node_pointer pos = this->find_node(key_hash, k); if (pos) { return emplace_return(iterator(pos), false); } else { return emplace_return( iterator(this->resize_and_add_node_unique( boost::unordered::detail::func::construct_node_pair_from_args( this->node_alloc(), boost::forward<Key>(k), BOOST_UNORDERED_EMPLACE_FORWARD), key_hash)), true); } } template <typename Key, BOOST_UNORDERED_EMPLACE_TEMPLATE> iterator try_emplace_hint_unique( c_iterator hint, BOOST_FWD_REF(Key) k, BOOST_UNORDERED_EMPLACE_ARGS) { if (hint.node_ && this->key_eq()(hint->first, k)) { return iterator(hint.node_); } else { return try_emplace_unique(k, BOOST_UNORDERED_EMPLACE_FORWARD).first; } } template <typename Key, typename M> emplace_return insert_or_assign_unique( BOOST_FWD_REF(Key) k, BOOST_FWD_REF(M) obj) { std::size_t key_hash = this->hash(k); node_pointer pos = this->find_node(key_hash, k); if (pos) { pos->value().second = boost::forward<M>(obj); return emplace_return(iterator(pos), false); } else { return emplace_return( iterator(this->resize_and_add_node_unique( boost::unordered::detail::func::construct_node_pair( this->node_alloc(), boost::forward<Key>(k), boost::forward<M>(obj)), key_hash)), true); } } template <typename NodeType, typename InsertReturnType> void move_insert_node_type_unique( NodeType& np, InsertReturnType& result) { if (np) { const_key_type& k = this->get_key(np.ptr_); std::size_t key_hash = this->hash(k); node_pointer pos = this->find_node(key_hash, k); if (pos) { result.node = boost::move(np); result.position = iterator(pos); } else { this->reserve_for_insert(this->size_ + 1); result.position = iterator(this->add_node_unique(np.ptr_, key_hash)); result.inserted = true; np.ptr_ = node_pointer(); } } } template <typename NodeType> iterator move_insert_node_type_with_hint_unique( c_iterator hint, NodeType& np) { if (!np) { return iterator(); } const_key_type& k = this->get_key(np.ptr_); if (hint.node_ && this->key_eq()(k, this->get_key(hint.node_))) { return iterator(hint.node_); } std::size_t key_hash = this->hash(k); node_pointer pos = this->find_node(key_hash, k); if (!pos) { this->reserve_for_insert(this->size_ + 1); pos = this->add_node_unique(np.ptr_, key_hash); np.ptr_ = node_pointer(); } return iterator(pos); } template <typename Types2> void merge_unique(boost::unordered::detail::table<Types2>& other) { typedef boost::unordered::detail::table<Types2> other_table; BOOST_STATIC_ASSERT( (boost::is_same<node, typename other_table::node>::value)); BOOST_ASSERT(this->node_alloc() == other.node_alloc()); if (other.size_) { link_pointer prev = other.get_previous_start(); while (prev->next_) { node_pointer n = other_table::next_node(prev); const_key_type& k = this->get_key(n); std::size_t key_hash = this->hash(k); node_pointer pos = this->find_node(key_hash, k); if (pos) { prev = n; } else { this->reserve_for_insert(this->size_ + 1); node_pointer n2 = next_node(n); prev->next_ = n2; if (n2 && n->is_first_in_group()) { n2->set_first_in_group(); } --other.size_; other.fix_bucket(other.node_bucket(n), prev, n2); this->add_node_unique(n, key_hash); } } } } //////////////////////////////////////////////////////////////////////// // Insert range methods // // if hash function throws, or inserting > 1 element, basic exception // safety strong otherwise template <class InputIt> void insert_range_unique(const_key_type& k, InputIt i, InputIt j) { insert_range_unique2(k, i, j); while (++i != j) { // Note: can't use get_key as '*i' might not be value_type - it // could be a pair with first_types as key_type without const or // a different second_type. insert_range_unique2(extractor::extract(*i), i, j); } } template <class InputIt> void insert_range_unique2(const_key_type& k, InputIt i, InputIt j) { // No side effects in this initial code std::size_t key_hash = this->hash(k); node_pointer pos = this->find_node(key_hash, k); if (!pos) { node_tmp b(boost::unordered::detail::func::construct_node( this->node_alloc(), *i), this->node_alloc()); if (this->size_ + 1 > this->max_load_) this->reserve_for_insert( this->size_ + boost::unordered::detail::insert_size(i, j)); this->add_node_unique(b.release(), key_hash); } } template <class InputIt> void insert_range_unique(no_key, InputIt i, InputIt j) { node_constructor a(this->node_alloc()); do { if (!a.node_) { a.create_node(); } BOOST_UNORDERED_CALL_CONSTRUCT1( node_allocator_traits, a.alloc_, a.node_->value_ptr(), *i); node_tmp b(a.release(), a.alloc_); const_key_type& k = this->get_key(b.node_); std::size_t key_hash = this->hash(k); node_pointer pos = this->find_node(key_hash, k); if (pos) { a.reclaim(b.release()); } else { // reserve has basic exception safety if the hash function // throws, strong otherwise. this->reserve_for_insert(this->size_ + 1); this->add_node_unique(b.release(), key_hash); } } while (++i != j); } //////////////////////////////////////////////////////////////////////// // Extract inline node_pointer extract_by_iterator_unique(c_iterator i) { node_pointer n = i.node_; BOOST_ASSERT(n); std::size_t bucket_index = this->node_bucket(n); link_pointer prev = this->get_previous_start(bucket_index); while (prev->next_ != n) { prev = prev->next_; } node_pointer n2 = next_node(n); prev->next_ = n2; --this->size_; this->fix_bucket(bucket_index, prev, n2); n->next_ = link_pointer(); return n; } //////////////////////////////////////////////////////////////////////// // Erase // // no throw std::size_t erase_key_unique(const_key_type& k) { if (!this->size_) return 0; std::size_t key_hash = this->hash(k); std::size_t bucket_index = this->hash_to_bucket(key_hash); link_pointer prev = this->find_previous_node(k, bucket_index); if (!prev) return 0; node_pointer n = next_node(prev); node_pointer n2 = next_node(n); prev->next_ = n2; --size_; this->fix_bucket(bucket_index, prev, n2); this->destroy_node(n); return 1; } void erase_nodes_unique(node_pointer i, node_pointer j) { std::size_t bucket_index = this->node_bucket(i); // Find the node before i. link_pointer prev = this->get_previous_start(bucket_index); while (prev->next_ != i) prev = prev->next_; // Delete the nodes. prev->next_ = j; do { node_pointer next = next_node(i); destroy_node(i); --size_; bucket_index = this->fix_bucket(bucket_index, prev, next); i = next; } while (i != j); } //////////////////////////////////////////////////////////////////////// // fill_buckets_unique void copy_buckets(table const& src, true_type) { this->create_buckets(this->bucket_count_); for (node_pointer n = src.begin(); n; n = next_node(n)) { std::size_t key_hash = this->hash(this->get_key(n)); this->add_node_unique( boost::unordered::detail::func::construct_node( this->node_alloc(), n->value()), key_hash); } } void assign_buckets(table const& src, true_type) { node_holder<node_allocator> holder(*this); for (node_pointer n = src.begin(); n; n = next_node(n)) { std::size_t key_hash = this->hash(this->get_key(n)); this->add_node_unique(holder.copy_of(n->value()), key_hash); } } void move_assign_buckets(table& src, true_type) { node_holder<node_allocator> holder(*this); for (node_pointer n = src.begin(); n; n = next_node(n)) { std::size_t key_hash = this->hash(this->get_key(n)); this->add_node_unique(holder.move_copy_of(n->value()), key_hash); } } //////////////////////////////////////////////////////////////////////// // Equivalent keys // Equality bool equals_equiv(table const& other) const { if (this->size_ != other.size_) return false; for (node_pointer n1 = this->begin(); n1;) { node_pointer n2 = other.find_node(other.get_key(n1)); if (!n2) return false; node_pointer end1 = next_group(n1); node_pointer end2 = next_group(n2); if (!group_equals_equiv(n1, end1, n2, end2)) return false; n1 = end1; } return true; } static bool group_equals_equiv(node_pointer n1, node_pointer end1, node_pointer n2, node_pointer end2) { for (;;) { if (n1->value() != n2->value()) break; n1 = next_node(n1); n2 = next_node(n2); if (n1 == end1) return n2 == end2; if (n2 == end2) return false; } for (node_pointer n1a = n1, n2a = n2;;) { n1a = next_node(n1a); n2a = next_node(n2a); if (n1a == end1) { if (n2a == end2) break; else return false; } if (n2a == end2) return false; } node_pointer start = n1; for (; n1 != end1; n1 = next_node(n1)) { value_type const& v = n1->value(); if (!find_equiv(start, n1, v)) { std::size_t matches = count_equal_equiv(n2, end2, v); if (!matches) return false; if (matches != 1 + count_equal_equiv(next_node(n1), end1, v)) return false; } } return true; } static bool find_equiv( node_pointer n, node_pointer end, value_type const& v) { for (; n != end; n = next_node(n)) if (n->value() == v) return true; return false; } static std::size_t count_equal_equiv( node_pointer n, node_pointer end, value_type const& v) { std::size_t count = 0; for (; n != end; n = next_node(n)) if (n->value() == v) ++count; return count; } // Emplace/Insert inline node_pointer add_node_equiv( node_pointer n, std::size_t key_hash, node_pointer pos) { std::size_t bucket_index = this->hash_to_bucket(key_hash); n->bucket_info_ = bucket_index; if (pos) { n->reset_first_in_group(); n->next_ = pos->next_; pos->next_ = n; if (n->next_) { std::size_t next_bucket = this->node_bucket(next_node(n)); if (next_bucket != bucket_index) { this->get_bucket_pointer(next_bucket)->next_ = n; } } } else { n->set_first_in_group(); bucket_pointer b = this->get_bucket_pointer(bucket_index); if (!b->next_) { link_pointer start_node = this->get_previous_start(); if (start_node->next_) { this ->get_bucket_pointer(this->node_bucket(next_node(start_node))) ->next_ = n; } b->next_ = start_node; n->next_ = start_node->next_; start_node->next_ = n; } else { n->next_ = b->next_->next_; b->next_->next_ = n; } } ++this->size_; return n; } inline node_pointer add_using_hint_equiv( node_pointer n, node_pointer hint) { n->bucket_info_ = hint->bucket_info_; n->reset_first_in_group(); n->next_ = hint->next_; hint->next_ = n; if (n->next_) { std::size_t next_bucket = this->node_bucket(next_node(n)); if (next_bucket != this->node_bucket(n)) { this->get_bucket_pointer(next_bucket)->next_ = n; } } ++this->size_; return n; } iterator emplace_equiv(node_pointer n) { node_tmp a(n, this->node_alloc()); const_key_type& k = this->get_key(a.node_); std::size_t key_hash = this->hash(k); node_pointer position = this->find_node(key_hash, k); this->reserve_for_insert(this->size_ + 1); return iterator( this->add_node_equiv(a.release(), key_hash, position)); } iterator emplace_hint_equiv(c_iterator hint, node_pointer n) { node_tmp a(n, this->node_alloc()); const_key_type& k = this->get_key(a.node_); if (hint.node_ && this->key_eq()(k, this->get_key(hint.node_))) { this->reserve_for_insert(this->size_ + 1); return iterator( this->add_using_hint_equiv(a.release(), hint.node_)); } else { std::size_t key_hash = this->hash(k); node_pointer position = this->find_node(key_hash, k); this->reserve_for_insert(this->size_ + 1); return iterator( this->add_node_equiv(a.release(), key_hash, position)); } } void emplace_no_rehash_equiv(node_pointer n) { node_tmp a(n, this->node_alloc()); const_key_type& k = this->get_key(a.node_); std::size_t key_hash = this->hash(k); node_pointer position = this->find_node(key_hash, k); this->add_node_equiv(a.release(), key_hash, position); } template <typename NodeType> iterator move_insert_node_type_equiv(NodeType& np) { iterator result; if (np) { const_key_type& k = this->get_key(np.ptr_); std::size_t key_hash = this->hash(k); node_pointer pos = this->find_node(key_hash, k); this->reserve_for_insert(this->size_ + 1); result = iterator(this->add_node_equiv(np.ptr_, key_hash, pos)); np.ptr_ = node_pointer(); } return result; } template <typename NodeType> iterator move_insert_node_type_with_hint_equiv( c_iterator hint, NodeType& np) { iterator result; if (np) { const_key_type& k = this->get_key(np.ptr_); if (hint.node_ && this->key_eq()(k, this->get_key(hint.node_))) { this->reserve_for_insert(this->size_ + 1); result = iterator(this->add_using_hint_equiv(np.ptr_, hint.node_)); } else { std::size_t key_hash = this->hash(k); node_pointer pos = this->find_node(key_hash, k); this->reserve_for_insert(this->size_ + 1); result = iterator(this->add_node_equiv(np.ptr_, key_hash, pos)); } np.ptr_ = node_pointer(); } return result; } //////////////////////////////////////////////////////////////////////// // Insert range methods // if hash function throws, or inserting > 1 element, basic exception // safety. Strong otherwise template <class I> void insert_range_equiv(I i, I j, typename boost::unordered::detail::enable_if_forward<I, void*>::type = 0) { if (i == j) return; std::size_t distance = static_cast<std::size_t>(std::distance(i, j)); if (distance == 1) { emplace_equiv(boost::unordered::detail::func::construct_node( this->node_alloc(), *i)); } else { // Only require basic exception safety here this->reserve_for_insert(this->size_ + distance); for (; i != j; ++i) { emplace_no_rehash_equiv( boost::unordered::detail::func::construct_node( this->node_alloc(), *i)); } } } template <class I> void insert_range_equiv(I i, I j, typename boost::unordered::detail::disable_if_forward<I, void*>::type = 0) { for (; i != j; ++i) { emplace_equiv(boost::unordered::detail::func::construct_node( this->node_alloc(), *i)); } } //////////////////////////////////////////////////////////////////////// // Extract inline node_pointer extract_by_iterator_equiv(c_iterator n) { node_pointer i = n.node_; BOOST_ASSERT(i); node_pointer j(next_node(i)); std::size_t bucket_index = this->node_bucket(i); link_pointer prev = this->get_previous_start(bucket_index); while (prev->next_ != i) { prev = next_node(prev); } prev->next_ = j; if (j && i->is_first_in_group()) { j->set_first_in_group(); } --this->size_; this->fix_bucket(bucket_index, prev, j); i->next_ = link_pointer(); return i; } //////////////////////////////////////////////////////////////////////// // Erase // // no throw std::size_t erase_key_equiv(const_key_type& k) { if (!this->size_) return 0; std::size_t key_hash = this->hash(k); std::size_t bucket_index = this->hash_to_bucket(key_hash); link_pointer prev = this->find_previous_node(k, bucket_index); if (!prev) return 0; std::size_t deleted_count = 0; node_pointer n = next_node(prev); do { node_pointer n2 = next_node(n); destroy_node(n); ++deleted_count; n = n2; } while (n && !n->is_first_in_group()); size_ -= deleted_count; prev->next_ = n; this->fix_bucket(bucket_index, prev, n); return deleted_count; } link_pointer erase_nodes_equiv(node_pointer i, node_pointer j) { std::size_t bucket_index = this->node_bucket(i); link_pointer prev = this->get_previous_start(bucket_index); while (prev->next_ != i) { prev = next_node(prev); } // Delete the nodes. // Is it inefficient to call fix_bucket for every node? bool includes_first = false; prev->next_ = j; do { includes_first = includes_first || i->is_first_in_group(); node_pointer next = next_node(i); destroy_node(i); --size_; bucket_index = this->fix_bucket(bucket_index, prev, next); i = next; } while (i != j); if (j && includes_first) { j->set_first_in_group(); } return prev; } //////////////////////////////////////////////////////////////////////// // fill_buckets void copy_buckets(table const& src, false_type) { this->create_buckets(this->bucket_count_); for (node_pointer n = src.begin(); n;) { std::size_t key_hash = this->hash(this->get_key(n)); node_pointer group_end(next_group(n)); node_pointer pos = this->add_node_equiv( boost::unordered::detail::func::construct_node( this->node_alloc(), n->value()), key_hash, node_pointer()); for (n = next_node(n); n != group_end; n = next_node(n)) { this->add_node_equiv( boost::unordered::detail::func::construct_node( this->node_alloc(), n->value()), key_hash, pos); } } } void assign_buckets(table const& src, false_type) { node_holder<node_allocator> holder(*this); for (node_pointer n = src.begin(); n;) { std::size_t key_hash = this->hash(this->get_key(n)); node_pointer group_end(next_group(n)); node_pointer pos = this->add_node_equiv( holder.copy_of(n->value()), key_hash, node_pointer()); for (n = next_node(n); n != group_end; n = next_node(n)) { this->add_node_equiv(holder.copy_of(n->value()), key_hash, pos); } } } void move_assign_buckets(table& src, false_type) { node_holder<node_allocator> holder(*this); for (node_pointer n = src.begin(); n;) { std::size_t key_hash = this->hash(this->get_key(n)); node_pointer group_end(next_group(n)); node_pointer pos = this->add_node_equiv( holder.move_copy_of(n->value()), key_hash, node_pointer()); for (n = next_node(n); n != group_end; n = next_node(n)) { this->add_node_equiv( holder.move_copy_of(n->value()), key_hash, pos); } } } }; ////////////////////////////////////////////////////////////////////////// // Clear template <typename Types> inline void table<Types>::clear_impl() { if (size_) { bucket_pointer end = get_bucket_pointer(bucket_count_); for (bucket_pointer it = buckets_; it != end; ++it) { it->next_ = node_pointer(); } link_pointer prev = end->first_from_start(); node_pointer n = next_node(prev); prev->next_ = node_pointer(); size_ = 0; while (n) { node_pointer next = next_node(n); destroy_node(n); n = next; } } } ////////////////////////////////////////////////////////////////////////// // Reserve & Rehash // basic exception safety template <typename Types> inline void table<Types>::reserve_for_insert(std::size_t size) { if (!buckets_) { create_buckets((std::max)(bucket_count_, min_buckets_for_size(size))); } else if (size > max_load_) { std::size_t num_buckets = min_buckets_for_size((std::max)(size, size_ + (size_ >> 1))); if (num_buckets != bucket_count_) this->rehash_impl(num_buckets); } } // if hash function throws, basic exception safety // strong otherwise. template <typename Types> inline void table<Types>::rehash(std::size_t min_buckets) { using namespace std; if (!size_) { delete_buckets(); bucket_count_ = policy::new_bucket_count(min_buckets); } else { min_buckets = policy::new_bucket_count((std::max)(min_buckets, boost::unordered::detail::double_to_size( floor(static_cast<double>(size_) / static_cast<double>(mlf_))) + 1)); if (min_buckets != bucket_count_) this->rehash_impl(min_buckets); } } template <typename Types> inline void table<Types>::rehash_impl(std::size_t num_buckets) { BOOST_ASSERT(this->buckets_); this->create_buckets(num_buckets); link_pointer prev = this->get_previous_start(); BOOST_TRY { while (prev->next_) { node_pointer n = next_node(prev); std::size_t key_hash = this->hash(this->get_key(n)); std::size_t bucket_index = this->hash_to_bucket(key_hash); n->bucket_info_ = bucket_index; n->set_first_in_group(); // Iterator through the rest of the group of equal nodes, // setting the bucket. for (;;) { node_pointer next = next_node(n); if (!next || next->is_first_in_group()) { break; } n = next; n->bucket_info_ = bucket_index; n->reset_first_in_group(); } // n is now the last node in the group bucket_pointer b = this->get_bucket_pointer(bucket_index); if (!b->next_) { b->next_ = prev; prev = n; } else { link_pointer next = n->next_; n->next_ = b->next_->next_; b->next_->next_ = prev->next_; prev->next_ = next; } } } BOOST_CATCH(...) { node_pointer n = next_node(prev); prev->next_ = node_pointer(); while (n) { node_pointer next = next_node(n); destroy_node(n); --size_; n = next; } BOOST_RETHROW } BOOST_CATCH_END } #if defined(BOOST_MSVC) #pragma warning(pop) #endif //////////////////////////////////////////////////////////////////////// // key extractors // // no throw // // 'extract_key' is called with the emplace parameters to return a // key if available or 'no_key' is one isn't and will need to be // constructed. This could be done by overloading the emplace // implementation // for the different cases, but that's a bit tricky on compilers without // variadic templates. template <typename Key, typename T> struct is_key { template <typename T2> static choice1::type test(T2 const&); static choice2::type test(Key const&); enum { value = sizeof(test(boost::unordered::detail::make<T>())) == sizeof(choice2::type) }; typedef typename boost::detail::if_true<value>::BOOST_NESTED_TEMPLATE then<Key const&, no_key>::type type; }; template <class ValueType> struct set_extractor { typedef ValueType value_type; typedef ValueType key_type; static key_type const& extract(value_type const& v) { return v; } static key_type const& extract(BOOST_UNORDERED_RV_REF(value_type) v) { return v; } static no_key extract() { return no_key(); } template <class Arg> static no_key extract(Arg const&) { return no_key(); } #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) template <class Arg1, class Arg2, class... Args> static no_key extract(Arg1 const&, Arg2 const&, Args const&...) { return no_key(); } #else template <class Arg1, class Arg2> static no_key extract(Arg1 const&, Arg2 const&) { return no_key(); } #endif }; template <class ValueType> struct map_extractor { typedef ValueType value_type; typedef typename boost::remove_const<typename boost::unordered::detail:: pair_traits<ValueType>::first_type>::type key_type; static key_type const& extract(value_type const& v) { return v.first; } template <class Second> static key_type const& extract(std::pair<key_type, Second> const& v) { return v.first; } template <class Second> static key_type const& extract( std::pair<key_type const, Second> const& v) { return v.first; } #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) template <class Second> static key_type const& extract( boost::rv<std::pair<key_type, Second> > const& v) { return v.first; } template <class Second> static key_type const& extract( boost::rv<std::pair<key_type const, Second> > const& v) { return v.first; } #endif template <class Arg1> static key_type const& extract(key_type const& k, Arg1 const&) { return k; } static no_key extract() { return no_key(); } template <class Arg> static no_key extract(Arg const&) { return no_key(); } template <class Arg1, class Arg2> static no_key extract(Arg1 const&, Arg2 const&) { return no_key(); } #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) template <class Arg1, class Arg2, class Arg3, class... Args> static no_key extract( Arg1 const&, Arg2 const&, Arg3 const&, Args const&...) { return no_key(); } #endif #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) #define BOOST_UNORDERED_KEY_FROM_TUPLE(namespace_) \ template <typename T2> \ static no_key extract(boost::unordered::piecewise_construct_t, \ namespace_ tuple<> const&, T2 const&) \ { \ return no_key(); \ } \ \ template <typename T, typename T2> \ static typename is_key<key_type, T>::type extract( \ boost::unordered::piecewise_construct_t, namespace_ tuple<T> const& k, \ T2 const&) \ { \ return typename is_key<key_type, T>::type(namespace_ get<0>(k)); \ } #else #define BOOST_UNORDERED_KEY_FROM_TUPLE(namespace_) \ static no_key extract( \ boost::unordered::piecewise_construct_t, namespace_ tuple<> const&) \ { \ return no_key(); \ } \ \ template <typename T> \ static typename is_key<key_type, T>::type extract( \ boost::unordered::piecewise_construct_t, namespace_ tuple<T> const& k) \ { \ return typename is_key<key_type, T>::type(namespace_ get<0>(k)); \ } #endif BOOST_UNORDERED_KEY_FROM_TUPLE(boost::) #if BOOST_UNORDERED_TUPLE_ARGS BOOST_UNORDERED_KEY_FROM_TUPLE(std::) #endif #undef BOOST_UNORDERED_KEY_FROM_TUPLE }; //////////////////////////////////////////////////////////////////////// // Unique nodes template <typename A, typename T> struct node : boost::unordered::detail::value_base<T> { typedef typename ::boost::unordered::detail::rebind_wrap<A, node<A, T> >::type allocator; typedef typename ::boost::unordered::detail::allocator_traits< allocator>::pointer node_pointer; typedef node_pointer link_pointer; typedef typename ::boost::unordered::detail::rebind_wrap<A, bucket<node_pointer> >::type bucket_allocator; typedef typename ::boost::unordered::detail::allocator_traits< bucket_allocator>::pointer bucket_pointer; link_pointer next_; std::size_t bucket_info_; node() : next_(), bucket_info_(0) {} std::size_t get_bucket() const { return bucket_info_ & ((std::size_t)-1 >> 1); } std::size_t is_first_in_group() const { return !(bucket_info_ & ~((std::size_t)-1 >> 1)); } void set_first_in_group() { bucket_info_ = bucket_info_ & ((std::size_t)-1 >> 1); } void reset_first_in_group() { bucket_info_ = bucket_info_ | ~((std::size_t)-1 >> 1); } private: node& operator=(node const&); }; template <typename T> struct ptr_node : boost::unordered::detail::ptr_bucket { typedef T value_type; typedef boost::unordered::detail::ptr_bucket bucket_base; typedef ptr_node<T>* node_pointer; typedef ptr_bucket* link_pointer; typedef ptr_bucket* bucket_pointer; std::size_t bucket_info_; boost::unordered::detail::value_base<T> value_base_; ptr_node() : bucket_base(), bucket_info_(0) {} void* address() { return value_base_.address(); } value_type& value() { return value_base_.value(); } value_type* value_ptr() { return value_base_.value_ptr(); } std::size_t get_bucket() const { return bucket_info_ & ((std::size_t)-1 >> 1); } std::size_t is_first_in_group() const { return !(bucket_info_ & ~((std::size_t)-1 >> 1)); } void set_first_in_group() { bucket_info_ = bucket_info_ & ((std::size_t)-1 >> 1); } void reset_first_in_group() { bucket_info_ = bucket_info_ | ~((std::size_t)-1 >> 1); } private: ptr_node& operator=(ptr_node const&); }; // If the allocator uses raw pointers use ptr_node // Otherwise use node. template <typename A, typename T, typename NodePtr, typename BucketPtr> struct pick_node2 { typedef boost::unordered::detail::node<A, T> node; typedef typename boost::unordered::detail::allocator_traits< typename boost::unordered::detail::rebind_wrap<A, node>::type>::pointer node_pointer; typedef boost::unordered::detail::bucket<node_pointer> bucket; typedef node_pointer link_pointer; }; template <typename A, typename T> struct pick_node2<A, T, boost::unordered::detail::ptr_node<T>*, boost::unordered::detail::ptr_bucket*> { typedef boost::unordered::detail::ptr_node<T> node; typedef boost::unordered::detail::ptr_bucket bucket; typedef bucket* link_pointer; }; template <typename A, typename T> struct pick_node { typedef typename boost::remove_const<T>::type nonconst; typedef boost::unordered::detail::allocator_traits< typename boost::unordered::detail::rebind_wrap<A, boost::unordered::detail::ptr_node<nonconst> >::type> tentative_node_traits; typedef boost::unordered::detail::allocator_traits< typename boost::unordered::detail::rebind_wrap<A, boost::unordered::detail::ptr_bucket>::type> tentative_bucket_traits; typedef pick_node2<A, nonconst, typename tentative_node_traits::pointer, typename tentative_bucket_traits::pointer> pick; typedef typename pick::node node; typedef typename pick::bucket bucket; typedef typename pick::link_pointer link_pointer; }; } } } #undef BOOST_UNORDERED_EMPLACE_TEMPLATE #undef BOOST_UNORDERED_EMPLACE_ARGS #undef BOOST_UNORDERED_EMPLACE_FORWARD #undef BOOST_UNORDERED_CALL_CONSTRUCT1 #undef BOOST_UNORDERED_CALL_DESTROY #endif