codekingpro/portable-devtools
114k
1// -*- C++ -*-2//===---------------------------- list ------------------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCUDACXX_LIST11#define _LIBCUDACXX_LIST12 13/*14 list synopsis15 16namespace std17{18 19template <class T, class Alloc = allocator<T> >20class list21{22public:23 24 // types:25 typedef T value_type;26 typedef Alloc allocator_type;27 typedef typename allocator_type::reference reference;28 typedef typename allocator_type::const_reference const_reference;29 typedef typename allocator_type::pointer pointer;30 typedef typename allocator_type::const_pointer const_pointer;31 typedef implementation-defined iterator;32 typedef implementation-defined const_iterator;33 typedef implementation-defined size_type;34 typedef implementation-defined difference_type;35 typedef reverse_iterator<iterator> reverse_iterator;36 typedef reverse_iterator<const_iterator> const_reverse_iterator;37 38 list()39 noexcept(is_nothrow_default_constructible<allocator_type>::value);40 explicit list(const allocator_type& a);41 explicit list(size_type n);42 explicit list(size_type n, const allocator_type& a); // C++1443 list(size_type n, const value_type& value);44 list(size_type n, const value_type& value, const allocator_type& a);45 template <class Iter>46 list(Iter first, Iter last);47 template <class Iter>48 list(Iter first, Iter last, const allocator_type& a);49 list(const list& x);50 list(const list&, const allocator_type& a);51 list(list&& x)52 noexcept(is_nothrow_move_constructible<allocator_type>::value);53 list(list&&, const allocator_type& a);54 list(initializer_list<value_type>);55 list(initializer_list<value_type>, const allocator_type& a);56 57 ~list();58 59 list& operator=(const list& x);60 list& operator=(list&& x)61 noexcept(62 allocator_type::propagate_on_container_move_assignment::value &&63 is_nothrow_move_assignable<allocator_type>::value);64 list& operator=(initializer_list<value_type>);65 template <class Iter>66 void assign(Iter first, Iter last);67 void assign(size_type n, const value_type& t);68 void assign(initializer_list<value_type>);69 70 allocator_type get_allocator() const noexcept;71 72 iterator begin() noexcept;73 const_iterator begin() const noexcept;74 iterator end() noexcept;75 const_iterator end() const noexcept;76 reverse_iterator rbegin() noexcept;77 const_reverse_iterator rbegin() const noexcept;78 reverse_iterator rend() noexcept;79 const_reverse_iterator rend() const noexcept;80 const_iterator cbegin() const noexcept;81 const_iterator cend() const noexcept;82 const_reverse_iterator crbegin() const noexcept;83 const_reverse_iterator crend() const noexcept;84 85 reference front();86 const_reference front() const;87 reference back();88 const_reference back() const;89 90 bool empty() const noexcept;91 size_type size() const noexcept;92 size_type max_size() const noexcept;93 94 template <class... Args>95 reference emplace_front(Args&&... args); // reference in C++1796 void pop_front();97 template <class... Args>98 reference emplace_back(Args&&... args); // reference in C++1799 void pop_back();100 void push_front(const value_type& x);101 void push_front(value_type&& x);102 void push_back(const value_type& x);103 void push_back(value_type&& x);104 template <class... Args>105 iterator emplace(const_iterator position, Args&&... args);106 iterator insert(const_iterator position, const value_type& x);107 iterator insert(const_iterator position, value_type&& x);108 iterator insert(const_iterator position, size_type n, const value_type& x);109 template <class Iter>110 iterator insert(const_iterator position, Iter first, Iter last);111 iterator insert(const_iterator position, initializer_list<value_type> il);112 113 iterator erase(const_iterator position);114 iterator erase(const_iterator position, const_iterator last);115 116 void resize(size_type sz);117 void resize(size_type sz, const value_type& c);118 119 void swap(list&)120 noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17121 void clear() noexcept;122 123 void splice(const_iterator position, list& x);124 void splice(const_iterator position, list&& x);125 void splice(const_iterator position, list& x, const_iterator i);126 void splice(const_iterator position, list&& x, const_iterator i);127 void splice(const_iterator position, list& x, const_iterator first,128 const_iterator last);129 void splice(const_iterator position, list&& x, const_iterator first,130 const_iterator last);131 132 size_type remove(const value_type& value); // void before C++20133 template <class Pred>134 size_type remove_if(Pred pred); // void before C++20135 size_type unique(); // void before C++20136 template <class BinaryPredicate>137 size_type unique(BinaryPredicate binary_pred); // void before C++20138 void merge(list& x);139 void merge(list&& x);140 template <class Compare>141 void merge(list& x, Compare comp);142 template <class Compare>143 void merge(list&& x, Compare comp);144 void sort();145 template <class Compare>146 void sort(Compare comp);147 void reverse() noexcept;148};149 150 151template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>152 list(InputIterator, InputIterator, Allocator = Allocator())153 -> list<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17154 155template <class T, class Alloc>156 bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y);157template <class T, class Alloc>158 bool operator< (const list<T,Alloc>& x, const list<T,Alloc>& y);159template <class T, class Alloc>160 bool operator!=(const list<T,Alloc>& x, const list<T,Alloc>& y);161template <class T, class Alloc>162 bool operator> (const list<T,Alloc>& x, const list<T,Alloc>& y);163template <class T, class Alloc>164 bool operator>=(const list<T,Alloc>& x, const list<T,Alloc>& y);165template <class T, class Alloc>166 bool operator<=(const list<T,Alloc>& x, const list<T,Alloc>& y);167 168template <class T, class Alloc>169 void swap(list<T,Alloc>& x, list<T,Alloc>& y)170 noexcept(noexcept(x.swap(y)));171 172template <class T, class Allocator, class U>173 void erase(list<T, Allocator>& c, const U& value); // C++20174template <class T, class Allocator, class Predicate>175 void erase_if(list<T, Allocator>& c, Predicate pred); // C++20176 177} // std178 179*/180 181#include <__config>182 183#include <memory>184#include <limits>185#include <initializer_list>186#include <iterator>187#include <algorithm>188#include <type_traits>189#include <version>190 191#include <__debug>192 193#if defined(_CCCL_IMPLICIT_SYSTEM_HEADER_GCC)194# pragma GCC system_header195#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_CLANG)196# pragma clang system_header197#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_MSVC)198# pragma system_header199#endif // no system header200 201_LIBCUDACXX_PUSH_MACROS202#include <__undef_macros>203 204 205_LIBCUDACXX_BEGIN_NAMESPACE_STD206 207template <class _Tp, class _VoidPtr> struct __list_node;208template <class _Tp, class _VoidPtr> struct __list_node_base;209 210template <class _Tp, class _VoidPtr>211struct __list_node_pointer_traits {212 typedef typename __rebind_pointer<_VoidPtr, __list_node<_Tp, _VoidPtr> >::type213 __node_pointer;214 typedef typename __rebind_pointer<_VoidPtr, __list_node_base<_Tp, _VoidPtr> >::type215 __base_pointer;216 217#if defined(_LIBCUDACXX_ABI_LIST_REMOVE_NODE_POINTER_UB)218 typedef __base_pointer __link_pointer;219#else220 typedef typename conditional<221 is_pointer<_VoidPtr>::value,222 __base_pointer,223 __node_pointer224 >::type __link_pointer;225#endif226 227 typedef typename conditional<228 is_same<__link_pointer, __node_pointer>::value,229 __base_pointer,230 __node_pointer231 >::type __non_link_pointer;232 233 static _LIBCUDACXX_INLINE_VISIBILITY234 __link_pointer __unsafe_link_pointer_cast(__link_pointer __p) {235 return __p;236 }237 238 static _LIBCUDACXX_INLINE_VISIBILITY239 __link_pointer __unsafe_link_pointer_cast(__non_link_pointer __p) {240 return static_cast<__link_pointer>(static_cast<_VoidPtr>(__p));241 }242 243};244 245template <class _Tp, class _VoidPtr>246struct __list_node_base247{248 typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;249 typedef typename _NodeTraits::__node_pointer __node_pointer;250 typedef typename _NodeTraits::__base_pointer __base_pointer;251 typedef typename _NodeTraits::__link_pointer __link_pointer;252 253 __link_pointer __prev_;254 __link_pointer __next_;255 256 _LIBCUDACXX_INLINE_VISIBILITY257 __list_node_base() : __prev_(_NodeTraits::__unsafe_link_pointer_cast(__self())),258 __next_(_NodeTraits::__unsafe_link_pointer_cast(__self())) {}259 260 _LIBCUDACXX_INLINE_VISIBILITY261 __base_pointer __self() {262 return pointer_traits<__base_pointer>::pointer_to(*this);263 }264 265 _LIBCUDACXX_INLINE_VISIBILITY266 __node_pointer __as_node() {267 return static_cast<__node_pointer>(__self());268 }269};270 271template <class _Tp, class _VoidPtr>272struct __list_node273 : public __list_node_base<_Tp, _VoidPtr>274{275 _Tp __value_;276 277 typedef __list_node_base<_Tp, _VoidPtr> __base;278 typedef typename __base::__link_pointer __link_pointer;279 280 _LIBCUDACXX_INLINE_VISIBILITY281 __link_pointer __as_link() {282 return static_cast<__link_pointer>(__base::__self());283 }284};285 286template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCUDACXX_TEMPLATE_VIS list;287template <class _Tp, class _Alloc> class __list_imp;288template <class _Tp, class _VoidPtr> class _LIBCUDACXX_TEMPLATE_VIS __list_const_iterator;289 290template <class _Tp, class _VoidPtr>291class _LIBCUDACXX_TEMPLATE_VIS __list_iterator292{293 typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;294 typedef typename _NodeTraits::__link_pointer __link_pointer;295 296 __link_pointer __ptr_;297 298#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE299 _LIBCUDACXX_INLINE_VISIBILITY300 explicit __list_iterator(__link_pointer __p, const void* __c) noexcept301 : __ptr_(__p)302 {303 __get_db()->__insert_ic(this, __c);304 }305#else306 _LIBCUDACXX_INLINE_VISIBILITY307 explicit __list_iterator(__link_pointer __p) noexcept : __ptr_(__p) {}308#endif309 310 311 312 template<class, class> friend class list;313 template<class, class> friend class __list_imp;314 template<class, class> friend class __list_const_iterator;315public:316 typedef bidirectional_iterator_tag iterator_category;317 typedef _Tp value_type;318 typedef value_type& reference;319 typedef typename __rebind_pointer<_VoidPtr, value_type>::type pointer;320 typedef typename pointer_traits<pointer>::difference_type difference_type;321 322 _LIBCUDACXX_INLINE_VISIBILITY323 __list_iterator() noexcept : __ptr_(nullptr)324 {325#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE326 __get_db()->__insert_i(this);327#endif328 }329 330#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE331 332 _LIBCUDACXX_INLINE_VISIBILITY333 __list_iterator(const __list_iterator& __p)334 : __ptr_(__p.__ptr_)335 {336 __get_db()->__iterator_copy(this, &__p);337 }338 339 _LIBCUDACXX_INLINE_VISIBILITY340 ~__list_iterator()341 {342 __get_db()->__erase_i(this);343 }344 345 _LIBCUDACXX_INLINE_VISIBILITY346 __list_iterator& operator=(const __list_iterator& __p)347 {348 if (this != &__p)349 {350 __get_db()->__iterator_copy(this, &__p);351 __ptr_ = __p.__ptr_;352 }353 return *this;354 }355 356#endif // _LIBCUDACXX_ENABLE_DEBUG_MODE357 358 _LIBCUDACXX_INLINE_VISIBILITY359 reference operator*() const360 {361#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE362 _LIBCUDACXX_ASSERT(__get_const_db()->__dereferenceable(this),363 "Attempted to dereference a non-dereferenceable list::iterator");364#endif365 return __ptr_->__as_node()->__value_;366 }367 _LIBCUDACXX_INLINE_VISIBILITY368 pointer operator->() const369 {370#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE371 _LIBCUDACXX_ASSERT(__get_const_db()->__dereferenceable(this),372 "Attempted to dereference a non-dereferenceable list::iterator");373#endif374 return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__value_);375 }376 377 _LIBCUDACXX_INLINE_VISIBILITY378 __list_iterator& operator++()379 {380#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE381 _LIBCUDACXX_ASSERT(__get_const_db()->__dereferenceable(this),382 "Attempted to increment non-incrementable list::iterator");383#endif384 __ptr_ = __ptr_->__next_;385 return *this;386 }387 _LIBCUDACXX_INLINE_VISIBILITY388 __list_iterator operator++(int) {__list_iterator __t(*this); ++(*this); return __t;}389 390 _LIBCUDACXX_INLINE_VISIBILITY391 __list_iterator& operator--()392 {393#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE394 _LIBCUDACXX_ASSERT(__get_const_db()->__decrementable(this),395 "Attempted to decrement non-decrementable list::iterator");396#endif397 __ptr_ = __ptr_->__prev_;398 return *this;399 }400 _LIBCUDACXX_INLINE_VISIBILITY401 __list_iterator operator--(int) {__list_iterator __t(*this); --(*this); return __t;}402 403 friend _LIBCUDACXX_INLINE_VISIBILITY404 bool operator==(const __list_iterator& __x, const __list_iterator& __y)405 {406 return __x.__ptr_ == __y.__ptr_;407 }408 friend _LIBCUDACXX_INLINE_VISIBILITY409 bool operator!=(const __list_iterator& __x, const __list_iterator& __y)410 {return !(__x == __y);}411};412 413template <class _Tp, class _VoidPtr>414class _LIBCUDACXX_TEMPLATE_VIS __list_const_iterator415{416 typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;417 typedef typename _NodeTraits::__link_pointer __link_pointer;418 419 __link_pointer __ptr_;420 421#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE422 _LIBCUDACXX_INLINE_VISIBILITY423 explicit __list_const_iterator(__link_pointer __p, const void* __c) noexcept424 : __ptr_(__p)425 {426 __get_db()->__insert_ic(this, __c);427 }428#else429 _LIBCUDACXX_INLINE_VISIBILITY430 explicit __list_const_iterator(__link_pointer __p) noexcept : __ptr_(__p) {}431#endif432 433 template<class, class> friend class list;434 template<class, class> friend class __list_imp;435public:436 typedef bidirectional_iterator_tag iterator_category;437 typedef _Tp value_type;438 typedef const value_type& reference;439 typedef typename __rebind_pointer<_VoidPtr, const value_type>::type pointer;440 typedef typename pointer_traits<pointer>::difference_type difference_type;441 442 _LIBCUDACXX_INLINE_VISIBILITY443 __list_const_iterator() noexcept : __ptr_(nullptr)444 {445#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE446 __get_db()->__insert_i(this);447#endif448 }449 _LIBCUDACXX_INLINE_VISIBILITY450 __list_const_iterator(const __list_iterator<_Tp, _VoidPtr>& __p) noexcept451 : __ptr_(__p.__ptr_)452 {453#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE454 __get_db()->__iterator_copy(this, &__p);455#endif456 }457 458#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE459 460 _LIBCUDACXX_INLINE_VISIBILITY461 __list_const_iterator(const __list_const_iterator& __p)462 : __ptr_(__p.__ptr_)463 {464 __get_db()->__iterator_copy(this, &__p);465 }466 467 _LIBCUDACXX_INLINE_VISIBILITY468 ~__list_const_iterator()469 {470 __get_db()->__erase_i(this);471 }472 473 _LIBCUDACXX_INLINE_VISIBILITY474 __list_const_iterator& operator=(const __list_const_iterator& __p)475 {476 if (this != &__p)477 {478 __get_db()->__iterator_copy(this, &__p);479 __ptr_ = __p.__ptr_;480 }481 return *this;482 }483 484#endif // _LIBCUDACXX_ENABLE_DEBUG_MODE485 _LIBCUDACXX_INLINE_VISIBILITY486 reference operator*() const487 {488#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE489 _LIBCUDACXX_ASSERT(__get_const_db()->__dereferenceable(this),490 "Attempted to dereference a non-dereferenceable list::const_iterator");491#endif492 return __ptr_->__as_node()->__value_;493 }494 _LIBCUDACXX_INLINE_VISIBILITY495 pointer operator->() const496 {497#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE498 _LIBCUDACXX_ASSERT(__get_const_db()->__dereferenceable(this),499 "Attempted to dereference a non-dereferenceable list::const_iterator");500#endif501 return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__value_);502 }503 504 _LIBCUDACXX_INLINE_VISIBILITY505 __list_const_iterator& operator++()506 {507#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE508 _LIBCUDACXX_ASSERT(__get_const_db()->__dereferenceable(this),509 "Attempted to increment non-incrementable list::const_iterator");510#endif511 __ptr_ = __ptr_->__next_;512 return *this;513 }514 _LIBCUDACXX_INLINE_VISIBILITY515 __list_const_iterator operator++(int) {__list_const_iterator __t(*this); ++(*this); return __t;}516 517 _LIBCUDACXX_INLINE_VISIBILITY518 __list_const_iterator& operator--()519 {520#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE521 _LIBCUDACXX_ASSERT(__get_const_db()->__decrementable(this),522 "Attempted to decrement non-decrementable list::const_iterator");523#endif524 __ptr_ = __ptr_->__prev_;525 return *this;526 }527 _LIBCUDACXX_INLINE_VISIBILITY528 __list_const_iterator operator--(int) {__list_const_iterator __t(*this); --(*this); return __t;}529 530 friend _LIBCUDACXX_INLINE_VISIBILITY531 bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y)532 {533 return __x.__ptr_ == __y.__ptr_;534 }535 friend _LIBCUDACXX_INLINE_VISIBILITY536 bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y)537 {return !(__x == __y);}538};539 540template <class _Tp, class _Alloc>541class __list_imp542{543 __list_imp(const __list_imp&);544 __list_imp& operator=(const __list_imp&);545public:546 typedef _Alloc allocator_type;547 typedef allocator_traits<allocator_type> __alloc_traits;548 typedef typename __alloc_traits::size_type size_type;549protected:550 typedef _Tp value_type;551 typedef typename __alloc_traits::void_pointer __void_pointer;552 typedef __list_iterator<value_type, __void_pointer> iterator;553 typedef __list_const_iterator<value_type, __void_pointer> const_iterator;554 typedef __list_node_base<value_type, __void_pointer> __node_base;555 typedef __list_node<value_type, __void_pointer> __node;556 typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator;557 typedef allocator_traits<__node_allocator> __node_alloc_traits;558 typedef typename __node_alloc_traits::pointer __node_pointer;559 typedef typename __node_alloc_traits::pointer __node_const_pointer;560 typedef __list_node_pointer_traits<value_type, __void_pointer> __node_pointer_traits;561 typedef typename __node_pointer_traits::__link_pointer __link_pointer;562 typedef __link_pointer __link_const_pointer;563 typedef typename __alloc_traits::pointer pointer;564 typedef typename __alloc_traits::const_pointer const_pointer;565 typedef typename __alloc_traits::difference_type difference_type;566 567 typedef typename __rebind_alloc_helper<__alloc_traits, __node_base>::type __node_base_allocator;568 typedef typename allocator_traits<__node_base_allocator>::pointer __node_base_pointer;569 static_assert((!is_same<allocator_type, __node_allocator>::value),570 "internal allocator type must differ from user-specified "571 "type; otherwise overload resolution breaks");572 573 __node_base __end_;574 __compressed_pair<size_type, __node_allocator> __size_alloc_;575 576 _LIBCUDACXX_INLINE_VISIBILITY577 __link_pointer __end_as_link() const noexcept {578 return __node_pointer_traits::__unsafe_link_pointer_cast(579 const_cast<__node_base&>(__end_).__self());580 }581 582 _LIBCUDACXX_INLINE_VISIBILITY583 size_type& __sz() noexcept {return __size_alloc_.first();}584 _LIBCUDACXX_INLINE_VISIBILITY585 const size_type& __sz() const noexcept586 {return __size_alloc_.first();}587 _LIBCUDACXX_INLINE_VISIBILITY588 __node_allocator& __node_alloc() noexcept589 {return __size_alloc_.second();}590 _LIBCUDACXX_INLINE_VISIBILITY591 const __node_allocator& __node_alloc() const noexcept592 {return __size_alloc_.second();}593 594 _LIBCUDACXX_INLINE_VISIBILITY595 size_type __node_alloc_max_size() const noexcept {596 return __node_alloc_traits::max_size(__node_alloc());597 }598 _LIBCUDACXX_INLINE_VISIBILITY599 static void __unlink_nodes(__link_pointer __f, __link_pointer __l) noexcept;600 601 _LIBCUDACXX_INLINE_VISIBILITY602 __list_imp()603 noexcept(is_nothrow_default_constructible<__node_allocator>::value);604 _LIBCUDACXX_INLINE_VISIBILITY605 __list_imp(const allocator_type& __a);606 _LIBCUDACXX_INLINE_VISIBILITY607 __list_imp(const __node_allocator& __a);608 __list_imp(__node_allocator&& __a) noexcept;609 ~__list_imp();610 void clear() noexcept;611 _LIBCUDACXX_INLINE_VISIBILITY612 bool empty() const noexcept {return __sz() == 0;}613 614 _LIBCUDACXX_INLINE_VISIBILITY615 iterator begin() noexcept616 {617#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE618 return iterator(__end_.__next_, this);619#else620 return iterator(__end_.__next_);621#endif622 }623 _LIBCUDACXX_INLINE_VISIBILITY624 const_iterator begin() const noexcept625 {626#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE627 return const_iterator(__end_.__next_, this);628#else629 return const_iterator(__end_.__next_);630#endif631 }632 _LIBCUDACXX_INLINE_VISIBILITY633 iterator end() noexcept634 {635#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE636 return iterator(__end_as_link(), this);637#else638 return iterator(__end_as_link());639#endif640 }641 _LIBCUDACXX_INLINE_VISIBILITY642 const_iterator end() const noexcept643 {644#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE645 return const_iterator(__end_as_link(), this);646#else647 return const_iterator(__end_as_link());648#endif649 }650 651 void swap(__list_imp& __c)652#if _LIBCUDACXX_STD_VER >= 14653 noexcept;654#else655 noexcept(!__alloc_traits::propagate_on_container_swap::value ||656 __is_nothrow_swappable<allocator_type>::value);657#endif658 659 _LIBCUDACXX_INLINE_VISIBILITY660 void __copy_assign_alloc(const __list_imp& __c)661 {__copy_assign_alloc(__c, integral_constant<bool,662 __node_alloc_traits::propagate_on_container_copy_assignment::value>());}663 664 _LIBCUDACXX_INLINE_VISIBILITY665 void __move_assign_alloc(__list_imp& __c)666 noexcept(667 !__node_alloc_traits::propagate_on_container_move_assignment::value ||668 is_nothrow_move_assignable<__node_allocator>::value)669 {__move_assign_alloc(__c, integral_constant<bool,670 __node_alloc_traits::propagate_on_container_move_assignment::value>());}671 672private:673 _LIBCUDACXX_INLINE_VISIBILITY674 void __copy_assign_alloc(const __list_imp& __c, true_type)675 {676 if (__node_alloc() != __c.__node_alloc())677 clear();678 __node_alloc() = __c.__node_alloc();679 }680 681 _LIBCUDACXX_INLINE_VISIBILITY682 void __copy_assign_alloc(const __list_imp&, false_type)683 {}684 685 _LIBCUDACXX_INLINE_VISIBILITY686 void __move_assign_alloc(__list_imp& __c, true_type)687 noexcept(is_nothrow_move_assignable<__node_allocator>::value)688 {689 __node_alloc() = _CUDA_VSTD::move(__c.__node_alloc());690 }691 692 _LIBCUDACXX_INLINE_VISIBILITY693 void __move_assign_alloc(__list_imp&, false_type)694 noexcept695 {}696 697 _LIBCUDACXX_INLINE_VISIBILITY698 void __invalidate_all_iterators() {699#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE700 __get_db()->__invalidate_all(this);701#endif702 }703};704 705// Unlink nodes [__f, __l]706template <class _Tp, class _Alloc>707inline708void709__list_imp<_Tp, _Alloc>::__unlink_nodes(__link_pointer __f, __link_pointer __l)710 noexcept711{712 __f->__prev_->__next_ = __l->__next_;713 __l->__next_->__prev_ = __f->__prev_;714}715 716template <class _Tp, class _Alloc>717inline718__list_imp<_Tp, _Alloc>::__list_imp()719 noexcept(is_nothrow_default_constructible<__node_allocator>::value)720 : __size_alloc_(0)721{722}723 724template <class _Tp, class _Alloc>725inline726__list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a)727 : __size_alloc_(0, __node_allocator(__a))728{729}730 731template <class _Tp, class _Alloc>732inline __list_imp<_Tp, _Alloc>::__list_imp(const __node_allocator& __a)733 : __size_alloc_(0, __a) {}734 735template <class _Tp, class _Alloc>736inline __list_imp<_Tp, _Alloc>::__list_imp(__node_allocator&& __a) noexcept737 : __size_alloc_(0, std::move(__a)) {}738 739template <class _Tp, class _Alloc>740__list_imp<_Tp, _Alloc>::~__list_imp() {741 clear();742#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE743 __get_db()->__erase_c(this);744#endif745}746 747template <class _Tp, class _Alloc>748void749__list_imp<_Tp, _Alloc>::clear() noexcept750{751 if (!empty())752 {753 __node_allocator& __na = __node_alloc();754 __link_pointer __f = __end_.__next_;755 __link_pointer __l = __end_as_link();756 __unlink_nodes(__f, __l->__prev_);757 __sz() = 0;758 while (__f != __l)759 {760 __node_pointer __np = __f->__as_node();761 __f = __f->__next_;762 __node_alloc_traits::destroy(__na, _CUDA_VSTD::addressof(__np->__value_));763 __node_alloc_traits::deallocate(__na, __np, 1);764 }765 __invalidate_all_iterators();766 }767}768 769template <class _Tp, class _Alloc>770void771__list_imp<_Tp, _Alloc>::swap(__list_imp& __c)772#if _LIBCUDACXX_STD_VER >= 14773 noexcept774#else775 noexcept(!__alloc_traits::propagate_on_container_swap::value ||776 __is_nothrow_swappable<allocator_type>::value)777#endif778{779 _LIBCUDACXX_ASSERT(__alloc_traits::propagate_on_container_swap::value ||780 this->__node_alloc() == __c.__node_alloc(),781 "list::swap: Either propagate_on_container_swap must be true"782 " or the allocators must compare equal");783 using _CUDA_VSTD::swap;784 __swap_allocator(__node_alloc(), __c.__node_alloc());785 swap(__sz(), __c.__sz());786 swap(__end_, __c.__end_);787 if (__sz() == 0)788 __end_.__next_ = __end_.__prev_ = __end_as_link();789 else790 __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_as_link();791 if (__c.__sz() == 0)792 __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_as_link();793 else794 __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_as_link();795 796#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE797 __libcpp_db* __db = __get_db();798 __c_node* __cn1 = __db->__find_c_and_lock(this);799 __c_node* __cn2 = __db->__find_c(&__c);800 std::swap(__cn1->beg_, __cn2->beg_);801 std::swap(__cn1->end_, __cn2->end_);802 std::swap(__cn1->cap_, __cn2->cap_);803 for (__i_node** __p = __cn1->end_; __p != __cn1->beg_;)804 {805 --__p;806 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);807 if (__i->__ptr_ == __c.__end_as_link())808 {809 __cn2->__add(*__p);810 if (--__cn1->end_ != __p)811 memmove(__p, __p+1, (__cn1->end_ - __p)*sizeof(__i_node*));812 }813 else814 (*__p)->__c_ = __cn1;815 }816 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)817 {818 --__p;819 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);820 if (__i->__ptr_ == __end_as_link())821 {822 __cn1->__add(*__p);823 if (--__cn2->end_ != __p)824 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));825 }826 else827 (*__p)->__c_ = __cn2;828 }829 __db->unlock();830#endif831}832 833template <class _Tp, class _Alloc /*= allocator<_Tp>*/>834class _LIBCUDACXX_TEMPLATE_VIS list835 : private __list_imp<_Tp, _Alloc>836{837 typedef __list_imp<_Tp, _Alloc> base;838 typedef typename base::__node __node;839 typedef typename base::__node_allocator __node_allocator;840 typedef typename base::__node_pointer __node_pointer;841 typedef typename base::__node_alloc_traits __node_alloc_traits;842 typedef typename base::__node_base __node_base;843 typedef typename base::__node_base_pointer __node_base_pointer;844 typedef typename base::__link_pointer __link_pointer;845 846public:847 typedef _Tp value_type;848 typedef _Alloc allocator_type;849 static_assert((is_same<value_type, typename allocator_type::value_type>::value),850 "Invalid allocator::value_type");851 typedef value_type& reference;852 typedef const value_type& const_reference;853 typedef typename base::pointer pointer;854 typedef typename base::const_pointer const_pointer;855 typedef typename base::size_type size_type;856 typedef typename base::difference_type difference_type;857 typedef typename base::iterator iterator;858 typedef typename base::const_iterator const_iterator;859 typedef _CUDA_VSTD::reverse_iterator<iterator> reverse_iterator;860 typedef _CUDA_VSTD::reverse_iterator<const_iterator> const_reverse_iterator;861#if _LIBCUDACXX_STD_VER > 17862 typedef size_type __remove_return_type;863#else864 typedef void __remove_return_type;865#endif866 867 _LIBCUDACXX_INLINE_VISIBILITY868 list()869 noexcept(is_nothrow_default_constructible<__node_allocator>::value)870 {871#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE872 __get_db()->__insert_c(this);873#endif874 }875 _LIBCUDACXX_INLINE_VISIBILITY876 explicit list(const allocator_type& __a) : base(__a)877 {878#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE879 __get_db()->__insert_c(this);880#endif881 }882 explicit list(size_type __n);883#if _LIBCUDACXX_STD_VER > 11884 explicit list(size_type __n, const allocator_type& __a);885#endif886 list(size_type __n, const value_type& __x);887 list(size_type __n, const value_type& __x, const allocator_type& __a);888 template <class _InpIter>889 list(_InpIter __f, _InpIter __l,890 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type* = 0);891 template <class _InpIter>892 list(_InpIter __f, _InpIter __l, const allocator_type& __a,893 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type* = 0);894 895 list(const list& __c);896 list(const list& __c, const allocator_type& __a);897 _LIBCUDACXX_INLINE_VISIBILITY898 list& operator=(const list& __c);899 list(initializer_list<value_type> __il);900 list(initializer_list<value_type> __il, const allocator_type& __a);901 902 _LIBCUDACXX_INLINE_VISIBILITY903 list(list&& __c)904 noexcept(is_nothrow_move_constructible<__node_allocator>::value);905 _LIBCUDACXX_INLINE_VISIBILITY906 list(list&& __c, const allocator_type& __a);907 _LIBCUDACXX_INLINE_VISIBILITY908 list& operator=(list&& __c)909 noexcept(910 __node_alloc_traits::propagate_on_container_move_assignment::value &&911 is_nothrow_move_assignable<__node_allocator>::value);912 913 _LIBCUDACXX_INLINE_VISIBILITY914 list& operator=(initializer_list<value_type> __il)915 {assign(__il.begin(), __il.end()); return *this;}916 917 _LIBCUDACXX_INLINE_VISIBILITY918 void assign(initializer_list<value_type> __il)919 {assign(__il.begin(), __il.end());}920 921 template <class _InpIter>922 void assign(_InpIter __f, _InpIter __l,923 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type* = 0);924 void assign(size_type __n, const value_type& __x);925 926 _LIBCUDACXX_INLINE_VISIBILITY927 allocator_type get_allocator() const noexcept;928 929 _LIBCUDACXX_INLINE_VISIBILITY930 size_type size() const noexcept {return base::__sz();}931 _LIBCUDACXX_NODISCARD_AFTER_CXX17 _LIBCUDACXX_INLINE_VISIBILITY932 bool empty() const noexcept {return base::empty();}933 _LIBCUDACXX_INLINE_VISIBILITY934 size_type max_size() const noexcept935 {936 return std::min<size_type>(937 base::__node_alloc_max_size(),938 numeric_limits<difference_type >::max());939 }940 941 _LIBCUDACXX_INLINE_VISIBILITY942 iterator begin() noexcept {return base::begin();}943 _LIBCUDACXX_INLINE_VISIBILITY944 const_iterator begin() const noexcept {return base::begin();}945 _LIBCUDACXX_INLINE_VISIBILITY946 iterator end() noexcept {return base::end();}947 _LIBCUDACXX_INLINE_VISIBILITY948 const_iterator end() const noexcept {return base::end();}949 _LIBCUDACXX_INLINE_VISIBILITY950 const_iterator cbegin() const noexcept {return base::begin();}951 _LIBCUDACXX_INLINE_VISIBILITY952 const_iterator cend() const noexcept {return base::end();}953 954 _LIBCUDACXX_INLINE_VISIBILITY955 reverse_iterator rbegin() noexcept956 {return reverse_iterator(end());}957 _LIBCUDACXX_INLINE_VISIBILITY958 const_reverse_iterator rbegin() const noexcept959 {return const_reverse_iterator(end());}960 _LIBCUDACXX_INLINE_VISIBILITY961 reverse_iterator rend() noexcept962 {return reverse_iterator(begin());}963 _LIBCUDACXX_INLINE_VISIBILITY964 const_reverse_iterator rend() const noexcept965 {return const_reverse_iterator(begin());}966 _LIBCUDACXX_INLINE_VISIBILITY967 const_reverse_iterator crbegin() const noexcept968 {return const_reverse_iterator(end());}969 _LIBCUDACXX_INLINE_VISIBILITY970 const_reverse_iterator crend() const noexcept971 {return const_reverse_iterator(begin());}972 973 _LIBCUDACXX_INLINE_VISIBILITY974 reference front()975 {976 _LIBCUDACXX_ASSERT(!empty(), "list::front called on empty list");977 return base::__end_.__next_->__as_node()->__value_;978 }979 _LIBCUDACXX_INLINE_VISIBILITY980 const_reference front() const981 {982 _LIBCUDACXX_ASSERT(!empty(), "list::front called on empty list");983 return base::__end_.__next_->__as_node()->__value_;984 }985 _LIBCUDACXX_INLINE_VISIBILITY986 reference back()987 {988 _LIBCUDACXX_ASSERT(!empty(), "list::back called on empty list");989 return base::__end_.__prev_->__as_node()->__value_;990 }991 _LIBCUDACXX_INLINE_VISIBILITY992 const_reference back() const993 {994 _LIBCUDACXX_ASSERT(!empty(), "list::back called on empty list");995 return base::__end_.__prev_->__as_node()->__value_;996 }997 998 void push_front(value_type&& __x);999 void push_back(value_type&& __x);1000 1001 template <class... _Args>1002#if _LIBCUDACXX_STD_VER > 141003 reference emplace_front(_Args&&... __args);1004#else1005 void emplace_front(_Args&&... __args);1006#endif1007 template <class... _Args>1008#if _LIBCUDACXX_STD_VER > 141009 reference emplace_back(_Args&&... __args);1010#else1011 void emplace_back(_Args&&... __args);1012#endif1013 template <class... _Args>1014 iterator emplace(const_iterator __p, _Args&&... __args);1015 1016 iterator insert(const_iterator __p, value_type&& __x);1017 1018 _LIBCUDACXX_INLINE_VISIBILITY1019 iterator insert(const_iterator __p, initializer_list<value_type> __il)1020 {return insert(__p, __il.begin(), __il.end());}1021 1022 void push_front(const value_type& __x);1023 void push_back(const value_type& __x);1024 1025 template <class _Arg>1026 _LIBCUDACXX_INLINE_VISIBILITY1027 void __emplace_back(_Arg&& __arg) { emplace_back(_CUDA_VSTD::forward<_Arg>(__arg)); }1028 1029 iterator insert(const_iterator __p, const value_type& __x);1030 iterator insert(const_iterator __p, size_type __n, const value_type& __x);1031 template <class _InpIter>1032 iterator insert(const_iterator __p, _InpIter __f, _InpIter __l,1033 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type* = 0);1034 1035 _LIBCUDACXX_INLINE_VISIBILITY1036 void swap(list& __c)1037#if _LIBCUDACXX_STD_VER >= 141038 noexcept1039#else1040 noexcept(!__node_alloc_traits::propagate_on_container_swap::value ||1041 __is_nothrow_swappable<__node_allocator>::value)1042#endif1043 {base::swap(__c);}1044 _LIBCUDACXX_INLINE_VISIBILITY1045 void clear() noexcept {base::clear();}1046 1047 void pop_front();1048 void pop_back();1049 1050 iterator erase(const_iterator __p);1051 iterator erase(const_iterator __f, const_iterator __l);1052 1053 void resize(size_type __n);1054 void resize(size_type __n, const value_type& __x);1055 1056 void splice(const_iterator __p, list& __c);1057 _LIBCUDACXX_INLINE_VISIBILITY1058 void splice(const_iterator __p, list&& __c) {splice(__p, __c);}1059 _LIBCUDACXX_INLINE_VISIBILITY1060 void splice(const_iterator __p, list&& __c, const_iterator __i)1061 {splice(__p, __c, __i);}1062 _LIBCUDACXX_INLINE_VISIBILITY1063 void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l)1064 {splice(__p, __c, __f, __l);}1065 void splice(const_iterator __p, list& __c, const_iterator __i);1066 void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l);1067 1068 __remove_return_type remove(const value_type& __x);1069 template <class _Pred> __remove_return_type remove_if(_Pred __pred);1070 _LIBCUDACXX_INLINE_VISIBILITY1071 __remove_return_type unique() { return unique(__equal_to<value_type>()); }1072 template <class _BinaryPred>1073 __remove_return_type unique(_BinaryPred __binary_pred);1074 _LIBCUDACXX_INLINE_VISIBILITY1075 void merge(list& __c);1076 _LIBCUDACXX_INLINE_VISIBILITY1077 void merge(list&& __c) {merge(__c);}1078 1079 template <class _Comp>1080 _LIBCUDACXX_INLINE_VISIBILITY1081 void merge(list&& __c, _Comp __comp) {merge(__c, __comp);}1082 template <class _Comp>1083 void merge(list& __c, _Comp __comp);1084 1085 _LIBCUDACXX_INLINE_VISIBILITY1086 void sort();1087 template <class _Comp>1088 _LIBCUDACXX_INLINE_VISIBILITY1089 void sort(_Comp __comp);1090 1091 void reverse() noexcept;1092 1093 bool __invariants() const;1094 1095 typedef __allocator_destructor<__node_allocator> __node_destructor;1096 typedef unique_ptr<__node, __node_destructor> __hold_pointer;1097 1098 _LIBCUDACXX_INLINE_VISIBILITY1099 __hold_pointer __allocate_node(__node_allocator& __na) {1100 __node_pointer __p = __node_alloc_traits::allocate(__na, 1);1101 __p->__prev_ = nullptr;1102 return __hold_pointer(__p, __node_destructor(__na, 1));1103 }1104 1105#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE1106 1107 bool __dereferenceable(const const_iterator* __i) const;1108 bool __decrementable(const const_iterator* __i) const;1109 bool __addable(const const_iterator* __i, ptrdiff_t __n) const;1110 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;1111 1112#endif // _LIBCUDACXX_ENABLE_DEBUG_MODE1113 1114private:1115 _LIBCUDACXX_INLINE_VISIBILITY1116 static void __link_nodes (__link_pointer __p, __link_pointer __f, __link_pointer __l);1117 _LIBCUDACXX_INLINE_VISIBILITY1118 void __link_nodes_at_front(__link_pointer __f, __link_pointer __l);1119 _LIBCUDACXX_INLINE_VISIBILITY1120 void __link_nodes_at_back (__link_pointer __f, __link_pointer __l);1121 iterator __iterator(size_type __n);1122 template <class _Comp>1123 static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp);1124 1125 void __move_assign(list& __c, true_type)1126 noexcept(is_nothrow_move_assignable<__node_allocator>::value);1127 void __move_assign(list& __c, false_type);1128};1129 1130#ifndef _LIBCUDACXX_HAS_NO_DEDUCTION_GUIDES1131template<class _InputIterator,1132 class _Alloc = typename std::allocator<typename iterator_traits<_InputIterator>::value_type>,1133 class = typename enable_if<__is_allocator<_Alloc>::value, void>::type1134 >1135list(_InputIterator, _InputIterator)1136 -> list<typename iterator_traits<_InputIterator>::value_type, _Alloc>;1137 1138template<class _InputIterator,1139 class _Alloc,1140 class = typename enable_if<__is_allocator<_Alloc>::value, void>::type1141 >1142list(_InputIterator, _InputIterator, _Alloc)1143 -> list<typename iterator_traits<_InputIterator>::value_type, _Alloc>;1144#endif1145 1146// Link in nodes [__f, __l] just prior to __p1147template <class _Tp, class _Alloc>1148inline1149void1150list<_Tp, _Alloc>::__link_nodes(__link_pointer __p, __link_pointer __f, __link_pointer __l)1151{1152 __p->__prev_->__next_ = __f;1153 __f->__prev_ = __p->__prev_;1154 __p->__prev_ = __l;1155 __l->__next_ = __p;1156}1157 1158// Link in nodes [__f, __l] at the front of the list1159template <class _Tp, class _Alloc>1160inline1161void1162list<_Tp, _Alloc>::__link_nodes_at_front(__link_pointer __f, __link_pointer __l)1163{1164 __f->__prev_ = base::__end_as_link();1165 __l->__next_ = base::__end_.__next_;1166 __l->__next_->__prev_ = __l;1167 base::__end_.__next_ = __f;1168}1169 1170// Link in nodes [__f, __l] at the back of the list1171template <class _Tp, class _Alloc>1172inline1173void1174list<_Tp, _Alloc>::__link_nodes_at_back(__link_pointer __f, __link_pointer __l)1175{1176 __l->__next_ = base::__end_as_link();1177 __f->__prev_ = base::__end_.__prev_;1178 __f->__prev_->__next_ = __f;1179 base::__end_.__prev_ = __l;1180}1181 1182 1183template <class _Tp, class _Alloc>1184inline1185typename list<_Tp, _Alloc>::iterator1186list<_Tp, _Alloc>::__iterator(size_type __n)1187{1188 return __n <= base::__sz() / 2 ? _CUDA_VSTD::next(begin(), __n)1189 : _CUDA_VSTD::prev(end(), base::__sz() - __n);1190}1191 1192template <class _Tp, class _Alloc>1193list<_Tp, _Alloc>::list(size_type __n)1194{1195#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE1196 __get_db()->__insert_c(this);1197#endif1198 for (; __n > 0; --__n)1199 emplace_back();1200}