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

   1 // <forward_list.tcc> -*- C++ -*-
   2
   3 // Copyright (C) 2008, 2009, 2010, 2011, 2012 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 /** @file bits/forward_list.tcc
  26  *  This is an internal header file, included by other library headers.
  27  *  Do not attempt to use it directly. @headername{forward_list}
  28  */
  29
  30 #ifndef _FORWARD_LIST_TCC
  31 #define _FORWARD_LIST_TCC 1
  32
  33 namespace std _GLIBCXX_VISIBILITY(default)
  34 {
  35 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
  36
  37   template<typename _Tp, typename _Alloc>
  38     _Fwd_list_base<_Tp, _Alloc>::
  39     _Fwd_list_base(const _Fwd_list_base& __lst, const _Node_alloc_type& __a)
  40     : _M_impl(__a)
  41     {
  42       this->_M_impl._M_head._M_next = 0;
  43       _Fwd_list_node_base* __to = &this->_M_impl._M_head;
  44       _Node* __curr = static_cast<_Node*>(__lst._M_impl._M_head._M_next);
  45
  46       while (__curr)
  47         {
  48           __to->_M_next = _M_create_node(__curr->_M_value);
  49           __to = __to->_M_next;
  50           __curr = static_cast<_Node*>(__curr->_M_next);
  51         }
  52     }
  53
  54   template<typename _Tp, typename _Alloc>
  55     _Fwd_list_base<_Tp, _Alloc>::
  56     _Fwd_list_base(_Fwd_list_base&& __lst, const _Node_alloc_type& __a)
  57     : _M_impl(__a)
  58     {
  59       if (__lst._M_get_Node_allocator() == __a)
  60         this->_M_impl._M_head._M_next = __lst._M_impl._M_head._M_next;
  61       else
  62         {
  63           this->_M_impl._M_head._M_next = 0;
  64           _Fwd_list_node_base* __to = &this->_M_impl._M_head;
  65           _Node* __curr = static_cast<_Node*>(__lst._M_impl._M_head._M_next);
  66
  67           while (__curr)
  68             {
  69               __to->_M_next =
  70                 _M_create_node(std::move_if_noexcept(__curr->_M_value));
  71               __to = __to->_M_next;
  72               __curr = static_cast<_Node*>(__curr->_M_next);
  73             }
  74         }
  75       __lst._M_impl._M_head._M_next = 0;
  76     }
  77
  78   template<typename _Tp, typename _Alloc>
  79     template<typename... _Args>
  80       _Fwd_list_node_base*
  81       _Fwd_list_base<_Tp, _Alloc>::
  82       _M_insert_after(const_iterator __pos, _Args&&... __args)
  83       {
  84         _Fwd_list_node_base* __to
  85           = const_cast<_Fwd_list_node_base*>(__pos._M_node);
  86         _Node* __thing = _M_create_node(std::forward<_Args>(__args)...);
  87         __thing->_M_next = __to->_M_next;
  88         __to->_M_next = __thing;
  89         return __to->_M_next;
  90       }
  91
  92   template<typename _Tp, typename _Alloc>
  93     _Fwd_list_node_base*
  94     _Fwd_list_base<_Tp, _Alloc>::
  95     _M_erase_after(_Fwd_list_node_base* __pos)
  96     {
  97       _Node* __curr = static_cast<_Node*>(__pos->_M_next);
  98       __pos->_M_next = __curr->_M_next;
  99       _Node_alloc_traits::destroy(_M_get_Node_allocator(), __curr);
 100       _M_put_node(__curr);
 101       return __pos->_M_next;
 102     }
 103
 104   template<typename _Tp, typename _Alloc>
 105     _Fwd_list_node_base*
 106     _Fwd_list_base<_Tp, _Alloc>::
 107     _M_erase_after(_Fwd_list_node_base* __pos,
 108                    _Fwd_list_node_base* __last)
 109     {
 110       _Node* __curr = static_cast<_Node*>(__pos->_M_next);
 111       while (__curr != __last)
 112         {
 113           _Node* __temp = __curr;
 114           __curr = static_cast<_Node*>(__curr->_M_next);
 115           _Node_alloc_traits::destroy(_M_get_Node_allocator(), __temp);
 116           _M_put_node(__temp);
 117         }
 118       __pos->_M_next = __last;
 119       return __last;
 120     }
 121
 122   // Called by the range constructor to implement [23.1.1]/9
 123   template<typename _Tp, typename _Alloc>
 124     template<typename _InputIterator>
 125       void
 126       forward_list<_Tp, _Alloc>::
 127       _M_range_initialize(_InputIterator __first, _InputIterator __last)
 128       {
 129         _Node_base* __to = &this->_M_impl._M_head;
 130         for (; __first != __last; ++__first)
 131           {
 132             __to->_M_next = this->_M_create_node(*__first);
 133             __to = __to->_M_next;
 134           }
 135       }
 136
 137   // Called by forward_list(n,v,a).
 138   template<typename _Tp, typename _Alloc>
 139     void
 140     forward_list<_Tp, _Alloc>::
 141     _M_fill_initialize(size_type __n, const value_type& __value)
 142     {
 143       _Node_base* __to = &this->_M_impl._M_head;
 144       for (; __n; --__n)
 145         {
 146           __to->_M_next = this->_M_create_node(__value);
 147           __to = __to->_M_next;
 148         }
 149     }
 150
 151   template<typename _Tp, typename _Alloc>
 152     void
 153     forward_list<_Tp, _Alloc>::
 154     _M_default_initialize(size_type __n)
 155     {
 156       _Node_base* __to = &this->_M_impl._M_head;
 157       for (; __n; --__n)
 158         {
 159           __to->_M_next = this->_M_create_node();
 160           __to = __to->_M_next;
 161         }
 162     }
 163
 164   template<typename _Tp, typename _Alloc>
 165     forward_list<_Tp, _Alloc>&
 166     forward_list<_Tp, _Alloc>::
 167     operator=(const forward_list& __list)
 168     {
 169       if (&__list != this)
 170         {
 171           if (_Node_alloc_traits::_S_propagate_on_copy_assign())
 172             {
 173               auto& __this_alloc = this->_M_get_Node_allocator();
 174               auto& __that_alloc = __list._M_get_Node_allocator();
 175               if (!_Node_alloc_traits::_S_always_equal()
 176                   && __this_alloc != __that_alloc)
 177                 {
 178                   // replacement allocator cannot free existing storage
 179                   clear();
 180                 }
 181               std::__alloc_on_copy(__this_alloc, __that_alloc);
 182             }
 183           iterator __prev1 = before_begin();
 184           iterator __curr1 = begin();
 185           iterator __last1 = end();
 186           const_iterator __first2 = __list.cbegin();
 187           const_iterator __last2 = __list.cend();
 188           while (__curr1 != __last1 && __first2 != __last2)
 189             {
 190               *__curr1 = *__first2;
 191               ++__prev1;
 192               ++__curr1;
 193               ++__first2;
 194             }
 195           if (__first2 == __last2)
 196             erase_after(__prev1, __last1);
 197           else
 198             insert_after(__prev1, __first2, __last2);
 199         }
 200       return *this;
 201     }
 202
 203   template<typename _Tp, typename _Alloc>
 204     void
 205     forward_list<_Tp, _Alloc>::
 206     _M_default_insert_after(const_iterator __pos, size_type __n)
 207     {
 208       const_iterator __saved_pos = __pos;
 209       __try
 210         {
 211           for (; __n; --__n)
 212             __pos = emplace_after(__pos);
 213         }
 214       __catch(...)
 215         {
 216           erase_after(__saved_pos, ++__pos);
 217           __throw_exception_again;
 218         }
 219     }
 220
 221   template<typename _Tp, typename _Alloc>
 222     void
 223     forward_list<_Tp, _Alloc>::
 224     resize(size_type __sz)
 225     {
 226       iterator __k = before_begin();
 227
 228       size_type __len = 0;
 229       while (__k._M_next() != end() && __len < __sz)
 230         {
 231           ++__k;
 232           ++__len;
 233         }
 234       if (__len == __sz)
 235         erase_after(__k, end());
 236       else
 237         _M_default_insert_after(__k, __sz - __len);
 238     }
 239
 240   template<typename _Tp, typename _Alloc>
 241     void
 242     forward_list<_Tp, _Alloc>::
 243     resize(size_type __sz, const value_type& __val)
 244     {
 245       iterator __k = before_begin();
 246
 247       size_type __len = 0;
 248       while (__k._M_next() != end() && __len < __sz)
 249         {
 250           ++__k;
 251           ++__len;
 252         }
 253       if (__len == __sz)
 254         erase_after(__k, end());
 255       else
 256         insert_after(__k, __sz - __len, __val);
 257     }
 258
 259   template<typename _Tp, typename _Alloc>
 260     typename forward_list<_Tp, _Alloc>::iterator
 261     forward_list<_Tp, _Alloc>::
 262     _M_splice_after(const_iterator __pos,
 263                     const_iterator __before, const_iterator __last)
 264     {
 265       _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
 266       _Node_base* __b = const_cast<_Node_base*>(__before._M_node);
 267       _Node_base* __end = __b;
 268
 269       while (__end && __end->_M_next != __last._M_node)
 270         __end = __end->_M_next;
 271
 272       if (__b != __end)
 273         return iterator(__tmp->_M_transfer_after(__b, __end));
 274       else
 275         return iterator(__tmp);
 276     }
 277
 278   template<typename _Tp, typename _Alloc>
 279     void
 280     forward_list<_Tp, _Alloc>::
 281     splice_after(const_iterator __pos, forward_list&&,
 282                  const_iterator __i)
 283     {
 284       const_iterator __j = __i;
 285       ++__j;
 286
 287       if (__pos == __i || __pos == __j)
 288         return;
 289
 290       _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
 291       __tmp->_M_transfer_after(const_cast<_Node_base*>(__i._M_node),
 292                                const_cast<_Node_base*>(__j._M_node));
 293     }
 294
 295   template<typename _Tp, typename _Alloc>
 296     typename forward_list<_Tp, _Alloc>::iterator
 297     forward_list<_Tp, _Alloc>::
 298     insert_after(const_iterator __pos, size_type __n, const _Tp& __val)
 299     {
 300       if (__n)
 301         {
 302           forward_list __tmp(__n, __val, get_allocator());
 303           return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
 304         }
 305       else
 306         return iterator(const_cast<_Node_base*>(__pos._M_node));
 307     }
 308
 309   template<typename _Tp, typename _Alloc>
 310     template<typename _InputIterator, typename>
 311       typename forward_list<_Tp, _Alloc>::iterator
 312       forward_list<_Tp, _Alloc>::
 313       insert_after(const_iterator __pos,
 314                    _InputIterator __first, _InputIterator __last)
 315       {
 316         forward_list __tmp(__first, __last, get_allocator());
 317         if (!__tmp.empty())
 318           return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
 319         else
 320           return iterator(const_cast<_Node_base*>(__pos._M_node));
 321       }
 322
 323   template<typename _Tp, typename _Alloc>
 324     void
 325     forward_list<_Tp, _Alloc>::
 326     remove(const _Tp& __val)
 327     {
 328       _Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
 329       _Node* __extra = 0;
 330
 331       while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
 332         {
 333           if (__tmp->_M_value == __val)
 334             {
 335               if (std::__addressof(__tmp->_M_value)
 336                   != std::__addressof(__val))
 337                 {
 338                   this->_M_erase_after(__curr);
 339                   continue;
 340                 }
 341               else
 342                 __extra = __curr;
 343             }
 344           __curr = static_cast<_Node*>(__curr->_M_next);
 345         }
 346
 347       if (__extra)
 348         this->_M_erase_after(__extra);
 349     }
 350
 351   template<typename _Tp, typename _Alloc>
 352     template<typename _Pred>
 353       void
 354       forward_list<_Tp, _Alloc>::
 355       remove_if(_Pred __pred)
 356       {
 357         _Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
 358         while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
 359           {
 360             if (__pred(__tmp->_M_value))
 361               this->_M_erase_after(__curr);
 362             else
 363               __curr = static_cast<_Node*>(__curr->_M_next);
 364           }
 365       }
 366
 367   template<typename _Tp, typename _Alloc>
 368     template<typename _BinPred>
 369       void
 370       forward_list<_Tp, _Alloc>::
 371       unique(_BinPred __binary_pred)
 372       {
 373         iterator __first = begin();
 374         iterator __last = end();
 375         if (__first == __last)
 376           return;
 377         iterator __next = __first;
 378         while (++__next != __last)
 379         {
 380           if (__binary_pred(*__first, *__next))
 381             erase_after(__first);
 382           else
 383             __first = __next;
 384           __next = __first;
 385         }
 386       }
 387
 388   template<typename _Tp, typename _Alloc>
 389     template<typename _Comp>
 390       void
 391       forward_list<_Tp, _Alloc>::
 392       merge(forward_list&& __list, _Comp __comp)
 393       {
 394         _Node_base* __node = &this->_M_impl._M_head;
 395         while (__node->_M_next && __list._M_impl._M_head._M_next)
 396           {
 397             if (__comp(static_cast<_Node*>
 398                        (__list._M_impl._M_head._M_next)->_M_value,
 399                        static_cast<_Node*>
 400                        (__node->_M_next)->_M_value))
 401               __node->_M_transfer_after(&__list._M_impl._M_head,
 402                                         __list._M_impl._M_head._M_next);
 403             __node = __node->_M_next;
 404           }
 405         if (__list._M_impl._M_head._M_next)
 406           {
 407             __node->_M_next = __list._M_impl._M_head._M_next;
 408             __list._M_impl._M_head._M_next = 0;
 409           }
 410       }
 411
 412   template<typename _Tp, typename _Alloc>
 413     bool
 414     operator==(const forward_list<_Tp, _Alloc>& __lx,
 415                const forward_list<_Tp, _Alloc>& __ly)
 416     {
 417       //  We don't have size() so we need to walk through both lists
 418       //  making sure both iterators are valid.
 419       auto __ix = __lx.cbegin();
 420       auto __iy = __ly.cbegin();
 421       while (__ix != __lx.cend() && __iy != __ly.cend())
 422         {
 423           if (*__ix != *__iy)
 424             return false;
 425           ++__ix;
 426           ++__iy;
 427         }
 428       if (__ix == __lx.cend() && __iy == __ly.cend())
 429         return true;
 430       else
 431         return false;
 432     }
 433
 434   template<typename _Tp, class _Alloc>
 435     template<typename _Comp>
 436       void
 437       forward_list<_Tp, _Alloc>::
 438       sort(_Comp __comp)
 439       {
 440         // If `next' is 0, return immediately.
 441         _Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next);
 442         if (!__list)
 443           return;
 444
 445         unsigned long __insize = 1;
 446
 447         while (1)
 448           {
 449             _Node* __p = __list;
 450             __list = 0;
 451             _Node* __tail = 0;
 452
 453             // Count number of merges we do in this pass.
 454             unsigned long __nmerges = 0;
 455
 456             while (__p)
 457               {
 458                 ++__nmerges;
 459                 // There exists a merge to be done.
 460                 // Step `insize' places along from p.
 461                 _Node* __q = __p;
 462                 unsigned long __psize = 0;
 463                 for (unsigned long __i = 0; __i < __insize; ++__i)
 464                   {
 465                     ++__psize;
 466                     __q = static_cast<_Node*>(__q->_M_next);
 467                     if (!__q)
 468                       break;
 469                   }
 470
 471                 // If q hasn't fallen off end, we have two lists to merge.
 472                 unsigned long __qsize = __insize;
 473
 474                 // Now we have two lists; merge them.
 475                 while (__psize > 0 || (__qsize > 0 && __q))
 476                   {
 477                     // Decide whether next node of merge comes from p or q.
 478                     _Node* __e;
 479                     if (__psize == 0)
 480                       {
 481                         // p is empty; e must come from q.
 482                         __e = __q;
 483                         __q = static_cast<_Node*>(__q->_M_next);
 484                         --__qsize;
 485                       }
 486                     else if (__qsize == 0 || !__q)
 487                       {
 488                         // q is empty; e must come from p.
 489                         __e = __p;
 490                         __p = static_cast<_Node*>(__p->_M_next);
 491                         --__psize;
 492                       }
 493                     else if (__comp(__p->_M_value, __q->_M_value))
 494                       {
 495                         // First node of p is lower; e must come from p.
 496                         __e = __p;
 497                         __p = static_cast<_Node*>(__p->_M_next);
 498                         --__psize;
 499                       }
 500                     else
 501                       {
 502                         // First node of q is lower; e must come from q.
 503                         __e = __q;
 504                         __q = static_cast<_Node*>(__q->_M_next);
 505                         --__qsize;
 506                       }
 507
 508                     // Add the next node to the merged list.
 509                     if (__tail)
 510                       __tail->_M_next = __e;
 511                     else
 512                       __list = __e;
 513                     __tail = __e;
 514                   }
 515
 516                 // Now p has stepped `insize' places along, and q has too.
 517                 __p = __q;
 518               }
 519             __tail->_M_next = 0;
 520
 521             // If we have done only one merge, we're finished.
 522             // Allow for nmerges == 0, the empty list case.
 523             if (__nmerges <= 1)
 524               {
 525                 this->_M_impl._M_head._M_next = __list;
 526                 return;
 527               }
 528
 529             // Otherwise repeat, merging lists twice the size.
 530             __insize *= 2;
 531           }
 532       }
 533
 534 _GLIBCXX_END_NAMESPACE_CONTAINER
 535 } // namespace std
 536
 537 #endif /* _FORWARD_LIST_TCC */
 538