This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: Add std::unordered_* C++11 allocator support
- From: François Dumont <frs dot dumont at gmail dot com>
- To: Jonathan Wakely <jwakely dot gcc at gmail dot com>
- Cc: Paolo Carlini <paolo dot carlini at oracle dot com>, "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>
- Date: Tue, 02 Apr 2013 22:39:17 +0200
- Subject: Re: Add std::unordered_* C++11 allocator support
- References: <51438861 dot 9010207 at gmail dot com> <5145A358 dot 4020104 at oracle dot com> <CAH6eHdQjrkLFa2rNZnq9ndkBs4sgZ4EXgxSWW=LX0kOK4i88Ww at mail dot gmail dot com>
Here is an updated, exception safe, version.
To validate it I have implemented a number of enhancements to the
exception test framework, mostly to the basic safety test:
- The allocator label is incremented throughout all tested methods
rather than reseted to 0 before each method. Adding more tests I had the
problem of a container containing memory allocated through a method with
label N and detected as memory leak when checking an other method later.
- I have added a check that there is no memory allocated left after all
methods got tested. To make this assumption sure I prefer to make
test_base a stateless class and instantiate everything in the run
method. This way, once outside scope of instantiation, there should be
nothing left.
- I have added check on correct invocation of allocator
construct/destroy. It is limited to C++11 mode, I will check if I can
remove this limitation.
- I have added check of copy assignment and move assignment for basic
exception safety
I plan to add a state information on the throw_allocator_base so
that I can test exception safety on operations dealing with not equal
allocators, does it sound ok ?
I also face an issue regarding implementation of copy assignment
operator. When allocators are not equal we need to release memory before
reallocating everything once __alloc_on_copy has been called. The
problem is that if this method or the allocation following throw we end
up with a _Hashtable instance having no memory allocated. I prefer not
to call __alloc_on_copy the other way and prepare the _Hashtable for
this situation. Some code was not expecting 0 buckets, like the %
operation, so I had to make _Hashtable ready for that adding some
__builtin_except calls. Doing so I have been able to leave the
_Hashtable instance alloc free after a move and not reallocate a small
number of buckets to surely free it just a little bit later.
Let me know what you think about it.
François
On 03/17/2013 02:11 PM, Jonathan Wakely wrote:
On 17 March 2013 11:04, Paolo Carlini wrote:
Hi,
On 03/15/2013 09:45 PM, François Dumont wrote:
Hello
I think I have completed support of C++11 allocators in unordered
containers.
Thanks. I think Jon can review this patch of yours much better than me.
Yes, I'm working through it :-)
It looks great so far.
There's no rush because I don't think we should commit it to trunk
until after 4.8.0 is released, so the unordered container code doesn't
diverge on trunk and the 4.8 branch until it's released, just to ease
debugging if a problem turns up in a release candidate.
Index: include/ext/throw_allocator.h
===================================================================
--- include/ext/throw_allocator.h (revision 197307)
+++ include/ext/throw_allocator.h (working copy)
@@ -90,7 +90,7 @@
annotate_base()
{
label();
- map();
+ map_alloc();
}
static void
@@ -111,8 +111,8 @@
std::__throw_logic_error(error.c_str());
}
- const_iterator found = map().find(p);
- if (found != map().end())
+ const_iterator found = map_alloc().find(p);
+ if (found != map_alloc().end())
{
std::string error("annotate_base::insert double insert!\n");
log_to_string(error, make_entry(p, size));
@@ -120,22 +120,52 @@
std::__throw_logic_error(error.c_str());
}
- map().insert(make_entry(p, size));
+ map_alloc().insert(make_entry(p, size));
}
void
erase(void* p, size_t size)
{
check_allocated(p, size);
- map().erase(p);
+ map_alloc().erase(p);
}
+#if __cplusplus >= 201103L
+ void
+ insert_construct(void* p)
+ {
+ if (!p)
+ {
+ std::string error("annotate_base::insert_construct null!\n");
+ std::__throw_logic_error(error.c_str());
+ }
+
+ auto found = map_construct().find(p);
+ if (found != map_construct().end())
+ {
+ std::string error("annotate_base::insert_construct double insert!\n");
+ log_to_string(error, std::make_pair(p, get_label()));
+ log_to_string(error, *found);
+ std::__throw_logic_error(error.c_str());
+ }
+
+ map_construct().insert(std::make_pair(p, get_label()));
+ }
+
+ void
+ erase_construct(void* p)
+ {
+ check_constructed(p);
+ map_construct().erase(p);
+ }
+#endif
+
// See if a particular address and allocation size has been saved.
inline void
check_allocated(void* p, size_t size)
{
- const_iterator found = map().find(p);
- if (found == map().end())
+ const_iterator found = map_alloc().find(p);
+ if (found == map_alloc().end())
{
std::string error("annotate_base::check_allocated by value "
"null erase!\n");
@@ -155,32 +185,121 @@
// See if a given label has been allocated.
inline void
- check_allocated(size_t label)
+ check(size_t label)
{
- const_iterator beg = map().begin();
- const_iterator end = map().end();
std::string found;
+ {
+ const_iterator beg = map_alloc().begin();
+ const_iterator end = map_alloc().end();
+ while (beg != end)
+ {
+ if (beg->second.first == label)
+ log_to_string(found, *beg);
+ ++beg;
+ }
+ }
+
+#if __cplusplus >= 201103L
+ {
+ auto beg = map_construct().begin();
+ auto end = map_construct().end();
+ while (beg != end)
+ {
+ if (beg->second == label)
+ log_to_string(found, *beg);
+ ++beg;
+ }
+ }
+#endif
+
+ if (!found.empty())
+ {
+ std::string error("annotate_base::check by label\n");
+ error += found;
+ std::__throw_logic_error(error.c_str());
+ }
+ }
+
+ // See if there is anything left allocated or constructed.
+ inline static void
+ check()
+ {
+ std::string found;
+ {
+ const_iterator beg = map_alloc().begin();
+ const_iterator end = map_alloc().end();
+ while (beg != end)
+ {
+ log_to_string(found, *beg);
+ ++beg;
+ }
+ }
+
+#if __cplusplus >= 201103L
+ {
+ auto beg = map_construct().begin();
+ auto end = map_construct().end();
+ while (beg != end)
+ {
+ log_to_string(found, *beg);
+ ++beg;
+ }
+ }
+#endif
+
+ if (!found.empty())
+ {
+ std::string error("annotate_base::check \n");
+ error += found;
+ std::__throw_logic_error(error.c_str());
+ }
+ }
+
+#if __cplusplus >= 201103L
+ inline void
+ check_constructed(void* p)
+ {
+ auto found = map_construct().find(p);
+ if (found == map_construct().end())
+ {
+ std::string error("annotate_base::check_constructed not "
+ "constructed!\n");
+ log_to_string(error, std::make_pair(p, get_label()));
+ std::__throw_logic_error(error.c_str());
+ }
+ }
+
+ inline void
+ check_constructed(size_t label)
+ {
+ auto beg = map_construct().begin();
+ auto end = map_construct().end();
+ std::string found;
while (beg != end)
{
- if (beg->second.first == label)
+ if (beg->second == label)
log_to_string(found, *beg);
++beg;
}
if (!found.empty())
{
- std::string error("annotate_base::check_allocated by label\n");
+ std::string error("annotate_base::check_constructed by label\n");
error += found;
std::__throw_logic_error(error.c_str());
}
}
+#endif
private:
- typedef std::pair<size_t, size_t> data_type;
- typedef std::map<void*, data_type> map_type;
- typedef map_type::value_type entry_type;
- typedef map_type::const_iterator const_iterator;
- typedef map_type::const_reference const_reference;
+ typedef std::pair<size_t, size_t> data_type;
+ typedef std::map<void*, data_type> map_alloc_type;
+ typedef map_alloc_type::value_type entry_type;
+ typedef map_alloc_type::const_iterator const_iterator;
+ typedef map_alloc_type::const_reference const_reference;
+#if __cplusplus >= 201103L
+ typedef std::map<void*, size_t> map_construct_type;
+#endif
friend std::ostream&
operator<<(std::ostream&, const annotate_base&);
@@ -189,8 +308,8 @@
make_entry(void* p, size_t size)
{ return std::make_pair(p, data_type(get_label(), size)); }
- void
- log_to_string(std::string& s, const_reference ref) const
+ static void
+ log_to_string(std::string& s, const_reference ref)
{
char buf[40];
const char tab('\t');
@@ -210,6 +329,24 @@
s += '\n';
}
+#if __cplusplus >= 201103L
+ static void
+ log_to_string(std::string& s, const std::pair<const void*, size_t>& ref)
+ {
+ char buf[40];
+ const char tab('\t');
+ s += "label: ";
+ unsigned long l = static_cast<unsigned long>(ref.second);
+ __builtin_sprintf(buf, "%lu", l);
+ s += buf;
+ s += tab;
+ s += "address: ";
+ __builtin_sprintf(buf, "%p", ref.first);
+ s += buf;
+ s += '\n';
+ }
+#endif
+
static size_t&
label()
{
@@ -217,12 +354,21 @@
return _S_label;
}
- static map_type&
- map()
+ static map_alloc_type&
+ map_alloc()
{
- static map_type _S_map;
+ static map_alloc_type _S_map;
return _S_map;
}
+
+#if __cplusplus >= 201103L
+ static map_construct_type&
+ map_construct()
+ {
+ static map_construct_type _S_map;
+ return _S_map;
+ }
+#endif
};
inline std::ostream&
@@ -230,10 +376,20 @@
{
std::string error;
typedef annotate_base base_type;
- base_type::const_iterator beg = __b.map().begin();
- base_type::const_iterator end = __b.map().end();
- for (; beg != end; ++beg)
- __b.log_to_string(error, *beg);
+ {
+ base_type::const_iterator beg = __b.map_alloc().begin();
+ base_type::const_iterator end = __b.map_alloc().end();
+ for (; beg != end; ++beg)
+ __b.log_to_string(error, *beg);
+ }
+#if __cplusplus >= 201103L
+ {
+ auto beg = __b.map_construct().begin();
+ auto end = __b.map_construct().end();
+ for (; beg != end; ++beg)
+ __b.log_to_string(error, *beg);
+ }
+#endif
return os << error;
}
@@ -685,12 +841,18 @@
template<typename _Up, typename... _Args>
void
construct(_Up* __p, _Args&&... __args)
- { return _M_allocator.construct(__p, std::forward<_Args>(__args)...); }
+ {
+ _M_allocator.construct(__p, std::forward<_Args>(__args)...);
+ insert_construct(__p);
+ }
template<typename _Up>
void
destroy(_Up* __p)
- { _M_allocator.destroy(__p); }
+ {
+ erase_construct(__p);
+ _M_allocator.destroy(__p);
+ }
#else
void
construct(pointer __p, const value_type& val)
@@ -716,8 +878,8 @@
}
void
- check_allocated(size_type __n)
- { annotate_base::check_allocated(__n); }
+ check(size_type __n)
+ { annotate_base::check(__n); }
};
template<typename _Tp, typename _Cond>
@@ -791,13 +953,14 @@
size_t
operator()(const __gnu_cxx::throw_value_limit& __val) const
{
+ __gnu_cxx::throw_value_limit::throw_conditionally();
std::hash<std::size_t> __h;
size_t __result = __h(__val._M_i);
return __result;
}
};
- /// Explicit specialization of std::hash for __gnu_cxx::throw_value_limit.
+ /// Explicit specialization of std::hash for __gnu_cxx::throw_value_random.
template<>
struct hash<__gnu_cxx::throw_value_random>
: public std::unary_function<__gnu_cxx::throw_value_random, size_t>
@@ -805,6 +968,7 @@
size_t
operator()(const __gnu_cxx::throw_value_random& __val) const
{
+ __gnu_cxx::throw_value_random::throw_conditionally();
std::hash<std::size_t> __h;
size_t __result = __h(__val._M_i);
return __result;
Index: include/bits/move.h
===================================================================
--- include/bits/move.h (revision 197307)
+++ include/bits/move.h (working copy)
@@ -121,6 +121,18 @@
move_if_noexcept(_Tp& __x) noexcept
{ return std::move(__x); }
+ template<typename _Tp>
+ struct __move_assign_if_noexcept_cond
+ : public __and_<__not_<is_nothrow_move_assignable<_Tp>>,
+ is_copy_assignable<_Tp>>::type { };
+
+ template<typename _Tp>
+ inline constexpr typename
+ conditional<__move_assign_if_noexcept_cond<_Tp>::value,
+ const _Tp&, _Tp&&>::type
+ __move_assign_if_noexcept(_Tp& __x) noexcept
+ { return std::move(__x); }
+
// declval, from type_traits.
/**
Index: include/bits/hashtable_policy.h
===================================================================
--- include/bits/hashtable_policy.h (revision 197307)
+++ include/bits/hashtable_policy.h (working copy)
@@ -102,6 +102,14 @@
{ return std::get<0>(std::forward<_Tp>(__x)); }
};
+ template<typename _Value>
+ struct _Mutable_Value_Type
+ { typedef _Value type; };
+
+ template<typename _T1, typename _T2>
+ struct _Mutable_Value_Type<std::pair<_T1, _T2>>
+ { typedef std::pair<typename std::remove_const<_T1>::type, _T2> type; };
+
// Auxiliary types used for all instantiations of _Hashtable nodes
// and iterators.
@@ -156,6 +164,43 @@
};
/**
+ * struct _Hash_node_value_base
+ *
+ * Node type with the value to store.
+ */
+ template<typename _Value>
+ struct _Hash_node_value_base : _Hash_node_base
+ {
+ typename aligned_storage<sizeof(_Value), alignment_of<_Value>::value>::type
+ _M_storage;
+
+ _Value*
+ _M_valptr() noexcept
+ { return static_cast<_Value*>(static_cast<void*>(&_M_storage)); }
+
+ const _Value*
+ _M_valptr() const noexcept
+ {
+ return
+ static_cast<const _Value*>(static_cast<const void*>(&_M_storage));
+ }
+
+ _Value&
+ _M_v() noexcept
+ { return *_M_valptr(); }
+
+ const _Value&
+ _M_v() const noexcept
+ { return *_M_valptr(); }
+
+ typedef typename _Mutable_Value_Type<_Value>::type _MValue;
+
+ _MValue&
+ _M_mv() noexcept
+ { return *static_cast<_MValue*>(static_cast<void*>(&_M_storage)); }
+ };
+
+ /**
* Primary template struct _Hash_node.
*/
template<typename _Value, bool _Cache_hash_code>
@@ -164,38 +209,27 @@
/**
* Specialization for nodes with caches, struct _Hash_node.
*
- * Base class is __detail::_Hash_node_base.
+ * Base class is __detail::_Hash_node_value_base.
*/
template<typename _Value>
- struct _Hash_node<_Value, true> : _Hash_node_base
+ struct _Hash_node<_Value, true> : _Hash_node_value_base<_Value>
{
- _Value _M_v;
std::size_t _M_hash_code;
- template<typename... _Args>
- _Hash_node(_Args&&... __args)
- : _M_v(std::forward<_Args>(__args)...), _M_hash_code() { }
-
_Hash_node*
- _M_next() const { return static_cast<_Hash_node*>(_M_nxt); }
+ _M_next() const { return static_cast<_Hash_node*>(this->_M_nxt); }
};
/**
* Specialization for nodes without caches, struct _Hash_node.
*
- * Base class is __detail::_Hash_node_base.
+ * Base class is __detail::_Hash_node_value_base.
*/
template<typename _Value>
- struct _Hash_node<_Value, false> : _Hash_node_base
+ struct _Hash_node<_Value, false> : _Hash_node_value_base<_Value>
{
- _Value _M_v;
-
- template<typename... _Args>
- _Hash_node(_Args&&... __args)
- : _M_v(std::forward<_Args>(__args)...) { }
-
_Hash_node*
- _M_next() const { return static_cast<_Hash_node*>(_M_nxt); }
+ _M_next() const { return static_cast<_Hash_node*>(this->_M_nxt); }
};
/// Base class for node iterators.
@@ -255,11 +289,11 @@
reference
operator*() const
- { return this->_M_cur->_M_v; }
+ { return this->_M_cur->_M_v(); }
pointer
operator->() const
- { return std::__addressof(this->_M_cur->_M_v); }
+ { return this->_M_cur->_M_valptr(); }
_Node_iterator&
operator++()
@@ -307,11 +341,11 @@
reference
operator*() const
- { return this->_M_cur->_M_v; }
+ { return this->_M_cur->_M_v(); }
pointer
operator->() const
- { return std::__addressof(this->_M_cur->_M_v); }
+ { return this->_M_cur->_M_valptr(); }
_Node_const_iterator&
operator++()
@@ -387,6 +421,10 @@
{ return _M_next_resize; }
void
+ _M_reset()
+ { _M_next_resize = 0; }
+
+ void
_M_reset(_State __state)
{ _M_next_resize = __state; }
@@ -496,7 +534,7 @@
return __h->_M_insert_unique_node(__n, __code, __p)->second;
}
- return (__p->_M_v).second;
+ return __p->_M_v().second;
}
template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
@@ -522,7 +560,7 @@
return __h->_M_insert_unique_node(__n, __code, __p)->second;
}
- return (__p->_M_v).second;
+ return __p->_M_v().second;
}
template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
@@ -542,7 +580,7 @@
if (!__p)
__throw_out_of_range(__N("_Map_base::at"));
- return (__p->_M_v).second;
+ return __p->_M_v().second;
}
template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
@@ -562,7 +600,7 @@
if (!__p)
__throw_out_of_range(__N("_Map_base::at"));
- return (__p->_M_v).second;
+ return __p->_M_v().second;
}
/**
@@ -939,7 +977,7 @@
std::size_t
_M_bucket_index(const __node_type* __p, std::size_t __n) const
- { return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); }
+ { return _M_ranged_hash()(_M_extract()(__p->_M_v()), __n); }
void
_M_store_code(__node_type*, __hash_code) const
@@ -1025,7 +1063,7 @@
std::size_t
_M_bucket_index(const __node_type* __p,
std::size_t __n) const
- { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); }
+ { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __n); }
void
_M_store_code(__node_type*, __hash_code) const
@@ -1163,7 +1201,7 @@
static bool
_S_equals(const _Equal& __eq, const _ExtractKey& __extract,
const _Key& __k, _HashCodeType __c, _Hash_node<_Value, true>* __n)
- { return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v)); }
+ { return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v())); }
};
/// Specialization.
@@ -1174,7 +1212,7 @@
static bool
_S_equals(const _Equal& __eq, const _ExtractKey& __extract,
const _Key& __k, _HashCodeType, _Hash_node<_Value, false>* __n)
- { return __eq(__k, __extract(__n->_M_v)); }
+ { return __eq(__k, __extract(__n->_M_v())); }
};
@@ -1305,11 +1343,11 @@
reference
operator*() const
- { return this->_M_cur->_M_v; }
+ { return this->_M_cur->_M_v(); }
pointer
operator->() const
- { return std::__addressof(this->_M_cur->_M_v); }
+ { return this->_M_cur->_M_valptr(); }
_Local_iterator&
operator++()
@@ -1364,11 +1402,11 @@
reference
operator*() const
- { return this->_M_cur->_M_v; }
+ { return this->_M_cur->_M_v(); }
pointer
operator->() const
- { return std::__addressof(this->_M_cur->_M_v); }
+ { return this->_M_cur->_M_valptr(); }
_Local_const_iterator&
operator++()
@@ -1662,6 +1700,198 @@
{ }
};
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash,
+ typename _RehashPolicy, typename _Traits,
+ bool = std::is_copy_assignable<
+ typename _Mutable_Value_Type<_Value>::type>::value>
+ struct _ReuseOrAllocNode
+ {
+ private:
+ using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
+ _Equal, _H1, _H2, _Hash,
+ _RehashPolicy, _Traits>;
+ using __alloc_type = typename __hashtable::_Value_alloc_type;
+ using __alloc_traits = typename __hashtable::_Value_alloc_traits;
+ using __node_type = typename __hashtable::__node_type;
+
+ public:
+ _ReuseOrAllocNode(__node_type* __nodes, __hashtable& __h)
+ : _M_nodes(__nodes), _M_h(__h) { }
+ _ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete;
+
+ ~_ReuseOrAllocNode()
+ { _M_h._M_deallocate_nodes(_M_nodes); }
+
+ __node_type*
+ operator()(const __node_type* __n) const
+ {
+ if (_M_nodes)
+ {
+ __node_type* __node = _M_nodes;
+ _M_nodes = _M_nodes->_M_next();
+ __node->_M_nxt = nullptr;
+ __alloc_type __a(_M_h._M_node_allocator());
+ __alloc_traits::destroy(__a, __node->_M_valptr());
+ __try
+ {
+ __alloc_traits::construct(__a, __node->_M_valptr(), __n->_M_v());
+ }
+ __catch(...)
+ {
+ __node->~__node_type();
+ __alloc_traits::deallocate(__a, __node, 1);
+ __throw_exception_again;
+ }
+ return __node;
+ }
+ return _M_h._M_allocate_node(__n->_M_v());
+ }
+
+ mutable __node_type* _M_nodes;
+ __hashtable& _M_h;
+ };
+
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash,
+ typename _RehashPolicy, typename _Traits>
+ struct _ReuseOrAllocNode<_Key, _Value, _Alloc, _ExtractKey,
+ _Equal, _H1, _H2, _Hash,
+ _RehashPolicy, _Traits,
+ true>
+ {
+ private:
+ using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
+ _Equal, _H1, _H2, _Hash,
+ _RehashPolicy, _Traits>;
+ using __node_type = typename __hashtable::__node_type;
+
+ public:
+ _ReuseOrAllocNode(__node_type* __nodes, __hashtable& __h)
+ : _M_nodes(__nodes), _M_h(__h) { }
+ _ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete;
+
+ ~_ReuseOrAllocNode()
+ { _M_h._M_deallocate_nodes(_M_nodes); }
+
+ __node_type*
+ operator()(const __node_type* __n) const
+ {
+ if (_M_nodes)
+ {
+ __node_type* __node = _M_nodes;
+ __node->_M_mv() = __n->_M_v();
+ // Assignment didn't throw, we can unlink the node.
+ _M_nodes = _M_nodes->_M_next();
+ __node->_M_nxt = nullptr;
+ return __node;
+ }
+ return _M_h._M_allocate_node(__n->_M_v());
+ }
+
+ mutable __node_type* _M_nodes;
+ __hashtable& _M_h;
+ };
+
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash,
+ typename _RehashPolicy, typename _Traits,
+ bool = std::is_move_assignable<
+ typename _Mutable_Value_Type<_Value>::type>::value>
+ struct _MoveReuseOrAllocNode
+ {
+ private:
+ using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
+ _Equal, _H1, _H2, _Hash,
+ _RehashPolicy, _Traits>;
+ using __alloc_type = typename __hashtable::_Value_alloc_type;
+ using __alloc_traits = typename __hashtable::_Value_alloc_traits;
+ using __node_type = typename __hashtable::__node_type;
+
+ public:
+ _MoveReuseOrAllocNode(__node_type* __nodes, __hashtable& __h)
+ : _M_nodes(__nodes), _M_h(__h) { }
+ _MoveReuseOrAllocNode(const _MoveReuseOrAllocNode&) = delete;
+
+ ~_MoveReuseOrAllocNode()
+ { _M_h._M_deallocate_nodes(_M_nodes); }
+
+ __node_type*
+ operator()(__node_type* __n) const
+ {
+ if (_M_nodes)
+ {
+ __node_type* __node = _M_nodes;
+ _M_nodes = _M_nodes->_M_next();
+ __node->_M_nxt = nullptr;
+ __alloc_type __a(_M_h._M_node_allocator());
+ __alloc_traits::destroy(__a, __node->_M_valptr());
+ __try
+ {
+ __alloc_traits::construct(__a, __node->_M_valptr(),
+ std::move_if_noexcept(__n->_M_mv()));
+ }
+ __catch(...)
+ {
+ __node->~__node_type();
+ __alloc_traits::deallocate(__a, __node, 1);
+ __throw_exception_again;
+ }
+ return __node;
+ }
+ return _M_h._M_allocate_node(std::move_if_noexcept(__n->_M_mv()));
+ }
+
+ mutable __node_type* _M_nodes;
+ __hashtable& _M_h;
+ };
+
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash,
+ typename _RehashPolicy, typename _Traits>
+ struct _MoveReuseOrAllocNode<_Key, _Value, _Alloc, _ExtractKey,
+ _Equal, _H1, _H2, _Hash,
+ _RehashPolicy, _Traits,
+ true>
+ {
+ private:
+ using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
+ _Equal, _H1, _H2, _Hash,
+ _RehashPolicy, _Traits>;
+ using __node_type = typename __hashtable::__node_type;
+
+ public:
+ _MoveReuseOrAllocNode(__node_type* __nodes, __hashtable& __h)
+ : _M_nodes(__nodes), _M_h(__h) { }
+ _MoveReuseOrAllocNode(const _MoveReuseOrAllocNode&) = delete;
+
+ ~_MoveReuseOrAllocNode()
+ { _M_h._M_deallocate_nodes(_M_nodes); }
+
+ __node_type*
+ operator()(__node_type* __n) const
+ {
+ if (_M_nodes)
+ {
+ __node_type* __node = _M_nodes;
+ __node->_M_mv() = std::__move_assign_if_noexcept(__n->_M_mv());
+ // Assignment didn't throw, we can unlink the node.
+ _M_nodes = _M_nodes->_M_next();
+ __node->_M_nxt = nullptr;
+ return __node;
+ }
+ // else we need to allocate new nodes.
+ return _M_h._M_allocate_node(std::move_if_noexcept(__n->_M_mv()));
+ }
+
+ mutable __node_type* _M_nodes;
+ __hashtable& _M_h;
+ };
+
//@} hashtable-detail
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace __detail
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h (revision 197307)
+++ include/bits/hashtable.h (working copy)
@@ -183,18 +183,23 @@
public __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_H1, _H2, _Hash, _RehashPolicy, _Traits>
{
+ typedef std::allocator_traits<_Alloc> _Alloc_traits;
+ typedef typename _Alloc_traits::template rebind_alloc<_Value>
+ _Value_alloc_type;
+ typedef __gnu_cxx::__alloc_traits<_Value_alloc_type> _Value_alloc_traits;
+
public:
- typedef _Key key_type;
- typedef _Value value_type;
- typedef _Alloc allocator_type;
- typedef _Equal key_equal;
+ typedef _Key key_type;
+ typedef _Value value_type;
+ typedef _Alloc allocator_type;
+ typedef _Equal key_equal;
// mapped_type, if present, comes from _Map_base.
// hasher, if present, comes from _Hash_code_base/_Hashtable_base.
- typedef typename _Alloc::pointer pointer;
- typedef typename _Alloc::const_pointer const_pointer;
- typedef typename _Alloc::reference reference;
- typedef typename _Alloc::const_reference const_reference;
+ typedef typename _Value_alloc_traits::pointer pointer;
+ typedef typename _Value_alloc_traits::const_pointer const_pointer;
+ typedef typename _Value_alloc_traits::reference reference;
+ typedef typename _Value_alloc_traits::const_reference const_reference;
private:
using __rehash_type = _RehashPolicy;
@@ -302,6 +307,20 @@
bool _Constant_iteratorsa, bool _Unique_keysa>
friend struct __detail::_Insert;
+ template<typename _Keya, typename _Valuea, typename _Alloca,
+ typename _ExtractKeya, typename _Equala,
+ typename _H1a, typename _H2a, typename _Hasha,
+ typename _RehashPolicya, typename _Traitsa,
+ bool _IsCopyAssignable>
+ friend struct __detail::_ReuseOrAllocNode;
+
+ template<typename _Keya, typename _Valuea, typename _Alloca,
+ typename _ExtractKeya, typename _Equala,
+ typename _H1a, typename _H2a, typename _Hasha,
+ typename _RehashPolicya, typename _Traitsa,
+ bool _IsMoveAssignable>
+ friend struct __detail::_MoveReuseOrAllocNode;
+
using size_type = typename __hashtable_base::size_type;
using difference_type = typename __hashtable_base::difference_type;
@@ -313,24 +332,29 @@
const_local_iterator;
private:
- typedef typename _Alloc::template rebind<__node_type>::other
- _Node_allocator_type;
- typedef typename _Alloc::template rebind<__bucket_type>::other
- _Bucket_allocator_type;
+ typedef typename _Alloc_traits::template rebind_alloc<__node_type>
+ _Node_alloc_type;
+ // Use __gnu_cxx to benefit from _S_always_equal and al.
+ typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits;
- using __before_begin = __detail::_Before_begin<_Node_allocator_type>;
+ typedef
+ typename _Alloc_traits::template rebind_alloc<__bucket_type>
+ _Bucket_alloc_type;
+ typedef std::allocator_traits<_Bucket_alloc_type> _Bucket_alloc_traits;
+ using __before_begin = __detail::_Before_begin<_Node_alloc_type>;
+
__bucket_type* _M_buckets;
size_type _M_bucket_count;
__before_begin _M_bbegin;
size_type _M_element_count;
_RehashPolicy _M_rehash_policy;
- _Node_allocator_type&
+ _Node_alloc_type&
_M_node_allocator()
{ return _M_bbegin; }
- const _Node_allocator_type&
+ const _Node_alloc_type&
_M_node_allocator() const
{ return _M_bbegin; }
@@ -359,6 +383,10 @@
void
_M_deallocate_buckets(__bucket_type*, size_type __n);
+ void
+ _M_deallocate_buckets()
+ { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
+
// Gets bucket begin, deals with the fact that non-empty buckets contain
// their before begin node.
__node_type*
@@ -368,6 +396,19 @@
_M_begin() const
{ return static_cast<__node_type*>(_M_before_begin()._M_nxt); }
+ template<typename _UnaryOp>
+ void
+ _M_assign(const _Hashtable&, const _UnaryOp&);
+
+ void
+ _M_move_assign(_Hashtable&&, std::true_type);
+
+ void
+ _M_move_assign(_Hashtable&&, std::false_type);
+
+ void
+ _M_reset();
+
public:
// Constructor, destructor, assignment, swap
_Hashtable(size_type __bucket_hint,
@@ -386,8 +427,19 @@
_Hashtable(_Hashtable&&);
+ _Hashtable(const _Hashtable&, const allocator_type&);
+
+ _Hashtable(_Hashtable&&, const allocator_type&);
+
// Use delegating constructors.
explicit
+ _Hashtable(const allocator_type& __a)
+ : _Hashtable(10, _H1(), __detail::_Mod_range_hashing(),
+ __detail::_Default_ranged_hash(), key_equal(),
+ __key_extract(), __a)
+ { }
+
+ explicit
_Hashtable(size_type __n = 10,
const _H1& __hf = _H1(),
const key_equal& __eql = key_equal(),
@@ -420,34 +472,33 @@
{ }
_Hashtable&
- operator=(const _Hashtable& __ht)
- {
- _Hashtable __tmp(__ht);
- this->swap(__tmp);
- return *this;
- }
+ operator=(const _Hashtable& __ht);
_Hashtable&
operator=(_Hashtable&& __ht)
+ noexcept(_Node_alloc_traits::_S_nothrow_move())
{
- // NB: DR 1204.
- // NB: DR 675.
- this->clear();
- this->swap(__ht);
+ constexpr bool __move_storage =
+ _Node_alloc_traits::_S_propagate_on_move_assign()
+ || _Node_alloc_traits::_S_always_equal();
+ _M_move_assign(std::move(__ht),
+ integral_constant<bool, __move_storage>());
return *this;
}
_Hashtable&
operator=(initializer_list<value_type> __l)
{
- this->clear();
+ clear();
this->insert(__l.begin(), __l.end());
return *this;
}
~_Hashtable() noexcept;
- void swap(_Hashtable&);
+ void
+ swap(_Hashtable&)
+ noexcept(_Node_alloc_traits::_S_nothrow_swap());
// Basic container operations
iterator
@@ -488,7 +539,7 @@
size_type
max_size() const noexcept
- { return _M_node_allocator().max_size(); }
+ { return _Node_alloc_traits::max_size(_M_node_allocator()); }
// Observers
key_equal
@@ -682,7 +733,11 @@
size_type
erase(const key_type& __k)
- { return _M_erase(__unique_keys(), __k); }
+ {
+ if (__builtin_expect(_M_bucket_count == 0, false))
+ return 0;
+ return _M_erase(__unique_keys(), __k);
+ }
iterator
erase(const_iterator, const_iterator);
@@ -721,15 +776,18 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
_M_allocate_node(_Args&&... __args)
{
- __node_type* __n = _M_node_allocator().allocate(1);
+ __node_type* __n = _Node_alloc_traits::allocate(_M_node_allocator(), 1);
__try
{
- _M_node_allocator().construct(__n, std::forward<_Args>(__args)...);
+ _Value_alloc_type __a(_M_node_allocator());
+ ::new ((void*)__n) __node_type();
+ _Value_alloc_traits::construct(__a, __n->_M_valptr(),
+ std::forward<_Args>(__args)...);
return __n;
}
__catch(...)
{
- _M_node_allocator().deallocate(__n, 1);
+ _Node_alloc_traits::deallocate(_M_node_allocator(), __n, 1);
__throw_exception_again;
}
}
@@ -743,8 +801,10 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
_M_deallocate_node(__node_type* __n)
{
- _M_node_allocator().destroy(__n);
- _M_node_allocator().deallocate(__n, 1);
+ _Value_alloc_type __a(_M_node_allocator());
+ _Value_alloc_traits::destroy(__a, __n->_M_valptr());
+ __n->~__node_type();
+ _Node_alloc_traits::deallocate(_M_node_allocator(), __n, 1);
}
template<typename _Key, typename _Value,
@@ -774,9 +834,9 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
_M_allocate_buckets(size_type __n)
{
- _Bucket_allocator_type __alloc(_M_node_allocator());
+ _Bucket_alloc_type __alloc(_M_node_allocator());
- __bucket_type* __p = __alloc.allocate(__n);
+ __bucket_type* __p = _Bucket_alloc_traits::allocate(__alloc, __n);
__builtin_memset(__p, 0, __n * sizeof(__bucket_type));
return __p;
}
@@ -788,10 +848,10 @@
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
- _M_deallocate_buckets(__bucket_type* __p, size_type __n)
+ _M_deallocate_buckets(__bucket_type* __bkts, size_type __n)
{
- _Bucket_allocator_type __alloc(_M_node_allocator());
- __alloc.deallocate(__p, __n);
+ _Bucket_alloc_type __alloc(_M_node_allocator());
+ _Bucket_alloc_traits::deallocate(__alloc, __bkts, __n);
}
template<typename _Key, typename _Value,
@@ -822,7 +882,6 @@
: __hashtable_base(__exk, __h1, __h2, __h, __eq),
__map_base(),
__rehash_base(),
- _M_bucket_count(0),
_M_bbegin(__a),
_M_element_count(0),
_M_rehash_policy()
@@ -846,7 +905,6 @@
: __hashtable_base(__exk, __h1, __h2, __h, __eq),
__map_base(),
__rehash_base(),
- _M_bucket_count(0),
_M_bbegin(__a),
_M_element_count(0),
_M_rehash_policy()
@@ -866,7 +924,7 @@
__catch(...)
{
clear();
- _M_deallocate_buckets(_M_buckets, _M_bucket_count);
+ _M_deallocate_buckets();
__throw_exception_again;
}
}
@@ -876,49 +934,266 @@
typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
typename _Traits>
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits>&
+ _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits>::operator=(
+ const _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits>& __ht)
+ {
+ if (&__ht == this)
+ return *this;
+
+ if (_Node_alloc_traits::_S_propagate_on_copy_assign())
+ {
+ auto& __this_alloc = this->_M_node_allocator();
+ auto& __that_alloc = __ht._M_node_allocator();
+ if (!_Node_alloc_traits::_S_always_equal()
+ && __this_alloc != __that_alloc)
+ {
+ // Replacement allocator cannot free existing storage.
+ _M_deallocate_nodes(_M_begin());
+ if (__builtin_expect(_M_bucket_count != 0, true))
+ _M_deallocate_buckets();
+ _M_reset();
+ std::__alloc_on_copy(__this_alloc, __that_alloc);
+ __hashtable_base::operator=(__ht);
+ _M_bucket_count = __ht._M_bucket_count;
+ _M_element_count = __ht._M_element_count;
+ _M_rehash_policy = __ht._M_rehash_policy;
+ __try
+ {
+ _M_assign(__ht,
+ [this](const __node_type* __n)
+ { return _M_allocate_node(__n->_M_v()); });
+ }
+ __catch(...)
+ {
+ // _M_assign took care of deallocating all memory. Now we
+ // must make sure this instance remains in a usable state.
+ _M_reset();
+ __throw_exception_again;
+ }
+ return *this;
+ }
+ std::__alloc_on_copy(__this_alloc, __that_alloc);
+ }
+
+ // Reuse allocated buckets and nodes.
+ __bucket_type* __former_buckets = nullptr;
+ std::size_t __former_bucket_count = _M_bucket_count;
+ const __rehash_state& __former_state = _M_rehash_policy._M_state();
+
+ if (_M_bucket_count != __ht._M_bucket_count)
+ {
+ __former_buckets = _M_buckets;
+ _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
+ _M_bucket_count = __ht._M_bucket_count;
+ }
+ else
+ __builtin_memset(_M_buckets, 0,
+ _M_bucket_count * sizeof(__bucket_type));
+
+ __try
+ {
+ __hashtable_base::operator=(__ht);
+ _M_element_count = __ht._M_element_count;
+ _M_rehash_policy = __ht._M_rehash_policy;
+ __detail::_ReuseOrAllocNode<_Key, _Value, _Alloc, _ExtractKey,
+ _Equal, _H1, _H2, _Hash,
+ _RehashPolicy, _Traits>
+ __roan(_M_begin(), *this);
+ _M_before_begin()._M_nxt = nullptr;
+ _M_assign(__ht, __roan);
+ if (__former_buckets)
+ _M_deallocate_buckets(__former_buckets, __former_bucket_count);
+ }
+ __catch(...)
+ {
+ if (__former_buckets)
+ {
+ // Restore previous buckets.
+ _M_deallocate_buckets();
+ _M_rehash_policy._M_reset(__former_state);
+ _M_buckets = __former_buckets;
+ _M_bucket_count = __former_bucket_count;
+ }
+ __builtin_memset(_M_buckets, 0,
+ _M_bucket_count * sizeof(__bucket_type));
+ __throw_exception_again;
+ }
+ return *this;
+ }
+
+ template<typename _Key, typename _Value,
+ typename _Alloc, typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+ typename _Traits>
+ template<typename _UnaryOp>
+ void
+ _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _M_assign(const _Hashtable& __ht, const _UnaryOp& __node_getter)
+ {
+ __bucket_type* __buckets = nullptr;
+ if (!_M_buckets)
+ _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
+
+ __try
+ {
+ if (!__ht._M_before_begin()._M_nxt)
+ return;
+
+ // First deal with the special first node pointed to by
+ // _M_before_begin.
+ __node_type* __ht_n = __ht._M_begin();
+ __node_type* __this_n = __node_getter(__ht_n);
+ this->_M_copy_code(__this_n, __ht_n);
+ _M_before_begin()._M_nxt = __this_n;
+ _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin();
+
+ // Then deal with other nodes.
+ __node_base* __prev_n = __this_n;
+ for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
+ {
+ __this_n = __node_getter(__ht_n);
+ __prev_n->_M_nxt = __this_n;
+ this->_M_copy_code(__this_n, __ht_n);
+ size_type __bkt = _M_bucket_index(__this_n);
+ if (!_M_buckets[__bkt])
+ _M_buckets[__bkt] = __prev_n;
+ __prev_n = __this_n;
+ }
+ }
+ __catch(...)
+ {
+ clear();
+ if (__buckets)
+ _M_deallocate_buckets();
+ __throw_exception_again;
+ }
+ }
+
+ template<typename _Key, typename _Value,
+ typename _Alloc, typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+ typename _Traits>
+ void
+ _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _M_reset()
+ {
+ _M_rehash_policy._M_reset();
+ _M_bucket_count = 0;
+ _M_buckets = nullptr;
+ _M_before_begin()._M_nxt = nullptr;
+ _M_element_count = 0;
+ }
+
+ template<typename _Key, typename _Value,
+ typename _Alloc, typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+ typename _Traits>
+ void
+ _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _M_move_assign(_Hashtable&& __ht, std::true_type)
+ {
+ _M_deallocate_nodes(_M_begin());
+ if (__builtin_expect(_M_bucket_count != 0, true))
+ _M_deallocate_buckets();
+
+ __hashtable_base::operator=(std::move(__ht));
+ _M_rehash_policy = __ht._M_rehash_policy;
+ _M_buckets = __ht._M_buckets;
+ _M_bucket_count = __ht._M_bucket_count;
+ _M_before_begin()._M_nxt = __ht._M_before_begin()._M_nxt;
+ _M_element_count = __ht._M_element_count;
+ std::__alloc_on_move(_M_node_allocator(), __ht._M_node_allocator());
+
+ // Fix buckets containing the _M_before_begin pointers that can't be
+ // moved.
+ if (_M_begin())
+ _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin();
+ __ht._M_reset();
+ }
+
+ template<typename _Key, typename _Value,
+ typename _Alloc, typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+ typename _Traits>
+ void
+ _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _M_move_assign(_Hashtable&& __ht, std::false_type)
+ {
+ if (__ht._M_node_allocator() == _M_node_allocator())
+ _M_move_assign(std::move(__ht), std::true_type());
+ else
+ {
+ // Can't move memory, move elements then.
+ __bucket_type* __former_buckets = nullptr;
+ size_type __former_bucket_count = _M_bucket_count;
+ const __rehash_state& __former_state = _M_rehash_policy._M_state();
+
+ if (_M_bucket_count != __ht._M_bucket_count)
+ {
+ __former_buckets = _M_buckets;
+ _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
+ _M_bucket_count = __ht._M_bucket_count;
+ }
+ else
+ __builtin_memset(_M_buckets, 0,
+ _M_bucket_count * sizeof(__bucket_type));
+
+ __try
+ {
+ __hashtable_base::operator=(std::move(__ht));
+ _M_element_count = __ht._M_element_count;
+ _M_rehash_policy = __ht._M_rehash_policy;
+ __detail::_MoveReuseOrAllocNode<_Key, _Value, _Alloc, _ExtractKey,
+ _Equal, _H1, _H2, _Hash,
+ _RehashPolicy, _Traits>
+ __mroan(_M_begin(), *this);
+ _M_before_begin()._M_nxt = nullptr;
+ _M_assign(__ht, __mroan);
+ __ht.clear();
+ }
+ __catch(...)
+ {
+ if (__former_buckets)
+ {
+ _M_deallocate_buckets();
+ _M_rehash_policy._M_reset(__former_state);
+ _M_buckets = __former_buckets;
+ _M_bucket_count = __former_bucket_count;
+ }
+ __builtin_memset(_M_buckets, 0,
+ _M_bucket_count * sizeof(__bucket_type));
+ __throw_exception_again;
+ }
+ }
+ }
+
+ template<typename _Key, typename _Value,
+ typename _Alloc, typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+ typename _Traits>
+ _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits>::
_Hashtable(const _Hashtable& __ht)
: __hashtable_base(__ht),
__map_base(__ht),
__rehash_base(__ht),
+ _M_buckets(),
_M_bucket_count(__ht._M_bucket_count),
- _M_bbegin(__ht._M_bbegin),
+ _M_bbegin(_Node_alloc_traits::_S_select_on_copy(
+ __ht._M_node_allocator())),
_M_element_count(__ht._M_element_count),
_M_rehash_policy(__ht._M_rehash_policy)
{
- _M_buckets = _M_allocate_buckets(_M_bucket_count);
- __try
- {
- if (!__ht._M_before_begin()._M_nxt)
- return;
-
- // First deal with the special first node pointed to by
- // _M_before_begin.
- const __node_type* __ht_n = __ht._M_begin();
- __node_type* __this_n = _M_allocate_node(__ht_n->_M_v);
- this->_M_copy_code(__this_n, __ht_n);
- _M_before_begin()._M_nxt = __this_n;
- _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin();
-
- // Then deal with other nodes.
- __node_base* __prev_n = __this_n;
- for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
- {
- __this_n = _M_allocate_node(__ht_n->_M_v);
- __prev_n->_M_nxt = __this_n;
- this->_M_copy_code(__this_n, __ht_n);
- size_type __bkt = _M_bucket_index(__this_n);
- if (!_M_buckets[__bkt])
- _M_buckets[__bkt] = __prev_n;
- __prev_n = __this_n;
- }
- }
- __catch(...)
- {
- clear();
- _M_deallocate_buckets(_M_buckets, _M_bucket_count);
- __throw_exception_again;
- }
+ _M_assign(__ht,
+ [this](const __node_type* __n)
+ { return _M_allocate_node(__n->_M_v()); });
}
template<typename _Key, typename _Value,
@@ -937,14 +1212,11 @@
_M_element_count(__ht._M_element_count),
_M_rehash_policy(__ht._M_rehash_policy)
{
- // Update, if necessary, bucket pointing to before begin that hasn't moved.
+ // Update, if necessary, bucket pointing to before begin that hasn't
+ // moved.
if (_M_begin())
_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin();
- __ht._M_rehash_policy = _RehashPolicy();
- __ht._M_bucket_count = __ht._M_rehash_policy._M_next_bkt(0);
- __ht._M_buckets = __ht._M_allocate_buckets(__ht._M_bucket_count);
- __ht._M_before_begin()._M_nxt = nullptr;
- __ht._M_element_count = 0;
+ __ht._M_reset();
}
template<typename _Key, typename _Value,
@@ -953,10 +1225,70 @@
typename _Traits>
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hashtable(const _Hashtable& __ht, const allocator_type& __a)
+ : __hashtable_base(__ht),
+ __map_base(__ht),
+ __rehash_base(__ht),
+ _M_buckets(),
+ _M_bucket_count(__ht._M_bucket_count),
+ _M_bbegin(_Node_alloc_type(__a)),
+ _M_element_count(__ht._M_element_count),
+ _M_rehash_policy(__ht._M_rehash_policy)
+ {
+ _M_assign(__ht,
+ [this](const __node_type* __n)
+ { return _M_allocate_node(__n->_M_v()); });
+ }
+
+ template<typename _Key, typename _Value,
+ typename _Alloc, typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+ typename _Traits>
+ _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+ _Hashtable(_Hashtable&& __ht, const allocator_type& __a)
+ : __hashtable_base(__ht),
+ __map_base(__ht),
+ __rehash_base(__ht),
+ _M_buckets(),
+ _M_bucket_count(__ht._M_bucket_count),
+ _M_bbegin(_Node_alloc_type(__a)),
+ _M_element_count(__ht._M_element_count),
+ _M_rehash_policy(__ht._M_rehash_policy)
+ {
+ if (__ht._M_node_allocator() == _M_node_allocator())
+ {
+ _M_buckets = __ht._M_buckets;
+ _M_before_begin()._M_nxt = __ht._M_before_begin()._M_nxt;
+ // Update, if necessary, bucket pointing to before begin that hasn't
+ // moved.
+ if (_M_begin())
+ _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin();
+ __ht._M_reset();
+ }
+ else
+ {
+ _M_assign(__ht,
+ [this](__node_type* __n)
+ {
+ return _M_allocate_node(
+ std::move_if_noexcept(__n->_M_mv()));
+ });
+ __ht.clear();
+ }
+ }
+
+ template<typename _Key, typename _Value,
+ typename _Alloc, typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+ typename _Traits>
+ _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits>::
~_Hashtable() noexcept
{
clear();
- _M_deallocate_buckets(_M_buckets, _M_bucket_count);
+ if (_M_buckets)
+ _M_deallocate_buckets();
}
template<typename _Key, typename _Value,
@@ -967,25 +1299,22 @@
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
swap(_Hashtable& __x)
+ noexcept(_Node_alloc_traits::_S_nothrow_swap())
{
// The only base class with member variables is hash_code_base.
// We define _Hash_code_base::_M_swap because different
// specializations have different members.
this->_M_swap(__x);
- // _GLIBCXX_RESOLVE_LIB_DEFECTS
- // 431. Swapping containers with unequal allocators.
- std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator(),
- __x._M_node_allocator());
-
+ std::__alloc_on_swap(_M_node_allocator(), __x._M_node_allocator());
std::swap(_M_rehash_policy, __x._M_rehash_policy);
std::swap(_M_buckets, __x._M_buckets);
std::swap(_M_bucket_count, __x._M_bucket_count);
std::swap(_M_before_begin()._M_nxt, __x._M_before_begin()._M_nxt);
std::swap(_M_element_count, __x._M_element_count);
- // Fix buckets containing the _M_before_begin pointers that
- // can't be swapped.
+ // Fix buckets containing the _M_before_begin pointers that can't be
+ // swapped.
if (_M_begin())
_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin();
if (__x._M_begin())
@@ -1020,10 +1349,13 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
find(const key_type& __k)
{
+ if (__builtin_expect(_M_bucket_count == 0, false))
+ return end();
+
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_find_node(__n, __k, __code);
- return __p ? iterator(__p) : this->end();
+ return __p ? iterator(__p) : end();
}
template<typename _Key, typename _Value,
@@ -1037,10 +1369,13 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
find(const key_type& __k) const
{
+ if (__builtin_expect(_M_bucket_count == 0, false))
+ return end();
+
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_find_node(__n, __k, __code);
- return __p ? const_iterator(__p) : this->end();
+ return __p ? const_iterator(__p) : end();
}
template<typename _Key, typename _Value,
@@ -1054,6 +1389,9 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
count(const key_type& __k) const
{
+ if (__builtin_expect(_M_bucket_count == 0, false))
+ return 0;
+
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_bucket_begin(__n);
@@ -1092,6 +1430,9 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
equal_range(const key_type& __k)
{
+ if (__builtin_expect(_M_bucket_count == 0, false))
+ return std::make_pair(end(), end());
+
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_find_node(__n, __k, __code);
@@ -1106,7 +1447,7 @@
return std::make_pair(iterator(__p), iterator(__p1));
}
else
- return std::make_pair(this->end(), this->end());
+ return std::make_pair(end(), end());
}
template<typename _Key, typename _Value,
@@ -1125,6 +1466,9 @@
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
equal_range(const key_type& __k) const
{
+ if (__builtin_expect(_M_bucket_count == 0, false))
+ return std::make_pair(end(), end());
+
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_find_node(__n, __k, __code);
@@ -1139,7 +1483,7 @@
return std::make_pair(const_iterator(__p), const_iterator(__p1));
}
else
- return std::make_pair(this->end(), this->end());
+ return std::make_pair(end(), end());
}
// Find the node whose key compares equal to k in the bucket n.
@@ -1258,7 +1602,7 @@
{
// First build the node to get access to the hash code
__node_type* __node = _M_allocate_node(std::forward<_Args>(__args)...);
- const key_type& __k = this->_M_extract()(__node->_M_v);
+ const key_type& __k = this->_M_extract()(__node->_M_v());
__hash_code __code;
__try
{
@@ -1301,7 +1645,7 @@
__hash_code __code;
__try
{
- __code = this->_M_hash_code(this->_M_extract()(__node->_M_v));
+ __code = this->_M_hash_code(this->_M_extract()(__node->_M_v()));
}
__catch(...)
{
@@ -1333,7 +1677,7 @@
if (__do_rehash.first)
{
_M_rehash(__do_rehash.second, __saved_state);
- __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v), __code);
+ __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code);
}
this->_M_store_code(__node, __code);
@@ -1373,7 +1717,7 @@
_M_rehash(__do_rehash.second, __saved_state);
this->_M_store_code(__node, __code);
- const key_type& __k = this->_M_extract()(__node->_M_v);
+ const key_type& __k = this->_M_extract()(__node->_M_v());
size_type __bkt = _M_bucket_index(__k, __code);
// Find the node before an equivalent one.
@@ -1722,7 +2066,9 @@
}
__p = __next;
}
- _M_deallocate_buckets(_M_buckets, _M_bucket_count);
+
+ if (__builtin_expect(_M_bucket_count != 0, true))
+ _M_deallocate_buckets();
_M_bucket_count = __n;
_M_buckets = __new_buckets;
}
@@ -1812,7 +2158,8 @@
__new_buckets[__next_bkt] = __prev_p;
}
- _M_deallocate_buckets(_M_buckets, _M_bucket_count);
+ if (__builtin_expect(_M_bucket_count != 0, true))
+ _M_deallocate_buckets();
_M_bucket_count = __n;
_M_buckets = __new_buckets;
}
Index: include/bits/unordered_set.h
===================================================================
--- include/bits/unordered_set.h (revision 197307)
+++ include/bits/unordered_set.h (working copy)
@@ -108,10 +108,10 @@
//@{
/// Iterator-related typedefs.
- typedef typename allocator_type::pointer pointer;
- typedef typename allocator_type::const_pointer const_pointer;
- typedef typename allocator_type::reference reference;
- typedef typename allocator_type::const_reference const_reference;
+ typedef typename _Hashtable::pointer pointer;
+ typedef typename _Hashtable::const_pointer const_pointer;
+ typedef typename _Hashtable::reference reference;
+ typedef typename _Hashtable::const_reference const_reference;
typedef typename _Hashtable::iterator iterator;
typedef typename _Hashtable::const_iterator const_iterator;
typedef typename _Hashtable::local_iterator local_iterator;
@@ -165,6 +165,35 @@
unordered_set(unordered_set&&) = default;
/**
+ * @brief Creates an %unordered_set with no elements.
+ * @param __a An allocator object.
+ */
+ explicit
+ unordered_set(const allocator_type& __a)
+ : _M_h(__a)
+ { }
+
+ /*
+ * @brief Copy constructor with allocator argument.
+ * @param __uset Input %unordered_set to copy.
+ * @param __a An allocator object.
+ */
+ unordered_set(const unordered_set& __uset,
+ const allocator_type& __a)
+ : _M_h(__uset._M_h, __a)
+ { }
+
+ /*
+ * @brief Move constructor with allocator argument.
+ * @param __uset Input %unordered_set to move.
+ * @param __a An allocator object.
+ */
+ unordered_set(unordered_set&& __uset,
+ const allocator_type& __a)
+ : _M_h(std::move(__uset._M_h), __a)
+ { }
+
+ /**
* @brief Builds an %unordered_set from an initializer_list.
* @param __l An initializer_list.
* @param __n Minimal initial number of buckets.
@@ -482,6 +511,7 @@
*/
void
swap(unordered_set& __x)
+ noexcept( noexcept(_M_h.swap(__x._M_h)) )
{ _M_h.swap(__x._M_h); }
// observers.
@@ -713,10 +743,10 @@
//@{
/// Iterator-related typedefs.
- typedef typename allocator_type::pointer pointer;
- typedef typename allocator_type::const_pointer const_pointer;
- typedef typename allocator_type::reference reference;
- typedef typename allocator_type::const_reference const_reference;
+ typedef typename _Hashtable::pointer pointer;
+ typedef typename _Hashtable::const_pointer const_pointer;
+ typedef typename _Hashtable::reference reference;
+ typedef typename _Hashtable::const_reference const_reference;
typedef typename _Hashtable::iterator iterator;
typedef typename _Hashtable::const_iterator const_iterator;
typedef typename _Hashtable::local_iterator local_iterator;
@@ -794,9 +824,38 @@
/// Move assignment operator.
unordered_multiset&
- operator=(unordered_multiset&& __x) = default;
+ operator=(unordered_multiset&&) = default;
/**
+ * @brief Creates an %unordered_multiset with no elements.
+ * @param __a An allocator object.
+ */
+ explicit
+ unordered_multiset(const allocator_type& __a)
+ : _M_h(__a)
+ { }
+
+ /*
+ * @brief Copy constructor with allocator argument.
+ * @param __uset Input %unordered_multiset to copy.
+ * @param __a An allocator object.
+ */
+ unordered_multiset(const unordered_multiset& __umset,
+ const allocator_type& __a)
+ : _M_h(__umset._M_h, __a)
+ { }
+
+ /*
+ * @brief Move constructor with allocator argument.
+ * @param __umset Input %unordered_multiset to move.
+ * @param __a An allocator object.
+ */
+ unordered_multiset(unordered_multiset&& __umset,
+ const allocator_type& __a)
+ : _M_h(std::move(__umset._M_h), __a)
+ { }
+
+ /**
* @brief %Unordered_multiset list assignment operator.
* @param __l An initializer_list.
*
@@ -1070,6 +1129,7 @@
*/
void
swap(unordered_multiset& __x)
+ noexcept( noexcept(_M_h.swap(__x._M_h)) )
{ _M_h.swap(__x._M_h); }
// observers.
Index: include/bits/unordered_map.h
===================================================================
--- include/bits/unordered_map.h (revision 197307)
+++ include/bits/unordered_map.h (working copy)
@@ -113,10 +113,10 @@
//@{
/// Iterator-related typedefs.
- typedef typename allocator_type::pointer pointer;
- typedef typename allocator_type::const_pointer const_pointer;
- typedef typename allocator_type::reference reference;
- typedef typename allocator_type::const_reference const_reference;
+ typedef typename _Hashtable::pointer pointer;
+ typedef typename _Hashtable::const_pointer const_pointer;
+ typedef typename _Hashtable::reference reference;
+ typedef typename _Hashtable::const_reference const_reference;
typedef typename _Hashtable::iterator iterator;
typedef typename _Hashtable::const_iterator const_iterator;
typedef typename _Hashtable::local_iterator local_iterator;
@@ -171,6 +171,35 @@
unordered_map(unordered_map&&) = default;
/**
+ * @brief Creates an %unordered_map with no elements.
+ * @param __a An allocator object.
+ */
+ explicit
+ unordered_map(const allocator_type& __a)
+ : _M_h(__a)
+ { }
+
+ /*
+ * @brief Copy constructor with allocator argument.
+ * @param __uset Input %unordered_map to copy.
+ * @param __a An allocator object.
+ */
+ unordered_map(const unordered_map& __umap,
+ const allocator_type& __a)
+ : _M_h(__umap._M_h, __a)
+ { }
+
+ /*
+ * @brief Move constructor with allocator argument.
+ * @param __uset Input %unordered_map to move.
+ * @param __a An allocator object.
+ */
+ unordered_map(unordered_map&& __umap,
+ const allocator_type& __a)
+ : _M_h(std::move(__umap._M_h), __a)
+ { }
+
+ /**
* @brief Builds an %unordered_map from an initializer_list.
* @param __l An initializer_list.
* @param __n Minimal initial number of buckets.
@@ -508,6 +537,7 @@
*/
void
swap(unordered_map& __x)
+ noexcept( noexcept(_M_h.swap(__x._M_h)) )
{ _M_h.swap(__x._M_h); }
// observers.
@@ -794,10 +824,10 @@
//@{
/// Iterator-related typedefs.
- typedef typename allocator_type::pointer pointer;
- typedef typename allocator_type::const_pointer const_pointer;
- typedef typename allocator_type::reference reference;
- typedef typename allocator_type::const_reference const_reference;
+ typedef typename _Hashtable::pointer pointer;
+ typedef typename _Hashtable::const_pointer const_pointer;
+ typedef typename _Hashtable::reference reference;
+ typedef typename _Hashtable::const_reference const_reference;
typedef typename _Hashtable::iterator iterator;
typedef typename _Hashtable::const_iterator const_iterator;
typedef typename _Hashtable::local_iterator local_iterator;
@@ -852,6 +882,35 @@
unordered_multimap(unordered_multimap&&) = default;
/**
+ * @brief Creates an %unordered_multimap with no elements.
+ * @param __a An allocator object.
+ */
+ explicit
+ unordered_multimap(const allocator_type& __a)
+ : _M_h(__a)
+ { }
+
+ /*
+ * @brief Copy constructor with allocator argument.
+ * @param __uset Input %unordered_multimap to copy.
+ * @param __a An allocator object.
+ */
+ unordered_multimap(const unordered_multimap& __ummap,
+ const allocator_type& __a)
+ : _M_h(__ummap._M_h, __a)
+ { }
+
+ /*
+ * @brief Move constructor with allocator argument.
+ * @param __uset Input %unordered_multimap to move.
+ * @param __a An allocator object.
+ */
+ unordered_multimap(unordered_multimap&& __ummap,
+ const allocator_type& __a)
+ : _M_h(std::move(__ummap._M_h), __a)
+ { }
+
+ /**
* @brief Builds an %unordered_multimap from an initializer_list.
* @param __l An initializer_list.
* @param __n Minimal initial number of buckets.
@@ -1173,6 +1232,7 @@
*/
void
swap(unordered_multimap& __x)
+ noexcept( noexcept(_M_h.swap(__x._M_h)) )
{ _M_h.swap(__x._M_h); }
// observers.
Index: include/std/unordered_set
===================================================================
--- include/std/unordered_set (revision 197307)
+++ include/std/unordered_set (working copy)
@@ -39,9 +39,8 @@
#include <type_traits>
#include <initializer_list>
#include <tuple>
-#include <bits/stl_algobase.h>
#include <bits/allocator.h>
-#include <bits/alloc_traits.h>
+#include <ext/alloc_traits.h>
#include <bits/stl_function.h> // equal_to, _Identity, _Select1st
#include <bits/functional_hash.h>
#include <bits/hashtable.h>
Index: include/std/unordered_map
===================================================================
--- include/std/unordered_map (revision 197307)
+++ include/std/unordered_map (working copy)
@@ -39,9 +39,8 @@
#include <type_traits>
#include <initializer_list>
#include <tuple>
-#include <bits/stl_algobase.h>
#include <bits/allocator.h>
-#include <bits/alloc_traits.h>
+#include <ext/alloc_traits.h>
#include <bits/stl_function.h> // equal_to, _Identity, _Select1st
#include <bits/functional_hash.h>
#include <bits/hashtable.h>
Index: include/debug/unordered_map
===================================================================
--- include/debug/unordered_map (revision 197307)
+++ include/debug/unordered_map (working copy)
@@ -60,6 +60,9 @@
typedef typename _Base::const_local_iterator _Base_const_local_iterator;
typedef typename _Base::local_iterator _Base_local_iterator;
+ typedef __gnu_cxx::__alloc_traits<typename
+ _Base::allocator_type> _Alloc_traits;
+
public:
typedef typename _Base::size_type size_type;
typedef typename _Base::hasher hasher;
@@ -96,13 +99,28 @@
__gnu_debug::__base(__last), __n,
__hf, __eql, __a) { }
- unordered_map(const unordered_map& __x) = default;
+ unordered_map(const unordered_map&) = default;
unordered_map(const _Base& __x)
: _Base(__x) { }
- unordered_map(unordered_map&& __x) = default;
+ unordered_map(unordered_map&&) = default;
+ explicit
+ unordered_map(const allocator_type& __a)
+ : _Base(__a)
+ { }
+
+ unordered_map(const unordered_map& __umap,
+ const allocator_type& __a)
+ : _Base(__umap._M_base(), __a)
+ { }
+
+ unordered_map(unordered_map&& __umap,
+ const allocator_type& __a)
+ : _Base(std::move(__umap._M_base()), __a)
+ { }
+
unordered_map(initializer_list<value_type> __l,
size_type __n = 0,
const hasher& __hf = hasher(),
@@ -115,33 +133,41 @@
unordered_map&
operator=(const unordered_map& __x)
{
- *static_cast<_Base*>(this) = __x;
+ _M_base() = __x._M_base();
this->_M_invalidate_all();
return *this;
}
unordered_map&
operator=(unordered_map&& __x)
+ noexcept(_Alloc_traits::_S_nothrow_move())
{
- // NB: DR 1204.
- // NB: DR 675.
__glibcxx_check_self_move_assign(__x);
- clear();
- swap(__x);
+ bool xfer_memory = _Alloc_traits::_S_propagate_on_move_assign()
+ || __x.get_allocator() == this->get_allocator();
+ _M_base() = std::move(__x._M_base());
+ if (xfer_memory)
+ this->_M_swap(__x);
+ else
+ this->_M_invalidate_all();
+ __x._M_invalidate_all();
return *this;
}
unordered_map&
operator=(initializer_list<value_type> __l)
{
- this->clear();
- this->insert(__l);
+ _M_base() = __l;
+ this->_M_invalidate_all();
return *this;
}
void
swap(unordered_map& __x)
+ noexcept(_Alloc_traits::_S_nothrow_swap())
{
+ if (!_Alloc_traits::_S_propagate_on_swap())
+ __glibcxx_check_equal_allocs(__x);
_Base::swap(__x);
_Safe_base::_M_swap(__x);
}
@@ -490,6 +516,9 @@
typedef typename _Base::const_local_iterator _Base_const_local_iterator;
typedef typename _Base::local_iterator _Base_local_iterator;
+ typedef __gnu_cxx::__alloc_traits<typename
+ _Base::allocator_type> _Alloc_traits;
+
public:
typedef typename _Base::size_type size_type;
typedef typename _Base::hasher hasher;
@@ -526,13 +555,28 @@
__gnu_debug::__base(__last), __n,
__hf, __eql, __a) { }
- unordered_multimap(const unordered_multimap& __x) = default;
+ unordered_multimap(const unordered_multimap&) = default;
unordered_multimap(const _Base& __x)
: _Base(__x) { }
- unordered_multimap(unordered_multimap&& __x) = default;
+ unordered_multimap(unordered_multimap&&) = default;
+ explicit
+ unordered_multimap(const allocator_type& __a)
+ : _Base(__a)
+ { }
+
+ unordered_multimap(const unordered_multimap& __umap,
+ const allocator_type& __a)
+ : _Base(__umap._M_base(), __a)
+ { }
+
+ unordered_multimap(unordered_multimap&& __umap,
+ const allocator_type& __a)
+ : _Base(std::move(__umap._M_base()), __a)
+ { }
+
unordered_multimap(initializer_list<value_type> __l,
size_type __n = 0,
const hasher& __hf = hasher(),
@@ -545,33 +589,41 @@
unordered_multimap&
operator=(const unordered_multimap& __x)
{
- *static_cast<_Base*>(this) = __x;
+ _M_base() = __x._M_base();
this->_M_invalidate_all();
return *this;
}
unordered_multimap&
operator=(unordered_multimap&& __x)
+ noexcept(_Alloc_traits::_S_nothrow_move())
{
- // NB: DR 1204.
- // NB: DR 675.
__glibcxx_check_self_move_assign(__x);
- clear();
- swap(__x);
+ bool xfer_memory = _Alloc_traits::_S_propagate_on_move_assign()
+ || __x.get_allocator() == this->get_allocator();
+ _M_base() = std::move(__x._M_base());
+ if (xfer_memory)
+ this->_M_swap(__x);
+ else
+ this->_M_invalidate_all();
+ __x._M_invalidate_all();
return *this;
}
unordered_multimap&
operator=(initializer_list<value_type> __l)
{
- this->clear();
- this->insert(__l);
+ _M_base() = __l;
+ this->_M_invalidate_all();
return *this;
}
void
swap(unordered_multimap& __x)
+ noexcept(_Alloc_traits::_S_nothrow_swap())
{
+ if (!_Alloc_traits::_S_propagate_on_swap())
+ __glibcxx_check_equal_allocs(__x);
_Base::swap(__x);
_Safe_base::_M_swap(__x);
}
Index: include/debug/unordered_set
===================================================================
--- include/debug/unordered_set (revision 197307)
+++ include/debug/unordered_set (working copy)
@@ -60,6 +60,8 @@
typedef typename _Base::const_local_iterator _Base_const_local_iterator;
typedef typename _Base::local_iterator _Base_local_iterator;
+ typedef __gnu_cxx::__alloc_traits<typename
+ _Base::allocator_type> _Alloc_traits;
public:
typedef typename _Base::size_type size_type;
typedef typename _Base::hasher hasher;
@@ -96,13 +98,28 @@
__gnu_debug::__base(__last), __n,
__hf, __eql, __a) { }
- unordered_set(const unordered_set& __x) = default;
+ unordered_set(const unordered_set&) = default;
unordered_set(const _Base& __x)
: _Base(__x) { }
- unordered_set(unordered_set&& __x) = default;
+ unordered_set(unordered_set&&) = default;
+ explicit
+ unordered_set(const allocator_type& __a)
+ : _Base(__a)
+ { }
+
+ unordered_set(const unordered_set& __uset,
+ const allocator_type& __a)
+ : _Base(__uset._M_base(), __a)
+ { }
+
+ unordered_set(unordered_set&& __uset,
+ const allocator_type& __a)
+ : _Base(std::move(__uset._M_base()), __a)
+ { }
+
unordered_set(initializer_list<value_type> __l,
size_type __n = 0,
const hasher& __hf = hasher(),
@@ -115,33 +132,41 @@
unordered_set&
operator=(const unordered_set& __x)
{
- *static_cast<_Base*>(this) = __x;
+ _M_base() = __x._M_base();
this->_M_invalidate_all();
return *this;
}
unordered_set&
operator=(unordered_set&& __x)
+ noexcept(_Alloc_traits::_S_nothrow_move())
{
- // NB: DR 1204.
- // NB: DR 675.
__glibcxx_check_self_move_assign(__x);
- clear();
- swap(__x);
+ bool xfer_memory = _Alloc_traits::_S_propagate_on_move_assign()
+ || __x.get_allocator() == this->get_allocator();
+ _M_base() = std::move(__x._M_base());
+ if (xfer_memory)
+ this->_M_swap(__x);
+ else
+ this->_M_invalidate_all();
+ __x._M_invalidate_all();
return *this;
}
unordered_set&
operator=(initializer_list<value_type> __l)
{
- this->clear();
- this->insert(__l);
+ _M_base() = __l;
+ this->_M_invalidate_all();
return *this;
}
void
swap(unordered_set& __x)
+ noexcept(_Alloc_traits::_S_nothrow_swap())
{
+ if (!_Alloc_traits::_S_propagate_on_swap())
+ __glibcxx_check_equal_allocs(__x);
_Base::swap(__x);
_Safe_base::_M_swap(__x);
}
@@ -485,6 +510,9 @@
typedef typename _Base::const_local_iterator _Base_const_local_iterator;
typedef typename _Base::local_iterator _Base_local_iterator;
+ typedef __gnu_cxx::__alloc_traits<typename
+ _Base::allocator_type> _Alloc_traits;
+
public:
typedef typename _Base::size_type size_type;
typedef typename _Base::hasher hasher;
@@ -521,13 +549,28 @@
__gnu_debug::__base(__last), __n,
__hf, __eql, __a) { }
- unordered_multiset(const unordered_multiset& __x) = default;
+ unordered_multiset(const unordered_multiset&) = default;
unordered_multiset(const _Base& __x)
: _Base(__x) { }
- unordered_multiset(unordered_multiset&& __x) = default;
+ unordered_multiset(unordered_multiset&&) = default;
+ explicit
+ unordered_multiset(const allocator_type& __a)
+ : _Base(__a)
+ { }
+
+ unordered_multiset(const unordered_multiset& __uset,
+ const allocator_type& __a)
+ : _Base(__uset._M_base(), __a)
+ { }
+
+ unordered_multiset(unordered_multiset&& __uset,
+ const allocator_type& __a)
+ : _Base(std::move(__uset._M_base()), __a)
+ { }
+
unordered_multiset(initializer_list<value_type> __l,
size_type __n = 0,
const hasher& __hf = hasher(),
@@ -540,33 +583,41 @@
unordered_multiset&
operator=(const unordered_multiset& __x)
{
- *static_cast<_Base*>(this) = __x;
+ _M_base() = __x._M_base();
this->_M_invalidate_all();
return *this;
}
unordered_multiset&
operator=(unordered_multiset&& __x)
+ noexcept(_Alloc_traits::_S_nothrow_move())
{
- // NB: DR 1204.
- // NB: DR 675.
__glibcxx_check_self_move_assign(__x);
- clear();
- swap(__x);
+ bool xfer_memory = _Alloc_traits::_S_propagate_on_move_assign()
+ || __x.get_allocator() == this->get_allocator();
+ _M_base() = std::move(__x._M_base());
+ if (xfer_memory)
+ this->_M_swap(__x);
+ else
+ this->_M_invalidate_all();
+ __x._M_invalidate_all();
return *this;
}
unordered_multiset&
operator=(initializer_list<value_type> __l)
{
- this->clear();
- this->insert(__l);
+ _M_base() = __l;
+ this->_M_invalidate_all();
return *this;
}
void
swap(unordered_multiset& __x)
+ noexcept(_Alloc_traits::_S_nothrow_swap())
{
+ if (!_Alloc_traits::_S_propagate_on_swap())
+ __glibcxx_check_equal_allocs(__x);
_Base::swap(__x);
_Safe_base::_M_swap(__x);
}
Index: testsuite/util/exception/safety.h
===================================================================
--- testsuite/util/exception/safety.h (revision 197307)
+++ testsuite/util/exception/safety.h (working copy)
@@ -1292,6 +1292,48 @@
{ throw; }
}
};
+
+ template<typename _Tp>
+ struct assign_operator
+ {
+ _Tp _M_other;
+
+ void
+ operator()(_Tp& __container)
+ {
+ try
+ {
+ // An exception while assigning might leave the container empty
+ // making future attemps less relevant. So we copy it before to
+ // always assign to a non empty container. It also check for copy
+ // constructor exception safety at the same time.
+ _Tp __clone(__container);
+ __clone = _M_other;
+ }
+ catch(const __gnu_cxx::forced_error&)
+ { throw; }
+ }
+ };
+
+
+#if __cplusplus >= 201103L
+ template<typename _Tp>
+ struct move_assign_operator
+ {
+ _Tp _M_other;
+
+ void
+ operator()(_Tp& __container)
+ {
+ try
+ {
+ __container = std::move(_M_other);
+ }
+ catch(const __gnu_cxx::forced_error&)
+ { throw; }
+ }
+ };
+#endif
};
// Base class for exception tests.
@@ -1320,27 +1362,12 @@
typedef swap<container_type> swap;
typedef iterator_operations<container_type> iterator_ops;
typedef const_iterator_operations<container_type> const_iterator_ops;
+ typedef assign_operator<container_type> assign_operator;
+#if __cplusplus >= 201103L
+ typedef move_assign_operator<container_type> move_assign_operator;
+#endif
using base_type::compare;
-
- // Functor objects.
- clear _M_clear;
- erase_point _M_erasep;
- erase_range _M_eraser;
- insert_point _M_insertp;
- emplace _M_emplace;
- emplace_point _M_emplacep;
- emplace_front _M_emplacef;
- emplace_back _M_emplaceb;
- pop_front _M_popf;
- pop_back _M_popb;
- push_front _M_pushf;
- push_back _M_pushb;
- rehash _M_rehash;
- swap _M_swap;
-
- iterator_ops _M_iops;
- const_iterator_ops _M_ciops;
};
@@ -1369,67 +1396,97 @@
using base_type::generate;
- container_type _M_container;
- std::vector<function_type> _M_functions;
-
basic_safety() { run(); }
void
run()
{
- // Setup.
- condition_type::never_adjustor off;
+ {
+ // Setup.
+ condition_type::never_adjustor off;
+
+ // Construct containers.
+ container_type container;
+ populate p1(container);
+
+ // Construct list of member functions to exercise.
+ std::vector<function_type> functions;
+ typename base_type::iterator_ops iops;
+ functions.push_back(function_type(iops));
+ typename base_type::const_iterator_ops ciops;
+ functions.push_back(function_type(ciops));
- // Construct containers.
- populate p1(_M_container);
- populate p2(base_type::_M_swap._M_other);
-
- // Construct list of member functions to exercise.
- _M_functions.push_back(function_type(base_type::_M_iops));
- _M_functions.push_back(function_type(base_type::_M_ciops));
-
- _M_functions.push_back(function_type(base_type::_M_erasep));
- _M_functions.push_back(function_type(base_type::_M_eraser));
- _M_functions.push_back(function_type(base_type::_M_insertp));
- _M_functions.push_back(function_type(base_type::_M_emplace));
- _M_functions.push_back(function_type(base_type::_M_emplacep));
- _M_functions.push_back(function_type(base_type::_M_emplacef));
- _M_functions.push_back(function_type(base_type::_M_emplaceb));
- _M_functions.push_back(function_type(base_type::_M_popf));
- _M_functions.push_back(function_type(base_type::_M_popb));
- _M_functions.push_back(function_type(base_type::_M_pushf));
- _M_functions.push_back(function_type(base_type::_M_pushb));
- _M_functions.push_back(function_type(base_type::_M_rehash));
- _M_functions.push_back(function_type(base_type::_M_swap));
-
- // Last.
- _M_functions.push_back(function_type(base_type::_M_clear));
+ typename base_type::erase_point erasep;
+ functions.push_back(function_type(erasep));
+ typename base_type::erase_range eraser;
+ functions.push_back(function_type(eraser));
+ typename base_type::insert_point insertp;
+ functions.push_back(function_type(insertp));
+ typename base_type::emplace emplace;
+ functions.push_back(function_type(emplace));
+ typename base_type::emplace_point emplacep;
+ functions.push_back(function_type(emplacep));
+ typename base_type::emplace_front emplacef;
+ functions.push_back(function_type(emplacef));
+ typename base_type::emplace_back emplaceb;
+ functions.push_back(function_type(emplaceb));
+ typename base_type::pop_front popf;
+ functions.push_back(function_type(popf));
+ typename base_type::pop_back popb;
+ functions.push_back(function_type(popb));
+ typename base_type::push_front pushf;
+ functions.push_back(function_type(pushf));
+ typename base_type::push_back pushb;
+ functions.push_back(function_type(pushb));
+ typename base_type::rehash rehash;
+ functions.push_back(function_type(rehash));
+ typename base_type::swap swap;
+ populate p2(swap._M_other);
+ functions.push_back(function_type(swap));
+ typename base_type::assign_operator assignop;
+ populate p3(assignop._M_other);
+ functions.push_back(function_type(assignop));
+#if __cplusplus >= 201103L
+ typename base_type::move_assign_operator massignop;
+ populate p4(massignop._M_other);
+ functions.push_back(function_type(massignop));
+#endif
+ // Last.
+ typename base_type::clear clear;
+ functions.push_back(function_type(clear));
- // Run tests.
- for (auto i = _M_functions.begin(); i != _M_functions.end(); ++i)
- {
- function_type& f = *i;
- run_steps_to_limit(f);
- }
+ // Run tests.
+ size_t i(1);
+ for (auto it = functions.begin(); it != functions.end(); ++it)
+ {
+ function_type& f = *it;
+ i = run_steps_to_limit(i, container, f);
+ }
+ }
+
+ // Now that all instances has been destroyed check that there is no
+ // allocation remaining.
+ std::cout << "Checking remaining stuff" << std::endl;
+ __gnu_cxx::annotate_base::check();
}
template<typename _Funct>
- void
- run_steps_to_limit(const _Funct& __f)
+ size_t
+ run_steps_to_limit(size_t __step, container_type& __cont,
+ const _Funct& __f)
{
- size_t i(1);
bool exit(false);
- auto a = _M_container.get_allocator();
+ auto a = __cont.get_allocator();
do
{
// Use the current step as an allocator label.
- a.set_label(i);
+ a.set_label(__step);
try
{
- condition_type::limit_adjustor limit(i);
- __f(_M_container);
+ condition_type::limit_adjustor limit(__step);
+ __f(__cont);
// If we get here, done.
exit = true;
@@ -1438,18 +1495,19 @@
{
// Check this step for allocations.
// NB: Will throw std::logic_error if allocations.
- a.check_allocated(i);
+ a.check(__step);
// Check memory allocated with operator new.
- ++i;
}
+ ++__step;
}
while (!exit);
// Log count info.
std::cout << __f.target_type().name() << std::endl;
- std::cout << "end count " << i << std::endl;
+ std::cout << "end count " << __step << std::endl;
+ return __step;
}
};
@@ -1467,8 +1525,6 @@
typedef typename base_type::populate populate;
typedef __gnu_cxx::random_condition condition_type;
- container_type _M_container;
-
generation_prohibited() { run(); }
void
@@ -1479,10 +1535,13 @@
// propagated and in error. Sudden death!
// Setup.
+ container_type container;
+ typename base_type::swap swap;
+
{
condition_type::never_adjustor off;
- populate p1(_M_container);
- populate p2(base_type::_M_swap._M_other);
+ populate p1(container);
+ populate p2(swap._M_other);
}
// Run tests.
@@ -1493,20 +1552,27 @@
// constructor or assignment operator of value_type throws.
if (!traits<container_type>::has_throwing_erase::value)
{
- this->_M_erasep(_M_container);
- this->_M_eraser(_M_container);
+ typename base_type::erase_point erasep;
+ erasep(container);
+ typename base_type::erase_range eraser;
+ eraser(container);
}
- this->_M_popf(_M_container);
- this->_M_popb(_M_container);
+ typename base_type::pop_front popf;
+ popf(container);
+ typename base_type::pop_back popb;
+ popb(container);
- this->_M_iops(_M_container);
- this->_M_ciops(_M_container);
+ typename base_type::iterator_ops iops;
+ iops(container);
+ typename base_type::const_iterator_ops ciops;
+ ciops(container);
- this->_M_swap(_M_container);
+ swap(container);
// Last.
- this->_M_clear(_M_container);
+ typename base_type::clear clear;
+ clear(container);
}
}
};
@@ -1529,16 +1595,8 @@
using base_type::compare;
- container_type _M_container_test;
- container_type _M_container_control;
- std::vector<function_type> _M_functions;
-
propagation_consistent() { run(); }
- void
- sync()
- { _M_container_test = _M_container_control; }
-
// Run test.
void
run()
@@ -1547,48 +1605,59 @@
condition_type::never_adjustor off;
// Construct containers.
- populate p(_M_container_control);
+ container_type container_control;
+ populate p(container_control);
+
// Construct list of member functions to exercise.
- _M_functions.push_back(function_type(base_type::_M_emplace));
- _M_functions.push_back(function_type(base_type::_M_emplacep));
- _M_functions.push_back(function_type(base_type::_M_emplacef));
- _M_functions.push_back(function_type(base_type::_M_emplaceb));
- _M_functions.push_back(function_type(base_type::_M_pushf));
- _M_functions.push_back(function_type(base_type::_M_pushb));
- _M_functions.push_back(function_type(base_type::_M_insertp));
- _M_functions.push_back(function_type(base_type::_M_rehash));
+ std::vector<function_type> functions;
+ typename base_type::emplace emplace;
+ functions.push_back(function_type(emplace));
+ typename base_type::emplace_point emplacep;
+ functions.push_back(function_type(emplacep));
+ typename base_type::emplace_front emplacef;
+ functions.push_back(function_type(emplacef));
+ typename base_type::emplace_back emplaceb;
+ functions.push_back(function_type(emplaceb));
+ typename base_type::push_front pushf;
+ functions.push_back(function_type(pushf));
+ typename base_type::push_back pushb;
+ functions.push_back(function_type(pushb));
+ typename base_type::insert_point insertp;
+ functions.push_back(function_type(insertp));
+ typename base_type::rehash rehash;
+ functions.push_back(function_type(rehash));
// Run tests.
- for (auto i = _M_functions.begin(); i != _M_functions.end(); ++i)
+ for (auto i = functions.begin(); i != functions.end(); ++i)
{
function_type& f = *i;
- run_steps_to_limit(f);
+ run_steps_to_limit(container_control, f);
}
}
template<typename _Funct>
void
- run_steps_to_limit(const _Funct& __f)
+ run_steps_to_limit(container_type& container_control, const _Funct& __f)
{
size_t i(1);
bool exit(false);
do
{
- sync();
+ container_type container_test(container_control);
try
{
condition_type::limit_adjustor limit(i);
- __f(_M_container_test);
+ __f(container_test);
// If we get here, done.
exit = true;
}
catch(const __gnu_cxx::forced_error&)
{
- compare(_M_container_control, _M_container_test);
+ compare(container_control, container_test);
++i;
}
}
Index: testsuite/util/testsuite_counter_type.h
===================================================================
--- testsuite/util/testsuite_counter_type.h (revision 197307)
+++ testsuite/util/testsuite_counter_type.h (working copy)
@@ -36,24 +36,22 @@
static int move_count;
static int move_assign_count;
#endif
+ static int destructor_count;
int val;
counter_type() : val(0)
- {
- ++default_count;
- }
+ { ++default_count; }
counter_type(int inval) : val(inval)
- {
- ++specialize_count;
- }
+ { ++specialize_count; }
counter_type(const counter_type& in) : val(in.val)
- {
- ++copy_count;
- }
+ { ++copy_count; }
+ ~counter_type()
+ { ++destructor_count; }
+
counter_type&
operator=(const counter_type& in)
{
@@ -70,7 +68,7 @@
}
counter_type&
- operator=(counter_type&& rhs)
+ operator=(counter_type&& rhs) noexcept
{
val = rhs.val;
++move_assign_count;
@@ -90,6 +88,7 @@
move_count = 0;
move_assign_count = 0;
#endif
+ destructor_count = 0;
}
bool operator==(const counter_type& rhs) const
@@ -109,6 +108,7 @@
int counter_type::move_count = 0;
int counter_type::move_assign_count = 0;
#endif
+ int counter_type::destructor_count = 0;
struct counter_type_hasher
{
Index: testsuite/23_containers/unordered_map/allocator/swap.cc
===================================================================
--- testsuite/23_containers/unordered_map/allocator/swap.cc (revision 0)
+++ testsuite/23_containers/unordered_map/allocator/swap.cc (revision 0)
@@ -0,0 +1,96 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+ std::size_t operator()(const T t) const noexcept
+ { return t.i; }
+};
+
+struct equal_to
+{
+ bool operator()(const T& lhs, const T& rhs) const noexcept
+ { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+// It is undefined behaviour to swap() containers wth unequal allocators
+// if the allocator doesn't propagate, so ensure the allocators compare
+// equal, while still being able to test propagation via get_personality().
+bool
+operator==(const propagating_allocator<std::pair<const T, T>, false>&,
+ const propagating_allocator<std::pair<const T, T>, false>&)
+{
+ return true;
+}
+
+bool
+operator!=(const propagating_allocator<std::pair<const T, T>, false>&,
+ const propagating_allocator<std::pair<const T, T>, false>&)
+{
+ return false;
+}
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<std::pair<const T, T>, false> alloc_type;
+ typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ test_type v2(alloc_type(2));
+ v2.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ std::swap(v1, v2);
+ VERIFY(1 == v1.get_allocator().get_personality());
+ VERIFY(2 == v2.get_allocator().get_personality());
+ // swap back so assertions in uneq_allocator::deallocate don't fail
+ std::swap(v1, v2);
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<std::pair<const T, T>, true> alloc_type;
+ typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ test_type v2(alloc_type(2));
+ v2.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ std::swap(v1, v2);
+ VERIFY(2 == v1.get_allocator().get_personality());
+ VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}
Index: testsuite/23_containers/unordered_map/allocator/copy.cc
===================================================================
--- testsuite/23_containers/unordered_map/allocator/copy.cc (revision 0)
+++ testsuite/23_containers/unordered_map/allocator/copy.cc (revision 0)
@@ -0,0 +1,71 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+ std::size_t operator()(const T t) const noexcept
+ { return t.i; }
+};
+
+struct equal_to
+{
+ bool operator()(const T& lhs, const T& rhs) const noexcept
+ { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<T, false> alloc_type;
+ typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ test_type v2(v1);
+ VERIFY(1 == v1.get_allocator().get_personality());
+ VERIFY(0 == v2.get_allocator().get_personality());
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<T, true> alloc_type;
+ typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ test_type v2(v1);
+ VERIFY(1 == v1.get_allocator().get_personality());
+ VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}
Index: testsuite/23_containers/unordered_map/allocator/move_assign.cc
===================================================================
--- testsuite/23_containers/unordered_map/allocator/move_assign.cc (revision 0)
+++ testsuite/23_containers/unordered_map/allocator/move_assign.cc (revision 0)
@@ -0,0 +1,88 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+#include <testsuite_counter_type.h>
+
+using __gnu_test::propagating_allocator;
+using __gnu_test::counter_type;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<counter_type, false> alloc_type;
+ typedef __gnu_test::counter_type_hasher hash;
+ typedef std::unordered_map<counter_type, counter_type, hash,
+ std::equal_to<counter_type>,
+ alloc_type> test_type;
+
+ test_type v1(alloc_type(1));
+ v1.emplace(std::piecewise_construct,
+ std::make_tuple(1), std::make_tuple(1));
+
+ test_type v2(alloc_type(2));
+ v2.emplace(std::piecewise_construct,
+ std::make_tuple(2), std::make_tuple(2));
+
+ counter_type::reset();
+
+ v2 = std::move(v1);
+
+ VERIFY( 1 == v1.get_allocator().get_personality() );
+ VERIFY( 2 == v2.get_allocator().get_personality() );
+
+ VERIFY( counter_type::move_assign_count == 2 );
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<counter_type, true> alloc_type;
+ typedef __gnu_test::counter_type_hasher hash;
+ typedef std::unordered_map<counter_type, counter_type, hash,
+ std::equal_to<counter_type>,
+ alloc_type> test_type;
+
+ test_type v1(alloc_type(1));
+ v1.emplace(std::piecewise_construct,
+ std::make_tuple(1), std::make_tuple(1));
+
+ test_type v2(alloc_type(2));
+ v2.emplace(std::piecewise_construct,
+ std::make_tuple(2), std::make_tuple(2));
+
+ counter_type::reset();
+
+ v2 = std::move(v1);
+
+ VERIFY(0 == v1.get_allocator().get_personality());
+ VERIFY(1 == v2.get_allocator().get_personality());
+
+ VERIFY( counter_type::move_assign_count == 0 );
+ VERIFY( counter_type::destructor_count == 2 );
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}
Index: testsuite/23_containers/unordered_map/allocator/copy_assign.cc
===================================================================
--- testsuite/23_containers/unordered_map/allocator/copy_assign.cc (revision 0)
+++ testsuite/23_containers/unordered_map/allocator/copy_assign.cc (revision 0)
@@ -0,0 +1,77 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+ std::size_t operator()(const T t) const noexcept
+ { return t.i; }
+};
+
+struct equal_to
+{
+ bool operator()(const T& lhs, const T& rhs) const noexcept
+ { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<T, false> alloc_type;
+ typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ test_type v2(alloc_type(2));
+ v2.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ v2 = v1;
+ VERIFY(1 == v1.get_allocator().get_personality());
+ VERIFY(2 == v2.get_allocator().get_personality());
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<T, true> alloc_type;
+ typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ test_type v2(alloc_type(2));
+ v2.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ v2 = v1;
+ VERIFY(1 == v1.get_allocator().get_personality());
+ VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}
Index: testsuite/23_containers/unordered_map/allocator/noexcept.cc
===================================================================
--- testsuite/23_containers/unordered_map/allocator/noexcept.cc (revision 0)
+++ testsuite/23_containers/unordered_map/allocator/noexcept.cc (revision 0)
@@ -0,0 +1,88 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+ std::size_t operator()(const T t) const noexcept
+ { return t.i; }
+};
+
+struct equal_to
+{
+ bool operator()(const T& lhs, const T& rhs) const noexcept
+ { return lhs.i == rhs.i; }
+};
+
+namespace __gnu_test
+{
+ inline void
+ swap(propagating_allocator<T, true>& l, propagating_allocator<T, true>& r)
+ noexcept(false)
+ {
+ typedef uneq_allocator<T> base_alloc;
+ swap(static_cast<base_alloc&>(l), static_cast<base_alloc&>(r));
+ }
+}
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+ typedef std::allocator<T> alloc_type;
+ typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+ test_type v1;
+ test_type v2;
+ // this is a GNU extension for std::allocator
+ static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" );
+ static_assert( noexcept( v1.swap(v2) ), "Swap cannot throw" );
+}
+
+void test02()
+{
+ typedef propagating_allocator<T, false> alloc_type;
+ typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ test_type v2(alloc_type(2));
+ static_assert( !noexcept( v1 = std::move(v2) ), "Move assign can throw" );
+ static_assert( noexcept( v1.swap(v2) ), "Swap cannot throw" );
+}
+
+void test03()
+{
+ typedef propagating_allocator<T, true> alloc_type;
+ typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ test_type v2(alloc_type(2));
+ static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" );
+ // static_assert( !noexcept( v1.swap(v2) ), "Swap can throw" );
+}
+
+int main()
+{
+ test01();
+ test02();
+ test03();
+ return 0;
+}
Index: testsuite/23_containers/unordered_map/allocator/minimal.cc
===================================================================
--- testsuite/23_containers/unordered_map/allocator/minimal.cc (revision 0)
+++ testsuite/23_containers/unordered_map/allocator/minimal.cc (revision 0)
@@ -0,0 +1,63 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <memory>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+ std::size_t operator()(const T t) const noexcept
+ { return t.i; }
+};
+
+struct equal_to
+{
+ bool operator()(const T& lhs, const T& rhs) const noexcept
+ { return lhs.i == rhs.i; }
+};
+
+
+bool operator==(const T& l, const T& r) { return l.i == r.i; }
+bool operator<(const T& l, const T& r) { return l.i < r.i; }
+
+using __gnu_test::SimpleAllocator;
+
+template class std::unordered_map<T, T, hash, equal_to, SimpleAllocator<T>>;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ typedef SimpleAllocator<T> alloc_type;
+ typedef std::allocator_traits<alloc_type> traits_type;
+ typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+ test_type v(alloc_type{});
+ v.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ VERIFY( v.max_size() == traits_type::max_size(v.get_allocator()) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
Index: testsuite/23_containers/unordered_multimap/allocator/noexcept.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/allocator/noexcept.cc (revision 0)
+++ testsuite/23_containers/unordered_multimap/allocator/noexcept.cc (revision 0)
@@ -0,0 +1,88 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+ std::size_t operator()(const T t) const noexcept
+ { return t.i; }
+};
+
+struct equal_to
+{
+ bool operator()(const T& lhs, const T& rhs) const noexcept
+ { return lhs.i == rhs.i; }
+};
+
+namespace __gnu_test
+{
+ inline void
+ swap(propagating_allocator<T, true>& l, propagating_allocator<T, true>& r)
+ noexcept(false)
+ {
+ typedef uneq_allocator<T> base_alloc;
+ swap(static_cast<base_alloc&>(l), static_cast<base_alloc&>(r));
+ }
+}
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+ typedef std::allocator<T> alloc_type;
+ typedef std::unordered_multimap<T, T, hash, equal_to, alloc_type> test_type;
+ test_type v1;
+ test_type v2;
+ // this is a GNU extension for std::allocator
+ static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" );
+ static_assert( noexcept( v1.swap(v2) ), "Swap cannot throw" );
+}
+
+void test02()
+{
+ typedef propagating_allocator<T, false> alloc_type;
+ typedef std::unordered_multimap<T, T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ test_type v2(alloc_type(2));
+ static_assert( !noexcept( v1 = std::move(v2) ), "Move assign can throw" );
+ static_assert( noexcept( v1.swap(v2) ), "Swap cannot throw" );
+}
+
+void test03()
+{
+ typedef propagating_allocator<T, true> alloc_type;
+ typedef std::unordered_multimap<T, T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ test_type v2(alloc_type(2));
+ static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" );
+ // static_assert( !noexcept( v1.swap(v2) ), "Swap can throw" );
+}
+
+int main()
+{
+ test01();
+ test02();
+ test03();
+ return 0;
+}
Index: testsuite/23_containers/unordered_multimap/allocator/minimal.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/allocator/minimal.cc (revision 0)
+++ testsuite/23_containers/unordered_multimap/allocator/minimal.cc (revision 0)
@@ -0,0 +1,64 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <memory>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+ std::size_t operator()(const T t) const noexcept
+ { return t.i; }
+};
+
+struct equal_to
+{
+ bool operator()(const T& lhs, const T& rhs) const noexcept
+ { return lhs.i == rhs.i; }
+};
+
+
+bool operator==(const T& l, const T& r) { return l.i == r.i; }
+bool operator<(const T& l, const T& r) { return l.i < r.i; }
+
+using __gnu_test::SimpleAllocator;
+
+template class std::unordered_multimap<T, T, hash, equal_to,
+ SimpleAllocator<T>>;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ typedef SimpleAllocator<T> alloc_type;
+ typedef std::allocator_traits<alloc_type> traits_type;
+ typedef std::unordered_multimap<T, T, hash, equal_to, alloc_type> test_type;
+ test_type v(alloc_type{});
+ v.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ VERIFY( v.max_size() == traits_type::max_size(v.get_allocator()) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
Index: testsuite/23_containers/unordered_multimap/allocator/swap.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/allocator/swap.cc (revision 0)
+++ testsuite/23_containers/unordered_multimap/allocator/swap.cc (revision 0)
@@ -0,0 +1,96 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+ std::size_t operator()(const T t) const noexcept
+ { return t.i; }
+};
+
+struct equal_to
+{
+ bool operator()(const T& lhs, const T& rhs) const noexcept
+ { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+// It is undefined behaviour to swap() containers wth unequal allocators
+// if the allocator doesn't propagate, so ensure the allocators compare
+// equal, while still being able to test propagation via get_personality().
+bool
+operator==(const propagating_allocator<std::pair<const T, T>, false>&,
+ const propagating_allocator<std::pair<const T, T>, false>&)
+{
+ return true;
+}
+
+bool
+operator!=(const propagating_allocator<std::pair<const T, T>, false>&,
+ const propagating_allocator<std::pair<const T, T>, false>&)
+{
+ return false;
+}
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<std::pair<const T, T>, false> alloc_type;
+ typedef std::unordered_multimap<T, T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ test_type v2(alloc_type(2));
+ v2.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ std::swap(v1, v2);
+ VERIFY(1 == v1.get_allocator().get_personality());
+ VERIFY(2 == v2.get_allocator().get_personality());
+ // swap back so assertions in uneq_allocator::deallocate don't fail
+ std::swap(v1, v2);
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<std::pair<const T, T>, true> alloc_type;
+ typedef std::unordered_multimap<T, T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ test_type v2(alloc_type(2));
+ v2.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ std::swap(v1, v2);
+ VERIFY(2 == v1.get_allocator().get_personality());
+ VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}
Index: testsuite/23_containers/unordered_multimap/allocator/copy.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/allocator/copy.cc (revision 0)
+++ testsuite/23_containers/unordered_multimap/allocator/copy.cc (revision 0)
@@ -0,0 +1,71 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+ std::size_t operator()(const T t) const noexcept
+ { return t.i; }
+};
+
+struct equal_to
+{
+ bool operator()(const T& lhs, const T& rhs) const noexcept
+ { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<T, false> alloc_type;
+ typedef std::unordered_multimap<T, T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ test_type v2(v1);
+ VERIFY(1 == v1.get_allocator().get_personality());
+ VERIFY(0 == v2.get_allocator().get_personality());
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<T, true> alloc_type;
+ typedef std::unordered_multimap<T, T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ test_type v2(v1);
+ VERIFY(1 == v1.get_allocator().get_personality());
+ VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}
Index: testsuite/23_containers/unordered_multimap/allocator/move_assign.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/allocator/move_assign.cc (revision 0)
+++ testsuite/23_containers/unordered_multimap/allocator/move_assign.cc (revision 0)
@@ -0,0 +1,88 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+#include <testsuite_counter_type.h>
+
+using __gnu_test::propagating_allocator;
+using __gnu_test::counter_type;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<counter_type, false> alloc_type;
+ typedef __gnu_test::counter_type_hasher hash;
+ typedef std::unordered_multimap<counter_type, counter_type, hash,
+ std::equal_to<counter_type>,
+ alloc_type> test_type;
+
+ test_type v1(alloc_type(1));
+ v1.emplace(std::piecewise_construct,
+ std::make_tuple(1), std::make_tuple(1));
+
+ test_type v2(alloc_type(2));
+ v2.emplace(std::piecewise_construct,
+ std::make_tuple(2), std::make_tuple(2));
+
+ counter_type::reset();
+
+ v2 = std::move(v1);
+
+ VERIFY( 1 == v1.get_allocator().get_personality() );
+ VERIFY( 2 == v2.get_allocator().get_personality() );
+
+ VERIFY( counter_type::move_assign_count == 2 );
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<counter_type, true> alloc_type;
+ typedef __gnu_test::counter_type_hasher hash;
+ typedef std::unordered_multimap<counter_type, counter_type, hash,
+ std::equal_to<counter_type>,
+ alloc_type> test_type;
+
+ test_type v1(alloc_type(1));
+ v1.emplace(std::piecewise_construct,
+ std::make_tuple(1), std::make_tuple(1));
+
+ test_type v2(alloc_type(2));
+ v2.emplace(std::piecewise_construct,
+ std::make_tuple(2), std::make_tuple(2));
+
+ counter_type::reset();
+
+ v2 = std::move(v1);
+
+ VERIFY(0 == v1.get_allocator().get_personality());
+ VERIFY(1 == v2.get_allocator().get_personality());
+
+ VERIFY( counter_type::move_assign_count == 0 );
+ VERIFY( counter_type::destructor_count == 2 );
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}
Index: testsuite/23_containers/unordered_multimap/allocator/copy_assign.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/allocator/copy_assign.cc (revision 0)
+++ testsuite/23_containers/unordered_multimap/allocator/copy_assign.cc (revision 0)
@@ -0,0 +1,77 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+ std::size_t operator()(const T t) const noexcept
+ { return t.i; }
+};
+
+struct equal_to
+{
+ bool operator()(const T& lhs, const T& rhs) const noexcept
+ { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<T, false> alloc_type;
+ typedef std::unordered_multimap<T, T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ test_type v2(alloc_type(2));
+ v2.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ v2 = v1;
+ VERIFY(1 == v1.get_allocator().get_personality());
+ VERIFY(2 == v2.get_allocator().get_personality());
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<T, true> alloc_type;
+ typedef std::unordered_multimap<T, T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ test_type v2(alloc_type(2));
+ v2.emplace(std::piecewise_construct,
+ std::make_tuple(T()), std::make_tuple(T()));
+ v2 = v1;
+ VERIFY(1 == v1.get_allocator().get_personality());
+ VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}
Index: testsuite/23_containers/unordered_multiset/allocator/copy_assign.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/allocator/copy_assign.cc (revision 0)
+++ testsuite/23_containers/unordered_multiset/allocator/copy_assign.cc (revision 0)
@@ -0,0 +1,73 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+ std::size_t operator()(const T t) const noexcept
+ { return t.i; }
+};
+
+struct equal_to
+{
+ bool operator()(const T& lhs, const T& rhs) const noexcept
+ { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<T, false> alloc_type;
+ typedef std::unordered_multiset<T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.insert(T());
+ test_type v2(alloc_type(2));
+ v2.insert(T());
+ v2 = v1;
+ VERIFY(1 == v1.get_allocator().get_personality());
+ VERIFY(2 == v2.get_allocator().get_personality());
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<T, true> alloc_type;
+ typedef std::unordered_multiset<T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.insert(T());
+ test_type v2(alloc_type(2));
+ v2.insert(T());
+ v2 = v1;
+ VERIFY(1 == v1.get_allocator().get_personality());
+ VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}
Index: testsuite/23_containers/unordered_multiset/allocator/noexcept.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/allocator/noexcept.cc (revision 0)
+++ testsuite/23_containers/unordered_multiset/allocator/noexcept.cc (revision 0)
@@ -0,0 +1,88 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+ std::size_t operator()(const T t) const noexcept
+ { return t.i; }
+};
+
+struct equal_to
+{
+ bool operator()(const T& lhs, const T& rhs) const noexcept
+ { return lhs.i == rhs.i; }
+};
+
+namespace __gnu_test
+{
+ inline void
+ swap(propagating_allocator<T, true>& l, propagating_allocator<T, true>& r)
+ noexcept(false)
+ {
+ typedef uneq_allocator<T> base_alloc;
+ swap(static_cast<base_alloc&>(l), static_cast<base_alloc&>(r));
+ }
+}
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+ typedef std::allocator<T> alloc_type;
+ typedef std::unordered_multiset<T, hash, equal_to, alloc_type> test_type;
+ test_type v1;
+ test_type v2;
+ // this is a GNU extension for std::allocator
+ static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" );
+ static_assert( noexcept( v1.swap(v2) ), "Swap cannot throw" );
+}
+
+void test02()
+{
+ typedef propagating_allocator<T, false> alloc_type;
+ typedef std::unordered_multiset<T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ test_type v2(alloc_type(2));
+ static_assert( !noexcept( v1 = std::move(v2) ), "Move assign can throw" );
+ static_assert( noexcept( v1.swap(v2) ), "Swap cannot throw" );
+}
+
+void test03()
+{
+ typedef propagating_allocator<T, true> alloc_type;
+ typedef std::unordered_multiset<T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ test_type v2(alloc_type(2));
+ static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" );
+ // static_assert( !noexcept( v1.swap(v2) ), "Swap can throw" );
+}
+
+int main()
+{
+ test01();
+ test02();
+ test03();
+ return 0;
+}
Index: testsuite/23_containers/unordered_multiset/allocator/minimal.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/allocator/minimal.cc (revision 0)
+++ testsuite/23_containers/unordered_multiset/allocator/minimal.cc (revision 0)
@@ -0,0 +1,62 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <memory>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+ std::size_t operator()(const T t) const noexcept
+ { return t.i; }
+};
+
+struct equal_to
+{
+ bool operator()(const T& lhs, const T& rhs) const noexcept
+ { return lhs.i == rhs.i; }
+};
+
+
+bool operator==(const T& l, const T& r) { return l.i == r.i; }
+bool operator<(const T& l, const T& r) { return l.i < r.i; }
+
+using __gnu_test::SimpleAllocator;
+
+template class std::unordered_multiset<T, hash, equal_to, SimpleAllocator<T>>;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ typedef SimpleAllocator<T> alloc_type;
+ typedef std::allocator_traits<alloc_type> traits_type;
+ typedef std::unordered_multiset<T, hash, equal_to, alloc_type> test_type;
+ test_type v(alloc_type{});
+ v.insert(T());
+ VERIFY( v.max_size() == traits_type::max_size(v.get_allocator()) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
Index: testsuite/23_containers/unordered_multiset/allocator/swap.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/allocator/swap.cc (revision 0)
+++ testsuite/23_containers/unordered_multiset/allocator/swap.cc (revision 0)
@@ -0,0 +1,92 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+ std::size_t operator()(const T t) const noexcept
+ { return t.i; }
+};
+
+struct equal_to
+{
+ bool operator()(const T& lhs, const T& rhs) const noexcept
+ { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+// It is undefined behaviour to swap() containers wth unequal allocators
+// if the allocator doesn't propagate, so ensure the allocators compare
+// equal, while still being able to test propagation via get_personality().
+bool
+operator==(const propagating_allocator<T, false>&,
+ const propagating_allocator<T, false>&)
+{
+ return true;
+}
+
+bool
+operator!=(const propagating_allocator<T, false>&,
+ const propagating_allocator<T, false>&)
+{
+ return false;
+}
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<T, false> alloc_type;
+ typedef std::unordered_multiset<T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.insert(T());
+ test_type v2(alloc_type(2));
+ v2.insert(T());
+ std::swap(v1, v2);
+ VERIFY(1 == v1.get_allocator().get_personality());
+ VERIFY(2 == v2.get_allocator().get_personality());
+ // swap back so assertions in uneq_allocator::deallocate don't fail
+ std::swap(v1, v2);
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<T, true> alloc_type;
+ typedef std::unordered_multiset<T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.insert(T());
+ test_type v2(alloc_type(2));
+ v2.insert(T());
+ std::swap(v1, v2);
+ VERIFY(2 == v1.get_allocator().get_personality());
+ VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}
Index: testsuite/23_containers/unordered_multiset/allocator/copy.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/allocator/copy.cc (revision 0)
+++ testsuite/23_containers/unordered_multiset/allocator/copy.cc (revision 0)
@@ -0,0 +1,69 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+ std::size_t operator()(const T t) const noexcept
+ { return t.i; }
+};
+
+struct equal_to
+{
+ bool operator()(const T& lhs, const T& rhs) const noexcept
+ { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<T, false> alloc_type;
+ typedef std::unordered_multiset<T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.insert(T());
+ test_type v2(v1);
+ VERIFY(1 == v1.get_allocator().get_personality());
+ VERIFY(0 == v2.get_allocator().get_personality());
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<T, true> alloc_type;
+ typedef std::unordered_multiset<T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.insert(T());
+ test_type v2(v1);
+ VERIFY(1 == v1.get_allocator().get_personality());
+ VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}
Index: testsuite/23_containers/unordered_multiset/allocator/move_assign.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/allocator/move_assign.cc (revision 0)
+++ testsuite/23_containers/unordered_multiset/allocator/move_assign.cc (revision 0)
@@ -0,0 +1,84 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+#include <testsuite_counter_type.h>
+
+using __gnu_test::propagating_allocator;
+using __gnu_test::counter_type;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<counter_type, false> alloc_type;
+ typedef __gnu_test::counter_type_hasher hash;
+ typedef std::unordered_multiset<counter_type, hash,
+ std::equal_to<counter_type>,
+ alloc_type> test_type;
+
+ test_type v1(alloc_type(1));
+ v1.emplace(0);
+
+ test_type v2(alloc_type(2));
+ v2.emplace(1);
+
+ counter_type::reset();
+
+ v2 = std::move(v1);
+
+ VERIFY( 1 == v1.get_allocator().get_personality() );
+ VERIFY( 2 == v2.get_allocator().get_personality() );
+
+ VERIFY( counter_type::move_assign_count == 1 );
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<counter_type, true> alloc_type;
+ typedef __gnu_test::counter_type_hasher hash;
+ typedef std::unordered_multiset<counter_type, hash,
+ std::equal_to<counter_type>,
+ alloc_type> test_type;
+
+ test_type v1(alloc_type(1));
+ v1.emplace(0);
+
+ test_type v2(alloc_type(2));
+ v2.emplace(0);
+
+ counter_type::reset();
+
+ v2 = std::move(v1);
+
+ VERIFY(0 == v1.get_allocator().get_personality());
+ VERIFY(1 == v2.get_allocator().get_personality());
+
+ VERIFY( counter_type::move_assign_count == 0 );
+ VERIFY( counter_type::destructor_count == 1 );
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}
Index: testsuite/23_containers/unordered_set/allocator/noexcept.cc
===================================================================
--- testsuite/23_containers/unordered_set/allocator/noexcept.cc (revision 0)
+++ testsuite/23_containers/unordered_set/allocator/noexcept.cc (revision 0)
@@ -0,0 +1,88 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+ std::size_t operator()(const T t) const noexcept
+ { return t.i; }
+};
+
+struct equal_to
+{
+ bool operator()(const T& lhs, const T& rhs) const noexcept
+ { return lhs.i == rhs.i; }
+};
+
+namespace __gnu_test
+{
+ inline void
+ swap(propagating_allocator<T, true>& l, propagating_allocator<T, true>& r)
+ noexcept(false)
+ {
+ typedef uneq_allocator<T> base_alloc;
+ swap(static_cast<base_alloc&>(l), static_cast<base_alloc&>(r));
+ }
+}
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+ typedef std::allocator<T> alloc_type;
+ typedef std::unordered_set<T, hash, equal_to, alloc_type> test_type;
+ test_type v1;
+ test_type v2;
+ // this is a GNU extension for std::allocator
+ static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" );
+ static_assert( noexcept( v1.swap(v2) ), "Swap cannot throw" );
+}
+
+void test02()
+{
+ typedef propagating_allocator<T, false> alloc_type;
+ typedef std::unordered_set<T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ test_type v2(alloc_type(2));
+ static_assert( !noexcept( v1 = std::move(v2) ), "Move assign can throw" );
+ static_assert( noexcept( v1.swap(v2) ), "Swap cannot throw" );
+}
+
+void test03()
+{
+ typedef propagating_allocator<T, true> alloc_type;
+ typedef std::unordered_set<T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ test_type v2(alloc_type(2));
+ static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" );
+ // static_assert( !noexcept( v1.swap(v2) ), "Swap can throw" );
+}
+
+int main()
+{
+ test01();
+ test02();
+ test03();
+ return 0;
+}
Index: testsuite/23_containers/unordered_set/allocator/minimal.cc
===================================================================
--- testsuite/23_containers/unordered_set/allocator/minimal.cc (revision 0)
+++ testsuite/23_containers/unordered_set/allocator/minimal.cc (revision 0)
@@ -0,0 +1,62 @@
+// Copyright (C) 2012-2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <memory>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+ std::size_t operator()(const T t) const noexcept
+ { return t.i; }
+};
+
+struct equal_to
+{
+ bool operator()(const T& lhs, const T& rhs) const noexcept
+ { return lhs.i == rhs.i; }
+};
+
+
+bool operator==(const T& l, const T& r) { return l.i == r.i; }
+bool operator<(const T& l, const T& r) { return l.i < r.i; }
+
+using __gnu_test::SimpleAllocator;
+
+template class std::unordered_set<T, hash, equal_to, SimpleAllocator<T>>;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ typedef SimpleAllocator<T> alloc_type;
+ typedef std::allocator_traits<alloc_type> traits_type;
+ typedef std::unordered_set<T, hash, equal_to, alloc_type> test_type;
+ test_type v(alloc_type{});
+ v.insert(T());
+ VERIFY( v.max_size() == traits_type::max_size(v.get_allocator()) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
Index: testsuite/23_containers/unordered_set/allocator/swap.cc
===================================================================
--- testsuite/23_containers/unordered_set/allocator/swap.cc (revision 0)
+++ testsuite/23_containers/unordered_set/allocator/swap.cc (revision 0)
@@ -0,0 +1,92 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+ std::size_t operator()(const T t) const noexcept
+ { return t.i; }
+};
+
+struct equal_to
+{
+ bool operator()(const T& lhs, const T& rhs) const noexcept
+ { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+// It is undefined behaviour to swap() containers wth unequal allocators
+// if the allocator doesn't propagate, so ensure the allocators compare
+// equal, while still being able to test propagation via get_personality().
+bool
+operator==(const propagating_allocator<T, false>&,
+ const propagating_allocator<T, false>&)
+{
+ return true;
+}
+
+bool
+operator!=(const propagating_allocator<T, false>&,
+ const propagating_allocator<T, false>&)
+{
+ return false;
+}
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<T, false> alloc_type;
+ typedef std::unordered_set<T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.insert(T());
+ test_type v2(alloc_type(2));
+ v2.insert(T());
+ std::swap(v1, v2);
+ VERIFY(1 == v1.get_allocator().get_personality());
+ VERIFY(2 == v2.get_allocator().get_personality());
+ // swap back so assertions in uneq_allocator::deallocate don't fail
+ std::swap(v1, v2);
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<T, true> alloc_type;
+ typedef std::unordered_set<T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.insert(T());
+ test_type v2(alloc_type(2));
+ v2.insert(T());
+ std::swap(v1, v2);
+ VERIFY(2 == v1.get_allocator().get_personality());
+ VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}
Index: testsuite/23_containers/unordered_set/allocator/copy.cc
===================================================================
--- testsuite/23_containers/unordered_set/allocator/copy.cc (revision 0)
+++ testsuite/23_containers/unordered_set/allocator/copy.cc (revision 0)
@@ -0,0 +1,69 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+ std::size_t operator()(const T t) const noexcept
+ { return t.i; }
+};
+
+struct equal_to
+{
+ bool operator()(const T& lhs, const T& rhs) const noexcept
+ { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<T, false> alloc_type;
+ typedef std::unordered_set<T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.insert(T());
+ test_type v2(v1);
+ VERIFY(1 == v1.get_allocator().get_personality());
+ VERIFY(0 == v2.get_allocator().get_personality());
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<T, true> alloc_type;
+ typedef std::unordered_set<T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.insert(T());
+ test_type v2(v1);
+ VERIFY(1 == v1.get_allocator().get_personality());
+ VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}
Index: testsuite/23_containers/unordered_set/allocator/move_assign.cc
===================================================================
--- testsuite/23_containers/unordered_set/allocator/move_assign.cc (revision 0)
+++ testsuite/23_containers/unordered_set/allocator/move_assign.cc (revision 0)
@@ -0,0 +1,84 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+#include <testsuite_counter_type.h>
+
+using __gnu_test::propagating_allocator;
+using __gnu_test::counter_type;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<counter_type, false> alloc_type;
+ typedef __gnu_test::counter_type_hasher hash;
+ typedef std::unordered_set<counter_type, hash,
+ std::equal_to<counter_type>,
+ alloc_type> test_type;
+
+ test_type v1(alloc_type(1));
+ v1.emplace(0);
+
+ test_type v2(alloc_type(2));
+ v2.emplace(1);
+
+ counter_type::reset();
+
+ v2 = std::move(v1);
+
+ VERIFY( 1 == v1.get_allocator().get_personality() );
+ VERIFY( 2 == v2.get_allocator().get_personality() );
+
+ VERIFY( counter_type::move_assign_count == 1 );
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<counter_type, true> alloc_type;
+ typedef __gnu_test::counter_type_hasher hash;
+ typedef std::unordered_set<counter_type, hash,
+ std::equal_to<counter_type>,
+ alloc_type> test_type;
+
+ test_type v1(alloc_type(1));
+ v1.emplace(0);
+
+ test_type v2(alloc_type(2));
+ v2.emplace(0);
+
+ counter_type::reset();
+
+ v2 = std::move(v1);
+
+ VERIFY(0 == v1.get_allocator().get_personality());
+ VERIFY(1 == v2.get_allocator().get_personality());
+
+ VERIFY( counter_type::move_assign_count == 0 );
+ VERIFY( counter_type::destructor_count == 1 );
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}
Index: testsuite/23_containers/unordered_set/allocator/copy_assign.cc
===================================================================
--- testsuite/23_containers/unordered_set/allocator/copy_assign.cc (revision 0)
+++ testsuite/23_containers/unordered_set/allocator/copy_assign.cc (revision 0)
@@ -0,0 +1,73 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+ std::size_t operator()(const T t) const noexcept
+ { return t.i; }
+};
+
+struct equal_to
+{
+ bool operator()(const T& lhs, const T& rhs) const noexcept
+ { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<T, false> alloc_type;
+ typedef std::unordered_set<T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.insert(T());
+ test_type v2(alloc_type(2));
+ v2.insert(T());
+ v2 = v1;
+ VERIFY(1 == v1.get_allocator().get_personality());
+ VERIFY(2 == v2.get_allocator().get_personality());
+}
+
+void test02()
+{
+ bool test __attribute__((unused)) = true;
+ typedef propagating_allocator<T, true> alloc_type;
+ typedef std::unordered_set<T, hash, equal_to, alloc_type> test_type;
+ test_type v1(alloc_type(1));
+ v1.insert(T());
+ test_type v2(alloc_type(2));
+ v2.insert(T());
+ v2 = v1;
+ VERIFY(1 == v1.get_allocator().get_personality());
+ VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}
Index: testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc
===================================================================
--- testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc (revision 197307)
+++ testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc (working copy)
@@ -19,7 +19,7 @@
// with this library; see the file COPYING3. If not see
// <http://www.gnu.org/licenses/>.
-// { dg-error "default constructible" "" { target *-*-* } 268 }
+// { dg-error "default constructible" "" { target *-*-* } 273 }
#include <unordered_set>
Index: testsuite/23_containers/unordered_set/instantiation_neg.cc
===================================================================
--- testsuite/23_containers/unordered_set/instantiation_neg.cc (revision 197307)
+++ testsuite/23_containers/unordered_set/instantiation_neg.cc (working copy)
@@ -19,7 +19,7 @@
// with this library; see the file COPYING3. If not see
// <http://www.gnu.org/licenses/>.
-// { dg-error "with noexcept" "" { target *-*-* } 252 }
+// { dg-error "with noexcept" "" { target *-*-* } 257 }
#include <unordered_set>