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