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