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

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