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