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

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