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

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