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