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