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/__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)