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); 43262801Sdim 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&) 121227825Stheraven noexcept(!allocator_type::propagate_on_container_swap::value || 122227825Stheraven __is_nothrow_swappable<allocator_type>::value); 123227825Stheraven void clear() noexcept; 124227825Stheraven 125227825Stheraven void splice(const_iterator position, list& x); 126227825Stheraven void splice(const_iterator position, list&& x); 127227825Stheraven void splice(const_iterator position, list& x, const_iterator i); 128227825Stheraven void splice(const_iterator position, list&& x, const_iterator i); 129227825Stheraven void splice(const_iterator position, list& x, const_iterator first, 130227825Stheraven const_iterator last); 131227825Stheraven void splice(const_iterator position, list&& x, const_iterator first, 132227825Stheraven const_iterator last); 133227825Stheraven 134227825Stheraven void remove(const value_type& value); 135227825Stheraven template <class Pred> void remove_if(Pred pred); 136227825Stheraven void unique(); 137227825Stheraven template <class BinaryPredicate> 138227825Stheraven void unique(BinaryPredicate binary_pred); 139227825Stheraven void merge(list& x); 140227825Stheraven void merge(list&& x); 141227825Stheraven template <class Compare> 142227825Stheraven void merge(list& x, Compare comp); 143227825Stheraven template <class Compare> 144227825Stheraven void merge(list&& x, Compare comp); 145227825Stheraven void sort(); 146227825Stheraven template <class Compare> 147227825Stheraven void sort(Compare comp); 148227825Stheraven void reverse() noexcept; 149227825Stheraven}; 150227825Stheraven 151227825Stheraventemplate <class T, class Alloc> 152227825Stheraven bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y); 153227825Stheraventemplate <class T, class Alloc> 154227825Stheraven bool operator< (const list<T,Alloc>& x, const list<T,Alloc>& y); 155227825Stheraventemplate <class T, class Alloc> 156227825Stheraven bool operator!=(const list<T,Alloc>& x, const list<T,Alloc>& y); 157227825Stheraventemplate <class T, class Alloc> 158227825Stheraven bool operator> (const list<T,Alloc>& x, const list<T,Alloc>& y); 159227825Stheraventemplate <class T, class Alloc> 160227825Stheraven bool operator>=(const list<T,Alloc>& x, const list<T,Alloc>& y); 161227825Stheraventemplate <class T, class Alloc> 162227825Stheraven bool operator<=(const list<T,Alloc>& x, const list<T,Alloc>& y); 163227825Stheraven 164227825Stheraventemplate <class T, class Alloc> 165227825Stheraven void swap(list<T,Alloc>& x, list<T,Alloc>& y) 166227825Stheraven noexcept(noexcept(x.swap(y))); 167227825Stheraven 168227825Stheraven} // std 169227825Stheraven 170227825Stheraven*/ 171227825Stheraven 172227825Stheraven#include <__config> 173227825Stheraven 174227825Stheraven#include <memory> 175227825Stheraven#include <limits> 176227825Stheraven#include <initializer_list> 177227825Stheraven#include <iterator> 178227825Stheraven#include <algorithm> 179227825Stheraven 180232950Stheraven#include <__undef_min_max> 181232950Stheraven 182278724Sdim#include <__debug> 183262801Sdim 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; 191227825Stheraven 192227825Stheraventemplate <class _Tp, class _VoidPtr> 193227825Stheravenstruct __list_node_base 194227825Stheraven{ 195227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 196227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 197227825Stheraven rebind<__list_node<_Tp, _VoidPtr> > pointer; 198227825Stheraven#else 199227825Stheraven rebind<__list_node<_Tp, _VoidPtr> >::other pointer; 200227825Stheraven#endif 201227825Stheraven 202253159Stheraven typedef typename pointer_traits<_VoidPtr>::template 203253159Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 204253159Stheraven rebind<__list_node_base> __base_pointer; 205253159Stheraven#else 206253159Stheraven rebind<__list_node_base>::other __base_pointer; 207253159Stheraven#endif 208253159Stheraven 209227825Stheraven pointer __prev_; 210227825Stheraven pointer __next_; 211227825Stheraven 212227825Stheraven _LIBCPP_INLINE_VISIBILITY 213278724Sdim __list_node_base() : __prev_(__self()), __next_(__self()) {} 214278724Sdim 215278724Sdim _LIBCPP_INLINE_VISIBILITY 216278724Sdim pointer __self() 217278724Sdim { 218278724Sdim return static_cast<pointer>(pointer_traits<__base_pointer>::pointer_to(*this)); 219278724Sdim } 220227825Stheraven}; 221227825Stheraven 222227825Stheraventemplate <class _Tp, class _VoidPtr> 223227825Stheravenstruct __list_node 224227825Stheraven : public __list_node_base<_Tp, _VoidPtr> 225227825Stheraven{ 226227825Stheraven _Tp __value_; 227227825Stheraven}; 228227825Stheraven 229262801Sdimtemplate <class _Tp, class _Alloc> class _LIBCPP_TYPE_VIS_ONLY list; 230227825Stheraventemplate <class _Tp, class _Alloc> class __list_imp; 231262801Sdimtemplate <class _Tp, class _VoidPtr> class _LIBCPP_TYPE_VIS_ONLY __list_const_iterator; 232227825Stheraven 233227825Stheraventemplate <class _Tp, class _VoidPtr> 234262801Sdimclass _LIBCPP_TYPE_VIS_ONLY __list_iterator 235227825Stheraven{ 236227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 237227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 238227825Stheraven rebind<__list_node<_Tp, _VoidPtr> > __node_pointer; 239227825Stheraven#else 240227825Stheraven rebind<__list_node<_Tp, _VoidPtr> >::other __node_pointer; 241227825Stheraven#endif 242227825Stheraven 243227825Stheraven __node_pointer __ptr_; 244227825Stheraven 245227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 246227825Stheraven _LIBCPP_INLINE_VISIBILITY 247227825Stheraven explicit __list_iterator(__node_pointer __p, const void* __c) _NOEXCEPT 248227825Stheraven : __ptr_(__p) 249227825Stheraven { 250227825Stheraven __get_db()->__insert_ic(this, __c); 251227825Stheraven } 252227825Stheraven#else 253227825Stheraven _LIBCPP_INLINE_VISIBILITY 254227825Stheraven explicit __list_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 255227825Stheraven#endif 256227825Stheraven 257227825Stheraven 258227825Stheraven 259227825Stheraven template<class, class> friend class list; 260227825Stheraven template<class, class> friend class __list_imp; 261227825Stheraven template<class, class> friend class __list_const_iterator; 262227825Stheravenpublic: 263227825Stheraven typedef bidirectional_iterator_tag iterator_category; 264227825Stheraven typedef _Tp value_type; 265227825Stheraven typedef value_type& reference; 266227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 267227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 268227825Stheraven rebind<value_type> 269227825Stheraven#else 270227825Stheraven rebind<value_type>::other 271227825Stheraven#endif 272227825Stheraven pointer; 273227825Stheraven typedef typename pointer_traits<pointer>::difference_type difference_type; 274227825Stheraven 275227825Stheraven _LIBCPP_INLINE_VISIBILITY 276262801Sdim __list_iterator() _NOEXCEPT : __ptr_(nullptr) 277227825Stheraven { 278227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 279227825Stheraven __get_db()->__insert_i(this); 280227825Stheraven#endif 281227825Stheraven } 282227825Stheraven 283227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 284227825Stheraven 285227825Stheraven _LIBCPP_INLINE_VISIBILITY 286227825Stheraven __list_iterator(const __list_iterator& __p) 287227825Stheraven : __ptr_(__p.__ptr_) 288227825Stheraven { 289227825Stheraven __get_db()->__iterator_copy(this, &__p); 290227825Stheraven } 291227825Stheraven 292227825Stheraven _LIBCPP_INLINE_VISIBILITY 293227825Stheraven ~__list_iterator() 294227825Stheraven { 295227825Stheraven __get_db()->__erase_i(this); 296227825Stheraven } 297227825Stheraven 298227825Stheraven _LIBCPP_INLINE_VISIBILITY 299227825Stheraven __list_iterator& operator=(const __list_iterator& __p) 300227825Stheraven { 301227825Stheraven if (this != &__p) 302227825Stheraven { 303227825Stheraven __get_db()->__iterator_copy(this, &__p); 304227825Stheraven __ptr_ = __p.__ptr_; 305227825Stheraven } 306227825Stheraven return *this; 307227825Stheraven } 308227825Stheraven 309227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 310227825Stheraven 311227825Stheraven _LIBCPP_INLINE_VISIBILITY 312227825Stheraven reference operator*() const 313227825Stheraven { 314227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 315227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 316227825Stheraven "Attempted to dereference a non-dereferenceable list::iterator"); 317227825Stheraven#endif 318227825Stheraven return __ptr_->__value_; 319227825Stheraven } 320227825Stheraven _LIBCPP_INLINE_VISIBILITY 321253159Stheraven pointer operator->() const 322253159Stheraven { 323253159Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 324253159Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 325253159Stheraven "Attempted to dereference a non-dereferenceable list::iterator"); 326253159Stheraven#endif 327253159Stheraven return pointer_traits<pointer>::pointer_to(__ptr_->__value_); 328253159Stheraven } 329227825Stheraven 330227825Stheraven _LIBCPP_INLINE_VISIBILITY 331227825Stheraven __list_iterator& operator++() 332227825Stheraven { 333227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 334227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 335227825Stheraven "Attempted to increment non-incrementable list::iterator"); 336227825Stheraven#endif 337227825Stheraven __ptr_ = __ptr_->__next_; 338227825Stheraven return *this; 339227825Stheraven } 340227825Stheraven _LIBCPP_INLINE_VISIBILITY 341227825Stheraven __list_iterator operator++(int) {__list_iterator __t(*this); ++(*this); return __t;} 342227825Stheraven 343227825Stheraven _LIBCPP_INLINE_VISIBILITY 344227825Stheraven __list_iterator& operator--() 345227825Stheraven { 346227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 347227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__decrementable(this), 348227825Stheraven "Attempted to decrement non-decrementable list::iterator"); 349227825Stheraven#endif 350227825Stheraven __ptr_ = __ptr_->__prev_; 351227825Stheraven return *this; 352227825Stheraven } 353227825Stheraven _LIBCPP_INLINE_VISIBILITY 354227825Stheraven __list_iterator operator--(int) {__list_iterator __t(*this); --(*this); return __t;} 355227825Stheraven 356227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 357227825Stheraven bool operator==(const __list_iterator& __x, const __list_iterator& __y) 358227825Stheraven { 359227825Stheraven return __x.__ptr_ == __y.__ptr_; 360227825Stheraven } 361227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 362227825Stheraven bool operator!=(const __list_iterator& __x, const __list_iterator& __y) 363227825Stheraven {return !(__x == __y);} 364227825Stheraven}; 365227825Stheraven 366227825Stheraventemplate <class _Tp, class _VoidPtr> 367262801Sdimclass _LIBCPP_TYPE_VIS_ONLY __list_const_iterator 368227825Stheraven{ 369227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 370227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 371253159Stheraven rebind<__list_node<_Tp, _VoidPtr> > __node_pointer; 372227825Stheraven#else 373253159Stheraven rebind<__list_node<_Tp, _VoidPtr> >::other __node_pointer; 374227825Stheraven#endif 375227825Stheraven 376227825Stheraven __node_pointer __ptr_; 377227825Stheraven 378227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 379227825Stheraven _LIBCPP_INLINE_VISIBILITY 380227825Stheraven explicit __list_const_iterator(__node_pointer __p, const void* __c) _NOEXCEPT 381227825Stheraven : __ptr_(__p) 382227825Stheraven { 383227825Stheraven __get_db()->__insert_ic(this, __c); 384227825Stheraven } 385227825Stheraven#else 386227825Stheraven _LIBCPP_INLINE_VISIBILITY 387227825Stheraven explicit __list_const_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} 388227825Stheraven#endif 389227825Stheraven 390227825Stheraven template<class, class> friend class list; 391227825Stheraven template<class, class> friend class __list_imp; 392227825Stheravenpublic: 393227825Stheraven typedef bidirectional_iterator_tag iterator_category; 394227825Stheraven typedef _Tp value_type; 395227825Stheraven typedef const value_type& reference; 396227825Stheraven typedef typename pointer_traits<_VoidPtr>::template 397227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 398227825Stheraven rebind<const value_type> 399227825Stheraven#else 400227825Stheraven rebind<const value_type>::other 401227825Stheraven#endif 402227825Stheraven pointer; 403227825Stheraven typedef typename pointer_traits<pointer>::difference_type difference_type; 404227825Stheraven 405227825Stheraven _LIBCPP_INLINE_VISIBILITY 406262801Sdim __list_const_iterator() _NOEXCEPT : __ptr_(nullptr) 407227825Stheraven { 408227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 409227825Stheraven __get_db()->__insert_i(this); 410227825Stheraven#endif 411227825Stheraven } 412227825Stheraven _LIBCPP_INLINE_VISIBILITY 413249998Sdim __list_const_iterator(const __list_iterator<_Tp, _VoidPtr>& __p) _NOEXCEPT 414227825Stheraven : __ptr_(__p.__ptr_) 415227825Stheraven { 416227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 417227825Stheraven __get_db()->__iterator_copy(this, &__p); 418227825Stheraven#endif 419227825Stheraven } 420227825Stheraven 421227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 422227825Stheraven 423227825Stheraven _LIBCPP_INLINE_VISIBILITY 424227825Stheraven __list_const_iterator(const __list_const_iterator& __p) 425227825Stheraven : __ptr_(__p.__ptr_) 426227825Stheraven { 427227825Stheraven __get_db()->__iterator_copy(this, &__p); 428227825Stheraven } 429227825Stheraven 430227825Stheraven _LIBCPP_INLINE_VISIBILITY 431227825Stheraven ~__list_const_iterator() 432227825Stheraven { 433227825Stheraven __get_db()->__erase_i(this); 434227825Stheraven } 435227825Stheraven 436227825Stheraven _LIBCPP_INLINE_VISIBILITY 437227825Stheraven __list_const_iterator& operator=(const __list_const_iterator& __p) 438227825Stheraven { 439227825Stheraven if (this != &__p) 440227825Stheraven { 441227825Stheraven __get_db()->__iterator_copy(this, &__p); 442227825Stheraven __ptr_ = __p.__ptr_; 443227825Stheraven } 444227825Stheraven return *this; 445227825Stheraven } 446227825Stheraven 447227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 448227825Stheraven _LIBCPP_INLINE_VISIBILITY 449227825Stheraven reference operator*() const 450227825Stheraven { 451227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 452227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 453227825Stheraven "Attempted to dereference a non-dereferenceable list::const_iterator"); 454227825Stheraven#endif 455227825Stheraven return __ptr_->__value_; 456227825Stheraven } 457227825Stheraven _LIBCPP_INLINE_VISIBILITY 458253159Stheraven pointer operator->() const 459253159Stheraven { 460253159Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 461253159Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 462253159Stheraven "Attempted to dereference a non-dereferenceable list::iterator"); 463253159Stheraven#endif 464253159Stheraven return pointer_traits<pointer>::pointer_to(__ptr_->__value_); 465253159Stheraven } 466227825Stheraven 467227825Stheraven _LIBCPP_INLINE_VISIBILITY 468227825Stheraven __list_const_iterator& operator++() 469227825Stheraven { 470227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 471227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 472227825Stheraven "Attempted to increment non-incrementable list::const_iterator"); 473227825Stheraven#endif 474227825Stheraven __ptr_ = __ptr_->__next_; 475227825Stheraven return *this; 476227825Stheraven } 477227825Stheraven _LIBCPP_INLINE_VISIBILITY 478227825Stheraven __list_const_iterator operator++(int) {__list_const_iterator __t(*this); ++(*this); return __t;} 479227825Stheraven 480227825Stheraven _LIBCPP_INLINE_VISIBILITY 481227825Stheraven __list_const_iterator& operator--() 482227825Stheraven { 483227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 484227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__decrementable(this), 485227825Stheraven "Attempted to decrement non-decrementable list::const_iterator"); 486227825Stheraven#endif 487227825Stheraven __ptr_ = __ptr_->__prev_; 488227825Stheraven return *this; 489227825Stheraven } 490227825Stheraven _LIBCPP_INLINE_VISIBILITY 491227825Stheraven __list_const_iterator operator--(int) {__list_const_iterator __t(*this); --(*this); return __t;} 492227825Stheraven 493227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 494227825Stheraven bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y) 495227825Stheraven { 496227825Stheraven return __x.__ptr_ == __y.__ptr_; 497227825Stheraven } 498227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 499227825Stheraven bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y) 500227825Stheraven {return !(__x == __y);} 501227825Stheraven}; 502227825Stheraven 503227825Stheraventemplate <class _Tp, class _Alloc> 504227825Stheravenclass __list_imp 505227825Stheraven{ 506227825Stheraven __list_imp(const __list_imp&); 507227825Stheraven __list_imp& operator=(const __list_imp&); 508227825Stheravenprotected: 509227825Stheraven typedef _Tp value_type; 510227825Stheraven typedef _Alloc allocator_type; 511227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 512227825Stheraven typedef typename __alloc_traits::size_type size_type; 513227825Stheraven typedef typename __alloc_traits::void_pointer __void_pointer; 514227825Stheraven typedef __list_iterator<value_type, __void_pointer> iterator; 515227825Stheraven typedef __list_const_iterator<value_type, __void_pointer> const_iterator; 516227825Stheraven typedef __list_node_base<value_type, __void_pointer> __node_base; 517227825Stheraven typedef __list_node<value_type, __void_pointer> __node; 518227825Stheraven typedef typename __alloc_traits::template 519227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 520227825Stheraven rebind_alloc<__node> 521227825Stheraven#else 522227825Stheraven rebind_alloc<__node>::other 523227825Stheraven#endif 524227825Stheraven __node_allocator; 525227825Stheraven typedef allocator_traits<__node_allocator> __node_alloc_traits; 526227825Stheraven typedef typename __node_alloc_traits::pointer __node_pointer; 527253159Stheraven typedef typename __node_alloc_traits::pointer __node_const_pointer; 528227825Stheraven typedef typename __alloc_traits::pointer pointer; 529227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 530227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 531227825Stheraven 532253159Stheraven typedef typename __alloc_traits::template 533253159Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 534253159Stheraven rebind_alloc<__node_base> 535253159Stheraven#else 536253159Stheraven rebind_alloc<__node_base>::other 537253159Stheraven#endif 538253159Stheraven __node_base_allocator; 539253159Stheraven typedef typename allocator_traits<__node_base_allocator>::pointer __node_base_pointer; 540253159Stheraven 541227825Stheraven __node_base __end_; 542227825Stheraven __compressed_pair<size_type, __node_allocator> __size_alloc_; 543227825Stheraven 544227825Stheraven _LIBCPP_INLINE_VISIBILITY 545227825Stheraven size_type& __sz() _NOEXCEPT {return __size_alloc_.first();} 546227825Stheraven _LIBCPP_INLINE_VISIBILITY 547227825Stheraven const size_type& __sz() const _NOEXCEPT 548227825Stheraven {return __size_alloc_.first();} 549227825Stheraven _LIBCPP_INLINE_VISIBILITY 550227825Stheraven __node_allocator& __node_alloc() _NOEXCEPT 551227825Stheraven {return __size_alloc_.second();} 552227825Stheraven _LIBCPP_INLINE_VISIBILITY 553227825Stheraven const __node_allocator& __node_alloc() const _NOEXCEPT 554227825Stheraven {return __size_alloc_.second();} 555227825Stheraven 556253159Stheraven static void __unlink_nodes(__node_pointer __f, __node_pointer __l) _NOEXCEPT; 557227825Stheraven 558227825Stheraven __list_imp() 559227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value); 560227825Stheraven __list_imp(const allocator_type& __a); 561227825Stheraven ~__list_imp(); 562227825Stheraven void clear() _NOEXCEPT; 563227825Stheraven _LIBCPP_INLINE_VISIBILITY 564227825Stheraven bool empty() const _NOEXCEPT {return __sz() == 0;} 565227825Stheraven 566227825Stheraven _LIBCPP_INLINE_VISIBILITY 567227825Stheraven iterator begin() _NOEXCEPT 568227825Stheraven { 569227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 570227825Stheraven return iterator(__end_.__next_, this); 571227825Stheraven#else 572227825Stheraven return iterator(__end_.__next_); 573227825Stheraven#endif 574227825Stheraven } 575227825Stheraven _LIBCPP_INLINE_VISIBILITY 576227825Stheraven const_iterator begin() const _NOEXCEPT 577227825Stheraven { 578227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 579227825Stheraven return const_iterator(__end_.__next_, this); 580227825Stheraven#else 581227825Stheraven return const_iterator(__end_.__next_); 582227825Stheraven#endif 583227825Stheraven } 584227825Stheraven _LIBCPP_INLINE_VISIBILITY 585227825Stheraven iterator end() _NOEXCEPT 586227825Stheraven { 587227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 588253159Stheraven return iterator(static_cast<__node_pointer>( 589253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(__end_)), this); 590227825Stheraven#else 591253159Stheraven return iterator(static_cast<__node_pointer>( 592253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(__end_))); 593227825Stheraven#endif 594227825Stheraven } 595227825Stheraven _LIBCPP_INLINE_VISIBILITY 596227825Stheraven const_iterator end() const _NOEXCEPT 597227825Stheraven { 598227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 599253159Stheraven return const_iterator(static_cast<__node_const_pointer>( 600253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(__end_))), this); 601227825Stheraven#else 602253159Stheraven return const_iterator(static_cast<__node_const_pointer>( 603253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(__end_)))); 604227825Stheraven#endif 605227825Stheraven } 606227825Stheraven 607227825Stheraven void swap(__list_imp& __c) 608227825Stheraven _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || 609227825Stheraven __is_nothrow_swappable<__node_allocator>::value); 610227825Stheraven 611227825Stheraven _LIBCPP_INLINE_VISIBILITY 612227825Stheraven void __copy_assign_alloc(const __list_imp& __c) 613227825Stheraven {__copy_assign_alloc(__c, integral_constant<bool, 614227825Stheraven __node_alloc_traits::propagate_on_container_copy_assignment::value>());} 615227825Stheraven 616227825Stheraven _LIBCPP_INLINE_VISIBILITY 617227825Stheraven void __move_assign_alloc(__list_imp& __c) 618227825Stheraven _NOEXCEPT_( 619227825Stheraven !__node_alloc_traits::propagate_on_container_move_assignment::value || 620227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 621227825Stheraven {__move_assign_alloc(__c, integral_constant<bool, 622227825Stheraven __node_alloc_traits::propagate_on_container_move_assignment::value>());} 623227825Stheraven 624227825Stheravenprivate: 625227825Stheraven _LIBCPP_INLINE_VISIBILITY 626227825Stheraven static void __swap_alloc(__node_allocator& __x, __node_allocator& __y) 627227825Stheraven _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || 628227825Stheraven __is_nothrow_swappable<__node_allocator>::value) 629227825Stheraven {__swap_alloc(__x, __y, integral_constant<bool, 630227825Stheraven __node_alloc_traits::propagate_on_container_swap::value>());} 631227825Stheraven _LIBCPP_INLINE_VISIBILITY 632227825Stheraven static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, true_type) 633227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__node_allocator>::value) 634227825Stheraven { 635227825Stheraven using _VSTD::swap; 636227825Stheraven swap(__x, __y); 637227825Stheraven } 638227825Stheraven _LIBCPP_INLINE_VISIBILITY 639227825Stheraven static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, false_type) 640227825Stheraven _NOEXCEPT 641227825Stheraven {} 642227825Stheraven 643227825Stheraven _LIBCPP_INLINE_VISIBILITY 644227825Stheraven void __copy_assign_alloc(const __list_imp& __c, true_type) 645227825Stheraven { 646227825Stheraven if (__node_alloc() != __c.__node_alloc()) 647227825Stheraven clear(); 648227825Stheraven __node_alloc() = __c.__node_alloc(); 649227825Stheraven } 650227825Stheraven 651227825Stheraven _LIBCPP_INLINE_VISIBILITY 652227825Stheraven void __copy_assign_alloc(const __list_imp& __c, false_type) 653227825Stheraven {} 654227825Stheraven 655227825Stheraven _LIBCPP_INLINE_VISIBILITY 656227825Stheraven void __move_assign_alloc(__list_imp& __c, true_type) 657227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 658227825Stheraven { 659227825Stheraven __node_alloc() = _VSTD::move(__c.__node_alloc()); 660227825Stheraven } 661227825Stheraven 662227825Stheraven _LIBCPP_INLINE_VISIBILITY 663227825Stheraven void __move_assign_alloc(__list_imp& __c, false_type) 664227825Stheraven _NOEXCEPT 665227825Stheraven {} 666227825Stheraven}; 667227825Stheraven 668227825Stheraven// Unlink nodes [__f, __l] 669227825Stheraventemplate <class _Tp, class _Alloc> 670227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 671227825Stheravenvoid 672253159Stheraven__list_imp<_Tp, _Alloc>::__unlink_nodes(__node_pointer __f, __node_pointer __l) 673227825Stheraven _NOEXCEPT 674227825Stheraven{ 675253159Stheraven __f->__prev_->__next_ = __l->__next_; 676253159Stheraven __l->__next_->__prev_ = __f->__prev_; 677227825Stheraven} 678227825Stheraven 679227825Stheraventemplate <class _Tp, class _Alloc> 680227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 681227825Stheraven__list_imp<_Tp, _Alloc>::__list_imp() 682227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 683227825Stheraven : __size_alloc_(0) 684227825Stheraven{ 685227825Stheraven} 686227825Stheraven 687227825Stheraventemplate <class _Tp, class _Alloc> 688227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 689227825Stheraven__list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a) 690227825Stheraven : __size_alloc_(0, __node_allocator(__a)) 691227825Stheraven{ 692227825Stheraven} 693227825Stheraven 694227825Stheraventemplate <class _Tp, class _Alloc> 695227825Stheraven__list_imp<_Tp, _Alloc>::~__list_imp() 696227825Stheraven{ 697227825Stheraven clear(); 698227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 699227825Stheraven __get_db()->__erase_c(this); 700227825Stheraven#endif 701227825Stheraven} 702227825Stheraven 703227825Stheraventemplate <class _Tp, class _Alloc> 704227825Stheravenvoid 705227825Stheraven__list_imp<_Tp, _Alloc>::clear() _NOEXCEPT 706227825Stheraven{ 707227825Stheraven if (!empty()) 708227825Stheraven { 709227825Stheraven __node_allocator& __na = __node_alloc(); 710227825Stheraven __node_pointer __f = __end_.__next_; 711253159Stheraven __node_pointer __l = static_cast<__node_pointer>( 712253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(__end_)); 713253159Stheraven __unlink_nodes(__f, __l->__prev_); 714227825Stheraven __sz() = 0; 715227825Stheraven while (__f != __l) 716227825Stheraven { 717253159Stheraven __node_pointer __n = __f; 718227825Stheraven __f = __f->__next_; 719253159Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_)); 720253159Stheraven __node_alloc_traits::deallocate(__na, __n, 1); 721227825Stheraven } 722227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 723227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 724227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 725227825Stheraven { 726227825Stheraven --__p; 727227825Stheraven const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); 728227825Stheraven if (__i->__ptr_ != __l) 729227825Stheraven { 730227825Stheraven (*__p)->__c_ = nullptr; 731227825Stheraven if (--__c->end_ != __p) 732227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 733227825Stheraven } 734227825Stheraven } 735227825Stheraven __get_db()->unlock(); 736227825Stheraven#endif 737227825Stheraven } 738227825Stheraven} 739227825Stheraven 740227825Stheraventemplate <class _Tp, class _Alloc> 741227825Stheravenvoid 742227825Stheraven__list_imp<_Tp, _Alloc>::swap(__list_imp& __c) 743227825Stheraven _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || 744227825Stheraven __is_nothrow_swappable<__node_allocator>::value) 745227825Stheraven{ 746227825Stheraven _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value || 747227825Stheraven this->__node_alloc() == __c.__node_alloc(), 748227825Stheraven "list::swap: Either propagate_on_container_swap must be true" 749227825Stheraven " or the allocators must compare equal"); 750227825Stheraven using _VSTD::swap; 751227825Stheraven __swap_alloc(__node_alloc(), __c.__node_alloc()); 752227825Stheraven swap(__sz(), __c.__sz()); 753227825Stheraven swap(__end_, __c.__end_); 754227825Stheraven if (__sz() == 0) 755278724Sdim __end_.__next_ = __end_.__prev_ = __end_.__self(); 756227825Stheraven else 757278724Sdim __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_.__self(); 758227825Stheraven if (__c.__sz() == 0) 759278724Sdim __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_.__self(); 760227825Stheraven else 761278724Sdim __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_.__self(); 762278724Sdim 763227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 764227825Stheraven __libcpp_db* __db = __get_db(); 765227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 766227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 767227825Stheraven std::swap(__cn1->beg_, __cn2->beg_); 768227825Stheraven std::swap(__cn1->end_, __cn2->end_); 769227825Stheraven std::swap(__cn1->cap_, __cn2->cap_); 770227825Stheraven for (__i_node** __p = __cn1->end_; __p != __cn1->beg_;) 771227825Stheraven { 772227825Stheraven --__p; 773227825Stheraven const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); 774253159Stheraven if (__i->__ptr_ == static_cast<__node_pointer>( 775253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(__c.__end_))) 776227825Stheraven { 777227825Stheraven __cn2->__add(*__p); 778227825Stheraven if (--__cn1->end_ != __p) 779227825Stheraven memmove(__p, __p+1, (__cn1->end_ - __p)*sizeof(__i_node*)); 780227825Stheraven } 781227825Stheraven else 782227825Stheraven (*__p)->__c_ = __cn1; 783227825Stheraven } 784227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 785227825Stheraven { 786227825Stheraven --__p; 787227825Stheraven const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); 788253159Stheraven if (__i->__ptr_ == static_cast<__node_pointer>( 789253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(__end_))) 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 802227825Stheraventemplate <class _Tp, class _Alloc = allocator<_Tp> > 803262801Sdimclass _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; 811253159Stheraven typedef typename base::__node_base __node_base; 812253159Stheraven typedef typename base::__node_base_pointer __node_base_pointer; 813227825Stheraven 814227825Stheravenpublic: 815227825Stheraven typedef _Tp value_type; 816227825Stheraven typedef _Alloc allocator_type; 817227825Stheraven static_assert((is_same<value_type, typename allocator_type::value_type>::value), 818227825Stheraven "Invalid allocator::value_type"); 819227825Stheraven typedef value_type& reference; 820227825Stheraven typedef const value_type& const_reference; 821227825Stheraven typedef typename base::pointer pointer; 822227825Stheraven typedef typename base::const_pointer const_pointer; 823227825Stheraven typedef typename base::size_type size_type; 824227825Stheraven typedef typename base::difference_type difference_type; 825227825Stheraven typedef typename base::iterator iterator; 826227825Stheraven typedef typename base::const_iterator const_iterator; 827227825Stheraven typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 828227825Stheraven typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 829227825Stheraven 830227825Stheraven _LIBCPP_INLINE_VISIBILITY 831227825Stheraven list() 832227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value) 833227825Stheraven { 834227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 835227825Stheraven __get_db()->__insert_c(this); 836227825Stheraven#endif 837227825Stheraven } 838227825Stheraven _LIBCPP_INLINE_VISIBILITY 839262801Sdim explicit list(const allocator_type& __a) : base(__a) 840227825Stheraven { 841227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 842227825Stheraven __get_db()->__insert_c(this); 843227825Stheraven#endif 844227825Stheraven } 845262801Sdim explicit list(size_type __n); 846262801Sdim#if _LIBCPP_STD_VER > 11 847262801Sdim explicit list(size_type __n, const allocator_type& __a); 848262801Sdim#endif 849227825Stheraven list(size_type __n, const value_type& __x); 850227825Stheraven list(size_type __n, const value_type& __x, const allocator_type& __a); 851227825Stheraven template <class _InpIter> 852227825Stheraven list(_InpIter __f, _InpIter __l, 853227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); 854227825Stheraven template <class _InpIter> 855227825Stheraven list(_InpIter __f, _InpIter __l, const allocator_type& __a, 856227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); 857227825Stheraven 858227825Stheraven list(const list& __c); 859227825Stheraven list(const list& __c, const allocator_type& __a); 860227825Stheraven list& operator=(const list& __c); 861227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 862227825Stheraven list(initializer_list<value_type> __il); 863227825Stheraven list(initializer_list<value_type> __il, const allocator_type& __a); 864227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 865227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 866227825Stheraven list(list&& __c) 867227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value); 868227825Stheraven list(list&& __c, const allocator_type& __a); 869227825Stheraven list& operator=(list&& __c) 870227825Stheraven _NOEXCEPT_( 871227825Stheraven __node_alloc_traits::propagate_on_container_move_assignment::value && 872227825Stheraven is_nothrow_move_assignable<__node_allocator>::value); 873227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 874227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 875227825Stheraven _LIBCPP_INLINE_VISIBILITY 876227825Stheraven list& operator=(initializer_list<value_type> __il) 877227825Stheraven {assign(__il.begin(), __il.end()); return *this;} 878227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 879227825Stheraven 880227825Stheraven template <class _InpIter> 881227825Stheraven void assign(_InpIter __f, _InpIter __l, 882227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); 883227825Stheraven void assign(size_type __n, const value_type& __x); 884227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 885227825Stheraven _LIBCPP_INLINE_VISIBILITY 886227825Stheraven void assign(initializer_list<value_type> __il) 887227825Stheraven {assign(__il.begin(), __il.end());} 888227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 889227825Stheraven 890227825Stheraven allocator_type get_allocator() const _NOEXCEPT; 891227825Stheraven 892227825Stheraven _LIBCPP_INLINE_VISIBILITY 893227825Stheraven size_type size() const _NOEXCEPT {return base::__sz();} 894227825Stheraven _LIBCPP_INLINE_VISIBILITY 895227825Stheraven bool empty() const _NOEXCEPT {return base::empty();} 896227825Stheraven _LIBCPP_INLINE_VISIBILITY 897227825Stheraven size_type max_size() const _NOEXCEPT 898227825Stheraven {return numeric_limits<difference_type>::max();} 899227825Stheraven 900227825Stheraven _LIBCPP_INLINE_VISIBILITY 901227825Stheraven iterator begin() _NOEXCEPT {return base::begin();} 902227825Stheraven _LIBCPP_INLINE_VISIBILITY 903227825Stheraven const_iterator begin() const _NOEXCEPT {return base::begin();} 904227825Stheraven _LIBCPP_INLINE_VISIBILITY 905227825Stheraven iterator end() _NOEXCEPT {return base::end();} 906227825Stheraven _LIBCPP_INLINE_VISIBILITY 907227825Stheraven const_iterator end() const _NOEXCEPT {return base::end();} 908227825Stheraven _LIBCPP_INLINE_VISIBILITY 909227825Stheraven const_iterator cbegin() const _NOEXCEPT {return base::begin();} 910227825Stheraven _LIBCPP_INLINE_VISIBILITY 911227825Stheraven const_iterator cend() const _NOEXCEPT {return base::end();} 912227825Stheraven 913227825Stheraven _LIBCPP_INLINE_VISIBILITY 914227825Stheraven reverse_iterator rbegin() _NOEXCEPT 915227825Stheraven {return reverse_iterator(end());} 916227825Stheraven _LIBCPP_INLINE_VISIBILITY 917227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 918227825Stheraven {return const_reverse_iterator(end());} 919227825Stheraven _LIBCPP_INLINE_VISIBILITY 920227825Stheraven reverse_iterator rend() _NOEXCEPT 921227825Stheraven {return reverse_iterator(begin());} 922227825Stheraven _LIBCPP_INLINE_VISIBILITY 923227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 924227825Stheraven {return const_reverse_iterator(begin());} 925227825Stheraven _LIBCPP_INLINE_VISIBILITY 926227825Stheraven const_reverse_iterator crbegin() const _NOEXCEPT 927227825Stheraven {return const_reverse_iterator(end());} 928227825Stheraven _LIBCPP_INLINE_VISIBILITY 929227825Stheraven const_reverse_iterator crend() const _NOEXCEPT 930227825Stheraven {return const_reverse_iterator(begin());} 931227825Stheraven 932227825Stheraven _LIBCPP_INLINE_VISIBILITY 933227825Stheraven reference front() 934227825Stheraven { 935227825Stheraven _LIBCPP_ASSERT(!empty(), "list::front called on empty list"); 936227825Stheraven return base::__end_.__next_->__value_; 937227825Stheraven } 938227825Stheraven _LIBCPP_INLINE_VISIBILITY 939227825Stheraven const_reference front() const 940227825Stheraven { 941227825Stheraven _LIBCPP_ASSERT(!empty(), "list::front called on empty list"); 942227825Stheraven return base::__end_.__next_->__value_; 943227825Stheraven } 944227825Stheraven _LIBCPP_INLINE_VISIBILITY 945227825Stheraven reference back() 946227825Stheraven { 947227825Stheraven _LIBCPP_ASSERT(!empty(), "list::back called on empty list"); 948227825Stheraven return base::__end_.__prev_->__value_; 949227825Stheraven } 950227825Stheraven _LIBCPP_INLINE_VISIBILITY 951227825Stheraven const_reference back() const 952227825Stheraven { 953227825Stheraven _LIBCPP_ASSERT(!empty(), "list::back called on empty list"); 954227825Stheraven return base::__end_.__prev_->__value_; 955227825Stheraven } 956227825Stheraven 957227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 958227825Stheraven void push_front(value_type&& __x); 959227825Stheraven void push_back(value_type&& __x); 960227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 961227825Stheraven template <class... _Args> 962227825Stheraven void emplace_front(_Args&&... __args); 963227825Stheraven template <class... _Args> 964227825Stheraven void emplace_back(_Args&&... __args); 965227825Stheraven template <class... _Args> 966227825Stheraven iterator emplace(const_iterator __p, _Args&&... __args); 967227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 968227825Stheraven iterator insert(const_iterator __p, value_type&& __x); 969227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 970227825Stheraven 971227825Stheraven void push_front(const value_type& __x); 972227825Stheraven void push_back(const value_type& __x); 973227825Stheraven 974227825Stheraven iterator insert(const_iterator __p, const value_type& __x); 975227825Stheraven iterator insert(const_iterator __p, size_type __n, const value_type& __x); 976227825Stheraven template <class _InpIter> 977227825Stheraven iterator insert(const_iterator __p, _InpIter __f, _InpIter __l, 978227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); 979227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 980227825Stheraven _LIBCPP_INLINE_VISIBILITY 981227825Stheraven iterator insert(const_iterator __p, initializer_list<value_type> __il) 982227825Stheraven {return insert(__p, __il.begin(), __il.end());} 983227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 984227825Stheraven 985227825Stheraven _LIBCPP_INLINE_VISIBILITY 986227825Stheraven void swap(list& __c) 987227825Stheraven _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value || 988227825Stheraven __is_nothrow_swappable<__node_allocator>::value) 989227825Stheraven {base::swap(__c);} 990227825Stheraven _LIBCPP_INLINE_VISIBILITY 991227825Stheraven void clear() _NOEXCEPT {base::clear();} 992227825Stheraven 993227825Stheraven void pop_front(); 994227825Stheraven void pop_back(); 995227825Stheraven 996227825Stheraven iterator erase(const_iterator __p); 997227825Stheraven iterator erase(const_iterator __f, const_iterator __l); 998227825Stheraven 999227825Stheraven void resize(size_type __n); 1000227825Stheraven void resize(size_type __n, const value_type& __x); 1001227825Stheraven 1002227825Stheraven void splice(const_iterator __p, list& __c); 1003227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1004227825Stheraven _LIBCPP_INLINE_VISIBILITY 1005227825Stheraven void splice(const_iterator __p, list&& __c) {splice(__p, __c);} 1006227825Stheraven#endif 1007227825Stheraven void splice(const_iterator __p, list& __c, const_iterator __i); 1008227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1009227825Stheraven _LIBCPP_INLINE_VISIBILITY 1010227825Stheraven void splice(const_iterator __p, list&& __c, const_iterator __i) 1011227825Stheraven {splice(__p, __c, __i);} 1012227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1013227825Stheraven void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l); 1014227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1015227825Stheraven _LIBCPP_INLINE_VISIBILITY 1016227825Stheraven void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l) 1017227825Stheraven {splice(__p, __c, __f, __l);} 1018227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1019227825Stheraven 1020227825Stheraven void remove(const value_type& __x); 1021227825Stheraven template <class _Pred> void remove_if(_Pred __pred); 1022227825Stheraven void unique(); 1023227825Stheraven template <class _BinaryPred> 1024227825Stheraven void unique(_BinaryPred __binary_pred); 1025227825Stheraven void merge(list& __c); 1026227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1027227825Stheraven _LIBCPP_INLINE_VISIBILITY 1028227825Stheraven void merge(list&& __c) {merge(__c);} 1029227825Stheraven#endif 1030227825Stheraven template <class _Comp> 1031227825Stheraven void merge(list& __c, _Comp __comp); 1032227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1033227825Stheraven template <class _Comp> 1034227825Stheraven _LIBCPP_INLINE_VISIBILITY 1035227825Stheraven void merge(list&& __c, _Comp __comp) {merge(__c, __comp);} 1036227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1037227825Stheraven void sort(); 1038227825Stheraven template <class _Comp> 1039227825Stheraven void sort(_Comp __comp); 1040227825Stheraven 1041227825Stheraven void reverse() _NOEXCEPT; 1042227825Stheraven 1043227825Stheraven bool __invariants() const; 1044227825Stheraven 1045227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1046227825Stheraven 1047227825Stheraven bool __dereferenceable(const const_iterator* __i) const; 1048227825Stheraven bool __decrementable(const const_iterator* __i) const; 1049227825Stheraven bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 1050227825Stheraven bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 1051227825Stheraven 1052227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 1053227825Stheraven 1054227825Stheravenprivate: 1055278724Sdim static void __link_nodes (__node_pointer __p, __node_pointer __f, __node_pointer __l); 1056278724Sdim void __link_nodes_at_front(__node_pointer __f, __node_pointer __l); 1057278724Sdim void __link_nodes_at_back (__node_pointer __f, __node_pointer __l); 1058227825Stheraven iterator __iterator(size_type __n); 1059227825Stheraven template <class _Comp> 1060227825Stheraven static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp); 1061227825Stheraven 1062227825Stheraven void __move_assign(list& __c, true_type) 1063227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value); 1064227825Stheraven void __move_assign(list& __c, false_type); 1065227825Stheraven}; 1066227825Stheraven 1067227825Stheraven// Link in nodes [__f, __l] just prior to __p 1068227825Stheraventemplate <class _Tp, class _Alloc> 1069227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1070227825Stheravenvoid 1071253159Stheravenlist<_Tp, _Alloc>::__link_nodes(__node_pointer __p, __node_pointer __f, __node_pointer __l) 1072227825Stheraven{ 1073253159Stheraven __p->__prev_->__next_ = __f; 1074253159Stheraven __f->__prev_ = __p->__prev_; 1075253159Stheraven __p->__prev_ = __l; 1076253159Stheraven __l->__next_ = __p; 1077227825Stheraven} 1078227825Stheraven 1079278724Sdim// Link in nodes [__f, __l] at the front of the list 1080227825Stheraventemplate <class _Tp, class _Alloc> 1081227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1082278724Sdimvoid 1083278724Sdimlist<_Tp, _Alloc>::__link_nodes_at_front(__node_pointer __f, __node_pointer __l) 1084278724Sdim{ 1085278724Sdim __f->__prev_ = base::__end_.__self(); 1086278724Sdim __l->__next_ = base::__end_.__next_; 1087278724Sdim __l->__next_->__prev_ = __l; 1088278724Sdim base::__end_.__next_ = __f; 1089278724Sdim} 1090278724Sdim 1091278724Sdim// Link in nodes [__f, __l] at the front of the list 1092278724Sdimtemplate <class _Tp, class _Alloc> 1093278724Sdiminline _LIBCPP_INLINE_VISIBILITY 1094278724Sdimvoid 1095278724Sdimlist<_Tp, _Alloc>::__link_nodes_at_back(__node_pointer __f, __node_pointer __l) 1096278724Sdim{ 1097278724Sdim __l->__next_ = base::__end_.__self(); 1098278724Sdim __f->__prev_ = base::__end_.__prev_; 1099278724Sdim __f->__prev_->__next_ = __f; 1100278724Sdim base::__end_.__prev_ = __l; 1101278724Sdim} 1102278724Sdim 1103278724Sdim 1104278724Sdimtemplate <class _Tp, class _Alloc> 1105278724Sdiminline _LIBCPP_INLINE_VISIBILITY 1106227825Stheraventypename list<_Tp, _Alloc>::iterator 1107227825Stheravenlist<_Tp, _Alloc>::__iterator(size_type __n) 1108227825Stheraven{ 1109227825Stheraven return __n <= base::__sz() / 2 ? _VSTD::next(begin(), __n) 1110227825Stheraven : _VSTD::prev(end(), base::__sz() - __n); 1111227825Stheraven} 1112227825Stheraven 1113227825Stheraventemplate <class _Tp, class _Alloc> 1114227825Stheravenlist<_Tp, _Alloc>::list(size_type __n) 1115227825Stheraven{ 1116227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1117227825Stheraven __get_db()->__insert_c(this); 1118227825Stheraven#endif 1119227825Stheraven for (; __n > 0; --__n) 1120227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1121227825Stheraven emplace_back(); 1122227825Stheraven#else 1123227825Stheraven push_back(value_type()); 1124227825Stheraven#endif 1125227825Stheraven} 1126227825Stheraven 1127262801Sdim#if _LIBCPP_STD_VER > 11 1128227825Stheraventemplate <class _Tp, class _Alloc> 1129262801Sdimlist<_Tp, _Alloc>::list(size_type __n, const allocator_type& __a) : base(__a) 1130262801Sdim{ 1131262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1132262801Sdim __get_db()->__insert_c(this); 1133262801Sdim#endif 1134262801Sdim for (; __n > 0; --__n) 1135262801Sdim#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1136262801Sdim emplace_back(); 1137262801Sdim#else 1138262801Sdim push_back(value_type()); 1139262801Sdim#endif 1140262801Sdim} 1141262801Sdim#endif 1142262801Sdim 1143262801Sdimtemplate <class _Tp, class _Alloc> 1144227825Stheravenlist<_Tp, _Alloc>::list(size_type __n, const value_type& __x) 1145227825Stheraven{ 1146227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1147227825Stheraven __get_db()->__insert_c(this); 1148227825Stheraven#endif 1149227825Stheraven for (; __n > 0; --__n) 1150227825Stheraven push_back(__x); 1151227825Stheraven} 1152227825Stheraven 1153227825Stheraventemplate <class _Tp, class _Alloc> 1154227825Stheravenlist<_Tp, _Alloc>::list(size_type __n, const value_type& __x, const allocator_type& __a) 1155227825Stheraven : base(__a) 1156227825Stheraven{ 1157227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1158227825Stheraven __get_db()->__insert_c(this); 1159227825Stheraven#endif 1160227825Stheraven for (; __n > 0; --__n) 1161227825Stheraven push_back(__x); 1162227825Stheraven} 1163227825Stheraven 1164227825Stheraventemplate <class _Tp, class _Alloc> 1165227825Stheraventemplate <class _InpIter> 1166227825Stheravenlist<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, 1167227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type*) 1168227825Stheraven{ 1169227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1170227825Stheraven __get_db()->__insert_c(this); 1171227825Stheraven#endif 1172227825Stheraven for (; __f != __l; ++__f) 1173227825Stheraven push_back(*__f); 1174227825Stheraven} 1175227825Stheraven 1176227825Stheraventemplate <class _Tp, class _Alloc> 1177227825Stheraventemplate <class _InpIter> 1178227825Stheravenlist<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a, 1179227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type*) 1180227825Stheraven : base(__a) 1181227825Stheraven{ 1182227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1183227825Stheraven __get_db()->__insert_c(this); 1184227825Stheraven#endif 1185227825Stheraven for (; __f != __l; ++__f) 1186227825Stheraven push_back(*__f); 1187227825Stheraven} 1188227825Stheraven 1189227825Stheraventemplate <class _Tp, class _Alloc> 1190227825Stheravenlist<_Tp, _Alloc>::list(const list& __c) 1191227825Stheraven : base(allocator_type( 1192227825Stheraven __node_alloc_traits::select_on_container_copy_construction( 1193227825Stheraven __c.__node_alloc()))) 1194227825Stheraven{ 1195227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1196227825Stheraven __get_db()->__insert_c(this); 1197227825Stheraven#endif 1198227825Stheraven for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) 1199227825Stheraven push_back(*__i); 1200227825Stheraven} 1201227825Stheraven 1202227825Stheraventemplate <class _Tp, class _Alloc> 1203227825Stheravenlist<_Tp, _Alloc>::list(const list& __c, const allocator_type& __a) 1204227825Stheraven : base(__a) 1205227825Stheraven{ 1206227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1207227825Stheraven __get_db()->__insert_c(this); 1208227825Stheraven#endif 1209227825Stheraven for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) 1210227825Stheraven push_back(*__i); 1211227825Stheraven} 1212227825Stheraven 1213227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1214227825Stheraven 1215227825Stheraventemplate <class _Tp, class _Alloc> 1216227825Stheravenlist<_Tp, _Alloc>::list(initializer_list<value_type> __il, const allocator_type& __a) 1217227825Stheraven : base(__a) 1218227825Stheraven{ 1219227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1220227825Stheraven __get_db()->__insert_c(this); 1221227825Stheraven#endif 1222227825Stheraven for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), 1223227825Stheraven __e = __il.end(); __i != __e; ++__i) 1224227825Stheraven push_back(*__i); 1225227825Stheraven} 1226227825Stheraven 1227227825Stheraventemplate <class _Tp, class _Alloc> 1228227825Stheravenlist<_Tp, _Alloc>::list(initializer_list<value_type> __il) 1229227825Stheraven{ 1230227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1231227825Stheraven __get_db()->__insert_c(this); 1232227825Stheraven#endif 1233227825Stheraven for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), 1234227825Stheraven __e = __il.end(); __i != __e; ++__i) 1235227825Stheraven push_back(*__i); 1236227825Stheraven} 1237227825Stheraven 1238227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1239227825Stheraven 1240227825Stheraventemplate <class _Tp, class _Alloc> 1241227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1242227825Stheravenlist<_Tp, _Alloc>& 1243227825Stheravenlist<_Tp, _Alloc>::operator=(const list& __c) 1244227825Stheraven{ 1245227825Stheraven if (this != &__c) 1246227825Stheraven { 1247227825Stheraven base::__copy_assign_alloc(__c); 1248227825Stheraven assign(__c.begin(), __c.end()); 1249227825Stheraven } 1250227825Stheraven return *this; 1251227825Stheraven} 1252227825Stheraven 1253227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1254227825Stheraven 1255227825Stheraventemplate <class _Tp, class _Alloc> 1256227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1257227825Stheravenlist<_Tp, _Alloc>::list(list&& __c) 1258227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value) 1259227825Stheraven : base(allocator_type(_VSTD::move(__c.__node_alloc()))) 1260227825Stheraven{ 1261227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1262227825Stheraven __get_db()->__insert_c(this); 1263227825Stheraven#endif 1264227825Stheraven splice(end(), __c); 1265227825Stheraven} 1266227825Stheraven 1267227825Stheraventemplate <class _Tp, class _Alloc> 1268227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1269227825Stheravenlist<_Tp, _Alloc>::list(list&& __c, const allocator_type& __a) 1270227825Stheraven : base(__a) 1271227825Stheraven{ 1272227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1273227825Stheraven __get_db()->__insert_c(this); 1274227825Stheraven#endif 1275227825Stheraven if (__a == __c.get_allocator()) 1276227825Stheraven splice(end(), __c); 1277227825Stheraven else 1278227825Stheraven { 1279232950Stheraven typedef move_iterator<iterator> _Ip; 1280232950Stheraven assign(_Ip(__c.begin()), _Ip(__c.end())); 1281227825Stheraven } 1282227825Stheraven} 1283227825Stheraven 1284227825Stheraventemplate <class _Tp, class _Alloc> 1285227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1286227825Stheravenlist<_Tp, _Alloc>& 1287227825Stheravenlist<_Tp, _Alloc>::operator=(list&& __c) 1288227825Stheraven _NOEXCEPT_( 1289227825Stheraven __node_alloc_traits::propagate_on_container_move_assignment::value && 1290227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 1291227825Stheraven{ 1292227825Stheraven __move_assign(__c, integral_constant<bool, 1293227825Stheraven __node_alloc_traits::propagate_on_container_move_assignment::value>()); 1294227825Stheraven return *this; 1295227825Stheraven} 1296227825Stheraven 1297227825Stheraventemplate <class _Tp, class _Alloc> 1298227825Stheravenvoid 1299227825Stheravenlist<_Tp, _Alloc>::__move_assign(list& __c, false_type) 1300227825Stheraven{ 1301227825Stheraven if (base::__node_alloc() != __c.__node_alloc()) 1302227825Stheraven { 1303232950Stheraven typedef move_iterator<iterator> _Ip; 1304232950Stheraven assign(_Ip(__c.begin()), _Ip(__c.end())); 1305227825Stheraven } 1306227825Stheraven else 1307227825Stheraven __move_assign(__c, true_type()); 1308227825Stheraven} 1309227825Stheraven 1310227825Stheraventemplate <class _Tp, class _Alloc> 1311227825Stheravenvoid 1312227825Stheravenlist<_Tp, _Alloc>::__move_assign(list& __c, true_type) 1313227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) 1314227825Stheraven{ 1315227825Stheraven clear(); 1316227825Stheraven base::__move_assign_alloc(__c); 1317227825Stheraven splice(end(), __c); 1318227825Stheraven} 1319227825Stheraven 1320227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1321227825Stheraven 1322227825Stheraventemplate <class _Tp, class _Alloc> 1323227825Stheraventemplate <class _InpIter> 1324227825Stheravenvoid 1325227825Stheravenlist<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l, 1326227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type*) 1327227825Stheraven{ 1328227825Stheraven iterator __i = begin(); 1329227825Stheraven iterator __e = end(); 1330227825Stheraven for (; __f != __l && __i != __e; ++__f, ++__i) 1331227825Stheraven *__i = *__f; 1332227825Stheraven if (__i == __e) 1333227825Stheraven insert(__e, __f, __l); 1334227825Stheraven else 1335227825Stheraven erase(__i, __e); 1336227825Stheraven} 1337227825Stheraven 1338227825Stheraventemplate <class _Tp, class _Alloc> 1339227825Stheravenvoid 1340227825Stheravenlist<_Tp, _Alloc>::assign(size_type __n, const value_type& __x) 1341227825Stheraven{ 1342227825Stheraven iterator __i = begin(); 1343227825Stheraven iterator __e = end(); 1344227825Stheraven for (; __n > 0 && __i != __e; --__n, ++__i) 1345227825Stheraven *__i = __x; 1346227825Stheraven if (__i == __e) 1347227825Stheraven insert(__e, __n, __x); 1348227825Stheraven else 1349227825Stheraven erase(__i, __e); 1350227825Stheraven} 1351227825Stheraven 1352227825Stheraventemplate <class _Tp, class _Alloc> 1353227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1354227825Stheraven_Alloc 1355227825Stheravenlist<_Tp, _Alloc>::get_allocator() const _NOEXCEPT 1356227825Stheraven{ 1357227825Stheraven return allocator_type(base::__node_alloc()); 1358227825Stheraven} 1359227825Stheraven 1360227825Stheraventemplate <class _Tp, class _Alloc> 1361227825Stheraventypename list<_Tp, _Alloc>::iterator 1362227825Stheravenlist<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x) 1363227825Stheraven{ 1364227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1365227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1366227825Stheraven "list::insert(iterator, x) called with an iterator not" 1367227825Stheraven " referring to this list"); 1368227825Stheraven#endif 1369227825Stheraven __node_allocator& __na = base::__node_alloc(); 1370232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1371232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1372227825Stheraven __hold->__prev_ = 0; 1373227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1374253159Stheraven __link_nodes(__p.__ptr_, __hold.get(), __hold.get()); 1375227825Stheraven ++base::__sz(); 1376249998Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1377249998Sdim return iterator(__hold.release(), this); 1378249998Sdim#else 1379227825Stheraven return iterator(__hold.release()); 1380249998Sdim#endif 1381227825Stheraven} 1382227825Stheraven 1383227825Stheraventemplate <class _Tp, class _Alloc> 1384227825Stheraventypename list<_Tp, _Alloc>::iterator 1385227825Stheravenlist<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x) 1386227825Stheraven{ 1387227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1388227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1389227825Stheraven "list::insert(iterator, n, x) called with an iterator not" 1390227825Stheraven " referring to this list"); 1391253159Stheraven iterator __r(__p.__ptr_, this); 1392227825Stheraven#else 1393253159Stheraven iterator __r(__p.__ptr_); 1394227825Stheraven#endif 1395227825Stheraven if (__n > 0) 1396227825Stheraven { 1397227825Stheraven size_type __ds = 0; 1398227825Stheraven __node_allocator& __na = base::__node_alloc(); 1399232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1400232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1401227825Stheraven __hold->__prev_ = 0; 1402227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1403227825Stheraven ++__ds; 1404227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1405227825Stheraven __r = iterator(__hold.get(), this); 1406227825Stheraven#else 1407227825Stheraven __r = iterator(__hold.get()); 1408227825Stheraven#endif 1409227825Stheraven __hold.release(); 1410227825Stheraven iterator __e = __r; 1411227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1412227825Stheraven try 1413227825Stheraven { 1414227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1415227825Stheraven for (--__n; __n != 0; --__n, ++__e, ++__ds) 1416227825Stheraven { 1417227825Stheraven __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1418227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1419227825Stheraven __e.__ptr_->__next_ = __hold.get(); 1420227825Stheraven __hold->__prev_ = __e.__ptr_; 1421227825Stheraven __hold.release(); 1422227825Stheraven } 1423227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1424227825Stheraven } 1425227825Stheraven catch (...) 1426227825Stheraven { 1427227825Stheraven while (true) 1428227825Stheraven { 1429227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1430227825Stheraven __node_pointer __prev = __e.__ptr_->__prev_; 1431227825Stheraven __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); 1432227825Stheraven if (__prev == 0) 1433227825Stheraven break; 1434227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1435227825Stheraven __e = iterator(__prev, this); 1436227825Stheraven#else 1437227825Stheraven __e = iterator(__prev); 1438227825Stheraven#endif 1439227825Stheraven } 1440227825Stheraven throw; 1441227825Stheraven } 1442227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1443253159Stheraven __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_); 1444227825Stheraven base::__sz() += __ds; 1445227825Stheraven } 1446227825Stheraven return __r; 1447227825Stheraven} 1448227825Stheraven 1449227825Stheraventemplate <class _Tp, class _Alloc> 1450227825Stheraventemplate <class _InpIter> 1451227825Stheraventypename list<_Tp, _Alloc>::iterator 1452227825Stheravenlist<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l, 1453227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value>::type*) 1454227825Stheraven{ 1455227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1456227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1457227825Stheraven "list::insert(iterator, range) called with an iterator not" 1458227825Stheraven " referring to this list"); 1459253159Stheraven iterator __r(__p.__ptr_, this); 1460227825Stheraven#else 1461253159Stheraven iterator __r(__p.__ptr_); 1462227825Stheraven#endif 1463227825Stheraven if (__f != __l) 1464227825Stheraven { 1465227825Stheraven size_type __ds = 0; 1466227825Stheraven __node_allocator& __na = base::__node_alloc(); 1467232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1468232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1469227825Stheraven __hold->__prev_ = 0; 1470227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f); 1471227825Stheraven ++__ds; 1472227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1473227825Stheraven __r = iterator(__hold.get(), this); 1474227825Stheraven#else 1475227825Stheraven __r = iterator(__hold.get()); 1476227825Stheraven#endif 1477227825Stheraven __hold.release(); 1478227825Stheraven iterator __e = __r; 1479227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1480227825Stheraven try 1481227825Stheraven { 1482227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1483227825Stheraven for (++__f; __f != __l; ++__f, ++__e, ++__ds) 1484227825Stheraven { 1485227825Stheraven __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1486227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f); 1487227825Stheraven __e.__ptr_->__next_ = __hold.get(); 1488227825Stheraven __hold->__prev_ = __e.__ptr_; 1489227825Stheraven __hold.release(); 1490227825Stheraven } 1491227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1492227825Stheraven } 1493227825Stheraven catch (...) 1494227825Stheraven { 1495227825Stheraven while (true) 1496227825Stheraven { 1497227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1498227825Stheraven __node_pointer __prev = __e.__ptr_->__prev_; 1499227825Stheraven __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); 1500227825Stheraven if (__prev == 0) 1501227825Stheraven break; 1502227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1503227825Stheraven __e = iterator(__prev, this); 1504227825Stheraven#else 1505227825Stheraven __e = iterator(__prev); 1506227825Stheraven#endif 1507227825Stheraven } 1508227825Stheraven throw; 1509227825Stheraven } 1510227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1511253159Stheraven __link_nodes(__p.__ptr_, __r.__ptr_, __e.__ptr_); 1512227825Stheraven base::__sz() += __ds; 1513227825Stheraven } 1514227825Stheraven return __r; 1515227825Stheraven} 1516227825Stheraven 1517227825Stheraventemplate <class _Tp, class _Alloc> 1518227825Stheravenvoid 1519227825Stheravenlist<_Tp, _Alloc>::push_front(const value_type& __x) 1520227825Stheraven{ 1521227825Stheraven __node_allocator& __na = base::__node_alloc(); 1522232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1523232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1524227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1525278724Sdim __link_nodes_at_front(__hold.get(), __hold.get()); 1526227825Stheraven ++base::__sz(); 1527227825Stheraven __hold.release(); 1528227825Stheraven} 1529227825Stheraven 1530227825Stheraventemplate <class _Tp, class _Alloc> 1531227825Stheravenvoid 1532227825Stheravenlist<_Tp, _Alloc>::push_back(const value_type& __x) 1533227825Stheraven{ 1534227825Stheraven __node_allocator& __na = base::__node_alloc(); 1535232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1536232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1537227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1538278724Sdim __link_nodes_at_back(__hold.get(), __hold.get()); 1539227825Stheraven ++base::__sz(); 1540227825Stheraven __hold.release(); 1541227825Stheraven} 1542227825Stheraven 1543227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1544227825Stheraven 1545227825Stheraventemplate <class _Tp, class _Alloc> 1546227825Stheravenvoid 1547227825Stheravenlist<_Tp, _Alloc>::push_front(value_type&& __x) 1548227825Stheraven{ 1549227825Stheraven __node_allocator& __na = base::__node_alloc(); 1550232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1551232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1552227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); 1553278724Sdim __link_nodes_at_front(__hold.get(), __hold.get()); 1554227825Stheraven ++base::__sz(); 1555227825Stheraven __hold.release(); 1556227825Stheraven} 1557227825Stheraven 1558227825Stheraventemplate <class _Tp, class _Alloc> 1559227825Stheravenvoid 1560227825Stheravenlist<_Tp, _Alloc>::push_back(value_type&& __x) 1561227825Stheraven{ 1562227825Stheraven __node_allocator& __na = base::__node_alloc(); 1563232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1564232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1565227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); 1566278724Sdim __link_nodes_at_back(__hold.get(), __hold.get()); 1567227825Stheraven ++base::__sz(); 1568227825Stheraven __hold.release(); 1569227825Stheraven} 1570227825Stheraven 1571227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1572227825Stheraven 1573227825Stheraventemplate <class _Tp, class _Alloc> 1574227825Stheraventemplate <class... _Args> 1575227825Stheravenvoid 1576227825Stheravenlist<_Tp, _Alloc>::emplace_front(_Args&&... __args) 1577227825Stheraven{ 1578227825Stheraven __node_allocator& __na = base::__node_alloc(); 1579232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1580232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1581227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); 1582278724Sdim __link_nodes_at_front(__hold.get(), __hold.get()); 1583227825Stheraven ++base::__sz(); 1584227825Stheraven __hold.release(); 1585227825Stheraven} 1586227825Stheraven 1587227825Stheraventemplate <class _Tp, class _Alloc> 1588227825Stheraventemplate <class... _Args> 1589227825Stheravenvoid 1590227825Stheravenlist<_Tp, _Alloc>::emplace_back(_Args&&... __args) 1591227825Stheraven{ 1592227825Stheraven __node_allocator& __na = base::__node_alloc(); 1593232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1594232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1595227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); 1596278724Sdim __link_nodes_at_back(__hold.get(), __hold.get()); 1597227825Stheraven ++base::__sz(); 1598227825Stheraven __hold.release(); 1599227825Stheraven} 1600227825Stheraven 1601227825Stheraventemplate <class _Tp, class _Alloc> 1602227825Stheraventemplate <class... _Args> 1603227825Stheraventypename list<_Tp, _Alloc>::iterator 1604227825Stheravenlist<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args) 1605227825Stheraven{ 1606249998Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1607249998Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1608249998Sdim "list::emplace(iterator, args...) called with an iterator not" 1609249998Sdim " referring to this list"); 1610249998Sdim#endif 1611227825Stheraven __node_allocator& __na = base::__node_alloc(); 1612232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1613232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1614227825Stheraven __hold->__prev_ = 0; 1615227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...); 1616253159Stheraven __link_nodes(__p.__ptr_, __hold.get(), __hold.get()); 1617227825Stheraven ++base::__sz(); 1618227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1619227825Stheraven return iterator(__hold.release(), this); 1620227825Stheraven#else 1621227825Stheraven return iterator(__hold.release()); 1622227825Stheraven#endif 1623227825Stheraven} 1624227825Stheraven 1625227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1626227825Stheraven 1627227825Stheraventemplate <class _Tp, class _Alloc> 1628227825Stheraventypename list<_Tp, _Alloc>::iterator 1629227825Stheravenlist<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x) 1630227825Stheraven{ 1631227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1632227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1633227825Stheraven "list::insert(iterator, x) called with an iterator not" 1634227825Stheraven " referring to this list"); 1635227825Stheraven#endif 1636227825Stheraven __node_allocator& __na = base::__node_alloc(); 1637232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1638232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1639227825Stheraven __hold->__prev_ = 0; 1640227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x)); 1641253159Stheraven __link_nodes(__p.__ptr_, __hold.get(), __hold.get()); 1642227825Stheraven ++base::__sz(); 1643227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1644227825Stheraven return iterator(__hold.release(), this); 1645227825Stheraven#else 1646227825Stheraven return iterator(__hold.release()); 1647227825Stheraven#endif 1648227825Stheraven} 1649227825Stheraven 1650227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1651227825Stheraven 1652227825Stheraventemplate <class _Tp, class _Alloc> 1653227825Stheravenvoid 1654227825Stheravenlist<_Tp, _Alloc>::pop_front() 1655227825Stheraven{ 1656227825Stheraven _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list"); 1657227825Stheraven __node_allocator& __na = base::__node_alloc(); 1658253159Stheraven __node_pointer __n = base::__end_.__next_; 1659227825Stheraven base::__unlink_nodes(__n, __n); 1660227825Stheraven --base::__sz(); 1661227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1662227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 1663227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1664227825Stheraven { 1665227825Stheraven --__p; 1666227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1667253159Stheraven if (__i->__ptr_ == __n) 1668227825Stheraven { 1669227825Stheraven (*__p)->__c_ = nullptr; 1670227825Stheraven if (--__c->end_ != __p) 1671227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1672227825Stheraven } 1673227825Stheraven } 1674227825Stheraven __get_db()->unlock(); 1675227825Stheraven#endif 1676253159Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_)); 1677253159Stheraven __node_alloc_traits::deallocate(__na, __n, 1); 1678227825Stheraven} 1679227825Stheraven 1680227825Stheraventemplate <class _Tp, class _Alloc> 1681227825Stheravenvoid 1682227825Stheravenlist<_Tp, _Alloc>::pop_back() 1683227825Stheraven{ 1684253159Stheraven _LIBCPP_ASSERT(!empty(), "list::pop_back() called with empty list"); 1685227825Stheraven __node_allocator& __na = base::__node_alloc(); 1686253159Stheraven __node_pointer __n = base::__end_.__prev_; 1687227825Stheraven base::__unlink_nodes(__n, __n); 1688227825Stheraven --base::__sz(); 1689227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1690227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 1691227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1692227825Stheraven { 1693227825Stheraven --__p; 1694227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1695253159Stheraven if (__i->__ptr_ == __n) 1696227825Stheraven { 1697227825Stheraven (*__p)->__c_ = nullptr; 1698227825Stheraven if (--__c->end_ != __p) 1699227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1700227825Stheraven } 1701227825Stheraven } 1702227825Stheraven __get_db()->unlock(); 1703227825Stheraven#endif 1704253159Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_)); 1705253159Stheraven __node_alloc_traits::deallocate(__na, __n, 1); 1706227825Stheraven} 1707227825Stheraven 1708227825Stheraventemplate <class _Tp, class _Alloc> 1709227825Stheraventypename list<_Tp, _Alloc>::iterator 1710227825Stheravenlist<_Tp, _Alloc>::erase(const_iterator __p) 1711227825Stheraven{ 1712227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1713227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1714227825Stheraven "list::erase(iterator) called with an iterator not" 1715227825Stheraven " referring to this list"); 1716227825Stheraven#endif 1717249998Sdim _LIBCPP_ASSERT(__p != end(), 1718249998Sdim "list::erase(iterator) called with a non-dereferenceable iterator"); 1719227825Stheraven __node_allocator& __na = base::__node_alloc(); 1720253159Stheraven __node_pointer __n = __p.__ptr_; 1721253159Stheraven __node_pointer __r = __n->__next_; 1722227825Stheraven base::__unlink_nodes(__n, __n); 1723227825Stheraven --base::__sz(); 1724227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1725227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 1726227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1727227825Stheraven { 1728227825Stheraven --__p; 1729227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1730253159Stheraven if (__i->__ptr_ == __n) 1731227825Stheraven { 1732227825Stheraven (*__p)->__c_ = nullptr; 1733227825Stheraven if (--__c->end_ != __p) 1734227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1735227825Stheraven } 1736227825Stheraven } 1737227825Stheraven __get_db()->unlock(); 1738227825Stheraven#endif 1739253159Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_)); 1740253159Stheraven __node_alloc_traits::deallocate(__na, __n, 1); 1741227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1742227825Stheraven return iterator(__r, this); 1743227825Stheraven#else 1744227825Stheraven return iterator(__r); 1745227825Stheraven#endif 1746227825Stheraven} 1747227825Stheraven 1748227825Stheraventemplate <class _Tp, class _Alloc> 1749227825Stheraventypename list<_Tp, _Alloc>::iterator 1750227825Stheravenlist<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l) 1751227825Stheraven{ 1752227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1753227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == this, 1754227825Stheraven "list::erase(iterator, iterator) called with an iterator not" 1755227825Stheraven " referring to this list"); 1756227825Stheraven#endif 1757227825Stheraven if (__f != __l) 1758227825Stheraven { 1759227825Stheraven __node_allocator& __na = base::__node_alloc(); 1760253159Stheraven base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_); 1761227825Stheraven while (__f != __l) 1762227825Stheraven { 1763253159Stheraven __node_pointer __n = __f.__ptr_; 1764227825Stheraven ++__f; 1765227825Stheraven --base::__sz(); 1766227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1767227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 1768227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1769227825Stheraven { 1770227825Stheraven --__p; 1771227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1772253159Stheraven if (__i->__ptr_ == __n) 1773227825Stheraven { 1774227825Stheraven (*__p)->__c_ = nullptr; 1775227825Stheraven if (--__c->end_ != __p) 1776227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1777227825Stheraven } 1778227825Stheraven } 1779227825Stheraven __get_db()->unlock(); 1780227825Stheraven#endif 1781253159Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_)); 1782253159Stheraven __node_alloc_traits::deallocate(__na, __n, 1); 1783227825Stheraven } 1784227825Stheraven } 1785227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1786253159Stheraven return iterator(__l.__ptr_, this); 1787227825Stheraven#else 1788253159Stheraven return iterator(__l.__ptr_); 1789227825Stheraven#endif 1790227825Stheraven} 1791227825Stheraven 1792227825Stheraventemplate <class _Tp, class _Alloc> 1793227825Stheravenvoid 1794227825Stheravenlist<_Tp, _Alloc>::resize(size_type __n) 1795227825Stheraven{ 1796227825Stheraven if (__n < base::__sz()) 1797227825Stheraven erase(__iterator(__n), end()); 1798227825Stheraven else if (__n > base::__sz()) 1799227825Stheraven { 1800227825Stheraven __n -= base::__sz(); 1801227825Stheraven size_type __ds = 0; 1802227825Stheraven __node_allocator& __na = base::__node_alloc(); 1803232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1804232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1805227825Stheraven __hold->__prev_ = 0; 1806227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_)); 1807227825Stheraven ++__ds; 1808227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1809227825Stheraven iterator __r = iterator(__hold.release(), this); 1810227825Stheraven#else 1811227825Stheraven iterator __r = iterator(__hold.release()); 1812227825Stheraven#endif 1813227825Stheraven iterator __e = __r; 1814227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1815227825Stheraven try 1816227825Stheraven { 1817227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1818227825Stheraven for (--__n; __n != 0; --__n, ++__e, ++__ds) 1819227825Stheraven { 1820227825Stheraven __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1821227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_)); 1822227825Stheraven __e.__ptr_->__next_ = __hold.get(); 1823227825Stheraven __hold->__prev_ = __e.__ptr_; 1824227825Stheraven __hold.release(); 1825227825Stheraven } 1826227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1827227825Stheraven } 1828227825Stheraven catch (...) 1829227825Stheraven { 1830227825Stheraven while (true) 1831227825Stheraven { 1832227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1833227825Stheraven __node_pointer __prev = __e.__ptr_->__prev_; 1834227825Stheraven __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); 1835227825Stheraven if (__prev == 0) 1836227825Stheraven break; 1837227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1838227825Stheraven __e = iterator(__prev, this); 1839227825Stheraven#else 1840227825Stheraven __e = iterator(__prev); 1841227825Stheraven#endif 1842227825Stheraven } 1843227825Stheraven throw; 1844227825Stheraven } 1845227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1846278724Sdim __link_nodes_at_back(__r.__ptr_, __e.__ptr_); 1847227825Stheraven base::__sz() += __ds; 1848227825Stheraven } 1849227825Stheraven} 1850227825Stheraven 1851227825Stheraventemplate <class _Tp, class _Alloc> 1852227825Stheravenvoid 1853227825Stheravenlist<_Tp, _Alloc>::resize(size_type __n, const value_type& __x) 1854227825Stheraven{ 1855227825Stheraven if (__n < base::__sz()) 1856227825Stheraven erase(__iterator(__n), end()); 1857227825Stheraven else if (__n > base::__sz()) 1858227825Stheraven { 1859227825Stheraven __n -= base::__sz(); 1860227825Stheraven size_type __ds = 0; 1861227825Stheraven __node_allocator& __na = base::__node_alloc(); 1862232950Stheraven typedef __allocator_destructor<__node_allocator> _Dp; 1863232950Stheraven unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1)); 1864227825Stheraven __hold->__prev_ = 0; 1865227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1866227825Stheraven ++__ds; 1867227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1868227825Stheraven iterator __r = iterator(__hold.release(), this); 1869227825Stheraven#else 1870227825Stheraven iterator __r = iterator(__hold.release()); 1871227825Stheraven#endif 1872227825Stheraven iterator __e = __r; 1873227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1874227825Stheraven try 1875227825Stheraven { 1876227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1877227825Stheraven for (--__n; __n != 0; --__n, ++__e, ++__ds) 1878227825Stheraven { 1879227825Stheraven __hold.reset(__node_alloc_traits::allocate(__na, 1)); 1880227825Stheraven __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x); 1881227825Stheraven __e.__ptr_->__next_ = __hold.get(); 1882227825Stheraven __hold->__prev_ = __e.__ptr_; 1883227825Stheraven __hold.release(); 1884227825Stheraven } 1885227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1886227825Stheraven } 1887227825Stheraven catch (...) 1888227825Stheraven { 1889227825Stheraven while (true) 1890227825Stheraven { 1891227825Stheraven __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e)); 1892227825Stheraven __node_pointer __prev = __e.__ptr_->__prev_; 1893227825Stheraven __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); 1894227825Stheraven if (__prev == 0) 1895227825Stheraven break; 1896227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1897227825Stheraven __e = iterator(__prev, this); 1898227825Stheraven#else 1899227825Stheraven __e = iterator(__prev); 1900227825Stheraven#endif 1901227825Stheraven } 1902227825Stheraven throw; 1903227825Stheraven } 1904227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1905253159Stheraven __link_nodes(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>:: 1906253159Stheraven pointer_to(base::__end_)), __r.__ptr_, __e.__ptr_); 1907227825Stheraven base::__sz() += __ds; 1908227825Stheraven } 1909227825Stheraven} 1910227825Stheraven 1911227825Stheraventemplate <class _Tp, class _Alloc> 1912227825Stheravenvoid 1913227825Stheravenlist<_Tp, _Alloc>::splice(const_iterator __p, list& __c) 1914227825Stheraven{ 1915227825Stheraven _LIBCPP_ASSERT(this != &__c, 1916227825Stheraven "list::splice(iterator, list) called with this == &list"); 1917227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1918227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1919227825Stheraven "list::splice(iterator, list) called with an iterator not" 1920227825Stheraven " referring to this list"); 1921227825Stheraven#endif 1922227825Stheraven if (!__c.empty()) 1923227825Stheraven { 1924253159Stheraven __node_pointer __f = __c.__end_.__next_; 1925253159Stheraven __node_pointer __l = __c.__end_.__prev_; 1926227825Stheraven base::__unlink_nodes(__f, __l); 1927253159Stheraven __link_nodes(__p.__ptr_, __f, __l); 1928227825Stheraven base::__sz() += __c.__sz(); 1929227825Stheraven __c.__sz() = 0; 1930227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1931227825Stheraven __libcpp_db* __db = __get_db(); 1932227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 1933227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 1934227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 1935227825Stheraven { 1936227825Stheraven --__p; 1937227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 1938253159Stheraven if (__i->__ptr_ != static_cast<__node_pointer>( 1939253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(__c.__end_))) 1940227825Stheraven { 1941227825Stheraven __cn1->__add(*__p); 1942227825Stheraven (*__p)->__c_ = __cn1; 1943227825Stheraven if (--__cn2->end_ != __p) 1944227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 1945227825Stheraven } 1946227825Stheraven } 1947227825Stheraven __db->unlock(); 1948227825Stheraven#endif 1949227825Stheraven } 1950227825Stheraven} 1951227825Stheraven 1952227825Stheraventemplate <class _Tp, class _Alloc> 1953227825Stheravenvoid 1954227825Stheravenlist<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i) 1955227825Stheraven{ 1956227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1957227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1958227825Stheraven "list::splice(iterator, list, iterator) called with first iterator not" 1959227825Stheraven " referring to this list"); 1960227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__i) == &__c, 1961227825Stheraven "list::splice(iterator, list, iterator) called with second iterator not" 1962227825Stheraven " referring to list argument"); 1963227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(&__i), 1964227825Stheraven "list::splice(iterator, list, iterator) called with second iterator not" 1965227825Stheraven " derefereceable"); 1966227825Stheraven#endif 1967227825Stheraven if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_) 1968227825Stheraven { 1969253159Stheraven __node_pointer __f = __i.__ptr_; 1970227825Stheraven base::__unlink_nodes(__f, __f); 1971253159Stheraven __link_nodes(__p.__ptr_, __f, __f); 1972227825Stheraven --__c.__sz(); 1973227825Stheraven ++base::__sz(); 1974227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1975227825Stheraven __libcpp_db* __db = __get_db(); 1976227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 1977227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 1978227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 1979227825Stheraven { 1980227825Stheraven --__p; 1981227825Stheraven iterator* __j = static_cast<iterator*>((*__p)->__i_); 1982253159Stheraven if (__j->__ptr_ == __f) 1983227825Stheraven { 1984227825Stheraven __cn1->__add(*__p); 1985227825Stheraven (*__p)->__c_ = __cn1; 1986227825Stheraven if (--__cn2->end_ != __p) 1987227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 1988227825Stheraven } 1989227825Stheraven } 1990227825Stheraven __db->unlock(); 1991227825Stheraven#endif 1992227825Stheraven } 1993227825Stheraven} 1994227825Stheraven 1995227825Stheraventemplate <class _Tp, class _Alloc> 1996227825Stheravenvoid 1997227825Stheravenlist<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l) 1998227825Stheraven{ 1999227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 2000227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2001227825Stheraven "list::splice(iterator, list, iterator, iterator) called with first iterator not" 2002227825Stheraven " referring to this list"); 2003227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == &__c, 2004227825Stheraven "list::splice(iterator, list, iterator, iterator) called with second iterator not" 2005227825Stheraven " referring to list argument"); 2006227825Stheraven if (this == &__c) 2007227825Stheraven { 2008227825Stheraven for (const_iterator __i = __f; __i != __l; ++__i) 2009227825Stheraven _LIBCPP_ASSERT(__i != __p, 2010227825Stheraven "list::splice(iterator, list, iterator, iterator)" 2011227825Stheraven " called with the first iterator within the range" 2012227825Stheraven " of the second and third iterators"); 2013227825Stheraven } 2014227825Stheraven#endif 2015227825Stheraven if (__f != __l) 2016227825Stheraven { 2017227825Stheraven if (this != &__c) 2018227825Stheraven { 2019227825Stheraven size_type __s = _VSTD::distance(__f, __l); 2020227825Stheraven __c.__sz() -= __s; 2021227825Stheraven base::__sz() += __s; 2022227825Stheraven } 2023253159Stheraven __node_pointer __first = __f.__ptr_; 2024227825Stheraven --__l; 2025253159Stheraven __node_pointer __last = __l.__ptr_; 2026227825Stheraven base::__unlink_nodes(__first, __last); 2027253159Stheraven __link_nodes(__p.__ptr_, __first, __last); 2028227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 2029227825Stheraven __libcpp_db* __db = __get_db(); 2030227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 2031227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 2032227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 2033227825Stheraven { 2034227825Stheraven --__p; 2035227825Stheraven iterator* __j = static_cast<iterator*>((*__p)->__i_); 2036253159Stheraven for (__node_pointer __k = __f.__ptr_; 2037227825Stheraven __k != __l.__ptr_; __k = __k->__next_) 2038227825Stheraven { 2039227825Stheraven if (__j->__ptr_ == __k) 2040227825Stheraven { 2041227825Stheraven __cn1->__add(*__p); 2042227825Stheraven (*__p)->__c_ = __cn1; 2043227825Stheraven if (--__cn2->end_ != __p) 2044227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 2045227825Stheraven } 2046227825Stheraven } 2047227825Stheraven } 2048227825Stheraven __db->unlock(); 2049227825Stheraven#endif 2050227825Stheraven } 2051227825Stheraven} 2052227825Stheraven 2053227825Stheraventemplate <class _Tp, class _Alloc> 2054227825Stheravenvoid 2055227825Stheravenlist<_Tp, _Alloc>::remove(const value_type& __x) 2056227825Stheraven{ 2057278724Sdim list<_Tp, _Alloc> __deleted_nodes; // collect the nodes we're removing 2058278724Sdim for (const_iterator __i = begin(), __e = end(); __i != __e;) 2059227825Stheraven { 2060227825Stheraven if (*__i == __x) 2061227825Stheraven { 2062278724Sdim const_iterator __j = _VSTD::next(__i); 2063227825Stheraven for (; __j != __e && *__j == __x; ++__j) 2064227825Stheraven ; 2065278724Sdim __deleted_nodes.splice(__deleted_nodes.end(), *this, __i, __j); 2066278724Sdim __i = __j; 2067269836Sdim if (__i != __e) 2068278724Sdim ++__i; 2069227825Stheraven } 2070227825Stheraven else 2071227825Stheraven ++__i; 2072227825Stheraven } 2073227825Stheraven} 2074227825Stheraven 2075227825Stheraventemplate <class _Tp, class _Alloc> 2076227825Stheraventemplate <class _Pred> 2077227825Stheravenvoid 2078227825Stheravenlist<_Tp, _Alloc>::remove_if(_Pred __pred) 2079227825Stheraven{ 2080227825Stheraven for (iterator __i = begin(), __e = end(); __i != __e;) 2081227825Stheraven { 2082227825Stheraven if (__pred(*__i)) 2083227825Stheraven { 2084227825Stheraven iterator __j = _VSTD::next(__i); 2085227825Stheraven for (; __j != __e && __pred(*__j); ++__j) 2086227825Stheraven ; 2087227825Stheraven __i = erase(__i, __j); 2088269836Sdim if (__i != __e) 2089278724Sdim ++__i; 2090227825Stheraven } 2091227825Stheraven else 2092227825Stheraven ++__i; 2093227825Stheraven } 2094227825Stheraven} 2095227825Stheraven 2096227825Stheraventemplate <class _Tp, class _Alloc> 2097227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2098227825Stheravenvoid 2099227825Stheravenlist<_Tp, _Alloc>::unique() 2100227825Stheraven{ 2101227825Stheraven unique(__equal_to<value_type>()); 2102227825Stheraven} 2103227825Stheraven 2104227825Stheraventemplate <class _Tp, class _Alloc> 2105227825Stheraventemplate <class _BinaryPred> 2106227825Stheravenvoid 2107227825Stheravenlist<_Tp, _Alloc>::unique(_BinaryPred __binary_pred) 2108227825Stheraven{ 2109227825Stheraven for (iterator __i = begin(), __e = end(); __i != __e;) 2110227825Stheraven { 2111227825Stheraven iterator __j = _VSTD::next(__i); 2112227825Stheraven for (; __j != __e && __binary_pred(*__i, *__j); ++__j) 2113227825Stheraven ; 2114227825Stheraven if (++__i != __j) 2115227825Stheraven __i = erase(__i, __j); 2116227825Stheraven } 2117227825Stheraven} 2118227825Stheraven 2119227825Stheraventemplate <class _Tp, class _Alloc> 2120227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2121227825Stheravenvoid 2122227825Stheravenlist<_Tp, _Alloc>::merge(list& __c) 2123227825Stheraven{ 2124227825Stheraven merge(__c, __less<value_type>()); 2125227825Stheraven} 2126227825Stheraven 2127227825Stheraventemplate <class _Tp, class _Alloc> 2128227825Stheraventemplate <class _Comp> 2129227825Stheravenvoid 2130227825Stheravenlist<_Tp, _Alloc>::merge(list& __c, _Comp __comp) 2131227825Stheraven{ 2132227825Stheraven if (this != &__c) 2133227825Stheraven { 2134227825Stheraven iterator __f1 = begin(); 2135227825Stheraven iterator __e1 = end(); 2136227825Stheraven iterator __f2 = __c.begin(); 2137227825Stheraven iterator __e2 = __c.end(); 2138227825Stheraven while (__f1 != __e1 && __f2 != __e2) 2139227825Stheraven { 2140227825Stheraven if (__comp(*__f2, *__f1)) 2141227825Stheraven { 2142227825Stheraven size_type __ds = 1; 2143227825Stheraven iterator __m2 = _VSTD::next(__f2); 2144227825Stheraven for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, ++__ds) 2145227825Stheraven ; 2146227825Stheraven base::__sz() += __ds; 2147227825Stheraven __c.__sz() -= __ds; 2148253159Stheraven __node_pointer __f = __f2.__ptr_; 2149253159Stheraven __node_pointer __l = __m2.__ptr_->__prev_; 2150227825Stheraven __f2 = __m2; 2151227825Stheraven base::__unlink_nodes(__f, __l); 2152227825Stheraven __m2 = _VSTD::next(__f1); 2153253159Stheraven __link_nodes(__f1.__ptr_, __f, __l); 2154227825Stheraven __f1 = __m2; 2155227825Stheraven } 2156227825Stheraven else 2157227825Stheraven ++__f1; 2158227825Stheraven } 2159227825Stheraven splice(__e1, __c); 2160227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 2161227825Stheraven __libcpp_db* __db = __get_db(); 2162227825Stheraven __c_node* __cn1 = __db->__find_c_and_lock(this); 2163227825Stheraven __c_node* __cn2 = __db->__find_c(&__c); 2164227825Stheraven for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;) 2165227825Stheraven { 2166227825Stheraven --__p; 2167227825Stheraven iterator* __i = static_cast<iterator*>((*__p)->__i_); 2168253159Stheraven if (__i->__ptr_ != static_cast<__node_pointer>( 2169253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(__c.__end_))) 2170227825Stheraven { 2171227825Stheraven __cn1->__add(*__p); 2172227825Stheraven (*__p)->__c_ = __cn1; 2173227825Stheraven if (--__cn2->end_ != __p) 2174227825Stheraven memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*)); 2175227825Stheraven } 2176227825Stheraven } 2177227825Stheraven __db->unlock(); 2178227825Stheraven#endif 2179227825Stheraven } 2180227825Stheraven} 2181227825Stheraven 2182227825Stheraventemplate <class _Tp, class _Alloc> 2183227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2184227825Stheravenvoid 2185227825Stheravenlist<_Tp, _Alloc>::sort() 2186227825Stheraven{ 2187227825Stheraven sort(__less<value_type>()); 2188227825Stheraven} 2189227825Stheraven 2190227825Stheraventemplate <class _Tp, class _Alloc> 2191227825Stheraventemplate <class _Comp> 2192227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2193227825Stheravenvoid 2194227825Stheravenlist<_Tp, _Alloc>::sort(_Comp __comp) 2195227825Stheraven{ 2196227825Stheraven __sort(begin(), end(), base::__sz(), __comp); 2197227825Stheraven} 2198227825Stheraven 2199227825Stheraventemplate <class _Tp, class _Alloc> 2200227825Stheraventemplate <class _Comp> 2201227825Stheraventypename list<_Tp, _Alloc>::iterator 2202227825Stheravenlist<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp) 2203227825Stheraven{ 2204227825Stheraven switch (__n) 2205227825Stheraven { 2206227825Stheraven case 0: 2207227825Stheraven case 1: 2208227825Stheraven return __f1; 2209227825Stheraven case 2: 2210227825Stheraven if (__comp(*--__e2, *__f1)) 2211227825Stheraven { 2212253159Stheraven __node_pointer __f = __e2.__ptr_; 2213227825Stheraven base::__unlink_nodes(__f, __f); 2214253159Stheraven __link_nodes(__f1.__ptr_, __f, __f); 2215227825Stheraven return __e2; 2216227825Stheraven } 2217227825Stheraven return __f1; 2218227825Stheraven } 2219227825Stheraven size_type __n2 = __n / 2; 2220227825Stheraven iterator __e1 = _VSTD::next(__f1, __n2); 2221227825Stheraven iterator __r = __f1 = __sort(__f1, __e1, __n2, __comp); 2222227825Stheraven iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp); 2223227825Stheraven if (__comp(*__f2, *__f1)) 2224227825Stheraven { 2225227825Stheraven iterator __m2 = _VSTD::next(__f2); 2226227825Stheraven for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2) 2227227825Stheraven ; 2228253159Stheraven __node_pointer __f = __f2.__ptr_; 2229253159Stheraven __node_pointer __l = __m2.__ptr_->__prev_; 2230227825Stheraven __r = __f2; 2231227825Stheraven __e1 = __f2 = __m2; 2232227825Stheraven base::__unlink_nodes(__f, __l); 2233227825Stheraven __m2 = _VSTD::next(__f1); 2234253159Stheraven __link_nodes(__f1.__ptr_, __f, __l); 2235227825Stheraven __f1 = __m2; 2236227825Stheraven } 2237227825Stheraven else 2238227825Stheraven ++__f1; 2239227825Stheraven while (__f1 != __e1 && __f2 != __e2) 2240227825Stheraven { 2241227825Stheraven if (__comp(*__f2, *__f1)) 2242227825Stheraven { 2243227825Stheraven iterator __m2 = _VSTD::next(__f2); 2244227825Stheraven for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2) 2245227825Stheraven ; 2246253159Stheraven __node_pointer __f = __f2.__ptr_; 2247253159Stheraven __node_pointer __l = __m2.__ptr_->__prev_; 2248227825Stheraven if (__e1 == __f2) 2249227825Stheraven __e1 = __m2; 2250227825Stheraven __f2 = __m2; 2251227825Stheraven base::__unlink_nodes(__f, __l); 2252227825Stheraven __m2 = _VSTD::next(__f1); 2253253159Stheraven __link_nodes(__f1.__ptr_, __f, __l); 2254227825Stheraven __f1 = __m2; 2255227825Stheraven } 2256227825Stheraven else 2257227825Stheraven ++__f1; 2258227825Stheraven } 2259227825Stheraven return __r; 2260227825Stheraven} 2261227825Stheraven 2262227825Stheraventemplate <class _Tp, class _Alloc> 2263227825Stheravenvoid 2264227825Stheravenlist<_Tp, _Alloc>::reverse() _NOEXCEPT 2265227825Stheraven{ 2266227825Stheraven if (base::__sz() > 1) 2267227825Stheraven { 2268227825Stheraven iterator __e = end(); 2269227825Stheraven for (iterator __i = begin(); __i.__ptr_ != __e.__ptr_;) 2270227825Stheraven { 2271227825Stheraven _VSTD::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_); 2272227825Stheraven __i.__ptr_ = __i.__ptr_->__prev_; 2273227825Stheraven } 2274227825Stheraven _VSTD::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_); 2275227825Stheraven } 2276227825Stheraven} 2277227825Stheraven 2278227825Stheraventemplate <class _Tp, class _Alloc> 2279227825Stheravenbool 2280227825Stheravenlist<_Tp, _Alloc>::__invariants() const 2281227825Stheraven{ 2282227825Stheraven return size() == _VSTD::distance(begin(), end()); 2283227825Stheraven} 2284227825Stheraven 2285227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 2286227825Stheraven 2287227825Stheraventemplate <class _Tp, class _Alloc> 2288227825Stheravenbool 2289227825Stheravenlist<_Tp, _Alloc>::__dereferenceable(const const_iterator* __i) const 2290227825Stheraven{ 2291253159Stheraven return __i->__ptr_ != static_cast<__node_pointer>( 2292253159Stheraven pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(this->__end_))); 2293227825Stheraven} 2294227825Stheraven 2295227825Stheraventemplate <class _Tp, class _Alloc> 2296227825Stheravenbool 2297227825Stheravenlist<_Tp, _Alloc>::__decrementable(const const_iterator* __i) const 2298227825Stheraven{ 2299227825Stheraven return !empty() && __i->__ptr_ != base::__end_.__next_; 2300227825Stheraven} 2301227825Stheraven 2302227825Stheraventemplate <class _Tp, class _Alloc> 2303227825Stheravenbool 2304227825Stheravenlist<_Tp, _Alloc>::__addable(const const_iterator* __i, ptrdiff_t __n) const 2305227825Stheraven{ 2306227825Stheraven return false; 2307227825Stheraven} 2308227825Stheraven 2309227825Stheraventemplate <class _Tp, class _Alloc> 2310227825Stheravenbool 2311227825Stheravenlist<_Tp, _Alloc>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const 2312227825Stheraven{ 2313227825Stheraven return false; 2314227825Stheraven} 2315227825Stheraven 2316227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 2317227825Stheraven 2318227825Stheraventemplate <class _Tp, class _Alloc> 2319227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2320227825Stheravenbool 2321227825Stheravenoperator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2322227825Stheraven{ 2323227825Stheraven return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 2324227825Stheraven} 2325227825Stheraven 2326227825Stheraventemplate <class _Tp, class _Alloc> 2327227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2328227825Stheravenbool 2329227825Stheravenoperator< (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2330227825Stheraven{ 2331227825Stheraven return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2332227825Stheraven} 2333227825Stheraven 2334227825Stheraventemplate <class _Tp, class _Alloc> 2335227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2336227825Stheravenbool 2337227825Stheravenoperator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2338227825Stheraven{ 2339227825Stheraven return !(__x == __y); 2340227825Stheraven} 2341227825Stheraven 2342227825Stheraventemplate <class _Tp, class _Alloc> 2343227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2344227825Stheravenbool 2345227825Stheravenoperator> (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2346227825Stheraven{ 2347227825Stheraven return __y < __x; 2348227825Stheraven} 2349227825Stheraven 2350227825Stheraventemplate <class _Tp, class _Alloc> 2351227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2352227825Stheravenbool 2353227825Stheravenoperator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2354227825Stheraven{ 2355227825Stheraven return !(__x < __y); 2356227825Stheraven} 2357227825Stheraven 2358227825Stheraventemplate <class _Tp, class _Alloc> 2359227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2360227825Stheravenbool 2361227825Stheravenoperator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) 2362227825Stheraven{ 2363227825Stheraven return !(__y < __x); 2364227825Stheraven} 2365227825Stheraven 2366227825Stheraventemplate <class _Tp, class _Alloc> 2367227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2368227825Stheravenvoid 2369227825Stheravenswap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) 2370227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2371227825Stheraven{ 2372227825Stheraven __x.swap(__y); 2373227825Stheraven} 2374227825Stheraven 2375227825Stheraven_LIBCPP_END_NAMESPACE_STD 2376227825Stheraven 2377227825Stheraven#endif // _LIBCPP_LIST 2378