Index: include/__config =================================================================== --- include/__config +++ include/__config @@ -43,6 +43,7 @@ #define _LIBCPP_ABI_LIST_REMOVE_NODE_POINTER_UB #define _LIBCPP_ABI_FORWARD_LIST_REMOVE_NODE_POINTER_UB #define _LIBCPP_ABI_FIX_UNORDERED_CONTAINER_SIZE_TYPE +#define _LIBCPP_ABI_FIX_UNORDERED_NODE_POINTER_UB #endif #define _LIBCPP_CONCAT1(_LIBCPP_X,_LIBCPP_Y) _LIBCPP_X##_LIBCPP_Y Index: include/__hash_table =================================================================== --- include/__hash_table +++ include/__hash_table @@ -59,9 +59,38 @@ template struct __hash_node_base { + typedef typename pointer_traits<_NodePtr>::element_type __node_type; typedef __hash_node_base __first_node; + typedef typename __rebind_pointer<_NodePtr, __first_node>::type __node_base_pointer; + typedef _NodePtr __node_pointer; + +#if defined(_LIBCPP_ABI_FIX_UNORDERED_NODE_POINTER_UB) + typedef __node_base_pointer __next_pointer; +#else + typedef typename conditional< + is_pointer<__node_pointer>::value, + __node_base_pointer, + __node_pointer>::type __next_pointer; +#endif + + __next_pointer __next_; + + _LIBCPP_INLINE_VISIBILITY + __next_pointer __ptr() { + return static_cast<__next_pointer>( + pointer_traits<__node_base_pointer>::pointer_to(*this)); + } + + _LIBCPP_INLINE_VISIBILITY + __node_pointer __upcast() { + return static_cast<__node_pointer>( + pointer_traits<__node_base_pointer>::pointer_to(*this)); + } - _NodePtr __next_; + _LIBCPP_INLINE_VISIBILITY + size_t __hash() const { + return static_cast<__node_type const&>(*this).__hash_; + } _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {} }; @@ -75,7 +104,7 @@ { typedef _Tp __node_value_type; - size_t __hash_; + size_t __hash_; __node_value_type __value_; }; @@ -218,11 +247,14 @@ typedef typename __rebind_pointer<_NodePtr, __node_base_type>::type __node_base_pointer; + typedef typename __node_base_type::__next_pointer __next_pointer; + typedef _Tp __node_value_type; typedef typename __rebind_pointer<_VoidPtr, __node_value_type>::type __node_value_type_pointer; typedef typename __rebind_pointer<_VoidPtr, const __node_value_type>::type __const_node_value_type_pointer; + private: static_assert(!is_const<__node_type>::value, "_NodePtr should never be a pointer to const"); @@ -257,9 +289,10 @@ class _LIBCPP_TYPE_VIS_ONLY __hash_iterator { typedef __hash_node_types<_NodePtr> _NodeTypes; - typedef _NodePtr __node_pointer; + typedef _NodePtr __node_pointer; + typedef typename _NodeTypes::__next_pointer __next_pointer; - __node_pointer __node_; + __next_pointer __node_; public: typedef forward_iterator_tag iterator_category; @@ -313,7 +346,7 @@ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), "Attempted to dereference a non-dereferenceable unordered container iterator"); #endif - return __node_->__value_; + return __get_np()->__value_; } _LIBCPP_INLINE_VISIBILITY pointer operator->() const @@ -322,7 +355,7 @@ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), "Attempted to dereference a non-dereferenceable unordered container iterator"); #endif - return pointer_traits::pointer_to(__node_->__value_); + return pointer_traits::pointer_to(__get_np()->__value_); } _LIBCPP_INLINE_VISIBILITY @@ -356,18 +389,19 @@ private: #if _LIBCPP_DEBUG_LEVEL >= 2 _LIBCPP_INLINE_VISIBILITY - __hash_iterator(__node_pointer __node, const void* __c) _NOEXCEPT + __hash_iterator(__next_pointer __node, const void* __c) _NOEXCEPT : __node_(__node) { __get_db()->__insert_ic(this, __c); } #else _LIBCPP_INLINE_VISIBILITY - __hash_iterator(__node_pointer __node) _NOEXCEPT + __hash_iterator(__next_pointer __node) _NOEXCEPT : __node_(__node) {} #endif - + _LIBCPP_INLINE_VISIBILITY + __node_pointer __get_np() const { return static_cast<__node_pointer>(__node_); } template friend class __hash_table; template friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; template friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; @@ -380,9 +414,10 @@ { static_assert(!is_const::element_type>::value, ""); typedef __hash_node_types<_NodePtr> _NodeTypes; - typedef _NodePtr __node_pointer; + typedef _NodePtr __node_pointer; + typedef typename _NodeTypes::__next_pointer __next_pointer; - __node_pointer __node_; + __next_pointer __node_; public: typedef __hash_iterator<_NodePtr> __non_const_iterator; @@ -447,7 +482,7 @@ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), "Attempted to dereference a non-dereferenceable unordered container const_iterator"); #endif - return __node_->__value_; + return __get_np()->__value_; } _LIBCPP_INLINE_VISIBILITY pointer operator->() const @@ -456,7 +491,7 @@ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), "Attempted to dereference a non-dereferenceable unordered container const_iterator"); #endif - return pointer_traits::pointer_to(__node_->__value_); + return pointer_traits::pointer_to(__get_np()->__value_); } _LIBCPP_INLINE_VISIBILITY @@ -490,18 +525,19 @@ private: #if _LIBCPP_DEBUG_LEVEL >= 2 _LIBCPP_INLINE_VISIBILITY - __hash_const_iterator(__node_pointer __node, const void* __c) _NOEXCEPT + __hash_const_iterator(__next_pointer __node, const void* __c) _NOEXCEPT : __node_(__node) { __get_db()->__insert_ic(this, __c); } #else _LIBCPP_INLINE_VISIBILITY - __hash_const_iterator(__node_pointer __node) _NOEXCEPT + __hash_const_iterator(__next_pointer __node) _NOEXCEPT : __node_(__node) {} #endif - + _LIBCPP_INLINE_VISIBILITY + __node_pointer __get_np() const { return static_cast<__node_pointer>(__node_); } template friend class __hash_table; template friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; template friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; @@ -512,9 +548,10 @@ class _LIBCPP_TYPE_VIS_ONLY __hash_local_iterator { typedef __hash_node_types<_NodePtr> _NodeTypes; - typedef _NodePtr __node_pointer; + typedef _NodePtr __node_pointer; + typedef typename _NodeTypes::__next_pointer __next_pointer; - __node_pointer __node_; + __next_pointer __node_; size_t __bucket_; size_t __bucket_count_; @@ -571,7 +608,7 @@ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), "Attempted to dereference a non-dereferenceable unordered container local_iterator"); #endif - return __node_->__value_; + return __get_np()->__value_; } _LIBCPP_INLINE_VISIBILITY pointer operator->() const @@ -580,7 +617,7 @@ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), "Attempted to dereference a non-dereferenceable unordered container local_iterator"); #endif - return pointer_traits::pointer_to(__node_->__value_); + return pointer_traits::pointer_to(__get_np()->__value_); } _LIBCPP_INLINE_VISIBILITY @@ -591,7 +628,7 @@ "Attempted to increment non-incrementable unordered container local_iterator"); #endif __node_ = __node_->__next_; - if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) + if (__node_ != nullptr && __constrain_hash(__get_np()->__hash_, __bucket_count_) != __bucket_) __node_ = nullptr; return *this; } @@ -616,7 +653,7 @@ private: #if _LIBCPP_DEBUG_LEVEL >= 2 _LIBCPP_INLINE_VISIBILITY - __hash_local_iterator(__node_pointer __node, size_t __bucket, + __hash_local_iterator(__next_pointer __node, size_t __bucket, size_t __bucket_count, const void* __c) _NOEXCEPT : __node_(__node), __bucket_(__bucket), @@ -628,7 +665,7 @@ } #else _LIBCPP_INLINE_VISIBILITY - __hash_local_iterator(__node_pointer __node, size_t __bucket, + __hash_local_iterator(__next_pointer __node, size_t __bucket, size_t __bucket_count) _NOEXCEPT : __node_(__node), __bucket_(__bucket), @@ -638,6 +675,8 @@ __node_ = __node_->__next_; } #endif + _LIBCPP_INLINE_VISIBILITY + __node_pointer __get_np() const { return static_cast<__node_pointer>(__node_); } template friend class __hash_table; template friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; template friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; @@ -647,9 +686,10 @@ class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator { typedef __hash_node_types<_ConstNodePtr> _NodeTypes; - typedef _ConstNodePtr __node_pointer; + typedef _ConstNodePtr __node_pointer; + typedef typename _NodeTypes::__next_pointer __next_pointer; - __node_pointer __node_; + __next_pointer __node_; size_t __bucket_; size_t __bucket_count_; @@ -726,7 +766,7 @@ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), "Attempted to dereference a non-dereferenceable unordered container const_local_iterator"); #endif - return __node_->__value_; + return __get_np()->__value_; } _LIBCPP_INLINE_VISIBILITY pointer operator->() const @@ -735,7 +775,7 @@ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), "Attempted to dereference a non-dereferenceable unordered container const_local_iterator"); #endif - return pointer_traits::pointer_to(__node_->__value_); + return pointer_traits::pointer_to(__get_np()->__value_); } _LIBCPP_INLINE_VISIBILITY @@ -746,7 +786,7 @@ "Attempted to increment non-incrementable unordered container const_local_iterator"); #endif __node_ = __node_->__next_; - if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) + if (__node_ != nullptr && __constrain_hash(__get_np()->__hash_, __bucket_count_) != __bucket_) __node_ = nullptr; return *this; } @@ -771,7 +811,7 @@ private: #if _LIBCPP_DEBUG_LEVEL >= 2 _LIBCPP_INLINE_VISIBILITY - __hash_const_local_iterator(__node_pointer __node, size_t __bucket, + __hash_const_local_iterator(__next_pointer __node, size_t __bucket, size_t __bucket_count, const void* __c) _NOEXCEPT : __node_(__node), __bucket_(__bucket), @@ -783,7 +823,7 @@ } #else _LIBCPP_INLINE_VISIBILITY - __hash_const_local_iterator(__node_pointer __node, size_t __bucket, + __hash_const_local_iterator(__next_pointer __node, size_t __bucket, size_t __bucket_count) _NOEXCEPT : __node_(__node), __bucket_(__bucket), @@ -793,6 +833,8 @@ __node_ = __node_->__next_; } #endif + _LIBCPP_INLINE_VISIBILITY + __node_pointer __get_np() const { return static_cast<__node_pointer>(__node_); } template friend class __hash_table; template friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; }; @@ -926,6 +968,7 @@ typedef typename _NodeTypes::__node_pointer __node_const_pointer; typedef typename _NodeTypes::__node_base_type __first_node; typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; + typedef typename _NodeTypes::__next_pointer __next_pointer; private: // check for sane allocator pointer rebinding semantics. Rebinding the @@ -941,11 +984,11 @@ private: - typedef typename __rebind_alloc_helper<__node_traits, __node_pointer>::type __pointer_allocator; + typedef typename __rebind_alloc_helper<__node_traits, __next_pointer>::type __pointer_allocator; typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter; - typedef unique_ptr<__node_pointer[], __bucket_list_deleter> __bucket_list; + typedef unique_ptr<__next_pointer[], __bucket_list_deleter> __bucket_list; typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits; - typedef typename __bucket_list_deleter::pointer __node_pointer_pointer; + typedef typename __bucket_list_deleter::pointer __node_pointer_pointer; // --- Member data begin --- __bucket_list __bucket_list_; @@ -1346,8 +1389,8 @@ void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {} #endif // _LIBCPP_CXX03_LANG - void __deallocate(__node_pointer __np) _NOEXCEPT; - __node_pointer __detach() _NOEXCEPT; + void __deallocate(__next_pointer __np) _NOEXCEPT; + __next_pointer __detach() _NOEXCEPT; template friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; template friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; @@ -1438,8 +1481,8 @@ { if (size() > 0) { - __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = - static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); + __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = + __p1_.first().__ptr(); __u.__p1_.first().__next_ = nullptr; __u.size() = 0; } @@ -1462,8 +1505,8 @@ { __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>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); + __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = + __p1_.first().__ptr(); size() = __u.size(); __u.size() = 0; } @@ -1513,13 +1556,13 @@ template void -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np) +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__next_pointer __np) _NOEXCEPT { __node_allocator& __na = __node_alloc(); while (__np != nullptr) { - __node_pointer __next = __np->__next_; + __next_pointer __next = __np->__next_; #if _LIBCPP_DEBUG_LEVEL >= 2 __c_node* __c = __get_db()->__find_c_and_lock(this); for (__i_node** __p = __c->end_; __p != __c->beg_; ) @@ -1535,21 +1578,22 @@ } __get_db()->unlock(); #endif - __node_traits::destroy(__na, _NodeTypes::__get_ptr(__np->__value_)); - __node_traits::deallocate(__na, __np, 1); + __node_pointer __real_np = __np->__upcast(); + __node_traits::destroy(__na, _NodeTypes::__get_ptr(__real_np->__value_)); + __node_traits::deallocate(__na, __real_np, 1); __np = __next; } } template -typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer +typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer __hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT { size_type __bc = bucket_count(); for (size_type __i = 0; __i < __bc; ++__i) __bucket_list_[__i] = nullptr; size() = 0; - __node_pointer __cache = __p1_.first().__next_; + __next_pointer __cache = __p1_.first().__next_; __p1_.first().__next_ = nullptr; return __cache; } @@ -1577,8 +1621,8 @@ __p1_.first().__next_ = __u.__p1_.first().__next_; if (size() > 0) { - __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = - static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); + __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = + __p1_.first().__ptr(); __u.__p1_.first().__next_ = nullptr; __u.size() = 0; } @@ -1601,7 +1645,7 @@ max_load_factor() = __u.max_load_factor(); if (bucket_count() != 0) { - __node_pointer __cache = __detach(); + __next_pointer __cache = __detach(); #ifndef _LIBCPP_NO_EXCEPTIONS try { @@ -1609,9 +1653,10 @@ const_iterator __i = __u.begin(); while (__cache != nullptr && __u.size() != 0) { - __cache->__value_ = _VSTD::move(__u.remove(__i++)->__value_); - __node_pointer __next = __cache->__next_; - __node_insert_multi(__cache); + __cache->__upcast()->__value_ = + _VSTD::move(__u.remove(__i++)->__value_); + __next_pointer __next = __cache->__next_; + __node_insert_multi(__cache->__upcast()); __cache = __next; } #ifndef _LIBCPP_NO_EXCEPTIONS @@ -1664,16 +1709,16 @@ if (bucket_count() != 0) { - __node_pointer __cache = __detach(); + __next_pointer __cache = __detach(); #ifndef _LIBCPP_NO_EXCEPTIONS try { #endif // _LIBCPP_NO_EXCEPTIONS for (; __cache != nullptr && __first != __last; ++__first) { - __cache->__value_ = *__first; - __node_pointer __next = __cache->__next_; - __node_insert_unique(__cache); + __cache->__upcast()->__value_ = *__first; + __next_pointer __next = __cache->__next_; + __node_insert_unique(__cache->__upcast()); __cache = __next; } #ifndef _LIBCPP_NO_EXCEPTIONS @@ -1704,16 +1749,16 @@ " or the nodes value type"); if (bucket_count() != 0) { - __node_pointer __cache = __detach(); + __next_pointer __cache = __detach(); #ifndef _LIBCPP_NO_EXCEPTIONS try { #endif // _LIBCPP_NO_EXCEPTIONS for (; __cache != nullptr && __first != __last; ++__first) { - __cache->__value_ = *__first; - __node_pointer __next = __cache->__next_; - __node_insert_multi(__cache); + __cache->__upcast()->__value_ = *__first; + __next_pointer __next = __cache->__next_; + __node_insert_multi(__cache->__upcast()); __cache = __next; } #ifndef _LIBCPP_NO_EXCEPTIONS @@ -1800,7 +1845,7 @@ __nd->__hash_ = hash_function()(__nd->__value_); size_type __bc = bucket_count(); bool __inserted = false; - __node_pointer __ndptr; + __next_pointer __ndptr; size_t __chash; if (__bc != 0) { @@ -1809,10 +1854,10 @@ if (__ndptr != nullptr) { for (__ndptr = __ndptr->__next_; __ndptr != nullptr && - __constrain_hash(__ndptr->__hash_, __bc) == __chash; + __constrain_hash(__ndptr->__hash(), __bc) == __chash; __ndptr = __ndptr->__next_) { - if (key_eq()(__ndptr->__value_, __nd->__value_)) + if (key_eq()(__ndptr->__upcast()->__value_, __nd->__value_)) goto __done; } } @@ -1826,23 +1871,23 @@ __chash = __constrain_hash(__nd->__hash_, __bc); } // insert_after __bucket_list_[__chash], or __first_node if bucket is null - __node_pointer __pn = __bucket_list_[__chash]; + __next_pointer __pn = __bucket_list_[__chash]; if (__pn == nullptr) { - __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); + __pn =__p1_.first().__ptr(); __nd->__next_ = __pn->__next_; - __pn->__next_ = __nd; + __pn->__next_ = __nd->__ptr(); // fix up __bucket_list_ __bucket_list_[__chash] = __pn; if (__nd->__next_ != nullptr) - __bucket_list_[__constrain_hash(__nd->__next_->__hash_, __bc)] = __nd; + __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr(); } else { __nd->__next_ = __pn->__next_; - __pn->__next_ = __nd; + __pn->__next_ = __nd->__ptr(); } - __ndptr = __nd; + __ndptr = __nd->__ptr(); // increment size ++size(); __inserted = true; @@ -1868,21 +1913,22 @@ __bc = bucket_count(); } size_t __chash = __constrain_hash(__cp->__hash_, __bc); - __node_pointer __pn = __bucket_list_[__chash]; + __next_pointer __pn = __bucket_list_[__chash]; if (__pn == nullptr) { - __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); + __pn =__p1_.first().__ptr(); __cp->__next_ = __pn->__next_; - __pn->__next_ = __cp; + __pn->__next_ = __cp->__ptr(); // fix up __bucket_list_ __bucket_list_[__chash] = __pn; if (__cp->__next_ != nullptr) - __bucket_list_[__constrain_hash(__cp->__next_->__hash_, __bc)] = __cp; + __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)] + = __cp->__ptr(); } else { for (bool __found = false; __pn->__next_ != nullptr && - __constrain_hash(__pn->__next_->__hash_, __bc) == __chash; + __constrain_hash(__pn->__next_->__hash(), __bc) == __chash; __pn = __pn->__next_) { // __found key_eq() action @@ -1890,8 +1936,8 @@ // true true loop // false true set __found to true // true false break - if (__found != (__pn->__next_->__hash_ == __cp->__hash_ && - key_eq()(__pn->__next_->__value_, __cp->__value_))) + if (__found != (__pn->__next_->__hash() == __cp->__hash_ && + key_eq()(__pn->__next_->__upcast()->__value_, __cp->__value_))) { if (!__found) __found = true; @@ -1900,19 +1946,19 @@ } } __cp->__next_ = __pn->__next_; - __pn->__next_ = __cp; + __pn->__next_ = __cp->__ptr(); if (__cp->__next_ != nullptr) { - size_t __nhash = __constrain_hash(__cp->__next_->__hash_, __bc); + size_t __nhash = __constrain_hash(__cp->__next_->__hash(), __bc); if (__nhash != __chash) - __bucket_list_[__nhash] = __cp; + __bucket_list_[__nhash] = __cp->__ptr(); } } ++size(); #if _LIBCPP_DEBUG_LEVEL >= 2 - return iterator(__cp, this); + return iterator(__cp->__ptr(), this); #else - return iterator(__cp); + return iterator(__cp->__ptr()); #endif } @@ -1928,8 +1974,8 @@ #endif if (__p != end() && key_eq()(*__p, __cp->__value_)) { - __node_pointer __np = __p.__node_; - __cp->__hash_ = __np->__hash_; + __next_pointer __np = __p.__node_; + __cp->__hash_ = __np->__hash(); size_type __bc = bucket_count(); if (size()+1 > __bc * max_load_factor() || __bc == 0) { @@ -1938,16 +1984,16 @@ __bc = bucket_count(); } size_t __chash = __constrain_hash(__cp->__hash_, __bc); - __node_pointer __pp = __bucket_list_[__chash]; + __next_pointer __pp = __bucket_list_[__chash]; while (__pp->__next_ != __np) __pp = __pp->__next_; __cp->__next_ = __np; - __pp->__next_ = __cp; + __pp->__next_ = static_cast<__next_pointer>(__cp); ++size(); #if _LIBCPP_DEBUG_LEVEL >= 2 - return iterator(__cp, this); + return iterator(static_cast<__next_pointer>(__cp), this); #else - return iterator(__cp); + return iterator(static_cast<__next_pointer>(__cp)); #endif } return __node_insert_multi(__cp); @@ -1973,7 +2019,7 @@ size_t __hash = hash_function()(__k); size_type __bc = bucket_count(); bool __inserted = false; - __node_pointer __nd; + __next_pointer __nd; size_t __chash; if (__bc != 0) { @@ -1982,10 +2028,10 @@ if (__nd != nullptr) { for (__nd = __nd->__next_; __nd != nullptr && - __constrain_hash(__nd->__hash_, __bc) == __chash; + __constrain_hash(__nd->__hash(), __bc) == __chash; __nd = __nd->__next_) { - if (key_eq()(__nd->__value_, __k)) + if (key_eq()(__nd->__upcast()->__value_, __k)) goto __done; } } @@ -2004,23 +2050,24 @@ __chash = __constrain_hash(__hash, __bc); } // insert_after __bucket_list_[__chash], or __first_node if bucket is null - __node_pointer __pn = __bucket_list_[__chash]; + __next_pointer __pn = __bucket_list_[__chash]; if (__pn == nullptr) { - __pn = static_cast<__node_pointer>(static_cast<__void_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()))); + __pn = __p1_.first().__ptr(); __h->__next_ = __pn->__next_; - __pn->__next_ = __h.get(); + __pn->__next_ = __h.get()->__ptr(); // fix up __bucket_list_ __bucket_list_[__chash] = __pn; if (__h->__next_ != nullptr) - __bucket_list_[__constrain_hash(__h->__next_->__hash_, __bc)] = __h.get(); + __bucket_list_[__constrain_hash(__h->__next_->__hash(), __bc)] + = __h.get()->__ptr(); } else { __h->__next_ = __pn->__next_; - __pn->__next_ = __h.get(); + __pn->__next_ = static_cast<__next_pointer>(__h.get()); } - __nd = __h.release(); + __nd = static_cast<__next_pointer>(__h.release()); // increment size ++size(); __inserted = true; @@ -2144,17 +2191,17 @@ { for (size_type __i = 0; __i < __nbc; ++__i) __bucket_list_[__i] = nullptr; - __node_pointer __pp(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()))); - __node_pointer __cp = __pp->__next_; + __next_pointer __pp = __p1_.first().__ptr(); + __next_pointer __cp = __pp->__next_; if (__cp != nullptr) { - size_type __chash = __constrain_hash(__cp->__hash_, __nbc); + size_type __chash = __constrain_hash(__cp->__hash(), __nbc); __bucket_list_[__chash] = __pp; size_type __phash = __chash; for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr; __cp = __pp->__next_) { - __chash = __constrain_hash(__cp->__hash_, __nbc); + __chash = __constrain_hash(__cp->__hash(), __nbc); if (__chash == __phash) __pp = __cp; else @@ -2167,9 +2214,10 @@ } else { - __node_pointer __np = __cp; + __next_pointer __np = __cp; for (; __np->__next_ != nullptr && - key_eq()(__cp->__value_, __np->__next_->__value_); + key_eq()(__cp->__upcast()->__value_, + __np->__next_->__upcast()->__value_); __np = __np->__next_) ; __pp->__next_ = __np->__next_; @@ -2193,14 +2241,14 @@ if (__bc != 0) { size_t __chash = __constrain_hash(__hash, __bc); - __node_pointer __nd = __bucket_list_[__chash]; + __next_pointer __nd = __bucket_list_[__chash]; if (__nd != nullptr) { for (__nd = __nd->__next_; __nd != nullptr && - __constrain_hash(__nd->__hash_, __bc) == __chash; + __constrain_hash(__nd->__hash(), __bc) == __chash; __nd = __nd->__next_) { - if (key_eq()(__nd->__value_, __k)) + if (key_eq()(__nd->__upcast()->__value_, __k)) #if _LIBCPP_DEBUG_LEVEL >= 2 return iterator(__nd, this); #else @@ -2222,14 +2270,14 @@ if (__bc != 0) { size_t __chash = __constrain_hash(__hash, __bc); - __node_const_pointer __nd = __bucket_list_[__chash]; + __next_pointer __nd = __bucket_list_[__chash]; if (__nd != nullptr) { for (__nd = __nd->__next_; __nd != nullptr && - __constrain_hash(__nd->__hash_, __bc) == __chash; + __constrain_hash(__nd->__hash(), __bc) == __chash; __nd = __nd->__next_) { - if (key_eq()(__nd->__value_, __k)) + if (key_eq()(__nd->__upcast()->__value_, __k)) #if _LIBCPP_DEBUG_LEVEL >= 2 return const_iterator(__nd, this); #else @@ -2314,7 +2362,7 @@ typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) { - __node_pointer __np = __p.__node_; + __next_pointer __np = __p.__node_; #if _LIBCPP_DEBUG_LEVEL >= 2 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, "unordered container erase(iterator) called with an iterator not" @@ -2348,7 +2396,7 @@ ++__first; erase(__p); } - __node_pointer __np = __last.__node_; + __next_pointer __np = __last.__node_; #if _LIBCPP_DEBUG_LEVEL >= 2 return iterator (__np, this); #else @@ -2392,26 +2440,27 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT { // current node - __node_pointer __cn = __p.__node_; + __next_pointer __cn = __p.__node_; size_type __bc = bucket_count(); - size_t __chash = __constrain_hash(__cn->__hash_, __bc); + size_t __chash = __constrain_hash(__cn->__hash(), __bc); // find previous node - __node_pointer __pn = __bucket_list_[__chash]; + __next_pointer __pn = __bucket_list_[__chash]; for (; __pn->__next_ != __cn; __pn = __pn->__next_) ; // 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 == static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())) - || __constrain_hash(__pn->__hash_, __bc) != __chash) + if (__pn == __p1_.first().__ptr() + || __constrain_hash(__pn->__hash(), __bc) != __chash) { - if (__cn->__next_ == nullptr || __constrain_hash(__cn->__next_->__hash_, __bc) != __chash) + if (__cn->__next_ == nullptr + || __constrain_hash(__cn->__next_->__hash(), __bc) != __chash) __bucket_list_[__chash] = nullptr; } // if __cn->__next_ is not in same bucket (nullptr is in same bucket) if (__cn->__next_ != nullptr) { - size_t __nhash = __constrain_hash(__cn->__next_->__hash_, __bc); + size_t __nhash = __constrain_hash(__cn->__next_->__hash(), __bc); if (__nhash != __chash) __bucket_list_[__nhash] = __pn; } @@ -2434,7 +2483,7 @@ } __get_db()->unlock(); #endif - return __node_holder(__cn, _Dp(__node_alloc(), true)); + return __node_holder(__cn->__upcast(), _Dp(__node_alloc(), true)); } template @@ -2561,11 +2610,11 @@ __p2_.swap(__u.__p2_); __p3_.swap(__u.__p3_); if (size() > 0) - __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = - static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); + __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = + __p1_.first().__ptr(); if (__u.size() > 0) - __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] = - static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__u.__p1_.first())); + __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash(), __u.bucket_count())] = + __u.__p1_.first().__ptr(); #if _LIBCPP_DEBUG_LEVEL >= 2 __get_db()->swap(this, &__u); #endif @@ -2577,13 +2626,13 @@ { _LIBCPP_ASSERT(__n < bucket_count(), "unordered container::bucket_size(n) called with n >= bucket_count()"); - __node_const_pointer __np = __bucket_list_[__n]; + __next_pointer __np = __bucket_list_[__n]; size_type __bc = bucket_count(); size_type __r = 0; if (__np != nullptr) { for (__np = __np->__next_; __np != nullptr && - __constrain_hash(__np->__hash_, __bc) == __n; + __constrain_hash(__np->__hash(), __bc) == __n; __np = __np->__next_, ++__r) ; }