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

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