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