libstdc++
|
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 */