libstdc++
|
00001 // <forward_list.tcc> -*- C++ -*- 00002 00003 // Copyright (C) 2008-2018 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 template<typename _Tp, typename _Alloc> 00282 void 00283 forward_list<_Tp, _Alloc>:: 00284 remove(const _Tp& __val) 00285 { 00286 _Node_base* __curr = &this->_M_impl._M_head; 00287 _Node_base* __extra = nullptr; 00288 00289 while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next)) 00290 { 00291 if (*__tmp->_M_valptr() == __val) 00292 { 00293 if (__tmp->_M_valptr() != std::__addressof(__val)) 00294 { 00295 this->_M_erase_after(__curr); 00296 continue; 00297 } 00298 else 00299 __extra = __curr; 00300 } 00301 __curr = __curr->_M_next; 00302 } 00303 00304 if (__extra) 00305 this->_M_erase_after(__extra); 00306 } 00307 00308 template<typename _Tp, typename _Alloc> 00309 template<typename _Pred> 00310 void 00311 forward_list<_Tp, _Alloc>:: 00312 remove_if(_Pred __pred) 00313 { 00314 _Node_base* __curr = &this->_M_impl._M_head; 00315 while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next)) 00316 { 00317 if (__pred(*__tmp->_M_valptr())) 00318 this->_M_erase_after(__curr); 00319 else 00320 __curr = __curr->_M_next; 00321 } 00322 } 00323 00324 template<typename _Tp, typename _Alloc> 00325 template<typename _BinPred> 00326 void 00327 forward_list<_Tp, _Alloc>:: 00328 unique(_BinPred __binary_pred) 00329 { 00330 iterator __first = begin(); 00331 iterator __last = end(); 00332 if (__first == __last) 00333 return; 00334 iterator __next = __first; 00335 while (++__next != __last) 00336 { 00337 if (__binary_pred(*__first, *__next)) 00338 erase_after(__first); 00339 else 00340 __first = __next; 00341 __next = __first; 00342 } 00343 } 00344 00345 template<typename _Tp, typename _Alloc> 00346 template<typename _Comp> 00347 void 00348 forward_list<_Tp, _Alloc>:: 00349 merge(forward_list&& __list, _Comp __comp) 00350 { 00351 _Node_base* __node = &this->_M_impl._M_head; 00352 while (__node->_M_next && __list._M_impl._M_head._M_next) 00353 { 00354 if (__comp(*static_cast<_Node*> 00355 (__list._M_impl._M_head._M_next)->_M_valptr(), 00356 *static_cast<_Node*> 00357 (__node->_M_next)->_M_valptr())) 00358 __node->_M_transfer_after(&__list._M_impl._M_head, 00359 __list._M_impl._M_head._M_next); 00360 __node = __node->_M_next; 00361 } 00362 00363 if (__list._M_impl._M_head._M_next) 00364 *__node = std::move(__list._M_impl._M_head); 00365 } 00366 00367 template<typename _Tp, typename _Alloc> 00368 bool 00369 operator==(const forward_list<_Tp, _Alloc>& __lx, 00370 const forward_list<_Tp, _Alloc>& __ly) 00371 { 00372 // We don't have size() so we need to walk through both lists 00373 // making sure both iterators are valid. 00374 auto __ix = __lx.cbegin(); 00375 auto __iy = __ly.cbegin(); 00376 while (__ix != __lx.cend() && __iy != __ly.cend()) 00377 { 00378 if (*__ix != *__iy) 00379 return false; 00380 ++__ix; 00381 ++__iy; 00382 } 00383 if (__ix == __lx.cend() && __iy == __ly.cend()) 00384 return true; 00385 else 00386 return false; 00387 } 00388 00389 template<typename _Tp, class _Alloc> 00390 template<typename _Comp> 00391 void 00392 forward_list<_Tp, _Alloc>:: 00393 sort(_Comp __comp) 00394 { 00395 // If `next' is nullptr, return immediately. 00396 _Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next); 00397 if (!__list) 00398 return; 00399 00400 unsigned long __insize = 1; 00401 00402 while (1) 00403 { 00404 _Node* __p = __list; 00405 __list = nullptr; 00406 _Node* __tail = nullptr; 00407 00408 // Count number of merges we do in this pass. 00409 unsigned long __nmerges = 0; 00410 00411 while (__p) 00412 { 00413 ++__nmerges; 00414 // There exists a merge to be done. 00415 // Step `insize' places along from p. 00416 _Node* __q = __p; 00417 unsigned long __psize = 0; 00418 for (unsigned long __i = 0; __i < __insize; ++__i) 00419 { 00420 ++__psize; 00421 __q = static_cast<_Node*>(__q->_M_next); 00422 if (!__q) 00423 break; 00424 } 00425 00426 // If q hasn't fallen off end, we have two lists to merge. 00427 unsigned long __qsize = __insize; 00428 00429 // Now we have two lists; merge them. 00430 while (__psize > 0 || (__qsize > 0 && __q)) 00431 { 00432 // Decide whether next node of merge comes from p or q. 00433 _Node* __e; 00434 if (__psize == 0) 00435 { 00436 // p is empty; e must come from q. 00437 __e = __q; 00438 __q = static_cast<_Node*>(__q->_M_next); 00439 --__qsize; 00440 } 00441 else if (__qsize == 0 || !__q) 00442 { 00443 // q is empty; e must come from p. 00444 __e = __p; 00445 __p = static_cast<_Node*>(__p->_M_next); 00446 --__psize; 00447 } 00448 else if (__comp(*__p->_M_valptr(), *__q->_M_valptr())) 00449 { 00450 // First node of p is lower; e must come from p. 00451 __e = __p; 00452 __p = static_cast<_Node*>(__p->_M_next); 00453 --__psize; 00454 } 00455 else 00456 { 00457 // First node of q is lower; e must come from q. 00458 __e = __q; 00459 __q = static_cast<_Node*>(__q->_M_next); 00460 --__qsize; 00461 } 00462 00463 // Add the next node to the merged list. 00464 if (__tail) 00465 __tail->_M_next = __e; 00466 else 00467 __list = __e; 00468 __tail = __e; 00469 } 00470 00471 // Now p has stepped `insize' places along, and q has too. 00472 __p = __q; 00473 } 00474 __tail->_M_next = nullptr; 00475 00476 // If we have done only one merge, we're finished. 00477 // Allow for nmerges == 0, the empty list case. 00478 if (__nmerges <= 1) 00479 { 00480 this->_M_impl._M_head._M_next = __list; 00481 return; 00482 } 00483 00484 // Otherwise repeat, merging lists twice the size. 00485 __insize *= 2; 00486 } 00487 } 00488 00489 _GLIBCXX_END_NAMESPACE_CONTAINER 00490 _GLIBCXX_END_NAMESPACE_VERSION 00491 } // namespace std 00492 00493 #endif /* _FORWARD_LIST_TCC */