diff options
Diffstat (limited to 'boost/unordered')
| -rw-r--r-- | boost/unordered/detail/allocate.hpp | 1246 | ||||
| -rw-r--r-- | boost/unordered/detail/allocator_helpers.hpp | 523 | ||||
| -rw-r--r-- | boost/unordered/detail/buckets.hpp | 519 | ||||
| -rw-r--r-- | boost/unordered/detail/emplace_args.hpp | 480 | ||||
| -rw-r--r-- | boost/unordered/detail/equivalent.hpp | 322 | ||||
| -rw-r--r-- | boost/unordered/detail/extract_key.hpp | 12 | ||||
| -rw-r--r-- | boost/unordered/detail/fwd.hpp | 30 | ||||
| -rw-r--r-- | boost/unordered/detail/table.hpp | 319 | ||||
| -rw-r--r-- | boost/unordered/detail/unique.hpp | 272 | ||||
| -rw-r--r-- | boost/unordered/detail/util.hpp | 2 | ||||
| -rw-r--r-- | boost/unordered/unordered_map.hpp | 91 | ||||
| -rw-r--r-- | boost/unordered/unordered_map_fwd.hpp | 18 | ||||
| -rw-r--r-- | boost/unordered/unordered_set.hpp | 77 | ||||
| -rw-r--r-- | boost/unordered/unordered_set_fwd.hpp | 16 |
14 files changed, 2245 insertions, 1682 deletions
diff --git a/boost/unordered/detail/allocate.hpp b/boost/unordered/detail/allocate.hpp new file mode 100644 index 0000000000..5574c15855 --- /dev/null +++ b/boost/unordered/detail/allocate.hpp @@ -0,0 +1,1246 @@ + +// Copyright 2005-2011 Daniel James. +// Copyright 2009 Pablo Halpern. +// 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) + +// See http://www.boost.org/libs/unordered for documentation + +#ifndef BOOST_UNORDERED_ALLOCATE_HPP +#define BOOST_UNORDERED_ALLOCATE_HPP + +#if defined(_MSC_VER) && (_MSC_VER >= 1020) +# pragma once +#endif + +#include <boost/unordered/detail/fwd.hpp> +#include <boost/move/move.hpp> +#include <boost/preprocessor/cat.hpp> +#include <boost/preprocessor/inc.hpp> +#include <boost/preprocessor/dec.hpp> +#include <boost/preprocessor/repetition/enum.hpp> +#include <boost/preprocessor/repetition/enum_params.hpp> +#include <boost/preprocessor/repetition/enum_binary_params.hpp> +#include <boost/preprocessor/repetition/repeat_from_to.hpp> +#include <boost/type_traits/is_class.hpp> +#include <boost/type_traits/add_lvalue_reference.hpp> +#include <boost/tuple/tuple.hpp> +#include <boost/utility/enable_if.hpp> +#include <boost/utility/addressof.hpp> +#include <boost/detail/select_type.hpp> +#include <boost/assert.hpp> +#include <utility> + +#if !defined(BOOST_NO_CXX11_HDR_TUPLE) +#include <tuple> +#endif + +#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 + +#define BOOST_UNORDERED_EMPLACE_LIMIT 10 + +namespace boost { namespace unordered { namespace detail { + + //////////////////////////////////////////////////////////////////////////// + // Bits and pieces for implementing traits + + template <typename T> typename boost::add_lvalue_reference<T>::type make(); + struct choice9 { typedef char (&type)[9]; }; + struct choice8 : choice9 { typedef char (&type)[8]; }; + struct choice7 : choice8 { typedef char (&type)[7]; }; + struct choice6 : choice7 { typedef char (&type)[6]; }; + struct choice5 : choice6 { typedef char (&type)[5]; }; + struct choice4 : choice5 { typedef char (&type)[4]; }; + struct choice3 : choice4 { typedef char (&type)[3]; }; + struct choice2 : choice3 { typedef char (&type)[2]; }; + struct choice1 : choice2 { typedef char (&type)[1]; }; + choice1 choose(); + + typedef choice1::type yes_type; + typedef choice2::type no_type; + + struct private_type + { + private_type const &operator,(int) const; + }; + + template <typename T> + no_type is_private_type(T const&); + yes_type is_private_type(private_type const&); + + struct convert_from_anything { + template <typename T> + convert_from_anything(T const&); + }; + + //////////////////////////////////////////////////////////////////////////// + // emplace_args + // + // Either forwarding variadic arguments, or storing the arguments in + // emplace_args##n + +#if !defined(BOOST_NO_VARIADIC_TEMPLATES) + +#define BOOST_UNORDERED_EMPLACE_TEMPLATE typename... Args +#define BOOST_UNORDERED_EMPLACE_ARGS BOOST_FWD_REF(Args)... args +#define BOOST_UNORDERED_EMPLACE_FORWARD boost::forward<Args>(args)... + +#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 + +#else + +#define BOOST_UNORDERED_EMPLACE_TEMPLATE typename Args +#define BOOST_UNORDERED_EMPLACE_ARGS Args const& args +#define BOOST_UNORDERED_EMPLACE_FORWARD args + +#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(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; \ + } + +#define BOOST_UNORDERED_EMPLACE_ARGS1 create_emplace_args +#define BOOST_UNORDERED_EMPLACE_ARGS2 create_emplace_args +#define BOOST_UNORDERED_EMPLACE_ARGS3 create_emplace_args + +#if defined(BOOST_NO_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); + +#define BOOST_UNORDERED_EARGS_INIT(z, n, _) \ + BOOST_PP_CAT(a, n)( \ + boost::forward<BOOST_PP_CAT(A,n)>(BOOST_PP_CAT(b, 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); + +#define BOOST_UNORDERED_EARGS_INIT(z, n, _) \ + BOOST_PP_CAT(a, n)(BOOST_PP_CAT(b, n)) + +#endif + +BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, BOOST_UNORDERED_EARGS, + _) + +#undef BOOST_UNORDERED_DEFINE_EMPLACE_ARGS +#undef BOOST_UNORDERED_EARGS_MEMBER +#undef BOOST_UNORDERED_EARGS_INIT + +#endif + + //////////////////////////////////////////////////////////////////////////// + // rvalue parameters when type can't be a BOOST_RV_REF(T) parameter + // e.g. for int + +#if !defined(BOOST_NO_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 + + //////////////////////////////////////////////////////////////////////////// + // Construct from tuple + // + // Used for piecewise construction. + +#if !defined(__SUNPRO_CC) + +# define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(n, namespace_) \ + template<typename T> \ + void construct_from_tuple(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 T, BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ + void construct_from_tuple(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 T> \ + void construct_from_tuple_impl( \ + boost::unordered::detail::length<0>, 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 T, BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ + void construct_from_tuple_impl( \ + boost::unordered::detail::length<n>, 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 T, typename Tuple> + void construct_from_tuple(T* ptr, Tuple const& x) + { + construct_from_tuple_impl( + boost::unordered::detail::length< + boost::tuples::length<Tuple>::value>(), + ptr, x); + } + +#endif + + //////////////////////////////////////////////////////////////////////////// + // SFINAE traits for construction. + + // Decide which construction method to use for a three argument + // call. Note that this is difficult to do using overloads because + // the arguments are packed into 'emplace_args3'. + // + // The decision is made on the first argument. + + +#if defined(BOOST_UNORDERED_DEPRECATED_PAIR_CONSTRUCT) + template <typename A, typename B, typename A0> + struct emulation1 { + static choice1::type test(choice1, std::pair<A, B> const&); + static choice2::type test(choice2, A const&); + static choice3::type test(choice3, convert_from_anything const&); + + enum { value = + sizeof(test(choose(), boost::unordered::detail::make<A0>())) == + sizeof(choice2::type) }; + }; +#endif + + template <typename A, typename B, typename A0> + struct check3_base { + static choice1::type test(choice1, + boost::unordered::piecewise_construct_t); + +#if defined(BOOST_UNORDERED_DEPRECATED_PAIR_CONSTRUCT) + static choice2::type test(choice2, A const&); +#endif + + static choice3::type test(choice3, ...); + + enum { value = + sizeof(test(choose(), boost::unordered::detail::make<A0>())) }; + }; + + template <typename A, typename B, typename A0> + struct piecewise3 { + enum { value = check3_base<A,B,A0>::value == sizeof(choice1::type) }; + }; + +#if defined(BOOST_UNORDERED_DEPRECATED_PAIR_CONSTRUCT) + template <typename A, typename B, typename A0> + struct emulation3 { + enum { value = check3_base<A,B,A0>::value == sizeof(choice2::type) }; + }; + +#endif + +#if !defined(BOOST_NO_VARIADIC_TEMPLATES) + + //////////////////////////////////////////////////////////////////////////// + // Construct from variadic parameters + + template <typename T, typename... Args> + inline void construct_impl(T* address, BOOST_FWD_REF(Args)... args) + { + new((void*) address) T(boost::forward<Args>(args)...); + } + + template <typename A, typename B, typename A0, typename A1, typename A2> + inline typename enable_if<piecewise3<A, B, A0>, void>::type + construct_impl(std::pair<A, B>* address, + BOOST_FWD_REF(A0), BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2) + { + boost::unordered::detail::construct_from_tuple( + boost::addressof(address->first), boost::forward<A1>(a1)); + boost::unordered::detail::construct_from_tuple( + boost::addressof(address->second), boost::forward<A2>(a2)); + } + +#if defined(BOOST_UNORDERED_DEPRECATED_PAIR_CONSTRUCT) + + template <typename A, typename B, typename A0> + inline typename enable_if<emulation1<A, B, A0>, void>::type + construct_impl(std::pair<A, B>* address, BOOST_FWD_REF(A0) a0) + { + new((void*) boost::addressof(address->first)) A(boost::forward<A0>(a0)); + new((void*) boost::addressof(address->second)) B(); + } + + template <typename A, typename B, typename A0, typename A1, typename A2> + inline typename enable_if<emulation3<A, B, A0>, void>::type + construct_impl(std::pair<A, B>* address, + BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2) + { + new((void*) boost::addressof(address->first)) A(boost::forward<A0>(a0)); + new((void*) boost::addressof(address->second)) B( + boost::forward<A1>(a1), + boost::forward<A2>(a2)); + } + + template <typename A, typename B, + typename A0, typename A1, typename A2, typename A3, + typename... Args> + inline void construct_impl(std::pair<A, B>* address, + BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2, + BOOST_FWD_REF(A3) a3, BOOST_FWD_REF(Args)... args) + { + new((void*) boost::addressof(address->first)) A(boost::forward<A0>(a0)); + + new((void*) boost::addressof(address->second)) B( + boost::forward<A1>(a1), + boost::forward<A2>(a2), + boost::forward<A3>(a3), + boost::forward<Args>(args)...); + } + +#endif // BOOST_UNORDERED_DEPRECATED_PAIR_CONSTRUCT + +#else // BOOST_NO_VARIADIC_TEMPLATES + +//////////////////////////////////////////////////////////////////////////////// +// Construct from emplace_args + +#define BOOST_UNORDERED_CONSTRUCT_IMPL(z, num_params, _) \ + template < \ + typename T, \ + BOOST_PP_ENUM_PARAMS_Z(z, num_params, typename A) \ + > \ + inline void construct_impl(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)); \ + } + + template <typename T, typename A0> + inline void construct_impl(T* address, emplace_args1<A0> const& args) + { + new((void*) address) T(boost::forward<A0>(args.a0)); + } + + template <typename T, typename A0, typename A1> + inline void construct_impl(T* address, emplace_args2<A0, A1> const& args) + { + new((void*) address) T( + boost::forward<A0>(args.a0), + boost::forward<A1>(args.a1) + ); + } + + template <typename T, typename A0, typename A1, typename A2> + inline void construct_impl(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) + ); + } + + BOOST_PP_REPEAT_FROM_TO(4, BOOST_UNORDERED_EMPLACE_LIMIT, + BOOST_UNORDERED_CONSTRUCT_IMPL, _) + +#undef BOOST_UNORDERED_CONSTRUCT_IMPL + + template <typename A, typename B, typename A0, typename A1, typename A2> + inline void construct_impl(std::pair<A, B>* address, + boost::unordered::detail::emplace_args3<A0, A1, A2> const& args, + typename enable_if<piecewise3<A, B, A0>, void*>::type = 0) + { + boost::unordered::detail::construct_from_tuple( + boost::addressof(address->first), args.a1); + boost::unordered::detail::construct_from_tuple( + boost::addressof(address->second), args.a2); + } + +#if defined(BOOST_UNORDERED_DEPRECATED_PAIR_CONSTRUCT) + + template <typename A, typename B, typename A0> + inline void construct_impl(std::pair<A, B>* address, + boost::unordered::detail::emplace_args1<A0> const& args, + typename enable_if<emulation1<A, B, A0>, void*>::type = 0) + { + new((void*) boost::addressof(address->first)) A( + boost::forward<A0>(args.a0)); + new((void*) boost::addressof(address->second)) B(); + } + + template <typename A, typename B, typename A0, typename A1, typename A2> + inline void construct_impl(std::pair<A, B>* address, + boost::unordered::detail::emplace_args3<A0, A1, A2> const& args, + typename enable_if<emulation3<A, B, A0>, void*>::type = 0) + { + new((void*) boost::addressof(address->first)) A( + boost::forward<A0>(args.a0)); + new((void*) boost::addressof(address->second)) B( + boost::forward<A1>(args.a1), + boost::forward<A2>(args.a2)); + } + +#define BOOST_UNORDERED_CONSTRUCT_PAIR_IMPL(z, num_params, _) \ + template <typename A, typename B, \ + BOOST_PP_ENUM_PARAMS_Z(z, num_params, typename A) \ + > \ + inline void construct_impl(std::pair<A, B>* address, \ + boost::unordered::detail::BOOST_PP_CAT(emplace_args, num_params) < \ + BOOST_PP_ENUM_PARAMS_Z(z, num_params, A) \ + > const& args) \ + { \ + new((void*) boost::addressof(address->first)) A( \ + boost::forward<A0>(args.a0)); \ + new((void*) boost::addressof(address->second)) B( \ + BOOST_PP_ENUM_##z(BOOST_PP_DEC(num_params), \ + BOOST_UNORDERED_CALL_FORWARD2, args.a)); \ + } + +#define BOOST_UNORDERED_CALL_FORWARD2(z, i, a) \ + BOOST_UNORDERED_CALL_FORWARD(z, BOOST_PP_INC(i), a) + + BOOST_UNORDERED_CONSTRUCT_PAIR_IMPL(1, 2, _) + BOOST_PP_REPEAT_FROM_TO(4, BOOST_UNORDERED_EMPLACE_LIMIT, + BOOST_UNORDERED_CONSTRUCT_PAIR_IMPL, _) + +#undef BOOST_UNORDERED_CONSTRUCT_PAIR_IMPL +#undef BOOST_UNORDERED_CALL_FORWARD2 + +#endif // BOOST_UNORDERED_DEPRECATED_PAIR_CONSTRUCT +#endif // BOOST_NO_VARIADIC_TEMPLATES + +}}} + +//////////////////////////////////////////////////////////////////////////////// +// +// 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(__GXX_EXPERIMENTAL_CXX0X__) && \ + (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 7)) +# define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 0 +# 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 + +//////////////////////////////////////////////////////////////////////////////// +// +// Some utilities for implementing allocator_traits, but useful elsewhere so +// they're always defined. + +#if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS) +# include <type_traits> +#endif + +namespace boost { namespace unordered { namespace detail { + + //////////////////////////////////////////////////////////////////////////// + // Integral_constrant, true_type, false_type + // + // Uses the standard versions if available. + +#if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS) + + using std::integral_constant; + using std::true_type; + using std::false_type; + +#else + + template <typename T, T Value> + struct integral_constant { enum { value = Value }; }; + + typedef boost::unordered::detail::integral_constant<bool, true> true_type; + typedef boost::unordered::detail::integral_constant<bool, false> false_type; + +#endif + + //////////////////////////////////////////////////////////////////////////// + // Explicitly call a destructor + +#if defined(BOOST_MSVC) +#pragma warning(push) +#pragma warning(disable:4100) // unreferenced formal parameter +#endif + + 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, unsigned int> struct expr_test; + template <typename T> struct expr_test<T, sizeof(char)> : T {}; + template <typename U> static char for_expr_test(U const&); + +# define BOOST_UNORDERED_CHECK_EXPRESSION(count, result, expression) \ + template <typename U> \ + static typename boost::unordered::detail::expr_test< \ + BOOST_PP_CAT(choice, result), \ + sizeof(boost::unordered::detail::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) \ + { \ + 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/utility/enable_if.hpp> +# include <boost/pointer_to_other.hpp> +# if defined(BOOST_NO_SFINAE_EXPR) +# include <boost/type_traits/is_same.hpp> +# endif + +# if !defined(BOOST_NO_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 { + + // TODO: Does this match std::allocator_traits<Alloc>::rebind_alloc<T>? + template <typename Alloc, typename T> + struct rebind_wrap + { + typedef typename Alloc::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_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 + + 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)(); + } + + 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; + + // TODO: rebind_alloc and rebind_traits + + 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 ((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::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 ((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::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 ((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::destroy(p); + } + +# endif + + static size_type max_size(const Alloc& a) + { + return boost::unordered::detail::call_max_size<size_type>(a); + } + + // Allocator propagation on construction + + static Alloc select_on_container_copy_construction(Alloc const& rhs) + { + return boost::unordered::detail:: + 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 + +//////////////////////////////////////////////////////////////////////////////// +// +// Some helper functions for allocating & constructing + +namespace boost { namespace unordered { namespace detail { + + //////////////////////////////////////////////////////////////////////////// + // + // construct_node/destroy_node + // + // Construct a node using the best available method. + +#if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT + + template <typename Alloc, typename T, BOOST_UNORDERED_EMPLACE_TEMPLATE> + inline void construct_node(Alloc& a, T* p, BOOST_UNORDERED_EMPLACE_ARGS) + { + boost::unordered::detail::allocator_traits<Alloc>::construct( + a, p, BOOST_UNORDERED_EMPLACE_FORWARD); + } + + template <typename Alloc, typename T> + inline void destroy_node(Alloc& a, T* p) + { + boost::unordered::detail::allocator_traits<Alloc>::destroy(a, p); + } + +#else + + template <typename AllocTraits, typename T> + struct value_construct + { + typedef BOOST_DEDUCED_TYPENAME AllocTraits::allocator_type allocator; + + allocator& alloc; + T* ptr; + + value_construct(allocator& a, T* p) : alloc(a), ptr(p) + { + AllocTraits::construct(alloc, ptr, T()); + } + + void release() + { + ptr = 0; + } + + ~value_construct() + { + if (ptr) AllocTraits::destroy(alloc, ptr); + } + + private: + value_construct(value_construct const&); + value_construct& operator=(value_construct const&); + }; + + template <typename Alloc, typename T, BOOST_UNORDERED_EMPLACE_TEMPLATE> + inline void construct_node(Alloc& a, T* p, BOOST_UNORDERED_EMPLACE_ARGS) + { + value_construct<boost::unordered::detail::allocator_traits<Alloc>, T> + construct_guard(a, p); + boost::unordered::detail::construct_impl( + p->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD); + construct_guard.release(); + } + + template <typename Alloc, typename T> + inline void destroy_node(Alloc& a, T* p) + { + boost::unordered::detail::destroy(p->value_ptr()); + boost::unordered::detail::allocator_traits<Alloc>::destroy(a, p); + } + +#endif + + //////////////////////////////////////////////////////////////////////////// + // + // array_constructor + // + // Allocate and construct an array in an exception safe manner, and + // clean up if an exception is thrown before the container takes charge + // of it. + + template <typename Allocator> + struct array_constructor + { + typedef boost::unordered::detail::allocator_traits<Allocator> traits; + typedef typename traits::pointer pointer; + + Allocator& alloc_; + pointer ptr_; + pointer constructed_; + std::size_t length_; + + array_constructor(Allocator& a) + : alloc_(a), ptr_(), constructed_(), length_(0) + { + constructed_ = pointer(); + ptr_ = pointer(); + } + + ~array_constructor() { + if (ptr_) { + for(pointer p = ptr_; p != constructed_; ++p) + traits::destroy(alloc_, boost::addressof(*p)); + + traits::deallocate(alloc_, ptr_, length_); + } + } + + template <typename V> + void construct(V const& v, std::size_t l) + { + BOOST_ASSERT(!ptr_); + length_ = l; + ptr_ = traits::allocate(alloc_, length_); + pointer end = ptr_ + static_cast<std::ptrdiff_t>(length_); + for(constructed_ = ptr_; constructed_ != end; ++constructed_) + traits::construct(alloc_, boost::addressof(*constructed_), v); + } + + pointer get() const + { + return ptr_; + } + + pointer release() + { + pointer p(ptr_); + ptr_ = pointer(); + return p; + } + + private: + + array_constructor(array_constructor const&); + array_constructor& operator=(array_constructor const&); + }; +}}} + +#if defined(BOOST_MSVC) +#pragma warning(pop) +#endif + +#endif diff --git a/boost/unordered/detail/allocator_helpers.hpp b/boost/unordered/detail/allocator_helpers.hpp deleted file mode 100644 index dbba504698..0000000000 --- a/boost/unordered/detail/allocator_helpers.hpp +++ /dev/null @@ -1,523 +0,0 @@ - -// Copyright 2005-2011 Daniel James. -// Copyright 2009 Pablo Halpern. -// -// 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) -// -// Allocator traits written by Daniel James based on Pablo Halpern's -// implementation. - -#ifndef BOOST_UNORDERED_DETAIL_ALLOCATOR_UTILITIES_HPP_INCLUDED -#define BOOST_UNORDERED_DETAIL_ALLOCATOR_UTILITIES_HPP_INCLUDED - -#if defined(_MSC_VER) && (_MSC_VER >= 1020) -# pragma once -#endif - -#include <boost/config.hpp> -#include <boost/detail/select_type.hpp> -#include <boost/utility/enable_if.hpp> -#include <boost/preprocessor/cat.hpp> -#include <boost/preprocessor/enum.hpp> -#include <boost/limits.hpp> -#include <boost/type_traits/add_lvalue_reference.hpp> -#include <boost/pointer_to_other.hpp> -#include <boost/assert.hpp> -#include <boost/utility/addressof.hpp> - -#if !defined(BOOST_UNORDERED_USE_ALLOCATOR_TRAITS) -#define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 0 -#endif - -#if BOOST_UNORDERED_USE_ALLOCATOR_TRAITS -# include <memory> -#endif - -#if !defined(BOOST_NO_0X_HDR_TYPE_TRAITS) -# include <type_traits> -#endif - -namespace boost { namespace unordered { namespace detail { - - //////////////////////////////////////////////////////////////////////////// - // Integral_constrant, true_type, false_type - // - // Uses the standard versions if available. - -#if !defined(BOOST_NO_0X_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 - - template <class T> - inline void destroy(T* x) { - x->~T(); - } - -#if defined(BOOST_MSVC) -#pragma warning(pop) -#endif - - //////////////////////////////////////////////////////////////////////////// - // Bits and pieces for implementing traits - // - // Some of these are also used elsewhere - - 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&); - }; - -#if !defined(BOOST_NO_SFINAE_EXPR) - -# define BOOST_UNORDERED_HAVE_CALL_DETECTION 1 - - template <typename T, unsigned int> struct expr_test; - template <typename T> struct expr_test<T, sizeof(char)> : T {}; - template <typename U> static char for_expr_test(U const&); - -#define BOOST_UNORDERED_CHECK_EXPRESSION(count, result, expression) \ - template <typename U> \ - static typename boost::unordered::detail::expr_test< \ - BOOST_PP_CAT(choice, result), \ - sizeof(boost::unordered::detail::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) \ - { \ - 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 - -# define BOOST_UNORDERED_HAVE_CALL_DETECTION 0 - - 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 - // - // Uses the standard versions if available. - // (although untested as I don't have access to a standard version yet) - -#if BOOST_UNORDERED_USE_ALLOCATOR_TRAITS - - 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; - }; - -#else - - // TODO: Does this match std::allocator_traits<Alloc>::rebind_alloc<T>? - template <typename Alloc, typename T> - struct rebind_wrap - { - typedef typename Alloc::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 BOOST_UNORDERED_HAVE_CALL_DETECTION - 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 - ); - - template <typename T, typename ValueType> - BOOST_UNORDERED_HAS_FUNCTION( - construct, U, ( - boost::unordered::detail::make<ValueType*>(), - boost::unordered::detail::make<ValueType const>()), 2 - ); - - 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 - - template <typename Alloc> - inline typename boost::enable_if_c< - boost::unordered::detail:: - has_select_on_container_copy_construction<Alloc>::value, Alloc - >::type call_select_on_container_copy_construction(const Alloc& rhs) - { - return rhs.select_on_container_copy_construction(); - } - - template <typename Alloc> - inline typename boost::disable_if_c< - boost::unordered::detail:: - has_select_on_container_copy_construction<Alloc>::value, Alloc - >::type call_select_on_container_copy_construction(const Alloc& rhs) - { - return rhs; - } - - template <typename SizeType, typename Alloc> - inline typename boost::enable_if_c< - boost::unordered::detail::has_max_size<Alloc>::value, SizeType - >::type call_max_size(const Alloc& a) - { - return a.max_size(); - } - - template <typename SizeType, typename Alloc> - inline typename boost::disable_if_c< - boost::unordered::detail::has_max_size<Alloc>::value, SizeType - >::type call_max_size(const Alloc&) - { - return (std::numeric_limits<SizeType>::max)(); - } - - 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; - - // TODO: rebind_alloc and rebind_traits - - 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: - - // Only supporting the basic copy constructor for now. - - 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 ((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::destroy(p); - } - - static size_type max_size(const Alloc& a) - { - return boost::unordered::detail::call_max_size<size_type>(a); - } - - // Allocator propagation on construction - - static Alloc select_on_container_copy_construction(Alloc const& rhs) - { - return boost::unordered::detail:: - 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 - -#endif - - // array_constructor - // - // Allocate and construct an array in an exception safe manner, and - // clean up if an exception is thrown before the container takes charge - // of it. - - template <typename Allocator> - struct array_constructor - { - typedef boost::unordered::detail::allocator_traits<Allocator> traits; - typedef typename traits::pointer pointer; - - Allocator& alloc_; - pointer ptr_; - pointer constructed_; - std::size_t length_; - - array_constructor(Allocator& a) - : alloc_(a), ptr_(), constructed_(), length_(0) - { - constructed_ = pointer(); - ptr_ = pointer(); - } - - ~array_constructor() { - if (ptr_) { - for(pointer p = ptr_; p != constructed_; ++p) - traits::destroy(alloc_, boost::addressof(*p)); - - traits::deallocate(alloc_, ptr_, length_); - } - } - - template <typename V> - void construct(V const& v, std::size_t l) - { - BOOST_ASSERT(!ptr_); - length_ = l; - ptr_ = traits::allocate(alloc_, length_); - pointer end = ptr_ + static_cast<std::ptrdiff_t>(length_); - for(constructed_ = ptr_; constructed_ != end; ++constructed_) - traits::construct(alloc_, boost::addressof(*constructed_), v); - } - - pointer get() const - { - return ptr_; - } - - pointer release() - { - pointer p(ptr_); - ptr_ = pointer(); - return p; - } - private: - array_constructor(array_constructor const&); - array_constructor& operator=(array_constructor const&); - }; -}}} - -#endif diff --git a/boost/unordered/detail/buckets.hpp b/boost/unordered/detail/buckets.hpp index 7492220b16..85681a685c 100644 --- a/boost/unordered/detail/buckets.hpp +++ b/boost/unordered/detail/buckets.hpp @@ -12,12 +12,13 @@ #endif #include <boost/unordered/detail/util.hpp> -#include <boost/unordered/detail/allocator_helpers.hpp> -#include <boost/unordered/detail/emplace_args.hpp> +#include <boost/unordered/detail/allocate.hpp> #include <boost/type_traits/aligned_storage.hpp> #include <boost/type_traits/alignment_of.hpp> #include <boost/swap.hpp> #include <boost/assert.hpp> +#include <boost/limits.hpp> +#include <boost/iterator.hpp> #if defined(BOOST_MSVC) #pragma warning(push) @@ -29,7 +30,10 @@ namespace boost { namespace unordered { namespace detail { template <typename Types> struct table; template <typename NodePointer> struct bucket; struct ptr_bucket; - template <typename A, typename Bucket, typename Node> struct buckets; + template <typename A, typename Bucket, typename Node, typename Policy> + struct buckets; + template <typename Types> struct table_impl; + template <typename Types> struct grouped_table_impl; /////////////////////////////////////////////////////////////////// // @@ -49,16 +53,14 @@ namespace boost { namespace unordered { namespace detail { node_allocator& alloc_; node_pointer node_; - bool node_constructed_; - bool value_constructed_; + bool constructed_; public: node_constructor(node_allocator& n) : alloc_(n), node_(), - node_constructed_(false), - value_constructed_(false) + constructed_(false) { } @@ -69,26 +71,36 @@ namespace boost { namespace unordered { namespace detail { template <BOOST_UNORDERED_EMPLACE_TEMPLATE> void construct_value(BOOST_UNORDERED_EMPLACE_ARGS) { - BOOST_ASSERT(node_ && node_constructed_ && !value_constructed_); - boost::unordered::detail::construct_impl( - node_->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD); - value_constructed_ = true; + BOOST_ASSERT(node_ && !constructed_); + boost::unordered::detail::construct_node(alloc_, + boost::addressof(*node_), BOOST_UNORDERED_EMPLACE_FORWARD); + node_->init(static_cast<typename node::link_pointer>(node_)); + constructed_ = true; } template <typename A0> void construct_value2(BOOST_FWD_REF(A0) a0) { - BOOST_ASSERT(node_ && node_constructed_ && !value_constructed_); - boost::unordered::detail::construct_impl2( - node_->value_ptr(), boost::forward<A0>(a0)); - value_constructed_ = true; + BOOST_ASSERT(node_ && !constructed_); + + boost::unordered::detail::construct_node(alloc_, + boost::addressof(*node_), + BOOST_UNORDERED_EMPLACE_ARGS1(boost::forward<A0>(a0))); + + constructed_ = true; + node_->init(static_cast<typename node::link_pointer>(node_)); } value_type const& value() const { - BOOST_ASSERT(node_ && node_constructed_ && value_constructed_); + BOOST_ASSERT(node_ && constructed_); return node_->value(); } + node_pointer get() + { + return node_; + } + // no throw node_pointer release() { @@ -106,12 +118,8 @@ namespace boost { namespace unordered { namespace detail { node_constructor<Alloc>::~node_constructor() { if (node_) { - if (value_constructed_) { - boost::unordered::detail::destroy(node_->value_ptr()); - } - - if (node_constructed_) { - node_allocator_traits::destroy(alloc_, + if (constructed_) { + boost::unordered::detail::destroy_node(alloc_, boost::addressof(*node_)); } @@ -123,24 +131,13 @@ namespace boost { namespace unordered { namespace detail { void node_constructor<Alloc>::construct_node() { if(!node_) { - node_constructed_ = false; - value_constructed_ = false; - + constructed_ = false; node_ = node_allocator_traits::allocate(alloc_, 1); - - node_allocator_traits::construct(alloc_, - boost::addressof(*node_), node()); - node_->init(static_cast<typename node::link_pointer>(node_)); - node_constructed_ = true; } - else { - BOOST_ASSERT(node_constructed_); - - if (value_constructed_) - { - boost::unordered::detail::destroy(node_->value_ptr()); - value_constructed_ = false; - } + else if (constructed_) { + boost::unordered::detail::destroy_node(alloc_, + boost::addressof(*node_)); + constructed_ = false; } } @@ -179,12 +176,373 @@ namespace boost { namespace unordered { namespace detail { enum { extra_node = false }; }; + template <typename LinkPointer> + struct node_base + { + typedef LinkPointer link_pointer; + link_pointer next_; + + node_base() : next_() {} + }; + +}}} + +namespace boost { namespace unordered { namespace iterator_detail { + + //////////////////////////////////////////////////////////////////////////// + // Iterators + // + // all no throw + + template <typename NodePointer, typename Value> struct iterator; + template <typename ConstNodePointer, typename NodePointer, + typename Value> struct c_iterator; + template <typename NodePointer, typename Value, typename Policy> + struct l_iterator; + template <typename ConstNodePointer, typename NodePointer, + typename Value, typename Policy> struct cl_iterator; + + // Local Iterators + // + // all no throw + + template <typename NodePointer, typename Value, typename Policy> + struct l_iterator + : public boost::iterator< + std::forward_iterator_tag, Value, std::ptrdiff_t, + NodePointer, Value&> + { +#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) + template <typename ConstNodePointer, typename NodePointer2, + typename Value2, typename Policy2> + friend struct boost::unordered::iterator_detail::cl_iterator; + private: +#endif + typedef NodePointer node_pointer; + typedef boost::unordered::iterator_detail::iterator<NodePointer, Value> + iterator; + node_pointer ptr_; + std::size_t bucket_; + std::size_t bucket_count_; + + public: + + l_iterator() : ptr_() {} + + l_iterator(iterator x, std::size_t b, std::size_t c) + : ptr_(x.node_), bucket_(b), bucket_count_(c) {} + + Value& operator*() const { + return ptr_->value(); + } + + Value* 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 { + return ptr_ == x.ptr_; + } + + bool operator!=(l_iterator x) const { + return ptr_ != x.ptr_; + } + }; + + template <typename ConstNodePointer, typename NodePointer, typename Value, + typename Policy> + struct cl_iterator + : public boost::iterator< + std::forward_iterator_tag, Value, std::ptrdiff_t, + ConstNodePointer, Value const&> + { + friend struct boost::unordered::iterator_detail::l_iterator + <NodePointer, Value, Policy>; + private: + + typedef NodePointer node_pointer; + typedef boost::unordered::iterator_detail::iterator<NodePointer, Value> + iterator; + node_pointer ptr_; + std::size_t bucket_; + std::size_t bucket_count_; + + public: + + cl_iterator() : ptr_() {} + + cl_iterator(iterator x, std::size_t b, std::size_t c) : + ptr_(x.node_), bucket_(b), bucket_count_(c) {} + + cl_iterator(boost::unordered::iterator_detail::l_iterator< + NodePointer, Value, Policy> const& x) : + ptr_(x.ptr_), bucket_(x.bucket_), bucket_count_(x.bucket_count_) + {} + + Value const& + operator*() const { + return ptr_->value(); + } + + Value 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) { + return x.ptr_ == y.ptr_; + } + + friend bool operator!=(cl_iterator const& x, cl_iterator const& y) { + return x.ptr_ != y.ptr_; + } + }; + + template <typename NodePointer, typename Value> + struct iterator + : public boost::iterator< + std::forward_iterator_tag, Value, std::ptrdiff_t, + NodePointer, Value&> + { +#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) + template <typename, typename, typename> + friend struct boost::unordered::iterator_detail::c_iterator; + template <typename, typename, typename> + friend struct boost::unordered::iterator_detail::l_iterator; + template <typename, typename, typename, typename> + friend struct boost::unordered::iterator_detail::cl_iterator; + template <typename> + friend struct boost::unordered::detail::table; + template <typename, typename, typename, typename> + friend struct boost::unordered::detail::buckets; + template <typename> + friend struct boost::unordered::detail::table_impl; + template <typename> + friend struct boost::unordered::detail::grouped_table_impl; + private: +#endif + typedef NodePointer node_pointer; + node_pointer node_; + + public: + + iterator() : node_() {} + + explicit iterator(node_pointer const& x) : node_(x) {} + + Value& operator*() const { + return node_->value(); + } + + Value* operator->() const { + return &node_->value(); + } + + 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 { + return node_ == x.node_; + } + + bool operator!=(iterator const& x) const { + return node_ != x.node_; + } + }; + + template <typename ConstNodePointer, typename NodePointer, typename Value> + struct c_iterator + : public boost::iterator< + std::forward_iterator_tag, Value, std::ptrdiff_t, + ConstNodePointer, Value const&> + { + friend struct boost::unordered::iterator_detail::iterator< + NodePointer, Value>; + +#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) + template <typename> + friend struct boost::unordered::detail::table; + template <typename, typename, typename, typename> + friend struct boost::unordered::detail::buckets; + template <typename> + friend struct boost::unordered::detail::table_impl; + template <typename> + friend struct boost::unordered::detail::grouped_table_impl; + + private: +#endif + + typedef NodePointer node_pointer; + typedef boost::unordered::iterator_detail::iterator<NodePointer, Value> + iterator; + node_pointer node_; + + public: + + c_iterator() : node_() {} + + explicit c_iterator(node_pointer const& x) : node_(x) {} + + c_iterator(boost::unordered::iterator_detail::iterator< + NodePointer, Value> const& x) : node_(x.node_) {} + + Value const& operator*() const { + return node_->value(); + } + + Value const* operator->() const { + return &node_->value(); + } + + 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) { + return x.node_ == y.node_; + } + + friend bool operator!=(c_iterator const& x, c_iterator const& y) { + return x.node_ != y.node_; + } + }; +}}} + +namespace boost { namespace unordered { namespace detail { + + /////////////////////////////////////////////////////////////////// + // + // Hash Policy + // + // Don't really want buckets to derive from this, but will for now. + + 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; + }; + + struct pick_policy : + pick_policy_impl< + std::numeric_limits<std::size_t>::digits, + std::numeric_limits<std::size_t>::radix> {}; + /////////////////////////////////////////////////////////////////// // // Buckets - template <typename A, typename Bucket, typename Node> - struct buckets + template <typename A, typename Bucket, typename Node, typename Policy> + struct buckets : Policy { private: buckets(buckets const&); @@ -193,6 +551,7 @@ namespace boost { namespace unordered { namespace detail { typedef boost::unordered::detail::allocator_traits<A> traits; typedef typename traits::value_type value_type; + typedef Policy policy; typedef Node node; typedef Bucket bucket; typedef typename boost::unordered::detail::rebind_wrap<A, node>::type @@ -214,6 +573,16 @@ namespace boost { namespace unordered { namespace detail { typedef boost::unordered::detail::node_constructor<node_allocator> node_constructor; + typedef boost::unordered::iterator_detail:: + iterator<node_pointer, value_type> iterator; + typedef boost::unordered::iterator_detail:: + c_iterator<const_node_pointer, node_pointer, value_type> c_iterator; + typedef boost::unordered::iterator_detail:: + l_iterator<node_pointer, value_type, policy> l_iterator; + typedef boost::unordered::iterator_detail:: + cl_iterator<const_node_pointer, node_pointer, value_type, policy> + cl_iterator; + // Members bucket_pointer buckets_; @@ -247,7 +616,7 @@ namespace boost { namespace unordered { namespace detail { std::size_t max_bucket_count() const { // -1 to account for the start bucket. - return boost::unordered::detail::prev_prime( + return policy::prev_bucket_count( bucket_allocator_traits::max_size(bucket_alloc()) - 1); } @@ -266,16 +635,17 @@ namespace boost { namespace unordered { namespace detail { return this->get_bucket(bucket_index)->next_; } - node_pointer get_start() const + iterator get_start() const { - return static_cast<node_pointer>(this->get_previous_start()->next_); + return iterator(static_cast<node_pointer>( + this->get_previous_start()->next_)); } - node_pointer get_start(std::size_t bucket_index) const + iterator get_start(std::size_t bucket_index) const { previous_pointer prev = this->get_previous_start(bucket_index); - return prev ? static_cast<node_pointer>(prev->next_) : - node_pointer(); + return prev ? iterator(static_cast<node_pointer>(prev->next_)) : + iterator(); } float load_factor() const @@ -288,14 +658,15 @@ namespace boost { namespace unordered { namespace detail { std::size_t bucket_size(std::size_t index) const { if (!this->size_) return 0; - node_pointer ptr = this->get_start(index); - if (!ptr) return 0; + iterator it = this->get_start(index); + if (!it.node_) return 0; std::size_t count = 0; - while(ptr && ptr->hash_ % this->bucket_count_ == index) + while(it.node_ && policy::to_bucket( + this->bucket_count_, it.node_->hash_) == index) { ++count; - ptr = static_cast<node_pointer>(ptr->next_); + ++it; } return count; @@ -349,6 +720,14 @@ namespace boost { namespace unordered { namespace detail { node_constructor a(this->node_alloc()); a.construct_node(); + // Since this node is just to mark the beginning it doesn't + // contain a value, so just construct node::node_base + // which containers the pointer to the next element. + node_allocator_traits::construct(node_alloc(), + static_cast<typename node::node_base*>( + boost::addressof(*a.get())), + typename node::node_base()); + (constructor.get() + static_cast<std::ptrdiff_t>(this->bucket_count_))->next_ = a.release(); @@ -391,21 +770,21 @@ namespace boost { namespace unordered { namespace detail { //////////////////////////////////////////////////////////////////////// // Delete/destruct - inline void delete_node(node_pointer n) + inline void delete_node(c_iterator n) { - boost::unordered::detail::destroy(n->value_ptr()); - node_allocator_traits::destroy(node_alloc(), boost::addressof(*n)); - node_allocator_traits::deallocate(node_alloc(), n, 1); + boost::unordered::detail::destroy_node( + node_alloc(), boost::addressof(*n.node_)); + node_allocator_traits::deallocate(node_alloc(), n.node_, 1); --size_; } - std::size_t delete_nodes(node_pointer begin, node_pointer end) + std::size_t delete_nodes(c_iterator begin, c_iterator end) { std::size_t count = 0; while(begin != end) { - node_pointer n = begin; - begin = static_cast<node_pointer>(begin->next_); + c_iterator n = begin; + ++begin; delete_node(n); ++count; } @@ -416,7 +795,8 @@ namespace boost { namespace unordered { namespace detail { inline void delete_extra_node(bucket_pointer) {} inline void delete_extra_node(node_pointer n) { - node_allocator_traits::destroy(node_alloc(), boost::addressof(*n)); + node_allocator_traits::destroy(node_alloc(), + static_cast<typename node::node_base*>(boost::addressof(*n))); node_allocator_traits::deallocate(node_alloc(), n, 1); } @@ -433,7 +813,7 @@ namespace boost { namespace unordered { namespace detail { while(prev->next_) { node_pointer n = static_cast<node_pointer>(prev->next_); prev->next_ = n->next_; - delete_node(n); + delete_node(iterator(n)); } delete_extra_node(prev); @@ -463,7 +843,7 @@ namespace boost { namespace unordered { namespace detail { while(prev->next_) { node_pointer n = static_cast<node_pointer>(prev->next_); prev->next_ = n->next_; - delete_node(n); + delete_node(iterator(n)); } bucket_pointer end = this->get_bucket(this->bucket_count_); @@ -477,22 +857,24 @@ namespace boost { namespace unordered { namespace detail { // This is called after erasing a node or group of nodes to fix up // the bucket pointers. - void fix_buckets(bucket_pointer bucket, + void fix_buckets(bucket_pointer this_bucket, previous_pointer prev, node_pointer next) { if (!next) { - if (bucket->next_ == prev) bucket->next_ = node_pointer(); + if (this_bucket->next_ == prev) + this_bucket->next_ = node_pointer(); } else { bucket_pointer next_bucket = this->get_bucket( - next->hash_ % this->bucket_count_); + policy::to_bucket(this->bucket_count_, next->hash_)); - if (next_bucket != bucket) + if (next_bucket != this_bucket) { next_bucket->next_ = prev; - if (bucket->next_ == prev) bucket->next_ = node_pointer(); + if (this_bucket->next_ == prev) + this_bucket->next_ = node_pointer(); } } } @@ -513,7 +895,7 @@ namespace boost { namespace unordered { namespace detail { if (n == end) return; std::size_t new_bucket_index = - n->hash_ % this->bucket_count_; + policy::to_bucket(this->bucket_count_, n->hash_); if (bucket_index != new_bucket_index) { bucket_index = new_bucket_index; break; @@ -529,7 +911,7 @@ namespace boost { namespace unordered { namespace detail { if (n == end) break; std::size_t new_bucket_index = - n->hash_ % this->bucket_count_; + policy::to_bucket(this->bucket_count_, n->hash_); if (bucket_index != new_bucket_index) { bucket_index = new_bucket_index; this->get_bucket(bucket_index)->next_ = previous_pointer(); @@ -538,7 +920,8 @@ namespace boost { namespace unordered { namespace detail { // Finally fix the bucket containing the trailing node. if (n) { - this->get_bucket(n->hash_ % this->bucket_count_)->next_ + this->get_bucket( + policy::to_bucket(this->bucket_count_, n->hash_))->next_ = prev; } } diff --git a/boost/unordered/detail/emplace_args.hpp b/boost/unordered/detail/emplace_args.hpp deleted file mode 100644 index 0e80d3c050..0000000000 --- a/boost/unordered/detail/emplace_args.hpp +++ /dev/null @@ -1,480 +0,0 @@ - -// Copyright (C) 2011 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) - -// See http://www.boost.org/libs/unordered for documentation - -#ifndef BOOST_UNORDERED_EMPLACE_ARGS_HPP -#define BOOST_UNORDERED_EMPLACE_ARGS_HPP - -#if defined(_MSC_VER) && (_MSC_VER >= 1020) -# pragma once -#endif - -#include <boost/move/move.hpp> -#include <boost/preprocessor/cat.hpp> -#include <boost/preprocessor/inc.hpp> -#include <boost/preprocessor/dec.hpp> -#include <boost/preprocessor/repetition/enum.hpp> -#include <boost/preprocessor/repetition/enum_params.hpp> -#include <boost/preprocessor/repetition/enum_binary_params.hpp> -#include <boost/preprocessor/repetition/repeat_from_to.hpp> -#include <boost/type_traits/is_class.hpp> -#include <boost/tuple/tuple.hpp> -#include <utility> - -#if !defined(BOOST_NO_0X_HDR_TUPLE) -#include <tuple> -#endif - -#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 - -#define BOOST_UNORDERED_EMPLACE_LIMIT 10 - -#if !defined(BOOST_NO_RVALUE_REFERENCES) && \ - !defined(BOOST_NO_VARIADIC_TEMPLATES) -#define BOOST_UNORDERED_VARIADIC_MOVE -#endif - -namespace boost { namespace unordered { namespace detail { - - //////////////////////////////////////////////////////////////////////////// - // emplace_args - // - // Either forwarding variadic arguments, or storing the arguments in - // emplace_args##n - -#if defined(BOOST_UNORDERED_VARIADIC_MOVE) - -#define BOOST_UNORDERED_EMPLACE_TEMPLATE typename... Args -#define BOOST_UNORDERED_EMPLACE_ARGS Args&&... args -#define BOOST_UNORDERED_EMPLACE_FORWARD boost::forward<Args>(args)... - -#else - -#define BOOST_UNORDERED_EMPLACE_TEMPLATE typename Args -#define BOOST_UNORDERED_EMPLACE_ARGS Args const& args -#define BOOST_UNORDERED_EMPLACE_FORWARD args - -#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(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, a) \ - ) : 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, a) \ - ) \ - { \ - BOOST_PP_CAT(emplace_args, n) < \ - BOOST_PP_ENUM_PARAMS_Z(z, n, A) \ - > e(BOOST_PP_ENUM_PARAMS_Z(z, n, a)); \ - return e; \ - } - -#if defined(BOOST_NO_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); - -#define BOOST_UNORDERED_EARGS_INIT(z, n, _) \ - BOOST_PP_CAT(a, n)( \ - boost::forward<BOOST_PP_CAT(A,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); - -#define BOOST_UNORDERED_EARGS_INIT(z, n, _) \ - BOOST_PP_CAT(a, n)(BOOST_PP_CAT(a, n)) - -#endif - -BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, BOOST_UNORDERED_EARGS, - _) - -#undef BOOST_UNORDERED_DEFINE_EMPLACE_ARGS -#undef BOOST_UNORDERED_EARGS_MEMBER -#undef BOOST_UNORDERED_EARGS_INIT - -#endif - - //////////////////////////////////////////////////////////////////////////// - // rvalue parameters when type can't be a BOOST_RV_REF(T) parameter - // e.g. for int - -#if !defined(BOOST_NO_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 - - //////////////////////////////////////////////////////////////////////////// - // Construct from tuple - // - // Used for piecewise construction. - -#if !BOOST_WORKAROUND(__SUNPRO_CC, <= 0x590) - -#define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(n, namespace_) \ - template<typename T> \ - void construct_from_tuple(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 T, BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ - void construct_from_tuple(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) - -BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(10, boost) - -#if !defined(BOOST_NO_0X_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 - -#else - - template <int N> struct length {}; - - template<typename T> - void construct_from_tuple_impl( - boost::unordered::detail::length<0>, T* ptr, - boost::tuple<>) - { - new ((void*) ptr) T(); - } - -#define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL(z, n, _) \ - template<typename T, BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ - void construct_from_tuple_impl( \ - boost::unordered::detail::length<n>, 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, _) \ - boost::get<n>(x) - - BOOST_PP_REPEAT_FROM_TO(1, 10, \ - BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL, _) - - template <typename T, typename Tuple> - void construct_from_tuple(T* ptr, Tuple const& x) - { - construct_from_tuple_impl( - boost::unordered::detail::length< - boost::tuples::length<Tuple>::value>(), - ptr, x); - } - -#undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL -#undef BOOST_UNORDERED_GET_TUPLE_ARG - -#endif - - //////////////////////////////////////////////////////////////////////////// - // SFINAE traits for construction. - - // Decide which construction method to use for a three argument - // call. Note that this is difficult to do using overloads because - // the arguments are packed into 'emplace_args3'. - // - // The decision is made on the first argument. - - -#if defined(BOOST_UNORDERED_DEPRECATED_PAIR_CONSTRUCT) - template <typename A, typename B, typename A0> - struct emulation1 { - static choice1::type test(choice1, std::pair<A, B> const&); - static choice2::type test(choice2, A const&); - static choice3::type test(choice3, convert_from_anything const&); - - enum { value = - sizeof(test(choose(), boost::unordered::detail::make<A0>())) == - sizeof(choice2::type) }; - }; -#endif - - template <typename A, typename B, typename A0> - struct check3_base { - static choice1::type test(choice1, - boost::unordered::piecewise_construct_t); - -#if defined(BOOST_UNORDERED_DEPRECATED_PAIR_CONSTRUCT) - static choice2::type test(choice2, A const&); -#endif - - static choice3::type test(choice3, ...); - - enum { value = - sizeof(test(choose(), boost::unordered::detail::make<A0>())) }; - }; - - template <typename A, typename B, typename A0> - struct piecewise3 { - enum { value = check3_base<A,B,A0>::value == sizeof(choice1::type) }; - }; - -#if defined(BOOST_UNORDERED_DEPRECATED_PAIR_CONSTRUCT) - template <typename A, typename B, typename A0> - struct emulation3 { - enum { value = check3_base<A,B,A0>::value == sizeof(choice2::type) }; - }; - -#endif - -#if defined(BOOST_UNORDERED_VARIADIC_MOVE) - - //////////////////////////////////////////////////////////////////////////// - // Construct from variadic parameters - - template <typename T, typename... Args> - inline void construct_impl(T* address, Args&&... args) - { - new((void*) address) T(boost::forward<Args>(args)...); - } - - template <typename A, typename B, typename A0, typename A1, typename A2> - inline typename enable_if<piecewise3<A, B, A0>, void>::type - construct_impl(std::pair<A, B>* address, A0&&, A1&& a1, A2&& a2) - { - boost::unordered::detail::construct_from_tuple( - boost::addressof(address->first), a1); - boost::unordered::detail::construct_from_tuple( - boost::addressof(address->second), a2); - } - -#if defined(BOOST_UNORDERED_DEPRECATED_PAIR_CONSTRUCT) - - template <typename A, typename B, typename A0> - inline typename enable_if<emulation1<A, B, A0>, void>::type - construct_impl(std::pair<A, B>* address, A0&& a0) - { - new((void*) boost::addressof(address->first)) A(boost::forward<A0>(a0)); - new((void*) boost::addressof(address->second)) B(); - } - - template <typename A, typename B, typename A0, typename A1, typename A2> - inline typename enable_if<emulation3<A, B, A0>, void>::type - construct_impl(std::pair<A, B>* address, A0&& a0, A1&& a1, A2&& a2) - { - new((void*) boost::addressof(address->first)) A(boost::forward<A0>(a0)); - new((void*) boost::addressof(address->second)) B( - boost::forward<A1>(a1), - boost::forward<A2>(a2)); - } - - template <typename A, typename B, - typename A0, typename A1, typename A2, typename A3, - typename... Args> - inline void construct_impl(std::pair<A, B>* address, - A0&& a0, A1&& a1, A2&& a2, A3&& a3, Args&&... args) - { - new((void*) boost::addressof(address->first)) A(boost::forward<A0>(a0)); - - new((void*) boost::addressof(address->second)) B( - boost::forward<A1>(a1), - boost::forward<A2>(a2), - boost::forward<A3>(a3), - boost::forward<Args>(args)...); - } - -#endif // BOOST_UNORDERED_DEPRECATED_PAIR_CONSTRUCT -#else // BOOST_UNORDERED_VARIADIC_MOVE - -//////////////////////////////////////////////////////////////////////////////// -// Construct from emplace_args - -#define BOOST_UNORDERED_CONSTRUCT_IMPL(z, num_params, _) \ - template < \ - typename T, \ - BOOST_PP_ENUM_PARAMS_Z(z, num_params, typename A) \ - > \ - inline void construct_impl(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)); \ - } - - template <typename T, typename A0> - inline void construct_impl(T* address, emplace_args1<A0> const& args) - { - new((void*) address) T(boost::forward<A0>(args.a0)); - } - - template <typename T, typename A0, typename A1> - inline void construct_impl(T* address, emplace_args2<A0, A1> const& args) - { - new((void*) address) T( - boost::forward<A0>(args.a0), - boost::forward<A1>(args.a1) - ); - } - - template <typename T, typename A0, typename A1, typename A2> - inline void construct_impl(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) - ); - } - - BOOST_PP_REPEAT_FROM_TO(4, BOOST_UNORDERED_EMPLACE_LIMIT, - BOOST_UNORDERED_CONSTRUCT_IMPL, _) - -#undef BOOST_UNORDERED_CONSTRUCT_IMPL - - template <typename A, typename B, typename A0, typename A1, typename A2> - inline typename enable_if<piecewise3<A, B, A0>, void>::type - construct_impl(std::pair<A, B>* address, - boost::unordered::detail::emplace_args3<A0, A1, A2> const& args) - { - boost::unordered::detail::construct_from_tuple( - boost::addressof(address->first), args.a1); - boost::unordered::detail::construct_from_tuple( - boost::addressof(address->second), args.a2); - } - -#if defined(BOOST_UNORDERED_DEPRECATED_PAIR_CONSTRUCT) - - template <typename A, typename B, typename A0> - inline typename enable_if<emulation1<A, B, A0>, void>::type - construct_impl(std::pair<A, B>* address, - boost::unordered::detail::emplace_args1<A0> const& args) - { - new((void*) boost::addressof(address->first)) A( - boost::forward<A0>(args.a0)); - new((void*) boost::addressof(address->second)) B(); - } - - template <typename A, typename B, typename A0, typename A1, typename A2> - inline typename enable_if<emulation3<A, B, A0>, void>::type - construct_impl(std::pair<A, B>* address, - boost::unordered::detail::emplace_args3<A0, A1, A2> const& args) - { - new((void*) boost::addressof(address->first)) A( - boost::forward<A0>(args.a0)); - new((void*) boost::addressof(address->second)) B( - boost::forward<A1>(args.a1), - boost::forward<A2>(args.a2)); - } - -#define BOOST_UNORDERED_CONSTRUCT_PAIR_IMPL(z, num_params, _) \ - template <typename A, typename B, \ - BOOST_PP_ENUM_PARAMS_Z(z, num_params, typename A) \ - > \ - inline void construct_impl(std::pair<A, B>* address, \ - boost::unordered::detail::BOOST_PP_CAT(emplace_args, num_params) < \ - BOOST_PP_ENUM_PARAMS_Z(z, num_params, A) \ - > const& args) \ - { \ - new((void*) boost::addressof(address->first)) A( \ - boost::forward<A0>(args.a0)); \ - new((void*) boost::addressof(address->second)) B( \ - BOOST_PP_ENUM_##z(BOOST_PP_DEC(num_params), \ - BOOST_UNORDERED_CALL_FORWARD2, args.a)); \ - } - -#define BOOST_UNORDERED_CALL_FORWARD2(z, i, a) \ - BOOST_UNORDERED_CALL_FORWARD(z, BOOST_PP_INC(i), a) - - BOOST_UNORDERED_CONSTRUCT_PAIR_IMPL(1, 2, _) - BOOST_PP_REPEAT_FROM_TO(4, BOOST_UNORDERED_EMPLACE_LIMIT, - BOOST_UNORDERED_CONSTRUCT_PAIR_IMPL, _) - -#undef BOOST_UNORDERED_CONSTRUCT_PAIR_IMPL -#undef BOOST_UNORDERED_CALL_FORWARD2 - -#endif // BOOST_UNORDERED_DEPRECATED_PAIR_CONSTRUCT -#endif // BOOST_UNORDERED_VARIADIC_MOVE - - //////////////////////////////////////////////////////////////////////////// - // Construct without using the emplace args mechanism. - - template <typename T, typename A0> - inline void construct_impl2(T* address, BOOST_FWD_REF(A0) a0) - { - new((void*) address) T( - boost::forward<A0>(a0) - ); - } - -}}} - -#if defined(BOOST_MSVC) -#pragma warning(pop) -#endif - -#endif diff --git a/boost/unordered/detail/equivalent.hpp b/boost/unordered/detail/equivalent.hpp index 6e7e4190da..5cbf6a7cea 100644 --- a/boost/unordered/detail/equivalent.hpp +++ b/boost/unordered/detail/equivalent.hpp @@ -12,7 +12,6 @@ #endif #include <boost/unordered/detail/table.hpp> -#include <boost/unordered/detail/emplace_args.hpp> #include <boost/unordered/detail/extract_key.hpp> namespace boost { namespace unordered { namespace detail { @@ -23,25 +22,52 @@ namespace boost { namespace unordered { namespace detail { template <typename A, typename T> struct grouped_node : + boost::unordered::detail::node_base< + typename ::boost::unordered::detail::rebind_wrap< + A, grouped_node<A, T> >::type::pointer + >, boost::unordered::detail::value_base<T> { typedef typename ::boost::unordered::detail::rebind_wrap< A, grouped_node<A, T> >::type::pointer link_pointer; + typedef boost::unordered::detail::node_base<link_pointer> node_base; - link_pointer next_; link_pointer group_prev_; std::size_t hash_; +#if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT + template <BOOST_UNORDERED_EMPLACE_TEMPLATE> + explicit grouped_node(BOOST_UNORDERED_EMPLACE_ARGS) : + node_base(), + group_prev_(), + hash_(0) + { + boost::unordered::detail::construct_impl( + this->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD); + } + + ~grouped_node() { + boost::unordered::detail::destroy(this->value_ptr()); + } + + grouped_node(grouped_node const&) { + assert(false); + } +#else grouped_node() : - next_(), + node_base(), group_prev_(), hash_(0) {} +#endif void init(link_pointer self) { group_prev_ = self; } + + private: + grouped_node& operator=(grouped_node const&); }; template <typename T> @@ -50,21 +76,45 @@ namespace boost { namespace unordered { namespace detail { boost::unordered::detail::ptr_bucket { typedef boost::unordered::detail::ptr_bucket bucket_base; + typedef bucket_base node_base; typedef ptr_bucket* link_pointer; link_pointer group_prev_; std::size_t hash_; +#if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT + template <BOOST_UNORDERED_EMPLACE_TEMPLATE> + explicit grouped_ptr_node(BOOST_UNORDERED_EMPLACE_ARGS) : + bucket_base(), + group_prev_(0), + hash_(0) + { + boost::unordered::detail::construct_impl( + this->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD); + } + + ~grouped_ptr_node() { + boost::unordered::detail::destroy(this->value_ptr()); + } + + grouped_ptr_node(grouped_ptr_node const&) { + assert(false); + } +#else grouped_ptr_node() : bucket_base(), group_prev_(0), hash_(0) {} +#endif void init(link_pointer self) { group_prev_ = self; } + + private: + grouped_ptr_node& operator=(grouped_ptr_node const&); }; // If the allocator uses raw pointers use grouped_ptr_node @@ -136,6 +186,8 @@ namespace boost { namespace unordered { namespace detail { typedef boost::unordered::detail::grouped_table_impl<types> table; typedef boost::unordered::detail::set_extractor<value_type> extractor; + + typedef boost::unordered::detail::pick_policy::type policy; }; template <typename A, typename K, typename M, typename H, typename P> @@ -160,6 +212,8 @@ namespace boost { namespace unordered { namespace detail { typedef boost::unordered::detail::grouped_table_impl<types> table; typedef boost::unordered::detail::map_extractor<key_type, value_type> extractor; + + typedef boost::unordered::detail::pick_policy::type policy; }; template <typename Types> @@ -169,6 +223,7 @@ namespace boost { namespace unordered { namespace detail { typedef typename table::value_type value_type; typedef typename table::bucket bucket; typedef typename table::buckets buckets; + 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; @@ -181,6 +236,7 @@ namespace boost { namespace unordered { namespace detail { typedef typename table::node_constructor node_constructor; typedef typename table::extractor extractor; typedef typename table::iterator iterator; + typedef typename table::c_iterator c_iterator; // Constructors @@ -214,59 +270,61 @@ namespace boost { namespace unordered { namespace detail { // Accessors template <class Key, class Pred> - node_pointer find_node_impl( - std::size_t hash, + iterator find_node_impl( + std::size_t key_hash, Key const& k, Pred const& eq) const { - std::size_t bucket_index = hash % this->bucket_count_; - node_pointer n = this->get_start(bucket_index); + std::size_t bucket_index = + policy::to_bucket(this->bucket_count_, key_hash); + iterator n = this->get_start(bucket_index); for (;;) { - if (!n) return n; + if (!n.node_) return n; - std::size_t node_hash = n->hash_; - if (hash == node_hash) + std::size_t node_hash = n.node_->hash_; + if (key_hash == node_hash) { - if (eq(k, this->get_key(n->value()))) + if (eq(k, this->get_key(*n))) return n; } else { - if (node_hash % this->bucket_count_ != bucket_index) - return node_pointer(); + if (policy::to_bucket(this->bucket_count_, node_hash) + != bucket_index) + return iterator(); } - n = static_cast<node_pointer>( - static_cast<node_pointer>(n->group_prev_)->next_); + n = iterator(static_cast<node_pointer>( + static_cast<node_pointer>(n.node_->group_prev_)->next_)); } } std::size_t count(key_type const& k) const { - node_pointer n = this->find_node(k); - if (!n) return 0; + iterator n = this->find_node(k); + if (!n.node_) return 0; - std::size_t count = 0; - node_pointer it = n; + std::size_t x = 0; + node_pointer it = n.node_; do { it = static_cast<node_pointer>(it->group_prev_); - ++count; - } while(it != n); + ++x; + } while(it != n.node_); - return count; + return x; } std::pair<iterator, iterator> equal_range(key_type const& k) const { - node_pointer n = this->find_node(k); + iterator n = this->find_node(k); return std::make_pair( - iterator(n), iterator(n ? + n, n.node_ ? iterator( static_cast<node_pointer>( - static_cast<node_pointer>(n->group_prev_)->next_) : - n)); + static_cast<node_pointer>(n.node_->group_prev_)->next_ + )) : n); } // Equality @@ -276,14 +334,14 @@ namespace boost { namespace unordered { namespace detail { if(this->size_ != other.size_) return false; if(!this->size_) return true; - for(node_pointer n1 = this->get_start(); n1;) + for(iterator n1 = this->get_start(); n1.node_;) { - node_pointer n2 = other.find_matching_node(n1); - if (!n2) return false; - node_pointer end1 = static_cast<node_pointer>( - static_cast<node_pointer>(n1->group_prev_)->next_); - node_pointer end2 = static_cast<node_pointer>( - static_cast<node_pointer>(n2->group_prev_)->next_); + iterator n2 = other.find_matching_node(n1); + if (!n2.node_) return false; + iterator end1(static_cast<node_pointer>( + static_cast<node_pointer>(n1.node_->group_prev_)->next_)); + iterator end2(static_cast<node_pointer>( + static_cast<node_pointer>(n2.node_->group_prev_)->next_)); if (!group_equals(n1, end1, n2, end2)) return false; n1 = end1; } @@ -293,25 +351,24 @@ namespace boost { namespace unordered { namespace detail { #if !defined(BOOST_UNORDERED_DEPRECATED_EQUALITY) - static bool group_equals(node_pointer n1, node_pointer end1, - node_pointer n2, node_pointer end2) + static bool group_equals(iterator n1, iterator end1, + iterator n2, iterator end2) { for(;;) { - if (n1->value() != n2->value()) - break; + if (*n1 != *n2) break; - n1 = static_cast<node_pointer>(n1->next_); - n2 = static_cast<node_pointer>(n2->next_); + ++n1; + ++n2; if (n1 == end1) return n2 == end2; if (n2 == end2) return false; } - for(node_pointer n1a = n1, n2a = n2;;) + for(iterator n1a = n1, n2a = n2;;) { - n1a = static_cast<node_pointer>(n1a->next_); - n2a = static_cast<node_pointer>(n2a->next_); + ++n1a; + ++n2a; if (n1a == end1) { @@ -322,50 +379,50 @@ namespace boost { namespace unordered { namespace detail { if (n2a == end2) return false; } - node_pointer start = n1; - for(;n1 != end2; n1 = static_cast<node_pointer>(n1->next_)) + iterator start = n1; + for(;n1 != end1; ++n1) { - value_type const& v = n1->value(); + value_type const& v = *n1; if (find(start, n1, v)) continue; std::size_t matches = count_equal(n2, end2, v); - if (!matches || matches != 1 + count_equal( - static_cast<node_pointer>(n1->next_), end1, v)) - return false; + if (!matches) return false; + iterator next = n1; + ++next; + if (matches != 1 + count_equal(next, end1, v)) return false; } return true; } - static bool find(node_pointer n, node_pointer end, value_type const& v) + static bool find(iterator n, iterator end, value_type const& v) { - for(;n != end; n = static_cast<node_pointer>(n->next_)) - if (n->value() == v) + for(;n != end; ++n) + if (*n == v) return true; return false; } - static std::size_t count_equal(node_pointer n, node_pointer end, + static std::size_t count_equal(iterator n, iterator end, value_type const& v) { std::size_t count = 0; - for(;n != end; n = static_cast<node_pointer>(n->next_)) - if (n->value() == v) ++count; + for(;n != end; ++n) + if (*n == v) ++count; return count; } #else - static bool group_equals(node_pointer n1, node_pointer end1, - node_pointer n2, node_pointer end2) + static bool group_equals(iterator n1, iterator end1, + iterator n2, iterator end2) { for(;;) { - if(!extractor::compare_mapped( - n1->value(), n2->value())) + if(!extractor::compare_mapped(*n1, *n2)) return false; - n1 = static_cast<node_pointer>(n1->next_); - n2 = static_cast<node_pointer>(n2->next_); + ++n1; + ++n2; if (n1 == end1) return n2 == end2; if (n2 == end2) return false; @@ -387,35 +444,37 @@ namespace boost { namespace unordered { namespace detail { pos->group_prev_ = static_cast<link_pointer>(n); } - inline node_pointer add_node( + inline iterator add_node( node_constructor& a, - std::size_t hash, - node_pointer pos) + std::size_t key_hash, + iterator pos) { node_pointer n = a.release(); - n->hash_ = hash; - if(pos) { - this->add_after_node(n, pos); + n->hash_ = key_hash; + if (pos.node_) { + this->add_after_node(n, pos.node_); if (n->next_) { - std::size_t next_bucket = - static_cast<node_pointer>(n->next_)->hash_ % - this->bucket_count_; - if (next_bucket != hash % this->bucket_count_) { + std::size_t next_bucket = policy::to_bucket( + this->bucket_count_, + static_cast<node_pointer>(n->next_)->hash_); + if (next_bucket != + policy::to_bucket(this->bucket_count_, key_hash)) { this->get_bucket(next_bucket)->next_ = n; } } } else { - bucket_pointer b = this->get_bucket(hash % this->bucket_count_); + bucket_pointer b = this->get_bucket( + policy::to_bucket(this->bucket_count_, key_hash)); if (!b->next_) { previous_pointer start_node = this->get_previous_start(); if (start_node->next_) { - this->get_bucket( + this->get_bucket(policy::to_bucket(this->bucket_count_, static_cast<node_pointer>(start_node->next_)->hash_ - % this->bucket_count_)->next_ = n; + ))->next_ = n; } b->next_ = start_node; @@ -429,36 +488,44 @@ namespace boost { namespace unordered { namespace detail { } } ++this->size_; - return n; + return iterator(n); } - node_pointer emplace_impl(node_constructor& a) + iterator emplace_impl(node_constructor& a) { key_type const& k = this->get_key(a.value()); - std::size_t hash = this->hash_function()(k); - node_pointer position = this->find_node(hash, k); + std::size_t key_hash = this->hash(k); + iterator position = this->find_node(key_hash, k); // reserve has basic exception safety if the hash function // throws, strong otherwise. this->reserve_for_insert(this->size_ + 1); - return this->add_node(a, hash, position); + return this->add_node(a, key_hash, position); } void emplace_impl_no_rehash(node_constructor& a) { key_type const& k = this->get_key(a.value()); - std::size_t hash = this->hash_function()(k); - this->add_node(a, hash, - this->find_node(hash, k)); + std::size_t key_hash = this->hash(k); + this->add_node(a, key_hash, this->find_node(key_hash, k)); } #if defined(BOOST_NO_RVALUE_REFERENCES) +# if defined(BOOST_NO_VARIADIC_TEMPLATES) iterator emplace(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(); + } +# endif #endif template <BOOST_UNORDERED_EMPLACE_TEMPLATE> @@ -523,11 +590,12 @@ namespace boost { namespace unordered { namespace detail { { if(!this->size_) return 0; - std::size_t hash = this->hash_function()(k); - std::size_t bucket_index = hash % this->bucket_count_; - bucket_pointer bucket = this->get_bucket(bucket_index); + std::size_t key_hash = this->hash(k); + std::size_t bucket_index = + policy::to_bucket(this->bucket_count_, key_hash); + bucket_pointer this_bucket = this->get_bucket(bucket_index); - previous_pointer prev = bucket->next_; + previous_pointer prev = this_bucket->next_; if (!prev) return 0; for (;;) @@ -535,9 +603,10 @@ namespace boost { namespace unordered { namespace detail { if (!prev->next_) return 0; std::size_t node_hash = static_cast<node_pointer>(prev->next_)->hash_; - if (node_hash % this->bucket_count_ != bucket_index) + if (policy::to_bucket(this->bucket_count_, node_hash) + != bucket_index) return 0; - if (node_hash == hash && + if (node_hash == key_hash && this->key_eq()(k, this->get_key( static_cast<node_pointer>(prev->next_)->value()))) break; @@ -550,37 +619,39 @@ namespace boost { namespace unordered { namespace detail { static_cast<node_pointer>(pos->group_prev_)->next_; node_pointer end = static_cast<node_pointer>(end1); prev->next_ = end1; - this->fix_buckets(bucket, prev, end); - return this->delete_nodes(pos, end); + this->fix_buckets(this_bucket, prev, end); + return this->delete_nodes(c_iterator(pos), c_iterator(end)); } - node_pointer erase(node_pointer r) + iterator erase(c_iterator r) { - BOOST_ASSERT(r); - node_pointer next = static_cast<node_pointer>(r->next_); + BOOST_ASSERT(r.node_); + iterator next(r.node_); + ++next; - bucket_pointer bucket = this->get_bucket( - r->hash_ % this->bucket_count_); - previous_pointer prev = unlink_node(*bucket, r); + bucket_pointer this_bucket = this->get_bucket( + policy::to_bucket(this->bucket_count_, r.node_->hash_)); + previous_pointer prev = unlink_node(*this_bucket, r.node_); - this->fix_buckets(bucket, prev, next); + this->fix_buckets(this_bucket, prev, next.node_); this->delete_node(r); return next; } - node_pointer erase_range(node_pointer r1, node_pointer r2) + iterator erase_range(c_iterator r1, c_iterator r2) { - if (r1 == r2) return r2; + if (r1 == r2) return iterator(r2.node_); - std::size_t bucket_index = r1->hash_ % this->bucket_count_; + std::size_t bucket_index = + policy::to_bucket(this->bucket_count_, r1.node_->hash_); previous_pointer prev = unlink_nodes( - *this->get_bucket(bucket_index), r1, r2); - this->fix_buckets_range(bucket_index, prev, r1, r2); + *this->get_bucket(bucket_index), r1.node_, r2.node_); + this->fix_buckets_range(bucket_index, prev, r1.node_, r2.node_); this->delete_nodes(r1, r2); - return r2; + return iterator(r2.node_); } static previous_pointer unlink_node(bucket& b, node_pointer n) @@ -697,31 +768,31 @@ namespace boost { namespace unordered { namespace detail { node_constructor a(dst.node_alloc()); - node_pointer n = src.get_start(); + iterator n = src.get_start(); previous_pointer prev = dst.get_previous_start(); - while(n) { - std::size_t hash = n->hash_; - node_pointer group_end = + while (n.node_) { + std::size_t key_hash = n.node_->hash_; + iterator group_end( static_cast<node_pointer>( - static_cast<node_pointer>(n->group_prev_)->next_); + static_cast<node_pointer>(n.node_->group_prev_)->next_ + )); a.construct_node(); - a.construct_value2(n->value()); + a.construct_value2(*n); node_pointer first_node = a.release(); node_pointer end = first_node; - first_node->hash_ = hash; + first_node->hash_ = key_hash; prev->next_ = static_cast<link_pointer>(first_node); ++dst.size_; - for(n = static_cast<node_pointer>(n->next_); n != group_end; - n = static_cast<node_pointer>(n->next_)) + for (++n; n != group_end; ++n) { a.construct_node(); - a.construct_value2(n->value()); + a.construct_value2(*n); end = a.release(); - end->hash_ = hash; + end->hash_ = key_hash; add_after_node(end, first_node); ++dst.size_; } @@ -744,31 +815,31 @@ namespace boost { namespace unordered { namespace detail { node_constructor a(dst.node_alloc()); - node_pointer n = src.get_start(); + iterator n = src.get_start(); previous_pointer prev = dst.get_previous_start(); - while(n) { - std::size_t hash = n->hash_; - node_pointer group_end = + while (n.node_) { + std::size_t key_hash = n.node_->hash_; + iterator group_end( static_cast<node_pointer>( - static_cast<node_pointer>(n->group_prev_)->next_); + static_cast<node_pointer>(n.node_->group_prev_)->next_ + )); a.construct_node(); - a.construct_value2(boost::move(n->value())); + a.construct_value2(boost::move(*n)); node_pointer first_node = a.release(); node_pointer end = first_node; - first_node->hash_ = hash; + first_node->hash_ = key_hash; prev->next_ = static_cast<link_pointer>(first_node); ++dst.size_; - for(n = static_cast<node_pointer>(n->next_); n != group_end; - n = static_cast<node_pointer>(n->next_)) + for(++n; n != group_end; ++n) { a.construct_node(); - a.construct_value2(boost::move(n->value())); + a.construct_value2(boost::move(*n)); end = a.release(); - end->hash_ = hash; + end->hash_ = key_hash; add_after_node(end, first_node); ++dst.size_; } @@ -809,7 +880,8 @@ namespace boost { namespace unordered { namespace detail { static previous_pointer place_in_bucket(buckets& dst, previous_pointer prev, node_pointer end) { - bucket_pointer b = dst.get_bucket(end->hash_ % dst.bucket_count_); + bucket_pointer b = dst.get_bucket(policy::to_bucket( + dst.bucket_count_, end->hash_)); if (!b->next_) { b->next_ = static_cast<node_pointer>(prev); diff --git a/boost/unordered/detail/extract_key.hpp b/boost/unordered/detail/extract_key.hpp index 4ca13e8ce2..56a85324ba 100644 --- a/boost/unordered/detail/extract_key.hpp +++ b/boost/unordered/detail/extract_key.hpp @@ -56,7 +56,7 @@ namespace detail { return no_key(); } -#if defined(BOOST_UNORDERED_VARIADIC_MOVE) +#if !defined(BOOST_NO_VARIADIC_TEMPLATES) template <class... Args> static no_key extract(Args const&...) { @@ -111,7 +111,7 @@ namespace detail { return v.first; } -#if defined(BOOST_UNORDERED_VARIADIC_MOVE) +#if !defined(BOOST_NO_VARIADIC_TEMPLATES) template <class Arg1, class... Args> static key_type const& extract(key_type const& k, Arg1 const&, Args const&...) @@ -150,12 +150,12 @@ namespace detail { } #endif -#if defined(BOOST_UNORDERED_VARIADIC_MOVE) +#if !defined(BOOST_NO_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&&) \ + namespace_::tuple<> const&, BOOST_FWD_REF(T2)) \ { \ return no_key(); \ } \ @@ -163,7 +163,7 @@ namespace detail { 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&&) \ + namespace_::tuple<T> const& k, BOOST_FWD_REF(T2)) \ { \ return typename is_key<key_type, T>::type( \ namespace_::get<0>(k)); \ @@ -191,7 +191,7 @@ namespace detail { BOOST_UNORDERED_KEY_FROM_TUPLE(boost) -#if !defined(BOOST_NO_0X_HDR_TUPLE) +#if !defined(BOOST_NO_CXX11_HDR_TUPLE) BOOST_UNORDERED_KEY_FROM_TUPLE(std) #endif diff --git a/boost/unordered/detail/fwd.hpp b/boost/unordered/detail/fwd.hpp index 1949b5d199..ee8966b755 100644 --- a/boost/unordered/detail/fwd.hpp +++ b/boost/unordered/detail/fwd.hpp @@ -10,41 +10,11 @@ # pragma once #endif -#include <boost/config.hpp> -#include <memory> -#include <functional> -#include <boost/functional/hash_fwd.hpp> namespace boost { namespace unordered { - template <class K, - class T, - class H = boost::hash<K>, - class P = std::equal_to<K>, - class A = std::allocator<std::pair<const K, T> > > - class unordered_map; - - template <class K, - class T, - class H = boost::hash<K>, - class P = std::equal_to<K>, - class A = std::allocator<std::pair<const K, T> > > - class unordered_multimap; - - template <class T, - class H = boost::hash<T>, - class P = std::equal_to<T>, - class A = std::allocator<T> > - class unordered_set; - - template <class T, - class H = boost::hash<T>, - class P = std::equal_to<T>, - class A = std::allocator<T> > - class unordered_multiset; - struct piecewise_construct_t {}; const piecewise_construct_t piecewise_construct = piecewise_construct_t(); } diff --git a/boost/unordered/detail/table.hpp b/boost/unordered/detail/table.hpp index 66c46084ce..cbf6219554 100644 --- a/boost/unordered/detail/table.hpp +++ b/boost/unordered/detail/table.hpp @@ -11,251 +11,8 @@ #include <boost/unordered/detail/util.hpp> #include <boost/type_traits/aligned_storage.hpp> #include <boost/type_traits/alignment_of.hpp> -#include <boost/iterator.hpp> #include <cmath> -namespace boost { namespace unordered { namespace iterator_detail { - - //////////////////////////////////////////////////////////////////////////// - // Iterators - // - // all no throw - - template <typename NodePointer, typename Value> struct iterator; - template <typename ConstNodePointer, typename NodePointer, - typename Value> struct c_iterator; - template <typename NodePointer, typename Value> struct l_iterator; - template <typename ConstNodePointer, typename NodePointer, - typename Value> struct cl_iterator; - - // Local Iterators - // - // all no throw - - template <typename NodePointer, typename Value> - struct l_iterator - : public boost::iterator< - std::forward_iterator_tag, Value, std::ptrdiff_t, - NodePointer, Value&> - { -#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) - template <typename ConstNodePointer, typename NodePointer2, - typename Value2> - friend struct boost::unordered::iterator_detail::cl_iterator; - private: -#endif - typedef NodePointer node_pointer; - node_pointer ptr_; - std::size_t bucket_; - std::size_t bucket_count_; - - public: - - l_iterator() : ptr_() {} - - l_iterator(node_pointer x, std::size_t b, std::size_t c) - : ptr_(x), bucket_(b), bucket_count_(c) {} - - Value& operator*() const { - return ptr_->value(); - } - - Value* operator->() const { - return ptr_->value_ptr(); - } - - l_iterator& operator++() { - ptr_ = static_cast<node_pointer>(ptr_->next_); - if (ptr_ && ptr_->hash_ % bucket_count_ != bucket_) - ptr_ = node_pointer(); - return *this; - } - - l_iterator operator++(int) { - l_iterator tmp(*this); - ++(*this); - return tmp; - } - - bool operator==(l_iterator x) const { - return ptr_ == x.ptr_; - } - - bool operator!=(l_iterator x) const { - return ptr_ != x.ptr_; - } - }; - - template <typename ConstNodePointer, typename NodePointer, typename Value> - struct cl_iterator - : public boost::iterator< - std::forward_iterator_tag, Value, std::ptrdiff_t, - ConstNodePointer, Value const&> - { - friend struct boost::unordered::iterator_detail::l_iterator - <NodePointer, Value>; - private: - - typedef NodePointer node_pointer; - node_pointer ptr_; - std::size_t bucket_; - std::size_t bucket_count_; - - public: - - cl_iterator() : ptr_() {} - - cl_iterator(node_pointer x, std::size_t b, std::size_t c) : - ptr_(x), bucket_(b), bucket_count_(c) {} - - cl_iterator(boost::unordered::iterator_detail::l_iterator< - NodePointer, Value> const& x) : - ptr_(x.ptr_), bucket_(x.bucket_), bucket_count_(x.bucket_count_) - {} - - Value const& - operator*() const { - return ptr_->value(); - } - - Value const* operator->() const { - return ptr_->value_ptr(); - } - - cl_iterator& operator++() { - ptr_ = static_cast<node_pointer>(ptr_->next_); - if (ptr_ && ptr_->hash_ % bucket_count_ != 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) { - return x.ptr_ == y.ptr_; - } - - friend bool operator!=(cl_iterator const& x, cl_iterator const& y) { - return x.ptr_ != y.ptr_; - } - }; - - template <typename NodePointer, typename Value> - struct iterator - : public boost::iterator< - std::forward_iterator_tag, Value, std::ptrdiff_t, - NodePointer, Value&> - { -#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) - template <typename ConstNodePointer, typename NodePointer2, - typename Value2> - friend struct boost::unordered::iterator_detail::c_iterator; - private: -#endif - typedef NodePointer node_pointer; - node_pointer node_; - - public: - - iterator() : node_() {} - - explicit iterator(node_pointer const& x) : node_(x) {} - - Value& operator*() const { - return node_->value(); - } - - Value* operator->() const { - return &node_->value(); - } - - 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 { - return node_ == x.node_; - } - - bool operator!=(iterator const& x) const { - return node_ != x.node_; - } - }; - - template <typename ConstNodePointer, typename NodePointer, typename Value> - struct c_iterator - : public boost::iterator< - std::forward_iterator_tag, Value, std::ptrdiff_t, - ConstNodePointer, Value const&> - { - friend struct boost::unordered::iterator_detail::iterator< - NodePointer, Value>; - -#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) - template <typename K, typename T, typename H, typename P, typename A> - friend class boost::unordered::unordered_map; - template <typename K, typename T, typename H, typename P, typename A> - friend class boost::unordered::unordered_multimap; - template <typename T, typename H, typename P, typename A> - friend class boost::unordered::unordered_set; - template <typename T, typename H, typename P, typename A> - friend class boost::unordered::unordered_multiset; - - private: -#endif - - typedef NodePointer node_pointer; - node_pointer node_; - - public: - - c_iterator() : node_() {} - - explicit c_iterator(node_pointer const& x) : node_(x) {} - - c_iterator(boost::unordered::iterator_detail::iterator< - NodePointer, Value> const& x) : node_(x.node_) {} - - Value const& operator*() const { - return node_->value(); - } - - Value const* operator->() const { - return &node_->value(); - } - - 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) { - return x.node_ == y.node_; - } - - friend bool operator!=(c_iterator const& x, c_iterator const& y) { - return x.node_ != y.node_; - } - }; -}}} - namespace boost { namespace unordered { namespace detail { //////////////////////////////////////////////////////////////////////////// @@ -302,7 +59,8 @@ namespace boost { namespace unordered { namespace detail { boost::unordered::detail::buckets< typename Types::allocator, typename Types::bucket, - typename Types::node>, + typename Types::node, + typename Types::policy>, boost::unordered::detail::functions< typename Types::hasher, typename Types::key_equal> @@ -318,6 +76,7 @@ namespace boost { namespace unordered { namespace detail { 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 boost::unordered::detail::functions< typename Types::hasher, @@ -326,22 +85,15 @@ namespace boost { namespace unordered { namespace detail { typedef boost::unordered::detail::buckets< typename Types::allocator, typename Types::bucket, - typename Types::node> buckets; + typename Types::node, + typename Types::policy> buckets; typedef typename buckets::node_allocator node_allocator; typedef typename buckets::node_allocator_traits node_allocator_traits; typedef typename buckets::node_pointer node_pointer; typedef typename buckets::const_node_pointer const_node_pointer; - typedef boost::unordered::iterator_detail:: - iterator<node_pointer, value_type> iterator; - typedef boost::unordered::iterator_detail:: - c_iterator<const_node_pointer, node_pointer, value_type> c_iterator; - typedef boost::unordered::iterator_detail:: - l_iterator<node_pointer, value_type> l_iterator; - typedef boost::unordered::iterator_detail:: - cl_iterator<const_node_pointer, node_pointer, value_type> - cl_iterator; + typedef typename table::iterator iterator; // Members @@ -384,7 +136,7 @@ namespace boost { namespace unordered { namespace detail { std::size_t min_buckets_for_size(std::size_t size) const { - BOOST_ASSERT(this->mlf_ != 0); + BOOST_ASSERT(this->mlf_ >= minimum_max_load_factor); using namespace std; @@ -395,7 +147,7 @@ namespace boost { namespace unordered { namespace detail { // Or from rehash post-condition: // count > size / mlf_ - return boost::unordered::detail::next_prime( + return policy::new_bucket_count( boost::unordered::detail::double_to_size(floor( static_cast<double>(size) / static_cast<double>(mlf_))) + 1); @@ -408,7 +160,7 @@ namespace boost { namespace unordered { namespace detail { hasher const& hf, key_equal const& eq, node_allocator const& a) : - buckets(a, boost::unordered::detail::next_prime(num_buckets)), + buckets(a, policy::new_bucket_count(num_buckets)), functions(hf, eq), mlf_(1.0f), max_load_(0) @@ -458,9 +210,9 @@ namespace boost { namespace unordered { namespace detail { // Iterators - node_pointer begin() const { + iterator begin() const { return !this->buckets_ ? - node_pointer() : this->get_start(); + iterator() : this->get_start(); } // Assignment @@ -586,36 +338,41 @@ namespace boost { namespace unordered { namespace detail { return extractor::extract(x); } + std::size_t hash(key_type const& k) const + { + return policy::apply_hash(this->hash_function(), k); + } + // Find Node template <typename Key, typename Hash, typename Pred> - node_pointer generic_find_node( + iterator generic_find_node( Key const& k, - Hash const& hash_function, + Hash const& hf, Pred const& eq) const { - if (!this->size_) return node_pointer(); + if (!this->size_) return iterator(); return static_cast<table_impl const*>(this)-> - find_node_impl(hash_function(k), k, eq); + find_node_impl(policy::apply_hash(hf, k), k, eq); } - node_pointer find_node( - std::size_t hash, + iterator find_node( + std::size_t key_hash, key_type const& k) const { - if (!this->size_) return node_pointer(); + if (!this->size_) return iterator(); return static_cast<table_impl const*>(this)-> - find_node_impl(hash, k, this->key_eq()); + find_node_impl(key_hash, k, this->key_eq()); } - node_pointer find_node(key_type const& k) const + iterator find_node(key_type const& k) const { - if (!this->size_) return node_pointer(); + if (!this->size_) return iterator(); return static_cast<table_impl const*>(this)-> - find_node_impl(this->hash_function()(k), k, this->key_eq()); + find_node_impl(this->hash(k), k, this->key_eq()); } - node_pointer find_matching_node(node_pointer n) const + iterator find_matching_node(iterator n) const { // TODO: Does this apply to C++11? // @@ -623,13 +380,14 @@ namespace boost { namespace unordered { namespace detail { // when different hash functions are used. So I can't use the hash // value from the node here. - return find_node(get_key(n->value())); + return find_node(get_key(*n)); } // Reserve and rehash void reserve_for_insert(std::size_t); void rehash(std::size_t); + void reserve(std::size_t); }; //////////////////////////////////////////////////////////////////////////// @@ -645,7 +403,9 @@ namespace boost { namespace unordered { namespace detail { this->create_buckets(); this->max_load_ = this->calculate_max_load(); } - else if(size >= max_load_) { + // According to the standard this should be 'size >= max_load_', + // but I think this is better, defect report filed. + else if(size > max_load_) { std::size_t num_buckets = this->min_buckets_for_size((std::max)(size, this->size_ + (this->size_ >> 1))); @@ -660,16 +420,16 @@ namespace boost { namespace unordered { namespace detail { // strong otherwise. template <typename Types> - void table<Types>::rehash(std::size_t min_buckets) + inline void table<Types>::rehash(std::size_t min_buckets) { using namespace std; if(!this->size_) { if(this->buckets_) this->delete_buckets(); - this->bucket_count_ = next_prime(min_buckets); + this->bucket_count_ = policy::new_bucket_count(min_buckets); } else { - min_buckets = next_prime((std::max)(min_buckets, + min_buckets = policy::new_bucket_count((std::max)(min_buckets, boost::unordered::detail::double_to_size(floor( static_cast<double>(this->size_) / static_cast<double>(mlf_))) + 1)); @@ -680,6 +440,13 @@ namespace boost { namespace unordered { namespace detail { } } } + + 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) / this->mlf_))); + } }}} #endif diff --git a/boost/unordered/detail/unique.hpp b/boost/unordered/detail/unique.hpp index 9c049f78c0..10db58fa75 100644 --- a/boost/unordered/detail/unique.hpp +++ b/boost/unordered/detail/unique.hpp @@ -12,35 +12,60 @@ #endif #include <boost/unordered/detail/table.hpp> -#include <boost/unordered/detail/emplace_args.hpp> #include <boost/unordered/detail/extract_key.hpp> #include <boost/throw_exception.hpp> #include <stdexcept> namespace boost { namespace unordered { namespace detail { - template <typename A, typename T> struct node; + 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 node : + struct unique_node : + boost::unordered::detail::node_base< + typename ::boost::unordered::detail::rebind_wrap< + A, unique_node<A, T> >::type::pointer + >, boost::unordered::detail::value_base<T> { typedef typename ::boost::unordered::detail::rebind_wrap< - A, node<A, T> >::type::pointer link_pointer; + A, unique_node<A, T> >::type::pointer link_pointer; + typedef boost::unordered::detail::node_base<link_pointer> node_base; - link_pointer next_; std::size_t hash_; - node() : - next_(), +#if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT + template <BOOST_UNORDERED_EMPLACE_TEMPLATE> + explicit unique_node(BOOST_UNORDERED_EMPLACE_ARGS) : + node_base(), + hash_(0) + { + boost::unordered::detail::construct_impl( + this->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD); + } + + ~unique_node() { + boost::unordered::detail::destroy(this->value_ptr()); + } + + unique_node(unique_node const&) { + BOOST_ASSERT(false); + } +#else + unique_node() : + node_base(), hash_(0) {} +#endif void init(link_pointer) { } + + private: + unique_node& operator=(unique_node const&); }; template <typename T> @@ -49,18 +74,41 @@ namespace boost { namespace unordered { namespace detail { boost::unordered::detail::ptr_bucket { typedef boost::unordered::detail::ptr_bucket bucket_base; + typedef bucket_base node_base; typedef ptr_bucket* link_pointer; std::size_t hash_; +#if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT + template <BOOST_UNORDERED_EMPLACE_TEMPLATE> + explicit ptr_node(BOOST_UNORDERED_EMPLACE_ARGS) : + bucket_base(), + hash_(0) + { + boost::unordered::detail::construct_impl( + this->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD); + } + + ~ptr_node() { + boost::unordered::detail::destroy(this->value_ptr()); + } + + ptr_node(ptr_node const&) { + BOOST_ASSERT(false); + } +#else ptr_node() : bucket_base(), hash_(0) {} +#endif void init(link_pointer) { } + + private: + ptr_node& operator=(ptr_node const&); }; // If the allocator uses raw pointers use ptr_node @@ -69,7 +117,7 @@ namespace boost { namespace unordered { namespace detail { template <typename A, typename T, typename NodePtr, typename BucketPtr> struct pick_node2 { - typedef boost::unordered::detail::node<A, T> node; + 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 @@ -132,6 +180,8 @@ namespace boost { namespace unordered { namespace detail { typedef boost::unordered::detail::table_impl<types> table; typedef boost::unordered::detail::set_extractor<value_type> extractor; + + typedef boost::unordered::detail::pick_policy::type policy; }; template <typename A, typename K, typename M, typename H, typename P> @@ -156,6 +206,8 @@ namespace boost { namespace unordered { namespace detail { typedef boost::unordered::detail::table_impl<types> table; typedef boost::unordered::detail::map_extractor<key_type, value_type> extractor; + + typedef boost::unordered::detail::pick_policy::type policy; }; template <typename Types> @@ -165,6 +217,7 @@ namespace boost { namespace unordered { namespace detail { typedef typename table::value_type value_type; typedef typename table::bucket bucket; typedef typename table::buckets buckets; + 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; @@ -177,6 +230,7 @@ namespace boost { namespace unordered { namespace detail { typedef typename table::node_constructor node_constructor; typedef typename table::extractor extractor; typedef typename table::iterator iterator; + typedef typename table::c_iterator c_iterator; typedef std::pair<iterator, bool> emplace_return; @@ -212,44 +266,46 @@ namespace boost { namespace unordered { namespace detail { // Accessors template <class Key, class Pred> - node_pointer find_node_impl( - std::size_t hash, + iterator find_node_impl( + std::size_t key_hash, Key const& k, Pred const& eq) const { - std::size_t bucket_index = hash % this->bucket_count_; - node_pointer n = this->get_start(bucket_index); + std::size_t bucket_index = + policy::to_bucket(this->bucket_count_, key_hash); + iterator n = this->get_start(bucket_index); for (;;) { - if (!n) return n; + if (!n.node_) return n; - std::size_t node_hash = n->hash_; - if (hash == node_hash) + std::size_t node_hash = n.node_->hash_; + if (key_hash == node_hash) { - if (eq(k, this->get_key(n->value()))) + if (eq(k, this->get_key(*n))) return n; } else { - if (node_hash % this->bucket_count_ != bucket_index) - return node_pointer(); + if (policy::to_bucket(this->bucket_count_, node_hash) + != bucket_index) + return iterator(); } - n = static_cast<node_pointer>(n->next_); + ++n; } } std::size_t count(key_type const& k) const { - return this->find_node(k) ? 1 : 0; + return this->find_node(k).node_ ? 1 : 0; } value_type& at(key_type const& k) const { if (this->size_) { - node_pointer it = this->find_node(k); - if (it) return it->value(); + iterator it = this->find_node(k); + if (it.node_) return *it; } boost::throw_exception( @@ -259,9 +315,10 @@ namespace boost { namespace unordered { namespace detail { std::pair<iterator, iterator> equal_range(key_type const& k) const { - node_pointer n = this->find_node(k); - return std::make_pair(iterator(n), - iterator(n ? static_cast<node_pointer>(n->next_) : n)); + iterator n = this->find_node(k); + iterator n2 = n; + if (n2.node_) ++n2; + return std::make_pair(n, n2); } // equals @@ -271,17 +328,15 @@ namespace boost { namespace unordered { namespace detail { if(this->size_ != other.size_) return false; if(!this->size_) return true; - for(node_pointer n1 = this->get_start(); n1; - n1 = static_cast<node_pointer>(n1->next_)) + for(iterator n1 = this->get_start(); n1.node_; ++n1) { - node_pointer n2 = other.find_matching_node(n1); + iterator n2 = other.find_matching_node(n1); #if !defined(BOOST_UNORDERED_DEPRECATED_EQUALITY) - if(!n2 || n1->value() != n2->value()) + if (!n2.node_ || *n1 != *n2) return false; #else - if(!n2 || !extractor::compare_mapped( - n1->value(), n2->value())) + if (!n2.node_ || !extractor::compare_mapped(*n1, *n2)) return false; #endif } @@ -291,23 +346,24 @@ namespace boost { namespace unordered { namespace detail { // Emplace/Insert - inline node_pointer add_node( + inline iterator add_node( node_constructor& a, - std::size_t hash) + std::size_t key_hash) { node_pointer n = a.release(); - n->hash_ = hash; + n->hash_ = key_hash; - bucket_pointer b = this->get_bucket(hash % this->bucket_count_); + bucket_pointer b = this->get_bucket( + policy::to_bucket(this->bucket_count_, key_hash)); if (!b->next_) { previous_pointer start_node = this->get_previous_start(); if (start_node->next_) { - this->get_bucket( - static_cast<node_pointer>(start_node->next_)->hash_ % - this->bucket_count_)->next_ = n; + this->get_bucket(policy::to_bucket(this->bucket_count_, + static_cast<node_pointer>(start_node->next_)->hash_) + )->next_ = n; } b->next_ = start_node; @@ -321,54 +377,57 @@ namespace boost { namespace unordered { namespace detail { } ++this->size_; - return n; + return iterator(n); } value_type& operator[](key_type const& k) { typedef typename value_type::second_type mapped_type; - std::size_t hash = this->hash_function()(k); - node_pointer pos = this->find_node(hash, k); + std::size_t key_hash = this->hash(k); + iterator pos = this->find_node(key_hash, k); - if (pos) return pos->value(); + if (pos.node_) return *pos; // Create the node before rehashing in case it throws an // exception (need strong safety in such a case). node_constructor a(this->node_alloc()); a.construct_node(); -#if defined(BOOST_UNORDERED_VARIADIC_MOVE) - a.construct_value(boost::unordered::piecewise_construct, - boost::make_tuple(k), boost::make_tuple()); -#else - a.construct_value( - boost::unordered::detail::create_emplace_args( - boost::unordered::piecewise_construct, - boost::make_tuple(k), - boost::make_tuple())); -#endif + + a.construct_value(BOOST_UNORDERED_EMPLACE_ARGS3( + boost::unordered::piecewise_construct, + boost::make_tuple(k), + boost::make_tuple())); this->reserve_for_insert(this->size_ + 1); - return add_node(a, hash)->value(); + return *add_node(a, key_hash); } #if defined(BOOST_NO_RVALUE_REFERENCES) +# if defined(BOOST_NO_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(this->begin()), false); + return emplace_return(this->begin(), false); + } +# else + emplace_return emplace( + boost::unordered::detail::please_ignore_this_overload const&) + { + BOOST_ASSERT(false); + return emplace_return(this->begin(), false); } +# endif #endif template <BOOST_UNORDERED_EMPLACE_TEMPLATE> emplace_return emplace(BOOST_UNORDERED_EMPLACE_ARGS) { -#if defined(BOOST_UNORDERED_VARIADIC_MOVE) +#if !defined(BOOST_NO_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), @@ -376,7 +435,7 @@ namespace boost { namespace unordered { namespace detail { #endif } -#if !defined(BOOST_UNORDERED_VARIADIC_MOVE) +#if defined(BOOST_NO_VARIADIC_TEMPLATES) template <typename A0> emplace_return emplace( boost::unordered::detail::emplace_args1<A0> const& args) @@ -389,10 +448,10 @@ namespace boost { namespace unordered { namespace detail { emplace_return emplace_impl(key_type const& k, BOOST_UNORDERED_EMPLACE_ARGS) { - std::size_t hash = this->hash_function()(k); - node_pointer pos = this->find_node(hash, k); + std::size_t key_hash = this->hash(k); + iterator pos = this->find_node(key_hash, k); - if (pos) return emplace_return(iterator(pos), false); + if (pos.node_) return emplace_return(pos, false); // Create the node before rehashing in case it throws an // exception (need strong safety in such a case). @@ -403,21 +462,21 @@ namespace boost { namespace unordered { namespace detail { // reserve has basic exception safety if the hash function // throws, strong otherwise. this->reserve_for_insert(this->size_ + 1); - return emplace_return(iterator(this->add_node(a, hash)), true); + return emplace_return(this->add_node(a, key_hash), true); } emplace_return emplace_impl_with_node(node_constructor& a) { key_type const& k = this->get_key(a.value()); - std::size_t hash = this->hash_function()(k); - node_pointer pos = this->find_node(hash, k); + std::size_t key_hash = this->hash(k); + iterator pos = this->find_node(key_hash, k); - if (pos) return emplace_return(iterator(pos), false); + if (pos.node_) return emplace_return(pos, false); // reserve has basic exception safety if the hash function // throws, strong otherwise. this->reserve_for_insert(this->size_ + 1); - return emplace_return(iterator(this->add_node(a, hash)), true); + return emplace_return(this->add_node(a, key_hash), true); } template <BOOST_UNORDERED_EMPLACE_TEMPLATE> @@ -473,12 +532,12 @@ namespace boost { namespace unordered { namespace detail { void insert_range_empty(node_constructor& a, key_type const& k, InputIt i, InputIt j) { - std::size_t hash = this->hash_function()(k); + std::size_t key_hash = this->hash(k); a.construct_node(); a.construct_value2(*i); this->reserve_for_insert(this->size_ + boost::unordered::detail::insert_size(i, j)); - this->add_node(a, hash); + this->add_node(a, key_hash); } template <class InputIt> @@ -486,19 +545,19 @@ namespace boost { namespace unordered { namespace detail { InputIt i, InputIt j) { // No side effects in this initial code - std::size_t hash = this->hash_function()(k); - node_pointer pos = this->find_node(hash, k); + std::size_t key_hash = this->hash(k); + iterator pos = this->find_node(key_hash, k); - if (!pos) { + if (!pos.node_) { a.construct_node(); a.construct_value2(*i); - if(this->size_ + 1 >= this->max_load_) + if(this->size_ + 1 > this->max_load_) this->reserve_for_insert(this->size_ + boost::unordered::detail::insert_size(i, j)); // Nothing after this point can throw. - this->add_node(a, hash); + this->add_node(a, key_hash); } } @@ -523,11 +582,12 @@ namespace boost { namespace unordered { namespace detail { { if(!this->size_) return 0; - std::size_t hash = this->hash_function()(k); - std::size_t bucket_index = hash % this->bucket_count_; - bucket_pointer bucket = this->get_bucket(bucket_index); + std::size_t key_hash = this->hash(k); + std::size_t bucket_index = + policy::to_bucket(this->bucket_count_, key_hash); + bucket_pointer this_bucket = this->get_bucket(bucket_index); - previous_pointer prev = bucket->next_; + previous_pointer prev = this_bucket->next_; if (!prev) return 0; for (;;) @@ -535,9 +595,10 @@ namespace boost { namespace unordered { namespace detail { if (!prev->next_) return 0; std::size_t node_hash = static_cast<node_pointer>(prev->next_)->hash_; - if (node_hash % this->bucket_count_ != bucket_index) + if (policy::to_bucket(this->bucket_count_, node_hash) + != bucket_index) return 0; - if (node_hash == hash && + if (node_hash == key_hash && this->key_eq()(k, this->get_key( static_cast<node_pointer>(prev->next_)->value()))) break; @@ -547,37 +608,39 @@ namespace boost { namespace unordered { namespace detail { node_pointer pos = static_cast<node_pointer>(prev->next_); node_pointer end = static_cast<node_pointer>(pos->next_); prev->next_ = pos->next_; - this->fix_buckets(bucket, prev, end); - return this->delete_nodes(pos, end); + this->fix_buckets(this_bucket, prev, end); + return this->delete_nodes(c_iterator(pos), c_iterator(end)); } - node_pointer erase(node_pointer r) + iterator erase(c_iterator r) { - BOOST_ASSERT(r); - node_pointer next = static_cast<node_pointer>(r->next_); + BOOST_ASSERT(r.node_); + iterator next(r.node_); + ++next; - bucket_pointer bucket = this->get_bucket( - r->hash_ % this->bucket_count_); - previous_pointer prev = unlink_node(*bucket, r); + bucket_pointer this_bucket = this->get_bucket( + policy::to_bucket(this->bucket_count_, r.node_->hash_)); + previous_pointer prev = unlink_node(*this_bucket, r.node_); - this->fix_buckets(bucket, prev, next); + this->fix_buckets(this_bucket, prev, next.node_); this->delete_node(r); return next; } - node_pointer erase_range(node_pointer r1, node_pointer r2) + iterator erase_range(c_iterator r1, c_iterator r2) { - if (r1 == r2) return r2; + if (r1 == r2) return iterator(r2.node_); - std::size_t bucket_index = r1->hash_ % this->bucket_count_; + std::size_t bucket_index = + policy::to_bucket(this->bucket_count_, r1.node_->hash_); previous_pointer prev = unlink_nodes( - *this->get_bucket(bucket_index), r1, r2); - this->fix_buckets_range(bucket_index, prev, r1, r2); + *this->get_bucket(bucket_index), r1.node_, r2.node_); + this->fix_buckets_range(bucket_index, prev, r1.node_, r2.node_); this->delete_nodes(r1, r2); - return r2; + return iterator(r2.node_); } static previous_pointer unlink_node(bucket& b, node_pointer n) @@ -610,18 +673,18 @@ namespace boost { namespace unordered { namespace detail { node_constructor a(dst.node_alloc()); - node_pointer n = src.get_start(); + iterator n = src.get_start(); previous_pointer prev = dst.get_previous_start(); - while(n) { + while(n.node_) { a.construct_node(); - a.construct_value2(n->value()); + a.construct_value2(*n); node_pointer node = a.release(); - node->hash_ = n->hash_; + node->hash_ = n.node_->hash_; prev->next_ = static_cast<link_pointer>(node); ++dst.size_; - n = static_cast<node_pointer>(n->next_); + ++n; prev = place_in_bucket(dst, prev); } @@ -641,18 +704,18 @@ namespace boost { namespace unordered { namespace detail { node_constructor a(dst.node_alloc()); - node_pointer n = src.get_start(); + iterator n = src.get_start(); previous_pointer prev = dst.get_previous_start(); - while(n) { + while (n.node_) { a.construct_node(); - a.construct_value2(boost::move(n->value())); + a.construct_value2(boost::move(*n)); node_pointer node = a.release(); - node->hash_ = n->hash_; + node->hash_ = n.node_->hash_; prev->next_ = static_cast<link_pointer>(node); ++dst.size_; - n = static_cast<node_pointer>(n->next_); + ++n; prev = place_in_bucket(dst, prev); } @@ -689,7 +752,8 @@ namespace boost { namespace unordered { namespace detail { previous_pointer prev) { node_pointer n = static_cast<node_pointer>(prev->next_); - bucket_pointer b = dst.get_bucket(n->hash_ % dst.bucket_count_); + bucket_pointer b = dst.get_bucket( + buckets::to_bucket(dst.bucket_count_, n->hash_)); if (!b->next_) { b->next_ = prev; diff --git a/boost/unordered/detail/util.hpp b/boost/unordered/detail/util.hpp index 53976f8e4f..a901477d19 100644 --- a/boost/unordered/detail/util.hpp +++ b/boost/unordered/detail/util.hpp @@ -56,7 +56,7 @@ namespace boost { namespace unordered { namespace detail { // primes #define BOOST_UNORDERED_PRIMES \ - (5ul)(11ul)(17ul)(29ul)(37ul)(53ul)(67ul)(79ul) \ + (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) \ diff --git a/boost/unordered/unordered_map.hpp b/boost/unordered/unordered_map.hpp index 1a7ff151cf..ce52e5becf 100644 --- a/boost/unordered/unordered_map.hpp +++ b/boost/unordered/unordered_map.hpp @@ -14,14 +14,13 @@ #endif #include <boost/unordered/unordered_map_fwd.hpp> -#include <boost/unordered/detail/allocator_helpers.hpp> #include <boost/unordered/detail/equivalent.hpp> #include <boost/unordered/detail/unique.hpp> #include <boost/unordered/detail/util.hpp> #include <boost/functional/hash.hpp> #include <boost/move/move.hpp> -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) #include <initializer_list> #endif @@ -133,7 +132,7 @@ namespace unordered unordered_map(unordered_map&&, allocator_type const&); #endif -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) unordered_map( std::initializer_list<value_type>, size_type = boost::unordered::detail::default_bucket_count, @@ -176,7 +175,7 @@ namespace unordered #endif #endif -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) unordered_map& operator=(std::initializer_list<value_type>); #endif @@ -203,12 +202,12 @@ namespace unordered iterator begin() { - return iterator(table_.begin()); + return table_.begin(); } const_iterator begin() const { - return const_iterator(table_.begin()); + return table_.begin(); } iterator end() @@ -223,7 +222,7 @@ namespace unordered const_iterator cbegin() const { - return const_iterator(table_.begin()); + return table_.begin(); } const_iterator cend() const @@ -233,15 +232,15 @@ namespace unordered // emplace -#if defined(BOOST_UNORDERED_VARIADIC_MOVE) +#if !defined(BOOST_NO_VARIADIC_TEMPLATES) template <class... Args> - std::pair<iterator, bool> emplace(Args&&... args) + std::pair<iterator, bool> emplace(BOOST_FWD_REF(Args)... args) { return table_.emplace(boost::forward<Args>(args)...); } template <class... Args> - iterator emplace_hint(const_iterator, Args&&... args) + iterator emplace_hint(const_iterator, BOOST_FWD_REF(Args)... args) { return table_.emplace(boost::forward<Args>(args)...).first; } @@ -401,7 +400,7 @@ namespace unordered template <class InputIt> void insert(InputIt, InputIt); -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) void insert(std::initializer_list<value_type>); #endif @@ -465,7 +464,8 @@ namespace unordered size_type bucket(const key_type& k) const { - return table_.hash_function()(k) % table_.bucket_count_; + return table::to_bucket(table_.bucket_count_, + table_.hash(k)); } local_iterator begin(size_type n) @@ -514,6 +514,7 @@ namespace unordered float load_factor() const; void max_load_factor(float); void rehash(size_type); + void reserve(size_type); #if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582) friend bool operator==<K,T,H,P,A>( @@ -617,7 +618,7 @@ namespace unordered unordered_multimap(unordered_multimap&&, allocator_type const&); #endif -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) unordered_multimap( std::initializer_list<value_type>, size_type = boost::unordered::detail::default_bucket_count, @@ -661,7 +662,7 @@ namespace unordered #endif #endif -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) unordered_multimap& operator=(std::initializer_list<value_type>); #endif @@ -688,12 +689,12 @@ namespace unordered iterator begin() { - return iterator(table_.begin()); + return table_.begin(); } const_iterator begin() const { - return const_iterator(table_.begin()); + return table_.begin(); } iterator end() @@ -708,7 +709,7 @@ namespace unordered const_iterator cbegin() const { - return const_iterator(table_.begin()); + return table_.begin(); } const_iterator cend() const @@ -718,15 +719,15 @@ namespace unordered // emplace -#if defined(BOOST_UNORDERED_VARIADIC_MOVE) +#if !defined(BOOST_NO_VARIADIC_TEMPLATES) template <class... Args> - iterator emplace(Args&&... args) + iterator emplace(BOOST_FWD_REF(Args)... args) { return table_.emplace(boost::forward<Args>(args)...); } template <class... Args> - iterator emplace_hint(const_iterator, Args&&... args) + iterator emplace_hint(const_iterator, BOOST_FWD_REF(Args)... args) { return table_.emplace(boost::forward<Args>(args)...); } @@ -886,7 +887,7 @@ namespace unordered template <class InputIt> void insert(InputIt, InputIt); -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) void insert(std::initializer_list<value_type>); #endif @@ -946,7 +947,8 @@ namespace unordered size_type bucket(const key_type& k) const { - return table_.hash_function()(k) % table_.bucket_count_; + return table::to_bucket(table_.bucket_count_, + table_.hash(k)); } local_iterator begin(size_type n) @@ -995,6 +997,7 @@ namespace unordered float load_factor() const; void max_load_factor(float); void rehash(size_type); + void reserve(size_type); #if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582) friend bool operator==<K,T,H,P,A>( @@ -1084,7 +1087,7 @@ namespace unordered #endif -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) template <class K, class T, class H, class P, class A> unordered_map<K,T,H,P,A>::unordered_map( @@ -1126,7 +1129,7 @@ namespace unordered table_.insert_range(first, last); } -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) template <class K, class T, class H, class P, class A> void unordered_map<K,T,H,P,A>::insert( std::initializer_list<value_type> list) @@ -1139,7 +1142,7 @@ namespace unordered typename unordered_map<K,T,H,P,A>::iterator unordered_map<K,T,H,P,A>::erase(const_iterator position) { - return iterator(table_.erase(position.node_)); + return table_.erase(position); } template <class K, class T, class H, class P, class A> @@ -1154,7 +1157,7 @@ namespace unordered unordered_map<K,T,H,P,A>::erase( const_iterator first, const_iterator last) { - return iterator(table_.erase_range(first.node_, last.node_)); + return table_.erase_range(first, last); } template <class K, class T, class H, class P, class A> @@ -1212,14 +1215,14 @@ namespace unordered typename unordered_map<K,T,H,P,A>::iterator unordered_map<K,T,H,P,A>::find(const key_type& k) { - return iterator(table_.find_node(k)); + return table_.find_node(k); } template <class K, class T, class H, class P, class A> typename unordered_map<K,T,H,P,A>::const_iterator unordered_map<K,T,H,P,A>::find(const key_type& k) const { - return const_iterator(table_.find_node(k)); + return table_.find_node(k); } template <class K, class T, class H, class P, class A> @@ -1231,7 +1234,7 @@ namespace unordered CompatibleHash const& hash, CompatiblePredicate const& eq) { - return iterator(table_.generic_find_node(k, hash, eq)); + return table_.generic_find_node(k, hash, eq); } template <class K, class T, class H, class P, class A> @@ -1243,7 +1246,7 @@ namespace unordered CompatibleHash const& hash, CompatiblePredicate const& eq) const { - return const_iterator(table_.generic_find_node(k, hash, eq)); + return table_.generic_find_node(k, hash, eq); } template <class K, class T, class H, class P, class A> @@ -1299,6 +1302,12 @@ namespace unordered } template <class K, class T, class H, class P, class A> + void unordered_map<K,T,H,P,A>::reserve(size_type n) + { + table_.reserve(n); + } + + template <class K, class T, class H, class P, class A> inline bool operator==( unordered_map<K,T,H,P,A> const& m1, unordered_map<K,T,H,P,A> const& m2) @@ -1411,7 +1420,7 @@ namespace unordered #endif -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) template <class K, class T, class H, class P, class A> unordered_multimap<K,T,H,P,A>::unordered_multimap( @@ -1453,7 +1462,7 @@ namespace unordered table_.insert_range(first, last); } -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) template <class K, class T, class H, class P, class A> void unordered_multimap<K,T,H,P,A>::insert( std::initializer_list<value_type> list) @@ -1466,7 +1475,7 @@ namespace unordered typename unordered_multimap<K,T,H,P,A>::iterator unordered_multimap<K,T,H,P,A>::erase(const_iterator position) { - return iterator(table_.erase(position.node_)); + return table_.erase(position); } template <class K, class T, class H, class P, class A> @@ -1481,7 +1490,7 @@ namespace unordered unordered_multimap<K,T,H,P,A>::erase( const_iterator first, const_iterator last) { - return iterator(table_.erase_range(first.node_, last.node_)); + return table_.erase_range(first, last); } template <class K, class T, class H, class P, class A> @@ -1518,14 +1527,14 @@ namespace unordered typename unordered_multimap<K,T,H,P,A>::iterator unordered_multimap<K,T,H,P,A>::find(const key_type& k) { - return iterator(table_.find_node(k)); + return table_.find_node(k); } template <class K, class T, class H, class P, class A> typename unordered_multimap<K,T,H,P,A>::const_iterator unordered_multimap<K,T,H,P,A>::find(const key_type& k) const { - return const_iterator(table_.find_node(k)); + return table_.find_node(k); } template <class K, class T, class H, class P, class A> @@ -1537,7 +1546,7 @@ namespace unordered CompatibleHash const& hash, CompatiblePredicate const& eq) { - return iterator(table_.generic_find_node(k, hash, eq)); + return table_.generic_find_node(k, hash, eq); } template <class K, class T, class H, class P, class A> @@ -1549,7 +1558,7 @@ namespace unordered CompatibleHash const& hash, CompatiblePredicate const& eq) const { - return const_iterator(table_.generic_find_node(k, hash, eq)); + return table_.generic_find_node(k, hash, eq); } template <class K, class T, class H, class P, class A> @@ -1605,6 +1614,12 @@ namespace unordered } template <class K, class T, class H, class P, class A> + void unordered_multimap<K,T,H,P,A>::reserve(size_type n) + { + table_.reserve(n); + } + + template <class K, class T, class H, class P, class A> inline bool operator==( unordered_multimap<K,T,H,P,A> const& m1, unordered_multimap<K,T,H,P,A> const& m2) diff --git a/boost/unordered/unordered_map_fwd.hpp b/boost/unordered/unordered_map_fwd.hpp index 91f1e3bdfa..980bb3ee77 100644 --- a/boost/unordered/unordered_map_fwd.hpp +++ b/boost/unordered/unordered_map_fwd.hpp @@ -10,12 +10,23 @@ # pragma once #endif +#include <boost/config.hpp> +#include <memory> +#include <functional> +#include <boost/functional/hash_fwd.hpp> #include <boost/unordered/detail/fwd.hpp> namespace boost { namespace unordered { + template <class K, + class T, + class H = boost::hash<K>, + class P = std::equal_to<K>, + class A = std::allocator<std::pair<const K, T> > > + class unordered_map; + template <class K, class T, class H, class P, class A> inline bool operator==(unordered_map<K, T, H, P, A> const&, unordered_map<K, T, H, P, A> const&); @@ -26,6 +37,13 @@ namespace boost inline void swap(unordered_map<K, T, H, P, A>&, unordered_map<K, T, H, P, A>&); + template <class K, + class T, + class H = boost::hash<K>, + class P = std::equal_to<K>, + class A = std::allocator<std::pair<const K, T> > > + class unordered_multimap; + template <class K, class T, class H, class P, class A> inline bool operator==(unordered_multimap<K, T, H, P, A> const&, unordered_multimap<K, T, H, P, A> const&); diff --git a/boost/unordered/unordered_set.hpp b/boost/unordered/unordered_set.hpp index 384769ddf1..5d9a0b8e8d 100644 --- a/boost/unordered/unordered_set.hpp +++ b/boost/unordered/unordered_set.hpp @@ -14,14 +14,13 @@ #endif #include <boost/unordered/unordered_set_fwd.hpp> -#include <boost/unordered/detail/allocator_helpers.hpp> #include <boost/unordered/detail/equivalent.hpp> #include <boost/unordered/detail/unique.hpp> #include <boost/unordered/detail/util.hpp> #include <boost/functional/hash.hpp> #include <boost/move/move.hpp> -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) #include <initializer_list> #endif @@ -131,7 +130,7 @@ namespace unordered unordered_set(unordered_set&&, allocator_type const&); #endif -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) unordered_set( std::initializer_list<value_type>, size_type = boost::unordered::detail::default_bucket_count, @@ -174,7 +173,7 @@ namespace unordered #endif #endif -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) unordered_set& operator=(std::initializer_list<value_type>); #endif @@ -201,12 +200,12 @@ namespace unordered iterator begin() { - return iterator(table_.begin()); + return table_.begin(); } const_iterator begin() const { - return const_iterator(table_.begin()); + return table_.begin(); } iterator end() @@ -221,7 +220,7 @@ namespace unordered const_iterator cbegin() const { - return const_iterator(table_.begin()); + return table_.begin(); } const_iterator cend() const @@ -231,15 +230,15 @@ namespace unordered // emplace -#if defined(BOOST_UNORDERED_VARIADIC_MOVE) +#if !defined(BOOST_NO_VARIADIC_TEMPLATES) template <class... Args> - std::pair<iterator, bool> emplace(Args&&... args) + std::pair<iterator, bool> emplace(BOOST_FWD_REF(Args)... args) { return table_.emplace(boost::forward<Args>(args)...); } template <class... Args> - iterator emplace_hint(const_iterator, Args&&... args) + iterator emplace_hint(const_iterator, BOOST_FWD_REF(Args)... args) { return table_.emplace(boost::forward<Args>(args)...).first; } @@ -400,7 +399,7 @@ namespace unordered template <class InputIt> void insert(InputIt, InputIt); -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) void insert(std::initializer_list<value_type>); #endif @@ -450,7 +449,8 @@ namespace unordered size_type bucket(const key_type& k) const { - return table_.hash_function()(k) % table_.bucket_count_; + return table::to_bucket(table_.bucket_count_, + table_.hash(k)); } local_iterator begin(size_type n) @@ -499,6 +499,7 @@ namespace unordered float load_factor() const; void max_load_factor(float); void rehash(size_type); + void reserve(size_type); #if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582) friend bool operator==<T,H,P,A>( @@ -601,7 +602,7 @@ namespace unordered unordered_multiset(unordered_multiset&&, allocator_type const&); #endif -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) unordered_multiset( std::initializer_list<value_type>, size_type = boost::unordered::detail::default_bucket_count, @@ -645,7 +646,7 @@ namespace unordered #endif #endif -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) unordered_multiset& operator=(std::initializer_list<value_type>); #endif @@ -702,15 +703,15 @@ namespace unordered // emplace -#if defined(BOOST_UNORDERED_VARIADIC_MOVE) +#if !defined(BOOST_NO_VARIADIC_TEMPLATES) template <class... Args> - iterator emplace(Args&&... args) + iterator emplace(BOOST_FWD_REF(Args)... args) { return table_.emplace(boost::forward<Args>(args)...); } template <class... Args> - iterator emplace_hint(const_iterator, Args&&... args) + iterator emplace_hint(const_iterator, BOOST_FWD_REF(Args)... args) { return table_.emplace(boost::forward<Args>(args)...); } @@ -871,7 +872,7 @@ namespace unordered template <class InputIt> void insert(InputIt, InputIt); -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) void insert(std::initializer_list<value_type>); #endif @@ -921,7 +922,8 @@ namespace unordered size_type bucket(const key_type& k) const { - return table_.hash_function()(k) % table_.bucket_count_; + return table::to_bucket(table_.bucket_count_, + table_.hash(k)); } local_iterator begin(size_type n) @@ -970,6 +972,7 @@ namespace unordered float load_factor() const; void max_load_factor(float); void rehash(size_type); + void reserve(size_type); #if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582) friend bool operator==<T,H,P,A>( @@ -1059,7 +1062,7 @@ namespace unordered #endif -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) template <class T, class H, class P, class A> unordered_set<T,H,P,A>::unordered_set( @@ -1101,7 +1104,7 @@ namespace unordered table_.insert_range(first, last); } -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) template <class T, class H, class P, class A> void unordered_set<T,H,P,A>::insert( std::initializer_list<value_type> list) @@ -1114,7 +1117,7 @@ namespace unordered typename unordered_set<T,H,P,A>::iterator unordered_set<T,H,P,A>::erase(const_iterator position) { - return iterator(table_.erase(position.node_)); + return table_.erase(position); } template <class T, class H, class P, class A> @@ -1129,7 +1132,7 @@ namespace unordered unordered_set<T,H,P,A>::erase( const_iterator first, const_iterator last) { - return iterator(table_.erase_range(first.node_, last.node_)); + return table_.erase_range(first, last); } template <class T, class H, class P, class A> @@ -1166,7 +1169,7 @@ namespace unordered typename unordered_set<T,H,P,A>::const_iterator unordered_set<T,H,P,A>::find(const key_type& k) const { - return const_iterator(table_.find_node(k)); + return table_.find_node(k); } template <class T, class H, class P, class A> @@ -1178,7 +1181,7 @@ namespace unordered CompatibleHash const& hash, CompatiblePredicate const& eq) const { - return const_iterator(table_.generic_find_node(k, hash, eq)); + return table_.generic_find_node(k, hash, eq); } template <class T, class H, class P, class A> @@ -1225,6 +1228,12 @@ namespace unordered } template <class T, class H, class P, class A> + void unordered_set<T,H,P,A>::reserve(size_type n) + { + table_.reserve(n); + } + + template <class T, class H, class P, class A> inline bool operator==( unordered_set<T,H,P,A> const& m1, unordered_set<T,H,P,A> const& m2) @@ -1337,7 +1346,7 @@ namespace unordered #endif -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) template <class T, class H, class P, class A> unordered_multiset<T,H,P,A>::unordered_multiset( @@ -1379,7 +1388,7 @@ namespace unordered table_.insert_range(first, last); } -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) template <class T, class H, class P, class A> void unordered_multiset<T,H,P,A>::insert( std::initializer_list<value_type> list) @@ -1392,7 +1401,7 @@ namespace unordered typename unordered_multiset<T,H,P,A>::iterator unordered_multiset<T,H,P,A>::erase(const_iterator position) { - return iterator(table_.erase(position.node_)); + return table_.erase(position); } template <class T, class H, class P, class A> @@ -1407,7 +1416,7 @@ namespace unordered unordered_multiset<T,H,P,A>::erase( const_iterator first, const_iterator last) { - return iterator(table_.erase_range(first.node_, last.node_)); + return table_.erase_range(first, last); } template <class T, class H, class P, class A> @@ -1444,7 +1453,7 @@ namespace unordered typename unordered_multiset<T,H,P,A>::const_iterator unordered_multiset<T,H,P,A>::find(const key_type& k) const { - return const_iterator(table_.find_node(k)); + return table_.find_node(k); } template <class T, class H, class P, class A> @@ -1456,7 +1465,7 @@ namespace unordered CompatibleHash const& hash, CompatiblePredicate const& eq) const { - return const_iterator(table_.generic_find_node(k, hash, eq)); + return table_.generic_find_node(k, hash, eq); } template <class T, class H, class P, class A> @@ -1503,6 +1512,12 @@ namespace unordered } template <class T, class H, class P, class A> + void unordered_multiset<T,H,P,A>::reserve(size_type n) + { + table_.reserve(n); + } + + template <class T, class H, class P, class A> inline bool operator==( unordered_multiset<T,H,P,A> const& m1, unordered_multiset<T,H,P,A> const& m2) diff --git a/boost/unordered/unordered_set_fwd.hpp b/boost/unordered/unordered_set_fwd.hpp index f19c137d74..0c8b6d8d63 100644 --- a/boost/unordered/unordered_set_fwd.hpp +++ b/boost/unordered/unordered_set_fwd.hpp @@ -10,12 +10,22 @@ # pragma once #endif +#include <boost/config.hpp> +#include <memory> +#include <functional> +#include <boost/functional/hash_fwd.hpp> #include <boost/unordered/detail/fwd.hpp> namespace boost { namespace unordered { + template <class T, + class H = boost::hash<T>, + class P = std::equal_to<T>, + class A = std::allocator<T> > + class unordered_set; + template <class T, class H, class P, class A> inline bool operator==(unordered_set<T, H, P, A> const&, unordered_set<T, H, P, A> const&); @@ -26,6 +36,12 @@ namespace boost inline void swap(unordered_set<T, H, P, A> &m1, unordered_set<T, H, P, A> &m2); + template <class T, + class H = boost::hash<T>, + class P = std::equal_to<T>, + class A = std::allocator<T> > + class unordered_multiset; + template <class T, class H, class P, class A> inline bool operator==(unordered_multiset<T, H, P, A> const&, unordered_multiset<T, H, P, A> const&); |