EricWF created this revision.
EricWF added a reviewer: mclow.lists.
EricWF added a subscriber: cfe-commits.
This patch attempts to fix the undefined behavior in __hash_table by changing
the node pointer types used throughout. The pointer types are changed for raw
pointers in the current ABI and for fancy pointers in ABI V2 (since the fancy
pointer types may not be ABI compatible).
The UB in `__hash_table` arises because tree downcasts the embedded end node
and then deferences that pointer. Currently there are 2 node types in
__hash_table:
* `__hash_node_base` which contains the `__next_` pointer.
* `__hash_node` which contains `__hash_` and `__value_`.
Currently the bucket list, iterators, and `__next_` pointers store pointers to
`__hash_node` even though they all need to store `__hash_node_base` pointers.
This patch makes that change by introducing a `__next_pointer` typedef which is
a pointer to `__hash_node` in the current ABI and `__hash_node_base` afterwards.
One notable change is to the type of `__bucket_list` which used to be defined
as `unique_ptr<__node_pointer[], ...>` and is now `unique_ptr<__next_pointer[],
...>` meaning that we now allocate and deallocate different types using a
different allocator. I'm going to give this part of the change more thought
since it may introduce compatibility issues.
This change is similar to D20786.
http://reviews.llvm.org/D20787
Files:
include/__config
include/__hash_table
Index: include/__hash_table
===================================================================
--- include/__hash_table
+++ include/__hash_table
@@ -59,9 +59,38 @@
template <class _NodePtr>
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,16 +346,16 @@
_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
{
#if _LIBCPP_DEBUG_LEVEL >= 2
_LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
"Attempted to dereference a non-dereferenceable unordered container iterator");
#endif
- return pointer_traits<pointer>::pointer_to(__node_->__value_);
+ return pointer_traits<pointer>::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 <class, class, class, class> friend class __hash_table;
template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;
template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator;
@@ -380,9 +414,10 @@
{
static_assert(!is_const<typename pointer_traits<_NodePtr>::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,16 +482,16 @@
_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
{
#if _LIBCPP_DEBUG_LEVEL >= 2
_LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
"Attempted to dereference a non-dereferenceable unordered container const_iterator");
#endif
- return pointer_traits<pointer>::pointer_to(__node_->__value_);
+ return pointer_traits<pointer>::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 <class, class, class, class> friend class __hash_table;
template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator;
template <class, class, class, class, class> 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,16 +608,16 @@
_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
{
#if _LIBCPP_DEBUG_LEVEL >= 2
_LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
"Attempted to dereference a non-dereferenceable unordered container local_iterator");
#endif
- return pointer_traits<pointer>::pointer_to(__node_->__value_);
+ return pointer_traits<pointer>::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 <class, class, class, class> friend class __hash_table;
template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;
template <class> 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,16 +766,16 @@
_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
{
#if _LIBCPP_DEBUG_LEVEL >= 2
_LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
"Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
#endif
- return pointer_traits<pointer>::pointer_to(__node_->__value_);
+ return pointer_traits<pointer>::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 <class, class, class, class> friend class __hash_table;
template <class> 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 <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
template <class, class, class, class, class> 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 <class _Tp, class _Hash, class _Equal, class _Alloc>
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 <class _Tp, class _Hash, class _Equal, class _Alloc>
-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,17 +1645,18 @@
max_load_factor() = __u.max_load_factor();
if (bucket_count() != 0)
{
- __node_pointer __cache = __detach();
+ __next_pointer __cache = __detach();
#ifndef _LIBCPP_NO_EXCEPTIONS
try
{
#endif // _LIBCPP_NO_EXCEPTIONS
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,19 +1845,19 @@
__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)
{
__chash = __constrain_hash(__nd->__hash_, __bc);
__ndptr = __bucket_list_[__chash];
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,51 +1913,52 @@
__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
// false false loop
// 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;
else
break;
}
}
__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,26 +1974,26 @@
#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)
{
rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
size_type(ceil(float(size() + 1) / max_load_factor()))));
__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,19 +2019,19 @@
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)
{
__chash = __constrain_hash(__hash, __bc);
__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))
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 <class _Tp, class _Hash, class _Equal, class _Alloc>
@@ -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)
;
}
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
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
