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