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