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

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