libstdc++
forward_list.tcc
Go to the documentation of this file.
00001 // <forward_list.tcc> -*- C++ -*-
00002 
00003 // Copyright (C) 2008-2019 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file bits/forward_list.tcc
00026  *  This is an internal header file, included by other library headers.
00027  *  Do not attempt to use it directly. @headername{forward_list}
00028  */
00029 
00030 #ifndef _FORWARD_LIST_TCC
00031 #define _FORWARD_LIST_TCC 1
00032 
00033 namespace std _GLIBCXX_VISIBILITY(default)
00034 {
00035 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00036 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00037 
00038   template<typename _Tp, typename _Alloc>
00039     _Fwd_list_base<_Tp, _Alloc>::
00040     _Fwd_list_base(_Fwd_list_base&& __lst, _Node_alloc_type&& __a)
00041     : _M_impl(std::move(__a))
00042     {
00043       if (__lst._M_get_Node_allocator() == _M_get_Node_allocator())
00044         this->_M_impl._M_head = std::move(__lst._M_impl._M_head);
00045     }
00046 
00047   template<typename _Tp, typename _Alloc>
00048     template<typename... _Args>
00049       _Fwd_list_node_base*
00050       _Fwd_list_base<_Tp, _Alloc>::
00051       _M_insert_after(const_iterator __pos, _Args&&... __args)
00052       {
00053         _Fwd_list_node_base* __to
00054           = const_cast<_Fwd_list_node_base*>(__pos._M_node);
00055         _Node* __thing = _M_create_node(std::forward<_Args>(__args)...);
00056         __thing->_M_next = __to->_M_next;
00057         __to->_M_next = __thing;
00058         return __to->_M_next;
00059       }
00060 
00061   template<typename _Tp, typename _Alloc>
00062     _Fwd_list_node_base*
00063     _Fwd_list_base<_Tp, _Alloc>::
00064     _M_erase_after(_Fwd_list_node_base* __pos)
00065     {
00066       _Node* __curr = static_cast<_Node*>(__pos->_M_next);
00067       __pos->_M_next = __curr->_M_next;
00068       _Node_alloc_traits::destroy(_M_get_Node_allocator(),
00069                                   __curr->_M_valptr());
00070       __curr->~_Node();
00071       _M_put_node(__curr);
00072       return __pos->_M_next;
00073     }
00074 
00075   template<typename _Tp, typename _Alloc>
00076     _Fwd_list_node_base*
00077     _Fwd_list_base<_Tp, _Alloc>::
00078     _M_erase_after(_Fwd_list_node_base* __pos,
00079                    _Fwd_list_node_base* __last)
00080     {
00081       _Node* __curr = static_cast<_Node*>(__pos->_M_next);
00082       while (__curr != __last)
00083         {
00084           _Node* __temp = __curr;
00085           __curr = static_cast<_Node*>(__curr->_M_next);
00086           _Node_alloc_traits::destroy(_M_get_Node_allocator(),
00087                                       __temp->_M_valptr());
00088           __temp->~_Node();
00089           _M_put_node(__temp);
00090         }
00091       __pos->_M_next = __last;
00092       return __last;
00093     }
00094 
00095   // Called by the range constructor to implement [23.3.4.2]/9
00096   template<typename _Tp, typename _Alloc>
00097     template<typename _InputIterator>
00098       void
00099       forward_list<_Tp, _Alloc>::
00100       _M_range_initialize(_InputIterator __first, _InputIterator __last)
00101       {
00102         _Node_base* __to = &this->_M_impl._M_head;
00103         for (; __first != __last; ++__first)
00104           {
00105             __to->_M_next = this->_M_create_node(*__first);
00106             __to = __to->_M_next;
00107           }
00108       }
00109 
00110   // Called by forward_list(n,v,a).
00111   template<typename _Tp, typename _Alloc>
00112     void
00113     forward_list<_Tp, _Alloc>::
00114     _M_fill_initialize(size_type __n, const value_type& __value)
00115     {
00116       _Node_base* __to = &this->_M_impl._M_head;
00117       for (; __n; --__n)
00118         {
00119           __to->_M_next = this->_M_create_node(__value);
00120           __to = __to->_M_next;
00121         }
00122     }
00123 
00124   template<typename _Tp, typename _Alloc>
00125     void
00126     forward_list<_Tp, _Alloc>::
00127     _M_default_initialize(size_type __n)
00128     {
00129       _Node_base* __to = &this->_M_impl._M_head;
00130       for (; __n; --__n)
00131         {
00132           __to->_M_next = this->_M_create_node();
00133           __to = __to->_M_next;
00134         }
00135     }
00136 
00137   template<typename _Tp, typename _Alloc>
00138     forward_list<_Tp, _Alloc>&
00139     forward_list<_Tp, _Alloc>::
00140     operator=(const forward_list& __list)
00141     {
00142       if (std::__addressof(__list) != this)
00143         {
00144           if (_Node_alloc_traits::_S_propagate_on_copy_assign())
00145             {
00146               auto& __this_alloc = this->_M_get_Node_allocator();
00147               auto& __that_alloc = __list._M_get_Node_allocator();
00148               if (!_Node_alloc_traits::_S_always_equal()
00149                   && __this_alloc != __that_alloc)
00150                 {
00151                   // replacement allocator cannot free existing storage
00152                   clear();
00153                 }
00154               std::__alloc_on_copy(__this_alloc, __that_alloc);
00155             }
00156           assign(__list.cbegin(), __list.cend());
00157         }
00158       return *this;
00159     }
00160 
00161   template<typename _Tp, typename _Alloc>
00162     void
00163     forward_list<_Tp, _Alloc>::
00164     _M_default_insert_after(const_iterator __pos, size_type __n)
00165     {
00166       const_iterator __saved_pos = __pos;
00167       __try
00168         {
00169           for (; __n; --__n)
00170             __pos = emplace_after(__pos);
00171         }
00172       __catch(...)
00173         {
00174           erase_after(__saved_pos, ++__pos);
00175           __throw_exception_again;
00176         }
00177     }
00178 
00179   template<typename _Tp, typename _Alloc>
00180     void
00181     forward_list<_Tp, _Alloc>::
00182     resize(size_type __sz)
00183     {
00184       iterator __k = before_begin();
00185 
00186       size_type __len = 0;
00187       while (__k._M_next() != end() && __len < __sz)
00188         {
00189           ++__k;
00190           ++__len;
00191         }
00192       if (__len == __sz)
00193         erase_after(__k, end());
00194       else
00195         _M_default_insert_after(__k, __sz - __len);
00196     }
00197 
00198   template<typename _Tp, typename _Alloc>
00199     void
00200     forward_list<_Tp, _Alloc>::
00201     resize(size_type __sz, const value_type& __val)
00202     {
00203       iterator __k = before_begin();
00204 
00205       size_type __len = 0;
00206       while (__k._M_next() != end() && __len < __sz)
00207         {
00208           ++__k;
00209           ++__len;
00210         }
00211       if (__len == __sz)
00212         erase_after(__k, end());
00213       else
00214         insert_after(__k, __sz - __len, __val);
00215     }
00216 
00217   template<typename _Tp, typename _Alloc>
00218     typename forward_list<_Tp, _Alloc>::iterator
00219     forward_list<_Tp, _Alloc>::
00220     _M_splice_after(const_iterator __pos,
00221                     const_iterator __before, const_iterator __last)
00222     {
00223       _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
00224       _Node_base* __b = const_cast<_Node_base*>(__before._M_node);
00225       _Node_base* __end = __b;
00226 
00227       while (__end && __end->_M_next != __last._M_node)
00228         __end = __end->_M_next;
00229 
00230       if (__b != __end)
00231         return iterator(__tmp->_M_transfer_after(__b, __end));
00232       else
00233         return iterator(__tmp);
00234     }
00235 
00236   template<typename _Tp, typename _Alloc>
00237     void
00238     forward_list<_Tp, _Alloc>::
00239     splice_after(const_iterator __pos, forward_list&&,
00240                  const_iterator __i) noexcept
00241     {
00242       const_iterator __j = __i;
00243       ++__j;
00244 
00245       if (__pos == __i || __pos == __j)
00246         return;
00247 
00248       _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
00249       __tmp->_M_transfer_after(const_cast<_Node_base*>(__i._M_node),
00250                                const_cast<_Node_base*>(__j._M_node));
00251     }
00252 
00253   template<typename _Tp, typename _Alloc>
00254     typename forward_list<_Tp, _Alloc>::iterator
00255     forward_list<_Tp, _Alloc>::
00256     insert_after(const_iterator __pos, size_type __n, const _Tp& __val)
00257     {
00258       if (__n)
00259         {
00260           forward_list __tmp(__n, __val, get_allocator());
00261           return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
00262         }
00263       else
00264         return iterator(const_cast<_Node_base*>(__pos._M_node));
00265     }
00266 
00267   template<typename _Tp, typename _Alloc>
00268     template<typename _InputIterator, typename>
00269       typename forward_list<_Tp, _Alloc>::iterator
00270       forward_list<_Tp, _Alloc>::
00271       insert_after(const_iterator __pos,
00272                    _InputIterator __first, _InputIterator __last)
00273       {
00274         forward_list __tmp(__first, __last, get_allocator());
00275         if (!__tmp.empty())
00276           return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
00277         else
00278           return iterator(const_cast<_Node_base*>(__pos._M_node));
00279       }
00280 
00281 #if __cplusplus > 201703L
00282 # define _GLIBCXX20_ONLY(__expr) __expr
00283 #else
00284 # define _GLIBCXX20_ONLY(__expr)
00285 #endif
00286 
00287   template<typename _Tp, typename _Alloc>
00288     auto
00289     forward_list<_Tp, _Alloc>::
00290     remove(const _Tp& __val) -> __remove_return_type
00291     {
00292       size_type __removed __attribute__((__unused__)) = 0;
00293       _Node_base* __curr = &this->_M_impl._M_head;
00294       _Node_base* __extra = nullptr;
00295 
00296       while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
00297         {
00298           if (*__tmp->_M_valptr() == __val)
00299             {
00300               if (__tmp->_M_valptr() != std::__addressof(__val))
00301                 {
00302                   this->_M_erase_after(__curr);
00303                   _GLIBCXX20_ONLY( __removed++ );
00304                   continue;
00305                 }
00306               else
00307                 __extra = __curr;
00308             }
00309           __curr = __curr->_M_next;
00310         }
00311 
00312       if (__extra)
00313         {
00314           this->_M_erase_after(__extra);
00315           _GLIBCXX20_ONLY( __removed++ );
00316         }
00317       return _GLIBCXX20_ONLY( __removed );
00318     }
00319 
00320   template<typename _Tp, typename _Alloc>
00321     template<typename _Pred>
00322       auto
00323       forward_list<_Tp, _Alloc>::
00324       remove_if(_Pred __pred) -> __remove_return_type
00325       {
00326         size_type __removed __attribute__((__unused__)) = 0;
00327         _Node_base* __curr = &this->_M_impl._M_head;
00328         while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
00329           {
00330             if (__pred(*__tmp->_M_valptr()))
00331               {
00332                 this->_M_erase_after(__curr);
00333                 _GLIBCXX20_ONLY( __removed++ );
00334               }
00335             else
00336               __curr = __curr->_M_next;
00337           }
00338         return _GLIBCXX20_ONLY( __removed );
00339       }
00340 
00341   template<typename _Tp, typename _Alloc>
00342     template<typename _BinPred>
00343       auto
00344       forward_list<_Tp, _Alloc>::
00345       unique(_BinPred __binary_pred) -> __remove_return_type
00346       {
00347         iterator __first = begin();
00348         iterator __last = end();
00349         if (__first == __last)
00350           return _GLIBCXX20_ONLY(0);
00351         size_type __removed __attribute__((__unused__)) = 0;
00352         iterator __next = __first;
00353         while (++__next != __last)
00354         {
00355           if (__binary_pred(*__first, *__next))
00356             {
00357               erase_after(__first);
00358               _GLIBCXX20_ONLY( __removed++ );
00359             }
00360           else
00361             __first = __next;
00362           __next = __first;
00363         }
00364         return _GLIBCXX20_ONLY( __removed );
00365       }
00366 
00367 #undef _GLIBCXX20_ONLY
00368 
00369   template<typename _Tp, typename _Alloc>
00370     template<typename _Comp>
00371       void
00372       forward_list<_Tp, _Alloc>::
00373       merge(forward_list&& __list, _Comp __comp)
00374       {
00375         _Node_base* __node = &this->_M_impl._M_head;
00376         while (__node->_M_next && __list._M_impl._M_head._M_next)
00377           {
00378             if (__comp(*static_cast<_Node*>
00379                        (__list._M_impl._M_head._M_next)->_M_valptr(),
00380                        *static_cast<_Node*>
00381                        (__node->_M_next)->_M_valptr()))
00382               __node->_M_transfer_after(&__list._M_impl._M_head,
00383                                         __list._M_impl._M_head._M_next);
00384             __node = __node->_M_next;
00385           }
00386 
00387         if (__list._M_impl._M_head._M_next)
00388           *__node = std::move(__list._M_impl._M_head);
00389       }
00390 
00391   template<typename _Tp, typename _Alloc>
00392     bool
00393     operator==(const forward_list<_Tp, _Alloc>& __lx,
00394                const forward_list<_Tp, _Alloc>& __ly)
00395     {
00396       //  We don't have size() so we need to walk through both lists
00397       //  making sure both iterators are valid.
00398       auto __ix = __lx.cbegin();
00399       auto __iy = __ly.cbegin();
00400       while (__ix != __lx.cend() && __iy != __ly.cend())
00401         {
00402           if (!(*__ix == *__iy))
00403             return false;
00404           ++__ix;
00405           ++__iy;
00406         }
00407       if (__ix == __lx.cend() && __iy == __ly.cend())
00408         return true;
00409       else
00410         return false;
00411     }
00412 
00413   template<typename _Tp, class _Alloc>
00414     template<typename _Comp>
00415       void
00416       forward_list<_Tp, _Alloc>::
00417       sort(_Comp __comp)
00418       {
00419         // If `next' is nullptr, return immediately.
00420         _Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next);
00421         if (!__list)
00422           return;
00423 
00424         unsigned long __insize = 1;
00425 
00426         while (1)
00427           {
00428             _Node* __p = __list;
00429             __list = nullptr;
00430             _Node* __tail = nullptr;
00431 
00432             // Count number of merges we do in this pass.
00433             unsigned long __nmerges = 0;
00434 
00435             while (__p)
00436               {
00437                 ++__nmerges;
00438                 // There exists a merge to be done.
00439                 // Step `insize' places along from p.
00440                 _Node* __q = __p;
00441                 unsigned long __psize = 0;
00442                 for (unsigned long __i = 0; __i < __insize; ++__i)
00443                   {
00444                     ++__psize;
00445                     __q = static_cast<_Node*>(__q->_M_next);
00446                     if (!__q)
00447                       break;
00448                   }
00449 
00450                 // If q hasn't fallen off end, we have two lists to merge.
00451                 unsigned long __qsize = __insize;
00452 
00453                 // Now we have two lists; merge them.
00454                 while (__psize > 0 || (__qsize > 0 && __q))
00455                   {
00456                     // Decide whether next node of merge comes from p or q.
00457                     _Node* __e;
00458                     if (__psize == 0)
00459                       {
00460                         // p is empty; e must come from q.
00461                         __e = __q;
00462                         __q = static_cast<_Node*>(__q->_M_next);
00463                         --__qsize;
00464                       }
00465                     else if (__qsize == 0 || !__q)
00466                       {
00467                         // q is empty; e must come from p.
00468                         __e = __p;
00469                         __p = static_cast<_Node*>(__p->_M_next);
00470                         --__psize;
00471                       }
00472                     else if (!__comp(*__q->_M_valptr(), *__p->_M_valptr()))
00473                       {
00474                         // First node of q is not lower; e must come from p.
00475                         __e = __p;
00476                         __p = static_cast<_Node*>(__p->_M_next);
00477                         --__psize;
00478                       }
00479                     else
00480                       {
00481                         // First node of q is lower; e must come from q.
00482                         __e = __q;
00483                         __q = static_cast<_Node*>(__q->_M_next);
00484                         --__qsize;
00485                       }
00486 
00487                     // Add the next node to the merged list.
00488                     if (__tail)
00489                       __tail->_M_next = __e;
00490                     else
00491                       __list = __e;
00492                     __tail = __e;
00493                   }
00494 
00495                 // Now p has stepped `insize' places along, and q has too.
00496                 __p = __q;
00497               }
00498             __tail->_M_next = nullptr;
00499 
00500             // If we have done only one merge, we're finished.
00501             // Allow for nmerges == 0, the empty list case.
00502             if (__nmerges <= 1)
00503               {
00504                 this->_M_impl._M_head._M_next = __list;
00505                 return;
00506               }
00507 
00508             // Otherwise repeat, merging lists twice the size.
00509             __insize *= 2;
00510           }
00511       }
00512 
00513 _GLIBCXX_END_NAMESPACE_CONTAINER
00514 _GLIBCXX_END_NAMESPACE_VERSION
00515 } // namespace std
00516 
00517 #endif /* _FORWARD_LIST_TCC */