diff options
Diffstat (limited to '3rdParty/Boost/src/boost/unordered')
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/allocate.hpp | 1241 | ||||
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/allocator_helpers.hpp | 111 | ||||
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/buckets.hpp | 882 | ||||
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp | 939 | ||||
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/extract_key.hpp | 82 | ||||
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/fwd.hpp | 935 | ||||
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/move.hpp | 243 | ||||
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/node.hpp | 226 | ||||
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/table.hpp | 1407 | ||||
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/unique.hpp | 984 | ||||
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/util.hpp | 321 | ||||
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/unordered_map.hpp | 1752 | ||||
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/unordered_map_fwd.hpp | 76 |
13 files changed, 5412 insertions, 3787 deletions
diff --git a/3rdParty/Boost/src/boost/unordered/detail/allocate.hpp b/3rdParty/Boost/src/boost/unordered/detail/allocate.hpp new file mode 100644 index 0000000..b6f1c79 --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/allocate.hpp @@ -0,0 +1,1241 @@ + +// 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 + +}}} + +//////////////////////////////////////////////////////////////////////////////// +// +// 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 + + +namespace boost { namespace unordered { namespace detail { + + //////////////////////////////////////////////////////////////////////////// + // call_construct + +#if !defined(BOOST_NO_VARIADIC_TEMPLATES) + +# if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT + + template <typename Alloc, typename T, typename... Args> + inline void call_construct(Alloc& alloc, T* address, + BOOST_FWD_REF(Args)... args) + { + boost::unordered::detail::allocator_traits<Alloc>::construct(alloc, + address, boost::forward<Args>(args)...); + } + + template <typename Alloc, typename T> + inline void destroy_value_impl(Alloc& alloc, T* x) { + boost::unordered::detail::allocator_traits<Alloc>::destroy(alloc, x); + } + + +# else + + template <typename Alloc, typename T, typename... Args> + inline void call_construct(Alloc&, T* address, + BOOST_FWD_REF(Args)... args) + { + new((void*) address) T(boost::forward<Args>(args)...); + } + + template <typename Alloc, typename T> + inline void destroy_value_impl(Alloc&, T* x) { + boost::unordered::detail::destroy(x); + } + + +# endif + +#else + + template <typename Alloc, typename T> + inline void destroy_value_impl(Alloc&, T* x) { + boost::unordered::detail::destroy(x); + } + +#endif + + //////////////////////////////////////////////////////////////////////////// + // Construct from tuple + // + // Used for piecewise construction. + +#if !defined(BOOST_NO_VARIADIC_TEMPLATES) + +# define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(n, namespace_) \ + template<typename Alloc, typename T> \ + void construct_from_tuple(Alloc& alloc, T* ptr, namespace_ tuple<>) \ + { \ + boost::unordered::detail::call_construct(alloc, ptr); \ + } \ + \ + BOOST_PP_REPEAT_FROM_TO(1, n, \ + BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL, namespace_) + +# define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL(z, n, namespace_) \ + template<typename Alloc, typename T, \ + BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ + void construct_from_tuple(Alloc& alloc, T* ptr, \ + namespace_ tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \ + { \ + boost::unordered::detail::call_construct(alloc, ptr, \ + BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_) \ + ); \ + } + +# define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) \ + namespace_ get<n>(x) + +#elif !defined(__SUNPRO_CC) + +# define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(n, namespace_) \ + template<typename Alloc, typename T> \ + void construct_from_tuple(Alloc&, T* ptr, namespace_ tuple<>) \ + { \ + new ((void*) ptr) T(); \ + } \ + \ + BOOST_PP_REPEAT_FROM_TO(1, n, \ + BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL, namespace_) + +# define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL(z, n, namespace_) \ + template<typename Alloc, typename T, \ + BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ + void construct_from_tuple(Alloc&, T* ptr, \ + namespace_ tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \ + { \ + new ((void*) ptr) T( \ + BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_) \ + ); \ + } + +# define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) \ + namespace_ get<n>(x) + +#else + + template <int N> struct length {}; + +# define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(n, namespace_) \ + template<typename Alloc, typename T> \ + void construct_from_tuple_impl( \ + boost::unordered::detail::length<0>, Alloc&, T* ptr, \ + namespace_ tuple<>) \ + { \ + new ((void*) ptr) T(); \ + } \ + \ + BOOST_PP_REPEAT_FROM_TO(1, n, \ + BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL, namespace_) + +# define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL(z, n, namespace_) \ + template<typename Alloc, typename T, \ + BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \ + void construct_from_tuple_impl( \ + boost::unordered::detail::length<n>, Alloc&, T* ptr, \ + namespace_ tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \ + { \ + new ((void*) ptr) T( \ + BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_) \ + ); \ + } + +# define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) \ + namespace_ get<n>(x) + +#endif + +BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(10, boost::) + +#if !defined(__SUNPRO_CC) && !defined(BOOST_NO_CXX11_HDR_TUPLE) + BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(10, std::) +#endif + +#undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE +#undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL +#undef BOOST_UNORDERED_GET_TUPLE_ARG + +#if defined(__SUNPRO_CC) + + template <typename Alloc, typename T, typename Tuple> + void construct_from_tuple(Alloc& alloc, T* ptr, Tuple const& x) + { + construct_from_tuple_impl( + boost::unordered::detail::length< + boost::tuples::length<Tuple>::value>(), + alloc, 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 + +// TODO: Full construct? +#if !defined(BOOST_NO_VARIADIC_TEMPLATES) + + //////////////////////////////////////////////////////////////////////////// + // Construct from variadic parameters + + template <typename Alloc, typename T, typename... Args> + inline void construct_value_impl(Alloc& alloc, T* address, + BOOST_FWD_REF(Args)... args) + { + boost::unordered::detail::call_construct(alloc, + address, boost::forward<Args>(args)...); + } + + template <typename Alloc, typename A, typename B, + typename A0, typename A1, typename A2> + inline typename enable_if<piecewise3<A, B, A0>, void>::type + construct_value_impl(Alloc& alloc, 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(alloc, + boost::addressof(address->first), boost::forward<A1>(a1)); + boost::unordered::detail::construct_from_tuple(alloc, + boost::addressof(address->second), boost::forward<A2>(a2)); + } + +#if defined(BOOST_UNORDERED_DEPRECATED_PAIR_CONSTRUCT) + + template <typename Alloc, typename A, typename B, typename A0> + inline typename enable_if<emulation1<A, B, A0>, void>::type + construct_value_impl(Alloc& alloc, std::pair<A, B>* address, + BOOST_FWD_REF(A0) a0) + { + boost::unordered::detail::call_construct(alloc, + boost::addressof(address->first),boost::forward<A0>(a0)); + boost::unordered::detail::call_construct(alloc, + boost::addressof(address->second)); + } + + template <typename Alloc, typename A, typename B, + typename A0, typename A1, typename A2> + inline typename enable_if<emulation3<A, B, A0>, void>::type + construct_value_impl(Alloc& alloc, std::pair<A, B>* address, + BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2) + { + boost::unordered::detail::call_construct(alloc, + boost::addressof(address->first),boost::forward<A0>(a0)); + boost::unordered::detail::call_construct(alloc, + boost::addressof(address->second), + boost::forward<A1>(a1), + boost::forward<A2>(a2)); + } + + template <typename Alloc, typename A, typename B, + typename A0, typename A1, typename A2, typename A3, + typename... Args> + inline void construct_value_impl(Alloc& alloc, 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) + { + boost::unordered::detail::call_construct(alloc, + boost::addressof(address->first),boost::forward<A0>(a0)); + boost::unordered::detail::call_construct(alloc, + boost::addressof(address->second), + 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 Alloc, typename T, \ + BOOST_PP_ENUM_PARAMS_Z(z, num_params, typename A) \ + > \ + inline void construct_value_impl(Alloc&, T* address, \ + boost::unordered::detail::BOOST_PP_CAT(emplace_args,num_params) < \ + BOOST_PP_ENUM_PARAMS_Z(z, num_params, A) \ + > const& args) \ + { \ + new((void*) address) T( \ + BOOST_PP_ENUM_##z(num_params, BOOST_UNORDERED_CALL_FORWARD, \ + args.a)); \ + } + + template <typename Alloc, typename T, typename A0> + inline void construct_value_impl(Alloc&, T* address, + emplace_args1<A0> const& args) + { + new((void*) address) T(boost::forward<A0>(args.a0)); + } + + template <typename Alloc, typename T, typename A0, typename A1> + inline void construct_value_impl(Alloc&, T* address, + emplace_args2<A0, A1> const& args) + { + new((void*) address) T( + boost::forward<A0>(args.a0), + boost::forward<A1>(args.a1) + ); + } + + template <typename Alloc, typename T, typename A0, typename A1, typename A2> + inline void construct_value_impl(Alloc&, T* address, + emplace_args3<A0, A1, A2> const& args) + { + new((void*) address) T( + boost::forward<A0>(args.a0), + boost::forward<A1>(args.a1), + boost::forward<A2>(args.a2) + ); + } + + BOOST_PP_REPEAT_FROM_TO(4, BOOST_UNORDERED_EMPLACE_LIMIT, + BOOST_UNORDERED_CONSTRUCT_IMPL, _) + +#undef BOOST_UNORDERED_CONSTRUCT_IMPL + + template <typename Alloc, typename A, typename B, + typename A0, typename A1, typename A2> + inline void construct_value_impl(Alloc& alloc, 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(alloc, + boost::addressof(address->first), args.a1); + boost::unordered::detail::construct_from_tuple(alloc, + boost::addressof(address->second), args.a2); + } + +#if defined(BOOST_UNORDERED_DEPRECATED_PAIR_CONSTRUCT) + + template <typename Alloc, typename A, typename B, typename A0> + inline void construct_value_impl(Alloc&, 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 Alloc, typename A, typename B, + typename A0, typename A1, typename A2> + inline void construct_value_impl(Alloc&, 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 Alloc, typename A, typename B, \ + BOOST_PP_ENUM_PARAMS_Z(z, num_params, typename A) \ + > \ + inline void construct_value_impl(Alloc&, 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 + +}}} + +//////////////////////////////////////////////////////////////////////////////// +// +// Some helper functions for allocating & constructing + +namespace boost { namespace unordered { namespace detail { + + //////////////////////////////////////////////////////////////////////////// + // + // 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/3rdParty/Boost/src/boost/unordered/detail/allocator_helpers.hpp b/3rdParty/Boost/src/boost/unordered/detail/allocator_helpers.hpp deleted file mode 100644 index 2c64223..0000000 --- a/3rdParty/Boost/src/boost/unordered/detail/allocator_helpers.hpp +++ /dev/null @@ -1,111 +0,0 @@ - -// Copyright 2005-2009 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) - -// A couple of templates to make using allocators easier. - -#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> - -#if (defined(BOOST_NO_STD_ALLOCATOR) || defined(BOOST_DINKUMWARE_STDLIB)) \ - && !defined(__BORLANDC__) -# define BOOST_UNORDERED_USE_ALLOCATOR_UTILITIES -#endif - -#if defined(BOOST_UNORDERED_USE_ALLOCATOR_UTILITIES) -# include <boost/detail/allocator_utilities.hpp> -#endif - -namespace boost { namespace unordered_detail { - - // rebind_wrap - // - // Rebind allocators. For some problematic libraries, use rebind_to - // from <boost/detail/allocator_utilities.hpp>. - -#if defined(BOOST_UNORDERED_USE_ALLOCATOR_UTILITIES) - template <class Alloc, class T> - struct rebind_wrap : ::boost::detail::allocator::rebind_to<Alloc, T> {}; -#else - template <class Alloc, class T> - struct rebind_wrap - { - typedef BOOST_DEDUCED_TYPENAME - Alloc::BOOST_NESTED_TEMPLATE rebind<T>::other - type; - }; -#endif - - // allocator_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 <class Allocator> - struct allocator_array_constructor - { - typedef BOOST_DEDUCED_TYPENAME Allocator::pointer pointer; - - Allocator& alloc_; - pointer ptr_; - pointer constructed_; - std::size_t length_; - - allocator_array_constructor(Allocator& a) - : alloc_(a), ptr_(), constructed_(), length_(0) - { - constructed_ = pointer(); - ptr_ = pointer(); - } - - ~allocator_array_constructor() { - if (ptr_) { - for(pointer p = ptr_; p != constructed_; ++p) - alloc_.destroy(p); - - alloc_.deallocate(ptr_, length_); - } - } - - template <class V> - void construct(V const& v, std::size_t l) - { - BOOST_ASSERT(!ptr_); - length_ = l; - ptr_ = alloc_.allocate(length_); - pointer end = ptr_ + static_cast<std::ptrdiff_t>(length_); - for(constructed_ = ptr_; constructed_ != end; ++constructed_) - alloc_.construct(constructed_, v); - } - - pointer get() const - { - return ptr_; - } - - pointer release() - { - pointer p(ptr_); - ptr_ = pointer(); - return p; - } - private: - allocator_array_constructor(allocator_array_constructor const&); - allocator_array_constructor& operator=( - allocator_array_constructor const&); - }; -}} - -#if defined(BOOST_UNORDERED_USE_ALLOCATOR_UTILITIES) -# undef BOOST_UNORDERED_USE_ALLOCATOR_UTILITIES -#endif - -#endif diff --git a/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp b/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp index 913dbcd..def5c7c 100644 --- a/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp +++ b/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp @@ -1,183 +1,799 @@ // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. -// Copyright (C) 2005-2009 Daniel James +// Copyright (C) 2005-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) #ifndef BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED #define BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED -#include <boost/config.hpp> -#include <boost/assert.hpp> -#include <boost/unordered/detail/node.hpp> +#if defined(_MSC_VER) && (_MSC_VER >= 1020) +# pragma once +#endif + #include <boost/unordered/detail/util.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> + +namespace boost { namespace unordered { namespace detail { + + template <typename Types> struct table; + template <typename NodePointer> struct bucket; + struct ptr_bucket; + template <typename Types> struct table_impl; + template <typename Types> struct grouped_table_impl; + +}}} + +namespace boost { namespace unordered { namespace iterator_detail { -namespace boost { namespace unordered_detail { - //////////////////////////////////////////////////////////////////////////// - // Buckets - - template <class A, class G> - inline std::size_t hash_buckets<A, G>::max_bucket_count() const { - // -1 to account for the sentinel. - return prev_prime(this->bucket_alloc().max_size() - 1); - } + // Iterators + // + // all no throw - template <class A, class G> - inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::bucket_ptr - hash_buckets<A, G>::get_bucket(std::size_t num) const + 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&> { - return buckets_ + static_cast<std::ptrdiff_t>(num); - } +#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) {} - template <class A, class G> - inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::bucket_ptr - hash_buckets<A, G>::bucket_ptr_from_hash(std::size_t hashed) const + 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&> { - return get_bucket(hashed % bucket_count_); - } - - template <class A, class G> - std::size_t hash_buckets<A, G>::bucket_size(std::size_t index) 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(!buckets_) return 0; - bucket_ptr ptr = get_bucket(index)->next_; - std::size_t count = 0; - while(ptr) { - ++count; - ptr = ptr->next_; - } - return count; - } +#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> + 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: - template <class A, class G> - inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::node_ptr - hash_buckets<A, G>::bucket_begin(std::size_t num) const + 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&> { - return buckets_ ? get_bucket(num)->next_ : node_ptr(); - } + friend struct boost::unordered::iterator_detail::iterator< + NodePointer, Value>; - //////////////////////////////////////////////////////////////////////////// - // Delete +#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) + template <typename> + friend struct boost::unordered::detail::table; + template <typename> + friend struct boost::unordered::detail::table_impl; + template <typename> + friend struct boost::unordered::detail::grouped_table_impl; + + private: +#endif + + typedef 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 { + + /////////////////////////////////////////////////////////////////// + // + // Node construction + + template <typename NodeAlloc> + struct node_constructor + { + private: + + typedef NodeAlloc node_allocator; + typedef boost::unordered::detail::allocator_traits<NodeAlloc> + node_allocator_traits; + typedef typename node_allocator_traits::value_type node; + typedef typename node_allocator_traits::pointer node_pointer; + typedef typename node::value_type value_type; + + protected: + + node_allocator& alloc_; + + private: + + node_pointer node_; + bool node_constructed_; + bool value_constructed_; + + public: + + node_constructor(node_allocator& n) : + alloc_(n), + node_(), + node_constructed_(false), + value_constructed_(false) + { + } + + ~node_constructor(); + + void construct(); + + template <BOOST_UNORDERED_EMPLACE_TEMPLATE> + void construct_with_value(BOOST_UNORDERED_EMPLACE_ARGS) + { + construct(); + boost::unordered::detail::construct_value_impl( + alloc_, node_->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD); + value_constructed_ = true; + } + + template <typename A0> + void construct_with_value2(BOOST_FWD_REF(A0) a0) + { + construct(); + boost::unordered::detail::construct_value_impl( + alloc_, node_->value_ptr(), + BOOST_UNORDERED_EMPLACE_ARGS1(boost::forward<A0>(a0))); + value_constructed_ = true; + } - template <class A, class G> - inline void hash_buckets<A, G>::delete_node(node_ptr b) + value_type const& value() const { + BOOST_ASSERT(node_ && node_constructed_ && value_constructed_); + return node_->value(); + } + + // no throw + node_pointer release() + { + BOOST_ASSERT(node_ && node_constructed_); + node_pointer p = node_; + node_ = node_pointer(); + return p; + } + + private: + node_constructor(node_constructor const&); + node_constructor& operator=(node_constructor const&); + }; + + template <typename Alloc> + node_constructor<Alloc>::~node_constructor() { - node* raw_ptr = static_cast<node*>(&*b); - boost::unordered_detail::destroy(raw_ptr->value_ptr()); - real_node_ptr n(node_alloc().address(*raw_ptr)); - node_alloc().destroy(n); - node_alloc().deallocate(n, 1); + if (node_) { + if (value_constructed_) { + boost::unordered::detail::destroy_value_impl(alloc_, + node_->value_ptr()); + } + + if (node_constructed_) { + node_allocator_traits::destroy(alloc_, + boost::addressof(*node_)); + } + + node_allocator_traits::deallocate(alloc_, node_, 1); + } } - template <class A, class G> - inline void hash_buckets<A, G>::clear_bucket(bucket_ptr b) + template <typename Alloc> + void node_constructor<Alloc>::construct() { - node_ptr node_it = b->next_; - b->next_ = node_ptr(); + if(!node_) { + node_constructed_ = false; + value_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_); - while(node_it) { - node_ptr node_to_delete = node_it; - node_it = node_it->next_; - delete_node(node_to_delete); + if (value_constructed_) + { + boost::unordered::detail::destroy_value_impl(alloc_, + node_->value_ptr()); + value_constructed_ = false; + } } } - template <class A, class G> - inline void hash_buckets<A, G>::delete_buckets() - { - bucket_ptr end = this->get_bucket(this->bucket_count_); + /////////////////////////////////////////////////////////////////// + // + // Node Holder + // + // Temporary store for nodes. Deletes any that aren't used. + + template <typename NodeAlloc> + struct node_holder : private node_constructor<NodeAlloc> + { + private: + typedef node_constructor<NodeAlloc> base; + + typedef NodeAlloc node_allocator; + typedef boost::unordered::detail::allocator_traits<NodeAlloc> + node_allocator_traits; + typedef typename node_allocator_traits::value_type node; + typedef typename node_allocator_traits::pointer node_pointer; + typedef typename node::value_type value_type; + typedef typename node::link_pointer link_pointer; + typedef boost::unordered::iterator_detail:: + iterator<node_pointer, value_type> iterator; - for(bucket_ptr begin = this->buckets_; begin != end; ++begin) { - clear_bucket(begin); + node_pointer nodes_; + + public: + + template <typename Table> + explicit node_holder(Table& b) : + base(b.node_alloc()), + nodes_() + { + if (b.size_) { + typename Table::previous_pointer prev = b.get_previous_start(); + nodes_ = static_cast<node_pointer>(prev->next_); + prev->next_ = link_pointer(); + b.size_ = 0; + } } - // Destroy the buckets (including the sentinel bucket). - ++end; - for(bucket_ptr begin = this->buckets_; begin != end; ++begin) { - bucket_alloc().destroy(begin); + ~node_holder(); + + template <typename T> + inline void assign_impl(T const& v) { + nodes_->value() = v; } - bucket_alloc().deallocate(this->buckets_, this->bucket_count_ + 1); + template <typename T1, typename T2> + inline void assign_impl(std::pair<T1 const, T2> const& v) { + const_cast<T1&>(nodes_->value().first) = v.first; + nodes_->value().second = v.second; + } - this->buckets_ = bucket_ptr(); - } + template <typename T> + inline void move_assign_impl(T& v) { + nodes_->value() = boost::move(v); + } - template <class A, class G> - inline std::size_t hash_buckets<A, G>::delete_nodes( - node_ptr begin, node_ptr end) + template <typename T1, typename T2> + inline void move_assign_impl(std::pair<T1 const, T2>& v) { + // TODO: Move key as well? + const_cast<T1&>(nodes_->value().first) = + boost::move(const_cast<T1&>(v.first)); + nodes_->value().second = boost::move(v.second); + } + + node_pointer copy_of(value_type const& v) + { + if (nodes_) { + assign_impl(v); + node_pointer p = nodes_; + nodes_ = static_cast<node_pointer>(p->next_); + p->init(static_cast<typename node::link_pointer>(p)); + p->next_ = link_pointer(); + return p; + } + else { + this->construct_with_value2(v); + return base::release(); + } + } + + node_pointer move_copy_of(value_type& v) + { + if (nodes_) { + move_assign_impl(v); + node_pointer p = nodes_; + nodes_ = static_cast<node_pointer>(p->next_); + p->init(static_cast<typename node::link_pointer>(p)); + p->next_ = link_pointer(); + return p; + } + else { + this->construct_with_value2(boost::move(v)); + return base::release(); + } + } + + iterator begin() const + { + return iterator(nodes_); + } + }; + + template <typename Alloc> + node_holder<Alloc>::~node_holder() { - std::size_t count = 0; - while(begin != end) { - node_ptr n = begin; - begin = begin->next_; - delete_node(n); - ++count; - } - return count; + while (nodes_) { + node_pointer p = nodes_; + nodes_ = static_cast<node_pointer>(p->next_); + + boost::unordered::detail::destroy_value_impl(this->alloc_, + p->value_ptr()); + node_allocator_traits::destroy(this->alloc_, boost::addressof(*p)); + node_allocator_traits::deallocate(this->alloc_, p, 1); + } } - //////////////////////////////////////////////////////////////////////////// - // Constructors and Destructors - - template <class A, class G> - inline hash_buckets<A, G>::hash_buckets( - node_allocator const& a, std::size_t bucket_count) - : buckets_(), - bucket_count_(bucket_count), - allocators_(a,a) + /////////////////////////////////////////////////////////////////// + // + // Bucket + + template <typename NodePointer> + struct bucket { - } + typedef NodePointer previous_pointer; + previous_pointer next_; + + bucket() : next_() {} - template <class A, class G> - inline hash_buckets<A, G>::~hash_buckets() + previous_pointer first_from_start() + { + return next_; + } + + enum { extra_node = true }; + }; + + struct ptr_bucket { - if(this->buckets_) { this->delete_buckets(); } - } - - template <class A, class G> - inline void hash_buckets<A, G>::create_buckets() + typedef ptr_bucket* previous_pointer; + previous_pointer next_; + + ptr_bucket() : next_(0) {} + + previous_pointer first_from_start() + { + return this; + } + + enum { extra_node = false }; + }; + + /////////////////////////////////////////////////////////////////// + // + // Hash Policy + // + // Don't really want table to derive from this, but will for now. + + template <typename SizeT> + struct prime_policy { - // The array constructor will clean up in the event of an - // exception. - allocator_array_constructor<bucket_allocator> - constructor(bucket_alloc()); - - // Creates an extra bucket to act as a sentinel. - constructor.construct(bucket(), this->bucket_count_ + 1); - - // Set up the sentinel (node_ptr cast) - bucket_ptr sentinel = constructor.get() + - static_cast<std::ptrdiff_t>(this->bucket_count_); - sentinel->next_ = sentinel; - - // Only release the buckets once everything is successfully - // done. - this->buckets_ = constructor.release(); - } + 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> {}; //////////////////////////////////////////////////////////////////////////// - // Constructors and Destructors + // Functions + + // Assigning and swapping the equality and hash function objects + // needs strong exception safety. To implement that normally we'd + // require one of them to be known to not throw and the other to + // guarantee strong exception safety. Unfortunately they both only + // have basic exception safety. So to acheive strong exception + // safety we have storage space for two copies, and assign the new + // copies to the unused space. Then switch to using that to use + // them. This is implemented in 'set_hash_functions' which + // atomically assigns the new function objects in a strongly + // exception safe manner. + + template <class H, class P> class set_hash_functions; - // no throw - template <class A, class G> - inline void hash_buckets<A, G>::move(hash_buckets& other) + template <class H, class P> + class functions { - BOOST_ASSERT(node_alloc() == other.node_alloc()); - if(this->buckets_) { this->delete_buckets(); } - this->buckets_ = other.buckets_; - this->bucket_count_ = other.bucket_count_; - other.buckets_ = bucket_ptr(); - other.bucket_count_ = 0; - } + friend class boost::unordered::detail::set_hash_functions<H, P>; + functions& operator=(functions const&); + + typedef compressed<H, P> function_pair; + + typedef typename boost::aligned_storage< + sizeof(function_pair), + boost::alignment_of<function_pair>::value>::type aligned_function; + + bool current_; // The currently active functions. + aligned_function funcs_[2]; + + function_pair const& current() const { + return *static_cast<function_pair const*>( + static_cast<void const*>(&funcs_[current_])); + } + + void construct(bool which, H const& hf, P const& eq) + { + new((void*) &funcs_[which]) function_pair(hf, eq); + } + + void construct(bool which, function_pair const& f) + { + new((void*) &funcs_[which]) function_pair(f); + } + + void destroy(bool which) + { + boost::unordered::detail::destroy((function_pair*)(&funcs_[which])); + } + + public: + + functions(H const& hf, P const& eq) + : current_(false) + { + construct(current_, hf, eq); + } - template <class A, class G> - inline void hash_buckets<A, G>::swap(hash_buckets<A, G>& other) + functions(functions const& bf) + : current_(false) + { + construct(current_, bf.current()); + } + + ~functions() { + this->destroy(current_); + } + + H const& hash_function() const { + return current().first(); + } + + P const& key_eq() const { + return current().second(); + } + }; + + template <class H, class P> + class set_hash_functions { - BOOST_ASSERT(node_alloc() == other.node_alloc()); - std::swap(buckets_, other.buckets_); - std::swap(bucket_count_, other.bucket_count_); - } -}} + set_hash_functions(set_hash_functions const&); + set_hash_functions& operator=(set_hash_functions const&); + + functions<H,P>& functions_; + bool tmp_functions_; + + public: + + set_hash_functions(functions<H,P>& f, H const& h, P const& p) + : functions_(f), + tmp_functions_(!f.current_) + { + f.construct(tmp_functions_, h, p); + } + + set_hash_functions(functions<H,P>& f, functions<H,P> const& other) + : functions_(f), + tmp_functions_(!f.current_) + { + f.construct(tmp_functions_, other.current()); + } + + ~set_hash_functions() + { + functions_.destroy(tmp_functions_); + } + + void commit() + { + functions_.current_ = tmp_functions_; + tmp_functions_ = !tmp_functions_; + } + }; + + //////////////////////////////////////////////////////////////////////////// + // 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 +}}} #endif diff --git a/3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp b/3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp index 1c497c3..3558b1c 100644 --- a/3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp +++ b/3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp @@ -1,304 +1,781 @@ // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. -// Copyright (C) 2005-2009 Daniel James +// Copyright (C) 2005-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) #ifndef BOOST_UNORDERED_DETAIL_EQUIVALENT_HPP_INCLUDED #define BOOST_UNORDERED_DETAIL_EQUIVALENT_HPP_INCLUDED +#if defined(_MSC_VER) && (_MSC_VER >= 1020) +# pragma once +#endif + #include <boost/unordered/detail/table.hpp> #include <boost/unordered/detail/extract_key.hpp> -namespace boost { namespace unordered_detail { +namespace boost { namespace unordered { namespace detail { + + template <typename A, typename T> struct grouped_node; + template <typename T> struct grouped_ptr_node; + template <typename Types> struct grouped_table_impl; - template <class T> - class hash_equivalent_table : public T::table + template <typename A, typename T> + struct grouped_node : + boost::unordered::detail::value_base<T> { - public: - typedef BOOST_DEDUCED_TYPENAME T::hasher hasher; - typedef BOOST_DEDUCED_TYPENAME T::key_equal key_equal; - typedef BOOST_DEDUCED_TYPENAME T::value_allocator value_allocator; - typedef BOOST_DEDUCED_TYPENAME T::key_type key_type; - typedef BOOST_DEDUCED_TYPENAME T::value_type value_type; - typedef BOOST_DEDUCED_TYPENAME T::table table; - typedef BOOST_DEDUCED_TYPENAME T::node_constructor node_constructor; - - typedef BOOST_DEDUCED_TYPENAME T::node node; - typedef BOOST_DEDUCED_TYPENAME T::node_ptr node_ptr; - typedef BOOST_DEDUCED_TYPENAME T::bucket_ptr bucket_ptr; - typedef BOOST_DEDUCED_TYPENAME T::iterator_base iterator_base; - typedef BOOST_DEDUCED_TYPENAME T::extractor extractor; + typedef typename ::boost::unordered::detail::rebind_wrap< + A, grouped_node<A, T> >::type::pointer link_pointer; - // Constructors + link_pointer next_; + link_pointer group_prev_; + std::size_t hash_; - hash_equivalent_table(std::size_t n, - hasher const& hf, key_equal const& eq, value_allocator const& a) - : table(n, hf, eq, a) {} - hash_equivalent_table(hash_equivalent_table const& x) - : table(x, x.node_alloc()) {} - hash_equivalent_table(hash_equivalent_table const& x, - value_allocator const& a) - : table(x, a) {} - hash_equivalent_table(hash_equivalent_table& x, move_tag m) - : table(x, m) {} - hash_equivalent_table(hash_equivalent_table& x, - value_allocator const& a, move_tag m) - : table(x, a, m) {} - ~hash_equivalent_table() {} + grouped_node() : + next_(), + group_prev_(), + hash_(0) + {} - // Insert methods + void init(link_pointer self) + { + group_prev_ = self; + } - iterator_base emplace_impl(node_constructor& a); - void emplace_impl_no_rehash(node_constructor& a); + private: + grouped_node& operator=(grouped_node const&); + }; - // equals + template <typename T> + struct grouped_ptr_node : + boost::unordered::detail::value_base<T>, + boost::unordered::detail::ptr_bucket + { + typedef boost::unordered::detail::ptr_bucket bucket_base; + typedef ptr_bucket* link_pointer; - bool equals(hash_equivalent_table const&) const; + link_pointer group_prev_; + std::size_t hash_; - inline node_ptr add_node(node_constructor& a, - bucket_ptr bucket, node_ptr pos); + grouped_ptr_node() : + bucket_base(), + group_prev_(0), + hash_(0) + {} -#if defined(BOOST_UNORDERED_STD_FORWARD) + void init(link_pointer self) + { + group_prev_ = self; + } - template <class... Args> - iterator_base emplace(Args&&... args); + private: + grouped_ptr_node& operator=(grouped_ptr_node const&); + }; -#else + // If the allocator uses raw pointers use grouped_ptr_node + // Otherwise use grouped_node. -#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \ - template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \ - iterator_base emplace(BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); + template <typename A, typename T, typename NodePtr, typename BucketPtr> + struct pick_grouped_node2 + { + typedef boost::unordered::detail::grouped_node<A, T> node; - BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, - BOOST_UNORDERED_INSERT_IMPL, _) + typedef typename boost::unordered::detail::allocator_traits< + typename boost::unordered::detail::rebind_wrap<A, node>::type + >::pointer node_pointer; -#undef BOOST_UNORDERED_INSERT_IMPL -#endif + typedef boost::unordered::detail::bucket<node_pointer> bucket; + typedef node_pointer link_pointer; + }; - template <class I> - void insert_for_range(I i, I j, forward_traversal_tag); - template <class I> - void insert_for_range(I i, I j, boost::incrementable_traversal_tag); - template <class I> - void insert_range(I i, I j); + template <typename A, typename T> + struct pick_grouped_node2<A, T, + boost::unordered::detail::grouped_ptr_node<T>*, + boost::unordered::detail::ptr_bucket*> + { + typedef boost::unordered::detail::grouped_ptr_node<T> node; + typedef boost::unordered::detail::ptr_bucket bucket; + typedef bucket* link_pointer; }; - template <class H, class P, class A> - struct multiset : public types< - BOOST_DEDUCED_TYPENAME A::value_type, - BOOST_DEDUCED_TYPENAME A::value_type, - H, P, A, - set_extractor<BOOST_DEDUCED_TYPENAME A::value_type>, - grouped> + template <typename A, typename T> + struct pick_grouped_node { - typedef hash_equivalent_table<multiset<H, P, A> > impl; - typedef hash_table<multiset<H, P, A> > table; + typedef boost::unordered::detail::allocator_traits< + typename boost::unordered::detail::rebind_wrap<A, + boost::unordered::detail::grouped_ptr_node<T> >::type + > tentative_node_traits; + + typedef boost::unordered::detail::allocator_traits< + typename boost::unordered::detail::rebind_wrap<A, + boost::unordered::detail::ptr_bucket >::type + > tentative_bucket_traits; + + typedef pick_grouped_node2<A, T, + typename tentative_node_traits::pointer, + typename tentative_bucket_traits::pointer> pick; + + typedef typename pick::node node; + typedef typename pick::bucket bucket; + typedef typename pick::link_pointer link_pointer; }; - template <class K, class H, class P, class A> - struct multimap : public types< - K, BOOST_DEDUCED_TYPENAME A::value_type, - H, P, A, - map_extractor<K, BOOST_DEDUCED_TYPENAME A::value_type>, - grouped> + template <typename A, typename T, typename H, typename P> + struct multiset { - typedef hash_equivalent_table<multimap<K, H, P, A> > impl; - typedef hash_table<multimap<K, H, P, A> > table; + typedef boost::unordered::detail::multiset<A, T, H, P> types; + + typedef A allocator; + typedef T value_type; + typedef H hasher; + typedef P key_equal; + typedef T key_type; + + typedef boost::unordered::detail::allocator_traits<allocator> traits; + typedef boost::unordered::detail::pick_grouped_node<allocator, + value_type> pick; + typedef typename pick::node node; + typedef typename pick::bucket bucket; + typedef typename pick::link_pointer link_pointer; + + 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; }; - //////////////////////////////////////////////////////////////////////////// - // Equality + template <typename A, typename K, typename M, typename H, typename P> + struct multimap + { + typedef boost::unordered::detail::multimap<A, K, M, H, P> types; + + typedef A allocator; + typedef std::pair<K const, M> value_type; + typedef H hasher; + typedef P key_equal; + typedef K key_type; + + typedef boost::unordered::detail::allocator_traits<allocator> traits; + typedef boost::unordered::detail::pick_grouped_node<allocator, + value_type> pick; + typedef typename pick::node node; + typedef typename pick::bucket bucket; + typedef typename pick::link_pointer link_pointer; + + 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 <class T> - bool hash_equivalent_table<T> - ::equals(hash_equivalent_table<T> const& other) const + template <typename Types> + struct grouped_table_impl : boost::unordered::detail::table<Types> { - if(this->size_ != other.size_) return false; - if(!this->size_) return true; + typedef boost::unordered::detail::table<Types> table; + typedef typename table::value_type value_type; + typedef typename table::bucket bucket; + typedef typename table::policy policy; + typedef typename table::node_pointer node_pointer; + typedef typename table::node_allocator node_allocator; + typedef typename table::node_allocator_traits node_allocator_traits; + typedef typename table::bucket_pointer bucket_pointer; + typedef typename table::link_pointer link_pointer; + typedef typename table::previous_pointer previous_pointer; + typedef typename table::hasher hasher; + typedef typename table::key_equal key_equal; + typedef typename table::key_type key_type; + 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 + + grouped_table_impl(std::size_t n, + hasher const& hf, + key_equal const& eq, + node_allocator const& a) + : table(n, hf, eq, a) + {} + + grouped_table_impl(grouped_table_impl const& x) + : table(x, node_allocator_traits:: + select_on_container_copy_construction(x.node_alloc())) + { + this->init(x); + } + + grouped_table_impl(grouped_table_impl const& x, + node_allocator const& a) + : table(x, a) + { + this->init(x); + } - bucket_ptr end = this->get_bucket(this->bucket_count_); - for(bucket_ptr i = this->cached_begin_bucket_; i != end; ++i) + grouped_table_impl(grouped_table_impl& x, + boost::unordered::detail::move_tag m) + : table(x, m) + {} + + grouped_table_impl(grouped_table_impl& x, + node_allocator const& a, + boost::unordered::detail::move_tag m) + : table(x, a, m) + { + this->move_init(x); + } + + // Accessors + + template <class Key, class Pred> + iterator find_node_impl( + std::size_t key_hash, + Key const& k, + Pred const& eq) const { - node_ptr it1 = i->next_; - while(BOOST_UNORDERED_BORLAND_BOOL(it1)) + std::size_t bucket_index = + policy::to_bucket(this->bucket_count_, key_hash); + iterator n = this->begin(bucket_index); + + for (;;) { - node_ptr it2 = other.find_iterator(this->get_key_from_ptr(it1)); - if(!BOOST_UNORDERED_BORLAND_BOOL(it2)) return false; - - node_ptr end1 = node::next_group(it1); - node_ptr end2 = node::next_group(it2); - - do { - if(!extractor::compare_mapped( - node::get_value(it1), node::get_value(it2))) - return false; - it1 = it1->next_; - it2 = it2->next_; - } while(it1 != end1 && it2 != end2); - if(it1 != end1 || it2 != end2) return false; + if (!n.node_) return n; + + std::size_t node_hash = n.node_->hash_; + if (key_hash == node_hash) + { + if (eq(k, this->get_key(*n))) + return n; + } + else + { + if (policy::to_bucket(this->bucket_count_, node_hash) + != bucket_index) + return iterator(); + } + + n = iterator(static_cast<node_pointer>( + static_cast<node_pointer>(n.node_->group_prev_)->next_)); } } - return true; - } + std::size_t count(key_type const& k) const + { + iterator n = this->find_node(k); + if (!n.node_) return 0; - //////////////////////////////////////////////////////////////////////////// - // A convenience method for adding nodes. + std::size_t x = 0; + node_pointer it = n.node_; + do { + it = static_cast<node_pointer>(it->group_prev_); + ++x; + } while(it != n.node_); - template <class T> - inline BOOST_DEDUCED_TYPENAME hash_equivalent_table<T>::node_ptr - hash_equivalent_table<T> - ::add_node(node_constructor& a, bucket_ptr bucket, node_ptr pos) - { - node_ptr n = a.release(); - if(BOOST_UNORDERED_BORLAND_BOOL(pos)) { - node::add_after_node(n, pos); + return x; } - else { - node::add_to_bucket(n, *bucket); - if(bucket < this->cached_begin_bucket_) - this->cached_begin_bucket_ = bucket; + + std::pair<iterator, iterator> + equal_range(key_type const& k) const + { + iterator n = this->find_node(k); + return std::make_pair( + n, n.node_ ? iterator( + static_cast<node_pointer>( + static_cast<node_pointer>(n.node_->group_prev_)->next_ + )) : n); } - ++this->size_; - return n; - } - //////////////////////////////////////////////////////////////////////////// - // Insert methods + // Equality - template <class T> - inline BOOST_DEDUCED_TYPENAME - hash_equivalent_table<T>::iterator_base - hash_equivalent_table<T>::emplace_impl(node_constructor& a) - { - key_type const& k = this->get_key(a.value()); - std::size_t hash_value = this->hash_function()(k); - - if(!this->size_) { - return this->emplace_empty_impl_with_node(a, 1); + bool equals(grouped_table_impl const& other) const + { + if(this->size_ != other.size_) return false; + + for(iterator n1 = this->begin(); n1.node_;) + { + 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; + } + + return true; } - else { - bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value); - node_ptr position = this->find_iterator(bucket, k); - // reserve has basic exception safety if the hash function - // throws, strong otherwise. - if(this->reserve_for_insert(this->size_ + 1)) - bucket = this->bucket_ptr_from_hash(hash_value); +#if !defined(BOOST_UNORDERED_DEPRECATED_EQUALITY) + + static bool group_equals(iterator n1, iterator end1, + iterator n2, iterator end2) + { + for(;;) + { + if (*n1 != *n2) break; - return iterator_base(bucket, add_node(a, bucket, position)); + ++n1; + ++n2; + + if (n1 == end1) return n2 == end2; + if (n2 == end2) return false; + } + + for(iterator n1a = n1, n2a = n2;;) + { + ++n1a; + ++n2a; + + if (n1a == end1) + { + if (n2a == end2) break; + else return false; + } + + if (n2a == end2) return false; + } + + iterator start = n1; + for(;n1 != end1; ++n1) + { + value_type const& v = *n1; + if (find(start, n1, v)) continue; + std::size_t matches = count_equal(n2, end2, v); + if (!matches) return false; + iterator next = n1; + ++next; + if (matches != 1 + count_equal(next, end1, v)) return false; + } + + return true; } - } - - template <class T> - inline void hash_equivalent_table<T> - ::emplace_impl_no_rehash(node_constructor& a) - { - key_type const& k = this->get_key(a.value()); - bucket_ptr bucket = this->get_bucket(this->bucket_index(k)); - add_node(a, bucket, this->find_iterator(bucket, k)); - } - -#if defined(BOOST_UNORDERED_STD_FORWARD) - - // Emplace (equivalent key containers) - // (I'm using an overloaded emplace for both 'insert' and 'emplace') - - // if hash function throws, basic exception safety - // strong otherwise - template <class T> - template <class... Args> - BOOST_DEDUCED_TYPENAME hash_equivalent_table<T>::iterator_base - hash_equivalent_table<T> - ::emplace(Args&&... args) - { - // Create the node before rehashing in case it throws an - // exception (need strong safety in such a case). - node_constructor a(*this); - a.construct(std::forward<Args>(args)...); - return emplace_impl(a); - } + static bool find(iterator n, iterator end, value_type const& v) + { + for(;n != end; ++n) + if (*n == v) + return true; + return false; + } + + static std::size_t count_equal(iterator n, iterator end, + value_type const& v) + { + std::size_t count = 0; + for(;n != end; ++n) + if (*n == v) ++count; + return count; + } #else -#define BOOST_UNORDERED_INSERT_IMPL(z, num_params, _) \ - template <class T> \ - template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \ - BOOST_DEDUCED_TYPENAME hash_equivalent_table<T>::iterator_base \ - hash_equivalent_table<T> \ - ::emplace(BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \ - { \ - node_constructor a(*this); \ - a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \ - return emplace_impl(a); \ - } - - BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, - BOOST_UNORDERED_INSERT_IMPL, _) - -#undef BOOST_UNORDERED_INSERT_IMPL + static bool group_equals(iterator n1, iterator end1, + iterator n2, iterator end2) + { + for(;;) + { + if(!extractor::compare_mapped(*n1, *n2)) + return false; + + ++n1; + ++n2; + + if (n1 == end1) return n2 == end2; + if (n2 == end2) return false; + } + } + #endif - //////////////////////////////////////////////////////////////////////////// - // Insert range methods + // Emplace/Insert - // if hash function throws, or inserting > 1 element, basic exception safety - // strong otherwise - template <class T> - template <class I> - inline void hash_equivalent_table<T> - ::insert_for_range(I i, I j, forward_traversal_tag) - { - if(i == j) return; - std::size_t distance = unordered_detail::distance(i, j); - if(distance == 1) { - emplace(*i); + static inline void add_after_node( + node_pointer n, + node_pointer pos) + { + n->next_ = static_cast<node_pointer>(pos->group_prev_)->next_; + n->group_prev_ = pos->group_prev_; + static_cast<node_pointer>(pos->group_prev_)->next_ = + static_cast<link_pointer>(n); + pos->group_prev_ = static_cast<link_pointer>(n); } - else { - node_constructor a(*this); - // Only require basic exception safety here - if(this->size_) { - this->reserve_for_insert(this->size_ + distance); + inline iterator add_node( + node_constructor& a, + std::size_t key_hash, + iterator pos) + { + node_pointer n = a.release(); + n->hash_ = key_hash; + if (pos.node_) { + this->add_after_node(n, pos.node_); + if (n->next_) { + 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( + 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(policy::to_bucket(this->bucket_count_, + static_cast<node_pointer>(start_node->next_)->hash_ + ))->next_ = n; + } + + b->next_ = start_node; + n->next_ = start_node->next_; + start_node->next_ = static_cast<link_pointer>(n); + } + else + { + n->next_ = b->next_->next_; + b->next_->next_ = static_cast<link_pointer>(n); + } + } + ++this->size_; + return iterator(n); + } + + iterator emplace_impl(node_constructor& a) + { + key_type const& k = this->get_key(a.value()); + 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, key_hash, position); + } + + void emplace_impl_no_rehash(node_constructor& a) + { + key_type const& k = this->get_key(a.value()); + 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> + iterator emplace(BOOST_UNORDERED_EMPLACE_ARGS) + { + node_constructor a(this->node_alloc()); + a.construct_with_value(BOOST_UNORDERED_EMPLACE_FORWARD); + + return iterator(emplace_impl(a)); + } + + //////////////////////////////////////////////////////////////////////// + // Insert range methods + + // if hash function throws, or inserting > 1 element, basic exception + // safety. Strong otherwise + template <class I> + typename boost::unordered::detail::enable_if_forward<I, void>::type + insert_range(I i, I j) + { + if(i == j) return; + + std::size_t distance = boost::unordered::detail::distance(i, j); + if(distance == 1) { + node_constructor a(this->node_alloc()); + a.construct_with_value2(*i); + emplace_impl(a); } else { - a.construct(*i++); - this->emplace_empty_impl_with_node(a, distance); + // Only require basic exception safety here + this->reserve_for_insert(this->size_ + distance); + + node_constructor a(this->node_alloc()); + for (; i != j; ++i) { + a.construct_with_value2(*i); + emplace_impl_no_rehash(a); + } } + } + template <class I> + typename boost::unordered::detail::disable_if_forward<I, void>::type + insert_range(I i, I j) + { + node_constructor a(this->node_alloc()); for (; i != j; ++i) { - a.construct(*i); - emplace_impl_no_rehash(a); + a.construct_with_value2(*i); + emplace_impl(a); } } - } - - // if hash function throws, or inserting > 1 element, basic exception safety - // strong otherwise - template <class T> - template <class I> - inline void hash_equivalent_table<T> - ::insert_for_range(I i, I j, boost::incrementable_traversal_tag) - { - node_constructor a(*this); - for (; i != j; ++i) { - a.construct(*i); - emplace_impl(a); + + //////////////////////////////////////////////////////////////////////// + // Erase + // + // no throw + + std::size_t erase_key(key_type const& k) + { + if(!this->size_) return 0; + + 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 = this_bucket->next_; + if (!prev) return 0; + + for (;;) + { + if (!prev->next_) return 0; + std::size_t node_hash = + static_cast<node_pointer>(prev->next_)->hash_; + if (policy::to_bucket(this->bucket_count_, node_hash) + != bucket_index) + return 0; + if (node_hash == key_hash && + this->key_eq()(k, this->get_key( + static_cast<node_pointer>(prev->next_)->value()))) + break; + prev = static_cast<previous_pointer>( + static_cast<node_pointer>(prev->next_)->group_prev_); + } + + node_pointer pos = static_cast<node_pointer>(prev->next_); + link_pointer end1 = + static_cast<node_pointer>(pos->group_prev_)->next_; + node_pointer end = static_cast<node_pointer>(end1); + prev->next_ = end1; + this->fix_buckets(this_bucket, prev, end); + return this->delete_nodes(c_iterator(pos), c_iterator(end)); } - } - // if hash function throws, or inserting > 1 element, basic exception safety - // strong otherwise - template <class T> - template <class I> - void hash_equivalent_table<T>::insert_range(I i, I j) - { - BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type - iterator_traversal_tag; - insert_for_range(i, j, iterator_traversal_tag); - } -}} + iterator erase(c_iterator r) + { + BOOST_ASSERT(r.node_); + iterator next(r.node_); + ++next; + + 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(this_bucket, prev, next.node_); + + this->delete_node(r); + + return next; + } + + iterator erase_range(c_iterator r1, c_iterator r2) + { + if (r1 == r2) return iterator(r2.node_); + + 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.node_, r2.node_); + this->fix_buckets_range(bucket_index, prev, r1.node_, r2.node_); + this->delete_nodes(r1, r2); + + return iterator(r2.node_); + } + + static previous_pointer unlink_node(bucket& b, node_pointer n) + { + node_pointer next = static_cast<node_pointer>(n->next_); + previous_pointer prev = + static_cast<previous_pointer>(n->group_prev_); + + if(prev->next_ != n) { + // The node is at the beginning of a group. + + // Find the previous node pointer: + prev = b.next_; + while(prev->next_ != n) { + prev = static_cast<previous_pointer>( + static_cast<node_pointer>(prev->next_)->group_prev_); + } + + // Remove from group + if (next && next->group_prev_ == static_cast<link_pointer>(n)) + { + next->group_prev_ = n->group_prev_; + } + } + else if (next && next->group_prev_ == static_cast<link_pointer>(n)) + { + // The deleted node is not at the end of the group, so + // change the link from the next node. + next->group_prev_ = n->group_prev_; + } + else { + // The deleted node is at the end of the group, so the + // first node in the group is pointing to it. + // Find that to change its pointer. + node_pointer x = static_cast<node_pointer>(n->group_prev_); + while(x->group_prev_ != static_cast<link_pointer>(n)) { + x = static_cast<node_pointer>(x->group_prev_); + } + x->group_prev_ = n->group_prev_; + } + + prev->next_ = static_cast<link_pointer>(next); + return prev; + } + + static previous_pointer unlink_nodes(bucket& b, + node_pointer begin, node_pointer end) + { + previous_pointer prev = static_cast<previous_pointer>( + begin->group_prev_); + + if(prev->next_ != static_cast<link_pointer>(begin)) { + // The node is at the beginning of a group. + + // Find the previous node pointer: + prev = b.next_; + while(prev->next_ != static_cast<link_pointer>(begin)) + prev = static_cast<previous_pointer>( + static_cast<node_pointer>(prev->next_)->group_prev_); + + if (end) split_group(end); + } + else { + node_pointer group1 = split_group(begin); + + if (end) { + node_pointer group2 = split_group(end); + + if(begin == group2) { + link_pointer end1 = group1->group_prev_; + link_pointer end2 = end->group_prev_; + group1->group_prev_ = end2; + end->group_prev_ = end1; + } + } + } + + prev->next_ = static_cast<link_pointer>(end); + + return prev; + } + + // Break a ciruclar list into two, with split as the beginning + // of the second group (if split is at the beginning then don't + // split). + static node_pointer split_group(node_pointer split) + { + // Find first node in group. + node_pointer first = split; + while (static_cast<node_pointer>(first->group_prev_)->next_ == + static_cast<link_pointer>(first)) + first = static_cast<node_pointer>(first->group_prev_); + + if(first == split) return split; + + link_pointer last = first->group_prev_; + first->group_prev_ = split->group_prev_; + split->group_prev_ = last; + + return first; + } + + //////////////////////////////////////////////////////////////////////// + // fill_buckets + + template <class NodeCreator> + static void fill_buckets(iterator n, table& dst, + NodeCreator& creator) + { + previous_pointer prev = dst.get_previous_start(); + + while (n.node_) { + std::size_t key_hash = n.node_->hash_; + iterator group_end( + static_cast<node_pointer>( + static_cast<node_pointer>(n.node_->group_prev_)->next_ + )); + + node_pointer first_node = creator.create(*n); + node_pointer end = first_node; + first_node->hash_ = key_hash; + prev->next_ = static_cast<link_pointer>(first_node); + ++dst.size_; + + for (++n; n != group_end; ++n) + { + end = creator.create(*n); + end->hash_ = key_hash; + add_after_node(end, first_node); + ++dst.size_; + } + + prev = place_in_bucket(dst, prev, end); + } + } + + // strong otherwise exception safety + void rehash_impl(std::size_t num_buckets) + { + BOOST_ASSERT(this->buckets_); + + this->create_buckets(num_buckets); + previous_pointer prev = this->get_previous_start(); + while (prev->next_) + prev = place_in_bucket(*this, prev, + static_cast<node_pointer>( + static_cast<node_pointer>(prev->next_)->group_prev_)); + } + + // Iterate through the nodes placing them in the correct buckets. + // pre: prev->next_ is not null. + static previous_pointer place_in_bucket(table& dst, + previous_pointer prev, node_pointer end) + { + bucket_pointer b = dst.get_bucket(policy::to_bucket( + dst.bucket_count_, end->hash_)); + + if (!b->next_) { + b->next_ = static_cast<node_pointer>(prev); + return static_cast<previous_pointer>(end); + } + else { + link_pointer next = end->next_; + end->next_ = b->next_->next_; + b->next_->next_ = prev->next_; + prev->next_ = next; + return prev; + } + } + }; +}}} #endif diff --git a/3rdParty/Boost/src/boost/unordered/detail/extract_key.hpp b/3rdParty/Boost/src/boost/unordered/detail/extract_key.hpp index bedb175..56a8532 100644 --- a/3rdParty/Boost/src/boost/unordered/detail/extract_key.hpp +++ b/3rdParty/Boost/src/boost/unordered/detail/extract_key.hpp @@ -1,17 +1,16 @@ -// Copyright (C) 2005-2009 Daniel James +// Copyright (C) 2005-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) #ifndef BOOST_UNORDERED_DETAIL_EXTRACT_KEY_HPP_INCLUDED #define BOOST_UNORDERED_DETAIL_EXTRACT_KEY_HPP_INCLUDED -#include <boost/config.hpp> -#include <boost/type_traits/remove_const.hpp> -#include <boost/unordered/detail/fwd.hpp> +#include <boost/unordered/detail/table.hpp> namespace boost { -namespace unordered_detail { +namespace unordered { +namespace detail { // key extractors // @@ -28,6 +27,19 @@ namespace unordered_detail { template <class T> no_key(T const&) {} }; + template <typename Key, typename T> + struct is_key { + template <typename T2> + static choice1::type test(T2 const&); + static choice2::type test(Key const&); + + enum { value = sizeof(test(boost::unordered::detail::make<T>())) == + sizeof(choice2::type) }; + + typedef typename boost::detail::if_true<value>:: + BOOST_NESTED_TEMPLATE then<Key const&, no_key>::type type; + }; + template <class ValueType> struct set_extractor { @@ -44,13 +56,12 @@ namespace unordered_detail { return no_key(); } -#if defined(BOOST_UNORDERED_STD_FORWARD) +#if !defined(BOOST_NO_VARIADIC_TEMPLATES) template <class... Args> static no_key extract(Args const&...) { return no_key(); } - #else template <class Arg> static no_key extract(Arg const&) @@ -58,8 +69,8 @@ namespace unordered_detail { return no_key(); } - template <class Arg> - static no_key extract(Arg const&, Arg const&) + template <class Arg1, class Arg2> + static no_key extract(Arg1 const&, Arg2 const&) { return no_key(); } @@ -75,7 +86,7 @@ namespace unordered_detail { struct map_extractor { typedef ValueType value_type; - typedef BOOST_DEDUCED_TYPENAME boost::remove_const<Key>::type key_type; + typedef typename boost::remove_const<Key>::type key_type; static key_type const& extract(value_type const& v) { @@ -100,7 +111,7 @@ namespace unordered_detail { return v.first; } -#if defined(BOOST_UNORDERED_STD_FORWARD) +#if !defined(BOOST_NO_VARIADIC_TEMPLATES) template <class Arg1, class... Args> static key_type const& extract(key_type const& k, Arg1 const&, Args const&...) @@ -114,6 +125,7 @@ namespace unordered_detail { return no_key(); } #else + template <class Arg1> static key_type const& extract(key_type const& k, Arg1 const&) { @@ -138,11 +150,57 @@ namespace unordered_detail { } #endif +#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&, BOOST_FWD_REF(T2)) \ + { \ + return no_key(); \ + } \ + \ + template <typename T, typename T2> \ + static typename is_key<key_type, T>::type \ + extract(boost::unordered::piecewise_construct_t, \ + namespace_::tuple<T> const& k, BOOST_FWD_REF(T2)) \ + { \ + return typename is_key<key_type, T>::type( \ + namespace_::get<0>(k)); \ + } + +#else + +#define BOOST_UNORDERED_KEY_FROM_TUPLE(namespace_) \ + static no_key extract(boost::unordered::piecewise_construct_t, \ + namespace_::tuple<> const&) \ + { \ + return no_key(); \ + } \ + \ + template <typename T> \ + static typename is_key<key_type, T>::type \ + extract(boost::unordered::piecewise_construct_t, \ + namespace_::tuple<T> const& k) \ + { \ + return typename is_key<key_type, T>::type( \ + namespace_::get<0>(k)); \ + } + +#endif + +BOOST_UNORDERED_KEY_FROM_TUPLE(boost) + +#if !defined(BOOST_NO_CXX11_HDR_TUPLE) +BOOST_UNORDERED_KEY_FROM_TUPLE(std) +#endif + + static bool compare_mapped(value_type const& x, value_type const& y) { return x.second == y.second; } }; -}} +}}} #endif diff --git a/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp b/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp index 471d1d2..ee8966b 100644 --- a/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp +++ b/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp @@ -1,932 +1,23 @@ -// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. -// Copyright (C) 2005-2009 Daniel James +// Copyright (C) 2008-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) -// This contains the basic data structure, apart from the actual values. There's -// no construction or deconstruction here. So this only depends on the pointer -// type. +#ifndef BOOST_UNORDERED_FWD_HPP_INCLUDED +#define BOOST_UNORDERED_FWD_HPP_INCLUDED -#ifndef BOOST_UNORDERED_DETAIL_FWD_HPP_INCLUDED -#define BOOST_UNORDERED_DETAIL_FWD_HPP_INCLUDED - -#include <boost/config.hpp> -#include <boost/iterator.hpp> -#include <boost/compressed_pair.hpp> -#include <boost/type_traits/aligned_storage.hpp> -#include <boost/type_traits/alignment_of.hpp> -#include <boost/unordered/detail/allocator_helpers.hpp> -#include <algorithm> - -// This header defines most of the classes used to implement the unordered -// containers. It doesn't include the insert methods as they require a lot -// of preprocessor metaprogramming - they are in unique.hpp and equivalent.hpp. - -// Template parameters: -// -// H = Hash Function -// P = Predicate -// A = Value Allocator -// G = Bucket group policy, 'grouped' or 'ungrouped' -// E = Key Extractor - -#if !defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_NO_VARIADIC_TEMPLATES) -# if defined(__SGI_STL_PORT) || defined(_STLPORT_VERSION) - // STLport doesn't have std::forward. -# else -# define BOOST_UNORDERED_STD_FORWARD -# endif -#endif - -#if !defined(BOOST_UNORDERED_EMPLACE_LIMIT) -#define BOOST_UNORDERED_EMPLACE_LIMIT 10 -#endif - -#if !defined(BOOST_UNORDERED_STD_FORWARD) - -#include <boost/preprocessor/repetition/enum_params.hpp> -#include <boost/preprocessor/repetition/enum_binary_params.hpp> -#include <boost/preprocessor/repetition/repeat_from_to.hpp> - -#define BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \ - BOOST_PP_ENUM_PARAMS_Z(z, num_params, class Arg) -#define BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \ - BOOST_PP_ENUM_BINARY_PARAMS_Z(z, num_params, Arg, const& arg) -#define BOOST_UNORDERED_CALL_PARAMS(z, num_params) \ - BOOST_PP_ENUM_PARAMS_Z(z, num_params, arg) - -#endif - -namespace boost { namespace unordered_detail { - - static const float minimum_max_load_factor = 1e-3f; - static const std::size_t default_bucket_count = 11; - struct move_tag {}; - - template <class T> class hash_unique_table; - template <class T> class hash_equivalent_table; - template <class Alloc, class Grouped> - class hash_node_constructor; - template <class ValueType> - struct set_extractor; - template <class Key, class ValueType> - struct map_extractor; - struct no_key; - - // 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) +#if defined(_MSC_VER) && (_MSC_VER >= 1020) +# pragma once #endif - //////////////////////////////////////////////////////////////////////////// - // - // This section implements buckets and nodes. Here's a rough - // inheritance diagram, to show how they pull together. - // - // For unordered_set/unordered_map: - // - // hash_bucket<A> - // | - // ungrouped_node_base<A> value_base<A::value_type> - // | | - // +--------------+-------------+ - // | - // hash_node<A, ungrouped> - // - // For unordered_multiset/unordered_multimap: - // - // hash_bucket<A> - // | - // grouped_node_base<A> value_base<A::value_type> - // | | - // +--------------+-------------+ - // | - // hash_node<A, grouped> - - // hash_bucket - // - // hash_bucket is used for both the buckets and as a base class for - // nodes. By using 'bucket_ptr' for 'node_ptr', 'next_' can point - // to either a bucket or a node. This is used later to implement a - // sentinel at the end of the bucket array. - - template <class A> - class hash_bucket - { - hash_bucket& operator=(hash_bucket const&); - public: - typedef hash_bucket<A> bucket; - typedef BOOST_DEDUCED_TYPENAME - boost::unordered_detail::rebind_wrap<A, bucket>::type - bucket_allocator; - typedef BOOST_DEDUCED_TYPENAME bucket_allocator::pointer bucket_ptr; - typedef bucket_ptr node_ptr; - - node_ptr next_; - - hash_bucket() : next_() {} - }; - - // In containers with equivalent keys (unordered_multimap and - // unordered_multiset) equivalent nodes are grouped together, in - // containers with unique keys (unordered_map and unordered_set) - // individual nodes are treated as groups of one. The following two - // classes implement the data structure. - - // This is used for containers with unique keys. There are no groups - // so it doesn't add any extra members, and just treats individual - // nodes as groups of one. - - template <class A> - struct ungrouped_node_base : hash_bucket<A> { - typedef hash_bucket<A> bucket; - typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr; - typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr; - - ungrouped_node_base() : bucket() {} - static inline node_ptr& next_group(node_ptr ptr); - static inline std::size_t group_count(node_ptr ptr); - static inline void add_to_bucket(node_ptr n, bucket& b); - static inline void add_after_node(node_ptr n, node_ptr position); - static void unlink_node(bucket& b, node_ptr n); - static void unlink_nodes(bucket& b, node_ptr begin, node_ptr end); - static void unlink_nodes(bucket& b, node_ptr end); - }; - - // This is used for containers with equivalent keys. It implements a - // circular list running in the opposite direction to the linked - // list through the nodes. - - template <class A> - struct grouped_node_base : hash_bucket<A> - { - typedef hash_bucket<A> bucket; - typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr; - typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr; - - node_ptr group_prev_; - - grouped_node_base() : bucket(), group_prev_() {} - static inline node_ptr& next_group(node_ptr ptr); - static inline node_ptr first_in_group(node_ptr n); - static inline std::size_t group_count(node_ptr ptr); - static inline void add_to_bucket(node_ptr n, bucket& b); - static inline void add_after_node(node_ptr n, node_ptr position); - static void unlink_node(bucket& b, node_ptr n); - static void unlink_nodes(bucket& b, node_ptr begin, node_ptr end); - static void unlink_nodes(bucket& b, node_ptr end); - - private: - static inline node_ptr split_group(node_ptr split); - static inline grouped_node_base& get(node_ptr ptr) { - return static_cast<grouped_node_base&>(*ptr); - } - }; - - // These two classes implement an easy way to pass around the node - // group policy classes without the messy template parameters. - // Whenever you see the template parameter 'G' it's one of these. - - struct ungrouped - { - template <class A> - struct base { - typedef ungrouped_node_base<A> type; - }; - }; - - struct grouped - { - template <class A> - struct base { - typedef grouped_node_base<A> type; - }; - }; - - // The space used to store values in a node. - - template <class ValueType> - struct value_base - { - typedef ValueType value_type; - BOOST_DEDUCED_TYPENAME boost::aligned_storage< - sizeof(value_type), - ::boost::alignment_of<value_type>::value>::type data_; - - void* address() { - return this; - } - value_type& value() { - return *(ValueType*) this; - } - value_type* value_ptr() { - return (ValueType*) this; - } - private: - value_base& operator=(value_base const&); - }; - - // Node - - template <class A, class G> - class hash_node : - public G::BOOST_NESTED_TEMPLATE base<A>::type, - public value_base<BOOST_DEDUCED_TYPENAME A::value_type> - { - public: - typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; - typedef BOOST_DEDUCED_TYPENAME hash_bucket<A>::node_ptr node_ptr; - - static value_type& get_value(node_ptr p) { - return static_cast<hash_node&>(*p).value(); - } - static value_type* get_value_ptr(node_ptr p) { - return static_cast<hash_node&>(*p).value_ptr(); - } - private: - hash_node& operator=(hash_node const&); - }; - - //////////////////////////////////////////////////////////////////////////// - // - // Iterator Base - // - // This is the iterator used internally, the external iterators are - // provided by lightweight wrappers (hash_iterator and - // hast_const_iterator) which provide the full iterator interface. - - template <class A, class G> - class hash_iterator_base - { - public: - typedef A value_allocator; - typedef hash_bucket<A> bucket; - typedef hash_node<A, G> node; - typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; - typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr; - typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr; - - bucket_ptr bucket_; - node_ptr node_; - - hash_iterator_base() : bucket_(), node_() {} - explicit hash_iterator_base(bucket_ptr b) - : bucket_(b), - node_(b ? b->next_ : node_ptr()) {} - hash_iterator_base(bucket_ptr b, node_ptr n) - : bucket_(b), - node_(n) {} - - bool operator==(hash_iterator_base const& x) const { - return node_ == x.node_; } - bool operator!=(hash_iterator_base const& x) const { - return node_ != x.node_; } - value_type& operator*() const { - return node::get_value(node_); - } - - void increment_bucket(node_ptr n) { - while(!n) { - ++bucket_; - n = bucket_->next_; - } - node_ = bucket_ == n ? node_ptr() : n; - } - - void increment() { - increment_bucket(node_->next_); - } - }; - - //////////////////////////////////////////////////////////////////////////// - // - // Now the main data structure: - // - // hash_buckets<A, G> hash_buffered_functions<H, P> - // | | - // +-------------+--------------+ - // | - // hash_table<T> - // - // T is a class which contains typedefs for all the types we need. - - // hash_buckets - // - // This is responsible for allocating and deallocating buckets and nodes. - // - // Notes: - // 1. For the sake exception safety the consturctors don't allocate - // anything. - // 2. It's the callers responsibility to allocate the buckets before calling - // any of the methods (other than getters and setters). - - template <class A, class G> - class hash_buckets - { - hash_buckets(hash_buckets const&); - hash_buckets& operator=(hash_buckets const&); - public: - // Types - - typedef A value_allocator; - typedef hash_bucket<A> bucket; - typedef hash_iterator_base<A, G> iterator_base; - typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; - typedef BOOST_DEDUCED_TYPENAME iterator_base::node node; - - typedef BOOST_DEDUCED_TYPENAME bucket::bucket_allocator - bucket_allocator; - typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr; - typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr; - - typedef BOOST_DEDUCED_TYPENAME rebind_wrap<value_allocator, node>::type - node_allocator; - typedef BOOST_DEDUCED_TYPENAME node_allocator::pointer real_node_ptr; - - // Members - - bucket_ptr buckets_; - std::size_t bucket_count_; - boost::compressed_pair<bucket_allocator, node_allocator> allocators_; - - // Data access - - bucket_allocator const& bucket_alloc() const { - return allocators_.first(); } - node_allocator const& node_alloc() const { - return allocators_.second(); } - bucket_allocator& bucket_alloc() { - return allocators_.first(); } - node_allocator& node_alloc() { - return allocators_.second(); } - std::size_t max_bucket_count() const; - - // Constructors - - hash_buckets(node_allocator const& a, std::size_t n); - void create_buckets(); - ~hash_buckets(); - - // no throw - void swap(hash_buckets& other); - void move(hash_buckets& other); - - // For the remaining functions, buckets_ must not be null. - - bucket_ptr get_bucket(std::size_t n) const; - bucket_ptr bucket_ptr_from_hash(std::size_t hashed) const; - std::size_t bucket_size(std::size_t index) const; - node_ptr bucket_begin(std::size_t n) const; - - // Alloc/Dealloc - - void delete_node(node_ptr); - - // - void delete_buckets(); - void clear_bucket(bucket_ptr); - std::size_t delete_nodes(node_ptr begin, node_ptr end); - std::size_t delete_to_bucket_end(node_ptr begin); - }; - - // Assigning and swapping the equality and hash function objects - // needs strong exception safety. To implement that normally we'd - // require one of them to be known to not throw and the other to - // guarantee strong exception safety. Unfortunately they both only - // have basic exception safety. So to acheive strong exception - // safety we have storage space for two copies, and assign the new - // copies to the unused space. Then switch to using that to use - // them. This is implemented in 'set_hash_functions' which - // atomically assigns the new function objects in a strongly - // exception safe manner. - - template <class H, class P> class set_hash_functions; - - template <class H, class P> - class hash_buffered_functions - { - friend class set_hash_functions<H, P>; - hash_buffered_functions& operator=(hash_buffered_functions const&); - - typedef boost::compressed_pair<H, P> function_pair; - typedef BOOST_DEDUCED_TYPENAME boost::aligned_storage< - sizeof(function_pair), - ::boost::alignment_of<function_pair>::value>::type aligned_function; - - bool current_; // The currently active functions. - aligned_function funcs_[2]; - - function_pair const& current() const { - return *static_cast<function_pair const*>( - static_cast<void const*>(&funcs_[current_])); - } - - void construct(bool which, H const& hf, P const& eq) - { - new((void*) &funcs_[which]) function_pair(hf, eq); - } - - void construct(bool which, function_pair const& f) - { - new((void*) &funcs_[which]) function_pair(f); - } - - void destroy(bool which) - { - boost::unordered_detail::destroy((function_pair*)(&funcs_[which])); - } - - public: - - hash_buffered_functions(H const& hf, P const& eq) - : current_(false) - { - construct(current_, hf, eq); - } - - hash_buffered_functions(hash_buffered_functions const& bf) - : current_(false) - { - construct(current_, bf.current()); - } - - ~hash_buffered_functions() { - destroy(current_); - } - - H const& hash_function() const { - return current().first(); - } - - P const& key_eq() const { - return current().second(); - } - }; - - template <class H, class P> - class set_hash_functions - { - set_hash_functions(set_hash_functions const&); - set_hash_functions& operator=(set_hash_functions const&); - - typedef hash_buffered_functions<H, P> buffered_functions; - buffered_functions& buffered_functions_; - bool tmp_functions_; - - public: - - set_hash_functions(buffered_functions& f, H const& h, P const& p) - : buffered_functions_(f), - tmp_functions_(!f.current_) - { - f.construct(tmp_functions_, h, p); - } - - set_hash_functions(buffered_functions& f, - buffered_functions const& other) - : buffered_functions_(f), - tmp_functions_(!f.current_) - { - f.construct(tmp_functions_, other.current()); - } - - ~set_hash_functions() - { - buffered_functions_.destroy(tmp_functions_); - } - - void commit() - { - buffered_functions_.current_ = tmp_functions_; - tmp_functions_ = !tmp_functions_; - } - }; - - // This implements almost all of the required functionality, apart - // from some things that are specific to containers with unique and - // equivalent keys which is implemented in hash_unique_table and - // hash_equivalent_table. See unique.hpp and equivalent.hpp for - // their declaration and implementation. - - template <class T> - class hash_table : public T::buckets, public T::buffered_functions - { - hash_table(hash_table const&); - public: - typedef BOOST_DEDUCED_TYPENAME T::hasher hasher; - typedef BOOST_DEDUCED_TYPENAME T::key_equal key_equal; - typedef BOOST_DEDUCED_TYPENAME T::value_allocator value_allocator; - typedef BOOST_DEDUCED_TYPENAME T::key_type key_type; - typedef BOOST_DEDUCED_TYPENAME T::value_type value_type; - typedef BOOST_DEDUCED_TYPENAME T::buffered_functions base; - typedef BOOST_DEDUCED_TYPENAME T::buckets buckets; - typedef BOOST_DEDUCED_TYPENAME T::extractor extractor; - typedef BOOST_DEDUCED_TYPENAME T::node_constructor node_constructor; - - typedef BOOST_DEDUCED_TYPENAME T::node node; - typedef BOOST_DEDUCED_TYPENAME T::bucket bucket; - typedef BOOST_DEDUCED_TYPENAME T::node_ptr node_ptr; - typedef BOOST_DEDUCED_TYPENAME T::bucket_ptr bucket_ptr; - typedef BOOST_DEDUCED_TYPENAME T::iterator_base iterator_base; - typedef BOOST_DEDUCED_TYPENAME T::node_allocator node_allocator; - typedef BOOST_DEDUCED_TYPENAME T::iterator_pair iterator_pair; - - // Members - - std::size_t size_; - float mlf_; - // Cached data - invalid if !this->buckets_ - bucket_ptr cached_begin_bucket_; - std::size_t max_load_; - - // Helper methods - - key_type const& get_key(value_type const& v) const { - return extractor::extract(v); - } - key_type const& get_key_from_ptr(node_ptr n) const { - return extractor::extract(node::get_value(n)); - } - bool equal(key_type const& k, value_type const& v) const; - template <class Key, class Pred> - node_ptr find_iterator(bucket_ptr bucket, Key const& k, - Pred const&) const; - node_ptr find_iterator(bucket_ptr bucket, key_type const& k) const; - node_ptr find_iterator(key_type const& k) const; - node_ptr* find_for_erase(bucket_ptr bucket, key_type const& k) const; - - // Load methods - - std::size_t max_size() const; - std::size_t bucket_index(key_type const& k) const; - void max_load_factor(float z); - std::size_t min_buckets_for_size(std::size_t n) const; - std::size_t calculate_max_load(); - - // Constructors - - hash_table(std::size_t n, hasher const& hf, key_equal const& eq, - node_allocator const& a); - hash_table(hash_table const& x, node_allocator const& a); - hash_table(hash_table& x, move_tag m); - hash_table(hash_table& x, node_allocator const& a, move_tag m); - ~hash_table() {} - hash_table& operator=(hash_table const&); - - // Iterators - - iterator_base begin() const { - return this->size_ ? - iterator_base(this->cached_begin_bucket_) : - iterator_base(); - } - iterator_base end() const { - return iterator_base(); - } - - // Swap & Move - - void swap(hash_table& x); - void fast_swap(hash_table& other); - void slow_swap(hash_table& other); - void partial_swap(hash_table& other); - void move(hash_table& x); - - // Reserve and rehash - - void create_for_insert(std::size_t n); - bool reserve_for_insert(std::size_t n); - void rehash(std::size_t n); - void rehash_impl(std::size_t n); - - // Move/copy buckets - - void move_buckets_to(buckets& dst); - void copy_buckets_to(buckets& dst) const; - - // Misc. key methods - - std::size_t count(key_type const& k) const; - iterator_base find(key_type const& k) const; - template <class Key, class Hash, class Pred> - iterator_base find(Key const& k, Hash const& h, Pred const& eq) const; - value_type& at(key_type const& k) const; - iterator_pair equal_range(key_type const& k) const; - - // Erase - // - // no throw - - void clear(); - std::size_t erase_key(key_type const& k); - iterator_base erase_return_iterator(iterator_base r); - void erase(iterator_base r); - std::size_t erase_group(node_ptr* it, bucket_ptr bucket); - iterator_base erase_range(iterator_base r1, iterator_base r2); - - // recompute_begin_bucket - - void init_buckets(); - - // After an erase cached_begin_bucket_ might be left pointing to - // an empty bucket, so this is called to update it - // - // no throw - - void recompute_begin_bucket(bucket_ptr b); - - // This is called when a range has been erased - // - // no throw - - void recompute_begin_bucket(bucket_ptr b1, bucket_ptr b2); - - // no throw - float load_factor() const; - - iterator_base emplace_empty_impl_with_node( - node_constructor&, std::size_t); - }; - - /////////////////////////////////////////////////////////////////// - // - // Iterators - - // iterator_access is used to access the internal iterator without - // making it publicly available. - - class iterator_access - { - public: - template <class Iterator> - static BOOST_DEDUCED_TYPENAME Iterator::base const& - get(Iterator const& it) - { - return it.base_; - } - }; - - template <class A, class G> class hash_iterator; - template <class A, class G> class hash_const_iterator; - template <class A, class G> class hash_local_iterator; - template <class A, class G> class hash_const_local_iterator; - - // Local Iterators - // - // all no throw - - template <class A, class G> - class hash_local_iterator - : public boost::iterator < - std::forward_iterator_tag, - BOOST_DEDUCED_TYPENAME A::value_type, - std::ptrdiff_t, - BOOST_DEDUCED_TYPENAME A::pointer, - BOOST_DEDUCED_TYPENAME A::reference> - { - public: - typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; - - private: - typedef hash_buckets<A, G> buckets; - typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr; - typedef BOOST_DEDUCED_TYPENAME buckets::node node; - typedef hash_const_local_iterator<A, G> const_local_iterator; - - friend class hash_const_local_iterator<A, G>; - node_ptr ptr_; - - public: - hash_local_iterator() : ptr_() {} - explicit hash_local_iterator(node_ptr x) : ptr_(x) {} - BOOST_DEDUCED_TYPENAME A::reference operator*() const { - return node::get_value(ptr_); - } - value_type* operator->() const { - return node::get_value_ptr(ptr_); - } - hash_local_iterator& operator++() { - ptr_ = ptr_->next_; return *this; - } - hash_local_iterator operator++(int) { - hash_local_iterator tmp(ptr_); ptr_ = ptr_->next_; return tmp; } - bool operator==(hash_local_iterator x) const { - return ptr_ == x.ptr_; - } - bool operator==(const_local_iterator x) const { - return ptr_ == x.ptr_; - } - bool operator!=(hash_local_iterator x) const { - return ptr_ != x.ptr_; - } - bool operator!=(const_local_iterator x) const { - return ptr_ != x.ptr_; - } - }; - - template <class A, class G> - class hash_const_local_iterator - : public boost::iterator < - std::forward_iterator_tag, - BOOST_DEDUCED_TYPENAME A::value_type, - std::ptrdiff_t, - BOOST_DEDUCED_TYPENAME A::const_pointer, - BOOST_DEDUCED_TYPENAME A::const_reference > - { - public: - typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; - - private: - typedef hash_buckets<A, G> buckets; - typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr ptr; - typedef BOOST_DEDUCED_TYPENAME buckets::node node; - typedef hash_local_iterator<A, G> local_iterator; - friend class hash_local_iterator<A, G>; - ptr ptr_; - - public: - hash_const_local_iterator() : ptr_() {} - explicit hash_const_local_iterator(ptr x) : ptr_(x) {} - hash_const_local_iterator(local_iterator x) : ptr_(x.ptr_) {} - BOOST_DEDUCED_TYPENAME A::const_reference - operator*() const { - return node::get_value(ptr_); - } - value_type const* operator->() const { - return node::get_value_ptr(ptr_); - } - hash_const_local_iterator& operator++() { - ptr_ = ptr_->next_; return *this; - } - hash_const_local_iterator operator++(int) { - hash_const_local_iterator tmp(ptr_); ptr_ = ptr_->next_; return tmp; - } - bool operator==(local_iterator x) const { - return ptr_ == x.ptr_; - } - bool operator==(hash_const_local_iterator x) const { - return ptr_ == x.ptr_; - } - bool operator!=(local_iterator x) const { - return ptr_ != x.ptr_; - } - bool operator!=(hash_const_local_iterator x) const { - return ptr_ != x.ptr_; - } - }; - - // Iterators - // - // all no throw - - - template <class A, class G> - class hash_iterator - : public boost::iterator < - std::forward_iterator_tag, - BOOST_DEDUCED_TYPENAME A::value_type, - std::ptrdiff_t, - BOOST_DEDUCED_TYPENAME A::pointer, - BOOST_DEDUCED_TYPENAME A::reference > - { - public: - typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; - - private: - typedef hash_buckets<A, G> buckets; - typedef BOOST_DEDUCED_TYPENAME buckets::node node; - typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base base; - typedef hash_const_iterator<A, G> const_iterator; - friend class hash_const_iterator<A, G>; - base base_; - - public: - - hash_iterator() : base_() {} - explicit hash_iterator(base const& x) : base_(x) {} - BOOST_DEDUCED_TYPENAME A::reference operator*() const { - return *base_; - } - value_type* operator->() const { - return &*base_; - } - hash_iterator& operator++() { - base_.increment(); return *this; - } - hash_iterator operator++(int) { - hash_iterator tmp(base_); base_.increment(); return tmp; - } - bool operator==(hash_iterator const& x) const { - return base_ == x.base_; - } - bool operator==(const_iterator const& x) const { - return base_ == x.base_; - } - bool operator!=(hash_iterator const& x) const { - return base_ != x.base_; - } - bool operator!=(const_iterator const& x) const { - return base_ != x.base_; - } - }; - - template <class A, class G> - class hash_const_iterator - : public boost::iterator < - std::forward_iterator_tag, - BOOST_DEDUCED_TYPENAME A::value_type, - std::ptrdiff_t, - BOOST_DEDUCED_TYPENAME A::const_pointer, - BOOST_DEDUCED_TYPENAME A::const_reference > - { - public: - typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; - - private: - typedef hash_buckets<A, G> buckets; - typedef BOOST_DEDUCED_TYPENAME buckets::node node; - typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base base; - typedef hash_iterator<A, G> iterator; - friend class hash_iterator<A, G>; - friend class iterator_access; - base base_; - - public: - - hash_const_iterator() : base_() {} - explicit hash_const_iterator(base const& x) : base_(x) {} - hash_const_iterator(iterator const& x) : base_(x.base_) {} - BOOST_DEDUCED_TYPENAME A::const_reference operator*() const { - return *base_; - } - value_type const* operator->() const { - return &*base_; - } - hash_const_iterator& operator++() { - base_.increment(); return *this; - } - hash_const_iterator operator++(int) { - hash_const_iterator tmp(base_); base_.increment(); return tmp; - } - bool operator==(iterator const& x) const { - return base_ == x.base_; - } - bool operator==(hash_const_iterator const& x) const { - return base_ == x.base_; - } - bool operator!=(iterator const& x) const { - return base_ != x.base_; - } - bool operator!=(hash_const_iterator const& x) const { - return base_ != x.base_; - } - }; - - //////////////////////////////////////////////////////////////////////////// - // - // types - // - // This is used to convieniently pass around a container's typedefs - // without having 7 template parameters. - - template <class K, class V, class H, class P, class A, class E, class G> - struct types - { - public: - typedef K key_type; - typedef V value_type; - typedef H hasher; - typedef P key_equal; - typedef A value_allocator; - typedef E extractor; - typedef G group_type; - - typedef hash_node_constructor<value_allocator, group_type> - node_constructor; - typedef hash_buckets<value_allocator, group_type> buckets; - typedef hash_buffered_functions<hasher, key_equal> buffered_functions; - - typedef BOOST_DEDUCED_TYPENAME buckets::node node; - typedef BOOST_DEDUCED_TYPENAME buckets::bucket bucket; - typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr; - typedef BOOST_DEDUCED_TYPENAME buckets::bucket_ptr bucket_ptr; - typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base iterator_base; - typedef BOOST_DEDUCED_TYPENAME buckets::node_allocator node_allocator; - typedef std::pair<iterator_base, iterator_base> iterator_pair; - }; -}} +namespace boost +{ +namespace unordered +{ + struct piecewise_construct_t {}; + const piecewise_construct_t piecewise_construct = piecewise_construct_t(); +} +} #endif diff --git a/3rdParty/Boost/src/boost/unordered/detail/move.hpp b/3rdParty/Boost/src/boost/unordered/detail/move.hpp deleted file mode 100644 index 16fd921..0000000 --- a/3rdParty/Boost/src/boost/unordered/detail/move.hpp +++ /dev/null @@ -1,243 +0,0 @@ -/* - Copyright 2005-2007 Adobe Systems Incorporated - - Use, modification and distribution are subject to the Boost Software License, - Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at - http://www.boost.org/LICENSE_1_0.txt). -*/ - -/*************************************************************************************************/ - -#ifndef BOOST_UNORDERED_DETAIL_MOVE_HEADER -#define BOOST_UNORDERED_DETAIL_MOVE_HEADER - -#include <boost/config.hpp> -#include <boost/mpl/bool.hpp> -#include <boost/mpl/and.hpp> -#include <boost/mpl/or.hpp> -#include <boost/mpl/not.hpp> -#include <boost/type_traits/is_convertible.hpp> -#include <boost/type_traits/is_same.hpp> -#include <boost/type_traits/is_class.hpp> -#include <boost/utility/enable_if.hpp> -#include <boost/detail/workaround.hpp> - -/*************************************************************************************************/ - -#if defined(BOOST_NO_SFINAE) -# define BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN -#elif defined(__GNUC__) && \ - (__GNUC__ < 3 || __GNUC__ == 3 && __GNUC_MINOR__ <= 3) -# define BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN -#elif BOOST_WORKAROUND(BOOST_INTEL, < 900) || \ - BOOST_WORKAROUND(__EDG_VERSION__, < 304) || \ - BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x0593)) -# define BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN -#endif - -/*************************************************************************************************/ - -namespace boost { -namespace unordered_detail { - -/*************************************************************************************************/ - -namespace move_detail { - -/*************************************************************************************************/ - -#if !defined(BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN) - -/*************************************************************************************************/ - -template <typename T> -struct class_has_move_assign { - class type { - typedef T& (T::*E)(T t); - typedef char (&no_type)[1]; - typedef char (&yes_type)[2]; - template <E e> struct sfinae { typedef yes_type type; }; - template <class U> - static typename sfinae<&U::operator=>::type test(int); - template <class U> - static no_type test(...); - public: - enum {value = sizeof(test<T>(1)) == sizeof(yes_type)}; - }; - }; - -/*************************************************************************************************/ - -template<typename T> -struct has_move_assign : boost::mpl::and_<boost::is_class<T>, class_has_move_assign<T> > {}; - -/*************************************************************************************************/ - -class test_can_convert_anything { }; - -/*************************************************************************************************/ - -#endif // BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN - -/*************************************************************************************************/ - -/* - REVISIT (sparent@adobe.com): This is a work around for Boost 1.34.1 and VC++ 2008 where - boost::is_convertible<T, T> fails to compile. -*/ - -template <typename T, typename U> -struct is_convertible : boost::mpl::or_< - boost::is_same<T, U>, - boost::is_convertible<T, U> -> { }; - -/*************************************************************************************************/ - -} //namespace move_detail - - -/*************************************************************************************************/ - -/*! -\ingroup move_related -\brief move_from is used for move_ctors. -*/ - -template <typename T> -struct move_from -{ - explicit move_from(T& x) : source(x) { } - T& source; -private: - move_from& operator=(move_from const&); -}; - -/*************************************************************************************************/ - -#if !defined(BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN) - -/*************************************************************************************************/ - -/*! -\ingroup move_related -\brief The is_movable trait can be used to identify movable types. -*/ -template <typename T> -struct is_movable : boost::mpl::and_< - boost::is_convertible<move_from<T>, T>, - move_detail::has_move_assign<T>, - boost::mpl::not_<boost::is_convertible<move_detail::test_can_convert_anything, T> > - > { }; - -/*************************************************************************************************/ - -#else // BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN - -// On compilers which don't have adequate SFINAE support, treat most types as unmovable, -// unless the trait is specialized. - -template <typename T> -struct is_movable : boost::mpl::false_ { }; - -#endif - -/*************************************************************************************************/ - -#if !defined(BOOST_NO_SFINAE) - -/*************************************************************************************************/ - -/*! -\ingroup move_related -\brief copy_sink and move_sink are used to select between overloaded operations according to - whether type T is movable and convertible to type U. -\sa move -*/ - -template <typename T, - typename U = T, - typename R = void*> -struct copy_sink : boost::enable_if< - boost::mpl::and_< - boost::unordered_detail::move_detail::is_convertible<T, U>, - boost::mpl::not_<is_movable<T> > - >, - R - > -{ }; - -/*************************************************************************************************/ - -/*! -\ingroup move_related -\brief move_sink and copy_sink are used to select between overloaded operations according to - whether type T is movable and convertible to type U. - \sa move -*/ - -template <typename T, - typename U = T, - typename R = void*> -struct move_sink : boost::enable_if< - boost::mpl::and_< - boost::unordered_detail::move_detail::is_convertible<T, U>, - is_movable<T> - >, - R - > -{ }; - -/*************************************************************************************************/ - -/*! -\ingroup move_related -\brief This version of move is selected when T is_movable . It in turn calls the move -constructor. This call, with the help of the return value optimization, will cause x to be moved -instead of copied to its destination. See adobe/test/move/main.cpp for examples. - -*/ -template <typename T> -T move(T& x, typename move_sink<T>::type = 0) { return T(move_from<T>(x)); } - -/*************************************************************************************************/ - -/*! -\ingroup move_related -\brief This version of move is selected when T is not movable . The net result will be that -x gets copied. -*/ -template <typename T> -T& move(T& x, typename copy_sink<T>::type = 0) { return x; } - -/*************************************************************************************************/ - -#else // BOOST_NO_SFINAE - -// On compilers without SFINAE, define copy_sink to always use the copy function. - -template <typename T, - typename U = T, - typename R = void*> -struct copy_sink -{ - typedef R type; -}; - -// Always copy the element unless this is overloaded. - -template <typename T> -T& move(T& x) { - return x; -} - -#endif // BOOST_NO_SFINAE - -} // namespace unordered_detail -} // namespace boost - -/*************************************************************************************************/ - -#endif - -/*************************************************************************************************/ diff --git a/3rdParty/Boost/src/boost/unordered/detail/node.hpp b/3rdParty/Boost/src/boost/unordered/detail/node.hpp deleted file mode 100644 index 85a3141..0000000 --- a/3rdParty/Boost/src/boost/unordered/detail/node.hpp +++ /dev/null @@ -1,226 +0,0 @@ - -// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. -// Copyright (C) 2005-2009 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) - -// This contains the basic data structure, apart from the actual values. There's -// no construction or deconstruction here. So this only depends on the pointer -// type. - -#ifndef BOOST_UNORDERED_DETAIL_NODE_HPP_INCLUDED -#define BOOST_UNORDERED_DETAIL_NODE_HPP_INCLUDED - -#include <boost/config.hpp> -#include <boost/assert.hpp> -#include <boost/detail/workaround.hpp> -#include <boost/unordered/detail/fwd.hpp> - -#if BOOST_WORKAROUND(__BORLANDC__, <= 0X0582) -#define BOOST_UNORDERED_BORLAND_BOOL(x) (bool)(x) -#else -#define BOOST_UNORDERED_BORLAND_BOOL(x) x -#endif - -namespace boost { namespace unordered_detail { - - //////////////////////////////////////////////////////////////////////////// - // ungrouped node implementation - - template <class A> - inline BOOST_DEDUCED_TYPENAME ungrouped_node_base<A>::node_ptr& - ungrouped_node_base<A>::next_group(node_ptr ptr) - { - return ptr->next_; - } - - template <class A> - inline std::size_t ungrouped_node_base<A>::group_count(node_ptr) - { - return 1; - } - - template <class A> - inline void ungrouped_node_base<A>::add_to_bucket(node_ptr n, bucket& b) - { - n->next_ = b.next_; - b.next_ = n; - } - - template <class A> - inline void ungrouped_node_base<A>::add_after_node(node_ptr n, - node_ptr position) - { - n->next_ = position->next_; - position->next_ = position; - } - - template <class A> - inline void ungrouped_node_base<A>::unlink_nodes(bucket& b, - node_ptr begin, node_ptr end) - { - node_ptr* pos = &b.next_; - while(*pos != begin) pos = &(*pos)->next_; - *pos = end; - } - - template <class A> - inline void ungrouped_node_base<A>::unlink_nodes(bucket& b, node_ptr end) - { - b.next_ = end; - } - - template <class A> - inline void ungrouped_node_base<A>::unlink_node(bucket& b, node_ptr n) - { - unlink_nodes(b, n, n->next_); - } - - //////////////////////////////////////////////////////////////////////////// - // grouped node implementation - - // If ptr is the first element in a group, return pointer to next group. - // Otherwise returns a pointer to ptr. - template <class A> - inline BOOST_DEDUCED_TYPENAME grouped_node_base<A>::node_ptr& - grouped_node_base<A>::next_group(node_ptr ptr) - { - return get(ptr).group_prev_->next_; - } - - template <class A> - inline BOOST_DEDUCED_TYPENAME grouped_node_base<A>::node_ptr - grouped_node_base<A>::first_in_group(node_ptr ptr) - { - while(next_group(ptr) == ptr) - ptr = get(ptr).group_prev_; - return ptr; - } - - template <class A> - inline std::size_t grouped_node_base<A>::group_count(node_ptr ptr) - { - node_ptr start = ptr; - std::size_t size = 0; - do { - ++size; - ptr = get(ptr).group_prev_; - } while(ptr != start); - return size; - } - - template <class A> - inline void grouped_node_base<A>::add_to_bucket(node_ptr n, bucket& b) - { - n->next_ = b.next_; - get(n).group_prev_ = n; - b.next_ = n; - } - - template <class A> - inline void grouped_node_base<A>::add_after_node(node_ptr n, node_ptr pos) - { - n->next_ = next_group(pos); - get(n).group_prev_ = get(pos).group_prev_; - next_group(pos) = n; - get(pos).group_prev_ = n; - } - - // Break a ciruclar list into two, with split as the beginning - // of the second group (if split is at the beginning then don't - // split). - template <class A> - inline BOOST_DEDUCED_TYPENAME grouped_node_base<A>::node_ptr - grouped_node_base<A>::split_group(node_ptr split) - { - node_ptr first = first_in_group(split); - if(first == split) return split; - - node_ptr last = get(first).group_prev_; - get(first).group_prev_ = get(split).group_prev_; - get(split).group_prev_ = last; - - return first; - } - - template <class A> - void grouped_node_base<A>::unlink_node(bucket& b, node_ptr n) - { - node_ptr next = n->next_; - node_ptr* pos = &next_group(n); - - if(*pos != n) { - // The node is at the beginning of a group. - - // Find the previous node pointer: - pos = &b.next_; - while(*pos != n) pos = &next_group(*pos); - - // Remove from group - if(BOOST_UNORDERED_BORLAND_BOOL(next) && - get(next).group_prev_ == n) - { - get(next).group_prev_ = get(n).group_prev_; - } - } - else if(BOOST_UNORDERED_BORLAND_BOOL(next) && - get(next).group_prev_ == n) - { - // The deleted node is not at the end of the group, so - // change the link from the next node. - get(next).group_prev_ = get(n).group_prev_; - } - else { - // The deleted node is at the end of the group, so the - // first node in the group is pointing to it. - // Find that to change its pointer. - node_ptr x = get(n).group_prev_; - while(get(x).group_prev_ != n) { - x = get(x).group_prev_; - } - get(x).group_prev_ = get(n).group_prev_; - } - *pos = next; - } - - template <class A> - void grouped_node_base<A>::unlink_nodes(bucket& b, - node_ptr begin, node_ptr end) - { - node_ptr* pos = &next_group(begin); - - if(*pos != begin) { - // The node is at the beginning of a group. - - // Find the previous node pointer: - pos = &b.next_; - while(*pos != begin) pos = &next_group(*pos); - - // Remove from group - if(BOOST_UNORDERED_BORLAND_BOOL(end)) split_group(end); - } - else { - node_ptr group1 = split_group(begin); - if(BOOST_UNORDERED_BORLAND_BOOL(end)) { - node_ptr group2 = split_group(end); - - if(begin == group2) { - node_ptr end1 = get(group1).group_prev_; - node_ptr end2 = get(group2).group_prev_; - get(group1).group_prev_ = end2; - get(group2).group_prev_ = end1; - } - } - } - *pos = end; - } - - template <class A> - void grouped_node_base<A>::unlink_nodes(bucket& b, node_ptr end) - { - split_group(end); - b.next_ = end; - } -}} - -#endif diff --git a/3rdParty/Boost/src/boost/unordered/detail/table.hpp b/3rdParty/Boost/src/boost/unordered/detail/table.hpp index d37c015..af376fe 100644 --- a/3rdParty/Boost/src/boost/unordered/detail/table.hpp +++ b/3rdParty/Boost/src/boost/unordered/detail/table.hpp @@ -1,778 +1,907 @@ // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. -// Copyright (C) 2005-2009 Daniel James +// Copyright (C) 2005-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) #ifndef BOOST_UNORDERED_DETAIL_ALL_HPP_INCLUDED #define BOOST_UNORDERED_DETAIL_ALL_HPP_INCLUDED -#include <cstddef> -#include <stdexcept> -#include <algorithm> -#include <boost/config/no_tr1/cmath.hpp> -#include <boost/iterator/iterator_categories.hpp> -#include <boost/throw_exception.hpp> - #include <boost/unordered/detail/buckets.hpp> +#include <boost/unordered/detail/util.hpp> +#include <boost/type_traits/aligned_storage.hpp> +#include <boost/type_traits/alignment_of.hpp> +#include <cmath> + +#if defined(BOOST_MSVC) +#pragma warning(push) +#pragma warning(disable:4127) // conditional expression is constant +#endif -namespace boost { namespace unordered_detail { +namespace boost { namespace unordered { namespace detail { //////////////////////////////////////////////////////////////////////////// - // Helper methods + // convert double to std::size_t - // strong exception safety, no side effects - template <class T> - inline bool hash_table<T>::equal( - key_type const& k, value_type const& v) const + inline std::size_t double_to_size(double f) { - return this->key_eq()(k, get_key(v)); + return f >= static_cast<double>( + (std::numeric_limits<std::size_t>::max)()) ? + (std::numeric_limits<std::size_t>::max)() : + static_cast<std::size_t>(f); } - // strong exception safety, no side effects - template <class T> - template <class Key, class Pred> - inline BOOST_DEDUCED_TYPENAME T::node_ptr - hash_table<T>::find_iterator(bucket_ptr bucket, Key const& k, - Pred const& eq) const + // The space used to store values in a node. + + template <typename ValueType> + struct value_base { - node_ptr it = bucket->next_; - while (BOOST_UNORDERED_BORLAND_BOOL(it) && - !eq(k, get_key(node::get_value(it)))) - { - it = node::next_group(it); + typedef ValueType value_type; + + typename boost::aligned_storage< + sizeof(value_type), + boost::alignment_of<value_type>::value>::type data_; + + void* address() { + return this; } - return it; - } + value_type& value() { + return *(ValueType*) this; + } - // strong exception safety, no side effects - template <class T> - inline BOOST_DEDUCED_TYPENAME T::node_ptr - hash_table<T>::find_iterator( - bucket_ptr bucket, key_type const& k) const - { - node_ptr it = bucket->next_; - while (BOOST_UNORDERED_BORLAND_BOOL(it) && - !equal(k, node::get_value(it))) - { - it = node::next_group(it); + value_type* value_ptr() { + return (ValueType*) this; } - return it; - } + private: - // strong exception safety, no side effects - // pre: this->buckets_ - template <class T> - inline BOOST_DEDUCED_TYPENAME T::node_ptr - hash_table<T>::find_iterator(key_type const& k) const - { - return find_iterator(this->get_bucket(this->bucket_index(k)), k); - } + value_base& operator=(value_base const&); + }; - // strong exception safety, no side effects - template <class T> - inline BOOST_DEDUCED_TYPENAME T::node_ptr* - hash_table<T>::find_for_erase( - bucket_ptr bucket, key_type const& k) const + template <typename NodeAlloc> + struct copy_nodes { - node_ptr* it = &bucket->next_; - while(BOOST_UNORDERED_BORLAND_BOOL(*it) && - !equal(k, node::get_value(*it))) + typedef boost::unordered::detail::allocator_traits<NodeAlloc> + node_allocator_traits; + + node_constructor<NodeAlloc> constructor; + + explicit copy_nodes(NodeAlloc& a) : constructor(a) {} + + typename node_allocator_traits::pointer create( + typename node_allocator_traits::value_type::value_type const& v) { - it = &node::next_group(*it); + constructor.construct_with_value2(v); + return constructor.release(); } + }; - return it; - } + template <typename NodeAlloc> + struct move_nodes + { + typedef boost::unordered::detail::allocator_traits<NodeAlloc> + node_allocator_traits; - //////////////////////////////////////////////////////////////////////////// - // Load methods + node_constructor<NodeAlloc> constructor; - // no throw - template <class T> - std::size_t hash_table<T>::max_size() const - { - using namespace std; + explicit move_nodes(NodeAlloc& a) : constructor(a) {} - // size < mlf_ * count - return double_to_size_t(ceil( - (double) this->mlf_ * this->max_bucket_count())) - 1; - } + typename node_allocator_traits::pointer create( + typename node_allocator_traits::value_type::value_type& v) + { + constructor.construct_with_value2(boost::move(v)); + return constructor.release(); + } + }; - // strong safety - template <class T> - inline std::size_t hash_table<T>::bucket_index( - key_type const& k) const + template <typename Buckets> + struct assign_nodes { - // hash_function can throw: - return this->hash_function()(k) % this->bucket_count_; - } + node_holder<typename Buckets::node_allocator> holder; + explicit assign_nodes(Buckets& b) : holder(b) {} - // no throw - template <class T> - inline std::size_t hash_table<T>::calculate_max_load() + typename Buckets::node_pointer create( + typename Buckets::value_type const& v) + { + return holder.copy_of(v); + } + }; + + template <typename Buckets> + struct move_assign_nodes { - using namespace std; + node_holder<typename Buckets::node_allocator> holder; - // From 6.3.1/13: - // Only resize when size >= mlf_ * count - return double_to_size_t(ceil((double) mlf_ * this->bucket_count_)); - } + explicit move_assign_nodes(Buckets& b) : holder(b) {} - template <class T> - void hash_table<T>::max_load_factor(float z) - { - BOOST_ASSERT(z > 0); - mlf_ = (std::max)(z, minimum_max_load_factor); - this->max_load_ = this->calculate_max_load(); - } + typename Buckets::node_pointer create( + typename Buckets::value_type& v) + { + return holder.move_copy_of(v); + } + }; + + template <typename Types> + struct table : + Types::policy, + boost::unordered::detail::functions< + typename Types::hasher, + typename Types::key_equal> + { + private: + table(table const&); + table& operator=(table const&); + public: + typedef typename Types::node node; + typedef typename Types::bucket bucket; + typedef typename Types::hasher hasher; + typedef typename Types::key_equal key_equal; + typedef typename Types::key_type key_type; + typedef typename Types::extractor extractor; + typedef typename Types::value_type value_type; + typedef typename Types::table table_impl; + typedef typename Types::link_pointer link_pointer; + typedef typename Types::policy policy; + + typedef boost::unordered::detail::functions< + typename Types::hasher, + typename Types::key_equal> functions; + + typedef typename Types::allocator allocator; + typedef typename boost::unordered::detail:: + rebind_wrap<allocator, node>::type node_allocator; + typedef typename boost::unordered::detail:: + rebind_wrap<allocator, bucket>::type bucket_allocator; + typedef boost::unordered::detail::allocator_traits<node_allocator> + node_allocator_traits; + typedef boost::unordered::detail::allocator_traits<bucket_allocator> + bucket_allocator_traits; + typedef typename node_allocator_traits::pointer + node_pointer; + typedef typename node_allocator_traits::const_pointer + const_node_pointer; + typedef typename bucket_allocator_traits::pointer + bucket_pointer; + typedef typename bucket::previous_pointer + previous_pointer; + 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 + + boost::unordered::detail::compressed<bucket_allocator, node_allocator> + allocators_; + std::size_t bucket_count_; + std::size_t size_; + float mlf_; + std::size_t max_load_; + bucket_pointer buckets_; + + //////////////////////////////////////////////////////////////////////// + // Data access + + bucket_allocator const& bucket_alloc() const + { + return allocators_.first(); + } - // no throw - template <class T> - inline std::size_t hash_table<T>::min_buckets_for_size( - std::size_t size) const - { - BOOST_ASSERT(this->mlf_ != 0); + node_allocator const& node_alloc() const + { + return allocators_.second(); + } - using namespace std; + bucket_allocator& bucket_alloc() + { + return allocators_.first(); + } - // From 6.3.1/13: - // size < mlf_ * count - // => count > size / mlf_ - // - // Or from rehash post-condition: - // count > size / mlf_ - return next_prime(double_to_size_t(floor(size / (double) mlf_)) + 1); - } + node_allocator& node_alloc() + { + return allocators_.second(); + } - //////////////////////////////////////////////////////////////////////////// - // recompute_begin_bucket + std::size_t max_bucket_count() const + { + // -1 to account for the start bucket. + return policy::prev_bucket_count( + bucket_allocator_traits::max_size(bucket_alloc()) - 1); + } - // init_buckets + bucket_pointer get_bucket(std::size_t bucket_index) const + { + BOOST_ASSERT(buckets_); + return buckets_ + static_cast<std::ptrdiff_t>(bucket_index); + } - template <class T> - inline void hash_table<T>::init_buckets() - { - if (this->size_) { - this->cached_begin_bucket_ = this->buckets_; - while (!this->cached_begin_bucket_->next_) - ++this->cached_begin_bucket_; - } else { - this->cached_begin_bucket_ = this->get_bucket(this->bucket_count_); - } - this->max_load_ = calculate_max_load(); - } + previous_pointer get_previous_start() const + { + return get_bucket(bucket_count_)->first_from_start(); + } - // After an erase cached_begin_bucket_ might be left pointing to - // an empty bucket, so this is called to update it - // - // no throw + previous_pointer get_previous_start(std::size_t bucket_index) const + { + return get_bucket(bucket_index)->next_; + } - template <class T> - inline void hash_table<T>::recompute_begin_bucket(bucket_ptr b) - { - BOOST_ASSERT(!(b < this->cached_begin_bucket_)); + iterator begin() const + { + return size_ ? iterator(static_cast<node_pointer>( + get_previous_start()->next_)) : iterator(); + } - if(b == this->cached_begin_bucket_) + iterator begin(std::size_t bucket_index) const { - if (this->size_ != 0) { - while (!this->cached_begin_bucket_->next_) - ++this->cached_begin_bucket_; - } else { - this->cached_begin_bucket_ = - this->get_bucket(this->bucket_count_); - } + if (!size_) return iterator(); + previous_pointer prev = get_previous_start(bucket_index); + return prev ? iterator(static_cast<node_pointer>(prev->next_)) : + iterator(); } - } - // This is called when a range has been erased - // - // no throw + float load_factor() const + { + BOOST_ASSERT(bucket_count_ != 0); + return static_cast<float>(size_) + / static_cast<float>(bucket_count_); + } - template <class T> - inline void hash_table<T>::recompute_begin_bucket( - bucket_ptr b1, bucket_ptr b2) - { - BOOST_ASSERT(!(b1 < this->cached_begin_bucket_) && !(b2 < b1)); - BOOST_ASSERT(BOOST_UNORDERED_BORLAND_BOOL(b2->next_)); + std::size_t bucket_size(std::size_t index) const + { + iterator it = begin(index); + if (!it.node_) return 0; + + std::size_t count = 0; + while(it.node_ && policy::to_bucket( + bucket_count_, it.node_->hash_) == index) + { + ++count; + ++it; + } - if(b1 == this->cached_begin_bucket_ && !b1->next_) - this->cached_begin_bucket_ = b2; - } + return count; + } - // no throw - template <class T> - inline float hash_table<T>::load_factor() const - { - BOOST_ASSERT(this->bucket_count_ != 0); - return static_cast<float>(this->size_) - / static_cast<float>(this->bucket_count_); - } + //////////////////////////////////////////////////////////////////////// + // Load methods - //////////////////////////////////////////////////////////////////////////// - // Constructors - - template <class T> - hash_table<T>::hash_table(std::size_t num_buckets, - hasher const& hf, key_equal const& eq, node_allocator const& a) - : buckets(a, next_prime(num_buckets)), - base(hf, eq), - size_(), - mlf_(1.0f), - cached_begin_bucket_(), - max_load_(0) - { - } + std::size_t max_size() const + { + using namespace std; + + // size < mlf_ * count + return boost::unordered::detail::double_to_size(ceil( + static_cast<double>(mlf_) * + static_cast<double>(max_bucket_count()) + )) - 1; + } + + void recalculate_max_load() + { + using namespace std; + + // From 6.3.1/13: + // Only resize when size >= mlf_ * count + max_load_ = buckets_ ? boost::unordered::detail::double_to_size(ceil( + static_cast<double>(mlf_) * + static_cast<double>(bucket_count_) + )) : 0; - // Copy Construct with allocator - - template <class T> - hash_table<T>::hash_table(hash_table const& x, - node_allocator const& a) - : buckets(a, x.min_buckets_for_size(x.size_)), - base(x), - size_(x.size_), - mlf_(x.mlf_), - cached_begin_bucket_(), - max_load_(0) - { - if(x.size_) { - x.copy_buckets_to(*this); - this->init_buckets(); } - } - // Move Construct + void max_load_factor(float z) + { + BOOST_ASSERT(z > 0); + mlf_ = (std::max)(z, minimum_max_load_factor); + recalculate_max_load(); + } - template <class T> - hash_table<T>::hash_table(hash_table& x, move_tag) - : buckets(x.node_alloc(), x.bucket_count_), - base(x), - size_(0), - mlf_(1.0f), - cached_begin_bucket_(), - max_load_(0) - { - this->partial_swap(x); - } + std::size_t min_buckets_for_size(std::size_t size) const + { + BOOST_ASSERT(mlf_ >= minimum_max_load_factor); + + using namespace std; + + // From 6.3.1/13: + // size < mlf_ * count + // => count > size / mlf_ + // + // Or from rehash post-condition: + // count > size / mlf_ + + return policy::new_bucket_count( + boost::unordered::detail::double_to_size(floor( + static_cast<double>(size) / + static_cast<double>(mlf_))) + 1); + } - template <class T> - hash_table<T>::hash_table(hash_table& x, - node_allocator const& a, move_tag) - : buckets(a, x.bucket_count_), - base(x), - size_(0), - mlf_(x.mlf_), - cached_begin_bucket_(), - max_load_(0) - { - if(a == x.node_alloc()) { - this->partial_swap(x); + //////////////////////////////////////////////////////////////////////// + // Constructors + + table(std::size_t num_buckets, + hasher const& hf, + key_equal const& eq, + node_allocator const& a) : + functions(hf, eq), + allocators_(a,a), + bucket_count_(policy::new_bucket_count(num_buckets)), + size_(0), + mlf_(1.0f), + max_load_(0), + buckets_() + {} + + table(table const& x, node_allocator const& a) : + functions(x), + allocators_(a,a), + bucket_count_(x.min_buckets_for_size(x.size_)), + size_(0), + mlf_(x.mlf_), + max_load_(0), + buckets_() + {} + + table(table& x, boost::unordered::detail::move_tag m) : + functions(x), + allocators_(x.allocators_, m), + bucket_count_(x.bucket_count_), + size_(x.size_), + mlf_(x.mlf_), + max_load_(x.max_load_), + buckets_(x.buckets_) + { + x.buckets_ = bucket_pointer(); + x.size_ = 0; + x.max_load_ = 0; } - else if(x.size_) { - x.copy_buckets_to(*this); - this->size_ = x.size_; - this->init_buckets(); + + table(table& x, node_allocator const& a, + boost::unordered::detail::move_tag) : + functions(x), + allocators_(a, a), + bucket_count_(x.bucket_count_), + size_(0), + mlf_(x.mlf_), + max_load_(x.max_load_), + buckets_() + {} + + //////////////////////////////////////////////////////////////////////// + // Initialisation. + + void init(table const& x) + { + if (x.size_) { + create_buckets(bucket_count_); + copy_nodes<node_allocator> copy(node_alloc()); + table_impl::fill_buckets(x.begin(), *this, copy); + } } - } - template <class T> - hash_table<T>& hash_table<T>::operator=( - hash_table const& x) - { - hash_table tmp(x, this->node_alloc()); - this->fast_swap(tmp); - return *this; - } + void move_init(table& x) + { + if(node_alloc() == x.node_alloc()) { + move_buckets_from(x); + } + else if(x.size_) { + // TODO: Could pick new bucket size? + create_buckets(bucket_count_); - //////////////////////////////////////////////////////////////////////////// - // Swap & Move + move_nodes<node_allocator> move(node_alloc()); + node_holder<node_allocator> nodes(x); + table_impl::fill_buckets(nodes.begin(), *this, move); + } + } + + //////////////////////////////////////////////////////////////////////// + // Create buckets + + void create_buckets(std::size_t new_count) + { + boost::unordered::detail::array_constructor<bucket_allocator> + constructor(bucket_alloc()); - // Swap - // - // Strong exception safety - // - // Can throw if hash or predicate object's copy constructor throws - // or if allocators are unequal. - - template <class T> - inline void hash_table<T>::partial_swap(hash_table& x) - { - this->buckets::swap(x); // No throw - std::swap(this->size_, x.size_); - std::swap(this->mlf_, x.mlf_); - std::swap(this->cached_begin_bucket_, x.cached_begin_bucket_); - std::swap(this->max_load_, x.max_load_); - } + // Creates an extra bucket to act as the start node. + constructor.construct(bucket(), new_count + 1); + + if (buckets_) + { + // Copy the nodes to the new buckets, including the dummy + // node if there is one. + (constructor.get() + + static_cast<std::ptrdiff_t>(new_count))->next_ = + (buckets_ + static_cast<std::ptrdiff_t>( + bucket_count_))->next_; + destroy_buckets(); + } + else if (bucket::extra_node) + { + node_constructor a(node_alloc()); + a.construct(); + + (constructor.get() + + static_cast<std::ptrdiff_t>(new_count))->next_ = + a.release(); + } - template <class T> - inline void hash_table<T>::fast_swap(hash_table& x) - { - // These can throw, but they only affect the function objects - // that aren't in use so it is strongly exception safe, via. - // double buffering. + bucket_count_ = new_count; + buckets_ = constructor.release(); + recalculate_max_load(); + } + + //////////////////////////////////////////////////////////////////////// + // Swap and Move + + void swap_allocators(table& other, false_type) { - set_hash_functions<hasher, key_equal> op1(*this, x); - set_hash_functions<hasher, key_equal> op2(x, *this); - op1.commit(); - op2.commit(); + // According to 23.2.1.8, if propagate_on_container_swap is + // false the behaviour is undefined unless the allocators + // are equal. + BOOST_ASSERT(node_alloc() == other.node_alloc()); } - this->buckets::swap(x); // No throw - std::swap(this->size_, x.size_); - std::swap(this->mlf_, x.mlf_); - std::swap(this->cached_begin_bucket_, x.cached_begin_bucket_); - std::swap(this->max_load_, x.max_load_); - } - template <class T> - inline void hash_table<T>::slow_swap(hash_table& x) - { - if(this == &x) return; + void swap_allocators(table& other, true_type) + { + allocators_.swap(other.allocators_); + } + // Only swaps the allocators if propagate_on_container_swap + void swap(table& x) { - // These can throw, but they only affect the function objects - // that aren't in use so it is strongly exception safe, via. - // double buffering. - set_hash_functions<hasher, key_equal> op1(*this, x); - set_hash_functions<hasher, key_equal> op2(x, *this); - - // Create new buckets in separate hash_buckets objects - // which will clean up if anything throws an exception. - // (all can throw, but with no effect as these are new objects). - - buckets b1(this->node_alloc(), x.min_buckets_for_size(x.size_)); - if(x.size_) x.copy_buckets_to(b1); - - buckets b2(x.node_alloc(), this->min_buckets_for_size(this->size_)); - if(this->size_) copy_buckets_to(b2); - - // Modifying the data, so no throw from now on. - - b1.swap(*this); - b2.swap(x); + boost::unordered::detail::set_hash_functions<hasher, key_equal> + op1(*this, x); + boost::unordered::detail::set_hash_functions<hasher, key_equal> + op2(x, *this); + + // I think swap can throw if Propagate::value, + // since the allocators' swap can throw. Not sure though. + swap_allocators(x, + boost::unordered::detail::integral_constant<bool, + allocator_traits<node_allocator>:: + propagate_on_container_swap::value>()); + + boost::swap(buckets_, x.buckets_); + boost::swap(bucket_count_, x.bucket_count_); + boost::swap(size_, x.size_); + std::swap(mlf_, x.mlf_); + std::swap(max_load_, x.max_load_); op1.commit(); op2.commit(); } - - std::swap(this->size_, x.size_); - if(this->buckets_) this->init_buckets(); - if(x.buckets_) x.init_buckets(); - } - - template <class T> - void hash_table<T>::swap(hash_table& x) - { - if(this->node_alloc() == x.node_alloc()) { - if(this != &x) this->fast_swap(x); + void move_buckets_from(table& other) + { + BOOST_ASSERT(node_alloc() == other.node_alloc()); + BOOST_ASSERT(!buckets_); + buckets_ = other.buckets_; + bucket_count_ = other.bucket_count_; + size_ = other.size_; + other.buckets_ = bucket_pointer(); + other.size_ = 0; + other.max_load_ = 0; } - else { - this->slow_swap(x); + + //////////////////////////////////////////////////////////////////////// + // Delete/destruct + + ~table() + { + delete_buckets(); } - } - - // Move - // - // Strong exception safety (might change unused function objects) - // - // Can throw if hash or predicate object's copy constructor throws - // or if allocators are unequal. - - template <class T> - void hash_table<T>::move(hash_table& x) - { - // This can throw, but it only affects the function objects - // that aren't in use so it is strongly exception safe, via. - // double buffering. - set_hash_functions<hasher, key_equal> new_func_this(*this, x); - - if(this->node_alloc() == x.node_alloc()) { - this->buckets::move(x); // no throw - this->size_ = x.size_; - this->cached_begin_bucket_ = x.cached_begin_bucket_; - this->max_load_ = x.max_load_; - x.size_ = 0; + void delete_node(c_iterator n) + { + boost::unordered::detail::destroy_value_impl(node_alloc(), + n.node_->value_ptr()); + node_allocator_traits::destroy(node_alloc(), + boost::addressof(*n.node_)); + node_allocator_traits::deallocate(node_alloc(), n.node_, 1); + --size_; } - else { - // Create new buckets in separate HASH_TABLE_DATA objects - // which will clean up if anything throws an exception. - // (all can throw, but with no effect as these are new objects). - - buckets b(this->node_alloc(), x.min_buckets_for_size(x.size_)); - if(x.size_) x.copy_buckets_to(b); - - // Start updating the data here, no throw from now on. - this->size_ = x.size_; - b.swap(*this); - this->init_buckets(); - } - - // We've made it, the rest is no throw. - this->mlf_ = x.mlf_; - new_func_this.commit(); - } - - //////////////////////////////////////////////////////////////////////////// - // Reserve & Rehash - // basic exception safety - template <class T> - inline void hash_table<T>::create_for_insert(std::size_t size) - { - this->bucket_count_ = (std::max)(this->bucket_count_, - this->min_buckets_for_size(size)); - this->create_buckets(); - this->init_buckets(); - } + std::size_t delete_nodes(c_iterator begin, c_iterator end) + { + std::size_t count = 0; - // basic exception safety - template <class T> - inline bool hash_table<T>::reserve_for_insert(std::size_t size) - { - if(size >= max_load_) { - std::size_t num_buckets - = this->min_buckets_for_size((std::max)(size, - this->size_ + (this->size_ >> 1))); - if(num_buckets != this->bucket_count_) { - rehash_impl(num_buckets); - return true; + while(begin != end) { + c_iterator n = begin; + ++begin; + delete_node(n); + ++count; } + + return count; } - - return false; - } - // if hash function throws, basic exception safety - // strong otherwise. + void delete_buckets() + { + if(buckets_) { + delete_nodes(begin(), iterator()); + + if (bucket::extra_node) { + node_pointer n = static_cast<node_pointer>( + get_bucket(bucket_count_)->next_); + node_allocator_traits::destroy(node_alloc(), + boost::addressof(*n)); + node_allocator_traits::deallocate(node_alloc(), n, 1); + } - template <class T> - inline void hash_table<T>::rehash(std::size_t min_buckets) - { - using namespace std; + destroy_buckets(); + buckets_ = bucket_pointer(); + max_load_ = 0; + } - if(!this->size_) { - if(this->buckets_) this->delete_buckets(); - this->bucket_count_ = next_prime(min_buckets); + BOOST_ASSERT(!size_); } - else { - // no throw: - min_buckets = next_prime((std::max)(min_buckets, - double_to_size_t(floor(this->size_ / (double) mlf_)) + 1)); - if(min_buckets != this->bucket_count_) rehash_impl(min_buckets); + + void clear() + { + if(!size_) return; + + delete_nodes(begin(), iterator()); + get_previous_start()->next_ = link_pointer(); + clear_buckets(); + + BOOST_ASSERT(!size_); } - } - // if hash function throws, basic exception safety - // strong otherwise - - template <class T> - void hash_table<T> - ::rehash_impl(std::size_t num_buckets) - { - hasher const& hf = this->hash_function(); - std::size_t size = this->size_; - bucket_ptr end = this->get_bucket(this->bucket_count_); - - buckets dst(this->node_alloc(), num_buckets); - dst.create_buckets(); - - buckets src(this->node_alloc(), this->bucket_count_); - src.swap(*this); - this->size_ = 0; - - for(bucket_ptr bucket = this->cached_begin_bucket_; - bucket != end; ++bucket) - { - node_ptr group = bucket->next_; - while(group) { - // Move the first group of equivalent nodes in bucket to dst. - - // This next line throws iff the hash function throws. - bucket_ptr dst_bucket = dst.bucket_ptr_from_hash( - hf(get_key_from_ptr(group))); - - node_ptr& next_group = node::next_group(group); - bucket->next_ = next_group; - next_group = dst_bucket->next_; - dst_bucket->next_ = group; - group = bucket->next_; + void clear_buckets() + { + bucket_pointer end = get_bucket(bucket_count_); + for(bucket_pointer it = buckets_; it != end; ++it) + { + it->next_ = node_pointer(); } } - // Swap the new nodes back into the container and setup the local - // variables. - this->size_ = size; - dst.swap(*this); // no throw - this->init_buckets(); - } + void destroy_buckets() + { + bucket_pointer end = get_bucket(bucket_count_ + 1); + for(bucket_pointer it = buckets_; it != end; ++it) + { + bucket_allocator_traits::destroy(bucket_alloc(), + boost::addressof(*it)); + } - //////////////////////////////////////////////////////////////////////////// - // copy_buckets_to + bucket_allocator_traits::deallocate(bucket_alloc(), + buckets_, bucket_count_ + 1); + } - // copy_buckets_to - // - // basic excpetion safety. If an exception is thrown this will - // leave dst partially filled. + //////////////////////////////////////////////////////////////////////// + // Fix buckets after erase - template <class T> - void hash_table<T> - ::copy_buckets_to(buckets& dst) const - { - BOOST_ASSERT(this->buckets_ && !dst.buckets_); + // This is called after erasing a node or group of nodes to fix up + // the bucket pointers. + void fix_buckets(bucket_pointer this_bucket, + previous_pointer prev, node_pointer next) + { + if (!next) + { + if (this_bucket->next_ == prev) + this_bucket->next_ = node_pointer(); + } + else + { + bucket_pointer next_bucket = get_bucket( + policy::to_bucket(bucket_count_, next->hash_)); + + if (next_bucket != this_bucket) + { + next_bucket->next_ = prev; + if (this_bucket->next_ == prev) + this_bucket->next_ = node_pointer(); + } + } + } - hasher const& hf = this->hash_function(); - bucket_ptr end = this->get_bucket(this->bucket_count_); + // This is called after erasing a range of nodes to fix any bucket + // pointers into that range. + void fix_buckets_range(std::size_t bucket_index, + previous_pointer prev, node_pointer begin, node_pointer end) + { + node_pointer n = begin; + + // If we're not at the start of the current bucket, then + // go to the start of the next bucket. + if (get_bucket(bucket_index)->next_ != prev) + { + for(;;) { + n = static_cast<node_pointer>(n->next_); + if (n == end) { + if (n) { + std::size_t new_bucket_index = + policy::to_bucket(bucket_count_, n->hash_); + if (bucket_index != new_bucket_index) { + get_bucket(new_bucket_index)->next_ = prev; + } + } + return; + } + + std::size_t new_bucket_index = + policy::to_bucket(bucket_count_, n->hash_); + if (bucket_index != new_bucket_index) { + bucket_index = new_bucket_index; + break; + } + } + } - node_constructor a(dst); - dst.create_buckets(); + // Iterate through the remaining nodes, clearing out the bucket + // pointers. + get_bucket(bucket_index)->next_ = previous_pointer(); + for(;;) { + n = static_cast<node_pointer>(n->next_); + if (n == end) break; + + std::size_t new_bucket_index = + policy::to_bucket(bucket_count_, n->hash_); + if (bucket_index != new_bucket_index) { + bucket_index = new_bucket_index; + get_bucket(bucket_index)->next_ = previous_pointer(); + } + }; - // no throw: - for(bucket_ptr i = this->cached_begin_bucket_; i != end; ++i) { - // no throw: - for(node_ptr it = i->next_; it;) { - // hash function can throw. - bucket_ptr dst_bucket = dst.bucket_ptr_from_hash( - hf(get_key_from_ptr(it))); - // throws, strong + // Finally fix the bucket containing the trailing node. + if (n) { + get_bucket( + policy::to_bucket(bucket_count_, n->hash_))->next_ + = prev; + } + } - node_ptr group_end = node::next_group(it); + //////////////////////////////////////////////////////////////////////// + // Assignment - a.construct(node::get_value(it)); - node_ptr n = a.release(); - node::add_to_bucket(n, *dst_bucket); - - for(it = it->next_; it != group_end; it = it->next_) { - a.construct(node::get_value(it)); - node::add_after_node(a.release(), n); - } + void assign(table const& x) + { + if (this != boost::addressof(x)) + { + assign(x, + boost::unordered::detail::integral_constant<bool, + allocator_traits<node_allocator>:: + propagate_on_container_copy_assignment::value>()); } } - } - //////////////////////////////////////////////////////////////////////////// - // Misc. key methods + void assign(table const& x, false_type) + { + // Strong exception safety. + boost::unordered::detail::set_hash_functions<hasher, key_equal> + new_func_this(*this, x); + new_func_this.commit(); + mlf_ = x.mlf_; + recalculate_max_load(); - // strong exception safety + if (!size_ && !x.size_) return; - // count - // - // strong exception safety, no side effects + if (x.size_ >= max_load_) { + create_buckets(min_buckets_for_size(x.size_)); + } + else { + clear_buckets(); + } - template <class T> - std::size_t hash_table<T>::count(key_type const& k) const - { - if(!this->size_) return 0; - node_ptr it = find_iterator(k); // throws, strong - return BOOST_UNORDERED_BORLAND_BOOL(it) ? node::group_count(it) : 0; - } + // assign_nodes takes ownership of the container's elements, + // assigning to them if possible, and deleting any that are + // left over. + assign_nodes<table> assign(*this); + table_impl::fill_buckets(x.begin(), *this, assign); + } - // find - // - // strong exception safety, no side effects - template <class T> - BOOST_DEDUCED_TYPENAME T::iterator_base - hash_table<T>::find(key_type const& k) const - { - if(!this->size_) return this->end(); + void assign(table const& x, true_type) + { + if (node_alloc() == x.node_alloc()) { + allocators_.assign(x.allocators_); + assign(x, false_type()); + } + else { + boost::unordered::detail::set_hash_functions<hasher, key_equal> + new_func_this(*this, x); + + // Delete everything with current allocators before assigning + // the new ones. + delete_buckets(); + allocators_.assign(x.allocators_); + + // Copy over other data, all no throw. + new_func_this.commit(); + mlf_ = x.mlf_; + bucket_count_ = min_buckets_for_size(x.size_); + max_load_ = 0; + + // Finally copy the elements. + if (x.size_) { + create_buckets(bucket_count_); + copy_nodes<node_allocator> copy(node_alloc()); + table_impl::fill_buckets(x.begin(), *this, copy); + } + } + } - bucket_ptr bucket = this->get_bucket(this->bucket_index(k)); - node_ptr it = find_iterator(bucket, k); + void move_assign(table& x) + { + if (this != boost::addressof(x)) + { + move_assign(x, + boost::unordered::detail::integral_constant<bool, + allocator_traits<node_allocator>:: + propagate_on_container_move_assignment::value>()); + } + } - if (BOOST_UNORDERED_BORLAND_BOOL(it)) - return iterator_base(bucket, it); - else - return this->end(); - } + void move_assign(table& x, true_type) + { + delete_buckets(); + allocators_.move_assign(x.allocators_); + move_assign_no_alloc(x); + } - template <class T> - template <class Key, class Hash, class Pred> - BOOST_DEDUCED_TYPENAME T::iterator_base hash_table<T>::find(Key const& k, - Hash const& h, Pred const& eq) const - { - if(!this->size_) return this->end(); + void move_assign(table& x, false_type) + { + if (node_alloc() == x.node_alloc()) { + delete_buckets(); + move_assign_no_alloc(x); + } + else { + boost::unordered::detail::set_hash_functions<hasher, key_equal> + new_func_this(*this, x); + new_func_this.commit(); + mlf_ = x.mlf_; + recalculate_max_load(); - bucket_ptr bucket = this->get_bucket(h(k) % this->bucket_count_); - node_ptr it = find_iterator(bucket, k, eq); + if (!size_ && !x.size_) return; - if (BOOST_UNORDERED_BORLAND_BOOL(it)) - return iterator_base(bucket, it); - else - return this->end(); - } + if (x.size_ >= max_load_) { + create_buckets(min_buckets_for_size(x.size_)); + } + else { + clear_buckets(); + } - template <class T> - BOOST_DEDUCED_TYPENAME T::value_type& - hash_table<T>::at(key_type const& k) const - { - if(!this->size_) - boost::throw_exception(std::out_of_range("Unable to find key in unordered_map.")); + // move_assign_nodes takes ownership of the container's + // elements, assigning to them if possible, and deleting + // any that are left over. + move_assign_nodes<table> assign(*this); + node_holder<node_allocator> nodes(x); + table_impl::fill_buckets(nodes.begin(), *this, assign); + } + } + + void move_assign_no_alloc(table& x) + { + boost::unordered::detail::set_hash_functions<hasher, key_equal> + new_func_this(*this, x); + // No throw from here. + mlf_ = x.mlf_; + max_load_ = x.max_load_; + move_buckets_from(x); + new_func_this.commit(); + } - bucket_ptr bucket = this->get_bucket(this->bucket_index(k)); - node_ptr it = find_iterator(bucket, k); + // Accessors - if (!it) - boost::throw_exception(std::out_of_range("Unable to find key in unordered_map.")); + key_type const& get_key(value_type const& x) const + { + return extractor::extract(x); + } - return node::get_value(it); - } + std::size_t hash(key_type const& k) const + { + return policy::apply_hash(this->hash_function(), k); + } - // equal_range - // - // strong exception safety, no side effects - template <class T> - BOOST_DEDUCED_TYPENAME T::iterator_pair - hash_table<T>::equal_range(key_type const& k) const - { - if(!this->size_) - return iterator_pair(this->end(), this->end()); + // Find Node - bucket_ptr bucket = this->get_bucket(this->bucket_index(k)); - node_ptr it = find_iterator(bucket, k); - if (BOOST_UNORDERED_BORLAND_BOOL(it)) { - iterator_base first(iterator_base(bucket, it)); - iterator_base second(first); - second.increment_bucket(node::next_group(second.node_)); - return iterator_pair(first, second); - } - else { - return iterator_pair(this->end(), this->end()); + template <typename Key, typename Hash, typename Pred> + iterator generic_find_node( + Key const& k, + Hash const& hf, + Pred const& eq) const + { + return static_cast<table_impl const*>(this)-> + find_node_impl(policy::apply_hash(hf, k), k, eq); } - } - - //////////////////////////////////////////////////////////////////////////// - // Erase methods - - template <class T> - void hash_table<T>::clear() - { - if(!this->size_) return; - bucket_ptr end = this->get_bucket(this->bucket_count_); - for(bucket_ptr begin = this->buckets_; begin != end; ++begin) { - this->clear_bucket(begin); + iterator find_node( + std::size_t key_hash, + key_type const& k) const + { + return static_cast<table_impl const*>(this)-> + find_node_impl(key_hash, k, this->key_eq()); } - this->size_ = 0; - this->cached_begin_bucket_ = end; - } + iterator find_node(key_type const& k) const + { + return static_cast<table_impl const*>(this)-> + find_node_impl(hash(k), k, this->key_eq()); + } - template <class T> - inline std::size_t hash_table<T>::erase_group( - node_ptr* it, bucket_ptr bucket) - { - node_ptr pos = *it; - node_ptr end = node::next_group(pos); - *it = end; - std::size_t count = this->delete_nodes(pos, end); - this->size_ -= count; - this->recompute_begin_bucket(bucket); - return count; - } - - template <class T> - std::size_t hash_table<T>::erase_key(key_type const& k) - { - if(!this->size_) return 0; + iterator find_matching_node(iterator n) const + { + // TODO: Does this apply to C++11? + // + // For some stupid reason, I decided to support equality comparison + // when different hash functions are used. So I can't use the hash + // value from the node here. - // No side effects in initial section - bucket_ptr bucket = this->get_bucket(this->bucket_index(k)); - node_ptr* it = this->find_for_erase(bucket, k); + return find_node(get_key(*n)); + } - // No throw. - return *it ? this->erase_group(it, bucket) : 0; - } + // Reserve and rehash - template <class T> - void hash_table<T>::erase(iterator_base r) - { - BOOST_ASSERT(r.node_); - --this->size_; - node::unlink_node(*r.bucket_, r.node_); - this->delete_node(r.node_); - // r has been invalidated but its bucket is still valid - this->recompute_begin_bucket(r.bucket_); - } + void reserve_for_insert(std::size_t); + void rehash(std::size_t); + void reserve(std::size_t); + }; - template <class T> - BOOST_DEDUCED_TYPENAME T::iterator_base - hash_table<T>::erase_return_iterator(iterator_base r) - { - BOOST_ASSERT(r.node_); - iterator_base next = r; - next.increment(); - --this->size_; - node::unlink_node(*r.bucket_, r.node_); - this->delete_node(r.node_); - // r has been invalidated but its bucket is still valid - this->recompute_begin_bucket(r.bucket_, next.bucket_); - return next; - } + //////////////////////////////////////////////////////////////////////////// + // Reserve & Rehash - template <class T> - BOOST_DEDUCED_TYPENAME T::iterator_base - hash_table<T>::erase_range( - iterator_base r1, iterator_base r2) + // basic exception safety + template <typename Types> + inline void table<Types>::reserve_for_insert(std::size_t size) { - if(r1 != r2) - { - BOOST_ASSERT(r1.node_); - if (r1.bucket_ == r2.bucket_) { - node::unlink_nodes(*r1.bucket_, r1.node_, r2.node_); - this->size_ -= this->delete_nodes(r1.node_, r2.node_); + if (!buckets_) { + create_buckets((std::max)(bucket_count_, + min_buckets_for_size(size))); + } + // 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 + = min_buckets_for_size((std::max)(size, + size_ + (size_ >> 1))); - // No need to call recompute_begin_bucket because - // the nodes are only deleted from one bucket, which - // still contains r2 after the erase. - BOOST_ASSERT(r1.bucket_->next_); - } - else { - bucket_ptr end_bucket = r2.node_ ? - r2.bucket_ : this->get_bucket(this->bucket_count_); - BOOST_ASSERT(r1.bucket_ < end_bucket); - node::unlink_nodes(*r1.bucket_, r1.node_, node_ptr()); - this->size_ -= this->delete_nodes(r1.node_, node_ptr()); - - bucket_ptr i = r1.bucket_; - for(++i; i != end_bucket; ++i) { - this->size_ -= this->delete_nodes(i->next_, node_ptr()); - i->next_ = node_ptr(); - } + if (num_buckets != bucket_count_) + static_cast<table_impl*>(this)->rehash_impl(num_buckets); + } + } - if(r2.node_) { - node_ptr first = r2.bucket_->next_; - node::unlink_nodes(*r2.bucket_, r2.node_); - this->size_ -= this->delete_nodes(first, r2.node_); - } + // if hash function throws, basic exception safety + // strong otherwise. - // r1 has been invalidated but its bucket is still - // valid. - this->recompute_begin_bucket(r1.bucket_, end_bucket); - } + template <typename Types> + inline void table<Types>::rehash(std::size_t min_buckets) + { + using namespace std; + + if(!size_) { + delete_buckets(); + bucket_count_ = policy::new_bucket_count(min_buckets); } + else { + min_buckets = policy::new_bucket_count((std::max)(min_buckets, + boost::unordered::detail::double_to_size(floor( + static_cast<double>(size_) / + static_cast<double>(mlf_))) + 1)); - return r2; + if(min_buckets != bucket_count_) + static_cast<table_impl*>(this)->rehash_impl(min_buckets); + } } - template <class T> - BOOST_DEDUCED_TYPENAME hash_table<T>::iterator_base - hash_table<T>::emplace_empty_impl_with_node( - node_constructor& a, std::size_t size) + template <typename Types> + inline void table<Types>::reserve(std::size_t num_elements) { - key_type const& k = get_key(a.value()); - std::size_t hash_value = this->hash_function()(k); - if(this->buckets_) this->reserve_for_insert(size); - else this->create_for_insert(size); - bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value); - node_ptr n = a.release(); - node::add_to_bucket(n, *bucket); - ++this->size_; - this->cached_begin_bucket_ = bucket; - return iterator_base(bucket, n); + rehash(static_cast<std::size_t>( + std::ceil(static_cast<double>(num_elements) / mlf_))); } -}} +}}} + +#if defined(BOOST_MSVC) +#pragma warning(pop) +#endif #endif diff --git a/3rdParty/Boost/src/boost/unordered/detail/unique.hpp b/3rdParty/Boost/src/boost/unordered/detail/unique.hpp index 96fdfee..8805652 100644 --- a/3rdParty/Boost/src/boost/unordered/detail/unique.hpp +++ b/3rdParty/Boost/src/boost/unordered/detail/unique.hpp @@ -1,513 +1,651 @@ // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. -// Copyright (C) 2005-2010 Daniel James +// Copyright (C) 2005-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) #ifndef BOOST_UNORDERED_DETAIL_UNIQUE_HPP_INCLUDED #define BOOST_UNORDERED_DETAIL_UNIQUE_HPP_INCLUDED +#if defined(_MSC_VER) && (_MSC_VER >= 1020) +# pragma once +#endif + #include <boost/unordered/detail/table.hpp> #include <boost/unordered/detail/extract_key.hpp> +#include <boost/throw_exception.hpp> +#include <stdexcept> + +namespace boost { namespace unordered { namespace detail { -namespace boost { namespace unordered_detail { + template <typename A, typename T> struct unique_node; + template <typename T> struct ptr_node; + template <typename Types> struct table_impl; - template <class T> - class hash_unique_table : public T::table + template <typename A, typename T> + struct unique_node : + boost::unordered::detail::value_base<T> { - public: - typedef BOOST_DEDUCED_TYPENAME T::hasher hasher; - typedef BOOST_DEDUCED_TYPENAME T::key_equal key_equal; - typedef BOOST_DEDUCED_TYPENAME T::value_allocator value_allocator; - typedef BOOST_DEDUCED_TYPENAME T::key_type key_type; - typedef BOOST_DEDUCED_TYPENAME T::value_type value_type; - typedef BOOST_DEDUCED_TYPENAME T::table table; - typedef BOOST_DEDUCED_TYPENAME T::node_constructor node_constructor; - - typedef BOOST_DEDUCED_TYPENAME T::node node; - typedef BOOST_DEDUCED_TYPENAME T::node_ptr node_ptr; - typedef BOOST_DEDUCED_TYPENAME T::bucket_ptr bucket_ptr; - typedef BOOST_DEDUCED_TYPENAME T::iterator_base iterator_base; - typedef BOOST_DEDUCED_TYPENAME T::extractor extractor; - - typedef std::pair<iterator_base, bool> emplace_return; + typedef typename ::boost::unordered::detail::rebind_wrap< + A, unique_node<A, T> >::type::pointer link_pointer; - // Constructors + link_pointer next_; + std::size_t hash_; - hash_unique_table(std::size_t n, hasher const& hf, key_equal const& eq, - value_allocator const& a) - : table(n, hf, eq, a) {} - hash_unique_table(hash_unique_table const& x) - : table(x, x.node_alloc()) {} - hash_unique_table(hash_unique_table const& x, value_allocator const& a) - : table(x, a) {} - hash_unique_table(hash_unique_table& x, move_tag m) - : table(x, m) {} - hash_unique_table(hash_unique_table& x, value_allocator const& a, - move_tag m) - : table(x, a, m) {} - ~hash_unique_table() {} - - // Insert methods - - emplace_return emplace_impl_with_node(node_constructor& a); - value_type& operator[](key_type const& k); + unique_node() : + next_(), + hash_(0) + {} - // equals + void init(link_pointer) + { + } - bool equals(hash_unique_table const&) const; + private: + unique_node& operator=(unique_node const&); + }; - node_ptr add_node(node_constructor& a, bucket_ptr bucket); - -#if defined(BOOST_UNORDERED_STD_FORWARD) + template <typename T> + struct ptr_node : + boost::unordered::detail::value_base<T>, + boost::unordered::detail::ptr_bucket + { + typedef boost::unordered::detail::ptr_bucket bucket_base; + typedef ptr_bucket* link_pointer; - template<class... Args> - emplace_return emplace(Args&&... args); - template<class... Args> - emplace_return emplace_impl(key_type const& k, Args&&... args); - template<class... Args> - emplace_return emplace_impl(no_key, Args&&... args); - template<class... Args> - emplace_return emplace_empty_impl(Args&&... args); -#else + std::size_t hash_; -#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \ - template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \ - emplace_return emplace( \ - BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); \ - template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \ - emplace_return emplace_impl(key_type const& k, \ - BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); \ - template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \ - emplace_return emplace_impl(no_key, \ - BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); \ - template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \ - emplace_return emplace_empty_impl( \ - BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); - - BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, - BOOST_UNORDERED_INSERT_IMPL, _) - -#undef BOOST_UNORDERED_INSERT_IMPL + ptr_node() : + bucket_base(), + hash_(0) + {} -#endif + void init(link_pointer) + { + } - // if hash function throws, or inserting > 1 element, basic exception - // safety strong otherwise - template <class InputIt> - void insert_range(InputIt i, InputIt j); - template <class InputIt> - void insert_range_impl(key_type const&, InputIt i, InputIt j); - template <class InputIt> - void insert_range_impl2(node_constructor&, key_type const&, InputIt i, InputIt j); - template <class InputIt> - void insert_range_impl(no_key, InputIt i, InputIt j); + private: + ptr_node& operator=(ptr_node const&); }; - template <class H, class P, class A> - struct set : public types< - BOOST_DEDUCED_TYPENAME A::value_type, - BOOST_DEDUCED_TYPENAME A::value_type, - H, P, A, - set_extractor<BOOST_DEDUCED_TYPENAME A::value_type>, - ungrouped> - { - typedef hash_unique_table<set<H, P, A> > impl; - typedef hash_table<set<H, P, A> > table; + // If the allocator uses raw pointers use ptr_node + // Otherwise use node. + + template <typename A, typename T, typename NodePtr, typename BucketPtr> + struct pick_node2 + { + typedef boost::unordered::detail::unique_node<A, T> node; + + typedef typename boost::unordered::detail::allocator_traits< + typename boost::unordered::detail::rebind_wrap<A, node>::type + >::pointer node_pointer; + + typedef boost::unordered::detail::bucket<node_pointer> bucket; + typedef node_pointer link_pointer; }; - template <class K, class H, class P, class A> - struct map : public types< - K, BOOST_DEDUCED_TYPENAME A::value_type, - H, P, A, - map_extractor<K, BOOST_DEDUCED_TYPENAME A::value_type>, - ungrouped> + template <typename A, typename T> + struct pick_node2<A, T, + boost::unordered::detail::ptr_node<T>*, + boost::unordered::detail::ptr_bucket*> { - typedef hash_unique_table<map<K, H, P, A> > impl; - typedef hash_table<map<K, H, P, A> > table; + typedef boost::unordered::detail::ptr_node<T> node; + typedef boost::unordered::detail::ptr_bucket bucket; + typedef bucket* link_pointer; }; - //////////////////////////////////////////////////////////////////////////// - // Equality + template <typename A, typename T> + struct pick_node + { + typedef boost::unordered::detail::allocator_traits< + typename boost::unordered::detail::rebind_wrap<A, + boost::unordered::detail::ptr_node<T> >::type + > tentative_node_traits; + + typedef boost::unordered::detail::allocator_traits< + typename boost::unordered::detail::rebind_wrap<A, + boost::unordered::detail::ptr_bucket >::type + > tentative_bucket_traits; + + typedef pick_node2<A, T, + typename tentative_node_traits::pointer, + typename tentative_bucket_traits::pointer> pick; + + typedef typename pick::node node; + typedef typename pick::bucket bucket; + typedef typename pick::link_pointer link_pointer; + }; + + template <typename A, typename T, typename H, typename P> + struct set + { + typedef boost::unordered::detail::set<A, T, H, P> types; + + typedef A allocator; + typedef T value_type; + typedef H hasher; + typedef P key_equal; + typedef T key_type; + + typedef boost::unordered::detail::allocator_traits<allocator> traits; + typedef boost::unordered::detail::pick_node<allocator, value_type> pick; + typedef typename pick::node node; + typedef typename pick::bucket bucket; + typedef typename pick::link_pointer link_pointer; + + 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> + struct map + { + typedef boost::unordered::detail::map<A, K, M, H, P> types; + + typedef A allocator; + typedef std::pair<K const, M> value_type; + typedef H hasher; + typedef P key_equal; + typedef K key_type; + + typedef boost::unordered::detail::allocator_traits<allocator> + traits; + typedef boost::unordered::detail::pick_node<allocator, value_type> pick; + typedef typename pick::node node; + typedef typename pick::bucket bucket; + typedef typename pick::link_pointer link_pointer; + + 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 <class T> - bool hash_unique_table<T> - ::equals(hash_unique_table<T> const& other) const + template <typename Types> + struct table_impl : boost::unordered::detail::table<Types> { - if(this->size_ != other.size_) return false; - if(!this->size_) return true; + typedef boost::unordered::detail::table<Types> table; + typedef typename table::value_type value_type; + typedef typename table::bucket bucket; + typedef typename table::policy policy; + typedef typename table::node_pointer node_pointer; + typedef typename table::node_allocator node_allocator; + typedef typename table::node_allocator_traits node_allocator_traits; + typedef typename table::bucket_pointer bucket_pointer; + typedef typename table::link_pointer link_pointer; + typedef typename table::previous_pointer previous_pointer; + typedef typename table::hasher hasher; + typedef typename table::key_equal key_equal; + typedef typename table::key_type key_type; + 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; + + // Constructors + + table_impl(std::size_t n, + hasher const& hf, + key_equal const& eq, + node_allocator const& a) + : table(n, hf, eq, a) + {} + + table_impl(table_impl const& x) + : table(x, node_allocator_traits:: + select_on_container_copy_construction(x.node_alloc())) + { + this->init(x); + } + + table_impl(table_impl const& x, + node_allocator const& a) + : table(x, a) + { + this->init(x); + } + + table_impl(table_impl& x, + boost::unordered::detail::move_tag m) + : table(x, m) + {} - bucket_ptr end = this->get_bucket(this->bucket_count_); - for(bucket_ptr i = this->cached_begin_bucket_; i != end; ++i) + table_impl(table_impl& x, + node_allocator const& a, + boost::unordered::detail::move_tag m) + : table(x, a, m) { - node_ptr it1 = i->next_; - while(BOOST_UNORDERED_BORLAND_BOOL(it1)) + this->move_init(x); + } + + // Accessors + + template <class Key, class Pred> + iterator find_node_impl( + std::size_t key_hash, + Key const& k, + Pred const& eq) const + { + std::size_t bucket_index = + policy::to_bucket(this->bucket_count_, key_hash); + iterator n = this->begin(bucket_index); + + for (;;) { - node_ptr it2 = other.find_iterator(this->get_key_from_ptr(it1)); - if(!BOOST_UNORDERED_BORLAND_BOOL(it2)) return false; - if(!extractor::compare_mapped( - node::get_value(it1), node::get_value(it2))) - return false; - it1 = it1->next_; + if (!n.node_) return n; + + std::size_t node_hash = n.node_->hash_; + if (key_hash == node_hash) + { + if (eq(k, this->get_key(*n))) + return n; + } + else + { + if (policy::to_bucket(this->bucket_count_, node_hash) + != bucket_index) + return iterator(); + } + + ++n; } } - return true; - } + std::size_t count(key_type const& k) const + { + return this->find_node(k).node_ ? 1 : 0; + } - //////////////////////////////////////////////////////////////////////////// - // A convenience method for adding nodes. + value_type& at(key_type const& k) const + { + if (this->size_) { + iterator it = this->find_node(k); + if (it.node_) return *it; + } - template <class T> - inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::node_ptr - hash_unique_table<T>::add_node(node_constructor& a, - bucket_ptr bucket) - { - node_ptr n = a.release(); - node::add_to_bucket(n, *bucket); - ++this->size_; - if(bucket < this->cached_begin_bucket_) - this->cached_begin_bucket_ = bucket; - return n; - } - - //////////////////////////////////////////////////////////////////////////// - // Insert methods - - // if hash function throws, basic exception safety - // strong otherwise - template <class T> - BOOST_DEDUCED_TYPENAME hash_unique_table<T>::value_type& - hash_unique_table<T>::operator[](key_type const& k) - { - typedef BOOST_DEDUCED_TYPENAME value_type::second_type mapped_type; - - std::size_t hash_value = this->hash_function()(k); - bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value); - - if(!this->buckets_) { - node_constructor a(*this); - a.construct_pair(k, (mapped_type*) 0); - return *this->emplace_empty_impl_with_node(a, 1); + boost::throw_exception( + std::out_of_range("Unable to find key in unordered_map.")); } - node_ptr pos = this->find_iterator(bucket, k); + std::pair<iterator, iterator> + equal_range(key_type const& k) const + { + iterator n = this->find_node(k); + iterator n2 = n; + if (n2.node_) ++n2; + return std::make_pair(n, n2); + } + + // equals - if (BOOST_UNORDERED_BORLAND_BOOL(pos)) { - return node::get_value(pos); + bool equals(table_impl const& other) const + { + if(this->size_ != other.size_) return false; + + for(iterator n1 = this->begin(); n1.node_; ++n1) + { + iterator n2 = other.find_matching_node(n1); + +#if !defined(BOOST_UNORDERED_DEPRECATED_EQUALITY) + if (!n2.node_ || *n1 != *n2) + return false; +#else + if (!n2.node_ || !extractor::compare_mapped(*n1, *n2)) + return false; +#endif + } + + return true; + } + + // Emplace/Insert + + inline iterator add_node( + node_constructor& a, + std::size_t key_hash) + { + node_pointer n = a.release(); + n->hash_ = key_hash; + + 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(policy::to_bucket(this->bucket_count_, + static_cast<node_pointer>(start_node->next_)->hash_) + )->next_ = n; + } + + b->next_ = start_node; + n->next_ = start_node->next_; + start_node->next_ = static_cast<link_pointer>(n); + } + else + { + n->next_ = b->next_->next_; + b->next_->next_ = static_cast<link_pointer>(n); + } + + ++this->size_; + return iterator(n); } - else { - // Side effects only in this block. + value_type& operator[](key_type const& k) + { + typedef typename value_type::second_type mapped_type; + + std::size_t key_hash = this->hash(k); + iterator pos = this->find_node(key_hash, k); + + 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); - a.construct_pair(k, (mapped_type*) 0); + node_constructor a(this->node_alloc()); + a.construct_with_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, key_hash); + } - // reserve has basic exception safety if the hash function - // throws, strong otherwise. - if(this->reserve_for_insert(this->size_ + 1)) - bucket = this->bucket_ptr_from_hash(hash_value); +#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(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 - // Nothing after this point can throw. + template <BOOST_UNORDERED_EMPLACE_TEMPLATE> + emplace_return emplace(BOOST_UNORDERED_EMPLACE_ARGS) + { +#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), + BOOST_UNORDERED_EMPLACE_FORWARD); +#endif + } - return node::get_value(add_node(a, bucket)); +#if defined(BOOST_NO_VARIADIC_TEMPLATES) + template <typename A0> + emplace_return emplace( + boost::unordered::detail::emplace_args1<A0> const& args) + { + return emplace_impl(extractor::extract(args.a0), args); } - } +#endif - template <class T> - inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return - hash_unique_table<T>::emplace_impl_with_node(node_constructor& a) - { - // No side effects in this initial code - key_type const& k = this->get_key(a.value()); - std::size_t hash_value = this->hash_function()(k); - bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value); - node_ptr pos = this->find_iterator(bucket, k); - - if (BOOST_UNORDERED_BORLAND_BOOL(pos)) { - // Found an existing key, return it (no throw). - return emplace_return(iterator_base(bucket, pos), false); - } else { + template <BOOST_UNORDERED_EMPLACE_TEMPLATE> + emplace_return emplace_impl(key_type const& k, + BOOST_UNORDERED_EMPLACE_ARGS) + { + std::size_t key_hash = this->hash(k); + iterator pos = this->find_node(key_hash, k); + + 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). + node_constructor a(this->node_alloc()); + a.construct_with_value(BOOST_UNORDERED_EMPLACE_FORWARD); + // reserve has basic exception safety if the hash function // throws, strong otherwise. - if(this->reserve_for_insert(this->size_ + 1)) - bucket = this->bucket_ptr_from_hash(hash_value); + this->reserve_for_insert(this->size_ + 1); + return emplace_return(this->add_node(a, key_hash), true); + } - // Nothing after this point can throw. + emplace_return emplace_impl_with_node(node_constructor& a) + { + key_type const& k = this->get_key(a.value()); + std::size_t key_hash = this->hash(k); + iterator pos = this->find_node(key_hash, k); - return emplace_return( - iterator_base(bucket, add_node(a, bucket)), - true); - } - } + if (pos.node_) return emplace_return(pos, false); -#if defined(BOOST_UNORDERED_STD_FORWARD) + // reserve has basic exception safety if the hash function + // throws, strong otherwise. + this->reserve_for_insert(this->size_ + 1); + return emplace_return(this->add_node(a, key_hash), true); + } - template <class T> - template<class... Args> - inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return - hash_unique_table<T>::emplace_impl(key_type const& k, - Args&&... args) - { - // No side effects in this initial code - std::size_t hash_value = this->hash_function()(k); - bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value); - node_ptr pos = this->find_iterator(bucket, k); + template <BOOST_UNORDERED_EMPLACE_TEMPLATE> + emplace_return emplace_impl(no_key, BOOST_UNORDERED_EMPLACE_ARGS) + { + // Don't have a key, so construct the node first in order + // to be able to lookup the position. + node_constructor a(this->node_alloc()); + a.construct_with_value(BOOST_UNORDERED_EMPLACE_FORWARD); + return emplace_impl_with_node(a); + } - if (BOOST_UNORDERED_BORLAND_BOOL(pos)) { - // Found an existing key, return it (no throw). - return emplace_return(iterator_base(bucket, pos), false); + //////////////////////////////////////////////////////////////////////// + // Insert range methods + // + // if hash function throws, or inserting > 1 element, basic exception + // safety strong otherwise - } else { - // Doesn't already exist, add to bucket. - // Side effects only in this block. + template <class InputIt> + void insert_range(InputIt i, InputIt j) + { + if(i != j) + return insert_range_impl(extractor::extract(*i), i, j); + } - // Create the node before rehashing in case it throws an - // exception (need strong safety in such a case). - node_constructor a(*this); - a.construct(std::forward<Args>(args)...); + template <class InputIt> + void insert_range_impl(key_type const& k, InputIt i, InputIt j) + { + node_constructor a(this->node_alloc()); + + insert_range_impl2(a, k, i, j); + + while(++i != j) { + // Note: can't use get_key as '*i' might not be value_type - it + // could be a pair with first_types as key_type without const or + // a different second_type. + // + // TODO: Might be worth storing the value_type instead of the + // key here. Could be more efficient if '*i' is expensive. Could + // be less efficient if copying the full value_type is + // expensive. + insert_range_impl2(a, extractor::extract(*i), i, j); + } + } - // reserve has basic exception safety if the hash function - // throws, strong otherwise. - if(this->reserve_for_insert(this->size_ + 1)) - bucket = this->bucket_ptr_from_hash(hash_value); + template <class InputIt> + void insert_range_impl2(node_constructor& a, key_type const& k, + InputIt i, InputIt j) + { + // No side effects in this initial code + std::size_t key_hash = this->hash(k); + iterator pos = this->find_node(key_hash, k); + + if (!pos.node_) { + a.construct_with_value2(*i); + 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, key_hash); + } + } - // Nothing after this point can throw. + template <class InputIt> + void insert_range_impl(no_key, InputIt i, InputIt j) + { + node_constructor a(this->node_alloc()); - return emplace_return( - iterator_base(bucket, add_node(a, bucket)), - true); + do { + a.construct_with_value2(*i); + emplace_impl_with_node(a); + } while(++i != j); } - } - template <class T> - template<class... Args> - inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return - hash_unique_table<T>::emplace_impl(no_key, Args&&... args) - { - // Construct the node regardless - in order to get the key. - // It will be discarded if it isn't used - node_constructor a(*this); - a.construct(std::forward<Args>(args)...); - return emplace_impl_with_node(a); - } - - template <class T> - template<class... Args> - inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return - hash_unique_table<T>::emplace_empty_impl(Args&&... args) - { - node_constructor a(*this); - a.construct(std::forward<Args>(args)...); - return emplace_return(this->emplace_empty_impl_with_node(a, 1), true); - } + //////////////////////////////////////////////////////////////////////// + // Erase + // + // no throw -#else + std::size_t erase_key(key_type const& k) + { + if(!this->size_) return 0; -#define BOOST_UNORDERED_INSERT_IMPL(z, num_params, _) \ - template <class T> \ - template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \ - inline BOOST_DEDUCED_TYPENAME \ - hash_unique_table<T>::emplace_return \ - hash_unique_table<T>::emplace_impl( \ - key_type const& k, \ - BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \ - { \ - std::size_t hash_value = this->hash_function()(k); \ - bucket_ptr bucket \ - = this->bucket_ptr_from_hash(hash_value); \ - node_ptr pos = this->find_iterator(bucket, k); \ - \ - if (BOOST_UNORDERED_BORLAND_BOOL(pos)) { \ - return emplace_return(iterator_base(bucket, pos), false); \ - } else { \ - node_constructor a(*this); \ - a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \ - \ - if(this->reserve_for_insert(this->size_ + 1)) \ - bucket = this->bucket_ptr_from_hash(hash_value); \ - \ - return emplace_return(iterator_base(bucket, \ - add_node(a, bucket)), true); \ - } \ - } \ - \ - template <class T> \ - template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \ - inline BOOST_DEDUCED_TYPENAME \ - hash_unique_table<T>::emplace_return \ - hash_unique_table<T>:: \ - emplace_impl(no_key, \ - BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \ - { \ - node_constructor a(*this); \ - a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \ - return emplace_impl_with_node(a); \ - } \ - \ - template <class T> \ - template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \ - inline BOOST_DEDUCED_TYPENAME \ - hash_unique_table<T>::emplace_return \ - hash_unique_table<T>:: \ - emplace_empty_impl( \ - BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \ - { \ - node_constructor a(*this); \ - a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \ - return emplace_return(this->emplace_empty_impl_with_node(a, 1), true); \ - } - - BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, - BOOST_UNORDERED_INSERT_IMPL, _) - -#undef BOOST_UNORDERED_INSERT_IMPL + 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); -#endif + previous_pointer prev = this_bucket->next_; + if (!prev) return 0; -#if defined(BOOST_UNORDERED_STD_FORWARD) + for (;;) + { + if (!prev->next_) return 0; + std::size_t node_hash = + static_cast<node_pointer>(prev->next_)->hash_; + if (policy::to_bucket(this->bucket_count_, node_hash) + != bucket_index) + return 0; + if (node_hash == key_hash && + this->key_eq()(k, this->get_key( + static_cast<node_pointer>(prev->next_)->value()))) + break; + prev = static_cast<previous_pointer>(prev->next_); + } - // Emplace (unique keys) - // (I'm using an overloaded emplace for both 'insert' and 'emplace') + 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(this_bucket, prev, end); + return this->delete_nodes(c_iterator(pos), c_iterator(end)); + } - // if hash function throws, basic exception safety - // strong otherwise + iterator erase(c_iterator r) + { + BOOST_ASSERT(r.node_); + iterator next(r.node_); + ++next; - template <class T> - template<class... Args> - BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return - hash_unique_table<T>::emplace(Args&&... args) - { - return this->size_ ? - emplace_impl( - extractor::extract(std::forward<Args>(args)...), - std::forward<Args>(args)...) : - emplace_empty_impl(std::forward<Args>(args)...); - } + 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_); -#else + this->fix_buckets(this_bucket, prev, next.node_); - template <class T> - template <class Arg0> - BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return - hash_unique_table<T>::emplace(Arg0 const& arg0) - { - return this->size_ ? - emplace_impl(extractor::extract(arg0), arg0) : - emplace_empty_impl(arg0); - } - -#define BOOST_UNORDERED_INSERT_IMPL(z, num_params, _) \ - template <class T> \ - template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \ - BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return \ - hash_unique_table<T>::emplace( \ - BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \ - { \ - return this->size_ ? \ - emplace_impl(extractor::extract(arg0, arg1), \ - BOOST_UNORDERED_CALL_PARAMS(z, num_params)) : \ - emplace_empty_impl( \ - BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \ - } - - BOOST_PP_REPEAT_FROM_TO(2, BOOST_UNORDERED_EMPLACE_LIMIT, - BOOST_UNORDERED_INSERT_IMPL, _) - -#undef BOOST_UNORDERED_INSERT_IMPL + this->delete_node(r); -#endif - - //////////////////////////////////////////////////////////////////////////// - // Insert range methods + return next; + } - template <class T> - template <class InputIt> - inline void hash_unique_table<T>::insert_range_impl2( - node_constructor& a, key_type const& k, InputIt i, InputIt j) - { - // No side effects in this initial code - std::size_t hash_value = this->hash_function()(k); - bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value); - node_ptr pos = this->find_iterator(bucket, k); + iterator erase_range(c_iterator r1, c_iterator r2) + { + if (r1 == r2) return iterator(r2.node_); - if (!BOOST_UNORDERED_BORLAND_BOOL(pos)) { - // Doesn't already exist, add to bucket. - // Side effects only in this block. + 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.node_, r2.node_); + this->fix_buckets_range(bucket_index, prev, r1.node_, r2.node_); + this->delete_nodes(r1, r2); - // Create the node before rehashing in case it throws an - // exception (need strong safety in such a case). - a.construct(*i); + return iterator(r2.node_); + } - // reserve has basic exception safety if the hash function - // throws, strong otherwise. - if(this->size_ + 1 >= this->max_load_) { - this->reserve_for_insert(this->size_ + insert_size(i, j)); - bucket = this->bucket_ptr_from_hash(hash_value); - } + static previous_pointer unlink_node(bucket& b, node_pointer n) + { + return unlink_nodes(b, n, static_cast<node_pointer>(n->next_)); + } - // Nothing after this point can throw. - add_node(a, bucket); + static previous_pointer unlink_nodes(bucket& b, + node_pointer begin, node_pointer end) + { + previous_pointer prev = b.next_; + link_pointer begin_void = static_cast<link_pointer>(begin); + while(prev->next_ != begin_void) + prev = static_cast<previous_pointer>(prev->next_); + prev->next_ = static_cast<link_pointer>(end); + return prev; } - } - template <class T> - template <class InputIt> - inline void hash_unique_table<T>::insert_range_impl( - key_type const&, InputIt i, InputIt j) - { - node_constructor a(*this); + //////////////////////////////////////////////////////////////////////// + // fill_buckets + + template <class NodeCreator> + static void fill_buckets(iterator n, table& dst, + NodeCreator& creator) + { + previous_pointer prev = dst.get_previous_start(); + + while (n.node_) { + node_pointer node = creator.create(*n); + node->hash_ = n.node_->hash_; + prev->next_ = static_cast<link_pointer>(node); + ++dst.size_; + ++n; - if(!this->size_) { - a.construct(*i); - this->emplace_empty_impl_with_node(a, 1); - ++i; - if(i == j) return; + prev = place_in_bucket(dst, prev); + } } - do { - // Note: can't use get_key as '*i' might not be value_type - it - // could be a pair with first_types as key_type without const or a - // different second_type. - // - // TODO: Might be worth storing the value_type instead of the key - // here. Could be more efficient if '*i' is expensive. Could be - // less efficient if copying the full value_type is expensive. - insert_range_impl2(a, extractor::extract(*i), i, j); - } while(++i != j); - } - - template <class T> - template <class InputIt> - inline void hash_unique_table<T>::insert_range_impl( - no_key, InputIt i, InputIt j) - { - node_constructor a(*this); + // strong otherwise exception safety + void rehash_impl(std::size_t num_buckets) + { + BOOST_ASSERT(this->buckets_); - if(!this->size_) { - a.construct(*i); - this->emplace_empty_impl_with_node(a, 1); - ++i; - if(i == j) return; + this->create_buckets(num_buckets); + previous_pointer prev = this->get_previous_start(); + while (prev->next_) + prev = place_in_bucket(*this, prev); } - do { - // No side effects in this initial code - a.construct(*i); - emplace_impl_with_node(a); - } while(++i != j); - } - - // if hash function throws, or inserting > 1 element, basic exception safety - // strong otherwise - template <class T> - template <class InputIt> - void hash_unique_table<T>::insert_range(InputIt i, InputIt j) - { - if(i != j) - return insert_range_impl(extractor::extract(*i), i, j); - } -}} + // Iterate through the nodes placing them in the correct buckets. + // pre: prev->next_ is not null. + static previous_pointer place_in_bucket(table& dst, + previous_pointer prev) + { + node_pointer n = static_cast<node_pointer>(prev->next_); + bucket_pointer b = dst.get_bucket( + table::to_bucket(dst.bucket_count_, n->hash_)); + + if (!b->next_) { + b->next_ = prev; + return static_cast<previous_pointer>(n); + } + else { + prev->next_ = n->next_; + n->next_ = b->next_->next_; + b->next_->next_ = static_cast<link_pointer>(n); + return prev; + } + } + }; +}}} #endif diff --git a/3rdParty/Boost/src/boost/unordered/detail/util.hpp b/3rdParty/Boost/src/boost/unordered/detail/util.hpp index 989883e..a901477 100644 --- a/3rdParty/Boost/src/boost/unordered/detail/util.hpp +++ b/3rdParty/Boost/src/boost/unordered/detail/util.hpp @@ -1,39 +1,62 @@ // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. -// Copyright (C) 2005-2009 Daniel James +// Copyright (C) 2005-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) #ifndef BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED #define BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED -#include <cstddef> -#include <utility> -#include <algorithm> -#include <boost/limits.hpp> +#if defined(_MSC_VER) && (_MSC_VER >= 1020) +# pragma once +#endif + +#include <boost/type_traits/is_convertible.hpp> +#include <boost/type_traits/is_empty.hpp> #include <boost/iterator/iterator_categories.hpp> +#include <boost/utility/enable_if.hpp> +#include <boost/detail/select_type.hpp> +#include <boost/move/move.hpp> #include <boost/preprocessor/seq/size.hpp> #include <boost/preprocessor/seq/enum.hpp> -#include <boost/unordered/detail/fwd.hpp> +#include <boost/swap.hpp> -namespace boost { namespace unordered_detail { +namespace boost { namespace unordered { namespace detail { - //////////////////////////////////////////////////////////////////////////// - // convert double to std::size_t + static const float minimum_max_load_factor = 1e-3f; + static const std::size_t default_bucket_count = 11; + struct move_tag {}; + struct empty_emplace {}; - inline std::size_t double_to_size_t(double f) - { - return f >= static_cast<double>( - (std::numeric_limits<std::size_t>::max)()) ? - (std::numeric_limits<std::size_t>::max)() : - static_cast<std::size_t>(f); - } + //////////////////////////////////////////////////////////////////////////// + // iterator SFINAE + + template <typename I> + struct is_forward : + boost::is_convertible< + typename boost::iterator_traversal<I>::type, + boost::forward_traversal_tag> + {}; + + template <typename I, typename ReturnType> + struct enable_if_forward : + boost::enable_if_c< + boost::unordered::detail::is_forward<I>::value, + ReturnType> + {}; + + template <typename I, typename ReturnType> + struct disable_if_forward : + boost::disable_if_c< + boost::unordered::detail::is_forward<I>::value, + ReturnType> + {}; //////////////////////////////////////////////////////////////////////////// // primes #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) \ @@ -93,239 +116,145 @@ namespace boost { namespace unordered_detail { } //////////////////////////////////////////////////////////////////////////// - // pair_cast - because some libraries don't have the full pair constructors. - - template <class Dst1, class Dst2, class Src1, class Src2> - inline std::pair<Dst1, Dst2> pair_cast(std::pair<Src1, Src2> const& x) - { - return std::pair<Dst1, Dst2>(Dst1(x.first), Dst2(x.second)); - } - - //////////////////////////////////////////////////////////////////////////// // insert_size/initial_size #if !defined(BOOST_NO_STD_DISTANCE) + using ::std::distance; + #else + template <class ForwardIterator> inline std::size_t distance(ForwardIterator i, ForwardIterator j) { std::size_t x; std::distance(i, j, x); return x; } + #endif template <class I> - inline std::size_t insert_size(I i, I j, boost::forward_traversal_tag) + inline typename + boost::unordered::detail::enable_if_forward<I, std::size_t>::type + insert_size(I i, I j) { return std::distance(i, j); } template <class I> - inline std::size_t insert_size(I, I, boost::incrementable_traversal_tag) + inline typename + boost::unordered::detail::disable_if_forward<I, std::size_t>::type + insert_size(I, I) { return 1; } template <class I> - inline std::size_t insert_size(I i, I j) - { - BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type - iterator_traversal_tag; - return insert_size(i, j, iterator_traversal_tag); - } - - template <class I> inline std::size_t initial_size(I i, I j, - std::size_t num_buckets = boost::unordered_detail::default_bucket_count) + std::size_t num_buckets = + boost::unordered::detail::default_bucket_count) { - return (std::max)(static_cast<std::size_t>(insert_size(i, j)) + 1, + // TODO: Why +1? + return (std::max)( + boost::unordered::detail::insert_size(i, j) + 1, num_buckets); } //////////////////////////////////////////////////////////////////////////// - // Node Constructors + // compressed -#if defined(BOOST_UNORDERED_STD_FORWARD) - - template <class T, class... Args> - inline void construct_impl(T*, void* address, Args&&... args) + template <typename T, int Index> + struct compressed_base : private T { - new(address) T(std::forward<Args>(args)...); - } + compressed_base(T const& x) : T(x) {} + compressed_base(T& x, move_tag) : T(boost::move(x)) {} -#if defined(BOOST_UNORDERED_CPP0X_PAIR) - template <class First, class Second, class Key, class Arg0, class... Args> - inline void construct_impl(std::pair<First, Second>*, void* address, - Key&& k, Arg0&& arg0, Args&&... args) - ) + T& get() { return *this; } + T const& get() const { return *this; } + }; + + template <typename T, int Index> + struct uncompressed_base { - new(address) std::pair<First, Second>(k, - Second(arg0, std::forward<Args>(args)...); - } -#endif - -#else - -#define BOOST_UNORDERED_CONSTRUCT_IMPL(z, num_params, _) \ - template < \ - class T, \ - BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \ - > \ - inline void construct_impl( \ - T*, void* address, \ - BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \ - ) \ - { \ - new(address) T( \ - BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \ - } \ - \ - template <class First, class Second, class Key, \ - BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \ - > \ - inline void construct_impl( \ - std::pair<First, Second>*, void* address, \ - Key const& k, BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \ - { \ - new(address) std::pair<First, Second>(k, \ - Second(BOOST_UNORDERED_CALL_PARAMS(z, num_params))); \ - } + uncompressed_base(T const& x) : value_(x) {} + uncompressed_base(T& x, move_tag) : value_(boost::move(x)) {} - BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, - BOOST_UNORDERED_CONSTRUCT_IMPL, _) - -#undef BOOST_UNORDERED_CONSTRUCT_IMPL -#endif - - // hash_node_constructor - // - // Used to construct nodes in an exception safe manner. - - template <class Alloc, class Grouped> - class hash_node_constructor + T& get() { return value_; } + T const& get() const { return value_; } + private: + T value_; + }; + + template <typename T, int Index> + struct generate_base + : boost::detail::if_true< + boost::is_empty<T>::value + >:: BOOST_NESTED_TEMPLATE then< + boost::unordered::detail::compressed_base<T, Index>, + boost::unordered::detail::uncompressed_base<T, Index> + > + {}; + + template <typename T1, typename T2> + struct compressed + : private boost::unordered::detail::generate_base<T1, 1>::type, + private boost::unordered::detail::generate_base<T2, 2>::type { - typedef hash_buckets<Alloc, Grouped> buckets; - typedef BOOST_DEDUCED_TYPENAME buckets::node node; - typedef BOOST_DEDUCED_TYPENAME buckets::real_node_ptr real_node_ptr; - typedef BOOST_DEDUCED_TYPENAME buckets::value_type value_type; - - buckets& buckets_; - real_node_ptr node_; - bool node_constructed_; - bool value_constructed_; - - public: - - hash_node_constructor(buckets& m) : - buckets_(m), - node_(), - node_constructed_(false), - value_constructed_(false) - { + typedef typename generate_base<T1, 1>::type base1; + typedef typename generate_base<T2, 2>::type base2; + + typedef T1 first_type; + typedef T2 second_type; + + first_type& first() { + return static_cast<base1*>(this)->get(); } - ~hash_node_constructor(); - void construct_preamble(); + first_type const& first() const { + return static_cast<base1 const*>(this)->get(); + } -#if defined(BOOST_UNORDERED_STD_FORWARD) - template <class... Args> - void construct(Args&&... args) - { - construct_preamble(); - construct_impl((value_type*) 0, node_->address(), - std::forward<Args>(args)...); - value_constructed_ = true; + second_type& second() { + return static_cast<base2*>(this)->get(); } -#else -#define BOOST_UNORDERED_CONSTRUCT(z, num_params, _) \ - template < \ - BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \ - > \ - void construct( \ - BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \ - ) \ - { \ - construct_preamble(); \ - construct_impl( \ - (value_type*) 0, node_->address(), \ - BOOST_UNORDERED_CALL_PARAMS(z, num_params) \ - ); \ - value_constructed_ = true; \ + second_type const& second() const { + return static_cast<base2 const*>(this)->get(); } - BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, - BOOST_UNORDERED_CONSTRUCT, _) + template <typename First, typename Second> + compressed(First const& x1, Second const& x2) + : base1(x1), base2(x2) {} -#undef BOOST_UNORDERED_CONSTRUCT + compressed(compressed const& x) + : base1(x.first()), base2(x.second()) {} -#endif - template <class K, class M> - void construct_pair(K const& k, M*) + compressed(compressed& x, move_tag m) + : base1(x.first(), m), base2(x.second(), m) {} + + void assign(compressed const& x) { - construct_preamble(); - new(node_->address()) value_type(k, M()); - value_constructed_ = true; + first() = x.first(); + second() = x.second(); } - value_type& value() const + void move_assign(compressed& x) { - BOOST_ASSERT(node_); - return node_->value(); + first() = boost::move(x.first()); + second() = boost::move(x.second()); } - - // no throw - BOOST_DEDUCED_TYPENAME buckets::node_ptr release() + + void swap(compressed& x) { - real_node_ptr p = node_; - node_ = real_node_ptr(); - // node_ptr cast - return buckets_.bucket_alloc().address(*p); + boost::swap(first(), x.first()); + boost::swap(second(), x.second()); } private: - hash_node_constructor(hash_node_constructor const&); - hash_node_constructor& operator=(hash_node_constructor const&); + // Prevent assignment just to make use of assign or + // move_assign explicit. + compressed& operator=(compressed const&); }; - - // hash_node_constructor - - template <class Alloc, class Grouped> - inline hash_node_constructor<Alloc, Grouped>::~hash_node_constructor() - { - if (node_) { - if (value_constructed_) { -#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613)) - struct dummy { hash_node<Alloc, Grouped> x; }; -#endif - boost::unordered_detail::destroy(node_->value_ptr()); - } - - if (node_constructed_) - buckets_.node_alloc().destroy(node_); - - buckets_.node_alloc().deallocate(node_, 1); - } - } - - template <class Alloc, class Grouped> - inline void hash_node_constructor<Alloc, Grouped>::construct_preamble() - { - if(!node_) { - node_constructed_ = false; - value_constructed_ = false; - - node_ = buckets_.node_alloc().allocate(1); - buckets_.node_alloc().construct(node_, node()); - node_constructed_ = true; - } - else { - BOOST_ASSERT(node_constructed_ && value_constructed_); - boost::unordered_detail::destroy(node_->value_ptr()); - value_constructed_ = false; - } - } -}} +}}} #endif diff --git a/3rdParty/Boost/src/boost/unordered/unordered_map.hpp b/3rdParty/Boost/src/boost/unordered/unordered_map.hpp index 86a6fc6..d606739 100644 --- a/3rdParty/Boost/src/boost/unordered/unordered_map.hpp +++ b/3rdParty/Boost/src/boost/unordered/unordered_map.hpp @@ -1,6 +1,6 @@ // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. -// Copyright (C) 2005-2009 Daniel James. +// Copyright (C) 2005-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) @@ -14,16 +14,13 @@ #endif #include <boost/unordered/unordered_map_fwd.hpp> -#include <boost/functional/hash.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_RVALUE_REFERENCES) -#include <boost/unordered/detail/move.hpp> -#endif - -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) #include <initializer_list> #endif @@ -38,10 +35,17 @@ namespace boost { +namespace unordered +{ template <class K, class T, class H, class P, class A> class unordered_map { +#if defined(BOOST_UNORDERED_USE_MOVE) + BOOST_COPYABLE_AND_MOVABLE(unordered_map) +#endif + public: + typedef K key_type; typedef std::pair<const K, T> value_type; typedef T mapped_type; @@ -49,179 +53,129 @@ namespace boost typedef P key_equal; typedef A allocator_type; -#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582) private: -#endif - - typedef BOOST_DEDUCED_TYPENAME - boost::unordered_detail::rebind_wrap< - allocator_type, value_type>::type - value_allocator; - typedef boost::unordered_detail::map<K, H, P, - value_allocator> types; - typedef BOOST_DEDUCED_TYPENAME types::impl table; - - typedef BOOST_DEDUCED_TYPENAME types::iterator_base iterator_base; + typedef boost::unordered::detail::map<A, K, T, H, P> types; + typedef typename types::traits allocator_traits; + typedef typename types::table table; public: - typedef BOOST_DEDUCED_TYPENAME - value_allocator::pointer pointer; - typedef BOOST_DEDUCED_TYPENAME - value_allocator::const_pointer const_pointer; - typedef BOOST_DEDUCED_TYPENAME - value_allocator::reference reference; - typedef BOOST_DEDUCED_TYPENAME - value_allocator::const_reference const_reference; + typedef typename allocator_traits::pointer pointer; + typedef typename allocator_traits::const_pointer const_pointer; + + typedef value_type& reference; + typedef value_type const& const_reference; typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; - typedef boost::unordered_detail::hash_const_local_iterator< - value_allocator, boost::unordered_detail::ungrouped> - const_local_iterator; - typedef boost::unordered_detail::hash_local_iterator< - value_allocator, boost::unordered_detail::ungrouped> - local_iterator; - typedef boost::unordered_detail::hash_const_iterator< - value_allocator, boost::unordered_detail::ungrouped> - const_iterator; - typedef boost::unordered_detail::hash_iterator< - value_allocator, boost::unordered_detail::ungrouped> - iterator; + typedef typename table::cl_iterator const_local_iterator; + typedef typename table::l_iterator local_iterator; + typedef typename table::c_iterator const_iterator; + typedef typename table::iterator iterator; -#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582) private: -#endif table table_; - - BOOST_DEDUCED_TYPENAME types::iterator_base const& - get(const_iterator const& it) - { - return boost::unordered_detail::iterator_access::get(it); - } public: - // construct/destroy/copy + // constructors explicit unordered_map( - size_type n = boost::unordered_detail::default_bucket_count, - const hasher &hf = hasher(), - const key_equal &eql = key_equal(), - const allocator_type &a = allocator_type()) - : table_(n, hf, eql, a) - { - } + size_type = boost::unordered::detail::default_bucket_count, + const hasher& = hasher(), + const key_equal& = key_equal(), + const allocator_type& = allocator_type()); - explicit unordered_map(allocator_type const& a) - : table_(boost::unordered_detail::default_bucket_count, - hasher(), key_equal(), a) - { - } - - unordered_map(unordered_map const& other, allocator_type const& a) - : table_(other.table_, a) - { - } + explicit unordered_map(allocator_type const&); template <class InputIt> - unordered_map(InputIt f, InputIt l) - : table_(boost::unordered_detail::initial_size(f, l), - hasher(), key_equal(), allocator_type()) - { - table_.insert_range(f, l); - } + unordered_map(InputIt, InputIt); template <class InputIt> - unordered_map(InputIt f, InputIt l, - size_type n, - const hasher &hf = hasher(), - const key_equal &eql = key_equal()) - : table_(boost::unordered_detail::initial_size(f, l, n), - hf, eql, allocator_type()) - { - table_.insert_range(f, l); - } + unordered_map( + InputIt, InputIt, + size_type, + const hasher& = hasher(), + const key_equal& = key_equal()); template <class InputIt> - unordered_map(InputIt f, InputIt l, - size_type n, - const hasher &hf, - const key_equal &eql, - const allocator_type &a) - : table_(boost::unordered_detail::initial_size(f, l, n), hf, eql, a) - { - table_.insert_range(f, l); - } + unordered_map( + InputIt, InputIt, + size_type, + const hasher&, + const key_equal&, + const allocator_type&); - ~unordered_map() {} + // copy/move constructors -#if !defined(BOOST_NO_RVALUE_REFERENCES) - unordered_map(unordered_map const& other) - : table_(other.table_) + unordered_map(unordered_map const&); + + unordered_map(unordered_map const&, allocator_type const&); + +#if defined(BOOST_UNORDERED_USE_MOVE) + unordered_map(BOOST_RV_REF(unordered_map) other) + : table_(other.table_, boost::unordered::detail::move_tag()) { } - +#elif !defined(BOOST_NO_RVALUE_REFERENCES) unordered_map(unordered_map&& other) - : table_(other.table_, boost::unordered_detail::move_tag()) + : table_(other.table_, boost::unordered::detail::move_tag()) { } +#endif - unordered_map(unordered_map&& other, allocator_type const& a) - : table_(other.table_, a, boost::unordered_detail::move_tag()) - { - } +#if !defined(BOOST_NO_RVALUE_REFERENCES) + unordered_map(unordered_map&&, allocator_type const&); +#endif - unordered_map& operator=(unordered_map const& x) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + unordered_map( + std::initializer_list<value_type>, + size_type = boost::unordered::detail::default_bucket_count, + const hasher& = hasher(), + const key_equal&l = key_equal(), + const allocator_type& = allocator_type()); +#endif + + // Destructor + + ~unordered_map(); + + // Assign + +#if defined(BOOST_UNORDERED_USE_MOVE) + unordered_map& operator=(BOOST_COPY_ASSIGN_REF(unordered_map) x) { - table_ = x.table_; + table_.assign(x.table_); return *this; } - unordered_map& operator=(unordered_map&& x) + unordered_map& operator=(BOOST_RV_REF(unordered_map) x) { - table_.move(x.table_); + table_.move_assign(x.table_); return *this; } #else - unordered_map(boost::unordered_detail::move_from< - unordered_map<K, T, H, P, A> - > other) - : table_(other.source.table_, boost::unordered_detail::move_tag()) + unordered_map& operator=(unordered_map const& x) { + table_.assign(x.table_); + return *this; } -#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0593) - unordered_map& operator=(unordered_map x) +#if !defined(BOOST_NO_RVALUE_REFERENCES) + unordered_map& operator=(unordered_map&& x) { - table_.move(x.table_); + table_.move_assign(x.table_); return *this; } #endif #endif -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) - unordered_map(std::initializer_list<value_type> list, - size_type n = boost::unordered_detail::default_bucket_count, - const hasher &hf = hasher(), - const key_equal &eql = key_equal(), - const allocator_type &a = allocator_type()) - : table_(boost::unordered_detail::initial_size( - list.begin(), list.end(), n), - hf, eql, a) - { - table_.insert_range(list.begin(), list.end()); - } - - unordered_map& operator=(std::initializer_list<value_type> list) - { - table_.clear(); - table_.insert_range(list.begin(), list.end()); - return *this; - } +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + unordered_map& operator=(std::initializer_list<value_type>); #endif allocator_type get_allocator() const @@ -241,244 +195,257 @@ namespace boost return table_.size_; } - size_type max_size() const - { - return table_.max_size(); - } + size_type max_size() const; // iterators iterator begin() { - return iterator(table_.begin()); + return table_.begin(); } const_iterator begin() const { - return const_iterator(table_.begin()); + return table_.begin(); } iterator end() { - return iterator(table_.end()); + return iterator(); } const_iterator end() const { - return const_iterator(table_.end()); + return const_iterator(); } const_iterator cbegin() const { - return const_iterator(table_.begin()); + return table_.begin(); } const_iterator cend() const { - return const_iterator(table_.end()); + return const_iterator(); } - // modifiers + // emplace -#if defined(BOOST_UNORDERED_STD_FORWARD) +#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 boost::unordered_detail::pair_cast<iterator, bool>( - table_.emplace(std::forward<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 iterator(table_.emplace(std::forward<Args>(args)...).first); + return table_.emplace(boost::forward<Args>(args)...).first; } #else - #if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100)) - std::pair<iterator, bool> emplace(value_type const& v = value_type()) - { - return boost::unordered_detail::pair_cast<iterator, bool>( - table_.emplace(v)); - } - - iterator emplace_hint(const_iterator, - value_type const& v = value_type()) - { - return iterator(table_.emplace(v).first); - } - #endif - -#define BOOST_UNORDERED_EMPLACE(z, n, _) \ - template < \ - BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \ - > \ - std::pair<iterator, bool> emplace( \ - BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \ - ) \ - { \ - return boost::unordered_detail::pair_cast<iterator, bool>( \ - table_.emplace( \ - BOOST_UNORDERED_CALL_PARAMS(z, n) \ - )); \ - } \ - \ - template < \ - BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \ - > \ - iterator emplace_hint(const_iterator, \ - BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \ - ) \ - { \ - return iterator(table_.emplace( \ - BOOST_UNORDERED_CALL_PARAMS(z, n)).first); \ - } - - BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, - BOOST_UNORDERED_EMPLACE, _) +#if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100)) -#undef BOOST_UNORDERED_EMPLACE + // 0 argument emplace requires special treatment in case + // the container is instantiated with a value type that + // doesn't have a default constructor. -#endif - - std::pair<iterator, bool> insert(const value_type& obj) + std::pair<iterator, bool> emplace( + boost::unordered::detail::empty_emplace + = boost::unordered::detail::empty_emplace(), + value_type v = value_type()) { - return boost::unordered_detail::pair_cast<iterator, bool>( - table_.emplace(obj)); + return this->emplace(boost::move(v)); } - iterator insert(const_iterator, const value_type& obj) - { - return iterator(table_.emplace(obj).first); - } - - template <class InputIt> - void insert(InputIt first, InputIt last) + iterator emplace_hint(const_iterator hint, + boost::unordered::detail::empty_emplace + = boost::unordered::detail::empty_emplace(), + value_type v = value_type() + ) { - table_.insert_range(first, last); + return this->emplace_hint(hint, boost::move(v)); } -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) - void insert(std::initializer_list<value_type> list) - { - table_.insert_range(list.begin(), list.end()); - } #endif - iterator erase(const_iterator position) + template <typename A0> + std::pair<iterator, bool> emplace(BOOST_FWD_REF(A0) a0) { - return iterator(table_.erase_return_iterator(get(position))); + return table_.emplace( + boost::unordered::detail::create_emplace_args( + boost::forward<A0>(a0)) + ); } - size_type erase(const key_type& k) + template <typename A0> + iterator emplace_hint(const_iterator, BOOST_FWD_REF(A0) a0) { - return table_.erase_key(k); + return table_.emplace( + boost::unordered::detail::create_emplace_args( + boost::forward<A0>(a0)) + ).first; } - iterator erase(const_iterator first, const_iterator last) + template <typename A0, typename A1> + std::pair<iterator, bool> emplace( + BOOST_FWD_REF(A0) a0, + BOOST_FWD_REF(A1) a1) { - return iterator(table_.erase_range(get(first), get(last))); + return table_.emplace( + boost::unordered::detail::create_emplace_args( + boost::forward<A0>(a0), + boost::forward<A1>(a1)) + ); } - void quick_erase(const_iterator position) + template <typename A0, typename A1> + iterator emplace_hint(const_iterator, + BOOST_FWD_REF(A0) a0, + BOOST_FWD_REF(A1) a1) { - table_.erase(get(position)); + return table_.emplace( + boost::unordered::detail::create_emplace_args( + boost::forward<A0>(a0), + boost::forward<A1>(a1)) + ).first; } - void erase_return_void(const_iterator position) + template <typename A0, typename A1, typename A2> + std::pair<iterator, bool> emplace( + BOOST_FWD_REF(A0) a0, + BOOST_FWD_REF(A1) a1, + BOOST_FWD_REF(A2) a2) { - table_.erase(get(position)); + return table_.emplace( + boost::unordered::detail::create_emplace_args( + boost::forward<A0>(a0), + boost::forward<A1>(a1), + boost::forward<A2>(a2)) + ); } - void clear() - { - table_.clear(); - } + template <typename A0, typename A1, typename A2> + iterator emplace_hint(const_iterator, + BOOST_FWD_REF(A0) a0, + BOOST_FWD_REF(A1) a1, + BOOST_FWD_REF(A2) a2) + { + return table_.emplace( + boost::unordered::detail::create_emplace_args( + boost::forward<A0>(a0), + boost::forward<A1>(a1), + boost::forward<A2>(a2)) + ).first; + } + +#define BOOST_UNORDERED_EMPLACE(z, n, _) \ + template < \ + BOOST_PP_ENUM_PARAMS_Z(z, n, typename A) \ + > \ + std::pair<iterator, bool> emplace( \ + BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a) \ + ) \ + { \ + return table_.emplace( \ + boost::unordered::detail::create_emplace_args( \ + BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, \ + a) \ + )); \ + } \ + \ + template < \ + BOOST_PP_ENUM_PARAMS_Z(z, n, typename A) \ + > \ + iterator emplace_hint( \ + const_iterator, \ + BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a) \ + ) \ + { \ + return table_.emplace( \ + boost::unordered::detail::create_emplace_args( \ + BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, \ + a) \ + )).first; \ + } - void swap(unordered_map& other) - { - table_.swap(other.table_); - } + BOOST_PP_REPEAT_FROM_TO(4, BOOST_UNORDERED_EMPLACE_LIMIT, + BOOST_UNORDERED_EMPLACE, _) - // observers +#undef BOOST_UNORDERED_EMPLACE - hasher hash_function() const - { - return table_.hash_function(); - } +#endif - key_equal key_eq() const + std::pair<iterator, bool> insert(value_type const& x) { - return table_.key_eq(); + return this->emplace(x); } - mapped_type& operator[](const key_type &k) + std::pair<iterator, bool> insert(BOOST_RV_REF(value_type) x) { - return table_[k].second; + return this->emplace(boost::move(x)); } - mapped_type& at(const key_type& k) + iterator insert(const_iterator hint, value_type const& x) { - return table_.at(k).second; + return this->emplace_hint(hint, x); } - mapped_type const& at(const key_type& k) const + iterator insert(const_iterator hint, BOOST_RV_REF(value_type) x) { - return table_.at(k).second; + return this->emplace_hint(hint, boost::move(x)); } - // lookup + template <class InputIt> void insert(InputIt, InputIt); - iterator find(const key_type& k) - { - return iterator(table_.find(k)); - } +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + void insert(std::initializer_list<value_type>); +#endif - const_iterator find(const key_type& k) const - { - return const_iterator(table_.find(k)); - } + iterator erase(const_iterator); + size_type erase(const key_type&); + iterator erase(const_iterator, const_iterator); + void quick_erase(const_iterator it) { erase(it); } + void erase_return_void(const_iterator it) { erase(it); } + + void clear(); + void swap(unordered_map&); + + // observers + + hasher hash_function() const; + key_equal key_eq() const; + + mapped_type& operator[](const key_type&); + mapped_type& at(const key_type&); + mapped_type const& at(const key_type&) const; + + // lookup + + iterator find(const key_type&); + const_iterator find(const key_type&) const; template <class CompatibleKey, class CompatibleHash, class CompatiblePredicate> iterator find( - CompatibleKey const& k, - CompatibleHash const& hash, - CompatiblePredicate const& eq) - { - return iterator(table_.find(k, hash, eq)); - } + CompatibleKey const&, + CompatibleHash const&, + CompatiblePredicate const&); template <class CompatibleKey, class CompatibleHash, class CompatiblePredicate> const_iterator find( - CompatibleKey const& k, - CompatibleHash const& hash, - CompatiblePredicate const& eq) const - { - return iterator(table_.find(k, hash, eq)); - } + CompatibleKey const&, + CompatibleHash const&, + CompatiblePredicate const&) const; - size_type count(const key_type& k) const - { - return table_.count(k); - } + size_type count(const key_type&) const; std::pair<iterator, iterator> - equal_range(const key_type& k) - { - return boost::unordered_detail::pair_cast< - iterator, iterator>( - table_.equal_range(k)); - } - + equal_range(const key_type&); std::pair<const_iterator, const_iterator> - equal_range(const key_type& k) const - { - return boost::unordered_detail::pair_cast< - const_iterator, const_iterator>( - table_.equal_range(k)); - } + equal_range(const key_type&) const; // bucket interface @@ -492,24 +459,24 @@ namespace boost return table_.max_bucket_count(); } - size_type bucket_size(size_type n) const - { - return table_.bucket_size(n); - } + size_type bucket_size(size_type) const; size_type bucket(const key_type& k) const { - return table_.bucket_index(k); + return table::to_bucket(table_.bucket_count_, + table_.hash(k)); } local_iterator begin(size_type n) { - return local_iterator(table_.bucket_begin(n)); + return local_iterator( + table_.begin(n), n, table_.bucket_count_); } const_local_iterator begin(size_type n) const { - return const_local_iterator(table_.bucket_begin(n)); + return const_local_iterator( + table_.begin(n), n, table_.bucket_count_); } local_iterator end(size_type) @@ -524,7 +491,8 @@ namespace boost const_local_iterator cbegin(size_type n) const { - return const_local_iterator(table_.bucket_begin(n)); + return const_local_iterator( + table_.begin(n), n, table_.bucket_count_); } const_local_iterator cend(size_type) const @@ -534,67 +502,30 @@ namespace boost // hash policy - float load_factor() const - { - return table_.load_factor(); - } - float max_load_factor() const { return table_.mlf_; } - void max_load_factor(float m) - { - table_.max_load_factor(m); - } + float load_factor() const; + void max_load_factor(float); + void rehash(size_type); + void reserve(size_type); - void rehash(size_type n) - { - table_.rehash(n); - } - #if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582) - friend bool operator==<K, T, H, P, A>( - unordered_map const&, unordered_map const&); - friend bool operator!=<K, T, H, P, A>( - unordered_map const&, unordered_map const&); + friend bool operator==<K,T,H,P,A>( + unordered_map const&, unordered_map const&); + friend bool operator!=<K,T,H,P,A>( + unordered_map const&, unordered_map const&); #endif }; // class template unordered_map 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) - { -#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613)) - struct dummy { unordered_map<K,T,H,P,A> x; }; -#endif - return m1.table_.equals(m2.table_); - } - - 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) - { -#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613)) - struct dummy { unordered_map<K,T,H,P,A> x; }; -#endif - return !m1.table_.equals(m2.table_); - } - - template <class K, class T, class H, class P, class A> - inline void swap(unordered_map<K, T, H, P, A> &m1, - unordered_map<K, T, H, P, A> &m2) - { -#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613)) - struct dummy { unordered_map<K,T,H,P,A> x; }; -#endif - m1.swap(m2); - } - - template <class K, class T, class H, class P, class A> class unordered_multimap { +#if defined(BOOST_UNORDERED_USE_MOVE) + BOOST_COPYABLE_AND_MOVABLE(unordered_multimap) +#endif public: typedef K key_type; @@ -604,180 +535,130 @@ namespace boost typedef P key_equal; typedef A allocator_type; -#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582) private: -#endif - - typedef BOOST_DEDUCED_TYPENAME - boost::unordered_detail::rebind_wrap< - allocator_type, value_type>::type - value_allocator; - typedef boost::unordered_detail::multimap<K, H, P, - value_allocator> types; - typedef BOOST_DEDUCED_TYPENAME types::impl table; - - typedef BOOST_DEDUCED_TYPENAME types::iterator_base iterator_base; + typedef boost::unordered::detail::multimap<A, K, T, H, P> types; + typedef typename types::traits allocator_traits; + typedef typename types::table table; public: - typedef BOOST_DEDUCED_TYPENAME - value_allocator::pointer pointer; - typedef BOOST_DEDUCED_TYPENAME - value_allocator::const_pointer const_pointer; - typedef BOOST_DEDUCED_TYPENAME - value_allocator::reference reference; - typedef BOOST_DEDUCED_TYPENAME - value_allocator::const_reference const_reference; + typedef typename allocator_traits::pointer pointer; + typedef typename allocator_traits::const_pointer const_pointer; + + typedef value_type& reference; + typedef value_type const& const_reference; typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; - typedef boost::unordered_detail::hash_const_local_iterator< - value_allocator, boost::unordered_detail::grouped> - const_local_iterator; - typedef boost::unordered_detail::hash_local_iterator< - value_allocator, boost::unordered_detail::grouped> - local_iterator; - typedef boost::unordered_detail::hash_const_iterator< - value_allocator, boost::unordered_detail::grouped> - const_iterator; - typedef boost::unordered_detail::hash_iterator< - value_allocator, boost::unordered_detail::grouped> - iterator; + typedef typename table::cl_iterator const_local_iterator; + typedef typename table::l_iterator local_iterator; + typedef typename table::c_iterator const_iterator; + typedef typename table::iterator iterator; -#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582) private: -#endif table table_; - BOOST_DEDUCED_TYPENAME types::iterator_base const& - get(const_iterator const& it) - { - return boost::unordered_detail::iterator_access::get(it); - } - public: - // construct/destroy/copy + // constructors explicit unordered_multimap( - size_type n = boost::unordered_detail::default_bucket_count, - const hasher &hf = hasher(), - const key_equal &eql = key_equal(), - const allocator_type &a = allocator_type()) - : table_(n, hf, eql, a) - { - } + size_type = boost::unordered::detail::default_bucket_count, + const hasher& = hasher(), + const key_equal& = key_equal(), + const allocator_type& = allocator_type()); - explicit unordered_multimap(allocator_type const& a) - : table_(boost::unordered_detail::default_bucket_count, - hasher(), key_equal(), a) - { - } - - unordered_multimap(unordered_multimap const& other, - allocator_type const& a) - : table_(other.table_, a) - { - } + explicit unordered_multimap(allocator_type const&); template <class InputIt> - unordered_multimap(InputIt f, InputIt l) - : table_(boost::unordered_detail::initial_size(f, l), - hasher(), key_equal(), allocator_type()) - { - table_.insert_range(f, l); - } + unordered_multimap(InputIt, InputIt); template <class InputIt> - unordered_multimap(InputIt f, InputIt l, - size_type n, - const hasher &hf = hasher(), - const key_equal &eql = key_equal()) - : table_(boost::unordered_detail::initial_size(f, l, n), - hf, eql, allocator_type()) - { - table_.insert_range(f, l); - } + unordered_multimap( + InputIt, InputIt, + size_type, + const hasher& = hasher(), + const key_equal& = key_equal()); template <class InputIt> - unordered_multimap(InputIt f, InputIt l, - size_type n, - const hasher &hf, - const key_equal &eql, - const allocator_type &a) - : table_(boost::unordered_detail::initial_size(f, l, n), hf, eql, a) - { - table_.insert_range(f, l); - } + unordered_multimap( + InputIt, InputIt, + size_type, + const hasher&, + const key_equal&, + const allocator_type&); - ~unordered_multimap() {} + // copy/move constructors -#if !defined(BOOST_NO_RVALUE_REFERENCES) - unordered_multimap(unordered_multimap const& other) - : table_(other.table_) + unordered_multimap(unordered_multimap const&); + + unordered_multimap(unordered_multimap const&, allocator_type const&); + +#if defined(BOOST_UNORDERED_USE_MOVE) + unordered_multimap(BOOST_RV_REF(unordered_multimap) other) + : table_(other.table_, boost::unordered::detail::move_tag()) { } - +#elif !defined(BOOST_NO_RVALUE_REFERENCES) unordered_multimap(unordered_multimap&& other) - : table_(other.table_, boost::unordered_detail::move_tag()) + : table_(other.table_, boost::unordered::detail::move_tag()) { } +#endif - unordered_multimap(unordered_multimap&& other, allocator_type const& a) - : table_(other.table_, a, boost::unordered_detail::move_tag()) - { - } +#if !defined(BOOST_NO_RVALUE_REFERENCES) + unordered_multimap(unordered_multimap&&, allocator_type const&); +#endif - unordered_multimap& operator=(unordered_multimap const& x) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + unordered_multimap( + std::initializer_list<value_type>, + size_type = boost::unordered::detail::default_bucket_count, + const hasher& = hasher(), + const key_equal&l = key_equal(), + const allocator_type& = allocator_type()); +#endif + + // Destructor + + ~unordered_multimap(); + + // Assign + +#if defined(BOOST_UNORDERED_USE_MOVE) + unordered_multimap& operator=( + BOOST_COPY_ASSIGN_REF(unordered_multimap) x) { - table_ = x.table_; + table_.assign(x.table_); return *this; } - unordered_multimap& operator=(unordered_multimap&& x) + unordered_multimap& operator=(BOOST_RV_REF(unordered_multimap) x) { - table_.move(x.table_); + table_.move_assign(x.table_); return *this; } #else - unordered_multimap(boost::unordered_detail::move_from< - unordered_multimap<K, T, H, P, A> - > other) - : table_(other.source.table_, boost::unordered_detail::move_tag()) + unordered_multimap& operator=(unordered_multimap const& x) { + table_.assign(x.table_); + return *this; } -#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0593) - unordered_multimap& operator=(unordered_multimap x) +#if !defined(BOOST_NO_RVALUE_REFERENCES) + unordered_multimap& operator=(unordered_multimap&& x) { - table_.move(x.table_); + table_.move_assign(x.table_); return *this; } #endif #endif -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) - unordered_multimap(std::initializer_list<value_type> list, - size_type n = boost::unordered_detail::default_bucket_count, - const hasher &hf = hasher(), - const key_equal &eql = key_equal(), - const allocator_type &a = allocator_type()) - : table_(boost::unordered_detail::initial_size( - list.begin(), list.end(), n), - hf, eql, a) - { - table_.insert_range(list.begin(), list.end()); - } - - unordered_multimap& operator=(std::initializer_list<value_type> list) - { - table_.clear(); - table_.insert_range(list.begin(), list.end()); - return *this; - } +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + unordered_multimap& operator=(std::initializer_list<value_type>); #endif allocator_type get_allocator() const @@ -797,227 +678,253 @@ namespace boost return table_.size_; } - size_type max_size() const - { - return table_.max_size(); - } + size_type max_size() const; // iterators iterator begin() { - return iterator(table_.begin()); + return table_.begin(); } const_iterator begin() const { - return const_iterator(table_.begin()); + return table_.begin(); } iterator end() { - return iterator(table_.end()); + return iterator(); } const_iterator end() const { - return const_iterator(table_.end()); + return const_iterator(); } const_iterator cbegin() const { - return const_iterator(table_.begin()); + return table_.begin(); } const_iterator cend() const { - return const_iterator(table_.end()); + return const_iterator(); } - // modifiers + // emplace -#if defined(BOOST_UNORDERED_STD_FORWARD) +#if !defined(BOOST_NO_VARIADIC_TEMPLATES) template <class... Args> - iterator emplace(Args&&... args) + iterator emplace(BOOST_FWD_REF(Args)... args) { - return iterator(table_.emplace(std::forward<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 iterator(table_.emplace(std::forward<Args>(args)...)); + return table_.emplace(boost::forward<Args>(args)...); } #else - #if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100)) - iterator emplace(value_type const& v = value_type()) - { - return iterator(table_.emplace(v)); - } - - iterator emplace_hint(const_iterator, - value_type const& v = value_type()) - { - return iterator(table_.emplace(v)); - } - #endif - -#define BOOST_UNORDERED_EMPLACE(z, n, _) \ - template < \ - BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \ - > \ - iterator emplace( \ - BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \ - ) \ - { \ - return iterator( \ - table_.emplace( \ - BOOST_UNORDERED_CALL_PARAMS(z, n) \ - )); \ - } \ - \ - template < \ - BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \ - > \ - iterator emplace_hint(const_iterator, \ - BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \ - ) \ - { \ - return iterator(table_.emplace( \ - BOOST_UNORDERED_CALL_PARAMS(z, n) \ - )); \ - } +#if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100)) - BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, - BOOST_UNORDERED_EMPLACE, _) + // 0 argument emplace requires special treatment in case + // the container is instantiated with a value type that + // doesn't have a default constructor. -#undef BOOST_UNORDERED_EMPLACE - -#endif - - iterator insert(const value_type& obj) + iterator emplace( + boost::unordered::detail::empty_emplace + = boost::unordered::detail::empty_emplace(), + value_type v = value_type()) { - return iterator(table_.emplace(obj)); + return this->emplace(boost::move(v)); } - iterator insert(const_iterator, const value_type& obj) + iterator emplace_hint(const_iterator hint, + boost::unordered::detail::empty_emplace + = boost::unordered::detail::empty_emplace(), + value_type v = value_type() + ) { - return iterator(table_.emplace(obj)); + return this->emplace_hint(hint, boost::move(v)); } - template <class InputIt> - void insert(InputIt first, InputIt last) +#endif + + template <typename A0> + iterator emplace(BOOST_FWD_REF(A0) a0) { - table_.insert_range(first, last); + return table_.emplace( + boost::unordered::detail::create_emplace_args( + boost::forward<A0>(a0)) + ); } -#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) - void insert(std::initializer_list<value_type> list) + template <typename A0> + iterator emplace_hint(const_iterator, BOOST_FWD_REF(A0) a0) { - table_.insert_range(list.begin(), list.end()); + return table_.emplace( + boost::unordered::detail::create_emplace_args( + boost::forward<A0>(a0)) + ); } -#endif - iterator erase(const_iterator position) + template <typename A0, typename A1> + iterator emplace( + BOOST_FWD_REF(A0) a0, + BOOST_FWD_REF(A1) a1) { - return iterator(table_.erase_return_iterator(get(position))); + return table_.emplace( + boost::unordered::detail::create_emplace_args( + boost::forward<A0>(a0), + boost::forward<A1>(a1)) + ); } - size_type erase(const key_type& k) + template <typename A0, typename A1> + iterator emplace_hint(const_iterator, + BOOST_FWD_REF(A0) a0, + BOOST_FWD_REF(A1) a1) { - return table_.erase_key(k); + return table_.emplace( + boost::unordered::detail::create_emplace_args( + boost::forward<A0>(a0), + boost::forward<A1>(a1)) + ); } - iterator erase(const_iterator first, const_iterator last) + template <typename A0, typename A1, typename A2> + iterator emplace( + BOOST_FWD_REF(A0) a0, + BOOST_FWD_REF(A1) a1, + BOOST_FWD_REF(A2) a2) { - return iterator(table_.erase_range(get(first), get(last))); + return table_.emplace( + boost::unordered::detail::create_emplace_args( + boost::forward<A0>(a0), + boost::forward<A1>(a1), + boost::forward<A2>(a2)) + ); } - void quick_erase(const_iterator position) + template <typename A0, typename A1, typename A2> + iterator emplace_hint(const_iterator, + BOOST_FWD_REF(A0) a0, + BOOST_FWD_REF(A1) a1, + BOOST_FWD_REF(A2) a2) + { + return table_.emplace( + boost::unordered::detail::create_emplace_args( + boost::forward<A0>(a0), + boost::forward<A1>(a1), + boost::forward<A2>(a2)) + ); + } + +#define BOOST_UNORDERED_EMPLACE(z, n, _) \ + template < \ + BOOST_PP_ENUM_PARAMS_Z(z, n, typename A) \ + > \ + iterator emplace( \ + BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a) \ + ) \ + { \ + return table_.emplace( \ + boost::unordered::detail::create_emplace_args( \ + BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, \ + a) \ + )); \ + } \ + \ + template < \ + BOOST_PP_ENUM_PARAMS_Z(z, n, typename A) \ + > \ + iterator emplace_hint( \ + const_iterator, \ + BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a) \ + ) \ + { \ + return table_.emplace( \ + boost::unordered::detail::create_emplace_args( \ + BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, \ + a) \ + )); \ + } + + BOOST_PP_REPEAT_FROM_TO(4, BOOST_UNORDERED_EMPLACE_LIMIT, + BOOST_UNORDERED_EMPLACE, _) + +#undef BOOST_UNORDERED_EMPLACE + +#endif + + iterator insert(value_type const& x) { - table_.erase(get(position)); + return this->emplace(x); } - void erase_return_void(const_iterator position) + iterator insert(BOOST_RV_REF(value_type) x) { - table_.erase(get(position)); + return this->emplace(boost::move(x)); } - void clear() + iterator insert(const_iterator hint, value_type const& x) { - table_.clear(); + return this->emplace_hint(hint, x); } - void swap(unordered_multimap& other) + iterator insert(const_iterator hint, BOOST_RV_REF(value_type) x) { - table_.swap(other.table_); + return this->emplace_hint(hint, boost::move(x)); } - // observers + template <class InputIt> void insert(InputIt, InputIt); - hasher hash_function() const - { - return table_.hash_function(); - } +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + void insert(std::initializer_list<value_type>); +#endif - key_equal key_eq() const - { - return table_.key_eq(); - } + iterator erase(const_iterator); + size_type erase(const key_type&); + iterator erase(const_iterator, const_iterator); + void quick_erase(const_iterator it) { erase(it); } + void erase_return_void(const_iterator it) { erase(it); } - // lookup + void clear(); + void swap(unordered_multimap&); - iterator find(const key_type& k) - { - return iterator(table_.find(k)); - } + // observers - const_iterator find(const key_type& k) const - { - return const_iterator(table_.find(k)); - } + hasher hash_function() const; + key_equal key_eq() const; + + // lookup + + iterator find(const key_type&); + const_iterator find(const key_type&) const; template <class CompatibleKey, class CompatibleHash, class CompatiblePredicate> iterator find( - CompatibleKey const& k, - CompatibleHash const& hash, - CompatiblePredicate const& eq) - { - return iterator(table_.find(k, hash, eq)); - } + CompatibleKey const&, + CompatibleHash const&, + CompatiblePredicate const&); template <class CompatibleKey, class CompatibleHash, class CompatiblePredicate> const_iterator find( - CompatibleKey const& k, - CompatibleHash const& hash, - CompatiblePredicate const& eq) const - { - return iterator(table_.find(k, hash, eq)); - } + CompatibleKey const&, + CompatibleHash const&, + CompatiblePredicate const&) const; - size_type count(const key_type& k) const - { - return table_.count(k); - } + size_type count(const key_type&) const; std::pair<iterator, iterator> - equal_range(const key_type& k) - { - return boost::unordered_detail::pair_cast< - iterator, iterator>( - table_.equal_range(k)); - } - + equal_range(const key_type&); std::pair<const_iterator, const_iterator> - equal_range(const key_type& k) const - { - return boost::unordered_detail::pair_cast< - const_iterator, const_iterator>( - table_.equal_range(k)); - } + equal_range(const key_type&) const; // bucket interface @@ -1031,24 +938,24 @@ namespace boost return table_.max_bucket_count(); } - size_type bucket_size(size_type n) const - { - return table_.bucket_size(n); - } + size_type bucket_size(size_type) const; size_type bucket(const key_type& k) const { - return table_.bucket_index(k); + return table::to_bucket(table_.bucket_count_, + table_.hash(k)); } local_iterator begin(size_type n) { - return local_iterator(table_.bucket_begin(n)); + return local_iterator( + table_.begin(n), n, table_.bucket_count_); } const_local_iterator begin(size_type n) const { - return const_local_iterator(table_.bucket_begin(n)); + return const_local_iterator( + table_.begin(n), n, table_.bucket_count_); } local_iterator end(size_type) @@ -1063,7 +970,8 @@ namespace boost const_local_iterator cbegin(size_type n) const { - return const_local_iterator(table_.bucket_begin(n)); + return const_local_iterator( + table_.begin(n), n, table_.bucket_count_); } const_local_iterator cend(size_type) const @@ -1073,37 +981,640 @@ namespace boost // hash policy - float load_factor() const - { - return table_.load_factor(); - } - float max_load_factor() const { return table_.mlf_; } - void max_load_factor(float m) - { - table_.max_load_factor(m); - } - - void rehash(size_type n) - { - table_.rehash(n); - } + 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>( - unordered_multimap const&, unordered_multimap const&); - friend bool operator!=<K, T, H, P, A>( - unordered_multimap const&, unordered_multimap const&); + friend bool operator==<K,T,H,P,A>( + unordered_multimap const&, unordered_multimap const&); + friend bool operator!=<K,T,H,P,A>( + unordered_multimap const&, unordered_multimap const&); #endif }; // class template unordered_multimap +//////////////////////////////////////////////////////////////////////////////// + + template <class K, class T, class H, class P, class A> + unordered_map<K,T,H,P,A>::unordered_map( + size_type n, const hasher &hf, const key_equal &eql, + const allocator_type &a) + : table_(n, hf, eql, a) + { + } + + template <class K, class T, class H, class P, class A> + unordered_map<K,T,H,P,A>::unordered_map(allocator_type const& a) + : table_(boost::unordered::detail::default_bucket_count, + hasher(), key_equal(), a) + { + } + + template <class K, class T, class H, class P, class A> + unordered_map<K,T,H,P,A>::unordered_map( + unordered_map const& other, allocator_type const& a) + : table_(other.table_, a) + { + } + + template <class K, class T, class H, class P, class A> + template <class InputIt> + unordered_map<K,T,H,P,A>::unordered_map(InputIt f, InputIt l) + : table_(boost::unordered::detail::initial_size(f, l), + hasher(), key_equal(), allocator_type()) + { + table_.insert_range(f, l); + } + + template <class K, class T, class H, class P, class A> + template <class InputIt> + unordered_map<K,T,H,P,A>::unordered_map( + InputIt f, InputIt l, + size_type n, + const hasher &hf, + const key_equal &eql) + : table_(boost::unordered::detail::initial_size(f, l, n), + hf, eql, allocator_type()) + { + table_.insert_range(f, l); + } + + template <class K, class T, class H, class P, class A> + template <class InputIt> + unordered_map<K,T,H,P,A>::unordered_map( + InputIt f, InputIt l, + size_type n, + const hasher &hf, + const key_equal &eql, + const allocator_type &a) + : table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a) + { + table_.insert_range(f, l); + } + + template <class K, class T, class H, class P, class A> + unordered_map<K,T,H,P,A>::~unordered_map() {} + + template <class K, class T, class H, class P, class A> + unordered_map<K,T,H,P,A>::unordered_map( + unordered_map const& other) + : table_(other.table_) + { + } + +#if !defined(BOOST_NO_RVALUE_REFERENCES) + + template <class K, class T, class H, class P, class A> + unordered_map<K,T,H,P,A>::unordered_map( + unordered_map&& other, allocator_type const& a) + : table_(other.table_, a, boost::unordered::detail::move_tag()) + { + } + +#endif + +#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( + std::initializer_list<value_type> list, size_type n, + const hasher &hf, const key_equal &eql, const allocator_type &a) + : table_( + boost::unordered::detail::initial_size( + list.begin(), list.end(), n), + hf, eql, a) + { + table_.insert_range(list.begin(), list.end()); + } + + template <class K, class T, class H, class P, class A> + unordered_map<K,T,H,P,A>& unordered_map<K,T,H,P,A>::operator=( + std::initializer_list<value_type> list) + { + table_.clear(); + table_.insert_range(list.begin(), list.end()); + return *this; + } + +#endif + + // size and capacity + + template <class K, class T, class H, class P, class A> + std::size_t unordered_map<K,T,H,P,A>::max_size() const + { + return table_.max_size(); + } + + // modifiers + + template <class K, class T, class H, class P, class A> + template <class InputIt> + void unordered_map<K,T,H,P,A>::insert(InputIt first, InputIt last) + { + table_.insert_range(first, last); + } + +#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) + { + table_.insert_range(list.begin(), list.end()); + } +#endif + + template <class K, class T, class H, class P, class A> + typename unordered_map<K,T,H,P,A>::iterator + unordered_map<K,T,H,P,A>::erase(const_iterator position) + { + return table_.erase(position); + } + + template <class K, class T, class H, class P, class A> + typename unordered_map<K,T,H,P,A>::size_type + unordered_map<K,T,H,P,A>::erase(const key_type& k) + { + return table_.erase_key(k); + } + + template <class K, class T, class H, class P, class A> + typename unordered_map<K,T,H,P,A>::iterator + unordered_map<K,T,H,P,A>::erase( + const_iterator first, const_iterator last) + { + return table_.erase_range(first, last); + } + + template <class K, class T, class H, class P, class A> + void unordered_map<K,T,H,P,A>::clear() + { + table_.clear(); + } + + template <class K, class T, class H, class P, class A> + void unordered_map<K,T,H,P,A>::swap(unordered_map& other) + { + table_.swap(other.table_); + } + + // observers + + template <class K, class T, class H, class P, class A> + typename unordered_map<K,T,H,P,A>::hasher + unordered_map<K,T,H,P,A>::hash_function() const + { + return table_.hash_function(); + } + + template <class K, class T, class H, class P, class A> + typename unordered_map<K,T,H,P,A>::key_equal + unordered_map<K,T,H,P,A>::key_eq() const + { + return table_.key_eq(); + } + + template <class K, class T, class H, class P, class A> + typename unordered_map<K,T,H,P,A>::mapped_type& + unordered_map<K,T,H,P,A>::operator[](const key_type &k) + { + return table_[k].second; + } + + template <class K, class T, class H, class P, class A> + typename unordered_map<K,T,H,P,A>::mapped_type& + unordered_map<K,T,H,P,A>::at(const key_type& k) + { + return table_.at(k).second; + } + + template <class K, class T, class H, class P, class A> + typename unordered_map<K,T,H,P,A>::mapped_type const& + unordered_map<K,T,H,P,A>::at(const key_type& k) const + { + return table_.at(k).second; + } + + // lookup + + template <class K, class T, class H, class P, class A> + typename unordered_map<K,T,H,P,A>::iterator + unordered_map<K,T,H,P,A>::find(const key_type& 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 table_.find_node(k); + } + + template <class K, class T, class H, class P, class A> + template <class CompatibleKey, class CompatibleHash, + class CompatiblePredicate> + typename unordered_map<K,T,H,P,A>::iterator + unordered_map<K,T,H,P,A>::find( + CompatibleKey const& k, + CompatibleHash const& hash, + CompatiblePredicate const& eq) + { + return table_.generic_find_node(k, hash, eq); + } + + template <class K, class T, class H, class P, class A> + template <class CompatibleKey, class CompatibleHash, + class CompatiblePredicate> + typename unordered_map<K,T,H,P,A>::const_iterator + unordered_map<K,T,H,P,A>::find( + CompatibleKey const& k, + CompatibleHash const& hash, + CompatiblePredicate const& eq) const + { + return table_.generic_find_node(k, hash, eq); + } + + template <class K, class T, class H, class P, class A> + typename unordered_map<K,T,H,P,A>::size_type + unordered_map<K,T,H,P,A>::count(const key_type& k) const + { + return table_.count(k); + } + + template <class K, class T, class H, class P, class A> + std::pair< + typename unordered_map<K,T,H,P,A>::iterator, + typename unordered_map<K,T,H,P,A>::iterator> + unordered_map<K,T,H,P,A>::equal_range(const key_type& k) + { + return table_.equal_range(k); + } + + template <class K, class T, class H, class P, class A> + std::pair< + typename unordered_map<K,T,H,P,A>::const_iterator, + typename unordered_map<K,T,H,P,A>::const_iterator> + unordered_map<K,T,H,P,A>::equal_range(const key_type& k) const + { + return table_.equal_range(k); + } + + template <class K, class T, class H, class P, class A> + typename unordered_map<K,T,H,P,A>::size_type + unordered_map<K,T,H,P,A>::bucket_size(size_type n) const + { + return table_.bucket_size(n); + } + + // hash policy + + template <class K, class T, class H, class P, class A> + float unordered_map<K,T,H,P,A>::load_factor() const + { + return table_.load_factor(); + } + + template <class K, class T, class H, class P, class A> + void unordered_map<K,T,H,P,A>::max_load_factor(float m) + { + table_.max_load_factor(m); + } + + template <class K, class T, class H, class P, class A> + void unordered_map<K,T,H,P,A>::rehash(size_type n) + { + table_.rehash(n); + } + + 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) + { +#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613)) + struct dummy { unordered_map<K,T,H,P,A> x; }; +#endif + return m1.table_.equals(m2.table_); + } + + 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) + { +#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613)) + struct dummy { unordered_map<K,T,H,P,A> x; }; +#endif + return !m1.table_.equals(m2.table_); + } + + template <class K, class T, class H, class P, class A> + inline void swap( + unordered_map<K,T,H,P,A> &m1, + unordered_map<K,T,H,P,A> &m2) + { +#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613)) + struct dummy { unordered_map<K,T,H,P,A> x; }; +#endif + m1.swap(m2); + } + +//////////////////////////////////////////////////////////////////////////////// + + template <class K, class T, class H, class P, class A> + unordered_multimap<K,T,H,P,A>::unordered_multimap( + size_type n, const hasher &hf, const key_equal &eql, + const allocator_type &a) + : table_(n, hf, eql, a) + { + } + + template <class K, class T, class H, class P, class A> + unordered_multimap<K,T,H,P,A>::unordered_multimap(allocator_type const& a) + : table_(boost::unordered::detail::default_bucket_count, + hasher(), key_equal(), a) + { + } + + template <class K, class T, class H, class P, class A> + unordered_multimap<K,T,H,P,A>::unordered_multimap( + unordered_multimap const& other, allocator_type const& a) + : table_(other.table_, a) + { + } + + template <class K, class T, class H, class P, class A> + template <class InputIt> + unordered_multimap<K,T,H,P,A>::unordered_multimap(InputIt f, InputIt l) + : table_(boost::unordered::detail::initial_size(f, l), + hasher(), key_equal(), allocator_type()) + { + table_.insert_range(f, l); + } + + template <class K, class T, class H, class P, class A> + template <class InputIt> + unordered_multimap<K,T,H,P,A>::unordered_multimap( + InputIt f, InputIt l, + size_type n, + const hasher &hf, + const key_equal &eql) + : table_(boost::unordered::detail::initial_size(f, l, n), + hf, eql, allocator_type()) + { + table_.insert_range(f, l); + } + + template <class K, class T, class H, class P, class A> + template <class InputIt> + unordered_multimap<K,T,H,P,A>::unordered_multimap( + InputIt f, InputIt l, + size_type n, + const hasher &hf, + const key_equal &eql, + const allocator_type &a) + : table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a) + { + table_.insert_range(f, l); + } + + template <class K, class T, class H, class P, class A> + unordered_multimap<K,T,H,P,A>::~unordered_multimap() {} + + template <class K, class T, class H, class P, class A> + unordered_multimap<K,T,H,P,A>::unordered_multimap( + unordered_multimap const& other) + : table_(other.table_) + { + } + +#if !defined(BOOST_NO_RVALUE_REFERENCES) + + template <class K, class T, class H, class P, class A> + unordered_multimap<K,T,H,P,A>::unordered_multimap( + unordered_multimap&& other, allocator_type const& a) + : table_(other.table_, a, boost::unordered::detail::move_tag()) + { + } + +#endif + +#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( + std::initializer_list<value_type> list, size_type n, + const hasher &hf, const key_equal &eql, const allocator_type &a) + : table_( + boost::unordered::detail::initial_size( + list.begin(), list.end(), n), + hf, eql, a) + { + table_.insert_range(list.begin(), list.end()); + } + + template <class K, class T, class H, class P, class A> + unordered_multimap<K,T,H,P,A>& unordered_multimap<K,T,H,P,A>::operator=( + std::initializer_list<value_type> list) + { + table_.clear(); + table_.insert_range(list.begin(), list.end()); + return *this; + } + +#endif + + // size and capacity + + template <class K, class T, class H, class P, class A> + std::size_t unordered_multimap<K,T,H,P,A>::max_size() const + { + return table_.max_size(); + } + + // modifiers + + template <class K, class T, class H, class P, class A> + template <class InputIt> + void unordered_multimap<K,T,H,P,A>::insert(InputIt first, InputIt last) + { + table_.insert_range(first, last); + } + +#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) + { + table_.insert_range(list.begin(), list.end()); + } +#endif + + template <class K, class T, class H, class P, class A> + typename unordered_multimap<K,T,H,P,A>::iterator + unordered_multimap<K,T,H,P,A>::erase(const_iterator position) + { + return table_.erase(position); + } + + template <class K, class T, class H, class P, class A> + typename unordered_multimap<K,T,H,P,A>::size_type + unordered_multimap<K,T,H,P,A>::erase(const key_type& k) + { + return table_.erase_key(k); + } + + template <class K, class T, class H, class P, class A> + typename unordered_multimap<K,T,H,P,A>::iterator + unordered_multimap<K,T,H,P,A>::erase( + const_iterator first, const_iterator last) + { + return table_.erase_range(first, last); + } + + template <class K, class T, class H, class P, class A> + void unordered_multimap<K,T,H,P,A>::clear() + { + table_.clear(); + } + + template <class K, class T, class H, class P, class A> + void unordered_multimap<K,T,H,P,A>::swap(unordered_multimap& other) + { + table_.swap(other.table_); + } + + // observers + + template <class K, class T, class H, class P, class A> + typename unordered_multimap<K,T,H,P,A>::hasher + unordered_multimap<K,T,H,P,A>::hash_function() const + { + return table_.hash_function(); + } + + template <class K, class T, class H, class P, class A> + typename unordered_multimap<K,T,H,P,A>::key_equal + unordered_multimap<K,T,H,P,A>::key_eq() const + { + return table_.key_eq(); + } + + // lookup + + template <class K, class T, class H, class P, class A> + typename unordered_multimap<K,T,H,P,A>::iterator + unordered_multimap<K,T,H,P,A>::find(const key_type& 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 table_.find_node(k); + } + + template <class K, class T, class H, class P, class A> + template <class CompatibleKey, class CompatibleHash, + class CompatiblePredicate> + typename unordered_multimap<K,T,H,P,A>::iterator + unordered_multimap<K,T,H,P,A>::find( + CompatibleKey const& k, + CompatibleHash const& hash, + CompatiblePredicate const& eq) + { + return table_.generic_find_node(k, hash, eq); + } + + template <class K, class T, class H, class P, class A> + template <class CompatibleKey, class CompatibleHash, + class CompatiblePredicate> + typename unordered_multimap<K,T,H,P,A>::const_iterator + unordered_multimap<K,T,H,P,A>::find( + CompatibleKey const& k, + CompatibleHash const& hash, + CompatiblePredicate const& eq) const + { + return table_.generic_find_node(k, hash, eq); + } + + template <class K, class T, class H, class P, class A> + typename unordered_multimap<K,T,H,P,A>::size_type + unordered_multimap<K,T,H,P,A>::count(const key_type& k) const + { + return table_.count(k); + } + + template <class K, class T, class H, class P, class A> + std::pair< + typename unordered_multimap<K,T,H,P,A>::iterator, + typename unordered_multimap<K,T,H,P,A>::iterator> + unordered_multimap<K,T,H,P,A>::equal_range(const key_type& k) + { + return table_.equal_range(k); + } + + template <class K, class T, class H, class P, class A> + std::pair< + typename unordered_multimap<K,T,H,P,A>::const_iterator, + typename unordered_multimap<K,T,H,P,A>::const_iterator> + unordered_multimap<K,T,H,P,A>::equal_range(const key_type& k) const + { + return table_.equal_range(k); + } + + template <class K, class T, class H, class P, class A> + typename unordered_multimap<K,T,H,P,A>::size_type + unordered_multimap<K,T,H,P,A>::bucket_size(size_type n) const + { + return table_.bucket_size(n); + } + + // hash policy + + template <class K, class T, class H, class P, class A> + float unordered_multimap<K,T,H,P,A>::load_factor() const + { + return table_.load_factor(); + } + + template <class K, class T, class H, class P, class A> + void unordered_multimap<K,T,H,P,A>::max_load_factor(float m) + { + table_.max_load_factor(m); + } + + template <class K, class T, class H, class P, class A> + void unordered_multimap<K,T,H,P,A>::rehash(size_type n) + { + table_.rehash(n); + } + + 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) + inline bool operator==( + unordered_multimap<K,T,H,P,A> const& m1, + unordered_multimap<K,T,H,P,A> const& m2) { #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613)) struct dummy { unordered_multimap<K,T,H,P,A> x; }; @@ -1112,8 +1623,9 @@ namespace boost } 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) + inline bool operator!=( + unordered_multimap<K,T,H,P,A> const& m1, + unordered_multimap<K,T,H,P,A> const& m2) { #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613)) struct dummy { unordered_multimap<K,T,H,P,A> x; }; @@ -1122,8 +1634,9 @@ namespace boost } template <class K, class T, class H, class P, class A> - inline void swap(unordered_multimap<K, T, H, P, A> &m1, - unordered_multimap<K, T, H, P, A> &m2) + inline void swap( + unordered_multimap<K,T,H,P,A> &m1, + unordered_multimap<K,T,H,P,A> &m2) { #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613)) struct dummy { unordered_multimap<K,T,H,P,A> x; }; @@ -1131,6 +1644,7 @@ namespace boost m1.swap(m2); } +} // namespace unordered } // namespace boost #if defined(BOOST_MSVC) diff --git a/3rdParty/Boost/src/boost/unordered/unordered_map_fwd.hpp b/3rdParty/Boost/src/boost/unordered/unordered_map_fwd.hpp index edecc5d..980bb3e 100644 --- a/3rdParty/Boost/src/boost/unordered/unordered_map_fwd.hpp +++ b/3rdParty/Boost/src/boost/unordered/unordered_map_fwd.hpp @@ -1,5 +1,5 @@ -// Copyright (C) 2008-2009 Daniel James. +// Copyright (C) 2008-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) @@ -14,40 +14,52 @@ #include <memory> #include <functional> #include <boost/functional/hash_fwd.hpp> +#include <boost/unordered/detail/fwd.hpp> namespace boost { - template <class K, - class T, - class H = 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&); - 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&); - template <class K, class T, class H, class P, class A> - inline void swap(unordered_map<K, T, H, P, A>&, - unordered_map<K, T, H, P, A>&); - - template <class K, - class T, - class H = 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&); - 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&); - template <class K, class T, class H, class P, class A> - inline void swap(unordered_multimap<K, T, H, P, A>&, - unordered_multimap<K, T, H, P, A>&); + 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&); + 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&); + template <class K, class T, class H, class P, class A> + 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&); + 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&); + template <class K, class T, class H, class P, class A> + inline void swap(unordered_multimap<K, T, H, P, A>&, + unordered_multimap<K, T, H, P, A>&); + } + + using boost::unordered::unordered_map; + using boost::unordered::unordered_multimap; + using boost::unordered::swap; + using boost::unordered::operator==; + using boost::unordered::operator!=; } #endif |