870 changes: 793 additions & 77 deletions doc/ref.xml
View file

Large diffs are not rendered by default.

170 changes: 128 additions & 42 deletions include/boost/unordered/detail/allocate.hpp
View file
Expand Up @@ -88,6 +88,16 @@ namespace boost { namespace unordered { namespace detail {
convert_from_anything(T const&);
};

namespace func {
// This is a bit nasty, when constructing the individual members
// of a std::pair, need to cast away 'const'. For modern compilers,
// should be able to use std::piecewise_construct instead.
template <typename T> T* const_cast_pointer(T* x) { return x; }
template <typename T> T* const_cast_pointer(T const* x) {
return const_cast<T*>(x);
}
}

////////////////////////////////////////////////////////////////////////////
// emplace_args
//
Expand Down Expand Up @@ -237,9 +247,8 @@ BOOST_PP_REPEAT_FROM_TO(4, BOOST_UNORDERED_EMPLACE_LIMIT, BOOST_UNORDERED_EARGS,
// 2 = boost::container::allocator_traits

#if !defined(BOOST_UNORDERED_USE_ALLOCATOR_TRAITS)
# if defined(__GXX_EXPERIMENTAL_CXX0X__) && \
(__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 7))
# define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 0
# if !defined(BOOST_NO_CXX11_ALLOCATOR)
# 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
Expand Down Expand Up @@ -316,7 +325,7 @@ namespace boost { namespace unordered { namespace detail {

#if !defined(BOOST_NO_SFINAE_EXPR)

template <typename T, unsigned int> struct expr_test;
template <typename T, long unsigned int> struct expr_test;
template <typename T> struct expr_test<T, sizeof(char)> : T {};

# define BOOST_UNORDERED_CHECK_EXPRESSION(count, result, expression) \
Expand Down Expand Up @@ -412,11 +421,69 @@ namespace boost { namespace unordered { namespace detail {

namespace boost { namespace unordered { namespace detail {

// TODO: Does this match std::allocator_traits<Alloc>::rebind_alloc<T>?
template <typename Alloc, typename T>
struct rebind_alloc;

#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)

template <template<typename, typename...> class Alloc,
typename U, typename T, typename... Args>
struct rebind_alloc<Alloc<U, Args...>, T>
{
typedef Alloc<T, Args...> type;
};

#else

template <
template<typename> class Alloc,
typename U, typename T>
struct rebind_alloc<Alloc<U>, T>
{
typedef Alloc<T> type;
};

template <
template<typename, typename> class Alloc,
typename U, typename T,
typename A0>
struct rebind_alloc<Alloc<U, A0>, T>
{
typedef Alloc<T, A0> type;
};

template <
template<typename, typename, typename> class Alloc,
typename U, typename T,
typename A0, typename A1>
struct rebind_alloc<Alloc<U, A0, A1>, T>
{
typedef Alloc<T, A0, A1> type;
};

#endif

template <typename Alloc, typename T>
struct rebind_wrap
{
typedef typename Alloc::BOOST_NESTED_TEMPLATE rebind<T>::other type;
template <typename X>
static choice1::type test(choice1,
typename X::BOOST_NESTED_TEMPLATE rebind<T>::other* = 0);
template <typename X>
static choice2::type test(choice2, void* = 0);

enum { value = (1 == sizeof(test<Alloc>(choose()))) };

struct fallback {
template <typename U>
struct rebind {
typedef typename rebind_alloc<Alloc, T>::type other;
};
};

typedef typename boost::detail::if_true<value>::
BOOST_NESTED_TEMPLATE then<Alloc, fallback>
::type::BOOST_NESTED_TEMPLATE rebind<T>::other type;
};

# if defined(BOOST_MSVC) && BOOST_MSVC <= 1400
Expand Down Expand Up @@ -606,7 +673,14 @@ namespace boost { namespace unordered { namespace detail {
typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, size_type, std::size_t)
size_type;

// TODO: rebind_alloc and rebind_traits
#if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES)
template <typename T>
using rebind_alloc = typename rebind_wrap<Alloc, T>::type;

template <typename T>
using rebind_traits =
boost::unordered::detail::allocator_traits<rebind_alloc<T> >;
#endif

static pointer allocate(Alloc& a, size_type n)
{ return a.allocate(n); }
Expand Down Expand Up @@ -639,7 +713,7 @@ namespace boost { namespace unordered { namespace detail {
::value>::type
construct(Alloc&, T* p, BOOST_FWD_REF(Args)... x)
{
new ((void*) p) T(boost::forward<Args>(x)...);
new (static_cast<void*>(p)) T(boost::forward<Args>(x)...);
}

template <typename T>
Expand Down Expand Up @@ -673,7 +747,7 @@ namespace boost { namespace unordered { namespace detail {
boost::unordered::detail::has_construct<Alloc, T>::value>::type
construct(Alloc&, T* p, T const& x)
{
new ((void*) p) T(x);
new (static_cast<void*>(p)) T(x);
}

template <typename T>
Expand Down Expand Up @@ -715,7 +789,7 @@ namespace boost { namespace unordered { namespace detail {
boost::is_same<T, value_type>::value,
void*>::type = 0)
{
new ((void*) p) T(x);
new (static_cast<void*>(p)) T(x);
}

template <typename T>
Expand Down Expand Up @@ -843,7 +917,7 @@ namespace boost { namespace unordered { namespace detail { namespace func {
}

template <typename Alloc, typename T>
inline void destroy_value_impl(Alloc& alloc, T* x) {
inline void call_destroy(Alloc& alloc, T* x) {
boost::unordered::detail::allocator_traits<Alloc>::destroy(alloc, x);
}

Expand All @@ -858,7 +932,7 @@ namespace boost { namespace unordered { namespace detail { namespace func {
}

template <typename Alloc, typename T>
inline void destroy_value_impl(Alloc&, T* x) {
inline void call_destroy(Alloc&, T* x) {
boost::unordered::detail::func::destroy(x);
}

Expand All @@ -880,7 +954,7 @@ namespace boost { namespace unordered { namespace detail { namespace func {
}

template <typename Alloc, typename T>
inline void destroy_value_impl(Alloc&, T* x) {
inline void call_destroy(Alloc&, T* x) {
boost::unordered::detail::func::destroy(x);
}

Expand Down Expand Up @@ -1021,7 +1095,7 @@ BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(10, boost::)
// For the standard pair constructor.

template <typename Alloc, typename T, typename... Args>
inline void construct_value_impl(Alloc& alloc, T* address,
inline void construct_from_args(Alloc& alloc, T* address,
BOOST_FWD_REF(Args)... args)
{
boost::unordered::detail::func::call_construct(alloc,
Expand All @@ -1036,32 +1110,36 @@ BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(10, boost::)
template <typename Alloc, typename A, typename B,
typename A0, typename A1, typename A2>
inline typename enable_if<use_piecewise<A0>, void>::type
construct_value_impl(Alloc& alloc, std::pair<A, B>* address,
construct_from_args(Alloc& alloc, std::pair<A, B>* address,
BOOST_FWD_REF(A0), BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
{
boost::unordered::detail::func::construct_from_tuple(alloc,
boost::addressof(address->first), boost::forward<A1>(a1));
boost::unordered::detail::func::const_cast_pointer(
boost::addressof(address->first)),
boost::forward<A1>(a1));
boost::unordered::detail::func::construct_from_tuple(alloc,
boost::addressof(address->second), boost::forward<A2>(a2));
boost::unordered::detail::func::const_cast_pointer(
boost::addressof(address->second)),
boost::forward<A2>(a2));
}

#else // BOOST_NO_CXX11_VARIADIC_TEMPLATES

////////////////////////////////////////////////////////////////////////////////
// Construct from emplace_args
////////////////////////////////////////////////////////////////////////////
// Construct from emplace_args

// 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,
inline void construct_from_args(Alloc&, T* address,
emplace_args1<A0> const& args)
{
new((void*) address) T(boost::forward<A0>(args.a0));
}

template <typename Alloc, typename T, typename A0, typename A1>
inline void construct_value_impl(Alloc&, T* address,
inline void construct_from_args(Alloc&, T* address,
emplace_args2<A0, A1> const& args)
{
new((void*) address) T(
Expand All @@ -1071,7 +1149,7 @@ BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(10, boost::)
}

template <typename Alloc, typename T, typename A0, typename A1, typename A2>
inline void construct_value_impl(Alloc&, T* address,
inline void construct_from_args(Alloc&, T* address,
emplace_args3<A0, A1, A2> const& args)
{
new((void*) address) T(
Expand All @@ -1088,7 +1166,7 @@ BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(10, boost::)
typename Alloc, typename T, \
BOOST_PP_ENUM_PARAMS_Z(z, num_params, typename A) \
> \
inline void construct_value_impl(Alloc&, T* address, \
inline void construct_from_args(Alloc&, T* address, \
boost::unordered::detail::BOOST_PP_CAT(emplace_args,num_params) < \
BOOST_PP_ENUM_PARAMS_Z(z, num_params, A) \
> const& args) \
Expand All @@ -1107,14 +1185,18 @@ BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(10, boost::)

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,
inline void construct_from_args(Alloc& alloc, std::pair<A, B>* address,
boost::unordered::detail::emplace_args3<A0, A1, A2> const& args,
typename enable_if<use_piecewise<A0>, void*>::type = 0)
{
boost::unordered::detail::func::construct_from_tuple(alloc,
boost::addressof(address->first), args.a1);
boost::unordered::detail::func::const_cast_pointer(
boost::addressof(address->first)),
args.a1);
boost::unordered::detail::func::construct_from_tuple(alloc,
boost::addressof(address->second), args.a2);
boost::unordered::detail::func::const_cast_pointer(
boost::addressof(address->second)),
args.a2);
}

#endif // BOOST_NO_CXX11_VARIADIC_TEMPLATES
Expand Down Expand Up @@ -1165,7 +1247,7 @@ namespace boost { namespace unordered { namespace detail {
BOOST_ASSERT(!node_);
node_ = p;
node_constructed_ = true;
boost::unordered::detail::func::destroy_value_impl(alloc_,
boost::unordered::detail::func::call_destroy(alloc_,
node_->value_ptr());
}

Expand Down Expand Up @@ -1231,7 +1313,7 @@ namespace boost { namespace unordered { namespace detail {
node_tmp<Alloc>::~node_tmp()
{
if (node_) {
boost::unordered::detail::func::destroy_value_impl(alloc_,
boost::unordered::detail::func::call_destroy(alloc_,
node_->value_ptr());
boost::unordered::detail::func::destroy(
boost::addressof(*node_));
Expand All @@ -1242,23 +1324,23 @@ namespace boost { namespace unordered { namespace detail {

namespace boost { namespace unordered { namespace detail { namespace func {

// Some nicer construct_value functions, might try to
// Some nicer construct_node functions, might try to
// improve implementation later.

template <typename Alloc, BOOST_UNORDERED_EMPLACE_TEMPLATE>
inline typename boost::unordered::detail::allocator_traits<Alloc>::pointer
construct_value_generic(Alloc& alloc, BOOST_UNORDERED_EMPLACE_ARGS)
construct_node_from_args(Alloc& alloc, BOOST_UNORDERED_EMPLACE_ARGS)
{
node_constructor<Alloc> a(alloc);
a.create_node();
construct_value_impl(alloc, a.node_->value_ptr(),
construct_from_args(alloc, a.node_->value_ptr(),
BOOST_UNORDERED_EMPLACE_FORWARD);
return a.release();
}

template <typename Alloc, typename U>
inline typename boost::unordered::detail::allocator_traits<Alloc>::pointer
construct_value(Alloc& alloc, BOOST_FWD_REF(U) x)
construct_node(Alloc& alloc, BOOST_FWD_REF(U) x)
{
node_constructor<Alloc> a(alloc);
a.create_node();
Expand All @@ -1271,29 +1353,33 @@ namespace boost { namespace unordered { namespace detail { namespace func {
// constructor for std::piece_construct with std::tuple.
template <typename Alloc, typename Key>
inline typename boost::unordered::detail::allocator_traits<Alloc>::pointer
construct_pair(Alloc& alloc, BOOST_FWD_REF(Key) k)
construct_node_pair(Alloc& alloc, BOOST_FWD_REF(Key) k)
{
node_constructor<Alloc> a(alloc);
a.create_node();
boost::unordered::detail::func::call_construct(
alloc, boost::addressof(a.node_->value_ptr()->first),
boost::unordered::detail::func::call_construct(alloc,
boost::unordered::detail::func::const_cast_pointer(
boost::addressof(a.node_->value_ptr()->first)),
boost::forward<Key>(k));
boost::unordered::detail::func::call_construct(
alloc, boost::addressof(a.node_->value_ptr()->second));
boost::unordered::detail::func::call_construct(alloc,
boost::unordered::detail::func::const_cast_pointer(
boost::addressof(a.node_->value_ptr()->second)));
return a.release();
}

template <typename Alloc, typename Key, typename Mapped>
inline typename boost::unordered::detail::allocator_traits<Alloc>::pointer
construct_pair(Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_FWD_REF(Mapped) m)
construct_node_pair(Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_FWD_REF(Mapped) m)
{
node_constructor<Alloc> a(alloc);
a.create_node();
boost::unordered::detail::func::call_construct(
alloc, boost::addressof(a.node_->value_ptr()->first),
boost::unordered::detail::func::call_construct(alloc,
boost::unordered::detail::func::const_cast_pointer(
boost::addressof(a.node_->value_ptr()->first)),
boost::forward<Key>(k));
boost::unordered::detail::func::call_construct(
alloc, boost::addressof(a.node_->value_ptr()->second),
boost::unordered::detail::func::call_construct(alloc,
boost::unordered::detail::func::const_cast_pointer(
boost::addressof(a.node_->value_ptr()->second)),
boost::forward<Mapped>(m));
return a.release();
}
Expand Down
47 changes: 5 additions & 42 deletions include/boost/unordered/detail/buckets.hpp
View file
Expand Up @@ -61,7 +61,6 @@ namespace boost { namespace unordered { namespace iterator_detail {
private:
#endif
typedef typename Node::node_pointer node_pointer;
typedef boost::unordered::iterator_detail::iterator<Node> n_iterator;
node_pointer ptr_;
std::size_t bucket_;
std::size_t bucket_count_;
Expand All @@ -72,8 +71,8 @@ namespace boost { namespace unordered { namespace iterator_detail {

l_iterator() BOOST_NOEXCEPT : ptr_() {}

l_iterator(n_iterator x, std::size_t b, std::size_t c) BOOST_NOEXCEPT
: ptr_(x.node_), bucket_(b), bucket_count_(c) {}
l_iterator(node_pointer n, std::size_t b, std::size_t c) BOOST_NOEXCEPT
: ptr_(n), bucket_(b), bucket_count_(c) {}

value_type& operator*() const {
return ptr_->value();
Expand Down Expand Up @@ -120,7 +119,6 @@ namespace boost { namespace unordered { namespace iterator_detail {
private:

typedef typename Node::node_pointer node_pointer;
typedef boost::unordered::iterator_detail::iterator<Node> n_iterator;
node_pointer ptr_;
std::size_t bucket_;
std::size_t bucket_count_;
Expand All @@ -131,8 +129,8 @@ namespace boost { namespace unordered { namespace iterator_detail {

cl_iterator() BOOST_NOEXCEPT : ptr_() {}

cl_iterator(n_iterator x, std::size_t b, std::size_t c) BOOST_NOEXCEPT :
ptr_(x.node_), bucket_(b), bucket_count_(c) {}
cl_iterator(node_pointer n, std::size_t b, std::size_t c) BOOST_NOEXCEPT :
ptr_(n), bucket_(b), bucket_count_(c) {}

cl_iterator(boost::unordered::iterator_detail::l_iterator<
Node, Policy> const& x) BOOST_NOEXCEPT :
Expand Down Expand Up @@ -186,10 +184,6 @@ namespace boost { namespace unordered { namespace iterator_detail {
#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
template <typename>
friend struct boost::unordered::iterator_detail::c_iterator;
template <typename, typename>
friend struct boost::unordered::iterator_detail::l_iterator;
template <typename, typename>
friend struct boost::unordered::iterator_detail::cl_iterator;
template <typename>
friend struct boost::unordered::detail::table;
template <typename>
Expand Down Expand Up @@ -359,21 +353,6 @@ namespace boost { namespace unordered { namespace detail {

template <typename T>
inline node_pointer copy_of(T const& v) {
if (nodes_) {
node_tmp<NodeAlloc> a(pop_node(), constructor_.alloc_);
a.node_->value() = v;
return a.release();
}
else {
constructor_.create_node();
boost::unordered::detail::func::call_construct(
constructor_.alloc_, constructor_.node_->value_ptr(), v);
return constructor_.release();
}
}

template <typename T1, typename T2>
inline node_pointer copy_of(std::pair<T1 const, T2> const& v) {
if (nodes_) {
constructor_.reclaim(pop_node());
}
Expand All @@ -387,22 +366,6 @@ namespace boost { namespace unordered { namespace detail {

template <typename T>
inline node_pointer move_copy_of(T& v) {
if (nodes_) {
node_tmp<NodeAlloc> a(pop_node(), constructor_.alloc_);
a.node_->value() = boost::move(v);
return a.release();
}
else {
constructor_.create_node();
boost::unordered::detail::func::call_construct(
constructor_.alloc_, constructor_.node_->value_ptr(),
boost::move(v));
return constructor_.release();
}
}

template <typename T1, typename T2>
inline node_pointer move_copy_of(std::pair<T1 const, T2>& v) {
if (nodes_) {
constructor_.reclaim(pop_node());
}
Expand All @@ -428,7 +391,7 @@ namespace boost { namespace unordered { namespace detail {
node_pointer p = nodes_;
nodes_ = static_cast<node_pointer>(p->next_);

boost::unordered::detail::func::destroy_value_impl(constructor_.alloc_,
boost::unordered::detail::func::call_destroy(constructor_.alloc_,
p->value_ptr());
boost::unordered::detail::func::destroy(boost::addressof(*p));
node_allocator_traits::deallocate(constructor_.alloc_, p, 1);
Expand Down
227 changes: 117 additions & 110 deletions include/boost/unordered/detail/equivalent.hpp
View file

Large diffs are not rendered by default.

18 changes: 18 additions & 0 deletions include/boost/unordered/detail/map.hpp
View file
Expand Up @@ -31,6 +31,15 @@ namespace boost { namespace unordered { namespace detail {
extractor;

typedef typename boost::unordered::detail::pick_policy<K>::type policy;

typedef boost::unordered::iterator_detail::
iterator<node> iterator;
typedef boost::unordered::iterator_detail::
c_iterator<node> c_iterator;
typedef boost::unordered::iterator_detail::
l_iterator<node, policy> l_iterator;
typedef boost::unordered::iterator_detail::
cl_iterator<node, policy> cl_iterator;
};

template <typename A, typename K, typename M, typename H, typename P>
Expand All @@ -56,6 +65,15 @@ namespace boost { namespace unordered { namespace detail {
extractor;

typedef typename boost::unordered::detail::pick_policy<K>::type policy;

typedef boost::unordered::iterator_detail::
iterator<node> iterator;
typedef boost::unordered::iterator_detail::
c_iterator<node> c_iterator;
typedef boost::unordered::iterator_detail::
l_iterator<node, policy> l_iterator;
typedef boost::unordered::iterator_detail::
cl_iterator<node, policy> cl_iterator;
};

}}}
18 changes: 18 additions & 0 deletions include/boost/unordered/detail/set.hpp
View file
Expand Up @@ -29,6 +29,15 @@ namespace boost { namespace unordered { namespace detail {
typedef boost::unordered::detail::set_extractor<value_type> extractor;

typedef typename boost::unordered::detail::pick_policy<T>::type policy;

typedef boost::unordered::iterator_detail::
c_iterator<node> iterator;
typedef boost::unordered::iterator_detail::
c_iterator<node> c_iterator;
typedef boost::unordered::iterator_detail::
cl_iterator<node, policy> l_iterator;
typedef boost::unordered::iterator_detail::
cl_iterator<node, policy> cl_iterator;
};

template <typename A, typename T, typename H, typename P>
Expand All @@ -53,5 +62,14 @@ namespace boost { namespace unordered { namespace detail {
typedef boost::unordered::detail::set_extractor<value_type> extractor;

typedef typename boost::unordered::detail::pick_policy<T>::type policy;

typedef boost::unordered::iterator_detail::
c_iterator<node> iterator;
typedef boost::unordered::iterator_detail::
c_iterator<node> c_iterator;
typedef boost::unordered::iterator_detail::
cl_iterator<node, policy> l_iterator;
typedef boost::unordered::iterator_detail::
cl_iterator<node, policy> cl_iterator;
};
}}}
57 changes: 24 additions & 33 deletions include/boost/unordered/detail/table.hpp
View file
Expand Up @@ -84,6 +84,10 @@ namespace boost { namespace unordered { namespace detail {
typedef typename Types::table table_impl;
typedef typename Types::link_pointer link_pointer;
typedef typename Types::policy policy;
typedef typename Types::iterator iterator;
typedef typename Types::c_iterator c_iterator;
typedef typename Types::l_iterator l_iterator;
typedef typename Types::cl_iterator cl_iterator;

typedef boost::unordered::detail::functions<
typename Types::hasher,
Expand All @@ -110,15 +114,6 @@ namespace boost { namespace unordered { namespace detail {
typedef boost::unordered::detail::node_tmp<node_allocator>
node_tmp;

typedef boost::unordered::iterator_detail::
iterator<node> iterator;
typedef boost::unordered::iterator_detail::
c_iterator<node> c_iterator;
typedef boost::unordered::iterator_detail::
l_iterator<node, policy> l_iterator;
typedef boost::unordered::iterator_detail::
cl_iterator<node, policy> cl_iterator;

////////////////////////////////////////////////////////////////////////
// Members

Expand All @@ -130,6 +125,13 @@ namespace boost { namespace unordered { namespace detail {
std::size_t max_load_;
bucket_pointer buckets_;

////////////////////////////////////////////////////////////////////////
// Node functions

static inline node_pointer next_node(link_pointer n) {
return static_cast<node_pointer>(n->next_);
}

////////////////////////////////////////////////////////////////////////
// Data access

Expand Down Expand Up @@ -176,16 +178,16 @@ namespace boost { namespace unordered { namespace detail {
return get_bucket(bucket_index)->next_;
}

iterator begin() const
node_pointer begin() const
{
return size_ ? iterator(get_previous_start()->next_) : iterator();
return size_ ? next_node(get_previous_start()) : node_pointer();
}

iterator begin(std::size_t bucket_index) const
node_pointer begin(std::size_t bucket_index) const
{
if (!size_) return iterator();
if (!size_) return node_pointer();
link_pointer prev = get_previous_start(bucket_index);
return prev ? iterator(prev->next_) : iterator();
return prev ? next_node(prev) : node_pointer();
}

std::size_t hash_to_bucket(std::size_t hash_value) const
Expand All @@ -202,14 +204,14 @@ namespace boost { namespace unordered { namespace detail {

std::size_t bucket_size(std::size_t index) const
{
iterator it = begin(index);
if (!it.node_) return 0;
node_pointer n = begin(index);
if (!n) return 0;

std::size_t count = 0;
while(it.node_ && hash_to_bucket(it.node_->hash_) == index)
while(n && hash_to_bucket(n->hash_) == index)
{
++count;
++it;
n = next_node(n);
}

return count;
Expand Down Expand Up @@ -462,7 +464,7 @@ namespace boost { namespace unordered { namespace detail {
node_pointer n = static_cast<node_pointer>(prev->next_);
prev->next_ = n->next_;

boost::unordered::detail::func::destroy_value_impl(node_alloc(),
boost::unordered::detail::func::call_destroy(node_alloc(),
n->value_ptr());
boost::unordered::detail::func::destroy(boost::addressof(*n));
node_allocator_traits::deallocate(node_alloc(), n, 1);
Expand Down Expand Up @@ -698,7 +700,7 @@ namespace boost { namespace unordered { namespace detail {
// Find Node

template <typename Key, typename Hash, typename Pred>
iterator generic_find_node(
node_pointer generic_find_node(
Key const& k,
Hash const& hf,
Pred const& eq) const
Expand All @@ -707,31 +709,20 @@ namespace boost { namespace unordered { namespace detail {
find_node_impl(policy::apply_hash(hf, k), k, eq);
}

iterator find_node(
node_pointer find_node(
std::size_t key_hash,
key_type const& k) const
{
return static_cast<table_impl const*>(this)->
find_node_impl(key_hash, k, this->key_eq());
}

iterator find_node(key_type const& k) const
node_pointer find_node(key_type const& k) const
{
return static_cast<table_impl const*>(this)->
find_node_impl(hash(k), k, this->key_eq());
}

iterator find_matching_node(iterator n) const
{
// TODO: Does this apply to C++11?
//
// For some stupid reason, I decided to support equality comparison
// when different hash functions are used. So I can't use the hash
// value from the node here.

return find_node(get_key(*n));
}

// Reserve and rehash

void reserve_for_insert(std::size_t);
Expand Down
152 changes: 80 additions & 72 deletions include/boost/unordered/detail/unique.hpp
View file
Expand Up @@ -106,17 +106,19 @@ namespace boost { namespace unordered { namespace detail {
template <typename A, typename T>
struct pick_node
{
typedef typename boost::remove_const<T>::type nonconst;

typedef boost::unordered::detail::allocator_traits<
typename boost::unordered::detail::rebind_wrap<A,
boost::unordered::detail::ptr_node<T> >::type
boost::unordered::detail::ptr_node<nonconst> >::type
> tentative_node_traits;

typedef boost::unordered::detail::allocator_traits<
typename boost::unordered::detail::rebind_wrap<A,
boost::unordered::detail::ptr_bucket >::type
> tentative_bucket_traits;

typedef pick_node2<A, T,
typedef pick_node2<A, nonconst,
typename tentative_node_traits::pointer,
typename tentative_bucket_traits::pointer> pick;

Expand Down Expand Up @@ -184,47 +186,53 @@ namespace boost { namespace unordered { namespace detail {
this->move_init(x);
}

// Node functions.

static inline node_pointer next_node(link_pointer n) {
return static_cast<node_pointer>(n->next_);
}

// Accessors

template <class Key, class Pred>
iterator find_node_impl(
node_pointer find_node_impl(
std::size_t key_hash,
Key const& k,
Pred const& eq) const
{
std::size_t bucket_index = this->hash_to_bucket(key_hash);
iterator n = this->begin(bucket_index);
node_pointer n = this->begin(bucket_index);

for (;;)
{
if (!n.node_) return n;
if (!n) return n;

std::size_t node_hash = n.node_->hash_;
std::size_t node_hash = n->hash_;
if (key_hash == node_hash)
{
if (eq(k, this->get_key(*n)))
if (eq(k, this->get_key(n->value())))
return n;
}
else
{
if (this->hash_to_bucket(node_hash) != bucket_index)
return iterator();
return node_pointer();
}

++n;
n = next_node(n);
}
}

std::size_t count(key_type const& k) const
{
return this->find_node(k).node_ ? 1 : 0;
return this->find_node(k) ? 1 : 0;
}

value_type& at(key_type const& k) const
{
if (this->size_) {
iterator it = this->find_node(k);
if (it.node_) return *it;
node_pointer n = this->find_node(k);
if (n) return n->value();
}

boost::throw_exception(
Expand All @@ -234,10 +242,8 @@ namespace boost { namespace unordered { namespace detail {
std::pair<iterator, iterator>
equal_range(key_type const& k) const
{
iterator n = this->find_node(k);
iterator n2 = n;
if (n2.node_) ++n2;
return std::make_pair(n, n2);
node_pointer n = this->find_node(k);
return std::make_pair(iterator(n), iterator(n ? next_node(n) : n));
}

// equals
Expand All @@ -246,11 +252,11 @@ namespace boost { namespace unordered { namespace detail {
{
if(this->size_ != other.size_) return false;

for(iterator n1 = this->begin(); n1.node_; ++n1)
for(node_pointer n1 = this->begin(); n1; n1 = next_node(n1))
{
iterator n2 = other.find_matching_node(n1);
node_pointer n2 = other.find_node(other.get_key(n1->value()));

if (!n2.node_ || *n1 != *n2)
if (!n2 || n1->value() != n2->value())
return false;
}

Expand All @@ -259,7 +265,7 @@ namespace boost { namespace unordered { namespace detail {

// Emplace/Insert

inline iterator add_node(
inline node_pointer add_node(
node_pointer n,
std::size_t key_hash)
{
Expand All @@ -273,7 +279,7 @@ namespace boost { namespace unordered { namespace detail {

if (start_node->next_) {
this->get_bucket(this->hash_to_bucket(
static_cast<node_pointer>(start_node->next_)->hash_)
next_node(start_node)->hash_)
)->next_ = n;
}

Expand All @@ -288,10 +294,10 @@ namespace boost { namespace unordered { namespace detail {
}

++this->size_;
return iterator(n);
return n;
}

inline iterator resize_and_add_node(node_pointer n, std::size_t key_hash)
inline node_pointer resize_and_add_node(node_pointer n, std::size_t key_hash)
{
node_tmp b(n, this->node_alloc());
this->reserve_for_insert(this->size_ + 1);
Expand All @@ -301,11 +307,15 @@ namespace boost { namespace unordered { namespace detail {
value_type& operator[](key_type const& k)
{
std::size_t key_hash = this->hash(k);
iterator pos = this->find_node(key_hash, k);
if (pos.node_) return *pos;
return *this->resize_and_add_node(
boost::unordered::detail::func::construct_pair(this->node_alloc(), k),
key_hash);
node_pointer pos = this->find_node(key_hash, k);
if (pos) {
return pos->value();
}
else {
return this->resize_and_add_node(
boost::unordered::detail::func::construct_node_pair(this->node_alloc(), k),
key_hash)->value();
}
}

#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
Expand All @@ -314,29 +324,29 @@ namespace boost { namespace unordered { namespace detail {
boost::unordered::detail::please_ignore_this_overload> const&)
{
BOOST_ASSERT(false);
return emplace_return(this->begin(), false);
return emplace_return(iterator(), false);
}

iterator emplace_hint(c_iterator,
boost::unordered::detail::emplace_args1<
boost::unordered::detail::please_ignore_this_overload> const&)
{
BOOST_ASSERT(false);
return this->begin();
return iterator();
}
# else
emplace_return emplace(
boost::unordered::detail::please_ignore_this_overload const&)
{
BOOST_ASSERT(false);
return emplace_return(this->begin(), false);
return emplace_return(iterator(), false);
}

iterator emplace_hint(c_iterator,
boost::unordered::detail::please_ignore_this_overload const&)
{
BOOST_ASSERT(false);
return this->begin();
return iterator();
}
# endif
#endif
Expand Down Expand Up @@ -403,16 +413,16 @@ namespace boost { namespace unordered { namespace detail {
BOOST_UNORDERED_EMPLACE_ARGS)
{
std::size_t key_hash = this->hash(k);
iterator pos = this->find_node(key_hash, k);
if (pos.node_) {
return emplace_return(pos, false);
node_pointer pos = this->find_node(key_hash, k);
if (pos) {
return emplace_return(iterator(pos), false);
}
else {
return emplace_return(
this->resize_and_add_node(
boost::unordered::detail::func::construct_value_generic(
iterator(this->resize_and_add_node(
boost::unordered::detail::func::construct_node_from_args(
this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD),
key_hash),
key_hash)),
true);
}
}
Expand All @@ -422,39 +432,39 @@ namespace boost { namespace unordered { namespace detail {
BOOST_UNORDERED_EMPLACE_ARGS)
{
node_tmp b(
boost::unordered::detail::func::construct_value_generic(
boost::unordered::detail::func::construct_node_from_args(
this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD),
this->node_alloc());
key_type const& k = this->get_key(b.node_->value());
if (hint.node_ && this->key_eq()(k, this->get_key(*hint))) {
return iterator(hint.node_);
}
std::size_t key_hash = this->hash(k);
iterator pos = this->find_node(key_hash, k);
if (pos.node_) {
return pos;
node_pointer pos = this->find_node(key_hash, k);
if (pos) {
return iterator(pos);
}
else {
return this->resize_and_add_node(b.release(), key_hash);
return iterator(this->resize_and_add_node(b.release(), key_hash));
}
}

template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
emplace_return emplace_impl(no_key, BOOST_UNORDERED_EMPLACE_ARGS)
{
node_tmp b(
boost::unordered::detail::func::construct_value_generic(
boost::unordered::detail::func::construct_node_from_args(
this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD),
this->node_alloc());
key_type const& k = this->get_key(b.node_->value());
std::size_t key_hash = this->hash(k);
iterator pos = this->find_node(key_hash, k);
if (pos.node_) {
return emplace_return(pos, false);
node_pointer pos = this->find_node(key_hash, k);
if (pos) {
return emplace_return(iterator(pos), false);
}
else {
return emplace_return(
this->resize_and_add_node(b.release(), key_hash),
iterator(this->resize_and_add_node(b.release(), key_hash)),
true);
}
}
Expand Down Expand Up @@ -495,11 +505,11 @@ namespace boost { namespace unordered { namespace detail {
{
// No side effects in this initial code
std::size_t key_hash = this->hash(k);
iterator pos = this->find_node(key_hash, k);
node_pointer pos = this->find_node(key_hash, k);

if (!pos.node_) {
if (!pos) {
node_tmp b(
boost::unordered::detail::func::construct_value(this->node_alloc(), *i),
boost::unordered::detail::func::construct_node(this->node_alloc(), *i),
this->node_alloc());
if(this->size_ + 1 > this->max_load_)
this->reserve_for_insert(this->size_ +
Expand All @@ -521,9 +531,9 @@ namespace boost { namespace unordered { namespace detail {

key_type const& k = this->get_key(b.node_->value());
std::size_t key_hash = this->hash(k);
iterator pos = this->find_node(key_hash, k);
node_pointer pos = this->find_node(key_hash, k);

if (pos.node_) {
if (pos) {
a.reclaim(b.release());
}
else {
Expand Down Expand Up @@ -552,18 +562,17 @@ namespace boost { namespace unordered { namespace detail {
for (;;)
{
if (!prev->next_) return 0;
std::size_t node_hash =
static_cast<node_pointer>(prev->next_)->hash_;
std::size_t node_hash = next_node(prev)->hash_;
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())))
next_node(prev)->value())))
break;
prev = prev->next_;
}

link_pointer end = static_cast<node_pointer>(prev->next_)->next_;
link_pointer end = next_node(prev)->next_;

std::size_t deleted_count = this->delete_nodes(prev, end);
this->fix_bucket(bucket_index, prev);
Expand All @@ -573,10 +582,9 @@ namespace boost { namespace unordered { namespace detail {
iterator erase(c_iterator r)
{
BOOST_ASSERT(r.node_);
iterator next(r.node_);
++next;
erase_nodes(r.node_, next.node_);
return next;
node_pointer next = next_node(r.node_);
erase_nodes(r.node_, next);
return iterator(next);
}

iterator erase_range(c_iterator r1, c_iterator r2)
Expand Down Expand Up @@ -607,36 +615,36 @@ namespace boost { namespace unordered { namespace detail {
void copy_buckets(table const& src) {
this->create_buckets(this->bucket_count_);

for(iterator n = src.begin(); n.node_; ++n) {
for(node_pointer n = src.begin(); n; n = next_node(n)) {
this->add_node(
boost::unordered::detail::func::construct_value(
this->node_alloc(), *n), n.node_->hash_);
boost::unordered::detail::func::construct_node(
this->node_alloc(), n->value()), n->hash_);
}
}

void move_buckets(table const& src) {
this->create_buckets(this->bucket_count_);

for(iterator n = src.begin(); n.node_; ++n) {
for(node_pointer n = src.begin(); n; n = next_node(n)) {
this->add_node(
boost::unordered::detail::func::construct_value(
this->node_alloc(), boost::move(*n)), n.node_->hash_);
boost::unordered::detail::func::construct_node(
this->node_alloc(), boost::move(n->value())), n->hash_);
}
}

void assign_buckets(table const& src)
{
node_holder<node_allocator> holder(*this);
for(iterator n = src.begin(); n.node_; ++n) {
this->add_node(holder.copy_of(*n), n.node_->hash_);
for(node_pointer n = src.begin(); n; n = next_node(n)) {
this->add_node(holder.copy_of(n->value()), n->hash_);
}
}

void move_assign_buckets(table& src)
{
node_holder<node_allocator> holder(*this);
for(iterator n = src.begin(); n.node_; ++n) {
this->add_node(holder.move_copy_of(*n), n.node_->hash_);
for(node_pointer n = src.begin(); n; n = next_node(n)) {
this->add_node(holder.move_copy_of(n->value()), n->hash_);
}
}

Expand All @@ -655,7 +663,7 @@ namespace boost { namespace unordered { namespace detail {
// pre: prev->next_ is not null.
static link_pointer place_in_bucket(table& dst, link_pointer prev)
{
node_pointer n = static_cast<node_pointer>(prev->next_);
node_pointer n = next_node(prev);
bucket_pointer b = dst.get_bucket(dst.hash_to_bucket(n->hash_));

if (!b->next_) {
Expand Down
260 changes: 226 additions & 34 deletions include/boost/unordered/unordered_map.hpp
View file

Large diffs are not rendered by default.

254 changes: 223 additions & 31 deletions include/boost/unordered/unordered_set.hpp
View file

Large diffs are not rendered by default.

4 changes: 4 additions & 0 deletions test/Jamfile.v2
View file
Expand Up @@ -14,6 +14,7 @@ project unordered-test/unordered
<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>clang:<cxxflags>"-pedantic -Wstrict-aliasing -fstrict-aliasing -Wextra -Wsign-promo -Wunused-parameter -Wsign-conversion -Wconversion -Wfloat-equal -Wshadow"
<toolset>msvc:<cxxflags>"/wd4494"
;

#alias framework : /boost/test//boost_unit_test_framework ;
Expand All @@ -27,6 +28,9 @@ test-suite unordered
[ run unordered/minimal_allocator.cpp ]
[ run unordered/compile_set.cpp ]
[ run unordered/compile_map.cpp ]
[ run unordered/compile_map.cpp : :
: <define>BOOST_UNORDERED_USE_ALLOCATOR_TRAITS=0
: compile_map_unordered_allocator ]
[ run unordered/noexcept_tests.cpp ]
[ run unordered/link_test_1.cpp unordered/link_test_2.cpp ]
[ run unordered/incomplete_test.cpp ]
Expand Down
35 changes: 25 additions & 10 deletions test/helpers/exception_test.hpp
View file
Expand Up @@ -179,12 +179,13 @@ namespace test {
class test_runner
{
Test const& test_;
bool exception_in_check_;

test_runner(test_runner const&);
test_runner& operator=(test_runner const&);
public:
test_runner(Test const& t) : test_(t) {}
void operator()() const {
test_runner(Test const& t) : test_(t), exception_in_check_(false) {}
void run() {
DISABLE_EXCEPTIONS;
test::scope = "";
BOOST_DEDUCED_TYPENAME Test::data_type x(test_.init());
Expand All @@ -199,14 +200,24 @@ namespace test {
>(&Test::run, test_, x, strong);
}
catch(...) {
call_ignore_extra_parameters<
Test,
BOOST_DEDUCED_TYPENAME Test::data_type const,
BOOST_DEDUCED_TYPENAME Test::strong_type const
>(&Test::check, test_, constant(x), constant(strong));
try {
DISABLE_EXCEPTIONS;
call_ignore_extra_parameters<
Test,
BOOST_DEDUCED_TYPENAME Test::data_type const,
BOOST_DEDUCED_TYPENAME Test::strong_type const
>(&Test::check, test_, constant(x), constant(strong));
} catch(...) {
exception_in_check_ = true;
}
throw;
}
}
void end() {
if (exception_in_check_) {
BOOST_ERROR("Unexcpected exception in test_runner check call.");
}
}
};

// Quick exception testing based on lightweight test
Expand Down Expand Up @@ -236,26 +247,30 @@ namespace test {

iteration = 0;
bool success = false;
char const* error_msg = 0;
do {
++iteration;
count = 0;

try {
runner();
runner.run();
success = true;
}
catch(test_failure) {
BOOST_ERROR("test_failure caught.");
error_msg = "test_failure caught.";
break;
}
catch(test_exception) {
continue;
}
catch(...) {
BOOST_ERROR("Unexpected exception.");
error_msg = "Unexpected exception.";
break;
}
} while(!success);

if (error_msg) { BOOST_ERROR(error_msg); }
runner.end();
}
}
}
Expand Down
4 changes: 4 additions & 0 deletions test/objects/cxx11_allocator.hpp
View file
Expand Up @@ -201,9 +201,11 @@ namespace test
public move_allocator_base<Flags>,
Flags
{
#if BOOST_WORKAROUND(BOOST_GCC_VERSION, < 402000)
template <typename U> struct rebind {
typedef cxx11_allocator<U, Flags> other;
};
#endif

explicit cxx11_allocator(int t = 0)
: cxx11_allocator_base<T>(t)
Expand Down Expand Up @@ -251,9 +253,11 @@ namespace test
return tmp;
}

#if BOOST_WORKAROUND(BOOST_GCC_VERSION, < 402000)
template <typename U> struct rebind {
typedef cxx11_allocator<U, Flags> other;
};
#endif

explicit cxx11_allocator(int t = 0)
: cxx11_allocator_base<T>(t)
Expand Down
2 changes: 1 addition & 1 deletion test/objects/minimal.hpp
View file
Expand Up @@ -447,7 +447,7 @@ namespace minimal
{
public:
typedef T value_type;
template <class U> struct rebind { typedef cxx11_allocator<U> other; };
//template <class U> struct rebind { typedef cxx11_allocator<U> other; };

cxx11_allocator() {}
template <class Y> cxx11_allocator(cxx11_allocator<Y> const&) {}
Expand Down
8 changes: 4 additions & 4 deletions test/unordered/compile_map.cpp
View file
Expand Up @@ -24,15 +24,15 @@ template class boost::unordered_map<
std::equal_to<int>,
test::minimal::allocator<std::pair<int const, int> > >;
template class boost::unordered_multimap<
int,
int,
int const,
int const,
boost::hash<int>,
std::equal_to<int>,
test::minimal::allocator<std::pair<int const, int> > >;

template class boost::unordered_map<
test::minimal::assignable,
test::minimal::default_assignable,
test::minimal::assignable const,
test::minimal::default_assignable const,
test::minimal::hash<test::minimal::assignable>,
test::minimal::equal_to<test::minimal::assignable>,
test::minimal::allocator<test::minimal::assignable> >;
Expand Down
4 changes: 2 additions & 2 deletions test/unordered/compile_set.cpp
View file
Expand Up @@ -23,13 +23,13 @@ template class boost::unordered_set<
std::equal_to<int>,
test::minimal::allocator<int> >;
template class boost::unordered_multiset<
int,
int const,
boost::hash<int>,
std::equal_to<int>,
test::minimal::allocator<int> >;

template class boost::unordered_set<
test::minimal::assignable,
test::minimal::assignable const,
test::minimal::hash<test::minimal::assignable>,
test::minimal::equal_to<test::minimal::assignable>,
test::minimal::allocator<test::minimal::assignable> >;
Expand Down
108 changes: 105 additions & 3 deletions test/unordered/compile_tests.hpp
View file
Expand Up @@ -101,7 +101,18 @@ void container_test(X& r, T const&)
static_cast<comparison_type>(
(std::numeric_limits<difference_type>::max)()));

// Constructors

// I don't test the runtime post-conditions here.

#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
// It isn't specified in the container requirements that the no argument
// constructor is implicit, but it is defined that way in the concrete
// container specification.
X u_implicit = {};
sink(u_implicit);
#endif

X u;
BOOST_TEST(u.size() == 0);
BOOST_TEST(X().size() == 0);
Expand All @@ -112,6 +123,8 @@ void container_test(X& r, T const&)
sink(X(a));
X u2(a);
X u3 = a;
X u4(rvalue(a_const));
X u5 = rvalue(a_const);

a.swap(b);
boost::swap(a, b);
Expand All @@ -121,12 +134,25 @@ void container_test(X& r, T const&)

typedef BOOST_DEDUCED_TYPENAME X::allocator_type allocator_type;
test::check_return_type<allocator_type>::equals(a_const.get_allocator());

allocator_type m = a.get_allocator();
sink(X(m));
X c(m);
sink(X(a_const, m));
X c2(a_const, m);
sink(X(rvalue(a_const), m));
X c3(rvalue(a_const), m);

// Avoid unused variable warnings:

sink(u);
sink(u2);
sink(u3);
sink(u4);
sink(u5);
sink(c);
sink(c2);
sink(c3);
}

template <class X>
Expand Down Expand Up @@ -247,6 +273,9 @@ void unordered_map_test(X& r, Key const& k, T const& v)
r.emplace(k, v);
r.emplace(k_lvalue, v_lvalue);
r.emplace(rvalue(k), rvalue(v));

r.emplace(boost::unordered::piecewise_construct,
boost::make_tuple(k), boost::make_tuple(v));
}

template <class X>
Expand Down Expand Up @@ -355,6 +384,7 @@ void unordered_test(X& x, Key& k, Hash& hf, Pred& eq)
typedef BOOST_DEDUCED_TYPENAME
boost::iterator_reference<const_local_iterator>::type
const_local_iterator_reference;
typedef BOOST_DEDUCED_TYPENAME X::allocator_type allocator_type;

BOOST_STATIC_ASSERT((boost::is_same<Key, key_type>::value));
//boost::function_requires<boost::CopyConstructibleConcept<key_type> >();
Expand Down Expand Up @@ -387,15 +417,29 @@ void unordered_test(X& x, Key& k, Hash& hf, Pred& eq)
BOOST_STATIC_ASSERT((boost::is_same<const_local_iterator_reference,
const_iterator_reference>::value));

X a;
allocator_type m = a.get_allocator();

// Constructors

X(10, hf, eq);
X a(10, hf, eq);
X a1(10, hf, eq);
X(10, hf);
X a2(10, hf);
X(10);
X a3(10);
X();
X a4;

X(10, hf, eq, m);
X a1a(10, hf, eq, m);
X(10, hf, m);
X a2a(10, hf, m);
X(10, m);
X a3a(10, m);
(X(m));
X a4a(m);

test::check_return_type<size_type>::equals(a.erase(k));

const_iterator q1 = a.cbegin(), q2 = a.cend();
Expand Down Expand Up @@ -438,9 +482,14 @@ void unordered_test(X& x, Key& k, Hash& hf, Pred& eq)
// Avoid unused variable warnings:

sink(a);
sink(a1);
sink(a2);
sink(a3);
sink(a4);
sink(a1a);
sink(a2a);
sink(a3a);
sink(a4a);
}

template <class X, class Key, class T, class Hash, class Pred>
Expand All @@ -450,14 +499,17 @@ void unordered_copyable_test(X& x, Key& k, T& t, Hash& hf, Pred& eq)

typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
typedef BOOST_DEDUCED_TYPENAME X::const_iterator const_iterator;
typedef BOOST_DEDUCED_TYPENAME X::allocator_type allocator_type;

X a;
allocator_type m = a.get_allocator();

BOOST_DEDUCED_TYPENAME X::value_type* i = 0;
BOOST_DEDUCED_TYPENAME X::value_type* j = 0;

X(i, j, 10, hf, eq);
// Constructors

X(i, j, 10, hf, eq);
X a5(i, j, 10, hf, eq);
X(i, j, 10, hf);
X a6(i, j, 10, hf);
Expand All @@ -466,11 +518,38 @@ void unordered_copyable_test(X& x, Key& k, T& t, Hash& hf, Pred& eq)
X(i, j);
X a8(i, j);

X(i, j, 10, hf, eq, m);
X a5a(i, j, 10, hf, eq, m);
X(i, j, 10, hf, m);
X a6a(i, j, 10, hf, m);
X(i, j, 10, m);
X a7a(i, j, 10, m);

// Not specified for some reason (maybe ambiguity with another constructor?)
//X(i, j, m);
//X a8a(i, j, m);
//sink(a8a);

#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
std::size_t min_buckets = 10;
X({t});
X({t}, min_buckets);
X({t}, min_buckets, hf);
X({t}, min_buckets, hf, eq);
//X({t}, m);
X({t}, min_buckets, m);
X({t}, min_buckets, hf, m);
X({t}, min_buckets, hf, eq, m);
#endif

X const b;
sink(X(b));
X a9(b);
a = b;

sink(X(b, m));
X a9a(b, m);

const_iterator q = a.cbegin();

test::check_return_type<iterator>::equals(a.insert(q, t));
Expand Down Expand Up @@ -502,6 +581,10 @@ void unordered_copyable_test(X& x, Key& k, T& t, Hash& hf, Pred& eq)
sink(a7);
sink(a8);
sink(a9);
sink(a5a);
sink(a6a);
sink(a7a);
sink(a9a);
}

template <class X, class Key, class T, class Hash, class Pred>
Expand All @@ -511,6 +594,7 @@ void unordered_movable_test(X& x, Key& k, T& /* t */, Hash& hf, Pred& eq)

typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
typedef BOOST_DEDUCED_TYPENAME X::const_iterator const_iterator;
typedef BOOST_DEDUCED_TYPENAME X::allocator_type allocator_type;

#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
X x1(rvalue_default<X>());
Expand All @@ -519,9 +603,14 @@ void unordered_movable_test(X& x, Key& k, T& /* t */, Hash& hf, Pred& eq)
x2 = boost::move(x1);
#endif

X a;
allocator_type m = a.get_allocator();

test::minimal::constructor_param* i = 0;
test::minimal::constructor_param* j = 0;

// Constructors

X(i, j, 10, hf, eq);
X a5(i, j, 10, hf, eq);
X(i, j, 10, hf);
Expand All @@ -531,7 +620,17 @@ void unordered_movable_test(X& x, Key& k, T& /* t */, Hash& hf, Pred& eq)
X(i, j);
X a8(i, j);

X a;
X(i, j, 10, hf, eq, m);
X a5a(i, j, 10, hf, eq, m);
X(i, j, 10, hf, m);
X a6a(i, j, 10, hf, m);
X(i, j, 10, m);
X a7a(i, j, 10, m);

// Not specified for some reason (maybe ambiguity with another constructor?)
//X(i, j, m);
//X a8a(i, j, m);
//sink(a8a);

const_iterator q = a.cbegin();

Expand Down Expand Up @@ -565,6 +664,9 @@ void unordered_movable_test(X& x, Key& k, T& /* t */, Hash& hf, Pred& eq)
sink(a6);
sink(a7);
sink(a8);
sink(a5a);
sink(a6a);
sink(a7a);
sink(a10);
}

Expand Down
2 changes: 2 additions & 0 deletions test/unordered/insert_tests.cpp
View file
Expand Up @@ -434,6 +434,7 @@ void move_emplace_tests(X*, test::random_generator generator)
template <class X>
void default_emplace_tests(X*, test::random_generator)
{
#if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100))
std::cerr<<"emplace() tests.\n";
bool is_unique = test::has_unique_keys<X>::value;

Expand Down Expand Up @@ -464,6 +465,7 @@ void default_emplace_tests(X*, test::random_generator)

BOOST_TEST(x.count(test::get_key<X>(y)) == (is_unique ? 1u : 2u));
BOOST_TEST(*x.equal_range(test::get_key<X>(y)).first == y);
#endif
}

template <class X>
Expand Down