1 // <forward_list.tcc> -*- C++ -*- 2 3 // Copyright (C) 2008-2022 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file bits/forward_list.tcc 26 * This is an internal header file, included by other library headers. 27 * Do not attempt to use it directly. @headername{forward_list} 28 */ 29 30 #ifndef _FORWARD_LIST_TCC 31 #define _FORWARD_LIST_TCC 1 32 33 namespace std _GLIBCXX_VISIBILITY(default) 34 { 35 _GLIBCXX_BEGIN_NAMESPACE_VERSION 36 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 37 38 template<typename _Tp, typename _Alloc> 39 _Fwd_list_base<_Tp, _Alloc>:: _Fwd_list_base(_Fwd_list_base && __lst,_Node_alloc_type && __a)40 _Fwd_list_base(_Fwd_list_base&& __lst, _Node_alloc_type&& __a) 41 : _M_impl(std::move(__a)) 42 { 43 if (__lst._M_get_Node_allocator() == _M_get_Node_allocator()) 44 this->_M_impl._M_head = std::move(__lst._M_impl._M_head); 45 } 46 47 template<typename _Tp, typename _Alloc> 48 template<typename... _Args> 49 _Fwd_list_node_base* 50 _Fwd_list_base<_Tp, _Alloc>:: _M_insert_after(const_iterator __pos,_Args &&...__args)51 _M_insert_after(const_iterator __pos, _Args&&... __args) 52 { 53 _Fwd_list_node_base* __to 54 = const_cast<_Fwd_list_node_base*>(__pos._M_node); 55 _Node* __thing = _M_create_node(std::forward<_Args>(__args)...); 56 __thing->_M_next = __to->_M_next; 57 __to->_M_next = __thing; 58 return __to->_M_next; 59 } 60 61 template<typename _Tp, typename _Alloc> 62 _Fwd_list_node_base* 63 _Fwd_list_base<_Tp, _Alloc>:: _M_erase_after(_Fwd_list_node_base * __pos)64 _M_erase_after(_Fwd_list_node_base* __pos) 65 { 66 _Node* __curr = static_cast<_Node*>(__pos->_M_next); 67 __pos->_M_next = __curr->_M_next; 68 _Node_alloc_traits::destroy(_M_get_Node_allocator(), 69 __curr->_M_valptr()); 70 __curr->~_Node(); 71 _M_put_node(__curr); 72 return __pos->_M_next; 73 } 74 75 template<typename _Tp, typename _Alloc> 76 _Fwd_list_node_base* 77 _Fwd_list_base<_Tp, _Alloc>:: _M_erase_after(_Fwd_list_node_base * __pos,_Fwd_list_node_base * __last)78 _M_erase_after(_Fwd_list_node_base* __pos, 79 _Fwd_list_node_base* __last) 80 { 81 _Node* __curr = static_cast<_Node*>(__pos->_M_next); 82 while (__curr != __last) 83 { 84 _Node* __temp = __curr; 85 __curr = static_cast<_Node*>(__curr->_M_next); 86 _Node_alloc_traits::destroy(_M_get_Node_allocator(), 87 __temp->_M_valptr()); 88 __temp->~_Node(); 89 _M_put_node(__temp); 90 } 91 __pos->_M_next = __last; 92 return __last; 93 } 94 95 // Called by the range constructor to implement [23.3.4.2]/9 96 template<typename _Tp, typename _Alloc> 97 template<typename _InputIterator> 98 void 99 forward_list<_Tp, _Alloc>:: _M_range_initialize(_InputIterator __first,_InputIterator __last)100 _M_range_initialize(_InputIterator __first, _InputIterator __last) 101 { 102 _Node_base* __to = &this->_M_impl._M_head; 103 for (; __first != __last; ++__first) 104 { 105 __to->_M_next = this->_M_create_node(*__first); 106 __to = __to->_M_next; 107 } 108 } 109 110 // Called by forward_list(n,v,a). 111 template<typename _Tp, typename _Alloc> 112 void 113 forward_list<_Tp, _Alloc>:: _M_fill_initialize(size_type __n,const value_type & __value)114 _M_fill_initialize(size_type __n, const value_type& __value) 115 { 116 _Node_base* __to = &this->_M_impl._M_head; 117 for (; __n; --__n) 118 { 119 __to->_M_next = this->_M_create_node(__value); 120 __to = __to->_M_next; 121 } 122 } 123 124 template<typename _Tp, typename _Alloc> 125 void 126 forward_list<_Tp, _Alloc>:: _M_default_initialize(size_type __n)127 _M_default_initialize(size_type __n) 128 { 129 _Node_base* __to = &this->_M_impl._M_head; 130 for (; __n; --__n) 131 { 132 __to->_M_next = this->_M_create_node(); 133 __to = __to->_M_next; 134 } 135 } 136 137 template<typename _Tp, typename _Alloc> 138 forward_list<_Tp, _Alloc>& 139 forward_list<_Tp, _Alloc>:: operator =(const forward_list & __list)140 operator=(const forward_list& __list) 141 { 142 if (std::__addressof(__list) != this) 143 { 144 if (_Node_alloc_traits::_S_propagate_on_copy_assign()) 145 { 146 auto& __this_alloc = this->_M_get_Node_allocator(); 147 auto& __that_alloc = __list._M_get_Node_allocator(); 148 if (!_Node_alloc_traits::_S_always_equal() 149 && __this_alloc != __that_alloc) 150 { 151 // replacement allocator cannot free existing storage 152 clear(); 153 } 154 std::__alloc_on_copy(__this_alloc, __that_alloc); 155 } 156 assign(__list.cbegin(), __list.cend()); 157 } 158 return *this; 159 } 160 161 template<typename _Tp, typename _Alloc> 162 void 163 forward_list<_Tp, _Alloc>:: _M_default_insert_after(const_iterator __pos,size_type __n)164 _M_default_insert_after(const_iterator __pos, size_type __n) 165 { 166 const_iterator __saved_pos = __pos; 167 __try 168 { 169 for (; __n; --__n) 170 __pos = emplace_after(__pos); 171 } 172 __catch(...) 173 { 174 erase_after(__saved_pos, ++__pos); 175 __throw_exception_again; 176 } 177 } 178 179 template<typename _Tp, typename _Alloc> 180 void 181 forward_list<_Tp, _Alloc>:: resize(size_type __sz)182 resize(size_type __sz) 183 { 184 iterator __k = before_begin(); 185 186 size_type __len = 0; 187 while (__k._M_next() != end() && __len < __sz) 188 { 189 ++__k; 190 ++__len; 191 } 192 if (__len == __sz) 193 erase_after(__k, end()); 194 else 195 _M_default_insert_after(__k, __sz - __len); 196 } 197 198 template<typename _Tp, typename _Alloc> 199 void 200 forward_list<_Tp, _Alloc>:: resize(size_type __sz,const value_type & __val)201 resize(size_type __sz, const value_type& __val) 202 { 203 iterator __k = before_begin(); 204 205 size_type __len = 0; 206 while (__k._M_next() != end() && __len < __sz) 207 { 208 ++__k; 209 ++__len; 210 } 211 if (__len == __sz) 212 erase_after(__k, end()); 213 else 214 insert_after(__k, __sz - __len, __val); 215 } 216 217 template<typename _Tp, typename _Alloc> 218 typename forward_list<_Tp, _Alloc>::iterator 219 forward_list<_Tp, _Alloc>:: _M_splice_after(const_iterator __pos,const_iterator __before,const_iterator __last)220 _M_splice_after(const_iterator __pos, 221 const_iterator __before, const_iterator __last) 222 { 223 _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node); 224 _Node_base* __b = const_cast<_Node_base*>(__before._M_node); 225 _Node_base* __end = __b; 226 227 while (__end && __end->_M_next != __last._M_node) 228 __end = __end->_M_next; 229 230 if (__b != __end) 231 return iterator(__tmp->_M_transfer_after(__b, __end)); 232 else 233 return iterator(__tmp); 234 } 235 236 template<typename _Tp, typename _Alloc> 237 void 238 forward_list<_Tp, _Alloc>:: splice_after(const_iterator __pos,forward_list &&,const_iterator __i)239 splice_after(const_iterator __pos, forward_list&&, 240 const_iterator __i) noexcept 241 { 242 const_iterator __j = __i; 243 ++__j; 244 245 if (__pos == __i || __pos == __j) 246 return; 247 248 _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node); 249 __tmp->_M_transfer_after(const_cast<_Node_base*>(__i._M_node), 250 const_cast<_Node_base*>(__j._M_node)); 251 } 252 253 template<typename _Tp, typename _Alloc> 254 typename forward_list<_Tp, _Alloc>::iterator 255 forward_list<_Tp, _Alloc>:: insert_after(const_iterator __pos,size_type __n,const _Tp & __val)256 insert_after(const_iterator __pos, size_type __n, const _Tp& __val) 257 { 258 if (__n) 259 { 260 forward_list __tmp(__n, __val, get_allocator()); 261 return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end()); 262 } 263 else 264 return iterator(const_cast<_Node_base*>(__pos._M_node)); 265 } 266 267 template<typename _Tp, typename _Alloc> 268 template<typename _InputIterator, typename> 269 typename forward_list<_Tp, _Alloc>::iterator 270 forward_list<_Tp, _Alloc>:: insert_after(const_iterator __pos,_InputIterator __first,_InputIterator __last)271 insert_after(const_iterator __pos, 272 _InputIterator __first, _InputIterator __last) 273 { 274 forward_list __tmp(__first, __last, get_allocator()); 275 if (!__tmp.empty()) 276 return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end()); 277 else 278 return iterator(const_cast<_Node_base*>(__pos._M_node)); 279 } 280 281 #if __cplusplus > 201703L 282 # define _GLIBCXX20_ONLY(__expr) __expr 283 #else 284 # define _GLIBCXX20_ONLY(__expr) 285 #endif 286 287 template<typename _Tp, typename _Alloc> 288 auto 289 forward_list<_Tp, _Alloc>:: remove(const _Tp & __val)290 remove(const _Tp& __val) -> __remove_return_type 291 { 292 size_type __removed __attribute__((__unused__)) = 0; 293 forward_list __to_destroy(get_allocator()); 294 295 auto __prev_it = cbefore_begin(); 296 while (_Node* __tmp = static_cast<_Node*>(__prev_it._M_node->_M_next)) 297 if (*__tmp->_M_valptr() == __val) 298 { 299 __to_destroy.splice_after(__to_destroy.cbefore_begin(), 300 *this, __prev_it); 301 _GLIBCXX20_ONLY( __removed++ ); 302 } 303 else 304 ++__prev_it; 305 306 return _GLIBCXX20_ONLY( __removed ); 307 } 308 309 template<typename _Tp, typename _Alloc> 310 template<typename _Pred> 311 auto 312 forward_list<_Tp, _Alloc>:: remove_if(_Pred __pred)313 remove_if(_Pred __pred) -> __remove_return_type 314 { 315 size_type __removed __attribute__((__unused__)) = 0; 316 forward_list __to_destroy(get_allocator()); 317 318 auto __prev_it = cbefore_begin(); 319 while (_Node* __tmp = static_cast<_Node*>(__prev_it._M_node->_M_next)) 320 if (__pred(*__tmp->_M_valptr())) 321 { 322 __to_destroy.splice_after(__to_destroy.cbefore_begin(), 323 *this, __prev_it); 324 _GLIBCXX20_ONLY( __removed++ ); 325 } 326 else 327 ++__prev_it; 328 329 return _GLIBCXX20_ONLY( __removed ); 330 } 331 332 template<typename _Tp, typename _Alloc> 333 template<typename _BinPred> 334 auto 335 forward_list<_Tp, _Alloc>:: unique(_BinPred __binary_pred)336 unique(_BinPred __binary_pred) -> __remove_return_type 337 { 338 iterator __first = begin(); 339 iterator __last = end(); 340 if (__first == __last) 341 return _GLIBCXX20_ONLY(0); 342 343 forward_list __to_destroy(get_allocator()); 344 size_type __removed __attribute__((__unused__)) = 0; 345 iterator __next = __first; 346 while (++__next != __last) 347 { 348 if (__binary_pred(*__first, *__next)) 349 { 350 __to_destroy.splice_after(__to_destroy.cbefore_begin(), 351 *this, __first); 352 _GLIBCXX20_ONLY( __removed++ ); 353 } 354 else 355 __first = __next; 356 __next = __first; 357 } 358 359 return _GLIBCXX20_ONLY( __removed ); 360 } 361 362 #undef _GLIBCXX20_ONLY 363 364 template<typename _Tp, typename _Alloc> 365 template<typename _Comp> 366 void 367 forward_list<_Tp, _Alloc>:: merge(forward_list && __list,_Comp __comp)368 merge(forward_list&& __list, _Comp __comp) 369 { 370 // _GLIBCXX_RESOLVE_LIB_DEFECTS 371 // 3088. forward_list::merge behavior unclear when passed *this 372 if (std::__addressof(__list) == this) 373 return; 374 375 _Node_base* __node = &this->_M_impl._M_head; 376 while (__node->_M_next && __list._M_impl._M_head._M_next) 377 { 378 if (__comp(*static_cast<_Node*> 379 (__list._M_impl._M_head._M_next)->_M_valptr(), 380 *static_cast<_Node*> 381 (__node->_M_next)->_M_valptr())) 382 __node->_M_transfer_after(&__list._M_impl._M_head, 383 __list._M_impl._M_head._M_next); 384 __node = __node->_M_next; 385 } 386 387 if (__list._M_impl._M_head._M_next) 388 *__node = std::move(__list._M_impl._M_head); 389 } 390 391 template<typename _Tp, typename _Alloc> 392 bool operator ==(const forward_list<_Tp,_Alloc> & __lx,const forward_list<_Tp,_Alloc> & __ly)393 operator==(const forward_list<_Tp, _Alloc>& __lx, 394 const forward_list<_Tp, _Alloc>& __ly) 395 { 396 // We don't have size() so we need to walk through both lists 397 // making sure both iterators are valid. 398 auto __ix = __lx.cbegin(); 399 auto __iy = __ly.cbegin(); 400 while (__ix != __lx.cend() && __iy != __ly.cend()) 401 { 402 if (!(*__ix == *__iy)) 403 return false; 404 ++__ix; 405 ++__iy; 406 } 407 if (__ix == __lx.cend() && __iy == __ly.cend()) 408 return true; 409 else 410 return false; 411 } 412 413 template<typename _Tp, class _Alloc> 414 template<typename _Comp> 415 void 416 forward_list<_Tp, _Alloc>:: sort(_Comp __comp)417 sort(_Comp __comp) 418 { 419 // If `next' is nullptr, return immediately. 420 _Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next); 421 if (!__list) 422 return; 423 424 unsigned long __insize = 1; 425 426 while (1) 427 { 428 _Node* __p = __list; 429 __list = nullptr; 430 _Node* __tail = nullptr; 431 432 // Count number of merges we do in this pass. 433 unsigned long __nmerges = 0; 434 435 while (__p) 436 { 437 ++__nmerges; 438 // There exists a merge to be done. 439 // Step `insize' places along from p. 440 _Node* __q = __p; 441 unsigned long __psize = 0; 442 for (unsigned long __i = 0; __i < __insize; ++__i) 443 { 444 ++__psize; 445 __q = static_cast<_Node*>(__q->_M_next); 446 if (!__q) 447 break; 448 } 449 450 // If q hasn't fallen off end, we have two lists to merge. 451 unsigned long __qsize = __insize; 452 453 // Now we have two lists; merge them. 454 while (__psize > 0 || (__qsize > 0 && __q)) 455 { 456 // Decide whether next node of merge comes from p or q. 457 _Node* __e; 458 if (__psize == 0) 459 { 460 // p is empty; e must come from q. 461 __e = __q; 462 __q = static_cast<_Node*>(__q->_M_next); 463 --__qsize; 464 } 465 else if (__qsize == 0 || !__q) 466 { 467 // q is empty; e must come from p. 468 __e = __p; 469 __p = static_cast<_Node*>(__p->_M_next); 470 --__psize; 471 } 472 else if (!__comp(*__q->_M_valptr(), *__p->_M_valptr())) 473 { 474 // First node of q is not lower; e must come from p. 475 __e = __p; 476 __p = static_cast<_Node*>(__p->_M_next); 477 --__psize; 478 } 479 else 480 { 481 // First node of q is lower; e must come from q. 482 __e = __q; 483 __q = static_cast<_Node*>(__q->_M_next); 484 --__qsize; 485 } 486 487 // Add the next node to the merged list. 488 if (__tail) 489 __tail->_M_next = __e; 490 else 491 __list = __e; 492 __tail = __e; 493 } 494 495 // Now p has stepped `insize' places along, and q has too. 496 __p = __q; 497 } 498 __tail->_M_next = nullptr; 499 500 // If we have done only one merge, we're finished. 501 // Allow for nmerges == 0, the empty list case. 502 if (__nmerges <= 1) 503 { 504 this->_M_impl._M_head._M_next = __list; 505 return; 506 } 507 508 // Otherwise repeat, merging lists twice the size. 509 __insize *= 2; 510 } 511 } 512 513 _GLIBCXX_END_NAMESPACE_CONTAINER 514 _GLIBCXX_END_NAMESPACE_VERSION 515 } // namespace std 516 517 #endif /* _FORWARD_LIST_TCC */ 518