Fix undefined behavior in __hash_table

[EricWF]

Summary

This patch attempts to fix the undefined behavior in __hash_table by changing the node pointer types used throughout. The pointer types are changed for raw pointers in the current ABI and for fancy pointers in ABI V2 (since the fancy pointer types may not be ABI compatible).

The UB in __hash_table arises because tree downcasts the embedded end node and then deferences that pointer. Currently there are 2 node types in __hash_table:

• __hash_node_base which contains the __next_ pointer.
• __hash_node which contains __hash_ and __value_.

Currently the bucket list, iterators, and __next_ pointers store pointers to __hash_node even though they all need to store __hash_node_base pointers.
This patch makes that change by introducing a __next_pointer typedef which is a pointer to __hash_node in the current ABI and __hash_node_base afterwards.

One notable change is to the type of __bucket_list which used to be defined as unique_ptr<__node_pointer[], ...> and is now unique_ptr<__next_pointer[], ...> meaning that we now allocate and deallocate different types using a different allocator. I'm going to give this part of the change more thought since it may introduce compatibility issues.

This change is similar to D20786.

[EricWF]

There's an unintentional functionality change somewhere is this patch.

[EricWF]

• Merge with upstream.
• Cleanup logic in iterator
• Remove UBSAN blacklist. It's no longer needed. We have no more UB.

include/__config

 // 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
+// Fix undefined behavior in how __hash_table stores it's pointer types
+#define _LIBCPP_ABI_FIX_UNORDERED_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/__debug

 #   include <cstdlib>
 #   include <cstdio>
 #   include <cstddef>
 #   ifndef _LIBCPP_ASSERT
 #      define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : (_VSTD::fprintf(stderr, "%s\n", m), _VSTD::abort()))
 #   endif
 #endif
 
+#if _LIBCPP_DEBUG_LEVEL >= 2
+#ifndef _LIBCPP_DEBUG_ASSERT
+#define _LIBCPP_DEBUG_ASSERT(x, m) _LIBCPP_ASSERT(x, m)
+#endif
+#define _LIBCPP_DEBUG_MODE(...) __VA_ARGS__
+#endif
+
 #ifndef _LIBCPP_ASSERT
 #   define _LIBCPP_ASSERT(x, m) ((void)0)
 #endif
+#ifndef _LIBCPP_DEBUG_ASSERT
+#   define _LIBCPP_DEBUG_ASSERT(x, m) ((void)0)
+#endif
+#ifndef _LIBCPP_DEBUG_MODE
+#define _LIBCPP_DEBUG_MODE(...) ((void)0)
+#endif
 
 #if _LIBCPP_DEBUG_LEVEL >= 2
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 struct _LIBCPP_TYPE_VIS __c_node;
 
 struct _LIBCPP_TYPE_VIS __i_node

include/__hash_table

 #endif
 
 _LIBCPP_FUNC_VIS
 size_t __next_prime(size_t __n);
 
 template <class _NodePtr>
 struct __hash_node_base
 {
+    typedef typename pointer_traits<_NodePtr>::element_type __node_type;
     typedef __hash_node_base __first_node;
+    typedef typename __rebind_pointer<_NodePtr, __first_node>::type __node_base_pointer;
+    typedef _NodePtr __node_pointer;
+
+#if defined(_LIBCPP_ABI_FIX_UNORDERED_NODE_POINTER_UB)
+  typedef __node_base_pointer __next_pointer;
+#else
+  typedef typename conditional<
+      is_pointer<__node_pointer>::value,
+      __node_base_pointer,
+      __node_pointer>::type   __next_pointer;
+#endif
+
+    __next_pointer    __next_;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __next_pointer __ptr() _NOEXCEPT {
+        return static_cast<__next_pointer>(
+            pointer_traits<__node_base_pointer>::pointer_to(*this));
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    __node_pointer __upcast() _NOEXCEPT {
+        return static_cast<__node_pointer>(
+            pointer_traits<__node_base_pointer>::pointer_to(*this));
+    }
 
-    _NodePtr    __next_;
+    _LIBCPP_INLINE_VISIBILITY
+    size_t __hash() const _NOEXCEPT {
+        return static_cast<__node_type const&>(*this).__hash_;
+    }
 
     _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {}
 };
 
 template <class _Tp, class _VoidPtr>
 struct __hash_node
     : public __hash_node_base
              <
                  typename __rebind_pointer<_VoidPtr, __hash_node<_Tp, _VoidPtr> >::type
              >
 {
     typedef _Tp __node_value_type;
 
-    size_t     __hash_;
+    size_t            __hash_;
     __node_value_type __value_;
 };
 
 inline _LIBCPP_INLINE_VISIBILITY
 bool
 __is_hash_power2(size_t __bc)
 {
     return __bc > 2 && !(__bc & (__bc - 1));
public:
 
   typedef typename pointer_traits<_NodePtr>::element_type       __node_type;
   typedef _NodePtr                                              __node_pointer;
 
   typedef __hash_node_base<__node_pointer>                      __node_base_type;
   typedef typename __rebind_pointer<_NodePtr, __node_base_type>::type
                                                              __node_base_pointer;
 
+  typedef typename __node_base_type::__next_pointer          __next_pointer;
+
   typedef _Tp                                                 __node_value_type;
   typedef typename __rebind_pointer<_VoidPtr, __node_value_type>::type
                                                       __node_value_type_pointer;
   typedef typename __rebind_pointer<_VoidPtr, const __node_value_type>::type
                                                 __const_node_value_type_pointer;
+
 private:
     static_assert(!is_const<__node_type>::value,
                 "_NodePtr should never be a pointer to const");
     static_assert((is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value),
                   "_VoidPtr does not point to unqualified void type");
     static_assert((is_same<typename __rebind_pointer<_VoidPtr, __node_type>::type,
                           _NodePtr>::value), "_VoidPtr does not rebind to _NodePtr.");
 };
 
-
-
 template <class _HashIterator>
 struct __hash_node_types_from_iterator;
 template <class _NodePtr>
 struct __hash_node_types_from_iterator<__hash_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
 template <class _NodePtr>
 struct __hash_node_types_from_iterator<__hash_const_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
 template <class _NodePtr>
 struct __hash_node_types_from_iterator<__hash_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
 template <class _NodePtr>
 struct __hash_node_types_from_iterator<__hash_const_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
 
 
 template <class _NodeValueTp, class _VoidPtr>
 struct __make_hash_node_types {
   typedef __hash_node<_NodeValueTp, _VoidPtr> _NodeTp;
   typedef typename __rebind_pointer<_VoidPtr, _NodeTp>::type _NodePtr;
   typedef __hash_node_types<_NodePtr> type;
 };
 
 template <class _NodePtr>
 class _LIBCPP_TYPE_VIS_ONLY __hash_iterator
 {
     typedef __hash_node_types<_NodePtr> _NodeTypes;
-    typedef _NodePtr                    __node_pointer;
+    typedef _NodePtr                            __node_pointer;
+    typedef typename _NodeTypes::__next_pointer __next_pointer;
 
-    __node_pointer            __node_;
+    __next_pointer            __node_;
 
 public:
     typedef forward_iterator_tag                           iterator_category;
     typedef typename _NodeTypes::__node_value_type         value_type;
     typedef typename _NodeTypes::difference_type           difference_type;
     typedef value_type&                                    reference;
     typedef typename _NodeTypes::__node_value_type_pointer pointer;
 
-    _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT
-#if _LIBCPP_STD_VER > 11
-    : __node_(nullptr)
-#endif
-    {
-#if _LIBCPP_DEBUG_LEVEL >= 2
-        __get_db()->__insert_i(this);
-#endif
+    _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT : __node_(nullptr) {
+        _LIBCPP_DEBUG_MODE(__get_db()->__insert_i(this));
     }
 
 #if _LIBCPP_DEBUG_LEVEL >= 2
-
     _LIBCPP_INLINE_VISIBILITY
     __hash_iterator(const __hash_iterator& __i)
         : __node_(__i.__node_)
     {
         __get_db()->__iterator_copy(this, &__i);
     }
 
     _LIBCPP_INLINE_VISIBILITY
     ~__hash_iterator()
     {
         __get_db()->__erase_i(this);
     }
 
     _LIBCPP_INLINE_VISIBILITY
     __hash_iterator& operator=(const __hash_iterator& __i)
     {
         if (this != &__i)
         {
             __get_db()->__iterator_copy(this, &__i);
             __node_ = __i.__node_;
         }
         return *this;
     }
-
 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
 
     _LIBCPP_INLINE_VISIBILITY
-        reference operator*() const
-        {
-#if _LIBCPP_DEBUG_LEVEL >= 2
-            _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+    reference operator*() const {
+        _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
                              "Attempted to dereference a non-dereferenceable unordered container iterator");
-#endif
-            return __node_->__value_;
-        }
+        return __node_->__upcast()->__value_;
+
     _LIBCPP_INLINE_VISIBILITY
-        pointer operator->() const
-        {
-#if _LIBCPP_DEBUG_LEVEL >= 2
-            _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+    pointer operator->() const {
+        _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
                            "Attempted to dereference a non-dereferenceable unordered container iterator");
-#endif
-            return pointer_traits<pointer>::pointer_to(__node_->__value_);
-        }
+        return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);
 
     _LIBCPP_INLINE_VISIBILITY
-    __hash_iterator& operator++()
-    {
-#if _LIBCPP_DEBUG_LEVEL >= 2
-        _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+    __hash_iterator& operator++() {
+        _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
                        "Attempted to increment non-incrementable unordered container iterator");
-#endif
         __node_ = __node_->__next_;
         return *this;
     }
 
     _LIBCPP_INLINE_VISIBILITY
     __hash_iterator operator++(int)
     {
         __hash_iterator __t(*this);
         ++(*this);
         return __t;
     }
 
     friend _LIBCPP_INLINE_VISIBILITY
     bool operator==(const __hash_iterator& __x, const __hash_iterator& __y)
     {
         return __x.__node_ == __y.__node_;
     }
     friend _LIBCPP_INLINE_VISIBILITY
     bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y)
         {return !(__x == __y);}
 
 private:
 #if _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_INLINE_VISIBILITY
-    __hash_iterator(__node_pointer __node, const void* __c) _NOEXCEPT
+    __hash_iterator(__next_pointer __node, const void* __c) _NOEXCEPT
         : __node_(__node)
         {
             __get_db()->__insert_ic(this, __c);
         }
 #else
     _LIBCPP_INLINE_VISIBILITY
-    __hash_iterator(__node_pointer __node) _NOEXCEPT
+    __hash_iterator(__next_pointer __node) _NOEXCEPT
         : __node_(__node)
         {}
 #endif
-
     template <class, class, class, class> friend class __hash_table;
     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;
     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator;
     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;
 };
 
 template <class _NodePtr>
 class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator
 {
     static_assert(!is_const<typename pointer_traits<_NodePtr>::element_type>::value, "");
     typedef __hash_node_types<_NodePtr> _NodeTypes;
-    typedef _NodePtr __node_pointer;
+    typedef _NodePtr                            __node_pointer;
+    typedef typename _NodeTypes::__next_pointer __next_pointer;
 
-    __node_pointer __node_;
+    __next_pointer __node_;
 
 public:
     typedef __hash_iterator<_NodePtr> __non_const_iterator;
 
     typedef forward_iterator_tag                                 iterator_category;
     typedef typename _NodeTypes::__node_value_type               value_type;
     typedef typename _NodeTypes::difference_type                 difference_type;
     typedef const value_type&                                    reference;
     typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
 
 
-    _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT
-#if _LIBCPP_STD_VER > 11
-    : __node_(nullptr)
-#endif
-    {
-#if _LIBCPP_DEBUG_LEVEL >= 2
-        __get_db()->__insert_i(this);
-#endif
+    _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT : __node_(nullptr) {
+        _LIBCPP_DEBUG_MODE(__get_db()->__insert_i(this));
     }
+
     _LIBCPP_INLINE_VISIBILITY 
     __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT
         : __node_(__x.__node_)
     {
-#if _LIBCPP_DEBUG_LEVEL >= 2
-        __get_db()->__iterator_copy(this, &__x);
-#endif
+        _LIBCPP_DEBUG_MODE(__get_db()->__iterator_copy(this, &__x));
     }
 
 #if _LIBCPP_DEBUG_LEVEL >= 2
-
     _LIBCPP_INLINE_VISIBILITY
     __hash_const_iterator(const __hash_const_iterator& __i)
         : __node_(__i.__node_)
     {
         __get_db()->__iterator_copy(this, &__i);
     }
 
     _LIBCPP_INLINE_VISIBILITY
     ~__hash_const_iterator()
     {
         __get_db()->__erase_i(this);
     }
 
     _LIBCPP_INLINE_VISIBILITY
     __hash_const_iterator& operator=(const __hash_const_iterator& __i)
     {
         if (this != &__i)
         {
             __get_db()->__iterator_copy(this, &__i);
             __node_ = __i.__node_;
         }
         return *this;
     }
-
 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
 
     _LIBCPP_INLINE_VISIBILITY
-        reference operator*() const
-        {
-#if _LIBCPP_DEBUG_LEVEL >= 2
-            _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+    reference operator*() const {
+        _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
                            "Attempted to dereference a non-dereferenceable unordered container const_iterator");
-#endif
-            return __node_->__value_;
-        }
+        return __node_->__upcast()->__value_;
     _LIBCPP_INLINE_VISIBILITY
-        pointer operator->() const
-        {
-#if _LIBCPP_DEBUG_LEVEL >= 2
-            _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+    pointer operator->() const {
+        _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
                            "Attempted to dereference a non-dereferenceable unordered container const_iterator");
-#endif
-            return pointer_traits<pointer>::pointer_to(__node_->__value_);
-        }
+        return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);
 
     _LIBCPP_INLINE_VISIBILITY
-    __hash_const_iterator& operator++()
-    {
-#if _LIBCPP_DEBUG_LEVEL >= 2
-        _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+    __hash_const_iterator& operator++() {
+        _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
                              "Attempted to increment non-incrementable unordered container const_iterator");
-#endif
         __node_ = __node_->__next_;
         return *this;
     }
 
     _LIBCPP_INLINE_VISIBILITY
     __hash_const_iterator operator++(int)
     {
         __hash_const_iterator __t(*this);
         ++(*this);
         return __t;
     }
 
     friend _LIBCPP_INLINE_VISIBILITY
     bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
     {
         return __x.__node_ == __y.__node_;
     }
     friend _LIBCPP_INLINE_VISIBILITY
     bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
         {return !(__x == __y);}
 
 private:
 #if _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_INLINE_VISIBILITY
-    __hash_const_iterator(__node_pointer __node, const void* __c) _NOEXCEPT
+    __hash_const_iterator(__next_pointer __node, const void* __c) _NOEXCEPT
         : __node_(__node)
         {
             __get_db()->__insert_ic(this, __c);
         }
 #else
     _LIBCPP_INLINE_VISIBILITY
-    __hash_const_iterator(__node_pointer __node) _NOEXCEPT
+    __hash_const_iterator(__next_pointer __node) _NOEXCEPT
         : __node_(__node)
         {}
 #endif
-
     template <class, class, class, class> friend class __hash_table;
     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator;
     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;
 };
 
 template <class _NodePtr>
 class _LIBCPP_TYPE_VIS_ONLY __hash_local_iterator
 {
     typedef __hash_node_types<_NodePtr> _NodeTypes;
-    typedef _NodePtr                    __node_pointer;
+    typedef _NodePtr                            __node_pointer;
+    typedef typename _NodeTypes::__next_pointer __next_pointer;
 
-    __node_pointer         __node_;
+    __next_pointer         __node_;
     size_t                 __bucket_;
     size_t                 __bucket_count_;
 
 public:
     typedef forward_iterator_tag                                iterator_category;
     typedef typename _NodeTypes::__node_value_type              value_type;
     typedef typename _NodeTypes::difference_type                difference_type;
     typedef value_type&                                         reference;
     typedef typename _NodeTypes::__node_value_type_pointer      pointer;
 
-    _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT
-    {
-#if _LIBCPP_DEBUG_LEVEL >= 2
-        __get_db()->__insert_i(this);
-#endif
+    _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT : __node_(nullptr) {
+        _LIBCPP_DEBUG_MODE(__get_db()->__insert_i(this));
     }
 
 #if _LIBCPP_DEBUG_LEVEL >= 2
-
     _LIBCPP_INLINE_VISIBILITY
     __hash_local_iterator(const __hash_local_iterator& __i)
         : __node_(__i.__node_),
           __bucket_(__i.__bucket_),
           __bucket_count_(__i.__bucket_count_)
     {
         __get_db()->__iterator_copy(this, &__i);
     }
__hash_local_iterator& operator=(const __hash_local_iterator& __i)
         {
             __get_db()->__iterator_copy(this, &__i);
             __node_ = __i.__node_;
             __bucket_ = __i.__bucket_;
             __bucket_count_ = __i.__bucket_count_;
         }
         return *this;
     }
-
 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
 
     _LIBCPP_INLINE_VISIBILITY
-        reference operator*() const
-        {
-#if _LIBCPP_DEBUG_LEVEL >= 2
-            _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+    reference operator*() const {
+        _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
                            "Attempted to dereference a non-dereferenceable unordered container local_iterator");
-#endif
-            return __node_->__value_;
-        }
+        return __node_->__upcast()->__value_;
+
     _LIBCPP_INLINE_VISIBILITY
-        pointer operator->() const
-        {
-#if _LIBCPP_DEBUG_LEVEL >= 2
-            _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+    pointer operator->() const {
+        _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
                              "Attempted to dereference a non-dereferenceable unordered container local_iterator");
-#endif
-            return pointer_traits<pointer>::pointer_to(__node_->__value_);
-        }
+        return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);
 
     _LIBCPP_INLINE_VISIBILITY
-    __hash_local_iterator& operator++()
-    {
-#if _LIBCPP_DEBUG_LEVEL >= 2
-        _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+    __hash_local_iterator& operator++() {
+        _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
                        "Attempted to increment non-incrementable unordered container local_iterator");
-#endif
         __node_ = __node_->__next_;
-        if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_)
+        if (__node_ != nullptr && __constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)
             __node_ = nullptr;
         return *this;
     }
 
     _LIBCPP_INLINE_VISIBILITY
     __hash_local_iterator operator++(int)
     {
         __hash_local_iterator __t(*this);
         ++(*this);
         return __t;
     }
 
     friend _LIBCPP_INLINE_VISIBILITY
     bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
     {
         return __x.__node_ == __y.__node_;
     }
     friend _LIBCPP_INLINE_VISIBILITY
     bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
         {return !(__x == __y);}
 
 private:
 #if _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_INLINE_VISIBILITY
-    __hash_local_iterator(__node_pointer __node, size_t __bucket,
+    __hash_local_iterator(__next_pointer __node, size_t __bucket,
                           size_t __bucket_count, const void* __c) _NOEXCEPT
         : __node_(__node),
           __bucket_(__bucket),
           __bucket_count_(__bucket_count)
         {
             __get_db()->__insert_ic(this, __c);
             if (__node_ != nullptr)
                 __node_ = __node_->__next_;
         }
 #else
     _LIBCPP_INLINE_VISIBILITY
-    __hash_local_iterator(__node_pointer __node, size_t __bucket,
+    __hash_local_iterator(__next_pointer __node, size_t __bucket,
                           size_t __bucket_count) _NOEXCEPT
         : __node_(__node),
           __bucket_(__bucket),
           __bucket_count_(__bucket_count)
         {
             if (__node_ != nullptr)
                 __node_ = __node_->__next_;
         }
 #endif
     template <class, class, class, class> friend class __hash_table;
     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;
     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator;
 };
 
 template <class _ConstNodePtr>
 class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator
 {
     typedef __hash_node_types<_ConstNodePtr> _NodeTypes;
-    typedef _ConstNodePtr                    __node_pointer;
+    typedef _ConstNodePtr                       __node_pointer;
+    typedef typename _NodeTypes::__next_pointer __next_pointer;
 
-    __node_pointer         __node_;
+    __next_pointer         __node_;
     size_t                 __bucket_;
     size_t                 __bucket_count_;
 
     typedef pointer_traits<__node_pointer>          __pointer_traits;
     typedef typename __pointer_traits::element_type __node;
     typedef typename remove_const<__node>::type     __non_const_node;
     typedef typename __rebind_pointer<__node_pointer, __non_const_node>::type
         __non_const_node_pointer;
 public:
     typedef __hash_local_iterator<__non_const_node_pointer>
                                                     __non_const_iterator;
 
     typedef forward_iterator_tag                                 iterator_category;
     typedef typename _NodeTypes::__node_value_type               value_type;
     typedef typename _NodeTypes::difference_type                 difference_type;
     typedef const value_type&                                    reference;
     typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
 
 
-    _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT
-    {
-#if _LIBCPP_DEBUG_LEVEL >= 2
-        __get_db()->__insert_i(this);
-#endif
+    _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT : __node_(nullptr) {
+        _LIBCPP_DEBUG_MODE(__get_db()->__insert_i(this));
     }
 
     _LIBCPP_INLINE_VISIBILITY
     __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT
         : __node_(__x.__node_),
           __bucket_(__x.__bucket_),
           __bucket_count_(__x.__bucket_count_)
     {
-#if _LIBCPP_DEBUG_LEVEL >= 2
-        __get_db()->__iterator_copy(this, &__x);
-#endif
+        _LIBCPP_DEBUG_MODE(__get_db()->__iterator_copy(this, &__x));
     }
 
 #if _LIBCPP_DEBUG_LEVEL >= 2
-
     _LIBCPP_INLINE_VISIBILITY
     __hash_const_local_iterator(const __hash_const_local_iterator& __i)
         : __node_(__i.__node_),
           __bucket_(__i.__bucket_),
           __bucket_count_(__i.__bucket_count_)
     {
         __get_db()->__iterator_copy(this, &__i);
     }
__hash_const_local_iterator& operator=(const __hash_const_local_iterator& __i)
         {
             __get_db()->__iterator_copy(this, &__i);
             __node_ = __i.__node_;
             __bucket_ = __i.__bucket_;
             __bucket_count_ = __i.__bucket_count_;
         }
         return *this;
     }
-
 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
 
     _LIBCPP_INLINE_VISIBILITY
-        reference operator*() const
-        {
-#if _LIBCPP_DEBUG_LEVEL >= 2
-            _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+    reference operator*() const {
+        _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
                            "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
-#endif
-            return __node_->__value_;
-        }
+        return __node_->__upcast()->__value_;
+
     _LIBCPP_INLINE_VISIBILITY
-        pointer operator->() const
-        {
-#if _LIBCPP_DEBUG_LEVEL >= 2
-            _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+    pointer operator->() const {
+        _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
                            "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
-#endif
-            return pointer_traits<pointer>::pointer_to(__node_->__value_);
-        }
+        return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);
 
     _LIBCPP_INLINE_VISIBILITY
-    __hash_const_local_iterator& operator++()
-    {
-#if _LIBCPP_DEBUG_LEVEL >= 2
-        _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
+    __hash_const_local_iterator& operator++() {
+        _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
                        "Attempted to increment non-incrementable unordered container const_local_iterator");
-#endif
         __node_ = __node_->__next_;
-        if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_)
+        if (__node_ != nullptr && __constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)
             __node_ = nullptr;
         return *this;
     }
 
     _LIBCPP_INLINE_VISIBILITY
     __hash_const_local_iterator operator++(int)
     {
         __hash_const_local_iterator __t(*this);
         ++(*this);
         return __t;
     }
 
     friend _LIBCPP_INLINE_VISIBILITY
     bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
     {
         return __x.__node_ == __y.__node_;
     }
     friend _LIBCPP_INLINE_VISIBILITY
     bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
         {return !(__x == __y);}
 
 private:
 #if _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_INLINE_VISIBILITY
-    __hash_const_local_iterator(__node_pointer __node, size_t __bucket,
+    __hash_const_local_iterator(__next_pointer __node, size_t __bucket,
                                 size_t __bucket_count, const void* __c) _NOEXCEPT
         : __node_(__node),
           __bucket_(__bucket),
           __bucket_count_(__bucket_count)
         {
             __get_db()->__insert_ic(this, __c);
             if (__node_ != nullptr)
                 __node_ = __node_->__next_;
         }
 #else
     _LIBCPP_INLINE_VISIBILITY
-    __hash_const_local_iterator(__node_pointer __node, size_t __bucket,
+    __hash_const_local_iterator(__next_pointer __node, size_t __bucket,
                                 size_t __bucket_count) _NOEXCEPT
         : __node_(__node),
           __bucket_(__bucket),
           __bucket_count_(__bucket_count)
         {
             if (__node_ != nullptr)
                 __node_ = __node_->__next_;
         }
public:
     typedef typename _NodeTypes::__node_type __node;
     typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator;
     typedef allocator_traits<__node_allocator>       __node_traits;
     typedef typename _NodeTypes::__void_pointer      __void_pointer;
     typedef typename _NodeTypes::__node_pointer      __node_pointer;
     typedef typename _NodeTypes::__node_pointer      __node_const_pointer;
     typedef typename _NodeTypes::__node_base_type    __first_node;
     typedef typename _NodeTypes::__node_base_pointer __node_base_pointer;
+    typedef typename _NodeTypes::__next_pointer      __next_pointer;
 
 private:
     // check for sane allocator pointer rebinding semantics. Rebinding the
     // 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, __first_node>::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:
 
-    typedef typename __rebind_alloc_helper<__node_traits, __node_pointer>::type __pointer_allocator;
+    typedef typename __rebind_alloc_helper<__node_traits, __next_pointer>::type __pointer_allocator;
     typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter;
-    typedef unique_ptr<__node_pointer[], __bucket_list_deleter> __bucket_list;
+    typedef unique_ptr<__next_pointer[], __bucket_list_deleter> __bucket_list;
     typedef allocator_traits<__pointer_allocator>          __pointer_alloc_traits;
-    typedef typename __bucket_list_deleter::pointer __node_pointer_pointer;
+    typedef typename __bucket_list_deleter::pointer       __node_pointer_pointer;
 
     // --- Member data begin ---
     __bucket_list                                         __bucket_list_;
     __compressed_pair<__first_node, __node_allocator>     __p1_;
     __compressed_pair<size_type, hasher>                  __p2_;
     __compressed_pair<float, key_equal>                   __p3_;
     // --- Member data end ---
 
void __move_assign_alloc(__hash_table& __u, true_type)
         __bucket_list_.get_deleter().__alloc() =
                 _VSTD::move(__u.__bucket_list_.get_deleter().__alloc());
         __node_alloc() = _VSTD::move(__u.__node_alloc());
     }
     _LIBCPP_INLINE_VISIBILITY
         void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {}
 #endif // _LIBCPP_CXX03_LANG
 
-    void __deallocate(__node_pointer __np) _NOEXCEPT;
-    __node_pointer __detach() _NOEXCEPT;
+    void __deallocate(__next_pointer __np) _NOEXCEPT;
+    __next_pointer __detach() _NOEXCEPT;
 
     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;
 };
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 inline
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table()
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u)
             is_nothrow_move_constructible<key_equal>::value)
     : __bucket_list_(_VSTD::move(__u.__bucket_list_)),
       __p1_(_VSTD::move(__u.__p1_)),
       __p2_(_VSTD::move(__u.__p2_)),
       __p3_(_VSTD::move(__u.__p3_))
 {
     if (size() > 0)
     {
-        __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
-            static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
+        __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
+            __p1_.first().__ptr();
         __u.__p1_.first().__next_ = nullptr;
         __u.size() = 0;
     }
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u,
                                                        const allocator_type& __a)
     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
       __p1_(__node_allocator(__a)),
       __p2_(0, _VSTD::move(__u.hash_function())),
       __p3_(_VSTD::move(__u.__p3_))
 {
     if (__a == allocator_type(__u.__node_alloc()))
     {
         __bucket_list_.reset(__u.__bucket_list_.release());
         __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
         __u.__bucket_list_.get_deleter().size() = 0;
         if (__u.size() > 0)
         {
             __p1_.first().__next_ = __u.__p1_.first().__next_;
             __u.__p1_.first().__next_ = nullptr;
-            __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
-                static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
+            __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
+                __p1_.first().__ptr();
             size() = __u.size();
             __u.size() = 0;
         }
     }
 }
 
 #endif  // _LIBCPP_CXX03_LANG
 
if (this != &__u)
         max_load_factor() = __u.max_load_factor();
         __assign_multi(__u.begin(), __u.end());
     }
     return *this;
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np)
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__next_pointer __np)
     _NOEXCEPT
 {
     __node_allocator& __na = __node_alloc();
     while (__np != nullptr)
     {
-        __node_pointer __next = __np->__next_;
+        __next_pointer __next = __np->__next_;
 #if _LIBCPP_DEBUG_LEVEL >= 2
         __c_node* __c = __get_db()->__find_c_and_lock(this);
         for (__i_node** __p = __c->end_; __p != __c->beg_; )
         {
             --__p;
             iterator* __i = static_cast<iterator*>((*__p)->__i_);
             if (__i->__node_ == __np)
             {
                 (*__p)->__c_ = nullptr;
                 if (--__c->end_ != __p)
                     memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
             }
         }
         __get_db()->unlock();
 #endif
-        __node_traits::destroy(__na, _NodeTypes::__get_ptr(__np->__value_));
-        __node_traits::deallocate(__na, __np, 1);
+        __node_pointer __real_np = __np->__upcast();
+        __node_traits::destroy(__na, _NodeTypes::__get_ptr(__real_np->__value_));
+        __node_traits::deallocate(__na, __real_np, 1);
         __np = __next;
     }
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT
 {
     size_type __bc = bucket_count();
     for (size_type __i = 0; __i < __bc; ++__i)
         __bucket_list_[__i] = nullptr;
     size() = 0;
-    __node_pointer __cache = __p1_.first().__next_;
+    __next_pointer __cache = __p1_.first().__next_;
     __p1_.first().__next_ = nullptr;
     return __cache;
 }
 
 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 void
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
     __move_assign_alloc(__u);
     size() = __u.size();
     hash_function() = _VSTD::move(__u.hash_function());
     max_load_factor() = __u.max_load_factor();
     key_eq() = _VSTD::move(__u.key_eq());
     __p1_.first().__next_ = __u.__p1_.first().__next_;
     if (size() > 0)
     {
-        __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
-            static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
+        __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
+            __p1_.first().__ptr();
         __u.__p1_.first().__next_ = nullptr;
         __u.size() = 0;
     }
 #if _LIBCPP_DEBUG_LEVEL >= 2
     __get_db()->swap(this, &__u);
 #endif
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 void
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
         __hash_table& __u, false_type)
 {
     if (__node_alloc() == __u.__node_alloc())
         __move_assign(__u, true_type());
     else
     {
         hash_function() = _VSTD::move(__u.hash_function());
         key_eq() = _VSTD::move(__u.key_eq());
         max_load_factor() = __u.max_load_factor();
         if (bucket_count() != 0)
         {
-            __node_pointer __cache = __detach();
+            __next_pointer __cache = __detach();
 #ifndef _LIBCPP_NO_EXCEPTIONS
             try
             {
 #endif  // _LIBCPP_NO_EXCEPTIONS
                 const_iterator __i = __u.begin();
                 while (__cache != nullptr && __u.size() != 0)
                 {
-                    __cache->__value_ = _VSTD::move(__u.remove(__i++)->__value_);
-                    __node_pointer __next = __cache->__next_;
-                    __node_insert_multi(__cache);
+                    __cache->__upcast()->__value_ =
+                        _VSTD::move(__u.remove(__i++)->__value_);
+                    __next_pointer __next = __cache->__next_;
+                    __node_insert_multi(__cache->__upcast());
                     __cache = __next;
                 }
 #ifndef _LIBCPP_NO_EXCEPTIONS
             }
             catch (...)
             {
                 __deallocate(__cache);
                 throw;

 {
     typedef iterator_traits<_InputIterator> _ITraits;
     typedef typename _ITraits::value_type _ItValueType;
     static_assert((is_same<_ItValueType, __container_value_type>::value),
                   "__assign_unique may only be called with the containers value type");
 
     if (bucket_count() != 0)
     {
-        __node_pointer __cache = __detach();
+        __next_pointer __cache = __detach();
 #ifndef _LIBCPP_NO_EXCEPTIONS
         try
         {
 #endif  // _LIBCPP_NO_EXCEPTIONS
             for (; __cache != nullptr && __first != __last; ++__first)
             {
-                __cache->__value_ = *__first;
-                __node_pointer __next = __cache->__next_;
-                __node_insert_unique(__cache);
+                __cache->__upcast()->__value_ = *__first;
+                __next_pointer __next = __cache->__next_;
+                __node_insert_unique(__cache->__upcast());
                 __cache = __next;
             }
 #ifndef _LIBCPP_NO_EXCEPTIONS
         }
         catch (...)
         {
             __deallocate(__cache);
             throw;
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first,
     typedef iterator_traits<_InputIterator> _ITraits;
     typedef typename _ITraits::value_type _ItValueType;
     static_assert((is_same<_ItValueType, __container_value_type>::value ||
                   is_same<_ItValueType, __node_value_type>::value),
                   "__assign_multi may only be called with the containers value type"
                   " or the nodes value type");
     if (bucket_count() != 0)
     {
-        __node_pointer __cache = __detach();
+        __next_pointer __cache = __detach();
 #ifndef _LIBCPP_NO_EXCEPTIONS
         try
         {
 #endif  // _LIBCPP_NO_EXCEPTIONS
             for (; __cache != nullptr && __first != __last; ++__first)
             {
-                __cache->__value_ = *__first;
-                __node_pointer __next = __cache->__next_;
-                __node_insert_multi(__cache);
+                __cache->__upcast()->__value_ = *__first;
+                __next_pointer __next = __cache->__next_;
+                __node_insert_multi(__cache->__upcast());
                 __cache = __next;
             }
 #ifndef _LIBCPP_NO_EXCEPTIONS
         }
         catch (...)
         {
             __deallocate(__cache);
             throw;

 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd)
 {
     __nd->__hash_ = hash_function()(__nd->__value_);
     size_type __bc = bucket_count();
     bool __inserted = false;
-    __node_pointer __ndptr;
+    __next_pointer __ndptr;
     size_t __chash;
     if (__bc != 0)
     {
         __chash = __constrain_hash(__nd->__hash_, __bc);
         __ndptr = __bucket_list_[__chash];
         if (__ndptr != nullptr)
         {
             for (__ndptr = __ndptr->__next_; __ndptr != nullptr &&
-                                             __constrain_hash(__ndptr->__hash_, __bc) == __chash;
+                                             __constrain_hash(__ndptr->__hash(), __bc) == __chash;
                                                      __ndptr = __ndptr->__next_)
             {
-                if (key_eq()(__ndptr->__value_, __nd->__value_))
+                if (key_eq()(__ndptr->__upcast()->__value_, __nd->__value_))
                     goto __done;
             }
         }
     }
     {
         if (size()+1 > __bc * max_load_factor() || __bc == 0)
         {
             rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
                            size_type(ceil(float(size() + 1) / max_load_factor()))));
             __bc = bucket_count();
             __chash = __constrain_hash(__nd->__hash_, __bc);
         }
         // insert_after __bucket_list_[__chash], or __first_node if bucket is null
-        __node_pointer __pn = __bucket_list_[__chash];
+        __next_pointer __pn = __bucket_list_[__chash];
         if (__pn == nullptr)
         {
-            __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
+            __pn =__p1_.first().__ptr();
             __nd->__next_ = __pn->__next_;
-            __pn->__next_ = __nd;
+            __pn->__next_ = __nd->__ptr();
             // fix up __bucket_list_
             __bucket_list_[__chash] = __pn;
             if (__nd->__next_ != nullptr)
-                __bucket_list_[__constrain_hash(__nd->__next_->__hash_, __bc)] = __nd;
+                __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr();
         }
         else
         {
             __nd->__next_ = __pn->__next_;
-            __pn->__next_ = __nd;
+            __pn->__next_ = __nd->__ptr();
         }
-        __ndptr = __nd;
+        __ndptr = __nd->__ptr();
         // increment size
         ++size();
         __inserted = true;
     }
 __done:
 #if _LIBCPP_DEBUG_LEVEL >= 2
     return pair<iterator, bool>(iterator(__ndptr, this), __inserted);
 #else
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp)
     size_type __bc = bucket_count();
     if (size()+1 > __bc * max_load_factor() || __bc == 0)
     {
         rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
                        size_type(ceil(float(size() + 1) / max_load_factor()))));
         __bc = bucket_count();
     }
     size_t __chash = __constrain_hash(__cp->__hash_, __bc);
-    __node_pointer __pn = __bucket_list_[__chash];
+    __next_pointer __pn = __bucket_list_[__chash];
     if (__pn == nullptr)
     {
-        __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
+        __pn =__p1_.first().__ptr();
         __cp->__next_ = __pn->__next_;
-        __pn->__next_ = __cp;
+        __pn->__next_ = __cp->__ptr();
         // fix up __bucket_list_
         __bucket_list_[__chash] = __pn;
         if (__cp->__next_ != nullptr)
-            __bucket_list_[__constrain_hash(__cp->__next_->__hash_, __bc)] = __cp;
+            __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)]
+                = __cp->__ptr();
     }
     else
     {
         for (bool __found = false; __pn->__next_ != nullptr &&
-                                   __constrain_hash(__pn->__next_->__hash_, __bc) == __chash;
+                                   __constrain_hash(__pn->__next_->__hash(), __bc) == __chash;
                                                            __pn = __pn->__next_)
         {
             //      __found    key_eq()     action
             //      false       false       loop
             //      true        true        loop
             //      false       true        set __found to true
             //      true        false       break
-            if (__found != (__pn->__next_->__hash_ == __cp->__hash_ &&
-                            key_eq()(__pn->__next_->__value_, __cp->__value_)))
+            if (__found != (__pn->__next_->__hash() == __cp->__hash_ &&
+                            key_eq()(__pn->__next_->__upcast()->__value_, __cp->__value_)))
             {
                 if (!__found)
                     __found = true;
                 else
                     break;
             }
         }
         __cp->__next_ = __pn->__next_;
-        __pn->__next_ = __cp;
+        __pn->__next_ = __cp->__ptr();
         if (__cp->__next_ != nullptr)
         {
-            size_t __nhash = __constrain_hash(__cp->__next_->__hash_, __bc);
+            size_t __nhash = __constrain_hash(__cp->__next_->__hash(), __bc);
             if (__nhash != __chash)
-                __bucket_list_[__nhash] = __cp;
+                __bucket_list_[__nhash] = __cp->__ptr();
         }
     }
     ++size();
 #if _LIBCPP_DEBUG_LEVEL >= 2
-    return iterator(__cp, this);
+    return iterator(__cp->__ptr(), this);
 #else
-    return iterator(__cp);
+    return iterator(__cp->__ptr());
 #endif
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(
         const_iterator __p, __node_pointer __cp)
 {
 #if _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
         "unordered container::emplace_hint(const_iterator, args...) called with an iterator not"
         " referring to this unordered container");
 #endif
     if (__p != end() && key_eq()(*__p, __cp->__value_))
     {
-        __node_pointer __np = __p.__node_;
-        __cp->__hash_ = __np->__hash_;
+        __next_pointer __np = __p.__node_;
+        __cp->__hash_ = __np->__hash();
         size_type __bc = bucket_count();
         if (size()+1 > __bc * max_load_factor() || __bc == 0)
         {
             rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
                            size_type(ceil(float(size() + 1) / max_load_factor()))));
             __bc = bucket_count();
         }
         size_t __chash = __constrain_hash(__cp->__hash_, __bc);
-        __node_pointer __pp = __bucket_list_[__chash];
+        __next_pointer __pp = __bucket_list_[__chash];
         while (__pp->__next_ != __np)
             __pp = __pp->__next_;
         __cp->__next_ = __np;
-        __pp->__next_ = __cp;
+        __pp->__next_ = static_cast<__next_pointer>(__cp);
         ++size();
 #if _LIBCPP_DEBUG_LEVEL >= 2
-        return iterator(__cp, this);
+        return iterator(static_cast<__next_pointer>(__cp), this);
 #else
-        return iterator(__cp);
+        return iterator(static_cast<__next_pointer>(__cp));
 #endif
     }
     return __node_insert_multi(__cp);
 }
 
 
 
 #ifndef _LIBCPP_CXX03_LANG

 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args& __args)
 #endif
 {
 
     size_t __hash = hash_function()(__k);
     size_type __bc = bucket_count();
     bool __inserted = false;
-    __node_pointer __nd;
+    __next_pointer __nd;
     size_t __chash;
     if (__bc != 0)
     {
         __chash = __constrain_hash(__hash, __bc);
         __nd = __bucket_list_[__chash];
         if (__nd != nullptr)
         {
             for (__nd = __nd->__next_; __nd != nullptr &&
-                                       __constrain_hash(__nd->__hash_, __bc) == __chash;
+                                       __constrain_hash(__nd->__hash(), __bc) == __chash;
                                                            __nd = __nd->__next_)
             {
-                if (key_eq()(__nd->__value_, __k))
+                if (key_eq()(__nd->__upcast()->__value_, __k))
                     goto __done;
             }
         }
     }
     {
 #ifndef _LIBCPP_CXX03_LANG
         __node_holder __h = __construct_node_hash(__hash, _VSTD::forward<_Args>(__args)...);
 #else
         __node_holder __h = __construct_node_hash(__hash, __args);
 #endif
         if (size()+1 > __bc * max_load_factor() || __bc == 0)
         {
             rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
                            size_type(ceil(float(size() + 1) / max_load_factor()))));
             __bc = bucket_count();
             __chash = __constrain_hash(__hash, __bc);
         }
         // insert_after __bucket_list_[__chash], or __first_node if bucket is null
-        __node_pointer __pn = __bucket_list_[__chash];
+        __next_pointer __pn = __bucket_list_[__chash];
         if (__pn == nullptr)
         {
-            __pn = static_cast<__node_pointer>(static_cast<__void_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())));
+            __pn = __p1_.first().__ptr();
             __h->__next_ = __pn->__next_;
-            __pn->__next_ = __h.get();
+            __pn->__next_ = __h.get()->__ptr();
             // fix up __bucket_list_
             __bucket_list_[__chash] = __pn;
             if (__h->__next_ != nullptr)
-                __bucket_list_[__constrain_hash(__h->__next_->__hash_, __bc)] = __h.get();
+                __bucket_list_[__constrain_hash(__h->__next_->__hash(), __bc)]
+                    = __h.get()->__ptr();
         }
         else
         {
             __h->__next_ = __pn->__next_;
-            __pn->__next_ = __h.get();
+            __pn->__next_ = static_cast<__next_pointer>(__h.get());
         }
-        __nd = __h.release();
+        __nd = static_cast<__next_pointer>(__h.release());
         // increment size
         ++size();
         __inserted = true;
     }
 __done:
 #if _LIBCPP_DEBUG_LEVEL >= 2
     return pair<iterator, bool>(iterator(__nd, this), __inserted);
 #else
#endif  // _LIBCPP_DEBUG_LEVEL >= 2
     __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc();
     __bucket_list_.reset(__nbc > 0 ?
                       __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr);
     __bucket_list_.get_deleter().size() = __nbc;
     if (__nbc > 0)
     {
         for (size_type __i = 0; __i < __nbc; ++__i)
             __bucket_list_[__i] = nullptr;
-        __node_pointer __pp(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())));
-        __node_pointer __cp = __pp->__next_;
+        __next_pointer __pp = __p1_.first().__ptr();
+        __next_pointer __cp = __pp->__next_;
         if (__cp != nullptr)
         {
-            size_type __chash = __constrain_hash(__cp->__hash_, __nbc);
+            size_type __chash = __constrain_hash(__cp->__hash(), __nbc);
             __bucket_list_[__chash] = __pp;
             size_type __phash = __chash;
             for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr;
                                                            __cp = __pp->__next_)
             {
-                __chash = __constrain_hash(__cp->__hash_, __nbc);
+                __chash = __constrain_hash(__cp->__hash(), __nbc);
                 if (__chash == __phash)
                     __pp = __cp;
                 else
                 {
                     if (__bucket_list_[__chash] == nullptr)
                     {
                         __bucket_list_[__chash] = __pp;
                         __pp = __cp;
                         __phash = __chash;
                     }
                     else
                     {
-                        __node_pointer __np = __cp;
+                        __next_pointer __np = __cp;
                         for (; __np->__next_ != nullptr &&
-                               key_eq()(__cp->__value_, __np->__next_->__value_);
+                               key_eq()(__cp->__upcast()->__value_,
+                                        __np->__next_->__upcast()->__value_);
                                                            __np = __np->__next_)
                             ;
                         __pp->__next_ = __np->__next_;
                         __np->__next_ = __bucket_list_[__chash]->__next_;
                         __bucket_list_[__chash]->__next_ = __cp;
 
                     }
                 }
             }
         }
     }
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _Key>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k)
 {
     size_t __hash = hash_function()(__k);
     size_type __bc = bucket_count();
     if (__bc != 0)
     {
         size_t __chash = __constrain_hash(__hash, __bc);
-        __node_pointer __nd = __bucket_list_[__chash];
+        __next_pointer __nd = __bucket_list_[__chash];
         if (__nd != nullptr)
         {
             for (__nd = __nd->__next_; __nd != nullptr &&
-                (__nd->__hash_ == __hash
-                  || __constrain_hash(__nd->__hash_, __bc) == __chash);
+                (__nd->__hash() == __hash
+                  || __constrain_hash(__nd->__hash(), __bc) == __chash);
                                                            __nd = __nd->__next_)
             {
-                if ((__nd->__hash_ == __hash) && key_eq()(__nd->__value_, __k))
+                if ((__nd->__hash() == __hash)
+                    && key_eq()(__nd->__upcast()->__value_, __k))
 #if _LIBCPP_DEBUG_LEVEL >= 2
                     return iterator(__nd, this);
 #else
                     return iterator(__nd);
 #endif
             }
         }
     }
     return end();
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _Key>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const
 {
     size_t __hash = hash_function()(__k);
     size_type __bc = bucket_count();
     if (__bc != 0)
     {
         size_t __chash = __constrain_hash(__hash, __bc);
-        __node_const_pointer __nd = __bucket_list_[__chash];
+        __next_pointer __nd = __bucket_list_[__chash];
         if (__nd != nullptr)
         {
             for (__nd = __nd->__next_; __nd != nullptr &&
-                (__hash == __nd->__hash_ || __constrain_hash(__nd->__hash_, __bc) == __chash);
+                (__hash == __nd->__hash()
+                    || __constrain_hash(__nd->__hash(), __bc) == __chash);
                                                            __nd = __nd->__next_)
             {
-                if ((__nd->__hash_ == __hash) && key_eq()(__nd->__value_, __k))
+                if ((__nd->__hash() == __hash)
+                    && key_eq()(__nd->__upcast()->__value_, __k))
 #if _LIBCPP_DEBUG_LEVEL >= 2
                     return const_iterator(__nd, this);
 #else
                     return const_iterator(__nd);
 #endif
             }
         }
 

 }
 
 #endif  // _LIBCPP_CXX03_LANG
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p)
 {
-    __node_pointer __np = __p.__node_;
+    __next_pointer __np = __p.__node_;
 #if _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
         "unordered container erase(iterator) called with an iterator not"
         " referring to this container");
     _LIBCPP_ASSERT(__p != end(),
         "unordered container erase(iterator) called with a non-dereferenceable iterator");
     iterator __r(__np, this);
 #else
_LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this,
         "unodered container::erase(iterator, iterator) called with an iterator not"
         " referring to this unodered container");
 #endif
     for (const_iterator __p = __first; __first != __last; __p = __first)
     {
         ++__first;
         erase(__p);
     }
-    __node_pointer __np = __last.__node_;
+    __next_pointer __np = __last.__node_;
 #if _LIBCPP_DEBUG_LEVEL >= 2
     return iterator (__np, this);
 #else
     return iterator (__np);
 #endif
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k)
     return __r;
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT
 {
     // current node
-    __node_pointer __cn = __p.__node_;
+    __next_pointer __cn = __p.__node_;
     size_type __bc = bucket_count();
-    size_t __chash = __constrain_hash(__cn->__hash_, __bc);
+    size_t __chash = __constrain_hash(__cn->__hash(), __bc);
     // find previous node
-    __node_pointer __pn = __bucket_list_[__chash];
+    __next_pointer __pn = __bucket_list_[__chash];
     for (; __pn->__next_ != __cn; __pn = __pn->__next_)
         ;
     // Fix up __bucket_list_
         // if __pn is not in same bucket (before begin is not in same bucket) &&
         //    if __cn->__next_ is not in same bucket (nullptr is not in same bucket)
-    if (__pn == static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()))
-                            || __constrain_hash(__pn->__hash_, __bc) != __chash)
+    if (__pn == __p1_.first().__ptr()
+            || __constrain_hash(__pn->__hash(), __bc) != __chash)
     {
-        if (__cn->__next_ == nullptr || __constrain_hash(__cn->__next_->__hash_, __bc) != __chash)
+        if (__cn->__next_ == nullptr
+            || __constrain_hash(__cn->__next_->__hash(), __bc) != __chash)
             __bucket_list_[__chash] = nullptr;
     }
         // if __cn->__next_ is not in same bucket (nullptr is in same bucket)
     if (__cn->__next_ != nullptr)
     {
-        size_t __nhash = __constrain_hash(__cn->__next_->__hash_, __bc);
+        size_t __nhash = __constrain_hash(__cn->__next_->__hash(), __bc);
         if (__nhash != __chash)
             __bucket_list_[__nhash] = __pn;
     }
     // remove __cn
     __pn->__next_ = __cn->__next_;
     __cn->__next_ = nullptr;
     --size();
 #if _LIBCPP_DEBUG_LEVEL >= 2
     __c_node* __c = __get_db()->__find_c_and_lock(this);
     for (__i_node** __p = __c->end_; __p != __c->beg_; )
     {
         --__p;
         iterator* __i = static_cast<iterator*>((*__p)->__i_);
         if (__i->__node_ == __cn)
         {
             (*__p)->__c_ = nullptr;
             if (--__c->end_ != __p)
                 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
         }
     }
     __get_db()->unlock();
 #endif
-    return __node_holder(__cn, _Dp(__node_alloc(), true));
+    return __node_holder(__cn->__upcast(), _Dp(__node_alloc(), true));
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _Key>
 inline
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const
 {
#endif
     _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size());
     __swap_allocator(__bucket_list_.get_deleter().__alloc(),
              __u.__bucket_list_.get_deleter().__alloc());
     __swap_allocator(__node_alloc(), __u.__node_alloc());
     _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_);
     __p2_.swap(__u.__p2_);
     __p3_.swap(__u.__p3_);
     if (size() > 0)
-        __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
-            static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
+        __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
+            __p1_.first().__ptr();
     if (__u.size() > 0)
-        __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] =
-            static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__u.__p1_.first()));
+        __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash(), __u.bucket_count())] =
+            __u.__p1_.first().__ptr();
 #if _LIBCPP_DEBUG_LEVEL >= 2
     __get_db()->swap(this, &__u);
 #endif
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const
 {
     _LIBCPP_ASSERT(__n < bucket_count(),
         "unordered container::bucket_size(n) called with n >= bucket_count()");
-    __node_const_pointer __np = __bucket_list_[__n];
+    __next_pointer __np = __bucket_list_[__n];
     size_type __bc = bucket_count();
     size_type __r = 0;
     if (__np != nullptr)
     {
         for (__np = __np->__next_; __np != nullptr &&
-                                   __constrain_hash(__np->__hash_, __bc) == __n;
+                                   __constrain_hash(__np->__hash(), __bc) == __n;
                                                     __np = __np->__next_, ++__r)
             ;
     }
     return __r;
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 inline _LIBCPP_INLINE_VISIBILITY

test/libcxx/test/config.py

def configure_sanitizer(self):
                 if san == 'MemoryWithOrigins':
                     self.cxx.compile_flags += [
                         '-fsanitize-memory-track-origins']
                 if llvm_symbolizer is not None:
                     self.env['MSAN_SYMBOLIZER_PATH'] = llvm_symbolizer
                 self.config.available_features.add('msan')
                 self.config.available_features.add('sanitizer-new-delete')
             elif san == 'Undefined':
-                blacklist = os.path.join(self.libcxx_src_root,
-                                         'test/ubsan_blacklist.txt')
                 self.cxx.flags += ['-fsanitize=undefined',
                                    '-fno-sanitize=vptr,function,float-divide-by-zero',
-                                   '-fno-sanitize-recover=all',
-                                   '-fsanitize-blacklist=' + blacklist]
-                self.cxx.compile_flags += ['-O3']
+                                   '-fno-sanitize-recover=all']
+                self.cxx.compile_flags += ['-O2']
                 self.env['UBSAN_OPTIONS'] = 'print_stacktrace=1'
                 self.config.available_features.add('ubsan')
             elif san == 'Thread':
                 self.cxx.flags += ['-fsanitize=thread']
                 self.config.available_features.add('tsan')
                 self.config.available_features.add('sanitizer-new-delete')
             else:
                 self.lit_config.fatal('unsupported value for '

test/ubsan_blacklist.txt

-fun:*__hash_table*