1227825Stheraven// -*- C++ -*- 2227825Stheraven//===---------------------------- list ------------------------------------===// 3227825Stheraven// 4227825Stheraven// The LLVM Compiler Infrastructure 5227825Stheraven// 6227825Stheraven// This file is dual licensed under the MIT and the University of Illinois Open 7227825Stheraven// Source Licenses. See LICENSE.TXT for details. 8227825Stheraven// 9227825Stheraven//===----------------------------------------------------------------------===// 10227825Stheraven 11227825Stheraven#ifndef _LIBCPP_LIST 12227825Stheraven#define _LIBCPP_LIST 13227825Stheraven 14227825Stheraven/* 15227825Stheraven list synopsis 16227825Stheraven 17227825Stheravennamespace std 18227825Stheraven{ 19227825Stheraven 20227825Stheraventemplate <class T, class Alloc = allocator<T> > 21227825Stheravenclass list 22227825Stheraven{ 23227825Stheravenpublic: 24227825Stheraven 25227825Stheraven // types: 26227825Stheraven typedef T value_type; 27227825Stheraven typedef Alloc allocator_type; 28227825Stheraven typedef typename allocator_type::reference reference; 29227825Stheraven typedef typename allocator_type::const_reference const_reference; 30227825Stheraven typedef typename allocator_type::pointer pointer; 31227825Stheraven typedef typename allocator_type::const_pointer const_pointer; 32227825Stheraven typedef implementation-defined iterator; 33227825Stheraven typedef implementation-defined const_iterator; 34227825Stheraven typedef implementation-defined size_type; 35227825Stheraven typedef implementation-defined difference_type; 36227825Stheraven typedef reverse_iterator<iterator> reverse_iterator; 37227825Stheraven typedef reverse_iterator<const_iterator> const_reverse_iterator; 38227825Stheraven 39227825Stheraven list() 40227825Stheraven noexcept(is_nothrow_default_constructible<allocator_type>::value); 41227825Stheraven explicit list(const allocator_type& a); 42227825Stheraven explicit list(size_type n); 43261272Sdim explicit list(size_type n, const allocator_type& a); // C++14 44227825Stheraven list(size_type n, const value_type& value); 45227825Stheraven list(size_type n, const value_type& value, const allocator_type& a); 46227825Stheraven template <class Iter> 47227825Stheraven list(Iter first, Iter last); 48227825Stheraven template <class Iter> 49227825Stheraven list(Iter first, Iter last, const allocator_type& a); 50227825Stheraven list(const list& x); 51227825Stheraven list(const list&, const allocator_type& a); 52227825Stheraven list(list&& x) 53227825Stheraven noexcept(is_nothrow_move_constructible<allocator_type>::value); 54227825Stheraven list(list&&, const allocator_type& a); 55227825Stheraven list(initializer_list<value_type>); 56227825Stheraven list(initializer_list<value_type>, const allocator_type& a); 57227825Stheraven 58227825Stheraven ~list(); 59227825Stheraven 60227825Stheraven list& operator=(const list& x); 61227825Stheraven list& operator=(list&& x) 62227825Stheraven noexcept( 63227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 64227825Stheraven is_nothrow_move_assignable<allocator_type>::value); 65227825Stheraven list& operator=(initializer_list<value_type>); 66227825Stheraven template <class Iter> 67227825Stheraven void assign(Iter first, Iter last); 68227825Stheraven void assign(size_type n, const value_type& t); 69227825Stheraven void assign(initializer_list<value_type>); 70227825Stheraven 71227825Stheraven allocator_type get_allocator() const noexcept; 72227825Stheraven 73227825Stheraven iterator begin() noexcept; 74227825Stheraven const_iterator begin() const noexcept; 75227825Stheraven iterator end() noexcept; 76227825Stheraven const_iterator end() const noexcept; 77227825Stheraven reverse_iterator rbegin() noexcept; 78227825Stheraven const_reverse_iterator rbegin() const noexcept; 79227825Stheraven reverse_iterator rend() noexcept; 80227825Stheraven const_reverse_iterator rend() const noexcept; 81227825Stheraven const_iterator cbegin() const noexcept; 82227825Stheraven const_iterator cend() const noexcept; 83227825Stheraven const_reverse_iterator crbegin() const noexcept; 84227825Stheraven const_reverse_iterator crend() const noexcept; 85227825Stheraven 86227825Stheraven reference front(); 87227825Stheraven const_reference front() const; 88227825Stheraven reference back(); 89227825Stheraven const_reference back() const; 90227825Stheraven 91227825Stheraven bool empty() const noexcept; 92227825Stheraven size_type size() const noexcept; 93227825Stheraven size_type max_size() const noexcept; 94227825Stheraven 95227825Stheraven template <class... Args> 96227825Stheraven void emplace_front(Args&&... args); 97227825Stheraven void pop_front(); 98227825Stheraven template <class... Args> 99227825Stheraven void emplace_back(Args&&... args); 100227825Stheraven void pop_back(); 101227825Stheraven void push_front(const value_type& x); 102227825Stheraven void push_front(value_type&& x); 103227825Stheraven void push_back(const value_type& x); 104227825Stheraven void push_back(value_type&& x); 105227825Stheraven template <class... Args> 106227825Stheraven iterator emplace(const_iterator position, Args&&... args); 107227825Stheraven iterator insert(const_iterator position, const value_type& x); 108227825Stheraven iterator insert(const_iterator position, value_type&& x); 109227825Stheraven iterator insert(const_iterator position, size_type n, const value_type& x); 110227825Stheraven template <class Iter> 111227825Stheraven iterator insert(const_iterator position, Iter first, Iter last); 112227825Stheraven iterator insert(const_iterator position, initializer_list<value_type> il); 113227825Stheraven 114227825Stheraven iterator erase(const_iterator position); 115227825Stheraven iterator erase(const_iterator position, const_iterator last); 116227825Stheraven 117227825Stheraven void resize(size_type sz); 118227825Stheraven void resize(size_type sz, const value_type& c); 119227825Stheraven 120227825Stheraven void swap(list&) 121288943Sdim noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17 122227825Stheraven void clear() noexcept; 123227825Stheraven 124227825Stheraven void splice(const_iterator position, list& x); 125227825Stheraven void splice(const_iterator position, list&& x); 126227825Stheraven void splice(const_iterator position, list& x, const_iterator i); 127227825Stheraven void splice(const_iterator position, list&& x, const_iterator i); 128227825Stheraven void splice(const_iterator position, list& x, const_iterator first, 129227825Stheraven const_iterator last); 130227825Stheraven void splice(const_iterator position, list&& x, const_iterator first, 131227825Stheraven const_iterator last); 132227825Stheraven 133227825Stheraven void remove(const value_type& value); 134227825Stheraven template <class Pred> void remove_if(Pred pred); 135227825Stheraven void unique(); 136227825Stheraven template <class BinaryPredicate> 137227825Stheraven void unique(BinaryPredicate binary_pred); 138227825Stheraven void merge(list& x); 139227825Stheraven void merge(list&& x); 140227825Stheraven template <class Compare> 141227825Stheraven void merge(list& x, Compare comp); 142227825Stheraven template <class Compare> 143227825Stheraven void merge(list&& x, Compare comp); 144227825Stheraven void sort(); 145227825Stheraven template <class Compare> 146227825Stheraven void sort(Compare comp); 147227825Stheraven void reverse() noexcept; 148227825Stheraven}; 149227825Stheraven 150227825Stheraventemplate <class T, class Alloc> 151227825Stheraven bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y); 152227825Stheraventemplate <class T, class Alloc> 153227825Stheraven bool operator< (const list<T,Alloc>& x, const list<T,Alloc>& y); 154227825Stheraventemplate <class T, class Alloc> 155227825Stheraven bool operator!=(const list<T,Alloc>& x, const list<T,Alloc>& y); 156227825Stheraventemplate <class T, class Alloc> 157227825Stheraven bool operator> (const list<T,Alloc>& x, const list<T,Alloc>& y); 158227825Stheraventemplate <class T, class Alloc> 159227825Stheraven bool operator>=(const list<T,Alloc>& x, const list<T,Alloc>& y); 160227825Stheraventemplate <class T, class Alloc> 161227825Stheraven bool operator<=(const list<T,Alloc>& x, const list<T,Alloc>& y); 162227825Stheraven 163227825Stheraventemplate <class T, class Alloc> 164227825Stheraven void swap(list<T,Alloc>& x, list<T,Alloc>& y) 165227825Stheraven noexcept(noexcept(x.swap(y))); 166227825Stheraven 167227825Stheraven} // std 168227825Stheraven 169227825Stheraven*/ 170227825Stheraven 171227825Stheraven#include <__config> 172227825Stheraven 173227825Stheraven#include <memory> 174227825Stheraven#include <limits> 175227825Stheraven#include <initializer_list> 176227825Stheraven#include <iterator> 177227825Stheraven#include <algorithm> 178300770Sdim#include <type_traits> 179227825Stheraven 180232924Stheraven#include <__undef_min_max> 181232924Stheraven 182276792Sdim#include <__debug> 183261272Sdim 184227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 185227825Stheraven#pragma GCC system_header 186227825Stheraven#endif 187227825Stheraven 188227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 189227825Stheraven 190227825Stheraventemplate <class _Tp, class _VoidPtr> struct __list_node; 191300770Sdimtemplate <class _Tp, class _VoidPtr> struct __list_node_base; 192227825Stheraven 193227825Stheraventemplate <class _Tp, class _VoidPtr> 194300770Sdimstruct __list_node_pointer_traits { 195300770Sdim typedef typename __rebind_pointer<_VoidPtr, __list_node<_Tp, _VoidPtr> >::type 196300770Sdim __node_pointer; 197300770Sdim typedef typename __rebind_pointer<_VoidPtr, __list_node_base<_Tp, _VoidPtr> >::type 198300770Sdim __base_pointer; 199227825Stheraven 200300770Sdim#if defined(_LIBCPP_ABI_LIST_REMOVE_NODE_POINTER_UB) 201300770Sdim typedef __base_pointer __link_pointer; 202253146Stheraven#else 203300770Sdim typedef typename conditional< 204300770Sdim is_pointer<_VoidPtr>::value, 205300770Sdim __base_pointer, 206300770Sdim __node_pointer 207300770Sdim >::type __link_pointer; 208253146Stheraven#endif 209253146Stheraven 210300770Sdim typedef typename conditional< 211300770Sdim is_same<__link_pointer, __node_pointer>::value, 212300770Sdim __base_pointer, 213300770Sdim __node_pointer 214300770Sdim >::type __non_link_pointer; 215227825Stheraven 216300770Sdim static _LIBCPP_INLINE_VISIBILITY 217300770Sdim __link_pointer __unsafe_link_pointer_cast(__link_pointer __p) { 218300770Sdim return __p; 219300770Sdim } 220300770Sdim 221300770Sdim static _LIBCPP_INLINE_VISIBILITY 222300770Sdim __link_pointer __unsafe_link_pointer_cast(__non_link_pointer __p) { 223300770Sdim return static_cast<__link_pointer>(static_cast<_VoidPtr>(__p)); 224300770Sdim } 225300770Sdim 226300770Sdim}; 227300770Sdim 228300770Sdimtemplate <class _Tp, class _VoidPtr> 229300770Sdimstruct __list_node_base 230300770Sdim{ 231300770Sdim typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits; 232300770Sdim typedef typename _NodeTraits::__node_pointer __node_pointer; 233300770Sdim typedef typename _NodeTraits::__base_pointer __base_pointer; 234300770Sdim typedef typename _NodeTraits::__link_pointer __link_pointer; 235300770Sdim 236300770Sdim __link_pointer __prev_; 237300770Sdim __link_pointer __next_; 238300770Sdim 239227825Stheraven _LIBCPP_INLINE_VISIBILITY 240300770Sdim __list_node_base() : __prev_(_NodeTraits::__unsafe_link_pointer_cast(__self())), 241300770Sdim __next_(_NodeTraits::__unsafe_link_pointer_cast(__self())) {} 242276792Sdim 243276792Sdim _LIBCPP_INLINE_VISIBILITY 244300770Sdim __base_pointer __self() { 245300770Sdim return pointer_traits<__base_pointer>::pointer_to(*this); 246276792Sdim } 247300770Sdim 248300770Sdim _LIBCPP_INLINE_VISIBILITY 249300770Sdim __node_pointer __as_node() { 250300770Sdim return static_cast<__node_pointer>(__self()); 251300770Sdim } 252227825Stheraven}; 253227825Stheraven 254227825Stheraventemplate <class _Tp, class _VoidPtr> 255227825Stheravenstruct __list_node 256227825Stheraven : public __list_node_base<_Tp, _VoidPtr> 257227825Stheraven{ 258227825Stheraven _Tp __value_; 259300770Sdim 260300770Sdim typedef __list_node_base<_Tp, _VoidPtr> __base; 261300770Sdim typedef typename __base::__link_pointer __link_pointer; 262300770Sdim 263300770Sdim _LIBCPP_INLINE_VISIBILITY 264300770Sdim __link_pointer __as_link() { 265300770Sdim return static_cast<__link_pointer>(__base::__self()); 266300770Sdim } 267227825Stheraven}; 268227825Stheraven 269288943Sdimtemplate <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TYPE_VIS_ONLY list; 270227825Stheraventemplate <class _Tp, class _Alloc> class __list_imp; 271261272Sdimtemplate <class _Tp, class _VoidPtr> class _LIBCPP_TYPE_VIS_ONLY __list_const_iterator; 272227825Stheraven 273227825Stheraventemplate <class _Tp, class _VoidPtr> 274261272Sdimclass _LIBCPP_TYPE_VIS_ONLY __list_iterator 275227825Stheraven{ 276300770Sdim typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits; 277300770Sdim typedef typename _NodeTraits::__link_pointer __link_pointer; 278227825Stheraven 279300770Sdim __link_pointer __ptr_; 280227825Stheraven 281227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 282227825Stheraven _LIBCPP_INLINE_VISIBILITY 283300770Sdim explicit __list_iterator(__link_pointer __p, const void* __c) _NOEXCEPT 284227825Stheraven : __ptr_(__p) 285227825Stheraven { 286227825Stheraven __get_db()->__insert_ic(this, __c); 287227825Stheraven } 288227825Stheraven#else 289227825Stheraven _LIBCPP_INLINE_VISIBILITY 290300770Sdim explicit __list_iterator(__link_pointer __p) _NOEXCEPT : __ptr_(__p) {} 291227825Stheraven#endif 292227825Stheraven 293227825Stheraven 294227825Stheraven 295227825Stheraven template<class, class> friend class list; 296227825Stheraven template<class, class> friend class __list_imp; 297227825Stheraven template<class, class> friend class __list_const_iterator; 298227825Stheravenpublic: 299227825Stheraven typedef bidirectional_iterator_tag iterator_category; 300227825Stheraven typedef _Tp value_type; 301227825Stheraven typedef value_type& reference; 302300770Sdim typedef typename __rebind_pointer<_VoidPtr, value_type>::type pointer; 303227825Stheraven typedef typename pointer_traits<pointer>::difference_type difference_type; 304227825Stheraven 305227825Stheraven _LIBCPP_INLINE_VISIBILITY 306261272Sdim __list_iterator() _NOEXCEPT : __ptr_(nullptr) 307227825Stheraven { 308227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 309227825Stheraven __get_db()->__insert_i(this); 310227825Stheraven#endif 311227825Stheraven } 312227825Stheraven 313227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 314227825Stheraven 315227825Stheraven _LIBCPP_INLINE_VISIBILITY 316227825Stheraven __list_iterator(const __list_iterator& __p) 317227825Stheraven : __ptr_(__p.__ptr_) 318227825Stheraven { 319227825Stheraven __get_db()->__iterator_copy(this, &__p); 320227825Stheraven } 321227825Stheraven 322227825Stheraven _LIBCPP_INLINE_VISIBILITY 323227825Stheraven ~__list_iterator() 324227825Stheraven { 325227825Stheraven __get_db()->__erase_i(this); 326227825Stheraven } 327227825Stheraven 328227825Stheraven _LIBCPP_INLINE_VISIBILITY 329227825Stheraven __list_iterator& operator=(const __list_iterator& __p) 330227825Stheraven { 331227825Stheraven if (this != &__p) 332227825Stheraven { 333227825Stheraven __get_db()->__iterator_copy(this, &__p); 334227825Stheraven __ptr_ = __p.__ptr_; 335227825Stheraven } 336227825Stheraven return *this; 337227825Stheraven } 338227825Stheraven 339227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 340227825Stheraven 341227825Stheraven _LIBCPP_INLINE_VISIBILITY 342227825Stheraven reference operator*() const 343227825Stheraven { 344227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 345227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 346227825Stheraven "Attempted to dereference a non-dereferenceable list::iterator"); 347227825Stheraven#endif 348300770Sdim return __ptr_->__as_node()->__value_; 349227825Stheraven } 350227825Stheraven _LIBCPP_INLINE_VISIBILITY 351253146Stheraven pointer operator->() const 352253146Stheraven { 353253146Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 354253146Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 355253146Stheraven "Attempted to dereference a non-dereferenceable list::iterator"); 356253146Stheraven#endif 357300770Sdim return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__value_); 358253146Stheraven } 359227825Stheraven 360227825Stheraven _LIBCPP_INLINE_VISIBILITY 361227825Stheraven __list_iterator& operator++() 362227825Stheraven { 363227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 364227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 365227825Stheraven "Attempted to increment non-incrementable list::iterator"); 366227825Stheraven#endif 367227825Stheraven __ptr_ = __ptr_->__next_; 368227825Stheraven return *this; 369227825Stheraven } 370227825Stheraven _LIBCPP_INLINE_VISIBILITY 371227825Stheraven __list_iterator operator++(int) {__list_iterator __t(*this); ++(*this); return __t;} 372227825Stheraven 373227825Stheraven _LIBCPP_INLINE_VISIBILITY 374227825Stheraven __list_iterator& operator--() 375227825Stheraven { 376227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 377227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__decrementable(this), 378227825Stheraven "Attempted to decrement non-decrementable list::iterator"); 379227825Stheraven#endif 380227825Stheraven __ptr_ = __ptr_->__prev_; 381227825Stheraven return *this; 382227825Stheraven } 383227825Stheraven _LIBCPP_INLINE_VISIBILITY 384227825Stheraven __list_iterator operator--(int) {__list_iterator __t(*this); --(*this); return __t;} 385227825Stheraven 386227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 387227825Stheraven bool operator==(const __list_iterator& __x, const __list_iterator& __y) 388227825Stheraven { 389227825Stheraven return __x.__ptr_ == __y.__ptr_; 390227825Stheraven } 391227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 392227825Stheraven bool operator!=(const __list_iterator& __x, const __list_iterator& __y) 393227825Stheraven {return !(__x == __y);} 394227825Stheraven}; 395227825Stheraven 396227825Stheraventemplate <class _Tp, class _VoidPtr> 397261272Sdimclass _LIBCPP_TYPE_VIS_ONLY __list_const_iterator 398227825Stheraven{ 399300770Sdim typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits; 400300770Sdim typedef typename _NodeTraits::__link_pointer __link_pointer; 401227825Stheraven 402300770Sdim __link_pointer __ptr_; 403227825Stheraven 404227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 405227825Stheraven _LIBCPP_INLINE_VISIBILITY 406300770Sdim explicit __list_const_iterator(__link_pointer __p, const void* __c) _NOEXCEPT 407227825Stheraven : __ptr_(__p) 408227825Stheraven { 409227825Stheraven __get_db()->__insert_ic(this, __c); 410227825Stheraven } 411227825Stheraven#else 412227825Stheraven _LIBCPP_INLINE_VISIBILITY 413300770Sdim explicit __list_const_iterator(__link_pointer __p) _NOEXCEPT : __ptr_(__p) {} 414227825Stheraven#endif 415227825Stheraven 416227825Stheraven template<class, class> friend class list; 417227825Stheraven template<class, class> friend class __list_imp; 418227825Stheravenpublic: 419227825Stheraven typedef bidirectional_iterator_tag iterator_category; 420227825Stheraven typedef _Tp value_type; 421227825Stheraven typedef const value_type& reference; 422300770Sdim typedef typename __rebind_pointer<_VoidPtr, const value_type>::type pointer; 423227825Stheraven typedef typename pointer_traits<pointer>::difference_type difference_type; 424227825Stheraven 425227825Stheraven _LIBCPP_INLINE_VISIBILITY 426261272Sdim __list_const_iterator() _NOEXCEPT : __ptr_(nullptr) 427227825Stheraven { 428227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 429227825Stheraven __get_db()->__insert_i(this); 430227825Stheraven#endif 431227825Stheraven } 432227825Stheraven _LIBCPP_INLINE_VISIBILITY 433249989Sdim __list_const_iterator(const __list_iterator<_Tp, _VoidPtr>& __p) _NOEXCEPT 434227825Stheraven : __ptr_(__p.__ptr_) 435227825Stheraven { 436227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 437227825Stheraven __get_db()->__iterator_copy(this, &__p); 438227825Stheraven#endif 439227825Stheraven } 440227825Stheraven 441227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 442227825Stheraven 443227825Stheraven _LIBCPP_INLINE_VISIBILITY 444227825Stheraven __list_const_iterator(const __list_const_iterator& __p) 445227825Stheraven : __ptr_(__p.__ptr_) 446227825Stheraven { 447227825Stheraven __get_db()->__iterator_copy(this, &__p); 448227825Stheraven } 449227825Stheraven 450227825Stheraven _LIBCPP_INLINE_VISIBILITY 451227825Stheraven ~__list_const_iterator() 452227825Stheraven { 453227825Stheraven __get_db()->__erase_i(this); 454227825Stheraven } 455227825Stheraven 456227825Stheraven _LIBCPP_INLINE_VISIBILITY 457227825Stheraven __list_const_iterator& operator=(const __list_const_iterator& __p) 458227825Stheraven { 459227825Stheraven if (this != &__p) 460227825Stheraven { 461227825Stheraven __get_db()->__iterator_copy(this, &__p); 462227825Stheraven __ptr_ = __p.__ptr_; 463227825Stheraven } 464227825Stheraven return *this; 465227825Stheraven } 466227825Stheraven 467227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 468227825Stheraven _LIBCPP_INLINE_VISIBILITY 469227825Stheraven reference operator*() const 470227825Stheraven { 471227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 472227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 473227825Stheraven "Attempted to dereference a non-dereferenceable list::const_iterator"); 474227825Stheraven#endif 475300770Sdim return __ptr_->__as_node()->__value_; 476227825Stheraven } 477227825Stheraven _LIBCPP_INLINE_VISIBILITY 478253146Stheraven pointer operator->() const 479253146Stheraven { 480253146Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 481253146Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 482253146Stheraven "Attempted to dereference a non-dereferenceable list::iterator"); 483253146Stheraven#endif 484300770Sdim return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__value_); 485253146Stheraven } 486227825Stheraven 487227825Stheraven _LIBCPP_INLINE_VISIBILITY 488227825Stheraven __list_const_iterator& operator++() 489227825Stheraven { 490227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 491227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 492227825Stheraven "Attempted to increment non-incrementable list::const_iterator"); 493227825Stheraven#endif 494227825Stheraven __ptr_ = __ptr_->__next_; 495227825Stheraven return *this; 496227825Stheraven } 497227825Stheraven _LIBCPP_INLINE_VISIBILITY 498227825Stheraven __list_const_iterator operator++(int) {__list_const_iterator __t(*this); ++(*this); return __t;} 499227825Stheraven 500227825Stheraven _LIBCPP_INLINE_VISIBILITY 501227825Stheraven __list_const_iterator& operator--() 502227825Stheraven { 503227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 504227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__decrementable(this), 505227825Stheraven "Attempted to decrement non-decrementable list::const_iterator"); 506227825Stheraven#endif 507227825Stheraven __ptr_ = __ptr_->__prev_; 508227825Stheraven return *this; 509227825Stheraven } 510227825Stheraven _LIBCPP_INLINE_VISIBILITY 511227825Stheraven __list_const_iterator operator--(int) {__list_const_iterator __t(*this); --(*this); return __t;} 512227825Stheraven 513227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 514227825Stheraven bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y) 515227825Stheraven { 516227825Stheraven return __x.__ptr_ == __y.__ptr_; 517227825Stheraven } 518227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 519227825Stheraven bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y) 520227825Stheraven {return !(__x == __y);} 521227825Stheraven}; 522227825Stheraven 523227825Stheraventemplate <class _Tp, class _Alloc> 524227825Stheravenclass __list_imp 525227825Stheraven{ 526227825Stheraven __list_imp(const __list_imp&); 527227825Stheraven __list_imp& operator=(const __list_imp&); 528227825Stheravenprotected: 529227825Stheraven typedef _Tp value_type; 530227825Stheraven typedef _Alloc allocator_type; 531227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 532227825Stheraven typedef typename __alloc_traits::size_type size_type; 533227825Stheraven typedef typename __alloc_traits::void_pointer __void_pointer; 534227825Stheraven typedef __list_iterator<value_type, __void_pointer> iterator; 535227825Stheraven typedef __list_const_iterator<value_type, __void_pointer> const_iterator; 536227825Stheraven typedef __list_node_base<value_type, __void_pointer> __node_base; 537227825Stheraven typedef __list_node<value_type, __void_pointer> __node; 538288943Sdim typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator; 539227825Stheraven typedef allocator_traits<__node_allocator> __node_alloc_traits; 540227825Stheraven typedef typename __node_alloc_traits::pointer __node_pointer; 541253146Stheraven typedef typename __node_alloc_traits::pointer __node_const_pointer; 542300770Sdim typedef __list_node_pointer_traits<value_type, __void_pointer> __node_pointer_traits; 543300770Sdim typedef typename __node_pointer_traits::__link_pointer __link_pointer; 544300770Sdim typedef __link_pointer __link_const_pointer; 545227825Stheraven typedef typename __alloc_traits::pointer pointer; 546227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 547227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 548227825Stheraven 549288943Sdim typedef typename __rebind_alloc_helper<__alloc_traits, __node_base>::type __node_base_allocator; 550253146Stheraven typedef typename allocator_traits<__node_base_allocator>::pointer __node_base_pointer; 551253146Stheraven 552227825Stheraven __node_base __end_; 553227825Stheraven __compressed_pair<size_type, __node_allocator> __size_alloc_; 554227825Stheraven 555227825Stheraven _LIBCPP_INLINE_VISIBILITY 556300770Sdim __link_pointer __end_as_link() const _NOEXCEPT { 557300770Sdim return __node_pointer_traits::__unsafe_link_pointer_cast( 558300770Sdim const_cast<__node_base&>(__end_).__self()); 559300770Sdim } 560300770Sdim 561300770Sdim _LIBCPP_INLINE_VISIBILITY 562227825Stheraven size_type& __sz() _NOEXCEPT {return __size_alloc_.first();} 563227825Stheraven _LIBCPP_INLINE_VISIBILITY 564227825Stheraven const size_type& __sz() const _NOEXCEPT 565227825Stheraven {return __size_alloc_.first();} 566227825Stheraven _LIBCPP_INLINE_VISIBILITY 567227825Stheraven __node_allocator& __node_alloc() _NOEXCEPT 568227825Stheraven {return __size_alloc_.second();} 569227825Stheraven _LIBCPP_INLINE_VISIBILITY 570227825Stheraven const __node_allocator& __node_alloc() const _NOEXCEPT 571227825Stheraven {return __size_alloc_.second();} 572227825Stheraven 573300770Sdim static void __unlink_nodes(__link_pointer __f, __link_pointer __l) _NOEXCEPT; 574227825Stheraven 575227825Stheraven __list_imp() 576227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value); 577227825Stheraven __list_imp(const allocator_type& __a); 578227825Stheraven ~__list_imp(); 579227825Stheraven void clear() _NOEXCEPT; 580227825Stheraven _LIBCPP_INLINE_VISIBILITY 581227825Stheraven bool empty() const _NOEXCEPT {return __sz() == 0;} 582227825Stheraven 583227825Stheraven _LIBCPP_INLINE_VISIBILITY 584227825Stheraven iterator begin() _NOEXCEPT 585227825Stheraven { 586227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 587227825Stheraven return iterator(__end_.__next_, this); 588227825Stheraven#else 589227825Stheraven return iterator(__end_.__next_); 590227825Stheraven#endif 591227825Stheraven } 592227825Stheraven _LIBCPP_INLINE_VISIBILITY 593227825Stheraven const_iterator begin() const _NOEXCEPT 594227825Stheraven { 595227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 596227825Stheraven return const_iterator(__end_.__next_, this); 597227825Stheraven#else 598227825Stheraven return const_iterator(__end_.__next_); 599227825Stheraven#endif 600227825Stheraven } 601227825Stheraven _LIBCPP_INLINE_VISIBILITY 602227825Stheraven iterator end() _NOEXCEPT 603227825Stheraven { 604227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 605300770Sdim return iterator(__end_as_link(), this); 606227825Stheraven#else 607300770Sdim return iterator(__end_as_link()); 608227825Stheraven#endif 609227825Stheraven } 610227825Stheraven _LIBCPP_INLINE_VISIBILITY 611227825Stheraven const_iterator end() const _NOEXCEPT 612227825Stheraven { 613227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 614300770Sdim return const_iterator(__end_as_link(), this); 615227825Stheraven#else 616300770Sdim return const_iterator(__end_as_link()); 617227825Stheraven#endif 618227825Stheraven } 619227825Stheraven 620227825Stheraven void swap(__list_imp& __c) 621288943Sdim#if _LIBCPP_STD_VER >= 14 622288943Sdim _NOEXCEPT; 623288943Sdim#else 624288943Sdim _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 625288943Sdim __is_nothrow_swappable<allocator_type>::value); 626288943Sdim#endif 627227825Stheraven 628227825Stheraven _LIBCPP_INLINE_VISIBILITY 629227825Stheraven void __copy_assign_alloc(const __list_imp& __c) 630227825Stheraven {__copy_assign_alloc(__c, integral_constant<bool, 631227825Stheraven __node_alloc_traits::propagate_on_container_copy_assignment::value>());} 632227825Stheraven 633227825Stheraven _LIBCPP_INLINE_VISIBILITY 634227825Stheraven void __move_assign_alloc(__list_imp& __c) 635227825Stheraven _NOEXCEPT_( 636227825Stheraven !__node_alloc_traits::propagate_on_container_move_assignment::value || 637227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 638227825Stheraven {__move_assign_alloc(__c, integral_constant<bool, 639227825Stheraven __node_alloc_traits::propagate_on_container_move_assignment::value>());} 640227825Stheraven 641227825Stheravenprivate: 642227825Stheraven _LIBCPP_INLINE_VISIBILITY 643227825Stheraven void __copy_assign_alloc(const __list_imp& __c, true_type) 644227825Stheraven { 645227825Stheraven if (__node_alloc() != __c.__node_alloc()) 646227825Stheraven clear(); 647227825Stheraven __node_alloc() = __c.__node_alloc(); 648227825Stheraven } 649227825Stheraven 650227825Stheraven _LIBCPP_INLINE_VISIBILITY 651227825Stheraven void __copy_assign_alloc(const __list_imp& __c, false_type) 652227825Stheraven {} 653227825Stheraven 654227825Stheraven _LIBCPP_INLINE_VISIBILITY 655227825Stheraven void __move_assign_alloc(__list_imp& __c, true_type) 656227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 657227825Stheraven { 658227825Stheraven __node_alloc() = _VSTD::move(__c.__node_alloc()); 659227825Stheraven } 660227825Stheraven 661227825Stheraven _LIBCPP_INLINE_VISIBILITY 662227825Stheraven void __move_assign_alloc(__list_imp& __c, false_type) 663227825Stheraven _NOEXCEPT 664227825Stheraven {} 665227825Stheraven}; 666227825Stheraven 667227825Stheraven// Unlink nodes [__f, __l] 668227825Stheraventemplate <class _Tp, class _Alloc> 669227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 670227825Stheravenvoid 671300770Sdim__list_imp<_Tp, _Alloc>::__unlink_nodes(__link_pointer __f, __link_pointer __l) 672227825Stheraven _NOEXCEPT 673227825Stheraven{ 674253146Stheraven __f->__prev_->__next_ = __l->__next_; 675253146Stheraven __l->__next_->__prev_ = __f->__prev_; 676227825Stheraven} 677227825Stheraven 678227825Stheraventemplate <class _Tp, class _Alloc> 679227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 680227825Stheraven__list_imp<_Tp, _Alloc>::__list_imp() 681227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 682227825Stheraven : __size_alloc_(0) 683227825Stheraven{ 684227825Stheraven} 685227825Stheraven 686227825Stheraventemplate <class _Tp, class _Alloc> 687227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 688227825Stheraven__list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a) 689227825Stheraven : __size_alloc_(0, __node_allocator(__a)) 690227825Stheraven{ 691227825Stheraven} 692227825Stheraven 693227825Stheraventemplate <class _Tp, class _Alloc> 694227825Stheraven__list_imp<_Tp, _Alloc>::~__list_imp() 695227825Stheraven{ 696227825Stheraven clear(); 697227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 698227825Stheraven __get_db()->__erase_c(this); 699227825Stheraven#endif 700227825Stheraven} 701227825Stheraven 702227825Stheraventemplate <class _Tp, class _Alloc> 703227825Stheravenvoid 704227825Stheraven__list_imp<_Tp, _Alloc>::clear() _NOEXCEPT 705227825Stheraven{ 706227825Stheraven if (!empty()) 707227825Stheraven { 708227825Stheraven __node_allocator& __na = __node_alloc(); 709300770Sdim __link_pointer __f = __end_.__next_; 710300770Sdim __link_pointer __l = __end_as_link(); 711253146Stheraven __unlink_nodes(__f, __l->__prev_); 712227825Stheraven __sz() = 0; 713227825Stheraven while (__f != __l) 714227825Stheraven { 715300770Sdim __node_pointer __np = __f->__as_node(); 716227825Stheraven __f = __f->__next_; 717300770Sdim __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 718300770Sdim __node_alloc_traits::deallocate(__na, __np, 1); 719227825Stheraven } 720227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 721227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 722227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 723227825Stheraven { 724227825Stheraven --__p; 725227825Stheraven const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); 726227825Stheraven if (__i->__ptr_ != __l) 727227825Stheraven { 728227825Stheraven (*__p)->__c_ = nullptr; 729227825Stheraven if (--__c->end_ != __p) 730227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 731227825Stheraven } 732227825Stheraven } 733227825Stheraven __get_db()->unlock(); 734227825Stheraven#endif 735227825Stheraven } 736227825Stheraven} 737227825Stheraven 738227825Stheraventemplate <class _Tp, class _Alloc> 739227825Stheravenvoid 740227825Stheraven__list_imp<_Tp, _Alloc>::swap(__list_imp& __c) 741288943Sdim#if _LIBCPP_STD_VER >= 14 742288943Sdim _NOEXCEPT 743288943Sdim#else 744288943Sdim _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 745288943Sdim __is_nothrow_swappable<allocator_type>::value) 746288943Sdim#endif 747227825Stheraven{ 748227825Stheraven _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value || 749227825Stheraven this->__node_alloc() == __c.__node_alloc(), 750227825Stheraven "list::swap: Either propagate_on_container_swap must be true" 751227825Stheraven " or the allocators must compare equal"); 752227825Stheraven using _VSTD::swap; 753288943Sdim __swap_allocator(__node_alloc(), __c.__node_alloc()); 754227825Stheraven swap(__sz(), __c.__sz()); 755227825Stheraven swap(__end_, __c.__end_); 756227825Stheraven if (__sz() == 0) 757300770Sdim __end_.__next_ = __end_.__prev_ = __end_as_link(); 758227825Stheraven else 759300770Sdim __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_as_link(); 760227825Stheraven if (__c.__sz() == 0) 761300770Sdim __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_as_link(); 762227825Stheraven else 763300770Sdim __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_as_link(); 764276792Sdim 765227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 766227825Stheraven __libcpp_db* __db = __get_db(); 767227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 768227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 769227825Stheraven std::swap(__cn1->beg_, __cn2->beg_); 770227825Stheraven std::swap(__cn1->end_, __cn2->end_); 771227825Stheraven std::swap(__cn1->cap_, __cn2->cap_); 772227825Stheraven for (__i_node** __p = __cn1->end_; __p != __cn1->beg_;) 773227825Stheraven { 774227825Stheraven --__p; 775227825Stheraven const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); 776300770Sdim if (__i->__ptr_ == __c.__end_as_link()) 777227825Stheraven { 778227825Stheraven __cn2->__add(*__p); 779227825Stheraven if (--__cn1->end_ != __p) 780227825Stheraven memmove(__p, __p+1, (__cn1->end_ - __p)*sizeof(__i_node*)); 781227825Stheraven } 782227825Stheraven else 783227825Stheraven (*__p)->__c_ = __cn1; 784227825Stheraven } 785227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 786227825Stheraven { 787227825Stheraven --__p; 788227825Stheraven const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); 789300770Sdim if (__i->__ptr_ == __end_as_link()) 790227825Stheraven { 791227825Stheraven __cn1->__add(*__p); 792227825Stheraven if (--__cn2->end_ != __p) 793227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 794227825Stheraven } 795227825Stheraven else 796227825Stheraven (*__p)->__c_ = __cn2; 797227825Stheraven } 798227825Stheraven __db->unlock(); 799227825Stheraven#endif 800227825Stheraven} 801227825Stheraven 802288943Sdimtemplate <class _Tp, class _Alloc /*= allocator<_Tp>*/> 803261272Sdimclass _LIBCPP_TYPE_VIS_ONLY list 804227825Stheraven : private __list_imp<_Tp, _Alloc> 805227825Stheraven{ 806227825Stheraven typedef __list_imp<_Tp, _Alloc> base; 807227825Stheraven typedef typename base::__node __node; 808227825Stheraven typedef typename base::__node_allocator __node_allocator; 809227825Stheraven typedef typename base::__node_pointer __node_pointer; 810227825Stheraven typedef typename base::__node_alloc_traits __node_alloc_traits; 811253146Stheraven typedef typename base::__node_base __node_base; 812253146Stheraven typedef typename base::__node_base_pointer __node_base_pointer; 813300770Sdim typedef typename base::__link_pointer __link_pointer; 814227825Stheraven 815227825Stheravenpublic: 816227825Stheraven typedef _Tp value_type; 817227825Stheraven typedef _Alloc allocator_type; 818227825Stheraven static_assert((is_same<value_type, typename allocator_type::value_type>::value), 819227825Stheraven "Invalid allocator::value_type"); 820227825Stheraven typedef value_type& reference; 821227825Stheraven typedef const value_type& const_reference; 822227825Stheraven typedef typename base::pointer pointer; 823227825Stheraven typedef typename base::const_pointer const_pointer; 824227825Stheraven typedef typename base::size_type size_type; 825227825Stheraven typedef typename base::difference_type difference_type; 826227825Stheraven typedef typename base::iterator iterator; 827227825Stheraven typedef typename base::const_iterator const_iterator; 828227825Stheraven typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 829227825Stheraven typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 830227825Stheraven 831227825Stheraven _LIBCPP_INLINE_VISIBILITY 832227825Stheraven list() 833227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 834227825Stheraven { 835227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 836227825Stheraven __get_db()->__insert_c(this); 837227825Stheraven#endif 838227825Stheraven } 839227825Stheraven _LIBCPP_INLINE_VISIBILITY 840261272Sdim explicit list(const allocator_type& __a) : base(__a) 841227825Stheraven { 842227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 843227825Stheraven __get_db()->__insert_c(this); 844227825Stheraven#endif 845227825Stheraven } 846261272Sdim explicit list(size_type __n); 847261272Sdim#if _LIBCPP_STD_VER > 11 848261272Sdim explicit list(size_type __n, const allocator_type& __a); 849261272Sdim#endif 850227825Stheraven list(size_type __n, const value_type& __x); 851227825Stheraven list(size_type __n, const value_type& __x, const allocator_type& __a); 852227825Stheraven template <class _InpIter> 853227825Stheraven list(_InpIter __f, _InpIter __l, 854227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); 855227825Stheraven template <class _InpIter> 856227825Stheraven list(_InpIter __f, _InpIter __l, const allocator_type& __a, 857227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); 858227825Stheraven 859227825Stheraven list(const list& __c); 860227825Stheraven list(const list& __c, const allocator_type& __a); 861227825Stheraven list& operator=(const list& __c); 862227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 863227825Stheraven list(initializer_list<value_type> __il); 864227825Stheraven list(initializer_list<value_type> __il, const allocator_type& __a); 865227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 866227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 867227825Stheraven list(list&& __c) 868227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value); 869227825Stheraven list(list&& __c, const allocator_type& __a); 870227825Stheraven list& operator=(list&& __c) 871227825Stheraven _NOEXCEPT_( 872227825Stheraven __node_alloc_traits::propagate_on_container_move_assignment::value && 873227825Stheraven is_nothrow_move_assignable<__node_allocator>::value); 874227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 875227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 876227825Stheraven _LIBCPP_INLINE_VISIBILITY 877227825Stheraven list& operator=(initializer_list<value_type> __il) 878227825Stheraven {assign(__il.begin(), __il.end()); return *this;} 879227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 880227825Stheraven 881227825Stheraven template <class _InpIter> 882227825Stheraven void assign(_InpIter __f, _InpIter __l, 883227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); 884227825Stheraven void assign(size_type __n, const value_type& __x); 885227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 886227825Stheraven _LIBCPP_INLINE_VISIBILITY 887227825Stheraven void assign(initializer_list<value_type> __il) 888227825Stheraven {assign(__il.begin(), __il.end());} 889227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 890227825Stheraven 891227825Stheraven allocator_type get_allocator() const _NOEXCEPT; 892227825Stheraven 893227825Stheraven _LIBCPP_INLINE_VISIBILITY 894227825Stheraven size_type size() const _NOEXCEPT {return base::__sz();} 895227825Stheraven _LIBCPP_INLINE_VISIBILITY 896227825Stheraven bool empty() const _NOEXCEPT {return base::empty();} 897227825Stheraven _LIBCPP_INLINE_VISIBILITY 898227825Stheraven size_type max_size() const _NOEXCEPT 899227825Stheraven {return numeric_limits<difference_type>::max();} 900227825Stheraven 901227825Stheraven _LIBCPP_INLINE_VISIBILITY 902227825Stheraven iterator begin() _NOEXCEPT {return base::begin();} 903227825Stheraven _LIBCPP_INLINE_VISIBILITY 904227825Stheraven const_iterator begin() const _NOEXCEPT {return base::begin();} 905227825Stheraven _LIBCPP_INLINE_VISIBILITY 906227825Stheraven iterator end() _NOEXCEPT {return base::end();} 907227825Stheraven _LIBCPP_INLINE_VISIBILITY 908227825Stheraven const_iterator end() const _NOEXCEPT {return base::end();} 909227825Stheraven _LIBCPP_INLINE_VISIBILITY 910227825Stheraven const_iterator cbegin() const _NOEXCEPT {return base::begin();} 911227825Stheraven _LIBCPP_INLINE_VISIBILITY 912227825Stheraven const_iterator cend() const _NOEXCEPT {return base::end();} 913227825Stheraven 914227825Stheraven _LIBCPP_INLINE_VISIBILITY 915227825Stheraven reverse_iterator rbegin() _NOEXCEPT 916227825Stheraven {return reverse_iterator(end());} 917227825Stheraven _LIBCPP_INLINE_VISIBILITY 918227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 919227825Stheraven {return const_reverse_iterator(end());} 920227825Stheraven _LIBCPP_INLINE_VISIBILITY 921227825Stheraven reverse_iterator rend() _NOEXCEPT 922227825Stheraven {return reverse_iterator(begin());} 923227825Stheraven _LIBCPP_INLINE_VISIBILITY 924227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 925227825Stheraven {return const_reverse_iterator(begin());} 926227825Stheraven _LIBCPP_INLINE_VISIBILITY 927227825Stheraven const_reverse_iterator crbegin() const _NOEXCEPT 928227825Stheraven {return const_reverse_iterator(end());} 929227825Stheraven _LIBCPP_INLINE_VISIBILITY 930227825Stheraven const_reverse_iterator crend() const _NOEXCEPT 931227825Stheraven {return const_reverse_iterator(begin());} 932227825Stheraven 933227825Stheraven _LIBCPP_INLINE_VISIBILITY 934227825Stheraven reference front() 935227825Stheraven { 936227825Stheraven _LIBCPP_ASSERT(!empty(), "list::front called on empty list"); 937300770Sdim return base::__end_.__next_->__as_node()->__value_; 938227825Stheraven } 939227825Stheraven _LIBCPP_INLINE_VISIBILITY 940227825Stheraven const_reference front() const 941227825Stheraven { 942227825Stheraven _LIBCPP_ASSERT(!empty(), "list::front called on empty list"); 943300770Sdim return base::__end_.__next_->__as_node()->__value_; 944227825Stheraven } 945227825Stheraven _LIBCPP_INLINE_VISIBILITY 946227825Stheraven reference back() 947227825Stheraven { 948227825Stheraven _LIBCPP_ASSERT(!empty(), "list::back called on empty list"); 949300770Sdim return base::__end_.__prev_->__as_node()->__value_; 950227825Stheraven } 951227825Stheraven _LIBCPP_INLINE_VISIBILITY 952227825Stheraven const_reference back() const 953227825Stheraven { 954227825Stheraven _LIBCPP_ASSERT(!empty(), "list::back called on empty list"); 955300770Sdim return base::__end_.__prev_->__as_node()->__value_; 956227825Stheraven } 957227825Stheraven 958227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 959227825Stheraven void push_front(value_type&& __x); 960227825Stheraven void push_back(value_type&& __x); 961227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 962227825Stheraven template <class... _Args> 963227825Stheraven void emplace_front(_Args&&... __args); 964227825Stheraven template <class... _Args> 965227825Stheraven void emplace_back(_Args&&... __args); 966227825Stheraven template <class... _Args> 967227825Stheraven iterator emplace(const_iterator __p, _Args&&... __args); 968227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 969227825Stheraven iterator insert(const_iterator __p, value_type&& __x); 970227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 971227825Stheraven 972227825Stheraven void push_front(const value_type& __x); 973227825Stheraven void push_back(const value_type& __x); 974227825Stheraven 975227825Stheraven iterator insert(const_iterator __p, const value_type& __x); 976227825Stheraven iterator insert(const_iterator __p, size_type __n, const value_type& __x); 977227825Stheraven template <class _InpIter> 978227825Stheraven iterator insert(const_iterator __p, _InpIter __f, _InpIter __l, 979227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); 980227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 981227825Stheraven _LIBCPP_INLINE_VISIBILITY 982227825Stheraven iterator insert(const_iterator __p, initializer_list<value_type> __il) 983227825Stheraven {return insert(__p, __il.begin(), __il.end());} 984227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 985227825Stheraven 986227825Stheraven _LIBCPP_INLINE_VISIBILITY 987227825Stheraven void swap(list& __c) 988288943Sdim#if _LIBCPP_STD_VER >= 14 989288943Sdim _NOEXCEPT 990288943Sdim#else 991227825Stheraven _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || 992227825Stheraven __is_nothrow_swappable<__node_allocator>::value) 993288943Sdim#endif 994227825Stheraven {base::swap(__c);} 995227825Stheraven _LIBCPP_INLINE_VISIBILITY 996227825Stheraven void clear() _NOEXCEPT {base::clear();} 997227825Stheraven 998227825Stheraven void pop_front(); 999227825Stheraven void pop_back(); 1000227825Stheraven 1001227825Stheraven iterator erase(const_iterator __p); 1002227825Stheraven iterator erase(const_iterator __f, const_iterator __l); 1003227825Stheraven 1004227825Stheraven void resize(size_type __n); 1005227825Stheraven void resize(size_type __n, const value_type& __x); 1006227825Stheraven 1007227825Stheraven void splice(const_iterator __p, list& __c); 1008227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1009227825Stheraven _LIBCPP_INLINE_VISIBILITY 1010227825Stheraven void splice(const_iterator __p, list&& __c) {splice(__p, __c);} 1011227825Stheraven#endif 1012227825Stheraven void splice(const_iterator __p, list& __c, const_iterator __i); 1013227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1014227825Stheraven _LIBCPP_INLINE_VISIBILITY 1015227825Stheraven void splice(const_iterator __p, list&& __c, const_iterator __i) 1016227825Stheraven {splice(__p, __c, __i);} 1017227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1018227825Stheraven void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l); 1019227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1020227825Stheraven _LIBCPP_INLINE_VISIBILITY 1021227825Stheraven void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l) 1022227825Stheraven {splice(__p, __c, __f, __l);} 1023227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1024227825Stheraven 1025227825Stheraven void remove(const value_type& __x); 1026227825Stheraven template <class _Pred> void remove_if(_Pred __pred); 1027227825Stheraven void unique(); 1028227825Stheraven template <class _BinaryPred> 1029227825Stheraven void unique(_BinaryPred __binary_pred); 1030227825Stheraven void merge(list& __c); 1031227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1032227825Stheraven _LIBCPP_INLINE_VISIBILITY 1033227825Stheraven void merge(list&& __c) {merge(__c);} 1034227825Stheraven#endif 1035227825Stheraven template <class _Comp> 1036227825Stheraven void merge(list& __c, _Comp __comp); 1037227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1038227825Stheraven template <class _Comp> 1039227825Stheraven _LIBCPP_INLINE_VISIBILITY 1040227825Stheraven void merge(list&& __c, _Comp __comp) {merge(__c, __comp);} 1041227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1042227825Stheraven void sort(); 1043227825Stheraven template <class _Comp> 1044227825Stheraven void sort(_Comp __comp); 1045227825Stheraven 1046227825Stheraven void reverse() _NOEXCEPT; 1047227825Stheraven 1048227825Stheraven bool __invariants() const; 1049227825Stheraven 1050227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1051227825Stheraven 1052227825Stheraven bool __dereferenceable(const const_iterator* __i) const; 1053227825Stheraven bool __decrementable(const const_iterator* __i) const; 1054227825Stheraven bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 1055227825Stheraven bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 1056227825Stheraven 1057227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 1058227825Stheraven 1059227825Stheravenprivate: 1060300770Sdim static void __link_nodes (__link_pointer __p, __link_pointer __f, __link_pointer __l); 1061300770Sdim void __link_nodes_at_front(__link_pointer __f, __link_pointer __l); 1062300770Sdim void __link_nodes_at_back (__link_pointer __f, __link_pointer __l); 1063227825Stheraven iterator __iterator(size_type __n); 1064227825Stheraven template <class _Comp> 1065227825Stheraven static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp); 1066227825Stheraven 1067227825Stheraven void __move_assign(list& __c, true_type) 1068227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value); 1069227825Stheraven void __move_assign(list& __c, false_type); 1070227825Stheraven}; 1071227825Stheraven 1072227825Stheraven// Link in nodes [__f, __l] just prior to __p 1073227825Stheraventemplate <class _Tp, class _Alloc> 1074227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1075227825Stheravenvoid 1076300770Sdimlist<_Tp, _Alloc>::__link_nodes(__link_pointer __p, __link_pointer __f, __link_pointer __l) 1077227825Stheraven{ 1078253146Stheraven __p->__prev_->__next_ = __f; 1079253146Stheraven __f->__prev_ = __p->__prev_; 1080253146Stheraven __p->__prev_ = __l; 1081253146Stheraven __l->__next_ = __p; 1082227825Stheraven} 1083227825Stheraven 1084276792Sdim// Link in nodes [__f, __l] at the front of the list 1085227825Stheraventemplate <class _Tp, class _Alloc> 1086227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1087276792Sdimvoid 1088300770Sdimlist<_Tp, _Alloc>::__link_nodes_at_front(__link_pointer __f, __link_pointer __l) 1089276792Sdim{ 1090300770Sdim __f->__prev_ = base::__end_as_link(); 1091276792Sdim __l->__next_ = base::__end_.__next_; 1092276792Sdim __l->__next_->__prev_ = __l; 1093276792Sdim base::__end_.__next_ = __f; 1094276792Sdim} 1095276792Sdim 1096276792Sdim// Link in nodes [__f, __l] at the front of the list 1097276792Sdimtemplate <class _Tp, class _Alloc> 1098276792Sdiminline _LIBCPP_INLINE_VISIBILITY 1099276792Sdimvoid 1100300770Sdimlist<_Tp, _Alloc>::__link_nodes_at_back(__link_pointer __f, __link_pointer __l) 1101276792Sdim{ 1102300770Sdim __l->__next_ = base::__end_as_link(); 1103276792Sdim __f->__prev_ = base::__end_.__prev_; 1104276792Sdim __f->__prev_->__next_ = __f; 1105276792Sdim base::__end_.__prev_ = __l; 1106276792Sdim} 1107276792Sdim 1108276792Sdim 1109276792Sdimtemplate <class _Tp, class _Alloc> 1110276792Sdiminline _LIBCPP_INLINE_VISIBILITY 1111227825Stheraventypename list<_Tp, _Alloc>::iterator 1112227825Stheravenlist<_Tp, _Alloc>::__iterator(size_type __n) 1113227825Stheraven{ 1114227825Stheraven return __n <= base::__sz() / 2 ? _VSTD::next(begin(), __n) 1115227825Stheraven : _VSTD::prev(end(), base::__sz() - __n); 1116227825Stheraven} 1117227825Stheraven 1118227825Stheraventemplate <class _Tp, class _Alloc> 1119227825Stheravenlist<_Tp, _Alloc>::list(size_type __n) 1120227825Stheraven{ 1121227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1122227825Stheraven __get_db()->__insert_c(this); 1123227825Stheraven#endif 1124227825Stheraven for (; __n > 0; --__n) 1125227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1126227825Stheraven emplace_back(); 1127227825Stheraven#else 1128227825Stheraven push_back(value_type()); 1129227825Stheraven#endif 1130227825Stheraven} 1131227825Stheraven 1132261272Sdim#if _LIBCPP_STD_VER > 11 1133227825Stheraventemplate <class _Tp, class _Alloc> 1134261272Sdimlist<_Tp, _Alloc>::list(size_type __n, const allocator_type& __a) : base(__a) 1135261272Sdim{ 1136261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1137261272Sdim __get_db()->__insert_c(this); 1138261272Sdim#endif 1139261272Sdim for (; __n > 0; --__n) 1140261272Sdim#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1141261272Sdim emplace_back(); 1142261272Sdim#else 1143261272Sdim push_back(value_type()); 1144261272Sdim#endif 1145261272Sdim} 1146261272Sdim#endif 1147261272Sdim 1148261272Sdimtemplate <class _Tp, class _Alloc> 1149227825Stheravenlist<_Tp, _Alloc>::list(size_type __n, const value_type& __x) 1150227825Stheraven{ 1151227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1152227825Stheraven __get_db()->__insert_c(this); 1153227825Stheraven#endif 1154227825Stheraven for (; __n > 0; --__n) 1155227825Stheraven push_back(__x); 1156227825Stheraven} 1157227825Stheraven 1158227825Stheraventemplate <class _Tp, class _Alloc> 1159227825Stheravenlist<_Tp, _Alloc>::list(size_type __n, const value_type& __x, const allocator_type& __a) 1160227825Stheraven : base(__a) 1161227825Stheraven{ 1162227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1163227825Stheraven __get_db()->__insert_c(this); 1164227825Stheraven#endif 1165227825Stheraven for (; __n > 0; --__n) 1166227825Stheraven push_back(__x); 1167227825Stheraven} 1168227825Stheraven 1169227825Stheraventemplate <class _Tp, class _Alloc> 1170227825Stheraventemplate <class _InpIter> 1171227825Stheravenlist<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, 1172227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type*) 1173227825Stheraven{ 1174227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1175227825Stheraven __get_db()->__insert_c(this); 1176227825Stheraven#endif 1177227825Stheraven for (; __f != __l; ++__f) 1178227825Stheraven push_back(*__f); 1179227825Stheraven} 1180227825Stheraven 1181227825Stheraventemplate <class _Tp, class _Alloc> 1182227825Stheraventemplate <class _InpIter> 1183227825Stheravenlist<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a, 1184227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type*) 1185227825Stheraven : base(__a) 1186227825Stheraven{ 1187227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1188227825Stheraven __get_db()->__insert_c(this); 1189227825Stheraven#endif 1190227825Stheraven for (; __f != __l; ++__f) 1191227825Stheraven push_back(*__f); 1192227825Stheraven} 1193227825Stheraven 1194227825Stheraventemplate <class _Tp, class _Alloc> 1195227825Stheravenlist<_Tp, _Alloc>::list(const list& __c) 1196227825Stheraven : base(allocator_type( 1197227825Stheraven __node_alloc_traits::select_on_container_copy_construction( 1198227825Stheraven __c.__node_alloc()))) 1199227825Stheraven{ 1200227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1201227825Stheraven __get_db()->__insert_c(this); 1202227825Stheraven#endif 1203227825Stheraven for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) 1204227825Stheraven push_back(*__i); 1205227825Stheraven} 1206227825Stheraven 1207227825Stheraventemplate <class _Tp, class _Alloc> 1208227825Stheravenlist<_Tp, _Alloc>::list(const list& __c, const allocator_type& __a) 1209227825Stheraven : base(__a) 1210227825Stheraven{ 1211227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1212227825Stheraven __get_db()->__insert_c(this); 1213227825Stheraven#endif 1214227825Stheraven for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) 1215227825Stheraven push_back(*__i); 1216227825Stheraven} 1217227825Stheraven 1218227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1219227825Stheraven 1220227825Stheraventemplate <class _Tp, class _Alloc> 1221227825Stheravenlist<_Tp, _Alloc>::list(initializer_list<value_type> __il, const allocator_type& __a) 1222227825Stheraven : base(__a) 1223227825Stheraven{ 1224227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1225227825Stheraven __get_db()->__insert_c(this); 1226227825Stheraven#endif 1227227825Stheraven for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), 1228227825Stheraven __e = __il.end(); __i != __e; ++__i) 1229227825Stheraven push_back(*__i); 1230227825Stheraven} 1231227825Stheraven 1232227825Stheraventemplate <class _Tp, class _Alloc> 1233227825Stheravenlist<_Tp, _Alloc>::list(initializer_list<value_type> __il) 1234227825Stheraven{ 1235227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1236227825Stheraven __get_db()->__insert_c(this); 1237227825Stheraven#endif 1238227825Stheraven for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), 1239227825Stheraven __e = __il.end(); __i != __e; ++__i) 1240227825Stheraven push_back(*__i); 1241227825Stheraven} 1242227825Stheraven 1243227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1244227825Stheraven 1245227825Stheraventemplate <class _Tp, class _Alloc> 1246227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1247227825Stheravenlist<_Tp, _Alloc>& 1248227825Stheravenlist<_Tp, _Alloc>::operator=(const list& __c) 1249227825Stheraven{ 1250227825Stheraven if (this != &__c) 1251227825Stheraven { 1252227825Stheraven base::__copy_assign_alloc(__c); 1253227825Stheraven assign(__c.begin(), __c.end()); 1254227825Stheraven } 1255227825Stheraven return *this; 1256227825Stheraven} 1257227825Stheraven 1258227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1259227825Stheraven 1260227825Stheraventemplate <class _Tp, class _Alloc> 1261227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1262227825Stheravenlist<_Tp, _Alloc>::list(list&& __c) 1263227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value) 1264227825Stheraven : base(allocator_type(_VSTD::move(__c.__node_alloc()))) 1265227825Stheraven{ 1266227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1267227825Stheraven __get_db()->__insert_c(this); 1268227825Stheraven#endif 1269227825Stheraven splice(end(), __c); 1270227825Stheraven} 1271227825Stheraven 1272227825Stheraventemplate <class _Tp, class _Alloc> 1273227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1274227825Stheravenlist<_Tp, _Alloc>::list(list&& __c, const allocator_type& __a) 1275227825Stheraven : base(__a) 1276227825Stheraven{ 1277227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1278227825Stheraven __get_db()->__insert_c(this); 1279227825Stheraven#endif 1280227825Stheraven if (__a == __c.get_allocator()) 1281227825Stheraven splice(end(), __c); 1282227825Stheraven else 1283227825Stheraven { 1284232924Stheraven typedef move_iterator<iterator> _Ip; 1285232924Stheraven assign(_Ip(__c.begin()), _Ip(__c.end())); 1286227825Stheraven } 1287227825Stheraven} 1288227825Stheraven 1289227825Stheraventemplate <class _Tp, class _Alloc> 1290227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1291227825Stheravenlist<_Tp, _Alloc>& 1292227825Stheravenlist<_Tp, _Alloc>::operator=(list&& __c) 1293227825Stheraven _NOEXCEPT_( 1294227825Stheraven __node_alloc_traits::propagate_on_container_move_assignment::value && 1295227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 1296227825Stheraven{ 1297227825Stheraven __move_assign(__c, integral_constant<bool, 1298227825Stheraven __node_alloc_traits::propagate_on_container_move_assignment::value>()); 1299227825Stheraven return *this; 1300227825Stheraven} 1301227825Stheraven 1302227825Stheraventemplate <class _Tp, class _Alloc> 1303227825Stheravenvoid 1304227825Stheravenlist<_Tp, _Alloc>::__move_assign(list& __c, false_type) 1305227825Stheraven{ 1306227825Stheraven if (base::__node_alloc() != __c.__node_alloc()) 1307227825Stheraven { 1308232924Stheraven typedef move_iterator<iterator> _Ip; 1309232924Stheraven assign(_Ip(__c.begin()), _Ip(__c.end())); 1310227825Stheraven } 1311227825Stheraven else 1312227825Stheraven __move_assign(__c, true_type()); 1313227825Stheraven} 1314227825Stheraven 1315227825Stheraventemplate <class _Tp, class _Alloc> 1316227825Stheravenvoid 1317227825Stheravenlist<_Tp, _Alloc>::__move_assign(list& __c, true_type) 1318227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 1319227825Stheraven{ 1320227825Stheraven clear(); 1321227825Stheraven base::__move_assign_alloc(__c); 1322227825Stheraven splice(end(), __c); 1323227825Stheraven} 1324227825Stheraven 1325227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1326227825Stheraven 1327227825Stheraventemplate <class _Tp, class _Alloc> 1328227825Stheraventemplate <class _InpIter> 1329227825Stheravenvoid 1330227825Stheravenlist<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l, 1331227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type*) 1332227825Stheraven{ 1333227825Stheraven iterator __i = begin(); 1334227825Stheraven iterator __e = end(); 1335227825Stheraven for (; __f != __l && __i != __e; ++__f, ++__i) 1336227825Stheraven *__i = *__f; 1337227825Stheraven if (__i == __e) 1338227825Stheraven insert(__e, __f, __l); 1339227825Stheraven else 1340227825Stheraven erase(__i, __e); 1341227825Stheraven} 1342227825Stheraven 1343227825Stheraventemplate <class _Tp, class _Alloc> 1344227825Stheravenvoid 1345227825Stheravenlist<_Tp, _Alloc>::assign(size_type __n, const value_type& __x) 1346227825Stheraven{ 1347227825Stheraven iterator __i = begin(); 1348227825Stheraven iterator __e = end(); 1349227825Stheraven for (; __n > 0 && __i != __e; --__n, ++__i) 1350227825Stheraven *__i = __x; 1351227825Stheraven if (__i == __e) 1352227825Stheraven insert(__e, __n, __x); 1353227825Stheraven else 1354227825Stheraven erase(__i, __e); 1355227825Stheraven} 1356227825Stheraven 1357227825Stheraventemplate <class _Tp, class _Alloc> 1358227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1359227825Stheraven_Alloc 1360227825Stheravenlist<_Tp, _Alloc>::get_allocator() const _NOEXCEPT 1361227825Stheraven{ 1362227825Stheraven return allocator_type(base::__node_alloc()); 1363227825Stheraven} 1364227825Stheraven 1365227825Stheraventemplate <class _Tp, class _Alloc> 1366227825Stheraventypename list<_Tp, _Alloc>::iterator 1367227825Stheravenlist<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x) 1368227825Stheraven{ 1369227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1370227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1371227825Stheraven "list::insert(iterator, x) called with an iterator not" 1372227825Stheraven " referring to this list"); 1373227825Stheraven#endif 1374227825Stheraven __node_allocator& __na = base::__node_alloc(); 1375232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1376232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1377227825Stheraven __hold->__prev_ = 0; 1378227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1379300770Sdim __link_nodes(__p.__ptr_, __hold->__as_link(), __hold->__as_link()); 1380227825Stheraven ++base::__sz(); 1381249989Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1382300770Sdim return iterator(__hold.release()->__as_link(), this); 1383249989Sdim#else 1384300770Sdim return iterator(__hold.release()->__as_link()); 1385249989Sdim#endif 1386227825Stheraven} 1387227825Stheraven 1388227825Stheraventemplate <class _Tp, class _Alloc> 1389227825Stheraventypename list<_Tp, _Alloc>::iterator 1390227825Stheravenlist<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x) 1391227825Stheraven{ 1392227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1393227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1394227825Stheraven "list::insert(iterator, n, x) called with an iterator not" 1395227825Stheraven " referring to this list"); 1396253146Stheraven iterator __r(__p.__ptr_, this); 1397227825Stheraven#else 1398253146Stheraven iterator __r(__p.__ptr_); 1399227825Stheraven#endif 1400227825Stheraven if (__n > 0) 1401227825Stheraven { 1402227825Stheraven size_type __ds = 0; 1403227825Stheraven __node_allocator& __na = base::__node_alloc(); 1404232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1405232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1406227825Stheraven __hold->__prev_ = 0; 1407227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1408227825Stheraven ++__ds; 1409227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1410300770Sdim __r = iterator(__hold->__as_link(), this); 1411227825Stheraven#else 1412300770Sdim __r = iterator(__hold->__as_link()); 1413227825Stheraven#endif 1414227825Stheraven __hold.release(); 1415227825Stheraven iterator __e = __r; 1416227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1417227825Stheraven try 1418227825Stheraven { 1419227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1420227825Stheraven for (--__n; __n != 0; --__n, ++__e, ++__ds) 1421227825Stheraven { 1422227825Stheraven __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1423227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1424300770Sdim __e.__ptr_->__next_ = __hold->__as_link(); 1425227825Stheraven __hold->__prev_ = __e.__ptr_; 1426227825Stheraven __hold.release(); 1427227825Stheraven } 1428227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1429227825Stheraven } 1430227825Stheraven catch (...) 1431227825Stheraven { 1432227825Stheraven while (true) 1433227825Stheraven { 1434227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1435300770Sdim __link_pointer __prev = __e.__ptr_->__prev_; 1436300770Sdim __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1); 1437227825Stheraven if (__prev == 0) 1438227825Stheraven break; 1439227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1440227825Stheraven __e = iterator(__prev, this); 1441227825Stheraven#else 1442227825Stheraven __e = iterator(__prev); 1443227825Stheraven#endif 1444227825Stheraven } 1445227825Stheraven throw; 1446227825Stheraven } 1447227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1448253146Stheraven __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_); 1449227825Stheraven base::__sz() += __ds; 1450227825Stheraven } 1451227825Stheraven return __r; 1452227825Stheraven} 1453227825Stheraven 1454227825Stheraventemplate <class _Tp, class _Alloc> 1455227825Stheraventemplate <class _InpIter> 1456227825Stheraventypename list<_Tp, _Alloc>::iterator 1457227825Stheravenlist<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l, 1458227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type*) 1459227825Stheraven{ 1460227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1461227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1462227825Stheraven "list::insert(iterator, range) called with an iterator not" 1463227825Stheraven " referring to this list"); 1464253146Stheraven iterator __r(__p.__ptr_, this); 1465227825Stheraven#else 1466253146Stheraven iterator __r(__p.__ptr_); 1467227825Stheraven#endif 1468227825Stheraven if (__f != __l) 1469227825Stheraven { 1470227825Stheraven size_type __ds = 0; 1471227825Stheraven __node_allocator& __na = base::__node_alloc(); 1472232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1473232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1474227825Stheraven __hold->__prev_ = 0; 1475227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f); 1476227825Stheraven ++__ds; 1477227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1478300770Sdim __r = iterator(__hold.get()->__as_link(), this); 1479227825Stheraven#else 1480300770Sdim __r = iterator(__hold.get()->__as_link()); 1481227825Stheraven#endif 1482227825Stheraven __hold.release(); 1483227825Stheraven iterator __e = __r; 1484227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1485227825Stheraven try 1486227825Stheraven { 1487227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1488288943Sdim for (++__f; __f != __l; ++__f, (void) ++__e, (void) ++__ds) 1489227825Stheraven { 1490227825Stheraven __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1491227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f); 1492300770Sdim __e.__ptr_->__next_ = __hold.get()->__as_link(); 1493227825Stheraven __hold->__prev_ = __e.__ptr_; 1494227825Stheraven __hold.release(); 1495227825Stheraven } 1496227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1497227825Stheraven } 1498227825Stheraven catch (...) 1499227825Stheraven { 1500227825Stheraven while (true) 1501227825Stheraven { 1502227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1503300770Sdim __link_pointer __prev = __e.__ptr_->__prev_; 1504300770Sdim __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1); 1505227825Stheraven if (__prev == 0) 1506227825Stheraven break; 1507227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1508227825Stheraven __e = iterator(__prev, this); 1509227825Stheraven#else 1510227825Stheraven __e = iterator(__prev); 1511227825Stheraven#endif 1512227825Stheraven } 1513227825Stheraven throw; 1514227825Stheraven } 1515227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1516253146Stheraven __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_); 1517227825Stheraven base::__sz() += __ds; 1518227825Stheraven } 1519227825Stheraven return __r; 1520227825Stheraven} 1521227825Stheraven 1522227825Stheraventemplate <class _Tp, class _Alloc> 1523227825Stheravenvoid 1524227825Stheravenlist<_Tp, _Alloc>::push_front(const value_type& __x) 1525227825Stheraven{ 1526227825Stheraven __node_allocator& __na = base::__node_alloc(); 1527232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1528232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1529227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1530300770Sdim __link_pointer __nl = __hold->__as_link(); 1531300770Sdim __link_nodes_at_front(__nl, __nl); 1532227825Stheraven ++base::__sz(); 1533227825Stheraven __hold.release(); 1534227825Stheraven} 1535227825Stheraven 1536227825Stheraventemplate <class _Tp, class _Alloc> 1537227825Stheravenvoid 1538227825Stheravenlist<_Tp, _Alloc>::push_back(const value_type& __x) 1539227825Stheraven{ 1540227825Stheraven __node_allocator& __na = base::__node_alloc(); 1541232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1542232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1543227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1544300770Sdim __link_nodes_at_back(__hold.get()->__as_link(), __hold.get()->__as_link()); 1545227825Stheraven ++base::__sz(); 1546227825Stheraven __hold.release(); 1547227825Stheraven} 1548227825Stheraven 1549227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1550227825Stheraven 1551227825Stheraventemplate <class _Tp, class _Alloc> 1552227825Stheravenvoid 1553227825Stheravenlist<_Tp, _Alloc>::push_front(value_type&& __x) 1554227825Stheraven{ 1555227825Stheraven __node_allocator& __na = base::__node_alloc(); 1556232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1557232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1558227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); 1559300770Sdim __link_nodes_at_front(__hold.get()->__as_link(), __hold.get()->__as_link()); 1560227825Stheraven ++base::__sz(); 1561227825Stheraven __hold.release(); 1562227825Stheraven} 1563227825Stheraven 1564227825Stheraventemplate <class _Tp, class _Alloc> 1565227825Stheravenvoid 1566227825Stheravenlist<_Tp, _Alloc>::push_back(value_type&& __x) 1567227825Stheraven{ 1568227825Stheraven __node_allocator& __na = base::__node_alloc(); 1569232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1570232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1571227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); 1572300770Sdim __link_nodes_at_back(__hold.get()->__as_link(), __hold.get()->__as_link()); 1573227825Stheraven ++base::__sz(); 1574227825Stheraven __hold.release(); 1575227825Stheraven} 1576227825Stheraven 1577227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1578227825Stheraven 1579227825Stheraventemplate <class _Tp, class _Alloc> 1580227825Stheraventemplate <class... _Args> 1581227825Stheravenvoid 1582227825Stheravenlist<_Tp, _Alloc>::emplace_front(_Args&&... __args) 1583227825Stheraven{ 1584227825Stheraven __node_allocator& __na = base::__node_alloc(); 1585232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1586232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1587227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); 1588300770Sdim __link_nodes_at_front(__hold.get()->__as_link(), __hold.get()->__as_link()); 1589227825Stheraven ++base::__sz(); 1590227825Stheraven __hold.release(); 1591227825Stheraven} 1592227825Stheraven 1593227825Stheraventemplate <class _Tp, class _Alloc> 1594227825Stheraventemplate <class... _Args> 1595227825Stheravenvoid 1596227825Stheravenlist<_Tp, _Alloc>::emplace_back(_Args&&... __args) 1597227825Stheraven{ 1598227825Stheraven __node_allocator& __na = base::__node_alloc(); 1599232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1600232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1601227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); 1602300770Sdim __link_pointer __nl = __hold->__as_link(); 1603300770Sdim __link_nodes_at_back(__nl, __nl); 1604227825Stheraven ++base::__sz(); 1605227825Stheraven __hold.release(); 1606227825Stheraven} 1607227825Stheraven 1608227825Stheraventemplate <class _Tp, class _Alloc> 1609227825Stheraventemplate <class... _Args> 1610227825Stheraventypename list<_Tp, _Alloc>::iterator 1611227825Stheravenlist<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args) 1612227825Stheraven{ 1613249989Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1614249989Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1615249989Sdim "list::emplace(iterator, args...) called with an iterator not" 1616249989Sdim " referring to this list"); 1617249989Sdim#endif 1618227825Stheraven __node_allocator& __na = base::__node_alloc(); 1619232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1620232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1621227825Stheraven __hold->__prev_ = 0; 1622227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); 1623300770Sdim __link_pointer __nl = __hold.get()->__as_link(); 1624300770Sdim __link_nodes(__p.__ptr_, __nl, __nl); 1625227825Stheraven ++base::__sz(); 1626300770Sdim __hold.release(); 1627227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1628300770Sdim return iterator(__nl, this); 1629227825Stheraven#else 1630300770Sdim return iterator(__nl); 1631227825Stheraven#endif 1632227825Stheraven} 1633227825Stheraven 1634227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1635227825Stheraven 1636227825Stheraventemplate <class _Tp, class _Alloc> 1637227825Stheraventypename list<_Tp, _Alloc>::iterator 1638227825Stheravenlist<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x) 1639227825Stheraven{ 1640227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1641227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1642227825Stheraven "list::insert(iterator, x) called with an iterator not" 1643227825Stheraven " referring to this list"); 1644227825Stheraven#endif 1645227825Stheraven __node_allocator& __na = base::__node_alloc(); 1646232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1647232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1648227825Stheraven __hold->__prev_ = 0; 1649227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); 1650300770Sdim __link_pointer __nl = __hold->__as_link(); 1651300770Sdim __link_nodes(__p.__ptr_, __nl, __nl); 1652227825Stheraven ++base::__sz(); 1653300770Sdim __hold.release(); 1654227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1655300770Sdim return iterator(__nl, this); 1656227825Stheraven#else 1657300770Sdim return iterator(__nl); 1658227825Stheraven#endif 1659227825Stheraven} 1660227825Stheraven 1661227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1662227825Stheraven 1663227825Stheraventemplate <class _Tp, class _Alloc> 1664227825Stheravenvoid 1665227825Stheravenlist<_Tp, _Alloc>::pop_front() 1666227825Stheraven{ 1667227825Stheraven _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list"); 1668227825Stheraven __node_allocator& __na = base::__node_alloc(); 1669300770Sdim __link_pointer __n = base::__end_.__next_; 1670227825Stheraven base::__unlink_nodes(__n, __n); 1671227825Stheraven --base::__sz(); 1672227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1673227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 1674227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1675227825Stheraven { 1676227825Stheraven --__p; 1677227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1678253146Stheraven if (__i->__ptr_ == __n) 1679227825Stheraven { 1680227825Stheraven (*__p)->__c_ = nullptr; 1681227825Stheraven if (--__c->end_ != __p) 1682227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1683227825Stheraven } 1684227825Stheraven } 1685227825Stheraven __get_db()->unlock(); 1686227825Stheraven#endif 1687300770Sdim __node_pointer __np = __n->__as_node(); 1688300770Sdim __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1689300770Sdim __node_alloc_traits::deallocate(__na, __np, 1); 1690227825Stheraven} 1691227825Stheraven 1692227825Stheraventemplate <class _Tp, class _Alloc> 1693227825Stheravenvoid 1694227825Stheravenlist<_Tp, _Alloc>::pop_back() 1695227825Stheraven{ 1696253146Stheraven _LIBCPP_ASSERT(!empty(), "list::pop_back() called with empty list"); 1697227825Stheraven __node_allocator& __na = base::__node_alloc(); 1698300770Sdim __link_pointer __n = base::__end_.__prev_; 1699227825Stheraven base::__unlink_nodes(__n, __n); 1700227825Stheraven --base::__sz(); 1701227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1702227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 1703227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1704227825Stheraven { 1705227825Stheraven --__p; 1706227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1707253146Stheraven if (__i->__ptr_ == __n) 1708227825Stheraven { 1709227825Stheraven (*__p)->__c_ = nullptr; 1710227825Stheraven if (--__c->end_ != __p) 1711227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1712227825Stheraven } 1713227825Stheraven } 1714227825Stheraven __get_db()->unlock(); 1715227825Stheraven#endif 1716300770Sdim __node_pointer __np = __n->__as_node(); 1717300770Sdim __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1718300770Sdim __node_alloc_traits::deallocate(__na, __np, 1); 1719227825Stheraven} 1720227825Stheraven 1721227825Stheraventemplate <class _Tp, class _Alloc> 1722227825Stheraventypename list<_Tp, _Alloc>::iterator 1723227825Stheravenlist<_Tp, _Alloc>::erase(const_iterator __p) 1724227825Stheraven{ 1725227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1726227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1727227825Stheraven "list::erase(iterator) called with an iterator not" 1728227825Stheraven " referring to this list"); 1729227825Stheraven#endif 1730249989Sdim _LIBCPP_ASSERT(__p != end(), 1731249989Sdim "list::erase(iterator) called with a non-dereferenceable iterator"); 1732227825Stheraven __node_allocator& __na = base::__node_alloc(); 1733300770Sdim __link_pointer __n = __p.__ptr_; 1734300770Sdim __link_pointer __r = __n->__next_; 1735227825Stheraven base::__unlink_nodes(__n, __n); 1736227825Stheraven --base::__sz(); 1737227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1738227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 1739227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1740227825Stheraven { 1741227825Stheraven --__p; 1742227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1743253146Stheraven if (__i->__ptr_ == __n) 1744227825Stheraven { 1745227825Stheraven (*__p)->__c_ = nullptr; 1746227825Stheraven if (--__c->end_ != __p) 1747227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1748227825Stheraven } 1749227825Stheraven } 1750227825Stheraven __get_db()->unlock(); 1751227825Stheraven#endif 1752300770Sdim __node_pointer __np = __n->__as_node(); 1753300770Sdim __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1754300770Sdim __node_alloc_traits::deallocate(__na, __np, 1); 1755227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1756227825Stheraven return iterator(__r, this); 1757227825Stheraven#else 1758227825Stheraven return iterator(__r); 1759227825Stheraven#endif 1760227825Stheraven} 1761227825Stheraven 1762227825Stheraventemplate <class _Tp, class _Alloc> 1763227825Stheraventypename list<_Tp, _Alloc>::iterator 1764227825Stheravenlist<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l) 1765227825Stheraven{ 1766227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1767227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == this, 1768227825Stheraven "list::erase(iterator, iterator) called with an iterator not" 1769227825Stheraven " referring to this list"); 1770227825Stheraven#endif 1771227825Stheraven if (__f != __l) 1772227825Stheraven { 1773227825Stheraven __node_allocator& __na = base::__node_alloc(); 1774253146Stheraven base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_); 1775227825Stheraven while (__f != __l) 1776227825Stheraven { 1777300770Sdim __link_pointer __n = __f.__ptr_; 1778227825Stheraven ++__f; 1779227825Stheraven --base::__sz(); 1780227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1781227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 1782227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1783227825Stheraven { 1784227825Stheraven --__p; 1785227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1786253146Stheraven if (__i->__ptr_ == __n) 1787227825Stheraven { 1788227825Stheraven (*__p)->__c_ = nullptr; 1789227825Stheraven if (--__c->end_ != __p) 1790227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1791227825Stheraven } 1792227825Stheraven } 1793227825Stheraven __get_db()->unlock(); 1794227825Stheraven#endif 1795300770Sdim __node_pointer __np = __n->__as_node(); 1796300770Sdim __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1797300770Sdim __node_alloc_traits::deallocate(__na, __np, 1); 1798227825Stheraven } 1799227825Stheraven } 1800227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1801253146Stheraven return iterator(__l.__ptr_, this); 1802227825Stheraven#else 1803253146Stheraven return iterator(__l.__ptr_); 1804227825Stheraven#endif 1805227825Stheraven} 1806227825Stheraven 1807227825Stheraventemplate <class _Tp, class _Alloc> 1808227825Stheravenvoid 1809227825Stheravenlist<_Tp, _Alloc>::resize(size_type __n) 1810227825Stheraven{ 1811227825Stheraven if (__n < base::__sz()) 1812227825Stheraven erase(__iterator(__n), end()); 1813227825Stheraven else if (__n > base::__sz()) 1814227825Stheraven { 1815227825Stheraven __n -= base::__sz(); 1816227825Stheraven size_type __ds = 0; 1817227825Stheraven __node_allocator& __na = base::__node_alloc(); 1818232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1819232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1820227825Stheraven __hold->__prev_ = 0; 1821227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_)); 1822227825Stheraven ++__ds; 1823227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1824300770Sdim iterator __r = iterator(__hold.release()->__as_link(), this); 1825227825Stheraven#else 1826300770Sdim iterator __r = iterator(__hold.release()->__as_link()); 1827227825Stheraven#endif 1828227825Stheraven iterator __e = __r; 1829227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1830227825Stheraven try 1831227825Stheraven { 1832227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1833227825Stheraven for (--__n; __n != 0; --__n, ++__e, ++__ds) 1834227825Stheraven { 1835227825Stheraven __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1836227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_)); 1837300770Sdim __e.__ptr_->__next_ = __hold.get()->__as_link(); 1838227825Stheraven __hold->__prev_ = __e.__ptr_; 1839227825Stheraven __hold.release(); 1840227825Stheraven } 1841227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1842227825Stheraven } 1843227825Stheraven catch (...) 1844227825Stheraven { 1845227825Stheraven while (true) 1846227825Stheraven { 1847227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1848300770Sdim __link_pointer __prev = __e.__ptr_->__prev_; 1849300770Sdim __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1); 1850227825Stheraven if (__prev == 0) 1851227825Stheraven break; 1852227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1853227825Stheraven __e = iterator(__prev, this); 1854227825Stheraven#else 1855227825Stheraven __e = iterator(__prev); 1856227825Stheraven#endif 1857227825Stheraven } 1858227825Stheraven throw; 1859227825Stheraven } 1860227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1861276792Sdim __link_nodes_at_back(__r.__ptr_, __e.__ptr_); 1862227825Stheraven base::__sz() += __ds; 1863227825Stheraven } 1864227825Stheraven} 1865227825Stheraven 1866227825Stheraventemplate <class _Tp, class _Alloc> 1867227825Stheravenvoid 1868227825Stheravenlist<_Tp, _Alloc>::resize(size_type __n, const value_type& __x) 1869227825Stheraven{ 1870227825Stheraven if (__n < base::__sz()) 1871227825Stheraven erase(__iterator(__n), end()); 1872227825Stheraven else if (__n > base::__sz()) 1873227825Stheraven { 1874227825Stheraven __n -= base::__sz(); 1875227825Stheraven size_type __ds = 0; 1876227825Stheraven __node_allocator& __na = base::__node_alloc(); 1877232924Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1878232924Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1879227825Stheraven __hold->__prev_ = 0; 1880227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1881227825Stheraven ++__ds; 1882300770Sdim __link_pointer __nl = __hold.release()->__as_link(); 1883227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1884300770Sdim iterator __r = iterator(__nl, this); 1885227825Stheraven#else 1886300770Sdim iterator __r = iterator(__nl); 1887227825Stheraven#endif 1888227825Stheraven iterator __e = __r; 1889227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1890227825Stheraven try 1891227825Stheraven { 1892227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1893227825Stheraven for (--__n; __n != 0; --__n, ++__e, ++__ds) 1894227825Stheraven { 1895227825Stheraven __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1896227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1897300770Sdim __e.__ptr_->__next_ = __hold.get()->__as_link(); 1898227825Stheraven __hold->__prev_ = __e.__ptr_; 1899227825Stheraven __hold.release(); 1900227825Stheraven } 1901227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1902227825Stheraven } 1903227825Stheraven catch (...) 1904227825Stheraven { 1905227825Stheraven while (true) 1906227825Stheraven { 1907227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1908300770Sdim __link_pointer __prev = __e.__ptr_->__prev_; 1909300770Sdim __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1); 1910227825Stheraven if (__prev == 0) 1911227825Stheraven break; 1912227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1913227825Stheraven __e = iterator(__prev, this); 1914227825Stheraven#else 1915227825Stheraven __e = iterator(__prev); 1916227825Stheraven#endif 1917227825Stheraven } 1918227825Stheraven throw; 1919227825Stheraven } 1920227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1921300770Sdim __link_nodes(base::__end_as_link(), __r.__ptr_, __e.__ptr_); 1922227825Stheraven base::__sz() += __ds; 1923227825Stheraven } 1924227825Stheraven} 1925227825Stheraven 1926227825Stheraventemplate <class _Tp, class _Alloc> 1927227825Stheravenvoid 1928227825Stheravenlist<_Tp, _Alloc>::splice(const_iterator __p, list& __c) 1929227825Stheraven{ 1930227825Stheraven _LIBCPP_ASSERT(this != &__c, 1931227825Stheraven "list::splice(iterator, list) called with this == &list"); 1932227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1933227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1934227825Stheraven "list::splice(iterator, list) called with an iterator not" 1935227825Stheraven " referring to this list"); 1936227825Stheraven#endif 1937227825Stheraven if (!__c.empty()) 1938227825Stheraven { 1939300770Sdim __link_pointer __f = __c.__end_.__next_; 1940300770Sdim __link_pointer __l = __c.__end_.__prev_; 1941227825Stheraven base::__unlink_nodes(__f, __l); 1942253146Stheraven __link_nodes(__p.__ptr_, __f, __l); 1943227825Stheraven base::__sz() += __c.__sz(); 1944227825Stheraven __c.__sz() = 0; 1945227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1946227825Stheraven __libcpp_db* __db = __get_db(); 1947227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 1948227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 1949227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 1950227825Stheraven { 1951227825Stheraven --__p; 1952227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1953300770Sdim if (__i->__ptr_ != __c.__end_as_link()) 1954227825Stheraven { 1955227825Stheraven __cn1->__add(*__p); 1956227825Stheraven (*__p)->__c_ = __cn1; 1957227825Stheraven if (--__cn2->end_ != __p) 1958227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 1959227825Stheraven } 1960227825Stheraven } 1961227825Stheraven __db->unlock(); 1962227825Stheraven#endif 1963227825Stheraven } 1964227825Stheraven} 1965227825Stheraven 1966227825Stheraventemplate <class _Tp, class _Alloc> 1967227825Stheravenvoid 1968227825Stheravenlist<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i) 1969227825Stheraven{ 1970227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1971227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1972227825Stheraven "list::splice(iterator, list, iterator) called with first iterator not" 1973227825Stheraven " referring to this list"); 1974227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__i) == &__c, 1975227825Stheraven "list::splice(iterator, list, iterator) called with second iterator not" 1976227825Stheraven " referring to list argument"); 1977227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(&__i), 1978227825Stheraven "list::splice(iterator, list, iterator) called with second iterator not" 1979227825Stheraven " derefereceable"); 1980227825Stheraven#endif 1981227825Stheraven if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_) 1982227825Stheraven { 1983300770Sdim __link_pointer __f = __i.__ptr_; 1984227825Stheraven base::__unlink_nodes(__f, __f); 1985253146Stheraven __link_nodes(__p.__ptr_, __f, __f); 1986227825Stheraven --__c.__sz(); 1987227825Stheraven ++base::__sz(); 1988227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1989227825Stheraven __libcpp_db* __db = __get_db(); 1990227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 1991227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 1992227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 1993227825Stheraven { 1994227825Stheraven --__p; 1995227825Stheraven iterator* __j = static_cast<iterator*>((*__p)->__i_); 1996253146Stheraven if (__j->__ptr_ == __f) 1997227825Stheraven { 1998227825Stheraven __cn1->__add(*__p); 1999227825Stheraven (*__p)->__c_ = __cn1; 2000227825Stheraven if (--__cn2->end_ != __p) 2001227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 2002227825Stheraven } 2003227825Stheraven } 2004227825Stheraven __db->unlock(); 2005227825Stheraven#endif 2006227825Stheraven } 2007227825Stheraven} 2008227825Stheraven 2009227825Stheraventemplate <class _Tp, class _Alloc> 2010227825Stheravenvoid 2011227825Stheravenlist<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l) 2012227825Stheraven{ 2013227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 2014227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2015227825Stheraven "list::splice(iterator, list, iterator, iterator) called with first iterator not" 2016227825Stheraven " referring to this list"); 2017227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == &__c, 2018227825Stheraven "list::splice(iterator, list, iterator, iterator) called with second iterator not" 2019227825Stheraven " referring to list argument"); 2020227825Stheraven if (this == &__c) 2021227825Stheraven { 2022227825Stheraven for (const_iterator __i = __f; __i != __l; ++__i) 2023227825Stheraven _LIBCPP_ASSERT(__i != __p, 2024227825Stheraven "list::splice(iterator, list, iterator, iterator)" 2025227825Stheraven " called with the first iterator within the range" 2026227825Stheraven " of the second and third iterators"); 2027227825Stheraven } 2028227825Stheraven#endif 2029227825Stheraven if (__f != __l) 2030227825Stheraven { 2031227825Stheraven if (this != &__c) 2032227825Stheraven { 2033227825Stheraven size_type __s = _VSTD::distance(__f, __l); 2034227825Stheraven __c.__sz() -= __s; 2035227825Stheraven base::__sz() += __s; 2036227825Stheraven } 2037300770Sdim __link_pointer __first = __f.__ptr_; 2038227825Stheraven --__l; 2039300770Sdim __link_pointer __last = __l.__ptr_; 2040227825Stheraven base::__unlink_nodes(__first, __last); 2041253146Stheraven __link_nodes(__p.__ptr_, __first, __last); 2042227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 2043227825Stheraven __libcpp_db* __db = __get_db(); 2044227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 2045227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 2046227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 2047227825Stheraven { 2048227825Stheraven --__p; 2049227825Stheraven iterator* __j = static_cast<iterator*>((*__p)->__i_); 2050300770Sdim for (__link_pointer __k = __f.__ptr_; 2051227825Stheraven __k != __l.__ptr_; __k = __k->__next_) 2052227825Stheraven { 2053227825Stheraven if (__j->__ptr_ == __k) 2054227825Stheraven { 2055227825Stheraven __cn1->__add(*__p); 2056227825Stheraven (*__p)->__c_ = __cn1; 2057227825Stheraven if (--__cn2->end_ != __p) 2058227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 2059227825Stheraven } 2060227825Stheraven } 2061227825Stheraven } 2062227825Stheraven __db->unlock(); 2063227825Stheraven#endif 2064227825Stheraven } 2065227825Stheraven} 2066227825Stheraven 2067227825Stheraventemplate <class _Tp, class _Alloc> 2068227825Stheravenvoid 2069227825Stheravenlist<_Tp, _Alloc>::remove(const value_type& __x) 2070227825Stheraven{ 2071276792Sdim list<_Tp, _Alloc> __deleted_nodes; // collect the nodes we're removing 2072276792Sdim for (const_iterator __i = begin(), __e = end(); __i != __e;) 2073227825Stheraven { 2074227825Stheraven if (*__i == __x) 2075227825Stheraven { 2076276792Sdim const_iterator __j = _VSTD::next(__i); 2077227825Stheraven for (; __j != __e && *__j == __x; ++__j) 2078227825Stheraven ; 2079276792Sdim __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j); 2080276792Sdim __i = __j; 2081276792Sdim if (__i != __e) 2082276792Sdim ++__i; 2083227825Stheraven } 2084227825Stheraven else 2085227825Stheraven ++__i; 2086227825Stheraven } 2087227825Stheraven} 2088227825Stheraven 2089227825Stheraventemplate <class _Tp, class _Alloc> 2090227825Stheraventemplate <class _Pred> 2091227825Stheravenvoid 2092227825Stheravenlist<_Tp, _Alloc>::remove_if(_Pred __pred) 2093227825Stheraven{ 2094227825Stheraven for (iterator __i = begin(), __e = end(); __i != __e;) 2095227825Stheraven { 2096227825Stheraven if (__pred(*__i)) 2097227825Stheraven { 2098227825Stheraven iterator __j = _VSTD::next(__i); 2099227825Stheraven for (; __j != __e && __pred(*__j); ++__j) 2100227825Stheraven ; 2101227825Stheraven __i = erase(__i, __j); 2102276792Sdim if (__i != __e) 2103276792Sdim ++__i; 2104227825Stheraven } 2105227825Stheraven else 2106227825Stheraven ++__i; 2107227825Stheraven } 2108227825Stheraven} 2109227825Stheraven 2110227825Stheraventemplate <class _Tp, class _Alloc> 2111227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2112227825Stheravenvoid 2113227825Stheravenlist<_Tp, _Alloc>::unique() 2114227825Stheraven{ 2115227825Stheraven unique(__equal_to<value_type>()); 2116227825Stheraven} 2117227825Stheraven 2118227825Stheraventemplate <class _Tp, class _Alloc> 2119227825Stheraventemplate <class _BinaryPred> 2120227825Stheravenvoid 2121227825Stheravenlist<_Tp, _Alloc>::unique(_BinaryPred __binary_pred) 2122227825Stheraven{ 2123227825Stheraven for (iterator __i = begin(), __e = end(); __i != __e;) 2124227825Stheraven { 2125227825Stheraven iterator __j = _VSTD::next(__i); 2126227825Stheraven for (; __j != __e && __binary_pred(*__i, *__j); ++__j) 2127227825Stheraven ; 2128227825Stheraven if (++__i != __j) 2129227825Stheraven __i = erase(__i, __j); 2130227825Stheraven } 2131227825Stheraven} 2132227825Stheraven 2133227825Stheraventemplate <class _Tp, class _Alloc> 2134227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2135227825Stheravenvoid 2136227825Stheravenlist<_Tp, _Alloc>::merge(list& __c) 2137227825Stheraven{ 2138227825Stheraven merge(__c, __less<value_type>()); 2139227825Stheraven} 2140227825Stheraven 2141227825Stheraventemplate <class _Tp, class _Alloc> 2142227825Stheraventemplate <class _Comp> 2143227825Stheravenvoid 2144227825Stheravenlist<_Tp, _Alloc>::merge(list& __c, _Comp __comp) 2145227825Stheraven{ 2146227825Stheraven if (this != &__c) 2147227825Stheraven { 2148227825Stheraven iterator __f1 = begin(); 2149227825Stheraven iterator __e1 = end(); 2150227825Stheraven iterator __f2 = __c.begin(); 2151227825Stheraven iterator __e2 = __c.end(); 2152227825Stheraven while (__f1 != __e1 && __f2 != __e2) 2153227825Stheraven { 2154227825Stheraven if (__comp(*__f2, *__f1)) 2155227825Stheraven { 2156227825Stheraven size_type __ds = 1; 2157227825Stheraven iterator __m2 = _VSTD::next(__f2); 2158227825Stheraven for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, ++__ds) 2159227825Stheraven ; 2160227825Stheraven base::__sz() += __ds; 2161227825Stheraven __c.__sz() -= __ds; 2162300770Sdim __link_pointer __f = __f2.__ptr_; 2163300770Sdim __link_pointer __l = __m2.__ptr_->__prev_; 2164227825Stheraven __f2 = __m2; 2165227825Stheraven base::__unlink_nodes(__f, __l); 2166227825Stheraven __m2 = _VSTD::next(__f1); 2167253146Stheraven __link_nodes(__f1.__ptr_, __f, __l); 2168227825Stheraven __f1 = __m2; 2169227825Stheraven } 2170227825Stheraven else 2171227825Stheraven ++__f1; 2172227825Stheraven } 2173227825Stheraven splice(__e1, __c); 2174227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 2175227825Stheraven __libcpp_db* __db = __get_db(); 2176227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 2177227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 2178227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 2179227825Stheraven { 2180227825Stheraven --__p; 2181227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 2182300770Sdim if (__i->__ptr_ != __c.__end_as_link()) 2183227825Stheraven { 2184227825Stheraven __cn1->__add(*__p); 2185227825Stheraven (*__p)->__c_ = __cn1; 2186227825Stheraven if (--__cn2->end_ != __p) 2187227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 2188227825Stheraven } 2189227825Stheraven } 2190227825Stheraven __db->unlock(); 2191227825Stheraven#endif 2192227825Stheraven } 2193227825Stheraven} 2194227825Stheraven 2195227825Stheraventemplate <class _Tp, class _Alloc> 2196227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2197227825Stheravenvoid 2198227825Stheravenlist<_Tp, _Alloc>::sort() 2199227825Stheraven{ 2200227825Stheraven sort(__less<value_type>()); 2201227825Stheraven} 2202227825Stheraven 2203227825Stheraventemplate <class _Tp, class _Alloc> 2204227825Stheraventemplate <class _Comp> 2205227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2206227825Stheravenvoid 2207227825Stheravenlist<_Tp, _Alloc>::sort(_Comp __comp) 2208227825Stheraven{ 2209227825Stheraven __sort(begin(), end(), base::__sz(), __comp); 2210227825Stheraven} 2211227825Stheraven 2212227825Stheraventemplate <class _Tp, class _Alloc> 2213227825Stheraventemplate <class _Comp> 2214227825Stheraventypename list<_Tp, _Alloc>::iterator 2215227825Stheravenlist<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp) 2216227825Stheraven{ 2217227825Stheraven switch (__n) 2218227825Stheraven { 2219227825Stheraven case 0: 2220227825Stheraven case 1: 2221227825Stheraven return __f1; 2222227825Stheraven case 2: 2223227825Stheraven if (__comp(*--__e2, *__f1)) 2224227825Stheraven { 2225300770Sdim __link_pointer __f = __e2.__ptr_; 2226227825Stheraven base::__unlink_nodes(__f, __f); 2227253146Stheraven __link_nodes(__f1.__ptr_, __f, __f); 2228227825Stheraven return __e2; 2229227825Stheraven } 2230227825Stheraven return __f1; 2231227825Stheraven } 2232227825Stheraven size_type __n2 = __n / 2; 2233227825Stheraven iterator __e1 = _VSTD::next(__f1, __n2); 2234227825Stheraven iterator __r = __f1 = __sort(__f1, __e1, __n2, __comp); 2235227825Stheraven iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp); 2236227825Stheraven if (__comp(*__f2, *__f1)) 2237227825Stheraven { 2238227825Stheraven iterator __m2 = _VSTD::next(__f2); 2239227825Stheraven for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2) 2240227825Stheraven ; 2241300770Sdim __link_pointer __f = __f2.__ptr_; 2242300770Sdim __link_pointer __l = __m2.__ptr_->__prev_; 2243227825Stheraven __r = __f2; 2244227825Stheraven __e1 = __f2 = __m2; 2245227825Stheraven base::__unlink_nodes(__f, __l); 2246227825Stheraven __m2 = _VSTD::next(__f1); 2247253146Stheraven __link_nodes(__f1.__ptr_, __f, __l); 2248227825Stheraven __f1 = __m2; 2249227825Stheraven } 2250227825Stheraven else 2251227825Stheraven ++__f1; 2252227825Stheraven while (__f1 != __e1 && __f2 != __e2) 2253227825Stheraven { 2254227825Stheraven if (__comp(*__f2, *__f1)) 2255227825Stheraven { 2256227825Stheraven iterator __m2 = _VSTD::next(__f2); 2257227825Stheraven for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2) 2258227825Stheraven ; 2259300770Sdim __link_pointer __f = __f2.__ptr_; 2260300770Sdim __link_pointer __l = __m2.__ptr_->__prev_; 2261227825Stheraven if (__e1 == __f2) 2262227825Stheraven __e1 = __m2; 2263227825Stheraven __f2 = __m2; 2264227825Stheraven base::__unlink_nodes(__f, __l); 2265227825Stheraven __m2 = _VSTD::next(__f1); 2266253146Stheraven __link_nodes(__f1.__ptr_, __f, __l); 2267227825Stheraven __f1 = __m2; 2268227825Stheraven } 2269227825Stheraven else 2270227825Stheraven ++__f1; 2271227825Stheraven } 2272227825Stheraven return __r; 2273227825Stheraven} 2274227825Stheraven 2275227825Stheraventemplate <class _Tp, class _Alloc> 2276227825Stheravenvoid 2277227825Stheravenlist<_Tp, _Alloc>::reverse() _NOEXCEPT 2278227825Stheraven{ 2279227825Stheraven if (base::__sz() > 1) 2280227825Stheraven { 2281227825Stheraven iterator __e = end(); 2282227825Stheraven for (iterator __i = begin(); __i.__ptr_ != __e.__ptr_;) 2283227825Stheraven { 2284227825Stheraven _VSTD::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_); 2285227825Stheraven __i.__ptr_ = __i.__ptr_->__prev_; 2286227825Stheraven } 2287227825Stheraven _VSTD::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_); 2288227825Stheraven } 2289227825Stheraven} 2290227825Stheraven 2291227825Stheraventemplate <class _Tp, class _Alloc> 2292227825Stheravenbool 2293227825Stheravenlist<_Tp, _Alloc>::__invariants() const 2294227825Stheraven{ 2295227825Stheraven return size() == _VSTD::distance(begin(), end()); 2296227825Stheraven} 2297227825Stheraven 2298227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 2299227825Stheraven 2300227825Stheraventemplate <class _Tp, class _Alloc> 2301227825Stheravenbool 2302227825Stheravenlist<_Tp, _Alloc>::__dereferenceable(const const_iterator* __i) const 2303227825Stheraven{ 2304300770Sdim return __i->__ptr_ != this->__end_as_link(); 2305227825Stheraven} 2306227825Stheraven 2307227825Stheraventemplate <class _Tp, class _Alloc> 2308227825Stheravenbool 2309227825Stheravenlist<_Tp, _Alloc>::__decrementable(const const_iterator* __i) const 2310227825Stheraven{ 2311227825Stheraven return !empty() && __i->__ptr_ != base::__end_.__next_; 2312227825Stheraven} 2313227825Stheraven 2314227825Stheraventemplate <class _Tp, class _Alloc> 2315227825Stheravenbool 2316227825Stheravenlist<_Tp, _Alloc>::__addable(const const_iterator* __i, ptrdiff_t __n) const 2317227825Stheraven{ 2318227825Stheraven return false; 2319227825Stheraven} 2320227825Stheraven 2321227825Stheraventemplate <class _Tp, class _Alloc> 2322227825Stheravenbool 2323227825Stheravenlist<_Tp, _Alloc>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const 2324227825Stheraven{ 2325227825Stheraven return false; 2326227825Stheraven} 2327227825Stheraven 2328227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 2329227825Stheraven 2330227825Stheraventemplate <class _Tp, class _Alloc> 2331227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2332227825Stheravenbool 2333227825Stheravenoperator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2334227825Stheraven{ 2335227825Stheraven return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 2336227825Stheraven} 2337227825Stheraven 2338227825Stheraventemplate <class _Tp, class _Alloc> 2339227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2340227825Stheravenbool 2341227825Stheravenoperator< (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2342227825Stheraven{ 2343227825Stheraven return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2344227825Stheraven} 2345227825Stheraven 2346227825Stheraventemplate <class _Tp, class _Alloc> 2347227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2348227825Stheravenbool 2349227825Stheravenoperator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2350227825Stheraven{ 2351227825Stheraven return !(__x == __y); 2352227825Stheraven} 2353227825Stheraven 2354227825Stheraventemplate <class _Tp, class _Alloc> 2355227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2356227825Stheravenbool 2357227825Stheravenoperator> (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2358227825Stheraven{ 2359227825Stheraven return __y < __x; 2360227825Stheraven} 2361227825Stheraven 2362227825Stheraventemplate <class _Tp, class _Alloc> 2363227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2364227825Stheravenbool 2365227825Stheravenoperator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2366227825Stheraven{ 2367227825Stheraven return !(__x < __y); 2368227825Stheraven} 2369227825Stheraven 2370227825Stheraventemplate <class _Tp, class _Alloc> 2371227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2372227825Stheravenbool 2373227825Stheravenoperator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2374227825Stheraven{ 2375227825Stheraven return !(__y < __x); 2376227825Stheraven} 2377227825Stheraven 2378227825Stheraventemplate <class _Tp, class _Alloc> 2379227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2380227825Stheravenvoid 2381227825Stheravenswap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) 2382227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2383227825Stheraven{ 2384227825Stheraven __x.swap(__y); 2385227825Stheraven} 2386227825Stheraven 2387227825Stheraven_LIBCPP_END_NAMESPACE_STD 2388227825Stheraven 2389227825Stheraven#endif // _LIBCPP_LIST 2390