Fix undefined behavior in __tree

[EricWF]

Summary

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 __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 the wrong type is in __tree_node_base::__parent_. Currently __left_, __right_, and __parent_ are all __tree_node_base 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_end_node in the new ABI or __tree_node_base in the current one.

Note that in the new ABI __iter_pointer and __parent_pointer are the same type (but not in 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.

[EricWF]

Fix __tree algorithm tests.

[EricWF]

Fix some code I broke last iteration.

[EricWF]

@mclow.lists What would you like to see in order to help this patch proceed?

[EricWF]

Fix merge conflicts in __config.

[EricWF]

Adding Howard to the reviewers. @howard.hinnant Feel free to take a look if your interested.

@mclow.lists Any comments?

[mclow.lists]

I'm not really happy with this situation, but I don't see how to improve this patch.

[EricWF]

Add test for PR28469 and remove __tree from the UBSAN blacklist.

include/__config

 #if defined(_LIBCPP_ABI_UNSTABLE) || _LIBCPP_ABI_VERSION >= 2
 // Change short string represention so that string data starts at offset 0,
 // improving its alignment in some cases.
 #define _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
 // Fix deque iterator type in order to support incomplete types.
 #define _LIBCPP_ABI_INCOMPLETE_TYPES_IN_DEQUE
 // Fix undefined behavior in how std::list stores it's linked nodes.
 #define _LIBCPP_ABI_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_FORWARD_LIST_REMOVE_NODE_POINTER_UB
 #define _LIBCPP_ABI_FIX_UNORDERED_CONTAINER_SIZE_TYPE
 #define _LIBCPP_ABI_VARIADIC_LOCK_GUARD
 #elif _LIBCPP_ABI_VERSION == 1
 // Feature macros for disabling pre ABI v1 features. All of these options
 // are deprecated.
 #if defined(__FreeBSD__)
 #define _LIBCPP_DEPRECATED_ABI_DISABLE_PAIR_TRIVIAL_COPY_CTOR

include/__tree

 // Precondition:  __x != nullptr.
 template <class _NodePtr>
 _NodePtr
 __tree_next(_NodePtr __x) _NOEXCEPT
 {
     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 _EndNodePtr, class _NodePtr>
+inline _LIBCPP_INLINE_VISIBILITY
+_EndNodePtr
+__tree_next_iter(_NodePtr __x) _NOEXCEPT
+{
+    if (__x->__right_ != nullptr)
+        return static_cast<_EndNodePtr>(__tree_min(__x->__right_));
+    while (!__tree_is_left_child(__x))
+        __x = __x->__parent_unsafe();
+    return static_cast<_EndNodePtr>(__x->__parent_);
 }
 
 // Returns:  pointer to the previous in-order node before __x.
 // Precondition:  __x != nullptr.
-template <class _NodePtr>
+// Note: __x may be the end node.
+template <class _NodePtr, class _EndNodePtr>
+inline _LIBCPP_INLINE_VISIBILITY
 _NodePtr
-__tree_prev(_NodePtr __x) _NOEXCEPT
+__tree_prev_iter(_EndNodePtr __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
 // Precondition:  __x != nullptr.
 template <class _NodePtr>
 _NodePtr
 __tree_leaf(_NodePtr __x) _NOEXCEPT
 {

 // Precondition:  __x->__right_ != nullptr
 template <class _NodePtr>
 void
 __tree_left_rotate(_NodePtr __x) _NOEXCEPT
 {
     _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
 //           while preserving in-order order.
 // Precondition:  __x->__left_ != nullptr
 template <class _NodePtr>
 void
 __tree_right_rotate(_NodePtr __x) _NOEXCEPT
 {
     _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.
 // Precondition:  __root != nulptr && __x != nullptr.
 //                __x has no children.
 //                __x == __root or == a direct or indirect child of __root.
 //                If __x were to be unlinked from __root (setting __root to
 //                  nullptr if __root == __x), __tree_invariant(__root) == true.
 // Postcondition: __tree_invariant(end_node->__left_) == true.  end_node->__left_
 //                may be different than the value passed in as __root.
 template <class _NodePtr>
 void
 __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;
             }
         }
     }
 }
 
__tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT
     _NodePtr __w = nullptr;
     // link __x to __y's parent, and find __w
     if (__x != nullptr)
         __x->__parent_ = __y->__parent_;
     if (__tree_is_left_child(__y))
     {
         __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_;
     }
     bool __removed_black = __y->__is_black_;
     // If we didn't remove __z, do so now by splicing in __y for __z,
     //    but copy __z's color.  This does not impact __x or __w.
     if (__y != __z)
     {
         // __z->__left_ != nulptr but __z->__right_ might == __x == nullptr
         __y->__parent_ = __z->__parent_;
         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;
     }
     // There is no need to rebalance if we removed a red, or if we removed
     //     the last node.
     if (__removed_black && __root != nullptr)
     {
if (__removed_black && __root != nullptr)
             //     with a non-null black child).
             while (true)
             {
                 if (!__tree_is_left_child(__w))  // if x is left child
                 {
                     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_)
                             __root = __w;
                         // reset sibling, and it still can't be null
                         __w = __w->__left_->__right_;
                     }
                     // __w->__is_black_ is now true, __w may have null children
                     if ((__w->__left_  == nullptr || __w->__left_->__is_black_) &&
                         (__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;
                     }
                     else  // __w has a red child
                     {
                         if (__w->__right_ == nullptr || __w->__right_->__is_black_)
                         {
                             // __w left child is non-null and red
                             __w->__left_->__is_black_ = true;
                             __w->__is_black_ = false;
                             __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_)
                             __root = __w;
                         // reset sibling, and it still can't be null
                         __w = __w->__right_->__left_;
                     }
                     // __w->__is_black_ is now true, __w may have null children
                     if ((__w->__left_  == nullptr || __w->__left_->__is_black_) &&
                         (__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;
                     }
                     else  // __w has a red child
                     {
                         if (__w->__left_ == nullptr || __w->__left_->__is_black_)
                         {
                             // __w right child is non-null and red
                             __w->__right_->__is_black_ = true;
                             __w->__is_black_ = false;
                             __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;
                     }
                 }
             }
         }
     }
 }
 
struct __tree_node_base_types {
 
   typedef __tree_node_base<__void_pointer>                      __node_base_type;
   typedef typename __rebind_pointer<_VoidPtr, __node_base_type>::type
                                                              __node_base_pointer;
 
   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");
 };
 
 template <class _Tp, class _AllocPtr, class _KVTypes = __tree_key_value_types<_Tp>,
          bool = _KVTypes::__is_map>
 struct __tree_map_pointer_types {};
public:
   typedef typename pointer_traits<_NodePtr>::element_type       __node_type;
   typedef _NodePtr                                              __node_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;
+#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");
     static_assert((is_same<typename __rebind_pointer<_VoidPtr, __node_type>::type,
                           _NodePtr>::value), "_VoidPtr does not rebind to _NodePtr.");
 };
 
 template <class _ValueTp, class _VoidPtr>

 template <class _VoidPtr>
 class __tree_node_base
     : public __tree_node_base_types<_VoidPtr>::__end_node_type
 {
     typedef __tree_node_base_types<_VoidPtr> _NodeBaseTypes;
 
 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;
   __tree_node_base& operator=(__tree_node_base const&) _LIBCPP_EQUAL_DELETE;
 };
 
 template <class _Tp, class _VoidPtr>
 class __tree_node

 
 
 template <class _Tp, class _NodePtr, class _DiffType>
 class _LIBCPP_TYPE_VIS_ONLY __tree_iterator
 {
     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;
     typedef _Tp                                            value_type;
     typedef _DiffType                                      difference_type;
     typedef value_type&                                    reference;
     typedef typename _NodeTypes::__node_value_type_pointer pointer;
 
     _LIBCPP_INLINE_VISIBILITY __tree_iterator() _NOEXCEPT
 #if _LIBCPP_STD_VER > 11
     : __ptr_(nullptr)
 #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
     __tree_iterator operator--(int)
         {__tree_iterator __t(*this); --(*this); return __t;}
 
     friend _LIBCPP_INLINE_VISIBILITY 
         bool operator==(const __tree_iterator& __x, const __tree_iterator& __y)
         {return __x.__ptr_ == __y.__ptr_;}
     friend _LIBCPP_INLINE_VISIBILITY
         bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y)
         {return !(__x == __y);}
 
 private:
     _LIBCPP_INLINE_VISIBILITY
     explicit __tree_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
+    _LIBCPP_INLINE_VISIBILITY
+    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;
     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 _Tp, class _NodePtr, class _DiffType>
 class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator
 {
     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;
     typedef _Tp                                                  value_type;
     typedef _DiffType                                            difference_type;
     typedef const value_type&                                    reference;
     typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
 
     _LIBCPP_INLINE_VISIBILITY __tree_const_iterator() _NOEXCEPT
 #if _LIBCPP_STD_VER > 11
     : __ptr_(nullptr)
 #endif
     {}
 
 private:
     typedef __tree_iterator<value_type, __node_pointer, difference_type>
                                                            __non_const_iterator;
 public:
     _LIBCPP_INLINE_VISIBILITY
     __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;
     }
 
     _LIBCPP_INLINE_VISIBILITY
     __tree_const_iterator operator++(int)
         {__tree_const_iterator __t(*this); ++(*this); return __t;}
 
     _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;
     }
 
     _LIBCPP_INLINE_VISIBILITY
     __tree_const_iterator operator--(int)
         {__tree_const_iterator __t(*this); --(*this); return __t;}
 
     friend _LIBCPP_INLINE_VISIBILITY
         bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y)
         {return __x.__ptr_ == __y.__ptr_;}
     friend _LIBCPP_INLINE_VISIBILITY
         bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y)
         {return !(__x == __y);}
 
 private:
     _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>
 class __tree
 {
 public:
     typedef _Tp                                      value_type;
     typedef _Compare                                 value_compare;
public:
     typedef typename _NodeTypes::__node_pointer        __node_pointer;
 
     typedef typename _NodeTypes::__node_base_type      __node_base;
     typedef typename _NodeTypes::__node_base_pointer   __node_base_pointer;
 
     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;
 
 private:
     // check for sane allocator pointer rebinding semantics. Rebinding the
     // allocator for a new pointer type should be exactly the same as rebinding
     // the pointer using 'pointer_traits'.
     static_assert((is_same<__node_pointer, typename __node_traits::pointer>::value),
                   "Allocator does not rebind pointers in a sane manner.");
     typedef typename __rebind_alloc_helper<__node_traits, __node_base>::type
         __node_base_allocator;
     typedef allocator_traits<__node_base_allocator> __node_base_traits;
     static_assert((is_same<__node_base_pointer, typename __node_base_traits::pointer>::value),
                  "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())
             )
         );
     }
     _LIBCPP_INLINE_VISIBILITY
           __node_allocator& __node_alloc() _NOEXCEPT {return __pair1_.second();}
 private:
     _LIBCPP_INLINE_VISIBILITY
     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 __node_pointer& __begin_node() const _NOEXCEPT {return __begin_node_;}
+    const __iter_pointer& __begin_node() const _NOEXCEPT {return __begin_node_;}
 public:
     _LIBCPP_INLINE_VISIBILITY
     allocator_type __alloc() const _NOEXCEPT
         {return allocator_type(__node_alloc());}
 private:
     _LIBCPP_INLINE_VISIBILITY
           size_type& size() _NOEXCEPT {return __pair3_.first();}
 public:
     _LIBCPP_INLINE_VISIBILITY
     const size_type& size() const _NOEXCEPT {return __pair3_.first();}
     _LIBCPP_INLINE_VISIBILITY
           value_compare& value_comp() _NOEXCEPT {return __pair3_.second();}
     _LIBCPP_INLINE_VISIBILITY
     const value_compare& value_comp() const _NOEXCEPT
         {return __pair3_.second();}
 public:
 
     _LIBCPP_INLINE_VISIBILITY
     __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;
 
     explicit __tree(const value_compare& __comp)
         _NOEXCEPT_(
             is_nothrow_default_constructible<__node_allocator>::value &&
             is_nothrow_copy_constructible<value_compare>::value);
     explicit __tree(const allocator_type& __a);
#endif // !_LIBCPP_CXX03_LANG
 
     iterator erase(const_iterator __p);
     iterator erase(const_iterator __f, const_iterator __l);
     template <class _Key>
         size_type __erase_unique(const _Key& __k);
     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);
 
     template <class _Key>
         iterator find(const _Key& __v);
     template <class _Key>
         const_iterator find(const _Key& __v) const;
 
     template <class _Key>
         size_type __count_unique(const _Key& __k) const;
     template <class _Key>
         size_type __count_multi(const _Key& __k) const;
 
     template <class _Key>
         _LIBCPP_INLINE_VISIBILITY
         iterator lower_bound(const _Key& __v)
             {return __lower_bound(__v, __root(), __end_node());}
     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);
     template <class _Key>
         pair<const_iterator, const_iterator>
         __equal_range_unique(const _Key& __k) const;
 
     template <class _Key>
         pair<iterator, iterator>
         __equal_range_multi(const _Key& __k);
     template <class _Key>
         pair<const_iterator, const_iterator>
         __equal_range_multi(const _Key& __k) const;
 
     typedef __tree_node_destructor<__node_allocator> _Dp;
     typedef unique_ptr<__node, _Dp> __node_holder;
 
     __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
     template <class ..._Args>
     __node_holder __construct_node(_Args&& ...__args);
 #else
     __node_holder __construct_node(const __container_value_type& __v);
 #endif
__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp)
             is_nothrow_copy_constructible<value_compare>::value)
     : __pair3_(0, __comp)
 {
     __begin_node() = __end_node();
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 __tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a)
-    : __begin_node_(__node_pointer()),
+    : __begin_node_(__iter_pointer()),
       __pair1_(__node_allocator(__a)),
       __pair3_(0)
 {
     __begin_node() = __end_node();
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 __tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp,
                                            const allocator_type& __a)
-    : __begin_node_(__node_pointer()),
+    : __begin_node_(__iter_pointer()),
       __pair1_(__node_allocator(__a)),
       __pair3_(0, __comp)
 {
     __begin_node() = __end_node();
 }
 
 // Precondition:  size() != 0
 template <class _Tp, class _Compare, class _Allocator>
 typename __tree<_Tp, _Compare, _Allocator>::__node_pointer
 __tree<_Tp, _Compare, _Allocator>::__detach()
 {
-    __node_pointer __cache = __begin_node();
+    __node_pointer __cache = static_cast<__node_pointer>(__begin_node());
     __begin_node() = __end_node();
     __end_node()->__left_->__parent_ = nullptr;
     __end_node()->__left_ = nullptr;
     size() = 0;
     // __cache->__left_ == nullptr
     if (__cache->__right_ != nullptr)
         __cache = static_cast<__node_pointer>(__cache->__right_);
     // __cache->__left_ == nullptr
__tree<_Tp, _Compare, _Allocator>::__detach(__node_pointer __cache)
     {
         __cache->__parent_->__left_ = nullptr;
         __cache = static_cast<__node_pointer>(__cache->__parent_);
         if (__cache->__right_ == nullptr)
             return __cache;
         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;
     return static_cast<__node_pointer>(__tree_leaf(__cache->__left_));
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 __tree<_Tp, _Compare, _Allocator>&
#endif  // _LIBCPP_NO_EXCEPTIONS
         }
     }
     for (; __first != __last; ++__first)
         __insert_multi(_NodeTypes::__get_value(*__first));
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 __tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t)
-    : __begin_node_(__node_pointer()),
+    : __begin_node_(__iter_pointer()),
       __pair1_(__node_traits::select_on_container_copy_construction(__t.__node_alloc())),
       __pair3_(0, __t.value_comp())
 {
     __begin_node() = __end_node();
 }
 
 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 
 template <class _Tp, class _Compare, class _Allocator>
 __tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t)
     _NOEXCEPT_(
         is_nothrow_move_constructible<__node_allocator>::value &&
         is_nothrow_move_constructible<value_compare>::value)
     : __begin_node_(_VSTD::move(__t.__begin_node_)),
       __pair1_(_VSTD::move(__t.__pair1_)),
       __pair3_(_VSTD::move(__t.__pair3_))
 {
     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());
         __t.__begin_node() = __t.__end_node();
         __t.__end_node()->__left_ = nullptr;
         __t.size() = 0;
     }
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 __tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a)
     : __pair1_(__node_allocator(__a)),
       __pair3_(0, _VSTD::move(__t.value_comp()))
 {
     if (__a == __t.__alloc())
     {
         if (__t.size() == 0)
             __begin_node() = __end_node();
         else
         {
             __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;
             __t.size() = 0;
         }
     }
     else
     {
__tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type)
     __begin_node_ = __t.__begin_node_;
     __pair1_.first() = __t.__pair1_.first();
     __move_assign_alloc(__t);
     __pair3_ = _VSTD::move(__t.__pair3_);
     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());
         __t.__begin_node() = __t.__end_node();
         __t.__end_node()->__left_ = nullptr;
         __t.size() = 0;
     }
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 void
#endif
     using _VSTD::swap;
     swap(__begin_node_, __t.__begin_node_);
     swap(__pair1_.first(), __t.__pair1_.first());
     __swap_allocator(__node_alloc(), __t.__node_alloc());
     __pair3_.swap(__t.__pair3_);
     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>
 void
 __tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT
 {
     destroy(__root());
     size() = 0;
     __begin_node() = __end_node();
     __end_node()->__left_ = nullptr;
 }
 
 // Find lower_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_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();
     if (__nd != nullptr)
     {
         while (true)
         {
             if (value_comp()(__nd->__value_, __v))
             {
                 if (__nd->__right_ != nullptr)
                     __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();
     if (__nd != nullptr)
     {
         while (true)
         {
             if (value_comp()(__v, __nd->__value_))
             {
                 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_;
                 }
             }
             else
             {
                 if (__nd->__right_ != nullptr)
                     __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_;
 }
 
 // Find leaf place to insert closest to __hint
 // First check prior to __hint.
 // Next check after __hint.
 // Next do O(log N) search.
 // 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
     {
         // __v <= *__hint
         const_iterator __prior = __hint;
         if (__prior == begin() || !value_comp()(__v, *--__prior))
         {
             // *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)
         return __find_leaf_high(__parent, __v);
     }
     // else __v > *__hint
     return __find_leaf_low(__parent, __v);
 }
 
 // Find place to insert if __v doesn't exist
 // Set __parent to parent of null leaf
 // Return reference to null leaf
 // 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_;
 }
 
 // Find place to insert if __v doesn't exist
 // First check prior to __hint.
 // Next check after __hint.
 // Next do O(log N) search.
 // Set __parent to parent of null leaf
 // Return reference to null leaf
 // 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
     {
         // __v < *__hint
         const_iterator __prior = __hint;
         if (__prior == begin() || value_comp()(*--__prior, __v))
         {
             // *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)
         return __find_equal(__parent, __v);
     }
     else if (value_comp()(*__hint, __v))  // check after
     {
         // *__hint < __v
         const_iterator __next = _VSTD::next(__hint);
         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();
 }
 
 #ifndef _LIBCPP_CXX03_LANG
 template <class _Tp, class _Compare, class _Allocator>
 template <class _Key, class... _Args>
 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
 __tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args)
 #else
 template <class _Tp, class _Compare, class _Allocator>
 template <class _Key, class _Args>
 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
 __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;
     if (__child == nullptr)
     {
 #ifndef _LIBCPP_CXX03_LANG
         __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
 #else

 #else
 template <class _Tp, class _Compare, class _Allocator>
 template <class _Key, class _Args>
 typename __tree<_Tp, _Compare, _Allocator>::iterator
 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args(
     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)
     {
 #ifndef _LIBCPP_CXX03_LANG
         __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
 #else
         __node_holder __h = __construct_node(__args);
 #endif

 
 
 template <class _Tp, class _Compare, class _Allocator>
 template <class... _Args>
 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
 __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;
     if (__child == nullptr)
     {
         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
         __r = __h.release();
         __inserted = true;
     }
     return pair<iterator, bool>(iterator(__r), __inserted);
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 template <class... _Args>
 typename __tree<_Tp, _Compare, _Allocator>::iterator
 __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)
     {
         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
         __r = __h.release();
     }
     return iterator(__r);
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 template <class... _Args>
 typename __tree<_Tp, _Compare, _Allocator>::iterator
 __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()));
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 template <class... _Args>
 typename __tree<_Tp, _Compare, _Allocator>::iterator
 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p,
                                                         _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()));
 }
 
 
 #else  // _LIBCPP_CXX03_LANG
 

 
 #endif  // _LIBCPP_CXX03_LANG
 
 #ifdef _LIBCPP_CXX03_LANG
 template <class _Tp, class _Compare, class _Allocator>
 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()));
     return iterator(__h.release());
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 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()));
     return iterator(__h.release());
 }
 #endif
 
 template <class _Tp, class _Compare, class _Allocator>
 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;
     if (__child == nullptr)
     {
         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
         __r = __nd;
         __inserted = true;
     }
     return pair<iterator, bool>(iterator(__r), __inserted);
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 typename __tree<_Tp, _Compare, _Allocator>::iterator
 __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)
     {
         __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
         __r = __nd;
     }
     return iterator(__r);
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 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);
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 typename __tree<_Tp, _Compare, _Allocator>::iterator
 __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);
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 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();
     __tree_remove(__end_node()->__left_,
                   static_cast<__node_base_pointer>(__np));
     __node_traits::destroy(__na, _NodeTypes::__get_ptr(
         const_cast<__node_value_type&>(*__p)));
     __node_traits::deallocate(__na, __np, 1);
__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) const
     return end();
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 template <class _Key>
 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))
             __rt = static_cast<__node_pointer>(__rt->__right_);
         else
             return 1;
     }
     return 0;
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 template <class _Key>
 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)
             );
     }
     return 0;
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 template <class _Key>
 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
             __root = static_cast<__node_pointer>(__root->__right_);
     }
     return iterator(__result);
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 template <class _Key>
 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
             __root = static_cast<__node_pointer>(__root->__right_);
     }
     return const_iterator(__result);
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 template <class _Key>
 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
             __root = static_cast<__node_pointer>(__root->__right_);
     }
     return iterator(__result);
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 template <class _Key>
 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
             __root = static_cast<__node_pointer>(__root->__right_);
     }
     return const_iterator(__result);
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 template <class _Key>
 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator,
      typename __tree<_Tp, _Compare, _Allocator>::iterator>
 __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));
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 template <class _Key>
 pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,
      typename __tree<_Tp, _Compare, _Allocator>::const_iterator>
 __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));
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 template <class _Key>
 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator,
      typename __tree<_Tp, _Compare, _Allocator>::iterator>
 __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));
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 template <class _Key>
 pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,
      typename __tree<_Tp, _Compare, _Allocator>::const_iterator>
 __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));
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 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_,
                   static_cast<__node_base_pointer>(__np));
     return __node_holder(__np, _Dp(__node_alloc(), true));
 }
 
 template <class _Tp, class _Compare, class _Allocator>

test/libcxx/containers/associative/tree_balance_after_insert.pass.cpp

 
 struct Node
 {
     Node* __left_;
     Node* __right_;
     Node* __parent_;
     bool __is_black_;
 
+    Node* __parent_unsafe() const { return __parent_; }
+    void __set_parent(Node* x) { __parent_ = x;}
+
     Node() : __left_(), __right_(), __parent_(), __is_black_() {}
 };
 
 void
 test1()
 {
     {
         Node root;

test/libcxx/containers/associative/tree_left_rotate.pass.cpp

 #include <cassert>
 
 struct Node
 {
     Node* __left_;
     Node* __right_;
     Node* __parent_;
 
+    Node* __parent_unsafe() const { return __parent_; }
+    void __set_parent(Node* x) { __parent_ = x;}
+
     Node() : __left_(), __right_(), __parent_() {}
 };
 
 void
 test1()
 {
     Node root;
     Node x;

test/libcxx/containers/associative/tree_remove.pass.cpp

 
 struct Node
 {
     Node* __left_;
     Node* __right_;
     Node* __parent_;
     bool __is_black_;
 
+    Node* __parent_unsafe() const { return __parent_; }
+    void __set_parent(Node* x) { __parent_ = x;}
+
     Node() : __left_(), __right_(), __parent_(), __is_black_() {}
 };
 
 void
 test1()
 {
     {
         // Left

test/libcxx/containers/associative/tree_right_rotate.pass.cpp

 #include <cassert>
 
 struct Node
 {
     Node* __left_;
     Node* __right_;
     Node* __parent_;
 
+    Node* __parent_unsafe() const { return __parent_; }
+    void __set_parent(Node* x) { __parent_ = x;}
+
     Node() : __left_(), __right_(), __parent_() {}
 };
 
 void
 test1()
 {
     Node root;
     Node x;

test/std/containers/associative/map/PR28469_undefined_behavior_segfault.sh.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// RUN: %build -O2
+// RUN: %run
+
+// <map>
+
+// Previously this code caused a segfault when compiled at -O2 due to undefined
+// behavior in __tree. See https://llvm.org/bugs/show_bug.cgi?id=28469
+
+#include <functional>
+#include <map>
+
+void dummy() {}
+
+struct F {
+    std::map<int, std::function<void()> > m;
+    F() { m[42] = &dummy; }
+};
+
+int main() {
+    F f;
+    f = F();
+}

test/ubsan_blacklist.txt

-fun:*__tree*
 fun:*__hash_table*