contrib/gcc-8.0/libstdc++-v3/include/bits/list.tcc

   1 // List implementation (out of line) -*- C++ -*-
   2
   3 // Copyright (C) 2001-2018 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, ++__first2)
 316           *__first1 = *__first2;
 317         if (__first2 == __last2)
 318           erase(__first1, __last1);
 319         else
 320           insert(__last1, __first2, __last2);
 321       }
 322
 323   template<typename _Tp, typename _Alloc>
 324     void
 325     list<_Tp, _Alloc>::
 326     remove(const value_type& __value)
 327     {
 328       iterator __first = begin();
 329       iterator __last = end();
 330       iterator __extra = __last;
 331       while (__first != __last)
 332         {
 333           iterator __next = __first;
 334           ++__next;
 335           if (*__first == __value)
 336             {
 337               // _GLIBCXX_RESOLVE_LIB_DEFECTS
 338               // 526. Is it undefined if a function in the standard changes
 339               // in parameters?
 340               if (std::__addressof(*__first) != std::__addressof(__value))
 341                 _M_erase(__first);
 342               else
 343                 __extra = __first;
 344             }
 345           __first = __next;
 346         }
 347       if (__extra != __last)
 348         _M_erase(__extra);
 349     }
 350
 351   template<typename _Tp, typename _Alloc>
 352     void
 353     list<_Tp, _Alloc>::
 354     unique()
 355     {
 356       iterator __first = begin();
 357       iterator __last = end();
 358       if (__first == __last)
 359         return;
 360       iterator __next = __first;
 361       while (++__next != __last)
 362         {
 363           if (*__first == *__next)
 364             _M_erase(__next);
 365           else
 366             __first = __next;
 367           __next = __first;
 368         }
 369     }
 370
 371   template<typename _Tp, typename _Alloc>
 372     void
 373     list<_Tp, _Alloc>::
 374 #if __cplusplus >= 201103L
 375     merge(list&& __x)
 376 #else
 377     merge(list& __x)
 378 #endif
 379     {
 380       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 381       // 300. list::merge() specification incomplete
 382       if (this != std::__addressof(__x))
 383         {
 384           _M_check_equal_allocators(__x);
 385
 386           iterator __first1 = begin();
 387           iterator __last1 = end();
 388           iterator __first2 = __x.begin();
 389           iterator __last2 = __x.end();
 390           const size_t __orig_size = __x.size();
 391           __try {
 392             while (__first1 != __last1 && __first2 != __last2)
 393               if (*__first2 < *__first1)
 394                 {
 395                   iterator __next = __first2;
 396                   _M_transfer(__first1, __first2, ++__next);
 397                   __first2 = __next;
 398                 }
 399               else
 400                 ++__first1;
 401             if (__first2 != __last2)
 402               _M_transfer(__last1, __first2, __last2);
 403
 404             this->_M_inc_size(__x._M_get_size());
 405             __x._M_set_size(0);
 406           }
 407           __catch(...)
 408             {
 409               const size_t __dist = std::distance(__first2, __last2);
 410               this->_M_inc_size(__orig_size - __dist);
 411               __x._M_set_size(__dist);
 412               __throw_exception_again;
 413             }
 414         }
 415     }
 416
 417   template<typename _Tp, typename _Alloc>
 418     template <typename _StrictWeakOrdering>
 419       void
 420       list<_Tp, _Alloc>::
 421 #if __cplusplus >= 201103L
 422       merge(list&& __x, _StrictWeakOrdering __comp)
 423 #else
 424       merge(list& __x, _StrictWeakOrdering __comp)
 425 #endif
 426       {
 427         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 428         // 300. list::merge() specification incomplete
 429         if (this != std::__addressof(__x))
 430           {
 431             _M_check_equal_allocators(__x);
 432
 433             iterator __first1 = begin();
 434             iterator __last1 = end();
 435             iterator __first2 = __x.begin();
 436             iterator __last2 = __x.end();
 437             const size_t __orig_size = __x.size();
 438             __try
 439               {
 440                 while (__first1 != __last1 && __first2 != __last2)
 441                   if (__comp(*__first2, *__first1))
 442                     {
 443                       iterator __next = __first2;
 444                       _M_transfer(__first1, __first2, ++__next);
 445                       __first2 = __next;
 446                     }
 447                   else
 448                     ++__first1;
 449                 if (__first2 != __last2)
 450                   _M_transfer(__last1, __first2, __last2);
 451
 452                 this->_M_inc_size(__x._M_get_size());
 453                 __x._M_set_size(0);
 454               }
 455             __catch(...)
 456               {
 457                 const size_t __dist = std::distance(__first2, __last2);
 458                 this->_M_inc_size(__orig_size - __dist);
 459                 __x._M_set_size(__dist);
 460                 __throw_exception_again;
 461               }
 462           }
 463       }
 464
 465   template<typename _Tp, typename _Alloc>
 466     void
 467     list<_Tp, _Alloc>::
 468     sort()
 469     {
 470       // Do nothing if the list has length 0 or 1.
 471       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 472           && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
 473       {
 474         list __carry;
 475         list __tmp[64];
 476         list * __fill = __tmp;
 477         list * __counter;
 478         __try
 479           {
 480             do
 481               {
 482                 __carry.splice(__carry.begin(), *this, begin());
 483
 484                 for(__counter = __tmp;
 485                     __counter != __fill && !__counter->empty();
 486                     ++__counter)
 487                   {
 488                     __counter->merge(__carry);
 489                     __carry.swap(*__counter);
 490                   }
 491                 __carry.swap(*__counter);
 492                 if (__counter == __fill)
 493                   ++__fill;
 494               }
 495             while ( !empty() );
 496
 497             for (__counter = __tmp + 1; __counter != __fill; ++__counter)
 498               __counter->merge(*(__counter - 1));
 499             swap( *(__fill - 1) );
 500           }
 501         __catch(...)
 502           {
 503             this->splice(this->end(), __carry);
 504             for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
 505               this->splice(this->end(), __tmp[__i]);
 506             __throw_exception_again;
 507           }
 508       }
 509     }
 510
 511   template<typename _Tp, typename _Alloc>
 512     template <typename _Predicate>
 513       void
 514       list<_Tp, _Alloc>::
 515       remove_if(_Predicate __pred)
 516       {
 517         iterator __first = begin();
 518         iterator __last = end();
 519         while (__first != __last)
 520           {
 521             iterator __next = __first;
 522             ++__next;
 523             if (__pred(*__first))
 524               _M_erase(__first);
 525             __first = __next;
 526           }
 527       }
 528
 529   template<typename _Tp, typename _Alloc>
 530     template <typename _BinaryPredicate>
 531       void
 532       list<_Tp, _Alloc>::
 533       unique(_BinaryPredicate __binary_pred)
 534       {
 535         iterator __first = begin();
 536         iterator __last = end();
 537         if (__first == __last)
 538           return;
 539         iterator __next = __first;
 540         while (++__next != __last)
 541           {
 542             if (__binary_pred(*__first, *__next))
 543               _M_erase(__next);
 544             else
 545               __first = __next;
 546             __next = __first;
 547           }
 548       }
 549
 550   template<typename _Tp, typename _Alloc>
 551     template <typename _StrictWeakOrdering>
 552       void
 553       list<_Tp, _Alloc>::
 554       sort(_StrictWeakOrdering __comp)
 555       {
 556         // Do nothing if the list has length 0 or 1.
 557         if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 558             && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
 559           {
 560             list __carry;
 561             list __tmp[64];
 562             list * __fill = __tmp;
 563             list * __counter;
 564             __try
 565               {
 566                 do
 567                   {
 568                     __carry.splice(__carry.begin(), *this, begin());
 569
 570                     for(__counter = __tmp;
 571                         __counter != __fill && !__counter->empty();
 572                         ++__counter)
 573                       {
 574                         __counter->merge(__carry, __comp);
 575                         __carry.swap(*__counter);
 576                       }
 577                     __carry.swap(*__counter);
 578                     if (__counter == __fill)
 579                       ++__fill;
 580                   }
 581                 while ( !empty() );
 582
 583                 for (__counter = __tmp + 1; __counter != __fill; ++__counter)
 584                   __counter->merge(*(__counter - 1), __comp);
 585                 swap(*(__fill - 1));
 586               }
 587             __catch(...)
 588               {
 589                 this->splice(this->end(), __carry);
 590                 for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
 591                   this->splice(this->end(), __tmp[__i]);
 592                 __throw_exception_again;
 593               }
 594           }
 595       }
 596
 597 _GLIBCXX_END_NAMESPACE_CONTAINER
 598 _GLIBCXX_END_NAMESPACE_VERSION
 599 } // namespace std
 600
 601 #endif /* _LIST_TCC */
 602