Subject: [Boost-commit] svn:boost r78432 - in branches/release: . boost boost/unordered boost/unordered/detail libs libs/functional libs/functional/hash/test libs/unordered libs/unordered/doc libs/unordered/test/exception libs/unordered/test/helpers libs/unordered/test/unordered
From: dnljms_at_[hidden]
Date: 2012-05-12 04:14:10
Author: danieljames
Date: 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
New Revision: 78432
URL: http://svn.boost.org/trac/boost/changeset/78432
Log:
Unordered: Merge unordered from trunk.
- Activate `std::allocator_traits` for gcc 4.7 and Visual C++ 11.
- Implement variadic construct in `boost::unordered::detail::allocator_traits`
when variadics, rvalue references and SFINAE expression are available.
- Use variadic construct from `allocator_traits`, or when not available move
the logic for constructing `value_type` to a lower level, so the container
code is a bit simpler.
- Avoid `-Wshadow` warnings. Fixes #6190.
- Implement `reserve`. Fixes #6857.
Properties modified:
branches/release/ (props changed)
branches/release/boost/ (props changed)
branches/release/boost/unordered/ (props changed)
branches/release/libs/ (props changed)
branches/release/libs/functional/ (props changed)
branches/release/libs/unordered/ (props changed)
Text files modified:
branches/release/boost/unordered/detail/allocator_helpers.hpp | 455 +++++++++++++++++++++++++++------------
branches/release/boost/unordered/detail/buckets.hpp | 104 +++++---
branches/release/boost/unordered/detail/emplace_args.hpp | 46 +++
branches/release/boost/unordered/detail/equivalent.hpp | 102 ++++++--
branches/release/boost/unordered/detail/table.hpp | 22 +
branches/release/boost/unordered/detail/unique.hpp | 110 ++++++---
branches/release/boost/unordered/unordered_map.hpp | 14 +
branches/release/boost/unordered/unordered_set.hpp | 14 +
branches/release/libs/functional/hash/test/Jamfile.v2 | 4
branches/release/libs/unordered/doc/changes.qbk | 8
branches/release/libs/unordered/doc/ref.php | 12 +
branches/release/libs/unordered/doc/ref.xml | 48 ++++
branches/release/libs/unordered/test/exception/assign_exception_tests.cpp | 2
branches/release/libs/unordered/test/exception/constructor_exception_tests.cpp | 2
branches/release/libs/unordered/test/exception/copy_exception_tests.cpp | 2
branches/release/libs/unordered/test/exception/erase_exception_tests.cpp | 2
branches/release/libs/unordered/test/exception/insert_exception_tests.cpp | 2
branches/release/libs/unordered/test/exception/rehash_exception_tests.cpp | 2
branches/release/libs/unordered/test/exception/swap_exception_tests.cpp | 2
branches/release/libs/unordered/test/helpers/list.hpp | 6
branches/release/libs/unordered/test/helpers/tracker.hpp | 12
branches/release/libs/unordered/test/unordered/assign_tests.cpp | 2
branches/release/libs/unordered/test/unordered/bucket_tests.cpp | 2
branches/release/libs/unordered/test/unordered/constructor_tests.cpp | 2
branches/release/libs/unordered/test/unordered/copy_tests.cpp | 2
branches/release/libs/unordered/test/unordered/erase_tests.cpp | 2
branches/release/libs/unordered/test/unordered/find_tests.cpp | 2
branches/release/libs/unordered/test/unordered/insert_tests.cpp | 2
branches/release/libs/unordered/test/unordered/load_factor_tests.cpp | 2
branches/release/libs/unordered/test/unordered/move_tests.cpp | 2
branches/release/libs/unordered/test/unordered/rehash_tests.cpp | 77 ++++++
branches/release/libs/unordered/test/unordered/swap_tests.cpp | 2
32 files changed, 767 insertions(+), 301 deletions(-)
Modified: branches/release/boost/unordered/detail/allocator_helpers.hpp
==============================================================================
--- branches/release/boost/unordered/detail/allocator_helpers.hpp (original)
+++ branches/release/boost/unordered/detail/allocator_helpers.hpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -15,47 +15,41 @@
# pragma once
#endif
-#include <boost/config.hpp>
-#include <boost/detail/select_type.hpp>
-#include <boost/utility/enable_if.hpp>
-#include <boost/preprocessor/cat.hpp>
-#include <boost/preprocessor/enum.hpp>
-#include <boost/limits.hpp>
-#include <boost/type_traits/add_lvalue_reference.hpp>
-#include <boost/pointer_to_other.hpp>
+#include <boost/unordered/detail/emplace_args.hpp>
#include <boost/assert.hpp>
#include <boost/utility/addressof.hpp>
-#if !defined(BOOST_UNORDERED_USE_ALLOCATOR_TRAITS)
-// An allocator_traits test is currently failing for gcc 4.7 on mingw. I think
-// this is because it's an older development version. Temporarily disabling
-// std::allocator_traits in order ot get clean test results. Will reactivate
-// later.
+////////////////////////////////////////////////////////////////////////////////
+//
+// Pick which version of allocator_traits to use
+//
+// 0 = Own partial implementation
+// 1 = std::allocator_traits
+// 2 = boost::container::allocator_traits
-/*
+#if !defined(BOOST_UNORDERED_USE_ALLOCATOR_TRAITS)
# if defined(__GXX_EXPERIMENTAL_CXX0X__) && \
(__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 7))
# define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 1
+# elif defined(BOOST_MSVC)
+# if BOOST_MSVC < 1400
+ // Use container's allocator_traits for older versions of Visual
+ // C++ as I don't test with them.
+# define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 2
+# elif BOOST_MSVC >= 1700
+# define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 1
+# endif
# endif
-*/
-
-// Use container's allocator_traits for older versions of Visual C++ as I don't
-// test with them.
-# if defined(BOOST_MSVC) && BOOST_MSVC < 1400
-# define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 2
-# endif
-
#endif
#if !defined(BOOST_UNORDERED_USE_ALLOCATOR_TRAITS)
# define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 0
#endif
-#if BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 1
-# include <memory>
-#elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 2
-# include <boost/container/allocator/allocator_traits.hpp>
-#endif
+////////////////////////////////////////////////////////////////////////////////
+//
+// Some utilities for implementing allocator_traits, but useful elsewhere so
+// they're always defined.
#if !defined(BOOST_NO_0X_HDR_TYPE_TRAITS)
# include <type_traits>
@@ -102,48 +96,22 @@
#endif
////////////////////////////////////////////////////////////////////////////
- // Bits and pieces for implementing traits
+ // Expression test mechanism
//
- // Some of these are also used elsewhere
-
- template <typename T> typename boost::add_lvalue_reference<T>::type make();
- struct choice9 { typedef char (&type)[9]; };
- struct choice8 : choice9 { typedef char (&type)[8]; };
- struct choice7 : choice8 { typedef char (&type)[7]; };
- struct choice6 : choice7 { typedef char (&type)[6]; };
- struct choice5 : choice6 { typedef char (&type)[5]; };
- struct choice4 : choice5 { typedef char (&type)[4]; };
- struct choice3 : choice4 { typedef char (&type)[3]; };
- struct choice2 : choice3 { typedef char (&type)[2]; };
- struct choice1 : choice2 { typedef char (&type)[1]; };
- choice1 choose();
-
- typedef choice1::type yes_type;
- typedef choice2::type no_type;
-
- struct private_type
- {
- private_type const &operator,(int) const;
- };
-
- template <typename T>
- no_type is_private_type(T const&);
- yes_type is_private_type(private_type const&);
-
- struct convert_from_anything {
- template <typename T>
- convert_from_anything(T const&);
- };
+ // When SFINAE expressions are available, define
+ // BOOST_UNORDERED_HAS_FUNCTION which can check if a function call is
+ // supported by a class, otherwise define BOOST_UNORDERED_HAS_MEMBER which
+ // can detect if a class has the specified member, but not that it has the
+ // correct type, this is good enough for a passable impression of
+ // allocator_traits.
#if !defined(BOOST_NO_SFINAE_EXPR)
-# define BOOST_UNORDERED_HAVE_CALL_DETECTION 1
-
template <typename T, unsigned int> struct expr_test;
template <typename T> struct expr_test<T, sizeof(char)> : T {};
template <typename U> static char for_expr_test(U const&);
-#define BOOST_UNORDERED_CHECK_EXPRESSION(count, result, expression) \
+# define BOOST_UNORDERED_CHECK_EXPRESSION(count, result, expression) \
template <typename U> \
static typename boost::unordered::detail::expr_test< \
BOOST_PP_CAT(choice, result), \
@@ -152,12 +120,12 @@
0)))>::type test( \
BOOST_PP_CAT(choice, count))
-#define BOOST_UNORDERED_DEFAULT_EXPRESSION(count, result) \
+# define BOOST_UNORDERED_DEFAULT_EXPRESSION(count, result) \
template <typename U> \
static BOOST_PP_CAT(choice, result)::type test( \
BOOST_PP_CAT(choice, count))
-#define BOOST_UNORDERED_HAS_FUNCTION(name, thing, args, _) \
+# define BOOST_UNORDERED_HAS_FUNCTION(name, thing, args, _) \
struct BOOST_PP_CAT(has_, name) \
{ \
BOOST_UNORDERED_CHECK_EXPRESSION(1, 1, \
@@ -169,11 +137,9 @@
#else
-# define BOOST_UNORDERED_HAVE_CALL_DETECTION 0
-
template <typename T> struct identity { typedef T type; };
-#define BOOST_UNORDERED_CHECK_MEMBER(count, result, name, member) \
+# define BOOST_UNORDERED_CHECK_MEMBER(count, result, name, member) \
\
typedef typename boost::unordered::detail::identity<member>::type \
BOOST_PP_CAT(check, count); \
@@ -187,11 +153,11 @@
BOOST_PP_CAT(test, count)<&U::name>::type \
test(BOOST_PP_CAT(choice, count))
-#define BOOST_UNORDERED_DEFAULT_MEMBER(count, result) \
+# define BOOST_UNORDERED_DEFAULT_MEMBER(count, result) \
template <class U> static BOOST_PP_CAT(choice, result)::type \
test(BOOST_PP_CAT(choice, count))
-#define BOOST_UNORDERED_HAS_MEMBER(name) \
+# define BOOST_UNORDERED_HAS_MEMBER(name) \
struct BOOST_PP_CAT(has_, name) \
{ \
struct impl { \
@@ -211,97 +177,90 @@
#endif
- ////////////////////////////////////////////////////////////////////////////
- // Allocator traits
- //
- // Uses the standard versions if available.
- // (although untested as I don't have access to a standard version yet)
-
-#if BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 1
-
- template <typename Alloc>
- struct allocator_traits : std::allocator_traits<Alloc> {};
-
- template <typename Alloc, typename T>
- struct rebind_wrap
- {
- typedef typename std::allocator_traits<Alloc>::
- template rebind_alloc<T> type;
- };
-
-#elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 2
+}}}
- template <typename Alloc>
- struct allocator_traits :
- boost::container::allocator_traits<Alloc> {};
+////////////////////////////////////////////////////////////////////////////////
+//
+// Allocator traits
+//
+// First our implementation, then later light wrappers around the alternatives
+
+#if BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 0
+
+# include <boost/limits.hpp>
+# include <boost/utility/enable_if.hpp>
+# include <boost/pointer_to_other.hpp>
+# if defined(BOOST_NO_SFINAE_EXPR)
+# include <boost/type_traits/is_same.hpp>
+# endif
- template <typename Alloc, typename T>
- struct rebind_wrap :
- boost::container::allocator_traits<Alloc>::
- template portable_rebind_alloc<T>
- {};
+# if defined(BOOST_UNORDERED_VARIADIC_MOVE) && \
+ !defined(BOOST_NO_SFINAE_EXPR)
+# define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 1
+# else
+# define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 0
+# endif
-#else
+namespace boost { namespace unordered { namespace detail {
// TODO: Does this match std::allocator_traits<Alloc>::rebind_alloc<T>?
template <typename Alloc, typename T>
struct rebind_wrap
{
- typedef typename Alloc::BOOST_NESTED_TEMPLATE rebind<T>::other
- type;
+ typedef typename Alloc::BOOST_NESTED_TEMPLATE rebind<T>::other type;
};
-#if defined(BOOST_MSVC) && BOOST_MSVC <= 1400
+# if defined(BOOST_MSVC) && BOOST_MSVC <= 1400
- #define BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(tname) \
- template <typename Tp, typename Default> \
- struct default_type_ ## tname { \
+# define BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(tname) \
+ template <typename Tp, typename Default> \
+ struct default_type_ ## tname { \
\
- template <typename X> \
- static choice1::type test(choice1, typename X::tname* = 0); \
+ template <typename X> \
+ static choice1::type test(choice1, typename X::tname* = 0); \
\
- template <typename X> \
- static choice2::type test(choice2, void* = 0); \
+ template <typename X> \
+ static choice2::type test(choice2, void* = 0); \
\
- struct DefaultWrap { typedef Default tname; }; \
+ struct DefaultWrap { typedef Default tname; }; \
\
- enum { value = (1 == sizeof(test<Tp>(choose()))) }; \
+ enum { value = (1 == sizeof(test<Tp>(choose()))) }; \
\
- typedef typename boost::detail::if_true<value>:: \
- BOOST_NESTED_TEMPLATE then<Tp, DefaultWrap> \
- ::type::tname type; \
- }
+ typedef typename boost::detail::if_true<value>:: \
+ BOOST_NESTED_TEMPLATE then<Tp, DefaultWrap> \
+ ::type::tname type; \
+ }
-#else
+# else
template <typename T, typename T2>
struct sfinae : T2 {};
- #define BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(tname) \
- template <typename Tp, typename Default> \
- struct default_type_ ## tname { \
+# define BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(tname) \
+ template <typename Tp, typename Default> \
+ struct default_type_ ## tname { \
\
- template <typename X> \
- static typename boost::unordered::detail::sfinae< \
- typename X::tname, choice1>::type \
- test(choice1); \
+ template <typename X> \
+ static typename boost::unordered::detail::sfinae< \
+ typename X::tname, choice1>::type \
+ test(choice1); \
\
- template <typename X> \
- static choice2::type test(choice2); \
+ template <typename X> \
+ static choice2::type test(choice2); \
\
- struct DefaultWrap { typedef Default tname; }; \
+ struct DefaultWrap { typedef Default tname; }; \
\
- enum { value = (1 == sizeof(test<Tp>(choose()))) }; \
+ enum { value = (1 == sizeof(test<Tp>(choose()))) }; \
\
- typedef typename boost::detail::if_true<value>:: \
- BOOST_NESTED_TEMPLATE then<Tp, DefaultWrap> \
- ::type::tname type; \
- }
+ typedef typename boost::detail::if_true<value>:: \
+ BOOST_NESTED_TEMPLATE then<Tp, DefaultWrap> \
+ ::type::tname type; \
+ }
-#endif
+# endif
- #define BOOST_UNORDERED_DEFAULT_TYPE(T,tname, arg) \
- typename default_type_ ## tname<T, arg>::type
+# define BOOST_UNORDERED_DEFAULT_TYPE(T,tname, arg) \
+ typename default_type_ ## tname<T, arg>::type
BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(pointer);
BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(const_pointer);
@@ -313,7 +272,8 @@
BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(propagate_on_container_move_assignment);
BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(propagate_on_container_swap);
-#if BOOST_UNORDERED_HAVE_CALL_DETECTION
+# if !defined(BOOST_NO_SFINAE_EXPR)
+
template <typename T>
BOOST_UNORDERED_HAS_FUNCTION(
select_on_container_copy_construction, U const, (), 0
@@ -324,18 +284,33 @@
max_size, U const, (), 0
);
+# if defined(BOOST_UNORDERED_VARIADIC_MOVE)
+
+ template <typename T, typename ValueType, typename... Args>
+ BOOST_UNORDERED_HAS_FUNCTION(
+ construct, U, (
+ boost::unordered::detail::make<ValueType*>(),
+ boost::unordered::detail::make<Args const>()...), 2
+ );
+
+# else
+
template <typename T, typename ValueType>
BOOST_UNORDERED_HAS_FUNCTION(
- construct, U, (
- boost::unordered::detail::make<ValueType*>(),
- boost::unordered::detail::make<ValueType const>()), 2
+ construct, U, (
+ boost::unordered::detail::make<ValueType*>(),
+ boost::unordered::detail::make<ValueType const>()), 2
);
+# endif
+
template <typename T, typename ValueType>
BOOST_UNORDERED_HAS_FUNCTION(
destroy, U, (boost::unordered::detail::make<ValueType*>()), 1
);
-#else
+
+# else
+
template <typename T>
BOOST_UNORDERED_HAS_MEMBER(select_on_container_copy_construction);
@@ -347,7 +322,8 @@
template <typename T, typename ValueType>
BOOST_UNORDERED_HAS_MEMBER(destroy);
-#endif
+
+# endif
template <typename Alloc>
inline typename boost::enable_if_c<
@@ -415,7 +391,7 @@
// TODO: rebind_alloc and rebind_traits
- static pointer allocate(Alloc& a, size_type n)
+ static pointer allocate(Alloc& a, size_type n)
{ return a.allocate(n); }
// I never use this, so I'll just comment it out for now.
@@ -423,13 +399,49 @@
//static pointer allocate(Alloc& a, size_type n,
// const_void_pointer hint)
// { return DEFAULT_FUNC(allocate, pointer)(a, n, hint); }
-
+
static void deallocate(Alloc& a, pointer p, size_type n)
{ a.deallocate(p, n); }
public:
- // Only supporting the basic copy constructor for now.
+# if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT
+
+ template <typename T, typename... Args>
+ static typename boost::enable_if_c<
+ boost::unordered::detail::has_construct<Alloc, T, Args...>
+ ::value>::type
+ construct(Alloc& a, T* p, Args&&... x)
+ {
+ a.construct(p, boost::forward<Args>(x)...);
+ }
+
+ template <typename T, typename... Args>
+ static typename boost::disable_if_c<
+ boost::unordered::detail::has_construct<Alloc, T, Args...>
+ ::value>::type
+ construct(Alloc&, T* p, Args&&... x)
+ {
+ new ((void*) p) T(boost::forward<Args>(x)...);
+ }
+
+ template <typename T>
+ static typename boost::enable_if_c<
+ boost::unordered::detail::has_destroy<Alloc, T>::value>::type
+ destroy(Alloc& a, T* p)
+ {
+ a.destroy(p);
+ }
+
+ template <typename T>
+ static typename boost::disable_if_c<
+ boost::unordered::detail::has_destroy<Alloc, T>::value>::type
+ destroy(Alloc&, T* p)
+ {
+ boost::unordered::detail::destroy(p);
+ }
+
+# elif !defined(BOOST_NO_SFINAE_EXPR)
template <typename T>
static typename boost::enable_if_c<
@@ -463,19 +475,67 @@
boost::unordered::detail::destroy(p);
}
+# else
+
+ // If we don't have SFINAE expressions, only call construct for the
+ // copy constructor for the allocator's value_type - as that's
+ // the only construct method that old fashioned allocators support.
+
+ template <typename T>
+ static typename boost::enable_if_c<
+ boost::unordered::detail::has_construct<Alloc, T>::value &&
+ boost::is_same<T, value_type>::value
+ >::type
+ construct(Alloc& a, T* p, T const& x)
+ {
+ a.construct(p, x);
+ }
+
+ template <typename T>
+ static typename boost::disable_if_c<
+ boost::unordered::detail::has_construct<Alloc, T>::value &&
+ boost::is_same<T, value_type>::value
+ >::type
+ construct(Alloc&, T* p, T const& x)
+ {
+ new ((void*) p) T(x);
+ }
+
+ template <typename T>
+ static typename boost::enable_if_c<
+ boost::unordered::detail::has_destroy<Alloc, T>::value &&
+ boost::is_same<T, value_type>::value
+ >::type
+ destroy(Alloc& a, T* p)
+ {
+ a.destroy(p);
+ }
+
+ template <typename T>
+ static typename boost::disable_if_c<
+ boost::unordered::detail::has_destroy<Alloc, T>::value &&
+ boost::is_same<T, value_type>::value
+ >::type
+ destroy(Alloc&, T* p)
+ {
+ boost::unordered::detail::destroy(p);
+ }
+
+# endif
+
static size_type max_size(const Alloc& a)
{
return boost::unordered::detail::call_max_size<size_type>(a);
}
// Allocator propagation on construction
-
+
static Alloc select_on_container_copy_construction(Alloc const& rhs)
{
return boost::unordered::detail::
call_select_on_container_copy_construction(rhs);
}
-
+
// Allocator propagation on assignment and swap.
// Return true if lhs is modified.
typedef BOOST_UNORDERED_DEFAULT_TYPE(
@@ -488,12 +548,117 @@
Alloc,propagate_on_container_swap,false_type)
propagate_on_container_swap;
};
+}}}
+
+# undef BOOST_UNORDERED_DEFAULT_TYPE_TMPLT
+# undef BOOST_UNORDERED_DEFAULT_TYPE
+
+////////////////////////////////////////////////////////////////////////////////
+//
+// std::allocator_traits
+
+#elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 1
+
+# include <memory>
+
+# define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 1
+
+namespace boost { namespace unordered { namespace detail {
+
+ template <typename Alloc>
+ struct allocator_traits : std::allocator_traits<Alloc> {};
+
+ template <typename Alloc, typename T>
+ struct rebind_wrap
+ {
+ typedef typename std::allocator_traits<Alloc>::
+ template rebind_alloc<T> type;
+ };
+}}}
+
+////////////////////////////////////////////////////////////////////////////////
+//
+// boost::container::allocator_traits
+
+#elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 2
-#undef BOOST_UNORDERED_DEFAULT_TYPE_TMPLT
-#undef BOOST_UNORDERED_DEFAULT_TYPE
+# include <boost/container/allocator_traits.hpp>
+
+# define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 0
+
+namespace boost { namespace unordered { namespace detail {
+
+ template <typename Alloc>
+ struct allocator_traits :
+ boost::container::allocator_traits<Alloc> {};
+
+ template <typename Alloc, typename T>
+ struct rebind_wrap :
+ boost::container::allocator_traits<Alloc>::
+ template portable_rebind_alloc<T>
+ {};
+
+}}}
+
+#else
+
+#error "Invalid BOOST_UNORDERED_USE_ALLOCATOR_TRAITS value."
#endif
+////////////////////////////////////////////////////////////////////////////////
+//
+// Some helper functions for allocating & constructing
+
+namespace boost { namespace unordered { namespace detail {
+
+ ////////////////////////////////////////////////////////////////////////////
+ //
+ // construct_node/destroy_node
+ //
+ // Construct a node using the best available method.
+
+#if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT
+
+ template <typename Alloc, typename T, BOOST_UNORDERED_EMPLACE_TEMPLATE>
+ inline void construct_node(Alloc& a, T* p, BOOST_UNORDERED_EMPLACE_ARGS)
+ {
+ boost::unordered::detail::allocator_traits<Alloc>::construct(
+ a, p, BOOST_UNORDERED_EMPLACE_FORWARD);
+ }
+
+ template <typename Alloc, typename T>
+ inline void destroy_node(Alloc& a, T* p)
+ {
+ boost::unordered::detail::allocator_traits<Alloc>::destroy(a, p);
+ }
+
+#else
+
+ template <typename Alloc, typename T, BOOST_UNORDERED_EMPLACE_TEMPLATE>
+ inline void construct_node(Alloc& a, T* p, BOOST_UNORDERED_EMPLACE_ARGS)
+ {
+ boost::unordered::detail::allocator_traits<Alloc>::construct(a, p, T());
+ try {
+ boost::unordered::detail::construct_impl(
+ p->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD);
+ } catch(...) {
+ boost::unordered::detail::allocator_traits<Alloc>::destroy(a, p);
+ throw;
+ }
+ }
+
+ template <typename Alloc, typename T>
+ inline void destroy_node(Alloc& a, T* p)
+ {
+ boost::unordered::detail::destroy(p->value_ptr());
+ boost::unordered::detail::allocator_traits<Alloc>::destroy(a, p);
+ }
+
+#endif
+
+ ////////////////////////////////////////////////////////////////////////////
+ //
// array_constructor
//
// Allocate and construct an array in an exception safe manner, and
@@ -549,7 +714,9 @@
ptr_ = pointer();
return p;
}
+
private:
+
array_constructor(array_constructor const&);
array_constructor& operator=(array_constructor const&);
};
Modified: branches/release/boost/unordered/detail/buckets.hpp
==============================================================================
--- branches/release/boost/unordered/detail/buckets.hpp (original)
+++ branches/release/boost/unordered/detail/buckets.hpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -13,7 +13,6 @@
#include <boost/unordered/detail/util.hpp>
#include <boost/unordered/detail/allocator_helpers.hpp>
-#include <boost/unordered/detail/emplace_args.hpp>
#include <boost/type_traits/aligned_storage.hpp>
#include <boost/type_traits/alignment_of.hpp>
#include <boost/swap.hpp>
@@ -54,16 +53,14 @@
node_allocator& alloc_;
node_pointer node_;
- bool node_constructed_;
- bool value_constructed_;
+ bool constructed_;
public:
node_constructor(node_allocator& n) :
alloc_(n),
node_(),
- node_constructed_(false),
- value_constructed_(false)
+ constructed_(false)
{
}
@@ -74,26 +71,40 @@
template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
void construct_value(BOOST_UNORDERED_EMPLACE_ARGS)
{
- BOOST_ASSERT(node_ && node_constructed_ && !value_constructed_);
- boost::unordered::detail::construct_impl(
- node_->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD);
- value_constructed_ = true;
+ BOOST_ASSERT(node_ && !constructed_);
+ boost::unordered::detail::construct_node(alloc_,
+ boost::addressof(*node_), BOOST_UNORDERED_EMPLACE_FORWARD);
+ node_->init(static_cast<typename node::link_pointer>(node_));
+ constructed_ = true;
}
template <typename A0>
void construct_value2(BOOST_FWD_REF(A0) a0)
{
- BOOST_ASSERT(node_ && node_constructed_ && !value_constructed_);
- boost::unordered::detail::construct_impl2(
- node_->value_ptr(), boost::forward<A0>(a0));
- value_constructed_ = true;
+ BOOST_ASSERT(node_ && !constructed_);
+# if defined(BOOST_UNORDERED_VARIADIC_MOVE)
+ boost::unordered::detail::construct_node(alloc_,
+ boost::addressof(*node_), boost::forward<A0>(a0));
+# else
+ boost::unordered::detail::construct_node(alloc_,
+ boost::addressof(*node_),
+ boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0)));
+# endif
+ constructed_ = true;
+ node_->init(static_cast<typename node::link_pointer>(node_));
}
value_type const& value() const {
- BOOST_ASSERT(node_ && node_constructed_ && value_constructed_);
+ BOOST_ASSERT(node_ && constructed_);
return node_->value();
}
+ node_pointer get()
+ {
+ return node_;
+ }
+
// no throw
node_pointer release()
{
@@ -111,12 +122,8 @@
node_constructor<Alloc>::~node_constructor()
{
if (node_) {
- if (value_constructed_) {
- boost::unordered::detail::destroy(node_->value_ptr());
- }
-
- if (node_constructed_) {
- node_allocator_traits::destroy(alloc_,
+ if (constructed_) {
+ boost::unordered::detail::destroy_node(alloc_,
boost::addressof(*node_));
}
@@ -128,24 +135,13 @@
void node_constructor<Alloc>::construct_node()
{
if(!node_) {
- node_constructed_ = false;
- value_constructed_ = false;
-
+ constructed_ = false;
node_ = node_allocator_traits::allocate(alloc_, 1);
-
- node_allocator_traits::construct(alloc_,
- boost::addressof(*node_), node());
- node_->init(static_cast<typename node::link_pointer>(node_));
- node_constructed_ = true;
}
- else {
- BOOST_ASSERT(node_constructed_);
-
- if (value_constructed_)
- {
- boost::unordered::detail::destroy(node_->value_ptr());
- value_constructed_ = false;
- }
+ else if (constructed_) {
+ boost::unordered::detail::destroy_node(alloc_,
+ boost::addressof(*node_));
+ constructed_ = false;
}
}
@@ -183,6 +179,16 @@
enum { extra_node = false };
};
+
+ template <typename LinkPointer>
+ struct node_base
+ {
+ typedef LinkPointer link_pointer;
+ link_pointer next_;
+
+ node_base() : next_() {}
+ };
+
}}}
namespace boost { namespace unordered { namespace iterator_detail {
@@ -718,6 +724,14 @@
node_constructor a(this->node_alloc());
a.construct_node();
+ // Since this node is just to mark the beginning it doesn't
+ // contain a value, so just construct node::node_base
+ // which containers the pointer to the next element.
+ node_allocator_traits::construct(node_alloc(),
+ static_cast<typename node::node_base*>(
+ boost::addressof(*a.get())),
+ typename node::node_base());
+
(constructor.get() +
static_cast<std::ptrdiff_t>(this->bucket_count_))->next_ =
a.release();
@@ -762,9 +776,8 @@
inline void delete_node(c_iterator n)
{
- boost::unordered::detail::destroy(n.node_->value_ptr());
- node_allocator_traits::destroy(node_alloc(),
- boost::addressof(*n.node_));
+ boost::unordered::detail::destroy_node(
+ node_alloc(), boost::addressof(*n.node_));
node_allocator_traits::deallocate(node_alloc(), n.node_, 1);
--size_;
}
@@ -786,7 +799,8 @@
inline void delete_extra_node(bucket_pointer) {}
inline void delete_extra_node(node_pointer n) {
- node_allocator_traits::destroy(node_alloc(), boost::addressof(*n));
+ node_allocator_traits::destroy(node_alloc(),
+ static_cast<typename node::node_base*>(boost::addressof(*n)));
node_allocator_traits::deallocate(node_alloc(), n, 1);
}
@@ -847,22 +861,24 @@
// This is called after erasing a node or group of nodes to fix up
// the bucket pointers.
- void fix_buckets(bucket_pointer bucket,
+ void fix_buckets(bucket_pointer this_bucket,
previous_pointer prev, node_pointer next)
{
if (!next)
{
- if (bucket->next_ == prev) bucket->next_ = node_pointer();
+ if (this_bucket->next_ == prev)
+ this_bucket->next_ = node_pointer();
}
else
{
bucket_pointer next_bucket = this->get_bucket(
policy::to_bucket(this->bucket_count_, next->hash_));
- if (next_bucket != bucket)
+ if (next_bucket != this_bucket)
{
next_bucket->next_ = prev;
- if (bucket->next_ == prev) bucket->next_ = node_pointer();
+ if (this_bucket->next_ == prev)
+ this_bucket->next_ = node_pointer();
}
}
}
Modified: branches/release/boost/unordered/detail/emplace_args.hpp
==============================================================================
--- branches/release/boost/unordered/detail/emplace_args.hpp (original)
+++ branches/release/boost/unordered/detail/emplace_args.hpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -12,6 +12,7 @@
# pragma once
#endif
+#include <boost/unordered/detail/fwd.hpp>
#include <boost/move/move.hpp>
#include <boost/preprocessor/cat.hpp>
#include <boost/preprocessor/inc.hpp>
@@ -21,7 +22,10 @@
#include <boost/preprocessor/repetition/enum_binary_params.hpp>
#include <boost/preprocessor/repetition/repeat_from_to.hpp>
#include <boost/type_traits/is_class.hpp>
+#include <boost/type_traits/add_lvalue_reference.hpp>
#include <boost/tuple/tuple.hpp>
+#include <boost/utility/enable_if.hpp>
+#include <boost/detail/select_type.hpp>
#include <utility>
#if !defined(BOOST_NO_0X_HDR_TUPLE)
@@ -46,6 +50,38 @@
namespace boost { namespace unordered { namespace detail {
////////////////////////////////////////////////////////////////////////////
+ // Bits and pieces for implementing traits
+
+ template <typename T> typename boost::add_lvalue_reference<T>::type make();
+ struct choice9 { typedef char (&type)[9]; };
+ struct choice8 : choice9 { typedef char (&type)[8]; };
+ struct choice7 : choice8 { typedef char (&type)[7]; };
+ struct choice6 : choice7 { typedef char (&type)[6]; };
+ struct choice5 : choice6 { typedef char (&type)[5]; };
+ struct choice4 : choice5 { typedef char (&type)[4]; };
+ struct choice3 : choice4 { typedef char (&type)[3]; };
+ struct choice2 : choice3 { typedef char (&type)[2]; };
+ struct choice1 : choice2 { typedef char (&type)[1]; };
+ choice1 choose();
+
+ typedef choice1::type yes_type;
+ typedef choice2::type no_type;
+
+ struct private_type
+ {
+ private_type const &operator,(int) const;
+ };
+
+ template <typename T>
+ no_type is_private_type(T const&);
+ yes_type is_private_type(private_type const&);
+
+ struct convert_from_anything {
+ template <typename T>
+ convert_from_anything(T const&);
+ };
+
+ ////////////////////////////////////////////////////////////////////////////
// emplace_args
//
// Either forwarding variadic arguments, or storing the arguments in
@@ -75,7 +111,7 @@
{ \
BOOST_PP_REPEAT_##z(n, BOOST_UNORDERED_EARGS_MEMBER, _) \
BOOST_PP_CAT(emplace_args, n) ( \
- BOOST_PP_ENUM_BINARY_PARAMS_Z(z, n, Arg, a) \
+ BOOST_PP_ENUM_BINARY_PARAMS_Z(z, n, Arg, b) \
) : BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_EARGS_INIT, _) \
{} \
\
@@ -85,12 +121,12 @@
inline BOOST_PP_CAT(emplace_args, n) < \
BOOST_PP_ENUM_PARAMS_Z(z, n, A) \
> create_emplace_args( \
- BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a) \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, b) \
) \
{ \
BOOST_PP_CAT(emplace_args, n) < \
BOOST_PP_ENUM_PARAMS_Z(z, n, A) \
- > e(BOOST_PP_ENUM_PARAMS_Z(z, n, a)); \
+ > e(BOOST_PP_ENUM_PARAMS_Z(z, n, b)); \
return e; \
}
@@ -102,7 +138,7 @@
#define BOOST_UNORDERED_EARGS_INIT(z, n, _) \
BOOST_PP_CAT(a, n)( \
- boost::forward<BOOST_PP_CAT(A,n)>(BOOST_PP_CAT(a, n)))
+ boost::forward<BOOST_PP_CAT(A,n)>(BOOST_PP_CAT(b, n)))
#else
@@ -112,7 +148,7 @@
BOOST_PP_CAT(Arg, n) BOOST_PP_CAT(a, n);
#define BOOST_UNORDERED_EARGS_INIT(z, n, _) \
- BOOST_PP_CAT(a, n)(BOOST_PP_CAT(a, n))
+ BOOST_PP_CAT(a, n)(BOOST_PP_CAT(b, n))
#endif
Modified: branches/release/boost/unordered/detail/equivalent.hpp
==============================================================================
--- branches/release/boost/unordered/detail/equivalent.hpp (original)
+++ branches/release/boost/unordered/detail/equivalent.hpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -12,7 +12,6 @@
#endif
#include <boost/unordered/detail/table.hpp>
-#include <boost/unordered/detail/emplace_args.hpp>
#include <boost/unordered/detail/extract_key.hpp>
namespace boost { namespace unordered { namespace detail {
@@ -23,20 +22,40 @@
template <typename A, typename T>
struct grouped_node :
+ boost::unordered::detail::node_base<
+ typename ::boost::unordered::detail::rebind_wrap<
+ A, grouped_node<A, T> >::type::pointer
+ >,
boost::unordered::detail::value_base<T>
{
typedef typename ::boost::unordered::detail::rebind_wrap<
A, grouped_node<A, T> >::type::pointer link_pointer;
+ typedef boost::unordered::detail::node_base<link_pointer> node_base;
- link_pointer next_;
link_pointer group_prev_;
std::size_t hash_;
+#if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT
+ template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
+ grouped_node(BOOST_UNORDERED_EMPLACE_ARGS) :
+ node_base(),
+ group_prev_(),
+ hash_(0)
+ {
+ boost::unordered::detail::construct_impl(
+ this->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD);
+ }
+
+ ~grouped_node() {
+ boost::unordered::detail::destroy(this->value_ptr());
+ }
+#else
grouped_node() :
- next_(),
+ node_base(),
group_prev_(),
hash_(0)
{}
+#endif
void init(link_pointer self)
{
@@ -50,16 +69,33 @@
boost::unordered::detail::ptr_bucket
{
typedef boost::unordered::detail::ptr_bucket bucket_base;
+ typedef bucket_base node_base;
typedef ptr_bucket* link_pointer;
link_pointer group_prev_;
std::size_t hash_;
+#if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT
+ template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
+ grouped_ptr_node(BOOST_UNORDERED_EMPLACE_ARGS) :
+ bucket_base(),
+ group_prev_(0),
+ hash_(0)
+ {
+ boost::unordered::detail::construct_impl(
+ this->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD);
+ }
+
+ ~grouped_ptr_node() {
+ boost::unordered::detail::destroy(this->value_ptr());
+ }
+#else
grouped_ptr_node() :
bucket_base(),
group_prev_(0),
hash_(0)
{}
+#endif
void init(link_pointer self)
{
@@ -221,12 +257,12 @@
template <class Key, class Pred>
iterator find_node_impl(
- std::size_t hash,
+ std::size_t key_hash,
Key const& k,
Pred const& eq) const
{
std::size_t bucket_index =
- policy::to_bucket(this->bucket_count_, hash);
+ policy::to_bucket(this->bucket_count_, key_hash);
iterator n = this->get_start(bucket_index);
for (;;)
@@ -234,7 +270,7 @@
if (!n.node_) return n;
std::size_t node_hash = n.node_->hash_;
- if (hash == node_hash)
+ if (key_hash == node_hash)
{
if (eq(k, this->get_key(*n)))
return n;
@@ -256,14 +292,14 @@
iterator n = this->find_node(k);
if (!n.node_) return 0;
- std::size_t count = 0;
+ std::size_t x = 0;
node_pointer it = n.node_;
do {
it = static_cast<node_pointer>(it->group_prev_);
- ++count;
+ ++x;
} while(it != n.node_);
- return count;
+ return x;
}
std::pair<iterator, iterator>
@@ -396,11 +432,11 @@
inline iterator add_node(
node_constructor& a,
- std::size_t hash,
+ std::size_t key_hash,
iterator pos)
{
node_pointer n = a.release();
- n->hash_ = hash;
+ n->hash_ = key_hash;
if (pos.node_) {
this->add_after_node(n, pos.node_);
if (n->next_) {
@@ -408,14 +444,14 @@
this->bucket_count_,
static_cast<node_pointer>(n->next_)->hash_);
if (next_bucket !=
- policy::to_bucket(this->bucket_count_, hash)) {
+ policy::to_bucket(this->bucket_count_, key_hash)) {
this->get_bucket(next_bucket)->next_ = n;
}
}
}
else {
bucket_pointer b = this->get_bucket(
- policy::to_bucket(this->bucket_count_, hash));
+ policy::to_bucket(this->bucket_count_, key_hash));
if (!b->next_)
{
@@ -444,20 +480,20 @@
iterator emplace_impl(node_constructor& a)
{
key_type const& k = this->get_key(a.value());
- std::size_t hash = this->hash(k);
- iterator position = this->find_node(hash, k);
+ std::size_t key_hash = this->hash(k);
+ iterator position = this->find_node(key_hash, k);
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
this->reserve_for_insert(this->size_ + 1);
- return this->add_node(a, hash, position);
+ return this->add_node(a, key_hash, position);
}
void emplace_impl_no_rehash(node_constructor& a)
{
key_type const& k = this->get_key(a.value());
- std::size_t hash = this->hash(k);
- this->add_node(a, hash, this->find_node(hash, k));
+ std::size_t key_hash = this->hash(k);
+ this->add_node(a, key_hash, this->find_node(key_hash, k));
}
#if defined(BOOST_NO_RVALUE_REFERENCES)
@@ -531,12 +567,12 @@
{
if(!this->size_) return 0;
- std::size_t hash = this->hash(k);
+ std::size_t key_hash = this->hash(k);
std::size_t bucket_index =
- policy::to_bucket(this->bucket_count_, hash);
- bucket_pointer bucket = this->get_bucket(bucket_index);
+ policy::to_bucket(this->bucket_count_, key_hash);
+ bucket_pointer this_bucket = this->get_bucket(bucket_index);
- previous_pointer prev = bucket->next_;
+ previous_pointer prev = this_bucket->next_;
if (!prev) return 0;
for (;;)
@@ -547,7 +583,7 @@
if (policy::to_bucket(this->bucket_count_, node_hash)
!= bucket_index)
return 0;
- if (node_hash == hash &&
+ if (node_hash == key_hash &&
this->key_eq()(k, this->get_key(
static_cast<node_pointer>(prev->next_)->value())))
break;
@@ -560,7 +596,7 @@
static_cast<node_pointer>(pos->group_prev_)->next_;
node_pointer end = static_cast<node_pointer>(end1);
prev->next_ = end1;
- this->fix_buckets(bucket, prev, end);
+ this->fix_buckets(this_bucket, prev, end);
return this->delete_nodes(c_iterator(pos), c_iterator(end));
}
@@ -570,11 +606,11 @@
iterator next(r.node_);
++next;
- bucket_pointer bucket = this->get_bucket(
+ bucket_pointer this_bucket = this->get_bucket(
policy::to_bucket(this->bucket_count_, r.node_->hash_));
- previous_pointer prev = unlink_node(*bucket, r.node_);
+ previous_pointer prev = unlink_node(*this_bucket, r.node_);
- this->fix_buckets(bucket, prev, next.node_);
+ this->fix_buckets(this_bucket, prev, next.node_);
this->delete_node(r);
@@ -713,7 +749,7 @@
previous_pointer prev = dst.get_previous_start();
while (n.node_) {
- std::size_t hash = n.node_->hash_;
+ std::size_t key_hash = n.node_->hash_;
iterator group_end(
static_cast<node_pointer>(
static_cast<node_pointer>(n.node_->group_prev_)->next_
@@ -724,7 +760,7 @@
node_pointer first_node = a.release();
node_pointer end = first_node;
- first_node->hash_ = hash;
+ first_node->hash_ = key_hash;
prev->next_ = static_cast<link_pointer>(first_node);
++dst.size_;
@@ -733,7 +769,7 @@
a.construct_node();
a.construct_value2(*n);
end = a.release();
- end->hash_ = hash;
+ end->hash_ = key_hash;
add_after_node(end, first_node);
++dst.size_;
}
@@ -760,7 +796,7 @@
previous_pointer prev = dst.get_previous_start();
while (n.node_) {
- std::size_t hash = n.node_->hash_;
+ std::size_t key_hash = n.node_->hash_;
iterator group_end(
static_cast<node_pointer>(
static_cast<node_pointer>(n.node_->group_prev_)->next_
@@ -771,7 +807,7 @@
node_pointer first_node = a.release();
node_pointer end = first_node;
- first_node->hash_ = hash;
+ first_node->hash_ = key_hash;
prev->next_ = static_cast<link_pointer>(first_node);
++dst.size_;
@@ -780,7 +816,7 @@
a.construct_node();
a.construct_value2(boost::move(*n));
end = a.release();
- end->hash_ = hash;
+ end->hash_ = key_hash;
add_after_node(end, first_node);
++dst.size_;
}
Modified: branches/release/boost/unordered/detail/table.hpp
==============================================================================
--- branches/release/boost/unordered/detail/table.hpp (original)
+++ branches/release/boost/unordered/detail/table.hpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -348,21 +348,21 @@
template <typename Key, typename Hash, typename Pred>
iterator generic_find_node(
Key const& k,
- Hash const& hash_function,
+ Hash const& hf,
Pred const& eq) const
{
if (!this->size_) return iterator();
return static_cast<table_impl const*>(this)->
- find_node_impl(policy::apply_hash(hash_function, k), k, eq);
+ find_node_impl(policy::apply_hash(hf, k), k, eq);
}
iterator find_node(
- std::size_t hash,
+ std::size_t key_hash,
key_type const& k) const
{
if (!this->size_) return iterator();
return static_cast<table_impl const*>(this)->
- find_node_impl(hash, k, this->key_eq());
+ find_node_impl(key_hash, k, this->key_eq());
}
iterator find_node(key_type const& k) const
@@ -387,6 +387,7 @@
void reserve_for_insert(std::size_t);
void rehash(std::size_t);
+ void reserve(std::size_t);
};
////////////////////////////////////////////////////////////////////////////
@@ -402,7 +403,9 @@
this->create_buckets();
this->max_load_ = this->calculate_max_load();
}
- else if(size >= max_load_) {
+ // According to the standard this should be 'size >= max_load_',
+ // but I think this is better, defect report filed.
+ else if(size > max_load_) {
std::size_t num_buckets
= this->min_buckets_for_size((std::max)(size,
this->size_ + (this->size_ >> 1)));
@@ -417,7 +420,7 @@
// strong otherwise.
template <typename Types>
- void table<Types>::rehash(std::size_t min_buckets)
+ inline void table<Types>::rehash(std::size_t min_buckets)
{
using namespace std;
@@ -437,6 +440,13 @@
}
}
}
+
+ template <typename Types>
+ inline void table<Types>::reserve(std::size_t num_elements)
+ {
+ rehash(static_cast<std::size_t>(
+ std::ceil(static_cast<double>(num_elements) / this->mlf_)));
+ }
}}}
#endif
Modified: branches/release/boost/unordered/detail/unique.hpp
==============================================================================
--- branches/release/boost/unordered/detail/unique.hpp (original)
+++ branches/release/boost/unordered/detail/unique.hpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -12,31 +12,49 @@
#endif
#include <boost/unordered/detail/table.hpp>
-#include <boost/unordered/detail/emplace_args.hpp>
#include <boost/unordered/detail/extract_key.hpp>
#include <boost/throw_exception.hpp>
#include <stdexcept>
namespace boost { namespace unordered { namespace detail {
- template <typename A, typename T> struct node;
+ template <typename A, typename T> struct unique_node;
template <typename T> struct ptr_node;
template <typename Types> struct table_impl;
template <typename A, typename T>
- struct node :
+ struct unique_node :
+ boost::unordered::detail::node_base<
+ typename ::boost::unordered::detail::rebind_wrap<
+ A, unique_node<A, T> >::type::pointer
+ >,
boost::unordered::detail::value_base<T>
{
typedef typename ::boost::unordered::detail::rebind_wrap<
- A, node<A, T> >::type::pointer link_pointer;
+ A, unique_node<A, T> >::type::pointer link_pointer;
+ typedef boost::unordered::detail::node_base<link_pointer> node_base;
- link_pointer next_;
std::size_t hash_;
- node() :
- next_(),
+#if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT
+ template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
+ unique_node(BOOST_UNORDERED_EMPLACE_ARGS) :
+ node_base(),
+ hash_(0)
+ {
+ boost::unordered::detail::construct_impl(
+ this->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD);
+ }
+
+ ~unique_node() {
+ boost::unordered::detail::destroy(this->value_ptr());
+ }
+#else
+ unique_node() :
+ node_base(),
hash_(0)
{}
+#endif
void init(link_pointer)
{
@@ -49,14 +67,30 @@
boost::unordered::detail::ptr_bucket
{
typedef boost::unordered::detail::ptr_bucket bucket_base;
+ typedef bucket_base node_base;
typedef ptr_bucket* link_pointer;
std::size_t hash_;
+#if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT
+ template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
+ ptr_node(BOOST_UNORDERED_EMPLACE_ARGS) :
+ bucket_base(),
+ hash_(0)
+ {
+ boost::unordered::detail::construct_impl(
+ this->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD);
+ }
+
+ ~ptr_node() {
+ boost::unordered::detail::destroy(this->value_ptr());
+ }
+#else
ptr_node() :
bucket_base(),
hash_(0)
{}
+#endif
void init(link_pointer)
{
@@ -69,7 +103,7 @@
template <typename A, typename T, typename NodePtr, typename BucketPtr>
struct pick_node2
{
- typedef boost::unordered::detail::node<A, T> node;
+ typedef boost::unordered::detail::unique_node<A, T> node;
typedef typename boost::unordered::detail::allocator_traits<
typename boost::unordered::detail::rebind_wrap<A, node>::type
@@ -219,12 +253,12 @@
template <class Key, class Pred>
iterator find_node_impl(
- std::size_t hash,
+ std::size_t key_hash,
Key const& k,
Pred const& eq) const
{
std::size_t bucket_index =
- policy::to_bucket(this->bucket_count_, hash);
+ policy::to_bucket(this->bucket_count_, key_hash);
iterator n = this->get_start(bucket_index);
for (;;)
@@ -232,7 +266,7 @@
if (!n.node_) return n;
std::size_t node_hash = n.node_->hash_;
- if (hash == node_hash)
+ if (key_hash == node_hash)
{
if (eq(k, this->get_key(*n)))
return n;
@@ -300,13 +334,13 @@
inline iterator add_node(
node_constructor& a,
- std::size_t hash)
+ std::size_t key_hash)
{
node_pointer n = a.release();
- n->hash_ = hash;
+ n->hash_ = key_hash;
bucket_pointer b = this->get_bucket(
- policy::to_bucket(this->bucket_count_, hash));
+ policy::to_bucket(this->bucket_count_, key_hash));
if (!b->next_)
{
@@ -336,8 +370,8 @@
{
typedef typename value_type::second_type mapped_type;
- std::size_t hash = this->hash(k);
- iterator pos = this->find_node(hash, k);
+ std::size_t key_hash = this->hash(k);
+ iterator pos = this->find_node(key_hash, k);
if (pos.node_) return *pos;
@@ -357,7 +391,7 @@
#endif
this->reserve_for_insert(this->size_ + 1);
- return *add_node(a, hash);
+ return *add_node(a, key_hash);
}
#if defined(BOOST_NO_RVALUE_REFERENCES)
@@ -397,8 +431,8 @@
emplace_return emplace_impl(key_type const& k,
BOOST_UNORDERED_EMPLACE_ARGS)
{
- std::size_t hash = this->hash(k);
- iterator pos = this->find_node(hash, k);
+ std::size_t key_hash = this->hash(k);
+ iterator pos = this->find_node(key_hash, k);
if (pos.node_) return emplace_return(pos, false);
@@ -411,21 +445,21 @@
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
this->reserve_for_insert(this->size_ + 1);
- return emplace_return(this->add_node(a, hash), true);
+ return emplace_return(this->add_node(a, key_hash), true);
}
emplace_return emplace_impl_with_node(node_constructor& a)
{
key_type const& k = this->get_key(a.value());
- std::size_t hash = this->hash(k);
- iterator pos = this->find_node(hash, k);
+ std::size_t key_hash = this->hash(k);
+ iterator pos = this->find_node(key_hash, k);
if (pos.node_) return emplace_return(pos, false);
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
this->reserve_for_insert(this->size_ + 1);
- return emplace_return(this->add_node(a, hash), true);
+ return emplace_return(this->add_node(a, key_hash), true);
}
template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
@@ -481,12 +515,12 @@
void insert_range_empty(node_constructor& a, key_type const& k,
InputIt i, InputIt j)
{
- std::size_t hash = this->hash(k);
+ std::size_t key_hash = this->hash(k);
a.construct_node();
a.construct_value2(*i);
this->reserve_for_insert(this->size_ +
boost::unordered::detail::insert_size(i, j));
- this->add_node(a, hash);
+ this->add_node(a, key_hash);
}
template <class InputIt>
@@ -494,19 +528,19 @@
InputIt i, InputIt j)
{
// No side effects in this initial code
- std::size_t hash = this->hash(k);
- iterator pos = this->find_node(hash, k);
+ std::size_t key_hash = this->hash(k);
+ iterator pos = this->find_node(key_hash, k);
if (!pos.node_) {
a.construct_node();
a.construct_value2(*i);
- if(this->size_ + 1 >= this->max_load_)
+ if(this->size_ + 1 > this->max_load_)
this->reserve_for_insert(this->size_ +
boost::unordered::detail::insert_size(i, j));
// Nothing after this point can throw.
- this->add_node(a, hash);
+ this->add_node(a, key_hash);
}
}
@@ -531,12 +565,12 @@
{
if(!this->size_) return 0;
- std::size_t hash = this->hash(k);
+ std::size_t key_hash = this->hash(k);
std::size_t bucket_index =
- policy::to_bucket(this->bucket_count_, hash);
- bucket_pointer bucket = this->get_bucket(bucket_index);
+ policy::to_bucket(this->bucket_count_, key_hash);
+ bucket_pointer this_bucket = this->get_bucket(bucket_index);
- previous_pointer prev = bucket->next_;
+ previous_pointer prev = this_bucket->next_;
if (!prev) return 0;
for (;;)
@@ -547,7 +581,7 @@
if (policy::to_bucket(this->bucket_count_, node_hash)
!= bucket_index)
return 0;
- if (node_hash == hash &&
+ if (node_hash == key_hash &&
this->key_eq()(k, this->get_key(
static_cast<node_pointer>(prev->next_)->value())))
break;
@@ -557,7 +591,7 @@
node_pointer pos = static_cast<node_pointer>(prev->next_);
node_pointer end = static_cast<node_pointer>(pos->next_);
prev->next_ = pos->next_;
- this->fix_buckets(bucket, prev, end);
+ this->fix_buckets(this_bucket, prev, end);
return this->delete_nodes(c_iterator(pos), c_iterator(end));
}
@@ -567,11 +601,11 @@
iterator next(r.node_);
++next;
- bucket_pointer bucket = this->get_bucket(
+ bucket_pointer this_bucket = this->get_bucket(
policy::to_bucket(this->bucket_count_, r.node_->hash_));
- previous_pointer prev = unlink_node(*bucket, r.node_);
+ previous_pointer prev = unlink_node(*this_bucket, r.node_);
- this->fix_buckets(bucket, prev, next.node_);
+ this->fix_buckets(this_bucket, prev, next.node_);
this->delete_node(r);
Modified: branches/release/boost/unordered/unordered_map.hpp
==============================================================================
--- branches/release/boost/unordered/unordered_map.hpp (original)
+++ branches/release/boost/unordered/unordered_map.hpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -515,6 +515,7 @@
float load_factor() const;
void max_load_factor(float);
void rehash(size_type);
+ void reserve(size_type);
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
friend bool operator==<K,T,H,P,A>(
@@ -997,6 +998,7 @@
float load_factor() const;
void max_load_factor(float);
void rehash(size_type);
+ void reserve(size_type);
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
friend bool operator==<K,T,H,P,A>(
@@ -1301,6 +1303,12 @@
}
template <class K, class T, class H, class P, class A>
+ void unordered_map<K,T,H,P,A>::reserve(size_type n)
+ {
+ table_.reserve(n);
+ }
+
+ template <class K, class T, class H, class P, class A>
inline bool operator==(
unordered_map<K,T,H,P,A> const& m1,
unordered_map<K,T,H,P,A> const& m2)
@@ -1607,6 +1615,12 @@
}
template <class K, class T, class H, class P, class A>
+ void unordered_multimap<K,T,H,P,A>::reserve(size_type n)
+ {
+ table_.reserve(n);
+ }
+
+ template <class K, class T, class H, class P, class A>
inline bool operator==(
unordered_multimap<K,T,H,P,A> const& m1,
unordered_multimap<K,T,H,P,A> const& m2)
Modified: branches/release/boost/unordered/unordered_set.hpp
==============================================================================
--- branches/release/boost/unordered/unordered_set.hpp (original)
+++ branches/release/boost/unordered/unordered_set.hpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -500,6 +500,7 @@
float load_factor() const;
void max_load_factor(float);
void rehash(size_type);
+ void reserve(size_type);
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
friend bool operator==<T,H,P,A>(
@@ -972,6 +973,7 @@
float load_factor() const;
void max_load_factor(float);
void rehash(size_type);
+ void reserve(size_type);
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
friend bool operator==<T,H,P,A>(
@@ -1227,6 +1229,12 @@
}
template <class T, class H, class P, class A>
+ void unordered_set<T,H,P,A>::reserve(size_type n)
+ {
+ table_.reserve(n);
+ }
+
+ template <class T, class H, class P, class A>
inline bool operator==(
unordered_set<T,H,P,A> const& m1,
unordered_set<T,H,P,A> const& m2)
@@ -1505,6 +1513,12 @@
}
template <class T, class H, class P, class A>
+ void unordered_multiset<T,H,P,A>::reserve(size_type n)
+ {
+ table_.reserve(n);
+ }
+
+ template <class T, class H, class P, class A>
inline bool operator==(
unordered_multiset<T,H,P,A> const& m1,
unordered_multiset<T,H,P,A> const& m2)
Modified: branches/release/libs/functional/hash/test/Jamfile.v2
==============================================================================
--- branches/release/libs/functional/hash/test/Jamfile.v2 (original)
+++ branches/release/libs/functional/hash/test/Jamfile.v2 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -10,8 +10,8 @@
<warnings>all
<toolset>intel:<warnings>on
<toolset>intel:<cxxflags>-strict-ansi
- <toolset>gcc:<cxxflags>"-pedantic -Wstrict-aliasing -fstrict-aliasing -Wextra -Wsign-promo -Wunused-parameter -Wconversion -Wfloat-equal"
- <toolset>darwin:<cxxflags>"-pedantic -Wstrict-aliasing -fstrict-aliasing -Wextra -Wsign-promo -Wunused-parameter -Wconversion -Wfloat-equal"
+ <toolset>gcc:<cxxflags>"-pedantic -Wstrict-aliasing -fstrict-aliasing -Wextra -Wsign-promo -Wunused-parameter -Wconversion -Wfloat-equal -Wshadow"
+ <toolset>darwin:<cxxflags>"-pedantic -Wstrict-aliasing -fstrict-aliasing -Wextra -Wsign-promo -Wunused-parameter -Wconversion -Wfloat-equal -Wshadow"
<toolset>msvc:<warnings-as-errors>on
#<toolset>gcc:<warnings-as-errors>on
#<toolset>darwin:<warnings-as-errors>on
Modified: branches/release/libs/unordered/doc/changes.qbk
==============================================================================
--- branches/release/libs/unordered/doc/changes.qbk (original)
+++ branches/release/libs/unordered/doc/changes.qbk 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -178,10 +178,14 @@
[h2 Boost 1.50.0]
* Fix equality for `unordered_multiset` and `unordered_multimap`.
-* [@http://svn.boost.org/trac/boost/ticket/6771 Ticket 6771]:
+* [@https://svn.boost.org/trac/boost/ticket/6857 Ticket 6857]:
+ Implement `reserve`.
+* [@https://svn.boost.org/trac/boost/ticket/6771 Ticket 6771]:
Avoid gcc's `-Wfloat-equal` warning.
-* [@http://svn.boost.org/trac/boost/ticket/6784 Ticket 6784]:
+* [@https://svn.boost.org/trac/boost/ticket/6784 Ticket 6784]:
Fix some Sun specific code.
+* [@https://svn.boost.org/trac/boost/ticket/6190 Ticket 6190]:
+ Avoid gcc's `-Wshadow` warning.
* Remove some of the smaller prime number of buckets, as they may make
collisions quite probable (e.g. multiples of 5 are very common because
we used base 10).
Modified: branches/release/libs/unordered/doc/ref.php
==============================================================================
--- branches/release/libs/unordered/doc/ref.php (original)
+++ branches/release/libs/unordered/doc/ref.php 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -963,6 +963,18 @@
<para>The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.</para>
</throws>
</method>
+ <method name="reserve">
+ <parameter name="n">
+ <paramtype>size_type</paramtype>
+ </parameter>
+ <type>void</type>
+ <description>
+ <para>Invalidates iterators, and changes the order of elements. Pointers and references to elements are not invalidated.</para>
+ </description>
+ <throws>
+ <para>The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.</para>
+ </throws>
+ </method>
</method-group>
<free-function-group name="Equality Comparisons">
<function name="operator==">
Modified: branches/release/libs/unordered/doc/ref.xml
==============================================================================
--- branches/release/libs/unordered/doc/ref.xml (original)
+++ branches/release/libs/unordered/doc/ref.xml 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -846,6 +846,18 @@
<para>The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.</para>
</throws>
</method>
+ <method name="reserve">
+ <parameter name="n">
+ <paramtype>size_type</paramtype>
+ </parameter>
+ <type>void</type>
+ <description>
+ <para>Invalidates iterators, and changes the order of elements. Pointers and references to elements are not invalidated.</para>
+ </description>
+ <throws>
+ <para>The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.</para>
+ </throws>
+ </method>
</method-group>
<free-function-group name="Equality Comparisons">
<function name="operator==">
@@ -1797,6 +1809,18 @@
<para>The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.</para>
</throws>
</method>
+ <method name="reserve">
+ <parameter name="n">
+ <paramtype>size_type</paramtype>
+ </parameter>
+ <type>void</type>
+ <description>
+ <para>Invalidates iterators, and changes the order of elements. Pointers and references to elements are not invalidated.</para>
+ </description>
+ <throws>
+ <para>The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.</para>
+ </throws>
+ </method>
</method-group>
<free-function-group name="Equality Comparisons">
<function name="operator==">
@@ -2793,6 +2817,18 @@
<para>The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.</para>
</throws>
</method>
+ <method name="reserve">
+ <parameter name="n">
+ <paramtype>size_type</paramtype>
+ </parameter>
+ <type>void</type>
+ <description>
+ <para>Invalidates iterators, and changes the order of elements. Pointers and references to elements are not invalidated.</para>
+ </description>
+ <throws>
+ <para>The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.</para>
+ </throws>
+ </method>
</method-group>
<free-function-group name="Equality Comparisons">
<function name="operator==">
@@ -3758,6 +3794,18 @@
<para>The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.</para>
</throws>
</method>
+ <method name="reserve">
+ <parameter name="n">
+ <paramtype>size_type</paramtype>
+ </parameter>
+ <type>void</type>
+ <description>
+ <para>Invalidates iterators, and changes the order of elements. Pointers and references to elements are not invalidated.</para>
+ </description>
+ <throws>
+ <para>The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.</para>
+ </throws>
+ </method>
</method-group>
<free-function-group name="Equality Comparisons">
<function name="operator==">
Modified: branches/release/libs/unordered/test/exception/assign_exception_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/exception/assign_exception_tests.cpp (original)
+++ branches/release/libs/unordered/test/exception/assign_exception_tests.cpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -11,7 +11,7 @@
#pragma warning(disable:4512) // assignment operator could not be generated
#endif
-test::seed_t seed(12847);
+test::seed_t initialize_seed(12847);
template <class T>
struct self_assign_base : public test::exception_base
Modified: branches/release/libs/unordered/test/exception/constructor_exception_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/exception/constructor_exception_tests.cpp (original)
+++ branches/release/libs/unordered/test/exception/constructor_exception_tests.cpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -9,7 +9,7 @@
template <typename T> inline void avoid_unused_warning(T const&) {}
-test::seed_t seed(91274);
+test::seed_t initialize_seed(91274);
struct objects
{
Modified: branches/release/libs/unordered/test/exception/copy_exception_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/exception/copy_exception_tests.cpp (original)
+++ branches/release/libs/unordered/test/exception/copy_exception_tests.cpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -8,7 +8,7 @@
template <typename T> inline void avoid_unused_warning(T const&) {}
-test::seed_t seed(73041);
+test::seed_t initialize_seed(73041);
template <class T>
struct copy_test1 : public test::exception_base
Modified: branches/release/libs/unordered/test/exception/erase_exception_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/exception/erase_exception_tests.cpp (original)
+++ branches/release/libs/unordered/test/exception/erase_exception_tests.cpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -8,7 +8,7 @@
#include "../helpers/invariants.hpp"
#include "../helpers/helpers.hpp"
-test::seed_t seed(835193);
+test::seed_t initialize_seed(835193);
template <class T>
struct erase_test_base : public test::exception_base
Modified: branches/release/libs/unordered/test/exception/insert_exception_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/exception/insert_exception_tests.cpp (original)
+++ branches/release/libs/unordered/test/exception/insert_exception_tests.cpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -11,7 +11,7 @@
#include <boost/utility.hpp>
#include <cmath>
-test::seed_t seed(747373);
+test::seed_t initialize_seed(747373);
template <class T>
struct insert_test_base : public test::exception_base
Modified: branches/release/libs/unordered/test/exception/rehash_exception_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/exception/rehash_exception_tests.cpp (original)
+++ branches/release/libs/unordered/test/exception/rehash_exception_tests.cpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -11,7 +11,7 @@
#include <iostream>
-test::seed_t seed(3298597);
+test::seed_t initialize_seed(3298597);
template <class T>
struct rehash_test_base : public test::exception_base
Modified: branches/release/libs/unordered/test/exception/swap_exception_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/exception/swap_exception_tests.cpp (original)
+++ branches/release/libs/unordered/test/exception/swap_exception_tests.cpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -11,7 +11,7 @@
#pragma warning(disable:4512) // assignment operator could not be generated
#endif
-test::seed_t seed(9387);
+test::seed_t initialize_seed(9387);
template <class T>
struct self_swap_base : public test::exception_base
Modified: branches/release/libs/unordered/test/helpers/list.hpp
==============================================================================
--- branches/release/libs/unordered/test/helpers/list.hpp (original)
+++ branches/release/libs/unordered/test/helpers/list.hpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -219,14 +219,14 @@
data_.last_ptr_ = &data_.first_;
}
- void erase(const_iterator start, const_iterator end) {
+ void erase(const_iterator i, const_iterator j) {
node** ptr = &data_.first_;
- while(*ptr != start.ptr_) {
+ while(*ptr != i.ptr_) {
ptr = &(*ptr)->next_;
}
- while(*ptr != end.ptr_) {
+ while(*ptr != j.ptr_) {
node* to_delete = *ptr;
*ptr = (*ptr)->next_;
--data_.size_;
Modified: branches/release/libs/unordered/test/helpers/tracker.hpp
==============================================================================
--- branches/release/libs/unordered/test/helpers/tracker.hpp (original)
+++ branches/release/libs/unordered/test/helpers/tracker.hpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -124,8 +124,8 @@
: base()
{}
- explicit ordered(key_compare const& compare)
- : base(compare)
+ explicit ordered(key_compare const& kc)
+ : base(kc)
{}
void compare(X const& x)
@@ -143,10 +143,10 @@
}
template <class It>
- void insert_range(It begin, It end) {
- while(begin != end) {
- this->insert(*begin);
- ++begin;
+ void insert_range(It b, It e) {
+ while(b != e) {
+ this->insert(*b);
+ ++b;
}
}
};
Modified: branches/release/libs/unordered/test/unordered/assign_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/assign_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/assign_tests.cpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -22,7 +22,7 @@
namespace assign_tests {
-test::seed_t seed(96785);
+test::seed_t initialize_seed(96785);
template <class T>
void assign_tests1(T*,
Modified: branches/release/libs/unordered/test/unordered/bucket_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/bucket_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/bucket_tests.cpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -21,7 +21,7 @@
namespace bucket_tests {
-test::seed_t seed(54635);
+test::seed_t initialize_seed(54635);
template <class X>
void tests(X* = 0, test::random_generator generator = test::default_generator)
Modified: branches/release/libs/unordered/test/unordered/constructor_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/constructor_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/constructor_tests.cpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -18,7 +18,7 @@
namespace constructor_tests {
-test::seed_t seed(356730);
+test::seed_t initialize_seed(356730);
template <class T>
void constructor_tests1(T*,
Modified: branches/release/libs/unordered/test/unordered/copy_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/copy_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/copy_tests.cpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -16,7 +16,7 @@
#include "../helpers/equivalent.hpp"
#include "../helpers/invariants.hpp"
-test::seed_t seed(9063);
+test::seed_t initialize_seed(9063);
namespace copy_tests
{
Modified: branches/release/libs/unordered/test/unordered/erase_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/erase_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/erase_tests.cpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -21,7 +21,7 @@
namespace erase_tests
{
-test::seed_t seed(85638);
+test::seed_t initialize_seed(85638);
template <class Container>
void erase_tests1(Container*,
Modified: branches/release/libs/unordered/test/unordered/find_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/find_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/find_tests.cpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -17,7 +17,7 @@
namespace find_tests
{
-test::seed_t seed(78937);
+test::seed_t initialize_seed(78937);
template <class X>
void find_tests1(X*, test::random_generator generator = test::default_generator)
Modified: branches/release/libs/unordered/test/unordered/insert_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/insert_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/insert_tests.cpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -21,7 +21,7 @@
namespace insert_tests {
-test::seed_t seed(243432);
+test::seed_t initialize_seed(243432);
template <class X>
void unique_insert_tests1(X*,
Modified: branches/release/libs/unordered/test/unordered/load_factor_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/load_factor_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/load_factor_tests.cpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -20,7 +20,7 @@
namespace load_factor_tests
{
-test::seed_t seed(783656);
+test::seed_t initialize_seed(783656);
template <class X>
void set_load_factor_tests(X* = 0)
Modified: branches/release/libs/unordered/test/unordered/move_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/move_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/move_tests.cpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -22,7 +22,7 @@
namespace move_tests
{
- test::seed_t seed(98624);
+ test::seed_t initialize_seed(98624);
#if defined(BOOST_UNORDERED_USE_MOVE) || !defined(BOOST_NO_RVALUE_REFERENCES)
#define BOOST_UNORDERED_TEST_MOVING 1
#else
Modified: branches/release/libs/unordered/test/unordered/rehash_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/rehash_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/rehash_tests.cpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -15,7 +15,7 @@
namespace rehash_tests
{
-test::seed_t seed(2974);
+test::seed_t initialize_seed(2974);
template <class X>
bool postcondition(X const& x, BOOST_DEDUCED_TYPENAME X::size_type n)
@@ -100,6 +100,75 @@
tracker.compare(x);
}
+template <class X>
+void reserve_test1(X* = 0,
+ test::random_generator generator = test::default_generator)
+{
+ for (int random_mlf = 0; random_mlf < 2; ++random_mlf)
+ {
+ for (int i = 1; i < 2000; i += i < 50 ? 1 : 13)
+ {
+ test::random_values<X> v(i, generator);
+
+ test::ordered<X> tracker;
+ tracker.insert_range(v.begin(), v.end());
+
+ X x;
+ x.max_load_factor(random_mlf ?
+ static_cast<float>(std::rand() % 1000) / 500.0f + 0.5f : 1.0f);
+
+ // For the current standard this should reserve i+1, I've
+ // submitted a defect report and will assume it's a defect
+ // for now.
+ x.reserve(i);
+
+ // Insert an element before the range insert, otherwise there are
+ // no iterators to invalidate in the range insert, and it can
+ // rehash.
+ typename test::random_values<X>::iterator it = v.begin();
+ x.insert(*it);
+ ++it;
+
+ std::size_t bucket_count = x.bucket_count();
+ x.insert(it, v.end());
+ BOOST_TEST(bucket_count == x.bucket_count());
+ tracker.compare(x);
+ }
+ }
+}
+
+template <class X>
+void reserve_test2(X* = 0,
+ test::random_generator generator = test::default_generator)
+{
+ for (int random_mlf = 0; random_mlf < 2; ++random_mlf)
+ {
+ for (int i = 0; i < 2000; i += i < 50 ? 1 : 13)
+ {
+ test::random_values<X> v(i, generator);
+
+ test::ordered<X> tracker;
+ tracker.insert_range(v.begin(), v.end());
+
+ X x;
+ x.max_load_factor(random_mlf ?
+ static_cast<float>(std::rand() % 1000) / 500.0f + 0.5f : 1.0f);
+
+ x.reserve(i);
+ std::size_t bucket_count = x.bucket_count();
+
+ for (typename test::random_values<X>::iterator it = v.begin();
+ it != v.end(); ++it)
+ {
+ x.insert(*it);
+ }
+
+ BOOST_TEST(bucket_count == x.bucket_count());
+ tracker.compare(x);
+ }
+ }
+}
+
boost::unordered_set<int>* int_set_ptr;
boost::unordered_multiset<int>* int_multiset_ptr;
boost::unordered_map<int, int>* int_map_ptr;
@@ -117,6 +186,12 @@
UNORDERED_TEST(rehash_test1,
((int_set_ptr)(int_multiset_ptr)(int_map_ptr)(int_multimap_ptr))
)
+UNORDERED_TEST(reserve_test1,
+ ((int_set_ptr)(int_multiset_ptr)(int_map_ptr)(int_multimap_ptr))
+)
+UNORDERED_TEST(reserve_test2,
+ ((int_set_ptr)(int_multiset_ptr)(int_map_ptr)(int_multimap_ptr))
+)
}
Modified: branches/release/libs/unordered/test/unordered/swap_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/swap_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/swap_tests.cpp 2012-05-12 04:14:05 EDT (Sat, 12 May 2012)
@@ -25,7 +25,7 @@
namespace swap_tests
{
-test::seed_t seed(783472);
+test::seed_t initialize_seed(783472);
template <class X>
void swap_test_impl(X& x1, X& x2)