Index: include/list =================================================================== --- include/list +++ include/list @@ -191,21 +191,25 @@ template struct __list_node_base { - typedef typename __rebind_pointer<_VoidPtr, __list_node<_Tp, _VoidPtr> >::type - pointer; typedef typename __rebind_pointer<_VoidPtr, __list_node_base>::type - __base_pointer; - - pointer __prev_; - pointer __next_; + __node_base_pointer; + typedef typename __rebind_pointer<_VoidPtr, __list_node<_Tp, _VoidPtr> >::type + __node_pointer; + __node_base_pointer __prev_; + __node_base_pointer __next_; _LIBCPP_INLINE_VISIBILITY - __list_node_base() : __prev_(__self()), __next_(__self()) {} + __list_node_base() : __prev_(__as_base()), __next_(__as_base()) {} _LIBCPP_INLINE_VISIBILITY - pointer __self() + __node_base_pointer __as_base() + { + return pointer_traits<__node_base_pointer>::pointer_to(*this); + } + _LIBCPP_INLINE_VISIBILITY + __node_pointer __as_node() { - return static_cast(pointer_traits<__base_pointer>::pointer_to(*this)); + return static_cast<__node_pointer>(__as_base()); } }; @@ -223,21 +227,21 @@ template class _LIBCPP_TYPE_VIS_ONLY __list_iterator { - typedef typename __rebind_pointer<_VoidPtr, __list_node<_Tp, _VoidPtr> >::type - __node_pointer; + typedef typename __rebind_pointer<_VoidPtr, __list_node_base<_Tp, _VoidPtr> >::type + __node_base_pointer; - __node_pointer __ptr_; + __node_base_pointer __ptr_; #if _LIBCPP_DEBUG_LEVEL >= 2 _LIBCPP_INLINE_VISIBILITY - explicit __list_iterator(__node_pointer __p, const void* __c) _NOEXCEPT + explicit __list_iterator(__node_base_pointer __p, const void* __c) _NOEXCEPT : __ptr_(__p) { __get_db()->__insert_ic(this, __c); } #else _LIBCPP_INLINE_VISIBILITY - explicit __list_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} + explicit __list_iterator(__node_base_pointer __p) _NOEXCEPT : __ptr_(__p) {} #endif @@ -295,7 +299,7 @@ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), "Attempted to dereference a non-dereferenceable list::iterator"); #endif - return __ptr_->__value_; + return __ptr_->__as_node()->__value_; } _LIBCPP_INLINE_VISIBILITY pointer operator->() const @@ -304,7 +308,7 @@ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), "Attempted to dereference a non-dereferenceable list::iterator"); #endif - return pointer_traits::pointer_to(__ptr_->__value_); + return pointer_traits::pointer_to(__ptr_->__as_node()->__value_); } _LIBCPP_INLINE_VISIBILITY @@ -346,21 +350,21 @@ template class _LIBCPP_TYPE_VIS_ONLY __list_const_iterator { - typedef typename __rebind_pointer<_VoidPtr, __list_node<_Tp, _VoidPtr> >::type - __node_pointer; + typedef typename __rebind_pointer<_VoidPtr, __list_node_base<_Tp, _VoidPtr> >::type + __node_base_pointer; - __node_pointer __ptr_; + __node_base_pointer __ptr_; #if _LIBCPP_DEBUG_LEVEL >= 2 _LIBCPP_INLINE_VISIBILITY - explicit __list_const_iterator(__node_pointer __p, const void* __c) _NOEXCEPT + explicit __list_const_iterator(__node_base_pointer __p, const void* __c) _NOEXCEPT : __ptr_(__p) { __get_db()->__insert_ic(this, __c); } #else _LIBCPP_INLINE_VISIBILITY - explicit __list_const_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} + explicit __list_const_iterator(__node_base_pointer __p) _NOEXCEPT : __ptr_(__p) {} #endif template friend class list; @@ -422,7 +426,7 @@ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), "Attempted to dereference a non-dereferenceable list::const_iterator"); #endif - return __ptr_->__value_; + return __ptr_->__as_node()->__value_; } _LIBCPP_INLINE_VISIBILITY pointer operator->() const @@ -431,7 +435,7 @@ _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), "Attempted to dereference a non-dereferenceable list::iterator"); #endif - return pointer_traits::pointer_to(__ptr_->__value_); + return pointer_traits::pointer_to(__ptr_->__as_node()->__value_); } _LIBCPP_INLINE_VISIBILITY @@ -511,7 +515,10 @@ const __node_allocator& __node_alloc() const _NOEXCEPT {return __size_alloc_.second();} - static void __unlink_nodes(__node_pointer __f, __node_pointer __l) _NOEXCEPT; + static void __unlink_nodes(__node_base_pointer __f, __node_base_pointer __l) _NOEXCEPT; + static void __unlink_nodes(__node_pointer __f, __node_pointer __l) _NOEXCEPT { + return __unlink_nodes(__f->__as_base(), __l->__as_base()); + } __list_imp() _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value); @@ -543,22 +550,18 @@ iterator end() _NOEXCEPT { #if _LIBCPP_DEBUG_LEVEL >= 2 - return iterator(static_cast<__node_pointer>( - pointer_traits<__node_base_pointer>::pointer_to(__end_)), this); + return iterator(__end_.__as_base(), this); #else - return iterator(static_cast<__node_pointer>( - pointer_traits<__node_base_pointer>::pointer_to(__end_))); + return iterator(__end_.__as_base()); #endif } _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT { #if _LIBCPP_DEBUG_LEVEL >= 2 - return const_iterator(static_cast<__node_const_pointer>( - pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(__end_))), this); + return const_iterator(const_cast<__node_base&>(__end_).__as_base(), this); #else - return const_iterator(static_cast<__node_const_pointer>( - pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(__end_)))); + return const_iterator(const_cast<__node_base&>(__end_).__as_base()); #endif } @@ -613,7 +616,7 @@ template inline _LIBCPP_INLINE_VISIBILITY void -__list_imp<_Tp, _Alloc>::__unlink_nodes(__node_pointer __f, __node_pointer __l) +__list_imp<_Tp, _Alloc>::__unlink_nodes(__node_base_pointer __f, __node_base_pointer __l) _NOEXCEPT { __f->__prev_->__next_ = __l->__next_; @@ -651,14 +654,13 @@ if (!empty()) { __node_allocator& __na = __node_alloc(); - __node_pointer __f = __end_.__next_; - __node_pointer __l = static_cast<__node_pointer>( - pointer_traits<__node_base_pointer>::pointer_to(__end_)); + __node_base_pointer __f = __end_.__next_; + __node_base_pointer __l = __end_.__as_base(); __unlink_nodes(__f, __l->__prev_); __sz() = 0; while (__f != __l) { - __node_pointer __n = __f; + __node_pointer __n = __f->__as_node(); __f = __f->__next_; __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_)); __node_alloc_traits::deallocate(__na, __n, 1); @@ -700,13 +702,13 @@ swap(__sz(), __c.__sz()); swap(__end_, __c.__end_); if (__sz() == 0) - __end_.__next_ = __end_.__prev_ = __end_.__self(); + __end_.__next_ = __end_.__prev_ = __end_.__as_base(); else - __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_.__self(); + __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_.__as_base(); if (__c.__sz() == 0) - __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_.__self(); + __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_.__as_base(); else - __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_.__self(); + __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_.__as_base(); #if _LIBCPP_DEBUG_LEVEL >= 2 __libcpp_db* __db = __get_db(); @@ -881,25 +883,25 @@ reference front() { _LIBCPP_ASSERT(!empty(), "list::front called on empty list"); - return base::__end_.__next_->__value_; + return base::__end_.__next_->__as_node()->__value_; } _LIBCPP_INLINE_VISIBILITY const_reference front() const { _LIBCPP_ASSERT(!empty(), "list::front called on empty list"); - return base::__end_.__next_->__value_; + return base::__end_.__next_->__as_node()->__value_; } _LIBCPP_INLINE_VISIBILITY reference back() { _LIBCPP_ASSERT(!empty(), "list::back called on empty list"); - return base::__end_.__prev_->__value_; + return base::__end_.__prev_->__as_node()->__value_; } _LIBCPP_INLINE_VISIBILITY const_reference back() const { _LIBCPP_ASSERT(!empty(), "list::back called on empty list"); - return base::__end_.__prev_->__value_; + return base::__end_.__prev_->__as_node()->__value_; } #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES @@ -1004,9 +1006,15 @@ #endif // _LIBCPP_DEBUG_LEVEL >= 2 private: - static void __link_nodes (__node_pointer __p, __node_pointer __f, __node_pointer __l); - void __link_nodes_at_front(__node_pointer __f, __node_pointer __l); - void __link_nodes_at_back (__node_pointer __f, __node_pointer __l); + static void __link_nodes (__node_base_pointer __p, __node_base_pointer __f, __node_base_pointer __l); + void __link_nodes_at_front(__node_base_pointer __f, __node_base_pointer __l); + void __link_nodes_at_front(__node_pointer __f, __node_pointer __l) { + return __link_nodes_at_front(__f->__as_base(), __l->__as_base()); + } + void __link_nodes_at_back (__node_base_pointer __f, __node_base_pointer __l); + void __link_nodes_at_back(__node_pointer __f, __node_pointer __l) { + return __link_nodes_at_back(__f->__as_base(), __l->__as_base()); + } iterator __iterator(size_type __n); template static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp); @@ -1020,7 +1028,7 @@ template inline _LIBCPP_INLINE_VISIBILITY void -list<_Tp, _Alloc>::__link_nodes(__node_pointer __p, __node_pointer __f, __node_pointer __l) +list<_Tp, _Alloc>::__link_nodes(__node_base_pointer __p, __node_base_pointer __f, __node_base_pointer __l) { __p->__prev_->__next_ = __f; __f->__prev_ = __p->__prev_; @@ -1032,9 +1040,9 @@ template inline _LIBCPP_INLINE_VISIBILITY void -list<_Tp, _Alloc>::__link_nodes_at_front(__node_pointer __f, __node_pointer __l) +list<_Tp, _Alloc>::__link_nodes_at_front(__node_base_pointer __f, __node_base_pointer __l) { - __f->__prev_ = base::__end_.__self(); + __f->__prev_ = base::__end_.__as_base(); __l->__next_ = base::__end_.__next_; __l->__next_->__prev_ = __l; base::__end_.__next_ = __f; @@ -1044,9 +1052,9 @@ template inline _LIBCPP_INLINE_VISIBILITY void -list<_Tp, _Alloc>::__link_nodes_at_back(__node_pointer __f, __node_pointer __l) +list<_Tp, _Alloc>::__link_nodes_at_back(__node_base_pointer __f, __node_base_pointer __l) { - __l->__next_ = base::__end_.__self(); + __l->__next_ = base::__end_.__as_base(); __f->__prev_ = base::__end_.__prev_; __f->__prev_->__next_ = __f; base::__end_.__prev_ = __l; @@ -1354,9 +1362,9 @@ __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); ++__ds; #if _LIBCPP_DEBUG_LEVEL >= 2 - __r = iterator(__hold.get(), this); + __r = iterator(__hold.get()->__as_base(), this); #else - __r = iterator(__hold.get()); + __r = iterator(__hold.get()->__as_base()); #endif __hold.release(); iterator __e = __r; @@ -1368,7 +1376,7 @@ { __hold.reset(__node_alloc_traits::allocate(__na, 1)); __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); - __e.__ptr_->__next_ = __hold.get(); + __e.__ptr_->__next_ = __hold.get()->__as_base(); __hold->__prev_ = __e.__ptr_; __hold.release(); } @@ -1379,14 +1387,14 @@ while (true) { __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); - __node_pointer __prev = __e.__ptr_->__prev_; - __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); + __node_base_pointer __prev = __e.__ptr_->__prev_; + __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1); if (__prev == 0) break; #if _LIBCPP_DEBUG_LEVEL >= 2 - __e = iterator(__prev, this); + __e = iterator(__prev->__as_base(), this); #else - __e = iterator(__prev); + __e = iterator(__prev->__as_base()); #endif } throw; @@ -1422,9 +1430,9 @@ __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f); ++__ds; #if _LIBCPP_DEBUG_LEVEL >= 2 - __r = iterator(__hold.get(), this); + __r = iterator(__hold.get()->__as_base(), this); #else - __r = iterator(__hold.get()); + __r = iterator(__hold.get()->__as_base()); #endif __hold.release(); iterator __e = __r; @@ -1436,7 +1444,7 @@ { __hold.reset(__node_alloc_traits::allocate(__na, 1)); __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f); - __e.__ptr_->__next_ = __hold.get(); + __e.__ptr_->__next_ = __hold.get()->__as_base(); __hold->__prev_ = __e.__ptr_; __hold.release(); } @@ -1447,8 +1455,8 @@ while (true) { __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); - __node_pointer __prev = __e.__ptr_->__prev_; - __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); + __node_base_pointer __prev = __e.__ptr_->__prev_; + __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1); if (__prev == 0) break; #if _LIBCPP_DEBUG_LEVEL >= 2 @@ -1565,12 +1573,12 @@ unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); __hold->__prev_ = 0; __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); - __link_nodes(__p.__ptr_, __hold.get(), __hold.get()); + __link_nodes(__p.__ptr_, __hold.get()->__as_base(), __hold.get()->__as_base()); ++base::__sz(); #if _LIBCPP_DEBUG_LEVEL >= 2 - return iterator(__hold.release(), this); + return iterator(__hold.release()->__as_base(), this); #else - return iterator(__hold.release()); + return iterator(__hold.release()->__as_base()); #endif } @@ -1590,12 +1598,12 @@ unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); __hold->__prev_ = 0; __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); - __link_nodes(__p.__ptr_, __hold.get(), __hold.get()); + __link_nodes(__p.__ptr_, __hold.get()->__as_base(), __hold.get()->__as_base()); ++base::__sz(); #if _LIBCPP_DEBUG_LEVEL >= 2 - return iterator(__hold.release(), this); + return iterator(__hold.release()->__as_base(), this); #else - return iterator(__hold.release()); + return iterator(__hold.release()->__as_base()); #endif } @@ -1607,7 +1615,7 @@ { _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list"); __node_allocator& __na = base::__node_alloc(); - __node_pointer __n = base::__end_.__next_; + __node_pointer __n = base::__end_.__next_->__as_node(); base::__unlink_nodes(__n, __n); --base::__sz(); #if _LIBCPP_DEBUG_LEVEL >= 2 @@ -1635,7 +1643,7 @@ { _LIBCPP_ASSERT(!empty(), "list::pop_back() called with empty list"); __node_allocator& __na = base::__node_alloc(); - __node_pointer __n = base::__end_.__prev_; + __node_pointer __n = base::__end_.__prev_->__as_node(); base::__unlink_nodes(__n, __n); --base::__sz(); #if _LIBCPP_DEBUG_LEVEL >= 2 @@ -1669,9 +1677,9 @@ _LIBCPP_ASSERT(__p != end(), "list::erase(iterator) called with a non-dereferenceable iterator"); __node_allocator& __na = base::__node_alloc(); - __node_pointer __n = __p.__ptr_; - __node_pointer __r = __n->__next_; - base::__unlink_nodes(__n, __n); + __node_pointer __n = __p.__ptr_->__as_node(); + __node_base_pointer __r = __n->__next_; + base::__unlink_nodes(__n->__as_base(), __n->__as_base()); --base::__sz(); #if _LIBCPP_DEBUG_LEVEL >= 2 __c_node* __c = __get_db()->__find_c_and_lock(this); @@ -1712,7 +1720,7 @@ base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_); while (__f != __l) { - __node_pointer __n = __f.__ptr_; + __node_pointer __n = __f.__ptr_->__as_node(); ++__f; --base::__sz(); #if _LIBCPP_DEBUG_LEVEL >= 2 @@ -1758,9 +1766,9 @@ __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_)); ++__ds; #if _LIBCPP_DEBUG_LEVEL >= 2 - iterator __r = iterator(__hold.release(), this); + iterator __r = iterator(__hold.release()->__as_base(), this); #else - iterator __r = iterator(__hold.release()); + iterator __r = iterator(__hold.release()->__as_base()); #endif iterator __e = __r; #ifndef _LIBCPP_NO_EXCEPTIONS @@ -1771,7 +1779,7 @@ { __hold.reset(__node_alloc_traits::allocate(__na, 1)); __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_)); - __e.__ptr_->__next_ = __hold.get(); + __e.__ptr_->__next_ = __hold.get()->__as_base(); __hold->__prev_ = __e.__ptr_; __hold.release(); } @@ -1782,8 +1790,8 @@ while (true) { __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); - __node_pointer __prev = __e.__ptr_->__prev_; - __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); + __node_base_pointer __prev = __e.__ptr_->__prev_; + __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1); if (__prev == 0) break; #if _LIBCPP_DEBUG_LEVEL >= 2 @@ -1817,9 +1825,9 @@ __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); ++__ds; #if _LIBCPP_DEBUG_LEVEL >= 2 - iterator __r = iterator(__hold.release(), this); + iterator __r = iterator(__hold.release()->__as_base(), this); #else - iterator __r = iterator(__hold.release()); + iterator __r = iterator(__hold.release()->__as_base()); #endif iterator __e = __r; #ifndef _LIBCPP_NO_EXCEPTIONS @@ -1830,7 +1838,7 @@ { __hold.reset(__node_alloc_traits::allocate(__na, 1)); __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); - __e.__ptr_->__next_ = __hold.get(); + __e.__ptr_->__next_ = __hold.get()->__as_base(); __hold->__prev_ = __e.__ptr_; __hold.release(); } @@ -1841,8 +1849,8 @@ while (true) { __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); - __node_pointer __prev = __e.__ptr_->__prev_; - __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); + __node_base_pointer __prev = __e.__ptr_->__prev_; + __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1); if (__prev == 0) break; #if _LIBCPP_DEBUG_LEVEL >= 2 @@ -1854,8 +1862,7 @@ throw; } #endif // _LIBCPP_NO_EXCEPTIONS - __link_nodes(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>:: - pointer_to(base::__end_)), __r.__ptr_, __e.__ptr_); + __link_nodes(base::__end_.__as_base(), __r.__ptr_, __e.__ptr_); base::__sz() += __ds; } } @@ -1873,8 +1880,8 @@ #endif if (!__c.empty()) { - __node_pointer __f = __c.__end_.__next_; - __node_pointer __l = __c.__end_.__prev_; + __node_base_pointer __f = __c.__end_.__next_; + __node_base_pointer __l = __c.__end_.__prev_; base::__unlink_nodes(__f, __l); __link_nodes(__p.__ptr_, __f, __l); base::__sz() += __c.__sz(); @@ -1918,7 +1925,7 @@ #endif if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_) { - __node_pointer __f = __i.__ptr_; + __node_base_pointer __f = __i.__ptr_; base::__unlink_nodes(__f, __f); __link_nodes(__p.__ptr_, __f, __f); --__c.__sz(); @@ -1972,9 +1979,9 @@ __c.__sz() -= __s; base::__sz() += __s; } - __node_pointer __first = __f.__ptr_; + __node_base_pointer __first = __f.__ptr_; --__l; - __node_pointer __last = __l.__ptr_; + __node_base_pointer __last = __l.__ptr_; base::__unlink_nodes(__first, __last); __link_nodes(__p.__ptr_, __first, __last); #if _LIBCPP_DEBUG_LEVEL >= 2 @@ -2097,8 +2104,8 @@ ; base::__sz() += __ds; __c.__sz() -= __ds; - __node_pointer __f = __f2.__ptr_; - __node_pointer __l = __m2.__ptr_->__prev_; + __node_base_pointer __f = __f2.__ptr_; + __node_base_pointer __l = __m2.__ptr_->__prev_; __f2 = __m2; base::__unlink_nodes(__f, __l); __m2 = _VSTD::next(__f1); @@ -2161,7 +2168,7 @@ case 2: if (__comp(*--__e2, *__f1)) { - __node_pointer __f = __e2.__ptr_; + __node_base_pointer __f = __e2.__ptr_; base::__unlink_nodes(__f, __f); __link_nodes(__f1.__ptr_, __f, __f); return __e2; @@ -2177,8 +2184,8 @@ iterator __m2 = _VSTD::next(__f2); for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2) ; - __node_pointer __f = __f2.__ptr_; - __node_pointer __l = __m2.__ptr_->__prev_; + __node_base_pointer __f = __f2.__ptr_; + __node_base_pointer __l = __m2.__ptr_->__prev_; __r = __f2; __e1 = __f2 = __m2; base::__unlink_nodes(__f, __l); @@ -2195,8 +2202,8 @@ iterator __m2 = _VSTD::next(__f2); for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2) ; - __node_pointer __f = __f2.__ptr_; - __node_pointer __l = __m2.__ptr_->__prev_; + __node_base_pointer __f = __f2.__ptr_; + __node_base_pointer __l = __m2.__ptr_->__prev_; if (__e1 == __f2) __e1 = __m2; __f2 = __m2;