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 __tree 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 `__tree` arises because tree downcasts the embedded end node and then
deferences that pointer. Currently there are 3 node types in __tree.
* `__tree_end_node` which contains the `__left_` pointer. This node is embedded
within the container.
* `__tree_node_base` which contains `__right_`, `__parent_` and `__is_black`.
This node is used throughout the tree rebalancing algorithms.
* `__tree_node` which contains `__value_`.
Currently both `__tree` stores the start of the tree, `__begin_node_`, as a
pointer to a `__tree_node`. Additionally the iterators store their position as
a pointer to a `__tree_node`. In both of these cases the pointee can be the end
node. This is fixed by changing them to store `__tree_end_node` pointers
instead.
To make this change I introduced an `__iter_pointer` typedef which is defined
to be a pointer to either `__tree_end_node` in the new ABI or `__tree_node` in
the current one.
Both `__tree::__begin_node_` and iterator pointers are now stored as
`__iter_pointers`.
The other situation where `__tree_end_node` is stored as a pointer to the wrong
type is as the `__parent_` pointer within another node. Currently `__left_`,
`__right_`, and `__parent_` are all `__tree_base_node` pointers. Since the end
node will only be stored in `__parent_` the fix is to change `__parent_` to be
a pointer to `__tree_end_node`.
To make this change I introduced a `__parent_pointer` typedef which is defined
to be a pointer to either `__tree_node_base` in the new ABI or `__tree_node` in
the current one.
Note that in the new ABI `__iter_pointer` and `__parent_pointer` are the same
type (but not the old one). The confusion between these two types is
unfortunate but it was the best solution I could come up with that maintains
the ABI.
The typedef changes force a ton of explicit type casts to correct pointer types
and to make current code compatible with both the old and new pointer typedefs.
This is the bulk of the change and it's really messy. Unfortunately I don't
know how to avoid it.
Please let me know what you think.
http://reviews.llvm.org/D20786
Files:
include/__config
include/__tree
Index: include/__tree
===================================================================
--- include/__tree
+++ include/__tree
@@ -165,21 +165,33 @@
if (__x->__right_ != nullptr)
return __tree_min(__x->__right_);
while (!__tree_is_left_child(__x))
- __x = __x->__parent_;
- return __x->__parent_;
+ __x = __x->__parent_unsafe();
+ return __x->__parent_unsafe();
+}
+
+template <class _NodeBasePtr, class _NodePtr>
+_NodeBasePtr
+__tree_next_iter(_NodePtr __x) _NOEXCEPT
+{
+ if (__x->__right_ != nullptr)
+ return static_cast<_NodeBasePtr>(__tree_min(__x->__right_));
+ while (!__tree_is_left_child(__x))
+ __x = __x->__parent_unsafe();
+ return __x->__parent_; // decltype(__parent_) == _NodeBasePtr
}
// Returns: pointer to the previous in-order node before __x.
// Precondition: __x != nullptr.
-template <class _NodePtr>
+template <class _NodePtr, class _NodeBasePtr>
_NodePtr
-__tree_prev(_NodePtr __x) _NOEXCEPT
+__tree_prev_iter(_NodeBasePtr __x) _NOEXCEPT
{
if (__x->__left_ != nullptr)
return __tree_max(__x->__left_);
- while (__tree_is_left_child(__x))
- __x = __x->__parent_;
- return __x->__parent_;
+ _NodePtr __xx = static_cast<_NodePtr>(__x);
+ while (__tree_is_left_child(__xx))
+ __xx = __xx->__parent_unsafe();
+ return __xx->__parent_unsafe();
}
// Returns: pointer to a node which has no children
@@ -215,14 +227,14 @@
_NodePtr __y = __x->__right_;
__x->__right_ = __y->__left_;
if (__x->__right_ != nullptr)
- __x->__right_->__parent_ = __x;
+ __x->__right_->__set_parent(__x);
__y->__parent_ = __x->__parent_;
if (__tree_is_left_child(__x))
__x->__parent_->__left_ = __y;
else
- __x->__parent_->__right_ = __y;
+ __x->__parent_unsafe()->__right_ = __y;
__y->__left_ = __x;
- __x->__parent_ = __y;
+ __x->__set_parent(__y);
}
// Effects: Makes __x->__left_ the subtree root with __x as its right child
@@ -235,14 +247,14 @@
_NodePtr __y = __x->__left_;
__x->__left_ = __y->__right_;
if (__x->__left_ != nullptr)
- __x->__left_->__parent_ = __x;
+ __x->__left_->__set_parent(__x);
__y->__parent_ = __x->__parent_;
if (__tree_is_left_child(__x))
__x->__parent_->__left_ = __y;
else
- __x->__parent_->__right_ = __y;
+ __x->__parent_unsafe()->__right_ = __y;
__y->__right_ = __x;
- __x->__parent_ = __y;
+ __x->__set_parent(__y);
}
// Effects: Rebalances __root after attaching __x to a leaf.
@@ -258,56 +270,56 @@
__tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT
{
__x->__is_black_ = __x == __root;
- while (__x != __root && !__x->__parent_->__is_black_)
+ while (__x != __root && !__x->__parent_unsafe()->__is_black_)
{
// __x->__parent_ != __root because __x->__parent_->__is_black == false
- if (__tree_is_left_child(__x->__parent_))
+ if (__tree_is_left_child(__x->__parent_unsafe()))
{
- _NodePtr __y = __x->__parent_->__parent_->__right_;
+ _NodePtr __y = __x->__parent_unsafe()->__parent_unsafe()->__right_;
if (__y != nullptr && !__y->__is_black_)
{
- __x = __x->__parent_;
+ __x = __x->__parent_unsafe();
__x->__is_black_ = true;
- __x = __x->__parent_;
+ __x = __x->__parent_unsafe();
__x->__is_black_ = __x == __root;
__y->__is_black_ = true;
}
else
{
if (!__tree_is_left_child(__x))
{
- __x = __x->__parent_;
+ __x = __x->__parent_unsafe();
__tree_left_rotate(__x);
}
- __x = __x->__parent_;
+ __x = __x->__parent_unsafe();
__x->__is_black_ = true;
- __x = __x->__parent_;
+ __x = __x->__parent_unsafe();
__x->__is_black_ = false;
__tree_right_rotate(__x);
break;
}
}
else
{
- _NodePtr __y = __x->__parent_->__parent_->__left_;
+ _NodePtr __y = __x->__parent_unsafe()->__parent_->__left_;
if (__y != nullptr && !__y->__is_black_)
{
- __x = __x->__parent_;
+ __x = __x->__parent_unsafe();
__x->__is_black_ = true;
- __x = __x->__parent_;
+ __x = __x->__parent_unsafe();
__x->__is_black_ = __x == __root;
__y->__is_black_ = true;
}
else
{
if (__tree_is_left_child(__x))
{
- __x = __x->__parent_;
+ __x = __x->__parent_unsafe();
__tree_right_rotate(__x);
}
- __x = __x->__parent_;
+ __x = __x->__parent_unsafe();
__x->__is_black_ = true;
- __x = __x->__parent_;
+ __x = __x->__parent_unsafe();
__x->__is_black_ = false;
__tree_left_rotate(__x);
break;
@@ -344,13 +356,13 @@
{
__y->__parent_->__left_ = __x;
if (__y != __root)
- __w = __y->__parent_->__right_;
+ __w = __y->__parent_unsafe()->__right_;
else
__root = __x; // __w == nullptr
}
else
{
- __y->__parent_->__right_ = __x;
+ __y->__parent_unsafe()->__right_ = __x;
// __y can't be root if it is a right child
__w = __y->__parent_->__left_;
}
@@ -364,12 +376,12 @@
if (__tree_is_left_child(__z))
__y->__parent_->__left_ = __y;
else
- __y->__parent_->__right_ = __y;
+ __y->__parent_unsafe()->__right_ = __y;
__y->__left_ = __z->__left_;
- __y->__left_->__parent_ = __y;
+ __y->__left_->__set_parent(__y);
__y->__right_ = __z->__right_;
if (__y->__right_ != nullptr)
- __y->__right_->__parent_ = __y;
+ __y->__right_->__set_parent(__y);
__y->__is_black_ = __z->__is_black_;
if (__root == __z)
__root = __y;
@@ -406,8 +418,8 @@
if (!__w->__is_black_)
{
__w->__is_black_ = true;
- __w->__parent_->__is_black_ = false;
- __tree_left_rotate(__w->__parent_);
+ __w->__parent_unsafe()->__is_black_ = false;
+ __tree_left_rotate(__w->__parent_unsafe());
// __x is still valid
// reset __root only if necessary
if (__root == __w->__left_)
@@ -420,16 +432,16 @@
(__w->__right_ == nullptr || __w->__right_->__is_black_))
{
__w->__is_black_ = false;
- __x = __w->__parent_;
+ __x = __w->__parent_unsafe();
// __x can no longer be null
if (__x == __root || !__x->__is_black_)
{
__x->__is_black_ = true;
break;
}
// reset sibling, and it still can't be null
__w = __tree_is_left_child(__x) ?
- __x->__parent_->__right_ :
+ __x->__parent_unsafe()->__right_ :
__x->__parent_->__left_;
// continue;
}
@@ -443,23 +455,23 @@
__tree_right_rotate(__w);
// __w is known not to be root, so root hasn't changed
// reset sibling, and it still can't be null
- __w = __w->__parent_;
+ __w = __w->__parent_unsafe();
}
// __w has a right red child, left child may be null
- __w->__is_black_ = __w->__parent_->__is_black_;
- __w->__parent_->__is_black_ = true;
+ __w->__is_black_ = __w->__parent_unsafe()->__is_black_;
+ __w->__parent_unsafe()->__is_black_ = true;
__w->__right_->__is_black_ = true;
- __tree_left_rotate(__w->__parent_);
+ __tree_left_rotate(__w->__parent_unsafe());
break;
}
}
else
{
if (!__w->__is_black_)
{
__w->__is_black_ = true;
- __w->__parent_->__is_black_ = false;
- __tree_right_rotate(__w->__parent_);
+ __w->__parent_unsafe()->__is_black_ = false;
+ __tree_right_rotate(__w->__parent_unsafe());
// __x is still valid
// reset __root only if necessary
if (__root == __w->__right_)
@@ -472,16 +484,16 @@
(__w->__right_ == nullptr || __w->__right_->__is_black_))
{
__w->__is_black_ = false;
- __x = __w->__parent_;
+ __x = __w->__parent_unsafe();
// __x can no longer be null
if (!__x->__is_black_ || __x == __root)
{
__x->__is_black_ = true;
break;
}
// reset sibling, and it still can't be null
__w = __tree_is_left_child(__x) ?
- __x->__parent_->__right_ :
+ __x->__parent_unsafe()->__right_ :
__x->__parent_->__left_;
// continue;
}
@@ -495,13 +507,13 @@
__tree_left_rotate(__w);
// __w is known not to be root, so root hasn't changed
// reset sibling, and it still can't be null
- __w = __w->__parent_;
+ __w = __w->__parent_unsafe();
}
// __w has a left red child, right child may be null
- __w->__is_black_ = __w->__parent_->__is_black_;
- __w->__parent_->__is_black_ = true;
+ __w->__is_black_ = __w->__parent_unsafe()->__is_black_;
+ __w->__parent_unsafe()->__is_black_ = true;
__w->__left_->__is_black_ = true;
- __tree_right_rotate(__w->__parent_);
+ __tree_right_rotate(__w->__parent_unsafe());
break;
}
}
@@ -617,6 +629,15 @@
typedef __tree_end_node<__node_base_pointer> __end_node_type;
typedef typename __rebind_pointer<_VoidPtr, __end_node_type>::type
__end_node_pointer;
+#if defined(_LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB)
+ typedef __end_node_pointer __parent_pointer;
+#else
+ typedef typename conditional<
+ is_pointer<__end_node_pointer>::value,
+ __end_node_pointer,
+ __node_base_pointer>::type __parent_pointer;
+#endif
+
private:
static_assert((is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value),
"_VoidPtr does not point to unqualified void type");
@@ -657,6 +678,14 @@
__node_value_type_pointer;
typedef typename __rebind_pointer<_VoidPtr, const __node_value_type>::type
__const_node_value_type_pointer;
+#if defined(_LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB)
+ typedef typename __base::__end_node_pointer __iter_pointer;
+#else
+ typedef typename conditional<
+ is_pointer<__node_pointer>::value,
+ typename __base::__end_node_pointer,
+ __node_pointer>::type __iter_pointer;
+#endif
private:
static_assert(!is_const<__node_type>::value,
"_NodePtr should never be a pointer to const");
@@ -692,11 +721,20 @@
public:
typedef typename _NodeBaseTypes::__node_base_pointer pointer;
+ typedef typename _NodeBaseTypes::__parent_pointer __parent_pointer;
- pointer __right_;
- pointer __parent_;
+ pointer __right_;
+ __parent_pointer __parent_;
bool __is_black_;
+ _LIBCPP_INLINE_VISIBILITY
+ pointer __parent_unsafe() const { return static_cast<pointer>(__parent_);}
+
+ _LIBCPP_INLINE_VISIBILITY
+ void __set_parent(pointer __p) {
+ __parent_ = static_cast<__parent_pointer>(__p);
+ }
+
private:
~__tree_node_base() _LIBCPP_EQUAL_DELETE;
__tree_node_base(__tree_node_base const&) _LIBCPP_EQUAL_DELETE;
@@ -761,9 +799,11 @@
typedef __tree_node_types<_NodePtr> _NodeTypes;
typedef _NodePtr __node_pointer;
typedef typename _NodeTypes::__node_base_pointer __node_base_pointer;
+ typedef typename _NodeTypes::__end_node_pointer __end_node_pointer;
+ typedef typename _NodeTypes::__iter_pointer __iter_pointer;
typedef pointer_traits<__node_pointer> __pointer_traits;
- __node_pointer __ptr_;
+ __iter_pointer __ptr_;
public:
typedef bidirectional_iterator_tag iterator_category;
@@ -778,24 +818,25 @@
#endif
{}
- _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;}
+ _LIBCPP_INLINE_VISIBILITY reference operator*() const
+ {return __get_np()->__value_;}
_LIBCPP_INLINE_VISIBILITY pointer operator->() const
- {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);}
+ {return pointer_traits<pointer>::pointer_to(__get_np()->__value_);}
_LIBCPP_INLINE_VISIBILITY
__tree_iterator& operator++() {
- __ptr_ = static_cast<__node_pointer>(
- __tree_next(static_cast<__node_base_pointer>(__ptr_)));
+ __ptr_ = static_cast<__iter_pointer>(
+ __tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_)));
return *this;
}
_LIBCPP_INLINE_VISIBILITY
__tree_iterator operator++(int)
{__tree_iterator __t(*this); ++(*this); return __t;}
_LIBCPP_INLINE_VISIBILITY
__tree_iterator& operator--() {
- __ptr_ = static_cast<__node_pointer>(
- __tree_prev(static_cast<__node_base_pointer>(__ptr_)));
+ __ptr_ = static_cast<__iter_pointer>(__tree_prev_iter<__node_base_pointer>(
+ static_cast<__end_node_pointer>(__ptr_)));
return *this;
}
_LIBCPP_INLINE_VISIBILITY
@@ -812,6 +853,9 @@
private:
_LIBCPP_INLINE_VISIBILITY
explicit __tree_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
+ explicit __tree_iterator(__end_node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
+ _LIBCPP_INLINE_VISIBILITY
+ __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); }
template <class, class, class> friend class __tree;
template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator;
template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_iterator;
@@ -827,9 +871,11 @@
typedef __tree_node_types<_NodePtr> _NodeTypes;
typedef typename _NodeTypes::__node_pointer __node_pointer;
typedef typename _NodeTypes::__node_base_pointer __node_base_pointer;
+ typedef typename _NodeTypes::__end_node_pointer __end_node_pointer;
+ typedef typename _NodeTypes::__iter_pointer __iter_pointer;
typedef pointer_traits<__node_pointer> __pointer_traits;
- __node_pointer __ptr_;
+ __iter_pointer __ptr_;
public:
typedef bidirectional_iterator_tag iterator_category;
@@ -852,14 +898,15 @@
__tree_const_iterator(__non_const_iterator __p) _NOEXCEPT
: __ptr_(__p.__ptr_) {}
- _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;}
+ _LIBCPP_INLINE_VISIBILITY reference operator*() const
+ {return __get_np()->__value_;}
_LIBCPP_INLINE_VISIBILITY pointer operator->() const
- {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);}
+ {return pointer_traits<pointer>::pointer_to(__get_np()->__value_);}
_LIBCPP_INLINE_VISIBILITY
__tree_const_iterator& operator++() {
- __ptr_ = static_cast<__node_pointer>(
- __tree_next(static_cast<__node_base_pointer>(__ptr_)));
+ __ptr_ = static_cast<__iter_pointer>(
+ __tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_)));
return *this;
}
@@ -869,8 +916,8 @@
_LIBCPP_INLINE_VISIBILITY
__tree_const_iterator& operator--() {
- __ptr_ = static_cast<__node_pointer>(
- __tree_prev(static_cast<__node_base_pointer>(__ptr_)));
+ __ptr_ = static_cast<__iter_pointer>(__tree_prev_iter<__node_base_pointer>(
+ static_cast<__end_node_pointer>(__ptr_)));
return *this;
}
@@ -889,12 +936,19 @@
_LIBCPP_INLINE_VISIBILITY
explicit __tree_const_iterator(__node_pointer __p) _NOEXCEPT
: __ptr_(__p) {}
+ _LIBCPP_INLINE_VISIBILITY
+ explicit __tree_const_iterator(__end_node_pointer __p) _NOEXCEPT
+ : __ptr_(__p) {}
+ _LIBCPP_INLINE_VISIBILITY
+ __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); }
+
template <class, class, class> friend class __tree;
template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY set;
template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multiset;
template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator;
+
};
template <class _Tp, class _Compare, class _Allocator>
@@ -932,6 +986,9 @@
typedef typename _NodeTypes::__end_node_type __end_node_t;
typedef typename _NodeTypes::__end_node_pointer __end_node_ptr;
+ typedef typename _NodeTypes::__parent_pointer __parent_pointer;
+ typedef typename _NodeTypes::__iter_pointer __iter_pointer;
+
typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator;
typedef allocator_traits<__node_allocator> __node_traits;
@@ -948,22 +1005,22 @@
"Allocator does not rebind pointers in a sane manner.");
private:
- __node_pointer __begin_node_;
+ __iter_pointer __begin_node_;
__compressed_pair<__end_node_t, __node_allocator> __pair1_;
__compressed_pair<size_type, value_compare> __pair3_;
public:
_LIBCPP_INLINE_VISIBILITY
- __node_pointer __end_node() _NOEXCEPT
+ __iter_pointer __end_node() _NOEXCEPT
{
- return static_cast<__node_pointer>(
+ return static_cast<__iter_pointer>(
pointer_traits<__end_node_ptr>::pointer_to(__pair1_.first())
);
}
_LIBCPP_INLINE_VISIBILITY
- __node_pointer __end_node() const _NOEXCEPT
+ __iter_pointer __end_node() const _NOEXCEPT
{
- return static_cast<__node_pointer>(
+ return static_cast<__iter_pointer>(
pointer_traits<__end_node_ptr>::pointer_to(
const_cast<__end_node_t&>(__pair1_.first())
)
@@ -976,9 +1033,12 @@
const __node_allocator& __node_alloc() const _NOEXCEPT
{return __pair1_.second();}
_LIBCPP_INLINE_VISIBILITY
- __node_pointer& __begin_node() _NOEXCEPT {return __begin_node_;}
+ __iter_pointer& __begin_node() _NOEXCEPT {return __begin_node_;}
+ _LIBCPP_INLINE_VISIBILITY
+ const __iter_pointer& __begin_node() const _NOEXCEPT {return __begin_node_;}
_LIBCPP_INLINE_VISIBILITY
- const __node_pointer& __begin_node() const _NOEXCEPT {return __begin_node_;}
+ __node_pointer __begin_node_downcast() const _NOEXCEPT
+ { return static_cast<__node_pointer>(__begin_node_);}
public:
_LIBCPP_INLINE_VISIBILITY
allocator_type __alloc() const _NOEXCEPT
@@ -1000,6 +1060,10 @@
__node_pointer __root() const _NOEXCEPT
{return static_cast<__node_pointer>(__end_node()->__left_);}
+ __node_base_pointer* __root_ptr() const _NOEXCEPT {
+ return _VSTD::addressof(__end_node()->__left_);
+ }
+
typedef __tree_iterator<value_type, __node_pointer, difference_type> iterator;
typedef __tree_const_iterator<value_type, __node_pointer, difference_type> const_iterator;
@@ -1257,7 +1321,7 @@
template <class _Key>
size_type __erase_multi(const _Key& __k);
- void __insert_node_at(__node_base_pointer __parent,
+ void __insert_node_at(__parent_pointer __parent,
__node_base_pointer& __child,
__node_base_pointer __new_node);
@@ -1278,31 +1342,31 @@
template <class _Key>
iterator __lower_bound(const _Key& __v,
__node_pointer __root,
- __node_pointer __result);
+ __iter_pointer __result);
template <class _Key>
_LIBCPP_INLINE_VISIBILITY
const_iterator lower_bound(const _Key& __v) const
{return __lower_bound(__v, __root(), __end_node());}
template <class _Key>
const_iterator __lower_bound(const _Key& __v,
__node_pointer __root,
- __node_pointer __result) const;
+ __iter_pointer __result) const;
template <class _Key>
_LIBCPP_INLINE_VISIBILITY
iterator upper_bound(const _Key& __v)
{return __upper_bound(__v, __root(), __end_node());}
template <class _Key>
iterator __upper_bound(const _Key& __v,
__node_pointer __root,
- __node_pointer __result);
+ __iter_pointer __result);
template <class _Key>
_LIBCPP_INLINE_VISIBILITY
const_iterator upper_bound(const _Key& __v) const
{return __upper_bound(__v, __root(), __end_node());}
template <class _Key>
const_iterator __upper_bound(const _Key& __v,
__node_pointer __root,
- __node_pointer __result) const;
+ __iter_pointer __result) const;
template <class _Key>
pair<iterator, iterator>
__equal_range_unique(const _Key& __k);
@@ -1322,19 +1386,20 @@
__node_holder remove(const_iterator __p) _NOEXCEPT;
private:
- typename __node_base::pointer&
- __find_leaf_low(typename __node_base::pointer& __parent, const key_type& __v);
- typename __node_base::pointer&
- __find_leaf_high(typename __node_base::pointer& __parent, const key_type& __v);
- typename __node_base::pointer&
+ __node_base_pointer&
+ __find_leaf_low(__parent_pointer& __parent, const key_type& __v);
+ __node_base_pointer&
+ __find_leaf_high(__parent_pointer& __parent, const key_type& __v);
+ __node_base_pointer&
__find_leaf(const_iterator __hint,
- typename __node_base::pointer& __parent, const key_type& __v);
+ __parent_pointer& __parent, const key_type& __v);
template <class _Key>
- typename __node_base::pointer&
- __find_equal(typename __node_base::pointer& __parent, const _Key& __v);
+ __node_base_pointer&
+ __find_equal(__parent_pointer& __parent, const _Key& __v);
template <class _Key>
- typename __node_base::pointer&
- __find_equal(const_iterator __hint, typename __node_base::pointer& __parent,
+ __node_base_pointer&
+ __find_equal(const_iterator __hint, __parent_pointer& __parent,
+ __node_base_pointer& __dummy,
const _Key& __v);
#ifndef _LIBCPP_CXX03_LANG
@@ -1418,7 +1483,7 @@
typename __tree<_Tp, _Compare, _Allocator>::__node_pointer
__tree<_Tp, _Compare, _Allocator>::__detach()
{
- __node_pointer __cache = __begin_node();
+ __node_pointer __cache = __begin_node_downcast();
__begin_node() = __end_node();
__end_node()->__left_->__parent_ = nullptr;
__end_node()->__left_ = nullptr;
@@ -1450,7 +1515,7 @@
return static_cast<__node_pointer>(__tree_leaf(__cache->__right_));
}
// __cache is right child
- __cache->__parent_->__right_ = nullptr;
+ __cache->__parent_unsafe()->__right_ = nullptr;
__cache = static_cast<__node_pointer>(__cache->__parent_);
if (__cache->__left_ == nullptr)
return __cache;
@@ -1585,7 +1650,7 @@
__begin_node() = __end_node();
else
{
- __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
+ __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
__t.__begin_node() = __t.__end_node();
__t.__end_node()->__left_ = nullptr;
__t.size() = 0;
@@ -1605,7 +1670,7 @@
{
__begin_node() = __t.__begin_node();
__end_node()->__left_ = __t.__end_node()->__left_;
- __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
+ __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
size() = __t.size();
__t.__begin_node() = __t.__end_node();
__t.__end_node()->__left_ = nullptr;
@@ -1633,7 +1698,7 @@
__begin_node() = __end_node();
else
{
- __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
+ __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
__t.__begin_node() = __t.__end_node();
__t.__end_node()->__left_ = nullptr;
__t.size() = 0;
@@ -1741,11 +1806,11 @@
if (size() == 0)
__begin_node() = __end_node();
else
- __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
+ __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
if (__t.size() == 0)
__t.__begin_node() = __t.__end_node();
else
- __t.__end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__t.__end_node());
+ __t.__end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__t.__end_node());
}
template <class _Tp, class _Compare, class _Allocator>
@@ -1762,8 +1827,8 @@
// Set __parent to parent of null leaf
// Return reference to null leaf
template <class _Tp, class _Compare, class _Allocator>
-typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
-__tree<_Tp, _Compare, _Allocator>::__find_leaf_low(typename __node_base::pointer& __parent,
+typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
+__tree<_Tp, _Compare, _Allocator>::__find_leaf_low(__parent_pointer& __parent,
const key_type& __v)
{
__node_pointer __nd = __root();
@@ -1777,32 +1842,32 @@
__nd = static_cast<__node_pointer>(__nd->__right_);
else
{
- __parent = static_cast<__node_base_pointer>(__nd);
- return __parent->__right_;
+ __parent = static_cast<__parent_pointer>(__nd);
+ return __nd->__right_;
}
}
else
{
if (__nd->__left_ != nullptr)
__nd = static_cast<__node_pointer>(__nd->__left_);
else
{
- __parent = static_cast<__node_base_pointer>(__nd);
+ __parent = static_cast<__parent_pointer>(__nd);
return __parent->__left_;
}
}
}
}
- __parent = static_cast<__node_base_pointer>(__end_node());
+ __parent = static_cast<__parent_pointer>(__end_node());
return __parent->__left_;
}
// Find upper_bound place to insert
// Set __parent to parent of null leaf
// Return reference to null leaf
template <class _Tp, class _Compare, class _Allocator>
-typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
-__tree<_Tp, _Compare, _Allocator>::__find_leaf_high(typename __node_base::pointer& __parent,
+typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
+__tree<_Tp, _Compare, _Allocator>::__find_leaf_high(__parent_pointer& __parent,
const key_type& __v)
{
__node_pointer __nd = __root();
@@ -1816,7 +1881,7 @@
__nd = static_cast<__node_pointer>(__nd->__left_);
else
{
- __parent = static_cast<__node_base_pointer>(__nd);
+ __parent = static_cast<__parent_pointer>(__nd);
return __parent->__left_;
}
}
@@ -1826,13 +1891,13 @@
__nd = static_cast<__node_pointer>(__nd->__right_);
else
{
- __parent = static_cast<__node_base_pointer>(__nd);
- return __parent->__right_;
+ __parent = static_cast<__parent_pointer>(__nd);
+ return __nd->__right_;
}
}
}
}
- __parent = static_cast<__node_base_pointer>(__end_node());
+ __parent = static_cast<__parent_pointer>(__end_node());
return __parent->__left_;
}
@@ -1843,9 +1908,9 @@
// Set __parent to parent of null leaf
// Return reference to null leaf
template <class _Tp, class _Compare, class _Allocator>
-typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
+typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
__tree<_Tp, _Compare, _Allocator>::__find_leaf(const_iterator __hint,
- typename __node_base::pointer& __parent,
+ __parent_pointer& __parent,
const key_type& __v)
{
if (__hint == end() || !value_comp()(*__hint, __v)) // check before
@@ -1857,13 +1922,13 @@
// *prev(__hint) <= __v <= *__hint
if (__hint.__ptr_->__left_ == nullptr)
{
- __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
+ __parent = static_cast<__parent_pointer>(__hint.__ptr_);
return __parent->__left_;
}
else
{
- __parent = static_cast<__node_base_pointer>(__prior.__ptr_);
- return __parent->__right_;
+ __parent = static_cast<__parent_pointer>(__prior.__ptr_);
+ return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_;
}
}
// __v < *prev(__hint)
@@ -1879,43 +1944,44 @@
// If __v exists, set parent to node of __v and return reference to node of __v
template <class _Tp, class _Compare, class _Allocator>
template <class _Key>
-typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
-__tree<_Tp, _Compare, _Allocator>::__find_equal(typename __node_base::pointer& __parent,
+typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
+__tree<_Tp, _Compare, _Allocator>::__find_equal(__parent_pointer& __parent,
const _Key& __v)
{
__node_pointer __nd = __root();
+ __node_base_pointer* __nd_ptr = __root_ptr();
if (__nd != nullptr)
{
while (true)
{
if (value_comp()(__v, __nd->__value_))
{
- if (__nd->__left_ != nullptr)
+ if (__nd->__left_ != nullptr) {
+ __nd_ptr = _VSTD::addressof(__nd->__left_);
__nd = static_cast<__node_pointer>(__nd->__left_);
- else
- {
- __parent = static_cast<__node_base_pointer>(__nd);
+ } else {
+ __parent = static_cast<__parent_pointer>(__nd);
return __parent->__left_;
}
}
else if (value_comp()(__nd->__value_, __v))
{
- if (__nd->__right_ != nullptr)
+ if (__nd->__right_ != nullptr) {
+ __nd_ptr = _VSTD::addressof(__nd->__right_);
__nd = static_cast<__node_pointer>(__nd->__right_);
- else
- {
- __parent = static_cast<__node_base_pointer>(__nd);
- return __parent->__right_;
+ } else {
+ __parent = static_cast<__parent_pointer>(__nd);
+ return __nd->__right_;
}
}
else
{
- __parent = static_cast<__node_base_pointer>(__nd);
- return __parent;
+ __parent = static_cast<__parent_pointer>(__nd);
+ return *__nd_ptr;
}
}
}
- __parent = static_cast<__node_base_pointer>(__end_node());
+ __parent = static_cast<__parent_pointer>(__end_node());
return __parent->__left_;
}
@@ -1928,9 +1994,10 @@
// If __v exists, set parent to node of __v and return reference to node of __v
template <class _Tp, class _Compare, class _Allocator>
template <class _Key>
-typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
+typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
__tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint,
- typename __node_base::pointer& __parent,
+ __parent_pointer& __parent,
+ __node_base_pointer& __dummy,
const _Key& __v)
{
if (__hint == end() || value_comp()(__v, *__hint)) // check before
@@ -1942,13 +2009,13 @@
// *prev(__hint) < __v < *__hint
if (__hint.__ptr_->__left_ == nullptr)
{
- __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
+ __parent = static_cast<__parent_pointer>(__hint.__ptr_);
return __parent->__left_;
}
else
{
- __parent = static_cast<__node_base_pointer>(__prior.__ptr_);
- return __parent->__right_;
+ __parent = static_cast<__parent_pointer>(__prior.__ptr_);
+ return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_;
}
}
// __v <= *prev(__hint)
@@ -1961,38 +2028,39 @@
if (__next == end() || value_comp()(__v, *__next))
{
// *__hint < __v < *_VSTD::next(__hint)
- if (__hint.__ptr_->__right_ == nullptr)
+ if (__hint.__get_np()->__right_ == nullptr)
{
- __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
- return __parent->__right_;
+ __parent = static_cast<__parent_pointer>(__hint.__ptr_);
+ return static_cast<__node_base_pointer>(__hint.__ptr_)->__right_;
}
else
{
- __parent = static_cast<__node_base_pointer>(__next.__ptr_);
+ __parent = static_cast<__parent_pointer>(__next.__ptr_);
return __parent->__left_;
}
}
// *next(__hint) <= __v
return __find_equal(__parent, __v);
}
// else __v == *__hint
- __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
- return __parent;
+ __parent = static_cast<__parent_pointer>(__hint.__ptr_);
+ __dummy = static_cast<__node_base_pointer>(__hint.__ptr_);
+ return __dummy;
}
template <class _Tp, class _Compare, class _Allocator>
void
-__tree<_Tp, _Compare, _Allocator>::__insert_node_at(__node_base_pointer __parent,
+__tree<_Tp, _Compare, _Allocator>::__insert_node_at(__parent_pointer __parent,
__node_base_pointer& __child,
- __node_base_pointer __new_node)
+ __node_base_pointer __new_node)
{
__new_node->__left_ = nullptr;
__new_node->__right_ = nullptr;
__new_node->__parent_ = __parent;
// __new_node->__is_black_ is initialized in __tree_balance_after_insert
__child = __new_node;
if (__begin_node()->__left_ != nullptr)
- __begin_node() = static_cast<__node_pointer>(__begin_node()->__left_);
+ __begin_node() = static_cast<__iter_pointer>(__begin_node()->__left_);
__tree_balance_after_insert(__end_node()->__left_, __child);
++size();
}
@@ -2009,7 +2077,7 @@
__tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args& __args)
#endif
{
- __node_base_pointer __parent;
+ __parent_pointer __parent;
__node_base_pointer& __child = __find_equal(__parent, __k);
__node_pointer __r = static_cast<__node_pointer>(__child);
bool __inserted = false;
@@ -2042,8 +2110,9 @@
const_iterator __p, _Key const& __k, _Args& __args)
#endif
{
- __node_base_pointer __parent;
- __node_base_pointer& __child = __find_equal(__p, __parent, __k);
+ __parent_pointer __parent;
+ __node_base_pointer __dummy;
+ __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __k);
__node_pointer __r = static_cast<__node_pointer>(__child);
if (__child == nullptr)
{
@@ -2082,7 +2151,7 @@
__tree<_Tp, _Compare, _Allocator>::__emplace_unique_impl(_Args&&... __args)
{
__node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
- __node_base_pointer __parent;
+ __parent_pointer __parent;
__node_base_pointer& __child = __find_equal(__parent, __h->__value_);
__node_pointer __r = static_cast<__node_pointer>(__child);
bool __inserted = false;
@@ -2101,8 +2170,9 @@
__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_impl(const_iterator __p, _Args&&... __args)
{
__node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
- __node_base_pointer __parent;
- __node_base_pointer& __child = __find_equal(__p, __parent, __h->__value_);
+ __parent_pointer __parent;
+ __node_base_pointer __dummy;
+ __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __h->__value_);
__node_pointer __r = static_cast<__node_pointer>(__child);
if (__child == nullptr)
{
@@ -2118,7 +2188,7 @@
__tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args)
{
__node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
- __node_base_pointer __parent;
+ __parent_pointer __parent;
__node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__h->__value_));
__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
return iterator(static_cast<__node_pointer>(__h.release()));
@@ -2131,7 +2201,7 @@
_Args&&... __args)
{
__node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
- __node_base_pointer __parent;
+ __parent_pointer __parent;
__node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__h->__value_));
__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
return iterator(static_cast<__node_pointer>(__h.release()));
@@ -2158,7 +2228,7 @@
typename __tree<_Tp, _Compare, _Allocator>::iterator
__tree<_Tp, _Compare, _Allocator>::__insert_multi(const __container_value_type& __v)
{
- __node_base_pointer __parent;
+ __parent_pointer __parent;
__node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__v));
__node_holder __h = __construct_node(__v);
__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
@@ -2169,7 +2239,7 @@
typename __tree<_Tp, _Compare, _Allocator>::iterator
__tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, const __container_value_type& __v)
{
- __node_base_pointer __parent;
+ __parent_pointer __parent;
__node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__v));
__node_holder __h = __construct_node(__v);
__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
@@ -2181,7 +2251,7 @@
pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
__tree<_Tp, _Compare, _Allocator>::__node_insert_unique(__node_pointer __nd)
{
- __node_base_pointer __parent;
+ __parent_pointer __parent;
__node_base_pointer& __child = __find_equal(__parent, __nd->__value_);
__node_pointer __r = static_cast<__node_pointer>(__child);
bool __inserted = false;
@@ -2199,7 +2269,8 @@
__tree<_Tp, _Compare, _Allocator>::__node_insert_unique(const_iterator __p,
__node_pointer __nd)
{
- __node_base_pointer __parent;
+ __parent_pointer __parent;
+ __node_base_pointer __dummy;
__node_base_pointer& __child = __find_equal(__p, __parent, __nd->__value_);
__node_pointer __r = static_cast<__node_pointer>(__child);
if (__child == nullptr)
@@ -2214,7 +2285,7 @@
typename __tree<_Tp, _Compare, _Allocator>::iterator
__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd)
{
- __node_base_pointer __parent;
+ __parent_pointer __parent;
__node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__nd->__value_));
__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
return iterator(__nd);
@@ -2225,7 +2296,7 @@
__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p,
__node_pointer __nd)
{
- __node_base_pointer __parent;
+ __parent_pointer __parent;
__node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__nd->__value_));
__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
return iterator(__nd);
@@ -2235,10 +2306,10 @@
typename __tree<_Tp, _Compare, _Allocator>::iterator
__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p)
{
- __node_pointer __np = __p.__ptr_;
- iterator __r(__np);
+ __node_pointer __np = __p.__get_np();
+ iterator __r(__p.__ptr_);
++__r;
- if (__begin_node() == __np)
+ if (__begin_node() == __p.__ptr_)
__begin_node() = __r.__ptr_;
--size();
__node_allocator& __na = __node_alloc();
@@ -2310,13 +2381,11 @@
typename __tree<_Tp, _Compare, _Allocator>::size_type
__tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const
{
- __node_pointer __result = __end_node();
__node_pointer __rt = __root();
while (__rt != nullptr)
{
if (value_comp()(__k, __rt->__value_))
{
- __result = __rt;
__rt = static_cast<__node_pointer>(__rt->__left_);
}
else if (value_comp()(__rt->__value_, __k))
@@ -2332,20 +2401,20 @@
typename __tree<_Tp, _Compare, _Allocator>::size_type
__tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const
{
- __node_pointer __result = __end_node();
+ __iter_pointer __result = __end_node();
__node_pointer __rt = __root();
while (__rt != nullptr)
{
if (value_comp()(__k, __rt->__value_))
{
- __result = __rt;
+ __result = static_cast<__iter_pointer>(__rt);
__rt = static_cast<__node_pointer>(__rt->__left_);
}
else if (value_comp()(__rt->__value_, __k))
__rt = static_cast<__node_pointer>(__rt->__right_);
else
return _VSTD::distance(
- __lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), __rt),
+ __lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)),
__upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result)
);
}
@@ -2357,13 +2426,13 @@
typename __tree<_Tp, _Compare, _Allocator>::iterator
__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v,
__node_pointer __root,
- __node_pointer __result)
+ __iter_pointer __result)
{
while (__root != nullptr)
{
if (!value_comp()(__root->__value_, __v))
{
- __result = __root;
+ __result = static_cast<__iter_pointer>(__root);
__root = static_cast<__node_pointer>(__root->__left_);
}
else
@@ -2377,13 +2446,13 @@
typename __tree<_Tp, _Compare, _Allocator>::const_iterator
__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v,
__node_pointer __root,
- __node_pointer __result) const
+ __iter_pointer __result) const
{
while (__root != nullptr)
{
if (!value_comp()(__root->__value_, __v))
{
- __result = __root;
+ __result = static_cast<__iter_pointer>(__root);
__root = static_cast<__node_pointer>(__root->__left_);
}
else
@@ -2397,13 +2466,13 @@
typename __tree<_Tp, _Compare, _Allocator>::iterator
__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v,
__node_pointer __root,
- __node_pointer __result)
+ __iter_pointer __result)
{
while (__root != nullptr)
{
if (value_comp()(__v, __root->__value_))
{
- __result = __root;
+ __result = static_cast<__iter_pointer>(__root);
__root = static_cast<__node_pointer>(__root->__left_);
}
else
@@ -2417,13 +2486,13 @@
typename __tree<_Tp, _Compare, _Allocator>::const_iterator
__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v,
__node_pointer __root,
- __node_pointer __result) const
+ __iter_pointer __result) const
{
while (__root != nullptr)
{
if (value_comp()(__v, __root->__value_))
{
- __result = __root;
+ __result = static_cast<__iter_pointer>(__root);
__root = static_cast<__node_pointer>(__root->__left_);
}
else
@@ -2439,22 +2508,22 @@
__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k)
{
typedef pair<iterator, iterator> _Pp;
- __node_pointer __result = __end_node();
+ __iter_pointer __result = __end_node();
__node_pointer __rt = __root();
while (__rt != nullptr)
{
if (value_comp()(__k, __rt->__value_))
{
- __result = __rt;
+ __result = static_cast<__iter_pointer>(__rt);
__rt = static_cast<__node_pointer>(__rt->__left_);
}
else if (value_comp()(__rt->__value_, __k))
__rt = static_cast<__node_pointer>(__rt->__right_);
else
return _Pp(iterator(__rt),
iterator(
__rt->__right_ != nullptr ?
- static_cast<__node_pointer>(__tree_min(__rt->__right_))
+ static_cast<__iter_pointer>(__tree_min(__rt->__right_))
: __result));
}
return _Pp(iterator(__result), iterator(__result));
@@ -2467,22 +2536,22 @@
__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const
{
typedef pair<const_iterator, const_iterator> _Pp;
- __node_pointer __result = __end_node();
+ __iter_pointer __result = __end_node();
__node_pointer __rt = __root();
while (__rt != nullptr)
{
if (value_comp()(__k, __rt->__value_))
{
- __result = __rt;
+ __result = static_cast<__iter_pointer>(__rt);
__rt = static_cast<__node_pointer>(__rt->__left_);
}
else if (value_comp()(__rt->__value_, __k))
__rt = static_cast<__node_pointer>(__rt->__right_);
else
return _Pp(const_iterator(__rt),
const_iterator(
__rt->__right_ != nullptr ?
- static_cast<__node_pointer>(__tree_min(__rt->__right_))
+ static_cast<__iter_pointer>(__tree_min(__rt->__right_))
: __result));
}
return _Pp(const_iterator(__result), const_iterator(__result));
@@ -2495,19 +2564,19 @@
__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k)
{
typedef pair<iterator, iterator> _Pp;
- __node_pointer __result = __end_node();
+ __iter_pointer __result = __end_node();
__node_pointer __rt = __root();
while (__rt != nullptr)
{
if (value_comp()(__k, __rt->__value_))
{
- __result = __rt;
+ __result = static_cast<__iter_pointer>(__rt);
__rt = static_cast<__node_pointer>(__rt->__left_);
}
else if (value_comp()(__rt->__value_, __k))
__rt = static_cast<__node_pointer>(__rt->__right_);
else
- return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), __rt),
+ return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)),
__upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result));
}
return _Pp(iterator(__result), iterator(__result));
@@ -2520,19 +2589,19 @@
__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const
{
typedef pair<const_iterator, const_iterator> _Pp;
- __node_pointer __result = __end_node();
+ __iter_pointer __result = __end_node();
__node_pointer __rt = __root();
while (__rt != nullptr)
{
if (value_comp()(__k, __rt->__value_))
{
- __result = __rt;
+ __result = static_cast<__iter_pointer>(__rt);
__rt = static_cast<__node_pointer>(__rt->__left_);
}
else if (value_comp()(__rt->__value_, __k))
__rt = static_cast<__node_pointer>(__rt->__right_);
else
- return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), __rt),
+ return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)),
__upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result));
}
return _Pp(const_iterator(__result), const_iterator(__result));
@@ -2542,13 +2611,13 @@
typename __tree<_Tp, _Compare, _Allocator>::__node_holder
__tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT
{
- __node_pointer __np = __p.__ptr_;
- if (__begin_node() == __np)
+ __node_pointer __np = __p.__get_np();
+ if (__begin_node() == __p.__ptr_)
{
if (__np->__right_ != nullptr)
- __begin_node() = static_cast<__node_pointer>(__np->__right_);
+ __begin_node() = static_cast<__iter_pointer>(__np->__right_);
else
- __begin_node() = static_cast<__node_pointer>(__np->__parent_);
+ __begin_node() = static_cast<__iter_pointer>(__np->__parent_);
}
--size();
__tree_remove(__end_node()->__left_,
Index: include/__config
===================================================================
--- include/__config
+++ include/__config
@@ -42,6 +42,8 @@
// Fix undefined behavior in how std::list stores it's linked nodes.
#define _LIBCPP_ABI_LIST_REMOVE_NODE_POINTER_UB
#define _LIBCPP_ABI_FORWARD_LIST_REMOVE_NODE_POINTER_UB
+// Fix undefined behavior in how __tree stores its end and parent nodes.
+#define _LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB
#define _LIBCPP_ABI_FIX_UNORDERED_CONTAINER_SIZE_TYPE
#endif
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
