summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat (limited to '3rdParty/Boost/src/boost/unordered')
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/allocate.hpp285
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/buckets.hpp399
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp293
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/extract_key.hpp80
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/fwd.hpp6
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/table.hpp224
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/unique.hpp139
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/util.hpp10
-rw-r--r--3rdParty/Boost/src/boost/unordered/unordered_map.hpp115
-rw-r--r--3rdParty/Boost/src/boost/unordered/unordered_map_fwd.hpp6
10 files changed, 703 insertions, 854 deletions
diff --git a/3rdParty/Boost/src/boost/unordered/detail/allocate.hpp b/3rdParty/Boost/src/boost/unordered/detail/allocate.hpp
index b6f1c79..4c20b16 100644
--- a/3rdParty/Boost/src/boost/unordered/detail/allocate.hpp
+++ b/3rdParty/Boost/src/boost/unordered/detail/allocate.hpp
@@ -9,8 +9,9 @@
#ifndef BOOST_UNORDERED_ALLOCATE_HPP
#define BOOST_UNORDERED_ALLOCATE_HPP
-#if defined(_MSC_VER) && (_MSC_VER >= 1020)
-# pragma once
+#include <boost/config.hpp>
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#pragma once
#endif
#include <boost/unordered/detail/fwd.hpp>
@@ -85,7 +86,7 @@ namespace boost { namespace unordered { namespace detail {
// Either forwarding variadic arguments, or storing the arguments in
// emplace_args##n
-#if !defined(BOOST_NO_VARIADIC_TEMPLATES)
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
#define BOOST_UNORDERED_EMPLACE_TEMPLATE typename... Args
#define BOOST_UNORDERED_EMPLACE_ARGS BOOST_FWD_REF(Args)... args
@@ -136,7 +137,7 @@ namespace boost { namespace unordered { namespace detail {
#define BOOST_UNORDERED_EMPLACE_ARGS2 create_emplace_args
#define BOOST_UNORDERED_EMPLACE_ARGS3 create_emplace_args
-#if defined(BOOST_NO_RVALUE_REFERENCES)
+#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
#define BOOST_UNORDERED_EARGS_MEMBER(z, n, _) \
typedef BOOST_FWD_REF(BOOST_PP_CAT(A, n)) BOOST_PP_CAT(Arg, n); \
@@ -234,9 +235,11 @@ namespace boost { namespace unordered { namespace detail {
#pragma warning(disable:4100) // unreferenced formal parameter
#endif
- template <class T>
- inline void destroy(T* x) {
- x->~T();
+ namespace func {
+ template <class T>
+ inline void destroy(T* x) {
+ x->~T();
+ }
}
#if defined(BOOST_MSVC)
@@ -257,13 +260,12 @@ namespace boost { namespace unordered { namespace detail {
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(( \
+ sizeof(for_expr_test(( \
(expression), \
0)))>::type test( \
BOOST_PP_CAT(choice, count))
@@ -276,6 +278,7 @@ namespace boost { namespace unordered { namespace detail {
# define BOOST_UNORDERED_HAS_FUNCTION(name, thing, args, _) \
struct BOOST_PP_CAT(has_, name) \
{ \
+ template <typename U> static char for_expr_test(U const&); \
BOOST_UNORDERED_CHECK_EXPRESSION(1, 1, \
boost::unordered::detail::make< thing >().name args); \
BOOST_UNORDERED_DEFAULT_EXPRESSION(2, 2); \
@@ -342,7 +345,7 @@ namespace boost { namespace unordered { namespace detail {
# include <boost/type_traits/is_same.hpp>
# endif
-# if !defined(BOOST_NO_VARIADIC_TEMPLATES) && \
+# if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) && \
!defined(BOOST_NO_SFINAE_EXPR)
# define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 1
# else
@@ -432,7 +435,7 @@ namespace boost { namespace unordered { namespace detail {
max_size, U const, (), 0
);
-# if !defined(BOOST_NO_VARIADIC_TEMPLATES)
+# if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
template <typename T, typename ValueType, typename... Args>
BOOST_UNORDERED_HAS_FUNCTION(
@@ -473,6 +476,9 @@ namespace boost { namespace unordered { namespace detail {
# endif
+ namespace func
+ {
+
template <typename Alloc>
inline Alloc call_select_on_container_copy_construction(const Alloc& rhs,
typename boost::enable_if_c<
@@ -510,6 +516,8 @@ namespace boost { namespace unordered { namespace detail {
return (std::numeric_limits<SizeType>::max)();
}
+ } // namespace func.
+
template <typename Alloc>
struct allocator_traits
{
@@ -589,7 +597,7 @@ namespace boost { namespace unordered { namespace detail {
boost::unordered::detail::has_destroy<Alloc, T>::value>::type
destroy(Alloc&, T* p)
{
- boost::unordered::detail::destroy(p);
+ boost::unordered::detail::func::destroy(p);
}
# elif !defined(BOOST_NO_SFINAE_EXPR)
@@ -623,7 +631,7 @@ namespace boost { namespace unordered { namespace detail {
boost::unordered::detail::has_destroy<Alloc, T>::value>::type
destroy(Alloc&, T* p)
{
- boost::unordered::detail::destroy(p);
+ boost::unordered::detail::func::destroy(p);
}
# else
@@ -669,21 +677,22 @@ namespace boost { namespace unordered { namespace detail {
boost::is_same<T, value_type>::value,
void*>::type = 0)
{
- boost::unordered::detail::destroy(p);
+ boost::unordered::detail::func::destroy(p);
}
# endif
static size_type max_size(const Alloc& a)
{
- return boost::unordered::detail::call_max_size<size_type>(a);
+ return boost::unordered::detail::func::
+ call_max_size<size_type>(a);
}
// Allocator propagation on construction
static Alloc select_on_container_copy_construction(Alloc const& rhs)
{
- return boost::unordered::detail::
+ return boost::unordered::detail::func::
call_select_on_container_copy_construction(rhs);
}
@@ -758,12 +767,12 @@ namespace boost { namespace unordered { namespace detail {
#endif
-namespace boost { namespace unordered { namespace detail {
+namespace boost { namespace unordered { namespace detail { namespace func {
////////////////////////////////////////////////////////////////////////////
// call_construct
-#if !defined(BOOST_NO_VARIADIC_TEMPLATES)
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
# if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT
@@ -792,7 +801,7 @@ namespace boost { namespace unordered { namespace detail {
template <typename Alloc, typename T>
inline void destroy_value_impl(Alloc&, T* x) {
- boost::unordered::detail::destroy(x);
+ boost::unordered::detail::func::destroy(x);
}
@@ -802,7 +811,7 @@ namespace boost { namespace unordered { namespace detail {
template <typename Alloc, typename T>
inline void destroy_value_impl(Alloc&, T* x) {
- boost::unordered::detail::destroy(x);
+ boost::unordered::detail::func::destroy(x);
}
#endif
@@ -812,13 +821,13 @@ namespace boost { namespace unordered { namespace detail {
//
// Used for piecewise construction.
-#if !defined(BOOST_NO_VARIADIC_TEMPLATES)
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
# define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(n, namespace_) \
template<typename Alloc, typename T> \
void construct_from_tuple(Alloc& alloc, T* ptr, namespace_ tuple<>) \
{ \
- boost::unordered::detail::call_construct(alloc, ptr); \
+ boost::unordered::detail::func::call_construct(alloc, ptr); \
} \
\
BOOST_PP_REPEAT_FROM_TO(1, n, \
@@ -830,7 +839,7 @@ namespace boost { namespace unordered { namespace detail {
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::unordered::detail::func::call_construct(alloc, ptr, \
BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_) \
); \
}
@@ -871,7 +880,7 @@ namespace boost { namespace unordered { namespace detail {
# 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, \
+ boost::unordered::detail::func::length<0>, Alloc&, T* ptr, \
namespace_ tuple<>) \
{ \
new ((void*) ptr) T(); \
@@ -884,7 +893,7 @@ namespace boost { namespace unordered { namespace detail {
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, \
+ boost::unordered::detail::func::length<n>, Alloc&, T* ptr, \
namespace_ tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \
{ \
new ((void*) ptr) T( \
@@ -913,7 +922,7 @@ BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(10, boost::)
void construct_from_tuple(Alloc& alloc, T* ptr, Tuple const& x)
{
construct_from_tuple_impl(
- boost::unordered::detail::length<
+ boost::unordered::detail::func::length<
boost::tuples::length<Tuple>::value>(),
alloc, ptr, x);
}
@@ -921,146 +930,58 @@ BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(10, boost::)
#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
+ // Trait to check for piecewise construction.
- template <typename A, typename B, typename A0>
- struct check3_base {
+ template <typename A0>
+ struct use_piecewise {
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, ...);
+ static choice2::type test(choice2, ...);
- enum { value =
+ enum { value = sizeof(choice1::type) ==
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)
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
////////////////////////////////////////////////////////////////////////////
// Construct from variadic parameters
+ // For the standard pair constructor.
+
template <typename Alloc, typename T, typename... Args>
inline void construct_value_impl(Alloc& alloc, T* address,
BOOST_FWD_REF(Args)... args)
{
- boost::unordered::detail::call_construct(alloc,
+ boost::unordered::detail::func::call_construct(alloc,
address, boost::forward<Args>(args)...);
}
+ // Special case for piece_construct
+ //
+ // TODO: When possible, it might be better to use std::pair's
+ // constructor for std::piece_construct with std::tuple.
+
template <typename Alloc, typename A, typename B,
typename A0, typename A1, typename A2>
- inline typename enable_if<piecewise3<A, B, A0>, void>::type
+ inline typename enable_if<use_piecewise<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::unordered::detail::func::construct_from_tuple(alloc,
boost::addressof(address->first), boost::forward<A1>(a1));
- boost::unordered::detail::construct_from_tuple(alloc,
+ boost::unordered::detail::func::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
+#else // BOOST_NO_CXX11_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)); \
- }
+ // Explicitly write out first three overloads for the sake of sane
+ // error messages.
template <typename Alloc, typename T, typename A0>
inline void construct_value_impl(Alloc&, T* address,
@@ -1090,82 +1011,45 @@ BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(10, boost::)
);
}
+ // Use a macro for the rest.
+
+#define BOOST_UNORDERED_CONSTRUCT_IMPL(z, num_params, _) \
+ template < \
+ typename Alloc, typename T, \
+ BOOST_PP_ENUM_PARAMS_Z(z, num_params, typename A) \
+ > \
+ inline void construct_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)); \
+ }
+
BOOST_PP_REPEAT_FROM_TO(4, BOOST_UNORDERED_EMPLACE_LIMIT,
BOOST_UNORDERED_CONSTRUCT_IMPL, _)
#undef BOOST_UNORDERED_CONSTRUCT_IMPL
+ // Construct with piece_construct
+
template <typename Alloc, typename A, typename B,
typename A0, typename A1, typename A2>
inline void construct_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)
+ typename enable_if<use_piecewise<A0>, void*>::type = 0)
{
- boost::unordered::detail::construct_from_tuple(alloc,
+ boost::unordered::detail::func::construct_from_tuple(alloc,
boost::addressof(address->first), args.a1);
- boost::unordered::detail::construct_from_tuple(alloc,
+ boost::unordered::detail::func::construct_from_tuple(alloc,
boost::addressof(address->second), args.a2);
}
-#if defined(BOOST_UNORDERED_DEPRECATED_PAIR_CONSTRUCT)
+#endif // BOOST_NO_CXX11_VARIADIC_TEMPLATES
- 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 {
@@ -1197,8 +1081,10 @@ namespace boost { namespace unordered { namespace detail {
~array_constructor() {
if (ptr_) {
- for(pointer p = ptr_; p != constructed_; ++p)
- traits::destroy(alloc_, boost::addressof(*p));
+ for(pointer p = ptr_; p != constructed_; ++p) {
+ boost::unordered::detail::func::destroy(
+ boost::addressof(*p));
+ }
traits::deallocate(alloc_, ptr_, length_);
}
@@ -1211,8 +1097,9 @@ namespace boost { namespace unordered { namespace detail {
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);
+ for(constructed_ = ptr_; constructed_ != end; ++constructed_) {
+ new ((void*) boost::addressof(*constructed_)) V(v);
+ }
}
pointer get() const
diff --git a/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp b/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp
index def5c7c..fd038b7 100644
--- a/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp
+++ b/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp
@@ -7,14 +7,17 @@
#ifndef BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED
#define BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED
-#if defined(_MSC_VER) && (_MSC_VER >= 1020)
-# pragma once
+#include <boost/config.hpp>
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#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/type_traits/is_nothrow_move_constructible.hpp>
+#include <boost/type_traits/is_nothrow_move_assignable.hpp>
#include <boost/swap.hpp>
#include <boost/assert.hpp>
#include <boost/limits.hpp>
@@ -30,6 +33,10 @@ namespace boost { namespace unordered { namespace detail {
}}}
+// The 'iterator_detail' namespace was a misguided attempt at avoiding ADL
+// in the detail namespace. It didn't work because the template parameters
+// were in detail. I'm not changing it at the moment to be safe. I might
+// do in the future if I change the iterator types.
namespace boost { namespace unordered { namespace iterator_detail {
////////////////////////////////////////////////////////////////////////////
@@ -37,49 +44,50 @@ namespace boost { namespace unordered { namespace iterator_detail {
//
// all no throw
- template <typename NodePointer, typename Value> struct iterator;
- template <typename ConstNodePointer, typename NodePointer,
- typename Value> struct c_iterator;
- template <typename NodePointer, typename Value, typename Policy>
- struct l_iterator;
- template <typename ConstNodePointer, typename NodePointer,
- typename Value, typename Policy> struct cl_iterator;
+ template <typename Node> struct iterator;
+ template <typename Node, typename ConstNodePointer> struct c_iterator;
+ template <typename Node, typename Policy> struct l_iterator;
+ template <typename Node, typename ConstNodePointer, typename Policy>
+ struct cl_iterator;
// Local Iterators
//
// all no throw
- template <typename NodePointer, typename Value, typename Policy>
+ template <typename Node, typename Policy>
struct l_iterator
: public boost::iterator<
- std::forward_iterator_tag, Value, std::ptrdiff_t,
- NodePointer, Value&>
+ std::forward_iterator_tag,
+ typename Node::value_type,
+ std::ptrdiff_t,
+ typename Node::node_pointer,
+ typename Node::value_type&>
{
#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
- template <typename ConstNodePointer, typename NodePointer2,
- typename Value2, typename Policy2>
+ template <typename Node2, typename ConstNodePointer, 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;
+ typedef typename Node::node_pointer node_pointer;
+ typedef boost::unordered::iterator_detail::iterator<Node> iterator;
node_pointer ptr_;
std::size_t bucket_;
std::size_t bucket_count_;
public:
- l_iterator() : ptr_() {}
+ typedef typename Node::value_type value_type;
- l_iterator(iterator x, std::size_t b, std::size_t c)
+ l_iterator() BOOST_NOEXCEPT : ptr_() {}
+
+ l_iterator(iterator x, std::size_t b, std::size_t c) BOOST_NOEXCEPT
: ptr_(x.node_), bucket_(b), bucket_count_(c) {}
- Value& operator*() const {
+ value_type& operator*() const {
return ptr_->value();
}
- Value* operator->() const {
+ value_type* operator->() const {
return ptr_->value_ptr();
}
@@ -97,51 +105,53 @@ namespace boost { namespace unordered { namespace iterator_detail {
return tmp;
}
- bool operator==(l_iterator x) const {
+ bool operator==(l_iterator x) const BOOST_NOEXCEPT {
return ptr_ == x.ptr_;
}
- bool operator!=(l_iterator x) const {
+ bool operator!=(l_iterator x) const BOOST_NOEXCEPT {
return ptr_ != x.ptr_;
}
};
- template <typename ConstNodePointer, typename NodePointer, typename Value,
- typename Policy>
+ template <typename Node, typename ConstNodePointer, typename Policy>
struct cl_iterator
: public boost::iterator<
- std::forward_iterator_tag, Value, std::ptrdiff_t,
- ConstNodePointer, Value const&>
+ std::forward_iterator_tag,
+ typename Node::value_type,
+ std::ptrdiff_t,
+ ConstNodePointer,
+ typename Node::value_type const&>
{
friend struct boost::unordered::iterator_detail::l_iterator
- <NodePointer, Value, Policy>;
+ <Node, Policy>;
private:
- typedef NodePointer node_pointer;
- typedef boost::unordered::iterator_detail::iterator<NodePointer, Value>
- iterator;
+ typedef typename Node::node_pointer node_pointer;
+ typedef boost::unordered::iterator_detail::iterator<Node> iterator;
node_pointer ptr_;
std::size_t bucket_;
std::size_t bucket_count_;
public:
- cl_iterator() : ptr_() {}
+ typedef typename Node::value_type value_type;
+
+ cl_iterator() BOOST_NOEXCEPT : ptr_() {}
- cl_iterator(iterator x, std::size_t b, std::size_t c) :
+ cl_iterator(iterator x, std::size_t b, std::size_t c) BOOST_NOEXCEPT :
ptr_(x.node_), bucket_(b), bucket_count_(c) {}
cl_iterator(boost::unordered::iterator_detail::l_iterator<
- NodePointer, Value, Policy> const& x) :
+ Node, Policy> const& x) BOOST_NOEXCEPT :
ptr_(x.ptr_), bucket_(x.bucket_), bucket_count_(x.bucket_count_)
{}
- Value const&
- operator*() const {
+ value_type const& operator*() const {
return ptr_->value();
}
- Value const* operator->() const {
+ value_type const* operator->() const {
return ptr_->value_ptr();
}
@@ -159,27 +169,34 @@ namespace boost { namespace unordered { namespace iterator_detail {
return tmp;
}
- friend bool operator==(cl_iterator const& x, cl_iterator const& y) {
+ friend bool operator==(cl_iterator const& x, cl_iterator const& y)
+ BOOST_NOEXCEPT
+ {
return x.ptr_ == y.ptr_;
}
- friend bool operator!=(cl_iterator const& x, cl_iterator const& y) {
+ friend bool operator!=(cl_iterator const& x, cl_iterator const& y)
+ BOOST_NOEXCEPT
+ {
return x.ptr_ != y.ptr_;
}
};
- template <typename NodePointer, typename Value>
+ template <typename Node>
struct iterator
: public boost::iterator<
- std::forward_iterator_tag, Value, std::ptrdiff_t,
- NodePointer, Value&>
+ std::forward_iterator_tag,
+ typename Node::value_type,
+ std::ptrdiff_t,
+ typename Node::node_pointer,
+ typename Node::value_type&>
{
#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
- template <typename, typename, typename>
+ template <typename, typename>
friend struct boost::unordered::iterator_detail::c_iterator;
- template <typename, typename, typename>
+ template <typename, typename>
friend struct boost::unordered::iterator_detail::l_iterator;
- template <typename, typename, typename, typename>
+ template <typename, typename, typename>
friend struct boost::unordered::iterator_detail::cl_iterator;
template <typename>
friend struct boost::unordered::detail::table;
@@ -189,20 +206,23 @@ namespace boost { namespace unordered { namespace iterator_detail {
friend struct boost::unordered::detail::grouped_table_impl;
private:
#endif
- typedef NodePointer node_pointer;
+ typedef typename Node::node_pointer node_pointer;
node_pointer node_;
public:
- iterator() : node_() {}
+ typedef typename Node::value_type value_type;
+
+ iterator() BOOST_NOEXCEPT : node_() {}
- explicit iterator(node_pointer const& x) : node_(x) {}
+ explicit iterator(typename Node::link_pointer x) BOOST_NOEXCEPT :
+ node_(static_cast<node_pointer>(x)) {}
- Value& operator*() const {
+ value_type& operator*() const {
return node_->value();
}
- Value* operator->() const {
+ value_type* operator->() const {
return &node_->value();
}
@@ -217,23 +237,25 @@ namespace boost { namespace unordered { namespace iterator_detail {
return tmp;
}
- bool operator==(iterator const& x) const {
+ bool operator==(iterator const& x) const BOOST_NOEXCEPT {
return node_ == x.node_;
}
- bool operator!=(iterator const& x) const {
+ bool operator!=(iterator const& x) const BOOST_NOEXCEPT {
return node_ != x.node_;
}
};
- template <typename ConstNodePointer, typename NodePointer, typename Value>
+ template <typename Node, typename ConstNodePointer>
struct c_iterator
: public boost::iterator<
- std::forward_iterator_tag, Value, std::ptrdiff_t,
- ConstNodePointer, Value const&>
+ std::forward_iterator_tag,
+ typename Node::value_type,
+ std::ptrdiff_t,
+ ConstNodePointer,
+ typename Node::value_type const&>
{
- friend struct boost::unordered::iterator_detail::iterator<
- NodePointer, Value>;
+ friend struct boost::unordered::iterator_detail::iterator<Node>;
#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
template <typename>
@@ -245,26 +267,26 @@ namespace boost { namespace unordered { namespace iterator_detail {
private:
#endif
-
- typedef NodePointer node_pointer;
- typedef boost::unordered::iterator_detail::iterator<NodePointer, Value>
- iterator;
+ typedef typename Node::node_pointer node_pointer;
+ typedef boost::unordered::iterator_detail::iterator<Node> iterator;
node_pointer node_;
public:
- c_iterator() : node_() {}
+ typedef typename Node::value_type value_type;
- explicit c_iterator(node_pointer const& x) : node_(x) {}
+ c_iterator() BOOST_NOEXCEPT : node_() {}
- c_iterator(boost::unordered::iterator_detail::iterator<
- NodePointer, Value> const& x) : node_(x.node_) {}
+ explicit c_iterator(typename Node::link_pointer x) BOOST_NOEXCEPT :
+ node_(static_cast<node_pointer>(x)) {}
- Value const& operator*() const {
+ c_iterator(iterator const& x) BOOST_NOEXCEPT : node_(x.node_) {}
+
+ value_type const& operator*() const {
return node_->value();
}
- Value const* operator->() const {
+ value_type const* operator->() const {
return &node_->value();
}
@@ -279,11 +301,15 @@ namespace boost { namespace unordered { namespace iterator_detail {
return tmp;
}
- friend bool operator==(c_iterator const& x, c_iterator const& y) {
+ friend bool operator==(c_iterator const& x, c_iterator const& y)
+ BOOST_NOEXCEPT
+ {
return x.node_ == y.node_;
}
- friend bool operator!=(c_iterator const& x, c_iterator const& y) {
+ friend bool operator!=(c_iterator const& x, c_iterator const& y)
+ BOOST_NOEXCEPT
+ {
return x.node_ != y.node_;
}
};
@@ -310,9 +336,6 @@ namespace boost { namespace unordered { namespace detail {
protected:
node_allocator& alloc_;
-
- private:
-
node_pointer node_;
bool node_constructed_;
bool value_constructed_;
@@ -335,7 +358,7 @@ namespace boost { namespace unordered { namespace detail {
void construct_with_value(BOOST_UNORDERED_EMPLACE_ARGS)
{
construct();
- boost::unordered::detail::construct_value_impl(
+ boost::unordered::detail::func::construct_value_impl(
alloc_, node_->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD);
value_constructed_ = true;
}
@@ -344,7 +367,7 @@ namespace boost { namespace unordered { namespace detail {
void construct_with_value2(BOOST_FWD_REF(A0) a0)
{
construct();
- boost::unordered::detail::construct_value_impl(
+ boost::unordered::detail::func::construct_value_impl(
alloc_, node_->value_ptr(),
BOOST_UNORDERED_EMPLACE_ARGS1(boost::forward<A0>(a0)));
value_constructed_ = true;
@@ -374,12 +397,12 @@ namespace boost { namespace unordered { namespace detail {
{
if (node_) {
if (value_constructed_) {
- boost::unordered::detail::destroy_value_impl(alloc_,
+ boost::unordered::detail::func::destroy_value_impl(alloc_,
node_->value_ptr());
}
if (node_constructed_) {
- node_allocator_traits::destroy(alloc_,
+ boost::unordered::detail::func::destroy(
boost::addressof(*node_));
}
@@ -396,9 +419,8 @@ namespace boost { namespace unordered { namespace detail {
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_));
+ new ((void*) boost::addressof(*node_)) node();
+ node_->init(node_);
node_constructed_ = true;
}
else {
@@ -406,7 +428,7 @@ namespace boost { namespace unordered { namespace detail {
if (value_constructed_)
{
- boost::unordered::detail::destroy_value_impl(alloc_,
+ boost::unordered::detail::func::destroy_value_impl(alloc_,
node_->value_ptr());
value_constructed_ = false;
}
@@ -432,8 +454,7 @@ namespace boost { namespace unordered { namespace detail {
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;
+ typedef boost::unordered::iterator_detail::iterator<node> iterator;
node_pointer nodes_;
@@ -445,7 +466,7 @@ namespace boost { namespace unordered { namespace detail {
nodes_()
{
if (b.size_) {
- typename Table::previous_pointer prev = b.get_previous_start();
+ typename Table::link_pointer prev = b.get_previous_start();
nodes_ = static_cast<node_pointer>(prev->next_);
prev->next_ = link_pointer();
b.size_ = 0;
@@ -454,60 +475,61 @@ namespace boost { namespace unordered { namespace detail {
~node_holder();
+ void node_for_assignment()
+ {
+ if (!this->node_ && nodes_) {
+ this->node_ = nodes_;
+ nodes_ = static_cast<node_pointer>(nodes_->next_);
+ this->node_->init(this->node_);
+ this->node_->next_ = link_pointer();
+
+ this->node_constructed_ = true;
+ this->value_constructed_ = true;
+ }
+ }
+
template <typename T>
inline void assign_impl(T const& v) {
- nodes_->value() = v;
+ if (this->node_ && this->value_constructed_) {
+ this->node_->value() = v;
+ }
+ else {
+ this->construct_with_value2(v);
+ }
}
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->construct_with_value2(v);
}
template <typename T>
inline void move_assign_impl(T& v) {
- nodes_->value() = boost::move(v);
+ if (this->node_ && this->value_constructed_) {
+ this->node_->value() = boost::move(v);
+ }
+ else {
+ this->construct_with_value2(boost::move(v));
+ }
}
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);
+ this->construct_with_value2(boost::move(v));
}
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_for_assignment();
+ assign_impl(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();
- }
+ node_for_assignment();
+ move_assign_impl(v);
+ return base::release();
}
iterator begin() const
@@ -523,9 +545,9 @@ namespace boost { namespace unordered { namespace detail {
node_pointer p = nodes_;
nodes_ = static_cast<node_pointer>(p->next_);
- boost::unordered::detail::destroy_value_impl(this->alloc_,
+ boost::unordered::detail::func::destroy_value_impl(this->alloc_,
p->value_ptr());
- node_allocator_traits::destroy(this->alloc_, boost::addressof(*p));
+ boost::unordered::detail::func::destroy(boost::addressof(*p));
node_allocator_traits::deallocate(this->alloc_, p, 1);
}
}
@@ -537,12 +559,12 @@ namespace boost { namespace unordered { namespace detail {
template <typename NodePointer>
struct bucket
{
- typedef NodePointer previous_pointer;
- previous_pointer next_;
+ typedef NodePointer link_pointer;
+ link_pointer next_;
bucket() : next_() {}
- previous_pointer first_from_start()
+ link_pointer first_from_start()
{
return next_;
}
@@ -552,12 +574,12 @@ namespace boost { namespace unordered { namespace detail {
struct ptr_bucket
{
- typedef ptr_bucket* previous_pointer;
- previous_pointer next_;
+ typedef ptr_bucket* link_pointer;
+ link_pointer next_;
ptr_bucket() : next_(0) {}
- previous_pointer first_from_start()
+ link_pointer first_from_start()
{
return this;
}
@@ -568,8 +590,6 @@ namespace boost { namespace unordered { namespace detail {
///////////////////////////////////////////////////////////////////
//
// Hash Policy
- //
- // Don't really want table to derive from this, but will for now.
template <typename SizeT>
struct prime_policy
@@ -645,11 +665,51 @@ namespace boost { namespace unordered { namespace detail {
typedef mix64_policy<std::size_t> type;
};
+ template <typename T>
struct pick_policy :
pick_policy_impl<
std::numeric_limits<std::size_t>::digits,
std::numeric_limits<std::size_t>::radix> {};
+ // While the mix policy is generally faster, the prime policy is a lot
+ // faster when a large number consecutive integers are used, because
+ // there are no collisions. Since that is probably quite common, use
+ // prime policy for integeral types. But not the smaller ones, as they
+ // don't have enough unique values for this to be an issue.
+
+ template <>
+ struct pick_policy<int> {
+ typedef prime_policy<std::size_t> type;
+ };
+
+ template <>
+ struct pick_policy<unsigned int> {
+ typedef prime_policy<std::size_t> type;
+ };
+
+ template <>
+ struct pick_policy<long> {
+ typedef prime_policy<std::size_t> type;
+ };
+
+ template <>
+ struct pick_policy<unsigned long> {
+ typedef prime_policy<std::size_t> type;
+ };
+
+ // TODO: Maybe not if std::size_t is smaller than long long.
+#if !defined(BOOST_NO_LONG_LONG)
+ template <>
+ struct pick_policy<long long> {
+ typedef prime_policy<std::size_t> type;
+ };
+
+ template <>
+ struct pick_policy<unsigned long long> {
+ typedef prime_policy<std::size_t> type;
+ };
+#endif
+
////////////////////////////////////////////////////////////////////////////
// Functions
@@ -664,12 +724,23 @@ namespace boost { namespace unordered { namespace detail {
// 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, bool NoThrowMoveAssign>
+ class set_hash_functions;
template <class H, class P>
class functions
{
- friend class boost::unordered::detail::set_hash_functions<H, P>;
+ public:
+ static const bool nothrow_move_assignable =
+ boost::is_nothrow_move_assignable<H>::value &&
+ boost::is_nothrow_move_assignable<P>::value;
+ static const bool nothrow_move_constructible =
+ boost::is_nothrow_move_constructible<H>::value &&
+ boost::is_nothrow_move_constructible<P>::value;
+
+ private:
+ friend class boost::unordered::detail::set_hash_functions<H, P,
+ nothrow_move_assignable>;
functions& operator=(functions const&);
typedef compressed<H, P> function_pair;
@@ -686,23 +757,40 @@ namespace boost { namespace unordered { namespace detail {
static_cast<void const*>(&funcs_[current_]));
}
+ function_pair& current() {
+ return *static_cast<function_pair*>(
+ static_cast<void*>(&funcs_[current_]));
+ }
+
void construct(bool which, H const& hf, P const& eq)
{
new((void*) &funcs_[which]) function_pair(hf, eq);
}
- void construct(bool which, function_pair const& f)
+ void construct(bool which, function_pair const& f,
+ boost::unordered::detail::false_type =
+ boost::unordered::detail::false_type())
{
new((void*) &funcs_[which]) function_pair(f);
}
+ void construct(bool which, function_pair& f,
+ boost::unordered::detail::true_type)
+ {
+ new((void*) &funcs_[which]) function_pair(f,
+ boost::unordered::detail::move_tag());
+ }
+
void destroy(bool which)
{
- boost::unordered::detail::destroy((function_pair*)(&funcs_[which]));
+ boost::unordered::detail::func::destroy((function_pair*)(&funcs_[which]));
}
public:
+ typedef boost::unordered::detail::set_hash_functions<H, P,
+ nothrow_move_assignable> set_hash_functions;
+
functions(H const& hf, P const& eq)
: current_(false)
{
@@ -715,6 +803,14 @@ namespace boost { namespace unordered { namespace detail {
construct(current_, bf.current());
}
+ functions(functions& bf, boost::unordered::detail::move_tag)
+ : current_(false)
+ {
+ construct(current_, bf.current(),
+ boost::unordered::detail::integral_constant<bool,
+ nothrow_move_constructible>());
+ }
+
~functions() {
this->destroy(current_);
}
@@ -727,26 +823,28 @@ namespace boost { namespace unordered { namespace detail {
return current().second();
}
};
-
+
template <class H, class P>
- class set_hash_functions
+ class set_hash_functions<H, P, false>
{
set_hash_functions(set_hash_functions const&);
set_hash_functions& operator=(set_hash_functions const&);
+
+ typedef functions<H, P> functions_type;
- functions<H,P>& functions_;
+ functions_type& functions_;
bool tmp_functions_;
public:
- set_hash_functions(functions<H,P>& f, H const& h, P const& p)
+ set_hash_functions(functions_type& f, H const& h, P const& p)
: functions_(f),
tmp_functions_(!f.current_)
{
f.construct(tmp_functions_, h, p);
}
- set_hash_functions(functions<H,P>& f, functions<H,P> const& other)
+ set_hash_functions(functions_type& f, functions_type const& other)
: functions_(f),
tmp_functions_(!f.current_)
{
@@ -765,11 +863,42 @@ namespace boost { namespace unordered { namespace detail {
}
};
+ template <class H, class P>
+ class set_hash_functions<H, P, true>
+ {
+ set_hash_functions(set_hash_functions const&);
+ set_hash_functions& operator=(set_hash_functions const&);
+
+ typedef functions<H, P> functions_type;
+
+ functions_type& functions_;
+ H hash_;
+ P pred_;
+
+ public:
+
+ set_hash_functions(functions_type& f, H const& h, P const& p) :
+ functions_(f),
+ hash_(h),
+ pred_(p) {}
+
+ set_hash_functions(functions_type& f, functions_type const& other) :
+ functions_(f),
+ hash_(other.hash_function()),
+ pred_(other.key_eq()) {}
+
+ void commit()
+ {
+ functions_.current().first() = boost::move(hash_);
+ functions_.current().second() = boost::move(pred_);
+ }
+ };
+
////////////////////////////////////////////////////////////////////////////
// rvalue parameters when type can't be a BOOST_RV_REF(T) parameter
// e.g. for int
-#if !defined(BOOST_NO_RVALUE_REFERENCES)
+#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
# define BOOST_UNORDERED_RV_REF(T) BOOST_RV_REF(T)
#else
struct please_ignore_this_overload {
diff --git a/3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp b/3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp
index 3558b1c..58478f9 100644
--- a/3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp
+++ b/3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp
@@ -7,8 +7,9 @@
#ifndef BOOST_UNORDERED_DETAIL_EQUIVALENT_HPP_INCLUDED
#define BOOST_UNORDERED_DETAIL_EQUIVALENT_HPP_INCLUDED
-#if defined(_MSC_VER) && (_MSC_VER >= 1020)
-# pragma once
+#include <boost/config.hpp>
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#pragma once
#endif
#include <boost/unordered/detail/table.hpp>
@@ -25,10 +26,13 @@ namespace boost { namespace unordered { namespace detail {
boost::unordered::detail::value_base<T>
{
typedef typename ::boost::unordered::detail::rebind_wrap<
- A, grouped_node<A, T> >::type::pointer link_pointer;
+ A, grouped_node<A, T> >::type allocator;
+ typedef typename ::boost::unordered::detail::
+ allocator_traits<allocator>::pointer node_pointer;
+ typedef node_pointer link_pointer;
link_pointer next_;
- link_pointer group_prev_;
+ node_pointer group_prev_;
std::size_t hash_;
grouped_node() :
@@ -37,7 +41,7 @@ namespace boost { namespace unordered { namespace detail {
hash_(0)
{}
- void init(link_pointer self)
+ void init(node_pointer self)
{
group_prev_ = self;
}
@@ -48,14 +52,16 @@ namespace boost { namespace unordered { namespace detail {
template <typename T>
struct grouped_ptr_node :
- boost::unordered::detail::value_base<T>,
boost::unordered::detail::ptr_bucket
{
+ typedef T value_type;
typedef boost::unordered::detail::ptr_bucket bucket_base;
+ typedef grouped_ptr_node<T>* node_pointer;
typedef ptr_bucket* link_pointer;
- link_pointer group_prev_;
+ node_pointer group_prev_;
std::size_t hash_;
+ boost::unordered::detail::value_base<T> value_base_;
grouped_ptr_node() :
bucket_base(),
@@ -63,11 +69,15 @@ namespace boost { namespace unordered { namespace detail {
hash_(0)
{}
- void init(link_pointer self)
+ void init(node_pointer self)
{
group_prev_ = self;
}
+ void* address() { return value_base_.address(); }
+ value_type& value() { return value_base_.value(); }
+ value_type* value_ptr() { return value_base_.value_ptr(); }
+
private:
grouped_ptr_node& operator=(grouped_ptr_node const&);
};
@@ -141,7 +151,7 @@ namespace boost { namespace unordered { namespace detail {
typedef boost::unordered::detail::grouped_table_impl<types> table;
typedef boost::unordered::detail::set_extractor<value_type> extractor;
- typedef boost::unordered::detail::pick_policy::type policy;
+ typedef typename boost::unordered::detail::pick_policy<T>::type policy;
};
template <typename A, typename K, typename M, typename H, typename P>
@@ -166,7 +176,7 @@ namespace boost { namespace unordered { namespace detail {
typedef boost::unordered::detail::map_extractor<key_type, value_type>
extractor;
- typedef boost::unordered::detail::pick_policy::type policy;
+ typedef typename boost::unordered::detail::pick_policy<K>::type policy;
};
template <typename Types>
@@ -181,7 +191,6 @@ namespace boost { namespace unordered { namespace detail {
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;
@@ -234,8 +243,7 @@ namespace boost { namespace unordered { namespace detail {
Key const& k,
Pred const& eq) const
{
- std::size_t bucket_index =
- policy::to_bucket(this->bucket_count_, key_hash);
+ std::size_t bucket_index = this->hash_to_bucket(key_hash);
iterator n = this->begin(bucket_index);
for (;;)
@@ -250,13 +258,11 @@ namespace boost { namespace unordered { namespace detail {
}
else
{
- if (policy::to_bucket(this->bucket_count_, node_hash)
- != bucket_index)
+ if (this->hash_to_bucket(node_hash) != bucket_index)
return iterator();
}
- n = iterator(static_cast<node_pointer>(
- static_cast<node_pointer>(n.node_->group_prev_)->next_));
+ n = iterator(n.node_->group_prev_->next_);
}
}
@@ -268,7 +274,7 @@ namespace boost { namespace unordered { namespace detail {
std::size_t x = 0;
node_pointer it = n.node_;
do {
- it = static_cast<node_pointer>(it->group_prev_);
+ it = it->group_prev_;
++x;
} while(it != n.node_);
@@ -280,10 +286,7 @@ namespace boost { namespace unordered { namespace detail {
{
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);
+ n, n.node_ ? iterator(n.node_->group_prev_->next_) : n);
}
// Equality
@@ -296,10 +299,8 @@ namespace boost { namespace unordered { namespace detail {
{
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_));
+ iterator end1(n1.node_->group_prev_->next_);
+ iterator end2(n2.node_->group_prev_->next_);
if (!group_equals(n1, end1, n2, end2)) return false;
n1 = end1;
}
@@ -307,8 +308,6 @@ namespace boost { namespace unordered { namespace detail {
return true;
}
-#if !defined(BOOST_UNORDERED_DEPRECATED_EQUALITY)
-
static bool group_equals(iterator n1, iterator end1,
iterator n2, iterator end2)
{
@@ -369,37 +368,16 @@ namespace boost { namespace unordered { namespace detail {
return count;
}
-#else
-
- 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
-
// Emplace/Insert
static inline void add_after_node(
node_pointer n,
node_pointer pos)
{
- n->next_ = static_cast<node_pointer>(pos->group_prev_)->next_;
+ n->next_ = 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);
+ pos->group_prev_->next_ = n;
+ pos->group_prev_ = n;
}
inline iterator add_node(
@@ -412,37 +390,35 @@ namespace boost { namespace unordered { namespace detail {
if (pos.node_) {
this->add_after_node(n, pos.node_);
if (n->next_) {
- std::size_t next_bucket = policy::to_bucket(
- this->bucket_count_,
+ std::size_t next_bucket = this->hash_to_bucket(
static_cast<node_pointer>(n->next_)->hash_);
- if (next_bucket !=
- policy::to_bucket(this->bucket_count_, key_hash)) {
+ if (next_bucket != this->hash_to_bucket(key_hash)) {
this->get_bucket(next_bucket)->next_ = n;
}
}
}
else {
bucket_pointer b = this->get_bucket(
- policy::to_bucket(this->bucket_count_, key_hash));
+ this->hash_to_bucket(key_hash));
if (!b->next_)
{
- previous_pointer start_node = this->get_previous_start();
+ link_pointer start_node = this->get_previous_start();
if (start_node->next_) {
- this->get_bucket(policy::to_bucket(this->bucket_count_,
+ this->get_bucket(this->hash_to_bucket(
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);
+ start_node->next_ = n;
}
else
{
n->next_ = b->next_->next_;
- b->next_->next_ = static_cast<link_pointer>(n);
+ b->next_->next_ = n;
}
}
++this->size_;
@@ -468,8 +444,8 @@ namespace boost { namespace unordered { namespace detail {
this->add_node(a, key_hash, this->find_node(key_hash, k));
}
-#if defined(BOOST_NO_RVALUE_REFERENCES)
-# if defined(BOOST_NO_VARIADIC_TEMPLATES)
+#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
+# if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
iterator emplace(boost::unordered::detail::emplace_args1<
boost::unordered::detail::please_ignore_this_overload> const&)
{
@@ -545,11 +521,8 @@ namespace boost { namespace unordered { namespace detail {
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_;
+ std::size_t bucket_index = this->hash_to_bucket(key_hash);
+ link_pointer prev = this->get_previous_start(bucket_index);
if (!prev) return 0;
for (;;)
@@ -557,24 +530,21 @@ namespace boost { namespace unordered { namespace detail {
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)
+ if (this->hash_to_bucket(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_);
+ prev = 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));
+ node_pointer first_node = static_cast<node_pointer>(prev->next_);
+ link_pointer end = first_node->group_prev_->next_;
+
+ std::size_t deleted_count = this->delete_nodes(prev, end);
+ this->fix_bucket(bucket_index, prev);
+ return deleted_count;
}
iterator erase(c_iterator r)
@@ -582,132 +552,72 @@ namespace boost { namespace unordered { namespace detail {
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);
-
+ erase_nodes(r.node_, next.node_);
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);
-
+ erase_nodes(r1.node_, r2.node_);
return iterator(r2.node_);
}
- static previous_pointer unlink_node(bucket& b, node_pointer n)
+ link_pointer erase_nodes(node_pointer i, node_pointer j)
{
- 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_;
+ std::size_t bucket_index = this->hash_to_bucket(i->hash_);
+
+ // Split the groups containing 'i' and 'j'.
+ // And get the pointer to the node before i while
+ // we're at it.
+ link_pointer prev = split_groups(i, j);
+
+ // If we don't have a 'prev' it means that i is at the
+ // beginning of a block, so search through the blocks in the
+ // same bucket.
+ if (!prev) {
+ prev = this->get_previous_start(bucket_index);
+ while (prev->next_ != i)
+ prev = static_cast<node_pointer>(prev->next_)->group_prev_;
}
- prev->next_ = static_cast<link_pointer>(next);
+ // Delete the nodes.
+ do {
+ link_pointer group_end =
+ static_cast<node_pointer>(prev->next_)->group_prev_->next_;
+ this->delete_nodes(prev, group_end);
+ bucket_index = this->fix_bucket(bucket_index, prev);
+ } while(prev->next_ != j);
+
return prev;
}
- static previous_pointer unlink_nodes(bucket& b,
- node_pointer begin, node_pointer end)
+ static link_pointer split_groups(node_pointer i, node_pointer j)
{
- previous_pointer prev = static_cast<previous_pointer>(
- begin->group_prev_);
+ node_pointer prev = i->group_prev_;
+ if (prev->next_ != i) prev = node_pointer();
- 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 (j) {
+ node_pointer first = j;
+ while (first != i && first->group_prev_->next_ == first) {
+ first = first->group_prev_;
+ }
- if (end) split_group(end);
+ boost::swap(first->group_prev_, j->group_prev_);
+ if (first == i) return prev;
}
- 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;
- }
+ if (prev) {
+ node_pointer first = prev;
+ while (first->group_prev_->next_ == first) {
+ first = first->group_prev_;
}
+ boost::swap(first->group_prev_, i->group_prev_);
}
- 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
@@ -715,19 +625,16 @@ namespace boost { namespace unordered { namespace detail {
static void fill_buckets(iterator n, table& dst,
NodeCreator& creator)
{
- previous_pointer prev = dst.get_previous_start();
+ link_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_
- ));
+ iterator group_end(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);
+ prev->next_ = first_node;
++dst.size_;
for (++n; n != group_end; ++n)
@@ -748,24 +655,22 @@ namespace boost { namespace unordered { namespace detail {
BOOST_ASSERT(this->buckets_);
this->create_buckets(num_buckets);
- previous_pointer prev = this->get_previous_start();
+ link_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_));
+ 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)
+ static link_pointer place_in_bucket(table& dst,
+ link_pointer prev, node_pointer end)
{
- bucket_pointer b = dst.get_bucket(policy::to_bucket(
- dst.bucket_count_, end->hash_));
+ bucket_pointer b = dst.get_bucket(dst.hash_to_bucket(end->hash_));
if (!b->next_) {
- b->next_ = static_cast<node_pointer>(prev);
- return static_cast<previous_pointer>(end);
+ b->next_ = prev;
+ return end;
}
else {
link_pointer next = end->next_;
diff --git a/3rdParty/Boost/src/boost/unordered/detail/extract_key.hpp b/3rdParty/Boost/src/boost/unordered/detail/extract_key.hpp
index 56a8532..d68a4a7 100644
--- a/3rdParty/Boost/src/boost/unordered/detail/extract_key.hpp
+++ b/3rdParty/Boost/src/boost/unordered/detail/extract_key.hpp
@@ -6,6 +6,11 @@
#ifndef BOOST_UNORDERED_DETAIL_EXTRACT_KEY_HPP_INCLUDED
#define BOOST_UNORDERED_DETAIL_EXTRACT_KEY_HPP_INCLUDED
+#include <boost/config.hpp>
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#pragma once
+#endif
+
#include <boost/unordered/detail/table.hpp>
namespace boost {
@@ -56,30 +61,25 @@ namespace detail {
return no_key();
}
-#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&)
{
return no_key();
}
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+ template <class Arg1, class Arg2, class... Args>
+ static no_key extract(Arg1 const&, Arg2 const&, Args const&...)
+ {
+ return no_key();
+ }
+#else
template <class Arg1, class Arg2>
static no_key extract(Arg1 const&, Arg2 const&)
{
return no_key();
}
#endif
-
- static bool compare_mapped(value_type const&, value_type const&)
- {
- return true;
- }
};
template <class Key, class ValueType>
@@ -93,11 +93,6 @@ namespace detail {
return v.first;
}
- static key_type const& extract(key_type const& v)
- {
- return v;
- }
-
template <class Second>
static key_type const& extract(std::pair<key_type, Second> const& v)
{
@@ -111,21 +106,6 @@ namespace detail {
return v.first;
}
-#if !defined(BOOST_NO_VARIADIC_TEMPLATES)
- template <class Arg1, class... Args>
- static key_type const& extract(key_type const& k,
- Arg1 const&, Args const&...)
- {
- return k;
- }
-
- template <class... Args>
- static no_key extract(Args const&...)
- {
- return no_key();
- }
-#else
-
template <class Arg1>
static key_type const& extract(key_type const& k, Arg1 const&)
{
@@ -143,19 +123,27 @@ namespace detail {
return no_key();
}
- template <class Arg, class Arg1>
- static no_key extract(Arg const&, Arg1 const&)
+ template <class Arg1, class Arg2>
+ static no_key extract(Arg1 const&, Arg2 const&)
+ {
+ return no_key();
+ }
+
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+ template <class Arg1, class Arg2, class Arg3, class... Args>
+ static no_key extract(Arg1 const&, Arg2 const&, Arg3 const&,
+ Args const&...)
{
return no_key();
}
#endif
-#if !defined(BOOST_NO_VARIADIC_TEMPLATES)
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
#define BOOST_UNORDERED_KEY_FROM_TUPLE(namespace_) \
template <typename T2> \
static no_key extract(boost::unordered::piecewise_construct_t, \
- namespace_::tuple<> const&, BOOST_FWD_REF(T2)) \
+ namespace_ tuple<> const&, T2 const&) \
{ \
return no_key(); \
} \
@@ -163,17 +151,17 @@ namespace detail {
template <typename T, typename T2> \
static typename is_key<key_type, T>::type \
extract(boost::unordered::piecewise_construct_t, \
- namespace_::tuple<T> const& k, BOOST_FWD_REF(T2)) \
+ namespace_ tuple<T> const& k, T2 const&) \
{ \
return typename is_key<key_type, T>::type( \
- namespace_::get<0>(k)); \
+ namespace_ get<0>(k)); \
}
#else
#define BOOST_UNORDERED_KEY_FROM_TUPLE(namespace_) \
static no_key extract(boost::unordered::piecewise_construct_t, \
- namespace_::tuple<> const&) \
+ namespace_ tuple<> const&) \
{ \
return no_key(); \
} \
@@ -181,25 +169,19 @@ namespace detail {
template <typename T> \
static typename is_key<key_type, T>::type \
extract(boost::unordered::piecewise_construct_t, \
- namespace_::tuple<T> const& k) \
+ namespace_ tuple<T> const& k) \
{ \
return typename is_key<key_type, T>::type( \
- namespace_::get<0>(k)); \
+ namespace_ get<0>(k)); \
}
#endif
-BOOST_UNORDERED_KEY_FROM_TUPLE(boost)
+BOOST_UNORDERED_KEY_FROM_TUPLE(boost::)
#if !defined(BOOST_NO_CXX11_HDR_TUPLE)
-BOOST_UNORDERED_KEY_FROM_TUPLE(std)
+BOOST_UNORDERED_KEY_FROM_TUPLE(std::)
#endif
-
-
- static bool compare_mapped(value_type const& x, value_type const& y)
- {
- return x.second == y.second;
- }
};
}}}
diff --git a/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp b/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp
index ee8966b..87c2c23 100644
--- a/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp
+++ b/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp
@@ -6,11 +6,11 @@
#ifndef BOOST_UNORDERED_FWD_HPP_INCLUDED
#define BOOST_UNORDERED_FWD_HPP_INCLUDED
-#if defined(_MSC_VER) && (_MSC_VER >= 1020)
-# pragma once
+#include <boost/config.hpp>
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#pragma once
#endif
-
namespace boost
{
namespace unordered
diff --git a/3rdParty/Boost/src/boost/unordered/detail/table.hpp b/3rdParty/Boost/src/boost/unordered/detail/table.hpp
index af376fe..7b4cc0e 100644
--- a/3rdParty/Boost/src/boost/unordered/detail/table.hpp
+++ b/3rdParty/Boost/src/boost/unordered/detail/table.hpp
@@ -7,6 +7,11 @@
#ifndef BOOST_UNORDERED_DETAIL_ALL_HPP_INCLUDED
#define BOOST_UNORDERED_DETAIL_ALL_HPP_INCLUDED
+#include <boost/config.hpp>
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#pragma once
+#endif
+
#include <boost/unordered/detail/buckets.hpp>
#include <boost/unordered/detail/util.hpp>
#include <boost/type_traits/aligned_storage.hpp>
@@ -18,6 +23,18 @@
#pragma warning(disable:4127) // conditional expression is constant
#endif
+#if defined(BOOST_UNORDERED_DEPRECATED_EQUALITY)
+
+#if defined(__EDG__)
+#elif defined(_MSC_VER) || defined(__BORLANDC__) || defined(__DMC__)
+#pragma message("Warning: BOOST_UNORDERED_DEPRECATED_EQUALITY is no longer supported.")
+#elif defined(__GNUC__) || defined(__HP_aCC) || \
+ defined(__SUNPRO_CC) || defined(__IBMCPP__)
+#warning "BOOST_UNORDERED_DEPRECATED_EQUALITY is no longer supported."
+#endif
+
+#endif
+
namespace boost { namespace unordered { namespace detail {
////////////////////////////////////////////////////////////////////////////
@@ -125,7 +142,6 @@ namespace boost { namespace unordered { namespace detail {
template <typename Types>
struct table :
- Types::policy,
boost::unordered::detail::functions<
typename Types::hasher,
typename Types::key_equal>
@@ -148,6 +164,7 @@ namespace boost { namespace unordered { namespace detail {
typedef boost::unordered::detail::functions<
typename Types::hasher,
typename Types::key_equal> functions;
+ typedef typename functions::set_hash_functions set_hash_functions;
typedef typename Types::allocator allocator;
typedef typename boost::unordered::detail::
@@ -164,20 +181,17 @@ namespace boost { namespace unordered { namespace detail {
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;
+ iterator<node> iterator;
typedef boost::unordered::iterator_detail::
- c_iterator<const_node_pointer, node_pointer, value_type> c_iterator;
+ c_iterator<node, const_node_pointer> c_iterator;
typedef boost::unordered::iterator_detail::
- l_iterator<node_pointer, value_type, policy> l_iterator;
+ l_iterator<node, policy> l_iterator;
typedef boost::unordered::iterator_detail::
- cl_iterator<const_node_pointer, node_pointer, value_type, policy>
- cl_iterator;
+ cl_iterator<node, const_node_pointer, policy> cl_iterator;
////////////////////////////////////////////////////////////////////////
// Members
@@ -226,28 +240,31 @@ namespace boost { namespace unordered { namespace detail {
return buckets_ + static_cast<std::ptrdiff_t>(bucket_index);
}
- previous_pointer get_previous_start() const
+ link_pointer get_previous_start() const
{
return get_bucket(bucket_count_)->first_from_start();
}
- previous_pointer get_previous_start(std::size_t bucket_index) const
+ link_pointer get_previous_start(std::size_t bucket_index) const
{
return get_bucket(bucket_index)->next_;
}
iterator begin() const
{
- return size_ ? iterator(static_cast<node_pointer>(
- get_previous_start()->next_)) : iterator();
+ return size_ ? iterator(get_previous_start()->next_) : iterator();
}
iterator begin(std::size_t bucket_index) const
{
if (!size_) return iterator();
- previous_pointer prev = get_previous_start(bucket_index);
- return prev ? iterator(static_cast<node_pointer>(prev->next_)) :
- iterator();
+ link_pointer prev = get_previous_start(bucket_index);
+ return prev ? iterator(prev->next_) : iterator();
+ }
+
+ std::size_t hash_to_bucket(std::size_t hash_value) const
+ {
+ return policy::to_bucket(bucket_count_, hash_value);
}
float load_factor() const
@@ -263,8 +280,7 @@ namespace boost { namespace unordered { namespace detail {
if (!it.node_) return 0;
std::size_t count = 0;
- while(it.node_ && policy::to_bucket(
- bucket_count_, it.node_->hash_) == index)
+ while(it.node_ && hash_to_bucket(it.node_->hash_) == index)
{
++count;
++it;
@@ -353,7 +369,7 @@ namespace boost { namespace unordered { namespace detail {
{}
table(table& x, boost::unordered::detail::move_tag m) :
- functions(x),
+ functions(x, m),
allocators_(x.allocators_, m),
bucket_count_(x.bucket_count_),
size_(x.size_),
@@ -367,8 +383,8 @@ namespace boost { namespace unordered { namespace detail {
}
table(table& x, node_allocator const& a,
- boost::unordered::detail::move_tag) :
- functions(x),
+ boost::unordered::detail::move_tag m) :
+ functions(x, m),
allocators_(a, a),
bucket_count_(x.bucket_count_),
size_(0),
@@ -384,8 +400,8 @@ namespace boost { namespace unordered { namespace detail {
{
if (x.size_) {
create_buckets(bucket_count_);
- copy_nodes<node_allocator> copy(node_alloc());
- table_impl::fill_buckets(x.begin(), *this, copy);
+ copy_nodes<node_allocator> node_creator(node_alloc());
+ table_impl::fill_buckets(x.begin(), *this, node_creator);
}
}
@@ -398,9 +414,9 @@ namespace boost { namespace unordered { namespace detail {
// TODO: Could pick new bucket size?
create_buckets(bucket_count_);
- move_nodes<node_allocator> move(node_alloc());
+ move_nodes<node_allocator> node_creator(node_alloc());
node_holder<node_allocator> nodes(x);
- table_impl::fill_buckets(nodes.begin(), *this, move);
+ table_impl::fill_buckets(nodes.begin(), *this, node_creator);
}
}
@@ -445,6 +461,8 @@ namespace boost { namespace unordered { namespace detail {
void swap_allocators(table& other, false_type)
{
+ boost::unordered::detail::func::ignore_unused_variable_warning(other);
+
// According to 23.2.1.8, if propagate_on_container_swap is
// false the behaviour is undefined unless the allocators
// are equal.
@@ -459,10 +477,8 @@ namespace boost { namespace unordered { namespace detail {
// Only swaps the allocators if propagate_on_container_swap
void swap(table& 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);
+ set_hash_functions op1(*this, x);
+ set_hash_functions op2(x, *this);
// I think swap can throw if Propagate::value,
// since the allocators' swap can throw. Not sure though.
@@ -500,26 +516,28 @@ namespace boost { namespace unordered { namespace detail {
delete_buckets();
}
- void delete_node(c_iterator n)
+ void delete_node(link_pointer prev)
{
- 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);
+ node_pointer n = static_cast<node_pointer>(prev->next_);
+ prev->next_ = n->next_;
+
+ boost::unordered::detail::func::destroy_value_impl(node_alloc(),
+ n->value_ptr());
+ boost::unordered::detail::func::destroy(boost::addressof(*n));
+ node_allocator_traits::deallocate(node_alloc(), n, 1);
--size_;
}
- std::size_t delete_nodes(c_iterator begin, c_iterator end)
+ std::size_t delete_nodes(link_pointer prev, link_pointer end)
{
+ BOOST_ASSERT(prev->next_ != end);
+
std::size_t count = 0;
- while(begin != end) {
- c_iterator n = begin;
- ++begin;
- delete_node(n);
+ do {
+ delete_node(prev);
++count;
- }
+ } while (prev->next_ != end);
return count;
}
@@ -527,12 +545,12 @@ namespace boost { namespace unordered { namespace detail {
void delete_buckets()
{
if(buckets_) {
- delete_nodes(begin(), iterator());
+ if (size_) delete_nodes(get_previous_start(), link_pointer());
if (bucket::extra_node) {
node_pointer n = static_cast<node_pointer>(
get_bucket(bucket_count_)->next_);
- node_allocator_traits::destroy(node_alloc(),
+ boost::unordered::detail::func::destroy(
boost::addressof(*n));
node_allocator_traits::deallocate(node_alloc(), n, 1);
}
@@ -547,10 +565,9 @@ namespace boost { namespace unordered { namespace detail {
void clear()
{
- if(!size_) return;
+ if (!size_) return;
- delete_nodes(begin(), iterator());
- get_previous_start()->next_ = link_pointer();
+ delete_nodes(get_previous_start(), link_pointer());
clear_buckets();
BOOST_ASSERT(!size_);
@@ -570,7 +587,7 @@ namespace boost { namespace unordered { namespace detail {
bucket_pointer end = get_bucket(bucket_count_ + 1);
for(bucket_pointer it = buckets_; it != end; ++it)
{
- bucket_allocator_traits::destroy(bucket_alloc(),
+ boost::unordered::detail::func::destroy(
boost::addressof(*it));
}
@@ -579,86 +596,33 @@ namespace boost { namespace unordered { namespace detail {
}
////////////////////////////////////////////////////////////////////////
- // Fix buckets after erase
+ // Fix buckets after delete
+ //
- // 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)
+ std::size_t fix_bucket(std::size_t bucket_index, link_pointer prev)
{
- if (!next)
- {
- if (this_bucket->next_ == prev)
- this_bucket->next_ = node_pointer();
- }
- else
+ link_pointer end = prev->next_;
+ std::size_t bucket_index2 = bucket_index;
+
+ if (end)
{
- 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();
- }
- }
- }
+ bucket_index2 = hash_to_bucket(
+ static_cast<node_pointer>(end)->hash_);
- // 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 begin and end are in the same bucket, then
+ // there's nothing to do.
+ if (bucket_index == bucket_index2) return bucket_index2;
- // 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;
- }
- }
+ // Update the bucket containing end.
+ get_bucket(bucket_index2)->next_ = prev;
}
- // 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();
- }
- };
+ // Check if this bucket is now empty.
+ bucket_pointer this_bucket = get_bucket(bucket_index);
+ if (this_bucket->next_ == prev)
+ this_bucket->next_ = link_pointer();
- // Finally fix the bucket containing the trailing node.
- if (n) {
- get_bucket(
- policy::to_bucket(bucket_count_, n->hash_))->next_
- = prev;
- }
+ return bucket_index2;
}
////////////////////////////////////////////////////////////////////////
@@ -678,8 +642,7 @@ namespace boost { namespace unordered { namespace detail {
void assign(table const& x, false_type)
{
// Strong exception safety.
- boost::unordered::detail::set_hash_functions<hasher, key_equal>
- new_func_this(*this, x);
+ set_hash_functions new_func_this(*this, x);
new_func_this.commit();
mlf_ = x.mlf_;
recalculate_max_load();
@@ -696,8 +659,8 @@ namespace boost { namespace unordered { namespace detail {
// 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);
+ assign_nodes<table> node_creator(*this);
+ table_impl::fill_buckets(x.begin(), *this, node_creator);
}
void assign(table const& x, true_type)
@@ -707,8 +670,7 @@ namespace boost { namespace unordered { namespace detail {
assign(x, false_type());
}
else {
- boost::unordered::detail::set_hash_functions<hasher, key_equal>
- new_func_this(*this, x);
+ set_hash_functions new_func_this(*this, x);
// Delete everything with current allocators before assigning
// the new ones.
@@ -724,8 +686,8 @@ namespace boost { namespace unordered { namespace detail {
// 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);
+ copy_nodes<node_allocator> node_creator(node_alloc());
+ table_impl::fill_buckets(x.begin(), *this, node_creator);
}
}
}
@@ -755,8 +717,7 @@ namespace boost { namespace unordered { namespace detail {
move_assign_no_alloc(x);
}
else {
- boost::unordered::detail::set_hash_functions<hasher, key_equal>
- new_func_this(*this, x);
+ set_hash_functions new_func_this(*this, x);
new_func_this.commit();
mlf_ = x.mlf_;
recalculate_max_load();
@@ -773,16 +734,15 @@ namespace boost { namespace unordered { namespace detail {
// 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);
+ move_assign_nodes<table> node_creator(*this);
node_holder<node_allocator> nodes(x);
- table_impl::fill_buckets(nodes.begin(), *this, assign);
+ table_impl::fill_buckets(nodes.begin(), *this, node_creator);
}
}
void move_assign_no_alloc(table& x)
{
- boost::unordered::detail::set_hash_functions<hasher, key_equal>
- new_func_this(*this, x);
+ set_hash_functions new_func_this(*this, x);
// No throw from here.
mlf_ = x.mlf_;
max_load_ = x.max_load_;
diff --git a/3rdParty/Boost/src/boost/unordered/detail/unique.hpp b/3rdParty/Boost/src/boost/unordered/detail/unique.hpp
index 8805652..f76ca5a 100644
--- a/3rdParty/Boost/src/boost/unordered/detail/unique.hpp
+++ b/3rdParty/Boost/src/boost/unordered/detail/unique.hpp
@@ -7,8 +7,9 @@
#ifndef BOOST_UNORDERED_DETAIL_UNIQUE_HPP_INCLUDED
#define BOOST_UNORDERED_DETAIL_UNIQUE_HPP_INCLUDED
-#if defined(_MSC_VER) && (_MSC_VER >= 1020)
-# pragma once
+#include <boost/config.hpp>
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#pragma once
#endif
#include <boost/unordered/detail/table.hpp>
@@ -27,7 +28,10 @@ namespace boost { namespace unordered { namespace detail {
boost::unordered::detail::value_base<T>
{
typedef typename ::boost::unordered::detail::rebind_wrap<
- A, unique_node<A, T> >::type::pointer link_pointer;
+ A, unique_node<A, T> >::type allocator;
+ typedef typename ::boost::unordered::detail::
+ allocator_traits<allocator>::pointer node_pointer;
+ typedef node_pointer link_pointer;
link_pointer next_;
std::size_t hash_;
@@ -37,7 +41,7 @@ namespace boost { namespace unordered { namespace detail {
hash_(0)
{}
- void init(link_pointer)
+ void init(node_pointer)
{
}
@@ -47,23 +51,29 @@ namespace boost { namespace unordered { namespace detail {
template <typename T>
struct ptr_node :
- boost::unordered::detail::value_base<T>,
boost::unordered::detail::ptr_bucket
{
+ typedef T value_type;
typedef boost::unordered::detail::ptr_bucket bucket_base;
+ typedef ptr_node<T>* node_pointer;
typedef ptr_bucket* link_pointer;
std::size_t hash_;
+ boost::unordered::detail::value_base<T> value_base_;
ptr_node() :
bucket_base(),
hash_(0)
{}
- void init(link_pointer)
+ void init(node_pointer)
{
}
+ void* address() { return value_base_.address(); }
+ value_type& value() { return value_base_.value(); }
+ value_type* value_ptr() { return value_base_.value_ptr(); }
+
private:
ptr_node& operator=(ptr_node const&);
};
@@ -136,7 +146,7 @@ namespace boost { namespace unordered { namespace detail {
typedef boost::unordered::detail::table_impl<types> table;
typedef boost::unordered::detail::set_extractor<value_type> extractor;
- typedef boost::unordered::detail::pick_policy::type policy;
+ typedef typename boost::unordered::detail::pick_policy<T>::type policy;
};
template <typename A, typename K, typename M, typename H, typename P>
@@ -161,7 +171,7 @@ namespace boost { namespace unordered { namespace detail {
typedef boost::unordered::detail::map_extractor<key_type, value_type>
extractor;
- typedef boost::unordered::detail::pick_policy::type policy;
+ typedef typename boost::unordered::detail::pick_policy<K>::type policy;
};
template <typename Types>
@@ -176,7 +186,6 @@ namespace boost { namespace unordered { namespace detail {
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;
@@ -231,8 +240,7 @@ namespace boost { namespace unordered { namespace detail {
Key const& k,
Pred const& eq) const
{
- std::size_t bucket_index =
- policy::to_bucket(this->bucket_count_, key_hash);
+ std::size_t bucket_index = this->hash_to_bucket(key_hash);
iterator n = this->begin(bucket_index);
for (;;)
@@ -247,8 +255,7 @@ namespace boost { namespace unordered { namespace detail {
}
else
{
- if (policy::to_bucket(this->bucket_count_, node_hash)
- != bucket_index)
+ if (this->hash_to_bucket(node_hash) != bucket_index)
return iterator();
}
@@ -291,13 +298,8 @@ namespace boost { namespace unordered { namespace detail {
{
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;
@@ -312,27 +314,26 @@ namespace boost { namespace unordered { namespace detail {
node_pointer n = a.release();
n->hash_ = key_hash;
- bucket_pointer b = this->get_bucket(
- policy::to_bucket(this->bucket_count_, key_hash));
+ bucket_pointer b = this->get_bucket(this->hash_to_bucket(key_hash));
if (!b->next_)
{
- previous_pointer start_node = this->get_previous_start();
+ link_pointer start_node = this->get_previous_start();
if (start_node->next_) {
- this->get_bucket(policy::to_bucket(this->bucket_count_,
+ this->get_bucket(this->hash_to_bucket(
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);
+ start_node->next_ = n;
}
else
{
n->next_ = b->next_->next_;
- b->next_->next_ = static_cast<link_pointer>(n);
+ b->next_->next_ = n;
}
++this->size_;
@@ -341,8 +342,6 @@ namespace boost { namespace unordered { namespace detail {
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);
@@ -360,8 +359,8 @@ namespace boost { namespace unordered { namespace detail {
return *add_node(a, key_hash);
}
-#if defined(BOOST_NO_RVALUE_REFERENCES)
-# if defined(BOOST_NO_VARIADIC_TEMPLATES)
+#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
+# if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
emplace_return emplace(boost::unordered::detail::emplace_args1<
boost::unordered::detail::please_ignore_this_overload> const&)
{
@@ -381,7 +380,7 @@ namespace boost { namespace unordered { namespace detail {
template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
emplace_return emplace(BOOST_UNORDERED_EMPLACE_ARGS)
{
-#if !defined(BOOST_NO_VARIADIC_TEMPLATES)
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
return emplace_impl(
extractor::extract(BOOST_UNORDERED_EMPLACE_FORWARD),
BOOST_UNORDERED_EMPLACE_FORWARD);
@@ -392,7 +391,7 @@ namespace boost { namespace unordered { namespace detail {
#endif
}
-#if defined(BOOST_NO_VARIADIC_TEMPLATES)
+#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
template <typename A0>
emplace_return emplace(
boost::unordered::detail::emplace_args1<A0> const& args)
@@ -518,11 +517,8 @@ namespace boost { namespace unordered { namespace detail {
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_;
+ std::size_t bucket_index = this->hash_to_bucket(key_hash);
+ link_pointer prev = this->get_previous_start(bucket_index);
if (!prev) return 0;
for (;;)
@@ -530,21 +526,20 @@ namespace boost { namespace unordered { namespace detail {
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)
+ if (this->hash_to_bucket(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_);
+ prev = prev->next_;
}
- 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));
+ link_pointer end = static_cast<node_pointer>(prev->next_)->next_;
+
+ std::size_t deleted_count = this->delete_nodes(prev, end);
+ this->fix_bucket(bucket_index, prev);
+ return deleted_count;
}
iterator erase(c_iterator r)
@@ -552,46 +547,30 @@ namespace boost { namespace unordered { namespace detail {
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);
-
+ erase_nodes(r.node_, next.node_);
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);
-
+ erase_nodes(r1.node_, r2.node_);
return iterator(r2.node_);
}
- static previous_pointer unlink_node(bucket& b, node_pointer n)
+ void erase_nodes(node_pointer i, node_pointer j)
{
- return unlink_nodes(b, n, static_cast<node_pointer>(n->next_));
- }
+ std::size_t bucket_index = this->hash_to_bucket(i->hash_);
- 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;
+ // Find the node before i.
+ link_pointer prev = this->get_previous_start(bucket_index);
+ while(prev->next_ != i) prev = prev->next_;
+
+ // Delete the nodes.
+ do {
+ this->delete_node(prev);
+ bucket_index = this->fix_bucket(bucket_index, prev);
+ } while (prev->next_ != j);
}
////////////////////////////////////////////////////////////////////////
@@ -601,12 +580,12 @@ namespace boost { namespace unordered { namespace detail {
static void fill_buckets(iterator n, table& dst,
NodeCreator& creator)
{
- previous_pointer prev = dst.get_previous_start();
+ link_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);
+ prev->next_ = node;
++dst.size_;
++n;
@@ -620,28 +599,26 @@ namespace boost { namespace unordered { namespace detail {
BOOST_ASSERT(this->buckets_);
this->create_buckets(num_buckets);
- previous_pointer prev = this->get_previous_start();
+ link_pointer prev = this->get_previous_start();
while (prev->next_)
prev = place_in_bucket(*this, 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)
+ static link_pointer place_in_bucket(table& dst, link_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_));
+ bucket_pointer b = dst.get_bucket(dst.hash_to_bucket(n->hash_));
if (!b->next_) {
b->next_ = prev;
- return static_cast<previous_pointer>(n);
+ return n;
}
else {
prev->next_ = n->next_;
n->next_ = b->next_->next_;
- b->next_->next_ = static_cast<link_pointer>(n);
+ b->next_->next_ = n;
return prev;
}
}
diff --git a/3rdParty/Boost/src/boost/unordered/detail/util.hpp b/3rdParty/Boost/src/boost/unordered/detail/util.hpp
index a901477..3428ed7 100644
--- a/3rdParty/Boost/src/boost/unordered/detail/util.hpp
+++ b/3rdParty/Boost/src/boost/unordered/detail/util.hpp
@@ -7,8 +7,9 @@
#ifndef BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED
#define BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED
-#if defined(_MSC_VER) && (_MSC_VER >= 1020)
-# pragma once
+#include <boost/config.hpp>
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#pragma once
#endif
#include <boost/type_traits/is_convertible.hpp>
@@ -28,6 +29,11 @@ namespace boost { namespace unordered { namespace detail {
struct move_tag {};
struct empty_emplace {};
+ namespace func {
+ template <class T>
+ inline void ignore_unused_variable_warning(T const&) {}
+ }
+
////////////////////////////////////////////////////////////////////////////
// iterator SFINAE
diff --git a/3rdParty/Boost/src/boost/unordered/unordered_map.hpp b/3rdParty/Boost/src/boost/unordered/unordered_map.hpp
index d606739..9b18079 100644
--- a/3rdParty/Boost/src/boost/unordered/unordered_map.hpp
+++ b/3rdParty/Boost/src/boost/unordered/unordered_map.hpp
@@ -9,8 +9,9 @@
#ifndef BOOST_UNORDERED_UNORDERED_MAP_HPP_INCLUDED
#define BOOST_UNORDERED_UNORDERED_MAP_HPP_INCLUDED
-#if defined(_MSC_VER) && (_MSC_VER >= 1020)
-# pragma once
+#include <boost/config.hpp>
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#pragma once
#endif
#include <boost/unordered/unordered_map_fwd.hpp>
@@ -117,17 +118,19 @@ namespace unordered
#if defined(BOOST_UNORDERED_USE_MOVE)
unordered_map(BOOST_RV_REF(unordered_map) other)
+ BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)
: table_(other.table_, boost::unordered::detail::move_tag())
{
}
-#elif !defined(BOOST_NO_RVALUE_REFERENCES)
+#elif !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
unordered_map(unordered_map&& other)
+ BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)
: table_(other.table_, boost::unordered::detail::move_tag())
{
}
#endif
-#if !defined(BOOST_NO_RVALUE_REFERENCES)
+#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
unordered_map(unordered_map&&, allocator_type const&);
#endif
@@ -142,7 +145,7 @@ namespace unordered
// Destructor
- ~unordered_map();
+ ~unordered_map() BOOST_NOEXCEPT;
// Assign
@@ -165,7 +168,7 @@ namespace unordered
return *this;
}
-#if !defined(BOOST_NO_RVALUE_REFERENCES)
+#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
unordered_map& operator=(unordered_map&& x)
{
table_.move_assign(x.table_);
@@ -178,60 +181,60 @@ namespace unordered
unordered_map& operator=(std::initializer_list<value_type>);
#endif
- allocator_type get_allocator() const
+ allocator_type get_allocator() const BOOST_NOEXCEPT
{
return table_.node_alloc();
}
// size and capacity
- bool empty() const
+ bool empty() const BOOST_NOEXCEPT
{
return table_.size_ == 0;
}
- size_type size() const
+ size_type size() const BOOST_NOEXCEPT
{
return table_.size_;
}
- size_type max_size() const;
+ size_type max_size() const BOOST_NOEXCEPT;
// iterators
- iterator begin()
+ iterator begin() BOOST_NOEXCEPT
{
return table_.begin();
}
- const_iterator begin() const
+ const_iterator begin() const BOOST_NOEXCEPT
{
return table_.begin();
}
- iterator end()
+ iterator end() BOOST_NOEXCEPT
{
return iterator();
}
- const_iterator end() const
+ const_iterator end() const BOOST_NOEXCEPT
{
return const_iterator();
}
- const_iterator cbegin() const
+ const_iterator cbegin() const BOOST_NOEXCEPT
{
return table_.begin();
}
- const_iterator cend() const
+ const_iterator cend() const BOOST_NOEXCEPT
{
return const_iterator();
}
// emplace
-#if !defined(BOOST_NO_VARIADIC_TEMPLATES)
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
template <class... Args>
std::pair<iterator, bool> emplace(BOOST_FWD_REF(Args)... args)
{
@@ -449,12 +452,12 @@ namespace unordered
// bucket interface
- size_type bucket_count() const
+ size_type bucket_count() const BOOST_NOEXCEPT
{
return table_.bucket_count_;
}
- size_type max_bucket_count() const
+ size_type max_bucket_count() const BOOST_NOEXCEPT
{
return table_.max_bucket_count();
}
@@ -463,8 +466,7 @@ namespace unordered
size_type bucket(const key_type& k) const
{
- return table::to_bucket(table_.bucket_count_,
- table_.hash(k));
+ return table_.hash_to_bucket(table_.hash(k));
}
local_iterator begin(size_type n)
@@ -502,13 +504,13 @@ namespace unordered
// hash policy
- float max_load_factor() const
+ float max_load_factor() const BOOST_NOEXCEPT
{
return table_.mlf_;
}
- float load_factor() const;
- void max_load_factor(float);
+ float load_factor() const BOOST_NOEXCEPT;
+ void max_load_factor(float) BOOST_NOEXCEPT;
void rehash(size_type);
void reserve(size_type);
@@ -599,17 +601,19 @@ namespace unordered
#if defined(BOOST_UNORDERED_USE_MOVE)
unordered_multimap(BOOST_RV_REF(unordered_multimap) other)
+ BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)
: table_(other.table_, boost::unordered::detail::move_tag())
{
}
-#elif !defined(BOOST_NO_RVALUE_REFERENCES)
+#elif !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
unordered_multimap(unordered_multimap&& other)
+ BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)
: table_(other.table_, boost::unordered::detail::move_tag())
{
}
#endif
-#if !defined(BOOST_NO_RVALUE_REFERENCES)
+#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
unordered_multimap(unordered_multimap&&, allocator_type const&);
#endif
@@ -624,7 +628,7 @@ namespace unordered
// Destructor
- ~unordered_multimap();
+ ~unordered_multimap() BOOST_NOEXCEPT;
// Assign
@@ -648,7 +652,7 @@ namespace unordered
return *this;
}
-#if !defined(BOOST_NO_RVALUE_REFERENCES)
+#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
unordered_multimap& operator=(unordered_multimap&& x)
{
table_.move_assign(x.table_);
@@ -661,60 +665,60 @@ namespace unordered
unordered_multimap& operator=(std::initializer_list<value_type>);
#endif
- allocator_type get_allocator() const
+ allocator_type get_allocator() const BOOST_NOEXCEPT
{
return table_.node_alloc();
}
// size and capacity
- bool empty() const
+ bool empty() const BOOST_NOEXCEPT
{
return table_.size_ == 0;
}
- size_type size() const
+ size_type size() const BOOST_NOEXCEPT
{
return table_.size_;
}
- size_type max_size() const;
+ size_type max_size() const BOOST_NOEXCEPT;
// iterators
- iterator begin()
+ iterator begin() BOOST_NOEXCEPT
{
return table_.begin();
}
- const_iterator begin() const
+ const_iterator begin() const BOOST_NOEXCEPT
{
return table_.begin();
}
- iterator end()
+ iterator end() BOOST_NOEXCEPT
{
return iterator();
}
- const_iterator end() const
+ const_iterator end() const BOOST_NOEXCEPT
{
return const_iterator();
}
- const_iterator cbegin() const
+ const_iterator cbegin() const BOOST_NOEXCEPT
{
return table_.begin();
}
- const_iterator cend() const
+ const_iterator cend() const BOOST_NOEXCEPT
{
return const_iterator();
}
// emplace
-#if !defined(BOOST_NO_VARIADIC_TEMPLATES)
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
template <class... Args>
iterator emplace(BOOST_FWD_REF(Args)... args)
{
@@ -928,12 +932,12 @@ namespace unordered
// bucket interface
- size_type bucket_count() const
+ size_type bucket_count() const BOOST_NOEXCEPT
{
return table_.bucket_count_;
}
- size_type max_bucket_count() const
+ size_type max_bucket_count() const BOOST_NOEXCEPT
{
return table_.max_bucket_count();
}
@@ -942,8 +946,7 @@ namespace unordered
size_type bucket(const key_type& k) const
{
- return table::to_bucket(table_.bucket_count_,
- table_.hash(k));
+ return table_.hash_to_bucket(table_.hash(k));
}
local_iterator begin(size_type n)
@@ -981,13 +984,13 @@ namespace unordered
// hash policy
- float max_load_factor() const
+ float max_load_factor() const BOOST_NOEXCEPT
{
return table_.mlf_;
}
- float load_factor() const;
- void max_load_factor(float);
+ float load_factor() const BOOST_NOEXCEPT;
+ void max_load_factor(float) BOOST_NOEXCEPT;
void rehash(size_type);
void reserve(size_type);
@@ -1059,7 +1062,7 @@ namespace unordered
}
template <class K, class T, class H, class P, class A>
- unordered_map<K,T,H,P,A>::~unordered_map() {}
+ unordered_map<K,T,H,P,A>::~unordered_map() BOOST_NOEXCEPT {}
template <class K, class T, class H, class P, class A>
unordered_map<K,T,H,P,A>::unordered_map(
@@ -1068,7 +1071,7 @@ namespace unordered
{
}
-#if !defined(BOOST_NO_RVALUE_REFERENCES)
+#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
template <class K, class T, class H, class P, class A>
unordered_map<K,T,H,P,A>::unordered_map(
@@ -1107,7 +1110,7 @@ namespace unordered
// size and capacity
template <class K, class T, class H, class P, class A>
- std::size_t unordered_map<K,T,H,P,A>::max_size() const
+ std::size_t unordered_map<K,T,H,P,A>::max_size() const BOOST_NOEXCEPT
{
return table_.max_size();
}
@@ -1276,13 +1279,13 @@ namespace unordered
// hash policy
template <class K, class T, class H, class P, class A>
- float unordered_map<K,T,H,P,A>::load_factor() const
+ float unordered_map<K,T,H,P,A>::load_factor() const BOOST_NOEXCEPT
{
return table_.load_factor();
}
template <class K, class T, class H, class P, class A>
- void unordered_map<K,T,H,P,A>::max_load_factor(float m)
+ void unordered_map<K,T,H,P,A>::max_load_factor(float m) BOOST_NOEXCEPT
{
table_.max_load_factor(m);
}
@@ -1392,7 +1395,7 @@ namespace unordered
}
template <class K, class T, class H, class P, class A>
- unordered_multimap<K,T,H,P,A>::~unordered_multimap() {}
+ unordered_multimap<K,T,H,P,A>::~unordered_multimap() BOOST_NOEXCEPT {}
template <class K, class T, class H, class P, class A>
unordered_multimap<K,T,H,P,A>::unordered_multimap(
@@ -1401,7 +1404,7 @@ namespace unordered
{
}
-#if !defined(BOOST_NO_RVALUE_REFERENCES)
+#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
template <class K, class T, class H, class P, class A>
unordered_multimap<K,T,H,P,A>::unordered_multimap(
@@ -1440,7 +1443,7 @@ namespace unordered
// size and capacity
template <class K, class T, class H, class P, class A>
- std::size_t unordered_multimap<K,T,H,P,A>::max_size() const
+ std::size_t unordered_multimap<K,T,H,P,A>::max_size() const BOOST_NOEXCEPT
{
return table_.max_size();
}
@@ -1588,13 +1591,13 @@ namespace unordered
// hash policy
template <class K, class T, class H, class P, class A>
- float unordered_multimap<K,T,H,P,A>::load_factor() const
+ float unordered_multimap<K,T,H,P,A>::load_factor() const BOOST_NOEXCEPT
{
return table_.load_factor();
}
template <class K, class T, class H, class P, class A>
- void unordered_multimap<K,T,H,P,A>::max_load_factor(float m)
+ void unordered_multimap<K,T,H,P,A>::max_load_factor(float m) BOOST_NOEXCEPT
{
table_.max_load_factor(m);
}
diff --git a/3rdParty/Boost/src/boost/unordered/unordered_map_fwd.hpp b/3rdParty/Boost/src/boost/unordered/unordered_map_fwd.hpp
index 980bb3e..1eb26ce 100644
--- a/3rdParty/Boost/src/boost/unordered/unordered_map_fwd.hpp
+++ b/3rdParty/Boost/src/boost/unordered/unordered_map_fwd.hpp
@@ -6,11 +6,11 @@
#ifndef BOOST_UNORDERED_MAP_FWD_HPP_INCLUDED
#define BOOST_UNORDERED_MAP_FWD_HPP_INCLUDED
-#if defined(_MSC_VER) && (_MSC_VER >= 1020)
-# pragma once
+#include <boost/config.hpp>
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#pragma once
#endif
-#include <boost/config.hpp>
#include <memory>
#include <functional>
#include <boost/functional/hash_fwd.hpp>