Swift
summaryrefslogtreecommitdiffstats
path: root/3rdParty/Boost/src/boost/unordered/detail
diff options
context:
space:
mode:
authorRemko Tronçon <git@el-tramo.be>2012-12-23 13:16:26 (GMT)
committerRemko Tronçon <git@el-tramo.be>2012-12-23 14:43:26 (GMT)
commit491ddd570a752cf9bda85933bed0c6942e39b1f9 (patch)
tree10c25c1be8cc08d0497df1dccd56a10fbb30beee /3rdParty/Boost/src/boost/unordered/detail
parentda7d7a0ca71b80281aa9ff2526290b61ccb0cc60 (diff)
downloadswift-491ddd570a752cf9bda85933bed0c6942e39b1f9.zip
swift-491ddd570a752cf9bda85933bed0c6942e39b1f9.tar.bz2
Update Boost to 1.52.0.
Change-Id: I1e56bea2600bf2ed9c5b3aba8c4f9d2a0f350e77
Diffstat (limited to '3rdParty/Boost/src/boost/unordered/detail')
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/allocate.hpp1241
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/allocator_helpers.hpp111
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/buckets.hpp882
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp939
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/extract_key.hpp82
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/fwd.hpp935
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/move.hpp243
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/node.hpp226
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/table.hpp1407
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/unique.hpp984
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/util.hpp321
11 files changed, 4235 insertions, 3136 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