Recommit r260012 - Cleanup node-type handling in the unordered containers.
This time I kept <ext/hash_map> working!
This patch is the first in a series of patches that's meant to better
support unordered_map. unordered_map has a special "value_type" that
differs from pair<const Key, Value>. In order to meet the EmplaceConstructible
and CopyInsertable requirements we need to teach __hash_table about this
special value_type.
This patch creates a "__hash_node_types" traits class that contains
all of the typedefs needed by the unordered containers and it's iterators.
These typedefs include ones for each node type and node pointer type,
as well as special typedefs for "unordered_map"'s value type.
As a result of this change all of the unordered containers now all support
incomplete types.
As a drive-by fix I changed the difference_type in __hash_table to always
be ptrdiff_t. There is a corresponding change to size_type but it cannot
take affect until an ABI break.
This patch will be followed up shortly with fixes for various unordered_map
bugs and problems.
git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@260431 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/unordered_map b/include/unordered_map
index 85a54a7..a05c2b5 100644
--- a/include/unordered_map
+++ b/include/unordered_map
@@ -384,6 +384,7 @@
class __unordered_map_hasher
: private _Hash
{
+ typedef typename __key_value_types<_Cp>::__map_value_type _PairT;
public:
_LIBCPP_INLINE_VISIBILITY
__unordered_map_hasher()
@@ -414,6 +415,7 @@
{
_Hash __hash_;
+ typedef typename __key_value_types<_Cp>::__map_value_type _PairT;
public:
_LIBCPP_INLINE_VISIBILITY
__unordered_map_hasher()
@@ -455,6 +457,7 @@
class __unordered_map_equal
: private _Pred
{
+ typedef typename __key_value_types<_Cp>::__map_value_type _PairT;
public:
_LIBCPP_INLINE_VISIBILITY
__unordered_map_equal()
@@ -488,6 +491,7 @@
{
_Pred __pred_;
+ typedef typename __key_value_types<_Cp>::__map_value_type _PairT;
public:
_LIBCPP_INLINE_VISIBILITY
__unordered_map_equal()
@@ -508,6 +512,9 @@
_LIBCPP_INLINE_VISIBILITY
bool operator()(const _Key& __x, const _Cp& __y) const
{return __pred_(__x, __y.__cc.first);}
+ _LIBCPP_INLINE_VISIBILITY
+ bool operator()(const _Key& __x, const _PairT& __y) const
+ {return __pred_(__x, __y.first);}
void swap(__unordered_map_equal&__y)
_NOEXCEPT_(__is_nothrow_swappable<_Pred>::value)
{
@@ -531,12 +538,11 @@
{
typedef _Alloc allocator_type;
typedef allocator_traits<allocator_type> __alloc_traits;
- typedef typename __alloc_traits::value_type::value_type value_type;
+
public:
- typedef typename __alloc_traits::pointer pointer;
+
+ typedef typename __alloc_traits::pointer pointer;
private:
- typedef typename value_type::value_type::first_type first_type;
- typedef typename value_type::value_type::second_type second_type;
allocator_type& __na_;
@@ -656,15 +662,14 @@
{
_HashIterator __i_;
- typedef const typename _HashIterator::value_type::value_type::first_type key_type;
- typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
+ typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
+
public:
typedef forward_iterator_tag iterator_category;
- typedef pair<key_type, mapped_type> value_type;
- typedef typename _HashIterator::difference_type difference_type;
+ typedef typename _NodeTypes::__map_value_type value_type;
+ typedef typename _NodeTypes::difference_type difference_type;
typedef value_type& reference;
- typedef typename __rebind_pointer<typename _HashIterator::pointer, value_type>::type
- pointer;
+ typedef typename _NodeTypes::__map_value_type_pointer pointer;
_LIBCPP_INLINE_VISIBILITY
__hash_map_iterator() _NOEXCEPT {}
@@ -706,15 +711,14 @@
{
_HashIterator __i_;
- typedef const typename _HashIterator::value_type::value_type::first_type key_type;
- typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
+ typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
+
public:
typedef forward_iterator_tag iterator_category;
- typedef pair<key_type, mapped_type> value_type;
- typedef typename _HashIterator::difference_type difference_type;
+ typedef typename _NodeTypes::__map_value_type value_type;
+ typedef typename _NodeTypes::difference_type difference_type;
typedef const value_type& reference;
- typedef typename __rebind_pointer<typename _HashIterator::pointer, const value_type>::type
- pointer;
+ typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
_LIBCPP_INLINE_VISIBILITY
__hash_map_const_iterator() _NOEXCEPT {}
@@ -796,8 +800,8 @@
public:
typedef typename __alloc_traits::pointer pointer;
typedef typename __alloc_traits::const_pointer const_pointer;
- typedef typename __alloc_traits::size_type size_type;
- typedef typename __alloc_traits::difference_type difference_type;
+ typedef typename __table::size_type size_type;
+ typedef typename __table::difference_type difference_type;
typedef __hash_map_iterator<typename __table::iterator> iterator;
typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
@@ -1641,11 +1645,14 @@
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 __node_traits::size_type,
+ typename __alloc_traits::size_type>::value),
+ "Allocator uses different size_type for different types");
public:
typedef typename __alloc_traits::pointer pointer;
typedef typename __alloc_traits::const_pointer const_pointer;
- typedef typename __alloc_traits::size_type size_type;
- typedef typename __alloc_traits::difference_type difference_type;
+ typedef typename __table::size_type size_type;
+ typedef typename __table::difference_type difference_type;
typedef __hash_map_iterator<typename __table::iterator> iterator;
typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;