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