libstdc++-v3/include/bits/list.tcc

   1 // List implementation (out of line) -*- C++ -*-
   2
   3 // Copyright (C) 2001-2024 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /*
  26  *
  27  * Copyright (c) 1994
  28  * Hewlett-Packard Company
  29  *
  30  * Permission to use, copy, modify, distribute and sell this software
  31  * and its documentation for any purpose is hereby granted without fee,
  32  * provided that the above copyright notice appear in all copies and
  33  * that both that copyright notice and this permission notice appear
  34  * in supporting documentation.  Hewlett-Packard Company makes no
  35  * representations about the suitability of this software for any
  36  * purpose.  It is provided "as is" without express or implied warranty.
  37  *
  38  *
  39  * Copyright (c) 1996,1997
  40  * Silicon Graphics Computer Systems, Inc.
  41  *
  42  * Permission to use, copy, modify, distribute and sell this software
  43  * and its documentation for any purpose is hereby granted without fee,
  44  * provided that the above copyright notice appear in all copies and
  45  * that both that copyright notice and this permission notice appear
  46  * in supporting documentation.  Silicon Graphics makes no
  47  * representations about the suitability of this software for any
  48  * purpose.  It is provided "as is" without express or implied warranty.
  49  */
  50
  51 /** @file bits/list.tcc
  52  *  This is an internal header file, included by other library headers.
  53  *  Do not attempt to use it directly. @headername{list}
  54  */
  55
  56 #ifndef _LIST_TCC
  57 #define _LIST_TCC 1
  58
  59 namespace std _GLIBCXX_VISIBILITY(default)
  60 {
  61 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  62 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
  63
  64   template<typename _Tp, typename _Alloc>
  65     void
  66     _List_base<_Tp, _Alloc>::
  67     _M_clear() _GLIBCXX_NOEXCEPT
  68     {
  69       typedef _List_node<_Tp>  _Node;
  70       __detail::_List_node_base* __cur = _M_impl._M_node._M_next;
  71       while (__cur != &_M_impl._M_node)
  72         {
  73           _Node* __tmp = static_cast<_Node*>(__cur);
  74           __cur = __tmp->_M_next;
  75           _Tp* __val = __tmp->_M_valptr();
  76 #if __cplusplus >= 201103L
  77           _Node_alloc_traits::destroy(_M_get_Node_allocator(), __val);
  78 #else
  79           _Tp_alloc_type(_M_get_Node_allocator()).destroy(__val);
  80 #endif
  81           _M_put_node(__tmp);
  82         }
  83     }
  84
  85 #if __cplusplus >= 201103L
  86   template<typename _Tp, typename _Alloc>
  87     template<typename... _Args>
  88       typename list<_Tp, _Alloc>::iterator
  89       list<_Tp, _Alloc>::
  90       emplace(const_iterator __position, _Args&&... __args)
  91       {
  92         _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
  93         __tmp->_M_hook(__position._M_const_cast()._M_node);
  94         this->_M_inc_size(1);
  95         return iterator(__tmp);
  96       }
  97 #endif
  98
  99   template<typename _Tp, typename _Alloc>
 100     typename list<_Tp, _Alloc>::iterator
 101     list<_Tp, _Alloc>::
 102 #if __cplusplus >= 201103L
 103     insert(const_iterator __position, const value_type& __x)
 104 #else
 105     insert(iterator __position, const value_type& __x)
 106 #endif
 107     {
 108       _Node* __tmp = _M_create_node(__x);
 109       __tmp->_M_hook(__position._M_const_cast()._M_node);
 110       this->_M_inc_size(1);
 111       return iterator(__tmp);
 112     }
 113
 114 #if __cplusplus >= 201103L
 115   template<typename _Tp, typename _Alloc>
 116     typename list<_Tp, _Alloc>::iterator
 117     list<_Tp, _Alloc>::
 118     insert(const_iterator __position, size_type __n, const value_type& __x)
 119     {
 120       if (__n)
 121         {
 122           list __tmp(__n, __x, get_allocator());
 123           iterator __it = __tmp.begin();
 124           splice(__position, __tmp);
 125           return __it;
 126         }
 127       return __position._M_const_cast();
 128     }
 129
 130   template<typename _Tp, typename _Alloc>
 131     template<typename _InputIterator, typename>
 132       typename list<_Tp, _Alloc>::iterator
 133       list<_Tp, _Alloc>::
 134       insert(const_iterator __position, _InputIterator __first,
 135              _InputIterator __last)
 136       {
 137         list __tmp(__first, __last, get_allocator());
 138         if (!__tmp.empty())
 139           {
 140             iterator __it = __tmp.begin();
 141             splice(__position, __tmp);
 142             return __it;
 143           }
 144         return __position._M_const_cast();
 145       }
 146 #endif
 147
 148   template<typename _Tp, typename _Alloc>
 149     typename list<_Tp, _Alloc>::iterator
 150     list<_Tp, _Alloc>::
 151 #if __cplusplus >= 201103L
 152     erase(const_iterator __position) noexcept
 153 #else
 154     erase(iterator __position)
 155 #endif
 156     {
 157       iterator __ret = iterator(__position._M_node->_M_next);
 158       _M_erase(__position._M_const_cast());
 159       return __ret;
 160     }
 161
 162   // Return a const_iterator indicating the position to start inserting or
 163   // erasing elements (depending whether the list is growing or shrinking),
 164   // and set __new_size to the number of new elements that must be appended.
 165   // Equivalent to the following, but performed optimally:
 166   // if (__new_size < size()) {
 167   //   __new_size = 0;
 168   //   return std::next(begin(), __new_size);
 169   // } else {
 170   //   __newsize -= size();
 171   //   return end();
 172   // }
 173   template<typename _Tp, typename _Alloc>
 174     typename list<_Tp, _Alloc>::const_iterator
 175     list<_Tp, _Alloc>::
 176     _M_resize_pos(size_type& __new_size) const
 177     {
 178       const_iterator __i;
 179 #if _GLIBCXX_USE_CXX11_ABI
 180       const size_type __len = size();
 181       if (__new_size < __len)
 182         {
 183           if (__new_size <= __len / 2)
 184             {
 185               __i = begin();
 186               std::advance(__i, __new_size);
 187             }
 188           else
 189             {
 190               __i = end();
 191               ptrdiff_t __num_erase = __len - __new_size;
 192               std::advance(__i, -__num_erase);
 193             }
 194           __new_size = 0;
 195           return __i;
 196         }
 197       else
 198         __i = end();
 199 #else
 200       size_type __len = 0;
 201       for (__i = begin(); __i != end() && __len < __new_size; ++__i, ++__len)
 202         ;
 203 #endif
 204       __new_size -= __len;
 205       return __i;
 206     }
 207
 208 #if __cplusplus >= 201103L
 209   template<typename _Tp, typename _Alloc>
 210     void
 211     list<_Tp, _Alloc>::
 212     _M_default_append(size_type __n)
 213     {
 214       size_type __i = 0;
 215       __try
 216         {
 217           for (; __i < __n; ++__i)
 218             emplace_back();
 219         }
 220       __catch(...)
 221         {
 222           for (; __i; --__i)
 223             pop_back();
 224           __throw_exception_again;
 225         }
 226     }
 227
 228   template<typename _Tp, typename _Alloc>
 229     void
 230     list<_Tp, _Alloc>::
 231     resize(size_type __new_size)
 232     {
 233       const_iterator __i = _M_resize_pos(__new_size);
 234       if (__new_size)
 235         _M_default_append(__new_size);
 236       else
 237         erase(__i, end());
 238     }
 239
 240   template<typename _Tp, typename _Alloc>
 241     void
 242     list<_Tp, _Alloc>::
 243     resize(size_type __new_size, const value_type& __x)
 244     {
 245       const_iterator __i = _M_resize_pos(__new_size);
 246       if (__new_size)
 247         insert(end(), __new_size, __x);
 248       else
 249         erase(__i, end());
 250     }
 251 #else
 252   template<typename _Tp, typename _Alloc>
 253     void
 254     list<_Tp, _Alloc>::
 255     resize(size_type __new_size, value_type __x)
 256     {
 257       const_iterator __i = _M_resize_pos(__new_size);
 258       if (__new_size)
 259         insert(end(), __new_size, __x);
 260       else
 261         erase(__i._M_const_cast(), end());
 262     }
 263 #endif
 264
 265   template<typename _Tp, typename _Alloc>
 266     list<_Tp, _Alloc>&
 267     list<_Tp, _Alloc>::
 268     operator=(const list& __x)
 269     {
 270       if (this != std::__addressof(__x))
 271         {
 272 #if __cplusplus >= 201103L
 273           if (_Node_alloc_traits::_S_propagate_on_copy_assign())
 274             {
 275               auto& __this_alloc = this->_M_get_Node_allocator();
 276               auto& __that_alloc = __x._M_get_Node_allocator();
 277               if (!_Node_alloc_traits::_S_always_equal()
 278                   && __this_alloc != __that_alloc)
 279                 {
 280                   // replacement allocator cannot free existing storage
 281                   clear();
 282                 }
 283               std::__alloc_on_copy(__this_alloc, __that_alloc);
 284             }
 285 #endif
 286           _M_assign_dispatch(__x.begin(), __x.end(), __false_type());
 287         }
 288       return *this;
 289     }
 290
 291   template<typename _Tp, typename _Alloc>
 292     void
 293     list<_Tp, _Alloc>::
 294     _M_fill_assign(size_type __n, const value_type& __val)
 295     {
 296       iterator __i = begin();
 297       for (; __i != end() && __n > 0; ++__i, --__n)
 298         *__i = __val;
 299       if (__n > 0)
 300         insert(end(), __n, __val);
 301       else
 302         erase(__i, end());
 303     }
 304
 305   template<typename _Tp, typename _Alloc>
 306     template <typename _InputIterator>
 307       void
 308       list<_Tp, _Alloc>::
 309       _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
 310                          __false_type)
 311       {
 312         iterator __first1 = begin();
 313         iterator __last1 = end();
 314         for (; __first1 != __last1 && __first2 != __last2;
 315              ++__first1, (void)++__first2)
 316           *__first1 = *__first2;
 317         if (__first2 == __last2)
 318           erase(__first1, __last1);
 319         else
 320           insert(__last1, __first2, __last2);
 321       }
 322
 323 #if __cplusplus > 201703L
 324 # define _GLIBCXX20_ONLY(__expr) __expr
 325 #else
 326 # define _GLIBCXX20_ONLY(__expr)
 327 #endif
 328
 329   template<typename _Tp, typename _Alloc>
 330     typename list<_Tp, _Alloc>::__remove_return_type
 331     list<_Tp, _Alloc>::
 332     remove(const value_type& __value)
 333     {
 334 #if !_GLIBCXX_USE_CXX11_ABI
 335       size_type __removed __attribute__((__unused__)) = 0;
 336 #endif
 337       list __to_destroy(get_allocator());
 338       iterator __first = begin();
 339       iterator __last = end();
 340       while (__first != __last)
 341         {
 342           iterator __next = __first;
 343           ++__next;
 344           if (*__first == __value)
 345             {
 346               // _GLIBCXX_RESOLVE_LIB_DEFECTS
 347               // 526. Is it undefined if a function in the standard changes
 348               // in parameters?
 349               __to_destroy.splice(__to_destroy.begin(), *this, __first);
 350 #if !_GLIBCXX_USE_CXX11_ABI
 351               _GLIBCXX20_ONLY( __removed++ );
 352 #endif
 353             }
 354
 355           __first = __next;
 356         }
 357
 358 #if !_GLIBCXX_USE_CXX11_ABI
 359         return _GLIBCXX20_ONLY( __removed );
 360 #else
 361         return _GLIBCXX20_ONLY( __to_destroy.size() );
 362 #endif
 363     }
 364
 365   template<typename _Tp, typename _Alloc>
 366     typename list<_Tp, _Alloc>::__remove_return_type
 367     list<_Tp, _Alloc>::
 368     unique()
 369     {
 370       iterator __first = begin();
 371       iterator __last = end();
 372       if (__first == __last)
 373         return _GLIBCXX20_ONLY( 0 );
 374 #if !_GLIBCXX_USE_CXX11_ABI
 375       size_type __removed __attribute__((__unused__)) = 0;
 376 #endif
 377       list __to_destroy(get_allocator());
 378       iterator __next = __first;
 379       while (++__next != __last)
 380         {
 381           if (*__first == *__next)
 382             {
 383               __to_destroy.splice(__to_destroy.begin(), *this, __next);
 384 #if !_GLIBCXX_USE_CXX11_ABI
 385               _GLIBCXX20_ONLY( __removed++ );
 386 #endif
 387             }
 388           else
 389             __first = __next;
 390           __next = __first;
 391         }
 392
 393 #if !_GLIBCXX_USE_CXX11_ABI
 394       return _GLIBCXX20_ONLY( __removed );
 395 #else
 396       return _GLIBCXX20_ONLY( __to_destroy.size() );
 397 #endif
 398     }
 399
 400   template<typename _Tp, typename _Alloc>
 401     void
 402     list<_Tp, _Alloc>::
 403 #if __cplusplus >= 201103L
 404     merge(list&& __x)
 405 #else
 406     merge(list& __x)
 407 #endif
 408     {
 409       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 410       // 300. list::merge() specification incomplete
 411       if (this != std::__addressof(__x))
 412         {
 413           _M_check_equal_allocators(__x);
 414
 415           iterator __first1 = begin();
 416           iterator __last1 = end();
 417           iterator __first2 = __x.begin();
 418           iterator __last2 = __x.end();
 419
 420           const _Finalize_merge __fin(*this, __x, __first2);
 421
 422           while (__first1 != __last1 && __first2 != __last2)
 423             if (*__first2 < *__first1)
 424               {
 425                 iterator __next = __first2;
 426                 _M_transfer(__first1, __first2, ++__next);
 427                 __first2 = __next;
 428               }
 429             else
 430               ++__first1;
 431           if (__first2 != __last2)
 432             {
 433               _M_transfer(__last1, __first2, __last2);
 434               __first2 = __last2;
 435             }
 436         }
 437     }
 438
 439   template<typename _Tp, typename _Alloc>
 440     template <typename _StrictWeakOrdering>
 441       void
 442       list<_Tp, _Alloc>::
 443 #if __cplusplus >= 201103L
 444       merge(list&& __x, _StrictWeakOrdering __comp)
 445 #else
 446       merge(list& __x, _StrictWeakOrdering __comp)
 447 #endif
 448       {
 449         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 450         // 300. list::merge() specification incomplete
 451         if (this != std::__addressof(__x))
 452           {
 453             _M_check_equal_allocators(__x);
 454
 455             iterator __first1 = begin();
 456             iterator __last1 = end();
 457             iterator __first2 = __x.begin();
 458             iterator __last2 = __x.end();
 459
 460             const _Finalize_merge __fin(*this, __x, __first2);
 461
 462             while (__first1 != __last1 && __first2 != __last2)
 463               if (__comp(*__first2, *__first1))
 464                 {
 465                   iterator __next = __first2;
 466                   _M_transfer(__first1, __first2, ++__next);
 467                   __first2 = __next;
 468                 }
 469               else
 470                 ++__first1;
 471             if (__first2 != __last2)
 472               {
 473                 _M_transfer(__last1, __first2, __last2);
 474                 __first2 = __last2;
 475               }
 476           }
 477       }
 478
 479   template<typename _Tp, typename _Alloc>
 480     void
 481     list<_Tp, _Alloc>::
 482     sort()
 483     {
 484       // Do nothing if the list has length 0 or 1.
 485       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 486           && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
 487       {
 488         using __detail::_Scratch_list;
 489         // The algorithm used here is largely unchanged from the SGI STL
 490         // and is described in The C++ Standard Template Library by Plauger,
 491         // Stepanov, Lee, Musser.
 492         // Each element of *this is spliced out and merged into one of the
 493         // sorted lists in __tmp, then all the lists in __tmp are merged
 494         // together and then swapped back into *this.
 495         // Because all nodes end up back in *this we do not need to update
 496         // this->size() while nodes are temporarily moved out.
 497         _Scratch_list __carry;
 498         _Scratch_list __tmp[64];
 499         _Scratch_list* __fill = __tmp;
 500         _Scratch_list* __counter;
 501
 502         _Scratch_list::_Ptr_cmp<iterator, void> __ptr_comp;
 503
 504         __try
 505           {
 506             do
 507               {
 508                 __carry._M_take_one(begin()._M_node);
 509
 510                 for(__counter = __tmp;
 511                     __counter != __fill && !__counter->empty();
 512                     ++__counter)
 513                   {
 514
 515                     __counter->merge(__carry, __ptr_comp);
 516                     __carry.swap(*__counter);
 517                   }
 518                 __carry.swap(*__counter);
 519                 if (__counter == __fill)
 520                   ++__fill;
 521               }
 522             while ( !empty() );
 523
 524             for (__counter = __tmp + 1; __counter != __fill; ++__counter)
 525               __counter->merge(__counter[-1], __ptr_comp);
 526             __fill[-1].swap(this->_M_impl._M_node);
 527           }
 528         __catch(...)
 529           {
 530             // Move all nodes back into *this.
 531             __carry._M_put_all(end()._M_node);
 532             for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
 533               __tmp[__i]._M_put_all(end()._M_node);
 534             __throw_exception_again;
 535           }
 536       }
 537     }
 538
 539   template<typename _Tp, typename _Alloc>
 540     template <typename _Predicate>
 541       typename list<_Tp, _Alloc>::__remove_return_type
 542       list<_Tp, _Alloc>::
 543       remove_if(_Predicate __pred)
 544       {
 545 #if !_GLIBCXX_USE_CXX11_ABI
 546         size_type __removed __attribute__((__unused__)) = 0;
 547 #endif
 548         list __to_destroy(get_allocator());
 549         iterator __first = begin();
 550         iterator __last = end();
 551         while (__first != __last)
 552           {
 553             iterator __next = __first;
 554             ++__next;
 555             if (__pred(*__first))
 556               {
 557                 __to_destroy.splice(__to_destroy.begin(), *this, __first);
 558 #if !_GLIBCXX_USE_CXX11_ABI
 559                 _GLIBCXX20_ONLY( __removed++ );
 560 #endif
 561               }
 562             __first = __next;
 563           }
 564
 565 #if !_GLIBCXX_USE_CXX11_ABI
 566         return _GLIBCXX20_ONLY( __removed );
 567 #else
 568         return _GLIBCXX20_ONLY( __to_destroy.size() );
 569 #endif
 570       }
 571
 572   template<typename _Tp, typename _Alloc>
 573     template <typename _BinaryPredicate>
 574       typename list<_Tp, _Alloc>::__remove_return_type
 575       list<_Tp, _Alloc>::
 576       unique(_BinaryPredicate __binary_pred)
 577       {
 578         iterator __first = begin();
 579         iterator __last = end();
 580         if (__first == __last)
 581           return _GLIBCXX20_ONLY(0);
 582 #if !_GLIBCXX_USE_CXX11_ABI
 583         size_type __removed __attribute__((__unused__)) = 0;
 584 #endif
 585         list __to_destroy(get_allocator());
 586         iterator __next = __first;
 587         while (++__next != __last)
 588           {
 589             if (__binary_pred(*__first, *__next))
 590               {
 591                 __to_destroy.splice(__to_destroy.begin(), *this, __next);
 592 #if !_GLIBCXX_USE_CXX11_ABI
 593                 _GLIBCXX20_ONLY( __removed++ );
 594 #endif
 595               }
 596             else
 597               __first = __next;
 598             __next = __first;
 599           }
 600
 601 #if !_GLIBCXX_USE_CXX11_ABI
 602         return _GLIBCXX20_ONLY( __removed );
 603 #else
 604         return _GLIBCXX20_ONLY( __to_destroy.size() );
 605 #endif
 606       }
 607
 608 #undef _GLIBCXX20_ONLY
 609
 610   template<typename _Tp, typename _Alloc>
 611     template <typename _StrictWeakOrdering>
 612       void
 613       list<_Tp, _Alloc>::
 614       sort(_StrictWeakOrdering __comp)
 615       {
 616         // Do nothing if the list has length 0 or 1.
 617         if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 618             && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
 619         {
 620           using __detail::_Scratch_list;
 621           _Scratch_list __carry;
 622           _Scratch_list __tmp[64];
 623           _Scratch_list* __fill = __tmp;
 624           _Scratch_list* __counter;
 625
 626         _Scratch_list::_Ptr_cmp<iterator, _StrictWeakOrdering> __ptr_comp
 627           = { __comp };
 628
 629           __try
 630             {
 631               do
 632                 {
 633                   __carry._M_take_one(begin()._M_node);
 634
 635                   for(__counter = __tmp;
 636                       __counter != __fill && !__counter->empty();
 637                       ++__counter)
 638                     {
 639
 640                       __counter->merge(__carry, __ptr_comp);
 641                       __carry.swap(*__counter);
 642                     }
 643                   __carry.swap(*__counter);
 644                   if (__counter == __fill)
 645                     ++__fill;
 646                 }
 647               while ( !empty() );
 648
 649               for (__counter = __tmp + 1; __counter != __fill; ++__counter)
 650                 __counter->merge(__counter[-1], __ptr_comp);
 651               __fill[-1].swap(this->_M_impl._M_node);
 652             }
 653           __catch(...)
 654             {
 655               // Move all nodes back into *this.
 656               __carry._M_put_all(end()._M_node);
 657               for (size_t __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
 658                 __tmp[__i]._M_put_all(end()._M_node);
 659               __throw_exception_again;
 660             }
 661         }
 662       }
 663
 664 _GLIBCXX_END_NAMESPACE_CONTAINER
 665 _GLIBCXX_END_NAMESPACE_VERSION
 666 } // namespace std
 667
 668 #endif /* _LIST_TCC */
 669