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