Teach __hash_table how to handle unordered_map's __hash_value_type.
This patch is fairly large and contains a number of changes. The main change
is teaching '__hash_table' how to handle '__hash_value_type'. Unfortunately
this change is a rampant layering violation, but it's required to make
unordered_map conforming without re-writing all of __hash_table.
After this change 'unordered_map' can delegate to '__hash_table' in almost all cases.
The major changes found in this patch are:
* Teach __hash_table to differentiate between the true container value type
and the node value type by introducing the "__container_value_type" and
"__node_value_type" typedefs. In the case of unordered_map '__container_value_type'
is 'pair<const Key, Value>' and '__node_value_type' is '__hash_value_type'.
* Switch almost all overloads in '__hash_table' previously taking 'value_type'
(AKA '__node_value_type) to take '__container_value_type' instead. Previously
'pair<K, V>' would be implicitly converted to '__hash_value_type<K, V>' because
of the function signature.
* Add '__get_key', '__get_value', '__get_ptr', and '__move' static functions to
'__key_value_types'. These functions allow '__hash_table' to unwrap
'__node_value_type' objects into '__container_value_type' and its sub-parts.
* Pass '__hash_value_type::__value_' to 'a.construct(p, ...)' instead of
'__hash_value_type' itself. The C++14 standard requires that 'a.construct()'
and 'a.destroy()' are only ever instantiated for the containers value type.
* Remove '__hash_value_type's constructors and destructors. We should never
construct an instance of this type.
(TODO this is UB but we already do it in plenty of places).
* Add a generic "try-emplace" function to '__hash_table' called
'__emplace_unique_key_args(Key const&, Args...)'.
The following changes were done as cleanup:
* Introduce the '_LIBCPP_CXX03_LANG' macro to be used in place of
'_LIBCPP_HAS_NO_VARIADICS' or '_LIBCPP_HAS_NO_RVALUE_REFERENCE'.
* Cleanup C++11 only overloads that assume an incomplete C++11 implementation.
For example this patch removes the __construct_node overloads that do
manual pack expansion.
* Forward 'unordered_map::emplace' to '__hash_table' and remove dead code
resulting from the change. This includes almost all
'unordered_map::__construct_node' overloads.
The following changes are planed for future revisions:
* Fix LWG issue #2469 by delegating 'unordered_map::operator[]' to use
'__emplace_unique_key_args'.
* Rewrite 'unordered_map::try_emplace' in terms of '__emplace_unique_key_args'.
* Optimize '__emplace_unique' to call '__emplace_unique_key_args' when possible.
This prevent unneeded allocations when inserting duplicate entries.
The additional follow up work needed after this patch:
* Respect the lifetime rules for '__hash_value_type' by actually constructing it.
* Make '__insert_multi' act similar to '__insert_unique' for objects of type
'T&' and 'T const &&' with 'T = __container_value_type'.
git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@260513 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/__config b/include/__config
index 6926fb3..a62b2be 100644
--- a/include/__config
+++ b/include/__config
@@ -475,8 +475,6 @@
#define _LIBCPP_NO_EXCEPTIONS
#endif
-#define _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-
// constexpr was added to GCC in 4.6.
#if _GNUC_VER < 406
#define _LIBCPP_HAS_NO_CONSTEXPR
@@ -508,6 +506,7 @@
#define _LIBCPP_HAS_NO_VARIADICS
#define _LIBCPP_HAS_NO_RVALUE_REFERENCES
#define _LIBCPP_HAS_NO_STRONG_ENUMS
+#define _LIBCPP_HAS_NO_TEMPLATE_ALIASES
#define _LIBCPP_HAS_NO_NOEXCEPT
#else // __GXX_EXPERIMENTAL_CXX0X__
@@ -531,6 +530,7 @@
#if _GNUC_VER < 406
#define _LIBCPP_HAS_NO_NOEXCEPT
#define _LIBCPP_HAS_NO_NULLPTR
+#define _LIBCPP_HAS_NO_TEMPLATE_ALIASES
#endif
#if _GNUC_VER < 407
@@ -849,7 +849,15 @@
#ifndef _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
#define _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
-#endif
+#endif
+
+#if __cplusplus < 201103L
+#define _LIBCPP_CXX03_LANG
+#else
+#if defined(_LIBCPP_HAS_NO_VARIADIC_TEMPLATES) || defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
+#error Libc++ requires a feature complete C++11 compiler in C++11 or greater.
+#endif
+#endif
#endif // __cplusplus
diff --git a/include/__hash_table b/include/__hash_table
index 5f21de4..c35c6df 100644
--- a/include/__hash_table
+++ b/include/__hash_table
@@ -30,6 +30,29 @@
_LIBCPP_BEGIN_NAMESPACE_STD
+
+#ifndef _LIBCPP_CXX03_LANG
+template <class _Key, class _Tp>
+union __hash_value_type;
+#else
+template <class _Key, class _Tp>
+struct __hash_value_type;
+#endif
+
+#ifndef _LIBCPP_CXX03_LANG
+template <class _Tp>
+struct __is_hash_value_type_imp : false_type {};
+
+template <class _Key, class _Value>
+struct __is_hash_value_type_imp<__hash_value_type<_Key, _Value>> : true_type {};
+
+template <class ..._Args>
+struct __is_hash_value_type : false_type {};
+
+template <class _One>
+struct __is_hash_value_type<_One> : __is_hash_value_type_imp<typename __uncvref<_One>::type> {};
+#endif
+
_LIBCPP_FUNC_VIS
size_t __next_prime(size_t __n);
@@ -86,14 +109,6 @@
template <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator;
template <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator;
-#if __cplusplus >= 201103L
-template <class _Key, class _Tp>
-union __hash_value_type;
-#else
-template <class _Key, class _Tp>
-struct __hash_value_type;
-#endif
-
template <class _Tp>
struct __key_value_types {
static_assert(!is_reference<_Tp>::value && !is_const<_Tp>::value, "");
@@ -101,6 +116,25 @@
typedef _Tp __node_value_type;
typedef _Tp __container_value_type;
static const bool __is_map = false;
+
+ _LIBCPP_INLINE_VISIBILITY
+ static key_type const& __get_key(_Tp const& __v) {
+ return __v;
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ static __container_value_type const& __get_value(__node_value_type const& __v) {
+ return __v;
+ }
+ _LIBCPP_INLINE_VISIBILITY
+ static __container_value_type* __get_ptr(__node_value_type& __n) {
+ return _VSTD::addressof(__n);
+ }
+#ifndef _LIBCPP_CXX03_LANG
+ _LIBCPP_INLINE_VISIBILITY
+ static __container_value_type&& __move(__node_value_type& __v) {
+ return _VSTD::move(__v);
+ }
+#endif
};
template <class _Key, class _Tp>
@@ -109,8 +143,42 @@
typedef _Tp mapped_type;
typedef __hash_value_type<_Key, _Tp> __node_value_type;
typedef pair<const _Key, _Tp> __container_value_type;
+ typedef pair<_Key, _Tp> __nc_value_type;
typedef __container_value_type __map_value_type;
static const bool __is_map = true;
+
+ _LIBCPP_INLINE_VISIBILITY
+ static key_type const& __get_key(__container_value_type const& __v) {
+ return __v.first;
+ }
+
+ template <class _Up>
+ _LIBCPP_INLINE_VISIBILITY
+ static typename enable_if<__is_same_uncvref<_Up, __node_value_type>::value,
+ __container_value_type const&>::type
+ __get_value(_Up& __t) {
+ return __t.__cc;
+ }
+
+ template <class _Up>
+ _LIBCPP_INLINE_VISIBILITY
+ static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value,
+ __container_value_type const&>::type
+ __get_value(_Up& __t) {
+ return __t;
+ }
+
+ _LIBCPP_INLINE_VISIBILITY
+ static __container_value_type* __get_ptr(__node_value_type& __n) {
+ return _VSTD::addressof(__n.__cc);
+ }
+#ifndef _LIBCPP_CXX03_LANG
+ _LIBCPP_INLINE_VISIBILITY
+ static __nc_value_type&& __move(__node_value_type& __v) {
+ return _VSTD::move(__v.__nc);
+ }
+#endif
+
};
template <class _Tp, class _AllocPtr, class _KVTypes = __key_value_types<_Tp>,
@@ -787,6 +855,7 @@
public:
typedef typename __alloc_traits::pointer pointer;
private:
+ typedef __hash_node_types<pointer> _NodeTypes;
allocator_type& __na_;
@@ -806,7 +875,7 @@
void operator()(pointer __p) _NOEXCEPT
{
if (__value_constructed)
- __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_));
+ __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_));
if (__p)
__alloc_traits::deallocate(__na_, __p, 1);
}
@@ -829,6 +898,9 @@
__make_hash_node_types<value_type, typename __alloc_traits::void_pointer>::type
_NodeTypes;
public:
+
+ typedef typename _NodeTypes::__node_value_type __node_value_type;
+ typedef typename _NodeTypes::__container_value_type __container_value_type;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef typename __alloc_traits::pointer pointer;
@@ -925,7 +997,7 @@
explicit __hash_table(const allocator_type& __a);
__hash_table(const __hash_table& __u);
__hash_table(const __hash_table& __u, const allocator_type& __a);
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#ifndef _LIBCPP_CXX03_LANG
__hash_table(__hash_table&& __u)
_NOEXCEPT_(
is_nothrow_move_constructible<__bucket_list>::value &&
@@ -934,11 +1006,11 @@
is_nothrow_move_constructible<hasher>::value &&
is_nothrow_move_constructible<key_equal>::value);
__hash_table(__hash_table&& __u, const allocator_type& __a);
-#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#endif // _LIBCPP_CXX03_LANG
~__hash_table();
__hash_table& operator=(const __hash_table& __u);
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#ifndef _LIBCPP_CXX03_LANG
_LIBCPP_INLINE_VISIBILITY
__hash_table& operator=(__hash_table&& __u)
_NOEXCEPT_(
@@ -964,41 +1036,56 @@
iterator __node_insert_multi(const_iterator __p,
__node_pointer __nd);
-#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
- template <class... _Args>
- pair<iterator, bool> __emplace_unique(_Args&&... __args);
- template <class... _Args>
- iterator __emplace_multi(_Args&&... __args);
- template <class... _Args>
- iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
-#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
+#ifndef _LIBCPP_CXX03_LANG
+ template <class _Key, class ..._Args>
+ pair<iterator, bool> __emplace_unique_key_args(_Key const& __k, _Args&&... __args);
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
- template <class _ValueTp>
+ template <class... _Args>
+ pair<iterator, bool> __emplace_unique(_Args&&... __args);
+ template <class... _Args>
+ iterator __emplace_multi(_Args&&... __args);
+ template <class... _Args>
+ iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
+
+
_LIBCPP_INLINE_VISIBILITY
- pair<iterator, bool> __insert_unique_value(_ValueTp&& __x);
-#else
+ pair<iterator, bool>
+ __insert_unique(__container_value_type&& __x) {
+ return __emplace_unique_key_args(_NodeTypes::__get_key(__x), _VSTD::move(__x));
+ }
+
+ template <class _Pp, class = typename enable_if<
+ !__is_same_uncvref<_Pp, __container_value_type>::value
+ >::type>
_LIBCPP_INLINE_VISIBILITY
- pair<iterator, bool> __insert_unique_value(const value_type& __x);
+ pair<iterator, bool> __insert_unique(_Pp&& __x) {
+ return __emplace_unique(_VSTD::forward<_Pp>(__x));
+ }
+
+ template <class _Pp>
+ _LIBCPP_INLINE_VISIBILITY
+ iterator __insert_multi(_Pp&& __x) {
+ return __emplace_multi(_VSTD::forward<_Pp>(__x));
+ }
+
+ template <class _Pp>
+ _LIBCPP_INLINE_VISIBILITY
+ iterator __insert_multi(const_iterator __p, _Pp&& __x) {
+ return __emplace_hint_multi(__p, _VSTD::forward<_Pp>(__x));
+ }
+
+#else // !defined(_LIBCPP_CXX03_LANG)
+ template <class _Key, class _Args>
+ pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args& __args);
+
+ iterator __insert_multi(const __container_value_type& __x);
+ iterator __insert_multi(const_iterator __p, const __container_value_type& __x);
#endif
- pair<iterator, bool> __insert_unique(const value_type& __x);
-
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
- pair<iterator, bool> __insert_unique(value_type&& __x);
- template <class _Pp>
- pair<iterator, bool> __insert_unique(_Pp&& __x);
-#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
-
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
- template <class _Pp>
- iterator __insert_multi(_Pp&& __x);
- template <class _Pp>
- iterator __insert_multi(const_iterator __p, _Pp&& __x);
-#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
- iterator __insert_multi(const value_type& __x);
- iterator __insert_multi(const_iterator __p, const value_type& __x);
-#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+ _LIBCPP_INLINE_VISIBILITY
+ pair<iterator, bool> __insert_unique(const __container_value_type& __x) {
+ return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x);
+ }
void clear() _NOEXCEPT;
void rehash(size_type __n);
@@ -1158,17 +1245,17 @@
private:
void __rehash(size_type __n);
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
-#ifndef _LIBCPP_HAS_NO_VARIADICS
+#ifndef _LIBCPP_CXX03_LANG
template <class ..._Args>
- __node_holder __construct_node(_Args&& ...__args);
-#endif // _LIBCPP_HAS_NO_VARIADICS
- template <class _ValueTp>
- __node_holder __construct_node_hash(_ValueTp&& __v, size_t __hash);
-#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
- __node_holder __construct_node(const value_type& __v);
+ __node_holder __construct_node(_Args&& ...__args);
+
+ template <class _First, class ..._Rest>
+ __node_holder __construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest);
+#else // _LIBCPP_CXX03_LANG
+ __node_holder __construct_node(const __container_value_type& __v);
+ __node_holder __construct_node_hash(size_t __hash, const __container_value_type& __v);
#endif
- __node_holder __construct_node_hash(const value_type& __v, size_t __hash);
+
_LIBCPP_INLINE_VISIBILITY
void __copy_assign_alloc(const __hash_table& __u)
@@ -1178,6 +1265,7 @@
_LIBCPP_INLINE_VISIBILITY
void __copy_assign_alloc(const __hash_table&, false_type) {}
+#ifndef _LIBCPP_CXX03_LANG
void __move_assign(__hash_table& __u, false_type);
void __move_assign(__hash_table& __u, true_type)
_NOEXCEPT_(
@@ -1204,6 +1292,7 @@
}
_LIBCPP_INLINE_VISIBILITY
void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {}
+#endif // _LIBCPP_CXX03_LANG
void __deallocate(__node_pointer __np) _NOEXCEPT;
__node_pointer __detach() _NOEXCEPT;
@@ -1280,7 +1369,7 @@
{
}
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#ifndef _LIBCPP_CXX03_LANG
template <class _Tp, class _Hash, class _Equal, class _Alloc>
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u)
@@ -1329,7 +1418,7 @@
}
}
-#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#endif // _LIBCPP_CXX03_LANG
template <class _Tp, class _Hash, class _Equal, class _Alloc>
__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table()
@@ -1394,7 +1483,7 @@
}
__get_db()->unlock();
#endif
- __node_traits::destroy(__na, _VSTD::addressof(__np->__value_));
+ __node_traits::destroy(__na, _NodeTypes::__get_ptr(__np->__value_));
__node_traits::deallocate(__na, __np, 1);
__np = __next;
}
@@ -1413,7 +1502,7 @@
return __cache;
}
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#ifndef _LIBCPP_CXX03_LANG
template <class _Tp, class _Hash, class _Equal, class _Alloc>
void
@@ -1486,8 +1575,7 @@
const_iterator __i = __u.begin();
while (__u.size() != 0)
{
- __node_holder __h =
- __construct_node(_VSTD::move(__u.remove(__i++)->__value_));
+ __node_holder __h = __construct_node(_NodeTypes::__move(__u.remove(__i++)->__value_));
__node_insert_multi(__h.get());
__h.release();
}
@@ -1509,7 +1597,7 @@
return *this;
}
-#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#endif // _LIBCPP_CXX03_LANG
template <class _Tp, class _Hash, class _Equal, class _Alloc>
template <class _InputIterator>
@@ -1517,6 +1605,11 @@
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first,
_InputIterator __last)
{
+ typedef iterator_traits<_InputIterator> _ITraits;
+ typedef typename _ITraits::value_type _ItValueType;
+ static_assert((is_same<_ItValueType, __container_value_type>::value),
+ "__assign_unique may only be called with the containers value type");
+
if (bucket_count() != 0)
{
__node_pointer __cache = __detach();
@@ -1551,6 +1644,12 @@
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first,
_InputIterator __last)
{
+ typedef iterator_traits<_InputIterator> _ITraits;
+ typedef typename _ITraits::value_type _ItValueType;
+ static_assert((is_same<_ItValueType, __container_value_type>::value ||
+ is_same<_ItValueType, __node_value_type>::value),
+ "__assign_multi may only be called with the containers value type"
+ " or the nodes value type");
if (bucket_count() != 0)
{
__node_pointer __cache = __detach();
@@ -1576,7 +1675,7 @@
__deallocate(__cache);
}
for (; __first != __last; ++__first)
- __insert_multi(*__first);
+ __insert_multi(_NodeTypes::__get_value(*__first));
}
template <class _Tp, class _Hash, class _Equal, class _Alloc>
@@ -1802,31 +1901,24 @@
return __node_insert_multi(__cp);
}
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(const value_type& __x)
-{
- return __insert_unique_value(__x);
-}
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#ifndef _LIBCPP_CXX03_LANG
template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class _ValueTp>
+template <class _Key, class ..._Args>
_LIBCPP_INLINE_VISIBILITY
pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique_value(_ValueTp&& __x)
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args)
#else
template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Key, class _Args>
_LIBCPP_INLINE_VISIBILITY
pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique_value(const value_type& __x)
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args& __args)
#endif
{
-#if defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
- typedef const value_type& _ValueTp;
-#endif
- size_t __hash = hash_function()(__x);
+
+ size_t __hash = hash_function()(__k);
size_type __bc = bucket_count();
bool __inserted = false;
__node_pointer __nd;
@@ -1841,13 +1933,17 @@
__constrain_hash(__nd->__hash_, __bc) == __chash;
__nd = __nd->__next_)
{
- if (key_eq()(__nd->__value_, __x))
+ if (key_eq()(__nd->__value_, __k))
goto __done;
}
}
}
{
- __node_holder __h = __construct_node_hash(_VSTD::forward<_ValueTp>(__x), __hash);
+#ifndef _LIBCPP_CXX03_LANG
+ __node_holder __h = __construct_node_hash(__hash, _VSTD::forward<_Args>(__args)...);
+#else
+ __node_holder __h = __construct_node_hash(__hash, __args);
+#endif
if (size()+1 > __bc * max_load_factor() || __bc == 0)
{
rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
@@ -1885,8 +1981,7 @@
#endif
}
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
-#ifndef _LIBCPP_HAS_NO_VARIADICS
+#ifndef _LIBCPP_CXX03_LANG
template <class _Tp, class _Hash, class _Equal, class _Alloc>
template <class... _Args>
@@ -1928,64 +2023,11 @@
return __r;
}
-#endif // _LIBCPP_HAS_NO_VARIADICS
-
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(value_type&& __x)
-{
- return __insert_unique_value(_VSTD::move(__x));
-}
-
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class _Pp>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(_Pp&& __x)
-{
- __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x));
- pair<iterator, bool> __r = __node_insert_unique(__h.get());
- if (__r.second)
- __h.release();
- return __r;
-}
-
-#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
-
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
-
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class _Pp>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(_Pp&& __x)
-{
- __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x));
- iterator __r = __node_insert_multi(__h.get());
- __h.release();
- return __r;
-}
-
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class _Pp>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p,
- _Pp&& __x)
-{
-#if _LIBCPP_DEBUG_LEVEL >= 2
- _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
- "unordered container::insert(const_iterator, rvalue) called with an iterator not"
- " referring to this unordered container");
-#endif
- __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x));
- iterator __r = __node_insert_multi(__p, __h.get());
- __h.release();
- return __r;
-}
-
-#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#else // _LIBCPP_CXX03_LANG
template <class _Tp, class _Hash, class _Equal, class _Alloc>
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const value_type& __x)
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const __container_value_type& __x)
{
__node_holder __h = __construct_node(__x);
iterator __r = __node_insert_multi(__h.get());
@@ -1996,7 +2038,7 @@
template <class _Tp, class _Hash, class _Equal, class _Alloc>
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p,
- const value_type& __x)
+ const __container_value_type& __x)
{
#if _LIBCPP_DEBUG_LEVEL >= 2
_LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
@@ -2009,7 +2051,7 @@
return __r;
}
-#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#endif // _LIBCPP_CXX03_LANG
template <class _Tp, class _Hash, class _Equal, class _Alloc>
void
@@ -2148,71 +2190,74 @@
return end();
}
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
-#ifndef _LIBCPP_HAS_NO_VARIADICS
+#ifndef _LIBCPP_CXX03_LANG
template <class _Tp, class _Hash, class _Equal, class _Alloc>
template <class ..._Args>
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args)
{
+ static_assert(!__is_hash_value_type<_Args...>::value,
+ "Construct cannot be called with a hash value type");
__node_allocator& __na = __node_alloc();
__node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...);
+ __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), _VSTD::forward<_Args>(__args)...);
__h.get_deleter().__value_constructed = true;
__h->__hash_ = hash_function()(__h->__value_);
__h->__next_ = nullptr;
return __h;
}
-#endif // _LIBCPP_HAS_NO_VARIADICS
-
template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class _ValueTp>
+template <class _First, class ..._Rest>
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(_ValueTp&& __v,
- size_t __hash)
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(
+ size_t __hash, _First&& __f, _Rest&& ...__rest)
{
+ static_assert(!__is_hash_value_type<_First, _Rest...>::value,
+ "Construct cannot be called with a hash value type");
__node_allocator& __na = __node_alloc();
__node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_ValueTp>(__v));
+ __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_),
+ _VSTD::forward<_First>(__f),
+ _VSTD::forward<_Rest>(__rest)...);
__h.get_deleter().__value_constructed = true;
__h->__hash_ = __hash;
__h->__next_ = nullptr;
return __h;
}
-#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#else // _LIBCPP_CXX03_LANG
template <class _Tp, class _Hash, class _Equal, class _Alloc>
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v)
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const __container_value_type& __v)
{
__node_allocator& __na = __node_alloc();
__node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v);
+ __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), __v);
__h.get_deleter().__value_constructed = true;
__h->__hash_ = hash_function()(__h->__value_);
__h->__next_ = nullptr;
return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03
}
-#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
-
template <class _Tp, class _Hash, class _Equal, class _Alloc>
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(const value_type& __v,
- size_t __hash)
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(size_t __hash,
+ const __container_value_type& __v)
{
__node_allocator& __na = __node_alloc();
__node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v);
+ __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), __v);
__h.get_deleter().__value_constructed = true;
__h->__hash_ = __hash;
__h->__next_ = nullptr;
return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03
}
+#endif // _LIBCPP_CXX03_LANG
+
template <class _Tp, class _Hash, class _Equal, class _Alloc>
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p)
diff --git a/include/type_traits b/include/type_traits
index 13af4ae..b0675e1 100644
--- a/include/type_traits
+++ b/include/type_traits
@@ -1091,6 +1091,12 @@
typedef typename remove_cv<typename remove_reference<_Tp>::type>::type type;
};
+// __is_same_uncvref
+
+template <class _Tp, class _Up>
+struct __is_same_uncvref : is_same<typename __uncvref<_Tp>::type,
+ typename __uncvref<_Up>::type> {};
+
struct __any
{
__any(...);
diff --git a/include/unordered_map b/include/unordered_map
index 89407b0..7e84f74 100644
--- a/include/unordered_map
+++ b/include/unordered_map
@@ -583,8 +583,7 @@
}
};
-#if __cplusplus >= 201103L
-
+#ifndef _LIBCPP_CXX03_LANG
template <class _Key, class _Tp>
union __hash_value_type
{
@@ -596,19 +595,6 @@
value_type __cc;
__nc_value_type __nc;
- template <class ..._Args>
- _LIBCPP_INLINE_VISIBILITY
- __hash_value_type(_Args&& ...__args)
- : __cc(std::forward<_Args>(__args)...) {}
-
- _LIBCPP_INLINE_VISIBILITY
- __hash_value_type(const __hash_value_type& __v)
- : __cc(__v.__cc) {}
-
- _LIBCPP_INLINE_VISIBILITY
- __hash_value_type(__hash_value_type&& __v)
- : __nc(_VSTD::move(__v.__nc)) {}
-
_LIBCPP_INLINE_VISIBILITY
__hash_value_type& operator=(const __hash_value_type& __v)
{__nc = __v.__cc; return *this;}
@@ -617,8 +603,23 @@
__hash_value_type& operator=(__hash_value_type&& __v)
{__nc = _VSTD::move(__v.__nc); return *this;}
+ template <class _ValueTp,
+ class = typename enable_if<
+ __is_same_uncvref<_ValueTp, value_type>::value
+ >::type
+ >
_LIBCPP_INLINE_VISIBILITY
- ~__hash_value_type() {__cc.~value_type();}
+ __hash_value_type& operator=(_ValueTp&& __v) {
+ __nc = _VSTD::forward<_ValueTp>(__v); return *this;
+ }
+
+private:
+ __hash_value_type(const __hash_value_type& __v) = delete;
+ __hash_value_type(__hash_value_type&& __v) = delete;
+ template <class ..._Args>
+ explicit __hash_value_type(_Args&& ...__args) = delete;
+
+ ~__hash_value_type() = delete;
};
#else
@@ -632,18 +633,8 @@
value_type __cc;
- _LIBCPP_INLINE_VISIBILITY
- __hash_value_type() {}
-
- template <class _A0>
- _LIBCPP_INLINE_VISIBILITY
- __hash_value_type(const _A0& __a0)
- : __cc(__a0) {}
-
- template <class _A0, class _A1>
- _LIBCPP_INLINE_VISIBILITY
- __hash_value_type(const _A0& __a0, const _A1& __a1)
- : __cc(__a0, __a1) {}
+private:
+ ~__hash_value_type();
};
#endif
@@ -780,6 +771,7 @@
__table __table_;
+ typedef typename __table::_NodeTypes _NodeTypes;
typedef typename __table::__node_pointer __node_pointer;
typedef typename __table::__node_const_pointer __node_const_pointer;
typedef typename __table::__node_traits __node_traits;
@@ -788,6 +780,9 @@
typedef __hash_map_node_destructor<__node_allocator> _Dp;
typedef unique_ptr<__node, _Dp> __node_holder;
typedef allocator_traits<allocator_type> __alloc_traits;
+
+ static_assert((is_same<typename __table::__container_value_type, value_type>::value), "");
+ static_assert((is_same<typename __table::__node_value_type, __value_type>::value), "");
public:
typedef typename __alloc_traits::pointer pointer;
typedef typename __alloc_traits::const_pointer const_pointer;
@@ -913,28 +908,26 @@
_LIBCPP_INLINE_VISIBILITY
const_iterator cend() const _NOEXCEPT {return __table_.end();}
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
-#ifndef _LIBCPP_HAS_NO_VARIADICS
+#ifndef _LIBCPP_CXX03_LANG
+ template <class... _Args>
+ _LIBCPP_INLINE_VISIBILITY
+ pair<iterator, bool> emplace(_Args&&... __args) {
+ return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
+ }
template <class... _Args>
- pair<iterator, bool> emplace(_Args&&... __args);
-
- template <class... _Args>
- _LIBCPP_INLINE_VISIBILITY
+ _LIBCPP_INLINE_VISIBILITY
+ iterator emplace_hint(const_iterator __p, _Args&&... __args) {
#if _LIBCPP_DEBUG_LEVEL >= 2
- iterator emplace_hint(const_iterator __p, _Args&&... __args)
- {
- _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
- "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not"
- " referring to this unordered_map");
- return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
- }
-#else
- iterator emplace_hint(const_iterator, _Args&&... __args)
- {return emplace(_VSTD::forward<_Args>(__args)...).first;}
+ _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
+ "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not"
+ " referring to this unordered_map");
#endif
-#endif // _LIBCPP_HAS_NO_VARIADICS
-#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+ return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
+ }
+
+#endif // _LIBCPP_CXX03_LANG
+
_LIBCPP_INLINE_VISIBILITY
pair<iterator, bool> insert(const value_type& __x)
{return __table_.__insert_unique(__x);}
@@ -1191,17 +1184,9 @@
#endif // _LIBCPP_DEBUG_LEVEL >= 2
private:
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
- __node_holder __construct_node();
- template <class _A0>
- __node_holder
- __construct_node(_A0&& __a0);
+#ifndef _LIBCPP_CXX03_LANG
__node_holder __construct_node_with_key(key_type&& __k);
-#ifndef _LIBCPP_HAS_NO_VARIADICS
- template <class _A0, class _A1, class ..._Args>
- __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
-#endif // _LIBCPP_HAS_NO_VARIADICS
-#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#endif // _LIBCPP_CXX03_LANG
__node_holder __construct_node_with_key(const key_type& __k);
};
@@ -1328,10 +1313,10 @@
if (__a != __u.get_allocator())
{
iterator __i = __u.begin();
- while (__u.size() != 0)
- __table_.__insert_unique(
- _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
- );
+ while (__u.size() != 0) {
+ __table_.__emplace_unique(_VSTD::move(
+ __u.__table_.remove((__i++).__i_)->__value_.__nc));
+ }
}
#if _LIBCPP_DEBUG_LEVEL >= 2
else
@@ -1409,33 +1394,7 @@
#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
-
-template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
-typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
-unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
-{
- __node_allocator& __na = __table_.__node_alloc();
- __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
- __h.get_deleter().__first_constructed = true;
- __h.get_deleter().__second_constructed = true;
- return __h;
-}
-
-template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
-template <class _A0>
-typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
-unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
-{
- __node_allocator& __na = __table_.__node_alloc();
- __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
- _VSTD::forward<_A0>(__a0));
- __h.get_deleter().__first_constructed = true;
- __h.get_deleter().__second_constructed = true;
- return __h;
-}
+#ifndef _LIBCPP_CXX03_LANG
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
@@ -1450,39 +1409,7 @@
return __h;
}
-#ifndef _LIBCPP_HAS_NO_VARIADICS
-
-template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
-template <class _A0, class _A1, class ..._Args>
-typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
-unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0,
- _A1&& __a1,
- _Args&&... __args)
-{
- __node_allocator& __na = __table_.__node_alloc();
- __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
- _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
- _VSTD::forward<_Args>(__args)...);
- __h.get_deleter().__first_constructed = true;
- __h.get_deleter().__second_constructed = true;
- return __h;
-}
-
-template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
-template <class... _Args>
-pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool>
-unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
-{
- __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
- pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
- if (__r.second)
- __h.release();
- return __r;
-}
-
-#endif // _LIBCPP_HAS_NO_VARIADICS
-#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#endif
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
@@ -1630,6 +1557,7 @@
__table __table_;
+ typedef typename __table::_NodeTypes _NodeTypes;
typedef typename __table::__node_traits __node_traits;
typedef typename __table::__node_allocator __node_allocator;
typedef typename __table::__node __node;
@@ -1765,16 +1693,18 @@
_LIBCPP_INLINE_VISIBILITY
const_iterator cend() const _NOEXCEPT {return __table_.end();}
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
-#ifndef _LIBCPP_HAS_NO_VARIADICS
+#ifndef _LIBCPP_CXX03_LANG
+ template <class... _Args>
+ iterator emplace(_Args&&... __args) {
+ return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
+ }
template <class... _Args>
- iterator emplace(_Args&&... __args);
+ iterator emplace_hint(const_iterator __p, _Args&&... __args) {
+ return __table_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
+ }
+#endif // _LIBCPP_CXX03_LANG
- template <class... _Args>
- iterator emplace_hint(const_iterator __p, _Args&&... __args);
-#endif // _LIBCPP_HAS_NO_VARIADICS
-#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
_LIBCPP_INLINE_VISIBILITY
iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
@@ -1888,17 +1818,7 @@
#endif // _LIBCPP_DEBUG_LEVEL >= 2
-private:
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
- __node_holder __construct_node();
- template <class _A0>
- __node_holder
- __construct_node(_A0&& __a0);
-#ifndef _LIBCPP_HAS_NO_VARIADICS
- template <class _A0, class _A1, class ..._Args>
- __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
-#endif // _LIBCPP_HAS_NO_VARIADICS
-#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+
};
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
@@ -2027,7 +1947,7 @@
while (__u.size() != 0)
{
__table_.__insert_multi(
- _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
+ _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_.__nc)
);
}
}
@@ -2107,77 +2027,7 @@
#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
-template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
-typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
-unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
-{
- __node_allocator& __na = __table_.__node_alloc();
- __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
- __h.get_deleter().__first_constructed = true;
- __h.get_deleter().__second_constructed = true;
- return __h;
-}
-
-template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
-template <class _A0>
-typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
-unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
-{
- __node_allocator& __na = __table_.__node_alloc();
- __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
- _VSTD::forward<_A0>(__a0));
- __h.get_deleter().__first_constructed = true;
- __h.get_deleter().__second_constructed = true;
- return __h;
-}
-
-#ifndef _LIBCPP_HAS_NO_VARIADICS
-
-template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
-template <class _A0, class _A1, class ..._Args>
-typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
-unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(
- _A0&& __a0, _A1&& __a1, _Args&&... __args)
-{
- __node_allocator& __na = __table_.__node_alloc();
- __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
- _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
- _VSTD::forward<_Args>(__args)...);
- __h.get_deleter().__first_constructed = true;
- __h.get_deleter().__second_constructed = true;
- return __h;
-}
-
-template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
-template <class... _Args>
-typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
-unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
-{
- __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
- iterator __r = __table_.__node_insert_multi(__h.get());
- __h.release();
- return __r;
-}
-
-template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
-template <class... _Args>
-typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
-unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint(
- const_iterator __p, _Args&&... __args)
-{
- __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
- iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get());
- __h.release();
- return __r;
-}
-
-#endif // _LIBCPP_HAS_NO_VARIADICS
-#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
template <class _InputIterator>
diff --git a/test/std/containers/unord/unord.map/unord.map.modifiers/insert_allocator_requirements.pass.cpp b/test/std/containers/unord/unord.map/unord.map.modifiers/insert_allocator_requirements.pass.cpp
new file mode 100644
index 0000000..e889ce3
--- /dev/null
+++ b/test/std/containers/unord/unord.map/unord.map.modifiers/insert_allocator_requirements.pass.cpp
@@ -0,0 +1,143 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <unordered_map>
+
+// class unordered_map
+
+// insert(...);
+
+// UNSUPPORTED: c++98, c++03
+
+
+#include <unordered_map>
+#include <iostream>
+#include <cassert>
+
+#include "test_macros.h"
+#include "count_new.hpp"
+#include "container_test_types.h"
+
+#if TEST_STD_VER >= 11
+template <class Arg>
+void PrintInfo(int line, Arg&& arg)
+#else
+template <class Arg>
+void PrintInfo(int line, Arg arg)
+#endif
+{
+ std::cout << "In " << __FILE__ << ":" << line << ":\n " << arg << "\n" << std::endl;
+}
+#define PRINT(...) PrintInfo(__LINE__, __VA_ARGS__)
+
+template <class Container>
+void testContainerInsert()
+{
+ typedef typename Container::value_type ValueTp;
+ typedef Container C;
+ typedef std::pair<typename C::iterator, bool> R;
+ ConstructController* cc = getConstructController();
+ cc->reset();
+ {
+ PRINT("Testing C::insert(const value_type&)");
+ Container c;
+ const ValueTp v(42, 1);
+ cc->expect<const ValueTp&>();
+ assert(c.insert(v).second);
+ assert(!cc->unchecked());
+ {
+ DisableAllocationGuard g;
+ const ValueTp v2(42, 1);
+ assert(c.insert(v2).second == false);
+ }
+ }
+ {
+ PRINT("Testing C::insert(value_type&)");
+ Container c;
+ ValueTp v(42, 1);
+ cc->expect<const ValueTp&>();
+ assert(c.insert(v).second);
+ assert(!cc->unchecked());
+ {
+ DisableAllocationGuard g;
+ ValueTp v2(42, 1);
+ assert(c.insert(v2).second == false);
+ }
+ }
+ {
+ PRINT("Testing C::insert(value_type&&)");
+ Container c;
+ ValueTp v(42, 1);
+ cc->expect<ValueTp&&>();
+ assert(c.insert(std::move(v)).second);
+ assert(!cc->unchecked());
+ {
+ DisableAllocationGuard g;
+ ValueTp v2(42, 1);
+ assert(c.insert(std::move(v2)).second == false);
+ }
+ }
+ {
+ PRINT("Testing C::insert(std::initializer_list<ValueTp>)");
+ Container c;
+ std::initializer_list<ValueTp> il = { ValueTp(1, 1), ValueTp(2, 1) };
+ cc->expect<ValueTp const&>(2);
+ c.insert(il);
+ assert(!cc->unchecked());
+ {
+ DisableAllocationGuard g;
+ c.insert(il);
+ }
+ }
+ {
+ PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type const&");
+ Container c;
+ const ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1), ValueTp(3, 1) };
+ cc->expect<ValueTp const&>(3);
+ c.insert(std::begin(ValueList), std::end(ValueList));
+ assert(!cc->unchecked());
+ {
+ DisableAllocationGuard g;
+ c.insert(std::begin(ValueList), std::end(ValueList));
+ }
+ }
+ {
+ PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&&");
+ Container c;
+ ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) };
+ cc->expect<ValueTp&&>(3);
+ c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList)),
+ std::move_iterator<ValueTp*>(std::end(ValueList)));
+ assert(!cc->unchecked());
+ {
+ DisableAllocationGuard g;
+ ValueTp ValueList2[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) };
+ c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList2)),
+ std::move_iterator<ValueTp*>(std::end(ValueList2)));
+ }
+ }
+ {
+ PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&");
+ Container c;
+ ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) };
+ cc->expect<ValueTp const&>(3);
+ c.insert(std::begin(ValueList), std::end(ValueList));
+ assert(!cc->unchecked());
+ {
+ DisableAllocationGuard g;
+ c.insert(std::begin(ValueList), std::end(ValueList));
+ }
+ }
+}
+
+
+int main()
+{
+ testContainerInsert<TCT::unordered_map<> >();
+}
diff --git a/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_allocator_requirements.pass.cpp b/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_allocator_requirements.pass.cpp
new file mode 100644
index 0000000..0926e80
--- /dev/null
+++ b/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_allocator_requirements.pass.cpp
@@ -0,0 +1,108 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <unordered_map>
+
+// class unordered_multimap
+
+// insert(...)
+
+// UNSUPPORTED: c++98, c++03
+
+#include <unordered_map>
+#include <iostream>
+#include <cassert>
+
+#include "test_macros.h"
+#include "count_new.hpp"
+#include "container_test_types.h"
+
+#if TEST_STD_VER >= 11
+template <class Arg>
+void PrintInfo(int line, Arg&& arg)
+#else
+template <class Arg>
+void PrintInfo(int line, Arg arg)
+#endif
+{
+ std::cout << "In " << __FILE__ << ":" << line << ":\n " << arg << "\n" << std::endl;
+}
+#define PRINT(...) PrintInfo(__LINE__, __VA_ARGS__)
+
+template <class Container>
+void testContainerInsert()
+{
+ typedef typename Container::value_type ValueTp;
+ typedef Container C;
+ ConstructController* cc = getConstructController();
+ cc->reset();
+ {
+ PRINT("Testing C::insert(const value_type&)");
+ Container c;
+ const ValueTp v(42, 1);
+ cc->expect<const ValueTp&>();
+ c.insert(v);
+ assert(!cc->unchecked());
+ }
+ {
+ PRINT("Testing C::insert(value_type&)");
+ Container c;
+ ValueTp v(42, 1);
+ cc->expect<ValueTp&>();
+ c.insert(v);
+ assert(!cc->unchecked());
+ }
+ {
+ PRINT("Testing C::insert(value_type&&)");
+ Container c;
+ ValueTp v(42, 1);
+ cc->expect<ValueTp&&>();
+ c.insert(std::move(v));
+ assert(!cc->unchecked());
+ }
+ {
+ PRINT("Testing C::insert(std::initializer_list<ValueTp>)");
+ Container c;
+ std::initializer_list<ValueTp> il = { ValueTp(1, 1), ValueTp(2, 1) };
+ cc->expect<ValueTp const&>(2);
+ c.insert(il);
+ assert(!cc->unchecked());
+ }
+ {
+ PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type const&");
+ Container c;
+ const ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1), ValueTp(3, 1) };
+ cc->expect<ValueTp const&>(3);
+ c.insert(std::begin(ValueList), std::end(ValueList));
+ assert(!cc->unchecked());
+ }
+ {
+ PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&&");
+ Container c;
+ ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) };
+ cc->expect<ValueTp&&>(3);
+ c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList)),
+ std::move_iterator<ValueTp*>(std::end(ValueList)));
+ assert(!cc->unchecked());
+ }
+ {
+ PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&");
+ Container c;
+ ValueTp ValueList[] = { ValueTp(1, 1), ValueTp(2, 1) , ValueTp(3, 1) };
+ cc->expect<ValueTp&>(3);
+ c.insert(std::begin(ValueList), std::end(ValueList));
+ assert(!cc->unchecked());
+ }
+}
+
+
+int main()
+{
+ testContainerInsert<TCT::unordered_multimap<> >();
+}
diff --git a/test/std/containers/unord/unord.multiset/insert_allocator_requirements.pass.cpp b/test/std/containers/unord/unord.multiset/insert_allocator_requirements.pass.cpp
new file mode 100644
index 0000000..ae8ce05
--- /dev/null
+++ b/test/std/containers/unord/unord.multiset/insert_allocator_requirements.pass.cpp
@@ -0,0 +1,107 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <unordered_set>
+
+// class unordered_multiset
+
+// insert(...)
+
+// UNSUPPORTED: c++98, c++03
+
+#include <unordered_set>
+#include <iostream>
+#include <cassert>
+
+#include "test_macros.h"
+#include "count_new.hpp"
+#include "container_test_types.h"
+
+#if TEST_STD_VER >= 11
+template <class Arg>
+void PrintInfo(int line, Arg&& arg)
+#else
+template <class Arg>
+void PrintInfo(int line, Arg arg)
+#endif
+{
+ std::cout << "In " << __FILE__ << ":" << line << ":\n " << arg << "\n" << std::endl;
+}
+#define PRINT(...) PrintInfo(__LINE__, __VA_ARGS__)
+
+template <class Container>
+void testContainerInsert()
+{
+ typedef typename Container::value_type ValueTp;
+ typedef Container C;
+ ConstructController* cc = getConstructController();
+ cc->reset();
+ {
+ PRINT("Testing C::insert(const value_type&)");
+ Container c;
+ const ValueTp v(42);
+ cc->expect<const ValueTp&>();
+ c.insert(v);
+ assert(!cc->unchecked());
+ }
+ {
+ PRINT("Testing C::insert(value_type&)");
+ Container c;
+ ValueTp v(42);
+ cc->expect<const ValueTp&>();
+ c.insert(v);
+ assert(!cc->unchecked());
+ }
+ {
+ PRINT("Testing C::insert(value_type&&)");
+ Container c;
+ ValueTp v(42);
+ cc->expect<ValueTp&&>();
+ c.insert(std::move(v));
+ assert(!cc->unchecked());
+ }
+ {
+ PRINT("Testing C::insert(std::initializer_list<ValueTp>)");
+ Container c;
+ std::initializer_list<ValueTp> il = { ValueTp(1), ValueTp(2) };
+ cc->expect<ValueTp const&>(2);
+ c.insert(il);
+ assert(!cc->unchecked());
+ }
+ {
+ PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type const&");
+ Container c;
+ const ValueTp ValueList[] = { ValueTp(1), ValueTp(2), ValueTp(3) };
+ cc->expect<ValueTp const&>(3);
+ c.insert(std::begin(ValueList), std::end(ValueList));
+ assert(!cc->unchecked());
+ }
+ {
+ PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&&");
+ Container c;
+ ValueTp ValueList[] = { ValueTp(1), ValueTp(2) , ValueTp(3) };
+ cc->expect<ValueTp&&>(3);
+ c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList)),
+ std::move_iterator<ValueTp*>(std::end(ValueList)));
+ assert(!cc->unchecked());
+ }
+ {
+ PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&");
+ Container c;
+ ValueTp ValueList[] = { ValueTp(1), ValueTp(2) , ValueTp(3) };
+ cc->expect<ValueTp&>(3);
+ c.insert(std::begin(ValueList), std::end(ValueList));
+ assert(!cc->unchecked());
+ }
+}
+
+int main()
+{
+ testContainerInsert<TCT::unordered_multiset<> >();
+}
diff --git a/test/std/containers/unord/unord.set/insert_allocator_requirements.pass.cpp b/test/std/containers/unord/unord.set/insert_allocator_requirements.pass.cpp
new file mode 100644
index 0000000..f5a30c2
--- /dev/null
+++ b/test/std/containers/unord/unord.set/insert_allocator_requirements.pass.cpp
@@ -0,0 +1,142 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <unordered_set>
+
+// class unordered_set
+
+// insert(...)
+
+// UNSUPPORTED: c++98, c++03
+
+#include <unordered_set>
+#include <iostream>
+#include <cassert>
+
+#include "test_macros.h"
+#include "count_new.hpp"
+#include "container_test_types.h"
+
+#if TEST_STD_VER >= 11
+template <class Arg>
+void PrintInfo(int line, Arg&& arg)
+#else
+template <class Arg>
+void PrintInfo(int line, Arg arg)
+#endif
+{
+ std::cout << "In " << __FILE__ << ":" << line << ":\n " << arg << "\n" << std::endl;
+}
+#define PRINT(...) PrintInfo(__LINE__, __VA_ARGS__)
+
+template <class Container>
+void testContainerInsert()
+{
+ typedef typename Container::value_type ValueTp;
+ typedef Container C;
+ typedef std::pair<typename C::iterator, bool> R;
+ ConstructController* cc = getConstructController();
+ cc->reset();
+ {
+ PRINT("Testing C::insert(const value_type&)");
+ Container c;
+ const ValueTp v(42);
+ cc->expect<const ValueTp&>();
+ assert(c.insert(v).second);
+ assert(!cc->unchecked());
+ {
+ DisableAllocationGuard g;
+ const ValueTp v2(42);
+ assert(c.insert(v2).second == false);
+ }
+ }
+ {
+ PRINT("Testing C::insert(value_type&)");
+ Container c;
+ ValueTp v(42);
+ cc->expect<const ValueTp&>();
+ assert(c.insert(v).second);
+ assert(!cc->unchecked());
+ {
+ DisableAllocationGuard g;
+ ValueTp v2(42);
+ assert(c.insert(v2).second == false);
+ }
+ }
+ {
+ PRINT("Testing C::insert(value_type&&)");
+ Container c;
+ ValueTp v(42);
+ cc->expect<ValueTp&&>();
+ assert(c.insert(std::move(v)).second);
+ assert(!cc->unchecked());
+ {
+ DisableAllocationGuard g;
+ ValueTp v2(42);
+ assert(c.insert(std::move(v2)).second == false);
+ }
+ }
+ {
+ PRINT("Testing C::insert(std::initializer_list<ValueTp>)");
+ Container c;
+ std::initializer_list<ValueTp> il = { ValueTp(1), ValueTp(2) };
+ cc->expect<ValueTp const&>(2);
+ c.insert(il);
+ assert(!cc->unchecked());
+ {
+ DisableAllocationGuard g;
+ c.insert(il);
+ }
+ }
+ {
+ PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type const&");
+ Container c;
+ const ValueTp ValueList[] = { ValueTp(1), ValueTp(2), ValueTp(3) };
+ cc->expect<ValueTp const&>(3);
+ c.insert(std::begin(ValueList), std::end(ValueList));
+ assert(!cc->unchecked());
+ {
+ DisableAllocationGuard g;
+ c.insert(std::begin(ValueList), std::end(ValueList));
+ }
+ }
+ {
+ PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&&");
+ Container c;
+ ValueTp ValueList[] = { ValueTp(1), ValueTp(2) , ValueTp(3) };
+ cc->expect<ValueTp&&>(3);
+ c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList)),
+ std::move_iterator<ValueTp*>(std::end(ValueList)));
+ assert(!cc->unchecked());
+ {
+ DisableAllocationGuard g;
+ ValueTp ValueList2[] = { ValueTp(1), ValueTp(2) , ValueTp(3) };
+ c.insert(std::move_iterator<ValueTp*>(std::begin(ValueList2)),
+ std::move_iterator<ValueTp*>(std::end(ValueList2)));
+ }
+ }
+ {
+ PRINT("Testing C::insert(Iter, Iter) for *Iter = value_type&");
+ Container c;
+ ValueTp ValueList[] = { ValueTp(1), ValueTp(2) , ValueTp(3) };
+ cc->expect<ValueTp const&>(3);
+ c.insert(std::begin(ValueList), std::end(ValueList));
+ assert(!cc->unchecked());
+ {
+ DisableAllocationGuard g;
+ c.insert(std::begin(ValueList), std::end(ValueList));
+ }
+ }
+}
+
+
+int main()
+{
+ testContainerInsert<TCT::unordered_set<> >();
+}
diff --git a/test/support/container_test_types.h b/test/support/container_test_types.h
new file mode 100644
index 0000000..7f6544e
--- /dev/null
+++ b/test/support/container_test_types.h
@@ -0,0 +1,522 @@
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+#ifndef SUPPORT_CONTAINER_TEST_TYPES_H
+#define SUPPORT_CONTAINER_TEST_TYPES_H
+
+// container_test_types.h - A set of types used for testing STL containers.
+// The types container within this header are used to test the requirements in
+// [container.requirements.general]. The header is made up of 3 main components:
+//
+// * test-types: 'CopyInsertable', 'MoveInsertable' and 'EmplaceConstructible' -
+// These test types are used to test the container requirements of the same
+// name. These test types use the global 'AllocatorConstructController' to
+// assert that they are only constructed by the containers allocator.
+//
+// * test-allocator: 'ContainerTestAllocator' - This test allocator is used to
+// test the portions of [container.requirements.general] that pertain to the
+// containers allocator. The three primary jobs of the test allocator are:
+// 1. Enforce that 'a.construct(...)' and 'a.destroy(...)' are only ever
+// instantiated for 'Container::value_type'.
+// 2. Provide a mechanism of checking calls to 'a.construct(Args...)'.
+// Including controlling when and with what types 'a.construct(...)'
+// may be called with.
+// 3. Support the test types internals by controlling the global
+// 'AllocatorConstructController' object.
+//
+// * 'AllocatorConstructController' - This type defines an interface for testing
+// the construction of types using an allocator. This type is used to communicate
+// between the test author, the containers allocator, and the types
+// being constructed by the container.
+// The controllers primary functions are:
+// 1. Allow calls to 'a.construct(p, args...)' to be checked by a test.
+// The test uses 'cc->expect<Args...>()' to specify that the allocator
+// should expect one call to 'a.construct' with the specified argument
+// types.
+// 2. Controlling the value of 'cc->isInAllocatorConstruct()' within the
+// 'construct' method. The test-types use this value to assert that
+// they are being constructed by the allocator.
+//
+// 'AllocatorConstructController' enforces the Singleton pattern since the
+// test-types, test-allocator and test need to share the same controller
+// object. A pointer to the global controller is returned by
+// 'getConstructController()'.
+//
+//----------------------------------------------------------------------------
+/*
+ * Usage: The following example checks that 'unordered_map::emplace(Args&&...)'
+ * with 'Args = [CopyInsertable<1> const&, CopyInsertible<2>&&]'
+ * calls 'alloc.construct(value_type*, Args&&...)' with the same types.
+ *
+ * // Typedefs for container
+ * using Key = CopyInsertible<1>;
+ * using Value = CopyInsertible<2>;
+ * using ValueTp = std::pair<const Key, Value>;
+ * using Alloc = ContainerTestAllocator<ValueTp, ValueTp>;
+ * using Map = std::unordered_map<Key, Value, std::hash<Key>, std::equal_to<Key>, Alloc>;
+ *
+ * // Get the global controller, reset it, and construct an allocator with
+ * // the controller.
+ * ConstructController* cc = getConstructController();
+ * cc->reset();
+ *
+ * // Create a Map and a Key and Value to insert. Note that the test-allocator
+ * // does not need to be given 'cc'.
+ * Map m;
+ * const Key k(1);
+ * Value v(1);
+ *
+ * // Tell the controller to expect a construction from the specified types.
+ * cc->expect<Key const&, Value&&>();
+ *
+ * // Emplace the objects into the container. 'Alloc.construct(p, UArgs...)'
+ * // will assert 'cc->check<UArgs&&>()' is true which will consume
+ * // the call to 'cc->expect<...>()'.
+ * m.emplace(k, std::move(v));
+ *
+ * // Assert that the "expect" was consumed by a matching "check" call within
+ * // Alloc.
+ * assert(!cc->unexpected());
+ *
+ */
+
+#include <functional>
+#include <unordered_map>
+#include <unordered_set>
+#include <cassert>
+
+#include "test_macros.h"
+
+namespace detail {
+// TypeID - Represent a unique identifier for a type. TypeID allows equality
+// comparisons between different types.
+struct TypeID {
+ friend bool operator==(TypeID const& LHS, TypeID const& RHS)
+ {return LHS.m_id == RHS.m_id; }
+ friend bool operator!=(TypeID const& LHS, TypeID const& RHS)
+ {return LHS.m_id != RHS.m_id; }
+private:
+ explicit TEST_CONSTEXPR TypeID(const int* xid) : m_id(xid) {}
+ const int* const m_id;
+ template <class T> friend class TypeInfo;
+};
+
+// TypeInfo - Represent information for the specified type 'T', including a
+// unique TypeID.
+template <class T>
+class TypeInfo {
+public:
+ typedef T value_type;
+ typedef TypeID ID;
+ static ID const& GetID() { static ID id(&dummy_addr); return id; }
+
+private:
+ static const int dummy_addr;
+};
+
+template <class L, class R>
+inline bool operator==(TypeInfo<L> const&, TypeInfo<R> const&)
+{ return std::is_same<L, R>::value; }
+
+template <class L, class R>
+inline bool operator!=(TypeInfo<L> const& lhs, TypeInfo<R> const& rhs)
+{ return !(lhs == rhs); }
+
+template <class T>
+const int TypeInfo<T>::dummy_addr = 42;
+
+// makeTypeID - Return the TypeID for the specified type 'T'.
+template <class T>
+inline TEST_CONSTEXPR TypeID const& makeTypeID() { return TypeInfo<T>::GetID(); }
+
+#if TEST_STD_VER >= 11
+template <class ...Args>
+struct ArgumentListID {};
+
+// makeArgumentID - Create and return a unique identifier for a given set
+// of arguments.
+template <class ...Args>
+inline TEST_CONSTEXPR TypeID const& makeArgumentID() {
+ return makeTypeID<ArgumentListID<Args...>>();
+}
+#else
+template <class A1 = void, class A2 = void, class A3 = void>
+struct ArgumentListID {};
+
+template <class A1>
+inline TypeID const& makeArgumentID() {
+ return makeTypeID<ArgumentListID<A1> >();
+}
+
+template <class A1, class A2>
+inline TypeID const& makeArgumentID() {
+ return makeTypeID<ArgumentListID<A1, A2> >();
+}
+
+template <class A1, class A2, class A3>
+inline TypeID const& makeArgumentID() {
+ return makeTypeID<ArgumentListID<A1, A2, A3> >();
+}
+#endif
+
+} // namespace detail
+
+//===----------------------------------------------------------------------===//
+// AllocatorConstructController
+//===----------------------------------------------------------------------===//
+
+struct AllocatorConstructController {
+ const detail::TypeID* m_expected_args;
+ bool m_allow_constructions;
+ bool m_allow_unchecked;
+ int m_expected_count;
+
+ // Check for and consume an expected construction added by 'expect'.
+ // Return true if the construction was expected and false otherwise.
+ // This should only be called by 'Allocator.construct'.
+ bool check(detail::TypeID const& tid) {
+ if (!m_expected_args)
+ assert(m_allow_unchecked);
+ bool res = *m_expected_args == tid;
+ if (m_expected_count == -1 || --m_expected_count == -1)
+ m_expected_args = nullptr;
+ return res;
+ }
+
+ // Return true iff there is an unchecked construction expression.
+ bool unchecked() {
+ return m_expected_args != nullptr;
+ }
+
+ // Expect a call to Allocator::construct with Args that match 'tid'.
+ void expect(detail::TypeID const& tid) {
+ assert(!unchecked());
+ m_expected_args = &tid;
+ }
+
+#if TEST_STD_VER >= 11
+ template <class ...Args>
+ void expect(int times = 1) {
+ assert(!unchecked());
+ assert(times > 0);
+ m_expected_count = times - 1;
+ m_expected_args = &detail::makeArgumentID<Args...>();
+ }
+ template <class ...Args>
+ bool check() {
+ return check(detail::makeArgumentID<Args...>());
+ }
+#else
+ template <class A1>
+ void expect(int times = 1) {
+ assert(!unchecked());
+ assert(times > 0);
+ m_expected_count = times - 1;
+ m_expected_args = &detail::makeArgumentID<A1>();
+ }
+ template <class A1>
+ bool check() {
+ return check(detail::makeArgumentID<A1>());
+ }
+#endif
+
+ // Return true iff the program is currently within a call to "Allocator::construct"
+ bool isInAllocatorConstruct() const {
+ return m_allow_constructions;
+ }
+
+ void inAllocatorConstruct(bool value = true) {
+ m_allow_constructions = value;
+ }
+
+ void allowUnchecked(bool value = true) {
+ m_allow_unchecked = value;
+ }
+
+ void reset() {
+ m_allow_constructions = false;
+ m_expected_args = nullptr;
+ m_allow_unchecked = false;
+ m_expected_count = -1;
+ }
+
+private:
+ friend AllocatorConstructController* getConstructController();
+ AllocatorConstructController() { reset(); }
+ AllocatorConstructController(AllocatorConstructController const&);
+ AllocatorConstructController& operator=(AllocatorConstructController const&);
+};
+
+typedef AllocatorConstructController ConstructController;
+
+// getConstructController - Return the global allocator construction controller.
+inline ConstructController* getConstructController() {
+ static ConstructController c;
+ return &c;
+}
+
+//===----------------------------------------------------------------------===//
+// ContainerTestAllocator
+//===----------------------------------------------------------------------===//
+
+// ContainerTestAllocator - A STL allocator type that only allows 'construct'
+// and 'destroy' to be called for 'AllowConstructT' types. ContainerTestAllocator
+// uses the 'AllocatorConstructionController' interface.
+template <class T, class AllowConstructT>
+class ContainerTestAllocator
+{
+ struct InAllocatorConstructGuard {
+ ConstructController *m_cc;
+ bool m_old;
+ InAllocatorConstructGuard(ConstructController* cc) : m_cc(cc) {
+ if (m_cc) {
+ m_old = m_cc->isInAllocatorConstruct();
+ m_cc->inAllocatorConstruct(true);
+ }
+ }
+ ~InAllocatorConstructGuard() {
+ if (m_cc) m_cc->inAllocatorConstruct(m_old);
+ }
+ private:
+ InAllocatorConstructGuard(InAllocatorConstructGuard const&);
+ InAllocatorConstructGuard& operator=(InAllocatorConstructGuard const&);
+ };
+
+public:
+ typedef T value_type;
+
+ int construct_called;
+ int destroy_called;
+ ConstructController* controller;
+
+ ContainerTestAllocator() TEST_NOEXCEPT
+ : controller(getConstructController()) {}
+
+ explicit ContainerTestAllocator(ConstructController* c)
+ : controller(c)
+ {}
+
+ template <class U>
+ ContainerTestAllocator(ContainerTestAllocator<U, AllowConstructT> other) TEST_NOEXCEPT
+ : controller(other.controller)
+ {}
+
+ T* allocate(std::size_t n)
+ {
+ return static_cast<T*>(::operator new(n*sizeof(T)));
+ }
+
+ void deallocate(T* p, std::size_t)
+ {
+ return ::operator delete(static_cast<void*>(p));
+ }
+#if TEST_STD_VER >= 11
+ template <class Up, class ...Args>
+ void construct(Up* p, Args&&... args) {
+ static_assert((std::is_same<Up, AllowConstructT>::value),
+ "Only allowed to construct Up");
+ assert(controller->check<Args&&...>());
+ {
+ InAllocatorConstructGuard g(controller);
+ ::new ((void*)p) Up(std::forward<Args>(args)...);
+ }
+ }
+#else
+ template <class Up, class A0>
+ void construct(Up* p, A0& a0) {
+ static_assert((std::is_same<Up, AllowConstructT>::value),
+ "Only allowed to construct Up");
+ assert(controller->check<A0&>());
+ {
+ InAllocatorConstructGuard g(controller);
+ ::new ((void*)p) Up(a0);
+ }
+ }
+ template <class Up, class A0, class A1>
+ void construct(Up* p, A0& a0, A1& a1) {
+ static_assert((std::is_same<Up, AllowConstructT>::value),
+ "Only allowed to construct Up");
+ assert((controller->check<A0&, A1&>()));
+ {
+ InAllocatorConstructGuard g(controller);
+ ::new ((void*)p) Up(a0, a1);
+ }
+ }
+#endif
+
+ template <class Up>
+ void destroy(Up* p) {
+ static_assert((std::is_same<Up, AllowConstructT>::value),
+ "Only allowed to destroy Up");
+ {
+ InAllocatorConstructGuard g(controller);
+ p->~Up();
+ }
+ }
+
+ friend bool operator==(ContainerTestAllocator, ContainerTestAllocator) {return true;}
+ friend bool operator!=(ContainerTestAllocator x, ContainerTestAllocator y) {return !(x == y);}
+};
+
+#if TEST_STD_VER >= 11
+namespace test_detail {
+typedef ContainerTestAllocator<int, int> A1;
+typedef std::allocator_traits<A1> A1T;
+typedef ContainerTestAllocator<float, int> A2;
+typedef std::allocator_traits<A2> A2T;
+
+static_assert(std::is_same<A1T::rebind_traits<float>, A2T>::value, "");
+static_assert(std::is_same<A2T::rebind_traits<int>, A1T>::value, "");
+} // end namespace test_detail
+#endif
+
+//===----------------------------------------------------------------------===//
+// 'CopyInsertable', 'MoveInsertable' and 'EmplaceConstructible' test types
+//===----------------------------------------------------------------------===//
+
+template <int Dummy = 0>
+struct CopyInsertable {
+ int data;
+ mutable bool copied_once;
+ bool constructed_under_allocator;
+
+ explicit CopyInsertable(int val) : data(val), copied_once(false),
+ constructed_under_allocator(false) {
+ if (getConstructController()->isInAllocatorConstruct()) {
+ copied_once = true;
+ constructed_under_allocator = true;
+ }
+ }
+
+ CopyInsertable(CopyInsertable const& other) : data(other.data),
+ copied_once(true),
+ constructed_under_allocator(true) {
+ assert(getConstructController()->isInAllocatorConstruct());
+ assert(other.copied_once == false);
+ other.copied_once = true;
+ }
+
+ CopyInsertable(CopyInsertable& other) : data(other.data), copied_once(true),
+ constructed_under_allocator(true) {
+ assert(getConstructController()->isInAllocatorConstruct());
+ assert(other.copied_once == false);
+ other.copied_once = true;
+ }
+
+#if TEST_STD_VER >= 11
+ CopyInsertable(CopyInsertable&& other) : CopyInsertable(other) {}
+
+ // Forgive pair for not downcasting this to an lvalue it its constructors.
+ CopyInsertable(CopyInsertable const && other) : CopyInsertable(other) {}
+
+
+ template <class ...Args>
+ CopyInsertable(Args&&... args) {
+ assert(false);
+ }
+#else
+ template <class Arg>
+ CopyInsertable(Arg&) {
+ assert(false);
+ }
+#endif
+
+ ~CopyInsertable() {
+ assert(constructed_under_allocator == getConstructController()->isInAllocatorConstruct());
+ }
+
+ void reset(int value) {
+ data = value;
+ copied_once = false;
+ constructed_under_allocator = false;
+ }
+};
+
+template <int ID>
+bool operator==(CopyInsertable<ID> const& L, CopyInsertable<ID> const& R) {
+ return L.data == R.data;
+}
+
+
+template <int ID>
+bool operator!=(CopyInsertable<ID> const& L, CopyInsertable<ID> const& R) {
+ return L.data != R.data;
+}
+
+template <int ID>
+bool operator <(CopyInsertable<ID> const& L, CopyInsertable<ID> const& R) {
+ return L.data < R.data;
+}
+
+namespace std {
+template <int ID>
+struct hash< ::CopyInsertable<ID> > {
+ typedef ::CopyInsertable<ID> argument_type;
+ typedef size_t result_type;
+
+ size_t operator()(argument_type const& arg) const {
+ return arg.data;
+ }
+};
+} // namespace std
+
+// TCT - Test container type
+namespace TCT {
+
+template <class Key = CopyInsertable<1>, class Value = CopyInsertable<2> >
+struct unordered_map_type {
+ typedef std::pair<const Key, Value> ValueTp;
+ typedef
+ std::unordered_map<Key, Value, std::hash<Key>, std::equal_to<Key>,
+ ContainerTestAllocator<ValueTp, ValueTp> >
+ type;
+};
+
+template <class Key = CopyInsertable<1>, class Value = CopyInsertable<2>>
+struct unordered_multimap_type {
+ typedef std::pair<const Key, Value> ValueTp;
+ typedef
+ std::unordered_multimap<Key, Value, std::hash<Key>, std::equal_to<Key>,
+ ContainerTestAllocator<ValueTp, ValueTp> >
+ type;
+};
+
+template <class Value = CopyInsertable<1> >
+struct unordered_set_type {
+ typedef
+ std::unordered_set<Value, std::hash<Value>, std::equal_to<Value>,
+ ContainerTestAllocator<Value, Value> >
+ type;
+};
+
+template <class Value = CopyInsertable<1> >
+struct unordered_multiset_type {
+ typedef
+ std::unordered_multiset<Value, std::hash<Value>, std::equal_to<Value>,
+ ContainerTestAllocator<Value, Value> >
+ type;
+};
+
+#if TEST_STD_VER >= 11
+template <class ...Args>
+using unordered_map = typename unordered_map_type<Args...>::type;
+
+template <class ...Args>
+using unordered_multimap = typename unordered_multimap_type<Args...>::type;
+
+template <class ...Args>
+using unordered_set = typename unordered_set_type<Args...>::type;
+
+template <class ...Args>
+using unordered_multiset = typename unordered_multiset_type<Args...>::type;
+#endif
+
+} // end namespace TCT
+
+
+#endif // SUPPORT_CONTAINER_TEST_TYPES_H