| // 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 |