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