Implement full support for non-pointer types in custom allocators. This is for the unordered containers only. This work still needs to be done on the sequence containers.
git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@184635 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/__hash_table b/include/__hash_table
index 6f6050d..2b282d3 100644
--- a/include/__hash_table
+++ b/include/__hash_table
@@ -33,7 +33,6 @@
struct __hash_node_base
{
typedef __hash_node_base __first_node;
- // typedef _NodePtr pointer;
_NodePtr __next_;
@@ -111,7 +110,7 @@
_LIBCPP_INLINE_VISIBILITY
reference operator*() const {return __node_->__value_;}
_LIBCPP_INLINE_VISIBILITY
- pointer operator->() const {return _VSTD::addressof(__node_->__value_);}
+ pointer operator->() const {return pointer_traits<pointer>::pointer_to(__node_->__value_);}
_LIBCPP_INLINE_VISIBILITY
__hash_iterator& operator++()
@@ -189,7 +188,7 @@
_LIBCPP_INLINE_VISIBILITY
reference operator*() const {return __node_->__value_;}
_LIBCPP_INLINE_VISIBILITY
- pointer operator->() const {return _VSTD::addressof(__node_->__value_);}
+ pointer operator->() const {return pointer_traits<pointer>::pointer_to(__node_->__value_);}
_LIBCPP_INLINE_VISIBILITY
__hash_const_iterator& operator++()
@@ -255,7 +254,7 @@
_LIBCPP_INLINE_VISIBILITY
reference operator*() const {return __node_->__value_;}
_LIBCPP_INLINE_VISIBILITY
- pointer operator->() const {return &__node_->__value_;}
+ pointer operator->() const {return pointer_traits<pointer>::pointer_to(__node_->__value_);}
_LIBCPP_INLINE_VISIBILITY
__hash_local_iterator& operator++()
@@ -345,7 +344,7 @@
_LIBCPP_INLINE_VISIBILITY
reference operator*() const {return __node_->__value_;}
_LIBCPP_INLINE_VISIBILITY
- pointer operator->() const {return &__node_->__value_;}
+ pointer operator->() const {return pointer_traits<pointer>::pointer_to(__node_->__value_);}
_LIBCPP_INLINE_VISIBILITY
__hash_const_local_iterator& operator++()
@@ -505,8 +504,15 @@
__node_allocator;
typedef allocator_traits<__node_allocator> __node_traits;
typedef typename __node_traits::pointer __node_pointer;
- typedef typename __node_traits::const_pointer __node_const_pointer;
+ typedef typename __node_traits::pointer __node_const_pointer;
typedef __hash_node_base<__node_pointer> __first_node;
+ typedef typename pointer_traits<__node_pointer>::template
+#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
+ rebind<__first_node>
+#else
+ rebind<__first_node>::other
+#endif
+ __node_base_pointer;
private:
@@ -558,9 +564,9 @@
public:
typedef __hash_iterator<__node_pointer> iterator;
- typedef __hash_const_iterator<__node_const_pointer> const_iterator;
+ typedef __hash_const_iterator<__node_pointer> const_iterator;
typedef __hash_local_iterator<__node_pointer> local_iterator;
- typedef __hash_const_local_iterator<__node_const_pointer> const_local_iterator;
+ typedef __hash_const_local_iterator<__node_pointer> const_local_iterator;
__hash_table()
_NOEXCEPT_(
@@ -706,7 +712,7 @@
_LIBCPP_INLINE_VISIBILITY
size_type max_bucket_count() const _NOEXCEPT
- {return __bucket_list_.get_deleter().__alloc().max_size();}
+ {return __pointer_alloc_traits::max_size(__bucket_list_.get_deleter().__alloc());}
size_type bucket_size(size_type __n) const;
_LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT
{
@@ -807,6 +813,9 @@
void __deallocate(__node_pointer __np) _NOEXCEPT;
__node_pointer __detach() _NOEXCEPT;
+
+ template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
+ template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
};
template <class _Tp, class _Hash, class _Equal, class _Alloc>
@@ -893,7 +902,7 @@
if (size() > 0)
{
__bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
- static_cast<__node_pointer>(_VSTD::addressof(__p1_.first()));
+ static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
__u.__p1_.first().__next_ = nullptr;
__u.size() = 0;
}
@@ -917,7 +926,7 @@
__p1_.first().__next_ = __u.__p1_.first().__next_;
__u.__p1_.first().__next_ = nullptr;
__bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
- static_cast<__node_pointer>(_VSTD::addressof(__p1_.first()));
+ static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
size() = __u.size();
__u.size() = 0;
}
@@ -1014,7 +1023,7 @@
if (size() > 0)
{
__bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
- static_cast<__node_pointer>(_VSTD::addressof(__p1_.first()));
+ static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
__u.__p1_.first().__next_ = nullptr;
__u.size() = 0;
}
@@ -1236,7 +1245,7 @@
__node_pointer __pn = __bucket_list_[__chash];
if (__pn == nullptr)
{
- __pn = static_cast<__node_pointer>(_VSTD::addressof(__p1_.first()));
+ __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
__nd->__next_ = __pn->__next_;
__pn->__next_ = __nd;
// fix up __bucket_list_
@@ -1274,7 +1283,7 @@
__node_pointer __pn = __bucket_list_[__chash];
if (__pn == nullptr)
{
- __pn = static_cast<__node_pointer>(_VSTD::addressof(__p1_.first()));
+ __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
__cp->__next_ = __pn->__next_;
__pn->__next_ = __cp;
// fix up __bucket_list_
@@ -1322,7 +1331,7 @@
{
if (__p != end() && key_eq()(*__p, __cp->__value_))
{
- __node_pointer __np = const_cast<__node_pointer>(__p.__node_);
+ __node_pointer __np = __p.__node_;
__cp->__hash_ = __np->__hash_;
size_type __bc = bucket_count();
if (size()+1 > __bc * max_load_factor() || __bc == 0)
@@ -1380,7 +1389,7 @@
__node_pointer __pn = __bucket_list_[__chash];
if (__pn == nullptr)
{
- __pn = static_cast<__node_pointer>(_VSTD::addressof(__p1_.first()));
+ __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
__h->__next_ = __pn->__next_;
__pn->__next_ = __h.get();
// fix up __bucket_list_
@@ -1542,7 +1551,7 @@
{
for (size_type __i = 0; __i < __nbc; ++__i)
__bucket_list_[__i] = nullptr;
- __node_pointer __pp(static_cast<__node_pointer>(_VSTD::addressof(__p1_.first())));
+ __node_pointer __pp(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())));
__node_pointer __cp = __pp->__next_;
if (__cp != nullptr)
{
@@ -1700,7 +1709,7 @@
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p)
{
- __node_pointer __np = const_cast<__node_pointer>(__p.__node_);
+ __node_pointer __np = __p.__node_;
iterator __r(__np);
++__r;
remove(__p);
@@ -1717,7 +1726,7 @@
++__first;
erase(__p);
}
- __node_pointer __np = const_cast<__node_pointer>(__last.__node_);
+ __node_pointer __np = __last.__node_;
return iterator (__np);
}
@@ -1757,7 +1766,7 @@
__hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT
{
// current node
- __node_pointer __cn = const_cast<__node_pointer>(__p.__node_);
+ __node_pointer __cn = __p.__node_;
size_type __bc = bucket_count();
size_t __chash = __constrain_hash(__cn->__hash_, __bc);
// find previous node
@@ -1767,7 +1776,8 @@
// Fix up __bucket_list_
// if __pn is not in same bucket (before begin is not in same bucket) &&
// if __cn->__next_ is not in same bucket (nullptr is not in same bucket)
- if (__pn == _VSTD::addressof(__p1_.first()) || __constrain_hash(__pn->__hash_, __bc) != __chash)
+ if (__pn == static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()))
+ || __constrain_hash(__pn->__hash_, __bc) != __chash)
{
if (__cn->__next_ == nullptr || __constrain_hash(__cn->__next_->__hash_, __bc) != __chash)
__bucket_list_[__chash] = nullptr;
@@ -1907,10 +1917,10 @@
__p3_.swap(__u.__p3_);
if (size() > 0)
__bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
- static_cast<__node_pointer>(_VSTD::addressof(__p1_.first()));
+ static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
if (__u.size() > 0)
__u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] =
- static_cast<__node_pointer>(_VSTD::addressof(__u.__p1_.first()));
+ static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__u.__p1_.first()));
}
template <class _Tp, class _Hash, class _Equal, class _Alloc>
diff --git a/include/unordered_map b/include/unordered_map
index 235b2ea..772c44b 100644
--- a/include/unordered_map
+++ b/include/unordered_map
@@ -492,8 +492,8 @@
public:
typedef typename __alloc_traits::pointer pointer;
private:
- typedef typename value_type::first_type first_type;
- typedef typename value_type::second_type second_type;
+ typedef typename value_type::value_type::first_type first_type;
+ typedef typename value_type::value_type::second_type second_type;
allocator_type& __na_;
@@ -535,9 +535,9 @@
void operator()(pointer __p) _NOEXCEPT
{
if (__second_constructed)
- __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second));
+ __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
if (__first_constructed)
- __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first));
+ __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
if (__p)
__alloc_traits::deallocate(__na_, __p, 1);
}
@@ -549,8 +549,8 @@
_HashIterator __i_;
typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
- typedef const typename _HashIterator::value_type::first_type key_type;
- typedef typename _HashIterator::value_type::second_type mapped_type;
+ typedef const typename _HashIterator::value_type::value_type::first_type key_type;
+ typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
public:
typedef forward_iterator_tag iterator_category;
typedef pair<key_type, mapped_type> value_type;
@@ -571,9 +571,9 @@
__hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
_LIBCPP_INLINE_VISIBILITY
- reference operator*() const {return *operator->();}
+ reference operator*() const {return __i_->__cc;}
_LIBCPP_INLINE_VISIBILITY
- pointer operator->() const {return (pointer)__i_.operator->();}
+ pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
_LIBCPP_INLINE_VISIBILITY
__hash_map_iterator& operator++() {++__i_; return *this;}
@@ -605,8 +605,8 @@
_HashIterator __i_;
typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
- typedef const typename _HashIterator::value_type::first_type key_type;
- typedef typename _HashIterator::value_type::second_type mapped_type;
+ typedef const typename _HashIterator::value_type::value_type::first_type key_type;
+ typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
public:
typedef forward_iterator_tag iterator_category;
typedef pair<key_type, mapped_type> value_type;
@@ -632,9 +632,9 @@
: __i_(__i.__i_) {}
_LIBCPP_INLINE_VISIBILITY
- reference operator*() const {return *operator->();}
+ reference operator*() const {return __i_->__cc;}
_LIBCPP_INLINE_VISIBILITY
- pointer operator->() const {return (pointer)__i_.operator->();}
+ pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
_LIBCPP_INLINE_VISIBILITY
__hash_map_const_iterator& operator++() {++__i_; return *this;}
@@ -671,11 +671,58 @@
typedef _Pred key_equal;
typedef _Alloc allocator_type;
typedef pair<const key_type, mapped_type> value_type;
+ typedef pair<key_type, mapped_type> __nc_value_type;
typedef value_type& reference;
typedef const value_type& const_reference;
private:
- typedef pair<key_type, mapped_type> __value_type;
+#if __cplusplus >= 201103L
+ union __value_type
+ {
+ typedef typename unordered_map::value_type value_type;
+ typedef typename unordered_map::__nc_value_type __nc_value_type;
+ value_type __cc;
+ __nc_value_type __nc;
+
+ template <class ..._Args>
+ __value_type(_Args&& ...__args)
+ : __cc(std::forward<_Args>(__args)...) {}
+
+ __value_type(const __value_type& __v)
+ : __cc(std::move(__v.__cc)) {}
+
+ __value_type(__value_type&& __v)
+ : __nc(std::move(__v.__nc)) {}
+
+ __value_type& operator=(const __value_type& __v)
+ {__nc = __v.__cc; return *this;}
+
+ __value_type& operator=(__value_type&& __v)
+ {__nc = std::move(__v.__nc); return *this;}
+
+ ~__value_type() {__cc.~value_type();}
+
+ operator const value_type& () const {return __cc;}
+ };
+#else
+ struct __value_type
+ {
+ typedef typename unordered_map::value_type value_type;
+ value_type __cc;
+
+ __value_type() {}
+
+ template <class _A0>
+ __value_type(const _A0& __a0)
+ : __cc(__a0) {}
+
+ template <class _A0, class _A1>
+ __value_type(const _A0& __a0, const _A1& __a1)
+ : __cc(__a0, __a1) {}
+
+ operator const value_type& () const {return __cc;}
+ };
+#endif
typedef __unordered_map_hasher<key_type, mapped_type, hasher> __hasher;
typedef __unordered_map_equal<key_type, mapped_type, key_equal> __key_equal;
typedef typename allocator_traits<allocator_type>::template
@@ -750,7 +797,16 @@
_LIBCPP_INLINE_VISIBILITY
unordered_map& operator=(const unordered_map& __u)
{
+#if __cplusplus >= 201103L
__table_ = __u.__table_;
+#else
+ __table_.clear();
+ __table_.hash_function() = __u.__table_.hash_function();
+ __table_.key_eq() = __u.__table_.key_eq();
+ __table_.max_load_factor() = __u.__table_.max_load_factor();
+ __table_.__copy_assign_alloc(__u.__table_);
+ insert(__u.begin(), __u.end());
+#endif
return *this;
}
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
@@ -1132,10 +1188,10 @@
{
__node_allocator& __na = __table_.__node_alloc();
__node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first),
+ __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first),
_VSTD::forward<_A0>(__a0));
__h.get_deleter().__first_constructed = true;
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
+ __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
__h.get_deleter().__second_constructed = true;
return __h;
}
@@ -1180,9 +1236,9 @@
{
__node_allocator& __na = __table_.__node_alloc();
__node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k);
+ __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
__h.get_deleter().__first_constructed = true;
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
+ __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
__h.get_deleter().__second_constructed = true;
return _VSTD::move(__h);
}
@@ -1304,11 +1360,58 @@
typedef _Pred key_equal;
typedef _Alloc allocator_type;
typedef pair<const key_type, mapped_type> value_type;
+ typedef pair<key_type, mapped_type> __nc_value_type;
typedef value_type& reference;
typedef const value_type& const_reference;
private:
- typedef pair<key_type, mapped_type> __value_type;
+#if __cplusplus >= 201103L
+ union __value_type
+ {
+ typedef typename unordered_multimap::value_type value_type;
+ typedef typename unordered_multimap::__nc_value_type __nc_value_type;
+ value_type __cc;
+ __nc_value_type __nc;
+
+ template <class ..._Args>
+ __value_type(_Args&& ...__args)
+ : __cc(std::forward<_Args>(__args)...) {}
+
+ __value_type(const __value_type& __v)
+ : __cc(std::move(__v.__cc)) {}
+
+ __value_type(__value_type&& __v)
+ : __nc(std::move(__v.__nc)) {}
+
+ __value_type& operator=(const __value_type& __v)
+ {__nc = __v.__cc; return *this;}
+
+ __value_type& operator=(__value_type&& __v)
+ {__nc = std::move(__v.__nc); return *this;}
+
+ ~__value_type() {__cc.~value_type();}
+
+ operator const value_type& () const {return __cc;}
+ };
+#else
+ struct __value_type
+ {
+ typedef typename unordered_multimap::value_type value_type;
+ value_type __cc;
+
+ __value_type() {}
+
+ template <class _A0>
+ __value_type(const _A0& __a0)
+ : __cc(__a0) {}
+
+ template <class _A0, class _A1>
+ __value_type(const _A0& __a0, const _A1& __a1)
+ : __cc(__a0, __a1) {}
+
+ operator const value_type& () const {return __cc;}
+ };
+#endif
typedef __unordered_map_hasher<key_type, mapped_type, hasher> __hasher;
typedef __unordered_map_equal<key_type, mapped_type, key_equal> __key_equal;
typedef typename allocator_traits<allocator_type>::template
@@ -1382,7 +1485,16 @@
_LIBCPP_INLINE_VISIBILITY
unordered_multimap& operator=(const unordered_multimap& __u)
{
+#if __cplusplus >= 201103L
__table_ = __u.__table_;
+#else
+ __table_.clear();
+ __table_.hash_function() = __u.__table_.hash_function();
+ __table_.key_eq() = __u.__table_.key_eq();
+ __table_.max_load_factor() = __u.__table_.max_load_factor();
+ __table_.__copy_assign_alloc(__u.__table_);
+ insert(__u.begin(), __u.end());
+#endif
return *this;
}
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
@@ -1754,10 +1866,10 @@
{
__node_allocator& __na = __table_.__node_alloc();
__node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first),
+ __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first),
_VSTD::forward<_A0>(__a0));
__h.get_deleter().__first_constructed = true;
- __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
+ __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
__h.get_deleter().__second_constructed = true;
return __h;
}