diff options
| author | DongHun Kwak <dh0128.kwak@samsung.com> | 2017-09-13 11:08:07 +0900 |
|---|---|---|
| committer | DongHun Kwak <dh0128.kwak@samsung.com> | 2017-09-13 11:09:00 +0900 |
| commit | b5c87084afaef42b2d058f68091be31988a6a874 (patch) | |
| tree | adef9a65870a41181687e11d57fdf98e7629de3c /boost/unordered/detail/implementation.hpp | |
| parent | 34bd32e225e2a8a94104489b31c42e5801cc1f4a (diff) | |
| download | boost-b5c87084afaef42b2d058f68091be31988a6a874.tar.gz boost-b5c87084afaef42b2d058f68091be31988a6a874.tar.bz2 boost-b5c87084afaef42b2d058f68091be31988a6a874.zip | |
Imported Upstream version 1.64.0upstream/1.64.0
Change-Id: Id9212edd016dd55f21172c427aa7894d1d24148b
Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>
Diffstat (limited to 'boost/unordered/detail/implementation.hpp')
| -rw-r--r-- | boost/unordered/detail/implementation.hpp | 4986 |
1 files changed, 4986 insertions, 0 deletions
diff --git a/boost/unordered/detail/implementation.hpp b/boost/unordered/detail/implementation.hpp new file mode 100644 index 0000000000..c293ae2f50 --- /dev/null +++ b/boost/unordered/detail/implementation.hpp @@ -0,0 +1,4986 @@ + +// 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/detail/no_exceptions_support.hpp> +#include <boost/detail/select_type.hpp> +#include <boost/iterator/iterator_categories.hpp> +#include <boost/limits.hpp> +#include <boost/move/move.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/is_class.hpp> +#include <boost/type_traits/is_convertible.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_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_TUPLE) +#include <tuple> +#endif + +#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. + +// 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 11 +#endif + +// BOOST_UNORDERED_INTEROPERABLE_NODES - Use the same node type for +// containers with unique and equivalent keys. +// +// 0 = Use different nodes +// 1 = Use ungrouped nodes everywhere +// +// Might add an extra value to use grouped nodes everywhere later. + +#if !defined(BOOST_UNORDERED_INTEROPERABLE_NODES) +#define BOOST_UNORDERED_INTEROPERABLE_NODES 0 +#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 + +namespace boost { +namespace unordered { +namespace iterator_detail { +template <typename Node> struct iterator; +template <typename Node> struct c_iterator; +template <typename Node, typename Policy> struct l_iterator; +template <typename Node, typename Policy> struct cl_iterator; +} +} +} + +namespace boost { +namespace unordered { +namespace detail { + +template <typename Types> struct table; +template <typename NodePointer> struct bucket; +struct ptr_bucket; +template <typename Types> struct table_impl; +template <typename Types> struct grouped_table_impl; + +template <typename A, typename T> struct unique_node; +template <typename T> struct ptr_node; +template <typename Types> struct table_impl; + +template <typename A, typename T> struct grouped_node; +template <typename T> struct grouped_ptr_node; +template <typename Types> struct grouped_table_impl; +template <typename N> struct node_algo; +template <typename N> struct grouped_node_algo; + +static const float minimum_max_load_factor = 1e-3f; +static const std::size_t default_bucket_count = 11; +struct move_tag +{ +}; +struct empty_emplace +{ +}; + +namespace func { +template <class T> inline void ignore_unused_variable_warning(T const&) {} +} + +//////////////////////////////////////////////////////////////////////////// +// iterator SFINAE + +template <typename I> +struct is_forward + : boost::is_convertible<typename boost::iterator_traversal<I>::type, + boost::forward_traversal_tag> +{ +}; + +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 + +template <class T> struct prime_list_template +{ + static std::size_t const value[]; + +#if !defined(SUNPRO_CC) + 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 !defined(SUNPRO_CC) +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) +{ + // TODO: Why +1? + return (std::max)( + boost::unordered::detail::insert_size(i, j) + 1, 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&); +}; + +namespace func { +// This is a bit nasty, when constructing the individual members +// of a std::pair, need to cast away 'const'. For modern compilers, +// should be able to use std::piecewise_construct instead. +template <typename T> T* const_cast_pointer(T* x) { return x; } +template <typename T> T* const_cast_pointer(T const* x) +{ + return const_cast<T*>(x); +} +} + +//////////////////////////////////////////////////////////////////////////// +// 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_ARGS1(a0) a0 +#define BOOST_UNORDERED_EMPLACE_ARGS2(a0, a1) a0, a1 +#define BOOST_UNORDERED_EMPLACE_ARGS3(a0, a1, a2) a0, a1, a2 + +#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_ARGS1 create_emplace_args +#define BOOST_UNORDERED_EMPLACE_ARGS2 create_emplace_args +#define BOOST_UNORDERED_EMPLACE_ARGS3 create_emplace_args + +#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 + +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; +} + +#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; \ + } + +BOOST_PP_REPEAT_FROM_TO( + 4, 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. + +//////////////////////////////////////////////////////////////////////////// +// 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 + +//////////////////////////////////////////////////////////////////////////// +// 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) + +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 + +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 +} +} +} + +//////////////////////////////////////////////////////////////////////////////// +// +// 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> + +#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) && \ + !defined(BOOST_NO_SFINAE_EXPR) +#define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 1 +#else +#define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 0 +#endif + +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; +}; + +#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 + +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 + +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); + +#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 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. + +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_DETAIL_FULL_CONSTRUCT + + 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; +}; +} +} +} + +#undef BOOST_UNORDERED_DEFAULT_TYPE_TMPLT +#undef BOOST_UNORDERED_DEFAULT_TYPE + +//////////////////////////////////////////////////////////////////////////////// +// +// std::allocator_traits + +#elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 1 + +#include <memory> + +#define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 1 + +namespace boost { +namespace unordered { +namespace detail { + +template <typename Alloc> struct allocator_traits : std::allocator_traits<Alloc> +{ +}; + +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> + +#define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 0 + +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. + +namespace boost { +namespace unordered { +namespace detail { +namespace func { + +//////////////////////////////////////////////////////////////////////////// +// call_construct + +#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + +#if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT + +template <typename Alloc, typename T, typename... Args> +inline void call_construct( + Alloc& alloc, T* address, BOOST_FWD_REF(Args)... args) +{ + boost::unordered::detail::allocator_traits<Alloc>::construct( + alloc, address, boost::forward<Args>(args)...); +} + +template <typename Alloc, typename T> +inline void call_destroy(Alloc& alloc, T* x) +{ + boost::unordered::detail::allocator_traits<Alloc>::destroy(alloc, x); +} + +#else + +template <typename Alloc, typename T, typename... Args> +inline void call_construct(Alloc&, T* address, BOOST_FWD_REF(Args)... args) +{ + new ((void*)address) T(boost::forward<Args>(args)...); +} + +template <typename Alloc, typename T> inline void call_destroy(Alloc&, T* x) +{ + boost::unordered::detail::func::destroy(x); +} + +#endif + +#else +template <typename Alloc, typename T> +inline void call_construct(Alloc&, T* address) +{ + new ((void*)address) T(); +} + +template <typename Alloc, typename T, typename A0> +inline void call_construct(Alloc&, T* address, BOOST_FWD_REF(A0) a0) +{ + new ((void*)address) T(boost::forward<A0>(a0)); +} + +template <typename Alloc, typename T> inline void call_destroy(Alloc&, T* x) +{ + boost::unordered::detail::func::destroy(x); +} + +#endif + +//////////////////////////////////////////////////////////////////////////// +// Construct from tuple +// +// Used for piecewise construction. + +#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + +#define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(n, namespace_) \ + template <typename Alloc, typename T> \ + void construct_from_tuple(Alloc& alloc, T* ptr, namespace_ tuple<>) \ + { \ + boost::unordered::detail::func::call_construct(alloc, ptr); \ + } \ + \ + BOOST_PP_REPEAT_FROM_TO( \ + 1, n, BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL, namespace_) + +#define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL(z, n, namespace_) \ + template <typename Alloc, typename T, \ + BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ + void construct_from_tuple(Alloc& alloc, T* ptr, \ + namespace_ tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \ + { \ + boost::unordered::detail::func::call_construct(alloc, ptr, \ + BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_)); \ + } + +#define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) namespace_ get<n>(x) + +#elif !defined(__SUNPRO_CC) + +#define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(n, namespace_) \ + template <typename Alloc, typename T> \ + void construct_from_tuple(Alloc&, T* ptr, namespace_ tuple<>) \ + { \ + new ((void*)ptr) T(); \ + } \ + \ + BOOST_PP_REPEAT_FROM_TO( \ + 1, n, BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL, namespace_) + +#define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL(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) + +#else + +template <int N> struct length +{ +}; + +#define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(n, namespace_) \ + template <typename Alloc, typename T> \ + void construct_from_tuple_impl(boost::unordered::detail::func::length<0>, \ + Alloc&, T* ptr, namespace_ tuple<>) \ + { \ + new ((void*)ptr) T(); \ + } \ + \ + BOOST_PP_REPEAT_FROM_TO( \ + 1, n, BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL, namespace_) + +#define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL(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) + +#endif + +BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(10, boost::) + +#if !defined(__SUNPRO_CC) && !defined(BOOST_NO_CXX11_HDR_TUPLE) +BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(10, std::) +#endif + +#undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE +#undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL +#undef BOOST_UNORDERED_GET_TUPLE_ARG + +#if defined(__SUNPRO_CC) + +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); +} + +#endif + +//////////////////////////////////////////////////////////////////////////// +// 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 !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + +//////////////////////////////////////////////////////////////////////////// +// Construct from variadic parameters + +// For the standard pair constructor. + +template <typename Alloc, typename T, typename... Args> +inline void construct_from_args( + Alloc& alloc, T* address, BOOST_FWD_REF(Args)... args) +{ + boost::unordered::detail::func::call_construct( + alloc, address, boost::forward<Args>(args)...); +} + +// Special case for piece_construct +// +// TODO: When possible, it might be better to use std::pair's +// constructor for std::piece_construct with std::tuple. + +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::unordered::detail::func::const_cast_pointer( + boost::addressof(address->first)), + boost::forward<A1>(a1)); + BOOST_TRY + { + boost::unordered::detail::func::construct_from_tuple( + alloc, boost::unordered::detail::func::const_cast_pointer( + boost::addressof(address->second)), + boost::forward<A2>(a2)); + } + BOOST_CATCH(...) + { + boost::unordered::detail::func::call_destroy( + alloc, boost::unordered::detail::func::const_cast_pointer( + 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_PP_REPEAT_FROM_TO( + 4, BOOST_UNORDERED_EMPLACE_LIMIT, BOOST_UNORDERED_CONSTRUCT_IMPL, _) + +#undef BOOST_UNORDERED_CONSTRUCT_IMPL + +// Construct with piece_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::unordered::detail::func::const_cast_pointer( + boost::addressof(address->first)), + args.a1); + BOOST_TRY + { + boost::unordered::detail::func::construct_from_tuple( + alloc, boost::unordered::detail::func::const_cast_pointer( + boost::addressof(address->second)), + args.a2); + } + BOOST_CATCH(...) + { + boost::unordered::detail::func::call_destroy( + alloc, boost::unordered::detail::func::const_cast_pointer( + 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_; + bool node_constructed_; + + node_constructor(node_allocator& n) + : alloc_(n), node_(), node_constructed_(false) + { + } + + ~node_constructor(); + + void create_node(); + + // no throw + node_pointer release() + { + BOOST_ASSERT(node_ && node_constructed_); + node_pointer p = node_; + node_ = node_pointer(); + return p; + } + + void reclaim(node_pointer p) + { + BOOST_ASSERT(!node_); + node_ = p; + node_constructed_ = true; + boost::unordered::detail::func::call_destroy( + 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_) { + if (node_constructed_) { + boost::unordered::detail::func::destroy(boost::addressof(*node_)); + } + + node_allocator_traits::deallocate(alloc_, node_, 1); + } +} + +template <typename Alloc> void node_constructor<Alloc>::create_node() +{ + BOOST_ASSERT(!node_); + node_constructed_ = false; + + node_ = node_allocator_traits::allocate(alloc_, 1); + + new ((void*)boost::addressof(*node_)) node(); + node_->init(node_); + node_constructed_ = true; +} + +template <typename NodeAlloc> struct node_tmp +{ + typedef boost::unordered::detail::allocator_traits<NodeAlloc> + node_allocator_traits; + typedef typename node_allocator_traits::pointer node_pointer; + + 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::detail::func::call_destroy( + alloc_, node_->value_ptr()); + boost::unordered::detail::func::destroy(boost::addressof(*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::detail::func::call_construct( + alloc, a.node_->value_ptr(), boost::forward<U>(x)); + return a.release(); +} + +// TODO: When possible, it might be better to use std::pair's +// constructor for std::piece_construct with std::tuple. +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::call_construct( + alloc, boost::unordered::detail::func::const_cast_pointer( + boost::addressof(a.node_->value_ptr()->first)), + boost::forward<Key>(k)); + BOOST_TRY + { + boost::unordered::detail::func::call_construct( + alloc, boost::unordered::detail::func::const_cast_pointer( + boost::addressof(a.node_->value_ptr()->second))); + } + BOOST_CATCH(...) + { + boost::unordered::detail::func::call_destroy( + alloc, boost::unordered::detail::func::const_cast_pointer( + 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::call_construct( + alloc, boost::unordered::detail::func::const_cast_pointer( + boost::addressof(a.node_->value_ptr()->first)), + boost::forward<Key>(k)); + BOOST_TRY + { + boost::unordered::detail::func::call_construct( + alloc, boost::unordered::detail::func::const_cast_pointer( + boost::addressof(a.node_->value_ptr()->second)), + boost::forward<Mapped>(m)); + } + BOOST_CATCH(...) + { + boost::unordered::detail::func::call_destroy( + alloc, boost::unordered::detail::func::const_cast_pointer( + 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::call_construct( + alloc, boost::unordered::detail::func::const_cast_pointer( + boost::addressof(a.node_->value_ptr()->first)), + boost::forward<Key>(k)); + BOOST_TRY + { + boost::unordered::detail::func::construct_from_args( + alloc, boost::unordered::detail::func::const_cast_pointer( + boost::addressof(a.node_->value_ptr()->second)), + BOOST_UNORDERED_EMPLACE_FORWARD); + } + BOOST_CATCH(...) + { + boost::unordered::detail::func::call_destroy( + alloc, boost::unordered::detail::func::const_cast_pointer( + boost::addressof(a.node_->value_ptr()->first))); + BOOST_RETHROW; + } + BOOST_CATCH_END + return a.release(); +} +} +} +} +} + +#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, typename Policy> +struct l_iterator : public std::iterator<std::forward_iterator_tag, + typename Node::value_type, std::ptrdiff_t, + typename Node::value_type*, typename Node::value_type&> +{ +#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) + template <typename Node2, typename Policy2> + 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 value_type; + + 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_ && Policy::to_bucket(bucket_count_, ptr_->hash_) != 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, typename Policy> +struct cl_iterator + : public std::iterator<std::forward_iterator_tag, typename Node::value_type, + std::ptrdiff_t, typename Node::value_type const*, + typename Node::value_type const&> +{ + friend struct boost::unordered::iterator_detail::l_iterator<Node, Policy>; + + 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 value_type; + + 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, Policy> 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_ && Policy::to_bucket(bucket_count_, ptr_->hash_) != 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 : public std::iterator<std::forward_iterator_tag, + typename Node::value_type, std::ptrdiff_t, + typename Node::value_type*, typename Node::value_type&> +{ +#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; + template <typename> friend struct boost::unordered::detail::table_impl; + template <typename> + friend struct boost::unordered::detail::grouped_table_impl; + + private: +#endif + typedef typename Node::node_pointer node_pointer; + node_pointer node_; + + public: + typedef typename Node::value_type value_type; + + 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 + : public std::iterator<std::forward_iterator_tag, typename Node::value_type, + std::ptrdiff_t, typename Node::value_type const*, + typename Node::value_type const&> +{ + friend struct boost::unordered::iterator_detail::iterator<Node>; + +#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) + template <typename> friend struct boost::unordered::detail::table; + template <typename> friend struct boost::unordered::detail::table_impl; + template <typename> + friend struct boost::unordered::detail::grouped_table_impl; + + 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 value_type; + + 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->init(n); + 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::detail::func::call_construct( + 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::detail::func::call_construct(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::detail::func::call_destroy( + constructor_.alloc_, p->value_ptr()); + boost::unordered::detail::func::destroy(boost::addressof(*p)); + node_allocator_traits::deallocate(constructor_.alloc_, p, 1); + } +} + +/////////////////////////////////////////////////////////////////// +// +// Bucket + +template <typename NodePointer> struct bucket +{ + typedef NodePointer link_pointer; + link_pointer next_; + + bucket() : next_() {} + + 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) {} + + 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; +}; + +// TODO: Maybe not if std::size_t is smaller than long long. +#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 + +// Assigning and swapping the equality and hash function objects +// needs strong exception safety. To implement that normally we'd +// require one of them to be known to not throw and the other to +// guarantee strong exception safety. Unfortunately they both only +// have basic exception safety. So to acheive strong exception +// safety we have storage space for two copies, and assign the new +// copies to the unused space. Then switch to using that to use +// them. This is implemented in 'set_hash_functions' which +// atomically assigns the new function objects in a strongly +// exception safe manner. + +template <class H, class P, bool NoThrowMoveAssign> class set_hash_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; + + private: + friend class boost::unordered::detail::set_hash_functions<H, P, + nothrow_move_assignable>; + 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; + + bool current_; // The currently active functions. + aligned_function funcs_[2]; + + function_pair const& current() const + { + return *static_cast<function_pair const*>( + static_cast<void const*>(&funcs_[current_])); + } + + function_pair& current() + { + return *static_cast<function_pair*>( + static_cast<void*>(&funcs_[current_])); + } + + void construct(bool which, H const& hf, P const& eq) + { + new ((void*)&funcs_[which]) function_pair(hf, eq); + } + + void construct(bool which, function_pair const& f, + boost::unordered::detail::false_type = + boost::unordered::detail::false_type()) + { + new ((void*)&funcs_[which]) function_pair(f); + } + + void construct( + bool which, function_pair& f, boost::unordered::detail::true_type) + { + new ((void*)&funcs_[which]) + function_pair(f, boost::unordered::detail::move_tag()); + } + + void destroy(bool which) + { + boost::unordered::detail::func::destroy( + (function_pair*)(&funcs_[which])); + } + + public: + typedef boost::unordered::detail::set_hash_functions<H, P, + nothrow_move_assignable> + set_hash_functions; + + functions(H const& hf, P const& eq) : current_(false) + { + construct(current_, hf, eq); + } + + functions(functions const& bf) : current_(false) + { + construct(current_, bf.current()); + } + + functions(functions& bf, boost::unordered::detail::move_tag) + : current_(false) + { + construct(current_, bf.current(), + boost::unordered::detail::integral_constant<bool, + nothrow_move_constructible>()); + } + + ~functions() { this->destroy(current_); } + + H const& hash_function() const { return current().first(); } + + P const& key_eq() const { return current().second(); } +}; + +template <class H, class P> class set_hash_functions<H, P, false> +{ + set_hash_functions(set_hash_functions const&); + set_hash_functions& operator=(set_hash_functions const&); + + typedef functions<H, P> functions_type; + + functions_type& functions_; + bool tmp_functions_; + + public: + set_hash_functions(functions_type& f, H const& h, P const& p) + : functions_(f), tmp_functions_(!f.current_) + { + f.construct(tmp_functions_, h, p); + } + + set_hash_functions(functions_type& f, functions_type const& other) + : functions_(f), tmp_functions_(!f.current_) + { + f.construct(tmp_functions_, other.current()); + } + + ~set_hash_functions() { functions_.destroy(tmp_functions_); } + + void commit() + { + functions_.current_ = tmp_functions_; + tmp_functions_ = !tmp_functions_; + } +}; + +template <class H, class P> class set_hash_functions<H, P, true> +{ + set_hash_functions(set_hash_functions const&); + set_hash_functions& operator=(set_hash_functions const&); + + typedef functions<H, P> functions_type; + + functions_type& functions_; + H hash_; + P pred_; + + public: + set_hash_functions(functions_type& f, H const& h, P const& p) + : functions_(f), hash_(h), pred_(p) + { + } + + set_hash_functions(functions_type& f, functions_type const& other) + : functions_(f), hash_(other.hash_function()), pred_(other.key_eq()) + { + } + + void commit() + { + functions_.current().first() = boost::move(hash_); + functions_.current().second() = boost::move(pred_); + } +}; + +//////////////////////////////////////////////////////////////////////////// +// 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); +} + +// The space used to store values in a node. + +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&); +}; + +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 typename Types::node_algo node_algo; + + typedef boost::unordered::detail::functions<typename Types::hasher, + typename Types::key_equal> + functions; + typedef typename functions::set_hash_functions set_hash_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; + + //////////////////////////////////////////////////////////////////////// + // 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 + + 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(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(bucket_count_)->first_from_start(); + } + + link_pointer get_previous_start(std::size_t bucket_index) const + { + return get_bucket(bucket_index)->next_; + } + + node_pointer begin() const + { + return size_ ? node_algo::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 ? node_algo::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); + } + + float load_factor() const + { + BOOST_ASSERT(bucket_count_ != 0); + return static_cast<float>(size_) / static_cast<float>(bucket_count_); + } + + 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 && hash_to_bucket(n->hash_) == index) { + ++count; + n = node_algo::next_node(n); + } + + return count; + } + + //////////////////////////////////////////////////////////////////////// + // Load methods + + std::size_t max_size() const + { + using namespace std; + + // size < mlf_ * count + return boost::unordered::detail::double_to_size( + ceil(static_cast<double>(mlf_) * + static_cast<double>(max_bucket_count()))) - + 1; + } + + 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_(x.max_load_), buckets_() + { + } + + //////////////////////////////////////////////////////////////////////// + // Initialisation. + + void init(table const& x) + { + if (x.size_) { + static_cast<table_impl*>(this)->copy_buckets(x); + } + } + + void move_init(table& x) + { + if (node_alloc() == x.node_alloc()) { + move_buckets_from(x); + } else if (x.size_) { + // TODO: Could pick new bucket size? + static_cast<table_impl*>(this)->move_buckets(x); + } + } + + //////////////////////////////////////////////////////////////////////// + // Create buckets + + void create_buckets(std::size_t new_count) + { + std::size_t length = new_count + 1; + bucket_pointer new_buckets = + bucket_allocator_traits::allocate(bucket_alloc(), length); + bucket_pointer constructed = new_buckets; + + BOOST_TRY + { + bucket_pointer end = + new_buckets + static_cast<std::ptrdiff_t>(length); + for (; constructed != end; ++constructed) { + new ((void*)boost::addressof(*constructed)) bucket(); + } + + if (buckets_) { + // Copy the nodes to the new buckets, including the dummy + // node if there is one. + (new_buckets + static_cast<std::ptrdiff_t>(new_count))->next_ = + (buckets_ + static_cast<std::ptrdiff_t>(bucket_count_)) + ->next_; + destroy_buckets(); + } else if (bucket::extra_node) { + node_constructor a(node_alloc()); + a.create_node(); + + (new_buckets + static_cast<std::ptrdiff_t>(new_count))->next_ = + a.release(); + } + } + BOOST_CATCH(...) + { + for (bucket_pointer p = new_buckets; p != constructed; ++p) { + boost::unordered::detail::func::destroy(boost::addressof(*p)); + } + + bucket_allocator_traits::deallocate( + bucket_alloc(), new_buckets, length); + + BOOST_RETHROW; + } + BOOST_CATCH_END + + bucket_count_ = new_count; + buckets_ = new_buckets; + recalculate_max_load(); + } + + //////////////////////////////////////////////////////////////////////// + // 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_); + } + + // Only swaps the allocators if propagate_on_container_swap + void swap(table& x) + { + set_hash_functions op1(*this, x); + set_hash_functions op2(x, *this); + + // I think swap can throw if Propagate::value, + // since the allocators' swap can throw. Not sure though. + 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_); + op1.commit(); + op2.commit(); + } + + // 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_; + other.buckets_ = bucket_pointer(); + other.size_ = 0; + other.max_load_ = 0; + } + + //////////////////////////////////////////////////////////////////////// + // Delete/destruct + + ~table() { delete_buckets(); } + + void delete_node(link_pointer prev) + { + node_pointer n = static_cast<node_pointer>(prev->next_); + prev->next_ = n->next_; + + boost::unordered::detail::func::call_destroy( + node_alloc(), n->value_ptr()); + boost::unordered::detail::func::destroy(boost::addressof(*n)); + node_allocator_traits::deallocate(node_alloc(), n, 1); + --size_; + } + + std::size_t delete_nodes(link_pointer prev, link_pointer end) + { + BOOST_ASSERT(prev->next_ != end); + + std::size_t count = 0; + + do { + delete_node(prev); + ++count; + } while (prev->next_ != end); + + return count; + } + + void delete_buckets() + { + if (buckets_) { + if (size_) + delete_nodes(get_previous_start(), link_pointer()); + + if (bucket::extra_node) { + node_pointer n = + static_cast<node_pointer>(get_bucket(bucket_count_)->next_); + boost::unordered::detail::func::destroy(boost::addressof(*n)); + node_allocator_traits::deallocate(node_alloc(), n, 1); + } + + destroy_buckets(); + buckets_ = bucket_pointer(); + max_load_ = 0; + } + + BOOST_ASSERT(!size_); + } + + void clear() + { + if (!size_) + return; + + delete_nodes(get_previous_start(), link_pointer()); + clear_buckets(); + + BOOST_ASSERT(!size_); + } + + void clear_buckets() + { + bucket_pointer end = get_bucket(bucket_count_); + for (bucket_pointer it = buckets_; it != end; ++it) { + it->next_ = node_pointer(); + } + } + + void destroy_buckets() + { + bucket_pointer end = get_bucket(bucket_count_ + 1); + for (bucket_pointer it = buckets_; it != end; ++it) { + boost::unordered::detail::func::destroy(boost::addressof(*it)); + } + + bucket_allocator_traits::deallocate( + bucket_alloc(), buckets_, bucket_count_ + 1); + } + + //////////////////////////////////////////////////////////////////////// + // Fix buckets after delete + // + + std::size_t fix_bucket(std::size_t bucket_index, link_pointer prev) + { + link_pointer end = prev->next_; + std::size_t bucket_index2 = bucket_index; + + if (end) { + bucket_index2 = + hash_to_bucket(static_cast<node_pointer>(end)->hash_); + + // If begin and end are in the same bucket, then + // there's nothing to do. + if (bucket_index == bucket_index2) + return bucket_index2; + + // Update the bucket containing end. + get_bucket(bucket_index2)->next_ = prev; + } + + // Check if this bucket is now empty. + bucket_pointer this_bucket = get_bucket(bucket_index); + if (this_bucket->next_ == prev) + this_bucket->next_ = link_pointer(); + + return bucket_index2; + } + + //////////////////////////////////////////////////////////////////////// + // Assignment + + void assign(table const& x) + { + if (this != boost::addressof(x)) { + assign(x, boost::unordered::detail::integral_constant<bool, + allocator_traits<node_allocator>:: + propagate_on_container_copy_assignment::value>()); + } + } + + void assign(table const& x, false_type) + { + // Strong exception safety. + set_hash_functions new_func_this(*this, x); + mlf_ = x.mlf_; + recalculate_max_load(); + + if (!size_ && !x.size_) { + new_func_this.commit(); + return; + } + + if (x.size_ >= max_load_) { + create_buckets(min_buckets_for_size(x.size_)); + } else { + clear_buckets(); + } + + new_func_this.commit(); + static_cast<table_impl*>(this)->assign_buckets(x); + } + + void assign(table const& x, true_type) + { + if (node_alloc() == x.node_alloc()) { + allocators_.assign(x.allocators_); + assign(x, false_type()); + } else { + set_hash_functions new_func_this(*this, x); + + // Delete everything with current allocators before assigning + // the new ones. + delete_buckets(); + allocators_.assign(x.allocators_); + + // Copy over other data, all no throw. + new_func_this.commit(); + mlf_ = x.mlf_; + bucket_count_ = min_buckets_for_size(x.size_); + max_load_ = 0; + + // Finally copy the elements. + if (x.size_) { + static_cast<table_impl*>(this)->copy_buckets(x); + } + } + } + + void move_assign(table& x) + { + if (this != boost::addressof(x)) { + move_assign( + x, boost::unordered::detail::integral_constant<bool, + allocator_traits<node_allocator>:: + propagate_on_container_move_assignment::value>()); + } + } + + void move_assign(table& x, true_type) + { + delete_buckets(); + set_hash_functions new_func_this(*this, x); + allocators_.move_assign(x.allocators_); + // No throw from here. + mlf_ = x.mlf_; + max_load_ = x.max_load_; + move_buckets_from(x); + new_func_this.commit(); + } + + void move_assign(table& x, false_type) + { + if (node_alloc() == x.node_alloc()) { + delete_buckets(); + set_hash_functions new_func_this(*this, x); + // No throw from here. + mlf_ = x.mlf_; + max_load_ = x.max_load_; + move_buckets_from(x); + new_func_this.commit(); + } else { + set_hash_functions new_func_this(*this, x); + mlf_ = x.mlf_; + recalculate_max_load(); + + if (!size_ && !x.size_) { + new_func_this.commit(); + return; + } + + if (x.size_ >= max_load_) { + create_buckets(min_buckets_for_size(x.size_)); + } else { + clear_buckets(); + } + + new_func_this.commit(); + static_cast<table_impl*>(this)->move_assign_buckets(x); + } + } + + // Accessors + + const_key_type& get_key(value_type const& x) const + { + return extractor::extract(x); + } + + std::size_t hash(const_key_type& k) const + { + return policy::apply_hash(this->hash_function(), k); + } + + // Find Node + + template <typename Key, typename Hash, typename Pred> + node_pointer generic_find_node( + Key const& k, Hash const& hf, Pred const& eq) const + { + return this->find_node_impl(policy::apply_hash(hf, k), k, eq); + } + + 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; + + std::size_t node_hash = n->hash_; + if (key_hash == node_hash) { + if (eq(k, this->get_key(n->value()))) + return n; + } else { + if (this->hash_to_bucket(node_hash) != bucket_index) + return node_pointer(); + } + + n = node_algo::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 key_hash, std::size_t bucket_index) + { + link_pointer prev = this->get_previous_start(bucket_index); + if (!prev) { + return prev; + } + + for (;;) { + if (!prev->next_) { + return link_pointer(); + } + std::size_t node_hash = node_algo::next_node(prev)->hash_; + if (this->hash_to_bucket(node_hash) != bucket_index) { + return link_pointer(); + } + if (node_hash == key_hash && + this->key_eq()( + k, this->get_key(node_algo::next_node(prev)->value()))) { + return prev; + } + prev = node_algo::next_for_erase(prev); + } + } + + // 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, key_hash, bucket_index); + if (!prev) { + return node_pointer(); + } + node_pointer n = node_algo::extract_first_node(prev); + --this->size_; + this->fix_bucket(bucket_index, prev); + 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); +}; + +//////////////////////////////////////////////////////////////////////////// +// 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>::reserve(std::size_t num_elements) +{ + rehash(static_cast<std::size_t>( + std::ceil(static_cast<double>(num_elements) / mlf_))); +} + +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(); + while (prev->next_) { + node_pointer group_last = node_algo::last_for_rehash(prev); + bucket_pointer b = + this->get_bucket(this->hash_to_bucket(group_last->hash_)); + if (!b->next_) { + b->next_ = prev; + prev = group_last; + } else { + link_pointer next = group_last->next_; + group_last->next_ = b->next_->next_; + b->next_->next_ = prev->next_; + prev->next_ = next; + } + } +} + +#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. + +struct no_key +{ + no_key() {} + template <class T> no_key(T const&) {} +}; + +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 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; + } + + 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 !defined(BOOST_NO_CXX11_HDR_TUPLE) + BOOST_UNORDERED_KEY_FROM_TUPLE(std::) +#endif +}; + +//////////////////////////////////////////////////////////////////////// +// Unique nodes + +template <typename A, typename T> +struct unique_node : boost::unordered::detail::value_base<T> +{ + typedef typename ::boost::unordered::detail::rebind_wrap<A, + unique_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 hash_; + + unique_node() : next_(), hash_(0) {} + + void init(node_pointer) {} + + private: + unique_node& operator=(unique_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 hash_; + boost::unordered::detail::value_base<T> value_base_; + + ptr_node() : bucket_base(), hash_(0) {} + + void init(node_pointer) {} + + void* address() { return value_base_.address(); } + value_type& value() { return value_base_.value(); } + value_type* value_ptr() { return value_base_.value_ptr(); } + + private: + ptr_node& operator=(ptr_node const&); +}; + +template <typename N> struct node_algo +{ + typedef typename N::node_pointer node_pointer; + typedef typename N::link_pointer link_pointer; + typedef typename N::bucket_pointer bucket_pointer; + + static node_pointer next_node(link_pointer n) + { + return static_cast<node_pointer>(n->next_); + } + + static node_pointer next_for_find(node_pointer n) + { + return static_cast<node_pointer>(n->next_); + } + + static link_pointer next_for_erase(link_pointer prev) + { + return prev->next_; + } + + // Group together all nodes with equal hash value, this may + // include nodes with different keys, but that's okay because + // they will end up in the same bucket. + static node_pointer last_for_rehash(link_pointer prev) + { + node_pointer n = next_node(prev); + std::size_t hash = n->hash_; + for (;;) { + node_pointer next = next_node(n); + if (!next || next->hash_ != hash) { + return n; + } + n = next; + } + } + + template <typename Table> + static node_pointer next_group(node_pointer n, Table const* t) + { + node_pointer n1 = n; + do { + n1 = next_node(n1); + } while ( + n1 && t->key_eq()(t->get_key(n->value()), t->get_key(n1->value()))); + return n1; + } + + template <typename Table> + static std::size_t count(node_pointer n, Table const* t) + { + std::size_t x = 0; + node_pointer it = n; + do { + ++x; + it = next_node(it); + } while ( + it && t->key_eq()(t->get_key(n->value()), t->get_key(it->value()))); + + return x; + } + + // Add node 'n' after 'pos'. + // This results in a different order to the grouped implementation. + static inline void add_to_node_group(node_pointer n, node_pointer pos) + { + n->next_ = pos->next_; + pos->next_ = n; + } + + static inline node_pointer extract_first_node(link_pointer prev) + { + node_pointer n = next_node(prev); + prev->next_ = n->next_; + return n; + } + + static link_pointer split_groups(node_pointer, node_pointer) + { + return link_pointer(); + } +}; + +// 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::unique_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; + typedef boost::unordered::detail::node_algo<node> node_algo; +}; + +template <typename Types> +struct table_impl : boost::unordered::detail::table<Types> +{ + typedef boost::unordered::detail::table<Types> table; + typedef typename table::value_type value_type; + typedef typename table::node node; + typedef typename table::bucket bucket; + typedef typename table::policy policy; + typedef typename table::node_pointer node_pointer; + typedef typename table::node_allocator node_allocator; + typedef typename table::node_allocator_traits node_allocator_traits; + typedef typename table::bucket_pointer bucket_pointer; + typedef typename table::link_pointer link_pointer; + typedef typename table::hasher hasher; + typedef typename table::key_equal key_equal; + typedef typename table::const_key_type const_key_type; + typedef typename table::node_constructor node_constructor; + typedef typename table::node_tmp node_tmp; + typedef typename table::extractor extractor; + typedef typename table::iterator iterator; + typedef typename table::c_iterator c_iterator; + typedef typename table::node_algo node_algo; + + typedef std::pair<iterator, bool> emplace_return; + + // Constructors + + table_impl(std::size_t n, hasher const& hf, key_equal const& eq, + node_allocator const& a) + : table(n, hf, eq, a) + { + } + + table_impl(table_impl const& x) + : table(x, node_allocator_traits::select_on_container_copy_construction( + x.node_alloc())) + { + this->init(x); + } + + table_impl(table_impl const& x, node_allocator const& a) : table(x, a) + { + this->init(x); + } + + table_impl(table_impl& x, boost::unordered::detail::move_tag m) + : table(x, m) + { + } + + table_impl(table_impl& x, node_allocator const& a, + boost::unordered::detail::move_tag m) + : table(x, a, m) + { + this->move_init(x); + } + + // Accessors + + std::size_t count(const_key_type& k) const + { + return this->find_node(k) ? 1 : 0; + } + + value_type& at(const_key_type& k) const + { + if (this->size_) { + node_pointer n = this->find_node(k); + if (n) + return n->value(); + } + + boost::throw_exception( + std::out_of_range("Unable to find key in unordered_map.")); + } + + std::pair<iterator, iterator> equal_range(const_key_type& k) const + { + node_pointer n = this->find_node(k); + return std::make_pair( + iterator(n), iterator(n ? node_algo::next_node(n) : n)); + } + + // equals + + bool equals(table_impl const& other) const + { + if (this->size_ != other.size_) + return false; + + for (node_pointer n1 = this->begin(); n1; + n1 = node_algo::next_node(n1)) { + node_pointer n2 = other.find_node(other.get_key(n1->value())); + + if (!n2 || n1->value() != n2->value()) + return false; + } + + return true; + } + + // Emplace/Insert + + inline node_pointer add_node(node_pointer n, std::size_t key_hash) + { + n->hash_ = key_hash; + + bucket_pointer b = this->get_bucket(this->hash_to_bucket(key_hash)); + + if (!b->next_) { + link_pointer start_node = this->get_previous_start(); + + if (start_node->next_) { + this->get_bucket(this->hash_to_bucket( + node_algo::next_node(start_node)->hash_)) + ->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( + 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(b.release(), key_hash); + } + +#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) +#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + emplace_return emplace(boost::unordered::detail::emplace_args1< + boost::unordered::detail::please_ignore_this_overload> const&) + { + BOOST_ASSERT(false); + return emplace_return(iterator(), false); + } + + iterator emplace_hint( + c_iterator, + boost::unordered::detail::emplace_args1< + boost::unordered::detail::please_ignore_this_overload> const&) + { + BOOST_ASSERT(false); + return iterator(); + } +#else + emplace_return emplace( + boost::unordered::detail::please_ignore_this_overload const&) + { + BOOST_ASSERT(false); + return emplace_return(iterator(), false); + } + + iterator emplace_hint(c_iterator, + boost::unordered::detail::please_ignore_this_overload const&) + { + BOOST_ASSERT(false); + return iterator(); + } +#endif +#endif + + template <BOOST_UNORDERED_EMPLACE_TEMPLATE> + emplace_return emplace(BOOST_UNORDERED_EMPLACE_ARGS) + { +#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + return emplace_impl(extractor::extract(BOOST_UNORDERED_EMPLACE_FORWARD), + BOOST_UNORDERED_EMPLACE_FORWARD); +#else + return emplace_impl(extractor::extract(args.a0, args.a1), + BOOST_UNORDERED_EMPLACE_FORWARD); +#endif + } + + template <BOOST_UNORDERED_EMPLACE_TEMPLATE> + iterator emplace_hint(c_iterator hint, BOOST_UNORDERED_EMPLACE_ARGS) + { +#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + return emplace_hint_impl(hint, + extractor::extract(BOOST_UNORDERED_EMPLACE_FORWARD), + BOOST_UNORDERED_EMPLACE_FORWARD); +#else + return emplace_hint_impl(hint, extractor::extract(args.a0, args.a1), + BOOST_UNORDERED_EMPLACE_FORWARD); +#endif + } + +#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + template <typename A0> + emplace_return emplace( + boost::unordered::detail::emplace_args1<A0> const& args) + { + return emplace_impl(extractor::extract(args.a0), args); + } + + template <typename A0> + iterator emplace_hint(c_iterator hint, + boost::unordered::detail::emplace_args1<A0> const& args) + { + return emplace_hint_impl(hint, extractor::extract(args.a0), args); + } +#endif + + template <BOOST_UNORDERED_EMPLACE_TEMPLATE> + iterator emplace_hint_impl( + c_iterator hint, const_key_type& k, BOOST_UNORDERED_EMPLACE_ARGS) + { + if (hint.node_ && this->key_eq()(k, this->get_key(*hint))) { + return iterator(hint.node_); + } else { + return emplace_impl(k, BOOST_UNORDERED_EMPLACE_FORWARD).first; + } + } + + template <BOOST_UNORDERED_EMPLACE_TEMPLATE> + emplace_return emplace_impl(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( + 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_impl( + 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_->value()); + if (hint.node_ && this->key_eq()(k, this->get_key(*hint))) { + 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(b.release(), key_hash)); + } + } + + template <BOOST_UNORDERED_EMPLACE_TEMPLATE> + emplace_return emplace_impl(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_->value()); + 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(b.release(), key_hash)), + true); + } + } + + template <typename Key> + emplace_return try_emplace_impl(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( + boost::unordered::detail::func::construct_node_pair( + this->node_alloc(), boost::forward<Key>(k)), + key_hash)), + true); + } + } + + template <typename Key> + iterator try_emplace_hint_impl(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_impl(k).first; + } + } + + template <typename Key, BOOST_UNORDERED_EMPLACE_TEMPLATE> + emplace_return try_emplace_impl( + 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( + 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_impl( + 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_impl(k, BOOST_UNORDERED_EMPLACE_FORWARD).first; + } + } + + template <typename Key, typename M> + emplace_return insert_or_assign_impl( + 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( + 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(NodeType& np, InsertReturnType& result) + { + if (np) { + const_key_type& k = this->get_key(np.ptr_->value()); + 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(np.ptr_, key_hash)); + result.inserted = true; + np.ptr_ = node_pointer(); + } + } + } + + template <typename NodeType> + iterator move_insert_node_type_with_hint(c_iterator hint, NodeType& np) + { + if (!np) { + return iterator(); + } + const_key_type& k = this->get_key(np.ptr_->value()); + if (hint.node_ && this->key_eq()(k, this->get_key(*hint))) { + 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(np.ptr_, key_hash); + np.ptr_ = node_pointer(); + } + return iterator(pos); + } + + template <typename Types2> + void merge_impl(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::node_algo::next_node(prev); + const_key_type& k = this->get_key(n->value()); + 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); + other_table::node_algo::split_groups( + n, other_table::node_algo::next_node(n)); + prev->next_ = n->next_; + --other.size_; + other.fix_bucket(other.hash_to_bucket(n->hash_), prev); + this->add_node(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(InputIt i, InputIt j) + { + if (i != j) + return insert_range_impl(extractor::extract(*i), i, j); + } + + template <class InputIt> + void insert_range_impl(const_key_type& k, InputIt i, InputIt j) + { + insert_range_impl2(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. + // + // TODO: Might be worth storing the value_type instead of the + // key here. Could be more efficient if '*i' is expensive. Could + // be less efficient if copying the full value_type is + // expensive. + insert_range_impl2(extractor::extract(*i), i, j); + } + } + + template <class InputIt> + void insert_range_impl2(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(b.release(), key_hash); + } + } + + template <class InputIt> + void insert_range_impl(no_key, InputIt i, InputIt j) + { + node_constructor a(this->node_alloc()); + + do { + if (!a.node_) { + a.create_node(); + } + boost::unordered::detail::func::call_construct( + a.alloc_, a.node_->value_ptr(), *i); + node_tmp b(a.release(), a.alloc_); + + const_key_type& k = this->get_key(b.node_->value()); + 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(b.release(), key_hash); + } + } while (++i != j); + } + + //////////////////////////////////////////////////////////////////////// + // Extract + + inline node_pointer extract_by_iterator(c_iterator i) + { + node_pointer n = i.node_; + BOOST_ASSERT(n); + std::size_t key_hash = n->hash_; + std::size_t bucket_index = this->hash_to_bucket(key_hash); + link_pointer prev = this->get_previous_start(bucket_index); + while (prev->next_ != n) { + prev = prev->next_; + } + prev->next_ = n->next_; + --this->size_; + this->fix_bucket(bucket_index, prev); + n->next_ = link_pointer(); + return n; + } + + //////////////////////////////////////////////////////////////////////// + // Erase + // + // no throw + + std::size_t erase_key(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, key_hash, bucket_index); + if (!prev) + return 0; + link_pointer end = node_algo::next_node(prev)->next_; + this->delete_nodes(prev, end); + this->fix_bucket(bucket_index, prev); + return 1; + } + + iterator erase(c_iterator r) + { + BOOST_ASSERT(r.node_); + node_pointer next = node_algo::next_node(r.node_); + erase_nodes(r.node_, next); + return iterator(next); + } + + iterator erase_range(c_iterator r1, c_iterator r2) + { + if (r1 == r2) + return iterator(r2.node_); + erase_nodes(r1.node_, r2.node_); + return iterator(r2.node_); + } + + void erase_nodes(node_pointer i, node_pointer j) + { + std::size_t bucket_index = this->hash_to_bucket(i->hash_); + + // Find the node before i. + link_pointer prev = this->get_previous_start(bucket_index); + while (prev->next_ != i) + prev = prev->next_; + + // Delete the nodes. + do { + this->delete_node(prev); + bucket_index = this->fix_bucket(bucket_index, prev); + } while (prev->next_ != j); + } + + //////////////////////////////////////////////////////////////////////// + // fill_buckets + + void copy_buckets(table const& src) + { + this->create_buckets(this->bucket_count_); + + for (node_pointer n = src.begin(); n; n = node_algo::next_node(n)) { + this->add_node(boost::unordered::detail::func::construct_node( + this->node_alloc(), n->value()), + n->hash_); + } + } + + void move_buckets(table const& src) + { + this->create_buckets(this->bucket_count_); + + for (node_pointer n = src.begin(); n; n = node_algo::next_node(n)) { + this->add_node(boost::unordered::detail::func::construct_node( + this->node_alloc(), boost::move(n->value())), + n->hash_); + } + } + + void assign_buckets(table const& src) + { + node_holder<node_allocator> holder(*this); + for (node_pointer n = src.begin(); n; n = node_algo::next_node(n)) { + this->add_node(holder.copy_of(n->value()), n->hash_); + } + } + + void move_assign_buckets(table& src) + { + node_holder<node_allocator> holder(*this); + for (node_pointer n = src.begin(); n; n = node_algo::next_node(n)) { + this->add_node(holder.move_copy_of(n->value()), n->hash_); + } + } +}; + +//////////////////////////////////////////////////////////////////////// +// Grouped nodes + +template <typename A, typename T> +struct grouped_node : boost::unordered::detail::value_base<T> +{ + typedef typename ::boost::unordered::detail::rebind_wrap<A, + grouped_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_; + node_pointer group_prev_; + std::size_t hash_; + + grouped_node() : next_(), group_prev_(), hash_(0) {} + + void init(node_pointer self) { group_prev_ = self; } + + private: + grouped_node& operator=(grouped_node const&); +}; + +template <typename T> +struct grouped_ptr_node : boost::unordered::detail::ptr_bucket +{ + typedef T value_type; + typedef boost::unordered::detail::ptr_bucket bucket_base; + typedef grouped_ptr_node<T>* node_pointer; + typedef ptr_bucket* link_pointer; + typedef ptr_bucket* bucket_pointer; + + node_pointer group_prev_; + std::size_t hash_; + boost::unordered::detail::value_base<T> value_base_; + + grouped_ptr_node() : bucket_base(), group_prev_(0), hash_(0) {} + + void init(node_pointer self) { group_prev_ = self; } + + void* address() { return value_base_.address(); } + value_type& value() { return value_base_.value(); } + value_type* value_ptr() { return value_base_.value_ptr(); } + + private: + grouped_ptr_node& operator=(grouped_ptr_node const&); +}; + +template <typename N> struct grouped_node_algo +{ + typedef typename N::node_pointer node_pointer; + typedef typename N::link_pointer link_pointer; + typedef typename N::bucket_pointer bucket_pointer; + + static node_pointer next_node(link_pointer n) + { + return static_cast<node_pointer>(n->next_); + } + + static node_pointer next_for_find(node_pointer n) + { + return static_cast<node_pointer>(n->group_prev_->next_); + } + + static link_pointer next_for_erase(link_pointer prev) + { + return static_cast<node_pointer>(prev->next_)->group_prev_; + } + + static node_pointer last_for_rehash(link_pointer prev) + { + return static_cast<node_pointer>(prev->next_)->group_prev_; + } + + // The 'void*' arguments are pointers to the table, which we + // will ignore, but without groups they could be used to + // access the various functions for dealing with values and keys. + static node_pointer next_group(node_pointer n, void const*) + { + return static_cast<node_pointer>(n->group_prev_->next_); + } + + static std::size_t count(node_pointer n, void const*) + { + std::size_t x = 0; + node_pointer it = n; + do { + it = it->group_prev_; + ++x; + } while (it != n); + + return x; + } + + // Adds node 'n' to the group containing 'pos'. + // If 'pos' is the first node in group, add to the end of the group, + // otherwise add before 'pos'. Other versions will probably behave + // differently. + static inline void add_to_node_group(node_pointer n, node_pointer pos) + { + n->next_ = pos->group_prev_->next_; + n->group_prev_ = pos->group_prev_; + pos->group_prev_->next_ = n; + pos->group_prev_ = n; + } + + static inline node_pointer extract_first_node(link_pointer prev) + { + node_pointer n = next_node(prev); + if (n->group_prev_ != n) { + node_pointer next = next_node(n); + next->group_prev_ = n->group_prev_; + n->group_prev_ = n; + } + prev->next_ = n->next_; + return n; + } + + // Split the groups containing 'i' and 'j' so that they can + // be safely erased/extracted. + static link_pointer split_groups(node_pointer i, node_pointer j) + { + node_pointer prev = i->group_prev_; + if (prev->next_ != i) + prev = node_pointer(); + + if (j) { + node_pointer first = j; + while (first != i && first->group_prev_->next_ == first) { + first = first->group_prev_; + } + + boost::swap(first->group_prev_, j->group_prev_); + if (first == i) + return prev; + } + + if (prev) { + node_pointer first = prev; + while (first->group_prev_->next_ == first) { + first = first->group_prev_; + } + boost::swap(first->group_prev_, i->group_prev_); + } + + return prev; + } +}; + +// If the allocator uses raw pointers use grouped_ptr_node +// Otherwise use grouped_node. + +template <typename A, typename T, typename NodePtr, typename BucketPtr> +struct pick_grouped_node2 +{ + typedef boost::unordered::detail::grouped_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_grouped_node2<A, T, boost::unordered::detail::grouped_ptr_node<T>*, + boost::unordered::detail::ptr_bucket*> +{ + typedef boost::unordered::detail::grouped_ptr_node<T> node; + typedef boost::unordered::detail::ptr_bucket bucket; + typedef bucket* link_pointer; +}; + +template <typename A, typename T> struct pick_grouped_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::grouped_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_grouped_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; + typedef boost::unordered::detail::grouped_node_algo<node> node_algo; +}; + +template <typename Types> +struct grouped_table_impl : boost::unordered::detail::table<Types> +{ + typedef boost::unordered::detail::table<Types> table; + typedef typename table::value_type value_type; + typedef typename table::bucket bucket; + typedef typename table::policy policy; + typedef typename table::node_pointer node_pointer; + typedef typename table::node_allocator node_allocator; + typedef typename table::node_allocator_traits node_allocator_traits; + typedef typename table::bucket_pointer bucket_pointer; + typedef typename table::link_pointer link_pointer; + typedef typename table::hasher hasher; + typedef typename table::key_equal key_equal; + typedef typename table::const_key_type const_key_type; + typedef typename table::node_constructor node_constructor; + typedef typename table::node_tmp node_tmp; + typedef typename table::extractor extractor; + typedef typename table::iterator iterator; + typedef typename table::c_iterator c_iterator; + typedef typename table::node_algo node_algo; + + // Constructors + + grouped_table_impl(std::size_t n, hasher const& hf, key_equal const& eq, + node_allocator const& a) + : table(n, hf, eq, a) + { + } + + grouped_table_impl(grouped_table_impl const& x) + : table(x, node_allocator_traits::select_on_container_copy_construction( + x.node_alloc())) + { + this->init(x); + } + + grouped_table_impl(grouped_table_impl const& x, node_allocator const& a) + : table(x, a) + { + this->init(x); + } + + grouped_table_impl( + grouped_table_impl& x, boost::unordered::detail::move_tag m) + : table(x, m) + { + } + + grouped_table_impl(grouped_table_impl& x, node_allocator const& a, + boost::unordered::detail::move_tag m) + : table(x, a, m) + { + this->move_init(x); + } + + // Accessors + + std::size_t count(const_key_type& k) const + { + node_pointer n = this->find_node(k); + return n ? node_algo::count(n, this) : 0; + } + + std::pair<iterator, iterator> equal_range(const_key_type& k) const + { + node_pointer n = this->find_node(k); + return std::make_pair( + iterator(n), iterator(n ? node_algo::next_group(n, this) : n)); + } + + // Equality + + bool equals(grouped_table_impl 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->value())); + if (!n2) + return false; + node_pointer end1 = node_algo::next_group(n1, this); + node_pointer end2 = node_algo::next_group(n2, this); + if (!group_equals(n1, end1, n2, end2)) + return false; + n1 = end1; + } + + return true; + } + + static bool group_equals( + node_pointer n1, node_pointer end1, node_pointer n2, node_pointer end2) + { + for (;;) { + if (n1->value() != n2->value()) + break; + + n1 = node_algo::next_node(n1); + n2 = node_algo::next_node(n2); + + if (n1 == end1) + return n2 == end2; + if (n2 == end2) + return false; + } + + for (node_pointer n1a = n1, n2a = n2;;) { + n1a = node_algo::next_node(n1a); + n2a = node_algo::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 = node_algo::next_node(n1)) { + value_type const& v = n1->value(); + if (!find(start, n1, v)) { + std::size_t matches = count_equal(n2, end2, v); + if (!matches) + return false; + if (matches != + 1 + count_equal(node_algo::next_node(n1), end1, v)) + return false; + } + } + + return true; + } + + static bool find(node_pointer n, node_pointer end, value_type const& v) + { + for (; n != end; n = node_algo::next_node(n)) + if (n->value() == v) + return true; + return false; + } + + static std::size_t count_equal( + node_pointer n, node_pointer end, value_type const& v) + { + std::size_t count = 0; + for (; n != end; n = node_algo::next_node(n)) + if (n->value() == v) + ++count; + return count; + } + + // Emplace/Insert + + inline node_pointer add_node( + node_pointer n, std::size_t key_hash, node_pointer pos) + { + n->hash_ = key_hash; + if (pos) { + node_algo::add_to_node_group(n, pos); + if (n->next_) { + std::size_t next_bucket = + this->hash_to_bucket(node_algo::next_node(n)->hash_); + if (next_bucket != this->hash_to_bucket(key_hash)) { + this->get_bucket(next_bucket)->next_ = n; + } + } + } else { + bucket_pointer b = this->get_bucket(this->hash_to_bucket(key_hash)); + + if (!b->next_) { + link_pointer start_node = this->get_previous_start(); + + if (start_node->next_) { + this->get_bucket( + this->hash_to_bucket( + node_algo::next_node(start_node)->hash_)) + ->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(node_pointer n, node_pointer hint) + { + n->hash_ = hint->hash_; + node_algo::add_to_node_group(n, hint); + if (n->next_ != hint && n->next_) { + std::size_t next_bucket = + this->hash_to_bucket(node_algo::next_node(n)->hash_); + if (next_bucket != this->hash_to_bucket(n->hash_)) { + this->get_bucket(next_bucket)->next_ = n; + } + } + ++this->size_; + return n; + } + +#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) +#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + iterator emplace(boost::unordered::detail::emplace_args1< + boost::unordered::detail::please_ignore_this_overload> const&) + { + BOOST_ASSERT(false); + return iterator(); + } + + iterator emplace_hint( + c_iterator, + boost::unordered::detail::emplace_args1< + boost::unordered::detail::please_ignore_this_overload> const&) + { + BOOST_ASSERT(false); + return iterator(); + } +#else + iterator emplace( + boost::unordered::detail::please_ignore_this_overload const&) + { + BOOST_ASSERT(false); + return iterator(); + } + + iterator emplace_hint(c_iterator, + boost::unordered::detail::please_ignore_this_overload const&) + { + BOOST_ASSERT(false); + return iterator(); + } +#endif +#endif + + template <BOOST_UNORDERED_EMPLACE_TEMPLATE> + iterator emplace(BOOST_UNORDERED_EMPLACE_ARGS) + { + return iterator(emplace_impl( + boost::unordered::detail::func::construct_node_from_args( + this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD))); + } + + template <BOOST_UNORDERED_EMPLACE_TEMPLATE> + iterator emplace_hint(c_iterator hint, BOOST_UNORDERED_EMPLACE_ARGS) + { + return iterator(emplace_hint_impl( + hint, boost::unordered::detail::func::construct_node_from_args( + this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD))); + } + + iterator emplace_impl(node_pointer n) + { + node_tmp a(n, this->node_alloc()); + const_key_type& k = this->get_key(a.node_->value()); + 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(a.release(), key_hash, position)); + } + + iterator emplace_hint_impl(c_iterator hint, node_pointer n) + { + node_tmp a(n, this->node_alloc()); + const_key_type& k = this->get_key(a.node_->value()); + if (hint.node_ && this->key_eq()(k, this->get_key(*hint))) { + this->reserve_for_insert(this->size_ + 1); + return iterator(this->add_using_hint(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(a.release(), key_hash, position)); + } + } + + void emplace_impl_no_rehash(node_pointer n) + { + node_tmp a(n, this->node_alloc()); + const_key_type& k = this->get_key(a.node_->value()); + std::size_t key_hash = this->hash(k); + node_pointer position = this->find_node(key_hash, k); + this->add_node(a.release(), key_hash, position); + } + + template <typename NodeType> iterator move_insert_node_type(NodeType& np) + { + iterator result; + + if (np) { + const_key_type& k = this->get_key(np.ptr_->value()); + 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(np.ptr_, key_hash, pos)); + np.ptr_ = node_pointer(); + } + + return result; + } + + template <typename NodeType> + iterator move_insert_node_type_with_hint(c_iterator hint, NodeType& np) + { + iterator result; + + if (np) { + const_key_type& k = this->get_key(np.ptr_->value()); + + if (hint.node_ && this->key_eq()(k, this->get_key(*hint))) { + this->reserve_for_insert(this->size_ + 1); + result = iterator(this->add_using_hint(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(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(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_impl(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_impl_no_rehash( + boost::unordered::detail::func::construct_node( + this->node_alloc(), *i)); + } + } + } + + template <class I> + void insert_range(I i, I j, + typename boost::unordered::detail::disable_if_forward<I, void*>::type = + 0) + { + for (; i != j; ++i) { + emplace_impl(boost::unordered::detail::func::construct_node( + this->node_alloc(), *i)); + } + } + + //////////////////////////////////////////////////////////////////////// + // Extract + + inline node_pointer extract_by_iterator(c_iterator n) + { + node_pointer i = n.node_; + BOOST_ASSERT(i); + node_pointer j(node_algo::next_node(i)); + std::size_t bucket_index = this->hash_to_bucket(i->hash_); + // Split the groups containing 'i' and 'j'. + // And get the pointer to the node before i while + // we're at it. + link_pointer prev = node_algo::split_groups(i, j); + + // If we don't have a 'prev' it means that i is at the + // beginning of a block, so search through the blocks in the + // same bucket. + if (!prev) { + prev = this->get_previous_start(bucket_index); + while (prev->next_ != i) { + prev = node_algo::next_for_erase(prev); + } + } + + prev->next_ = i->next_; + --this->size_; + this->fix_bucket(bucket_index, prev); + i->next_ = link_pointer(); + + return i; + } + + //////////////////////////////////////////////////////////////////////// + // Erase + // + // no throw + + std::size_t erase_key(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, key_hash, bucket_index); + if (!prev) + return 0; + + node_pointer first_node = node_algo::next_node(prev); + link_pointer end = node_algo::next_group(first_node, this); + + std::size_t deleted_count = this->delete_nodes(prev, end); + this->fix_bucket(bucket_index, prev); + return deleted_count; + } + + iterator erase(c_iterator r) + { + BOOST_ASSERT(r.node_); + node_pointer next = node_algo::next_node(r.node_); + erase_nodes(r.node_, next); + return iterator(next); + } + + iterator erase_range(c_iterator r1, c_iterator r2) + { + if (r1 == r2) + return iterator(r2.node_); + erase_nodes(r1.node_, r2.node_); + return iterator(r2.node_); + } + + link_pointer erase_nodes(node_pointer i, node_pointer j) + { + std::size_t bucket_index = this->hash_to_bucket(i->hash_); + + // Split the groups containing 'i' and 'j'. + // And get the pointer to the node before i while + // we're at it. + link_pointer prev = node_algo::split_groups(i, j); + + // If we don't have a 'prev' it means that i is at the + // beginning of a block, so search through the blocks in the + // same bucket. + if (!prev) { + prev = this->get_previous_start(bucket_index); + while (prev->next_ != i) { + prev = node_algo::next_for_erase(prev); + } + } + + // Delete the nodes. + // Is it inefficient to call fix_bucket for every node? + do { + this->delete_node(prev); + bucket_index = this->fix_bucket(bucket_index, prev); + } while (prev->next_ != j); + + return prev; + } + + //////////////////////////////////////////////////////////////////////// + // fill_buckets + + void copy_buckets(table const& src) + { + this->create_buckets(this->bucket_count_); + + for (node_pointer n = src.begin(); n;) { + std::size_t key_hash = n->hash_; + node_pointer group_end(node_algo::next_group(n, this)); + node_pointer pos = + this->add_node(boost::unordered::detail::func::construct_node( + this->node_alloc(), n->value()), + key_hash, node_pointer()); + for (n = node_algo::next_node(n); n != group_end; + n = node_algo::next_node(n)) { + this->add_node(boost::unordered::detail::func::construct_node( + this->node_alloc(), n->value()), + key_hash, pos); + } + } + } + + void move_buckets(table const& src) + { + this->create_buckets(this->bucket_count_); + + for (node_pointer n = src.begin(); n;) { + std::size_t key_hash = n->hash_; + node_pointer group_end(node_algo::next_group(n, this)); + node_pointer pos = + this->add_node(boost::unordered::detail::func::construct_node( + this->node_alloc(), boost::move(n->value())), + key_hash, node_pointer()); + for (n = node_algo::next_node(n); n != group_end; + n = node_algo::next_node(n)) { + this->add_node(boost::unordered::detail::func::construct_node( + this->node_alloc(), boost::move(n->value())), + key_hash, pos); + } + } + } + + void assign_buckets(table const& src) + { + node_holder<node_allocator> holder(*this); + for (node_pointer n = src.begin(); n;) { + std::size_t key_hash = n->hash_; + node_pointer group_end(node_algo::next_group(n, this)); + node_pointer pos = this->add_node( + holder.copy_of(n->value()), key_hash, node_pointer()); + for (n = node_algo::next_node(n); n != group_end; + n = node_algo::next_node(n)) { + this->add_node(holder.copy_of(n->value()), key_hash, pos); + } + } + } + + void move_assign_buckets(table& src) + { + node_holder<node_allocator> holder(*this); + for (node_pointer n = src.begin(); n;) { + std::size_t key_hash = n->hash_; + node_pointer group_end(node_algo::next_group(n, this)); + node_pointer pos = this->add_node( + holder.move_copy_of(n->value()), key_hash, node_pointer()); + for (n = node_algo::next_node(n); n != group_end; + n = node_algo::next_node(n)) { + this->add_node(holder.move_copy_of(n->value()), key_hash, pos); + } + } + } +}; +} +} +} + +#endif |