diff options
Diffstat (limited to 'system/include/libcxx/list')
| -rw-r--r-- | system/include/libcxx/list | 723 |
1 files changed, 661 insertions, 62 deletions
diff --git a/system/include/libcxx/list b/system/include/libcxx/list index 900e2ec9..81258869 100644 --- a/system/include/libcxx/list +++ b/system/include/libcxx/list @@ -176,7 +176,11 @@ template <class T, class Alloc> #include <iterator> #include <algorithm> +#include <__undef_min_max> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header +#endif _LIBCPP_BEGIN_NAMESPACE_STD @@ -209,9 +213,9 @@ struct __list_node _Tp __value_; }; -template <class _Tp, class _Alloc> class list; +template <class _Tp, class _Alloc> class _LIBCPP_VISIBLE list; template <class _Tp, class _Alloc> class __list_imp; -template <class _Tp, class _VoidPtr> class __list_const_iterator; +template <class _Tp, class _VoidPtr> class _LIBCPP_VISIBLE __list_const_iterator; template <class _Tp, class _VoidPtr> class _LIBCPP_VISIBLE __list_iterator @@ -225,8 +229,19 @@ class _LIBCPP_VISIBLE __list_iterator __node_pointer __ptr_; +#if _LIBCPP_DEBUG_LEVEL >= 2 + _LIBCPP_INLINE_VISIBILITY + explicit __list_iterator(__node_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) {} +#endif + + template<class, class> friend class list; template<class, class> friend class __list_imp; @@ -245,25 +260,88 @@ public: typedef typename pointer_traits<pointer>::difference_type difference_type; _LIBCPP_INLINE_VISIBILITY - __list_iterator() _NOEXCEPT {} + __list_iterator() _NOEXCEPT + { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_i(this); +#endif + } + +#if _LIBCPP_DEBUG_LEVEL >= 2 + _LIBCPP_INLINE_VISIBILITY - reference operator*() const {return __ptr_->__value_;} + __list_iterator(const __list_iterator& __p) + : __ptr_(__p.__ptr_) + { + __get_db()->__iterator_copy(this, &__p); + } + + _LIBCPP_INLINE_VISIBILITY + ~__list_iterator() + { + __get_db()->__erase_i(this); + } + + _LIBCPP_INLINE_VISIBILITY + __list_iterator& operator=(const __list_iterator& __p) + { + if (this != &__p) + { + __get_db()->__iterator_copy(this, &__p); + __ptr_ = __p.__ptr_; + } + 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), + "Attempted to dereference a non-dereferenceable list::iterator"); +#endif + return __ptr_->__value_; + } _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return &(operator*());} _LIBCPP_INLINE_VISIBILITY - __list_iterator& operator++() {__ptr_ = __ptr_->__next_; return *this;} + __list_iterator& operator++() + { +#if _LIBCPP_DEBUG_LEVEL >= 2 + _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), + "Attempted to increment non-incrementable list::iterator"); +#endif + __ptr_ = __ptr_->__next_; + return *this; + } _LIBCPP_INLINE_VISIBILITY __list_iterator operator++(int) {__list_iterator __t(*this); ++(*this); return __t;} _LIBCPP_INLINE_VISIBILITY - __list_iterator& operator--() {__ptr_ = __ptr_->__prev_; return *this;} + __list_iterator& operator--() + { +#if _LIBCPP_DEBUG_LEVEL >= 2 + _LIBCPP_ASSERT(__get_const_db()->__decrementable(this), + "Attempted to decrement non-decrementable list::iterator"); +#endif + __ptr_ = __ptr_->__prev_; + return *this; + } _LIBCPP_INLINE_VISIBILITY __list_iterator operator--(int) {__list_iterator __t(*this); --(*this); return __t;} friend _LIBCPP_INLINE_VISIBILITY bool operator==(const __list_iterator& __x, const __list_iterator& __y) - {return __x.__ptr_ == __y.__ptr_;} + { +#if _LIBCPP_DEBUG_LEVEL >= 2 + _LIBCPP_ASSERT(__get_const_db()->__comparable(&__x, &__y), + "Attempted to compare non-comparable list::iterator"); +#endif + return __x.__ptr_ == __y.__ptr_; + } friend _LIBCPP_INLINE_VISIBILITY bool operator!=(const __list_iterator& __x, const __list_iterator& __y) {return !(__x == __y);} @@ -281,8 +359,17 @@ class _LIBCPP_VISIBLE __list_const_iterator __node_pointer __ptr_; +#if _LIBCPP_DEBUG_LEVEL >= 2 + _LIBCPP_INLINE_VISIBILITY + explicit __list_const_iterator(__node_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) {} +#endif template<class, class> friend class list; template<class, class> friend class __list_imp; @@ -300,29 +387,95 @@ public: typedef typename pointer_traits<pointer>::difference_type difference_type; _LIBCPP_INLINE_VISIBILITY - __list_const_iterator() _NOEXCEPT {} + __list_const_iterator() _NOEXCEPT + { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_i(this); +#endif + } _LIBCPP_INLINE_VISIBILITY __list_const_iterator(__list_iterator<_Tp, _VoidPtr> __p) _NOEXCEPT - : __ptr_(__p.__ptr_) {} + : __ptr_(__p.__ptr_) + { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__iterator_copy(this, &__p); +#endif + } + +#if _LIBCPP_DEBUG_LEVEL >= 2 + + _LIBCPP_INLINE_VISIBILITY + __list_const_iterator(const __list_const_iterator& __p) + : __ptr_(__p.__ptr_) + { + __get_db()->__iterator_copy(this, &__p); + } + + _LIBCPP_INLINE_VISIBILITY + ~__list_const_iterator() + { + __get_db()->__erase_i(this); + } + + _LIBCPP_INLINE_VISIBILITY + __list_const_iterator& operator=(const __list_const_iterator& __p) + { + if (this != &__p) + { + __get_db()->__iterator_copy(this, &__p); + __ptr_ = __p.__ptr_; + } + return *this; + } +#endif // _LIBCPP_DEBUG_LEVEL >= 2 _LIBCPP_INLINE_VISIBILITY - reference operator*() const {return __ptr_->__value_;} + reference operator*() const + { +#if _LIBCPP_DEBUG_LEVEL >= 2 + _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), + "Attempted to dereference a non-dereferenceable list::const_iterator"); +#endif + return __ptr_->__value_; + } _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return &(operator*());} _LIBCPP_INLINE_VISIBILITY - __list_const_iterator& operator++() {__ptr_ = __ptr_->__next_; return *this;} + __list_const_iterator& operator++() + { +#if _LIBCPP_DEBUG_LEVEL >= 2 + _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), + "Attempted to increment non-incrementable list::const_iterator"); +#endif + __ptr_ = __ptr_->__next_; + return *this; + } _LIBCPP_INLINE_VISIBILITY __list_const_iterator operator++(int) {__list_const_iterator __t(*this); ++(*this); return __t;} _LIBCPP_INLINE_VISIBILITY - __list_const_iterator& operator--() {__ptr_ = __ptr_->__prev_; return *this;} + __list_const_iterator& operator--() + { +#if _LIBCPP_DEBUG_LEVEL >= 2 + _LIBCPP_ASSERT(__get_const_db()->__decrementable(this), + "Attempted to decrement non-decrementable list::const_iterator"); +#endif + __ptr_ = __ptr_->__prev_; + return *this; + } _LIBCPP_INLINE_VISIBILITY __list_const_iterator operator--(int) {__list_const_iterator __t(*this); --(*this); return __t;} friend _LIBCPP_INLINE_VISIBILITY bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y) - {return __x.__ptr_ == __y.__ptr_;} + { +#if _LIBCPP_DEBUG_LEVEL >= 2 + _LIBCPP_ASSERT(__get_const_db()->__comparable(&__x, &__y), + "Attempted to compare non-comparable list::const_iterator"); +#endif + return __x.__ptr_ == __y.__ptr_; + } friend _LIBCPP_INLINE_VISIBILITY bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y) {return !(__x == __y);} @@ -383,17 +536,41 @@ protected: bool empty() const _NOEXCEPT {return __sz() == 0;} _LIBCPP_INLINE_VISIBILITY - iterator begin() _NOEXCEPT - {return iterator(__end_.__next_);} + iterator begin() _NOEXCEPT + { +#if _LIBCPP_DEBUG_LEVEL >= 2 + return iterator(__end_.__next_, this); +#else + return iterator(__end_.__next_); +#endif + } _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT - {return const_iterator(__end_.__next_);} + { +#if _LIBCPP_DEBUG_LEVEL >= 2 + return const_iterator(__end_.__next_, this); +#else + return const_iterator(__end_.__next_); +#endif + } _LIBCPP_INLINE_VISIBILITY - iterator end() _NOEXCEPT - {return iterator(static_cast<__node_pointer> (&__end_));} + iterator end() _NOEXCEPT + { +#if _LIBCPP_DEBUG_LEVEL >= 2 + return iterator(static_cast<__node_pointer>(&__end_), this); +#else + return iterator(static_cast<__node_pointer>(&__end_)); +#endif + } _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT - {return const_iterator(static_cast<__node_const_pointer>(&__end_));} + { +#if _LIBCPP_DEBUG_LEVEL >= 2 + return const_iterator(static_cast<__node_const_pointer>(&__end_), this); +#else + return const_iterator(static_cast<__node_const_pointer>(&__end_)); +#endif + } void swap(__list_imp& __c) _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || @@ -486,6 +663,9 @@ template <class _Tp, class _Alloc> __list_imp<_Tp, _Alloc>::~__list_imp() { clear(); +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__erase_c(this); +#endif } template <class _Tp, class _Alloc> @@ -495,17 +675,32 @@ __list_imp<_Tp, _Alloc>::clear() _NOEXCEPT if (!empty()) { __node_allocator& __na = __node_alloc(); - iterator __f = begin(); - iterator __l = end(); - __unlink_nodes(*__f.__ptr_, *__l.__ptr_->__prev_); + __node_pointer __f = __end_.__next_; + __node_pointer __l = static_cast<__node_pointer>(&__end_); + __unlink_nodes(*__f, *__l->__prev_); __sz() = 0; while (__f != __l) { - __node& __n = *__f.__ptr_; - ++__f; + __node& __n = *__f; + __f = __f->__next_; __node_alloc_traits::destroy(__na, _VSTD::addressof(__n.__value_)); __node_alloc_traits::deallocate(__na, _VSTD::addressof(__n), 1); } +#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; + const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); + if (__i->__ptr_ != __l) + { + (*__p)->__c_ = nullptr; + if (--__c->end_ != __p) + memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); + } + } + __get_db()->unlock(); +#endif } } @@ -515,6 +710,10 @@ __list_imp<_Tp, _Alloc>::swap(__list_imp& __c) _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable<__node_allocator>::value) { + _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value || + this->__node_alloc() == __c.__node_alloc(), + "list::swap: Either propagate_on_container_swap must be true" + " or the allocators must compare equal"); using _VSTD::swap; __swap_alloc(__node_alloc(), __c.__node_alloc()); swap(__sz(), __c.__sz()); @@ -530,6 +729,41 @@ __list_imp<_Tp, _Alloc>::swap(__list_imp& __c) else __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = &static_cast<__node&>(__c.__end_); +#if _LIBCPP_DEBUG_LEVEL >= 2 + __libcpp_db* __db = __get_db(); + __c_node* __cn1 = __db->__find_c_and_lock(this); + __c_node* __cn2 = __db->__find_c(&__c); + std::swap(__cn1->beg_, __cn2->beg_); + std::swap(__cn1->end_, __cn2->end_); + std::swap(__cn1->cap_, __cn2->cap_); + for (__i_node** __p = __cn1->end_; __p != __cn1->beg_;) + { + --__p; + const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); + if (__i->__ptr_ == static_cast<__node_pointer>(&__c.__end_)) + { + __cn2->__add(*__p); + if (--__cn1->end_ != __p) + memmove(__p, __p+1, (__cn1->end_ - __p)*sizeof(__i_node*)); + } + else + (*__p)->__c_ = __cn1; + } + for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) + { + --__p; + const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); + if (__i->__ptr_ == static_cast<__node_pointer>(&__end_)) + { + __cn1->__add(*__p); + if (--__cn2->end_ != __p) + memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); + } + else + (*__p)->__c_ = __cn2; + } + __db->unlock(); +#endif } template <class _Tp, class _Alloc = allocator<_Tp> > @@ -561,9 +795,18 @@ public: _LIBCPP_INLINE_VISIBILITY list() _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) - {} + { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif + } _LIBCPP_INLINE_VISIBILITY - list(const allocator_type& __a) : base(__a) {} + list(const allocator_type& __a) : base(__a) + { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif + } list(size_type __n); list(size_type __n, const value_type& __x); list(size_type __n, const value_type& __x, const allocator_type& __a); @@ -649,13 +892,29 @@ public: {return const_reverse_iterator(begin());} _LIBCPP_INLINE_VISIBILITY - reference front() {return base::__end_.__next_->__value_;} + reference front() + { + _LIBCPP_ASSERT(!empty(), "list::front called on empty list"); + return base::__end_.__next_->__value_; + } _LIBCPP_INLINE_VISIBILITY - const_reference front() const {return base::__end_.__next_->__value_;} + const_reference front() const + { + _LIBCPP_ASSERT(!empty(), "list::front called on empty list"); + return base::__end_.__next_->__value_; + } _LIBCPP_INLINE_VISIBILITY - reference back() {return base::__end_.__prev_->__value_;} + reference back() + { + _LIBCPP_ASSERT(!empty(), "list::back called on empty list"); + return base::__end_.__prev_->__value_; + } _LIBCPP_INLINE_VISIBILITY - const_reference back() const {return base::__end_.__prev_->__value_;} + const_reference back() const + { + _LIBCPP_ASSERT(!empty(), "list::back called on empty list"); + return base::__end_.__prev_->__value_; + } #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES void push_front(value_type&& __x); @@ -743,6 +1002,17 @@ public: void reverse() _NOEXCEPT; + bool __invariants() const; + +#if _LIBCPP_DEBUG_LEVEL >= 2 + + bool __dereferenceable(const const_iterator* __i) const; + bool __decrementable(const const_iterator* __i) const; + bool __addable(const const_iterator* __i, ptrdiff_t __n) const; + bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; + +#endif // _LIBCPP_DEBUG_LEVEL >= 2 + private: static void __link_nodes(__node& __p, __node& __f, __node& __l); iterator __iterator(size_type __n); @@ -778,6 +1048,9 @@ list<_Tp, _Alloc>::__iterator(size_type __n) template <class _Tp, class _Alloc> list<_Tp, _Alloc>::list(size_type __n) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif for (; __n > 0; --__n) #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES emplace_back(); @@ -789,6 +1062,9 @@ list<_Tp, _Alloc>::list(size_type __n) template <class _Tp, class _Alloc> list<_Tp, _Alloc>::list(size_type __n, const value_type& __x) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif for (; __n > 0; --__n) push_back(__x); } @@ -797,6 +1073,9 @@ template <class _Tp, class _Alloc> list<_Tp, _Alloc>::list(size_type __n, const value_type& __x, const allocator_type& __a) : base(__a) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif for (; __n > 0; --__n) push_back(__x); } @@ -806,6 +1085,9 @@ template <class _InpIter> list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, typename enable_if<__is_input_iterator<_InpIter>::value>::type*) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif for (; __f != __l; ++__f) push_back(*__f); } @@ -816,6 +1098,9 @@ list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a, typename enable_if<__is_input_iterator<_InpIter>::value>::type*) : base(__a) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif for (; __f != __l; ++__f) push_back(*__f); } @@ -826,6 +1111,9 @@ list<_Tp, _Alloc>::list(const list& __c) __node_alloc_traits::select_on_container_copy_construction( __c.__node_alloc()))) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) push_back(*__i); } @@ -834,6 +1122,9 @@ template <class _Tp, class _Alloc> list<_Tp, _Alloc>::list(const list& __c, const allocator_type& __a) : base(__a) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) push_back(*__i); } @@ -844,6 +1135,9 @@ template <class _Tp, class _Alloc> list<_Tp, _Alloc>::list(initializer_list<value_type> __il, const allocator_type& __a) : base(__a) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), __e = __il.end(); __i != __e; ++__i) push_back(*__i); @@ -852,6 +1146,9 @@ list<_Tp, _Alloc>::list(initializer_list<value_type> __il, const allocator_type& template <class _Tp, class _Alloc> list<_Tp, _Alloc>::list(initializer_list<value_type> __il) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), __e = __il.end(); __i != __e; ++__i) push_back(*__i); @@ -880,6 +1177,9 @@ list<_Tp, _Alloc>::list(list&& __c) _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value) : base(allocator_type(_VSTD::move(__c.__node_alloc()))) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif splice(end(), __c); } @@ -888,12 +1188,15 @@ inline _LIBCPP_INLINE_VISIBILITY list<_Tp, _Alloc>::list(list&& __c, const allocator_type& __a) : base(__a) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif if (__a == __c.get_allocator()) splice(end(), __c); else { - typedef move_iterator<iterator> _I; - assign(_I(__c.begin()), _I(__c.end())); + typedef move_iterator<iterator> _Ip; + assign(_Ip(__c.begin()), _Ip(__c.end())); } } @@ -916,8 +1219,8 @@ list<_Tp, _Alloc>::__move_assign(list& __c, false_type) { if (base::__node_alloc() != __c.__node_alloc()) { - typedef move_iterator<iterator> _I; - assign(_I(__c.begin()), _I(__c.end())); + typedef move_iterator<iterator> _Ip; + assign(_Ip(__c.begin()), _Ip(__c.end())); } else __move_assign(__c, true_type()); @@ -977,9 +1280,14 @@ template <class _Tp, class _Alloc> typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, + "list::insert(iterator, x) called with an iterator not" + " referring to this list"); +#endif __node_allocator& __na = base::__node_alloc(); - typedef __allocator_destructor<__node_allocator> _D; - unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1)); + typedef __allocator_destructor<__node_allocator> _Dp; + 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_), __x); __link_nodes(const_cast<__node&>(*__p.__ptr_), *__hold, *__hold); @@ -991,17 +1299,28 @@ template <class _Tp, class _Alloc> typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, + "list::insert(iterator, n, x) called with an iterator not" + " referring to this list"); + iterator __r(const_cast<__node_pointer>(__p.__ptr_), this); +#else iterator __r(const_cast<__node_pointer>(__p.__ptr_)); +#endif if (__n > 0) { size_type __ds = 0; __node_allocator& __na = base::__node_alloc(); - typedef __allocator_destructor<__node_allocator> _D; - unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1)); + typedef __allocator_destructor<__node_allocator> _Dp; + 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_), __x); ++__ds; +#if _LIBCPP_DEBUG_LEVEL >= 2 + __r = iterator(__hold.get(), this); +#else __r = iterator(__hold.get()); +#endif __hold.release(); iterator __e = __r; #ifndef _LIBCPP_NO_EXCEPTIONS @@ -1027,7 +1346,11 @@ list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& _ __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); if (__prev == 0) break; +#if _LIBCPP_DEBUG_LEVEL >= 2 + __e = iterator(__prev, this); +#else __e = iterator(__prev); +#endif } throw; } @@ -1044,17 +1367,28 @@ typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l, typename enable_if<__is_input_iterator<_InpIter>::value>::type*) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, + "list::insert(iterator, range) called with an iterator not" + " referring to this list"); + iterator __r(const_cast<__node_pointer>(__p.__ptr_), this); +#else iterator __r(const_cast<__node_pointer>(__p.__ptr_)); +#endif if (__f != __l) { size_type __ds = 0; __node_allocator& __na = base::__node_alloc(); - typedef __allocator_destructor<__node_allocator> _D; - unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1)); + typedef __allocator_destructor<__node_allocator> _Dp; + 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_), *__f); ++__ds; +#if _LIBCPP_DEBUG_LEVEL >= 2 + __r = iterator(__hold.get(), this); +#else __r = iterator(__hold.get()); +#endif __hold.release(); iterator __e = __r; #ifndef _LIBCPP_NO_EXCEPTIONS @@ -1080,7 +1414,11 @@ list<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l, __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); if (__prev == 0) break; +#if _LIBCPP_DEBUG_LEVEL >= 2 + __e = iterator(__prev, this); +#else __e = iterator(__prev); +#endif } throw; } @@ -1096,8 +1434,8 @@ void list<_Tp, _Alloc>::push_front(const value_type& __x) { __node_allocator& __na = base::__node_alloc(); - typedef __allocator_destructor<__node_allocator> _D; - unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1)); + typedef __allocator_destructor<__node_allocator> _Dp; + unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); __link_nodes(*base::__end_.__next_, *__hold, *__hold); ++base::__sz(); @@ -1109,8 +1447,8 @@ void list<_Tp, _Alloc>::push_back(const value_type& __x) { __node_allocator& __na = base::__node_alloc(); - typedef __allocator_destructor<__node_allocator> _D; - unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1)); + typedef __allocator_destructor<__node_allocator> _Dp; + unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); __link_nodes(static_cast<__node&>(base::__end_), *__hold, *__hold); ++base::__sz(); @@ -1124,8 +1462,8 @@ void list<_Tp, _Alloc>::push_front(value_type&& __x) { __node_allocator& __na = base::__node_alloc(); - typedef __allocator_destructor<__node_allocator> _D; - unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1)); + typedef __allocator_destructor<__node_allocator> _Dp; + unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); __link_nodes(*base::__end_.__next_, *__hold, *__hold); ++base::__sz(); @@ -1137,8 +1475,8 @@ void list<_Tp, _Alloc>::push_back(value_type&& __x) { __node_allocator& __na = base::__node_alloc(); - typedef __allocator_destructor<__node_allocator> _D; - unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1)); + typedef __allocator_destructor<__node_allocator> _Dp; + unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); __link_nodes(static_cast<__node&>(base::__end_), *__hold, *__hold); ++base::__sz(); @@ -1153,8 +1491,8 @@ void list<_Tp, _Alloc>::emplace_front(_Args&&... __args) { __node_allocator& __na = base::__node_alloc(); - typedef __allocator_destructor<__node_allocator> _D; - unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1)); + typedef __allocator_destructor<__node_allocator> _Dp; + unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); __link_nodes(*base::__end_.__next_, *__hold, *__hold); ++base::__sz(); @@ -1167,8 +1505,8 @@ void list<_Tp, _Alloc>::emplace_back(_Args&&... __args) { __node_allocator& __na = base::__node_alloc(); - typedef __allocator_destructor<__node_allocator> _D; - unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1)); + typedef __allocator_destructor<__node_allocator> _Dp; + unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); __link_nodes(static_cast<__node&>(base::__end_), *__hold, *__hold); ++base::__sz(); @@ -1181,13 +1519,17 @@ typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args) { __node_allocator& __na = base::__node_alloc(); - typedef __allocator_destructor<__node_allocator> _D; - unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1)); + typedef __allocator_destructor<__node_allocator> _Dp; + 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(const_cast<__node&>(*__p.__ptr_), *__hold, *__hold); ++base::__sz(); +#if _LIBCPP_DEBUG_LEVEL >= 2 + return iterator(__hold.release(), this); +#else return iterator(__hold.release()); +#endif } #endif // _LIBCPP_HAS_NO_VARIADICS @@ -1196,14 +1538,23 @@ template <class _Tp, class _Alloc> typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, + "list::insert(iterator, x) called with an iterator not" + " referring to this list"); +#endif __node_allocator& __na = base::__node_alloc(); - typedef __allocator_destructor<__node_allocator> _D; - unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1)); + typedef __allocator_destructor<__node_allocator> _Dp; + 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(const_cast<__node&>(*__p.__ptr_), *__hold, *__hold); ++base::__sz(); +#if _LIBCPP_DEBUG_LEVEL >= 2 + return iterator(__hold.release(), this); +#else return iterator(__hold.release()); +#endif } #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES @@ -1212,10 +1563,26 @@ template <class _Tp, class _Alloc> void list<_Tp, _Alloc>::pop_front() { + _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list"); __node_allocator& __na = base::__node_alloc(); __node& __n = *base::__end_.__next_; base::__unlink_nodes(__n, __n); --base::__sz(); +#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->__ptr_ == &__n) + { + (*__p)->__c_ = nullptr; + if (--__c->end_ != __p) + memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); + } + } + __get_db()->unlock(); +#endif __node_alloc_traits::destroy(__na, _VSTD::addressof(__n.__value_)); __node_alloc_traits::deallocate(__na, _VSTD::addressof(__n), 1); } @@ -1224,10 +1591,26 @@ template <class _Tp, class _Alloc> void list<_Tp, _Alloc>::pop_back() { + _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list"); __node_allocator& __na = base::__node_alloc(); __node& __n = *base::__end_.__prev_; base::__unlink_nodes(__n, __n); --base::__sz(); +#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->__ptr_ == &__n) + { + (*__p)->__c_ = nullptr; + if (--__c->end_ != __p) + memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); + } + } + __get_db()->unlock(); +#endif __node_alloc_traits::destroy(__na, _VSTD::addressof(__n.__value_)); __node_alloc_traits::deallocate(__na, _VSTD::addressof(__n), 1); } @@ -1236,20 +1619,49 @@ template <class _Tp, class _Alloc> typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::erase(const_iterator __p) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, + "list::erase(iterator) called with an iterator not" + " referring to this list"); +#endif __node_allocator& __na = base::__node_alloc(); __node& __n = const_cast<__node&>(*__p.__ptr_); __node_pointer __r = __n.__next_; base::__unlink_nodes(__n, __n); --base::__sz(); +#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->__ptr_ == &__n) + { + (*__p)->__c_ = nullptr; + if (--__c->end_ != __p) + memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); + } + } + __get_db()->unlock(); +#endif __node_alloc_traits::destroy(__na, _VSTD::addressof(__n.__value_)); __node_alloc_traits::deallocate(__na, _VSTD::addressof(__n), 1); +#if _LIBCPP_DEBUG_LEVEL >= 2 + return iterator(__r, this); +#else return iterator(__r); +#endif } template <class _Tp, class _Alloc> typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == this, + "list::erase(iterator, iterator) called with an iterator not" + " referring to this list"); +#endif if (__f != __l) { __node_allocator& __na = base::__node_alloc(); @@ -1259,11 +1671,30 @@ list<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l) __node& __n = const_cast<__node&>(*__f.__ptr_); ++__f; --base::__sz(); +#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->__ptr_ == &__n) + { + (*__p)->__c_ = nullptr; + if (--__c->end_ != __p) + memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); + } + } + __get_db()->unlock(); +#endif __node_alloc_traits::destroy(__na, _VSTD::addressof(__n.__value_)); __node_alloc_traits::deallocate(__na, _VSTD::addressof(__n), 1); } } +#if _LIBCPP_DEBUG_LEVEL >= 2 + return iterator(const_cast<__node_pointer>(__l.__ptr_), this); +#else return iterator(const_cast<__node_pointer>(__l.__ptr_)); +#endif } template <class _Tp, class _Alloc> @@ -1277,12 +1708,16 @@ list<_Tp, _Alloc>::resize(size_type __n) __n -= base::__sz(); size_type __ds = 0; __node_allocator& __na = base::__node_alloc(); - typedef __allocator_destructor<__node_allocator> _D; - unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1)); + typedef __allocator_destructor<__node_allocator> _Dp; + 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_)); ++__ds; +#if _LIBCPP_DEBUG_LEVEL >= 2 + iterator __r = iterator(__hold.release(), this); +#else iterator __r = iterator(__hold.release()); +#endif iterator __e = __r;</ |