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

   1 // <forward_list.tcc> -*- C++ -*-
   2
   3 // Copyright (C) 2008 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  19 // Boston, MA 02110-1301, USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /** @file forward_list.tcc
  31  *  This is a Standard C++ Library header.
  32  */
  33
  34 #ifndef _FORWARD_LIST_TCC
  35 #define _FORWARD_LIST_TCC 1
  36
  37 _GLIBCXX_BEGIN_NAMESPACE(std)
  38
  39  /**
  40   *  @brief  Sort the singly linked list starting after this node.
  41   *          This node is assumed to be an empty head node (of type
  42   *          _Fwd_list_node_base).
  43   */
  44   template<typename _Tp>
  45     template<typename _Comp>
  46       void
  47       _Fwd_list_node<_Tp>::
  48       _M_sort_after(_Comp __comp)
  49       {
  50         // If `next' is 0, return immediately.
  51         _Fwd_list_node* __list = static_cast<_Fwd_list_node*>(this->_M_next);
  52         if (!__list)
  53           return;
  54
  55         unsigned long __insize = 1;
  56
  57         while (1)
  58           {
  59             _Fwd_list_node* __p = __list;
  60             __list = 0;
  61             _Fwd_list_node* __tail = 0;
  62
  63             // Count number of merges we do in this pass.
  64             unsigned long __nmerges = 0;
  65
  66             while (__p)
  67               {
  68                 ++__nmerges;
  69                 // There exists a merge to be done.
  70                 // Step `insize' places along from p.
  71                 _Fwd_list_node* __q = __p;
  72                 unsigned long __psize = 0;
  73                 for (unsigned long __i = 0; __i < __insize; ++__i)
  74                   {
  75                     ++__psize;
  76                     __q = static_cast<_Fwd_list_node*>(__q->_M_next);
  77                     if (!__q)
  78                       break;
  79                   }
  80
  81                 // If q hasn't fallen off end, we have two lists to merge.
  82                 unsigned long __qsize = __insize;
  83
  84                 // Now we have two lists; merge them.
  85                 while (__psize > 0 || (__qsize > 0 && __q))
  86                   {
  87                     // Decide whether next node of merge comes from p or q.
  88                     _Fwd_list_node<_Tp>* __e;
  89                     if (__psize == 0)
  90                       {
  91                         // p is empty; e must come from q.
  92                         __e = __q;
  93                         __q = static_cast<_Fwd_list_node*>(__q->_M_next);
  94                         --__qsize;
  95                       }
  96                     else if (__qsize == 0 || !__q)
  97                       {
  98                         // q is empty; e must come from p.
  99                         __e = __p;
 100                         __p = static_cast<_Fwd_list_node*>(__p->_M_next);
 101                         --__psize;
 102                       }
 103                     else if (__comp(__p->_M_value, __q->_M_value))
 104                       {
 105                         // First node of p is lower; e must come from p.
 106                         __e = __p;
 107                         __p = static_cast<_Fwd_list_node*>(__p->_M_next);
 108                         --__psize;
 109                       }
 110                     else
 111                       {
 112                         // First node of q is lower; e must come from q.
 113                         __e = __q;
 114                         __q = static_cast<_Fwd_list_node*>(__q->_M_next);
 115                         --__qsize;
 116                       }
 117
 118                     // Add the next node to the merged list.
 119                     if (__tail)
 120                       __tail->_M_next = __e;
 121                     else
 122                       __list = __e;
 123                     __tail = __e;
 124                   }
 125
 126                 // Now p has stepped `insize' places along, and q has too.
 127                 __p = __q;
 128               }
 129             __tail->_M_next = 0;
 130
 131             // If we have done only one merge, we're finished.
 132             // Allow for nmerges == 0, the empty list case.
 133             if (__nmerges <= 1)
 134               {
 135                 this->_M_next = __list;
 136                 return;
 137               }
 138
 139             // Otherwise repeat, merging lists twice the size.
 140             __insize *= 2;
 141           }
 142       }
 143
 144   template<typename _Tp, typename _Alloc>
 145     _Fwd_list_base<_Tp, _Alloc>::
 146     _Fwd_list_base(const _Fwd_list_base& __lst, const _Alloc& __a)
 147     : _M_impl(__a)
 148     {
 149       this->_M_impl._M_head._M_next = 0;
 150       _Fwd_list_node_base* __to = &this->_M_impl._M_head;
 151       _Node* __curr = static_cast<_Node*>(__lst._M_impl._M_head._M_next);
 152       while (__curr)
 153         {
 154           __to->_M_next = _M_create_node(__curr->_M_value);
 155           __to = __to->_M_next;
 156           __curr = static_cast<_Node*>(__curr->_M_next);
 157         }
 158     }
 159
 160   template<typename _Tp, typename _Alloc>
 161     template<typename... _Args>
 162       _Fwd_list_node_base*
 163       _Fwd_list_base<_Tp, _Alloc>::
 164       _M_insert_after(const_iterator __pos, _Args&&... __args)
 165       {
 166         _Fwd_list_node_base* __to
 167           = const_cast<_Fwd_list_node_base*>(__pos._M_node);
 168         _Node* __thing = _M_create_node(std::forward<_Args>(__args)...);
 169         __thing->_M_next = __to->_M_next;
 170         __to->_M_next = __thing;
 171         return __to->_M_next;
 172       }
 173
 174   template<typename _Tp, typename _Alloc>
 175     _Fwd_list_node_base*
 176     _Fwd_list_base<_Tp, _Alloc>::
 177     _M_erase_after(_Fwd_list_node_base* __pos)
 178     {
 179       _Node* __curr = static_cast<_Node*>(__pos->_M_next);
 180       if (__curr)
 181         {
 182           _Fwd_list_node_base* __next = __curr->_M_next;
 183           __pos->_M_next = __next;
 184           _M_get_Node_allocator().destroy(__curr);
 185           _M_put_node(__curr);
 186         }
 187       return __pos;
 188     }
 189
 190   template<typename _Tp, typename _Alloc>
 191     _Fwd_list_node_base*
 192     _Fwd_list_base<_Tp, _Alloc>::
 193     _M_erase_after(_Fwd_list_node_base* __pos, _Fwd_list_node_base* __last)
 194     {
 195       _Node* __curr = static_cast<_Node*>(__pos->_M_next);
 196       while (__curr)
 197         {
 198           _Node* __temp = __curr;
 199           __curr = static_cast<_Node*>(__curr->_M_next);
 200           _M_get_Node_allocator().destroy(__temp);
 201           _M_put_node(__temp);
 202           __pos->_M_next = __curr;
 203           if (__temp == __last)
 204             break;
 205         }
 206       return __pos;
 207     }
 208
 209   template<typename _Tp, typename _Alloc>
 210     forward_list<_Tp, _Alloc>::
 211     forward_list(size_type __n)
 212     : _Base()
 213     {
 214       _Fwd_list_node_base* __to = &this->_M_impl._M_head;
 215       for (size_type __i = 0; __i < __n; ++__i)
 216         {
 217           __to->_M_next = this->_M_create_node(_Tp());
 218           __to = __to->_M_next;
 219         }
 220     }
 221
 222   template<typename _Tp, typename _Alloc>
 223     forward_list<_Tp, _Alloc>::
 224     forward_list(size_type __n, const _Tp& __value, const _Alloc& __al)
 225     : _Base(__al)
 226     {
 227       _Fwd_list_node_base* __to = &this->_M_impl._M_head;
 228       for (size_type __i = 0; __i < __n; ++__i)
 229         {
 230           __to->_M_next = this->_M_create_node(__value);
 231           __to = __to->_M_next;
 232         }
 233     }
 234
 235   template<typename _Tp, typename _Alloc>
 236     template<typename _InputIterator>
 237       forward_list<_Tp, _Alloc>::
 238       forward_list(_InputIterator __first, _InputIterator __last,
 239                    const _Alloc& __al)
 240       : _Base(__al)
 241       {
 242         _Fwd_list_node_base* __to = &this->_M_impl._M_head;
 243         _InputIterator __curr = __first;
 244         while (__curr != __last)
 245           {
 246             __to->_M_next = this->_M_create_node(*__curr);
 247             __to = __to->_M_next;
 248             ++__curr;
 249           }
 250       }
 251
 252   template<typename _Tp, typename _Alloc>
 253     forward_list<_Tp, _Alloc>::
 254     forward_list(const forward_list& __list)
 255     : _Base(__list._M_get_Node_allocator())
 256     {
 257       const _Fwd_list_node_base* __from = &__list._M_impl._M_head;
 258       _Fwd_list_node_base* __to = &this->_M_impl._M_head;
 259       while (__from->_M_next != 0)
 260         {
 261           const _Node* __temp = static_cast<_Node*>(__from->_M_next);
 262           __to->_M_next = this->_M_create_node(__temp->_M_value);
 263           __from = __from->_M_next;
 264           __to = __to->_M_next;
 265         }
 266     }
 267
 268   template<typename _Tp, typename _Alloc>
 269     forward_list<_Tp, _Alloc>::
 270     forward_list(std::initializer_list<_Tp> __il, const _Alloc& __al)
 271     : _Base(__al)
 272     {
 273       _Fwd_list_node_base* __to = &this->_M_impl._M_head;
 274       for (const _Tp* __item = __il.begin();
 275            __item != __il.end(); ++__item)
 276         {
 277           __to->_M_next = this->_M_create_node(*__item);
 278           __to = __to->_M_next;
 279         }
 280     }
 281
 282   template<typename _Tp, typename _Alloc>
 283     forward_list<_Tp, _Alloc>&
 284     forward_list<_Tp, _Alloc>::
 285     operator=(const forward_list& __list)
 286     {
 287       if (&__list != this)
 288         {
 289           iterator __prev1 = before_begin();
 290           iterator __curr1 = begin();
 291           iterator __last1 = end();
 292           const_iterator __first2 = __list.cbegin();
 293           const_iterator __last2 = __list.cend();
 294           while (__curr1 != __last1 && __first2 != __last2)
 295             {
 296               *__curr1 = *__first2;
 297               ++__prev1;
 298               ++__curr1;
 299               ++__first2;
 300             }
 301           if (__first2 == __last2)
 302             erase_after(__prev1, __last1);
 303           else
 304             insert_after(__prev1, __first2, __last2);
 305         }
 306       return *this;
 307     }
 308
 309   template<typename _Tp, typename _Alloc>
 310     void
 311     forward_list<_Tp, _Alloc>::
 312     insert_after(const_iterator __pos,
 313                  size_type __n, const _Tp& __val)
 314     {
 315       _Fwd_list_node_base* __to
 316         = const_cast<_Fwd_list_node_base*>(__pos._M_node);
 317       _Fwd_list_node_base* __keep = __to->_M_next;
 318       for (size_type __i = 0; __i < __n; ++__i)
 319         {
 320           __to->_M_next = this->_M_create_node(__val);
 321           __to = __to->_M_next;
 322         }
 323       __to->_M_next = __keep;
 324     }
 325
 326   template<typename _Tp, typename _Alloc>
 327     template<typename _InputIterator>
 328       void
 329       forward_list<_Tp, _Alloc>::
 330       insert_after(const_iterator __pos,
 331                    _InputIterator __first, _InputIterator __last)
 332       {
 333         _Fwd_list_node_base* __to
 334           = const_cast<_Fwd_list_node_base*>(__pos._M_node);
 335         _Fwd_list_node_base* __keep = __to->_M_next;
 336         _InputIterator __curr = __first;
 337         while (__curr != __last)
 338           {
 339             __to->_M_next = this->_M_create_node(*__curr);
 340             __to = __to->_M_next;
 341             ++__curr;
 342           }
 343         __to->_M_next = __keep;
 344       }
 345
 346   template<typename _Tp, typename _Alloc>
 347     void
 348     forward_list<_Tp, _Alloc>::
 349     insert_after(const_iterator __pos, std::initializer_list<_Tp> __il)
 350     {
 351       _Fwd_list_node_base* __to
 352         = const_cast<_Fwd_list_node_base*>(__pos._M_node);
 353       _Fwd_list_node_base* __keep = __to->_M_next;
 354       const _Tp* __item = __il.begin();
 355       while (__item != __il.end())
 356         {
 357           __to->_M_next = this->_M_create_node(*__item);
 358           __to = __to->_M_next;
 359           ++__item;
 360         }
 361       __to->_M_next = __keep;
 362     }
 363
 364   template<typename _Tp, typename _Alloc>
 365     void
 366     forward_list<_Tp, _Alloc>::
 367     resize(size_type __sz, value_type __val)
 368     {
 369       iterator __k = before_begin();
 370
 371       size_type __len = 0;
 372       while (__k._M_next() != end() && __len < __sz)
 373         {
 374           ++__k;
 375           ++__len;
 376         }
 377       if (__len == __sz)
 378         erase_after(__k, end());
 379       else
 380         insert_after(__k, __sz - __len, __val);
 381     }
 382
 383   template<typename _Tp, typename _Alloc>
 384     void
 385     forward_list<_Tp, _Alloc>::
 386     splice_after(const_iterator __pos, forward_list&& __list)
 387     {
 388       if (!__list.empty() && &__list != this)
 389         {
 390           _Fwd_list_node_base* __tmp
 391             = const_cast<_Fwd_list_node_base*>(__pos._M_node);
 392           const_iterator __before = __list.cbefore_begin();
 393           __tmp->_M_transfer_after(const_cast<_Fwd_list_node_base*>
 394                                    (__before._M_node));
 395         }
 396     }
 397
 398   template<typename _Tp, typename _Alloc>
 399     void
 400     forward_list<_Tp, _Alloc>::
 401     splice_after(const_iterator __pos, forward_list&& __list,
 402                  const_iterator __before, const_iterator __last)
 403     {
 404       _Fwd_list_node_base* __tmp
 405         = const_cast<_Fwd_list_node_base*>(__pos._M_node);
 406       __tmp->_M_transfer_after(const_cast<_Fwd_list_node_base*>
 407                                (__before._M_node),
 408                                const_cast<_Fwd_list_node_base*>
 409                                (__last._M_node));
 410     }
 411
 412   template<typename _Tp, typename _Alloc>
 413     void
 414     forward_list<_Tp, _Alloc>::
 415     remove(const _Tp& __val)
 416     {
 417       _Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
 418       while (_Node* __temp = static_cast<_Node*>(__curr->_M_next))
 419         {
 420           if (__temp->_M_value == __val)
 421             this->_M_erase_after(__curr);
 422           else
 423             __curr = static_cast<_Node*>(__curr->_M_next);
 424         }
 425     }
 426
 427   template<typename _Tp, typename _Alloc>
 428     template<typename _Pred>
 429       void
 430       forward_list<_Tp, _Alloc>::
 431       remove_if(_Pred __pred)
 432       {
 433         _Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
 434         while (_Node* __temp = static_cast<_Node*>(__curr->_M_next))
 435           {
 436             if (__pred(__temp->_M_value))
 437               this->_M_erase_after(__curr);
 438             else
 439               __curr = static_cast<_Node*>(__curr->_M_next);
 440           }
 441       }
 442
 443   template<typename _Tp, typename _Alloc>
 444     void
 445     forward_list<_Tp, _Alloc>::
 446     unique()
 447     {
 448       iterator __first = begin();
 449       iterator __last = end();
 450       if (__first == __last)
 451         return;
 452       iterator __next = __first;
 453       while (++__next != __last)
 454         {
 455           if (*__first == *__next)
 456             erase_after(__first);
 457           else
 458             __first = __next;
 459           __next = __first;
 460         }
 461     }
 462
 463   template<typename _Tp, typename _Alloc>
 464     template<typename _BinPred>
 465       void
 466       forward_list<_Tp, _Alloc>::
 467       unique(_BinPred __binary_pred)
 468       {
 469         iterator __first = begin();
 470         iterator __last = end();
 471         if (__first == __last)
 472           return;
 473         iterator __next = __first;
 474         while (++__next != __last)
 475         {
 476           if (__binary_pred(*__first, *__next))
 477             erase_after(__first);
 478           else
 479             __first = __next;
 480           __next = __first;
 481         }
 482       }
 483
 484   template<typename _Tp, typename _Alloc>
 485     template<typename _Comp>
 486       void
 487       forward_list<_Tp, _Alloc>::
 488       merge(forward_list&& __list, _Comp __comp)
 489       {
 490         _Fwd_list_node_base* __node = &this->_M_impl._M_head;
 491         while (__node->_M_next && __list._M_impl._M_head._M_next)
 492           {
 493             if (__comp(static_cast<_Node*>
 494                        (__list._M_impl._M_head._M_next)->_M_value,
 495                        static_cast<_Node*>
 496                        (__node->_M_next)->_M_value))
 497               __node->_M_transfer_after(&__list._M_impl._M_head,
 498                                         __list._M_impl._M_head._M_next);
 499             __node = __node->_M_next;
 500           }
 501         if (__list._M_impl._M_head._M_next)
 502           {
 503             __node->_M_next = __list._M_impl._M_head._M_next;
 504             __list._M_impl._M_head._M_next = 0;
 505           }
 506       }
 507
 508   template<typename _Tp, typename _Alloc>
 509     void
 510     forward_list<_Tp, _Alloc>::
 511     reverse()
 512     { this->_M_impl._M_head._M_reverse_after(); }
 513
 514   template<typename _Tp, typename _Alloc>
 515     bool
 516     operator==(const forward_list<_Tp, _Alloc>& __lx,
 517                const forward_list<_Tp, _Alloc>& __ly)
 518     {
 519       //  We don't have size() so we need to walk through both lists
 520       //  making sure both iterators are valid.
 521       auto __ix = __lx.cbegin();
 522       auto __iy = __ly.cbegin();
 523       while (__ix != __lx.cend() && __iy != __ly.cend())
 524         {
 525           if (*__ix != *__iy)
 526             return false;
 527           ++__ix;
 528           ++__iy;
 529         }
 530       if (__ix == __lx.cend() && __iy == __ly.cend())
 531         return true;
 532       else
 533         return false;
 534     }
 535
 536 _GLIBCXX_END_NAMESPACE // namespace std
 537
 538 #endif /* _FORWARD_LIST_TCC */
 539