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