===================================================================
@@ -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;
===================================================================
@@ -156,6 +156,33 @@
};
/**
+ * struct _Hash_node_value_base
+ *
+ * Node type with the value to store.
+ */
+ template<typename _Value>
+ struct _Hash_node_value_base : _Hash_node_base
+ {
+ __gnu_cxx::__aligned_buffer<_Value> _M_storage;
+
+ _Value*
+ _M_valptr() noexcept
+ { return _M_storage._M_ptr(); }
+
+ const _Value*
+ _M_valptr() const noexcept
+ { return _M_storage._M_ptr(); }
+
+ _Value&
+ _M_v() noexcept
+ { return *_M_valptr(); }
+
+ const _Value&
+ _M_v() const noexcept
+ { return *_M_valptr(); }
+ };
+
+ /**
* Primary template struct _Hash_node.
*/
template<typename _Value, bool _Cache_hash_code>
@@ -164,38 +191,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 +271,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 +323,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++()
@@ -341,7 +357,8 @@
typedef std::size_t result_type;
result_type
- operator()(first_argument_type __num, second_argument_type __den) const
+ operator()(first_argument_type __num,
+ second_argument_type __den) const noexcept
{ return __num % __den; }
};
@@ -387,6 +404,10 @@
{ return _M_next_resize; }
void
+ _M_reset() noexcept
+ { _M_next_resize = 0; }
+
+ void
_M_reset(_State __state)
{ _M_next_resize = __state; }
@@ -496,7 +517,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 +543,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 +563,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 +583,7 @@
if (!__p)
__throw_out_of_range(__N("_Map_base::at"));
- return (__p->_M_v).second;
+ return __p->_M_v().second;
}
/**
@@ -939,7 +960,8 @@
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); }
+ noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>(), (std::size_t)0)) )
+ { return _M_ranged_hash()(_M_extract()(__p->_M_v()), __n); }
void
_M_store_code(__node_type*, __hash_code) const
@@ -1023,9 +1045,10 @@
{ return _M_h2()(__c, __n); }
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); }
+ _M_bucket_index(const __node_type* __p, std::size_t __n) const
+ noexcept( noexcept(declval<const _H1&>()(declval<const _Key&>()))
+ && noexcept(declval<const _H2&>()((__hash_code)0, (std::size_t)0)) )
+ { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __n); }
void
_M_store_code(__node_type*, __hash_code) const
@@ -1109,6 +1132,8 @@
std::size_t
_M_bucket_index(const __node_type* __p, std::size_t __n) const
+ noexcept( noexcept(declval<const _H2&>()((__hash_code)0,
+ (std::size_t)0)) )
{ return _M_h2()(__p->_M_hash_code, __n); }
void
@@ -1163,7 +1188,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 +1199,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 +1330,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 +1389,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 +1687,120 @@
{ }
};
+ /*
+ * Following are functors recyclicing a pool of nodes and using allocation
+ * once the pool is empty.
+ */
+ /// Version using copy semantic through the copy constructor.
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash,
+ typename _RehashPolicy, typename _Traits>
+ struct _ReuseOrAllocNode
+ {
+ private:
+ using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
+ _Equal, _H1, _H2, _Hash,
+ _RehashPolicy, _Traits>;
+ using __val_alloc_type = typename __hashtable::_Value_alloc_type;
+ using __val_alloc_traits = typename __hashtable::_Value_alloc_traits;
+ using __node_alloc_traits = typename __hashtable::_Node_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;
+ __val_alloc_type __a(_M_h._M_node_allocator());
+ __val_alloc_traits::destroy(__a, __node->_M_valptr());
+ __try
+ {
+ __val_alloc_traits::construct(__a, __node->_M_valptr(),
+ __n->_M_v());
+ }
+ __catch(...)
+ {
+ __node->~__node_type();
+ __node_alloc_traits::deallocate(_M_h._M_node_allocator(),
+ __node, 1);
+ __throw_exception_again;
+ }
+ return __node;
+ }
+ return _M_h._M_allocate_node(__n->_M_v());
+ }
+
+ mutable __node_type* _M_nodes;
+ __hashtable& _M_h;
+ };
+
+ /// Version using move semantic through the move constructor.
+ template<typename _Key, typename _Value, typename _Alloc,
+ typename _ExtractKey, typename _Equal,
+ typename _H1, typename _H2, typename _Hash,
+ typename _RehashPolicy, typename _Traits>
+ struct _MoveReuseOrAllocNode
+ {
+ private:
+ using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
+ _Equal, _H1, _H2, _Hash,
+ _RehashPolicy, _Traits>;
+ using __val_alloc_type = typename __hashtable::_Value_alloc_type;
+ using __val_alloc_traits = typename __hashtable::_Value_alloc_traits;
+ using __node_alloc_traits = typename __hashtable::_Node_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;
+ __val_alloc_type __a(_M_h._M_node_allocator());
+ __val_alloc_traits::destroy(__a, __node->_M_valptr());
+ __try
+ {
+ __val_alloc_traits::construct(__a, __node->_M_valptr(),
+ std::move_if_noexcept(__n->_M_v()));
+ }
+ __catch(...)
+ {
+ __node->~__node_type();
+ __node_alloc_traits::deallocate(_M_h._M_node_allocator(),
+ __node, 1);
+ __throw_exception_again;
+ }
+ return __node;
+ }
+ return _M_h._M_allocate_node(std::move_if_noexcept(__n->_M_v()));
+ }
+
+ mutable __node_type* _M_nodes;
+ __hashtable& _M_h;
+ };
+
//@} hashtable-detail
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace __detail
===================================================================
@@ -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 value_type& reference;
+ typedef const value_type& const_reference;
private:
using __rehash_type = _RehashPolicy;
@@ -236,8 +241,6 @@
_RehashPolicy, _Traits>;
// Metaprogramming for picking apart hash caching.
- using __hash_noexcept = __detail::__is_noexcept_hash<_Key, _H1>;
-
template<typename _Cond>
using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>;
@@ -246,12 +249,13 @@
// Compile-time diagnostics.
- // When hash codes are not cached the hash functor shall not
- // throw because it is used in methods (erase, swap...) that
- // shall not throw.
- static_assert(__if_hash_not_cached<__hash_noexcept>::value,
- "Cache the hash code"
- " or qualify your hash functor with noexcept");
+ // Getting a bucket index from a node shall not throw because it is used
+ // in methods (erase, swap...) that shall not throw.
+ static_assert(noexcept(declval<const _Hashtable&>()
+ ._M_bucket_index((const __node_type*)nullptr,
+ (std::size_t)0)),
+ "Cache the hash code or qualify your functors involved"
+ " in hash code and bucket index computation with noexcept");
// Following two static assertions are necessary to guarantee
// that local_iterator will be default constructible.
@@ -302,6 +306,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 +331,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 +382,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 +395,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() noexcept;
+
public:
// Constructor, destructor, assignment, swap
_Hashtable(size_type __bucket_hint,
@@ -384,10 +424,21 @@
_Hashtable(const _Hashtable&);
- _Hashtable(_Hashtable&&);
+ _Hashtable(_Hashtable&&) noexcept;
+ _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 +471,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 +538,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
@@ -585,7 +635,7 @@
protected:
// Bucket index computation helpers.
size_type
- _M_bucket_index(__node_type* __n) const
+ _M_bucket_index(__node_type* __n) const noexcept
{ return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
size_type
@@ -682,7 +732,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 +775,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 +800,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 +833,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 +847,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 +881,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 +904,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 +923,7 @@
__catch(...)
{
clear();
- _M_deallocate_buckets(_M_buckets, _M_bucket_count);
+ _M_deallocate_buckets();
__throw_exception_again;
}
}
@@ -876,49 +933,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() noexcept
+ {
+ _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,
@@ -927,7 +1201,7 @@
typename _Traits>
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
- _Hashtable(_Hashtable&& __ht)
+ _Hashtable(_Hashtable&& __ht) noexcept
: __hashtable_base(__ht),
__map_base(__ht),
__rehash_base(__ht),
@@ -937,14 +1211,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 +1224,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_v()));
+ });
+ __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 +1298,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 +1348,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 +1368,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 +1388,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 +1429,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 +1446,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 +1465,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 +1482,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 +1601,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 +1644,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 +1676,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 +1716,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 +2065,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 +2157,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;
}
===================================================================
@@ -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.
===================================================================
@@ -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.
===================================================================
@@ -39,9 +39,9 @@
#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 <ext/aligned_buffer.h>
#include <bits/stl_function.h> // equal_to, _Identity, _Select1st
#include <bits/functional_hash.h>
#include <bits/hashtable.h>
===================================================================
@@ -39,9 +39,9 @@
#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 <ext/aligned_buffer.h>
#include <bits/stl_function.h> // equal_to, _Identity, _Select1st
#include <bits/functional_hash.h>
#include <bits/hashtable.h>
===================================================================
@@ -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(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);
}
===================================================================
@@ -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);
}
===================================================================
@@ -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
{
===================================================================
@@ -352,11 +352,11 @@
try
{
for (size_t n = starting_label; n <= m_n; ++n)
- m_alloc.check_allocated(n);
+ m_alloc.check(n);
}
catch (std::logic_error& obj)
{
- // On fail, check_allocated should throw std::logic_error.
+ // On fail, check should throw std::logic_error.
std::cerr << obj.what() << std::endl;
std::cerr << typeid(Cntnr).name() << std::endl;
throw;
===================================================================
@@ -1003,7 +1003,7 @@
delete m_p_c;
try
- { m_alloc.check_allocated(memory_label); }
+ { m_alloc.check(memory_label); }
catch (...)
{
std::cerr << "detected leaks!" << std::endl;
===================================================================
@@ -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;
}
}
===================================================================
@@ -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;
+}
===================================================================
@@ -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;
+}
===================================================================
@@ -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;
+}
===================================================================
@@ -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;
+}
===================================================================
@@ -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;
+}
===================================================================
@@ -0,0 +1,89 @@
+// 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() );
+
+ // No move because key is const.
+ VERIFY( counter_type::move_assign_count == 0 );
+}
+
+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;
+}
===================================================================
@@ -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;
+}
===================================================================
@@ -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;
+}
===================================================================
@@ -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;
+}
===================================================================
@@ -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;
+}
===================================================================
@@ -0,0 +1,89 @@
+// 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() );
+
+ // No move because key is const.
+ VERIFY( counter_type::move_assign_count == 0 );
+}
+
+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;
+}
===================================================================
@@ -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;
+}
===================================================================
@@ -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;
+}
===================================================================
@@ -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;
+}
===================================================================
@@ -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;
+}
===================================================================
@@ -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;
+}
===================================================================
@@ -0,0 +1,86 @@
+// 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_count == 1 );
+ VERIFY( counter_type::destructor_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_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_count == 0 );
+ VERIFY( counter_type::copy_count == 0 );
+ VERIFY( counter_type::destructor_count == 1 );
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 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;
+}
===================================================================
@@ -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 *-*-* } 254 }
#include <unordered_set>
===================================================================
@@ -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;
+}
===================================================================
@@ -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;
+}
===================================================================
@@ -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;
+}
===================================================================
@@ -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;
+}
===================================================================
@@ -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;
+}
===================================================================
@@ -0,0 +1,86 @@
+// 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_count == 1 );
+ VERIFY( counter_type::destructor_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_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_count == 0 );
+ VERIFY( counter_type::copy_count == 0 );
+ VERIFY( counter_type::destructor_count == 1 );
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}
===================================================================
@@ -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 *-*-* } 272 }
#include <unordered_set>
Hi Here is another proposal with: - No attempt to remove const key - No attempt to use assignment operator - noexcept move constructor; I slightly modify a static assertion so that it checks that _M_bucket_index is noexcept qualified which depends on the noexcept qualification of the functors involved in bucket computation 2013-04-21 François Dumont <fdumont@gcc.gnu.org> * include/bits/hashtable_policy.h: Add C++11 allocator support. * include/bits/hashtable.h: Likewise. * include/bits/unordered_set.h: Likewise. * include/bits/unordered_map.h: Likewise. * include/debug/unordered_set: Likewise. * include/debug/unordered_map: Likewise. * include/std/unordered_set: Remove bits/algobase.h include. Replace bits/alloc_traits.h by ext/alloc_traits.h. * include/std/unordered_map: Likewise. * testsuite/util/testsuite_counter_type.h: Add count of destructors. * testsuite/23_containers/unordered_set/ not_default_constructible_hash_neg.cc: Adjust dg-error line number. * testsuite/23_containers/unordered_set/instantiation_neg.cc: Likewise. * testsuite/23_containers/unordered_set/allocator/copy.cc: New. * testsuite/23_containers/unordered_set/allocator/copy_assign.cc: New. * testsuite/23_containers/unordered_set/allocator/minimal.cc: New. * testsuite/23_containers/unordered_set/allocator/move_assign.cc: New. * testsuite/23_containers/unordered_set/allocator/noexcept.cc: New. * testsuite/23_containers/unordered_set/allocator/swap.cc: New. * testsuite/23_containers/unordered_multiset/allocator/copy.cc: New. * testsuite/23_containers/unordered_multiset/allocator/copy_assign.cc: New. * testsuite/23_containers/unordered_multiset/allocator/minimal.cc: New. * testsuite/23_containers/unordered_multiset/allocator/move_assign.cc: New. * testsuite/23_containers/unordered_multiset/allocator/noexcept.cc: New. * testsuite/23_containers/unordered_multiset/allocator/swap.cc: New. * testsuite/23_containers/unordered_map/allocator/copy.cc: New. * testsuite/23_containers/unordered_map/allocator/copy_assign.cc: New. * testsuite/23_containers/unordered_map/allocator/minimal.cc: New. * testsuite/23_containers/unordered_map/allocator/move_assign.cc: New. * testsuite/23_containers/unordered_map/allocator/noexcept.cc: New. * testsuite/23_containers/unordered_map/allocator/swap.cc: New. * testsuite/23_containers/unordered_multimap/allocator/copy.cc: New. * testsuite/23_containers/unordered_multimap/allocator/copy_assign.cc: New. * testsuite/23_containers/unordered_multimap/allocator/minimal.cc: New. * testsuite/23_containers/unordered_multimap/allocator/move_assign.cc: New. * testsuite/23_containers/unordered_multimap/allocator/noexcept.cc: New. * testsuite/23_containers/unordered_multimap/allocator/swap.cc: New. Tested under Linux x86_64. Ok to commit ? François On 04/08/2013 10:24 AM, Jonathan Wakely wrote: > On 6 April 2013 19:53, Jonathan Wakely wrote: >> I'm not very comfortable with the "mutable value type" part which >> accesses the stored value through a pointer to a different type. This >> violates strict aliasing rules and would also give the wrong result if >> users provide an explicit specialization of std::pair<int, Foo> which >> stores pair::second before pair::first, then tries to store that type >> in an unordered_map. When a pair<const int, Foo>* is cast to >> pair<int, Foo>* the user's explicit specialization would not be used >> and the layout would be wrong. Would it be possible to separate the >> C++11 allocator support from the new feature that attempts to reuse >> existing nodes? Or maybe remove the mutable value type stuff so that >> nodes can be reused for unordered sets but not unordered maps? > For a non-assignable value_type we can reuse the node (but not the > value_type) by destroying and constructing a new value_type in place: > > __node_type* > operator()(const __node_type* __n) const > { > if (_M_nodes) > { > __node_type* __node = _M_nodes; > allocator_traits<A>::destroy(a, __node->_M_valptr()); > __try { > allocator_traits<A>::construct(a, __node->_M_valptr(), > *__n->_M_valptr()); > // Construction didn't throw, we can unlink the node. > _M_nodes = _M_nodes->_M_next(); > __node->_M_nxt = nullptr; > return __node; > } __catch (...) { > // TODO deallocate node > __throw_exception_again; > } > } > return _M_h._M_allocate_node(__n->_M_v()); > } > > This can be much less efficient than assignment if the value_type has > its own allocated memory, but I don't see any alternative. Casting > pair<const A,B>& to pair<A,B>& is not an option. > > N.B. the code above >